Page MenuHomePhabricator

Cache reverse graph edges during dominator construction to avoid having to look them up later.
AcceptedPublic

Authored by dberlin on Jan 27 2017, 10:37 PM.

Details

Reviewers
chandlerc
davide
Summary

We already visit every single successor of the graph, so we don't
actually need to find the inverse edges, we can just store what they
are. This removes the need for inverse traits to compute dominators.

It's also a very slight speedup on large graphs, i'm leaving it here
while I test it on non-x86 platforms.

Event Timeline

dberlin created this revision.Jan 27 2017, 10:37 PM
davide added a subscriber: davide.Jan 27 2017, 10:41 PM
davide added inline comments.
include/llvm/Support/GenericDomTree.h
250

Just wondering, why 2?

Mostly empirical testing. By far, most nodes are either unconditional jumps or two block conditionals (be cond, invoke, etc)

davide accepted this revision.Jan 28 2017, 7:46 PM

Mostly empirical testing. By far, most nodes are either unconditional jumps or two block conditionals (be cond, invoke, etc)

Makes sense. I would add a comment to explain, if you don't mind. Most of the times I scratch my head trying to figure out how SmallVector<> initial size was chosen, and guess what, sometimes the choice is quite arbitrary (here we have a rationale, so wouldn't hurt adding that to the code). Assuming your non-x86 testing doesn't reveal any problems, I'd say ship it.

This revision is now accepted and ready to land.Jan 28 2017, 7:46 PM
davide added inline comments.Jan 28 2017, 7:49 PM
include/llvm/Support/GenericDomTreeConstruction.h
206

Nit: I prefer the explicit type when non-obvious from the right hand side, and I just recently realized LLVM coding convention suggests this too. Anyway, this is just splitting hair, so, up to you.

davide added a comment.Feb 3 2017, 5:30 PM

Are you landing this one?

I will add a comment about the #2 and land this one.

dberlin marked an inline comment as done.Feb 5 2017, 12:20 PM
dberlin added inline comments.
include/llvm/Support/GenericDomTree.h
250

commented

include/llvm/Support/GenericDomTreeConstruction.h
206

Making this an explicit type is a bit annoying. The real type is really GraphTraits<Inverse<NodeT> >::NodeRef

You would think it's just NodeT * (since that's what is in the SmallVector) ,but using NodeT causes it to screw up the inference of Calculate everywhere.

So i'm going to leave it auto :)

davide added a comment.Feb 5 2017, 1:30 PM

LGTM, thanks.

include/llvm/Support/GenericDomTreeConstruction.h
206

Oh, sure.

Dan, you still plan to get this in? FWIW, I ran with it for a while in my local tree.