Page MenuHomePhabricator

DSE miscompile when store is clobbered across loop iterations
Needs ReviewPublic

Authored by apilipenko on Sep 24 2019, 7:34 PM.

Details

Summary

(This is a resubmission of D67870 with llvm-commits is subscribers)

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

bjope added inline comments.Oct 8 2019, 3:53 AM
lib/Transforms/Scalar/DeadStoreElimination.cpp
625

Isn't store-block confusing?

630

Load-block?

636

Is LI an old name for FirstI or FirstBBI? There is several more refs to LI and SI in the code below. Makes it a little bit hard to follow what is going on here, since the code/comments are rotten already in the baseline. Would not mind if that was cleaned up in a separate commit.

641

Is SI an old name for SecondI? Or SecondBBI?

666

nit: I don't think that we need this local variable. Just use *PredI instead. If you keep it, then be explicit about the type instead of using auto. (As currently written you have similarly named variables that more or less can denote the same thing, but without really explaining the difference by having any type information. Just confusing IMHO.)

670

If we have a cfg such as

A: (firstBB)
B: preds A, D
C: preds B (secondBB)
D: preds C

then I think we only visit block B once with this solution. And with VisitedThroughBackedge being false. It is only the SecondBB that can be visited twice afaict. Isn't that a problem?