1//===- GlobalsModRef.h - Simple Mod/Ref AA for Globals ----------*- C++ -*-===//
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/// \file
10/// This is the interface for a simple mod/ref and alias analysis over globals.
11///
12//===----------------------------------------------------------------------===//
13
14#ifndef LLVM_ANALYSIS_GLOBALSMODREF_H
15#define LLVM_ANALYSIS_GLOBALSMODREF_H
16
17#include "llvm/Analysis/AliasAnalysis.h"
18#include "llvm/Analysis/CallGraph.h"
19#include "llvm/IR/Constants.h"
20#include "llvm/IR/Function.h"
21#include "llvm/IR/Module.h"
22#include "llvm/IR/ValueHandle.h"
23#include "llvm/Pass.h"
24#include <list>
25
26namespace llvm {
27
28/// An alias analysis result set for globals.
29///
30/// This focuses on handling aliasing properties of globals and interprocedural
31/// function call mod/ref information.
32class GlobalsAAResult : public AAResultBase<GlobalsAAResult> {
33  friend AAResultBase<GlobalsAAResult>;
34
35  class FunctionInfo;
36
37  const DataLayout &DL;
38
39  /// The globals that do not have their addresses taken.
40  SmallPtrSet<const GlobalValue *, 8> NonAddressTakenGlobals;
41
42  /// IndirectGlobals - The memory pointed to by this global is known to be
43  /// 'owned' by the global.
44  SmallPtrSet<const GlobalValue *, 8> IndirectGlobals;
45
46  /// AllocsForIndirectGlobals - If an instruction allocates memory for an
47  /// indirect global, this map indicates which one.
48  DenseMap<const Value *, const GlobalValue *> AllocsForIndirectGlobals;
49
50  /// For each function, keep track of what globals are modified or read.
51  DenseMap<const Function *, FunctionInfo> FunctionInfos;
52
53  /// A map of functions to SCC. The SCCs are described by a simple integer
54  /// ID that is only useful for comparing for equality (are two functions
55  /// in the same SCC or not?)
56  DenseMap<const Function *, unsigned> FunctionToSCCMap;
57
58  /// Handle to clear this analysis on deletion of values.
59  struct DeletionCallbackHandle final : CallbackVH {
60    GlobalsAAResult *GAR;
61    std::list<DeletionCallbackHandle>::iterator I;
62
63    DeletionCallbackHandle(GlobalsAAResult &GAR, Value *V)
64        : CallbackVH(V), GAR(&GAR) {}
65
66    void deleted() override;
67  };
68
69  /// List of callbacks for globals being tracked by this analysis. Note that
70  /// these objects are quite large, but we only anticipate having one per
71  /// global tracked by this analysis. There are numerous optimizations we
72  /// could perform to the memory utilization here if this becomes a problem.
73  std::list<DeletionCallbackHandle> Handles;
74
75  explicit GlobalsAAResult(const DataLayout &DL, const TargetLibraryInfo &TLI);
76
77public:
78  GlobalsAAResult(GlobalsAAResult &&Arg);
79
80  static GlobalsAAResult analyzeModule(Module &M, const TargetLibraryInfo &TLI,
81                                       CallGraph &CG);
82
83  //------------------------------------------------
84  // Implement the AliasAnalysis API
85  //
86  AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB);
87
88  using AAResultBase::getModRefInfo;
89  ModRefInfo getModRefInfo(ImmutableCallSite CS, const MemoryLocation &Loc);
90
91  /// getModRefBehavior - Return the behavior of the specified function if
92  /// called from the specified call site.  The call site may be null in which
93  /// case the most generic behavior of this function should be returned.
94  FunctionModRefBehavior getModRefBehavior(const Function *F);
95
96  /// getModRefBehavior - Return the behavior of the specified function if
97  /// called from the specified call site.  The call site may be null in which
98  /// case the most generic behavior of this function should be returned.
99  FunctionModRefBehavior getModRefBehavior(ImmutableCallSite CS);
100
101private:
102  FunctionInfo *getFunctionInfo(const Function *F);
103
104  void AnalyzeGlobals(Module &M);
105  void AnalyzeCallGraph(CallGraph &CG, Module &M);
106  bool AnalyzeUsesOfPointer(Value *V,
107                            SmallPtrSetImpl<Function *> *Readers = nullptr,
108                            SmallPtrSetImpl<Function *> *Writers = nullptr,
109                            GlobalValue *OkayStoreDest = nullptr);
110  bool AnalyzeIndirectGlobalMemory(GlobalVariable *GV);
111  void CollectSCCMembership(CallGraph &CG);
112
113  bool isNonEscapingGlobalNoAlias(const GlobalValue *GV, const Value *V);
114  ModRefInfo getModRefInfoForArgument(ImmutableCallSite CS,
115                                      const GlobalValue *GV);
116};
117
118/// Analysis pass providing a never-invalidated alias analysis result.
119class GlobalsAA {
120public:
121  typedef GlobalsAAResult Result;
122
123  /// \brief Opaque, unique identifier for this analysis pass.
124  static void *ID() { return (void *)&PassID; }
125
126  GlobalsAAResult run(Module &M, AnalysisManager<Module> *AM);
127
128  /// \brief Provide access to a name for this pass for debugging purposes.
129  static StringRef name() { return "GlobalsAA"; }
130
131private:
132  static char PassID;
133};
134
135/// Legacy wrapper pass to provide the GlobalsAAResult object.
136class GlobalsAAWrapperPass : public ModulePass {
137  std::unique_ptr<GlobalsAAResult> Result;
138
139public:
140  static char ID;
141
142  GlobalsAAWrapperPass();
143
144  GlobalsAAResult &getResult() { return *Result; }
145  const GlobalsAAResult &getResult() const { return *Result; }
146
147  bool runOnModule(Module &M) override;
148  bool doFinalization(Module &M) override;
149  void getAnalysisUsage(AnalysisUsage &AU) const override;
150};
151
152//===--------------------------------------------------------------------===//
153//
154// createGlobalsAAWrapperPass - This pass provides alias and mod/ref info for
155// global values that do not have their addresses taken.
156//
157ModulePass *createGlobalsAAWrapperPass();
158}
159
160#endif
161