Page MenuHomePhabricator

Ensure a complete post-dominance tree is built in the presence of unreachables
Needs ReviewPublic

Authored by grosser on Sep 7 2015, 6:47 AM.

Details

Summary

This patch ensures a full post-dominance tree is built for all reachable parts
of a CFG even if some parts of the CFG are unreachable. Before this change,
we treated basic blocks that end in both return statements or unreachable
instructions as roots of the post-dominance tree. As a result, as soon as an
unreachable statement was part of the CFG, parts of the post-dominance relation
in the reachable part of the CFG was lost. With this patch, we now only add
returning basic blocks, but not unreachable basic blocks as root nodes to the
post-dominance tree. This means the unreachable blocks are treated identical to
infinite loops. They do not show up in the post-dominance relation and they do
not affect the post-dominance tree of the reachable part of the CFG.

Diff Detail

Event Timeline

grosser updated this revision to Diff 34156.Sep 7 2015, 6:47 AM
grosser retitled this revision from to Ensure a complete post-dominance tree is built in the presence of unreachables.
grosser updated this object.
grosser added reviewers: dberlin, chandlerc, arsenm.
grosser added a subscriber: llvm-commits.
dberlin edited edge metadata.Sep 7 2015, 10:05 AM

So, IIRC, in the dominance tree, unreachable blocks are deliberately part of the domtree, and we have dominance queries answerable about them.
What is the reason we should have different behavior for the two?

(Also, what happens if i try to make a post-dominates query about an unreachable block now?
It would be good to have a unit test for this)

I'm also not suggesting your patch is wrong, i'm suggesting our behavior in dominators may be undesirable as well, though i haven't thought about it.

Also note that your change to when we do addRoot will still not handle infinite loops properly:
We will end up with a null root node in some cases (infinite self-loops, for example), because it has predecessors, (the entry and itself), and a successor (itself)
This will cause child_begin != child_end, and thus, return false from isDomExit, which will cause us not to add a root, and end up with a null root node instead of a proper virtual root node.

It's one thing to leave the blocks out, it's another to say "there is no root node at all". We are still supposed to have a root node, even if it's virtual.

Note that in general, it's not going to be possible to determine reachability, and what we should exclude anyway, without a DFS walk

Given that we know that the only way (at least, i can think of) to avoid adding another DFS walk is to make the root finding part of dom tree construction, i'd rather not add see us add isDomExit, because it's another thing that will need to be cleaned up to make this happen.
(The bug has more details).

include/llvm/IR/Dominators.h
119

This is not a sufficient check for non-reachability.

What if i have a infinite self-loop?

https://llvm.org/bugs/show_bug.cgi?id=24415

(extend it to multiple blocks if you like)

Thank you Daniel for joining the discussion. It seems the corner
cases of (post)dominance analysis are always worth some thoughts.

dberlin added a comment.

So, IIRC, in the dominance tree, unreachable blocks are deliberately part of the domtree, and we have dominance queries answerable about them.
What is the reason we should have different behavior for the two?

B is dominated by A if every path from the entry of the function to B goes through A.

For unreachables this seems well defined:

Example 1:

entry:
   br label %exit

exit:
   unreachable

Inorder Dominator Tree:

[1] %entry {0,3}
  [2] %exit {1,2}

The basic blocks that we leave out of the dominance tree (and which I believe
are similar to unreachables in the post-dominance tree) are the once to which
there is no path from the entry at all. Something like:

Example 2:

entry:
   br label %exit

otherbb:
   br label %exit

exit:
   ret void

Inorder Dominator Tree:

[1] %entry {0,3}
  [2] %exit {1,2}

'otherbb' is left out.

If we now look at the post-dominance tree of example 2, 'otherbb' shows up again as there
is a path going backwards from exit to otherbb:

Inorder PostDominator Tree:

[1] %exit {0,5}
  [2] %otherbb {1,2}
  [2] %entry {3,4}

This means 'exit' is post-dominating by 'otherbb'. This relation is reflected in the post-dominator
tree.

(Also, what happens if i try to make a post-dominates query about an unreachable block now?
It would be good to have a unit test for this)

The same as what happens today with infinite loops in post-dominator trees or 'otherbb' in
example 2, we return nullptr:

DomTreeNodeBase<NodeT> *getNode(NodeT *BB) const {
  auto I = DomTreeNodes.find(BB);
  if (I != DomTreeNodes.end())
    return I->second.get();
  return nullptr;
}

I think this makes sense, but you are right that a unittest would probablynot hurt. I would
be glad to add one.

I'm also not suggesting your patch is wrong, i'm suggesting our behavior in dominators may be undesirable as well, though i haven't thought about it.

I think leaving unreachables in dominators is right, but this does not mean that they should be part of the post-dominator tree.

In case of an unreachable (or an infinite loop), there can not be any path from a function exit through an unreachable/infinite-loop basic block that
could establish a post-dominance relation.

Also note that your change to when we do addRoot will still not handle infinite loops properly:
We will end up with a null root node in some cases (infinite self-loops, for example), because it has predecessors, (the entry and itself), and a successor (itself)
This will cause child_begin != child_end, and thus, return false from isDomExit, which will cause us not to add a root, and end up with a null root node instead of a proper virtual root node.

This patch was not intended to address the issue you are pointing me to (I was not aware of it). It leaves the behavior for this case unchanged.

Looking at the example below, we see that infinite loops are left out of the post-dominator tree exactly the way I suggest us to do for the unreachable blocks.

define void @foo() {
entry:
   br i1 true, label %next, label %exit

next:
   br label %next

exit:
   ret void
}

Inorder PostDominator Tree:

[1]  <<exit node>> {0,5}
  [2] %exit {1,4}
    [3] %entry {2,3}

This result is what I expect.

Now for the case where there is no reachable node at all, we do - as you observe - not even get a virtual exit node:

define void @foo() {
entry:
   br label %next

next:
   br label %next
}

Printing analysis 'Post-Dominator Tree Construction' for function 'foo':

Inorder PostDominator Tree: DFSNumbers invalid: 0 slow queries.

It's one thing to leave the blocks out, it's another to say "there is no root node at all". We are still supposed to have a root node, even if it's virtual.

I do not have a strong opinion here, but adding a virtual exit in case there is not even a single root node seems to be simple.

If we agree that is the right behavior, I could add this in a follow-up patch.

Note that in general, it's not going to be possible to determine reachability, and what we should exclude anyway, without a DFS walk

I think these are two issues: I am in this patch mainly concerned about the post-dominator tree being correct for dominance relations that are caused by a path
that goes through two basic blocks and ends at an exit of the function. This is what is well defined and for this I do not see why another DFS walk would be needed.
The set of exits is well defined and can just be added, no?

What you seem to aim for below is to define a relation similar to post-dominance for blocks that are not on any path that
finishes in an exit block of the function. To my understanding, this would correspond to adding 'otherbb' somehow into the dominator tree (e.g. to
establish a dominance-like relation in parts of the tree that can not be reached from the exit node. I believe this is considerably more involved and indeed
requires some larger restructuring. Do you have use cases were having such relation actually is beneficial in some way? I thought about this myself, but did
not yet find an example where this would be useful.

Given that we know that the only way (at least, i can think of) to avoid adding another DFS walk is to make the root finding part of dom tree construction, i'd rather not add see us add isDomExit, because it's another thing that will need to be cleaned up to make this happen.
(The bug has more details).

Given my explanation above, I think this patch makes sense. However, let's see first if we can reach a common understanding on the issues.

================
Comment at: include/llvm/IR/Dominators.h:119
@@ +118,3 @@
+ GraphTraits<Function *>::child_end(N))
+ return false;
+


This is not a sufficient check for non-reachability.

What if i have a infinite self-loop?

https://llvm.org/bugs/show_bug.cgi?id=24415

(extend it to multiple blocks if you like)

This is not intended as check for non-reachability. This is intended as a check of where to start the DFS search that determines reachability.

Best,
Tobias

lvoufo added a subscriber: lvoufo.Dec 17 2015, 5:59 AM
arsenm resigned from this revision.Aug 3 2017, 4:54 PM