Final Code Generationfront endsrcpgmintermediatecodeo optimizerfinal codegeneratortargetpgmsymbol tableInput to Code Generator:• intermediate code program• symbol tableOutput of Code Generator : target program. Thiscan be any of:• assembly language program• absolute machine-language program• relocatable machine-language program1Translating 3-address code to final codeThis is almost a macro expansion process. Examples:3-Address Code MIPS assembly codex = A[i] load i into reg1la reg2, Aadd reg2, reg2, reg1lw reg2, ( reg2)sw reg2, xx = y+z load y into reg1load z into reg2add reg3, reg1, reg2sw reg3, xif x >= y goto L load x into reg1load y into reg2bge reg1, reg2, LThe resulting code may not be very efficient, but canbe improved via various code optimization techniques.2Improving Code Quality : Peephole OptimizationWe can traverse the sequence of intermediate code in-structions looking for sequences that can be improved.Examples of such improvements include:• redundant instruction elimination, e.g.:. . .goto LL:. . .⇒. . .L:. . .• flow-of-control optimizations, e.g.:. . .goto L1. . .L1: goto L2. . .⇒. . .goto L2. . .L1: goto L2. . .• algebraic simplifications, e.g.:– instructions of the form x := x+0 or x := x*1 canbe eliminated.– special case expressions can be simplified, e.g.:x := 2*y can be simplified to x := y+y.3Improving Code Quality : Register AllocationA value in a register can be accessed much more effi-ciently than one in memory, so we should try to keep(frequently used) values in registers.Local Register Allocation: considers only small seg-ments of code (“basic blocks”) :• If an expression will be used soon after it is evalu-ated, try to compute it into an unused register.• If there are no free registers, we can either computeinto memory (if addressing modes allow), or freeup a register by storing its contents into memory.Choose the register cheapest to store to memoryand least likely to be accessed soon.Global Register Allocation: considers the entire bodyof a function or procedure:• Tries to keep frequently accessed values in registers,esp. across loops.• Uses loop nesting depth as a guide to frequency ofaccess: variables in the most deeply nested loopsare assumed to be accessed the most frequently.4Improving Code Quality : Code Optimization• Examine the program to find out about certainproperties of interest (“Dataflow Analysis”).• Use this information to change the code in a waythat improves performance. (“Code Optimization”).Examples of optimizations include:– Code Motion out of Loops : if a computationinside a loop produces the same result for alliterations (e.g., computing the base address ofa local array), it may be possible to move thecomputation outside the loop.– Common Subexpression Elimination : if the sameexpression is computed in many places (e.g., ar-ray addresse computations; results of macro ex-pansion), compute it once and reuse the result.– Copy Propagation : If we have an intermediatecode “copy” instruction ‘x := y’, replace subse-quent uses of x by y (where possible).– Dead Code Elimination : delete instructions whoseresults are not used.5Basic Blocks and Flow Graphs• For program analysis and optimization, it is usu-ally necessary to know control flow relationshipsbetween different pieces of code.• For this, we:– group 3-address instructions into basic blocks– represent control flow relationships between ba-sic blocks using a control flow graph.Example:L1: if x > y goto L0t1 = x+1x = t1L0: y = 0goto L1⇒x = t1L1:L0:y = 0goto L1if x>y goto L0t1 = x+16Basic BlocksDefinition : A basic block is a sequence of consecutiveinstructions such that:1. control enters at the beginning;2. control leaves at the end; and3. control cannot halt or branch except at the end.Identifying basic blocks :1. Determine the set of leaders, i.e., the first in-struction of each basic block:(a) The first instruction of the function is a leader.(b) Any instruction that is the target of a branchis a leader.(c) Any instruction immediately following a (con-ditional or unconditional) branch is a leader.2. For each leader, its basic block consists of itselfand all instructions upto, but not including, thenext leader (or end of function).7Example/* dot product: prod =NXi=1a[i] ∗ b[i] */No. leader? Instruction basic block(1)√prod = 0 1(2) i = 1 1(3)√t1 = 4*i 2(4) t2 = a[t1] 2(5) t3 = 4*i 2(6) t4 = b[t3] 2(7) t5 = t2*t4 2(8) t6 = prod+t5 2(9) prod = t6 2(10) t7 = i+1 2(11) i = t7 2(12) if i ≤ N goto (3) 28Control Flow GraphsDefinition : A flow graph for a function is a directedgraph G = (V, E) whose nodes are the basic blocksof the function, and where a → b ∈ E iff control canleave a and immediately enter b.The distinguished initial node if a flow graph is thebasic block whose leader is the first instruction ofthe function.Constructing the flow graph of a function :1. Identify the basic blocks of the function.2. There is a directed edge from block B1to blockB2if(a) there is a (conditional or unconditional) jumpfrom the last instruction of B1to the firstinstruction of B2; or(b) B2immediately follows B1in the textual orderof the program, and B1does not end in anunconditional jump.Predecessors and Successors : if there is an edgea → b then a is a precedessor of b, and b is asuccessor of a.9Example :L1: prod = 0i = 1L2: t1 = 4*it2 = a[t1]t3 = 4*it4 = b[t3]t5 = t2*t4t6 = prod+t5prod = t6t7 = i+1i = t7if i ≤ N goto L2⇒prod = 0i = 1t1 = 4 * it2 = a[t1]t3 = 4 * iB2:t4 = b[t2]t5 = t2 * t4t6 = prod + t5prod = t6t7 = i + 1i = t7if i<=N goto B2B1:10Representing Basic Blocks in a Flow GraphMany different representations are possible, with differ-ent tradeoffs. One possibility:struct bblk_struct {int bblno;instruction *first_inst;instruction *last_inst;struct bblk_struct *preds, *succs;struct bblk_struct *prev, *next;/* + information computed during analysis */}11Global Register Allocation by Graph Coloring• When a register is needed but all registers are in use,a register has to be freed by storing its contents inmemory (“spilling”).Graph coloring is a systematic way of allocatingregisters and managing spills.• Graph coloring uses two passes:1. Target machine instructions are selected as thoughthere are infinitely many symbolic registers.2. Physical registers are assigned to symbolic reg-isters in a way that minimizes the cost of spills.• Basic Idea: Construct an interference graph:Nodes : symbolic
View Full Document