This is an archive of the discontinued LLVM Phabricator instance.

DSE miscompile when store is clobbered across loop iterations
AbandonedPublic

Authored by apilipenko on Sep 20 2019, 5:41 PM.

Details

Summary

Currently DSE miscompiles the following example:

a = calloc(n+1)
for (int i = 0; i < n; i++) {
  store 1, a[i+1] // (1)
  store 0, a[i]   // (2)
}

It eliminates the second store thinking that it's redundant. This happens because memoryIsNotModifiedBetween doesn't see a[i] being clobbered in between the allocation and the store.

memoryIsNotModifiedBetween does a backwards scan through the CFG from SecondI to FirstI. It looks for instructions which can modify the memory location accessed by SecondI. For every may-write-to-memory instruction is asks AA whether this instruction modifies memory location accessed by SecondI.

The problem occurs when it visits the loop block through a backedge. It asks the AA about aliasing between stores (1) and (2). BasicAA sees that two stores access addresses which are distincs offsets from the same base and concludes that they don't alias. This is true for accesses within one loop iteration, but this is not true across iterations.

The change is to keep track whether we visit a block through a backedge. If we visit the block through a backedge, be conservative and treat any may-write-to-memory instruction as a clobber.

Note that there is a somewhat similar problem in DA:
https://bugs.llvm.org/show_bug.cgi?id=42143

Diff Detail

Event Timeline

apilipenko created this revision.Sep 20 2019, 5:41 PM
reames added a subscriber: reames.Sep 23 2019, 2:19 PM

The problem occurs when it visits the loop block through a backedge. It asks the AA about aliasing between stores (1) and (2). BasicAA sees that two stores access addresses which are distincs offsets from the same base and concludes that they don't alias. This is true for accesses within one loop iteration, but this is not true across iterations.

This really sounds like a bug in BasicAA, not a bug in DSE. Reading through BasicAA, we have a number of cases where we explicitly reason about values in loops from different iterations being potentially equal. I think you've simply found one more. I will certainly admit, the documentation on expected behaviour is a tad bit lacking here though.

How do others interpret this?

It looks like you forgot to CC llvm-commits? Please post a new differential so the patch is sent to the list.

In some sense, the alias() method of AliasAnalysis really has three parameters: the two memory locations are explicit, and the implicit third parameter is a position in the source code where both locations are valid. Given that context, you can prove "obvious" identities like aliasing between x and x+1, aliasing with restrict pointers, etc. This is generally useful for a lot of transforms. In contexts where that doesn't work, we use some other mechanism, like LoopAccessAnalysis. BasicAA does look through PHI nodes in certain cases, but when it does, it's very careful to use a different set of assumptions (although we've had bugs with this in the past).

This is specifically a hole in the calloc() handling, right? This case can't come up in regular load->store no-op stores: the address of the load dominates the load, so the address dominates all the operations between the load and the store, so alias() does the right thing.

fhahn added a subscriber: fhahn.Sep 24 2019, 9:21 AM

It looks like you forgot to CC llvm-commits? Please post a new differential so the patch is sent to the list.

Resubmitted as D68006.

This is specifically a hole in the calloc() handling, right? This case can't come up in regular load->store no-op stores: the address of the load dominates the load, so the address dominates all the operations between the load and the store, so alias() does the right thing.

That's right. I don't think that load->store case is affected.

apilipenko abandoned this revision.Sep 27 2019, 4:44 PM

This change was resubmitted as D68006.