LCOV - code coverage report
Current view: top level - lib/Analysis - AliasAnalysis.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 258 273 94.5 %
Date: 2018-06-17 00:07:59 Functions: 43 45 95.6 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : //==- AliasAnalysis.cpp - Generic Alias Analysis Interface 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 generic AliasAnalysis interface which is used as the
      11             : // common interface used by all clients and implementations of alias analysis.
      12             : //
      13             : // This file also implements the default version of the AliasAnalysis interface
      14             : // that is to be used when no other implementation is specified.  This does some
      15             : // simple tests that detect obvious cases: two different global pointers cannot
      16             : // alias, a global cannot alias a malloc, two different mallocs cannot alias,
      17             : // etc.
      18             : //
      19             : // This alias analysis implementation really isn't very good for anything, but
      20             : // it is very fast, and makes a nice clean default implementation.  Because it
      21             : // handles lots of little corner cases, other, more complex, alias analysis
      22             : // implementations may choose to rely on this pass to resolve these simple and
      23             : // easy cases.
      24             : //
      25             : //===----------------------------------------------------------------------===//
      26             : 
      27             : #include "llvm/Analysis/AliasAnalysis.h"
      28             : #include "llvm/Analysis/BasicAliasAnalysis.h"
      29             : #include "llvm/Analysis/CFLAndersAliasAnalysis.h"
      30             : #include "llvm/Analysis/CFLSteensAliasAnalysis.h"
      31             : #include "llvm/Analysis/CaptureTracking.h"
      32             : #include "llvm/Analysis/GlobalsModRef.h"
      33             : #include "llvm/Analysis/MemoryLocation.h"
      34             : #include "llvm/Analysis/ObjCARCAliasAnalysis.h"
      35             : #include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h"
      36             : #include "llvm/Analysis/ScopedNoAliasAA.h"
      37             : #include "llvm/Analysis/TargetLibraryInfo.h"
      38             : #include "llvm/Analysis/TypeBasedAliasAnalysis.h"
      39             : #include "llvm/Analysis/ValueTracking.h"
      40             : #include "llvm/IR/Argument.h"
      41             : #include "llvm/IR/Attributes.h"
      42             : #include "llvm/IR/BasicBlock.h"
      43             : #include "llvm/IR/CallSite.h"
      44             : #include "llvm/IR/Instruction.h"
      45             : #include "llvm/IR/Instructions.h"
      46             : #include "llvm/IR/Module.h"
      47             : #include "llvm/IR/Type.h"
      48             : #include "llvm/IR/Value.h"
      49             : #include "llvm/Pass.h"
      50             : #include "llvm/Support/AtomicOrdering.h"
      51             : #include "llvm/Support/Casting.h"
      52             : #include "llvm/Support/CommandLine.h"
      53             : #include <algorithm>
      54             : #include <cassert>
      55             : #include <functional>
      56             : #include <iterator>
      57             : 
      58             : using namespace llvm;
      59             : 
      60             : /// Allow disabling BasicAA from the AA results. This is particularly useful
      61             : /// when testing to isolate a single AA implementation.
      62      101169 : static cl::opt<bool> DisableBasicAA("disable-basicaa", cl::Hidden,
      63      101169 :                                     cl::init(false));
      64             : 
      65      141305 : AAResults::AAResults(AAResults &&Arg)
      66      141305 :     : TLI(Arg.TLI), AAs(std::move(Arg.AAs)), AADeps(std::move(Arg.AADeps)) {
      67      620068 :   for (auto &AA : AAs)
      68      478764 :     AA->setAAResults(this);
      69      141304 : }
      70             : 
      71     2203142 : AAResults::~AAResults() {
      72             : // FIXME; It would be nice to at least clear out the pointers back to this
      73             : // aggregation here, but we end up with non-nesting lifetimes in the legacy
      74             : // pass manager that prevent this from working. In the legacy pass manager
      75             : // we'll end up with dangling references here in some cases.
      76             : #if 0
      77             :   for (auto &AA : AAs)
      78             :     AA->setAAResults(nullptr);
      79             : #endif
      80     1101570 : }
      81             : 
      82         988 : bool AAResults::invalidate(Function &F, const PreservedAnalyses &PA,
      83             :                            FunctionAnalysisManager::Invalidator &Inv) {
      84             :   // Check if the AA manager itself has been invalidated.
      85             :   auto PAC = PA.getChecker<AAManager>();
      86         988 :   if (!PAC.preserved() && !PAC.preservedSet<AllAnalysesOn<Function>>())
      87             :     return true; // The manager needs to be blown away, clear everything.
      88             : 
      89             :   // Check all of the dependencies registered.
      90         800 :   for (AnalysisKey *ID : AADeps)
      91         317 :     if (Inv.invalidate(ID, F, PA))
      92             :       return true;
      93             : 
      94             :   // Everything we depend on is still fine, so are we. Nothing to invalidate.
      95             :   return false;
      96             : }
      97             : 
      98             : //===----------------------------------------------------------------------===//
      99             : // Default chaining methods
     100             : //===----------------------------------------------------------------------===//
     101             : 
     102    19702189 : AliasResult AAResults::alias(const MemoryLocation &LocA,
     103             :                              const MemoryLocation &LocB) {
     104    28658391 :   for (const auto &AA : AAs) {
     105    26403728 :     auto Result = AA->alias(LocA, LocB);
     106    26403728 :     if (Result != MayAlias)
     107             :       return Result;
     108             :   }
     109             :   return MayAlias;
     110             : }
     111             : 
     112     4381976 : bool AAResults::pointsToConstantMemory(const MemoryLocation &Loc,
     113             :                                        bool OrLocal) {
     114    20691894 :   for (const auto &AA : AAs)
     115    16334414 :     if (AA->pointsToConstantMemory(Loc, OrLocal))
     116             :       return true;
     117             : 
     118             :   return false;
     119             : }
     120             : 
     121     2183028 : ModRefInfo AAResults::getArgModRefInfo(ImmutableCallSite CS, unsigned ArgIdx) {
     122             :   ModRefInfo Result = ModRefInfo::ModRef;
     123             : 
     124    10911796 :   for (const auto &AA : AAs) {
     125     8728769 :     Result = intersectModRef(Result, AA->getArgModRefInfo(CS, ArgIdx));
     126             : 
     127             :     // Early-exit the moment we reach the bottom of the lattice.
     128     8728769 :     if (isNoModRef(Result))
     129             :       return ModRefInfo::NoModRef;
     130             :   }
     131             : 
     132             :   return Result;
     133             : }
     134             : 
     135        9285 : ModRefInfo AAResults::getModRefInfo(Instruction *I, ImmutableCallSite Call) {
     136             :   // We may have two calls.
     137        9285 :   if (auto CS = ImmutableCallSite(I)) {
     138             :     // Check if the two calls modify the same memory.
     139         814 :     return getModRefInfo(CS, Call);
     140             :   } else if (I->isFenceLike()) {
     141             :     // If this is a fence, just return ModRef.
     142             :     return ModRefInfo::ModRef;
     143             :   } else {
     144             :     // Otherwise, check if the call modifies or references the
     145             :     // location this memory access defines.  The best we can say
     146             :     // is that if the call references what this instruction
     147             :     // defines, it must be clobbered by this location.
     148             :     const MemoryLocation DefLoc = MemoryLocation::get(I);
     149        8470 :     ModRefInfo MR = getModRefInfo(Call, DefLoc);
     150        8470 :     if (isModOrRefSet(MR))
     151         895 :       return setModAndRef(MR);
     152             :   }
     153        7575 :   return ModRefInfo::NoModRef;
     154             : }
     155             : 
     156     4504347 : ModRefInfo AAResults::getModRefInfo(ImmutableCallSite CS,
     157             :                                     const MemoryLocation &Loc) {
     158             :   ModRefInfo Result = ModRefInfo::ModRef;
     159             : 
     160    22244475 :   for (const auto &AA : AAs) {
     161    17787425 :     Result = intersectModRef(Result, AA->getModRefInfo(CS, Loc));
     162             : 
     163             :     // Early-exit the moment we reach the bottom of the lattice.
     164    17787425 :     if (isNoModRef(Result))
     165             :       return ModRefInfo::NoModRef;
     166             :   }
     167             : 
     168             :   // Try to refine the mod-ref info further using other API entry points to the
     169             :   // aggregate set of AA results.
     170     4457050 :   auto MRB = getModRefBehavior(CS);
     171     8914100 :   if (MRB == FMRB_DoesNotAccessMemory ||
     172     4457050 :       MRB == FMRB_OnlyAccessesInaccessibleMem)
     173             :     return ModRefInfo::NoModRef;
     174             : 
     175     4444462 :   if (onlyReadsMemory(MRB))
     176             :     Result = clearMod(Result);
     177     4430045 :   else if (doesNotReadMemory(MRB))
     178             :     Result = clearRef(Result);
     179             : 
     180     6153276 :   if (onlyAccessesArgPointees(MRB) || onlyAccessesInaccessibleOrArgMem(MRB)) {
     181             :     bool DoesAlias = false;
     182             :     bool IsMustAlias = true;
     183             :     ModRefInfo AllArgsMask = ModRefInfo::NoModRef;
     184             :     if (doesAccessArgPointees(MRB)) {
     185    12394198 :       for (auto AI = CS.arg_begin(), AE = CS.arg_end(); AI != AE; ++AI) {
     186     9658473 :         const Value *Arg = *AI;
     187    19316946 :         if (!Arg->getType()->isPointerTy())
     188     6916963 :           continue;
     189     2741510 :         unsigned ArgIdx = std::distance(CS.arg_begin(), AI);
     190     2741510 :         MemoryLocation ArgLoc = MemoryLocation::getForArgument(CS, ArgIdx, TLI);
     191     2741510 :         AliasResult ArgAlias = alias(ArgLoc, Loc);
     192     2741510 :         if (ArgAlias != NoAlias) {
     193       27162 :           ModRefInfo ArgMask = getArgModRefInfo(CS, ArgIdx);
     194             :           DoesAlias = true;
     195             :           AllArgsMask = unionModRef(AllArgsMask, ArgMask);
     196             :         }
     197             :         // Conservatively clear IsMustAlias unless only MustAlias is found.
     198     2741510 :         IsMustAlias &= (ArgAlias == MustAlias);
     199             :       }
     200             :     }
     201             :     // Return NoModRef if no alias found with any argument.
     202     2735725 :     if (!DoesAlias)
     203             :       return ModRefInfo::NoModRef;
     204             :     // Logical & between other AA analyses and argument analysis.
     205             :     Result = intersectModRef(Result, AllArgsMask);
     206             :     // If only MustAlias found above, set Must bit.
     207       23329 :     Result = IsMustAlias ? setMust(Result) : clearMust(Result);
     208             :   }
     209             : 
     210             :   // If Loc is a constant memory location, the call definitely could not
     211             :   // modify the memory location.
     212     1732066 :   if (isModSet(Result) && pointsToConstantMemory(Loc, /*OrLocal*/ false))
     213             :     Result = clearMod(Result);
     214             : 
     215             :   return Result;
     216             : }
     217             : 
     218     2186409 : ModRefInfo AAResults::getModRefInfo(ImmutableCallSite CS1,
     219             :                                     ImmutableCallSite CS2) {
     220             :   ModRefInfo Result = ModRefInfo::ModRef;
     221             : 
     222    10927353 :   for (const auto &AA : AAs) {
     223     8741808 :     Result = intersectModRef(Result, AA->getModRefInfo(CS1, CS2));
     224             : 
     225             :     // Early-exit the moment we reach the bottom of the lattice.
     226     8741808 :     if (isNoModRef(Result))
     227             :       return ModRefInfo::NoModRef;
     228             :   }
     229             : 
     230             :   // Try to refine the mod-ref info further using other API entry points to the
     231             :   // aggregate set of AA results.
     232             : 
     233             :   // If CS1 or CS2 are readnone, they don't interact.
     234     2185545 :   auto CS1B = getModRefBehavior(CS1);
     235     2185545 :   if (CS1B == FMRB_DoesNotAccessMemory)
     236             :     return ModRefInfo::NoModRef;
     237             : 
     238     2185537 :   auto CS2B = getModRefBehavior(CS2);
     239     2185537 :   if (CS2B == FMRB_DoesNotAccessMemory)
     240             :     return ModRefInfo::NoModRef;
     241             : 
     242             :   // If they both only read from memory, there is no dependence.
     243     2188062 :   if (onlyReadsMemory(CS1B) && onlyReadsMemory(CS2B))
     244             :     return ModRefInfo::NoModRef;
     245             : 
     246             :   // If CS1 only reads memory, the only dependence on CS2 can be
     247             :   // from CS1 reading memory written by CS2.
     248     2183697 :   if (onlyReadsMemory(CS1B))
     249             :     Result = clearMod(Result);
     250     2182950 :   else if (doesNotReadMemory(CS1B))
     251             :     Result = clearRef(Result);
     252             : 
     253             :   // If CS2 only access memory through arguments, accumulate the mod/ref
     254             :   // information from CS1's references to the memory referenced by
     255             :   // CS2's arguments.
     256     2183697 :   if (onlyAccessesArgPointees(CS2B)) {
     257             :     if (!doesAccessArgPointees(CS2B))
     258             :       return ModRefInfo::NoModRef;
     259             :     ModRefInfo R = ModRefInfo::NoModRef;
     260             :     bool IsMustAlias = true;
     261    10446212 :     for (auto I = CS2.arg_begin(), E = CS2.arg_end(); I != E; ++I) {
     262     8350473 :       const Value *Arg = *I;
     263    16700946 :       if (!Arg->getType()->isPointerTy())
     264     6232545 :         continue;
     265     2117928 :       unsigned CS2ArgIdx = std::distance(CS2.arg_begin(), I);
     266     2117928 :       auto CS2ArgLoc = MemoryLocation::getForArgument(CS2, CS2ArgIdx, TLI);
     267             : 
     268             :       // ArgModRefCS2 indicates what CS2 might do to CS2ArgLoc, and the
     269             :       // dependence of CS1 on that location is the inverse:
     270             :       // - If CS2 modifies location, dependence exists if CS1 reads or writes.
     271             :       // - If CS2 only reads location, dependence exists if CS1 writes.
     272     2117928 :       ModRefInfo ArgModRefCS2 = getArgModRefInfo(CS2, CS2ArgIdx);
     273             :       ModRefInfo ArgMask = ModRefInfo::NoModRef;
     274     2117928 :       if (isModSet(ArgModRefCS2))
     275             :         ArgMask = ModRefInfo::ModRef;
     276         257 :       else if (isRefSet(ArgModRefCS2))
     277             :         ArgMask = ModRefInfo::Mod;
     278             : 
     279             :       // ModRefCS1 indicates what CS1 might do to CS2ArgLoc, and we use
     280             :       // above ArgMask to update dependence info.
     281     2117928 :       ModRefInfo ModRefCS1 = getModRefInfo(CS1, CS2ArgLoc);
     282             :       ArgMask = intersectModRef(ArgMask, ModRefCS1);
     283             : 
     284             :       // Conservatively clear IsMustAlias unless only MustAlias is found.
     285             :       IsMustAlias &= isMustSet(ModRefCS1);
     286             : 
     287             :       R = intersectModRef(unionModRef(R, ArgMask), Result);
     288     2117928 :       if (R == Result) {
     289             :         // On early exit, not all args were checked, cannot set Must.
     290       21994 :         if (I + 1 != E)
     291             :           IsMustAlias = false;
     292       21994 :         break;
     293             :       }
     294             :     }
     295             : 
     296     2117733 :     if (isNoModRef(R))
     297             :       return ModRefInfo::NoModRef;
     298             : 
     299             :     // If MustAlias found above, set Must bit.
     300       22909 :     return IsMustAlias ? setMust(R) : clearMust(R);
     301             :   }
     302             : 
     303             :   // If CS1 only accesses memory through arguments, check if CS2 references
     304             :   // any of the memory referenced by CS1's arguments. If not, return NoModRef.
     305       65964 :   if (onlyAccessesArgPointees(CS1B)) {
     306             :     if (!doesAccessArgPointees(CS1B))
     307             :       return ModRefInfo::NoModRef;
     308             :     ModRefInfo R = ModRefInfo::NoModRef;
     309             :     bool IsMustAlias = true;
     310       94403 :     for (auto I = CS1.arg_begin(), E = CS1.arg_end(); I != E; ++I) {
     311       86549 :       const Value *Arg = *I;
     312      173098 :       if (!Arg->getType()->isPointerTy())
     313       48611 :         continue;
     314       37938 :       unsigned CS1ArgIdx = std::distance(CS1.arg_begin(), I);
     315       37938 :       auto CS1ArgLoc = MemoryLocation::getForArgument(CS1, CS1ArgIdx, TLI);
     316             : 
     317             :       // ArgModRefCS1 indicates what CS1 might do to CS1ArgLoc; if CS1 might
     318             :       // Mod CS1ArgLoc, then we care about either a Mod or a Ref by CS2. If
     319             :       // CS1 might Ref, then we care only about a Mod by CS2.
     320       37938 :       ModRefInfo ArgModRefCS1 = getArgModRefInfo(CS1, CS1ArgIdx);
     321       37938 :       ModRefInfo ModRefCS2 = getModRefInfo(CS2, CS1ArgLoc);
     322       37938 :       if ((isModSet(ArgModRefCS1) && isModOrRefSet(ModRefCS2)) ||
     323        2502 :           (isRefSet(ArgModRefCS1) && isModSet(ModRefCS2)))
     324             :         R = intersectModRef(unionModRef(R, ArgModRefCS1), Result);
     325             : 
     326             :       // Conservatively clear IsMustAlias unless only MustAlias is found.
     327             :       IsMustAlias &= isMustSet(ModRefCS2);
     328             : 
     329       37938 :       if (R == Result) {
     330             :         // On early exit, not all args were checked, cannot set Must.
     331       30029 :         if (I + 1 != E)
     332             :           IsMustAlias = false;
     333       30029 :         break;
     334             :       }
     335             :     }
     336             : 
     337       37883 :     if (isNoModRef(R))
     338             :       return ModRefInfo::NoModRef;
     339             : 
     340             :     // If MustAlias found above, set Must bit.
     341       35410 :     return IsMustAlias ? setMust(R) : clearMust(R);
     342             :   }
     343             : 
     344             :   return Result;
     345             : }
     346             : 
     347     9336075 : FunctionModRefBehavior AAResults::getModRefBehavior(ImmutableCallSite CS) {
     348             :   FunctionModRefBehavior Result = FMRB_UnknownModRefBehavior;
     349             : 
     350    46101955 :   for (const auto &AA : AAs) {
     351    36883011 :     Result = FunctionModRefBehavior(Result & AA->getModRefBehavior(CS));
     352             : 
     353             :     // Early-exit the moment we reach the bottom of the lattice.
     354    36883011 :     if (Result == FMRB_DoesNotAccessMemory)
     355             :       return Result;
     356             :   }
     357             : 
     358             :   return Result;
     359             : }
     360             : 
     361     9237974 : FunctionModRefBehavior AAResults::getModRefBehavior(const Function *F) {
     362             :   FunctionModRefBehavior Result = FMRB_UnknownModRefBehavior;
     363             : 
     364    46075760 :   for (const auto &AA : AAs) {
     365    36840389 :     Result = FunctionModRefBehavior(Result & AA->getModRefBehavior(F));
     366             : 
     367             :     // Early-exit the moment we reach the bottom of the lattice.
     368    36840387 :     if (Result == FMRB_DoesNotAccessMemory)
     369             :       return Result;
     370             :   }
     371             : 
     372             :   return Result;
     373             : }
     374             : 
     375        5626 : raw_ostream &llvm::operator<<(raw_ostream &OS, AliasResult AR) {
     376        5626 :   switch (AR) {
     377        2447 :   case NoAlias:
     378        2447 :     OS << "NoAlias";
     379        2447 :     break;
     380         190 :   case MustAlias:
     381         190 :     OS << "MustAlias";
     382         190 :     break;
     383        2948 :   case MayAlias:
     384        2948 :     OS << "MayAlias";
     385        2948 :     break;
     386          41 :   case PartialAlias:
     387          41 :     OS << "PartialAlias";
     388          41 :     break;
     389             :   }
     390        5626 :   return OS;
     391             : }
     392             : 
     393             : //===----------------------------------------------------------------------===//
     394             : // Helper method implementation
     395             : //===----------------------------------------------------------------------===//
     396             : 
     397      472168 : ModRefInfo AAResults::getModRefInfo(const LoadInst *L,
     398             :                                     const MemoryLocation &Loc) {
     399             :   // Be conservative in the face of atomic.
     400      472168 :   if (isStrongerThan(L->getOrdering(), AtomicOrdering::Unordered))
     401             :     return ModRefInfo::ModRef;
     402             : 
     403             :   // If the load address doesn't alias the given address, it doesn't read
     404             :   // or write the specified memory.
     405      472006 :   if (Loc.Ptr) {
     406        7249 :     AliasResult AR = alias(MemoryLocation::get(L), Loc);
     407        7249 :     if (AR == NoAlias)
     408             :       return ModRefInfo::NoModRef;
     409        2826 :     if (AR == MustAlias)
     410             :       return ModRefInfo::MustRef;
     411             :   }
     412             :   // Otherwise, a load just reads.
     413             :   return ModRefInfo::Ref;
     414             : }
     415             : 
     416     8893195 : ModRefInfo AAResults::getModRefInfo(const StoreInst *S,
     417             :                                     const MemoryLocation &Loc) {
     418             :   // Be conservative in the face of atomic.
     419     8893195 :   if (isStrongerThan(S->getOrdering(), AtomicOrdering::Unordered))
     420             :     return ModRefInfo::ModRef;
     421             : 
     422     8893144 :   if (Loc.Ptr) {
     423     8258639 :     AliasResult AR = alias(MemoryLocation::get(S), Loc);
     424             :     // If the store address cannot alias the pointer in question, then the
     425             :     // specified memory cannot be modified by the store.
     426     8258639 :     if (AR == NoAlias)
     427             :       return ModRefInfo::NoModRef;
     428             : 
     429             :     // If the pointer is a pointer to constant memory, then it could not have
     430             :     // been modified by this store.
     431      455002 :     if (pointsToConstantMemory(Loc))
     432             :       return ModRefInfo::NoModRef;
     433             : 
     434             :     // If the store address aliases the pointer as must alias, set Must.
     435      451783 :     if (AR == MustAlias)
     436             :       return ModRefInfo::MustMod;
     437             :   }
     438             : 
     439             :   // Otherwise, a store just writes.
     440             :   return ModRefInfo::Mod;
     441             : }
     442             : 
     443         357 : ModRefInfo AAResults::getModRefInfo(const FenceInst *S, const MemoryLocation &Loc) {
     444             :   // If we know that the location is a constant memory location, the fence
     445             :   // cannot modify this location.
     446         357 :   if (Loc.Ptr && pointsToConstantMemory(Loc))
     447             :     return ModRefInfo::Ref;
     448             :   return ModRefInfo::ModRef;
     449             : }
     450             : 
     451           3 : ModRefInfo AAResults::getModRefInfo(const VAArgInst *V,
     452             :                                     const MemoryLocation &Loc) {
     453           3 :   if (Loc.Ptr) {
     454           1 :     AliasResult AR = alias(MemoryLocation::get(V), Loc);
     455             :     // If the va_arg address cannot alias the pointer in question, then the
     456             :     // specified memory cannot be accessed by the va_arg.
     457           1 :     if (AR == NoAlias)
     458             :       return ModRefInfo::NoModRef;
     459             : 
     460             :     // If the pointer is a pointer to constant memory, then it could not have
     461             :     // been modified by this va_arg.
     462           0 :     if (pointsToConstantMemory(Loc))
     463             :       return ModRefInfo::NoModRef;
     464             : 
     465             :     // If the va_arg aliases the pointer as must alias, set Must.
     466           0 :     if (AR == MustAlias)
     467             :       return ModRefInfo::MustModRef;
     468             :   }
     469             : 
     470             :   // Otherwise, a va_arg reads and writes.
     471             :   return ModRefInfo::ModRef;
     472             : }
     473             : 
     474           2 : ModRefInfo AAResults::getModRefInfo(const CatchPadInst *CatchPad,
     475             :                                     const MemoryLocation &Loc) {
     476           2 :   if (Loc.Ptr) {
     477             :     // If the pointer is a pointer to constant memory,
     478             :     // then it could not have been modified by this catchpad.
     479           0 :     if (pointsToConstantMemory(Loc))
     480             :       return ModRefInfo::NoModRef;
     481             :   }
     482             : 
     483             :   // Otherwise, a catchpad reads and writes.
     484             :   return ModRefInfo::ModRef;
     485             : }
     486             : 
     487           6 : ModRefInfo AAResults::getModRefInfo(const CatchReturnInst *CatchRet,
     488             :                                     const MemoryLocation &Loc) {
     489           6 :   if (Loc.Ptr) {
     490             :     // If the pointer is a pointer to constant memory,
     491             :     // then it could not have been modified by this catchpad.
     492           4 :     if (pointsToConstantMemory(Loc))
     493             :       return ModRefInfo::NoModRef;
     494             :   }
     495             : 
     496             :   // Otherwise, a catchret reads and writes.
     497             :   return ModRefInfo::ModRef;
     498             : }
     499             : 
     500        1925 : ModRefInfo AAResults::getModRefInfo(const AtomicCmpXchgInst *CX,
     501             :                                     const MemoryLocation &Loc) {
     502             :   // Acquire/Release cmpxchg has properties that matter for arbitrary addresses.
     503        1925 :   if (isStrongerThanMonotonic(CX->getSuccessOrdering()))
     504             :     return ModRefInfo::ModRef;
     505             : 
     506           2 :   if (Loc.Ptr) {
     507           0 :     AliasResult AR = alias(MemoryLocation::get(CX), Loc);
     508             :     // If the cmpxchg address does not alias the location, it does not access
     509             :     // it.
     510           0 :     if (AR == NoAlias)
     511             :       return ModRefInfo::NoModRef;
     512             : 
     513             :     // If the cmpxchg address aliases the pointer as must alias, set Must.
     514           0 :     if (AR == MustAlias)
     515             :       return ModRefInfo::MustModRef;
     516             :   }
     517             : 
     518             :   return ModRefInfo::ModRef;
     519             : }
     520             : 
     521        2242 : ModRefInfo AAResults::getModRefInfo(const AtomicRMWInst *RMW,
     522             :                                     const MemoryLocation &Loc) {
     523             :   // Acquire/Release atomicrmw has properties that matter for arbitrary addresses.
     524        2242 :   if (isStrongerThanMonotonic(RMW->getOrdering()))
     525             :     return ModRefInfo::ModRef;
     526             : 
     527           6 :   if (Loc.Ptr) {
     528           2 :     AliasResult AR = alias(MemoryLocation::get(RMW), Loc);
     529             :     // If the atomicrmw address does not alias the location, it does not access
     530             :     // it.
     531           2 :     if (AR == NoAlias)
     532             :       return ModRefInfo::NoModRef;
     533             : 
     534             :     // If the atomicrmw address aliases the pointer as must alias, set Must.
     535           0 :     if (AR == MustAlias)
     536             :       return ModRefInfo::MustModRef;
     537             :   }
     538             : 
     539             :   return ModRefInfo::ModRef;
     540             : }
     541             : 
     542             : /// Return information about whether a particular call site modifies
     543             : /// or reads the specified memory location \p MemLoc before instruction \p I
     544             : /// in a BasicBlock. An ordered basic block \p OBB can be used to speed up
     545             : /// instruction-ordering queries inside the BasicBlock containing \p I.
     546             : /// FIXME: this is really just shoring-up a deficiency in alias analysis.
     547             : /// BasicAA isn't willing to spend linear time determining whether an alloca
     548             : /// was captured before or after this particular call, while we are. However,
     549             : /// with a smarter AA in place, this test is just wasting compile time.
     550      379667 : ModRefInfo AAResults::callCapturesBefore(const Instruction *I,
     551             :                                          const MemoryLocation &MemLoc,
     552             :                                          DominatorTree *DT,
     553             :                                          OrderedBasicBlock *OBB) {
     554      379667 :   if (!DT)
     555             :     return ModRefInfo::ModRef;
     556             : 
     557             :   const Value *Object =
     558      379667 :       GetUnderlyingObject(MemLoc.Ptr, I->getModule()->getDataLayout());
     559      432169 :   if (!isIdentifiedObject(Object) || isa<GlobalValue>(Object) ||
     560             :       isa<Constant>(Object))
     561             :     return ModRefInfo::ModRef;
     562             : 
     563             :   ImmutableCallSite CS(I);
     564       52502 :   if (!CS.getInstruction() || CS.getInstruction() == Object)
     565             :     return ModRefInfo::ModRef;
     566             : 
     567       52444 :   if (PointerMayBeCapturedBefore(Object, /* ReturnCaptures */ true,
     568             :                                  /* StoreCaptures */ true, I, DT,
     569             :                                  /* include Object */ true,
     570             :                                  /* OrderedBasicBlock */ OBB))
     571             :     return ModRefInfo::ModRef;
     572             : 
     573             :   unsigned ArgNo = 0;
     574             :   ModRefInfo R = ModRefInfo::NoModRef;
     575             :   bool IsMustAlias = true;
     576             :   // Set flag only if no May found and all operands processed.
     577        5243 :   for (auto CI = CS.data_operands_begin(), CE = CS.data_operands_end();
     578        5243 :        CI != CE; ++CI, ++ArgNo) {
     579             :     // Only look at the no-capture or byval pointer arguments.  If this
     580             :     // pointer were passed to arguments that were neither of these, then it
     581             :     // couldn't be no-capture.
     582       12172 :     if (!(*CI)->getType()->isPointerTy() ||
     583        1320 :         (!CS.doesNotCapture(ArgNo) &&
     584        2640 :          ArgNo < CS.getNumArgOperands() && !CS.isByValArgument(ArgNo)))
     585        1636 :       continue;
     586             : 
     587        4030 :     AliasResult AR = alias(MemoryLocation(*CI), MemoryLocation(Object));
     588             :     // If this is a no-capture pointer argument, see if we can tell that it
     589             :     // is impossible to alias the pointer we're checking.  If not, we have to
     590             :     // assume that the call could touch the pointer, even though it doesn't
     591             :     // escape.
     592        2015 :     if (AR != MustAlias)
     593             :       IsMustAlias = false;
     594        2015 :     if (AR == NoAlias)
     595        1757 :       continue;
     596         258 :     if (CS.doesNotAccessMemory(ArgNo))
     597           0 :       continue;
     598         258 :     if (CS.onlyReadsMemory(ArgNo)) {
     599             :       R = ModRefInfo::Ref;
     600           4 :       continue;
     601             :     }
     602             :     // Not returning MustModRef since we have not seen all the arguments.
     603             :     return ModRefInfo::ModRef;
     604             :   }
     605        1592 :   return IsMustAlias ? setMust(R) : clearMust(R);
     606             : }
     607             : 
     608             : /// canBasicBlockModify - Return true if it is possible for execution of the
     609             : /// specified basic block to modify the location Loc.
     610             : ///
     611           2 : bool AAResults::canBasicBlockModify(const BasicBlock &BB,
     612             :                                     const MemoryLocation &Loc) {
     613           2 :   return canInstructionRangeModRef(BB.front(), BB.back(), Loc, ModRefInfo::Mod);
     614             : }
     615             : 
     616             : /// canInstructionRangeModRef - Return true if it is possible for the
     617             : /// execution of the specified instructions to mod\ref (according to the
     618             : /// mode) the location Loc. The instructions to consider are all
     619             : /// of the instructions in the range of [I1,I2] INCLUSIVE.
     620             : /// I1 and I2 must be in the same basic block.
     621         545 : bool AAResults::canInstructionRangeModRef(const Instruction &I1,
     622             :                                           const Instruction &I2,
     623             :                                           const MemoryLocation &Loc,
     624             :                                           const ModRefInfo Mode) {
     625             :   assert(I1.getParent() == I2.getParent() &&
     626             :          "Instructions not in same basic block!");
     627         545 :   BasicBlock::const_iterator I = I1.getIterator();
     628         545 :   BasicBlock::const_iterator E = I2.getIterator();
     629             :   ++E;  // Convert from inclusive to exclusive range.
     630             : 
     631        3700 :   for (; I != E; ++I) // Check every instruction in range
     632        6734 :     if (isModOrRefSet(intersectModRef(getModRefInfo(&*I, Loc), Mode)))
     633             :       return true;
     634             :   return false;
     635             : }
     636             : 
     637             : // Provide a definition for the root virtual destructor.
     638             : AAResults::Concept::~Concept() = default;
     639             : 
     640             : // Provide a definition for the static object used to identify passes.
     641             : AnalysisKey AAManager::Key;
     642             : 
     643             : namespace {
     644             : 
     645             : /// A wrapper pass for external alias analyses. This just squirrels away the
     646             : /// callback used to run any analyses and register their results.
     647        6375 : struct ExternalAAWrapperPass : ImmutablePass {
     648             :   using CallbackT = std::function<void(Pass &, Function &, AAResults &)>;
     649             : 
     650             :   CallbackT CB;
     651             : 
     652             :   static char ID;
     653             : 
     654           0 :   ExternalAAWrapperPass() : ImmutablePass(ID) {
     655           0 :     initializeExternalAAWrapperPassPass(*PassRegistry::getPassRegistry());
     656           0 :   }
     657             : 
     658        2133 :   explicit ExternalAAWrapperPass(CallbackT CB)
     659        4266 :       : ImmutablePass(ID), CB(std::move(CB)) {
     660        2133 :     initializeExternalAAWrapperPassPass(*PassRegistry::getPassRegistry());
     661        2133 :   }
     662             : 
     663        2122 :   void getAnalysisUsage(AnalysisUsage &AU) const override {
     664             :     AU.setPreservesAll();
     665        2122 :   }
     666             : };
     667             : 
     668             : } // end anonymous namespace
     669             : 
     670             : char ExternalAAWrapperPass::ID = 0;
     671             : 
     672      310670 : INITIALIZE_PASS(ExternalAAWrapperPass, "external-aa", "External Alias Analysis",
     673             :                 false, true)
     674             : 
     675             : ImmutablePass *
     676        2133 : llvm::createExternalAAWrapperPass(ExternalAAWrapperPass::CallbackT Callback) {
     677        4266 :   return new ExternalAAWrapperPass(std::move(Callback));
     678             : }
     679             : 
     680      115514 : AAResultsWrapperPass::AAResultsWrapperPass() : FunctionPass(ID) {
     681       57757 :   initializeAAResultsWrapperPassPass(*PassRegistry::getPassRegistry());
     682       57757 : }
     683             : 
     684             : char AAResultsWrapperPass::ID = 0;
     685             : 
     686       76601 : INITIALIZE_PASS_BEGIN(AAResultsWrapperPass, "aa",
     687             :                       "Function Alias Analysis Results", false, true)
     688       76601 : INITIALIZE_PASS_DEPENDENCY(BasicAAWrapperPass)
     689       76601 : INITIALIZE_PASS_DEPENDENCY(CFLAndersAAWrapperPass)
     690       76601 : INITIALIZE_PASS_DEPENDENCY(CFLSteensAAWrapperPass)
     691       76601 : INITIALIZE_PASS_DEPENDENCY(ExternalAAWrapperPass)
     692       76601 : INITIALIZE_PASS_DEPENDENCY(GlobalsAAWrapperPass)
     693       76601 : INITIALIZE_PASS_DEPENDENCY(ObjCARCAAWrapperPass)
     694       76601 : INITIALIZE_PASS_DEPENDENCY(SCEVAAWrapperPass)
     695       76601 : INITIALIZE_PASS_DEPENDENCY(ScopedNoAliasAAWrapperPass)
     696       76601 : INITIALIZE_PASS_DEPENDENCY(TypeBasedAAWrapperPass)
     697     4230864 : INITIALIZE_PASS_END(AAResultsWrapperPass, "aa",
     698             :                     "Function Alias Analysis Results", false, true)
     699             : 
     700           0 : FunctionPass *llvm::createAAResultsWrapperPass() {
     701           0 :   return new AAResultsWrapperPass();
     702             : }
     703             : 
     704             : /// Run the wrapper pass to rebuild an aggregation over known AA passes.
     705             : ///
     706             : /// This is the legacy pass manager's interface to the new-style AA results
     707             : /// aggregation object. Because this is somewhat shoe-horned into the legacy
     708             : /// pass manager, we hard code all the specific alias analyses available into
     709             : /// it. While the particular set enabled is configured via commandline flags,
     710             : /// adding a new alias analysis to LLVM will require adding support for it to
     711             : /// this list.
     712      820766 : bool AAResultsWrapperPass::runOnFunction(Function &F) {
     713             :   // NB! This *must* be reset before adding new AA results to the new
     714             :   // AAResults object because in the legacy pass manager, each instance
     715             :   // of these will refer to the *same* immutable analyses, registering and
     716             :   // unregistering themselves with them. We need to carefully tear down the
     717             :   // previous object first, in this case replacing it with an empty one, before
     718             :   // registering new results.
     719             :   AAR.reset(
     720     1641532 :       new AAResults(getAnalysis<TargetLibraryInfoWrapperPass>().getTLI()));
     721             : 
     722             :   // BasicAA is always available for function analyses. Also, we add it first
     723             :   // so that it can trump TBAA results when it proves MustAlias.
     724             :   // FIXME: TBAA should have an explicit mode to support this and then we
     725             :   // should reconsider the ordering here.
     726      820766 :   if (!DisableBasicAA)
     727     1641178 :     AAR->addAAResult(getAnalysis<BasicAAWrapperPass>().getResult());
     728             : 
     729             :   // Populate the results with the currently available AAs.
     730      820766 :   if (auto *WrapperPass = getAnalysisIfAvailable<ScopedNoAliasAAWrapperPass>())
     731      799530 :     AAR->addAAResult(WrapperPass->getResult());
     732      820766 :   if (auto *WrapperPass = getAnalysisIfAvailable<TypeBasedAAWrapperPass>())
     733      799691 :     AAR->addAAResult(WrapperPass->getResult());
     734      820766 :   if (auto *WrapperPass =
     735      820766 :           getAnalysisIfAvailable<objcarc::ObjCARCAAWrapperPass>())
     736         645 :     AAR->addAAResult(WrapperPass->getResult());
     737      820766 :   if (auto *WrapperPass = getAnalysisIfAvailable<GlobalsAAWrapperPass>())
     738      470338 :     AAR->addAAResult(WrapperPass->getResult());
     739      820766 :   if (auto *WrapperPass = getAnalysisIfAvailable<SCEVAAWrapperPass>())
     740           7 :     AAR->addAAResult(WrapperPass->getResult());
     741      820766 :   if (auto *WrapperPass = getAnalysisIfAvailable<CFLAndersAAWrapperPass>())
     742          42 :     AAR->addAAResult(WrapperPass->getResult());
     743      820766 :   if (auto *WrapperPass = getAnalysisIfAvailable<CFLSteensAAWrapperPass>())
     744          64 :     AAR->addAAResult(WrapperPass->getResult());
     745             : 
     746             :   // If available, run an external AA providing callback over the results as
     747             :   // well.
     748      820766 :   if (auto *WrapperPass = getAnalysisIfAvailable<ExternalAAWrapperPass>())
     749      105784 :     if (WrapperPass->CB)
     750             :       WrapperPass->CB(*this, F, *AAR);
     751             : 
     752             :   // Analyses don't mutate the IR, so return false.
     753      820766 :   return false;
     754             : }
     755             : 
     756       57760 : void AAResultsWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
     757             :   AU.setPreservesAll();
     758             :   AU.addRequired<BasicAAWrapperPass>();
     759             :   AU.addRequired<TargetLibraryInfoWrapperPass>();
     760             : 
     761             :   // We also need to mark all the alias analysis passes we will potentially
     762             :   // probe in runOnFunction as used here to ensure the legacy pass manager
     763             :   // preserves them. This hard coding of lists of alias analyses is specific to
     764             :   // the legacy pass manager.
     765             :   AU.addUsedIfAvailable<ScopedNoAliasAAWrapperPass>();
     766             :   AU.addUsedIfAvailable<TypeBasedAAWrapperPass>();
     767             :   AU.addUsedIfAvailable<objcarc::ObjCARCAAWrapperPass>();
     768             :   AU.addUsedIfAvailable<GlobalsAAWrapperPass>();
     769             :   AU.addUsedIfAvailable<SCEVAAWrapperPass>();
     770             :   AU.addUsedIfAvailable<CFLAndersAAWrapperPass>();
     771             :   AU.addUsedIfAvailable<CFLSteensAAWrapperPass>();
     772       57760 : }
     773             : 
     774      138012 : AAResults llvm::createLegacyPMAAResults(Pass &P, Function &F,
     775             :                                         BasicAAResult &BAR) {
     776      138012 :   AAResults AAR(P.getAnalysis<TargetLibraryInfoWrapperPass>().getTLI());
     777             : 
     778             :   // Add in our explicitly constructed BasicAA results.
     779      138012 :   if (!DisableBasicAA)
     780      138012 :     AAR.addAAResult(BAR);
     781             : 
     782             :   // Populate the results with the other currently available AAs.
     783      138011 :   if (auto *WrapperPass =
     784      138011 :           P.getAnalysisIfAvailable<ScopedNoAliasAAWrapperPass>())
     785      113247 :     AAR.addAAResult(WrapperPass->getResult());
     786      138012 :   if (auto *WrapperPass = P.getAnalysisIfAvailable<TypeBasedAAWrapperPass>())
     787      113262 :     AAR.addAAResult(WrapperPass->getResult());
     788      138012 :   if (auto *WrapperPass =
     789      138012 :           P.getAnalysisIfAvailable<objcarc::ObjCARCAAWrapperPass>())
     790          54 :     AAR.addAAResult(WrapperPass->getResult());
     791      138012 :   if (auto *WrapperPass = P.getAnalysisIfAvailable<GlobalsAAWrapperPass>())
     792      110677 :     AAR.addAAResult(WrapperPass->getResult());
     793      138012 :   if (auto *WrapperPass = P.getAnalysisIfAvailable<CFLAndersAAWrapperPass>())
     794           0 :     AAR.addAAResult(WrapperPass->getResult());
     795      138012 :   if (auto *WrapperPass = P.getAnalysisIfAvailable<CFLSteensAAWrapperPass>())
     796           0 :     AAR.addAAResult(WrapperPass->getResult());
     797             : 
     798      138012 :   return AAR;
     799             : }
     800             : 
     801     7631228 : bool llvm::isNoAliasCall(const Value *V) {
     802     7631228 :   if (auto CS = ImmutableCallSite(V))
     803      189173 :     return CS.hasRetAttr(Attribute::NoAlias);
     804     7442055 :   return false;
     805             : }
     806             : 
     807     1107475 : bool llvm::isNoAliasArgument(const Value *V) {
     808             :   if (const Argument *A = dyn_cast<Argument>(V))
     809      186979 :     return A->hasNoAliasAttr();
     810             :   return false;
     811             : }
     812             : 
     813    41028741 : bool llvm::isIdentifiedObject(const Value *V) {
     814             :   if (isa<AllocaInst>(V))
     815             :     return true;
     816    32982278 :   if (isa<GlobalValue>(V) && !isa<GlobalAlias>(V))
     817             :     return true;
     818     4585207 :   if (isNoAliasCall(V))
     819             :     return true;
     820             :   if (const Argument *A = dyn_cast<Argument>(V))
     821     2769427 :     return A->hasNoAliasAttr() || A->hasByValAttr();
     822             :   return false;
     823             : }
     824             : 
     825     1156450 : bool llvm::isIdentifiedFunctionLocal(const Value *V) {
     826     1110198 :   return isa<AllocaInst>(V) || isNoAliasCall(V) || isNoAliasArgument(V);
     827             : }
     828             : 
     829       16216 : void llvm::getAAResultsAnalysisUsage(AnalysisUsage &AU) {
     830             :   // This function needs to be in sync with llvm::createLegacyPMAAResults -- if
     831             :   // more alias analyses are added to llvm::createLegacyPMAAResults, they need
     832             :   // to be added here also.
     833             :   AU.addRequired<TargetLibraryInfoWrapperPass>();
     834             :   AU.addUsedIfAvailable<ScopedNoAliasAAWrapperPass>();
     835             :   AU.addUsedIfAvailable<TypeBasedAAWrapperPass>();
     836             :   AU.addUsedIfAvailable<objcarc::ObjCARCAAWrapperPass>();
     837             :   AU.addUsedIfAvailable<GlobalsAAWrapperPass>();
     838             :   AU.addUsedIfAvailable<CFLAndersAAWrapperPass>();
     839             :   AU.addUsedIfAvailable<CFLSteensAAWrapperPass>();
     840      319723 : }

Generated by: LCOV version 1.13