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 (Loop::block_iterator I = L->block_begin(), E = L->block_end();
297  I != E; ++I)
298  NewOuter->addBlockEntry(*I);
299 
300  // Now reset the header in L, which had been moved by
301  // SplitBlockPredecessors for the outer loop.
302  L->moveToHeader(Header);
303 
304  // Determine which blocks should stay in L and which should be moved out to
305  // the Outer loop now.
307  for (BasicBlock *P : predecessors(Header)) {
308  if (DT->dominates(Header, P))
309  addBlockAndPredsToSet(P, Header, BlocksInL);
310  }
311 
312  // Scan all of the loop children of L, moving them to OuterLoop if they are
313  // not part of the inner loop.
314  const std::vector<Loop*> &SubLoops = L->getSubLoops();
315  for (size_t I = 0; I != SubLoops.size(); )
316  if (BlocksInL.count(SubLoops[I]->getHeader()))
317  ++I; // Loop remains in L
318  else
319  NewOuter->addChildLoop(L->removeChildLoop(SubLoops.begin() + I));
320 
321  SmallVector<BasicBlock *, 8> OuterLoopBlocks;
322  OuterLoopBlocks.push_back(NewBB);
323  // Now that we know which blocks are in L and which need to be moved to
324  // OuterLoop, move any blocks that need it.
325  for (unsigned i = 0; i != L->getBlocks().size(); ++i) {
326  BasicBlock *BB = L->getBlocks()[i];
327  if (!BlocksInL.count(BB)) {
328  // Move this block to the parent, updating the exit blocks sets
330  if ((*LI)[BB] == L) {
331  LI->changeLoopFor(BB, NewOuter);
332  OuterLoopBlocks.push_back(BB);
333  }
334  --i;
335  }
336  }
337 
338  // Split edges to exit blocks from the inner loop, if they emerged in the
339  // process of separating the outer one.
340  formDedicatedExitBlocks(L, DT, LI, MSSAU, PreserveLCSSA);
341 
342  if (PreserveLCSSA) {
343  // Fix LCSSA form for L. Some values, which previously were only used inside
344  // L, can now be used in NewOuter loop. We need to insert phi-nodes for them
345  // in corresponding exit blocks.
346  // We don't need to form LCSSA recursively, because there cannot be uses
347  // inside a newly created loop of defs from inner loops as those would
348  // already be a use of an LCSSA phi node.
349  formLCSSA(*L, *DT, LI, SE);
350 
351  assert(NewOuter->isRecursivelyLCSSAForm(*DT, *LI) &&
352  "LCSSA is broken after separating nested loops!");
353  }
354 
355  return NewOuter;
356 }
357 
358 /// This method is called when the specified loop has more than one
359 /// backedge in it.
360 ///
361 /// If this occurs, revector all of these backedges to target a new basic block
362 /// and have that block branch to the loop header. This ensures that loops
363 /// have exactly one backedge.
365  DominatorTree *DT, LoopInfo *LI,
366  MemorySSAUpdater *MSSAU) {
367  assert(L->getNumBackEdges() > 1 && "Must have > 1 backedge!");
368 
369  // Get information about the loop
370  BasicBlock *Header = L->getHeader();
371  Function *F = Header->getParent();
372 
373  // Unique backedge insertion currently depends on having a preheader.
374  if (!Preheader)
375  return nullptr;
376 
377  // The header is not an EH pad; preheader insertion should ensure this.
378  assert(!Header->isEHPad() && "Can't insert backedge to EH pad");
379 
380  // Figure out which basic blocks contain back-edges to the loop header.
381  std::vector<BasicBlock*> BackedgeBlocks;
382  for (BasicBlock *P : predecessors(Header)) {
383  // Indirect edges cannot be split, so we must fail if we find one.
384  if (P->getTerminator()->isIndirectTerminator())
385  return nullptr;
386 
387  if (P != Preheader) BackedgeBlocks.push_back(P);
388  }
389 
390  // Create and insert the new backedge block...
391  BasicBlock *BEBlock = BasicBlock::Create(Header->getContext(),
392  Header->getName() + ".backedge", F);
393  BranchInst *BETerminator = BranchInst::Create(Header, BEBlock);
394  BETerminator->setDebugLoc(Header->getFirstNonPHI()->getDebugLoc());
395 
396  LLVM_DEBUG(dbgs() << "LoopSimplify: Inserting unique backedge block "
397  << BEBlock->getName() << "\n");
398 
399  // Move the new backedge block to right after the last backedge block.
400  Function::iterator InsertPos = ++BackedgeBlocks.back()->getIterator();
401  F->getBasicBlockList().splice(InsertPos, F->getBasicBlockList(), BEBlock);
402 
403  // Now that the block has been inserted into the function, create PHI nodes in
404  // the backedge block which correspond to any PHI nodes in the header block.
405  for (BasicBlock::iterator I = Header->begin(); isa<PHINode>(I); ++I) {
406  PHINode *PN = cast<PHINode>(I);
407  PHINode *NewPN = PHINode::Create(PN->getType(), BackedgeBlocks.size(),
408  PN->getName()+".be", BETerminator);
409 
410  // Loop over the PHI node, moving all entries except the one for the
411  // preheader over to the new PHI node.
412  unsigned PreheaderIdx = ~0U;
413  bool HasUniqueIncomingValue = true;
414  Value *UniqueValue = nullptr;
415  for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
416  BasicBlock *IBB = PN->getIncomingBlock(i);
417  Value *IV = PN->getIncomingValue(i);
418  if (IBB == Preheader) {
419  PreheaderIdx = i;
420  } else {
421  NewPN->addIncoming(IV, IBB);
422  if (HasUniqueIncomingValue) {
423  if (!UniqueValue)
424  UniqueValue = IV;
425  else if (UniqueValue != IV)
426  HasUniqueIncomingValue = false;
427  }
428  }
429  }
430 
431  // Delete all of the incoming values from the old PN except the preheader's
432  assert(PreheaderIdx != ~0U && "PHI has no preheader entry??");
433  if (PreheaderIdx != 0) {
434  PN->setIncomingValue(0, PN->getIncomingValue(PreheaderIdx));
435  PN->setIncomingBlock(0, PN->getIncomingBlock(PreheaderIdx));
436  }
437  // Nuke all entries except the zero'th.
438  for (unsigned i = 0, e = PN->getNumIncomingValues()-1; i != e; ++i)
439  PN->removeIncomingValue(e-i, false);
440 
441  // Finally, add the newly constructed PHI node as the entry for the BEBlock.
442  PN->addIncoming(NewPN, BEBlock);
443 
444  // As an optimization, if all incoming values in the new PhiNode (which is a
445  // subset of the incoming values of the old PHI node) have the same value,
446  // eliminate the PHI Node.
447  if (HasUniqueIncomingValue) {
448  NewPN->replaceAllUsesWith(UniqueValue);
449  BEBlock->getInstList().erase(NewPN);
450  }
451  }
452 
453  // Now that all of the PHI nodes have been inserted and adjusted, modify the
454  // backedge blocks to jump to the BEBlock instead of the header.
455  // If one of the backedges has llvm.loop metadata attached, we remove
456  // it from the backedge and add it to BEBlock.
457  unsigned LoopMDKind = BEBlock->getContext().getMDKindID("llvm.loop");
458  MDNode *LoopMD = nullptr;
459  for (unsigned i = 0, e = BackedgeBlocks.size(); i != e; ++i) {
460  Instruction *TI = BackedgeBlocks[i]->getTerminator();
461  if (!LoopMD)
462  LoopMD = TI->getMetadata(LoopMDKind);
463  TI->setMetadata(LoopMDKind, nullptr);
464  TI->replaceSuccessorWith(Header, BEBlock);
465  }
466  BEBlock->getTerminator()->setMetadata(LoopMDKind, LoopMD);
467 
468  //===--- Update all analyses which we must preserve now -----------------===//
469 
470  // Update Loop Information - we know that this block is now in the current
471  // loop and all parent loops.
472  L->addBasicBlockToLoop(BEBlock, *LI);
473 
474  // Update dominator information
475  DT->splitBlock(BEBlock);
476 
477  if (MSSAU)
478  MSSAU->updatePhisWhenInsertingUniqueBackedgeBlock(Header, Preheader,
479  BEBlock);
480 
481  return BEBlock;
482 }
483 
484 /// Simplify one loop and queue further loops for simplification.
485 static bool simplifyOneLoop(Loop *L, SmallVectorImpl<Loop *> &Worklist,
486  DominatorTree *DT, LoopInfo *LI,
488  MemorySSAUpdater *MSSAU, bool PreserveLCSSA) {
489  bool Changed = false;
490  if (MSSAU && VerifyMemorySSA)
491  MSSAU->getMemorySSA()->verifyMemorySSA();
492 
493 ReprocessLoop:
494 
495  // Check to see that no blocks (other than the header) in this loop have
496  // predecessors that are not in the loop. This is not valid for natural
497  // loops, but can occur if the blocks are unreachable. Since they are
498  // unreachable we can just shamelessly delete those CFG edges!
499  for (Loop::block_iterator BB = L->block_begin(), E = L->block_end();
500  BB != E; ++BB) {
501  if (*BB == L->getHeader()) continue;
502 
504  for (BasicBlock *P : predecessors(*BB))
505  if (!L->contains(P))
506  BadPreds.insert(P);
507 
508  // Delete each unique out-of-loop (and thus dead) predecessor.
509  for (BasicBlock *P : BadPreds) {
510 
511  LLVM_DEBUG(dbgs() << "LoopSimplify: Deleting edge from dead predecessor "
512  << P->getName() << "\n");
513 
514  // Zap the dead pred's terminator and replace it with unreachable.
515  Instruction *TI = P->getTerminator();
516  changeToUnreachable(TI, PreserveLCSSA,
517  /*DTU=*/nullptr, MSSAU);
518  Changed = true;
519  }
520  }
521 
522  if (MSSAU && VerifyMemorySSA)
523  MSSAU->getMemorySSA()->verifyMemorySSA();
524 
525  // If there are exiting blocks with branches on undef, resolve the undef in
526  // the direction which will exit the loop. This will help simplify loop
527  // trip count computations.
528  SmallVector<BasicBlock*, 8> ExitingBlocks;
529  L->getExitingBlocks(ExitingBlocks);
530  for (BasicBlock *ExitingBlock : ExitingBlocks)
531  if (BranchInst *BI = dyn_cast<BranchInst>(ExitingBlock->getTerminator()))
532  if (BI->isConditional()) {
533  if (UndefValue *Cond = dyn_cast<UndefValue>(BI->getCondition())) {
534 
535  LLVM_DEBUG(dbgs()
536  << "LoopSimplify: Resolving \"br i1 undef\" to exit in "
537  << ExitingBlock->getName() << "\n");
538 
539  BI->setCondition(ConstantInt::get(Cond->getType(),
540  !L->contains(BI->getSuccessor(0))));
541 
542  Changed = true;
543  }
544  }
545 
546  // Does the loop already have a preheader? If so, don't insert one.
547  BasicBlock *Preheader = L->getLoopPreheader();
548  if (!Preheader) {
549  Preheader = InsertPreheaderForLoop(L, DT, LI, MSSAU, PreserveLCSSA);
550  if (Preheader)
551  Changed = true;
552  }
553 
554  // Next, check to make sure that all exit nodes of the loop only have
555  // predecessors that are inside of the loop. This check guarantees that the
556  // loop preheader/header will dominate the exit blocks. If the exit block has
557  // predecessors from outside of the loop, split the edge now.
558  if (formDedicatedExitBlocks(L, DT, LI, MSSAU, PreserveLCSSA))
559  Changed = true;
560 
561  if (MSSAU && VerifyMemorySSA)
562  MSSAU->getMemorySSA()->verifyMemorySSA();
563 
564  // If the header has more than two predecessors at this point (from the
565  // preheader and from multiple backedges), we must adjust the loop.
566  BasicBlock *LoopLatch = L->getLoopLatch();
567  if (!LoopLatch) {
568  // If this is really a nested loop, rip it out into a child loop. Don't do
569  // this for loops with a giant number of backedges, just factor them into a
570  // common backedge instead.
571  if (L->getNumBackEdges() < 8) {
572  if (Loop *OuterL = separateNestedLoop(L, Preheader, DT, LI, SE,
573  PreserveLCSSA, AC, MSSAU)) {
574  ++NumNested;
575  // Enqueue the outer loop as it should be processed next in our
576  // depth-first nest walk.
577  Worklist.push_back(OuterL);
578 
579  // This is a big restructuring change, reprocess the whole loop.
580  Changed = true;
581  // GCC doesn't tail recursion eliminate this.
582  // FIXME: It isn't clear we can't rely on LLVM to TRE this.
583  goto ReprocessLoop;
584  }
585  }
586 
587  // If we either couldn't, or didn't want to, identify nesting of the loops,
588  // insert a new block that all backedges target, then make it jump to the
589  // loop header.
590  LoopLatch = insertUniqueBackedgeBlock(L, Preheader, DT, LI, MSSAU);
591  if (LoopLatch)
592  Changed = true;
593  }
594 
595  if (MSSAU && VerifyMemorySSA)
596  MSSAU->getMemorySSA()->verifyMemorySSA();
597 
598  const DataLayout &DL = L->getHeader()->getModule()->getDataLayout();
599 
600  // Scan over the PHI nodes in the loop header. Since they now have only two
601  // incoming values (the loop is canonicalized), we may have simplified the PHI
602  // down to 'X = phi [X, Y]', which should be replaced with 'Y'.
603  PHINode *PN;
604  for (BasicBlock::iterator I = L->getHeader()->begin();
605  (PN = dyn_cast<PHINode>(I++)); )
606  if (Value *V = SimplifyInstruction(PN, {DL, nullptr, DT, AC})) {
607  if (SE) SE->forgetValue(PN);
608  if (!PreserveLCSSA || LI->replacementPreservesLCSSAForm(PN, V)) {
609  PN->replaceAllUsesWith(V);
610  PN->eraseFromParent();
611  Changed = true;
612  }
613  }
614 
615  // If this loop has multiple exits and the exits all go to the same
616  // block, attempt to merge the exits. This helps several passes, such
617  // as LoopRotation, which do not support loops with multiple exits.
618  // SimplifyCFG also does this (and this code uses the same utility
619  // function), however this code is loop-aware, where SimplifyCFG is
620  // not. That gives it the advantage of being able to hoist
621  // loop-invariant instructions out of the way to open up more
622  // opportunities, and the disadvantage of having the responsibility
623  // to preserve dominator information.
624  auto HasUniqueExitBlock = [&]() {
625  BasicBlock *UniqueExit = nullptr;
626  for (auto *ExitingBB : ExitingBlocks)
627  for (auto *SuccBB : successors(ExitingBB)) {
628  if (L->contains(SuccBB))
629  continue;
630 
631  if (!UniqueExit)
632  UniqueExit = SuccBB;
633  else if (UniqueExit != SuccBB)
634  return false;
635  }
636 
637  return true;
638  };
639  if (HasUniqueExitBlock()) {
640  for (unsigned i = 0, e = ExitingBlocks.size(); i != e; ++i) {
641  BasicBlock *ExitingBlock = ExitingBlocks[i];
642  if (!ExitingBlock->getSinglePredecessor()) continue;
643  BranchInst *BI = dyn_cast<BranchInst>(ExitingBlock->getTerminator());
644  if (!BI || !BI->isConditional()) continue;
645  CmpInst *CI = dyn_cast<CmpInst>(BI->getCondition());
646  if (!CI || CI->getParent() != ExitingBlock) continue;
647 
648  // Attempt to hoist out all instructions except for the
649  // comparison and the branch.
650  bool AllInvariant = true;
651  bool AnyInvariant = false;
652  for (auto I = ExitingBlock->instructionsWithoutDebug().begin(); &*I != BI; ) {
653  Instruction *Inst = &*I++;
654  if (Inst == CI)
655  continue;
656  if (!L->makeLoopInvariant(
657  Inst, AnyInvariant,
658  Preheader ? Preheader->getTerminator() : nullptr, MSSAU)) {
659  AllInvariant = false;
660  break;
661  }
662  }
663  if (AnyInvariant) {
664  Changed = true;
665  // The loop disposition of all SCEV expressions that depend on any
666  // hoisted values have also changed.
667  if (SE)
668  SE->forgetLoopDispositions(L);
669  }
670  if (!AllInvariant) continue;
671 
672  // The block has now been cleared of all instructions except for
673  // a comparison and a conditional branch. SimplifyCFG may be able
674  // to fold it now.
675  if (!FoldBranchToCommonDest(BI, /*DTU=*/nullptr, MSSAU))
676  continue;
677 
678  // Success. The block is now dead, so remove it from the loop,
679  // update the dominator tree and delete it.
680  LLVM_DEBUG(dbgs() << "LoopSimplify: Eliminating exiting block "
681  << ExitingBlock->getName() << "\n");
682 
683  assert(pred_empty(ExitingBlock));
684  Changed = true;
685  LI->removeBlock(ExitingBlock);
686 
687  DomTreeNode *Node = DT->getNode(ExitingBlock);
688  while (!Node->isLeaf()) {
689  DomTreeNode *Child = Node->back();
690  DT->changeImmediateDominator(Child, Node->getIDom());
691  }
692  DT->eraseNode(ExitingBlock);
693  if (MSSAU) {
694  SmallSetVector<BasicBlock *, 8> ExitBlockSet;
695  ExitBlockSet.insert(ExitingBlock);
696  MSSAU->removeBlocks(ExitBlockSet);
697  }
698 
700  ExitingBlock, /* KeepOneInputPHIs */ PreserveLCSSA);
702  ExitingBlock, /* KeepOneInputPHIs */ PreserveLCSSA);
703  ExitingBlock->eraseFromParent();
704  }
705  }
706 
707  // Changing exit conditions for blocks may affect exit counts of this loop and
708  // any of its paretns, so we must invalidate the entire subtree if we've made
709  // any changes.
710  if (Changed && SE)
711  SE->forgetTopmostLoop(L);
712 
713  if (MSSAU && VerifyMemorySSA)
714  MSSAU->getMemorySSA()->verifyMemorySSA();
715 
716  return Changed;
717 }
718 
721  MemorySSAUpdater *MSSAU, bool PreserveLCSSA) {
722  bool Changed = false;
723 
724 #ifndef NDEBUG
725  // If we're asked to preserve LCSSA, the loop nest needs to start in LCSSA
726  // form.
727  if (PreserveLCSSA) {
728  assert(DT && "DT not available.");
729  assert(LI && "LI not available.");
730  assert(L->isRecursivelyLCSSAForm(*DT, *LI) &&
731  "Requested to preserve LCSSA, but it's already broken.");
732  }
733 #endif
734 
735  // Worklist maintains our depth-first queue of loops in this nest to process.
736  SmallVector<Loop *, 4> Worklist;
737  Worklist.push_back(L);
738 
739  // Walk the worklist from front to back, pushing newly found sub loops onto
740  // the back. This will let us process loops from back to front in depth-first
741  // order. We can use this simple process because loops form a tree.
742  for (unsigned Idx = 0; Idx != Worklist.size(); ++Idx) {
743  Loop *L2 = Worklist[Idx];
744  Worklist.append(L2->begin(), L2->end());
745  }
746 
747  while (!Worklist.empty())
748  Changed |= simplifyOneLoop(Worklist.pop_back_val(), Worklist, DT, LI, SE,
749  AC, MSSAU, PreserveLCSSA);
750 
751  return Changed;
752 }
753 
754 namespace {
755  struct LoopSimplify : public FunctionPass {
756  static char ID; // Pass identification, replacement for typeid
757  LoopSimplify() : FunctionPass(ID) {
759  }
760 
761  bool runOnFunction(Function &F) override;
762 
763  void getAnalysisUsage(AnalysisUsage &AU) const override {
765 
766  // We need loop information to identify the loops...
769 
772 
780  AU.addPreservedID(BreakCriticalEdgesID); // No critical edges added.
783  }
784 
785  /// verifyAnalysis() - Verify LoopSimplifyForm's guarantees.
786  void verifyAnalysis() const override;
787  };
788 }
789 
790 char LoopSimplify::ID = 0;
791 INITIALIZE_PASS_BEGIN(LoopSimplify, "loop-simplify",
792  "Canonicalize natural loops", false, false)
797  "Canonicalize natural loops", false, false)
798 
799 // Publicly exposed interface to pass...
800 char &llvm::LoopSimplifyID = LoopSimplify::ID;
801 Pass *llvm::createLoopSimplifyPass() { return new LoopSimplify(); }
802 
803 /// runOnFunction - Run down all loops in the CFG (recursively, but we could do
804 /// it in any convenient order) inserting preheaders...
805 ///
807  bool Changed = false;
808  LoopInfo *LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
809  DominatorTree *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
810  auto *SEWP = getAnalysisIfAvailable<ScalarEvolutionWrapperPass>();
811  ScalarEvolution *SE = SEWP ? &SEWP->getSE() : nullptr;
812  AssumptionCache *AC =
813  &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
814  MemorySSA *MSSA = nullptr;
815  std::unique_ptr<MemorySSAUpdater> MSSAU;
816  auto *MSSAAnalysis = getAnalysisIfAvailable<MemorySSAWrapperPass>();
817  if (MSSAAnalysis) {
818  MSSA = &MSSAAnalysis->getMSSA();
819  MSSAU = std::make_unique<MemorySSAUpdater>(MSSA);
820  }
821 
822  bool PreserveLCSSA = mustPreserveAnalysisID(LCSSAID);
823 
824  // Simplify each loop nest in the function.
825  for (auto *L : *LI)
826  Changed |= simplifyLoop(L, DT, LI, SE, AC, MSSAU.get(), PreserveLCSSA);
827 
828 #ifndef NDEBUG
829  if (PreserveLCSSA) {
830  bool InLCSSA = all_of(
831  *LI, [&](Loop *L) { return L->isRecursivelyLCSSAForm(*DT, *LI); });
832  assert(InLCSSA && "LCSSA is broken after loop-simplify.");
833  }
834 #endif
835  return Changed;
836 }
837 
840  bool Changed = false;
841  LoopInfo *LI = &AM.getResult<LoopAnalysis>(F);
845  auto *MSSAAnalysis = AM.getCachedResult<MemorySSAAnalysis>(F);
846  std::unique_ptr<MemorySSAUpdater> MSSAU;
847  if (MSSAAnalysis) {
848  auto *MSSA = &MSSAAnalysis->getMSSA();
849  MSSAU = std::make_unique<MemorySSAUpdater>(MSSA);
850  }
851 
852 
853  // Note that we don't preserve LCSSA in the new PM, if you need it run LCSSA
854  // after simplifying the loops. MemorySSA is preserved if it exists.
855  for (auto *L : *LI)
856  Changed |=
857  simplifyLoop(L, DT, LI, SE, AC, MSSAU.get(), /*PreserveLCSSA*/ false);
858 
859  if (!Changed)
860  return PreservedAnalyses::all();
861 
864  PA.preserve<LoopAnalysis>();
867  if (MSSAAnalysis)
869  // BPI maps conditional terminators to probabilities, LoopSimplify can insert
870  // blocks, but it does so only by splitting existing blocks and edges. This
871  // results in the interesting property that all new terminators inserted are
872  // unconditional branches which do not appear in BPI. All deletions are
873  // handled via ValueHandle callbacks w/in BPI.
875  return PA;
876 }
877 
878 // FIXME: Restore this code when we re-enable verification in verifyAnalysis
879 // below.
880 #if 0
881 static void verifyLoop(Loop *L) {
882  // Verify subloops.
883  for (Loop::iterator I = L->begin(), E = L->end(); I != E; ++I)
884  verifyLoop(*I);
885 
886  // It used to be possible to just assert L->isLoopSimplifyForm(), however
887  // with the introduction of indirectbr, there are now cases where it's
888  // not possible to transform a loop as necessary. We can at least check
889  // that there is an indirectbr near any time there's trouble.
890 
891  // Indirectbr can interfere with preheader and unique backedge insertion.
892  if (!L->getLoopPreheader() || !L->getLoopLatch()) {
893  bool HasIndBrPred = false;
894  for (BasicBlock *Pred : predecessors(L->getHeader()))
895  if (isa<IndirectBrInst>(Pred->getTerminator())) {
896  HasIndBrPred = true;
897  break;
898  }
899  assert(HasIndBrPred &&
900  "LoopSimplify has no excuse for missing loop header info!");
901  (void)HasIndBrPred;
902  }
903 
904  // Indirectbr can interfere with exit block canonicalization.
905  if (!L->hasDedicatedExits()) {
906  bool HasIndBrExiting = false;
907  SmallVector<BasicBlock*, 8> ExitingBlocks;
908  L->getExitingBlocks(ExitingBlocks);
909  for (unsigned i = 0, e = ExitingBlocks.size(); i != e; ++i) {
910  if (isa<IndirectBrInst>((ExitingBlocks[i])->getTerminator())) {
911  HasIndBrExiting = true;
912  break;
913  }
914  }
915 
916  assert(HasIndBrExiting &&
917  "LoopSimplify has no excuse for missing exit block info!");
918  (void)HasIndBrExiting;
919  }
920 }
921 #endif
922 
923 void LoopSimplify::verifyAnalysis() const {
924  // FIXME: This routine is being called mid-way through the loop pass manager
925  // as loop passes destroy this analysis. That's actually fine, but we have no
926  // way of expressing that here. Once all of the passes that destroy this are
927  // hoisted out of the loop pass manager we can add back verification here.
928 #if 0
929  for (LoopInfo::iterator I = LI->begin(), E = LI->end(); I != E; ++I)
930  verifyLoop(*I);
931 #endif
932 }
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::predecessors
pred_range predecessors(BasicBlock *BB)
Definition: CFG.h:127
llvm::ScalarEvolutionAnalysis
Analysis pass that exposes the ScalarEvolution for a function.
Definition: ScalarEvolution.h:2036
llvm
---------------------— PointerInfo ------------------------------------—
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:801
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:1899
llvm::DataLayout
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:112
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:735
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:779
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:7542
llvm::DependenceAnalysisWrapperPass
Legacy pass manager pass to access dependence information.
Definition: DependenceAnalysis.h:979
MemorySSAUpdater.h
llvm::Function
Definition: Function.h:61
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::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1168
Statistic.h
llvm::ScalarEvolution
The main scalar evolution driver.
Definition: ScalarEvolution.h:461
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:1005
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:1376
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:485
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:1032
Module.h
llvm::BasicBlock::eraseFromParent
SymbolTableList< BasicBlock >::iterator eraseFromParent()
Unlink 'this' from the containing function and delete it.
Definition: BasicBlock.cpp:129
llvm::LoopInfoWrapperPass
The legacy pass manager's analysis pass to compute loop information.
Definition: LoopInfo.h:1268
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:797
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::BasicBlock::getSinglePredecessor
const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
Definition: BasicBlock.cpp:264
llvm::SmallVectorImpl::pop_back_val
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:635
llvm::successors
succ_range successors(Instruction *I)
Definition: CFG.h:262
BasicAliasAnalysis.h
llvm::PHINode::setIncomingValue
void setIncomingValue(unsigned i, Value *V)
Definition: Instructions.h:2732
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
DepthFirstIterator.h
F
#define F(x, y, z)
Definition: MD5.cpp:56
llvm::Instruction::setMetadata
void setMetadata(unsigned KindID, MDNode *Node)
Set the metadata of the specified kind to the specified node.
Definition: Metadata.cpp:1336
llvm::LoopBase::block_end
block_iterator block_end() const
Definition: LoopInfo.h:177
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: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: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:1551
llvm::MemorySSAWrapperPass
Legacy analysis pass which computes MemorySSA.
Definition: MemorySSA.h:981
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:2729
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:648
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:3165
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:1115
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:6293
llvm::DominatorTreeWrapperPass
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:287
llvm::STATISTIC
STATISTIC(NumFunctions, "Total number of functions")
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:900
LoopUtils.h
llvm::ScalarEvolutionWrapperPass
Definition: ScalarEvolution.h:2066
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:1148
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:144
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:212
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:2725
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:931
llvm::BranchInst::getCondition
Value * getCondition() const
Definition: Instructions.h:3149
placeSplitBlockCarefully
static void placeSplitBlockCarefully(BasicBlock *NewBB, SmallVectorImpl< BasicBlock * > &SplitPreds, Loop *L)
Definition: LoopSimplify.cpp:86
llvm::LoopBase::block_begin
block_iterator block_begin() const
Definition: LoopInfo.h:176
llvm::CmpInst
This class is the base class for the comparison instructions.
Definition: InstrTypes.h:710
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:364
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::LoopBase< BasicBlock, Loop >::block_iterator
ArrayRef< BasicBlock * >::const_iterator block_iterator
Definition: LoopInfo.h:175
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:796
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:56
llvm::MemorySSAUpdater::getMemorySSA
MemorySSA * getMemorySSA() const
Get handle on MemorySSA.
Definition: MemorySSAUpdater.h:244
llvm::AssumptionAnalysis
A function analysis which provides an AssumptionCache.
Definition: AssumptionCache.h:169
llvm::PHINode::setIncomingBlock
void setIncomingBlock(unsigned i, BasicBlock *BB)
Definition: Instructions.h:2768
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:244
llvm::PHINode::addIncoming
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
Definition: Instructions.h:2783
llvm::numbers::e
constexpr double e
Definition: MathExtras.h:57
llvm::BranchInst::Create
static BranchInst * Create(BasicBlock *IfTrue, Instruction *InsertBefore=nullptr)
Definition: Instructions.h:3124
llvm::MemorySSA
Encapsulates MemorySSA, including all data associated with memory accesses.
Definition: MemorySSA.h:705
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::UndefValue
'undef' values are things that do not have specified contents.
Definition: Constants.h:1348
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:7515
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:801
llvm::ScalarEvolution::forgetTopmostLoop
void forgetTopmostLoop(const Loop *L)
Definition: ScalarEvolution.cpp:7509
llvm::MDNode
Metadata node.
Definition: Metadata.h:906
llvm::MemorySSAAnalysis
An analysis that produces MemorySSA for a function.
Definition: MemorySSA.h:931
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:1532
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:200
llvm::LoopInfo
Definition: LoopInfo.h:1083
llvm::BasicBlock::instructionsWithoutDebug
iterator_range< filter_iterator< BasicBlock::const_iterator, std::function< bool(const Instruction &)> > > instructionsWithoutDebug(bool SkipPseudoOp=false) const
Return a const iterator range over the instructions in the block, skipping any debug instructions.
Definition: BasicBlock.cpp:100
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:138
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:41
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:256
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:1748
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:148
llvm::BasicBlock::getContext
LLVMContext & getContext() const
Get the context in which this basic block lives.
Definition: BasicBlock.cpp:32
runOnFunction
static bool runOnFunction(Function &F, bool PostInlining)
Definition: EntryExitInstrumenter.cpp:69
llvm::LCSSAID
char & LCSSAID
Definition: LCSSA.cpp:485
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:62
llvm::LoopSimplifyID
char & LoopSimplifyID
Definition: LoopSimplify.cpp:800
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:7452
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:2675
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:798
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:468
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:719
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:2101
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:1015
Dominators.h
llvm::AAResultsWrapperPass
A wrapper pass to provide the legacy pass manager access to a suitably prepared AAResults object.
Definition: AliasAnalysis.h:1336
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:2749
llvm::PHINode
Definition: Instructions.h:2633
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:939
llvm::BasicBlock::removePredecessor
void removePredecessor(BasicBlock *Pred, bool KeepOneInputPHIs=false)
Update PHI nodes in this BasicBlock before removal of predecessor Pred.
Definition: BasicBlock.cpp:321
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:838
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:3068
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:75
Debug.h
llvm::BranchInst::isConditional
bool isConditional() const
Definition: Instructions.h:3147
llvm::Instruction::isIndirectTerminator
bool isIndirectTerminator() const
Definition: Instruction.h:178
llvm::BranchInst::getSuccessor
BasicBlock * getSuccessor(unsigned i) const
Definition: Instructions.h:3161
llvm::LoopAnalysis
Analysis pass that exposes the LoopInfo for a function.
Definition: LoopInfo.h:1243
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:67
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:37
llvm::initializeLoopSimplifyPass
void initializeLoopSimplifyPass(PassRegistry &)