[GVN] Fix miscompile shown in github issue #57025

[bjope]

Summary

Make sure that we are conservative in AnalyzeLoadAvailability when
finding an Unknown memdep, also when the dependent BB is dead.

Fixes: https://github.com/llvm/llvm-project/issues/57025

[bjope]

llvm/test/Transforms/GVN/memdep-unknown-deadblocks.ll

49

This was almost correct.
It would have been correct if this phi looked like this instead:

[[VALUE:%.*]] = phi i16 [ 42, [[STORE_IDX_I]] ], [ [[7]], [[STORE_IDX_0]] ]

and then the load in while.end can be eliminated. And then we also would get rid of VALUE2 and DEAD.

But my fix here is not aiming at optimizing this kind of scenario, just to avoid the miscompile we see today.
Current fix makes the result look just like if we would have had

%j = phi i16 [ %i, %store.done ], [ poison, %while.body ]

instead of

%j = phi i16 [ %i, %store.done ], [ 0, %while.body ]

already in the input. Which would have triggered an early remove of that phi in GVN iteration 0. So it does not seem like GVN would eliminate the load by adding a phi in store.done even if cleaning up some of the "stupid" things in the IR such as the dead load and the phi related to the unconditional cond branch.

[bjope]

Gentle ping!

(Looks like nikic har been away for some time. Do you know anything about this @fhahn, or any idea for additional reviewers? I know that someone is trying to replace MemDep by MemorySSA in this pass, but maybe won't hurt to get things more correct first anyway.)

[nikic]

I've spent a good bit of time looking into this, and I don't think this patch fixes the right issue.

The core problem seems to be that the store in store.idx.0 is not reported as a def clobber, even though it clearly is on the first loop iteration. The reason we get this result is that we perform an AA query between %arr and %arr.i -- but %arr.i is in a block that that is guarded by %i != 0, so the two are NoAlias.

I'm not entirely sure who is at fault here yet, but probably we shouldn't be using %arr.i as the pointer value here -- while it has the correct value, it is located in an incorrect context.

[nikic]

The good news is that PHITranslateValue has a MustDominate argument that controls this behavior. If we make MemDep pass MustDominate=true, then this phi translation is no longer performed. The bad news is that this does regress GVN test results...

[nikic]

Alternative patch: https://reviews.llvm.org/D132935

[bjope]

In D131776#3758136, @nikic wrote:

Alternative patch: https://reviews.llvm.org/D132935

Big thanks for looking at this (and I wasn't sure at all about my patch attempt so your solution is probably much better, specially if it also happens to solve our old outstanding issue since 2017 ( https://github.com/llvm/llvm-project/issues/30999 ).

[bjope]

llvm/lib/Transforms/Scalar/GVN.cpp

1297

I've tried replacing this with assert(!DepInfo.isUnknown()) and it seems like that is a totally untested scenario (except for the new test/Transforms/GVN/memdep-unknown-deadblocks.ll test case).

So even if D131776 is a better fix in some sense, I'm still wondering what would be correct to do if getting here with a DepInfo that is Unknown. At least when I looked at this a couple of weeks ago I got the feeling that the behavior without this patch could be wrong and that adding to UnavailableBlocks would be more correct as we do not know if there is a dependent mem-op or not. Or am I missing something.

Given that D131776 probably will hide this code path also for the memdep-unknown-deadblocks.ll test case, then I'm not sure how to motivate this fix. If we never expect to get here with DepInfo.isUnknown, then maybe we should assert on that instead.

I'll try to run some fuzzy testing to see if I can trigger this code path even with the fix from D131776.

[nikic]

llvm/lib/Transforms/Scalar/GVN.cpp

1297

I don't think this code path cares about the value of DepInfo at all. If the block is unreachable, then we can always assume it produces a poison value.

[bjope]

Abandoned. Problem was solved in D131776.

llvm/lib/Transforms/Scalar/GVN.cpp

1297

Right. Well, I have been able to trigger this code path with a DepInfo.isUnknown() here, but haven't found any case where the change in this patch makes a difference to the end result (given that I have merged the fix from D131776).

So I'm not doing any further investigation of this right now, and will just abondon this issue.

Btw, thanks a lot for the help (and with the more correct fix in D131776). Very much appreciated!

llvm/lib/Transforms/Scalar/GVN.cpp

void GVNPass::AnalyzeLoadAvailability(LoadInst *Load, LoadDepVect &Deps,
   // dependencies that produce an unknown value for the load (such as a call
   // that could potentially clobber the load).
   unsigned NumDeps = Deps.size();
   for (unsigned i = 0, e = NumDeps; i != e; ++i) {
     BasicBlock *DepBB = Deps[i].getBB();
     MemDepResult DepInfo = Deps[i].getResult();
 
     if (DeadBlocks.count(DepBB)) {
+      // A non-local dependency means that the analysis might have given up
+      // e.g. based on phi translation failure (at least if the dependency is
+      // Unknown). Need to be conservative and say that the value isn't
+      // available.
+      if (DepInfo.isUnknown()) {
+        UnavailableBlocks.push_back(DepBB);
+        continue;
+      }
       // Dead dependent mem-op disguise as a load evaluating the same value
       // as the load in question.
       ValuesPerBlock.push_back(AvailableValueInBlock::getUndef(DepBB));
       continue;
     }
 
     // The address being loaded in this non-local block may not be the same as
     // the pointer operand of the load if PHI translation occurs.  Make sure

llvm/test/Transforms/GVN/memdep-unknown-deadblocks.ll

 declare void @verify(i16)
 
 define void @test(i16 %g) {
 ; CHECK-GVN-LABEL: @test(
 ; CHECK-GVN-NEXT:  entry:
 ; CHECK-GVN-NEXT:    [[ARR:%.*]] = alloca [4 x i16], align 1
 ; CHECK-GVN-NEXT:    br label [[FOR_BODY:%.*]]
 ; CHECK-GVN:       for.body:
-; CHECK-GVN-NEXT:    [[VALUE2:%.*]] = phi i16 [ undef, [[ENTRY:%.*]] ], [ [[DEAD:%.*]], [[WHILE_END:%.*]] ]
-; CHECK-GVN-NEXT:    [[I:%.*]] = phi i16 [ 0, [[ENTRY]] ], [ [[NEXT_I:%.*]], [[WHILE_END]] ]
+; CHECK-GVN-NEXT:    [[I:%.*]] = phi i16 [ 0, [[ENTRY:%.*]] ], [ [[NEXT_I:%.*]], [[WHILE_END:%.*]] ]
 ; CHECK-GVN-NEXT:    [[CMP0:%.*]] = icmp eq i16 [[I]], 0
 ; CHECK-GVN-NEXT:    br i1 [[CMP0]], label [[STORE_IDX_0:%.*]], label [[STORE_IDX_I:%.*]]
 ; CHECK-GVN:       store.idx.0:
 ; CHECK-GVN-NEXT:    store i16 7, ptr [[ARR]], align 1
 ; CHECK-GVN-NEXT:    br label [[STORE_DONE:%.*]]
 ; CHECK-GVN:       store.idx.i:
 ; CHECK-GVN-NEXT:    [[ARR_I:%.*]] = getelementptr [4 x i16], ptr [[ARR]], i16 0, i16 [[I]]
 ; CHECK-GVN-NEXT:    store i16 42, ptr [[ARR_I]], align 1
 ; CHECK-GVN-NEXT:    br label [[STORE_DONE]]
 ; CHECK-GVN:       store.done:
-; CHECK-GVN-NEXT:    [[VALUE:%.*]] = phi i16 [ 42, [[STORE_IDX_I]] ], [ [[VALUE2]], [[STORE_IDX_0]] ]
 ; CHECK-GVN-NEXT:    br label [[WHILE_BODY:%.*]]
 ; CHECK-GVN:       while.body:
 ; CHECK-GVN-NEXT:    br i1 false, label [[WHILE_BODY_WHILE_BODY_CRIT_EDGE:%.*]], label [[WHILE_END]]
 ; CHECK-GVN:       while.body.while.body_crit_edge:
 ; CHECK-GVN-NEXT:    br label [[WHILE_BODY]]
 ; CHECK-GVN:       while.end:
 ; CHECK-GVN-NEXT:    [[ARR_J:%.*]] = getelementptr [4 x i16], ptr [[ARR]], i16 0, i16 [[I]]
+; CHECK-GVN-NEXT:    [[VALUE:%.*]] = load i16, ptr [[ARR_J]], align 1
 ; CHECK-GVN-NEXT:    tail call void @verify(i16 [[VALUE]])
 ; CHECK-GVN-NEXT:    [[NEXT_I]] = add i16 [[I]], 1
 ; CHECK-GVN-NEXT:    [[ARR_NEXT_I:%.*]] = getelementptr [4 x i16], ptr [[ARR]], i16 0, i16 [[NEXT_I]]
-; CHECK-GVN-NEXT:    [[DEAD]] = load i16, ptr [[ARR_NEXT_I]], align 1
 ; CHECK-GVN-NEXT:    [[CMP4:%.*]] = icmp slt i16 [[NEXT_I]], 3
 ; CHECK-GVN-NEXT:    br i1 [[CMP4]], label [[FOR_BODY]], label [[FOR_END:%.*]]
 ; CHECK-GVN:       for.end:
 ; CHECK-GVN-NEXT:    ret void
 ;
 ; CHECK-GVN-O1-LABEL: @test(
 ; CHECK-GVN-O1-NEXT:  entry:
-; CHECK-GVN-O1-NEXT:    tail call void @verify(i16 42)
+; CHECK-GVN-O1-NEXT:    tail call void @verify(i16 7)
 ; CHECK-GVN-O1-NEXT:    tail call void @verify(i16 42)
 ; CHECK-GVN-O1-NEXT:    tail call void @verify(i16 42)
 ; CHECK-GVN-O1-NEXT:    ret void
 ;
 ; CHECK-O1-LABEL: @test(
 ; CHECK-O1-NEXT:  entry:
 ; CHECK-O1-NEXT:    tail call void @verify(i16 7)
 ; CHECK-O1-NEXT:    tail call void @verify(i16 42)