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:

Figure 1: A control flow graph.

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