LLVM  7.0.0svn
JumpThreading.cpp
Go to the documentation of this file.
1 //===- JumpThreading.cpp - Thread control through conditional blocks ------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file implements the Jump Threading pass.
11 //
12 //===----------------------------------------------------------------------===//
13 
15 #include "llvm/ADT/DenseMap.h"
16 #include "llvm/ADT/DenseSet.h"
17 #include "llvm/ADT/Optional.h"
18 #include "llvm/ADT/STLExtras.h"
19 #include "llvm/ADT/SmallPtrSet.h"
20 #include "llvm/ADT/SmallVector.h"
21 #include "llvm/ADT/Statistic.h"
25 #include "llvm/Analysis/CFG.h"
30 #include "llvm/Analysis/Loads.h"
31 #include "llvm/Analysis/LoopInfo.h"
35 #include "llvm/IR/BasicBlock.h"
36 #include "llvm/IR/CFG.h"
37 #include "llvm/IR/Constant.h"
38 #include "llvm/IR/ConstantRange.h"
39 #include "llvm/IR/Constants.h"
40 #include "llvm/IR/DataLayout.h"
41 #include "llvm/IR/Dominators.h"
42 #include "llvm/IR/Function.h"
43 #include "llvm/IR/InstrTypes.h"
44 #include "llvm/IR/Instruction.h"
45 #include "llvm/IR/Instructions.h"
46 #include "llvm/IR/IntrinsicInst.h"
47 #include "llvm/IR/Intrinsics.h"
48 #include "llvm/IR/LLVMContext.h"
49 #include "llvm/IR/MDBuilder.h"
50 #include "llvm/IR/Metadata.h"
51 #include "llvm/IR/Module.h"
52 #include "llvm/IR/PassManager.h"
53 #include "llvm/IR/PatternMatch.h"
54 #include "llvm/IR/Type.h"
55 #include "llvm/IR/Use.h"
56 #include "llvm/IR/User.h"
57 #include "llvm/IR/Value.h"
58 #include "llvm/Pass.h"
61 #include "llvm/Support/Casting.h"
63 #include "llvm/Support/Debug.h"
65 #include "llvm/Transforms/Scalar.h"
70 #include <algorithm>
71 #include <cassert>
72 #include <cstddef>
73 #include <cstdint>
74 #include <iterator>
75 #include <memory>
76 #include <utility>
77 
78 using namespace llvm;
79 using namespace jumpthreading;
80 
81 #define DEBUG_TYPE "jump-threading"
82 
83 STATISTIC(NumThreads, "Number of jumps threaded");
84 STATISTIC(NumFolds, "Number of terminators folded");
85 STATISTIC(NumDupes, "Number of branch blocks duplicated to eliminate phi");
86 
87 static cl::opt<unsigned>
88 BBDuplicateThreshold("jump-threading-threshold",
89  cl::desc("Max block size to duplicate for jump threading"),
90  cl::init(6), cl::Hidden);
91 
92 static cl::opt<unsigned>
94  "jump-threading-implication-search-threshold",
95  cl::desc("The number of predecessors to search for a stronger "
96  "condition to use to thread over a weaker condition"),
97  cl::init(3), cl::Hidden);
98 
100  "print-lvi-after-jump-threading",
101  cl::desc("Print the LazyValueInfo cache after JumpThreading"), cl::init(false),
102  cl::Hidden);
103 
104 namespace {
105 
106  /// This pass performs 'jump threading', which looks at blocks that have
107  /// multiple predecessors and multiple successors. If one or more of the
108  /// predecessors of the block can be proven to always jump to one of the
109  /// successors, we forward the edge from the predecessor to the successor by
110  /// duplicating the contents of this block.
111  ///
112  /// An example of when this can occur is code like this:
113  ///
114  /// if () { ...
115  /// X = 4;
116  /// }
117  /// if (X < 3) {
118  ///
119  /// In this case, the unconditional branch at the end of the first if can be
120  /// revectored to the false side of the second if.
121  class JumpThreading : public FunctionPass {
122  JumpThreadingPass Impl;
123 
124  public:
125  static char ID; // Pass identification
126 
127  JumpThreading(int T = -1) : FunctionPass(ID), Impl(T) {
129  }
130 
131  bool runOnFunction(Function &F) override;
132 
133  void getAnalysisUsage(AnalysisUsage &AU) const override {
141  }
142 
143  void releaseMemory() override { Impl.releaseMemory(); }
144  };
145 
146 } // end anonymous namespace
147 
148 char JumpThreading::ID = 0;
149 
150 INITIALIZE_PASS_BEGIN(JumpThreading, "jump-threading",
151  "Jump Threading", false, false)
156 INITIALIZE_PASS_END(JumpThreading, "jump-threading",
157  "Jump Threading", false, false)
158 
159 // Public interface to the Jump Threading pass
161  return new JumpThreading(Threshold);
162 }
163 
165  BBDupThreshold = (T == -1) ? BBDuplicateThreshold : unsigned(T);
166 }
167 
168 // Update branch probability information according to conditional
169 // branch probability. This is usually made possible for cloned branches
170 // in inline instances by the context specific profile in the caller.
171 // For instance,
172 //
173 // [Block PredBB]
174 // [Branch PredBr]
175 // if (t) {
176 // Block A;
177 // } else {
178 // Block B;
179 // }
180 //
181 // [Block BB]
182 // cond = PN([true, %A], [..., %B]); // PHI node
183 // [Branch CondBr]
184 // if (cond) {
185 // ... // P(cond == true) = 1%
186 // }
187 //
188 // Here we know that when block A is taken, cond must be true, which means
189 // P(cond == true | A) = 1
190 //
191 // Given that P(cond == true) = P(cond == true | A) * P(A) +
192 // P(cond == true | B) * P(B)
193 // we get:
194 // P(cond == true ) = P(A) + P(cond == true | B) * P(B)
195 //
196 // which gives us:
197 // P(A) is less than P(cond == true), i.e.
198 // P(t == true) <= P(cond == true)
199 //
200 // In other words, if we know P(cond == true) is unlikely, we know
201 // that P(t == true) is also unlikely.
202 //
204  BranchInst *CondBr = dyn_cast<BranchInst>(BB->getTerminator());
205  if (!CondBr)
206  return;
207 
209  uint64_t TrueWeight, FalseWeight;
210  if (!CondBr->extractProfMetadata(TrueWeight, FalseWeight))
211  return;
212 
213  // Returns the outgoing edge of the dominating predecessor block
214  // that leads to the PhiNode's incoming block:
215  auto GetPredOutEdge =
216  [](BasicBlock *IncomingBB,
217  BasicBlock *PhiBB) -> std::pair<BasicBlock *, BasicBlock *> {
218  auto *PredBB = IncomingBB;
219  auto *SuccBB = PhiBB;
220  while (true) {
221  BranchInst *PredBr = dyn_cast<BranchInst>(PredBB->getTerminator());
222  if (PredBr && PredBr->isConditional())
223  return {PredBB, SuccBB};
224  auto *SinglePredBB = PredBB->getSinglePredecessor();
225  if (!SinglePredBB)
226  return {nullptr, nullptr};
227  SuccBB = PredBB;
228  PredBB = SinglePredBB;
229  }
230  };
231 
232  for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
233  Value *PhiOpnd = PN->getIncomingValue(i);
234  ConstantInt *CI = dyn_cast<ConstantInt>(PhiOpnd);
235 
236  if (!CI || !CI->getType()->isIntegerTy(1))
237  continue;
238 
240  TrueWeight, TrueWeight + FalseWeight)
242  FalseWeight, TrueWeight + FalseWeight));
243 
244  auto PredOutEdge = GetPredOutEdge(PN->getIncomingBlock(i), BB);
245  if (!PredOutEdge.first)
246  return;
247 
248  BasicBlock *PredBB = PredOutEdge.first;
249  BranchInst *PredBr = cast<BranchInst>(PredBB->getTerminator());
250 
251  uint64_t PredTrueWeight, PredFalseWeight;
252  // FIXME: We currently only set the profile data when it is missing.
253  // With PGO, this can be used to refine even existing profile data with
254  // context information. This needs to be done after more performance
255  // testing.
256  if (PredBr->extractProfMetadata(PredTrueWeight, PredFalseWeight))
257  continue;
258 
259  // We can not infer anything useful when BP >= 50%, because BP is the
260  // upper bound probability value.
261  if (BP >= BranchProbability(50, 100))
262  continue;
263 
264  SmallVector<uint32_t, 2> Weights;
265  if (PredBr->getSuccessor(0) == PredOutEdge.second) {
266  Weights.push_back(BP.getNumerator());
267  Weights.push_back(BP.getCompl().getNumerator());
268  } else {
269  Weights.push_back(BP.getCompl().getNumerator());
270  Weights.push_back(BP.getNumerator());
271  }
273  MDBuilder(PredBr->getParent()->getContext())
274  .createBranchWeights(Weights));
275  }
276 }
277 
278 /// runOnFunction - Toplevel algorithm.
280  if (skipFunction(F))
281  return false;
282  auto TLI = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
283  // Get DT analysis before LVI. When LVI is initialized it conditionally adds
284  // DT if it's available.
285  auto DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
286  auto LVI = &getAnalysis<LazyValueInfoWrapperPass>().getLVI();
287  auto AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
288  DeferredDominance DDT(*DT);
289  std::unique_ptr<BlockFrequencyInfo> BFI;
290  std::unique_ptr<BranchProbabilityInfo> BPI;
291  bool HasProfileData = F.hasProfileData();
292  if (HasProfileData) {
293  LoopInfo LI{DominatorTree(F)};
294  BPI.reset(new BranchProbabilityInfo(F, LI, TLI));
295  BFI.reset(new BlockFrequencyInfo(F, *BPI, LI));
296  }
297 
298  bool Changed = Impl.runImpl(F, TLI, LVI, AA, &DDT, HasProfileData,
299  std::move(BFI), std::move(BPI));
301  dbgs() << "LVI for function '" << F.getName() << "':\n";
302  LVI->printLVI(F, *DT, dbgs());
303  }
304  return Changed;
305 }
306 
309  auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);
310  // Get DT analysis before LVI. When LVI is initialized it conditionally adds
311  // DT if it's available.
312  auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
313  auto &LVI = AM.getResult<LazyValueAnalysis>(F);
314  auto &AA = AM.getResult<AAManager>(F);
315  DeferredDominance DDT(DT);
316 
317  std::unique_ptr<BlockFrequencyInfo> BFI;
318  std::unique_ptr<BranchProbabilityInfo> BPI;
319  if (F.hasProfileData()) {
320  LoopInfo LI{DominatorTree(F)};
321  BPI.reset(new BranchProbabilityInfo(F, LI, &TLI));
322  BFI.reset(new BlockFrequencyInfo(F, *BPI, LI));
323  }
324 
325  bool Changed = runImpl(F, &TLI, &LVI, &AA, &DDT, HasProfileData,
326  std::move(BFI), std::move(BPI));
327 
328  if (!Changed)
329  return PreservedAnalyses::all();
331  PA.preserve<GlobalsAA>();
334  return PA;
335 }
336 
338  LazyValueInfo *LVI_, AliasAnalysis *AA_,
339  DeferredDominance *DDT_, bool HasProfileData_,
340  std::unique_ptr<BlockFrequencyInfo> BFI_,
341  std::unique_ptr<BranchProbabilityInfo> BPI_) {
342  LLVM_DEBUG(dbgs() << "Jump threading on function '" << F.getName() << "'\n");
343  TLI = TLI_;
344  LVI = LVI_;
345  AA = AA_;
346  DDT = DDT_;
347  BFI.reset();
348  BPI.reset();
349  // When profile data is available, we need to update edge weights after
350  // successful jump threading, which requires both BPI and BFI being available.
351  HasProfileData = HasProfileData_;
352  auto *GuardDecl = F.getParent()->getFunction(
353  Intrinsic::getName(Intrinsic::experimental_guard));
354  HasGuards = GuardDecl && !GuardDecl->use_empty();
355  if (HasProfileData) {
356  BPI = std::move(BPI_);
357  BFI = std::move(BFI_);
358  }
359 
360  // JumpThreading must not processes blocks unreachable from entry. It's a
361  // waste of compute time and can potentially lead to hangs.
362  SmallPtrSet<BasicBlock *, 16> Unreachable;
363  DominatorTree &DT = DDT->flush();
364  for (auto &BB : F)
365  if (!DT.isReachableFromEntry(&BB))
366  Unreachable.insert(&BB);
367 
368  FindLoopHeaders(F);
369 
370  bool EverChanged = false;
371  bool Changed;
372  do {
373  Changed = false;
374  for (auto &BB : F) {
375  if (Unreachable.count(&BB))
376  continue;
377  while (ProcessBlock(&BB)) // Thread all of the branches we can over BB.
378  Changed = true;
379  // Stop processing BB if it's the entry or is now deleted. The following
380  // routines attempt to eliminate BB and locating a suitable replacement
381  // for the entry is non-trivial.
382  if (&BB == &F.getEntryBlock() || DDT->pendingDeletedBB(&BB))
383  continue;
384 
385  if (pred_empty(&BB)) {
386  // When ProcessBlock makes BB unreachable it doesn't bother to fix up
387  // the instructions in it. We must remove BB to prevent invalid IR.
388  LLVM_DEBUG(dbgs() << " JT: Deleting dead block '" << BB.getName()
389  << "' with terminator: " << *BB.getTerminator()
390  << '\n');
391  LoopHeaders.erase(&BB);
392  LVI->eraseBlock(&BB);
393  DeleteDeadBlock(&BB, DDT);
394  Changed = true;
395  continue;
396  }
397 
398  // ProcessBlock doesn't thread BBs with unconditional TIs. However, if BB
399  // is "almost empty", we attempt to merge BB with its sole successor.
400  auto *BI = dyn_cast<BranchInst>(BB.getTerminator());
401  if (BI && BI->isUnconditional() &&
402  // The terminator must be the only non-phi instruction in BB.
403  BB.getFirstNonPHIOrDbg()->isTerminator() &&
404  // Don't alter Loop headers and latches to ensure another pass can
405  // detect and transform nested loops later.
406  !LoopHeaders.count(&BB) && !LoopHeaders.count(BI->getSuccessor(0)) &&
408  // BB is valid for cleanup here because we passed in DDT. F remains
409  // BB's parent until a DDT->flush() event.
410  LVI->eraseBlock(&BB);
411  Changed = true;
412  }
413  }
414  EverChanged |= Changed;
415  } while (Changed);
416 
417  LoopHeaders.clear();
418  DDT->flush();
419  LVI->enableDT();
420  return EverChanged;
421 }
422 
423 // Replace uses of Cond with ToVal when safe to do so. If all uses are
424 // replaced, we can remove Cond. We cannot blindly replace all uses of Cond
425 // because we may incorrectly replace uses when guards/assumes are uses of
426 // of `Cond` and we used the guards/assume to reason about the `Cond` value
427 // at the end of block. RAUW unconditionally replaces all uses
428 // including the guards/assumes themselves and the uses before the
429 // guard/assume.
430 static void ReplaceFoldableUses(Instruction *Cond, Value *ToVal) {
431  assert(Cond->getType() == ToVal->getType());
432  auto *BB = Cond->getParent();
433  // We can unconditionally replace all uses in non-local blocks (i.e. uses
434  // strictly dominated by BB), since LVI information is true from the
435  // terminator of BB.
436  replaceNonLocalUsesWith(Cond, ToVal);
437  for (Instruction &I : reverse(*BB)) {
438  // Reached the Cond whose uses we are trying to replace, so there are no
439  // more uses.
440  if (&I == Cond)
441  break;
442  // We only replace uses in instructions that are guaranteed to reach the end
443  // of BB, where we know Cond is ToVal.
445  break;
446  I.replaceUsesOfWith(Cond, ToVal);
447  }
448  if (Cond->use_empty() && !Cond->mayHaveSideEffects())
449  Cond->eraseFromParent();
450 }
451 
452 /// Return the cost of duplicating a piece of this block from first non-phi
453 /// and before StopAt instruction to thread across it. Stop scanning the block
454 /// when exceeding the threshold. If duplication is impossible, returns ~0U.
456  Instruction *StopAt,
457  unsigned Threshold) {
458  assert(StopAt->getParent() == BB && "Not an instruction from proper BB?");
459  /// Ignore PHI nodes, these will be flattened when duplication happens.
461 
462  // FIXME: THREADING will delete values that are just used to compute the
463  // branch, so they shouldn't count against the duplication cost.
464 
465  unsigned Bonus = 0;
466  if (BB->getTerminator() == StopAt) {
467  // Threading through a switch statement is particularly profitable. If this
468  // block ends in a switch, decrease its cost to make it more likely to
469  // happen.
470  if (isa<SwitchInst>(StopAt))
471  Bonus = 6;
472 
473  // The same holds for indirect branches, but slightly more so.
474  if (isa<IndirectBrInst>(StopAt))
475  Bonus = 8;
476  }
477 
478  // Bump the threshold up so the early exit from the loop doesn't skip the
479  // terminator-based Size adjustment at the end.
480  Threshold += Bonus;
481 
482  // Sum up the cost of each instruction until we get to the terminator. Don't
483  // include the terminator because the copy won't include it.
484  unsigned Size = 0;
485  for (; &*I != StopAt; ++I) {
486 
487  // Stop scanning the block if we've reached the threshold.
488  if (Size > Threshold)
489  return Size;
490 
491  // Debugger intrinsics don't incur code size.
492  if (isa<DbgInfoIntrinsic>(I)) continue;
493 
494  // If this is a pointer->pointer bitcast, it is free.
495  if (isa<BitCastInst>(I) && I->getType()->isPointerTy())
496  continue;
497 
498  // Bail out if this instruction gives back a token type, it is not possible
499  // to duplicate it if it is used outside this BB.
500  if (I->getType()->isTokenTy() && I->isUsedOutsideOfBlock(BB))
501  return ~0U;
502 
503  // All other instructions count for at least one unit.
504  ++Size;
505 
506  // Calls are more expensive. If they are non-intrinsic calls, we model them
507  // as having cost of 4. If they are a non-vector intrinsic, we model them
508  // as having cost of 2 total, and if they are a vector intrinsic, we model
509  // them as having cost 1.
510  if (const CallInst *CI = dyn_cast<CallInst>(I)) {
511  if (CI->cannotDuplicate() || CI->isConvergent())
512  // Blocks with NoDuplicate are modelled as having infinite cost, so they
513  // are never duplicated.
514  return ~0U;
515  else if (!isa<IntrinsicInst>(CI))
516  Size += 3;
517  else if (!CI->getType()->isVectorTy())
518  Size += 1;
519  }
520  }
521 
522  return Size > Bonus ? Size - Bonus : 0;
523 }
524 
525 /// FindLoopHeaders - We do not want jump threading to turn proper loop
526 /// structures into irreducible loops. Doing this breaks up the loop nesting
527 /// hierarchy and pessimizes later transformations. To prevent this from
528 /// happening, we first have to find the loop headers. Here we approximate this
529 /// by finding targets of backedges in the CFG.
530 ///
531 /// Note that there definitely are cases when we want to allow threading of
532 /// edges across a loop header. For example, threading a jump from outside the
533 /// loop (the preheader) to an exit block of the loop is definitely profitable.
534 /// It is also almost always profitable to thread backedges from within the loop
535 /// to exit blocks, and is often profitable to thread backedges to other blocks
536 /// within the loop (forming a nested loop). This simple analysis is not rich
537 /// enough to track all of these properties and keep it up-to-date as the CFG
538 /// mutates, so we don't allow any of these transformations.
541  FindFunctionBackedges(F, Edges);
542 
543  for (const auto &Edge : Edges)
544  LoopHeaders.insert(Edge.second);
545 }
546 
547 /// getKnownConstant - Helper method to determine if we can thread over a
548 /// terminator with the given value as its condition, and if so what value to
549 /// use for that. What kind of value this is depends on whether we want an
550 /// integer or a block address, but an undef is always accepted.
551 /// Returns null if Val is null or not an appropriate constant.
553  if (!Val)
554  return nullptr;
555 
556  // Undef is "known" enough.
557  if (UndefValue *U = dyn_cast<UndefValue>(Val))
558  return U;
559 
560  if (Preference == WantBlockAddress)
561  return dyn_cast<BlockAddress>(Val->stripPointerCasts());
562 
563  return dyn_cast<ConstantInt>(Val);
564 }
565 
566 /// ComputeValueKnownInPredecessors - Given a basic block BB and a value V, see
567 /// if we can infer that the value is a known ConstantInt/BlockAddress or undef
568 /// in any of our predecessors. If so, return the known list of value and pred
569 /// BB in the result vector.
570 ///
571 /// This returns true if there were any known values.
573  Value *V, BasicBlock *BB, PredValueInfo &Result,
575  // This method walks up use-def chains recursively. Because of this, we could
576  // get into an infinite loop going around loops in the use-def chain. To
577  // prevent this, keep track of what (value, block) pairs we've already visited
578  // and terminate the search if we loop back to them
579  if (!RecursionSet.insert(std::make_pair(V, BB)).second)
580  return false;
581 
582  // An RAII help to remove this pair from the recursion set once the recursion
583  // stack pops back out again.
584  RecursionSetRemover remover(RecursionSet, std::make_pair(V, BB));
585 
586  // If V is a constant, then it is known in all predecessors.
587  if (Constant *KC = getKnownConstant(V, Preference)) {
588  for (BasicBlock *Pred : predecessors(BB))
589  Result.push_back(std::make_pair(KC, Pred));
590 
591  return !Result.empty();
592  }
593 
594  // If V is a non-instruction value, or an instruction in a different block,
595  // then it can't be derived from a PHI.
597  if (!I || I->getParent() != BB) {
598 
599  // Okay, if this is a live-in value, see if it has a known value at the end
600  // of any of our predecessors.
601  //
602  // FIXME: This should be an edge property, not a block end property.
603  /// TODO: Per PR2563, we could infer value range information about a
604  /// predecessor based on its terminator.
605  //
606  // FIXME: change this to use the more-rich 'getPredicateOnEdge' method if
607  // "I" is a non-local compare-with-a-constant instruction. This would be
608  // able to handle value inequalities better, for example if the compare is
609  // "X < 4" and "X < 3" is known true but "X < 4" itself is not available.
610  // Perhaps getConstantOnEdge should be smart enough to do this?
611 
612  if (DDT->pending())
613  LVI->disableDT();
614  else
615  LVI->enableDT();
616  for (BasicBlock *P : predecessors(BB)) {
617  // If the value is known by LazyValueInfo to be a constant in a
618  // predecessor, use that information to try to thread this block.
619  Constant *PredCst = LVI->getConstantOnEdge(V, P, BB, CxtI);
620  if (Constant *KC = getKnownConstant(PredCst, Preference))
621  Result.push_back(std::make_pair(KC, P));
622  }
623 
624  return !Result.empty();
625  }
626 
627  /// If I is a PHI node, then we know the incoming values for any constants.
628  if (PHINode *PN = dyn_cast<PHINode>(I)) {
629  if (DDT->pending())
630  LVI->disableDT();
631  else
632  LVI->enableDT();
633  for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
634  Value *InVal = PN->getIncomingValue(i);
635  if (Constant *KC = getKnownConstant(InVal, Preference)) {
636  Result.push_back(std::make_pair(KC, PN->getIncomingBlock(i)));
637  } else {
638  Constant *CI = LVI->getConstantOnEdge(InVal,
639  PN->getIncomingBlock(i),
640  BB, CxtI);
641  if (Constant *KC = getKnownConstant(CI, Preference))
642  Result.push_back(std::make_pair(KC, PN->getIncomingBlock(i)));
643  }
644  }
645 
646  return !Result.empty();
647  }
648 
649  // Handle Cast instructions. Only see through Cast when the source operand is
650  // PHI or Cmp to save the compilation time.
651  if (CastInst *CI = dyn_cast<CastInst>(I)) {
652  Value *Source = CI->getOperand(0);
653  if (!isa<PHINode>(Source) && !isa<CmpInst>(Source))
654  return false;
655  ComputeValueKnownInPredecessors(Source, BB, Result, Preference, CxtI);
656  if (Result.empty())
657  return false;
658 
659  // Convert the known values.
660  for (auto &R : Result)
661  R.first = ConstantExpr::getCast(CI->getOpcode(), R.first, CI->getType());
662 
663  return true;
664  }
665 
666  // Handle some boolean conditions.
667  if (I->getType()->getPrimitiveSizeInBits() == 1) {
668  assert(Preference == WantInteger && "One-bit non-integer type?");
669  // X | true -> true
670  // X & false -> false
671  if (I->getOpcode() == Instruction::Or ||
672  I->getOpcode() == Instruction::And) {
673  PredValueInfoTy LHSVals, RHSVals;
674 
675  ComputeValueKnownInPredecessors(I->getOperand(0), BB, LHSVals,
676  WantInteger, CxtI);
677  ComputeValueKnownInPredecessors(I->getOperand(1), BB, RHSVals,
678  WantInteger, CxtI);
679 
680  if (LHSVals.empty() && RHSVals.empty())
681  return false;
682 
683  ConstantInt *InterestingVal;
684  if (I->getOpcode() == Instruction::Or)
685  InterestingVal = ConstantInt::getTrue(I->getContext());
686  else
687  InterestingVal = ConstantInt::getFalse(I->getContext());
688 
689  SmallPtrSet<BasicBlock*, 4> LHSKnownBBs;
690 
691  // Scan for the sentinel. If we find an undef, force it to the
692  // interesting value: x|undef -> true and x&undef -> false.
693  for (const auto &LHSVal : LHSVals)
694  if (LHSVal.first == InterestingVal || isa<UndefValue>(LHSVal.first)) {
695  Result.emplace_back(InterestingVal, LHSVal.second);
696  LHSKnownBBs.insert(LHSVal.second);
697  }
698  for (const auto &RHSVal : RHSVals)
699  if (RHSVal.first == InterestingVal || isa<UndefValue>(RHSVal.first)) {
700  // If we already inferred a value for this block on the LHS, don't
701  // re-add it.
702  if (!LHSKnownBBs.count(RHSVal.second))
703  Result.emplace_back(InterestingVal, RHSVal.second);
704  }
705 
706  return !Result.empty();
707  }
708 
709  // Handle the NOT form of XOR.
710  if (I->getOpcode() == Instruction::Xor &&
711  isa<ConstantInt>(I->getOperand(1)) &&
712  cast<ConstantInt>(I->getOperand(1))->isOne()) {
713  ComputeValueKnownInPredecessors(I->getOperand(0), BB, Result,
714  WantInteger, CxtI);
715  if (Result.empty())
716  return false;
717 
718  // Invert the known values.
719  for (auto &R : Result)
720  R.first = ConstantExpr::getNot(R.first);
721 
722  return true;
723  }
724 
725  // Try to simplify some other binary operator values.
726  } else if (BinaryOperator *BO = dyn_cast<BinaryOperator>(I)) {
727  assert(Preference != WantBlockAddress
728  && "A binary operator creating a block address?");
729  if (ConstantInt *CI = dyn_cast<ConstantInt>(BO->getOperand(1))) {
730  PredValueInfoTy LHSVals;
731  ComputeValueKnownInPredecessors(BO->getOperand(0), BB, LHSVals,
732  WantInteger, CxtI);
733 
734  // Try to use constant folding to simplify the binary operator.
735  for (const auto &LHSVal : LHSVals) {
736  Constant *V = LHSVal.first;
737  Constant *Folded = ConstantExpr::get(BO->getOpcode(), V, CI);
738 
739  if (Constant *KC = getKnownConstant(Folded, WantInteger))
740  Result.push_back(std::make_pair(KC, LHSVal.second));
741  }
742  }
743 
744  return !Result.empty();
745  }
746 
747  // Handle compare with phi operand, where the PHI is defined in this block.
748  if (CmpInst *Cmp = dyn_cast<CmpInst>(I)) {
749  assert(Preference == WantInteger && "Compares only produce integers");
750  Type *CmpType = Cmp->getType();
751  Value *CmpLHS = Cmp->getOperand(0);
752  Value *CmpRHS = Cmp->getOperand(1);
753  CmpInst::Predicate Pred = Cmp->getPredicate();
754 
755  PHINode *PN = dyn_cast<PHINode>(CmpLHS);
756  if (!PN)
757  PN = dyn_cast<PHINode>(CmpRHS);
758  if (PN && PN->getParent() == BB) {
759  const DataLayout &DL = PN->getModule()->getDataLayout();
760  // We can do this simplification if any comparisons fold to true or false.
761  // See if any do.
762  if (DDT->pending())
763  LVI->disableDT();
764  else
765  LVI->enableDT();
766  for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
767  BasicBlock *PredBB = PN->getIncomingBlock(i);
768  Value *LHS, *RHS;
769  if (PN == CmpLHS) {
770  LHS = PN->getIncomingValue(i);
771  RHS = CmpRHS->DoPHITranslation(BB, PredBB);
772  } else {
773  LHS = CmpLHS->DoPHITranslation(BB, PredBB);
774  RHS = PN->getIncomingValue(i);
775  }
776  Value *Res = SimplifyCmpInst(Pred, LHS, RHS, {DL});
777  if (!Res) {
778  if (!isa<Constant>(RHS))
779  continue;
780 
781  // getPredicateOnEdge call will make no sense if LHS is defined in BB.
782  auto LHSInst = dyn_cast<Instruction>(LHS);
783  if (LHSInst && LHSInst->getParent() == BB)
784  continue;
785 
787  ResT = LVI->getPredicateOnEdge(Pred, LHS,
788  cast<Constant>(RHS), PredBB, BB,
789  CxtI ? CxtI : Cmp);
790  if (ResT == LazyValueInfo::Unknown)
791  continue;
792  Res = ConstantInt::get(Type::getInt1Ty(LHS->getContext()), ResT);
793  }
794 
795  if (Constant *KC = getKnownConstant(Res, WantInteger))
796  Result.push_back(std::make_pair(KC, PredBB));
797  }
798 
799  return !Result.empty();
800  }
801 
802  // If comparing a live-in value against a constant, see if we know the
803  // live-in value on any predecessors.
804  if (isa<Constant>(CmpRHS) && !CmpType->isVectorTy()) {
805  Constant *CmpConst = cast<Constant>(CmpRHS);
806 
807  if (!isa<Instruction>(CmpLHS) ||
808  cast<Instruction>(CmpLHS)->getParent() != BB) {
809  if (DDT->pending())
810  LVI->disableDT();
811  else
812  LVI->enableDT();
813  for (BasicBlock *P : predecessors(BB)) {
814  // If the value is known by LazyValueInfo to be a constant in a
815  // predecessor, use that information to try to thread this block.
817  LVI->getPredicateOnEdge(Pred, CmpLHS,
818  CmpConst, P, BB, CxtI ? CxtI : Cmp);
819  if (Res == LazyValueInfo::Unknown)
820  continue;
821 
822  Constant *ResC = ConstantInt::get(CmpType, Res);
823  Result.push_back(std::make_pair(ResC, P));
824  }
825 
826  return !Result.empty();
827  }
828 
829  // InstCombine can fold some forms of constant range checks into
830  // (icmp (add (x, C1)), C2). See if we have we have such a thing with
831  // x as a live-in.
832  {
833  using namespace PatternMatch;
834 
835  Value *AddLHS;
836  ConstantInt *AddConst;
837  if (isa<ConstantInt>(CmpConst) &&
838  match(CmpLHS, m_Add(m_Value(AddLHS), m_ConstantInt(AddConst)))) {
839  if (!isa<Instruction>(AddLHS) ||
840  cast<Instruction>(AddLHS)->getParent() != BB) {
841  if (DDT->pending())
842  LVI->disableDT();
843  else
844  LVI->enableDT();
845  for (BasicBlock *P : predecessors(BB)) {
846  // If the value is known by LazyValueInfo to be a ConstantRange in
847  // a predecessor, use that information to try to thread this
848  // block.
849  ConstantRange CR = LVI->getConstantRangeOnEdge(
850  AddLHS, P, BB, CxtI ? CxtI : cast<Instruction>(CmpLHS));
851  // Propagate the range through the addition.
852  CR = CR.add(AddConst->getValue());
853 
854  // Get the range where the compare returns true.
856  Pred, cast<ConstantInt>(CmpConst)->getValue());
857 
858  Constant *ResC;
859  if (CmpRange.contains(CR))
860  ResC = ConstantInt::getTrue(CmpType);
861  else if (CmpRange.inverse().contains(CR))
862  ResC = ConstantInt::getFalse(CmpType);
863  else
864  continue;
865 
866  Result.push_back(std::make_pair(ResC, P));
867  }
868 
869  return !Result.empty();
870  }
871  }
872  }
873 
874  // Try to find a constant value for the LHS of a comparison,
875  // and evaluate it statically if we can.
876  PredValueInfoTy LHSVals;
877  ComputeValueKnownInPredecessors(I->getOperand(0), BB, LHSVals,
878  WantInteger, CxtI);
879 
880  for (const auto &LHSVal : LHSVals) {
881  Constant *V = LHSVal.first;
882  Constant *Folded = ConstantExpr::getCompare(Pred, V, CmpConst);
883  if (Constant *KC = getKnownConstant(Folded, WantInteger))
884  Result.push_back(std::make_pair(KC, LHSVal.second));
885  }
886 
887  return !Result.empty();
888  }
889  }
890 
891  if (SelectInst *SI = dyn_cast<SelectInst>(I)) {
892  // Handle select instructions where at least one operand is a known constant
893  // and we can figure out the condition value for any predecessor block.
894  Constant *TrueVal = getKnownConstant(SI->getTrueValue(), Preference);
895  Constant *FalseVal = getKnownConstant(SI->getFalseValue(), Preference);
896  PredValueInfoTy Conds;
897  if ((TrueVal || FalseVal) &&
898  ComputeValueKnownInPredecessors(SI->getCondition(), BB, Conds,
899  WantInteger, CxtI)) {
900  for (auto &C : Conds) {
901  Constant *Cond = C.first;
902 
903  // Figure out what value to use for the condition.
904  bool KnownCond;
905  if (ConstantInt *CI = dyn_cast<ConstantInt>(Cond)) {
906  // A known boolean.
907  KnownCond = CI->isOne();
908  } else {
909  assert(isa<UndefValue>(Cond) && "Unexpected condition value");
910  // Either operand will do, so be sure to pick the one that's a known
911  // constant.
912  // FIXME: Do this more cleverly if both values are known constants?
913  KnownCond = (TrueVal != nullptr);
914  }
915 
916  // See if the select has a known constant value for this predecessor.
917  if (Constant *Val = KnownCond ? TrueVal : FalseVal)
918  Result.push_back(std::make_pair(Val, C.second));
919  }
920 
921  return !Result.empty();
922  }
923  }
924 
925  // If all else fails, see if LVI can figure out a constant value for us.
926  if (DDT->pending())
927  LVI->disableDT();
928  else
929  LVI->enableDT();
930  Constant *CI = LVI->getConstant(V, BB, CxtI);
931  if (Constant *KC = getKnownConstant(CI, Preference)) {
932  for (BasicBlock *Pred : predecessors(BB))
933  Result.push_back(std::make_pair(KC, Pred));
934  }
935 
936  return !Result.empty();
937 }
938 
939 /// GetBestDestForBranchOnUndef - If we determine that the specified block ends
940 /// in an undefined jump, decide which block is best to revector to.
941 ///
942 /// Since we can pick an arbitrary destination, we pick the successor with the
943 /// fewest predecessors. This should reduce the in-degree of the others.
944 static unsigned GetBestDestForJumpOnUndef(BasicBlock *BB) {
945  TerminatorInst *BBTerm = BB->getTerminator();
946  unsigned MinSucc = 0;
947  BasicBlock *TestBB = BBTerm->getSuccessor(MinSucc);
948  // Compute the successor with the minimum number of predecessors.
949  unsigned MinNumPreds = pred_size(TestBB);
950  for (unsigned i = 1, e = BBTerm->getNumSuccessors(); i != e; ++i) {
951  TestBB = BBTerm->getSuccessor(i);
952  unsigned NumPreds = pred_size(TestBB);
953  if (NumPreds < MinNumPreds) {
954  MinSucc = i;
955  MinNumPreds = NumPreds;
956  }
957  }
958 
959  return MinSucc;
960 }
961 
963  if (!BB->hasAddressTaken()) return false;
964 
965  // If the block has its address taken, it may be a tree of dead constants
966  // hanging off of it. These shouldn't keep the block alive.
969  return !BA->use_empty();
970 }
971 
972 /// ProcessBlock - If there are any predecessors whose control can be threaded
973 /// through to a successor, transform them now.
975  // If the block is trivially dead, just return and let the caller nuke it.
976  // This simplifies other transformations.
977  if (DDT->pendingDeletedBB(BB) ||
978  (pred_empty(BB) && BB != &BB->getParent()->getEntryBlock()))
979  return false;
980 
981  // If this block has a single predecessor, and if that pred has a single
982  // successor, merge the blocks. This encourages recursive jump threading
983  // because now the condition in this block can be threaded through
984  // predecessors of our predecessor block.
985  if (BasicBlock *SinglePred = BB->getSinglePredecessor()) {
986  const TerminatorInst *TI = SinglePred->getTerminator();
987  if (!TI->isExceptional() && TI->getNumSuccessors() == 1 &&
988  SinglePred != BB && !hasAddressTakenAndUsed(BB)) {
989  // If SinglePred was a loop header, BB becomes one.
990  if (LoopHeaders.erase(SinglePred))
991  LoopHeaders.insert(BB);
992 
993  LVI->eraseBlock(SinglePred);
994  MergeBasicBlockIntoOnlyPred(BB, nullptr, DDT);
995 
996  // Now that BB is merged into SinglePred (i.e. SinglePred Code followed by
997  // BB code within one basic block `BB`), we need to invalidate the LVI
998  // information associated with BB, because the LVI information need not be
999  // true for all of BB after the merge. For example,
1000  // Before the merge, LVI info and code is as follows:
1001  // SinglePred: <LVI info1 for %p val>
1002  // %y = use of %p
1003  // call @exit() // need not transfer execution to successor.
1004  // assume(%p) // from this point on %p is true
1005  // br label %BB
1006  // BB: <LVI info2 for %p val, i.e. %p is true>
1007  // %x = use of %p
1008  // br label exit
1009  //
1010  // Note that this LVI info for blocks BB and SinglPred is correct for %p
1011  // (info2 and info1 respectively). After the merge and the deletion of the
1012  // LVI info1 for SinglePred. We have the following code:
1013  // BB: <LVI info2 for %p val>
1014  // %y = use of %p
1015  // call @exit()
1016  // assume(%p)
1017  // %x = use of %p <-- LVI info2 is correct from here onwards.
1018  // br label exit
1019  // LVI info2 for BB is incorrect at the beginning of BB.
1020 
1021  // Invalidate LVI information for BB if the LVI is not provably true for
1022  // all of BB.
1024  LVI->eraseBlock(BB);
1025  return true;
1026  }
1027  }
1028 
1029  if (TryToUnfoldSelectInCurrBB(BB))
1030  return true;
1031 
1032  // Look if we can propagate guards to predecessors.
1033  if (HasGuards && ProcessGuards(BB))
1034  return true;
1035 
1036  // What kind of constant we're looking for.
1038 
1039  // Look to see if the terminator is a conditional branch, switch or indirect
1040  // branch, if not we can't thread it.
1041  Value *Condition;
1043  if (BranchInst *BI = dyn_cast<BranchInst>(Terminator)) {
1044  // Can't thread an unconditional jump.
1045  if (BI->isUnconditional()) return false;
1046  Condition = BI->getCondition();
1047  } else if (SwitchInst *SI = dyn_cast<SwitchInst>(Terminator)) {
1048  Condition = SI->getCondition();
1049  } else if (IndirectBrInst *IB = dyn_cast<IndirectBrInst>(Terminator)) {
1050  // Can't thread indirect branch with no successors.
1051  if (IB->getNumSuccessors() == 0) return false;
1052  Condition = IB->getAddress()->stripPointerCasts();
1053  Preference = WantBlockAddress;
1054  } else {
1055  return false; // Must be an invoke.
1056  }
1057 
1058  // Run constant folding to see if we can reduce the condition to a simple
1059  // constant.
1060  if (Instruction *I = dyn_cast<Instruction>(Condition)) {
1061  Value *SimpleVal =
1063  if (SimpleVal) {
1064  I->replaceAllUsesWith(SimpleVal);
1065  if (isInstructionTriviallyDead(I, TLI))
1066  I->eraseFromParent();
1067  Condition = SimpleVal;
1068  }
1069  }
1070 
1071  // If the terminator is branching on an undef, we can pick any of the
1072  // successors to branch to. Let GetBestDestForJumpOnUndef decide.
1073  if (isa<UndefValue>(Condition)) {
1074  unsigned BestSucc = GetBestDestForJumpOnUndef(BB);
1075  std::vector<DominatorTree::UpdateType> Updates;
1076 
1077  // Fold the branch/switch.
1078  TerminatorInst *BBTerm = BB->getTerminator();
1079  Updates.reserve(BBTerm->getNumSuccessors());
1080  for (unsigned i = 0, e = BBTerm->getNumSuccessors(); i != e; ++i) {
1081  if (i == BestSucc) continue;
1082  BasicBlock *Succ = BBTerm->getSuccessor(i);
1083  Succ->removePredecessor(BB, true);
1084  Updates.push_back({DominatorTree::Delete, BB, Succ});
1085  }
1086 
1087  LLVM_DEBUG(dbgs() << " In block '" << BB->getName()
1088  << "' folding undef terminator: " << *BBTerm << '\n');
1089  BranchInst::Create(BBTerm->getSuccessor(BestSucc), BBTerm);
1090  BBTerm->eraseFromParent();
1091  DDT->applyUpdates(Updates);
1092  return true;
1093  }
1094 
1095  // If the terminator of this block is branching on a constant, simplify the
1096  // terminator to an unconditional branch. This can occur due to threading in
1097  // other blocks.
1098  if (getKnownConstant(Condition, Preference)) {
1099  LLVM_DEBUG(dbgs() << " In block '" << BB->getName()
1100  << "' folding terminator: " << *BB->getTerminator()
1101  << '\n');
1102  ++NumFolds;
1103  ConstantFoldTerminator(BB, true, nullptr, DDT);
1104  return true;
1105  }
1106 
1107  Instruction *CondInst = dyn_cast<Instruction>(Condition);
1108 
1109  // All the rest of our checks depend on the condition being an instruction.
1110  if (!CondInst) {
1111  // FIXME: Unify this with code below.
1112  if (ProcessThreadableEdges(Condition, BB, Preference, Terminator))
1113  return true;
1114  return false;
1115  }
1116 
1117  if (CmpInst *CondCmp = dyn_cast<CmpInst>(CondInst)) {
1118  // If we're branching on a conditional, LVI might be able to determine
1119  // it's value at the branch instruction. We only handle comparisons
1120  // against a constant at this time.
1121  // TODO: This should be extended to handle switches as well.
1122  BranchInst *CondBr = dyn_cast<BranchInst>(BB->getTerminator());
1123  Constant *CondConst = dyn_cast<Constant>(CondCmp->getOperand(1));
1124  if (CondBr && CondConst) {
1125  // We should have returned as soon as we turn a conditional branch to
1126  // unconditional. Because its no longer interesting as far as jump
1127  // threading is concerned.
1128  assert(CondBr->isConditional() && "Threading on unconditional terminator");
1129 
1130  if (DDT->pending())
1131  LVI->disableDT();
1132  else
1133  LVI->enableDT();
1135  LVI->getPredicateAt(CondCmp->getPredicate(), CondCmp->getOperand(0),
1136  CondConst, CondBr);
1137  if (Ret != LazyValueInfo::Unknown) {
1138  unsigned ToRemove = Ret == LazyValueInfo::True ? 1 : 0;
1139  unsigned ToKeep = Ret == LazyValueInfo::True ? 0 : 1;
1140  BasicBlock *ToRemoveSucc = CondBr->getSuccessor(ToRemove);
1141  ToRemoveSucc->removePredecessor(BB, true);
1142  BranchInst::Create(CondBr->getSuccessor(ToKeep), CondBr);
1143  CondBr->eraseFromParent();
1144  if (CondCmp->use_empty())
1145  CondCmp->eraseFromParent();
1146  // We can safely replace *some* uses of the CondInst if it has
1147  // exactly one value as returned by LVI. RAUW is incorrect in the
1148  // presence of guards and assumes, that have the `Cond` as the use. This
1149  // is because we use the guards/assume to reason about the `Cond` value
1150  // at the end of block, but RAUW unconditionally replaces all uses
1151  // including the guards/assumes themselves and the uses before the
1152  // guard/assume.
1153  else if (CondCmp->getParent() == BB) {
1154  auto *CI = Ret == LazyValueInfo::True ?
1155  ConstantInt::getTrue(CondCmp->getType()) :
1156  ConstantInt::getFalse(CondCmp->getType());
1157  ReplaceFoldableUses(CondCmp, CI);
1158  }
1159  DDT->deleteEdge(BB, ToRemoveSucc);
1160  return true;
1161  }
1162 
1163  // We did not manage to simplify this branch, try to see whether
1164  // CondCmp depends on a known phi-select pattern.
1165  if (TryToUnfoldSelect(CondCmp, BB))
1166  return true;
1167  }
1168  }
1169 
1170  // Check for some cases that are worth simplifying. Right now we want to look
1171  // for loads that are used by a switch or by the condition for the branch. If
1172  // we see one, check to see if it's partially redundant. If so, insert a PHI
1173  // which can then be used to thread the values.
1174  Value *SimplifyValue = CondInst;
1175  if (CmpInst *CondCmp = dyn_cast<CmpInst>(SimplifyValue))
1176  if (isa<Constant>(CondCmp->getOperand(1)))
1177  SimplifyValue = CondCmp->getOperand(0);
1178 
1179  // TODO: There are other places where load PRE would be profitable, such as
1180  // more complex comparisons.
1181  if (LoadInst *LoadI = dyn_cast<LoadInst>(SimplifyValue))
1182  if (SimplifyPartiallyRedundantLoad(LoadI))
1183  return true;
1184 
1185  // Before threading, try to propagate profile data backwards:
1186  if (PHINode *PN = dyn_cast<PHINode>(CondInst))
1187  if (PN->getParent() == BB && isa<BranchInst>(BB->getTerminator()))
1189 
1190  // Handle a variety of cases where we are branching on something derived from
1191  // a PHI node in the current block. If we can prove that any predecessors
1192  // compute a predictable value based on a PHI node, thread those predecessors.
1193  if (ProcessThreadableEdges(CondInst, BB, Preference, Terminator))
1194  return true;
1195 
1196  // If this is an otherwise-unfoldable branch on a phi node in the current
1197  // block, see if we can simplify.
1198  if (PHINode *PN = dyn_cast<PHINode>(CondInst))
1199  if (PN->getParent() == BB && isa<BranchInst>(BB->getTerminator()))
1200  return ProcessBranchOnPHI(PN);
1201 
1202  // If this is an otherwise-unfoldable branch on a XOR, see if we can simplify.
1203  if (CondInst->getOpcode() == Instruction::Xor &&
1204  CondInst->getParent() == BB && isa<BranchInst>(BB->getTerminator()))
1205  return ProcessBranchOnXOR(cast<BinaryOperator>(CondInst));
1206 
1207  // Search for a stronger dominating condition that can be used to simplify a
1208  // conditional branch leaving BB.
1209  if (ProcessImpliedCondition(BB))
1210  return true;
1211 
1212  return false;
1213 }
1214 
1216  auto *BI = dyn_cast<BranchInst>(BB->getTerminator());
1217  if (!BI || !BI->isConditional())
1218  return false;
1219 
1220  Value *Cond = BI->getCondition();
1221  BasicBlock *CurrentBB = BB;
1222  BasicBlock *CurrentPred = BB->getSinglePredecessor();
1223  unsigned Iter = 0;
1224 
1225  auto &DL = BB->getModule()->getDataLayout();
1226 
1227  while (CurrentPred && Iter++ < ImplicationSearchThreshold) {
1228  auto *PBI = dyn_cast<BranchInst>(CurrentPred->getTerminator());
1229  if (!PBI || !PBI->isConditional())
1230  return false;
1231  if (PBI->getSuccessor(0) != CurrentBB && PBI->getSuccessor(1) != CurrentBB)
1232  return false;
1233 
1234  bool CondIsTrue = PBI->getSuccessor(0) == CurrentBB;
1235  Optional<bool> Implication =
1236  isImpliedCondition(PBI->getCondition(), Cond, DL, CondIsTrue);
1237  if (Implication) {
1238  BasicBlock *KeepSucc = BI->getSuccessor(*Implication ? 0 : 1);
1239  BasicBlock *RemoveSucc = BI->getSuccessor(*Implication ? 1 : 0);
1240  RemoveSucc->removePredecessor(BB);
1241  BranchInst::Create(KeepSucc, BI);
1242  BI->eraseFromParent();
1243  DDT->deleteEdge(BB, RemoveSucc);
1244  return true;
1245  }
1246  CurrentBB = CurrentPred;
1247  CurrentPred = CurrentBB->getSinglePredecessor();
1248  }
1249 
1250  return false;
1251 }
1252 
1253 /// Return true if Op is an instruction defined in the given block.
1255  if (Instruction *OpInst = dyn_cast<Instruction>(Op))
1256  if (OpInst->getParent() == BB)
1257  return true;
1258  return false;
1259 }
1260 
1261 /// SimplifyPartiallyRedundantLoad - If LoadI is an obviously partially
1262 /// redundant load instruction, eliminate it by replacing it with a PHI node.
1263 /// This is an important optimization that encourages jump threading, and needs
1264 /// to be run interlaced with other jump threading tasks.
1266  // Don't hack volatile and ordered loads.
1267  if (!LoadI->isUnordered()) return false;
1268 
1269  // If the load is defined in a block with exactly one predecessor, it can't be
1270  // partially redundant.
1271  BasicBlock *LoadBB = LoadI->getParent();
1272  if (LoadBB->getSinglePredecessor())
1273  return false;
1274 
1275  // If the load is defined in an EH pad, it can't be partially redundant,
1276  // because the edges between the invoke and the EH pad cannot have other
1277  // instructions between them.
1278  if (LoadBB->isEHPad())
1279  return false;
1280 
1281  Value *LoadedPtr = LoadI->getOperand(0);
1282 
1283  // If the loaded operand is defined in the LoadBB and its not a phi,
1284  // it can't be available in predecessors.
1285  if (isOpDefinedInBlock(LoadedPtr, LoadBB) && !isa<PHINode>(LoadedPtr))
1286  return false;
1287 
1288  // Scan a few instructions up from the load, to see if it is obviously live at
1289  // the entry to its block.
1290  BasicBlock::iterator BBIt(LoadI);
1291  bool IsLoadCSE;
1292  if (Value *AvailableVal = FindAvailableLoadedValue(
1293  LoadI, LoadBB, BBIt, DefMaxInstsToScan, AA, &IsLoadCSE)) {
1294  // If the value of the load is locally available within the block, just use
1295  // it. This frequently occurs for reg2mem'd allocas.
1296 
1297  if (IsLoadCSE) {
1298  LoadInst *NLoadI = cast<LoadInst>(AvailableVal);
1299  combineMetadataForCSE(NLoadI, LoadI);
1300  };
1301 
1302  // If the returned value is the load itself, replace with an undef. This can
1303  // only happen in dead loops.
1304  if (AvailableVal == LoadI)
1305  AvailableVal = UndefValue::get(LoadI->getType());
1306  if (AvailableVal->getType() != LoadI->getType())
1307  AvailableVal = CastInst::CreateBitOrPointerCast(
1308  AvailableVal, LoadI->getType(), "", LoadI);
1309  LoadI->replaceAllUsesWith(AvailableVal);
1310  LoadI->eraseFromParent();
1311  return true;
1312  }
1313 
1314  // Otherwise, if we scanned the whole block and got to the top of the block,
1315  // we know the block is locally transparent to the load. If not, something
1316  // might clobber its value.
1317  if (BBIt != LoadBB->begin())
1318  return false;
1319 
1320  // If all of the loads and stores that feed the value have the same AA tags,
1321  // then we can propagate them onto any newly inserted loads.
1322  AAMDNodes AATags;
1323  LoadI->getAAMetadata(AATags);
1324 
1325  SmallPtrSet<BasicBlock*, 8> PredsScanned;
1326 
1327  using AvailablePredsTy = SmallVector<std::pair<BasicBlock *, Value *>, 8>;
1328 
1329  AvailablePredsTy AvailablePreds;
1330  BasicBlock *OneUnavailablePred = nullptr;
1331  SmallVector<LoadInst*, 8> CSELoads;
1332 
1333  // If we got here, the loaded value is transparent through to the start of the
1334  // block. Check to see if it is available in any of the predecessor blocks.
1335  for (BasicBlock *PredBB : predecessors(LoadBB)) {
1336  // If we already scanned this predecessor, skip it.
1337  if (!PredsScanned.insert(PredBB).second)
1338  continue;
1339 
1340  BBIt = PredBB->end();
1341  unsigned NumScanedInst = 0;
1342  Value *PredAvailable = nullptr;
1343  // NOTE: We don't CSE load that is volatile or anything stronger than
1344  // unordered, that should have been checked when we entered the function.
1345  assert(LoadI->isUnordered() &&
1346  "Attempting to CSE volatile or atomic loads");
1347  // If this is a load on a phi pointer, phi-translate it and search
1348  // for available load/store to the pointer in predecessors.
1349  Value *Ptr = LoadedPtr->DoPHITranslation(LoadBB, PredBB);
1350  PredAvailable = FindAvailablePtrLoadStore(
1351  Ptr, LoadI->getType(), LoadI->isAtomic(), PredBB, BBIt,
1352  DefMaxInstsToScan, AA, &IsLoadCSE, &NumScanedInst);
1353 
1354  // If PredBB has a single predecessor, continue scanning through the
1355  // single predecessor.
1356  BasicBlock *SinglePredBB = PredBB;
1357  while (!PredAvailable && SinglePredBB && BBIt == SinglePredBB->begin() &&
1358  NumScanedInst < DefMaxInstsToScan) {
1359  SinglePredBB = SinglePredBB->getSinglePredecessor();
1360  if (SinglePredBB) {
1361  BBIt = SinglePredBB->end();
1362  PredAvailable = FindAvailablePtrLoadStore(
1363  Ptr, LoadI->getType(), LoadI->isAtomic(), SinglePredBB, BBIt,
1364  (DefMaxInstsToScan - NumScanedInst), AA, &IsLoadCSE,
1365  &NumScanedInst);
1366  }
1367  }
1368 
1369  if (!PredAvailable) {
1370  OneUnavailablePred = PredBB;
1371  continue;
1372  }
1373 
1374  if (IsLoadCSE)
1375  CSELoads.push_back(cast<LoadInst>(PredAvailable));
1376 
1377  // If so, this load is partially redundant. Remember this info so that we
1378  // can create a PHI node.
1379  AvailablePreds.push_back(std::make_pair(PredBB, PredAvailable));
1380  }
1381 
1382  // If the loaded value isn't available in any predecessor, it isn't partially
1383  // redundant.
1384  if (AvailablePreds.empty()) return false;
1385 
1386  // Okay, the loaded value is available in at least one (and maybe all!)
1387  // predecessors. If the value is unavailable in more than one unique
1388  // predecessor, we want to insert a merge block for those common predecessors.
1389  // This ensures that we only have to insert one reload, thus not increasing
1390  // code size.
1391  BasicBlock *UnavailablePred = nullptr;
1392 
1393  // If the value is unavailable in one of predecessors, we will end up
1394  // inserting a new instruction into them. It is only valid if all the
1395  // instructions before LoadI are guaranteed to pass execution to its
1396  // successor, or if LoadI is safe to speculate.
1397  // TODO: If this logic becomes more complex, and we will perform PRE insertion
1398  // farther than to a predecessor, we need to reuse the code from GVN's PRE.
1399  // It requires domination tree analysis, so for this simple case it is an
1400  // overkill.
1401  if (PredsScanned.size() != AvailablePreds.size() &&
1403  for (auto I = LoadBB->begin(); &*I != LoadI; ++I)
1405  return false;
1406 
1407  // If there is exactly one predecessor where the value is unavailable, the
1408  // already computed 'OneUnavailablePred' block is it. If it ends in an
1409  // unconditional branch, we know that it isn't a critical edge.
1410  if (PredsScanned.size() == AvailablePreds.size()+1 &&
1411  OneUnavailablePred->getTerminator()->getNumSuccessors() == 1) {
1412  UnavailablePred = OneUnavailablePred;
1413  } else if (PredsScanned.size() != AvailablePreds.size()) {
1414  // Otherwise, we had multiple unavailable predecessors or we had a critical
1415  // edge from the one.
1416  SmallVector<BasicBlock*, 8> PredsToSplit;
1417  SmallPtrSet<BasicBlock*, 8> AvailablePredSet;
1418 
1419  for (const auto &AvailablePred : AvailablePreds)
1420  AvailablePredSet.insert(AvailablePred.first);
1421 
1422  // Add all the unavailable predecessors to the PredsToSplit list.
1423  for (BasicBlock *P : predecessors(LoadBB)) {
1424  // If the predecessor is an indirect goto, we can't split the edge.
1425  if (isa<IndirectBrInst>(P->getTerminator()))
1426  return false;
1427 
1428  if (!AvailablePredSet.count(P))
1429  PredsToSplit.push_back(P);
1430  }
1431 
1432  // Split them out to their own block.
1433  UnavailablePred = SplitBlockPreds(LoadBB, PredsToSplit, "thread-pre-split");
1434  }
1435 
1436  // If the value isn't available in all predecessors, then there will be
1437  // exactly one where it isn't available. Insert a load on that edge and add
1438  // it to the AvailablePreds list.
1439  if (UnavailablePred) {
1440  assert(UnavailablePred->getTerminator()->getNumSuccessors() == 1 &&
1441  "Can't handle critical edge here!");
1442  LoadInst *NewVal =
1443  new LoadInst(LoadedPtr->DoPHITranslation(LoadBB, UnavailablePred),
1444  LoadI->getName() + ".pr", false, LoadI->getAlignment(),
1445  LoadI->getOrdering(), LoadI->getSyncScopeID(),
1446  UnavailablePred->getTerminator());
1447  NewVal->setDebugLoc(LoadI->getDebugLoc());
1448  if (AATags)
1449  NewVal->setAAMetadata(AATags);
1450 
1451  AvailablePreds.push_back(std::make_pair(UnavailablePred, NewVal));
1452  }
1453 
1454  // Now we know that each predecessor of this block has a value in
1455  // AvailablePreds, sort them for efficient access as we're walking the preds.
1456  array_pod_sort(AvailablePreds.begin(), AvailablePreds.end());
1457 
1458  // Create a PHI node at the start of the block for the PRE'd load value.
1459  pred_iterator PB = pred_begin(LoadBB), PE = pred_end(LoadBB);
1460  PHINode *PN = PHINode::Create(LoadI->getType(), std::distance(PB, PE), "",
1461  &LoadBB->front());
1462  PN->takeName(LoadI);
1463  PN->setDebugLoc(LoadI->getDebugLoc());
1464 
1465  // Insert new entries into the PHI for each predecessor. A single block may
1466  // have multiple entries here.
1467  for (pred_iterator PI = PB; PI != PE; ++PI) {
1468  BasicBlock *P = *PI;
1469  AvailablePredsTy::iterator I =
1470  std::lower_bound(AvailablePreds.begin(), AvailablePreds.end(),
1471  std::make_pair(P, (Value*)nullptr));
1472 
1473  assert(I != AvailablePreds.end() && I->first == P &&
1474  "Didn't find entry for predecessor!");
1475 
1476  // If we have an available predecessor but it requires casting, insert the
1477  // cast in the predecessor and use the cast. Note that we have to update the
1478  // AvailablePreds vector as we go so that all of the PHI entries for this
1479  // predecessor use the same bitcast.
1480  Value *&PredV = I->second;
1481  if (PredV->getType() != LoadI->getType())
1482  PredV = CastInst::CreateBitOrPointerCast(PredV, LoadI->getType(), "",
1483  P->getTerminator());
1484 
1485  PN->addIncoming(PredV, I->first);
1486  }
1487 
1488  for (LoadInst *PredLoadI : CSELoads) {
1489  combineMetadataForCSE(PredLoadI, LoadI);
1490  }
1491 
1492  LoadI->replaceAllUsesWith(PN);
1493  LoadI->eraseFromParent();
1494 
1495  return true;
1496 }
1497 
1498 /// FindMostPopularDest - The specified list contains multiple possible
1499 /// threadable destinations. Pick the one that occurs the most frequently in
1500 /// the list.
1501 static BasicBlock *
1503  const SmallVectorImpl<std::pair<BasicBlock *,
1504  BasicBlock *>> &PredToDestList) {
1505  assert(!PredToDestList.empty());
1506 
1507  // Determine popularity. If there are multiple possible destinations, we
1508  // explicitly choose to ignore 'undef' destinations. We prefer to thread
1509  // blocks with known and real destinations to threading undef. We'll handle
1510  // them later if interesting.
1511  DenseMap<BasicBlock*, unsigned> DestPopularity;
1512  for (const auto &PredToDest : PredToDestList)
1513  if (PredToDest.second)
1514  DestPopularity[PredToDest.second]++;
1515 
1516  if (DestPopularity.empty())
1517  return nullptr;
1518 
1519  // Find the most popular dest.
1520  DenseMap<BasicBlock*, unsigned>::iterator DPI = DestPopularity.begin();
1521  BasicBlock *MostPopularDest = DPI->first;
1522  unsigned Popularity = DPI->second;
1523  SmallVector<BasicBlock*, 4> SamePopularity;
1524 
1525  for (++DPI; DPI != DestPopularity.end(); ++DPI) {
1526  // If the popularity of this entry isn't higher than the popularity we've
1527  // seen so far, ignore it.
1528  if (DPI->second < Popularity)
1529  ; // ignore.
1530  else if (DPI->second == Popularity) {
1531  // If it is the same as what we've seen so far, keep track of it.
1532  SamePopularity.push_back(DPI->first);
1533  } else {
1534  // If it is more popular, remember it.
1535  SamePopularity.clear();
1536  MostPopularDest = DPI->first;
1537  Popularity = DPI->second;
1538  }
1539  }
1540 
1541  // Okay, now we know the most popular destination. If there is more than one
1542  // destination, we need to determine one. This is arbitrary, but we need
1543  // to make a deterministic decision. Pick the first one that appears in the
1544  // successor list.
1545  if (!SamePopularity.empty()) {
1546  SamePopularity.push_back(MostPopularDest);
1547  TerminatorInst *TI = BB->getTerminator();
1548  for (unsigned i = 0; ; ++i) {
1549  assert(i != TI->getNumSuccessors() && "Didn't find any successor!");
1550 
1551  if (!is_contained(SamePopularity, TI->getSuccessor(i)))
1552  continue;
1553 
1554  MostPopularDest = TI->getSuccessor(i);
1555  break;
1556  }
1557  }
1558 
1559  // Okay, we have finally picked the most popular destination.
1560  return MostPopularDest;
1561 }
1562 
1565  Instruction *CxtI) {
1566  // If threading this would thread across a loop header, don't even try to
1567  // thread the edge.
1568  if (LoopHeaders.count(BB))
1569  return false;
1570 
1571  PredValueInfoTy PredValues;
1572  if (!ComputeValueKnownInPredecessors(Cond, BB, PredValues, Preference, CxtI))
1573  return false;
1574 
1575  assert(!PredValues.empty() &&
1576  "ComputeValueKnownInPredecessors returned true with no values");
1577 
1578  LLVM_DEBUG(dbgs() << "IN BB: " << *BB;
1579  for (const auto &PredValue : PredValues) {
1580  dbgs() << " BB '" << BB->getName()
1581  << "': FOUND condition = " << *PredValue.first
1582  << " for pred '" << PredValue.second->getName() << "'.\n";
1583  });
1584 
1585  // Decide what we want to thread through. Convert our list of known values to
1586  // a list of known destinations for each pred. This also discards duplicate
1587  // predecessors and keeps track of the undefined inputs (which are represented
1588  // as a null dest in the PredToDestList).
1589  SmallPtrSet<BasicBlock*, 16> SeenPreds;
1591 
1592  BasicBlock *OnlyDest = nullptr;
1593  BasicBlock *MultipleDestSentinel = (BasicBlock*)(intptr_t)~0ULL;
1594  Constant *OnlyVal = nullptr;
1595  Constant *MultipleVal = (Constant *)(intptr_t)~0ULL;
1596 
1597  unsigned PredWithKnownDest = 0;
1598  for (const auto &PredValue : PredValues) {
1599  BasicBlock *Pred = PredValue.second;
1600  if (!SeenPreds.insert(Pred).second)
1601  continue; // Duplicate predecessor entry.
1602 
1603  Constant *Val = PredValue.first;
1604 
1605  BasicBlock *DestBB;
1606  if (isa<UndefValue>(Val))
1607  DestBB = nullptr;
1608  else if (BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator())) {
1609  assert(isa<ConstantInt>(Val) && "Expecting a constant integer");
1610  DestBB = BI->getSuccessor(cast<ConstantInt>(Val)->isZero());
1611  } else if (SwitchInst *SI = dyn_cast<SwitchInst>(BB->getTerminator())) {
1612  assert(isa<ConstantInt>(Val) && "Expecting a constant integer");
1613  DestBB = SI->findCaseValue(cast<ConstantInt>(Val))->getCaseSuccessor();
1614  } else {
1615  assert(isa<IndirectBrInst>(BB->getTerminator())
1616  && "Unexpected terminator");
1617  assert(isa<BlockAddress>(Val) && "Expecting a constant blockaddress");
1618  DestBB = cast<BlockAddress>(Val)->getBasicBlock();
1619  }
1620 
1621  // If we have exactly one destination, remember it for efficiency below.
1622  if (PredToDestList.empty()) {
1623  OnlyDest = DestBB;
1624  OnlyVal = Val;
1625  } else {
1626  if (OnlyDest != DestBB)
1627  OnlyDest = MultipleDestSentinel;
1628  // It possible we have same destination, but different value, e.g. default
1629  // case in switchinst.
1630  if (Val != OnlyVal)
1631  OnlyVal = MultipleVal;
1632  }
1633 
1634  // We know where this predecessor is going.
1635  ++PredWithKnownDest;
1636 
1637  // If the predecessor ends with an indirect goto, we can't change its
1638  // destination.
1639  if (isa<IndirectBrInst>(Pred->getTerminator()))
1640  continue;
1641 
1642  PredToDestList.push_back(std::make_pair(Pred, DestBB));
1643  }
1644 
1645  // If all edges were unthreadable, we fail.
1646  if (PredToDestList.empty())
1647  return false;
1648 
1649  // If all the predecessors go to a single known successor, we want to fold,
1650  // not thread. By doing so, we do not need to duplicate the current block and
1651  // also miss potential opportunities in case we dont/cant duplicate.
1652  if (OnlyDest && OnlyDest != MultipleDestSentinel) {
1653  if (PredWithKnownDest == (size_t)pred_size(BB)) {
1654  bool SeenFirstBranchToOnlyDest = false;
1655  std::vector <DominatorTree::UpdateType> Updates;
1656  Updates.reserve(BB->getTerminator()->getNumSuccessors() - 1);
1657  for (BasicBlock *SuccBB : successors(BB)) {
1658  if (SuccBB == OnlyDest && !SeenFirstBranchToOnlyDest) {
1659  SeenFirstBranchToOnlyDest = true; // Don't modify the first branch.
1660  } else {
1661  SuccBB->removePredecessor(BB, true); // This is unreachable successor.
1662  Updates.push_back({DominatorTree::Delete, BB, SuccBB});
1663  }
1664  }
1665 
1666  // Finally update the terminator.
1667  TerminatorInst *Term = BB->getTerminator();
1668  BranchInst::Create(OnlyDest, Term);
1669  Term->eraseFromParent();
1670  DDT->applyUpdates(Updates);
1671 
1672  // If the condition is now dead due to the removal of the old terminator,
1673  // erase it.
1674  if (auto *CondInst = dyn_cast<Instruction>(Cond)) {
1675  if (CondInst->use_empty() && !CondInst->mayHaveSideEffects())
1676  CondInst->eraseFromParent();
1677  // We can safely replace *some* uses of the CondInst if it has
1678  // exactly one value as returned by LVI. RAUW is incorrect in the
1679  // presence of guards and assumes, that have the `Cond` as the use. This
1680  // is because we use the guards/assume to reason about the `Cond` value
1681  // at the end of block, but RAUW unconditionally replaces all uses
1682  // including the guards/assumes themselves and the uses before the
1683  // guard/assume.
1684  else if (OnlyVal && OnlyVal != MultipleVal &&
1685  CondInst->getParent() == BB)
1686  ReplaceFoldableUses(CondInst, OnlyVal);
1687  }
1688  return true;
1689  }
1690  }
1691 
1692  // Determine which is the most common successor. If we have many inputs and
1693  // this block is a switch, we want to start by threading the batch that goes
1694  // to the most popular destination first. If we only know about one
1695  // threadable destination (the common case) we can avoid this.
1696  BasicBlock *MostPopularDest = OnlyDest;
1697 
1698  if (MostPopularDest == MultipleDestSentinel) {
1699  // Remove any loop headers from the Dest list, ThreadEdge conservatively
1700  // won't process them, but we might have other destination that are eligible
1701  // and we still want to process.
1702  erase_if(PredToDestList,
1703  [&](const std::pair<BasicBlock *, BasicBlock *> &PredToDest) {
1704  return LoopHeaders.count(PredToDest.second) != 0;
1705  });
1706 
1707  if (PredToDestList.empty())
1708  return false;
1709 
1710  MostPopularDest = FindMostPopularDest(BB, PredToDestList);
1711  }
1712 
1713  // Now that we know what the most popular destination is, factor all
1714  // predecessors that will jump to it into a single predecessor.
1715  SmallVector<BasicBlock*, 16> PredsToFactor;
1716  for (const auto &PredToDest : PredToDestList)
1717  if (PredToDest.second == MostPopularDest) {
1718  BasicBlock *Pred = PredToDest.first;
1719 
1720  // This predecessor may be a switch or something else that has multiple
1721  // edges to the block. Factor each of these edges by listing them
1722  // according to # occurrences in PredsToFactor.
1723  for (BasicBlock *Succ : successors(Pred))
1724  if (Succ == BB)
1725  PredsToFactor.push_back(Pred);
1726  }
1727 
1728  // If the threadable edges are branching on an undefined value, we get to pick
1729  // the destination that these predecessors should get to.
1730  if (!MostPopularDest)
1731  MostPopularDest = BB->getTerminator()->
1732  getSuccessor(GetBestDestForJumpOnUndef(BB));
1733 
1734  // Ok, try to thread it!
1735  return ThreadEdge(BB, PredsToFactor, MostPopularDest);
1736 }
1737 
1738 /// ProcessBranchOnPHI - We have an otherwise unthreadable conditional branch on
1739 /// a PHI node in the current block. See if there are any simplifications we
1740 /// can do based on inputs to the phi node.
1742  BasicBlock *BB = PN->getParent();
1743 
1744  // TODO: We could make use of this to do it once for blocks with common PHI
1745  // values.
1747  PredBBs.resize(1);
1748 
1749  // If any of the predecessor blocks end in an unconditional branch, we can
1750  // *duplicate* the conditional branch into that block in order to further
1751  // encourage jump threading and to eliminate cases where we have branch on a
1752  // phi of an icmp (branch on icmp is much better).
1753  for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
1754  BasicBlock *PredBB = PN->getIncomingBlock(i);
1755  if (BranchInst *PredBr = dyn_cast<BranchInst>(PredBB->getTerminator()))
1756  if (PredBr->isUnconditional()) {
1757  PredBBs[0] = PredBB;
1758  // Try to duplicate BB into PredBB.
1759  if (DuplicateCondBranchOnPHIIntoPred(BB, PredBBs))
1760  return true;
1761  }
1762  }
1763 
1764  return false;
1765 }
1766 
1767 /// ProcessBranchOnXOR - We have an otherwise unthreadable conditional branch on
1768 /// a xor instruction in the current block. See if there are any
1769 /// simplifications we can do based on inputs to the xor.
1771  BasicBlock *BB = BO->getParent();
1772 
1773  // If either the LHS or RHS of the xor is a constant, don't do this
1774  // optimization.
1775  if (isa<ConstantInt>(BO->getOperand(0)) ||
1776  isa<ConstantInt>(BO->getOperand(1)))
1777  return false;
1778 
1779  // If the first instruction in BB isn't a phi, we won't be able to infer
1780  // anything special about any particular predecessor.
1781  if (!isa<PHINode>(BB->front()))
1782  return false;
1783 
1784  // If this BB is a landing pad, we won't be able to split the edge into it.
1785  if (BB->isEHPad())
1786  return false;
1787 
1788  // If we have a xor as the branch input to this block, and we know that the
1789  // LHS or RHS of the xor in any predecessor is true/false, then we can clone
1790  // the condition into the predecessor and fix that value to true, saving some
1791  // logical ops on that path and encouraging other paths to simplify.
1792  //
1793  // This copies something like this:
1794  //
1795  // BB:
1796  // %X = phi i1 [1], [%X']
1797  // %Y = icmp eq i32 %A, %B
1798  // %Z = xor i1 %X, %Y
1799  // br i1 %Z, ...
1800  //
1801  // Into:
1802  // BB':
1803  // %Y = icmp ne i32 %A, %B
1804  // br i1 %Y, ...
1805 
1806  PredValueInfoTy XorOpValues;
1807  bool isLHS = true;
1808  if (!ComputeValueKnownInPredecessors(BO->getOperand(0), BB, XorOpValues,
1809  WantInteger, BO)) {
1810  assert(XorOpValues.empty());
1811  if (!ComputeValueKnownInPredecessors(BO->getOperand(1), BB, XorOpValues,
1812  WantInteger, BO))
1813  return false;
1814  isLHS = false;
1815  }
1816 
1817  assert(!XorOpValues.empty() &&
1818  "ComputeValueKnownInPredecessors returned true with no values");
1819 
1820  // Scan the information to see which is most popular: true or false. The
1821  // predecessors can be of the set true, false, or undef.
1822  unsigned NumTrue = 0, NumFalse = 0;
1823  for (const auto &XorOpValue : XorOpValues) {
1824  if (isa<UndefValue>(XorOpValue.first))
1825  // Ignore undefs for the count.
1826  continue;
1827  if (cast<ConstantInt>(XorOpValue.first)->isZero())
1828  ++NumFalse;
1829  else
1830  ++NumTrue;
1831  }
1832 
1833  // Determine which value to split on, true, false, or undef if neither.
1834  ConstantInt *SplitVal = nullptr;
1835  if (NumTrue > NumFalse)
1836  SplitVal = ConstantInt::getTrue(BB->getContext());
1837  else if (NumTrue != 0 || NumFalse != 0)
1838  SplitVal = ConstantInt::getFalse(BB->getContext());
1839 
1840  // Collect all of the blocks that this can be folded into so that we can
1841  // factor this once and clone it once.
1842  SmallVector<BasicBlock*, 8> BlocksToFoldInto;
1843  for (const auto &XorOpValue : XorOpValues) {
1844  if (XorOpValue.first != SplitVal && !isa<UndefValue>(XorOpValue.first))
1845  continue;
1846 
1847  BlocksToFoldInto.push_back(XorOpValue.second);
1848  }
1849 
1850  // If we inferred a value for all of the predecessors, then duplication won't
1851  // help us. However, we can just replace the LHS or RHS with the constant.
1852  if (BlocksToFoldInto.size() ==
1853  cast<PHINode>(BB->front()).getNumIncomingValues()) {
1854  if (!SplitVal) {
1855  // If all preds provide undef, just nuke the xor, because it is undef too.
1857  BO->eraseFromParent();
1858  } else if (SplitVal->isZero()) {
1859  // If all preds provide 0, replace the xor with the other input.
1860  BO->replaceAllUsesWith(BO->getOperand(isLHS));
1861  BO->eraseFromParent();
1862  } else {
1863  // If all preds provide 1, set the computed value to 1.
1864  BO->setOperand(!isLHS, SplitVal);
1865  }
1866 
1867  return true;
1868  }
1869 
1870  // Try to duplicate BB into PredBB.
1871  return DuplicateCondBranchOnPHIIntoPred(BB, BlocksToFoldInto);
1872 }
1873 
1874 /// AddPHINodeEntriesForMappedBlock - We're adding 'NewPred' as a new
1875 /// predecessor to the PHIBB block. If it has PHI nodes, add entries for
1876 /// NewPred using the entries from OldPred (suitably mapped).
1878  BasicBlock *OldPred,
1879  BasicBlock *NewPred,
1881  for (PHINode &PN : PHIBB->phis()) {
1882  // Ok, we have a PHI node. Figure out what the incoming value was for the
1883  // DestBlock.
1884  Value *IV = PN.getIncomingValueForBlock(OldPred);
1885 
1886  // Remap the value if necessary.
1887  if (Instruction *Inst = dyn_cast<Instruction>(IV)) {
1889  if (I != ValueMap.end())
1890  IV = I->second;
1891  }
1892 
1893  PN.addIncoming(IV, NewPred);
1894  }
1895 }
1896 
1897 /// ThreadEdge - We have decided that it is safe and profitable to factor the
1898 /// blocks in PredBBs to one predecessor, then thread an edge from it to SuccBB
1899 /// across BB. Transform the IR to reflect this change.
1901  const SmallVectorImpl<BasicBlock *> &PredBBs,
1902  BasicBlock *SuccBB) {
1903  // If threading to the same block as we come from, we would infinite loop.
1904  if (SuccBB == BB) {
1905  LLVM_DEBUG(dbgs() << " Not threading across BB '" << BB->getName()
1906  << "' - would thread to self!\n");
1907  return false;
1908  }
1909 
1910  // If threading this would thread across a loop header, don't thread the edge.
1911  // See the comments above FindLoopHeaders for justifications and caveats.
1912  if (LoopHeaders.count(BB) || LoopHeaders.count(SuccBB)) {
1913  LLVM_DEBUG({
1914  bool BBIsHeader = LoopHeaders.count(BB);
1915  bool SuccIsHeader = LoopHeaders.count(SuccBB);
1916  dbgs() << " Not threading across "
1917  << (BBIsHeader ? "loop header BB '" : "block BB '") << BB->getName()
1918  << "' to dest " << (SuccIsHeader ? "loop header BB '" : "block BB '")
1919  << SuccBB->getName() << "' - it might create an irreducible loop!\n";
1920  });
1921  return false;
1922  }
1923 
1924  unsigned JumpThreadCost =
1925  getJumpThreadDuplicationCost(BB, BB->getTerminator(), BBDupThreshold);
1926  if (JumpThreadCost > BBDupThreshold) {
1927  LLVM_DEBUG(dbgs() << " Not threading BB '" << BB->getName()
1928  << "' - Cost is too high: " << JumpThreadCost << "\n");
1929  return false;
1930  }
1931 
1932  // And finally, do it! Start by factoring the predecessors if needed.
1933  BasicBlock *PredBB;
1934  if (PredBBs.size() == 1)
1935  PredBB = PredBBs[0];
1936  else {
1937  LLVM_DEBUG(dbgs() << " Factoring out " << PredBBs.size()
1938  << " common predecessors.\n");
1939  PredBB = SplitBlockPreds(BB, PredBBs, ".thr_comm");
1940  }
1941 
1942  // And finally, do it!
1943  LLVM_DEBUG(dbgs() << " Threading edge from '" << PredBB->getName()
1944  << "' to '" << SuccBB->getName()
1945  << "' with cost: " << JumpThreadCost
1946  << ", across block:\n " << *BB << "\n");
1947 
1948  if (DDT->pending())
1949  LVI->disableDT();
1950  else
1951  LVI->enableDT();
1952  LVI->threadEdge(PredBB, BB, SuccBB);
1953 
1954  // We are going to have to map operands from the original BB block to the new
1955  // copy of the block 'NewBB'. If there are PHI nodes in BB, evaluate them to
1956  // account for entry from PredBB.
1958 
1959  BasicBlock *NewBB = BasicBlock::Create(BB->getContext(),
1960  BB->getName()+".thread",
1961  BB->getParent(), BB);
1962  NewBB->moveAfter(PredBB);
1963 
1964  // Set the block frequency of NewBB.
1965  if (HasProfileData) {
1966  auto NewBBFreq =
1967  BFI->getBlockFreq(PredBB) * BPI->getEdgeProbability(PredBB, BB);
1968  BFI->setBlockFreq(NewBB, NewBBFreq.getFrequency());
1969  }
1970 
1971  BasicBlock::iterator BI = BB->begin();
1972  for (; PHINode *PN = dyn_cast<PHINode>(BI); ++BI)
1973  ValueMapping[PN] = PN->getIncomingValueForBlock(PredBB);
1974 
1975  // Clone the non-phi instructions of BB into NewBB, keeping track of the
1976  // mapping and using it to remap operands in the cloned instructions.
1977  for (; !isa<TerminatorInst>(BI); ++BI) {
1978  Instruction *New = BI->clone();
1979  New->setName(BI->getName());
1980  NewBB->getInstList().push_back(New);
1981  ValueMapping[&*BI] = New;
1982 
1983  // Remap operands to patch up intra-block references.
1984  for (unsigned i = 0, e = New->getNumOperands(); i != e; ++i)
1985  if (Instruction *Inst = dyn_cast<Instruction>(New->getOperand(i))) {
1986  DenseMap<Instruction*, Value*>::iterator I = ValueMapping.find(Inst);
1987  if (I != ValueMapping.end())
1988  New->setOperand(i, I->second);
1989  }
1990  }
1991 
1992  // We didn't copy the terminator from BB over to NewBB, because there is now
1993  // an unconditional jump to SuccBB. Insert the unconditional jump.
1994  BranchInst *NewBI = BranchInst::Create(SuccBB, NewBB);
1995  NewBI->setDebugLoc(BB->getTerminator()->getDebugLoc());
1996 
1997  // Check to see if SuccBB has PHI nodes. If so, we need to add entries to the
1998  // PHI nodes for NewBB now.
1999  AddPHINodeEntriesForMappedBlock(SuccBB, BB, NewBB, ValueMapping);
2000 
2001  // Update the terminator of PredBB to jump to NewBB instead of BB. This
2002  // eliminates predecessors from BB, which requires us to simplify any PHI
2003  // nodes in BB.
2004  TerminatorInst *PredTerm = PredBB->getTerminator();
2005  for (unsigned i = 0, e = PredTerm->getNumSuccessors(); i != e; ++i)
2006  if (PredTerm->getSuccessor(i) == BB) {
2007  BB->removePredecessor(PredBB, true);
2008  PredTerm->setSuccessor(i, NewBB);
2009  }
2010 
2011  // Enqueue required DT updates.
2012  DDT->applyUpdates({{DominatorTree::Insert, NewBB, SuccBB},
2013  {DominatorTree::Insert, PredBB, NewBB},
2014  {DominatorTree::Delete, PredBB, BB}});
2015 
2016  // If there were values defined in BB that are used outside the block, then we
2017  // now have to update all uses of the value to use either the original value,
2018  // the cloned value, or some PHI derived value. This can require arbitrary
2019  // PHI insertion, of which we are prepared to do, clean these up now.
2020  SSAUpdater SSAUpdate;
2021  SmallVector<Use*, 16> UsesToRename;
2022 
2023  for (Instruction &I : *BB) {
2024  // Scan all uses of this instruction to see if their uses are no longer
2025  // dominated by the previous def and if so, record them in UsesToRename.
2026  // Also, skip phi operands from PredBB - we'll remove them anyway.
2027  for (Use &U : I.uses()) {
2028  Instruction *User = cast<Instruction>(U.getUser());
2029  if (PHINode *UserPN = dyn_cast<PHINode>(User)) {
2030  if (UserPN->getIncomingBlock(U) == BB)
2031  continue;
2032  } else if (User->getParent() == BB)
2033  continue;
2034 
2035  UsesToRename.push_back(&U);
2036  }
2037 
2038  // If there are no uses outside the block, we're done with this instruction.
2039  if (UsesToRename.empty())
2040  continue;
2041  LLVM_DEBUG(dbgs() << "JT: Renaming non-local uses of: " << I << "\n");
2042 
2043  // We found a use of I outside of BB. Rename all uses of I that are outside
2044  // its block to be uses of the appropriate PHI node etc. See ValuesInBlocks
2045  // with the two values we know.
2046  SSAUpdate.Initialize(I.getType(), I.getName());
2047  SSAUpdate.AddAvailableValue(BB, &I);
2048  SSAUpdate.AddAvailableValue(NewBB, ValueMapping[&I]);
2049 
2050  while (!UsesToRename.empty())
2051  SSAUpdate.RewriteUse(*UsesToRename.pop_back_val());
2052  LLVM_DEBUG(dbgs() << "\n");
2053  }
2054 
2055  // At this point, the IR is fully up to date and consistent. Do a quick scan
2056  // over the new instructions and zap any that are constants or dead. This
2057  // frequently happens because of phi translation.
2058  SimplifyInstructionsInBlock(NewBB, TLI);
2059 
2060  // Update the edge weight from BB to SuccBB, which should be less than before.
2061  UpdateBlockFreqAndEdgeWeight(PredBB, BB, NewBB, SuccBB);
2062 
2063  // Threaded an edge!
2064  ++NumThreads;
2065  return true;
2066 }
2067 
2068 /// Create a new basic block that will be the predecessor of BB and successor of
2069 /// all blocks in Preds. When profile data is available, update the frequency of
2070 /// this new block.
2071 BasicBlock *JumpThreadingPass::SplitBlockPreds(BasicBlock *BB,
2072  ArrayRef<BasicBlock *> Preds,
2073  const char *Suffix) {
2075 
2076  // Collect the frequencies of all predecessors of BB, which will be used to
2077  // update the edge weight of the result of splitting predecessors.
2079  if (HasProfileData)
2080  for (auto Pred : Preds)
2081  FreqMap.insert(std::make_pair(
2082  Pred, BFI->getBlockFreq(Pred) * BPI->getEdgeProbability(Pred, BB)));
2083 
2084  // In the case when BB is a LandingPad block we create 2 new predecessors
2085  // instead of just one.
2086  if (BB->isLandingPad()) {
2087  std::string NewName = std::string(Suffix) + ".split-lp";
2088  SplitLandingPadPredecessors(BB, Preds, Suffix, NewName.c_str(), NewBBs);
2089  } else {
2090  NewBBs.push_back(SplitBlockPredecessors(BB, Preds, Suffix));
2091  }
2092 
2093  std::vector<DominatorTree::UpdateType> Updates;
2094  Updates.reserve((2 * Preds.size()) + NewBBs.size());
2095  for (auto NewBB : NewBBs) {
2096  BlockFrequency NewBBFreq(0);
2097  Updates.push_back({DominatorTree::Insert, NewBB, BB});
2098  for (auto Pred : predecessors(NewBB)) {
2099  Updates.push_back({DominatorTree::Delete, Pred, BB});
2100  Updates.push_back({DominatorTree::Insert, Pred, NewBB});
2101  if (HasProfileData) // Update frequencies between Pred -> NewBB.
2102  NewBBFreq += FreqMap.lookup(Pred);
2103  }
2104  if (HasProfileData) // Apply the summed frequency to NewBB.
2105  BFI->setBlockFreq(NewBB, NewBBFreq.getFrequency());
2106  }
2107 
2108  DDT->applyUpdates(Updates);
2109  return NewBBs[0];
2110 }
2111 
2112 bool JumpThreadingPass::doesBlockHaveProfileData(BasicBlock *BB) {
2113  const TerminatorInst *TI = BB->getTerminator();
2114  assert(TI->getNumSuccessors() > 1 && "not a split");
2115 
2116  MDNode *WeightsNode = TI->getMetadata(LLVMContext::MD_prof);
2117  if (!WeightsNode)
2118  return false;
2119 
2120  MDString *MDName = cast<MDString>(WeightsNode->getOperand(0));
2121  if (MDName->getString() != "branch_weights")
2122  return false;
2123 
2124  // Ensure there are weights for all of the successors. Note that the first
2125  // operand to the metadata node is a name, not a weight.
2126  return WeightsNode->getNumOperands() == TI->getNumSuccessors() + 1;
2127 }
2128 
2129 /// Update the block frequency of BB and branch weight and the metadata on the
2130 /// edge BB->SuccBB. This is done by scaling the weight of BB->SuccBB by 1 -
2131 /// Freq(PredBB->BB) / Freq(BB->SuccBB).
2132 void JumpThreadingPass::UpdateBlockFreqAndEdgeWeight(BasicBlock *PredBB,
2133  BasicBlock *BB,
2134  BasicBlock *NewBB,
2135  BasicBlock *SuccBB) {
2136  if (!HasProfileData)
2137  return;
2138 
2139  assert(BFI && BPI && "BFI & BPI should have been created here");
2140 
2141  // As the edge from PredBB to BB is deleted, we have to update the block
2142  // frequency of BB.
2143  auto BBOrigFreq = BFI->getBlockFreq(BB);
2144  auto NewBBFreq = BFI->getBlockFreq(NewBB);
2145  auto BB2SuccBBFreq = BBOrigFreq * BPI->getEdgeProbability(BB, SuccBB);
2146  auto BBNewFreq = BBOrigFreq - NewBBFreq;
2147  BFI->setBlockFreq(BB, BBNewFreq.getFrequency());
2148 
2149  // Collect updated outgoing edges' frequencies from BB and use them to update
2150  // edge probabilities.
2151  SmallVector<uint64_t, 4> BBSuccFreq;
2152  for (BasicBlock *Succ : successors(BB)) {
2153  auto SuccFreq = (Succ == SuccBB)
2154  ? BB2SuccBBFreq - NewBBFreq
2155  : BBOrigFreq * BPI->getEdgeProbability(BB, Succ);
2156  BBSuccFreq.push_back(SuccFreq.getFrequency());
2157  }
2158 
2159  uint64_t MaxBBSuccFreq =
2160  *std::max_element(BBSuccFreq.begin(), BBSuccFreq.end());
2161 
2163  if (MaxBBSuccFreq == 0)
2164  BBSuccProbs.assign(BBSuccFreq.size(),
2165  {1, static_cast<unsigned>(BBSuccFreq.size())});
2166  else {
2167  for (uint64_t Freq : BBSuccFreq)
2168  BBSuccProbs.push_back(
2169  BranchProbability::getBranchProbability(Freq, MaxBBSuccFreq));
2170  // Normalize edge probabilities so that they sum up to one.
2171  BranchProbability::normalizeProbabilities(BBSuccProbs.begin(),
2172  BBSuccProbs.end());
2173  }
2174 
2175  // Update edge probabilities in BPI.
2176  for (int I = 0, E = BBSuccProbs.size(); I < E; I++)
2177  BPI->setEdgeProbability(BB, I, BBSuccProbs[I]);
2178 
2179  // Update the profile metadata as well.
2180  //
2181  // Don't do this if the profile of the transformed blocks was statically
2182  // estimated. (This could occur despite the function having an entry
2183  // frequency in completely cold parts of the CFG.)
2184  //
2185  // In this case we don't want to suggest to subsequent passes that the
2186  // calculated weights are fully consistent. Consider this graph:
2187  //
2188  // check_1
2189  // 50% / |
2190  // eq_1 | 50%
2191  // \ |
2192  // check_2
2193  // 50% / |
2194  // eq_2 | 50%
2195  // \ |
2196  // check_3
2197  // 50% / |
2198  // eq_3 | 50%
2199  // \ |
2200  //
2201  // Assuming the blocks check_* all compare the same value against 1, 2 and 3,
2202  // the overall probabilities are inconsistent; the total probability that the
2203  // value is either 1, 2 or 3 is 150%.
2204  //
2205  // As a consequence if we thread eq_1 -> check_2 to check_3, check_2->check_3
2206  // becomes 0%. This is even worse if the edge whose probability becomes 0% is
2207  // the loop exit edge. Then based solely on static estimation we would assume
2208  // the loop was extremely hot.
2209  //
2210  // FIXME this locally as well so that BPI and BFI are consistent as well. We
2211  // shouldn't make edges extremely likely or unlikely based solely on static
2212  // estimation.
2213  if (BBSuccProbs.size() >= 2 && doesBlockHaveProfileData(BB)) {
2214  SmallVector<uint32_t, 4> Weights;
2215  for (auto Prob : BBSuccProbs)
2216  Weights.push_back(Prob.getNumerator());
2217 
2218  auto TI = BB->getTerminator();
2219  TI->setMetadata(
2221  MDBuilder(TI->getParent()->getContext()).createBranchWeights(Weights));
2222  }
2223 }
2224 
2225 /// DuplicateCondBranchOnPHIIntoPred - PredBB contains an unconditional branch
2226 /// to BB which contains an i1 PHI node and a conditional branch on that PHI.
2227 /// If we can duplicate the contents of BB up into PredBB do so now, this
2228 /// improves the odds that the branch will be on an analyzable instruction like
2229 /// a compare.
2231  BasicBlock *BB, const SmallVectorImpl<BasicBlock *> &PredBBs) {
2232  assert(!PredBBs.empty() && "Can't handle an empty set");
2233 
2234  // If BB is a loop header, then duplicating this block outside the loop would
2235  // cause us to transform this into an irreducible loop, don't do this.
2236  // See the comments above FindLoopHeaders for justifications and caveats.
2237  if (LoopHeaders.count(BB)) {
2238  LLVM_DEBUG(dbgs() << " Not duplicating loop header '" << BB->getName()
2239  << "' into predecessor block '" << PredBBs[0]->getName()
2240  << "' - it might create an irreducible loop!\n");
2241  return false;
2242  }
2243 
2244  unsigned DuplicationCost =
2245  getJumpThreadDuplicationCost(BB, BB->getTerminator(), BBDupThreshold);
2246  if (DuplicationCost > BBDupThreshold) {
2247  LLVM_DEBUG(dbgs() << " Not duplicating BB '" << BB->getName()
2248  << "' - Cost is too high: " << DuplicationCost << "\n");
2249  return false;
2250  }
2251 
2252  // And finally, do it! Start by factoring the predecessors if needed.
2253  std::vector<DominatorTree::UpdateType> Updates;
2254  BasicBlock *PredBB;
2255  if (PredBBs.size() == 1)
2256  PredBB = PredBBs[0];
2257  else {
2258  LLVM_DEBUG(dbgs() << " Factoring out " << PredBBs.size()
2259  << " common predecessors.\n");
2260  PredBB = SplitBlockPreds(BB, PredBBs, ".thr_comm");
2261  }
2262  Updates.push_back({DominatorTree::Delete, PredBB, BB});
2263 
2264  // Okay, we decided to do this! Clone all the instructions in BB onto the end
2265  // of PredBB.
2266  LLVM_DEBUG(dbgs() << " Duplicating block '" << BB->getName()
2267  << "' into end of '" << PredBB->getName()
2268  << "' to eliminate branch on phi. Cost: "
2269  << DuplicationCost << " block is:" << *BB << "\n");
2270 
2271  // Unless PredBB ends with an unconditional branch, split the edge so that we
2272  // can just clone the bits from BB into the end of the new PredBB.
2273  BranchInst *OldPredBranch = dyn_cast<BranchInst>(PredBB->getTerminator());
2274 
2275  if (!OldPredBranch || !OldPredBranch->isUnconditional()) {
2276  BasicBlock *OldPredBB = PredBB;
2277  PredBB = SplitEdge(OldPredBB, BB);
2278  Updates.push_back({DominatorTree::Insert, OldPredBB, PredBB});
2279  Updates.push_back({DominatorTree::Insert, PredBB, BB});
2280  Updates.push_back({DominatorTree::Delete, OldPredBB, BB});
2281  OldPredBranch = cast<BranchInst>(PredBB->getTerminator());
2282  }
2283 
2284  // We are going to have to map operands from the original BB block into the
2285  // PredBB block. Evaluate PHI nodes in BB.
2287 
2288  BasicBlock::iterator BI = BB->begin();
2289  for (; PHINode *PN = dyn_cast<PHINode>(BI); ++BI)
2290  ValueMapping[PN] = PN->getIncomingValueForBlock(PredBB);
2291  // Clone the non-phi instructions of BB into PredBB, keeping track of the
2292  // mapping and using it to remap operands in the cloned instructions.
2293  for (; BI != BB->end(); ++BI) {
2294  Instruction *New = BI->clone();
2295 
2296  // Remap operands to patch up intra-block references.
2297  for (unsigned i = 0, e = New->getNumOperands(); i != e; ++i)
2298  if (Instruction *Inst = dyn_cast<Instruction>(New->getOperand(i))) {
2299  DenseMap<Instruction*, Value*>::iterator I = ValueMapping.find(Inst);
2300  if (I != ValueMapping.end())
2301  New->setOperand(i, I->second);
2302  }
2303 
2304  // If this instruction can be simplified after the operands are updated,
2305  // just use the simplified value instead. This frequently happens due to
2306  // phi translation.
2307  if (Value *IV = SimplifyInstruction(
2308  New,
2309  {BB->getModule()->getDataLayout(), TLI, nullptr, nullptr, New})) {
2310  ValueMapping[&*BI] = IV;
2311  if (!New->mayHaveSideEffects()) {
2312  New->deleteValue();
2313  New = nullptr;
2314  }
2315  } else {
2316  ValueMapping[&*BI] = New;
2317  }
2318  if (New) {
2319  // Otherwise, insert the new instruction into the block.
2320  New->setName(BI->getName());
2321  PredBB->getInstList().insert(OldPredBranch->getIterator(), New);
2322  // Update Dominance from simplified New instruction operands.
2323  for (unsigned i = 0, e = New->getNumOperands(); i != e; ++i)
2324  if (BasicBlock *SuccBB = dyn_cast<BasicBlock>(New->getOperand(i)))
2325  Updates.push_back({DominatorTree::Insert, PredBB, SuccBB});
2326  }
2327  }
2328 
2329  // Check to see if the targets of the branch had PHI nodes. If so, we need to
2330  // add entries to the PHI nodes for branch from PredBB now.
2331  BranchInst *BBBranch = cast<BranchInst>(BB->getTerminator());
2332  AddPHINodeEntriesForMappedBlock(BBBranch->getSuccessor(0), BB, PredBB,
2333  ValueMapping);
2334  AddPHINodeEntriesForMappedBlock(BBBranch->getSuccessor(1), BB, PredBB,
2335  ValueMapping);
2336 
2337  // If there were values defined in BB that are used outside the block, then we
2338  // now have to update all uses of the value to use either the original value,
2339  // the cloned value, or some PHI derived value. This can require arbitrary
2340  // PHI insertion, of which we are prepared to do, clean these up now.
2341  SSAUpdater SSAUpdate;
2342  SmallVector<Use*, 16> UsesToRename;
2343  for (Instruction &I : *BB) {
2344  // Scan all uses of this instruction to see if it is used outside of its
2345  // block, and if so, record them in UsesToRename.
2346  for (Use &U : I.uses()) {
2347  Instruction *User = cast<Instruction>(U.getUser());
2348  if (PHINode *UserPN = dyn_cast<PHINode>(User)) {
2349  if (UserPN->getIncomingBlock(U) == BB)
2350  continue;
2351  } else if (User->getParent() == BB)
2352  continue;
2353 
2354  UsesToRename.push_back(&U);
2355  }
2356 
2357  // If there are no uses outside the block, we're done with this instruction.
2358  if (UsesToRename.empty())
2359  continue;
2360 
2361  LLVM_DEBUG(dbgs() << "JT: Renaming non-local uses of: " << I << "\n");
2362 
2363  // We found a use of I outside of BB. Rename all uses of I that are outside
2364  // its block to be uses of the appropriate PHI node etc. See ValuesInBlocks
2365  // with the two values we know.
2366  SSAUpdate.Initialize(I.getType(), I.getName());
2367  SSAUpdate.AddAvailableValue(BB, &I);
2368  SSAUpdate.AddAvailableValue(PredBB, ValueMapping[&I]);
2369 
2370  while (!UsesToRename.empty())
2371  SSAUpdate.RewriteUse(*UsesToRename.pop_back_val());
2372  LLVM_DEBUG(dbgs() << "\n");
2373  }
2374 
2375  // PredBB no longer jumps to BB, remove entries in the PHI node for the edge
2376  // that we nuked.
2377  BB->removePredecessor(PredBB, true);
2378 
2379  // Remove the unconditional branch at the end of the PredBB block.
2380  OldPredBranch->eraseFromParent();
2381  DDT->applyUpdates(Updates);
2382 
2383  ++NumDupes;
2384  return true;
2385 }
2386 
2387 /// TryToUnfoldSelect - Look for blocks of the form
2388 /// bb1:
2389 /// %a = select
2390 /// br bb2
2391 ///
2392 /// bb2:
2393 /// %p = phi [%a, %bb1] ...
2394 /// %c = icmp %p
2395 /// br i1 %c
2396 ///
2397 /// And expand the select into a branch structure if one of its arms allows %c
2398 /// to be folded. This later enables threading from bb1 over bb2.
2400  BranchInst *CondBr = dyn_cast<BranchInst>(BB->getTerminator());
2401  PHINode *CondLHS = dyn_cast<PHINode>(CondCmp->getOperand(0));
2402  Constant *CondRHS = cast<Constant>(CondCmp->getOperand(1));
2403 
2404  if (!CondBr || !CondBr->isConditional() || !CondLHS ||
2405  CondLHS->getParent() != BB)
2406  return false;
2407 
2408  for (unsigned I = 0, E = CondLHS->getNumIncomingValues(); I != E; ++I) {
2409  BasicBlock *Pred = CondLHS->getIncomingBlock(I);
2410  SelectInst *SI = dyn_cast<SelectInst>(CondLHS->getIncomingValue(I));
2411 
2412  // Look if one of the incoming values is a select in the corresponding
2413  // predecessor.
2414  if (!SI || SI->getParent() != Pred || !SI->hasOneUse())
2415  continue;
2416 
2417  BranchInst *PredTerm = dyn_cast<BranchInst>(Pred->getTerminator());
2418  if (!PredTerm || !PredTerm->isUnconditional())
2419  continue;
2420 
2421  // Now check if one of the select values would allow us to constant fold the
2422  // terminator in BB. We don't do the transform if both sides fold, those
2423  // cases will be threaded in any case.
2424  if (DDT->pending())
2425  LVI->disableDT();
2426  else
2427  LVI->enableDT();
2428  LazyValueInfo::Tristate LHSFolds =
2429  LVI->getPredicateOnEdge(CondCmp->getPredicate(), SI->getOperand(1),
2430  CondRHS, Pred, BB, CondCmp);
2431  LazyValueInfo::Tristate RHSFolds =
2432  LVI->getPredicateOnEdge(CondCmp->getPredicate(), SI->getOperand(2),
2433  CondRHS, Pred, BB, CondCmp);
2434  if ((LHSFolds != LazyValueInfo::Unknown ||
2435  RHSFolds != LazyValueInfo::Unknown) &&
2436  LHSFolds != RHSFolds) {
2437  // Expand the select.
2438  //
2439  // Pred --
2440  // | v
2441  // | NewBB
2442  // | |
2443  // |-----
2444  // v
2445  // BB
2446  BasicBlock *NewBB = BasicBlock::Create(BB->getContext(), "select.unfold",
2447  BB->getParent(), BB);
2448  // Move the unconditional branch to NewBB.
2449  PredTerm->removeFromParent();
2450  NewBB->getInstList().insert(NewBB->end(), PredTerm);
2451  // Create a conditional branch and update PHI nodes.
2452  BranchInst::Create(NewBB, BB, SI->getCondition(), Pred);
2453  CondLHS->setIncomingValue(I, SI->getFalseValue());
2454  CondLHS->addIncoming(SI->getTrueValue(), NewBB);
2455  // The select is now dead.
2456  SI->eraseFromParent();
2457 
2458  DDT->applyUpdates({{DominatorTree::Insert, NewBB, BB},
2459  {DominatorTree::Insert, Pred, NewBB}});
2460  // Update any other PHI nodes in BB.
2461  for (BasicBlock::iterator BI = BB->begin();
2462  PHINode *Phi = dyn_cast<PHINode>(BI); ++BI)
2463  if (Phi != CondLHS)
2464  Phi->addIncoming(Phi->getIncomingValueForBlock(Pred), NewBB);
2465  return true;
2466  }
2467  }
2468  return false;
2469 }
2470 
2471 /// TryToUnfoldSelectInCurrBB - Look for PHI/Select or PHI/CMP/Select in the
2472 /// same BB in the form
2473 /// bb:
2474 /// %p = phi [false, %bb1], [true, %bb2], [false, %bb3], [true, %bb4], ...
2475 /// %s = select %p, trueval, falseval
2476 ///
2477 /// or
2478 ///
2479 /// bb:
2480 /// %p = phi [0, %bb1], [1, %bb2], [0, %bb3], [1, %bb4], ...
2481 /// %c = cmp %p, 0
2482 /// %s = select %c, trueval, falseval
2483 ///
2484 /// And expand the select into a branch structure. This later enables
2485 /// jump-threading over bb in this pass.
2486 ///
2487 /// Using the similar approach of SimplifyCFG::FoldCondBranchOnPHI(), unfold
2488 /// select if the associated PHI has at least one constant. If the unfolded
2489 /// select is not jump-threaded, it will be folded again in the later
2490 /// optimizations.
2492  // If threading this would thread across a loop header, don't thread the edge.
2493  // See the comments above FindLoopHeaders for justifications and caveats.
2494  if (LoopHeaders.count(BB))
2495  return false;
2496 
2497  for (BasicBlock::iterator BI = BB->begin();
2498  PHINode *PN = dyn_cast<PHINode>(BI); ++BI) {
2499  // Look for a Phi having at least one constant incoming value.
2500  if (llvm::all_of(PN->incoming_values(),
2501  [](Value *V) { return !isa<ConstantInt>(V); }))
2502  continue;
2503 
2504  auto isUnfoldCandidate = [BB](SelectInst *SI, Value *V) {
2505  // Check if SI is in BB and use V as condition.
2506  if (SI->getParent() != BB)
2507  return false;
2508  Value *Cond = SI->getCondition();
2509  return (Cond && Cond == V && Cond->getType()->isIntegerTy(1));
2510  };
2511 
2512  SelectInst *SI = nullptr;
2513  for (Use &U : PN->uses()) {
2514  if (ICmpInst *Cmp = dyn_cast<ICmpInst>(U.getUser())) {
2515  // Look for a ICmp in BB that compares PN with a constant and is the
2516  // condition of a Select.
2517  if (Cmp->getParent() == BB && Cmp->hasOneUse() &&
2518  isa<ConstantInt>(Cmp->getOperand(1 - U.getOperandNo())))
2519  if (SelectInst *SelectI = dyn_cast<SelectInst>(Cmp->user_back()))
2520  if (isUnfoldCandidate(SelectI, Cmp->use_begin()->get())) {
2521  SI = SelectI;
2522  break;
2523  }
2524  } else if (SelectInst *SelectI = dyn_cast<SelectInst>(U.getUser())) {
2525  // Look for a Select in BB that uses PN as condition.
2526  if (isUnfoldCandidate(SelectI, U.get())) {
2527  SI = SelectI;
2528  break;
2529  }
2530  }
2531  }
2532 
2533  if (!SI)
2534  continue;
2535  // Expand the select.
2536  TerminatorInst *Term =
2537  SplitBlockAndInsertIfThen(SI->getCondition(), SI, false);
2538  BasicBlock *SplitBB = SI->getParent();
2539  BasicBlock *NewBB = Term->getParent();
2540  PHINode *NewPN = PHINode::Create(SI->getType(), 2, "", SI);
2541  NewPN->addIncoming(SI->getTrueValue(), Term->getParent());
2542  NewPN->addIncoming(SI->getFalseValue(), BB);
2543  SI->replaceAllUsesWith(NewPN);
2544  SI->eraseFromParent();
2545  // NewBB and SplitBB are newly created blocks which require insertion.
2546  std::vector<DominatorTree::UpdateType> Updates;
2547  Updates.reserve((2 * SplitBB->getTerminator()->getNumSuccessors()) + 3);
2548  Updates.push_back({DominatorTree::Insert, BB, SplitBB});
2549  Updates.push_back({DominatorTree::Insert, BB, NewBB});
2550  Updates.push_back({DominatorTree::Insert, NewBB, SplitBB});
2551  // BB's successors were moved to SplitBB, update DDT accordingly.
2552  for (auto *Succ : successors(SplitBB)) {
2553  Updates.push_back({DominatorTree::Delete, BB, Succ});
2554  Updates.push_back({DominatorTree::Insert, SplitBB, Succ});
2555  }
2556  DDT->applyUpdates(Updates);
2557  return true;
2558  }
2559  return false;
2560 }
2561 
2562 /// Try to propagate a guard from the current BB into one of its predecessors
2563 /// in case if another branch of execution implies that the condition of this
2564 /// guard is always true. Currently we only process the simplest case that
2565 /// looks like:
2566 ///
2567 /// Start:
2568 /// %cond = ...
2569 /// br i1 %cond, label %T1, label %F1
2570 /// T1:
2571 /// br label %Merge
2572 /// F1:
2573 /// br label %Merge
2574 /// Merge:
2575 /// %condGuard = ...
2576 /// call void(i1, ...) @llvm.experimental.guard( i1 %condGuard )[ "deopt"() ]
2577 ///
2578 /// And cond either implies condGuard or !condGuard. In this case all the
2579 /// instructions before the guard can be duplicated in both branches, and the
2580 /// guard is then threaded to one of them.
2582  using namespace PatternMatch;
2583 
2584  // We only want to deal with two predecessors.
2585  BasicBlock *Pred1, *Pred2;
2586  auto PI = pred_begin(BB), PE = pred_end(BB);
2587  if (PI == PE)
2588  return false;
2589  Pred1 = *PI++;
2590  if (PI == PE)
2591  return false;
2592  Pred2 = *PI++;
2593  if (PI != PE)
2594  return false;
2595  if (Pred1 == Pred2)
2596  return false;
2597 
2598  // Try to thread one of the guards of the block.
2599  // TODO: Look up deeper than to immediate predecessor?
2600  auto *Parent = Pred1->getSinglePredecessor();
2601  if (!Parent || Parent != Pred2->getSinglePredecessor())
2602  return false;
2603 
2604  if (auto *BI = dyn_cast<BranchInst>(Parent->getTerminator()))
2605  for (auto &I : *BB)
2606  if (match(&I, m_Intrinsic<Intrinsic::experimental_guard>()))
2607  if (ThreadGuard(BB, cast<IntrinsicInst>(&I), BI))
2608  return true;
2609 
2610  return false;
2611 }
2612 
2613 /// Try to propagate the guard from BB which is the lower block of a diamond
2614 /// to one of its branches, in case if diamond's condition implies guard's
2615 /// condition.
2617  BranchInst *BI) {
2618  assert(BI->getNumSuccessors() == 2 && "Wrong number of successors?");
2619  assert(BI->isConditional() && "Unconditional branch has 2 successors?");
2620  Value *GuardCond = Guard->getArgOperand(0);
2621  Value *BranchCond = BI->getCondition();
2622  BasicBlock *TrueDest = BI->getSuccessor(0);
2623  BasicBlock *FalseDest = BI->getSuccessor(1);
2624 
2625  auto &DL = BB->getModule()->getDataLayout();
2626  bool TrueDestIsSafe = false;
2627  bool FalseDestIsSafe = false;
2628 
2629  // True dest is safe if BranchCond => GuardCond.
2630  auto Impl = isImpliedCondition(BranchCond, GuardCond, DL);
2631  if (Impl && *Impl)
2632  TrueDestIsSafe = true;
2633  else {
2634  // False dest is safe if !BranchCond => GuardCond.
2635  Impl = isImpliedCondition(BranchCond, GuardCond, DL, /* LHSIsTrue */ false);
2636  if (Impl && *Impl)
2637  FalseDestIsSafe = true;
2638  }
2639 
2640  if (!TrueDestIsSafe && !FalseDestIsSafe)
2641  return false;
2642 
2643  BasicBlock *PredUnguardedBlock = TrueDestIsSafe ? TrueDest : FalseDest;
2644  BasicBlock *PredGuardedBlock = FalseDestIsSafe ? TrueDest : FalseDest;
2645 
2646  ValueToValueMapTy UnguardedMapping, GuardedMapping;
2647  Instruction *AfterGuard = Guard->getNextNode();
2648  unsigned Cost = getJumpThreadDuplicationCost(BB, AfterGuard, BBDupThreshold);
2649  if (Cost > BBDupThreshold)
2650  return false;
2651  // Duplicate all instructions before the guard and the guard itself to the
2652  // branch where implication is not proved.
2654  BB, PredGuardedBlock, AfterGuard, GuardedMapping);
2655  assert(GuardedBlock && "Could not create the guarded block?");
2656  // Duplicate all instructions before the guard in the unguarded branch.
2657  // Since we have successfully duplicated the guarded block and this block
2658  // has fewer instructions, we expect it to succeed.
2660  BB, PredUnguardedBlock, Guard, UnguardedMapping);
2661  assert(UnguardedBlock && "Could not create the unguarded block?");
2662  LLVM_DEBUG(dbgs() << "Moved guard " << *Guard << " to block "
2663  << GuardedBlock->getName() << "\n");
2664  // DuplicateInstructionsInSplitBetween inserts a new block "BB.split" between
2665  // PredBB and BB. We need to perform two inserts and one delete for each of
2666  // the above calls to update Dominators.
2667  DDT->applyUpdates(
2668  {// Guarded block split.
2669  {DominatorTree::Delete, PredGuardedBlock, BB},
2670  {DominatorTree::Insert, PredGuardedBlock, GuardedBlock},
2671  {DominatorTree::Insert, GuardedBlock, BB},
2672  // Unguarded block split.
2673  {DominatorTree::Delete, PredUnguardedBlock, BB},
2674  {DominatorTree::Insert, PredUnguardedBlock, UnguardedBlock},
2675  {DominatorTree::Insert, UnguardedBlock, BB}});
2676  // Some instructions before the guard may still have uses. For them, we need
2677  // to create Phi nodes merging their copies in both guarded and unguarded
2678  // branches. Those instructions that have no uses can be just removed.
2680  for (auto BI = BB->begin(); &*BI != AfterGuard; ++BI)
2681  if (!isa<PHINode>(&*BI))
2682  ToRemove.push_back(&*BI);
2683 
2684  Instruction *InsertionPoint = &*BB->getFirstInsertionPt();
2685  assert(InsertionPoint && "Empty block?");
2686  // Substitute with Phis & remove.
2687  for (auto *Inst : reverse(ToRemove)) {
2688  if (!Inst->use_empty()) {
2689  PHINode *NewPN = PHINode::Create(Inst->getType(), 2);
2690  NewPN->addIncoming(UnguardedMapping[Inst], UnguardedBlock);
2691  NewPN->addIncoming(GuardedMapping[Inst], GuardedBlock);
2692  NewPN->insertBefore(InsertionPoint);
2693  Inst->replaceAllUsesWith(NewPN);
2694  }
2695  Inst->eraseFromParent();
2696  }
2697  return true;
2698 }
Legacy wrapper pass to provide the GlobalsAAResult object.
bool ThreadEdge(BasicBlock *BB, const SmallVectorImpl< BasicBlock *> &PredBBs, BasicBlock *SuccBB)
ThreadEdge - We have decided that it is safe and profitable to factor the blocks in PredBBs to one pr...
uint64_t CallInst * C
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks &#39;this&#39; from the containing basic block and deletes it.
Definition: Instruction.cpp:68
IntegerType * getType() const
getType - Specialize the getType() method to always return an IntegerType, which reduces the amount o...
Definition: Constants.h:172
A parsed version of the target data layout string in and methods for querying it. ...
Definition: DataLayout.h:111
static ConstantInt * getFalse(LLVMContext &Context)
Definition: Constants.cpp:584
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
Definition: PatternMatch.h:72
This class is the base class for the comparison instructions.
Definition: InstrTypes.h:875
static bool runImpl(Function &F, TargetLibraryInfo &TLI, DominatorTree &DT)
This is the entry point for all transforms.
iterator_range< use_iterator > uses()
Definition: Value.h:354
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
void removePredecessor(BasicBlock *Pred, bool DontDeleteUselessPHIs=false)
Notify the BasicBlock that the predecessor Pred is no longer able to reach it.
Definition: BasicBlock.cpp:295
static IntegerType * getInt1Ty(LLVMContext &C)
Definition: Type.cpp:173
Helper class for SSA formation on a set of values defined in multiple blocks.
Definition: SSAUpdater.h:39
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
BranchProbability getCompl() const
NodeTy * getNextNode()
Get the next node, or nullptr for the list tail.
Definition: ilist_node.h:289
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:687
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
bool isAtomic() const
Return true if this instruction has an AtomicOrdering of unordered or higher.
Wrapper around LazyValueInfo.
This is the interface for a simple mod/ref and alias analysis over globals.
void Initialize(Type *Ty, StringRef Name)
Reset this object to get ready for a new set of SSA updates with type &#39;Ty&#39;.
Definition: SSAUpdater.cpp:54
BasicBlock * getSuccessor(unsigned idx) const
Return the specified successor.
void initializeJumpThreadingPass(PassRegistry &)
void AddAvailableValue(BasicBlock *BB, Value *V)
Indicate that a rewritten value is available in the specified block with the specified value...
Definition: SSAUpdater.cpp:67
BasicBlock * DuplicateInstructionsInSplitBetween(BasicBlock *BB, BasicBlock *PredBB, Instruction *StopAt, ValueToValueMapTy &ValueMapping, DominatorTree *DT=nullptr)
Split edge between BB and PredBB and duplicate all non-Phi instructions from BB between its beginning...
This class represents a function call, abstracting a target machine&#39;s calling convention.
cl::opt< unsigned > DefMaxInstsToScan
The default number of maximum instructions to scan in the block, used by FindAvailableLoadedValue().
This file contains the declarations for metadata subclasses.
const Value * getTrueValue() const
uint64_t getFrequency() const
Returns the frequency as a fixpoint number scaled by the entry frequency.
AtomicOrdering getOrdering() const
Returns the ordering constraint of this load instruction.
Definition: Instructions.h:237
LLVMContext & getContext() const
All values hold a context through their type.
Definition: Value.cpp:714
static CastInst * CreateBitOrPointerCast(Value *S, Type *Ty, const Twine &Name="", Instruction *InsertBefore=nullptr)
Create a BitCast, a PtrToInt, or an IntToPTr cast instruction.
void deleteValue()
Delete a pointer to a generic Value.
Definition: Value.cpp:99
static cl::opt< unsigned > ImplicationSearchThreshold("jump-threading-implication-search-threshold", cl::desc("The number of predecessors to search for a stronger " "condition to use to thread over a weaker condition"), cl::init(3), cl::Hidden)
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:921
Value * FindAvailablePtrLoadStore(Value *Ptr, Type *AccessTy, bool AtLeastAtomic, BasicBlock *ScanBB, BasicBlock::iterator &ScanFrom, unsigned MaxInstsToScan, AliasAnalysis *AA, bool *IsLoad, unsigned *NumScanedInst)
Scan backwards to see if we have the value of the given pointer available locally within a small numb...
Definition: Loads.cpp:336
static BasicBlock * FindMostPopularDest(BasicBlock *BB, const SmallVectorImpl< std::pair< BasicBlock *, BasicBlock *>> &PredToDestList)
FindMostPopularDest - The specified list contains multiple possible threadable destinations.
BasicBlock * getSuccessor(unsigned i) const
STATISTIC(NumFunctions, "Total number of functions")
bool SimplifyInstructionsInBlock(BasicBlock *BB, const TargetLibraryInfo *TLI=nullptr)
Scan the specified basic block and try to simplify any instructions in it and recursively delete dead...
Definition: Local.cpp:577
Metadata node.
Definition: Metadata.h:862
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:225
F(f)
An instruction for reading from memory.
Definition: Instructions.h:168
static Constant * getCompare(unsigned short pred, Constant *C1, Constant *C2, bool OnlyIfReduced=false)
Return an ICmp or FCmp comparison operator constant expression.
Definition: Constants.cpp:1903
Value * getCondition() const
bool isVectorTy() const
True if this is an instance of VectorType.
Definition: Type.h:230
This defines the Use class.
const Value * DoPHITranslation(const BasicBlock *CurBB, const BasicBlock *PredBB) const
Translate PHI node to its predecessor from the given basic block.
Definition: Value.cpp:706
LLVMContext & getContext() const
Get the context in which this basic block lives.
Definition: BasicBlock.cpp:33
bool isReachableFromEntry(const Use &U) const
Provide an overload for a Use.
Definition: Dominators.cpp:295
FunctionPass * createJumpThreadingPass(int Threshold=-1)
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:264
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: DenseMap.h:191
The address of a basic block.
Definition: Constants.h:836
bool match(Val *V, const Pattern &P)
Definition: PatternMatch.h:49
AnalysisUsage & addRequired()
const Module * getModule() const
Return the module owning the function this basic block belongs to, or nullptr if the function does no...
Definition: BasicBlock.cpp:134
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:51
void MergeBasicBlockIntoOnlyPred(BasicBlock *BB, DominatorTree *DT=nullptr, DeferredDominance *DDT=nullptr)
BB is a block with one predecessor and its predecessor is known to have one successor (BB!)...
Definition: Local.cpp:660
StringRef getName(ID id)
Return the LLVM name for an intrinsic, such as "llvm.ppc.altivec.lvx".
Definition: Function.cpp:613
This class represents the LLVM &#39;select&#39; instruction.
const DataLayout & getDataLayout() const
Get the data layout for the module&#39;s target platform.
Definition: Module.cpp:361
This is the base class for all instructions that perform data casts.
Definition: InstrTypes.h:592
static cl::opt< unsigned > BBDuplicateThreshold("jump-threading-threshold", cl::desc("Max block size to duplicate for jump threading"), cl::init(6), cl::Hidden)
&#39;undef&#39; values are things that do not have specified contents.
Definition: Constants.h:1275
Value * FindAvailableLoadedValue(LoadInst *Load, BasicBlock *ScanBB, BasicBlock::iterator &ScanFrom, unsigned MaxInstsToScan=DefMaxInstsToScan, AliasAnalysis *AA=nullptr, bool *IsLoadCSE=nullptr, unsigned *NumScanedInst=nullptr)
Scan backwards to see if we have the value of the given load available locally within a small number ...
Definition: Loads.cpp:321
unsigned getNumSuccessors() const
A Use represents the edge between a Value definition and its users.
Definition: Use.h:56
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:42
jump threading
bool isIntegerTy() const
True if this is an instance of IntegerType.
Definition: Type.h:197
void setName(const Twine &Name)
Change the name of the value.
Definition: Value.cpp:295
bool contains(const APInt &Val) const
Return true if the specified value is in the set.
bool TryToUnfoldSelectInCurrBB(BasicBlock *BB)
TryToUnfoldSelectInCurrBB - Look for PHI/Select or PHI/CMP/Select in the same BB in the form bb: p = ...
BinaryOp_match< LHS, RHS, Instruction::Add > m_Add(const LHS &L, const RHS &R)
Definition: PatternMatch.h:639
void assign(size_type NumElts, const T &Elt)
Definition: SmallVector.h:418
auto reverse(ContainerTy &&C, typename std::enable_if< has_rbegin< ContainerTy >::value >::type *=nullptr) -> decltype(make_range(C.rbegin(), C.rend()))
Definition: STLExtras.h:250
bool isOne() const
This is just a convenience method to make client code smaller for a common case.
Definition: Constants.h:201
static Constant * get(unsigned Opcode, Constant *C1, Constant *C2, unsigned Flags=0, Type *OnlyIfReducedTy=nullptr)
get - Return a binary or shift operator constant expression, folding if possible. ...
Definition: Constants.cpp:1783
Value * SimplifyCmpInst(unsigned Predicate, Value *LHS, Value *RHS, const SimplifyQuery &Q)
Given operands for a CmpInst, fold the result or return null.
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:245
static void normalizeProbabilities(ProbabilityIter Begin, ProbabilityIter End)
MDNode * getMetadata(unsigned KindID) const
Get the metadata of given kind attached to this Instruction.
Definition: Instruction.h:200
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory)...
Definition: APInt.h:33
class_match< ConstantInt > m_ConstantInt()
Match an arbitrary ConstantInt and ignore it.
Definition: PatternMatch.h:83
const APInt & getValue() const
Return the constant as an APInt value reference.
Definition: Constants.h:138
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
Definition: Instruction.h:126
auto lower_bound(R &&Range, ForwardIt I) -> decltype(adl_begin(Range))
Provide wrappers to std::lower_bound which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1017
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:439
void SplitLandingPadPredecessors(BasicBlock *OrigBB, ArrayRef< BasicBlock *> Preds, const char *Suffix, const char *Suffix2, SmallVectorImpl< BasicBlock *> &NewBBs, DominatorTree *DT=nullptr, LoopInfo *LI=nullptr, bool PreserveLCSSA=false)
This method transforms the landing pad, OrigBB, by introducing two new basic blocks into the function...
static bool ProcessBlock(BasicBlock &BB, DominatorTree &DT, LoopInfo &LI, AAResults &AA)
Definition: Sink.cpp:199
bool runImpl(Function &F, TargetLibraryInfo *TLI_, LazyValueInfo *LVI_, AliasAnalysis *AA_, DeferredDominance *DDT_, bool HasProfileData_, std::unique_ptr< BlockFrequencyInfo > BFI_, std::unique_ptr< BranchProbabilityInfo > BPI_)
void takeName(Value *V)
Transfer the name from V to this value.
Definition: Value.cpp:301
static Constant * getKnownConstant(Value *Val, ConstantPreference Preference)
getKnownConstant - Helper method to determine if we can thread over a terminator with the given value...
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:142
Value * getOperand(unsigned i) const
Definition: User.h:170
void removeDeadConstantUsers() const
If there are any dead constant users dangling off of this constant, remove them.
Definition: Constants.cpp:536
StringRef getString() const
Definition: Metadata.cpp:464
const BasicBlock & getEntryBlock() const
Definition: Function.h:626
void getAAMetadata(AAMDNodes &N, bool Merge=false) const
Fills the AAMDNodes structure with AA metadata from this instruction.
BlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate IR basic block frequen...
static bool runOnFunction(Function &F, bool PostInlining)
#define P(N)
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:410
bool isGuaranteedToTransferExecutionToSuccessor(const Instruction *I)
Return true if this function can prove that the instruction I will always transfer execution to one o...
void array_pod_sort(IteratorTy Start, IteratorTy End)
array_pod_sort - This sorts an array with the specified start and end extent.
Definition: STLExtras.h:839
const Instruction * getFirstNonPHI() const
Returns a pointer to the first instruction in this block that is not a PHINode instruction.
Definition: BasicBlock.cpp:189
Subclasses of this class are all able to terminate a basic block.
Definition: InstrTypes.h:55
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:153
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:218
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
Definition: Instruction.h:287
void setSuccessor(unsigned idx, BasicBlock *B)
Update the specified successor to point at the provided block.
const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
Definition: BasicBlock.cpp:235
void insertBefore(Instruction *InsertPos)
Insert an unlinked instruction into a basic block immediately before the specified instruction...
Definition: Instruction.cpp:74
LLVM Basic Block Representation.
Definition: BasicBlock.h:59
The instances of the Type class are immutable: once they are created, they are never changed...
Definition: Type.h:46
Conditional or Unconditional Branch instruction.
static BlockAddress * get(Function *F, BasicBlock *BB)
Return a BlockAddress for the specified function and basic block.
Definition: Constants.cpp:1411
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
This is an important base class in LLVM.
Definition: Constant.h:42
LLVM_ATTRIBUTE_ALWAYS_INLINE iterator begin()
Definition: SmallVector.h:124
static bool isOpDefinedInBlock(Value *Op, BasicBlock *BB)
Return true if Op is an instruction defined in the given block.
Value * getIncomingValueForBlock(const BasicBlock *BB) const
This file contains the declarations for the subclasses of Constant, which represent the different fla...
const Instruction & front() const
Definition: BasicBlock.h:276
Indirect Branch Instruction.
A manager for alias analyses.
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:371
bool mayHaveSideEffects() const
Return true if the instruction may have side effects.
Definition: Instruction.h:541
Constant * ConstantFoldInstruction(Instruction *I, const DataLayout &DL, const TargetLibraryInfo *TLI=nullptr)
ConstantFoldInstruction - Try to constant fold the specified instruction.
Interval::pred_iterator pred_begin(Interval *I)
pred_begin/pred_end - define methods so that Intervals may be used just like BasicBlocks can with the...
Definition: Interval.h:113
bool isUnordered() const
Definition: Instructions.h:268
Represent the analysis usage information of a pass.
This instruction compares its operands according to the predicate given to the constructor.
Analysis pass providing a never-invalidated alias analysis result.
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:885
jump Jump Threading
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:285
ConstantRange add(const ConstantRange &Other) const
Return a new range representing the possible values resulting from an addition of a value in this ran...
Interval::pred_iterator pred_end(Interval *I)
Definition: Interval.h:116
BasicBlock * SplitBlockPredecessors(BasicBlock *BB, ArrayRef< BasicBlock *> Preds, const char *Suffix, DominatorTree *DT=nullptr, LoopInfo *LI=nullptr, bool PreserveLCSSA=false)
This method introduces at least one new basic block into the function and moves some of the predecess...
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
Definition: BasicBlock.h:101
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:382
bool pred_empty(const BasicBlock *BB)
Definition: CFG.h:107
static Constant * getNot(Constant *C)
Definition: Constants.cpp:2180
void FindLoopHeaders(Function &F)
FindLoopHeaders - We do not want jump threading to turn proper loop structures into irreducible loops...
bool ConstantFoldTerminator(BasicBlock *BB, bool DeleteDeadConditions=false, const TargetLibraryInfo *TLI=nullptr, DeferredDominance *DDT=nullptr)
If a terminator instruction is predicated on a constant value, convert it into an unconditional branc...
Definition: Local.cpp:103
const Value * getCondition() const
static void updatePredecessorProfileMetadata(PHINode *PN, BasicBlock *BB)
static UndefValue * get(Type *T)
Static factory methods - Return an &#39;undef&#39; object of the specified type.
Definition: Constants.cpp:1392
const Value * stripPointerCasts() const
Strip off pointer casts, all-zero GEPs, and aliases.
Definition: Value.cpp:539
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:159
size_t size() const
Definition: SmallVector.h:53
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
void setMetadata(unsigned KindID, MDNode *Node)
Set the metadata of the specified kind to the specified node.
Definition: Metadata.cpp:1226
static unsigned GetBestDestForJumpOnUndef(BasicBlock *BB)
GetBestDestForBranchOnUndef - If we determine that the specified block ends in an undefined jump...
Tristate
This is used to return true/false/dunno results.
Definition: LazyValueInfo.h:63
bool TryToSimplifyUncondBranchFromEmptyBlock(BasicBlock *BB, DeferredDominance *DDT=nullptr)
BB is known to contain an unconditional branch, and contains no instructions other than PHI nodes...
Definition: Local.cpp:947
bool ProcessBranchOnPHI(PHINode *PN)
ProcessBranchOnPHI - We have an otherwise unthreadable conditional branch on a PHI node in the curren...
bool ComputeValueKnownInPredecessors(Value *V, BasicBlock *BB, jumpthreading::PredValueInfo &Result, jumpthreading::ConstantPreference Preference, Instruction *CxtI=nullptr)
ComputeValueKnownInPredecessors - Given a basic block BB and a value V, see if we can infer that the ...
size_type size() const
Definition: SmallPtrSet.h:93
bool isLandingPad() const
Return true if this basic block is a landing pad.
Definition: BasicBlock.cpp:461
bool hasAddressTaken() const
Returns true if there are any uses of this basic block other than direct branches, switches, etc.
Definition: BasicBlock.h:387
const InstListType & getInstList() const
Return the underlying instruction list container.
Definition: BasicBlock.h:329
static cl::opt< bool > PrintLVIAfterJumpThreading("print-lvi-after-jump-threading", cl::desc("Print the LazyValueInfo cache after JumpThreading"), cl::init(false), cl::Hidden)
Iterator for intrusive lists based on ilist_node.
unsigned getNumOperands() const
Definition: User.h:192
void moveAfter(BasicBlock *MovePos)
Unlink this basic block from its current function and insert it right after MovePos in the function M...
Definition: BasicBlock.cpp:128
static ConstantRange makeExactICmpRegion(CmpInst::Predicate Pred, const APInt &Other)
Produce the exact range such that all values in the returned range satisfy the given predicate with a...
See the file comment.
Definition: ValueMap.h:86
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
Definition: SmallPtrSet.h:418
This is the shared class of boolean and integer constants.
Definition: Constants.h:84
iterator end()
Definition: BasicBlock.h:266
bool isExceptional() const
Definition: InstrTypes.h:85
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:841
Module.h This file contains the declarations for the Module class.
Provides information about what library functions are available for the current target.
This pass performs &#39;jump threading&#39;, which looks at blocks that have multiple predecessors and multip...
Definition: JumpThreading.h:77
This class represents a range of values.
Definition: ConstantRange.h:47
static BranchProbability getBranchProbability(uint64_t Numerator, uint64_t Denominator)
TerminatorInst * SplitBlockAndInsertIfThen(Value *Cond, Instruction *SplitBefore, bool Unreachable, MDNode *BranchWeights=nullptr, DominatorTree *DT=nullptr, LoopInfo *LI=nullptr)
Split the containing block at the specified instruction - everything before SplitBefore stays in the ...
A collection of metadata nodes that might be associated with a memory access used by the alias-analys...
Definition: Metadata.h:642
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:376
static Constant * get(Type *Ty, uint64_t V, bool isSigned=false)
If Ty is a vector type, return a Constant with a splat of the given value.
Definition: Constants.cpp:621
bool SimplifyPartiallyRedundantLoad(LoadInst *LI)
SimplifyPartiallyRedundantLoad - If LoadI is an obviously partially redundant load instruction...
static BranchInst * Create(BasicBlock *IfTrue, Instruction *InsertBefore=nullptr)
bool isConditional() const
static PHINode * Create(Type *Ty, unsigned NumReservedValues, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
Constructors - NumReservedValues is a hint for the number of incoming edges that this phi node will h...
pred_range predecessors(BasicBlock *BB)
Definition: CFG.h:113
unsigned getNumIncomingValues() const
Return the number of incoming edges.
static ConstantInt * getTrue(LLVMContext &Context)
Definition: Constants.cpp:577
void erase_if(Container &C, UnaryPredicate P)
Provide a container algorithm similar to C++ Library Fundamentals v2&#39;s erase_if which is equivalent t...
Definition: STLExtras.h:1038
void setOperand(unsigned i, Value *Val)
Definition: User.h:175
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:133
static unsigned getJumpThreadDuplicationCost(BasicBlock *BB, Instruction *StopAt, unsigned Threshold)
Return the cost of duplicating a piece of this block from first non-phi and before StopAt instruction...
Function * getFunction(StringRef Name) const
Look up the specified function in the module symbol table.
Definition: Module.cpp:172
const Module * getModule() const
Return the module owning the function this instruction belongs to or nullptr it the function does not...
Definition: Instruction.cpp:56
void push_back(pointer val)
Definition: ilist.h:313
Class to defer updates to a DominatorTree.
Definition: Dominators.h:307
static Constant * getCast(unsigned ops, Constant *C, Type *Ty, bool OnlyIfReduced=false)
Convenience function for getting a Cast operation.
Definition: Constants.cpp:1507
const Value * getFalseValue() const
void removeFromParent()
This method unlinks &#39;this&#39; from the containing basic block, but does not delete it.
Definition: Instruction.cpp:64
Predicate getPredicate() const
Return the predicate for this instruction.
Definition: InstrTypes.h:959
static bool isZero(Value *V, const DataLayout &DL, DominatorTree *DT, AssumptionCache *AC)
Definition: Lint.cpp:546
LLVM_ATTRIBUTE_ALWAYS_INLINE iterator end()
Definition: SmallVector.h:128
Analysis providing branch probability information.
iterator insert(iterator where, pointer New)
Definition: ilist.h:228
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
Definition: Instruction.h:290
unsigned getAlignment() const
Return the alignment of the access that is being performed.
Definition: Instructions.h:230
void emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:647
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:56
iterator begin()
Definition: DenseMap.h:70
bool ProcessBranchOnXOR(BinaryOperator *BO)
ProcessBranchOnXOR - We have an otherwise unthreadable conditional branch on a xor instruction in the...
StringRef getName() const
Return a constant reference to the value&#39;s name.
Definition: Value.cpp:224
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:108
SyncScope::ID getSyncScopeID() const
Returns the synchronization scope ID of this load instruction.
Definition: Instructions.h:249
bool ProcessImpliedCondition(BasicBlock *BB)
unsigned pred_size(const BasicBlock *BB)
Definition: CFG.h:110
#define I(x, y, z)
Definition: MD5.cpp:58
bool isZero() const
This is just a convenience method to make client code smaller for a common code.
Definition: Constants.h:193
LLVM_NODISCARD std::enable_if<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type >::type dyn_cast(const Y &Val)
Definition: Casting.h:323
static void ReplaceFoldableUses(Instruction *Cond, Value *ToVal)
void preserve()
Mark an analysis as preserved.
Definition: PassManager.h:174
iterator_range< const_phi_iterator > phis() const
Returns a range that iterates over the phis in the basic block.
Definition: BasicBlock.h:320
void combineMetadataForCSE(Instruction *K, const Instruction *J)
Combine the metadata of two instructions so that K can replace J.
Definition: Local.cpp:2320
bool isUnconditional() const
static void AddPHINodeEntriesForMappedBlock(BasicBlock *PHIBB, BasicBlock *OldPred, BasicBlock *NewPred, DenseMap< Instruction *, Value *> &ValueMap)
AddPHINodeEntriesForMappedBlock - We&#39;re adding &#39;NewPred&#39; as a new predecessor to the PHIBB block...
ValueT lookup(const_arg_type_t< KeyT > Val) const
lookup - Return the entry for the specified key, or a default constructed value if no such entry exis...
Definition: DenseMap.h:181
bool ProcessThreadableEdges(Value *Cond, BasicBlock *BB, jumpthreading::ConstantPreference Preference, Instruction *CxtI=nullptr)
Optional< bool > isImpliedCondition(const Value *LHS, const Value *RHS, const DataLayout &DL, bool LHSIsTrue=true, unsigned Depth=0)
Return true if RHS is known to be implied true by LHS.
void FindFunctionBackedges(const Function &F, SmallVectorImpl< std::pair< const BasicBlock *, const BasicBlock *> > &Result)
Analyze the specified function to find all of the loop backedges in the function and return them...
Definition: CFG.cpp:27
Analysis pass providing the TargetLibraryInfo.
static int const Threshold
TODO: Write a new FunctionPass AliasAnalysis so that it can keep a cache.
Multiway switch.
Helper struct that represents how a value is mapped through different register banks.
This pass computes, caches, and vends lazy value constraint information.
Definition: LazyValueInfo.h:32
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
unsigned getNumSuccessors() const
Return the number of successors that this terminator has.
See the comments on JumpThreadingPass.
void DeleteDeadBlock(BasicBlock *BB, DeferredDominance *DDT=nullptr)
Delete the specified block, which must have no predecessors.
Value * getArgOperand(unsigned i) const
getArgOperand/setArgOperand - Return/set the i-th call argument.
bool isSafeToSpeculativelyExecute(const Value *V, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr)
Return true if the instruction does not have any effects besides calculating the result and does not ...
bool isEHPad() const
Return true if this basic block is an exception handling block.
Definition: BasicBlock.h:394
unsigned getPrimitiveSizeInBits() const LLVM_READONLY
Return the basic size of this type if it is a primitive type.
Definition: Type.cpp:115
bool ThreadGuard(BasicBlock *BB, IntrinsicInst *Guard, BranchInst *BI)
Try to propagate the guard from BB which is the lower block of a diamond to one of its branches...
bool ProcessGuards(BasicBlock *BB)
Try to propagate a guard from the current BB into one of its predecessors in case if another branch o...
Module * getParent()
Get the module that this global value is contained inside of...
Definition: GlobalValue.h:565
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:346
LLVM Value Representation.
Definition: Value.h:73
succ_range successors(BasicBlock *BB)
Definition: CFG.h:149
constexpr char Size[]
Key for Kernel::Arg::Metadata::mSize.
bool ProcessBlock(BasicBlock *BB)
ProcessBlock - If there are any predecessors whose control can be threaded through to a successor...
static const Function * getParent(const Value *V)
BasicBlock * SplitEdge(BasicBlock *From, BasicBlock *To, DominatorTree *DT=nullptr, LoopInfo *LI=nullptr)
Split the edge connecting specified block.
bool hasOneUse() const
Return true if there is exactly one user of this value.
Definition: Value.h:412
A single uniqued string.
Definition: Metadata.h:602
A container for analyses that lazily runs them and caches their results.
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:254
A wrapper pass to provide the legacy pass manager access to a suitably prepared AAResults object...
const TerminatorInst * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
Definition: BasicBlock.cpp:138
This header defines various interfaces for pass management in LLVM.
INITIALIZE_PASS_BEGIN(JumpThreading, "jump-threading", "Jump Threading", false, false) INITIALIZE_PASS_END(JumpThreading
#define LLVM_DEBUG(X)
Definition: Debug.h:119
bool extractProfMetadata(uint64_t &TrueVal, uint64_t &FalseVal) const
Retrieve the raw weight values of a conditional branch or select.
Definition: Metadata.cpp:1315
op_range incoming_values()
ConstantRange inverse() const
Return a new range that is the logical not of the current set.
void RewriteUse(Use &U)
Rewrite a use of the symbolic value.
Definition: SSAUpdater.cpp:185
bool DuplicateCondBranchOnPHIIntoPred(BasicBlock *BB, const SmallVectorImpl< BasicBlock *> &PredBBs)
DuplicateCondBranchOnPHIIntoPred - PredBB contains an unconditional branch to BB which contains an i1...
static bool hasAddressTakenAndUsed(BasicBlock *BB)
Value * SimplifyInstruction(Instruction *I, const SimplifyQuery &Q, OptimizationRemarkEmitter *ORE=nullptr)
See if we can compute a simplified version of this instruction.
bool hasProfileData() const
Return true if the function is annotated with profile data.
Definition: Function.h:294
uint32_t getNumerator() const
bool use_empty() const
Definition: Value.h:322
unsigned replaceNonLocalUsesWith(Instruction *From, Value *To)
Definition: Local.cpp:2351
Analysis to compute lazy value information.
A wrapper class for inspecting calls to intrinsic functions.
Definition: IntrinsicInst.h:44
const BasicBlock * getParent() const
Definition: Instruction.h:67
bool TryToUnfoldSelect(CmpInst *CondCmp, BasicBlock *BB)
TryToUnfoldSelect - Look for blocks of the form bb1: a = select br bb2.
void resize(size_type N)
Definition: SmallVector.h:346
bool is_contained(R &&Range, const E &Element)
Wrapper function around std::find to detect if an element exists in a container.
Definition: STLExtras.h:980