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