lib/Analysis/AliasAnalysisSummary.h

   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 independently, 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
  44 namespace llvm {
  45 namespace 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).
  54 static 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.
  59 typedef 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).
  63 AliasAttrs 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).
  67 AliasAttrs getAttrUnknown();
  68 bool 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
  73 AliasAttrs getAttrCaller();
  74 bool hasCallerAttr(AliasAttrs);
  75 bool 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.
  81 AliasAttrs getAttrEscaped();
  82 bool 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.
  87 AliasAttrs getGlobalOrArgAttrFromValue(const Value &);
  88 bool 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
  95 AliasAttrs getExternallyVisibleAttrs(AliasAttrs);
  96
  97 //===----------------------------------------------------------------------===//
  98 // Function summary related stuffs
  99 //===----------------------------------------------------------------------===//
 100
 101 /// The maximum number of arguments we can put into a summary.
 102 static const 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.
 112 struct InterfaceValue {
 113   unsigned Index;
 114   unsigned DerefLevel;
 115 };
 116
 117 inline bool operator==(InterfaceValue LHS, InterfaceValue RHS) {
 118   return LHS.Index == RHS.Index && LHS.DerefLevel == RHS.DerefLevel;
 119 }
 120 inline bool operator!=(InterfaceValue LHS, InterfaceValue RHS) {
 121   return !(LHS == RHS);
 122 }
 123 inline bool operator<(InterfaceValue LHS, InterfaceValue RHS) {
 124   return LHS.Index < RHS.Index ||
 125          (LHS.Index == RHS.Index && LHS.DerefLevel < RHS.DerefLevel);
 126 }
 127 inline bool operator>(InterfaceValue LHS, InterfaceValue RHS) {
 128   return RHS < LHS;
 129 }
 130 inline bool operator<=(InterfaceValue LHS, InterfaceValue RHS) {
 131   return !(RHS < LHS);
 132 }
 133 inline bool operator>=(InterfaceValue LHS, InterfaceValue RHS) {
 134   return !(LHS < RHS);
 135 }
 136
 137 // We use UnknownOffset to represent pointer offsets that cannot be determined
 138 // at compile time. Note that MemoryLocation::UnknownSize cannot be used here
 139 // because we require a signed value.
 140 static const int64_t UnknownOffset = INT64_MAX;
 141
 142 inline int64_t addOffset(int64_t LHS, int64_t RHS) {
 143   if (LHS == UnknownOffset || RHS == UnknownOffset)
 144     return UnknownOffset;
 145   // FIXME: Do we need to guard against integer overflow here?
 146   return LHS + RHS;
 147 }
 148
 149 /// We use ExternalRelation to describe an externally visible aliasing relations
 150 /// between parameters/return value of a function.
 151 struct ExternalRelation {
 152   InterfaceValue From, To;
 153   int64_t Offset;
 154 };
 155
 156 inline bool operator==(ExternalRelation LHS, ExternalRelation RHS) {
 157   return LHS.From == RHS.From && LHS.To == RHS.To && LHS.Offset == RHS.Offset;
 158 }
 159 inline bool operator!=(ExternalRelation LHS, ExternalRelation RHS) {
 160   return !(LHS == RHS);
 161 }
 162 inline bool operator<(ExternalRelation LHS, ExternalRelation RHS) {
 163   if (LHS.From < RHS.From)
 164     return true;
 165   if (LHS.From > RHS.From)
 166     return false;
 167   if (LHS.To < RHS.To)
 168     return true;
 169   if (LHS.To > RHS.To)
 170     return false;
 171   return LHS.Offset < RHS.Offset;
 172 }
 173 inline bool operator>(ExternalRelation LHS, ExternalRelation RHS) {
 174   return RHS < LHS;
 175 }
 176 inline bool operator<=(ExternalRelation LHS, ExternalRelation RHS) {
 177   return !(RHS < LHS);
 178 }
 179 inline bool operator>=(ExternalRelation LHS, ExternalRelation RHS) {
 180   return !(LHS < RHS);
 181 }
 182
 183 /// We use ExternalAttribute to describe an externally visible AliasAttrs
 184 /// for parameters/return value.
 185 struct ExternalAttribute {
 186   InterfaceValue IValue;
 187   AliasAttrs Attr;
 188 };
 189
 190 /// AliasSummary is just a collection of ExternalRelation and ExternalAttribute
 191 struct AliasSummary {
 192   // RetParamRelations is a collection of ExternalRelations.
 193   SmallVector<ExternalRelation, 8> RetParamRelations;
 194
 195   // RetParamAttributes is a collection of ExternalAttributes.
 196   SmallVector<ExternalAttribute, 8> RetParamAttributes;
 197 };
 198
 199 /// This is the result of instantiating InterfaceValue at a particular callsite
 200 struct InstantiatedValue {
 201   Value *Val;
 202   unsigned DerefLevel;
 203 };
 204 Optional<InstantiatedValue> instantiateInterfaceValue(InterfaceValue, CallSite);
 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> instantiateExternalRelation(ExternalRelation,
 233                                                            CallSite);
 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,
 242                                                         CallSite);
 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