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