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/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  assert(TrueDest != FalseDest && "Branch targets should be different");
914  // Insert a conditional branch on LIC to the two preheaders. The original
915  // code is the true version and the new code is the false version.
916  Value *BranchVal = LIC;
917  bool Swapped = false;
918  if (!isa<ConstantInt>(Val) ||
919  Val->getType() != Type::getInt1Ty(LIC->getContext()))
920  BranchVal = new ICmpInst(OldBranch, ICmpInst::ICMP_EQ, LIC, Val);
921  else if (Val != ConstantInt::getTrue(Val->getContext())) {
922  // We want to enter the new loop when the condition is true.
923  std::swap(TrueDest, FalseDest);
924  Swapped = true;
925  }
926 
927  // Old branch will be removed, so save its parent and successor to update the
928  // DomTree.
929  auto *OldBranchSucc = OldBranch->getSuccessor(0);
930  auto *OldBranchParent = OldBranch->getParent();
931 
932  // Insert the new branch.
933  BranchInst *BI =
934  IRBuilder<>(OldBranch).CreateCondBr(BranchVal, TrueDest, FalseDest, TI);
935  if (Swapped)
936  BI->swapProfMetadata();
937 
938  // Remove the old branch so there is only one branch at the end. This is
939  // needed to perform DomTree's internal DFS walk on the function's CFG.
940  OldBranch->removeFromParent();
941 
942  // Inform the DT about the new branch.
943  if (DT) {
944  // First, add both successors.
946  if (TrueDest != OldBranchSucc)
947  Updates.push_back({DominatorTree::Insert, OldBranchParent, TrueDest});
948  if (FalseDest != OldBranchSucc)
949  Updates.push_back({DominatorTree::Insert, OldBranchParent, FalseDest});
950  // If both of the new successors are different from the old one, inform the
951  // DT that the edge was deleted.
952  if (OldBranchSucc != TrueDest && OldBranchSucc != FalseDest) {
953  Updates.push_back({DominatorTree::Delete, OldBranchParent, OldBranchSucc});
954  }
955 
956  DT->applyUpdates(Updates);
957  }
958 
959  // If either edge is critical, split it. This helps preserve LoopSimplify
960  // form for enclosing loops.
961  auto Options = CriticalEdgeSplittingOptions(DT, LI).setPreserveLCSSA();
962  SplitCriticalEdge(BI, 0, Options);
963  SplitCriticalEdge(BI, 1, Options);
964 }
965 
966 /// Given a loop that has a trivial unswitchable condition in it (a cond branch
967 /// from its header block to its latch block, where the path through the loop
968 /// that doesn't execute its body has no side-effects), unswitch it. This
969 /// doesn't involve any code duplication, just moving the conditional branch
970 /// outside of the loop and updating loop info.
971 void LoopUnswitch::UnswitchTrivialCondition(Loop *L, Value *Cond, Constant *Val,
972  BasicBlock *ExitBlock,
973  TerminatorInst *TI) {
974  LLVM_DEBUG(dbgs() << "loop-unswitch: Trivial-Unswitch loop %"
975  << loopHeader->getName() << " [" << L->getBlocks().size()
976  << " blocks] in Function "
977  << L->getHeader()->getParent()->getName()
978  << " on cond: " << *Val << " == " << *Cond << "\n");
979  // We are going to make essential changes to CFG. This may invalidate cached
980  // information for L or one of its parent loops in SCEV.
981  if (auto *SEWP = getAnalysisIfAvailable<ScalarEvolutionWrapperPass>())
982  SEWP->getSE().forgetTopmostLoop(L);
983 
984  // First step, split the preheader, so that we know that there is a safe place
985  // to insert the conditional branch. We will change loopPreheader to have a
986  // conditional branch on Cond.
987  BasicBlock *NewPH = SplitEdge(loopPreheader, loopHeader, DT, LI);
988 
989  // Now that we have a place to insert the conditional branch, create a place
990  // to branch to: this is the exit block out of the loop that we should
991  // short-circuit to.
992 
993  // Split this block now, so that the loop maintains its exit block, and so
994  // that the jump from the preheader can execute the contents of the exit block
995  // without actually branching to it (the exit block should be dominated by the
996  // loop header, not the preheader).
997  assert(!L->contains(ExitBlock) && "Exit block is in the loop?");
998  BasicBlock *NewExit = SplitBlock(ExitBlock, &ExitBlock->front(), DT, LI);
999 
1000  // Okay, now we have a position to branch from and a position to branch to,
1001  // insert the new conditional branch.
1002  auto *OldBranch = dyn_cast<BranchInst>(loopPreheader->getTerminator());
1003  assert(OldBranch && "Failed to split the preheader");
1004  EmitPreheaderBranchOnCondition(Cond, Val, NewExit, NewPH, OldBranch, TI);
1005  LPM->deleteSimpleAnalysisValue(OldBranch, L);
1006 
1007  // EmitPreheaderBranchOnCondition removed the OldBranch from the function.
1008  // Delete it, as it is no longer needed.
1009  delete OldBranch;
1010 
1011  // We need to reprocess this loop, it could be unswitched again.
1012  redoLoop = true;
1013 
1014  // Now that we know that the loop is never entered when this condition is a
1015  // particular value, rewrite the loop with this info. We know that this will
1016  // at least eliminate the old branch.
1017  RewriteLoopBodyWithConditionConstant(L, Cond, Val, false);
1018  ++NumTrivial;
1019 }
1020 
1021 /// Check if the first non-constant condition starting from the loop header is
1022 /// a trivial unswitch condition: that is, a condition controls whether or not
1023 /// the loop does anything at all. If it is a trivial condition, unswitching
1024 /// produces no code duplications (equivalently, it produces a simpler loop and
1025 /// a new empty loop, which gets deleted). Therefore always unswitch trivial
1026 /// condition.
1027 bool LoopUnswitch::TryTrivialLoopUnswitch(bool &Changed) {
1028  BasicBlock *CurrentBB = currentLoop->getHeader();
1029  TerminatorInst *CurrentTerm = CurrentBB->getTerminator();
1030  LLVMContext &Context = CurrentBB->getContext();
1031 
1032  // If loop header has only one reachable successor (currently via an
1033  // unconditional branch or constant foldable conditional branch, but
1034  // should also consider adding constant foldable switch instruction in
1035  // future), we should keep looking for trivial condition candidates in
1036  // the successor as well. An alternative is to constant fold conditions
1037  // and merge successors into loop header (then we only need to check header's
1038  // terminator). The reason for not doing this in LoopUnswitch pass is that
1039  // it could potentially break LoopPassManager's invariants. Folding dead
1040  // branches could either eliminate the current loop or make other loops
1041  // unreachable. LCSSA form might also not be preserved after deleting
1042  // branches. The following code keeps traversing loop header's successors
1043  // until it finds the trivial condition candidate (condition that is not a
1044  // constant). Since unswitching generates branches with constant conditions,
1045  // this scenario could be very common in practice.
1047 
1048  while (true) {
1049  // If we exit loop or reach a previous visited block, then
1050  // we can not reach any trivial condition candidates (unfoldable
1051  // branch instructions or switch instructions) and no unswitch
1052  // can happen. Exit and return false.
1053  if (!currentLoop->contains(CurrentBB) || !Visited.insert(CurrentBB).second)
1054  return false;
1055 
1056  // Check if this loop will execute any side-effecting instructions (e.g.
1057  // stores, calls, volatile loads) in the part of the loop that the code
1058  // *would* execute. Check the header first.
1059  for (Instruction &I : *CurrentBB)
1060  if (I.mayHaveSideEffects())
1061  return false;
1062 
1063  if (BranchInst *BI = dyn_cast<BranchInst>(CurrentTerm)) {
1064  if (BI->isUnconditional()) {
1065  CurrentBB = BI->getSuccessor(0);
1066  } else if (BI->getCondition() == ConstantInt::getTrue(Context)) {
1067  CurrentBB = BI->getSuccessor(0);
1068  } else if (BI->getCondition() == ConstantInt::getFalse(Context)) {
1069  CurrentBB = BI->getSuccessor(1);
1070  } else {
1071  // Found a trivial condition candidate: non-foldable conditional branch.
1072  break;
1073  }
1074  } else if (SwitchInst *SI = dyn_cast<SwitchInst>(CurrentTerm)) {
1075  // At this point, any constant-foldable instructions should have probably
1076  // been folded.
1077  ConstantInt *Cond = dyn_cast<ConstantInt>(SI->getCondition());
1078  if (!Cond)
1079  break;
1080  // Find the target block we are definitely going to.
1081  CurrentBB = SI->findCaseValue(Cond)->getCaseSuccessor();
1082  } else {
1083  // We do not understand these terminator instructions.
1084  break;
1085  }
1086 
1087  CurrentTerm = CurrentBB->getTerminator();
1088  }
1089 
1090  // CondVal is the condition that controls the trivial condition.
1091  // LoopExitBB is the BasicBlock that loop exits when meets trivial condition.
1092  Constant *CondVal = nullptr;
1093  BasicBlock *LoopExitBB = nullptr;
1094 
1095  if (BranchInst *BI = dyn_cast<BranchInst>(CurrentTerm)) {
1096  // If this isn't branching on an invariant condition, we can't unswitch it.
1097  if (!BI->isConditional())
1098  return false;
1099 
1100  Value *LoopCond = FindLIVLoopCondition(BI->getCondition(),
1101  currentLoop, Changed).first;
1102 
1103  // Unswitch only if the trivial condition itself is an LIV (not
1104  // partial LIV which could occur in and/or)
1105  if (!LoopCond || LoopCond != BI->getCondition())
1106  return false;
1107 
1108  // Check to see if a successor of the branch is guaranteed to
1109  // exit through a unique exit block without having any
1110  // side-effects. If so, determine the value of Cond that causes
1111  // it to do this.
1112  if ((LoopExitBB = isTrivialLoopExitBlock(currentLoop,
1113  BI->getSuccessor(0)))) {
1114  CondVal = ConstantInt::getTrue(Context);
1115  } else if ((LoopExitBB = isTrivialLoopExitBlock(currentLoop,
1116  BI->getSuccessor(1)))) {
1117  CondVal = ConstantInt::getFalse(Context);
1118  }
1119 
1120  // If we didn't find a single unique LoopExit block, or if the loop exit
1121  // block contains phi nodes, this isn't trivial.
1122  if (!LoopExitBB || isa<PHINode>(LoopExitBB->begin()))
1123  return false; // Can't handle this.
1124 
1125  if (EqualityPropUnSafe(*LoopCond))
1126  return false;
1127 
1128  UnswitchTrivialCondition(currentLoop, LoopCond, CondVal, LoopExitBB,
1129  CurrentTerm);
1130  ++NumBranches;
1131  return true;
1132  } else if (SwitchInst *SI = dyn_cast<SwitchInst>(CurrentTerm)) {
1133  // If this isn't switching on an invariant condition, we can't unswitch it.
1134  Value *LoopCond = FindLIVLoopCondition(SI->getCondition(),
1135  currentLoop, Changed).first;
1136 
1137  // Unswitch only if the trivial condition itself is an LIV (not
1138  // partial LIV which could occur in and/or)
1139  if (!LoopCond || LoopCond != SI->getCondition())
1140  return false;
1141 
1142  // Check to see if a successor of the switch is guaranteed to go to the
1143  // latch block or exit through a one exit block without having any
1144  // side-effects. If so, determine the value of Cond that causes it to do
1145  // this.
1146  // Note that we can't trivially unswitch on the default case or
1147  // on already unswitched cases.
1148  for (auto Case : SI->cases()) {
1149  BasicBlock *LoopExitCandidate;
1150  if ((LoopExitCandidate =
1151  isTrivialLoopExitBlock(currentLoop, Case.getCaseSuccessor()))) {
1152  // Okay, we found a trivial case, remember the value that is trivial.
1153  ConstantInt *CaseVal = Case.getCaseValue();
1154 
1155  // Check that it was not unswitched before, since already unswitched
1156  // trivial vals are looks trivial too.
1157  if (BranchesInfo.isUnswitched(SI, CaseVal))
1158  continue;
1159  LoopExitBB = LoopExitCandidate;
1160  CondVal = CaseVal;
1161  break;
1162  }
1163  }
1164 
1165  // If we didn't find a single unique LoopExit block, or if the loop exit
1166  // block contains phi nodes, this isn't trivial.
1167  if (!LoopExitBB || isa<PHINode>(LoopExitBB->begin()))
1168  return false; // Can't handle this.
1169 
1170  UnswitchTrivialCondition(currentLoop, LoopCond, CondVal, LoopExitBB,
1171  nullptr);
1172 
1173  // We are only unswitching full LIV.
1174  BranchesInfo.setUnswitched(SI, CondVal);
1175  ++NumSwitches;
1176  return true;
1177  }
1178  return false;
1179 }
1180 
1181 /// Split all of the edges from inside the loop to their exit blocks.
1182 /// Update the appropriate Phi nodes as we do so.
1183 void LoopUnswitch::SplitExitEdges(Loop *L,
1184  const SmallVectorImpl<BasicBlock *> &ExitBlocks){
1185 
1186  for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) {
1187  BasicBlock *ExitBlock = ExitBlocks[i];
1188  SmallVector<BasicBlock *, 4> Preds(pred_begin(ExitBlock),
1189  pred_end(ExitBlock));
1190 
1191  // Although SplitBlockPredecessors doesn't preserve loop-simplify in
1192  // general, if we call it on all predecessors of all exits then it does.
1193  SplitBlockPredecessors(ExitBlock, Preds, ".us-lcssa", DT, LI,
1194  /*PreserveLCSSA*/ true);
1195  }
1196 }
1197 
1198 /// We determined that the loop is profitable to unswitch when LIC equal Val.
1199 /// Split it into loop versions and test the condition outside of either loop.
1200 /// Return the loops created as Out1/Out2.
1201 void LoopUnswitch::UnswitchNontrivialCondition(Value *LIC, Constant *Val,
1202  Loop *L, TerminatorInst *TI) {
1203  Function *F = loopHeader->getParent();
1204  LLVM_DEBUG(dbgs() << "loop-unswitch: Unswitching loop %"
1205  << loopHeader->getName() << " [" << L->getBlocks().size()
1206  << " blocks] in Function " << F->getName() << " when '"
1207  << *Val << "' == " << *LIC << "\n");
1208 
1209  // We are going to make essential changes to CFG. This may invalidate cached
1210  // information for L or one of its parent loops in SCEV.
1211  if (auto *SEWP = getAnalysisIfAvailable<ScalarEvolutionWrapperPass>())
1212  SEWP->getSE().forgetTopmostLoop(L);
1213 
1214  LoopBlocks.clear();
1215  NewBlocks.clear();
1216 
1217  // First step, split the preheader and exit blocks, and add these blocks to
1218  // the LoopBlocks list.
1219  BasicBlock *NewPreheader = SplitEdge(loopPreheader, loopHeader, DT, LI);
1220  LoopBlocks.push_back(NewPreheader);
1221 
1222  // We want the loop to come after the preheader, but before the exit blocks.
1223  LoopBlocks.insert(LoopBlocks.end(), L->block_begin(), L->block_end());
1224 
1225  SmallVector<BasicBlock*, 8> ExitBlocks;
1226  L->getUniqueExitBlocks(ExitBlocks);
1227 
1228  // Split all of the edges from inside the loop to their exit blocks. Update
1229  // the appropriate Phi nodes as we do so.
1230  SplitExitEdges(L, ExitBlocks);
1231 
1232  // The exit blocks may have been changed due to edge splitting, recompute.
1233  ExitBlocks.clear();
1234  L->getUniqueExitBlocks(ExitBlocks);
1235 
1236  // Add exit blocks to the loop blocks.
1237  LoopBlocks.insert(LoopBlocks.end(), ExitBlocks.begin(), ExitBlocks.end());
1238 
1239  // Next step, clone all of the basic blocks that make up the loop (including
1240  // the loop preheader and exit blocks), keeping track of the mapping between
1241  // the instructions and blocks.
1242  NewBlocks.reserve(LoopBlocks.size());
1243  ValueToValueMapTy VMap;
1244  for (unsigned i = 0, e = LoopBlocks.size(); i != e; ++i) {
1245  BasicBlock *NewBB = CloneBasicBlock(LoopBlocks[i], VMap, ".us", F);
1246 
1247  NewBlocks.push_back(NewBB);
1248  VMap[LoopBlocks[i]] = NewBB; // Keep the BB mapping.
1249  LPM->cloneBasicBlockSimpleAnalysis(LoopBlocks[i], NewBB, L);
1250  }
1251 
1252  // Splice the newly inserted blocks into the function right before the
1253  // original preheader.
1254  F->getBasicBlockList().splice(NewPreheader->getIterator(),
1255  F->getBasicBlockList(),
1256  NewBlocks[0]->getIterator(), F->end());
1257 
1258  // Now we create the new Loop object for the versioned loop.
1259  Loop *NewLoop = CloneLoop(L, L->getParentLoop(), VMap, LI, LPM);
1260 
1261  // Recalculate unswitching quota, inherit simplified switches info for NewBB,
1262  // Probably clone more loop-unswitch related loop properties.
1263  BranchesInfo.cloneData(NewLoop, L, VMap);
1264 
1265  Loop *ParentLoop = L->getParentLoop();
1266  if (ParentLoop) {
1267  // Make sure to add the cloned preheader and exit blocks to the parent loop
1268  // as well.
1269  ParentLoop->addBasicBlockToLoop(NewBlocks[0], *LI);
1270  }
1271 
1272  for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) {
1273  BasicBlock *NewExit = cast<BasicBlock>(VMap[ExitBlocks[i]]);
1274  // The new exit block should be in the same loop as the old one.
1275  if (Loop *ExitBBLoop = LI->getLoopFor(ExitBlocks[i]))
1276  ExitBBLoop->addBasicBlockToLoop(NewExit, *LI);
1277 
1278  assert(NewExit->getTerminator()->getNumSuccessors() == 1 &&
1279  "Exit block should have been split to have one successor!");
1280  BasicBlock *ExitSucc = NewExit->getTerminator()->getSuccessor(0);
1281 
1282  // If the successor of the exit block had PHI nodes, add an entry for
1283  // NewExit.
1284  for (PHINode &PN : ExitSucc->phis()) {
1285  Value *V = PN.getIncomingValueForBlock(ExitBlocks[i]);
1286  ValueToValueMapTy::iterator It = VMap.find(V);
1287  if (It != VMap.end()) V = It->second;
1288  PN.addIncoming(V, NewExit);
1289  }
1290 
1291  if (LandingPadInst *LPad = NewExit->getLandingPadInst()) {
1292  PHINode *PN = PHINode::Create(LPad->getType(), 0, "",
1293  &*ExitSucc->getFirstInsertionPt());
1294 
1295  for (pred_iterator I = pred_begin(ExitSucc), E = pred_end(ExitSucc);
1296  I != E; ++I) {
1297  BasicBlock *BB = *I;
1298  LandingPadInst *LPI = BB->getLandingPadInst();
1299  LPI->replaceAllUsesWith(PN);
1300  PN->addIncoming(LPI, BB);
1301  }
1302  }
1303  }
1304 
1305  // Rewrite the code to refer to itself.
1306  for (unsigned i = 0, e = NewBlocks.size(); i != e; ++i) {
1307  for (Instruction &I : *NewBlocks[i]) {
1308  RemapInstruction(&I, VMap,
1310  if (auto *II = dyn_cast<IntrinsicInst>(&I))
1311  if (II->getIntrinsicID() == Intrinsic::assume)
1312  AC->registerAssumption(II);
1313  }
1314  }
1315 
1316  // Rewrite the original preheader to select between versions of the loop.
1317  BranchInst *OldBR = cast<BranchInst>(loopPreheader->getTerminator());
1318  assert(OldBR->isUnconditional() && OldBR->getSuccessor(0) == LoopBlocks[0] &&
1319  "Preheader splitting did not work correctly!");
1320 
1321  // Emit the new branch that selects between the two versions of this loop.
1322  EmitPreheaderBranchOnCondition(LIC, Val, NewBlocks[0], LoopBlocks[0], OldBR,
1323  TI);
1324  LPM->deleteSimpleAnalysisValue(OldBR, L);
1325 
1326  // The OldBr was replaced by a new one and removed (but not erased) by
1327  // EmitPreheaderBranchOnCondition. It is no longer needed, so delete it.
1328  delete OldBR;
1329 
1330  LoopProcessWorklist.push_back(NewLoop);
1331  redoLoop = true;
1332 
1333  // Keep a WeakTrackingVH holding onto LIC. If the first call to
1334  // RewriteLoopBody
1335  // deletes the instruction (for example by simplifying a PHI that feeds into
1336  // the condition that we're unswitching on), we don't rewrite the second
1337  // iteration.
1338  WeakTrackingVH LICHandle(LIC);
1339 
1340  // Now we rewrite the original code to know that the condition is true and the
1341  // new code to know that the condition is false.
1342  RewriteLoopBodyWithConditionConstant(L, LIC, Val, false);
1343 
1344  // It's possible that simplifying one loop could cause the other to be
1345  // changed to another value or a constant. If its a constant, don't simplify
1346  // it.
1347  if (!LoopProcessWorklist.empty() && LoopProcessWorklist.back() == NewLoop &&
1348  LICHandle && !isa<Constant>(LICHandle))
1349  RewriteLoopBodyWithConditionConstant(NewLoop, LICHandle, Val, true);
1350 }
1351 
1352 /// Remove all instances of I from the worklist vector specified.
1354  std::vector<Instruction*> &Worklist) {
1355 
1356  Worklist.erase(std::remove(Worklist.begin(), Worklist.end(), I),
1357  Worklist.end());
1358 }
1359 
1360 /// When we find that I really equals V, remove I from the
1361 /// program, replacing all uses with V and update the worklist.
1363  std::vector<Instruction*> &Worklist,
1364  Loop *L, LPPassManager *LPM) {
1365  LLVM_DEBUG(dbgs() << "Replace with '" << *V << "': " << *I << "\n");
1366 
1367  // Add uses to the worklist, which may be dead now.
1368  for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i)
1369  if (Instruction *Use = dyn_cast<Instruction>(I->getOperand(i)))
1370  Worklist.push_back(Use);
1371 
1372  // Add users to the worklist which may be simplified now.
1373  for (User *U : I->users())
1374  Worklist.push_back(cast<Instruction>(U));
1375  LPM->deleteSimpleAnalysisValue(I, L);
1376  RemoveFromWorklist(I, Worklist);
1377  I->replaceAllUsesWith(V);
1378  if (!I->mayHaveSideEffects())
1379  I->eraseFromParent();
1380  ++NumSimplify;
1381 }
1382 
1383 /// We know either that the value LIC has the value specified by Val in the
1384 /// specified loop, or we know it does NOT have that value.
1385 /// Rewrite any uses of LIC or of properties correlated to it.
1386 void LoopUnswitch::RewriteLoopBodyWithConditionConstant(Loop *L, Value *LIC,
1387  Constant *Val,
1388  bool IsEqual) {
1389  assert(!isa<Constant>(LIC) && "Why are we unswitching on a constant?");
1390 
1391  // FIXME: Support correlated properties, like:
1392  // for (...)
1393  // if (li1 < li2)
1394  // ...
1395  // if (li1 > li2)
1396  // ...
1397 
1398  // FOLD boolean conditions (X|LIC), (X&LIC). Fold conditional branches,
1399  // selects, switches.
1400  std::vector<Instruction*> Worklist;
1401  LLVMContext &Context = Val->getContext();
1402 
1403  // If we know that LIC == Val, or that LIC == NotVal, just replace uses of LIC
1404  // in the loop with the appropriate one directly.
1405  if (IsEqual || (isa<ConstantInt>(Val) &&
1406  Val->getType()->isIntegerTy(1))) {
1407  Value *Replacement;
1408  if (IsEqual)
1409  Replacement = Val;
1410  else
1411  Replacement = ConstantInt::get(Type::getInt1Ty(Val->getContext()),
1412  !cast<ConstantInt>(Val)->getZExtValue());
1413 
1414  for (User *U : LIC->users()) {
1415  Instruction *UI = dyn_cast<Instruction>(U);
1416  if (!UI || !L->contains(UI))
1417  continue;
1418  Worklist.push_back(UI);
1419  }
1420 
1421  for (Instruction *UI : Worklist)
1422  UI->replaceUsesOfWith(LIC, Replacement);
1423 
1424  SimplifyCode(Worklist, L);
1425  return;
1426  }
1427 
1428  // Otherwise, we don't know the precise value of LIC, but we do know that it
1429  // is certainly NOT "Val". As such, simplify any uses in the loop that we
1430  // can. This case occurs when we unswitch switch statements.
1431  for (User *U : LIC->users()) {
1432  Instruction *UI = dyn_cast<Instruction>(U);
1433  if (!UI || !L->contains(UI))
1434  continue;
1435 
1436  // At this point, we know LIC is definitely not Val. Try to use some simple
1437  // logic to simplify the user w.r.t. to the context.
1438  if (Value *Replacement = SimplifyInstructionWithNotEqual(UI, LIC, Val)) {
1439  if (LI->replacementPreservesLCSSAForm(UI, Replacement)) {
1440  // This in-loop instruction has been simplified w.r.t. its context,
1441  // i.e. LIC != Val, make sure we propagate its replacement value to
1442  // all its users.
1443  //
1444  // We can not yet delete UI, the LIC user, yet, because that would invalidate
1445  // the LIC->users() iterator !. However, we can make this instruction
1446  // dead by replacing all its users and push it onto the worklist so that
1447  // it can be properly deleted and its operands simplified.
1448  UI->replaceAllUsesWith(Replacement);
1449  }
1450  }
1451 
1452  // This is a LIC user, push it into the worklist so that SimplifyCode can
1453  // attempt to simplify it.
1454  Worklist.push_back(UI);
1455 
1456  // If we know that LIC is not Val, use this info to simplify code.
1457  SwitchInst *SI = dyn_cast<SwitchInst>(UI);
1458  if (!SI || !isa<ConstantInt>(Val)) continue;
1459 
1460  // NOTE: if a case value for the switch is unswitched out, we record it
1461  // after the unswitch finishes. We can not record it here as the switch
1462  // is not a direct user of the partial LIV.
1463  SwitchInst::CaseHandle DeadCase =
1464  *SI->findCaseValue(cast<ConstantInt>(Val));
1465  // Default case is live for multiple values.
1466  if (DeadCase == *SI->case_default())
1467  continue;
1468 
1469  // Found a dead case value. Don't remove PHI nodes in the
1470  // successor if they become single-entry, those PHI nodes may
1471  // be in the Users list.
1472 
1473  BasicBlock *Switch = SI->getParent();
1474  BasicBlock *SISucc = DeadCase.getCaseSuccessor();
1475  BasicBlock *Latch = L->getLoopLatch();
1476 
1477  if (!SI->findCaseDest(SISucc)) continue; // Edge is critical.
1478  // If the DeadCase successor dominates the loop latch, then the
1479  // transformation isn't safe since it will delete the sole predecessor edge
1480  // to the latch.
1481  if (Latch && DT->dominates(SISucc, Latch))
1482  continue;
1483 
1484  // FIXME: This is a hack. We need to keep the successor around
1485  // and hooked up so as to preserve the loop structure, because
1486  // trying to update it is complicated. So instead we preserve the
1487  // loop structure and put the block on a dead code path.
1488  SplitEdge(Switch, SISucc, DT, LI);
1489  // Compute the successors instead of relying on the return value
1490  // of SplitEdge, since it may have split the switch successor
1491  // after PHI nodes.
1492  BasicBlock *NewSISucc = DeadCase.getCaseSuccessor();
1493  BasicBlock *OldSISucc = *succ_begin(NewSISucc);
1494  // Create an "unreachable" destination.
1495  BasicBlock *Abort = BasicBlock::Create(Context, "us-unreachable",
1496  Switch->getParent(),
1497  OldSISucc);
1498  new UnreachableInst(Context, Abort);
1499  // Force the new case destination to branch to the "unreachable"
1500  // block while maintaining a (dead) CFG edge to the old block.
1501  NewSISucc->getTerminator()->eraseFromParent();
1502  BranchInst::Create(Abort, OldSISucc,
1503  ConstantInt::getTrue(Context), NewSISucc);
1504  // Release the PHI operands for this edge.
1505  for (PHINode &PN : NewSISucc->phis())
1506  PN.setIncomingValue(PN.getBasicBlockIndex(Switch),
1507  UndefValue::get(PN.getType()));
1508  // Tell the domtree about the new block. We don't fully update the
1509  // domtree here -- instead we force it to do a full recomputation
1510  // after the pass is complete -- but we do need to inform it of
1511  // new blocks.
1512  DT->addNewBlock(Abort, NewSISucc);
1513  }
1514 
1515  SimplifyCode(Worklist, L);
1516 }
1517 
1518 /// Now that we have simplified some instructions in the loop, walk over it and
1519 /// constant prop, dce, and fold control flow where possible. Note that this is
1520 /// effectively a very simple loop-structure-aware optimizer. During processing
1521 /// of this loop, L could very well be deleted, so it must not be used.
1522 ///
1523 /// FIXME: When the loop optimizer is more mature, separate this out to a new
1524 /// pass.
1525 ///
1526 void LoopUnswitch::SimplifyCode(std::vector<Instruction*> &Worklist, Loop *L) {
1527  const DataLayout &DL = L->getHeader()->getModule()->getDataLayout();
1528  while (!Worklist.empty()) {
1529  Instruction *I = Worklist.back();
1530  Worklist.pop_back();
1531 
1532  // Simple DCE.
1533  if (isInstructionTriviallyDead(I)) {
1534  LLVM_DEBUG(dbgs() << "Remove dead instruction '" << *I << "\n");
1535 
1536  // Add uses to the worklist, which may be dead now.
1537  for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i)
1538  if (Instruction *Use = dyn_cast<Instruction>(I->getOperand(i)))
1539  Worklist.push_back(Use);
1540  LPM->deleteSimpleAnalysisValue(I, L);
1541  RemoveFromWorklist(I, Worklist);
1542  I->eraseFromParent();
1543  ++NumSimplify;
1544  continue;
1545  }
1546 
1547  // See if instruction simplification can hack this up. This is common for
1548  // things like "select false, X, Y" after unswitching made the condition be
1549  // 'false'. TODO: update the domtree properly so we can pass it here.
1550  if (Value *V = SimplifyInstruction(I, DL))
1551  if (LI->replacementPreservesLCSSAForm(I, V)) {
1552  ReplaceUsesOfWith(I, V, Worklist, L, LPM);
1553  continue;
1554  }
1555 
1556  // Special case hacks that appear commonly in unswitched code.
1557  if (BranchInst *BI = dyn_cast<BranchInst>(I)) {
1558  if (BI->isUnconditional()) {
1559  // If BI's parent is the only pred of the successor, fold the two blocks
1560  // together.
1561  BasicBlock *Pred = BI->getParent();
1562  BasicBlock *Succ = BI->getSuccessor(0);
1563  BasicBlock *SinglePred = Succ->getSinglePredecessor();
1564  if (!SinglePred) continue; // Nothing to do.
1565  assert(SinglePred == Pred && "CFG broken");
1566 
1567  LLVM_DEBUG(dbgs() << "Merging blocks: " << Pred->getName() << " <- "
1568  << Succ->getName() << "\n");
1569 
1570  // Resolve any single entry PHI nodes in Succ.
1571  while (PHINode *PN = dyn_cast<PHINode>(Succ->begin()))
1572  ReplaceUsesOfWith(PN, PN->getIncomingValue(0), Worklist, L, LPM);
1573 
1574  // If Succ has any successors with PHI nodes, update them to have
1575  // entries coming from Pred instead of Succ.
1576  Succ->replaceAllUsesWith(Pred);
1577 
1578  // Move all of the successor contents from Succ to Pred.
1579  Pred->getInstList().splice(BI->getIterator(), Succ->getInstList(),
1580  Succ->begin(), Succ->end());
1581  LPM->deleteSimpleAnalysisValue(BI, L);
1582  RemoveFromWorklist(BI, Worklist);
1583  BI->eraseFromParent();
1584 
1585  // Remove Succ from the loop tree.
1586  LI->removeBlock(Succ);
1587  LPM->deleteSimpleAnalysisValue(Succ, L);
1588  Succ->eraseFromParent();
1589  ++NumSimplify;
1590  continue;
1591  }
1592 
1593  continue;
1594  }
1595  }
1596 }
1597 
1598 /// Simple simplifications we can do given the information that Cond is
1599 /// definitely not equal to Val.
1600 Value *LoopUnswitch::SimplifyInstructionWithNotEqual(Instruction *Inst,
1601  Value *Invariant,
1602  Constant *Val) {
1603  // icmp eq cond, val -> false
1604  ICmpInst *CI = dyn_cast<ICmpInst>(Inst);
1605  if (CI && CI->isEquality()) {
1606  Value *Op0 = CI->getOperand(0);
1607  Value *Op1 = CI->getOperand(1);
1608  if ((Op0 == Invariant && Op1 == Val) || (Op0 == Val && Op1 == Invariant)) {
1609  LLVMContext &Ctx = Inst->getContext();
1610  if (CI->getPredicate() == CmpInst::ICMP_EQ)
1611  return ConstantInt::getFalse(Ctx);
1612  else
1613  return ConstantInt::getTrue(Ctx);
1614  }
1615  }
1616 
1617  // FIXME: there may be other opportunities, e.g. comparison with floating
1618  // point, or Invariant - Val != 0, etc.
1619  return nullptr;
1620 }
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
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
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.
OperatorChain
Operator chain lattice.
iterator end()
Definition: Function.h:644
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:176
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: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: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
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
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: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
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: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: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: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: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:847
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: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: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: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:959
LLVM_ATTRIBUTE_ALWAYS_INLINE iterator end()
Definition: SmallVector.h:133
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:331
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: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: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:1227
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:347
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.
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
#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