Register allocation

Control Flow Graph
CFG models flow of control in the program (procedure)
G = (N, E) as a directed graph
Node n ? N: basic blocks
• A basic block is a maximal sequence of stmts with a single entry point, single exit point, and no internal from branches
• For simplicity, we assume a unique entry node n0 and a unique exit node nf in later discussions
Edge e=(ni, nj) ? E: possible transfer of control block ni to block nj






Basic Blocks
A basic block is a maximal sequence of consecutive statements with a single entry point, a single exit point, and no internal
branches
• Basic unit in control flow analysis
• Local level of code optimizations
1. Redundancy elimination
2. Register-allocation






Identify Basic Blocks
Input: A sequence of intermediate code statements

1. Determine the leaders, the first statements of basic blocks
• The first statement in the sequence (entry point) is a leader
• Any statement that is the target of a branch (conditional or unconditional) is a leader
• Any statement immediately following a branch (conditional or unconditional) or a return is a leader

2. For each leader, its basic block is the leader and all statements up to, but not including, the next leader or the end of the program.

Control Flow Graph
CFG models flow of control in the program (procedure)
G = (N, E) as a directed graph
Node n ? N: basic blocks
• A basic block is a maximal sequence of stmts with a single entry point, single exit point, and no internal from branches
• For simplicity, we assume a unique entry node n0 and a unique exit node nf in later discussions
Edge e=(ni, nj) ? E: possible transfer of control block ni to block nj






Basic Blocks
A basic block is a maximal sequence of consecutive statements with a single entry point, a single exit point, and no internal
branches
• Basic unit in control flow analysis
• Local level of code optimizations
1. Redundancy elimination
2. Register-allocation






Identify Basic Blocks
Input: A sequence of intermediate code statements

1. Determine the leaders, the first statements of basic blocks
• The first statement in the sequence (entry point) is a leader
• Any statement that is the target of a branch (conditional or unconditional) is a leader
• Any statement immediately following a branch (conditional or unconditional) or a return is a leader

2. For each leader, its basic block is the leader and all statements up to, but not including, the next leader or the end of the program.

Control Flow Graph
CFG models flow of control in the program (procedure)
G = (N, E) as a directed graph
Node n ? N: basic blocks
• A basic block is a maximal sequence of stmts with a single entry point, single exit point, and no internal from branches
• For simplicity, we assume a unique entry node n0 and a unique exit node nf in later discussions
Edge e=(ni, nj) ? E: possible transfer of control block ni to block nj






Basic Blocks
A basic block is a maximal sequence of consecutive statements with a single entry point, a single exit point, and no internal
branches
• Basic unit in control flow analysis
• Local level of code optimizations
1. Redundancy elimination
2. Register-allocation






Identify Basic Blocks
Input: A sequence of intermediate code statements

1. Determine the leaders, the first statements of basic blocks
• The first statement in the sequence (entry point) is a leader
• Any statement that is the target of a branch (conditional or unconditional) is a leader
• Any statement immediately following a branch (conditional or unconditional) or a return is a leader

2. For each leader, its basic block is the leader and all statements up to, but not including, the next leader or the end of the program.

Control Flow Graph
CFG models flow of control in the program (procedure)
G = (N, E) as a directed graph
Node n ? N: basic blocks
• A basic block is a maximal sequence of stmts with a single entry point, single exit point, and no internal from branches
• For simplicity, we assume a unique entry node n0 and a unique exit node nf in later discussions
Edge e=(ni, nj) ? E: possible transfer of control block ni to block nj






Basic Blocks
A basic block is a maximal sequence of consecutive statements with a single entry point, a single exit point, and no internal
branches
• Basic unit in control flow analysis
• Local level of code optimizations
1. Redundancy elimination
2. Register-allocation






Identify Basic Blocks
Input: A sequence of intermediate code statements

1. Determine the leaders, the first statements of basic blocks
• The first statement in the sequence (entry point) is a leader
• Any statement that is the target of a branch (conditional or unconditional) is a leader
• Any statement immediately following a branch (conditional or unconditional) or a return is a leader

2. For each leader, its basic block is the leader and all statements up to, but not including, the next leader or the end of the program.

Control Flow Graph
CFG models flow of control in the program (procedure)
G = (N, E) as a directed graph
Node n ? N: basic blocks
• A basic block is a maximal sequence of stmts with a single entry point, single exit point, and no internal from branches
• For simplicity, we assume a unique entry node n0 and a unique exit node nf in later discussions
Edge e=(ni, nj) ? E: possible transfer of control block ni to block nj






Basic Blocks
A basic block is a maximal sequence of consecutive statements with a single entry point, a single exit point, and no internal
branches
• Basic unit in control flow analysis
• Local level of code optimizations
1. Redundancy elimination
2. Register-allocation






Identify Basic Blocks
Input: A sequence of intermediate code statements

1. Determine the leaders, the first statements of basic blocks
• The first statement in the sequence (entry point) is a leader
• Any statement that is the target of a branch (conditional or unconditional) is a leader
• Any statement immediately following a branch (conditional or unconditional) or a return is a leader

2. For each leader, its basic block is the leader and all statements up to, but not including, the next leader or the end of the program.

Control Flow Graph
CFG models flow of control in the program (procedure)
G = (N, E) as a directed graph
Node n ? N: basic blocks
• A basic block is a maximal sequence of stmts with a single entry point, single exit point, and no internal from branches
• For simplicity, we assume a unique entry node n0 and a unique exit node nf in later discussions
Edge e=(ni, nj) ? E: possible transfer of control block ni to block nj






Basic Blocks
A basic block is a maximal sequence of consecutive statements with a single entry point, a single exit point, and no internal
branches
• Basic unit in control flow analysis
• Local level of code optimizations
1. Redundancy elimination
2. Register-allocation






Identify Basic Blocks
Input: A sequence of intermediate code statements

1. Determine the leaders, the first statements of basic blocks
• The first statement in the sequence (entry point) is a leader
• Any statement that is the target of a branch (conditional or unconditional) is a leader
• Any statement immediately following a branch (conditional or unconditional) or a return is a leader

2. For each leader, its basic block is the leader and all statements up to, but not including, the next leader or the end of the program.

Control Flow Graph
CFG models flow of control in the program (procedure)
G = (N, E) as a directed graph
Node n ? N: basic blocks
• A basic block is a maximal sequence of stmts with a single entry point, single exit point, and no internal from branches
• For simplicity, we assume a unique entry node n0 and a unique exit node nf in later discussions
Edge e=(ni, nj) ? E: possible transfer of control block ni to block nj






Basic Blocks
A basic block is a maximal sequence of consecutive statements with a single entry point, a single exit point, and no internal
branches
• Basic unit in control flow analysis
• Local level of code optimizations
1. Redundancy elimination
2. Register-allocation






Identify Basic Blocks
Input: A sequence of intermediate code statements

1. Determine the leaders, the first statements of basic blocks
• The first statement in the sequence (entry point) is a leader
• Any statement that is the target of a branch (conditional or unconditional) is a leader
• Any statement immediately following a branch (conditional or unconditional) or a return is a leader

2. For each leader, its basic block is the leader and all statements up to, but not including, the next leader or the end of the program.
Control Flow Graph
CFG models flow of control in the program (procedure)
G = (N, E) as a directed graph
Node n ? N: basic blocks
• A basic block is a maximal sequence of stmts with a single entry point, single exit point, and no internal from branches
• For simplicity, we assume a unique entry node n0 and a unique exit node nf in later discussions
Edge e=(ni, nj) ? E: possible transfer of control block ni to block nj






Basic Blocks
A basic block is a maximal sequence of consecutive statements with a single entry point, a single exit point, and no internal
branches
• Basic unit in control flow analysis
• Local level of code optimizations
1. Redundancy elimination
2. Register-allocation






Identify Basic Blocks
Input: A sequence of intermediate code statements

1. Determine the leaders, the first statements of basic blocks
• The first statement in the sequence (entry point) is a leader
• Any statement that is the target of a branch (conditional or unconditional) is a leader
• Any statement immediately following a branch (conditional or unconditional) or a return is a leader

2. For each leader, its basic block is the leader and all statements up to, but not including, the next leader or the end of the program.

Control Flow Graph
CFG models flow of control in the program (procedure)
G = (N, E) as a directed graph
Node n ? N: basic blocks
• A basic block is a maximal sequence of stmts with a single entry point, single exit point, and no internal from branches
• For simplicity, we assume a unique entry node n0 and a unique exit node nf in later discussions
Edge e=(ni, nj) ? E: possible transfer of control block ni to block nj






Basic Blocks
A basic block is a maximal sequence of consecutive statements with a single entry point, a single exit point, and no internal
branches
• Basic unit in control flow analysis
• Local level of code optimizations
1. Redundancy elimination
2. Register-allocation






Identify Basic Blocks
Input: A sequence of intermediate code statements

1. Determine the leaders, the first statements of basic blocks
• The first statement in the sequence (entry point) is a leader
• Any statement that is the target of a branch (conditional or unconditional) is a leader
• Any statement immediately following a branch (conditional or unconditional) or a return is a leader

2. For each leader, its basic block is the leader and all statements up to, but not including, the next leader or the end of the program.

Control Flow Graph
CFG models flow of control in the program (procedure)
G = (N, E) as a directed graph
Node n ? N: basic blocks
• A basic block is a maximal sequence of stmts with a single entry point, single exit point, and no internal from branches
• For simplicity, we assume a unique entry node n0 and a unique exit node nf in later discussions
Edge e=(ni, nj) ? E: possible transfer of control block ni to block nj






Basic Blocks
A basic block is a maximal sequence of consecutive statements with a single entry point, a single exit point, and no internal
branches
• Basic unit in control flow analysis
• Local level of code optimizations
1. Redundancy elimination
2. Register-allocation






Identify Basic Blocks
Input: A sequence of intermediate code statements

1. Determine the leaders, the first statements of basic blocks
• The first statement in the sequence (entry point) is a leader
• Any statement that is the target of a branch (conditional or unconditional) is a leader
• Any statement immediately following a branch (conditional or unconditional) or a return is a leader

2. For each leader, its basic block is the leader and all statements up to, but not including, the next leader or the end of the program.

Control Flow Graph
CFG models flow of control in the program (procedure)
G = (N, E) as a directed graph
Node n ? N: basic blocks
• A basic block is a maximal sequence of stmts with a single entry point, single exit point, and no internal from branches
• For simplicity, we assume a unique entry node n0 and a unique exit node nf in later discussions
Edge e=(ni, nj) ? E: possible transfer of control block ni to block nj






Basic Blocks
A basic block is a maximal sequence of consecutive statements with a single entry point, a single exit point, and no internal
branches
• Basic unit in control flow analysis
• Local level of code optimizations
1. Redundancy elimination
2. Register-allocation






Identify Basic Blocks
Input: A sequence of intermediate code statements

1. Determine the leaders, the first statements of basic blocks
• The first statement in the sequence (entry point) is a leader
• Any statement that is the target of a branch (conditional or unconditional) is a leader
• Any statement immediately following a branch (conditional or unconditional) or a return is a leader

2. For each leader, its basic block is the leader and all statements up to, but not including, the next leader or the end of the program.

Control Flow Graph
CFG models flow of control in the program (procedure)
G = (N, E) as a directed graph
Node n ? N: basic blocks
• A basic block is a maximal sequence of stmts with a single entry point, single exit point, and no internal from branches
• For simplicity, we assume a unique entry node n0 and a unique exit node nf in later discussions
Edge e=(ni, nj) ? E: possible transfer of control block ni to block nj






Basic Blocks
A basic block is a maximal sequence of consecutive statements with a single entry point, a single exit point, and no internal
branches
• Basic unit in control flow analysis
• Local level of code optimizations
1. Redundancy elimination
2. Register-allocation






Identify Basic Blocks
Input: A sequence of intermediate code statements

1. Determine the leaders, the first statements of basic blocks
• The first statement in the sequence (entry point) is a leader
• Any statement that is the target of a branch (conditional or unconditional) is a leader
• Any statement immediately following a branch (conditional or unconditional) or a return is a leader

2. For each leader, its basic block is the leader and all statements up to, but not including, the next leader or the end of the program.

Control Flow Graph
CFG models flow of control in the program (procedure)
G = (N, E) as a directed graph
Node n ? N: basic blocks
• A basic block is a maximal sequence of stmts with a single entry point, single exit point, and no internal from branches
• For simplicity, we assume a unique entry node n0 and a unique exit node nf in later discussions
Edge e=(ni, nj) ? E: possible transfer of control block ni to block nj






Basic Blocks
A basic block is a maximal sequence of consecutive statements with a single entry point, a single exit point, and no internal
branches
• Basic unit in control flow analysis
• Local level of code optimizations
1. Redundancy elimination
2. Register-allocation






Identify Basic Blocks
Input: A sequence of intermediate code statements

1. Determine the leaders, the first statements of basic blocks
• The first statement in the sequence (entry point) is a leader
• Any statement that is the target of a branch (conditional or unconditional) is a leader
• Any statement immediately following a branch (conditional or unconditional) or a return is a leader

2. For each leader, its basic block is the leader and all statements up to, but not including, the next leader or the end of the program.

Control Flow Graph
CFG models flow of control in the program (procedure)
G = (N, E) as a directed graph
Node n ? N: basic blocks
• A basic block is a maximal sequence of stmts with a single entry point, single exit point, and no internal from branches
• For simplicity, we assume a unique entry node n0 and a unique exit node nf in later discussions
Edge e=(ni, nj) ? E: possible transfer of control block ni to block nj






Basic Blocks
A basic block is a maximal sequence of consecutive statements with a single entry point, a single exit point, and no internal
branches
• Basic unit in control flow analysis
• Local level of code optimizations
1. Redundancy elimination
2. Register-allocation






Identify Basic Blocks
Input: A sequence of intermediate code statements

1. Determine the leaders, the first statements of basic blocks
• The first statement in the sequence (entry point) is a leader
• Any statement that is the target of a branch (conditional or unconditional) is a leader
• Any statement immediately following a branch (conditional or unconditional) or a return is a leader

2. For each leader, its basic block is the leader and all statements up to, but not including, the next leader or the end of the program.

Control Flow Graph
CFG models flow of control in the program (procedure)
G = (N, E) as a directed graph
Node n ? N: basic blocks
• A basic block is a maximal sequence of stmts with a single entry point, single exit point, and no internal from branches
• For simplicity, we assume a unique entry node n0 and a unique exit node nf in later discussions
Edge e=(ni, nj) ? E: possible transfer of control block ni to block nj






Basic Blocks
A basic block is a maximal sequence of consecutive statements with a single entry point, a single exit point, and no internal
branches
• Basic unit in control flow analysis
• Local level of code optimizations
1. Redundancy elimination
2. Register-allocation






Identify Basic Blocks
Input: A sequence of intermediate code statements

1. Determine the leaders, the first statements of basic blocks
• The first statement in the sequence (entry point) is a leader
• Any statement that is the target of a branch (conditional or unconditional) is a leader
• Any statement immediately following a branch (conditional or unconditional) or a return is a leader

2. For each leader, its basic block is the leader and all statements up to, but not including, the next leader or the end of the program.

Control Flow Graph
CFG models flow of control in the program (procedure)
G = (N, E) as a directed graph
Node n ? N: basic blocks
• A basic block is a maximal sequence of stmts with a single entry point, single exit point, and no internal from branches
• For simplicity, we assume a unique entry node n0 and a unique exit node nf in later discussions
Edge e=(ni, nj) ? E: possible transfer of control block ni to block nj






Basic Blocks
A basic block is a maximal sequence of consecutive statements with a single entry point, a single exit point, and no internal
branches
• Basic unit in control flow analysis
• Local level of code optimizations
1. Redundancy elimination
2. Register-allocation






Identify Basic Blocks
Input: A sequence of intermediate code statements

1. Determine the leaders, the first statements of basic blocks
• The first statement in the sequence (entry point) is a leader
• Any statement that is the target of a branch (conditional or unconditional) is a leader
• Any statement immediately following a branch (conditional or unconditional) or a return is a leader

2. For each leader, its basic block is the leader and all statements up to, but not including, the next leader or the end of the program.

Control Flow Graph
CFG models flow of control in the program (procedure)
G = (N, E) as a directed graph
Node n ? N: basic blocks
• A basic block is a maximal sequence of stmts with a single entry point, single exit point, and no internal from branches
• For simplicity, we assume a unique entry node n0 and a unique exit node nf in later discussions
Edge e=(ni, nj) ? E: possible transfer of control block ni to block nj






Basic Blocks
A basic block is a maximal sequence of consecutive statements with a single entry point, a single exit point, and no internal
branches
• Basic unit in control flow analysis
• Local level of code optimizations
1. Redundancy elimination
2. Register-allocation






Identify Basic Blocks
Input: A sequence of intermediate code statements

1. Determine the leaders, the first statements of basic blocks
• The first statement in the sequence (entry point) is a leader
• Any statement that is the target of a branch (conditional or unconditional) is a leader
• Any statement immediately following a branch (conditional or unconditional) or a return is a leader

2. For each leader, its basic block is the leader and all statements up to, but not including, the next leader or the end of the program.

Control Flow Graph
CFG models flow of control in the program (procedure)
G = (N, E) as a directed graph
Node n ? N: basic blocks
• A basic block is a maximal sequence of stmts with a single entry point, single exit point, and no internal from branches
• For simplicity, we assume a unique entry node n0 and a unique exit node nf in later discussions
Edge e=(ni, nj) ? E: possible transfer of control block ni to block nj






Basic Blocks
A basic block is a maximal sequence of consecutive statements with a single entry point, a single exit point, and no internal
branches
• Basic unit in control flow analysis
• Local level of code optimizations
1. Redundancy elimination
2. Register-allocation






Identify Basic Blocks
Input: A sequence of intermediate code statements

1. Determine the leaders, the first statements of basic blocks
• The first statement in the sequence (entry point) is a leader
• Any statement that is the target of a branch (conditional or unconditional) is a leader
• Any statement immediately following a branch (conditional or unconditional) or a return is a leader

2. For each leader, its basic block is the leader and all statements up to, but not including, the next leader or the end of the program.

Control Flow Graph
CFG models flow of control in the program (procedure)
G = (N, E) as a directed graph
Node n ? N: basic blocks
• A basic block is a maximal sequence of stmts with a single entry point, single exit point, and no internal from branches
• For simplicity, we assume a unique entry node n0 and a unique exit node nf in later discussions
Edge e=(ni, nj) ? E: possible transfer of control block ni to block nj






Basic Blocks
A basic block is a maximal sequence of consecutive statements with a single entry point, a single exit point, and no internal
branches
• Basic unit in control flow analysis
• Local level of code optimizations
1. Redundancy elimination
2. Register-allocation






Identify Basic Blocks
Input: A sequence of intermediate code statements

1. Determine the leaders, the first statements of basic blocks
• The first statement in the sequence (entry point) is a leader
• Any statement that is the target of a branch (conditional or unconditional) is a leader
• Any statement immediately following a branch (conditional or unconditional) or a return is a leader

2. For each leader, its basic block is the leader and all statements up to, but not including, the next leader or the end of the program.

Control Flow Graph
CFG models flow of control in the program (procedure)
G = (N, E) as a directed graph
Node n ? N: basic blocks
• A basic block is a maximal sequence of stmts with a single entry point, single exit point, and no internal from branches
• For simplicity, we assume a unique entry node n0 and a unique exit node nf in later discussions
Edge e=(ni, nj) ? E: possible transfer of control block ni to block nj






Basic Blocks
A basic block is a maximal sequence of consecutive statements with a single entry point, a single exit point, and no internal
branches
• Basic unit in control flow analysis
• Local level of code optimizations
1. Redundancy elimination
2. Register-allocation






Identify Basic Blocks
Input: A sequence of intermediate code statements

1. Determine the leaders, the first statements of basic blocks
• The first statement in the sequence (entry point) is a leader
• Any statement that is the target of a branch (conditional or unconditional) is a leader
• Any statement immediately following a branch (conditional or unconditional) or a return is a leader

2. For each leader, its basic block is the leader and all statements up to, but not including, the next leader or the end of the program.

Control Flow Graph
CFG models flow of control in the program (procedure)
G = (N, E) as a directed graph
Node n ? N: basic blocks
• A basic block is a maximal sequence of stmts with a single entry point, single exit point, and no internal from branches
• For simplicity, we assume a unique entry node n0 and a unique exit node nf in later discussions
Edge e=(ni, nj) ? E: possible transfer of control block ni to block nj






Basic Blocks
A basic block is a maximal sequence of consecutive statements with a single entry point, a single exit point, and no internal
branches
• Basic unit in control flow analysis
• Local level of code optimizations
1. Redundancy elimination
2. Register-allocation






Identify Basic Blocks
Input: A sequence of intermediate code statements

1. Determine the leaders, the first statements of basic blocks
• The first statement in the sequence (entry point) is a leader
• Any statement that is the target of a branch (conditional or unconditional) is a leader
• Any statement immediately following a branch (conditional or unconditional) or a return is a leader

2. For each leader, its basic block is the leader and all statements up to, but not including, the next leader or the end of the program.