1 files changed, 93 insertions, 33 deletions

diff --git a/contrib/llvm-project/llvm/lib/Transforms/Scalar/LoopBoundSplit.cpp b/contrib/llvm-project/llvm/lib/Transforms/Scalar/LoopBoundSplit.cpp
index 993b154dc9a8..d438d56e38ca 100644
--- a/contrib/llvm-project/llvm/lib/Transforms/Scalar/LoopBoundSplit.cpp
+++ b/contrib/llvm-project/llvm/lib/Transforms/Scalar/LoopBoundSplit.cpp
@@ -7,6 +7,7 @@
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Transforms/Scalar/LoopBoundSplit.h"
+#include "llvm/ADT/Sequence.h"
 #include "llvm/Analysis/LoopAccessAnalysis.h"
 #include "llvm/Analysis/LoopAnalysisManager.h"
 #include "llvm/Analysis/LoopInfo.h"
@@ -39,10 +40,12 @@ struct ConditionInfo {
   ICmpInst::Predicate Pred;
   /// AddRec llvm value
   Value *AddRecValue;
+  /// Non PHI AddRec llvm value
+  Value *NonPHIAddRecValue;
   /// Bound llvm value
   Value *BoundValue;
   /// AddRec SCEV
-  const SCEV *AddRecSCEV;
+  const SCEVAddRecExpr *AddRecSCEV;
   /// Bound SCEV
   const SCEV *BoundSCEV;
 
@@ -54,19 +57,31 @@ struct ConditionInfo {
 } // namespace
 
 static void analyzeICmp(ScalarEvolution &SE, ICmpInst *ICmp,
-                        ConditionInfo &Cond) {
+                        ConditionInfo &Cond, const Loop &L) {
   Cond.ICmp = ICmp;
   if (match(ICmp, m_ICmp(Cond.Pred, m_Value(Cond.AddRecValue),
                          m_Value(Cond.BoundValue)))) {
-    Cond.AddRecSCEV = SE.getSCEV(Cond.AddRecValue);
-    Cond.BoundSCEV = SE.getSCEV(Cond.BoundValue);
+    const SCEV *AddRecSCEV = SE.getSCEV(Cond.AddRecValue);
+    const SCEV *BoundSCEV = SE.getSCEV(Cond.BoundValue);
+    const SCEVAddRecExpr *LHSAddRecSCEV = dyn_cast<SCEVAddRecExpr>(AddRecSCEV);
+    const SCEVAddRecExpr *RHSAddRecSCEV = dyn_cast<SCEVAddRecExpr>(BoundSCEV);
     // Locate AddRec in LHSSCEV and Bound in RHSSCEV.
-    if (isa<SCEVAddRecExpr>(Cond.BoundSCEV) &&
-        !isa<SCEVAddRecExpr>(Cond.AddRecSCEV)) {
+    if (!LHSAddRecSCEV && RHSAddRecSCEV) {
       std::swap(Cond.AddRecValue, Cond.BoundValue);
-      std::swap(Cond.AddRecSCEV, Cond.BoundSCEV);
+      std::swap(AddRecSCEV, BoundSCEV);
       Cond.Pred = ICmpInst::getSwappedPredicate(Cond.Pred);
     }
+
+    Cond.AddRecSCEV = dyn_cast<SCEVAddRecExpr>(AddRecSCEV);
+    Cond.BoundSCEV = BoundSCEV;
+    Cond.NonPHIAddRecValue = Cond.AddRecValue;
+
+    // If the Cond.AddRecValue is PHI node, update Cond.NonPHIAddRecValue with
+    // value from backedge.
+    if (Cond.AddRecSCEV && isa<PHINode>(Cond.AddRecValue)) {
+      PHINode *PN = cast<PHINode>(Cond.AddRecValue);
+      Cond.NonPHIAddRecValue = PN->getIncomingValueForBlock(L.getLoopLatch());
+    }
   }
 }
 
@@ -118,21 +133,20 @@ static bool calculateUpperBound(const Loop &L, ScalarEvolution &SE,
 static bool hasProcessableCondition(const Loop &L, ScalarEvolution &SE,
                                     ICmpInst *ICmp, ConditionInfo &Cond,
                                     bool IsExitCond) {
-  analyzeICmp(SE, ICmp, Cond);
+  analyzeICmp(SE, ICmp, Cond, L);
 
   // The BoundSCEV should be evaluated at loop entry.
   if (!SE.isAvailableAtLoopEntry(Cond.BoundSCEV, &L))
     return false;
 
-  const SCEVAddRecExpr *AddRecSCEV = dyn_cast<SCEVAddRecExpr>(Cond.AddRecSCEV);
   // Allowed AddRec as induction variable.
-  if (!AddRecSCEV)
+  if (!Cond.AddRecSCEV)
     return false;
 
-  if (!AddRecSCEV->isAffine())
+  if (!Cond.AddRecSCEV->isAffine())
     return false;
 
-  const SCEV *StepRecSCEV = AddRecSCEV->getStepRecurrence(SE);
+  const SCEV *StepRecSCEV = Cond.AddRecSCEV->getStepRecurrence(SE);
   // Allowed constant step.
   if (!isa<SCEVConstant>(StepRecSCEV))
     return false;
@@ -264,6 +278,14 @@ static BranchInst *findSplitCandidate(const Loop &L, ScalarEvolution &SE,
         SplitCandidateCond.BoundSCEV->getType())
       continue;
 
+    // After transformation, we assume the split condition of the pre-loop is
+    // always true. In order to guarantee it, we need to check the start value
+    // of the split cond AddRec satisfies the split condition.
+    if (!SE.isLoopEntryGuardedByCond(&L, SplitCandidateCond.Pred,
+                                     SplitCandidateCond.AddRecSCEV->getStart(),
+                                     SplitCandidateCond.BoundSCEV))
+      continue;
+
     SplitCandidateCond.BI = BI;
     return BI;
   }
@@ -341,13 +363,45 @@ static bool splitLoopBound(Loop &L, DominatorTree &DT, LoopInfo &LI,
                                     ".split", &LI, &DT, PostLoopBlocks);
   remapInstructionsInBlocks(PostLoopBlocks, VMap);
 
-  // Add conditional branch to check we can skip post-loop in its preheader.
   BasicBlock *PostLoopPreHeader = PostLoop->getLoopPreheader();
-  IRBuilder<> Builder(PostLoopPreHeader);
+  IRBuilder<> Builder(&PostLoopPreHeader->front());
+
+  // Update phi nodes in header of post-loop.
+  bool isExitingLatch =
+      (L.getExitingBlock() == L.getLoopLatch()) ? true : false;
+  Value *ExitingCondLCSSAPhi = nullptr;
+  for (PHINode &PN : L.getHeader()->phis()) {
+    // Create LCSSA phi node in preheader of post-loop.
+    PHINode *LCSSAPhi =
+        Builder.CreatePHI(PN.getType(), 1, PN.getName() + ".lcssa");
+    LCSSAPhi->setDebugLoc(PN.getDebugLoc());
+    // If the exiting block is loop latch, the phi does not have the update at
+    // last iteration. In this case, update lcssa phi with value from backedge.
+    LCSSAPhi->addIncoming(
+        isExitingLatch ? PN.getIncomingValueForBlock(L.getLoopLatch()) : &PN,
+        L.getExitingBlock());
+
+    // Update the start value of phi node in post-loop with the LCSSA phi node.
+    PHINode *PostLoopPN = cast<PHINode>(VMap[&PN]);
+    PostLoopPN->setIncomingValueForBlock(PostLoopPreHeader, LCSSAPhi);
+
+    // Find PHI with exiting condition from pre-loop. The PHI should be
+    // SCEVAddRecExpr and have same incoming value from backedge with
+    // ExitingCond.
+    if (!SE.isSCEVable(PN.getType()))
+      continue;
+
+    const SCEVAddRecExpr *PhiSCEV = dyn_cast<SCEVAddRecExpr>(SE.getSCEV(&PN));
+    if (PhiSCEV && ExitingCond.NonPHIAddRecValue ==
+                       PN.getIncomingValueForBlock(L.getLoopLatch()))
+      ExitingCondLCSSAPhi = LCSSAPhi;
+  }
+
+  // Add conditional branch to check we can skip post-loop in its preheader.
   Instruction *OrigBI = PostLoopPreHeader->getTerminator();
   ICmpInst::Predicate Pred = ICmpInst::ICMP_NE;
   Value *Cond =
-      Builder.CreateICmp(Pred, ExitingCond.AddRecValue, ExitingCond.BoundValue);
+      Builder.CreateICmp(Pred, ExitingCondLCSSAPhi, ExitingCond.BoundValue);
   Builder.CreateCondBr(Cond, PostLoop->getHeader(), PostLoop->getExitBlock());
   OrigBI->eraseFromParent();
 
@@ -368,21 +422,6 @@ static bool splitLoopBound(Loop &L, DominatorTree &DT, LoopInfo &LI,
   // Replace exiting bound value of pre-loop NewBound.
   ExitingCond.ICmp->setOperand(1, NewBoundValue);
 
-  // Replace IV's start value of post-loop by NewBound.
-  for (PHINode &PN : L.getHeader()->phis()) {
-    // Find PHI with exiting condition from pre-loop.
-    if (SE.isSCEVable(PN.getType()) && isa<SCEVAddRecExpr>(SE.getSCEV(&PN))) {
-      for (Value *Op : PN.incoming_values()) {
-        if (Op == ExitingCond.AddRecValue) {
-          // Find cloned PHI for post-loop.
-          PHINode *PostLoopPN = cast<PHINode>(VMap[&PN]);
-          PostLoopPN->setIncomingValueForBlock(PostLoopPreHeader,
-                                               NewBoundValue);
-        }
-      }
-    }
-  }
-
   // Replace SplitCandidateCond.BI's condition of pre-loop by True.
   LLVMContext &Context = PreHeader->getContext();
   SplitCandidateCond.BI->setCondition(ConstantInt::getTrue(Context));
@@ -398,6 +437,30 @@ static bool splitLoopBound(Loop &L, DominatorTree &DT, LoopInfo &LI,
   else
     ExitingCond.BI->setSuccessor(1, PostLoopPreHeader);
 
+  // Update phi node in exit block of post-loop.
+  Builder.SetInsertPoint(&PostLoopPreHeader->front());
+  for (PHINode &PN : PostLoop->getExitBlock()->phis()) {
+    for (auto i : seq<int>(0, PN.getNumOperands())) {
+      // Check incoming block is pre-loop's exiting block.
+      if (PN.getIncomingBlock(i) == L.getExitingBlock()) {
+        Value *IncomingValue = PN.getIncomingValue(i);
+
+        // Create LCSSA phi node for incoming value.
+        PHINode *LCSSAPhi =
+            Builder.CreatePHI(PN.getType(), 1, PN.getName() + ".lcssa");
+        LCSSAPhi->setDebugLoc(PN.getDebugLoc());
+        LCSSAPhi->addIncoming(IncomingValue, PN.getIncomingBlock(i));
+
+        // Replace pre-loop's exiting block by post-loop's preheader.
+        PN.setIncomingBlock(i, PostLoopPreHeader);
+        // Replace incoming value by LCSSAPhi.
+        PN.setIncomingValue(i, LCSSAPhi);
+        // Add a new incoming value with post-loop's exiting block.
+        PN.addIncoming(VMap[IncomingValue], PostLoop->getExitingBlock());
+      }
+    }
+  }
+
   // Update dominator tree.
   DT.changeImmediateDominator(PostLoopPreHeader, L.getExitingBlock());
   DT.changeImmediateDominator(PostLoop->getExitBlock(), PostLoopPreHeader);
@@ -406,10 +469,7 @@ static bool splitLoopBound(Loop &L, DominatorTree &DT, LoopInfo &LI,
   SE.forgetLoop(&L);
 
   // Canonicalize loops.
-  // TODO: Try to update LCSSA information according to above change.
-  formLCSSA(L, DT, &LI, &SE);
   simplifyLoop(&L, &DT, &LI, &SE, nullptr, nullptr, true);
-  formLCSSA(*PostLoop, DT, &LI, &SE);
   simplifyLoop(PostLoop, &DT, &LI, &SE, nullptr, nullptr, true);
 
   // Add new post-loop to loop pass manager.