Coverage Report

Created: 2019-07-24 05:18

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