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