SSA

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.



This page was dynamically generated by the web application development tool RADpage © 1996-2017 H.E.I. All Rights Reserved
 
Homepage
Products
    Web Development
    Compiler Tools
        BEG
        Firm Optimizer
            Intermediate Rep.
            SSA
            Optimizations
Consulting
Company
Impressum/Contact