LCOV - code coverage report
Current view: top level - include/llvm/Analysis - AliasSetTracker.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 73 73 100.0 %
Date: 2017-09-14 15:23:50 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 MemSetInst;
      41             : class MemTransferInst;
      42             : class raw_ostream;
      43             : class StoreInst;
      44             : class VAArgInst;
      45             : class Value;
      46             : 
      47       38691 : 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             :     uint64_t Size = 0;
      56             :     AAMDNodes AAInfo;
      57             : 
      58             :   public:
      59             :     PointerRec(Value *V)
      60      156451 :       : 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      171159 :       PrevInList = PIL;
      69      156451 :       return &NextInList;
      70             :     }
      71             : 
      72      538855 :     bool updateSizeAndAAInfo(uint64_t NewSize, const AAMDNodes &NewAAInfo) {
      73      538855 :       bool SizeChanged = false;
      74      538855 :       if (NewSize > Size) {
      75      156612 :         Size = NewSize;
      76      156612 :         SizeChanged = true;
      77             :       }
      78             : 
      79     1077710 :       if (AAInfo == DenseMapInfo<AAMDNodes>::getEmptyKey())
      80             :         // We don't have a AAInfo yet. Set it to NewAAInfo.
      81      156451 :         AAInfo = NewAAInfo;
      82             :       else {
      83      764808 :         AAMDNodes Intersection(AAInfo.intersect(NewAAInfo));
      84      335405 :         if (!Intersection) {
      85             :           // NewAAInfo conflicts with AAInfo.
      86      335405 :           AAInfo = DenseMapInfo<AAMDNodes>::getTombstoneKey();
      87      335405 :           return SizeChanged;
      88             :         }
      89       46999 :         AAInfo = Intersection;
      90             :       }
      91             :       return SizeChanged;
      92             :     }
      93             : 
      94             :     uint64_t 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     4258054 :       if (AAInfo == DenseMapInfo<AAMDNodes>::getEmptyKey() ||
     101     2849784 :           AAInfo == DenseMapInfo<AAMDNodes>::getTombstoneKey())
     102             :         return AAMDNodes();
     103      720757 :       return AAInfo;
     104             :     }
     105             : 
     106      362036 :     AliasSet *getAliasSet(AliasSetTracker &AST) {
     107             :       assert(AS && "No AliasSet yet!");
     108      362036 :       if (AS->Forward) {
     109       13453 :         AliasSet *OldAS = AS;
     110       13453 :         AS = OldAS->getForwardedTarget(AST);
     111       26906 :         AS->addRef();
     112             :         OldAS->dropRef(AST);
     113             :       }
     114      362036 :       return AS;
     115             :     }
     116             : 
     117             :     void setAliasSet(AliasSet *as) {
     118             :       assert(!AS && "Already have an alias set!");
     119      156451 :       AS = as;
     120             :     }
     121             : 
     122      156333 :     void eraseFromList() {
     123      156333 :       if (NextInList) NextInList->PrevInList = PrevInList;
     124      156333 :       *PrevInList = NextInList;
     125      156333 :       if (AS->PtrListEnd == &NextInList) {
     126       36320 :         AS->PtrListEnd = PrevInList;
     127             :         assert(*AS->PtrListEnd == nullptr && "List not terminated right!");
     128             :       }
     129      156333 :       delete this;
     130      156333 :     }
     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      192071 :   void addRef() { ++RefCount; }
     184             : 
     185       12985 :   void dropRef(AliasSetTracker &AST) {
     186             :     assert(RefCount >= 1 && "Invalid reference count detected!");
     187       28135 :     if (--RefCount == 0)
     188       12990 :       removeFromTracker(AST);
     189       12985 :   }
     190             : 
     191             :   Instruction *getUnknownInst(unsigned i) const {
     192             :     assert(i < UnknownInsts.size());
     193      493998 :     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      133250 :   bool isMod() const { return Access & ModAccess; }
     203      193222 :   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        8342 :   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      160868 :   iterator begin() const { return iterator(PtrList); }
     220      157892 :   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     2065936 :       return CurNode == x.CurNode;
     240             :     }
     241     2115335 :     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        2923 :     value_type *operator->() const { return &operator*(); }
     248             : 
     249     2010244 :     Value *getPointer() const { return CurNode->getValue(); }
     250     2010244 :     uint64_t getSize() const { return CurNode->getSize(); }
     251     4020382 :     AAMDNodes getAAInfo() const { return CurNode->getAAInfo(); }
     252             : 
     253             :     iterator& operator++() {                // Preincrement
     254             :       assert(CurNode && "Advancing past AliasSet.end()!");
     255     1957390 :       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       77598 :       : PtrListEnd(&PtrList), RefCount(0),  AliasAny(false), Access(NoAccess),
     267      155196 :         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      389104 :   AliasSet *getForwardedTarget(AliasSetTracker &AST) {
     277      389104 :     if (!Forward) return this;
     278             : 
     279       13751 :     AliasSet *Dest = Forward->getForwardedTarget(AST);
     280       13751 :     if (Dest != Forward) {
     281         298 :       Dest->addRef();
     282         596 :       Forward->dropRef(AST);
     283         298 :       Forward = Dest;
     284             :     }
     285             :     return Dest;
     286             :   }
     287             : 
     288             :   void removeFromTracker(AliasSetTracker &AST);
     289             : 
     290             :   void addPointer(AliasSetTracker &AST, PointerRec &Entry, uint64_t Size,
     291             :                   const AAMDNodes &AAInfo,
     292             :                   bool KnownMustAlias = false);
     293             :   void addUnknownInst(Instruction *I, AliasAnalysis &AA);
     294             : 
     295             :   void removeUnknownInst(AliasSetTracker &AST, Instruction *I) {
     296             :     bool WasEmpty = UnknownInsts.empty();
     297             :     for (size_t i = 0, e = UnknownInsts.size(); i != e; ++i)
     298             :       if (UnknownInsts[i] == I) {
     299             :         UnknownInsts[i] = UnknownInsts.back();
     300             :         UnknownInsts.pop_back();
     301             :         --i; --e;  // Revisit the moved entry.
     302             :       }
     303             :     if (!WasEmpty && UnknownInsts.empty())
     304             :       dropRef(AST);
     305             :   }
     306             : 
     307        1038 :   void setVolatile() { Volatile = true; }
     308             : 
     309             : public:
     310             :   /// Return true if the specified pointer "may" (or must) alias one of the
     311             :   /// members in the set.
     312             :   bool aliasesPointer(const Value *Ptr, uint64_t Size, const AAMDNodes &AAInfo,
     313             :                       AliasAnalysis &AA) const;
     314             :   bool aliasesUnknownInst(const Instruction *Inst, AliasAnalysis &AA) const;
     315             : };
     316             : 
     317             : inline raw_ostream& operator<<(raw_ostream &OS, const AliasSet &AS) {
     318             :   AS.print(OS);
     319             :   return OS;
     320             : }
     321             : 
     322             : class AliasSetTracker {
     323             :   /// A CallbackVH to arrange for AliasSetTracker to be notified whenever a
     324             :   /// Value is deleted.
     325    10383636 :   class ASTCallbackVH final : public CallbackVH {
     326             :     AliasSetTracker *AST;
     327             : 
     328             :     void deleted() override;
     329             :     void allUsesReplacedWith(Value *) override;
     330             : 
     331             :   public:
     332             :     ASTCallbackVH(Value *V, AliasSetTracker *AST = nullptr);
     333             : 
     334             :     ASTCallbackVH &operator=(Value *V);
     335             :   };
     336             :   /// Traits to tell DenseMap that tell us how to compare and hash the value
     337             :   /// handle.
     338             :   struct ASTCallbackVHDenseMapInfo : public DenseMapInfo<Value *> {};
     339             : 
     340             :   AliasAnalysis &AA;
     341             :   ilist<AliasSet> AliasSets;
     342             : 
     343             :   using PointerMapType = DenseMap<ASTCallbackVH, AliasSet::PointerRec *,
     344             :                                   ASTCallbackVHDenseMapInfo>;
     345             : 
     346             :   // Map from pointers to their node
     347             :   PointerMapType PointerMap;
     348             : 
     349             : public:
     350             :   /// Create an empty collection of AliasSets, and use the specified alias
     351             :   /// analysis object to disambiguate load and store addresses.
     352      123177 :   explicit AliasSetTracker(AliasAnalysis &aa) : AA(aa) {}
     353      122721 :   ~AliasSetTracker() { clear(); }
     354             : 
     355             :   /// These methods are used to add different types of instructions to the alias
     356             :   /// sets. Adding a new instruction can result in one of three actions
     357             :   /// happening:
     358             :   ///
     359             :   ///   1. If the instruction doesn't alias any other sets, create a new set.
     360             :   ///   2. If the instruction aliases exactly one set, add it to the set
     361             :   ///   3. If the instruction aliases multiple sets, merge the sets, and add
     362             :   ///      the instruction to the result.
     363             :   ///
     364             :   /// These methods return true if inserting the instruction resulted in the
     365             :   /// addition of a new alias set (i.e., the pointer did not alias anything).
     366             :   ///
     367             :   void add(Value *Ptr, uint64_t Size, const AAMDNodes &AAInfo); // Add a loc.
     368             :   void add(LoadInst *LI);
     369             :   void add(StoreInst *SI);
     370             :   void add(VAArgInst *VAAI);
     371             :   void add(MemSetInst *MSI);
     372             :   void add(MemTransferInst *MTI);
     373             :   void add(Instruction *I);       // Dispatch to one of the other add methods...
     374             :   void add(BasicBlock &BB);       // Add all instructions in basic block
     375             :   void add(const AliasSetTracker &AST); // Add alias relations from another AST
     376             :   void addUnknown(Instruction *I);
     377             : 
     378             :   void clear();
     379             : 
     380             :   /// Return the alias sets that are active.
     381             :   const ilist<AliasSet> &getAliasSets() const { return AliasSets; }
     382             : 
     383             :   /// Return the alias set that the specified pointer lives in. If the New
     384             :   /// argument is non-null, this method sets the value to true if a new alias
     385             :   /// set is created to contain the pointer (because the pointer didn't alias
     386             :   /// anything).
     387             :   AliasSet &getAliasSetForPointer(Value *P, uint64_t Size,
     388             :                                   const AAMDNodes &AAInfo);
     389             : 
     390             :   /// Return the alias set containing the location specified if one exists,
     391             :   /// otherwise return null.
     392             :   AliasSet *getAliasSetForPointerIfExists(const Value *P, uint64_t Size,
     393             :                                           const AAMDNodes &AAInfo) {
     394             :     return mergeAliasSetsForPointer(P, Size, AAInfo);
     395             :   }
     396             : 
     397             :   /// Return true if the specified instruction "may" (or must) alias one of the
     398             :   /// members in any of the sets.
     399             :   bool containsUnknown(const Instruction *I) const;
     400             : 
     401             :   /// Return the underlying alias analysis object used by this tracker.
     402             :   AliasAnalysis &getAliasAnalysis() const { return AA; }
     403             : 
     404             :   /// This method is used to remove a pointer value from the AliasSetTracker
     405             :   /// entirely. It should be used when an instruction is deleted from the
     406             :   /// program to update the AST. If you don't use this, you would have dangling
     407             :   /// pointers to deleted instructions.
     408             :   void deleteValue(Value *PtrVal);
     409             : 
     410             :   /// This method should be used whenever a preexisting value in the program is
     411             :   /// copied or cloned, introducing a new value.  Note that it is ok for clients
     412             :   /// that use this method to introduce the same value multiple times: if the
     413             :   /// tracker already knows about a value, it will ignore the request.
     414             :   void copyValue(Value *From, Value *To);
     415             : 
     416             :   using iterator = ilist<AliasSet>::iterator;
     417             :   using const_iterator = ilist<AliasSet>::const_iterator;
     418             : 
     419       40618 :   const_iterator begin() const { return AliasSets.begin(); }
     420       40618 :   const_iterator end()   const { return AliasSets.end(); }
     421             : 
     422      497324 :   iterator begin() { return AliasSets.begin(); }
     423      497324 :   iterator end()   { return AliasSets.end(); }
     424             : 
     425             :   void print(raw_ostream &OS) const;
     426             :   void dump() const;
     427             : 
     428             : private:
     429             :   friend class AliasSet;
     430             : 
     431             :   // The total number of pointers contained in all "may" alias sets.
     432             :   unsigned TotalMayAliasSetSize = 0;
     433             : 
     434             :   // A non-null value signifies this AST is saturated. A saturated AST lumps
     435             :   // all pointers into a single "May" set.
     436             :   AliasSet *AliasAnyAS = nullptr;
     437             : 
     438             :   void removeAliasSet(AliasSet *AS);
     439             : 
     440             :   /// Just like operator[] on the map, except that it creates an entry for the
     441             :   /// pointer if it doesn't already exist.
     442      538475 :   AliasSet::PointerRec &getEntryFor(Value *V) {
     443     1615425 :     AliasSet::PointerRec *&Entry = PointerMap[ASTCallbackVH(V, this)];
     444      538475 :     if (!Entry)
     445      312902 :       Entry = new AliasSet::PointerRec(V);
     446      538475 :     return *Entry;
     447             :   }
     448             : 
     449             :   AliasSet &addPointer(Value *P, uint64_t Size, const AAMDNodes &AAInfo,
     450             :                        AliasSet::AccessLattice E);
     451             :   AliasSet *mergeAliasSetsForPointer(const Value *Ptr, uint64_t Size,
     452             :                                      const AAMDNodes &AAInfo);
     453             : 
     454             :   /// Merge all alias sets into a single set that is considered to alias any
     455             :   /// pointer.
     456             :   AliasSet &mergeAllAliasSets();
     457             : 
     458             :   AliasSet *findAliasSetForUnknownInst(Instruction *Inst);
     459             : };
     460             : 
     461             : inline raw_ostream& operator<<(raw_ostream &OS, const AliasSetTracker &AST) {
     462             :   AST.print(OS);
     463             :   return OS;
     464             : }
     465             : 
     466             : } // end namespace llvm
     467             : 
     468             : #endif // LLVM_ANALYSIS_ALIASSETTRACKER_H

Generated by: LCOV version 1.13