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

Generated by: LCOV version 1.13