LLVM  14.0.0git
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 <bitset>
41 
42 namespace llvm {
43 
44 class CallBase;
45 class Value;
46 
47 namespace cflaa {
48 
49 //===----------------------------------------------------------------------===//
50 // AliasAttr related stuffs
51 //===----------------------------------------------------------------------===//
52 
53 /// The number of attributes that AliasAttr should contain. Attributes are
54 /// described below, and 32 was an arbitrary choice because it fits nicely in 32
55 /// bits (because we use a bitset for AliasAttr).
56 static const unsigned NumAliasAttrs = 32;
57 
58 /// These are attributes that an alias analysis can use to mark certain special
59 /// properties of a given pointer. Refer to the related functions below to see
60 /// what kinds of attributes are currently defined.
61 typedef std::bitset<NumAliasAttrs> AliasAttrs;
62 
63 /// Attr represent whether the said pointer comes from an unknown source
64 /// (such as opaque memory or an integer cast).
66 
67 /// AttrUnknown represent whether the said pointer comes from a source not known
68 /// to alias analyses (such as opaque memory or an integer cast).
71 
72 /// AttrCaller represent whether the said pointer comes from a source not known
73 /// to the current function but known to the caller. Values pointed to by the
74 /// arguments of the current function have this attribute set
78 
79 /// AttrEscaped represent whether the said pointer comes from a known source but
80 /// escapes to the unknown world (e.g. casted to an integer, or passed as an
81 /// argument to opaque function). Unlike non-escaped pointers, escaped ones may
82 /// alias pointers coming from unknown sources.
85 
86 /// AttrGlobal represent whether the said pointer is a global value.
87 /// AttrArg represent whether the said pointer is an argument, and if so, what
88 /// index the argument has.
91 
92 /// Given an AliasAttrs, return a new AliasAttrs that only contains attributes
93 /// meaningful to the caller. This function is primarily used for
94 /// interprocedural analysis
95 /// Currently, externally visible AliasAttrs include AttrUnknown, AttrGlobal,
96 /// and AttrEscaped
98 
99 //===----------------------------------------------------------------------===//
100 // Function summary related stuffs
101 //===----------------------------------------------------------------------===//
102 
103 /// The maximum number of arguments we can put into a summary.
104 static const unsigned MaxSupportedArgsInSummary = 50;
105 
106 /// We use InterfaceValue to describe parameters/return value, as well as
107 /// potential memory locations that are pointed to by parameters/return value,
108 /// of a function.
109 /// Index is an integer which represents a single parameter or a return value.
110 /// When the index is 0, it refers to the return value. Non-zero index i refers
111 /// to the i-th parameter.
112 /// DerefLevel indicates the number of dereferences one must perform on the
113 /// parameter/return value to get this InterfaceValue.
115  unsigned Index;
116  unsigned DerefLevel;
117 };
118 
119 inline bool operator==(InterfaceValue LHS, InterfaceValue RHS) {
120  return LHS.Index == RHS.Index && LHS.DerefLevel == RHS.DerefLevel;
121 }
122 inline bool operator!=(InterfaceValue LHS, InterfaceValue RHS) {
123  return !(LHS == RHS);
124 }
125 inline bool operator<(InterfaceValue LHS, InterfaceValue RHS) {
126  return LHS.Index < RHS.Index ||
127  (LHS.Index == RHS.Index && LHS.DerefLevel < RHS.DerefLevel);
128 }
129 inline bool operator>(InterfaceValue LHS, InterfaceValue RHS) {
130  return RHS < LHS;
131 }
132 inline bool operator<=(InterfaceValue LHS, InterfaceValue RHS) {
133  return !(RHS < LHS);
134 }
135 inline bool operator>=(InterfaceValue LHS, InterfaceValue RHS) {
136  return !(LHS < RHS);
137 }
138 
139 // We use UnknownOffset to represent pointer offsets that cannot be determined
140 // at compile time. Note that MemoryLocation::UnknownSize cannot be used here
141 // because we require a signed value.
142 static const int64_t UnknownOffset = INT64_MAX;
143 
144 inline int64_t addOffset(int64_t LHS, int64_t RHS) {
145  if (LHS == UnknownOffset || RHS == UnknownOffset)
146  return UnknownOffset;
147  // FIXME: Do we need to guard against integer overflow here?
148  return LHS + RHS;
149 }
150 
151 /// We use ExternalRelation to describe an externally visible aliasing relations
152 /// between parameters/return value of a function.
155  int64_t Offset;
156 };
157 
159  return LHS.From == RHS.From && LHS.To == RHS.To && LHS.Offset == RHS.Offset;
160 }
162  return !(LHS == RHS);
163 }
165  if (LHS.From < RHS.From)
166  return true;
167  if (LHS.From > RHS.From)
168  return false;
169  if (LHS.To < RHS.To)
170  return true;
171  if (LHS.To > RHS.To)
172  return false;
173  return LHS.Offset < RHS.Offset;
174 }
176  return RHS < LHS;
177 }
179  return !(RHS < LHS);
180 }
182  return !(LHS < RHS);
183 }
184 
185 /// We use ExternalAttribute to describe an externally visible AliasAttrs
186 /// for parameters/return value.
190 };
191 
192 /// AliasSummary is just a collection of ExternalRelation and ExternalAttribute
193 struct AliasSummary {
194  // RetParamRelations is a collection of ExternalRelations.
196 
197  // RetParamAttributes is a collection of ExternalAttributes.
199 };
200 
201 /// This is the result of instantiating InterfaceValue at a particular call
204  unsigned DerefLevel;
205 };
207  CallBase &Call);
208 
210  return LHS.Val == RHS.Val && LHS.DerefLevel == RHS.DerefLevel;
211 }
213  return !(LHS == RHS);
214 }
216  return std::less<Value *>()(LHS.Val, RHS.Val) ||
217  (LHS.Val == RHS.Val && LHS.DerefLevel < RHS.DerefLevel);
218 }
220  return RHS < LHS;
221 }
223  return !(RHS < LHS);
224 }
226  return !(LHS < RHS);
227 }
228 
229 /// This is the result of instantiating ExternalRelation at a particular
230 /// callsite
233  int64_t Offset;
234 };
237 
238 /// This is the result of instantiating ExternalAttribute at a particular
239 /// callsite
243 };
245  CallBase &Call);
246 }
247 
248 template <> struct DenseMapInfo<cflaa::InstantiatedValue> {
252  }
256  }
257  static unsigned getHashValue(const cflaa::InstantiatedValue &IV) {
258  return DenseMapInfo<std::pair<Value *, unsigned>>::getHashValue(
259  std::make_pair(IV.Val, IV.DerefLevel));
260  }
261  static bool isEqual(const cflaa::InstantiatedValue &LHS,
262  const cflaa::InstantiatedValue &RHS) {
263  return LHS.Val == RHS.Val && LHS.DerefLevel == RHS.DerefLevel;
264  }
265 };
266 }
267 
268 #endif
llvm::cflaa::ExternalRelation::From
InterfaceValue From
Definition: AliasAnalysisSummary.h:154
llvm::cflaa::operator<=
bool operator<=(InterfaceValue LHS, InterfaceValue RHS)
Definition: AliasAnalysisSummary.h:132
llvm::cflaa::InstantiatedAttr
This is the result of instantiating ExternalAttribute at a particular callsite.
Definition: AliasAnalysisSummary.h:240
llvm
---------------------— PointerInfo ------------------------------------—
Definition: AllocatorList.h:23
llvm::cflaa::ExternalRelation::To
InterfaceValue To
Definition: AliasAnalysisSummary.h:154
Optional.h
llvm::cflaa::InstantiatedValue::Val
Value * Val
Definition: AliasAnalysisSummary.h:203
llvm::DenseMapInfo< cflaa::InstantiatedValue >::getTombstoneKey
static cflaa::InstantiatedValue getTombstoneKey()
Definition: AliasAnalysisSummary.h:253
llvm::DenseMapInfo< cflaa::InstantiatedValue >::isEqual
static bool isEqual(const cflaa::InstantiatedValue &LHS, const cflaa::InstantiatedValue &RHS)
Definition: AliasAnalysisSummary.h:261
llvm::cflaa::instantiateExternalAttribute
Optional< InstantiatedAttr > instantiateExternalAttribute(ExternalAttribute EAttr, CallBase &Call)
Definition: AliasAnalysisSummary.cpp:96
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1168
llvm::cflaa::instantiateInterfaceValue
Optional< InstantiatedValue > instantiateInterfaceValue(InterfaceValue IValue, CallBase &Call)
Definition: AliasAnalysisSummary.cpp:76
llvm::cflaa::InstantiatedAttr::IValue
InstantiatedValue IValue
Definition: AliasAnalysisSummary.h:241
llvm::cflaa::AliasSummary::RetParamRelations
SmallVector< ExternalRelation, 8 > RetParamRelations
Definition: AliasAnalysisSummary.h:195
llvm::Optional
Definition: APInt.h:33
llvm::cflaa::InterfaceValue
We use InterfaceValue to describe parameters/return value, as well as potential memory locations that...
Definition: AliasAnalysisSummary.h:114
llvm::cflaa::NumAliasAttrs
static const unsigned NumAliasAttrs
The number of attributes that AliasAttr should contain.
Definition: AliasAnalysisSummary.h:56
llvm::cflaa::InstantiatedValue::DerefLevel
unsigned DerefLevel
Definition: AliasAnalysisSummary.h:204
llvm::cflaa::ExternalRelation
We use ExternalRelation to describe an externally visible aliasing relations between parameters/retur...
Definition: AliasAnalysisSummary.h:153
llvm::DenseMapInfo
Definition: APInt.h:34
llvm::cflaa::InterfaceValue::DerefLevel
unsigned DerefLevel
Definition: AliasAnalysisSummary.h:116
llvm::DenseMapInfo< cflaa::InstantiatedValue >::getHashValue
static unsigned getHashValue(const cflaa::InstantiatedValue &IV)
Definition: AliasAnalysisSummary.h:257
llvm::cflaa::ExternalRelation::Offset
int64_t Offset
Definition: AliasAnalysisSummary.h:155
llvm::DenseMapInfo< cflaa::InstantiatedValue >::getEmptyKey
static cflaa::InstantiatedValue getEmptyKey()
Definition: AliasAnalysisSummary.h:249
llvm::cflaa::ExternalAttribute::Attr
AliasAttrs Attr
Definition: AliasAnalysisSummary.h:189
INT64_MAX
#define INT64_MAX
Definition: DataTypes.h:71
llvm::cflaa::getAttrEscaped
AliasAttrs getAttrEscaped()
AttrEscaped represent whether the said pointer comes from a known source but escapes to the unknown w...
Definition: AliasAnalysisSummary.cpp:41
llvm::cflaa::InstantiatedRelation::To
InstantiatedValue To
Definition: AliasAnalysisSummary.h:232
llvm::cflaa::hasUnknownAttr
bool hasUnknownAttr(AliasAttrs Attr)
Definition: AliasAnalysisSummary.cpp:33
llvm::cflaa::instantiateExternalRelation
Optional< InstantiatedRelation > instantiateExternalRelation(ExternalRelation ERelation, CallBase &Call)
Definition: AliasAnalysisSummary.cpp:86
llvm::cflaa::InstantiatedRelation::From
InstantiatedValue From
Definition: AliasAnalysisSummary.h:232
llvm::cflaa::operator<
bool operator<(InterfaceValue LHS, InterfaceValue RHS)
Definition: AliasAnalysisSummary.h:125
llvm::cflaa::isGlobalOrArgAttr
bool isGlobalOrArgAttr(AliasAttrs Attr)
Definition: AliasAnalysisSummary.cpp:65
llvm::cflaa::operator>=
bool operator>=(InterfaceValue LHS, InterfaceValue RHS)
Definition: AliasAnalysisSummary.h:135
llvm::cflaa::operator>
bool operator>(InterfaceValue LHS, InterfaceValue RHS)
Definition: AliasAnalysisSummary.h:129
llvm::cflaa::getAttrUnknown
AliasAttrs getAttrUnknown()
AttrUnknown represent whether the said pointer comes from a source not known to alias analyses (such ...
Definition: AliasAnalysisSummary.cpp:32
llvm::cflaa::AliasSummary::RetParamAttributes
SmallVector< ExternalAttribute, 8 > RetParamAttributes
Definition: AliasAnalysisSummary.h:198
llvm::cflaa::InstantiatedRelation::Offset
int64_t Offset
Definition: AliasAnalysisSummary.h:233
llvm::cflaa::InterfaceValue::Index
unsigned Index
Definition: AliasAnalysisSummary.h:115
llvm::cflaa::UnknownOffset
static const int64_t UnknownOffset
Definition: AliasAnalysisSummary.h:142
llvm::cflaa::hasCallerAttr
bool hasCallerAttr(AliasAttrs Attr)
Definition: AliasAnalysisSummary.cpp:36
llvm::cflaa::InstantiatedRelation
This is the result of instantiating ExternalRelation at a particular callsite.
Definition: AliasAnalysisSummary.h:231
llvm::cflaa::AliasSummary
AliasSummary is just a collection of ExternalRelation and ExternalAttribute.
Definition: AliasAnalysisSummary.h:193
llvm::cflaa::getAttrCaller
AliasAttrs getAttrCaller()
AttrCaller represent whether the said pointer comes from a source not known to the current function b...
Definition: AliasAnalysisSummary.cpp:35
llvm::cflaa::addOffset
int64_t addOffset(int64_t LHS, int64_t RHS)
Definition: AliasAnalysisSummary.h:144
llvm::cflaa::getGlobalOrArgAttrFromValue
AliasAttrs getGlobalOrArgAttrFromValue(const Value &Val)
AttrGlobal represent whether the said pointer is a global value.
Definition: AliasAnalysisSummary.cpp:52
llvm::cflaa::getExternallyVisibleAttrs
AliasAttrs getExternallyVisibleAttrs(AliasAttrs Attr)
Given an AliasAttrs, return a new AliasAttrs that only contains attributes meaningful to the caller.
Definition: AliasAnalysisSummary.cpp:72
llvm::cflaa::InstantiatedAttr::Attr
AliasAttrs Attr
Definition: AliasAnalysisSummary.h:242
llvm::cflaa::operator!=
bool operator!=(InterfaceValue LHS, InterfaceValue RHS)
Definition: AliasAnalysisSummary.h:122
llvm::cflaa::InstantiatedValue
This is the result of instantiating InterfaceValue at a particular call.
Definition: AliasAnalysisSummary.h:202
llvm::TargetStackID::Value
Value
Definition: TargetFrameLowering.h:27
llvm::cflaa::operator==
bool operator==(InterfaceValue LHS, InterfaceValue RHS)
Definition: AliasAnalysisSummary.h:119
llvm::cflaa::ExternalAttribute::IValue
InterfaceValue IValue
Definition: AliasAnalysisSummary.h:188
llvm::cflaa::hasEscapedAttr
bool hasEscapedAttr(AliasAttrs Attr)
Definition: AliasAnalysisSummary.cpp:42
SmallVector.h
llvm::cflaa::AliasAttrs
std::bitset< NumAliasAttrs > AliasAttrs
These are attributes that an alias analysis can use to mark certain special properties of a given poi...
Definition: AliasAnalysisSummary.h:61
DenseMapInfo.h
llvm::CallBase
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
Definition: InstrTypes.h:1161
llvm::cflaa::getAttrNone
AliasAttrs getAttrNone()
Attr represent whether the said pointer comes from an unknown source (such as opaque memory or an int...
Definition: AliasAnalysisSummary.cpp:30
llvm::cflaa::MaxSupportedArgsInSummary
static const unsigned MaxSupportedArgsInSummary
The maximum number of arguments we can put into a summary.
Definition: AliasAnalysisSummary.h:104
llvm::Value
LLVM Value Representation.
Definition: Value.h:75
llvm::cflaa::ExternalAttribute
We use ExternalAttribute to describe an externally visible AliasAttrs for parameters/return value.
Definition: AliasAnalysisSummary.h:187
llvm::cflaa::hasUnknownOrCallerAttr
bool hasUnknownOrCallerAttr(AliasAttrs Attr)
Definition: AliasAnalysisSummary.cpp:37