[GVN] Do PHI translations across all edges between the load and the unavailable pred.

[fhahn]

Summary

Currently we do not properly translate addresses with PHIs if LoadBB !=
LI->getParent(), because PHITranslateAddr expects a direct predecessor as argument,
because it considers all instructions outside of the current block to
not requiring translation.

The amount of cases that trigger this should be very low, as most single
predecessor blocks should be folded into their predecessor by GVN before
we actually start with value numbering. It is still not guaranteed to
happen, so we should do PHI translation along all edges between the
loads' block and the predecessor where we have to place a load.

There are a few test cases showing current limits of the PHI translation, which
could be improved later.

[fhahn]

ping

[fhahn]

ping

[efriedma]

Given that each block only has a single predecessor, there aren't any PHI nodes involved. In that case, what does PHITranslateWithInsertion actually do?

llvm/lib/Transforms/Scalar/GVN.cpp

1207

I don't see any explanation for this change?

[fhahn]

In D65020#1630448, @efriedma wrote:

Given that each block only has a single predecessor, there aren't any PHI nodes involved. In that case, what does PHITranslateWithInsertion actually do?

I think this is related to how PHITranslateAddr does the translation: it only translates along CFG edges. When called with (%input, %BB, %PredBB), it tries to generate a value that represents %input in %PredBB. If %input (or any of its operands) are not defined in %BB, there is nothing to translate for this edge (they must also be available in the predecessor) and it will return the untranslated version of the input. This is the problem we hit in phi_trans6, if we would just call it with (%gep.1, %header, %latch).

llvm/lib/Transforms/Scalar/GVN.cpp

1207

markInstructionForDeletion asserts that the removed instructions are defined in the current basic block.

But PHI translation may insert instructions in any of the basic blocks traversed during translation. If that happens and translation fails, we have to remove instructions from different basic blocks than the current one. I thought it is best to directly remove them (no other parts of GVN have seen them yet and they are not numbered yet).

I can update the comment to make that clearer.

[efriedma]

llvm/lib/Transforms/Scalar/GVN.cpp

1207

That makes sense. Please update the comment to at least mention the cross-BB issue.

[fhahn]

Update comment about deleting instructions directly. also run clang-format-diff.

[fhahn]

llvm/lib/Transforms/Scalar/GVN.cpp

1207

Thanks, I've updated the comment. I hope it is clearer now.

[fhahn]

ping. Eli, are you happy with the latest version, with the updated comment?

[efriedma]

LGTM

llvm/lib/Transforms/Scalar/GVN.cpp

bool GVN::PerformLoadPRE(LoadInst *LI, AvailValInBlkVect &ValuesPerBlock,
   bool CanDoPRE = true;
   const DataLayout &DL = LI->getModule()->getDataLayout();
   SmallVector<Instruction*, 8> NewInsts;
   for (auto &PredLoad : PredLoads) {
     BasicBlock *UnavailablePred = PredLoad.first;
 
     // Do PHI translation to get its value in the predecessor if necessary.  The
     // returned pointer (if non-null) is guaranteed to dominate UnavailablePred.
+    // We do the translation for each edge we skipped by going from LI's block
+    // to LoadBB, otherwise we might miss pieces needing translation.
 
     // If all preds have a single successor, then we know it is safe to insert
     // the load on the pred (?!?), so we can insert code to materialize the
     // pointer if it is not available.
-    PHITransAddr Address(LI->getPointerOperand(), DL, AC);
-    Value *LoadPtr = nullptr;
-    LoadPtr = Address.PHITranslateWithInsertion(LoadBB, UnavailablePred,
-                                                *DT, NewInsts);
+    Value *LoadPtr = LI->getPointerOperand();
+    BasicBlock *Cur = LI->getParent();
+    while (Cur != LoadBB) {
+      PHITransAddr Address(LoadPtr, DL, AC);
+      LoadPtr = Address.PHITranslateWithInsertion(
+          Cur, Cur->getSinglePredecessor(), *DT, NewInsts);
+      if (!LoadPtr) {
+        CanDoPRE = false;
+        break;
+      }
+      Cur = Cur->getSinglePredecessor();
+    }
 
+    if (LoadPtr) {
+      PHITransAddr Address(LoadPtr, DL, AC);
+      LoadPtr = Address.PHITranslateWithInsertion(LoadBB, UnavailablePred, *DT,
+                                                  NewInsts);
+    }
     // If we couldn't find or insert a computation of this phi translated value,
     // we fail PRE.
     if (!LoadPtr) {
       LLVM_DEBUG(dbgs() << "COULDN'T INSERT PHI TRANSLATED VALUE OF: "
                         << *LI->getPointerOperand() << "\n");
       CanDoPRE = false;
       break;
     }
 
     PredLoad.second = LoadPtr;
   }
 
   if (!CanDoPRE) {
     while (!NewInsts.empty()) {
-      Instruction *I = NewInsts.pop_back_val();
-      markInstructionForDeletion(I);
+      // Erase instructions generated by the failed PHI translation before
+      // trying to number them. PHI translation might insert instructions
+      // in basic blocks other than the current one, and we delete them
+      // directly, as markInstructionForDeletion only allows removing from the
+      // current basic block.
+      NewInsts.pop_back_val()->eraseFromParent();
     }
     // HINT: Don't revert the edge-splitting as following transformation may
     // also need to split these critical edges.
     return !CriticalEdgePred.empty();
   }
 
   // Okay, we can eliminate this load by inserting a reload in the predecessor
   // and using PHI construction to get the value in the other predecessors, do

llvm/test/Transforms/GVN/PRE/rle.ll

 ; CHECK-NEXT: load i8, i8*
   br label %loop
   
 out:
   %R = add i8 %Y, %Y2
   ret i8 %R
 }
 
+declare void @use_i32(i32) readonly
+
+; indirectbr currently prevents MergeBlockIntoPredecessor from merging latch
+; into header. Make sure we translate the address for %l1 correctly where
+; parts of the address computations are in different basic blocks.
+define i32 @phi_trans6(i32* noalias nocapture readonly %x, i1 %cond) {
+; CHECK-LABEL: define i32 @phi_trans6(
+; CHECK-LABEL: entry:
+; CHECK-NEXT:   %l0 = load i32, i32* %x
+;
+; CHECK-LABEL: header:
+; CHECK-NEXT:    %l1 = phi i32 [ %l0, %entry ], [ %l1.pre, %latch.header_crit_edge ]
+; CHECK-NEXT:    %iv = phi i32 [ 0, %entry ], [ %iv.next, %latch.header_crit_edge ]
+; CHECK-NEXT:    indirectbr i8* blockaddress(@phi_trans6, %latch), [label %latch]
+;
+; CHECK-LABEL: latch:
+; CHECK-NEXT:    %iv.next = add i32 %iv, 1
+; CHECK-NEXT:    br i1 %cond, label %exit, label %latch.header_crit_edge
+;
+; CHECK-LABEL: latch.header_crit_edge:
+; CHECK-NEXT:    %gep.1.phi.trans.insert.phi.trans.insert = getelementptr i32, i32* %x, i32 %iv.next
+; CHECK-NEXT:    %l1.pre = load i32, i32* %gep.1.phi.trans.insert.phi.trans.insert
+; CHECK-LABEL:   br label %header
+;
+entry:
+  %l0 = load i32, i32* %x
+  call void @use_i32(i32 %l0)
+  br label %header
+
+header:
+  %iv = phi i32 [0, %entry], [ %iv.next, %latch]
+  indirectbr i8* blockaddress(@phi_trans6, %latch), [label %latch]
+
+latch:
+  %gep.1 = getelementptr i32, i32* %x, i32 %iv
+  %l1 = load i32, i32* %gep.1
+  %iv.next = add i32 %iv, 1
+  br i1 %cond, label %exit, label %header
+
+exit:
+  ret i32 %l1
+}
+
+; FIXME: Currently we fail to translate the PHI in this case.
+define i32 @phi_trans7(i32* noalias nocapture readonly %x, i1 %cond) {
+; CHECK-LABEL: define i32 @phi_trans7(
+; CHECK-LABEL: entry:
+; CHECK-NEXT:   %l0 = load i32, i32* %x
+;
+; CHECK-LABEL: header:
+; CHECK-NEXT:    %iv = phi i32 [ 2, %entry ], [ %iv.next, %latch.header_crit_edge ]
+; CHECK-NEXT:    %offset = add i32 %iv, -2
+; CHECK-NEXT:    indirectbr i8* blockaddress(@phi_trans7, %latch), [label %latch]
+;
+; CHECK-LABEL: latch:
+; CHECK-NEXT:    %gep.1 = getelementptr i32, i32* %x, i32 %offset
+; CHECK-NEXT:    %l1 = load i32, i32* %gep.1
+; CHECK-NEXT:    %iv.next = add i32 %iv, 1
+; CHECK-NEXT:    br i1 %cond, label %exit, label %latch.header_crit_edge
+;
+; CHECK-LABEL: latch.header_crit_edge:
+; CHECK-LABEL:   br label %header
+;
+entry:
+  %l0 = load i32, i32* %x
+  call void @use_i32(i32 %l0)
+  br label %header
+
+header:
+  %iv = phi i32 [2, %entry], [ %iv.next, %latch]
+  %offset = add i32 %iv, -2
+  indirectbr i8* blockaddress(@phi_trans7, %latch), [label %latch]
+
+latch:
+  %gep.1 = getelementptr i32, i32* %x, i32 %offset
+  %l1 = load i32, i32* %gep.1
+  %iv.next = add i32 %iv, 1
+  br i1 %cond, label %exit, label %header
+
+exit:
+  ret i32 %l1
+}
+
+; FIXME: Currently we fail to translate the PHI in this case.
+define i32 @phi_trans8(i32* noalias nocapture readonly %x, i1 %cond) {
+; CHECK-LABEL: define i32 @phi_trans8(
+; CHECK-LABEL: entry:
+; CHECK-NEXT:   %l0 = load i32, i32* %x
+;
+; CHECK-LABEL: header:
+; CHECK-NEXT:    %iv = phi i32 [ 2, %entry ], [ %iv.next, %latch.header_crit_edge ]
+; CHECK-NEXT:    indirectbr i8* blockaddress(@phi_trans8, %latch), [label %latch]
+;
+; CHECK-LABEL: latch:
+; CHECK-NEXT:    %offset = add i32 %iv, -2
+; CHECK-NEXT:    %gep.1 = getelementptr i32, i32* %x, i32 %offset
+; CHECK-NEXT:    %l1 = load i32, i32* %gep.1
+; CHECK-NEXT:    %iv.next = add i32 %iv, 1
+; CHECK-NEXT:    br i1 %cond, label %exit, label %latch.header_crit_edge
+;
+; CHECK-LABEL: latch.header_crit_edge:
+; CHECK-LABEL:   br label %header
+;
+entry:
+  %l0 = load i32, i32* %x
+  call void @use_i32(i32 %l0)
+  br label %header
+
+header:
+  %iv = phi i32 [2, %entry], [ %iv.next, %latch]
+  indirectbr i8* blockaddress(@phi_trans8, %latch), [label %latch]
+
+latch:
+  %offset = add i32 %iv, -2
+  %gep.1 = getelementptr i32, i32* %x, i32 %offset
+  %l1 = load i32, i32* %gep.1
+  %iv.next = add i32 %iv, 1
+  br i1 %cond, label %exit, label %header
+
+exit:
+  ret i32 %l1
+}
+
+
 
 ; PR6642
 define i32 @memset_to_load() nounwind readnone {
 entry:
   %x = alloca [256 x i32], align 4                ; <[256 x i32]*> [#uses=2]
   %tmp = bitcast [256 x i32]* %x to i8*           ; <i8*> [#uses=1]
   call void @llvm.memset.p0i8.i64(i8* align 4 %tmp, i8 0, i64 1024, i1 false)
   %arraydecay = getelementptr inbounds [256 x i32], [256 x i32]* %x, i32 0, i32 0 ; <i32*>

 ; CHECK: load i8, i8*
 ; CHECK: load i8, i8*
 ; CHECK: load i8, i8*
 ; CHECK: load i8, i8*
 ; CHECK-NOT: load
 ; CHECK: ret i32
 }
 
+
 declare void @llvm.memset.p0i8.i64(i8* nocapture, i8, i64, i1) nounwind
 
 declare void @llvm.memcpy.p0i8.p0i8.i64(i8* nocapture, i8* nocapture, i64, i1) nounwind
 declare void @llvm.memcpy.p0i8.p1i8.i64(i8* nocapture, i8 addrspace(1)* nocapture, i64, i1) nounwind
 
 
 ;;===----------------------------------------------------------------------===;;
 ;; Load -> Store dependency which isn't interfered with by a call that happens