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