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{DominatorTree(F)};
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  using VT = decltype(DestPopularity)::value_type;
1563  auto MostPopular = std::max_element(
1564  DestPopularity.begin(), DestPopularity.end(),
1565  [](const VT &L, const VT &R) { return L.second < R.second; });
1566 
1567  // Okay, we have finally picked the most popular destination.
1568  return MostPopular->first;
1569 }
1570 
1571 // Try to evaluate the value of V when the control flows from PredPredBB to
1572 // BB->getSinglePredecessor() and then on to BB.
1574  BasicBlock *PredPredBB,
1575  Value *V) {
1576  BasicBlock *PredBB = BB->getSinglePredecessor();
1577  assert(PredBB && "Expected a single predecessor");
1578 
1579  if (Constant *Cst = dyn_cast<Constant>(V)) {
1580  return Cst;
1581  }
1582 
1583  // Consult LVI if V is not an instruction in BB or PredBB.
1584  Instruction *I = dyn_cast<Instruction>(V);
1585  if (!I || (I->getParent() != BB && I->getParent() != PredBB)) {
1586  return LVI->getConstantOnEdge(V, PredPredBB, PredBB, nullptr);
1587  }
1588 
1589  // Look into a PHI argument.
1590  if (PHINode *PHI = dyn_cast<PHINode>(V)) {
1591  if (PHI->getParent() == PredBB)
1592  return dyn_cast<Constant>(PHI->getIncomingValueForBlock(PredPredBB));
1593  return nullptr;
1594  }
1595 
1596  // If we have a CmpInst, try to fold it for each incoming edge into PredBB.
1597  if (CmpInst *CondCmp = dyn_cast<CmpInst>(V)) {
1598  if (CondCmp->getParent() == BB) {
1599  Constant *Op0 =
1600  evaluateOnPredecessorEdge(BB, PredPredBB, CondCmp->getOperand(0));
1601  Constant *Op1 =
1602  evaluateOnPredecessorEdge(BB, PredPredBB, CondCmp->getOperand(1));
1603  if (Op0 && Op1) {
1604  return ConstantExpr::getCompare(CondCmp->getPredicate(), Op0, Op1);
1605  }
1606  }
1607  return nullptr;
1608  }
1609 
1610  return nullptr;
1611 }
1612 
1615  Instruction *CxtI) {
1616  // If threading this would thread across a loop header, don't even try to
1617  // thread the edge.
1618  if (LoopHeaders.count(BB))
1619  return false;
1620 
1621  PredValueInfoTy PredValues;
1622  if (!computeValueKnownInPredecessors(Cond, BB, PredValues, Preference,
1623  CxtI)) {
1624  // We don't have known values in predecessors. See if we can thread through
1625  // BB and its sole predecessor.
1626  return maybethreadThroughTwoBasicBlocks(BB, Cond);
1627  }
1628 
1629  assert(!PredValues.empty() &&
1630  "computeValueKnownInPredecessors returned true with no values");
1631 
1632  LLVM_DEBUG(dbgs() << "IN BB: " << *BB;
1633  for (const auto &PredValue : PredValues) {
1634  dbgs() << " BB '" << BB->getName()
1635  << "': FOUND condition = " << *PredValue.first
1636  << " for pred '" << PredValue.second->getName() << "'.\n";
1637  });
1638 
1639  // Decide what we want to thread through. Convert our list of known values to
1640  // a list of known destinations for each pred. This also discards duplicate
1641  // predecessors and keeps track of the undefined inputs (which are represented
1642  // as a null dest in the PredToDestList).
1643  SmallPtrSet<BasicBlock*, 16> SeenPreds;
1645 
1646  BasicBlock *OnlyDest = nullptr;
1647  BasicBlock *MultipleDestSentinel = (BasicBlock*)(intptr_t)~0ULL;
1648  Constant *OnlyVal = nullptr;
1649  Constant *MultipleVal = (Constant *)(intptr_t)~0ULL;
1650 
1651  for (const auto &PredValue : PredValues) {
1652  BasicBlock *Pred = PredValue.second;
1653  if (!SeenPreds.insert(Pred).second)
1654  continue; // Duplicate predecessor entry.
1655 
1656  Constant *Val = PredValue.first;
1657 
1658  BasicBlock *DestBB;
1659  if (isa<UndefValue>(Val))
1660  DestBB = nullptr;
1661  else if (BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator())) {
1662  assert(isa<ConstantInt>(Val) && "Expecting a constant integer");
1663  DestBB = BI->getSuccessor(cast<ConstantInt>(Val)->isZero());
1664  } else if (SwitchInst *SI = dyn_cast<SwitchInst>(BB->getTerminator())) {
1665  assert(isa<ConstantInt>(Val) && "Expecting a constant integer");
1666  DestBB = SI->findCaseValue(cast<ConstantInt>(Val))->getCaseSuccessor();
1667  } else {
1668  assert(isa<IndirectBrInst>(BB->getTerminator())
1669  && "Unexpected terminator");
1670  assert(isa<BlockAddress>(Val) && "Expecting a constant blockaddress");
1671  DestBB = cast<BlockAddress>(Val)->getBasicBlock();
1672  }
1673 
1674  // If we have exactly one destination, remember it for efficiency below.
1675  if (PredToDestList.empty()) {
1676  OnlyDest = DestBB;
1677  OnlyVal = Val;
1678  } else {
1679  if (OnlyDest != DestBB)
1680  OnlyDest = MultipleDestSentinel;
1681  // It possible we have same destination, but different value, e.g. default
1682  // case in switchinst.
1683  if (Val != OnlyVal)
1684  OnlyVal = MultipleVal;
1685  }
1686 
1687  // If the predecessor ends with an indirect goto, we can't change its
1688  // destination. Same for CallBr.
1689  if (isa<IndirectBrInst>(Pred->getTerminator()) ||
1690  isa<CallBrInst>(Pred->getTerminator()))
1691  continue;
1692 
1693  PredToDestList.emplace_back(Pred, DestBB);
1694  }
1695 
1696  // If all edges were unthreadable, we fail.
1697  if (PredToDestList.empty())
1698  return false;
1699 
1700  // If all the predecessors go to a single known successor, we want to fold,
1701  // not thread. By doing so, we do not need to duplicate the current block and
1702  // also miss potential opportunities in case we dont/cant duplicate.
1703  if (OnlyDest && OnlyDest != MultipleDestSentinel) {
1704  if (BB->hasNPredecessors(PredToDestList.size())) {
1705  bool SeenFirstBranchToOnlyDest = false;
1706  std::vector <DominatorTree::UpdateType> Updates;
1707  Updates.reserve(BB->getTerminator()->getNumSuccessors() - 1);
1708  for (BasicBlock *SuccBB : successors(BB)) {
1709  if (SuccBB == OnlyDest && !SeenFirstBranchToOnlyDest) {
1710  SeenFirstBranchToOnlyDest = true; // Don't modify the first branch.
1711  } else {
1712  SuccBB->removePredecessor(BB, true); // This is unreachable successor.
1713  Updates.push_back({DominatorTree::Delete, BB, SuccBB});
1714  }
1715  }
1716 
1717  // Finally update the terminator.
1718  Instruction *Term = BB->getTerminator();
1719  BranchInst::Create(OnlyDest, Term);
1720  ++NumFolds;
1721  Term->eraseFromParent();
1722  DTU->applyUpdatesPermissive(Updates);
1723  if (HasProfileData)
1724  BPI->eraseBlock(BB);
1725 
1726  // If the condition is now dead due to the removal of the old terminator,
1727  // erase it.
1728  if (auto *CondInst = dyn_cast<Instruction>(Cond)) {
1729  if (CondInst->use_empty() && !CondInst->mayHaveSideEffects())
1730  CondInst->eraseFromParent();
1731  // We can safely replace *some* uses of the CondInst if it has
1732  // exactly one value as returned by LVI. RAUW is incorrect in the
1733  // presence of guards and assumes, that have the `Cond` as the use. This
1734  // is because we use the guards/assume to reason about the `Cond` value
1735  // at the end of block, but RAUW unconditionally replaces all uses
1736  // including the guards/assumes themselves and the uses before the
1737  // guard/assume.
1738  else if (OnlyVal && OnlyVal != MultipleVal)
1739  replaceFoldableUses(CondInst, OnlyVal, BB);
1740  }
1741  return true;
1742  }
1743  }
1744 
1745  // Determine which is the most common successor. If we have many inputs and
1746  // this block is a switch, we want to start by threading the batch that goes
1747  // to the most popular destination first. If we only know about one
1748  // threadable destination (the common case) we can avoid this.
1749  BasicBlock *MostPopularDest = OnlyDest;
1750 
1751  if (MostPopularDest == MultipleDestSentinel) {
1752  // Remove any loop headers from the Dest list, threadEdge conservatively
1753  // won't process them, but we might have other destination that are eligible
1754  // and we still want to process.
1755  erase_if(PredToDestList,
1756  [&](const std::pair<BasicBlock *, BasicBlock *> &PredToDest) {
1757  return LoopHeaders.contains(PredToDest.second);
1758  });
1759 
1760  if (PredToDestList.empty())
1761  return false;
1762 
1763  MostPopularDest = findMostPopularDest(BB, PredToDestList);
1764  }
1765 
1766  // Now that we know what the most popular destination is, factor all
1767  // predecessors that will jump to it into a single predecessor.
1768  SmallVector<BasicBlock*, 16> PredsToFactor;
1769  for (const auto &PredToDest : PredToDestList)
1770  if (PredToDest.second == MostPopularDest) {
1771  BasicBlock *Pred = PredToDest.first;
1772 
1773  // This predecessor may be a switch or something else that has multiple
1774  // edges to the block. Factor each of these edges by listing them
1775  // according to # occurrences in PredsToFactor.
1776  for (BasicBlock *Succ : successors(Pred))
1777  if (Succ == BB)
1778  PredsToFactor.push_back(Pred);
1779  }
1780 
1781  // If the threadable edges are branching on an undefined value, we get to pick
1782  // the destination that these predecessors should get to.
1783  if (!MostPopularDest)
1784  MostPopularDest = BB->getTerminator()->
1785  getSuccessor(getBestDestForJumpOnUndef(BB));
1786 
1787  // Ok, try to thread it!
1788  return tryThreadEdge(BB, PredsToFactor, MostPopularDest);
1789 }
1790 
1791 /// processBranchOnPHI - We have an otherwise unthreadable conditional branch on
1792 /// a PHI node (or freeze PHI) in the current block. See if there are any
1793 /// simplifications we can do based on inputs to the phi node.
1795  BasicBlock *BB = PN->getParent();
1796 
1797  // TODO: We could make use of this to do it once for blocks with common PHI
1798  // values.
1800  PredBBs.resize(1);
1801 
1802  // If any of the predecessor blocks end in an unconditional branch, we can
1803  // *duplicate* the conditional branch into that block in order to further
1804  // encourage jump threading and to eliminate cases where we have branch on a
1805  // phi of an icmp (branch on icmp is much better).
1806  // This is still beneficial when a frozen phi is used as the branch condition
1807  // because it allows CodeGenPrepare to further canonicalize br(freeze(icmp))
1808  // to br(icmp(freeze ...)).
1809  for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
1810  BasicBlock *PredBB = PN->getIncomingBlock(i);
1811  if (BranchInst *PredBr = dyn_cast<BranchInst>(PredBB->getTerminator()))
1812  if (PredBr->isUnconditional()) {
1813  PredBBs[0] = PredBB;
1814  // Try to duplicate BB into PredBB.
1815  if (duplicateCondBranchOnPHIIntoPred(BB, PredBBs))
1816  return true;
1817  }
1818  }
1819 
1820  return false;
1821 }
1822 
1823 /// processBranchOnXOR - We have an otherwise unthreadable conditional branch on
1824 /// a xor instruction in the current block. See if there are any
1825 /// simplifications we can do based on inputs to the xor.
1827  BasicBlock *BB = BO->getParent();
1828 
1829  // If either the LHS or RHS of the xor is a constant, don't do this
1830  // optimization.
1831  if (isa<ConstantInt>(BO->getOperand(0)) ||
1832  isa<ConstantInt>(BO->getOperand(1)))
1833  return false;
1834 
1835  // If the first instruction in BB isn't a phi, we won't be able to infer
1836  // anything special about any particular predecessor.
1837  if (!isa<PHINode>(BB->front()))
1838  return false;
1839 
1840  // If this BB is a landing pad, we won't be able to split the edge into it.
1841  if (BB->isEHPad())
1842  return false;
1843 
1844  // If we have a xor as the branch input to this block, and we know that the
1845  // LHS or RHS of the xor in any predecessor is true/false, then we can clone
1846  // the condition into the predecessor and fix that value to true, saving some
1847  // logical ops on that path and encouraging other paths to simplify.
1848  //
1849  // This copies something like this:
1850  //
1851  // BB:
1852  // %X = phi i1 [1], [%X']
1853  // %Y = icmp eq i32 %A, %B
1854  // %Z = xor i1 %X, %Y
1855  // br i1 %Z, ...
1856  //
1857  // Into:
1858  // BB':
1859  // %Y = icmp ne i32 %A, %B
1860  // br i1 %Y, ...
1861 
1862  PredValueInfoTy XorOpValues;
1863  bool isLHS = true;
1864  if (!computeValueKnownInPredecessors(BO->getOperand(0), BB, XorOpValues,
1865  WantInteger, BO)) {
1866  assert(XorOpValues.empty());
1867  if (!computeValueKnownInPredecessors(BO->getOperand(1), BB, XorOpValues,
1868  WantInteger, BO))
1869  return false;
1870  isLHS = false;
1871  }
1872 
1873  assert(!XorOpValues.empty() &&
1874  "computeValueKnownInPredecessors returned true with no values");
1875 
1876  // Scan the information to see which is most popular: true or false. The
1877  // predecessors can be of the set true, false, or undef.
1878  unsigned NumTrue = 0, NumFalse = 0;
1879  for (const auto &XorOpValue : XorOpValues) {
1880  if (isa<UndefValue>(XorOpValue.first))
1881  // Ignore undefs for the count.
1882  continue;
1883  if (cast<ConstantInt>(XorOpValue.first)->isZero())
1884  ++NumFalse;
1885  else
1886  ++NumTrue;
1887  }
1888 
1889  // Determine which value to split on, true, false, or undef if neither.
1890  ConstantInt *SplitVal = nullptr;
1891  if (NumTrue > NumFalse)
1892  SplitVal = ConstantInt::getTrue(BB->getContext());
1893  else if (NumTrue != 0 || NumFalse != 0)
1894  SplitVal = ConstantInt::getFalse(BB->getContext());
1895 
1896  // Collect all of the blocks that this can be folded into so that we can
1897  // factor this once and clone it once.
1898  SmallVector<BasicBlock*, 8> BlocksToFoldInto;
1899  for (const auto &XorOpValue : XorOpValues) {
1900  if (XorOpValue.first != SplitVal && !isa<UndefValue>(XorOpValue.first))
1901  continue;
1902 
1903  BlocksToFoldInto.push_back(XorOpValue.second);
1904  }
1905 
1906  // If we inferred a value for all of the predecessors, then duplication won't
1907  // help us. However, we can just replace the LHS or RHS with the constant.
1908  if (BlocksToFoldInto.size() ==
1909  cast<PHINode>(BB->front()).getNumIncomingValues()) {
1910  if (!SplitVal) {
1911  // If all preds provide undef, just nuke the xor, because it is undef too.
1913  BO->eraseFromParent();
1914  } else if (SplitVal->isZero()) {
1915  // If all preds provide 0, replace the xor with the other input.
1916  BO->replaceAllUsesWith(BO->getOperand(isLHS));
1917  BO->eraseFromParent();
1918  } else {
1919  // If all preds provide 1, set the computed value to 1.
1920  BO->setOperand(!isLHS, SplitVal);
1921  }
1922 
1923  return true;
1924  }
1925 
1926  // If any of predecessors end with an indirect goto, we can't change its
1927  // destination. Same for CallBr.
1928  if (any_of(BlocksToFoldInto, [](BasicBlock *Pred) {
1929  return isa<IndirectBrInst>(Pred->getTerminator()) ||
1930  isa<CallBrInst>(Pred->getTerminator());
1931  }))
1932  return false;
1933 
1934  // Try to duplicate BB into PredBB.
1935  return duplicateCondBranchOnPHIIntoPred(BB, BlocksToFoldInto);
1936 }
1937 
1938 /// addPHINodeEntriesForMappedBlock - We're adding 'NewPred' as a new
1939 /// predecessor to the PHIBB block. If it has PHI nodes, add entries for
1940 /// NewPred using the entries from OldPred (suitably mapped).
1942  BasicBlock *OldPred,
1943  BasicBlock *NewPred,
1945  for (PHINode &PN : PHIBB->phis()) {
1946  // Ok, we have a PHI node. Figure out what the incoming value was for the
1947  // DestBlock.
1948  Value *IV = PN.getIncomingValueForBlock(OldPred);
1949 
1950  // Remap the value if necessary.
1951  if (Instruction *Inst = dyn_cast<Instruction>(IV)) {
1953  if (I != ValueMap.end())
1954  IV = I->second;
1955  }
1956 
1957  PN.addIncoming(IV, NewPred);
1958  }
1959 }
1960 
1961 /// Merge basic block BB into its sole predecessor if possible.
1963  BasicBlock *SinglePred = BB->getSinglePredecessor();
1964  if (!SinglePred)
1965  return false;
1966 
1967  const Instruction *TI = SinglePred->getTerminator();
1968  if (TI->isExceptionalTerminator() || TI->getNumSuccessors() != 1 ||
1969  SinglePred == BB || hasAddressTakenAndUsed(BB))
1970  return false;
1971 
1972  // If SinglePred was a loop header, BB becomes one.
1973  if (LoopHeaders.erase(SinglePred))
1974  LoopHeaders.insert(BB);
1975 
1976  LVI->eraseBlock(SinglePred);
1978 
1979  // Now that BB is merged into SinglePred (i.e. SinglePred code followed by
1980  // BB code within one basic block `BB`), we need to invalidate the LVI
1981  // information associated with BB, because the LVI information need not be
1982  // true for all of BB after the merge. For example,
1983  // Before the merge, LVI info and code is as follows:
1984  // SinglePred: <LVI info1 for %p val>
1985  // %y = use of %p
1986  // call @exit() // need not transfer execution to successor.
1987  // assume(%p) // from this point on %p is true
1988  // br label %BB
1989  // BB: <LVI info2 for %p val, i.e. %p is true>
1990  // %x = use of %p
1991  // br label exit
1992  //
1993  // Note that this LVI info for blocks BB and SinglPred is correct for %p
1994  // (info2 and info1 respectively). After the merge and the deletion of the
1995  // LVI info1 for SinglePred. We have the following code:
1996  // BB: <LVI info2 for %p val>
1997  // %y = use of %p
1998  // call @exit()
1999  // assume(%p)
2000  // %x = use of %p <-- LVI info2 is correct from here onwards.
2001  // br label exit
2002  // LVI info2 for BB is incorrect at the beginning of BB.
2003 
2004  // Invalidate LVI information for BB if the LVI is not provably true for
2005  // all of BB.
2007  LVI->eraseBlock(BB);
2008  return true;
2009 }
2010 
2011 /// Update the SSA form. NewBB contains instructions that are copied from BB.
2012 /// ValueMapping maps old values in BB to new ones in NewBB.
2014  BasicBlock *BB, BasicBlock *NewBB,
2015  DenseMap<Instruction *, Value *> &ValueMapping) {
2016  // If there were values defined in BB that are used outside the block, then we
2017  // now have to update all uses of the value to use either the original value,
2018  // the cloned value, or some PHI derived value. This can require arbitrary
2019  // PHI insertion, of which we are prepared to do, clean these up now.
2020  SSAUpdater SSAUpdate;
2021  SmallVector<Use *, 16> UsesToRename;
2022 
2023  for (Instruction &I : *BB) {
2024  // Scan all uses of this instruction to see if it is used outside of its
2025  // block, and if so, record them in UsesToRename.
2026  for (Use &U : I.uses()) {
2027  Instruction *User = cast<Instruction>(U.getUser());
2028  if (PHINode *UserPN = dyn_cast<PHINode>(User)) {
2029  if (UserPN->getIncomingBlock(U) == BB)
2030  continue;
2031  } else if (User->getParent() == BB)
2032  continue;
2033 
2034  UsesToRename.push_back(&U);
2035  }
2036 
2037  // If there are no uses outside the block, we're done with this instruction.
2038  if (UsesToRename.empty())
2039  continue;
2040  LLVM_DEBUG(dbgs() << "JT: Renaming non-local uses of: " << I << "\n");
2041 
2042  // We found a use of I outside of BB. Rename all uses of I that are outside
2043  // its block to be uses of the appropriate PHI node etc. See ValuesInBlocks
2044  // with the two values we know.
2045  SSAUpdate.Initialize(I.getType(), I.getName());
2046  SSAUpdate.AddAvailableValue(BB, &I);
2047  SSAUpdate.AddAvailableValue(NewBB, ValueMapping[&I]);
2048 
2049  while (!UsesToRename.empty())
2050  SSAUpdate.RewriteUse(*UsesToRename.pop_back_val());
2051  LLVM_DEBUG(dbgs() << "\n");
2052  }
2053 }
2054 
2055 /// Clone instructions in range [BI, BE) to NewBB. For PHI nodes, we only clone
2056 /// arguments that come from PredBB. Return the map from the variables in the
2057 /// source basic block to the variables in the newly created basic block.
2060  BasicBlock::iterator BE, BasicBlock *NewBB,
2061  BasicBlock *PredBB) {
2062  // We are going to have to map operands from the source basic block to the new
2063  // copy of the block 'NewBB'. If there are PHI nodes in the source basic
2064  // block, evaluate them to account for entry from PredBB.
2065  DenseMap<Instruction *, Value *> ValueMapping;
2066 
2067  // Clone the phi nodes of the source basic block into NewBB. The resulting
2068  // phi nodes are trivial since NewBB only has one predecessor, but SSAUpdater
2069  // might need to rewrite the operand of the cloned phi.
2070  for (; PHINode *PN = dyn_cast<PHINode>(BI); ++BI) {
2071  PHINode *NewPN = PHINode::Create(PN->getType(), 1, PN->getName(), NewBB);
2072  NewPN->addIncoming(PN->getIncomingValueForBlock(PredBB), PredBB);
2073  ValueMapping[PN] = NewPN;
2074  }
2075 
2076  // Clone noalias scope declarations in the threaded block. When threading a
2077  // loop exit, we would otherwise end up with two idential scope declarations
2078  // visible at the same time.
2079  SmallVector<MDNode *> NoAliasScopes;
2080  DenseMap<MDNode *, MDNode *> ClonedScopes;
2081  LLVMContext &Context = PredBB->getContext();
2082  identifyNoAliasScopesToClone(BI, BE, NoAliasScopes);
2083  cloneNoAliasScopes(NoAliasScopes, ClonedScopes, "thread", Context);
2084 
2085  // Clone the non-phi instructions of the source basic block into NewBB,
2086  // keeping track of the mapping and using it to remap operands in the cloned
2087  // instructions.
2088  for (; BI != BE; ++BI) {
2089  Instruction *New = BI->clone();
2090  New->setName(BI->getName());
2091  NewBB->getInstList().push_back(New);
2092  ValueMapping[&*BI] = New;
2093  adaptNoAliasScopes(New, ClonedScopes, Context);
2094 
2095  // Remap operands to patch up intra-block references.
2096  for (unsigned i = 0, e = New->getNumOperands(); i != e; ++i)
2097  if (Instruction *Inst = dyn_cast<Instruction>(New->getOperand(i))) {
2098  DenseMap<Instruction *, Value *>::iterator I = ValueMapping.find(Inst);
2099  if (I != ValueMapping.end())
2100  New->setOperand(i, I->second);
2101  }
2102  }
2103 
2104  return ValueMapping;
2105 }
2106 
2107 /// Attempt to thread through two successive basic blocks.
2109  Value *Cond) {
2110  // Consider:
2111  //
2112  // PredBB:
2113  // %var = phi i32* [ null, %bb1 ], [ @a, %bb2 ]
2114  // %tobool = icmp eq i32 %cond, 0
2115  // br i1 %tobool, label %BB, label ...
2116  //
2117  // BB:
2118  // %cmp = icmp eq i32* %var, null
2119  // br i1 %cmp, label ..., label ...
2120  //
2121  // We don't know the value of %var at BB even if we know which incoming edge
2122  // we take to BB. However, once we duplicate PredBB for each of its incoming
2123  // edges (say, PredBB1 and PredBB2), we know the value of %var in each copy of
2124  // PredBB. Then we can thread edges PredBB1->BB and PredBB2->BB through BB.
2125 
2126  // Require that BB end with a Branch for simplicity.
2127  BranchInst *CondBr = dyn_cast<BranchInst>(BB->getTerminator());
2128  if (!CondBr)
2129  return false;
2130 
2131  // BB must have exactly one predecessor.
2132  BasicBlock *PredBB = BB->getSinglePredecessor();
2133  if (!PredBB)
2134  return false;
2135 
2136  // Require that PredBB end with a conditional Branch. If PredBB ends with an
2137  // unconditional branch, we should be merging PredBB and BB instead. For
2138  // simplicity, we don't deal with a switch.
2139  BranchInst *PredBBBranch = dyn_cast<BranchInst>(PredBB->getTerminator());
2140  if (!PredBBBranch || PredBBBranch->isUnconditional())
2141  return false;
2142 
2143  // If PredBB has exactly one incoming edge, we don't gain anything by copying
2144  // PredBB.
2145  if (PredBB->getSinglePredecessor())
2146  return false;
2147 
2148  // Don't thread through PredBB if it contains a successor edge to itself, in
2149  // which case we would infinite loop. Suppose we are threading an edge from
2150  // PredPredBB through PredBB and BB to SuccBB with PredBB containing a
2151  // successor edge to itself. If we allowed jump threading in this case, we
2152  // could duplicate PredBB and BB as, say, PredBB.thread and BB.thread. Since
2153  // PredBB.thread has a successor edge to PredBB, we would immediately come up
2154  // with another jump threading opportunity from PredBB.thread through PredBB
2155  // and BB to SuccBB. This jump threading would repeatedly occur. That is, we
2156  // would keep peeling one iteration from PredBB.
2157  if (llvm::is_contained(successors(PredBB), PredBB))
2158  return false;
2159 
2160  // Don't thread across a loop header.
2161  if (LoopHeaders.count(PredBB))
2162  return false;
2163 
2164  // Avoid complication with duplicating EH pads.
2165  if (PredBB->isEHPad())
2166  return false;
2167 
2168  // Find a predecessor that we can thread. For simplicity, we only consider a
2169  // successor edge out of BB to which we thread exactly one incoming edge into
2170  // PredBB.
2171  unsigned ZeroCount = 0;
2172  unsigned OneCount = 0;
2173  BasicBlock *ZeroPred = nullptr;
2174  BasicBlock *OnePred = nullptr;
2175  for (BasicBlock *P : predecessors(PredBB)) {
2176  if (ConstantInt *CI = dyn_cast_or_null<ConstantInt>(
2177  evaluateOnPredecessorEdge(BB, P, Cond))) {
2178  if (CI->isZero()) {
2179  ZeroCount++;
2180  ZeroPred = P;
2181  } else if (CI->isOne()) {
2182  OneCount++;
2183  OnePred = P;
2184  }
2185  }
2186  }
2187 
2188  // Disregard complicated cases where we have to thread multiple edges.
2189  BasicBlock *PredPredBB;
2190  if (ZeroCount == 1) {
2191  PredPredBB = ZeroPred;
2192  } else if (OneCount == 1) {
2193  PredPredBB = OnePred;
2194  } else {
2195  return false;
2196  }
2197 
2198  BasicBlock *SuccBB = CondBr->getSuccessor(PredPredBB == ZeroPred);
2199 
2200  // If threading to the same block as we come from, we would infinite loop.
2201  if (SuccBB == BB) {
2202  LLVM_DEBUG(dbgs() << " Not threading across BB '" << BB->getName()
2203  << "' - would thread to self!\n");
2204  return false;
2205  }
2206 
2207  // If threading this would thread across a loop header, don't thread the edge.
2208  // See the comments above findLoopHeaders for justifications and caveats.
2209  if (LoopHeaders.count(BB) || LoopHeaders.count(SuccBB)) {
2210  LLVM_DEBUG({
2211  bool BBIsHeader = LoopHeaders.count(BB);
2212  bool SuccIsHeader = LoopHeaders.count(SuccBB);
2213  dbgs() << " Not threading across "
2214  << (BBIsHeader ? "loop header BB '" : "block BB '")
2215  << BB->getName() << "' to dest "
2216  << (SuccIsHeader ? "loop header BB '" : "block BB '")
2217  << SuccBB->getName()
2218  << "' - it might create an irreducible loop!\n";
2219  });
2220  return false;
2221  }
2222 
2223  // Compute the cost of duplicating BB and PredBB.
2224  unsigned BBCost = getJumpThreadDuplicationCost(
2225  TTI, BB, BB->getTerminator(), BBDupThreshold);
2226  unsigned PredBBCost = getJumpThreadDuplicationCost(
2227  TTI, PredBB, PredBB->getTerminator(), BBDupThreshold);
2228 
2229  // Give up if costs are too high. We need to check BBCost and PredBBCost
2230  // individually before checking their sum because getJumpThreadDuplicationCost
2231  // return (unsigned)~0 for those basic blocks that cannot be duplicated.
2232  if (BBCost > BBDupThreshold || PredBBCost > BBDupThreshold ||
2233  BBCost + PredBBCost > BBDupThreshold) {
2234  LLVM_DEBUG(dbgs() << " Not threading BB '" << BB->getName()
2235  << "' - Cost is too high: " << PredBBCost
2236  << " for PredBB, " << BBCost << "for BB\n");
2237  return false;
2238  }
2239 
2240  // Now we are ready to duplicate PredBB.
2241  threadThroughTwoBasicBlocks(PredPredBB, PredBB, BB, SuccBB);
2242  return true;
2243 }
2244 
2246  BasicBlock *PredBB,
2247  BasicBlock *BB,
2248  BasicBlock *SuccBB) {
2249  LLVM_DEBUG(dbgs() << " Threading through '" << PredBB->getName() << "' and '"
2250  << BB->getName() << "'\n");
2251 
2252  BranchInst *CondBr = cast<BranchInst>(BB->getTerminator());
2253  BranchInst *PredBBBranch = cast<BranchInst>(PredBB->getTerminator());
2254 
2255  BasicBlock *NewBB =
2256  BasicBlock::Create(PredBB->getContext(), PredBB->getName() + ".thread",
2257  PredBB->getParent(), PredBB);
2258  NewBB->moveAfter(PredBB);
2259 
2260  // Set the block frequency of NewBB.
2261  if (HasProfileData) {
2262  auto NewBBFreq = BFI->getBlockFreq(PredPredBB) *
2263  BPI->getEdgeProbability(PredPredBB, PredBB);
2264  BFI->setBlockFreq(NewBB, NewBBFreq.getFrequency());
2265  }
2266 
2267  // We are going to have to map operands from the original BB block to the new
2268  // copy of the block 'NewBB'. If there are PHI nodes in PredBB, evaluate them
2269  // to account for entry from PredPredBB.
2270  DenseMap<Instruction *, Value *> ValueMapping =
2271  cloneInstructions(PredBB->begin(), PredBB->end(), NewBB, PredPredBB);
2272 
2273  // Copy the edge probabilities from PredBB to NewBB.
2274  if (HasProfileData)
2275  BPI->copyEdgeProbabilities(PredBB, NewBB);
2276 
2277  // Update the terminator of PredPredBB to jump to NewBB instead of PredBB.
2278  // This eliminates predecessors from PredPredBB, which requires us to simplify
2279  // any PHI nodes in PredBB.
2280  Instruction *PredPredTerm = PredPredBB->getTerminator();
2281  for (unsigned i = 0, e = PredPredTerm->getNumSuccessors(); i != e; ++i)
2282  if (PredPredTerm->getSuccessor(i) == PredBB) {
2283  PredBB->removePredecessor(PredPredBB, true);
2284  PredPredTerm->setSuccessor(i, NewBB);
2285  }
2286 
2287  addPHINodeEntriesForMappedBlock(PredBBBranch->getSuccessor(0), PredBB, NewBB,
2288  ValueMapping);
2289  addPHINodeEntriesForMappedBlock(PredBBBranch->getSuccessor(1), PredBB, NewBB,
2290  ValueMapping);
2291 
2292  DTU->applyUpdatesPermissive(
2293  {{DominatorTree::Insert, NewBB, CondBr->getSuccessor(0)},
2294  {DominatorTree::Insert, NewBB, CondBr->getSuccessor(1)},
2295  {DominatorTree::Insert, PredPredBB, NewBB},
2296  {DominatorTree::Delete, PredPredBB, PredBB}});
2297 
2298  updateSSA(PredBB, NewBB, ValueMapping);
2299 
2300  // Clean up things like PHI nodes with single operands, dead instructions,
2301  // etc.
2302  SimplifyInstructionsInBlock(NewBB, TLI);
2303  SimplifyInstructionsInBlock(PredBB, TLI);
2304 
2305  SmallVector<BasicBlock *, 1> PredsToFactor;
2306  PredsToFactor.push_back(NewBB);
2307  threadEdge(BB, PredsToFactor, SuccBB);
2308 }
2309 
2310 /// tryThreadEdge - Thread an edge if it's safe and profitable to do so.
2312  BasicBlock *BB, const SmallVectorImpl<BasicBlock *> &PredBBs,
2313  BasicBlock *SuccBB) {
2314  // If threading to the same block as we come from, we would infinite loop.
2315  if (SuccBB == BB) {
2316  LLVM_DEBUG(dbgs() << " Not threading across BB '" << BB->getName()
2317  << "' - would thread to self!\n");
2318  return false;
2319  }
2320 
2321  // If threading this would thread across a loop header, don't thread the edge.
2322  // See the comments above findLoopHeaders for justifications and caveats.
2323  if (LoopHeaders.count(BB) || LoopHeaders.count(SuccBB)) {
2324  LLVM_DEBUG({
2325  bool BBIsHeader = LoopHeaders.count(BB);
2326  bool SuccIsHeader = LoopHeaders.count(SuccBB);
2327  dbgs() << " Not threading across "
2328  << (BBIsHeader ? "loop header BB '" : "block BB '") << BB->getName()
2329  << "' to dest " << (SuccIsHeader ? "loop header BB '" : "block BB '")
2330  << SuccBB->getName() << "' - it might create an irreducible loop!\n";
2331  });
2332  return false;
2333  }
2334 
2335  unsigned JumpThreadCost = getJumpThreadDuplicationCost(
2336  TTI, BB, BB->getTerminator(), BBDupThreshold);
2337  if (JumpThreadCost > BBDupThreshold) {
2338  LLVM_DEBUG(dbgs() << " Not threading BB '" << BB->getName()
2339  << "' - Cost is too high: " << JumpThreadCost << "\n");
2340  return false;
2341  }
2342 
2343  threadEdge(BB, PredBBs, SuccBB);
2344  return true;
2345 }
2346 
2347 /// threadEdge - We have decided that it is safe and profitable to factor the
2348 /// blocks in PredBBs to one predecessor, then thread an edge from it to SuccBB
2349 /// across BB. Transform the IR to reflect this change.
2351  const SmallVectorImpl<BasicBlock *> &PredBBs,
2352  BasicBlock *SuccBB) {
2353  assert(SuccBB != BB && "Don't create an infinite loop");
2354 
2355  assert(!LoopHeaders.count(BB) && !LoopHeaders.count(SuccBB) &&
2356  "Don't thread across loop headers");
2357 
2358  // And finally, do it! Start by factoring the predecessors if needed.
2359  BasicBlock *PredBB;
2360  if (PredBBs.size() == 1)
2361  PredBB = PredBBs[0];
2362  else {
2363  LLVM_DEBUG(dbgs() << " Factoring out " << PredBBs.size()
2364  << " common predecessors.\n");
2365  PredBB = splitBlockPreds(BB, PredBBs, ".thr_comm");
2366  }
2367 
2368  // And finally, do it!
2369  LLVM_DEBUG(dbgs() << " Threading edge from '" << PredBB->getName()
2370  << "' to '" << SuccBB->getName()
2371  << ", across block:\n " << *BB << "\n");
2372 
2373  LVI->threadEdge(PredBB, BB, SuccBB);
2374 
2375  BasicBlock *NewBB = BasicBlock::Create(BB->getContext(),
2376  BB->getName()+".thread",
2377  BB->getParent(), BB);
2378  NewBB->moveAfter(PredBB);
2379 
2380  // Set the block frequency of NewBB.
2381  if (HasProfileData) {
2382  auto NewBBFreq =
2383  BFI->getBlockFreq(PredBB) * BPI->getEdgeProbability(PredBB, BB);
2384  BFI->setBlockFreq(NewBB, NewBBFreq.getFrequency());
2385  }
2386 
2387  // Copy all the instructions from BB to NewBB except the terminator.
2388  DenseMap<Instruction *, Value *> ValueMapping =
2389  cloneInstructions(BB->begin(), std::prev(BB->end()), NewBB, PredBB);
2390 
2391  // We didn't copy the terminator from BB over to NewBB, because there is now
2392  // an unconditional jump to SuccBB. Insert the unconditional jump.
2393  BranchInst *NewBI = BranchInst::Create(SuccBB, NewBB);
2394  NewBI->setDebugLoc(BB->getTerminator()->getDebugLoc());
2395 
2396  // Check to see if SuccBB has PHI nodes. If so, we need to add entries to the
2397  // PHI nodes for NewBB now.
2398  addPHINodeEntriesForMappedBlock(SuccBB, BB, NewBB, ValueMapping);
2399 
2400  // Update the terminator of PredBB to jump to NewBB instead of BB. This
2401  // eliminates predecessors from BB, which requires us to simplify any PHI
2402  // nodes in BB.
2403  Instruction *PredTerm = PredBB->getTerminator();
2404  for (unsigned i = 0, e = PredTerm->getNumSuccessors(); i != e; ++i)
2405  if (PredTerm->getSuccessor(i) == BB) {
2406  BB->removePredecessor(PredBB, true);
2407  PredTerm->setSuccessor(i, NewBB);
2408  }
2409 
2410  // Enqueue required DT updates.
2411  DTU->applyUpdatesPermissive({{DominatorTree::Insert, NewBB, SuccBB},
2412  {DominatorTree::Insert, PredBB, NewBB},
2413  {DominatorTree::Delete, PredBB, BB}});
2414 
2415  updateSSA(BB, NewBB, ValueMapping);
2416 
2417  // At this point, the IR is fully up to date and consistent. Do a quick scan
2418  // over the new instructions and zap any that are constants or dead. This
2419  // frequently happens because of phi translation.
2420  SimplifyInstructionsInBlock(NewBB, TLI);
2421 
2422  // Update the edge weight from BB to SuccBB, which should be less than before.
2423  updateBlockFreqAndEdgeWeight(PredBB, BB, NewBB, SuccBB);
2424 
2425  // Threaded an edge!
2426  ++NumThreads;
2427 }
2428 
2429 /// Create a new basic block that will be the predecessor of BB and successor of
2430 /// all blocks in Preds. When profile data is available, update the frequency of
2431 /// this new block.
2432 BasicBlock *JumpThreadingPass::splitBlockPreds(BasicBlock *BB,
2433  ArrayRef<BasicBlock *> Preds,
2434  const char *Suffix) {
2436 
2437  // Collect the frequencies of all predecessors of BB, which will be used to
2438  // update the edge weight of the result of splitting predecessors.
2440  if (HasProfileData)
2441  for (auto Pred : Preds)
2442  FreqMap.insert(std::make_pair(
2443  Pred, BFI->getBlockFreq(Pred) * BPI->getEdgeProbability(Pred, BB)));
2444 
2445  // In the case when BB is a LandingPad block we create 2 new predecessors
2446  // instead of just one.
2447  if (BB->isLandingPad()) {
2448  std::string NewName = std::string(Suffix) + ".split-lp";
2449  SplitLandingPadPredecessors(BB, Preds, Suffix, NewName.c_str(), NewBBs);
2450  } else {
2451  NewBBs.push_back(SplitBlockPredecessors(BB, Preds, Suffix));
2452  }
2453 
2454  std::vector<DominatorTree::UpdateType> Updates;
2455  Updates.reserve((2 * Preds.size()) + NewBBs.size());
2456  for (auto NewBB : NewBBs) {
2457  BlockFrequency NewBBFreq(0);
2458  Updates.push_back({DominatorTree::Insert, NewBB, BB});
2459  for (auto Pred : predecessors(NewBB)) {
2460  Updates.push_back({DominatorTree::Delete, Pred, BB});
2461  Updates.push_back({DominatorTree::Insert, Pred, NewBB});
2462  if (HasProfileData) // Update frequencies between Pred -> NewBB.
2463  NewBBFreq += FreqMap.lookup(Pred);
2464  }
2465  if (HasProfileData) // Apply the summed frequency to NewBB.
2466  BFI->setBlockFreq(NewBB, NewBBFreq.getFrequency());
2467  }
2468 
2469  DTU->applyUpdatesPermissive(Updates);
2470  return NewBBs[0];
2471 }
2472 
2473 bool JumpThreadingPass::doesBlockHaveProfileData(BasicBlock *BB) {
2474  const Instruction *TI = BB->getTerminator();
2475  assert(TI->getNumSuccessors() > 1 && "not a split");
2476 
2477  MDNode *WeightsNode = TI->getMetadata(LLVMContext::MD_prof);
2478  if (!WeightsNode)
2479  return false;
2480 
2481  MDString *MDName = cast<MDString>(WeightsNode->getOperand(0));
2482  if (MDName->getString() != "branch_weights")
2483  return false;
2484 
2485  // Ensure there are weights for all of the successors. Note that the first
2486  // operand to the metadata node is a name, not a weight.
2487  return WeightsNode->getNumOperands() == TI->getNumSuccessors() + 1;
2488 }
2489 
2490 /// Update the block frequency of BB and branch weight and the metadata on the
2491 /// edge BB->SuccBB. This is done by scaling the weight of BB->SuccBB by 1 -
2492 /// Freq(PredBB->BB) / Freq(BB->SuccBB).
2493 void JumpThreadingPass::updateBlockFreqAndEdgeWeight(BasicBlock *PredBB,
2494  BasicBlock *BB,
2495  BasicBlock *NewBB,
2496  BasicBlock *SuccBB) {
2497  if (!HasProfileData)
2498  return;
2499 
2500  assert(BFI && BPI && "BFI & BPI should have been created here");
2501 
2502  // As the edge from PredBB to BB is deleted, we have to update the block
2503  // frequency of BB.
2504  auto BBOrigFreq = BFI->getBlockFreq(BB);
2505  auto NewBBFreq = BFI->getBlockFreq(NewBB);
2506  auto BB2SuccBBFreq = BBOrigFreq * BPI->getEdgeProbability(BB, SuccBB);
2507  auto BBNewFreq = BBOrigFreq - NewBBFreq;
2508  BFI->setBlockFreq(BB, BBNewFreq.getFrequency());
2509 
2510  // Collect updated outgoing edges' frequencies from BB and use them to update
2511  // edge probabilities.
2512  SmallVector<uint64_t, 4> BBSuccFreq;
2513  for (BasicBlock *Succ : successors(BB)) {
2514  auto SuccFreq = (Succ == SuccBB)
2515  ? BB2SuccBBFreq - NewBBFreq
2516  : BBOrigFreq * BPI->getEdgeProbability(BB, Succ);
2517  BBSuccFreq.push_back(SuccFreq.getFrequency());
2518  }
2519 
2520  uint64_t MaxBBSuccFreq =
2521  *std::max_element(BBSuccFreq.begin(), BBSuccFreq.end());
2522 
2524  if (MaxBBSuccFreq == 0)
2525  BBSuccProbs.assign(BBSuccFreq.size(),
2526  {1, static_cast<unsigned>(BBSuccFreq.size())});
2527  else {
2528  for (uint64_t Freq : BBSuccFreq)
2529  BBSuccProbs.push_back(
2530  BranchProbability::getBranchProbability(Freq, MaxBBSuccFreq));
2531  // Normalize edge probabilities so that they sum up to one.
2532  BranchProbability::normalizeProbabilities(BBSuccProbs.begin(),
2533  BBSuccProbs.end());
2534  }
2535 
2536  // Update edge probabilities in BPI.
2537  BPI->setEdgeProbability(BB, BBSuccProbs);
2538 
2539  // Update the profile metadata as well.
2540  //
2541  // Don't do this if the profile of the transformed blocks was statically
2542  // estimated. (This could occur despite the function having an entry
2543  // frequency in completely cold parts of the CFG.)
2544  //
2545  // In this case we don't want to suggest to subsequent passes that the
2546  // calculated weights are fully consistent. Consider this graph:
2547  //
2548  // check_1
2549  // 50% / |
2550  // eq_1 | 50%
2551  // \ |
2552  // check_2
2553  // 50% / |
2554  // eq_2 | 50%
2555  // \ |
2556  // check_3
2557  // 50% / |
2558  // eq_3 | 50%
2559  // \ |
2560  //
2561  // Assuming the blocks check_* all compare the same value against 1, 2 and 3,
2562  // the overall probabilities are inconsistent; the total probability that the
2563  // value is either 1, 2 or 3 is 150%.
2564  //
2565  // As a consequence if we thread eq_1 -> check_2 to check_3, check_2->check_3
2566  // becomes 0%. This is even worse if the edge whose probability becomes 0% is
2567  // the loop exit edge. Then based solely on static estimation we would assume
2568  // the loop was extremely hot.
2569  //
2570  // FIXME this locally as well so that BPI and BFI are consistent as well. We
2571  // shouldn't make edges extremely likely or unlikely based solely on static
2572  // estimation.
2573  if (BBSuccProbs.size() >= 2 && doesBlockHaveProfileData(BB)) {
2574  SmallVector<uint32_t, 4> Weights;
2575  for (auto Prob : BBSuccProbs)
2576  Weights.push_back(Prob.getNumerator());
2577 
2578  auto TI = BB->getTerminator();
2579  TI->setMetadata(
2580  LLVMContext::MD_prof,
2581  MDBuilder(TI->getParent()->getContext()).createBranchWeights(Weights));
2582  }
2583 }
2584 
2585 /// duplicateCondBranchOnPHIIntoPred - PredBB contains an unconditional branch
2586 /// to BB which contains an i1 PHI node and a conditional branch on that PHI.
2587 /// If we can duplicate the contents of BB up into PredBB do so now, this
2588 /// improves the odds that the branch will be on an analyzable instruction like
2589 /// a compare.
2591  BasicBlock *BB, const SmallVectorImpl<BasicBlock *> &PredBBs) {
2592  assert(!PredBBs.empty() && "Can't handle an empty set");
2593 
2594  // If BB is a loop header, then duplicating this block outside the loop would
2595  // cause us to transform this into an irreducible loop, don't do this.
2596  // See the comments above findLoopHeaders for justifications and caveats.
2597  if (LoopHeaders.count(BB)) {
2598  LLVM_DEBUG(dbgs() << " Not duplicating loop header '" << BB->getName()
2599  << "' into predecessor block '" << PredBBs[0]->getName()
2600  << "' - it might create an irreducible loop!\n");
2601  return false;
2602  }
2603 
2604  unsigned DuplicationCost = getJumpThreadDuplicationCost(
2605  TTI, BB, BB->getTerminator(), BBDupThreshold);
2606  if (DuplicationCost > BBDupThreshold) {
2607  LLVM_DEBUG(dbgs() << " Not duplicating BB '" << BB->getName()
2608  << "' - Cost is too high: " << DuplicationCost << "\n");
2609  return false;
2610  }
2611 
2612  // And finally, do it! Start by factoring the predecessors if needed.
2613  std::vector<DominatorTree::UpdateType> Updates;
2614  BasicBlock *PredBB;
2615  if (PredBBs.size() == 1)
2616  PredBB = PredBBs[0];
2617  else {
2618  LLVM_DEBUG(dbgs() << " Factoring out " << PredBBs.size()
2619  << " common predecessors.\n");
2620  PredBB = splitBlockPreds(BB, PredBBs, ".thr_comm");
2621  }
2622  Updates.push_back({DominatorTree::Delete, PredBB, BB});
2623 
2624  // Okay, we decided to do this! Clone all the instructions in BB onto the end
2625  // of PredBB.
2626  LLVM_DEBUG(dbgs() << " Duplicating block '" << BB->getName()
2627  << "' into end of '" << PredBB->getName()
2628  << "' to eliminate branch on phi. Cost: "
2629  << DuplicationCost << " block is:" << *BB << "\n");
2630 
2631  // Unless PredBB ends with an unconditional branch, split the edge so that we
2632  // can just clone the bits from BB into the end of the new PredBB.
2633  BranchInst *OldPredBranch = dyn_cast<BranchInst>(PredBB->getTerminator());
2634 
2635  if (!OldPredBranch || !OldPredBranch->isUnconditional()) {
2636  BasicBlock *OldPredBB = PredBB;
2637  PredBB = SplitEdge(OldPredBB, BB);
2638  Updates.push_back({DominatorTree::Insert, OldPredBB, PredBB});
2639  Updates.push_back({DominatorTree::Insert, PredBB, BB});
2640  Updates.push_back({DominatorTree::Delete, OldPredBB, BB});
2641  OldPredBranch = cast<BranchInst>(PredBB->getTerminator());
2642  }
2643 
2644  // We are going to have to map operands from the original BB block into the
2645  // PredBB block. Evaluate PHI nodes in BB.
2646  DenseMap<Instruction*, Value*> ValueMapping;
2647 
2648  BasicBlock::iterator BI = BB->begin();
2649  for (; PHINode *PN = dyn_cast<PHINode>(BI); ++BI)
2650  ValueMapping[PN] = PN->getIncomingValueForBlock(PredBB);
2651  // Clone the non-phi instructions of BB into PredBB, keeping track of the
2652  // mapping and using it to remap operands in the cloned instructions.
2653  for (; BI != BB->end(); ++BI) {
2654  Instruction *New = BI->clone();
2655 
2656  // Remap operands to patch up intra-block references.
2657  for (unsigned i = 0, e = New->getNumOperands(); i != e; ++i)
2658  if (Instruction *Inst = dyn_cast<Instruction>(New->getOperand(i))) {
2659  DenseMap<Instruction*, Value*>::iterator I = ValueMapping.find(Inst);
2660  if (I != ValueMapping.end())
2661  New->setOperand(i, I->second);
2662  }
2663 
2664  // If this instruction can be simplified after the operands are updated,
2665  // just use the simplified value instead. This frequently happens due to
2666  // phi translation.
2667  if (Value *IV = SimplifyInstruction(
2668  New,
2669  {BB->getModule()->getDataLayout(), TLI, nullptr, nullptr, New})) {
2670  ValueMapping[&*BI] = IV;
2671  if (!New->mayHaveSideEffects()) {
2672  New->deleteValue();
2673  New = nullptr;
2674  }
2675  } else {
2676  ValueMapping[&*BI] = New;
2677  }
2678  if (New) {
2679  // Otherwise, insert the new instruction into the block.
2680  New->setName(BI->getName());
2681  PredBB->getInstList().insert(OldPredBranch->getIterator(), New);
2682  // Update Dominance from simplified New instruction operands.
2683  for (unsigned i = 0, e = New->getNumOperands(); i != e; ++i)
2684  if (BasicBlock *SuccBB = dyn_cast<BasicBlock>(New->getOperand(i)))
2685  Updates.push_back({DominatorTree::Insert, PredBB, SuccBB});
2686  }
2687  }
2688 
2689  // Check to see if the targets of the branch had PHI nodes. If so, we need to
2690  // add entries to the PHI nodes for branch from PredBB now.
2691  BranchInst *BBBranch = cast<BranchInst>(BB->getTerminator());
2692  addPHINodeEntriesForMappedBlock(BBBranch->getSuccessor(0), BB, PredBB,
2693  ValueMapping);
2694  addPHINodeEntriesForMappedBlock(BBBranch->getSuccessor(1), BB, PredBB,
2695  ValueMapping);
2696 
2697  updateSSA(BB, PredBB, ValueMapping);
2698 
2699  // PredBB no longer jumps to BB, remove entries in the PHI node for the edge
2700  // that we nuked.
2701  BB->removePredecessor(PredBB, true);
2702 
2703  // Remove the unconditional branch at the end of the PredBB block.
2704  OldPredBranch->eraseFromParent();
2705  if (HasProfileData)
2706  BPI->copyEdgeProbabilities(BB, PredBB);
2707  DTU->applyUpdatesPermissive(Updates);
2708 
2709  ++NumDupes;
2710  return true;
2711 }
2712 
2713 // Pred is a predecessor of BB with an unconditional branch to BB. SI is
2714 // a Select instruction in Pred. BB has other predecessors and SI is used in
2715 // a PHI node in BB. SI has no other use.
2716 // A new basic block, NewBB, is created and SI is converted to compare and
2717 // conditional branch. SI is erased from parent.
2719  SelectInst *SI, PHINode *SIUse,
2720  unsigned Idx) {
2721  // Expand the select.
2722  //
2723  // Pred --
2724  // | v
2725  // | NewBB
2726  // | |
2727  // |-----
2728  // v
2729  // BB
2730  BranchInst *PredTerm = cast<BranchInst>(Pred->getTerminator());
2731  BasicBlock *NewBB = BasicBlock::Create(BB->getContext(), "select.unfold",
2732  BB->getParent(), BB);
2733  // Move the unconditional branch to NewBB.
2734  PredTerm->removeFromParent();
2735  NewBB->getInstList().insert(NewBB->end(), PredTerm);
2736  // Create a conditional branch and update PHI nodes.
2737  auto *BI = BranchInst::Create(NewBB, BB, SI->getCondition(), Pred);
2738  BI->applyMergedLocation(PredTerm->getDebugLoc(), SI->getDebugLoc());
2739  SIUse->setIncomingValue(Idx, SI->getFalseValue());
2740  SIUse->addIncoming(SI->getTrueValue(), NewBB);
2741 
2742  // The select is now dead.
2743  SI->eraseFromParent();
2744  DTU->applyUpdatesPermissive({{DominatorTree::Insert, NewBB, BB},
2745  {DominatorTree::Insert, Pred, NewBB}});
2746 
2747  // Update any other PHI nodes in BB.
2748  for (BasicBlock::iterator BI = BB->begin();
2749  PHINode *Phi = dyn_cast<PHINode>(BI); ++BI)
2750  if (Phi != SIUse)
2751  Phi->addIncoming(Phi->getIncomingValueForBlock(Pred), NewBB);
2752 }
2753 
2755  PHINode *CondPHI = dyn_cast<PHINode>(SI->getCondition());
2756 
2757  if (!CondPHI || CondPHI->getParent() != BB)
2758  return false;
2759 
2760  for (unsigned I = 0, E = CondPHI->getNumIncomingValues(); I != E; ++I) {
2761  BasicBlock *Pred = CondPHI->getIncomingBlock(I);
2762  SelectInst *PredSI = dyn_cast<SelectInst>(CondPHI->getIncomingValue(I));
2763 
2764  // The second and third condition can be potentially relaxed. Currently
2765  // the conditions help to simplify the code and allow us to reuse existing
2766  // code, developed for tryToUnfoldSelect(CmpInst *, BasicBlock *)
2767  if (!PredSI || PredSI->getParent() != Pred || !PredSI->hasOneUse())
2768  continue;
2769 
2770  BranchInst *PredTerm = dyn_cast<BranchInst>(Pred->getTerminator());
2771  if (!PredTerm || !PredTerm->isUnconditional())
2772  continue;
2773 
2774  unfoldSelectInstr(Pred, BB, PredSI, CondPHI, I);
2775  return true;
2776  }
2777  return false;
2778 }
2779 
2780 /// tryToUnfoldSelect - Look for blocks of the form
2781 /// bb1:
2782 /// %a = select
2783 /// br bb2
2784 ///
2785 /// bb2:
2786 /// %p = phi [%a, %bb1] ...
2787 /// %c = icmp %p
2788 /// br i1 %c
2789 ///
2790 /// And expand the select into a branch structure if one of its arms allows %c
2791 /// to be folded. This later enables threading from bb1 over bb2.
2793  BranchInst *CondBr = dyn_cast<BranchInst>(BB->getTerminator());
2794  PHINode *CondLHS = dyn_cast<PHINode>(CondCmp->getOperand(0));
2795  Constant *CondRHS = cast<Constant>(CondCmp->getOperand(1));
2796 
2797  if (!CondBr || !CondBr->isConditional() || !CondLHS ||
2798  CondLHS->getParent() != BB)
2799  return false;
2800 
2801  for (unsigned I = 0, E = CondLHS->getNumIncomingValues(); I != E; ++I) {
2802  BasicBlock *Pred = CondLHS->getIncomingBlock(I);
2803  SelectInst *SI = dyn_cast<SelectInst>(CondLHS->getIncomingValue(I));
2804 
2805  // Look if one of the incoming values is a select in the corresponding
2806  // predecessor.
2807  if (!SI || SI->getParent() != Pred || !SI->hasOneUse())
2808  continue;
2809 
2810  BranchInst *PredTerm = dyn_cast<BranchInst>(Pred->getTerminator());
2811  if (!PredTerm || !PredTerm->isUnconditional())
2812  continue;
2813 
2814  // Now check if one of the select values would allow us to constant fold the
2815  // terminator in BB. We don't do the transform if both sides fold, those
2816  // cases will be threaded in any case.
2817  LazyValueInfo::Tristate LHSFolds =
2818  LVI->getPredicateOnEdge(CondCmp->getPredicate(), SI->getOperand(1),
2819  CondRHS, Pred, BB, CondCmp);
2820  LazyValueInfo::Tristate RHSFolds =
2821  LVI->getPredicateOnEdge(CondCmp->getPredicate(), SI->getOperand(2),
2822  CondRHS, Pred, BB, CondCmp);
2823  if ((LHSFolds != LazyValueInfo::Unknown ||
2824  RHSFolds != LazyValueInfo::Unknown) &&
2825  LHSFolds != RHSFolds) {
2826  unfoldSelectInstr(Pred, BB, SI, CondLHS, I);
2827  return true;
2828  }
2829  }
2830  return false;
2831 }
2832 
2833 /// tryToUnfoldSelectInCurrBB - Look for PHI/Select or PHI/CMP/Select in the
2834 /// same BB in the form
2835 /// bb:
2836 /// %p = phi [false, %bb1], [true, %bb2], [false, %bb3], [true, %bb4], ...
2837 /// %s = select %p, trueval, falseval
2838 ///
2839 /// or
2840 ///
2841 /// bb:
2842 /// %p = phi [0, %bb1], [1, %bb2], [0, %bb3], [1, %bb4], ...
2843 /// %c = cmp %p, 0
2844 /// %s = select %c, trueval, falseval
2845 ///
2846 /// And expand the select into a branch structure. This later enables
2847 /// jump-threading over bb in this pass.
2848 ///
2849 /// Using the similar approach of SimplifyCFG::FoldCondBranchOnPHI(), unfold
2850 /// select if the associated PHI has at least one constant. If the unfolded
2851 /// select is not jump-threaded, it will be folded again in the later
2852 /// optimizations.
2854  // This transform would reduce the quality of msan diagnostics.
2855  // Disable this transform under MemorySanitizer.
2856  if (BB->getParent()->hasFnAttribute(Attribute::SanitizeMemory))
2857  return false;
2858 
2859  // If threading this would thread across a loop header, don't thread the edge.
2860  // See the comments above findLoopHeaders for justifications and caveats.
2861  if (LoopHeaders.count(BB))
2862  return false;
2863 
2864  for (BasicBlock::iterator BI = BB->begin();
2865  PHINode *PN = dyn_cast<PHINode>(BI); ++BI) {
2866  // Look for a Phi having at least one constant incoming value.
2867  if (llvm::all_of(PN->incoming_values(),
2868  [](Value *V) { return !isa<ConstantInt>(V); }))
2869  continue;
2870 
2871  auto isUnfoldCandidate = [BB](SelectInst *SI, Value *V) {
2872  using namespace PatternMatch;
2873 
2874  // Check if SI is in BB and use V as condition.
2875  if (SI->getParent() != BB)
2876  return false;
2877  Value *Cond = SI->getCondition();
2878  bool IsAndOr = match(SI, m_CombineOr(m_LogicalAnd(), m_LogicalOr()));
2879  return Cond && Cond == V && Cond->getType()->isIntegerTy(1) && !IsAndOr;
2880  };
2881 
2882  SelectInst *SI = nullptr;
2883  for (Use &U : PN->uses()) {
2884  if (ICmpInst *Cmp = dyn_cast<ICmpInst>(U.getUser())) {
2885  // Look for a ICmp in BB that compares PN with a constant and is the
2886  // condition of a Select.
2887  if (Cmp->getParent() == BB && Cmp->hasOneUse() &&
2888  isa<ConstantInt>(Cmp->getOperand(1 - U.getOperandNo())))
2889  if (SelectInst *SelectI = dyn_cast<SelectInst>(Cmp->user_back()))
2890  if (isUnfoldCandidate(SelectI, Cmp->use_begin()->get())) {
2891  SI = SelectI;
2892  break;
2893  }
2894  } else if (SelectInst *SelectI = dyn_cast<SelectInst>(U.getUser())) {
2895  // Look for a Select in BB that uses PN as condition.
2896  if (isUnfoldCandidate(SelectI, U.get())) {
2897  SI = SelectI;
2898  break;
2899  }
2900  }
2901  }
2902 
2903  if (!SI)
2904  continue;
2905  // Expand the select.
2906  Value *Cond = SI->getCondition();
2907  if (!isGuaranteedNotToBeUndefOrPoison(Cond, nullptr, SI))
2908  Cond = new FreezeInst(Cond, "cond.fr", SI);
2910  BasicBlock *SplitBB = SI->getParent();
2911  BasicBlock *NewBB = Term->getParent();
2912  PHINode *NewPN = PHINode::Create(SI->getType(), 2, "", SI);
2913  NewPN->addIncoming(SI->getTrueValue(), Term->getParent());
2914  NewPN->addIncoming(SI->getFalseValue(), BB);
2915  SI->replaceAllUsesWith(NewPN);
2916  SI->eraseFromParent();
2917  // NewBB and SplitBB are newly created blocks which require insertion.
2918  std::vector<DominatorTree::UpdateType> Updates;
2919  Updates.reserve((2 * SplitBB->getTerminator()->getNumSuccessors()) + 3);
2920  Updates.push_back({DominatorTree::Insert, BB, SplitBB});
2921  Updates.push_back({DominatorTree::Insert, BB, NewBB});
2922  Updates.push_back({DominatorTree::Insert, NewBB, SplitBB});
2923  // BB's successors were moved to SplitBB, update DTU accordingly.
2924  for (auto *Succ : successors(SplitBB)) {
2925  Updates.push_back({DominatorTree::Delete, BB, Succ});
2926  Updates.push_back({DominatorTree::Insert, SplitBB, Succ});
2927  }
2928  DTU->applyUpdatesPermissive(Updates);
2929  return true;
2930  }
2931  return false;
2932 }
2933 
2934 /// Try to propagate a guard from the current BB into one of its predecessors
2935 /// in case if another branch of execution implies that the condition of this
2936 /// guard is always true. Currently we only process the simplest case that
2937 /// looks like:
2938 ///
2939 /// Start:
2940 /// %cond = ...
2941 /// br i1 %cond, label %T1, label %F1
2942 /// T1:
2943 /// br label %Merge
2944 /// F1:
2945 /// br label %Merge
2946 /// Merge:
2947 /// %condGuard = ...
2948 /// call void(i1, ...) @llvm.experimental.guard( i1 %condGuard )[ "deopt"() ]
2949 ///
2950 /// And cond either implies condGuard or !condGuard. In this case all the
2951 /// instructions before the guard can be duplicated in both branches, and the
2952 /// guard is then threaded to one of them.
2954  using namespace PatternMatch;
2955 
2956  // We only want to deal with two predecessors.
2957  BasicBlock *Pred1, *Pred2;
2958  auto PI = pred_begin(BB), PE = pred_end(BB);
2959  if (PI == PE)
2960  return false;
2961  Pred1 = *PI++;
2962  if (PI == PE)
2963  return false;
2964  Pred2 = *PI++;
2965  if (PI != PE)
2966  return false;
2967  if (Pred1 == Pred2)
2968  return false;
2969 
2970  // Try to thread one of the guards of the block.
2971  // TODO: Look up deeper than to immediate predecessor?
2972  auto *Parent = Pred1->getSinglePredecessor();
2973  if (!Parent || Parent != Pred2->getSinglePredecessor())
2974  return false;
2975 
2976  if (auto *BI = dyn_cast<BranchInst>(Parent->getTerminator()))
2977  for (auto &I : *BB)
2978  if (isGuard(&I) && threadGuard(BB, cast<IntrinsicInst>(&I), BI))
2979  return true;
2980 
2981  return false;
2982 }
2983 
2984 /// Try to propagate the guard from BB which is the lower block of a diamond
2985 /// to one of its branches, in case if diamond's condition implies guard's
2986 /// condition.
2988  BranchInst *BI) {
2989  assert(BI->getNumSuccessors() == 2 && "Wrong number of successors?");
2990  assert(BI->isConditional() && "Unconditional branch has 2 successors?");
2991  Value *GuardCond = Guard->getArgOperand(0);
2992  Value *BranchCond = BI->getCondition();
2993  BasicBlock *TrueDest = BI->getSuccessor(0);
2994  BasicBlock *FalseDest = BI->getSuccessor(1);
2995 
2996  auto &DL = BB->getModule()->getDataLayout();
2997  bool TrueDestIsSafe = false;
2998  bool FalseDestIsSafe = false;
2999 
3000  // True dest is safe if BranchCond => GuardCond.
3001  auto Impl = isImpliedCondition(BranchCond, GuardCond, DL);
3002  if (Impl && *Impl)
3003  TrueDestIsSafe = true;
3004  else {
3005  // False dest is safe if !BranchCond => GuardCond.
3006  Impl = isImpliedCondition(BranchCond, GuardCond, DL, /* LHSIsTrue */ false);
3007  if (Impl && *Impl)
3008  FalseDestIsSafe = true;
3009  }
3010 
3011  if (!TrueDestIsSafe && !FalseDestIsSafe)
3012  return false;
3013 
3014  BasicBlock *PredUnguardedBlock = TrueDestIsSafe ? TrueDest : FalseDest;
3015  BasicBlock *PredGuardedBlock = FalseDestIsSafe ? TrueDest : FalseDest;
3016 
3017  ValueToValueMapTy UnguardedMapping, GuardedMapping;
3018  Instruction *AfterGuard = Guard->getNextNode();
3019  unsigned Cost =
3020  getJumpThreadDuplicationCost(TTI, BB, AfterGuard, BBDupThreshold);
3021  if (Cost > BBDupThreshold)
3022  return false;
3023  // Duplicate all instructions before the guard and the guard itself to the
3024  // branch where implication is not proved.
3026  BB, PredGuardedBlock, AfterGuard, GuardedMapping, *DTU);
3027  assert(GuardedBlock && "Could not create the guarded block?");
3028  // Duplicate all instructions before the guard in the unguarded branch.
3029  // Since we have successfully duplicated the guarded block and this block
3030  // has fewer instructions, we expect it to succeed.
3032  BB, PredUnguardedBlock, Guard, UnguardedMapping, *DTU);
3033  assert(UnguardedBlock && "Could not create the unguarded block?");
3034  LLVM_DEBUG(dbgs() << "Moved guard " << *Guard << " to block "
3035  << GuardedBlock->getName() << "\n");
3036  // Some instructions before the guard may still have uses. For them, we need
3037  // to create Phi nodes merging their copies in both guarded and unguarded
3038  // branches. Those instructions that have no uses can be just removed.
3040  for (auto BI = BB->begin(); &*BI != AfterGuard; ++BI)
3041  if (!isa<PHINode>(&*BI))
3042  ToRemove.push_back(&*BI);
3043 
3044  Instruction *InsertionPoint = &*BB->getFirstInsertionPt();
3045  assert(InsertionPoint && "Empty block?");
3046  // Substitute with Phis & remove.
3047  for (auto *Inst : reverse(ToRemove)) {
3048  if (!Inst->use_empty()) {
3049  PHINode *NewPN = PHINode::Create(Inst->getType(), 2);
3050  NewPN->addIncoming(UnguardedMapping[Inst], UnguardedBlock);
3051  NewPN->addIncoming(GuardedMapping[Inst], GuardedBlock);
3052  NewPN->insertBefore(InsertionPoint);
3053  Inst->replaceAllUsesWith(NewPN);
3054  }
3055  Inst->eraseFromParent();
3056  }
3057  return true;
3058 }
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:1510
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:2461
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:2709
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:2718
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:4595
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:1726
llvm::BranchProbability::getNumerator
uint32_t getNumerator() const
Definition: BranchProbability.h:64
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:6670
llvm::JumpThreadingPass::processBranchOnXOR
bool processBranchOnXOR(BinaryOperator *BO)
processBranchOnXOR - We have an otherwise unthreadable conditional branch on a xor instruction in the...
Definition: JumpThreading.cpp:1826
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:5267
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:988
llvm::PatternMatch::m_CombineOr
match_combine_or< LTy, RTy > m_CombineOr(const LTy &L, const RTy &R)
Combine two pattern matchers matching L || R.
Definition: PatternMatch.h:210
llvm::TargetTransformInfo
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
Definition: TargetTransformInfo.h:167
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:1797
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:2108
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:1573
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:3190
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:5560
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:61
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:224
llvm::PHINode::setIncomingValue
void setIncomingValue(unsigned i, Value *V)
Definition: Instructions.h:2763
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:2311
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:1368
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:2590
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:2350
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:1607
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:518
llvm::PHINode::getIncomingValue
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
Definition: Instructions.h:2760
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:230
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:2849
llvm::PatternMatch::m_ConstantInt
class_match< ConstantInt > m_ConstantInt()
Match an arbitrary ConstantInt and ignore it.
Definition: PatternMatch.h:145
llvm::Instruction
Definition: Instruction.h:42
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:6460
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:1769
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:919
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:1402
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:2792
llvm::PHINode::getNumIncomingValues
unsigned getNumIncomingValues() const
Return the number of incoming edges.
Definition: Instructions.h:2756
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:1437
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:2853
llvm::LoadInst::getSyncScopeID
SyncScope::ID getSyncScopeID() const
Returns the synchronization scope ID of this load instruction.
Definition: Instructions.h:243
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:3180
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:2423
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:1186
llvm::TargetLibraryInfoWrapperPass
Definition: TargetLibraryInfo.h:468
uint64_t
llvm::TargetTransformInfoWrapperPass
Wrapper pass for TargetTransformInfo.
Definition: TargetTransformInfo.h:2517
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:2567
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:2814
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:3155
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:2292
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:1382
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:1672
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:2002
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:1737
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:3177
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:2953
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:261
llvm::BlockAddress
The address of a basic block.
Definition: Constants.h:848
llvm::Sched::Source
@ Source
Definition: TargetLowering.h:99
llvm::ArrayRef
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: APInt.h:32
llvm::isInstructionTriviallyDead
bool isInstructionTriviallyDead(Instruction *I, const TargetLibraryInfo *TLI=nullptr)
Return true if the result produced by the instruction is not used, and the instruction will return.
Definition: Local.cpp:395
llvm::LoopInfo
Definition: LoopInfo.h:1086
llvm::Constant::removeDeadConstantUsers
void removeDeadConstantUsers() const
If there are any dead constant users dangling off of this constant, remove them.
Definition: Constants.cpp:742
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:1614
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:1962
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:2987
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:214
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:217
llvm::JumpThreadingPass::threadThroughTwoBasicBlocks
void threadThroughTwoBasicBlocks(BasicBlock *PredPredBB, BasicBlock *PredBB, BasicBlock *BB, BasicBlock *SuccBB)
Definition: JumpThreading.cpp:2245
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:29
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:233
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:176
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:874
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:1941
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:867
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:1613
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:3335
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:344
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:2706
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:5298
Casting.h
llvm::Instruction::setAAMetadata
void setAAMetadata(const AAMDNodes &N)
Sets the AA metadata on this instruction from the AAMDNodes structure.
Definition: Metadata.cpp:1411
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:3641
llvm::BranchProbability::getCompl
BranchProbability getCompl() const
Definition: BranchProbability.h:68
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:2013
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:204
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:5407
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:1807
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:2780
TargetTransformInfo.h
llvm::PHINode
Definition: Instructions.h:2664
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:1474
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:262
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:3243
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:509
llvm::BranchInst
Conditional or Unconditional Branch instruction.
Definition: Instructions.h:3099
llvm::ConstantFoldInstruction
Constant * ConstantFoldInstruction(Instruction *I, const DataLayout &DL, const TargetLibraryInfo *TLI=nullptr)
ConstantFoldInstruction - Try to constant fold the specified instruction.
Definition: ConstantFolding.cpp:1095
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:2059
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:61
Value.h
InitializePasses.h
llvm::BasicBlock::isEHPad
bool isEHPad() const
Return true if this basic block is an exception handling block.
Definition: BasicBlock.h: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:1794
llvm::BranchInst::isConditional
bool isConditional() const
Definition: Instructions.h:3178
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:2549
llvm::BranchInst::getSuccessor
BasicBlock * getSuccessor(unsigned i) const
Definition: Instructions.h:3192
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:37