12385e0e22ca482f2896dfa975a08db2f54926c09Dan Gohman//===- ScalarEvolutionAliasAnalysis.cpp - SCEV-based Alias Analysis -------===// 22385e0e22ca482f2896dfa975a08db2f54926c09Dan Gohman// 32385e0e22ca482f2896dfa975a08db2f54926c09Dan Gohman// The LLVM Compiler Infrastructure 42385e0e22ca482f2896dfa975a08db2f54926c09Dan Gohman// 52385e0e22ca482f2896dfa975a08db2f54926c09Dan Gohman// This file is distributed under the University of Illinois Open Source 62385e0e22ca482f2896dfa975a08db2f54926c09Dan Gohman// License. See LICENSE.TXT for details. 72385e0e22ca482f2896dfa975a08db2f54926c09Dan Gohman// 82385e0e22ca482f2896dfa975a08db2f54926c09Dan Gohman//===----------------------------------------------------------------------===// 92385e0e22ca482f2896dfa975a08db2f54926c09Dan Gohman// 102385e0e22ca482f2896dfa975a08db2f54926c09Dan Gohman// This file defines the ScalarEvolutionAliasAnalysis pass, which implements a 112385e0e22ca482f2896dfa975a08db2f54926c09Dan Gohman// simple alias analysis implemented in terms of ScalarEvolution queries. 122385e0e22ca482f2896dfa975a08db2f54926c09Dan Gohman// 137cbf5a803e58b844a537cbf63eb0364d01a842a1Dan Gohman// This differs from traditional loop dependence analysis in that it tests 147cbf5a803e58b844a537cbf63eb0364d01a842a1Dan Gohman// for dependencies within a single iteration of a loop, rather than 154f46e14b8ab3861a8dbea14ed70cb9527ae24a06Dan Gohman// dependencies between different iterations. 167cbf5a803e58b844a537cbf63eb0364d01a842a1Dan Gohman// 172385e0e22ca482f2896dfa975a08db2f54926c09Dan Gohman// ScalarEvolution has a more complete understanding of pointer arithmetic 182385e0e22ca482f2896dfa975a08db2f54926c09Dan Gohman// than BasicAliasAnalysis' collection of ad-hoc analyses. 192385e0e22ca482f2896dfa975a08db2f54926c09Dan Gohman// 202385e0e22ca482f2896dfa975a08db2f54926c09Dan Gohman//===----------------------------------------------------------------------===// 212385e0e22ca482f2896dfa975a08db2f54926c09Dan Gohman 22d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Analysis/Passes.h" 232385e0e22ca482f2896dfa975a08db2f54926c09Dan Gohman#include "llvm/Analysis/AliasAnalysis.h" 242385e0e22ca482f2896dfa975a08db2f54926c09Dan Gohman#include "llvm/Analysis/ScalarEvolutionExpressions.h" 254c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar#include "llvm/IR/Module.h" 262385e0e22ca482f2896dfa975a08db2f54926c09Dan Gohman#include "llvm/Pass.h" 272385e0e22ca482f2896dfa975a08db2f54926c09Dan Gohmanusing namespace llvm; 282385e0e22ca482f2896dfa975a08db2f54926c09Dan Gohman 292385e0e22ca482f2896dfa975a08db2f54926c09Dan Gohmannamespace { 302385e0e22ca482f2896dfa975a08db2f54926c09Dan Gohman /// ScalarEvolutionAliasAnalysis - This is a simple alias analysis 312385e0e22ca482f2896dfa975a08db2f54926c09Dan Gohman /// implementation that uses ScalarEvolution to answer queries. 326726b6d75a8b679068a58cb954ba97cf9d1690baNick Lewycky class ScalarEvolutionAliasAnalysis : public FunctionPass, 336726b6d75a8b679068a58cb954ba97cf9d1690baNick Lewycky public AliasAnalysis { 342385e0e22ca482f2896dfa975a08db2f54926c09Dan Gohman ScalarEvolution *SE; 352385e0e22ca482f2896dfa975a08db2f54926c09Dan Gohman 362385e0e22ca482f2896dfa975a08db2f54926c09Dan Gohman public: 372385e0e22ca482f2896dfa975a08db2f54926c09Dan Gohman static char ID; // Class identification, replacement for typeinfo 38dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines ScalarEvolutionAliasAnalysis() : FunctionPass(ID), SE(nullptr) { 39081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson initializeScalarEvolutionAliasAnalysisPass( 40081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson *PassRegistry::getPassRegistry()); 41081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson } 422385e0e22ca482f2896dfa975a08db2f54926c09Dan Gohman 431bc76d48d476446f226f06f0aced7efb268f2536Chris Lattner /// getAdjustedAnalysisPointer - This method is used when a pass implements 441bc76d48d476446f226f06f0aced7efb268f2536Chris Lattner /// an analysis interface through multiple inheritance. If needed, it 451bc76d48d476446f226f06f0aced7efb268f2536Chris Lattner /// should override this to adjust the this pointer as needed for the 461bc76d48d476446f226f06f0aced7efb268f2536Chris Lattner /// specified pass info. 4736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void *getAdjustedAnalysisPointer(AnalysisID PI) override { 4890c579de5a383cee278acc3f7e7b9d0a656e6a35Owen Anderson if (PI == &AliasAnalysis::ID) 491bc76d48d476446f226f06f0aced7efb268f2536Chris Lattner return (AliasAnalysis*)this; 501bc76d48d476446f226f06f0aced7efb268f2536Chris Lattner return this; 511bc76d48d476446f226f06f0aced7efb268f2536Chris Lattner } 527cbf5a803e58b844a537cbf63eb0364d01a842a1Dan Gohman 532385e0e22ca482f2896dfa975a08db2f54926c09Dan Gohman private: 5436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void getAnalysisUsage(AnalysisUsage &AU) const override; 5536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines bool runOnFunction(Function &F) override; 5636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines AliasResult alias(const Location &LocA, const Location &LocB) override; 572385e0e22ca482f2896dfa975a08db2f54926c09Dan Gohman 58576fd76a682a1d6a6912d27ca432460dcdf0f738Dan Gohman Value *GetBaseValue(const SCEV *S); 592385e0e22ca482f2896dfa975a08db2f54926c09Dan Gohman }; 602385e0e22ca482f2896dfa975a08db2f54926c09Dan Gohman} // End of anonymous namespace 612385e0e22ca482f2896dfa975a08db2f54926c09Dan Gohman 622385e0e22ca482f2896dfa975a08db2f54926c09Dan Gohman// Register this pass... 632385e0e22ca482f2896dfa975a08db2f54926c09Dan Gohmanchar ScalarEvolutionAliasAnalysis::ID = 0; 642ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_AG_PASS_BEGIN(ScalarEvolutionAliasAnalysis, AliasAnalysis, "scev-aa", 65ce665bd2e2b581ab0858d1afe359192bac96b868Owen Anderson "ScalarEvolution-based Alias Analysis", false, true, false) 662ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_DEPENDENCY(ScalarEvolution) 672ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_AG_PASS_END(ScalarEvolutionAliasAnalysis, AliasAnalysis, "scev-aa", 682ab36d350293c77fc8941ce1023e4899df7e3a82Owen Anderson "ScalarEvolution-based Alias Analysis", false, true, false) 692385e0e22ca482f2896dfa975a08db2f54926c09Dan Gohman 702385e0e22ca482f2896dfa975a08db2f54926c09Dan GohmanFunctionPass *llvm::createScalarEvolutionAliasAnalysisPass() { 712385e0e22ca482f2896dfa975a08db2f54926c09Dan Gohman return new ScalarEvolutionAliasAnalysis(); 722385e0e22ca482f2896dfa975a08db2f54926c09Dan Gohman} 732385e0e22ca482f2896dfa975a08db2f54926c09Dan Gohman 742385e0e22ca482f2896dfa975a08db2f54926c09Dan Gohmanvoid 752385e0e22ca482f2896dfa975a08db2f54926c09Dan GohmanScalarEvolutionAliasAnalysis::getAnalysisUsage(AnalysisUsage &AU) const { 762385e0e22ca482f2896dfa975a08db2f54926c09Dan Gohman AU.addRequiredTransitive<ScalarEvolution>(); 772385e0e22ca482f2896dfa975a08db2f54926c09Dan Gohman AU.setPreservesAll(); 782385e0e22ca482f2896dfa975a08db2f54926c09Dan Gohman AliasAnalysis::getAnalysisUsage(AU); 792385e0e22ca482f2896dfa975a08db2f54926c09Dan Gohman} 802385e0e22ca482f2896dfa975a08db2f54926c09Dan Gohman 812385e0e22ca482f2896dfa975a08db2f54926c09Dan Gohmanbool 822385e0e22ca482f2896dfa975a08db2f54926c09Dan GohmanScalarEvolutionAliasAnalysis::runOnFunction(Function &F) { 834c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar InitializeAliasAnalysis(this, &F.getParent()->getDataLayout()); 842385e0e22ca482f2896dfa975a08db2f54926c09Dan Gohman SE = &getAnalysis<ScalarEvolution>(); 852385e0e22ca482f2896dfa975a08db2f54926c09Dan Gohman return false; 862385e0e22ca482f2896dfa975a08db2f54926c09Dan Gohman} 872385e0e22ca482f2896dfa975a08db2f54926c09Dan Gohman 88576fd76a682a1d6a6912d27ca432460dcdf0f738Dan Gohman/// GetBaseValue - Given an expression, try to find a 89576fd76a682a1d6a6912d27ca432460dcdf0f738Dan Gohman/// base value. Return null is none was found. 902385e0e22ca482f2896dfa975a08db2f54926c09Dan GohmanValue * 91576fd76a682a1d6a6912d27ca432460dcdf0f738Dan GohmanScalarEvolutionAliasAnalysis::GetBaseValue(const SCEV *S) { 922385e0e22ca482f2896dfa975a08db2f54926c09Dan Gohman if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S)) { 93ed77e52dd972ada58608f5540d3d0d434899114eDan Gohman // In an addrec, assume that the base will be in the start, rather 94ed77e52dd972ada58608f5540d3d0d434899114eDan Gohman // than the step. 95576fd76a682a1d6a6912d27ca432460dcdf0f738Dan Gohman return GetBaseValue(AR->getStart()); 962385e0e22ca482f2896dfa975a08db2f54926c09Dan Gohman } else if (const SCEVAddExpr *A = dyn_cast<SCEVAddExpr>(S)) { 972385e0e22ca482f2896dfa975a08db2f54926c09Dan Gohman // If there's a pointer operand, it'll be sorted at the end of the list. 982385e0e22ca482f2896dfa975a08db2f54926c09Dan Gohman const SCEV *Last = A->getOperand(A->getNumOperands()-1); 991df9859c40492511b8aa4321eb76496005d3b75bDuncan Sands if (Last->getType()->isPointerTy()) 100576fd76a682a1d6a6912d27ca432460dcdf0f738Dan Gohman return GetBaseValue(Last); 1012385e0e22ca482f2896dfa975a08db2f54926c09Dan Gohman } else if (const SCEVUnknown *U = dyn_cast<SCEVUnknown>(S)) { 102576fd76a682a1d6a6912d27ca432460dcdf0f738Dan Gohman // This is a leaf node. 103576fd76a682a1d6a6912d27ca432460dcdf0f738Dan Gohman return U->getValue(); 1042385e0e22ca482f2896dfa975a08db2f54926c09Dan Gohman } 1052385e0e22ca482f2896dfa975a08db2f54926c09Dan Gohman // No Identified object found. 106dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 1072385e0e22ca482f2896dfa975a08db2f54926c09Dan Gohman} 1082385e0e22ca482f2896dfa975a08db2f54926c09Dan Gohman 1092385e0e22ca482f2896dfa975a08db2f54926c09Dan GohmanAliasAnalysis::AliasResult 110b2143b6247901ae4eca2192ee134564c4f5f7853Dan GohmanScalarEvolutionAliasAnalysis::alias(const Location &LocA, 111b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman const Location &LocB) { 11249bda917dbfbb09e2410272ebb1c6e4a2a3f45a2Dan Gohman // If either of the memory references is empty, it doesn't matter what the 11349bda917dbfbb09e2410272ebb1c6e4a2a3f45a2Dan Gohman // pointer values are. This allows the code below to ignore this special 11449bda917dbfbb09e2410272ebb1c6e4a2a3f45a2Dan Gohman // case. 115b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman if (LocA.Size == 0 || LocB.Size == 0) 11649bda917dbfbb09e2410272ebb1c6e4a2a3f45a2Dan Gohman return NoAlias; 11749bda917dbfbb09e2410272ebb1c6e4a2a3f45a2Dan Gohman 1182385e0e22ca482f2896dfa975a08db2f54926c09Dan Gohman // This is ScalarEvolutionAliasAnalysis. Get the SCEVs! 119b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman const SCEV *AS = SE->getSCEV(const_cast<Value *>(LocA.Ptr)); 120b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman const SCEV *BS = SE->getSCEV(const_cast<Value *>(LocB.Ptr)); 1212385e0e22ca482f2896dfa975a08db2f54926c09Dan Gohman 1222385e0e22ca482f2896dfa975a08db2f54926c09Dan Gohman // If they evaluate to the same expression, it's a MustAlias. 1232385e0e22ca482f2896dfa975a08db2f54926c09Dan Gohman if (AS == BS) return MustAlias; 1242385e0e22ca482f2896dfa975a08db2f54926c09Dan Gohman 1252385e0e22ca482f2896dfa975a08db2f54926c09Dan Gohman // If something is known about the difference between the two addresses, 1262385e0e22ca482f2896dfa975a08db2f54926c09Dan Gohman // see if it's enough to prove a NoAlias. 1272385e0e22ca482f2896dfa975a08db2f54926c09Dan Gohman if (SE->getEffectiveSCEVType(AS->getType()) == 1282385e0e22ca482f2896dfa975a08db2f54926c09Dan Gohman SE->getEffectiveSCEVType(BS->getType())) { 1292385e0e22ca482f2896dfa975a08db2f54926c09Dan Gohman unsigned BitWidth = SE->getTypeSizeInBits(AS->getType()); 130b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman APInt ASizeInt(BitWidth, LocA.Size); 131b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman APInt BSizeInt(BitWidth, LocB.Size); 13249bda917dbfbb09e2410272ebb1c6e4a2a3f45a2Dan Gohman 13349bda917dbfbb09e2410272ebb1c6e4a2a3f45a2Dan Gohman // Compute the difference between the two pointers. 1342385e0e22ca482f2896dfa975a08db2f54926c09Dan Gohman const SCEV *BA = SE->getMinusSCEV(BS, AS); 13549bda917dbfbb09e2410272ebb1c6e4a2a3f45a2Dan Gohman 13649bda917dbfbb09e2410272ebb1c6e4a2a3f45a2Dan Gohman // Test whether the difference is known to be great enough that memory of 13749bda917dbfbb09e2410272ebb1c6e4a2a3f45a2Dan Gohman // the given sizes don't overlap. This assumes that ASizeInt and BSizeInt 13849bda917dbfbb09e2410272ebb1c6e4a2a3f45a2Dan Gohman // are non-zero, which is special-cased above. 13949bda917dbfbb09e2410272ebb1c6e4a2a3f45a2Dan Gohman if (ASizeInt.ule(SE->getUnsignedRange(BA).getUnsignedMin()) && 14049bda917dbfbb09e2410272ebb1c6e4a2a3f45a2Dan Gohman (-BSizeInt).uge(SE->getUnsignedRange(BA).getUnsignedMax())) 14149bda917dbfbb09e2410272ebb1c6e4a2a3f45a2Dan Gohman return NoAlias; 14249bda917dbfbb09e2410272ebb1c6e4a2a3f45a2Dan Gohman 14349bda917dbfbb09e2410272ebb1c6e4a2a3f45a2Dan Gohman // Folding the subtraction while preserving range information can be tricky 14449bda917dbfbb09e2410272ebb1c6e4a2a3f45a2Dan Gohman // (because of INT_MIN, etc.); if the prior test failed, swap AS and BS 14549bda917dbfbb09e2410272ebb1c6e4a2a3f45a2Dan Gohman // and try again to see if things fold better that way. 14649bda917dbfbb09e2410272ebb1c6e4a2a3f45a2Dan Gohman 14749bda917dbfbb09e2410272ebb1c6e4a2a3f45a2Dan Gohman // Compute the difference between the two pointers. 14849bda917dbfbb09e2410272ebb1c6e4a2a3f45a2Dan Gohman const SCEV *AB = SE->getMinusSCEV(AS, BS); 14949bda917dbfbb09e2410272ebb1c6e4a2a3f45a2Dan Gohman 15049bda917dbfbb09e2410272ebb1c6e4a2a3f45a2Dan Gohman // Test whether the difference is known to be great enough that memory of 15149bda917dbfbb09e2410272ebb1c6e4a2a3f45a2Dan Gohman // the given sizes don't overlap. This assumes that ASizeInt and BSizeInt 15249bda917dbfbb09e2410272ebb1c6e4a2a3f45a2Dan Gohman // are non-zero, which is special-cased above. 15349bda917dbfbb09e2410272ebb1c6e4a2a3f45a2Dan Gohman if (BSizeInt.ule(SE->getUnsignedRange(AB).getUnsignedMin()) && 15449bda917dbfbb09e2410272ebb1c6e4a2a3f45a2Dan Gohman (-ASizeInt).uge(SE->getUnsignedRange(AB).getUnsignedMax())) 15549bda917dbfbb09e2410272ebb1c6e4a2a3f45a2Dan Gohman return NoAlias; 1562385e0e22ca482f2896dfa975a08db2f54926c09Dan Gohman } 1572385e0e22ca482f2896dfa975a08db2f54926c09Dan Gohman 1582385e0e22ca482f2896dfa975a08db2f54926c09Dan Gohman // If ScalarEvolution can find an underlying object, form a new query. 1592385e0e22ca482f2896dfa975a08db2f54926c09Dan Gohman // The correctness of this depends on ScalarEvolution not recognizing 1602385e0e22ca482f2896dfa975a08db2f54926c09Dan Gohman // inttoptr and ptrtoint operators. 161576fd76a682a1d6a6912d27ca432460dcdf0f738Dan Gohman Value *AO = GetBaseValue(AS); 162576fd76a682a1d6a6912d27ca432460dcdf0f738Dan Gohman Value *BO = GetBaseValue(BS); 163b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman if ((AO && AO != LocA.Ptr) || (BO && BO != LocB.Ptr)) 164b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman if (alias(Location(AO ? AO : LocA.Ptr, 165b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman AO ? +UnknownSize : LocA.Size, 16637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines AO ? AAMDNodes() : LocA.AATags), 167b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman Location(BO ? BO : LocB.Ptr, 168b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman BO ? +UnknownSize : LocB.Size, 16937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines BO ? AAMDNodes() : LocB.AATags)) == NoAlias) 1702385e0e22ca482f2896dfa975a08db2f54926c09Dan Gohman return NoAlias; 1712385e0e22ca482f2896dfa975a08db2f54926c09Dan Gohman 1722385e0e22ca482f2896dfa975a08db2f54926c09Dan Gohman // Forward the query to the next analysis. 173b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman return AliasAnalysis::alias(LocA, LocB); 1742385e0e22ca482f2896dfa975a08db2f54926c09Dan Gohman} 175