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