Coverage Report

Created: 2019-07-24 05:18

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