LLVM 17.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
39#include <bitset>
40#include <optional>
41
42namespace llvm {
43
44class CallBase;
45class Value;
46
47namespace 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).
56static 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.
61typedef 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.
104static 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
120 return LHS.Index == RHS.Index && LHS.DerefLevel == RHS.DerefLevel;
121}
123 return !(LHS == RHS);
124}
126 return LHS.Index < RHS.Index ||
127 (LHS.Index == RHS.Index && LHS.DerefLevel < RHS.DerefLevel);
128}
130 return RHS < LHS;
131}
133 return !(RHS < LHS);
134}
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.
142static const int64_t UnknownOffset = INT64_MAX;
143
144inline 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
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};
206std::optional<InstantiatedValue>
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};
235std::optional<InstantiatedRelation>
237
238/// This is the result of instantiating ExternalAttribute at a particular
239/// callsite
243};
244std::optional<InstantiatedAttr>
246}
247
248template <> 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 }
263 return LHS.Val == RHS.Val && LHS.DerefLevel == RHS.DerefLevel;
264 }
265};
266}
267
268#endif
This file defines DenseMapInfo traits for DenseMap.
This file defines the SmallVector class.
Value * RHS
Value * LHS
static const uint32_t IV[8]
Definition: blake3_impl.h:85
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
Definition: InstrTypes.h:1184
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1200
LLVM Value Representation.
Definition: Value.h:74
#define INT64_MAX
Definition: DataTypes.h:71
std::optional< InstantiatedValue > instantiateInterfaceValue(InterfaceValue IValue, CallBase &Call)
AliasAttrs getExternallyVisibleAttrs(AliasAttrs Attr)
Given an AliasAttrs, return a new AliasAttrs that only contains attributes meaningful to the caller.
bool hasUnknownOrCallerAttr(AliasAttrs Attr)
AliasAttrs getAttrCaller()
AttrCaller represent whether the said pointer comes from a source not known to the current function b...
int64_t addOffset(int64_t LHS, int64_t RHS)
std::optional< InstantiatedRelation > instantiateExternalRelation(ExternalRelation ERelation, CallBase &Call)
bool hasEscapedAttr(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 operator!=(InterfaceValue LHS, InterfaceValue RHS)
AliasAttrs getAttrNone()
Attr represent whether the said pointer comes from an unknown source (such as opaque memory or an int...
bool operator<=(InterfaceValue LHS, InterfaceValue RHS)
std::optional< InstantiatedAttr > instantiateExternalAttribute(ExternalAttribute EAttr, CallBase &Call)
bool hasCallerAttr(AliasAttrs Attr)
AliasAttrs getGlobalOrArgAttrFromValue(const Value &Val)
AttrGlobal represent whether the said pointer is a global value.
bool operator<(InterfaceValue LHS, InterfaceValue RHS)
bool operator==(InterfaceValue LHS, InterfaceValue RHS)
bool operator>(InterfaceValue LHS, InterfaceValue RHS)
static const unsigned NumAliasAttrs
The number of attributes that AliasAttr should contain.
bool isGlobalOrArgAttr(AliasAttrs Attr)
AliasAttrs getAttrUnknown()
AttrUnknown represent whether the said pointer comes from a source not known to alias analyses (such ...
bool operator>=(InterfaceValue LHS, InterfaceValue RHS)
bool hasUnknownAttr(AliasAttrs Attr)
static const int64_t UnknownOffset
static const unsigned MaxSupportedArgsInSummary
The maximum number of arguments we can put into a summary.
AliasAttrs getAttrEscaped()
AttrEscaped represent whether the said pointer comes from a known source but escapes to the unknown w...
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
static unsigned getHashValue(const cflaa::InstantiatedValue &IV)
static bool isEqual(const cflaa::InstantiatedValue &LHS, const cflaa::InstantiatedValue &RHS)
static cflaa::InstantiatedValue getEmptyKey()
static cflaa::InstantiatedValue getTombstoneKey()
An information struct used to provide DenseMap with the various necessary components for a given valu...
Definition: DenseMapInfo.h:51
AliasSummary is just a collection of ExternalRelation and ExternalAttribute.
SmallVector< ExternalAttribute, 8 > RetParamAttributes
SmallVector< ExternalRelation, 8 > RetParamRelations
We use ExternalAttribute to describe an externally visible AliasAttrs for parameters/return value.
We use ExternalRelation to describe an externally visible aliasing relations between parameters/retur...
This is the result of instantiating ExternalAttribute at a particular callsite.
This is the result of instantiating ExternalRelation at a particular callsite.
This is the result of instantiating InterfaceValue at a particular call.
We use InterfaceValue to describe parameters/return value, as well as potential memory locations that...