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