LLVM  14.0.0git
LoopSimplify.cpp
Go to the documentation of this file.
1 //===- LoopSimplify.cpp - Loop Canonicalization Pass ----------------------===//
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 pass performs several transformations to transform natural loops into a
10 // simpler form, which makes subsequent analyses and transformations simpler and
11 // more effective.
12 //
13 // Loop pre-header insertion guarantees that there is a single, non-critical
14 // entry edge from outside of the loop to the loop header. This simplifies a
15 // number of analyses and transformations, such as LICM.
16 //
17 // Loop exit-block insertion guarantees that all exit blocks from the loop
18 // (blocks which are outside of the loop that have predecessors inside of the
19 // loop) only have predecessors from inside of the loop (and are thus dominated
20 // by the loop header). This simplifies transformations such as store-sinking
21 // that are built into LICM.
22 //
23 // This pass also guarantees that loops will have exactly one backedge.
24 //
25 // Indirectbr instructions introduce several complications. If the loop
26 // contains or is entered by an indirectbr instruction, it may not be possible
27 // to transform the loop and make these guarantees. Client code should check
28 // that these conditions are true before relying on them.
29 //
30 // Similar complications arise from callbr instructions, particularly in
31 // asm-goto where blockaddress expressions are used.
32 //
33 // Note that the simplifycfg pass will clean up blocks which are split out but
34 // end up being unnecessary, so usage of this pass should not pessimize
35 // generated code.
36 //
37 // This pass obviously modifies the CFG, but updates loop information and
38 // dominator information.
39 //
40 //===----------------------------------------------------------------------===//
41 
44 #include "llvm/ADT/SetOperations.h"
45 #include "llvm/ADT/SetVector.h"
46 #include "llvm/ADT/SmallVector.h"
47 #include "llvm/ADT/Statistic.h"
55 #include "llvm/Analysis/LoopInfo.h"
60 #include "llvm/IR/CFG.h"
61 #include "llvm/IR/Constants.h"
62 #include "llvm/IR/DataLayout.h"
63 #include "llvm/IR/Dominators.h"
64 #include "llvm/IR/Function.h"
65 #include "llvm/IR/Instructions.h"
66 #include "llvm/IR/IntrinsicInst.h"
67 #include "llvm/IR/LLVMContext.h"
68 #include "llvm/IR/Module.h"
69 #include "llvm/IR/Type.h"
70 #include "llvm/InitializePasses.h"
71 #include "llvm/Support/Debug.h"
73 #include "llvm/Transforms/Utils.h"
77 using namespace llvm;
78 
79 #define DEBUG_TYPE "loop-simplify"
80 
81 STATISTIC(NumNested , "Number of nested loops split out");
82 
83 // If the block isn't already, move the new block to right after some 'outside
84 // block' block. This prevents the preheader from being placed inside the loop
85 // body, e.g. when the loop hasn't been rotated.
88  Loop *L) {
89  // Check to see if NewBB is already well placed.
90  Function::iterator BBI = --NewBB->getIterator();
91  for (unsigned i = 0, e = SplitPreds.size(); i != e; ++i) {
92  if (&*BBI == SplitPreds[i])
93  return;
94  }
95 
96  // If it isn't already after an outside block, move it after one. This is
97  // always good as it makes the uncond branch from the outside block into a
98  // fall-through.
99 
100  // Figure out *which* outside block to put this after. Prefer an outside
101  // block that neighbors a BB actually in the loop.
102  BasicBlock *FoundBB = nullptr;
103  for (unsigned i = 0, e = SplitPreds.size(); i != e; ++i) {
104  Function::iterator BBI = SplitPreds[i]->getIterator();
105  if (++BBI != NewBB->getParent()->end() && L->contains(&*BBI)) {
106  FoundBB = SplitPreds[i];
107  break;
108  }
109  }
110 
111  // If our heuristic for a *good* bb to place this after doesn't find
112  // anything, just pick something. It's likely better than leaving it within
113  // the loop.
114  if (!FoundBB)
115  FoundBB = SplitPreds[0];
116  NewBB->moveAfter(FoundBB);
117 }
118 
119 /// InsertPreheaderForLoop - Once we discover that a loop doesn't have a
120 /// preheader, this method is called to insert one. This method has two phases:
121 /// preheader insertion and analysis updating.
122 ///
124  LoopInfo *LI, MemorySSAUpdater *MSSAU,
125  bool PreserveLCSSA) {
126  BasicBlock *Header = L->getHeader();
127 
128  // Compute the set of predecessors of the loop that are not in the loop.
129  SmallVector<BasicBlock*, 8> OutsideBlocks;
130  for (BasicBlock *P : predecessors(Header)) {
131  if (!L->contains(P)) { // Coming in from outside the loop?
132  // If the loop is branched to from an indirect terminator, we won't
133  // be able to fully transform the loop, because it prohibits
134  // edge splitting.
135  if (P->getTerminator()->isIndirectTerminator())
136  return nullptr;
137 
138  // Keep track of it.
139  OutsideBlocks.push_back(P);
140  }
141  }
142 
143  // Split out the loop pre-header.
144  BasicBlock *PreheaderBB;
145  PreheaderBB = SplitBlockPredecessors(Header, OutsideBlocks, ".preheader", DT,
146  LI, MSSAU, PreserveLCSSA);
147  if (!PreheaderBB)
148  return nullptr;
149 
150  LLVM_DEBUG(dbgs() << "LoopSimplify: Creating pre-header "
151  << PreheaderBB->getName() << "\n");
152 
153  // Make sure that NewBB is put someplace intelligent, which doesn't mess up
154  // code layout too horribly.
155  placeSplitBlockCarefully(PreheaderBB, OutsideBlocks, L);
156 
157  return PreheaderBB;
158 }
159 
160 /// Add the specified block, and all of its predecessors, to the specified set,
161 /// if it's not already in there. Stop predecessor traversal when we reach
162 /// StopBlock.
163 static void addBlockAndPredsToSet(BasicBlock *InputBB, BasicBlock *StopBlock,
166  Worklist.push_back(InputBB);
167  do {
168  BasicBlock *BB = Worklist.pop_back_val();
169  if (Blocks.insert(BB).second && BB != StopBlock)
170  // If BB is not already processed and it is not a stop block then
171  // insert its predecessor in the work list
172  append_range(Worklist, predecessors(BB));
173  } while (!Worklist.empty());
174 }
175 
176 /// The first part of loop-nestification is to find a PHI node that tells
177 /// us how to partition the loops.
179  AssumptionCache *AC) {
180  const DataLayout &DL = L->getHeader()->getModule()->getDataLayout();
181  for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(I); ) {
182  PHINode *PN = cast<PHINode>(I);
183  ++I;
184  if (Value *V = SimplifyInstruction(PN, {DL, nullptr, DT, AC})) {
185  // This is a degenerate PHI already, don't modify it!
186  PN->replaceAllUsesWith(V);
187  PN->eraseFromParent();
188  continue;
189  }
190 
191  // Scan this PHI node looking for a use of the PHI node by itself.
192  for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
193  if (PN->getIncomingValue(i) == PN &&
194  L->contains(PN->getIncomingBlock(i)))
195  // We found something tasty to remove.
196  return PN;
197  }
198  return nullptr;
199 }
200 
201 /// If this loop has multiple backedges, try to pull one of them out into
202 /// a nested loop.
203 ///
204 /// This is important for code that looks like
205 /// this:
206 ///
207 /// Loop:
208 /// ...
209 /// br cond, Loop, Next
210 /// ...
211 /// br cond2, Loop, Out
212 ///
213 /// To identify this common case, we look at the PHI nodes in the header of the
214 /// loop. PHI nodes with unchanging values on one backedge correspond to values
215 /// that change in the "outer" loop, but not in the "inner" loop.
216 ///
217 /// If we are able to separate out a loop, return the new outer loop that was
218 /// created.
219 ///
220 static Loop *separateNestedLoop(Loop *L, BasicBlock *Preheader,
221  DominatorTree *DT, LoopInfo *LI,
222  ScalarEvolution *SE, bool PreserveLCSSA,
223  AssumptionCache *AC, MemorySSAUpdater *MSSAU) {
224  // Don't try to separate loops without a preheader.
225  if (!Preheader)
226  return nullptr;
227 
228  // Treat the presence of convergent functions conservatively. The
229  // transformation is invalid if calls to certain convergent
230  // functions (like an AMDGPU barrier) get included in the resulting
231  // inner loop. But blocks meant for the inner loop will be
232  // identified later at a point where it's too late to abort the
233  // transformation. Also, the convergent attribute is not really
234  // sufficient to express the semantics of functions that are
235  // affected by this transformation. So we choose to back off if such
236  // a function call is present until a better alternative becomes
237  // available. This is similar to the conservative treatment of
238  // convergent function calls in GVNHoist and JumpThreading.
239  for (auto BB : L->blocks()) {
240  for (auto &II : *BB) {
241  if (auto CI = dyn_cast<CallBase>(&II)) {
242  if (CI->isConvergent()) {
243  return nullptr;
244  }
245  }
246  }
247  }
248 
249  // The header is not a landing pad; preheader insertion should ensure this.
250  BasicBlock *Header = L->getHeader();
251  assert(!Header->isEHPad() && "Can't insert backedge to EH pad");
252 
253  PHINode *PN = findPHIToPartitionLoops(L, DT, AC);
254  if (!PN) return nullptr; // No known way to partition.
255 
256  // Pull out all predecessors that have varying values in the loop. This
257  // handles the case when a PHI node has multiple instances of itself as
258  // arguments.
259  SmallVector<BasicBlock*, 8> OuterLoopPreds;
260  for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
261  if (PN->getIncomingValue(i) != PN ||
262  !L->contains(PN->getIncomingBlock(i))) {
263  // We can't split indirect control flow edges.
265  return nullptr;
266  OuterLoopPreds.push_back(PN->getIncomingBlock(i));
267  }
268  }
269  LLVM_DEBUG(dbgs() << "LoopSimplify: Splitting out a new outer loop\n");
270 
271  // If ScalarEvolution is around and knows anything about values in
272  // this loop, tell it to forget them, because we're about to
273  // substantially change it.
274  if (SE)
275  SE->forgetLoop(L);
276 
277  BasicBlock *NewBB = SplitBlockPredecessors(Header, OuterLoopPreds, ".outer",
278  DT, LI, MSSAU, PreserveLCSSA);
279 
280  // Make sure that NewBB is put someplace intelligent, which doesn't mess up
281  // code layout too horribly.
282  placeSplitBlockCarefully(NewBB, OuterLoopPreds, L);
283 
284  // Create the new outer loop.
285  Loop *NewOuter = LI->AllocateLoop();
286 
287  // Change the parent loop to use the outer loop as its child now.
288  if (Loop *Parent = L->getParentLoop())
289  Parent->replaceChildLoopWith(L, NewOuter);
290  else
291  LI->changeTopLevelLoop(L, NewOuter);
292 
293  // L is now a subloop of our outer loop.
294  NewOuter->addChildLoop(L);
295 
296  for (BasicBlock *BB : L->blocks())
297  NewOuter->addBlockEntry(BB);
298 
299  // Now reset the header in L, which had been moved by
300  // SplitBlockPredecessors for the outer loop.
301  L->moveToHeader(Header);
302 
303  // Determine which blocks should stay in L and which should be moved out to
304  // the Outer loop now.
306  for (BasicBlock *P : predecessors(Header)) {
307  if (DT->dominates(Header, P))
308  addBlockAndPredsToSet(P, Header, BlocksInL);
309  }
310 
311  // Scan all of the loop children of L, moving them to OuterLoop if they are
312  // not part of the inner loop.
313  const std::vector<Loop*> &SubLoops = L->getSubLoops();
314  for (size_t I = 0; I != SubLoops.size(); )
315  if (BlocksInL.count(SubLoops[I]->getHeader()))
316  ++I; // Loop remains in L
317  else
318  NewOuter->addChildLoop(L->removeChildLoop(SubLoops.begin() + I));
319 
320  SmallVector<BasicBlock *, 8> OuterLoopBlocks;
321  OuterLoopBlocks.push_back(NewBB);
322  // Now that we know which blocks are in L and which need to be moved to
323  // OuterLoop, move any blocks that need it.
324  for (unsigned i = 0; i != L->getBlocks().size(); ++i) {
325  BasicBlock *BB = L->getBlocks()[i];
326  if (!BlocksInL.count(BB)) {
327  // Move this block to the parent, updating the exit blocks sets
329  if ((*LI)[BB] == L) {
330  LI->changeLoopFor(BB, NewOuter);
331  OuterLoopBlocks.push_back(BB);
332  }
333  --i;
334  }
335  }
336 
337  // Split edges to exit blocks from the inner loop, if they emerged in the
338  // process of separating the outer one.
339  formDedicatedExitBlocks(L, DT, LI, MSSAU, PreserveLCSSA);
340 
341  if (PreserveLCSSA) {
342  // Fix LCSSA form for L. Some values, which previously were only used inside
343  // L, can now be used in NewOuter loop. We need to insert phi-nodes for them
344  // in corresponding exit blocks.
345  // We don't need to form LCSSA recursively, because there cannot be uses
346  // inside a newly created loop of defs from inner loops as those would
347  // already be a use of an LCSSA phi node.
348  formLCSSA(*L, *DT, LI, SE);
349 
350  assert(NewOuter->isRecursivelyLCSSAForm(*DT, *LI) &&
351  "LCSSA is broken after separating nested loops!");
352  }
353 
354  return NewOuter;
355 }
356 
357 /// This method is called when the specified loop has more than one
358 /// backedge in it.
359 ///
360 /// If this occurs, revector all of these backedges to target a new basic block
361 /// and have that block branch to the loop header. This ensures that loops
362 /// have exactly one backedge.
364  DominatorTree *DT, LoopInfo *LI,
365  MemorySSAUpdater *MSSAU) {
366  assert(L->getNumBackEdges() > 1 && "Must have > 1 backedge!");
367 
368  // Get information about the loop
369  BasicBlock *Header = L->getHeader();
370  Function *F = Header->getParent();
371 
372  // Unique backedge insertion currently depends on having a preheader.
373  if (!Preheader)
374  return nullptr;
375 
376  // The header is not an EH pad; preheader insertion should ensure this.
377  assert(!Header->isEHPad() && "Can't insert backedge to EH pad");
378 
379  // Figure out which basic blocks contain back-edges to the loop header.
380  std::vector<BasicBlock*> BackedgeBlocks;
381  for (BasicBlock *P : predecessors(Header)) {
382  // Indirect edges cannot be split, so we must fail if we find one.
383  if (P->getTerminator()->isIndirectTerminator())
384  return nullptr;
385 
386  if (P != Preheader) BackedgeBlocks.push_back(P);
387  }
388 
389  // Create and insert the new backedge block...
390  BasicBlock *BEBlock = BasicBlock::Create(Header->getContext(),
391  Header->getName() + ".backedge", F);
392  BranchInst *BETerminator = BranchInst::Create(Header, BEBlock);
393  BETerminator->setDebugLoc(Header->getFirstNonPHI()->getDebugLoc());
394 
395  LLVM_DEBUG(dbgs() << "LoopSimplify: Inserting unique backedge block "
396  << BEBlock->getName() << "\n");
397 
398  // Move the new backedge block to right after the last backedge block.
399  Function::iterator InsertPos = ++BackedgeBlocks.back()->getIterator();
400  F->getBasicBlockList().splice(InsertPos, F->getBasicBlockList(), BEBlock);
401 
402  // Now that the block has been inserted into the function, create PHI nodes in
403  // the backedge block which correspond to any PHI nodes in the header block.
404  for (BasicBlock::iterator I = Header->begin(); isa<PHINode>(I); ++I) {
405  PHINode *PN = cast<PHINode>(I);
406  PHINode *NewPN = PHINode::Create(PN->getType(), BackedgeBlocks.size(),
407  PN->getName()+".be", BETerminator);
408 
409  // Loop over the PHI node, moving all entries except the one for the
410  // preheader over to the new PHI node.
411  unsigned PreheaderIdx = ~0U;
412  bool HasUniqueIncomingValue = true;
413  Value *UniqueValue = nullptr;
414  for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
415  BasicBlock *IBB = PN->getIncomingBlock(i);
416  Value *IV = PN->getIncomingValue(i);
417  if (IBB == Preheader) {
418  PreheaderIdx = i;
419  } else {
420  NewPN->addIncoming(IV, IBB);
421  if (HasUniqueIncomingValue) {
422  if (!UniqueValue)
423  UniqueValue = IV;
424  else if (UniqueValue != IV)
425  HasUniqueIncomingValue = false;
426  }
427  }
428  }
429 
430  // Delete all of the incoming values from the old PN except the preheader's
431  assert(PreheaderIdx != ~0U && "PHI has no preheader entry??");
432  if (PreheaderIdx != 0) {
433  PN->setIncomingValue(0, PN->getIncomingValue(PreheaderIdx));
434  PN->setIncomingBlock(0, PN->getIncomingBlock(PreheaderIdx));
435  }
436  // Nuke all entries except the zero'th.
437  for (unsigned i = 0, e = PN->getNumIncomingValues()-1; i != e; ++i)
438  PN->removeIncomingValue(e-i, false);
439 
440  // Finally, add the newly constructed PHI node as the entry for the BEBlock.
441  PN->addIncoming(NewPN, BEBlock);
442 
443  // As an optimization, if all incoming values in the new PhiNode (which is a
444  // subset of the incoming values of the old PHI node) have the same value,
445  // eliminate the PHI Node.
446  if (HasUniqueIncomingValue) {
447  NewPN->replaceAllUsesWith(UniqueValue);
448  BEBlock->getInstList().erase(NewPN);
449  }
450  }
451 
452  // Now that all of the PHI nodes have been inserted and adjusted, modify the
453  // backedge blocks to jump to the BEBlock instead of the header.
454  // If one of the backedges has llvm.loop metadata attached, we remove
455  // it from the backedge and add it to BEBlock.
456  unsigned LoopMDKind = BEBlock->getContext().getMDKindID("llvm.loop");
457  MDNode *LoopMD = nullptr;
458  for (unsigned i = 0, e = BackedgeBlocks.size(); i != e; ++i) {
459  Instruction *TI = BackedgeBlocks[i]->getTerminator();
460  if (!LoopMD)
461  LoopMD = TI->getMetadata(LoopMDKind);
462  TI->setMetadata(LoopMDKind, nullptr);
463  TI->replaceSuccessorWith(Header, BEBlock);
464  }
465  BEBlock->getTerminator()->setMetadata(LoopMDKind, LoopMD);
466 
467  //===--- Update all analyses which we must preserve now -----------------===//
468 
469  // Update Loop Information - we know that this block is now in the current
470  // loop and all parent loops.
471  L->addBasicBlockToLoop(BEBlock, *LI);
472 
473  // Update dominator information
474  DT->splitBlock(BEBlock);
475 
476  if (MSSAU)
477  MSSAU->updatePhisWhenInsertingUniqueBackedgeBlock(Header, Preheader,
478  BEBlock);
479 
480  return BEBlock;
481 }
482 
483 /// Simplify one loop and queue further loops for simplification.
484 static bool simplifyOneLoop(Loop *L, SmallVectorImpl<Loop *> &Worklist,
485  DominatorTree *DT, LoopInfo *LI,
487  MemorySSAUpdater *MSSAU, bool PreserveLCSSA) {
488  bool Changed = false;
489  if (MSSAU && VerifyMemorySSA)
490  MSSAU->getMemorySSA()->verifyMemorySSA();
491 
492 ReprocessLoop:
493 
494  // Check to see that no blocks (other than the header) in this loop have
495  // predecessors that are not in the loop. This is not valid for natural
496  // loops, but can occur if the blocks are unreachable. Since they are
497  // unreachable we can just shamelessly delete those CFG edges!
498  for (BasicBlock *BB : L->blocks()) {
499  if (BB == L->getHeader())
500  continue;
501 
503  for (BasicBlock *P : predecessors(BB))
504  if (!L->contains(P))
505  BadPreds.insert(P);
506 
507  // Delete each unique out-of-loop (and thus dead) predecessor.
508  for (BasicBlock *P : BadPreds) {
509 
510  LLVM_DEBUG(dbgs() << "LoopSimplify: Deleting edge from dead predecessor "
511  << P->getName() << "\n");
512 
513  // Zap the dead pred's terminator and replace it with unreachable.
514  Instruction *TI = P->getTerminator();
515  changeToUnreachable(TI, PreserveLCSSA,
516  /*DTU=*/nullptr, MSSAU);
517  Changed = true;
518  }
519  }
520 
521  if (MSSAU && VerifyMemorySSA)
522  MSSAU->getMemorySSA()->verifyMemorySSA();
523 
524  // If there are exiting blocks with branches on undef, resolve the undef in
525  // the direction which will exit the loop. This will help simplify loop
526  // trip count computations.
527  SmallVector<BasicBlock*, 8> ExitingBlocks;
528  L->getExitingBlocks(ExitingBlocks);
529  for (BasicBlock *ExitingBlock : ExitingBlocks)
530  if (BranchInst *BI = dyn_cast<BranchInst>(ExitingBlock->getTerminator()))
531  if (BI->isConditional()) {
532  if (UndefValue *Cond = dyn_cast<UndefValue>(BI->getCondition())) {
533 
534  LLVM_DEBUG(dbgs()
535  << "LoopSimplify: Resolving \"br i1 undef\" to exit in "
536  << ExitingBlock->getName() << "\n");
537 
538  BI->setCondition(ConstantInt::get(Cond->getType(),
539  !L->contains(BI->getSuccessor(0))));
540 
541  Changed = true;
542  }
543  }
544 
545  // Does the loop already have a preheader? If so, don't insert one.
546  BasicBlock *Preheader = L->getLoopPreheader();
547  if (!Preheader) {
548  Preheader = InsertPreheaderForLoop(L, DT, LI, MSSAU, PreserveLCSSA);
549  if (Preheader)
550  Changed = true;
551  }
552 
553  // Next, check to make sure that all exit nodes of the loop only have
554  // predecessors that are inside of the loop. This check guarantees that the
555  // loop preheader/header will dominate the exit blocks. If the exit block has
556  // predecessors from outside of the loop, split the edge now.
557  if (formDedicatedExitBlocks(L, DT, LI, MSSAU, PreserveLCSSA))
558  Changed = true;
559 
560  if (MSSAU && VerifyMemorySSA)
561  MSSAU->getMemorySSA()->verifyMemorySSA();
562 
563  // If the header has more than two predecessors at this point (from the
564  // preheader and from multiple backedges), we must adjust the loop.
565  BasicBlock *LoopLatch = L->getLoopLatch();
566  if (!LoopLatch) {
567  // If this is really a nested loop, rip it out into a child loop. Don't do
568  // this for loops with a giant number of backedges, just factor them into a
569  // common backedge instead.
570  if (L->getNumBackEdges() < 8) {
571  if (Loop *OuterL = separateNestedLoop(L, Preheader, DT, LI, SE,
572  PreserveLCSSA, AC, MSSAU)) {
573  ++NumNested;
574  // Enqueue the outer loop as it should be processed next in our
575  // depth-first nest walk.
576  Worklist.push_back(OuterL);
577 
578  // This is a big restructuring change, reprocess the whole loop.
579  Changed = true;
580  // GCC doesn't tail recursion eliminate this.
581  // FIXME: It isn't clear we can't rely on LLVM to TRE this.
582  goto ReprocessLoop;
583  }
584  }
585 
586  // If we either couldn't, or didn't want to, identify nesting of the loops,
587  // insert a new block that all backedges target, then make it jump to the
588  // loop header.
589  LoopLatch = insertUniqueBackedgeBlock(L, Preheader, DT, LI, MSSAU);
590  if (LoopLatch)
591  Changed = true;
592  }
593 
594  if (MSSAU && VerifyMemorySSA)
595  MSSAU->getMemorySSA()->verifyMemorySSA();
596 
597  const DataLayout &DL = L->getHeader()->getModule()->getDataLayout();
598 
599  // Scan over the PHI nodes in the loop header. Since they now have only two
600  // incoming values (the loop is canonicalized), we may have simplified the PHI
601  // down to 'X = phi [X, Y]', which should be replaced with 'Y'.
602  PHINode *PN;
603  for (BasicBlock::iterator I = L->getHeader()->begin();
604  (PN = dyn_cast<PHINode>(I++)); )
605  if (Value *V = SimplifyInstruction(PN, {DL, nullptr, DT, AC})) {
606  if (SE) SE->forgetValue(PN);
607  if (!PreserveLCSSA || LI->replacementPreservesLCSSAForm(PN, V)) {
608  PN->replaceAllUsesWith(V);
609  PN->eraseFromParent();
610  Changed = true;
611  }
612  }
613 
614  // If this loop has multiple exits and the exits all go to the same
615  // block, attempt to merge the exits. This helps several passes, such
616  // as LoopRotation, which do not support loops with multiple exits.
617  // SimplifyCFG also does this (and this code uses the same utility
618  // function), however this code is loop-aware, where SimplifyCFG is
619  // not. That gives it the advantage of being able to hoist
620  // loop-invariant instructions out of the way to open up more
621  // opportunities, and the disadvantage of having the responsibility
622  // to preserve dominator information.
623  auto HasUniqueExitBlock = [&]() {
624  BasicBlock *UniqueExit = nullptr;
625  for (auto *ExitingBB : ExitingBlocks)
626  for (auto *SuccBB : successors(ExitingBB)) {
627  if (L->contains(SuccBB))
628  continue;
629 
630  if (!UniqueExit)
631  UniqueExit = SuccBB;
632  else if (UniqueExit != SuccBB)
633  return false;
634  }
635 
636  return true;
637  };
638  if (HasUniqueExitBlock()) {
639  for (unsigned i = 0, e = ExitingBlocks.size(); i != e; ++i) {
640  BasicBlock *ExitingBlock = ExitingBlocks[i];
641  if (!ExitingBlock->getSinglePredecessor()) continue;
642  BranchInst *BI = dyn_cast<BranchInst>(ExitingBlock->getTerminator());
643  if (!BI || !BI->isConditional()) continue;
644  CmpInst *CI = dyn_cast<CmpInst>(BI->getCondition());
645  if (!CI || CI->getParent() != ExitingBlock) continue;
646 
647  // Attempt to hoist out all instructions except for the
648  // comparison and the branch.
649  bool AllInvariant = true;
650  bool AnyInvariant = false;
651  for (auto I = ExitingBlock->instructionsWithoutDebug().begin(); &*I != BI; ) {
652  Instruction *Inst = &*I++;
653  if (Inst == CI)
654  continue;
655  if (!L->makeLoopInvariant(
656  Inst, AnyInvariant,
657  Preheader ? Preheader->getTerminator() : nullptr, MSSAU)) {
658  AllInvariant = false;
659  break;
660  }
661  }
662  if (AnyInvariant) {
663  Changed = true;
664  // The loop disposition of all SCEV expressions that depend on any
665  // hoisted values have also changed.
666  if (SE)
667  SE->forgetLoopDispositions(L);
668  }
669  if (!AllInvariant) continue;
670 
671  // The block has now been cleared of all instructions except for
672  // a comparison and a conditional branch. SimplifyCFG may be able
673  // to fold it now.
674  if (!FoldBranchToCommonDest(BI, /*DTU=*/nullptr, MSSAU))
675  continue;
676 
677  // Success. The block is now dead, so remove it from the loop,
678  // update the dominator tree and delete it.
679  LLVM_DEBUG(dbgs() << "LoopSimplify: Eliminating exiting block "
680  << ExitingBlock->getName() << "\n");
681 
682  assert(pred_empty(ExitingBlock));
683  Changed = true;
684  LI->removeBlock(ExitingBlock);
685 
686  DomTreeNode *Node = DT->getNode(ExitingBlock);
687  while (!Node->isLeaf()) {
688  DomTreeNode *Child = Node->back();
689  DT->changeImmediateDominator(Child, Node->getIDom());
690  }
691  DT->eraseNode(ExitingBlock);
692  if (MSSAU) {
693  SmallSetVector<BasicBlock *, 8> ExitBlockSet;
694  ExitBlockSet.insert(ExitingBlock);
695  MSSAU->removeBlocks(ExitBlockSet);
696  }
697 
699  ExitingBlock, /* KeepOneInputPHIs */ PreserveLCSSA);
701  ExitingBlock, /* KeepOneInputPHIs */ PreserveLCSSA);
702  ExitingBlock->eraseFromParent();
703  }
704  }
705 
706  // Changing exit conditions for blocks may affect exit counts of this loop and
707  // any of its paretns, so we must invalidate the entire subtree if we've made
708  // any changes.
709  if (Changed && SE)
710  SE->forgetTopmostLoop(L);
711 
712  if (MSSAU && VerifyMemorySSA)
713  MSSAU->getMemorySSA()->verifyMemorySSA();
714 
715  return Changed;
716 }
717 
720  MemorySSAUpdater *MSSAU, bool PreserveLCSSA) {
721  bool Changed = false;
722 
723 #ifndef NDEBUG
724  // If we're asked to preserve LCSSA, the loop nest needs to start in LCSSA
725  // form.
726  if (PreserveLCSSA) {
727  assert(DT && "DT not available.");
728  assert(LI && "LI not available.");
729  assert(L->isRecursivelyLCSSAForm(*DT, *LI) &&
730  "Requested to preserve LCSSA, but it's already broken.");
731  }
732 #endif
733 
734  // Worklist maintains our depth-first queue of loops in this nest to process.
735  SmallVector<Loop *, 4> Worklist;
736  Worklist.push_back(L);
737 
738  // Walk the worklist from front to back, pushing newly found sub loops onto
739  // the back. This will let us process loops from back to front in depth-first
740  // order. We can use this simple process because loops form a tree.
741  for (unsigned Idx = 0; Idx != Worklist.size(); ++Idx) {
742  Loop *L2 = Worklist[Idx];
743  Worklist.append(L2->begin(), L2->end());
744  }
745 
746  while (!Worklist.empty())
747  Changed |= simplifyOneLoop(Worklist.pop_back_val(), Worklist, DT, LI, SE,
748  AC, MSSAU, PreserveLCSSA);
749 
750  return Changed;
751 }
752 
753 namespace {
754  struct LoopSimplify : public FunctionPass {
755  static char ID; // Pass identification, replacement for typeid
756  LoopSimplify() : FunctionPass(ID) {
758  }
759 
760  bool runOnFunction(Function &F) override;
761 
762  void getAnalysisUsage(AnalysisUsage &AU) const override {
764 
765  // We need loop information to identify the loops...
768 
771 
779  AU.addPreservedID(BreakCriticalEdgesID); // No critical edges added.
782  }
783 
784  /// verifyAnalysis() - Verify LoopSimplifyForm's guarantees.
785  void verifyAnalysis() const override;
786  };
787 }
788 
789 char LoopSimplify::ID = 0;
790 INITIALIZE_PASS_BEGIN(LoopSimplify, "loop-simplify",
791  "Canonicalize natural loops", false, false)
796  "Canonicalize natural loops", false, false)
797 
798 // Publicly exposed interface to pass...
799 char &llvm::LoopSimplifyID = LoopSimplify::ID;
800 Pass *llvm::createLoopSimplifyPass() { return new LoopSimplify(); }
801 
802 /// runOnFunction - Run down all loops in the CFG (recursively, but we could do
803 /// it in any convenient order) inserting preheaders...
804 ///
806  bool Changed = false;
807  LoopInfo *LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
808  DominatorTree *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
809  auto *SEWP = getAnalysisIfAvailable<ScalarEvolutionWrapperPass>();
810  ScalarEvolution *SE = SEWP ? &SEWP->getSE() : nullptr;
811  AssumptionCache *AC =
812  &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
813  MemorySSA *MSSA = nullptr;
814  std::unique_ptr<MemorySSAUpdater> MSSAU;
815  auto *MSSAAnalysis = getAnalysisIfAvailable<MemorySSAWrapperPass>();
816  if (MSSAAnalysis) {
817  MSSA = &MSSAAnalysis->getMSSA();
818  MSSAU = std::make_unique<MemorySSAUpdater>(MSSA);
819  }
820 
821  bool PreserveLCSSA = mustPreserveAnalysisID(LCSSAID);
822 
823  // Simplify each loop nest in the function.
824  for (auto *L : *LI)
825  Changed |= simplifyLoop(L, DT, LI, SE, AC, MSSAU.get(), PreserveLCSSA);
826 
827 #ifndef NDEBUG
828  if (PreserveLCSSA) {
829  bool InLCSSA = all_of(
830  *LI, [&](Loop *L) { return L->isRecursivelyLCSSAForm(*DT, *LI); });
831  assert(InLCSSA && "LCSSA is broken after loop-simplify.");
832  }
833 #endif
834  return Changed;
835 }
836 
839  bool Changed = false;
840  LoopInfo *LI = &AM.getResult<LoopAnalysis>(F);
844  auto *MSSAAnalysis = AM.getCachedResult<MemorySSAAnalysis>(F);
845  std::unique_ptr<MemorySSAUpdater> MSSAU;
846  if (MSSAAnalysis) {
847  auto *MSSA = &MSSAAnalysis->getMSSA();
848  MSSAU = std::make_unique<MemorySSAUpdater>(MSSA);
849  }
850 
851 
852  // Note that we don't preserve LCSSA in the new PM, if you need it run LCSSA
853  // after simplifying the loops. MemorySSA is preserved if it exists.
854  for (auto *L : *LI)
855  Changed |=
856  simplifyLoop(L, DT, LI, SE, AC, MSSAU.get(), /*PreserveLCSSA*/ false);
857 
858  if (!Changed)
859  return PreservedAnalyses::all();
860 
863  PA.preserve<LoopAnalysis>();
866  if (MSSAAnalysis)
868  // BPI maps conditional terminators to probabilities, LoopSimplify can insert
869  // blocks, but it does so only by splitting existing blocks and edges. This
870  // results in the interesting property that all new terminators inserted are
871  // unconditional branches which do not appear in BPI. All deletions are
872  // handled via ValueHandle callbacks w/in BPI.
874  return PA;
875 }
876 
877 // FIXME: Restore this code when we re-enable verification in verifyAnalysis
878 // below.
879 #if 0
880 static void verifyLoop(Loop *L) {
881  // Verify subloops.
882  for (Loop::iterator I = L->begin(), E = L->end(); I != E; ++I)
883  verifyLoop(*I);
884 
885  // It used to be possible to just assert L->isLoopSimplifyForm(), however
886  // with the introduction of indirectbr, there are now cases where it's
887  // not possible to transform a loop as necessary. We can at least check
888  // that there is an indirectbr near any time there's trouble.
889 
890  // Indirectbr can interfere with preheader and unique backedge insertion.
891  if (!L->getLoopPreheader() || !L->getLoopLatch()) {
892  bool HasIndBrPred = false;
893  for (BasicBlock *Pred : predecessors(L->getHeader()))
894  if (isa<IndirectBrInst>(Pred->getTerminator())) {
895  HasIndBrPred = true;
896  break;
897  }
898  assert(HasIndBrPred &&
899  "LoopSimplify has no excuse for missing loop header info!");
900  (void)HasIndBrPred;
901  }
902 
903  // Indirectbr can interfere with exit block canonicalization.
904  if (!L->hasDedicatedExits()) {
905  bool HasIndBrExiting = false;
906  SmallVector<BasicBlock*, 8> ExitingBlocks;
907  L->getExitingBlocks(ExitingBlocks);
908  for (unsigned i = 0, e = ExitingBlocks.size(); i != e; ++i) {
909  if (isa<IndirectBrInst>((ExitingBlocks[i])->getTerminator())) {
910  HasIndBrExiting = true;
911  break;
912  }
913  }
914 
915  assert(HasIndBrExiting &&
916  "LoopSimplify has no excuse for missing exit block info!");
917  (void)HasIndBrExiting;
918  }
919 }
920 #endif
921 
922 void LoopSimplify::verifyAnalysis() const {
923  // FIXME: This routine is being called mid-way through the loop pass manager
924  // as loop passes destroy this analysis. That's actually fine, but we have no
925  // way of expressing that here. Once all of the passes that destroy this are
926  // hoisted out of the loop pass manager we can add back verification here.
927 #if 0
928  for (LoopInfo::iterator I = LI->begin(), E = LI->end(); I != E; ++I)
929  verifyLoop(*I);
930 #endif
931 }
i
i
Definition: README.txt:29
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:155
llvm::formLCSSA
bool formLCSSA(Loop &L, const DominatorTree &DT, const LoopInfo *LI, ScalarEvolution *SE)
Put loop into LCSSA form.
Definition: LCSSA.cpp:336
AssumptionCache.h
llvm::ScalarEvolutionAnalysis
Analysis pass that exposes the ScalarEvolution for a function.
Definition: ScalarEvolution.h:2109
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AllocatorList.h:23
LoopSimplify.h
llvm::Instruction::replaceSuccessorWith
void replaceSuccessorWith(BasicBlock *OldBB, BasicBlock *NewBB)
Replace specified successor OldBB to point at the provided block.
Definition: Instruction.cpp:811
llvm::MemorySSA::verifyMemorySSA
void verifyMemorySSA(VerificationLevel=VerificationLevel::Fast) const
Verify that MemorySSA is self consistent (IE definitions dominate all uses, uses appear in the right ...
Definition: MemorySSA.cpp:1901
llvm::DataLayout
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:113
llvm::DominatorTreeBase::eraseNode
void eraseNode(NodeT *BB)
eraseNode - Removes a node from the dominator tree.
Definition: GenericDomTree.h:669
llvm::Function::end
iterator end()
Definition: Function.h:725
llvm::BasicBlock::iterator
InstListType::iterator iterator
Instruction iterators...
Definition: BasicBlock.h:90
llvm::BasicBlock::getParent
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:107
IntrinsicInst.h
llvm::AnalysisManager::getResult
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:783
SetOperations.h
llvm::ScalarEvolution::forgetLoopDispositions
void forgetLoopDispositions(const Loop *L)
Called when the client has changed the disposition of values in this loop.
Definition: ScalarEvolution.cpp:7940
llvm::DependenceAnalysisWrapperPass
Legacy pass manager pass to access dependence information.
Definition: DependenceAnalysis.h:979
MemorySSAUpdater.h
llvm::Function
Definition: Function.h:62
llvm::Loop
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:530
P
This currently compiles esp xmm0 movsd esp eax eax esp ret We should use not the dag combiner This is because dagcombine2 needs to be able to see through the X86ISD::Wrapper which DAGCombine can t really do The code for turning x load into a single vector load is target independent and should be moved to the dag combiner The code for turning x load into a vector load can only handle a direct load from a global or a direct load from the stack It should be generalized to handle any load from P
Definition: README-SSE.txt:411
INITIALIZE_PASS_BEGIN
INITIALIZE_PASS_BEGIN(LoopSimplify, "loop-simplify", "Canonicalize natural loops", false, false) INITIALIZE_PASS_END(LoopSimplify
llvm::LoopBase::contains
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
Definition: LoopInfo.h:122
llvm::BasicBlock::instructionsWithoutDebug
iterator_range< filter_iterator< BasicBlock::const_iterator, std::function< bool(const Instruction &)> > > instructionsWithoutDebug(bool SkipPseudoOp=true) const
Return a const iterator range over the instructions in the block, skipping any debug instructions.
Definition: BasicBlock.cpp:104
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1175
Statistic.h
llvm::ScalarEvolution
The main scalar evolution driver.
Definition: ScalarEvolution.h:460
llvm::PHINode::removeIncomingValue
Value * removeIncomingValue(unsigned Idx, bool DeletePHIIfEmpty=true)
Remove an incoming value.
Definition: Instructions.cpp:113
llvm::LoopInfoBase::changeLoopFor
void changeLoopFor(BlockT *BB, LoopT *L)
Change the top-level loop that contains BB to the specified loop.
Definition: LoopInfo.h:1008
Local.h
llvm::MemorySSAUpdater::removeBlocks
void removeBlocks(const SmallSetVector< BasicBlock *, 8 > &DeadBlocks)
Remove all MemoryAcceses in a set of BasicBlocks about to be deleted.
Definition: MemorySSAUpdater.cpp:1371
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:151
GlobalsModRef.h
simplifyOneLoop
static bool simplifyOneLoop(Loop *L, SmallVectorImpl< Loop * > &Worklist, DominatorTree *DT, LoopInfo *LI, ScalarEvolution *SE, AssumptionCache *AC, MemorySSAUpdater *MSSAU, bool PreserveLCSSA)
Simplify one loop and queue further loops for simplification.
Definition: LoopSimplify.cpp:484
ScalarEvolution.h
llvm::LoopInfoBase::removeBlock
void removeBlock(BlockT *BB)
This method completely removes BB from all data structures, including all of the Loop objects it is n...
Definition: LoopInfo.h:1035
Module.h
llvm::BasicBlock::eraseFromParent
SymbolTableList< BasicBlock >::iterator eraseFromParent()
Unlink 'this' from the containing function and delete it.
Definition: BasicBlock.cpp:133
llvm::LoopInfoWrapperPass
The legacy pass manager's analysis pass to compute loop information.
Definition: LoopInfo.h:1271
llvm::DominatorTreeBase::getNode
DomTreeNodeBase< NodeT > * getNode(const NodeT *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
Definition: GenericDomTree.h:351
loops
loop Canonicalize natural loops
Definition: LoopSimplify.cpp:796
llvm::LoopBase::begin
iterator begin() const
Definition: LoopInfo.h:154
llvm::SmallPtrSet
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:449
llvm::successors
auto successors(MachineBasicBlock *BB)
Definition: MachineSSAContext.h:31
llvm::BasicBlock::getSinglePredecessor
const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
Definition: BasicBlock.cpp:268
llvm::SmallVectorImpl::pop_back_val
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:642
BasicAliasAnalysis.h
llvm::PHINode::setIncomingValue
void setIncomingValue(unsigned i, Value *V)
Definition: Instructions.h:2756
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
DepthFirstIterator.h
F
#define F(x, y, z)
Definition: MD5.cpp:55
llvm::Instruction::setMetadata
void setMetadata(unsigned KindID, MDNode *Node)
Set the metadata of the specified kind to the specified node.
Definition: Metadata.cpp:1336
loop
Analysis the ScalarEvolution expression for r is< loop > Outside the loop
Definition: README.txt:8
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
AliasAnalysis.h
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
llvm::DominatorTree::dominates
bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
Definition: Dominators.cpp:115
llvm::MemorySSAUpdater::updatePhisWhenInsertingUniqueBackedgeBlock
void updatePhisWhenInsertingUniqueBackedgeBlock(BasicBlock *LoopHeader, BasicBlock *LoopPreheader, BasicBlock *BackedgeBlock)
Update MemorySSA when inserting a unique backedge block for a loop.
Definition: MemorySSAUpdater.cpp:636
llvm::LoopBase::getParentLoop
LoopT * getParentLoop() const
Return the parent loop if it exists or nullptr for top level loops.
Definition: LoopInfo.h:113
llvm::LoopBase::getSubLoops
const std::vector< LoopT * > & getSubLoops() const
Return the loops contained entirely within this loop.
Definition: LoopInfo.h:143
llvm::BranchProbabilityAnalysis
Analysis pass which computes BranchProbabilityInfo.
Definition: BranchProbabilityInfo.h:414
llvm::all_of
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1649
llvm::MemorySSAWrapperPass
Legacy analysis pass which computes MemorySSA.
Definition: MemorySSA.h:980
llvm::PassRegistry::getPassRegistry
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Definition: PassRegistry.cpp:31
L2
add sub stmia L5 ldr L2
Definition: README.txt:201
Constants.h
llvm::PHINode::getIncomingValue
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
Definition: Instructions.h:2753
llvm::BranchProbabilityInfoWrapperPass
Legacy analysis pass which computes BranchProbabilityInfo.
Definition: BranchProbabilityInfo.h:440
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
llvm::SmallVectorImpl::append
void append(in_iter in_start, in_iter in_end)
Add the specified range to the end of the SmallVector.
Definition: SmallVector.h:655
llvm::LoopBase::addChildLoop
void addChildLoop(LoopT *NewChild)
Add the specified loop to be a child of this loop.
Definition: LoopInfo.h:395
llvm::BasicBlock::begin
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:296
llvm::FoldBranchToCommonDest
bool FoldBranchToCommonDest(BranchInst *BI, llvm::DomTreeUpdater *DTU=nullptr, MemorySSAUpdater *MSSAU=nullptr, const TargetTransformInfo *TTI=nullptr, unsigned BonusInstThreshold=1)
If this basic block is ONLY a setcc and a branch, and if a predecessor branches to us and one of our ...
Definition: SimplifyCFG.cpp:3173
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
llvm::LoopBase::end
iterator end() const
Definition: LoopInfo.h:155
llvm::LoopBase::blocks
iterator_range< block_iterator > blocks() const
Definition: LoopInfo.h:178
llvm::LoopInfo::replacementPreservesLCSSAForm
bool replacementPreservesLCSSAForm(Instruction *From, Value *To)
Returns true if replacing From with To everywhere is guaranteed to preserve LCSSA form.
Definition: LoopInfo.h:1118
false
Definition: StackSlotColoring.cpp:142
llvm::LoopBase::getBlocks
ArrayRef< BlockT * > getBlocks() const
Get a list of the basic blocks which make up this loop.
Definition: LoopInfo.h:171
llvm::Instruction
Definition: Instruction.h:45
llvm::SimplifyInstruction
Value * SimplifyInstruction(Instruction *I, const SimplifyQuery &Q, OptimizationRemarkEmitter *ORE=nullptr)
See if we can compute a simplified version of this instruction.
Definition: InstructionSimplify.cpp:6363
llvm::DominatorTreeWrapperPass
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:287
llvm::STATISTIC
STATISTIC(NumFunctions, "Total number of functions")
llvm::predecessors
auto predecessors(MachineBasicBlock *BB)
Definition: MachineSSAContext.h:32
llvm::LoopBase::getExitingBlocks
void getExitingBlocks(SmallVectorImpl< BlockT * > &ExitingBlocks) const
Return all blocks inside the loop that have successors outside of the loop.
Definition: LoopInfoImpl.h:34
llvm::ConstantInt::get
static Constant * get(Type *Ty, uint64_t V, bool IsSigned=false)
If Ty is a vector type, return a Constant with a splat of the given value.
Definition: Constants.cpp:932
LoopUtils.h
llvm::ScalarEvolutionWrapperPass
Definition: ScalarEvolution.h:2139
llvm::SplitBlockPredecessors
BasicBlock * SplitBlockPredecessors(BasicBlock *BB, ArrayRef< BasicBlock * > Preds, const char *Suffix, DominatorTree *DT, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, bool PreserveLCSSA=false)
This method introduces at least one new basic block into the function and moves some of the predecess...
Definition: BasicBlockUtils.cpp:1174
llvm::BasicBlock::getModule
const Module * getModule() const
Return the module owning the function this basic block belongs to, or nullptr if the function does no...
Definition: BasicBlock.cpp:148
llvm::DominatorTreeBase::changeImmediateDominator
void changeImmediateDominator(DomTreeNodeBase< NodeT > *N, DomTreeNodeBase< NodeT > *NewIDom)
changeImmediateDominator - This method is used to update the dominator tree information when a node's...
Definition: GenericDomTree.h:655
llvm::BasicBlock::getFirstNonPHI
const Instruction * getFirstNonPHI() const
Returns a pointer to the first instruction in this block that is not a PHINode instruction.
Definition: BasicBlock.cpp:216
llvm::LoopBase::removeBlockFromLoop
void removeBlockFromLoop(BlockT *BB)
This removes the specified basic block from the current loop, updating the Blocks as appropriate.
Definition: LoopInfo.h:460
Utils.h
llvm::PHINode::getNumIncomingValues
unsigned getNumIncomingValues() const
Return the number of incoming edges.
Definition: Instructions.h:2749
Type.h
llvm::Instruction::getMetadata
MDNode * getMetadata(unsigned KindID) const
Get the metadata of given kind attached to this Instruction.
Definition: Instruction.h:282
INITIALIZE_PASS_END
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:58
CFG.h
LoopInfo.h
llvm::LoopInfoBase::AllocateLoop
LoopT * AllocateLoop(ArgsTy &&... Args)
Definition: LoopInfo.h:934
llvm::BranchInst::getCondition
Value * getCondition() const
Definition: Instructions.h:3173
placeSplitBlockCarefully
static void placeSplitBlockCarefully(BasicBlock *NewBB, SmallVectorImpl< BasicBlock * > &SplitPreds, Loop *L)
Definition: LoopSimplify.cpp:86
llvm::CmpInst
This class is the base class for the comparison instructions.
Definition: InstrTypes.h:711
insertUniqueBackedgeBlock
static BasicBlock * insertUniqueBackedgeBlock(Loop *L, BasicBlock *Preheader, DominatorTree *DT, LoopInfo *LI, MemorySSAUpdater *MSSAU)
This method is called when the specified loop has more than one backedge in it.
Definition: LoopSimplify.cpp:363
llvm::InsertPreheaderForLoop
BasicBlock * InsertPreheaderForLoop(Loop *L, DominatorTree *DT, LoopInfo *LI, MemorySSAUpdater *MSSAU, bool PreserveLCSSA)
InsertPreheaderForLoop - Once we discover that a loop doesn't have a preheader, this method is called...
Definition: LoopSimplify.cpp:123
llvm::Instruction::eraseFromParent
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
Definition: Instruction.cpp:78
BranchProbabilityInfo.h
llvm::SCEVAAWrapperPass
Legacy wrapper pass to provide the SCEVAAResult object.
Definition: ScalarEvolutionAliasAnalysis.h:55
simplify
loop simplify
Definition: LoopSimplify.cpp:795
llvm::LoopBase::moveToHeader
void moveToHeader(BlockT *BB)
This method is used to move BB (which must be part of this loop) to be the loop header of the loop (t...
Definition: LoopInfo.h:443
llvm::MemorySSAUpdater
Definition: MemorySSAUpdater.h:55
llvm::MemorySSAUpdater::getMemorySSA
MemorySSA * getMemorySSA() const
Get handle on MemorySSA.
Definition: MemorySSAUpdater.h:243
llvm::AssumptionAnalysis
A function analysis which provides an AssumptionCache.
Definition: AssumptionCache.h:173
llvm::PHINode::setIncomingBlock
void setIncomingBlock(unsigned i, BasicBlock *BB)
Definition: Instructions.h:2792
llvm::PreservedAnalyses::preserve
void preserve()
Mark an analysis as preserved.
Definition: PassManager.h:176
INITIALIZE_PASS_DEPENDENCY
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
llvm::BasicAAWrapperPass
Legacy wrapper pass to provide the BasicAAResult object.
Definition: BasicAliasAnalysis.h:175
llvm::PHINode::addIncoming
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
Definition: Instructions.h:2807
llvm::numbers::e
constexpr double e
Definition: MathExtras.h:57
llvm::BranchInst::Create
static BranchInst * Create(BasicBlock *IfTrue, Instruction *InsertBefore=nullptr)
Definition: Instructions.h:3148
llvm::MemorySSA
Encapsulates MemorySSA, including all data associated with memory accesses.
Definition: MemorySSA.h:704
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::UndefValue
'undef' values are things that do not have specified contents.
Definition: Constants.h:1377
llvm::LoopBase::getLoopPreheader
BlockT * getLoopPreheader() const
If there is a preheader for this loop, return it.
Definition: LoopInfoImpl.h:167
llvm::Instruction::setDebugLoc
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
Definition: Instruction.h:367
llvm::ScalarEvolution::forgetValue
void forgetValue(Value *V)
This method should be called by the client when it has changed a value in a way that may effect its v...
Definition: ScalarEvolution.cpp:7913
llvm::LoopBase::getLoopLatch
BlockT * getLoopLatch() const
If there is a single latch block for this loop, return it.
Definition: LoopInfoImpl.h:216
llvm::LoopBase::hasDedicatedExits
bool hasDedicatedExits() const
Return true if no exit block for the loop has a predecessor that is outside the loop.
Definition: LoopInfoImpl.h:92
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::createLoopSimplifyPass
Pass * createLoopSimplifyPass()
Definition: LoopSimplify.cpp:800
llvm::ScalarEvolution::forgetTopmostLoop
void forgetTopmostLoop(const Loop *L)
Definition: ScalarEvolution.cpp:7907
llvm::MDNode
Metadata node.
Definition: Metadata.h:906
llvm::MemorySSAAnalysis
An analysis that produces MemorySSA for a function.
Definition: MemorySSA.h:930
llvm::SmallPtrSetImpl::count
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:382
llvm::SetVector< T, SmallVector< T, N >, SmallDenseSet< T, N > >::insert
bool insert(const value_type &X)
Insert a new element into the SetVector.
Definition: SetVector.h:141
llvm::size
auto size(R &&Range, std::enable_if_t< std::is_base_of< std::random_access_iterator_tag, typename std::iterator_traits< decltype(Range.begin())>::iterator_category >::value, void > *=nullptr)
Get the size of a range.
Definition: STLExtras.h:1630
llvm::LoopBase::removeChildLoop
LoopT * removeChildLoop(iterator I)
This removes the specified child from being a subloop of this loop.
Definition: LoopInfo.h:404
llvm::AssumptionCacheTracker
An immutable pass that tracks lazily created AssumptionCache objects.
Definition: AssumptionCache.h:202
llvm::LoopInfo
Definition: LoopInfo.h:1086
llvm::BasicBlock::moveAfter
void moveAfter(BasicBlock *MovePos)
Unlink this basic block from its current function and insert it right after MovePos in the function M...
Definition: BasicBlock.cpp:142
DataLayout.h
Cond
SmallVector< MachineOperand, 4 > Cond
Definition: BasicBlockSections.cpp:179
llvm::Loop::makeLoopInvariant
bool makeLoopInvariant(Value *V, bool &Changed, Instruction *InsertPt=nullptr, MemorySSAUpdater *MSSAU=nullptr) const
If the given value is an instruction inside of the loop and it can be hoisted, do so to make it trivi...
Definition: LoopInfo.cpp:74
llvm::AssumptionCache
A cache of @llvm.assume calls within a function.
Definition: AssumptionCache.h:42
llvm::AnalysisUsage::addPreservedID
AnalysisUsage & addPreservedID(const void *ID)
Definition: PassAnalysisSupport.h:88
llvm::Value::getType
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:255
llvm::AnalysisUsage::addPreserved
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
Definition: PassAnalysisSupport.h:98
llvm::Value::replaceAllUsesWith
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:532
llvm::BasicBlock::Create
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
Definition: BasicBlock.h:100
llvm::append_range
void append_range(Container &C, Range &&R)
Wrapper function to append a range to a container.
Definition: STLExtras.h:1846
llvm::ilist_node_impl::getIterator
self_iterator getIterator()
Definition: ilist_node.h:81
DL
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Definition: AArch64SLSHardening.cpp:76
llvm::DependenceAnalysis
AnalysisPass to compute dependence information in a function.
Definition: DependenceAnalysis.h:957
llvm::LoopBase::replaceChildLoopWith
void replaceChildLoopWith(LoopT *OldChild, LoopT *NewChild)
This is used when splitting loops up.
Definition: LoopInfoImpl.h:272
llvm::pred_empty
bool pred_empty(const BasicBlock *BB)
Definition: CFG.h:119
separateNestedLoop
static Loop * separateNestedLoop(Loop *L, BasicBlock *Preheader, DominatorTree *DT, LoopInfo *LI, ScalarEvolution *SE, bool PreserveLCSSA, AssumptionCache *AC, MemorySSAUpdater *MSSAU)
If this loop has multiple backedges, try to pull one of them out into a nested loop.
Definition: LoopSimplify.cpp:220
llvm::DomTreeNodeBase< BasicBlock >
llvm::Value::getName
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:309
llvm::BasicBlock::getTerminator
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
Definition: BasicBlock.cpp:152
llvm::BasicBlock::getContext
LLVMContext & getContext() const
Get the context in which this basic block lives.
Definition: BasicBlock.cpp:36
runOnFunction
static bool runOnFunction(Function &F, bool PostInlining)
Definition: EntryExitInstrumenter.cpp:69
llvm::LCSSAID
char & LCSSAID
Definition: LCSSA.cpp:487
llvm::formDedicatedExitBlocks
bool formDedicatedExitBlocks(Loop *L, DominatorTree *DT, LoopInfo *LI, MemorySSAUpdater *MSSAU, bool PreserveLCSSA)
Ensure that all exit blocks of the loop are dedicated exits.
Definition: LoopUtils.cpp:63
llvm::LoopSimplifyID
char & LoopSimplifyID
Definition: LoopSimplify.cpp:799
llvm::ScalarEvolution::forgetLoop
void forgetLoop(const Loop *L)
This method should be called by the client when it has changed a loop in a way that may effect Scalar...
Definition: ScalarEvolution.cpp:7850
llvm::PreservedAnalyses::all
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:161
llvm::PHINode::Create
static PHINode * Create(Type *Ty, unsigned NumReservedValues, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
Constructors - NumReservedValues is a hint for the number of incoming edges that this phi node will h...
Definition: Instructions.h:2699
findPHIToPartitionLoops
static PHINode * findPHIToPartitionLoops(Loop *L, DominatorTree *DT, AssumptionCache *AC)
The first part of loop-nestification is to find a PHI node that tells us how to partition the loops.
Definition: LoopSimplify.cpp:178
llvm::AnalysisManager::getCachedResult
PassT::Result * getCachedResult(IRUnitT &IR) const
Get the cached result of an analysis pass for a given IR unit.
Definition: PassManager.h:802
llvm::DominatorTreeBase::splitBlock
void splitBlock(NodeT *NewBB)
splitBlock - BB is split and now it has one successor.
Definition: GenericDomTree.h:700
Function.h
llvm::LoopBase::getHeader
BlockT * getHeader() const
Definition: LoopInfo.h:104
llvm::Loop::isRecursivelyLCSSAForm
bool isRecursivelyLCSSAForm(const DominatorTree &DT, const LoopInfo &LI) const
Return true if this Loop and all inner subloops are in LCSSA form.
Definition: LoopInfo.cpp:469
llvm::simplifyLoop
bool simplifyLoop(Loop *L, DominatorTree *DT, LoopInfo *LI, ScalarEvolution *SE, AssumptionCache *AC, MemorySSAUpdater *MSSAU, bool PreserveLCSSA)
Simplify each loop in a loop nest recursively.
Definition: LoopSimplify.cpp:718
llvm::LoopBase::addBlockEntry
void addBlockEntry(BlockT *BB)
This adds a basic block directly to the basic block list.
Definition: LoopInfo.h:423
ScalarEvolutionAliasAnalysis.h
llvm::BreakCriticalEdgesID
char & BreakCriticalEdgesID
llvm::LoopBase::getNumBackEdges
unsigned getNumBackEdges() const
Calculate the number of back edges to the loop header.
Definition: LoopInfo.h:250
llvm::DominatorTreeAnalysis
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:252
llvm::changeToUnreachable
unsigned changeToUnreachable(Instruction *I, bool PreserveLCSSA=false, DomTreeUpdater *DTU=nullptr, MemorySSAUpdater *MSSAU=nullptr)
Insert an unreachable instruction before the specified instruction, making it and the rest of the cod...
Definition: Local.cpp:2128
llvm::BasicBlock::getInstList
const InstListType & getInstList() const
Return the underlying instruction list container.
Definition: BasicBlock.h:363
llvm::Pass
Pass interface - Implemented by all 'passes'.
Definition: Pass.h:91
MemorySSA.h
Instructions.h
SmallVector.h
llvm::Instruction::getDebugLoc
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
Definition: Instruction.h:370
llvm::LoopBase::addBasicBlockToLoop
void addBasicBlockToLoop(BlockT *NewBB, LoopInfoBase< BlockT, LoopT > &LI)
This method is used by other analyses to update loop information.
Definition: LoopInfoImpl.h:242
llvm::LoopBase< BasicBlock, Loop >::iterator
std::vector< Loop * >::const_iterator iterator
Definition: LoopInfo.h:151
llvm::LoopInfoBase::changeTopLevelLoop
void changeTopLevelLoop(LoopT *OldLoop, LoopT *NewLoop)
Replace the specified loop in the top-level loops list with the indicated loop.
Definition: LoopInfo.h:1018
Dominators.h
llvm::AAResultsWrapperPass
A wrapper pass to provide the legacy pass manager access to a suitably prepared AAResults object.
Definition: AliasAnalysis.h:1335
llvm::Instruction::getParent
const BasicBlock * getParent() const
Definition: Instruction.h:94
InstructionSimplify.h
llvm::GlobalsAAWrapperPass
Legacy wrapper pass to provide the GlobalsAAResult object.
Definition: GlobalsModRef.h:143
llvm::PHINode::getIncomingBlock
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
Definition: Instructions.h:2773
llvm::PHINode
Definition: Instructions.h:2657
llvm::LoopInfoBase< BasicBlock, Loop >::iterator
std::vector< Loop * >::const_iterator iterator
iterator/begin/end - The interface to the top-level loops in the current function.
Definition: LoopInfo.h:942
llvm::BasicBlock::removePredecessor
void removePredecessor(BasicBlock *Pred, bool KeepOneInputPHIs=false)
Update PHI nodes in this BasicBlock before removal of predecessor Pred.
Definition: BasicBlock.cpp:325
llvm::SmallVectorImpl< BasicBlock * >
llvm::LLVMContext::getMDKindID
unsigned getMDKindID(StringRef Name) const
getMDKindID - Return a unique non-zero ID for the specified metadata kind.
Definition: LLVMContext.cpp:260
llvm::Module::getDataLayout
const DataLayout & getDataLayout() const
Get the data layout for the module's target platform.
Definition: Module.cpp:401
llvm::SmallPtrSetImpl
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:343
llvm::SmallSetVector
A SetVector that performs no allocations if smaller than a certain size.
Definition: SetVector.h:307
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:44
llvm::FunctionPass
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:298
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
llvm::LoopSimplifyPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: LoopSimplify.cpp:837
llvm::AnalysisUsage::addRequired
AnalysisUsage & addRequired()
Definition: PassAnalysisSupport.h:75
llvm::VerifyMemorySSA
bool VerifyMemorySSA
Enables verification of MemorySSA.
Definition: MemorySSA.cpp:91
DependenceAnalysis.h
LLVMContext.h
llvm::BranchInst
Conditional or Unconditional Branch instruction.
Definition: Instructions.h:3092
raw_ostream.h
BasicBlockUtils.h
InitializePasses.h
llvm::BasicBlock::isEHPad
bool isEHPad() const
Return true if this basic block is an exception handling block.
Definition: BasicBlock.h:465
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
Debug.h
llvm::BranchInst::isConditional
bool isConditional() const
Definition: Instructions.h:3171
llvm::Instruction::isIndirectTerminator
bool isIndirectTerminator() const
Definition: Instruction.h:178
llvm::BranchInst::getSuccessor
BasicBlock * getSuccessor(unsigned i) const
Definition: Instructions.h:3185
llvm::LoopAnalysis
Analysis pass that exposes the LoopInfo for a function.
Definition: LoopInfo.h:1246
SetVector.h
addBlockAndPredsToSet
static void addBlockAndPredsToSet(BasicBlock *InputBB, BasicBlock *StopBlock, SmallPtrSetImpl< BasicBlock * > &Blocks)
Add the specified block, and all of its predecessors, to the specified set, if it's not already in th...
Definition: LoopSimplify.cpp:163
llvm::Function::iterator
BasicBlockListType::iterator iterator
Definition: Function.h:68
llvm::SmallPtrSetImpl::insert
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:364
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:38
llvm::initializeLoopSimplifyPass
void initializeLoopSimplifyPass(PassRegistry &)