LLVM  6.0.0svn
LoopUnswitch.cpp
Go to the documentation of this file.
1 //===- LoopUnswitch.cpp - Hoist loop-invariant conditionals in loop -------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This pass transforms loops that contain branches on loop-invariant conditions
11 // to multiple loops. For example, it turns the left into the right code:
12 //
13 // for (...) if (lic)
14 // A for (...)
15 // if (lic) A; B; C
16 // B else
17 // C for (...)
18 // A; C
19 //
20 // This can increase the size of the code exponentially (doubling it every time
21 // a loop is unswitched) so we only unswitch if the resultant code will be
22 // smaller than a threshold.
23 //
24 // This pass expects LICM to be run before it to hoist invariant conditions out
25 // of the loop, to make the unswitching opportunity obvious.
26 //
27 //===----------------------------------------------------------------------===//
28 
29 #include "llvm/ADT/DenseMap.h"
30 #include "llvm/ADT/SmallPtrSet.h"
31 #include "llvm/ADT/SmallSet.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"
42 #include "llvm/IR/Attributes.h"
43 #include "llvm/IR/BasicBlock.h"
44 #include "llvm/IR/CallSite.h"
45 #include "llvm/IR/Constant.h"
46 #include "llvm/IR/Constants.h"
47 #include "llvm/IR/DerivedTypes.h"
48 #include "llvm/IR/Dominators.h"
49 #include "llvm/IR/Function.h"
50 #include "llvm/IR/IRBuilder.h"
51 #include "llvm/IR/InstrTypes.h"
52 #include "llvm/IR/Instruction.h"
53 #include "llvm/IR/Instructions.h"
54 #include "llvm/IR/IntrinsicInst.h"
55 #include "llvm/IR/Intrinsics.h"
56 #include "llvm/IR/Module.h"
57 #include "llvm/IR/Type.h"
58 #include "llvm/IR/User.h"
59 #include "llvm/IR/Value.h"
60 #include "llvm/IR/ValueHandle.h"
61 #include "llvm/Pass.h"
62 #include "llvm/Support/Casting.h"
64 #include "llvm/Support/Debug.h"
66 #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  DEBUG(dbgs() << "NOT unswitching loop %"
302  << L->getHeader()->getName() << ", 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  // Run through the instructions in the loop, keeping track of three things:
639  //
640  // - That we do not unswitch loops containing convergent operations, as we
641  // might be making them control dependent on the unswitch value when they
642  // were not before.
643  // FIXME: This could be refined to only bail if the convergent operation is
644  // not already control-dependent on the unswitch value.
645  //
646  // - That basic blocks in the loop contain invokes whose predecessor edges we
647  // cannot split.
648  //
649  // - The set of guard intrinsics encountered (these are non terminator
650  // instructions that are also profitable to be unswitched).
651 
653 
654  for (const auto BB : currentLoop->blocks()) {
655  for (auto &I : *BB) {
656  auto CS = CallSite(&I);
657  if (!CS) continue;
658  if (CS.hasFnAttr(Attribute::Convergent))
659  return false;
660  if (auto *II = dyn_cast<InvokeInst>(&I))
661  if (!II->getUnwindDest()->canSplitPredecessors())
662  return false;
663  if (auto *II = dyn_cast<IntrinsicInst>(&I))
664  if (II->getIntrinsicID() == Intrinsic::experimental_guard)
665  Guards.push_back(II);
666  }
667  }
668 
669  // Do not do non-trivial unswitch while optimizing for size.
670  // FIXME: Use Function::optForSize().
671  if (OptimizeForSize ||
672  loopHeader->getParent()->hasFnAttribute(Attribute::OptimizeForSize))
673  return false;
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  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  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  DEBUG(dbgs() << "loop-unswitch: Trivial-Unswitch loop %"
974  << loopHeader->getName() << " [" << L->getBlocks().size()
975  << " blocks] in Function "
976  << L->getHeader()->getParent()->getName() << " on cond: " << *Val
977  << " == " << *Cond << "\n");
978 
979  // First step, split the preheader, so that we know that there is a safe place
980  // to insert the conditional branch. We will change loopPreheader to have a
981  // conditional branch on Cond.
982  BasicBlock *NewPH = SplitEdge(loopPreheader, loopHeader, DT, LI);
983 
984  // Now that we have a place to insert the conditional branch, create a place
985  // to branch to: this is the exit block out of the loop that we should
986  // short-circuit to.
987 
988  // Split this block now, so that the loop maintains its exit block, and so
989  // that the jump from the preheader can execute the contents of the exit block
990  // without actually branching to it (the exit block should be dominated by the
991  // loop header, not the preheader).
992  assert(!L->contains(ExitBlock) && "Exit block is in the loop?");
993  BasicBlock *NewExit = SplitBlock(ExitBlock, &ExitBlock->front(), DT, LI);
994 
995  // Okay, now we have a position to branch from and a position to branch to,
996  // insert the new conditional branch.
997  auto *OldBranch = dyn_cast<BranchInst>(loopPreheader->getTerminator());
998  assert(OldBranch && "Failed to split the preheader");
999  EmitPreheaderBranchOnCondition(Cond, Val, NewExit, NewPH, OldBranch, TI);
1000  LPM->deleteSimpleAnalysisValue(OldBranch, L);
1001 
1002  // EmitPreheaderBranchOnCondition removed the OldBranch from the function.
1003  // Delete it, as it is no longer needed.
1004  delete OldBranch;
1005 
1006  // We need to reprocess this loop, it could be unswitched again.
1007  redoLoop = true;
1008 
1009  // Now that we know that the loop is never entered when this condition is a
1010  // particular value, rewrite the loop with this info. We know that this will
1011  // at least eliminate the old branch.
1012  RewriteLoopBodyWithConditionConstant(L, Cond, Val, false);
1013  ++NumTrivial;
1014 }
1015 
1016 /// Check if the first non-constant condition starting from the loop header is
1017 /// a trivial unswitch condition: that is, a condition controls whether or not
1018 /// the loop does anything at all. If it is a trivial condition, unswitching
1019 /// produces no code duplications (equivalently, it produces a simpler loop and
1020 /// a new empty loop, which gets deleted). Therefore always unswitch trivial
1021 /// condition.
1022 bool LoopUnswitch::TryTrivialLoopUnswitch(bool &Changed) {
1023  BasicBlock *CurrentBB = currentLoop->getHeader();
1024  TerminatorInst *CurrentTerm = CurrentBB->getTerminator();
1025  LLVMContext &Context = CurrentBB->getContext();
1026 
1027  // If loop header has only one reachable successor (currently via an
1028  // unconditional branch or constant foldable conditional branch, but
1029  // should also consider adding constant foldable switch instruction in
1030  // future), we should keep looking for trivial condition candidates in
1031  // the successor as well. An alternative is to constant fold conditions
1032  // and merge successors into loop header (then we only need to check header's
1033  // terminator). The reason for not doing this in LoopUnswitch pass is that
1034  // it could potentially break LoopPassManager's invariants. Folding dead
1035  // branches could either eliminate the current loop or make other loops
1036  // unreachable. LCSSA form might also not be preserved after deleting
1037  // branches. The following code keeps traversing loop header's successors
1038  // until it finds the trivial condition candidate (condition that is not a
1039  // constant). Since unswitching generates branches with constant conditions,
1040  // this scenario could be very common in practice.
1041  SmallSet<BasicBlock*, 8> Visited;
1042 
1043  while (true) {
1044  // If we exit loop or reach a previous visited block, then
1045  // we can not reach any trivial condition candidates (unfoldable
1046  // branch instructions or switch instructions) and no unswitch
1047  // can happen. Exit and return false.
1048  if (!currentLoop->contains(CurrentBB) || !Visited.insert(CurrentBB).second)
1049  return false;
1050 
1051  // Check if this loop will execute any side-effecting instructions (e.g.
1052  // stores, calls, volatile loads) in the part of the loop that the code
1053  // *would* execute. Check the header first.
1054  for (Instruction &I : *CurrentBB)
1055  if (I.mayHaveSideEffects())
1056  return false;
1057 
1058  if (BranchInst *BI = dyn_cast<BranchInst>(CurrentTerm)) {
1059  if (BI->isUnconditional()) {
1060  CurrentBB = BI->getSuccessor(0);
1061  } else if (BI->getCondition() == ConstantInt::getTrue(Context)) {
1062  CurrentBB = BI->getSuccessor(0);
1063  } else if (BI->getCondition() == ConstantInt::getFalse(Context)) {
1064  CurrentBB = BI->getSuccessor(1);
1065  } else {
1066  // Found a trivial condition candidate: non-foldable conditional branch.
1067  break;
1068  }
1069  } else if (SwitchInst *SI = dyn_cast<SwitchInst>(CurrentTerm)) {
1070  // At this point, any constant-foldable instructions should have probably
1071  // been folded.
1072  ConstantInt *Cond = dyn_cast<ConstantInt>(SI->getCondition());
1073  if (!Cond)
1074  break;
1075  // Find the target block we are definitely going to.
1076  CurrentBB = SI->findCaseValue(Cond)->getCaseSuccessor();
1077  } else {
1078  // We do not understand these terminator instructions.
1079  break;
1080  }
1081 
1082  CurrentTerm = CurrentBB->getTerminator();
1083  }
1084 
1085  // CondVal is the condition that controls the trivial condition.
1086  // LoopExitBB is the BasicBlock that loop exits when meets trivial condition.
1087  Constant *CondVal = nullptr;
1088  BasicBlock *LoopExitBB = nullptr;
1089 
1090  if (BranchInst *BI = dyn_cast<BranchInst>(CurrentTerm)) {
1091  // If this isn't branching on an invariant condition, we can't unswitch it.
1092  if (!BI->isConditional())
1093  return false;
1094 
1095  Value *LoopCond = FindLIVLoopCondition(BI->getCondition(),
1096  currentLoop, Changed).first;
1097 
1098  // Unswitch only if the trivial condition itself is an LIV (not
1099  // partial LIV which could occur in and/or)
1100  if (!LoopCond || LoopCond != BI->getCondition())
1101  return false;
1102 
1103  // Check to see if a successor of the branch is guaranteed to
1104  // exit through a unique exit block without having any
1105  // side-effects. If so, determine the value of Cond that causes
1106  // it to do this.
1107  if ((LoopExitBB = isTrivialLoopExitBlock(currentLoop,
1108  BI->getSuccessor(0)))) {
1109  CondVal = ConstantInt::getTrue(Context);
1110  } else if ((LoopExitBB = isTrivialLoopExitBlock(currentLoop,
1111  BI->getSuccessor(1)))) {
1112  CondVal = ConstantInt::getFalse(Context);
1113  }
1114 
1115  // If we didn't find a single unique LoopExit block, or if the loop exit
1116  // block contains phi nodes, this isn't trivial.
1117  if (!LoopExitBB || isa<PHINode>(LoopExitBB->begin()))
1118  return false; // Can't handle this.
1119 
1120  if (EqualityPropUnSafe(*LoopCond))
1121  return false;
1122 
1123  UnswitchTrivialCondition(currentLoop, LoopCond, CondVal, LoopExitBB,
1124  CurrentTerm);
1125  ++NumBranches;
1126  return true;
1127  } else if (SwitchInst *SI = dyn_cast<SwitchInst>(CurrentTerm)) {
1128  // If this isn't switching on an invariant condition, we can't unswitch it.
1129  Value *LoopCond = FindLIVLoopCondition(SI->getCondition(),
1130  currentLoop, Changed).first;
1131 
1132  // Unswitch only if the trivial condition itself is an LIV (not
1133  // partial LIV which could occur in and/or)
1134  if (!LoopCond || LoopCond != SI->getCondition())
1135  return false;
1136 
1137  // Check to see if a successor of the switch is guaranteed to go to the
1138  // latch block or exit through a one exit block without having any
1139  // side-effects. If so, determine the value of Cond that causes it to do
1140  // this.
1141  // Note that we can't trivially unswitch on the default case or
1142  // on already unswitched cases.
1143  for (auto Case : SI->cases()) {
1144  BasicBlock *LoopExitCandidate;
1145  if ((LoopExitCandidate =
1146  isTrivialLoopExitBlock(currentLoop, Case.getCaseSuccessor()))) {
1147  // Okay, we found a trivial case, remember the value that is trivial.
1148  ConstantInt *CaseVal = Case.getCaseValue();
1149 
1150  // Check that it was not unswitched before, since already unswitched
1151  // trivial vals are looks trivial too.
1152  if (BranchesInfo.isUnswitched(SI, CaseVal))
1153  continue;
1154  LoopExitBB = LoopExitCandidate;
1155  CondVal = CaseVal;
1156  break;
1157  }
1158  }
1159 
1160  // If we didn't find a single unique LoopExit block, or if the loop exit
1161  // block contains phi nodes, this isn't trivial.
1162  if (!LoopExitBB || isa<PHINode>(LoopExitBB->begin()))
1163  return false; // Can't handle this.
1164 
1165  UnswitchTrivialCondition(currentLoop, LoopCond, CondVal, LoopExitBB,
1166  nullptr);
1167 
1168  // We are only unswitching full LIV.
1169  BranchesInfo.setUnswitched(SI, CondVal);
1170  ++NumSwitches;
1171  return true;
1172  }
1173  return false;
1174 }
1175 
1176 /// Split all of the edges from inside the loop to their exit blocks.
1177 /// Update the appropriate Phi nodes as we do so.
1178 void LoopUnswitch::SplitExitEdges(Loop *L,
1179  const SmallVectorImpl<BasicBlock *> &ExitBlocks){
1180 
1181  for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) {
1182  BasicBlock *ExitBlock = ExitBlocks[i];
1183  SmallVector<BasicBlock *, 4> Preds(pred_begin(ExitBlock),
1184  pred_end(ExitBlock));
1185 
1186  // Although SplitBlockPredecessors doesn't preserve loop-simplify in
1187  // general, if we call it on all predecessors of all exits then it does.
1188  SplitBlockPredecessors(ExitBlock, Preds, ".us-lcssa", DT, LI,
1189  /*PreserveLCSSA*/ true);
1190  }
1191 }
1192 
1193 /// We determined that the loop is profitable to unswitch when LIC equal Val.
1194 /// Split it into loop versions and test the condition outside of either loop.
1195 /// Return the loops created as Out1/Out2.
1196 void LoopUnswitch::UnswitchNontrivialCondition(Value *LIC, Constant *Val,
1197  Loop *L, TerminatorInst *TI) {
1198  Function *F = loopHeader->getParent();
1199  DEBUG(dbgs() << "loop-unswitch: Unswitching loop %"
1200  << loopHeader->getName() << " [" << L->getBlocks().size()
1201  << " blocks] in Function " << F->getName()
1202  << " when '" << *Val << "' == " << *LIC << "\n");
1203 
1204  if (auto *SEWP = getAnalysisIfAvailable<ScalarEvolutionWrapperPass>())
1205  SEWP->getSE().forgetLoop(L);
1206 
1207  LoopBlocks.clear();
1208  NewBlocks.clear();
1209 
1210  // First step, split the preheader and exit blocks, and add these blocks to
1211  // the LoopBlocks list.
1212  BasicBlock *NewPreheader = SplitEdge(loopPreheader, loopHeader, DT, LI);
1213  LoopBlocks.push_back(NewPreheader);
1214 
1215  // We want the loop to come after the preheader, but before the exit blocks.
1216  LoopBlocks.insert(LoopBlocks.end(), L->block_begin(), L->block_end());
1217 
1218  SmallVector<BasicBlock*, 8> ExitBlocks;
1219  L->getUniqueExitBlocks(ExitBlocks);
1220 
1221  // Split all of the edges from inside the loop to their exit blocks. Update
1222  // the appropriate Phi nodes as we do so.
1223  SplitExitEdges(L, ExitBlocks);
1224 
1225  // The exit blocks may have been changed due to edge splitting, recompute.
1226  ExitBlocks.clear();
1227  L->getUniqueExitBlocks(ExitBlocks);
1228 
1229  // Add exit blocks to the loop blocks.
1230  LoopBlocks.insert(LoopBlocks.end(), ExitBlocks.begin(), ExitBlocks.end());
1231 
1232  // Next step, clone all of the basic blocks that make up the loop (including
1233  // the loop preheader and exit blocks), keeping track of the mapping between
1234  // the instructions and blocks.
1235  NewBlocks.reserve(LoopBlocks.size());
1236  ValueToValueMapTy VMap;
1237  for (unsigned i = 0, e = LoopBlocks.size(); i != e; ++i) {
1238  BasicBlock *NewBB = CloneBasicBlock(LoopBlocks[i], VMap, ".us", F);
1239 
1240  NewBlocks.push_back(NewBB);
1241  VMap[LoopBlocks[i]] = NewBB; // Keep the BB mapping.
1242  LPM->cloneBasicBlockSimpleAnalysis(LoopBlocks[i], NewBB, L);
1243  }
1244 
1245  // Splice the newly inserted blocks into the function right before the
1246  // original preheader.
1247  F->getBasicBlockList().splice(NewPreheader->getIterator(),
1248  F->getBasicBlockList(),
1249  NewBlocks[0]->getIterator(), F->end());
1250 
1251  // Now we create the new Loop object for the versioned loop.
1252  Loop *NewLoop = CloneLoop(L, L->getParentLoop(), VMap, LI, LPM);
1253 
1254  // Recalculate unswitching quota, inherit simplified switches info for NewBB,
1255  // Probably clone more loop-unswitch related loop properties.
1256  BranchesInfo.cloneData(NewLoop, L, VMap);
1257 
1258  Loop *ParentLoop = L->getParentLoop();
1259  if (ParentLoop) {
1260  // Make sure to add the cloned preheader and exit blocks to the parent loop
1261  // as well.
1262  ParentLoop->addBasicBlockToLoop(NewBlocks[0], *LI);
1263  }
1264 
1265  for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) {
1266  BasicBlock *NewExit = cast<BasicBlock>(VMap[ExitBlocks[i]]);
1267  // The new exit block should be in the same loop as the old one.
1268  if (Loop *ExitBBLoop = LI->getLoopFor(ExitBlocks[i]))
1269  ExitBBLoop->addBasicBlockToLoop(NewExit, *LI);
1270 
1271  assert(NewExit->getTerminator()->getNumSuccessors() == 1 &&
1272  "Exit block should have been split to have one successor!");
1273  BasicBlock *ExitSucc = NewExit->getTerminator()->getSuccessor(0);
1274 
1275  // If the successor of the exit block had PHI nodes, add an entry for
1276  // NewExit.
1277  for (BasicBlock::iterator I = ExitSucc->begin();
1278  PHINode *PN = dyn_cast<PHINode>(I); ++I) {
1279  Value *V = PN->getIncomingValueForBlock(ExitBlocks[i]);
1280  ValueToValueMapTy::iterator It = VMap.find(V);
1281  if (It != VMap.end()) V = It->second;
1282  PN->addIncoming(V, NewExit);
1283  }
1284 
1285  if (LandingPadInst *LPad = NewExit->getLandingPadInst()) {
1286  PHINode *PN = PHINode::Create(LPad->getType(), 0, "",
1287  &*ExitSucc->getFirstInsertionPt());
1288 
1289  for (pred_iterator I = pred_begin(ExitSucc), E = pred_end(ExitSucc);
1290  I != E; ++I) {
1291  BasicBlock *BB = *I;
1292  LandingPadInst *LPI = BB->getLandingPadInst();
1293  LPI->replaceAllUsesWith(PN);
1294  PN->addIncoming(LPI, BB);
1295  }
1296  }
1297  }
1298 
1299  // Rewrite the code to refer to itself.
1300  for (unsigned i = 0, e = NewBlocks.size(); i != e; ++i) {
1301  for (Instruction &I : *NewBlocks[i]) {
1302  RemapInstruction(&I, VMap,
1304  if (auto *II = dyn_cast<IntrinsicInst>(&I))
1305  if (II->getIntrinsicID() == Intrinsic::assume)
1306  AC->registerAssumption(II);
1307  }
1308  }
1309 
1310  // Rewrite the original preheader to select between versions of the loop.
1311  BranchInst *OldBR = cast<BranchInst>(loopPreheader->getTerminator());
1312  assert(OldBR->isUnconditional() && OldBR->getSuccessor(0) == LoopBlocks[0] &&
1313  "Preheader splitting did not work correctly!");
1314 
1315  // Emit the new branch that selects between the two versions of this loop.
1316  EmitPreheaderBranchOnCondition(LIC, Val, NewBlocks[0], LoopBlocks[0], OldBR,
1317  TI);
1318  LPM->deleteSimpleAnalysisValue(OldBR, L);
1319 
1320  // The OldBr was replaced by a new one and removed (but not erased) by
1321  // EmitPreheaderBranchOnCondition. It is no longer needed, so delete it.
1322  delete OldBR;
1323 
1324  LoopProcessWorklist.push_back(NewLoop);
1325  redoLoop = true;
1326 
1327  // Keep a WeakTrackingVH holding onto LIC. If the first call to
1328  // RewriteLoopBody
1329  // deletes the instruction (for example by simplifying a PHI that feeds into
1330  // the condition that we're unswitching on), we don't rewrite the second
1331  // iteration.
1332  WeakTrackingVH LICHandle(LIC);
1333 
1334  // Now we rewrite the original code to know that the condition is true and the
1335  // new code to know that the condition is false.
1336  RewriteLoopBodyWithConditionConstant(L, LIC, Val, false);
1337 
1338  // It's possible that simplifying one loop could cause the other to be
1339  // changed to another value or a constant. If its a constant, don't simplify
1340  // it.
1341  if (!LoopProcessWorklist.empty() && LoopProcessWorklist.back() == NewLoop &&
1342  LICHandle && !isa<Constant>(LICHandle))
1343  RewriteLoopBodyWithConditionConstant(NewLoop, LICHandle, Val, true);
1344 }
1345 
1346 /// Remove all instances of I from the worklist vector specified.
1348  std::vector<Instruction*> &Worklist) {
1349 
1350  Worklist.erase(std::remove(Worklist.begin(), Worklist.end(), I),
1351  Worklist.end());
1352 }
1353 
1354 /// When we find that I really equals V, remove I from the
1355 /// program, replacing all uses with V and update the worklist.
1357  std::vector<Instruction*> &Worklist,
1358  Loop *L, LPPassManager *LPM) {
1359  DEBUG(dbgs() << "Replace with '" << *V << "': " << *I << "\n");
1360 
1361  // Add uses to the worklist, which may be dead now.
1362  for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i)
1363  if (Instruction *Use = dyn_cast<Instruction>(I->getOperand(i)))
1364  Worklist.push_back(Use);
1365 
1366  // Add users to the worklist which may be simplified now.
1367  for (User *U : I->users())
1368  Worklist.push_back(cast<Instruction>(U));
1369  LPM->deleteSimpleAnalysisValue(I, L);
1370  RemoveFromWorklist(I, Worklist);
1371  I->replaceAllUsesWith(V);
1372  if (!I->mayHaveSideEffects())
1373  I->eraseFromParent();
1374  ++NumSimplify;
1375 }
1376 
1377 /// We know either that the value LIC has the value specified by Val in the
1378 /// specified loop, or we know it does NOT have that value.
1379 /// Rewrite any uses of LIC or of properties correlated to it.
1380 void LoopUnswitch::RewriteLoopBodyWithConditionConstant(Loop *L, Value *LIC,
1381  Constant *Val,
1382  bool IsEqual) {
1383  assert(!isa<Constant>(LIC) && "Why are we unswitching on a constant?");
1384 
1385  // FIXME: Support correlated properties, like:
1386  // for (...)
1387  // if (li1 < li2)
1388  // ...
1389  // if (li1 > li2)
1390  // ...
1391 
1392  // FOLD boolean conditions (X|LIC), (X&LIC). Fold conditional branches,
1393  // selects, switches.
1394  std::vector<Instruction*> Worklist;
1395  LLVMContext &Context = Val->getContext();
1396 
1397  // If we know that LIC == Val, or that LIC == NotVal, just replace uses of LIC
1398  // in the loop with the appropriate one directly.
1399  if (IsEqual || (isa<ConstantInt>(Val) &&
1400  Val->getType()->isIntegerTy(1))) {
1401  Value *Replacement;
1402  if (IsEqual)
1403  Replacement = Val;
1404  else
1405  Replacement = ConstantInt::get(Type::getInt1Ty(Val->getContext()),
1406  !cast<ConstantInt>(Val)->getZExtValue());
1407 
1408  for (User *U : LIC->users()) {
1409  Instruction *UI = dyn_cast<Instruction>(U);
1410  if (!UI || !L->contains(UI))
1411  continue;
1412  Worklist.push_back(UI);
1413  }
1414 
1415  for (Instruction *UI : Worklist)
1416  UI->replaceUsesOfWith(LIC, Replacement);
1417 
1418  SimplifyCode(Worklist, L);
1419  return;
1420  }
1421 
1422  // Otherwise, we don't know the precise value of LIC, but we do know that it
1423  // is certainly NOT "Val". As such, simplify any uses in the loop that we
1424  // can. This case occurs when we unswitch switch statements.
1425  for (User *U : LIC->users()) {
1426  Instruction *UI = dyn_cast<Instruction>(U);
1427  if (!UI || !L->contains(UI))
1428  continue;
1429 
1430  // At this point, we know LIC is definitely not Val. Try to use some simple
1431  // logic to simplify the user w.r.t. to the context.
1432  if (Value *Replacement = SimplifyInstructionWithNotEqual(UI, LIC, Val)) {
1433  if (LI->replacementPreservesLCSSAForm(UI, Replacement)) {
1434  // This in-loop instruction has been simplified w.r.t. its context,
1435  // i.e. LIC != Val, make sure we propagate its replacement value to
1436  // all its users.
1437  //
1438  // We can not yet delete UI, the LIC user, yet, because that would invalidate
1439  // the LIC->users() iterator !. However, we can make this instruction
1440  // dead by replacing all its users and push it onto the worklist so that
1441  // it can be properly deleted and its operands simplified.
1442  UI->replaceAllUsesWith(Replacement);
1443  }
1444  }
1445 
1446  // This is a LIC user, push it into the worklist so that SimplifyCode can
1447  // attempt to simplify it.
1448  Worklist.push_back(UI);
1449 
1450  // If we know that LIC is not Val, use this info to simplify code.
1451  SwitchInst *SI = dyn_cast<SwitchInst>(UI);
1452  if (!SI || !isa<ConstantInt>(Val)) continue;
1453 
1454  // NOTE: if a case value for the switch is unswitched out, we record it
1455  // after the unswitch finishes. We can not record it here as the switch
1456  // is not a direct user of the partial LIV.
1457  SwitchInst::CaseHandle DeadCase =
1458  *SI->findCaseValue(cast<ConstantInt>(Val));
1459  // Default case is live for multiple values.
1460  if (DeadCase == *SI->case_default())
1461  continue;
1462 
1463  // Found a dead case value. Don't remove PHI nodes in the
1464  // successor if they become single-entry, those PHI nodes may
1465  // be in the Users list.
1466 
1467  BasicBlock *Switch = SI->getParent();
1468  BasicBlock *SISucc = DeadCase.getCaseSuccessor();
1469  BasicBlock *Latch = L->getLoopLatch();
1470 
1471  if (!SI->findCaseDest(SISucc)) continue; // Edge is critical.
1472  // If the DeadCase successor dominates the loop latch, then the
1473  // transformation isn't safe since it will delete the sole predecessor edge
1474  // to the latch.
1475  if (Latch && DT->dominates(SISucc, Latch))
1476  continue;
1477 
1478  // FIXME: This is a hack. We need to keep the successor around
1479  // and hooked up so as to preserve the loop structure, because
1480  // trying to update it is complicated. So instead we preserve the
1481  // loop structure and put the block on a dead code path.
1482  SplitEdge(Switch, SISucc, DT, LI);
1483  // Compute the successors instead of relying on the return value
1484  // of SplitEdge, since it may have split the switch successor
1485  // after PHI nodes.
1486  BasicBlock *NewSISucc = DeadCase.getCaseSuccessor();
1487  BasicBlock *OldSISucc = *succ_begin(NewSISucc);
1488  // Create an "unreachable" destination.
1489  BasicBlock *Abort = BasicBlock::Create(Context, "us-unreachable",
1490  Switch->getParent(),
1491  OldSISucc);
1492  new UnreachableInst(Context, Abort);
1493  // Force the new case destination to branch to the "unreachable"
1494  // block while maintaining a (dead) CFG edge to the old block.
1495  NewSISucc->getTerminator()->eraseFromParent();
1496  BranchInst::Create(Abort, OldSISucc,
1497  ConstantInt::getTrue(Context), NewSISucc);
1498  // Release the PHI operands for this edge.
1499  for (BasicBlock::iterator II = NewSISucc->begin();
1500  PHINode *PN = dyn_cast<PHINode>(II); ++II)
1501  PN->setIncomingValue(PN->getBasicBlockIndex(Switch),
1502  UndefValue::get(PN->getType()));
1503  // Tell the domtree about the new block. We don't fully update the
1504  // domtree here -- instead we force it to do a full recomputation
1505  // after the pass is complete -- but we do need to inform it of
1506  // new blocks.
1507  DT->addNewBlock(Abort, NewSISucc);
1508  }
1509 
1510  SimplifyCode(Worklist, L);
1511 }
1512 
1513 /// Now that we have simplified some instructions in the loop, walk over it and
1514 /// constant prop, dce, and fold control flow where possible. Note that this is
1515 /// effectively a very simple loop-structure-aware optimizer. During processing
1516 /// of this loop, L could very well be deleted, so it must not be used.
1517 ///
1518 /// FIXME: When the loop optimizer is more mature, separate this out to a new
1519 /// pass.
1520 ///
1521 void LoopUnswitch::SimplifyCode(std::vector<Instruction*> &Worklist, Loop *L) {
1522  const DataLayout &DL = L->getHeader()->getModule()->getDataLayout();
1523  while (!Worklist.empty()) {
1524  Instruction *I = Worklist.back();
1525  Worklist.pop_back();
1526 
1527  // Simple DCE.
1528  if (isInstructionTriviallyDead(I)) {
1529  DEBUG(dbgs() << "Remove dead instruction '" << *I << "\n");
1530 
1531  // Add uses to the worklist, which may be dead now.
1532  for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i)
1533  if (Instruction *Use = dyn_cast<Instruction>(I->getOperand(i)))
1534  Worklist.push_back(Use);
1535  LPM->deleteSimpleAnalysisValue(I, L);
1536  RemoveFromWorklist(I, Worklist);
1537  I->eraseFromParent();
1538  ++NumSimplify;
1539  continue;
1540  }
1541 
1542  // See if instruction simplification can hack this up. This is common for
1543  // things like "select false, X, Y" after unswitching made the condition be
1544  // 'false'. TODO: update the domtree properly so we can pass it here.
1545  if (Value *V = SimplifyInstruction(I, DL))
1546  if (LI->replacementPreservesLCSSAForm(I, V)) {
1547  ReplaceUsesOfWith(I, V, Worklist, L, LPM);
1548  continue;
1549  }
1550 
1551  // Special case hacks that appear commonly in unswitched code.
1552  if (BranchInst *BI = dyn_cast<BranchInst>(I)) {
1553  if (BI->isUnconditional()) {
1554  // If BI's parent is the only pred of the successor, fold the two blocks
1555  // together.
1556  BasicBlock *Pred = BI->getParent();
1557  BasicBlock *Succ = BI->getSuccessor(0);
1558  BasicBlock *SinglePred = Succ->getSinglePredecessor();
1559  if (!SinglePred) continue; // Nothing to do.
1560  assert(SinglePred == Pred && "CFG broken");
1561 
1562  DEBUG(dbgs() << "Merging blocks: " << Pred->getName() << " <- "
1563  << Succ->getName() << "\n");
1564 
1565  // Resolve any single entry PHI nodes in Succ.
1566  while (PHINode *PN = dyn_cast<PHINode>(Succ->begin()))
1567  ReplaceUsesOfWith(PN, PN->getIncomingValue(0), Worklist, L, LPM);
1568 
1569  // If Succ has any successors with PHI nodes, update them to have
1570  // entries coming from Pred instead of Succ.
1571  Succ->replaceAllUsesWith(Pred);
1572 
1573  // Move all of the successor contents from Succ to Pred.
1574  Pred->getInstList().splice(BI->getIterator(), Succ->getInstList(),
1575  Succ->begin(), Succ->end());
1576  LPM->deleteSimpleAnalysisValue(BI, L);
1577  RemoveFromWorklist(BI, Worklist);
1578  BI->eraseFromParent();
1579 
1580  // Remove Succ from the loop tree.
1581  LI->removeBlock(Succ);
1582  LPM->deleteSimpleAnalysisValue(Succ, L);
1583  Succ->eraseFromParent();
1584  ++NumSimplify;
1585  continue;
1586  }
1587 
1588  continue;
1589  }
1590  }
1591 }
1592 
1593 /// Simple simplifications we can do given the information that Cond is
1594 /// definitely not equal to Val.
1595 Value *LoopUnswitch::SimplifyInstructionWithNotEqual(Instruction *Inst,
1596  Value *Invariant,
1597  Constant *Val) {
1598  // icmp eq cond, val -> false
1599  ICmpInst *CI = dyn_cast<ICmpInst>(Inst);
1600  if (CI && CI->isEquality()) {
1601  Value *Op0 = CI->getOperand(0);
1602  Value *Op1 = CI->getOperand(1);
1603  if ((Op0 == Invariant && Op1 == Val) || (Op0 == Val && Op1 == Invariant)) {
1604  LLVMContext &Ctx = Inst->getContext();
1605  if (CI->getPredicate() == CmpInst::ICMP_EQ)
1606  return ConstantInt::getFalse(Ctx);
1607  else
1608  return ConstantInt::getTrue(Ctx);
1609  }
1610  }
1611 
1612  // FIXME: there may be other opportunities, e.g. comparison with floating
1613  // point, or Invariant - Val != 0, etc.
1614  return nullptr;
1615 }
Pass interface - Implemented by all &#39;passes&#39;.
Definition: Pass.h:81
static void collectEphemeralValues(const Loop *L, AssumptionCache *AC, SmallPtrSetImpl< const Value *> &EphValues)
Collect a loop&#39;s ephemeral values (those used only by an assume or similar intrinsics in the loop)...
Definition: CodeMetrics.cpp:73
DomTreeNodeBase< NodeT > * getNode(NodeT *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
unsigned getNumCases() const
Return the number of &#39;cases&#39; in this switch instruction, excluding the default case.
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks &#39;this&#39; from the containing basic block and deletes it.
Definition: Instruction.cpp:69
void initializeLoopUnswitchPass(PassRegistry &)
A parsed version of the target data layout string in and methods for querying it. ...
Definition: DataLayout.h:109
static ConstantInt * getFalse(LLVMContext &Context)
Definition: Constants.cpp:523
static IntegerType * getInt1Ty(LLVMContext &C)
Definition: Type.cpp:173
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
BlockT * getLoopLatch() const
If there is a single latch block for this loop, return it.
Definition: LoopInfoImpl.h: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:136
OperatorChain
Operator chain lattice.
iterator end()
Definition: Function.h:590
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:175
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 .assume calls within a function.
LLVMContext & getContext() const
All values hold a context through their type.
Definition: Value.cpp:728
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:66
bool hasFnAttribute(Attribute::AttrKind Kind) const
Return true if the function has the attribute.
Definition: Function.h:262
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:207
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:252
AnalysisUsage & addRequired()
const Module * getModule() const
Return the module owning the function this basic block belongs to, or nullptr it the function does no...
Definition: BasicBlock.cpp:116
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:51
static void ReplaceUsesOfWith(Instruction *I, Value *V, std::vector< Instruction *> &Worklist, Loop *L, LPPassManager *LPM)
When we find that I really equals V, remove I from the program, replacing all uses with V and update ...
static Loop * CloneLoop(Loop *L, Loop *PL, ValueToValueMapTy &VM, LoopInfo *LI, LPPassManager *LPM)
Recursively clone the specified loop and all of its children, mapping the blocks with the specified m...
This class represents the LLVM &#39;select&#39; instruction.
const DataLayout & getDataLayout() const
Get the data layout for the module&#39;s target platform.
Definition: Module.cpp:361
Option class for critical edge splitting.
int getBasicBlockIndex(const BasicBlock *BB) const
Return the first index of the specified basic block in the value list for this PHI.
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
Definition: LoopInfo.h:678
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:668
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: LICM.cpp:493
bool hasDedicatedExits() const
Return true if no exit block for the loop has a predecessor that is outside the loop.
Definition: LoopInfo.cpp:380
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:729
iterator find(const KeyT &Val)
Definition: ValueMap.h:158
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:430
ValueT lookup(const KeyT &Val) const
lookup - Return the entry for the specified key, or a default constructed value if no such entry exis...
Definition: ValueMap.h:167
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:140
Value * getOperand(unsigned i) const
Definition: User.h:154
If this flag is set, the remapper knows that only local values within a function (such as an instruct...
Definition: ValueMapper.h:73
void getUniqueExitBlocks(SmallVectorImpl< BasicBlock *> &ExitBlocks) const
Return all unique successor blocks of this loop.
Definition: LoopInfo.cpp:393
Interval::succ_iterator succ_end(Interval *I)
Definition: Interval.h:106
void replaceUsesOfWith(Value *From, Value *To)
Replace uses of one Value with another.
Definition: User.cpp:22
static Value * FindLIVLoopCondition(Value *Cond, Loop *L, bool &Changed, OperatorChain &ParentChain, DenseMap< Value *, Value *> &Cache)
Cond is a condition that occurs in L.
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:406
The landingpad instruction holds all of the information necessary to generate correct exception handl...
Subclasses of this class are all able to terminate a basic block.
Definition: InstrTypes.h:54
Wrapper pass for TargetTransformInfo.
* if(!EatIfPresent(lltok::kw_thread_local)) return false
ParseOptionalThreadLocal := /*empty.
const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
Definition: BasicBlock.cpp:217
LLVM Basic Block Representation.
Definition: BasicBlock.h:59
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h: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:116
Value * getIncomingValueForBlock(const BasicBlock *BB) const
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
Definition: SmallSet.h:36
This file contains the declarations for the subclasses of Constant, which represent the different fla...
static void RemoveFromWorklist(Instruction *I, std::vector< Instruction *> &Worklist)
Remove all instances of I from the worklist vector specified.
const Instruction & front() const
Definition: BasicBlock.h:264
Machine Trace Metrics
bool mayHaveSideEffects() const
Return true if the instruction may have side effects.
Definition: Instruction.h:535
Interval::pred_iterator pred_begin(Interval *I)
pred_begin/pred_end - define methods so that Intervals may be used just like BasicBlocks can with the...
Definition: Interval.h:113
Represent the analysis usage information of a pass.
void analyzeBasicBlock(const BasicBlock *BB, const TargetTransformInfo &TTI, const SmallPtrSetImpl< const Value *> &EphValues)
Add information about a block to the current state.
void splice(iterator where, iplist_impl &L2)
Definition: ilist.h:342
static bool isTrivialLoopExitBlockHelper(Loop *L, BasicBlock *BB, BasicBlock *&ExitBB, std::set< BasicBlock *> &Visited)
Check to see if all paths from BB exit the loop with no side effects (including infinite loops)...
This instruction compares its operands according to the predicate given to the constructor.
Interval::pred_iterator pred_end(Interval *I)
Definition: Interval.h:116
BasicBlock * SplitBlockPredecessors(BasicBlock *BB, ArrayRef< BasicBlock *> Preds, const char *Suffix, DominatorTree *DT=nullptr, LoopInfo *LI=nullptr, bool PreserveLCSSA=false)
This method introduces at least one new basic block into the function and moves some of the predecess...
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
Definition: BasicBlock.h:101
self_iterator getIterator()
Definition: ilist_node.h:82
std::pair< NoneType, bool > insert(const T &V)
insert - Insert an element into the set if it isn&#39;t already there.
Definition: SmallSet.h:81
static bool EqualityPropUnSafe(Value &LoopCond)
FIXME: Remove this workaround when freeze related patches are done.
INITIALIZE_PASS_BEGIN(LoopUnswitch, "loop-unswitch", "Unswitch loops", false, false) INITIALIZE_PASS_END(LoopUnswitch
static Constant * getAllOnesValue(Type *Ty)
Get the all ones value.
Definition: Constants.cpp:261
static UndefValue * get(Type *T)
Static factory methods - Return an &#39;undef&#39; object of the specified type.
Definition: Constants.cpp:1320
loop unswitch
void swapProfMetadata()
If the instruction has "branch_weights" MD_prof metadata and the MDNode has three operands (including...
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
unsigned first
iterator end()
Definition: ValueMap.h:138
void deleteSimpleAnalysisValue(Value *V, Loop *L)
deleteSimpleAnalysisValue - Invoke deleteAnalysisValue hook for all passes that implement simple anal...
Definition: LoopPass.cpp:105
const InstListType & getInstList() const
Return the underlying instruction list container.
Definition: BasicBlock.h:317
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
Definition: LoopInfo.h:110
Iterator for intrusive lists based on ilist_node.
unsigned getNumOperands() const
Definition: User.h:176
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
Definition: SmallPtrSet.h: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:254
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:864
bool dominates(const Instruction *Def, const Use &U) const
Return true if Def dominates a use in User.
Definition: Dominators.cpp:239
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:642
CriticalEdgeSplittingOptions & setPreserveLCSSA()
CHAIN = SC CHAIN, Imm128 - System call.
static Constant * get(Type *Ty, uint64_t V, bool isSigned=false)
If Ty is a vector type, return a Constant with a splat of the given value.
Definition: Constants.cpp:560
static BranchInst * Create(BasicBlock *IfTrue, Instruction *InsertBefore=nullptr)
bool isConditional() const
static PHINode * Create(Type *Ty, unsigned NumReservedValues, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
Constructors - NumReservedValues is a hint for the number of incoming edges that this phi node will h...
CaseIt findCaseValue(const ConstantInt *C)
Search all of the case values for the specified constant.
static ConstantInt * getTrue(LLVMContext &Context)
Definition: Constants.cpp:516
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:923
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:401
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:65
LoopT * getParentLoop() const
Definition: LoopInfo.h:101
Predicate getPredicate() const
Return the predicate for this instruction.
Definition: InstrTypes.h:927
LLVM_ATTRIBUTE_ALWAYS_INLINE iterator end()
Definition: SmallVector.h:120
Captures loop safety information.
Definition: LoopUtils.h:51
void registerAssumption(CallInst *CI)
Add an .assume intrinsic to this function&#39;s cache.
void addChildLoop(LoopT *NewChild)
Add the specified loop to be a child of this loop.
Definition: LoopInfo.h:311
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:439
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:220
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:108
SymbolTableList< BasicBlock >::iterator eraseFromParent()
Unlink &#39;this&#39; from the containing function and delete it.
Definition: BasicBlock.cpp:97
#define I(x, y, z)
Definition: MD5.cpp:58
DomTreeNodeBase< NodeT > * addNewBlock(NodeT *BB, NodeT *DomBB)
Add a new node to the dominator tree information.
void addLoop(Loop &L)
Definition: LoopPass.cpp: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:1023
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:565
block_iterator block_end() const
Definition: LoopInfo.h:155
bool isSafeToClone() const
Return true if the loop body is safe to clone in practice.
Definition: LoopInfo.cpp:198
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:324
LLVM Value Representation.
Definition: Value.h:73
There are only ORs.
#define DEBUG(X)
Definition: Debug.h:118
BasicBlock * SplitEdge(BasicBlock *From, BasicBlock *To, DominatorTree *DT=nullptr, LoopInfo *LI=nullptr)
Split the edge connecting specified block.
const LandingPadInst * getLandingPadInst() const
Return the landingpad instruction associated with the landing pad.
Definition: BasicBlock.cpp:447
bool replacementPreservesLCSSAForm(Instruction *From, Value *To)
Returns true if replacing From with To everywhere is guaranteed to preserve LCSSA form...
Definition: LoopInfo.h:820
This pass exposes codegen information to IR-level passes.
const TerminatorInst * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
Definition: BasicBlock.cpp:120
void setIncomingValue(unsigned i, Value *V)
unsigned NumInsts
Number of instructions in the analyzed blocks.
Definition: CodeMetrics.h:63
iterator_range< block_iterator > blocks() const
Definition: LoopInfo.h: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. ...
Definition: LoopUtils.cpp:1264
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:737
A wrapper class for inspecting calls to intrinsic functions.
Definition: IntrinsicInst.h:44
const BasicBlock * getParent() const
Definition: Instruction.h:66