CSE 5317Lecture'14:'Instruc.on'selec.on'and'register'alloca.on11'Mar'2010Nate'NystromUniversity'of'Texas'at'ArlingtonSpigletSpiglet'is'simplified'Piglet2Piglet for expressionsRepresents'a'computa.on'that'returns'a'single'value3INT'iAn'integer'constant'iLABEL'nSymbolic'constant'n'(a'code'label)TEMP'iTemporary'i'(a'“register”)BIN'e1'e2Applica.on'of'a'binary'operator'to'integer'operandsHALLOCATE'eAllocate'e'bytes'on'the'heapCALL'f'e1'...'enProcedure'callESEQ's'eExpression'sequence;'evaluate's'for'side'effectsPiglet for statementsRepresents'a'computa.on'that'returns'no'value4MOVE'(TEMP't)'eEvaluate'e'and'put'result'in'a'temporary'tHLOAD'(TEMP't)'e1'(INT'i)Evaluate'e1'to'an'address'a,'load'*(a+i)'and'put'result'in'tHSTORE'e1'(INT'i)'e2Evaluate'e1'to'an'address'a,'store'e2'in'*(a+i)EXP'eEvaluate'e'and'discard'resultJUMP'(LABEL'n)Jump'to'code'address'nCJUMP'e1'(LABEL'n)Evaluate'e1,'jump'to'n'if'true;'otherwise'fall'throughBEGIN's1'...'sn'ENDEvaluate's1,'then's2,'...,'then'snLABEL'nDefine'a'constant'value'of'name'n'as'current'code'address.PRINT'eEvaluate'integer'e,'print'resultERRORReport'an'error'and'exitNOPDo'nothingSpiglet for expressionsDis.nguish'between'expressions'e'and'simple+expressions'p5pSimple'expressionBIN'(TEMP't1)'p2Applica.on'of'a'binary'operator'to'integer'operandsHALLOCATE'pAllocate'e'bytes'on'the'heapCALL'p'(TEMP't1)'...'(TEMP'tn)Procedure'callSpiglet for expressionsDis.nguish'between'expressions'e'and'simple+expressions'p6INT'iAn'integer'constant'iLABEL'nSymbolic'constant'n'(a'code'label)TEMP'iTemporary'i'(a'“register”)Spiglet for statementsRepresents'a'computa.on'that'returns'no'value7MOVE'(TEMP't)'eEvaluate'e'and'put'result'in'a'temporary'tHLOAD'(TEMP't1)'(TEMP't2)'(INT'i)Evaluate't2'to'an'address'a,'load'*(a+i)'and'put'result'in't1HSTORE'(TEMP't1)'(INT'i)'(TEMP't2)Evaluate't1'to'an'address'a,'store't2'in'*(a+i)JUMP'(LABEL'n)Jump'to'code'address'nCJUMP'(TEMP't)'(LABEL'n)Evaluate'e1,'jump'to'n'if'true;'otherwise'fall'throughBEGIN's1'...'sn'ENDEvaluate's1,'then's2,'...,'then'snLABEL'nDefine'a'constant'value'of'name'n'as'current'code'address.PRINT'pEvaluate'integer'e,'print'resultERRORReport'an'error'and'exitNOPDo'nothingNo'EXP'statementNo'ESEQ'expressionsNon`simple'expressions'can'occur'only'as'RHS 'of' MOVE8Generating SpigletSimple'version:Visit'each'expression,'building'a'list'of'MOVEs'to'TEMPs,'replacing'subexpressions'with'TEMPsE⟦'e'⟧'tevaluates'e,'storing'result'in'the'TEMP'tS⟦'e'⟧flabens'statement'e9E⟦'TEMP't1'⟧'t'=MOVE't'(TEMP't1)10E⟦'INT'n'⟧'t'=MOVE't'(INT'n)11Piglet to SpigletE⟦'PLUS'e1'e2'⟧'t'=BEGIN''''E⟦'e1'⟧'(TEMP't1)''''E⟦'e2'⟧'(TEMP't2)''''MOVE't'(PLUS'(TEMP't1)'(TEMP't2))ENDPass'down'temporary'in'which'to'write'the'result.12S⟦'HSTORE'a'i'b'⟧'t'=BEGIN''''E⟦'a'⟧'t1''''E⟦'b'⟧'t2''''HSTORE't1'i't2END13S⟦'HLOAD'a'b'i'⟧'t'=BEGIN''''E⟦'a'⟧'t1''''E⟦'n'⟧'t2''''HLOAD't1't2'iEND14S⟦'CALL'e0'e1'...'en'⟧'=E⟦'e0'⟧'t0E⟦'e1'⟧'t1...E⟦'en'⟧'tnCALL't0't1'...'tn15E⟦'BEGIN's1'...'sn'END'e'⟧'t'=BEGIN''''s1''''...''''sn''''E⟦'e'⟧'tEND16S⟦'MOVE'(TEMP't)'e'⟧'=''''E⟦'e'⟧'t17TilingAbove'transla.on'introduces'a'lot'of'temporariesCan'reduce'number'of'temporari es'by'!ling◾Tile'='fragment'of'IR'tree'(“tree'pabern”)◾Each'.le'is'translated'i nto'a'short'sequence'of'instruc.ons'that'put'result'of'the'expression'rooted'at'that'node'into'a'registerIdea'is'to'cover'IR'tree'in'disjo int'.les,'using'the'smallest'number'of'.les'possibleUsed'mainly'for'instruc.on'selec.on'(i.e.,'genera.ng'assembly'code'from'IR'trees)Can'also'be'used'for'Piglet'`>'Spiglet18Tile libraryTo'implement'.ling,'need'a'li brary'of'.lesTiny'.les'`` >'can'always'find'a'coveringLarge'.les'``>'produce'fewer'instruc.onsNeed'both'to'cover'all'cases19Tiling example20HLOAD'(TEMP't)'(PLUS'(TEMP'base)'(MUL'(PLUS'(INT'3)'(INT'1))'(INT'4)))PLUSTEMP'tHLOADINT'4INT'1INT'3PLUSMULTEMP'baseTiling example21HLOAD'(TEMP't)'(PLUS'(TEMP'base)'(MUL'(PLUS'(INT'3)'(INT'1))'(INT'4)))PLUSTEMP'tHLOADINT'4INT'1INT'3PLUSMULTEMP'baset1'='3'+'1t2'='t1'*'4t3'='base'+'t2t'='[t3]Tiling example22HLOAD'(TEMP't)'(PLUS'(TEMP'base)'(MUL'(PLUS'(INT'3)'(INT'1))'(INT'4)))PLUSTEMP'tHLOADINT'4INT'1INT'3PLUSMULTEMP'baset'='16[base]Maximal munch23Greedy'algorithm:Start'at'root,'and'use'largest'.le'possible'for'that'nodeWork'down'the'treeMaximal munchvisit(MOVE*m)*{****//*order*by*size*of*tile****//*recurse*on*descendants*not*included*in****//*the*tile****if*(m.dst*instanceof*PLUS*&&*******((PLUS)*m.dst).right*instanceof*INT)*{********m.dst.left.accept(this);********m.src.accept(this);********emit(“store”);****}*else*...****}*else*{********m.dst.accept(this);********m.src.accept(this);********emit(“store”);****}}24Dynamic programmingStart'at'leaves'and'work'upMemoize'cheapest'.le'at'each'rootAt'each'node,'choose'.le'whose'cost'plus'cost'of'.les'for'its'descendants'is'cheapest25Tiling effectivenessWorks'well'for'genera.ng'assembly'from'IR'treesWorks'beber'for'RISC'instruc.on'sets'than'CISCNot'as'effec.ve'for'Piglet'`>'Spiglet26Next stepsNext'steps'in'project:◾instruc.on'selec.on◾register'alloca.onInstruc.on'selec.on:◾map'IR'trees'to'assembly'instruc.onsRegister'alloca.on:◾replace'temporaries'with'references'to'registers◾if'not'enough'registers,'spill'to'the'stack27ProjectUsually,'do'instruc.on'selec.on'first'(with'pseudo`registers)Then,'do'register'alloca.onProject:◾do'register'alloca.on'on'Spiglet'(pro duci ng'Kanga),◾then'do'very'simple'instruc.on'selec.on28Register allocationNeed'to'have'values'in'register'before'useLimited'number'of'registers'(MIPS:'31,'x86:'8,'x86`64:'16)Register'alloca.on'changes'instruc.on'choicesCan'move'loads'and'storesOp.mal'alloca.on'is'NP`complete'for'>='1'register29Liveness analysisProblem:◾IR'has'unbounded'number'of'temporaries◾Target'machine'has'fixed'number'of'registersApproach:◾Temporaries'that'are'not'used'at'the'same'.me'can'map'to'the'same'register◾Not'used'at'the'same'.me'='disjoint'live'ranges◾If'not'enough'registers,'spill'to'memoryCompiler'does'liveness+analysis'for'each'temporary◾live'if'holds'a'value'that'may'be'needed'in'the'future30Control-flow analysisBefore'doing'liveness'analysis,'need'to'understand'control'flow'of'the'programBuild'control`flow'graph'(CFG)31Control-flow graphsint'max(int'x,'int'y)'{''''int'z;''''if'(x'>'y)''''''''z'='x;''''else''''''''z'='y;''''return'z;}32x'>'yz'='x z'='yreturn'zFor'now:'each'node'is'a'single'instruc.on.Live
View Full Document