[PHITranslateAddr] Require dominance when searching for translated address (PR57025)

[nikic]

Summary

This is a fix for PR57025 and an alternative to D131776. The problem in the memdep-unknown-deadblocks.ll test case is that phi translation of gep %arr, %j into store.done looks for a GEP of the form gep %arr, %i and picks the one in the store.idx.i block. While this instruction has the correct pointer address, it occurs in a context where %i != 0. As such, we get a NoAlias result for the store in store.idx.0 block, even though they do alias for %i == 0 (which is legal in the original context of the pointer).

PHITranslateValue already has a MustDominate option, which can be used to restrict PHI translation results to values that dominate the translated-into block. However, this is more aggressive than what we need and would significantly regress GVN results. In particular, if we have a pointer value that does not require any translation, then it is fine to continue using that value in the predecessor, because the context is still correct for the original query. We only run into problems if PHITranslateSubExpr() picks a completely random instruction in a context that may have preconditions that do not hold.

Fix this by always performing the dominance checks in PHITranslateSubExpr(), without enabling the more general MustDominate requirement.

Fixes https://github.com/llvm/llvm-project/issues/57025. This also fixes the test case for https://github.com/llvm/llvm-project/issues/30999, but I'm not sure whether that's just the particular test case, or a general solution to the problem.

Depends on D131775.

[asbirlea]

Thank you for digging to figure this out. I believe this is the right solution here, but please wait for other's input too.

[nikic]

Rebase over another test llvm/test/Transforms/GVN/phi-translation-to-wrong-context.ll, which I think makes the root cause of the issue easier to understand, and doesn't involve unreachable code or loops.

[asbirlea]

Wow on that last test O_o.

[fhahn]

Thanks for the fix, LGTM as well.

, if we have a pointer value that does not require any translation, then it is fine to continue using that value in the predecessor, because the context is still correct for the original query.

Could we just check for that case in translation and then always set MustDominate to true?

[nikic]

In D132935#3764102, @fhahn wrote:

Thanks for the fix, LGTM as well.

, if we have a pointer value that does not require any translation, then it is fine to continue using that value in the predecessor, because the context is still correct for the original query.

Could we just check for that case in translation and then always set MustDominate to true?

I don't think so, in that we do need the current strict MustDominate behavior when we check whether the translated value needs to be materialized in the predecessor during PRE.

llvm/lib/Analysis/PHITransAddr.cpp

 /// 'MustDominate' is true, the translated value must dominate
 /// PredBB.  This returns true on failure and sets Addr to null.
 bool PHITransAddr::PHITranslateValue(BasicBlock *CurBB, BasicBlock *PredBB,
                                      const DominatorTree *DT,
                                      bool MustDominate) {
   assert(DT || !MustDominate);
   assert(Verify() && "Invalid PHITransAddr!");
   if (DT && DT->isReachableFromEntry(PredBB))
-    Addr =
-        PHITranslateSubExpr(Addr, CurBB, PredBB, MustDominate ? DT : nullptr);
+    Addr = PHITranslateSubExpr(Addr, CurBB, PredBB, DT);
   else
     Addr = nullptr;
   assert(Verify() && "Invalid PHITransAddr!");
 
   if (MustDominate)
     // Make sure the value is live in the predecessor.
     if (Instruction *Inst = dyn_cast_or_null<Instruction>(Addr))
       if (!DT->dominates(Inst->getParent(), PredBB))

llvm/test/Transforms/GVN/condprop-memdep-invalidation.ll

 ; CHECK-NEXT:    call void @use(i16 [[L_2]])
 ; CHECK-NEXT:    br label [[LOOP_1_LATCH]]
 ; CHECK:       else.2:
 ; CHECK-NEXT:    [[GEP_4:%.*]] = getelementptr [4 x i16], ptr [[UB_16]], i16 1, i16 [[IV_1]]
 ; CHECK-NEXT:    [[L_3:%.*]] = load i16, ptr [[GEP_4]], align 2
 ; CHECK-NEXT:    call void @use(i16 [[L_3]])
 ; CHECK-NEXT:    br label [[LOOP_1_LATCH]]
 ; CHECK:       loop.1.latch:
-; CHECK-NEXT:    [[L_42:%.*]] = phi i16 [ [[L_3]], [[ELSE_2]] ], [ [[L_2]], [[THEN_2]] ]
 ; CHECK-NEXT:    [[IV_1_NEXT]] = add i16 [[IV_1]], 1
 ; CHECK-NEXT:    [[CMP_3:%.*]] = icmp slt i16 [[IV_1_NEXT]], 2
 ; CHECK-NEXT:    br i1 [[CMP_3]], label [[LOOP_1_HEADER]], label [[LOOP_2:%.*]]
 ; CHECK:       loop.2:
-; CHECK-NEXT:    [[L_4:%.*]] = phi i16 [ [[L_42]], [[LOOP_1_LATCH]] ], [ [[L_4_PRE:%.*]], [[LOOP_2_LOOP_2_CRIT_EDGE:%.*]] ]
-; CHECK-NEXT:    [[IV_2:%.*]] = phi i16 [ 0, [[LOOP_1_LATCH]] ], [ [[IV_2_NEXT:%.*]], [[LOOP_2_LOOP_2_CRIT_EDGE]] ]
-; CHECK-NEXT:    [[SUM:%.*]] = phi i16 [ 0, [[LOOP_1_LATCH]] ], [ [[SUM_NEXT:%.*]], [[LOOP_2_LOOP_2_CRIT_EDGE]] ]
+; CHECK-NEXT:    [[IV_2:%.*]] = phi i16 [ 0, [[LOOP_1_LATCH]] ], [ [[IV_2_NEXT:%.*]], [[LOOP_2]] ]
+; CHECK-NEXT:    [[SUM:%.*]] = phi i16 [ 0, [[LOOP_1_LATCH]] ], [ [[SUM_NEXT:%.*]], [[LOOP_2]] ]
 ; CHECK-NEXT:    [[GEP_5:%.*]] = getelementptr [4 x i16], ptr [[UB_16]], i16 1, i16 [[IV_2]]
+; CHECK-NEXT:    [[L_4:%.*]] = load i16, ptr [[GEP_5]], align 2
 ; CHECK-NEXT:    [[SUM_NEXT]] = add i16 [[SUM]], [[L_4]]
 ; CHECK-NEXT:    [[IV_2_NEXT]] = add i16 [[IV_2]], 1
 ; CHECK-NEXT:    [[CMP_4:%.*]] = icmp slt i16 [[IV_2_NEXT]], 2
-; CHECK-NEXT:    br i1 [[CMP_4]], label [[LOOP_2_LOOP_2_CRIT_EDGE]], label [[EXIT:%.*]]
-; CHECK:       loop.2.loop.2_crit_edge:
-; CHECK-NEXT:    [[GEP_5_PHI_TRANS_INSERT:%.*]] = getelementptr [4 x i16], ptr [[UB_16]], i16 1, i16 [[IV_2_NEXT]]
-; CHECK-NEXT:    [[L_4_PRE]] = load i16, ptr [[GEP_5_PHI_TRANS_INSERT]], align 2
-; CHECK-NEXT:    br label [[LOOP_2]]
+; CHECK-NEXT:    br i1 [[CMP_4]], label [[LOOP_2]], label [[EXIT:%.*]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    ret i16 [[SUM_NEXT]]
 ;
   br label %loop.1.header
 
 loop.1.header:
   %iv.1 = phi i16 [ 0, %0 ], [ %iv.1.next, %loop.1.latch ]
   %cmp.1 = icmp eq i16 %iv.1, 0

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

 ;    and the loaded value is passed to the verify function.
 ;  - There is a dead load of the not yet initialized arr[j+1] in the epilog
 ;    block. This might seem irrelevant, but is needed to reproduce the
 ;    miscompile.
 ;
 ; Expected semantic of the function is that verify() will be called three
 ; times, with the values 7, 42 and 42.
 
-; FIXME: The value passed to the verify function is loaded by
-;           %value = load i16, ptr %arr.j, align 1
-;        but currently GVN is replacing it with a faulty PHI in the
-;        store.done block.
-
 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)

llvm/test/Transforms/GVN/phi-translation-to-wrong-context.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -S -gvn < %s | FileCheck %s
 
-; FIXME
 ; Phi translation of %gep.j cannot use %gep.i, which is located in a context
 ; where %i != 0, and would result in incorrect NoAlias results in a context
 ; where %i == 0 may hold.
 
 define i32 @test(i64 %i, i1 %c1, i1 %c2) {
 ; CHECK-LABEL: @test(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[PTR:%.*]] = alloca [2 x i32], align 4
 ; CHECK-NEXT:    br i1 [[C1:%.*]], label [[IF:%.*]], label [[ELSE:%.*]]
 ; CHECK:       if:
 ; CHECK-NEXT:    br i1 [[C2:%.*]], label [[IF2:%.*]], label [[ELSE2:%.*]]
 ; CHECK:       if2:
 ; CHECK-NEXT:    store i32 1, ptr [[PTR]], align 4
+; CHECK-NEXT:    [[GEP_J_PHI_TRANS_INSERT:%.*]] = getelementptr inbounds i32, ptr [[PTR]], i64 [[I:%.*]]
+; CHECK-NEXT:    [[V_PRE:%.*]] = load i32, ptr [[GEP_J_PHI_TRANS_INSERT]], align 4
 ; CHECK-NEXT:    br label [[JOIN:%.*]]
 ; CHECK:       else2:
 ; CHECK-NEXT:    store i32 2, ptr [[PTR]], align 4
 ; CHECK-NEXT:    br label [[JOIN]]
 ; CHECK:       join:
-; CHECK-NEXT:    [[J:%.*]] = phi i64 [ [[I:%.*]], [[IF2]] ], [ 0, [[ELSE2]] ]
+; CHECK-NEXT:    [[V:%.*]] = phi i32 [ [[V_PRE]], [[IF2]] ], [ 2, [[ELSE2]] ]
+; CHECK-NEXT:    [[J:%.*]] = phi i64 [ [[I]], [[IF2]] ], [ 0, [[ELSE2]] ]
 ; CHECK-NEXT:    [[GEP_J:%.*]] = getelementptr inbounds i32, ptr [[PTR]], i64 [[J]]
-; CHECK-NEXT:    ret i32 2
+; CHECK-NEXT:    ret i32 [[V]]
 ; CHECK:       else:
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i64 [[I]], 0
 ; CHECK-NEXT:    call void @llvm.assume(i1 [[CMP]])
 ; CHECK-NEXT:    [[GEP_I:%.*]] = getelementptr inbounds i32, ptr [[PTR]], i64 [[I]]
 ; CHECK-NEXT:    ret i32 0
 ;
 entry:
   %ptr = alloca [2 x i32]