This is an archive of the discontinued LLVM Phabricator instance.

[VPlan] Introduce VPlan-based dominator analysis.
ClosedPublic

Authored by dcaballe on Jul 1 2018, 10:18 PM.

Details

Summary

Context: Patch Series #1 for outer loop vectorization support in LV
using VPlan. (RFC: http://lists.llvm.org/pipermail/llvm-dev/2017-December/119523.html).

The patch introduces dominator analysis for VPBlockBases and extend
VPlan's GraphTraits specialization with the required interfaces. Dominator
analysis will be necessary to perform some H-CFG transformations and
to introduce VPLoopInfo (LoopInfo analysis on top of the VPlan representation).

Diff Detail

Repository
rL LLVM

Event Timeline

dcaballe created this revision.Jul 1 2018, 10:18 PM
fhahn added inline comments.Jul 6 2018, 9:44 AM
unittests/Transforms/Vectorize/VPlanDominatorTreeTest.cpp
20 ↗(On Diff #153666)

I've put up D49032 for review, which adds a VPlanTestBase class which can be re-used by different tests to construct modules & VPlans. What do you think? I can adjust the interface so it matches the one described here. What do you think? :)

dcaballe added inline comments.Jul 6 2018, 12:15 PM
unittests/Transforms/Vectorize/VPlanDominatorTreeTest.cpp
20 ↗(On Diff #153666)

It sounds pretty good! Much cleaner! I approved it but feel free to change it to match the interfaces here. I'll have a look at it again.
I'll rebase this patch on top of that once it's ready.

dcaballe added inline comments.Jul 6 2018, 1:07 PM
lib/Transforms/Vectorize/VPlan.cpp
198 ↗(On Diff #153666)

I'd like to hear your feedback on this. Internally, we started with an 'unsigned size' class member that we tried to maintain transformation after transformation. However, there are many cases where a simple size update is not possible and you need some kind of CFG traversal (sometimes a full region's traversal, such as in this code). For example, when you wrap part of a CFG with a region, when you insert or remove part of a CFG into/from a region, etc. Since 'getSize' is only used by GraphTraits and it's not a highly used interface, I though it could be cleaner to just compute the size when needed instead of trying to store and maintain it. However, if you think this is an overkill, we could give it a try to the latter approach.

dcaballe updated this revision to Diff 155230.Jul 12 2018, 11:25 AM

Rebasing this patch on top of D49032.

fhahn added inline comments.Jul 13 2018, 6:16 AM
lib/Transforms/Vectorize/VPlan.cpp
198 ↗(On Diff #153666)

It looks like is is not used for building a dominator tree. Maybe we should only add once it's needed?

Storing the size and updating it in the transformations would be better IMO and with an assertion here that checks the stored size matches the computed size it should be easy to track down cases where it is not updated properly.

592 ↗(On Diff #155230)

Use VPDominatorTree defined in VPlanDominatorTree.h?

lib/Transforms/Vectorize/VPlan.h
1319 ↗(On Diff #155230)

The only difference to the non-const VPRegionBlock* is the type parameter, right? It's not a lot of code, but would it make sense to add a templated implementation which we then can instantiate with both <VPRegionBlock*> and <const VPRegionBlock*>?

1340 ↗(On Diff #155230)

If we implement GraphTraits<const VPRegionBlock*>, should we also implement to const variant here?

lib/Transforms/Vectorize/VPlanDominatorTree.h
27 ↗(On Diff #155230)

can we just use using VPDominatorTree = DomTreeBase<VPBlockBase>; here?

34 ↗(On Diff #155230)

same as for VPDominatorTree

unittests/Transforms/Vectorize/VPlanDominatorTreeTest.cpp
59 ↗(On Diff #155230)

I am wondering if we could use a mapping from IR BBs to VPBBs and just match if the DT and VPDT agree on all cases. So instead testing everything manually, we rely on the DT to be correct.

dcaballe updated this revision to Diff 155793.Jul 16 2018, 5:13 PM

Thanks for the comments, Florian! Addressing your comments.

dcaballe added inline comments.Jul 16 2018, 5:16 PM
lib/Transforms/Vectorize/VPlan.cpp
198 ↗(On Diff #153666)

It looks like is is not used for building a dominator tree. Maybe we should only add once it's needed?

Weird... now I can't find the patch that needed this code. Hopefully, this code is no longer needed!

Storing the size and updating it in the transformations would be better IMO and with an assertion here that checks the stored size matches the computed size it should be easy to track down cases where it is not updated properly.

OK. if needed, let's try but I would leave the assertion for VPlanVerifier. We may want to incrementally update the size even when the region is inconsistent (e.g., region's entry and exit are not reachable from each other). We may also need a 'recomputeSize' for those cases where we cannot do an incremental update and a full recomputation is needed.

592 ↗(On Diff #155230)

OK. However, this only compiles if VPlanDominatorTree is a typedef. If VPDominatorTree turns into a derived class in the future, this won't compile (trying to use a protected class member). Hopefully, it will be easy to deduce that the error is coming from here.

lib/Transforms/Vectorize/VPlan.h
1319 ↗(On Diff #155230)

Well, lines 1299 and 1329 are explicit template specializations. I found this way to do it by using an extra level of inheritance but I'm not sure if the proposed solutions is worth the complexity. Deciphering an error message on these classes could be more challenging that desired :)

1340 ↗(On Diff #155230)

We are introducing GraphTraits on demand and the const variant of Inverse<VPRegionBlock*> doesn't seem to be needed at this point. Same happens for Inverse<VPBasicBlock *>

lib/Transforms/Vectorize/VPlanDominatorTree.h
27 ↗(On Diff #155230)

Ok, we can turn it into a class when specific extensions are needed.

34 ↗(On Diff #155230)

Sorry, I'll remove VPPostDominatorTree since it's not being used currently.

lib/Transforms/Vectorize/VPlanHCFGBuilder.h
64 ↗(On Diff #155230)

I'm not too happy with making this interface public just for unittesting. Are there any examples of unittest for private member functions? Could friendship be applied here in a clean way?

unittests/Transforms/Vectorize/VPlanDominatorTreeTest.cpp
59 ↗(On Diff #155230)

Let me think about it but I'm not sure. Wouldn't that hide bugs in the main algorithm that could be caught otherwise here?

fhahn added inline comments.Jul 17 2018, 1:49 PM
lib/Transforms/Vectorize/VPlan.h
1319 ↗(On Diff #155230)

Thanks, I think either way is fine and I suppose simpler error messages trump the slightly more compact code :)

1340 ↗(On Diff #155230)

Sounds good to me!

lib/Transforms/Vectorize/VPlanHCFGBuilder.h
64 ↗(On Diff #155230)

A friend class could work, if a forward declaration is enough (I don't think we want to include the unit test file here). googletest also ships a FRIEND_TEST macro (https://github.com/google/googletest/blob/master/googletest/include/gtest/gtest_prod.h) and from that I think the name of the friend class should have the following format: `
#define FRIEND_TEST(test_case_name, test_name)\
friend class test_case_name_test_name##_Test`

unittests/Transforms/Vectorize/VPlanDominatorTreeTest.cpp
59 ↗(On Diff #155230)

I don't think it's worth spending too much time on that, I just thought it might be a slightly more compact way to write the checks (DTs are widely used and *heavily* tested :))

dcaballe added inline comments.Jul 17 2018, 9:46 PM
lib/Transforms/Vectorize/VPlan.h
1319 ↗(On Diff #155230)

Ok, I'll revert it then.

lib/Transforms/Vectorize/VPlanHCFGBuilder.h
64 ↗(On Diff #155230)

Thanks a lot. I thought the friendship would be more problematic. Done!

unittests/Transforms/Vectorize/VPlanDominatorTreeTest.cpp
59 ↗(On Diff #155230)

Ok, let's go with this. More than an exhaustive testing of VPDT, what I want to test here is the new GraphTraits code and this should be enough for that.

dcaballe updated this revision to Diff 156007.Jul 17 2018, 9:49 PM

Reverting GraphTraits changes and adding VPlanTestBase as friend of VPlanHCFGBuilder.

fhahn accepted this revision.Jul 23 2018, 8:54 AM

LGTM, thanks! Please hold off committing a few days, in case other people have additional comments.

lib/Transforms/Vectorize/LoopVectorize.cpp
7062 ↗(On Diff #156007)

nit: Just *Plan should be enough.

unittests/Transforms/Vectorize/VPlanTestBase.h
54 ↗(On Diff #156007)

nit: just *Plan should work

65 ↗(On Diff #156007)

nit: just *Plan

This revision is now accepted and ready to land.Jul 23 2018, 8:54 AM
dcaballe marked 3 inline comments as done.Jul 27 2018, 12:15 PM

Thanks, Florian! I'll go ahead with the commit!

This revision was automatically updated to reflect the committed changes.