Question about a few properties of ideal graph

Liu, Xin xxinliu at amazon.com
Fri Oct 9 06:20:47 UTC 2020


Hi, Community, 

I feel the more I read C2's optimizations, the more questions arise.  I do have some previous experiences in conventional IRs, but it's a little bit hard to map them to c2. 
Could you help me to clarify some properties of the node and graph? I think they are critical to understand why some phases iterate the outputs of nodes(du-chain) and some phases iterate the inputs of nodes(ud-chain).

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

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. 

 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? 

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

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?

5. root node
Can I say the root node of each compilation unit(CU) is the beginning and the end of that CU?  
So far, I feel the inputs of a root node are return values and side effect.  It that correct? 
If I traverse uses of nodes from root, I should return to root eventually? if yes, it means ideal graph is a DAG.   

Thanks you in advance!

[1] Cooper, Keith, and Linda Torczon. Engineering a compiler. Elsevier, 2011.
 



More information about the hotspot-compiler-dev mailing list