llvm/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 <bitset>
  41
  42 namespace llvm {
  43
  44 class CallBase;
  45 class Value;
  46
  47 namespace 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).
  56 static 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.
  61 typedef 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).
  65 AliasAttrs getAttrNone();
  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).
  69 AliasAttrs getAttrUnknown();
  70 bool hasUnknownAttr(AliasAttrs);
  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
  75 AliasAttrs getAttrCaller();
  76 bool hasCallerAttr(AliasAttrs);
  77 bool hasUnknownOrCallerAttr(AliasAttrs);
  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.
  83 AliasAttrs getAttrEscaped();
  84 bool hasEscapedAttr(AliasAttrs);
  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.
  89 AliasAttrs getGlobalOrArgAttrFromValue(const Value &);
  90 bool isGlobalOrArgAttr(AliasAttrs);
  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
  97 AliasAttrs getExternallyVisibleAttrs(AliasAttrs);
  98
  99 //===----------------------------------------------------------------------===//
 100 // Function summary related stuffs
 101 //===----------------------------------------------------------------------===//
 102
 103 /// The maximum number of arguments we can put into a summary.
 104 static 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.
 114 struct InterfaceValue {
 115   unsigned Index;
 116   unsigned DerefLevel;
 117 };
 118
 119 inline bool operator==(InterfaceValue LHS, InterfaceValue RHS) {
 120   return LHS.Index == RHS.Index && LHS.DerefLevel == RHS.DerefLevel;
 121 }
 122 inline bool operator!=(InterfaceValue LHS, InterfaceValue RHS) {
 123   return !(LHS == RHS);
 124 }
 125 inline bool operator<(InterfaceValue LHS, InterfaceValue RHS) {
 126   return LHS.Index < RHS.Index ||
 127          (LHS.Index == RHS.Index && LHS.DerefLevel < RHS.DerefLevel);
 128 }
 129 inline bool operator>(InterfaceValue LHS, InterfaceValue RHS) {
 130   return RHS < LHS;
 131 }
 132 inline bool operator<=(InterfaceValue LHS, InterfaceValue RHS) {
 133   return !(RHS < LHS);
 134 }
 135 inline bool operator>=(InterfaceValue LHS, InterfaceValue RHS) {
 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.
 142 static const int64_t UnknownOffset = INT64_MAX;
 143
 144 inline 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.
 153 struct ExternalRelation {
 154   InterfaceValue From, To;
 155   int64_t Offset;
 156 };
 157
 158 inline bool operator==(ExternalRelation LHS, ExternalRelation RHS) {
 159   return LHS.From == RHS.From && LHS.To == RHS.To && LHS.Offset == RHS.Offset;
 160 }
 161 inline bool operator!=(ExternalRelation LHS, ExternalRelation RHS) {
 162   return !(LHS == RHS);
 163 }
 164 inline bool operator<(ExternalRelation LHS, ExternalRelation RHS) {
 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 }
 175 inline bool operator>(ExternalRelation LHS, ExternalRelation RHS) {
 176   return RHS < LHS;
 177 }
 178 inline bool operator<=(ExternalRelation LHS, ExternalRelation RHS) {
 179   return !(RHS < LHS);
 180 }
 181 inline bool operator>=(ExternalRelation LHS, ExternalRelation RHS) {
 182   return !(LHS < RHS);
 183 }
 184
 185 /// We use ExternalAttribute to describe an externally visible AliasAttrs
 186 /// for parameters/return value.
 187 struct ExternalAttribute {
 188   InterfaceValue IValue;
 189   AliasAttrs Attr;
 190 };
 191
 192 /// AliasSummary is just a collection of ExternalRelation and ExternalAttribute
 193 struct AliasSummary {
 194   // RetParamRelations is a collection of ExternalRelations.
 195   SmallVector<ExternalRelation, 8> RetParamRelations;
 196
 197   // RetParamAttributes is a collection of ExternalAttributes.
 198   SmallVector<ExternalAttribute, 8> RetParamAttributes;
 199 };
 200
 201 /// This is the result of instantiating InterfaceValue at a particular call
 202 struct InstantiatedValue {
 203   Value *Val;
 204   unsigned DerefLevel;
 205 };
 206 Optional<InstantiatedValue> instantiateInterfaceValue(InterfaceValue IValue,
 207                                                       CallBase &Call);
 208
 209 inline bool operator==(InstantiatedValue LHS, InstantiatedValue RHS) {
 210   return LHS.Val == RHS.Val && LHS.DerefLevel == RHS.DerefLevel;
 211 }
 212 inline bool operator!=(InstantiatedValue LHS, InstantiatedValue RHS) {
 213   return !(LHS == RHS);
 214 }
 215 inline bool operator<(InstantiatedValue LHS, InstantiatedValue RHS) {
 216   return std::less<Value *>()(LHS.Val, RHS.Val) ||
 217          (LHS.Val == RHS.Val && LHS.DerefLevel < RHS.DerefLevel);
 218 }
 219 inline bool operator>(InstantiatedValue LHS, InstantiatedValue RHS) {
 220   return RHS < LHS;
 221 }
 222 inline bool operator<=(InstantiatedValue LHS, InstantiatedValue RHS) {
 223   return !(RHS < LHS);
 224 }
 225 inline bool operator>=(InstantiatedValue LHS, InstantiatedValue RHS) {
 226   return !(LHS < RHS);
 227 }
 228
 229 /// This is the result of instantiating ExternalRelation at a particular
 230 /// callsite
 231 struct InstantiatedRelation {
 232   InstantiatedValue From, To;
 233   int64_t Offset;
 234 };
 235 Optional<InstantiatedRelation>
 236 instantiateExternalRelation(ExternalRelation ERelation, CallBase &Call);
 237
 238 /// This is the result of instantiating ExternalAttribute at a particular
 239 /// callsite
 240 struct InstantiatedAttr {
 241   InstantiatedValue IValue;
 242   AliasAttrs Attr;
 243 };
 244 Optional<InstantiatedAttr> instantiateExternalAttribute(ExternalAttribute EAttr,
 245                                                         CallBase &Call);
 246 }
 247
 248 template <> struct DenseMapInfo<cflaa::InstantiatedValue> {
 249   static inline cflaa::InstantiatedValue getEmptyKey() {
 250     return cflaa::InstantiatedValue{DenseMapInfo<Value *>::getEmptyKey(),
 251                                     DenseMapInfo<unsigned>::getEmptyKey()};
 252   }
 253   static inline cflaa::InstantiatedValue getTombstoneKey() {
 254     return cflaa::InstantiatedValue{DenseMapInfo<Value *>::getTombstoneKey(),
 255                                     DenseMapInfo<unsigned>::getTombstoneKey()};
 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   }
 261   static bool isEqual(const cflaa::InstantiatedValue &LHS,
 262                       const cflaa::InstantiatedValue &RHS) {
 263     return LHS.Val == RHS.Val && LHS.DerefLevel == RHS.DerefLevel;
 264   }
 265 };
 266 }
 267
 268 #endif