LCOV - code coverage report
Current view: top level - include/llvm/Analysis - AliasSetTracker.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 53 53 100.0 %
Date: 2018-07-13 00:08:38 Functions: 8 8 100.0 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : //===- llvm/Analysis/AliasSetTracker.h - Build Alias Sets -------*- C++ -*-===//
       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             : //
      10             : // This file defines two classes: AliasSetTracker and AliasSet. These interfaces
      11             : // are used to classify a collection of pointer references into a maximal number
      12             : // of disjoint sets. Each AliasSet object constructed by the AliasSetTracker
      13             : // object refers to memory disjoint from the other sets.
      14             : //
      15             : //===----------------------------------------------------------------------===//
      16             : 
      17             : #ifndef LLVM_ANALYSIS_ALIASSETTRACKER_H
      18             : #define LLVM_ANALYSIS_ALIASSETTRACKER_H
      19             : 
      20             : #include "llvm/ADT/DenseMap.h"
      21             : #include "llvm/ADT/DenseMapInfo.h"
      22             : #include "llvm/ADT/ilist.h"
      23             : #include "llvm/ADT/ilist_node.h"
      24             : #include "llvm/Analysis/AliasAnalysis.h"
      25             : #include "llvm/IR/Instruction.h"
      26             : #include "llvm/IR/Metadata.h"
      27             : #include "llvm/IR/ValueHandle.h"
      28             : #include "llvm/Support/Casting.h"
      29             : #include <cassert>
      30             : #include <cstddef>
      31             : #include <cstdint>
      32             : #include <iterator>
      33             : #include <vector>
      34             : 
      35             : namespace llvm {
      36             : 
      37             : class AliasSetTracker;
      38             : class BasicBlock;
      39             : class LoadInst;
      40             : class AnyMemSetInst;
      41             : class AnyMemTransferInst;
      42             : class raw_ostream;
      43             : class StoreInst;
      44             : class VAArgInst;
      45             : class Value;
      46             : 
      47       43910 : class AliasSet : public ilist_node<AliasSet> {
      48             :   friend class AliasSetTracker;
      49             : 
      50             :   class PointerRec {
      51             :     Value *Val;  // The pointer this record corresponds to.
      52             :     PointerRec **PrevInList = nullptr;
      53             :     PointerRec *NextInList = nullptr;
      54             :     AliasSet *AS = nullptr;
      55             :     LocationSize Size = 0;
      56             :     AAMDNodes AAInfo;
      57             : 
      58             :   public:
      59             :     PointerRec(Value *V)
      60      172874 :       : Val(V), AAInfo(DenseMapInfo<AAMDNodes>::getEmptyKey()) {}
      61             : 
      62             :     Value *getValue() const { return Val; }
      63             : 
      64             :     PointerRec *getNext() const { return NextInList; }
      65             :     bool hasAliasSet() const { return AS != nullptr; }
      66             : 
      67             :     PointerRec** setPrevInList(PointerRec **PIL) {
      68      190652 :       PrevInList = PIL;
      69      172874 :       return &NextInList;
      70             :     }
      71             : 
      72      594141 :     bool updateSizeAndAAInfo(LocationSize NewSize, const AAMDNodes &NewAAInfo) {
      73             :       bool SizeChanged = false;
      74      594141 :       if (NewSize > Size) {
      75      172978 :         Size = NewSize;
      76             :         SizeChanged = true;
      77             :       }
      78             : 
      79             :       if (AAInfo == DenseMapInfo<AAMDNodes>::getEmptyKey())
      80             :         // We don't have a AAInfo yet. Set it to NewAAInfo.
      81      172874 :         AAInfo = NewAAInfo;
      82             :       else {
      83             :         AAMDNodes Intersection(AAInfo.intersect(NewAAInfo));
      84             :         if (!Intersection) {
      85             :           // NewAAInfo conflicts with AAInfo.
      86      368394 :           AAInfo = DenseMapInfo<AAMDNodes>::getTombstoneKey();
      87             :           return SizeChanged;
      88             :         }
      89       52873 :         AAInfo = Intersection;
      90             :       }
      91             :       return SizeChanged;
      92             :     }
      93             : 
      94             :     LocationSize getSize() const { return Size; }
      95             : 
      96             :     /// Return the AAInfo, or null if there is no information or conflicting
      97             :     /// information.
      98             :     AAMDNodes getAAInfo() const {
      99             :       // If we have missing or conflicting AAInfo, return null.
     100             :       if (AAInfo == DenseMapInfo<AAMDNodes>::getEmptyKey() ||
     101             :           AAInfo == DenseMapInfo<AAMDNodes>::getTombstoneKey())
     102             :         return AAMDNodes();
     103      824117 :       return AAInfo;
     104             :     }
     105             : 
     106      397720 :     AliasSet *getAliasSet(AliasSetTracker &AST) {
     107             :       assert(AS && "No AliasSet yet!");
     108      397720 :       if (AS->Forward) {
     109             :         AliasSet *OldAS = AS;
     110       15967 :         AS = OldAS->getForwardedTarget(AST);
     111             :         AS->addRef();
     112             :         OldAS->dropRef(AST);
     113             :       }
     114      397720 :       return AS;
     115             :     }
     116             : 
     117             :     void setAliasSet(AliasSet *as) {
     118             :       assert(!AS && "Already have an alias set!");
     119      172874 :       AS = as;
     120             :     }
     121             : 
     122      172756 :     void eraseFromList() {
     123      172756 :       if (NextInList) NextInList->PrevInList = PrevInList;
     124      172756 :       *PrevInList = NextInList;
     125      172756 :       if (AS->PtrListEnd == &NextInList) {
     126       40043 :         AS->PtrListEnd = PrevInList;
     127             :         assert(*AS->PtrListEnd == nullptr && "List not terminated right!");
     128             :       }
     129      172756 :       delete this;
     130      172756 :     }
     131             :   };
     132             : 
     133             :   // Doubly linked list of nodes.
     134             :   PointerRec *PtrList = nullptr;
     135             :   PointerRec **PtrListEnd;
     136             :   // Forwarding pointer.
     137             :   AliasSet *Forward = nullptr;
     138             : 
     139             :   /// All instructions without a specific address in this alias set.
     140             :   /// In rare cases this vector can have a null'ed out WeakVH
     141             :   /// instances (can happen if some other loop pass deletes an
     142             :   /// instruction in this list).
     143             :   std::vector<WeakVH> UnknownInsts;
     144             : 
     145             :   /// Number of nodes pointing to this AliasSet plus the number of AliasSets
     146             :   /// forwarding to it.
     147             :   unsigned RefCount : 27;
     148             : 
     149             :   // Signifies that this set should be considered to alias any pointer.
     150             :   // Use when the tracker holding this set is saturated.
     151             :   unsigned AliasAny : 1;
     152             : 
     153             :   /// The kinds of access this alias set models.
     154             :   ///
     155             :   /// We keep track of whether this alias set merely refers to the locations of
     156             :   /// memory (and not any particular access), whether it modifies or references
     157             :   /// the memory, or whether it does both. The lattice goes from "NoAccess" to
     158             :   /// either RefAccess or ModAccess, then to ModRefAccess as necessary.
     159             :   enum AccessLattice {
     160             :     NoAccess = 0,
     161             :     RefAccess = 1,
     162             :     ModAccess = 2,
     163             :     ModRefAccess = RefAccess | ModAccess
     164             :   };
     165             :   unsigned Access : 2;
     166             : 
     167             :   /// The kind of alias relationship between pointers of the set.
     168             :   ///
     169             :   /// These represent conservatively correct alias results between any members
     170             :   /// of the set. We represent these independently of the values of alias
     171             :   /// results in order to pack it into a single bit. Lattice goes from
     172             :   /// MustAlias to MayAlias.
     173             :   enum AliasLattice {
     174             :     SetMustAlias = 0, SetMayAlias = 1
     175             :   };
     176             :   unsigned Alias : 1;
     177             : 
     178             :   /// True if this alias set contains volatile loads or stores.
     179             :   unsigned Volatile : 1;
     180             : 
     181             :   unsigned SetSize = 0;
     182             : 
     183      215046 :   void addRef() { ++RefCount; }
     184             : 
     185       14946 :   void dropRef(AliasSetTracker &AST) {
     186             :     assert(RefCount >= 1 && "Invalid reference count detected!");
     187       32841 :     if (--RefCount == 0)
     188       14955 :       removeFromTracker(AST);
     189       14946 :   }
     190             : 
     191             :   Instruction *getUnknownInst(unsigned i) const {
     192             :     assert(i < UnknownInsts.size());
     193      179365 :     return cast_or_null<Instruction>(UnknownInsts[i]);
     194             :   }
     195             : 
     196             : public:
     197             :   AliasSet(const AliasSet &) = delete;
     198             :   AliasSet &operator=(const AliasSet &) = delete;
     199             : 
     200             :   /// Accessors...
     201             :   bool isRef() const { return Access & RefAccess; }
     202      144976 :   bool isMod() const { return Access & ModAccess; }
     203      211292 :   bool isMustAlias() const { return Alias == SetMustAlias; }
     204             :   bool isMayAlias()  const { return Alias == SetMayAlias; }
     205             : 
     206             :   /// Return true if this alias set contains volatile loads or stores.
     207        9963 :   bool isVolatile() const { return Volatile; }
     208             : 
     209             :   /// Return true if this alias set should be ignored as part of the
     210             :   /// AliasSetTracker object.
     211             :   bool isForwardingAliasSet() const { return Forward; }
     212             : 
     213             :   /// Merge the specified alias set into this alias set.
     214             :   void mergeSetIn(AliasSet &AS, AliasSetTracker &AST);
     215             : 
     216             :   // Alias Set iteration - Allow access to all of the pointers which are part of
     217             :   // this alias set.
     218             :   class iterator;
     219             :   iterator begin() const { return iterator(PtrList); }
     220             :   iterator end()   const { return iterator(); }
     221             :   bool empty() const { return PtrList == nullptr; }
     222             : 
     223             :   // Unfortunately, ilist::size() is linear, so we have to add code to keep
     224             :   // track of the list's exact size.
     225             :   unsigned size() { return SetSize; }
     226             : 
     227             :   void print(raw_ostream &OS) const;
     228             :   void dump() const;
     229             : 
     230             :   /// Define an iterator for alias sets... this is just a forward iterator.
     231             :   class iterator : public std::iterator<std::forward_iterator_tag,
     232             :                                         PointerRec, ptrdiff_t> {
     233             :     PointerRec *CurNode;
     234             : 
     235             :   public:
     236             :     explicit iterator(PointerRec *CN = nullptr) : CurNode(CN) {}
     237             : 
     238             :     bool operator==(const iterator& x) const {
     239     2260270 :       return CurNode == x.CurNode;
     240             :     }
     241             :     bool operator!=(const iterator& x) const { return !operator==(x); }
     242             : 
     243             :     value_type &operator*() const {
     244             :       assert(CurNode && "Dereferencing AliasSet.end()!");
     245             :       return *CurNode;
     246             :     }
     247             :     value_type *operator->() const { return &operator*(); }
     248             : 
     249     2199482 :     Value *getPointer() const { return CurNode->getValue(); }
     250     2199482 :     LocationSize getSize() const { return CurNode->getSize(); }
     251     4398830 :     AAMDNodes getAAInfo() const { return CurNode->getAAInfo(); }
     252             : 
     253             :     iterator& operator++() {                // Preincrement
     254             :       assert(CurNode && "Advancing past AliasSet.end()!");
     255     2145006 :       CurNode = CurNode->getNext();
     256             :       return *this;
     257             :     }
     258             :     iterator operator++(int) { // Postincrement
     259             :       iterator tmp = *this; ++*this; return tmp;
     260             :     }
     261             :   };
     262             : 
     263             : private:
     264             :   // Can only be created by AliasSetTracker.
     265             :   AliasSet()
     266       88036 :       : PtrListEnd(&PtrList), RefCount(0),  AliasAny(false), Access(NoAccess),
     267      132054 :         Alias(SetMustAlias), Volatile(false) {}
     268             : 
     269             :   PointerRec *getSomePointer() const {
     270             :     return PtrList;
     271             :   }
     272             : 
     273             :   /// Return the real alias set this represents. If this has been merged with
     274             :   /// another set and is forwarding, return the ultimate destination set. This
     275             :   /// also implements the union-find collapsing as well.
     276      429946 :   AliasSet *getForwardedTarget(AliasSetTracker &AST) {
     277      429946 :     if (!Forward) return this;
     278             : 
     279       16391 :     AliasSet *Dest = Forward->getForwardedTarget(AST);
     280       16391 :     if (Dest != Forward) {
     281             :       Dest->addRef();
     282             :       Forward->dropRef(AST);
     283         424 :       Forward = Dest;
     284             :     }
     285             :     return Dest;
     286             :   }
     287             : 
     288             :   void removeFromTracker(AliasSetTracker &AST);
     289             : 
     290             :   void addPointer(AliasSetTracker &AST, PointerRec &Entry, LocationSize Size,
     291             :                   const AAMDNodes &AAInfo, bool KnownMustAlias = false);
     292             :   void addUnknownInst(Instruction *I, AliasAnalysis &AA);
     293             : 
     294             :   void removeUnknownInst(AliasSetTracker &AST, Instruction *I) {
     295             :     bool WasEmpty = UnknownInsts.empty();
     296             :     for (size_t i = 0, e = UnknownInsts.size(); i != e; ++i)
     297             :       if (UnknownInsts[i] == I) {
     298             :         UnknownInsts[i] = UnknownInsts.back();
     299             :         UnknownInsts.pop_back();
     300             :         --i; --e;  // Revisit the moved entry.
     301             :       }
     302             :     if (!WasEmpty && UnknownInsts.empty())
     303             :       dropRef(AST);
     304             :   }
     305             : 
     306         992 :   void setVolatile() { Volatile = true; }
     307             : 
     308             : public:
     309             :   /// Return true if the specified pointer "may" (or must) alias one of the
     310             :   /// members in the set.
     311             :   bool aliasesPointer(const Value *Ptr, LocationSize Size,
     312             :                       const AAMDNodes &AAInfo, AliasAnalysis &AA) const;
     313             :   bool aliasesUnknownInst(const Instruction *Inst, AliasAnalysis &AA) const;
     314             : };
     315             : 
     316             : inline raw_ostream& operator<<(raw_ostream &OS, const AliasSet &AS) {
     317             :   AS.print(OS);
     318             :   return OS;
     319             : }
     320             : 
     321             : class AliasSetTracker {
     322             :   /// A CallbackVH to arrange for AliasSetTracker to be notified whenever a
     323             :   /// Value is deleted.
     324     5417889 :   class ASTCallbackVH final : public CallbackVH {
     325             :     AliasSetTracker *AST;
     326             : 
     327             :     void deleted() override;
     328             :     void allUsesReplacedWith(Value *) override;
     329             : 
     330             :   public:
     331             :     ASTCallbackVH(Value *V, AliasSetTracker *AST = nullptr);
     332             : 
     333             :     ASTCallbackVH &operator=(Value *V);
     334             :   };
     335             :   /// Traits to tell DenseMap that tell us how to compare and hash the value
     336             :   /// handle.
     337             :   struct ASTCallbackVHDenseMapInfo : public DenseMapInfo<Value *> {};
     338             : 
     339             :   AliasAnalysis &AA;
     340             :   ilist<AliasSet> AliasSets;
     341             : 
     342             :   using PointerMapType = DenseMap<ASTCallbackVH, AliasSet::PointerRec *,
     343             :                                   ASTCallbackVHDenseMapInfo>;
     344             : 
     345             :   // Map from pointers to their node
     346             :   PointerMapType PointerMap;
     347             : 
     348             : public:
     349             :   /// Create an empty collection of AliasSets, and use the specified alias
     350             :   /// analysis object to disambiguate load and store addresses.
     351      129660 :   explicit AliasSetTracker(AliasAnalysis &aa) : AA(aa) {}
     352       87704 :   ~AliasSetTracker() { clear(); }
     353             : 
     354             :   /// These methods are used to add different types of instructions to the alias
     355             :   /// sets. Adding a new instruction can result in one of three actions
     356             :   /// happening:
     357             :   ///
     358             :   ///   1. If the instruction doesn't alias any other sets, create a new set.
     359             :   ///   2. If the instruction aliases exactly one set, add it to the set
     360             :   ///   3. If the instruction aliases multiple sets, merge the sets, and add
     361             :   ///      the instruction to the result.
     362             :   ///
     363             :   /// These methods return true if inserting the instruction resulted in the
     364             :   /// addition of a new alias set (i.e., the pointer did not alias anything).
     365             :   ///
     366             :   void add(Value *Ptr, LocationSize Size, const AAMDNodes &AAInfo); // Add a loc
     367             :   void add(LoadInst *LI);
     368             :   void add(StoreInst *SI);
     369             :   void add(VAArgInst *VAAI);
     370             :   void add(AnyMemSetInst *MSI);
     371             :   void add(AnyMemTransferInst *MTI);
     372             :   void add(Instruction *I);       // Dispatch to one of the other add methods...
     373             :   void add(BasicBlock &BB);       // Add all instructions in basic block
     374             :   void add(const AliasSetTracker &AST); // Add alias relations from another AST
     375             :   void addUnknown(Instruction *I);
     376             : 
     377             :   void clear();
     378             : 
     379             :   /// Return the alias sets that are active.
     380             :   const ilist<AliasSet> &getAliasSets() const { return AliasSets; }
     381             : 
     382             :   /// Return the alias set that the specified pointer lives in. If the New
     383             :   /// argument is non-null, this method sets the value to true if a new alias
     384             :   /// set is created to contain the pointer (because the pointer didn't alias
     385             :   /// anything).
     386             :   AliasSet &getAliasSetForPointer(Value *P, LocationSize Size,
     387             :                                   const AAMDNodes &AAInfo);
     388             : 
     389             :   /// Return the alias set containing the location specified if one exists,
     390             :   /// otherwise return null.
     391             :   AliasSet *getAliasSetForPointerIfExists(const Value *P, LocationSize Size,
     392             :                                           const AAMDNodes &AAInfo) {
     393             :     return mergeAliasSetsForPointer(P, Size, AAInfo);
     394             :   }
     395             : 
     396             :   /// Return true if the specified instruction "may" (or must) alias one of the
     397             :   /// members in any of the sets.
     398             :   bool containsUnknown(const Instruction *I) const;
     399             : 
     400             :   /// Return the underlying alias analysis object used by this tracker.
     401             :   AliasAnalysis &getAliasAnalysis() const { return AA; }
     402             : 
     403             :   /// This method is used to remove a pointer value from the AliasSetTracker
     404             :   /// entirely. It should be used when an instruction is deleted from the
     405             :   /// program to update the AST. If you don't use this, you would have dangling
     406             :   /// pointers to deleted instructions.
     407             :   void deleteValue(Value *PtrVal);
     408             : 
     409             :   /// This method should be used whenever a preexisting value in the program is
     410             :   /// copied or cloned, introducing a new value.  Note that it is ok for clients
     411             :   /// that use this method to introduce the same value multiple times: if the
     412             :   /// tracker already knows about a value, it will ignore the request.
     413             :   void copyValue(Value *From, Value *To);
     414             : 
     415             :   using iterator = ilist<AliasSet>::iterator;
     416             :   using const_iterator = ilist<AliasSet>::const_iterator;
     417             : 
     418             :   const_iterator begin() const { return AliasSets.begin(); }
     419             :   const_iterator end()   const { return AliasSets.end(); }
     420             : 
     421             :   iterator begin() { return AliasSets.begin(); }
     422             :   iterator end()   { return AliasSets.end(); }
     423             : 
     424             :   void print(raw_ostream &OS) const;
     425             :   void dump() const;
     426             : 
     427             : private:
     428             :   friend class AliasSet;
     429             : 
     430             :   // The total number of pointers contained in all "may" alias sets.
     431             :   unsigned TotalMayAliasSetSize = 0;
     432             : 
     433             :   // A non-null value signifies this AST is saturated. A saturated AST lumps
     434             :   // all pointers into a single "May" set.
     435             :   AliasSet *AliasAnyAS = nullptr;
     436             : 
     437             :   void removeAliasSet(AliasSet *AS);
     438             : 
     439             :   /// Just like operator[] on the map, except that it creates an entry for the
     440             :   /// pointer if it doesn't already exist.
     441      593824 :   AliasSet::PointerRec &getEntryFor(Value *V) {
     442     1187648 :     AliasSet::PointerRec *&Entry = PointerMap[ASTCallbackVH(V, this)];
     443      593824 :     if (!Entry)
     444      345748 :       Entry = new AliasSet::PointerRec(V);
     445      593824 :     return *Entry;
     446             :   }
     447             : 
     448             :   AliasSet &addPointer(Value *P, LocationSize Size, const AAMDNodes &AAInfo,
     449             :                        AliasSet::AccessLattice E);
     450             :   AliasSet *mergeAliasSetsForPointer(const Value *Ptr, LocationSize Size,
     451             :                                      const AAMDNodes &AAInfo);
     452             : 
     453             :   /// Merge all alias sets into a single set that is considered to alias any
     454             :   /// pointer.
     455             :   AliasSet &mergeAllAliasSets();
     456             : 
     457             :   AliasSet *findAliasSetForUnknownInst(Instruction *Inst);
     458             : };
     459             : 
     460             : inline raw_ostream& operator<<(raw_ostream &OS, const AliasSetTracker &AST) {
     461             :   AST.print(OS);
     462             :   return OS;
     463             : }
     464             : 
     465             : } // end namespace llvm
     466             : 
     467             : #endif // LLVM_ANALYSIS_ALIASSETTRACKER_H

Generated by: LCOV version 1.13