Use auxiliary table to track register use. Register Allocation for Expressions Choice of evaluation order can affect number of registers needed. If we compute left child first, need 4 regs, but doing right child first needs only 3. Can then save result of this evaluation in a register while doing other subtree. Label each node with minimum number of registers needed to evaluate subtree.
Registers behave like a cache for memory locations.
To determine how long to keep a given variable in a register, need to know the range of instructions for which the variable is live . A variable is live immediately following an instruction if its current value will be needed in the future. It's easy to calculate live ranges within a basic block, just by working backwards through the block. Can assume that all user variables are live at the end of a basic block, i.e., that their values may be used in a subsequent block. Can improve accuracy by calculating liveness over entire routines, including control flow statements, not just BBs.