|
As most modern designs, Firm employs static single assignment form
(SSA) to represent scalar data flow. SSA encodes use->def information
compactly, and completely avoids anti- and output-dependencies. This
allows elegant and fast optimization algorithms, notably sparse
data flow analysis.
SSA cannot directly model arbitrary data flow through memory. Firm
casts memory access dependencies as data dependency between memory
states (stores). Stores can be treated (almost) like scalar values.
This integrates all the data flow in a simple, SSA based dependency
formalism.
Traditional IRs treat control and data flow separately. The control
flow graph (CFG) has basic blocks as nodes and possible control
transfers as edges. Basic blocks contain a sequence of operations,
specifying data flow in one way or another, for instance by defining
and using named variables. This two-tier structure is well suited for
traditional bit-vector data flow analysis. Modern sparse data flow
analysis calls for a different structure. Firm sticks to the CFG to
represent control transfers, but replaces the rest by control
dependence. If a Firm operator is semantically required to execute in
a node of the CFG, it is control dependent on that node. This
integrates data flow and control flow into a single dependence graph.
| 
