LCOV - code coverage report
Current view: top level - lib/Analysis - AliasSetTracker.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 282 298 94.6 %
Date: 2018-07-13 00:08:38 Functions: 36 40 90.0 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : //===- AliasSetTracker.cpp - Alias Sets Tracker 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             : //
      10             : // This file implements the AliasSetTracker and AliasSet classes.
      11             : //
      12             : //===----------------------------------------------------------------------===//
      13             : 
      14             : #include "llvm/Analysis/AliasSetTracker.h"
      15             : #include "llvm/Analysis/AliasAnalysis.h"
      16             : #include "llvm/Analysis/MemoryLocation.h"
      17             : #include "llvm/Config/llvm-config.h"
      18             : #include "llvm/IR/CallSite.h"
      19             : #include "llvm/IR/Constants.h"
      20             : #include "llvm/IR/DataLayout.h"
      21             : #include "llvm/IR/Function.h"
      22             : #include "llvm/IR/InstIterator.h"
      23             : #include "llvm/IR/Instruction.h"
      24             : #include "llvm/IR/Instructions.h"
      25             : #include "llvm/IR/IntrinsicInst.h"
      26             : #include "llvm/IR/Module.h"
      27             : #include "llvm/IR/Value.h"
      28             : #include "llvm/Pass.h"
      29             : #include "llvm/Support/AtomicOrdering.h"
      30             : #include "llvm/Support/Casting.h"
      31             : #include "llvm/Support/CommandLine.h"
      32             : #include "llvm/Support/Compiler.h"
      33             : #include "llvm/Support/Debug.h"
      34             : #include "llvm/Support/ErrorHandling.h"
      35             : #include "llvm/Support/raw_ostream.h"
      36             : #include <cassert>
      37             : #include <cstdint>
      38             : #include <vector>
      39             : 
      40             : using namespace llvm;
      41             : 
      42             : static cl::opt<unsigned>
      43       99743 :     SaturationThreshold("alias-set-saturation-threshold", cl::Hidden,
      44      199486 :                         cl::init(250),
      45       99743 :                         cl::desc("The maximum number of pointers may-alias "
      46       99743 :                                  "sets may contain before degradation"));
      47             : 
      48             : /// mergeSetIn - Merge the specified alias set into this alias set.
      49             : ///
      50       18695 : void AliasSet::mergeSetIn(AliasSet &AS, AliasSetTracker &AST) {
      51             :   assert(!AS.Forward && "Alias set is already forwarding!");
      52             :   assert(!Forward && "This set is a forwarding set!!");
      53             : 
      54       18695 :   bool WasMustAlias = (Alias == SetMustAlias);
      55             :   // Update the alias and access types of this set...
      56       18695 :   Access |= AS.Access;
      57       18695 :   Alias  |= AS.Alias;
      58       18695 :   Volatile |= AS.Volatile;
      59             : 
      60       18695 :   if (Alias == SetMustAlias) {
      61             :     // Check that these two merged sets really are must aliases.  Since both
      62             :     // used to be must-alias sets, we can just check any pointer from each set
      63             :     // for aliasing.
      64        2851 :     AliasAnalysis &AA = AST.getAliasAnalysis();
      65        2851 :     PointerRec *L = getSomePointer();
      66        2851 :     PointerRec *R = AS.getSomePointer();
      67             : 
      68             :     // If the pointers are not a must-alias pair, this set becomes a may alias.
      69        8553 :     if (AA.alias(MemoryLocation(L->getValue(), L->getSize(), L->getAAInfo()),
      70        5702 :                  MemoryLocation(R->getValue(), R->getSize(), R->getAAInfo())) !=
      71             :         MustAlias)
      72        2851 :       Alias = SetMayAlias;
      73             :   }
      74             : 
      75       18695 :   if (Alias == SetMayAlias) {
      76       18695 :     if (WasMustAlias)
      77        3724 :       AST.TotalMayAliasSetSize += size();
      78       18695 :     if (AS.Alias == SetMustAlias)
      79       16157 :       AST.TotalMayAliasSetSize += AS.size();
      80             :   }
      81             : 
      82             :   bool ASHadUnknownInsts = !AS.UnknownInsts.empty();
      83       18695 :   if (UnknownInsts.empty()) {            // Merge call sites...
      84       15776 :     if (ASHadUnknownInsts) {
      85             :       std::swap(UnknownInsts, AS.UnknownInsts);
      86             :       addRef();
      87             :     }
      88        2919 :   } else if (ASHadUnknownInsts) {
      89        1284 :     UnknownInsts.insert(UnknownInsts.end(), AS.UnknownInsts.begin(), AS.UnknownInsts.end());
      90             :     AS.UnknownInsts.clear();
      91             :   }
      92             : 
      93       18695 :   AS.Forward = this; // Forward across AS now...
      94             :   addRef();          // AS is now pointing to us...
      95             : 
      96             :   // Merge the list of constituent pointers...
      97       18695 :   if (AS.PtrList) {
      98       17778 :     SetSize += AS.size();
      99       17778 :     AS.SetSize = 0;
     100       17778 :     *PtrListEnd = AS.PtrList;
     101       17778 :     AS.PtrList->setPrevInList(PtrListEnd);
     102       17778 :     PtrListEnd = AS.PtrListEnd;
     103             : 
     104       17778 :     AS.PtrList = nullptr;
     105       17778 :     AS.PtrListEnd = &AS.PtrList;
     106             :     assert(*AS.PtrListEnd == nullptr && "End of list is not null?");
     107             :   }
     108       18695 :   if (ASHadUnknownInsts)
     109             :     AS.dropRef(AST);
     110       18695 : }
     111             : 
     112       14955 : void AliasSetTracker::removeAliasSet(AliasSet *AS) {
     113       14955 :   if (AliasSet *Fwd = AS->Forward) {
     114       14946 :     Fwd->dropRef(*this);
     115       14946 :     AS->Forward = nullptr;
     116             :   }
     117             : 
     118       14955 :   if (AS->Alias == AliasSet::SetMayAlias)
     119        1476 :     TotalMayAliasSetSize -= AS->size();
     120             : 
     121             :   AliasSets.erase(AS);
     122       14955 : }
     123             : 
     124       14955 : void AliasSet::removeFromTracker(AliasSetTracker &AST) {
     125             :   assert(RefCount == 0 && "Cannot remove non-dead alias set from tracker!");
     126       14955 :   AST.removeAliasSet(this);
     127       14955 : }
     128             : 
     129      172874 : void AliasSet::addPointer(AliasSetTracker &AST, PointerRec &Entry,
     130             :                           LocationSize Size, const AAMDNodes &AAInfo,
     131             :                           bool KnownMustAlias) {
     132             :   assert(!Entry.hasAliasSet() && "Entry already in set!");
     133             : 
     134             :   // Check to see if we have to downgrade to _may_ alias.
     135      172874 :   if (isMustAlias() && !KnownMustAlias)
     136       47305 :     if (PointerRec *P = getSomePointer()) {
     137        6169 :       AliasAnalysis &AA = AST.getAliasAnalysis();
     138             :       AliasResult Result =
     139       12338 :           AA.alias(MemoryLocation(P->getValue(), P->getSize(), P->getAAInfo()),
     140       18507 :                    MemoryLocation(Entry.getValue(), Size, AAInfo));
     141        6169 :       if (Result != MustAlias) {
     142        5789 :         Alias = SetMayAlias;
     143        5789 :         AST.TotalMayAliasSetSize += size();
     144             :       } else {
     145             :         // First entry of must alias must have maximum size!        
     146         380 :         P->updateSizeAndAAInfo(Size, AAInfo);
     147             :       }
     148             :       assert(Result != NoAlias && "Cannot be part of must set!");
     149             :     }
     150             : 
     151             :   Entry.setAliasSet(this);
     152      172874 :   Entry.updateSizeAndAAInfo(Size, AAInfo);
     153             : 
     154             :   // Add it to the end of the list...
     155      172874 :   ++SetSize;
     156             :   assert(*PtrListEnd == nullptr && "End of list is not null?");
     157      172874 :   *PtrListEnd = &Entry;
     158      172874 :   PtrListEnd = Entry.setPrevInList(PtrListEnd);
     159             :   assert(*PtrListEnd == nullptr && "End of list is not null?");
     160             :   // Entry points to alias set.
     161             :   addRef();
     162             : 
     163      172874 :   if (Alias == SetMayAlias)
     164      131344 :     AST.TotalMayAliasSetSize++;
     165      172874 : }
     166             : 
     167       88182 : void AliasSet::addUnknownInst(Instruction *I, AliasAnalysis &AA) {
     168       88182 :   if (UnknownInsts.empty())
     169             :     addRef();
     170       88182 :   UnknownInsts.emplace_back(I);
     171             : 
     172       88182 :   if (!I->mayWriteToMemory()) {
     173        1108 :     Alias = SetMayAlias;
     174        1108 :     Access |= RefAccess;
     175        1108 :     return;
     176             :   }
     177             : 
     178             :   // FIXME: This should use mod/ref information to make this not suck so bad
     179       87074 :   Alias = SetMayAlias;
     180       87074 :   Access = ModRefAccess;
     181             : }
     182             : 
     183             : /// aliasesPointer - Return true if the specified pointer "may" (or must)
     184             : /// alias one of the members in the set.
     185             : ///
     186      259112 : bool AliasSet::aliasesPointer(const Value *Ptr, LocationSize Size,
     187             :                               const AAMDNodes &AAInfo,
     188             :                               AliasAnalysis &AA) const {
     189      259112 :   if (AliasAny)
     190             :     return true;
     191             : 
     192      259112 :   if (Alias == SetMustAlias) {
     193             :     assert(UnknownInsts.empty() && "Illegal must alias set!");
     194             : 
     195             :     // If this is a set of MustAliases, only check to see if the pointer aliases
     196             :     // SOME value in the set.
     197      122508 :     PointerRec *SomePtr = getSomePointer();
     198             :     assert(SomePtr && "Empty must-alias set??");
     199      367524 :     return AA.alias(MemoryLocation(SomePtr->getValue(), SomePtr->getSize(),
     200             :                                    SomePtr->getAAInfo()),
     201      245016 :                     MemoryLocation(Ptr, Size, AAInfo));
     202             :   }
     203             : 
     204             :   // If this is a may-alias set, we have to check all of the pointers in the set
     205             :   // to be sure it doesn't alias the set...
     206     2347690 :   for (iterator I = begin(), E = end(); I != E; ++I)
     207     4320992 :     if (AA.alias(MemoryLocation(Ptr, Size, AAInfo),
     208     4320992 :                  MemoryLocation(I.getPointer(), I.getSize(), I.getAAInfo())))
     209       86014 :       return true;
     210             : 
     211             :   // Check the unknown instructions...
     212       50590 :   if (!UnknownInsts.empty()) {
     213       80367 :     for (unsigned i = 0, e = UnknownInsts.size(); i != e; ++i)
     214             :       if (auto *Inst = getUnknownInst(i))
     215       73976 :         if (isModOrRefSet(
     216             :                 AA.getModRefInfo(Inst, MemoryLocation(Ptr, Size, AAInfo))))
     217             :           return true;
     218             :   }
     219             : 
     220             :   return false;
     221             : }
     222             : 
     223      106098 : bool AliasSet::aliasesUnknownInst(const Instruction *Inst,
     224             :                                   AliasAnalysis &AA) const {
     225             : 
     226      106098 :   if (AliasAny)
     227             :     return true;
     228             : 
     229      103754 :   if (!Inst->mayReadOrWriteMemory())
     230             :     return false;
     231             : 
     232      228636 :   for (unsigned i = 0, e = UnknownInsts.size(); i != e; ++i) {
     233             :     if (auto *UnknownInst = getUnknownInst(i)) {
     234             :       ImmutableCallSite C1(UnknownInst), C2(Inst);
     235      223029 :       if (!C1 || !C2 || isModOrRefSet(AA.getModRefInfo(C1, C2)) ||
     236       21132 :           isModOrRefSet(AA.getModRefInfo(C2, C1)))
     237             :         return true;
     238             :     }
     239             :   }
     240             : 
     241       62463 :   for (iterator I = begin(), E = end(); I != E; ++I)
     242       58028 :     if (isModOrRefSet(AA.getModRefInfo(
     243       58028 :             Inst, MemoryLocation(I.getPointer(), I.getSize(), I.getAAInfo()))))
     244       14401 :       return true;
     245             : 
     246        9524 :   return false;
     247             : }
     248             : 
     249       43852 : void AliasSetTracker::clear() {
     250             :   // Delete all the PointerRec entries.
     251       43852 :   for (PointerMapType::iterator I = PointerMap.begin(), E = PointerMap.end();
     252      216535 :        I != E; ++I)
     253      172683 :     I->second->eraseFromList();
     254             :   
     255       43852 :   PointerMap.clear();
     256             :   
     257             :   // The alias sets should all be clear now.
     258             :   AliasSets.clear();
     259       43852 : }
     260             : 
     261             : 
     262             : /// mergeAliasSetsForPointer - Given a pointer, merge all alias sets that may
     263             : /// alias the pointer. Return the unified set, or nullptr if no set that aliases
     264             : /// the pointer was found.
     265      171976 : AliasSet *AliasSetTracker::mergeAliasSetsForPointer(const Value *Ptr,
     266             :                                                     LocationSize Size,
     267             :                                                     const AAMDNodes &AAInfo) {
     268             :   AliasSet *FoundSet = nullptr;
     269      673510 :   for (iterator I = begin(), E = end(); I != E;) {
     270             :     iterator Cur = I++;
     271      501534 :     if (Cur->Forward || !Cur->aliasesPointer(Ptr, Size, AAInfo, AA)) continue;
     272             :     
     273      138263 :     if (!FoundSet) {      // If this is the first alias set ptr can go into.
     274             :       FoundSet = &*Cur;   // Remember it.
     275             :     } else {              // Otherwise, we must merge the sets.
     276        7423 :       FoundSet->mergeSetIn(*Cur, *this);     // Merge in contents.
     277             :     }
     278             :   }
     279             : 
     280      171976 :   return FoundSet;
     281             : }
     282             : 
     283           0 : bool AliasSetTracker::containsUnknown(const Instruction *Inst) const {
     284           0 :   for (const AliasSet &AS : *this)
     285           0 :     if (!AS.Forward && AS.aliasesUnknownInst(Inst, AA))
     286             :       return true;
     287             :   return false;
     288             : }
     289             : 
     290       88182 : AliasSet *AliasSetTracker::findAliasSetForUnknownInst(Instruction *Inst) {
     291             :   AliasSet *FoundSet = nullptr;
     292      336256 :   for (iterator I = begin(), E = end(); I != E;) {
     293             :     iterator Cur = I++;
     294      248074 :     if (Cur->Forward || !Cur->aliasesUnknownInst(Inst, AA))
     295             :       continue;
     296       96569 :     if (!FoundSet)            // If this is the first alias set ptr can go into.
     297             :       FoundSet = &*Cur;       // Remember it.
     298       11231 :     else if (!Cur->Forward)   // Otherwise, we must merge the sets.
     299       11231 :       FoundSet->mergeSetIn(*Cur, *this);     // Merge in contents.
     300             :   }
     301       88182 :   return FoundSet;
     302             : }
     303             : 
     304             : /// getAliasSetForPointer - Return the alias set that the specified pointer
     305             : /// lives in.
     306      593702 : AliasSet &AliasSetTracker::getAliasSetForPointer(Value *Pointer,
     307             :                                                  LocationSize Size,
     308             :                                                  const AAMDNodes &AAInfo) {
     309      593702 :   AliasSet::PointerRec &Entry = getEntryFor(Pointer);
     310             : 
     311      593702 :   if (AliasAnyAS) {
     312             :     // At this point, the AST is saturated, so we only have one active alias
     313             :     // set. That means we already know which alias set we want to return, and
     314             :     // just need to add the pointer to that set to keep the data structure
     315             :     // consistent.
     316             :     // This, of course, means that we will never need a merge here.
     317       24239 :     if (Entry.hasAliasSet()) {
     318       23299 :       Entry.updateSizeAndAAInfo(Size, AAInfo);
     319             :       assert(Entry.getAliasSet(*this) == AliasAnyAS &&
     320             :              "Entry in saturated AST must belong to only alias set");
     321             :     } else {
     322         940 :       AliasAnyAS->addPointer(*this, Entry, Size, AAInfo);
     323             :     }
     324       24239 :     return *AliasAnyAS;
     325             :   }
     326             : 
     327             :   // Check to see if the pointer is already known.
     328      569463 :   if (Entry.hasAliasSet()) {
     329             :     // If the size changed, we may need to merge several alias sets.
     330             :     // Note that we can *not* return the result of mergeAliasSetsForPointer
     331             :     // due to a quirk of alias analysis behavior. Since alias(undef, undef)
     332             :     // is NoAlias, mergeAliasSetsForPointer(undef, ...) will not find the
     333             :     // the right set for undef, even if it exists.
     334      397588 :     if (Entry.updateSizeAndAAInfo(Size, AAInfo))
     335         101 :       mergeAliasSetsForPointer(Pointer, Size, AAInfo);
     336             :     // Return the set!
     337      397588 :     return *Entry.getAliasSet(*this)->getForwardedTarget(*this);
     338             :   }
     339             :   
     340      171875 :   if (AliasSet *AS = mergeAliasSetsForPointer(Pointer, Size, AAInfo)) {
     341             :     // Add it to the alias set it aliases.
     342      130739 :     AS->addPointer(*this, Entry, Size, AAInfo);
     343      130739 :     return *AS;
     344             :   }
     345             :   
     346             :   // Otherwise create a new alias set to hold the loaded pointer.
     347       41136 :   AliasSets.push_back(new AliasSet());
     348       41136 :   AliasSets.back().addPointer(*this, Entry, Size, AAInfo);
     349       41136 :   return AliasSets.back();
     350             : }
     351             : 
     352        6913 : void AliasSetTracker::add(Value *Ptr, LocationSize Size,
     353             :                           const AAMDNodes &AAInfo) {
     354        6913 :   addPointer(Ptr, Size, AAInfo, AliasSet::NoAccess);
     355        6913 : }
     356             : 
     357      205991 : void AliasSetTracker::add(LoadInst *LI) {
     358      205991 :   if (isStrongerThanMonotonic(LI->getOrdering())) return addUnknown(LI);
     359             : 
     360             :   AAMDNodes AAInfo;
     361      205990 :   LI->getAAMetadata(AAInfo);
     362             : 
     363             :   AliasSet::AccessLattice Access = AliasSet::RefAccess;
     364      205990 :   const DataLayout &DL = LI->getModule()->getDataLayout();
     365             :   AliasSet &AS = addPointer(LI->getOperand(0),
     366      411980 :                             DL.getTypeStoreSize(LI->getType()), AAInfo, Access);
     367      205990 :   if (LI->isVolatile()) AS.setVolatile();
     368             : }
     369             : 
     370      214322 : void AliasSetTracker::add(StoreInst *SI) {
     371      214322 :   if (isStrongerThanMonotonic(SI->getOrdering())) return addUnknown(SI);
     372             : 
     373             :   AAMDNodes AAInfo;
     374      214317 :   SI->getAAMetadata(AAInfo);
     375             : 
     376             :   AliasSet::AccessLattice Access = AliasSet::ModAccess;
     377      214317 :   const DataLayout &DL = SI->getModule()->getDataLayout();
     378             :   Value *Val = SI->getOperand(0);
     379             :   AliasSet &AS = addPointer(
     380      428634 :       SI->getOperand(1), DL.getTypeStoreSize(Val->getType()), AAInfo, Access);
     381      214317 :   if (SI->isVolatile()) AS.setVolatile();
     382             : }
     383             : 
     384           1 : void AliasSetTracker::add(VAArgInst *VAAI) {
     385             :   AAMDNodes AAInfo;
     386           1 :   VAAI->getAAMetadata(AAInfo);
     387             : 
     388           1 :   addPointer(VAAI->getOperand(0), MemoryLocation::UnknownSize, AAInfo,
     389             :              AliasSet::ModRefAccess);
     390           1 : }
     391             : 
     392         284 : void AliasSetTracker::add(AnyMemSetInst *MSI) {
     393             :   AAMDNodes AAInfo;
     394         284 :   MSI->getAAMetadata(AAInfo);
     395             : 
     396             :   uint64_t Len;
     397             : 
     398             :   if (ConstantInt *C = dyn_cast<ConstantInt>(MSI->getLength()))
     399             :     Len = C->getZExtValue();
     400             :   else
     401             :     Len = MemoryLocation::UnknownSize;
     402             : 
     403             :   AliasSet &AS =
     404         284 :       addPointer(MSI->getRawDest(), Len, AAInfo, AliasSet::ModAccess);
     405             :   auto *MS = dyn_cast<MemSetInst>(MSI);
     406         284 :   if (MS && MS->isVolatile())
     407             :     AS.setVolatile();
     408         284 : }
     409             : 
     410         558 : void AliasSetTracker::add(AnyMemTransferInst *MTI) {
     411             :   AAMDNodes AAInfo;
     412         558 :   MTI->getAAMetadata(AAInfo);
     413             : 
     414             :   uint64_t Len;
     415             :   if (ConstantInt *C = dyn_cast<ConstantInt>(MTI->getLength()))
     416             :     Len = C->getZExtValue();
     417             :   else
     418             :     Len = MemoryLocation::UnknownSize;
     419             : 
     420             :   AliasSet &ASSrc =
     421         558 :       addPointer(MTI->getRawSource(), Len, AAInfo, AliasSet::RefAccess);
     422             : 
     423             :   AliasSet &ASDst =
     424         558 :       addPointer(MTI->getRawDest(), Len, AAInfo, AliasSet::ModAccess);
     425             : 
     426             :   auto* MT = dyn_cast<MemTransferInst>(MTI);
     427         552 :   if (MT && MT->isVolatile()) {
     428             :     ASSrc.setVolatile();
     429             :     ASDst.setVolatile();
     430             :   }
     431         558 : }
     432             : 
     433      594047 : void AliasSetTracker::addUnknown(Instruction *Inst) {
     434             :   if (isa<DbgInfoIntrinsic>(Inst))
     435             :     return; // Ignore DbgInfo Intrinsics.
     436             : 
     437             :   if (auto *II = dyn_cast<IntrinsicInst>(Inst)) {
     438             :     // These intrinsics will show up as affecting memory, but they are just
     439             :     // markers.
     440       25013 :     switch (II->getIntrinsicID()) {
     441             :     default:
     442             :       break;
     443             :       // FIXME: Add lifetime/invariant intrinsics (See: PR30807).
     444             :     case Intrinsic::assume:
     445             :     case Intrinsic::sideeffect:
     446             :       return;
     447             :     }
     448             :   }
     449      522587 :   if (!Inst->mayReadOrWriteMemory())
     450             :     return; // doesn't alias anything
     451             : 
     452       88182 :   AliasSet *AS = findAliasSetForUnknownInst(Inst);
     453       88182 :   if (AS) {
     454       85338 :     AS->addUnknownInst(Inst, AA);
     455       85338 :     return;
     456             :   }
     457        2844 :   AliasSets.push_back(new AliasSet());
     458             :   AS = &AliasSets.back();
     459        2844 :   AS->addUnknownInst(Inst, AA);
     460             : }
     461             : 
     462     1015197 : void AliasSetTracker::add(Instruction *I) {
     463             :   // Dispatch to one of the other add methods.
     464             :   if (LoadInst *LI = dyn_cast<LoadInst>(I))
     465      205991 :     return add(LI);
     466             :   if (StoreInst *SI = dyn_cast<StoreInst>(I))
     467      214322 :     return add(SI);
     468             :   if (VAArgInst *VAAI = dyn_cast<VAArgInst>(I))
     469           1 :     return add(VAAI);
     470             :   if (AnyMemSetInst *MSI = dyn_cast<AnyMemSetInst>(I))
     471         284 :     return add(MSI);
     472             :   if (AnyMemTransferInst *MTI = dyn_cast<AnyMemTransferInst>(I))
     473         558 :     return add(MTI);
     474      594041 :   return addUnknown(I);
     475             : }
     476             : 
     477       79535 : void AliasSetTracker::add(BasicBlock &BB) {
     478     1083597 :   for (auto &I : BB)
     479     1004062 :     add(&I);
     480       79535 : }
     481             : 
     482       21185 : void AliasSetTracker::add(const AliasSetTracker &AST) {
     483             :   assert(&AA == &AST.AA &&
     484             :          "Merging AliasSetTracker objects with different Alias Analyses!");
     485             : 
     486             :   // Loop over all of the alias sets in AST, adding the pointers contained
     487             :   // therein into the current alias sets.  This can cause alias sets to be
     488             :   // merged together in the current AST.
     489       22204 :   for (const AliasSet &AS : AST) {
     490        1019 :     if (AS.Forward)
     491         278 :       continue; // Ignore forwarding alias sets
     492             : 
     493             :     // If there are any call sites in the alias set, add them to this AST.
     494        5912 :     for (unsigned i = 0, e = AS.UnknownInsts.size(); i != e; ++i)
     495             :       if (auto *Inst = AS.getUnknownInst(i))
     496        4430 :         add(Inst);
     497             : 
     498             :     // Loop over all of the pointers in this alias set.
     499       11387 :     for (AliasSet::iterator ASI = AS.begin(), E = AS.end(); ASI != E; ++ASI) {
     500             :       AliasSet &NewAS =
     501       19810 :           addPointer(ASI.getPointer(), ASI.getSize(), ASI.getAAInfo(),
     502       19810 :                      (AliasSet::AccessLattice)AS.Access);
     503        9905 :       if (AS.isVolatile()) NewAS.setVolatile();
     504             :     }
     505             :   }
     506       21185 : }
     507             : 
     508             : // deleteValue method - This method is used to remove a pointer value from the
     509             : // AliasSetTracker entirely.  It should be used when an instruction is deleted
     510             : // from the program to update the AST.  If you don't use this, you would have
     511             : // dangling pointers to deleted instructions.
     512             : //
     513        1202 : void AliasSetTracker::deleteValue(Value *PtrVal) {
     514             :   // First, look up the PointerRec for this pointer.
     515        1202 :   PointerMapType::iterator I = PointerMap.find_as(PtrVal);
     516        2331 :   if (I == PointerMap.end()) return;  // Noop
     517             : 
     518             :   // If we found one, remove the pointer from the alias set it is in.
     519          73 :   AliasSet::PointerRec *PtrValEnt = I->second;
     520          73 :   AliasSet *AS = PtrValEnt->getAliasSet(*this);
     521             : 
     522             :   // Unlink and delete from the list of values.
     523          73 :   PtrValEnt->eraseFromList();
     524             : 
     525          73 :   if (AS->Alias == AliasSet::SetMayAlias) {
     526          47 :     AS->SetSize--;
     527          47 :     TotalMayAliasSetSize--;
     528             :   }
     529             :   
     530             :   // Stop using the alias set.
     531             :   AS->dropRef(*this);
     532             :   
     533          73 :   PointerMap.erase(I);
     534             : }
     535             : 
     536             : // copyValue - This method should be used whenever a preexisting value in the
     537             : // program is copied or cloned, introducing a new value.  Note that it is ok for
     538             : // clients that use this method to introduce the same value multiple times: if
     539             : // the tracker already knows about a value, it will ignore the request.
     540             : //
     541         513 : void AliasSetTracker::copyValue(Value *From, Value *To) {
     542             :   // First, look up the PointerRec for this pointer.
     543         513 :   PointerMapType::iterator I = PointerMap.find_as(From);
     544         513 :   if (I == PointerMap.end())
     545         454 :     return;  // Noop
     546             :   assert(I->second->hasAliasSet() && "Dead entry?");
     547             : 
     548         122 :   AliasSet::PointerRec &Entry = getEntryFor(To);
     549         122 :   if (Entry.hasAliasSet()) return;    // Already in the tracker!
     550             : 
     551             :   // getEntryFor above may invalidate iterator \c I, so reinitialize it.
     552          59 :   I = PointerMap.find_as(From);
     553             :   // Add it to the alias set it aliases...
     554          59 :   AliasSet *AS = I->second->getAliasSet(*this);
     555          59 :   AS->addPointer(*this, Entry, I->second->getSize(),
     556         118 :                  I->second->getAAInfo(),
     557             :                  true);
     558             : }
     559             : 
     560          38 : AliasSet &AliasSetTracker::mergeAllAliasSets() {
     561             :   assert(!AliasAnyAS && (TotalMayAliasSetSize > SaturationThreshold) &&
     562             :          "Full merge should happen once, when the saturation threshold is "
     563             :          "reached");
     564             : 
     565             :   // Collect all alias sets, so that we can drop references with impunity
     566             :   // without worrying about iterator invalidation.
     567             :   std::vector<AliasSet *> ASVector;
     568          38 :   ASVector.reserve(SaturationThreshold);
     569          82 :   for (iterator I = begin(), E = end(); I != E; I++)
     570          88 :     ASVector.push_back(&*I);
     571             : 
     572             :   // Copy all instructions and pointers into a new set, and forward all other
     573             :   // sets to it.
     574          38 :   AliasSets.push_back(new AliasSet());
     575          38 :   AliasAnyAS = &AliasSets.back();
     576          38 :   AliasAnyAS->Alias = AliasSet::SetMayAlias;
     577          38 :   AliasAnyAS->Access = AliasSet::ModRefAccess;
     578          38 :   AliasAnyAS->AliasAny = true;
     579             : 
     580          82 :   for (auto Cur : ASVector) {
     581             :     // If Cur was already forwarding, just forward to the new AS instead.
     582          44 :     AliasSet *FwdTo = Cur->Forward;
     583          47 :     if (FwdTo) {
     584           3 :       Cur->Forward = AliasAnyAS;
     585             :       AliasAnyAS->addRef();
     586             :       FwdTo->dropRef(*this);
     587           3 :       continue;
     588             :     }
     589             : 
     590             :     // Otherwise, perform the actual merge.
     591          41 :     AliasAnyAS->mergeSetIn(*Cur, *this);
     592             :   }
     593             : 
     594          76 :   return *AliasAnyAS;
     595             : }
     596             : 
     597      438526 : AliasSet &AliasSetTracker::addPointer(Value *P, LocationSize Size,
     598             :                                       const AAMDNodes &AAInfo,
     599             :                                       AliasSet::AccessLattice E) {
     600      438526 :   AliasSet &AS = getAliasSetForPointer(P, Size, AAInfo);
     601      438526 :   AS.Access |= E;
     602             : 
     603      865687 :   if (!AliasAnyAS && (TotalMayAliasSetSize > SaturationThreshold)) {
     604             :     // The AST is now saturated. From here on, we conservatively consider all
     605             :     // pointers to alias each-other.
     606          38 :     return mergeAllAliasSets();
     607             :   }
     608             : 
     609             :   return AS;
     610             : }
     611             : 
     612             : //===----------------------------------------------------------------------===//
     613             : //               AliasSet/AliasSetTracker Printing Support
     614             : //===----------------------------------------------------------------------===//
     615             : 
     616          58 : void AliasSet::print(raw_ostream &OS) const {
     617         116 :   OS << "  AliasSet[" << (const void*)this << ", " << RefCount << "] ";
     618          58 :   OS << (Alias == SetMustAlias ? "must" : "may") << " alias, ";
     619          58 :   switch (Access) {
     620           0 :   case NoAccess:     OS << "No access "; break;
     621           5 :   case RefAccess:    OS << "Ref       "; break;
     622          37 :   case ModAccess:    OS << "Mod       "; break;
     623          16 :   case ModRefAccess: OS << "Mod/Ref   "; break;
     624           0 :   default: llvm_unreachable("Bad value for Access!");
     625             :   }
     626          58 :   if (isVolatile()) OS << "[volatile] ";
     627          58 :   if (Forward)
     628           5 :     OS << " forwarding to " << (void*)Forward;
     629             : 
     630          58 :   if (!empty()) {
     631          53 :     OS << "Pointers: ";
     632          53 :     for (iterator I = begin(), E = end(); I != E; ++I) {
     633          67 :       if (I != begin()) OS << ", ";
     634          67 :       I.getPointer()->printAsOperand(OS << "(");
     635         134 :       OS << ", " << I.getSize() << ")";
     636             :     }
     637             :   }
     638          58 :   if (!UnknownInsts.empty()) {
     639           0 :     OS << "\n    " << UnknownInsts.size() << " Unknown instructions: ";
     640           0 :     for (unsigned i = 0, e = UnknownInsts.size(); i != e; ++i) {
     641           0 :       if (i) OS << ", ";
     642             :       if (auto *I = getUnknownInst(i)) {
     643           0 :         if (I->hasName())
     644           0 :           I->printAsOperand(OS);
     645             :         else
     646           0 :           I->print(OS);
     647             :       }
     648             :     }
     649             :   }
     650          58 :   OS << "\n";
     651          58 : }
     652             : 
     653          20 : void AliasSetTracker::print(raw_ostream &OS) const {
     654          40 :   OS << "Alias Set Tracker: " << AliasSets.size() << " alias sets for "
     655          20 :      << PointerMap.size() << " pointer values.\n";
     656          78 :   for (const AliasSet &AS : *this)
     657          58 :     AS.print(OS);
     658          20 :   OS << "\n";
     659          20 : }
     660             : 
     661             : #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
     662             : LLVM_DUMP_METHOD void AliasSet::dump() const { print(dbgs()); }
     663             : LLVM_DUMP_METHOD void AliasSetTracker::dump() const { print(dbgs()); }
     664             : #endif
     665             : 
     666             : //===----------------------------------------------------------------------===//
     667             : //                     ASTCallbackVH Class Implementation
     668             : //===----------------------------------------------------------------------===//
     669             : 
     670           0 : void AliasSetTracker::ASTCallbackVH::deleted() {
     671             :   assert(AST && "ASTCallbackVH called with a null AliasSetTracker!");
     672           0 :   AST->deleteValue(getValPtr());
     673             :   // this now dangles!
     674           0 : }
     675             : 
     676          61 : void AliasSetTracker::ASTCallbackVH::allUsesReplacedWith(Value *V) {
     677          61 :   AST->copyValue(getValPtr(), V);
     678          61 : }
     679             : 
     680     2575066 : AliasSetTracker::ASTCallbackVH::ASTCallbackVH(Value *V, AliasSetTracker *ast)
     681     2575066 :   : CallbackVH(V), AST(ast) {}
     682             : 
     683             : AliasSetTracker::ASTCallbackVH &
     684           0 : AliasSetTracker::ASTCallbackVH::operator=(Value *V) {
     685           0 :   return *this = ASTCallbackVH(V, AST);
     686             : }
     687             : 
     688             : //===----------------------------------------------------------------------===//
     689             : //                            AliasSetPrinter Pass
     690             : //===----------------------------------------------------------------------===//
     691             : 
     692             : namespace {
     693             : 
     694          10 :   class AliasSetPrinter : public FunctionPass {
     695             :     AliasSetTracker *Tracker;
     696             : 
     697             :   public:
     698             :     static char ID; // Pass identification, replacement for typeid
     699             : 
     700          10 :     AliasSetPrinter() : FunctionPass(ID) {
     701           5 :       initializeAliasSetPrinterPass(*PassRegistry::getPassRegistry());
     702             :     }
     703             : 
     704           5 :     void getAnalysisUsage(AnalysisUsage &AU) const override {
     705             :       AU.setPreservesAll();
     706             :       AU.addRequired<AAResultsWrapperPass>();
     707           5 :     }
     708             : 
     709          20 :     bool runOnFunction(Function &F) override {
     710          20 :       auto &AAWP = getAnalysis<AAResultsWrapperPass>();
     711          40 :       Tracker = new AliasSetTracker(AAWP.getAAResults());
     712          20 :       errs() << "Alias sets for function '" << F.getName() << "':\n";
     713         160 :       for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I)
     714         320 :         Tracker->add(&*I);
     715          20 :       Tracker->print(errs());
     716          20 :       delete Tracker;
     717          20 :       return false;
     718             :     }
     719             :   };
     720             : 
     721             : } // end anonymous namespace
     722             : 
     723             : char AliasSetPrinter::ID = 0;
     724             : 
     725       10397 : INITIALIZE_PASS_BEGIN(AliasSetPrinter, "print-alias-sets",
     726             :                 "Alias Set Printer", false, true)
     727       10397 : INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
     728      340827 : INITIALIZE_PASS_END(AliasSetPrinter, "print-alias-sets",
     729             :                 "Alias Set Printer", false, true)

Generated by: LCOV version 1.13