DOC PREVIEW
UCR CS 152 - Final Code Generation

This preview shows page 1-2-3-4-5-6 out of 19 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 19 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 19 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 19 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 19 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 19 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 19 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 19 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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

UCR CS 152 - Final Code Generation

Download Final Code Generation
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Final Code Generation and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Final Code Generation 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?