High instruction fetch bandwidth is essential for high performance in today?s wide-issue out-of-order processors. Instruction caches must provide a low miss rate as well as low latency. We introduce Procedure Level Relocation, a class of dynamic feedback-directed optimizations that substantially reduce the instruction cache miss rate by exploiting the temporal locality of procedure usage. Based on the observation that half of all procedures executed are at most 128 bytes in length, we present a Small Procedure Cache, a small and fast explicitly managed memory for storing small procedures. We show that Procedure Level Relocation into a Small Procedure Cache reduces the instruction cache miss rate by an average of 15%.