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  MemorySSAUpdater *MSSAU) {
425  auto CacheIt = Cache.find(Cond);
426  if (CacheIt != Cache.end())
427  return CacheIt->second;
428 
429  // We started analyze new instruction, increment scanned instructions counter.
430  ++TotalInsts;
431 
432  // We can never unswitch on vector conditions.
433  if (Cond->getType()->isVectorTy())
434  return nullptr;
435 
436  // Constants should be folded, not unswitched on!
437  if (isa<Constant>(Cond)) return nullptr;
438 
439  // TODO: Handle: br (VARIANT|INVARIANT).
440 
441  // Hoist simple values out.
442  if (L->makeLoopInvariant(Cond, Changed, nullptr, MSSAU)) {
443  Cache[Cond] = Cond;
444  return Cond;
445  }
446 
447  // Walk up the operator chain to find partial invariant conditions.
448  if (BinaryOperator *BO = dyn_cast<BinaryOperator>(Cond))
449  if (BO->getOpcode() == Instruction::And ||
450  BO->getOpcode() == Instruction::Or) {
451  // Given the previous operator, compute the current operator chain status.
452  OperatorChain NewChain;
453  switch (ParentChain) {
454  case OC_OpChainNone:
455  NewChain = BO->getOpcode() == Instruction::And ? OC_OpChainAnd :
456  OC_OpChainOr;
457  break;
458  case OC_OpChainOr:
459  NewChain = BO->getOpcode() == Instruction::Or ? OC_OpChainOr :
461  break;
462  case OC_OpChainAnd:
463  NewChain = BO->getOpcode() == Instruction::And ? OC_OpChainAnd :
465  break;
466  case OC_OpChainMixed:
467  NewChain = OC_OpChainMixed;
468  break;
469  }
470 
471  // If we reach a Mixed state, we do not want to keep walking up as we can not
472  // reliably find a value that will simplify the chain. With this check, we
473  // will return null on the first sight of mixed chain and the caller will
474  // either backtrack to find partial LIV in other operand or return null.
475  if (NewChain != OC_OpChainMixed) {
476  // Update the current operator chain type before we search up the chain.
477  ParentChain = NewChain;
478  // If either the left or right side is invariant, we can unswitch on this,
479  // which will cause the branch to go away in one loop and the condition to
480  // simplify in the other one.
481  if (Value *LHS = FindLIVLoopCondition(BO->getOperand(0), L, Changed,
482  ParentChain, Cache, MSSAU)) {
483  Cache[Cond] = LHS;
484  return LHS;
485  }
486  // We did not manage to find a partial LIV in operand(0). Backtrack and try
487  // operand(1).
488  ParentChain = NewChain;
489  if (Value *RHS = FindLIVLoopCondition(BO->getOperand(1), L, Changed,
490  ParentChain, Cache, MSSAU)) {
491  Cache[Cond] = RHS;
492  return RHS;
493  }
494  }
495  }
496 
497  Cache[Cond] = nullptr;
498  return nullptr;
499 }
500 
501 /// Cond is a condition that occurs in L. If it is invariant in the loop, or has
502 /// an invariant piece, return the invariant along with the operator chain type.
503 /// Otherwise, return null.
504 static std::pair<Value *, OperatorChain>
505 FindLIVLoopCondition(Value *Cond, Loop *L, bool &Changed,
506  MemorySSAUpdater *MSSAU) {
508  OperatorChain OpChain = OC_OpChainNone;
509  Value *FCond = FindLIVLoopCondition(Cond, L, Changed, OpChain, Cache, MSSAU);
510 
511  // In case we do find a LIV, it can not be obtained by walking up a mixed
512  // operator chain.
513  assert((!FCond || OpChain != OC_OpChainMixed) &&
514  "Do not expect a partial LIV with mixed operator chain");
515  return {FCond, OpChain};
516 }
517 
518 bool LoopUnswitch::runOnLoop(Loop *L, LPPassManager &LPM_Ref) {
519  if (skipLoop(L))
520  return false;
521 
522  AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(
523  *L->getHeader()->getParent());
524  LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
525  LPM = &LPM_Ref;
526  DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
528  MSSA = &getAnalysis<MemorySSAWrapperPass>().getMSSA();
529  MSSAU = std::make_unique<MemorySSAUpdater>(MSSA);
530  assert(DT && "Cannot update MemorySSA without a valid DomTree.");
531  }
532  currentLoop = L;
533  Function *F = currentLoop->getHeader()->getParent();
534 
535  SanitizeMemory = F->hasFnAttribute(Attribute::SanitizeMemory);
536  if (SanitizeMemory)
537  SafetyInfo.computeLoopSafetyInfo(L);
538 
539  if (MSSA && VerifyMemorySSA)
540  MSSA->verifyMemorySSA();
541 
542  bool Changed = false;
543  do {
544  assert(currentLoop->isLCSSAForm(*DT));
545  if (MSSA && VerifyMemorySSA)
546  MSSA->verifyMemorySSA();
547  redoLoop = false;
548  Changed |= processCurrentLoop();
549  } while(redoLoop);
550 
551  if (MSSA && VerifyMemorySSA)
552  MSSA->verifyMemorySSA();
553 
554  return Changed;
555 }
556 
557 // Return true if the BasicBlock BB is unreachable from the loop header.
558 // Return false, otherwise.
559 bool LoopUnswitch::isUnreachableDueToPreviousUnswitching(BasicBlock *BB) {
560  auto *Node = DT->getNode(BB)->getIDom();
561  BasicBlock *DomBB = Node->getBlock();
562  while (currentLoop->contains(DomBB)) {
563  BranchInst *BInst = dyn_cast<BranchInst>(DomBB->getTerminator());
564 
565  Node = DT->getNode(DomBB)->getIDom();
566  DomBB = Node->getBlock();
567 
568  if (!BInst || !BInst->isConditional())
569  continue;
570 
571  Value *Cond = BInst->getCondition();
572  if (!isa<ConstantInt>(Cond))
573  continue;
574 
575  BasicBlock *UnreachableSucc =
576  Cond == ConstantInt::getTrue(Cond->getContext())
577  ? BInst->getSuccessor(1)
578  : BInst->getSuccessor(0);
579 
580  if (DT->dominates(UnreachableSucc, BB))
581  return true;
582  }
583  return false;
584 }
585 
586 /// FIXME: Remove this workaround when freeze related patches are done.
587 /// LoopUnswitch and Equality propagation in GVN have discrepancy about
588 /// whether branch on undef/poison has undefine behavior. Here it is to
589 /// rule out some common cases that we found such discrepancy already
590 /// causing problems. Detail could be found in PR31652. Note if the
591 /// func returns true, it is unsafe. But if it is false, it doesn't mean
592 /// it is necessarily safe.
593 static bool EqualityPropUnSafe(Value &LoopCond) {
594  ICmpInst *CI = dyn_cast<ICmpInst>(&LoopCond);
595  if (!CI || !CI->isEquality())
596  return false;
597 
598  Value *LHS = CI->getOperand(0);
599  Value *RHS = CI->getOperand(1);
600  if (isa<UndefValue>(LHS) || isa<UndefValue>(RHS))
601  return true;
602 
603  auto hasUndefInPHI = [](PHINode &PN) {
604  for (Value *Opd : PN.incoming_values()) {
605  if (isa<UndefValue>(Opd))
606  return true;
607  }
608  return false;
609  };
610  PHINode *LPHI = dyn_cast<PHINode>(LHS);
611  PHINode *RPHI = dyn_cast<PHINode>(RHS);
612  if ((LPHI && hasUndefInPHI(*LPHI)) || (RPHI && hasUndefInPHI(*RPHI)))
613  return true;
614 
615  auto hasUndefInSelect = [](SelectInst &SI) {
616  if (isa<UndefValue>(SI.getTrueValue()) ||
617  isa<UndefValue>(SI.getFalseValue()))
618  return true;
619  return false;
620  };
621  SelectInst *LSI = dyn_cast<SelectInst>(LHS);
622  SelectInst *RSI = dyn_cast<SelectInst>(RHS);
623  if ((LSI && hasUndefInSelect(*LSI)) || (RSI && hasUndefInSelect(*RSI)))
624  return true;
625  return false;
626 }
627 
628 /// Do actual work and unswitch loop if possible and profitable.
629 bool LoopUnswitch::processCurrentLoop() {
630  bool Changed = false;
631 
632  initLoopData();
633 
634  // If LoopSimplify was unable to form a preheader, don't do any unswitching.
635  if (!loopPreheader)
636  return false;
637 
638  // Loops with indirectbr cannot be cloned.
639  if (!currentLoop->isSafeToClone())
640  return false;
641 
642  // Without dedicated exits, splitting the exit edge may fail.
643  if (!currentLoop->hasDedicatedExits())
644  return false;
645 
646  LLVMContext &Context = loopHeader->getContext();
647 
648  // Analyze loop cost, and stop unswitching if loop content can not be duplicated.
649  if (!BranchesInfo.countLoop(
650  currentLoop, getAnalysis<TargetTransformInfoWrapperPass>().getTTI(
651  *currentLoop->getHeader()->getParent()),
652  AC))
653  return false;
654 
655  // Try trivial unswitch first before loop over other basic blocks in the loop.
656  if (TryTrivialLoopUnswitch(Changed)) {
657  return true;
658  }
659 
660  // Do not do non-trivial unswitch while optimizing for size.
661  // FIXME: Use Function::hasOptSize().
662  if (OptimizeForSize ||
663  loopHeader->getParent()->hasFnAttribute(Attribute::OptimizeForSize))
664  return false;
665 
666  // Run through the instructions in the loop, keeping track of three things:
667  //
668  // - That we do not unswitch loops containing convergent operations, as we
669  // might be making them control dependent on the unswitch value when they
670  // were not before.
671  // FIXME: This could be refined to only bail if the convergent operation is
672  // not already control-dependent on the unswitch value.
673  //
674  // - That basic blocks in the loop contain invokes whose predecessor edges we
675  // cannot split.
676  //
677  // - The set of guard intrinsics encountered (these are non terminator
678  // instructions that are also profitable to be unswitched).
679 
681 
682  for (const auto BB : currentLoop->blocks()) {
683  for (auto &I : *BB) {
684  auto CS = CallSite(&I);
685  if (!CS) continue;
686  if (CS.hasFnAttr(Attribute::Convergent))
687  return false;
688  if (auto *II = dyn_cast<InvokeInst>(&I))
689  if (!II->getUnwindDest()->canSplitPredecessors())
690  return false;
691  if (auto *II = dyn_cast<IntrinsicInst>(&I))
692  if (II->getIntrinsicID() == Intrinsic::experimental_guard)
693  Guards.push_back(II);
694  }
695  }
696 
697  for (IntrinsicInst *Guard : Guards) {
698  Value *LoopCond = FindLIVLoopCondition(Guard->getOperand(0), currentLoop,
699  Changed, MSSAU.get())
700  .first;
701  if (LoopCond &&
702  UnswitchIfProfitable(LoopCond, ConstantInt::getTrue(Context))) {
703  // NB! Unswitching (if successful) could have erased some of the
704  // instructions in Guards leaving dangling pointers there. This is fine
705  // because we're returning now, and won't look at Guards again.
706  ++NumGuards;
707  return true;
708  }
709  }
710 
711  // Loop over all of the basic blocks in the loop. If we find an interior
712  // block that is branching on a loop-invariant condition, we can unswitch this
713  // loop.
714  for (Loop::block_iterator I = currentLoop->block_begin(),
715  E = currentLoop->block_end(); I != E; ++I) {
716  Instruction *TI = (*I)->getTerminator();
717 
718  // Unswitching on a potentially uninitialized predicate is not
719  // MSan-friendly. Limit this to the cases when the original predicate is
720  // guaranteed to execute, to avoid creating a use-of-uninitialized-value
721  // in the code that did not have one.
722  // This is a workaround for the discrepancy between LLVM IR and MSan
723  // semantics. See PR28054 for more details.
724  if (SanitizeMemory &&
725  !SafetyInfo.isGuaranteedToExecute(*TI, DT, currentLoop))
726  continue;
727 
728  if (BranchInst *BI = dyn_cast<BranchInst>(TI)) {
729  // Some branches may be rendered unreachable because of previous
730  // unswitching.
731  // Unswitch only those branches that are reachable.
732  if (isUnreachableDueToPreviousUnswitching(*I))
733  continue;
734 
735  // If this isn't branching on an invariant condition, we can't unswitch
736  // it.
737  if (BI->isConditional()) {
738  // See if this, or some part of it, is loop invariant. If so, we can
739  // unswitch on it if we desire.
740  Value *LoopCond = FindLIVLoopCondition(BI->getCondition(), currentLoop,
741  Changed, MSSAU.get())
742  .first;
743  if (LoopCond && !EqualityPropUnSafe(*LoopCond) &&
744  UnswitchIfProfitable(LoopCond, ConstantInt::getTrue(Context), TI)) {
745  ++NumBranches;
746  return true;
747  }
748  }
749  } else if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
750  Value *SC = SI->getCondition();
751  Value *LoopCond;
752  OperatorChain OpChain;
753  std::tie(LoopCond, OpChain) =
754  FindLIVLoopCondition(SC, currentLoop, Changed, MSSAU.get());
755 
756  unsigned NumCases = SI->getNumCases();
757  if (LoopCond && NumCases) {
758  // Find a value to unswitch on:
759  // FIXME: this should chose the most expensive case!
760  // FIXME: scan for a case with a non-critical edge?
761  Constant *UnswitchVal = nullptr;
762  // Find a case value such that at least one case value is unswitched
763  // out.
764  if (OpChain == OC_OpChainAnd) {
765  // If the chain only has ANDs and the switch has a case value of 0.
766  // Dropping in a 0 to the chain will unswitch out the 0-casevalue.
767  auto *AllZero = cast<ConstantInt>(Constant::getNullValue(SC->getType()));
768  if (BranchesInfo.isUnswitched(SI, AllZero))
769  continue;
770  // We are unswitching 0 out.
771  UnswitchVal = AllZero;
772  } else if (OpChain == OC_OpChainOr) {
773  // If the chain only has ORs and the switch has a case value of ~0.
774  // Dropping in a ~0 to the chain will unswitch out the ~0-casevalue.
775  auto *AllOne = cast<ConstantInt>(Constant::getAllOnesValue(SC->getType()));
776  if (BranchesInfo.isUnswitched(SI, AllOne))
777  continue;
778  // We are unswitching ~0 out.
779  UnswitchVal = AllOne;
780  } else {
781  assert(OpChain == OC_OpChainNone &&
782  "Expect to unswitch on trivial chain");
783  // Do not process same value again and again.
784  // At this point we have some cases already unswitched and
785  // some not yet unswitched. Let's find the first not yet unswitched one.
786  for (auto Case : SI->cases()) {
787  Constant *UnswitchValCandidate = Case.getCaseValue();
788  if (!BranchesInfo.isUnswitched(SI, UnswitchValCandidate)) {
789  UnswitchVal = UnswitchValCandidate;
790  break;
791  }
792  }
793  }
794 
795  if (!UnswitchVal)
796  continue;
797 
798  if (UnswitchIfProfitable(LoopCond, UnswitchVal)) {
799  ++NumSwitches;
800  // In case of a full LIV, UnswitchVal is the value we unswitched out.
801  // In case of a partial LIV, we only unswitch when its an AND-chain
802  // or OR-chain. In both cases switch input value simplifies to
803  // UnswitchVal.
804  BranchesInfo.setUnswitched(SI, UnswitchVal);
805  return true;
806  }
807  }
808  }
809 
810  // Scan the instructions to check for unswitchable values.
811  for (BasicBlock::iterator BBI = (*I)->begin(), E = (*I)->end();
812  BBI != E; ++BBI)
813  if (SelectInst *SI = dyn_cast<SelectInst>(BBI)) {
814  Value *LoopCond = FindLIVLoopCondition(SI->getCondition(), currentLoop,
815  Changed, MSSAU.get())
816  .first;
817  if (LoopCond && UnswitchIfProfitable(LoopCond,
818  ConstantInt::getTrue(Context))) {
819  ++NumSelects;
820  return true;
821  }
822  }
823  }
824  return Changed;
825 }
826 
827 /// Check to see if all paths from BB exit the loop with no side effects
828 /// (including infinite loops).
829 ///
830 /// If true, we return true and set ExitBB to the block we
831 /// exit through.
832 ///
834  BasicBlock *&ExitBB,
835  std::set<BasicBlock*> &Visited) {
836  if (!Visited.insert(BB).second) {
837  // Already visited. Without more analysis, this could indicate an infinite
838  // loop.
839  return false;
840  }
841  if (!L->contains(BB)) {
842  // Otherwise, this is a loop exit, this is fine so long as this is the
843  // first exit.
844  if (ExitBB) return false;
845  ExitBB = BB;
846  return true;
847  }
848 
849  // Otherwise, this is an unvisited intra-loop node. Check all successors.
850  for (succ_iterator SI = succ_begin(BB), E = succ_end(BB); SI != E; ++SI) {
851  // Check to see if the successor is a trivial loop exit.
852  if (!isTrivialLoopExitBlockHelper(L, *SI, ExitBB, Visited))
853  return false;
854  }
855 
856  // Okay, everything after this looks good, check to make sure that this block
857  // doesn't include any side effects.
858  for (Instruction &I : *BB)
859  if (I.mayHaveSideEffects())
860  return false;
861 
862  return true;
863 }
864 
865 /// Return true if the specified block unconditionally leads to an exit from
866 /// the specified loop, and has no side-effects in the process. If so, return
867 /// the block that is exited to, otherwise return null.
869  std::set<BasicBlock*> Visited;
870  Visited.insert(L->getHeader()); // Branches to header make infinite loops.
871  BasicBlock *ExitBB = nullptr;
872  if (isTrivialLoopExitBlockHelper(L, BB, ExitBB, Visited))
873  return ExitBB;
874  return nullptr;
875 }
876 
877 /// We have found that we can unswitch currentLoop when LoopCond == Val to
878 /// simplify the loop. If we decide that this is profitable,
879 /// unswitch the loop, reprocess the pieces, then return true.
880 bool LoopUnswitch::UnswitchIfProfitable(Value *LoopCond, Constant *Val,
881  Instruction *TI) {
882  // Check to see if it would be profitable to unswitch current loop.
883  if (!BranchesInfo.CostAllowsUnswitching()) {
884  LLVM_DEBUG(dbgs() << "NOT unswitching loop %"
885  << currentLoop->getHeader()->getName()
886  << " at non-trivial condition '" << *Val
887  << "' == " << *LoopCond << "\n"
888  << ". Cost too high.\n");
889  return false;
890  }
891  if (hasBranchDivergence &&
892  getAnalysis<LegacyDivergenceAnalysis>().isDivergent(LoopCond)) {
893  LLVM_DEBUG(dbgs() << "NOT unswitching loop %"
894  << currentLoop->getHeader()->getName()
895  << " at non-trivial condition '" << *Val
896  << "' == " << *LoopCond << "\n"
897  << ". Condition is divergent.\n");
898  return false;
899  }
900 
901  UnswitchNontrivialCondition(LoopCond, Val, currentLoop, TI);
902  return true;
903 }
904 
905 /// Recursively clone the specified loop and all of its children,
906 /// mapping the blocks with the specified map.
908  LoopInfo *LI, LPPassManager *LPM) {
909  Loop &New = *LI->AllocateLoop();
910  if (PL)
911  PL->addChildLoop(&New);
912  else
913  LI->addTopLevelLoop(&New);
914  LPM->addLoop(New);
915 
916  // Add all of the blocks in L to the new loop.
917  for (Loop::block_iterator I = L->block_begin(), E = L->block_end();
918  I != E; ++I)
919  if (LI->getLoopFor(*I) == L)
920  New.addBasicBlockToLoop(cast<BasicBlock>(VM[*I]), *LI);
921 
922  // Add all of the subloops to the new loop.
923  for (Loop *I : *L)
924  CloneLoop(I, &New, VM, LI, LPM);
925 
926  return &New;
927 }
928 
929 /// Emit a conditional branch on two values if LIC == Val, branch to TrueDst,
930 /// otherwise branch to FalseDest. Insert the code immediately before OldBranch
931 /// and remove (but not erase!) it from the function.
932 void LoopUnswitch::EmitPreheaderBranchOnCondition(Value *LIC, Constant *Val,
933  BasicBlock *TrueDest,
934  BasicBlock *FalseDest,
935  BranchInst *OldBranch,
936  Instruction *TI) {
937  assert(OldBranch->isUnconditional() && "Preheader is not split correctly");
938  assert(TrueDest != FalseDest && "Branch targets should be different");
939  // Insert a conditional branch on LIC to the two preheaders. The original
940  // code is the true version and the new code is the false version.
941  Value *BranchVal = LIC;
942  bool Swapped = false;
943  if (!isa<ConstantInt>(Val) ||
944  Val->getType() != Type::getInt1Ty(LIC->getContext()))
945  BranchVal = new ICmpInst(OldBranch, ICmpInst::ICMP_EQ, LIC, Val);
946  else if (Val != ConstantInt::getTrue(Val->getContext())) {
947  // We want to enter the new loop when the condition is true.
948  std::swap(TrueDest, FalseDest);
949  Swapped = true;
950  }
951 
952  // Old branch will be removed, so save its parent and successor to update the
953  // DomTree.
954  auto *OldBranchSucc = OldBranch->getSuccessor(0);
955  auto *OldBranchParent = OldBranch->getParent();
956 
957  // Insert the new branch.
958  BranchInst *BI =
959  IRBuilder<>(OldBranch).CreateCondBr(BranchVal, TrueDest, FalseDest, TI);
960  if (Swapped)
961  BI->swapProfMetadata();
962 
963  // Remove the old branch so there is only one branch at the end. This is
964  // needed to perform DomTree's internal DFS walk on the function's CFG.
965  OldBranch->removeFromParent();
966 
967  // Inform the DT about the new branch.
968  if (DT) {
969  // First, add both successors.
971  if (TrueDest != OldBranchSucc)
972  Updates.push_back({DominatorTree::Insert, OldBranchParent, TrueDest});
973  if (FalseDest != OldBranchSucc)
974  Updates.push_back({DominatorTree::Insert, OldBranchParent, FalseDest});
975  // If both of the new successors are different from the old one, inform the
976  // DT that the edge was deleted.
977  if (OldBranchSucc != TrueDest && OldBranchSucc != FalseDest) {
978  Updates.push_back({DominatorTree::Delete, OldBranchParent, OldBranchSucc});
979  }
980  DT->applyUpdates(Updates);
981 
982  if (MSSAU)
983  MSSAU->applyUpdates(Updates, *DT);
984  }
985 
986  // If either edge is critical, split it. This helps preserve LoopSimplify
987  // form for enclosing loops.
988  auto Options =
989  CriticalEdgeSplittingOptions(DT, LI, MSSAU.get()).setPreserveLCSSA();
990  SplitCriticalEdge(BI, 0, Options);
991  SplitCriticalEdge(BI, 1, Options);
992 }
993 
994 /// Given a loop that has a trivial unswitchable condition in it (a cond branch
995 /// from its header block to its latch block, where the path through the loop
996 /// that doesn't execute its body has no side-effects), unswitch it. This
997 /// doesn't involve any code duplication, just moving the conditional branch
998 /// outside of the loop and updating loop info.
999 void LoopUnswitch::UnswitchTrivialCondition(Loop *L, Value *Cond, Constant *Val,
1000  BasicBlock *ExitBlock,
1001  Instruction *TI) {
1002  LLVM_DEBUG(dbgs() << "loop-unswitch: Trivial-Unswitch loop %"
1003  << loopHeader->getName() << " [" << L->getBlocks().size()
1004  << " blocks] in Function "
1005  << L->getHeader()->getParent()->getName()
1006  << " on cond: " << *Val << " == " << *Cond << "\n");
1007  // We are going to make essential changes to CFG. This may invalidate cached
1008  // information for L or one of its parent loops in SCEV.
1009  if (auto *SEWP = getAnalysisIfAvailable<ScalarEvolutionWrapperPass>())
1010  SEWP->getSE().forgetTopmostLoop(L);
1011 
1012  // First step, split the preheader, so that we know that there is a safe place
1013  // to insert the conditional branch. We will change loopPreheader to have a
1014  // conditional branch on Cond.
1015  BasicBlock *NewPH = SplitEdge(loopPreheader, loopHeader, DT, LI, MSSAU.get());
1016 
1017  // Now that we have a place to insert the conditional branch, create a place
1018  // to branch to: this is the exit block out of the loop that we should
1019  // short-circuit to.
1020 
1021  // Split this block now, so that the loop maintains its exit block, and so
1022  // that the jump from the preheader can execute the contents of the exit block
1023  // without actually branching to it (the exit block should be dominated by the
1024  // loop header, not the preheader).
1025  assert(!L->contains(ExitBlock) && "Exit block is in the loop?");
1026  BasicBlock *NewExit =
1027  SplitBlock(ExitBlock, &ExitBlock->front(), DT, LI, MSSAU.get());
1028 
1029  // Okay, now we have a position to branch from and a position to branch to,
1030  // insert the new conditional branch.
1031  auto *OldBranch = dyn_cast<BranchInst>(loopPreheader->getTerminator());
1032  assert(OldBranch && "Failed to split the preheader");
1033  EmitPreheaderBranchOnCondition(Cond, Val, NewExit, NewPH, OldBranch, TI);
1034  LPM->deleteSimpleAnalysisValue(OldBranch, L);
1035 
1036  // EmitPreheaderBranchOnCondition removed the OldBranch from the function.
1037  // Delete it, as it is no longer needed.
1038  delete OldBranch;
1039 
1040  // We need to reprocess this loop, it could be unswitched again.
1041  redoLoop = true;
1042 
1043  // Now that we know that the loop is never entered when this condition is a
1044  // particular value, rewrite the loop with this info. We know that this will
1045  // at least eliminate the old branch.
1046  RewriteLoopBodyWithConditionConstant(L, Cond, Val, false);
1047 
1048  ++NumTrivial;
1049 }
1050 
1051 /// Check if the first non-constant condition starting from the loop header is
1052 /// a trivial unswitch condition: that is, a condition controls whether or not
1053 /// the loop does anything at all. If it is a trivial condition, unswitching
1054 /// produces no code duplications (equivalently, it produces a simpler loop and
1055 /// a new empty loop, which gets deleted). Therefore always unswitch trivial
1056 /// condition.
1057 bool LoopUnswitch::TryTrivialLoopUnswitch(bool &Changed) {
1058  BasicBlock *CurrentBB = currentLoop->getHeader();
1059  Instruction *CurrentTerm = CurrentBB->getTerminator();
1060  LLVMContext &Context = CurrentBB->getContext();
1061 
1062  // If loop header has only one reachable successor (currently via an
1063  // unconditional branch or constant foldable conditional branch, but
1064  // should also consider adding constant foldable switch instruction in
1065  // future), we should keep looking for trivial condition candidates in
1066  // the successor as well. An alternative is to constant fold conditions
1067  // and merge successors into loop header (then we only need to check header's
1068  // terminator). The reason for not doing this in LoopUnswitch pass is that
1069  // it could potentially break LoopPassManager's invariants. Folding dead
1070  // branches could either eliminate the current loop or make other loops
1071  // unreachable. LCSSA form might also not be preserved after deleting
1072  // branches. The following code keeps traversing loop header's successors
1073  // until it finds the trivial condition candidate (condition that is not a
1074  // constant). Since unswitching generates branches with constant conditions,
1075  // this scenario could be very common in practice.
1077 
1078  while (true) {
1079  // If we exit loop or reach a previous visited block, then
1080  // we can not reach any trivial condition candidates (unfoldable
1081  // branch instructions or switch instructions) and no unswitch
1082  // can happen. Exit and return false.
1083  if (!currentLoop->contains(CurrentBB) || !Visited.insert(CurrentBB).second)
1084  return false;
1085 
1086  // Check if this loop will execute any side-effecting instructions (e.g.
1087  // stores, calls, volatile loads) in the part of the loop that the code
1088  // *would* execute. Check the header first.
1089  for (Instruction &I : *CurrentBB)
1090  if (I.mayHaveSideEffects())
1091  return false;
1092 
1093  if (BranchInst *BI = dyn_cast<BranchInst>(CurrentTerm)) {
1094  if (BI->isUnconditional()) {
1095  CurrentBB = BI->getSuccessor(0);
1096  } else if (BI->getCondition() == ConstantInt::getTrue(Context)) {
1097  CurrentBB = BI->getSuccessor(0);
1098  } else if (BI->getCondition() == ConstantInt::getFalse(Context)) {
1099  CurrentBB = BI->getSuccessor(1);
1100  } else {
1101  // Found a trivial condition candidate: non-foldable conditional branch.
1102  break;
1103  }
1104  } else if (SwitchInst *SI = dyn_cast<SwitchInst>(CurrentTerm)) {
1105  // At this point, any constant-foldable instructions should have probably
1106  // been folded.
1107  ConstantInt *Cond = dyn_cast<ConstantInt>(SI->getCondition());
1108  if (!Cond)
1109  break;
1110  // Find the target block we are definitely going to.
1111  CurrentBB = SI->findCaseValue(Cond)->getCaseSuccessor();
1112  } else {
1113  // We do not understand these terminator instructions.
1114  break;
1115  }
1116 
1117  CurrentTerm = CurrentBB->getTerminator();
1118  }
1119 
1120  // CondVal is the condition that controls the trivial condition.
1121  // LoopExitBB is the BasicBlock that loop exits when meets trivial condition.
1122  Constant *CondVal = nullptr;
1123  BasicBlock *LoopExitBB = nullptr;
1124 
1125  if (BranchInst *BI = dyn_cast<BranchInst>(CurrentTerm)) {
1126  // If this isn't branching on an invariant condition, we can't unswitch it.
1127  if (!BI->isConditional())
1128  return false;
1129 
1130  Value *LoopCond = FindLIVLoopCondition(BI->getCondition(), currentLoop,
1131  Changed, MSSAU.get())
1132  .first;
1133 
1134  // Unswitch only if the trivial condition itself is an LIV (not
1135  // partial LIV which could occur in and/or)
1136  if (!LoopCond || LoopCond != BI->getCondition())
1137  return false;
1138 
1139  // Check to see if a successor of the branch is guaranteed to
1140  // exit through a unique exit block without having any
1141  // side-effects. If so, determine the value of Cond that causes
1142  // it to do this.
1143  if ((LoopExitBB = isTrivialLoopExitBlock(currentLoop,
1144  BI->getSuccessor(0)))) {
1145  CondVal = ConstantInt::getTrue(Context);
1146  } else if ((LoopExitBB = isTrivialLoopExitBlock(currentLoop,
1147  BI->getSuccessor(1)))) {
1148  CondVal = ConstantInt::getFalse(Context);
1149  }
1150 
1151  // If we didn't find a single unique LoopExit block, or if the loop exit
1152  // block contains phi nodes, this isn't trivial.
1153  if (!LoopExitBB || isa<PHINode>(LoopExitBB->begin()))
1154  return false; // Can't handle this.
1155 
1156  if (EqualityPropUnSafe(*LoopCond))
1157  return false;
1158 
1159  UnswitchTrivialCondition(currentLoop, LoopCond, CondVal, LoopExitBB,
1160  CurrentTerm);
1161  ++NumBranches;
1162  return true;
1163  } else if (SwitchInst *SI = dyn_cast<SwitchInst>(CurrentTerm)) {
1164  // If this isn't switching on an invariant condition, we can't unswitch it.
1165  Value *LoopCond = FindLIVLoopCondition(SI->getCondition(), currentLoop,
1166  Changed, MSSAU.get())
1167  .first;
1168 
1169  // Unswitch only if the trivial condition itself is an LIV (not
1170  // partial LIV which could occur in and/or)
1171  if (!LoopCond || LoopCond != SI->getCondition())
1172  return false;
1173 
1174  // Check to see if a successor of the switch is guaranteed to go to the
1175  // latch block or exit through a one exit block without having any
1176  // side-effects. If so, determine the value of Cond that causes it to do
1177  // this.
1178  // Note that we can't trivially unswitch on the default case or
1179  // on already unswitched cases.
1180  for (auto Case : SI->cases()) {
1181  BasicBlock *LoopExitCandidate;
1182  if ((LoopExitCandidate =
1183  isTrivialLoopExitBlock(currentLoop, Case.getCaseSuccessor()))) {
1184  // Okay, we found a trivial case, remember the value that is trivial.
1185  ConstantInt *CaseVal = Case.getCaseValue();
1186 
1187  // Check that it was not unswitched before, since already unswitched
1188  // trivial vals are looks trivial too.
1189  if (BranchesInfo.isUnswitched(SI, CaseVal))
1190  continue;
1191  LoopExitBB = LoopExitCandidate;
1192  CondVal = CaseVal;
1193  break;
1194  }
1195  }
1196 
1197  // If we didn't find a single unique LoopExit block, or if the loop exit
1198  // block contains phi nodes, this isn't trivial.
1199  if (!LoopExitBB || isa<PHINode>(LoopExitBB->begin()))
1200  return false; // Can't handle this.
1201 
1202  UnswitchTrivialCondition(currentLoop, LoopCond, CondVal, LoopExitBB,
1203  nullptr);
1204 
1205  // We are only unswitching full LIV.
1206  BranchesInfo.setUnswitched(SI, CondVal);
1207  ++NumSwitches;
1208  return true;
1209  }
1210  return false;
1211 }
1212 
1213 /// Split all of the edges from inside the loop to their exit blocks.
1214 /// Update the appropriate Phi nodes as we do so.
1215 void LoopUnswitch::SplitExitEdges(Loop *L,
1216  const SmallVectorImpl<BasicBlock *> &ExitBlocks){
1217 
1218  for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) {
1219  BasicBlock *ExitBlock = ExitBlocks[i];
1220  SmallVector<BasicBlock *, 4> Preds(pred_begin(ExitBlock),
1221  pred_end(ExitBlock));
1222 
1223  // Although SplitBlockPredecessors doesn't preserve loop-simplify in
1224  // general, if we call it on all predecessors of all exits then it does.
1225  SplitBlockPredecessors(ExitBlock, Preds, ".us-lcssa", DT, LI, MSSAU.get(),
1226  /*PreserveLCSSA*/ true);
1227  }
1228 }
1229 
1230 /// We determined that the loop is profitable to unswitch when LIC equal Val.
1231 /// Split it into loop versions and test the condition outside of either loop.
1232 /// Return the loops created as Out1/Out2.
1233 void LoopUnswitch::UnswitchNontrivialCondition(Value *LIC, Constant *Val,
1234  Loop *L, Instruction *TI) {
1235  Function *F = loopHeader->getParent();
1236  LLVM_DEBUG(dbgs() << "loop-unswitch: Unswitching loop %"
1237  << loopHeader->getName() << " [" << L->getBlocks().size()
1238  << " blocks] in Function " << F->getName() << " when '"
1239  << *Val << "' == " << *LIC << "\n");
1240 
1241  // We are going to make essential changes to CFG. This may invalidate cached
1242  // information for L or one of its parent loops in SCEV.
1243  if (auto *SEWP = getAnalysisIfAvailable<ScalarEvolutionWrapperPass>())
1244  SEWP->getSE().forgetTopmostLoop(L);
1245 
1246  LoopBlocks.clear();
1247  NewBlocks.clear();
1248 
1249  if (MSSAU && VerifyMemorySSA)
1250  MSSA->verifyMemorySSA();
1251 
1252  // First step, split the preheader and exit blocks, and add these blocks to
1253  // the LoopBlocks list.
1254  BasicBlock *NewPreheader =
1255  SplitEdge(loopPreheader, loopHeader, DT, LI, MSSAU.get());
1256  LoopBlocks.push_back(NewPreheader);
1257 
1258  // We want the loop to come after the preheader, but before the exit blocks.
1259  LoopBlocks.insert(LoopBlocks.end(), L->block_begin(), L->block_end());
1260 
1261  SmallVector<BasicBlock*, 8> ExitBlocks;
1262  L->getUniqueExitBlocks(ExitBlocks);
1263 
1264  // Split all of the edges from inside the loop to their exit blocks. Update
1265  // the appropriate Phi nodes as we do so.
1266  SplitExitEdges(L, ExitBlocks);
1267 
1268  // The exit blocks may have been changed due to edge splitting, recompute.
1269  ExitBlocks.clear();
1270  L->getUniqueExitBlocks(ExitBlocks);
1271 
1272  // Add exit blocks to the loop blocks.
1273  LoopBlocks.insert(LoopBlocks.end(), ExitBlocks.begin(), ExitBlocks.end());
1274 
1275  // Next step, clone all of the basic blocks that make up the loop (including
1276  // the loop preheader and exit blocks), keeping track of the mapping between
1277  // the instructions and blocks.
1278  NewBlocks.reserve(LoopBlocks.size());
1279  ValueToValueMapTy VMap;
1280  for (unsigned i = 0, e = LoopBlocks.size(); i != e; ++i) {
1281  BasicBlock *NewBB = CloneBasicBlock(LoopBlocks[i], VMap, ".us", F);
1282 
1283  NewBlocks.push_back(NewBB);
1284  VMap[LoopBlocks[i]] = NewBB; // Keep the BB mapping.
1285  LPM->cloneBasicBlockSimpleAnalysis(LoopBlocks[i], NewBB, L);
1286  }
1287 
1288  // Splice the newly inserted blocks into the function right before the
1289  // original preheader.
1290  F->getBasicBlockList().splice(NewPreheader->getIterator(),
1291  F->getBasicBlockList(),
1292  NewBlocks[0]->getIterator(), F->end());
1293 
1294  // Now we create the new Loop object for the versioned loop.
1295  Loop *NewLoop = CloneLoop(L, L->getParentLoop(), VMap, LI, LPM);
1296 
1297  // Recalculate unswitching quota, inherit simplified switches info for NewBB,
1298  // Probably clone more loop-unswitch related loop properties.
1299  BranchesInfo.cloneData(NewLoop, L, VMap);
1300 
1301  Loop *ParentLoop = L->getParentLoop();
1302  if (ParentLoop) {
1303  // Make sure to add the cloned preheader and exit blocks to the parent loop
1304  // as well.
1305  ParentLoop->addBasicBlockToLoop(NewBlocks[0], *LI);
1306  }
1307 
1308  for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) {
1309  BasicBlock *NewExit = cast<BasicBlock>(VMap[ExitBlocks[i]]);
1310  // The new exit block should be in the same loop as the old one.
1311  if (Loop *ExitBBLoop = LI->getLoopFor(ExitBlocks[i]))
1312  ExitBBLoop->addBasicBlockToLoop(NewExit, *LI);
1313 
1314  assert(NewExit->getTerminator()->getNumSuccessors() == 1 &&
1315  "Exit block should have been split to have one successor!");
1316  BasicBlock *ExitSucc = NewExit->getTerminator()->getSuccessor(0);
1317 
1318  // If the successor of the exit block had PHI nodes, add an entry for
1319  // NewExit.
1320  for (PHINode &PN : ExitSucc->phis()) {
1321  Value *V = PN.getIncomingValueForBlock(ExitBlocks[i]);
1322  ValueToValueMapTy::iterator It = VMap.find(V);
1323  if (It != VMap.end()) V = It->second;
1324  PN.addIncoming(V, NewExit);
1325  }
1326 
1327  if (LandingPadInst *LPad = NewExit->getLandingPadInst()) {
1328  PHINode *PN = PHINode::Create(LPad->getType(), 0, "",
1329  &*ExitSucc->getFirstInsertionPt());
1330 
1331  for (pred_iterator I = pred_begin(ExitSucc), E = pred_end(ExitSucc);
1332  I != E; ++I) {
1333  BasicBlock *BB = *I;
1334  LandingPadInst *LPI = BB->getLandingPadInst();
1335  LPI->replaceAllUsesWith(PN);
1336  PN->addIncoming(LPI, BB);
1337  }
1338  }
1339  }
1340 
1341  // Rewrite the code to refer to itself.
1342  for (unsigned i = 0, e = NewBlocks.size(); i != e; ++i) {
1343  for (Instruction &I : *NewBlocks[i]) {
1344  RemapInstruction(&I, VMap,
1346  if (auto *II = dyn_cast<IntrinsicInst>(&I))
1347  if (II->getIntrinsicID() == Intrinsic::assume)
1348  AC->registerAssumption(II);
1349  }
1350  }
1351 
1352  // Rewrite the original preheader to select between versions of the loop.
1353  BranchInst *OldBR = cast<BranchInst>(loopPreheader->getTerminator());
1354  assert(OldBR->isUnconditional() && OldBR->getSuccessor(0) == LoopBlocks[0] &&
1355  "Preheader splitting did not work correctly!");
1356 
1357  if (MSSAU) {
1358  // Update MemorySSA after cloning, and before splitting to unreachables,
1359  // since that invalidates the 1:1 mapping of clones in VMap.
1360  LoopBlocksRPO LBRPO(L);
1361  LBRPO.perform(LI);
1362  MSSAU->updateForClonedLoop(LBRPO, ExitBlocks, VMap);
1363  }
1364 
1365  // Emit the new branch that selects between the two versions of this loop.
1366  EmitPreheaderBranchOnCondition(LIC, Val, NewBlocks[0], LoopBlocks[0], OldBR,
1367  TI);
1368  LPM->deleteSimpleAnalysisValue(OldBR, L);
1369  if (MSSAU) {
1370  // Update MemoryPhis in Exit blocks.
1371  MSSAU->updateExitBlocksForClonedLoop(ExitBlocks, VMap, *DT);
1372  if (VerifyMemorySSA)
1373  MSSA->verifyMemorySSA();
1374  }
1375 
1376  // The OldBr was replaced by a new one and removed (but not erased) by
1377  // EmitPreheaderBranchOnCondition. It is no longer needed, so delete it.
1378  delete OldBR;
1379 
1380  LoopProcessWorklist.push_back(NewLoop);
1381  redoLoop = true;
1382 
1383  // Keep a WeakTrackingVH holding onto LIC. If the first call to
1384  // RewriteLoopBody
1385  // deletes the instruction (for example by simplifying a PHI that feeds into
1386  // the condition that we're unswitching on), we don't rewrite the second
1387  // iteration.
1388  WeakTrackingVH LICHandle(LIC);
1389 
1390  // Now we rewrite the original code to know that the condition is true and the
1391  // new code to know that the condition is false.
1392  RewriteLoopBodyWithConditionConstant(L, LIC, Val, false);
1393 
1394  // It's possible that simplifying one loop could cause the other to be
1395  // changed to another value or a constant. If its a constant, don't simplify
1396  // it.
1397  if (!LoopProcessWorklist.empty() && LoopProcessWorklist.back() == NewLoop &&
1398  LICHandle && !isa<Constant>(LICHandle))
1399  RewriteLoopBodyWithConditionConstant(NewLoop, LICHandle, Val, true);
1400 
1401  if (MSSA && VerifyMemorySSA)
1402  MSSA->verifyMemorySSA();
1403 }
1404 
1405 /// Remove all instances of I from the worklist vector specified.
1407  std::vector<Instruction*> &Worklist) {
1408 
1409  Worklist.erase(std::remove(Worklist.begin(), Worklist.end(), I),
1410  Worklist.end());
1411 }
1412 
1413 /// When we find that I really equals V, remove I from the
1414 /// program, replacing all uses with V and update the worklist.
1416  std::vector<Instruction *> &Worklist, Loop *L,
1417  LPPassManager *LPM, MemorySSAUpdater *MSSAU) {
1418  LLVM_DEBUG(dbgs() << "Replace with '" << *V << "': " << *I << "\n");
1419 
1420  // Add uses to the worklist, which may be dead now.
1421  for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i)
1422  if (Instruction *Use = dyn_cast<Instruction>(I->getOperand(i)))
1423  Worklist.push_back(Use);
1424 
1425  // Add users to the worklist which may be simplified now.
1426  for (User *U : I->users())
1427  Worklist.push_back(cast<Instruction>(U));
1428  LPM->deleteSimpleAnalysisValue(I, L);
1429  RemoveFromWorklist(I, Worklist);
1430  I->replaceAllUsesWith(V);
1431  if (!I->mayHaveSideEffects()) {
1432  if (MSSAU)
1433  MSSAU->removeMemoryAccess(I);
1434  I->eraseFromParent();
1435  }
1436  ++NumSimplify;
1437 }
1438 
1439 /// We know either that the value LIC has the value specified by Val in the
1440 /// specified loop, or we know it does NOT have that value.
1441 /// Rewrite any uses of LIC or of properties correlated to it.
1442 void LoopUnswitch::RewriteLoopBodyWithConditionConstant(Loop *L, Value *LIC,
1443  Constant *Val,
1444  bool IsEqual) {
1445  assert(!isa<Constant>(LIC) && "Why are we unswitching on a constant?");
1446 
1447  // FIXME: Support correlated properties, like:
1448  // for (...)
1449  // if (li1 < li2)
1450  // ...
1451  // if (li1 > li2)
1452  // ...
1453 
1454  // FOLD boolean conditions (X|LIC), (X&LIC). Fold conditional branches,
1455  // selects, switches.
1456  std::vector<Instruction*> Worklist;
1457  LLVMContext &Context = Val->getContext();
1458 
1459  // If we know that LIC == Val, or that LIC == NotVal, just replace uses of LIC
1460  // in the loop with the appropriate one directly.
1461  if (IsEqual || (isa<ConstantInt>(Val) &&
1462  Val->getType()->isIntegerTy(1))) {
1463  Value *Replacement;
1464  if (IsEqual)
1465  Replacement = Val;
1466  else
1467  Replacement = ConstantInt::get(Type::getInt1Ty(Val->getContext()),
1468  !cast<ConstantInt>(Val)->getZExtValue());
1469 
1470  for (User *U : LIC->users()) {
1471  Instruction *UI = dyn_cast<Instruction>(U);
1472  if (!UI || !L->contains(UI))
1473  continue;
1474  Worklist.push_back(UI);
1475  }
1476 
1477  for (Instruction *UI : Worklist)
1478  UI->replaceUsesOfWith(LIC, Replacement);
1479 
1480  SimplifyCode(Worklist, L);
1481  return;
1482  }
1483 
1484  // Otherwise, we don't know the precise value of LIC, but we do know that it
1485  // is certainly NOT "Val". As such, simplify any uses in the loop that we
1486  // can. This case occurs when we unswitch switch statements.
1487  for (User *U : LIC->users()) {
1488  Instruction *UI = dyn_cast<Instruction>(U);
1489  if (!UI || !L->contains(UI))
1490  continue;
1491 
1492  // At this point, we know LIC is definitely not Val. Try to use some simple
1493  // logic to simplify the user w.r.t. to the context.
1494  if (Value *Replacement = SimplifyInstructionWithNotEqual(UI, LIC, Val)) {
1495  if (LI->replacementPreservesLCSSAForm(UI, Replacement)) {
1496  // This in-loop instruction has been simplified w.r.t. its context,
1497  // i.e. LIC != Val, make sure we propagate its replacement value to
1498  // all its users.
1499  //
1500  // We can not yet delete UI, the LIC user, yet, because that would invalidate
1501  // the LIC->users() iterator !. However, we can make this instruction
1502  // dead by replacing all its users and push it onto the worklist so that
1503  // it can be properly deleted and its operands simplified.
1504  UI->replaceAllUsesWith(Replacement);
1505  }
1506  }
1507 
1508  // This is a LIC user, push it into the worklist so that SimplifyCode can
1509  // attempt to simplify it.
1510  Worklist.push_back(UI);
1511 
1512  // If we know that LIC is not Val, use this info to simplify code.
1513  SwitchInst *SI = dyn_cast<SwitchInst>(UI);
1514  if (!SI || !isa<ConstantInt>(Val)) continue;
1515 
1516  // NOTE: if a case value for the switch is unswitched out, we record it
1517  // after the unswitch finishes. We can not record it here as the switch
1518  // is not a direct user of the partial LIV.
1519  SwitchInst::CaseHandle DeadCase =
1520  *SI->findCaseValue(cast<ConstantInt>(Val));
1521  // Default case is live for multiple values.
1522  if (DeadCase == *SI->case_default())
1523  continue;
1524 
1525  // Found a dead case value. Don't remove PHI nodes in the
1526  // successor if they become single-entry, those PHI nodes may
1527  // be in the Users list.
1528 
1529  BasicBlock *Switch = SI->getParent();
1530  BasicBlock *SISucc = DeadCase.getCaseSuccessor();
1531  BasicBlock *Latch = L->getLoopLatch();
1532 
1533  if (!SI->findCaseDest(SISucc)) continue; // Edge is critical.
1534  // If the DeadCase successor dominates the loop latch, then the
1535  // transformation isn't safe since it will delete the sole predecessor edge
1536  // to the latch.
1537  if (Latch && DT->dominates(SISucc, Latch))
1538  continue;
1539 
1540  // FIXME: This is a hack. We need to keep the successor around
1541  // and hooked up so as to preserve the loop structure, because
1542  // trying to update it is complicated. So instead we preserve the
1543  // loop structure and put the block on a dead code path.
1544  SplitEdge(Switch, SISucc, DT, LI, MSSAU.get());
1545  // Compute the successors instead of relying on the return value
1546  // of SplitEdge, since it may have split the switch successor
1547  // after PHI nodes.
1548  BasicBlock *NewSISucc = DeadCase.getCaseSuccessor();
1549  BasicBlock *OldSISucc = *succ_begin(NewSISucc);
1550  // Create an "unreachable" destination.
1551  BasicBlock *Abort = BasicBlock::Create(Context, "us-unreachable",
1552  Switch->getParent(),
1553  OldSISucc);
1554  new UnreachableInst(Context, Abort);
1555  // Force the new case destination to branch to the "unreachable"
1556  // block while maintaining a (dead) CFG edge to the old block.
1557  NewSISucc->getTerminator()->eraseFromParent();
1558  BranchInst::Create(Abort, OldSISucc,
1559  ConstantInt::getTrue(Context), NewSISucc);
1560  // Release the PHI operands for this edge.
1561  for (PHINode &PN : NewSISucc->phis())
1562  PN.setIncomingValueForBlock(Switch, UndefValue::get(PN.getType()));
1563  // Tell the domtree about the new block. We don't fully update the
1564  // domtree here -- instead we force it to do a full recomputation
1565  // after the pass is complete -- but we do need to inform it of
1566  // new blocks.
1567  DT->addNewBlock(Abort, NewSISucc);
1568  }
1569 
1570  SimplifyCode(Worklist, L);
1571 }
1572 
1573 /// Now that we have simplified some instructions in the loop, walk over it and
1574 /// constant prop, dce, and fold control flow where possible. Note that this is
1575 /// effectively a very simple loop-structure-aware optimizer. During processing
1576 /// of this loop, L could very well be deleted, so it must not be used.
1577 ///
1578 /// FIXME: When the loop optimizer is more mature, separate this out to a new
1579 /// pass.
1580 ///
1581 void LoopUnswitch::SimplifyCode(std::vector<Instruction*> &Worklist, Loop *L) {
1582  const DataLayout &DL = L->getHeader()->getModule()->getDataLayout();
1583  while (!Worklist.empty()) {
1584  Instruction *I = Worklist.back();
1585  Worklist.pop_back();
1586 
1587  // Simple DCE.
1588  if (isInstructionTriviallyDead(I)) {
1589  LLVM_DEBUG(dbgs() << "Remove dead instruction '" << *I << "\n");
1590 
1591  // Add uses to the worklist, which may be dead now.
1592  for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i)
1593  if (Instruction *Use = dyn_cast<Instruction>(I->getOperand(i)))
1594  Worklist.push_back(Use);
1595  LPM->deleteSimpleAnalysisValue(I, L);
1596  RemoveFromWorklist(I, Worklist);
1597  if (MSSAU)
1598  MSSAU->removeMemoryAccess(I);
1599  I->eraseFromParent();
1600  ++NumSimplify;
1601  continue;
1602  }
1603 
1604  // See if instruction simplification can hack this up. This is common for
1605  // things like "select false, X, Y" after unswitching made the condition be
1606  // 'false'. TODO: update the domtree properly so we can pass it here.
1607  if (Value *V = SimplifyInstruction(I, DL))
1608  if (LI->replacementPreservesLCSSAForm(I, V)) {
1609  ReplaceUsesOfWith(I, V, Worklist, L, LPM, MSSAU.get());
1610  continue;
1611  }
1612 
1613  // Special case hacks that appear commonly in unswitched code.
1614  if (BranchInst *BI = dyn_cast<BranchInst>(I)) {
1615  if (BI->isUnconditional()) {
1616  // If BI's parent is the only pred of the successor, fold the two blocks
1617  // together.
1618  BasicBlock *Pred = BI->getParent();
1619  (void)Pred;
1620  BasicBlock *Succ = BI->getSuccessor(0);
1621  BasicBlock *SinglePred = Succ->getSinglePredecessor();
1622  if (!SinglePred) continue; // Nothing to do.
1623  assert(SinglePred == Pred && "CFG broken");
1624 
1625  // Make the LPM and Worklist updates specific to LoopUnswitch.
1626  LPM->deleteSimpleAnalysisValue(BI, L);
1627  RemoveFromWorklist(BI, Worklist);
1628  LPM->deleteSimpleAnalysisValue(Succ, L);
1629  auto SuccIt = Succ->begin();
1630  while (PHINode *PN = dyn_cast<PHINode>(SuccIt++)) {
1631  for (unsigned It = 0, E = PN->getNumOperands(); It != E; ++It)
1632  if (Instruction *Use = dyn_cast<Instruction>(PN->getOperand(It)))
1633  Worklist.push_back(Use);
1634  for (User *U : PN->users())
1635  Worklist.push_back(cast<Instruction>(U));
1636  LPM->deleteSimpleAnalysisValue(PN, L);
1637  RemoveFromWorklist(PN, Worklist);
1638  ++NumSimplify;
1639  }
1640  // Merge the block and make the remaining analyses updates.
1642  MergeBlockIntoPredecessor(Succ, &DTU, LI, MSSAU.get());
1643  ++NumSimplify;
1644  continue;
1645  }
1646 
1647  continue;
1648  }
1649  }
1650 }
1651 
1652 /// Simple simplifications we can do given the information that Cond is
1653 /// definitely not equal to Val.
1654 Value *LoopUnswitch::SimplifyInstructionWithNotEqual(Instruction *Inst,
1655  Value *Invariant,
1656  Constant *Val) {
1657  // icmp eq cond, val -> false
1658  ICmpInst *CI = dyn_cast<ICmpInst>(Inst);
1659  if (CI && CI->isEquality()) {
1660  Value *Op0 = CI->getOperand(0);
1661  Value *Op1 = CI->getOperand(1);
1662  if ((Op0 == Invariant && Op1 == Val) || (Op0 == Val && Op1 == Invariant)) {
1663  LLVMContext &Ctx = Inst->getContext();
1664  if (CI->getPredicate() == CmpInst::ICMP_EQ)
1665  return ConstantInt::getFalse(Ctx);
1666  else
1667  return ConstantInt::getTrue(Ctx);
1668  }
1669  }
1670 
1671  // FIXME: there may be other opportunities, e.g. comparison with floating
1672  // point, or Invariant - Val != 0, etc.
1673  return nullptr;
1674 }
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:49
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:111
static ConstantInt * getFalse(LLVMContext &Context)
Definition: Constants.cpp:616
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
static IntegerType * getInt1Ty(LLVMContext &C)
Definition: Type.cpp:177
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:209
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:83
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:158
OperatorChain
Operator chain lattice.
BasicBlock * getSuccessor(unsigned Idx) const
Return the specified successor. This instruction must be a terminator.
iterator end()
Definition: Function.h:687
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:448
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:743
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:144
bool isVectorTy() const
True if this is an instance of VectorType.
Definition: Type.h:230
There are only ANDs.
BasicBlock * SplitBlock(BasicBlock *Old, Instruction *SplitPt, DominatorTree *DT=nullptr, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, const Twine &BBName="")
Split the specified block at the specified instruction - everything before SplitPt stays in Old and e...
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:289
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:273
bool MergeBlockIntoPredecessor(BasicBlock *BB, DomTreeUpdater *DTU=nullptr, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, MemoryDependenceResults *MemDep=nullptr, bool PredecessorWithTwoSuccessors=false)
Attempts to merge a block into its predecessor, if possible.
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:104
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:140
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:50
Legacy analysis pass which computes MemorySSA.
Definition: MemorySSA.h:965
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:928
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:197
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:105
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:246
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:235
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:979
iterator find(const KeyT &Val)
Definition: ValueMap.h:156
static Value * FindLIVLoopCondition(Value *Cond, Loop *L, bool &Changed, OperatorChain &ParentChain, DenseMap< Value *, Value *> &Cache, MemorySSAUpdater *MSSAU)
Cond is a condition that occurs in L.
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:165
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
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:240
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:285
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:582
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.
constexpr double e
Definition: MathExtras.h:57
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:343
static UndefValue * get(Type *T)
Static factory methods - Return an &#39;undef&#39; object of the specified type.
Definition: Constants.cpp:1446
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:136
void deleteSimpleAnalysisValue(Value *V, Loop *L)
deleteSimpleAnalysisValue - Invoke deleteAnalysisValue hook for all passes that implement simple anal...
Definition: LoopPass.cpp:106
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
Definition: LoopInfo.h:115
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:1870
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
There is no operator.
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:892
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:653
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:609
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:420
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: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:106
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:375
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:509
ArrayRef< BlockT * > getBlocks() const
Get a list of the basic blocks which make up this loop.
Definition: LoopInfo.h:154
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
#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:138
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:662
block_iterator block_end() const
Definition: LoopInfo.h:160
bool isSafeToClone() const
Return true if the loop body is safe to clone in practice.
Definition: LoopInfo.cpp:471
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:74
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:475
bool replacementPreservesLCSSAForm(Instruction *From, Value *To)
Returns true if replacing From with To everywhere is guaranteed to preserve LCSSA form...
Definition: LoopInfo.h:1070
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:161
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:159
Value * SimplifyInstruction(Instruction *I, const SimplifyQuery &Q, OptimizationRemarkEmitter *ORE=nullptr)
See if we can compute a simplified version of this instruction.
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