This is an archive of the discontinued LLVM Phabricator instance.

[LICM & MSSA] Limit unsafe sinking and hoisting.
ClosedPublic

Authored by asbirlea on Jun 19 2019, 5:18 PM.

Details

Summary

The getClobberingMemoryAccess API checks for clobbering accesses in a loop by walking the backedge. This may check if a memory access is being
clobbered by the loop in a previous iteration, depending how smart AA got over the course of the updates in MemorySSA (it does not occur when built from scratch).
If no clobbering access is found inside the loop, it will optimize to an access outside the loop. This however does not mean that access is safe to sink.
Given:

for i
  load a[i]
  store a[i]

The access corresponding to the load can be optimized to outside the loop, and the load can be hoisted. But it is incorrect to sink it.
In order to sink the load, we'd need to check no Def clobbers the Use in the same iteration. With this patch we currently restrict sinking to either
Defs not existing in the loop, or Defs preceding the load in the same block. An easy extension is to ensure the load (Use) post-dominates all Defs.

Caught by PR42294.

This issue also shed light on the converse problem: hoisting stores in this same scenario would be illegal. With this patch we restrict
hoisting of stores to the case when their corresponding Defs are dominating all Uses in the loop.

Diff Detail

Repository
rL LLVM

Event Timeline

asbirlea created this revision.Jun 19 2019, 5:18 PM
Herald added a project: Restricted Project. · View Herald TranscriptJun 19 2019, 5:18 PM
Herald added subscribers: Prazek, jlebar. · View Herald Transcript

Thanks for this!

I realize that the original test-case is difficult to minimize and reproduce, so having a 'fails before, succeeds now' test isn't easy to make, nor would it be easy to reason about if it breaks. Still, can we please have a quick lit test that asserts e.g.

for i
  load a[i]
  store a[i]

doesn't have the load sunk?

lib/Transforms/Scalar/LICM.cpp
380 ↗(On Diff #205721)

nit: please add /*IsSink=*/

1238 ↗(On Diff #205721)

s/hoising/hoisting/

2303 ↗(On Diff #205721)

s/dyn_cast/isa

also, isa<MemoryDef>(X) implies !isa<MemoryUse>(X), so is this check needed?

2305 ↗(On Diff #205721)

nit: if the check is needed, no else after an if that continues, please

asbirlea updated this revision to Diff 205894.Jun 20 2019, 1:40 PM
asbirlea marked 4 inline comments as done.

Address comments and add testcase.

This revision is now accepted and ready to land.Jun 20 2019, 1:48 PM
This revision was automatically updated to reflect the committed changes.

The test pr42294.ll breaks when running the test suite on a build without asserts. Specifically, opt doesn't know about the option -debug-only. I confirmed that adding a REQUIRES: asserts to the beginning of the test fixes things. I'm not too familiar with this area, so if you have a way to make it work with non-asserts build then that would be great. Otherwise, we can just require that asserts are enabled for this test to run.

yrouban added inline comments.
llvm/trunk/test/Analysis/MemorySSA/pr42294.ll
1

I have just added REQUIRES asserts as it uses -debug-only=licm