| Dynamic optimization systems store optimized or translated code in software-managed code caches in order to maximize reuse of transformed code. Code caches store superblocks that are not fixed in size, may contain links to other superblocks, and carry a high replacement overhead. These additional constraints reduce the effectiveness of conventional cache management policies. This dissertation investigates the code cache management problem in dynamic optimization systems and presents three major advances that cover the design space of cache management decisions.;Through code cache simulations, we show that a FIFO replacement policy outperforms other traditional policies, as it enables contiguous cache evictions, allows for a simple circular buffer implementation, and results in comparable cache miss rates to LRU. Furthermore, a pseudo-circular FIFO algorithm is presented, which handles the problem of un-deletable cache blocks.;An investigation of cache eviction granularities also reveals that evicting more than the minimum number of superblocks from the code cache at a time results in less run-time overhead than other alternatives. In high cache pressure situations, the choice of medium-granularity evictions translates into a significant reduction in overall execution time versus both fine and coarse granularities, as the fixed costs of invoking the eviction mechanism can be amortized across multiple cache insertions.;A study of the ideal lifetimes of superblocks in a code cache motivates the design of a global cache management algorithm that leverages generational heuristics to provide for separate code caches for short- and long-lived superblocks. Using this algorithm, short-lived superblocks can easily be removed from a code cache without introducing fragmentation and without suffering the performance penalties associated with evicting long-lived superblocks. The generational code cache algorithm results in an average miss rate reduction of 18% over a unified cache, which translates into 19% fewer instructions spent in the dynamic optimizer.;Finally, an implementation of generational code caches in the DynamoRIO framework reveals important design decisions that affect the performance of code cache management policies, such as support for relocatable code, lightweight link adjustment, and lightweight profiling insertion and removal. As dynamic optimization systems become more prevalent, effective code cache management policies will be essential to reliable, scalable performance. This dissertation presents the first steps in the direction of understanding the behavior of code caches and designing effective code cache replacement policies for modern applications, and opens the doors for follow-up research on cache insertion policies, phase detection, and persistent caches. |
