This is an archive of the discontinued LLVM Phabricator instance.

[LoopInterchange] Track all dependencies, not just anti dependencies.
ClosedPublic

Authored by mcrosier on Sep 14 2016, 8:18 AM.

Details

Summary

Currently, we give up on loop interchange if we encounter a flow dependency anywhere in the loop list. Worse yet, we don't even track output dependencies.

This patch updates the dependency matrix computation to flow and output dependencies in the same way anti dependencies are tracked.

This improve an internal workload by a 2.2x speedup. All correctness test pass including SPEC2000, SPEC2006, and the llvm test-suite.

Note the loop interchange pass is off by default. It can be enabled with '-mllvm -enable-loopinterchange'

Please take a look.

Chad

Diff Detail

Repository
rL LLVM

Event Timeline

mcrosier updated this revision to Diff 71363.Sep 14 2016, 8:18 AM
mcrosier retitled this revision from to [LoopInterchange] Don't bail on flow dependencies when building dependency matrix..
mcrosier updated this object.
mcrosier updated this revision to Diff 71374.Sep 14 2016, 9:44 AM

-Provide full diff context.

mcrosier updated this revision to Diff 72087.Sep 21 2016, 11:03 AM
mcrosier retitled this revision from [LoopInterchange] Don't bail on flow dependencies when building dependency matrix. to [LoopInterchange] Track all dependencies, not just anti dependencies..
mcrosier updated this object.
mcrosier added a reviewer: mssimpso.
mcrosier removed a subscriber: mssimpso.

-Changed so flow and output dependencies are tracked the same way as anti dependencies. The legality analysis shouldn't care about the type of the dependency based on my reading (and Matt's feedback).

mssimpso added inline comments.Sep 21 2016, 11:20 AM
lib/Transforms/Scalar/LoopInterchange.cpp
120 ↗(On Diff #72087)

I'm not sure this check is needed. The unordered dependences are input dependences (RAR). It looks like the RAR case is explicitly checked a few lines up.

mcrosier added inline comments.Sep 21 2016, 11:27 AM
lib/Transforms/Scalar/LoopInterchange.cpp
120 ↗(On Diff #72087)

You are correct; I don't think we need the check. I was thinking it would make the code a bit more readable. However, I'm fine with changing it to an assert and reducing the indent.. I think that would accomplish the same thing.

mssimpso added inline comments.Sep 21 2016, 11:35 AM
lib/Transforms/Scalar/LoopInterchange.cpp
120 ↗(On Diff #72087)

An assert sounds good to me!

test/Transforms/LoopInterchange/interchange.ll
592 ↗(On Diff #72087)

It's probably not a bad idea to go ahead name the unnamed values here (like "%tmp0"), even though the rest of the tests here don't do this, to help prevent future breakage when making interleave more sophisticated.

mcrosier updated this revision to Diff 72091.Sep 21 2016, 12:00 PM
mcrosier marked 4 inline comments as done.

-Address Matt's feedback.

mssimpso accepted this revision.Sep 21 2016, 12:13 PM
mssimpso edited edge metadata.

LGTM.

This revision is now accepted and ready to land.Sep 21 2016, 12:13 PM
This revision was automatically updated to reflect the committed changes.

Thanks, Matt.