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