Next: An overview of some basic Up: Introduction to three-address code optimization Previous: Introduction to three-address code optimization

## Code analysis.

OPTIMIZATIONS TO THREE-ADDRESS CODE (TAC) are portable to different back-ends. They rely on some simple concepts

• basic blocks
• control flow graphs

BASIC BLOCKS. A basic block is a TAC sequence where flow of control

• enters at the beginning and
• leaves at the end.
 L3: t5 := a * b t6 := t5 + c d := t2 * t2 if d = 0 goto L4

METHOD TO RECOGNIZE BASIC BLOCKS.

1. Statements that start a basic block are identified by searching for
• first statement of any function
• any labeled statement that is the target of a jump (conditional or unconditional)
• any statement following a jump (conditional or unconditional)
2. for each statement starting a basic block, the block consists of all statements up to (but excluding) the start of the next basic block or the end of the program.

MANIPULATING TAC IN A BASIC BLOCK

• implies that we need to worry only about effects caused to the values of variables
• at the start of a block and
• at its end
• is generally referred to as local optimization.

CONTROL FLOW GRAPH. Basic Blocks can be organized into a directed graph: the Control Flow Graph (CFG)

• whose nodes are the basic blocks and
• such that there is an edge that goes from basic block A to basic block B if it is possible for control to flow from A to B.
 i := 20 s := 20 L1: if i=0 goto L2 s := s + i i := i - 1 goto L1 L2:

LIVE VARIABLE ANALYSIS. We say that the TAC statement

x := y op z

• references y and z and
• defines x.
A name in a basic block B is said to be live after B if it is referenced further in the program after B, otherwise it is said to be dead in B.

Warning! In a basic block B, any piece of code of the form x := y op z where x is a variable dead in B is not necessarily a useless piece of code. Indeed x may be a temporary used to build a value propagated after B.

Algorithm 1 computes the dead names of a block B that are never referenced for computing the right values of a live variable. We will call such names useless.

Determining the life time and the use of variables in a program is called live variable analysis. We can say that a basic block computes a set of expressions: the values of variables that are live when we exit the block

Next: An overview of some basic Up: Introduction to three-address code optimization Previous: Introduction to three-address code optimization
Marc Moreno Maza
2004-12-02