"Fossies" - the Fresh Open Source Software Archive

Member "clamav-0.102.3/libclamav/c++/llvm/lib/Analysis/AliasAnalysis.cpp" (12 May 2020, 12358 Bytes) of package /linux/misc/clamav-0.102.3.tar.gz:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file. For more information about "AliasAnalysis.cpp" see the Fossies "Dox" file reference documentation.

    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/Pass.h"
   29 #include "llvm/BasicBlock.h"
   30 #include "llvm/Function.h"
   31 #include "llvm/IntrinsicInst.h"
   32 #include "llvm/Instructions.h"
   33 #include "llvm/Type.h"
   34 #include "llvm/Target/TargetData.h"
   35 using namespace llvm;
   36 
   37 // Register the AliasAnalysis interface, providing a nice name to refer to.
   38 static RegisterAnalysisGroup<AliasAnalysis> Z("Alias Analysis");
   39 char AliasAnalysis::ID = 0;
   40 
   41 //===----------------------------------------------------------------------===//
   42 // Default chaining methods
   43 //===----------------------------------------------------------------------===//
   44 
   45 AliasAnalysis::AliasResult
   46 AliasAnalysis::alias(const Value *V1, unsigned V1Size,
   47                      const Value *V2, unsigned V2Size) {
   48   assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!");
   49   return AA->alias(V1, V1Size, V2, V2Size);
   50 }
   51 
   52 bool AliasAnalysis::pointsToConstantMemory(const Value *P) {
   53   assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!");
   54   return AA->pointsToConstantMemory(P);
   55 }
   56 
   57 void AliasAnalysis::deleteValue(Value *V) {
   58   assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!");
   59   AA->deleteValue(V);
   60 }
   61 
   62 void AliasAnalysis::copyValue(Value *From, Value *To) {
   63   assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!");
   64   AA->copyValue(From, To);
   65 }
   66 
   67 AliasAnalysis::ModRefResult
   68 AliasAnalysis::getModRefInfo(ImmutableCallSite CS,
   69                              const Value *P, unsigned Size) {
   70   // Don't assert AA because BasicAA calls us in order to make use of the
   71   // logic here.
   72 
   73   ModRefBehavior MRB = getModRefBehavior(CS);
   74   if (MRB == DoesNotAccessMemory)
   75     return NoModRef;
   76 
   77   ModRefResult Mask = ModRef;
   78   if (MRB == OnlyReadsMemory)
   79     Mask = Ref;
   80   else if (MRB == AliasAnalysis::AccessesArguments) {
   81     bool doesAlias = false;
   82     for (ImmutableCallSite::arg_iterator AI = CS.arg_begin(), AE = CS.arg_end();
   83          AI != AE; ++AI)
   84       if (!isNoAlias(*AI, ~0U, P, Size)) {
   85         doesAlias = true;
   86         break;
   87       }
   88 
   89     if (!doesAlias)
   90       return NoModRef;
   91   }
   92 
   93   // If P points to a constant memory location, the call definitely could not
   94   // modify the memory location.
   95   if ((Mask & Mod) && pointsToConstantMemory(P))
   96     Mask = ModRefResult(Mask & ~Mod);
   97 
   98   // If this is BasicAA, don't forward.
   99   if (!AA) return Mask;
  100 
  101   // Otherwise, fall back to the next AA in the chain. But we can merge
  102   // in any mask we've managed to compute.
  103   return ModRefResult(AA->getModRefInfo(CS, P, Size) & Mask);
  104 }
  105 
  106 AliasAnalysis::ModRefResult
  107 AliasAnalysis::getModRefInfo(ImmutableCallSite CS1, ImmutableCallSite CS2) {
  108   // Don't assert AA because BasicAA calls us in order to make use of the
  109   // logic here.
  110 
  111   // If CS1 or CS2 are readnone, they don't interact.
  112   ModRefBehavior CS1B = getModRefBehavior(CS1);
  113   if (CS1B == DoesNotAccessMemory) return NoModRef;
  114 
  115   ModRefBehavior CS2B = getModRefBehavior(CS2);
  116   if (CS2B == DoesNotAccessMemory) return NoModRef;
  117 
  118   // If they both only read from memory, there is no dependence.
  119   if (CS1B == OnlyReadsMemory && CS2B == OnlyReadsMemory)
  120     return NoModRef;
  121 
  122   AliasAnalysis::ModRefResult Mask = ModRef;
  123 
  124   // If CS1 only reads memory, the only dependence on CS2 can be
  125   // from CS1 reading memory written by CS2.
  126   if (CS1B == OnlyReadsMemory)
  127     Mask = ModRefResult(Mask & Ref);
  128 
  129   // If CS2 only access memory through arguments, accumulate the mod/ref
  130   // information from CS1's references to the memory referenced by
  131   // CS2's arguments.
  132   if (CS2B == AccessesArguments) {
  133     AliasAnalysis::ModRefResult R = NoModRef;
  134     for (ImmutableCallSite::arg_iterator
  135          I = CS2.arg_begin(), E = CS2.arg_end(); I != E; ++I) {
  136       R = ModRefResult((R | getModRefInfo(CS1, *I, UnknownSize)) & Mask);
  137       if (R == Mask)
  138         break;
  139     }
  140     return R;
  141   }
  142 
  143   // If CS1 only accesses memory through arguments, check if CS2 references
  144   // any of the memory referenced by CS1's arguments. If not, return NoModRef.
  145   if (CS1B == AccessesArguments) {
  146     AliasAnalysis::ModRefResult R = NoModRef;
  147     for (ImmutableCallSite::arg_iterator
  148          I = CS1.arg_begin(), E = CS1.arg_end(); I != E; ++I)
  149       if (getModRefInfo(CS2, *I, UnknownSize) != NoModRef) {
  150         R = Mask;
  151         break;
  152       }
  153     if (R == NoModRef)
  154       return R;
  155   }
  156 
  157   // If this is BasicAA, don't forward.
  158   if (!AA) return Mask;
  159 
  160   // Otherwise, fall back to the next AA in the chain. But we can merge
  161   // in any mask we've managed to compute.
  162   return ModRefResult(AA->getModRefInfo(CS1, CS2) & Mask);
  163 }
  164 
  165 AliasAnalysis::ModRefBehavior
  166 AliasAnalysis::getModRefBehavior(ImmutableCallSite CS) {
  167   // Don't assert AA because BasicAA calls us in order to make use of the
  168   // logic here.
  169 
  170   ModRefBehavior Min = UnknownModRefBehavior;
  171 
  172   // Call back into the alias analysis with the other form of getModRefBehavior
  173   // to see if it can give a better response.
  174   if (const Function *F = CS.getCalledFunction())
  175     Min = getModRefBehavior(F);
  176 
  177   // If this is BasicAA, don't forward.
  178   if (!AA) return Min;
  179 
  180   // Otherwise, fall back to the next AA in the chain. But we can merge
  181   // in any result we've managed to compute.
  182   return std::min(AA->getModRefBehavior(CS), Min);
  183 }
  184 
  185 AliasAnalysis::ModRefBehavior
  186 AliasAnalysis::getModRefBehavior(const Function *F) {
  187   assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!");
  188   return AA->getModRefBehavior(F);
  189 }
  190 
  191 
  192 //===----------------------------------------------------------------------===//
  193 // AliasAnalysis non-virtual helper method implementation
  194 //===----------------------------------------------------------------------===//
  195 
  196 AliasAnalysis::ModRefResult
  197 AliasAnalysis::getModRefInfo(const LoadInst *L, const Value *P, unsigned Size) {
  198   // Be conservative in the face of volatile.
  199   if (L->isVolatile())
  200     return ModRef;
  201 
  202   // If the load address doesn't alias the given address, it doesn't read
  203   // or write the specified memory.
  204   if (!alias(L->getOperand(0), getTypeStoreSize(L->getType()), P, Size))
  205     return NoModRef;
  206 
  207   // Otherwise, a load just reads.
  208   return Ref;
  209 }
  210 
  211 AliasAnalysis::ModRefResult
  212 AliasAnalysis::getModRefInfo(const StoreInst *S, const Value *P, unsigned Size) {
  213   // Be conservative in the face of volatile.
  214   if (S->isVolatile())
  215     return ModRef;
  216 
  217   // If the store address cannot alias the pointer in question, then the
  218   // specified memory cannot be modified by the store.
  219   if (!alias(S->getOperand(1),
  220              getTypeStoreSize(S->getOperand(0)->getType()), P, Size))
  221     return NoModRef;
  222 
  223   // If the pointer is a pointer to constant memory, then it could not have been
  224   // modified by this store.
  225   if (pointsToConstantMemory(P))
  226     return NoModRef;
  227 
  228   // Otherwise, a store just writes.
  229   return Mod;
  230 }
  231 
  232 AliasAnalysis::ModRefResult
  233 AliasAnalysis::getModRefInfo(const VAArgInst *V, const Value *P, unsigned Size) {
  234   // If the va_arg address cannot alias the pointer in question, then the
  235   // specified memory cannot be accessed by the va_arg.
  236   if (!alias(V->getOperand(0), UnknownSize, P, Size))
  237     return NoModRef;
  238 
  239   // If the pointer is a pointer to constant memory, then it could not have been
  240   // modified by this va_arg.
  241   if (pointsToConstantMemory(P))
  242     return NoModRef;
  243 
  244   // Otherwise, a va_arg reads and writes.
  245   return ModRef;
  246 }
  247 
  248 
  249 AliasAnalysis::ModRefBehavior
  250 AliasAnalysis::getIntrinsicModRefBehavior(unsigned iid) {
  251 #define GET_INTRINSIC_MODREF_BEHAVIOR
  252 #include "llvm/Intrinsics.gen"
  253 #undef GET_INTRINSIC_MODREF_BEHAVIOR
  254 }
  255 
  256 // AliasAnalysis destructor: DO NOT move this to the header file for
  257 // AliasAnalysis or else clients of the AliasAnalysis class may not depend on
  258 // the AliasAnalysis.o file in the current .a file, causing alias analysis
  259 // support to not be included in the tool correctly!
  260 //
  261 AliasAnalysis::~AliasAnalysis() {}
  262 
  263 /// InitializeAliasAnalysis - Subclasses must call this method to initialize the
  264 /// AliasAnalysis interface before any other methods are called.
  265 ///
  266 void AliasAnalysis::InitializeAliasAnalysis(Pass *P) {
  267   TD = P->getAnalysisIfAvailable<TargetData>();
  268   AA = &P->getAnalysis<AliasAnalysis>();
  269 }
  270 
  271 // getAnalysisUsage - All alias analysis implementations should invoke this
  272 // directly (using AliasAnalysis::getAnalysisUsage(AU)).
  273 void AliasAnalysis::getAnalysisUsage(AnalysisUsage &AU) const {
  274   AU.addRequired<AliasAnalysis>();         // All AA's chain
  275 }
  276 
  277 /// getTypeStoreSize - Return the TargetData store size for the given type,
  278 /// if known, or a conservative value otherwise.
  279 ///
  280 unsigned AliasAnalysis::getTypeStoreSize(const Type *Ty) {
  281   return TD ? TD->getTypeStoreSize(Ty) : ~0u;
  282 }
  283 
  284 /// canBasicBlockModify - Return true if it is possible for execution of the
  285 /// specified basic block to modify the value pointed to by Ptr.
  286 ///
  287 bool AliasAnalysis::canBasicBlockModify(const BasicBlock &BB,
  288                                         const Value *Ptr, unsigned Size) {
  289   return canInstructionRangeModify(BB.front(), BB.back(), Ptr, Size);
  290 }
  291 
  292 /// canInstructionRangeModify - Return true if it is possible for the execution
  293 /// of the specified instructions to modify the value pointed to by Ptr.  The
  294 /// instructions to consider are all of the instructions in the range of [I1,I2]
  295 /// INCLUSIVE.  I1 and I2 must be in the same basic block.
  296 ///
  297 bool AliasAnalysis::canInstructionRangeModify(const Instruction &I1,
  298                                               const Instruction &I2,
  299                                               const Value *Ptr, unsigned Size) {
  300   assert(I1.getParent() == I2.getParent() &&
  301          "Instructions not in same basic block!");
  302   BasicBlock::const_iterator I = &I1;
  303   BasicBlock::const_iterator E = &I2;
  304   ++E;  // Convert from inclusive to exclusive range.
  305 
  306   for (; I != E; ++I) // Check every instruction in range
  307     if (getModRefInfo(I, Ptr, Size) & Mod)
  308       return true;
  309   return false;
  310 }
  311 
  312 /// isNoAliasCall - Return true if this pointer is returned by a noalias
  313 /// function.
  314 bool llvm::isNoAliasCall(const Value *V) {
  315   if (isa<CallInst>(V) || isa<InvokeInst>(V))
  316     return ImmutableCallSite(cast<Instruction>(V))
  317       .paramHasAttr(0, Attribute::NoAlias);
  318   return false;
  319 }
  320 
  321 /// isIdentifiedObject - Return true if this pointer refers to a distinct and
  322 /// identifiable object.  This returns true for:
  323 ///    Global Variables and Functions (but not Global Aliases)
  324 ///    Allocas and Mallocs
  325 ///    ByVal and NoAlias Arguments
  326 ///    NoAlias returns
  327 ///
  328 bool llvm::isIdentifiedObject(const Value *V) {
  329   if (isa<AllocaInst>(V))
  330     return true;
  331   if (isa<GlobalValue>(V) && !isa<GlobalAlias>(V))
  332     return true;
  333   if (isNoAliasCall(V))
  334     return true;
  335   if (const Argument *A = dyn_cast<Argument>(V))
  336     return A->hasNoAliasAttr() || A->hasByValAttr();
  337   return false;
  338 }
  339 
  340 // Because of the way .a files work, we must force the BasicAA implementation to
  341 // be pulled in if the AliasAnalysis classes are pulled in.  Otherwise we run
  342 // the risk of AliasAnalysis being used, but the default implementation not
  343 // being linked into the tool that uses it.
  344 DEFINING_FILE_FOR(AliasAnalysis)