aboutsummaryrefslogtreecommitdiffstats
path: root/include/llvm/Analysis/AliasAnalysis.h
blob: f1ab7031d0931e675565b420a54ebae4c6dc9289 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
//===- llvm/Analysis/AliasAnalysis.h - Alias Analysis Interface -*- C++ -*-===//
// 
//                     The LLVM Compiler Infrastructure
//
// This file was developed by the LLVM research group and is distributed under
// the University of Illinois Open Source License. See LICENSE.TXT for details.
// 
//===----------------------------------------------------------------------===//
//
// This file defines the generic AliasAnalysis interface, which is used as the
// common interface used by all clients of alias analysis information, and
// implemented by all alias analysis implementations.  Mod/Ref information is
// also captured by this interface.
//
// Implementations of this interface must implement the various virtual methods,
// which automatically provides functionality for the entire suite of client
// APIs.
//
// This API represents memory as a (Pointer, Size) pair.  The Pointer component
// specifies the base memory address of the region, the Size specifies how large
// of an area is being queried.  If Size is 0, two pointers only alias if they
// are exactly equal.  If size is greater than zero, but small, the two pointers
// alias if the areas pointed to overlap.  If the size is very large (ie, ~0U),
// then the two pointers alias if they may be pointing to components of the same
// memory object.  Pointers that point to two completely different objects in
// memory never alias, regardless of the value of the Size component.
//
//===----------------------------------------------------------------------===//

#ifndef LLVM_ANALYSIS_ALIAS_ANALYSIS_H
#define LLVM_ANALYSIS_ALIAS_ANALYSIS_H

#include "llvm/Support/CallSite.h"
#include "llvm/Pass.h"    // Need this for IncludeFile

namespace llvm {

class LoadInst;
class StoreInst;
class TargetData;

class AliasAnalysis {
protected:
  const TargetData *TD;
  AliasAnalysis *AA;       // Previous Alias Analysis to chain to.

  /// InitializeAliasAnalysis - Subclasses must call this method to initialize
  /// the AliasAnalysis interface before any other methods are called.  This is
  /// typically called by the run* methods of these subclasses.  This may be
  /// called multiple times.
  ///
  void InitializeAliasAnalysis(Pass *P);
  
  // getAnalysisUsage - All alias analysis implementations should invoke this
  // directly (using AliasAnalysis::getAnalysisUsage(AU)) to make sure that
  // TargetData is required by the pass.
  virtual void getAnalysisUsage(AnalysisUsage &AU) const;

public:
  AliasAnalysis() : TD(0), AA(0) {}
  virtual ~AliasAnalysis();  // We want to be subclassed

  /// getTargetData - Every alias analysis implementation depends on the size of
  /// data items in the current Target.  This provides a uniform way to handle
  /// it.
  ///
  const TargetData &getTargetData() const { return *TD; }

  //===--------------------------------------------------------------------===//
  /// Alias Queries...
  ///

  /// Alias analysis result - Either we know for sure that it does not alias, we
  /// know for sure it must alias, or we don't know anything: The two pointers
  /// _might_ alias.  This enum is designed so you can do things like:
  ///     if (AA.alias(P1, P2)) { ... }
  /// to check to see if two pointers might alias.
  ///
  enum AliasResult { NoAlias = 0, MayAlias = 1, MustAlias = 2 };

  /// alias - The main low level interface to the alias analysis implementation.
  /// Returns a Result indicating whether the two pointers are aliased to each
  /// other.  This is the interface that must be implemented by specific alias
  /// analysis implementations.
  ///
  virtual AliasResult alias(const Value *V1, unsigned V1Size,
                            const Value *V2, unsigned V2Size);

  /// getMustAliases - If there are any pointers known that must alias this
  /// pointer, return them now.  This allows alias-set based alias analyses to
  /// perform a form a value numbering (which is exposed by load-vn).  If an
  /// alias analysis supports this, it should ADD any must aliased pointers to
  /// the specified vector.
  ///
  virtual void getMustAliases(Value *P, std::vector<Value*> &RetVals);

  /// pointsToConstantMemory - If the specified pointer is known to point into
  /// constant global memory, return true.  This allows disambiguation of store
  /// instructions from constant pointers.
  ///
  virtual bool pointsToConstantMemory(const Value *P);

  /// doesNotAccessMemory - If the specified function is known to never read or
  /// write memory, return true.  If the function only reads from known-constant
  /// memory, it is also legal to return true.  Functions that unwind the stack
  /// are not legal for this predicate.
  ///
  /// Many optimizations (such as CSE and LICM) can be performed on calls to it,
  /// without worrying about aliasing properties, and many functions have this
  /// property (e.g. 'sin' and 'cos').
  ///
  /// This property corresponds to the GCC 'const' attribute.
  ///
  virtual bool doesNotAccessMemory(Function *F);

  /// onlyReadsMemory - If the specified function is known to only read from
  /// non-volatile memory (or not access memory at all), return true.  Functions
  /// that unwind the stack are not legal for this predicate.
  ///
  /// This property allows many common optimizations to be performed in the
  /// absence of interfering store instructions, such as CSE of strlen calls.
  ///
  /// This property corresponds to the GCC 'pure' attribute.
  ///
  virtual bool onlyReadsMemory(Function *F);


  //===--------------------------------------------------------------------===//
  /// Simple mod/ref information...
  ///

  /// ModRefResult - Represent the result of a mod/ref query.  Mod and Ref are
  /// bits which may be or'd together.
  ///
  enum ModRefResult { NoModRef = 0, Ref = 1, Mod = 2, ModRef = 3 };

  /// getModRefInfo - Return information about whether or not an instruction may
  /// read or write memory specified by the pointer operand.  An instruction
  /// that doesn't read or write memory may be trivially LICM'd for example.

  /// getModRefInfo (for call sites) - Return whether information about whether
  /// a particular call site modifies or reads the memory specified by the
  /// pointer.
  ///
  virtual ModRefResult getModRefInfo(CallSite CS, Value *P, unsigned Size);

  /// getModRefInfo - Return information about whether two call sites may refer
  /// to the same set of memory locations.  This function returns NoModRef if
  /// the two calls refer to disjoint memory locations, Ref if CS1 reads memory
  /// written by CS2, Mod if CS1 writes to memory read or written by CS2, or
  /// ModRef if CS1 might read or write memory accessed by CS2.
  ///
  virtual ModRefResult getModRefInfo(CallSite CS1, CallSite CS2);

  /// hasNoModRefInfoForCalls - Return true if the analysis has no mod/ref
  /// information for pairs of function calls (other than "pure" and "const"
  /// functions).  This can be used by clients to avoid many pointless queries.
  /// Remember that if you override this and chain to another analysis, you must
  /// make sure that it doesn't have mod/ref info either.
  ///
  virtual bool hasNoModRefInfoForCalls() const;

  /// Convenience functions...
  ModRefResult getModRefInfo(LoadInst *L, Value *P, unsigned Size);
  ModRefResult getModRefInfo(StoreInst *S, Value *P, unsigned Size);
  ModRefResult getModRefInfo(CallInst *C, Value *P, unsigned Size) {
    return getModRefInfo(CallSite(C), P, Size);
  }
  ModRefResult getModRefInfo(InvokeInst *I, Value *P, unsigned Size) {
    return getModRefInfo(CallSite(I), P, Size);
  }
  ModRefResult getModRefInfo(Instruction *I, Value *P, unsigned Size) {
    switch (I->getOpcode()) {
    case Instruction::Load:   return getModRefInfo((LoadInst*)I, P, Size);
    case Instruction::Store:  return getModRefInfo((StoreInst*)I, P, Size);
    case Instruction::Call:   return getModRefInfo((CallInst*)I, P, Size);
    case Instruction::Invoke: return getModRefInfo((InvokeInst*)I, P, Size);
    default:                  return NoModRef;
    }
  }

  //===--------------------------------------------------------------------===//
  /// Higher level methods for querying mod/ref information.
  ///

  /// canBasicBlockModify - Return true if it is possible for execution of the
  /// specified basic block to modify the value pointed to by Ptr.
  ///
  bool canBasicBlockModify(const BasicBlock &BB, const Value *P, unsigned Size);

  /// canInstructionRangeModify - Return true if it is possible for the
  /// execution of the specified instructions to modify the value pointed to by
  /// Ptr.  The instructions to consider are all of the instructions in the
  /// range of [I1,I2] INCLUSIVE.  I1 and I2 must be in the same basic block.
  ///
  bool canInstructionRangeModify(const Instruction &I1, const Instruction &I2,
                                 const Value *Ptr, unsigned Size);

  //===--------------------------------------------------------------------===//
  /// Methods that clients should call when they transform the program to allow
  /// alias analyses to update their internal data structures.  Note that these
  /// methods may be called on any instruction, regardless of whether or not
  /// they have pointer-analysis implications.
  ///

  /// deleteValue - This method should be called whenever an LLVM Value is
  /// deleted from the program, for example when an instruction is found to be
  /// redundant and is eliminated.
  ///
  virtual void deleteValue(Value *V);

  /// copyValue - This method should be used whenever a preexisting value in the
  /// program is copied or cloned, introducing a new value.  Note that analysis
  /// implementations should tolerate clients that use this method to introduce
  /// the same value multiple times: if the analysis already knows about a
  /// value, it should ignore the request.
  ///
  virtual void copyValue(Value *From, Value *To);

  /// replaceWithNewValue - This method is the obvious combination of the two
  /// above, and it provided as a helper to simplify client code.
  ///
  void replaceWithNewValue(Value *Old, Value *New) {
    copyValue(Old, New);
    deleteValue(Old);
  }
};

// Because of the way .a files work, we must force the BasicAA implementation to
// be pulled in if the AliasAnalysis header is included.  Otherwise we run
// the risk of AliasAnalysis being used, but the default implementation not
// being linked into the tool that uses it.
//
extern void BasicAAStub();
static IncludeFile HDR_INCLUDE_BASICAA_CPP((void*)&BasicAAStub);

} // End llvm namespace

#endif