By extending the baseline processor with application specific instructions, an application specific co-processor can meet the computational demands of the application. Working with the traditional co-processor interface, it doesn't require the extensible processor core and has least impact on the existing hardware and software. This paper proposes a framework for design space exploration and automatic co-processor instructions generation, in which application profiling, instruction identification and evaluation proceed seamlessly and iteratively. The optimal instruction set of the co-processor under given constraints is automatically generated from the source code of the application. To demonstrate the effectiveness of the method we generate the instruction set of a SPARC V8 co-processor for a VoIP application. The experiment gives promising results with the speedup of factor 2.3.