[GVN] Support chain of phi nodes in exit blocks.

[fhahn]

Summary

This patch extends to logic added in D118143 to allow chains of phis
from the lcssa phi to the using load instruction. The intermediate phis
must be in blocks only containing the phi and an unconditional branch.
The blocks must be connected directly. This ensures that the load
instruction executes if the loop exit executes.

Such chains of phi nodes are common for rotated loops and is required to
be able to handle cases such as (https://clang.godbolt.org/z/6czGzzqbs)

#include <vector>
#include <algorithm>

int foo(const std::vector<int> &V) {
   return *std::min_element(V.begin(), V.end());
}

Depends on D118143.

[fhahn]

add missing ;

[fhahn]

A major rewrite/update following @reames' suggestion in D118143 as extension to the available value analysis. This patch now tries to find an existing value-select that can be used instead of loading from a pointer-select. The first version is intentionally kept quite restrictive and can be extended through follow-ups.

Together with D118143, this enables vectorization for common code like std::min_element, yielding substantial speedups for code that uses it for non-tiny numbers of elements.

[reames]

Really not a fan here.

I think what we need to do is recognize the address clobber being from a select, and then perform both sides of the memory dependency "as if" we had two loads at the point of the select. Doing that would let this work generically.

I'd mentioned this scheme in the prior patch, but I was sorta okay with the special casing there. I'm really not on board with the extension made here.

Note that you don't need to go all the way to the fully general scheme. You could fork the analysis only once and handle only the case where there's a single select on the address. You do need to be consistent for both within block and cross block, but that's a different issue.

As an aside, I think this whole problem gets much easier if we can use the MSSA interfaces. I know there's someone trying to switch legacy GVN to MSSA. It might be worth trying to drive that through, and then revisiting.

[fhahn]

In D118144#3285181, @reames wrote:

Really not a fan here.

I think what we need to do is recognize the address clobber being from a select, and then perform both sides of the memory dependency "as if" we had two loads at the point of the select. Doing that would let this work generically.

That's a fair point, this patch is indeed very specific! Let me take a look at what some kind of 'fork-analysis' would take.

[lebedev.ri]

This review may be stuck/dead, consider abandoning if no longer relevant.
Removing myself as reviewer in attempt to clean dashboard.

llvm/lib/Transforms/Scalar/GVN.cpp

for (Value *U : Sel->users()) {
     }
 
     auto *PN = dyn_cast<PHINode>(I);
     if (!PN || ExitPhi)
       return false;
     ExitPhi = PN;
   }
 
-  if (!ExitPhi || ExitPhi->getNumIncomingValues() != 1)
+  PHINode *Current = ExitPhi;
+  PHINode *LastPhi = nullptr;
+  SmallVector<BasicBlock *> Blocks;
+  while (Current) {
+    LastPhi = Current;
+    if (Current->hasOneUse()) {
+      Blocks.push_back(Current->getParent());
+      Current = dyn_cast<PHINode>(*Current->user_begin());
+    } else
       return false;
-  auto LastLI = dyn_cast<LoadInst>(*ExitPhi->user_begin());
+  }
+
+  auto LastLI = dyn_cast<LoadInst>(*LastPhi->user_begin());
   auto ExitBlock = L->getExitBlock();
-  if (!LastLI || ExitPhi->getParent() != LastLI->getParent() ||
-      ExitPhi->getParent() != ExitBlock)
+  if (!LastLI || LastPhi->getParent() != LastLI->getParent() ||
+      ExitBlock != Blocks[0])
+    return false;
+
+  // If we have phis across multiple blocks, make sure the blocks only contain
+  // the phi and an unconditional branch and are connected to the previous
+  // block. This ensures that the last block in the chain executes if the loop
+  // exit block executes.
+  for (unsigned I = 1; I < Blocks.size(); ++I) {
+    BasicBlock *A = Blocks[I - 1];
+    if (&*std::next(A->begin()) != A->getTerminator())
+      return false;
+    auto *Term = dyn_cast<BranchInst>(A->getTerminator());
+    if (Term->isConditional() || A->getSingleSuccessor() != Blocks[I])
       return false;
+  }
 
-  for (Instruction &I : make_range(ExitBlock->begin(), LastLI->getIterator())) {
+  // Make sure LastLI is guaranteed to execute on entry to its containing block.
+  for (Instruction &I :
+       make_range(Blocks.back()->begin(), LastLI->getIterator())) {
     if (!isGuaranteedToTransferExecutionToSuccessor(&I) || I.mayWriteToMemory())
       return false;
   }
 
   // The loop is of the form below.
   // loop:
   //   %sel.phi = phi i32* [ %start, %ph ], [ %sel, %ph ]
   //   %l = load %ptr
bool GVNPass::performLoopLoadPREThroughSelect(LoadInst *Load) {
   Value *NewSel =
       SelectInst::Create(Sel->getCondition(), IterLoad, ValuePhi, "", Sel);
   ValuePhi->addIncoming(PreheaderLoad, PH);
   ValuePhi->addIncoming(NewSel, L->getLoopLatch());
   PhiLoad->replaceAllUsesWith(ValuePhi);
 
   // Finally, replace phi nodes referencing the pointer select with a phi node
   // for the selected value.
-  PHINode *ExitValuePhi = PHINode::Create(
-      LastLI->getType(), 2, LastLI->getName() + ".promoted.load", ExitPhi);
-  ExitValuePhi->addIncoming(NewSel, ExitPhi->getIncomingBlock(0));
-  LastLI->replaceAllUsesWith(ExitValuePhi);
+  Current = ExitPhi;
+  DenseMap<Value *, Value *> Old2New;
+  Old2New[Sel] = NewSel;
+  while (Current) {
+    PHINode *ValuePhi = PHINode::Create(
+        LastLI->getType(), 2, LastLI->getName() + ".promoted.load", Current);
+    for (unsigned I = 0; I != Current->getNumIncomingValues(); ++I) {
+      BasicBlock *IncBB = Current->getIncomingBlock(I);
+      ValuePhi->addIncoming(PoisonValue::get(ValuePhi->getType()), IncBB);
+      auto Iter = Old2New.find(Current->getIncomingValue(I));
+      if (Iter != Old2New.end()) {
+        ValuePhi->setIncomingValue(I, Iter->second);
+      } else {
+        BasicBlock *Split =
+            SplitEdge(IncBB, Current->getParent(), DT, LI, MSSAU);
+        auto NewLI = new LoadInst(
+            LastLI->getType(), Current->getIncomingValue(I),
+            LastLI->getName() + ".promoted", Split->getTerminator());
+        IncBB = Split;
+        if (MSSAU) {
+          MemoryAccess *NewMemAcc = MSSAU->createMemoryAccessInBB(
+              NewLI, nullptr, NewLI->getParent(), MemorySSA::End);
+          MSSAU->insertUse(cast<MemoryUse>(NewMemAcc), /*RenameUses=*/true);
+        }
+        ValuePhi->setIncomingValue(I, NewLI);
+      }
+    }
+    Old2New[Current] = ValuePhi;
+    Current = dyn_cast<PHINode>(*Current->user_begin());
+  }
+  LastLI->replaceAllUsesWith(Old2New[LastPhi]);
   markInstructionForDeletion(PhiLoad);
   return true;
 }
 
 bool GVNPass::performLoopLoadPRE(LoadInst *Load,
                                  AvailValInBlkVect &ValuesPerBlock,
                                  UnavailBlkVect &UnavailableBlocks) {
   if (!LI)

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

exit:
   %res = load i32, i32* %min.select, align 4
   ret i32 %res
 }
 
 define i32 @test_pointer_phi_select_same_object_split_edge(i32* %ptr, i32* %end, i1 %c)  {
 ; CHECK-LABEL: @test_pointer_phi_select_same_object_split_edge(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[START_PTR:%.*]] = getelementptr inbounds i32, i32* [[PTR:%.*]], i64 1
-; CHECK-NEXT:    br i1 [[C:%.*]], label [[EXIT:%.*]], label [[LOOP_PREHEADER:%.*]]
+; CHECK-NEXT:    br i1 [[C:%.*]], label [[ENTRY_EXIT_CRIT_EDGE:%.*]], label [[LOOP_PREHEADER:%.*]]
+; CHECK:       entry.exit_crit_edge:
+; CHECK-NEXT:    [[RES_PROMOTED:%.*]] = load i32, i32* [[END:%.*]], align 4
+; CHECK-NEXT:    br label [[EXIT:%.*]]
 ; CHECK:       loop.preheader:
+; CHECK-NEXT:    [[L_2_PROMOTED:%.*]] = load i32, i32* [[PTR]], align 4
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
+; CHECK-NEXT:    [[L_2_PROMOTED_LOAD:%.*]] = phi i32 [ [[L_2_PROMOTED]], [[LOOP_PREHEADER]] ], [ [[TMP0:%.*]], [[LOOP]] ]
 ; CHECK-NEXT:    [[PTR_IV:%.*]] = phi i32* [ [[PTR_IV_NEXT:%.*]], [[LOOP]] ], [ [[START_PTR]], [[LOOP_PREHEADER]] ]
 ; CHECK-NEXT:    [[MIN_PTR:%.*]] = phi i32* [ [[MIN_SELECT:%.*]], [[LOOP]] ], [ [[PTR]], [[LOOP_PREHEADER]] ]
 ; CHECK-NEXT:    [[L_1:%.*]] = load i32, i32* [[PTR_IV]], align 4
-; CHECK-NEXT:    [[L_2:%.*]] = load i32, i32* [[MIN_PTR]], align 4
-; CHECK-NEXT:    [[CMP_I_I_I:%.*]] = icmp ult i32 [[L_1]], [[L_2]]
+; CHECK-NEXT:    [[CMP_I_I_I:%.*]] = icmp ult i32 [[L_1]], [[L_2_PROMOTED_LOAD]]
+; CHECK-NEXT:    [[TMP0]] = select i1 [[CMP_I_I_I]], i32 [[L_1]], i32 [[L_2_PROMOTED_LOAD]]
 ; CHECK-NEXT:    [[MIN_SELECT]] = select i1 [[CMP_I_I_I]], i32* [[PTR_IV]], i32* [[MIN_PTR]]
 ; CHECK-NEXT:    [[PTR_IV_NEXT]] = getelementptr inbounds i32, i32* [[PTR_IV]], i64 1
-; CHECK-NEXT:    [[EC:%.*]] = icmp eq i32* [[PTR_IV_NEXT]], [[END:%.*]]
+; CHECK-NEXT:    [[EC:%.*]] = icmp eq i32* [[PTR_IV_NEXT]], [[END]]
 ; CHECK-NEXT:    br i1 [[EC]], label [[LOOP_EXIT:%.*]], label [[LOOP]]
 ; CHECK:       loop.exit:
 ; CHECK-NEXT:    br label [[EXIT]]
 ; CHECK:       exit:
-; CHECK-NEXT:    [[LCSSA_PHI_2:%.*]] = phi i32* [ [[END]], [[ENTRY:%.*]] ], [ [[MIN_SELECT]], [[LOOP_EXIT]] ]
-; CHECK-NEXT:    [[RES:%.*]] = load i32, i32* [[LCSSA_PHI_2]], align 4
-; CHECK-NEXT:    ret i32 [[RES]]
+; CHECK-NEXT:    [[RES_PROMOTED_LOAD1:%.*]] = phi i32 [ [[RES_PROMOTED]], [[ENTRY_EXIT_CRIT_EDGE]] ], [ [[TMP0]], [[LOOP_EXIT]] ]
+; CHECK-NEXT:    [[LCSSA_PHI_2:%.*]] = phi i32* [ [[END]], [[ENTRY_EXIT_CRIT_EDGE]] ], [ [[MIN_SELECT]], [[LOOP_EXIT]] ]
+; CHECK-NEXT:    ret i32 [[RES_PROMOTED_LOAD1]]
 ;
 entry:
   %start.ptr = getelementptr inbounds i32, i32* %ptr, i64 1
   br i1 %c, label %exit, label %loop
 
 loop:
   %ptr.iv = phi i32* [ %start.ptr, %entry ], [ %ptr.iv.next, %loop ]
   %min.ptr = phi i32* [ %ptr, %entry ], [ %min.select, %loop ]