[GVN] Refactor findDominatingLoad function

[kachkov98]

Summary

Improve findDominatingLoad implementation:

1. Result is saved into gvn::AvailableValue struct
2. Search is done in extended BB (while there is a single predecessor or limit is reached)

[kachkov98]

Rebase
Split pre-commit test

[nikic]

llvm/lib/Transforms/Scalar/GVN.cpp

201

clobbered

1128

Can you please add a test where the loads have the same size but different types? I think you need to compare pointer and type here, not location.

llvm/test/Transforms/GVN/PRE/pre-load-through-select.ll

80

Precommit test please.

[kachkov98]

Check that load types are matched (add negative test for that)

[kachkov98]

llvm/lib/Transforms/Scalar/GVN.cpp

1128

Added check that types are the same, in future cast instruction can be generated for such cases (there is also posibility to generate shift + truncate if found load has bigger memory location that is fully covering the needed MemLoc). Memory location instead of pointer value is used to refine clobber check with TBAA (location also stores AA tags)

[nikic]

LGTM

llvm/lib/Transforms/Scalar/GVN.cpp

1125

It would be better to create a BatchAAResults instance before the loop.

[kachkov98]

Thank you for the reviews!

[uabelho]

llvm/lib/Transforms/Scalar/GVN.cpp

1123

This limit and the fact that we iterate over all instructions in the BB (including debug instructions/intrinsics) unfortunately makes GVN behave in different ways depending on if we have debug information present or not.

This can be seen with
opt "-passes=gvn" bbi-86242.ll -S -o -

bbi-86242.ll15 KBDownload

If we remove the debug intrinsics from the input we see that GVN does more changes than with the debug stuff present
(the input can probably be reduced a lot if we pass -gvn-max-num-visited-insts=<something small> to opt).

[kachkov98]

llvm/lib/Transforms/Scalar/GVN.cpp

1123

Thank you for the report! I've created PR to fix it: https://github.com/llvm/llvm-project/pull/65977

llvm/lib/Transforms/Scalar/GVN.cpp

 
 // This is based on IsValueFullyAvailableInBlockNumSpeculationsMax stat.
 static cl::opt<uint32_t> MaxBBSpeculations(
     "gvn-max-block-speculations", cl::Hidden, cl::init(600),
     cl::desc("Max number of blocks we're willing to speculate on (and recurse "
              "into) when deducing if a value is fully available or not in GVN "
              "(default = 600)"));
 
+static cl::opt<uint32_t> MaxNumVisitedInsts(
+    "gvn-max-num-visited-insts", cl::Hidden, cl::init(100),
+    cl::desc("Max number of visited instructions when trying to find "
+             "dominating value of select dependency (default = 100)"));
+
 struct llvm::GVNPass::Expression {
   uint32_t opcode;
   bool commutative = false;
   // The type is not necessarily the result type of the expression, it may be
   // any additional type needed to disambiguate the expression.
   Type *type = nullptr;
   SmallVector<uint32_t, 4> varargs;
 
struct llvm::gvn::AvailableValue {
 
   /// Val - The value that is live out of the block.
   Value *Val;
   /// Kind of the live-out value.
   ValType Kind;
 
   /// Offset - The byte offset in Val that is interesting for the load query.
   unsigned Offset = 0;
+  /// V1, V2 - The dominating non-cloberred values of SelectVal.
+  Value *V1 = nullptr, *V2 = nullptr;
 
   static AvailableValue get(Value *V, unsigned Offset = 0) {
     AvailableValue Res;
     Res.Val = V;
     Res.Kind = ValType::SimpleVal;
     Res.Offset = Offset;
     return Res;
   }
struct llvm::gvn::AvailableValue {
   static AvailableValue getUndef() {
     AvailableValue Res;
     Res.Val = nullptr;
     Res.Kind = ValType::UndefVal;
     Res.Offset = 0;
     return Res;
   }
 
-  static AvailableValue getSelect(SelectInst *Sel) {
+  static AvailableValue getSelect(SelectInst *Sel, Value *V1, Value *V2) {
     AvailableValue Res;
     Res.Val = Sel;
     Res.Kind = ValType::SelectVal;
     Res.Offset = 0;
+    Res.V1 = V1;
+    Res.V2 = V2;
     return Res;
   }
 
   bool isSimpleValue() const { return Kind == ValType::SimpleVal; }
   bool isCoercedLoadValue() const { return Kind == ValType::LoadVal; }
   bool isMemIntrinValue() const { return Kind == ValType::MemIntrin; }
   bool isUndefValue() const { return Kind == ValType::UndefVal; }
   bool isSelectValue() const { return Kind == ValType::SelectVal; }
static AvailableValueInBlock get(BasicBlock *BB, Value *V,
                                    unsigned Offset = 0) {
     return get(BB, AvailableValue::get(V, Offset));
   }
 
   static AvailableValueInBlock getUndef(BasicBlock *BB) {
     return get(BB, AvailableValue::getUndef());
   }
 
-  static AvailableValueInBlock getSelect(BasicBlock *BB, SelectInst *Sel) {
-    return get(BB, AvailableValue::getSelect(Sel));
+  static AvailableValueInBlock getSelect(BasicBlock *BB, SelectInst *Sel,
+                                         Value *V1, Value *V2) {
+    return get(BB, AvailableValue::getSelect(Sel, V1, V2));
   }
 
   /// Emit code at the end of this block to adjust the value defined here to
   /// the specified type. This handles various coercion cases.
   Value *MaterializeAdjustedValue(LoadInst *Load, GVNPass &gvn) const {
     return AV.MaterializeAdjustedValue(Load, BB->getTerminator(), gvn);
   }
 };
for (const AvailableValueInBlock &AV : ValuesPerBlock) {
 
     SSAUpdate.AddAvailableValue(BB, AV.MaterializeAdjustedValue(Load, gvn));
   }
 
   // Perform PHI construction.
   return SSAUpdate.GetValueInMiddleOfBlock(Load->getParent());
 }
 
-static LoadInst *findDominatingLoad(Value *Ptr, Type *LoadTy, SelectInst *Sel,
-                                    DominatorTree &DT) {
-  for (Value *U : Ptr->users()) {
-    auto *LI = dyn_cast<LoadInst>(U);
-    if (LI && LI->getType() == LoadTy && LI->getParent() == Sel->getParent() &&
-        DT.dominates(LI, Sel))
-      return LI;
-  }
-  return nullptr;
-}
-
 Value *AvailableValue::MaterializeAdjustedValue(LoadInst *Load,
                                                 Instruction *InsertPt,
                                                 GVNPass &gvn) const {
   Value *Res;
   Type *LoadTy = Load->getType();
   const DataLayout &DL = Load->getModule()->getDataLayout();
   if (isSimpleValue()) {
     Res = getSimpleValue();
Res = getMemInstValueForLoad(getMemIntrinValue(), Offset, LoadTy,
                                  InsertPt, DL);
     LLVM_DEBUG(dbgs() << "GVN COERCED NONLOCAL MEM INTRIN:\nOffset: " << Offset
                       << "  " << *getMemIntrinValue() << '\n'
                       << *Res << '\n'
                       << "\n\n\n");
   } else if (isSelectValue()) {
     // Introduce a new value select for a load from an eligible pointer select.
     SelectInst *Sel = getSelectValue();
-    LoadInst *L1 = findDominatingLoad(Sel->getOperand(1), LoadTy, Sel,
-                                      gvn.getDominatorTree());
-    LoadInst *L2 = findDominatingLoad(Sel->getOperand(2), LoadTy, Sel,
-                                      gvn.getDominatorTree());
-    assert(L1 && L2 &&
-           "must be able to obtain dominating loads for both value operands of "
-           "the select");
-    Res = SelectInst::Create(Sel->getCondition(), L1, L2, "", Sel);
+    assert(V1 && V2 && "both value operands of the select must be present");
+    Res = SelectInst::Create(Sel->getCondition(), V1, V2, "", Sel);
   } else {
     llvm_unreachable("Should not materialize value from dead block");
   }
   assert(Res && "failed to materialize?");
   return Res;
 }
 
 static bool isLifetimeStart(const Instruction *Inst) {
static void reportMayClobberedLoad(LoadInst *Load, MemDepResult DepInfo,
   if (OtherAccess)
     R << " in favor of " << NV("OtherAccess", OtherAccess);
 
   R << " because it is clobbered by " << NV("ClobberedBy", DepInfo.getInst());
 
   ORE->emit(R);
 }
 
-/// Check if a load from pointer-select \p Address in \p DepBB can be converted
-/// to a value select. The following conditions need to be satisfied:
-/// 1. The pointer select (\p Address) must be defined in \p DepBB.
-/// 2. Both value operands of the pointer select must be loaded in the same
-/// basic block, before the pointer select.
-/// 3. There must be no instructions between the found loads and \p End that may
-/// clobber the loads.
-static std::optional<AvailableValue>
-tryToConvertLoadOfPtrSelect(SelectInst *Sel, Type *LoadTy, DominatorTree &DT,
+// Find non-clobbered value for Loc memory location in extended basic block
+// (chain of basic blocks with single predecessors) starting From instruction.
+static Value *findDominatingValue(const MemoryLocation &Loc, Instruction *From,
                                   AAResults *AA) {
-  LoadInst *L1 = findDominatingLoad(Sel->getOperand(1), LoadTy, Sel, DT);
-  LoadInst *L2 = findDominatingLoad(Sel->getOperand(2), LoadTy, Sel, DT);
-  if (!L1 || !L2)
-    return std::nullopt;
-
-  // Ensure there are no accesses that may modify the locations referenced by
-  // either L1 or L2 between L1, L2 and the specified End iterator.
-  Instruction *EarlierLoad = L1->comesBefore(L2) ? L1 : L2;
-  MemoryLocation L1Loc = MemoryLocation::get(L1);
-  MemoryLocation L2Loc = MemoryLocation::get(L2);
-  if (any_of(make_range(EarlierLoad->getIterator(), Sel->getIterator()),
-             [&](Instruction &I) {
-               return isModSet(AA->getModRefInfo(&I, L1Loc)) ||
-                      isModSet(AA->getModRefInfo(&I, L2Loc));
-             }))
-    return std::nullopt;
-
-  return AvailableValue::getSelect(Sel);
+  uint32_t NumVisitedInsts = 0;
+  BasicBlock *FromBB = From->getParent();
+  for (BasicBlock *BB = FromBB; BB; BB = BB->getSinglePredecessor())
+    for (auto I = BB == FromBB ? From->getReverseIterator() : BB->rbegin(),
+              E = BB->rend();
+         I != E; ++I) {
+      // Stop the search if limit is reached.
+      if (++NumVisitedInsts > MaxNumVisitedInsts)
+        return nullptr;
+      Instruction *Inst = &*I;
+      if (isModSet(AA->getModRefInfo(Inst, Loc)))
+        return nullptr;
+      if (auto *LI = dyn_cast<LoadInst>(Inst))
+        if (MemoryLocation::get(LI) == Loc)
+          return LI;
+    }
+  return nullptr;
 }
 
 std::optional<AvailableValue>
 GVNPass::AnalyzeLoadAvailability(LoadInst *Load, MemDepResult DepInfo,
                                  Value *Address) {
   assert(Load->isUnordered() && "rules below are incorrect for ordered access");
   assert(DepInfo.isLocal() && "expected a local dependence");
 
   Instruction *DepInst = DepInfo.getInst();
   if (DepInfo.isSelect()) {
     // Check if load with Addr dependent from select can be converted to select
     // between load values. There must be no instructions between the found
     // loads and DepInst that may clobber the loads.
     assert(isa<SelectInst>(DepInst) && "Dependency must be select instruction");
     auto *Sel = cast<SelectInst>(DepInst);
-    return tryToConvertLoadOfPtrSelect(Sel, Load->getType(), getDominatorTree(),
-                                       getAliasAnalysis());
+    assert(Sel->getType() == Load->getPointerOperandType());
+    auto Loc = MemoryLocation::get(Load);
+    Value *V1 = findDominatingValue(Loc.getWithNewPtr(Sel->getTrueValue()),
+                                    DepInst, getAliasAnalysis());
+    if (!V1)
+      return std::nullopt;
+    Value *V2 = findDominatingValue(Loc.getWithNewPtr(Sel->getFalseValue()),
+                                    DepInst, getAliasAnalysis());
+    if (!V2)
+      return std::nullopt;
+    return AvailableValue::getSelect(Sel, V1, V2);
   }
 
   const DataLayout &DL = Load->getModule()->getDataLayout();
   if (DepInfo.isClobber()) {
     // If the dependence is to a store that writes to a superset of the bits
     // read by the load, we can extract the bits we need for the load from the
     // stored value.
     if (StoreInst *DepSI = dyn_cast<StoreInst>(DepInst)) {

llvm/test/Transforms/GVN/PRE/pre-load-through-select.ll

else:
   br label %exit
 
 exit:
   %p = phi ptr [ %min.select, %then ], [ %a, %else ]
   %res.2 = load i32, ptr %p, align 4
   ret i32 %res.2
 }
 
+define i32 @test_pointer_phi_select_simp_non_local(ptr %a, ptr %b)  {
+; CHECK-LABEL: @test_pointer_phi_select_simp_non_local(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[L_1:%.*]] = load i32, ptr [[A:%.*]], align 4
+; CHECK-NEXT:    [[COND:%.*]] = icmp sgt i32 [[L_1]], 0
+; CHECK-NEXT:    br i1 [[COND]], label [[THEN:%.*]], label [[ELSE:%.*]]
+; CHECK:       then:
+; CHECK-NEXT:    [[L_2:%.*]] = load i32, ptr [[B:%.*]], align 4
+; CHECK-NEXT:    [[CMP_I_I_I:%.*]] = icmp ult i32 [[L_1]], [[L_2]]
+; CHECK-NEXT:    [[TMP0:%.*]] = select i1 [[CMP_I_I_I]], i32 [[L_1]], i32 [[L_2]]
+; CHECK-NEXT:    [[MIN_SELECT:%.*]] = select i1 [[CMP_I_I_I]], ptr [[A]], ptr [[B]]
+; CHECK-NEXT:    br label [[EXIT:%.*]]
+; CHECK:       else:
+; CHECK-NEXT:    br label [[EXIT]]
+; CHECK:       exit:
+; CHECK-NEXT:    [[RES_2:%.*]] = phi i32 [ [[TMP0]], [[THEN]] ], [ [[L_1]], [[ELSE]] ]
+; CHECK-NEXT:    [[P:%.*]] = phi ptr [ [[MIN_SELECT]], [[THEN]] ], [ [[A]], [[ELSE]] ]
+; CHECK-NEXT:    ret i32 [[RES_2]]
+;
+entry:
+  %l.1 = load i32, ptr %a, align 4
+  %cond = icmp sgt i32 %l.1, 0
+  br i1 %cond, label %then, label %else
+
+then:
+  %l.2 = load i32, ptr %b, align 4
+  %cmp.i.i.i = icmp ult i32 %l.1, %l.2
+  %min.select  = select i1 %cmp.i.i.i, ptr %a, ptr %b
+  br label %exit
+
+else:
+  br label %exit
+
+exit:
+  %p = phi ptr [ %min.select, %then ], [ %a, %else ]
+  %res.2 = load i32, ptr %p, align 4
+  ret i32 %res.2
+}
+
 define i32 @test_pointer_phi_select_simp_no_load_for_select_op_1(ptr %a, ptr %b, ptr %c, i1 %cond)  {
 ; CHECK-LABEL: @test_pointer_phi_select_simp_no_load_for_select_op_1(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br i1 [[COND:%.*]], label [[THEN:%.*]], label [[ELSE:%.*]]
 ; CHECK:       then:
 ; CHECK-NEXT:    [[L_1:%.*]] = load i32, ptr [[C:%.*]], align 4
 ; CHECK-NEXT:    [[L_2:%.*]] = load i32, ptr [[B:%.*]], align 4
 ; CHECK-NEXT:    [[CMP_I_I_I:%.*]] = icmp ult i32 [[L_1]], [[L_2]]