This is an archive of the discontinued LLVM Phabricator instance.

[LAA] LLE 1/6: Expose Forward dependences
ClosedPublic

Authored by anemet on Sep 29 2015, 10:28 AM.

Details

Summary

Before this change, we didn't use to collect forward dependences since
none of the current clients (LV, LDist) required them.

The motivation to also collect forward dependences is a new pass
LoopLoadElimination (LLE) which discovers store-to-load forwarding
opportunities across the loop's backedge. The pass uses both lexically
forward or backward loop-carried dependences to detect these
opportunities.

The new pass also analyzes loop-independent (forward) dependences since
they can conflict with the loop-carried dependences in terms of how the
data flows through memory.

The newly added test only covers loop-carried forward dependences
because loop-independent ones are currently categorized as NoDep. The
next patch will fix this.

The two patches were tested together for compile-time regression. None
found in LNT/SPEC.

Note that with this change LAA provides all dependences rather than just
"interesting" ones. A subsequent NFC patch will remove the now trivial
isInterestingDependence and rename the APIs.

Diff Detail

Event Timeline

anemet updated this revision to Diff 35998.Sep 29 2015, 10:28 AM
anemet retitled this revision from to [LAA] LLE 1/6: Expose Forward dependences.
anemet updated this object.
anemet added a reviewer: hfinkel.
anemet added a subscriber: llvm-commits.

Hi Adam,

I've just been referred to this set of reviews as a mean to fix the following problem:

for (k..N)
  a[k] = b[k] + b[k+1];

Currently, GVN is hoisting the [k] load and adding an extra PHI to the loop body, making it unvectorizeable.

By adding LLE after the vectorizer, we can cover the same case in LLE without breaking vectorization opportunities.

Ultimately, Hal should approve all those patches, but I'll give my own take on them, if you're still interested in pushing them through.

This first one, LGTM.

cheers,
--renato

Hi Renato,

Thanks very much for looking at the set! I sure am interested pushing these through but I wanted to see where the main LLE patch was going before pinging these ones.

Adam

hfinkel accepted this revision.Nov 2 2015, 9:32 AM
hfinkel edited edge metadata.

LGTM too.

This revision is now accepted and ready to land.Nov 2 2015, 9:32 AM
This revision was automatically updated to reflect the committed changes.