CSc 453Compilers and Systems Software22 : OptimizationDepartment of Computer ScienceUniversity of [email protected]° 2009 Christian CollbergIntroductionCompiler PhaseserrorsASTasmSemanticAnalyserInterm.Code GenIRMachineCode GenIRASTLexertokenssourceParserOptimizeOr maybe here!Or how about here?We are here!errorserrorsASTTransformation 1Transformation 2....Inter−Proc. OptTransformation 1Transformation 2....Local OptTransformation 1Transformation 2....Global OptSyntactic AnalysisLexical AnalysisSemantic AnalysisSOURCEBuild CallGraphgen[S]={..}kill[S1]={..}...Data FlowAnalysisMachine Code Gen.Peephole Opt.B5Interm. Code Gen.TransformationsTreeControl Flow AnalysisIntermediate Code OptimizationASTWhat do we Optimize?What do we Optimize?1Optimize everything, all the time. The problem is thatoptimization interferes with debugging. In fact, many (most)compilers don’t let you generate an optimized program withdebugging information. The problem of debugging optimizedcode is an important research field.Furthermore, optimization is probably the most timeconsuming pass in the compiler. Always optimizing everything(even routines which will never be called!) wastes valuabletime.2The programmer decides what to optimize. The problem isthat the programmer has a local view of the code. Whentiming a program programmers are often very surprised to seewhere most of the time is spent.3Turn optimization on when program is complete.Unfortunately, optimizers aren’t perfect, and a program thatperformed OK with debugging turned on often behavesdifferently when debugging is off and optimization is on.4Optimize inner loops only. Unfortunately, procedure calls canhide inner loops:PROCEDURE P(n);BEGINFOR k:=1 TO n DO · · · END;END P;FOR i:=1 TO 10000 DO P(i) END;5Use profiling information to guide what to optimize.dataCompiler Front−EndOptimizerCodeGenerator"Carefullychosen input"ExecutableProgramProfile6Runtime code generation/optimization. We delay codegeneration and optimization until execution time. At thattime we have more information to guide the otpimizations:Specialized CodeFront−EndQ [...]P [...]Interm.Code TableCompiledCode TableQ [...]P(_,3) [...]P [...]Interm.CodeGen spec. codefor P(_,3), optimize, thencallExecution timecall P(x,3)CompilerLocal vs. Global vs.Inter-procedural OptimizationLocal, Global, Inter-Proc.Some compilers optimize more aggressively than others. Anaggressive compiler optimizes over a large piece of code, asimple one only considers a small chunk of code at a time.Local Optimization:Consider each basic block by itself. (Allcompilers.)Global Optimization:Consider each procedure by itself. (Mostcompilers.)Inter-Procedural Optimization:Consider the control flow between procedures.(A few compilers do this.)Local Optimization — TransformationsLocal common subexpression elimination.Local copy propagation.Local dead-code elimination.Algebraic optimization.Jump-to-jump removal.Reduction in strength.Peephole OptimizationCan be done at the machine code level or at the intermediatecode level.1Examine a “window” of instructions.2Improve code in window.3Slide window.4Repeat until “optimal”.Local OptimizationPeephole optimization—Redundant LoadsA naive code generator will generate the same address orvariable several times.A := A + 1; ⇒ set A, %l0set A, %l1ld [%l1], %l1add %l1, 1, %l1st %l1, [%l0]⇓set A, %l0ld [%l0], %l1add %l1, 1, %l1st %l1, [%l0]Peephole optimization—Jumps-to-jumpsComplicated boolean expressions (with many and, or,nots) can easily produce lots of jumps to jumps.if a < b goto L1...L1: goto L2...L2: goto L3⇒ if a < b goto L3...L1: goto L3...L2: goto L3Algebraic SimplificationBeware of numerical problems:(x ∗ 0.00000001) ∗ 10000000000.0may produce a different result than(x ∗ 1000.0)!FORTRAN requires that parenthesis be honored:(5.0 ∗ x) ∗ (6.0 ∗ y) can’t be evaluated as (30.0 ∗ x ∗ y).Note that multiplication is often faster than division.Algebraic Simplification. . .x := x + 0; ⇒x := x - 0; ⇒x := x ∗ 1; ⇒x := 1 ∗ 1; ⇒ x := 1x := x / 1; ⇒x := x ** 2; ⇒ x := x * x;f := f / 2.0; ⇒ f := f ∗ 0.5;Reduction in StrengthSHL(x,y) = shift x left y steps.Multiplications (and divisions) by constants can be replacedby cheaper sequences of shifts and adds.x := x ∗ 32 ⇒ x := SHL(x, 5);x := x ∗ 100⇓x := x ∗ (64 + 32 + 4)⇓x := x ∗ 64 + x ∗32 + x ∗4⇓x := SHL(x,6) + SHL(x,5) + SHL(x,2)Local, Global,Inter-ProceduralOriginal CodeFUNCTION P (X,n): INT;IF n = 3 THEN RETURN X[1]ELSE RETURN X[n];CONST R = 1;BEGINK := 3; ...IF P(X,K) = X[1] THENX[1] := R * (X[1] ** 2)FUNCTION P (X,n): INT;IF n=3 THEN RETURN X[1] ELSE RETURN X[n];CONST R = 1;BEGINK := 3; ...IF P(X,K) = X[1] THEN X[1] := R * (X[1] ** 2)After Local OptimizationFUNCTION P (X,n): INT;IF n=3 THEN RETURN X[1] ELSE RETURN X[n]BEGINK := 3; ...IF P(X,K) = X[1] THEN X[1] := X[1] * X[1]FUNCTION P (X,n): INT;IF n=3 THEN RETURN X[1] ELSE RETURN X[n]BEGINK := 3;...IF P(X,K) = X[1] THEN X[1] := X[1] * X[1]After Global OptimizationFUNCTION P (X,n): INT;IF n=3 THEN RETURN X[1] ELSE RETURN X[n]BEGIN...IF P(X,3) = X[1] THEN X[1] := X[1] * X[1]FUNCTION P (X,n): INT;IF n=3 THEN RETURN X[1] ELSE RETURN X[n]BEGINIF P(X,3) = X[1] THEN X[1] := X[1] * X[1]After Inter-Procedural OptBEGINIF TRUE THEN X[1] := X[1] * X[1]After Another Local OptBEGINX[1] := X[1] * X[1]Delete P if it isn’t used elsewhere. This can maybe bededuced by an inter-procedural analysis.Global OptimizationGlobal OptimizationMakes use of control-flow and data-flow analysis.Dead code elimination.Common subexpression elimination (local and global).Loop unrolling.Code hoisting.Induction variables.Reduction in strenght.Copy propagation.Live variable analysis.Uninitialized Variable Analysis.Control Flow GraphsPerform optimizations over the control flow graph of a procedure.Basic Blockif ... goto B2B2if ... goto B3B3B5B6goto B2if ... goto B6B4B1Common Sub−ExpressionEliminationB5t9 := 4 * jx := A[t9] x := A[t3]B2B3B4t3 := 4 * jt5 := j * 4A[t5] := 20t3 := 4 * jA[t3] := 20No changes to j here!B1Copy Propagationx := t3A[t4] := t3A[t4] := t3B5B3B4x := t3A[t4] := xA[x] := 20 A[t3] := 20No more uses of x!No changes to x!Many optimizations produce X := Y .After an assignment X := Y , replace references to X by Y .Remove the assignment if possible.Dead CodeEliminationB5B2B3B4if x>20 goto B4t1 := 4 * jA[t3] := 20No changes to x here!Nor here!x := 23B1A piece of code is dead if we can determine at