FIRM 论文分析

[leozp]

FIRM—A Graph-Based Intermediate Representation

FIRM Node Types and Signatures

• The types TEDG are interpreted as follows:

  B basic block 
  X control flow 
  M memory
  P pointer
  I integer (32-bit)
  S integer (16-bit)
  B integer (8-bit)
  F floating point (32-bit)
  D floating point (64-bit) 
  E floating point (80-bit) 
  b boolean
  T tuple
  Num {P, I, S, B, F, D, E} 
  Any T EAG

FIRM construction optimizes

• Arithmetic Simplification (implicit)

  A node constructor is able to detect local simplifications, like x-x = 0, and returns a node, which represents the simplified expression.

• Common Subexpression Elimination (implicit)

  This optimization merges duplicate expressions. In FIRM this is also done implicitly during node creation. For example, before a new Const 1 node is created, the constructor checks if there is already a Const 1 in the graph and then returns this instead.

• Constant Folding (implicit)

  This optimization exchanges constant expressions for their resulting value, e.g. 23 is optimized to 6. Due to the mostly referentially transparent nature of operations, the 23 expression is easily detected in FIRM. FIRM performs this optimization during every node creation, so when a frontend calls the constructor for the Add node with the two Const operands a Const 6 is constructed internally and returned in- stead of an Add.

• Copy Propagation (inherent)

  This optimization removes unnecessary assignments, e.g. x = y. As FIRM has no local variables, there are no assignments between them either. A copy operation doesn’t even exist in the representation. If x is a global variable, then the FIRM graph represents access with a Store/Load operation. However, if x is local, then its users will just reference the defining of y directly.

• Dead Code Elimination (inherent)

  Since a FIRM node can only be accesses through its users an unused node is not seen, when walking the program graph. A garbage collection mechanism frees the memory occupied by dead code.

[leozp]

Definition

• Definition 1

  A program is in SSA-form iff each variable has exactly one definition.

• Definition 2 (explicit dependency graph)

  An explicit dependency graph (EDG) is a directed, marked graph. The nodes are marked with a signature of ΣEDG, which is their operation. The nodes have ordered in- and outputs. Their number and order correspond to the parameters and results of the respective term in ΣEDG. The in- and outputs are marked with types of TEDG. Edges connect outs with ins of the same type.

• Definition 3 (path convergence)

  Two non-null paths X0 →+ XJ and Y0 →+ YK are said to converge at a block Z iff the following conditions hold: X0 ̸=Y0; (1) XJ =Z=YK; (2) (Xj =Yk)⇒(j=J∨k=K). (3)

• Definition 4 (necessary φ-function).

  A φ-function for variable v is necessary in block Z iff two non-null paths X →+ Z and Y →+ Z converge at a block Z, such that the blocks X and Y contain assignments to v.

• Definition 5 (reducible flow graph)

  A (control) flow graph G is reducible iff for each cycle C of G there is a node of C which dominates all other nodes in C.

Keyword

• SSA

  Static Single Assignment form, where each variable is assigned exactly once.

• EDG

  explicit dependency graph

• Proj

  extract values from tuples

• φ-functions

  the insertion of special φ-functions at places where different assignments meet.

• Phi-Nodes

  Phi-nodes for example are an exception, because the behavior that all Phi-nodes must be evaluated simultaneously at beginning of a basic block is not represented with edges.

• CFG

  control flow graph

• Mature

  We use this knowledge to improve our construction algorithm: Blocks with known predecessors are called mature other blocks immature.

Reducing the Number of φ-Functions

• If we have to create additional φ-functions in a mature block, we will immediately calculate their arguments. Obviously the φ can be omitted if a mature block has exactly 1 predecessor.

• A second simplification called REMOVEUNNECESSARYPHI is applied when all arguments of a φ-function have been determined

Extraneous φ-Functions:

1. There might be φ-functions that no one references.
2. There might be φ-functions where all arguments effectively have the same value at runtime.
   • Pruned SSA-form

     only create φ-functions as a result of a situation where someone will use it

   • Minimal SSA-form

     φ-functions for a variable v only occur at basic blocks where different definitions of v meet for the first time.

[leozp]

FIRM Node Types

Add B × Num × Num → Num 
Alloc B × M × Num → M × P 
And B × Num × Num → Num 
ASM B × variable → variable 
Bad → Any
Block X0 × · · · × Xn →→ B
Call B×Num0 ×···×Numk ×M →Num0 ×···×Numk ×M 
Cmp B×Num×Num→b0 ×···×b15
Cond B×b→X×X
Const → Num
Conv B × Num → Num
Div B × Num × Num → Num
End B×X→
Eor B × Num × Num → Num
Free B → M × P × Num
Jmp B→X
Load B × P × M → Num × M
Minus B × Num → Num
Mod B × Num × Num → Num
Mul B × Num × Num → Num
Mux B×b×Num×Num→Num
NoMem →M
Not B × Num → Num
Or B × Num × Num → Num
Phi B×Num0 ×···×Numn →Num
Proj B×T →Num
Return B × M × N um0 × · · · × N umn → X
Rotl B×Num×Num→Num
Sel B×M×P→M×P
Shl B×Num×Num→Num
Shr B×Num×Num→Num
Shrs B×Num×Num→Num
Start B→X×M×P×P×T
Store B × M × P × Num → M
Sub B×Num×Num→Num
SymConst B×P
Sync B × M0 × · · · × Mn → M
Unknown → Any