1214571Sdim//===- ScalarEvolutionAliasAnalysis.cpp - SCEV-based Alias Analysis -------===// 2214571Sdim// 3214571Sdim// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4214571Sdim// See https://llvm.org/LICENSE.txt for license information. 5214571Sdim// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6214571Sdim// 7214571Sdim//===----------------------------------------------------------------------===// 8214571Sdim// 9214571Sdim// This file defines the ScalarEvolutionAliasAnalysis pass, which implements a 10214571Sdim// simple alias analysis implemented in terms of ScalarEvolution queries. 11214571Sdim// 12214571Sdim// This differs from traditional loop dependence analysis in that it tests 13214571Sdim// for dependencies within a single iteration of a loop, rather than 14214571Sdim// dependencies between different iterations. 15214571Sdim// 16214571Sdim// ScalarEvolution has a more complete understanding of pointer arithmetic 17214571Sdim// than BasicAliasAnalysis' collection of ad-hoc analyses. 18214571Sdim// 19214571Sdim//===----------------------------------------------------------------------===// 20214571Sdim 21214571Sdim#include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h" 22214571Sdim#include "llvm/InitializePasses.h" 23214571Sdimusing namespace llvm; 24214571Sdim 25214571SdimAliasResult SCEVAAResult::alias(const MemoryLocation &LocA, 26214571Sdim const MemoryLocation &LocB, AAQueryInfo &AAQI) { 27214571Sdim // If either of the memory references is empty, it doesn't matter what the 28214571Sdim // pointer values are. This allows the code below to ignore this special 29214571Sdim // case. 30214571Sdim if (LocA.Size.isZero() || LocB.Size.isZero()) 31214571Sdim return NoAlias; 32214571Sdim 33214571Sdim // This is SCEVAAResult. Get the SCEVs! 34214571Sdim const SCEV *AS = SE.getSCEV(const_cast<Value *>(LocA.Ptr)); 35214571Sdim const SCEV *BS = SE.getSCEV(const_cast<Value *>(LocB.Ptr)); 36214571Sdim 37214571Sdim // If they evaluate to the same expression, it's a MustAlias. 38214571Sdim if (AS == BS) 39214571Sdim return MustAlias; 40214571Sdim 41214571Sdim // If something is known about the difference between the two addresses, 42214571Sdim // see if it's enough to prove a NoAlias. 43214571Sdim if (SE.getEffectiveSCEVType(AS->getType()) == 44214571Sdim SE.getEffectiveSCEVType(BS->getType())) { 45214571Sdim unsigned BitWidth = SE.getTypeSizeInBits(AS->getType()); 46214571Sdim APInt ASizeInt(BitWidth, LocA.Size.hasValue() 47214571Sdim ? LocA.Size.getValue() 48214571Sdim : MemoryLocation::UnknownSize); 49214571Sdim APInt BSizeInt(BitWidth, LocB.Size.hasValue() 50214571Sdim ? LocB.Size.getValue() 51214571Sdim : MemoryLocation::UnknownSize); 52214571Sdim 53214571Sdim // Compute the difference between the two pointers. 54214571Sdim const SCEV *BA = SE.getMinusSCEV(BS, AS); 55214571Sdim 56214571Sdim // Test whether the difference is known to be great enough that memory of 57214571Sdim // the given sizes don't overlap. This assumes that ASizeInt and BSizeInt 58214571Sdim // are non-zero, which is special-cased above. 59214571Sdim if (ASizeInt.ule(SE.getUnsignedRange(BA).getUnsignedMin()) && 60214571Sdim (-BSizeInt).uge(SE.getUnsignedRange(BA).getUnsignedMax())) 61214571Sdim return NoAlias; 62214571Sdim 63214571Sdim // Folding the subtraction while preserving range information can be tricky 64214571Sdim // (because of INT_MIN, etc.); if the prior test failed, swap AS and BS 65214571Sdim // and try again to see if things fold better that way. 66214571Sdim 67214571Sdim // Compute the difference between the two pointers. 68214571Sdim const SCEV *AB = SE.getMinusSCEV(AS, BS); 69214571Sdim 70214571Sdim // Test whether the difference is known to be great enough that memory of 71214571Sdim // the given sizes don't overlap. This assumes that ASizeInt and BSizeInt 72214571Sdim // are non-zero, which is special-cased above. 73214571Sdim if (BSizeInt.ule(SE.getUnsignedRange(AB).getUnsignedMin()) && 74214571Sdim (-ASizeInt).uge(SE.getUnsignedRange(AB).getUnsignedMax())) 75214571Sdim return NoAlias; 76214571Sdim } 77214571Sdim 78214571Sdim // If ScalarEvolution can find an underlying object, form a new query. 79214571Sdim // The correctness of this depends on ScalarEvolution not recognizing 80214571Sdim // inttoptr and ptrtoint operators. 81214571Sdim Value *AO = GetBaseValue(AS); 82214571Sdim Value *BO = GetBaseValue(BS); 83214571Sdim if ((AO && AO != LocA.Ptr) || (BO && BO != LocB.Ptr)) 84214571Sdim if (alias(MemoryLocation(AO ? AO : LocA.Ptr, 85214571Sdim AO ? LocationSize::unknown() : LocA.Size, 86214571Sdim AO ? AAMDNodes() : LocA.AATags), 87214571Sdim MemoryLocation(BO ? BO : LocB.Ptr, 88214571Sdim BO ? LocationSize::unknown() : LocB.Size, 89214571Sdim BO ? AAMDNodes() : LocB.AATags), 90214571Sdim AAQI) == NoAlias) 91214571Sdim return NoAlias; 92214571Sdim 93214571Sdim // Forward the query to the next analysis. 94214571Sdim return AAResultBase::alias(LocA, LocB, AAQI); 95214571Sdim} 96214571Sdim 97214571Sdim/// Given an expression, try to find a base value. 98214571Sdim/// 99214571Sdim/// Returns null if none was found. 100214571SdimValue *SCEVAAResult::GetBaseValue(const SCEV *S) { 101214571Sdim if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S)) { 102214571Sdim // In an addrec, assume that the base will be in the start, rather 103214571Sdim // than the step. 104214571Sdim return GetBaseValue(AR->getStart()); 105214571Sdim } else if (const SCEVAddExpr *A = dyn_cast<SCEVAddExpr>(S)) { 106214571Sdim // If there's a pointer operand, it'll be sorted at the end of the list. 107214571Sdim const SCEV *Last = A->getOperand(A->getNumOperands() - 1); 108214571Sdim if (Last->getType()->isPointerTy()) 109214571Sdim return GetBaseValue(Last); 110214571Sdim } else if (const SCEVUnknown *U = dyn_cast<SCEVUnknown>(S)) { 111214571Sdim // This is a leaf node. 112 return U->getValue(); 113 } 114 // No Identified object found. 115 return nullptr; 116} 117 118AnalysisKey SCEVAA::Key; 119 120SCEVAAResult SCEVAA::run(Function &F, FunctionAnalysisManager &AM) { 121 return SCEVAAResult(AM.getResult<ScalarEvolutionAnalysis>(F)); 122} 123 124char SCEVAAWrapperPass::ID = 0; 125INITIALIZE_PASS_BEGIN(SCEVAAWrapperPass, "scev-aa", 126 "ScalarEvolution-based Alias Analysis", false, true) 127INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass) 128INITIALIZE_PASS_END(SCEVAAWrapperPass, "scev-aa", 129 "ScalarEvolution-based Alias Analysis", false, true) 130 131FunctionPass *llvm::createSCEVAAWrapperPass() { 132 return new SCEVAAWrapperPass(); 133} 134 135SCEVAAWrapperPass::SCEVAAWrapperPass() : FunctionPass(ID) { 136 initializeSCEVAAWrapperPassPass(*PassRegistry::getPassRegistry()); 137} 138 139bool SCEVAAWrapperPass::runOnFunction(Function &F) { 140 Result.reset( 141 new SCEVAAResult(getAnalysis<ScalarEvolutionWrapperPass>().getSE())); 142 return false; 143} 144 145void SCEVAAWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const { 146 AU.setPreservesAll(); 147 AU.addRequired<ScalarEvolutionWrapperPass>(); 148} 149