LLVM  6.0.0svn
LoopUnswitch.cpp
Go to the documentation of this file.
1 //===-- LoopUnswitch.cpp - Hoist loop-invariant conditionals in loop ------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This pass transforms loops that contain branches on loop-invariant conditions
11 // to multiple loops. For example, it turns the left into the right code:
12 //
13 // for (...) if (lic)
14 // A for (...)
15 // if (lic) A; B; C
16 // B else
17 // C for (...)
18 // A; C
19 //
20 // This can increase the size of the code exponentially (doubling it every time
21 // a loop is unswitched) so we only unswitch if the resultant code will be
22 // smaller than a threshold.
23 //
24 // This pass expects LICM to be run before it to hoist invariant conditions out
25 // of the loop, to make the unswitching opportunity obvious.
26 //
27 //===----------------------------------------------------------------------===//
28 
29 #include "llvm/ADT/STLExtras.h"
30 #include "llvm/ADT/SmallPtrSet.h"
31 #include "llvm/ADT/Statistic.h"
40 #include "llvm/Analysis/LoopInfo.h"
41 #include "llvm/Analysis/LoopPass.h"
44 #include "llvm/IR/Constants.h"
45 #include "llvm/IR/DerivedTypes.h"
46 #include "llvm/IR/Dominators.h"
47 #include "llvm/IR/Function.h"
48 #include "llvm/IR/InstrTypes.h"
49 #include "llvm/IR/Instructions.h"
50 #include "llvm/IR/MDBuilder.h"
51 #include "llvm/IR/Module.h"
54 #include "llvm/Support/Debug.h"
56 #include "llvm/Transforms/Scalar.h"
61 #include <algorithm>
62 #include <map>
63 #include <set>
64 using namespace llvm;
65 
66 #define DEBUG_TYPE "loop-unswitch"
67 
68 STATISTIC(NumBranches, "Number of branches unswitched");
69 STATISTIC(NumSwitches, "Number of switches unswitched");
70 STATISTIC(NumGuards, "Number of guards unswitched");
71 STATISTIC(NumSelects , "Number of selects unswitched");
72 STATISTIC(NumTrivial , "Number of unswitches that are trivial");
73 STATISTIC(NumSimplify, "Number of simplifications of unswitched code");
74 STATISTIC(TotalInsts, "Total number of instructions analyzed");
75 
76 // The specific value of 100 here was chosen based only on intuition and a
77 // few specific examples.
78 static cl::opt<unsigned>
79 Threshold("loop-unswitch-threshold", cl::desc("Max loop size to unswitch"),
80  cl::init(100), cl::Hidden);
81 
82 namespace {
83 
84  class LUAnalysisCache {
85 
87  UnswitchedValsMap;
88 
89  typedef UnswitchedValsMap::iterator UnswitchedValsIt;
90 
91  struct LoopProperties {
92  unsigned CanBeUnswitchedCount;
93  unsigned WasUnswitchedCount;
94  unsigned SizeEstimation;
95  UnswitchedValsMap UnswitchedVals;
96  };
97 
98  // Here we use std::map instead of DenseMap, since we need to keep valid
99  // LoopProperties pointer for current loop for better performance.
100  typedef std::map<const Loop*, LoopProperties> LoopPropsMap;
101  typedef LoopPropsMap::iterator LoopPropsMapIt;
102 
103  LoopPropsMap LoopsProperties;
104  UnswitchedValsMap *CurLoopInstructions;
105  LoopProperties *CurrentLoopProperties;
106 
107  // A loop unswitching with an estimated cost above this threshold
108  // is not performed. MaxSize is turned into unswitching quota for
109  // the current loop, and reduced correspondingly, though note that
110  // the quota is returned by releaseMemory() when the loop has been
111  // processed, so that MaxSize will return to its previous
112  // value. So in most cases MaxSize will equal the Threshold flag
113  // when a new loop is processed. An exception to that is that
114  // MaxSize will have a smaller value while processing nested loops
115  // that were introduced due to loop unswitching of an outer loop.
116  //
117  // FIXME: The way that MaxSize works is subtle and depends on the
118  // pass manager processing loops and calling releaseMemory() in a
119  // specific order. It would be good to find a more straightforward
120  // way of doing what MaxSize does.
121  unsigned MaxSize;
122 
123  public:
124  LUAnalysisCache()
125  : CurLoopInstructions(nullptr), CurrentLoopProperties(nullptr),
126  MaxSize(Threshold) {}
127 
128  // Analyze loop. Check its size, calculate is it possible to unswitch
129  // it. Returns true if we can unswitch this loop.
130  bool countLoop(const Loop *L, const TargetTransformInfo &TTI,
131  AssumptionCache *AC);
132 
133  // Clean all data related to given loop.
134  void forgetLoop(const Loop *L);
135 
136  // Mark case value as unswitched.
137  // Since SI instruction can be partly unswitched, in order to avoid
138  // extra unswitching in cloned loops keep track all unswitched values.
139  void setUnswitched(const SwitchInst *SI, const Value *V);
140 
141  // Check was this case value unswitched before or not.
142  bool isUnswitched(const SwitchInst *SI, const Value *V);
143 
144  // Returns true if another unswitching could be done within the cost
145  // threshold.
146  bool CostAllowsUnswitching();
147 
148  // Clone all loop-unswitch related loop properties.
149  // Redistribute unswitching quotas.
150  // Note, that new loop data is stored inside the VMap.
151  void cloneData(const Loop *NewLoop, const Loop *OldLoop,
152  const ValueToValueMapTy &VMap);
153  };
154 
155  class LoopUnswitch : public LoopPass {
156  LoopInfo *LI; // Loop information
157  LPPassManager *LPM;
158  AssumptionCache *AC;
159 
160  // Used to check if second loop needs processing after
161  // RewriteLoopBodyWithConditionConstant rewrites first loop.
162  std::vector<Loop*> LoopProcessWorklist;
163 
164  LUAnalysisCache BranchesInfo;
165 
166  bool OptimizeForSize;
167  bool redoLoop;
168 
169  Loop *currentLoop;
170  DominatorTree *DT;
171  BasicBlock *loopHeader;
172  BasicBlock *loopPreheader;
173 
174  bool SanitizeMemory;
175  LoopSafetyInfo SafetyInfo;
176 
177  // LoopBlocks contains all of the basic blocks of the loop, including the
178  // preheader of the loop, the body of the loop, and the exit blocks of the
179  // loop, in that order.
180  std::vector<BasicBlock*> LoopBlocks;
181  // NewBlocks contained cloned copy of basic blocks from LoopBlocks.
182  std::vector<BasicBlock*> NewBlocks;
183 
184  bool hasBranchDivergence;
185 
186  public:
187  static char ID; // Pass ID, replacement for typeid
188  explicit LoopUnswitch(bool Os = false, bool hasBranchDivergence = false) :
189  LoopPass(ID), OptimizeForSize(Os), redoLoop(false),
190  currentLoop(nullptr), DT(nullptr), loopHeader(nullptr),
191  loopPreheader(nullptr), hasBranchDivergence(hasBranchDivergence) {
193  }
194 
195  bool runOnLoop(Loop *L, LPPassManager &LPM) override;
196  bool processCurrentLoop();
197  bool isUnreachableDueToPreviousUnswitching(BasicBlock *);
198  /// This transformation requires natural loop information & requires that
199  /// loop preheaders be inserted into the CFG.
200  ///
201  void getAnalysisUsage(AnalysisUsage &AU) const override {
204  if (hasBranchDivergence)
207  }
208 
209  private:
210 
211  void releaseMemory() override {
212  BranchesInfo.forgetLoop(currentLoop);
213  }
214 
215  void initLoopData() {
216  loopHeader = currentLoop->getHeader();
217  loopPreheader = currentLoop->getLoopPreheader();
218  }
219 
220  /// Split all of the edges from inside the loop to their exit blocks.
221  /// Update the appropriate Phi nodes as we do so.
222  void SplitExitEdges(Loop *L,
223  const SmallVectorImpl<BasicBlock *> &ExitBlocks);
224 
225  bool TryTrivialLoopUnswitch(bool &Changed);
226 
227  bool UnswitchIfProfitable(Value *LoopCond, Constant *Val,
228  TerminatorInst *TI = nullptr);
229  void UnswitchTrivialCondition(Loop *L, Value *Cond, Constant *Val,
230  BasicBlock *ExitBlock, TerminatorInst *TI);
231  void UnswitchNontrivialCondition(Value *LIC, Constant *OnVal, Loop *L,
232  TerminatorInst *TI);
233 
234  void RewriteLoopBodyWithConditionConstant(Loop *L, Value *LIC,
235  Constant *Val, bool isEqual);
236 
237  void EmitPreheaderBranchOnCondition(Value *LIC, Constant *Val,
238  BasicBlock *TrueDest,
239  BasicBlock *FalseDest,
240  Instruction *InsertPt,
241  TerminatorInst *TI);
242 
243  void SimplifyCode(std::vector<Instruction*> &Worklist, Loop *L);
244 
245  /// Given that the Invariant is not equal to Val. Simplify instructions
246  /// in the loop.
247  Value *SimplifyInstructionWithNotEqual(Instruction *Inst, Value *Invariant,
248  Constant *Val);
249  };
250 }
251 
252 // Analyze loop. Check its size, calculate is it possible to unswitch
253 // it. Returns true if we can unswitch this loop.
254 bool LUAnalysisCache::countLoop(const Loop *L, const TargetTransformInfo &TTI,
255  AssumptionCache *AC) {
256 
257  LoopPropsMapIt PropsIt;
258  bool Inserted;
259  std::tie(PropsIt, Inserted) =
260  LoopsProperties.insert(std::make_pair(L, LoopProperties()));
261 
262  LoopProperties &Props = PropsIt->second;
263 
264  if (Inserted) {
265  // New loop.
266 
267  // Limit the number of instructions to avoid causing significant code
268  // expansion, and the number of basic blocks, to avoid loops with
269  // large numbers of branches which cause loop unswitching to go crazy.
270  // This is a very ad-hoc heuristic.
271 
273  CodeMetrics::collectEphemeralValues(L, AC, EphValues);
274 
275  // FIXME: This is overly conservative because it does not take into
276  // consideration code simplification opportunities and code that can
277  // be shared by the resultant unswitched loops.
279  for (Loop::block_iterator I = L->block_begin(), E = L->block_end(); I != E;
280  ++I)
281  Metrics.analyzeBasicBlock(*I, TTI, EphValues);
282 
283  Props.SizeEstimation = Metrics.NumInsts;
284  Props.CanBeUnswitchedCount = MaxSize / (Props.SizeEstimation);
285  Props.WasUnswitchedCount = 0;
286  MaxSize -= Props.SizeEstimation * Props.CanBeUnswitchedCount;
287 
288  if (Metrics.notDuplicatable) {
289  DEBUG(dbgs() << "NOT unswitching loop %"
290  << L->getHeader()->getName() << ", contents cannot be "
291  << "duplicated!\n");
292  return false;
293  }
294  }
295 
296  // Be careful. This links are good only before new loop addition.
297  CurrentLoopProperties = &Props;
298  CurLoopInstructions = &Props.UnswitchedVals;
299 
300  return true;
301 }
302 
303 // Clean all data related to given loop.
304 void LUAnalysisCache::forgetLoop(const Loop *L) {
305 
306  LoopPropsMapIt LIt = LoopsProperties.find(L);
307 
308  if (LIt != LoopsProperties.end()) {
309  LoopProperties &Props = LIt->second;
310  MaxSize += (Props.CanBeUnswitchedCount + Props.WasUnswitchedCount) *
311  Props.SizeEstimation;
312  LoopsProperties.erase(LIt);
313  }
314 
315  CurrentLoopProperties = nullptr;
316  CurLoopInstructions = nullptr;
317 }
318 
319 // Mark case value as unswitched.
320 // Since SI instruction can be partly unswitched, in order to avoid
321 // extra unswitching in cloned loops keep track all unswitched values.
322 void LUAnalysisCache::setUnswitched(const SwitchInst *SI, const Value *V) {
323  (*CurLoopInstructions)[SI].insert(V);
324 }
325 
326 // Check was this case value unswitched before or not.
327 bool LUAnalysisCache::isUnswitched(const SwitchInst *SI, const Value *V) {
328  return (*CurLoopInstructions)[SI].count(V);
329 }
330 
331 bool LUAnalysisCache::CostAllowsUnswitching() {
332  return CurrentLoopProperties->CanBeUnswitchedCount > 0;
333 }
334 
335 // Clone all loop-unswitch related loop properties.
336 // Redistribute unswitching quotas.
337 // Note, that new loop data is stored inside the VMap.
338 void LUAnalysisCache::cloneData(const Loop *NewLoop, const Loop *OldLoop,
339  const ValueToValueMapTy &VMap) {
340 
341  LoopProperties &NewLoopProps = LoopsProperties[NewLoop];
342  LoopProperties &OldLoopProps = *CurrentLoopProperties;
343  UnswitchedValsMap &Insts = OldLoopProps.UnswitchedVals;
344 
345  // Reallocate "can-be-unswitched quota"
346 
347  --OldLoopProps.CanBeUnswitchedCount;
348  ++OldLoopProps.WasUnswitchedCount;
349  NewLoopProps.WasUnswitchedCount = 0;
350  unsigned Quota = OldLoopProps.CanBeUnswitchedCount;
351  NewLoopProps.CanBeUnswitchedCount = Quota / 2;
352  OldLoopProps.CanBeUnswitchedCount = Quota - Quota / 2;
353 
354  NewLoopProps.SizeEstimation = OldLoopProps.SizeEstimation;
355 
356  // Clone unswitched values info:
357  // for new loop switches we clone info about values that was
358  // already unswitched and has redundant successors.
359  for (UnswitchedValsIt I = Insts.begin(); I != Insts.end(); ++I) {
360  const SwitchInst *OldInst = I->first;
361  Value *NewI = VMap.lookup(OldInst);
362  const SwitchInst *NewInst = cast_or_null<SwitchInst>(NewI);
363  assert(NewInst && "All instructions that are in SrcBB must be in VMap.");
364 
365  NewLoopProps.UnswitchedVals[NewInst] = OldLoopProps.UnswitchedVals[OldInst];
366  }
367 }
368 
369 char LoopUnswitch::ID = 0;
370 INITIALIZE_PASS_BEGIN(LoopUnswitch, "loop-unswitch", "Unswitch loops",
371  false, false)
376 INITIALIZE_PASS_END(LoopUnswitch, "loop-unswitch", "Unswitch loops",
377  false, false)
378 
379 Pass *llvm::createLoopUnswitchPass(bool Os, bool hasBranchDivergence) {
380  return new LoopUnswitch(Os, hasBranchDivergence);
381 }
382 
383 /// Operator chain lattice.
385  OC_OpChainNone, ///< There is no operator.
386  OC_OpChainOr, ///< There are only ORs.
387  OC_OpChainAnd, ///< There are only ANDs.
388  OC_OpChainMixed ///< There are ANDs and ORs.
389 };
390 
391 /// Cond is a condition that occurs in L. If it is invariant in the loop, or has
392 /// an invariant piece, return the invariant. Otherwise, return null.
393 //
394 /// NOTE: FindLIVLoopCondition will not return a partial LIV by walking up a
395 /// mixed operator chain, as we can not reliably find a value which will simplify
396 /// the operator chain. If the chain is AND-only or OR-only, we can use 0 or ~0
397 /// to simplify the chain.
398 ///
399 /// NOTE: In case a partial LIV and a mixed operator chain, we may be able to
400 /// simplify the condition itself to a loop variant condition, but at the
401 /// cost of creating an entirely new loop.
402 static Value *FindLIVLoopCondition(Value *Cond, Loop *L, bool &Changed,
403  OperatorChain &ParentChain,
405  auto CacheIt = Cache.find(Cond);
406  if (CacheIt != Cache.end())
407  return CacheIt->second;
408 
409  // We started analyze new instruction, increment scanned instructions counter.
410  ++TotalInsts;
411 
412  // We can never unswitch on vector conditions.
413  if (Cond->getType()->isVectorTy())
414  return nullptr;
415 
416  // Constants should be folded, not unswitched on!
417  if (isa<Constant>(Cond)) return nullptr;
418 
419  // TODO: Handle: br (VARIANT|INVARIANT).
420 
421  // Hoist simple values out.
422  if (L->makeLoopInvariant(Cond, Changed)) {
423  Cache[Cond] = Cond;
424  return Cond;
425  }
426 
427  // Walk up the operator chain to find partial invariant conditions.
428  if (BinaryOperator *BO = dyn_cast<BinaryOperator>(Cond))
429  if (BO->getOpcode() == Instruction::And ||
430  BO->getOpcode() == Instruction::Or) {
431  // Given the previous operator, compute the current operator chain status.
432  OperatorChain NewChain;
433  switch (ParentChain) {
434  case OC_OpChainNone:
435  NewChain = BO->getOpcode() == Instruction::And ? OC_OpChainAnd :
436  OC_OpChainOr;
437  break;
438  case OC_OpChainOr:
439  NewChain = BO->getOpcode() == Instruction::Or ? OC_OpChainOr :
441  break;
442  case OC_OpChainAnd:
443  NewChain = BO->getOpcode() == Instruction::And ? OC_OpChainAnd :
445  break;
446  case OC_OpChainMixed:
447  NewChain = OC_OpChainMixed;
448  break;
449  }
450 
451  // If we reach a Mixed state, we do not want to keep walking up as we can not
452  // reliably find a value that will simplify the chain. With this check, we
453  // will return null on the first sight of mixed chain and the caller will
454  // either backtrack to find partial LIV in other operand or return null.
455  if (NewChain != OC_OpChainMixed) {
456  // Update the current operator chain type before we search up the chain.
457  ParentChain = NewChain;
458  // If either the left or right side is invariant, we can unswitch on this,
459  // which will cause the branch to go away in one loop and the condition to
460  // simplify in the other one.
461  if (Value *LHS = FindLIVLoopCondition(BO->getOperand(0), L, Changed,
462  ParentChain, Cache)) {
463  Cache[Cond] = LHS;
464  return LHS;
465  }
466  // We did not manage to find a partial LIV in operand(0). Backtrack and try
467  // operand(1).
468  ParentChain = NewChain;
469  if (Value *RHS = FindLIVLoopCondition(BO->getOperand(1), L, Changed,
470  ParentChain, Cache)) {
471  Cache[Cond] = RHS;
472  return RHS;
473  }
474  }
475  }
476 
477  Cache[Cond] = nullptr;
478  return nullptr;
479 }
480 
481 /// Cond is a condition that occurs in L. If it is invariant in the loop, or has
482 /// an invariant piece, return the invariant along with the operator chain type.
483 /// Otherwise, return null.
484 static std::pair<Value *, OperatorChain> FindLIVLoopCondition(Value *Cond,
485  Loop *L,
486  bool &Changed) {
488  OperatorChain OpChain = OC_OpChainNone;
489  Value *FCond = FindLIVLoopCondition(Cond, L, Changed, OpChain, Cache);
490 
491  // In case we do find a LIV, it can not be obtained by walking up a mixed
492  // operator chain.
493  assert((!FCond || OpChain != OC_OpChainMixed) &&
494  "Do not expect a partial LIV with mixed operator chain");
495  return {FCond, OpChain};
496 }
497 
498 bool LoopUnswitch::runOnLoop(Loop *L, LPPassManager &LPM_Ref) {
499  if (skipLoop(L))
500  return false;
501 
502  AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(
503  *L->getHeader()->getParent());
504  LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
505  LPM = &LPM_Ref;
506  DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
507  currentLoop = L;
508  Function *F = currentLoop->getHeader()->getParent();
509 
510  SanitizeMemory = F->hasFnAttribute(Attribute::SanitizeMemory);
511  if (SanitizeMemory)
512  computeLoopSafetyInfo(&SafetyInfo, L);
513 
514  bool Changed = false;
515  do {
516  assert(currentLoop->isLCSSAForm(*DT));
517  redoLoop = false;
518  Changed |= processCurrentLoop();
519  } while(redoLoop);
520 
521  // FIXME: Reconstruct dom info, because it is not preserved properly.
522  if (Changed)
523  DT->recalculate(*F);
524  return Changed;
525 }
526 
527 // Return true if the BasicBlock BB is unreachable from the loop header.
528 // Return false, otherwise.
529 bool LoopUnswitch::isUnreachableDueToPreviousUnswitching(BasicBlock *BB) {
530  auto *Node = DT->getNode(BB)->getIDom();
531  BasicBlock *DomBB = Node->getBlock();
532  while (currentLoop->contains(DomBB)) {
533  BranchInst *BInst = dyn_cast<BranchInst>(DomBB->getTerminator());
534 
535  Node = DT->getNode(DomBB)->getIDom();
536  DomBB = Node->getBlock();
537 
538  if (!BInst || !BInst->isConditional())
539  continue;
540 
541  Value *Cond = BInst->getCondition();
542  if (!isa<ConstantInt>(Cond))
543  continue;
544 
545  BasicBlock *UnreachableSucc =
546  Cond == ConstantInt::getTrue(Cond->getContext())
547  ? BInst->getSuccessor(1)
548  : BInst->getSuccessor(0);
549 
550  if (DT->dominates(UnreachableSucc, BB))
551  return true;
552  }
553  return false;
554 }
555 
556 /// FIXME: Remove this workaround when freeze related patches are done.
557 /// LoopUnswitch and Equality propagation in GVN have discrepancy about
558 /// whether branch on undef/poison has undefine behavior. Here it is to
559 /// rule out some common cases that we found such discrepancy already
560 /// causing problems. Detail could be found in PR31652. Note if the
561 /// func returns true, it is unsafe. But if it is false, it doesn't mean
562 /// it is necessarily safe.
563 static bool EqualityPropUnSafe(Value &LoopCond) {
564  ICmpInst *CI = dyn_cast<ICmpInst>(&LoopCond);
565  if (!CI || !CI->isEquality())
566  return false;
567 
568  Value *LHS = CI->getOperand(0);
569  Value *RHS = CI->getOperand(1);
570  if (isa<UndefValue>(LHS) || isa<UndefValue>(RHS))
571  return true;
572 
573  auto hasUndefInPHI = [](PHINode &PN) {
574  for (Value *Opd : PN.incoming_values()) {
575  if (isa<UndefValue>(Opd))
576  return true;
577  }
578  return false;
579  };
580  PHINode *LPHI = dyn_cast<PHINode>(LHS);
581  PHINode *RPHI = dyn_cast<PHINode>(RHS);
582  if ((LPHI && hasUndefInPHI(*LPHI)) || (RPHI && hasUndefInPHI(*RPHI)))
583  return true;
584 
585  auto hasUndefInSelect = [](SelectInst &SI) {
586  if (isa<UndefValue>(SI.getTrueValue()) ||
587  isa<UndefValue>(SI.getFalseValue()))
588  return true;
589  return false;
590  };
591  SelectInst *LSI = dyn_cast<SelectInst>(LHS);
592  SelectInst *RSI = dyn_cast<SelectInst>(RHS);
593  if ((LSI && hasUndefInSelect(*LSI)) || (RSI && hasUndefInSelect(*RSI)))
594  return true;
595  return false;
596 }
597 
598 /// Do actual work and unswitch loop if possible and profitable.
599 bool LoopUnswitch::processCurrentLoop() {
600  bool Changed = false;
601 
602  initLoopData();
603 
604  // If LoopSimplify was unable to form a preheader, don't do any unswitching.
605  if (!loopPreheader)
606  return false;
607 
608  // Loops with indirectbr cannot be cloned.
609  if (!currentLoop->isSafeToClone())
610  return false;
611 
612  // Without dedicated exits, splitting the exit edge may fail.
613  if (!currentLoop->hasDedicatedExits())
614  return false;
615 
616  LLVMContext &Context = loopHeader->getContext();
617 
618  // Analyze loop cost, and stop unswitching if loop content can not be duplicated.
619  if (!BranchesInfo.countLoop(
620  currentLoop, getAnalysis<TargetTransformInfoWrapperPass>().getTTI(
621  *currentLoop->getHeader()->getParent()),
622  AC))
623  return false;
624 
625  // Try trivial unswitch first before loop over other basic blocks in the loop.
626  if (TryTrivialLoopUnswitch(Changed)) {
627  return true;
628  }
629 
630  // Run through the instructions in the loop, keeping track of three things:
631  //
632  // - That we do not unswitch loops containing convergent operations, as we
633  // might be making them control dependent on the unswitch value when they
634  // were not before.
635  // FIXME: This could be refined to only bail if the convergent operation is
636  // not already control-dependent on the unswitch value.
637  //
638  // - That basic blocks in the loop contain invokes whose predecessor edges we
639  // cannot split.
640  //
641  // - The set of guard intrinsics encountered (these are non terminator
642  // instructions that are also profitable to be unswitched).
643 
645 
646  for (const auto BB : currentLoop->blocks()) {
647  for (auto &I : *BB) {
648  auto CS = CallSite(&I);
649  if (!CS) continue;
650  if (CS.hasFnAttr(Attribute::Convergent))
651  return false;
652  if (auto *II = dyn_cast<InvokeInst>(&I))
653  if (!II->getUnwindDest()->canSplitPredecessors())
654  return false;
655  if (auto *II = dyn_cast<IntrinsicInst>(&I))
656  if (II->getIntrinsicID() == Intrinsic::experimental_guard)
657  Guards.push_back(II);
658  }
659  }
660 
661  // Do not do non-trivial unswitch while optimizing for size.
662  // FIXME: Use Function::optForSize().
663  if (OptimizeForSize ||
664  loopHeader->getParent()->hasFnAttribute(Attribute::OptimizeForSize))
665  return false;
666 
667  for (IntrinsicInst *Guard : Guards) {
668  Value *LoopCond =
669  FindLIVLoopCondition(Guard->getOperand(0), currentLoop, Changed).first;
670  if (LoopCond &&
671  UnswitchIfProfitable(LoopCond, ConstantInt::getTrue(Context))) {
672  // NB! Unswitching (if successful) could have erased some of the
673  // instructions in Guards leaving dangling pointers there. This is fine
674  // because we're returning now, and won't look at Guards again.
675  ++NumGuards;
676  return true;
677  }
678  }
679 
680  // Loop over all of the basic blocks in the loop. If we find an interior
681  // block that is branching on a loop-invariant condition, we can unswitch this
682  // loop.
683  for (Loop::block_iterator I = currentLoop->block_begin(),
684  E = currentLoop->block_end(); I != E; ++I) {
685  TerminatorInst *TI = (*I)->getTerminator();
686 
687  // Unswitching on a potentially uninitialized predicate is not
688  // MSan-friendly. Limit this to the cases when the original predicate is
689  // guaranteed to execute, to avoid creating a use-of-uninitialized-value
690  // in the code that did not have one.
691  // This is a workaround for the discrepancy between LLVM IR and MSan
692  // semantics. See PR28054 for more details.
693  if (SanitizeMemory &&
694  !isGuaranteedToExecute(*TI, DT, currentLoop, &SafetyInfo))
695  continue;
696 
697  if (BranchInst *BI = dyn_cast<BranchInst>(TI)) {
698  // Some branches may be rendered unreachable because of previous
699  // unswitching.
700  // Unswitch only those branches that are reachable.
701  if (isUnreachableDueToPreviousUnswitching(*I))
702  continue;
703 
704  // If this isn't branching on an invariant condition, we can't unswitch
705  // it.
706  if (BI->isConditional()) {
707  // See if this, or some part of it, is loop invariant. If so, we can
708  // unswitch on it if we desire.
709  Value *LoopCond = FindLIVLoopCondition(BI->getCondition(),
710  currentLoop, Changed).first;
711  if (!LoopCond || EqualityPropUnSafe(*LoopCond))
712  continue;
713 
714  if (UnswitchIfProfitable(LoopCond, ConstantInt::getTrue(Context), TI)) {
715  ++NumBranches;
716  return true;
717  }
718  }
719  } else if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
720  Value *SC = SI->getCondition();
721  Value *LoopCond;
722  OperatorChain OpChain;
723  std::tie(LoopCond, OpChain) =
724  FindLIVLoopCondition(SC, currentLoop, Changed);
725 
726  unsigned NumCases = SI->getNumCases();
727  if (LoopCond && NumCases) {
728  // Find a value to unswitch on:
729  // FIXME: this should chose the most expensive case!
730  // FIXME: scan for a case with a non-critical edge?
731  Constant *UnswitchVal = nullptr;
732  // Find a case value such that at least one case value is unswitched
733  // out.
734  if (OpChain == OC_OpChainAnd) {
735  // If the chain only has ANDs and the switch has a case value of 0.
736  // Dropping in a 0 to the chain will unswitch out the 0-casevalue.
737  auto *AllZero = cast<ConstantInt>(Constant::getNullValue(SC->getType()));
738  if (BranchesInfo.isUnswitched(SI, AllZero))
739  continue;
740  // We are unswitching 0 out.
741  UnswitchVal = AllZero;
742  } else if (OpChain == OC_OpChainOr) {
743  // If the chain only has ORs and the switch has a case value of ~0.
744  // Dropping in a ~0 to the chain will unswitch out the ~0-casevalue.
745  auto *AllOne = cast<ConstantInt>(Constant::getAllOnesValue(SC->getType()));
746  if (BranchesInfo.isUnswitched(SI, AllOne))
747  continue;
748  // We are unswitching ~0 out.
749  UnswitchVal = AllOne;
750  } else {
751  assert(OpChain == OC_OpChainNone &&
752  "Expect to unswitch on trivial chain");
753  // Do not process same value again and again.
754  // At this point we have some cases already unswitched and
755  // some not yet unswitched. Let's find the first not yet unswitched one.
756  for (auto Case : SI->cases()) {
757  Constant *UnswitchValCandidate = Case.getCaseValue();
758  if (!BranchesInfo.isUnswitched(SI, UnswitchValCandidate)) {
759  UnswitchVal = UnswitchValCandidate;
760  break;
761  }
762  }
763  }
764 
765  if (!UnswitchVal)
766  continue;
767 
768  if (UnswitchIfProfitable(LoopCond, UnswitchVal)) {
769  ++NumSwitches;
770  // In case of a full LIV, UnswitchVal is the value we unswitched out.
771  // In case of a partial LIV, we only unswitch when its an AND-chain
772  // or OR-chain. In both cases switch input value simplifies to
773  // UnswitchVal.
774  BranchesInfo.setUnswitched(SI, UnswitchVal);
775  return true;
776  }
777  }
778  }
779 
780  // Scan the instructions to check for unswitchable values.
781  for (BasicBlock::iterator BBI = (*I)->begin(), E = (*I)->end();
782  BBI != E; ++BBI)
783  if (SelectInst *SI = dyn_cast<SelectInst>(BBI)) {
784  Value *LoopCond = FindLIVLoopCondition(SI->getCondition(),
785  currentLoop, Changed).first;
786  if (LoopCond && UnswitchIfProfitable(LoopCond,
787  ConstantInt::getTrue(Context))) {
788  ++NumSelects;
789  return true;
790  }
791  }
792  }
793  return Changed;
794 }
795 
796 /// Check to see if all paths from BB exit the loop with no side effects
797 /// (including infinite loops).
798 ///
799 /// If true, we return true and set ExitBB to the block we
800 /// exit through.
801 ///
803  BasicBlock *&ExitBB,
804  std::set<BasicBlock*> &Visited) {
805  if (!Visited.insert(BB).second) {
806  // Already visited. Without more analysis, this could indicate an infinite
807  // loop.
808  return false;
809  }
810  if (!L->contains(BB)) {
811  // Otherwise, this is a loop exit, this is fine so long as this is the
812  // first exit.
813  if (ExitBB) return false;
814  ExitBB = BB;
815  return true;
816  }
817 
818  // Otherwise, this is an unvisited intra-loop node. Check all successors.
819  for (succ_iterator SI = succ_begin(BB), E = succ_end(BB); SI != E; ++SI) {
820  // Check to see if the successor is a trivial loop exit.
821  if (!isTrivialLoopExitBlockHelper(L, *SI, ExitBB, Visited))
822  return false;
823  }
824 
825  // Okay, everything after this looks good, check to make sure that this block
826  // doesn't include any side effects.
827  for (Instruction &I : *BB)
828  if (I.mayHaveSideEffects())
829  return false;
830 
831  return true;
832 }
833 
834 /// Return true if the specified block unconditionally leads to an exit from
835 /// the specified loop, and has no side-effects in the process. If so, return
836 /// the block that is exited to, otherwise return null.
838  std::set<BasicBlock*> Visited;
839  Visited.insert(L->getHeader()); // Branches to header make infinite loops.
840  BasicBlock *ExitBB = nullptr;
841  if (isTrivialLoopExitBlockHelper(L, BB, ExitBB, Visited))
842  return ExitBB;
843  return nullptr;
844 }
845 
846 /// We have found that we can unswitch currentLoop when LoopCond == Val to
847 /// simplify the loop. If we decide that this is profitable,
848 /// unswitch the loop, reprocess the pieces, then return true.
849 bool LoopUnswitch::UnswitchIfProfitable(Value *LoopCond, Constant *Val,
850  TerminatorInst *TI) {
851  // Check to see if it would be profitable to unswitch current loop.
852  if (!BranchesInfo.CostAllowsUnswitching()) {
853  DEBUG(dbgs() << "NOT unswitching loop %"
854  << currentLoop->getHeader()->getName()
855  << " at non-trivial condition '" << *Val
856  << "' == " << *LoopCond << "\n"
857  << ". Cost too high.\n");
858  return false;
859  }
860  if (hasBranchDivergence &&
861  getAnalysis<DivergenceAnalysis>().isDivergent(LoopCond)) {
862  DEBUG(dbgs() << "NOT unswitching loop %"
863  << currentLoop->getHeader()->getName()
864  << " at non-trivial condition '" << *Val
865  << "' == " << *LoopCond << "\n"
866  << ". Condition is divergent.\n");
867  return false;
868  }
869 
870  UnswitchNontrivialCondition(LoopCond, Val, currentLoop, TI);
871  return true;
872 }
873 
874 /// Recursively clone the specified loop and all of its children,
875 /// mapping the blocks with the specified map.
877  LoopInfo *LI, LPPassManager *LPM) {
878  Loop &New = *new Loop();
879  if (PL)
880  PL->addChildLoop(&New);
881  else
882  LI->addTopLevelLoop(&New);
883  LPM->addLoop(New);
884 
885  // Add all of the blocks in L to the new loop.
886  for (Loop::block_iterator I = L->block_begin(), E = L->block_end();
887  I != E; ++I)
888  if (LI->getLoopFor(*I) == L)
889  New.addBasicBlockToLoop(cast<BasicBlock>(VM[*I]), *LI);
890 
891  // Add all of the subloops to the new loop.
892  for (Loop *I : *L)
893  CloneLoop(I, &New, VM, LI, LPM);
894 
895  return &New;
896 }
897 
898 /// Emit a conditional branch on two values if LIC == Val, branch to TrueDst,
899 /// otherwise branch to FalseDest. Insert the code immediately before InsertPt.
900 void LoopUnswitch::EmitPreheaderBranchOnCondition(Value *LIC, Constant *Val,
901  BasicBlock *TrueDest,
902  BasicBlock *FalseDest,
903  Instruction *InsertPt,
904  TerminatorInst *TI) {
905  // Insert a conditional branch on LIC to the two preheaders. The original
906  // code is the true version and the new code is the false version.
907  Value *BranchVal = LIC;
908  bool Swapped = false;
909  if (!isa<ConstantInt>(Val) ||
910  Val->getType() != Type::getInt1Ty(LIC->getContext()))
911  BranchVal = new ICmpInst(InsertPt, ICmpInst::ICMP_EQ, LIC, Val);
912  else if (Val != ConstantInt::getTrue(Val->getContext())) {
913  // We want to enter the new loop when the condition is true.
914  std::swap(TrueDest, FalseDest);
915  Swapped = true;
916  }
917 
918  // Insert the new branch.
919  BranchInst *BI =
920  IRBuilder<>(InsertPt).CreateCondBr(BranchVal, TrueDest, FalseDest, TI);
921  if (Swapped)
922  BI->swapProfMetadata();
923 
924  // If either edge is critical, split it. This helps preserve LoopSimplify
925  // form for enclosing loops.
926  auto Options = CriticalEdgeSplittingOptions(DT, LI).setPreserveLCSSA();
927  SplitCriticalEdge(BI, 0, Options);
928  SplitCriticalEdge(BI, 1, Options);
929 }
930 
931 /// Given a loop that has a trivial unswitchable condition in it (a cond branch
932 /// from its header block to its latch block, where the path through the loop
933 /// that doesn't execute its body has no side-effects), unswitch it. This
934 /// doesn't involve any code duplication, just moving the conditional branch
935 /// outside of the loop and updating loop info.
936 void LoopUnswitch::UnswitchTrivialCondition(Loop *L, Value *Cond, Constant *Val,
937  BasicBlock *ExitBlock,
938  TerminatorInst *TI) {
939  DEBUG(dbgs() << "loop-unswitch: Trivial-Unswitch loop %"
940  << loopHeader->getName() << " [" << L->getBlocks().size()
941  << " blocks] in Function "
942  << L->getHeader()->getParent()->getName() << " on cond: " << *Val
943  << " == " << *Cond << "\n");
944 
945  // First step, split the preheader, so that we know that there is a safe place
946  // to insert the conditional branch. We will change loopPreheader to have a
947  // conditional branch on Cond.
948  BasicBlock *NewPH = SplitEdge(loopPreheader, loopHeader, DT, LI);
949 
950  // Now that we have a place to insert the conditional branch, create a place
951  // to branch to: this is the exit block out of the loop that we should
952  // short-circuit to.
953 
954  // Split this block now, so that the loop maintains its exit block, and so
955  // that the jump from the preheader can execute the contents of the exit block
956  // without actually branching to it (the exit block should be dominated by the
957  // loop header, not the preheader).
958  assert(!L->contains(ExitBlock) && "Exit block is in the loop?");
959  BasicBlock *NewExit = SplitBlock(ExitBlock, &ExitBlock->front(), DT, LI);
960 
961  // Okay, now we have a position to branch from and a position to branch to,
962  // insert the new conditional branch.
963  EmitPreheaderBranchOnCondition(Cond, Val, NewExit, NewPH,
964  loopPreheader->getTerminator(), TI);
965  LPM->deleteSimpleAnalysisValue(loopPreheader->getTerminator(), L);
966  loopPreheader->getTerminator()->eraseFromParent();
967 
968  // We need to reprocess this loop, it could be unswitched again.
969  redoLoop = true;
970 
971  // Now that we know that the loop is never entered when this condition is a
972  // particular value, rewrite the loop with this info. We know that this will
973  // at least eliminate the old branch.
974  RewriteLoopBodyWithConditionConstant(L, Cond, Val, false);
975  ++NumTrivial;
976 }
977 
978 /// Check if the first non-constant condition starting from the loop header is
979 /// a trivial unswitch condition: that is, a condition controls whether or not
980 /// the loop does anything at all. If it is a trivial condition, unswitching
981 /// produces no code duplications (equivalently, it produces a simpler loop and
982 /// a new empty loop, which gets deleted). Therefore always unswitch trivial
983 /// condition.
984 bool LoopUnswitch::TryTrivialLoopUnswitch(bool &Changed) {
985  BasicBlock *CurrentBB = currentLoop->getHeader();
986  TerminatorInst *CurrentTerm = CurrentBB->getTerminator();
987  LLVMContext &Context = CurrentBB->getContext();
988 
989  // If loop header has only one reachable successor (currently via an
990  // unconditional branch or constant foldable conditional branch, but
991  // should also consider adding constant foldable switch instruction in
992  // future), we should keep looking for trivial condition candidates in
993  // the successor as well. An alternative is to constant fold conditions
994  // and merge successors into loop header (then we only need to check header's
995  // terminator). The reason for not doing this in LoopUnswitch pass is that
996  // it could potentially break LoopPassManager's invariants. Folding dead
997  // branches could either eliminate the current loop or make other loops
998  // unreachable. LCSSA form might also not be preserved after deleting
999  // branches. The following code keeps traversing loop header's successors
1000  // until it finds the trivial condition candidate (condition that is not a
1001  // constant). Since unswitching generates branches with constant conditions,
1002  // this scenario could be very common in practice.
1003  SmallSet<BasicBlock*, 8> Visited;
1004 
1005  while (true) {
1006  // If we exit loop or reach a previous visited block, then
1007  // we can not reach any trivial condition candidates (unfoldable
1008  // branch instructions or switch instructions) and no unswitch
1009  // can happen. Exit and return false.
1010  if (!currentLoop->contains(CurrentBB) || !Visited.insert(CurrentBB).second)
1011  return false;
1012 
1013  // Check if this loop will execute any side-effecting instructions (e.g.
1014  // stores, calls, volatile loads) in the part of the loop that the code
1015  // *would* execute. Check the header first.
1016  for (Instruction &I : *CurrentBB)
1017  if (I.mayHaveSideEffects())
1018  return false;
1019 
1020  if (BranchInst *BI = dyn_cast<BranchInst>(CurrentTerm)) {
1021  if (BI->isUnconditional()) {
1022  CurrentBB = BI->getSuccessor(0);
1023  } else if (BI->getCondition() == ConstantInt::getTrue(Context)) {
1024  CurrentBB = BI->getSuccessor(0);
1025  } else if (BI->getCondition() == ConstantInt::getFalse(Context)) {
1026  CurrentBB = BI->getSuccessor(1);
1027  } else {
1028  // Found a trivial condition candidate: non-foldable conditional branch.
1029  break;
1030  }
1031  } else if (SwitchInst *SI = dyn_cast<SwitchInst>(CurrentTerm)) {
1032  // At this point, any constant-foldable instructions should have probably
1033  // been folded.
1034  ConstantInt *Cond = dyn_cast<ConstantInt>(SI->getCondition());
1035  if (!Cond)
1036  break;
1037  // Find the target block we are definitely going to.
1038  CurrentBB = SI->findCaseValue(Cond)->getCaseSuccessor();
1039  } else {
1040  // We do not understand these terminator instructions.
1041  break;
1042  }
1043 
1044  CurrentTerm = CurrentBB->getTerminator();
1045  }
1046 
1047  // CondVal is the condition that controls the trivial condition.
1048  // LoopExitBB is the BasicBlock that loop exits when meets trivial condition.
1049  Constant *CondVal = nullptr;
1050  BasicBlock *LoopExitBB = nullptr;
1051 
1052  if (BranchInst *BI = dyn_cast<BranchInst>(CurrentTerm)) {
1053  // If this isn't branching on an invariant condition, we can't unswitch it.
1054  if (!BI->isConditional())
1055  return false;
1056 
1057  Value *LoopCond = FindLIVLoopCondition(BI->getCondition(),
1058  currentLoop, Changed).first;
1059 
1060  // Unswitch only if the trivial condition itself is an LIV (not
1061  // partial LIV which could occur in and/or)
1062  if (!LoopCond || LoopCond != BI->getCondition())
1063  return false;
1064 
1065  // Check to see if a successor of the branch is guaranteed to
1066  // exit through a unique exit block without having any
1067  // side-effects. If so, determine the value of Cond that causes
1068  // it to do this.
1069  if ((LoopExitBB = isTrivialLoopExitBlock(currentLoop,
1070  BI->getSuccessor(0)))) {
1071  CondVal = ConstantInt::getTrue(Context);
1072  } else if ((LoopExitBB = isTrivialLoopExitBlock(currentLoop,
1073  BI->getSuccessor(1)))) {
1074  CondVal = ConstantInt::getFalse(Context);
1075  }
1076 
1077  // If we didn't find a single unique LoopExit block, or if the loop exit
1078  // block contains phi nodes, this isn't trivial.
1079  if (!LoopExitBB || isa<PHINode>(LoopExitBB->begin()))
1080  return false; // Can't handle this.
1081 
1082  if (EqualityPropUnSafe(*LoopCond))
1083  return false;
1084 
1085  UnswitchTrivialCondition(currentLoop, LoopCond, CondVal, LoopExitBB,
1086  CurrentTerm);
1087  ++NumBranches;
1088  return true;
1089  } else if (SwitchInst *SI = dyn_cast<SwitchInst>(CurrentTerm)) {
1090  // If this isn't switching on an invariant condition, we can't unswitch it.
1091  Value *LoopCond = FindLIVLoopCondition(SI->getCondition(),
1092  currentLoop, Changed).first;
1093 
1094  // Unswitch only if the trivial condition itself is an LIV (not
1095  // partial LIV which could occur in and/or)
1096  if (!LoopCond || LoopCond != SI->getCondition())
1097  return false;
1098 
1099  // Check to see if a successor of the switch is guaranteed to go to the
1100  // latch block or exit through a one exit block without having any
1101  // side-effects. If so, determine the value of Cond that causes it to do
1102  // this.
1103  // Note that we can't trivially unswitch on the default case or
1104  // on already unswitched cases.
1105  for (auto Case : SI->cases()) {
1106  BasicBlock *LoopExitCandidate;
1107  if ((LoopExitCandidate =
1108  isTrivialLoopExitBlock(currentLoop, Case.getCaseSuccessor()))) {
1109  // Okay, we found a trivial case, remember the value that is trivial.
1110  ConstantInt *CaseVal = Case.getCaseValue();
1111 
1112  // Check that it was not unswitched before, since already unswitched
1113  // trivial vals are looks trivial too.
1114  if (BranchesInfo.isUnswitched(SI, CaseVal))
1115  continue;
1116  LoopExitBB = LoopExitCandidate;
1117  CondVal = CaseVal;
1118  break;
1119  }
1120  }
1121 
1122  // If we didn't find a single unique LoopExit block, or if the loop exit
1123  // block contains phi nodes, this isn't trivial.
1124  if (!LoopExitBB || isa<PHINode>(LoopExitBB->begin()))
1125  return false; // Can't handle this.
1126 
1127  UnswitchTrivialCondition(currentLoop, LoopCond, CondVal, LoopExitBB,
1128  nullptr);
1129 
1130  // We are only unswitching full LIV.
1131  BranchesInfo.setUnswitched(SI, CondVal);
1132  ++NumSwitches;
1133  return true;
1134  }
1135  return false;
1136 }
1137 
1138 /// Split all of the edges from inside the loop to their exit blocks.
1139 /// Update the appropriate Phi nodes as we do so.
1140 void LoopUnswitch::SplitExitEdges(Loop *L,
1141  const SmallVectorImpl<BasicBlock *> &ExitBlocks){
1142 
1143  for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) {
1144  BasicBlock *ExitBlock = ExitBlocks[i];
1145  SmallVector<BasicBlock *, 4> Preds(pred_begin(ExitBlock),
1146  pred_end(ExitBlock));
1147 
1148  // Although SplitBlockPredecessors doesn't preserve loop-simplify in
1149  // general, if we call it on all predecessors of all exits then it does.
1150  SplitBlockPredecessors(ExitBlock, Preds, ".us-lcssa", DT, LI,
1151  /*PreserveLCSSA*/ true);
1152  }
1153 }
1154 
1155 /// We determined that the loop is profitable to unswitch when LIC equal Val.
1156 /// Split it into loop versions and test the condition outside of either loop.
1157 /// Return the loops created as Out1/Out2.
1158 void LoopUnswitch::UnswitchNontrivialCondition(Value *LIC, Constant *Val,
1159  Loop *L, TerminatorInst *TI) {
1160  Function *F = loopHeader->getParent();
1161  DEBUG(dbgs() << "loop-unswitch: Unswitching loop %"
1162  << loopHeader->getName() << " [" << L->getBlocks().size()
1163  << " blocks] in Function " << F->getName()
1164  << " when '" << *Val << "' == " << *LIC << "\n");
1165 
1166  if (auto *SEWP = getAnalysisIfAvailable<ScalarEvolutionWrapperPass>())
1167  SEWP->getSE().forgetLoop(L);
1168 
1169  LoopBlocks.clear();
1170  NewBlocks.clear();
1171 
1172  // First step, split the preheader and exit blocks, and add these blocks to
1173  // the LoopBlocks list.
1174  BasicBlock *NewPreheader = SplitEdge(loopPreheader, loopHeader, DT, LI);
1175  LoopBlocks.push_back(NewPreheader);
1176 
1177  // We want the loop to come after the preheader, but before the exit blocks.
1178  LoopBlocks.insert(LoopBlocks.end(), L->block_begin(), L->block_end());
1179 
1180  SmallVector<BasicBlock*, 8> ExitBlocks;
1181  L->getUniqueExitBlocks(ExitBlocks);
1182 
1183  // Split all of the edges from inside the loop to their exit blocks. Update
1184  // the appropriate Phi nodes as we do so.
1185  SplitExitEdges(L, ExitBlocks);
1186 
1187  // The exit blocks may have been changed due to edge splitting, recompute.
1188  ExitBlocks.clear();
1189  L->getUniqueExitBlocks(ExitBlocks);
1190 
1191  // Add exit blocks to the loop blocks.
1192  LoopBlocks.insert(LoopBlocks.end(), ExitBlocks.begin(), ExitBlocks.end());
1193 
1194  // Next step, clone all of the basic blocks that make up the loop (including
1195  // the loop preheader and exit blocks), keeping track of the mapping between
1196  // the instructions and blocks.
1197  NewBlocks.reserve(LoopBlocks.size());
1198  ValueToValueMapTy VMap;
1199  for (unsigned i = 0, e = LoopBlocks.size(); i != e; ++i) {
1200  BasicBlock *NewBB = CloneBasicBlock(LoopBlocks[i], VMap, ".us", F);
1201 
1202  NewBlocks.push_back(NewBB);
1203  VMap[LoopBlocks[i]] = NewBB; // Keep the BB mapping.
1204  LPM->cloneBasicBlockSimpleAnalysis(LoopBlocks[i], NewBB, L);
1205  }
1206 
1207  // Splice the newly inserted blocks into the function right before the
1208  // original preheader.
1209  F->getBasicBlockList().splice(NewPreheader->getIterator(),
1210  F->getBasicBlockList(),
1211  NewBlocks[0]->getIterator(), F->end());
1212 
1213  // Now we create the new Loop object for the versioned loop.
1214  Loop *NewLoop = CloneLoop(L, L->getParentLoop(), VMap, LI, LPM);
1215 
1216  // Recalculate unswitching quota, inherit simplified switches info for NewBB,
1217  // Probably clone more loop-unswitch related loop properties.
1218  BranchesInfo.cloneData(NewLoop, L, VMap);
1219 
1220  Loop *ParentLoop = L->getParentLoop();
1221  if (ParentLoop) {
1222  // Make sure to add the cloned preheader and exit blocks to the parent loop
1223  // as well.
1224  ParentLoop->addBasicBlockToLoop(NewBlocks[0], *LI);
1225  }
1226 
1227  for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) {
1228  BasicBlock *NewExit = cast<BasicBlock>(VMap[ExitBlocks[i]]);
1229  // The new exit block should be in the same loop as the old one.
1230  if (Loop *ExitBBLoop = LI->getLoopFor(ExitBlocks[i]))
1231  ExitBBLoop->addBasicBlockToLoop(NewExit, *LI);
1232 
1233  assert(NewExit->getTerminator()->getNumSuccessors() == 1 &&
1234  "Exit block should have been split to have one successor!");
1235  BasicBlock *ExitSucc = NewExit->getTerminator()->getSuccessor(0);
1236 
1237  // If the successor of the exit block had PHI nodes, add an entry for
1238  // NewExit.
1239  for (BasicBlock::iterator I = ExitSucc->begin();
1240  PHINode *PN = dyn_cast<PHINode>(I); ++I) {
1241  Value *V = PN->getIncomingValueForBlock(ExitBlocks[i]);
1242  ValueToValueMapTy::iterator It = VMap.find(V);
1243  if (It != VMap.end()) V = It->second;
1244  PN->addIncoming(V, NewExit);
1245  }
1246 
1247  if (LandingPadInst *LPad = NewExit->getLandingPadInst()) {
1248  PHINode *PN = PHINode::Create(LPad->getType(), 0, "",
1249  &*ExitSucc->getFirstInsertionPt());
1250 
1251  for (pred_iterator I = pred_begin(ExitSucc), E = pred_end(ExitSucc);
1252  I != E; ++I) {
1253  BasicBlock *BB = *I;
1254  LandingPadInst *LPI = BB->getLandingPadInst();
1255  LPI->replaceAllUsesWith(PN);
1256  PN->addIncoming(LPI, BB);
1257  }
1258  }
1259  }
1260 
1261  // Rewrite the code to refer to itself.
1262  for (unsigned i = 0, e = NewBlocks.size(); i != e; ++i) {
1263  for (Instruction &I : *NewBlocks[i]) {
1264  RemapInstruction(&I, VMap,
1266  if (auto *II = dyn_cast<IntrinsicInst>(&I))
1267  if (II->getIntrinsicID() == Intrinsic::assume)
1268  AC->registerAssumption(II);
1269  }
1270  }
1271 
1272  // Rewrite the original preheader to select between versions of the loop.
1273  BranchInst *OldBR = cast<BranchInst>(loopPreheader->getTerminator());
1274  assert(OldBR->isUnconditional() && OldBR->getSuccessor(0) == LoopBlocks[0] &&
1275  "Preheader splitting did not work correctly!");
1276 
1277  // Emit the new branch that selects between the two versions of this loop.
1278  EmitPreheaderBranchOnCondition(LIC, Val, NewBlocks[0], LoopBlocks[0], OldBR,
1279  TI);
1280  LPM->deleteSimpleAnalysisValue(OldBR, L);
1281  OldBR->eraseFromParent();
1282 
1283  LoopProcessWorklist.push_back(NewLoop);
1284  redoLoop = true;
1285 
1286  // Keep a WeakTrackingVH holding onto LIC. If the first call to
1287  // RewriteLoopBody
1288  // deletes the instruction (for example by simplifying a PHI that feeds into
1289  // the condition that we're unswitching on), we don't rewrite the second
1290  // iteration.
1291  WeakTrackingVH LICHandle(LIC);
1292 
1293  // Now we rewrite the original code to know that the condition is true and the
1294  // new code to know that the condition is false.
1295  RewriteLoopBodyWithConditionConstant(L, LIC, Val, false);
1296 
1297  // It's possible that simplifying one loop could cause the other to be
1298  // changed to another value or a constant. If its a constant, don't simplify
1299  // it.
1300  if (!LoopProcessWorklist.empty() && LoopProcessWorklist.back() == NewLoop &&
1301  LICHandle && !isa<Constant>(LICHandle))
1302  RewriteLoopBodyWithConditionConstant(NewLoop, LICHandle, Val, true);
1303 }
1304 
1305 /// Remove all instances of I from the worklist vector specified.
1307  std::vector<Instruction*> &Worklist) {
1308 
1309  Worklist.erase(std::remove(Worklist.begin(), Worklist.end(), I),
1310  Worklist.end());
1311 }
1312 
1313 /// When we find that I really equals V, remove I from the
1314 /// program, replacing all uses with V and update the worklist.
1316  std::vector<Instruction*> &Worklist,
1317  Loop *L, LPPassManager *LPM) {
1318  DEBUG(dbgs() << "Replace with '" << *V << "': " << *I << "\n");
1319 
1320  // Add uses to the worklist, which may be dead now.
1321  for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i)
1322  if (Instruction *Use = dyn_cast<Instruction>(I->getOperand(i)))
1323  Worklist.push_back(Use);
1324 
1325  // Add users to the worklist which may be simplified now.
1326  for (User *U : I->users())
1327  Worklist.push_back(cast<Instruction>(U));
1328  LPM->deleteSimpleAnalysisValue(I, L);
1329  RemoveFromWorklist(I, Worklist);
1330  I->replaceAllUsesWith(V);
1331  if (!I->mayHaveSideEffects())
1332  I->eraseFromParent();
1333  ++NumSimplify;
1334 }
1335 
1336 /// We know either that the value LIC has the value specified by Val in the
1337 /// specified loop, or we know it does NOT have that value.
1338 /// Rewrite any uses of LIC or of properties correlated to it.
1339 void LoopUnswitch::RewriteLoopBodyWithConditionConstant(Loop *L, Value *LIC,
1340  Constant *Val,
1341  bool IsEqual) {
1342  assert(!isa<Constant>(LIC) && "Why are we unswitching on a constant?");
1343 
1344  // FIXME: Support correlated properties, like:
1345  // for (...)
1346  // if (li1 < li2)
1347  // ...
1348  // if (li1 > li2)
1349  // ...
1350 
1351  // FOLD boolean conditions (X|LIC), (X&LIC). Fold conditional branches,
1352  // selects, switches.
1353  std::vector<Instruction*> Worklist;
1354  LLVMContext &Context = Val->getContext();
1355 
1356  // If we know that LIC == Val, or that LIC == NotVal, just replace uses of LIC
1357  // in the loop with the appropriate one directly.
1358  if (IsEqual || (isa<ConstantInt>(Val) &&
1359  Val->getType()->isIntegerTy(1))) {
1360  Value *Replacement;
1361  if (IsEqual)
1362  Replacement = Val;
1363  else
1364  Replacement = ConstantInt::get(Type::getInt1Ty(Val->getContext()),
1365  !cast<ConstantInt>(Val)->getZExtValue());
1366 
1367  for (User *U : LIC->users()) {
1368  Instruction *UI = dyn_cast<Instruction>(U);
1369  if (!UI || !L->contains(UI))
1370  continue;
1371  Worklist.push_back(UI);
1372  }
1373 
1374  for (Instruction *UI : Worklist)
1375  UI->replaceUsesOfWith(LIC, Replacement);
1376 
1377  SimplifyCode(Worklist, L);
1378  return;
1379  }
1380 
1381  // Otherwise, we don't know the precise value of LIC, but we do know that it
1382  // is certainly NOT "Val". As such, simplify any uses in the loop that we
1383  // can. This case occurs when we unswitch switch statements.
1384  for (User *U : LIC->users()) {
1385  Instruction *UI = dyn_cast<Instruction>(U);
1386  if (!UI || !L->contains(UI))
1387  continue;
1388 
1389  // At this point, we know LIC is definitely not Val. Try to use some simple
1390  // logic to simplify the user w.r.t. to the context.
1391  if (Value *Replacement = SimplifyInstructionWithNotEqual(UI, LIC, Val)) {
1392  if (LI->replacementPreservesLCSSAForm(UI, Replacement)) {
1393  // This in-loop instruction has been simplified w.r.t. its context,
1394  // i.e. LIC != Val, make sure we propagate its replacement value to
1395  // all its users.
1396  //
1397  // We can not yet delete UI, the LIC user, yet, because that would invalidate
1398  // the LIC->users() iterator !. However, we can make this instruction
1399  // dead by replacing all its users and push it onto the worklist so that
1400  // it can be properly deleted and its operands simplified.
1401  UI->replaceAllUsesWith(Replacement);
1402  }
1403  }
1404 
1405  // This is a LIC user, push it into the worklist so that SimplifyCode can
1406  // attempt to simplify it.
1407  Worklist.push_back(UI);
1408 
1409  // If we know that LIC is not Val, use this info to simplify code.
1410  SwitchInst *SI = dyn_cast<SwitchInst>(UI);
1411  if (!SI || !isa<ConstantInt>(Val)) continue;
1412 
1413  // NOTE: if a case value for the switch is unswitched out, we record it
1414  // after the unswitch finishes. We can not record it here as the switch
1415  // is not a direct user of the partial LIV.
1416  SwitchInst::CaseHandle DeadCase =
1417  *SI->findCaseValue(cast<ConstantInt>(Val));
1418  // Default case is live for multiple values.
1419  if (DeadCase == *SI->case_default())
1420  continue;
1421 
1422  // Found a dead case value. Don't remove PHI nodes in the
1423  // successor if they become single-entry, those PHI nodes may
1424  // be in the Users list.
1425 
1426  BasicBlock *Switch = SI->getParent();
1427  BasicBlock *SISucc = DeadCase.getCaseSuccessor();
1428  BasicBlock *Latch = L->getLoopLatch();
1429 
1430  if (!SI->findCaseDest(SISucc)) continue; // Edge is critical.
1431  // If the DeadCase successor dominates the loop latch, then the
1432  // transformation isn't safe since it will delete the sole predecessor edge
1433  // to the latch.
1434  if (Latch && DT->dominates(SISucc, Latch))
1435  continue;
1436 
1437  // FIXME: This is a hack. We need to keep the successor around
1438  // and hooked up so as to preserve the loop structure, because
1439  // trying to update it is complicated. So instead we preserve the
1440  // loop structure and put the block on a dead code path.
1441  SplitEdge(Switch, SISucc, DT, LI);
1442  // Compute the successors instead of relying on the return value
1443  // of SplitEdge, since it may have split the switch successor
1444  // after PHI nodes.
1445  BasicBlock *NewSISucc = DeadCase.getCaseSuccessor();
1446  BasicBlock *OldSISucc = *succ_begin(NewSISucc);
1447  // Create an "unreachable" destination.
1448  BasicBlock *Abort = BasicBlock::Create(Context, "us-unreachable",
1449  Switch->getParent(),
1450  OldSISucc);
1451  new UnreachableInst(Context, Abort);
1452  // Force the new case destination to branch to the "unreachable"
1453  // block while maintaining a (dead) CFG edge to the old block.
1454  NewSISucc->getTerminator()->eraseFromParent();
1455  BranchInst::Create(Abort, OldSISucc,
1456  ConstantInt::getTrue(Context), NewSISucc);
1457  // Release the PHI operands for this edge.
1458  for (BasicBlock::iterator II = NewSISucc->begin();
1459  PHINode *PN = dyn_cast<PHINode>(II); ++II)
1460  PN->setIncomingValue(PN->getBasicBlockIndex(Switch),
1461  UndefValue::get(PN->getType()));
1462  // Tell the domtree about the new block. We don't fully update the
1463  // domtree here -- instead we force it to do a full recomputation
1464  // after the pass is complete -- but we do need to inform it of
1465  // new blocks.
1466  DT->addNewBlock(Abort, NewSISucc);
1467  }
1468 
1469  SimplifyCode(Worklist, L);
1470 }
1471 
1472 /// Now that we have simplified some instructions in the loop, walk over it and
1473 /// constant prop, dce, and fold control flow where possible. Note that this is
1474 /// effectively a very simple loop-structure-aware optimizer. During processing
1475 /// of this loop, L could very well be deleted, so it must not be used.
1476 ///
1477 /// FIXME: When the loop optimizer is more mature, separate this out to a new
1478 /// pass.
1479 ///
1480 void LoopUnswitch::SimplifyCode(std::vector<Instruction*> &Worklist, Loop *L) {
1481  const DataLayout &DL = L->getHeader()->getModule()->getDataLayout();
1482  while (!Worklist.empty()) {
1483  Instruction *I = Worklist.back();
1484  Worklist.pop_back();
1485 
1486  // Simple DCE.
1487  if (isInstructionTriviallyDead(I)) {
1488  DEBUG(dbgs() << "Remove dead instruction '" << *I << "\n");
1489 
1490  // Add uses to the worklist, which may be dead now.
1491  for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i)
1492  if (Instruction *Use = dyn_cast<Instruction>(I->getOperand(i)))
1493  Worklist.push_back(Use);
1494  LPM->deleteSimpleAnalysisValue(I, L);
1495  RemoveFromWorklist(I, Worklist);
1496  I->eraseFromParent();
1497  ++NumSimplify;
1498  continue;
1499  }
1500 
1501  // See if instruction simplification can hack this up. This is common for
1502  // things like "select false, X, Y" after unswitching made the condition be
1503  // 'false'. TODO: update the domtree properly so we can pass it here.
1504  if (Value *V = SimplifyInstruction(I, DL))
1505  if (LI->replacementPreservesLCSSAForm(I, V)) {
1506  ReplaceUsesOfWith(I, V, Worklist, L, LPM);
1507  continue;
1508  }
1509 
1510  // Special case hacks that appear commonly in unswitched code.
1511  if (BranchInst *BI = dyn_cast<BranchInst>(I)) {
1512  if (BI->isUnconditional()) {
1513  // If BI's parent is the only pred of the successor, fold the two blocks
1514  // together.
1515  BasicBlock *Pred = BI->getParent();
1516  BasicBlock *Succ = BI->getSuccessor(0);
1517  BasicBlock *SinglePred = Succ->getSinglePredecessor();
1518  if (!SinglePred) continue; // Nothing to do.
1519  assert(SinglePred == Pred && "CFG broken");
1520 
1521  DEBUG(dbgs() << "Merging blocks: " << Pred->getName() << " <- "
1522  << Succ->getName() << "\n");
1523 
1524  // Resolve any single entry PHI nodes in Succ.
1525  while (PHINode *PN = dyn_cast<PHINode>(Succ->begin()))
1526  ReplaceUsesOfWith(PN, PN->getIncomingValue(0), Worklist, L, LPM);
1527 
1528  // If Succ has any successors with PHI nodes, update them to have
1529  // entries coming from Pred instead of Succ.
1530  Succ->replaceAllUsesWith(Pred);
1531 
1532  // Move all of the successor contents from Succ to Pred.
1533  Pred->getInstList().splice(BI->getIterator(), Succ->getInstList(),
1534  Succ->begin(), Succ->end());
1535  LPM->deleteSimpleAnalysisValue(BI, L);
1536  RemoveFromWorklist(BI, Worklist);
1537  BI->eraseFromParent();
1538 
1539  // Remove Succ from the loop tree.
1540  LI->removeBlock(Succ);
1541  LPM->deleteSimpleAnalysisValue(Succ, L);
1542  Succ->eraseFromParent();
1543  ++NumSimplify;
1544  continue;
1545  }
1546 
1547  continue;
1548  }
1549  }
1550 }
1551 
1552 /// Simple simplifications we can do given the information that Cond is
1553 /// definitely not equal to Val.
1554 Value *LoopUnswitch::SimplifyInstructionWithNotEqual(Instruction *Inst,
1555  Value *Invariant,
1556  Constant *Val) {
1557  // icmp eq cond, val -> false
1558  ICmpInst *CI = dyn_cast<ICmpInst>(Inst);
1559  if (CI && CI->isEquality()) {
1560  Value *Op0 = CI->getOperand(0);
1561  Value *Op1 = CI->getOperand(1);
1562  if ((Op0 == Invariant && Op1 == Val) || (Op0 == Val && Op1 == Invariant)) {
1563  LLVMContext &Ctx = Inst->getContext();
1564  if (CI->getPredicate() == CmpInst::ICMP_EQ)
1565  return ConstantInt::getFalse(Ctx);
1566  else
1567  return ConstantInt::getTrue(Ctx);
1568  }
1569  }
1570 
1571  // FIXME: there may be other opportunities, e.g. comparison with floating
1572  // point, or Invariant - Val != 0, etc.
1573  return nullptr;
1574 }
Pass interface - Implemented by all &#39;passes&#39;.
Definition: Pass.h:81
static void collectEphemeralValues(const Loop *L, AssumptionCache *AC, SmallPtrSetImpl< const Value *> &EphValues)
Collect a loop&#39;s ephemeral values (those used only by an assume or similar intrinsics in the loop)...
Definition: CodeMetrics.cpp:73
DomTreeNodeBase< NodeT > * getNode(NodeT *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
unsigned getNumCases() const
Return the number of &#39;cases&#39; in this switch instruction, excluding the default case.
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks &#39;this&#39; from the containing basic block and deletes it.
Definition: Instruction.cpp:69
void initializeLoopUnswitchPass(PassRegistry &)
A parsed version of the target data layout string in and methods for querying it. ...
Definition: DataLayout.h:109
static ConstantInt * getFalse(LLVMContext &Context)
Definition: Constants.cpp:523
static IntegerType * getInt1Ty(LLVMContext &C)
Definition: Type.cpp:173
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
BlockT * getLoopLatch() const
If there is a single latch block for this loop, return it.
Definition: LoopInfoImpl.h:149
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
iterator_range< CaseIt > cases()
Iteration adapter for range-for loops.
LLVMContext & Context
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
BasicBlock * SplitBlock(BasicBlock *Old, Instruction *SplitPt, DominatorTree *DT=nullptr, LoopInfo *LI=nullptr)
Split the specified block at the specified instruction - everything before SplitPt stays in Old and e...
This is the interface for a simple mod/ref and alias analysis over globals.
BasicBlock * getSuccessor(unsigned idx) const
Return the specified successor.
LLVM_ATTRIBUTE_ALWAYS_INLINE size_type size() const
Definition: SmallVector.h:136
OperatorChain
Operator chain lattice.
iterator end()
Definition: Function.h:582
std::error_code remove(const Twine &path, bool IgnoreNonExisting=true)
Remove path.
bool isLCSSAForm(DominatorTree &DT) const
Return true if the Loop is in LCSSA form.
Definition: LoopInfo.cpp:174
BlockT * getLoopPreheader() const
If there is a preheader for this loop, return it.
Definition: LoopInfoImpl.h:101
An immutable pass that tracks lazily created AssumptionCache objects.
Value * getCondition() const
loop Unswitch loops
A cache of .assume calls within a function.
LLVMContext & getContext() const
All values hold a context through their type.
Definition: Value.cpp:697
bool makeLoopInvariant(Value *V, bool &Changed, Instruction *InsertPt=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:65
bool hasFnAttribute(Attribute::AttrKind Kind) const
Return true if the function has the attribute.
Definition: Function.h:254
const std::vector< BlockT * > & getBlocks() const
Get a list of the basic blocks which make up this loop.
Definition: LoopInfo.h:140
static bool isEquality(Predicate P)
Return true if this predicate is either EQ or NE.
BasicBlock * getSuccessor(unsigned i) const
STATISTIC(NumFunctions, "Total number of functions")
Value * getCondition() const
bool isVectorTy() const
True if this is an instance of VectorType.
Definition: Type.h:227
There are only ANDs.
bool notDuplicatable
True if this function cannot be duplicated.
Definition: CodeMetrics.h:54
LLVMContext & getContext() const
Get the context in which this basic block lives.
Definition: BasicBlock.cpp:33
ConstantInt * findCaseDest(BasicBlock *BB)
Finds the unique case value for a given successor.
static Constant * getNullValue(Type *Ty)
Constructor to create a &#39;0&#39; constant of arbitrary type.
Definition: Constants.cpp:207
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:252
std::vector< BasicBlock *>::const_iterator block_iterator
Definition: LoopInfo.h:141
AnalysisUsage & addRequired()
const Module * getModule() const
Return the module owning the function this basic block belongs to, or nullptr it the function does no...
Definition: BasicBlock.cpp:116
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:51
static void ReplaceUsesOfWith(Instruction *I, Value *V, std::vector< Instruction *> &Worklist, Loop *L, LPPassManager *LPM)
When we find that I really equals V, remove I from the program, replacing all uses with V and update ...
static Loop * CloneLoop(Loop *L, Loop *PL, ValueToValueMapTy &VM, LoopInfo *LI, LPPassManager *LPM)
Recursively clone the specified loop and all of its children, mapping the blocks with the specified m...
This class represents the LLVM &#39;select&#39; instruction.
const DataLayout & getDataLayout() const
Get the data layout for the module&#39;s target platform.
Definition: Module.cpp:361
Option class for critical edge splitting.
int getBasicBlockIndex(const BasicBlock *BB) const
Return the first index of the specified basic block in the value list for this PHI.
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
Definition: LoopInfo.h:585
A Use represents the edge between a Value definition and its users.
Definition: Use.h:56
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:42
bool isIntegerTy() const
True if this is an instance of IntegerType.
Definition: Type.h:197
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Definition: IRBuilder.h:664
BlockT * getHeader() const
Definition: LoopInfo.h:103
Interval::succ_iterator succ_begin(Interval *I)
succ_begin/succ_end - define methods so that Intervals may be used just like BasicBlocks can with the...
Definition: Interval.h:103
There are ANDs and ORs.
void computeLoopSafetyInfo(LoopSafetyInfo *, Loop *)
Computes safety information for a loop checks loop body & header for the possibility of may throw exc...
Definition: LICM.cpp:496
bool hasDedicatedExits() const
Return true if no exit block for the loop has a predecessor that is outside the loop.
Definition: LoopInfo.cpp:347
#define F(x, y, z)
Definition: MD5.cpp:55
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:245
Value handle that is nullable, but tries to track the Value.
Definition: ValueHandle.h:182
static bool isEqual(const Function &Caller, const Function &Callee)
void addBasicBlockToLoop(BlockT *NewBB, LoopInfoBase< BlockT, LoopT > &LI)
This method is used by other analyses to update loop information.
Definition: LoopInfoImpl.h:174
void addTopLevelLoop(LoopT *New)
This adds the specified loop to the collection of top-level loops.
Definition: LoopInfo.h:639
iterator find(const KeyT &Val)
Definition: ValueMap.h:158
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:428
ValueT lookup(const KeyT &Val) const
lookup - Return the entry for the specified key, or a default constructed value if no such entry exis...
Definition: ValueMap.h:167
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:134
int Switch(int a)
Definition: Switch2Test.cpp:11
Value * getOperand(unsigned i) const
Definition: User.h:154
If this flag is set, the remapper knows that only local values within a function (such as an instruct...
Definition: ValueMapper.h:65
void getUniqueExitBlocks(SmallVectorImpl< BasicBlock *> &ExitBlocks) const
Return all unique successor blocks of this loop.
Definition: LoopInfo.cpp:361
Interval::succ_iterator succ_end(Interval *I)
Definition: Interval.h:106
void replaceUsesOfWith(Value *From, Value *To)
Replace uses of one Value with another.
Definition: User.cpp:22
static Value * FindLIVLoopCondition(Value *Cond, Loop *L, bool &Changed, OperatorChain &ParentChain, DenseMap< Value *, Value *> &Cache)
Cond is a condition that occurs in L.
BasicBlock * SplitCriticalEdge(TerminatorInst *TI, unsigned SuccNum, const CriticalEdgeSplittingOptions &Options=CriticalEdgeSplittingOptions())
If this edge is a critical edge, insert a new node to split the critical edge.
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:404
The landingpad instruction holds all of the information necessary to generate correct exception handl...
Subclasses of this class are all able to terminate a basic block.
Definition: InstrTypes.h:54
Wrapper pass for TargetTransformInfo.
* if(!EatIfPresent(lltok::kw_thread_local)) return false
ParseOptionalThreadLocal := /*empty.
const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
Definition: BasicBlock.cpp:217
LLVM Basic Block Representation.
Definition: BasicBlock.h:59
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:68
Conditional or Unconditional Branch instruction.
This function has undefined behavior.
DomTreeNodeBase * getIDom() const
This is an important base class in LLVM.
Definition: Constant.h:42
LLVM_ATTRIBUTE_ALWAYS_INLINE iterator begin()
Definition: SmallVector.h:116
Value * getIncomingValueForBlock(const BasicBlock *BB) const
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
Definition: SmallSet.h:36
This file contains the declarations for the subclasses of Constant, which represent the different fla...
static void RemoveFromWorklist(Instruction *I, std::vector< Instruction *> &Worklist)
Remove all instances of I from the worklist vector specified.
const Instruction & front() const
Definition: BasicBlock.h:264
Machine Trace Metrics
bool mayHaveSideEffects() const
Return true if the instruction may have side effects.
Definition: Instruction.h:500
Interval::pred_iterator pred_begin(Interval *I)
pred_begin/pred_end - define methods so that Intervals may be used just like BasicBlocks can with the...
Definition: Interval.h:113
Represent the analysis usage information of a pass.
void analyzeBasicBlock(const BasicBlock *BB, const TargetTransformInfo &TTI, const SmallPtrSetImpl< const Value *> &EphValues)
Add information about a block to the current state.
void splice(iterator where, iplist_impl &L2)
Definition: ilist.h:342
static bool isTrivialLoopExitBlockHelper(Loop *L, BasicBlock *BB, BasicBlock *&ExitBB, std::set< BasicBlock *> &Visited)
Check to see if all paths from BB exit the loop with no side effects (including infinite loops)...
This instruction compares its operands according to the predicate given to the constructor.
Interval::pred_iterator pred_end(Interval *I)
Definition: Interval.h:116
BasicBlock * SplitBlockPredecessors(BasicBlock *BB, ArrayRef< BasicBlock *> Preds, const char *Suffix, DominatorTree *DT=nullptr, LoopInfo *LI=nullptr, bool PreserveLCSSA=false)
This method introduces at least one new basic block into the function and moves some of the predecess...
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
Definition: BasicBlock.h:101
self_iterator getIterator()
Definition: ilist_node.h:82
std::pair< NoneType, bool > insert(const T &V)
insert - Insert an element into the set if it isn&#39;t already there.
Definition: SmallSet.h:81
static bool EqualityPropUnSafe(Value &LoopCond)
FIXME: Remove this workaround when freeze related patches are done.
INITIALIZE_PASS_BEGIN(LoopUnswitch, "loop-unswitch", "Unswitch loops", false, false) INITIALIZE_PASS_END(LoopUnswitch
static Constant * getAllOnesValue(Type *Ty)
Get the all ones value.
Definition: Constants.cpp:261
static UndefValue * get(Type *T)
Static factory methods - Return an &#39;undef&#39; object of the specified type.
Definition: Constants.cpp:1320
loop unswitch
void swapProfMetadata()
If the instruction has "branch_weights" MD_prof metadata and the MDNode has three operands (including...
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
unsigned first
iterator end()
Definition: ValueMap.h:138
void deleteSimpleAnalysisValue(Value *V, Loop *L)
deleteSimpleAnalysisValue - Invoke deleteAnalysisValue hook for all passes that implement simple anal...
Definition: LoopPass.cpp:106
const InstListType & getInstList() const
Return the underlying instruction list container.
Definition: BasicBlock.h:317
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
Definition: LoopInfo.h:110
Iterator for intrusive lists based on ilist_node.
unsigned getNumOperands() const
Definition: User.h:176
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
Definition: SmallPtrSet.h:423
#define E
Definition: LargeTest.cpp:27
This is the shared class of boolean and integer constants.
Definition: Constants.h:84
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
There is no operator.
iterator end()
Definition: BasicBlock.h:254
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:864
bool dominates(const Instruction *Def, const Use &U) const
Return true if Def dominates a use in User.
Definition: Dominators.cpp:234
Module.h This file contains the declarations for the Module class.
Utility to calculate the size and a few similar metrics for a set of basic blocks.
Definition: CodeMetrics.h:42
CriticalEdgeSplittingOptions & setPreserveLCSSA()
CHAIN = SC CHAIN, Imm128 - System call.
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:560
static BranchInst * Create(BasicBlock *IfTrue, Instruction *InsertBefore=nullptr)
bool isConditional() const
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...
CaseIt findCaseValue(const ConstantInt *C)
Search all of the case values for the specified constant.
static ConstantInt * getTrue(LLVMContext &Context)
Definition: Constants.cpp:516
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:923
void push_back(pointer val)
Definition: ilist.h:326
BasicBlock * CloneBasicBlock(const BasicBlock *BB, ValueToValueMapTy &VMap, const Twine &NameSuffix="", Function *F=nullptr, ClonedCodeInfo *CodeInfo=nullptr, DebugInfoFinder *DIFinder=nullptr)
CloneBasicBlock - Return a copy of the specified basic block, but without embedding the block into a ...
Pass * createLoopUnswitchPass(bool OptimizeForSize=false, bool hasBranchDivergence=false)
iterator_range< user_iterator > users()
Definition: Value.h:395
void RemapInstruction(Instruction *I, ValueToValueMapTy &VM, RemapFlags Flags=RF_None, ValueMapTypeRemapper *TypeMapper=nullptr, ValueMaterializer *Materializer=nullptr)
Convert the instruction operands from referencing the current values into those specified by VM...
Definition: ValueMapper.h:243
static cl::opt< unsigned > Threshold("loop-unswitch-threshold", cl::desc("Max loop size to unswitch"), cl::init(100), cl::Hidden)
If this flag is set, the remapper ignores missing function-local entries (Argument, Instruction, BasicBlock) that are not in the value map.
Definition: ValueMapper.h:83
void recalculate(FT &F)
recalculate - compute a dominator tree for the given function
LoopT * getParentLoop() const
Definition: LoopInfo.h:104
Predicate getPredicate() const
Return the predicate for this instruction.
Definition: InstrTypes.h:934
LLVM_ATTRIBUTE_ALWAYS_INLINE iterator end()
Definition: SmallVector.h:120
Captures loop safety information.
Definition: LoopUtils.h:50
void registerAssumption(CallInst *CI)
Add an .assume intrinsic to this function&#39;s cache.
void addChildLoop(LoopT *NewChild)
Add the specified loop to be a child of this loop.
Definition: LoopInfo.h:271
void cloneBasicBlockSimpleAnalysis(BasicBlock *From, BasicBlock *To, Loop *L)
SimpleAnalysis - Provides simple interface to update analysis info maintained by various passes...
Definition: LoopPass.cpp:97
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:360
StringRef getName() const
Return a constant reference to the value&#39;s name.
Definition: Value.cpp:218
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:108
SymbolTableList< BasicBlock >::iterator eraseFromParent()
Unlink &#39;this&#39; from the containing function and delete it.
Definition: BasicBlock.cpp:97
#define I(x, y, z)
Definition: MD5.cpp:58
DomTreeNodeBase< NodeT > * addNewBlock(NodeT *BB, NodeT *DomBB)
Add a new node to the dominator tree information.
void addLoop(Loop &L)
Definition: LoopPass.cpp:77
BasicBlockT * getCaseSuccessor() const
Resolves successor for current case.
void getLoopAnalysisUsage(AnalysisUsage &AU)
Helper to consistently add the set of standard passes to a loop pass&#39;s AnalysisUsage.
Definition: LoopUtils.cpp:1022
LLVM_NODISCARD std::enable_if<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type >::type dyn_cast(const Y &Val)
Definition: Casting.h:323
const BasicBlockListType & getBasicBlockList() const
Get the underlying elements of the Function...
Definition: Function.h:557
block_iterator block_end() const
Definition: LoopInfo.h:143
bool isSafeToClone() const
Return true if the loop body is safe to clone in practice.
Definition: LoopInfo.cpp:197
CaseIt case_default()
Returns an iterator that points to the default case.
bool isUnconditional() const
Multiway switch.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
unsigned getNumSuccessors() const
Return the number of successors that this terminator has.
bool isInstructionTriviallyDead(Instruction *I, const TargetLibraryInfo *TLI=nullptr)
Return true if the result produced by the instruction is not used, and the instruction has no side ef...
Definition: Local.cpp:293
LLVM Value Representation.
Definition: Value.h:73
There are only ORs.
#define DEBUG(X)
Definition: Debug.h:118
BasicBlock * SplitEdge(BasicBlock *From, BasicBlock *To, DominatorTree *DT=nullptr, LoopInfo *LI=nullptr)
Split the edge connecting specified block.
const LandingPadInst * getLandingPadInst() const
Return the landingpad instruction associated with the landing pad.
Definition: BasicBlock.cpp:447
bool replacementPreservesLCSSAForm(Instruction *From, Value *To)
Returns true if replacing From with To everywhere is guaranteed to preserve LCSSA form...
Definition: LoopInfo.h:709
This pass exposes codegen information to IR-level passes.
const TerminatorInst * 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:120
void setIncomingValue(unsigned i, Value *V)
unsigned NumInsts
Number of instructions in the analyzed blocks.
Definition: CodeMetrics.h:63
iterator_range< block_iterator > blocks() const
Definition: LoopInfo.h:144
bool isGuaranteedToExecute(const Instruction &Inst, const DominatorTree *DT, const Loop *CurLoop, const LoopSafetyInfo *SafetyInfo)
Returns true if the instruction in a loop is guaranteed to execute at least once. ...
Definition: LoopUtils.cpp:1120
static BasicBlock * isTrivialLoopExitBlock(Loop *L, BasicBlock *BB)
Return true if the specified block unconditionally leads to an exit from the specified loop...
block_iterator block_begin() const
Definition: LoopInfo.h:142
Value * SimplifyInstruction(Instruction *I, const SimplifyQuery &Q, OptimizationRemarkEmitter *ORE=nullptr)
See if we can compute a simplified version of this instruction.
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:647
A wrapper class for inspecting calls to intrinsic functions.
Definition: IntrinsicInst.h:44
const BasicBlock * getParent() const
Definition: Instruction.h:66