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