LCOV - code coverage report
Current view: top level - include/llvm/Analysis - AliasSetTracker.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 45 71 63.4 %
Date: 2018-10-20 13:21:21 Functions: 6 24 25.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           0 : 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 = LocationSize::mapEmpty();
      56             :     AAMDNodes AAInfo;
      57             : 
      58             :     // Whether the size for this record has been set at all. This makes no
      59             :     // guarantees about the size being known.
      60             :     bool isSizeSet() const { return Size != LocationSize::mapEmpty(); }
      61             : 
      62             :   public:
      63             :     PointerRec(Value *V)
      64      236245 :       : Val(V), AAInfo(DenseMapInfo<AAMDNodes>::getEmptyKey()) {}
      65             : 
      66           0 :     Value *getValue() const { return Val; }
      67             : 
      68           0 :     PointerRec *getNext() const { return NextInList; }
      69           0 :     bool hasAliasSet() const { return AS != nullptr; }
      70             : 
      71             :     PointerRec** setPrevInList(PointerRec **PIL) {
      72       23820 :       PrevInList = PIL;
      73      236245 :       return &NextInList;
      74             :     }
      75             : 
      76      907090 :     bool updateSizeAndAAInfo(LocationSize NewSize, const AAMDNodes &NewAAInfo) {
      77             :       bool SizeChanged = false;
      78      907090 :       if (NewSize != Size) {
      79             :         LocationSize OldSize = Size;
      80      243109 :         Size = isSizeSet() ? Size.unionWith(NewSize) : NewSize;
      81             :         SizeChanged = OldSize != Size;
      82             :       }
      83             : 
      84             :       if (AAInfo == DenseMapInfo<AAMDNodes>::getEmptyKey())
      85             :         // We don't have a AAInfo yet. Set it to NewAAInfo.
      86      236245 :         AAInfo = NewAAInfo;
      87             :       else {
      88             :         AAMDNodes Intersection(AAInfo.intersect(NewAAInfo));
      89             :         if (!Intersection) {
      90             :           // NewAAInfo conflicts with AAInfo.
      91      586028 :           AAInfo = DenseMapInfo<AAMDNodes>::getTombstoneKey();
      92             :           return SizeChanged;
      93             :         }
      94       84817 :         AAInfo = Intersection;
      95             :       }
      96             :       return SizeChanged;
      97             :     }
      98             : 
      99           0 :     LocationSize getSize() const {
     100             :       assert(isSizeSet() && "Getting an unset size!");
     101           0 :       return Size;
     102             :     }
     103             : 
     104             :     /// Return the AAInfo, or null if there is no information or conflicting
     105             :     /// information.
     106             :     AAMDNodes getAAInfo() const {
     107             :       // If we have missing or conflicting AAInfo, return null.
     108             :       if (AAInfo == DenseMapInfo<AAMDNodes>::getEmptyKey() ||
     109             :           AAInfo == DenseMapInfo<AAMDNodes>::getTombstoneKey())
     110             :         return AAMDNodes();
     111     1057011 :       return AAInfo;
     112             :     }
     113             : 
     114           0 :     AliasSet *getAliasSet(AliasSetTracker &AST) {
     115             :       assert(AS && "No AliasSet yet!");
     116           0 :       if (AS->Forward) {
     117             :         AliasSet *OldAS = AS;
     118           0 :         AS = OldAS->getForwardedTarget(AST);
     119             :         AS->addRef();
     120             :         OldAS->dropRef(AST);
     121             :       }
     122           0 :       return AS;
     123             :     }
     124             : 
     125           0 :     void setAliasSet(AliasSet *as) {
     126             :       assert(!AS && "Already have an alias set!");
     127      236245 :       AS = as;
     128           0 :     }
     129             : 
     130      236127 :     void eraseFromList() {
     131      236127 :       if (NextInList) NextInList->PrevInList = PrevInList;
     132      236127 :       *PrevInList = NextInList;
     133      236127 :       if (AS->PtrListEnd == &NextInList) {
     134       48382 :         AS->PtrListEnd = PrevInList;
     135             :         assert(*AS->PtrListEnd == nullptr && "List not terminated right!");
     136             :       }
     137      236127 :       delete this;
     138      236127 :     }
     139             :   };
     140             : 
     141             :   // Doubly linked list of nodes.
     142             :   PointerRec *PtrList = nullptr;
     143             :   PointerRec **PtrListEnd;
     144             :   // Forwarding pointer.
     145             :   AliasSet *Forward = nullptr;
     146             : 
     147             :   /// All instructions without a specific address in this alias set.
     148             :   /// In rare cases this vector can have a null'ed out WeakVH
     149             :   /// instances (can happen if some other loop pass deletes an
     150             :   /// instruction in this list).
     151             :   std::vector<WeakVH> UnknownInsts;
     152             : 
     153             :   /// Number of nodes pointing to this AliasSet plus the number of AliasSets
     154             :   /// forwarding to it.
     155             :   unsigned RefCount : 27;
     156             : 
     157             :   // Signifies that this set should be considered to alias any pointer.
     158             :   // Use when the tracker holding this set is saturated.
     159             :   unsigned AliasAny : 1;
     160             : 
     161             :   /// The kinds of access this alias set models.
     162             :   ///
     163             :   /// We keep track of whether this alias set merely refers to the locations of
     164             :   /// memory (and not any particular access), whether it modifies or references
     165             :   /// the memory, or whether it does both. The lattice goes from "NoAccess" to
     166             :   /// either RefAccess or ModAccess, then to ModRefAccess as necessary.
     167             :   enum AccessLattice {
     168             :     NoAccess = 0,
     169             :     RefAccess = 1,
     170             :     ModAccess = 2,
     171             :     ModRefAccess = RefAccess | ModAccess
     172             :   };
     173             :   unsigned Access : 2;
     174             : 
     175             :   /// The kind of alias relationship between pointers of the set.
     176             :   ///
     177             :   /// These represent conservatively correct alias results between any members
     178             :   /// of the set. We represent these independently of the values of alias
     179             :   /// results in order to pack it into a single bit. Lattice goes from
     180             :   /// MustAlias to MayAlias.
     181             :   enum AliasLattice {
     182             :     SetMustAlias = 0, SetMayAlias = 1
     183             :   };
     184             :   unsigned Alias : 1;
     185             : 
     186             :   unsigned SetSize = 0;
     187             : 
     188      267062 :   void addRef() { ++RefCount; }
     189             : 
     190       21204 :   void dropRef(AliasSetTracker &AST) {
     191             :     assert(RefCount >= 1 && "Invalid reference count detected!");
     192       21345 :     if (--RefCount == 0)
     193          10 :       removeFromTracker(AST);
     194       21204 :   }
     195             : 
     196             :   Instruction *getUnknownInst(unsigned i) const {
     197             :     assert(i < UnknownInsts.size());
     198       70001 :     return cast_or_null<Instruction>(UnknownInsts[i]);
     199             :   }
     200             : 
     201             : public:
     202             :   AliasSet(const AliasSet &) = delete;
     203             :   AliasSet &operator=(const AliasSet &) = delete;
     204             : 
     205             :   /// Accessors...
     206      210616 :   bool isRef() const { return Access & RefAccess; }
     207      203517 :   bool isMod() const { return Access & ModAccess; }
     208      280908 :   bool isMustAlias() const { return Alias == SetMustAlias; }
     209             :   bool isMayAlias()  const { return Alias == SetMayAlias; }
     210             : 
     211             :   /// Return true if this alias set should be ignored as part of the
     212             :   /// AliasSetTracker object.
     213           0 :   bool isForwardingAliasSet() const { return Forward; }
     214             : 
     215             :   /// Merge the specified alias set into this alias set.
     216             :   void mergeSetIn(AliasSet &AS, AliasSetTracker &AST);
     217             : 
     218             :   // Alias Set iteration - Allow access to all of the pointers which are part of
     219             :   // this alias set.
     220             :   class iterator;
     221           0 :   iterator begin() const { return iterator(PtrList); }
     222           0 :   iterator end()   const { return iterator(); }
     223           0 :   bool empty() const { return PtrList == nullptr; }
     224             : 
     225             :   // Unfortunately, ilist::size() is linear, so we have to add code to keep
     226             :   // track of the list's exact size.
     227           0 :   unsigned size() { return SetSize; }
     228             : 
     229             :   /// If this alias set is known to contain a single instruction and *only* a
     230             :   /// single unique instruction, return it.  Otherwise, return nullptr.
     231             :   Instruction* getUniqueInstruction();
     232             : 
     233             :   void print(raw_ostream &OS) const;
     234             :   void dump() const;
     235             : 
     236             :   /// Define an iterator for alias sets... this is just a forward iterator.
     237             :   class iterator : public std::iterator<std::forward_iterator_tag,
     238             :                                         PointerRec, ptrdiff_t> {
     239             :     PointerRec *CurNode;
     240             : 
     241             :   public:
     242             :     explicit iterator(PointerRec *CN = nullptr) : CurNode(CN) {}
     243             : 
     244           0 :     bool operator==(const iterator& x) const {
     245           0 :       return CurNode == x.CurNode;
     246             :     }
     247             :     bool operator!=(const iterator& x) const { return !operator==(x); }
     248             : 
     249           0 :     value_type &operator*() const {
     250             :       assert(CurNode && "Dereferencing AliasSet.end()!");
     251           0 :       return *CurNode;
     252             :     }
     253             :     value_type *operator->() const { return &operator*(); }
     254             : 
     255     3598584 :     Value *getPointer() const { return CurNode->getValue(); }
     256           0 :     LocationSize getSize() const { return CurNode->getSize(); }
     257           0 :     AAMDNodes getAAInfo() const { return CurNode->getAAInfo(); }
     258             : 
     259             :     iterator& operator++() {                // Preincrement
     260             :       assert(CurNode && "Advancing past AliasSet.end()!");
     261     3495723 :       CurNode = CurNode->getNext();
     262             :       return *this;
     263             :     }
     264             :     iterator operator++(int) { // Postincrement
     265             :       iterator tmp = *this; ++*this; return tmp;
     266             :     }
     267             :   };
     268             : 
     269             : private:
     270             :   // Can only be created by AliasSetTracker.
     271             :   AliasSet()
     272      109772 :       : PtrListEnd(&PtrList), RefCount(0),  AliasAny(false), Access(NoAccess),
     273      109772 :         Alias(SetMustAlias) {}
     274             : 
     275           0 :   PointerRec *getSomePointer() const {
     276           0 :     return PtrList;
     277             :   }
     278             : 
     279             :   /// Return the real alias set this represents. If this has been merged with
     280             :   /// another set and is forwarding, return the ultimate destination set. This
     281             :   /// also implements the union-find collapsing as well.
     282      648218 :   AliasSet *getForwardedTarget(AliasSetTracker &AST) {
     283      648218 :     if (!Forward) return this;
     284             : 
     285       22543 :     AliasSet *Dest = Forward->getForwardedTarget(AST);
     286       22543 :     if (Dest != Forward) {
     287             :       Dest->addRef();
     288             :       Forward->dropRef(AST);
     289           8 :       Forward = Dest;
     290             :     }
     291             :     return Dest;
     292             :   }
     293             : 
     294             :   void removeFromTracker(AliasSetTracker &AST);
     295             : 
     296             :   void addPointer(AliasSetTracker &AST, PointerRec &Entry, LocationSize Size,
     297             :                   const AAMDNodes &AAInfo, bool KnownMustAlias = false);
     298             :   void addUnknownInst(Instruction *I, AliasAnalysis &AA);
     299             : 
     300             :   void removeUnknownInst(AliasSetTracker &AST, Instruction *I) {
     301             :     bool WasEmpty = UnknownInsts.empty();
     302             :     for (size_t i = 0, e = UnknownInsts.size(); i != e; ++i)
     303             :       if (UnknownInsts[i] == I) {
     304             :         UnknownInsts[i] = UnknownInsts.back();
     305             :         UnknownInsts.pop_back();
     306             :         --i; --e;  // Revisit the moved entry.
     307             :       }
     308             :     if (!WasEmpty && UnknownInsts.empty())
     309             :       dropRef(AST);
     310             :   }
     311             : 
     312             : public:
     313             :   /// Return true if the specified pointer "may" (or must) alias one of the
     314             :   /// members in the set.
     315             :   bool aliasesPointer(const Value *Ptr, LocationSize Size,
     316             :                       const AAMDNodes &AAInfo, AliasAnalysis &AA) const;
     317             :   bool aliasesUnknownInst(const Instruction *Inst, AliasAnalysis &AA) const;
     318             : };
     319             : 
     320             : inline raw_ostream& operator<<(raw_ostream &OS, const AliasSet &AS) {
     321             :   AS.print(OS);
     322             :   return OS;
     323             : }
     324             : 
     325             : class AliasSetTracker {
     326             :   /// A CallbackVH to arrange for AliasSetTracker to be notified whenever a
     327             :   /// Value is deleted.
     328     5201627 :   class ASTCallbackVH final : public CallbackVH {
     329             :     AliasSetTracker *AST;
     330             : 
     331             :     void deleted() override;
     332             :     void allUsesReplacedWith(Value *) override;
     333             : 
     334             :   public:
     335             :     ASTCallbackVH(Value *V, AliasSetTracker *AST = nullptr);
     336             : 
     337             :     ASTCallbackVH &operator=(Value *V);
     338             :   };
     339             :   /// Traits to tell DenseMap that tell us how to compare and hash the value
     340             :   /// handle.
     341             :   struct ASTCallbackVHDenseMapInfo : public DenseMapInfo<Value *> {};
     342             : 
     343             :   AliasAnalysis &AA;
     344             :   ilist<AliasSet> AliasSets;
     345             : 
     346             :   using PointerMapType = DenseMap<ASTCallbackVH, AliasSet::PointerRec *,
     347             :                                   ASTCallbackVHDenseMapInfo>;
     348             : 
     349             :   // Map from pointers to their node
     350             :   PointerMapType PointerMap;
     351             : 
     352             : public:
     353             :   /// Create an empty collection of AliasSets, and use the specified alias
     354             :   /// analysis object to disambiguate load and store addresses.
     355       93141 :   explicit AliasSetTracker(AliasAnalysis &aa) : AA(aa) {}
     356       47596 :   ~AliasSetTracker() { clear(); }
     357             : 
     358             :   /// These methods are used to add different types of instructions to the alias
     359             :   /// sets. Adding a new instruction can result in one of three actions
     360             :   /// happening:
     361             :   ///
     362             :   ///   1. If the instruction doesn't alias any other sets, create a new set.
     363             :   ///   2. If the instruction aliases exactly one set, add it to the set
     364             :   ///   3. If the instruction aliases multiple sets, merge the sets, and add
     365             :   ///      the instruction to the result.
     366             :   ///
     367             :   /// These methods return true if inserting the instruction resulted in the
     368             :   /// addition of a new alias set (i.e., the pointer did not alias anything).
     369             :   ///
     370             :   void add(Value *Ptr, LocationSize Size, const AAMDNodes &AAInfo); // Add a loc
     371             :   void add(LoadInst *LI);
     372             :   void add(StoreInst *SI);
     373             :   void add(VAArgInst *VAAI);
     374             :   void add(AnyMemSetInst *MSI);
     375             :   void add(AnyMemTransferInst *MTI);
     376             :   void add(Instruction *I);       // Dispatch to one of the other add methods...
     377             :   void add(BasicBlock &BB);       // Add all instructions in basic block
     378             :   void add(const AliasSetTracker &AST); // Add alias relations from another AST
     379             :   void addUnknown(Instruction *I);
     380             : 
     381             :   void clear();
     382             : 
     383             :   /// Return the alias sets that are active.
     384             :   const ilist<AliasSet> &getAliasSets() const { return AliasSets; }
     385             : 
     386             :   /// Return the alias set which contains the specified memory location.  If
     387             :   /// the memory location aliases two or more existing alias sets, will have
     388             :   /// the effect of merging those alias sets before the single resulting alias
     389             :   /// set is returned.
     390             :   AliasSet &getAliasSetFor(const MemoryLocation &MemLoc);
     391             : 
     392             :   /// Return true if the specified instruction "may" (or must) alias one of the
     393             :   /// members in any of the sets.
     394             :   bool containsUnknown(const Instruction *I) const;
     395             : 
     396             :   /// Return the underlying alias analysis object used by this tracker.
     397           0 :   AliasAnalysis &getAliasAnalysis() const { return AA; }
     398             : 
     399             :   /// This method is used to remove a pointer value from the AliasSetTracker
     400             :   /// entirely. It should be used when an instruction is deleted from the
     401             :   /// program to update the AST. If you don't use this, you would have dangling
     402             :   /// pointers to deleted instructions.
     403             :   void deleteValue(Value *PtrVal);
     404             : 
     405             :   /// This method should be used whenever a preexisting value in the program is
     406             :   /// copied or cloned, introducing a new value.  Note that it is ok for clients
     407             :   /// that use this method to introduce the same value multiple times: if the
     408             :   /// tracker already knows about a value, it will ignore the request.
     409             :   void copyValue(Value *From, Value *To);
     410             : 
     411             :   using iterator = ilist<AliasSet>::iterator;
     412             :   using const_iterator = ilist<AliasSet>::const_iterator;
     413             : 
     414             :   const_iterator begin() const { return AliasSets.begin(); }
     415             :   const_iterator end()   const { return AliasSets.end(); }
     416             : 
     417             :   iterator begin() { return AliasSets.begin(); }
     418             :   iterator end()   { return AliasSets.end(); }
     419             : 
     420             :   void print(raw_ostream &OS) const;
     421             :   void dump() const;
     422             : 
     423             : private:
     424             :   friend class AliasSet;
     425             : 
     426             :   // The total number of pointers contained in all "may" alias sets.
     427             :   unsigned TotalMayAliasSetSize = 0;
     428             : 
     429             :   // A non-null value signifies this AST is saturated. A saturated AST lumps
     430             :   // all pointers into a single "May" set.
     431             :   AliasSet *AliasAnyAS = nullptr;
     432             : 
     433             :   void removeAliasSet(AliasSet *AS);
     434             : 
     435             :   /// Just like operator[] on the map, except that it creates an entry for the
     436             :   /// pointer if it doesn't already exist.
     437      906119 :   AliasSet::PointerRec &getEntryFor(Value *V) {
     438      906119 :     AliasSet::PointerRec *&Entry = PointerMap[ASTCallbackVH(V, this)];
     439      906119 :     if (!Entry)
     440      236245 :       Entry = new AliasSet::PointerRec(V);
     441      906119 :     return *Entry;
     442             :   }
     443             : 
     444             :   AliasSet &addPointer(Value *P, LocationSize Size, const AAMDNodes &AAInfo,
     445             :                        AliasSet::AccessLattice E);
     446             :   AliasSet &addPointer(MemoryLocation Loc,
     447             :                        AliasSet::AccessLattice E) {
     448      466088 :     return addPointer(const_cast<Value*>(Loc.Ptr), Loc.Size, Loc.AATags, E);
     449             :   }
     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