Coverage Report

Created: 2017-10-03 07:32

/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/lib/Analysis/Loads.cpp
Line
Count
Source (jump to first uncovered line)
1
//===- Loads.cpp - Local load analysis ------------------------------------===//
2
//
3
//                     The LLVM Compiler Infrastructure
4
//
5
// This file is distributed under the University of Illinois Open Source
6
// License. See LICENSE.TXT for details.
7
//
8
//===----------------------------------------------------------------------===//
9
//
10
// This file defines simple local analyses for load instructions.
11
//
12
//===----------------------------------------------------------------------===//
13
14
#include "llvm/Analysis/Loads.h"
15
#include "llvm/Analysis/AliasAnalysis.h"
16
#include "llvm/Analysis/ValueTracking.h"
17
#include "llvm/IR/DataLayout.h"
18
#include "llvm/IR/GlobalAlias.h"
19
#include "llvm/IR/GlobalVariable.h"
20
#include "llvm/IR/IntrinsicInst.h"
21
#include "llvm/IR/LLVMContext.h"
22
#include "llvm/IR/Module.h"
23
#include "llvm/IR/Operator.h"
24
#include "llvm/IR/Statepoint.h"
25
26
using namespace llvm;
27
28
static bool isAligned(const Value *Base, const APInt &Offset, unsigned Align,
29
2.30M
                      const DataLayout &DL) {
30
2.30M
  APInt BaseAlign(Offset.getBitWidth(), Base->getPointerAlignment(DL));
31
2.30M
32
2.30M
  if (
!BaseAlign2.30M
) {
33
420k
    Type *Ty = Base->getType()->getPointerElementType();
34
420k
    if (!Ty->isSized())
35
2
      return false;
36
420k
    BaseAlign = DL.getABITypeAlignment(Ty);
37
420k
  }
38
2.30M
39
2.30M
  APInt Alignment(Offset.getBitWidth(), Align);
40
2.30M
41
2.30M
  assert(Alignment.isPowerOf2() && "must be a power of 2!");
42
2.30M
  return BaseAlign.uge(Alignment) && !(Offset & (Alignment-1));
43
2.30M
}
44
45
2.30M
static bool isAligned(const Value *Base, unsigned Align, const DataLayout &DL) {
46
2.30M
  Type *Ty = Base->getType();
47
2.30M
  assert(Ty->isSized() && "must be sized");
48
2.30M
  APInt Offset(DL.getTypeStoreSizeInBits(Ty), 0);
49
2.30M
  return isAligned(Base, Offset, Align, DL);
50
2.30M
}
51
52
/// Test if V is always a pointer to allocated and suitably aligned memory for
53
/// a simple load or store.
54
static bool isDereferenceableAndAlignedPointer(
55
    const Value *V, unsigned Align, const APInt &Size, const DataLayout &DL,
56
    const Instruction *CtxI, const DominatorTree *DT,
57
11.8M
    SmallPtrSetImpl<const Value *> &Visited) {
58
11.8M
  // Already visited?  Bail out, we've likely hit unreachable code.
59
11.8M
  if (!Visited.insert(V).second)
60
8
    return false;
61
11.8M
62
11.8M
  // Note that it is not safe to speculate into a malloc'd region because
63
11.8M
  // malloc may return null.
64
11.8M
65
11.8M
  // bitcast instructions are no-ops as far as dereferenceability is concerned.
66
11.8M
  
if (const BitCastOperator *11.8M
BC11.8M
= dyn_cast<BitCastOperator>(V))
67
1.03M
    return isDereferenceableAndAlignedPointer(BC->getOperand(0), Align, Size,
68
1.03M
                                              DL, CtxI, DT, Visited);
69
10.7M
70
10.7M
  bool CheckForNonNull = false;
71
10.7M
  APInt KnownDerefBytes(Size.getBitWidth(),
72
10.7M
                        V->getPointerDereferenceableBytes(DL, CheckForNonNull));
73
10.7M
  if (
KnownDerefBytes.getBoolValue()10.7M
) {
74
2.30M
    if (KnownDerefBytes.uge(Size))
75
2.30M
      
if (2.30M
!CheckForNonNull || 2.30M
isKnownNonZero(V, DL, 0, nullptr, CtxI, DT)17
)
76
2.30M
        return isAligned(V, Align, DL);
77
8.48M
  }
78
8.48M
79
8.48M
  // For GEPs, determine if the indexing lands within the allocated object.
80
8.48M
  
if (const GEPOperator *8.48M
GEP8.48M
= dyn_cast<GEPOperator>(V)) {
81
4.94M
    const Value *Base = GEP->getPointerOperand();
82
4.94M
83
4.94M
    APInt Offset(DL.getPointerTypeSizeInBits(GEP->getType()), 0);
84
4.94M
    if (
!GEP->accumulateConstantOffset(DL, Offset) || 4.94M
Offset.isNegative()4.09M
||
85
4.03M
        !Offset.urem(APInt(Offset.getBitWidth(), Align)).isMinValue())
86
903k
      return false;
87
4.03M
88
4.03M
    // If the base pointer is dereferenceable for Offset+Size bytes, then the
89
4.03M
    // GEP (== Base + Offset) is dereferenceable for Size bytes.  If the base
90
4.03M
    // pointer is aligned to Align bytes, and the Offset is divisible by Align
91
4.03M
    // then the GEP (== Base + Offset == k_0 * Align + k_1 * Align) is also
92
4.03M
    // aligned to Align bytes.
93
4.03M
94
4.03M
    // Offset and Size may have different bit widths if we have visited an
95
4.03M
    // addrspacecast, so we can't do arithmetic directly on the APInt values.
96
4.03M
    return isDereferenceableAndAlignedPointer(
97
4.03M
        Base, Align, Offset + Size.sextOrTrunc(Offset.getBitWidth()),
98
4.03M
        DL, CtxI, DT, Visited);
99
4.03M
  }
100
3.54M
101
3.54M
  // For gc.relocate, look through relocations
102
3.54M
  
if (const GCRelocateInst *3.54M
RelocateInst3.54M
= dyn_cast<GCRelocateInst>(V))
103
5
    return isDereferenceableAndAlignedPointer(
104
5
        RelocateInst->getDerivedPtr(), Align, Size, DL, CtxI, DT, Visited);
105
3.54M
106
3.54M
  
if (const AddrSpaceCastInst *3.54M
ASC3.54M
= dyn_cast<AddrSpaceCastInst>(V))
107
140
    return isDereferenceableAndAlignedPointer(ASC->getOperand(0), Align, Size,
108
140
                                              DL, CtxI, DT, Visited);
109
3.54M
110
3.54M
  
if (auto 3.54M
CS3.54M
= ImmutableCallSite(V))
111
213k
    
if (const Value *213k
RV213k
= CS.getReturnedArgOperand())
112
328
      return isDereferenceableAndAlignedPointer(RV, Align, Size, DL, CtxI, DT,
113
328
                                                Visited);
114
3.53M
115
3.53M
  // If we don't know, assume the worst.
116
3.53M
  return false;
117
3.53M
}
118
119
bool llvm::isDereferenceableAndAlignedPointer(const Value *V, unsigned Align,
120
                                              const APInt &Size,
121
                                              const DataLayout &DL,
122
                                              const Instruction *CtxI,
123
9.90k
                                              const DominatorTree *DT) {
124
9.90k
  SmallPtrSet<const Value *, 32> Visited;
125
9.90k
  return ::isDereferenceableAndAlignedPointer(V, Align, Size, DL, CtxI, DT,
126
9.90k
                                              Visited);
127
9.90k
}
128
129
bool llvm::isDereferenceableAndAlignedPointer(const Value *V, unsigned Align,
130
                                              const DataLayout &DL,
131
                                              const Instruction *CtxI,
132
6.73M
                                              const DominatorTree *DT) {
133
6.73M
  // When dereferenceability information is provided by a dereferenceable
134
6.73M
  // attribute, we know exactly how many bytes are dereferenceable. If we can
135
6.73M
  // determine the exact offset to the attributed variable, we can use that
136
6.73M
  // information here.
137
6.73M
  Type *VTy = V->getType();
138
6.73M
  Type *Ty = VTy->getPointerElementType();
139
6.73M
140
6.73M
  // Require ABI alignment for loads without alignment specification
141
6.73M
  if (Align == 0)
142
106k
    Align = DL.getABITypeAlignment(Ty);
143
6.73M
144
6.73M
  if (!Ty->isSized())
145
306
    return false;
146
6.73M
147
6.73M
  SmallPtrSet<const Value *, 32> Visited;
148
6.73M
  return ::isDereferenceableAndAlignedPointer(
149
6.73M
      V, Align, APInt(DL.getTypeSizeInBits(VTy), DL.getTypeStoreSize(Ty)), DL,
150
6.73M
      CtxI, DT, Visited);
151
6.73M
}
152
153
bool llvm::isDereferenceablePointer(const Value *V, const DataLayout &DL,
154
                                    const Instruction *CtxI,
155
1.94M
                                    const DominatorTree *DT) {
156
1.94M
  return isDereferenceableAndAlignedPointer(V, 1, DL, CtxI, DT);
157
1.94M
}
158
159
/// \brief Test if A and B will obviously have the same value.
160
///
161
/// This includes recognizing that %t0 and %t1 will have the same
162
/// value in code like this:
163
/// \code
164
///   %t0 = getelementptr \@a, 0, 3
165
///   store i32 0, i32* %t0
166
///   %t1 = getelementptr \@a, 0, 3
167
///   %t2 = load i32* %t1
168
/// \endcode
169
///
170
14.9M
static bool AreEquivalentAddressValues(const Value *A, const Value *B) {
171
14.9M
  // Test if the values are trivially equivalent.
172
14.9M
  if (A == B)
173
22.1k
    return true;
174
14.9M
175
14.9M
  // Test if the values come from identical arithmetic instructions.
176
14.9M
  // Use isIdenticalToWhenDefined instead of isIdenticalTo because
177
14.9M
  // this function is only used when one address use dominates the
178
14.9M
  // other, which means that they'll always either have the same
179
14.9M
  // value or one of them will have an undefined value.
180
14.9M
  
if (14.9M
isa<BinaryOperator>(A) || 14.9M
isa<CastInst>(A)14.9M
||
isa<PHINode>(A)14.9M
||
181
14.4M
      isa<GetElementPtrInst>(A))
182
10.8M
    
if (const Instruction *10.8M
BI10.8M
= dyn_cast<Instruction>(B))
183
9.52M
      
if (9.52M
cast<Instruction>(A)->isIdenticalToWhenDefined(BI)9.52M
)
184
477
        return true;
185
14.9M
186
14.9M
  // Otherwise they may not be equivalent.
187
14.9M
  return false;
188
14.9M
}
189
190
/// \brief Check if executing a load of this pointer value cannot trap.
191
///
192
/// If DT and ScanFrom are specified this method performs context-sensitive
193
/// analysis and returns true if it is safe to load immediately before ScanFrom.
194
///
195
/// If it is not obviously safe to load from the specified pointer, we do
196
/// a quick local scan of the basic block containing \c ScanFrom, to determine
197
/// if the address is already accessed.
198
///
199
/// This uses the pointee type to determine how many bytes need to be safe to
200
/// load from the pointer.
201
bool llvm::isSafeToLoadUnconditionally(Value *V, unsigned Align,
202
                                       const DataLayout &DL,
203
                                       Instruction *ScanFrom,
204
13.7k
                                       const DominatorTree *DT) {
205
13.7k
  // Zero alignment means that the load has the ABI alignment for the target
206
13.7k
  if (Align == 0)
207
102
    Align = DL.getABITypeAlignment(V->getType()->getPointerElementType());
208
13.7k
  assert(isPowerOf2_32(Align));
209
13.7k
210
13.7k
  // If DT is not specified we can't make context-sensitive query
211
13.7k
  const Instruction* CtxI = DT ? 
ScanFrom0
:
nullptr13.7k
;
212
13.7k
  if (isDereferenceableAndAlignedPointer(V, Align, DL, CtxI, DT))
213
706
    return true;
214
13.0k
215
13.0k
  int64_t ByteOffset = 0;
216
13.0k
  Value *Base = V;
217
13.0k
  Base = GetPointerBaseWithConstantOffset(V, ByteOffset, DL);
218
13.0k
219
13.0k
  if (ByteOffset < 0) // out of bounds
220
20
    return false;
221
13.0k
222
13.0k
  Type *BaseType = nullptr;
223
13.0k
  unsigned BaseAlign = 0;
224
13.0k
  if (const AllocaInst *
AI13.0k
= dyn_cast<AllocaInst>(Base)) {
225
2
    // An alloca is safe to load from as load as it is suitably aligned.
226
2
    BaseType = AI->getAllocatedType();
227
2
    BaseAlign = AI->getAlignment();
228
13.0k
  } else 
if (const GlobalVariable *13.0k
GV13.0k
= dyn_cast<GlobalVariable>(Base)) {
229
2
    // Global variables are not necessarily safe to load from if they are
230
2
    // interposed arbitrarily. Their size may change or they may be weak and
231
2
    // require a test to determine if they were in fact provided.
232
2
    if (
!GV->isInterposable()2
) {
233
1
      BaseType = GV->getType()->getElementType();
234
1
      BaseAlign = GV->getAlignment();
235
1
    }
236
13.0k
  }
237
13.0k
238
13.0k
  PointerType *AddrTy = cast<PointerType>(V->getType());
239
13.0k
  uint64_t LoadSize = DL.getTypeStoreSize(AddrTy->getElementType());
240
13.0k
241
13.0k
  // If we found a base allocated type from either an alloca or global variable,
242
13.0k
  // try to see if we are definitively within the allocated region. We need to
243
13.0k
  // know the size of the base type and the loaded type to do anything in this
244
13.0k
  // case.
245
13.0k
  if (
BaseType && 13.0k
BaseType->isSized()3
) {
246
3
    if (BaseAlign == 0)
247
0
      BaseAlign = DL.getPrefTypeAlignment(BaseType);
248
3
249
3
    if (
Align <= BaseAlign3
) {
250
0
      // Check if the load is within the bounds of the underlying object.
251
0
      if (ByteOffset + LoadSize <= DL.getTypeAllocSize(BaseType) &&
252
0
          ((ByteOffset % Align) == 0))
253
0
        return true;
254
13.0k
    }
255
3
  }
256
13.0k
257
13.0k
  
if (13.0k
!ScanFrom13.0k
)
258
644
    return false;
259
12.4k
260
12.4k
  // Otherwise, be a little bit aggressive by scanning the local block where we
261
12.4k
  // want to check to see if the pointer is already being loaded or stored
262
12.4k
  // from/to.  If so, the previous load or store would have already trapped,
263
12.4k
  // so there is no harm doing an extra load (also, CSE will later eliminate
264
12.4k
  // the load entirely).
265
12.4k
  BasicBlock::iterator BBI = ScanFrom->getIterator(),
266
12.4k
                       E = ScanFrom->getParent()->begin();
267
12.4k
268
12.4k
  // We can at least always strip pointer casts even though we can't use the
269
12.4k
  // base here.
270
12.4k
  V = V->stripPointerCasts();
271
12.4k
272
156k
  while (
BBI != E156k
) {
273
145k
    --BBI;
274
145k
275
145k
    // If we see a free or a call which may write to memory (i.e. which might do
276
145k
    // a free) the pointer could be marked invalid.
277
145k
    if (
isa<CallInst>(BBI) && 145k
BBI->mayWriteToMemory()1.58k
&&
278
1.54k
        !isa<DbgInfoIntrinsic>(BBI))
279
1.54k
      return false;
280
143k
281
143k
    Value *AccessedPtr;
282
143k
    unsigned AccessedAlign;
283
143k
    if (LoadInst *
LI143k
= dyn_cast<LoadInst>(BBI)) {
284
26.6k
      AccessedPtr = LI->getPointerOperand();
285
26.6k
      AccessedAlign = LI->getAlignment();
286
143k
    } else 
if (StoreInst *117k
SI117k
= dyn_cast<StoreInst>(BBI)) {
287
11.8k
      AccessedPtr = SI->getPointerOperand();
288
11.8k
      AccessedAlign = SI->getAlignment();
289
11.8k
    } else
290
105k
      continue;
291
38.4k
292
38.4k
    Type *AccessedTy = AccessedPtr->getType()->getPointerElementType();
293
38.4k
    if (AccessedAlign == 0)
294
9
      AccessedAlign = DL.getABITypeAlignment(AccessedTy);
295
38.4k
    if (AccessedAlign < Align)
296
3.56k
      continue;
297
34.9k
298
34.9k
    // Handle trivial cases.
299
34.9k
    
if (34.9k
AccessedPtr == V34.9k
)
300
114
      return true;
301
34.8k
302
34.8k
    
if (34.8k
AreEquivalentAddressValues(AccessedPtr->stripPointerCasts(), V) &&
303
3
        LoadSize <= DL.getTypeStoreSize(AccessedTy))
304
3
      return true;
305
145k
  }
306
10.7k
  return false;
307
13.7k
}
308
309
/// DefMaxInstsToScan - the default number of maximum instructions
310
/// to scan in the block, used by FindAvailableLoadedValue().
311
/// FindAvailableLoadedValue() was introduced in r60148, to improve jump
312
/// threading in part by eliminating partially redundant loads.
313
/// At that point, the value of MaxInstsToScan was already set to '6'
314
/// without documented explanation.
315
cl::opt<unsigned>
316
llvm::DefMaxInstsToScan("available-load-scan-limit", cl::init(6), cl::Hidden,
317
  cl::desc("Use this to specify the default maximum number of instructions "
318
           "to scan backward from a given instruction, when searching for "
319
           "available loaded value"));
320
321
Value *llvm::FindAvailableLoadedValue(LoadInst *Load,
322
                                      BasicBlock *ScanBB,
323
                                      BasicBlock::iterator &ScanFrom,
324
                                      unsigned MaxInstsToScan,
325
                                      AliasAnalysis *AA, bool *IsLoad,
326
25.4M
                                      unsigned *NumScanedInst) {
327
25.4M
  // Don't CSE load that is volatile or anything stronger than unordered.
328
25.4M
  if (!Load->isUnordered())
329
61.8k
    return nullptr;
330
25.3M
331
25.3M
  return FindAvailablePtrLoadStore(
332
25.3M
      Load->getPointerOperand(), Load->getType(), Load->isAtomic(), ScanBB,
333
25.3M
      ScanFrom, MaxInstsToScan, AA, IsLoad, NumScanedInst);
334
25.3M
}
335
336
Value *llvm::FindAvailablePtrLoadStore(Value *Ptr, Type *AccessTy,
337
                                       bool AtLeastAtomic, BasicBlock *ScanBB,
338
                                       BasicBlock::iterator &ScanFrom,
339
                                       unsigned MaxInstsToScan,
340
                                       AliasAnalysis *AA, bool *IsLoadCSE,
341
25.9M
                                       unsigned *NumScanedInst) {
342
25.9M
  if (MaxInstsToScan == 0)
343
0
    MaxInstsToScan = ~0U;
344
25.9M
345
25.9M
  const DataLayout &DL = ScanBB->getModule()->getDataLayout();
346
25.9M
347
25.9M
  // Try to get the store size for the type.
348
25.9M
  uint64_t AccessSize = DL.getTypeStoreSize(AccessTy);
349
25.9M
350
25.9M
  Value *StrippedPtr = Ptr->stripPointerCasts();
351
25.9M
352
85.5M
  while (
ScanFrom != ScanBB->begin()85.5M
) {
353
68.9M
    // We must ignore debug info directives when counting (otherwise they
354
68.9M
    // would affect codegen).
355
68.9M
    Instruction *Inst = &*--ScanFrom;
356
68.9M
    if (isa<DbgInfoIntrinsic>(Inst))
357
81
      continue;
358
68.9M
359
68.9M
    // Restore ScanFrom to expected value in case next test succeeds
360
68.9M
    ScanFrom++;
361
68.9M
362
68.9M
    if (NumScanedInst)
363
1.90M
      ++(*NumScanedInst);
364
68.9M
365
68.9M
    // Don't scan huge blocks.
366
68.9M
    if (MaxInstsToScan-- == 0)
367
4.09M
      return nullptr;
368
64.8M
369
64.8M
    --ScanFrom;
370
64.8M
    // If this is a load of Ptr, the loaded value is available.
371
64.8M
    // (This is true even if the load is volatile or atomic, although
372
64.8M
    // those cases are unlikely.)
373
64.8M
    if (LoadInst *LI = dyn_cast<LoadInst>(Inst))
374
10.8M
      
if (10.8M
AreEquivalentAddressValues(
375
10.8M
              LI->getPointerOperand()->stripPointerCasts(), StrippedPtr) &&
376
10.8M
          
CastInst::isBitOrNoopPointerCastable(LI->getType(), AccessTy, DL)15.7k
) {
377
14.9k
378
14.9k
        // We can value forward from an atomic to a non-atomic, but not the
379
14.9k
        // other way around.
380
14.9k
        if (LI->isAtomic() < AtLeastAtomic)
381
0
          return nullptr;
382
14.9k
383
14.9k
        
if (14.9k
IsLoadCSE14.9k
)
384
14.9k
            *IsLoadCSE = true;
385
10.8M
        return LI;
386
10.8M
      }
387
64.8M
388
64.8M
    
if (StoreInst *64.8M
SI64.8M
= dyn_cast<StoreInst>(Inst)) {
389
4.10M
      Value *StorePtr = SI->getPointerOperand()->stripPointerCasts();
390
4.10M
      // If this is a store through Ptr, the value is available!
391
4.10M
      // (This is true even if the store is volatile or atomic, although
392
4.10M
      // those cases are unlikely.)
393
4.10M
      if (AreEquivalentAddressValues(StorePtr, StrippedPtr) &&
394
6.93k
          CastInst::isBitOrNoopPointerCastable(SI->getValueOperand()->getType(),
395
4.10M
                                               AccessTy, DL)) {
396
6.68k
397
6.68k
        // We can value forward from an atomic to a non-atomic, but not the
398
6.68k
        // other way around.
399
6.68k
        if (SI->isAtomic() < AtLeastAtomic)
400
0
          return nullptr;
401
6.68k
402
6.68k
        
if (6.68k
IsLoadCSE6.68k
)
403
6.68k
          *IsLoadCSE = false;
404
6.68k
        return SI->getOperand(0);
405
6.68k
      }
406
4.09M
407
4.09M
      // If both StrippedPtr and StorePtr reach all the way to an alloca or
408
4.09M
      // global and they are different, ignore the store. This is a trivial form
409
4.09M
      // of alias analysis that is important for reg2mem'd code.
410
4.09M
      
if (4.09M
(isa<AllocaInst>(StrippedPtr) || 4.09M
isa<GlobalVariable>(StrippedPtr)4.03M
) &&
411
830k
          
(isa<AllocaInst>(StorePtr) || 830k
isa<GlobalVariable>(StorePtr)810k
) &&
412
268k
          StrippedPtr != StorePtr)
413
268k
        continue;
414
3.82M
415
3.82M
      // If we have alias analysis and it says the store won't modify the loaded
416
3.82M
      // value, ignore the store.
417
3.82M
      
if (3.82M
AA && 3.82M
(AA->getModRefInfo(SI, StrippedPtr, AccessSize) & MRI_Mod) == 03.82M
)
418
2.27M
        continue;
419
1.55M
420
1.55M
      // Otherwise the store that may or may not alias the pointer, bail out.
421
1.55M
      ++ScanFrom;
422
1.55M
      return nullptr;
423
1.55M
    }
424
60.7M
425
60.7M
    // If this is some other instruction that may clobber Ptr, bail out.
426
60.7M
    
if (60.7M
Inst->mayWriteToMemory()60.7M
) {
427
4.10M
      // If alias analysis claims that it really won't modify the load,
428
4.10M
      // ignore it.
429
4.10M
      if (AA &&
430
4.10M
          (AA->getModRefInfo(Inst, StrippedPtr, AccessSize) & MRI_Mod) == 0)
431
446k
        continue;
432
3.66M
433
3.66M
      // May modify the pointer, bail out.
434
3.66M
      ++ScanFrom;
435
3.66M
      return nullptr;
436
3.66M
    }
437
68.9M
  }
438
25.9M
439
25.9M
  // Got to the start of the block, we didn't find it, but are done for this
440
25.9M
  // block.
441
16.6M
  return nullptr;
442
25.9M
}