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