Extensible embedded processors allow the designer to adapt the instruction set to a certain application profile. It is either done during design time or at run time. In the latter case it is fixed when which part of the instruction set is used. The processor is then configured according to a predefined schedule. Our approach goes a step further: our extensible processor is self-adaptive. That means, during run time the processor analyzes the usage of Special Instructions and self-adapts when and how these are used and configured. We show that this kind of self-adaptation leads to a high efficiency (e.g. performance per chip area, etc.) and is superior to state-of-the-art extensible processors. In this paper we present the main techniques of our novel self-adaptive approach. We evaluate by means of an H. 264 Video Encoder.