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