From:
                                                                   Wed 19:02
Subject: Re: Branch Target Cache (&& AMD 29K)

> BTBs and BTCs are different things. Characterize such structures
> by
> a) how the structure is indexed
> b) what is cached

At the risk of reducing the number of future patent plaques on my wall,
let me enumerate some possible combinations of the above that I
consider "obvious to someone skilled in the art".

Index structure by:
---------------------------

instruction address
branch target address
branch from address
path (sequence of branch from/to addresses)
branch history (taken/not-taken)
procedure call address
procedure call point
branch address (or procedure address) in combination with certain parameter values
basic block number (i.e. transformed branch target address)
data address
address of data referencing instruction (e.g. load at address A accesses B)
memory addressing mode
memory addressing mode and parameters
register version numbers or timestamps

any hash or checksum of the above
        e.g bitfield extracts, shifts, XORs, etc.
linear offsets of any of the above
        denominated in a variety of units such as time, etc.
        e.g. branch from address - 2 instructions
transitive closures of the above
        denominated in a variety of units such as time, same unit, etc.
        e.g. the branch from address 2 branches before the instruction

What is cached
-----------------------

raw instructions
data
branch target address
instructions at branch target
decoded instructions
sequence of instructions at branch target
        possibly beyond multiple branches, e.g. a trace
optimized sequence of instructions at branch target
        where optimizations may include
        a) pre-renaming (relative to trace)
        b) rearranging instructions for schedule
        c) eliminating dead code
        d) common sub expressions detected by hardware
        e) predication to eliminate some branches
type information (e.g. this value is an integer; this value is a pointer)
skip list information
future branch history
future branch path
past branch history
past branch path
schedules indicating expected order of fetch or execution of instructions
cache miss addresses
        absolute, or relative to given data values

compressed versions of the above
combinations of the above - e.g. return both a trace of instructions,
        and a expected cache miss addresses