  Many contemporary applications feature multi-megabyte instruction footprints
that overwhelm the capacity of branch target buffers (BTB) and instruction
caches (L1-I), causing frequent front-end stalls that inevitably hurt
performance. BTB capacity is crucial for performance as a sufficiently large
BTB enables the front-end to accurately resolve the upcoming execution path and
steer instruction fetch appropriately. Moreover, it also enables highly
effective fetch-directed instruction prefetching that can eliminate a large
portion L1-I misses. For these reasons, commercial processors allocate vast
amounts of storage capacity to BTBs.
  This work aims to reduce BTB storage requirements by optimizing the
organization of BTB entries. Our key insight is that storing branch target
offsets, instead of full or compressed targets, can drastically reduce BTB
storage cost as the vast majority of dynamic branches have short offsets
requiring just a handful of bits to encode. Based on this insight, we size the
ways of a set associative BTB to hold different number of target offset bits
such that each way stores offsets within a particular range. Doing so enables a
dramatic reduction in storage for target addresses. Our final design, called
BTB-X, uses an 8-way set associative BTB with differently sized ways that
enables it to track about 2.24x more branches than a conventional BTB and 1.3x
more branches than a storage-optimized state-of-the-art BTB organization,
called PDede, with the same storage budget.
