Code Shape II Expressions & ArraysCode ShapeSlide 3Generating Code for ExpressionsSlide 5Slide 6Slide 7Extending the Simple Treewalk AlgorithmSlide 9Handling Assignment (just another operator)Handling AssignmentSlide 12How does the compiler handle A[i,j] ?Laying Out ArraysComputing an Array AddressSlide 16Slide 17Optimizing Address Calculation for A[i,j]Array ReferencesSlide 20Example: Array Address Calculations in a LoopSlide 22Code Shape IIExpressions & ArraysCopyright 2003, Keith D. Cooper, Ken Kennedy & Linda Torczon, all rights reserved.Code Shape•What if x is 2 and z is 3?•What if y+z is evaluated earlier?The “best” shape for x+y+z depends on contextual knowledgeThere may be several conflicting optionsx + y + z x + y  t1t1+ z  t2x + z  t1t1+ y  t2y + z  t1t1+ z  t2zyxzyxyzxxzyAddition is commutative & associative for integersCode ShapeAnother example -- the case statement•Implement it as cascaded if-then-else statementsCost depends on where your case actually occursO(number of cases)•Implement it as a binary searchNeed a dense set of conditions to searchUniform (log n) cost•Implement it as a jump tableLookup address in a table & jump to itUniform (constant) costCompiler must choose best implementation strategyNo amount of massaging or transforming will convert one into anotherGenerating Code for ExpressionsThe key code quality issue is holding values in registers•When can a value be safely allocated to a register?When only 1 name can reference its valuePointers, parameters, aggregates & arrays all cause trouble•When should a value be allocated to a register?When it is both safe & profitableEncoding this knowledge into the IR•Use code shape to make it known to every later phase•Assign a virtual register to anything that can go into one•Load or store the others at each referenceRelies on a strong register allocatorGenerating Code for ExpressionsThe concept• Use a simple treewalk evaluator• Bury complexity in routines it calls> base(), offset(), & val()• Implements expected behavior> Visits & evaluates children> Emits code for the op itself> Returns register with result• Works for simple expressions• Easily extended to other operators• Does not handle control flowexpr(node) { int result, t1, t2; switch (type(node)) { case ,,, : t1 expr(left child(node)); t2 expr(right child(node)); result  NextRegister(); emit (op(node), t1, t2, result); break; case IDENTIFIER: t1 base(node); t2 offset(node); result  NextRegister(); emit (loadAO, t1, t2, result); break; case NUMBER: result  NextRegister(); emit (loadI, val(node), none, result); break; } return result; }Generating Code for ExpressionsExample:Produces:x yexpr(node) { int result, t1, t2; switch (type(node)) { case ,,, : t1 expr(left child(node)); t2 expr(right child(node)); result  NextRegister(); emit (op(node), t1, t2, result); break; case IDENTIFIER: t1 base(node); t2 offset(node); result  NextRegister(); emit (loadAO, t1, t2, result); break; case NUMBER: result  NextRegister(); emit (loadI, val(node), none, result); break; } return result; }Generating Code for ExpressionsExample:Generates:xy2expr(node) { int result, t1, t2; switch (type(node)) { case ,,, : t1 expr(left child(node)); t2 expr(right child(node)); result  NextRegister(); emit (op(node), t1, t2, result); break; case IDENTIFIER: t1 base(node); t2 offset(node); result  NextRegister(); emit (loadAO, t1, t2, result); break; case NUMBER: result  NextRegister(); emit (loadI, val(node), none, result); break; } return result; }Extending the Simple Treewalk AlgorithmMore complex cases for IDENTIFIER•What about values in registers? Modify the IDENTIFIER caseAlready in a register  return the register nameNot in a register  load it as before, but record the factChoose names to avoid creating false dependences•What about parameter values?Many linkages pass the first several values in registersCall-by-value  just a local variable with “funny” offsetCall-by-reference  needs an extra indirection•What about function calls in expressions?Generate the calling sequence & load the return valueSeverely limits compiler’s ability to reorder operationsExtending the Simple Treewalk AlgorithmAdding other operators•Evaluate the operands, then perform the operation•Complex operations may turn into library calls•Handle assignment as an operatorMixed-type expressions•Insert conversions as needed from conversion table•Most languages have symmetric & rational conversion tablesTypical Addition TableHandling Assignment (just another operator)lhs  rhsStrategy•Evaluate rhs to a value (an rvalue)•Evaluate lhs to a location (an lvalue)lvalue is a register  move rhslvalue is an address  store rhs•If rvalue & lvalue have different typesEvaluate rvalue to its “natural” typeConvert that value to the type of *lvalueUnambiguous scalars go into registersAmbiguous scalars or aggregates go into memoryLet hardware sort out the addresses !Handling AssignmentWhat if the compiler cannot determine the rhs’s type ?•This is a property of the language & the specific program•If type-safety is desired, compiler must insert a run-time check•Add a tag field to the data items to hold type informationCode for assignment becomes more complexevaluate rhsif type(lhs)  rhs.tag then convert rhs to type(lhs) or signal a run-time errorlhs  rhsThis is much more complex than if it knew the typesHandling AssignmentCompile-time type-checking•Goal is to eliminate both the check & the tag•Determine, at compile time, the type of each subexpression•Use compile-time types to determine if a run-time check is neededOptimization strategy•If compiler knows the type, move the check to compile-time•Unless tags are needed for garbage collection, eliminate them•If check is needed, try to overlap it with other computationCan design the language so all checks are