Home | History | Annotate | Download | only in Analysis 
      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 
     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 LLVM_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.
    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 
    124 /// We use ExternalRelation to describe an externally visible aliasing relations
    125 /// between parameters/return value of a function.
    126 struct ExternalRelation {
    127   InterfaceValue From, To;
    128 };
    129 
    130 /// We use ExternalAttribute to describe an externally visible AliasAttrs
    131 /// for parameters/return value.
    132 struct ExternalAttribute {
    133   InterfaceValue IValue;
    134   AliasAttrs Attr;
    135 };
    136 
    137 /// AliasSummary is just a collection of ExternalRelation and ExternalAttribute
    138 struct 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
    147 struct InstantiatedValue {
    148   Value *Val;
    149   unsigned DerefLevel;
    150 };
    151 Optional<InstantiatedValue> instantiateInterfaceValue(InterfaceValue, CallSite);
    152 
    153 /// This is the result of instantiating ExternalRelation at a particular
    154 /// callsite
    155 struct InstantiatedRelation {
    156   InstantiatedValue From, To;
    157 };
    158 Optional<InstantiatedRelation> instantiateExternalRelation(ExternalRelation,
    159                                                            CallSite);
    160 
    161 /// This is the result of instantiating ExternalAttribute at a particular
    162 /// callsite
    163 struct InstantiatedAttr {
    164   InstantiatedValue IValue;
    165   AliasAttrs Attr;
    166 };
    167 Optional<InstantiatedAttr> instantiateExternalAttribute(ExternalAttribute,
    168                                                         CallSite);
    169 }
    170 
    171 template <> 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