Compiler Design: Difference between revisions

From dankwiki
Line 8: Line 8:
The directed  multigraph defined by interpreting basic blocks as vertices, and flow relationships as edges, yields its control flow graph (CFG). A start node exists for each CFG, corresponding to the basic block whose header is the first instruction of the program.
The directed  multigraph defined by interpreting basic blocks as vertices, and flow relationships as edges, yields its control flow graph (CFG). A start node exists for each CFG, corresponding to the basic block whose header is the first instruction of the program.
===Dominance===
===Dominance===
We induce the domination relation on vertices of a CFG, and thus basic blocks of the underlying program. A vertex a ''dominates'' b (a <= b) if every path from the start node s to b passes through a. A vertex a ''properly dominates'' b (a < b) if a dominates and is not equal to b. A vertex a ''directly/immediately dominates'' b (a <d b) if a properly dominates b, and a dominates no vertex c that dominates b.
We induce the reflexive domination relation on vertices of a CFG, and thus basic blocks of the underlying program. A vertex a ''dominates'' b (a <= b) if every path from the start node s to b passes through a. A vertex a ''properly dominates'' b (a < b) if a dominates and is not equal to b. A vertex a ''directly/immediately dominates'' b (a <d b) if a properly dominates b, and a dominates no vertex c that dominates b.
* It should be obvious that a's preceding of b in the CFG is not necessary for even immediate dominance of b by a.
* It should be obvious that a's preceding of b in the CFG is not necessary for even immediate dominance of b by a.

Revision as of 06:45, 9 March 2009

Control Flow

Control Flow Graph

The first instruction of the program is a leader, as is every target of a branch, and every instruction following a branch (including conditional branches and procedure returns) is a leader. A basic block is the largest sequence of instructions that can only be entered via the first (leader) instruction, and only exited by the last instruction (terminator, although this is not common terminology). A basic block a flows to b if and only if:

  • either b immediately follows a, and a does not end in an unconditional branch,
  • or a ends in a branch, of which b is a potential target.

Note that an indirect branch, without context information, trivializes all blocks (every instruction becomes a leader) and flows to them all from at least that point (an arborescence is formed)!

The directed multigraph defined by interpreting basic blocks as vertices, and flow relationships as edges, yields its control flow graph (CFG). A start node exists for each CFG, corresponding to the basic block whose header is the first instruction of the program.

Dominance

We induce the reflexive domination relation on vertices of a CFG, and thus basic blocks of the underlying program. A vertex a dominates b (a <= b) if every path from the start node s to b passes through a. A vertex a properly dominates b (a < b) if a dominates and is not equal to b. A vertex a directly/immediately dominates b (a <d b) if a properly dominates b, and a dominates no vertex c that dominates b.

  • It should be obvious that a's preceding of b in the CFG is not necessary for even immediate dominance of b by a.