C2 IR Graph and Nodes

Input edges

Node inputs (use-def edges) is an ordered collection. Every node has a control input that has index 0. The value of it can be null, in which case it is not dependent on any control. The control edge is typically referenced by its index node->in(0), however many nodes define a constant to refer to it symbolically as in node->in(NodeType::Control), where NodeType is a particular type of a node.

Here is an example of a method that adds two integers passed as parameters to a function (the following print out of the graph can be obtained by specifying -XX:+PrintIdeal command-line option):

class X {
    private static int foo1(int a, int b) {
        return a + b;
    }
}

11 Parm ===  3  [[ 23 ]] Parm1: int !jvms: X::foo1 @ bci:-1
10 Parm ===  3  [[ 23 ]] Parm0: int !jvms: X::foo1 @ bci:-1
3 Start ===  3  0  [[ 3  5  6  7  8  9  10  11 ]]  #{0:control, 1:abIO, 2:memory, 3:rawptr:BotPTR, 4:return_address, 5:int, 6:int}
23 AddI === _  10  11  [[ 24 ]]  !jvms: X::foo1 @ bci:2
9 Parm ===  3  [[ 24 ]] ReturnAdr !jvms: X::foo1 @ bci:-1
8 Parm ===  3  [[ 24 ]] FramePtr !jvms: X::foo1 @ bci:-1
7 Parm ===  3  [[ 24 ]] Memory  Memory: @BotPTR *+bot, idx=Bot; !jvms: X::foo1 @ bci:-1
6 Parm ===  3  [[ 24 ]] I_O !jvms: X::foo1 @ bci:-1
5 Parm ===  3  [[ 24 ]] Control !jvms: X::foo1 @ bci:-1
24 Return ===  5  6  7  8  9 returns 23  [[ 0 ]]
0 Root ===  0  24  [[ 0  1  3 ]] inner

Notice that AddI has the "_" placeholder, which means its control input is null. 

Nodes that access memory or otherwise depend of memory state express that dependency by having a memory state edge. It can encoded as edge with index 1 for subclasses of MemNode (Loads and Stores), or at index 2 for subclasses of the SafePointNode (which are all the calls and the safepoint). It is a good idea refer to the index symbolically - MemNode::Memory for MemNode subclasses and TypeFunc::Memory for SafePointNode subclasses. When traversing the memory graph one has to dispatch on the type of the node to get the correct index of the memory edge. Store nodes produce memory directly, Call nodes need projection nodes to extract their memory effect result.

 Some nodes (like calls) require dependency on the state that is different from memory, which is called an IO dependency (input with index 1 for SafePointNode subclasses) and can be refered to as NodeType::I_O, for example TypeFunc::I_O. The rest of the input edges depend on the type of node, in the example above AddI has two inputs for its left and right argument.

 Whatever the input edges are the rules of the IR evaluation require that dependencies (all inputs) be evaluated before the given node (in general the evaluation model requires a depth-first traversal over input edges starting from the Return node). The graph itself encodes the program in essentially a functional form composing pure operations with monadic operations (that depend on control, memory and i/o side effects).

Output edges

Node's outgoing edges (def-use edges) is an unordered collection linking the node to every other node that has input edges pointing to it. In the example graph above the output edges are listed in double square brackets. Typically the out edges are iterated over using the following idiom:

for (DUIterator i = x->outs(); x->has_out(i); i++) {
  Node* y = x->out(i);
  ...
}

or (which is faster but disallows insertion to the outs array, while iterating):

for (DUIterator_Fast imax, i = x->fast_outs(imax); i < imax; i++) {
  Node* y = x->fast_out(i);
  ...
}

Having def-use edges is essential to facilitate constant-time node replacement.

Projections

Result extraction from nodes producing multiple values is achieved by using projection nodes, which may be viewed as method to extract an element from the node returning a tuple. One of the important types of projections are control projections (subclasses of the CProjNode node): IfTrue and IfFalse that are used to split the control flow as a result of the If operation.

 Consider the example below:

class X {
    private static int foo1(int a, int b) {
        return a + b;
    }
    private static int foo2(int a, int b) {
        if (a < 0) {
            return foo1(a, b);
        }
        return 0;
    }
}

In the following subgraph of the foo2 the test of a < 0 is performed and the control flow is split using If and its projections:

Another example of projection nodes usage is extracting side effects and return values from Call nodes: 

public class X {
    private static int foo1(int a, int b) {
        return a + b;
    }
    private static int foo2(int a, int b) {
        return foo1(a, b);
    }
}

In this case node 28 selects the return value (an int), node 26 gets the memory effect, node 25 gets the i/o effect, node 24 is the exception edge.

Catch projections are used to select the exception handler.It is passed in the bci of the target handler (node 32, that transfers control to a rethrow), or no_handler_bci (node 31 in the example) in case the projection doesn't lead to an exception handler.

public class X {
    private static int foo3(int a, int b, int c) {
        if (a > b) {
            return a + c;
        } else {
            return a + b;
        }
    }
}

public class X {
    private int f1;
    private int f2;
    private void foo4(int a, int b) {
        f1 = a;
        f2 = b;
    }
}

29 StoreI ===  5  7  28  12  [[ 18 ]]  @X+16 *, name=f2, idx=5;  Memory: @X:NotNull+16 *, name=f2, idx=5; !jvms: X::foo4 @ bci:7
26 StoreI ===  5  7  25  11  [[ 18 ]]  @X+12 *, name=f1, idx=4;  Memory: @X:NotNull+12 *, name=f1, idx=4; !jvms: X::foo4 @ bci:2
7 Parm ===  3  [[ 18  29  26 ]] Memory  Memory: @BotPTR *+bot, idx=Bot; !jvms: X::foo4 @ bci:-1
18 MergeMem === _  1  7  1  26  29  [[ 32 ]]  { - N26:X+12 * N29:X+16 * }  Memory: @BotPTR *+bot, idx=Bot;
32 Return ===  5  6  18  8  9  [[ 0 ]]