1 //===-- UnrollLoop.cpp - Loop unrolling utilities -------------------------===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file implements some loop unrolling utilities. It does not define any
11 // actual pass or policy, but provides a single function to perform loop
12 // unrolling.
13 //
14 // The process of unrolling can produce extraneous basic blocks linked with
15 // unconditional branches.  This will be corrected in the future.
16 //
17 //===----------------------------------------------------------------------===//
18 
19 #include "llvm/Transforms/Utils/UnrollLoop.h"
20 #include "llvm/ADT/SmallPtrSet.h"
21 #include "llvm/ADT/Statistic.h"
22 #include "llvm/Analysis/AssumptionCache.h"
23 #include "llvm/Analysis/InstructionSimplify.h"
24 #include "llvm/Analysis/LoopIterator.h"
25 #include "llvm/Analysis/LoopPass.h"
26 #include "llvm/Analysis/ScalarEvolution.h"
27 #include "llvm/IR/BasicBlock.h"
28 #include "llvm/IR/DataLayout.h"
29 #include "llvm/IR/DiagnosticInfo.h"
30 #include "llvm/IR/Dominators.h"
31 #include "llvm/IR/LLVMContext.h"
32 #include "llvm/Support/Debug.h"
33 #include "llvm/Support/raw_ostream.h"
34 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
35 #include "llvm/Transforms/Utils/Cloning.h"
36 #include "llvm/Transforms/Utils/Local.h"
37 #include "llvm/Transforms/Utils/LoopUtils.h"
38 #include "llvm/Transforms/Utils/SimplifyIndVar.h"
39 using namespace llvm;
40 
41 #define DEBUG_TYPE "loop-unroll"
42 
43 // TODO: Should these be here or in LoopUnroll?
44 STATISTIC(NumCompletelyUnrolled, "Number of loops completely unrolled");
45 STATISTIC(NumUnrolled, "Number of loops unrolled (completely or otherwise)");
46 
47 /// RemapInstruction - Convert the instruction operands from referencing the
48 /// current values into those specified by VMap.
RemapInstruction(Instruction * I,ValueToValueMapTy & VMap)49 static inline void RemapInstruction(Instruction *I,
50                                     ValueToValueMapTy &VMap) {
51   for (unsigned op = 0, E = I->getNumOperands(); op != E; ++op) {
52     Value *Op = I->getOperand(op);
53     ValueToValueMapTy::iterator It = VMap.find(Op);
54     if (It != VMap.end())
55       I->setOperand(op, It->second);
56   }
57 
58   if (PHINode *PN = dyn_cast<PHINode>(I)) {
59     for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
60       ValueToValueMapTy::iterator It = VMap.find(PN->getIncomingBlock(i));
61       if (It != VMap.end())
62         PN->setIncomingBlock(i, cast<BasicBlock>(It->second));
63     }
64   }
65 }
66 
67 /// FoldBlockIntoPredecessor - Folds a basic block into its predecessor if it
68 /// only has one predecessor, and that predecessor only has one successor.
69 /// The LoopInfo Analysis that is passed will be kept consistent.  If folding is
70 /// successful references to the containing loop must be removed from
71 /// ScalarEvolution by calling ScalarEvolution::forgetLoop because SE may have
72 /// references to the eliminated BB.  The argument ForgottenLoops contains a set
73 /// of loops that have already been forgotten to prevent redundant, expensive
74 /// calls to ScalarEvolution::forgetLoop.  Returns the new combined block.
75 static BasicBlock *
FoldBlockIntoPredecessor(BasicBlock * BB,LoopInfo * LI,ScalarEvolution * SE,SmallPtrSetImpl<Loop * > & ForgottenLoops)76 FoldBlockIntoPredecessor(BasicBlock *BB, LoopInfo* LI, ScalarEvolution *SE,
77                          SmallPtrSetImpl<Loop *> &ForgottenLoops) {
78   // Merge basic blocks into their predecessor if there is only one distinct
79   // pred, and if there is only one distinct successor of the predecessor, and
80   // if there are no PHI nodes.
81   BasicBlock *OnlyPred = BB->getSinglePredecessor();
82   if (!OnlyPred) return nullptr;
83 
84   if (OnlyPred->getTerminator()->getNumSuccessors() != 1)
85     return nullptr;
86 
87   DEBUG(dbgs() << "Merging: " << *BB << "into: " << *OnlyPred);
88 
89   // Resolve any PHI nodes at the start of the block.  They are all
90   // guaranteed to have exactly one entry if they exist, unless there are
91   // multiple duplicate (but guaranteed to be equal) entries for the
92   // incoming edges.  This occurs when there are multiple edges from
93   // OnlyPred to OnlySucc.
94   FoldSingleEntryPHINodes(BB);
95 
96   // Delete the unconditional branch from the predecessor...
97   OnlyPred->getInstList().pop_back();
98 
99   // Make all PHI nodes that referred to BB now refer to Pred as their
100   // source...
101   BB->replaceAllUsesWith(OnlyPred);
102 
103   // Move all definitions in the successor to the predecessor...
104   OnlyPred->getInstList().splice(OnlyPred->end(), BB->getInstList());
105 
106   // OldName will be valid until erased.
107   StringRef OldName = BB->getName();
108 
109   // Erase basic block from the function...
110 
111   // ScalarEvolution holds references to loop exit blocks.
112   if (SE) {
113     if (Loop *L = LI->getLoopFor(BB)) {
114       if (ForgottenLoops.insert(L).second)
115         SE->forgetLoop(L);
116     }
117   }
118   LI->removeBlock(BB);
119 
120   // Inherit predecessor's name if it exists...
121   if (!OldName.empty() && !OnlyPred->hasName())
122     OnlyPred->setName(OldName);
123 
124   BB->eraseFromParent();
125 
126   return OnlyPred;
127 }
128 
129 /// Unroll the given loop by Count. The loop must be in LCSSA form. Returns true
130 /// if unrolling was successful, or false if the loop was unmodified. Unrolling
131 /// can only fail when the loop's latch block is not terminated by a conditional
132 /// branch instruction. However, if the trip count (and multiple) are not known,
133 /// loop unrolling will mostly produce more code that is no faster.
134 ///
135 /// TripCount is generally defined as the number of times the loop header
136 /// executes. UnrollLoop relaxes the definition to permit early exits: here
137 /// TripCount is the iteration on which control exits LatchBlock if no early
138 /// exits were taken. Note that UnrollLoop assumes that the loop counter test
139 /// terminates LatchBlock in order to remove unnecesssary instances of the
140 /// test. In other words, control may exit the loop prior to TripCount
141 /// iterations via an early branch, but control may not exit the loop from the
142 /// LatchBlock's terminator prior to TripCount iterations.
143 ///
144 /// Similarly, TripMultiple divides the number of times that the LatchBlock may
145 /// execute without exiting the loop.
146 ///
147 /// If AllowRuntime is true then UnrollLoop will consider unrolling loops that
148 /// have a runtime (i.e. not compile time constant) trip count.  Unrolling these
149 /// loops require a unroll "prologue" that runs "RuntimeTripCount % Count"
150 /// iterations before branching into the unrolled loop.  UnrollLoop will not
151 /// runtime-unroll the loop if computing RuntimeTripCount will be expensive and
152 /// AllowExpensiveTripCount is false.
153 ///
154 /// The LoopInfo Analysis that is passed will be kept consistent.
155 ///
156 /// This utility preserves LoopInfo. It will also preserve ScalarEvolution and
157 /// DominatorTree if they are non-null.
UnrollLoop(Loop * L,unsigned Count,unsigned TripCount,bool AllowRuntime,bool AllowExpensiveTripCount,unsigned TripMultiple,LoopInfo * LI,ScalarEvolution * SE,DominatorTree * DT,AssumptionCache * AC,bool PreserveLCSSA)158 bool llvm::UnrollLoop(Loop *L, unsigned Count, unsigned TripCount,
159                       bool AllowRuntime, bool AllowExpensiveTripCount,
160                       unsigned TripMultiple, LoopInfo *LI, ScalarEvolution *SE,
161                       DominatorTree *DT, AssumptionCache *AC,
162                       bool PreserveLCSSA) {
163   BasicBlock *Preheader = L->getLoopPreheader();
164   if (!Preheader) {
165     DEBUG(dbgs() << "  Can't unroll; loop preheader-insertion failed.\n");
166     return false;
167   }
168 
169   BasicBlock *LatchBlock = L->getLoopLatch();
170   if (!LatchBlock) {
171     DEBUG(dbgs() << "  Can't unroll; loop exit-block-insertion failed.\n");
172     return false;
173   }
174 
175   // Loops with indirectbr cannot be cloned.
176   if (!L->isSafeToClone()) {
177     DEBUG(dbgs() << "  Can't unroll; Loop body cannot be cloned.\n");
178     return false;
179   }
180 
181   BasicBlock *Header = L->getHeader();
182   BranchInst *BI = dyn_cast<BranchInst>(LatchBlock->getTerminator());
183 
184   if (!BI || BI->isUnconditional()) {
185     // The loop-rotate pass can be helpful to avoid this in many cases.
186     DEBUG(dbgs() <<
187              "  Can't unroll; loop not terminated by a conditional branch.\n");
188     return false;
189   }
190 
191   if (Header->hasAddressTaken()) {
192     // The loop-rotate pass can be helpful to avoid this in many cases.
193     DEBUG(dbgs() <<
194           "  Won't unroll loop: address of header block is taken.\n");
195     return false;
196   }
197 
198   if (TripCount != 0)
199     DEBUG(dbgs() << "  Trip Count = " << TripCount << "\n");
200   if (TripMultiple != 1)
201     DEBUG(dbgs() << "  Trip Multiple = " << TripMultiple << "\n");
202 
203   // Effectively "DCE" unrolled iterations that are beyond the tripcount
204   // and will never be executed.
205   if (TripCount != 0 && Count > TripCount)
206     Count = TripCount;
207 
208   // Don't enter the unroll code if there is nothing to do. This way we don't
209   // need to support "partial unrolling by 1".
210   if (TripCount == 0 && Count < 2)
211     return false;
212 
213   assert(Count > 0);
214   assert(TripMultiple > 0);
215   assert(TripCount == 0 || TripCount % TripMultiple == 0);
216 
217   // Are we eliminating the loop control altogether?
218   bool CompletelyUnroll = Count == TripCount;
219   SmallVector<BasicBlock *, 4> ExitBlocks;
220   L->getExitBlocks(ExitBlocks);
221   Loop *ParentL = L->getParentLoop();
222   bool AllExitsAreInsideParentLoop = !ParentL ||
223       std::all_of(ExitBlocks.begin(), ExitBlocks.end(),
224                   [&](BasicBlock *BB) { return ParentL->contains(BB); });
225 
226   // We assume a run-time trip count if the compiler cannot
227   // figure out the loop trip count and the unroll-runtime
228   // flag is specified.
229   bool RuntimeTripCount = (TripCount == 0 && Count > 0 && AllowRuntime);
230 
231   if (RuntimeTripCount &&
232       !UnrollRuntimeLoopProlog(L, Count, AllowExpensiveTripCount, LI, SE, DT,
233                                PreserveLCSSA))
234     return false;
235 
236   // Notify ScalarEvolution that the loop will be substantially changed,
237   // if not outright eliminated.
238   if (SE)
239     SE->forgetLoop(L);
240 
241   // If we know the trip count, we know the multiple...
242   unsigned BreakoutTrip = 0;
243   if (TripCount != 0) {
244     BreakoutTrip = TripCount % Count;
245     TripMultiple = 0;
246   } else {
247     // Figure out what multiple to use.
248     BreakoutTrip = TripMultiple =
249       (unsigned)GreatestCommonDivisor64(Count, TripMultiple);
250   }
251 
252   // Report the unrolling decision.
253   DebugLoc LoopLoc = L->getStartLoc();
254   Function *F = Header->getParent();
255   LLVMContext &Ctx = F->getContext();
256 
257   if (CompletelyUnroll) {
258     DEBUG(dbgs() << "COMPLETELY UNROLLING loop %" << Header->getName()
259           << " with trip count " << TripCount << "!\n");
260     emitOptimizationRemark(Ctx, DEBUG_TYPE, *F, LoopLoc,
261                            Twine("completely unrolled loop with ") +
262                                Twine(TripCount) + " iterations");
263   } else {
264     auto EmitDiag = [&](const Twine &T) {
265       emitOptimizationRemark(Ctx, DEBUG_TYPE, *F, LoopLoc,
266                              "unrolled loop by a factor of " + Twine(Count) +
267                                  T);
268     };
269 
270     DEBUG(dbgs() << "UNROLLING loop %" << Header->getName()
271           << " by " << Count);
272     if (TripMultiple == 0 || BreakoutTrip != TripMultiple) {
273       DEBUG(dbgs() << " with a breakout at trip " << BreakoutTrip);
274       EmitDiag(" with a breakout at trip " + Twine(BreakoutTrip));
275     } else if (TripMultiple != 1) {
276       DEBUG(dbgs() << " with " << TripMultiple << " trips per branch");
277       EmitDiag(" with " + Twine(TripMultiple) + " trips per branch");
278     } else if (RuntimeTripCount) {
279       DEBUG(dbgs() << " with run-time trip count");
280       EmitDiag(" with run-time trip count");
281     }
282     DEBUG(dbgs() << "!\n");
283   }
284 
285   bool ContinueOnTrue = L->contains(BI->getSuccessor(0));
286   BasicBlock *LoopExit = BI->getSuccessor(ContinueOnTrue);
287 
288   // For the first iteration of the loop, we should use the precloned values for
289   // PHI nodes.  Insert associations now.
290   ValueToValueMapTy LastValueMap;
291   std::vector<PHINode*> OrigPHINode;
292   for (BasicBlock::iterator I = Header->begin(); isa<PHINode>(I); ++I) {
293     OrigPHINode.push_back(cast<PHINode>(I));
294   }
295 
296   std::vector<BasicBlock*> Headers;
297   std::vector<BasicBlock*> Latches;
298   Headers.push_back(Header);
299   Latches.push_back(LatchBlock);
300 
301   // The current on-the-fly SSA update requires blocks to be processed in
302   // reverse postorder so that LastValueMap contains the correct value at each
303   // exit.
304   LoopBlocksDFS DFS(L);
305   DFS.perform(LI);
306 
307   // Stash the DFS iterators before adding blocks to the loop.
308   LoopBlocksDFS::RPOIterator BlockBegin = DFS.beginRPO();
309   LoopBlocksDFS::RPOIterator BlockEnd = DFS.endRPO();
310 
311   for (unsigned It = 1; It != Count; ++It) {
312     std::vector<BasicBlock*> NewBlocks;
313     SmallDenseMap<const Loop *, Loop *, 4> NewLoops;
314     NewLoops[L] = L;
315 
316     for (LoopBlocksDFS::RPOIterator BB = BlockBegin; BB != BlockEnd; ++BB) {
317       ValueToValueMapTy VMap;
318       BasicBlock *New = CloneBasicBlock(*BB, VMap, "." + Twine(It));
319       Header->getParent()->getBasicBlockList().push_back(New);
320 
321       // Tell LI about New.
322       if (*BB == Header) {
323         assert(LI->getLoopFor(*BB) == L && "Header should not be in a sub-loop");
324         L->addBasicBlockToLoop(New, *LI);
325       } else {
326         // Figure out which loop New is in.
327         const Loop *OldLoop = LI->getLoopFor(*BB);
328         assert(OldLoop && "Should (at least) be in the loop being unrolled!");
329 
330         Loop *&NewLoop = NewLoops[OldLoop];
331         if (!NewLoop) {
332           // Found a new sub-loop.
333           assert(*BB == OldLoop->getHeader() &&
334                  "Header should be first in RPO");
335 
336           Loop *NewLoopParent = NewLoops.lookup(OldLoop->getParentLoop());
337           assert(NewLoopParent &&
338                  "Expected parent loop before sub-loop in RPO");
339           NewLoop = new Loop;
340           NewLoopParent->addChildLoop(NewLoop);
341 
342           // Forget the old loop, since its inputs may have changed.
343           if (SE)
344             SE->forgetLoop(OldLoop);
345         }
346         NewLoop->addBasicBlockToLoop(New, *LI);
347       }
348 
349       if (*BB == Header)
350         // Loop over all of the PHI nodes in the block, changing them to use
351         // the incoming values from the previous block.
352         for (unsigned i = 0, e = OrigPHINode.size(); i != e; ++i) {
353           PHINode *NewPHI = cast<PHINode>(VMap[OrigPHINode[i]]);
354           Value *InVal = NewPHI->getIncomingValueForBlock(LatchBlock);
355           if (Instruction *InValI = dyn_cast<Instruction>(InVal))
356             if (It > 1 && L->contains(InValI))
357               InVal = LastValueMap[InValI];
358           VMap[OrigPHINode[i]] = InVal;
359           New->getInstList().erase(NewPHI);
360         }
361 
362       // Update our running map of newest clones
363       LastValueMap[*BB] = New;
364       for (ValueToValueMapTy::iterator VI = VMap.begin(), VE = VMap.end();
365            VI != VE; ++VI)
366         LastValueMap[VI->first] = VI->second;
367 
368       // Add phi entries for newly created values to all exit blocks.
369       for (succ_iterator SI = succ_begin(*BB), SE = succ_end(*BB);
370            SI != SE; ++SI) {
371         if (L->contains(*SI))
372           continue;
373         for (BasicBlock::iterator BBI = (*SI)->begin();
374              PHINode *phi = dyn_cast<PHINode>(BBI); ++BBI) {
375           Value *Incoming = phi->getIncomingValueForBlock(*BB);
376           ValueToValueMapTy::iterator It = LastValueMap.find(Incoming);
377           if (It != LastValueMap.end())
378             Incoming = It->second;
379           phi->addIncoming(Incoming, New);
380         }
381       }
382       // Keep track of new headers and latches as we create them, so that
383       // we can insert the proper branches later.
384       if (*BB == Header)
385         Headers.push_back(New);
386       if (*BB == LatchBlock)
387         Latches.push_back(New);
388 
389       NewBlocks.push_back(New);
390     }
391 
392     // Remap all instructions in the most recent iteration
393     for (unsigned i = 0; i < NewBlocks.size(); ++i)
394       for (BasicBlock::iterator I = NewBlocks[i]->begin(),
395            E = NewBlocks[i]->end(); I != E; ++I)
396         ::RemapInstruction(&*I, LastValueMap);
397   }
398 
399   // Loop over the PHI nodes in the original block, setting incoming values.
400   for (unsigned i = 0, e = OrigPHINode.size(); i != e; ++i) {
401     PHINode *PN = OrigPHINode[i];
402     if (CompletelyUnroll) {
403       PN->replaceAllUsesWith(PN->getIncomingValueForBlock(Preheader));
404       Header->getInstList().erase(PN);
405     }
406     else if (Count > 1) {
407       Value *InVal = PN->removeIncomingValue(LatchBlock, false);
408       // If this value was defined in the loop, take the value defined by the
409       // last iteration of the loop.
410       if (Instruction *InValI = dyn_cast<Instruction>(InVal)) {
411         if (L->contains(InValI))
412           InVal = LastValueMap[InVal];
413       }
414       assert(Latches.back() == LastValueMap[LatchBlock] && "bad last latch");
415       PN->addIncoming(InVal, Latches.back());
416     }
417   }
418 
419   // Now that all the basic blocks for the unrolled iterations are in place,
420   // set up the branches to connect them.
421   for (unsigned i = 0, e = Latches.size(); i != e; ++i) {
422     // The original branch was replicated in each unrolled iteration.
423     BranchInst *Term = cast<BranchInst>(Latches[i]->getTerminator());
424 
425     // The branch destination.
426     unsigned j = (i + 1) % e;
427     BasicBlock *Dest = Headers[j];
428     bool NeedConditional = true;
429 
430     if (RuntimeTripCount && j != 0) {
431       NeedConditional = false;
432     }
433 
434     // For a complete unroll, make the last iteration end with a branch
435     // to the exit block.
436     if (CompletelyUnroll) {
437       if (j == 0)
438         Dest = LoopExit;
439       NeedConditional = false;
440     }
441 
442     // If we know the trip count or a multiple of it, we can safely use an
443     // unconditional branch for some iterations.
444     if (j != BreakoutTrip && (TripMultiple == 0 || j % TripMultiple != 0)) {
445       NeedConditional = false;
446     }
447 
448     if (NeedConditional) {
449       // Update the conditional branch's successor for the following
450       // iteration.
451       Term->setSuccessor(!ContinueOnTrue, Dest);
452     } else {
453       // Remove phi operands at this loop exit
454       if (Dest != LoopExit) {
455         BasicBlock *BB = Latches[i];
456         for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB);
457              SI != SE; ++SI) {
458           if (*SI == Headers[i])
459             continue;
460           for (BasicBlock::iterator BBI = (*SI)->begin();
461                PHINode *Phi = dyn_cast<PHINode>(BBI); ++BBI) {
462             Phi->removeIncomingValue(BB, false);
463           }
464         }
465       }
466       // Replace the conditional branch with an unconditional one.
467       BranchInst::Create(Dest, Term);
468       Term->eraseFromParent();
469     }
470   }
471 
472   // Merge adjacent basic blocks, if possible.
473   SmallPtrSet<Loop *, 4> ForgottenLoops;
474   for (unsigned i = 0, e = Latches.size(); i != e; ++i) {
475     BranchInst *Term = cast<BranchInst>(Latches[i]->getTerminator());
476     if (Term->isUnconditional()) {
477       BasicBlock *Dest = Term->getSuccessor(0);
478       if (BasicBlock *Fold = FoldBlockIntoPredecessor(Dest, LI, SE,
479                                                       ForgottenLoops))
480         std::replace(Latches.begin(), Latches.end(), Dest, Fold);
481     }
482   }
483 
484   // FIXME: We could register any cloned assumptions instead of clearing the
485   // whole function's cache.
486   AC->clear();
487 
488   // FIXME: Reconstruct dom info, because it is not preserved properly.
489   // Incrementally updating domtree after loop unrolling would be easy.
490   if (DT)
491     DT->recalculate(*L->getHeader()->getParent());
492 
493   // Simplify any new induction variables in the partially unrolled loop.
494   if (SE && !CompletelyUnroll) {
495     SmallVector<WeakVH, 16> DeadInsts;
496     simplifyLoopIVs(L, SE, DT, LI, DeadInsts);
497 
498     // Aggressively clean up dead instructions that simplifyLoopIVs already
499     // identified. Any remaining should be cleaned up below.
500     while (!DeadInsts.empty())
501       if (Instruction *Inst =
502               dyn_cast_or_null<Instruction>(&*DeadInsts.pop_back_val()))
503         RecursivelyDeleteTriviallyDeadInstructions(Inst);
504   }
505 
506   // At this point, the code is well formed.  We now do a quick sweep over the
507   // inserted code, doing constant propagation and dead code elimination as we
508   // go.
509   const DataLayout &DL = Header->getModule()->getDataLayout();
510   const std::vector<BasicBlock*> &NewLoopBlocks = L->getBlocks();
511   for (std::vector<BasicBlock*>::const_iterator BB = NewLoopBlocks.begin(),
512        BBE = NewLoopBlocks.end(); BB != BBE; ++BB)
513     for (BasicBlock::iterator I = (*BB)->begin(), E = (*BB)->end(); I != E; ) {
514       Instruction *Inst = &*I++;
515 
516       if (isInstructionTriviallyDead(Inst))
517         (*BB)->getInstList().erase(Inst);
518       else if (Value *V = SimplifyInstruction(Inst, DL))
519         if (LI->replacementPreservesLCSSAForm(Inst, V)) {
520           Inst->replaceAllUsesWith(V);
521           (*BB)->getInstList().erase(Inst);
522         }
523     }
524 
525   NumCompletelyUnrolled += CompletelyUnroll;
526   ++NumUnrolled;
527 
528   Loop *OuterL = L->getParentLoop();
529   // Update LoopInfo if the loop is completely removed.
530   if (CompletelyUnroll)
531     LI->updateUnloop(L);;
532 
533   // If we have a pass and a DominatorTree we should re-simplify impacted loops
534   // to ensure subsequent analyses can rely on this form. We want to simplify
535   // at least one layer outside of the loop that was unrolled so that any
536   // changes to the parent loop exposed by the unrolling are considered.
537   if (DT) {
538     if (!OuterL && !CompletelyUnroll)
539       OuterL = L;
540     if (OuterL) {
541       bool Simplified = simplifyLoop(OuterL, DT, LI, SE, AC, PreserveLCSSA);
542 
543       // LCSSA must be performed on the outermost affected loop. The unrolled
544       // loop's last loop latch is guaranteed to be in the outermost loop after
545       // LoopInfo's been updated by updateUnloop.
546       Loop *LatchLoop = LI->getLoopFor(Latches.back());
547       if (!OuterL->contains(LatchLoop))
548         while (OuterL->getParentLoop() != LatchLoop)
549           OuterL = OuterL->getParentLoop();
550 
551       if (CompletelyUnroll && (!AllExitsAreInsideParentLoop || Simplified))
552         formLCSSARecursively(*OuterL, *DT, LI, SE);
553       else
554         assert(OuterL->isLCSSAForm(*DT) &&
555                "Loops should be in LCSSA form after loop-unroll.");
556     }
557   }
558 
559   return true;
560 }
561 
562 /// Given an llvm.loop loop id metadata node, returns the loop hint metadata
563 /// node with the given name (for example, "llvm.loop.unroll.count"). If no
564 /// such metadata node exists, then nullptr is returned.
GetUnrollMetadata(MDNode * LoopID,StringRef Name)565 MDNode *llvm::GetUnrollMetadata(MDNode *LoopID, StringRef Name) {
566   // First operand should refer to the loop id itself.
567   assert(LoopID->getNumOperands() > 0 && "requires at least one operand");
568   assert(LoopID->getOperand(0) == LoopID && "invalid loop id");
569 
570   for (unsigned i = 1, e = LoopID->getNumOperands(); i < e; ++i) {
571     MDNode *MD = dyn_cast<MDNode>(LoopID->getOperand(i));
572     if (!MD)
573       continue;
574 
575     MDString *S = dyn_cast<MDString>(MD->getOperand(0));
576     if (!S)
577       continue;
578 
579     if (Name.equals(S->getString()))
580       return MD;
581   }
582   return nullptr;
583 }
584