Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Analysis/LazyValueInfo.cpp
Line
Count
Source (jump to first uncovered line)
1
//===- LazyValueInfo.cpp - Value constraint analysis ------------*- C++ -*-===//
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 defines the interface for lazy computation of value constraint
10
// information.
11
//
12
//===----------------------------------------------------------------------===//
13
14
#include "llvm/Analysis/LazyValueInfo.h"
15
#include "llvm/ADT/DenseSet.h"
16
#include "llvm/ADT/Optional.h"
17
#include "llvm/ADT/STLExtras.h"
18
#include "llvm/Analysis/AssumptionCache.h"
19
#include "llvm/Analysis/ConstantFolding.h"
20
#include "llvm/Analysis/InstructionSimplify.h"
21
#include "llvm/Analysis/TargetLibraryInfo.h"
22
#include "llvm/Analysis/ValueTracking.h"
23
#include "llvm/Analysis/ValueLattice.h"
24
#include "llvm/IR/AssemblyAnnotationWriter.h"
25
#include "llvm/IR/CFG.h"
26
#include "llvm/IR/ConstantRange.h"
27
#include "llvm/IR/Constants.h"
28
#include "llvm/IR/DataLayout.h"
29
#include "llvm/IR/Dominators.h"
30
#include "llvm/IR/Instructions.h"
31
#include "llvm/IR/IntrinsicInst.h"
32
#include "llvm/IR/Intrinsics.h"
33
#include "llvm/IR/LLVMContext.h"
34
#include "llvm/IR/PatternMatch.h"
35
#include "llvm/IR/ValueHandle.h"
36
#include "llvm/Support/Debug.h"
37
#include "llvm/Support/FormattedStream.h"
38
#include "llvm/Support/raw_ostream.h"
39
#include <map>
40
using namespace llvm;
41
using namespace PatternMatch;
42
43
#define DEBUG_TYPE "lazy-value-info"
44
45
// This is the number of worklist items we will process to try to discover an
46
// answer for a given value.
47
static const unsigned MaxProcessedPerValue = 500;
48
49
char LazyValueInfoWrapperPass::ID = 0;
50
48.9k
INITIALIZE_PASS_BEGIN(LazyValueInfoWrapperPass, "lazy-value-info",
51
48.9k
                "Lazy Value Information Analysis", false, true)
52
48.9k
INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
53
48.9k
INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
54
48.9k
INITIALIZE_PASS_END(LazyValueInfoWrapperPass, "lazy-value-info",
55
                "Lazy Value Information Analysis", false, true)
56
57
namespace llvm {
58
0
  FunctionPass *createLazyValueInfoPass() { return new LazyValueInfoWrapperPass(); }
59
}
60
61
AnalysisKey LazyValueAnalysis::Key;
62
63
/// Returns true if this lattice value represents at most one possible value.
64
/// This is as precise as any lattice value can get while still representing
65
/// reachable code.
66
36.8M
static bool hasSingleValue(const ValueLatticeElement &Val) {
67
36.8M
  if (Val.isConstantRange() &&
68
36.8M
      
Val.getConstantRange().isSingleElement()3.18M
)
69
129k
    // Integer constants are single element ranges
70
129k
    return true;
71
36.7M
  if (Val.isConstant())
72
18.3k
    // Non integer constants
73
18.3k
    return true;
74
36.7M
  return false;
75
36.7M
}
76
77
/// Combine two sets of facts about the same value into a single set of
78
/// facts.  Note that this method is not suitable for merging facts along
79
/// different paths in a CFG; that's what the mergeIn function is for.  This
80
/// is for merging facts gathered about the same value at the same location
81
/// through two independent means.
82
/// Notes:
83
/// * This method does not promise to return the most precise possible lattice
84
///   value implied by A and B.  It is allowed to return any lattice element
85
///   which is at least as strong as *either* A or B (unless our facts
86
///   conflict, see below).
87
/// * Due to unreachable code, the intersection of two lattice values could be
88
///   contradictory.  If this happens, we return some valid lattice value so as
89
///   not confuse the rest of LVI.  Ideally, we'd always return Undefined, but
90
///   we do not make this guarantee.  TODO: This would be a useful enhancement.
91
static ValueLatticeElement intersect(const ValueLatticeElement &A,
92
23.1M
                                     const ValueLatticeElement &B) {
93
23.1M
  // Undefined is the strongest state.  It means the value is known to be along
94
23.1M
  // an unreachable path.
95
23.1M
  if (A.isUndefined())
96
4
    return A;
97
23.1M
  if (B.isUndefined())
98
162k
    return B;
99
22.9M
100
22.9M
  // If we gave up for one, but got a useable fact from the other, use it.
101
22.9M
  if (A.isOverdefined())
102
21.4M
    return B;
103
1.50M
  if (B.isOverdefined())
104
883k
    return A;
105
621k
106
621k
  // Can't get any more precise than constants.
107
621k
  if (hasSingleValue(A))
108
16.5k
    return A;
109
605k
  if (hasSingleValue(B))
110
71
    return B;
111
605k
112
605k
  // Could be either constant range or not constant here.
113
605k
  if (!A.isConstantRange() || 
!B.isConstantRange()603k
) {
114
1.50k
    // TODO: Arbitrary choice, could be improved
115
1.50k
    return A;
116
1.50k
  }
117
603k
118
603k
  // Intersect two constant ranges
119
603k
  ConstantRange Range =
120
603k
    A.getConstantRange().intersectWith(B.getConstantRange());
121
603k
  // Note: An empty range is implicitly converted to overdefined internally.
122
603k
  // TODO: We could instead use Undefined here since we've proven a conflict
123
603k
  // and thus know this path must be unreachable.
124
603k
  return ValueLatticeElement::getRange(std::move(Range));
125
603k
}
126
127
//===----------------------------------------------------------------------===//
128
//                          LazyValueInfoCache Decl
129
//===----------------------------------------------------------------------===//
130
131
namespace {
132
  /// A callback value handle updates the cache when values are erased.
133
  class LazyValueInfoCache;
134
  struct LVIValueHandle final : public CallbackVH {
135
    // Needs to access getValPtr(), which is protected.
136
    friend struct DenseMapInfo<LVIValueHandle>;
137
138
    LazyValueInfoCache *Parent;
139
140
    LVIValueHandle(Value *V, LazyValueInfoCache *P)
141
5.34M
      : CallbackVH(V), Parent(P) { }
142
143
    void deleted() override;
144
7.95k
    void allUsesReplacedWith(Value *V) override {
145
7.95k
      deleted();
146
7.95k
    }
147
  };
148
} // end anonymous namespace
149
150
namespace {
151
  /// This is the cache kept by LazyValueInfo which
152
  /// maintains information about queries across the clients' queries.
153
  class LazyValueInfoCache {
154
    /// This is all of the cached block information for exactly one Value*.
155
    /// The entries are sorted by the BasicBlock* of the
156
    /// entries, allowing us to do a lookup with a binary search.
157
    /// Over-defined lattice values are recorded in OverDefinedCache to reduce
158
    /// memory overhead.
159
    struct ValueCacheEntryTy {
160
5.34M
      ValueCacheEntryTy(Value *V, LazyValueInfoCache *P) : Handle(V, P) {}
161
      LVIValueHandle Handle;
162
      SmallDenseMap<PoisoningVH<BasicBlock>, ValueLatticeElement, 4> BlockVals;
163
    };
164
165
    /// This tracks, on a per-block basis, the set of values that are
166
    /// over-defined at the end of that block.
167
    typedef DenseMap<PoisoningVH<BasicBlock>, SmallPtrSet<Value *, 4>>
168
        OverDefinedCacheTy;
169
    /// Keep track of all blocks that we have ever seen, so we
170
    /// don't spend time removing unused blocks from our caches.
171
    DenseSet<PoisoningVH<BasicBlock> > SeenBlocks;
172
173
    /// This is all of the cached information for all values,
174
    /// mapped from Value* to key information.
175
    DenseMap<Value *, std::unique_ptr<ValueCacheEntryTy>> ValueCache;
176
    OverDefinedCacheTy OverDefinedCache;
177
178
179
  public:
180
    void insertResult(Value *Val, BasicBlock *BB,
181
21.8M
                      const ValueLatticeElement &Result) {
182
21.8M
      SeenBlocks.insert(BB);
183
21.8M
184
21.8M
      // Insert over-defined values into their own cache to reduce memory
185
21.8M
      // overhead.
186
21.8M
      if (Result.isOverdefined())
187
11.6M
        OverDefinedCache[BB].insert(Val);
188
10.1M
      else {
189
10.1M
        auto It = ValueCache.find_as(Val);
190
10.1M
        if (It == ValueCache.end()) {
191
5.34M
          ValueCache[Val] = make_unique<ValueCacheEntryTy>(Val, this);
192
5.34M
          It = ValueCache.find_as(Val);
193
5.34M
          assert(It != ValueCache.end() && "Val was just added to the map!");
194
5.34M
        }
195
10.1M
        It->second->BlockVals[BB] = Result;
196
10.1M
      }
197
21.8M
    }
198
199
115M
    bool isOverdefined(Value *V, BasicBlock *BB) const {
200
115M
      auto ODI = OverDefinedCache.find(BB);
201
115M
202
115M
      if (ODI == OverDefinedCache.end())
203
24.7M
        return false;
204
90.6M
205
90.6M
      return ODI->second.count(V);
206
90.6M
    }
207
208
82.8M
    bool hasCachedValueInfo(Value *V, BasicBlock *BB) const {
209
82.8M
      if (isOverdefined(V, BB))
210
14.3M
        return true;
211
68.4M
212
68.4M
      auto I = ValueCache.find_as(V);
213
68.4M
      if (I == ValueCache.end())
214
41.1M
        return false;
215
27.3M
216
27.3M
      return I->second->BlockVals.count(BB);
217
27.3M
    }
218
219
32.5M
    ValueLatticeElement getCachedValueInfo(Value *V, BasicBlock *BB) const {
220
32.5M
      if (isOverdefined(V, BB))
221
16.8M
        return ValueLatticeElement::getOverdefined();
222
15.7M
223
15.7M
      auto I = ValueCache.find_as(V);
224
15.7M
      if (I == ValueCache.end())
225
0
        return ValueLatticeElement();
226
15.7M
      auto BBI = I->second->BlockVals.find(BB);
227
15.7M
      if (BBI == I->second->BlockVals.end())
228
0
        return ValueLatticeElement();
229
15.7M
      return BBI->second;
230
15.7M
    }
231
232
    /// clear - Empty the cache.
233
0
    void clear() {
234
0
      SeenBlocks.clear();
235
0
      ValueCache.clear();
236
0
      OverDefinedCache.clear();
237
0
    }
238
239
    /// Inform the cache that a given value has been deleted.
240
    void eraseValue(Value *V);
241
242
    /// This is part of the update interface to inform the cache
243
    /// that a block has been deleted.
244
    void eraseBlock(BasicBlock *BB);
245
246
    /// Updates the cache to remove any influence an overdefined value in
247
    /// OldSucc might have (unless also overdefined in NewSucc).  This just
248
    /// flushes elements from the cache and does not add any.
249
    void threadEdgeImpl(BasicBlock *OldSucc,BasicBlock *NewSucc);
250
251
    friend struct LVIValueHandle;
252
  };
253
}
254
255
9.00k
void LazyValueInfoCache::eraseValue(Value *V) {
256
352k
  for (auto I = OverDefinedCache.begin(), E = OverDefinedCache.end(); I != E;) {
257
343k
    // Copy and increment the iterator immediately so we can erase behind
258
343k
    // ourselves.
259
343k
    auto Iter = I++;
260
343k
    SmallPtrSetImpl<Value *> &ValueSet = Iter->second;
261
343k
    ValueSet.erase(V);
262
343k
    if (ValueSet.empty())
263
631
      OverDefinedCache.erase(Iter);
264
343k
  }
265
9.00k
266
9.00k
  ValueCache.erase(V);
267
9.00k
}
268
269
9.00k
void LVIValueHandle::deleted() {
270
9.00k
  // This erasure deallocates *this, so it MUST happen after we're done
271
9.00k
  // using any and all members of *this.
272
9.00k
  Parent->eraseValue(*this);
273
9.00k
}
274
275
342k
void LazyValueInfoCache::eraseBlock(BasicBlock *BB) {
276
342k
  // Shortcut if we have never seen this block.
277
342k
  DenseSet<PoisoningVH<BasicBlock> >::iterator I = SeenBlocks.find(BB);
278
342k
  if (I == SeenBlocks.end())
279
295k
    return;
280
46.6k
  SeenBlocks.erase(I);
281
46.6k
282
46.6k
  auto ODI = OverDefinedCache.find(BB);
283
46.6k
  if (ODI != OverDefinedCache.end())
284
34.2k
    OverDefinedCache.erase(ODI);
285
46.6k
286
46.6k
  for (auto &I : ValueCache)
287
463k
    I.second->BlockVals.erase(BB);
288
46.6k
}
289
290
void LazyValueInfoCache::threadEdgeImpl(BasicBlock *OldSucc,
291
48.6k
                                        BasicBlock *NewSucc) {
292
48.6k
  // When an edge in the graph has been threaded, values that we could not
293
48.6k
  // determine a value for before (i.e. were marked overdefined) may be
294
48.6k
  // possible to solve now. We do NOT try to proactively update these values.
295
48.6k
  // Instead, we clear their entries from the cache, and allow lazy updating to
296
48.6k
  // recompute them when needed.
297
48.6k
298
48.6k
  // The updating process is fairly simple: we need to drop cached info
299
48.6k
  // for all values that were marked overdefined in OldSucc, and for those same
300
48.6k
  // values in any successor of OldSucc (except NewSucc) in which they were
301
48.6k
  // also marked overdefined.
302
48.6k
  std::vector<BasicBlock*> worklist;
303
48.6k
  worklist.push_back(OldSucc);
304
48.6k
305
48.6k
  auto I = OverDefinedCache.find(OldSucc);
306
48.6k
  if (I == OverDefinedCache.end())
307
44.4k
    return; // Nothing to process here.
308
4.19k
  SmallVector<Value *, 4> ValsToClear(I->second.begin(), I->second.end());
309
4.19k
310
4.19k
  // Use a worklist to perform a depth-first search of OldSucc's successors.
311
4.19k
  // NOTE: We do not need a visited list since any blocks we have already
312
4.19k
  // visited will have had their overdefined markers cleared already, and we
313
4.19k
  // thus won't loop to their successors.
314
30.8k
  while (!worklist.empty()) {
315
26.6k
    BasicBlock *ToUpdate = worklist.back();
316
26.6k
    worklist.pop_back();
317
26.6k
318
26.6k
    // Skip blocks only accessible through NewSucc.
319
26.6k
    if (ToUpdate == NewSucc) 
continue4.73k
;
320
21.8k
321
21.8k
    // If a value was marked overdefined in OldSucc, and is here too...
322
21.8k
    auto OI = OverDefinedCache.find(ToUpdate);
323
21.8k
    if (OI == OverDefinedCache.end())
324
7.85k
      continue;
325
14.0k
    SmallPtrSetImpl<Value *> &ValueSet = OI->second;
326
14.0k
327
14.0k
    bool changed = false;
328
25.4k
    for (Value *V : ValsToClear) {
329
25.4k
      if (!ValueSet.erase(V))
330
10.0k
        continue;
331
15.3k
332
15.3k
      // If we removed anything, then we potentially need to update
333
15.3k
      // blocks successors too.
334
15.3k
      changed = true;
335
15.3k
336
15.3k
      if (ValueSet.empty()) {
337
9.25k
        OverDefinedCache.erase(OI);
338
9.25k
        break;
339
9.25k
      }
340
15.3k
    }
341
14.0k
342
14.0k
    if (!changed) 
continue1.75k
;
343
12.2k
344
12.2k
    worklist.insert(worklist.end(), succ_begin(ToUpdate), succ_end(ToUpdate));
345
12.2k
  }
346
4.19k
}
347
348
349
namespace {
350
/// An assembly annotator class to print LazyValueCache information in
351
/// comments.
352
class LazyValueInfoImpl;
353
class LazyValueInfoAnnotatedWriter : public AssemblyAnnotationWriter {
354
  LazyValueInfoImpl *LVIImpl;
355
  // While analyzing which blocks we can solve values for, we need the dominator
356
  // information. Since this is an optional parameter in LVI, we require this
357
  // DomTreeAnalysis pass in the printer pass, and pass the dominator
358
  // tree to the LazyValueInfoAnnotatedWriter.
359
  DominatorTree &DT;
360
361
public:
362
  LazyValueInfoAnnotatedWriter(LazyValueInfoImpl *L, DominatorTree &DTree)
363
4
      : LVIImpl(L), DT(DTree) {}
364
365
  virtual void emitBasicBlockStartAnnot(const BasicBlock *BB,
366
                                        formatted_raw_ostream &OS);
367
368
  virtual void emitInstructionAnnot(const Instruction *I,
369
                                    formatted_raw_ostream &OS);
370
};
371
}
372
namespace {
373
  // The actual implementation of the lazy analysis and update.  Note that the
374
  // inheritance from LazyValueInfoCache is intended to be temporary while
375
  // splitting the code and then transitioning to a has-a relationship.
376
  class LazyValueInfoImpl {
377
378
    /// Cached results from previous queries
379
    LazyValueInfoCache TheCache;
380
381
    /// This stack holds the state of the value solver during a query.
382
    /// It basically emulates the callstack of the naive
383
    /// recursive value lookup process.
384
    SmallVector<std::pair<BasicBlock*, Value*>, 8> BlockValueStack;
385
386
    /// Keeps track of which block-value pairs are in BlockValueStack.
387
    DenseSet<std::pair<BasicBlock*, Value*> > BlockValueSet;
388
389
    /// Push BV onto BlockValueStack unless it's already in there.
390
    /// Returns true on success.
391
22.9M
    bool pushBlockValue(const std::pair<BasicBlock *, Value *> &BV) {
392
22.9M
      if (!BlockValueSet.insert(BV).second)
393
1.01M
        return false;  // It's already in the stack.
394
21.9M
395
21.9M
      LLVM_DEBUG(dbgs() << "PUSH: " << *BV.second << " in "
396
21.9M
                        << BV.first->getName() << "\n");
397
21.9M
      BlockValueStack.push_back(BV);
398
21.9M
      return true;
399
21.9M
    }
400
401
    AssumptionCache *AC;  ///< A pointer to the cache of @llvm.assume calls.
402
    const DataLayout &DL; ///< A mandatory DataLayout
403
    DominatorTree *DT;    ///< An optional DT pointer.
404
    DominatorTree *DisabledDT; ///< Stores DT if it's disabled.
405
406
  ValueLatticeElement getBlockValue(Value *Val, BasicBlock *BB);
407
  bool getEdgeValue(Value *V, BasicBlock *F, BasicBlock *T,
408
                    ValueLatticeElement &Result, Instruction *CxtI = nullptr);
409
  bool hasBlockValue(Value *Val, BasicBlock *BB);
410
411
  // These methods process one work item and may add more. A false value
412
  // returned means that the work item was not completely processed and must
413
  // be revisited after going through the new items.
414
  bool solveBlockValue(Value *Val, BasicBlock *BB);
415
  bool solveBlockValueImpl(ValueLatticeElement &Res, Value *Val,
416
                           BasicBlock *BB);
417
  bool solveBlockValueNonLocal(ValueLatticeElement &BBLV, Value *Val,
418
                               BasicBlock *BB);
419
  bool solveBlockValuePHINode(ValueLatticeElement &BBLV, PHINode *PN,
420
                              BasicBlock *BB);
421
  bool solveBlockValueSelect(ValueLatticeElement &BBLV, SelectInst *S,
422
                             BasicBlock *BB);
423
  Optional<ConstantRange> getRangeForOperand(unsigned Op, Instruction *I,
424
                                             BasicBlock *BB);
425
  bool solveBlockValueBinaryOpImpl(
426
      ValueLatticeElement &BBLV, Instruction *I, BasicBlock *BB,
427
      std::function<ConstantRange(const ConstantRange &,
428
                                  const ConstantRange &)> OpFn);
429
  bool solveBlockValueBinaryOp(ValueLatticeElement &BBLV, BinaryOperator *BBI,
430
                               BasicBlock *BB);
431
  bool solveBlockValueCast(ValueLatticeElement &BBLV, CastInst *CI,
432
                           BasicBlock *BB);
433
  bool solveBlockValueOverflowIntrinsic(
434
      ValueLatticeElement &BBLV, WithOverflowInst *WO, BasicBlock *BB);
435
  bool solveBlockValueIntrinsic(ValueLatticeElement &BBLV, IntrinsicInst *II,
436
                                BasicBlock *BB);
437
  void intersectAssumeOrGuardBlockValueConstantRange(Value *Val,
438
                                                     ValueLatticeElement &BBLV,
439
                                                     Instruction *BBI);
440
441
  void solve();
442
443
  public:
444
    /// This is the query interface to determine the lattice
445
    /// value for the specified Value* at the end of the specified block.
446
    ValueLatticeElement getValueInBlock(Value *V, BasicBlock *BB,
447
                                        Instruction *CxtI = nullptr);
448
449
    /// This is the query interface to determine the lattice
450
    /// value for the specified Value* at the specified instruction (generally
451
    /// from an assume intrinsic).
452
    ValueLatticeElement getValueAt(Value *V, Instruction *CxtI);
453
454
    /// This is the query interface to determine the lattice
455
    /// value for the specified Value* that is true on the specified edge.
456
    ValueLatticeElement getValueOnEdge(Value *V, BasicBlock *FromBB,
457
                                       BasicBlock *ToBB,
458
                                   Instruction *CxtI = nullptr);
459
460
    /// Complete flush all previously computed values
461
0
    void clear() {
462
0
      TheCache.clear();
463
0
    }
464
465
    /// Printing the LazyValueInfo Analysis.
466
4
    void printLVI(Function &F, DominatorTree &DTree, raw_ostream &OS) {
467
4
        LazyValueInfoAnnotatedWriter Writer(this, DTree);
468
4
        F.print(OS, &Writer);
469
4
    }
470
471
    /// This is part of the update interface to inform the cache
472
    /// that a block has been deleted.
473
342k
    void eraseBlock(BasicBlock *BB) {
474
342k
      TheCache.eraseBlock(BB);
475
342k
    }
476
477
    /// Disables use of the DominatorTree within LVI.
478
4.07M
    void disableDT() {
479
4.07M
      if (DT) {
480
91.3k
        assert(!DisabledDT && "Both DT and DisabledDT are not nullptr!");
481
91.3k
        std::swap(DT, DisabledDT);
482
91.3k
      }
483
4.07M
    }
484
485
    /// Enables use of the DominatorTree within LVI. Does nothing if the class
486
    /// instance was initialized without a DT pointer.
487
2.56M
    void enableDT() {
488
2.56M
      if (DisabledDT) {
489
91.3k
        assert(!DT && "Both DT and DisabledDT are not nullptr!");
490
91.3k
        std::swap(DT, DisabledDT);
491
91.3k
      }
492
2.56M
    }
493
494
    /// This is the update interface to inform the cache that an edge from
495
    /// PredBB to OldSucc has been threaded to be from PredBB to NewSucc.
496
    void threadEdge(BasicBlock *PredBB,BasicBlock *OldSucc,BasicBlock *NewSucc);
497
498
    LazyValueInfoImpl(AssumptionCache *AC, const DataLayout &DL,
499
                       DominatorTree *DT = nullptr)
500
854k
        : AC(AC), DL(DL), DT(DT), DisabledDT(nullptr) {}
501
  };
502
} // end anonymous namespace
503
504
505
10.4M
void LazyValueInfoImpl::solve() {
506
10.4M
  SmallVector<std::pair<BasicBlock *, Value *>, 8> StartingStack(
507
10.4M
      BlockValueStack.begin(), BlockValueStack.end());
508
10.4M
509
10.4M
  unsigned processedCount = 0;
510
43.5M
  while (!BlockValueStack.empty()) {
511
33.0M
    processedCount++;
512
33.0M
    // Abort if we have to process too many values to get a result for this one.
513
33.0M
    // Because of the design of the overdefined cache currently being per-block
514
33.0M
    // to avoid naming-related issues (IE it wants to try to give different
515
33.0M
    // results for the same name in different blocks), overdefined results don't
516
33.0M
    // get cached globally, which in turn means we will often try to rediscover
517
33.0M
    // the same overdefined result again and again.  Once something like
518
33.0M
    // PredicateInfo is used in LVI or CVP, we should be able to make the
519
33.0M
    // overdefined cache global, and remove this throttle.
520
33.0M
    if (processedCount > MaxProcessedPerValue) {
521
652
      LLVM_DEBUG(
522
652
          dbgs() << "Giving up on stack because we are getting too deep\n");
523
652
      // Fill in the original values
524
1.30k
      while (!StartingStack.empty()) {
525
652
        std::pair<BasicBlock *, Value *> &e = StartingStack.back();
526
652
        TheCache.insertResult(e.second, e.first,
527
652
                              ValueLatticeElement::getOverdefined());
528
652
        StartingStack.pop_back();
529
652
      }
530
652
      BlockValueSet.clear();
531
652
      BlockValueStack.clear();
532
652
      return;
533
652
    }
534
33.0M
    std::pair<BasicBlock *, Value *> e = BlockValueStack.back();
535
33.0M
    assert(BlockValueSet.count(e) && "Stack value should be in BlockValueSet!");
536
33.0M
537
33.0M
    if (solveBlockValue(e.second, e.first)) {
538
21.8M
      // The work item was completely processed.
539
21.8M
      assert(BlockValueStack.back() == e && "Nothing should have been pushed!");
540
21.8M
      assert(TheCache.hasCachedValueInfo(e.second, e.first) &&
541
21.8M
             "Result should be in cache!");
542
21.8M
543
21.8M
      LLVM_DEBUG(
544
21.8M
          dbgs() << "POP " << *e.second << " in " << e.first->getName() << " = "
545
21.8M
                 << TheCache.getCachedValueInfo(e.second, e.first) << "\n");
546
21.8M
547
21.8M
      BlockValueStack.pop_back();
548
21.8M
      BlockValueSet.erase(e);
549
21.8M
    } else {
550
11.2M
      // More work needs to be done before revisiting.
551
11.2M
      assert(BlockValueStack.back() != e && "Stack should have been pushed!");
552
11.2M
    }
553
33.0M
  }
554
10.4M
}
555
556
52.9M
bool LazyValueInfoImpl::hasBlockValue(Value *Val, BasicBlock *BB) {
557
52.9M
  // If already a constant, there is nothing to compute.
558
52.9M
  if (isa<Constant>(Val))
559
3.17M
    return true;
560
49.7M
561
49.7M
  return TheCache.hasCachedValueInfo(Val, BB);
562
49.7M
}
563
564
ValueLatticeElement LazyValueInfoImpl::getBlockValue(Value *Val,
565
34.4M
                                                     BasicBlock *BB) {
566
34.4M
  // If already a constant, there is nothing to compute.
567
34.4M
  if (Constant *VC = dyn_cast<Constant>(Val))
568
1.90M
    return ValueLatticeElement::get(VC);
569
32.5M
570
32.5M
  return TheCache.getCachedValueInfo(Val, BB);
571
32.5M
}
572
573
8.53M
static ValueLatticeElement getFromRangeMetadata(Instruction *BBI) {
574
8.53M
  switch (BBI->getOpcode()) {
575
8.53M
  
default: break3.37M
;
576
8.53M
  case Instruction::Load:
577
5.15M
  case Instruction::Call:
578
5.15M
  case Instruction::Invoke:
579
5.15M
    if (MDNode *Ranges = BBI->getMetadata(LLVMContext::MD_range))
580
237k
      if (isa<IntegerType>(BBI->getType())) {
581
237k
        return ValueLatticeElement::getRange(
582
237k
            getConstantRangeFromMetadata(*Ranges));
583
237k
      }
584
4.92M
    break;
585
8.29M
  };
586
8.29M
  // Nothing known - will be intersected with other facts
587
8.29M
  return ValueLatticeElement::getOverdefined();
588
8.29M
}
589
590
33.0M
bool LazyValueInfoImpl::solveBlockValue(Value *Val, BasicBlock *BB) {
591
33.0M
  if (isa<Constant>(Val))
592
0
    return true;
593
33.0M
594
33.0M
  if (TheCache.hasCachedValueInfo(Val, BB)) {
595
0
    // If we have a cached value, use that.
596
0
    LLVM_DEBUG(dbgs() << "  reuse BB '" << BB->getName() << "' val="
597
0
                      << TheCache.getCachedValueInfo(Val, BB) << '\n');
598
0
599
0
    // Since we're reusing a cached value, we don't need to update the
600
0
    // OverDefinedCache. The cache will have been properly updated whenever the
601
0
    // cached value was inserted.
602
0
    return true;
603
0
  }
604
33.0M
605
33.0M
  // Hold off inserting this value into the Cache in case we have to return
606
33.0M
  // false and come back later.
607
33.0M
  ValueLatticeElement Res;
608
33.0M
  if (!solveBlockValueImpl(Res, Val, BB))
609
11.2M
    // Work pushed, will revisit
610
11.2M
    return false;
611
21.8M
612
21.8M
  TheCache.insertResult(Val, BB, Res);
613
21.8M
  return true;
614
21.8M
}
615
616
bool LazyValueInfoImpl::solveBlockValueImpl(ValueLatticeElement &Res,
617
33.0M
                                            Value *Val, BasicBlock *BB) {
618
33.0M
619
33.0M
  Instruction *BBI = dyn_cast<Instruction>(Val);
620
33.0M
  if (!BBI || 
BBI->getParent() != BB28.1M
)
621
21.9M
    return solveBlockValueNonLocal(Res, Val, BB);
622
11.1M
623
11.1M
  if (PHINode *PN = dyn_cast<PHINode>(BBI))
624
1.07M
    return solveBlockValuePHINode(Res, PN, BB);
625
10.0M
626
10.0M
  if (auto *SI = dyn_cast<SelectInst>(BBI))
627
266k
    return solveBlockValueSelect(Res, SI, BB);
628
9.79M
629
9.79M
  // If this value is a nonnull pointer, record it's range and bailout.  Note
630
9.79M
  // that for all other pointer typed values, we terminate the search at the
631
9.79M
  // definition.  We could easily extend this to look through geps, bitcasts,
632
9.79M
  // and the like to prove non-nullness, but it's not clear that's worth it
633
9.79M
  // compile time wise.  The context-insensitive value walk done inside
634
9.79M
  // isKnownNonZero gets most of the profitable cases at much less expense.
635
9.79M
  // This does mean that we have a sensitivity to where the defining
636
9.79M
  // instruction is placed, even if it could legally be hoisted much higher.
637
9.79M
  // That is unfortunate.
638
9.79M
  PointerType *PT = dyn_cast<PointerType>(BBI->getType());
639
9.79M
  if (PT && 
isKnownNonZero(BBI, DL)4.84M
) {
640
3.11M
    Res = ValueLatticeElement::getNot(ConstantPointerNull::get(PT));
641
3.11M
    return true;
642
3.11M
  }
643
6.67M
  if (BBI->getType()->isIntegerTy()) {
644
4.87M
    if (auto *CI = dyn_cast<CastInst>(BBI))
645
572k
      return solveBlockValueCast(Res, CI, BB);
646
4.30M
647
4.30M
    if (BinaryOperator *BO = dyn_cast<BinaryOperator>(BBI))
648
1.88M
      return solveBlockValueBinaryOp(Res, BO, BB);
649
2.41M
650
2.41M
    if (auto *EVI = dyn_cast<ExtractValueInst>(BBI))
651
37.4k
      if (auto *WO = dyn_cast<WithOverflowInst>(EVI->getAggregateOperand()))
652
2.71k
        if (EVI->getNumIndices() == 1 && *EVI->idx_begin() == 0)
653
136
          return solveBlockValueOverflowIntrinsic(Res, WO, BB);
654
2.41M
655
2.41M
    if (auto *II = dyn_cast<IntrinsicInst>(BBI))
656
15.5k
      return solveBlockValueIntrinsic(Res, II, BB);
657
4.20M
  }
658
4.20M
659
4.20M
  LLVM_DEBUG(dbgs() << " compute BB '" << BB->getName()
660
4.20M
                    << "' - unknown inst def found.\n");
661
4.20M
  Res = getFromRangeMetadata(BBI);
662
4.20M
  return true;
663
4.20M
}
664
665
20.8M
static bool InstructionDereferencesPointer(Instruction *I, Value *Ptr) {
666
20.8M
  if (LoadInst *L = dyn_cast<LoadInst>(I)) {
667
2.93M
    return L->getPointerAddressSpace() == 0 &&
668
2.93M
           GetUnderlyingObject(L->getPointerOperand(),
669
2.93M
                               L->getModule()->getDataLayout()) == Ptr;
670
2.93M
  }
671
17.9M
  if (StoreInst *S = dyn_cast<StoreInst>(I)) {
672
1.07M
    return S->getPointerAddressSpace() == 0 &&
673
1.07M
           GetUnderlyingObject(S->getPointerOperand(),
674
1.07M
                               S->getModule()->getDataLayout()) == Ptr;
675
1.07M
  }
676
16.8M
  if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(I)) {
677
71.2k
    if (MI->isVolatile()) 
return false2
;
678
71.2k
679
71.2k
    // FIXME: check whether it has a valuerange that excludes zero?
680
71.2k
    ConstantInt *Len = dyn_cast<ConstantInt>(MI->getLength());
681
71.2k
    if (!Len || 
Len->isZero()68.1k
)
return false3.15k
;
682
68.1k
683
68.1k
    if (MI->getDestAddressSpace() == 0)
684
68.1k
      if (GetUnderlyingObject(MI->getRawDest(),
685
68.1k
                              MI->getModule()->getDataLayout()) == Ptr)
686
13.0k
        return true;
687
55.0k
    if (MemTransferInst *MTI = dyn_cast<MemTransferInst>(MI))
688
21.6k
      if (MTI->getSourceAddressSpace() == 0)
689
21.6k
        if (GetUnderlyingObject(MTI->getRawSource(),
690
21.6k
                                MTI->getModule()->getDataLayout()) == Ptr)
691
510
          return true;
692
16.8M
  }
693
16.8M
  return false;
694
16.8M
}
695
696
/// Return true if the allocation associated with Val is ever dereferenced
697
/// within the given basic block.  This establishes the fact Val is not null,
698
/// but does not imply that the memory at Val is dereferenceable.  (Val may
699
/// point off the end of the dereferenceable part of the object.)
700
4.32M
static bool isObjectDereferencedInBlock(Value *Val, BasicBlock *BB) {
701
4.32M
  assert(Val->getType()->isPointerTy());
702
4.32M
703
4.32M
  const DataLayout &DL = BB->getModule()->getDataLayout();
704
4.32M
  Value *UnderlyingVal = GetUnderlyingObject(Val, DL);
705
4.32M
  // If 'GetUnderlyingObject' didn't converge, skip it. It won't converge
706
4.32M
  // inside InstructionDereferencesPointer either.
707
4.32M
  if (UnderlyingVal == GetUnderlyingObject(UnderlyingVal, DL, 1))
708
4.32M
    for (Instruction &I : *BB)
709
20.8M
      if (InstructionDereferencesPointer(&I, UnderlyingVal))
710
688k
        return true;
711
4.32M
  
return false3.63M
;
712
4.32M
}
713
714
bool LazyValueInfoImpl::solveBlockValueNonLocal(ValueLatticeElement &BBLV,
715
21.9M
                                                 Value *Val, BasicBlock *BB) {
716
21.9M
  ValueLatticeElement Result;  // Start Undefined.
717
21.9M
718
21.9M
  // If this is the entry block, we must be asking about an argument.  The
719
21.9M
  // value is overdefined.
720
21.9M
  if (BB == &BB->getParent()->getEntryBlock()) {
721
569k
    assert(isa<Argument>(Val) && "Unknown live-in to the entry block");
722
569k
    // Before giving up, see if we can prove the pointer non-null local to
723
569k
    // this particular block.
724
569k
    PointerType *PTy = dyn_cast<PointerType>(Val->getType());
725
569k
    if (PTy &&
726
569k
        
(424k
isKnownNonZero(Val, DL)424k
||
727
424k
          
(397k
isObjectDereferencedInBlock(Val, BB)397k
&&
728
397k
           
!NullPointerIsDefined(BB->getParent(), PTy->getAddressSpace())82.5k
))) {
729
109k
      Result = ValueLatticeElement::getNot(ConstantPointerNull::get(PTy));
730
460k
    } else {
731
460k
      Result = ValueLatticeElement::getOverdefined();
732
460k
    }
733
569k
    BBLV = Result;
734
569k
    return true;
735
569k
  }
736
21.3M
737
21.3M
  // Loop over all of our predecessors, merging what we know from them into
738
21.3M
  // result.  If we encounter an unexplored predecessor, we eagerly explore it
739
21.3M
  // in a depth first manner.  In practice, this has the effect of discovering
740
21.3M
  // paths we can't analyze eagerly without spending compile times analyzing
741
21.3M
  // other paths.  This heuristic benefits from the fact that predecessors are
742
21.3M
  // frequently arranged such that dominating ones come first and we quickly
743
21.3M
  // find a path to function entry.  TODO: We should consider explicitly
744
21.3M
  // canonicalizing to make this true rather than relying on this happy
745
21.3M
  // accident.
746
29.7M
  
for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); 21.3M
PI != E;
++PI8.40M
) {
747
25.2M
    ValueLatticeElement EdgeResult;
748
25.2M
    if (!getEdgeValue(Val, *PI, BB, EdgeResult))
749
9.92M
      // Explore that input, then return here
750
9.92M
      return false;
751
15.3M
752
15.3M
    Result.mergeIn(EdgeResult, DL);
753
15.3M
754
15.3M
    // If we hit overdefined, exit early.  The BlockVals entry is already set
755
15.3M
    // to overdefined.
756
15.3M
    if (Result.isOverdefined()) {
757
6.90M
      LLVM_DEBUG(dbgs() << " compute BB '" << BB->getName()
758
6.90M
                        << "' - overdefined because of pred (non local).\n");
759
6.90M
      // Before giving up, see if we can prove the pointer non-null local to
760
6.90M
      // this particular block.
761
6.90M
      PointerType *PTy = dyn_cast<PointerType>(Val->getType());
762
6.90M
      if (PTy && 
isObjectDereferencedInBlock(Val, BB)3.92M
&&
763
6.90M
          
!NullPointerIsDefined(BB->getParent(), PTy->getAddressSpace())606k
) {
764
606k
        Result = ValueLatticeElement::getNot(ConstantPointerNull::get(PTy));
765
606k
      }
766
6.90M
767
6.90M
      BBLV = Result;
768
6.90M
      return true;
769
6.90M
    }
770
15.3M
  }
771
21.3M
772
21.3M
  // Return the merged value, which is more precise than 'overdefined'.
773
21.3M
  assert(!Result.isOverdefined());
774
4.56M
  BBLV = Result;
775
4.56M
  return true;
776
21.3M
}
777
778
bool LazyValueInfoImpl::solveBlockValuePHINode(ValueLatticeElement &BBLV,
779
1.07M
                                               PHINode *PN, BasicBlock *BB) {
780
1.07M
  ValueLatticeElement Result;  // Start Undefined.
781
1.07M
782
1.07M
  // Loop over all of our predecessors, merging what we know from them into
783
1.07M
  // result.  See the comment about the chosen traversal order in
784
1.07M
  // solveBlockValueNonLocal; the same reasoning applies here.
785
2.05M
  for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; 
++i982k
) {
786
1.81M
    BasicBlock *PhiBB = PN->getIncomingBlock(i);
787
1.81M
    Value *PhiVal = PN->getIncomingValue(i);
788
1.81M
    ValueLatticeElement EdgeResult;
789
1.81M
    // Note that we can provide PN as the context value to getEdgeValue, even
790
1.81M
    // though the results will be cached, because PN is the value being used as
791
1.81M
    // the cache key in the caller.
792
1.81M
    if (!getEdgeValue(PhiVal, PhiBB, BB, EdgeResult, PN))
793
224k
      // Explore that input, then return here
794
224k
      return false;
795
1.59M
796
1.59M
    Result.mergeIn(EdgeResult, DL);
797
1.59M
798
1.59M
    // If we hit overdefined, exit early.  The BlockVals entry is already set
799
1.59M
    // to overdefined.
800
1.59M
    if (Result.isOverdefined()) {
801
608k
      LLVM_DEBUG(dbgs() << " compute BB '" << BB->getName()
802
608k
                        << "' - overdefined because of pred (local).\n");
803
608k
804
608k
      BBLV = Result;
805
608k
      return true;
806
608k
    }
807
1.59M
  }
808
1.07M
809
1.07M
  // Return the merged value, which is more precise than 'overdefined'.
810
1.07M
  assert(!Result.isOverdefined() && "Possible PHI in entry block?");
811
241k
  BBLV = Result;
812
241k
  return true;
813
1.07M
}
814
815
static ValueLatticeElement getValueFromCondition(Value *Val, Value *Cond,
816
                                                 bool isTrueDest = true);
817
818
// If we can determine a constraint on the value given conditions assumed by
819
// the program, intersect those constraints with BBLV
820
void LazyValueInfoImpl::intersectAssumeOrGuardBlockValueConstantRange(
821
61.5M
        Value *Val, ValueLatticeElement &BBLV, Instruction *BBI) {
822
61.5M
  BBI = BBI ? 
BBI47.0M
:
dyn_cast<Instruction>(Val)14.5M
;
823
61.5M
  if (!BBI)
824
2.44M
    return;
825
59.0M
826
59.0M
  for (auto &AssumeVH : AC->assumptionsFor(Val)) {
827
85
    if (!AssumeVH)
828
0
      continue;
829
85
    auto *I = cast<CallInst>(AssumeVH);
830
85
    if (!isValidAssumeForContext(I, BBI, DT))
831
48
      continue;
832
37
833
37
    BBLV = intersect(BBLV, getValueFromCondition(Val, I->getArgOperand(0)));
834
37
  }
835
59.0M
836
59.0M
  // If guards are not used in the module, don't spend time looking for them
837
59.0M
  auto *GuardDecl = BBI->getModule()->getFunction(
838
59.0M
          Intrinsic::getName(Intrinsic::experimental_guard));
839
59.0M
  if (!GuardDecl || 
GuardDecl->use_empty()544
)
840
59.0M
    return;
841
545
842
545
  if (BBI->getIterator() == BBI->getParent()->begin())
843
197
    return;
844
348
  for (Instruction &I : make_range(std::next(BBI->getIterator().getReverse()),
845
910
                                   BBI->getParent()->rend())) {
846
910
    Value *Cond = nullptr;
847
910
    if (match(&I, m_Intrinsic<Intrinsic::experimental_guard>(m_Value(Cond))))
848
71
      BBLV = intersect(BBLV, getValueFromCondition(Val, Cond));
849
910
  }
850
348
}
851
852
bool LazyValueInfoImpl::solveBlockValueSelect(ValueLatticeElement &BBLV,
853
266k
                                              SelectInst *SI, BasicBlock *BB) {
854
266k
855
266k
  // Recurse on our inputs if needed
856
266k
  if (!hasBlockValue(SI->getTrueValue(), BB)) {
857
88.7k
    if (pushBlockValue(std::make_pair(BB, SI->getTrueValue())))
858
88.5k
      return false;
859
236
    BBLV = ValueLatticeElement::getOverdefined();
860
236
    return true;
861
236
  }
862
177k
  ValueLatticeElement TrueVal = getBlockValue(SI->getTrueValue(), BB);
863
177k
  // If we hit overdefined, don't ask more queries.  We want to avoid poisoning
864
177k
  // extra slots in the table if we can.
865
177k
  if (TrueVal.isOverdefined()) {
866
37.8k
    BBLV = ValueLatticeElement::getOverdefined();
867
37.8k
    return true;
868
37.8k
  }
869
139k
870
139k
  if (!hasBlockValue(SI->getFalseValue(), BB)) {
871
40.7k
    if (pushBlockValue(std::make_pair(BB, SI->getFalseValue())))
872
40.5k
      return false;
873
139
    BBLV = ValueLatticeElement::getOverdefined();
874
139
    return true;
875
139
  }
876
98.8k
  ValueLatticeElement FalseVal = getBlockValue(SI->getFalseValue(), BB);
877
98.8k
  // If we hit overdefined, don't ask more queries.  We want to avoid poisoning
878
98.8k
  // extra slots in the table if we can.
879
98.8k
  if (FalseVal.isOverdefined()) {
880
23.3k
    BBLV = ValueLatticeElement::getOverdefined();
881
23.3k
    return true;
882
23.3k
  }
883
75.4k
884
75.4k
  if (TrueVal.isConstantRange() && 
FalseVal.isConstantRange()68.7k
) {
885
68.6k
    const ConstantRange &TrueCR = TrueVal.getConstantRange();
886
68.6k
    const ConstantRange &FalseCR = FalseVal.getConstantRange();
887
68.6k
    Value *LHS = nullptr;
888
68.6k
    Value *RHS = nullptr;
889
68.6k
    SelectPatternResult SPR = matchSelectPattern(SI, LHS, RHS);
890
68.6k
    // Is this a min specifically of our two inputs?  (Avoid the risk of
891
68.6k
    // ValueTracking getting smarter looking back past our immediate inputs.)
892
68.6k
    if (SelectPatternResult::isMinOrMax(SPR.Flavor) &&
893
68.6k
        
LHS == SI->getTrueValue()22.6k
&&
RHS == SI->getFalseValue()18.4k
) {
894
18.4k
      ConstantRange ResultCR = [&]() {
895
18.4k
        switch (SPR.Flavor) {
896
18.4k
        default:
897
0
          llvm_unreachable("unexpected minmax type!");
898
18.4k
        case SPF_SMIN:                   /// Signed minimum
899
662
          return TrueCR.smin(FalseCR);
900
18.4k
        case SPF_UMIN:                   /// Unsigned minimum
901
1.26k
          return TrueCR.umin(FalseCR);
902
18.4k
        case SPF_SMAX:                   /// Signed maximum
903
3.93k
          return TrueCR.smax(FalseCR);
904
18.4k
        case SPF_UMAX:                   /// Unsigned maximum
905
12.6k
          return TrueCR.umax(FalseCR);
906
0
        };
907
0
      }();
908
18.4k
      BBLV = ValueLatticeElement::getRange(ResultCR);
909
18.4k
      return true;
910
18.4k
    }
911
50.2k
912
50.2k
    if (SPR.Flavor == SPF_ABS) {
913
1.25k
      if (LHS == SI->getTrueValue()) {
914
5
        BBLV = ValueLatticeElement::getRange(TrueCR.abs());
915
5
        return true;
916
5
      }
917
1.24k
      if (LHS == SI->getFalseValue()) {
918
1.24k
        BBLV = ValueLatticeElement::getRange(FalseCR.abs());
919
1.24k
        return true;
920
1.24k
      }
921
48.9k
    }
922
48.9k
923
48.9k
    if (SPR.Flavor == SPF_NABS) {
924
2
      ConstantRange Zero(APInt::getNullValue(TrueCR.getBitWidth()));
925
2
      if (LHS == SI->getTrueValue()) {
926
1
        BBLV = ValueLatticeElement::getRange(Zero.sub(TrueCR.abs()));
927
1
        return true;
928
1
      }
929
1
      if (LHS == SI->getFalseValue()) {
930
1
        BBLV = ValueLatticeElement::getRange(Zero.sub(FalseCR.abs()));
931
1
        return true;
932
1
      }
933
55.7k
    }
934
48.9k
  }
935
55.7k
936
55.7k
  // Can we constrain the facts about the true and false values by using the
937
55.7k
  // condition itself?  This shows up with idioms like e.g. select(a > 5, a, 5).
938
55.7k
  // TODO: We could potentially refine an overdefined true value above.
939
55.7k
  Value *Cond = SI->getCondition();
940
55.7k
  TrueVal = intersect(TrueVal,
941
55.7k
                      getValueFromCondition(SI->getTrueValue(), Cond, true));
942
55.7k
  FalseVal = intersect(FalseVal,
943
55.7k
                       getValueFromCondition(SI->getFalseValue(), Cond, false));
944
55.7k
945
55.7k
  // Handle clamp idioms such as:
946
55.7k
  //   %24 = constantrange<0, 17>
947
55.7k
  //   %39 = icmp eq i32 %24, 0
948
55.7k
  //   %40 = add i32 %24, -1
949
55.7k
  //   %siv.next = select i1 %39, i32 16, i32 %40
950
55.7k
  //   %siv.next = constantrange<0, 17> not <-1, 17>
951
55.7k
  // In general, this can handle any clamp idiom which tests the edge
952
55.7k
  // condition via an equality or inequality.
953
55.7k
  if (auto *ICI = dyn_cast<ICmpInst>(Cond)) {
954
53.3k
    ICmpInst::Predicate Pred = ICI->getPredicate();
955
53.3k
    Value *A = ICI->getOperand(0);
956
53.3k
    if (ConstantInt *CIBase = dyn_cast<ConstantInt>(ICI->getOperand(1))) {
957
40.2k
      auto addConstants = [](ConstantInt *A, ConstantInt *B) {
958
205
        assert(A->getType() == B->getType());
959
205
        return ConstantInt::get(A->getType(), A->getValue() + B->getValue());
960
205
      };
961
40.2k
      // See if either input is A + C2, subject to the constraint from the
962
40.2k
      // condition that A != C when that input is used.  We can assume that
963
40.2k
      // that input doesn't include C + C2.
964
40.2k
      ConstantInt *CIAdded;
965
40.2k
      switch (Pred) {
966
40.2k
      
default: break12.5k
;
967
40.2k
      case ICmpInst::ICMP_EQ:
968
27.3k
        if (match(SI->getFalseValue(), m_Add(m_Specific(A),
969
27.3k
                                             m_ConstantInt(CIAdded)))) {
970
133
          auto ResNot = addConstants(CIBase, CIAdded);
971
133
          FalseVal = intersect(FalseVal,
972
133
                               ValueLatticeElement::getNot(ResNot));
973
133
        }
974
27.3k
        break;
975
40.2k
      case ICmpInst::ICMP_NE:
976
308
        if (match(SI->getTrueValue(), m_Add(m_Specific(A),
977
308
                                            m_ConstantInt(CIAdded)))) {
978
72
          auto ResNot = addConstants(CIBase, CIAdded);
979
72
          TrueVal = intersect(TrueVal,
980
72
                              ValueLatticeElement::getNot(ResNot));
981
72
        }
982
308
        break;
983
40.2k
      };
984
40.2k
    }
985
53.3k
  }
986
55.7k
987
55.7k
  ValueLatticeElement Result;  // Start Undefined.
988
55.7k
  Result.mergeIn(TrueVal, DL);
989
55.7k
  Result.mergeIn(FalseVal, DL);
990
55.7k
  BBLV = Result;
991
55.7k
  return true;
992
55.7k
}
993
994
Optional<ConstantRange> LazyValueInfoImpl::getRangeForOperand(unsigned Op,
995
                                                              Instruction *I,
996
4.18M
                                                              BasicBlock *BB) {
997
4.18M
  if (!hasBlockValue(I->getOperand(Op), BB))
998
1.22M
    if (pushBlockValue(std::make_pair(BB, I->getOperand(Op))))
999
1.21M
      return None;
1000
2.96M
1001
2.96M
  const unsigned OperandBitWidth =
1002
2.96M
    DL.getTypeSizeInBits(I->getOperand(Op)->getType());
1003
2.96M
  ConstantRange Range = ConstantRange::getFull(OperandBitWidth);
1004
2.96M
  if (hasBlockValue(I->getOperand(Op), BB)) {
1005
2.96M
    ValueLatticeElement Val = getBlockValue(I->getOperand(Op), BB);
1006
2.96M
    intersectAssumeOrGuardBlockValueConstantRange(I->getOperand(Op), Val, I);
1007
2.96M
    if (Val.isConstantRange())
1008
2.13M
      Range = Val.getConstantRange();
1009
2.96M
  }
1010
2.96M
  return Range;
1011
2.96M
}
1012
1013
bool LazyValueInfoImpl::solveBlockValueCast(ValueLatticeElement &BBLV,
1014
                                            CastInst *CI,
1015
572k
                                            BasicBlock *BB) {
1016
572k
  if (!CI->getOperand(0)->getType()->isSized()) {
1017
0
    // Without knowing how wide the input is, we can't analyze it in any useful
1018
0
    // way.
1019
0
    BBLV = ValueLatticeElement::getOverdefined();
1020
0
    return true;
1021
0
  }
1022
572k
1023
572k
  // Filter out casts we don't know how to reason about before attempting to
1024
572k
  // recurse on our operand.  This can cut a long search short if we know we're
1025
572k
  // not going to be able to get any useful information anways.
1026
572k
  switch (CI->getOpcode()) {
1027
572k
  case Instruction::Trunc:
1028
458k
  case Instruction::SExt:
1029
458k
  case Instruction::ZExt:
1030
458k
  case Instruction::BitCast:
1031
458k
    break;
1032
458k
  default:
1033
114k
    // Unhandled instructions are overdefined.
1034
114k
    LLVM_DEBUG(dbgs() << " compute BB '" << BB->getName()
1035
114k
                      << "' - overdefined (unknown cast).\n");
1036
114k
    BBLV = ValueLatticeElement::getOverdefined();
1037
114k
    return true;
1038
458k
  }
1039
458k
1040
458k
  // Figure out the range of the LHS.  If that fails, we still apply the
1041
458k
  // transfer rule on the full set since we may be able to locally infer
1042
458k
  // interesting facts.
1043
458k
  Optional<ConstantRange> LHSRes = getRangeForOperand(0, CI, BB);
1044
458k
  if (!LHSRes.hasValue())
1045
217k
    // More work to do before applying this transfer rule.
1046
217k
    return false;
1047
240k
  ConstantRange LHSRange = LHSRes.getValue();
1048
240k
1049
240k
  const unsigned ResultBitWidth = CI->getType()->getIntegerBitWidth();
1050
240k
1051
240k
  // NOTE: We're currently limited by the set of operations that ConstantRange
1052
240k
  // can evaluate symbolically.  Enhancing that set will allows us to analyze
1053
240k
  // more definitions.
1054
240k
  BBLV = ValueLatticeElement::getRange(LHSRange.castOp(CI->getOpcode(),
1055
240k
                                                       ResultBitWidth));
1056
240k
  return true;
1057
240k
}
1058
1059
bool LazyValueInfoImpl::solveBlockValueBinaryOpImpl(
1060
    ValueLatticeElement &BBLV, Instruction *I, BasicBlock *BB,
1061
    std::function<ConstantRange(const ConstantRange &,
1062
1.86M
                                const ConstantRange &)> OpFn) {
1063
1.86M
  // Figure out the ranges of the operands.  If that fails, use a
1064
1.86M
  // conservative range, but apply the transfer rule anyways.  This
1065
1.86M
  // lets us pick up facts from expressions like "and i32 (call i32
1066
1.86M
  // @foo()), 32"
1067
1.86M
  Optional<ConstantRange> LHSRes = getRangeForOperand(0, I, BB);
1068
1.86M
  Optional<ConstantRange> RHSRes = getRangeForOperand(1, I, BB);
1069
1.86M
  if (!LHSRes.hasValue() || 
!RHSRes.hasValue()1.10M
)
1070
793k
    // More work to do before applying this transfer rule.
1071
793k
    return false;
1072
1.06M
1073
1.06M
  ConstantRange LHSRange = LHSRes.getValue();
1074
1.06M
  ConstantRange RHSRange = RHSRes.getValue();
1075
1.06M
  BBLV = ValueLatticeElement::getRange(OpFn(LHSRange, RHSRange));
1076
1.06M
  return true;
1077
1.06M
}
1078
1079
bool LazyValueInfoImpl::solveBlockValueBinaryOp(ValueLatticeElement &BBLV,
1080
                                                BinaryOperator *BO,
1081
1.88M
                                                BasicBlock *BB) {
1082
1.88M
1083
1.88M
  assert(BO->getOperand(0)->getType()->isSized() &&
1084
1.88M
         "all operands to binary operators are sized");
1085
1.88M
  if (BO->getOpcode() == Instruction::Xor) {
1086
22.7k
    // Xor is the only operation not supported by ConstantRange::binaryOp().
1087
22.7k
    LLVM_DEBUG(dbgs() << " compute BB '" << BB->getName()
1088
22.7k
                      << "' - overdefined (unknown binary operator).\n");
1089
22.7k
    BBLV = ValueLatticeElement::getOverdefined();
1090
22.7k
    return true;
1091
22.7k
  }
1092
1.86M
1093
1.86M
  return solveBlockValueBinaryOpImpl(BBLV, BO, BB,
1094
1.86M
      [BO](const ConstantRange &CR1, const ConstantRange &CR2) {
1095
1.06M
        return CR1.binaryOp(BO->getOpcode(), CR2);
1096
1.06M
      });
1097
1.86M
}
1098
1099
bool LazyValueInfoImpl::solveBlockValueOverflowIntrinsic(
1100
136
    ValueLatticeElement &BBLV, WithOverflowInst *WO, BasicBlock *BB) {
1101
136
  return solveBlockValueBinaryOpImpl(BBLV, WO, BB,
1102
136
      [WO](const ConstantRange &CR1, const ConstantRange &CR2) {
1103
101
        return CR1.binaryOp(WO->getBinaryOp(), CR2);
1104
101
      });
1105
136
}
1106
1107
bool LazyValueInfoImpl::solveBlockValueIntrinsic(
1108
15.5k
    ValueLatticeElement &BBLV, IntrinsicInst *II, BasicBlock *BB) {
1109
15.5k
  switch (II->getIntrinsicID()) {
1110
15.5k
  case Intrinsic::uadd_sat:
1111
161
    return solveBlockValueBinaryOpImpl(BBLV, II, BB,
1112
161
        [](const ConstantRange &CR1, const ConstantRange &CR2) {
1113
109
          return CR1.uadd_sat(CR2);
1114
109
        });
1115
15.5k
  case Intrinsic::usub_sat:
1116
8
    return solveBlockValueBinaryOpImpl(BBLV, II, BB,
1117
8
        [](const ConstantRange &CR1, const ConstantRange &CR2) {
1118
5
          return CR1.usub_sat(CR2);
1119
5
        });
1120
15.5k
  case Intrinsic::sadd_sat:
1121
1
    return solveBlockValueBinaryOpImpl(BBLV, II, BB,
1122
1
        [](const ConstantRange &CR1, const ConstantRange &CR2) {
1123
1
          return CR1.sadd_sat(CR2);
1124
1
        });
1125
15.5k
  case Intrinsic::ssub_sat:
1126
1
    return solveBlockValueBinaryOpImpl(BBLV, II, BB,
1127
1
        [](const ConstantRange &CR1, const ConstantRange &CR2) {
1128
1
          return CR1.ssub_sat(CR2);
1129
1
        });
1130
15.5k
  default:
1131
15.3k
    LLVM_DEBUG(dbgs() << " compute BB '" << BB->getName()
1132
15.3k
                      << "' - overdefined (unknown intrinsic).\n");
1133
15.3k
    BBLV = ValueLatticeElement::getOverdefined();
1134
15.3k
    return true;
1135
15.5k
  }
1136
15.5k
}
1137
1138
static ValueLatticeElement getValueFromICmpCondition(Value *Val, ICmpInst *ICI,
1139
26.8M
                                                     bool isTrueDest) {
1140
26.8M
  Value *LHS = ICI->getOperand(0);
1141
26.8M
  Value *RHS = ICI->getOperand(1);
1142
26.8M
  CmpInst::Predicate Predicate = ICI->getPredicate();
1143
26.8M
1144
26.8M
  if (isa<Constant>(RHS)) {
1145
20.2M
    if (ICI->isEquality() && 
LHS == Val15.4M
) {
1146
815k
      // We know that V has the RHS constant if this is a true SETEQ or
1147
815k
      // false SETNE.
1148
815k
      if (isTrueDest == (Predicate == ICmpInst::ICMP_EQ))
1149
53.2k
        return ValueLatticeElement::get(cast<Constant>(RHS));
1150
762k
      else
1151
762k
        return ValueLatticeElement::getNot(cast<Constant>(RHS));
1152
26.0M
    }
1153
20.2M
  }
1154
26.0M
1155
26.0M
  if (!Val->getType()->isIntegerTy())
1156
13.5M
    return ValueLatticeElement::getOverdefined();
1157
12.4M
1158
12.4M
  // Use ConstantRange::makeAllowedICmpRegion in order to determine the possible
1159
12.4M
  // range of Val guaranteed by the condition. Recognize comparisons in the from
1160
12.4M
  // of:
1161
12.4M
  //  icmp <pred> Val, ...
1162
12.4M
  //  icmp <pred> (add Val, Offset), ...
1163
12.4M
  // The latter is the range checking idiom that InstCombine produces. Subtract
1164
12.4M
  // the offset from the allowed range for RHS in this case.
1165
12.4M
1166
12.4M
  // Val or (add Val, Offset) can be on either hand of the comparison
1167
12.4M
  if (LHS != Val && 
!match(LHS, m_Add(m_Specific(Val), m_ConstantInt()))11.3M
) {
1168
11.3M
    std::swap(LHS, RHS);
1169
11.3M
    Predicate = CmpInst::getSwappedPredicate(Predicate);
1170
11.3M
  }
1171
12.4M
1172
12.4M
  ConstantInt *Offset = nullptr;
1173
12.4M
  if (LHS != Val)
1174
11.0M
    match(LHS, m_Add(m_Specific(Val), m_ConstantInt(Offset)));
1175
12.4M
1176
12.4M
  if (LHS == Val || 
Offset11.0M
) {
1177
1.48M
    // Calculate the range of values that are allowed by the comparison
1178
1.48M
    ConstantRange RHSRange(RHS->getType()->getIntegerBitWidth(),
1179
1.48M
                           /*isFullSet=*/true);
1180
1.48M
    if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS))
1181
554k
      RHSRange = ConstantRange(CI->getValue());
1182
928k
    else if (Instruction *I = dyn_cast<Instruction>(RHS))
1183
875k
      if (auto *Ranges = I->getMetadata(LLVMContext::MD_range))
1184
291
        RHSRange = getConstantRangeFromMetadata(*Ranges);
1185
1.48M
1186
1.48M
    // If we're interested in the false dest, invert the condition
1187
1.48M
    CmpInst::Predicate Pred =
1188
1.48M
            isTrueDest ? 
Predicate815k
:
CmpInst::getInversePredicate(Predicate)667k
;
1189
1.48M
    ConstantRange TrueValues =
1190
1.48M
            ConstantRange::makeAllowedICmpRegion(Pred, RHSRange);
1191
1.48M
1192
1.48M
    if (Offset) // Apply the offset from above.
1193
50.8k
      TrueValues = TrueValues.subtract(Offset->getValue());
1194
1.48M
1195
1.48M
    return ValueLatticeElement::getRange(std::move(TrueValues));
1196
1.48M
  }
1197
10.9M
1198
10.9M
  return ValueLatticeElement::getOverdefined();
1199
10.9M
}
1200
1201
// Handle conditions of the form
1202
// extractvalue(op.with.overflow(%x, C), 1).
1203
static ValueLatticeElement getValueFromOverflowCondition(
1204
177
    Value *Val, WithOverflowInst *WO, bool IsTrueDest) {
1205
177
  // TODO: This only works with a constant RHS for now. We could also compute
1206
177
  // the range of the RHS, but this doesn't fit into the current structure of
1207
177
  // the edge value calculation.
1208
177
  const APInt *C;
1209
177
  if (WO->getLHS() != Val || 
!match(WO->getRHS(), m_APInt(C))47
)
1210
130
    return ValueLatticeElement::getOverdefined();
1211
47
1212
47
  // Calculate the possible values of %x for which no overflow occurs.
1213
47
  ConstantRange NWR = ConstantRange::makeExactNoWrapRegion(
1214
47
      WO->getBinaryOp(), *C, WO->getNoWrapKind());
1215
47
1216
47
  // If overflow is false, %x is constrained to NWR. If overflow is true, %x is
1217
47
  // constrained to it's inverse (all values that might cause overflow).
1218
47
  if (IsTrueDest)
1219
14
    NWR = NWR.inverse();
1220
47
  return ValueLatticeElement::getRange(NWR);
1221
47
}
1222
1223
static ValueLatticeElement
1224
getValueFromCondition(Value *Val, Value *Cond, bool isTrueDest,
1225
                      DenseMap<Value*, ValueLatticeElement> &Visited);
1226
1227
static ValueLatticeElement
1228
getValueFromConditionImpl(Value *Val, Value *Cond, bool isTrueDest,
1229
31.0M
                          DenseMap<Value*, ValueLatticeElement> &Visited) {
1230
31.0M
  if (ICmpInst *ICI = dyn_cast<ICmpInst>(Cond))
1231
26.8M
    return getValueFromICmpCondition(Val, ICI, isTrueDest);
1232
4.20M
1233
4.20M
  if (auto *EVI = dyn_cast<ExtractValueInst>(Cond))
1234
7.66k
    if (auto *WO = dyn_cast<WithOverflowInst>(EVI->getAggregateOperand()))
1235
177
      if (EVI->getNumIndices() == 1 && *EVI->idx_begin() == 1)
1236
177
        return getValueFromOverflowCondition(Val, WO, isTrueDest);
1237
4.20M
1238
4.20M
  // Handle conditions in the form of (cond1 && cond2), we know that on the
1239
4.20M
  // true dest path both of the conditions hold. Similarly for conditions of
1240
4.20M
  // the form (cond1 || cond2), we know that on the false dest path neither
1241
4.20M
  // condition holds.
1242
4.20M
  BinaryOperator *BO = dyn_cast<BinaryOperator>(Cond);
1243
4.20M
  if (!BO || 
(3.10M
isTrueDest3.10M
&&
BO->getOpcode() != BinaryOperator::And1.58M
) ||
1244
4.20M
             
(2.78M
!isTrueDest2.78M
&&
BO->getOpcode() != BinaryOperator::Or1.52M
))
1245
2.57M
    return ValueLatticeElement::getOverdefined();
1246
1.62M
1247
1.62M
  // Prevent infinite recursion if Cond references itself as in this example:
1248
1.62M
  //  Cond: "%tmp4 = and i1 %tmp4, undef"
1249
1.62M
  //    BL: "%tmp4 = and i1 %tmp4, undef"
1250
1.62M
  //    BR: "i1 undef"
1251
1.62M
  Value *BL = BO->getOperand(0);
1252
1.62M
  Value *BR = BO->getOperand(1);
1253
1.62M
  if (BL == Cond || 
BR == Cond1.62M
)
1254
2
    return ValueLatticeElement::getOverdefined();
1255
1.62M
1256
1.62M
  return intersect(getValueFromCondition(Val, BL, isTrueDest, Visited),
1257
1.62M
                   getValueFromCondition(Val, BR, isTrueDest, Visited));
1258
1.62M
}
1259
1260
static ValueLatticeElement
1261
getValueFromCondition(Value *Val, Value *Cond, bool isTrueDest,
1262
31.0M
                      DenseMap<Value*, ValueLatticeElement> &Visited) {
1263
31.0M
  auto I = Visited.find(Cond);
1264
31.0M
  if (I != Visited.end())
1265
281
    return I->second;
1266
31.0M
1267
31.0M
  auto Result = getValueFromConditionImpl(Val, Cond, isTrueDest, Visited);
1268
31.0M
  Visited[Cond] = Result;
1269
31.0M
  return Result;
1270
31.0M
}
1271
1272
ValueLatticeElement getValueFromCondition(Value *Val, Value *Cond,
1273
27.8M
                                          bool isTrueDest) {
1274
27.8M
  assert(Cond && "precondition");
1275
27.8M
  DenseMap<Value*, ValueLatticeElement> Visited;
1276
27.8M
  return getValueFromCondition(Val, Cond, isTrueDest, Visited);
1277
27.8M
}
1278
1279
// Return true if Usr has Op as an operand, otherwise false.
1280
2.34M
static bool usesOperand(User *Usr, Value *Op) {
1281
2.34M
  return find(Usr->operands(), Op) != Usr->op_end();
1282
2.34M
}
1283
1284
// Return true if the instruction type of Val is supported by
1285
// constantFoldUser(). Currently CastInst and BinaryOperator only.  Call this
1286
// before calling constantFoldUser() to find out if it's even worth attempting
1287
// to call it.
1288
7.60M
static bool isOperationFoldable(User *Usr) {
1289
7.60M
  return isa<CastInst>(Usr) || 
isa<BinaryOperator>(Usr)6.64M
;
1290
7.60M
}
1291
1292
// Check if Usr can be simplified to an integer constant when the value of one
1293
// of its operands Op is an integer constant OpConstVal. If so, return it as an
1294
// lattice value range with a single element or otherwise return an overdefined
1295
// lattice value.
1296
static ValueLatticeElement constantFoldUser(User *Usr, Value *Op,
1297
                                            const APInt &OpConstVal,
1298
12.1k
                                            const DataLayout &DL) {
1299
12.1k
  assert(isOperationFoldable(Usr) && "Precondition");
1300
12.1k
  Constant* OpConst = Constant::getIntegerValue(Op->getType(), OpConstVal);
1301
12.1k
  // Check if Usr can be simplified to a constant.
1302
12.1k
  if (auto *CI = dyn_cast<CastInst>(Usr)) {
1303
10.0k
    assert(CI->getOperand(0) == Op && "Operand 0 isn't Op");
1304
10.0k
    if (auto *C = dyn_cast_or_null<ConstantInt>(
1305
10.0k
            SimplifyCastInst(CI->getOpcode(), OpConst,
1306
10.0k
                             CI->getDestTy(), DL))) {
1307
10.0k
      return ValueLatticeElement::getRange(ConstantRange(C->getValue()));
1308
10.0k
    }
1309
2.11k
  } else if (auto *BO = dyn_cast<BinaryOperator>(Usr)) {
1310
2.11k
    bool Op0Match = BO->getOperand(0) == Op;
1311
2.11k
    bool Op1Match = BO->getOperand(1) == Op;
1312
2.11k
    assert((Op0Match || Op1Match) &&
1313
2.11k
           "Operand 0 nor Operand 1 isn't a match");
1314
2.11k
    Value *LHS = Op0Match ? 
OpConst1.53k
:
BO->getOperand(0)584
;
1315
2.11k
    Value *RHS = Op1Match ? 
OpConst585
:
BO->getOperand(1)1.53k
;
1316
2.11k
    if (auto *C = dyn_cast_or_null<ConstantInt>(
1317
1.16k
            SimplifyBinOp(BO->getOpcode(), LHS, RHS, DL))) {
1318
1.16k
      return ValueLatticeElement::getRange(ConstantRange(C->getValue()));
1319
1.16k
    }
1320
949
  }
1321
949
  return ValueLatticeElement::getOverdefined();
1322
949
}
1323
1324
/// Compute the value of Val on the edge BBFrom -> BBTo. Returns false if
1325
/// Val is not constrained on the edge.  Result is unspecified if return value
1326
/// is false.
1327
static bool getEdgeValueLocal(Value *Val, BasicBlock *BBFrom,
1328
35.6M
                              BasicBlock *BBTo, ValueLatticeElement &Result) {
1329
35.6M
  // TODO: Handle more complex conditionals. If (v == 0 || v2 < 1) is false, we
1330
35.6M
  // know that v != 0.
1331
35.6M
  if (BranchInst *BI = dyn_cast<BranchInst>(BBFrom->getTerminator())) {
1332
34.3M
    // If this is a conditional branch and only one successor goes to BBTo, then
1333
34.3M
    // we may be able to infer something from the condition.
1334
34.3M
    if (BI->isConditional() &&
1335
34.3M
        
BI->getSuccessor(0) != BI->getSuccessor(1)24.0M
) {
1336
24.0M
      bool isTrueDest = BI->getSuccessor(0) == BBTo;
1337
24.0M
      assert(BI->getSuccessor(!isTrueDest) == BBTo &&
1338
24.0M
             "BBTo isn't a successor of BBFrom");
1339
24.0M
      Value *Condition = BI->getCondition();
1340
24.0M
1341
24.0M
      // If V is the condition of the branch itself, then we know exactly what
1342
24.0M
      // it is.
1343
24.0M
      if (Condition == Val) {
1344
72.1k
        Result = ValueLatticeElement::get(ConstantInt::get(
1345
72.1k
                              Type::getInt1Ty(Val->getContext()), isTrueDest));
1346
72.1k
        return true;
1347
72.1k
      }
1348
24.0M
1349
24.0M
      // If the condition of the branch is an equality comparison, we may be
1350
24.0M
      // able to infer the value.
1351
24.0M
      Result = getValueFromCondition(Val, Condition, isTrueDest);
1352
24.0M
      if (!Result.isOverdefined())
1353
2.09M
        return true;
1354
21.9M
1355
21.9M
      if (User *Usr = dyn_cast<User>(Val)) {
1356
16.6M
        assert(Result.isOverdefined() && "Result isn't overdefined");
1357
16.6M
        // Check with isOperationFoldable() first to avoid linearly iterating
1358
16.6M
        // over the operands unnecessarily which can be expensive for
1359
16.6M
        // instructions with many operands.
1360
16.6M
        if (isa<IntegerType>(Usr->getType()) && 
isOperationFoldable(Usr)7.38M
) {
1361
2.33M
          const DataLayout &DL = BBTo->getModule()->getDataLayout();
1362
2.33M
          if (usesOperand(Usr, Condition)) {
1363
4.62k
            // If Val has Condition as an operand and Val can be folded into a
1364
4.62k
            // constant with either Condition == true or Condition == false,
1365
4.62k
            // propagate the constant.
1366
4.62k
            // eg.
1367
4.62k
            //   ; %Val is true on the edge to %then.
1368
4.62k
            //   %Val = and i1 %Condition, true.
1369
4.62k
            //   br %Condition, label %then, label %else
1370
4.62k
            APInt ConditionVal(1, isTrueDest ? 
13.01k
:
01.61k
);
1371
4.62k
            Result = constantFoldUser(Usr, Condition, ConditionVal, DL);
1372
2.32M
          } else {
1373
2.32M
            // If one of Val's operand has an inferred value, we may be able to
1374
2.32M
            // infer the value of Val.
1375
2.32M
            // eg.
1376
2.32M
            //    ; %Val is 94 on the edge to %then.
1377
2.32M
            //    %Val = add i8 %Op, 1
1378
2.32M
            //    %Condition = icmp eq i8 %Op, 93
1379
2.32M
            //    br i1 %Condition, label %then, label %else
1380
6.02M
            for (unsigned i = 0; i < Usr->getNumOperands(); 
++i3.69M
) {
1381
3.69M
              Value *Op = Usr->getOperand(i);
1382
3.69M
              ValueLatticeElement OpLatticeVal =
1383
3.69M
                  getValueFromCondition(Op, Condition, isTrueDest);
1384
3.69M
              if (Optional<APInt> OpConst = OpLatticeVal.asConstantInteger()) {
1385
1.47k
                Result = constantFoldUser(Usr, Op, OpConst.getValue(), DL);
1386
1.47k
                break;
1387
1.47k
              }
1388
3.69M
            }
1389
2.32M
          }
1390
2.33M
        }
1391
16.6M
      }
1392
21.9M
      if (!Result.isOverdefined())
1393
5.16k
        return true;
1394
33.4M
    }
1395
34.3M
  }
1396
33.4M
1397
33.4M
  // If the edge was formed by a switch on the value, then we may know exactly
1398
33.4M
  // what it is.
1399
33.4M
  if (SwitchInst *SI = dyn_cast<SwitchInst>(BBFrom->getTerminator())) {
1400
652k
    Value *Condition = SI->getCondition();
1401
652k
    if (!isa<IntegerType>(Val->getType()))
1402
385k
      return false;
1403
267k
    bool ValUsesConditionAndMayBeFoldable = false;
1404
267k
    if (Condition != Val) {
1405
227k
      // Check if Val has Condition as an operand.
1406
227k
      if (User *Usr = dyn_cast<User>(Val))
1407
217k
        ValUsesConditionAndMayBeFoldable = isOperationFoldable(Usr) &&
1408
217k
            
usesOperand(Usr, Condition)16.1k
;
1409
227k
      if (!ValUsesConditionAndMayBeFoldable)
1410
226k
        return false;
1411
40.2k
    }
1412
40.2k
    assert((Condition == Val || ValUsesConditionAndMayBeFoldable) &&
1413
40.2k
           "Condition != Val nor Val doesn't use Condition");
1414
40.2k
1415
40.2k
    bool DefaultCase = SI->getDefaultDest() == BBTo;
1416
40.2k
    unsigned BitWidth = Val->getType()->getIntegerBitWidth();
1417
40.2k
    ConstantRange EdgesVals(BitWidth, DefaultCase/*isFullSet*/);
1418
40.2k
1419
188k
    for (auto Case : SI->cases()) {
1420
188k
      APInt CaseValue = Case.getCaseValue()->getValue();
1421
188k
      ConstantRange EdgeVal(CaseValue);
1422
188k
      if (ValUsesConditionAndMayBeFoldable) {
1423
6.07k
        User *Usr = cast<User>(Val);
1424
6.07k
        const DataLayout &DL = BBTo->getModule()->getDataLayout();
1425
6.07k
        ValueLatticeElement EdgeLatticeVal =
1426
6.07k
            constantFoldUser(Usr, Condition, CaseValue, DL);
1427
6.07k
        if (EdgeLatticeVal.isOverdefined())
1428
21
          return false;
1429
6.05k
        EdgeVal = EdgeLatticeVal.getConstantRange();
1430
6.05k
      }
1431
188k
      
if (188k
DefaultCase188k
) {
1432
69.8k
        // It is possible that the default destination is the destination of
1433
69.8k
        // some cases. We cannot perform difference for those cases.
1434
69.8k
        // We know Condition != CaseValue in BBTo.  In some cases we can use
1435
69.8k
        // this to infer Val == f(Condition) is != f(CaseValue).  For now, we
1436
69.8k
        // only do this when f is identity (i.e. Val == Condition), but we
1437
69.8k
        // should be able to do this for any injective f.
1438
69.8k
        if (Case.getCaseSuccessor() != BBTo && 
Condition == Val69.7k
)
1439
68.4k
          EdgesVals = EdgesVals.difference(EdgeVal);
1440
118k
      } else if (Case.getCaseSuccessor() == BBTo)
1441
61.9k
        EdgesVals = EdgesVals.unionWith(EdgeVal);
1442
188k
    }
1443
40.2k
    Result = ValueLatticeElement::getRange(std::move(EdgesVals));
1444
40.2k
    return true;
1445
32.8M
  }
1446
32.8M
  return false;
1447
32.8M
}
1448
1449
/// Compute the value of Val on the edge BBFrom -> BBTo or the value at
1450
/// the basic block if the edge does not constrain Val.
1451
bool LazyValueInfoImpl::getEdgeValue(Value *Val, BasicBlock *BBFrom,
1452
                                     BasicBlock *BBTo,
1453
                                     ValueLatticeElement &Result,
1454
36.3M
                                     Instruction *CxtI) {
1455
36.3M
  // If already a constant, there is nothing to compute.
1456
36.3M
  if (Constant *VC = dyn_cast<Constant>(Val)) {
1457
644k
    Result = ValueLatticeElement::get(VC);
1458
644k
    return true;
1459
644k
  }
1460
35.6M
1461
35.6M
  ValueLatticeElement LocalResult;
1462
35.6M
  if (!getEdgeValueLocal(Val, BBFrom, BBTo, LocalResult))
1463
33.4M
    // If we couldn't constrain the value on the edge, LocalResult doesn't
1464
33.4M
    // provide any information.
1465
33.4M
    LocalResult = ValueLatticeElement::getOverdefined();
1466
35.6M
1467
35.6M
  if (hasSingleValue(LocalResult)) {
1468
131k
    // Can't get any more precise here
1469
131k
    Result = LocalResult;
1470
131k
    return true;
1471
131k
  }
1472
35.5M
1473
35.5M
  if (!hasBlockValue(Val, BBFrom)) {
1474
14.1M
    if (pushBlockValue(std::make_pair(BBFrom, Val)))
1475
13.1M
      return false;
1476
1.00M
    // No new information.
1477
1.00M
    Result = LocalResult;
1478
1.00M
    return true;
1479
1.00M
  }
1480
21.3M
1481
21.3M
  // Try to intersect ranges of the BB and the constraint on the edge.
1482
21.3M
  ValueLatticeElement InBlock = getBlockValue(Val, BBFrom);
1483
21.3M
  intersectAssumeOrGuardBlockValueConstantRange(Val, InBlock,
1484
21.3M
                                                BBFrom->getTerminator());
1485
21.3M
  // We can use the context instruction (generically the ultimate instruction
1486
21.3M
  // the calling pass is trying to simplify) here, even though the result of
1487
21.3M
  // this function is generally cached when called from the solve* functions
1488
21.3M
  // (and that cached result might be used with queries using a different
1489
21.3M
  // context instruction), because when this function is called from the solve*
1490
21.3M
  // functions, the context instruction is not provided. When called from
1491
21.3M
  // LazyValueInfoImpl::getValueOnEdge, the context instruction is provided,
1492
21.3M
  // but then the result is not cached.
1493
21.3M
  intersectAssumeOrGuardBlockValueConstantRange(Val, InBlock, CxtI);
1494
21.3M
1495
21.3M
  Result = intersect(LocalResult, InBlock);
1496
21.3M
  return true;
1497
21.3M
}
1498
1499
ValueLatticeElement LazyValueInfoImpl::getValueInBlock(Value *V, BasicBlock *BB,
1500
9.84M
                                                       Instruction *CxtI) {
1501
9.84M
  LLVM_DEBUG(dbgs() << "LVI Getting block end value " << *V << " at '"
1502
9.84M
                    << BB->getName() << "'\n");
1503
9.84M
1504
9.84M
  assert(BlockValueStack.empty() && BlockValueSet.empty());
1505
9.84M
  if (!hasBlockValue(V, BB)) {
1506
7.47M
    pushBlockValue(std::make_pair(BB, V));
1507
7.47M
    solve();
1508
7.47M
  }
1509
9.84M
  ValueLatticeElement Result = getBlockValue(V, BB);
1510
9.84M
  intersectAssumeOrGuardBlockValueConstantRange(V, Result, CxtI);
1511
9.84M
1512
9.84M
  LLVM_DEBUG(dbgs() << "  Result = " << Result << "\n");
1513
9.84M
  return Result;
1514
9.84M
}
1515
1516
5.91M
ValueLatticeElement LazyValueInfoImpl::getValueAt(Value *V, Instruction *CxtI) {
1517
5.91M
  LLVM_DEBUG(dbgs() << "LVI Getting value " << *V << " at '" << CxtI->getName()
1518
5.91M
                    << "'\n");
1519
5.91M
1520
5.91M
  if (auto *C = dyn_cast<Constant>(V))
1521
3.64k
    return ValueLatticeElement::get(C);
1522
5.91M
1523
5.91M
  ValueLatticeElement Result = ValueLatticeElement::getOverdefined();
1524
5.91M
  if (auto *I = dyn_cast<Instruction>(V))
1525
4.32M
    Result = getFromRangeMetadata(I);
1526
5.91M
  intersectAssumeOrGuardBlockValueConstantRange(V, Result, CxtI);
1527
5.91M
1528
5.91M
  LLVM_DEBUG(dbgs() << "  Result = " << Result << "\n");
1529
5.91M
  return Result;
1530
5.91M
}
1531
1532
ValueLatticeElement LazyValueInfoImpl::
1533
getValueOnEdge(Value *V, BasicBlock *FromBB, BasicBlock *ToBB,
1534
6.28M
               Instruction *CxtI) {
1535
6.28M
  LLVM_DEBUG(dbgs() << "LVI Getting edge value " << *V << " from '"
1536
6.28M
                    << FromBB->getName() << "' to '" << ToBB->getName()
1537
6.28M
                    << "'\n");
1538
6.28M
1539
6.28M
  ValueLatticeElement Result;
1540
6.28M
  if (!getEdgeValue(V, FromBB, ToBB, Result, CxtI)) {
1541
2.98M
    solve();
1542
2.98M
    bool WasFastQuery = getEdgeValue(V, FromBB, ToBB, Result, CxtI);
1543
2.98M
    (void)WasFastQuery;
1544
2.98M
    assert(WasFastQuery && "More work to do after problem solved?");
1545
2.98M
  }
1546
6.28M
1547
6.28M
  LLVM_DEBUG(dbgs() << "  Result = " << Result << "\n");
1548
6.28M
  return Result;
1549
6.28M
}
1550
1551
void LazyValueInfoImpl::threadEdge(BasicBlock *PredBB, BasicBlock *OldSucc,
1552
48.6k
                                   BasicBlock *NewSucc) {
1553
48.6k
  TheCache.threadEdgeImpl(OldSucc, NewSucc);
1554
48.6k
}
1555
1556
//===----------------------------------------------------------------------===//
1557
//                            LazyValueInfo Impl
1558
//===----------------------------------------------------------------------===//
1559
1560
/// This lazily constructs the LazyValueInfoImpl.
1561
static LazyValueInfoImpl &getImpl(void *&PImpl, AssumptionCache *AC,
1562
                                  const DataLayout *DL,
1563
29.9M
                                  DominatorTree *DT = nullptr) {
1564
29.9M
  if (!PImpl) {
1565
854k
    assert(DL && "getCache() called with a null DataLayout");
1566
854k
    PImpl = new LazyValueInfoImpl(AC, *DL, DT);
1567
854k
  }
1568
29.9M
  return *static_cast<LazyValueInfoImpl*>(PImpl);
1569
29.9M
}
1570
1571
987k
bool LazyValueInfoWrapperPass::runOnFunction(Function &F) {
1572
987k
  Info.AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
1573
987k
  const DataLayout &DL = F.getParent()->getDataLayout();
1574
987k
1575
987k
  DominatorTreeWrapperPass *DTWP =
1576
987k
      getAnalysisIfAvailable<DominatorTreeWrapperPass>();
1577
987k
  Info.DT = DTWP ? 
&DTWP->getDomTree()931k
:
nullptr55.0k
;
1578
987k
  Info.TLI = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
1579
987k
1580
987k
  if (Info.PImpl)
1581
0
    getImpl(Info.PImpl, Info.AC, &DL, Info.DT).clear();
1582
987k
1583
987k
  // Fully lazy.
1584
987k
  return false;
1585
987k
}
1586
1587
32.3k
void LazyValueInfoWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
1588
32.3k
  AU.setPreservesAll();
1589
32.3k
  AU.addRequired<AssumptionCacheTracker>();
1590
32.3k
  AU.addRequired<TargetLibraryInfoWrapperPass>();
1591
32.3k
}
1592
1593
1.91M
LazyValueInfo &LazyValueInfoWrapperPass::getLVI() { return Info; }
1594
1595
38.0k
LazyValueInfo::~LazyValueInfo() { releaseMemory(); }
1596
1597
1.02M
void LazyValueInfo::releaseMemory() {
1598
1.02M
  // If the cache was allocated, free it.
1599
1.02M
  if (PImpl) {
1600
854k
    delete &getImpl(PImpl, AC, nullptr);
1601
854k
    PImpl = nullptr;
1602
854k
  }
1603
1.02M
}
1604
1605
bool LazyValueInfo::invalidate(Function &F, const PreservedAnalyses &PA,
1606
1.63k
                               FunctionAnalysisManager::Invalidator &Inv) {
1607
1.63k
  // We need to invalidate if we have either failed to preserve this analyses
1608
1.63k
  // result directly or if any of its dependencies have been invalidated.
1609
1.63k
  auto PAC = PA.getChecker<LazyValueAnalysis>();
1610
1.63k
  if (!(PAC.preserved() || 
PAC.preservedSet<AllAnalysesOn<Function>>()1.59k
) ||
1611
1.63k
      
(40
DT40
&&
Inv.invalidate<DominatorTreeAnalysis>(F, PA)38
))
1612
1.59k
    return true;
1613
39
1614
39
  return false;
1615
39
}
1616
1617
987k
void LazyValueInfoWrapperPass::releaseMemory() { Info.releaseMemory(); }
1618
1619
LazyValueInfo LazyValueAnalysis::run(Function &F,
1620
1.91k
                                     FunctionAnalysisManager &FAM) {
1621
1.91k
  auto &AC = FAM.getResult<AssumptionAnalysis>(F);
1622
1.91k
  auto &TLI = FAM.getResult<TargetLibraryAnalysis>(F);
1623
1.91k
  auto *DT = FAM.getCachedResult<DominatorTreeAnalysis>(F);
1624
1.91k
1625
1.91k
  return LazyValueInfo(&AC, &F.getParent()->getDataLayout(), &TLI, DT);
1626
1.91k
}
1627
1628
/// Returns true if we can statically tell that this value will never be a
1629
/// "useful" constant.  In practice, this means we've got something like an
1630
/// alloca or a malloc call for which a comparison against a constant can
1631
/// only be guarding dead code.  Note that we are potentially giving up some
1632
/// precision in dead code (a constant result) in favour of avoiding a
1633
/// expensive search for a easily answered common query.
1634
8.15M
static bool isKnownNonConstant(Value *V) {
1635
8.15M
  V = V->stripPointerCasts();
1636
8.15M
  // The return val of alloc cannot be a Constant.
1637
8.15M
  if (isa<AllocaInst>(V))
1638
210k
    return true;
1639
7.94M
  return false;
1640
7.94M
}
1641
1642
Constant *LazyValueInfo::getConstant(Value *V, BasicBlock *BB,
1643
8.15M
                                     Instruction *CxtI) {
1644
8.15M
  // Bail out early if V is known not to be a Constant.
1645
8.15M
  if (isKnownNonConstant(V))
1646
210k
    return nullptr;
1647
7.94M
1648
7.94M
  const DataLayout &DL = BB->getModule()->getDataLayout();
1649
7.94M
  ValueLatticeElement Result =
1650
7.94M
      getImpl(PImpl, AC, &DL, DT).getValueInBlock(V, BB, CxtI);
1651
7.94M
1652
7.94M
  if (Result.isConstant())
1653
2
    return Result.getConstant();
1654
7.94M
  if (Result.isConstantRange()) {
1655
223k
    const ConstantRange &CR = Result.getConstantRange();
1656
223k
    if (const APInt *SingleVal = CR.getSingleElement())
1657
46
      return ConstantInt::get(V->getContext(), *SingleVal);
1658
7.94M
  }
1659
7.94M
  return nullptr;
1660
7.94M
}
1661
1662
ConstantRange LazyValueInfo::getConstantRange(Value *V, BasicBlock *BB,
1663
1.90M
                                              Instruction *CxtI) {
1664
1.90M
  assert(V->getType()->isIntegerTy());
1665
1.90M
  unsigned Width = V->getType()->getIntegerBitWidth();
1666
1.90M
  const DataLayout &DL = BB->getModule()->getDataLayout();
1667
1.90M
  ValueLatticeElement Result =
1668
1.90M
      getImpl(PImpl, AC, &DL, DT).getValueInBlock(V, BB, CxtI);
1669
1.90M
  if (Result.isUndefined())
1670
1
    return ConstantRange::getEmpty(Width);
1671
1.90M
  if (Result.isConstantRange())
1672
1.08M
    return Result.getConstantRange();
1673
820k
  // We represent ConstantInt constants as constant ranges but other kinds
1674
820k
  // of integer constants, i.e. ConstantExpr will be tagged as constants
1675
820k
  assert(!(Result.isConstant() && isa<ConstantInt>(Result.getConstant())) &&
1676
820k
         "ConstantInt value must be represented as constantrange");
1677
820k
  return ConstantRange::getFull(Width);
1678
820k
}
1679
1680
/// Determine whether the specified value is known to be a
1681
/// constant on the specified edge. Return null if not.
1682
Constant *LazyValueInfo::getConstantOnEdge(Value *V, BasicBlock *FromBB,
1683
                                           BasicBlock *ToBB,
1684
2.93M
                                           Instruction *CxtI) {
1685
2.93M
  const DataLayout &DL = FromBB->getModule()->getDataLayout();
1686
2.93M
  ValueLatticeElement Result =
1687
2.93M
      getImpl(PImpl, AC, &DL, DT).getValueOnEdge(V, FromBB, ToBB, CxtI);
1688
2.93M
1689
2.93M
  if (Result.isConstant())
1690
2.05k
    return Result.getConstant();
1691
2.92M
  if (Result.isConstantRange()) {
1692
837k
    const ConstantRange &CR = Result.getConstantRange();
1693
837k
    if (const APInt *SingleVal = CR.getSingleElement())
1694
52.9k
      return ConstantInt::get(V->getContext(), *SingleVal);
1695
2.87M
  }
1696
2.87M
  return nullptr;
1697
2.87M
}
1698
1699
ConstantRange LazyValueInfo::getConstantRangeOnEdge(Value *V,
1700
                                                    BasicBlock *FromBB,
1701
                                                    BasicBlock *ToBB,
1702
52.7k
                                                    Instruction *CxtI) {
1703
52.7k
  unsigned Width = V->getType()->getIntegerBitWidth();
1704
52.7k
  const DataLayout &DL = FromBB->getModule()->getDataLayout();
1705
52.7k
  ValueLatticeElement Result =
1706
52.7k
      getImpl(PImpl, AC, &DL, DT).getValueOnEdge(V, FromBB, ToBB, CxtI);
1707
52.7k
1708
52.7k
  if (Result.isUndefined())
1709
2
    return ConstantRange::getEmpty(Width);
1710
52.7k
  if (Result.isConstantRange())
1711
33.1k
    return Result.getConstantRange();
1712
19.6k
  // We represent ConstantInt constants as constant ranges but other kinds
1713
19.6k
  // of integer constants, i.e. ConstantExpr will be tagged as constants
1714
19.6k
  assert(!(Result.isConstant() && isa<ConstantInt>(Result.getConstant())) &&
1715
19.6k
         "ConstantInt value must be represented as constantrange");
1716
19.6k
  return ConstantRange::getFull(Width);
1717
19.6k
}
1718
1719
static LazyValueInfo::Tristate
1720
getPredicateResult(unsigned Pred, Constant *C, const ValueLatticeElement &Val,
1721
9.22M
                   const DataLayout &DL, TargetLibraryInfo *TLI) {
1722
9.22M
  // If we know the value is a constant, evaluate the conditional.
1723
9.22M
  Constant *Res = nullptr;
1724
9.22M
  if (Val.isConstant()) {
1725
12.4k
    Res = ConstantFoldCompareInstOperands(Pred, Val.getConstant(), C, DL, TLI);
1726
12.4k
    if (ConstantInt *ResCI = dyn_cast<ConstantInt>(Res))
1727
12.3k
      return ResCI->isZero() ? 
LazyValueInfo::False2.36k
:
LazyValueInfo::True10.0k
;
1728
12
    return LazyValueInfo::Unknown;
1729
12
  }
1730
9.21M
1731
9.21M
  if (Val.isConstantRange()) {
1732
987k
    ConstantInt *CI = dyn_cast<ConstantInt>(C);
1733
987k
    if (!CI) 
return LazyValueInfo::Unknown20
;
1734
987k
1735
987k
    const ConstantRange &CR = Val.getConstantRange();
1736
987k
    if (Pred == ICmpInst::ICMP_EQ) {
1737
525k
      if (!CR.contains(CI->getValue()))
1738
28.8k
        return LazyValueInfo::False;
1739
497k
1740
497k
      if (CR.isSingleElement())
1741
31.5k
        return LazyValueInfo::True;
1742
461k
    } else if (Pred == ICmpInst::ICMP_NE) {
1743
35.9k
      if (!CR.contains(CI->getValue()))
1744
1.35k
        return LazyValueInfo::True;
1745
34.5k
1746
34.5k
      if (CR.isSingleElement())
1747
779
        return LazyValueInfo::False;
1748
425k
    } else {
1749
425k
      // Handle more complex predicates.
1750
425k
      ConstantRange TrueValues = ConstantRange::makeExactICmpRegion(
1751
425k
          (ICmpInst::Predicate)Pred, CI->getValue());
1752
425k
      if (TrueValues.contains(CR))
1753
21.4k
        return LazyValueInfo::True;
1754
403k
      if (TrueValues.inverse().contains(CR))
1755
59.4k
        return LazyValueInfo::False;
1756
843k
    }
1757
843k
    return LazyValueInfo::Unknown;
1758
843k
  }
1759
8.22M
1760
8.22M
  if (Val.isNotConstant()) {
1761
76.9k
    // If this is an equality comparison, we can try to fold it knowing that
1762
76.9k
    // "V != C1".
1763
76.9k
    if (Pred == ICmpInst::ICMP_EQ) {
1764
68.2k
      // !C1 == C -> false iff C1 == C.
1765
68.2k
      Res = ConstantFoldCompareInstOperands(ICmpInst::ICMP_NE,
1766
68.2k
                                            Val.getNotConstant(), C, DL,
1767
68.2k
                                            TLI);
1768
68.2k
      if (Res->isNullValue())
1769
65.2k
        return LazyValueInfo::False;
1770
8.72k
    } else if (Pred == ICmpInst::ICMP_NE) {
1771
1.74k
      // !C1 != C -> true iff C1 == C.
1772
1.74k
      Res = ConstantFoldCompareInstOperands(ICmpInst::ICMP_NE,
1773
1.74k
                                            Val.getNotConstant(), C, DL,
1774
1.74k
                                            TLI);
1775
1.74k
      if (Res->isNullValue())
1776
1.71k
        return LazyValueInfo::True;
1777
10.0k
    }
1778
10.0k
    return LazyValueInfo::Unknown;
1779
10.0k
  }
1780
8.14M
1781
8.14M
  return LazyValueInfo::Unknown;
1782
8.14M
}
1783
1784
/// Determine whether the specified value comparison with a constant is known to
1785
/// be true or false on the specified CFG edge. Pred is a CmpInst predicate.
1786
LazyValueInfo::Tristate
1787
LazyValueInfo::getPredicateOnEdge(unsigned Pred, Value *V, Constant *C,
1788
                                  BasicBlock *FromBB, BasicBlock *ToBB,
1789
3.30M
                                  Instruction *CxtI) {
1790
3.30M
  const DataLayout &DL = FromBB->getModule()->getDataLayout();
1791
3.30M
  ValueLatticeElement Result =
1792
3.30M
      getImpl(PImpl, AC, &DL, DT).getValueOnEdge(V, FromBB, ToBB, CxtI);
1793
3.30M
1794
3.30M
  return getPredicateResult(Pred, C, Result, DL, TLI);
1795
3.30M
}
1796
1797
LazyValueInfo::Tristate
1798
LazyValueInfo::getPredicateAt(unsigned Pred, Value *V, Constant *C,
1799
5.95M
                              Instruction *CxtI) {
1800
5.95M
  // Is or is not NonNull are common predicates being queried. If
1801
5.95M
  // isKnownNonZero can tell us the result of the predicate, we can
1802
5.95M
  // return it quickly. But this is only a fastpath, and falling
1803
5.95M
  // through would still be correct.
1804
5.95M
  const DataLayout &DL = CxtI->getModule()->getDataLayout();
1805
5.95M
  if (V->getType()->isPointerTy() && 
C->isNullValue()3.35M
&&
1806
5.95M
      
isKnownNonZero(V->stripPointerCastsSameRepresentation(), DL)3.34M
) {
1807
41.5k
    if (Pred == ICmpInst::ICMP_EQ)
1808
41.5k
      return LazyValueInfo::False;
1809
20
    else if (Pred == ICmpInst::ICMP_NE)
1810
20
      return LazyValueInfo::True;
1811
5.91M
  }
1812
5.91M
  ValueLatticeElement Result = getImpl(PImpl, AC, &DL, DT).getValueAt(V, CxtI);
1813
5.91M
  Tristate Ret = getPredicateResult(Pred, C, Result, DL, TLI);
1814
5.91M
  if (Ret != Unknown)
1815
3.68k
    return Ret;
1816
5.91M
1817
5.91M
  // Note: The following bit of code is somewhat distinct from the rest of LVI;
1818
5.91M
  // LVI as a whole tries to compute a lattice value which is conservatively
1819
5.91M
  // correct at a given location.  In this case, we have a predicate which we
1820
5.91M
  // weren't able to prove about the merged result, and we're pushing that
1821
5.91M
  // predicate back along each incoming edge to see if we can prove it
1822
5.91M
  // separately for each input.  As a motivating example, consider:
1823
5.91M
  // bb1:
1824
5.91M
  //   %v1 = ... ; constantrange<1, 5>
1825
5.91M
  //   br label %merge
1826
5.91M
  // bb2:
1827
5.91M
  //   %v2 = ... ; constantrange<10, 20>
1828
5.91M
  //   br label %merge
1829
5.91M
  // merge:
1830
5.91M
  //   %phi = phi [%v1, %v2] ; constantrange<1,20>
1831
5.91M
  //   %pred = icmp eq i32 %phi, 8
1832
5.91M
  // We can't tell from the lattice value for '%phi' that '%pred' is false
1833
5.91M
  // along each path, but by checking the predicate over each input separately,
1834
5.91M
  // we can.
1835
5.91M
  // We limit the search to one step backwards from the current BB and value.
1836
5.91M
  // We could consider extending this to search further backwards through the
1837
5.91M
  // CFG and/or value graph, but there are non-obvious compile time vs quality
1838
5.91M
  // tradeoffs.
1839
5.91M
  
if (5.91M
CxtI5.91M
) {
1840
5.91M
    BasicBlock *BB = CxtI->getParent();
1841
5.91M
1842
5.91M
    // Function entry or an unreachable block.  Bail to avoid confusing
1843
5.91M
    // analysis below.
1844
5.91M
    pred_iterator PI = pred_begin(BB), PE = pred_end(BB);
1845
5.91M
    if (PI == PE)
1846
1.58M
      return Unknown;
1847
4.33M
1848
4.33M
    // If V is a PHI node in the same block as the context, we need to ask
1849
4.33M
    // questions about the predicate as applied to the incoming value along
1850
4.33M
    // each edge. This is useful for eliminating cases where the predicate is
1851
4.33M
    // known along all incoming edges.
1852
4.33M
    if (auto *PHI = dyn_cast<PHINode>(V))
1853
439k
      if (PHI->getParent() == BB) {
1854
202k
        Tristate Baseline = Unknown;
1855
315k
        for (unsigned i = 0, e = PHI->getNumIncomingValues(); i < e; 
i++113k
) {
1856
310k
          Value *Incoming = PHI->getIncomingValue(i);
1857
310k
          BasicBlock *PredBB = PHI->getIncomingBlock(i);
1858
310k
          // Note that PredBB may be BB itself.
1859
310k
          Tristate Result = getPredicateOnEdge(Pred, Incoming, C, PredBB, BB,
1860
310k
                                               CxtI);
1861
310k
1862
310k
          // Keep going as long as we've seen a consistent known result for
1863
310k
          // all inputs.
1864
310k
          Baseline = (i == 0) ? 
Result202k
/* First iteration */
1865
310k
            : 
(Baseline == Result 107k
?
Baseline51.6k
:
Unknown56.3k
); /* All others */
1866
310k
          if (Baseline == Unknown)
1867
197k
            break;
1868
310k
        }
1869
202k
        if (Baseline != Unknown)
1870
5.04k
          return Baseline;
1871
4.32M
      }
1872
4.32M
1873
4.32M
    // For a comparison where the V is outside this block, it's possible
1874
4.32M
    // that we've branched on it before. Look to see if the value is known
1875
4.32M
    // on all incoming edges.
1876
4.32M
    if (!isa<Instruction>(V) ||
1877
4.32M
        
cast<Instruction>(V)->getParent() != BB3.39M
) {
1878
1.86M
      // For predecessor edge, determine if the comparison is true or false
1879
1.86M
      // on that edge. If they're all true or all false, we can conclude
1880
1.86M
      // the value of the comparison in this block.
1881
1.86M
      Tristate Baseline = getPredicateOnEdge(Pred, V, C, *PI, BB, CxtI);
1882
1.86M
      if (Baseline != Unknown) {
1883
49.8k
        // Check that all remaining incoming values match the first one.
1884
62.7k
        while (++PI != PE) {
1885
25.2k
          Tristate Ret = getPredicateOnEdge(Pred, V, C, *PI, BB, CxtI);
1886
25.2k
          if (Ret != Baseline) 
break12.3k
;
1887
25.2k
        }
1888
49.8k
        // If we terminated early, then one of the values didn't match.
1889
49.8k
        if (PI == PE) {
1890
37.5k
          return Baseline;
1891
37.5k
        }
1892
4.28M
      }
1893
1.86M
    }
1894
4.32M
  }
1895
4.28M
  return Unknown;
1896
4.28M
}
1897
1898
void LazyValueInfo::threadEdge(BasicBlock *PredBB, BasicBlock *OldSucc,
1899
48.8k
                               BasicBlock *NewSucc) {
1900
48.8k
  if (PImpl) {
1901
48.6k
    const DataLayout &DL = PredBB->getModule()->getDataLayout();
1902
48.6k
    getImpl(PImpl, AC, &DL, DT).threadEdge(PredBB, OldSucc, NewSucc);
1903
48.6k
  }
1904
48.8k
}
1905
1906
356k
void LazyValueInfo::eraseBlock(BasicBlock *BB) {
1907
356k
  if (PImpl) {
1908
342k
    const DataLayout &DL = BB->getModule()->getDataLayout();
1909
342k
    getImpl(PImpl, AC, &DL, DT).eraseBlock(BB);
1910
342k
  }
1911
356k
}
1912
1913
1914
4
void LazyValueInfo::printLVI(Function &F, DominatorTree &DTree, raw_ostream &OS) {
1915
4
  if (PImpl) {
1916
4
    getImpl(PImpl, AC, DL, DT).printLVI(F, DTree, OS);
1917
4
  }
1918
4
}
1919
1920
4.13M
void LazyValueInfo::disableDT() {
1921
4.13M
  if (PImpl)
1922
4.07M
    getImpl(PImpl, AC, DL, DT).disableDT();
1923
4.13M
}
1924
1925
3.51M
void LazyValueInfo::enableDT() {
1926
3.51M
  if (PImpl)
1927
2.56M
    getImpl(PImpl, AC, DL, DT).enableDT();
1928
3.51M
}
1929
1930
// Print the LVI for the function arguments at the start of each basic block.
1931
void LazyValueInfoAnnotatedWriter::emitBasicBlockStartAnnot(
1932
16
    const BasicBlock *BB, formatted_raw_ostream &OS) {
1933
16
  // Find if there are latticevalues defined for arguments of the function.
1934
16
  auto *F = BB->getParent();
1935
37
  for (auto &Arg : F->args()) {
1936
37
    ValueLatticeElement Result = LVIImpl->getValueInBlock(
1937
37
        const_cast<Argument *>(&Arg), const_cast<BasicBlock *>(BB));
1938
37
    if (Result.isUndefined())
1939
0
      continue;
1940
37
    OS << "; LatticeVal for: '" << Arg << "' is: " << Result << "\n";
1941
37
  }
1942
16
}
1943
1944
// This function prints the LVI analysis for the instruction I at the beginning
1945
// of various basic blocks. It relies on calculated values that are stored in
1946
// the LazyValueInfoCache, and in the absence of cached values, recalculate the
1947
// LazyValueInfo for `I`, and print that info.
1948
void LazyValueInfoAnnotatedWriter::emitInstructionAnnot(
1949
43
    const Instruction *I, formatted_raw_ostream &OS) {
1950
43
1951
43
  auto *ParentBB = I->getParent();
1952
43
  SmallPtrSet<const BasicBlock*, 16> BlocksContainingLVI;
1953
43
  // We can generate (solve) LVI values only for blocks that are dominated by
1954
43
  // the I's parent. However, to avoid generating LVI for all dominating blocks,
1955
43
  // that contain redundant/uninteresting information, we print LVI for
1956
43
  // blocks that may use this LVI information (such as immediate successor
1957
43
  // blocks, and blocks that contain uses of `I`).
1958
106
  auto printResult = [&](const BasicBlock *BB) {
1959
106
    if (!BlocksContainingLVI.insert(BB).second)
1960
32
      return;
1961
74
    ValueLatticeElement Result = LVIImpl->getValueInBlock(
1962
74
        const_cast<Instruction *>(I), const_cast<BasicBlock *>(BB));
1963
74
      OS << "; LatticeVal for: '" << *I << "' in BB: '";
1964
74
      BB->printAsOperand(OS, false);
1965
74
      OS << "' is: " << Result << "\n";
1966
74
  };
1967
43
1968
43
  printResult(ParentBB);
1969
43
  // Print the LVI analysis results for the immediate successor blocks, that
1970
43
  // are dominated by `ParentBB`.
1971
43
  for (auto *BBSucc : successors(ParentBB))
1972
74
    if (DT.dominates(ParentBB, BBSucc))
1973
39
      printResult(BBSucc);
1974
43
1975
43
  // Print LVI in blocks where `I` is used.
1976
43
  for (auto *U : I->users())
1977
26
    if (auto *UseI = dyn_cast<Instruction>(U))
1978
26
      if (!isa<PHINode>(UseI) || 
DT.dominates(ParentBB, UseI->getParent())3
)
1979
24
        printResult(UseI->getParent());
1980
43
1981
43
}
1982
1983
namespace {
1984
// Printer class for LazyValueInfo results.
1985
class LazyValueInfoPrinter : public FunctionPass {
1986
public:
1987
  static char ID; // Pass identification, replacement for typeid
1988
0
  LazyValueInfoPrinter() : FunctionPass(ID) {
1989
0
    initializeLazyValueInfoPrinterPass(*PassRegistry::getPassRegistry());
1990
0
  }
1991
1992
0
  void getAnalysisUsage(AnalysisUsage &AU) const override {
1993
0
    AU.setPreservesAll();
1994
0
    AU.addRequired<LazyValueInfoWrapperPass>();
1995
0
    AU.addRequired<DominatorTreeWrapperPass>();
1996
0
  }
1997
1998
  // Get the mandatory dominator tree analysis and pass this in to the
1999
  // LVIPrinter. We cannot rely on the LVI's DT, since it's optional.
2000
0
  bool runOnFunction(Function &F) override {
2001
0
    dbgs() << "LVI for function '" << F.getName() << "':\n";
2002
0
    auto &LVI = getAnalysis<LazyValueInfoWrapperPass>().getLVI();
2003
0
    auto &DTree = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
2004
0
    LVI.printLVI(F, DTree, dbgs());
2005
0
    return false;
2006
0
  }
2007
};
2008
}
2009
2010
char LazyValueInfoPrinter::ID = 0;
2011
11.0k
INITIALIZE_PASS_BEGIN(LazyValueInfoPrinter, "print-lazy-value-info",
2012
11.0k
                "Lazy Value Info Printer Pass", false, false)
2013
11.0k
INITIALIZE_PASS_DEPENDENCY(LazyValueInfoWrapperPass)
2014
11.0k
INITIALIZE_PASS_END(LazyValueInfoPrinter, "print-lazy-value-info",
2015
                "Lazy Value Info Printer Pass", false, false)