Wednesday, February 02, 2005

Control Flow Graph

Building a Control-flow Graph from Scheduled Assembly Code

This paper presents an algorithm for building correct CFGs from scheduled assembly code that includes branches in branch delay slots. The algorithm works by building an approximate CFG
and then refining it to reflect the actions of delayed branches.

Excerpts from the paper that I think are important to understand the paper

-- The control flow graph (CFG) is a fundamental data structure needed by almost all the techniques that compilers use to find oppurtunities for optimization and to prove the safety of these
optimizations. Such analysis includes

global data flow analysis
construction of a SSA graph
data dependence analysis.

--Branches that target an address held in a register (as opposed to an immediate constant) introduce a level of uncertainty that produces spurious edges in the CFG.
Add an edge from the block containing the branch to every block that it might reach.

The compiler can narrow the set by finding all the labels that the program loads into registers. This is safe unless the program performs arithmetic on a label value and branches to the result.

For a more precise analysis : Call-graph construction with function-valued parameters. (Cross Reference this)

Base Algorithm:
The first step partitions the code into a set of basic blocks (single assembly instruction)
These become the nodes in the CFG. THe second step looks at the branches in the code and fills in
the CFG's edges to represent the flow of control.

To show the exploration algorithm can use the style presented in the page 4 of this paper.
Do we assume that branches only see target labels and not arbitary PC addresses???

No comments: