### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# LANG COMPILER DESIGN CS 322

PSU

GPA 3.91

### View Full Document

## 7

## 0

## Popular in Course

## Popular in ComputerScienence

This 233 page Class Notes was uploaded by Orrin Rutherford on Tuesday September 1, 2015. The Class Notes belongs to CS 322 at Portland State University taught by Harry Porter in Fall. Since its upload, it has received 7 views. For similar materials see /class/168280/cs-322-portland-state-university in ComputerScienence at Portland State University.

## Reviews for LANG COMPILER DESIGN

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 09/01/15

CS322 Target Generation Part 2 Code Generation Algorithm 2 Focus on one Basic Block at a time Ignore all other basic blocks 0 Generate best possible code for the basic block 3 Harry H Porter 2006 CS322 Target Generation Part 2 Code Generation Algorithms 2 and 3 Focus on one Basic Block at a time Ignore all other basic blocks 0 Generate best possible code for the basic block Register Strategy 0 Store all LIVE variables in memory between basic blocks 0 Within each basic block Use registers for variables and computation as necessary 0 Each basic block will use registers independently of other basic blocks 3 Harry H Porter 2006 CS322 Target Generation Part 2 Q Why store all variables at the end of each Basic Block Why not leave them in registers 3 Harry H Porter 2006 CS322 Target Generation Part 2 Q Why store all variables at the end of each Basic Block Why not leave them in registers A Each Basic Block is processed in isolation A variable might be put in different registers in different blocks 3 Harry H Porter 2006 CS322 Target Generation Part 2 Q Why store all variables at the end of each Basic Block A Each Basic Block is processed in isolation A variable might be put in different registers in different blocks Why not leave them in registers An Alternate Approach Assign X to one register for the entire routine S B at that ties up a register for too much time Harry H Porter 2006 5 CS322 Target Generation Part 2 We Need Live Variable Information We ll need to know which variables are LIVE at the end of each basic block We ll only store LIVE variables at the end of each Basic Block 3 Harry H Porter 2006 CS322 Target Generation Part 2 We Need Live Variable Information We ll need to know which variables are LIVE at the end of each basic block Option 1 Perform live variable analysis beforehand during optimization phase We ll only store LIVE variables at the end of each Basic Block 3 Harry H Porter 2006 CS322 Target Generation Part 2 We Need Live Variable Information We ll need to know which variables are LIVE at the end of each basic block Option 1 Perform live variable analysis beforehand during optimization phase We ll only store LIVE variables at the end of 0 tion 2 each Basic Block Assume every variable is live at the end of every basic block 3 Harry H Porter 2006 CS322 Target Generation Part 2 We Need Live Variable Information We ll need to know which variables are LIVE at the end of each basic block Option 1 Perform live variable analysis beforehand during optimization phase We ll only store LIVE variables at the end of 0 tion 2 each Basic Block Assume every variable is live at the end of every basic block Option 3 Distinguish temporaries from normal variables Assume temps are not live between blocks Assume normal variables are live between blocks For more precision we may want to distinguish which variables are in any UseBi sets 3 Harry H Porter 2006 CS322 Target Generation Part 2 Definition and Use of Variables A Definition of variable X is an instruction that changes the value x A Use of X is an instruction that reads or uses the value x This statement defines y 104 y a 5 10 5 z What are the next uses of the 106 b 2 y b variable it defines 107 stmts 106 109 112 108 109 y ifcontrol ow could allow this 110 x value to reach these uses 111 112 c y b 3 Harry H Porter 20 06 1 0 CS322 Target Generation Part 2 The NextUse Information Consider a bunch of statements Some of the statements define variables For each definition we want to know What are its NextUses What statements use the value assigned in the definition Control ow must be able to go from the definition to the use without any intervening definitions For each statement we want to know What are its NextUses Defs Next Uses 104 y a 5 105 106 b y b 104 106109112 107 105 108 106 109110 1091 X by 107 110 b b x 108 111 112 c y b 3 Harry H Porter 2006 CS322 Target Generation Part 2 NextUse Algorithm Goal Process a single basic block Compute the NextUse info For each IR instruction X y 2 For each variable in the instruction eg X y 2 Determine Is the variable LIVE or DEAD after the instruction If it is LIVE then Is it used again in this block If so where is it used next Assumption We already have LIVENESS info for all variables at the end of the block 3 Harry H Porter 2006 CS322 Target Generation Part 2 11 t1 1 4 1 lt t1L2 113 21 t2 1 alt t2L5 aL0 3 t3 1 4 i t3L4 iL8 11 t4 I 31 t4L5 bL0 51 t5 1 t2 14 lt t516 t2D 61 t6 1 Pr d t5 t617 prodzD 71 Pr d 16 prodsz t6D 8 t7 1 1 1 lt t7L9 113 93 i 37 lt iL10 t7D 10 if i lt 20 gOtOe iLo Keg L 4 Live nextuse in statement 4 L 0 Live n0 nextuse in this block D Dead t3D t4D t5D 3 Harry H Porter 2006 CS322 Target Generation Part 2 13 NextUse Algorithm 0 Identify all variables used in this block 0 Use a table One entry for each variable For each variable store Its current status LIVE 0r DEAD If LIVE its nextuse in this block 0n0t used again in this block 0 Start with the LIVEness info at the BOTTOM of the block 0 Work through the block in reverse order instructionbyinstruction 0 Update the table as we go upward A temporary data structure used only for this algorithm Implementation Idea Add fields to VarDecl to hold this info 3 Harry H Porter 2006 14 CS322 Target Generation Part 2 medo mhWNH 39139 U1 H 3 Harry H Porter 2006 4 i at1 4 i bt3 t2 t4 prod t5 t6 i1 if i lt 20 goto CS322 Target Generation Part 2 15 t1 t2 OkOCDxlthUanNH 39139 U1 H 3 Harry H Porter 2006 4 i at1 4 i bt3 t2 t4 16 CS322 Target Generation Part 2 medo mhWNH 39139 U1 H 3 Harry H Porter 2006 4 i at1 4 i bt3 t2 t4 prod t5 t6 i1 1f 1 lt 20 gotoe isz t1 D t2 D t3 D t4 D t5 D t6 D t7 D a L0 b L0 prod L0 i L10 CS322 Target Generation Part 2 17 t1 t2 medo mhWNH 39139 U1 H 3 Harry H Porter 2006 4 i at1 4 i bt3 t2 t4 iL10 if i lt 20 gOtOe iLo t1 D t2 D t3 D t4 D t5 D t6 D t7 D a39 L0 b L0 prod L0 i39 L10 t7 D 18 CS322 Target Generation Part 2 1 t1 4 i 2 t2 at1 3 t3 4 i 4 t4 bt3 5 t5 t2 t4 6 t6 prod t5 7 prod t6 8 t7 i 1 93 i 37 lt iL10 t7D 10 if i lt 20 gOtOe iLo t1 D t2 D t3 D t4 D t5 D t6 D t7 L9 a LO b LO prod LO i n 3 Harry H Porter 2006 CS322 Target Generation Part 2 1 t1 4 i 2 t2 at1 3 t3 4 i 4 t4 bt3 5 t5 t2 t4 6 t6 prod t5 7 prod t6 8 F7 i 1 lt t7L9 113 93 1 37 lt iL10 t7D 10 if i lt 20 gOtOe iLo t1 D t2 D t3 D t4 D t5 D t6 D t739 L9 a LO b LO prod LO 3 Harry H Porter 2006 l CS322 Target Generation Part 2 medo mhWNH 39139 U1 H 3 Harry H Porter 2006 4 i at1 4 i bt3 t2 t4 prod t5 t6 1 1 lt t7L9 37 lt iL10 1f 1 lt 20 gotoe 1mm t1 D t2 D t3 D t4 D t5 D t6 D t7 D a L0 b L0 prod L0 i L8 iD t7D CS322 Target Generation Part 2 21 t1 t2 medo mhWNH 39139 U1 H 3 Harry H Porter 2006 4 i at1 4 i bt3 t2 t4 prod t5 1 16 prodsz t6D 1 1 lt t7L9 iD 37 lt iL10 t7D 1f 1 lt 20 gotoe 1mm t1 D t2 D t3 D t4 D t5 D t6 D t7 D a L0 b L0 prod L0 i L8 22 CS322 Target Generation Part 2 1 t1 4 i 2 t2 at1 3 t3 4 i 4 t4 bt3 5 t5 t2 t4 6 t6 prod t5 71 Pr d 1 16 prodsz t6D 8 F7 1 1 lt t7L9 113 93 1 17 lt iL10 t7D 10 if i lt 20 gOtOe iLo t1 D t2 D t3 D t4 D t5 D t6 L7 t7 D a LO b LO prod D i L8 3 Harry H Porter 2006 CS322 Target Generation Part 2 1 t1 4 i 2 t2 at1 3 t3 4 i 4 t4 bt3 5 t5 t2 t4 61 t6 Pr d t5 t617 prodD t5D 71 Pr d 1 16 prodsz t6D 8 F7 1 1 lt t7L9 113 93 1 17 lt iL10 t7D 10 if i lt 20 gOtOe iLo t1 D t2 D t3 D t4 D t5 D t6 L7 t7 D a LO b LO prod D i L8 3 Harry H Porter 2006 CS322 Target Generation Part 2 1 t1 4 i 2 t2 at1 3 t3 4 i 4 t4 bt3 5 t5 t2 t4 61 t6 Pr d t5 1e17 prodzD t5D 71 Pr d 1 16 lt prodL0 t6D 8 F7 1 1 lt t7L9 113 93 1 17 lt iL10 t7D 10 if i lt 20 gOtOe iLo t1 D t2 D t3 D t4 D t5 L6 t6 D t7 D a L0 b L0 prod L6 i L8 3 Harry H Porter 2006 CS322 Target Generation Part 2 1 t1 4 i 2 t2 at1 3 t3 4 i 4 t4 bt3 51 t5 t2 14 lt t516 t2D t4D 61 t6 Pr d t5 1e17 prodzD t5D 71 Pr d 1 16 lt prodL0 t6D 8 F7 1 1 lt t7L9 113 93 1 17 lt iL10 t7D 10 if i lt 20 gOtOe iLo t1 D t2 D t3 D t4 D t5 L6 t6 D t7 D a L0 b L0 prod L6 i L8 3 Harry H Porter 2006 CS322 Target Generation Part 2 1 t1 4 i 2 t2 at1 3 t3 4 i 4 t4 bt3 51 t5 t2 14 lt t516 t2D t4D 61 t6 Pr d t5 1e17 prodzD t5D 71 Pr d 16 lt prodL0 t6D 8 t7 i 1 lt t7L9 113 93 i 37 lt iL10 t7D 10 if i lt 20 gOtOe iLo t1 D t2 L5 t3 D t4 L5 t5 D t6 D t7 D a LO b LO prod L6 i L8 3 Harry H Porter 2006 CS322 Target Generation Part 2 1 t1 4 i 2 t2 at1 3 t3 4 i 41 t4 131 lt t4L5 bL0 t3D 51 t5 t2 14 lt t516 t2D t4D 61 t6 Pr d t5 1e17 prodzD t5D 71 Pr d 1 16 lt prodL0 t6D 8 t7 i 1 lt t7L9 113 93 i 37 lt iL10 t7D 10 if i lt 20 3 Harry H Porter 2006 gOtOe iLo t1 D t2 L5 t3 D t4 L5 t5 D t6 D t7 D a LO b LO prod L6 i L8 28 CS322 Target Generation Part 2 1 t1 4 i 2 t2 at1 3 t3 4 i 4 t4 113 lt t4L5 bL0 t3D 51 t5 t2 14 lt t516 tzD t4D 61 t6 Pr d t5 1e17 prodzD t5D 71 Pr d 1 16 lt prodL0 t6D 8 F7 1 1 lt t7L9 113 93 1 1 17 lt iL10 t7D 10 if i lt 20 gOtOe iLo t1 D t2 L5 t3 L4 t4 D t5 D t6 D t7 D a L0 b L4 prod L6 i L8 3 Harry H Porter 2006 CS322 Target Generation Part 2 1 t1 4 i 2 t2 at1 3 t3 4 1 t3L4 iL8 41 t4 131 lt t4L5 bL0 t3D 51 t5 t2 14 lt t516 t2D t4D 61 t6 Pr d t5 1e17 prodzD t5D 71 Pr d 1 16 lt prodL0 t6D 8 F7 1 1 lt t7L9 113 93 1 17 lt iL10 t7D 10 if i lt 20 gOtOe iLo t1 D t2 L5 t3 L4 t4 D t5 D t6 D t7 D a L0 b L4 prod L6 i L8 3 Harry H Porter 2006 CS322 Target Generation Part 2 1 t1 4 i 2 t2 at1 3 t3 4 1 t3L4 iL8 11 t4 113 lt t4L5 bL0 t3D 51 t5 t2 14 lt t516 t2D t4D 61 t6 Pr d t5 1e17 prodzD t5D 71 Pr d 1 16 lt prodL0 t6D 8 F7 1 1 lt t7L9 113 93 1 17 lt iL10 t7D 10 if i lt 20 gOtOe iLo t1 D t2 L5 t3 D t4 D t5 D t6 D t7 D a L0 b L4 prod L6 i L3 3 Harry H Porter 2006 CS322 Target Generation Part 2 1 t1 4 i 21 t2 at11 lt t2L5 aL0 t1D 3 t3 4 1 t3L4 iL8 41 t4 131 lt t4L5 bL0 t3D 51 t5 t2 14 lt t516 t2D t4D 61 t6 Pr d t5 1e17 prodzD t5D 71 Pr d 1 16 lt prodL0 t6D 8 F7 1 1 lt t7L9 113 93 1 17 lt iL10 t7D 10 if i lt 20 gOtOe iLo t1 D t2 L5 t3 D t4 D t5 D t6 D t7 D a L0 b L4 prod L6 i L3 3 Harry H Porter 2006 CS322 Target Generation Part 2 1 t1 4 i 21 t2 at11 t2L5 aL0 t1D 3 t3 4 1 t3L4 iL8 11 t4 113 lt t4L5 bL0 t3D 51 t5 t2 14 lt t516 t2D t4D 61 t6 Pr d t5 t617 prodzD t5D 71 Pr d 1 16 prodsz t6D 8 F7 1 1 lt t7L9 113 93 1 17 lt iL10 t7D 10 if i lt 20 gOtOe iLo t1 L2 t2 D t3 D t4 D t5 D t6 D t7 D a L2 b L4 prod L6 i L3 3 Harry H Porter 2006 CS322 Target Generation Part 2 11 t1 4 1 lt t1L2 113 21 t2 at11 lt t2L5 aL0 t1D 3 t3 4 1 t3L4 iL8 41 t4 131 lt t4L5 bL0 t3D 51 t5 t2 14 lt t516 t2D t4D 61 t6 Pr d t5 t617 prodzD t5D 71 Pr d 1 16 prodsz t6D 8 F7 1 1 lt t7L9 113 93 1 17 lt iL10 t7D 10 if i lt 20 gOtOe iLo t1 L2 t2 D t3 D t4 D t5 D t6 D t7 D a L2 b L4 prod L6 i L3 3 Harry H Porter 2006 CS322 Target Generation Part 2 Algorithm gin more detail INITIALIZE the table Use results from LIVEVARIABLE ANALYSIS if available Else set all variables to L0 LIVE after this block Go through the instructions in REVERSE order Let x be the variable DEFINED in any LEt y1 y2 be any USED variables FOR each instruction m Let the instruction be 5 t5 t2 t4 n x yl y2 Look up the current status of each variable x yl y2 Fill in the NEXTUSE info for this instruction NOTE Could have the same variab being DEFINED and USED 1 I 1 Must set status of the DEFINED Set the status of x to D Set the status of yl to L n variable rst Set the status of y2 to L n ENDFOR Then setchange the status of the USED variables 3 Harry H Porter 2006 CS322 Target Generation Part 2 The Point of This x y 68 0 If the de ned variable is DEAD after this statement Eliminate the statement 0 If the de ned variable is LIVE but has no NextUse in this block No need to keep it in a register Write back to memory immediately 0 If a used variable is DEAD We can reuse its register Example ltAssume y is in R4gt SUB 68R4 MOV R4 x Otherwise use another register R4R5 SUB 68R5 MOV R5 x 3 Harry H Porter 2006 CS322 Target Generation Part 2 WM 0 Generate code for each Basic Block in isolation Assume that NextUse info is available see previous algorithm 0 Go through the statements in FORWARD order 0 Try to keep variables in registers eave as long as possible in register Store back to memory only when necessary Some variables may be left in registers for several instructions 0 At the end of the basic block Move all LIVE variables back to memory Data Structure From statement to statement we need to remember For each variable Is it in a register Which one For each register Which variables does it contain if any 3 Harry H Porter 2006 CS322 Target Generation Part 2 Example IR Code Code Gen Alg 1 Code Gen Alg 2 t1 43 a 3 Harry H Porter 2006 CS322 Target Generation Part 2 Example IR Code Code Gen Alg 1 Code Gen Alg 2 t1 43 a LD aR1 MUI 43121 ST R1t1 t1 t1 7 LD t1 R1 ADD 7121 ST R1t1 a t1 4 LD t1 R1 MUI 4121 ST R1a 3 Harry H Porter 2006 CS322 Target Generation Part 2 Example IR Code Code Gen Alg 1 Code Gen Alg 2 t1 43 a LD aR1 LD aR1 MUI 43121 MUL 43121 Assuming t1 is LIVE at the end of the block we need to store it If t1 is DEAD this instruction would be omitted 3 Harry H Porter 2006 CS322 Target Generation Part 2 Data Needed During Code Generation Register Descriptors For each register which variables are currently stored in the register Initially all registers are marked EMPTY Variable Descriptors For each variable where is its value currently stored Registers Memo 0 Some combination Initially all variables Will be marked in MEMORY 3 Harry H Porter 2006 CS322 Target Generation Part 2 Code Generation Algorithm 2 Overview Initialize REGISTERDESCRIPTORS t0 EMPTY Initialize VARIABLEDESCRIPTORS to in MEMORY FOR EACH IR Statement E h 1 Let X be the defined variable if any 0t ers are sum ar Let y and 1 be the used variables if any i I Y 39 z 1 Y At thispoint the REGISTERDESCRIPTORS if Y lt Z g t and VARIABLEDESCRIPTORS tell what is in regs and where the variables are stored Step 1 Determine Where we will be storin the result value Call it DEST Step 2 Move y into DEST Step 3 Figure out Where z is Generate the instruction Step 4 Update REGISTERDESCRIPTORS and VARIABLEDESCRIPTORS ENDFOR Generate stores for all LIVE variables 3 Harry H Porter 2006 CS322 Target Generation Part 2 Stepl Determine Where to put the result In Register In Memory b Set DEST R7 Example IR instruction a c Might generate this SUB R7 Or this SUB 3 Harry H Porter 2006 CS322 Target Generation Part 2 Set DEST a a 43 y is already in a register call it Ri AND y is DEAD after this statement AND Ri holds no other variables THEN DEST Ri Modify the descriptors to say that y is not in Ri anymore ELSE E any register is empty THEN Let DEST R where Rj is an empty register ELSE E x has a NleXt Use in this block the operator 9 requires a register for its destination THEN Select an occupied register call it Rk How to choose R If the vars in some reg are also in mem no spills necessary If the Next Uses of vars in some reg are distant choose it Generate SPILL instructions as necessary Assume that REG CONTENTS Rk Vw Generate ST Rk v ST Rk w DEST Rk ELSE N0 NextUse in this block Put the result straight into memory X DES END m SHarry H Porter 2006 44 CS322 Target Generation Part 2 Step 2 Determine the location of y and get y into DEST if not already there IF y is in a register THEN The register containing y LOCy Ry ELSE LOCy y The memory address of y ENDIF E LOCy 9 DEST THEN Generate the instruction LD MOV LOCY DEST ENDIF 3 Harry H Porter 2006 CS322 Target Generation Part 2 Step 3 Generate the instruction that performs the actual operation Let LOCz be the location of z If z is both in memory and a register we prefer to use the register Generate the instruction SUB LOCz DEST 0r whatever operation is involved Update the VARIABLEDESCRIPTOR for X to show that it is in DEST only If DEST is a register update its REGISTERDESCRIPTOR to show that it contains only X 3 Harry H Porter 2006 CS322 Target Generation Part 2 Step 4 Update REGISTERDESCRIPTORS and VARIABLEDESCRIPTORS for y and z m y is in a register call it Ry AND y has no NextUse in this block THEN m y is LIVE THEN Generate a SPILL instruction ST Ry 3 END Modify Descriptors to say that y is no longer in any register D IF z is in a register AND 1 has no NextUse m z is LIVE Generate a SPILL instruction Same for 2 END Modify END 3 Harry H Porter 2006 CS322 Target Generation Part 2 47 Special Case The assign IR Instruction xy Register Descriptors Ify is in a register Don t generate any code Just modify the descriptors Variable Descriptors 3 Harry H Porter 2006 48 CS322 Target Generation Part 2 Special Case The assign IR Instruction x z y Register Descriptors Ify is in a register Don t generate any code Just modify the descriptors Variable Descriptors x R6 y R5 9 gt R5 x y R6 EMPTY x R5 y R5 3 Harry H Porter 2006 CS322 Target Generation Part 2 49 FOR each variable X that is LIVE at the end of the Basic Block Look at X s Variable Descriptor m X is only in a register THEN Generate ST R llx END END At the End of the Basic Block After processing all IR statements in the Basic Block generate SPILL instructions for any LIVE variables 3 Harry H Porter 2006 50 CS322 Target Generation Part 2 Example IR Instructions Target Code Register Descriptors t1 b c Variable Descriptors Assume DEAD after block 3 Harry H Porter 2006 CS322 Target Generation Part 2 Example IR Instructions Target Code Register Descriptors t1 b c LD bR0 ADD cR0 Variable Descriptors Assume DEAD after block 3 Harry H Porter 2006 CS322 Target Generation Part 2 Example IR Instructions Target Code Register Descriptors t1 b c LD bR0 ADD cR0 Variable Descriptors a DEM b DEM c DEM d DEM t1 R0 12 Assume DEAD t3 after block 3 Harry H Porter 2006 CS322 Target Generation Part 2 Example IR Instructions Target Code Register Descriptors t1 b c LD bR0 ADD cR0 Variable Descriptors a DEM b DEM c DEM d DEM t1 R0 12 Assume DEAD t3 after block 3 Harry H Porter 2006 CS322 Target Generation Part 2 Example IR Instructions Target Code Register Descriptors t1 b c LD bR0 ADD cR0 LD bR1 ma MUL dR1 Variable Descriptors a DEM b DEM c DEM d DEM t1 R0 12 Assume DEAD t3 after block 3 Harry H Porter 2006 CS322 Target Generation Part 2 Example IR Instructions Target Code Register Descriptors t1 b c LD bR0 ADD cR0 LD bR1 ma MUL dR1 Variable Descriptors a DEM b DEM c DEM d DEM t1 R0 Assume DEAD 2 51 after block 3 Harry H Porter 2006 CS322 Target Generation Part 2 Example IR Instructions Target Code Register Descriptors t1 b c LD bR0 ADD cR0 LD bR1 ma MUL dR1 E t t1t2 Variable Descriptors a DEM b DEM c DEM d DEM t1 R0 Assume DEAD 2 51 after block 3 Harry H Porter 2006 CS322 Target Generation Part 2 Example IR Instructions Target Code Register Descriptors t1 b c LD bR0 ADD cR0 LD bR1 ma MUL dR1 t1 t2 t m M RllRo Variable Descriptors a DEM b DEM c DEM d DEM t1 R0 Assume DEAD 2 51 after block 3 Harry H Porter 2006 CS322 Target Generation Part 2 Example IR Instructions Target Code Register Descriptors t1 b c LD bR0 ADD cR0 t2 b d LD bR1 W MUL dR1 t t1 t2 MUI39 Rl Ro Variable Descriptors a DEM b DEM c DEM d DEM t1 t2 R1 t3 R0 Assume DEAD after block 3 Harry H Porter 2006 CS322 Target Generation Part 2 59 Example IR Instructions Target Code Register Descriptors t1 b c LD bR0 ADD cR0 t2 b d LD bR1 W MUL dR1 1 t1 t2 m MUI39 Rl Ro Variable Descriptors a t3 t2 a c DEM d DEM t1 t2 R1 t3 R0 Assume DEAD after block 3 Harry H Porter 2006 60 CS322 Target Generation Part 2 Example IR Instructions Target Code Register Descriptors t1 b c LD bR0 ADD cR0 LD bR1 ma MUL dR1 MUL R1R0 Variable Descriptors R1 a b MEM c d MEM t1 A DEAD 12 R1 ssume FT after block 3 Harry H Porter 2006 CS322 Target Generation Part 2 Example IR Instructions Target Code Register Descriptors t1 b c LD bR0 ADD cR0 LD bR1 ma MUL dR1 t t1t2 MUI39 R1 R0 Variable Descriptors at3 t2 R1 Assume DEAD after block 3 Harry H Porter 2006 CS322 Target Generation Part 2 Example IR Instructions Target Code Register Descriptors t1 b c LD bR0 ADD cR0 t2 b 6 LD bR1 ma MUL dR1 t t1 t2 MUI39 R1 R0 Variable Descriptors at3 t2 R1 ltEnd of blockgt Assume LIVE need to save Assume DEAD after block 3 Harry H Porter 2006 CS322 Target Generation Part 2 Example IR Instructions Target Code Register Descriptors t1 b c LD bR0 ADD cR0 t2 b 6 LD bR1 ma MUL dR1 t t1 t2 MUI39 R1 R0 Variable Descriptors at3 t2 SUB R1R0 Assume LIVE need to save ltEnd of blockgt ST R0 a Assume DEAD after block 3 Harry H Porter 2006 CS322 Code GenerationPart 3 During IR generation do we make use of target machine specifics 0 Addressing modes 0 Specific weird instructions 0 Size of data N 0 Isolate machine dependencies in final code generation To retarget the compiler Replace the nal code generation Don t need to modify IR code generation Optimization phase Yes IR code generator creates more specific code The optimizer can improve this code Example gt 3 Harry H Porter 2006 CS322 Code GenerationPart 3 Our Approach to Variables For each routine and main body 0 Run through the stmts and generate IR quads Also compute maXArgNumber When generating IR code for foo bar aaa bbb ccc ddd 1 2 3 4 Assign offset to our variables nextoffset 4 for each VarDecl p Q p0ffset nextoffset nextoffset nextoffset 4 endFor Assign offsetto ourformals nextFormal 68 for each Formal f do foffset nextFormal nextFormal nextFormal 4 endFor 0 Compute sizeOfFrame bodysizeOfFrame 3 Harry H Porter 2006 CS322 Code GenerationPart 3 CS322 Code GenerationPart 3 A A Activation Record Layout spgt Register window save area Erocedure foo x x x 64 bytes var yl y2 y1 2 M y 2 Display reg save area begin N 1 V 2 barzl22 39 end I Storage or args to 26 II b a r to 27 ca ees eg ar 2 P ma Optional alignment word Let P be the YN MaxArgN umber E Spgce fl 100415 for all routines sup 4 Y1 an temporanes thatccfoo cans fPgt fr ax Fr m 3 1 Space or a e of our ormals our caller XM 3 Harry H Porter 20 06 3 var x integer A Records gin Clike languages I Frame Stack 3 Harry H Porter 2006 CS322 Code GenerationPart 3 Records gin Clike languages E x integer A A type T is record X3 f1 f2 y f3 1 Frame Stack 3 Harry H Porter 2006 CS322 Code GenerationPart 3 Records gin Clike languages var x integer A A type T is record X3 f1 f2 y f3 end var y T pzz var p Etr t T Heap Frame Stack 3 Harry H Porter 2006 CS322 Code GenerationPart 3 Records in PCAT type T is record f1 f2 f3 r 1 Er T rf2 rf3 IR Code for reading a tie rfl t8 r4 genExp We will allocate all records and arrays 0n the heap t9 t9 IR Code for setting a tie rf3 genLValue 11 t12 t11 t12 3 Harry H Porter 2006 CS322 Code GenerationPart 3 Our Approach When walking the AST we will Visit all nodes whenever we see a RecordType in genRecordType 0 Walk the list of fields Fill in the offsets 0 Set the size of the entire record in bytes 0 Must recursively handle nested record types 3 Harry H Porter 2006 CS322 Code GenerationPart 3 Translating Assignment Statements Source x y 3 Translation t1 ampx genLleue t2 genExPr t1 t2 2 Most general approach Handles complex L Values a foo y 3 Problem Difficult to optimize this t ampx t Solution In genAssignStmt watch for special case L Value is a simple variable t2 Goal Reduce tempora usage This is easier to optimize see optimization phase 3 Harry H Porter 2006 CS322 Code GenerationPart 3 Goal Reduce Temp Usage t6 Note t5 and t6 are never used again Idea Recycle newTemp gt temp Create a new temp and return it recycle temp Maintain a collection of unused temporalies Each routine will start with an empty collection recycle 1 Add the temp to collection newTemp1 Get a temp from the collection Create a new temp only when necessary E0 gt E1 E2 Generates t5 El t3 t5 t6 3 Harry H Porter 2006 10 CS322 Code GenerationPart 3 Source Before When to recycle x t1 t2 t3 t4 t5 x ab ed ab cd t1t2 ef t3 t4 t5 In expressions every temp is used exactly once So call recycle When the temp is used as an operand ef Compiler Code tx genExpr ty genExpr recycle tx recycle ty tz newTemp IRaddtztxty 3 Harry H Porter 2006 CS322 Code GenerationPart 3 11 Source Before When to recycle With R ecycling x t1 t2 t3 t4 t5 x t1 t2 t1 t2 t1 x ab ed ab cd t1t2 ef t3 t4 t5 In expressions every temp is used exactly once So call recycle When the temp is used as an operand ab cd t1t2 ef t1 t2 t1 ef Compiler Code tx genExpr ty genExpr recycle tx recycle ty tz newTemp IRaddtztxty 3 Harry H Porter 2006 12 CS322 Code GenerationPart 3 Recycling Bins PCAT Only one kind of temp 4 bytes long Other compilers Many kind of temps byte word double Approach Will have a bin ie collection for each kind of temp recycleByteTemp temp Returns the temp to the recycling bin for byte temps newByteTemp gt temp Check the byte recycling bin before creating recycleWordTemp temp newWordTemp gt temp recycleDoubleTemp temp newDoubleTemp gt temp 3 Harry H Porter 2006 CS322 Code GenerationPart 3 13 Arrays in PCAT Array of N elements 52 1000 of 123456 ai 3 Harry H Porter 2006 30 3 1 3N 1 All arrays will be stored in the heap N a 0 Will be stored in a block of N1 words a39 F 2 The first word will contain L the number of elements in the array At rum ime we must check for Index out0fb0unds error a 11 1 Uninitiulized array error var a array of real nil 1 4 bytes gt 14 CS322 Code GenerationPart 3 Source aexpr Code Generated W t1 t1 if t2 0 goto nullptrerror t3 3 if t3 lt 0 goto boundserror t4 t2 if gt t4 goto boundserror t5 t3 4 t6 t5 t2 t7t64 3 Harry H Porter 2006 CS322 Code GenerationPart 3 137 Now t7 contains the address of the word in question Generating Code to Access ai aO al a2 a 111 1 4 bytes gt 15 How is an array stored in memory Where is Ai stored Array Representation 3 Harry H Porter 2006 16 CS322 Code GenerationPart 3 Assumptions Array Representation How is an array stored in memory Where is Ai stored 0 Array starts at AO 0 No other information eg size stored in the array 0 No indirection no pointers Example w 8 bytes base 1000 3 Harry H Porter 2006 CS322 Code GenerationPart 3 17 Assumptions base i w Array Representation How is an array stored in memory Where is Ai stored 0 Array starts at AO 0 No other information eg size stored in the array 0 No indirection no pointers Let w Width in bytes of each element base 2 address of 1st byte of the array The address of A i Example w 8 bytes base 1000 J 1000 1008 1016 1024 1032 1040 3 Harry H Porter 2006 18 CS322 Code GenerationPart 3 How is an array stored in memory Where is Ai stored Assumptions 0 Array starts at A0 0 No other information eg size stored in the array 0 No indirection no pointers Let w Width in bytes of each element base 2 address of 1st byte of the array The address of A i base i w Example A 3 1000 38 1024 Array Representation Example w 8 bytes base 1000 3 Harry H Porter 2006 CS322 Code GenerationPart 3 19 Assumption Array can start anywhere A 5 A 4 AO B6 B7 Array Representation 3 Harry H Porter 2006 20 CS322 Code GenerationPart 3 Assumption Array can start anywhere A 5 A 4 A0 B6 B7 Let w Width of elements base 2 starting address of the array low 2 smallest legal index eg 5 Array Representation 3 Harry H Porter 2006 CS322 Code GenerationPart 3 Assumption Array can start anywhere A 5 A 4 A0 B6 B7 ILt w Width of elements base 2 starting address of the array low 2 smallest legal index eg 5 The address of A i Before base i w New base i low w Example A 2 1000 2 5 8 1056 2 8 1000 5 8 16 1040 1056 Array Representation Example W 8 bytes base 1000 low 5 3 Harry H Porter 2006 CS322 Code GenerationPart 3 The ZeroNormalized Base Address of A i base i low W R ewriting iw base low W If base and low are known at compiletime we can precompute this constant base low W 3 Harry H Porter 2006 23 CS322 Code GenerationPart 3 The Zero Normalized Base Address of A i base i low W R ewriting Exulfgle iw base low W W 8 bytes base 1000 If base and low are known at compiletime 10w 5 we can precompute this constant base low W 1000 5 8 1040 3 Harry H Porter 2006 CS322 Code GenerationPart 3 Address of A i base i low W R ewriting iw base low W If base and low are known at compiletime we can precompute this constant base low W 1000 5 8 1040 This is the address 0fA0 The zeronormalized base Address of A i iw constant The ZeroNormalized Base Exalee w 8 bytes base 1000 low 5 3 Harry H Porter 2006 CS322 Code GenerationPart 3 Address of A i base i low W R ewriting iw base low W If base and low are known at compiletime we can precompute this constant base low W 1000 5 8 1040 This is the address 0fA0 The zeronormalized base Address of A i iw constant Address of A 2 28 1040 1056 The Zero Normalized Base Exalee W 8 bytes base 1000 low 5 3 Harry H Porter 2006 CS322 Code GenerationPart 3 The ZeroNormalized Base The zero normalized base works even if array does NOT contain A0 3 Harry H Port er 2006 CS322 Code GenerationPart 3 27 Examgle 10 The Zero Normalized Base The zeronormalized base works even if array does NOT contain A0 Exalee W 8 bytes base 1000 W A3 A7 3 Harry H Port er 2006 CS322 Code GenerationPart 3 The zero normalized base works even if array does NOT contain A0 Examgle 10W 2 3 A3 A7 The ZeroNormalized Base Exalee w 8 bytes base 1000 3 Harry H Porter 2006 CS322 Code GenerationPart 3 The zeronormalized base works even if array does NOT contain A0 Examgle 10W 2 A3 A7 Address of AM iW base 10W W iW constant ZeroNormalized Base base 10W W 1000 3 8 6 The Zero Normalized Base Exalee W 8 bytes base 1000 low 3 3 Harry H Porter 2006 CS322 Code GenerationPart 3 The ZeroNormalized Base The zero normalized base works even if array does NOT contain A0 Exalee Examgle w 8 bytes 10W 2 3 base 1000 A3 A7 low 3 Address of AM iW base 10W W 9 iW constant 90M 922 ZeroNormalized Base 1000 base 10W W 1000 38 1032 976 1040 Address of A151 iW constant 58 976 1016 3 Harry H Porter 2006 CS322 Code GenerationPart 3 MultiDimensional Arrays Two Dimensional Arrays var A array 6 81 4 of double R 1 1 2 3 4 Aij 0 quot5 0 Three Dimensional Arrays var B array 6 81 40 9 of double Bijk MultiDimensional Arrays var C array 6814 09 of How do we place the array elements in memory 3 Harry H Porter 2006 CS322 Code GenerationPart 3 7 1000 8 1008 1016 1024 1032 1040 1048 1056 1064 1072 1080 1088 Row Major Order Row 6 Row 7 Row 8 3 Harry H Porter 2006 CS322 Code GenerationPart 3 33 7 1000 8 1008 1016 1024 1032 1040 1048 1056 1064 1072 1080 1088 Row Major Order Row 6 Row 7 Row 8 Column Major Order 1000 1008 1016 1024 1032 1040 1048 1056 1064 1072 1080 1088 Column 1 Column 2 Column 3 Column 4 3 Harry H Porter 2006 34 CS322 Code GenerationPart 3 Row Major Order Column Major Order 1 2 3 4 6 397 1000 6 1000 6 l 8 1008 1008 7 Column 1 Row 6 1016 6 3 1016 8 RowMaJor IS 1024 I 1024 6 most common Column 2 Like decimal numbers 1032 7 1032 7 2 Last digit varies fastest 1040 7 I 2 R 7 1040 8 0W 3687 1048 1048 6 3688 1056 I 1056 7 I Column 3 3689 3690 1064 81 1064 3 3691 1072 1072 6 Row 8 RowMalor Order 1030 8 3 logo 7 Column 4 This idea extends to 1088 8 I 1088 I 4 higher dimensions I Harry H Porter 2006 CS322 Code GenerationPart 3 35 A67 14 37 T 3 Dimensional Arrays RowMajor Order Row 6 Row 8 3 Harry H Porter 2006 36 CS322 Code GenerationPart 3 C01 2 C0 3 CS322 Code GenerationPart 3 3 Dimensional Arrays RowMajor Order A6 7 14 37 3 I 1 617 ROW6 I 624 639 625 739 626 72 1 2 3 4 R0W7 627 j 739 633 739 634 839 635 82 ROW8 8393 637 I4 643 3 Harry H Porter 2006 37 Where is Ai Stored Assumption TwoDimensions ROWMajor Order var A array 08 04 greal Let w Width of elements 8 base 2 starting address of the array 1000 highl 2 highest row index A 0 8 0 highz 2 highest column index A 0 8 0 Compute N1 number of rows highl 1 8 1 9 N2 number of columns highz 1 4 1 5 2 size of each m A i basei N2j w 3 Harry H Porter 2006 38 CS322 Code GenerationPart 3 Where is Ai Stored Assumption TwoDimensions ROWMajor Order var A array 6 8 1 41g real Let w Width of elements 8 base 2 starting address of the array 1000 lowl 2 lowest row index A 6 8 1 highl 2 highest row index A6 8 1 lowz 2 lowest column index A 6 8 1 highz 2 highest column index A 6 8 1 Compute N1 number of rows high1 low11 8 61 3 N2 number of columns high2 low21 4 11 4 2 size of each row AL basei low1 N2j low2 w 4 4 4 3 Harry H Porter 2006 CS322 Code GenerationPart 3 39 R epeating A i39 is stored at basei low1N2j low2w 6 operations Can we compute any of this at compiletime 3 Harry H Porter 2006 40 CS322 Code GenerationPart 3 R epeating A i39 is stored at basei low1N2j low2w 6 operations Can we compute any of this at compiletime Rewriting i N2 j w base lowl N2 lowz w 0 Assume the array bounds are fixed at compiletime 0 Assume the base address is known at compiletime i N2 j w base lowl N2 lowz w 4 operations The ZeroNormalized Base The address of A00 Compiletime constant Precompnte it 3 Harry H Porter 2006 CS322 Code GenerationPart 3 41 R epeating A i39 is stored at basei low1N2j low2w A 00 is stored at base 0 low1 N2 0 low2 w R ewriting base low1 N2 low2 w base lowl N2 lowz w i N2 j w base lowl N2 lowz w C ampiletime constant Precompnte it 3 Harry H Porter 2006 42 CS322 Code GenerationPart 3 Accessing MultiDimensional Arrays Assume all indexes start at zero A 0high1 0high2 0highK Ai j is stored at 39 39 base 1 N2 J W Number 0fdimensi0ns K The general case A 10W1high1 10W2high2 10WKhighK A i j basei 10W1 N2 j lOW2 W 3 Harry H Porter 2006 CS322 Code GenerationPart 3 Accessing MultiDimensional Arrays Assume all indexes start at zero A 0high1 0high2 0highK Ai j is stored at 39 39 Allis ti21 J W Number of dimensions K baseilN2i2N3i3W The general case A 10W1high1 10W2high2 10WKhighK A i j basei 10W1 N2 j lOW2 W Ailizi3 baseii 10W1N2i2 10W2N3i3 10W3 W 3 Harry H Porter 2006 CS322 Code GenerationPart 3 Accessing MultiDimensional Arrays Assume all indexes start at zero A 0high1 0high2 0highK Aij isstored at 39 Alflsiliil ii2 l W NumberofdimensionsKj baseilN2i2N3i3w Ailizi3i4 baseilN2i2N3i3N4i4w The general case A 10W1high1 lowzhigh2 lowKhighK Ai j 1 basei 10W1 N2 j lOW2 W Ailizi3 baseil 10W1N2i2 10W2N3i3 10W3 W Ailizi3i4 base il lOW1 N2 i2 lowz N3 i3 lOW3 N4i4 low4w 3 Harry H Porter 2006 CS322 Code GenerationPart 3 Accessing MultiDimensional Arrays Assume all indexes start at zero A 0high1 0high2 0highK Aij isstoredat Allis 121 J W Number of dimensions K basei1N2i2N3i3w Ailizi3i4 baseilN2i2N3i3N4i4w Ailizi3iK baseilN2i2N3i3NKiKW The general case A 10W1high1 lowzhigh2 lowKhighK Aij basei 10W1N2j 10W2W Ailizi3 basell 10W1N2l2 lOW2N3l3 10W3W Ailizi3i4 baseil 10W1N2i2 10W2N3i3 10W3 N4i4 low4w AiliziK base ll lOW1 N2 i2 lowz N3 i3 lOW3 NKiK lowK w 3 Harry H Porter 2006 CS322 Code GenerationPart 3 A67 14 37 3 Dimensional Arrays Row 6 Row 7 Row 8 3 Harry H Porter 2006 CS322 Code GenerationPart 3 47 14 37 61 3 Dimensional Arrays 62 63 64 71 72 73 74 81 82 83 84 617 Row 6 Row 7 Row 8 623 624 5236 627 633 634 635 636 637 643 C01 2 C0 3 3 Harry H Porter 2006 48 CS322 Code GenerationPart 3 Precomputing the ZeroNormalized Base Ai1 iz iK is stored at base i1 low1 N2 i2 lowz N3 i3 low3 NKiK lowKw Factoring out the constant i1N2i2N3i3 NKiKw base low1N2low2N3low3 NKlowKw CS322 Code GenerationPart 3 3 Harry H Porter 2006 Precomputing the ZeroNormalized Base Ai1 iz iK is stored at base i1 low1 N2 i2 lowz N3 i3 low3 NKiK lowKw Factoring out the constant i1N2i2N3i3 NKiKw base low1N2low2N3low3 NKlowKw Performing the computation at runtime i1 3 Harry H Porter 2006 CS322 Code GenerationPart 3 Precomputing the ZeroNormalized Base Ai1 iz iK is stored at base i1 low1 N2 i2 lowz N3 i3 low3 NKiK lowKw Factoring out the constant i1N2i2N3i3 NKiKw base low1 N2low2 N3low3 NKlowK w Performing the computation at runtime i1 11N2 12 CS322 Code GenerationPart 3 3 Harry H Porter 2006 Precomputing the ZeroNormalized Base Ai1 iz iK is stored at base i1 low1 N2 i2 lowz N3 i3 low3 NKiK lowKw Factoring out the constant i1N2i2N3i3 NKiKw base low1 N2low2N3low3 NKlowK w Performing the computation at runtime i1 11N2 i 11N2 12 N3 13 3 Harry H Porter 2006 CS322 Code GenerationPart 3 Precomputing the ZeroNormalized Base Ai1 12 iK is stored at base i1 low1 N2 i2 lowz N3 i3 low3 NKiK lowKw Factoring out the constant i1N2i2N3i3 NKiKw base low1 N2low2 N3low3 NKlowK w Performing the computation at runtime i1 11N2 12 11N2 izN3 13 ilN2 izN3 13 NK iK CS322 Code GenerationPart 3 3 Harry H Porter 2006 Precomputing the ZeroNormalized Base Ai1 12 iK is stored at base i1 low1 N2 i2 lowz N3 i3 low3 NKiK lowKw Factoring out the constant i1N2i2N3i3 NKiKw base low1 N2low2N3low3 NKlowK w Performing the computation at runtime 11 11N2 i 11N2 12N3 13 11N2 12N3 13NK 1K 11N2 12N3 13NK 1K w 3 Harry H Porter 2006 CS322 Code GenerationPart 3 Precomputing the ZeroNormalized Base Ai1 12 iK is stored at base i1 low1 N2 i2 lowz N3 i3 low3 NKiK lowKw Factoring out the constant i1N2i2N3i3 NKiKw base low1 N2low2 N3low3 NKlowK w Performing the computation at runtime 11 11N2 12 1N2 izN3 13 ilN2 izN3 13 NK iK ilN2 izN3 13 NK iK w ilN2 izN3 13 NK iK w constant 3 Harry H Porter 2006 CS322 Code GenerationPart 3 Checking Array Limits 1Dimensional 0 Check i before computation of address low 5 i 5 high 0 Perform the address computation pbasei loww Check that address is Within array base 5 p lt base sizeInBytes 3 Harry H Porter 2006 CS322 Code GenerationPart 3 Checking Array Limits 1Dimensional 0 Check i before computation of address low 5 i 5 high 0 Perform the address computation pbasei loww Check that address is Within array base 5 p lt base sizeInBytes MultiDimensional 0 Check each index individually aijk lowl Si 5 highl lowz Sj S highz low3 s k S high3 0 Perform the address computation p base Check that address is Within array base 5 p lt base sizeInBytes 3 Harry H Porter 2006 CS322 Code GenerationPart 3 Checking Array Limits 1Dimensional 0 Check i before computation of address Faster but flawed low 5 1 5 high 1 2 3 4 0 Perform the address computation 6 pbasei loww 7 Check that address is Within array 8 b s ltb IBt 359 P 35quot mequot yes MAMA Not in array M It D al W Perform address calculation 0 Check each 1ndex 1nd1V1dually b l N l aijk low1 si s high1 35 0 Owl 20 OWZ w base 6 64 10 1w lowz SJ 5 hlghz l 2 base 9w ow3 S k s high3 base 8 642 1w 0 Perform the address computation base 9w p base The access is still within the array Check that address is Within array base 5 p lt base sizeInBytes I Faster but awed 3 Harry H Porter 2006 CS322 Code GenerationPart 3 Arrays in PCAT Always 1 dimensional Always start at zero M ultidimensional arrays 3 Harry H Porter 2006 CS322 Code GenerationPart 3 59 Arrays in PCAT Always 1 dimensional Always start at zero M ultidimensional arrays E a array g integer In Heap or on Stack In The HEAP 3 Harry H Porter 2006 60 CS322 Code GenerationPart 3 Arrays in PCAT Always 1 dimensional Always start at zero M ultidimensional arrays var a array g array of integer a5 7 a5 7 In Heap or on Stack In The HEAP 3 Harry H Porter 2006 CS322 Code GenerationPart 3 Arrays in PCAT Always 1 dimensional Always start at zero M ultidimensional arrays E a array g array of array g integer a5 7 9 a579 In Heap or on Stack E In The HEAP 3 Harry H Porter 2006 CS322 Code GenerationPart 3 Arrays can have different sizes and some elements may be NIL integer a517191 123 In Heap or on Stack HIE 3941 ZZZ HHH IHHH In The HEAP 3 Harry H Porter 2006 Elk CS322 Code GenerationPart 3 AKA Case Statements Switch Statements switch expr case valuelz Stmt List1 case valuezz Stmt List2 case value Stmt ListN default Strut List 1 endSwitch In CCJava StmtListi Will fall through to StmtList11 Must use break 3 Harry H Porter 2006 CS322 Code GenerationPart 3 AKA Case Statements Switch Statements M exPr Switch Expression case valu e1 Stmt List1 Case Arms Case Clauses case valuezz Stmt List2 Default Case is optional If missing fall through case value Stmt ListN default Stmt List endSwitch N1 In CCJava StmtListi will fall through to StmtList11 Must use break The value s must be constants ie statically known Statically Executable Statically Evaluatable Statically Computable static final E MAX 100 case 4317MAX Stmt Listi 3 Harry H Porter 2006 CS322 Code GenerationPart 3 Switch Statements Three Implementation Techniques 1 Sequence of N expilicit tests 2 Precompute a table of N entries Generate code to quickly search this table 3 Direct Jump Table Generate a vector of N addresses Use the switch value as an offset into this table Execute a JumpIndirect through the table 3 Harry H Porter 2006 CS322 Code GenerationPart 3 11 Seguence of N Tests Treat the switch statement exactly like a sequence if thenelse statements switch expr t expr case valuelz Stmt List1 i t value1 then case valuezz Stmt List2 Stmt List1 elseIf t value2 then case value Stmt ListN Stmt List2 default Stmt Listn1 endSwitch elseIf t valueN then Stmt LIstN else Stmt LIstn1 endIf 3 Harry H Porter 2006 CS322 Code GenerationPart 3 67 code for Expr enExpr t 1 Se uence of N Tests abl Labz if t a Valuel goto Labl code for Stmt Listl goto endLabel if t a Valuez goto Lab2 code for Stmt List2 goto endLabel Prologue C use Arms goto endLabel Lab endLabel code for Stmt List if t a ValueN goto LabN code for Stmt ListN N1 C ode for Default 3 Harry H Porter 2006 68 CS322 Code GenerationPart 3 1 Se uence of N Tests enExpr t Prologue if t a Valuel goto Labl code for Stmt Listl goto endLabel l This code is if t a Valuez goto Lab2 easy to generate code for stint List2 But it is difficult goto endl39abel Cu to recognize it as Lab2 a sw1tch statement We want to do that during the Optimization phase if t a ValueN goto LabN code for Stmt ListN to endLabel g Lab code for Stmt ListNl C0def0r Default endLabel 3 Harry H Porter 2006 CS322 Code GenerationPart 3 11 Sequence of N Tests if t Valuel goto Labl t if t Value2 goto Lab2 Prologue t ValueN goto LabN goto L n1 Lablz code for Stmt Listl goto endLabel Lab2 code for Stmt List goto endLabel 2 case Arms Lab C ode for default statements optional Ncode for Stmt ListN goto endLabel LabNl i code for SEEE Listul endLabel 3 Harry H Porter 2006 CS322 Code GenerationPart 3 11 Sequence of N Tests if t Valuel goto Labl t if t Value2 goto Lab2 Prologue t ValueN goto LabN goto LabN1 For CCJava the break statement produces this goto code for Stmt Listl Case Arms C ode for default statements optional LabNl code for Stmt ListNl endLabel 3 Harry H Porter 2006 CS322 Code GenerationPart 3 11 Sequence of N Tests if t Valuel goto Labl t if t Valuez goto Lab2 Perhaps this can be optimized during optimization phase t ValueN goto LabN goto LabN1 Lablz code for Stmt Listl For CCJava the break statement produces this goto Case Arms C ode for default statements optional code for Stmt ListNl endLabel 3 Harry H Porter 2006 CS322 Code GenerationPart 3 11 Seguence of N Tests To generate code for a Switch statement Prologue Create a new label endLabel Generate code to evaluate the expr into temporary 1 Run through all case arms Compute Valuei Create a new label Labi Generate if tValuei goto Labi Remember each label Generate goto LabN 1 Run through all case arms a second time To generate code for case Valuei Stmt Listi Generate label Labi Generate the code for Strut Listi Generate label goto endLabel Egilogue Generate label LabN 1 Generate code for default statements optional Generate label endLabel 3 Harry H Porter 2006 CS322 Code GenerationPart 3 73 Previously if t Valuel goto Labl if t Valuez goto Lab2 if t ValueN goto LabN goto LabN1 Ideas tor IR Instructions switch t LabN case Valuel Labl case Valuez Lab2 case ValueN LabN Maybe we can generate search for the rtght case 3 Harry H Porter 2006 74 CS322 Code GenerationPart 3 12 Precompute a Table and Search It Approach Build a table in static storage Each entry contains a Value and a Label Generate code to search the table Upon finding the matching value The code Will jump to the stored label Table Implementation f the table mm 7903 VTAB LTAB 0 word Lab4 3 word 406 397 word Lab44 o o 0 word 8 98 9 word Lab45 p ampTable Code to do a Loop linear search if Table p t goto Table p4 p p 8 goto Loop 3 Harry H Porter 2006 CS322 Code GenerationPart 3 75 12 Precompute a Table and Search It Dealing with the default case The Switch expression value does not match any Case Clause M Use a Sentinel 0 Add one extra entry to the table Use the label of the default code Will fill in value at runtime 0 Generate code to store the value of t into the last entry During the search If no values match we ll match the last entry VTAB LTAB 3 Harry H Porter 2006 76 CS322 Code GenerationPart 3 Use a Hash Table Linear search is slow Use a hashbased search At compiletime We know the number of values Determine the optimal hash table size Determine the hash function Build the table precompile it Generate code to 0 Compute the switch expression 0 Compute HasheXpr Search the table until Match is found Null entry is found 0 Jump indirect through the table 3 Harry H Porter 2006 CS322 Code GenerationPart 3 77 Some W131 switch x17 E 2004 Stmt List1 E 5006 Stmt List2 E 4003 Stmt List3 E 7009 Stmt List4 case 6006 Stmt List5 case 3001 Stmt List6 default Stmt List endSwitch N1 3 Harry H Porter 2006 78 CS322 Code GenerationPart 3 Some W131 switch x17 E 2004 Stmt List1 case 5006 Stmt List2 case 4003 Stmt List3 case 7009 Stmt List4 E 6006 Stmt List5 case 3001 Stmt List6 default Stmt List endSwitch N1 Number of cases 6 Hash Table size 10 Hash Function hashV V mod 10 2004 gt 4 5006 gt 6 3 Harry H Porter 2006 CS322 Code GenerationPart 3 Some W131 switch x17 E 2004 Stmt List1 E 5006 Stmt List2 BulldTable 0 E 4003 Stmt List3 1 E 7009 Stmt List4 case 6006 Stmt List5 case 3001 Stmt List6 default Stmt List endSwitch VTAB LTAB N1 Number of cases 6 Hash Table size 10 Hash Function hashV V mod 10 2004 gt 4 5006 gt 6 Wmde39lth N 6006 gt 6 3001 gt 1 3 Harry H Porter 2006 CS322 Code GenerationPart 3 Some W131 switch x17 E 2004 Stmt List1 case 5006 Stmt List2 BulldTable case 4003 Stmt List3 case 7009 Stmt List4 E 6006 Stmt List5 case 3001 Stmt List6 default Stmt List endSwitch VTAB LTAB N1 Number of cases 6 Hash Table size 10 Hash Function hashV V mod 10 2004 gt 4 At runtime 5006 6 Compute t x17 4003 3 Compute Hash t 7009 9 Search the table 6006 6 If VTAB p matches JumpIndirect 3001 gt 1 If LTAB p null jump to default LabN 1 3 Harry H Porter 20 06 8 1 CS322 Code GenerationPart 3 13 DirectJump Table switch x 1 7 case 4 Stmt List1 LTAB case 6 Stmt List2 0 case 3 Stmt List3 1 case 9 Stmt List4 2 case 7 Stmt List5 3 case 2 Stmt List6 4 default Strut List 1 5 endSwitch 6 Determine the range of values 7 Build a table this size 8 9 Each table entry Will contain a label 3 Harry H Porter 2006 CS322 Code GenerationPart 3 13 DirectJump Table switch x 1 7 case 4 Stmt LIst1 case 6 Stmt LIst2 case 3 Stmt List3 case 9 Stmt List4 case 7 Stmt List5 case 2 Stmt List6 default Strut List 1 endSwitch Determine the range of values Build a table this size Each table entry Will contain a label Wmde39lth NI O 3 Harry H Porter 2006 CS322 Code GenerationPart 3 13 DirectJump Table switch x 1 7 case 4 Stmt List1 case 6 Stmt List2 case 3 Stmt List3 case 9 Stmt List4 case 7 Stmt List5 case 2 Stmt List6 default Stmt Lis endSwitch tN1 Determine the range of values Build a table this size Each table entry Will contain a label Unused table entn39es Fill With LabN 1 Wmde39lth NI O 3 Harry H Porter 2006 CS322 Code GenerationPart 3 13 DirectJump Table switch x 1 7 case 4 Stmt LIst1 case 6 Stmt LIst2 case 3 Stmt List3 case 9 Stmt List4 case 7 Stmt List5 case 2 Stmt List6 default stint List 1 endSwitch Determine the range of values Build a table this size Each table entry will contain a label Unused table entn39es Fill with LabN 1 Generate code to Compute the switch expression Use t as an index into the table Perform IndirectJump through the table 3 Harry H Porter 2006 Wmde39lth NI O CS322 Code GenerationPart 3 13 DirectJump Table switch x 1 7 case 4 Stmt List1 case 6 Stmt List2 case 3 Stmt List3 case 9 Stmt List4 case 7 Stmt List5 case 2 Stmt List6 default Stmt Lis endSwitch tN1 Determine the range of values Build a table this size Each table entry will contain a label Unused table entn39es Wmde39lth NI O Fill with Lab 1 This approach only works when the Generate code to range of values is small Compute the switch expression OtheI WiSe LTAB is too large Use t as an index into the table NOTE The values can be shifted Perform IndirectJump through the table 35002 35009 gt 07 3 Harry H Porter 2006 CS322 Code GenerationPart 3 Switch Table Implementation Recap 1 Sequence of Explicit Tests 2 Table plus Search Linear Search Hash based search Other search e g Binary Search 3 Direct Jump Table Very Fast but can only use if range is small Which method is best Which method s does gcc use Under what circumstances Nice to know how smartdumb your compiler is so you can write ef cient code 3 Harry H Porter 2006 87 CS322 SPAR CPart 2 Each SPARC instruction is one word long 32bits Info is encoded into each instruction Opcode Register Instructions are stored in memory with data Instructions are always word aligned Registers PC the program counter The quotfetch incrementexecute loop Basic Concepts Instruction Execution 01001101 10101010 10111001 00101101 L39AW l LiteralData PC 0 100 instr MEMORY PC PC PC 4 Execute instr I fetch operands I perform computations endLoo I store results includes modifying PC 3 Harry Porter 2006 CS322 SPAR CPart 2 Machine Architecture Variations Stack Architectures Easy to compile to ASSIGN Lots of memory accesses Used mostly for interpreters Accumulator Architectures LOAD x One general purpose register ADD y STORE Z CISC TwoOperand Architectures Several generalpurpose registers Two operand fields in instructions The result overwrites one operand RISC Load Store Threeoperand Architectures Lots of generalpurpose registers LOAD Instructlons have3 operand fields LOAD Each instructlon is either D Computation STORE xR1 121122123 R3z Memory access Operands for computation must be in registers Many instructions execute in a single clock cycle 3 Harry H Porter 2006 CS322 SPAR CPart 2 SPARC Registers GeneralPurgose Registers 32 registers Well okay to assume 32bits 32bits 4bytes each 39 Divided into 4 sets of 8 registers Global g0 g1 g7 Local 10 11 17 In iO il i7 Out 00 01 07 Available operations Integer an39thmetic add sub mul div cmp Logical and or not shiftleft shiftlight F loatin gPoint Registers 32 registers f0 f1 f31 Available operations Floatingpoint an39thmetic add sub mul div cmp Integerto oating conversion 3 Harry H Porter 2006 CS322 SPAR CPart 2 Other Registers Program Counter PC 32bits Integer Condition Code Register 4bits For integer operations F lootingPoint Condition Code Register 4bits For oatingpoint operations Y Register 3A0E 2c33 3239b1ts 0145 0000 Used forinteger mulitply 0049 B543 lCBF 0000 and divide operations H Y reg Normal Reg 0th er Registers Lots ignore them 3 Harry H Porter 2006 CS322 SPAR CPart 2 Example SPARC Instructions sub g2 g7 g5 Operand 1 Result Destination regl Operand 2 regD reg2 1000 1010 0010 0000 1000 0000 0000 0111 regD regl reg2 sub g2 7 g5 1000 1010 0010 0000 1010 0000 0000 0111 H J regD regl Literal data value 3 Harry H Porter 2006 CS322 SPAR CPart 2 13Bit Immediate Values The instruction includes a 13bit signed value Range 4096 4095 This value is signextended to 32bits Examgle o 0000 0000 0111 N r I0000 0000 0000 0000 0000 0000 0000 0111 I 3 Harry H Porter 2006 CS322 SPAR CPart 2 13Bit Immediate Values The instruction includes a 13bit signed value Range 4096 4095 This value is signextended to 32bits Examgle 1 1111 1111 1001 r I1111 1111 1111 1111 1111 1111 1111 1001 I 3 Harry H Porter 2006 CS322 SPAR CPart 2 Notation sub regl reg2orimmed regD regl reg2 regD Any one of the 32 generalpurpose integer registers 5 bits immed 13bit signed integer value Must be between 4096 and 4095 Signedextended to 32bits before being used S yntax Full C like exgressions Character literals m quotmu Hex 0266 All equal Decimal 10 9 Octal 0 155 Expressions 64 3 m Symbols x e Assemblytime constants not runtime variables 3 Harry H Porter 2006 CS322 SPAR CPart 2 Assembler Syntax One instruction per line I spaces are okay Labels on same line or on line alone but not normally used label sub g3g5 g Comments add g756g7 add 12 34 12 W H4 Hg Tab Tab Tab Note the Commenting style Examgle 1d myVal 12 myVal myVal 78 add 127812 st 12 myV The destination is always on the light Not quite legal SPARC 3 Harry H Porter 20 06 9 CS322 SPAR CPart 2 Instructions Arithmetic Arithmetic add addcc sub subcc Si ed smul smulcc g sdiv sdivcc Unsigned These 10 n0t mil These Q ud1v udlvcc modify the modify the L0 wl condition code Logical condition code and Register andcc register or orcc xor xorcc W lijet andn andncc f It orn orncc N3 resu lS zero xnor xnorcc if result is neg etc Shifting sll srl sra 3 Harry H Porter 20 06 1 0 CS322 SPAR CPart 2 Logical Functions and or xor x y andn x and not y orn x or not y xnor x y x y and or xor andn orn xnor 0 0 0 0 0 0 1 1 0 1 0 1 1 0 0 0 1 0 0 1 1 1 1 0 1 1 1 1 0 0 1 1 These instructions work on all 32 bits at once and g4g5g6 g4 gt0011 1100 1010 g5 gt1010 1101 1001 g6 gt0010 1100 1000 3 Harry H Porter 2006 CS322 SPAR CPart 2 11 T 0 turn on bits in a word Use the or instruction and a mask word or x mask result Tum on bits in x Wherever the mask has a 1 bit Example Turn on every other bit in 3AOF 0011 1010 0000 11113AOF 0101 0101 0101 0101 e mask 0111 1111 0101 1111 result T 0 turn all bits in a word Use the and instruction and a mask and x mask result Tum off bits in x Wherever the mask has a 0 bit To i or to le bits in a word Use the xor instruction and a mask xor x mask result Change the bits in x Wherever the mask has a 1 bit 3 Harry H Porter 2006 12 CS322 SPAR CPart 2 Shifting Instructions 5 ll Number of bits 031 Shift Left Log1cal ltlt 511 regl reg2orimmed regD 31 A fast way to multiply by 2N Ilt o Examgle Multiply by 32 25 511 x5result 0000 0000 0000 0011 0000 0000 0110 0000 0 5 r1 31 Shift Right Logical gtgtgt srl regl reg2orimmed regD S r a 31 30 Shift Right Arithmetic gtgt sra regl reg2orimmed regD A fast way to divide by 2N rounding toward oc sra x 1 result 3 Harry H Porter 2006 CS322 SPAR CPart 2 Testing cmp regl reg2orimmed Compare operandl to operand2 Set integer condition codes accordingly The next instruction will normally be a conditional branch Exumgle cmp g373 if x lt 3973 goto loop ble loop Branch if the condition codes indicate op Stud 3 Harry H Porter 2006 14 CS322 SPAR CPart 2 How to turn highlevel code into assembly code if x gt 73 ampamp y lt 98 then b c d endIf Step 1 Convert LOOPS and IFS into GOTOs possibly reversing the tests if xlt73 then goto elseLabel if ygt98 then goto elseLabel b c d elseLabel Step 2 Turn into assembly code Keep the operand order and tests the same Cmp 951373 if x gt 73 bl elseLabel amp 951298 and y lt 98 NOTE The comments bge e1 seLabel look like source code add g4g5g3 b c 1 including indentation elseLabel endIf 3 Harry H Porter 2006 CS322 SPAR CPart 2 Unconditional Branch the goto instruction ba label Conditional Branches For Signed Values For Unsigned Values 1 abel blu label ble label bleu label bg label bg39u label bge label bgeu label Equality Testing be label ltsamegt bne label ltsamegt 3 Harry H Porter 2006 CS322 SPAR CPart 2 The Condition Code Register 4 bits N 1 2 negative Z 1 2 zero V 1 over ow C 1 calry out Set after an39thmetic operations addcc subcc Re ect the result Instructions to test the bits individually Instruction Will branch if bneg label N1 bpos label N0 bz label Z1 bnz label Z0 bvs label V1 bvc label V0 bcs label C1 bcc label C0 3 Harry H Porter 2006 CS322 SPAR CPart 2 The Delay Slot Due to pipelining All branch instructions take 1 extra instruction to go into effect The instructiohfollowihg the branch is executed before the branch happensH 3 Harry H Porter 2006 CS322 SPAR CPart 2 The Delay Slot Due to pipelining All branch instructions take 1 extra instruction to go into effect The instruction following the branch is executed before the branch happensH Ogt39ion 1 Put a nop instruction in the delay slot cmp 13 73 bl elseLabel nop 3 Harry H Porter 2006 CS322 SPAR CPart 2 The Delay Slot Due to pipelining All branch instructions take 1 extra instruction to go into effect The instruction following the branch is executed before the branch happensH Ogt39ion 1 Put a nop instruction in the delay slot cmp l373 t t d bl elseLabel Vm quotCky 0 0 correctly nop co Ogt39ion 2 Figure out how to put a real useful instruction in the delay slot 1d myVarl3 var var 1 sub l3113 st l3myVar cmp l373 if var lt 73 bl elseLabel goto elseLabel nop 3 Harry H Porter 2006 CS322 SPAR CPart 2 The Delay Slot Due to pipelining All branch instructions take 1 extra instruction to go into effect The instructiorzfollowihg the branch is executed before the branch happensH Ogt39ion 1 Put a nop instruction in the delay slot cmp l373 t t d bl elseLabel Vm quotCky 0 0 correctly nop co Ogt39ion 2 Figure out how to put a real useful instruction in the delay slot 16 myVarl3 var var 1 sub 13 1 13 cmp l373 if var lt 73 bl elseLabel goto elseLabel st 13 myVar delay 3 Harry H Porter 2006 CS322 SPAR CPart 2 0 Figuring out how to rearrange the code to fill the delay slot is difficult amp error prone 0 Study Chapter 2 in Paul for examples 0 Project 7 You can practice filling the delay slots Get the program right first 0 Our Compiler Will not make this important optimization 0 See how smart the C compiler is 3 Harry H Porter 2006 CS322 SPAR CPart 2 Optimizing Assembly Code Aggicalloog A bl while x1 lt 17 Q ssume varjla es 1nlrlegyters x1x1x2 x2gt12 x3 x3 1 x x3 13 end Translation into SPARC Execution Time A a l i N 7 test cmp 11 17 bg done 11 F add 111211 add 13 1 13 ba test 11 F done 3 Harry H Porter 2006 CS322 SPAR CPart 2 23 Rotating a Loop 3 Harry H Porter 2006 24 CS322 SPAR CPart 2 Rotating a Loop An extra branch is Inserted here but it is only executed once The conditional branch Is also used to jump Back to the loop top U nn ecessary branch here 3 Harry H Porter 2006 CS322 SPAR CPart 2 Optimizing Assembly Code A tygical loog while x1 lt 17 Q Assume vamzbles m regsters x1x1x2 X1gt11 x3 x3 1 x2 12 x3 gt 13 Translation into SPARC Execution Time test N7 cmp 1117 bg done 11 F add 111211 add 13113 ba test 11 F done 3 Harry H Porter 20 06 CS322 SPAR CPart 2 Optimizing Assembly Code Aggicalloog A bl while x1 lt 17 Q ssume varjla es 1nlrfgisters x1x1x2 x2gt12 x3 x3 1 x x3 gt 13 end Translation into SPARC test 11 12 11 add 13 1 13 test add 111211 add 13 1 13 ba test cmp 11 17 ble loop done Execution Time N 5 3 Harry H Porter 2006 CS322 SPAR CPart 2 Optimizing Assembly Code A gical loog while x1 lt 17 Q Assume vanablesm registers x1x1x2 x3 x3 1 x x3 gt 13 end Translation into SPARC ba test nop add 111211 add 13 1 13 ba test cmp 11 17 test loop cmp 11 17 add 111211 ble loop add 13113 1117 test Execution Time N 5 1 cycle saved total 3 Harry H Porter 2006 ble loop CS322 SPAR CPart 2 How to fill a delay slot ble target lt mul div u 39 target add 101112 sub Copy the target instruction into the delay slot and branch to 2nd instruction ble target add 101112 mul div add 10 1112 target sub 3 Harry H Porter 2006 CS322 SPAR CPart 2 How to fill a delay slot ble target lt mul d1v target add 101112 sub Copy the target instruction into the delay slot and branch to 2nd instruction ble arget add 101112 mul div add 101112 target sub Problem The add is executed even when the branch is NOT taken Solution Annulled Branches 3 Harry H Porter 2006 CS322 SPAR CPart 2 Annulled Branches Assumption 0 Loops end With a conditional branch 0 The branch is back to the looptop Loops execute many times 0 Goal Speed up highly repetitive loops 0 The branch is taken more often than not 0 Goal Optimize the branchis taken case Approach 0 Execute the delay instruction When branch is taken 0 Add some support for the case When branch not taken May execute a little slower but 3 Harry H Porter 2006 CS322 SPAR CPart 2 31 Annulled Branches One bit in conditional branch instructions The man bit If the bit is 0 The branch is not annulled The instruction in the delay slot is always executed Syntax bge label If the bit is 1 The branch is annulled Branch Taken Instruction in delay slot is executed Branch Not Taken Instruction in delay slot is M executed Syntax bge a label 3 Harry H Porter 2006 32 CS322 SPAR CPart 2 Optimizing Assembly Code Execution Time Translation into SPARC 3 Harry H Porter 2006 CS322 SPAR CPart 2 Aggicalloog A bl while x1 lt 17 Q ssume vaer es 1nlr1egisters x1x1x2 x2gt12 x3 x3 1 x x3 13 end test ba test cup 1117 cmp 11 17 loop loop add l3 1l3 add 111211 cup 1117 add 13 1 13 test ll17 blea loop test 111211 ble loop 11 F 33 PseudoOps byte 35 0x23 half 35 0x0023 Word 35 0x00000023 The value can be specified many ways hex decimal ascii expressions word half 1230x0F00ltlt5 byte 3 A list of values may be used word 25780x44000000 a fills 3 words FloatingPoint values may be placed in memory single 0r12 34 4 byte floating point value double 0r1234e 2 8 byte floating point value Labels will often be used myVar rd Oxffffabcd 3 Harry H Porter 2006 34 CS322 SPAR CPart 2 ascii quot abcdefquot Will initialize N bytes of storage lling it with character data C strings are terminated with 0x00 asciz quot abcdefquot skip 3500 Will skip 3500 bytes leaving them uninitialized Will initialize N1 bytes of storage putting 0x00 after the final byte 3 Harry H Porter 2006 CS322 SPAR CPart 2 35 The align PseudoOE align 2 align 4 align 8 Will skip as many bytes as necessary to get onto the indicated alignment boundary Example asciz quothello quot align 2 half 0x12 3 4 align 4 word 0xfedcba98 3 Harry H Porter 2006 36 CS322 SPAR CPart 2 Symbols Each label is a symbolic name for an address loop ba loop nop By default each symbol is local to one s file global symbol Makes symbol available to the linker and debugger as an external symbol The linker will resolve the symbol If not defined in any 0 le gt Linker error unknown symbol global main main To use an externally defined symbol nothing special is needed call The assembler will not compain if printf is not defined in this s file 3 Harry H Porter 2006 CS322 SPAR CPart 2 37 Segments gin Unix data 9 Put most data here Will be placed in readwn39te pages text 9 Put code and constant data here Will be readonly pages bss Put uninitialized data here Readwrite pages Will be allocated 3 Harry H Porter 2006 38 CS322 SPAR CPart 2 Unix Commands gcc myProgs c Looks at the 5 extension Calls assembler c means produce a 0 file gcc myProg 0 plus other ofiles o myProg Looks at the 0 extensions Calls the linker xxx means produce an executable with name xxx myProg Loads the program into memory and executes it gcc S samplePgm c To see What the C compiler produces Creates samplePgms 3 Harry H Porter 2006 CS322 SPAR CPart 2 Integer Multiplication and Division No multiply or divide instructions in early versions of SPARC Place operand 1 in 00 Place operand 2 in 01 Call a subroutine Find the result in 00 Example 16 xoO 39 z x y 16 yol call mul nop 39 st 00z Available subroutines 7 mul umul 00 x 01 00 div udiv rem 00 01 00 urem 3 Harry H Porter 2006 CS322 SPAR CPart 2 1d address regD st regl address mov regl regD Address reg regoffset regreg Examgles 1d i4 i6 These each move one word 32 bits reg and regD may be any integer register Loadin Storin Movin 0000 0004 0008 000c i4e 0010 0014 0018 001c 0020 0024 0028 002c 0030 0010 0034 Data always moves to the left xxxx 3 Harry H Porter 2006 CS322 SPAR CPart 2 1d address regD st regl address mov regl regD Address reg regoffset regreg Examgles 1d i4 i6 1d i424 i6 A constant 13bit value These each move one word 32 bits reg and regD may be any integer register 0x18 Loadin Storin Movin 0000 0004 0008 000c i4e 0010 0014 0018 001c 0020 0024 0028 002c 0030 0010 0034 24 Data always moves to the left a0 a1 a2 a3 a4 a5 a6 a7 Harry H Porter 2006 CS322 SPAR CPart 2 Loadin Storin Movin 1d address regD st regl address mov regl regD Data always moves to the left These each move one word 32 bits 0000 reg and regD may be any integer register 0004 0008 000c Address i4e 0010 a0 reg 0014 1 regoffset L regreg 24 0018 001C a3 0x18 E 0020 a4 xamgles 1d i4 16 0 24 1d i424 16 0028 i 1d i415 16 002 amp 0030 i4 0010 0034 15 0018 3 Harry H Porter 20 06 CS322 SPAR CPart 2 g0 Special register g0 Reading from it Always zero Writing to it Data is discarded 3 Harry H Porter 2006 44 CS322 SPAR CPart 2 Synthetic Instructions Programmer codes this mov regorinmed regD Assembler produces this or g0 regorimmed regD 39 not regl regD xnor regl g0 regD cmp regl reg2orinmed subcc regl reg2orinmed g0 3 Harry H Porter 2006 CS322 SPAR CPart 2 45 Ogtion 1 The range Loading Immediate Data into a Register mov regorimmedregD The immediate value Will be encoded in 13 bits And signextended to to 32bits When used 4096 4095 1 0000 0101 0111 1111 1111 1111 1111 1111 0000 0101 0111 3 Harry H Porter 2006 46 CS322 SPAR CPart 2 The sethi Instruction sethi immed22 regD A 22bit value included in instruction Loaded into the hi ghorder most significant 22 bits of regD The loworder 10 bits are cleared to zero Builtin macros in the assembler hi X Returns the highorder 22 bits of X lo X Returns the loworder 10 bits of X Ogtion 2 sethi or hi value regD regD 10 value regD 3 Harry H Porter 2006 CS322 SPAR CPart 2 47 The set Synthetic Instruction QM set value regD Exumgle set 16 Any 32bit value Expands into two instructions myVar 14 sethi 14 15 hi value regD or regD 10 value regD 3 Harry H Porter 2006 48 CS322 SPAR CPart 2 The set Synthetic Instruction 02mm 3 set value regD Any 32bit value W Expands into two instructions set myVar I l4 sethi hi value regD 1d 14115 or regD 10 value regD The Delay S lot cmp The delay slot sub Do not put set in the delay slot Actually for some values set Will expand to only one instruction Still do not put set in the delay slot 3 Harry H Porter 2006 CS322 SPAR CPart 2 W Shorthand What Gets Assembled tst reg orcc reg g0 g0 clr regD or g0 g0 regD btst regorimmed reg andcc reg regorimmed g0 bset regorimmed regD or regD regorimmed regD bclr regorimmed regD andn regD regorimmed regD btog regorimmed regD xor regD regorimmed regD mov regorimmed gD or g0 regorimmed regD not regl regD xnor regl g0 regD cmp regl reg2ori d subcc regl reg2orimmed g0 nop ethi 0 g0 Mask with selected bits set to 1 3 Harry H Porter 2006 CS322 SPAR CPart 2 Registers Four groups of 8 registers each Global g Local 1 In i Out 0 Local 10 11 12 17 Used by this routine any way it wants Will be saved automatically during subroutine calls Global gO gl g2 g7 g0 is special 2 zero can not be modified Used for global data visible to all routines Not saved during subroutine calls In iO il 12 i7 00 01 02 07 Used in passing parameters tofrom subroutines The Calling Conventions Efficient parameter passing 3 Harry H Porter 2006 CS322 SPAR CPart 2 51 SPARC Calling Conventions Consider calling a subroutine The caller calls the callee From the perspective of the current routine In R egisters Arguments to this routine are found in iO il 12 i 5 arg1 arg2 arg3 arg6 Fewer than 6 arguments Use only as many as needed Additional arguments Must be passed on the stack 16 Has a special name fp the frame pointer i7 Has a special use Will be used by the return instruction This routine will put the retu1ned value into iO before returning if any Holds a pointer to the call instruction which called this routine 3 Harry H Porter 2006 52 CS322 SPAR CPart 2 SPARC Calling Conventions Out R egisters Used to pass arguments to routines we Will call Just before the call arguments to the subroutine are put into 00 01 02 05 arg1 arg2 arg3 arg6 Fewer than 6 arguments Use only as many as needed Additional arguments Must be passed on the stack If the callee returns a value This routine Will nd it in 00 m Has a special name sp the stack pointer m Has a special use When a call instruction is executed the address of the call instruction Will be placed in 07 3 Harry H Porter 2006 CS322 SPAR CPart 2 53 Caller Callee 00 3510 01 3511 02 Args 12 03 i3 04 i4 05 15 tack Manipulation sp fp Return Addr 07 H 3517 3 Harry H Porter 2006 54 CS322 SPAR CPart 2 Subroutine Calling Stack Local variables for each routine kept in the stack frame Also called activation record The stack of frames is located in main memory Frame for routine B Frame for routine A Frame for main routine 3 Harry H Porter 2006 CS322 SPAR CPart 2 55 Subroutine Calling Stack Local variables for each routine kept in the stack frame Also called activation record The stack of frames is located in main memory Frame for routine C Frame for routine B Frame for routine A Frame for main routine 3 Harry H Porter 2006 56 CS322 SPAR CPart 2 The SPARC Idea Goal Fast subroutine calling Keep the calling stack in registers But each frame has a different size Idea Cache part of the frame in registers Create a stack of frames in the CPU Avoid main memory most of the time 3 Harry H Porter 2006 CS322 SPAR CPart 2 57 Routine B R outine A main routine Stack in Main Memory 3 Harry H Porter 2006 58 CS322 SPAR CPart 2 Each has 16 registers 32bits each A R egisters for B R outine A Registers for A main routine Registers for main Stack in Main Memory Stack in CPU 3 Harry H Porter 2006 CS322 SPAR CPart 2 Each has 16 registers 32bits each R outine C R egisters for C Registers for B Registers for A main routine Registers for main R Outlne A Stack in Main Memory Stack in CPU 3 Harry H Porter 2006 CS322 SPAR CPart 2 Registers for A Global R egisters CS322 SPAR CPart 2 Registers for B Global R egisters CS322 SPAR CPart 2 R egisters for C Global R egisters CS322 SPAR CPart 2 0 Lots of onchip registers 0 Each routine gets a new set of 16 registers Access to stack ie to main memory is reduced Arguments can be passed in registers Most of the time Twig Usage 0 Return addresses are stored in registers onchip call foo 0 Relevant instructions ret f save These mstructlons ozave restore manipulate the lt E regiSter StaCk restore ret 3 Harry H Porter 2006 CS322 Optimization Part 3 Global Data Flow Analysis Examples Reaching Definitions Which DEFINITIONS reach which USEs LIVE Variable Analysis Which variables are live at a given point P Global SubExpression Elimination Which expressions reach point P and do not need to be recomputed Copy Propagation Which copies reach point P Can we do copy propagation 3 Harry H Porter 2006 CS322 Optimization Part 3 Terminology A point between two adjacent statements in a basic block or directly before the basic block or directly after the basic block 3 Harry H Porter 23 CS322 Optimization Part 3 Terminology A point between two adjacent statements in a basic block or directly before the basic block or directly after the basic block A m is a sequence of points from P1 to PN such that control could ow from P1 to PN The path may traverse several blocks from here 3 Harry H Porter 2006 3 CS322 Optimization Part 3 Reaching Definitions A definition of variable X A statement that assigns to X or might assign to X Ambiguous Definitions Might assign Unambiguous Definitions Will definitely assign Examples x z Unambiguous will d de nitely change x rea X r here x is passed by reference call foo x by copyretore or by name Where the function may access X as a nonlocal call foo 3 Harry H Porter 23 4 CS322 Optimization Part 3 Killing De nitions A de nition is killed along a path if there is an unambiguous de nition of the variable IK This definition is killed by this statement b ae 9 before it reaches this point c xa 3 Harry H Porter 2075 CS322 Optimization Part 3 A de nition D reaches a point P if there is a path from D to P along which D is not killed If X is defined at D then the value given to X might be the value of X at point P When D reaches P it means The value of X might reach P at runtime 3 Harry H Porter 23 CS322 Optimization Part 3 A definition D reaches a point P if there is a path from D to P along which D is not killed If X is defined at D then the value given to X might be the value of X at point P When D reaches P it means The value of X might reach P at runtime B2 Does D1 reach P Does D2 reach P 3 Harry H Porter 2006 CS322 Optimization Part 3 A definition D reaches a point P if there is a path from D to P along which D is not killed If X is defined at D then the value given to X might be the value of X at point P When D reaches P it means The value of X might reach P at runtime Bz Does D1 reach P YES Does D2 reach P N 0 3 Harry H Porter 23 CS322 Optimization Part 3 Safe Conservative Estimates Will the value of x reach point P The runtime value of variables may cause some paths to It may be the case that NEVER be taken In ALL executions control ALWAYS passes through B2 D may get killed in every execution The value of X may never reach point P Nevertheless we say D reaches P It is undecideable in general to determine statically which paths will be taken at runtime 3 Harry H Porter 2006 9 CS322 Optimization Part 3 USEDEFINITION Chains UD Chains For each USE of some variable X build a list of all the DEFINITIONS of X that reach this USE x cd U IQNOQ quotIIquot HONU 3 Harry H Porter 23 1 0 CS322 Optimization Part 3 USEDEFINITION Chains UD Chains For each USE of some variable X build a list of all the DEFINITIONS of X that reach this USE x cd b d ce x xbc ga 1 b 6 E 1 I 3 Harry H Porter 2006 CS322 Optimization Part 3 11 USEDEFINITION Chains UD Chains For each USE of some variable X build a list of all the DEFINITIONS of X that reach this USE ab x 05 d b C I e x x b c 4 g a 1 bf a ltamp1 A 3 Harry H Porter 23 12 CS322 Optimization Part 3 If we can deduce that the set of definitions reaching this point contains ONLY the assignment D to X then it is okay to substitute 5 for X here 0 3 Harry H Porter 2006 1 3 CS322 Optimization Part 3 DEFINITIONUSE Chains DU Chains A variable is USED at statement S if its value may required For each DEFINITION of a variable compute a list of all possible USEs of that variable xy x 1 z a x Wbutnothere 3 Harry H Porter 23 1 4 CS322 Optimization Part 3 If we can deduce that the de nition D has NO POSSIBLE USES then D is DEAD useless code and can be eliminated 3 Harry H Porter 2006 CS322 Optimization Part 3 15 The Universe U Universe the set of all DEFINITIONS in the program CFG Number them D1 D2 D3 Example 3 Harry H Porter 23 16 CS322 Optimization Part 3 Representing Sets We will work with sets How to represent Each set is represented with a Bit Vector Elma Example A D2 D4 D7 N l 3 Harry H Porter 2006 CS322 Optimization Part 3 17 Representing Sets We will work with sets How to represent Each set is represented with a Bit Vector Elma Example A D2 D4 D7 N l How to comgute set ogemtions Set Union A U B Set Intersection A n B gt Set Difference A B 3 Harry H Porter 23 18 CS322 Optimization Part 3 Representing Sets We will work with sets How to represent Each set is represented with a Bit Vector Elma Example A D2 D4 D7 A IIIIIIII How to compute set operations Set Union A U B gt A g B Set Intersection A n B A M B Set Difference A B gt A M 11 0t 3 3 Harry H Porter 2006 1 9 CS322 Optimization Part 3 Approach Figure out what happens in each basic block In the text DEDef GENB I The set of definitions appearing in block B which reach the end of B Without being KILLed before the end of the block In the text DefKill KILLB I The set of definitions KILLed by statements in block B I If B contains an unambiguous definition of variable X then add all definitions of X to KILLB unless the definition D of X also occurs in B and there are no unambiguous definitions between D and the end of B Use this info to do the entire ow graph Using DATA FLOW EQUATIONS 3 Harry H Porter 2006 CS322 Optimization Part 3 Example of GEN B Consider this Basic Block BDszc Consider D5 a definition of c Add D5 to GEN B Consider D6 a definition of X But this is KILLed before the end of the block Consider D7 a definition of X Add D7 to GEN B GEN B D5 D7 3 Harry H Porter 2006 CS322 Optimization Part 3 21 Example of KILL B Consider this Basic Block Consider D 5 an unambiguous defintion of c Add all other definitions of c to KILL B Except do not add D5 itself since this definition makes it to the end of the block Consider D7 an unambiguous defintion of X Add all other definitions of X to KILL B Except do not add D7 itself since this definition makes it to the end of the block 3 Harry H Porter 2E6 22 CS322 Optimization Part 3 Overview of the Computation For every point in the program we want to know which definitions can reach that point We will compute the set of definitions that can reach the beginning of a basic block In the text Reaches IN B Then using GEN B and KILL B we will compute the set of definitions reaching the end of the basic block OUT B Then we will use OUT B to compute the set of definitions that can reach other basic blocks And we will repeat until we learn which definitions could possibly reach which blocks 3 Harry H Porter 2006 CS322 Optimization Part 3 The Data Flow Algorithm Approach Build the IN and OUT sets simultaneously by successive approximations Given A control flow graph of basic blocks Assume GENB and KILLB have already be computed for each basic block Output INB and OUTB for each basic block 3 Harry H Porter 23 CS322 Optimization Part 3 Start by setting INB to for each basic block Then compute OUTB from the previous estimate of INB Finally propagate OUTB to the INB for all successor blocks to B Repeat until no more changes As the definitions ow through the graph the IN and OUT sets grow and grow The approximation gets closer and closer Conservative May overestimate how far definitions Will reach ie the results may be larger than truly necessary 3 Harry H Porter 2006 CS322 Optimization Part 3 A Recurrence a set of simultaneous equations INB ux P is a predecessor of B OUTB 39 GENE U INB KILLBV 3 Harry H Porter 23 CS322 Optimization Part f eaCh b1 Ck B Q Initialize OUT on the OUT B 1 GENB assumption that endf or INB for all blocks while change do for each block B do INB U OUTP P is a predecessor of B OUTB GENB U INB KILLB endfor endwhile 3 Harry H Porter 2006 CS322 Optimization Part f eaCh b1 Ck B Q Initialize OUT on the OUT B 1 GENB assumption that endf or INB for all blocks change true while change do change false OUT for each block B do U OUTP INB P is a predecessor of B OLDOUT OUTB OUTB GENB U INB KILLB i OUTB e OLDOUT then change true endif endfor endwhile 3 Harry H Porter 2006 CS322 Optimization Part3 GENB1 D1 D2 D3 K1LLB lDlDOOIOJ0 D 1 00401511 7 GENBDD 2 060 51100 KILLBDDD 2 1110 0071 B1 Example GENB3D 0 0 0010 K1LLB3D3 001 0000 GENB4 D 0 00 K1LLB4 D1 D4 10 100 O O 1 32 3 4 OUT 111 0000 000 1100 000 0010 000 0001 3 Harry H Porter 2006 CS322 Optimization Part3 GENB1 Df D3 D8 K1LLB lDlD 0D0 D 11 1 00401511 7 GENB2D D 0 0 100 Example K1LLB2 D1 D D7 110 001 GENB3D 30 0010 K1LLB3D3 B 001 0000 3 GENB4D 00 0001 K1LLB4 D1 D4 100 1000 B1 32 B3 B4 OUT 111 0000 000 1100 000 0010 000 0001 IN 000 0000 111 0001 000 1100 000 1110 3 Harry H Porter 23 3 0 CS322 Optimization Part 3 Example B1 KILLBDD D D 1 0040 1511i 7 GENB1D1D2D3 111 0000 GENB DD 2 000 51100 KILLBDDD 2 1110 0071 GENB3D 0 0 0010 KILLB3D3 001 0000 GENB4 D 0 00 KILLB4 D1 D4 10 100 94 O O 1 32 B3 4 OUT 111 0000 000 1100 000 0010 000 0001 IN 000 0000 111 0001 000 1100 000 1110 OUT 111 0000 001 1100 000 1110 000 0111 3 Harry H Porter 2075 3 1 CS322 Optimization Part 3 GENB1 Di D3 D8 1 KILLB lDlD 0D0 D 11 1 004015111 7 GENB2D D 0 0 100 Example KILLBZ D1 D D7 110 001 GENB3D 00 0010 KILLB3D3 B 001 0000 3 GENB4D 00 0001 KILLB4 D1 D4 100 1000 B1 32 B3 B4 OUT 111 0000 000 1100 000 0010 000 0001 IN 000 0000 111 0001 000 1100 000 1110 OUT 111 0000 001 1100 000 1110 000 0111 IN 000 0000 111 0111 001 1100 001 1110 3 Harry H Porter 23 3 2 CS322 Optimization Part 3 B1 Example GENB1D1D2D3 111 0000 KILLBDD D D 1 0040 15111 7 GENB DD 2 060 51100 KILLB2 D1 th0 1371 110 GENB3D 0 0 0010 KILLB3D3 001 0000 GENB4 D 0 00 KILLB4 D1 D4 10 100 O O B1 32 B3 B4 OUT 111 0000 000 1100 000 0010 000 0001 IN 000 0000 111 0001 000 1100 000 1110 OUT 111 0000 001 1100 000 1110 000 0111 IN 000 0000 111 0111 001 1100 001 1110 OUT 111 0000 001 1110 000 1110 001 0111 3 Harry H Porter 2075 3 3 CS322 Optimization Part 3 GENB1 Di D3 D8 1 KILLB1D1D 0D0 D 11 1 004015i11 7 GENB2D D Example KILLB2 ODS D 1370 110 001 GENBsD 30 0010 KILLBsD3 B 001 0000 3 GENB4D 00 0001 KILLB4 D1 D4 100 1000 B1 32 B3 B4 OUT 111 0000 000 1100 000 0010 000 0001 IN 000 0000 111 0001 000 1100 000 1110 OUT 111 0000 001 1100 000 1110 000 0111 IN 000 0000 111 0111 001 1100 001 1110 OUT 111 0000 001 1110 000 1110 001 0111 IN 000 0000 111 0111 001 1110 001 1110 3 Harry H Porter 23 CS322 Optimization Part 3 Example B1 1 1 0 GENB3 D KILLB3 D3 0 0 GENB4 D O O 101 0 0 0 KILLB4 D1 D430 GENB1 D1 D2 D3 1 1 1 0 0 0 0 KILMBI 034915113 D7 GENB D D mg 03331130 003 0 0 0 0 1 0 1 0 0 0 0 B1 32 B3 B4 OUT 111 0000 000 1100 000 0010 000 0001 IN 000 0000 111 0001 000 1100 000 1110 OUT 111 0000 001 1100 000 1110 000 0111 IN 000 0000 111 0111 001 1100 001 1110 OUT 111 0000 001 1110 000 1110 001 0111 IN 000 0000 111 0111 001 1110 001 1110 OUT 111 0000 001 1110 000 1110 001 0111 3 Harry H Porter 2075 3 5 CS322 Optimization Part 3 IN IN D3D4D5D6 OUT D4 D5 D6 OUT D1 D2 D3 IN D3 D4 D5 D6 OUT D3 D5 D6 D7 B1 32 B3 134 IN 000 0000 111 0111 001 1110 001 1110 OUT 111 0000 001 1110 000 1110 001 0111 3 Harry H Porter ZEN IND1D2D3D5D6D7 OUT D3 D4 D5 D6 36 CS322 Optimization Part 3 This algorithm converges OUTB never decreases Once in OUTB a definition stays there Eventually no changes will be made to OUTB An upper bound on the while loop Number of nodes in the ow graph Each iteration propagates reaching de nitions The while loop will converge quickly if you select a good order for the nodes in the for loop This algorithm is e icient in practice 3 Harry H Porter 2006 3 7 CS322 Optimization Part 3 LIVE Variable Analysis A similar Data Flow Algorithm Goal Compute IN and OUT However it will work backwards ie data will flow upwards against the arrow directions Given Comgute Which variables Which are LIVE variables here are LIVE here 3 Harry H Porter 23 3 8 CS322 Optimization Part 3 LIVE Variable Analysis Then Compute the OUT set from all the IN sets of the block s successors 3 Harry H Porter 2006 CS322 Optimization Part 3 39 LIVE Variable Analysis Then Compute the OUT set from all the IN sets of the block s successors Given Given 3 Harry H Porter 23 40 CS322 Optimization Part 3 LIVE Variable Analysis Then Compute the OUT set from all the IN sets of the block s successors Compute Given Given 3 Harry H Porter 2006 CS322 Optimization Part 3 41 LIVE Variable Analysis Then Compute the OUT set from all the IN sets of the block s successors In 0 ows u wards against the ow graph edges 3 Harry H Porter 23 42 CS322 Optimization Part 3 De nitions Variable X is LIVE at some point P if its value might be used at some point later on a path starting at P DEF B the set of variables de nitely assigned values in block B prior to any use in B USE B the set of variables Whose values may be used in B prior to any definitions of the variable IN B the set of variables LIVE at the beginning of B OUT B e set of variables LIVE at the end of B 1 3 Harry H Porter 2006 N 0 9 the 39 v 43 CS322 Optimization Part 3 De nitions Variable X is LIVE at some point P if its value might be used at some point later on a path starting 2am DEF B the set of variables definitely assigned values in block B prior to any use in B Text UEVar USE B the set of variables Whose values may be used in B prior to any definitions of the variable IN B the set of variables LIVE at the beginning of B OUT B e set of variables LIVE at the end of B Text LiveOut 2006 Note these 39J 39 39 3 Harry H Porter CS322 Optimization Part 3 Recurrence Equations to be Solved Xy LIVE I zLIVE I I wx LIVE I 3 Harry H Porter 2006 CS322 Optimization Part 3 45 Recurrence Equations to be Solved Wxyz must be LIVE here Xy LIVE l zLIVE I I wx LIVE I 3 Harry H Porter ns 46 CS322 Optimization Part 3 Input Flow graph of basic blocks DEF and USE for each block Output OUTB Live variables at end of B Algorithm m each block B do INB IN gt endfor while changes occur for any IN set E E each block B Q U INS OUTB S is a successor of B INB USEB U OUTB DEFB endfor endwhile Algorithm to Compute LIVE Variables 3 Harry H Porter 2006 CS322 Optimization Part 3 47 Example Compute LIVE variables B At the end of each block 3 Harry H Porter 23 48 CS322 Optimization Part 3 Computing Available Expressions An expression X B y Binary expressions only Any operator Examples a b Wx y4 An expression is available at point P if every path to P computes it M there are no subsequent assignments to x or y between the last evaluation of x 9 y and P A block generates x 9 y if it evaluates x 9 y and does not subsequently assign to x or y A block kills x 13 y if it assigns to x or y Without subsequently recomputing x 9 y 3 Harry H Porter 2006 CS322 Optimization Part 3 Example Which expressions are available xyz yx w awz zx w YYz 3 Harry H Porter 23 5 0 CS322 Optimization Part 3 Example Which expressions are available U yz x w wz xyz yx w awz zx w YYz 3 Harry H Porter 2006 CS322 Optimization Part 3 51 Example Which expressions are available U yz x w wz Avail z xY yx w awz zx w YYz 3 Harry H Porter 23 52 CS322 Optimization Part 3 Example Which expressions are available U yz x w wz Avail x yz AV l yz yx w awz zx w yyz 3 Harry H Porter 2006 CS322 Optimization Part 3 53 Example Which expressions are available U yz x w wz lt Avail xy z AV l yz yx w 6 39Avail x w a wz z x w y yz 3 Harry H Porter 23 54 CS322 Optimization Part 3 Example Which expressions are available U yz x w wz Avail z Avail yz yx w Avail x w azwz Avail x w wz z x w yzyz 3 Harry H Porter 2006 CS322 Optimization Part 3 55 Example Which expressions are available U yz x w wz Avail z Avail yz w Avail x w azwz Avail x w wz yx zx w Avail x w yzyz 3 Harry H Porter 23 56 CS322 Optimization Part 3 Example Which expressions are available U yz x w wz Avail xyz Avail yz y x w Avail x w a w z amp Avail x w wz z x w Avail x w Y 13 z lt Avail x w 3 Harry H Porter 2006 CS322 Optimization Part 3 57 Computing Available Expressions The Universe The set of all expressions appearing in the flow graph Example U a b Wx y4 x1 b c EGEN B The set of expressions computed in the block x y is included if some statement in B evaluates it l the block does not assign to x or y after that EKILL B The set of expressions that are invalidated because EIN B The set of expressions available at the beginning of block B EOUT B The set of expressions available at the end of block B the block contains an assignment to a variable they use 3 Harry H Porter 23 58 CS322 Optimization Part 3 Computing Available Expressions The Universe The set of all expressions appearing in the flow graph Example U a b Wx y4 x1 b c T t DEE EGEN B 9quot X1 0 The set of expressions computed in the block x 13 y is included if some statement in B evaluates it l the block does not assign to x or y after that EKILL B The set of expressions that are invalidated because the block contains an assignment to a variable they use EIN B Text Avail The set of expressions available at the beginning of block B EOUT B The set of expressions available at the end of block B 3 Harry H Porter 2006 CS322 Optimization Part 3 59 Recurrence Equations to be Solved EOUT B EINB P is a predecessor of B EOUT P For 131 EGENB EINB EKILL B the initial black EIN B1 l i Nothing aVailaIzle before the initial block 3 Harry H Porter 23 60 CS322 Optimization Part 3 Forward Propagation like reaching definitions but f7 instead of U 3 Reaching De nitions Start with estimates that are too small and enlarge them INB U OUTP ppredecessor Available Expressions Start with estimates that are too large and shrink them EINB n EOUT P ppredecessor 3 Harry H Porter 2006 CS322 Optimization Part 3 Algorithm to Compute Available Expressions Input EGEN and EKILL for each block Output EINB Expressions available at begining of B Algorithm EINBl EOUTB1 EGENB1 f each block B except B1 Q EOUTB U EKILLB endfor while changes occur for any EOUT set do f each block B except B1 do E OUTP s a prdecessor of B EGENB U EINB EKILLB E INB P 1 EOUT B endf or endwhile 3 Harry H Porter 23 62 CS322 Optimization Part 3 Conservative Safe Estimates 0 Begin by assuming all expressions available anywhere 0 Work toward a smaller solution 0 If there is a possible definition of X or y then consider X B y as not available 0 We Will tend to err by eliminating too many expressions from EIN and EOUT 0 Our computed result Will be a subset of the expressions that are truly available at point P 0 If our computation determines that x 9 y is available at point P then it surely is We can eliminate its recomputation 3 Harry H Porter 2006 6 3 CS322 Optimization Part 3 7 quot 39 quot nmmnn Global Subexnressions The Transformation a 3 Harry H Porter 23 6 4 CS322 Optimization Part 3 17 quot quot nmmnn Global Suhexnreuions The Transformation Create a new temporary 3 Harry H Porter 2006 65 CS322 Optimization Part 3 7 quot 39 quot nmmnn Global thexnreeeiom The Transformation And use it here 3 Harry H Porter 23 66 CS322 Optimization Part 3 17 quot quot nmmnn Global SubeXDressions The Transformation Copy Propagation may eliminate these statements 3 Harry H Porter 2006 CS322 Optimization Part 3 67 Algorithm Input Flow Graph Available Expression Information Output Revised Flow Graph Step 1 Find a statement such as W X 9 such that expression X y is available directly before it Or X 6 y is available in EINB for the block and there are no assignments to X or y before this statement 3 Harry H Porter 23 68 CS322 Optimization Part 3 Algorithm Input Flow Graph Available Expression Information Output Revised Flow Graph Step 1 Find a statement such as w x 9 y such that expression X B y is available directly before it Or X y is available in EINB for the block and there are no assignments to X or y before this statement Step 2 Follow the flow graph edges backward until you hit an evaluation of X B y Find all such evaluations 3 Harry H Porter 2006 CS322 Optimization Part 3 69 Algorithm Step 339 Create a new temporary say t 3 Harry H Porter 23 70 CS322 Optimization Part 3 Algorithm Step 339 Create a new temporary say t Step 4 Replace all statements found in step 2 a X 9 y b X 9 y c l l X y X y t t XC39By we a t t a b 3 Harry H Porter 2006 CS322 Optimization Part 3 71 Algorithm Step 3 Create a new temporary say t Step 4 Replace all statements found in step 2 axy bxy cXy tXBy tX y txBy a t b t c t Step 5 Replace w x Dy W t 3 Harry H Porter 23 72 CS322 Optimization Part 3 Algorithm Step 339 Create a new temporary say t Step 4 Replace all statements found in step 2 axDy bXCDy cXBy tX y tX y tX y at bt ct Steps Replace Notes wxBy Wt Copy propagation may eliminate some of the extra assignments but might not 0 Program size could grow 0 Want to limit this effect If more than 1 statement found in step 2 just forget it 3 Harry H Porter 2006 CS322 Optimization Part 3 73 Copy Propagation A copy statement xy Where do the copies come from 0 IR code generation 0 Common SubExpression Elimination 0 Other Optimizations 3 Harry H Porter 2006 74 CS322 Optimization Part 3 Copy Propagation We can use y instead of X if 0 The only de nition of X reaching a bCBX is X y and 0 There is no assignment to y on any path from X y to a b X 3 Harry H Porter 2006 7 5 CS322 Optimization Part 3 Copy Propagation There must be M assignment to y on my path m X y to a 3 Harry H Porter 23 7 6 CS322 Optimization Part 3 Copy Propagation We can not propagate the copy in this example There must be M assignment to y on my path fromX yt0ab X 3 Harry H Porter 2006 7 7 CS322 Optimization Part 3 We can use y instead of X if 0 The only de nition of X reaching a bCBX is X y and 0 There is no assignment to y on any path fromXytoab6X 3 Harry H Porter 2006 7 8 CS322 Optimization Part 3 We can use y instead of X if 0 The only de nition of X reaching a b X is X y and Compute the UD Chains and use that info to determine this 0 There is no assignment to y on any path fromXytoab X 3 Harry H Porter 2006 7 9 CS322 Optimization Part 3 We can use y instead of X if 0 The only definition of X reaching a bCBX is X y and Compute the UD Chains and use that info to determine this 0 There is no assignment to y on any path fromXytoab6X A new Data Flow problem 3 Harry H Porter 2006 8 0 CS322 Optimization Part 3 Look at the entire Control Flow Graph Identify all copy statements Two copy statements are different even if they have the same variables 3 Harry H Porter 2006 CS322 Optimization Part 3 Look at the entire Control Flow Graph Identify all copy statements Two copy statements are different even if they have the same variables 3 Harry H Porter ns 82 CS322 Optimization Part 3 Look at the entire Control Flow Graph Identify all copy statements Two copy statements are different even if they have the same variables 3 Harry H Porter 2006 CS322 Optimization Part 3 A block kills a copy X y if it contains an assignment to X or y 39 l 3 Harry H Porter ns 84 CS322 Optimization Part 3 A block kills a copy X y if it contains an assignment to X or y unless the block contains the copy itself and does not assign to X or y after the coEy 8 5 3 Harry H Porter 2006 CS322 Optimization Part 3 For each basic block we rst compute CGEN B The set of all copy statements in basic block B not killed before they reach the end of the block CKILL B The set of all copies in U that are killed by block B 3 Harry H Porter ns 8 6 CS322 Optimization Part 3 Then Use Data Flow to Compute CIN B The set of all copy statements X y such that every path from the initial block to the beginning of B contains the copy and there are no assignments to X or y on any path from the copy statement to the beginning of block B Technically there must be no assignments on the path between the last occurrence of the copy and the beginning ofblock B COUT B Same at the end of the block 3 Harry H Porter 2006 8 7 CS322 Optimization Part 3 The Data Flow Eguations CDUTB CGENEB U CINB CKIIIB CINB 2n CQUMP J 1303 I the initial black P is a predecessor of B CIN B1 i i Nothing awilalzle before the initial block 3 Harry H Porter 23 8 8 CS322 Optimization Part 3 The Data Flow Eguations G GENB U GINB CKIILB 7 COUT B CINB CoxJT P1 G1N31 l l Nothing available before the initial block For 31 P is a Predecessor of B thezmtmi block These equations are identical to the Available Expression equations 3 Harry H Porter 2006 CS322 Optimization Part 3 89 Copy Deletion Algorithm Input Control Flow Graph UD Chain info DU Chain info Results of Data Flow Analysis CIN B for each block Output Modi ed Flow Graph 3 Harry H Porter 23 90 CS322 Optimization Part 3 Copy Deletion Algorithm f each copy statement C xy do Determine the set of all uses of x that are reached by C Call such stmts U1 U2 U3 UN E each use Ui x do Let B be the basic block containing Ui E C E CINB and there are no definitions of x or y prior to Ui within B then It might be okay to delete C Keep checking other uses else We must not delete C Skip to the next copy statement endif endfor delete C modify all uses U1U2UN endfor 3 Harry H Porter 2006 91 CS322 Target Generation Part 1 Lexer Parser Type Checking I Intermediate Code Generation Front End Symbol Table Intermediate Representation Information BackEnd Final Code Generation Target Code eg SPARC 5 file Executable eg an a0ut file 3 Harry H Porter 2006 CS322 Target Generation Part 1 Lexer Parser Type Checking I Intermediate Code Generation Front End Symbol Table Intermediate Representation Information BackEnd Final Code Generation Byte Odes Java Approach Virtual Machine Interpreter 3 Harry H Porter 2006 CS322 Target Generation Part 1 Type Checking I Front End Intermediate Code Generation Symbol Intermediate Representation Table Information BaCk39End Final Code Generation Mach39 e Code CPU 3 Harry H Porter 2006 CS322 Target Generation Part 1 Out ut to Assembl Code vs machine code Breaks code generation task into 2 phases 0 Compiler back end 0 Assembler Easier to debug compiler output Slightly slower 3 Harry H Porter 2006 CS322 Target Generation Part 1 Porting the Compiler Porting to a new target machine architecture Re Write the backend Intermediate Code BackEnd Target Code 3 Harry H Porter 2006 CS322 Target Generation Part 1 Porting the Compiler Porting to a new target machine architecture Re Write the backend Intermediate Code BackEnd Target Code SpecificationDriven Approaches Code GeneratorGenerators Intermediate Code CPU Speci cation eg set of rules Target Code 3 Harry H Porter 2006 CS322 Target Generation Part 1 Reguirements 0 Target code must be correct 0 Target code should be efficient 0 Back end should run quickly Want ogtimal code sequences NP Complete Generate all correct code sequences and see which is best Optimal The target program executes faster takes less memory 3 Harry H Porter 2006 CS322 Target Generation Part 1 Code Generation Algorithms Algorithm 1 lt Easiest We ll use for PCAT Algorithm 2 Algorithm 3 lt Most complex 3 Harry H Porter 2006 CS322 Target Generation Part 1 Code Generation Algorithms Algorithm 1 lt Easiest We ll use for PCAT Algorithm 2 Algorithm 3 lt Most complex Example Target Machine 2Address Architecture source destination mov xr0 add yr0lt mov r0 Z r0r0y store back into memory 3 Harry H Porter 2006 CS322 Target Generation Part 1 Code Generation Algorithm 1 Statementbystatement generation Code for each IR instruction is generated independently of all other IR instructions IRCode a bc d ae 3 Harry H Porter 2006 10 CS322 Target Generation Part 1 Code Generation Algorithm 1 Statementbystatement generation Code for each IR instruction is generated independently of all other IR instructions IRCode a bc d ae T arget Code mov br0 add cr0 a b c mov r0a mov ar0 add er0 d a e mov r0d 3 Harry H Porter 2006 CS322 Target Generation Part 1 Code Generation Algorithm 1 Statementbystatement generation Code for each IR instruction is generated independently of all other IR instructions IRCode a bc d ae T arget Code mov br0 add cr0 a b c mov r0a mov ar0 add er0 d a e mov r0d This instruction is totally y39 3 Harry H Porter 2006 CS322 Target Generation Part 1 Code Generation Algorithm 1 Statementbystatement generation Code for each IR instruction is generated independently of all other IR instructions RC 0 19 ALSO Registers are not a b c used effectively 6 a e T arget Code mov br0 add cr0 a b c mov r0a mov ar0 add er0 d a e mov r0d 3 Harry H Porter 2006 CS322 Target Generation Part 1 Machine Idioms IRCode x x 5 Target Code mov x r0 add 5 r0 mov r0x 3 Harry H Porter 2006 CS322 Target Generation Part 1 Machine Idioms IRCode x x 5 Target Code mov x rO add 5 r0 mov r0 x IRCode x x 1 Target Code mov x rO add 1 r0 mov r0x 3 Harry H Porter 2006 CS322 Target Generation Part 1 15 IRCode x x 5 Target Code mov x r0 add 5 r0 mov r0x IRCode x x 1 Target Code mov x r0 add 1 r0 mov r0x Target Code mov x rO inc r0 mov r0 x Machine Idioms 3 Harry H Porter 2006 16 CS322 Target Generation Part 1 Machine Idioms add 1 r0 mov r0 x Target Code mov x rO inc r0 mov r0x Target Code inc x IRCode x x 5 Target Code mov x r0 add 5 r0 mov r0 x IRCode x x 1 Target Code mov x r0 3 Harry H Porter 2006 CS322 Target Generation Part 1 17 Using Registers Goal Keep some variables in registers instead of in memory Problem Not enough registers I Register Allocation Problem I Which variables will reside in registers at a given point in the program I Register Assignment Problem I Which register will we use for a variable For a given variable we may use a different register at different points in the program 3 Harry H Porter 2006 18 CS322 Target Generation Part 1 Assume M It 1 I t t u 1p y HS rue Ion Must specify an even numbered register mul y r4 r5 xy gt r4r5 Multiply Instruction div y r4 4 Must specify an even numbered register r4r5 y gt r4r5 SRDA Shift Right Double Arithmetic srda 32 r6 r6 r7 r6 r7 19 3 Harry H Porter 2006 CS322 Target Generation Part 1 IR Code t a b t t c t t d Target Code mov a r1 add b r1 mul c r0 div d r0 mov r1 t 20 3 Harry H Porter 2006 CS322 Target Generation Part 1 IR Code IR Code t a b t a b t t c t t c t t d t t d Target Code Target Code mov ar1 mov ar0 add br1 add br0 mul cr0 add cr0 div dr0 srda 32 rO mov r1t div dr0 mov r1t 3 Harry H Porter 2006 CS322 Target Generation Part 1 IR Code IR Code t a b t a b t t c t t c t t d t t d Target Code Target Code mov a r1 mov a r0 add b r1 add b r0 mul c r0 add c r0 div dr0 srda 32r0 mov r1 t div d r0 Conclusion mov r1 t Where you put the result of tab either r0 or r1 depends on how it will be used later A chickenandegg problem 3 Harry H Porter 20 06 CS322 Target Generation Part 1 Evaluation Order The IR code establishes an order on the operations Simplest Approach 0 Don t mess with re ordering 0 Target code will perform all operations in the same order as the IR code Trickier Approach 0 Consider reordering operations 0 May produce better code Get operands into registers just before they are needed May use registers more efficiently 3 Harry H Porter 2006 CS322 Target Generation Part 1 23 Moving Results Back to Memory After an operation the result will be in a register I mmediatelg Wait as long as possible before moving it back Only move data back to memory at the end or when absolutely necessary May be able to avoid reloading it later When to move results from registers back into memory Move data back to memory just after it is computed May make more registers available for use elsewhere 3 Harry H Porter 2006 24 CS322 Target Generation Part 1 An Example Target Machine QM A 2address Architecture mov 2 operands at most op sourc destinatlon add quota sub Address Modes mul Absolute Memory Address x gt y W quotIY k sub x y y X y Register mov r0 r1 r3 r2 gt r3 sub r2 r3 Literal Data is included in the mov 39 r1 instruction directly sub 4 7 r2 Register contains an address Indirect Register mov r0 I I1 Moves dalta 1139 to ivord Indirect plus Index pomte to y r mov r0 r148 Use r148 as an address Double Indirect Go to memory and fetch a second mov r0 r148 address p p points to the word 3 Harry H Porter 2006 CS322 Target Generation Part 1 Evaluating A Potential Code Seguence Each instruction has a cost Cost 2 Execution Time Execution Time is difficult to predict Pipelining Branches Delay Slots etc Goal Approximate the real cost A Cost Model 3 Harry H Porter 2006 CS322 Target Generation Part 1 Evaluating A Potential Code Seguence Each instruction has a cost Cost 2 Execution Time Execution Time is difficult to predict Pipelining Branches Delay Slots etc Goal Approximate the real cost A Cost Model Simplest Cost Model Code Length Execution Time Just count the instructions 3 Harry H Porter 2006 CS322 Target Generation Part 1 A Better Cost Model Look at each instruction Compute a cost in units Count the number of memory accesses Cost 1 Costofoperandl CostofoperandZ Costofresult example cost Absolute 1Iemory Address 2 1 R egister r0 0 Literal 3 9 0 Indirect R egister r1 1 Indirect plus Index r148 1 Double Indirect r148 2 Example sub 97 r5 r5 97 gt r5 Cost10001 Example sub 97 r5 r5 97 gt r5 Cost11013 Example sub r1 r548 r548 r1 gt r548 Cost12126 3 Harry H Porter 2006 CS322 Target Generation Part 1 Code Generation Example IR Code x y 2 Translation 1 mov y x 3 add 22 4 C05t 7 3 Harry H Porter 2006 CS322 Target Generation Part 1 Code Generation Example IR Code x y 2 Translation 1 mov y x 3 C t 7 add 2 x 4 OS W mov y r1 2 14 9330quot 1 add 2 r1 2 Cost 5 Use Reglsters mov r1 2 2 3 Harry H Porter 2006 CS322 Target Generation Part 1 Code Generation Example IR Code x y 2 Translation 1 mov y x 3 add 22 4 C05t 7 Translation 2 mov yr1 2 M I add 2 r1 2 Cost 5 Use Registers mov r1 x 2 Translation 3 Lesson 2 Assume y is in r1 and z is in r2 Keep variables in regiswrs Assume y will not be needed again add r2 r1 1 mov r1 x 2 COSt 3 3 Harry H Porter 2006 CS322 Target Generation Part 1 Code Generation Example IR Code x y 2 Translation 1 mov y x 3 C t 7 add 2 x 4 OS Translation 2 mov yr1 2 M I add 2 r1 2 Cost 5 Use Registers mov r1 x 2 Translation 3 Lesson 2 Assume y is in r1 and z is in r2 Keep variables in regiswrs Assume y will not be needed again add r2 r1 1 Lesson 3 mOV r1 Ix 2 cost 3 Avoid or delay storing Translation 4 into memory Assume y is in r1 and z is in r2 Assume y will not be needed again Assume we can keep x in a register add r2 r1 1 10m 1 3 Harry H Porter 2006 CS322 Target Generation Part 1 Code Generation Example IR Code x y 2 Translation 1 mov y x 3 C t 7 add 2 x 4 OS Translation 2 mov yr1 2 M I add 2 r1 2 Cost 5 Use Registers mov r1 x 2 Translation 3 Lesson 2 Assume y is in r1 and z is in r2 Keep variables in regiswrs Assume y will not be needed again add r2 r1 1 Lesson 3 mov r1 x 2 COSt 3 Avoid or delay storing Translation 4 into memory Assume y is in r1 and z is in r2 Assume y will not be needed again Lesson 4 not illustrated Assume we can keep x in a register Use di erent addressin add r2r1 1 10m 1 ff g modes effectively 3 Harry H Porter 2006 CS322 Target Generation Part 1 Basic Blocks Break IR code into blocks such that The block contains amp transferofcontrol instructions except as the last instruction 0 A sequence of consecutive statements 0 Control enters only at the beginning 0 Control leaves only at the end 3 Harry H Porter 2006 CS322 Target Generation Part 1 Basic Blocks Label43 t3 t4 7 t5 t3 8 if t5 lt 9 goto Label44 t6 1 goto Label45 Label44 t6 0 Label45 t7 t6 3 t8 y z x t8 4 y t8 x Label46 z w x 3 Harry H Porter 2006 CS322 Target Generation Part 1 35 Basic Blocks Label43 t3 t4 7 t5 t3 8 B1 if t5 lt 9 goto Label44 t6 1 B2 goto Label 45 Label44 t6 0 B3 Label45 t7 t6 3 t8 y z x t8 4 B4 y t8 x Label46 z w x t9 z 5 B5 3 Harry H Porter 2006 36 CS322 Target Generation Part 1 Control Flow Graph 131 t3t47 t5t3 8 if t5 lt 9 goto B3 Bz t61 33 t6 0 B4 t7 t63 t8 yz xt8 4 yt8x B5 zwx t9z 5 3 Harry H Porter 2006 CS322 Target Generation Part 1 37 Al orithm to Partition Instructions into Basic Blocks Concept Leader T he rst instruction in a basic block Idea Identify leaders Any statement that immediately follows a branch goto a call instruction is a leader A Basic Block consists of A leader and all statements that follow it up to but not including the next leader The first instruction of each routine is a leader 0 Any statement that is the target of a branch goto is a leader 3 Harry H Porter 2006 38 CS322 Target Generation Part 1 Label4 3 Label4 4 Label4 5 Label4 6 Identify Leaders t3 t4 7 t5 t3 8 if t5 lt 9 goto Label44 1 goto Label45 t6 0 t7 t6 3 3 Harry H Porter 2006 CS322 Target Generation Part 1 39 Label4 3 Label4 4 Label4 5 Label4 6 Identify Leaders t3 t4 7 t5 t3 8 if t5 lt 9 goto Label44 t6 1 goto Label45 Targets of GOTOs 3 Harry H Porter 2006 40 CS322 Target Generation Part 1 Identify Leaders Label43 t3 t4 7 t5 t3 8 if t5 lt 9 goto Label44 t6 1 goto Label45 Label44 t6 0 Label45 t7 t6 3 t8 y z x t8 4 y t8 x Label46 z w x Follows a GOTO 3 Harry H Porter 2006 CS322 Target Generation Part 1 41 Identify Leaders Label43 t3 t4 7 t5 t3 8 if t5 lt 9 goto Label44 t6 1 goto Label 45 Label44 t6 0 Label45 t7 t6 3 t8 y z x t8 4 y t8 x Label46 z w x t9 z 5 3 Harry H Porter 2006 42 CS322 Target Generation Part 1 Look at Each Basic Block in Isolation Use B The set of variables used ie read by the Basic Block before being written updated The inputs to the BB Def B The set of variables in the Basic Block that are written assigned to The outputs of the BB B7x yv z z x y UseB7 v z 5 DefB7 if w lt v goto B9 x 3 Harry H Porter 2006 CS322 Target Generation Part 1 43 Use 3 W The set of variables used ie read by the Basic Block before being written updated The inputs to the BB Def B The set of variables in the Basic Block that are written assigned to The outputs of the BB gt B7x yv z x y US B7yVW v z 5 DefB7 if w lt v goto B9 3 Harry H Porter 2006 44 CS322 Target Generation Part 1 Use 3 W The set of variables used ie read by the Basic Block before being written updated The inputs to the BB Def B The set of variables in the Basic Block that are written assigned to The outputs of the BB B x 39 7 Y V z x y UseB7yvW v z 5 DefB7Xzv if w lt v goto B9 x 3 Harry H Porter 2006 CS322 Target Generation Part 1 45 Use 3 W The set of variables used ie read by the Basic Block before being written updated The inputs to the BB Def B The set of variables in the Basic Block that are written assigned to The outputs of the BB B x 39 7 Y V z x y UseB7yvW v z 5 DefB7Xzv if w lt v goto B9 View the basic block as a function ltX z vgtfy v w Okay to transform the block as long as it computes the same function 3 Harry H Porter 2006 46 CS322 Target Generation Part 1 Common SubEX ression Elimination A Basic Block x b c a d z b c We compute bc twice 3 Harry H Porter 2006 CS322 Target Generation Part 1 47 Common SubEX ression Elimination Transform x b c y a d d z b c We compute bc twice Into x b c y a d d x 3 Harry H Porter 2006 48 CS322 Target Generation Part 1 Common SubEX ression Elimination Transform x b c y a d d b c What about ad z a d Do we need to recompute Into x b c y a d d x z 3 Harry H Porter 2006 CS322 Target Generation Part 1 49 Common SubEX ression Elimination Transform x b c y a d d b c What about ad z z a d Do we need recompute Into x b y a d d x Yes 2 a d d has been changed since ad computed Now ad may compute a different value 3 Harry H Porter 2006 50 CS322 Target Generation Part 1 Sometimes we can change the order of instructions xbc xbc def azxy axygtltdzef Reordering Instructions in a Basic Block 3 Harry H Porter 2006 CS322 Target Generation Part 1 51 Sometimes we can change the order of instructions gtlt2 i f d bc x x def a xygtltd oxu so Reordering Instructions in a Basic Block DUN HIO39lt 3 Harry H Porter 2006 52 CS322 Target Generation Part 1 Reordering Instructions in a Basic Block Sometimes we can change the order of instructions Sgtlta f xbc x def xygtltd But some changes would change the program in II oxu DUN HIO39lt 3 Harry H Porter 2006 CS322 Target Generation Part 1 53 Reordering Instructions in a Basic Block Sometimes we can change the order of instructions gtlt2 i f d xbc x def a azxygtltdz But some changes would change the program oxu DUN HIO39lt When can we exchange these two instructions x v1v2 y v3v4 Any variables including possibly x and y 3 Harry H Porter 2006 54 CS322 Target Generation Part 1 Reordering Instructions in a Basic Block Sometimes we can change the order of instructions xbc xbc azxy def azxygtltxzbc azxygtltdzef ef But some changes would change the program When can we exchange these two instructions x vlv2 y v3v4 If and only vl i y v2 a y Any variables including V3 a x possibly x and y v 1 a x 3 Harry H Porter 2006 CS322 Target Generation Part 1 Live Variables Is some variable x live at some point P in the program Could the value of X at point P ever be needed later in the execution 3 Harry H Porter 2006 CS322 Target Generation Part 1 Live Variables Is some variable x live at some point P in the program Could the value of X at point P ever be needed later in the execution Point in a program A point in a program occurs between two statements lt a39 bclt PointP defE b5E C 3 Harry H Porter 2006 CS322 Target Generation Part 1 Live Variables Is some variable x live at some point P in the program Could the value of X at point P ever be needed later in the execution Point in a program A point in a program occurs between two statements abc d ze f Poth cb 5E Is it possible that the program will ever read from X along a path from P before X is written stored into 3 Harry H Porter 2006 CS322 Target Generation Part 1 Dead Variables A Variable is Dead atpoint P Not Live Value will de nitely never be used No need to compute it If value is in register no need to store it 3 Harry H Porter 2006 CS322 Target Generation Part 1 59 Liveness Example cb 5 a z b c At thisp0int gtC1 Is b llve e f 3 Harry H Porter 2006 60 CS322 Target Generation Part 1 Liveness Example a b c At this point gtd Isblive YES e f Is 6 llve 3 Harry H Porter 2006 CS322 Target Generation Part 1 61 Liveness Example a b c At this point gtC1 e f Isblive YES Is 6 live N0 Is alive 3 Harry H Porter 2006 62 CS322 Target Generation Part 1 Liveness Example At this point Is b live YES Is 6 live N0 Is a live Don t Know Is g live 3 Harry H Porter 2006 CS322 Target Generation Part 1 63 Liveness Example At this point Is b live YES Is 6 live N0 Is g live Possibly Is a live Don t Know 3 Harry H Porter 2006 64 CS322 Target Generation Part 1 Liveness Example a if x lt y goto Must look at the whole control ow graph to determine liveness Is a live at the end of thls block b a 5 a 47 O O O O O O 3 Harry H Porter 20 06 CS322 Target Generation Part 1 Liveness Example 65 a 3 Harry H Porter 2006 if x lt y goto IS a a llve here Must look at the whole control ow graph to determine liveness Is a live at the end of this block IS a live here 66 CS322 Target Generation Part 1 Liveness Example Must look at the whole control ow graph to determine liveness a Is a live at the if x lt oto y g end of thls block 3 3 Is a a 4 Is a llve here llve here 0 O O O O O 3 Harry H Porter 2006 CS322 Target Generation Part 1 67 a Liveness Example Must look at the whole control ow graph to determine liveness Is a live at the f lt t l x y go o end of thls block IS a 4 a 3 a llve here hve here YE NO 0 3 Harry H Porter 20 06 68 CS322 Target Generation Part 1 Liveness Example M ust look at the whole control ow graph to determine liveness a ifxltygoto Is a live at the end of this block IS a a 4 a live here live here YES NO 3 Harry H Porter 2006 69 CS322 Target Generation Part 1 Live Variable Analysis A Rather Complex Algorithm Input The Control Flow Graph UseBi DefBi for all Bi Output LiveBi a list of all variables live at the end of Bi Live Variable Analysis missing Assume all variables are live at the end of each basic block 3 Harry H Porter 2006 70 CS322 Target Generation Part 1 Temporaries Assumption Each temporary is used in only one basic block True of temps for expression evaluation t5 xxxx xxxx XXXX Z Temps are never live at the end of a basic block I f LiveVariableAnalysis is missing t5 xxxx More precisely 0 temp will ever be in UseBl for any BB Conclusion this assumption can at least identify many dead variables 3 Harry H Porter 2006 CS322 Target Generation Part 1 71 Dead Code Dead Code first meaning Any code that cannot be reached Will never be executed x y 2 goto Label45 If a 1 b c I Dead Code unreachable l gfl Label 45 z I x a 3 Harry H Porter 2006 72 CS322 Target Generation Part 1 Dead Code Dead Code first meaning Any code that cannot be reached Will never be executed x y 2 goto Label45 quotI Dead Code unreachable Dead Code second meaning A statement which computes a dead variable Example b x y b clt If a is not live here Then eliminate this statement 3 Harry H Porter 2006 a CS322 Target Generation Part 1 Temporaries E you can identify a variable which is not in UseBi for any basic block eg a temporary used only in this basic block w you may 0 Rename the variable 0 Keep the variable in a register instead of in memory 0 Eliminate it entirely during some optimization Must be careful that the variable is not used in other routines ie accessed as a nonlocal from another routine 3 Harry H Porter 2006 CS322 Target Generation Part 1 Algebraic Transformations Watch for special cases Replace with equivalent instructions that execute with a lower cost Exalees x y 0 x 3 x y 1 gt x y x y 2 gt x y y x y 1 gt x incry x y 1 gt x decry etc May do some transformations during Peephole Optimization Other transformations may be Target Architecture Degendent use your cost model to determine when to transform 3 Harry H Porter 2006 CS322 Target Generation Part 1 Control Flow Graphs Definitions 0 Initial Block 0 Predecessor Blocks 0 Successor Blocks Predecessors Successors 3 Harry H Porter 2006 CS322 Target Generation Part 1 Representing Basic Blocks Ideas leader numberof I ns t o 2 2 C goto W 3 Harry H Porter 2006 CS322 Target Generation Part 1 Representing Basic Blocks Ideas successor instructions IR Instructions Brunch instructions now point to Basic Blocks not to IR instructions as before 3 Harry H Porter 2006 CS322 Target Generation Part 1 What is a LOOP A cycle in the ow graph Can go from B back to B A path from B to B All blocks on any path from B to B 3 Harry H Porter 2006 CS322 Target Generation Part 1 79 Note This loop has multiple entries 0 Very unnatural 0 Rare in assembly language programs 0 Impossible in many programming languages goto Lab45 while xlty Lab45 3 Harry H Porter 2006 80 CS322 Target Generation Part 1 Natural Loops Each loop has a unique entry its Header Block While To reach any block in the loop from outside the loop you must first go through the header block I ile Result from structured programming constructs 39 39 39 while for dountil if Concepts 39 39 loop nesting inner outer loops I a J Inner Loop 3 Harry H Porter 2006 8 1 CS322 Optimization Part 4 Loop Unrolling Source for i 1 Q 100 91 1 Ai Ai Bi endfor Transformed Code for i 1 Q 100 21 4 Ai Ai Bi Ai1 Ai1 Bi1 Ai2 Ai2 Bi2 Ai3 Ai3 Bi3 endfor 3 Harry H Porter 2006 CS322 Optimization Part 4 Loop Unrolling Source for i 1 Q 100 91 1 Ai Ai Bi endfor Transformed Code for i 1 Q 100 Q1 4 Ai Ai Bi Ai1 Ai1 Bi1 Ai2 Ai2 Bi2 Ai3 Ai3 Bi3 endfor m I The overhead of testing and branching is reduced I This optimization may enable other optimizations 3 Harry H Porter 2006 CS322 Optimization Part 4 Source f r i A i endfor for i Ai Ai1 Ai2 Ai3 endfor Transformed Code Loop Unrolling 1 Q 100 21 1 Ai Bi More opportunities for optimizations such as 1 Q 100 91 4 scheduling Ai Bi Ai1 Bi1 Ai2 Bi2 Ai3 Bi3 7 Benefits I The overhead of testing and branching is reduced I This optimization may enable other optimizations 3 Harry H Porter 2006 CS322 Optimization Part 4 Larger Basic Blocks are Good Source f r i A i m Transforme 1 i Ai Ai1 Ai2 Ai3 i i endwhile while i Ai i i endwhile Ai Bi Loop Unrolling 1 2 MAX Q1 1 Ai Bi Number of iterations is 1 Code while 13 lt MAX Q Ai Bi Ai1 Bi1 Ai2 Bi2 Ai3 Bi3 4 lt MAX Q Do 0 to 3 more Iterations 1 as necessary to nish 3 Harry H Porter 23 not known at compiletime 4 CS322 Optimization Part 4 LoopInvariant Computations An assignment x y 6 z is LoopInvariant if 0 It is in a loop and 0 All definitions of y and z that reach the statement are outside the loop We may be able to move the computation into the preheader Step 1 Detect the LoopInvariant Computations Step 2 See if it is okay to move the statement into the preheader 3 Harry H Porter 2006 CS322 Optimization Part 4 Example 3 Harry H Porter 23 CS322 Optimization Part 4 Preheader 3 Harry H Porter 2006 7 CS322 Optimization Part 4 Detecting LoopInvariant Computations Ingut Loop L a set of basic blocks UD Chain information On ut The set of loopinvariant statements Idea 0 Mark some of the statements as loopinvariant 0 This may allow us to mark even more statements as loopinvariant 0 Remember the order in which theses statements are marked 3 Harry H Porter 2006 8 CS322 Optimization Part 4 Detecting LoopInvariant Computations repeat until no new statements are marked Look at each statement in the loop If all its operands are unchanging then mark the statement as loop invariantquot An operand is unchanging if I It is a constant I It has all reaching definitions outside of the loop I It has exactly one reaching definition and that definition has already been marked loop invariantquot 1 Remember the order in which statements are marked loopinvariant 3 Harry H Porter 2006 CS322 Optimization Part 4 Moving LoopInvariant Computations Consider moving statement S x y 9 2 into the loop s preheader The statement must satisfy three conditions If it satisfies all conditions then it can be moved 3 Harry H Porter 23 10 CS322 Optimization Part 4 Condition 1 The block containing S must dominate all exits from the loop This is loopinvariant V U 3 Harry H Porter 2006 CS322 Optimization Part 4 11 Condition 1 The block containing S must dominate all exits from the loop 3 Harry H Porter 23 CS322 Optimization Part 4 Condition 2 There must be no other assignments to X in the loop This is loopinvariant 3 Harry H Porter 2006 1 3 CS322 Optimization Part 4 Condition 2 There must be no other assignments to X in the loop This is loopinvariant 3 Harry H Porter 2E6 CS322 Optimization Part 4 Condition 3 All uses of X in the loop must be reached by ONLY the loopinvariant assignment ISA 7 d This is 1 V loopinvariant 3 Harry H Porter 2006 1 5 CS322 Optimization Part 4 Condition 3 All uses of X in the loop must be reached by ONLY the loopinvariant assignment 3 Harry H Porter 23 CS322 Optimization Part 4 If all three conditions are satisfied move the statements into the preheader in the order they were marked LoopInvariant wzab x w1 y x5 3 Harry H Porter 2006 1 7 CS322 Optimization Part 4 If all three conditions are satisfied move the statements into the preheader in the order they were marked LoopInvariant wzab Marked LoopInvariant 3 Harry H Porter 23 CS322 Optimization Part 4 If all three conditions are satisfied move the statements into the preheader in the order they were marked LoopInvariant wzab N Now this becomes loopinvariant 3 Harry H Porter 2006 CS322 Optimization Part 4 19 If all three conditions are satisfied move the statements into the preheader in the order they were marked LoopInvariant Create a preheader 3 Harry H Porter 23 20 CS322 Optimization Part 4 If all three conditions are satisfied move the statements into the preheader in the order they were marked LoopInvariant Move this into preheader rst 3 Harry H Porter 2006 CS322 Optimization Part 4 21 If all three conditions are satisfied move the statements into the preheader in the order they were marked LoopInvariant ab Move this into preheader second 3 Harry H Porter 2E6 22 CS322 Code GenerationPart 2 Where to Store Variables S tatic Allocation Variables created at compile time Size and address known at compile time S tack Allocation Variables placed in activation records on a stack Variables are created destroyed in LIFO order H eup Allocation Size and address determined at run time Creation destruction of data occurs in any order 3 Harry H Porter 2006 CS322 Code GenerationPart 2 Static Allocation Earl Lan ua es ORTRAN Each variable is placed in memory static allocation Fortran had routines but No stack Recursion was not possible Values of a routine s variables are retained across invocations Initialization vs re initialization Each variable s size must be known at compile time Dynamic arrays 3 Harry H Porter 2006 CS322 Code GenerationPart 2 Stack Allocation Each variable is local to some routine Invoke a routine Allocate storage for its variables and initialize it R eturn Pop frame Variables are destroyed Consider one routine e2 quicksort Many activations many frames gt Many copies of each local variable Local variables Each invocation has its own set of variables The currently active invocation Its variables Will be in the frame on top of stack Every reference to a local variable Will access data in the top frame 3 Harry H Porter 2006 CS322 Code GenerationPart 2 References to a local variable in the currently active routine General Idea In the SPARC A A A A L r gt 1 SP gt W o 14 I o StackTop offsetx 1d fp4815 3 Harry H Porter 2006 CS322 Code GenerationPart 2 Laying Out the Frame Each local and temp van39able has a size C int 4 bytes double 8bytes Each local and temp valiable needs an offset f each procedure or block do offset 0 f each local and temp variable do assign this variable to current offset offset offset this variable s length endFor endFor 3 Harry H Porter 2006 CS322 Code GenerationPart 2 Laying Out the Frame Each local and temp van39able has a size C int 4 bytes double 8 bytes PCAT all van39ables 4bytes Each local and temp valiable needs an offset f Pr edure r b1 k d May start at some other value 4 offset 0 for each local and temp variable do assign this variable to current offset offset offset this variable s length 3 Harry H Porter 2006 CS322 Code GenerationPart 2 Laying Out the Frame Each local and temp variable has a size C int 4 bytes double 8bytes PCAT all valiables 4 bytes Each local and temp variable needs an offset f PINquot9513re r b1 k d May start at some other value 4 offset 0 f each local and temp variable do assign this variable to current offset offset offset this variable s length endFor endFor We ll use 4 We ll treat main body as just another routine It Will have a frame Global variables Treat identically to local variables for procedures 3 Harry H Porter 2006 CS322 Code GenerationPart 2 Exam le Variable S Offset w 4 0 x 8 4 y 4 1 2 z 1 1 6 a 8 1 7 b 1 2 5 C E E 34 34 Ignoring alignment issues 3 Harry H Porter 2006 CS322 Code GenerationPart 2 Example Variable Sii Offset Offset with Alignment W 4 0 0 x 8 4 8 y 4 1 2 1 6 a 8 1 7 2 4 C E E Q 34 34 4 8 3 Harry H Porter 20 06 9 CS322 Code GenerationPart 2 Example Variable S Offset Offset with Alignment W 4 0 0 x 8 4 8 y 4 1 2 1 6 z 1 1 6 2 0 a 8 1 7 2 4 b 1 2 5 32 C E E Q 34 34 4 8 Variable M Offset x 8 0 Re order a 8 8 Place variables with C 8 16 most restrictive alignment W 11 Y rst 2 1 32 b 1 2 34 34 3 Harry H Porter 2006 10 CS322 Code GenerationPart 2 PCAT Example Variable w Initial offset 4 Increment 4 3 Harry H Porter 2006 CS322 Code GenerationPart 2 The Stack of Activation Records An Abstract View STACK TOP Temp data elds Local data elds Machine Status To access a local 0r temp variable Static lmk stacktop offset One actwatwn record Return address Stack frame Returned value 3 Harry H Porter 2006 CS322 Code GenerationPart 2 The Dynamic Link When we retum we need to be able to go back to previous frame During a call 0 Save old StackTop Increment StackTop Allocate new frame 0 Store old StackTop in Dynamic Link field StackT During a return 0 Use the Dynamic Link to restore the old StackTop To access local variables StackTop offsetx a To access variables in our caller s frame W StackTop offsetnynamicunk offsetx 3811 to access nonlocal variables 9 What do we need from the caller s frame to be discussed later 0 Arguments 0 Place to store a returned result 3 Harry H Porter 2006 CS322 Code GenerationPart 2 SPARC Much of the Activation Record is cached in registers Dynamic Link Stored in registers sp fp R eturn Address fp Stored in registers i7 o7 hidden Arguments hidden register Some in registers iO iS h dd t Rest in caller s frame 1 en regls er R eturned Value 32bits in register i0 00 Machine Status 64 bytes Architecture dependent amp often not needed 3 Harry H Porter 2006 CS322 Code GenerationPart 2 The Calling Sequence 0 Compute argument values 0 Allocate new frame 0 Initialize it 0 Move arguments into the new frame optional 0 Save machine state optional 0 Save return address 0 Transfer control to new routine The Return Sequence 0 Compute and move return value optional 0 Pop stack delete the top frame 0 Resume execution in the caller s code Flexibility as to who caller callee does what calling sequence return sequence 3 Harry H Porter 2006 CS322 Code GenerationPart 2 15 Caller s Code foo X call f oo Calli W BBB BBB BBB AAA AAA AAA CCC DDD CCC Rel r11 Sequence CCC Callee s Code 3 Harry H Porter 2006 16 CS322 Code GenerationPart 2 Where do you draw the line between the caller s frame and the callee s frame Shared by caller and callee Callee must be responsible for part of the job since only it knows the size of its local area When compiling the caller The compiler does not have the callee s code Parms R eturned Value Links Machine Status Local Vars Parms R eturned Value Links Machine Status Local Vars Callee s Frame Caller s Frame 3 Harry H Porter 2006 CS322 Code GenerationPart 2 17 Where do Vou draw the line between the caller s frame and the callee s frame Shared by caller and callee Callee must be responsible for part of the job since only it knows the size of its local area When compiling the caller The compiler does not have the callee s code Parms R eturned Value Links Machine Status Local Vars Parms R eturned Value Links Machine Status Local Vars Callee s Frame Caller s Frame 3 Harry H Porter 2006 18 CS322 Code GenerationPart 2 Parameter Passing in SPARC A A Sp Callee awy fP v Arguments to bar 1 92 WW Caller at known offset in fp96 foo the caller s frame 39 39 2 O O O 3 Harry H Porter 2006 CS322 Code GenerationPart 2 19 Using a Stack for Expression Evaluation Source Code x y 2 2 Target Code push y push 2 push z mult add pop x 3 Harry H Porter 2006 20 CS322 Code GenerationPart 2 Source Code x y 2 2 Target Code TOP push 2 push z mult add P0P x push y M FP Using a Stack for Expression Evaluation Used for expression evaluation Frame with local variables 3 Harry H Porter 2006 CS322 Code GenerationPart 2 Calling Seguence Push args onto the stack Save FP FP TOP TOP 2 TOP FrameSize Return Seguence Move return value to Where arg 1 was Restore TOP FP Pop stack top into Using a Stack for Argument Evaluation and Parameter Passing FP 3 Harry H Porter 2006 21 Fan s Frame CS322 Code GenerationPart 2 Using a Stack for Argument Evaluation and Parameter Passing Calling Seguence Push args onto the stack Save PP FP TOP TOP 2 TOP FrameSize R eturn Seg uence Move return value to Where arg 1 was Restore TOP FP Pop stack top into TOP W 7 Arguments A W Fee s Frame FP 3 Harry H Porter 2006 CS322 Code GenerationPart 2 Using a Stack for Argument Evaluation and Parameter Passing Calling Seguence Push args onto the stack Save FP FP TOP TOP 2 TOP FrameSize TOP Return Seguence Move return value to Where arg 1 was Restore TOP FP FP Pop stack top into WW Bar s F 7 me Arguments A WW Fee s Frame 3 Harry H Porter 2006 CS322 Code GenerationPart 2 Using a Stack for Argument Evaluation and Parameter Passing Calling Seguence Push args onto the stack A Save PP FP TOP TOP 2 TOP FrameSize R eturn Seg uence Move return value to Where arg 1 was Restore TOP FP Pop stack top into TOP FP Foo s Frame 25 3 Harry H Porter 2006 CS322 Code GenerationPart 2 Foo s Frame 26 Using a Stack for Ar ument Evaluation and Parameter Passin A A Source Code x y 2 bar7i1 Target Code push y push 2 7 l Top gt 1 x Y z 15 mlt 1 add FP P0P x O 3 Harry H Porter 20 06 CS322 Code GenerationPart 2 Using a Stack for Ar ument Evaluation and Parameter Passin A A Source Code x y 2 bar7i1 Target Code h IP115 Y push 2 TOP P 30 x y z 15 1 FP o o Foo s Frame 3 Harry H Porter 2006 CS322 Code GenerationPart 2 27 Using a Stack for Ar ument Evaluation and Parameter Passin A A Source Code x y 2 bar7i1 Target Code TOP V 2 30 x Y z 15 1 FP o Foo s Frame 3 Harry H Porter 2006 28 CS322 Code GenerationPart 2 Using a Stack for Ar ument Evaluation and Parameter Passin A A Source Code x y 2 bar7i1 Target Code push y TOP P 7 2 30 x y z 1 FF 0 o Foo s Frame 3 Harry H Porter 2006 CS322 Code GenerationPart 2 29 Using a Stack for Ar ument Evaluation and Parameter Passin A A Source Code x y 2 bar7i1 Target Code push y TOP D 50 push 2 7 2 30 x Y z 15 1 FF 0 Foo s Frame 3 Harry H Porter 2006 30 CS322 Code GenerationPart 2 Using a Stack for Ar ument Evaluation and Parameter Passin A A Source Code x y 2 bar7i1 Target Code TOP gt 1 push y 50 push 2 7 2 30 x y z 1 FP o o Foo s Frame 3 Harry H Porter 2006 CS322 Code GenerationPart 2 31 Using a Stack for Ar ument Evaluation and Parameter Passin A A Source Code x y 2 bar7i1 Target Code push y TOP V 51 push 2 7 2 30 x Y z 15 1 FP o Foo s Frame 3 Harry H Porter 2006 32 CS322 Code GenerationPart 2 Waiting Bar s Frame Fan s Frame CS322 Code GenerationPart 2 Using a Stack for Ar ument Evaluation and Parameter Passin A A Source Code a x y 2 bar7i1 Target Code FP push y 51 push 2 7 2 30 x y z it pop x o O 3 Harry H Porter 20 06 33 Source Code Target Code push y push 2 x y 2 bar7i1 Using a Stack for Ar ument Evaluation and Parameter Passin A A TOP P 3 2 30 x Y z 15 1 FP O Result from Bar Fan s Frame 3 Harry H Porter 2006 34 CS322 Code GenerationPart 2 Foo s Frame Using a Stack for Ar ument Evaluation and Parameter Passin A A Source Code x y 2 bar7i1 Target Code push y push 2 TOP V 6 30 x y z 15 1 FP O O 3 Harry H Porter 20 06 CS322 Code GenerationPart 2 35 Foo s Frame Using a Stack for Ar ument Evaluation and Parameter Passin A A Source Code x y 2 bar7i1 Target Code push y push 2 TOP gt 36 x Y z 15 1 FP O 3 Harry H Porter 20 06 36 CS322 Code GenerationPart 2 Using a Stack for Ar ument Evaluation and Parameter Passin A A Source Code x y 2 bar7i1 Target Code push y push 2 TOP V x y z 15 1 FP gtP P x o Foo s Frame 37 3 Harry H Porter 2006 CS322 Code GenerationPart 2 VariableLength Local Variables Goal Allow a routine to have van39ablelength data ie dynamicallysized arrays as local data in frame 38 3 Harry H Porter 2006 CS322 Code GenerationPart 2 VariableLength Local Variables Goal Allow a routine to have variablelength data ie dynamicallysized arrays as local data in frame Option 1 Allocate the variable on the heap Work with pointers to the data PCAT Hide the pointers from the programmer Programmer codes a1 Compiler produces code like this a 4i Auto free the data when the routine returns 3 Harry H Porter 2006 39 CS322 Code GenerationPart 2 VariableLength Local Variables Goal Allow a routine to have variablelength data ie dynamicallysized arrays as local data in frame Option 1 Allocate the variable on the heap Work with pointers to the data PCAT Hide the pointers from the programmer Programmer codes ai Compiler produces code like this a 4i Auto free the data when the routine returns Option 2 Create the variable on the stack dynamically Effectively Enlarge the frame as necessary Still need to work with pointers 3 Harry H Porter 2006 40 CS322 Code GenerationPart 2 VariableLen th Local Variables A A We must have two p01nters Stack Top FP Local Van39ables at fixed offsets from FP Dynamically sized variables use hidden pointers TC All references to a and b a Foo s Will be indirect b Frame through hidden pointers I J I FP o o o 3 Harry H Porter 20 06 4 1 CS322 Code GenerationPart 2 VariableLen th Local Variables We must have two pointers Stack Top FP Local Van39ables at fixed offsets from FP Dynamically sized variables use hidden pointers All references to a and b Will be indirect through hidden pointers t IHU Su 3 Harry H Porter 2006 CS322 Code GenerationPart 2 procedure main int y procedure foo1 int x procedure foo2 x call foo3 y procedure foo3 int x x call fool call foo2 call fool call foo2 x call fool y Local NonLocal Variables 3 Harry H Porter 2006 CS322 Code GenerationPart 2 43 39 procedure main o int y procedure foo2 x call foo3 y procedure foo3 int x3 x call fool call foo2 call fool call foo2 x U J Local NonLocal Variables 3 Harry H Porter 2006 44 CS322 Code GenerationPart 2 Local NonLocal Variables NonLocal 1 level cal foo3 NonLocal 2 levels procedure foo3 int x3 Local 0 levels call fool call fooz call fool call fooz 3 Harry H Porter 2006 CS322 Code GenerationPart 2 Local NonLocal Variables x X1 fool fprocedure main 0 A A Ln y foo2 X3 foo3 c foo2 procedure foo3 gt int x3 x1 f 1 Local 0 levels X3 f003 call fool call fooz f002 Dynamic D Links call fool call fooz Xl f001 Static y mam l Links 3 Harry H Porter 2006 CS322 Code GenerationPart 2 Static Scoping Rules Lexical Scoping For nonlocal valiables Look in syntactically enclosing routine Look in next enclosing routine etc The norm for most languages K rocedure f oo2 3 Harry H Porter 2006 CS322 Code GenerationPart 2 47 Dynamic Scoping Rules For nonlocal valiables Search the calling stack at runtime to locate the light valiable A A Uncommon procedure bar begin x bar end procedure fool var x integer f 1 begin x call bar fool end X2 procedure foo2 var x integer begin call bar end 3 Harry H Porter 2006 48 CS322 Code GenerationPart 2 S ntax begln end Statement Blocks A f procedure foo is var xy endProcedure 3 Harry H Porter 2006 CS322 Code GenerationPart 2 Statement Blocks Blocks are entered and exited in nested order Idea Create a new frame for each block Push 0n stack 3 Harry H Porter 2006 CS322 Code GenerationPart 2 Statement Blocks Blocks are entered and exited in nested order Idea Create a new frame for each block Push on stack 1M No parameters No recursion All calls are inline gt Overhead amp Just put variables in frame of surrounding routine 3 Harry H Porter 2006 CS322 Code GenerationPart 2 Statement Blocks procedure foo is A A 20 Frame 16 z for foo 12 temp y 8 Y 4 x endProcedure 3 Harry H Porter 2006

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

#### "I made $350 in just two days after posting my first study guide."

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

#### "Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.