Question about a few properties of ideal graph

[Roland Westrelin]

> 1. Useless.  [1] defines an operation is useless if no operation uses its results, or if all uses of the results are dead (10.2)   
> Presumably,  a node is useless if it’s not useful.  Can I say identify_useful_nodes() is same as the definition above?
> https://github.com/openjdk/jdk/blob/master/src/hotspot/share/opto/compile.cpp#L302

I would say yes. In the ideal graph, nodes that have no use are useless
and can be removed. identify_useful_nodes() is applied after parsing to
remove nodes that have no use because parsing leaves some behind it.

> 2. Unreachable.  In my understanding, a node is unreachable if control flow never be there. I feel this definition only fits in CFG.  Is it still the same meaning in ideal graph? 
>
> According to the code here: https://github.com/openjdk/jdk/blob/master/src/hotspot/share/opto/node.cpp#L744, 
> it looks like a node is unreachable if 
> 1) no use or 
> 2) its type is TOP or
> 3) its control input node's is_top() is true.
>
> Is it complementary to Node::is_reachable_from_root()?  To be honest, I don't understand why finding the root from a node by following uses using BFS is same thing as the control flow can reach it from the root. 

I would say 1) is not unreachable. It can still be reachable but it is useless.
Not all nodes have a control input (AddNode for instance) so looking
only at control inputs can't be sufficient.

I would say, a node is unreachable if one of its required inputs is top
or NULL.

Region/Phi are special cases because they merge multiple control
flows. So if one of their inputs become top but all other inputs are
not, the Region/Phi is still reachable.

>  3. dead:  dead is everywhere in c2. I feel it could refer to different things in different places.
>     1. useless? e.g. Compile::_dead_node_list
> https://github.com/openjdk/jdk/blob/master/src/hotspot/share/opto/compile.cpp#L326
>     2. no direct use e.g. outcnt() == 0 is dead. 
> https://github.com/openjdk/jdk/blob/master/src/hotspot/share/opto/phaseX.hpp#L511
>     3. sometimes, I feel c2 removes a dead node because it's unreachable. 
>
> Is there a definition of dead node in c2?  Or dead/useless/unreachable are all same thing in ideal graph? 

Not sure if there's a consistent use of "dead" in the source base.

> 4. top.   What's semantic if a node's is_top() is true? Is it same thing as its type is TOP? 

Node::is_top() returns true for the unique top node (constant node that
has type TOP). I don't think you can say the type TOP and the node top
are the same thing. Let's say you have a AddNode with a top input. The
AddNode now has type TOP which at GVN would lead that AddNode to be
replaced by the top node.

> In type lattice, TOP is vague to me too. I feel that the type of a node is TOP has a slight different meaning for different nodes. If the node is a CFG node,  TOP seems to mean control flow can't reach to it. 
> If a value node whose type is TOP, I guess it means the value of this node is undefined.  I am correct here?

I don't think TOP has a different meaning for control nodes. One thing
about the ideal graph is that control flow is often treated as just
another dependence.

> 5. root node
> Can I say the root node of each compilation unit(CU) is the beginning and the end of that CU?  

I think so.

> So far, I feel the inputs of a root node are return values and side effect.  It that correct? 

Side effect is a bit vague, I guess. Return and other exits from the
method such as deoptimization. Maybe there are other edges added from
the root node, maybe temporarily, to keep some nodes from becoming
useless. Not sure.

> If I traverse uses of nodes from root, I should return to root eventually? if yes, it means ideal graph is a DAG.   

Yes, you should. But it's not a DAG anyway because there can be loops.

Roland.