Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Transforms/Scalar/SCCP.cpp
Line
Count
Source (jump to first uncovered line)
1
//===- SCCP.cpp - Sparse Conditional Constant Propagation -----------------===//
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 sparse conditional constant propagation and merging:
10
//
11
// Specifically, this:
12
//   * Assumes values are constant unless proven otherwise
13
//   * Assumes BasicBlocks are dead unless proven otherwise
14
//   * Proves values to be constant, and replaces them with constants
15
//   * Proves conditional branches to be unconditional
16
//
17
//===----------------------------------------------------------------------===//
18
19
#include "llvm/Transforms/Scalar/SCCP.h"
20
#include "llvm/ADT/ArrayRef.h"
21
#include "llvm/ADT/DenseMap.h"
22
#include "llvm/ADT/DenseSet.h"
23
#include "llvm/ADT/MapVector.h"
24
#include "llvm/ADT/PointerIntPair.h"
25
#include "llvm/ADT/STLExtras.h"
26
#include "llvm/ADT/SmallPtrSet.h"
27
#include "llvm/ADT/SmallVector.h"
28
#include "llvm/ADT/Statistic.h"
29
#include "llvm/Analysis/ConstantFolding.h"
30
#include "llvm/Analysis/GlobalsModRef.h"
31
#include "llvm/Analysis/TargetLibraryInfo.h"
32
#include "llvm/Transforms/Utils/Local.h"
33
#include "llvm/Analysis/ValueLattice.h"
34
#include "llvm/Analysis/ValueLatticeUtils.h"
35
#include "llvm/IR/BasicBlock.h"
36
#include "llvm/IR/CallSite.h"
37
#include "llvm/IR/Constant.h"
38
#include "llvm/IR/Constants.h"
39
#include "llvm/IR/DataLayout.h"
40
#include "llvm/IR/DerivedTypes.h"
41
#include "llvm/IR/Function.h"
42
#include "llvm/IR/GlobalVariable.h"
43
#include "llvm/IR/InstVisitor.h"
44
#include "llvm/IR/InstrTypes.h"
45
#include "llvm/IR/Instruction.h"
46
#include "llvm/IR/Instructions.h"
47
#include "llvm/IR/Module.h"
48
#include "llvm/IR/PassManager.h"
49
#include "llvm/IR/Type.h"
50
#include "llvm/IR/User.h"
51
#include "llvm/IR/Value.h"
52
#include "llvm/Pass.h"
53
#include "llvm/Support/Casting.h"
54
#include "llvm/Support/Debug.h"
55
#include "llvm/Support/ErrorHandling.h"
56
#include "llvm/Support/raw_ostream.h"
57
#include "llvm/Transforms/Scalar.h"
58
#include "llvm/Transforms/Utils/PredicateInfo.h"
59
#include <cassert>
60
#include <utility>
61
#include <vector>
62
63
using namespace llvm;
64
65
#define DEBUG_TYPE "sccp"
66
67
STATISTIC(NumInstRemoved, "Number of instructions removed");
68
STATISTIC(NumDeadBlocks , "Number of basic blocks unreachable");
69
70
STATISTIC(IPNumInstRemoved, "Number of instructions removed by IPSCCP");
71
STATISTIC(IPNumArgsElimed ,"Number of arguments constant propagated by IPSCCP");
72
STATISTIC(IPNumGlobalConst, "Number of globals found to be constant by IPSCCP");
73
74
namespace {
75
76
/// LatticeVal class - This class represents the different lattice values that
77
/// an LLVM value may occupy.  It is a simple class with value semantics.
78
///
79
class LatticeVal {
80
  enum LatticeValueTy {
81
    /// unknown - This LLVM Value has no known value yet.
82
    unknown,
83
84
    /// constant - This LLVM Value has a specific constant value.
85
    constant,
86
87
    /// forcedconstant - This LLVM Value was thought to be undef until
88
    /// ResolvedUndefsIn.  This is treated just like 'constant', but if merged
89
    /// with another (different) constant, it goes to overdefined, instead of
90
    /// asserting.
91
    forcedconstant,
92
93
    /// overdefined - This instruction is not known to be constant, and we know
94
    /// it has a value.
95
    overdefined
96
  };
97
98
  /// Val: This stores the current lattice value along with the Constant* for
99
  /// the constant if this is a 'constant' or 'forcedconstant' value.
100
  PointerIntPair<Constant *, 2, LatticeValueTy> Val;
101
102
203M
  LatticeValueTy getLatticeValue() const {
103
203M
    return Val.getInt();
104
203M
  }
105
106
public:
107
92.6M
  LatticeVal() : Val(nullptr, unknown) {}
108
109
47.7M
  bool isUnknown() const { return getLatticeValue() == unknown; }
110
111
14.4M
  bool isConstant() const {
112
14.4M
    return getLatticeValue() == constant || 
getLatticeValue() == forcedconstant10.4M
;
113
14.4M
  }
114
115
128M
  bool isOverdefined() const { return getLatticeValue() == overdefined; }
116
117
6.17M
  Constant *getConstant() const {
118
6.17M
    assert(isConstant() && "Cannot get the constant of a non-constant!");
119
6.17M
    return Val.getPointer();
120
6.17M
  }
121
122
  /// markOverdefined - Return true if this is a change in status.
123
27.7M
  bool markOverdefined() {
124
27.7M
    if (isOverdefined())
125
5.91M
      return false;
126
21.7M
127
21.7M
    Val.setInt(overdefined);
128
21.7M
    return true;
129
21.7M
  }
130
131
  /// markConstant - Return true if this is a change in status.
132
2.84M
  bool markConstant(Constant *V) {
133
2.84M
    if (getLatticeValue() == constant) { // Constant but not forcedconstant.
134
123k
      assert(getConstant() == V && "Marking constant with different value");
135
123k
      return false;
136
123k
    }
137
2.71M
138
2.71M
    
if (2.71M
isUnknown()2.71M
) {
139
2.71M
      Val.setInt(constant);
140
2.71M
      assert(V && "Marking constant with NULL");
141
2.71M
      Val.setPointer(V);
142
18.4E
    } else {
143
18.4E
      assert(getLatticeValue() == forcedconstant &&
144
18.4E
             "Cannot move from overdefined to constant!");
145
18.4E
      // Stay at forcedconstant if the constant is the same.
146
18.4E
      if (V == getConstant()) 
return false0
;
147
18.4E
148
18.4E
      // Otherwise, we go to overdefined.  Assumptions made based on the
149
18.4E
      // forced value are possibly wrong.  Assuming this is another constant
150
18.4E
      // could expose a contradiction.
151
18.4E
      Val.setInt(overdefined);
152
18.4E
    }
153
2.71M
    return true;
154
2.71M
  }
155
156
  /// getConstantInt - If this is a constant with a ConstantInt value, return it
157
  /// otherwise return null.
158
5.00M
  ConstantInt *getConstantInt() const {
159
5.00M
    if (isConstant())
160
177k
      return dyn_cast<ConstantInt>(getConstant());
161
4.82M
    return nullptr;
162
4.82M
  }
163
164
  /// getBlockAddress - If this is a constant with a BlockAddress value, return
165
  /// it, otherwise return null.
166
18
  BlockAddress *getBlockAddress() const {
167
18
    if (isConstant())
168
4
      return dyn_cast<BlockAddress>(getConstant());
169
14
    return nullptr;
170
14
  }
171
172
18
  void markForcedConstant(Constant *V) {
173
18
    assert(isUnknown() && "Can't force a defined value!");
174
18
    Val.setInt(forcedconstant);
175
18
    Val.setPointer(V);
176
18
  }
177
178
5.98M
  ValueLatticeElement toValueLattice() const {
179
5.98M
    if (isOverdefined())
180
3.45M
      return ValueLatticeElement::getOverdefined();
181
2.53M
    if (isConstant())
182
2.36M
      return ValueLatticeElement::get(getConstant());
183
162k
    return ValueLatticeElement();
184
162k
  }
185
};
186
187
//===----------------------------------------------------------------------===//
188
//
189
/// SCCPSolver - This class is a general purpose solver for Sparse Conditional
190
/// Constant Propagation.
191
///
192
class SCCPSolver : public InstVisitor<SCCPSolver> {
193
  const DataLayout &DL;
194
  const TargetLibraryInfo *TLI;
195
  SmallPtrSet<BasicBlock *, 8> BBExecutable; // The BBs that are executable.
196
  DenseMap<Value *, LatticeVal> ValueState;  // The state each value is in.
197
  // The state each parameter is in.
198
  DenseMap<Value *, ValueLatticeElement> ParamState;
199
200
  /// StructValueState - This maintains ValueState for values that have
201
  /// StructType, for example for formal arguments, calls, insertelement, etc.
202
  DenseMap<std::pair<Value *, unsigned>, LatticeVal> StructValueState;
203
204
  /// GlobalValue - If we are tracking any values for the contents of a global
205
  /// variable, we keep a mapping from the constant accessor to the element of
206
  /// the global, to the currently known value.  If the value becomes
207
  /// overdefined, it's entry is simply removed from this map.
208
  DenseMap<GlobalVariable *, LatticeVal> TrackedGlobals;
209
210
  /// TrackedRetVals - If we are tracking arguments into and the return
211
  /// value out of a function, it will have an entry in this map, indicating
212
  /// what the known return value for the function is.
213
  MapVector<Function *, LatticeVal> TrackedRetVals;
214
215
  /// TrackedMultipleRetVals - Same as TrackedRetVals, but used for functions
216
  /// that return multiple values.
217
  MapVector<std::pair<Function *, unsigned>, LatticeVal> TrackedMultipleRetVals;
218
219
  /// MRVFunctionsTracked - Each function in TrackedMultipleRetVals is
220
  /// represented here for efficient lookup.
221
  SmallPtrSet<Function *, 16> MRVFunctionsTracked;
222
223
  /// MustTailFunctions - Each function here is a callee of non-removable
224
  /// musttail call site.
225
  SmallPtrSet<Function *, 16> MustTailCallees;
226
227
  /// TrackingIncomingArguments - This is the set of functions for whose
228
  /// arguments we make optimistic assumptions about and try to prove as
229
  /// constants.
230
  SmallPtrSet<Function *, 16> TrackingIncomingArguments;
231
232
  /// The reason for two worklists is that overdefined is the lowest state
233
  /// on the lattice, and moving things to overdefined as fast as possible
234
  /// makes SCCP converge much faster.
235
  ///
236
  /// By having a separate worklist, we accomplish this because everything
237
  /// possibly overdefined will become overdefined at the soonest possible
238
  /// point.
239
  SmallVector<Value *, 64> OverdefinedInstWorkList;
240
  SmallVector<Value *, 64> InstWorkList;
241
242
  // The BasicBlock work list
243
  SmallVector<BasicBlock *, 64>  BBWorkList;
244
245
  /// KnownFeasibleEdges - Entries in this set are edges which have already had
246
  /// PHI nodes retriggered.
247
  using Edge = std::pair<BasicBlock *, BasicBlock *>;
248
  DenseSet<Edge> KnownFeasibleEdges;
249
250
  DenseMap<Function *, AnalysisResultsForFn> AnalysisResults;
251
  DenseMap<Value *, SmallPtrSet<User *, 2>> AdditionalUsers;
252
253
public:
254
590k
  void addAnalysis(Function &F, AnalysisResultsForFn A) {
255
590k
    AnalysisResults.insert({&F, std::move(A)});
256
590k
  }
257
258
14.1M
  const PredicateBase *getPredicateInfoFor(Instruction *I) {
259
14.1M
    auto A = AnalysisResults.find(I->getParent()->getParent());
260
14.1M
    if (A == AnalysisResults.end())
261
0
      return nullptr;
262
14.1M
    return A->second.PredInfo->getPredicateInfoFor(I);
263
14.1M
  }
264
265
590k
  DomTreeUpdater getDTU(Function &F) {
266
590k
    auto A = AnalysisResults.find(&F);
267
590k
    assert(A != AnalysisResults.end() && "Need analysis results for function.");
268
590k
    return {A->second.DT, A->second.PDT, DomTreeUpdater::UpdateStrategy::Lazy};
269
590k
  }
270
271
  SCCPSolver(const DataLayout &DL, const TargetLibraryInfo *tli)
272
480k
      : DL(DL), TLI(tli) {}
273
274
  /// MarkBlockExecutable - This method can be used by clients to mark all of
275
  /// the blocks that are known to be intrinsically live in the processed unit.
276
  ///
277
  /// This returns true if the block was not considered live before.
278
7.83M
  bool MarkBlockExecutable(BasicBlock *BB) {
279
7.83M
    if (!BBExecutable.insert(BB).second)
280
2.52M
      return false;
281
5.31M
    LLVM_DEBUG(dbgs() << "Marking Block Executable: " << BB->getName() << '\n');
282
5.31M
    BBWorkList.push_back(BB);  // Add the block to the work list!
283
5.31M
    return true;
284
5.31M
  }
285
286
  /// TrackValueOfGlobalVariable - Clients can use this method to
287
  /// inform the SCCPSolver that it should track loads and stores to the
288
  /// specified global variable if it can.  This is only legal to call if
289
  /// performing Interprocedural SCCP.
290
4.79k
  void TrackValueOfGlobalVariable(GlobalVariable *GV) {
291
4.79k
    // We only track the contents of scalar globals.
292
4.79k
    if (GV->getValueType()->isSingleValueType()) {
293
4.77k
      LatticeVal &IV = TrackedGlobals[GV];
294
4.77k
      if (!isa<UndefValue>(GV->getInitializer()))
295
4.77k
        IV.markConstant(GV->getInitializer());
296
4.77k
    }
297
4.79k
  }
298
299
  /// AddTrackedFunction - If the SCCP solver is supposed to track calls into
300
  /// and out of the specified function (which cannot have its address taken),
301
  /// this method must be called.
302
98.5k
  void AddTrackedFunction(Function *F) {
303
98.5k
    // Add an entry, F -> undef.
304
98.5k
    if (auto *STy = dyn_cast<StructType>(F->getReturnType())) {
305
866
      MRVFunctionsTracked.insert(F);
306
2.49k
      for (unsigned i = 0, e = STy->getNumElements(); i != e; 
++i1.62k
)
307
1.62k
        TrackedMultipleRetVals.insert(std::make_pair(std::make_pair(F, i),
308
1.62k
                                                     LatticeVal()));
309
866
    } else
310
97.7k
      TrackedRetVals.insert(std::make_pair(F, LatticeVal()));
311
98.5k
  }
312
313
  /// AddMustTailCallee - If the SCCP solver finds that this function is called
314
  /// from non-removable musttail call site.
315
5
  void AddMustTailCallee(Function *F) {
316
5
    MustTailCallees.insert(F);
317
5
  }
318
319
  /// Returns true if the given function is called from non-removable musttail
320
  /// call site.
321
759
  bool isMustTailCallee(Function *F) {
322
759
    return MustTailCallees.count(F);
323
759
  }
324
325
25.3k
  void AddArgumentTrackedFunction(Function *F) {
326
25.3k
    TrackingIncomingArguments.insert(F);
327
25.3k
  }
328
329
  /// Returns true if the given function is in the solver's set of
330
  /// argument-tracked functions.
331
7.65k
  bool isArgumentTrackedFunction(Function *F) {
332
7.65k
    return TrackingIncomingArguments.count(F);
333
7.65k
  }
334
335
  /// Solve - Solve for constants and executable blocks.
336
  void Solve();
337
338
  /// ResolvedUndefsIn - While solving the dataflow for a function, we assume
339
  /// that branches on undef values cannot reach any of their successors.
340
  /// However, this is not a safe assumption.  After we solve dataflow, this
341
  /// method should be use to handle this.  If this returns true, the solver
342
  /// should be rerun.
343
  bool ResolvedUndefsIn(Function &F);
344
345
6.52M
  bool isBlockExecutable(BasicBlock *BB) const {
346
6.52M
    return BBExecutable.count(BB);
347
6.52M
  }
348
349
  // isEdgeFeasible - Return true if the control flow edge from the 'From' basic
350
  // block to the 'To' basic block is currently feasible.
351
  bool isEdgeFeasible(BasicBlock *From, BasicBlock *To);
352
353
76.3k
  std::vector<LatticeVal> getStructLatticeValueFor(Value *V) const {
354
76.3k
    std::vector<LatticeVal> StructValues;
355
76.3k
    auto *STy = dyn_cast<StructType>(V->getType());
356
76.3k
    assert(STy && "getStructLatticeValueFor() can be called only on structs");
357
222k
    for (unsigned i = 0, e = STy->getNumElements(); i != e; 
++i146k
) {
358
146k
      auto I = StructValueState.find(std::make_pair(V, i));
359
146k
      assert(I != StructValueState.end() && "Value not in valuemap!");
360
146k
      StructValues.push_back(I->second);
361
146k
    }
362
76.3k
    return StructValues;
363
76.3k
  }
364
365
20.5M
  const LatticeVal &getLatticeValueFor(Value *V) const {
366
20.5M
    assert(!V->getType()->isStructTy() &&
367
20.5M
           "Should use getStructLatticeValueFor");
368
20.5M
    DenseMap<Value *, LatticeVal>::const_iterator I = ValueState.find(V);
369
20.5M
    assert(I != ValueState.end() &&
370
20.5M
           "V not found in ValueState nor Paramstate map!");
371
20.5M
    return I->second;
372
20.5M
  }
373
374
  /// getTrackedRetVals - Get the inferred return value map.
375
13.6k
  const MapVector<Function*, LatticeVal> &getTrackedRetVals() {
376
13.6k
    return TrackedRetVals;
377
13.6k
  }
378
379
  /// getTrackedGlobals - Get and return the set of inferred initializers for
380
  /// global variables.
381
13.6k
  const DenseMap<GlobalVariable*, LatticeVal> &getTrackedGlobals() {
382
13.6k
    return TrackedGlobals;
383
13.6k
  }
384
385
  /// getMRVFunctionsTracked - Get the set of functions which return multiple
386
  /// values tracked by the pass.
387
13.6k
  const SmallPtrSet<Function *, 16> getMRVFunctionsTracked() {
388
13.6k
    return MRVFunctionsTracked;
389
13.6k
  }
390
391
  /// getMustTailCallees - Get the set of functions which are called
392
  /// from non-removable musttail call sites.
393
0
  const SmallPtrSet<Function *, 16> getMustTailCallees() {
394
0
    return MustTailCallees;
395
0
  }
396
397
  /// markOverdefined - Mark the specified value overdefined.  This
398
  /// works with both scalars and structs.
399
23.7M
  void markOverdefined(Value *V) {
400
23.7M
    if (auto *STy = dyn_cast<StructType>(V->getType()))
401
374k
      
for (unsigned i = 0, e = STy->getNumElements(); 131k
i != e;
++i243k
)
402
243k
        markOverdefined(getStructValueState(V, i), V);
403
23.5M
    else
404
23.5M
      markOverdefined(ValueState[V], V);
405
23.7M
  }
406
407
  // isStructLatticeConstant - Return true if all the lattice values
408
  // corresponding to elements of the structure are not overdefined,
409
  // false otherwise.
410
866
  bool isStructLatticeConstant(Function *F, StructType *STy) {
411
915
    for (unsigned i = 0, e = STy->getNumElements(); i != e; 
++i49
) {
412
889
      const auto &It = TrackedMultipleRetVals.find(std::make_pair(F, i));
413
889
      assert(It != TrackedMultipleRetVals.end());
414
889
      LatticeVal LV = It->second;
415
889
      if (LV.isOverdefined())
416
840
        return false;
417
889
    }
418
866
    
return true26
;
419
866
  }
420
421
private:
422
  // pushToWorkList - Helper for markConstant/markForcedConstant/markOverdefined
423
22.8M
  void pushToWorkList(LatticeVal &IV, Value *V) {
424
22.8M
    if (IV.isOverdefined())
425
21.7M
      return OverdefinedInstWorkList.push_back(V);
426
1.07M
    InstWorkList.push_back(V);
427
1.07M
  }
428
429
  // markConstant - Make a value be marked as "constant".  If the value
430
  // is not already a constant, add it to the instruction work list so that
431
  // the users of the instruction are updated later.
432
1.19M
  bool markConstant(LatticeVal &IV, Value *V, Constant *C) {
433
1.19M
    if (!IV.markConstant(C)) 
return false123k
;
434
1.07M
    LLVM_DEBUG(dbgs() << "markConstant: " << *C << ": " << *V << '\n');
435
1.07M
    pushToWorkList(IV, V);
436
1.07M
    return true;
437
1.07M
  }
438
439
649k
  bool markConstant(Value *V, Constant *C) {
440
649k
    assert(!V->getType()->isStructTy() && "structs should use mergeInValue");
441
649k
    return markConstant(ValueState[V], V, C);
442
649k
  }
443
444
18
  void markForcedConstant(Value *V, Constant *C) {
445
18
    assert(!V->getType()->isStructTy() && "structs should use mergeInValue");
446
18
    LatticeVal &IV = ValueState[V];
447
18
    IV.markForcedConstant(C);
448
18
    LLVM_DEBUG(dbgs() << "markForcedConstant: " << *C << ": " << *V << '\n');
449
18
    pushToWorkList(IV, V);
450
18
  }
451
452
  // markOverdefined - Make a value be marked as "overdefined". If the
453
  // value is not already overdefined, add it to the overdefined instruction
454
  // work list so that the users of the instruction are updated later.
455
27.7M
  bool markOverdefined(LatticeVal &IV, Value *V) {
456
27.7M
    if (!IV.markOverdefined()) 
return false5.91M
;
457
21.7M
458
21.7M
    LLVM_DEBUG(dbgs() << "markOverdefined: ";
459
21.7M
               if (auto *F = dyn_cast<Function>(V)) dbgs()
460
21.7M
               << "Function '" << F->getName() << "'\n";
461
21.7M
               else dbgs() << *V << '\n');
462
21.7M
    // Only instructions go on the work list
463
21.7M
    pushToWorkList(IV, V);
464
21.7M
    return true;
465
21.7M
  }
466
467
2.18M
  bool mergeInValue(LatticeVal &IV, Value *V, LatticeVal MergeWithV) {
468
2.18M
    if (IV.isOverdefined() || 
MergeWithV.isUnknown()1.34M
)
469
1.08M
      return false; // Noop.
470
1.10M
    if (MergeWithV.isOverdefined())
471
808k
      return markOverdefined(IV, V);
472
299k
    if (IV.isUnknown())
473
249k
      return markConstant(IV, V, MergeWithV.getConstant());
474
50.0k
    if (IV.getConstant() != MergeWithV.getConstant())
475
4.17k
      return markOverdefined(IV, V);
476
45.8k
    return false;
477
45.8k
  }
478
479
1.14M
  bool mergeInValue(Value *V, LatticeVal MergeWithV) {
480
1.14M
    assert(!V->getType()->isStructTy() &&
481
1.14M
           "non-structs should use markConstant");
482
1.14M
    return mergeInValue(ValueState[V], V, MergeWithV);
483
1.14M
  }
484
485
  /// getValueState - Return the LatticeVal object that corresponds to the
486
  /// value.  This function handles the case when the value hasn't been seen yet
487
  /// by properly seeding constants etc.
488
72.2M
  LatticeVal &getValueState(Value *V) {
489
72.2M
    assert(!V->getType()->isStructTy() && "Should use getStructValueState");
490
72.2M
491
72.2M
    std::pair<DenseMap<Value*, LatticeVal>::iterator, bool> I =
492
72.2M
      ValueState.insert(std::make_pair(V, LatticeVal()));
493
72.2M
    LatticeVal &LV = I.first->second;
494
72.2M
495
72.2M
    if (!I.second)
496
68.5M
      return LV;  // Common case, already in the map.
497
3.79M
498
3.79M
    if (auto *C = dyn_cast<Constant>(V)) {
499
1.53M
      // Undef values remain unknown.
500
1.53M
      if (!isa<UndefValue>(V))
501
1.53M
        LV.markConstant(C);          // Constants are constant
502
1.53M
    }
503
3.79M
504
3.79M
    // All others are underdefined by default.
505
3.79M
    return LV;
506
3.79M
  }
507
508
546k
  ValueLatticeElement &getParamState(Value *V) {
509
546k
    assert(!V->getType()->isStructTy() && "Should use getStructValueState");
510
546k
511
546k
    std::pair<DenseMap<Value*, ValueLatticeElement>::iterator, bool>
512
546k
        PI = ParamState.insert(std::make_pair(V, ValueLatticeElement()));
513
546k
    ValueLatticeElement &LV = PI.first->second;
514
546k
    if (PI.second)
515
49.8k
      LV = getValueState(V).toValueLattice();
516
546k
517
546k
    return LV;
518
546k
  }
519
520
  /// getStructValueState - Return the LatticeVal object that corresponds to the
521
  /// value/field pair.  This function handles the case when the value hasn't
522
  /// been seen yet by properly seeding constants etc.
523
700k
  LatticeVal &getStructValueState(Value *V, unsigned i) {
524
700k
    assert(V->getType()->isStructTy() && "Should use getValueState");
525
700k
    assert(i < cast<StructType>(V->getType())->getNumElements() &&
526
700k
           "Invalid element #");
527
700k
528
700k
    std::pair<DenseMap<std::pair<Value*, unsigned>, LatticeVal>::iterator,
529
700k
              bool> I = StructValueState.insert(
530
700k
                        std::make_pair(std::make_pair(V, i), LatticeVal()));
531
700k
    LatticeVal &LV = I.first->second;
532
700k
533
700k
    if (!I.second)
534
551k
      return LV;  // Common case, already in the map.
535
149k
536
149k
    if (auto *C = dyn_cast<Constant>(V)) {
537
2.98k
      Constant *Elt = C->getAggregateElement(i);
538
2.98k
539
2.98k
      if (!Elt)
540
0
        LV.markOverdefined();      // Unknown sort of constant.
541
2.98k
      else if (isa<UndefValue>(Elt))
542
2.94k
        ; // Undef values remain unknown.
543
36
      else
544
36
        LV.markConstant(Elt);      // Constants are constant.
545
2.98k
    }
546
149k
547
149k
    // All others are underdefined by default.
548
149k
    return LV;
549
149k
  }
550
551
  /// markEdgeExecutable - Mark a basic block as executable, adding it to the BB
552
  /// work list if it is not already executable.
553
11.1M
  bool markEdgeExecutable(BasicBlock *Source, BasicBlock *Dest) {
554
11.1M
    if (!KnownFeasibleEdges.insert(Edge(Source, Dest)).second)
555
4.57M
      return false;  // This edge is already known to be executable!
556
6.53M
557
6.53M
    if (!MarkBlockExecutable(Dest)) {
558
2.27M
      // If the destination is already executable, we just made an *edge*
559
2.27M
      // feasible that wasn't before.  Revisit the PHI nodes in the block
560
2.27M
      // because they have potentially new operands.
561
2.27M
      LLVM_DEBUG(dbgs() << "Marking Edge Executable: " << Source->getName()
562
2.27M
                        << " -> " << Dest->getName() << '\n');
563
2.27M
564
2.27M
      for (PHINode &PN : Dest->phis())
565
1.78M
        visitPHINode(PN);
566
2.27M
    }
567
6.53M
    return true;
568
6.53M
  }
569
570
  // getFeasibleSuccessors - Return a vector of booleans to indicate which
571
  // successors are reachable from a given terminator instruction.
572
  void getFeasibleSuccessors(Instruction &TI, SmallVectorImpl<bool> &Succs);
573
574
  // OperandChangedState - This method is invoked on all of the users of an
575
  // instruction that was just changed state somehow.  Based on this
576
  // information, we need to update the specified user of this instruction.
577
31.9M
  void OperandChangedState(Instruction *I) {
578
31.9M
    if (BBExecutable.count(I->getParent()))   // Inst is executable?
579
29.0M
      visit(*I);
580
31.9M
  }
581
582
  // Add U as additional user of V.
583
35.4k
  void addAdditionalUser(Value *V, User *U) {
584
35.4k
    auto Iter = AdditionalUsers.insert({V, {}});
585
35.4k
    Iter.first->second.insert(U);
586
35.4k
  }
587
588
  // Mark I's users as changed, including AdditionalUsers.
589
21.9M
  void markUsersAsChanged(Value *I) {
590
21.9M
    for (User *U : I->users())
591
31.9M
      if (auto *UI = dyn_cast<Instruction>(U))
592
31.9M
        OperandChangedState(UI);
593
21.9M
594
21.9M
    auto Iter = AdditionalUsers.find(I);
595
21.9M
    if (Iter != AdditionalUsers.end()) {
596
21.6k
      for (User *U : Iter->second)
597
21.6k
        if (auto *UI = dyn_cast<Instruction>(U))
598
21.6k
          OperandChangedState(UI);
599
21.6k
    }
600
21.9M
  }
601
602
private:
603
  friend class InstVisitor<SCCPSolver>;
604
605
  // visit implementations - Something changed in this instruction.  Either an
606
  // operand made a transition, or the instruction is newly executable.  Change
607
  // the value type of I to reflect these changes if appropriate.
608
  void visitPHINode(PHINode &I);
609
610
  // Terminators
611
612
  void visitReturnInst(ReturnInst &I);
613
  void visitTerminator(Instruction &TI);
614
615
  void visitCastInst(CastInst &I);
616
  void visitSelectInst(SelectInst &I);
617
  void visitUnaryOperator(Instruction &I);
618
  void visitBinaryOperator(Instruction &I);
619
  void visitCmpInst(CmpInst &I);
620
  void visitExtractValueInst(ExtractValueInst &EVI);
621
  void visitInsertValueInst(InsertValueInst &IVI);
622
623
4
  void visitCatchSwitchInst(CatchSwitchInst &CPI) {
624
4
    markOverdefined(&CPI);
625
4
    visitTerminator(CPI);
626
4
  }
627
628
  // Instructions that cannot be folded away.
629
630
  void visitStoreInst     (StoreInst &I);
631
  void visitLoadInst      (LoadInst &I);
632
  void visitGetElementPtrInst(GetElementPtrInst &I);
633
634
10.1M
  void visitCallInst      (CallInst &I) {
635
10.1M
    visitCallSite(&I);
636
10.1M
  }
637
638
149k
  void visitInvokeInst    (InvokeInst &II) {
639
149k
    visitCallSite(&II);
640
149k
    visitTerminator(II);
641
149k
  }
642
643
0
  void visitCallBrInst    (CallBrInst &CBI) {
644
0
    visitCallSite(&CBI);
645
0
    visitTerminator(CBI);
646
0
  }
647
648
  void visitCallSite      (CallSite CS);
649
29.4k
  void visitResumeInst    (ResumeInst &I) { /*returns void*/ }
650
76.4k
  void visitUnreachableInst(UnreachableInst &I) { /*returns void*/ }
651
12.2k
  void visitFenceInst     (FenceInst &I) { /*returns void*/ }
652
653
494k
  void visitInstruction(Instruction &I) {
654
494k
    // All the instructions we don't do any special handling for just
655
494k
    // go to overdefined.
656
494k
    LLVM_DEBUG(dbgs() << "SCCP: Don't know how to handle: " << I << '\n');
657
494k
    markOverdefined(&I);
658
494k
  }
659
};
660
661
} // end anonymous namespace
662
663
// getFeasibleSuccessors - Return a vector of booleans to indicate which
664
// successors are reachable from a given terminator instruction.
665
void SCCPSolver::getFeasibleSuccessors(Instruction &TI,
666
6.49M
                                       SmallVectorImpl<bool> &Succs) {
667
6.49M
  Succs.resize(TI.getNumSuccessors());
668
6.49M
  if (auto *BI = dyn_cast<BranchInst>(&TI)) {
669
6.27M
    if (BI->isUnconditional()) {
670
1.82M
      Succs[0] = true;
671
1.82M
      return;
672
1.82M
    }
673
4.44M
674
4.44M
    LatticeVal BCValue = getValueState(BI->getCondition());
675
4.44M
    ConstantInt *CI = BCValue.getConstantInt();
676
4.44M
    if (!CI) {
677
4.30M
      // Overdefined condition variables, and branches on unfoldable constant
678
4.30M
      // conditions, mean the branch could go either way.
679
4.30M
      if (!BCValue.isUnknown())
680
4.28M
        Succs[0] = Succs[1] = true;
681
4.30M
      return;
682
4.30M
    }
683
138k
684
138k
    // Constant condition variables mean the branch can only go a single way.
685
138k
    Succs[CI->isZero()] = true;
686
138k
    return;
687
138k
  }
688
216k
689
216k
  // Unwinding instructions successors are always executable.
690
216k
  if (TI.isExceptionalTerminator()) {
691
149k
    Succs.assign(TI.getNumSuccessors(), true);
692
149k
    return;
693
149k
  }
694
66.2k
695
66.2k
  if (auto *SI = dyn_cast<SwitchInst>(&TI)) {
696
66.2k
    if (!SI->getNumCases()) {
697
1
      Succs[0] = true;
698
1
      return;
699
1
    }
700
66.2k
    LatticeVal SCValue = getValueState(SI->getCondition());
701
66.2k
    ConstantInt *CI = SCValue.getConstantInt();
702
66.2k
703
66.2k
    if (!CI) {   // Overdefined or unknown condition?
704
61.9k
      // All destinations are executable!
705
61.9k
      if (!SCValue.isUnknown())
706
61.8k
        Succs.assign(TI.getNumSuccessors(), true);
707
61.9k
      return;
708
61.9k
    }
709
4.23k
710
4.23k
    Succs[SI->findCaseValue(CI)->getSuccessorIndex()] = true;
711
4.23k
    return;
712
4.23k
  }
713
18
714
18
  // In case of indirect branch and its address is a blockaddress, we mark
715
18
  // the target as executable.
716
18
  if (auto *IBR = dyn_cast<IndirectBrInst>(&TI)) {
717
18
    // Casts are folded by visitCastInst.
718
18
    LatticeVal IBRValue = getValueState(IBR->getAddress());
719
18
    BlockAddress *Addr = IBRValue.getBlockAddress();
720
18
    if (!Addr) {   // Overdefined or unknown condition?
721
14
      // All destinations are executable!
722
14
      if (!IBRValue.isUnknown())
723
13
        Succs.assign(TI.getNumSuccessors(), true);
724
14
      return;
725
14
    }
726
4
727
4
    BasicBlock* T = Addr->getBasicBlock();
728
4
    assert(Addr->getFunction() == T->getParent() &&
729
4
           "Block address of a different function ?");
730
7
    for (unsigned i = 0; i < IBR->getNumSuccessors(); 
++i3
) {
731
7
      // This is the target.
732
7
      if (IBR->getDestination(i) == T) {
733
4
        Succs[i] = true;
734
4
        return;
735
4
      }
736
7
    }
737
4
738
4
    // If we didn't find our destination in the IBR successor list, then we
739
4
    // have undefined behavior. Its ok to assume no successor is executable.
740
4
    
return0
;
741
0
  }
742
0
743
0
  // In case of callbr, we pessimistically assume that all successors are
744
0
  // feasible.
745
0
  if (isa<CallBrInst>(&TI)) {
746
0
    Succs.assign(TI.getNumSuccessors(), true);
747
0
    return;
748
0
  }
749
0
750
0
  LLVM_DEBUG(dbgs() << "Unknown terminator instruction: " << TI << '\n');
751
0
  llvm_unreachable("SCCP: Don't know how to handle this terminator!");
752
0
}
753
754
// isEdgeFeasible - Return true if the control flow edge from the 'From' basic
755
// block to the 'To' basic block is currently feasible.
756
2.87M
bool SCCPSolver::isEdgeFeasible(BasicBlock *From, BasicBlock *To) {
757
2.87M
  // Check if we've called markEdgeExecutable on the edge yet. (We could
758
2.87M
  // be more aggressive and try to consider edges which haven't been marked
759
2.87M
  // yet, but there isn't any need.)
760
2.87M
  return KnownFeasibleEdges.count(Edge(From, To));
761
2.87M
}
762
763
// visit Implementations - Something changed in this instruction, either an
764
// operand made a transition, or the instruction is newly executable.  Change
765
// the value type of I to reflect these changes if appropriate.  This method
766
// makes sure to do the following actions:
767
//
768
// 1. If a phi node merges two constants in, and has conflicting value coming
769
//    from different branches, or if the PHI node merges in an overdefined
770
//    value, then the PHI node becomes overdefined.
771
// 2. If a phi node merges only constants in, and they all agree on value, the
772
//    PHI node becomes a constant value equal to that.
773
// 3. If V <- x (op) y && isConstant(x) && isConstant(y) V = Constant
774
// 4. If V <- x (op) y && (isOverdefined(x) || isOverdefined(y)) V = Overdefined
775
// 5. If V <- MEM or V <- CALL or V <- (unknown) then V = Overdefined
776
// 6. If a conditional branch has a value that is constant, make the selected
777
//    destination executable
778
// 7. If a conditional branch has a value that is overdefined, make all
779
//    successors executable.
780
5.00M
void SCCPSolver::visitPHINode(PHINode &PN) {
781
5.00M
  // If this PN returns a struct, just mark the result overdefined.
782
5.00M
  // TODO: We could do a lot better than this if code actually uses this.
783
5.00M
  if (PN.getType()->isStructTy())
784
11.5k
    return (void)markOverdefined(&PN);
785
4.99M
786
4.99M
  if (getValueState(&PN).isOverdefined())
787
3.31M
    return;  // Quick exit
788
1.68M
789
1.68M
  // Super-extra-high-degree PHI nodes are unlikely to ever be marked constant,
790
1.68M
  // and slow us down a lot.  Just mark them overdefined.
791
1.68M
  if (PN.getNumIncomingValues() > 64)
792
78
    return (void)markOverdefined(&PN);
793
1.68M
794
1.68M
  // Look at all of the executable operands of the PHI node.  If any of them
795
1.68M
  // are overdefined, the PHI becomes overdefined as well.  If they are all
796
1.68M
  // constant, and they agree with each other, the PHI becomes the identical
797
1.68M
  // constant.  If they are constant and don't agree, the PHI is overdefined.
798
1.68M
  // If there are no executable operands, the PHI remains unknown.
799
1.68M
  Constant *OperandVal = nullptr;
800
4.34M
  for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; 
++i2.66M
) {
801
3.80M
    LatticeVal IV = getValueState(PN.getIncomingValue(i));
802
3.80M
    if (IV.isUnknown()) 
continue928k
; // Doesn't influence PHI node.
803
2.87M
804
2.87M
    if (!isEdgeFeasible(PN.getIncomingBlock(i), PN.getParent()))
805
578k
      continue;
806
2.29M
807
2.29M
    if (IV.isOverdefined())    // PHI node becomes overdefined!
808
828k
      return (void)markOverdefined(&PN);
809
1.46M
810
1.46M
    if (!OperandVal) {   // Grab the first value.
811
894k
      OperandVal = IV.getConstant();
812
894k
      continue;
813
894k
    }
814
573k
815
573k
    // There is already a reachable operand.  If we conflict with it,
816
573k
    // then the PHI node becomes overdefined.  If we agree with it, we
817
573k
    // can continue on.
818
573k
819
573k
    // Check to see if there are two different constants merging, if so, the PHI
820
573k
    // node is overdefined.
821
573k
    if (IV.getConstant() != OperandVal)
822
306k
      return (void)markOverdefined(&PN);
823
573k
  }
824
1.68M
825
1.68M
  // If we exited the loop, this means that the PHI node only has constant
826
1.68M
  // arguments that agree with each other(and OperandVal is the constant) or
827
1.68M
  // OperandVal is null because there are no defined incoming arguments.  If
828
1.68M
  // this is the case, the PHI remains unknown.
829
1.68M
  
if (546k
OperandVal546k
)
830
510k
    markConstant(&PN, OperandVal);      // Acquire operand value
831
546k
}
832
833
1.69M
void SCCPSolver::visitReturnInst(ReturnInst &I) {
834
1.69M
  if (I.getNumOperands() == 0) 
return316k
; // ret void
835
1.37M
836
1.37M
  Function *F = I.getParent()->getParent();
837
1.37M
  Value *ResultOp = I.getOperand(0);
838
1.37M
839
1.37M
  // If we are tracking the return value of this function, merge it in.
840
1.37M
  if (!TrackedRetVals.empty() && 
!ResultOp->getType()->isStructTy()353k
) {
841
349k
    MapVector<Function*, LatticeVal>::iterator TFRVI =
842
349k
      TrackedRetVals.find(F);
843
349k
    if (TFRVI != TrackedRetVals.end()) {
844
115k
      mergeInValue(TFRVI->second, F, getValueState(ResultOp));
845
115k
      return;
846
115k
    }
847
1.25M
  }
848
1.25M
849
1.25M
  // Handle functions that return multiple values.
850
1.25M
  if (!TrackedMultipleRetVals.empty()) {
851
10.1k
    if (auto *STy = dyn_cast<StructType>(ResultOp->getType()))
852
3.16k
      if (MRVFunctionsTracked.count(F))
853
7.22k
        
for (unsigned i = 0, e = STy->getNumElements(); 2.46k
i != e;
++i4.76k
)
854
4.76k
          mergeInValue(TrackedMultipleRetVals[std::make_pair(F, i)], F,
855
4.76k
                       getStructValueState(ResultOp, i));
856
10.1k
  }
857
1.25M
}
858
859
6.49M
void SCCPSolver::visitTerminator(Instruction &TI) {
860
6.49M
  SmallVector<bool, 16> SuccFeasible;
861
6.49M
  getFeasibleSuccessors(TI, SuccFeasible);
862
6.49M
863
6.49M
  BasicBlock *BB = TI.getParent();
864
6.49M
865
6.49M
  // Mark all feasible successors executable.
866
17.8M
  for (unsigned i = 0, e = SuccFeasible.size(); i != e; 
++i11.3M
)
867
11.3M
    if (SuccFeasible[i])
868
11.1M
      markEdgeExecutable(BB, TI.getSuccessor(i));
869
6.49M
}
870
871
4.85M
void SCCPSolver::visitCastInst(CastInst &I) {
872
4.85M
  LatticeVal OpSt = getValueState(I.getOperand(0));
873
4.85M
  if (OpSt.isOverdefined())          // Inherit overdefinedness of operand
874
4.64M
    markOverdefined(&I);
875
211k
  else if (OpSt.isConstant()) {
876
103k
    // Fold the constant as we build.
877
103k
    Constant *C = ConstantFoldCastOperand(I.getOpcode(), OpSt.getConstant(),
878
103k
                                          I.getType(), DL);
879
103k
    if (isa<UndefValue>(C))
880
4
      return;
881
103k
    // Propagate constant value
882
103k
    markConstant(&I, C);
883
103k
  }
884
4.85M
}
885
886
289k
void SCCPSolver::visitExtractValueInst(ExtractValueInst &EVI) {
887
289k
  // If this returns a struct, mark all elements over defined, we don't track
888
289k
  // structs in structs.
889
289k
  if (EVI.getType()->isStructTy())
890
193
    return (void)markOverdefined(&EVI);
891
288k
892
288k
  // If this is extracting from more than one level of struct, we don't know.
893
288k
  if (EVI.getNumIndices() != 1)
894
625
    return (void)markOverdefined(&EVI);
895
288k
896
288k
  Value *AggVal = EVI.getAggregateOperand();
897
288k
  if (AggVal->getType()->isStructTy()) {
898
252k
    unsigned i = *EVI.idx_begin();
899
252k
    LatticeVal EltVal = getStructValueState(AggVal, i);
900
252k
    mergeInValue(getValueState(&EVI), &EVI, EltVal);
901
252k
  } else {
902
36.0k
    // Otherwise, must be extracting from an array.
903
36.0k
    return (void)markOverdefined(&EVI);
904
36.0k
  }
905
288k
}
906
907
55.8k
void SCCPSolver::visitInsertValueInst(InsertValueInst &IVI) {
908
55.8k
  auto *STy = dyn_cast<StructType>(IVI.getType());
909
55.8k
  if (!STy)
910
18.0k
    return (void)markOverdefined(&IVI);
911
37.8k
912
37.8k
  // If this has more than one index, we can't handle it, drive all results to
913
37.8k
  // undef.
914
37.8k
  if (IVI.getNumIndices() != 1)
915
13.6k
    return (void)markOverdefined(&IVI);
916
24.1k
917
24.1k
  Value *Aggr = IVI.getAggregateOperand();
918
24.1k
  unsigned Idx = *IVI.idx_begin();
919
24.1k
920
24.1k
  // Compute the result based on what we're inserting.
921
73.0k
  for (unsigned i = 0, e = STy->getNumElements(); i != e; 
++i48.8k
) {
922
48.8k
    // This passes through all values that aren't the inserted element.
923
48.8k
    if (i != Idx) {
924
24.6k
      LatticeVal EltVal = getStructValueState(Aggr, i);
925
24.6k
      mergeInValue(getStructValueState(&IVI, i), &IVI, EltVal);
926
24.6k
      continue;
927
24.6k
    }
928
24.1k
929
24.1k
    Value *Val = IVI.getInsertedValueOperand();
930
24.1k
    if (Val->getType()->isStructTy())
931
0
      // We don't track structs in structs.
932
0
      markOverdefined(getStructValueState(&IVI, i), &IVI);
933
24.1k
    else {
934
24.1k
      LatticeVal InVal = getValueState(Val);
935
24.1k
      mergeInValue(getStructValueState(&IVI, i), &IVI, InVal);
936
24.1k
    }
937
24.1k
  }
938
24.1k
}
939
940
517k
void SCCPSolver::visitSelectInst(SelectInst &I) {
941
517k
  // If this select returns a struct, just mark the result overdefined.
942
517k
  // TODO: We could do a lot better than this if code actually uses this.
943
517k
  if (I.getType()->isStructTy())
944
0
    return (void)markOverdefined(&I);
945
517k
946
517k
  LatticeVal CondValue = getValueState(I.getCondition());
947
517k
  if (CondValue.isUnknown())
948
57.7k
    return;
949
460k
950
460k
  if (ConstantInt *CondCB = CondValue.getConstantInt()) {
951
5.87k
    Value *OpVal = CondCB->isZero() ? 
I.getFalseValue()3.00k
:
I.getTrueValue()2.87k
;
952
5.87k
    mergeInValue(&I, getValueState(OpVal));
953
5.87k
    return;
954
5.87k
  }
955
454k
956
454k
  // Otherwise, the condition is overdefined or a constant we can't evaluate.
957
454k
  // See if we can produce something better than overdefined based on the T/F
958
454k
  // value.
959
454k
  LatticeVal TVal = getValueState(I.getTrueValue());
960
454k
  LatticeVal FVal = getValueState(I.getFalseValue());
961
454k
962
454k
  // select ?, C, C -> C.
963
454k
  if (TVal.isConstant() && 
FVal.isConstant()148k
&&
964
454k
      
TVal.getConstant() == FVal.getConstant()65.8k
)
965
483
    return (void)markConstant(&I, FVal.getConstant());
966
453k
967
453k
  if (TVal.isUnknown())   // select ?, undef, X -> X.
968
4.37k
    return (void)mergeInValue(&I, FVal);
969
449k
  if (FVal.isUnknown())   // select ?, X, undef -> X.
970
1.42k
    return (void)mergeInValue(&I, TVal);
971
447k
  markOverdefined(&I);
972
447k
}
973
974
// Handle Unary Operators.
975
4
void SCCPSolver::visitUnaryOperator(Instruction &I) {
976
4
  LatticeVal V0State = getValueState(I.getOperand(0));
977
4
978
4
  LatticeVal &IV = ValueState[&I];
979
4
  if (IV.isOverdefined()) 
return0
;
980
4
981
4
  if (V0State.isConstant()) {
982
3
    Constant *C = ConstantExpr::get(I.getOpcode(), V0State.getConstant());
983
3
984
3
    // op Y -> undef.
985
3
    if (isa<UndefValue>(C))
986
0
      return;
987
3
    return (void)markConstant(IV, &I, C);
988
3
  }
989
1
990
1
  // If something is undef, wait for it to resolve.
991
1
  if (!V0State.isOverdefined())
992
1
    return;
993
0
994
0
  markOverdefined(&I);
995
0
}
996
997
// Handle Binary Operators.
998
5.06M
void SCCPSolver::visitBinaryOperator(Instruction &I) {
999
5.06M
  LatticeVal V1State = getValueState(I.getOperand(0));
1000
5.06M
  LatticeVal V2State = getValueState(I.getOperand(1));
1001
5.06M
1002
5.06M
  LatticeVal &IV = ValueState[&I];
1003
5.06M
  if (IV.isOverdefined()) 
return2.51M
;
1004
2.54M
1005
2.54M
  if (V1State.isConstant() && 
V2State.isConstant()439k
) {
1006
284k
    Constant *C = ConstantExpr::get(I.getOpcode(), V1State.getConstant(),
1007
284k
                                    V2State.getConstant());
1008
284k
    // X op Y -> undef.
1009
284k
    if (isa<UndefValue>(C))
1010
92
      return;
1011
284k
    return (void)markConstant(IV, &I, C);
1012
284k
  }
1013
2.25M
1014
2.25M
  // If something is undef, wait for it to resolve.
1015
2.25M
  if (!V1State.isOverdefined() && 
!V2State.isOverdefined()285k
)
1016
25.7k
    return;
1017
2.23M
1018
2.23M
  // Otherwise, one of our operands is overdefined.  Try to produce something
1019
2.23M
  // better than overdefined with some tricks.
1020
2.23M
  // If this is 0 / Y, it doesn't matter that the second operand is
1021
2.23M
  // overdefined, and we can replace it with zero.
1022
2.23M
  if (I.getOpcode() == Instruction::UDiv || 
I.getOpcode() == Instruction::SDiv2.21M
)
1023
41.8k
    if (V1State.isConstant() && 
V1State.getConstant()->isNullValue()4.21k
)
1024
126
      return (void)markConstant(IV, &I, V1State.getConstant());
1025
2.23M
1026
2.23M
  // If this is:
1027
2.23M
  // -> AND/MUL with 0
1028
2.23M
  // -> OR with -1
1029
2.23M
  // it doesn't matter that the other operand is overdefined.
1030
2.23M
  if (I.getOpcode() == Instruction::And || 
I.getOpcode() == Instruction::Mul1.93M
||
1031
2.23M
      
I.getOpcode() == Instruction::Or1.74M
) {
1032
622k
    LatticeVal *NonOverdefVal = nullptr;
1033
622k
    if (!V1State.isOverdefined())
1034
66.8k
      NonOverdefVal = &V1State;
1035
555k
    else if (!V2State.isOverdefined())
1036
252k
      NonOverdefVal = &V2State;
1037
622k
1038
622k
    if (NonOverdefVal) {
1039
319k
      if (NonOverdefVal->isUnknown())
1040
69.1k
        return;
1041
250k
1042
250k
      if (I.getOpcode() == Instruction::And ||
1043
250k
          
I.getOpcode() == Instruction::Mul93.0k
) {
1044
221k
        // X and 0 = 0
1045
221k
        // X * 0 = 0
1046
221k
        if (NonOverdefVal->getConstant()->isNullValue())
1047
7.23k
          return (void)markConstant(IV, &I, NonOverdefVal->getConstant());
1048
28.8k
      } else {
1049
28.8k
        // X or -1 = -1
1050
28.8k
        if (ConstantInt *CI = NonOverdefVal->getConstantInt())
1051
28.7k
          if (CI->isMinusOne())
1052
551
            return (void)markConstant(IV, &I, NonOverdefVal->getConstant());
1053
2.15M
      }
1054
250k
    }
1055
622k
  }
1056
2.15M
1057
2.15M
  markOverdefined(&I);
1058
2.15M
}
1059
1060
// Handle ICmpInst instruction.
1061
5.29M
void SCCPSolver::visitCmpInst(CmpInst &I) {
1062
5.29M
  // Do not cache this lookup, getValueState calls later in the function might
1063
5.29M
  // invalidate the reference.
1064
5.29M
  if (ValueState[&I].isOverdefined()) 
return2.59M
;
1065
2.69M
1066
2.69M
  Value *Op1 = I.getOperand(0);
1067
2.69M
  Value *Op2 = I.getOperand(1);
1068
2.69M
1069
2.69M
  // For parameters, use ParamState which includes constant range info if
1070
2.69M
  // available.
1071
2.69M
  auto V1Param = ParamState.find(Op1);
1072
2.69M
  ValueLatticeElement V1State = (V1Param != ParamState.end())
1073
2.69M
                                    ? 
V1Param->second5.73k
1074
2.69M
                                    : 
getValueState(Op1).toValueLattice()2.69M
;
1075
2.69M
1076
2.69M
  auto V2Param = ParamState.find(Op2);
1077
2.69M
  ValueLatticeElement V2State = V2Param != ParamState.end()
1078
2.69M
                                    ? 
V2Param->second3.23k
1079
2.69M
                                    : 
getValueState(Op2).toValueLattice()2.69M
;
1080
2.69M
1081
2.69M
  Constant *C = V1State.getCompare(I.getPredicate(), I.getType(), V2State);
1082
2.69M
  if (C) {
1083
203k
    if (isa<UndefValue>(C))
1084
94.9k
      return;
1085
108k
    LatticeVal CV;
1086
108k
    CV.markConstant(C);
1087
108k
    mergeInValue(&I, CV);
1088
108k
    return;
1089
108k
  }
1090
2.49M
1091
2.49M
  // If operands are still unknown, wait for it to resolve.
1092
2.49M
  if (!V1State.isOverdefined() && 
!V2State.isOverdefined()166k
&&
1093
2.49M
      
!ValueState[&I].isConstant()294
)
1094
188
    return;
1095
2.49M
1096
2.49M
  markOverdefined(&I);
1097
2.49M
}
1098
1099
// Handle getelementptr instructions.  If all operands are constants then we
1100
// can turn this into a getelementptr ConstantExpr.
1101
9.01M
void SCCPSolver::visitGetElementPtrInst(GetElementPtrInst &I) {
1102
9.01M
  if (ValueState[&I].isOverdefined()) 
return3.93M
;
1103
5.07M
1104
5.07M
  SmallVector<Constant*, 8> Operands;
1105
5.07M
  Operands.reserve(I.getNumOperands());
1106
5.07M
1107
5.37M
  for (unsigned i = 0, e = I.getNumOperands(); i != e; 
++i296k
) {
1108
5.33M
    LatticeVal State = getValueState(I.getOperand(i));
1109
5.33M
    if (State.isUnknown())
1110
415k
      return;  // Operands are not resolved yet.
1111
4.91M
1112
4.91M
    if (State.isOverdefined())
1113
4.62M
      return (void)markOverdefined(&I);
1114
296k
1115
296k
    assert(State.isConstant() && "Unknown state!");
1116
296k
    Operands.push_back(State.getConstant());
1117
296k
  }
1118
5.07M
1119
5.07M
  Constant *Ptr = Operands[0];
1120
35.0k
  auto Indices = makeArrayRef(Operands.begin() + 1, Operands.end());
1121
35.0k
  Constant *C =
1122
35.0k
      ConstantExpr::getGetElementPtr(I.getSourceElementType(), Ptr, Indices);
1123
35.0k
  if (isa<UndefValue>(C))
1124
0
      return;
1125
35.0k
  markConstant(&I, C);
1126
35.0k
}
1127
1128
4.81M
void SCCPSolver::visitStoreInst(StoreInst &SI) {
1129
4.81M
  // If this store is of a struct, ignore it.
1130
4.81M
  if (SI.getOperand(0)->getType()->isStructTy())
1131
24
    return;
1132
4.81M
1133
4.81M
  if (TrackedGlobals.empty() || 
!isa<GlobalVariable>(SI.getOperand(1))493k
)
1134
4.77M
    return;
1135
41.8k
1136
41.8k
  GlobalVariable *GV = cast<GlobalVariable>(SI.getOperand(1));
1137
41.8k
  DenseMap<GlobalVariable*, LatticeVal>::iterator I = TrackedGlobals.find(GV);
1138
41.8k
  if (I == TrackedGlobals.end() || 
I->second.isOverdefined()5.10k
)
return36.7k
;
1139
5.10k
1140
5.10k
  // Get the value we are storing into the global, then merge it.
1141
5.10k
  mergeInValue(I->second, GV, getValueState(SI.getOperand(0)));
1142
5.10k
  if (I->second.isOverdefined())
1143
4.42k
    TrackedGlobals.erase(I);      // No need to keep tracking this!
1144
5.10k
}
1145
1146
// Handle load instructions.  If the operand is a constant pointer to a constant
1147
// global, we can replace the load with the loaded constant value!
1148
5.52M
void SCCPSolver::visitLoadInst(LoadInst &I) {
1149
5.52M
  // If this load is of a struct, just mark the result overdefined.
1150
5.52M
  if (I.getType()->isStructTy())
1151
14
    return (void)markOverdefined(&I);
1152
5.52M
1153
5.52M
  LatticeVal PtrVal = getValueState(I.getOperand(0));
1154
5.52M
  if (PtrVal.isUnknown()) 
return43.6k
; // The pointer is not resolved yet!
1155
5.48M
1156
5.48M
  LatticeVal &IV = ValueState[&I];
1157
5.48M
  if (IV.isOverdefined()) 
return2.42M
;
1158
3.05M
1159
3.05M
  if (!PtrVal.isConstant() || 
I.isVolatile()450k
)
1160
2.62M
    return (void)markOverdefined(IV, &I);
1161
431k
1162
431k
  Constant *Ptr = PtrVal.getConstant();
1163
431k
1164
431k
  // load null is undefined.
1165
431k
  if (isa<ConstantPointerNull>(Ptr)) {
1166
611
    if (NullPointerIsDefined(I.getFunction(), I.getPointerAddressSpace()))
1167
2
      return (void)markOverdefined(IV, &I);
1168
609
    else
1169
609
      return;
1170
431k
  }
1171
431k
1172
431k
  // Transform load (constant global) into the value loaded.
1173
431k
  if (auto *GV = dyn_cast<GlobalVariable>(Ptr)) {
1174
291k
    if (!TrackedGlobals.empty()) {
1175
50.3k
      // If we are tracking this global, merge in the known value for it.
1176
50.3k
      DenseMap<GlobalVariable*, LatticeVal>::iterator It =
1177
50.3k
        TrackedGlobals.find(GV);
1178
50.3k
      if (It != TrackedGlobals.end()) {
1179
7.10k
        mergeInValue(IV, &I, It->second);
1180
7.10k
        return;
1181
7.10k
      }
1182
424k
    }
1183
291k
  }
1184
424k
1185
424k
  // Transform load from a constant into a constant if possible.
1186
424k
  if (Constant *C = ConstantFoldLoadFromConstPtr(Ptr, I.getType(), DL)) {
1187
1.58k
    if (isa<UndefValue>(C))
1188
3
      return;
1189
1.57k
    return (void)markConstant(IV, &I, C);
1190
1.57k
  }
1191
422k
1192
422k
  // Otherwise we cannot say for certain what value this load will produce.
1193
422k
  // Bail out.
1194
422k
  markOverdefined(IV, &I);
1195
422k
}
1196
1197
10.3M
void SCCPSolver::visitCallSite(CallSite CS) {
1198
10.3M
  Function *F = CS.getCalledFunction();
1199
10.3M
  Instruction *I = CS.getInstruction();
1200
10.3M
1201
10.3M
  if (auto *II = dyn_cast<IntrinsicInst>(I)) {
1202
2.33M
    if (II->getIntrinsicID() == Intrinsic::ssa_copy) {
1203
969k
      if (ValueState[I].isOverdefined())
1204
358k
        return;
1205
611k
1206
611k
      auto *PI = getPredicateInfoFor(I);
1207
611k
      if (!PI)
1208
0
        return;
1209
611k
1210
611k
      Value *CopyOf = I->getOperand(0);
1211
611k
      auto *PBranch = dyn_cast<PredicateBranch>(PI);
1212
611k
      if (!PBranch) {
1213
203
        mergeInValue(ValueState[I], I, getValueState(CopyOf));
1214
203
        return;
1215
203
      }
1216
611k
1217
611k
      Value *Cond = PBranch->Condition;
1218
611k
1219
611k
      // Everything below relies on the condition being a comparison.
1220
611k
      auto *Cmp = dyn_cast<CmpInst>(Cond);
1221
611k
      if (!Cmp) {
1222
0
        mergeInValue(ValueState[I], I, getValueState(CopyOf));
1223
0
        return;
1224
0
      }
1225
611k
1226
611k
      Value *CmpOp0 = Cmp->getOperand(0);
1227
611k
      Value *CmpOp1 = Cmp->getOperand(1);
1228
611k
      if (CopyOf != CmpOp0 && 
CopyOf != CmpOp189.5k
) {
1229
6.10k
        mergeInValue(ValueState[I], I, getValueState(CopyOf));
1230
6.10k
        return;
1231
6.10k
      }
1232
604k
1233
604k
      if (CmpOp0 != CopyOf)
1234
83.4k
        std::swap(CmpOp0, CmpOp1);
1235
604k
1236
604k
      LatticeVal OriginalVal = getValueState(CopyOf);
1237
604k
      LatticeVal EqVal = getValueState(CmpOp1);
1238
604k
      LatticeVal &IV = ValueState[I];
1239
604k
      if (PBranch->TrueEdge && 
Cmp->getPredicate() == CmpInst::ICMP_EQ346k
) {
1240
31.9k
        addAdditionalUser(CmpOp1, I);
1241
31.9k
        if (OriginalVal.isConstant())
1242
506
          mergeInValue(IV, I, OriginalVal);
1243
31.4k
        else
1244
31.4k
          mergeInValue(IV, I, EqVal);
1245
31.9k
        return;
1246
31.9k
      }
1247
572k
      if (!PBranch->TrueEdge && 
Cmp->getPredicate() == CmpInst::ICMP_NE258k
) {
1248
3.49k
        addAdditionalUser(CmpOp1, I);
1249
3.49k
        if (OriginalVal.isConstant())
1250
475
          mergeInValue(IV, I, OriginalVal);
1251
3.01k
        else
1252
3.01k
          mergeInValue(IV, I, EqVal);
1253
3.49k
        return;
1254
3.49k
      }
1255
569k
1256
569k
      return (void)mergeInValue(IV, I, getValueState(CopyOf));
1257
569k
    }
1258
2.33M
  }
1259
9.37M
1260
9.37M
  // The common case is that we aren't tracking the callee, either because we
1261
9.37M
  // are not doing interprocedural analysis or the callee is indirect, or is
1262
9.37M
  // external.  Handle these cases first.
1263
9.37M
  if (!F || 
F->isDeclaration()8.92M
) {
1264
8.90M
CallOverdefined:
1265
8.90M
    // Void return and not tracking callee, just bail.
1266
8.90M
    if (I->getType()->isVoidTy()) 
return3.25M
;
1267
5.64M
1268
5.64M
    // Otherwise, if we have a single return value case, and if the function is
1269
5.64M
    // a declaration, maybe we can constant fold it.
1270
5.64M
    if (F && 
F->isDeclaration()5.39M
&&
!I->getType()->isStructTy()1.73M
&&
1271
5.64M
        
canConstantFoldCallTo(cast<CallBase>(CS.getInstruction()), F)1.71M
) {
1272
167k
      SmallVector<Constant*, 8> Operands;
1273
167k
      for (CallSite::arg_iterator AI = CS.arg_begin(), E = CS.arg_end();
1274
170k
           AI != E; 
++AI3.23k
) {
1275
169k
        if (AI->get()->getType()->isStructTy())
1276
8
          return markOverdefined(I); // Can't handle struct args.
1277
169k
        LatticeVal State = getValueState(*AI);
1278
169k
1279
169k
        if (State.isUnknown())
1280
443
          return;  // Operands are not resolved yet.
1281
169k
        if (State.isOverdefined())
1282
166k
          return (void)markOverdefined(I);
1283
3.23k
        assert(State.isConstant() && "Unknown state!");
1284
3.23k
        Operands.push_back(State.getConstant());
1285
3.23k
      }
1286
167k
1287
167k
      
if (711
getValueState(I).isOverdefined()711
)
1288
1
        return;
1289
710
1290
710
      // If we can constant fold this, mark the result of the call as a
1291
710
      // constant.
1292
710
      if (Constant *C = ConstantFoldCall(cast<CallBase>(CS.getInstruction()), F,
1293
678
                                         Operands, TLI)) {
1294
678
        // call -> undef.
1295
678
        if (isa<UndefValue>(C))
1296
0
          return;
1297
678
        return (void)markConstant(I, C);
1298
678
      }
1299
710
    }
1300
5.47M
1301
5.47M
    // Otherwise, we don't know anything about this call, mark it overdefined.
1302
5.47M
    return (void)markOverdefined(I);
1303
5.47M
  }
1304
5.37M
1305
5.37M
  // If this is a local function that doesn't have its address taken, mark its
1306
5.37M
  // entry block executable and merge in the actual arguments to the call into
1307
5.37M
  // the formal arguments of the function.
1308
5.37M
  if (!TrackingIncomingArguments.empty() && 
TrackingIncomingArguments.count(F)1.07M
){
1309
266k
    MarkBlockExecutable(&F->front());
1310
266k
1311
266k
    // Propagate information from this call site into the callee.
1312
266k
    CallSite::arg_iterator CAI = CS.arg_begin();
1313
266k
    for (Function::arg_iterator AI = F->arg_begin(), E = F->arg_end();
1314
814k
         AI != E; 
++AI, ++CAI547k
) {
1315
547k
      // If this argument is byval, and if the function is not readonly, there
1316
547k
      // will be an implicit copy formed of the input aggregate.
1317
547k
      if (AI->hasByValAttr() && 
!F->onlyReadsMemory()995
) {
1318
993
        markOverdefined(&*AI);
1319
993
        continue;
1320
993
      }
1321
546k
1322
546k
      if (auto *STy = dyn_cast<StructType>(AI->getType())) {
1323
24
        for (unsigned i = 0, e = STy->getNumElements(); i != e; 
++i16
) {
1324
16
          LatticeVal CallArg = getStructValueState(*CAI, i);
1325
16
          mergeInValue(getStructValueState(&*AI, i), &*AI, CallArg);
1326
16
        }
1327
546k
      } else {
1328
546k
        // Most other parts of the Solver still only use the simpler value
1329
546k
        // lattice, so we propagate changes for parameters to both lattices.
1330
546k
        LatticeVal ConcreteArgument = getValueState(*CAI);
1331
546k
        bool ParamChanged =
1332
546k
            getParamState(&*AI).mergeIn(ConcreteArgument.toValueLattice(), DL);
1333
546k
         bool ValueChanged = mergeInValue(&*AI, ConcreteArgument);
1334
546k
        // Add argument to work list, if the state of a parameter changes but
1335
546k
        // ValueState does not change (because it is already overdefined there),
1336
546k
        // We have to take changes in ParamState into account, as it is used
1337
546k
        // when evaluating Cmp instructions.
1338
546k
        if (!ValueChanged && 
ParamChanged492k
)
1339
971
          pushToWorkList(ValueState[&*AI], &*AI);
1340
546k
      }
1341
546k
    }
1342
266k
  }
1343
5.37M
1344
5.37M
  // If this is a single/zero retval case, see if we're tracking the function.
1345
5.37M
  if (auto *STy = dyn_cast<StructType>(F->getReturnType())) {
1346
11.3k
    if (!MRVFunctionsTracked.count(F))
1347
9.39k
      goto CallOverdefined;  // Not tracking this callee.
1348
1.96k
1349
1.96k
    // If we are tracking this callee, propagate the result of the function
1350
1.96k
    // into this call site.
1351
5.61k
    
for (unsigned i = 0, e = STy->getNumElements(); 1.96k
i != e;
++i3.65k
)
1352
3.65k
      mergeInValue(getStructValueState(I, i), I,
1353
3.65k
                   TrackedMultipleRetVals[std::make_pair(F, i)]);
1354
5.36M
  } else {
1355
5.36M
    MapVector<Function*, LatticeVal>::iterator TFRVI = TrackedRetVals.find(F);
1356
5.36M
    if (TFRVI == TrackedRetVals.end())
1357
4.89M
      goto CallOverdefined;  // Not tracking this callee.
1358
473k
1359
473k
    // If so, propagate the return value of the callee into this call result.
1360
473k
    mergeInValue(I, TFRVI->second);
1361
473k
  }
1362
5.37M
}
1363
1364
480k
void SCCPSolver::Solve() {
1365
480k
  // Process the work lists until they are empty!
1366
1.21M
  while (!BBWorkList.empty() || 
!InstWorkList.empty()738k
||
1367
1.21M
         
!OverdefinedInstWorkList.empty()658k
) {
1368
737k
    // Process the overdefined instruction's work list first, which drives other
1369
737k
    // things to overdefined more quickly.
1370
22.5M
    while (!OverdefinedInstWorkList.empty()) {
1371
21.7M
      Value *I = OverdefinedInstWorkList.pop_back_val();
1372
21.7M
1373
21.7M
      LLVM_DEBUG(dbgs() << "\nPopped off OI-WL: " << *I << '\n');
1374
21.7M
1375
21.7M
      // "I" got into the work list because it either made the transition from
1376
21.7M
      // bottom to constant, or to overdefined.
1377
21.7M
      //
1378
21.7M
      // Anything on this worklist that is overdefined need not be visited
1379
21.7M
      // since all of its users will have already been marked as overdefined
1380
21.7M
      // Update all of the users of this instruction's value.
1381
21.7M
      //
1382
21.7M
      markUsersAsChanged(I);
1383
21.7M
    }
1384
737k
1385
737k
    // Process the instruction work list.
1386
1.80M
    while (!InstWorkList.empty()) {
1387
1.07M
      Value *I = InstWorkList.pop_back_val();
1388
1.07M
1389
1.07M
      LLVM_DEBUG(dbgs() << "\nPopped off I-WL: " << *I << '\n');
1390
1.07M
1391
1.07M
      // "I" got into the work list because it made the transition from undef to
1392
1.07M
      // constant.
1393
1.07M
      //
1394
1.07M
      // Anything on this worklist that is overdefined need not be visited
1395
1.07M
      // since all of its users will have already been marked as overdefined.
1396
1.07M
      // Update all of the users of this instruction's value.
1397
1.07M
      //
1398
1.07M
      if (I->getType()->isStructTy() || 
!getValueState(I).isOverdefined()1.07M
)
1399
132k
        markUsersAsChanged(I);
1400
1.07M
    }
1401
737k
1402
737k
    // Process the basic block work list.
1403
6.04M
    while (!BBWorkList.empty()) {
1404
5.31M
      BasicBlock *BB = BBWorkList.back();
1405
5.31M
      BBWorkList.pop_back();
1406
5.31M
1407
5.31M
      LLVM_DEBUG(dbgs() << "\nPopped off BBWL: " << *BB << '\n');
1408
5.31M
1409
5.31M
      // Notify all instructions in this basic block that they are newly
1410
5.31M
      // executable.
1411
5.31M
      visit(BB);
1412
5.31M
    }
1413
737k
  }
1414
480k
}
1415
1416
/// ResolvedUndefsIn - While solving the dataflow for a function, we assume
1417
/// that branches on undef values cannot reach any of their successors.
1418
/// However, this is not a safe assumption.  After we solve dataflow, this
1419
/// method should be use to handle this.  If this returns true, the solver
1420
/// should be rerun.
1421
///
1422
/// This method handles this by finding an unresolved branch and marking it one
1423
/// of the edges from the block as being feasible, even though the condition
1424
/// doesn't say it would otherwise be.  This allows SCCP to find the rest of the
1425
/// CFG and only slightly pessimizes the analysis results (by marking one,
1426
/// potentially infeasible, edge feasible).  This cannot usefully modify the
1427
/// constraints on the condition of the branch, as that would impact other users
1428
/// of the value.
1429
///
1430
/// This scan also checks for values that use undefs, whose results are actually
1431
/// defined.  For example, 'zext i8 undef to i32' should produce all zeros
1432
/// conservatively, as "(zext i8 X -> i32) & 0xFF00" must always return zero,
1433
/// even if X isn't defined.
1434
1.99M
bool SCCPSolver::ResolvedUndefsIn(Function &F) {
1435
5.45M
  for (BasicBlock &BB : F) {
1436
5.45M
    if (!BBExecutable.count(&BB))
1437
23.8k
      continue;
1438
5.43M
1439
29.1M
    
for (Instruction &I : BB)5.43M
{
1440
29.1M
      // Look for instructions which produce undef values.
1441
29.1M
      if (I.getType()->isVoidTy()) 
continue9.12M
;
1442
20.0M
1443
20.0M
      if (auto *STy = dyn_cast<StructType>(I.getType())) {
1444
77.5k
        // Only a few things that can be structs matter for undef.
1445
77.5k
1446
77.5k
        // Tracked calls must never be marked overdefined in ResolvedUndefsIn.
1447
77.5k
        if (CallSite CS = CallSite(&I))
1448
10.4k
          if (Function *F = CS.getCalledFunction())
1449
10.1k
            if (MRVFunctionsTracked.count(F))
1450
393
              continue;
1451
77.1k
1452
77.1k
        // extractvalue and insertvalue don't need to be marked; they are
1453
77.1k
        // tracked as precisely as their operands.
1454
77.1k
        if (isa<ExtractValueInst>(I) || 
isa<InsertValueInst>(I)77.1k
)
1455
15.1k
          continue;
1456
62.0k
1457
62.0k
        // Send the results of everything else to overdefined.  We could be
1458
62.0k
        // more precise than this but it isn't worth bothering.
1459
184k
        
for (unsigned i = 0, e = STy->getNumElements(); 62.0k
i != e;
++i122k
) {
1460
122k
          LatticeVal &LV = getStructValueState(&I, i);
1461
122k
          if (LV.isUnknown())
1462
0
            markOverdefined(LV, &I);
1463
122k
        }
1464
62.0k
        continue;
1465
62.0k
      }
1466
19.9M
1467
19.9M
      LatticeVal &LV = getValueState(&I);
1468
19.9M
      if (!LV.isUnknown()) 
continue19.9M
;
1469
871
1470
871
      // extractvalue is safe; check here because the argument is a struct.
1471
871
      if (isa<ExtractValueInst>(I))
1472
1
        continue;
1473
870
1474
870
      // Compute the operand LatticeVals, for convenience below.
1475
870
      // Anything taking a struct is conservatively assumed to require
1476
870
      // overdefined markings.
1477
870
      if (I.getOperand(0)->getType()->isStructTy()) {
1478
0
        markOverdefined(&I);
1479
0
        return true;
1480
0
      }
1481
870
      LatticeVal Op0LV = getValueState(I.getOperand(0));
1482
870
      LatticeVal Op1LV;
1483
870
      if (I.getNumOperands() == 2) {
1484
271
        if (I.getOperand(1)->getType()->isStructTy()) {
1485
0
          markOverdefined(&I);
1486
0
          return true;
1487
0
        }
1488
271
1489
271
        Op1LV = getValueState(I.getOperand(1));
1490
271
      }
1491
870
      // If this is an instructions whose result is defined even if the input is
1492
870
      // not fully defined, propagate the information.
1493
870
      Type *ITy = I.getType();
1494
870
      switch (I.getOpcode()) {
1495
870
      case Instruction::Add:
1496
16
      case Instruction::Sub:
1497
16
      case Instruction::Trunc:
1498
16
      case Instruction::FPTrunc:
1499
16
      case Instruction::BitCast:
1500
16
        break; // Any undef -> undef
1501
16
      case Instruction::FSub:
1502
0
      case Instruction::FAdd:
1503
0
      case Instruction::FMul:
1504
0
      case Instruction::FDiv:
1505
0
      case Instruction::FRem:
1506
0
        // Floating-point binary operation: be conservative.
1507
0
        if (Op0LV.isUnknown() && Op1LV.isUnknown())
1508
0
          markForcedConstant(&I, Constant::getNullValue(ITy));
1509
0
        else
1510
0
          markOverdefined(&I);
1511
0
        return true;
1512
1
      case Instruction::FNeg:
1513
1
        break; // fneg undef -> undef
1514
3
      case Instruction::ZExt:
1515
3
      case Instruction::SExt:
1516
3
      case Instruction::FPToUI:
1517
3
      case Instruction::FPToSI:
1518
3
      case Instruction::FPExt:
1519
3
      case Instruction::PtrToInt:
1520
3
      case Instruction::IntToPtr:
1521
3
      case Instruction::SIToFP:
1522
3
      case Instruction::UIToFP:
1523
3
        // undef -> 0; some outputs are impossible
1524
3
        markForcedConstant(&I, Constant::getNullValue(ITy));
1525
3
        return true;
1526
7
      case Instruction::Mul:
1527
7
      case Instruction::And:
1528
7
        // Both operands undef -> undef
1529
7
        if (Op0LV.isUnknown() && 
Op1LV.isUnknown()5
)
1530
0
          break;
1531
7
        // undef * X -> 0.   X could be zero.
1532
7
        // undef & X -> 0.   X could be zero.
1533
7
        markForcedConstant(&I, Constant::getNullValue(ITy));
1534
7
        return true;
1535
7
      case Instruction::Or:
1536
1
        // Both operands undef -> undef
1537
1
        if (Op0LV.isUnknown() && 
Op1LV.isUnknown()0
)
1538
0
          break;
1539
1
        // undef | X -> -1.   X could be -1.
1540
1
        markForcedConstant(&I, Constant::getAllOnesValue(ITy));
1541
1
        return true;
1542
3
      case Instruction::Xor:
1543
3
        // undef ^ undef -> 0; strictly speaking, this is not strictly
1544
3
        // necessary, but we try to be nice to people who expect this
1545
3
        // behavior in simple cases
1546
3
        if (Op0LV.isUnknown() && Op1LV.isUnknown()) {
1547
3
          markForcedConstant(&I, Constant::getNullValue(ITy));
1548
3
          return true;
1549
3
        }
1550
0
        // undef ^ X -> undef
1551
0
        break;
1552
1
      case Instruction::SDiv:
1553
1
      case Instruction::UDiv:
1554
1
      case Instruction::SRem:
1555
1
      case Instruction::URem:
1556
1
        // X / undef -> undef.  No change.
1557
1
        // X % undef -> undef.  No change.
1558
1
        if (Op1LV.isUnknown()) 
break0
;
1559
1
1560
1
        // X / 0 -> undef.  No change.
1561
1
        // X % 0 -> undef.  No change.
1562
1
        if (Op1LV.isConstant() && Op1LV.getConstant()->isZeroValue())
1563
1
          break;
1564
0
1565
0
        // undef / X -> 0.   X could be maxint.
1566
0
        // undef % X -> 0.   X could be 1.
1567
0
        markForcedConstant(&I, Constant::getNullValue(ITy));
1568
0
        return true;
1569
6
      case Instruction::AShr:
1570
6
        // X >>a undef -> undef.
1571
6
        if (Op1LV.isUnknown()) 
break0
;
1572
6
1573
6
        // Shifting by the bitwidth or more is undefined.
1574
6
        if (Op1LV.isConstant()) {
1575
6
          if (auto *ShiftAmt = Op1LV.getConstantInt())
1576
5
            if (ShiftAmt->getLimitedValue() >=
1577
5
                ShiftAmt->getType()->getScalarSizeInBits())
1578
4
              break;
1579
2
        }
1580
2
1581
2
        // undef >>a X -> 0
1582
2
        markForcedConstant(&I, Constant::getNullValue(ITy));
1583
2
        return true;
1584
17
      case Instruction::LShr:
1585
17
      case Instruction::Shl:
1586
17
        // X << undef -> undef.
1587
17
        // X >> undef -> undef.
1588
17
        if (Op1LV.isUnknown()) 
break7
;
1589
10
1590
10
        // Shifting by the bitwidth or more is undefined.
1591
10
        if (Op1LV.isConstant()) {
1592
10
          if (auto *ShiftAmt = Op1LV.getConstantInt())
1593
10
            if (ShiftAmt->getLimitedValue() >=
1594
10
                ShiftAmt->getType()->getScalarSizeInBits())
1595
9
              break;
1596
1
        }
1597
1
1598
1
        // undef << X -> 0
1599
1
        // undef >> X -> 0
1600
1
        markForcedConstant(&I, Constant::getNullValue(ITy));
1601
1
        return true;
1602
4
      case Instruction::Select:
1603
4
        Op1LV = getValueState(I.getOperand(1));
1604
4
        // undef ? X : Y  -> X or Y.  There could be commonality between X/Y.
1605
4
        if (Op0LV.isUnknown()) {
1606
4
          if (!Op1LV.isConstant())  // Pick the constant one if there is any.
1607
3
            Op1LV = getValueState(I.getOperand(2));
1608
4
        } else 
if (0
Op1LV.isUnknown()0
) {
1609
0
          // c ? undef : undef -> undef.  No change.
1610
0
          Op1LV = getValueState(I.getOperand(2));
1611
0
          if (Op1LV.isUnknown())
1612
0
            break;
1613
0
          // Otherwise, c ? undef : x -> x.
1614
0
        } else {
1615
0
          // Leave Op1LV as Operand(1)'s LatticeValue.
1616
0
        }
1617
4
1618
4
        if (Op1LV.isConstant())
1619
1
          markForcedConstant(&I, Op1LV.getConstant());
1620
3
        else
1621
3
          markOverdefined(&I);
1622
4
        return true;
1623
28
      case Instruction::Load:
1624
28
        // A load here means one of two things: a load of undef from a global,
1625
28
        // a load from an unknown pointer.  Either way, having it return undef
1626
28
        // is okay.
1627
28
        break;
1628
131
      case Instruction::ICmp:
1629
131
        // X == undef -> undef.  Other comparisons get more complicated.
1630
131
        Op0LV = getValueState(I.getOperand(0));
1631
131
        Op1LV = getValueState(I.getOperand(1));
1632
131
1633
131
        if ((Op0LV.isUnknown() || 
Op1LV.isUnknown()106
) &&
1634
131
            
cast<ICmpInst>(&I)->isEquality()33
)
1635
28
          break;
1636
103
        markOverdefined(&I);
1637
103
        return true;
1638
599
      case Instruction::Call:
1639
599
      case Instruction::Invoke:
1640
599
      case Instruction::CallBr:
1641
599
        // There are two reasons a call can have an undef result
1642
599
        // 1. It could be tracked.
1643
599
        // 2. It could be constant-foldable.
1644
599
        // Because of the way we solve return values, tracked calls must
1645
599
        // never be marked overdefined in ResolvedUndefsIn.
1646
599
        if (Function *F = CallSite(&I).getCalledFunction())
1647
599
          if (TrackedRetVals.count(F))
1648
597
            break;
1649
2
1650
2
        // If the call is constant-foldable, we mark it overdefined because
1651
2
        // we do not know what return values are valid.
1652
2
        markOverdefined(&I);
1653
2
        return true;
1654
54
      default:
1655
54
        // If we don't know what should happen here, conservatively mark it
1656
54
        // overdefined.
1657
54
        markOverdefined(&I);
1658
54
        return true;
1659
870
      }
1660
870
    }
1661
5.43M
1662
5.43M
    // Check to see if we have a branch or switch on an undefined value.  If so
1663
5.43M
    // we force the branch to go one way or the other to make the successor
1664
5.43M
    // values live.  It doesn't really matter which way we force it.
1665
5.43M
    Instruction *TI = BB.getTerminator();
1666
5.43M
    if (auto *BI = dyn_cast<BranchInst>(TI)) {
1667
4.17M
      if (!BI->isConditional()) 
continue1.87M
;
1668
2.29M
      if (!getValueState(BI->getCondition()).isUnknown())
1669
2.29M
        continue;
1670
33
1671
33
      // If the input to SCCP is actually branch on undef, fix the undef to
1672
33
      // false.
1673
33
      if (isa<UndefValue>(BI->getCondition())) {
1674
14
        BI->setCondition(ConstantInt::getFalse(BI->getContext()));
1675
14
        markEdgeExecutable(&BB, TI->getSuccessor(1));
1676
14
        return true;
1677
14
      }
1678
19
1679
19
      // Otherwise, it is a branch on a symbolic value which is currently
1680
19
      // considered to be undef.  Make sure some edge is executable, so a
1681
19
      // branch on "undef" always flows somewhere.
1682
19
      // FIXME: Distinguish between dead code and an LLVM "undef" value.
1683
19
      BasicBlock *DefaultSuccessor = TI->getSuccessor(1);
1684
19
      if (markEdgeExecutable(&BB, DefaultSuccessor))
1685
11
        return true;
1686
8
1687
8
      continue;
1688
8
    }
1689
1.25M
1690
1.25M
   if (auto *IBR = dyn_cast<IndirectBrInst>(TI)) {
1691
11
      // Indirect branch with no successor ?. Its ok to assume it branches
1692
11
      // to no target.
1693
11
      if (IBR->getNumSuccessors() < 1)
1694
0
        continue;
1695
11
1696
11
      if (!getValueState(IBR->getAddress()).isUnknown())
1697
10
        continue;
1698
1
1699
1
      // If the input to SCCP is actually branch on undef, fix the undef to
1700
1
      // the first successor of the indirect branch.
1701
1
      if (isa<UndefValue>(IBR->getAddress())) {
1702
1
        IBR->setAddress(BlockAddress::get(IBR->getSuccessor(0)));
1703
1
        markEdgeExecutable(&BB, IBR->getSuccessor(0));
1704
1
        return true;
1705
1
      }
1706
0
1707
0
      // Otherwise, it is a branch on a symbolic value which is currently
1708
0
      // considered to be undef.  Make sure some edge is executable, so a
1709
0
      // branch on "undef" always flows somewhere.
1710
0
      // FIXME: IndirectBr on "undef" doesn't actually need to go anywhere:
1711
0
      // we can assume the branch has undefined behavior instead.
1712
0
      BasicBlock *DefaultSuccessor = IBR->getSuccessor(0);
1713
0
      if (markEdgeExecutable(&BB, DefaultSuccessor))
1714
0
        return true;
1715
0
1716
0
      continue;
1717
0
    }
1718
1.25M
1719
1.25M
    if (auto *SI = dyn_cast<SwitchInst>(TI)) {
1720
34.3k
      if (!SI->getNumCases() || 
!getValueState(SI->getCondition()).isUnknown()34.3k
)
1721
34.3k
        continue;
1722
6
1723
6
      // If the input to SCCP is actually switch on undef, fix the undef to
1724
6
      // the first constant.
1725
6
      if (isa<UndefValue>(SI->getCondition())) {
1726
2
        SI->setCondition(SI->case_begin()->getCaseValue());
1727
2
        markEdgeExecutable(&BB, SI->case_begin()->getCaseSuccessor());
1728
2
        return true;
1729
2
      }
1730
4
1731
4
      // Otherwise, it is a branch on a symbolic value which is currently
1732
4
      // considered to be undef.  Make sure some edge is executable, so a
1733
4
      // branch on "undef" always flows somewhere.
1734
4
      // FIXME: Distinguish between dead code and an LLVM "undef" value.
1735
4
      BasicBlock *DefaultSuccessor = SI->case_begin()->getCaseSuccessor();
1736
4
      if (markEdgeExecutable(&BB, DefaultSuccessor))
1737
2
        return true;
1738
2
1739
2
      continue;
1740
2
    }
1741
1.25M
  }
1742
1.99M
1743
1.99M
  
return false1.99M
;
1744
1.99M
}
1745
1746
20.6M
static bool tryToReplaceWithConstant(SCCPSolver &Solver, Value *V) {
1747
20.6M
  Constant *Const = nullptr;
1748
20.6M
  if (V->getType()->isStructTy()) {
1749
76.3k
    std::vector<LatticeVal> IVs = Solver.getStructLatticeValueFor(V);
1750
76.3k
    if (llvm::any_of(IVs,
1751
76.4k
                     [](const LatticeVal &LV) { return LV.isOverdefined(); }))
1752
76.3k
      return false;
1753
36
    std::vector<Constant *> ConstVals;
1754
36
    auto *ST = dyn_cast<StructType>(V->getType());
1755
93
    for (unsigned i = 0, e = ST->getNumElements(); i != e; 
++i57
) {
1756
57
      LatticeVal V = IVs[i];
1757
57
      ConstVals.push_back(V.isConstant()
1758
57
                              ? 
V.getConstant()46
1759
57
                              : 
UndefValue::get(ST->getElementType(i))11
);
1760
57
    }
1761
36
    Const = ConstantStruct::get(ST, ConstVals);
1762
20.5M
  } else {
1763
20.5M
    const LatticeVal &IV = Solver.getLatticeValueFor(V);
1764
20.5M
    if (IV.isOverdefined())
1765
20.5M
      return false;
1766
37.4k
1767
37.4k
    Const = IV.isConstant() ? 
IV.getConstant()37.2k
:
UndefValue::get(V->getType())178
;
1768
37.4k
  }
1769
20.6M
  assert(Const && "Constant is nullptr here!");
1770
37.5k
1771
37.5k
  // Replacing `musttail` instructions with constant breaks `musttail` invariant
1772
37.5k
  // unless the call itself can be removed
1773
37.5k
  CallInst *CI = dyn_cast<CallInst>(V);
1774
37.5k
  if (CI && 
CI->isMustTailCall()22.1k
&&
!CI->isSafeToRemove()7
) {
1775
5
    CallSite CS(CI);
1776
5
    Function *F = CS.getCalledFunction();
1777
5
1778
5
    // Don't zap returns of the callee
1779
5
    if (F)
1780
5
      Solver.AddMustTailCallee(F);
1781
5
1782
5
    LLVM_DEBUG(dbgs() << "  Can\'t treat the result of musttail call : " << *CI
1783
5
                      << " as a constant\n");
1784
5
    return false;
1785
5
  }
1786
37.5k
1787
37.5k
  LLVM_DEBUG(dbgs() << "  Constant: " << *Const << " = " << *V << '\n');
1788
37.5k
1789
37.5k
  // Replaces all of the uses of a variable with uses of the constant.
1790
37.5k
  V->replaceAllUsesWith(Const);
1791
37.5k
  return true;
1792
37.5k
}
1793
1794
// runSCCP() - Run the Sparse Conditional Constant Propagation algorithm,
1795
// and return true if the function was modified.
1796
static bool runSCCP(Function &F, const DataLayout &DL,
1797
467k
                    const TargetLibraryInfo *TLI) {
1798
467k
  LLVM_DEBUG(dbgs() << "SCCP on function '" << F.getName() << "'\n");
1799
467k
  SCCPSolver Solver(DL, TLI);
1800
467k
1801
467k
  // Mark the first block of the function as being executable.
1802
467k
  Solver.MarkBlockExecutable(&F.front());
1803
467k
1804
467k
  // Mark all arguments to the function as being overdefined.
1805
467k
  for (Argument &AI : F.args())
1806
954k
    Solver.markOverdefined(&AI);
1807
467k
1808
467k
  // Solve for constants.
1809
467k
  bool ResolvedUndefs = true;
1810
934k
  while (ResolvedUndefs) {
1811
467k
    Solver.Solve();
1812
467k
    LLVM_DEBUG(dbgs() << "RESOLVING UNDEFs\n");
1813
467k
    ResolvedUndefs = Solver.ResolvedUndefsIn(F);
1814
467k
  }
1815
467k
1816
467k
  bool MadeChanges = false;
1817
467k
1818
467k
  // If we decided that there are basic blocks that are dead in this function,
1819
467k
  // delete their contents now.  Note that we cannot actually delete the blocks,
1820
467k
  // as we cannot modify the CFG of the function.
1821
467k
1822
2.91M
  for (BasicBlock &BB : F) {
1823
2.91M
    if (!Solver.isBlockExecutable(&BB)) {
1824
8.05k
      LLVM_DEBUG(dbgs() << "  BasicBlock Dead:" << BB);
1825
8.05k
1826
8.05k
      ++NumDeadBlocks;
1827
8.05k
      NumInstRemoved += removeAllNonTerminatorAndEHPadInstructions(&BB);
1828
8.05k
1829
8.05k
      MadeChanges = true;
1830
8.05k
      continue;
1831
8.05k
    }
1832
2.90M
1833
2.90M
    // Iterate over all of the instructions in a function, replacing them with
1834
2.90M
    // constants if we have found them to be of constant values.
1835
17.9M
    
for (BasicBlock::iterator BI = BB.begin(), E = BB.end(); 2.90M
BI != E;) {
1836
15.0M
      Instruction *Inst = &*BI++;
1837
15.0M
      if (Inst->getType()->isVoidTy() || 
Inst->isTerminator()10.0M
)
1838
4.98M
        continue;
1839
10.0M
1840
10.0M
      if (tryToReplaceWithConstant(Solver, Inst)) {
1841
849
        if (isInstructionTriviallyDead(Inst))
1842
848
          Inst->eraseFromParent();
1843
849
        // Hey, we just changed something!
1844
849
        MadeChanges = true;
1845
849
        ++NumInstRemoved;
1846
849
      }
1847
10.0M
    }
1848
2.90M
  }
1849
467k
1850
467k
  return MadeChanges;
1851
467k
}
1852
1853
1.17k
PreservedAnalyses SCCPPass::run(Function &F, FunctionAnalysisManager &AM) {
1854
1.17k
  const DataLayout &DL = F.getParent()->getDataLayout();
1855
1.17k
  auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);
1856
1.17k
  if (!runSCCP(F, DL, &TLI))
1857
1.17k
    return PreservedAnalyses::all();
1858
3
1859
3
  auto PA = PreservedAnalyses();
1860
3
  PA.preserve<GlobalsAA>();
1861
3
  PA.preserveSet<CFGAnalyses>();
1862
3
  return PA;
1863
3
}
1864
1865
namespace {
1866
1867
//===--------------------------------------------------------------------===//
1868
//
1869
/// SCCP Class - This class uses the SCCPSolver to implement a per-function
1870
/// Sparse Conditional Constant Propagator.
1871
///
1872
class SCCPLegacyPass : public FunctionPass {
1873
public:
1874
  // Pass identification, replacement for typeid
1875
  static char ID;
1876
1877
13.5k
  SCCPLegacyPass() : FunctionPass(ID) {
1878
13.5k
    initializeSCCPLegacyPassPass(*PassRegistry::getPassRegistry());
1879
13.5k
  }
1880
1881
13.5k
  void getAnalysisUsage(AnalysisUsage &AU) const override {
1882
13.5k
    AU.addRequired<TargetLibraryInfoWrapperPass>();
1883
13.5k
    AU.addPreserved<GlobalsAAWrapperPass>();
1884
13.5k
    AU.setPreservesCFG();
1885
13.5k
  }
1886
1887
  // runOnFunction - Run the Sparse Conditional Constant Propagation
1888
  // algorithm, and return true if the function was modified.
1889
465k
  bool runOnFunction(Function &F) override {
1890
465k
    if (skipFunction(F))
1891
48
      return false;
1892
465k
    const DataLayout &DL = F.getParent()->getDataLayout();
1893
465k
    const TargetLibraryInfo *TLI =
1894
465k
        &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
1895
465k
    return runSCCP(F, DL, TLI);
1896
465k
  }
1897
};
1898
1899
} // end anonymous namespace
1900
1901
char SCCPLegacyPass::ID = 0;
1902
1903
48.9k
INITIALIZE_PASS_BEGIN(SCCPLegacyPass, "sccp",
1904
48.9k
                      "Sparse Conditional Constant Propagation", false, false)
1905
48.9k
INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
1906
48.9k
INITIALIZE_PASS_END(SCCPLegacyPass, "sccp",
1907
                    "Sparse Conditional Constant Propagation", false, false)
1908
1909
// createSCCPPass - This is the public interface to this file.
1910
13.5k
FunctionPass *llvm::createSCCPPass() { return new SCCPLegacyPass(); }
1911
1912
static void findReturnsToZap(Function &F,
1913
                             SmallVector<ReturnInst *, 8> &ReturnsToZap,
1914
7.65k
                             SCCPSolver &Solver) {
1915
7.65k
  // We can only do this if we know that nothing else can call the function.
1916
7.65k
  if (!Solver.isArgumentTrackedFunction(&F))
1917
6.89k
    return;
1918
759
1919
759
  // There is a non-removable musttail call site of this function. Zapping
1920
759
  // returns is not allowed.
1921
759
  if (Solver.isMustTailCallee(&F)) {
1922
2
    LLVM_DEBUG(dbgs() << "Can't zap returns of the function : " << F.getName()
1923
2
                      << " due to present musttail call of it\n");
1924
2
    return;
1925
2
  }
1926
757
1927
2.64k
  
for (BasicBlock &BB : F)757
{
1928
2.64k
    if (CallInst *CI = BB.getTerminatingMustTailCall()) {
1929
0
      LLVM_DEBUG(dbgs() << "Can't zap return of the block due to present "
1930
0
                        << "musttail call : " << *CI << "\n");
1931
0
      (void)CI;
1932
0
      return;
1933
0
    }
1934
2.64k
1935
2.64k
    if (auto *RI = dyn_cast<ReturnInst>(BB.getTerminator()))
1936
731
      if (!isa<UndefValue>(RI->getOperand(0)))
1937
730
        ReturnsToZap.push_back(RI);
1938
2.64k
  }
1939
757
}
1940
1941
// Update the condition for terminators that are branching on indeterminate
1942
// values, forcing them to use a specific edge.
1943
12.2k
static void forceIndeterminateEdge(Instruction* I, SCCPSolver &Solver) {
1944
12.2k
  BasicBlock *Dest = nullptr;
1945
12.2k
  Constant *C = nullptr;
1946
12.2k
  if (SwitchInst *SI = dyn_cast<SwitchInst>(I)) {
1947
37
    if (!isa<ConstantInt>(SI->getCondition())) {
1948
2
      // Indeterminate switch; use first case value.
1949
2
      Dest = SI->case_begin()->getCaseSuccessor();
1950
2
      C = SI->case_begin()->getCaseValue();
1951
2
    }
1952
12.2k
  } else if (BranchInst *BI = dyn_cast<BranchInst>(I)) {
1953
12.2k
    if (!isa<ConstantInt>(BI->getCondition())) {
1954
1
      // Indeterminate branch; use false.
1955
1
      Dest = BI->getSuccessor(1);
1956
1
      C = ConstantInt::getFalse(BI->getContext());
1957
1
    }
1958
12.2k
  } else 
if (IndirectBrInst *0
IBR0
= dyn_cast<IndirectBrInst>(I)) {
1959
0
    if (!isa<BlockAddress>(IBR->getAddress()->stripPointerCasts())) {
1960
0
      // Indeterminate indirectbr; use successor 0.
1961
0
      Dest = IBR->getSuccessor(0);
1962
0
      C = BlockAddress::get(IBR->getSuccessor(0));
1963
0
    }
1964
0
  } else {
1965
0
    llvm_unreachable("Unexpected terminator instruction");
1966
0
  }
1967
12.2k
  if (C) {
1968
3
    assert(Solver.isEdgeFeasible(I->getParent(), Dest) &&
1969
3
           "Didn't find feasible edge?");
1970
3
    (void)Dest;
1971
3
1972
3
    I->setOperand(0, C);
1973
3
  }
1974
12.2k
}
1975
1976
bool llvm::runIPSCCP(
1977
    Module &M, const DataLayout &DL, const TargetLibraryInfo *TLI,
1978
13.6k
    function_ref<AnalysisResultsForFn(Function &)> getAnalysis) {
1979
13.6k
  SCCPSolver Solver(DL, TLI);
1980
13.6k
1981
13.6k
  // Loop over all functions, marking arguments to those with their addresses
1982
13.6k
  // taken or that are external as overdefined.
1983
1.51M
  for (Function &F : M) {
1984
1.51M
    if (F.isDeclaration())
1985
919k
      continue;
1986
590k
1987
590k
    Solver.addAnalysis(F, getAnalysis(F));
1988
590k
1989
590k
    // Determine if we can track the function's return values. If so, add the
1990
590k
    // function to the solver's set of return-tracked functions.
1991
590k
    if (canTrackReturnsInterprocedurally(&F))
1992
98.5k
      Solver.AddTrackedFunction(&F);
1993
590k
1994
590k
    // Determine if we can track the function's arguments. If so, add the
1995
590k
    // function to the solver's set of argument-tracked functions.
1996
590k
    if (canTrackArgumentsInterprocedurally(&F)) {
1997
25.3k
      Solver.AddArgumentTrackedFunction(&F);
1998
25.3k
      continue;
1999
25.3k
    }
2000
565k
2001
565k
    // Assume the function is called.
2002
565k
    Solver.MarkBlockExecutable(&F.front());
2003
565k
2004
565k
    // Assume nothing about the incoming arguments.
2005
565k
    for (Argument &AI : F.args())
2006
1.05M
      Solver.markOverdefined(&AI);
2007
565k
  }
2008
13.6k
2009
13.6k
  // Determine if we can track any of the module's global variables. If so, add
2010
13.6k
  // the global variables we can track to the solver's set of tracked global
2011
13.6k
  // variables.
2012
453k
  for (GlobalVariable &G : M.globals()) {
2013
453k
    G.removeDeadConstantUsers();
2014
453k
    if (canTrackGlobalVariableInterprocedurally(&G))
2015
4.79k
      Solver.TrackValueOfGlobalVariable(&G);
2016
453k
  }
2017
13.6k
2018
13.6k
  // Solve for constants.
2019
13.6k
  bool ResolvedUndefs = true;
2020
13.6k
  Solver.Solve();
2021
27.3k
  while (ResolvedUndefs) {
2022
13.7k
    LLVM_DEBUG(dbgs() << "RESOLVING UNDEFS\n");
2023
13.7k
    ResolvedUndefs = false;
2024
13.7k
    for (Function &F : M)
2025
1.52M
      if (Solver.ResolvedUndefsIn(F)) {
2026
158
        // We run Solve() after we resolved an undef in a function, because
2027
158
        // we might deduce a fact that eliminates an undef in another function.
2028
158
        Solver.Solve();
2029
158
        ResolvedUndefs = true;
2030
158
      }
2031
13.7k
  }
2032
13.6k
2033
13.6k
  bool MadeChanges = false;
2034
13.6k
2035
13.6k
  // Iterate over all of the instructions in the module, replacing them with
2036
13.6k
  // constants if we have found them to be of constant values.
2037
13.6k
2038
1.51M
  for (Function &F : M) {
2039
1.51M
    if (F.isDeclaration())
2040
919k
      continue;
2041
590k
2042
590k
    SmallVector<BasicBlock *, 512> BlocksToErase;
2043
590k
2044
590k
    if (Solver.isBlockExecutable(&F.front()))
2045
1.69M
      
for (Function::arg_iterator AI = F.arg_begin(), E = F.arg_end(); 590k
AI != E;
2046
1.10M
           ++AI) {
2047
1.10M
        if (!AI->use_empty() && 
tryToReplaceWithConstant(Solver, &*AI)1.05M
) {
2048
2.38k
          ++IPNumArgsElimed;
2049
2.38k
          continue;
2050
2.38k
        }
2051
1.10M
      }
2052
590k
2053
3.01M
    for (Function::iterator BB = F.begin(), E = F.end(); BB != E; 
++BB2.42M
) {
2054
2.42M
      if (!Solver.isBlockExecutable(&*BB)) {
2055
13.2k
        LLVM_DEBUG(dbgs() << "  BasicBlock Dead:" << *BB);
2056
13.2k
        ++NumDeadBlocks;
2057
13.2k
2058
13.2k
        MadeChanges = true;
2059
13.2k
2060
13.2k
        if (&*BB != &F.front())
2061
13.2k
          BlocksToErase.push_back(&*BB);
2062
13.2k
        continue;
2063
13.2k
      }
2064
2.40M
2065
15.9M
      
for (BasicBlock::iterator BI = BB->begin(), E = BB->end(); 2.40M
BI != E; ) {
2066
13.5M
        Instruction *Inst = &*BI++;
2067
13.5M
        if (Inst->getType()->isVoidTy())
2068
3.98M
          continue;
2069
9.56M
        if (tryToReplaceWithConstant(Solver, Inst)) {
2070
34.2k
          if (Inst->isSafeToRemove())
2071
14.7k
            Inst->eraseFromParent();
2072
34.2k
          // Hey, we just changed something!
2073
34.2k
          MadeChanges = true;
2074
34.2k
          ++IPNumInstRemoved;
2075
34.2k
        }
2076
9.56M
      }
2077
2.40M
    }
2078
590k
2079
590k
    DomTreeUpdater DTU = Solver.getDTU(F);
2080
590k
    // Change dead blocks to unreachable. We do it after replacing constants
2081
590k
    // in all executable blocks, because changeToUnreachable may remove PHI
2082
590k
    // nodes in executable blocks we found values for. The function's entry
2083
590k
    // block is not part of BlocksToErase, so we have to handle it separately.
2084
590k
    for (BasicBlock *BB : BlocksToErase) {
2085
13.2k
      NumInstRemoved +=
2086
13.2k
          changeToUnreachable(BB->getFirstNonPHI(), /*UseLLVMTrap=*/false,
2087
13.2k
                              /*PreserveLCSSA=*/false, &DTU);
2088
13.2k
    }
2089
590k
    if (!Solver.isBlockExecutable(&F.front()))
2090
40
      NumInstRemoved += changeToUnreachable(F.front().getFirstNonPHI(),
2091
40
                                            /*UseLLVMTrap=*/false,
2092
40
                                            /*PreserveLCSSA=*/false, &DTU);
2093
590k
2094
590k
    // Now that all instructions in the function are constant folded,
2095
590k
    // use ConstantFoldTerminator to get rid of in-edges, record DT updates and
2096
590k
    // delete dead BBs.
2097
590k
    for (BasicBlock *DeadBB : BlocksToErase) {
2098
13.2k
      // If there are any PHI nodes in this successor, drop entries for BB now.
2099
13.2k
      for (Value::user_iterator UI = DeadBB->user_begin(),
2100
13.2k
                                UE = DeadBB->user_end();
2101
25.5k
           UI != UE;) {
2102
12.2k
        // Grab the user and then increment the iterator early, as the user
2103
12.2k
        // will be deleted. Step past all adjacent uses from the same user.
2104
12.2k
        auto *I = dyn_cast<Instruction>(*UI);
2105
12.2k
        do { ++UI; } while (UI != UE && 
*UI == I59
);
2106
12.2k
2107
12.2k
        // Ignore blockaddress users; BasicBlock's dtor will handle them.
2108
12.2k
        if (!I) 
continue2
;
2109
12.2k
2110
12.2k
        // If we have forced an edge for an indeterminate value, then force the
2111
12.2k
        // terminator to fold to that edge.
2112
12.2k
        forceIndeterminateEdge(I, Solver);
2113
12.2k
        BasicBlock *InstBB = I->getParent();
2114
12.2k
        bool Folded = ConstantFoldTerminator(InstBB,
2115
12.2k
                                             /*DeleteDeadConditions=*/false,
2116
12.2k
                                             /*TLI=*/nullptr, &DTU);
2117
12.2k
        assert(Folded &&
2118
12.2k
              "Expect TermInst on constantint or blockaddress to be folded");
2119
12.2k
        (void) Folded;
2120
12.2k
        // If we folded the terminator to an unconditional branch to another
2121
12.2k
        // dead block, replace it with Unreachable, to avoid trying to fold that
2122
12.2k
        // branch again.
2123
12.2k
        BranchInst *BI = cast<BranchInst>(InstBB->getTerminator());
2124
12.2k
        if (BI && BI->isUnconditional() &&
2125
12.2k
            !Solver.isBlockExecutable(BI->getSuccessor(0))) {
2126
4
          InstBB->getTerminator()->eraseFromParent();
2127
4
          new UnreachableInst(InstBB->getContext(), InstBB);
2128
4
        }
2129
12.2k
      }
2130
13.2k
      // Mark dead BB for deletion.
2131
13.2k
      DTU.deleteBB(DeadBB);
2132
13.2k
    }
2133
590k
2134
2.42M
    for (BasicBlock &BB : F) {
2135
15.9M
      for (BasicBlock::iterator BI = BB.begin(), E = BB.end(); BI != E;) {
2136
13.5M
        Instruction *Inst = &*BI++;
2137
13.5M
        if (Solver.getPredicateInfoFor(Inst)) {
2138
512k
          if (auto *II = dyn_cast<IntrinsicInst>(Inst)) {
2139
512k
            if (II->getIntrinsicID() == Intrinsic::ssa_copy) {
2140
512k
              Value *Op = II->getOperand(0);
2141
512k
              Inst->replaceAllUsesWith(Op);
2142
512k
              Inst->eraseFromParent();
2143
512k
            }
2144
512k
          }
2145
512k
        }
2146
13.5M
      }
2147
2.42M
    }
2148
590k
  }
2149
13.6k
2150
13.6k
  // If we inferred constant or undef return values for a function, we replaced
2151
13.6k
  // all call uses with the inferred value.  This means we don't need to bother
2152
13.6k
  // actually returning anything from the function.  Replace all return
2153
13.6k
  // instructions with return undef.
2154
13.6k
  //
2155
13.6k
  // Do this in two stages: first identify the functions we should process, then
2156
13.6k
  // actually zap their returns.  This is important because we can only do this
2157
13.6k
  // if the address of the function isn't taken.  In cases where a return is the
2158
13.6k
  // last use of a function, the order of processing functions would affect
2159
13.6k
  // whether other functions are optimizable.
2160
13.6k
  SmallVector<ReturnInst*, 8> ReturnsToZap;
2161
13.6k
2162
13.6k
  const MapVector<Function*, LatticeVal> &RV = Solver.getTrackedRetVals();
2163
97.7k
  for (const auto &I : RV) {
2164
97.7k
    Function *F = I.first;
2165
97.7k
    if (I.second.isOverdefined() || 
F->getReturnType()->isVoidTy()44.4k
)
2166
90.0k
      continue;
2167
7.62k
    findReturnsToZap(*F, ReturnsToZap, Solver);
2168
7.62k
  }
2169
13.6k
2170
13.6k
  for (const auto &F : Solver.getMRVFunctionsTracked()) {
2171
866
    assert(F->getReturnType()->isStructTy() &&
2172
866
           "The return type should be a struct");
2173
866
    StructType *STy = cast<StructType>(F->getReturnType());
2174
866
    if (Solver.isStructLatticeConstant(F, STy))
2175
26
      findReturnsToZap(*F, ReturnsToZap, Solver);
2176
866
  }
2177
13.6k
2178
13.6k
  // Zap all returns which we've identified as zap to change.
2179
14.3k
  for (unsigned i = 0, e = ReturnsToZap.size(); i != e; 
++i730
) {
2180
730
    Function *F = ReturnsToZap[i]->getParent()->getParent();
2181
730
    ReturnsToZap[i]->setOperand(0, UndefValue::get(F->getReturnType()));
2182
730
  }
2183
13.6k
2184
13.6k
  // If we inferred constant or undef values for globals variables, we can
2185
13.6k
  // delete the global and any stores that remain to it.
2186
13.6k
  const DenseMap<GlobalVariable*, LatticeVal> &TG = Solver.getTrackedGlobals();
2187
13.6k
  for (DenseMap<GlobalVariable*, LatticeVal>::const_iterator I = TG.begin(),
2188
13.9k
         E = TG.end(); I != E; 
++I351
) {
2189
351
    GlobalVariable *GV = I->first;
2190
351
    assert(!I->second.isOverdefined() &&
2191
351
           "Overdefined values should have been taken out of the map!");
2192
351
    LLVM_DEBUG(dbgs() << "Found that GV '" << GV->getName()
2193
351
                      << "' is constant!\n");
2194
405
    while (!GV->use_empty()) {
2195
54
      StoreInst *SI = cast<StoreInst>(GV->user_back());
2196
54
      SI->eraseFromParent();
2197
54
    }
2198
351
    M.getGlobalList().erase(GV);
2199
351
    ++IPNumGlobalConst;
2200
351
  }
2201
13.6k
2202
13.6k
  return MadeChanges;
2203
13.6k
}