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
43namespace llvm {
44namespace 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).
53static 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.
58typedef 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).
62AliasAttrs 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).
66AliasAttrs getAttrUnknown();
67bool 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
72AliasAttrs getAttrCaller();
73bool hasCallerAttr(AliasAttrs);
74bool 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.
80AliasAttrs getAttrEscaped();
81bool 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.
86AliasAttrs getGlobalOrArgAttrFromValue(const Value &);
87bool 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
94AliasAttrs getExternallyVisibleAttrs(AliasAttrs);
95
96//===----------------------------------------------------------------------===//
97// Function summary related stuffs
98//===----------------------------------------------------------------------===//
99
100/// The maximum number of arguments we can put into a summary.
101static 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.
111struct InterfaceValue {
112  unsigned Index;
113  unsigned DerefLevel;
114};
115
116inline bool operator==(InterfaceValue LHS, InterfaceValue RHS) {
117  return LHS.Index == RHS.Index && LHS.DerefLevel == RHS.DerefLevel;
118}
119inline bool operator!=(InterfaceValue LHS, InterfaceValue RHS) {
120  return !(LHS == RHS);
121}
122inline bool operator<(InterfaceValue LHS, InterfaceValue RHS) {
123  return LHS.Index < RHS.Index ||
124         (LHS.Index == RHS.Index && LHS.DerefLevel < RHS.DerefLevel);
125}
126inline bool operator>(InterfaceValue LHS, InterfaceValue RHS) {
127  return RHS < LHS;
128}
129inline bool operator<=(InterfaceValue LHS, InterfaceValue RHS) {
130  return !(RHS < LHS);
131}
132inline 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.
139static const int64_t UnknownOffset = INT64_MAX;
140
141inline 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.
150struct ExternalRelation {
151  InterfaceValue From, To;
152  int64_t Offset;
153};
154
155inline bool operator==(ExternalRelation LHS, ExternalRelation RHS) {
156  return LHS.From == RHS.From && LHS.To == RHS.To && LHS.Offset == RHS.Offset;
157}
158inline bool operator!=(ExternalRelation LHS, ExternalRelation RHS) {
159  return !(LHS == RHS);
160}
161inline bool operator<(ExternalRelation LHS, ExternalRelation RHS) {
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}
172inline bool operator>(ExternalRelation LHS, ExternalRelation RHS) {
173  return RHS < LHS;
174}
175inline bool operator<=(ExternalRelation LHS, ExternalRelation RHS) {
176  return !(RHS < LHS);
177}
178inline bool operator>=(ExternalRelation LHS, ExternalRelation RHS) {
179  return !(LHS < RHS);
180}
181
182/// We use ExternalAttribute to describe an externally visible AliasAttrs
183/// for parameters/return value.
184struct ExternalAttribute {
185  InterfaceValue IValue;
186  AliasAttrs Attr;
187};
188
189/// AliasSummary is just a collection of ExternalRelation and ExternalAttribute
190struct AliasSummary {
191  // RetParamRelations is a collection of ExternalRelations.
192  SmallVector<ExternalRelation, 8> RetParamRelations;
193
194  // RetParamAttributes is a collection of ExternalAttributes.
195  SmallVector<ExternalAttribute, 8> RetParamAttributes;
196};
197
198/// This is the result of instantiating InterfaceValue at a particular call
199struct InstantiatedValue {
200  Value *Val;
201  unsigned DerefLevel;
202};
203Optional<InstantiatedValue> instantiateInterfaceValue(InterfaceValue IValue,
204                                                      CallBase &Call);
205
206inline bool operator==(InstantiatedValue LHS, InstantiatedValue RHS) {
207  return LHS.Val == RHS.Val && LHS.DerefLevel == RHS.DerefLevel;
208}
209inline bool operator!=(InstantiatedValue LHS, InstantiatedValue RHS) {
210  return !(LHS == RHS);
211}
212inline bool operator<(InstantiatedValue LHS, InstantiatedValue RHS) {
213  return std::less<Value *>()(LHS.Val, RHS.Val) ||
214         (LHS.Val == RHS.Val && LHS.DerefLevel < RHS.DerefLevel);
215}
216inline bool operator>(InstantiatedValue LHS, InstantiatedValue RHS) {
217  return RHS < LHS;
218}
219inline bool operator<=(InstantiatedValue LHS, InstantiatedValue RHS) {
220  return !(RHS < LHS);
221}
222inline bool operator>=(InstantiatedValue LHS, InstantiatedValue RHS) {
223  return !(LHS < RHS);
224}
225
226/// This is the result of instantiating ExternalRelation at a particular
227/// callsite
228struct InstantiatedRelation {
229  InstantiatedValue From, To;
230  int64_t Offset;
231};
232Optional<InstantiatedRelation>
233instantiateExternalRelation(ExternalRelation ERelation, CallBase &Call);
234
235/// This is the result of instantiating ExternalAttribute at a particular
236/// callsite
237struct InstantiatedAttr {
238  InstantiatedValue IValue;
239  AliasAttrs Attr;
240};
241Optional<InstantiatedAttr> instantiateExternalAttribute(ExternalAttribute EAttr,
242                                                        CallBase &Call);
243}
244
245template <> struct DenseMapInfo<cflaa::InstantiatedValue> {
246  static inline cflaa::InstantiatedValue getEmptyKey() {
247    return cflaa::InstantiatedValue{DenseMapInfo<Value *>::getEmptyKey(),
248                                    DenseMapInfo<unsigned>::getEmptyKey()};
249  }
250  static inline cflaa::InstantiatedValue getTombstoneKey() {
251    return cflaa::InstantiatedValue{DenseMapInfo<Value *>::getTombstoneKey(),
252                                    DenseMapInfo<unsigned>::getTombstoneKey()};
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
266