llvm.org GIT mirror llvm / release_60 lib / Analysis / ScalarEvolutionAliasAnalysis.cpp
release_60

Tree @release_60 (Download .tar.gz)

ScalarEvolutionAliasAnalysis.cpp @release_60

2385e0e
 
 
 
 
 
 
 
 
 
 
 
7cbf5a8
 
4f46e14
7cbf5a8
2385e0e
 
 
 
 
217849d
2385e0e
 
9146833
 
49bda91
 
 
b2143b6
49bda91
 
9146833
 
 
2385e0e
 
72644df
 
2385e0e
 
 
9146833
 
 
b2143b6
 
49bda91
 
9146833
49bda91
 
 
 
9146833
 
49bda91
 
 
 
 
 
 
9146833
49bda91
 
 
 
9146833
 
49bda91
2385e0e
 
 
 
 
576fd76
 
b2143b6
2cdca0c
 
4d7ed39
2cdca0c
 
4d7ed39
2385e0e
 
 
9146833
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
33d5681
e95015f
20b343c
8e27cb2
9146833
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
cf88e92
9146833
 
 
 
 
 
2385e0e
//===- ScalarEvolutionAliasAnalysis.cpp - SCEV-based Alias Analysis -------===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This file defines the ScalarEvolutionAliasAnalysis pass, which implements a
// simple alias analysis implemented in terms of ScalarEvolution queries.
//
// This differs from traditional loop dependence analysis in that it tests
// for dependencies within a single iteration of a loop, rather than
// dependencies between different iterations.
//
// ScalarEvolution has a more complete understanding of pointer arithmetic
// than BasicAliasAnalysis' collection of ad-hoc analyses.
//
//===----------------------------------------------------------------------===//

#include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h"
using namespace llvm;

AliasResult SCEVAAResult::alias(const MemoryLocation &LocA,
                                const MemoryLocation &LocB) {
  // If either of the memory references is empty, it doesn't matter what the
  // pointer values are. This allows the code below to ignore this special
  // case.
  if (LocA.Size == 0 || LocB.Size == 0)
    return NoAlias;

  // This is SCEVAAResult. Get the SCEVs!
  const SCEV *AS = SE.getSCEV(const_cast<Value *>(LocA.Ptr));
  const SCEV *BS = SE.getSCEV(const_cast<Value *>(LocB.Ptr));

  // If they evaluate to the same expression, it's a MustAlias.
  if (AS == BS)
    return MustAlias;

  // If something is known about the difference between the two addresses,
  // see if it's enough to prove a NoAlias.
  if (SE.getEffectiveSCEVType(AS->getType()) ==
      SE.getEffectiveSCEVType(BS->getType())) {
    unsigned BitWidth = SE.getTypeSizeInBits(AS->getType());
    APInt ASizeInt(BitWidth, LocA.Size);
    APInt BSizeInt(BitWidth, LocB.Size);

    // Compute the difference between the two pointers.
    const SCEV *BA = SE.getMinusSCEV(BS, AS);

    // Test whether the difference is known to be great enough that memory of
    // the given sizes don't overlap. This assumes that ASizeInt and BSizeInt
    // are non-zero, which is special-cased above.
    if (ASizeInt.ule(SE.getUnsignedRange(BA).getUnsignedMin()) &&
        (-BSizeInt).uge(SE.getUnsignedRange(BA).getUnsignedMax()))
      return NoAlias;

    // Folding the subtraction while preserving range information can be tricky
    // (because of INT_MIN, etc.); if the prior test failed, swap AS and BS
    // and try again to see if things fold better that way.

    // Compute the difference between the two pointers.
    const SCEV *AB = SE.getMinusSCEV(AS, BS);

    // Test whether the difference is known to be great enough that memory of
    // the given sizes don't overlap. This assumes that ASizeInt and BSizeInt
    // are non-zero, which is special-cased above.
    if (BSizeInt.ule(SE.getUnsignedRange(AB).getUnsignedMin()) &&
        (-ASizeInt).uge(SE.getUnsignedRange(AB).getUnsignedMax()))
      return NoAlias;
  }

  // If ScalarEvolution can find an underlying object, form a new query.
  // The correctness of this depends on ScalarEvolution not recognizing
  // inttoptr and ptrtoint operators.
  Value *AO = GetBaseValue(AS);
  Value *BO = GetBaseValue(BS);
  if ((AO && AO != LocA.Ptr) || (BO && BO != LocB.Ptr))
    if (alias(MemoryLocation(AO ? AO : LocA.Ptr,
                             AO ? +MemoryLocation::UnknownSize : LocA.Size,
                             AO ? AAMDNodes() : LocA.AATags),
              MemoryLocation(BO ? BO : LocB.Ptr,
                             BO ? +MemoryLocation::UnknownSize : LocB.Size,
                             BO ? AAMDNodes() : LocB.AATags)) == NoAlias)
      return NoAlias;

  // Forward the query to the next analysis.
  return AAResultBase::alias(LocA, LocB);
}

/// Given an expression, try to find a base value.
///
/// Returns null if none was found.
Value *SCEVAAResult::GetBaseValue(const SCEV *S) {
  if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S)) {
    // In an addrec, assume that the base will be in the start, rather
    // than the step.
    return GetBaseValue(AR->getStart());
  } else if (const SCEVAddExpr *A = dyn_cast<SCEVAddExpr>(S)) {
    // If there's a pointer operand, it'll be sorted at the end of the list.
    const SCEV *Last = A->getOperand(A->getNumOperands() - 1);
    if (Last->getType()->isPointerTy())
      return GetBaseValue(Last);
  } else if (const SCEVUnknown *U = dyn_cast<SCEVUnknown>(S)) {
    // This is a leaf node.
    return U->getValue();
  }
  // No Identified object found.
  return nullptr;
}

AnalysisKey SCEVAA::Key;

SCEVAAResult SCEVAA::run(Function &F, FunctionAnalysisManager &AM) {
  return SCEVAAResult(AM.getResult<ScalarEvolutionAnalysis>(F));
}

char SCEVAAWrapperPass::ID = 0;
INITIALIZE_PASS_BEGIN(SCEVAAWrapperPass, "scev-aa",
                      "ScalarEvolution-based Alias Analysis", false, true)
INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass)
INITIALIZE_PASS_END(SCEVAAWrapperPass, "scev-aa",
                    "ScalarEvolution-based Alias Analysis", false, true)

FunctionPass *llvm::createSCEVAAWrapperPass() {
  return new SCEVAAWrapperPass();
}

SCEVAAWrapperPass::SCEVAAWrapperPass() : FunctionPass(ID) {
  initializeSCEVAAWrapperPassPass(*PassRegistry::getPassRegistry());
}

bool SCEVAAWrapperPass::runOnFunction(Function &F) {
  Result.reset(
      new SCEVAAResult(getAnalysis<ScalarEvolutionWrapperPass>().getSE()));
  return false;
}

void SCEVAAWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
  AU.setPreservesAll();
  AU.addRequired<ScalarEvolutionWrapperPass>();
}