[GVN] Simple GVNHoist - limits

[chill]

Summary

This patch adds a parameter limiting how deep in a block we go looking
for instructions to hoist.

It also prevents certain instructions from initiating the hoist of a
dependency chain with the goal to not separate them from their
users. Such instructions are:

• GEPs, with the intent to keep them together with the (comparatively harder to hoist) loads/stores

• binary ops, which are converted to boolean by comparing them to zero: often the result of comparison to zero is (or can be chosen to be) a side effect from the original computation

• conditions to br and select instructions

Nevertheless, such instructions can be hoisted, if the process starts
from their users.

[junparser]

Would it better use some parameter from GVNHoist? Also I do think maybe the default value is too large.

[chill]

In D111418#3054542, @junparser wrote:

Would it better use some parameter from GVNHoist? Also I do think maybe the default value is too large.

I wanted to be independent from GVNHoist.cpp, e.g. choose different defaults. Indeed, defaults may well be large, I'm going to look
at various benchmarks and defaults' effect on them, and maybe change the defaults.

[junparser]

LGTM

[chill]

• Removed the maximum chain length limit as the current implementation does not iterate and does not need renumbering as the original GVNHoist
• Spent some effort to not separate certain instructions from their users (that's an outcome from some tuning/regression fixing with various benchmarks).

llvm/include/llvm/Transforms/Scalar/GVN.h

private:
   bool performScalarPREInsertion(Instruction *Instr, BasicBlock *Pred,
                                  BasicBlock *Curr, unsigned int ValNo);
   bool performHoist(Function &F);
   void collectHoistCandidates(BasicBlock *ThenBB);
   void matchHoistCandidates(BasicBlock *ElseBB);
   void replaceInstruction(Instruction *I, Instruction *Repl);
   std::pair<bool, bool> hoistPair(BasicBlock *DestBB, BasicBlock *ThenBB,
                                   BasicBlock *ElseBB, Instruction *ThenI,
-                                  Instruction *ElseI);
+                                  Instruction *ElseI, uint32_t DepLength);
   Value *findLeader(const BasicBlock *BB, uint32_t num);
   void cleanupGlobalSets();
   void verifyRemoved(const Instruction *I) const;
   bool splitCriticalEdges();
   BasicBlock *splitCriticalEdges(BasicBlock *Pred, BasicBlock *Succ);
   bool replaceOperandsForInBlockEquality(Instruction *I) const;
   bool propagateEquality(Value *LHS, Value *RHS, const BasicBlockEdge &Root,
                          bool DominatesByEdge);

llvm/lib/Transforms/Scalar/GVN.cpp

 static cl::opt<uint32_t> MaxBBSpeculations(
     "gvn-max-block-speculations", cl::Hidden, cl::init(600), cl::ZeroOrMore,
     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<bool> GVNEnableSimpleGVNHoist("enable-simple-gvn-hoist",
                                              cl::init(true));
+static cl::opt<uint32_t> MaxBlockDepth(
+    "simple-gvn-hoist-max-block-depth", cl::Hidden, cl::init(100),
+    cl::desc("Limit hoist candidates to the first N instructions in a block"));
+
+static cl::opt<uint32_t> MaxChainLength(
+    "simple-gvn-hoist-max-chain-length", cl::Hidden, cl::init(10),
+    cl::desc("Limit the length of dependency chains"));
 
 struct llvm::GVN::Expression {
   uint32_t opcode;
   bool commutative = false;
   Type *type = nullptr;
   SmallVector<uint32_t, 4> varargs;
 
   Expression(uint32_t o = ~2U) : opcode(o) {}
if (const auto *SA = dyn_cast<StoreInst>(&A)) {
     return SA->isVolatile() == SB->isVolatile() &&
            SA->getOrdering() == SB->getOrdering();
   }
 
   return true;
 }
 
 void GVN::collectHoistCandidates(BasicBlock *BB) {
+  uint32_t Depth = 0;
   bool HasHoistBarrier = false;
   for (Instruction &I : *BB) {
+    if (++Depth > MaxBlockDepth)
+      break;
     if (I.isTerminator())
       break;
     if (isa<PHINode>(I))
       continue;
 
     if (!HasHoistBarrier || isSafeToSpeculativelyExecute(&I))
       HoistPairs[VN.lookupOrAdd(&I)].first = &I;
 
     if ((HasHoistBarrier |= isHoistBarrier(I)))
       LLVM_DEBUG(dbgs() << "Simple GVNHoist: reached hoist barrier" << I
                         << '\n';);
   }
 }
 
 void GVN::matchHoistCandidates(BasicBlock *BB) {
+  uint32_t Depth = 0;
   bool HasHoistBarrier = false;
   for (Instruction &I : *BB) {
+    if (++Depth > MaxBlockDepth)
+      break;
     if (I.isTerminator())
       break;
     if (isa<PHINode>(I))
       continue;
 
     if (!HasHoistBarrier || isSafeToSpeculativelyExecute(&I)) {
       uint32_t N = VN.lookupOrAdd(&I);
       auto It = HoistPairs.find(N);
static bool defClobbersUse(AAResults *AA, Instruction *Def, Instruction *Use) {
   return DefLoc && UseLoc ? !AA->isNoAlias(*DefLoc, *UseLoc) : true;
 }
 
 // Only hoist instructions from the "then" block.
 // Each hoisted instructions must be paired with an instruction from the "else"
 // block.
 std::pair<bool, bool> GVN::hoistPair(BasicBlock *DestBB, BasicBlock *ThenBB,
                                      BasicBlock *ElseBB, Instruction *ThenI,
-                                     Instruction *ElseI) {
+                                     Instruction *ElseI, uint32_t DepLength) {
   // If the instruction is moved out of the "then" block there's nothing to do.
   if (ThenI->getParent() != ThenBB)
     return {false, false};
 
+  // Check if we have exceeded dependency chain length limit.
+  if (DepLength > MaxChainLength)
+    return {false, true};
+
   // Instruction must have already been selected for hoisting and matched with
   // another instruction.
   auto It = HoistPairs.find(VN.lookupOrAdd(ThenI));
   if (It == HoistPairs.end())
     return {false, true};
 
   assert((ElseI == nullptr || ElseI == It->second.second) &&
          "Attempt to hoist two not paired instructions.");
std::pair<bool, bool> GVN::hoistPair(BasicBlock *DestBB, BasicBlock *ThenBB,
   // instruction, then check all of the operands of the "else" instruction
   // dominate its block.
   for (unsigned I = 0, N = ThenI->getNumOperands(); I < N; ++I) {
     auto *Op = dyn_cast<Instruction>(ThenI->getOperand(I));
     if (Op == nullptr)
       continue;
     bool OpChange, CantHoist;
     std::tie(OpChange, CantHoist) =
-        hoistPair(DestBB, ThenBB, ElseBB, Op, nullptr);
+        hoistPair(DestBB, ThenBB, ElseBB, Op, nullptr, DepLength + 1);
     Change |= OpChange;
     if (CantHoist)
       return {Change, true};
   }
 
   for (unsigned I = 0, N = ElseI->getNumOperands(); I < N; ++I) {
     auto *Op = dyn_cast<Instruction>(ElseI->getOperand(I));
     if (Op == nullptr)
       continue;
     if (Op->getParent() == ElseBB)
       return {Change, true};
   }
 
   // Do the same for memory dependencies.
   if (ThenI->mayReadOrWriteMemory()) {
     // Hoist preceding aliased MemoryDefs.
     auto *MSSA = MSSAU->getMemorySSA();
     auto *Walker = MSSA->getSkipSelfWalker();
     MemoryAccess *ThenMA = Walker->getClobberingMemoryAccess(ThenI);
     while (!MSSA->isLiveOnEntryDef(ThenMA) && ThenMA->getBlock() == ThenBB) {
       bool DepChange, CantHoist;
-      std::tie(DepChange, CantHoist) =
-          hoistPair(DestBB, ThenBB, ElseBB,
-                    cast<MemoryDef>(ThenMA)->getMemoryInst(), nullptr);
+      std::tie(DepChange, CantHoist) = hoistPair(
+          DestBB, ThenBB, ElseBB, cast<MemoryDef>(ThenMA)->getMemoryInst(),
+          nullptr, DepLength + 1);
       Change |= DepChange;
       if (CantHoist)
         return {Change, true};
       ThenMA = Walker->getClobberingMemoryAccess(ThenI);
     }
 
     MemoryAccess *ElseMA = Walker->getClobberingMemoryAccess(ElseI);
     if (!MSSA->isLiveOnEntryDef(ElseMA) && ElseMA->getBlock() == ElseBB)
if (const auto *Def = dyn_cast<MemoryDef>(MSSA->getMemoryAccess(ThenI))) {
           MemoryUses.push_back(U);
         }
       }
 
       // ... then try to hoist them.
       for (Instruction *I : MemoryUses) {
         bool DepChange, CantHoist;
         std::tie(DepChange, CantHoist) =
-            hoistPair(DestBB, ThenBB, ElseBB, I, nullptr);
+            hoistPair(DestBB, ThenBB, ElseBB, I, nullptr, DepLength + 1);
         Change |= DepChange;
         if (CantHoist)
           return {Change, true};
       }
 
       // None should have remained in the "else" block.
       Def = cast<MemoryDef>(MSSA->getMemoryAccess(ElseI));
       for (const MemoryAccess &MA : *MSSA->getBlockAccesses(ElseBB)) {
for (BasicBlock *BB : RPOT) {
 
     HoistPairs.clear();
     collectHoistCandidates(Then);
     matchHoistCandidates(Else);
 
     // Hoist matched pairs.
     for (const auto &P : HoistPairs) {
       bool LocalChange, _;
-      std::tie(LocalChange, _) =
-          hoistPair(BB, Then, Else, P.second.first, P.second.second);
+      Instruction *ThenI = P.second.first, *ElseI = P.second.second;
+      // Don't initiate hoisting from GEPs (they still can be hoisted by their
+      // users).
+      if (isa<GetElementPtrInst>(ThenI))
+        continue;
+      std::tie(LocalChange, _) = hoistPair(BB, Then, Else, ThenI, ElseI, 0);
       Change |= LocalChange;
     }
   }
 
   return Change;
 }
 
 class llvm::gvn::GVNLegacyPass : public FunctionPass {

llvm/test/Transforms/PhaseOrdering/AArch64/hoisting-sinking-required-for-vectorization.ll

 ; CHECK-NEXT:    [[BROADCAST_SPLAT:%.*]] = shufflevector <4 x float> [[BROADCAST_SPLATINSERT]], <4 x float> poison, <4 x i32> zeroinitializer
 ; CHECK-NEXT:    br label [[VECTOR_BODY:%.*]]
 ; CHECK:       vector.body:
 ; CHECK-NEXT:    [[INDEX:%.*]] = phi i64 [ 0, [[VECTOR_PH]] ], [ [[INDEX_NEXT:%.*]], [[VECTOR_BODY]] ]
 ; CHECK-NEXT:    [[TMP2:%.*]] = getelementptr inbounds i32, i32* [[C]], i64 [[INDEX]]
 ; CHECK-NEXT:    [[TMP3:%.*]] = bitcast i32* [[TMP2]] to <4 x i32>*
 ; CHECK-NEXT:    [[WIDE_LOAD:%.*]] = load <4 x i32>, <4 x i32>* [[TMP3]], align 4, !alias.scope !8
 ; CHECK-NEXT:    [[TMP4:%.*]] = icmp eq <4 x i32> [[WIDE_LOAD]], <i32 20, i32 20, i32 20, i32 20>
-; CHECK-NEXT:    [[TMP5:%.*]] = getelementptr inbounds float, float* [[B]], i64 [[INDEX]]
-; CHECK-NEXT:    [[TMP6:%.*]] = getelementptr inbounds float, float* [[A]], i64 [[INDEX]]
-; CHECK-NEXT:    [[TMP7:%.*]] = bitcast float* [[TMP6]] to <4 x float>*
-; CHECK-NEXT:    [[WIDE_LOAD14:%.*]] = load <4 x float>, <4 x float>* [[TMP7]], align 4, !alias.scope !11
-; CHECK-NEXT:    [[TMP8:%.*]] = fmul <4 x float> [[WIDE_LOAD14]], [[BROADCAST_SPLAT]]
-; CHECK-NEXT:    [[TMP9:%.*]] = bitcast float* [[TMP5]] to <4 x float>*
+; CHECK-NEXT:    [[TMP5:%.*]] = getelementptr inbounds float, float* [[A]], i64 [[INDEX]]
+; CHECK-NEXT:    [[TMP6:%.*]] = bitcast float* [[TMP5]] to <4 x float>*
+; CHECK-NEXT:    [[WIDE_LOAD14:%.*]] = load <4 x float>, <4 x float>* [[TMP6]], align 4, !alias.scope !11
+; CHECK-NEXT:    [[TMP7:%.*]] = fmul <4 x float> [[WIDE_LOAD14]], [[BROADCAST_SPLAT]]
+; CHECK-NEXT:    [[TMP8:%.*]] = getelementptr inbounds float, float* [[B]], i64 [[INDEX]]
+; CHECK-NEXT:    [[TMP9:%.*]] = bitcast float* [[TMP8]] to <4 x float>*
 ; CHECK-NEXT:    [[WIDE_LOAD15:%.*]] = load <4 x float>, <4 x float>* [[TMP9]], align 4, !alias.scope !13, !noalias !15
-; CHECK-NEXT:    [[TMP10:%.*]] = fadd <4 x float> [[TMP8]], [[WIDE_LOAD15]]
-; CHECK-NEXT:    [[PREDPHI:%.*]] = select <4 x i1> [[TMP4]], <4 x float> [[TMP8]], <4 x float> [[TMP10]]
-; CHECK-NEXT:    [[TMP11:%.*]] = bitcast float* [[TMP5]] to <4 x float>*
+; CHECK-NEXT:    [[TMP10:%.*]] = fadd <4 x float> [[TMP7]], [[WIDE_LOAD15]]
+; CHECK-NEXT:    [[PREDPHI:%.*]] = select <4 x i1> [[TMP4]], <4 x float> [[TMP7]], <4 x float> [[TMP10]]
+; CHECK-NEXT:    [[TMP11:%.*]] = bitcast float* [[TMP8]] to <4 x float>*
 ; CHECK-NEXT:    store <4 x float> [[PREDPHI]], <4 x float>* [[TMP11]], align 4, !alias.scope !13, !noalias !15
 ; CHECK-NEXT:    [[INDEX_NEXT]] = add nuw i64 [[INDEX]], 4
 ; CHECK-NEXT:    [[TMP12:%.*]] = icmp eq i64 [[INDEX_NEXT]], 10000
 ; CHECK-NEXT:    br i1 [[TMP12]], label [[EXIT:%.*]], label [[VECTOR_BODY]], !llvm.loop [[LOOP16:![0-9]+]]
 ; CHECK:       loop.body:
 ; CHECK-NEXT:    [[IV1:%.*]] = phi i64 [ [[IV_NEXT:%.*]], [[LOOP_LATCH:%.*]] ], [ 0, [[ENTRY:%.*]] ]
 ; CHECK-NEXT:    [[C_GEP:%.*]] = getelementptr inbounds i32, i32* [[C]], i64 [[IV1]]
 ; CHECK-NEXT:    [[C_LV:%.*]] = load i32, i32* [[C_GEP]], align 4
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[C_LV]], 20
-; CHECK-NEXT:    [[B_GEP_0:%.*]] = getelementptr inbounds float, float* [[B]], i64 [[IV1]]
 ; CHECK-NEXT:    [[A_GEP_0:%.*]] = getelementptr inbounds float, float* [[A]], i64 [[IV1]]
 ; CHECK-NEXT:    [[A_LV_0:%.*]] = load float, float* [[A_GEP_0]], align 4
 ; CHECK-NEXT:    [[MUL2_I81_I:%.*]] = fmul float [[A_LV_0]], [[X]]
+; CHECK-NEXT:    [[B_GEP_0:%.*]] = getelementptr inbounds float, float* [[B]], i64 [[IV1]]
 ; CHECK-NEXT:    br i1 [[CMP]], label [[LOOP_LATCH]], label [[ELSE:%.*]]
 ; CHECK:       else:
 ; CHECK-NEXT:    [[B_LV:%.*]] = load float, float* [[B_GEP_0]], align 4
 ; CHECK-NEXT:    [[ADD:%.*]] = fadd float [[MUL2_I81_I]], [[B_LV]]
 ; CHECK-NEXT:    br label [[LOOP_LATCH]]
 ; CHECK:       loop.latch:
-; CHECK-NEXT:    [[STOREMERGE:%.*]] = phi float [ [[ADD]], [[ELSE]] ], [ [[MUL2_I81_I]], [[LOOP_BODY]] ]
-; CHECK-NEXT:    store float [[STOREMERGE]], float* [[B_GEP_0]], align 4
+; CHECK-NEXT:    [[ADD_SINK:%.*]] = phi float [ [[ADD]], [[ELSE]] ], [ [[MUL2_I81_I]], [[LOOP_BODY]] ]
+; CHECK-NEXT:    store float [[ADD_SINK]], float* [[B_GEP_0]], align 4
 ; CHECK-NEXT:    [[IV_NEXT]] = add nuw nsw i64 [[IV1]], 1
 ; CHECK-NEXT:    [[CMP_0:%.*]] = icmp ult i64 [[IV1]], 9999
 ; CHECK-NEXT:    br i1 [[CMP_0]], label [[LOOP_BODY]], label [[EXIT]], !llvm.loop [[LOOP17:![0-9]+]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    ret void
 ;
 entry:
   br label %loop.header