Code Optimization Techniques

Code Optimization and Generation

• Code optimization involves transformations to make code faster or use less space.
• Optimizing compilers perform these optimizations.
• Code optimization is optional and should not alter the program's meaning.

Need for Optimization

• Compiler-produced code might not be perfect regarding speed and space.
• Manual optimization is more time-consuming.
• Programmers might lack knowledge of machine-level details.
• Advanced architectures benefit from optimized code.
• Optimization improves code reusability and maintainability.

Criteria for Code Optimization

• Preserve program meaning without changing the output or causing errors; instead, improve efficiency
• Worth the effort; optimization benefits must justify the effort.

Optimization Locations

• Source code
• Intermediate code
• Target code

Types of Optimization

• Machine-dependent optimization runs on a specific machine.
• Machine-independent optimization can be used on any machine.

Optimization Phases

• Local optimization is applied to basic blocks, small code segments executed sequentially.
• Global optimization is applied to larger segments like loops.
• Local optimization should precede global optimization.

Basic Block

• A basic block is a sequence of consecutive three-address statements entered only at the beginning.
• Statements are executed in sequence without halts or branches.

Identifying Basic Blocks and Flow Graphs

• Leader statements need to be found to identify basic blocks.
• The first three-address instruction is a leader.
• Jump targets are leaders.
• Instructions following conditional or unconditional jumps are leaders.
• A basic block consists of a leader and subsequent instructions up to the next leader or the end of the program.
• Flow graphs are pictorial representations of control flow, showing relationships between basic blocks
• Nodes represent basic blocks, and edges represent control flow; G = (N, E) where N is basic blocks and E is control flows.
• B1 is the predecessor of B2, and B2 is the successor of B1 if the control transfers to the first statement of B2

Function-Preserving Transformations

• Compilers can improve programs without altering the function.
• Common subexpression elimination avoids re-computing expressions.
• Copy propagation replaces variables with their assigned values.
• Dead code elimination removes unused code.
• Constant folding evaluates constant expressions at compile time.

Common Subexpression Elimination (CSE)

• An expression E is a common sub-expression if it was previously computed and variables in E have not changed.
• Re-computing the expression can be avoided by using the previously computed value.

Copy Propagation

• Assignments of the form f = g are copy statements.
• Copy propagation uses g for f whenever possible after the copy statement.
• It involves using one variable instead of another.

Dead-Code Elimination

• A variable is live if its value is used subsequently.
• Otherwise, it's dead.
• Dead code includes statements that compute unused values.
• Dead code may result from previous transformations

Constant Folding

• Constant expressions are evaluated at compile time and the result replaces the original expression.
• Improves the run time performance.

Loop Optimization

• Loop performance can be improved by reducing the number of instructions in inner loops.
• Code motion decreases the amount of code in a loop.
• Loop-invariant code motion moves loop-invariant code outside the loop.
• Induction variables are variables whose values remain in lock-step; every time the one value decreases by one, the other decreases by 4, such an example is called induction variables

Reduction In Strength

• In loops with two or more induction variables, all but one can be potentially eliminated through induction-variable elimination.

Loop Jamming

• Merging or combining loops.

Loop Unrolling

• Replacing the loop with simple code, to reduce repetition and potentially be more efficient.

Optimization of Basic Blocks

• Structure-preserving transformations
• Algebraic transformations
• Structure preserving includes dead code elimination, copy propagation, common sub expression elimination, strength reduction, constant folding and interchange of independant statements
• Copy Propagation includes Variable Propagation and Constant Propagation,
• Strength Reduction: Replace expensive statement/ Instruction with cheaper ones
• Algebraic simplification includes reduction in strength

Directed Acyclic Graph (DAG)

• DAG is an abstract syntax tree with a unique node for each value.
• DAG is used for transformation on basic blocks.
• Constructed from three address code.
• Common subexpressions can be detected when adding a new node.

Applications of DAG

• Determine common subexpressions.
• Determine names used and computed outside the block.
• Simplify quadruples by eliminating common sub expressions and not doing unnecassary assignments

Rules for DAG Construction

• Leaf nodes represent identifiers, names, and constants.
• Interior nodes represent operators.
• A node is only created if one with the same children does not exist.

Machine Independent Optimization

• all discussed optimization is machine independant

Machine Dependent Optimization

• Machine dependent optimization is done on the target code.
• Peephole optimization is a simple technique for locally improving target code.
• Peephole optimization improves the performance of the target program by examining a short sequence of the instructions and replacing the instructions by a shorter, faster sequence.

Peephole Optimization Characteristics

• Redundant Load/Store
• Remove Unreachable Code
• Flow of Control Optimization
• Algebraic Simplifications
• Use of Machine Idioms

Unreachable Code

• Part of the program that is never accessed due to the programming constructs.

Flow of Control

• There are instances in a code where the program control jumps back and forth without performing any significant task.
• These jumps can be removed.

Algebraic Simplifications

• It represents another important class of optimizations on basic blocks
• Use Machine Idioms Some target instructions have equivalent machine instructions to perform some type of operations. Hence we can replace these target instructions with the corresponding machine instructions to improve the efficiency

Code Generation

• The final compiler phase is the code generator.
• It takes an intermediate representation of the source program and produces an equivalent target program.

Input to Code Generator

• Input consists of the intermediate representation and information in the symbol table.
• Intermediate language choices include postfix notation, three-address representation.

Target Programs

• The code generator's output can be absolute machine language, relocatable machine language, or assembly language.
• Absolute machine language can be placed in a memory with a fixed notation
• An assembly language program as output makes the process of code generation somewhat easier
• The target machine architecture affects code generation difficulty.
• The most common target machines are RISC, CISC, and stack based.
• RISC machines have many registers, three-address instructions, and simple instruction sets.
• CISC machines have few registers, two-address instructions, and varied addressing modes.
• Stack-based machines use the stack for operations.

Instruction Selection

• The complexity of this mapping is determined by the level of the IR, the nature of the instruction-set architecture, and the desired quality of the generated code
• Uniformity and completeness of the instruction is important factors
• If we do not core about the efficiency of the target program, instruction selection is straightforward

Moving the Source and Destination

• These locations can be registers and memory locations with address modes.

Simple Code Generator

• It uses registers to store operands of three-address statements.
• It uses descriptors to keep track of register contents and name addresses.
• A Register Descriptor keeps track of what is currently in each register and is consulting whenever a new register is needed.
• An Address Descriptor keeps track of the location where the current value of the name.

Code Generation Algorithm

• It takes a sequence of three-address statements as input.
• A function getreg is called to find the location for the result of y op z
• The instruction OP z', L is generated., where z' is the location of z.

Considerations for using Register

• If a variable Y is already in register R, it uses that register
• If some register R is available, it uses that register
• If above options are not possible, it chooses a register that requires minimal number of load and store instructions.