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