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#include "llvm/Analysis/TargetLibraryInfo.h"
24using namespace llvm;
25
26AliasResult SCEVAAResult::alias(const MemoryLocation &LocA,
27                                const MemoryLocation &LocB) {
28  // If either of the memory references is empty, it doesn't matter what the
29  // pointer values are. This allows the code below to ignore this special
30  // case.
31  if (LocA.Size == 0 || LocB.Size == 0)
32    return NoAlias;
33
34  // This is SCEVAAResult. Get the SCEVs!
35  const SCEV *AS = SE.getSCEV(const_cast<Value *>(LocA.Ptr));
36  const SCEV *BS = SE.getSCEV(const_cast<Value *>(LocB.Ptr));
37
38  // If they evaluate to the same expression, it's a MustAlias.
39  if (AS == BS)
40    return MustAlias;
41
42  // If something is known about the difference between the two addresses,
43  // see if it's enough to prove a NoAlias.
44  if (SE.getEffectiveSCEVType(AS->getType()) ==
45      SE.getEffectiveSCEVType(BS->getType())) {
46    unsigned BitWidth = SE.getTypeSizeInBits(AS->getType());
47    APInt ASizeInt(BitWidth, LocA.Size);
48    APInt BSizeInt(BitWidth, LocB.Size);
49
50    // Compute the difference between the two pointers.
51    const SCEV *BA = SE.getMinusSCEV(BS, AS);
52
53    // Test whether the difference is known to be great enough that memory of
54    // the given sizes don't overlap. This assumes that ASizeInt and BSizeInt
55    // are non-zero, which is special-cased above.
56    if (ASizeInt.ule(SE.getUnsignedRange(BA).getUnsignedMin()) &&
57        (-BSizeInt).uge(SE.getUnsignedRange(BA).getUnsignedMax()))
58      return NoAlias;
59
60    // Folding the subtraction while preserving range information can be tricky
61    // (because of INT_MIN, etc.); if the prior test failed, swap AS and BS
62    // and try again to see if things fold better that way.
63
64    // Compute the difference between the two pointers.
65    const SCEV *AB = SE.getMinusSCEV(AS, BS);
66
67    // Test whether the difference is known to be great enough that memory of
68    // the given sizes don't overlap. This assumes that ASizeInt and BSizeInt
69    // are non-zero, which is special-cased above.
70    if (BSizeInt.ule(SE.getUnsignedRange(AB).getUnsignedMin()) &&
71        (-ASizeInt).uge(SE.getUnsignedRange(AB).getUnsignedMax()))
72      return NoAlias;
73  }
74
75  // If ScalarEvolution can find an underlying object, form a new query.
76  // The correctness of this depends on ScalarEvolution not recognizing
77  // inttoptr and ptrtoint operators.
78  Value *AO = GetBaseValue(AS);
79  Value *BO = GetBaseValue(BS);
80  if ((AO && AO != LocA.Ptr) || (BO && BO != LocB.Ptr))
81    if (alias(MemoryLocation(AO ? AO : LocA.Ptr,
82                             AO ? +MemoryLocation::UnknownSize : LocA.Size,
83                             AO ? AAMDNodes() : LocA.AATags),
84              MemoryLocation(BO ? BO : LocB.Ptr,
85                             BO ? +MemoryLocation::UnknownSize : LocB.Size,
86                             BO ? AAMDNodes() : LocB.AATags)) == NoAlias)
87      return NoAlias;
88
89  // Forward the query to the next analysis.
90  return AAResultBase::alias(LocA, LocB);
91}
92
93/// Given an expression, try to find a base value.
94///
95/// Returns null if none was found.
96Value *SCEVAAResult::GetBaseValue(const SCEV *S) {
97  if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S)) {
98    // In an addrec, assume that the base will be in the start, rather
99    // than the step.
100    return GetBaseValue(AR->getStart());
101  } else if (const SCEVAddExpr *A = dyn_cast<SCEVAddExpr>(S)) {
102    // If there's a pointer operand, it'll be sorted at the end of the list.
103    const SCEV *Last = A->getOperand(A->getNumOperands() - 1);
104    if (Last->getType()->isPointerTy())
105      return GetBaseValue(Last);
106  } else if (const SCEVUnknown *U = dyn_cast<SCEVUnknown>(S)) {
107    // This is a leaf node.
108    return U->getValue();
109  }
110  // No Identified object found.
111  return nullptr;
112}
113
114SCEVAAResult SCEVAA::run(Function &F, AnalysisManager<Function> *AM) {
115  return SCEVAAResult(AM->getResult<TargetLibraryAnalysis>(F),
116                      AM->getResult<ScalarEvolutionAnalysis>(F));
117}
118
119char SCEVAA::PassID;
120
121char SCEVAAWrapperPass::ID = 0;
122INITIALIZE_PASS_BEGIN(SCEVAAWrapperPass, "scev-aa",
123                      "ScalarEvolution-based Alias Analysis", false, true)
124INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass)
125INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
126INITIALIZE_PASS_END(SCEVAAWrapperPass, "scev-aa",
127                    "ScalarEvolution-based Alias Analysis", false, true)
128
129FunctionPass *llvm::createSCEVAAWrapperPass() {
130  return new SCEVAAWrapperPass();
131}
132
133SCEVAAWrapperPass::SCEVAAWrapperPass() : FunctionPass(ID) {
134  initializeSCEVAAWrapperPassPass(*PassRegistry::getPassRegistry());
135}
136
137bool SCEVAAWrapperPass::runOnFunction(Function &F) {
138  Result.reset(
139      new SCEVAAResult(getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(),
140                       getAnalysis<ScalarEvolutionWrapperPass>().getSE()));
141  return false;
142}
143
144void SCEVAAWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
145  AU.setPreservesAll();
146  AU.addRequired<ScalarEvolutionWrapperPass>();
147  AU.addRequired<TargetLibraryInfoWrapperPass>();
148}
149