LCOV - code coverage report
Current view: top level - lib/Analysis - AliasAnalysisSummary.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 5 15 33.3 %
Date: 2017-09-14 15:23:50 Functions: 2 3 66.7 %
Legend: Lines: hit not hit

          Line data    Source code
       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             : 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          51 :   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           0 :   return LHS.Index < RHS.Index ||
     125           0 :          (LHS.Index == RHS.Index && LHS.DerefLevel < RHS.DerefLevel);
     126             : }
     127             : inline bool operator>(InterfaceValue LHS, InterfaceValue RHS) {
     128           0 :   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           0 :   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           0 : inline bool operator<(ExternalRelation LHS, ExternalRelation RHS) {
     163           0 :   if (LHS.From < RHS.From)
     164             :     return true;
     165           0 :   if (LHS.From > RHS.From)
     166             :     return false;
     167           0 :   if (LHS.To < RHS.To)
     168             :     return true;
     169           0 :   if (LHS.To > RHS.To)
     170             :     return false;
     171           0 :   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        2520 : 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        1289 :   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       26730 :         std::make_pair(IV.Val, IV.DerefLevel));
     257             :   }
     258             :   static bool isEqual(const cflaa::InstantiatedValue &LHS,
     259             :                       const cflaa::InstantiatedValue &RHS) {
     260      102606 :     return LHS.Val == RHS.Val && LHS.DerefLevel == RHS.DerefLevel;
     261             :   }
     262             : };
     263             : }
     264             : 
     265             : #endif

Generated by: LCOV version 1.13