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