LLVM  6.0.0svn
AliasAnalysisSummary.h
Go to the documentation of this file.
1 //=====- CFLSummary.h - Abstract stratified sets implementation. --------=====//
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 file defines various utility types and functions useful to
11 /// summary-based alias analysis.
12 ///
13 /// Summary-based analysis, also known as bottom-up analysis, is a style of
14 /// interprocedrual static analysis that tries to analyze the callees before the
15 /// callers get analyzed. The key idea of summary-based analysis is to first
16 /// process each function indepedently, outline its behavior in a condensed
17 /// summary, and then instantiate the summary at the callsite when the said
18 /// function is called elsewhere. This is often in contrast to another style
19 /// called top-down analysis, in which callers are always analyzed first before
20 /// the callees.
21 ///
22 /// In a summary-based analysis, functions must be examined independently and
23 /// out-of-context. We have no information on the state of the memory, the
24 /// arguments, the global values, and anything else external to the function. To
25 /// carry out the analysis conservative assumptions have to be made about those
26 /// external states. In exchange for the potential loss of precision, the
27 /// summary we obtain this way is highly reusable, which makes the analysis
28 /// easier to scale to large programs even if carried out context-sensitively.
29 ///
30 /// Currently, all CFL-based alias analyses adopt the summary-based approach
31 /// and therefore heavily rely on this header.
32 ///
33 //===----------------------------------------------------------------------===//
34 
35 #ifndef LLVM_ANALYSIS_ALIASANALYSISSUMMARY_H
36 #define LLVM_ANALYSIS_ALIASANALYSISSUMMARY_H
37 
38 #include "llvm/ADT/DenseMapInfo.h"
39 #include "llvm/ADT/Optional.h"
40 #include "llvm/ADT/SmallVector.h"
41 #include "llvm/IR/CallSite.h"
42 #include <bitset>
43 
44 namespace llvm {
45 namespace cflaa {
46 
47 //===----------------------------------------------------------------------===//
48 // AliasAttr related stuffs
49 //===----------------------------------------------------------------------===//
50 
51 /// The number of attributes that AliasAttr should contain. Attributes are
52 /// described below, and 32 was an arbitrary choice because it fits nicely in 32
53 /// bits (because we use a bitset for AliasAttr).
54 static const unsigned NumAliasAttrs = 32;
55 
56 /// These are attributes that an alias analysis can use to mark certain special
57 /// properties of a given pointer. Refer to the related functions below to see
58 /// what kinds of attributes are currently defined.
59 typedef std::bitset<NumAliasAttrs> AliasAttrs;
60 
61 /// Attr represent whether the said pointer comes from an unknown source
62 /// (such as opaque memory or an integer cast).
63 AliasAttrs getAttrNone();
64 
65 /// AttrUnknown represent whether the said pointer comes from a source not known
66 /// to alias analyses (such as opaque memory or an integer cast).
67 AliasAttrs getAttrUnknown();
68 bool hasUnknownAttr(AliasAttrs);
69 
70 /// AttrCaller represent whether the said pointer comes from a source not known
71 /// to the current function but known to the caller. Values pointed to by the
72 /// arguments of the current function have this attribute set
73 AliasAttrs getAttrCaller();
74 bool hasCallerAttr(AliasAttrs);
75 bool hasUnknownOrCallerAttr(AliasAttrs);
76 
77 /// AttrEscaped represent whether the said pointer comes from a known source but
78 /// escapes to the unknown world (e.g. casted to an integer, or passed as an
79 /// argument to opaque function). Unlike non-escaped pointers, escaped ones may
80 /// alias pointers coming from unknown sources.
81 AliasAttrs getAttrEscaped();
82 bool hasEscapedAttr(AliasAttrs);
83 
84 /// AttrGlobal represent whether the said pointer is a global value.
85 /// AttrArg represent whether the said pointer is an argument, and if so, what
86 /// index the argument has.
87 AliasAttrs getGlobalOrArgAttrFromValue(const Value &);
88 bool isGlobalOrArgAttr(AliasAttrs);
89 
90 /// Given an AliasAttrs, return a new AliasAttrs that only contains attributes
91 /// meaningful to the caller. This function is primarily used for
92 /// interprocedural analysis
93 /// Currently, externally visible AliasAttrs include AttrUnknown, AttrGlobal,
94 /// and AttrEscaped
95 AliasAttrs getExternallyVisibleAttrs(AliasAttrs);
96 
97 //===----------------------------------------------------------------------===//
98 // Function summary related stuffs
99 //===----------------------------------------------------------------------===//
100 
101 /// The maximum number of arguments we can put into a summary.
102 static const unsigned MaxSupportedArgsInSummary = 50;
103 
104 /// We use InterfaceValue to describe parameters/return value, as well as
105 /// potential memory locations that are pointed to by parameters/return value,
106 /// of a function.
107 /// Index is an integer which represents a single parameter or a return value.
108 /// When the index is 0, it refers to the return value. Non-zero index i refers
109 /// to the i-th parameter.
110 /// DerefLevel indicates the number of dereferences one must perform on the
111 /// parameter/return value to get this InterfaceValue.
113  unsigned Index;
114  unsigned DerefLevel;
115 };
116 
117 inline bool operator==(InterfaceValue LHS, InterfaceValue RHS) {
118  return LHS.Index == RHS.Index && LHS.DerefLevel == RHS.DerefLevel;
119 }
120 inline bool operator!=(InterfaceValue LHS, InterfaceValue RHS) {
121  return !(LHS == RHS);
122 }
123 inline bool operator<(InterfaceValue LHS, InterfaceValue RHS) {
124  return LHS.Index < RHS.Index ||
125  (LHS.Index == RHS.Index && LHS.DerefLevel < RHS.DerefLevel);
126 }
127 inline bool operator>(InterfaceValue LHS, InterfaceValue RHS) {
128  return RHS < LHS;
129 }
130 inline bool operator<=(InterfaceValue LHS, InterfaceValue RHS) {
131  return !(RHS < LHS);
132 }
133 inline bool operator>=(InterfaceValue LHS, InterfaceValue RHS) {
134  return !(LHS < RHS);
135 }
136 
137 // We use UnknownOffset to represent pointer offsets that cannot be determined
138 // at compile time. Note that MemoryLocation::UnknownSize cannot be used here
139 // because we require a signed value.
140 static const int64_t UnknownOffset = INT64_MAX;
141 
142 inline int64_t addOffset(int64_t LHS, int64_t RHS) {
143  if (LHS == UnknownOffset || RHS == UnknownOffset)
144  return UnknownOffset;
145  // FIXME: Do we need to guard against integer overflow here?
146  return LHS + RHS;
147 }
148 
149 /// We use ExternalRelation to describe an externally visible aliasing relations
150 /// between parameters/return value of a function.
153  int64_t Offset;
154 };
155 
157  return LHS.From == RHS.From && LHS.To == RHS.To && LHS.Offset == RHS.Offset;
158 }
160  return !(LHS == RHS);
161 }
163  if (LHS.From < RHS.From)
164  return true;
165  if (LHS.From > RHS.From)
166  return false;
167  if (LHS.To < RHS.To)
168  return true;
169  if (LHS.To > RHS.To)
170  return false;
171  return LHS.Offset < RHS.Offset;
172 }
174  return RHS < LHS;
175 }
177  return !(RHS < LHS);
178 }
180  return !(LHS < RHS);
181 }
182 
183 /// We use ExternalAttribute to describe an externally visible AliasAttrs
184 /// for parameters/return value.
187  AliasAttrs Attr;
188 };
189 
190 /// AliasSummary is just a collection of ExternalRelation and ExternalAttribute
191 struct AliasSummary {
192  // RetParamRelations is a collection of ExternalRelations.
194 
195  // RetParamAttributes is a collection of ExternalAttributes.
197 };
198 
199 /// This is the result of instantiating InterfaceValue at a particular callsite
202  unsigned DerefLevel;
203 };
205 
207  return LHS.Val == RHS.Val && LHS.DerefLevel == RHS.DerefLevel;
208 }
210  return !(LHS == RHS);
211 }
213  return std::less<Value *>()(LHS.Val, RHS.Val) ||
214  (LHS.Val == RHS.Val && LHS.DerefLevel < RHS.DerefLevel);
215 }
217  return RHS < LHS;
218 }
220  return !(RHS < LHS);
221 }
223  return !(LHS < RHS);
224 }
225 
226 /// This is the result of instantiating ExternalRelation at a particular
227 /// callsite
230  int64_t Offset;
231 };
233  CallSite);
234 
235 /// This is the result of instantiating ExternalAttribute at a particular
236 /// callsite
239  AliasAttrs Attr;
240 };
242  CallSite);
243 }
244 
245 template <> struct DenseMapInfo<cflaa::InstantiatedValue> {
249  }
253  }
254  static unsigned getHashValue(const cflaa::InstantiatedValue &IV) {
255  return DenseMapInfo<std::pair<Value *, unsigned>>::getHashValue(
256  std::make_pair(IV.Val, IV.DerefLevel));
257  }
258  static bool isEqual(const cflaa::InstantiatedValue &LHS,
259  const cflaa::InstantiatedValue &RHS) {
260  return LHS.Val == RHS.Val && LHS.DerefLevel == RHS.DerefLevel;
261  }
262 };
263 }
264 
265 #endif
Optional< InstantiatedValue > instantiateInterfaceValue(InterfaceValue IValue, CallSite CS)
static const unsigned NumAliasAttrs
The number of attributes that AliasAttr should contain.
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
We use ExternalRelation to describe an externally visible aliasing relations between parameters/retur...
bool operator<=(InterfaceValue LHS, InterfaceValue RHS)
static cflaa::InstantiatedValue getEmptyKey()
This is the result of instantiating InterfaceValue at a particular callsite.
We use ExternalAttribute to describe an externally visible AliasAttrs for parameters/return value...
We use InterfaceValue to describe parameters/return value, as well as potential memory locations that...
static cflaa::InstantiatedValue getTombstoneKey()
SmallVector< ExternalAttribute, 8 > RetParamAttributes
bool operator<(InterfaceValue LHS, InterfaceValue RHS)
AliasSummary is just a collection of ExternalRelation and ExternalAttribute.
static bool isEqual(const cflaa::InstantiatedValue &LHS, const cflaa::InstantiatedValue &RHS)
AliasAttrs getAttrEscaped()
AttrEscaped represent whether the said pointer comes from a known source but escapes to the unknown w...
SmallVector< ExternalRelation, 8 > RetParamRelations
Optional< InstantiatedAttr > instantiateExternalAttribute(ExternalAttribute EAttr, CallSite CS)
bool hasUnknownAttr(AliasAttrs Attr)
int64_t addOffset(int64_t LHS, int64_t RHS)
bool isGlobalOrArgAttr(AliasAttrs Attr)
bool operator>=(InterfaceValue LHS, InterfaceValue RHS)
AliasAttrs getAttrUnknown()
AttrUnknown represent whether the said pointer comes from a source not known to alias analyses (such ...
static unsigned getHashValue(const cflaa::InstantiatedValue &IV)
bool operator>(InterfaceValue LHS, InterfaceValue RHS)
AliasAttrs getExternallyVisibleAttrs(AliasAttrs Attr)
Given an AliasAttrs, return a new AliasAttrs that only contains attributes meaningful to the caller...
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:864
bool operator!=(InterfaceValue LHS, InterfaceValue RHS)
static const int64_t UnknownOffset
AliasAttrs getGlobalOrArgAttrFromValue(const Value &Val)
AttrGlobal represent whether the said pointer is a global value.
bool hasUnknownOrCallerAttr(AliasAttrs Attr)
std::bitset< NumAliasAttrs > AliasAttrs
These are attributes that an alias analysis can use to mark certain special properties of a given poi...
bool hasCallerAttr(AliasAttrs Attr)
AliasAttrs getAttrCaller()
AttrCaller represent whether the said pointer comes from a source not known to the current function b...
This is the result of instantiating ExternalRelation at a particular callsite.
bool hasEscapedAttr(AliasAttrs Attr)
LLVM Value Representation.
Definition: Value.h:73
AliasAttrs getAttrNone()
Attr represent whether the said pointer comes from an unknown source (such as opaque memory or an int...
Optional< InstantiatedRelation > instantiateExternalRelation(ExternalRelation ERelation, CallSite CS)
static const unsigned MaxSupportedArgsInSummary
The maximum number of arguments we can put into a summary.
This is the result of instantiating ExternalAttribute at a particular callsite.
bool operator==(InterfaceValue LHS, InterfaceValue RHS)