P5
Context:
Recently, I have been working on a bug that triggers domination asserts. I get a broken Mach graph, but the bug is most likely in the IR from previous phases.
Scenario:
I have both a Mach graph (new nodes) and the old IR graph (old nodes). This means I might have a node with idx 302 for each of those graphs. These two nodes are not really related, they are located at very different locations in the respective graphs.
Problem:
I want to find node 302 in the new graph (or the old graph).
I tried these calls in rr (gdb would be equivalent):
(rr) p find_node(302)->dump()
find: 0x00007f6de85a1dc8 and 0x00007f6de8635480 both have idx==302
o302 If === o253 o269 o270 [[o312 o318 ]] P=0.900000, C=-1.000000
$18 = void
(rr) p find_node(305)->dump()
find: 0x00007f6de8635628 and 0x00007f6de85a22a8 both have idx==305
305 Region === 305 56 [[ 305 304 ]]
$19 = void
(rr) p find_node(305)
find: 0x00007f6de8635628 and 0x00007f6de85a22a8 both have idx==305
$20 = (Node *) 0x7f6de85a22a8
(rr) p find_node(302)
find: 0x00007f6de85a1dc8 and 0x00007f6de8635480 both have idx==302
$21 = (Node *) 0x7f6de8635480
As you can see, for both idx 302 and 305, we have a node per old and new graph. find_node(int) finds both (see print statements), but sometimes returns the node from the old graph, sometimes from the new graph. This unreliable behaviour is really annoying for me when debugging.
Analysis:
find_node(idx) redirects to
Compile::current()->root()->find(idx)
Node::find(idx) starts at the this node and does BFS through the graph, over input and output edges. If it finds a node with idx, it caches it. At the end, it returns the last node it found. If it finds a second node with idx, it prints a warning, and caches only the later one.
However, if ASSERT is defined, we also traverse n->debug_orig(). debug_orig about the "original version" of this node (e.g. before cloning, or from last phase). Traversing these "orig edges" means we will traverse from the new graph to the old graph, and often find two nodes with the same idx, returning the last visited node with idx. Depending on the new and old graph, sometimes this is a node from the old or the new graph.
I believe this is not the desired behavior. If we start the search at the new root Compile::current()->root() we want to find only nodes in the new graph. If we want to find old nodes, we can start at the old root. If one wants to find the old node, given a new Mach node:
Compile::current()->matcher()->find_old_node(new_node);
Solution 1:
We remove traversing debug_orig from Node::find, so that we cannot traverse from new to old graph.
I wonder if traversing debug_orig has a legitimate use case?
Is there ever a case where a node is only reachable through debug_orig, and not through input/output edges?
If not, this is the best solution, since we get rid of code rather than adding new code that we need to maintain.
Solution 2:
We keep traversing debug_orig "edges", but only if both nodes are of the same graph (either both new, or both old).
Solution 3:
We always traverse debug_orig. But when we find a second node with idx, then we cache the one that is in the same graph as the BFS root node. If there is only a node with idx in the old graph, we would still report it, even if we start with the new root.
Usages of find_node and Node::find(idx):
find_node is only defined in node.cpp, and in no header file. It is only used in the debugger.
Node::find is used in find_node, and find_ctrl (both debgging only). Further, Node::find is used in PhaseIdealLoop::dump (as far as I understand, we only want to find new nodes here, reporting an old one would probably lead to problems). An other use is in IdealLoopTree::verify_tree (we verify if a node is dead by finding it via its idx. Reporting another, old node would be bad here).
As far as I can see, reporting nodes from another graph is never required, but rather potentially problematic.
Conclusion:
It seems find_node and Node::find are giving unreliable results. That should be fixed. Which solution would you take? Do you have any other solutions or objections in mind?
Recently, I have been working on a bug that triggers domination asserts. I get a broken Mach graph, but the bug is most likely in the IR from previous phases.
Scenario:
I have both a Mach graph (new nodes) and the old IR graph (old nodes). This means I might have a node with idx 302 for each of those graphs. These two nodes are not really related, they are located at very different locations in the respective graphs.
Problem:
I want to find node 302 in the new graph (or the old graph).
I tried these calls in rr (gdb would be equivalent):
(rr) p find_node(302)->dump()
find: 0x00007f6de85a1dc8 and 0x00007f6de8635480 both have idx==302
o302 If === o253 o269 o270 [[o312 o318 ]] P=0.900000, C=-1.000000
$18 = void
(rr) p find_node(305)->dump()
find: 0x00007f6de8635628 and 0x00007f6de85a22a8 both have idx==305
305 Region === 305 56 [[ 305 304 ]]
$19 = void
(rr) p find_node(305)
find: 0x00007f6de8635628 and 0x00007f6de85a22a8 both have idx==305
$20 = (Node *) 0x7f6de85a22a8
(rr) p find_node(302)
find: 0x00007f6de85a1dc8 and 0x00007f6de8635480 both have idx==302
$21 = (Node *) 0x7f6de8635480
As you can see, for both idx 302 and 305, we have a node per old and new graph. find_node(int) finds both (see print statements), but sometimes returns the node from the old graph, sometimes from the new graph. This unreliable behaviour is really annoying for me when debugging.
Analysis:
find_node(idx) redirects to
Compile::current()->root()->find(idx)
Node::find(idx) starts at the this node and does BFS through the graph, over input and output edges. If it finds a node with idx, it caches it. At the end, it returns the last node it found. If it finds a second node with idx, it prints a warning, and caches only the later one.
However, if ASSERT is defined, we also traverse n->debug_orig(). debug_orig about the "original version" of this node (e.g. before cloning, or from last phase). Traversing these "orig edges" means we will traverse from the new graph to the old graph, and often find two nodes with the same idx, returning the last visited node with idx. Depending on the new and old graph, sometimes this is a node from the old or the new graph.
I believe this is not the desired behavior. If we start the search at the new root Compile::current()->root() we want to find only nodes in the new graph. If we want to find old nodes, we can start at the old root. If one wants to find the old node, given a new Mach node:
Compile::current()->matcher()->find_old_node(new_node);
Solution 1:
We remove traversing debug_orig from Node::find, so that we cannot traverse from new to old graph.
I wonder if traversing debug_orig has a legitimate use case?
Is there ever a case where a node is only reachable through debug_orig, and not through input/output edges?
If not, this is the best solution, since we get rid of code rather than adding new code that we need to maintain.
Solution 2:
We keep traversing debug_orig "edges", but only if both nodes are of the same graph (either both new, or both old).
Solution 3:
We always traverse debug_orig. But when we find a second node with idx, then we cache the one that is in the same graph as the BFS root node. If there is only a node with idx in the old graph, we would still report it, even if we start with the new root.
Usages of find_node and Node::find(idx):
find_node is only defined in node.cpp, and in no header file. It is only used in the debugger.
Node::find is used in find_node, and find_ctrl (both debgging only). Further, Node::find is used in PhaseIdealLoop::dump (as far as I understand, we only want to find new nodes here, reporting an old one would probably lead to problems). An other use is in IdealLoopTree::verify_tree (we verify if a node is dead by finding it via its idx. Reporting another, old node would be bad here).
As far as I can see, reporting nodes from another graph is never required, but rather potentially problematic.
Conclusion:
It seems find_node and Node::find are giving unreliable results. That should be fixed. Which solution would you take? Do you have any other solutions or objections in mind?
