1. A method, in a data processing system for evicting cache lines from an instruction cache of the data processing system, comprising: storing, by a processor of the data processing system, for a portion of code in a current cache line, a linked list of call sites that directly or indirectly target the portion of code in the current cache line; determining, by the processor, that the current cache line is to be evicted from the instruction cache; and processing, by the processor, the linked list of call sites to identify one or more rewritten branch instructions having associated branch stubs, that either directly or indirectly target the portion of code in the current cache line; and rewriting, by the processor, the one or more rewritten branch instructions to restore the one or more rewritten branch instructions to an original state based on information in the associated branch stubs.