Lesson 13--Storage Assignment Optimizations Flashcards
Address register
Contains the address of the operand to fetch from memory
Auto increment mode
Get the operand and increment the same instruction. Reduces code size and improves efficiency.
Access Graph
A graph of the access sequence. Unlike an adjacency graph, directions are not material.
Access graph weight
Sum of the edges
Access graph cost
Sum of the weights of the edges in G but not in C, where C is the cover (no cycles and we can remove uncovered edges and the graph will still be connected).
MWPC
Maximum weight per cover
Single Offset Assignment
–Every data object has a size of one word
–A single address register AR) is used to address all variables. Auto increment and decrement are used to transition
–One-to-one mapping of variables to locations
–The basic block has a fixed evaluation order (schedule).
General Offset Assignment
–K address registers Ar0AR(k1)
–Given access sequence L, set of variables V number of address registers k
–Find a partition of V, where m <= k.
–Such that the total cost of the optimal SOA of the corresponding access subsequences plus the setup cost for using the m register is minimal.
Relax fixed evaluation order assumption
Transform the access sequence using algebraic properties to change the access order
Variable coalescence
Putting two variables into the same memory location
Coalesced Node (C-Node)
A set of live ranges in the AG or IG that are coalesced
Coalesced Edge (C-Edge)
An edge set defined for a pair of C-Nodes
Coalesced Access Graph (C-AG)
The AG after coalescence
Coalesced IG (C-IG)
The IG after node coalescence
Coalesced Path Cover (C-PC)
On a C-AG, a C-PC consists of a sequence
