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