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