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