The last decade has witnessed the emergence of the application-specific instruction-set processor (ASIP) as a viable platform for embedded systems. Extensible ASIPs allow the user to augment a base processor with instruction set extensions (ISEs) that execute on dedicated hardware application-specific functional units (AFUs). Due to the limited number of read and write ports in the register file of the base processor, the size and complexity of AFUs are generally limited. Recent papers have focused on overcoming these constraints by serializing access to the register file. Exhaustive ISE enumeration methods are not scalable and generally fail for larger applications and register files with a large number of read and write ports. To address this concern, a new approach to ISE identification is proposed. The approach presented in this paper significantly prunes the list of the best possible ISE candidates compared to previous approaches. Experimentally, we observe that the new approach produces optimal results on larger applications where prior approaches either fail or produce inferior results.