Dan Gohman | 2385e0e | 2009-08-26 14:53:06 +0000 | [diff] [blame] | 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 | // ScalarEvolution has a more complete understanding of pointer arithmetic |
| 14 | // than BasicAliasAnalysis' collection of ad-hoc analyses. |
| 15 | // |
| 16 | //===----------------------------------------------------------------------===// |
| 17 | |
| 18 | #include "llvm/Analysis/AliasAnalysis.h" |
| 19 | #include "llvm/Analysis/ScalarEvolutionExpressions.h" |
| 20 | #include "llvm/Analysis/Passes.h" |
| 21 | #include "llvm/Pass.h" |
Dan Gohman | 2385e0e | 2009-08-26 14:53:06 +0000 | [diff] [blame] | 22 | using namespace llvm; |
| 23 | |
| 24 | namespace { |
| 25 | /// ScalarEvolutionAliasAnalysis - This is a simple alias analysis |
| 26 | /// implementation that uses ScalarEvolution to answer queries. |
Nick Lewycky | 6726b6d | 2009-10-25 06:33:48 +0000 | [diff] [blame] | 27 | class ScalarEvolutionAliasAnalysis : public FunctionPass, |
| 28 | public AliasAnalysis { |
Dan Gohman | 2385e0e | 2009-08-26 14:53:06 +0000 | [diff] [blame] | 29 | ScalarEvolution *SE; |
| 30 | |
| 31 | public: |
| 32 | static char ID; // Class identification, replacement for typeinfo |
| 33 | ScalarEvolutionAliasAnalysis() : FunctionPass(&ID), SE(0) {} |
| 34 | |
| 35 | private: |
| 36 | virtual void getAnalysisUsage(AnalysisUsage &AU) const; |
| 37 | virtual bool runOnFunction(Function &F); |
| 38 | virtual AliasResult alias(const Value *V1, unsigned V1Size, |
| 39 | const Value *V2, unsigned V2Size); |
| 40 | |
Dan Gohman | 576fd76 | 2009-10-31 14:32:25 +0000 | [diff] [blame] | 41 | Value *GetBaseValue(const SCEV *S); |
Dan Gohman | 2385e0e | 2009-08-26 14:53:06 +0000 | [diff] [blame] | 42 | }; |
| 43 | } // End of anonymous namespace |
| 44 | |
| 45 | // Register this pass... |
| 46 | char ScalarEvolutionAliasAnalysis::ID = 0; |
| 47 | static RegisterPass<ScalarEvolutionAliasAnalysis> |
| 48 | X("scev-aa", "ScalarEvolution-based Alias Analysis", false, true); |
| 49 | |
| 50 | // Declare that we implement the AliasAnalysis interface |
| 51 | static RegisterAnalysisGroup<AliasAnalysis> Y(X); |
| 52 | |
| 53 | FunctionPass *llvm::createScalarEvolutionAliasAnalysisPass() { |
| 54 | return new ScalarEvolutionAliasAnalysis(); |
| 55 | } |
| 56 | |
| 57 | void |
| 58 | ScalarEvolutionAliasAnalysis::getAnalysisUsage(AnalysisUsage &AU) const { |
| 59 | AU.addRequiredTransitive<ScalarEvolution>(); |
| 60 | AU.setPreservesAll(); |
| 61 | AliasAnalysis::getAnalysisUsage(AU); |
| 62 | } |
| 63 | |
| 64 | bool |
| 65 | ScalarEvolutionAliasAnalysis::runOnFunction(Function &F) { |
| 66 | InitializeAliasAnalysis(this); |
| 67 | SE = &getAnalysis<ScalarEvolution>(); |
| 68 | return false; |
| 69 | } |
| 70 | |
Dan Gohman | 576fd76 | 2009-10-31 14:32:25 +0000 | [diff] [blame] | 71 | /// GetBaseValue - Given an expression, try to find a |
| 72 | /// base value. Return null is none was found. |
Dan Gohman | 2385e0e | 2009-08-26 14:53:06 +0000 | [diff] [blame] | 73 | Value * |
Dan Gohman | 576fd76 | 2009-10-31 14:32:25 +0000 | [diff] [blame] | 74 | ScalarEvolutionAliasAnalysis::GetBaseValue(const SCEV *S) { |
Dan Gohman | 2385e0e | 2009-08-26 14:53:06 +0000 | [diff] [blame] | 75 | if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S)) { |
Dan Gohman | ed77e52 | 2009-08-29 23:36:57 +0000 | [diff] [blame] | 76 | // In an addrec, assume that the base will be in the start, rather |
| 77 | // than the step. |
Dan Gohman | 576fd76 | 2009-10-31 14:32:25 +0000 | [diff] [blame] | 78 | return GetBaseValue(AR->getStart()); |
Dan Gohman | 2385e0e | 2009-08-26 14:53:06 +0000 | [diff] [blame] | 79 | } else if (const SCEVAddExpr *A = dyn_cast<SCEVAddExpr>(S)) { |
| 80 | // If there's a pointer operand, it'll be sorted at the end of the list. |
| 81 | const SCEV *Last = A->getOperand(A->getNumOperands()-1); |
| 82 | if (isa<PointerType>(Last->getType())) |
Dan Gohman | 576fd76 | 2009-10-31 14:32:25 +0000 | [diff] [blame] | 83 | return GetBaseValue(Last); |
Dan Gohman | 2385e0e | 2009-08-26 14:53:06 +0000 | [diff] [blame] | 84 | } else if (const SCEVUnknown *U = dyn_cast<SCEVUnknown>(S)) { |
Dan Gohman | 576fd76 | 2009-10-31 14:32:25 +0000 | [diff] [blame] | 85 | // This is a leaf node. |
| 86 | return U->getValue(); |
Dan Gohman | 2385e0e | 2009-08-26 14:53:06 +0000 | [diff] [blame] | 87 | } |
| 88 | // No Identified object found. |
| 89 | return 0; |
| 90 | } |
| 91 | |
| 92 | AliasAnalysis::AliasResult |
| 93 | ScalarEvolutionAliasAnalysis::alias(const Value *A, unsigned ASize, |
| 94 | const Value *B, unsigned BSize) { |
| 95 | // This is ScalarEvolutionAliasAnalysis. Get the SCEVs! |
| 96 | const SCEV *AS = SE->getSCEV(const_cast<Value *>(A)); |
| 97 | const SCEV *BS = SE->getSCEV(const_cast<Value *>(B)); |
| 98 | |
| 99 | // If they evaluate to the same expression, it's a MustAlias. |
| 100 | if (AS == BS) return MustAlias; |
| 101 | |
| 102 | // If something is known about the difference between the two addresses, |
| 103 | // see if it's enough to prove a NoAlias. |
| 104 | if (SE->getEffectiveSCEVType(AS->getType()) == |
| 105 | SE->getEffectiveSCEVType(BS->getType())) { |
| 106 | unsigned BitWidth = SE->getTypeSizeInBits(AS->getType()); |
| 107 | APInt AI(BitWidth, ASize); |
| 108 | const SCEV *BA = SE->getMinusSCEV(BS, AS); |
| 109 | if (AI.ule(SE->getUnsignedRange(BA).getUnsignedMin())) { |
| 110 | APInt BI(BitWidth, BSize); |
| 111 | const SCEV *AB = SE->getMinusSCEV(AS, BS); |
| 112 | if (BI.ule(SE->getUnsignedRange(AB).getUnsignedMin())) |
| 113 | return NoAlias; |
| 114 | } |
| 115 | } |
| 116 | |
| 117 | // If ScalarEvolution can find an underlying object, form a new query. |
| 118 | // The correctness of this depends on ScalarEvolution not recognizing |
| 119 | // inttoptr and ptrtoint operators. |
Dan Gohman | 576fd76 | 2009-10-31 14:32:25 +0000 | [diff] [blame] | 120 | Value *AO = GetBaseValue(AS); |
| 121 | Value *BO = GetBaseValue(BS); |
Dan Gohman | 2385e0e | 2009-08-26 14:53:06 +0000 | [diff] [blame] | 122 | if ((AO && AO != A) || (BO && BO != B)) |
| 123 | if (alias(AO ? AO : A, AO ? ~0u : ASize, |
| 124 | BO ? BO : B, BO ? ~0u : BSize) == NoAlias) |
| 125 | return NoAlias; |
| 126 | |
| 127 | // Forward the query to the next analysis. |
| 128 | return AliasAnalysis::alias(A, ASize, B, BSize); |
| 129 | } |