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