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