LCOV - code coverage report
Current view: top level - lib/Analysis - ScalarEvolutionAliasAnalysis.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 49 51 96.1 %
Date: 2017-09-14 15:23:50 Functions: 8 9 88.9 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : //===- ScalarEvolutionAliasAnalysis.cpp - SCEV-based Alias Analysis -------===//
       2             : //
       3             : //                     The LLVM Compiler Infrastructure
       4             : //
       5             : // This file is distributed under the University of Illinois Open Source
       6             : // License. See LICENSE.TXT for details.
       7             : //
       8             : //===----------------------------------------------------------------------===//
       9             : //
      10             : // This file defines the ScalarEvolutionAliasAnalysis pass, which implements a
      11             : // simple alias analysis implemented in terms of ScalarEvolution queries.
      12             : //
      13             : // This differs from traditional loop dependence analysis in that it tests
      14             : // for dependencies within a single iteration of a loop, rather than
      15             : // dependencies between different iterations.
      16             : //
      17             : // ScalarEvolution has a more complete understanding of pointer arithmetic
      18             : // than BasicAliasAnalysis' collection of ad-hoc analyses.
      19             : //
      20             : //===----------------------------------------------------------------------===//
      21             : 
      22             : #include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h"
      23             : using namespace llvm;
      24             : 
      25         180 : AliasResult SCEVAAResult::alias(const MemoryLocation &LocA,
      26             :                                 const MemoryLocation &LocB) {
      27             :   // If either of the memory references is empty, it doesn't matter what the
      28             :   // pointer values are. This allows the code below to ignore this special
      29             :   // case.
      30         180 :   if (LocA.Size == 0 || LocB.Size == 0)
      31             :     return NoAlias;
      32             : 
      33             :   // This is SCEVAAResult. Get the SCEVs!
      34         180 :   const SCEV *AS = SE.getSCEV(const_cast<Value *>(LocA.Ptr));
      35         180 :   const SCEV *BS = SE.getSCEV(const_cast<Value *>(LocB.Ptr));
      36             : 
      37             :   // If they evaluate to the same expression, it's a MustAlias.
      38         180 :   if (AS == BS)
      39             :     return MustAlias;
      40             : 
      41             :   // If something is known about the difference between the two addresses,
      42             :   // see if it's enough to prove a NoAlias.
      43         184 :   if (SE.getEffectiveSCEVType(AS->getType()) ==
      44          92 :       SE.getEffectiveSCEVType(BS->getType())) {
      45          92 :     unsigned BitWidth = SE.getTypeSizeInBits(AS->getType());
      46         248 :     APInt ASizeInt(BitWidth, LocA.Size);
      47         248 :     APInt BSizeInt(BitWidth, LocB.Size);
      48             : 
      49             :     // Compute the difference between the two pointers.
      50          92 :     const SCEV *BA = SE.getMinusSCEV(BS, AS);
      51             : 
      52             :     // Test whether the difference is known to be great enough that memory of
      53             :     // the given sizes don't overlap. This assumes that ASizeInt and BSizeInt
      54             :     // are non-zero, which is special-cased above.
      55         484 :     if (ASizeInt.ule(SE.getUnsignedRange(BA).getUnsignedMin()) &&
      56         600 :         (-BSizeInt).uge(SE.getUnsignedRange(BA).getUnsignedMax()))
      57          28 :       return NoAlias;
      58             : 
      59             :     // Folding the subtraction while preserving range information can be tricky
      60             :     // (because of INT_MIN, etc.); if the prior test failed, swap AS and BS
      61             :     // and try again to see if things fold better that way.
      62             : 
      63             :     // Compute the difference between the two pointers.
      64          66 :     const SCEV *AB = SE.getMinusSCEV(AS, BS);
      65             : 
      66             :     // Test whether the difference is known to be great enough that memory of
      67             :     // the given sizes don't overlap. This assumes that ASizeInt and BSizeInt
      68             :     // are non-zero, which is special-cased above.
      69         268 :     if (BSizeInt.ule(SE.getUnsignedRange(AB).getUnsignedMin()) &&
      70         272 :         (-ASizeInt).uge(SE.getUnsignedRange(AB).getUnsignedMax()))
      71             :       return NoAlias;
      72             :   }
      73             : 
      74             :   // If ScalarEvolution can find an underlying object, form a new query.
      75             :   // The correctness of this depends on ScalarEvolution not recognizing
      76             :   // inttoptr and ptrtoint operators.
      77          64 :   Value *AO = GetBaseValue(AS);
      78          64 :   Value *BO = GetBaseValue(BS);
      79          64 :   if ((AO && AO != LocA.Ptr) || (BO && BO != LocB.Ptr))
      80         168 :     if (alias(MemoryLocation(AO ? AO : LocA.Ptr,
      81             :                              AO ? +MemoryLocation::UnknownSize : LocA.Size,
      82          56 :                              AO ? AAMDNodes() : LocA.AATags),
      83         168 :               MemoryLocation(BO ? BO : LocB.Ptr,
      84             :                              BO ? +MemoryLocation::UnknownSize : LocB.Size,
      85          56 :                              BO ? AAMDNodes() : LocB.AATags)) == NoAlias)
      86             :       return NoAlias;
      87             : 
      88             :   // Forward the query to the next analysis.
      89          64 :   return AAResultBase::alias(LocA, LocB);
      90             : }
      91             : 
      92             : /// Given an expression, try to find a base value.
      93             : ///
      94             : /// Returns null if none was found.
      95         128 : Value *SCEVAAResult::GetBaseValue(const SCEV *S) {
      96          44 :   if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S)) {
      97             :     // In an addrec, assume that the base will be in the start, rather
      98             :     // than the step.
      99          44 :     return GetBaseValue(AR->getStart());
     100          56 :   } else if (const SCEVAddExpr *A = dyn_cast<SCEVAddExpr>(S)) {
     101             :     // If there's a pointer operand, it'll be sorted at the end of the list.
     102         112 :     const SCEV *Last = A->getOperand(A->getNumOperands() - 1);
     103         112 :     if (Last->getType()->isPointerTy())
     104             :       return GetBaseValue(Last);
     105         128 :   } else if (const SCEVUnknown *U = dyn_cast<SCEVUnknown>(S)) {
     106             :     // This is a leaf node.
     107         128 :     return U->getValue();
     108             :   }
     109             :   // No Identified object found.
     110             :   return nullptr;
     111             : }
     112             : 
     113             : AnalysisKey SCEVAA::Key;
     114             : 
     115           6 : SCEVAAResult SCEVAA::run(Function &F, FunctionAnalysisManager &AM) {
     116          12 :   return SCEVAAResult(AM.getResult<ScalarEvolutionAnalysis>(F));
     117             : }
     118             : 
     119             : char SCEVAAWrapperPass::ID = 0;
     120       53265 : INITIALIZE_PASS_BEGIN(SCEVAAWrapperPass, "scev-aa",
     121             :                       "ScalarEvolution-based Alias Analysis", false, true)
     122       53265 : INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass)
     123     1468995 : INITIALIZE_PASS_END(SCEVAAWrapperPass, "scev-aa",
     124             :                     "ScalarEvolution-based Alias Analysis", false, true)
     125             : 
     126           0 : FunctionPass *llvm::createSCEVAAWrapperPass() {
     127           0 :   return new SCEVAAWrapperPass();
     128             : }
     129             : 
     130          24 : SCEVAAWrapperPass::SCEVAAWrapperPass() : FunctionPass(ID) {
     131           8 :   initializeSCEVAAWrapperPassPass(*PassRegistry::getPassRegistry());
     132           8 : }
     133             : 
     134          13 : bool SCEVAAWrapperPass::runOnFunction(Function &F) {
     135          39 :   Result.reset(
     136          39 :       new SCEVAAResult(getAnalysis<ScalarEvolutionWrapperPass>().getSE()));
     137          13 :   return false;
     138             : }
     139             : 
     140           8 : void SCEVAAWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
     141          16 :   AU.setPreservesAll();
     142           8 :   AU.addRequired<ScalarEvolutionWrapperPass>();
     143           8 : }

Generated by: LCOV version 1.13