Coverage Report

Created: 2017-10-03 07:32

/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/lib/Analysis/GlobalsModRef.cpp
Line
Count
Source (jump to first uncovered line)
1
//===- GlobalsModRef.cpp - Simple Mod/Ref Analysis for Globals ------------===//
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 simple pass provides alias and mod/ref information for global values
11
// that do not have their address taken, and keeps track of whether functions
12
// read or write memory (are "pure").  For this simple (but very common) case,
13
// we can provide pretty accurate and useful information.
14
//
15
//===----------------------------------------------------------------------===//
16
17
#include "llvm/Analysis/GlobalsModRef.h"
18
#include "llvm/ADT/SCCIterator.h"
19
#include "llvm/ADT/SmallPtrSet.h"
20
#include "llvm/ADT/Statistic.h"
21
#include "llvm/Analysis/MemoryBuiltins.h"
22
#include "llvm/Analysis/TargetLibraryInfo.h"
23
#include "llvm/Analysis/ValueTracking.h"
24
#include "llvm/IR/DerivedTypes.h"
25
#include "llvm/IR/InstIterator.h"
26
#include "llvm/IR/Instructions.h"
27
#include "llvm/IR/IntrinsicInst.h"
28
#include "llvm/IR/Module.h"
29
#include "llvm/Pass.h"
30
#include "llvm/Support/CommandLine.h"
31
using namespace llvm;
32
33
#define DEBUG_TYPE "globalsmodref-aa"
34
35
STATISTIC(NumNonAddrTakenGlobalVars,
36
          "Number of global vars without address taken");
37
STATISTIC(NumNonAddrTakenFunctions,"Number of functions without address taken");
38
STATISTIC(NumNoMemFunctions, "Number of functions that do not access memory");
39
STATISTIC(NumReadMemFunctions, "Number of functions that only read memory");
40
STATISTIC(NumIndirectGlobalVars, "Number of indirect global objects");
41
42
// An option to enable unsafe alias results from the GlobalsModRef analysis.
43
// When enabled, GlobalsModRef will provide no-alias results which in extremely
44
// rare cases may not be conservatively correct. In particular, in the face of
45
// transforms which cause assymetry between how effective GetUnderlyingObject
46
// is for two pointers, it may produce incorrect results.
47
//
48
// These unsafe results have been returned by GMR for many years without
49
// causing significant issues in the wild and so we provide a mechanism to
50
// re-enable them for users of LLVM that have a particular performance
51
// sensitivity and no known issues. The option also makes it easy to evaluate
52
// the performance impact of these results.
53
static cl::opt<bool> EnableUnsafeGlobalsModRefAliasResults(
54
    "enable-unsafe-globalsmodref-alias-results", cl::init(false), cl::Hidden);
55
56
/// The mod/ref information collected for a particular function.
57
///
58
/// We collect information about mod/ref behavior of a function here, both in
59
/// general and as pertains to specific globals. We only have this detailed
60
/// information when we know *something* useful about the behavior. If we
61
/// saturate to fully general mod/ref, we remove the info for the function.
62
class GlobalsAAResult::FunctionInfo {
63
  typedef SmallDenseMap<const GlobalValue *, ModRefInfo, 16> GlobalInfoMapType;
64
65
  /// Build a wrapper struct that has 8-byte alignment. All heap allocations
66
  /// should provide this much alignment at least, but this makes it clear we
67
  /// specifically rely on this amount of alignment.
68
  struct LLVM_ALIGNAS(8) AlignedMap {
69
38.8k
    AlignedMap() {}
70
2.26k
    AlignedMap(const AlignedMap &Arg) : Map(Arg.Map) {}
71
    GlobalInfoMapType Map;
72
  };
73
74
  /// Pointer traits for our aligned map.
75
  struct AlignedMapPointerTraits {
76
278k
    static inline void *getAsVoidPointer(AlignedMap *P) { return P; }
77
11.2M
    static inline AlignedMap *getFromVoidPointer(void *P) {
78
11.2M
      return (AlignedMap *)P;
79
11.2M
    }
80
    enum { NumLowBitsAvailable = 3 };
81
    static_assert(alignof(AlignedMap) >= (1 << NumLowBitsAvailable),
82
                  "AlignedMap insufficiently aligned to have enough low bits.");
83
  };
84
85
  /// The bit that flags that this function may read any global. This is
86
  /// chosen to mix together with ModRefInfo bits.
87
  enum { MayReadAnyGlobal = 4 };
88
89
  /// Checks to document the invariants of the bit packing here.
90
  static_assert((MayReadAnyGlobal & MRI_ModRef) == 0,
91
                "ModRef and the MayReadAnyGlobal flag bits overlap.");
92
  static_assert(((MayReadAnyGlobal | MRI_ModRef) >>
93
                 AlignedMapPointerTraits::NumLowBitsAvailable) == 0,
94
                "Insufficient low bits to store our flag and ModRef info.");
95
96
public:
97
614k
  FunctionInfo() : Info() {}
98
806k
  ~FunctionInfo() {
99
806k
    delete Info.getPointer();
100
806k
  }
101
  // Spell out the copy ond move constructors and assignment operators to get
102
  // deep copy semantics and correct move semantics in the face of the
103
  // pointer-int pair.
104
  FunctionInfo(const FunctionInfo &Arg)
105
146k
      : Info(nullptr, Arg.Info.getInt()) {
106
146k
    if (const auto *ArgPtr = Arg.Info.getPointer())
107
2.26k
      Info.setPointer(new AlignedMap(*ArgPtr));
108
146k
  }
109
  FunctionInfo(FunctionInfo &&Arg)
110
45.2k
      : Info(Arg.Info.getPointer(), Arg.Info.getInt()) {
111
45.2k
    Arg.Info.setPointerAndInt(nullptr, 0);
112
45.2k
  }
113
28
  FunctionInfo &operator=(const FunctionInfo &RHS) {
114
28
    delete Info.getPointer();
115
28
    Info.setPointerAndInt(nullptr, RHS.Info.getInt());
116
28
    if (const auto *RHSPtr = RHS.Info.getPointer())
117
0
      Info.setPointer(new AlignedMap(*RHSPtr));
118
28
    return *this;
119
28
  }
120
0
  FunctionInfo &operator=(FunctionInfo &&RHS) {
121
0
    delete Info.getPointer();
122
0
    Info.setPointerAndInt(RHS.Info.getPointer(), RHS.Info.getInt());
123
0
    RHS.Info.setPointerAndInt(nullptr, 0);
124
0
    return *this;
125
0
  }
126
127
  /// Returns the \c ModRefInfo info for this function.
128
12.6M
  ModRefInfo getModRefInfo() const {
129
12.6M
    return ModRefInfo(Info.getInt() & MRI_ModRef);
130
12.6M
  }
131
132
  /// Adds new \c ModRefInfo for this function to its state.
133
608k
  void addModRefInfo(ModRefInfo NewMRI) {
134
608k
    Info.setInt(Info.getInt() | NewMRI);
135
608k
  }
136
137
  /// Returns whether this function may read any global variable, and we don't
138
  /// know which global.
139
139k
  bool mayReadAnyGlobal() const { return Info.getInt() & MayReadAnyGlobal; }
140
141
  /// Sets this function as potentially reading from any global.
142
32.8k
  void setMayReadAnyGlobal() { Info.setInt(Info.getInt() | MayReadAnyGlobal); }
143
144
  /// Returns the \c ModRefInfo info for this function w.r.t. a particular
145
  /// global, which may be more precise than the general information above.
146
38.4k
  ModRefInfo getModRefInfoForGlobal(const GlobalValue &GV) const {
147
38.4k
    ModRefInfo GlobalMRI = mayReadAnyGlobal() ? 
MRI_Ref8.67k
:
MRI_NoModRef29.7k
;
148
38.4k
    if (AlignedMap *
P38.4k
= Info.getPointer()) {
149
2.19k
      auto I = P->Map.find(&GV);
150
2.19k
      if (I != P->Map.end())
151
1.03k
        GlobalMRI = ModRefInfo(GlobalMRI | I->second);
152
2.19k
    }
153
38.4k
    return GlobalMRI;
154
38.4k
  }
155
156
  /// Add mod/ref info from another function into ours, saturating towards
157
  /// MRI_ModRef.
158
101k
  void addFunctionInfo(const FunctionInfo &FI) {
159
101k
    addModRefInfo(FI.getModRefInfo());
160
101k
161
101k
    if (FI.mayReadAnyGlobal())
162
13.1k
      setMayReadAnyGlobal();
163
101k
164
101k
    if (AlignedMap *P = FI.Info.getPointer())
165
1.39k
      for (const auto &G : P->Map)
166
2.91k
        addModRefInfoForGlobal(*G.first, G.second);
167
101k
  }
168
169
67.4k
  void addModRefInfoForGlobal(const GlobalValue &GV, ModRefInfo NewMRI) {
170
67.4k
    AlignedMap *P = Info.getPointer();
171
67.4k
    if (
!P67.4k
) {
172
38.8k
      P = new AlignedMap();
173
38.8k
      Info.setPointer(P);
174
38.8k
    }
175
67.4k
    auto &GlobalMRI = P->Map[&GV];
176
67.4k
    GlobalMRI = ModRefInfo(GlobalMRI | NewMRI);
177
67.4k
  }
178
179
  /// Clear a global's ModRef info. Should be used when a global is being
180
  /// deleted.
181
10.0M
  void eraseModRefInfoForGlobal(const GlobalValue &GV) {
182
10.0M
    if (AlignedMap *P = Info.getPointer())
183
57.4k
      P->Map.erase(&GV);
184
10.0M
  }
185
186
private:
187
  /// All of the information is encoded into a single pointer, with a three bit
188
  /// integer in the low three bits. The high bit provides a flag for when this
189
  /// function may read any global. The low two bits are the ModRefInfo. And
190
  /// the pointer, when non-null, points to a map from GlobalValue to
191
  /// ModRefInfo specific to that GlobalValue.
192
  PointerIntPair<AlignedMap *, 3, unsigned, AlignedMapPointerTraits> Info;
193
};
194
195
30.6k
void GlobalsAAResult::DeletionCallbackHandle::deleted() {
196
30.6k
  Value *V = getValPtr();
197
30.6k
  if (auto *F = dyn_cast<Function>(V))
198
23.0k
    GAR->FunctionInfos.erase(F);
199
30.6k
200
30.6k
  if (GlobalValue *
GV30.6k
= dyn_cast<GlobalValue>(V)) {
201
30.6k
    if (
GAR->NonAddressTakenGlobals.erase(GV)30.6k
) {
202
30.6k
      // This global might be an indirect global.  If so, remove it and
203
30.6k
      // remove any AllocRelatedValues for it.
204
30.6k
      if (
GAR->IndirectGlobals.erase(GV)30.6k
) {
205
0
        // Remove any entries in AllocsForIndirectGlobals for this global.
206
0
        for (auto I = GAR->AllocsForIndirectGlobals.begin(),
207
0
                  E = GAR->AllocsForIndirectGlobals.end();
208
0
             
I != E0
;
++I0
)
209
0
          
if (0
I->second == GV0
)
210
0
            GAR->AllocsForIndirectGlobals.erase(I);
211
0
      }
212
30.6k
213
30.6k
      // Scan the function info we have collected and remove this global
214
30.6k
      // from all of them.
215
30.6k
      for (auto &FIPair : GAR->FunctionInfos)
216
10.0M
        FIPair.second.eraseModRefInfoForGlobal(*GV);
217
30.6k
    }
218
30.6k
  }
219
30.6k
220
30.6k
  // If this is an allocation related to an indirect global, remove it.
221
30.6k
  GAR->AllocsForIndirectGlobals.erase(V);
222
30.6k
223
30.6k
  // And clear out the handle.
224
30.6k
  setValPtr(nullptr);
225
30.6k
  GAR->Handles.erase(I);
226
30.6k
  // This object is now destroyed!
227
30.6k
}
228
229
21.7M
FunctionModRefBehavior GlobalsAAResult::getModRefBehavior(const Function *F) {
230
21.7M
  FunctionModRefBehavior Min = FMRB_UnknownModRefBehavior;
231
21.7M
232
21.7M
  if (FunctionInfo *
FI21.7M
= getFunctionInfo(F)) {
233
2.91M
    if (FI->getModRefInfo() == MRI_NoModRef)
234
16.2k
      Min = FMRB_DoesNotAccessMemory;
235
2.89M
    else 
if (2.89M
(FI->getModRefInfo() & MRI_Mod) == 02.89M
)
236
547k
      Min = FMRB_OnlyReadsMemory;
237
2.91M
  }
238
21.7M
239
21.7M
  return FunctionModRefBehavior(AAResultBase::getModRefBehavior(F) & Min);
240
21.7M
}
241
242
FunctionModRefBehavior
243
22.0M
GlobalsAAResult::getModRefBehavior(ImmutableCallSite CS) {
244
22.0M
  FunctionModRefBehavior Min = FMRB_UnknownModRefBehavior;
245
22.0M
246
22.0M
  if (!CS.hasOperandBundles())
247
22.0M
    
if (const Function *22.0M
F22.0M
= CS.getCalledFunction())
248
20.9M
      
if (FunctionInfo *20.9M
FI20.9M
= getFunctionInfo(F)) {
249
2.84M
        if (FI->getModRefInfo() == MRI_NoModRef)
250
6
          Min = FMRB_DoesNotAccessMemory;
251
2.84M
        else 
if (2.84M
(FI->getModRefInfo() & MRI_Mod) == 02.84M
)
252
527k
          Min = FMRB_OnlyReadsMemory;
253
22.0M
      }
254
22.0M
255
22.0M
  return FunctionModRefBehavior(AAResultBase::getModRefBehavior(CS) & Min);
256
22.0M
}
257
258
/// Returns the function info for the function, or null if we don't have
259
/// anything useful to say about it.
260
GlobalsAAResult::FunctionInfo *
261
43.0M
GlobalsAAResult::getFunctionInfo(const Function *F) {
262
43.0M
  auto I = FunctionInfos.find(F);
263
43.0M
  if (I != FunctionInfos.end())
264
5.89M
    return &I->second;
265
37.1M
  return nullptr;
266
37.1M
}
267
268
/// AnalyzeGlobals - Scan through the users of all of the internal
269
/// GlobalValue's in the program.  If none of them have their "address taken"
270
/// (really, their address passed to something nontrivial), record this fact,
271
/// and record the functions that they are used directly in.
272
34.8k
void GlobalsAAResult::AnalyzeGlobals(Module &M) {
273
34.8k
  SmallPtrSet<Function *, 32> TrackedFunctions;
274
34.8k
  for (Function &F : M)
275
1.40M
    
if (1.40M
F.hasLocalLinkage()1.40M
)
276
34.0k
      
if (34.0k
!AnalyzeUsesOfPointer(&F)34.0k
) {
277
28.1k
        // Remember that we are tracking this global.
278
28.1k
        NonAddressTakenGlobals.insert(&F);
279
28.1k
        TrackedFunctions.insert(&F);
280
28.1k
        Handles.emplace_front(*this, &F);
281
28.1k
        Handles.front().I = Handles.begin();
282
28.1k
        ++NumNonAddrTakenFunctions;
283
28.1k
      }
284
34.8k
285
34.8k
  SmallPtrSet<Function *, 16> Readers, Writers;
286
34.8k
  for (GlobalVariable &GV : M.globals())
287
1.53M
    
if (1.53M
GV.hasLocalLinkage()1.53M
) {
288
1.28M
      if (!AnalyzeUsesOfPointer(&GV, &Readers,
289
1.28M
                                GV.isConstant() ? 
nullptr1.23M
:
&Writers49.5k
)) {
290
34.3k
        // Remember that we are tracking this global, and the mod/ref fns
291
34.3k
        NonAddressTakenGlobals.insert(&GV);
292
34.3k
        Handles.emplace_front(*this, &GV);
293
34.3k
        Handles.front().I = Handles.begin();
294
34.3k
295
34.2k
        for (Function *Reader : Readers) {
296
34.2k
          if (
TrackedFunctions.insert(Reader).second34.2k
) {
297
22.8k
            Handles.emplace_front(*this, Reader);
298
22.8k
            Handles.front().I = Handles.begin();
299
22.8k
          }
300
34.2k
          FunctionInfos[Reader].addModRefInfoForGlobal(GV, MRI_Ref);
301
34.2k
        }
302
34.3k
303
34.3k
        if (!GV.isConstant()) // No need to keep track of writers to constants
304
13.9k
          
for (Function *Writer : Writers) 13.9k
{
305
30.2k
            if (
TrackedFunctions.insert(Writer).second30.2k
) {
306
14.1k
              Handles.emplace_front(*this, Writer);
307
14.1k
              Handles.front().I = Handles.begin();
308
14.1k
            }
309
13.9k
            FunctionInfos[Writer].addModRefInfoForGlobal(GV, MRI_Mod);
310
13.9k
          }
311
34.3k
        ++NumNonAddrTakenGlobalVars;
312
34.3k
313
34.3k
        // If this global holds a pointer type, see if it is an indirect global.
314
34.3k
        if (GV.getValueType()->isPointerTy() &&
315
3.92k
            AnalyzeIndirectGlobalMemory(&GV))
316
3
          ++NumIndirectGlobalVars;
317
34.3k
      }
318
1.53M
      Readers.clear();
319
1.53M
      Writers.clear();
320
1.53M
    }
321
34.8k
}
322
323
/// AnalyzeUsesOfPointer - Look at all of the users of the specified pointer.
324
/// If this is used by anything complex (i.e., the address escapes), return
325
/// true.  Also, while we are at it, keep track of those functions that read and
326
/// write to the value.
327
///
328
/// If OkayStoreDest is non-null, stores into this global are allowed.
329
bool GlobalsAAResult::AnalyzeUsesOfPointer(Value *V,
330
                                           SmallPtrSetImpl<Function *> *Readers,
331
                                           SmallPtrSetImpl<Function *> *Writers,
332
2.61M
                                           GlobalValue *OkayStoreDest) {
333
2.61M
  if (!V->getType()->isPointerTy())
334
0
    return true;
335
2.61M
336
2.61M
  
for (Use &U : V->uses()) 2.61M
{
337
2.88M
    User *I = U.getUser();
338
2.88M
    if (LoadInst *
LI2.88M
= dyn_cast<LoadInst>(I)) {
339
87.4k
      if (Readers)
340
83.9k
        Readers->insert(LI->getParent()->getParent());
341
2.88M
    } else 
if (StoreInst *2.79M
SI2.79M
= dyn_cast<StoreInst>(I)) {
342
80.6k
      if (
V == SI->getOperand(1)80.6k
) {
343
77.4k
        if (Writers)
344
76.4k
          Writers->insert(SI->getParent()->getParent());
345
80.6k
      } else 
if (3.23k
SI->getOperand(1) != OkayStoreDest3.23k
) {
346
3.22k
        return true; // Storing the pointer
347
3.22k
      }
348
2.71M
    } else 
if (2.71M
Operator::getOpcode(I) == Instruction::GetElementPtr2.71M
) {
349
1.26M
      if (AnalyzeUsesOfPointer(I, Readers, Writers))
350
1.19M
        return true;
351
1.45M
    } else 
if (1.45M
Operator::getOpcode(I) == Instruction::BitCast1.45M
) {
352
32.1k
      if (AnalyzeUsesOfPointer(I, Readers, Writers, OkayStoreDest))
353
27.3k
        return true;
354
1.41M
    } else 
if (auto 1.41M
CS1.41M
= CallSite(I)) {
355
1.22M
      // Make sure that this is just the function being called, not that it is
356
1.22M
      // passing into the function.
357
1.22M
      if (
CS.isDataOperand(&U)1.22M
) {
358
1.05M
        // Detect calls to free.
359
1.05M
        if (
CS.isArgOperand(&U) && 1.05M
isFreeCall(I, &TLI)1.05M
) {
360
66
          if (Writers)
361
0
            Writers->insert(CS->getParent()->getParent());
362
1.05M
        } else {
363
1.05M
          return true; // Argument of an unknown call.
364
1.05M
        }
365
1.41M
      }
366
196k
    } else 
if (ICmpInst *196k
ICI196k
= dyn_cast<ICmpInst>(I)) {
367
270
      if (!isa<ConstantPointerNull>(ICI->getOperand(1)))
368
82
        return true; // Allow comparison against null.
369
195k
    } else 
if (Constant *195k
C195k
= dyn_cast<Constant>(I)) {
370
133k
      // Ignore constants which don't have any live uses.
371
133k
      if (
isa<GlobalValue>(C) || 133k
C->isConstantUsed()131k
)
372
133k
        return true;
373
62.8k
    } else {
374
62.8k
      return true;
375
62.8k
    }
376
137k
  }
377
137k
378
137k
  return false;
379
137k
}
380
381
/// AnalyzeIndirectGlobalMemory - We found an non-address-taken global variable
382
/// which holds a pointer type.  See if the global always points to non-aliased
383
/// heap memory: that is, all initializers of the globals are allocations, and
384
/// those allocations have no use other than initialization of the global.
385
/// Further, all loads out of GV must directly use the memory, not store the
386
/// pointer somewhere.  If this is true, we consider the memory pointed to by
387
/// GV to be owned by GV and can disambiguate other pointers from it.
388
3.92k
bool GlobalsAAResult::AnalyzeIndirectGlobalMemory(GlobalVariable *GV) {
389
3.92k
  // Keep track of values related to the allocation of the memory, f.e. the
390
3.92k
  // value produced by the malloc call and any casts.
391
3.92k
  std::vector<Value *> AllocRelatedValues;
392
3.92k
393
3.92k
  // If the initializer is a valid pointer, bail.
394
3.92k
  if (Constant *C = GV->getInitializer())
395
3.92k
    
if (3.92k
!C->isNullValue()3.92k
)
396
62
      return false;
397
3.86k
    
398
3.86k
  // Walk the user list of the global.  If we find anything other than a direct
399
3.86k
  // load or store, bail out.
400
3.86k
  
for (User *U : GV->users()) 3.86k
{
401
7.22k
    if (LoadInst *
LI7.22k
= dyn_cast<LoadInst>(U)) {
402
5.05k
      // The pointer loaded from the global can only be used in simple ways:
403
5.05k
      // we allow addressing of it and loading storing to it.  We do *not* allow
404
5.05k
      // storing the loaded pointer somewhere else or passing to a function.
405
5.05k
      if (AnalyzeUsesOfPointer(LI))
406
1.84k
        return false; // Loaded pointer escapes.
407
7.22k
      // TODO: Could try some IP mod/ref of the loaded pointer.
408
2.17k
    } else 
if (StoreInst *2.17k
SI2.17k
= dyn_cast<StoreInst>(U)) {
409
1.24k
      // Storing the global itself.
410
1.24k
      if (SI->getOperand(0) == GV)
411
0
        return false;
412
1.24k
413
1.24k
      // If storing the null pointer, ignore it.
414
1.24k
      
if (1.24k
isa<ConstantPointerNull>(SI->getOperand(0))1.24k
)
415
151
        continue;
416
1.09k
417
1.09k
      // Check the value being stored.
418
1.09k
      Value *Ptr = GetUnderlyingObject(SI->getOperand(0),
419
1.09k
                                       GV->getParent()->getDataLayout());
420
1.09k
421
1.09k
      if (!isAllocLikeFn(Ptr, &TLI))
422
1.05k
        return false; // Too hard to analyze.
423
36
424
36
      // Analyze all uses of the allocation.  If any of them are used in a
425
36
      // non-simple way (e.g. stored to another global) bail out.
426
36
      
if (36
AnalyzeUsesOfPointer(Ptr, /*Readers*/ nullptr, /*Writers*/ nullptr,
427
36
                               GV))
428
24
        return false; // Loaded pointer escapes.
429
12
430
12
      // Remember that this allocation is related to the indirect global.
431
12
      AllocRelatedValues.push_back(Ptr);
432
2.17k
    } else {
433
934
      // Something complex, bail out.
434
934
      return false;
435
934
    }
436
3
  }
437
3
438
3
  // Okay, this is an indirect global.  Remember all of the allocations for
439
3
  // this global in AllocsForIndirectGlobals.
440
5
  
while (3
!AllocRelatedValues.empty()5
) {
441
2
    AllocsForIndirectGlobals[AllocRelatedValues.back()] = GV;
442
2
    Handles.emplace_front(*this, AllocRelatedValues.back());
443
2
    Handles.front().I = Handles.begin();
444
2
    AllocRelatedValues.pop_back();
445
2
  }
446
3.92k
  IndirectGlobals.insert(GV);
447
3.92k
  Handles.emplace_front(*this, GV);
448
3.92k
  Handles.front().I = Handles.begin();
449
3.92k
  return true;
450
3.92k
}
451
452
34.8k
void GlobalsAAResult::CollectSCCMembership(CallGraph &CG) {  
453
34.8k
  // We do a bottom-up SCC traversal of the call graph.  In other words, we
454
34.8k
  // visit all callees before callers (leaf-first).
455
34.8k
  unsigned SCCID = 0;
456
1.49M
  for (scc_iterator<CallGraph *> I = scc_begin(&CG); 
!I.isAtEnd()1.49M
;
++I1.46M
) {
457
1.46M
    const std::vector<CallGraphNode *> &SCC = *I;
458
1.46M
    assert(!SCC.empty() && "SCC with no functions?");
459
1.46M
460
1.46M
    for (auto *CGN : SCC)
461
1.46M
      
if (Function *1.46M
F1.46M
= CGN->getFunction())
462
1.40M
        FunctionToSCCMap[F] = SCCID;
463
1.46M
    ++SCCID;
464
1.46M
  }
465
34.8k
}
466
467
/// AnalyzeCallGraph - At this point, we know the functions where globals are
468
/// immediately stored to and read from.  Propagate this information up the call
469
/// graph to all callers and compute the mod/ref info for all memory for each
470
/// function.
471
34.8k
void GlobalsAAResult::AnalyzeCallGraph(CallGraph &CG, Module &M) {
472
34.8k
  // We do a bottom-up SCC traversal of the call graph.  In other words, we
473
34.8k
  // visit all callees before callers (leaf-first).
474
1.49M
  for (scc_iterator<CallGraph *> I = scc_begin(&CG); 
!I.isAtEnd()1.49M
;
++I1.46M
) {
475
1.46M
    const std::vector<CallGraphNode *> &SCC = *I;
476
1.46M
    assert(!SCC.empty() && "SCC with no functions?");
477
1.46M
478
1.46M
    Function *F = SCC[0]->getFunction();
479
1.46M
480
1.46M
    if (
!F || 1.46M
!F->isDefinitionExact()1.40M
) {
481
866k
      // Calls externally or not exact - can't say anything useful. Remove any
482
866k
      // existing function records (may have been created when scanning
483
866k
      // globals).
484
866k
      for (auto *Node : SCC)
485
866k
        FunctionInfos.erase(Node->getFunction());
486
866k
      continue;
487
866k
    }
488
597k
489
597k
    FunctionInfo &FI = FunctionInfos[F];
490
597k
    bool KnowNothing = false;
491
597k
492
597k
    // Collect the mod/ref properties due to called functions.  We only compute
493
597k
    // one mod-ref set.
494
1.19M
    for (unsigned i = 0, e = SCC.size(); 
i != e && 1.19M
!KnowNothing598k
;
++i597k
) {
495
597k
      if (
!F597k
) {
496
0
        KnowNothing = true;
497
0
        break;
498
0
      }
499
597k
500
597k
      
if (597k
F->isDeclaration() || 597k
F->hasFnAttribute(Attribute::OptimizeNone)175k
) {
501
422k
        // Try to get mod/ref behaviour from function attributes.
502
422k
        if (
F->doesNotAccessMemory()422k
) {
503
18.9k
          // Can't do better than that!
504
422k
        } else 
if (403k
F->onlyReadsMemory()403k
) {
505
27.2k
          FI.addModRefInfo(MRI_Ref);
506
27.2k
          if (
!F->isIntrinsic() && 27.2k
!F->onlyAccessesArgMemory()26.4k
)
507
27.2k
            // This function might call back into the module and read a global -
508
27.2k
            // consider every global as possibly being read by this function.
509
19.7k
            FI.setMayReadAnyGlobal();
510
403k
        } else {
511
376k
          FI.addModRefInfo(MRI_ModRef);
512
376k
          // Can't say anything useful unless it's an intrinsic - they don't
513
376k
          // read or write global variables of the kind considered here.
514
376k
          KnowNothing = !F->isIntrinsic();
515
376k
        }
516
422k
        continue;
517
422k
      }
518
175k
519
175k
      for (CallGraphNode::iterator CI = SCC[i]->begin(), E = SCC[i]->end();
520
390k
           
CI != E && 390k
!KnowNothing297k
;
++CI215k
)
521
215k
        
if (Function *215k
Callee215k
= CI->second->getFunction()) {
522
208k
          if (FunctionInfo *
CalleeFI208k
= getFunctionInfo(Callee)) {
523
101k
            // Propagate function effect up.
524
101k
            FI.addFunctionInfo(*CalleeFI);
525
208k
          } else {
526
107k
            // Can't say anything about it.  However, if it is inside our SCC,
527
107k
            // then nothing needs to be done.
528
107k
            CallGraphNode *CalleeNode = CG[Callee];
529
107k
            if (!is_contained(SCC, CalleeNode))
530
107k
              KnowNothing = true;
531
107k
          }
532
215k
        } else {
533
6.51k
          KnowNothing = true;
534
6.51k
        }
535
597k
    }
536
597k
537
597k
    // If we can't say anything useful about this SCC, remove all SCC functions
538
597k
    // from the FunctionInfos map.
539
597k
    if (
KnowNothing597k
) {
540
451k
      for (auto *Node : SCC)
541
451k
        FunctionInfos.erase(Node->getFunction());
542
451k
      continue;
543
451k
    }
544
146k
545
146k
    // Scan the function bodies for explicit loads or stores.
546
146k
    
for (auto *Node : SCC) 146k
{
547
146k
      if (FI.getModRefInfo() == MRI_ModRef)
548
42.3k
        break; // The mod/ref lattice saturates here.
549
104k
550
104k
      // Don't prove any properties based on the implementation of an optnone
551
104k
      // function. Function attributes were already used as a best approximation
552
104k
      // above.
553
104k
      
if (104k
Node->getFunction()->hasFnAttribute(Attribute::OptimizeNone)104k
)
554
2
        continue;
555
104k
556
104k
      
for (Instruction &I : instructions(Node->getFunction())) 104k
{
557
647k
        if (FI.getModRefInfo() == MRI_ModRef)
558
17.2k
          break; // The mod/ref lattice saturates here.
559
630k
560
630k
        // We handle calls specially because the graph-relevant aspects are
561
630k
        // handled above.
562
630k
        
if (auto 630k
CS630k
= CallSite(&I)) {
563
16.6k
          if (
isAllocationFn(&I, &TLI) || 16.6k
isFreeCall(&I, &TLI)16.6k
) {
564
0
            // FIXME: It is completely unclear why this is necessary and not
565
0
            // handled by the above graph code.
566
0
            FI.addModRefInfo(MRI_ModRef);
567
16.6k
          } else 
if (Function *16.6k
Callee16.6k
= CS.getCalledFunction()) {
568
16.6k
            // The callgraph doesn't include intrinsic calls.
569
16.6k
            if (
Callee->isIntrinsic()16.6k
) {
570
6.50k
              FunctionModRefBehavior Behaviour =
571
6.50k
                  AAResultBase::getModRefBehavior(Callee);
572
6.50k
              FI.addModRefInfo(ModRefInfo(Behaviour & MRI_ModRef));
573
6.50k
            }
574
16.6k
          }
575
16.6k
          continue;
576
16.6k
        }
577
613k
578
613k
        // All non-call instructions we use the primary predicates for whether
579
613k
        // thay read or write memory.
580
613k
        
if (613k
I.mayReadFromMemory()613k
)
581
68.6k
          FI.addModRefInfo(MRI_Ref);
582
613k
        if (I.mayWriteToMemory())
583
28.0k
          FI.addModRefInfo(MRI_Mod);
584
647k
      }
585
146k
    }
586
146k
587
146k
    if ((FI.getModRefInfo() & MRI_Mod) == 0)
588
82.8k
      ++NumReadMemFunctions;
589
146k
    if (FI.getModRefInfo() == MRI_NoModRef)
590
46.4k
      ++NumNoMemFunctions;
591
146k
592
146k
    // Finally, now that we know the full effect on this SCC, clone the
593
146k
    // information to each function in the SCC.
594
146k
    // FI is a reference into FunctionInfos, so copy it now so that it doesn't
595
146k
    // get invalidated if DenseMap decides to re-hash.
596
146k
    FunctionInfo CachedFI = FI;
597
146k
    for (unsigned i = 1, e = SCC.size(); 
i != e146k
;
++i28
)
598
28
      FunctionInfos[SCC[i]->getFunction()] = CachedFI;
599
1.46M
  }
600
34.8k
}
601
602
// GV is a non-escaping global. V is a pointer address that has been loaded from.
603
// If we can prove that V must escape, we can conclude that a load from V cannot
604
// alias GV.
605
static bool isNonEscapingGlobalNoAliasWithLoad(const GlobalValue *GV,
606
                                               const Value *V,
607
                                               int &Depth,
608
452k
                                               const DataLayout &DL) {
609
452k
  SmallPtrSet<const Value *, 8> Visited;
610
452k
  SmallVector<const Value *, 8> Inputs;
611
452k
  Visited.insert(V);
612
452k
  Inputs.push_back(V);
613
741k
  do {
614
741k
    const Value *Input = Inputs.pop_back_val();
615
741k
    
616
741k
    if (
isa<GlobalValue>(Input) || 741k
isa<Argument>(Input)439k
||
isa<CallInst>(Input)354k
||
617
345k
        isa<InvokeInst>(Input))
618
741k
      // Arguments to functions or returns from functions are inherently
619
741k
      // escaping, so we can immediately classify those as not aliasing any
620
741k
      // non-addr-taken globals.
621
741k
      //
622
741k
      // (Transitive) loads from a global are also safe - if this aliased
623
741k
      // another global, its address would escape, so no alias.
624
395k
      continue;
625
345k
626
345k
    // Recurse through a limited number of selects, loads and PHIs. This is an
627
345k
    // arbitrary depth of 4, lower numbers could be used to fix compile time
628
345k
    // issues if needed, but this is generally expected to be only be important
629
345k
    // for small depths.
630
345k
    
if (345k
++Depth > 4345k
)
631
54.7k
      return false;
632
291k
633
291k
    
if (auto *291k
LI291k
= dyn_cast<LoadInst>(Input)) {
634
206k
      Inputs.push_back(GetUnderlyingObject(LI->getPointerOperand(), DL));
635
206k
      continue;
636
206k
    }  
637
85.0k
    
if (auto *85.0k
SI85.0k
= dyn_cast<SelectInst>(Input)) {
638
638
      const Value *LHS = GetUnderlyingObject(SI->getTrueValue(), DL);
639
638
      const Value *RHS = GetUnderlyingObject(SI->getFalseValue(), DL);
640
638
      if (Visited.insert(LHS).second)
641
638
        Inputs.push_back(LHS);
642
638
      if (Visited.insert(RHS).second)
643
402
        Inputs.push_back(RHS);
644
638
      continue;
645
638
    }
646
84.4k
    
if (auto *84.4k
PN84.4k
= dyn_cast<PHINode>(Input)) {
647
188k
      for (const Value *Op : PN->incoming_values()) {
648
188k
        Op = GetUnderlyingObject(Op, DL);
649
188k
        if (Visited.insert(Op).second)
650
110k
          Inputs.push_back(Op);
651
188k
      }
652
71.7k
      continue;
653
71.7k
    }
654
12.6k
    
655
12.6k
    return false;
656
673k
  } while (!Inputs.empty());
657
452k
658
452k
  // All inputs were known to be no-alias.
659
385k
  return true;
660
452k
}
661
662
// There are particular cases where we can conclude no-alias between
663
// a non-addr-taken global and some other underlying object. Specifically,
664
// a non-addr-taken global is known to not be escaped from any function. It is
665
// also incorrect for a transformation to introduce an escape of a global in
666
// a way that is observable when it was not there previously. One function
667
// being transformed to introduce an escape which could possibly be observed
668
// (via loading from a global or the return value for example) within another
669
// function is never safe. If the observation is made through non-atomic
670
// operations on different threads, it is a data-race and UB. If the
671
// observation is well defined, by being observed the transformation would have
672
// changed program behavior by introducing the observed escape, making it an
673
// invalid transform.
674
//
675
// This property does require that transformations which *temporarily* escape
676
// a global that was not previously escaped, prior to restoring it, cannot rely
677
// on the results of GMR::alias. This seems a reasonable restriction, although
678
// currently there is no way to enforce it. There is also no realistic
679
// optimization pass that would make this mistake. The closest example is
680
// a transformation pass which does reg2mem of SSA values but stores them into
681
// global variables temporarily before restoring the global variable's value.
682
// This could be useful to expose "benign" races for example. However, it seems
683
// reasonable to require that a pass which introduces escapes of global
684
// variables in this way to either not trust AA results while the escape is
685
// active, or to be forced to operate as a module pass that cannot co-exist
686
// with an alias analysis such as GMR.
687
bool GlobalsAAResult::isNonEscapingGlobalNoAlias(const GlobalValue *GV,
688
908k
                                                 const Value *V) {
689
908k
  // In order to know that the underlying object cannot alias the
690
908k
  // non-addr-taken global, we must know that it would have to be an escape.
691
908k
  // Thus if the underlying object is a function argument, a load from
692
908k
  // a global, or the return of a function, it cannot alias. We can also
693
908k
  // recurse through PHI nodes and select nodes provided all of their inputs
694
908k
  // resolve to one of these known-escaping roots.
695
908k
  SmallPtrSet<const Value *, 8> Visited;
696
908k
  SmallVector<const Value *, 8> Inputs;
697
908k
  Visited.insert(V);
698
908k
  Inputs.push_back(V);
699
908k
  int Depth = 0;
700
1.40M
  do {
701
1.40M
    const Value *Input = Inputs.pop_back_val();
702
1.40M
703
1.40M
    if (auto *
InputGV1.40M
= dyn_cast<GlobalValue>(Input)) {
704
10.3k
      // If one input is the very global we're querying against, then we can't
705
10.3k
      // conclude no-alias.
706
10.3k
      if (InputGV == GV)
707
200
        return false;
708
10.1k
709
10.1k
      // Distinct GlobalVariables never alias, unless overriden or zero-sized.
710
10.1k
      // FIXME: The condition can be refined, but be conservative for now.
711
10.1k
      auto *GVar = dyn_cast<GlobalVariable>(GV);
712
10.1k
      auto *InputGVar = dyn_cast<GlobalVariable>(InputGV);
713
10.1k
      if (
GVar && 10.1k
InputGVar10.1k
&&
714
10.1k
          
!GVar->isDeclaration()10.1k
&&
!InputGVar->isDeclaration()10.1k
&&
715
10.1k
          
!GVar->isInterposable()10.0k
&&
!InputGVar->isInterposable()10.0k
) {
716
9.82k
        Type *GVType = GVar->getInitializer()->getType();
717
9.82k
        Type *InputGVType = InputGVar->getInitializer()->getType();
718
9.82k
        if (
GVType->isSized() && 9.82k
InputGVType->isSized()9.82k
&&
719
9.82k
            (DL.getTypeAllocSize(GVType) > 0) &&
720
9.82k
            (DL.getTypeAllocSize(InputGVType) > 0))
721
9.82k
          continue;
722
344
      }
723
344
724
344
      // Conservatively return false, even though we could be smarter
725
344
      // (e.g. look through GlobalAliases).
726
344
      return false;
727
344
    }
728
1.39M
729
1.39M
    
if (1.39M
isa<Argument>(Input) || 1.39M
isa<CallInst>(Input)1.23M
||
730
1.39M
        
isa<InvokeInst>(Input)1.19M
) {
731
200k
      // Arguments to functions or returns from functions are inherently
732
200k
      // escaping, so we can immediately classify those as not aliasing any
733
200k
      // non-addr-taken globals.
734
200k
      continue;
735
200k
    }
736
1.19M
    
737
1.19M
    // Recurse through a limited number of selects, loads and PHIs. This is an
738
1.19M
    // arbitrary depth of 4, lower numbers could be used to fix compile time
739
1.19M
    // issues if needed, but this is generally expected to be only be important
740
1.19M
    // for small depths.
741
1.19M
    
if (1.19M
++Depth > 41.19M
)
742
28.0k
      return false;
743
1.16M
744
1.16M
    
if (auto *1.16M
LI1.16M
= dyn_cast<LoadInst>(Input)) {
745
452k
      // A pointer loaded from a global would have been captured, and we know
746
452k
      // that the global is non-escaping, so no alias.
747
452k
      const Value *Ptr = GetUnderlyingObject(LI->getPointerOperand(), DL);
748
452k
      if (isNonEscapingGlobalNoAliasWithLoad(GV, Ptr, Depth, DL))
749
452k
        // The load does not alias with GV.
750
385k
        continue;
751
67.3k
      // Otherwise, a load could come from anywhere, so bail.
752
67.3k
      return false;
753
67.3k
    }
754
709k
    
if (auto *709k
SI709k
= dyn_cast<SelectInst>(Input)) {
755
3.94k
      const Value *LHS = GetUnderlyingObject(SI->getTrueValue(), DL);
756
3.94k
      const Value *RHS = GetUnderlyingObject(SI->getFalseValue(), DL);
757
3.94k
      if (Visited.insert(LHS).second)
758
3.21k
        Inputs.push_back(LHS);
759
3.94k
      if (Visited.insert(RHS).second)
760
3.03k
        Inputs.push_back(RHS);
761
3.94k
      continue;
762
3.94k
    }
763
705k
    
if (auto *705k
PN705k
= dyn_cast<PHINode>(Input)) {
764
1.17M
      for (const Value *Op : PN->incoming_values()) {
765
1.17M
        Op = GetUnderlyingObject(Op, DL);
766
1.17M
        if (Visited.insert(Op).second)
767
548k
          Inputs.push_back(Op);
768
1.17M
      }
769
453k
      continue;
770
453k
    }
771
252k
772
252k
    // FIXME: It would be good to handle other obvious no-alias cases here, but
773
252k
    // it isn't clear how to do so reasonbly without building a small version
774
252k
    // of BasicAA into this code. We could recurse into AAResultBase::alias
775
252k
    // here but that seems likely to go poorly as we're inside the
776
252k
    // implementation of such a query. Until then, just conservatievly retun
777
252k
    // false.
778
252k
    return false;
779
1.05M
  } while (!Inputs.empty());
780
908k
781
908k
  // If all the inputs to V were definitively no-alias, then V is no-alias.
782
559k
  return true;
783
908k
}
784
785
/// alias - If one of the pointers is to a global that we are tracking, and the
786
/// other is some random pointer, we know there cannot be an alias, because the
787
/// address of the global isn't taken.
788
AliasResult GlobalsAAResult::alias(const MemoryLocation &LocA,
789
45.5M
                                   const MemoryLocation &LocB) {
790
45.5M
  // Get the base object these pointers point to.
791
45.5M
  const Value *UV1 = GetUnderlyingObject(LocA.Ptr, DL);
792
45.5M
  const Value *UV2 = GetUnderlyingObject(LocB.Ptr, DL);
793
45.5M
794
45.5M
  // If either of the underlying values is a global, they may be non-addr-taken
795
45.5M
  // globals, which we can answer queries about.
796
45.5M
  const GlobalValue *GV1 = dyn_cast<GlobalValue>(UV1);
797
45.5M
  const GlobalValue *GV2 = dyn_cast<GlobalValue>(UV2);
798
45.5M
  if (
GV1 || 45.5M
GV240.8M
) {
799
7.62M
    // If the global's address is taken, pretend we don't know it's a pointer to
800
7.62M
    // the global.
801
7.62M
    if (
GV1 && 7.62M
!NonAddressTakenGlobals.count(GV1)4.62M
)
802
4.00M
      GV1 = nullptr;
803
7.62M
    if (
GV2 && 7.62M
!NonAddressTakenGlobals.count(GV2)3.33M
)
804
2.96M
      GV2 = nullptr;
805
7.62M
806
7.62M
    // If the two pointers are derived from two different non-addr-taken
807
7.62M
    // globals we know these can't alias.
808
7.62M
    if (
GV1 && 7.62M
GV2618k
&&
GV1 != GV239.0k
)
809
0
      return NoAlias;
810
7.62M
811
7.62M
    // If one is and the other isn't, it isn't strictly safe but we can fake
812
7.62M
    // this result if necessary for performance. This does not appear to be
813
7.62M
    // a common problem in practice.
814
7.62M
    
if (7.62M
EnableUnsafeGlobalsModRefAliasResults7.62M
)
815
4
      
if (4
(GV1 || 4
GV20
) &&
GV1 != GV24
)
816
4
        return NoAlias;
817
7.62M
818
7.62M
    // Check for a special case where a non-escaping global can be used to
819
7.62M
    // conclude no-alias.
820
7.62M
    
if (7.62M
(GV1 || 7.62M
GV27.00M
) &&
GV1 != GV2947k
) {
821
908k
      const GlobalValue *GV = GV1 ? 
GV1579k
:
GV2329k
;
822
908k
      const Value *UV = GV1 ? 
UV2579k
:
UV1329k
;
823
908k
      if (isNonEscapingGlobalNoAlias(GV, UV))
824
559k
        return NoAlias;
825
44.9M
    }
826
7.62M
827
7.62M
    // Otherwise if they are both derived from the same addr-taken global, we
828
7.62M
    // can't know the two accesses don't overlap.
829
7.62M
  }
830
44.9M
831
44.9M
  // These pointers may be based on the memory owned by an indirect global.  If
832
44.9M
  // so, we may be able to handle this.  First check to see if the base pointer
833
44.9M
  // is a direct load from an indirect global.
834
44.9M
  GV1 = GV2 = nullptr;
835
44.9M
  if (const LoadInst *LI = dyn_cast<LoadInst>(UV1))
836
16.7M
    
if (GlobalVariable *16.7M
GV16.7M
= dyn_cast<GlobalVariable>(LI->getOperand(0)))
837
1.58M
      
if (1.58M
IndirectGlobals.count(GV)1.58M
)
838
0
        GV1 = GV;
839
44.9M
  if (const LoadInst *LI = dyn_cast<LoadInst>(UV2))
840
22.0M
    
if (const GlobalVariable *22.0M
GV22.0M
= dyn_cast<GlobalVariable>(LI->getOperand(0)))
841
1.71M
      
if (1.71M
IndirectGlobals.count(GV)1.71M
)
842
2
        GV2 = GV;
843
44.9M
844
44.9M
  // These pointers may also be from an allocation for the indirect global.  If
845
44.9M
  // so, also handle them.
846
44.9M
  if (!GV1)
847
44.9M
    GV1 = AllocsForIndirectGlobals.lookup(UV1);
848
44.9M
  if (!GV2)
849
44.9M
    GV2 = AllocsForIndirectGlobals.lookup(UV2);
850
44.9M
851
44.9M
  // Now that we know whether the two pointers are related to indirect globals,
852
44.9M
  // use this to disambiguate the pointers. If the pointers are based on
853
44.9M
  // different indirect globals they cannot alias.
854
44.9M
  if (
GV1 && 44.9M
GV20
&&
GV1 != GV20
)
855
0
    return NoAlias;
856
44.9M
857
44.9M
  // If one is based on an indirect global and the other isn't, it isn't
858
44.9M
  // strictly safe but we can fake this result if necessary for performance.
859
44.9M
  // This does not appear to be a common problem in practice.
860
44.9M
  
if (44.9M
EnableUnsafeGlobalsModRefAliasResults44.9M
)
861
2
    
if (2
(GV1 || 2
GV22
) &&
GV1 != GV22
)
862
2
      return NoAlias;
863
44.9M
864
44.9M
  return AAResultBase::alias(LocA, LocB);
865
44.9M
}
866
867
ModRefInfo GlobalsAAResult::getModRefInfoForArgument(ImmutableCallSite CS,
868
38.4k
                                                     const GlobalValue *GV) {
869
38.4k
  if (CS.doesNotAccessMemory())
870
3.05k
    return MRI_NoModRef;
871
35.3k
  
ModRefInfo ConservativeResult = CS.onlyReadsMemory() ? 35.3k
MRI_Ref6.11k
:
MRI_ModRef29.2k
;
872
35.3k
873
35.3k
  // Iterate through all the arguments to the called function. If any argument
874
35.3k
  // is based on GV, return the conservative result.
875
53.8k
  for (auto &A : CS.args()) {
876
53.8k
    SmallVector<Value*, 4> Objects;
877
53.8k
    GetUnderlyingObjects(A, Objects, DL);
878
53.8k
879
53.8k
    // All objects must be identified.
880
53.8k
    if (!all_of(Objects, isIdentifiedObject) &&
881
53.8k
        // Try ::alias to see if all objects are known not to alias GV.
882
43.8k
        
!all_of(Objects, [&](Value *V) 43.8k
{
883
47.8k
          return this->alias(MemoryLocation(V), MemoryLocation(GV)) == NoAlias;
884
47.8k
        }))
885
23.5k
      return ConservativeResult;
886
30.2k
887
30.2k
    
if (30.2k
is_contained(Objects, GV)30.2k
)
888
0
      return ConservativeResult;
889
11.7k
  }
890
11.7k
891
11.7k
  // We identified all objects in the argument list, and none of them were GV.
892
11.7k
  return MRI_NoModRef;
893
11.7k
}
894
895
ModRefInfo GlobalsAAResult::getModRefInfo(ImmutableCallSite CS,
896
8.45M
                                          const MemoryLocation &Loc) {
897
8.45M
  unsigned Known = MRI_ModRef;
898
8.45M
899
8.45M
  // If we are asking for mod/ref info of a direct call with a pointer to a
900
8.45M
  // global we are tracking, return information if we have it.
901
8.45M
  if (const GlobalValue *GV =
902
8.45M
          dyn_cast<GlobalValue>(GetUnderlyingObject(Loc.Ptr, DL)))
903
1.70M
    
if (1.70M
GV->hasLocalLinkage()1.70M
)
904
257k
      
if (const Function *257k
F257k
= CS.getCalledFunction())
905
245k
        
if (245k
NonAddressTakenGlobals.count(GV)245k
)
906
188k
          
if (const FunctionInfo *188k
FI188k
= getFunctionInfo(F))
907
38.4k
            Known = FI->getModRefInfoForGlobal(*GV) |
908
38.4k
              getModRefInfoForArgument(CS, GV);
909
8.45M
910
8.45M
  if (Known == MRI_NoModRef)
911
7.24k
    return MRI_NoModRef; // No need to query other mod/ref analyses
912
8.44M
  return ModRefInfo(Known & AAResultBase::getModRefInfo(CS, Loc));
913
8.44M
}
914
915
GlobalsAAResult::GlobalsAAResult(const DataLayout &DL,
916
                                 const TargetLibraryInfo &TLI)
917
34.8k
    : AAResultBase(), DL(DL), TLI(TLI) {}
918
919
GlobalsAAResult::GlobalsAAResult(GlobalsAAResult &&Arg)
920
    : AAResultBase(std::move(Arg)), DL(Arg.DL), TLI(Arg.TLI),
921
      NonAddressTakenGlobals(std::move(Arg.NonAddressTakenGlobals)),
922
      IndirectGlobals(std::move(Arg.IndirectGlobals)),
923
      AllocsForIndirectGlobals(std::move(Arg.AllocsForIndirectGlobals)),
924
      FunctionInfos(std::move(Arg.FunctionInfos)),
925
158
      Handles(std::move(Arg.Handles)) {
926
158
  // Update the parent for each DeletionCallbackHandle.
927
48
  for (auto &H : Handles) {
928
48
    assert(H.GAR == &Arg);
929
48
    H.GAR = this;
930
48
  }
931
158
}
932
933
34.9k
GlobalsAAResult::~GlobalsAAResult() {}
934
935
/*static*/ GlobalsAAResult
936
GlobalsAAResult::analyzeModule(Module &M, const TargetLibraryInfo &TLI,
937
34.8k
                               CallGraph &CG) {
938
34.8k
  GlobalsAAResult Result(M.getDataLayout(), TLI);
939
34.8k
940
34.8k
  // Discover which functions aren't recursive, to feed into AnalyzeGlobals.
941
34.8k
  Result.CollectSCCMembership(CG);
942
34.8k
943
34.8k
  // Find non-addr taken globals.
944
34.8k
  Result.AnalyzeGlobals(M);
945
34.8k
946
34.8k
  // Propagate on CG.
947
34.8k
  Result.AnalyzeCallGraph(CG, M);
948
34.8k
949
34.8k
  return Result;
950
34.8k
}
951
952
AnalysisKey GlobalsAA::Key;
953
954
79
GlobalsAAResult GlobalsAA::run(Module &M, ModuleAnalysisManager &AM) {
955
79
  return GlobalsAAResult::analyzeModule(M,
956
79
                                        AM.getResult<TargetLibraryAnalysis>(M),
957
79
                                        AM.getResult<CallGraphAnalysis>(M));
958
79
}
959
960
char GlobalsAAWrapperPass::ID = 0;
961
90.2k
INITIALIZE_PASS_BEGIN90.2k
(GlobalsAAWrapperPass, "globals-aa",
962
90.2k
                      "Globals Alias Analysis", false, true)
963
90.2k
INITIALIZE_PASS_DEPENDENCY(CallGraphWrapperPass)
964
90.2k
INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
965
90.2k
INITIALIZE_PASS_END(GlobalsAAWrapperPass, "globals-aa",
966
                    "Globals Alias Analysis", false, true)
967
968
34.7k
ModulePass *llvm::createGlobalsAAWrapperPass() {
969
34.7k
  return new GlobalsAAWrapperPass();
970
34.7k
}
971
972
34.7k
GlobalsAAWrapperPass::GlobalsAAWrapperPass() : ModulePass(ID) {
973
34.7k
  initializeGlobalsAAWrapperPassPass(*PassRegistry::getPassRegistry());
974
34.7k
}
975
976
34.7k
bool GlobalsAAWrapperPass::runOnModule(Module &M) {
977
34.7k
  Result.reset(new GlobalsAAResult(GlobalsAAResult::analyzeModule(
978
34.7k
      M, getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(),
979
34.7k
      getAnalysis<CallGraphWrapperPass>().getCallGraph())));
980
34.7k
  return false;
981
34.7k
}
982
983
34.7k
bool GlobalsAAWrapperPass::doFinalization(Module &M) {
984
34.7k
  Result.reset();
985
34.7k
  return false;
986
34.7k
}
987
988
34.7k
void GlobalsAAWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
989
34.7k
  AU.setPreservesAll();
990
34.7k
  AU.addRequired<CallGraphWrapperPass>();
991
34.7k
  AU.addRequired<TargetLibraryInfoWrapperPass>();
992
34.7k
}