Formula Sheets: Code Optimization | Compiler Design - Computer Science Engineering (CSE) PDF Download

 Page 1


Code Optimization F ormula Sheet
1. Basic Blocks and Flow Gr aphs
• Basic Block : Sequence of instructions with single entry and exit.
– Leader : First instruction, target of jump, or instruction following a jump.
– Construction : Group instructions from leader to next leader or jump.
• Flow Gr aph : Directed gr aph with basic blocks as nodes, edges for control flow .
• Time Complexity : O(n) for construction, wheren is number of instructions.
2. Function-Preserving Tr ansformations
• Definition : Optimizations preserving progr am semantics.
• Types :
– Common Subexpression Elimination (CSE) : Replacex = a +b;y = a +b
withx =a+b;y =x .
– Cop y Propagation : Replacex =y;z =x+1 withz =y +1 .
– Dead Code Elimination : Removex =a+b ifx is unused.
– Constant F olding : Evaluatex = 2+3 tox = 5 at compile time.
• Time Complexity : O(n) per block for local optimizations, O(n·|V|) for global
(data-flow analysis), where |V| is number of variables.
3. Peephole Optimization
• Definition : Local optimization over small code window (2-3 instructions).
• T echniques :
– Redundant Load/Store Elimination : Removex =y;y =x .
– Strength Reduction : Replacex =a*2 withx =a+a .
– Algebr aic Simplification : Simplifyx =x+0 tox =x .
– Flow Control Optimization : Replace goto L1; L1: goto L2 with goto
L2 .
• Time Complexity : O(w) per instruction, wherew is window size (constant).
4. Loop Optimizations
• Loop Identification : Find loops in flow gr aph (dominators, back edges).
– Back Edge : Edge from noden to ancestorm in depth-first spanning tree.
– Natur al Loop : Nodes reachable from back edge target to source.
1
Page 2


Code Optimization F ormula Sheet
1. Basic Blocks and Flow Gr aphs
• Basic Block : Sequence of instructions with single entry and exit.
– Leader : First instruction, target of jump, or instruction following a jump.
– Construction : Group instructions from leader to next leader or jump.
• Flow Gr aph : Directed gr aph with basic blocks as nodes, edges for control flow .
• Time Complexity : O(n) for construction, wheren is number of instructions.
2. Function-Preserving Tr ansformations
• Definition : Optimizations preserving progr am semantics.
• Types :
– Common Subexpression Elimination (CSE) : Replacex = a +b;y = a +b
withx =a+b;y =x .
– Cop y Propagation : Replacex =y;z =x+1 withz =y +1 .
– Dead Code Elimination : Removex =a+b ifx is unused.
– Constant F olding : Evaluatex = 2+3 tox = 5 at compile time.
• Time Complexity : O(n) per block for local optimizations, O(n·|V|) for global
(data-flow analysis), where |V| is number of variables.
3. Peephole Optimization
• Definition : Local optimization over small code window (2-3 instructions).
• T echniques :
– Redundant Load/Store Elimination : Removex =y;y =x .
– Strength Reduction : Replacex =a*2 withx =a+a .
– Algebr aic Simplification : Simplifyx =x+0 tox =x .
– Flow Control Optimization : Replace goto L1; L1: goto L2 with goto
L2 .
• Time Complexity : O(w) per instruction, wherew is window size (constant).
4. Loop Optimizations
• Loop Identification : Find loops in flow gr aph (dominators, back edges).
– Back Edge : Edge from noden to ancestorm in depth-first spanning tree.
– Natur al Loop : Nodes reachable from back edge target to source.
1
• T echniques :
– Loop Unrolling : Replace loop body with multiple copies, e.g., fori = 1 to
4 , unroll toa[1] = 0;a[2] = 0;a[3] = 0;a[4] = 0 .
– Loop Jamming (Fusion) : Combine loops with same bounds, e.g., merge
two loops overi = 1 ton into one.
– Induction V ariable Elimination : Replacei =i+1;x = 4*i withx =x+4 .
– Code Motion : Move invariant code, e.g., x = a +b outside loop if a,b un-
changed.
• Time Complexity : O(|E|+|V|) for loop identification, where |E|,|V| are edges
and nodes in flow gr aph.
5. Local Common Subexpression Elimination
• Definition : Eliminate redundant computations within a basic block.
• Algorithm :
– Tr ack expressions lik ea+b in a vailable expression set.
– Replacey =a+b withy =t ift =a+b computed earlier anda,b unchanged.
• Time Complexity : O(n) per block, wheren is number of instru ctions.
6. Global Data-Flow Analysis
• A vailable Expressions : Compute expressions computed on all paths to a point.
– IN[B] =
n
P? pred(B)
OUT[P] .
– OUT[B] = GEN[B]?( IN[B]- KILL[B]) .
• Live V ariables : Compute variables used after a point.
– OUT[B] =
?
S? succ(B)
IN[S] .
– IN[B] = USE[B]?( OUT[B]- DEF[B]) .
• Time Complexity : O(|V|
2
) for iter ative data-flow analysis, where |V| is number
of basic blocks.
7. Time Complexities
• Basic Block/Flow Gr aph Construction : O(n) .
• Peephole Optimization : O(1) per ins truction.
• Local CSE :O(n) per block.
• Loop Identification : O(|E|+|V|) .
• Global Data-Flow Analysis : O(|V|
2
) .
2
Page 3


Code Optimization F ormula Sheet
1. Basic Blocks and Flow Gr aphs
• Basic Block : Sequence of instructions with single entry and exit.
– Leader : First instruction, target of jump, or instruction following a jump.
– Construction : Group instructions from leader to next leader or jump.
• Flow Gr aph : Directed gr aph with basic blocks as nodes, edges for control flow .
• Time Complexity : O(n) for construction, wheren is number of instructions.
2. Function-Preserving Tr ansformations
• Definition : Optimizations preserving progr am semantics.
• Types :
– Common Subexpression Elimination (CSE) : Replacex = a +b;y = a +b
withx =a+b;y =x .
– Cop y Propagation : Replacex =y;z =x+1 withz =y +1 .
– Dead Code Elimination : Removex =a+b ifx is unused.
– Constant F olding : Evaluatex = 2+3 tox = 5 at compile time.
• Time Complexity : O(n) per block for local optimizations, O(n·|V|) for global
(data-flow analysis), where |V| is number of variables.
3. Peephole Optimization
• Definition : Local optimization over small code window (2-3 instructions).
• T echniques :
– Redundant Load/Store Elimination : Removex =y;y =x .
– Strength Reduction : Replacex =a*2 withx =a+a .
– Algebr aic Simplification : Simplifyx =x+0 tox =x .
– Flow Control Optimization : Replace goto L1; L1: goto L2 with goto
L2 .
• Time Complexity : O(w) per instruction, wherew is window size (constant).
4. Loop Optimizations
• Loop Identification : Find loops in flow gr aph (dominators, back edges).
– Back Edge : Edge from noden to ancestorm in depth-first spanning tree.
– Natur al Loop : Nodes reachable from back edge target to source.
1
• T echniques :
– Loop Unrolling : Replace loop body with multiple copies, e.g., fori = 1 to
4 , unroll toa[1] = 0;a[2] = 0;a[3] = 0;a[4] = 0 .
– Loop Jamming (Fusion) : Combine loops with same bounds, e.g., merge
two loops overi = 1 ton into one.
– Induction V ariable Elimination : Replacei =i+1;x = 4*i withx =x+4 .
– Code Motion : Move invariant code, e.g., x = a +b outside loop if a,b un-
changed.
• Time Complexity : O(|E|+|V|) for loop identification, where |E|,|V| are edges
and nodes in flow gr aph.
5. Local Common Subexpression Elimination
• Definition : Eliminate redundant computations within a basic block.
• Algorithm :
– Tr ack expressions lik ea+b in a vailable expression set.
– Replacey =a+b withy =t ift =a+b computed earlier anda,b unchanged.
• Time Complexity : O(n) per block, wheren is number of instru ctions.
6. Global Data-Flow Analysis
• A vailable Expressions : Compute expressions computed on all paths to a point.
– IN[B] =
n
P? pred(B)
OUT[P] .
– OUT[B] = GEN[B]?( IN[B]- KILL[B]) .
• Live V ariables : Compute variables used after a point.
– OUT[B] =
?
S? succ(B)
IN[S] .
– IN[B] = USE[B]?( OUT[B]- DEF[B]) .
• Time Complexity : O(|V|
2
) for iter ative data-flow analysis, where |V| is number
of basic blocks.
7. Time Complexities
• Basic Block/Flow Gr aph Construction : O(n) .
• Peephole Optimization : O(1) per ins truction.
• Local CSE :O(n) per block.
• Loop Identification : O(|E|+|V|) .
• Global Data-Flow Analysis : O(|V|
2
) .
2
• Loop Optimizations : O(n) per loop for unrolling, jamming, etc.
3