xref: /openbsd-src/gnu/llvm/llvm/lib/Transforms/Scalar/LoopBoundSplit.cpp (revision 73471bf04ceb096474c7f0fa83b1b65c70a787a1)
1*73471bf0Spatrick //===------- LoopBoundSplit.cpp - Split Loop Bound --------------*- C++ -*-===//
2*73471bf0Spatrick //
3*73471bf0Spatrick // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4*73471bf0Spatrick // See https://llvm.org/LICENSE.txt for license information.
5*73471bf0Spatrick // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6*73471bf0Spatrick //
7*73471bf0Spatrick //===----------------------------------------------------------------------===//
8*73471bf0Spatrick 
9*73471bf0Spatrick #include "llvm/Transforms/Scalar/LoopBoundSplit.h"
10*73471bf0Spatrick #include "llvm/Analysis/LoopAccessAnalysis.h"
11*73471bf0Spatrick #include "llvm/Analysis/LoopAnalysisManager.h"
12*73471bf0Spatrick #include "llvm/Analysis/LoopInfo.h"
13*73471bf0Spatrick #include "llvm/Analysis/LoopIterator.h"
14*73471bf0Spatrick #include "llvm/Analysis/LoopPass.h"
15*73471bf0Spatrick #include "llvm/Analysis/MemorySSA.h"
16*73471bf0Spatrick #include "llvm/Analysis/MemorySSAUpdater.h"
17*73471bf0Spatrick #include "llvm/Analysis/ScalarEvolution.h"
18*73471bf0Spatrick #include "llvm/Analysis/ScalarEvolutionExpressions.h"
19*73471bf0Spatrick #include "llvm/IR/PatternMatch.h"
20*73471bf0Spatrick #include "llvm/Transforms/Utils/BasicBlockUtils.h"
21*73471bf0Spatrick #include "llvm/Transforms/Utils/Cloning.h"
22*73471bf0Spatrick #include "llvm/Transforms/Utils/LoopSimplify.h"
23*73471bf0Spatrick #include "llvm/Transforms/Utils/LoopUtils.h"
24*73471bf0Spatrick #include "llvm/Transforms/Utils/ScalarEvolutionExpander.h"
25*73471bf0Spatrick 
26*73471bf0Spatrick #define DEBUG_TYPE "loop-bound-split"
27*73471bf0Spatrick 
28*73471bf0Spatrick namespace llvm {
29*73471bf0Spatrick 
30*73471bf0Spatrick using namespace PatternMatch;
31*73471bf0Spatrick 
32*73471bf0Spatrick namespace {
33*73471bf0Spatrick struct ConditionInfo {
34*73471bf0Spatrick   /// Branch instruction with this condition
35*73471bf0Spatrick   BranchInst *BI;
36*73471bf0Spatrick   /// ICmp instruction with this condition
37*73471bf0Spatrick   ICmpInst *ICmp;
38*73471bf0Spatrick   /// Preciate info
39*73471bf0Spatrick   ICmpInst::Predicate Pred;
40*73471bf0Spatrick   /// AddRec llvm value
41*73471bf0Spatrick   Value *AddRecValue;
42*73471bf0Spatrick   /// Bound llvm value
43*73471bf0Spatrick   Value *BoundValue;
44*73471bf0Spatrick   /// AddRec SCEV
45*73471bf0Spatrick   const SCEV *AddRecSCEV;
46*73471bf0Spatrick   /// Bound SCEV
47*73471bf0Spatrick   const SCEV *BoundSCEV;
48*73471bf0Spatrick 
49*73471bf0Spatrick   ConditionInfo()
50*73471bf0Spatrick       : BI(nullptr), ICmp(nullptr), Pred(ICmpInst::BAD_ICMP_PREDICATE),
51*73471bf0Spatrick         AddRecValue(nullptr), BoundValue(nullptr), AddRecSCEV(nullptr),
52*73471bf0Spatrick         BoundSCEV(nullptr) {}
53*73471bf0Spatrick };
54*73471bf0Spatrick } // namespace
55*73471bf0Spatrick 
56*73471bf0Spatrick static void analyzeICmp(ScalarEvolution &SE, ICmpInst *ICmp,
57*73471bf0Spatrick                         ConditionInfo &Cond) {
58*73471bf0Spatrick   Cond.ICmp = ICmp;
59*73471bf0Spatrick   if (match(ICmp, m_ICmp(Cond.Pred, m_Value(Cond.AddRecValue),
60*73471bf0Spatrick                          m_Value(Cond.BoundValue)))) {
61*73471bf0Spatrick     Cond.AddRecSCEV = SE.getSCEV(Cond.AddRecValue);
62*73471bf0Spatrick     Cond.BoundSCEV = SE.getSCEV(Cond.BoundValue);
63*73471bf0Spatrick     // Locate AddRec in LHSSCEV and Bound in RHSSCEV.
64*73471bf0Spatrick     if (isa<SCEVAddRecExpr>(Cond.BoundSCEV) &&
65*73471bf0Spatrick         !isa<SCEVAddRecExpr>(Cond.AddRecSCEV)) {
66*73471bf0Spatrick       std::swap(Cond.AddRecValue, Cond.BoundValue);
67*73471bf0Spatrick       std::swap(Cond.AddRecSCEV, Cond.BoundSCEV);
68*73471bf0Spatrick       Cond.Pred = ICmpInst::getSwappedPredicate(Cond.Pred);
69*73471bf0Spatrick     }
70*73471bf0Spatrick   }
71*73471bf0Spatrick }
72*73471bf0Spatrick 
73*73471bf0Spatrick static bool calculateUpperBound(const Loop &L, ScalarEvolution &SE,
74*73471bf0Spatrick                                 ConditionInfo &Cond, bool IsExitCond) {
75*73471bf0Spatrick   if (IsExitCond) {
76*73471bf0Spatrick     const SCEV *ExitCount = SE.getExitCount(&L, Cond.ICmp->getParent());
77*73471bf0Spatrick     if (isa<SCEVCouldNotCompute>(ExitCount))
78*73471bf0Spatrick       return false;
79*73471bf0Spatrick 
80*73471bf0Spatrick     Cond.BoundSCEV = ExitCount;
81*73471bf0Spatrick     return true;
82*73471bf0Spatrick   }
83*73471bf0Spatrick 
84*73471bf0Spatrick   // For non-exit condtion, if pred is LT, keep existing bound.
85*73471bf0Spatrick   if (Cond.Pred == ICmpInst::ICMP_SLT || Cond.Pred == ICmpInst::ICMP_ULT)
86*73471bf0Spatrick     return true;
87*73471bf0Spatrick 
88*73471bf0Spatrick   // For non-exit condition, if pre is LE, try to convert it to LT.
89*73471bf0Spatrick   //      Range                 Range
90*73471bf0Spatrick   // AddRec <= Bound  -->  AddRec < Bound + 1
91*73471bf0Spatrick   if (Cond.Pred != ICmpInst::ICMP_ULE && Cond.Pred != ICmpInst::ICMP_SLE)
92*73471bf0Spatrick     return false;
93*73471bf0Spatrick 
94*73471bf0Spatrick   if (IntegerType *BoundSCEVIntType =
95*73471bf0Spatrick           dyn_cast<IntegerType>(Cond.BoundSCEV->getType())) {
96*73471bf0Spatrick     unsigned BitWidth = BoundSCEVIntType->getBitWidth();
97*73471bf0Spatrick     APInt Max = ICmpInst::isSigned(Cond.Pred)
98*73471bf0Spatrick                     ? APInt::getSignedMaxValue(BitWidth)
99*73471bf0Spatrick                     : APInt::getMaxValue(BitWidth);
100*73471bf0Spatrick     const SCEV *MaxSCEV = SE.getConstant(Max);
101*73471bf0Spatrick     // Check Bound < INT_MAX
102*73471bf0Spatrick     ICmpInst::Predicate Pred =
103*73471bf0Spatrick         ICmpInst::isSigned(Cond.Pred) ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT;
104*73471bf0Spatrick     if (SE.isKnownPredicate(Pred, Cond.BoundSCEV, MaxSCEV)) {
105*73471bf0Spatrick       const SCEV *BoundPlusOneSCEV =
106*73471bf0Spatrick           SE.getAddExpr(Cond.BoundSCEV, SE.getOne(BoundSCEVIntType));
107*73471bf0Spatrick       Cond.BoundSCEV = BoundPlusOneSCEV;
108*73471bf0Spatrick       Cond.Pred = Pred;
109*73471bf0Spatrick       return true;
110*73471bf0Spatrick     }
111*73471bf0Spatrick   }
112*73471bf0Spatrick 
113*73471bf0Spatrick   // ToDo: Support ICMP_NE/EQ.
114*73471bf0Spatrick 
115*73471bf0Spatrick   return false;
116*73471bf0Spatrick }
117*73471bf0Spatrick 
118*73471bf0Spatrick static bool hasProcessableCondition(const Loop &L, ScalarEvolution &SE,
119*73471bf0Spatrick                                     ICmpInst *ICmp, ConditionInfo &Cond,
120*73471bf0Spatrick                                     bool IsExitCond) {
121*73471bf0Spatrick   analyzeICmp(SE, ICmp, Cond);
122*73471bf0Spatrick 
123*73471bf0Spatrick   // The BoundSCEV should be evaluated at loop entry.
124*73471bf0Spatrick   if (!SE.isAvailableAtLoopEntry(Cond.BoundSCEV, &L))
125*73471bf0Spatrick     return false;
126*73471bf0Spatrick 
127*73471bf0Spatrick   const SCEVAddRecExpr *AddRecSCEV = dyn_cast<SCEVAddRecExpr>(Cond.AddRecSCEV);
128*73471bf0Spatrick   // Allowed AddRec as induction variable.
129*73471bf0Spatrick   if (!AddRecSCEV)
130*73471bf0Spatrick     return false;
131*73471bf0Spatrick 
132*73471bf0Spatrick   if (!AddRecSCEV->isAffine())
133*73471bf0Spatrick     return false;
134*73471bf0Spatrick 
135*73471bf0Spatrick   const SCEV *StepRecSCEV = AddRecSCEV->getStepRecurrence(SE);
136*73471bf0Spatrick   // Allowed constant step.
137*73471bf0Spatrick   if (!isa<SCEVConstant>(StepRecSCEV))
138*73471bf0Spatrick     return false;
139*73471bf0Spatrick 
140*73471bf0Spatrick   ConstantInt *StepCI = cast<SCEVConstant>(StepRecSCEV)->getValue();
141*73471bf0Spatrick   // Allowed positive step for now.
142*73471bf0Spatrick   // TODO: Support negative step.
143*73471bf0Spatrick   if (StepCI->isNegative() || StepCI->isZero())
144*73471bf0Spatrick     return false;
145*73471bf0Spatrick 
146*73471bf0Spatrick   // Calculate upper bound.
147*73471bf0Spatrick   if (!calculateUpperBound(L, SE, Cond, IsExitCond))
148*73471bf0Spatrick     return false;
149*73471bf0Spatrick 
150*73471bf0Spatrick   return true;
151*73471bf0Spatrick }
152*73471bf0Spatrick 
153*73471bf0Spatrick static bool isProcessableCondBI(const ScalarEvolution &SE,
154*73471bf0Spatrick                                 const BranchInst *BI) {
155*73471bf0Spatrick   BasicBlock *TrueSucc = nullptr;
156*73471bf0Spatrick   BasicBlock *FalseSucc = nullptr;
157*73471bf0Spatrick   ICmpInst::Predicate Pred;
158*73471bf0Spatrick   Value *LHS, *RHS;
159*73471bf0Spatrick   if (!match(BI, m_Br(m_ICmp(Pred, m_Value(LHS), m_Value(RHS)),
160*73471bf0Spatrick                       m_BasicBlock(TrueSucc), m_BasicBlock(FalseSucc))))
161*73471bf0Spatrick     return false;
162*73471bf0Spatrick 
163*73471bf0Spatrick   if (!SE.isSCEVable(LHS->getType()))
164*73471bf0Spatrick     return false;
165*73471bf0Spatrick   assert(SE.isSCEVable(RHS->getType()) && "Expected RHS's type is SCEVable");
166*73471bf0Spatrick 
167*73471bf0Spatrick   if (TrueSucc == FalseSucc)
168*73471bf0Spatrick     return false;
169*73471bf0Spatrick 
170*73471bf0Spatrick   return true;
171*73471bf0Spatrick }
172*73471bf0Spatrick 
173*73471bf0Spatrick static bool canSplitLoopBound(const Loop &L, const DominatorTree &DT,
174*73471bf0Spatrick                               ScalarEvolution &SE, ConditionInfo &Cond) {
175*73471bf0Spatrick   // Skip function with optsize.
176*73471bf0Spatrick   if (L.getHeader()->getParent()->hasOptSize())
177*73471bf0Spatrick     return false;
178*73471bf0Spatrick 
179*73471bf0Spatrick   // Split only innermost loop.
180*73471bf0Spatrick   if (!L.isInnermost())
181*73471bf0Spatrick     return false;
182*73471bf0Spatrick 
183*73471bf0Spatrick   // Check loop is in simplified form.
184*73471bf0Spatrick   if (!L.isLoopSimplifyForm())
185*73471bf0Spatrick     return false;
186*73471bf0Spatrick 
187*73471bf0Spatrick   // Check loop is in LCSSA form.
188*73471bf0Spatrick   if (!L.isLCSSAForm(DT))
189*73471bf0Spatrick     return false;
190*73471bf0Spatrick 
191*73471bf0Spatrick   // Skip loop that cannot be cloned.
192*73471bf0Spatrick   if (!L.isSafeToClone())
193*73471bf0Spatrick     return false;
194*73471bf0Spatrick 
195*73471bf0Spatrick   BasicBlock *ExitingBB = L.getExitingBlock();
196*73471bf0Spatrick   // Assumed only one exiting block.
197*73471bf0Spatrick   if (!ExitingBB)
198*73471bf0Spatrick     return false;
199*73471bf0Spatrick 
200*73471bf0Spatrick   BranchInst *ExitingBI = dyn_cast<BranchInst>(ExitingBB->getTerminator());
201*73471bf0Spatrick   if (!ExitingBI)
202*73471bf0Spatrick     return false;
203*73471bf0Spatrick 
204*73471bf0Spatrick   // Allowed only conditional branch with ICmp.
205*73471bf0Spatrick   if (!isProcessableCondBI(SE, ExitingBI))
206*73471bf0Spatrick     return false;
207*73471bf0Spatrick 
208*73471bf0Spatrick   // Check the condition is processable.
209*73471bf0Spatrick   ICmpInst *ICmp = cast<ICmpInst>(ExitingBI->getCondition());
210*73471bf0Spatrick   if (!hasProcessableCondition(L, SE, ICmp, Cond, /*IsExitCond*/ true))
211*73471bf0Spatrick     return false;
212*73471bf0Spatrick 
213*73471bf0Spatrick   Cond.BI = ExitingBI;
214*73471bf0Spatrick   return true;
215*73471bf0Spatrick }
216*73471bf0Spatrick 
217*73471bf0Spatrick static bool isProfitableToTransform(const Loop &L, const BranchInst *BI) {
218*73471bf0Spatrick   // If the conditional branch splits a loop into two halves, we could
219*73471bf0Spatrick   // generally say it is profitable.
220*73471bf0Spatrick   //
221*73471bf0Spatrick   // ToDo: Add more profitable cases here.
222*73471bf0Spatrick 
223*73471bf0Spatrick   // Check this branch causes diamond CFG.
224*73471bf0Spatrick   BasicBlock *Succ0 = BI->getSuccessor(0);
225*73471bf0Spatrick   BasicBlock *Succ1 = BI->getSuccessor(1);
226*73471bf0Spatrick 
227*73471bf0Spatrick   BasicBlock *Succ0Succ = Succ0->getSingleSuccessor();
228*73471bf0Spatrick   BasicBlock *Succ1Succ = Succ1->getSingleSuccessor();
229*73471bf0Spatrick   if (!Succ0Succ || !Succ1Succ || Succ0Succ != Succ1Succ)
230*73471bf0Spatrick     return false;
231*73471bf0Spatrick 
232*73471bf0Spatrick   // ToDo: Calculate each successor's instruction cost.
233*73471bf0Spatrick 
234*73471bf0Spatrick   return true;
235*73471bf0Spatrick }
236*73471bf0Spatrick 
237*73471bf0Spatrick static BranchInst *findSplitCandidate(const Loop &L, ScalarEvolution &SE,
238*73471bf0Spatrick                                       ConditionInfo &ExitingCond,
239*73471bf0Spatrick                                       ConditionInfo &SplitCandidateCond) {
240*73471bf0Spatrick   for (auto *BB : L.blocks()) {
241*73471bf0Spatrick     // Skip condition of backedge.
242*73471bf0Spatrick     if (L.getLoopLatch() == BB)
243*73471bf0Spatrick       continue;
244*73471bf0Spatrick 
245*73471bf0Spatrick     auto *BI = dyn_cast<BranchInst>(BB->getTerminator());
246*73471bf0Spatrick     if (!BI)
247*73471bf0Spatrick       continue;
248*73471bf0Spatrick 
249*73471bf0Spatrick     // Check conditional branch with ICmp.
250*73471bf0Spatrick     if (!isProcessableCondBI(SE, BI))
251*73471bf0Spatrick       continue;
252*73471bf0Spatrick 
253*73471bf0Spatrick     // Skip loop invariant condition.
254*73471bf0Spatrick     if (L.isLoopInvariant(BI->getCondition()))
255*73471bf0Spatrick       continue;
256*73471bf0Spatrick 
257*73471bf0Spatrick     // Check the condition is processable.
258*73471bf0Spatrick     ICmpInst *ICmp = cast<ICmpInst>(BI->getCondition());
259*73471bf0Spatrick     if (!hasProcessableCondition(L, SE, ICmp, SplitCandidateCond,
260*73471bf0Spatrick                                  /*IsExitCond*/ false))
261*73471bf0Spatrick       continue;
262*73471bf0Spatrick 
263*73471bf0Spatrick     if (ExitingCond.BoundSCEV->getType() !=
264*73471bf0Spatrick         SplitCandidateCond.BoundSCEV->getType())
265*73471bf0Spatrick       continue;
266*73471bf0Spatrick 
267*73471bf0Spatrick     SplitCandidateCond.BI = BI;
268*73471bf0Spatrick     return BI;
269*73471bf0Spatrick   }
270*73471bf0Spatrick 
271*73471bf0Spatrick   return nullptr;
272*73471bf0Spatrick }
273*73471bf0Spatrick 
274*73471bf0Spatrick static bool splitLoopBound(Loop &L, DominatorTree &DT, LoopInfo &LI,
275*73471bf0Spatrick                            ScalarEvolution &SE, LPMUpdater &U) {
276*73471bf0Spatrick   ConditionInfo SplitCandidateCond;
277*73471bf0Spatrick   ConditionInfo ExitingCond;
278*73471bf0Spatrick 
279*73471bf0Spatrick   // Check we can split this loop's bound.
280*73471bf0Spatrick   if (!canSplitLoopBound(L, DT, SE, ExitingCond))
281*73471bf0Spatrick     return false;
282*73471bf0Spatrick 
283*73471bf0Spatrick   if (!findSplitCandidate(L, SE, ExitingCond, SplitCandidateCond))
284*73471bf0Spatrick     return false;
285*73471bf0Spatrick 
286*73471bf0Spatrick   if (!isProfitableToTransform(L, SplitCandidateCond.BI))
287*73471bf0Spatrick     return false;
288*73471bf0Spatrick 
289*73471bf0Spatrick   // Now, we have a split candidate. Let's build a form as below.
290*73471bf0Spatrick   //    +--------------------+
291*73471bf0Spatrick   //    |     preheader      |
292*73471bf0Spatrick   //    |  set up newbound   |
293*73471bf0Spatrick   //    +--------------------+
294*73471bf0Spatrick   //             |     /----------------\
295*73471bf0Spatrick   //    +--------v----v------+          |
296*73471bf0Spatrick   //    |      header        |---\      |
297*73471bf0Spatrick   //    | with true condition|   |      |
298*73471bf0Spatrick   //    +--------------------+   |      |
299*73471bf0Spatrick   //             |               |      |
300*73471bf0Spatrick   //    +--------v-----------+   |      |
301*73471bf0Spatrick   //    |     if.then.BB     |   |      |
302*73471bf0Spatrick   //    +--------------------+   |      |
303*73471bf0Spatrick   //             |               |      |
304*73471bf0Spatrick   //    +--------v-----------<---/      |
305*73471bf0Spatrick   //    |       latch        >----------/
306*73471bf0Spatrick   //    |   with newbound    |
307*73471bf0Spatrick   //    +--------------------+
308*73471bf0Spatrick   //             |
309*73471bf0Spatrick   //    +--------v-----------+
310*73471bf0Spatrick   //    |     preheader2     |--------------\
311*73471bf0Spatrick   //    | if (AddRec i !=    |              |
312*73471bf0Spatrick   //    |     org bound)     |              |
313*73471bf0Spatrick   //    +--------------------+              |
314*73471bf0Spatrick   //             |     /----------------\   |
315*73471bf0Spatrick   //    +--------v----v------+          |   |
316*73471bf0Spatrick   //    |      header2       |---\      |   |
317*73471bf0Spatrick   //    | conditional branch |   |      |   |
318*73471bf0Spatrick   //    |with false condition|   |      |   |
319*73471bf0Spatrick   //    +--------------------+   |      |   |
320*73471bf0Spatrick   //             |               |      |   |
321*73471bf0Spatrick   //    +--------v-----------+   |      |   |
322*73471bf0Spatrick   //    |    if.then.BB2     |   |      |   |
323*73471bf0Spatrick   //    +--------------------+   |      |   |
324*73471bf0Spatrick   //             |               |      |   |
325*73471bf0Spatrick   //    +--------v-----------<---/      |   |
326*73471bf0Spatrick   //    |       latch2       >----------/   |
327*73471bf0Spatrick   //    |   with org bound   |              |
328*73471bf0Spatrick   //    +--------v-----------+              |
329*73471bf0Spatrick   //             |                          |
330*73471bf0Spatrick   //             |  +---------------+       |
331*73471bf0Spatrick   //             +-->     exit      <-------/
332*73471bf0Spatrick   //                +---------------+
333*73471bf0Spatrick 
334*73471bf0Spatrick   // Let's create post loop.
335*73471bf0Spatrick   SmallVector<BasicBlock *, 8> PostLoopBlocks;
336*73471bf0Spatrick   Loop *PostLoop;
337*73471bf0Spatrick   ValueToValueMapTy VMap;
338*73471bf0Spatrick   BasicBlock *PreHeader = L.getLoopPreheader();
339*73471bf0Spatrick   BasicBlock *SplitLoopPH = SplitEdge(PreHeader, L.getHeader(), &DT, &LI);
340*73471bf0Spatrick   PostLoop = cloneLoopWithPreheader(L.getExitBlock(), SplitLoopPH, &L, VMap,
341*73471bf0Spatrick                                     ".split", &LI, &DT, PostLoopBlocks);
342*73471bf0Spatrick   remapInstructionsInBlocks(PostLoopBlocks, VMap);
343*73471bf0Spatrick 
344*73471bf0Spatrick   // Add conditional branch to check we can skip post-loop in its preheader.
345*73471bf0Spatrick   BasicBlock *PostLoopPreHeader = PostLoop->getLoopPreheader();
346*73471bf0Spatrick   IRBuilder<> Builder(PostLoopPreHeader);
347*73471bf0Spatrick   Instruction *OrigBI = PostLoopPreHeader->getTerminator();
348*73471bf0Spatrick   ICmpInst::Predicate Pred = ICmpInst::ICMP_NE;
349*73471bf0Spatrick   Value *Cond =
350*73471bf0Spatrick       Builder.CreateICmp(Pred, ExitingCond.AddRecValue, ExitingCond.BoundValue);
351*73471bf0Spatrick   Builder.CreateCondBr(Cond, PostLoop->getHeader(), PostLoop->getExitBlock());
352*73471bf0Spatrick   OrigBI->eraseFromParent();
353*73471bf0Spatrick 
354*73471bf0Spatrick   // Create new loop bound and add it into preheader of pre-loop.
355*73471bf0Spatrick   const SCEV *NewBoundSCEV = ExitingCond.BoundSCEV;
356*73471bf0Spatrick   const SCEV *SplitBoundSCEV = SplitCandidateCond.BoundSCEV;
357*73471bf0Spatrick   NewBoundSCEV = ICmpInst::isSigned(ExitingCond.Pred)
358*73471bf0Spatrick                      ? SE.getSMinExpr(NewBoundSCEV, SplitBoundSCEV)
359*73471bf0Spatrick                      : SE.getUMinExpr(NewBoundSCEV, SplitBoundSCEV);
360*73471bf0Spatrick 
361*73471bf0Spatrick   SCEVExpander Expander(
362*73471bf0Spatrick       SE, L.getHeader()->getParent()->getParent()->getDataLayout(), "split");
363*73471bf0Spatrick   Instruction *InsertPt = SplitLoopPH->getTerminator();
364*73471bf0Spatrick   Value *NewBoundValue =
365*73471bf0Spatrick       Expander.expandCodeFor(NewBoundSCEV, NewBoundSCEV->getType(), InsertPt);
366*73471bf0Spatrick   NewBoundValue->setName("new.bound");
367*73471bf0Spatrick 
368*73471bf0Spatrick   // Replace exiting bound value of pre-loop NewBound.
369*73471bf0Spatrick   ExitingCond.ICmp->setOperand(1, NewBoundValue);
370*73471bf0Spatrick 
371*73471bf0Spatrick   // Replace IV's start value of post-loop by NewBound.
372*73471bf0Spatrick   for (PHINode &PN : L.getHeader()->phis()) {
373*73471bf0Spatrick     // Find PHI with exiting condition from pre-loop.
374*73471bf0Spatrick     if (SE.isSCEVable(PN.getType()) && isa<SCEVAddRecExpr>(SE.getSCEV(&PN))) {
375*73471bf0Spatrick       for (Value *Op : PN.incoming_values()) {
376*73471bf0Spatrick         if (Op == ExitingCond.AddRecValue) {
377*73471bf0Spatrick           // Find cloned PHI for post-loop.
378*73471bf0Spatrick           PHINode *PostLoopPN = cast<PHINode>(VMap[&PN]);
379*73471bf0Spatrick           PostLoopPN->setIncomingValueForBlock(PostLoopPreHeader,
380*73471bf0Spatrick                                                NewBoundValue);
381*73471bf0Spatrick         }
382*73471bf0Spatrick       }
383*73471bf0Spatrick     }
384*73471bf0Spatrick   }
385*73471bf0Spatrick 
386*73471bf0Spatrick   // Replace SplitCandidateCond.BI's condition of pre-loop by True.
387*73471bf0Spatrick   LLVMContext &Context = PreHeader->getContext();
388*73471bf0Spatrick   SplitCandidateCond.BI->setCondition(ConstantInt::getTrue(Context));
389*73471bf0Spatrick 
390*73471bf0Spatrick   // Replace cloned SplitCandidateCond.BI's condition in post-loop by False.
391*73471bf0Spatrick   BranchInst *ClonedSplitCandidateBI =
392*73471bf0Spatrick       cast<BranchInst>(VMap[SplitCandidateCond.BI]);
393*73471bf0Spatrick   ClonedSplitCandidateBI->setCondition(ConstantInt::getFalse(Context));
394*73471bf0Spatrick 
395*73471bf0Spatrick   // Replace exit branch target of pre-loop by post-loop's preheader.
396*73471bf0Spatrick   if (L.getExitBlock() == ExitingCond.BI->getSuccessor(0))
397*73471bf0Spatrick     ExitingCond.BI->setSuccessor(0, PostLoopPreHeader);
398*73471bf0Spatrick   else
399*73471bf0Spatrick     ExitingCond.BI->setSuccessor(1, PostLoopPreHeader);
400*73471bf0Spatrick 
401*73471bf0Spatrick   // Update dominator tree.
402*73471bf0Spatrick   DT.changeImmediateDominator(PostLoopPreHeader, L.getExitingBlock());
403*73471bf0Spatrick   DT.changeImmediateDominator(PostLoop->getExitBlock(), PostLoopPreHeader);
404*73471bf0Spatrick 
405*73471bf0Spatrick   // Invalidate cached SE information.
406*73471bf0Spatrick   SE.forgetLoop(&L);
407*73471bf0Spatrick 
408*73471bf0Spatrick   // Canonicalize loops.
409*73471bf0Spatrick   // TODO: Try to update LCSSA information according to above change.
410*73471bf0Spatrick   formLCSSA(L, DT, &LI, &SE);
411*73471bf0Spatrick   simplifyLoop(&L, &DT, &LI, &SE, nullptr, nullptr, true);
412*73471bf0Spatrick   formLCSSA(*PostLoop, DT, &LI, &SE);
413*73471bf0Spatrick   simplifyLoop(PostLoop, &DT, &LI, &SE, nullptr, nullptr, true);
414*73471bf0Spatrick 
415*73471bf0Spatrick   // Add new post-loop to loop pass manager.
416*73471bf0Spatrick   U.addSiblingLoops(PostLoop);
417*73471bf0Spatrick 
418*73471bf0Spatrick   return true;
419*73471bf0Spatrick }
420*73471bf0Spatrick 
421*73471bf0Spatrick PreservedAnalyses LoopBoundSplitPass::run(Loop &L, LoopAnalysisManager &AM,
422*73471bf0Spatrick                                           LoopStandardAnalysisResults &AR,
423*73471bf0Spatrick                                           LPMUpdater &U) {
424*73471bf0Spatrick   Function &F = *L.getHeader()->getParent();
425*73471bf0Spatrick   (void)F;
426*73471bf0Spatrick 
427*73471bf0Spatrick   LLVM_DEBUG(dbgs() << "Spliting bound of loop in " << F.getName() << ": " << L
428*73471bf0Spatrick                     << "\n");
429*73471bf0Spatrick 
430*73471bf0Spatrick   if (!splitLoopBound(L, AR.DT, AR.LI, AR.SE, U))
431*73471bf0Spatrick     return PreservedAnalyses::all();
432*73471bf0Spatrick 
433*73471bf0Spatrick   assert(AR.DT.verify(DominatorTree::VerificationLevel::Fast));
434*73471bf0Spatrick   AR.LI.verify(AR.DT);
435*73471bf0Spatrick 
436*73471bf0Spatrick   return getLoopPassPreservedAnalyses();
437*73471bf0Spatrick }
438*73471bf0Spatrick 
439*73471bf0Spatrick } // end namespace llvm
440