lib/Analysis/AliasAnalysisSummary.h

   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.
 111 struct 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.
 150 struct ExternalRelation {
 151   InterfaceValue From, To;
 152   int64_t Offset;
 153 };
 154
 155 inline bool operator==(ExternalRelation LHS, ExternalRelation RHS) {
 156   return LHS.From == RHS.From && LHS.To == RHS.To && LHS.Offset == RHS.Offset;
 157 }
 158 inline bool operator!=(ExternalRelation LHS, ExternalRelation RHS) {
 159   return !(LHS == RHS);
 160 }
 161 inline 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 }
 172 inline bool operator>(ExternalRelation LHS, ExternalRelation RHS) {
 173   return RHS < LHS;
 174 }
 175 inline bool operator<=(ExternalRelation LHS, ExternalRelation RHS) {
 176   return !(RHS < LHS);
 177 }
 178 inline 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.
 184 struct ExternalAttribute {
 185   InterfaceValue IValue;
 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.
 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
 199 struct InstantiatedValue {
 200   Value *Val;
 201   unsigned DerefLevel;
 202 };
 203 Optional<InstantiatedValue> instantiateInterfaceValue(InterfaceValue IValue,
 204                                                       CallBase &Call);
 205
 206 inline bool operator==(InstantiatedValue LHS, InstantiatedValue RHS) {
 207   return LHS.Val == RHS.Val && LHS.DerefLevel == RHS.DerefLevel;
 208 }
 209 inline bool operator!=(InstantiatedValue LHS, InstantiatedValue RHS) {
 210   return !(LHS == RHS);
 211 }
 212 inline 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 }
 216 inline bool operator>(InstantiatedValue LHS, InstantiatedValue RHS) {
 217   return RHS < LHS;
 218 }
 219 inline bool operator<=(InstantiatedValue LHS, InstantiatedValue RHS) {
 220   return !(RHS < LHS);
 221 }
 222 inline 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
 228 struct InstantiatedRelation {
 229   InstantiatedValue From, To;
 230   int64_t Offset;
 231 };
 232 Optional<InstantiatedRelation>
 233 instantiateExternalRelation(ExternalRelation ERelation, CallBase &Call);
 234
 235 /// This is the result of instantiating ExternalAttribute at a particular
 236 /// callsite
 237 struct InstantiatedAttr {
 238   InstantiatedValue IValue;
 239   AliasAttrs Attr;
 240 };
 241 Optional<InstantiatedAttr> instantiateExternalAttribute(ExternalAttribute EAttr,
 242                                                         CallBase &Call);
 243 }
 244
 245 template <> 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