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