1 | //===- ScalarEvolutionAliasAnalysis.cpp - SCEV-based Alias Analysis -------===// |
2 | // |
3 | // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
4 | // See https://llvm.org/LICENSE.txt for license information. |
5 | // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
6 | // |
7 | //===----------------------------------------------------------------------===// |
8 | // |
9 | // This file defines the ScalarEvolutionAliasAnalysis pass, which implements a |
10 | // simple alias analysis implemented in terms of ScalarEvolution queries. |
11 | // |
12 | // This differs from traditional loop dependence analysis in that it tests |
13 | // for dependencies within a single iteration of a loop, rather than |
14 | // dependencies between different iterations. |
15 | // |
16 | // ScalarEvolution has a more complete understanding of pointer arithmetic |
17 | // than BasicAliasAnalysis' collection of ad-hoc analyses. |
18 | // |
19 | //===----------------------------------------------------------------------===// |
20 | |
21 | #include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h" |
22 | #include "llvm/Analysis/ScalarEvolution.h" |
23 | #include "llvm/Analysis/ScalarEvolutionExpressions.h" |
24 | #include "llvm/InitializePasses.h" |
25 | using namespace llvm; |
26 | |
27 | static bool canComputePointerDiff(ScalarEvolution &SE, |
28 | const SCEV *A, const SCEV *B) { |
29 | if (SE.getEffectiveSCEVType(Ty: A->getType()) != |
30 | SE.getEffectiveSCEVType(Ty: B->getType())) |
31 | return false; |
32 | |
33 | return SE.instructionCouldExistWithOperands(A, B); |
34 | } |
35 | |
36 | AliasResult SCEVAAResult::alias(const MemoryLocation &LocA, |
37 | const MemoryLocation &LocB, AAQueryInfo &AAQI, |
38 | const Instruction *) { |
39 | // If either of the memory references is empty, it doesn't matter what the |
40 | // pointer values are. This allows the code below to ignore this special |
41 | // case. |
42 | if (LocA.Size.isZero() || LocB.Size.isZero()) |
43 | return AliasResult::NoAlias; |
44 | |
45 | // This is SCEVAAResult. Get the SCEVs! |
46 | const SCEV *AS = SE.getSCEV(V: const_cast<Value *>(LocA.Ptr)); |
47 | const SCEV *BS = SE.getSCEV(V: const_cast<Value *>(LocB.Ptr)); |
48 | |
49 | // If they evaluate to the same expression, it's a MustAlias. |
50 | if (AS == BS) |
51 | return AliasResult::MustAlias; |
52 | |
53 | // If something is known about the difference between the two addresses, |
54 | // see if it's enough to prove a NoAlias. |
55 | if (canComputePointerDiff(SE, A: AS, B: BS)) { |
56 | unsigned BitWidth = SE.getTypeSizeInBits(Ty: AS->getType()); |
57 | APInt ASizeInt(BitWidth, LocA.Size.hasValue() |
58 | ? static_cast<uint64_t>(LocA.Size.getValue()) |
59 | : MemoryLocation::UnknownSize); |
60 | APInt BSizeInt(BitWidth, LocB.Size.hasValue() |
61 | ? static_cast<uint64_t>(LocB.Size.getValue()) |
62 | : MemoryLocation::UnknownSize); |
63 | |
64 | // Compute the difference between the two pointers. |
65 | const SCEV *BA = SE.getMinusSCEV(LHS: BS, RHS: AS); |
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 (!isa<SCEVCouldNotCompute>(Val: BA) && |
71 | ASizeInt.ule(RHS: SE.getUnsignedRange(S: BA).getUnsignedMin()) && |
72 | (-BSizeInt).uge(RHS: SE.getUnsignedRange(S: BA).getUnsignedMax())) |
73 | return AliasResult::NoAlias; |
74 | |
75 | // Folding the subtraction while preserving range information can be tricky |
76 | // (because of INT_MIN, etc.); if the prior test failed, swap AS and BS |
77 | // and try again to see if things fold better that way. |
78 | |
79 | // Compute the difference between the two pointers. |
80 | const SCEV *AB = SE.getMinusSCEV(LHS: AS, RHS: BS); |
81 | |
82 | // Test whether the difference is known to be great enough that memory of |
83 | // the given sizes don't overlap. This assumes that ASizeInt and BSizeInt |
84 | // are non-zero, which is special-cased above. |
85 | if (!isa<SCEVCouldNotCompute>(Val: AB) && |
86 | BSizeInt.ule(RHS: SE.getUnsignedRange(S: AB).getUnsignedMin()) && |
87 | (-ASizeInt).uge(RHS: SE.getUnsignedRange(S: AB).getUnsignedMax())) |
88 | return AliasResult::NoAlias; |
89 | } |
90 | |
91 | // If ScalarEvolution can find an underlying object, form a new query. |
92 | // The correctness of this depends on ScalarEvolution not recognizing |
93 | // inttoptr and ptrtoint operators. |
94 | Value *AO = GetBaseValue(S: AS); |
95 | Value *BO = GetBaseValue(S: BS); |
96 | if ((AO && AO != LocA.Ptr) || (BO && BO != LocB.Ptr)) |
97 | if (alias(LocA: MemoryLocation(AO ? AO : LocA.Ptr, |
98 | AO ? LocationSize::beforeOrAfterPointer() |
99 | : LocA.Size, |
100 | AO ? AAMDNodes() : LocA.AATags), |
101 | LocB: MemoryLocation(BO ? BO : LocB.Ptr, |
102 | BO ? LocationSize::beforeOrAfterPointer() |
103 | : LocB.Size, |
104 | BO ? AAMDNodes() : LocB.AATags), |
105 | AAQI, nullptr) == AliasResult::NoAlias) |
106 | return AliasResult::NoAlias; |
107 | |
108 | return AliasResult::MayAlias; |
109 | } |
110 | |
111 | /// Given an expression, try to find a base value. |
112 | /// |
113 | /// Returns null if none was found. |
114 | Value *SCEVAAResult::GetBaseValue(const SCEV *S) { |
115 | if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(Val: S)) { |
116 | // In an addrec, assume that the base will be in the start, rather |
117 | // than the step. |
118 | return GetBaseValue(S: AR->getStart()); |
119 | } else if (const SCEVAddExpr *A = dyn_cast<SCEVAddExpr>(Val: S)) { |
120 | // If there's a pointer operand, it'll be sorted at the end of the list. |
121 | const SCEV *Last = A->getOperand(i: A->getNumOperands() - 1); |
122 | if (Last->getType()->isPointerTy()) |
123 | return GetBaseValue(S: Last); |
124 | } else if (const SCEVUnknown *U = dyn_cast<SCEVUnknown>(Val: S)) { |
125 | // This is a leaf node. |
126 | return U->getValue(); |
127 | } |
128 | // No Identified object found. |
129 | return nullptr; |
130 | } |
131 | |
132 | bool SCEVAAResult::invalidate(Function &Fn, const PreservedAnalyses &PA, |
133 | FunctionAnalysisManager::Invalidator &Inv) { |
134 | // We don't care if this analysis itself is preserved, it has no state. But |
135 | // we need to check that the analyses it depends on have been. |
136 | return Inv.invalidate<ScalarEvolutionAnalysis>(IR&: Fn, PA); |
137 | } |
138 | |
139 | AnalysisKey SCEVAA::Key; |
140 | |
141 | SCEVAAResult SCEVAA::run(Function &F, FunctionAnalysisManager &AM) { |
142 | return SCEVAAResult(AM.getResult<ScalarEvolutionAnalysis>(IR&: F)); |
143 | } |
144 | |
145 | char SCEVAAWrapperPass::ID = 0; |
146 | INITIALIZE_PASS_BEGIN(SCEVAAWrapperPass, "scev-aa" , |
147 | "ScalarEvolution-based Alias Analysis" , false, true) |
148 | INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass) |
149 | INITIALIZE_PASS_END(SCEVAAWrapperPass, "scev-aa" , |
150 | "ScalarEvolution-based Alias Analysis" , false, true) |
151 | |
152 | FunctionPass *llvm::createSCEVAAWrapperPass() { |
153 | return new SCEVAAWrapperPass(); |
154 | } |
155 | |
156 | SCEVAAWrapperPass::SCEVAAWrapperPass() : FunctionPass(ID) { |
157 | initializeSCEVAAWrapperPassPass(Registry&: *PassRegistry::getPassRegistry()); |
158 | } |
159 | |
160 | bool SCEVAAWrapperPass::runOnFunction(Function &F) { |
161 | Result.reset( |
162 | p: new SCEVAAResult(getAnalysis<ScalarEvolutionWrapperPass>().getSE())); |
163 | return false; |
164 | } |
165 | |
166 | void SCEVAAWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const { |
167 | AU.setPreservesAll(); |
168 | AU.addRequired<ScalarEvolutionWrapperPass>(); |
169 | } |
170 | |