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