(8.4.1)--第08章-代码生成4-一个简单的代码生成器_en.pdf

Compilers TechniquesCode GenerationBefore collecting global information,code is generated temporarily in basic blocks.A Simple Code Generatorprod:=0prod:=0i:=1i:=1t t1 1:=4*i:=4*it t2 2:=at:=at1 1 t t3 3:=4*I:=4*It t4 4:=bt:=bt3 3 t t5 5:=t:=t2 2*t*t4 4t t6 6:=prod+t:=prod+t5 5prod:=tprod:=t6 6t t7 7:=i+1:=i+1i:=ti:=t7 7if i=20 if i=20 goto goto B B2 2B B1 1B B2 2Consider each statement of the basic blocks in turn to generate code for it.Basic considerations:Assume that each operator of the three-address statement has a corresponding target machine operator.Assume that the calculation results remain in the register as long as possible unless:.This register is to be used for other calculations,orAt the end of the basic block.So some information needs to be recorded during code generation.A Simple Code Generatore.g.a=b+c.If register Ri contains b,Rj contains c,and b no longer active after that ADD Rj,Ri are generated,and result a is in Ri.If Ri contains b,but c is in the memory unit,b is still no longer active.Generate ADD c,Ri,or generate.MOV c,Rj.ADD Rj,Ri.If the value of c is used later,the second code is more attractive.A Simple Code GeneratorIn the process of code generation,it is necessary to track the contents of the registers and the addresses of the names.e.g.b=aRegister description record what is currently stored in each register?At any point,each register holds the values of several(including zero)names.A Simple Code Generator/Before the statement,R0 holds the value of variable a./does not generate any instructions for this statement./After the statement,R0 holds the values of variables a and b.In the process of code generation,it is necessary to track the contents of the registers and the addresses of the names.Register description record what is currently stored in each register?Address description of name(variable)record where the current value of each name can be found at runtime.This place can be a register,stack unit,memory address,or even a set of them.For example,after generating MOV c,R0,the value of c can be found in the memory units of R0 and c.A Simple Code GeneratorIn the process of code generation,it is necessary to track the contents of the registers and the addresses of the names.The address information of the name is stored in the symbol table,and a register description table is built separately.These two descriptions change during code generation.A Simple Code GeneratorRegister description record what is currently stored in each register?Address description of name(variable)record where the current value of each name can be found at runtime.For each three-address statement x=y op zCall the function getreg to determine the place L where the y op z evaluation results will be placed.Look at the address description of y and determine the current place y with the y value.If the value of y is not yet in L,the instruction MOV y,L is generated.Generates the instruction op z,L,where z is one of the current places of z.If the current values of y and/or z are no longer referenced,are not active at the exit of the block,and are still in the register,then the register description is modified.A Simple Code GeneratorCode generation algorithmThe function getreg returns the place L where x=y op z is held.If the name y is in R,this R does not contain the value of other names,and y does not have the next reference after executing x=y op z,then this R is returned as L.Otherwise,if have,an idle register is returned.Otherwise,if x has the next reference in the block,or op is an operator that must use registers,then find an occupied register R(MOV R,M instructions may be generated,and the description of M may be modified).Otherwise,if X is no longer referenced in the basic block or the appropriate occupied register cannot be found,the memory unit of x is selected as L.A Simple Code GeneratorRegister select functionAssignment statement d=(a b)+(a c)+(a c)Compile to produce a three-address statement sequence:t1=a bt2=a ct3=t1+t2d=t3+t2 A Simple Code GeneratorStatemant Generated code Register descriptionaddress description of the nameEmpty register MOV R0,dd is in R0 and memoryd=t3+t2 ADD R1,R0 R0 contains dd is inR0t3=t1+t2 ADD R1,R0 R0 contains t3 R1 contains t2 t3 is in R0t2 is in R1 t2=a cMOV a,R1SUB c,R1R0 contains t1R1contains t2t1is in R0 t2 is in R1t1=a b MOV a,R0SUB b,R0 R0 contains t1 t1is in R0 Assignment statement:d=(a b)+(a c)+(a c)A Simple Code GeneratorThe first three instructions can be modified to reduce the execution costBefore modification After modificationMOV a,R0 MOV a,R0SUB b,R0 MOV R0,R1 MOV a,R1 SUB b,R0SUB c,R1 SUB c,R1A Simple Code GeneratorGenerate code for index and pointer statementsThe three address statements with index and pointer operations are treated the same as binary operatorsA Simple Code GeneratorThere are two ways to implement conditional transfer.Condition codes are used to indicate whether the calculated result or the value loaded into the register is negative,zero or positive.Branching depends on whether the register value is one of the following six conditions:negative,zero,positive,non-negative,non-zero,and non-positive.Conditional statementA Simple Code GeneratorBranching depends on whether the register value is one of the following six conditions:negative,zero,positive,non-negative,non-zero,and non-positive.e.g.if x y goto z The value of x minus y is stored in Register R.If the value of R is negative,it skips to z.1A Simple Code GeneratorIf the implementation of if x y goto z is:CMP x,y CJz 2.Examples of using conditional codesA Simple Code Generator|then the implementation of：|x=y+w|if x 0 goto z|is:|MOVy，R0|ADD w，R0|MOVR0，x|CJzCompilers TechniquesCode Generation