全套电子课件：编译原理 第四套.ppt

过程声明的例子 procedure Q( x: real ); var u : real ; function f(k:real):real; begin f := k +k end; begin u := f(50); y:= u * x end； (EntryQ,LabelQ,SizeQ,LQ) (Entryf,Labelf,Sizef,Lf) (ADDF, k, k, t0) (ASSIG, t0,f) (ENDFUNC,……) (VALACT, 50,?1,1) (CALL, Labelf,true,t1) (ASSIG, t1, u) (MULTF, u,x, t2) (ASSIG, t2, y) (ENDPROC, ……) * * 过程/函数声明的语法制导 ProcFunDec → ProcDec | FunDec ProcDec → Procedure id (ParamList) Declaration #Entry ProgramBody #EndProc FunDec → Function id (ParamList): Type Declaration #Entry ProgramBody #EndFunc #Entry (1) 给子程序Q分配新标号LevelQ，并将它填到Q的符号表项中 (2) 产生入口中间代码 (ENTRY, LabelQ, SizeQ, LevelQ) #EndProc 和 #EndFunc 在遇到end时产生出口中间代码 (ENDPROC, _, _, _) 或 (ENDFUNC, _, _, _) * * 第八章 中间代码优化 引言 常量表达式优化 公共表达式优化 循环不变式外提 * * 优化的目标： 优化的要求： 优化的对象：深层循环和下标变量地址的计算 优化的种类： 常表达式优化（合并常数项） 公共表达式优化（消除重复操作） 循环不变表达式外提 削减运算强度等等 优化方法： 全局优化：全局信息 局部优化：局部信息 * * 基本块和程序流图 基本块：单入口单出口的程序段。 程序流图：以基本块为结点的有向图，有向边表示 程序执行的流程。 中间代码基本块的划分： ? 初始代码为第一个基本块的入口 ? 遇转移性中间代码时，结束当前基本块，下一条 代码作为新基本块的入口 ? 遇标号性代码结束当前基本块，代码本身作为新 基本块的入口。 ? 遇（ASSIG, A, X）时，如果X为引用型形参时结 束当前块，并作为该块的出口。 * * 基本块划分的例子 y := 1 ; L: if A and B then x := 0 else y := 0 ; x := x + 1 ; y := y – 1 ; while x + y 0 do x := x - 1 ; z := 0 ; * * 基本块划分的例子 B1:(ASSIG ,1,_,y) B2:(LABEL,L) (AND, A, B, t) (THEN,t,_,_) B3:(ASSIG,0,_,x) (ELSE,_,_,_) B4:(ASSIG,0,_,y) (ENDIF,_,_,_) B5:(ADDI,x,1,t1) (ASSIG,t1,_,x) (SUBI,y,1,t2) (ASSIG,t2,_,y) B1 B2 B4 B3 B5 B6 B8 B7 程序流图例 B6:(WHILE,_,_,) (ADDI,x,y,t3) (GT,t3,0,t4) (DO,t4,_,_) B7:(SUBI,x,1,t5) (ASSIG,t5,_,x) (ENDWHILE,_,_,_) B8:(ASSIG,0,_,z) * * 常表达式局部优化 常表达式：任何时候都取固定常数值的表达式 处理思想：针对每个基本块，如果一个多元式的两 个分量的值已知，则计算其值，并删掉 相应的中间代码。 原理：常量定值表ConsDef：(Var,Val)。 ? 基本块入口置ConstDef为空； ? 对当前多元式的分量利用ConstDef表进行值代换； ? 新多元式形如（?，A, B,t）:如果A和B是常数， 则计算A?B的值v，并将（t,v）填入ConsDef表。并 删除该多元式 ? 形如（ASSIG，A, B