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
44namespace llvm {
45namespace 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).
54static 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.
59typedef 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).
63AliasAttrs 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).
67AliasAttrs getAttrUnknown();
68bool 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
73AliasAttrs getAttrCaller();
74bool hasCallerAttr(AliasAttrs);
75bool 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.
81AliasAttrs getAttrEscaped();
82bool 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.
87AliasAttrs getGlobalOrArgAttrFromValue(const Value &);
88bool 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
95AliasAttrs getExternallyVisibleAttrs(AliasAttrs);
96
97//===----------------------------------------------------------------------===//
98// Function summary related stuffs
99//===----------------------------------------------------------------------===//
100
101/// The maximum number of arguments we can put into a summary.
102LLVM_CONSTEXPR static 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.
112struct InterfaceValue {
113  unsigned Index;
114  unsigned DerefLevel;
115};
116
117inline bool operator==(InterfaceValue lhs, InterfaceValue rhs) {
118  return lhs.Index == rhs.Index && lhs.DerefLevel == rhs.DerefLevel;
119}
120inline bool operator!=(InterfaceValue lhs, InterfaceValue rhs) {
121  return !(lhs == rhs);
122}
123
124/// We use ExternalRelation to describe an externally visible aliasing relations
125/// between parameters/return value of a function.
126struct ExternalRelation {
127  InterfaceValue From, To;
128};
129
130/// We use ExternalAttribute to describe an externally visible AliasAttrs
131/// for parameters/return value.
132struct ExternalAttribute {
133  InterfaceValue IValue;
134  AliasAttrs Attr;
135};
136
137/// AliasSummary is just a collection of ExternalRelation and ExternalAttribute
138struct AliasSummary {
139  // RetParamRelations is a collection of ExternalRelations.
140  SmallVector<ExternalRelation, 8> RetParamRelations;
141
142  // RetParamAttributes is a collection of ExternalAttributes.
143  SmallVector<ExternalAttribute, 8> RetParamAttributes;
144};
145
146/// This is the result of instantiating InterfaceValue at a particular callsite
147struct InstantiatedValue {
148  Value *Val;
149  unsigned DerefLevel;
150};
151Optional<InstantiatedValue> instantiateInterfaceValue(InterfaceValue, CallSite);
152
153/// This is the result of instantiating ExternalRelation at a particular
154/// callsite
155struct InstantiatedRelation {
156  InstantiatedValue From, To;
157};
158Optional<InstantiatedRelation> instantiateExternalRelation(ExternalRelation,
159                                                           CallSite);
160
161/// This is the result of instantiating ExternalAttribute at a particular
162/// callsite
163struct InstantiatedAttr {
164  InstantiatedValue IValue;
165  AliasAttrs Attr;
166};
167Optional<InstantiatedAttr> instantiateExternalAttribute(ExternalAttribute,
168                                                        CallSite);
169}
170
171template <> struct DenseMapInfo<cflaa::InstantiatedValue> {
172  static inline cflaa::InstantiatedValue getEmptyKey() {
173    return cflaa::InstantiatedValue{DenseMapInfo<Value *>::getEmptyKey(),
174                                    DenseMapInfo<unsigned>::getEmptyKey()};
175  }
176  static inline cflaa::InstantiatedValue getTombstoneKey() {
177    return cflaa::InstantiatedValue{DenseMapInfo<Value *>::getTombstoneKey(),
178                                    DenseMapInfo<unsigned>::getTombstoneKey()};
179  }
180  static unsigned getHashValue(const cflaa::InstantiatedValue &IV) {
181    return DenseMapInfo<std::pair<Value *, unsigned>>::getHashValue(
182        std::make_pair(IV.Val, IV.DerefLevel));
183  }
184  static bool isEqual(const cflaa::InstantiatedValue &LHS,
185                      const cflaa::InstantiatedValue &RHS) {
186    return LHS.Val == RHS.Val && LHS.DerefLevel == RHS.DerefLevel;
187  }
188};
189}
190
191#endif
192