1 //===-- LoopUtils.cpp - Loop Utility functions -------------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file defines common loop utility functions.
10 //
11 //===----------------------------------------------------------------------===//
12 
13 #include "llvm/Transforms/Utils/LoopUtils.h"
14 #include "llvm/ADT/DenseSet.h"
15 #include "llvm/ADT/Optional.h"
16 #include "llvm/ADT/PriorityWorklist.h"
17 #include "llvm/ADT/ScopeExit.h"
18 #include "llvm/ADT/SetVector.h"
19 #include "llvm/ADT/SmallPtrSet.h"
20 #include "llvm/ADT/SmallVector.h"
21 #include "llvm/Analysis/AliasAnalysis.h"
22 #include "llvm/Analysis/BasicAliasAnalysis.h"
23 #include "llvm/Analysis/DomTreeUpdater.h"
24 #include "llvm/Analysis/GlobalsModRef.h"
25 #include "llvm/Analysis/InstructionSimplify.h"
26 #include "llvm/Analysis/LoopAccessAnalysis.h"
27 #include "llvm/Analysis/LoopInfo.h"
28 #include "llvm/Analysis/LoopPass.h"
29 #include "llvm/Analysis/MemorySSA.h"
30 #include "llvm/Analysis/MemorySSAUpdater.h"
31 #include "llvm/Analysis/MustExecute.h"
32 #include "llvm/Analysis/ScalarEvolution.h"
33 #include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h"
34 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
35 #include "llvm/Analysis/TargetTransformInfo.h"
36 #include "llvm/Analysis/ValueTracking.h"
37 #include "llvm/IR/DIBuilder.h"
38 #include "llvm/IR/Dominators.h"
39 #include "llvm/IR/Instructions.h"
40 #include "llvm/IR/IntrinsicInst.h"
41 #include "llvm/IR/MDBuilder.h"
42 #include "llvm/IR/Module.h"
43 #include "llvm/IR/Operator.h"
44 #include "llvm/IR/PatternMatch.h"
45 #include "llvm/IR/ValueHandle.h"
46 #include "llvm/InitializePasses.h"
47 #include "llvm/Pass.h"
48 #include "llvm/Support/Debug.h"
49 #include "llvm/Support/KnownBits.h"
50 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
51 #include "llvm/Transforms/Utils/Local.h"
52 #include "llvm/Transforms/Utils/ScalarEvolutionExpander.h"
53 
54 using namespace llvm;
55 using namespace llvm::PatternMatch;
56 
57 static cl::opt<bool> ForceReductionIntrinsic(
58     "force-reduction-intrinsics", cl::Hidden,
59     cl::desc("Force creating reduction intrinsics for testing."),
60     cl::init(false));
61 
62 #define DEBUG_TYPE "loop-utils"
63 
64 static const char *LLVMLoopDisableNonforced = "llvm.loop.disable_nonforced";
65 static const char *LLVMLoopDisableLICM = "llvm.licm.disable";
66 static const char *LLVMLoopMustProgress = "llvm.loop.mustprogress";
67 
formDedicatedExitBlocks(Loop * L,DominatorTree * DT,LoopInfo * LI,MemorySSAUpdater * MSSAU,bool PreserveLCSSA)68 bool llvm::formDedicatedExitBlocks(Loop *L, DominatorTree *DT, LoopInfo *LI,
69                                    MemorySSAUpdater *MSSAU,
70                                    bool PreserveLCSSA) {
71   bool Changed = false;
72 
73   // We re-use a vector for the in-loop predecesosrs.
74   SmallVector<BasicBlock *, 4> InLoopPredecessors;
75 
76   auto RewriteExit = [&](BasicBlock *BB) {
77     assert(InLoopPredecessors.empty() &&
78            "Must start with an empty predecessors list!");
79     auto Cleanup = make_scope_exit([&] { InLoopPredecessors.clear(); });
80 
81     // See if there are any non-loop predecessors of this exit block and
82     // keep track of the in-loop predecessors.
83     bool IsDedicatedExit = true;
84     for (auto *PredBB : predecessors(BB))
85       if (L->contains(PredBB)) {
86         if (isa<IndirectBrInst>(PredBB->getTerminator()))
87           // We cannot rewrite exiting edges from an indirectbr.
88           return false;
89         if (isa<CallBrInst>(PredBB->getTerminator()))
90           // We cannot rewrite exiting edges from a callbr.
91           return false;
92 
93         InLoopPredecessors.push_back(PredBB);
94       } else {
95         IsDedicatedExit = false;
96       }
97 
98     assert(!InLoopPredecessors.empty() && "Must have *some* loop predecessor!");
99 
100     // Nothing to do if this is already a dedicated exit.
101     if (IsDedicatedExit)
102       return false;
103 
104     auto *NewExitBB = SplitBlockPredecessors(
105         BB, InLoopPredecessors, ".loopexit", DT, LI, MSSAU, PreserveLCSSA);
106 
107     if (!NewExitBB)
108       LLVM_DEBUG(
109           dbgs() << "WARNING: Can't create a dedicated exit block for loop: "
110                  << *L << "\n");
111     else
112       LLVM_DEBUG(dbgs() << "LoopSimplify: Creating dedicated exit block "
113                         << NewExitBB->getName() << "\n");
114     return true;
115   };
116 
117   // Walk the exit blocks directly rather than building up a data structure for
118   // them, but only visit each one once.
119   SmallPtrSet<BasicBlock *, 4> Visited;
120   for (auto *BB : L->blocks())
121     for (auto *SuccBB : successors(BB)) {
122       // We're looking for exit blocks so skip in-loop successors.
123       if (L->contains(SuccBB))
124         continue;
125 
126       // Visit each exit block exactly once.
127       if (!Visited.insert(SuccBB).second)
128         continue;
129 
130       Changed |= RewriteExit(SuccBB);
131     }
132 
133   return Changed;
134 }
135 
136 /// Returns the instructions that use values defined in the loop.
findDefsUsedOutsideOfLoop(Loop * L)137 SmallVector<Instruction *, 8> llvm::findDefsUsedOutsideOfLoop(Loop *L) {
138   SmallVector<Instruction *, 8> UsedOutside;
139 
140   for (auto *Block : L->getBlocks())
141     // FIXME: I believe that this could use copy_if if the Inst reference could
142     // be adapted into a pointer.
143     for (auto &Inst : *Block) {
144       auto Users = Inst.users();
145       if (any_of(Users, [&](User *U) {
146             auto *Use = cast<Instruction>(U);
147             return !L->contains(Use->getParent());
148           }))
149         UsedOutside.push_back(&Inst);
150     }
151 
152   return UsedOutside;
153 }
154 
getLoopAnalysisUsage(AnalysisUsage & AU)155 void llvm::getLoopAnalysisUsage(AnalysisUsage &AU) {
156   // By definition, all loop passes need the LoopInfo analysis and the
157   // Dominator tree it depends on. Because they all participate in the loop
158   // pass manager, they must also preserve these.
159   AU.addRequired<DominatorTreeWrapperPass>();
160   AU.addPreserved<DominatorTreeWrapperPass>();
161   AU.addRequired<LoopInfoWrapperPass>();
162   AU.addPreserved<LoopInfoWrapperPass>();
163 
164   // We must also preserve LoopSimplify and LCSSA. We locally access their IDs
165   // here because users shouldn't directly get them from this header.
166   extern char &LoopSimplifyID;
167   extern char &LCSSAID;
168   AU.addRequiredID(LoopSimplifyID);
169   AU.addPreservedID(LoopSimplifyID);
170   AU.addRequiredID(LCSSAID);
171   AU.addPreservedID(LCSSAID);
172   // This is used in the LPPassManager to perform LCSSA verification on passes
173   // which preserve lcssa form
174   AU.addRequired<LCSSAVerificationPass>();
175   AU.addPreserved<LCSSAVerificationPass>();
176 
177   // Loop passes are designed to run inside of a loop pass manager which means
178   // that any function analyses they require must be required by the first loop
179   // pass in the manager (so that it is computed before the loop pass manager
180   // runs) and preserved by all loop pasess in the manager. To make this
181   // reasonably robust, the set needed for most loop passes is maintained here.
182   // If your loop pass requires an analysis not listed here, you will need to
183   // carefully audit the loop pass manager nesting structure that results.
184   AU.addRequired<AAResultsWrapperPass>();
185   AU.addPreserved<AAResultsWrapperPass>();
186   AU.addPreserved<BasicAAWrapperPass>();
187   AU.addPreserved<GlobalsAAWrapperPass>();
188   AU.addPreserved<SCEVAAWrapperPass>();
189   AU.addRequired<ScalarEvolutionWrapperPass>();
190   AU.addPreserved<ScalarEvolutionWrapperPass>();
191   // FIXME: When all loop passes preserve MemorySSA, it can be required and
192   // preserved here instead of the individual handling in each pass.
193 }
194 
195 /// Manually defined generic "LoopPass" dependency initialization. This is used
196 /// to initialize the exact set of passes from above in \c
197 /// getLoopAnalysisUsage. It can be used within a loop pass's initialization
198 /// with:
199 ///
200 ///   INITIALIZE_PASS_DEPENDENCY(LoopPass)
201 ///
202 /// As-if "LoopPass" were a pass.
initializeLoopPassPass(PassRegistry & Registry)203 void llvm::initializeLoopPassPass(PassRegistry &Registry) {
204   INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
205   INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
206   INITIALIZE_PASS_DEPENDENCY(LoopSimplify)
207   INITIALIZE_PASS_DEPENDENCY(LCSSAWrapperPass)
208   INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
209   INITIALIZE_PASS_DEPENDENCY(BasicAAWrapperPass)
210   INITIALIZE_PASS_DEPENDENCY(GlobalsAAWrapperPass)
211   INITIALIZE_PASS_DEPENDENCY(SCEVAAWrapperPass)
212   INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass)
213   INITIALIZE_PASS_DEPENDENCY(MemorySSAWrapperPass)
214 }
215 
216 /// Create MDNode for input string.
createStringMetadata(Loop * TheLoop,StringRef Name,unsigned V)217 static MDNode *createStringMetadata(Loop *TheLoop, StringRef Name, unsigned V) {
218   LLVMContext &Context = TheLoop->getHeader()->getContext();
219   Metadata *MDs[] = {
220       MDString::get(Context, Name),
221       ConstantAsMetadata::get(ConstantInt::get(Type::getInt32Ty(Context), V))};
222   return MDNode::get(Context, MDs);
223 }
224 
225 /// Set input string into loop metadata by keeping other values intact.
226 /// If the string is already in loop metadata update value if it is
227 /// different.
addStringMetadataToLoop(Loop * TheLoop,const char * StringMD,unsigned V)228 void llvm::addStringMetadataToLoop(Loop *TheLoop, const char *StringMD,
229                                    unsigned V) {
230   SmallVector<Metadata *, 4> MDs(1);
231   // If the loop already has metadata, retain it.
232   MDNode *LoopID = TheLoop->getLoopID();
233   if (LoopID) {
234     for (unsigned i = 1, ie = LoopID->getNumOperands(); i < ie; ++i) {
235       MDNode *Node = cast<MDNode>(LoopID->getOperand(i));
236       // If it is of form key = value, try to parse it.
237       if (Node->getNumOperands() == 2) {
238         MDString *S = dyn_cast<MDString>(Node->getOperand(0));
239         if (S && S->getString().equals(StringMD)) {
240           ConstantInt *IntMD =
241               mdconst::extract_or_null<ConstantInt>(Node->getOperand(1));
242           if (IntMD && IntMD->getSExtValue() == V)
243             // It is already in place. Do nothing.
244             return;
245           // We need to update the value, so just skip it here and it will
246           // be added after copying other existed nodes.
247           continue;
248         }
249       }
250       MDs.push_back(Node);
251     }
252   }
253   // Add new metadata.
254   MDs.push_back(createStringMetadata(TheLoop, StringMD, V));
255   // Replace current metadata node with new one.
256   LLVMContext &Context = TheLoop->getHeader()->getContext();
257   MDNode *NewLoopID = MDNode::get(Context, MDs);
258   // Set operand 0 to refer to the loop id itself.
259   NewLoopID->replaceOperandWith(0, NewLoopID);
260   TheLoop->setLoopID(NewLoopID);
261 }
262 
263 /// Find string metadata for loop
264 ///
265 /// If it has a value (e.g. {"llvm.distribute", 1} return the value as an
266 /// operand or null otherwise.  If the string metadata is not found return
267 /// Optional's not-a-value.
findStringMetadataForLoop(const Loop * TheLoop,StringRef Name)268 Optional<const MDOperand *> llvm::findStringMetadataForLoop(const Loop *TheLoop,
269                                                             StringRef Name) {
270   MDNode *MD = findOptionMDForLoop(TheLoop, Name);
271   if (!MD)
272     return None;
273   switch (MD->getNumOperands()) {
274   case 1:
275     return nullptr;
276   case 2:
277     return &MD->getOperand(1);
278   default:
279     llvm_unreachable("loop metadata has 0 or 1 operand");
280   }
281 }
282 
getOptionalBoolLoopAttribute(const Loop * TheLoop,StringRef Name)283 static Optional<bool> getOptionalBoolLoopAttribute(const Loop *TheLoop,
284                                                    StringRef Name) {
285   MDNode *MD = findOptionMDForLoop(TheLoop, Name);
286   if (!MD)
287     return None;
288   switch (MD->getNumOperands()) {
289   case 1:
290     // When the value is absent it is interpreted as 'attribute set'.
291     return true;
292   case 2:
293     if (ConstantInt *IntMD =
294             mdconst::extract_or_null<ConstantInt>(MD->getOperand(1).get()))
295       return IntMD->getZExtValue();
296     return true;
297   }
298   llvm_unreachable("unexpected number of options");
299 }
300 
getBooleanLoopAttribute(const Loop * TheLoop,StringRef Name)301 bool llvm::getBooleanLoopAttribute(const Loop *TheLoop, StringRef Name) {
302   return getOptionalBoolLoopAttribute(TheLoop, Name).getValueOr(false);
303 }
304 
305 Optional<ElementCount>
getOptionalElementCountLoopAttribute(Loop * TheLoop)306 llvm::getOptionalElementCountLoopAttribute(Loop *TheLoop) {
307   Optional<int> Width =
308       getOptionalIntLoopAttribute(TheLoop, "llvm.loop.vectorize.width");
309 
310   if (Width.hasValue()) {
311     Optional<int> IsScalable = getOptionalIntLoopAttribute(
312         TheLoop, "llvm.loop.vectorize.scalable.enable");
313     return ElementCount::get(*Width, IsScalable.getValueOr(false));
314   }
315 
316   return None;
317 }
318 
getOptionalIntLoopAttribute(Loop * TheLoop,StringRef Name)319 llvm::Optional<int> llvm::getOptionalIntLoopAttribute(Loop *TheLoop,
320                                                       StringRef Name) {
321   const MDOperand *AttrMD =
322       findStringMetadataForLoop(TheLoop, Name).getValueOr(nullptr);
323   if (!AttrMD)
324     return None;
325 
326   ConstantInt *IntMD = mdconst::extract_or_null<ConstantInt>(AttrMD->get());
327   if (!IntMD)
328     return None;
329 
330   return IntMD->getSExtValue();
331 }
332 
makeFollowupLoopID(MDNode * OrigLoopID,ArrayRef<StringRef> FollowupOptions,const char * InheritOptionsExceptPrefix,bool AlwaysNew)333 Optional<MDNode *> llvm::makeFollowupLoopID(
334     MDNode *OrigLoopID, ArrayRef<StringRef> FollowupOptions,
335     const char *InheritOptionsExceptPrefix, bool AlwaysNew) {
336   if (!OrigLoopID) {
337     if (AlwaysNew)
338       return nullptr;
339     return None;
340   }
341 
342   assert(OrigLoopID->getOperand(0) == OrigLoopID);
343 
344   bool InheritAllAttrs = !InheritOptionsExceptPrefix;
345   bool InheritSomeAttrs =
346       InheritOptionsExceptPrefix && InheritOptionsExceptPrefix[0] != '\0';
347   SmallVector<Metadata *, 8> MDs;
348   MDs.push_back(nullptr);
349 
350   bool Changed = false;
351   if (InheritAllAttrs || InheritSomeAttrs) {
352     for (const MDOperand &Existing : drop_begin(OrigLoopID->operands())) {
353       MDNode *Op = cast<MDNode>(Existing.get());
354 
355       auto InheritThisAttribute = [InheritSomeAttrs,
356                                    InheritOptionsExceptPrefix](MDNode *Op) {
357         if (!InheritSomeAttrs)
358           return false;
359 
360         // Skip malformatted attribute metadata nodes.
361         if (Op->getNumOperands() == 0)
362           return true;
363         Metadata *NameMD = Op->getOperand(0).get();
364         if (!isa<MDString>(NameMD))
365           return true;
366         StringRef AttrName = cast<MDString>(NameMD)->getString();
367 
368         // Do not inherit excluded attributes.
369         return !AttrName.startswith(InheritOptionsExceptPrefix);
370       };
371 
372       if (InheritThisAttribute(Op))
373         MDs.push_back(Op);
374       else
375         Changed = true;
376     }
377   } else {
378     // Modified if we dropped at least one attribute.
379     Changed = OrigLoopID->getNumOperands() > 1;
380   }
381 
382   bool HasAnyFollowup = false;
383   for (StringRef OptionName : FollowupOptions) {
384     MDNode *FollowupNode = findOptionMDForLoopID(OrigLoopID, OptionName);
385     if (!FollowupNode)
386       continue;
387 
388     HasAnyFollowup = true;
389     for (const MDOperand &Option : drop_begin(FollowupNode->operands())) {
390       MDs.push_back(Option.get());
391       Changed = true;
392     }
393   }
394 
395   // Attributes of the followup loop not specified explicity, so signal to the
396   // transformation pass to add suitable attributes.
397   if (!AlwaysNew && !HasAnyFollowup)
398     return None;
399 
400   // If no attributes were added or remove, the previous loop Id can be reused.
401   if (!AlwaysNew && !Changed)
402     return OrigLoopID;
403 
404   // No attributes is equivalent to having no !llvm.loop metadata at all.
405   if (MDs.size() == 1)
406     return nullptr;
407 
408   // Build the new loop ID.
409   MDTuple *FollowupLoopID = MDNode::get(OrigLoopID->getContext(), MDs);
410   FollowupLoopID->replaceOperandWith(0, FollowupLoopID);
411   return FollowupLoopID;
412 }
413 
hasDisableAllTransformsHint(const Loop * L)414 bool llvm::hasDisableAllTransformsHint(const Loop *L) {
415   return getBooleanLoopAttribute(L, LLVMLoopDisableNonforced);
416 }
417 
hasDisableLICMTransformsHint(const Loop * L)418 bool llvm::hasDisableLICMTransformsHint(const Loop *L) {
419   return getBooleanLoopAttribute(L, LLVMLoopDisableLICM);
420 }
421 
hasMustProgress(const Loop * L)422 bool llvm::hasMustProgress(const Loop *L) {
423   return getBooleanLoopAttribute(L, LLVMLoopMustProgress);
424 }
425 
hasUnrollTransformation(Loop * L)426 TransformationMode llvm::hasUnrollTransformation(Loop *L) {
427   if (getBooleanLoopAttribute(L, "llvm.loop.unroll.disable"))
428     return TM_SuppressedByUser;
429 
430   Optional<int> Count =
431       getOptionalIntLoopAttribute(L, "llvm.loop.unroll.count");
432   if (Count.hasValue())
433     return Count.getValue() == 1 ? TM_SuppressedByUser : TM_ForcedByUser;
434 
435   if (getBooleanLoopAttribute(L, "llvm.loop.unroll.enable"))
436     return TM_ForcedByUser;
437 
438   if (getBooleanLoopAttribute(L, "llvm.loop.unroll.full"))
439     return TM_ForcedByUser;
440 
441   if (hasDisableAllTransformsHint(L))
442     return TM_Disable;
443 
444   return TM_Unspecified;
445 }
446 
hasUnrollAndJamTransformation(Loop * L)447 TransformationMode llvm::hasUnrollAndJamTransformation(Loop *L) {
448   if (getBooleanLoopAttribute(L, "llvm.loop.unroll_and_jam.disable"))
449     return TM_SuppressedByUser;
450 
451   Optional<int> Count =
452       getOptionalIntLoopAttribute(L, "llvm.loop.unroll_and_jam.count");
453   if (Count.hasValue())
454     return Count.getValue() == 1 ? TM_SuppressedByUser : TM_ForcedByUser;
455 
456   if (getBooleanLoopAttribute(L, "llvm.loop.unroll_and_jam.enable"))
457     return TM_ForcedByUser;
458 
459   if (hasDisableAllTransformsHint(L))
460     return TM_Disable;
461 
462   return TM_Unspecified;
463 }
464 
hasVectorizeTransformation(Loop * L)465 TransformationMode llvm::hasVectorizeTransformation(Loop *L) {
466   Optional<bool> Enable =
467       getOptionalBoolLoopAttribute(L, "llvm.loop.vectorize.enable");
468 
469   if (Enable == false)
470     return TM_SuppressedByUser;
471 
472   Optional<ElementCount> VectorizeWidth =
473       getOptionalElementCountLoopAttribute(L);
474   Optional<int> InterleaveCount =
475       getOptionalIntLoopAttribute(L, "llvm.loop.interleave.count");
476 
477   // 'Forcing' vector width and interleave count to one effectively disables
478   // this tranformation.
479   if (Enable == true && VectorizeWidth && VectorizeWidth->isScalar() &&
480       InterleaveCount == 1)
481     return TM_SuppressedByUser;
482 
483   if (getBooleanLoopAttribute(L, "llvm.loop.isvectorized"))
484     return TM_Disable;
485 
486   if (Enable == true)
487     return TM_ForcedByUser;
488 
489   if ((VectorizeWidth && VectorizeWidth->isScalar()) && InterleaveCount == 1)
490     return TM_Disable;
491 
492   if ((VectorizeWidth && VectorizeWidth->isVector()) || InterleaveCount > 1)
493     return TM_Enable;
494 
495   if (hasDisableAllTransformsHint(L))
496     return TM_Disable;
497 
498   return TM_Unspecified;
499 }
500 
hasDistributeTransformation(Loop * L)501 TransformationMode llvm::hasDistributeTransformation(Loop *L) {
502   if (getBooleanLoopAttribute(L, "llvm.loop.distribute.enable"))
503     return TM_ForcedByUser;
504 
505   if (hasDisableAllTransformsHint(L))
506     return TM_Disable;
507 
508   return TM_Unspecified;
509 }
510 
hasLICMVersioningTransformation(Loop * L)511 TransformationMode llvm::hasLICMVersioningTransformation(Loop *L) {
512   if (getBooleanLoopAttribute(L, "llvm.loop.licm_versioning.disable"))
513     return TM_SuppressedByUser;
514 
515   if (hasDisableAllTransformsHint(L))
516     return TM_Disable;
517 
518   return TM_Unspecified;
519 }
520 
521 /// Does a BFS from a given node to all of its children inside a given loop.
522 /// The returned vector of nodes includes the starting point.
523 SmallVector<DomTreeNode *, 16>
collectChildrenInLoop(DomTreeNode * N,const Loop * CurLoop)524 llvm::collectChildrenInLoop(DomTreeNode *N, const Loop *CurLoop) {
525   SmallVector<DomTreeNode *, 16> Worklist;
526   auto AddRegionToWorklist = [&](DomTreeNode *DTN) {
527     // Only include subregions in the top level loop.
528     BasicBlock *BB = DTN->getBlock();
529     if (CurLoop->contains(BB))
530       Worklist.push_back(DTN);
531   };
532 
533   AddRegionToWorklist(N);
534 
535   for (size_t I = 0; I < Worklist.size(); I++) {
536     for (DomTreeNode *Child : Worklist[I]->children())
537       AddRegionToWorklist(Child);
538   }
539 
540   return Worklist;
541 }
542 
deleteDeadLoop(Loop * L,DominatorTree * DT,ScalarEvolution * SE,LoopInfo * LI,MemorySSA * MSSA)543 void llvm::deleteDeadLoop(Loop *L, DominatorTree *DT, ScalarEvolution *SE,
544                           LoopInfo *LI, MemorySSA *MSSA) {
545   assert((!DT || L->isLCSSAForm(*DT)) && "Expected LCSSA!");
546   auto *Preheader = L->getLoopPreheader();
547   assert(Preheader && "Preheader should exist!");
548 
549   std::unique_ptr<MemorySSAUpdater> MSSAU;
550   if (MSSA)
551     MSSAU = std::make_unique<MemorySSAUpdater>(MSSA);
552 
553   // Now that we know the removal is safe, remove the loop by changing the
554   // branch from the preheader to go to the single exit block.
555   //
556   // Because we're deleting a large chunk of code at once, the sequence in which
557   // we remove things is very important to avoid invalidation issues.
558 
559   // Tell ScalarEvolution that the loop is deleted. Do this before
560   // deleting the loop so that ScalarEvolution can look at the loop
561   // to determine what it needs to clean up.
562   if (SE)
563     SE->forgetLoop(L);
564 
565   auto *OldBr = dyn_cast<BranchInst>(Preheader->getTerminator());
566   assert(OldBr && "Preheader must end with a branch");
567   assert(OldBr->isUnconditional() && "Preheader must have a single successor");
568   // Connect the preheader to the exit block. Keep the old edge to the header
569   // around to perform the dominator tree update in two separate steps
570   // -- #1 insertion of the edge preheader -> exit and #2 deletion of the edge
571   // preheader -> header.
572   //
573   //
574   // 0.  Preheader          1.  Preheader           2.  Preheader
575   //        |                    |   |                   |
576   //        V                    |   V                   |
577   //      Header <--\            | Header <--\           | Header <--\
578   //       |  |     |            |  |  |     |           |  |  |     |
579   //       |  V     |            |  |  V     |           |  |  V     |
580   //       | Body --/            |  | Body --/           |  | Body --/
581   //       V                     V  V                    V  V
582   //      Exit                   Exit                    Exit
583   //
584   // By doing this is two separate steps we can perform the dominator tree
585   // update without using the batch update API.
586   //
587   // Even when the loop is never executed, we cannot remove the edge from the
588   // source block to the exit block. Consider the case where the unexecuted loop
589   // branches back to an outer loop. If we deleted the loop and removed the edge
590   // coming to this inner loop, this will break the outer loop structure (by
591   // deleting the backedge of the outer loop). If the outer loop is indeed a
592   // non-loop, it will be deleted in a future iteration of loop deletion pass.
593   IRBuilder<> Builder(OldBr);
594 
595   auto *ExitBlock = L->getUniqueExitBlock();
596   DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Eager);
597   if (ExitBlock) {
598     assert(ExitBlock && "Should have a unique exit block!");
599     assert(L->hasDedicatedExits() && "Loop should have dedicated exits!");
600 
601     Builder.CreateCondBr(Builder.getFalse(), L->getHeader(), ExitBlock);
602     // Remove the old branch. The conditional branch becomes a new terminator.
603     OldBr->eraseFromParent();
604 
605     // Rewrite phis in the exit block to get their inputs from the Preheader
606     // instead of the exiting block.
607     for (PHINode &P : ExitBlock->phis()) {
608       // Set the zero'th element of Phi to be from the preheader and remove all
609       // other incoming values. Given the loop has dedicated exits, all other
610       // incoming values must be from the exiting blocks.
611       int PredIndex = 0;
612       P.setIncomingBlock(PredIndex, Preheader);
613       // Removes all incoming values from all other exiting blocks (including
614       // duplicate values from an exiting block).
615       // Nuke all entries except the zero'th entry which is the preheader entry.
616       // NOTE! We need to remove Incoming Values in the reverse order as done
617       // below, to keep the indices valid for deletion (removeIncomingValues
618       // updates getNumIncomingValues and shifts all values down into the
619       // operand being deleted).
620       for (unsigned i = 0, e = P.getNumIncomingValues() - 1; i != e; ++i)
621         P.removeIncomingValue(e - i, false);
622 
623       assert((P.getNumIncomingValues() == 1 &&
624               P.getIncomingBlock(PredIndex) == Preheader) &&
625              "Should have exactly one value and that's from the preheader!");
626     }
627 
628     if (DT) {
629       DTU.applyUpdates({{DominatorTree::Insert, Preheader, ExitBlock}});
630       if (MSSA) {
631         MSSAU->applyUpdates({{DominatorTree::Insert, Preheader, ExitBlock}},
632                             *DT);
633         if (VerifyMemorySSA)
634           MSSA->verifyMemorySSA();
635       }
636     }
637 
638     // Disconnect the loop body by branching directly to its exit.
639     Builder.SetInsertPoint(Preheader->getTerminator());
640     Builder.CreateBr(ExitBlock);
641     // Remove the old branch.
642     Preheader->getTerminator()->eraseFromParent();
643   } else {
644     assert(L->hasNoExitBlocks() &&
645            "Loop should have either zero or one exit blocks.");
646 
647     Builder.SetInsertPoint(OldBr);
648     Builder.CreateUnreachable();
649     Preheader->getTerminator()->eraseFromParent();
650   }
651 
652   if (DT) {
653     DTU.applyUpdates({{DominatorTree::Delete, Preheader, L->getHeader()}});
654     if (MSSA) {
655       MSSAU->applyUpdates({{DominatorTree::Delete, Preheader, L->getHeader()}},
656                           *DT);
657       SmallSetVector<BasicBlock *, 8> DeadBlockSet(L->block_begin(),
658                                                    L->block_end());
659       MSSAU->removeBlocks(DeadBlockSet);
660       if (VerifyMemorySSA)
661         MSSA->verifyMemorySSA();
662     }
663   }
664 
665   // Use a map to unique and a vector to guarantee deterministic ordering.
666   llvm::SmallDenseSet<std::pair<DIVariable *, DIExpression *>, 4> DeadDebugSet;
667   llvm::SmallVector<DbgVariableIntrinsic *, 4> DeadDebugInst;
668 
669   if (ExitBlock) {
670     // Given LCSSA form is satisfied, we should not have users of instructions
671     // within the dead loop outside of the loop. However, LCSSA doesn't take
672     // unreachable uses into account. We handle them here.
673     // We could do it after drop all references (in this case all users in the
674     // loop will be already eliminated and we have less work to do but according
675     // to API doc of User::dropAllReferences only valid operation after dropping
676     // references, is deletion. So let's substitute all usages of
677     // instruction from the loop with undef value of corresponding type first.
678     for (auto *Block : L->blocks())
679       for (Instruction &I : *Block) {
680         auto *Undef = UndefValue::get(I.getType());
681         for (Value::use_iterator UI = I.use_begin(), E = I.use_end();
682              UI != E;) {
683           Use &U = *UI;
684           ++UI;
685           if (auto *Usr = dyn_cast<Instruction>(U.getUser()))
686             if (L->contains(Usr->getParent()))
687               continue;
688           // If we have a DT then we can check that uses outside a loop only in
689           // unreachable block.
690           if (DT)
691             assert(!DT->isReachableFromEntry(U) &&
692                    "Unexpected user in reachable block");
693           U.set(Undef);
694         }
695         auto *DVI = dyn_cast<DbgVariableIntrinsic>(&I);
696         if (!DVI)
697           continue;
698         auto Key =
699             DeadDebugSet.find({DVI->getVariable(), DVI->getExpression()});
700         if (Key != DeadDebugSet.end())
701           continue;
702         DeadDebugSet.insert({DVI->getVariable(), DVI->getExpression()});
703         DeadDebugInst.push_back(DVI);
704       }
705 
706     // After the loop has been deleted all the values defined and modified
707     // inside the loop are going to be unavailable.
708     // Since debug values in the loop have been deleted, inserting an undef
709     // dbg.value truncates the range of any dbg.value before the loop where the
710     // loop used to be. This is particularly important for constant values.
711     DIBuilder DIB(*ExitBlock->getModule());
712     Instruction *InsertDbgValueBefore = ExitBlock->getFirstNonPHI();
713     assert(InsertDbgValueBefore &&
714            "There should be a non-PHI instruction in exit block, else these "
715            "instructions will have no parent.");
716     for (auto *DVI : DeadDebugInst)
717       DIB.insertDbgValueIntrinsic(UndefValue::get(Builder.getInt32Ty()),
718                                   DVI->getVariable(), DVI->getExpression(),
719                                   DVI->getDebugLoc(), InsertDbgValueBefore);
720   }
721 
722   // Remove the block from the reference counting scheme, so that we can
723   // delete it freely later.
724   for (auto *Block : L->blocks())
725     Block->dropAllReferences();
726 
727   if (MSSA && VerifyMemorySSA)
728     MSSA->verifyMemorySSA();
729 
730   if (LI) {
731     // Erase the instructions and the blocks without having to worry
732     // about ordering because we already dropped the references.
733     // NOTE: This iteration is safe because erasing the block does not remove
734     // its entry from the loop's block list.  We do that in the next section.
735     for (Loop::block_iterator LpI = L->block_begin(), LpE = L->block_end();
736          LpI != LpE; ++LpI)
737       (*LpI)->eraseFromParent();
738 
739     // Finally, the blocks from loopinfo.  This has to happen late because
740     // otherwise our loop iterators won't work.
741 
742     SmallPtrSet<BasicBlock *, 8> blocks;
743     blocks.insert(L->block_begin(), L->block_end());
744     for (BasicBlock *BB : blocks)
745       LI->removeBlock(BB);
746 
747     // The last step is to update LoopInfo now that we've eliminated this loop.
748     // Note: LoopInfo::erase remove the given loop and relink its subloops with
749     // its parent. While removeLoop/removeChildLoop remove the given loop but
750     // not relink its subloops, which is what we want.
751     if (Loop *ParentLoop = L->getParentLoop()) {
752       Loop::iterator I = find(*ParentLoop, L);
753       assert(I != ParentLoop->end() && "Couldn't find loop");
754       ParentLoop->removeChildLoop(I);
755     } else {
756       Loop::iterator I = find(*LI, L);
757       assert(I != LI->end() && "Couldn't find loop");
758       LI->removeLoop(I);
759     }
760     LI->destroy(L);
761   }
762 }
763 
getOutermostLoop(Loop * L)764 static Loop *getOutermostLoop(Loop *L) {
765   while (Loop *Parent = L->getParentLoop())
766     L = Parent;
767   return L;
768 }
769 
breakLoopBackedge(Loop * L,DominatorTree & DT,ScalarEvolution & SE,LoopInfo & LI,MemorySSA * MSSA)770 void llvm::breakLoopBackedge(Loop *L, DominatorTree &DT, ScalarEvolution &SE,
771                              LoopInfo &LI, MemorySSA *MSSA) {
772   auto *Latch = L->getLoopLatch();
773   assert(Latch && "multiple latches not yet supported");
774   auto *Header = L->getHeader();
775   Loop *OutermostLoop = getOutermostLoop(L);
776 
777   SE.forgetLoop(L);
778 
779   // Note: By splitting the backedge, and then explicitly making it unreachable
780   // we gracefully handle corner cases such as non-bottom tested loops and the
781   // like.  We also have the benefit of being able to reuse existing well tested
782   // code.  It might be worth special casing the common bottom tested case at
783   // some point to avoid code churn.
784 
785   std::unique_ptr<MemorySSAUpdater> MSSAU;
786   if (MSSA)
787     MSSAU = std::make_unique<MemorySSAUpdater>(MSSA);
788 
789   auto *BackedgeBB = SplitEdge(Latch, Header, &DT, &LI, MSSAU.get());
790 
791   DomTreeUpdater DTU(&DT, DomTreeUpdater::UpdateStrategy::Eager);
792   (void)changeToUnreachable(BackedgeBB->getTerminator(), /*UseTrap*/false,
793                             /*PreserveLCSSA*/true, &DTU, MSSAU.get());
794 
795   // Erase (and destroy) this loop instance.  Handles relinking sub-loops
796   // and blocks within the loop as needed.
797   LI.erase(L);
798 
799   // If the loop we broke had a parent, then changeToUnreachable might have
800   // caused a block to be removed from the parent loop (see loop_nest_lcssa
801   // test case in zero-btc.ll for an example), thus changing the parent's
802   // exit blocks.  If that happened, we need to rebuild LCSSA on the outermost
803   // loop which might have a had a block removed.
804   if (OutermostLoop != L)
805     formLCSSARecursively(*OutermostLoop, DT, &LI, &SE);
806 }
807 
808 
809 /// Checks if \p L has single exit through latch block except possibly
810 /// "deoptimizing" exits. Returns branch instruction terminating the loop
811 /// latch if above check is successful, nullptr otherwise.
getExpectedExitLoopLatchBranch(Loop * L)812 static BranchInst *getExpectedExitLoopLatchBranch(Loop *L) {
813   BasicBlock *Latch = L->getLoopLatch();
814   if (!Latch)
815     return nullptr;
816 
817   BranchInst *LatchBR = dyn_cast<BranchInst>(Latch->getTerminator());
818   if (!LatchBR || LatchBR->getNumSuccessors() != 2 || !L->isLoopExiting(Latch))
819     return nullptr;
820 
821   assert((LatchBR->getSuccessor(0) == L->getHeader() ||
822           LatchBR->getSuccessor(1) == L->getHeader()) &&
823          "At least one edge out of the latch must go to the header");
824 
825   SmallVector<BasicBlock *, 4> ExitBlocks;
826   L->getUniqueNonLatchExitBlocks(ExitBlocks);
827   if (any_of(ExitBlocks, [](const BasicBlock *EB) {
828         return !EB->getTerminatingDeoptimizeCall();
829       }))
830     return nullptr;
831 
832   return LatchBR;
833 }
834 
835 Optional<unsigned>
getLoopEstimatedTripCount(Loop * L,unsigned * EstimatedLoopInvocationWeight)836 llvm::getLoopEstimatedTripCount(Loop *L,
837                                 unsigned *EstimatedLoopInvocationWeight) {
838   // Support loops with an exiting latch and other existing exists only
839   // deoptimize.
840   BranchInst *LatchBranch = getExpectedExitLoopLatchBranch(L);
841   if (!LatchBranch)
842     return None;
843 
844   // To estimate the number of times the loop body was executed, we want to
845   // know the number of times the backedge was taken, vs. the number of times
846   // we exited the loop.
847   uint64_t BackedgeTakenWeight, LatchExitWeight;
848   if (!LatchBranch->extractProfMetadata(BackedgeTakenWeight, LatchExitWeight))
849     return None;
850 
851   if (LatchBranch->getSuccessor(0) != L->getHeader())
852     std::swap(BackedgeTakenWeight, LatchExitWeight);
853 
854   if (!LatchExitWeight)
855     return None;
856 
857   if (EstimatedLoopInvocationWeight)
858     *EstimatedLoopInvocationWeight = LatchExitWeight;
859 
860   // Estimated backedge taken count is a ratio of the backedge taken weight by
861   // the weight of the edge exiting the loop, rounded to nearest.
862   uint64_t BackedgeTakenCount =
863       llvm::divideNearest(BackedgeTakenWeight, LatchExitWeight);
864   // Estimated trip count is one plus estimated backedge taken count.
865   return BackedgeTakenCount + 1;
866 }
867 
setLoopEstimatedTripCount(Loop * L,unsigned EstimatedTripCount,unsigned EstimatedloopInvocationWeight)868 bool llvm::setLoopEstimatedTripCount(Loop *L, unsigned EstimatedTripCount,
869                                      unsigned EstimatedloopInvocationWeight) {
870   // Support loops with an exiting latch and other existing exists only
871   // deoptimize.
872   BranchInst *LatchBranch = getExpectedExitLoopLatchBranch(L);
873   if (!LatchBranch)
874     return false;
875 
876   // Calculate taken and exit weights.
877   unsigned LatchExitWeight = 0;
878   unsigned BackedgeTakenWeight = 0;
879 
880   if (EstimatedTripCount > 0) {
881     LatchExitWeight = EstimatedloopInvocationWeight;
882     BackedgeTakenWeight = (EstimatedTripCount - 1) * LatchExitWeight;
883   }
884 
885   // Make a swap if back edge is taken when condition is "false".
886   if (LatchBranch->getSuccessor(0) != L->getHeader())
887     std::swap(BackedgeTakenWeight, LatchExitWeight);
888 
889   MDBuilder MDB(LatchBranch->getContext());
890 
891   // Set/Update profile metadata.
892   LatchBranch->setMetadata(
893       LLVMContext::MD_prof,
894       MDB.createBranchWeights(BackedgeTakenWeight, LatchExitWeight));
895 
896   return true;
897 }
898 
hasIterationCountInvariantInParent(Loop * InnerLoop,ScalarEvolution & SE)899 bool llvm::hasIterationCountInvariantInParent(Loop *InnerLoop,
900                                               ScalarEvolution &SE) {
901   Loop *OuterL = InnerLoop->getParentLoop();
902   if (!OuterL)
903     return true;
904 
905   // Get the backedge taken count for the inner loop
906   BasicBlock *InnerLoopLatch = InnerLoop->getLoopLatch();
907   const SCEV *InnerLoopBECountSC = SE.getExitCount(InnerLoop, InnerLoopLatch);
908   if (isa<SCEVCouldNotCompute>(InnerLoopBECountSC) ||
909       !InnerLoopBECountSC->getType()->isIntegerTy())
910     return false;
911 
912   // Get whether count is invariant to the outer loop
913   ScalarEvolution::LoopDisposition LD =
914       SE.getLoopDisposition(InnerLoopBECountSC, OuterL);
915   if (LD != ScalarEvolution::LoopInvariant)
916     return false;
917 
918   return true;
919 }
920 
createMinMaxOp(IRBuilderBase & Builder,RecurKind RK,Value * Left,Value * Right)921 Value *llvm::createMinMaxOp(IRBuilderBase &Builder, RecurKind RK, Value *Left,
922                             Value *Right) {
923   CmpInst::Predicate Pred;
924   switch (RK) {
925   default:
926     llvm_unreachable("Unknown min/max recurrence kind");
927   case RecurKind::UMin:
928     Pred = CmpInst::ICMP_ULT;
929     break;
930   case RecurKind::UMax:
931     Pred = CmpInst::ICMP_UGT;
932     break;
933   case RecurKind::SMin:
934     Pred = CmpInst::ICMP_SLT;
935     break;
936   case RecurKind::SMax:
937     Pred = CmpInst::ICMP_SGT;
938     break;
939   case RecurKind::FMin:
940     Pred = CmpInst::FCMP_OLT;
941     break;
942   case RecurKind::FMax:
943     Pred = CmpInst::FCMP_OGT;
944     break;
945   }
946 
947   // We only match FP sequences that are 'fast', so we can unconditionally
948   // set it on any generated instructions.
949   IRBuilderBase::FastMathFlagGuard FMFG(Builder);
950   FastMathFlags FMF;
951   FMF.setFast();
952   Builder.setFastMathFlags(FMF);
953   Value *Cmp = Builder.CreateCmp(Pred, Left, Right, "rdx.minmax.cmp");
954   Value *Select = Builder.CreateSelect(Cmp, Left, Right, "rdx.minmax.select");
955   return Select;
956 }
957 
958 // Helper to generate an ordered reduction.
getOrderedReduction(IRBuilderBase & Builder,Value * Acc,Value * Src,unsigned Op,RecurKind RdxKind,ArrayRef<Value * > RedOps)959 Value *llvm::getOrderedReduction(IRBuilderBase &Builder, Value *Acc, Value *Src,
960                                  unsigned Op, RecurKind RdxKind,
961                                  ArrayRef<Value *> RedOps) {
962   unsigned VF = cast<FixedVectorType>(Src->getType())->getNumElements();
963 
964   // Extract and apply reduction ops in ascending order:
965   // e.g. ((((Acc + Scl[0]) + Scl[1]) + Scl[2]) + ) ... + Scl[VF-1]
966   Value *Result = Acc;
967   for (unsigned ExtractIdx = 0; ExtractIdx != VF; ++ExtractIdx) {
968     Value *Ext =
969         Builder.CreateExtractElement(Src, Builder.getInt32(ExtractIdx));
970 
971     if (Op != Instruction::ICmp && Op != Instruction::FCmp) {
972       Result = Builder.CreateBinOp((Instruction::BinaryOps)Op, Result, Ext,
973                                    "bin.rdx");
974     } else {
975       assert(RecurrenceDescriptor::isMinMaxRecurrenceKind(RdxKind) &&
976              "Invalid min/max");
977       Result = createMinMaxOp(Builder, RdxKind, Result, Ext);
978     }
979 
980     if (!RedOps.empty())
981       propagateIRFlags(Result, RedOps);
982   }
983 
984   return Result;
985 }
986 
987 // Helper to generate a log2 shuffle reduction.
getShuffleReduction(IRBuilderBase & Builder,Value * Src,unsigned Op,RecurKind RdxKind,ArrayRef<Value * > RedOps)988 Value *llvm::getShuffleReduction(IRBuilderBase &Builder, Value *Src,
989                                  unsigned Op, RecurKind RdxKind,
990                                  ArrayRef<Value *> RedOps) {
991   unsigned VF = cast<FixedVectorType>(Src->getType())->getNumElements();
992   // VF is a power of 2 so we can emit the reduction using log2(VF) shuffles
993   // and vector ops, reducing the set of values being computed by half each
994   // round.
995   assert(isPowerOf2_32(VF) &&
996          "Reduction emission only supported for pow2 vectors!");
997   Value *TmpVec = Src;
998   SmallVector<int, 32> ShuffleMask(VF);
999   for (unsigned i = VF; i != 1; i >>= 1) {
1000     // Move the upper half of the vector to the lower half.
1001     for (unsigned j = 0; j != i / 2; ++j)
1002       ShuffleMask[j] = i / 2 + j;
1003 
1004     // Fill the rest of the mask with undef.
1005     std::fill(&ShuffleMask[i / 2], ShuffleMask.end(), -1);
1006 
1007     Value *Shuf = Builder.CreateShuffleVector(TmpVec, ShuffleMask, "rdx.shuf");
1008 
1009     if (Op != Instruction::ICmp && Op != Instruction::FCmp) {
1010       // The builder propagates its fast-math-flags setting.
1011       TmpVec = Builder.CreateBinOp((Instruction::BinaryOps)Op, TmpVec, Shuf,
1012                                    "bin.rdx");
1013     } else {
1014       assert(RecurrenceDescriptor::isMinMaxRecurrenceKind(RdxKind) &&
1015              "Invalid min/max");
1016       TmpVec = createMinMaxOp(Builder, RdxKind, TmpVec, Shuf);
1017     }
1018     if (!RedOps.empty())
1019       propagateIRFlags(TmpVec, RedOps);
1020 
1021     // We may compute the reassociated scalar ops in a way that does not
1022     // preserve nsw/nuw etc. Conservatively, drop those flags.
1023     if (auto *ReductionInst = dyn_cast<Instruction>(TmpVec))
1024       ReductionInst->dropPoisonGeneratingFlags();
1025   }
1026   // The result is in the first element of the vector.
1027   return Builder.CreateExtractElement(TmpVec, Builder.getInt32(0));
1028 }
1029 
createSimpleTargetReduction(IRBuilderBase & Builder,const TargetTransformInfo * TTI,Value * Src,RecurKind RdxKind,ArrayRef<Value * > RedOps)1030 Value *llvm::createSimpleTargetReduction(IRBuilderBase &Builder,
1031                                          const TargetTransformInfo *TTI,
1032                                          Value *Src, RecurKind RdxKind,
1033                                          ArrayRef<Value *> RedOps) {
1034   unsigned Opcode = RecurrenceDescriptor::getOpcode(RdxKind);
1035   TargetTransformInfo::ReductionFlags RdxFlags;
1036   RdxFlags.IsMaxOp = RdxKind == RecurKind::SMax || RdxKind == RecurKind::UMax ||
1037                      RdxKind == RecurKind::FMax;
1038   RdxFlags.IsSigned = RdxKind == RecurKind::SMax || RdxKind == RecurKind::SMin;
1039   if (!ForceReductionIntrinsic &&
1040       !TTI->useReductionIntrinsic(Opcode, Src->getType(), RdxFlags))
1041     return getShuffleReduction(Builder, Src, Opcode, RdxKind, RedOps);
1042 
1043   auto *SrcVecEltTy = cast<VectorType>(Src->getType())->getElementType();
1044   switch (RdxKind) {
1045   case RecurKind::Add:
1046     return Builder.CreateAddReduce(Src);
1047   case RecurKind::Mul:
1048     return Builder.CreateMulReduce(Src);
1049   case RecurKind::And:
1050     return Builder.CreateAndReduce(Src);
1051   case RecurKind::Or:
1052     return Builder.CreateOrReduce(Src);
1053   case RecurKind::Xor:
1054     return Builder.CreateXorReduce(Src);
1055   case RecurKind::FAdd:
1056     return Builder.CreateFAddReduce(ConstantFP::getNegativeZero(SrcVecEltTy),
1057                                     Src);
1058   case RecurKind::FMul:
1059     return Builder.CreateFMulReduce(ConstantFP::get(SrcVecEltTy, 1.0), Src);
1060   case RecurKind::SMax:
1061     return Builder.CreateIntMaxReduce(Src, true);
1062   case RecurKind::SMin:
1063     return Builder.CreateIntMinReduce(Src, true);
1064   case RecurKind::UMax:
1065     return Builder.CreateIntMaxReduce(Src, false);
1066   case RecurKind::UMin:
1067     return Builder.CreateIntMinReduce(Src, false);
1068   case RecurKind::FMax:
1069     return Builder.CreateFPMaxReduce(Src);
1070   case RecurKind::FMin:
1071     return Builder.CreateFPMinReduce(Src);
1072   default:
1073     llvm_unreachable("Unhandled opcode");
1074   }
1075 }
1076 
createTargetReduction(IRBuilderBase & B,const TargetTransformInfo * TTI,RecurrenceDescriptor & Desc,Value * Src)1077 Value *llvm::createTargetReduction(IRBuilderBase &B,
1078                                    const TargetTransformInfo *TTI,
1079                                    RecurrenceDescriptor &Desc, Value *Src) {
1080   // TODO: Support in-order reductions based on the recurrence descriptor.
1081   // All ops in the reduction inherit fast-math-flags from the recurrence
1082   // descriptor.
1083   IRBuilderBase::FastMathFlagGuard FMFGuard(B);
1084   B.setFastMathFlags(Desc.getFastMathFlags());
1085   return createSimpleTargetReduction(B, TTI, Src, Desc.getRecurrenceKind());
1086 }
1087 
propagateIRFlags(Value * I,ArrayRef<Value * > VL,Value * OpValue)1088 void llvm::propagateIRFlags(Value *I, ArrayRef<Value *> VL, Value *OpValue) {
1089   auto *VecOp = dyn_cast<Instruction>(I);
1090   if (!VecOp)
1091     return;
1092   auto *Intersection = (OpValue == nullptr) ? dyn_cast<Instruction>(VL[0])
1093                                             : dyn_cast<Instruction>(OpValue);
1094   if (!Intersection)
1095     return;
1096   const unsigned Opcode = Intersection->getOpcode();
1097   VecOp->copyIRFlags(Intersection);
1098   for (auto *V : VL) {
1099     auto *Instr = dyn_cast<Instruction>(V);
1100     if (!Instr)
1101       continue;
1102     if (OpValue == nullptr || Opcode == Instr->getOpcode())
1103       VecOp->andIRFlags(V);
1104   }
1105 }
1106 
isKnownNegativeInLoop(const SCEV * S,const Loop * L,ScalarEvolution & SE)1107 bool llvm::isKnownNegativeInLoop(const SCEV *S, const Loop *L,
1108                                  ScalarEvolution &SE) {
1109   const SCEV *Zero = SE.getZero(S->getType());
1110   return SE.isAvailableAtLoopEntry(S, L) &&
1111          SE.isLoopEntryGuardedByCond(L, ICmpInst::ICMP_SLT, S, Zero);
1112 }
1113 
isKnownNonNegativeInLoop(const SCEV * S,const Loop * L,ScalarEvolution & SE)1114 bool llvm::isKnownNonNegativeInLoop(const SCEV *S, const Loop *L,
1115                                     ScalarEvolution &SE) {
1116   const SCEV *Zero = SE.getZero(S->getType());
1117   return SE.isAvailableAtLoopEntry(S, L) &&
1118          SE.isLoopEntryGuardedByCond(L, ICmpInst::ICMP_SGE, S, Zero);
1119 }
1120 
cannotBeMinInLoop(const SCEV * S,const Loop * L,ScalarEvolution & SE,bool Signed)1121 bool llvm::cannotBeMinInLoop(const SCEV *S, const Loop *L, ScalarEvolution &SE,
1122                              bool Signed) {
1123   unsigned BitWidth = cast<IntegerType>(S->getType())->getBitWidth();
1124   APInt Min = Signed ? APInt::getSignedMinValue(BitWidth) :
1125     APInt::getMinValue(BitWidth);
1126   auto Predicate = Signed ? ICmpInst::ICMP_SGT : ICmpInst::ICMP_UGT;
1127   return SE.isAvailableAtLoopEntry(S, L) &&
1128          SE.isLoopEntryGuardedByCond(L, Predicate, S,
1129                                      SE.getConstant(Min));
1130 }
1131 
cannotBeMaxInLoop(const SCEV * S,const Loop * L,ScalarEvolution & SE,bool Signed)1132 bool llvm::cannotBeMaxInLoop(const SCEV *S, const Loop *L, ScalarEvolution &SE,
1133                              bool Signed) {
1134   unsigned BitWidth = cast<IntegerType>(S->getType())->getBitWidth();
1135   APInt Max = Signed ? APInt::getSignedMaxValue(BitWidth) :
1136     APInt::getMaxValue(BitWidth);
1137   auto Predicate = Signed ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT;
1138   return SE.isAvailableAtLoopEntry(S, L) &&
1139          SE.isLoopEntryGuardedByCond(L, Predicate, S,
1140                                      SE.getConstant(Max));
1141 }
1142 
1143 //===----------------------------------------------------------------------===//
1144 // rewriteLoopExitValues - Optimize IV users outside the loop.
1145 // As a side effect, reduces the amount of IV processing within the loop.
1146 //===----------------------------------------------------------------------===//
1147 
1148 // Return true if the SCEV expansion generated by the rewriter can replace the
1149 // original value. SCEV guarantees that it produces the same value, but the way
1150 // it is produced may be illegal IR.  Ideally, this function will only be
1151 // called for verification.
isValidRewrite(ScalarEvolution * SE,Value * FromVal,Value * ToVal)1152 static bool isValidRewrite(ScalarEvolution *SE, Value *FromVal, Value *ToVal) {
1153   // If an SCEV expression subsumed multiple pointers, its expansion could
1154   // reassociate the GEP changing the base pointer. This is illegal because the
1155   // final address produced by a GEP chain must be inbounds relative to its
1156   // underlying object. Otherwise basic alias analysis, among other things,
1157   // could fail in a dangerous way. Ultimately, SCEV will be improved to avoid
1158   // producing an expression involving multiple pointers. Until then, we must
1159   // bail out here.
1160   //
1161   // Retrieve the pointer operand of the GEP. Don't use getUnderlyingObject
1162   // because it understands lcssa phis while SCEV does not.
1163   Value *FromPtr = FromVal;
1164   Value *ToPtr = ToVal;
1165   if (auto *GEP = dyn_cast<GEPOperator>(FromVal))
1166     FromPtr = GEP->getPointerOperand();
1167 
1168   if (auto *GEP = dyn_cast<GEPOperator>(ToVal))
1169     ToPtr = GEP->getPointerOperand();
1170 
1171   if (FromPtr != FromVal || ToPtr != ToVal) {
1172     // Quickly check the common case
1173     if (FromPtr == ToPtr)
1174       return true;
1175 
1176     // SCEV may have rewritten an expression that produces the GEP's pointer
1177     // operand. That's ok as long as the pointer operand has the same base
1178     // pointer. Unlike getUnderlyingObject(), getPointerBase() will find the
1179     // base of a recurrence. This handles the case in which SCEV expansion
1180     // converts a pointer type recurrence into a nonrecurrent pointer base
1181     // indexed by an integer recurrence.
1182 
1183     // If the GEP base pointer is a vector of pointers, abort.
1184     if (!FromPtr->getType()->isPointerTy() || !ToPtr->getType()->isPointerTy())
1185       return false;
1186 
1187     const SCEV *FromBase = SE->getPointerBase(SE->getSCEV(FromPtr));
1188     const SCEV *ToBase = SE->getPointerBase(SE->getSCEV(ToPtr));
1189     if (FromBase == ToBase)
1190       return true;
1191 
1192     LLVM_DEBUG(dbgs() << "rewriteLoopExitValues: GEP rewrite bail out "
1193                       << *FromBase << " != " << *ToBase << "\n");
1194 
1195     return false;
1196   }
1197   return true;
1198 }
1199 
hasHardUserWithinLoop(const Loop * L,const Instruction * I)1200 static bool hasHardUserWithinLoop(const Loop *L, const Instruction *I) {
1201   SmallPtrSet<const Instruction *, 8> Visited;
1202   SmallVector<const Instruction *, 8> WorkList;
1203   Visited.insert(I);
1204   WorkList.push_back(I);
1205   while (!WorkList.empty()) {
1206     const Instruction *Curr = WorkList.pop_back_val();
1207     // This use is outside the loop, nothing to do.
1208     if (!L->contains(Curr))
1209       continue;
1210     // Do we assume it is a "hard" use which will not be eliminated easily?
1211     if (Curr->mayHaveSideEffects())
1212       return true;
1213     // Otherwise, add all its users to worklist.
1214     for (auto U : Curr->users()) {
1215       auto *UI = cast<Instruction>(U);
1216       if (Visited.insert(UI).second)
1217         WorkList.push_back(UI);
1218     }
1219   }
1220   return false;
1221 }
1222 
1223 // Collect information about PHI nodes which can be transformed in
1224 // rewriteLoopExitValues.
1225 struct RewritePhi {
1226   PHINode *PN;               // For which PHI node is this replacement?
1227   unsigned Ith;              // For which incoming value?
1228   const SCEV *ExpansionSCEV; // The SCEV of the incoming value we are rewriting.
1229   Instruction *ExpansionPoint; // Where we'd like to expand that SCEV?
1230   bool HighCost;               // Is this expansion a high-cost?
1231 
1232   Value *Expansion = nullptr;
1233   bool ValidRewrite = false;
1234 
RewritePhiRewritePhi1235   RewritePhi(PHINode *P, unsigned I, const SCEV *Val, Instruction *ExpansionPt,
1236              bool H)
1237       : PN(P), Ith(I), ExpansionSCEV(Val), ExpansionPoint(ExpansionPt),
1238         HighCost(H) {}
1239 };
1240 
1241 // Check whether it is possible to delete the loop after rewriting exit
1242 // value. If it is possible, ignore ReplaceExitValue and do rewriting
1243 // aggressively.
canLoopBeDeleted(Loop * L,SmallVector<RewritePhi,8> & RewritePhiSet)1244 static bool canLoopBeDeleted(Loop *L, SmallVector<RewritePhi, 8> &RewritePhiSet) {
1245   BasicBlock *Preheader = L->getLoopPreheader();
1246   // If there is no preheader, the loop will not be deleted.
1247   if (!Preheader)
1248     return false;
1249 
1250   // In LoopDeletion pass Loop can be deleted when ExitingBlocks.size() > 1.
1251   // We obviate multiple ExitingBlocks case for simplicity.
1252   // TODO: If we see testcase with multiple ExitingBlocks can be deleted
1253   // after exit value rewriting, we can enhance the logic here.
1254   SmallVector<BasicBlock *, 4> ExitingBlocks;
1255   L->getExitingBlocks(ExitingBlocks);
1256   SmallVector<BasicBlock *, 8> ExitBlocks;
1257   L->getUniqueExitBlocks(ExitBlocks);
1258   if (ExitBlocks.size() != 1 || ExitingBlocks.size() != 1)
1259     return false;
1260 
1261   BasicBlock *ExitBlock = ExitBlocks[0];
1262   BasicBlock::iterator BI = ExitBlock->begin();
1263   while (PHINode *P = dyn_cast<PHINode>(BI)) {
1264     Value *Incoming = P->getIncomingValueForBlock(ExitingBlocks[0]);
1265 
1266     // If the Incoming value of P is found in RewritePhiSet, we know it
1267     // could be rewritten to use a loop invariant value in transformation
1268     // phase later. Skip it in the loop invariant check below.
1269     bool found = false;
1270     for (const RewritePhi &Phi : RewritePhiSet) {
1271       if (!Phi.ValidRewrite)
1272         continue;
1273       unsigned i = Phi.Ith;
1274       if (Phi.PN == P && (Phi.PN)->getIncomingValue(i) == Incoming) {
1275         found = true;
1276         break;
1277       }
1278     }
1279 
1280     Instruction *I;
1281     if (!found && (I = dyn_cast<Instruction>(Incoming)))
1282       if (!L->hasLoopInvariantOperands(I))
1283         return false;
1284 
1285     ++BI;
1286   }
1287 
1288   for (auto *BB : L->blocks())
1289     if (llvm::any_of(*BB, [](Instruction &I) {
1290           return I.mayHaveSideEffects();
1291         }))
1292       return false;
1293 
1294   return true;
1295 }
1296 
rewriteLoopExitValues(Loop * L,LoopInfo * LI,TargetLibraryInfo * TLI,ScalarEvolution * SE,const TargetTransformInfo * TTI,SCEVExpander & Rewriter,DominatorTree * DT,ReplaceExitVal ReplaceExitValue,SmallVector<WeakTrackingVH,16> & DeadInsts)1297 int llvm::rewriteLoopExitValues(Loop *L, LoopInfo *LI, TargetLibraryInfo *TLI,
1298                                 ScalarEvolution *SE,
1299                                 const TargetTransformInfo *TTI,
1300                                 SCEVExpander &Rewriter, DominatorTree *DT,
1301                                 ReplaceExitVal ReplaceExitValue,
1302                                 SmallVector<WeakTrackingVH, 16> &DeadInsts) {
1303   // Check a pre-condition.
1304   assert(L->isRecursivelyLCSSAForm(*DT, *LI) &&
1305          "Indvars did not preserve LCSSA!");
1306 
1307   SmallVector<BasicBlock*, 8> ExitBlocks;
1308   L->getUniqueExitBlocks(ExitBlocks);
1309 
1310   SmallVector<RewritePhi, 8> RewritePhiSet;
1311   // Find all values that are computed inside the loop, but used outside of it.
1312   // Because of LCSSA, these values will only occur in LCSSA PHI Nodes.  Scan
1313   // the exit blocks of the loop to find them.
1314   for (BasicBlock *ExitBB : ExitBlocks) {
1315     // If there are no PHI nodes in this exit block, then no values defined
1316     // inside the loop are used on this path, skip it.
1317     PHINode *PN = dyn_cast<PHINode>(ExitBB->begin());
1318     if (!PN) continue;
1319 
1320     unsigned NumPreds = PN->getNumIncomingValues();
1321 
1322     // Iterate over all of the PHI nodes.
1323     BasicBlock::iterator BBI = ExitBB->begin();
1324     while ((PN = dyn_cast<PHINode>(BBI++))) {
1325       if (PN->use_empty())
1326         continue; // dead use, don't replace it
1327 
1328       if (!SE->isSCEVable(PN->getType()))
1329         continue;
1330 
1331       // It's necessary to tell ScalarEvolution about this explicitly so that
1332       // it can walk the def-use list and forget all SCEVs, as it may not be
1333       // watching the PHI itself. Once the new exit value is in place, there
1334       // may not be a def-use connection between the loop and every instruction
1335       // which got a SCEVAddRecExpr for that loop.
1336       SE->forgetValue(PN);
1337 
1338       // Iterate over all of the values in all the PHI nodes.
1339       for (unsigned i = 0; i != NumPreds; ++i) {
1340         // If the value being merged in is not integer or is not defined
1341         // in the loop, skip it.
1342         Value *InVal = PN->getIncomingValue(i);
1343         if (!isa<Instruction>(InVal))
1344           continue;
1345 
1346         // If this pred is for a subloop, not L itself, skip it.
1347         if (LI->getLoopFor(PN->getIncomingBlock(i)) != L)
1348           continue; // The Block is in a subloop, skip it.
1349 
1350         // Check that InVal is defined in the loop.
1351         Instruction *Inst = cast<Instruction>(InVal);
1352         if (!L->contains(Inst))
1353           continue;
1354 
1355         // Okay, this instruction has a user outside of the current loop
1356         // and varies predictably *inside* the loop.  Evaluate the value it
1357         // contains when the loop exits, if possible.  We prefer to start with
1358         // expressions which are true for all exits (so as to maximize
1359         // expression reuse by the SCEVExpander), but resort to per-exit
1360         // evaluation if that fails.
1361         const SCEV *ExitValue = SE->getSCEVAtScope(Inst, L->getParentLoop());
1362         if (isa<SCEVCouldNotCompute>(ExitValue) ||
1363             !SE->isLoopInvariant(ExitValue, L) ||
1364             !isSafeToExpand(ExitValue, *SE)) {
1365           // TODO: This should probably be sunk into SCEV in some way; maybe a
1366           // getSCEVForExit(SCEV*, L, ExitingBB)?  It can be generalized for
1367           // most SCEV expressions and other recurrence types (e.g. shift
1368           // recurrences).  Is there existing code we can reuse?
1369           const SCEV *ExitCount = SE->getExitCount(L, PN->getIncomingBlock(i));
1370           if (isa<SCEVCouldNotCompute>(ExitCount))
1371             continue;
1372           if (auto *AddRec = dyn_cast<SCEVAddRecExpr>(SE->getSCEV(Inst)))
1373             if (AddRec->getLoop() == L)
1374               ExitValue = AddRec->evaluateAtIteration(ExitCount, *SE);
1375           if (isa<SCEVCouldNotCompute>(ExitValue) ||
1376               !SE->isLoopInvariant(ExitValue, L) ||
1377               !isSafeToExpand(ExitValue, *SE))
1378             continue;
1379         }
1380 
1381         // Computing the value outside of the loop brings no benefit if it is
1382         // definitely used inside the loop in a way which can not be optimized
1383         // away. Avoid doing so unless we know we have a value which computes
1384         // the ExitValue already. TODO: This should be merged into SCEV
1385         // expander to leverage its knowledge of existing expressions.
1386         if (ReplaceExitValue != AlwaysRepl && !isa<SCEVConstant>(ExitValue) &&
1387             !isa<SCEVUnknown>(ExitValue) && hasHardUserWithinLoop(L, Inst))
1388           continue;
1389 
1390         // Check if expansions of this SCEV would count as being high cost.
1391         bool HighCost = Rewriter.isHighCostExpansion(
1392             ExitValue, L, SCEVCheapExpansionBudget, TTI, Inst);
1393 
1394         // Note that we must not perform expansions until after
1395         // we query *all* the costs, because if we perform temporary expansion
1396         // inbetween, one that we might not intend to keep, said expansion
1397         // *may* affect cost calculation of the the next SCEV's we'll query,
1398         // and next SCEV may errneously get smaller cost.
1399 
1400         // Collect all the candidate PHINodes to be rewritten.
1401         RewritePhiSet.emplace_back(PN, i, ExitValue, Inst, HighCost);
1402       }
1403     }
1404   }
1405 
1406   // Now that we've done preliminary filtering and billed all the SCEV's,
1407   // we can perform the last sanity check - the expansion must be valid.
1408   for (RewritePhi &Phi : RewritePhiSet) {
1409     Phi.Expansion = Rewriter.expandCodeFor(Phi.ExpansionSCEV, Phi.PN->getType(),
1410                                            Phi.ExpansionPoint);
1411 
1412     LLVM_DEBUG(dbgs() << "rewriteLoopExitValues: AfterLoopVal = "
1413                       << *(Phi.Expansion) << '\n'
1414                       << "  LoopVal = " << *(Phi.ExpansionPoint) << "\n");
1415 
1416     // FIXME: isValidRewrite() is a hack. it should be an assert, eventually.
1417     Phi.ValidRewrite = isValidRewrite(SE, Phi.ExpansionPoint, Phi.Expansion);
1418     if (!Phi.ValidRewrite) {
1419       DeadInsts.push_back(Phi.Expansion);
1420       continue;
1421     }
1422 
1423 #ifndef NDEBUG
1424     // If we reuse an instruction from a loop which is neither L nor one of
1425     // its containing loops, we end up breaking LCSSA form for this loop by
1426     // creating a new use of its instruction.
1427     if (auto *ExitInsn = dyn_cast<Instruction>(Phi.Expansion))
1428       if (auto *EVL = LI->getLoopFor(ExitInsn->getParent()))
1429         if (EVL != L)
1430           assert(EVL->contains(L) && "LCSSA breach detected!");
1431 #endif
1432   }
1433 
1434   // TODO: after isValidRewrite() is an assertion, evaluate whether
1435   // it is beneficial to change how we calculate high-cost:
1436   // if we have SCEV 'A' which we know we will expand, should we calculate
1437   // the cost of other SCEV's after expanding SCEV 'A',
1438   // thus potentially giving cost bonus to those other SCEV's?
1439 
1440   bool LoopCanBeDel = canLoopBeDeleted(L, RewritePhiSet);
1441   int NumReplaced = 0;
1442 
1443   // Transformation.
1444   for (const RewritePhi &Phi : RewritePhiSet) {
1445     if (!Phi.ValidRewrite)
1446       continue;
1447 
1448     PHINode *PN = Phi.PN;
1449     Value *ExitVal = Phi.Expansion;
1450 
1451     // Only do the rewrite when the ExitValue can be expanded cheaply.
1452     // If LoopCanBeDel is true, rewrite exit value aggressively.
1453     if (ReplaceExitValue == OnlyCheapRepl && !LoopCanBeDel && Phi.HighCost) {
1454       DeadInsts.push_back(ExitVal);
1455       continue;
1456     }
1457 
1458     NumReplaced++;
1459     Instruction *Inst = cast<Instruction>(PN->getIncomingValue(Phi.Ith));
1460     PN->setIncomingValue(Phi.Ith, ExitVal);
1461 
1462     // If this instruction is dead now, delete it. Don't do it now to avoid
1463     // invalidating iterators.
1464     if (isInstructionTriviallyDead(Inst, TLI))
1465       DeadInsts.push_back(Inst);
1466 
1467     // Replace PN with ExitVal if that is legal and does not break LCSSA.
1468     if (PN->getNumIncomingValues() == 1 &&
1469         LI->replacementPreservesLCSSAForm(PN, ExitVal)) {
1470       PN->replaceAllUsesWith(ExitVal);
1471       PN->eraseFromParent();
1472     }
1473   }
1474 
1475   // The insertion point instruction may have been deleted; clear it out
1476   // so that the rewriter doesn't trip over it later.
1477   Rewriter.clearInsertPoint();
1478   return NumReplaced;
1479 }
1480 
1481 /// Set weights for \p UnrolledLoop and \p RemainderLoop based on weights for
1482 /// \p OrigLoop.
setProfileInfoAfterUnrolling(Loop * OrigLoop,Loop * UnrolledLoop,Loop * RemainderLoop,uint64_t UF)1483 void llvm::setProfileInfoAfterUnrolling(Loop *OrigLoop, Loop *UnrolledLoop,
1484                                         Loop *RemainderLoop, uint64_t UF) {
1485   assert(UF > 0 && "Zero unrolled factor is not supported");
1486   assert(UnrolledLoop != RemainderLoop &&
1487          "Unrolled and Remainder loops are expected to distinct");
1488 
1489   // Get number of iterations in the original scalar loop.
1490   unsigned OrigLoopInvocationWeight = 0;
1491   Optional<unsigned> OrigAverageTripCount =
1492       getLoopEstimatedTripCount(OrigLoop, &OrigLoopInvocationWeight);
1493   if (!OrigAverageTripCount)
1494     return;
1495 
1496   // Calculate number of iterations in unrolled loop.
1497   unsigned UnrolledAverageTripCount = *OrigAverageTripCount / UF;
1498   // Calculate number of iterations for remainder loop.
1499   unsigned RemainderAverageTripCount = *OrigAverageTripCount % UF;
1500 
1501   setLoopEstimatedTripCount(UnrolledLoop, UnrolledAverageTripCount,
1502                             OrigLoopInvocationWeight);
1503   setLoopEstimatedTripCount(RemainderLoop, RemainderAverageTripCount,
1504                             OrigLoopInvocationWeight);
1505 }
1506 
1507 /// Utility that implements appending of loops onto a worklist.
1508 /// Loops are added in preorder (analogous for reverse postorder for trees),
1509 /// and the worklist is processed LIFO.
1510 template <typename RangeT>
appendReversedLoopsToWorklist(RangeT && Loops,SmallPriorityWorklist<Loop *,4> & Worklist)1511 void llvm::appendReversedLoopsToWorklist(
1512     RangeT &&Loops, SmallPriorityWorklist<Loop *, 4> &Worklist) {
1513   // We use an internal worklist to build up the preorder traversal without
1514   // recursion.
1515   SmallVector<Loop *, 4> PreOrderLoops, PreOrderWorklist;
1516 
1517   // We walk the initial sequence of loops in reverse because we generally want
1518   // to visit defs before uses and the worklist is LIFO.
1519   for (Loop *RootL : Loops) {
1520     assert(PreOrderLoops.empty() && "Must start with an empty preorder walk.");
1521     assert(PreOrderWorklist.empty() &&
1522            "Must start with an empty preorder walk worklist.");
1523     PreOrderWorklist.push_back(RootL);
1524     do {
1525       Loop *L = PreOrderWorklist.pop_back_val();
1526       PreOrderWorklist.append(L->begin(), L->end());
1527       PreOrderLoops.push_back(L);
1528     } while (!PreOrderWorklist.empty());
1529 
1530     Worklist.insert(std::move(PreOrderLoops));
1531     PreOrderLoops.clear();
1532   }
1533 }
1534 
1535 template <typename RangeT>
appendLoopsToWorklist(RangeT && Loops,SmallPriorityWorklist<Loop *,4> & Worklist)1536 void llvm::appendLoopsToWorklist(RangeT &&Loops,
1537                                  SmallPriorityWorklist<Loop *, 4> &Worklist) {
1538   appendReversedLoopsToWorklist(reverse(Loops), Worklist);
1539 }
1540 
1541 template void llvm::appendLoopsToWorklist<ArrayRef<Loop *> &>(
1542     ArrayRef<Loop *> &Loops, SmallPriorityWorklist<Loop *, 4> &Worklist);
1543 
1544 template void
1545 llvm::appendLoopsToWorklist<Loop &>(Loop &L,
1546                                     SmallPriorityWorklist<Loop *, 4> &Worklist);
1547 
appendLoopsToWorklist(LoopInfo & LI,SmallPriorityWorklist<Loop *,4> & Worklist)1548 void llvm::appendLoopsToWorklist(LoopInfo &LI,
1549                                  SmallPriorityWorklist<Loop *, 4> &Worklist) {
1550   appendReversedLoopsToWorklist(LI, Worklist);
1551 }
1552 
cloneLoop(Loop * L,Loop * PL,ValueToValueMapTy & VM,LoopInfo * LI,LPPassManager * LPM)1553 Loop *llvm::cloneLoop(Loop *L, Loop *PL, ValueToValueMapTy &VM,
1554                       LoopInfo *LI, LPPassManager *LPM) {
1555   Loop &New = *LI->AllocateLoop();
1556   if (PL)
1557     PL->addChildLoop(&New);
1558   else
1559     LI->addTopLevelLoop(&New);
1560 
1561   if (LPM)
1562     LPM->addLoop(New);
1563 
1564   // Add all of the blocks in L to the new loop.
1565   for (Loop::block_iterator I = L->block_begin(), E = L->block_end();
1566        I != E; ++I)
1567     if (LI->getLoopFor(*I) == L)
1568       New.addBasicBlockToLoop(cast<BasicBlock>(VM[*I]), *LI);
1569 
1570   // Add all of the subloops to the new loop.
1571   for (Loop *I : *L)
1572     cloneLoop(I, &New, VM, LI, LPM);
1573 
1574   return &New;
1575 }
1576 
1577 /// IR Values for the lower and upper bounds of a pointer evolution.  We
1578 /// need to use value-handles because SCEV expansion can invalidate previously
1579 /// expanded values.  Thus expansion of a pointer can invalidate the bounds for
1580 /// a previous one.
1581 struct PointerBounds {
1582   TrackingVH<Value> Start;
1583   TrackingVH<Value> End;
1584 };
1585 
1586 /// Expand code for the lower and upper bound of the pointer group \p CG
1587 /// in \p TheLoop.  \return the values for the bounds.
expandBounds(const RuntimeCheckingPtrGroup * CG,Loop * TheLoop,Instruction * Loc,SCEVExpander & Exp,ScalarEvolution * SE)1588 static PointerBounds expandBounds(const RuntimeCheckingPtrGroup *CG,
1589                                   Loop *TheLoop, Instruction *Loc,
1590                                   SCEVExpander &Exp, ScalarEvolution *SE) {
1591   // TODO: Add helper to retrieve pointers to CG.
1592   Value *Ptr = CG->RtCheck.Pointers[CG->Members[0]].PointerValue;
1593   const SCEV *Sc = SE->getSCEV(Ptr);
1594 
1595   unsigned AS = Ptr->getType()->getPointerAddressSpace();
1596   LLVMContext &Ctx = Loc->getContext();
1597 
1598   // Use this type for pointer arithmetic.
1599   Type *PtrArithTy = Type::getInt8PtrTy(Ctx, AS);
1600 
1601   if (SE->isLoopInvariant(Sc, TheLoop)) {
1602     LLVM_DEBUG(dbgs() << "LAA: Adding RT check for a loop invariant ptr:"
1603                       << *Ptr << "\n");
1604     // Ptr could be in the loop body. If so, expand a new one at the correct
1605     // location.
1606     Instruction *Inst = dyn_cast<Instruction>(Ptr);
1607     Value *NewPtr = (Inst && TheLoop->contains(Inst))
1608                         ? Exp.expandCodeFor(Sc, PtrArithTy, Loc)
1609                         : Ptr;
1610     // We must return a half-open range, which means incrementing Sc.
1611     const SCEV *ScPlusOne = SE->getAddExpr(Sc, SE->getOne(PtrArithTy));
1612     Value *NewPtrPlusOne = Exp.expandCodeFor(ScPlusOne, PtrArithTy, Loc);
1613     return {NewPtr, NewPtrPlusOne};
1614   } else {
1615     Value *Start = nullptr, *End = nullptr;
1616     LLVM_DEBUG(dbgs() << "LAA: Adding RT check for range:\n");
1617     Start = Exp.expandCodeFor(CG->Low, PtrArithTy, Loc);
1618     End = Exp.expandCodeFor(CG->High, PtrArithTy, Loc);
1619     LLVM_DEBUG(dbgs() << "Start: " << *CG->Low << " End: " << *CG->High
1620                       << "\n");
1621     return {Start, End};
1622   }
1623 }
1624 
1625 /// Turns a collection of checks into a collection of expanded upper and
1626 /// lower bounds for both pointers in the check.
1627 static SmallVector<std::pair<PointerBounds, PointerBounds>, 4>
expandBounds(const SmallVectorImpl<RuntimePointerCheck> & PointerChecks,Loop * L,Instruction * Loc,ScalarEvolution * SE,SCEVExpander & Exp)1628 expandBounds(const SmallVectorImpl<RuntimePointerCheck> &PointerChecks, Loop *L,
1629              Instruction *Loc, ScalarEvolution *SE, SCEVExpander &Exp) {
1630   SmallVector<std::pair<PointerBounds, PointerBounds>, 4> ChecksWithBounds;
1631 
1632   // Here we're relying on the SCEV Expander's cache to only emit code for the
1633   // same bounds once.
1634   transform(PointerChecks, std::back_inserter(ChecksWithBounds),
1635             [&](const RuntimePointerCheck &Check) {
1636               PointerBounds First = expandBounds(Check.first, L, Loc, Exp, SE),
1637                             Second =
1638                                 expandBounds(Check.second, L, Loc, Exp, SE);
1639               return std::make_pair(First, Second);
1640             });
1641 
1642   return ChecksWithBounds;
1643 }
1644 
addRuntimeChecks(Instruction * Loc,Loop * TheLoop,const SmallVectorImpl<RuntimePointerCheck> & PointerChecks,ScalarEvolution * SE)1645 std::pair<Instruction *, Instruction *> llvm::addRuntimeChecks(
1646     Instruction *Loc, Loop *TheLoop,
1647     const SmallVectorImpl<RuntimePointerCheck> &PointerChecks,
1648     ScalarEvolution *SE) {
1649   // TODO: Move noalias annotation code from LoopVersioning here and share with LV if possible.
1650   // TODO: Pass  RtPtrChecking instead of PointerChecks and SE separately, if possible
1651   const DataLayout &DL = TheLoop->getHeader()->getModule()->getDataLayout();
1652   SCEVExpander Exp(*SE, DL, "induction");
1653   auto ExpandedChecks = expandBounds(PointerChecks, TheLoop, Loc, SE, Exp);
1654 
1655   LLVMContext &Ctx = Loc->getContext();
1656   Instruction *FirstInst = nullptr;
1657   IRBuilder<> ChkBuilder(Loc);
1658   // Our instructions might fold to a constant.
1659   Value *MemoryRuntimeCheck = nullptr;
1660 
1661   // FIXME: this helper is currently a duplicate of the one in
1662   // LoopVectorize.cpp.
1663   auto GetFirstInst = [](Instruction *FirstInst, Value *V,
1664                          Instruction *Loc) -> Instruction * {
1665     if (FirstInst)
1666       return FirstInst;
1667     if (Instruction *I = dyn_cast<Instruction>(V))
1668       return I->getParent() == Loc->getParent() ? I : nullptr;
1669     return nullptr;
1670   };
1671 
1672   for (const auto &Check : ExpandedChecks) {
1673     const PointerBounds &A = Check.first, &B = Check.second;
1674     // Check if two pointers (A and B) conflict where conflict is computed as:
1675     // start(A) <= end(B) && start(B) <= end(A)
1676     unsigned AS0 = A.Start->getType()->getPointerAddressSpace();
1677     unsigned AS1 = B.Start->getType()->getPointerAddressSpace();
1678 
1679     assert((AS0 == B.End->getType()->getPointerAddressSpace()) &&
1680            (AS1 == A.End->getType()->getPointerAddressSpace()) &&
1681            "Trying to bounds check pointers with different address spaces");
1682 
1683     Type *PtrArithTy0 = Type::getInt8PtrTy(Ctx, AS0);
1684     Type *PtrArithTy1 = Type::getInt8PtrTy(Ctx, AS1);
1685 
1686     Value *Start0 = ChkBuilder.CreateBitCast(A.Start, PtrArithTy0, "bc");
1687     Value *Start1 = ChkBuilder.CreateBitCast(B.Start, PtrArithTy1, "bc");
1688     Value *End0 = ChkBuilder.CreateBitCast(A.End, PtrArithTy1, "bc");
1689     Value *End1 = ChkBuilder.CreateBitCast(B.End, PtrArithTy0, "bc");
1690 
1691     // [A|B].Start points to the first accessed byte under base [A|B].
1692     // [A|B].End points to the last accessed byte, plus one.
1693     // There is no conflict when the intervals are disjoint:
1694     // NoConflict = (B.Start >= A.End) || (A.Start >= B.End)
1695     //
1696     // bound0 = (B.Start < A.End)
1697     // bound1 = (A.Start < B.End)
1698     //  IsConflict = bound0 & bound1
1699     Value *Cmp0 = ChkBuilder.CreateICmpULT(Start0, End1, "bound0");
1700     FirstInst = GetFirstInst(FirstInst, Cmp0, Loc);
1701     Value *Cmp1 = ChkBuilder.CreateICmpULT(Start1, End0, "bound1");
1702     FirstInst = GetFirstInst(FirstInst, Cmp1, Loc);
1703     Value *IsConflict = ChkBuilder.CreateAnd(Cmp0, Cmp1, "found.conflict");
1704     FirstInst = GetFirstInst(FirstInst, IsConflict, Loc);
1705     if (MemoryRuntimeCheck) {
1706       IsConflict =
1707           ChkBuilder.CreateOr(MemoryRuntimeCheck, IsConflict, "conflict.rdx");
1708       FirstInst = GetFirstInst(FirstInst, IsConflict, Loc);
1709     }
1710     MemoryRuntimeCheck = IsConflict;
1711   }
1712 
1713   if (!MemoryRuntimeCheck)
1714     return std::make_pair(nullptr, nullptr);
1715 
1716   // We have to do this trickery because the IRBuilder might fold the check to a
1717   // constant expression in which case there is no Instruction anchored in a
1718   // the block.
1719   Instruction *Check =
1720       BinaryOperator::CreateAnd(MemoryRuntimeCheck, ConstantInt::getTrue(Ctx));
1721   ChkBuilder.Insert(Check, "memcheck.conflict");
1722   FirstInst = GetFirstInst(FirstInst, Check, Loc);
1723   return std::make_pair(FirstInst, Check);
1724 }
1725