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