Bug Summary

File:lib/Analysis/DependenceAnalysis.cpp
Warning:line 946, column 1
Potential leak of memory pointed to by 'SrcLoops.X'

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -disable-llvm-verifier -discard-value-names -main-file-name DependenceAnalysis.cpp -analyzer-store=region -analyzer-opt-analyze-nested-blocks -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=cplusplus -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -analyzer-config-compatibility-mode=true -mrelocation-model pic -pic-level 2 -mthread-model posix -fmath-errno -masm-verbose -mconstructor-aliases -munwind-tables -fuse-init-array -target-cpu x86-64 -dwarf-column-info -debugger-tuning=gdb -momit-leaf-frame-pointer -ffunction-sections -fdata-sections -resource-dir /usr/lib/llvm-9/lib/clang/9.0.0 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I /build/llvm-toolchain-snapshot-9~svn362543/build-llvm/lib/Analysis -I /build/llvm-toolchain-snapshot-9~svn362543/lib/Analysis -I /build/llvm-toolchain-snapshot-9~svn362543/build-llvm/include -I /build/llvm-toolchain-snapshot-9~svn362543/include -U NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/x86_64-linux-gnu/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/x86_64-linux-gnu/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/c++/6.3.0/backward -internal-isystem /usr/include/clang/9.0.0/include/ -internal-isystem /usr/local/include -internal-isystem /usr/lib/llvm-9/lib/clang/9.0.0/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -O2 -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-maybe-uninitialized -Wno-comment -std=c++11 -fdeprecated-macro -fdebug-compilation-dir /build/llvm-toolchain-snapshot-9~svn362543/build-llvm/lib/Analysis -fdebug-prefix-map=/build/llvm-toolchain-snapshot-9~svn362543=. -ferror-limit 19 -fmessage-length 0 -fvisibility-inlines-hidden -stack-protector 2 -fobjc-runtime=gcc -fdiagnostics-show-option -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -o /tmp/scan-build-2019-06-05-060531-1271-1 -x c++ /build/llvm-toolchain-snapshot-9~svn362543/lib/Analysis/DependenceAnalysis.cpp -faddrsig

/build/llvm-toolchain-snapshot-9~svn362543/lib/Analysis/DependenceAnalysis.cpp

1//===-- DependenceAnalysis.cpp - DA Implementation --------------*- C++ -*-===//
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// DependenceAnalysis is an LLVM pass that analyses dependences between memory
10// accesses. Currently, it is an (incomplete) implementation of the approach
11// described in
12//
13// Practical Dependence Testing
14// Goff, Kennedy, Tseng
15// PLDI 1991
16//
17// There's a single entry point that analyzes the dependence between a pair
18// of memory references in a function, returning either NULL, for no dependence,
19// or a more-or-less detailed description of the dependence between them.
20//
21// Currently, the implementation cannot propagate constraints between
22// coupled RDIV subscripts and lacks a multi-subscript MIV test.
23// Both of these are conservative weaknesses;
24// that is, not a source of correctness problems.
25//
26// Since Clang linearizes some array subscripts, the dependence
27// analysis is using SCEV->delinearize to recover the representation of multiple
28// subscripts, and thus avoid the more expensive and less precise MIV tests. The
29// delinearization is controlled by the flag -da-delinearize.
30//
31// We should pay some careful attention to the possibility of integer overflow
32// in the implementation of the various tests. This could happen with Add,
33// Subtract, or Multiply, with both APInt's and SCEV's.
34//
35// Some non-linear subscript pairs can be handled by the GCD test
36// (and perhaps other tests).
37// Should explore how often these things occur.
38//
39// Finally, it seems like certain test cases expose weaknesses in the SCEV
40// simplification, especially in the handling of sign and zero extensions.
41// It could be useful to spend time exploring these.
42//
43// Please note that this is work in progress and the interface is subject to
44// change.
45//
46//===----------------------------------------------------------------------===//
47// //
48// In memory of Ken Kennedy, 1945 - 2007 //
49// //
50//===----------------------------------------------------------------------===//
51
52#include "llvm/Analysis/DependenceAnalysis.h"
53#include "llvm/ADT/STLExtras.h"
54#include "llvm/ADT/Statistic.h"
55#include "llvm/Analysis/AliasAnalysis.h"
56#include "llvm/Analysis/LoopInfo.h"
57#include "llvm/Analysis/ScalarEvolution.h"
58#include "llvm/Analysis/ScalarEvolutionExpressions.h"
59#include "llvm/Analysis/ValueTracking.h"
60#include "llvm/Config/llvm-config.h"
61#include "llvm/IR/InstIterator.h"
62#include "llvm/IR/Module.h"
63#include "llvm/IR/Operator.h"
64#include "llvm/Support/CommandLine.h"
65#include "llvm/Support/Debug.h"
66#include "llvm/Support/ErrorHandling.h"
67#include "llvm/Support/raw_ostream.h"
68
69using namespace llvm;
70
71#define DEBUG_TYPE"da" "da"
72
73//===----------------------------------------------------------------------===//
74// statistics
75
76STATISTIC(TotalArrayPairs, "Array pairs tested")static llvm::Statistic TotalArrayPairs = {"da", "TotalArrayPairs"
, "Array pairs tested", {0}, {false}}
;
77STATISTIC(SeparableSubscriptPairs, "Separable subscript pairs")static llvm::Statistic SeparableSubscriptPairs = {"da", "SeparableSubscriptPairs"
, "Separable subscript pairs", {0}, {false}}
;
78STATISTIC(CoupledSubscriptPairs, "Coupled subscript pairs")static llvm::Statistic CoupledSubscriptPairs = {"da", "CoupledSubscriptPairs"
, "Coupled subscript pairs", {0}, {false}}
;
79STATISTIC(NonlinearSubscriptPairs, "Nonlinear subscript pairs")static llvm::Statistic NonlinearSubscriptPairs = {"da", "NonlinearSubscriptPairs"
, "Nonlinear subscript pairs", {0}, {false}}
;
80STATISTIC(ZIVapplications, "ZIV applications")static llvm::Statistic ZIVapplications = {"da", "ZIVapplications"
, "ZIV applications", {0}, {false}}
;
81STATISTIC(ZIVindependence, "ZIV independence")static llvm::Statistic ZIVindependence = {"da", "ZIVindependence"
, "ZIV independence", {0}, {false}}
;
82STATISTIC(StrongSIVapplications, "Strong SIV applications")static llvm::Statistic StrongSIVapplications = {"da", "StrongSIVapplications"
, "Strong SIV applications", {0}, {false}}
;
83STATISTIC(StrongSIVsuccesses, "Strong SIV successes")static llvm::Statistic StrongSIVsuccesses = {"da", "StrongSIVsuccesses"
, "Strong SIV successes", {0}, {false}}
;
84STATISTIC(StrongSIVindependence, "Strong SIV independence")static llvm::Statistic StrongSIVindependence = {"da", "StrongSIVindependence"
, "Strong SIV independence", {0}, {false}}
;
85STATISTIC(WeakCrossingSIVapplications, "Weak-Crossing SIV applications")static llvm::Statistic WeakCrossingSIVapplications = {"da", "WeakCrossingSIVapplications"
, "Weak-Crossing SIV applications", {0}, {false}}
;
86STATISTIC(WeakCrossingSIVsuccesses, "Weak-Crossing SIV successes")static llvm::Statistic WeakCrossingSIVsuccesses = {"da", "WeakCrossingSIVsuccesses"
, "Weak-Crossing SIV successes", {0}, {false}}
;
87STATISTIC(WeakCrossingSIVindependence, "Weak-Crossing SIV independence")static llvm::Statistic WeakCrossingSIVindependence = {"da", "WeakCrossingSIVindependence"
, "Weak-Crossing SIV independence", {0}, {false}}
;
88STATISTIC(ExactSIVapplications, "Exact SIV applications")static llvm::Statistic ExactSIVapplications = {"da", "ExactSIVapplications"
, "Exact SIV applications", {0}, {false}}
;
89STATISTIC(ExactSIVsuccesses, "Exact SIV successes")static llvm::Statistic ExactSIVsuccesses = {"da", "ExactSIVsuccesses"
, "Exact SIV successes", {0}, {false}}
;
90STATISTIC(ExactSIVindependence, "Exact SIV independence")static llvm::Statistic ExactSIVindependence = {"da", "ExactSIVindependence"
, "Exact SIV independence", {0}, {false}}
;
91STATISTIC(WeakZeroSIVapplications, "Weak-Zero SIV applications")static llvm::Statistic WeakZeroSIVapplications = {"da", "WeakZeroSIVapplications"
, "Weak-Zero SIV applications", {0}, {false}}
;
92STATISTIC(WeakZeroSIVsuccesses, "Weak-Zero SIV successes")static llvm::Statistic WeakZeroSIVsuccesses = {"da", "WeakZeroSIVsuccesses"
, "Weak-Zero SIV successes", {0}, {false}}
;
93STATISTIC(WeakZeroSIVindependence, "Weak-Zero SIV independence")static llvm::Statistic WeakZeroSIVindependence = {"da", "WeakZeroSIVindependence"
, "Weak-Zero SIV independence", {0}, {false}}
;
94STATISTIC(ExactRDIVapplications, "Exact RDIV applications")static llvm::Statistic ExactRDIVapplications = {"da", "ExactRDIVapplications"
, "Exact RDIV applications", {0}, {false}}
;
95STATISTIC(ExactRDIVindependence, "Exact RDIV independence")static llvm::Statistic ExactRDIVindependence = {"da", "ExactRDIVindependence"
, "Exact RDIV independence", {0}, {false}}
;
96STATISTIC(SymbolicRDIVapplications, "Symbolic RDIV applications")static llvm::Statistic SymbolicRDIVapplications = {"da", "SymbolicRDIVapplications"
, "Symbolic RDIV applications", {0}, {false}}
;
97STATISTIC(SymbolicRDIVindependence, "Symbolic RDIV independence")static llvm::Statistic SymbolicRDIVindependence = {"da", "SymbolicRDIVindependence"
, "Symbolic RDIV independence", {0}, {false}}
;
98STATISTIC(DeltaApplications, "Delta applications")static llvm::Statistic DeltaApplications = {"da", "DeltaApplications"
, "Delta applications", {0}, {false}}
;
99STATISTIC(DeltaSuccesses, "Delta successes")static llvm::Statistic DeltaSuccesses = {"da", "DeltaSuccesses"
, "Delta successes", {0}, {false}}
;
100STATISTIC(DeltaIndependence, "Delta independence")static llvm::Statistic DeltaIndependence = {"da", "DeltaIndependence"
, "Delta independence", {0}, {false}}
;
101STATISTIC(DeltaPropagations, "Delta propagations")static llvm::Statistic DeltaPropagations = {"da", "DeltaPropagations"
, "Delta propagations", {0}, {false}}
;
102STATISTIC(GCDapplications, "GCD applications")static llvm::Statistic GCDapplications = {"da", "GCDapplications"
, "GCD applications", {0}, {false}}
;
103STATISTIC(GCDsuccesses, "GCD successes")static llvm::Statistic GCDsuccesses = {"da", "GCDsuccesses", "GCD successes"
, {0}, {false}}
;
104STATISTIC(GCDindependence, "GCD independence")static llvm::Statistic GCDindependence = {"da", "GCDindependence"
, "GCD independence", {0}, {false}}
;
105STATISTIC(BanerjeeApplications, "Banerjee applications")static llvm::Statistic BanerjeeApplications = {"da", "BanerjeeApplications"
, "Banerjee applications", {0}, {false}}
;
106STATISTIC(BanerjeeIndependence, "Banerjee independence")static llvm::Statistic BanerjeeIndependence = {"da", "BanerjeeIndependence"
, "Banerjee independence", {0}, {false}}
;
107STATISTIC(BanerjeeSuccesses, "Banerjee successes")static llvm::Statistic BanerjeeSuccesses = {"da", "BanerjeeSuccesses"
, "Banerjee successes", {0}, {false}}
;
108
109static cl::opt<bool>
110 Delinearize("da-delinearize", cl::init(true), cl::Hidden, cl::ZeroOrMore,
111 cl::desc("Try to delinearize array references."));
112
113//===----------------------------------------------------------------------===//
114// basics
115
116DependenceAnalysis::Result
117DependenceAnalysis::run(Function &F, FunctionAnalysisManager &FAM) {
118 auto &AA = FAM.getResult<AAManager>(F);
119 auto &SE = FAM.getResult<ScalarEvolutionAnalysis>(F);
120 auto &LI = FAM.getResult<LoopAnalysis>(F);
121 return DependenceInfo(&F, &AA, &SE, &LI);
122}
123
124AnalysisKey DependenceAnalysis::Key;
125
126INITIALIZE_PASS_BEGIN(DependenceAnalysisWrapperPass, "da",static void *initializeDependenceAnalysisWrapperPassPassOnce(
PassRegistry &Registry) {
127 "Dependence Analysis", true, true)static void *initializeDependenceAnalysisWrapperPassPassOnce(
PassRegistry &Registry) {
128INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)initializeLoopInfoWrapperPassPass(Registry);
129INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass)initializeScalarEvolutionWrapperPassPass(Registry);
130INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)initializeAAResultsWrapperPassPass(Registry);
131INITIALIZE_PASS_END(DependenceAnalysisWrapperPass, "da", "Dependence Analysis",PassInfo *PI = new PassInfo( "Dependence Analysis", "da", &
DependenceAnalysisWrapperPass::ID, PassInfo::NormalCtor_t(callDefaultCtor
<DependenceAnalysisWrapperPass>), true, true); Registry
.registerPass(*PI, true); return PI; } static llvm::once_flag
InitializeDependenceAnalysisWrapperPassPassFlag; void llvm::
initializeDependenceAnalysisWrapperPassPass(PassRegistry &
Registry) { llvm::call_once(InitializeDependenceAnalysisWrapperPassPassFlag
, initializeDependenceAnalysisWrapperPassPassOnce, std::ref(Registry
)); }
132 true, true)PassInfo *PI = new PassInfo( "Dependence Analysis", "da", &
DependenceAnalysisWrapperPass::ID, PassInfo::NormalCtor_t(callDefaultCtor
<DependenceAnalysisWrapperPass>), true, true); Registry
.registerPass(*PI, true); return PI; } static llvm::once_flag
InitializeDependenceAnalysisWrapperPassPassFlag; void llvm::
initializeDependenceAnalysisWrapperPassPass(PassRegistry &
Registry) { llvm::call_once(InitializeDependenceAnalysisWrapperPassPassFlag
, initializeDependenceAnalysisWrapperPassPassOnce, std::ref(Registry
)); }
133
134char DependenceAnalysisWrapperPass::ID = 0;
135
136FunctionPass *llvm::createDependenceAnalysisWrapperPass() {
137 return new DependenceAnalysisWrapperPass();
138}
139
140bool DependenceAnalysisWrapperPass::runOnFunction(Function &F) {
141 auto &AA = getAnalysis<AAResultsWrapperPass>().getAAResults();
142 auto &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE();
143 auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
144 info.reset(new DependenceInfo(&F, &AA, &SE, &LI));
145 return false;
146}
147
148DependenceInfo &DependenceAnalysisWrapperPass::getDI() const { return *info; }
149
150void DependenceAnalysisWrapperPass::releaseMemory() { info.reset(); }
151
152void DependenceAnalysisWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
153 AU.setPreservesAll();
154 AU.addRequiredTransitive<AAResultsWrapperPass>();
155 AU.addRequiredTransitive<ScalarEvolutionWrapperPass>();
156 AU.addRequiredTransitive<LoopInfoWrapperPass>();
157}
158
159
160// Used to test the dependence analyzer.
161// Looks through the function, noting loads and stores.
162// Calls depends() on every possible pair and prints out the result.
163// Ignores all other instructions.
164static void dumpExampleDependence(raw_ostream &OS, DependenceInfo *DA) {
165 auto *F = DA->getFunction();
166 for (inst_iterator SrcI = inst_begin(F), SrcE = inst_end(F); SrcI != SrcE;
167 ++SrcI) {
168 if (isa<StoreInst>(*SrcI) || isa<LoadInst>(*SrcI)) {
169 for (inst_iterator DstI = SrcI, DstE = inst_end(F);
170 DstI != DstE; ++DstI) {
171 if (isa<StoreInst>(*DstI) || isa<LoadInst>(*DstI)) {
172 OS << "da analyze - ";
173 if (auto D = DA->depends(&*SrcI, &*DstI, true)) {
174 D->dump(OS);
175 for (unsigned Level = 1; Level <= D->getLevels(); Level++) {
176 if (D->isSplitable(Level)) {
177 OS << "da analyze - split level = " << Level;
178 OS << ", iteration = " << *DA->getSplitIteration(*D, Level);
179 OS << "!\n";
180 }
181 }
182 }
183 else
184 OS << "none!\n";
185 }
186 }
187 }
188 }
189}
190
191void DependenceAnalysisWrapperPass::print(raw_ostream &OS,
192 const Module *) const {
193 dumpExampleDependence(OS, info.get());
194}
195
196PreservedAnalyses
197DependenceAnalysisPrinterPass::run(Function &F, FunctionAnalysisManager &FAM) {
198 OS << "'Dependence Analysis' for function '" << F.getName() << "':\n";
199 dumpExampleDependence(OS, &FAM.getResult<DependenceAnalysis>(F));
200 return PreservedAnalyses::all();
201}
202
203//===----------------------------------------------------------------------===//
204// Dependence methods
205
206// Returns true if this is an input dependence.
207bool Dependence::isInput() const {
208 return Src->mayReadFromMemory() && Dst->mayReadFromMemory();
209}
210
211
212// Returns true if this is an output dependence.
213bool Dependence::isOutput() const {
214 return Src->mayWriteToMemory() && Dst->mayWriteToMemory();
215}
216
217
218// Returns true if this is an flow (aka true) dependence.
219bool Dependence::isFlow() const {
220 return Src->mayWriteToMemory() && Dst->mayReadFromMemory();
221}
222
223
224// Returns true if this is an anti dependence.
225bool Dependence::isAnti() const {
226 return Src->mayReadFromMemory() && Dst->mayWriteToMemory();
227}
228
229
230// Returns true if a particular level is scalar; that is,
231// if no subscript in the source or destination mention the induction
232// variable associated with the loop at this level.
233// Leave this out of line, so it will serve as a virtual method anchor
234bool Dependence::isScalar(unsigned level) const {
235 return false;
236}
237
238
239//===----------------------------------------------------------------------===//
240// FullDependence methods
241
242FullDependence::FullDependence(Instruction *Source, Instruction *Destination,
243 bool PossiblyLoopIndependent,
244 unsigned CommonLevels)
245 : Dependence(Source, Destination), Levels(CommonLevels),
246 LoopIndependent(PossiblyLoopIndependent) {
247 Consistent = true;
248 if (CommonLevels)
249 DV = make_unique<DVEntry[]>(CommonLevels);
250}
251
252// The rest are simple getters that hide the implementation.
253
254// getDirection - Returns the direction associated with a particular level.
255unsigned FullDependence::getDirection(unsigned Level) const {
256 assert(0 < Level && Level <= Levels && "Level out of range")((0 < Level && Level <= Levels && "Level out of range"
) ? static_cast<void> (0) : __assert_fail ("0 < Level && Level <= Levels && \"Level out of range\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/Analysis/DependenceAnalysis.cpp"
, 256, __PRETTY_FUNCTION__))
;
257 return DV[Level - 1].Direction;
258}
259
260
261// Returns the distance (or NULL) associated with a particular level.
262const SCEV *FullDependence::getDistance(unsigned Level) const {
263 assert(0 < Level && Level <= Levels && "Level out of range")((0 < Level && Level <= Levels && "Level out of range"
) ? static_cast<void> (0) : __assert_fail ("0 < Level && Level <= Levels && \"Level out of range\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/Analysis/DependenceAnalysis.cpp"
, 263, __PRETTY_FUNCTION__))
;
264 return DV[Level - 1].Distance;
265}
266
267
268// Returns true if a particular level is scalar; that is,
269// if no subscript in the source or destination mention the induction
270// variable associated with the loop at this level.
271bool FullDependence::isScalar(unsigned Level) const {
272 assert(0 < Level && Level <= Levels && "Level out of range")((0 < Level && Level <= Levels && "Level out of range"
) ? static_cast<void> (0) : __assert_fail ("0 < Level && Level <= Levels && \"Level out of range\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/Analysis/DependenceAnalysis.cpp"
, 272, __PRETTY_FUNCTION__))
;
273 return DV[Level - 1].Scalar;
274}
275
276
277// Returns true if peeling the first iteration from this loop
278// will break this dependence.
279bool FullDependence::isPeelFirst(unsigned Level) const {
280 assert(0 < Level && Level <= Levels && "Level out of range")((0 < Level && Level <= Levels && "Level out of range"
) ? static_cast<void> (0) : __assert_fail ("0 < Level && Level <= Levels && \"Level out of range\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/Analysis/DependenceAnalysis.cpp"
, 280, __PRETTY_FUNCTION__))
;
281 return DV[Level - 1].PeelFirst;
282}
283
284
285// Returns true if peeling the last iteration from this loop
286// will break this dependence.
287bool FullDependence::isPeelLast(unsigned Level) const {
288 assert(0 < Level && Level <= Levels && "Level out of range")((0 < Level && Level <= Levels && "Level out of range"
) ? static_cast<void> (0) : __assert_fail ("0 < Level && Level <= Levels && \"Level out of range\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/Analysis/DependenceAnalysis.cpp"
, 288, __PRETTY_FUNCTION__))
;
289 return DV[Level - 1].PeelLast;
290}
291
292
293// Returns true if splitting this loop will break the dependence.
294bool FullDependence::isSplitable(unsigned Level) const {
295 assert(0 < Level && Level <= Levels && "Level out of range")((0 < Level && Level <= Levels && "Level out of range"
) ? static_cast<void> (0) : __assert_fail ("0 < Level && Level <= Levels && \"Level out of range\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/Analysis/DependenceAnalysis.cpp"
, 295, __PRETTY_FUNCTION__))
;
296 return DV[Level - 1].Splitable;
297}
298
299
300//===----------------------------------------------------------------------===//
301// DependenceInfo::Constraint methods
302
303// If constraint is a point <X, Y>, returns X.
304// Otherwise assert.
305const SCEV *DependenceInfo::Constraint::getX() const {
306 assert(Kind == Point && "Kind should be Point")((Kind == Point && "Kind should be Point") ? static_cast
<void> (0) : __assert_fail ("Kind == Point && \"Kind should be Point\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/Analysis/DependenceAnalysis.cpp"
, 306, __PRETTY_FUNCTION__))
;
307 return A;
308}
309
310
311// If constraint is a point <X, Y>, returns Y.
312// Otherwise assert.
313const SCEV *DependenceInfo::Constraint::getY() const {
314 assert(Kind == Point && "Kind should be Point")((Kind == Point && "Kind should be Point") ? static_cast
<void> (0) : __assert_fail ("Kind == Point && \"Kind should be Point\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/Analysis/DependenceAnalysis.cpp"
, 314, __PRETTY_FUNCTION__))
;
315 return B;
316}
317
318
319// If constraint is a line AX + BY = C, returns A.
320// Otherwise assert.
321const SCEV *DependenceInfo::Constraint::getA() const {
322 assert((Kind == Line || Kind == Distance) &&(((Kind == Line || Kind == Distance) && "Kind should be Line (or Distance)"
) ? static_cast<void> (0) : __assert_fail ("(Kind == Line || Kind == Distance) && \"Kind should be Line (or Distance)\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/Analysis/DependenceAnalysis.cpp"
, 323, __PRETTY_FUNCTION__))
323 "Kind should be Line (or Distance)")(((Kind == Line || Kind == Distance) && "Kind should be Line (or Distance)"
) ? static_cast<void> (0) : __assert_fail ("(Kind == Line || Kind == Distance) && \"Kind should be Line (or Distance)\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/Analysis/DependenceAnalysis.cpp"
, 323, __PRETTY_FUNCTION__))
;
324 return A;
325}
326
327
328// If constraint is a line AX + BY = C, returns B.
329// Otherwise assert.
330const SCEV *DependenceInfo::Constraint::getB() const {
331 assert((Kind == Line || Kind == Distance) &&(((Kind == Line || Kind == Distance) && "Kind should be Line (or Distance)"
) ? static_cast<void> (0) : __assert_fail ("(Kind == Line || Kind == Distance) && \"Kind should be Line (or Distance)\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/Analysis/DependenceAnalysis.cpp"
, 332, __PRETTY_FUNCTION__))
332 "Kind should be Line (or Distance)")(((Kind == Line || Kind == Distance) && "Kind should be Line (or Distance)"
) ? static_cast<void> (0) : __assert_fail ("(Kind == Line || Kind == Distance) && \"Kind should be Line (or Distance)\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/Analysis/DependenceAnalysis.cpp"
, 332, __PRETTY_FUNCTION__))
;
333 return B;
334}
335
336
337// If constraint is a line AX + BY = C, returns C.
338// Otherwise assert.
339const SCEV *DependenceInfo::Constraint::getC() const {
340 assert((Kind == Line || Kind == Distance) &&(((Kind == Line || Kind == Distance) && "Kind should be Line (or Distance)"
) ? static_cast<void> (0) : __assert_fail ("(Kind == Line || Kind == Distance) && \"Kind should be Line (or Distance)\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/Analysis/DependenceAnalysis.cpp"
, 341, __PRETTY_FUNCTION__))
341 "Kind should be Line (or Distance)")(((Kind == Line || Kind == Distance) && "Kind should be Line (or Distance)"
) ? static_cast<void> (0) : __assert_fail ("(Kind == Line || Kind == Distance) && \"Kind should be Line (or Distance)\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/Analysis/DependenceAnalysis.cpp"
, 341, __PRETTY_FUNCTION__))
;
342 return C;
343}
344
345
346// If constraint is a distance, returns D.
347// Otherwise assert.
348const SCEV *DependenceInfo::Constraint::getD() const {
349 assert(Kind == Distance && "Kind should be Distance")((Kind == Distance && "Kind should be Distance") ? static_cast
<void> (0) : __assert_fail ("Kind == Distance && \"Kind should be Distance\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/Analysis/DependenceAnalysis.cpp"
, 349, __PRETTY_FUNCTION__))
;
350 return SE->getNegativeSCEV(C);
351}
352
353
354// Returns the loop associated with this constraint.
355const Loop *DependenceInfo::Constraint::getAssociatedLoop() const {
356 assert((Kind == Distance || Kind == Line || Kind == Point) &&(((Kind == Distance || Kind == Line || Kind == Point) &&
"Kind should be Distance, Line, or Point") ? static_cast<
void> (0) : __assert_fail ("(Kind == Distance || Kind == Line || Kind == Point) && \"Kind should be Distance, Line, or Point\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/Analysis/DependenceAnalysis.cpp"
, 357, __PRETTY_FUNCTION__))
357 "Kind should be Distance, Line, or Point")(((Kind == Distance || Kind == Line || Kind == Point) &&
"Kind should be Distance, Line, or Point") ? static_cast<
void> (0) : __assert_fail ("(Kind == Distance || Kind == Line || Kind == Point) && \"Kind should be Distance, Line, or Point\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/Analysis/DependenceAnalysis.cpp"
, 357, __PRETTY_FUNCTION__))
;
358 return AssociatedLoop;
359}
360
361void DependenceInfo::Constraint::setPoint(const SCEV *X, const SCEV *Y,
362 const Loop *CurLoop) {
363 Kind = Point;
364 A = X;
365 B = Y;
366 AssociatedLoop = CurLoop;
367}
368
369void DependenceInfo::Constraint::setLine(const SCEV *AA, const SCEV *BB,
370 const SCEV *CC, const Loop *CurLoop) {
371 Kind = Line;
372 A = AA;
373 B = BB;
374 C = CC;
375 AssociatedLoop = CurLoop;
376}
377
378void DependenceInfo::Constraint::setDistance(const SCEV *D,
379 const Loop *CurLoop) {
380 Kind = Distance;
381 A = SE->getOne(D->getType());
382 B = SE->getNegativeSCEV(A);
383 C = SE->getNegativeSCEV(D);
384 AssociatedLoop = CurLoop;
385}
386
387void DependenceInfo::Constraint::setEmpty() { Kind = Empty; }
388
389void DependenceInfo::Constraint::setAny(ScalarEvolution *NewSE) {
390 SE = NewSE;
391 Kind = Any;
392}
393
394#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
395// For debugging purposes. Dumps the constraint out to OS.
396LLVM_DUMP_METHOD__attribute__((noinline)) __attribute__((__used__)) void DependenceInfo::Constraint::dump(raw_ostream &OS) const {
397 if (isEmpty())
398 OS << " Empty\n";
399 else if (isAny())
400 OS << " Any\n";
401 else if (isPoint())
402 OS << " Point is <" << *getX() << ", " << *getY() << ">\n";
403 else if (isDistance())
404 OS << " Distance is " << *getD() <<
405 " (" << *getA() << "*X + " << *getB() << "*Y = " << *getC() << ")\n";
406 else if (isLine())
407 OS << " Line is " << *getA() << "*X + " <<
408 *getB() << "*Y = " << *getC() << "\n";
409 else
410 llvm_unreachable("unknown constraint type in Constraint::dump")::llvm::llvm_unreachable_internal("unknown constraint type in Constraint::dump"
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/Analysis/DependenceAnalysis.cpp"
, 410)
;
411}
412#endif
413
414
415// Updates X with the intersection
416// of the Constraints X and Y. Returns true if X has changed.
417// Corresponds to Figure 4 from the paper
418//
419// Practical Dependence Testing
420// Goff, Kennedy, Tseng
421// PLDI 1991
422bool DependenceInfo::intersectConstraints(Constraint *X, const Constraint *Y) {
423 ++DeltaApplications;
424 LLVM_DEBUG(dbgs() << "\tintersect constraints\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\tintersect constraints\n"; } } while
(false)
;
425 LLVM_DEBUG(dbgs() << "\t X ="; X->dump(dbgs()))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\t X ="; X->dump(dbgs()); } }
while (false)
;
426 LLVM_DEBUG(dbgs() << "\t Y ="; Y->dump(dbgs()))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\t Y ="; Y->dump(dbgs()); } }
while (false)
;
427 assert(!Y->isPoint() && "Y must not be a Point")((!Y->isPoint() && "Y must not be a Point") ? static_cast
<void> (0) : __assert_fail ("!Y->isPoint() && \"Y must not be a Point\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/Analysis/DependenceAnalysis.cpp"
, 427, __PRETTY_FUNCTION__))
;
428 if (X->isAny()) {
429 if (Y->isAny())
430 return false;
431 *X = *Y;
432 return true;
433 }
434 if (X->isEmpty())
435 return false;
436 if (Y->isEmpty()) {
437 X->setEmpty();
438 return true;
439 }
440
441 if (X->isDistance() && Y->isDistance()) {
442 LLVM_DEBUG(dbgs() << "\t intersect 2 distances\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\t intersect 2 distances\n"; } }
while (false)
;
443 if (isKnownPredicate(CmpInst::ICMP_EQ, X->getD(), Y->getD()))
444 return false;
445 if (isKnownPredicate(CmpInst::ICMP_NE, X->getD(), Y->getD())) {
446 X->setEmpty();
447 ++DeltaSuccesses;
448 return true;
449 }
450 // Hmmm, interesting situation.
451 // I guess if either is constant, keep it and ignore the other.
452 if (isa<SCEVConstant>(Y->getD())) {
453 *X = *Y;
454 return true;
455 }
456 return false;
457 }
458
459 // At this point, the pseudo-code in Figure 4 of the paper
460 // checks if (X->isPoint() && Y->isPoint()).
461 // This case can't occur in our implementation,
462 // since a Point can only arise as the result of intersecting
463 // two Line constraints, and the right-hand value, Y, is never
464 // the result of an intersection.
465 assert(!(X->isPoint() && Y->isPoint()) &&((!(X->isPoint() && Y->isPoint()) && "We shouldn't ever see X->isPoint() && Y->isPoint()"
) ? static_cast<void> (0) : __assert_fail ("!(X->isPoint() && Y->isPoint()) && \"We shouldn't ever see X->isPoint() && Y->isPoint()\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/Analysis/DependenceAnalysis.cpp"
, 466, __PRETTY_FUNCTION__))
466 "We shouldn't ever see X->isPoint() && Y->isPoint()")((!(X->isPoint() && Y->isPoint()) && "We shouldn't ever see X->isPoint() && Y->isPoint()"
) ? static_cast<void> (0) : __assert_fail ("!(X->isPoint() && Y->isPoint()) && \"We shouldn't ever see X->isPoint() && Y->isPoint()\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/Analysis/DependenceAnalysis.cpp"
, 466, __PRETTY_FUNCTION__))
;
467
468 if (X->isLine() && Y->isLine()) {
469 LLVM_DEBUG(dbgs() << "\t intersect 2 lines\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\t intersect 2 lines\n"; } } while
(false)
;
470 const SCEV *Prod1 = SE->getMulExpr(X->getA(), Y->getB());
471 const SCEV *Prod2 = SE->getMulExpr(X->getB(), Y->getA());
472 if (isKnownPredicate(CmpInst::ICMP_EQ, Prod1, Prod2)) {
473 // slopes are equal, so lines are parallel
474 LLVM_DEBUG(dbgs() << "\t\tsame slope\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\t\tsame slope\n"; } } while (false
)
;
475 Prod1 = SE->getMulExpr(X->getC(), Y->getB());
476 Prod2 = SE->getMulExpr(X->getB(), Y->getC());
477 if (isKnownPredicate(CmpInst::ICMP_EQ, Prod1, Prod2))
478 return false;
479 if (isKnownPredicate(CmpInst::ICMP_NE, Prod1, Prod2)) {
480 X->setEmpty();
481 ++DeltaSuccesses;
482 return true;
483 }
484 return false;
485 }
486 if (isKnownPredicate(CmpInst::ICMP_NE, Prod1, Prod2)) {
487 // slopes differ, so lines intersect
488 LLVM_DEBUG(dbgs() << "\t\tdifferent slopes\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\t\tdifferent slopes\n"; } } while
(false)
;
489 const SCEV *C1B2 = SE->getMulExpr(X->getC(), Y->getB());
490 const SCEV *C1A2 = SE->getMulExpr(X->getC(), Y->getA());
491 const SCEV *C2B1 = SE->getMulExpr(Y->getC(), X->getB());
492 const SCEV *C2A1 = SE->getMulExpr(Y->getC(), X->getA());
493 const SCEV *A1B2 = SE->getMulExpr(X->getA(), Y->getB());
494 const SCEV *A2B1 = SE->getMulExpr(Y->getA(), X->getB());
495 const SCEVConstant *C1A2_C2A1 =
496 dyn_cast<SCEVConstant>(SE->getMinusSCEV(C1A2, C2A1));
497 const SCEVConstant *C1B2_C2B1 =
498 dyn_cast<SCEVConstant>(SE->getMinusSCEV(C1B2, C2B1));
499 const SCEVConstant *A1B2_A2B1 =
500 dyn_cast<SCEVConstant>(SE->getMinusSCEV(A1B2, A2B1));
501 const SCEVConstant *A2B1_A1B2 =
502 dyn_cast<SCEVConstant>(SE->getMinusSCEV(A2B1, A1B2));
503 if (!C1B2_C2B1 || !C1A2_C2A1 ||
504 !A1B2_A2B1 || !A2B1_A1B2)
505 return false;
506 APInt Xtop = C1B2_C2B1->getAPInt();
507 APInt Xbot = A1B2_A2B1->getAPInt();
508 APInt Ytop = C1A2_C2A1->getAPInt();
509 APInt Ybot = A2B1_A1B2->getAPInt();
510 LLVM_DEBUG(dbgs() << "\t\tXtop = " << Xtop << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\t\tXtop = " << Xtop <<
"\n"; } } while (false)
;
511 LLVM_DEBUG(dbgs() << "\t\tXbot = " << Xbot << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\t\tXbot = " << Xbot <<
"\n"; } } while (false)
;
512 LLVM_DEBUG(dbgs() << "\t\tYtop = " << Ytop << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\t\tYtop = " << Ytop <<
"\n"; } } while (false)
;
513 LLVM_DEBUG(dbgs() << "\t\tYbot = " << Ybot << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\t\tYbot = " << Ybot <<
"\n"; } } while (false)
;
514 APInt Xq = Xtop; // these need to be initialized, even
515 APInt Xr = Xtop; // though they're just going to be overwritten
516 APInt::sdivrem(Xtop, Xbot, Xq, Xr);
517 APInt Yq = Ytop;
518 APInt Yr = Ytop;
519 APInt::sdivrem(Ytop, Ybot, Yq, Yr);
520 if (Xr != 0 || Yr != 0) {
521 X->setEmpty();
522 ++DeltaSuccesses;
523 return true;
524 }
525 LLVM_DEBUG(dbgs() << "\t\tX = " << Xq << ", Y = " << Yq << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\t\tX = " << Xq << ", Y = "
<< Yq << "\n"; } } while (false)
;
526 if (Xq.slt(0) || Yq.slt(0)) {
527 X->setEmpty();
528 ++DeltaSuccesses;
529 return true;
530 }
531 if (const SCEVConstant *CUB =
532 collectConstantUpperBound(X->getAssociatedLoop(), Prod1->getType())) {
533 const APInt &UpperBound = CUB->getAPInt();
534 LLVM_DEBUG(dbgs() << "\t\tupper bound = " << UpperBound << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\t\tupper bound = " << UpperBound
<< "\n"; } } while (false)
;
535 if (Xq.sgt(UpperBound) || Yq.sgt(UpperBound)) {
536 X->setEmpty();
537 ++DeltaSuccesses;
538 return true;
539 }
540 }
541 X->setPoint(SE->getConstant(Xq),
542 SE->getConstant(Yq),
543 X->getAssociatedLoop());
544 ++DeltaSuccesses;
545 return true;
546 }
547 return false;
548 }
549
550 // if (X->isLine() && Y->isPoint()) This case can't occur.
551 assert(!(X->isLine() && Y->isPoint()) && "This case should never occur")((!(X->isLine() && Y->isPoint()) && "This case should never occur"
) ? static_cast<void> (0) : __assert_fail ("!(X->isLine() && Y->isPoint()) && \"This case should never occur\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/Analysis/DependenceAnalysis.cpp"
, 551, __PRETTY_FUNCTION__))
;
552
553 if (X->isPoint() && Y->isLine()) {
554 LLVM_DEBUG(dbgs() << "\t intersect Point and Line\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\t intersect Point and Line\n";
} } while (false)
;
555 const SCEV *A1X1 = SE->getMulExpr(Y->getA(), X->getX());
556 const SCEV *B1Y1 = SE->getMulExpr(Y->getB(), X->getY());
557 const SCEV *Sum = SE->getAddExpr(A1X1, B1Y1);
558 if (isKnownPredicate(CmpInst::ICMP_EQ, Sum, Y->getC()))
559 return false;
560 if (isKnownPredicate(CmpInst::ICMP_NE, Sum, Y->getC())) {
561 X->setEmpty();
562 ++DeltaSuccesses;
563 return true;
564 }
565 return false;
566 }
567
568 llvm_unreachable("shouldn't reach the end of Constraint intersection")::llvm::llvm_unreachable_internal("shouldn't reach the end of Constraint intersection"
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/Analysis/DependenceAnalysis.cpp"
, 568)
;
569 return false;
570}
571
572
573//===----------------------------------------------------------------------===//
574// DependenceInfo methods
575
576// For debugging purposes. Dumps a dependence to OS.
577void Dependence::dump(raw_ostream &OS) const {
578 bool Splitable = false;
579 if (isConfused())
580 OS << "confused";
581 else {
582 if (isConsistent())
583 OS << "consistent ";
584 if (isFlow())
585 OS << "flow";
586 else if (isOutput())
587 OS << "output";
588 else if (isAnti())
589 OS << "anti";
590 else if (isInput())
591 OS << "input";
592 unsigned Levels = getLevels();
593 OS << " [";
594 for (unsigned II = 1; II <= Levels; ++II) {
595 if (isSplitable(II))
596 Splitable = true;
597 if (isPeelFirst(II))
598 OS << 'p';
599 const SCEV *Distance = getDistance(II);
600 if (Distance)
601 OS << *Distance;
602 else if (isScalar(II))
603 OS << "S";
604 else {
605 unsigned Direction = getDirection(II);
606 if (Direction == DVEntry::ALL)
607 OS << "*";
608 else {
609 if (Direction & DVEntry::LT)
610 OS << "<";
611 if (Direction & DVEntry::EQ)
612 OS << "=";
613 if (Direction & DVEntry::GT)
614 OS << ">";
615 }
616 }
617 if (isPeelLast(II))
618 OS << 'p';
619 if (II < Levels)
620 OS << " ";
621 }
622 if (isLoopIndependent())
623 OS << "|<";
624 OS << "]";
625 if (Splitable)
626 OS << " splitable";
627 }
628 OS << "!\n";
629}
630
631// Returns NoAlias/MayAliass/MustAlias for two memory locations based upon their
632// underlaying objects. If LocA and LocB are known to not alias (for any reason:
633// tbaa, non-overlapping regions etc), then it is known there is no dependecy.
634// Otherwise the underlying objects are checked to see if they point to
635// different identifiable objects.
636static AliasResult underlyingObjectsAlias(AliasAnalysis *AA,
637 const DataLayout &DL,
638 const MemoryLocation &LocA,
639 const MemoryLocation &LocB) {
640 // Check the original locations (minus size) for noalias, which can happen for
641 // tbaa, incompatible underlying object locations, etc.
642 MemoryLocation LocAS(LocA.Ptr, LocationSize::unknown(), LocA.AATags);
643 MemoryLocation LocBS(LocB.Ptr, LocationSize::unknown(), LocB.AATags);
644 if (AA->alias(LocAS, LocBS) == NoAlias)
645 return NoAlias;
646
647 // Check the underlying objects are the same
648 const Value *AObj = GetUnderlyingObject(LocA.Ptr, DL);
649 const Value *BObj = GetUnderlyingObject(LocB.Ptr, DL);
650
651 // If the underlying objects are the same, they must alias
652 if (AObj == BObj)
653 return MustAlias;
654
655 // We may have hit the recursion limit for underlying objects, or have
656 // underlying objects where we don't know they will alias.
657 if (!isIdentifiedObject(AObj) || !isIdentifiedObject(BObj))
658 return MayAlias;
659
660 // Otherwise we know the objects are different and both identified objects so
661 // must not alias.
662 return NoAlias;
663}
664
665
666// Returns true if the load or store can be analyzed. Atomic and volatile
667// operations have properties which this analysis does not understand.
668static
669bool isLoadOrStore(const Instruction *I) {
670 if (const LoadInst *LI = dyn_cast<LoadInst>(I))
671 return LI->isUnordered();
672 else if (const StoreInst *SI = dyn_cast<StoreInst>(I))
673 return SI->isUnordered();
674 return false;
675}
676
677
678// Examines the loop nesting of the Src and Dst
679// instructions and establishes their shared loops. Sets the variables
680// CommonLevels, SrcLevels, and MaxLevels.
681// The source and destination instructions needn't be contained in the same
682// loop. The routine establishNestingLevels finds the level of most deeply
683// nested loop that contains them both, CommonLevels. An instruction that's
684// not contained in a loop is at level = 0. MaxLevels is equal to the level
685// of the source plus the level of the destination, minus CommonLevels.
686// This lets us allocate vectors MaxLevels in length, with room for every
687// distinct loop referenced in both the source and destination subscripts.
688// The variable SrcLevels is the nesting depth of the source instruction.
689// It's used to help calculate distinct loops referenced by the destination.
690// Here's the map from loops to levels:
691// 0 - unused
692// 1 - outermost common loop
693// ... - other common loops
694// CommonLevels - innermost common loop
695// ... - loops containing Src but not Dst
696// SrcLevels - innermost loop containing Src but not Dst
697// ... - loops containing Dst but not Src
698// MaxLevels - innermost loops containing Dst but not Src
699// Consider the follow code fragment:
700// for (a = ...) {
701// for (b = ...) {
702// for (c = ...) {
703// for (d = ...) {
704// A[] = ...;
705// }
706// }
707// for (e = ...) {
708// for (f = ...) {
709// for (g = ...) {
710// ... = A[];
711// }
712// }
713// }
714// }
715// }
716// If we're looking at the possibility of a dependence between the store
717// to A (the Src) and the load from A (the Dst), we'll note that they
718// have 2 loops in common, so CommonLevels will equal 2 and the direction
719// vector for Result will have 2 entries. SrcLevels = 4 and MaxLevels = 7.
720// A map from loop names to loop numbers would look like
721// a - 1
722// b - 2 = CommonLevels
723// c - 3
724// d - 4 = SrcLevels
725// e - 5
726// f - 6
727// g - 7 = MaxLevels
728void DependenceInfo::establishNestingLevels(const Instruction *Src,
729 const Instruction *Dst) {
730 const BasicBlock *SrcBlock = Src->getParent();
731 const BasicBlock *DstBlock = Dst->getParent();
732 unsigned SrcLevel = LI->getLoopDepth(SrcBlock);
733 unsigned DstLevel = LI->getLoopDepth(DstBlock);
734 const Loop *SrcLoop = LI->getLoopFor(SrcBlock);
735 const Loop *DstLoop = LI->getLoopFor(DstBlock);
736 SrcLevels = SrcLevel;
737 MaxLevels = SrcLevel + DstLevel;
738 while (SrcLevel > DstLevel) {
739 SrcLoop = SrcLoop->getParentLoop();
740 SrcLevel--;
741 }
742 while (DstLevel > SrcLevel) {
743 DstLoop = DstLoop->getParentLoop();
744 DstLevel--;
745 }
746 while (SrcLoop != DstLoop) {
747 SrcLoop = SrcLoop->getParentLoop();
748 DstLoop = DstLoop->getParentLoop();
749 SrcLevel--;
750 }
751 CommonLevels = SrcLevel;
752 MaxLevels -= CommonLevels;
753}
754
755
756// Given one of the loops containing the source, return
757// its level index in our numbering scheme.
758unsigned DependenceInfo::mapSrcLoop(const Loop *SrcLoop) const {
759 return SrcLoop->getLoopDepth();
760}
761
762
763// Given one of the loops containing the destination,
764// return its level index in our numbering scheme.
765unsigned DependenceInfo::mapDstLoop(const Loop *DstLoop) const {
766 unsigned D = DstLoop->getLoopDepth();
767 if (D > CommonLevels)
768 return D - CommonLevels + SrcLevels;
769 else
770 return D;
771}
772
773
774// Returns true if Expression is loop invariant in LoopNest.
775bool DependenceInfo::isLoopInvariant(const SCEV *Expression,
776 const Loop *LoopNest) const {
777 if (!LoopNest)
778 return true;
779 return SE->isLoopInvariant(Expression, LoopNest) &&
780 isLoopInvariant(Expression, LoopNest->getParentLoop());
781}
782
783
784
785// Finds the set of loops from the LoopNest that
786// have a level <= CommonLevels and are referred to by the SCEV Expression.
787void DependenceInfo::collectCommonLoops(const SCEV *Expression,
788 const Loop *LoopNest,
789 SmallBitVector &Loops) const {
790 while (LoopNest) {
791 unsigned Level = LoopNest->getLoopDepth();
792 if (Level <= CommonLevels && !SE->isLoopInvariant(Expression, LoopNest))
793 Loops.set(Level);
794 LoopNest = LoopNest->getParentLoop();
795 }
796}
797
798void DependenceInfo::unifySubscriptType(ArrayRef<Subscript *> Pairs) {
799
800 unsigned widestWidthSeen = 0;
801 Type *widestType;
802
803 // Go through each pair and find the widest bit to which we need
804 // to extend all of them.
805 for (Subscript *Pair : Pairs) {
806 const SCEV *Src = Pair->Src;
807 const SCEV *Dst = Pair->Dst;
808 IntegerType *SrcTy = dyn_cast<IntegerType>(Src->getType());
809 IntegerType *DstTy = dyn_cast<IntegerType>(Dst->getType());
810 if (SrcTy == nullptr || DstTy == nullptr) {
811 assert(SrcTy == DstTy && "This function only unify integer types and "((SrcTy == DstTy && "This function only unify integer types and "
"expect Src and Dst share the same type " "otherwise.") ? static_cast
<void> (0) : __assert_fail ("SrcTy == DstTy && \"This function only unify integer types and \" \"expect Src and Dst share the same type \" \"otherwise.\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/Analysis/DependenceAnalysis.cpp"
, 813, __PRETTY_FUNCTION__))
812 "expect Src and Dst share the same type "((SrcTy == DstTy && "This function only unify integer types and "
"expect Src and Dst share the same type " "otherwise.") ? static_cast
<void> (0) : __assert_fail ("SrcTy == DstTy && \"This function only unify integer types and \" \"expect Src and Dst share the same type \" \"otherwise.\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/Analysis/DependenceAnalysis.cpp"
, 813, __PRETTY_FUNCTION__))
813 "otherwise.")((SrcTy == DstTy && "This function only unify integer types and "
"expect Src and Dst share the same type " "otherwise.") ? static_cast
<void> (0) : __assert_fail ("SrcTy == DstTy && \"This function only unify integer types and \" \"expect Src and Dst share the same type \" \"otherwise.\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/Analysis/DependenceAnalysis.cpp"
, 813, __PRETTY_FUNCTION__))
;
814 continue;
815 }
816 if (SrcTy->getBitWidth() > widestWidthSeen) {
817 widestWidthSeen = SrcTy->getBitWidth();
818 widestType = SrcTy;
819 }
820 if (DstTy->getBitWidth() > widestWidthSeen) {
821 widestWidthSeen = DstTy->getBitWidth();
822 widestType = DstTy;
823 }
824 }
825
826
827 assert(widestWidthSeen > 0)((widestWidthSeen > 0) ? static_cast<void> (0) : __assert_fail
("widestWidthSeen > 0", "/build/llvm-toolchain-snapshot-9~svn362543/lib/Analysis/DependenceAnalysis.cpp"
, 827, __PRETTY_FUNCTION__))
;
828
829 // Now extend each pair to the widest seen.
830 for (Subscript *Pair : Pairs) {
831 const SCEV *Src = Pair->Src;
832 const SCEV *Dst = Pair->Dst;
833 IntegerType *SrcTy = dyn_cast<IntegerType>(Src->getType());
834 IntegerType *DstTy = dyn_cast<IntegerType>(Dst->getType());
835 if (SrcTy == nullptr || DstTy == nullptr) {
836 assert(SrcTy == DstTy && "This function only unify integer types and "((SrcTy == DstTy && "This function only unify integer types and "
"expect Src and Dst share the same type " "otherwise.") ? static_cast
<void> (0) : __assert_fail ("SrcTy == DstTy && \"This function only unify integer types and \" \"expect Src and Dst share the same type \" \"otherwise.\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/Analysis/DependenceAnalysis.cpp"
, 838, __PRETTY_FUNCTION__))
837 "expect Src and Dst share the same type "((SrcTy == DstTy && "This function only unify integer types and "
"expect Src and Dst share the same type " "otherwise.") ? static_cast
<void> (0) : __assert_fail ("SrcTy == DstTy && \"This function only unify integer types and \" \"expect Src and Dst share the same type \" \"otherwise.\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/Analysis/DependenceAnalysis.cpp"
, 838, __PRETTY_FUNCTION__))
838 "otherwise.")((SrcTy == DstTy && "This function only unify integer types and "
"expect Src and Dst share the same type " "otherwise.") ? static_cast
<void> (0) : __assert_fail ("SrcTy == DstTy && \"This function only unify integer types and \" \"expect Src and Dst share the same type \" \"otherwise.\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/Analysis/DependenceAnalysis.cpp"
, 838, __PRETTY_FUNCTION__))
;
839 continue;
840 }
841 if (SrcTy->getBitWidth() < widestWidthSeen)
842 // Sign-extend Src to widestType
843 Pair->Src = SE->getSignExtendExpr(Src, widestType);
844 if (DstTy->getBitWidth() < widestWidthSeen) {
845 // Sign-extend Dst to widestType
846 Pair->Dst = SE->getSignExtendExpr(Dst, widestType);
847 }
848 }
849}
850
851// removeMatchingExtensions - Examines a subscript pair.
852// If the source and destination are identically sign (or zero)
853// extended, it strips off the extension in an effect to simplify
854// the actual analysis.
855void DependenceInfo::removeMatchingExtensions(Subscript *Pair) {
856 const SCEV *Src = Pair->Src;
857 const SCEV *Dst = Pair->Dst;
858 if ((isa<SCEVZeroExtendExpr>(Src) && isa<SCEVZeroExtendExpr>(Dst)) ||
859 (isa<SCEVSignExtendExpr>(Src) && isa<SCEVSignExtendExpr>(Dst))) {
860 const SCEVCastExpr *SrcCast = cast<SCEVCastExpr>(Src);
861 const SCEVCastExpr *DstCast = cast<SCEVCastExpr>(Dst);
862 const SCEV *SrcCastOp = SrcCast->getOperand();
863 const SCEV *DstCastOp = DstCast->getOperand();
864 if (SrcCastOp->getType() == DstCastOp->getType()) {
865 Pair->Src = SrcCastOp;
866 Pair->Dst = DstCastOp;
867 }
868 }
869}
870
871
872// Examine the scev and return true iff it's linear.
873// Collect any loops mentioned in the set of "Loops".
874bool DependenceInfo::checkSrcSubscript(const SCEV *Src, const Loop *LoopNest,
875 SmallBitVector &Loops) {
876 const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(Src);
877 if (!AddRec)
878 return isLoopInvariant(Src, LoopNest);
879 const SCEV *Start = AddRec->getStart();
880 const SCEV *Step = AddRec->getStepRecurrence(*SE);
881 const SCEV *UB = SE->getBackedgeTakenCount(AddRec->getLoop());
882 if (!isa<SCEVCouldNotCompute>(UB)) {
883 if (SE->getTypeSizeInBits(Start->getType()) <
884 SE->getTypeSizeInBits(UB->getType())) {
885 if (!AddRec->getNoWrapFlags())
886 return false;
887 }
888 }
889 if (!isLoopInvariant(Step, LoopNest))
890 return false;
891 Loops.set(mapSrcLoop(AddRec->getLoop()));
892 return checkSrcSubscript(Start, LoopNest, Loops);
893}
894
895
896
897// Examine the scev and return true iff it's linear.
898// Collect any loops mentioned in the set of "Loops".
899bool DependenceInfo::checkDstSubscript(const SCEV *Dst, const Loop *LoopNest,
900 SmallBitVector &Loops) {
901 const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(Dst);
902 if (!AddRec)
903 return isLoopInvariant(Dst, LoopNest);
904 const SCEV *Start = AddRec->getStart();
905 const SCEV *Step = AddRec->getStepRecurrence(*SE);
906 const SCEV *UB = SE->getBackedgeTakenCount(AddRec->getLoop());
907 if (!isa<SCEVCouldNotCompute>(UB)) {
908 if (SE->getTypeSizeInBits(Start->getType()) <
909 SE->getTypeSizeInBits(UB->getType())) {
910 if (!AddRec->getNoWrapFlags())
911 return false;
912 }
913 }
914 if (!isLoopInvariant(Step, LoopNest))
915 return false;
916 Loops.set(mapDstLoop(AddRec->getLoop()));
917 return checkDstSubscript(Start, LoopNest, Loops);
918}
919
920
921// Examines the subscript pair (the Src and Dst SCEVs)
922// and classifies it as either ZIV, SIV, RDIV, MIV, or Nonlinear.
923// Collects the associated loops in a set.
924DependenceInfo::Subscript::ClassificationKind
925DependenceInfo::classifyPair(const SCEV *Src, const Loop *SrcLoopNest,
926 const SCEV *Dst, const Loop *DstLoopNest,
927 SmallBitVector &Loops) {
928 SmallBitVector SrcLoops(MaxLevels + 1);
14
Calling constructor for 'SmallBitVector'
17
Returning from constructor for 'SmallBitVector'
929 SmallBitVector DstLoops(MaxLevels + 1);
930 if (!checkSrcSubscript(Src, SrcLoopNest, SrcLoops))
18
Taking true branch
931 return Subscript::NonLinear;
932 if (!checkDstSubscript(Dst, DstLoopNest, DstLoops))
933 return Subscript::NonLinear;
934 Loops = SrcLoops;
935 Loops |= DstLoops;
936 unsigned N = Loops.count();
937 if (N == 0)
938 return Subscript::ZIV;
939 if (N == 1)
940 return Subscript::SIV;
941 if (N == 2 && (SrcLoops.count() == 0 ||
942 DstLoops.count() == 0 ||
943 (SrcLoops.count() == 1 && DstLoops.count() == 1)))
944 return Subscript::RDIV;
945 return Subscript::MIV;
946}
19
Potential leak of memory pointed to by 'SrcLoops.X'
947
948
949// A wrapper around SCEV::isKnownPredicate.
950// Looks for cases where we're interested in comparing for equality.
951// If both X and Y have been identically sign or zero extended,
952// it strips off the (confusing) extensions before invoking
953// SCEV::isKnownPredicate. Perhaps, someday, the ScalarEvolution package
954// will be similarly updated.
955//
956// If SCEV::isKnownPredicate can't prove the predicate,
957// we try simple subtraction, which seems to help in some cases
958// involving symbolics.
959bool DependenceInfo::isKnownPredicate(ICmpInst::Predicate Pred, const SCEV *X,
960 const SCEV *Y) const {
961 if (Pred == CmpInst::ICMP_EQ ||
962 Pred == CmpInst::ICMP_NE) {
963 if ((isa<SCEVSignExtendExpr>(X) &&
964 isa<SCEVSignExtendExpr>(Y)) ||
965 (isa<SCEVZeroExtendExpr>(X) &&
966 isa<SCEVZeroExtendExpr>(Y))) {
967 const SCEVCastExpr *CX = cast<SCEVCastExpr>(X);
968 const SCEVCastExpr *CY = cast<SCEVCastExpr>(Y);
969 const SCEV *Xop = CX->getOperand();
970 const SCEV *Yop = CY->getOperand();
971 if (Xop->getType() == Yop->getType()) {
972 X = Xop;
973 Y = Yop;
974 }
975 }
976 }
977 if (SE->isKnownPredicate(Pred, X, Y))
978 return true;
979 // If SE->isKnownPredicate can't prove the condition,
980 // we try the brute-force approach of subtracting
981 // and testing the difference.
982 // By testing with SE->isKnownPredicate first, we avoid
983 // the possibility of overflow when the arguments are constants.
984 const SCEV *Delta = SE->getMinusSCEV(X, Y);
985 switch (Pred) {
986 case CmpInst::ICMP_EQ:
987 return Delta->isZero();
988 case CmpInst::ICMP_NE:
989 return SE->isKnownNonZero(Delta);
990 case CmpInst::ICMP_SGE:
991 return SE->isKnownNonNegative(Delta);
992 case CmpInst::ICMP_SLE:
993 return SE->isKnownNonPositive(Delta);
994 case CmpInst::ICMP_SGT:
995 return SE->isKnownPositive(Delta);
996 case CmpInst::ICMP_SLT:
997 return SE->isKnownNegative(Delta);
998 default:
999 llvm_unreachable("unexpected predicate in isKnownPredicate")::llvm::llvm_unreachable_internal("unexpected predicate in isKnownPredicate"
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/Analysis/DependenceAnalysis.cpp"
, 999)
;
1000 }
1001}
1002
1003/// Compare to see if S is less than Size, using isKnownNegative(S - max(Size, 1))
1004/// with some extra checking if S is an AddRec and we can prove less-than using
1005/// the loop bounds.
1006bool DependenceInfo::isKnownLessThan(const SCEV *S, const SCEV *Size) const {
1007 // First unify to the same type
1008 auto *SType = dyn_cast<IntegerType>(S->getType());
1009 auto *SizeType = dyn_cast<IntegerType>(Size->getType());
1010 if (!SType || !SizeType)
1011 return false;
1012 Type *MaxType =
1013 (SType->getBitWidth() >= SizeType->getBitWidth()) ? SType : SizeType;
1014 S = SE->getTruncateOrZeroExtend(S, MaxType);
1015 Size = SE->getTruncateOrZeroExtend(Size, MaxType);
1016
1017 // Special check for addrecs using BE taken count
1018 const SCEV *Bound = SE->getMinusSCEV(S, Size);
1019 if (const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(Bound)) {
1020 if (AddRec->isAffine()) {
1021 const SCEV *BECount = SE->getBackedgeTakenCount(AddRec->getLoop());
1022 if (!isa<SCEVCouldNotCompute>(BECount)) {
1023 const SCEV *Limit = AddRec->evaluateAtIteration(BECount, *SE);
1024 if (SE->isKnownNegative(Limit))
1025 return true;
1026 }
1027 }
1028 }
1029
1030 // Check using normal isKnownNegative
1031 const SCEV *LimitedBound =
1032 SE->getMinusSCEV(S, SE->getSMaxExpr(Size, SE->getOne(Size->getType())));
1033 return SE->isKnownNegative(LimitedBound);
1034}
1035
1036bool DependenceInfo::isKnownNonNegative(const SCEV *S, const Value *Ptr) const {
1037 bool Inbounds = false;
1038 if (auto *SrcGEP = dyn_cast<GetElementPtrInst>(Ptr))
1039 Inbounds = SrcGEP->isInBounds();
1040 if (Inbounds) {
1041 if (const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(S)) {
1042 if (AddRec->isAffine()) {
1043 // We know S is for Ptr, the operand on a load/store, so doesn't wrap.
1044 // If both parts are NonNegative, the end result will be NonNegative
1045 if (SE->isKnownNonNegative(AddRec->getStart()) &&
1046 SE->isKnownNonNegative(AddRec->getOperand(1)))
1047 return true;
1048 }
1049 }
1050 }
1051
1052 return SE->isKnownNonNegative(S);
1053}
1054
1055// All subscripts are all the same type.
1056// Loop bound may be smaller (e.g., a char).
1057// Should zero extend loop bound, since it's always >= 0.
1058// This routine collects upper bound and extends or truncates if needed.
1059// Truncating is safe when subscripts are known not to wrap. Cases without
1060// nowrap flags should have been rejected earlier.
1061// Return null if no bound available.
1062const SCEV *DependenceInfo::collectUpperBound(const Loop *L, Type *T) const {
1063 if (SE->hasLoopInvariantBackedgeTakenCount(L)) {
1064 const SCEV *UB = SE->getBackedgeTakenCount(L);
1065 return SE->getTruncateOrZeroExtend(UB, T);
1066 }
1067 return nullptr;
1068}
1069
1070
1071// Calls collectUpperBound(), then attempts to cast it to SCEVConstant.
1072// If the cast fails, returns NULL.
1073const SCEVConstant *DependenceInfo::collectConstantUpperBound(const Loop *L,
1074 Type *T) const {
1075 if (const SCEV *UB = collectUpperBound(L, T))
1076 return dyn_cast<SCEVConstant>(UB);
1077 return nullptr;
1078}
1079
1080
1081// testZIV -
1082// When we have a pair of subscripts of the form [c1] and [c2],
1083// where c1 and c2 are both loop invariant, we attack it using
1084// the ZIV test. Basically, we test by comparing the two values,
1085// but there are actually three possible results:
1086// 1) the values are equal, so there's a dependence
1087// 2) the values are different, so there's no dependence
1088// 3) the values might be equal, so we have to assume a dependence.
1089//
1090// Return true if dependence disproved.
1091bool DependenceInfo::testZIV(const SCEV *Src, const SCEV *Dst,
1092 FullDependence &Result) const {
1093 LLVM_DEBUG(dbgs() << " src = " << *Src << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << " src = " << *Src <<
"\n"; } } while (false)
;
1094 LLVM_DEBUG(dbgs() << " dst = " << *Dst << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << " dst = " << *Dst <<
"\n"; } } while (false)
;
1095 ++ZIVapplications;
1096 if (isKnownPredicate(CmpInst::ICMP_EQ, Src, Dst)) {
1097 LLVM_DEBUG(dbgs() << " provably dependent\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << " provably dependent\n"; } } while
(false)
;
1098 return false; // provably dependent
1099 }
1100 if (isKnownPredicate(CmpInst::ICMP_NE, Src, Dst)) {
1101 LLVM_DEBUG(dbgs() << " provably independent\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << " provably independent\n"; } } while
(false)
;
1102 ++ZIVindependence;
1103 return true; // provably independent
1104 }
1105 LLVM_DEBUG(dbgs() << " possibly dependent\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << " possibly dependent\n"; } } while
(false)
;
1106 Result.Consistent = false;
1107 return false; // possibly dependent
1108}
1109
1110
1111// strongSIVtest -
1112// From the paper, Practical Dependence Testing, Section 4.2.1
1113//
1114// When we have a pair of subscripts of the form [c1 + a*i] and [c2 + a*i],
1115// where i is an induction variable, c1 and c2 are loop invariant,
1116// and a is a constant, we can solve it exactly using the Strong SIV test.
1117//
1118// Can prove independence. Failing that, can compute distance (and direction).
1119// In the presence of symbolic terms, we can sometimes make progress.
1120//
1121// If there's a dependence,
1122//
1123// c1 + a*i = c2 + a*i'
1124//
1125// The dependence distance is
1126//
1127// d = i' - i = (c1 - c2)/a
1128//
1129// A dependence only exists if d is an integer and abs(d) <= U, where U is the
1130// loop's upper bound. If a dependence exists, the dependence direction is
1131// defined as
1132//
1133// { < if d > 0
1134// direction = { = if d = 0
1135// { > if d < 0
1136//
1137// Return true if dependence disproved.
1138bool DependenceInfo::strongSIVtest(const SCEV *Coeff, const SCEV *SrcConst,
1139 const SCEV *DstConst, const Loop *CurLoop,
1140 unsigned Level, FullDependence &Result,
1141 Constraint &NewConstraint) const {
1142 LLVM_DEBUG(dbgs() << "\tStrong SIV test\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\tStrong SIV test\n"; } } while (false
)
;
1143 LLVM_DEBUG(dbgs() << "\t Coeff = " << *Coeff)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\t Coeff = " << *Coeff; }
} while (false)
;
1144 LLVM_DEBUG(dbgs() << ", " << *Coeff->getType() << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << ", " << *Coeff->getType() <<
"\n"; } } while (false)
;
1145 LLVM_DEBUG(dbgs() << "\t SrcConst = " << *SrcConst)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\t SrcConst = " << *SrcConst
; } } while (false)
;
1146 LLVM_DEBUG(dbgs() << ", " << *SrcConst->getType() << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << ", " << *SrcConst->getType
() << "\n"; } } while (false)
;
1147 LLVM_DEBUG(dbgs() << "\t DstConst = " << *DstConst)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\t DstConst = " << *DstConst
; } } while (false)
;
1148 LLVM_DEBUG(dbgs() << ", " << *DstConst->getType() << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << ", " << *DstConst->getType
() << "\n"; } } while (false)
;
1149 ++StrongSIVapplications;
1150 assert(0 < Level && Level <= CommonLevels && "level out of range")((0 < Level && Level <= CommonLevels &&
"level out of range") ? static_cast<void> (0) : __assert_fail
("0 < Level && Level <= CommonLevels && \"level out of range\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/Analysis/DependenceAnalysis.cpp"
, 1150, __PRETTY_FUNCTION__))
;
1151 Level--;
1152
1153 const SCEV *Delta = SE->getMinusSCEV(SrcConst, DstConst);
1154 LLVM_DEBUG(dbgs() << "\t Delta = " << *Delta)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\t Delta = " << *Delta; }
} while (false)
;
1155 LLVM_DEBUG(dbgs() << ", " << *Delta->getType() << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << ", " << *Delta->getType() <<
"\n"; } } while (false)
;
1156
1157 // check that |Delta| < iteration count
1158 if (const SCEV *UpperBound = collectUpperBound(CurLoop, Delta->getType())) {
1159 LLVM_DEBUG(dbgs() << "\t UpperBound = " << *UpperBound)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\t UpperBound = " << *UpperBound
; } } while (false)
;
1160 LLVM_DEBUG(dbgs() << ", " << *UpperBound->getType() << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << ", " << *UpperBound->getType
() << "\n"; } } while (false)
;
1161 const SCEV *AbsDelta =
1162 SE->isKnownNonNegative(Delta) ? Delta : SE->getNegativeSCEV(Delta);
1163 const SCEV *AbsCoeff =
1164 SE->isKnownNonNegative(Coeff) ? Coeff : SE->getNegativeSCEV(Coeff);
1165 const SCEV *Product = SE->getMulExpr(UpperBound, AbsCoeff);
1166 if (isKnownPredicate(CmpInst::ICMP_SGT, AbsDelta, Product)) {
1167 // Distance greater than trip count - no dependence
1168 ++StrongSIVindependence;
1169 ++StrongSIVsuccesses;
1170 return true;
1171 }
1172 }
1173
1174 // Can we compute distance?
1175 if (isa<SCEVConstant>(Delta) && isa<SCEVConstant>(Coeff)) {
1176 APInt ConstDelta = cast<SCEVConstant>(Delta)->getAPInt();
1177 APInt ConstCoeff = cast<SCEVConstant>(Coeff)->getAPInt();
1178 APInt Distance = ConstDelta; // these need to be initialized
1179 APInt Remainder = ConstDelta;
1180 APInt::sdivrem(ConstDelta, ConstCoeff, Distance, Remainder);
1181 LLVM_DEBUG(dbgs() << "\t Distance = " << Distance << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\t Distance = " << Distance
<< "\n"; } } while (false)
;
1182 LLVM_DEBUG(dbgs() << "\t Remainder = " << Remainder << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\t Remainder = " << Remainder
<< "\n"; } } while (false)
;
1183 // Make sure Coeff divides Delta exactly
1184 if (Remainder != 0) {
1185 // Coeff doesn't divide Distance, no dependence
1186 ++StrongSIVindependence;
1187 ++StrongSIVsuccesses;
1188 return true;
1189 }
1190 Result.DV[Level].Distance = SE->getConstant(Distance);
1191 NewConstraint.setDistance(SE->getConstant(Distance), CurLoop);
1192 if (Distance.sgt(0))
1193 Result.DV[Level].Direction &= Dependence::DVEntry::LT;
1194 else if (Distance.slt(0))
1195 Result.DV[Level].Direction &= Dependence::DVEntry::GT;
1196 else
1197 Result.DV[Level].Direction &= Dependence::DVEntry::EQ;
1198 ++StrongSIVsuccesses;
1199 }
1200 else if (Delta->isZero()) {
1201 // since 0/X == 0
1202 Result.DV[Level].Distance = Delta;
1203 NewConstraint.setDistance(Delta, CurLoop);
1204 Result.DV[Level].Direction &= Dependence::DVEntry::EQ;
1205 ++StrongSIVsuccesses;
1206 }
1207 else {
1208 if (Coeff->isOne()) {
1209 LLVM_DEBUG(dbgs() << "\t Distance = " << *Delta << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\t Distance = " << *Delta
<< "\n"; } } while (false)
;
1210 Result.DV[Level].Distance = Delta; // since X/1 == X
1211 NewConstraint.setDistance(Delta, CurLoop);
1212 }
1213 else {
1214 Result.Consistent = false;
1215 NewConstraint.setLine(Coeff,
1216 SE->getNegativeSCEV(Coeff),
1217 SE->getNegativeSCEV(Delta), CurLoop);
1218 }
1219
1220 // maybe we can get a useful direction
1221 bool DeltaMaybeZero = !SE->isKnownNonZero(Delta);
1222 bool DeltaMaybePositive = !SE->isKnownNonPositive(Delta);
1223 bool DeltaMaybeNegative = !SE->isKnownNonNegative(Delta);
1224 bool CoeffMaybePositive = !SE->isKnownNonPositive(Coeff);
1225 bool CoeffMaybeNegative = !SE->isKnownNonNegative(Coeff);
1226 // The double negatives above are confusing.
1227 // It helps to read !SE->isKnownNonZero(Delta)
1228 // as "Delta might be Zero"
1229 unsigned NewDirection = Dependence::DVEntry::NONE;
1230 if ((DeltaMaybePositive && CoeffMaybePositive) ||
1231 (DeltaMaybeNegative && CoeffMaybeNegative))
1232 NewDirection = Dependence::DVEntry::LT;
1233 if (DeltaMaybeZero)
1234 NewDirection |= Dependence::DVEntry::EQ;
1235 if ((DeltaMaybeNegative && CoeffMaybePositive) ||
1236 (DeltaMaybePositive && CoeffMaybeNegative))
1237 NewDirection |= Dependence::DVEntry::GT;
1238 if (NewDirection < Result.DV[Level].Direction)
1239 ++StrongSIVsuccesses;
1240 Result.DV[Level].Direction &= NewDirection;
1241 }
1242 return false;
1243}
1244
1245
1246// weakCrossingSIVtest -
1247// From the paper, Practical Dependence Testing, Section 4.2.2
1248//
1249// When we have a pair of subscripts of the form [c1 + a*i] and [c2 - a*i],
1250// where i is an induction variable, c1 and c2 are loop invariant,
1251// and a is a constant, we can solve it exactly using the
1252// Weak-Crossing SIV test.
1253//
1254// Given c1 + a*i = c2 - a*i', we can look for the intersection of
1255// the two lines, where i = i', yielding
1256//
1257// c1 + a*i = c2 - a*i
1258// 2a*i = c2 - c1
1259// i = (c2 - c1)/2a
1260//
1261// If i < 0, there is no dependence.
1262// If i > upperbound, there is no dependence.
1263// If i = 0 (i.e., if c1 = c2), there's a dependence with distance = 0.
1264// If i = upperbound, there's a dependence with distance = 0.
1265// If i is integral, there's a dependence (all directions).
1266// If the non-integer part = 1/2, there's a dependence (<> directions).
1267// Otherwise, there's no dependence.
1268//
1269// Can prove independence. Failing that,
1270// can sometimes refine the directions.
1271// Can determine iteration for splitting.
1272//
1273// Return true if dependence disproved.
1274bool DependenceInfo::weakCrossingSIVtest(
1275 const SCEV *Coeff, const SCEV *SrcConst, const SCEV *DstConst,
1276 const Loop *CurLoop, unsigned Level, FullDependence &Result,
1277 Constraint &NewConstraint, const SCEV *&SplitIter) const {
1278 LLVM_DEBUG(dbgs() << "\tWeak-Crossing SIV test\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\tWeak-Crossing SIV test\n"; } } while
(false)
;
1279 LLVM_DEBUG(dbgs() << "\t Coeff = " << *Coeff << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\t Coeff = " << *Coeff <<
"\n"; } } while (false)
;
1280 LLVM_DEBUG(dbgs() << "\t SrcConst = " << *SrcConst << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\t SrcConst = " << *SrcConst
<< "\n"; } } while (false)
;
1281 LLVM_DEBUG(dbgs() << "\t DstConst = " << *DstConst << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\t DstConst = " << *DstConst
<< "\n"; } } while (false)
;
1282 ++WeakCrossingSIVapplications;
1283 assert(0 < Level && Level <= CommonLevels && "Level out of range")((0 < Level && Level <= CommonLevels &&
"Level out of range") ? static_cast<void> (0) : __assert_fail
("0 < Level && Level <= CommonLevels && \"Level out of range\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/Analysis/DependenceAnalysis.cpp"
, 1283, __PRETTY_FUNCTION__))
;
1284 Level--;
1285 Result.Consistent = false;
1286 const SCEV *Delta = SE->getMinusSCEV(DstConst, SrcConst);
1287 LLVM_DEBUG(dbgs() << "\t Delta = " << *Delta << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\t Delta = " << *Delta <<
"\n"; } } while (false)
;
1288 NewConstraint.setLine(Coeff, Coeff, Delta, CurLoop);
1289 if (Delta->isZero()) {
1290 Result.DV[Level].Direction &= unsigned(~Dependence::DVEntry::LT);
1291 Result.DV[Level].Direction &= unsigned(~Dependence::DVEntry::GT);
1292 ++WeakCrossingSIVsuccesses;
1293 if (!Result.DV[Level].Direction) {
1294 ++WeakCrossingSIVindependence;
1295 return true;
1296 }
1297 Result.DV[Level].Distance = Delta; // = 0
1298 return false;
1299 }
1300 const SCEVConstant *ConstCoeff = dyn_cast<SCEVConstant>(Coeff);
1301 if (!ConstCoeff)
1302 return false;
1303
1304 Result.DV[Level].Splitable = true;
1305 if (SE->isKnownNegative(ConstCoeff)) {
1306 ConstCoeff = dyn_cast<SCEVConstant>(SE->getNegativeSCEV(ConstCoeff));
1307 assert(ConstCoeff &&((ConstCoeff && "dynamic cast of negative of ConstCoeff should yield constant"
) ? static_cast<void> (0) : __assert_fail ("ConstCoeff && \"dynamic cast of negative of ConstCoeff should yield constant\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/Analysis/DependenceAnalysis.cpp"
, 1308, __PRETTY_FUNCTION__))
1308 "dynamic cast of negative of ConstCoeff should yield constant")((ConstCoeff && "dynamic cast of negative of ConstCoeff should yield constant"
) ? static_cast<void> (0) : __assert_fail ("ConstCoeff && \"dynamic cast of negative of ConstCoeff should yield constant\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/Analysis/DependenceAnalysis.cpp"
, 1308, __PRETTY_FUNCTION__))
;
1309 Delta = SE->getNegativeSCEV(Delta);
1310 }
1311 assert(SE->isKnownPositive(ConstCoeff) && "ConstCoeff should be positive")((SE->isKnownPositive(ConstCoeff) && "ConstCoeff should be positive"
) ? static_cast<void> (0) : __assert_fail ("SE->isKnownPositive(ConstCoeff) && \"ConstCoeff should be positive\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/Analysis/DependenceAnalysis.cpp"
, 1311, __PRETTY_FUNCTION__))
;
1312
1313 // compute SplitIter for use by DependenceInfo::getSplitIteration()
1314 SplitIter = SE->getUDivExpr(
1315 SE->getSMaxExpr(SE->getZero(Delta->getType()), Delta),
1316 SE->getMulExpr(SE->getConstant(Delta->getType(), 2), ConstCoeff));
1317 LLVM_DEBUG(dbgs() << "\t Split iter = " << *SplitIter << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\t Split iter = " << *SplitIter
<< "\n"; } } while (false)
;
1318
1319 const SCEVConstant *ConstDelta = dyn_cast<SCEVConstant>(Delta);
1320 if (!ConstDelta)
1321 return false;
1322
1323 // We're certain that ConstCoeff > 0; therefore,
1324 // if Delta < 0, then no dependence.
1325 LLVM_DEBUG(dbgs() << "\t Delta = " << *Delta << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\t Delta = " << *Delta <<
"\n"; } } while (false)
;
1326 LLVM_DEBUG(dbgs() << "\t ConstCoeff = " << *ConstCoeff << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\t ConstCoeff = " << *ConstCoeff
<< "\n"; } } while (false)
;
1327 if (SE->isKnownNegative(Delta)) {
1328 // No dependence, Delta < 0
1329 ++WeakCrossingSIVindependence;
1330 ++WeakCrossingSIVsuccesses;
1331 return true;
1332 }
1333
1334 // We're certain that Delta > 0 and ConstCoeff > 0.
1335 // Check Delta/(2*ConstCoeff) against upper loop bound
1336 if (const SCEV *UpperBound = collectUpperBound(CurLoop, Delta->getType())) {
1337 LLVM_DEBUG(dbgs() << "\t UpperBound = " << *UpperBound << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\t UpperBound = " << *UpperBound
<< "\n"; } } while (false)
;
1338 const SCEV *ConstantTwo = SE->getConstant(UpperBound->getType(), 2);
1339 const SCEV *ML = SE->getMulExpr(SE->getMulExpr(ConstCoeff, UpperBound),
1340 ConstantTwo);
1341 LLVM_DEBUG(dbgs() << "\t ML = " << *ML << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\t ML = " << *ML <<
"\n"; } } while (false)
;
1342 if (isKnownPredicate(CmpInst::ICMP_SGT, Delta, ML)) {
1343 // Delta too big, no dependence
1344 ++WeakCrossingSIVindependence;
1345 ++WeakCrossingSIVsuccesses;
1346 return true;
1347 }
1348 if (isKnownPredicate(CmpInst::ICMP_EQ, Delta, ML)) {
1349 // i = i' = UB
1350 Result.DV[Level].Direction &= unsigned(~Dependence::DVEntry::LT);
1351 Result.DV[Level].Direction &= unsigned(~Dependence::DVEntry::GT);
1352 ++WeakCrossingSIVsuccesses;
1353 if (!Result.DV[Level].Direction) {
1354 ++WeakCrossingSIVindependence;
1355 return true;
1356 }
1357 Result.DV[Level].Splitable = false;
1358 Result.DV[Level].Distance = SE->getZero(Delta->getType());
1359 return false;
1360 }
1361 }
1362
1363 // check that Coeff divides Delta
1364 APInt APDelta = ConstDelta->getAPInt();
1365 APInt APCoeff = ConstCoeff->getAPInt();
1366 APInt Distance = APDelta; // these need to be initialzed
1367 APInt Remainder = APDelta;
1368 APInt::sdivrem(APDelta, APCoeff, Distance, Remainder);
1369 LLVM_DEBUG(dbgs() << "\t Remainder = " << Remainder << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\t Remainder = " << Remainder
<< "\n"; } } while (false)
;
1370 if (Remainder != 0) {
1371 // Coeff doesn't divide Delta, no dependence
1372 ++WeakCrossingSIVindependence;
1373 ++WeakCrossingSIVsuccesses;
1374 return true;
1375 }
1376 LLVM_DEBUG(dbgs() << "\t Distance = " << Distance << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\t Distance = " << Distance
<< "\n"; } } while (false)
;
1377
1378 // if 2*Coeff doesn't divide Delta, then the equal direction isn't possible
1379 APInt Two = APInt(Distance.getBitWidth(), 2, true);
1380 Remainder = Distance.srem(Two);
1381 LLVM_DEBUG(dbgs() << "\t Remainder = " << Remainder << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\t Remainder = " << Remainder
<< "\n"; } } while (false)
;
1382 if (Remainder != 0) {
1383 // Equal direction isn't possible
1384 Result.DV[Level].Direction &= unsigned(~Dependence::DVEntry::EQ);
1385 ++WeakCrossingSIVsuccesses;
1386 }
1387 return false;
1388}
1389
1390
1391// Kirch's algorithm, from
1392//
1393// Optimizing Supercompilers for Supercomputers
1394// Michael Wolfe
1395// MIT Press, 1989
1396//
1397// Program 2.1, page 29.
1398// Computes the GCD of AM and BM.
1399// Also finds a solution to the equation ax - by = gcd(a, b).
1400// Returns true if dependence disproved; i.e., gcd does not divide Delta.
1401static bool findGCD(unsigned Bits, const APInt &AM, const APInt &BM,
1402 const APInt &Delta, APInt &G, APInt &X, APInt &Y) {
1403 APInt A0(Bits, 1, true), A1(Bits, 0, true);
1404 APInt B0(Bits, 0, true), B1(Bits, 1, true);
1405 APInt G0 = AM.abs();
1406 APInt G1 = BM.abs();
1407 APInt Q = G0; // these need to be initialized
1408 APInt R = G0;
1409 APInt::sdivrem(G0, G1, Q, R);
1410 while (R != 0) {
1411 APInt A2 = A0 - Q*A1; A0 = A1; A1 = A2;
1412 APInt B2 = B0 - Q*B1; B0 = B1; B1 = B2;
1413 G0 = G1; G1 = R;
1414 APInt::sdivrem(G0, G1, Q, R);
1415 }
1416 G = G1;
1417 LLVM_DEBUG(dbgs() << "\t GCD = " << G << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\t GCD = " << G << "\n"
; } } while (false)
;
1418 X = AM.slt(0) ? -A1 : A1;
1419 Y = BM.slt(0) ? B1 : -B1;
1420
1421 // make sure gcd divides Delta
1422 R = Delta.srem(G);
1423 if (R != 0)
1424 return true; // gcd doesn't divide Delta, no dependence
1425 Q = Delta.sdiv(G);
1426 X *= Q;
1427 Y *= Q;
1428 return false;
1429}
1430
1431static APInt floorOfQuotient(const APInt &A, const APInt &B) {
1432 APInt Q = A; // these need to be initialized
1433 APInt R = A;
1434 APInt::sdivrem(A, B, Q, R);
1435 if (R == 0)
1436 return Q;
1437 if ((A.sgt(0) && B.sgt(0)) ||
1438 (A.slt(0) && B.slt(0)))
1439 return Q;
1440 else
1441 return Q - 1;
1442}
1443
1444static APInt ceilingOfQuotient(const APInt &A, const APInt &B) {
1445 APInt Q = A; // these need to be initialized
1446 APInt R = A;
1447 APInt::sdivrem(A, B, Q, R);
1448 if (R == 0)
1449 return Q;
1450 if ((A.sgt(0) && B.sgt(0)) ||
1451 (A.slt(0) && B.slt(0)))
1452 return Q + 1;
1453 else
1454 return Q;
1455}
1456
1457
1458static
1459APInt maxAPInt(APInt A, APInt B) {
1460 return A.sgt(B) ? A : B;
1461}
1462
1463
1464static
1465APInt minAPInt(APInt A, APInt B) {
1466 return A.slt(B) ? A : B;
1467}
1468
1469
1470// exactSIVtest -
1471// When we have a pair of subscripts of the form [c1 + a1*i] and [c2 + a2*i],
1472// where i is an induction variable, c1 and c2 are loop invariant, and a1
1473// and a2 are constant, we can solve it exactly using an algorithm developed
1474// by Banerjee and Wolfe. See Section 2.5.3 in
1475//
1476// Optimizing Supercompilers for Supercomputers
1477// Michael Wolfe
1478// MIT Press, 1989
1479//
1480// It's slower than the specialized tests (strong SIV, weak-zero SIV, etc),
1481// so use them if possible. They're also a bit better with symbolics and,
1482// in the case of the strong SIV test, can compute Distances.
1483//
1484// Return true if dependence disproved.
1485bool DependenceInfo::exactSIVtest(const SCEV *SrcCoeff, const SCEV *DstCoeff,
1486 const SCEV *SrcConst, const SCEV *DstConst,
1487 const Loop *CurLoop, unsigned Level,
1488 FullDependence &Result,
1489 Constraint &NewConstraint) const {
1490 LLVM_DEBUG(dbgs() << "\tExact SIV test\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\tExact SIV test\n"; } } while (false
)
;
1491 LLVM_DEBUG(dbgs() << "\t SrcCoeff = " << *SrcCoeff << " = AM\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\t SrcCoeff = " << *SrcCoeff
<< " = AM\n"; } } while (false)
;
1492 LLVM_DEBUG(dbgs() << "\t DstCoeff = " << *DstCoeff << " = BM\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\t DstCoeff = " << *DstCoeff
<< " = BM\n"; } } while (false)
;
1493 LLVM_DEBUG(dbgs() << "\t SrcConst = " << *SrcConst << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\t SrcConst = " << *SrcConst
<< "\n"; } } while (false)
;
1494 LLVM_DEBUG(dbgs() << "\t DstConst = " << *DstConst << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\t DstConst = " << *DstConst
<< "\n"; } } while (false)
;
1495 ++ExactSIVapplications;
1496 assert(0 < Level && Level <= CommonLevels && "Level out of range")((0 < Level && Level <= CommonLevels &&
"Level out of range") ? static_cast<void> (0) : __assert_fail
("0 < Level && Level <= CommonLevels && \"Level out of range\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/Analysis/DependenceAnalysis.cpp"
, 1496, __PRETTY_FUNCTION__))
;
1497 Level--;
1498 Result.Consistent = false;
1499 const SCEV *Delta = SE->getMinusSCEV(DstConst, SrcConst);
1500 LLVM_DEBUG(dbgs() << "\t Delta = " << *Delta << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\t Delta = " << *Delta <<
"\n"; } } while (false)
;
1501 NewConstraint.setLine(SrcCoeff, SE->getNegativeSCEV(DstCoeff),
1502 Delta, CurLoop);
1503 const SCEVConstant *ConstDelta = dyn_cast<SCEVConstant>(Delta);
1504 const SCEVConstant *ConstSrcCoeff = dyn_cast<SCEVConstant>(SrcCoeff);
1505 const SCEVConstant *ConstDstCoeff = dyn_cast<SCEVConstant>(DstCoeff);
1506 if (!ConstDelta || !ConstSrcCoeff || !ConstDstCoeff)
1507 return false;
1508
1509 // find gcd
1510 APInt G, X, Y;
1511 APInt AM = ConstSrcCoeff->getAPInt();
1512 APInt BM = ConstDstCoeff->getAPInt();
1513 unsigned Bits = AM.getBitWidth();
1514 if (findGCD(Bits, AM, BM, ConstDelta->getAPInt(), G, X, Y)) {
1515 // gcd doesn't divide Delta, no dependence
1516 ++ExactSIVindependence;
1517 ++ExactSIVsuccesses;
1518 return true;
1519 }
1520
1521 LLVM_DEBUG(dbgs() << "\t X = " << X << ", Y = " << Y << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\t X = " << X << ", Y = "
<< Y << "\n"; } } while (false)
;
1522
1523 // since SCEV construction normalizes, LM = 0
1524 APInt UM(Bits, 1, true);
1525 bool UMvalid = false;
1526 // UM is perhaps unavailable, let's check
1527 if (const SCEVConstant *CUB =
1528 collectConstantUpperBound(CurLoop, Delta->getType())) {
1529 UM = CUB->getAPInt();
1530 LLVM_DEBUG(dbgs() << "\t UM = " << UM << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\t UM = " << UM << "\n"
; } } while (false)
;
1531 UMvalid = true;
1532 }
1533
1534 APInt TU(APInt::getSignedMaxValue(Bits));
1535 APInt TL(APInt::getSignedMinValue(Bits));
1536
1537 // test(BM/G, LM-X) and test(-BM/G, X-UM)
1538 APInt TMUL = BM.sdiv(G);
1539 if (TMUL.sgt(0)) {
1540 TL = maxAPInt(TL, ceilingOfQuotient(-X, TMUL));
1541 LLVM_DEBUG(dbgs() << "\t TL = " << TL << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\t TL = " << TL << "\n"
; } } while (false)
;
1542 if (UMvalid) {
1543 TU = minAPInt(TU, floorOfQuotient(UM - X, TMUL));
1544 LLVM_DEBUG(dbgs() << "\t TU = " << TU << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\t TU = " << TU << "\n"
; } } while (false)
;
1545 }
1546 }
1547 else {
1548 TU = minAPInt(TU, floorOfQuotient(-X, TMUL));
1549 LLVM_DEBUG(dbgs() << "\t TU = " << TU << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\t TU = " << TU << "\n"
; } } while (false)
;
1550 if (UMvalid) {
1551 TL = maxAPInt(TL, ceilingOfQuotient(UM - X, TMUL));
1552 LLVM_DEBUG(dbgs() << "\t TL = " << TL << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\t TL = " << TL << "\n"
; } } while (false)
;
1553 }
1554 }
1555
1556 // test(AM/G, LM-Y) and test(-AM/G, Y-UM)
1557 TMUL = AM.sdiv(G);
1558 if (TMUL.sgt(0)) {
1559 TL = maxAPInt(TL, ceilingOfQuotient(-Y, TMUL));
1560 LLVM_DEBUG(dbgs() << "\t TL = " << TL << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\t TL = " << TL << "\n"
; } } while (false)
;
1561 if (UMvalid) {
1562 TU = minAPInt(TU, floorOfQuotient(UM - Y, TMUL));
1563 LLVM_DEBUG(dbgs() << "\t TU = " << TU << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\t TU = " << TU << "\n"
; } } while (false)
;
1564 }
1565 }
1566 else {
1567 TU = minAPInt(TU, floorOfQuotient(-Y, TMUL));
1568 LLVM_DEBUG(dbgs() << "\t TU = " << TU << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\t TU = " << TU << "\n"
; } } while (false)
;
1569 if (UMvalid) {
1570 TL = maxAPInt(TL, ceilingOfQuotient(UM - Y, TMUL));
1571 LLVM_DEBUG(dbgs() << "\t TL = " << TL << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\t TL = " << TL << "\n"
; } } while (false)
;
1572 }
1573 }
1574 if (TL.sgt(TU)) {
1575 ++ExactSIVindependence;
1576 ++ExactSIVsuccesses;
1577 return true;
1578 }
1579
1580 // explore directions
1581 unsigned NewDirection = Dependence::DVEntry::NONE;
1582
1583 // less than
1584 APInt SaveTU(TU); // save these
1585 APInt SaveTL(TL);
1586 LLVM_DEBUG(dbgs() << "\t exploring LT direction\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\t exploring LT direction\n"; }
} while (false)
;
1587 TMUL = AM - BM;
1588 if (TMUL.sgt(0)) {
1589 TL = maxAPInt(TL, ceilingOfQuotient(X - Y + 1, TMUL));
1590 LLVM_DEBUG(dbgs() << "\t\t TL = " << TL << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\t\t TL = " << TL <<
"\n"; } } while (false)
;
1591 }
1592 else {
1593 TU = minAPInt(TU, floorOfQuotient(X - Y + 1, TMUL));
1594 LLVM_DEBUG(dbgs() << "\t\t TU = " << TU << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\t\t TU = " << TU <<
"\n"; } } while (false)
;
1595 }
1596 if (TL.sle(TU)) {
1597 NewDirection |= Dependence::DVEntry::LT;
1598 ++ExactSIVsuccesses;
1599 }
1600
1601 // equal
1602 TU = SaveTU; // restore
1603 TL = SaveTL;
1604 LLVM_DEBUG(dbgs() << "\t exploring EQ direction\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\t exploring EQ direction\n"; }
} while (false)
;
1605 if (TMUL.sgt(0)) {
1606 TL = maxAPInt(TL, ceilingOfQuotient(X - Y, TMUL));
1607 LLVM_DEBUG(dbgs() << "\t\t TL = " << TL << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\t\t TL = " << TL <<
"\n"; } } while (false)
;
1608 }
1609 else {
1610 TU = minAPInt(TU, floorOfQuotient(X - Y, TMUL));
1611 LLVM_DEBUG(dbgs() << "\t\t TU = " << TU << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\t\t TU = " << TU <<
"\n"; } } while (false)
;
1612 }
1613 TMUL = BM - AM;
1614 if (TMUL.sgt(0)) {
1615 TL = maxAPInt(TL, ceilingOfQuotient(Y - X, TMUL));
1616 LLVM_DEBUG(dbgs() << "\t\t TL = " << TL << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\t\t TL = " << TL <<
"\n"; } } while (false)
;
1617 }
1618 else {
1619 TU = minAPInt(TU, floorOfQuotient(Y - X, TMUL));
1620 LLVM_DEBUG(dbgs() << "\t\t TU = " << TU << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\t\t TU = " << TU <<
"\n"; } } while (false)
;
1621 }
1622 if (TL.sle(TU)) {
1623 NewDirection |= Dependence::DVEntry::EQ;
1624 ++ExactSIVsuccesses;
1625 }
1626
1627 // greater than
1628 TU = SaveTU; // restore
1629 TL = SaveTL;
1630 LLVM_DEBUG(dbgs() << "\t exploring GT direction\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\t exploring GT direction\n"; }
} while (false)
;
1631 if (TMUL.sgt(0)) {
1632 TL = maxAPInt(TL, ceilingOfQuotient(Y - X + 1, TMUL));
1633 LLVM_DEBUG(dbgs() << "\t\t TL = " << TL << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\t\t TL = " << TL <<
"\n"; } } while (false)
;
1634 }
1635 else {
1636 TU = minAPInt(TU, floorOfQuotient(Y - X + 1, TMUL));
1637 LLVM_DEBUG(dbgs() << "\t\t TU = " << TU << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\t\t TU = " << TU <<
"\n"; } } while (false)
;
1638 }
1639 if (TL.sle(TU)) {
1640 NewDirection |= Dependence::DVEntry::GT;
1641 ++ExactSIVsuccesses;
1642 }
1643
1644 // finished
1645 Result.DV[Level].Direction &= NewDirection;
1646 if (Result.DV[Level].Direction == Dependence::DVEntry::NONE)
1647 ++ExactSIVindependence;
1648 return Result.DV[Level].Direction == Dependence::DVEntry::NONE;
1649}
1650
1651
1652
1653// Return true if the divisor evenly divides the dividend.
1654static
1655bool isRemainderZero(const SCEVConstant *Dividend,
1656 const SCEVConstant *Divisor) {
1657 const APInt &ConstDividend = Dividend->getAPInt();
1658 const APInt &ConstDivisor = Divisor->getAPInt();
1659 return ConstDividend.srem(ConstDivisor) == 0;
1660}
1661
1662
1663// weakZeroSrcSIVtest -
1664// From the paper, Practical Dependence Testing, Section 4.2.2
1665//
1666// When we have a pair of subscripts of the form [c1] and [c2 + a*i],
1667// where i is an induction variable, c1 and c2 are loop invariant,
1668// and a is a constant, we can solve it exactly using the
1669// Weak-Zero SIV test.
1670//
1671// Given
1672//
1673// c1 = c2 + a*i
1674//
1675// we get
1676//
1677// (c1 - c2)/a = i
1678//
1679// If i is not an integer, there's no dependence.
1680// If i < 0 or > UB, there's no dependence.
1681// If i = 0, the direction is >= and peeling the
1682// 1st iteration will break the dependence.
1683// If i = UB, the direction is <= and peeling the
1684// last iteration will break the dependence.
1685// Otherwise, the direction is *.
1686//
1687// Can prove independence. Failing that, we can sometimes refine
1688// the directions. Can sometimes show that first or last
1689// iteration carries all the dependences (so worth peeling).
1690//
1691// (see also weakZeroDstSIVtest)
1692//
1693// Return true if dependence disproved.
1694bool DependenceInfo::weakZeroSrcSIVtest(const SCEV *DstCoeff,
1695 const SCEV *SrcConst,
1696 const SCEV *DstConst,
1697 const Loop *CurLoop, unsigned Level,
1698 FullDependence &Result,
1699 Constraint &NewConstraint) const {
1700 // For the WeakSIV test, it's possible the loop isn't common to
1701 // the Src and Dst loops. If it isn't, then there's no need to
1702 // record a direction.
1703 LLVM_DEBUG(dbgs() << "\tWeak-Zero (src) SIV test\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\tWeak-Zero (src) SIV test\n"; } }
while (false)
;
1704 LLVM_DEBUG(dbgs() << "\t DstCoeff = " << *DstCoeff << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\t DstCoeff = " << *DstCoeff
<< "\n"; } } while (false)
;
1705 LLVM_DEBUG(dbgs() << "\t SrcConst = " << *SrcConst << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\t SrcConst = " << *SrcConst
<< "\n"; } } while (false)
;
1706 LLVM_DEBUG(dbgs() << "\t DstConst = " << *DstConst << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\t DstConst = " << *DstConst
<< "\n"; } } while (false)
;
1707 ++WeakZeroSIVapplications;
1708 assert(0 < Level && Level <= MaxLevels && "Level out of range")((0 < Level && Level <= MaxLevels && "Level out of range"
) ? static_cast<void> (0) : __assert_fail ("0 < Level && Level <= MaxLevels && \"Level out of range\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/Analysis/DependenceAnalysis.cpp"
, 1708, __PRETTY_FUNCTION__))
;
1709 Level--;
1710 Result.Consistent = false;
1711 const SCEV *Delta = SE->getMinusSCEV(SrcConst, DstConst);
1712 NewConstraint.setLine(SE->getZero(Delta->getType()), DstCoeff, Delta,
1713 CurLoop);
1714 LLVM_DEBUG(dbgs() << "\t Delta = " << *Delta << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\t Delta = " << *Delta <<
"\n"; } } while (false)
;
1715 if (isKnownPredicate(CmpInst::ICMP_EQ, SrcConst, DstConst)) {
1716 if (Level < CommonLevels) {
1717 Result.DV[Level].Direction &= Dependence::DVEntry::GE;
1718 Result.DV[Level].PeelFirst = true;
1719 ++WeakZeroSIVsuccesses;
1720 }
1721 return false; // dependences caused by first iteration
1722 }
1723 const SCEVConstant *ConstCoeff = dyn_cast<SCEVConstant>(DstCoeff);
1724 if (!ConstCoeff)
1725 return false;
1726 const SCEV *AbsCoeff =
1727 SE->isKnownNegative(ConstCoeff) ?
1728 SE->getNegativeSCEV(ConstCoeff) : ConstCoeff;
1729 const SCEV *NewDelta =
1730 SE->isKnownNegative(ConstCoeff) ? SE->getNegativeSCEV(Delta) : Delta;
1731
1732 // check that Delta/SrcCoeff < iteration count
1733 // really check NewDelta < count*AbsCoeff
1734 if (const SCEV *UpperBound = collectUpperBound(CurLoop, Delta->getType())) {
1735 LLVM_DEBUG(dbgs() << "\t UpperBound = " << *UpperBound << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\t UpperBound = " << *UpperBound
<< "\n"; } } while (false)
;
1736 const SCEV *Product = SE->getMulExpr(AbsCoeff, UpperBound);
1737 if (isKnownPredicate(CmpInst::ICMP_SGT, NewDelta, Product)) {
1738 ++WeakZeroSIVindependence;
1739 ++WeakZeroSIVsuccesses;
1740 return true;
1741 }
1742 if (isKnownPredicate(CmpInst::ICMP_EQ, NewDelta, Product)) {
1743 // dependences caused by last iteration
1744 if (Level < CommonLevels) {
1745 Result.DV[Level].Direction &= Dependence::DVEntry::LE;
1746 Result.DV[Level].PeelLast = true;
1747 ++WeakZeroSIVsuccesses;
1748 }
1749 return false;
1750 }
1751 }
1752
1753 // check that Delta/SrcCoeff >= 0
1754 // really check that NewDelta >= 0
1755 if (SE->isKnownNegative(NewDelta)) {
1756 // No dependence, newDelta < 0
1757 ++WeakZeroSIVindependence;
1758 ++WeakZeroSIVsuccesses;
1759 return true;
1760 }
1761
1762 // if SrcCoeff doesn't divide Delta, then no dependence
1763 if (isa<SCEVConstant>(Delta) &&
1764 !isRemainderZero(cast<SCEVConstant>(Delta), ConstCoeff)) {
1765 ++WeakZeroSIVindependence;
1766 ++WeakZeroSIVsuccesses;
1767 return true;
1768 }
1769 return false;
1770}
1771
1772
1773// weakZeroDstSIVtest -
1774// From the paper, Practical Dependence Testing, Section 4.2.2
1775//
1776// When we have a pair of subscripts of the form [c1 + a*i] and [c2],
1777// where i is an induction variable, c1 and c2 are loop invariant,
1778// and a is a constant, we can solve it exactly using the
1779// Weak-Zero SIV test.
1780//
1781// Given
1782//
1783// c1 + a*i = c2
1784//
1785// we get
1786//
1787// i = (c2 - c1)/a
1788//
1789// If i is not an integer, there's no dependence.
1790// If i < 0 or > UB, there's no dependence.
1791// If i = 0, the direction is <= and peeling the
1792// 1st iteration will break the dependence.
1793// If i = UB, the direction is >= and peeling the
1794// last iteration will break the dependence.
1795// Otherwise, the direction is *.
1796//
1797// Can prove independence. Failing that, we can sometimes refine
1798// the directions. Can sometimes show that first or last
1799// iteration carries all the dependences (so worth peeling).
1800//
1801// (see also weakZeroSrcSIVtest)
1802//
1803// Return true if dependence disproved.
1804bool DependenceInfo::weakZeroDstSIVtest(const SCEV *SrcCoeff,
1805 const SCEV *SrcConst,
1806 const SCEV *DstConst,
1807 const Loop *CurLoop, unsigned Level,
1808 FullDependence &Result,
1809 Constraint &NewConstraint) const {
1810 // For the WeakSIV test, it's possible the loop isn't common to the
1811 // Src and Dst loops. If it isn't, then there's no need to record a direction.
1812 LLVM_DEBUG(dbgs() << "\tWeak-Zero (dst) SIV test\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\tWeak-Zero (dst) SIV test\n"; } }
while (false)
;
1813 LLVM_DEBUG(dbgs() << "\t SrcCoeff = " << *SrcCoeff << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\t SrcCoeff = " << *SrcCoeff
<< "\n"; } } while (false)
;
1814 LLVM_DEBUG(dbgs() << "\t SrcConst = " << *SrcConst << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\t SrcConst = " << *SrcConst
<< "\n"; } } while (false)
;
1815 LLVM_DEBUG(dbgs() << "\t DstConst = " << *DstConst << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\t DstConst = " << *DstConst
<< "\n"; } } while (false)
;
1816 ++WeakZeroSIVapplications;
1817 assert(0 < Level && Level <= SrcLevels && "Level out of range")((0 < Level && Level <= SrcLevels && "Level out of range"
) ? static_cast<void> (0) : __assert_fail ("0 < Level && Level <= SrcLevels && \"Level out of range\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/Analysis/DependenceAnalysis.cpp"
, 1817, __PRETTY_FUNCTION__))
;
1818 Level--;
1819 Result.Consistent = false;
1820 const SCEV *Delta = SE->getMinusSCEV(DstConst, SrcConst);
1821 NewConstraint.setLine(SrcCoeff, SE->getZero(Delta->getType()), Delta,
1822 CurLoop);
1823 LLVM_DEBUG(dbgs() << "\t Delta = " << *Delta << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\t Delta = " << *Delta <<
"\n"; } } while (false)
;
1824 if (isKnownPredicate(CmpInst::ICMP_EQ, DstConst, SrcConst)) {
1825 if (Level < CommonLevels) {
1826 Result.DV[Level].Direction &= Dependence::DVEntry::LE;
1827 Result.DV[Level].PeelFirst = true;
1828 ++WeakZeroSIVsuccesses;
1829 }
1830 return false; // dependences caused by first iteration
1831 }
1832 const SCEVConstant *ConstCoeff = dyn_cast<SCEVConstant>(SrcCoeff);
1833 if (!ConstCoeff)
1834 return false;
1835 const SCEV *AbsCoeff =
1836 SE->isKnownNegative(ConstCoeff) ?
1837 SE->getNegativeSCEV(ConstCoeff) : ConstCoeff;
1838 const SCEV *NewDelta =
1839 SE->isKnownNegative(ConstCoeff) ? SE->getNegativeSCEV(Delta) : Delta;
1840
1841 // check that Delta/SrcCoeff < iteration count
1842 // really check NewDelta < count*AbsCoeff
1843 if (const SCEV *UpperBound = collectUpperBound(CurLoop, Delta->getType())) {
1844 LLVM_DEBUG(dbgs() << "\t UpperBound = " << *UpperBound << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\t UpperBound = " << *UpperBound
<< "\n"; } } while (false)
;
1845 const SCEV *Product = SE->getMulExpr(AbsCoeff, UpperBound);
1846 if (isKnownPredicate(CmpInst::ICMP_SGT, NewDelta, Product)) {
1847 ++WeakZeroSIVindependence;
1848 ++WeakZeroSIVsuccesses;
1849 return true;
1850 }
1851 if (isKnownPredicate(CmpInst::ICMP_EQ, NewDelta, Product)) {
1852 // dependences caused by last iteration
1853 if (Level < CommonLevels) {
1854 Result.DV[Level].Direction &= Dependence::DVEntry::GE;
1855 Result.DV[Level].PeelLast = true;
1856 ++WeakZeroSIVsuccesses;
1857 }
1858 return false;
1859 }
1860 }
1861
1862 // check that Delta/SrcCoeff >= 0
1863 // really check that NewDelta >= 0
1864 if (SE->isKnownNegative(NewDelta)) {
1865 // No dependence, newDelta < 0
1866 ++WeakZeroSIVindependence;
1867 ++WeakZeroSIVsuccesses;
1868 return true;
1869 }
1870
1871 // if SrcCoeff doesn't divide Delta, then no dependence
1872 if (isa<SCEVConstant>(Delta) &&
1873 !isRemainderZero(cast<SCEVConstant>(Delta), ConstCoeff)) {
1874 ++WeakZeroSIVindependence;
1875 ++WeakZeroSIVsuccesses;
1876 return true;
1877 }
1878 return false;
1879}
1880
1881
1882// exactRDIVtest - Tests the RDIV subscript pair for dependence.
1883// Things of the form [c1 + a*i] and [c2 + b*j],
1884// where i and j are induction variable, c1 and c2 are loop invariant,
1885// and a and b are constants.
1886// Returns true if any possible dependence is disproved.
1887// Marks the result as inconsistent.
1888// Works in some cases that symbolicRDIVtest doesn't, and vice versa.
1889bool DependenceInfo::exactRDIVtest(const SCEV *SrcCoeff, const SCEV *DstCoeff,
1890 const SCEV *SrcConst, const SCEV *DstConst,
1891 const Loop *SrcLoop, const Loop *DstLoop,
1892 FullDependence &Result) const {
1893 LLVM_DEBUG(dbgs() << "\tExact RDIV test\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\tExact RDIV test\n"; } } while (false
)
;
1894 LLVM_DEBUG(dbgs() << "\t SrcCoeff = " << *SrcCoeff << " = AM\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\t SrcCoeff = " << *SrcCoeff
<< " = AM\n"; } } while (false)
;
1895 LLVM_DEBUG(dbgs() << "\t DstCoeff = " << *DstCoeff << " = BM\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\t DstCoeff = " << *DstCoeff
<< " = BM\n"; } } while (false)
;
1896 LLVM_DEBUG(dbgs() << "\t SrcConst = " << *SrcConst << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\t SrcConst = " << *SrcConst
<< "\n"; } } while (false)
;
1897 LLVM_DEBUG(dbgs() << "\t DstConst = " << *DstConst << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\t DstConst = " << *DstConst
<< "\n"; } } while (false)
;
1898 ++ExactRDIVapplications;
1899 Result.Consistent = false;
1900 const SCEV *Delta = SE->getMinusSCEV(DstConst, SrcConst);
1901 LLVM_DEBUG(dbgs() << "\t Delta = " << *Delta << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\t Delta = " << *Delta <<
"\n"; } } while (false)
;
1902 const SCEVConstant *ConstDelta = dyn_cast<SCEVConstant>(Delta);
1903 const SCEVConstant *ConstSrcCoeff = dyn_cast<SCEVConstant>(SrcCoeff);
1904 const SCEVConstant *ConstDstCoeff = dyn_cast<SCEVConstant>(DstCoeff);
1905 if (!ConstDelta || !ConstSrcCoeff || !ConstDstCoeff)
1906 return false;
1907
1908 // find gcd
1909 APInt G, X, Y;
1910 APInt AM = ConstSrcCoeff->getAPInt();
1911 APInt BM = ConstDstCoeff->getAPInt();
1912 unsigned Bits = AM.getBitWidth();
1913 if (findGCD(Bits, AM, BM, ConstDelta->getAPInt(), G, X, Y)) {
1914 // gcd doesn't divide Delta, no dependence
1915 ++ExactRDIVindependence;
1916 return true;
1917 }
1918
1919 LLVM_DEBUG(dbgs() << "\t X = " << X << ", Y = " << Y << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\t X = " << X << ", Y = "
<< Y << "\n"; } } while (false)
;
1920
1921 // since SCEV construction seems to normalize, LM = 0
1922 APInt SrcUM(Bits, 1, true);
1923 bool SrcUMvalid = false;
1924 // SrcUM is perhaps unavailable, let's check
1925 if (const SCEVConstant *UpperBound =
1926 collectConstantUpperBound(SrcLoop, Delta->getType())) {
1927 SrcUM = UpperBound->getAPInt();
1928 LLVM_DEBUG(dbgs() << "\t SrcUM = " << SrcUM << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\t SrcUM = " << SrcUM <<
"\n"; } } while (false)
;
1929 SrcUMvalid = true;
1930 }
1931
1932 APInt DstUM(Bits, 1, true);
1933 bool DstUMvalid = false;
1934 // UM is perhaps unavailable, let's check
1935 if (const SCEVConstant *UpperBound =
1936 collectConstantUpperBound(DstLoop, Delta->getType())) {
1937 DstUM = UpperBound->getAPInt();
1938 LLVM_DEBUG(dbgs() << "\t DstUM = " << DstUM << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\t DstUM = " << DstUM <<
"\n"; } } while (false)
;
1939 DstUMvalid = true;
1940 }
1941
1942 APInt TU(APInt::getSignedMaxValue(Bits));
1943 APInt TL(APInt::getSignedMinValue(Bits));
1944
1945 // test(BM/G, LM-X) and test(-BM/G, X-UM)
1946 APInt TMUL = BM.sdiv(G);
1947 if (TMUL.sgt(0)) {
1948 TL = maxAPInt(TL, ceilingOfQuotient(-X, TMUL));
1949 LLVM_DEBUG(dbgs() << "\t TL = " << TL << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\t TL = " << TL << "\n"
; } } while (false)
;
1950 if (SrcUMvalid) {
1951 TU = minAPInt(TU, floorOfQuotient(SrcUM - X, TMUL));
1952 LLVM_DEBUG(dbgs() << "\t TU = " << TU << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\t TU = " << TU << "\n"
; } } while (false)
;
1953 }
1954 }
1955 else {
1956 TU = minAPInt(TU, floorOfQuotient(-X, TMUL));
1957 LLVM_DEBUG(dbgs() << "\t TU = " << TU << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\t TU = " << TU << "\n"
; } } while (false)
;
1958 if (SrcUMvalid) {
1959 TL = maxAPInt(TL, ceilingOfQuotient(SrcUM - X, TMUL));
1960 LLVM_DEBUG(dbgs() << "\t TL = " << TL << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\t TL = " << TL << "\n"
; } } while (false)
;
1961 }
1962 }
1963
1964 // test(AM/G, LM-Y) and test(-AM/G, Y-UM)
1965 TMUL = AM.sdiv(G);
1966 if (TMUL.sgt(0)) {
1967 TL = maxAPInt(TL, ceilingOfQuotient(-Y, TMUL));
1968 LLVM_DEBUG(dbgs() << "\t TL = " << TL << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\t TL = " << TL << "\n"
; } } while (false)
;
1969 if (DstUMvalid) {
1970 TU = minAPInt(TU, floorOfQuotient(DstUM - Y, TMUL));
1971 LLVM_DEBUG(dbgs() << "\t TU = " << TU << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\t TU = " << TU << "\n"
; } } while (false)
;
1972 }
1973 }
1974 else {
1975 TU = minAPInt(TU, floorOfQuotient(-Y, TMUL));
1976 LLVM_DEBUG(dbgs() << "\t TU = " << TU << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\t TU = " << TU << "\n"
; } } while (false)
;
1977 if (DstUMvalid) {
1978 TL = maxAPInt(TL, ceilingOfQuotient(DstUM - Y, TMUL));
1979 LLVM_DEBUG(dbgs() << "\t TL = " << TL << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\t TL = " << TL << "\n"
; } } while (false)
;
1980 }
1981 }
1982 if (TL.sgt(TU))
1983 ++ExactRDIVindependence;
1984 return TL.sgt(TU);
1985}
1986
1987
1988// symbolicRDIVtest -
1989// In Section 4.5 of the Practical Dependence Testing paper,the authors
1990// introduce a special case of Banerjee's Inequalities (also called the
1991// Extreme-Value Test) that can handle some of the SIV and RDIV cases,
1992// particularly cases with symbolics. Since it's only able to disprove
1993// dependence (not compute distances or directions), we'll use it as a
1994// fall back for the other tests.
1995//
1996// When we have a pair of subscripts of the form [c1 + a1*i] and [c2 + a2*j]
1997// where i and j are induction variables and c1 and c2 are loop invariants,
1998// we can use the symbolic tests to disprove some dependences, serving as a
1999// backup for the RDIV test. Note that i and j can be the same variable,
2000// letting this test serve as a backup for the various SIV tests.
2001//
2002// For a dependence to exist, c1 + a1*i must equal c2 + a2*j for some
2003// 0 <= i <= N1 and some 0 <= j <= N2, where N1 and N2 are the (normalized)
2004// loop bounds for the i and j loops, respectively. So, ...
2005//
2006// c1 + a1*i = c2 + a2*j
2007// a1*i - a2*j = c2 - c1
2008//
2009// To test for a dependence, we compute c2 - c1 and make sure it's in the
2010// range of the maximum and minimum possible values of a1*i - a2*j.
2011// Considering the signs of a1 and a2, we have 4 possible cases:
2012//
2013// 1) If a1 >= 0 and a2 >= 0, then
2014// a1*0 - a2*N2 <= c2 - c1 <= a1*N1 - a2*0
2015// -a2*N2 <= c2 - c1 <= a1*N1
2016//
2017// 2) If a1 >= 0 and a2 <= 0, then
2018// a1*0 - a2*0 <= c2 - c1 <= a1*N1 - a2*N2
2019// 0 <= c2 - c1 <= a1*N1 - a2*N2
2020//
2021// 3) If a1 <= 0 and a2 >= 0, then
2022// a1*N1 - a2*N2 <= c2 - c1 <= a1*0 - a2*0
2023// a1*N1 - a2*N2 <= c2 - c1 <= 0
2024//
2025// 4) If a1 <= 0 and a2 <= 0, then
2026// a1*N1 - a2*0 <= c2 - c1 <= a1*0 - a2*N2
2027// a1*N1 <= c2 - c1 <= -a2*N2
2028//
2029// return true if dependence disproved
2030bool DependenceInfo::symbolicRDIVtest(const SCEV *A1, const SCEV *A2,
2031 const SCEV *C1, const SCEV *C2,
2032 const Loop *Loop1,
2033 const Loop *Loop2) const {
2034 ++SymbolicRDIVapplications;
2035 LLVM_DEBUG(dbgs() << "\ttry symbolic RDIV test\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\ttry symbolic RDIV test\n"; } } while
(false)
;
2036 LLVM_DEBUG(dbgs() << "\t A1 = " << *A1)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\t A1 = " << *A1; } } while
(false)
;
2037 LLVM_DEBUG(dbgs() << ", type = " << *A1->getType() << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << ", type = " << *A1->getType
() << "\n"; } } while (false)
;
2038 LLVM_DEBUG(dbgs() << "\t A2 = " << *A2 << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\t A2 = " << *A2 <<
"\n"; } } while (false)
;
2039 LLVM_DEBUG(dbgs() << "\t C1 = " << *C1 << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\t C1 = " << *C1 <<
"\n"; } } while (false)
;
2040 LLVM_DEBUG(dbgs() << "\t C2 = " << *C2 << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\t C2 = " << *C2 <<
"\n"; } } while (false)
;
2041 const SCEV *N1 = collectUpperBound(Loop1, A1->getType());
2042 const SCEV *N2 = collectUpperBound(Loop2, A1->getType());
2043 LLVM_DEBUG(if (N1) dbgs() << "\t N1 = " << *N1 << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { if (N1) dbgs() << "\t N1 = " << *N1 <<
"\n"; } } while (false)
;
2044 LLVM_DEBUG(if (N2) dbgs() << "\t N2 = " << *N2 << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { if (N2) dbgs() << "\t N2 = " << *N2 <<
"\n"; } } while (false)
;
2045 const SCEV *C2_C1 = SE->getMinusSCEV(C2, C1);
2046 const SCEV *C1_C2 = SE->getMinusSCEV(C1, C2);
2047 LLVM_DEBUG(dbgs() << "\t C2 - C1 = " << *C2_C1 << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\t C2 - C1 = " << *C2_C1 <<
"\n"; } } while (false)
;
2048 LLVM_DEBUG(dbgs() << "\t C1 - C2 = " << *C1_C2 << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\t C1 - C2 = " << *C1_C2 <<
"\n"; } } while (false)
;
2049 if (SE->isKnownNonNegative(A1)) {
2050 if (SE->isKnownNonNegative(A2)) {
2051 // A1 >= 0 && A2 >= 0
2052 if (N1) {
2053 // make sure that c2 - c1 <= a1*N1
2054 const SCEV *A1N1 = SE->getMulExpr(A1, N1);
2055 LLVM_DEBUG(dbgs() << "\t A1*N1 = " << *A1N1 << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\t A1*N1 = " << *A1N1 <<
"\n"; } } while (false)
;
2056 if (isKnownPredicate(CmpInst::ICMP_SGT, C2_C1, A1N1)) {
2057 ++SymbolicRDIVindependence;
2058 return true;
2059 }
2060 }
2061 if (N2) {
2062 // make sure that -a2*N2 <= c2 - c1, or a2*N2 >= c1 - c2
2063 const SCEV *A2N2 = SE->getMulExpr(A2, N2);
2064 LLVM_DEBUG(dbgs() << "\t A2*N2 = " << *A2N2 << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\t A2*N2 = " << *A2N2 <<
"\n"; } } while (false)
;
2065 if (isKnownPredicate(CmpInst::ICMP_SLT, A2N2, C1_C2)) {
2066 ++SymbolicRDIVindependence;
2067 return true;
2068 }
2069 }
2070 }
2071 else if (SE->isKnownNonPositive(A2)) {
2072 // a1 >= 0 && a2 <= 0
2073 if (N1 && N2) {
2074 // make sure that c2 - c1 <= a1*N1 - a2*N2
2075 const SCEV *A1N1 = SE->getMulExpr(A1, N1);
2076 const SCEV *A2N2 = SE->getMulExpr(A2, N2);
2077 const SCEV *A1N1_A2N2 = SE->getMinusSCEV(A1N1, A2N2);
2078 LLVM_DEBUG(dbgs() << "\t A1*N1 - A2*N2 = " << *A1N1_A2N2 << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\t A1*N1 - A2*N2 = " << *
A1N1_A2N2 << "\n"; } } while (false)
;
2079 if (isKnownPredicate(CmpInst::ICMP_SGT, C2_C1, A1N1_A2N2)) {
2080 ++SymbolicRDIVindependence;
2081 return true;
2082 }
2083 }
2084 // make sure that 0 <= c2 - c1
2085 if (SE->isKnownNegative(C2_C1)) {
2086 ++SymbolicRDIVindependence;
2087 return true;
2088 }
2089 }
2090 }
2091 else if (SE->isKnownNonPositive(A1)) {
2092 if (SE->isKnownNonNegative(A2)) {
2093 // a1 <= 0 && a2 >= 0
2094 if (N1 && N2) {
2095 // make sure that a1*N1 - a2*N2 <= c2 - c1
2096 const SCEV *A1N1 = SE->getMulExpr(A1, N1);
2097 const SCEV *A2N2 = SE->getMulExpr(A2, N2);
2098 const SCEV *A1N1_A2N2 = SE->getMinusSCEV(A1N1, A2N2);
2099 LLVM_DEBUG(dbgs() << "\t A1*N1 - A2*N2 = " << *A1N1_A2N2 << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\t A1*N1 - A2*N2 = " << *
A1N1_A2N2 << "\n"; } } while (false)
;
2100 if (isKnownPredicate(CmpInst::ICMP_SGT, A1N1_A2N2, C2_C1)) {
2101 ++SymbolicRDIVindependence;
2102 return true;
2103 }
2104 }
2105 // make sure that c2 - c1 <= 0
2106 if (SE->isKnownPositive(C2_C1)) {
2107 ++SymbolicRDIVindependence;
2108 return true;
2109 }
2110 }
2111 else if (SE->isKnownNonPositive(A2)) {
2112 // a1 <= 0 && a2 <= 0
2113 if (N1) {
2114 // make sure that a1*N1 <= c2 - c1
2115 const SCEV *A1N1 = SE->getMulExpr(A1, N1);
2116 LLVM_DEBUG(dbgs() << "\t A1*N1 = " << *A1N1 << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\t A1*N1 = " << *A1N1 <<
"\n"; } } while (false)
;
2117 if (isKnownPredicate(CmpInst::ICMP_SGT, A1N1, C2_C1)) {
2118 ++SymbolicRDIVindependence;
2119 return true;
2120 }
2121 }
2122 if (N2) {
2123 // make sure that c2 - c1 <= -a2*N2, or c1 - c2 >= a2*N2
2124 const SCEV *A2N2 = SE->getMulExpr(A2, N2);
2125 LLVM_DEBUG(dbgs() << "\t A2*N2 = " << *A2N2 << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\t A2*N2 = " << *A2N2 <<
"\n"; } } while (false)
;
2126 if (isKnownPredicate(CmpInst::ICMP_SLT, C1_C2, A2N2)) {
2127 ++SymbolicRDIVindependence;
2128 return true;
2129 }
2130 }
2131 }
2132 }
2133 return false;
2134}
2135
2136
2137// testSIV -
2138// When we have a pair of subscripts of the form [c1 + a1*i] and [c2 - a2*i]
2139// where i is an induction variable, c1 and c2 are loop invariant, and a1 and
2140// a2 are constant, we attack it with an SIV test. While they can all be
2141// solved with the Exact SIV test, it's worthwhile to use simpler tests when
2142// they apply; they're cheaper and sometimes more precise.
2143//
2144// Return true if dependence disproved.
2145bool DependenceInfo::testSIV(const SCEV *Src, const SCEV *Dst, unsigned &Level,
2146 FullDependence &Result, Constraint &NewConstraint,
2147 const SCEV *&SplitIter) const {
2148 LLVM_DEBUG(dbgs() << " src = " << *Src << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << " src = " << *Src <<
"\n"; } } while (false)
;
2149 LLVM_DEBUG(dbgs() << " dst = " << *Dst << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << " dst = " << *Dst <<
"\n"; } } while (false)
;
2150 const SCEVAddRecExpr *SrcAddRec = dyn_cast<SCEVAddRecExpr>(Src);
2151 const SCEVAddRecExpr *DstAddRec = dyn_cast<SCEVAddRecExpr>(Dst);
2152 if (SrcAddRec && DstAddRec) {
2153 const SCEV *SrcConst = SrcAddRec->getStart();
2154 const SCEV *DstConst = DstAddRec->getStart();
2155 const SCEV *SrcCoeff = SrcAddRec->getStepRecurrence(*SE);
2156 const SCEV *DstCoeff = DstAddRec->getStepRecurrence(*SE);
2157 const Loop *CurLoop = SrcAddRec->getLoop();
2158 assert(CurLoop == DstAddRec->getLoop() &&((CurLoop == DstAddRec->getLoop() && "both loops in SIV should be same"
) ? static_cast<void> (0) : __assert_fail ("CurLoop == DstAddRec->getLoop() && \"both loops in SIV should be same\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/Analysis/DependenceAnalysis.cpp"
, 2159, __PRETTY_FUNCTION__))
2159 "both loops in SIV should be same")((CurLoop == DstAddRec->getLoop() && "both loops in SIV should be same"
) ? static_cast<void> (0) : __assert_fail ("CurLoop == DstAddRec->getLoop() && \"both loops in SIV should be same\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/Analysis/DependenceAnalysis.cpp"
, 2159, __PRETTY_FUNCTION__))
;
2160 Level = mapSrcLoop(CurLoop);
2161 bool disproven;
2162 if (SrcCoeff == DstCoeff)
2163 disproven = strongSIVtest(SrcCoeff, SrcConst, DstConst, CurLoop,
2164 Level, Result, NewConstraint);
2165 else if (SrcCoeff == SE->getNegativeSCEV(DstCoeff))
2166 disproven = weakCrossingSIVtest(SrcCoeff, SrcConst, DstConst, CurLoop,
2167 Level, Result, NewConstraint, SplitIter);
2168 else
2169 disproven = exactSIVtest(SrcCoeff, DstCoeff, SrcConst, DstConst, CurLoop,
2170 Level, Result, NewConstraint);
2171 return disproven ||
2172 gcdMIVtest(Src, Dst, Result) ||
2173 symbolicRDIVtest(SrcCoeff, DstCoeff, SrcConst, DstConst, CurLoop, CurLoop);
2174 }
2175 if (SrcAddRec) {
2176 const SCEV *SrcConst = SrcAddRec->getStart();
2177 const SCEV *SrcCoeff = SrcAddRec->getStepRecurrence(*SE);
2178 const SCEV *DstConst = Dst;
2179 const Loop *CurLoop = SrcAddRec->getLoop();
2180 Level = mapSrcLoop(CurLoop);
2181 return weakZeroDstSIVtest(SrcCoeff, SrcConst, DstConst, CurLoop,
2182 Level, Result, NewConstraint) ||
2183 gcdMIVtest(Src, Dst, Result);
2184 }
2185 if (DstAddRec) {
2186 const SCEV *DstConst = DstAddRec->getStart();
2187 const SCEV *DstCoeff = DstAddRec->getStepRecurrence(*SE);
2188 const SCEV *SrcConst = Src;
2189 const Loop *CurLoop = DstAddRec->getLoop();
2190 Level = mapDstLoop(CurLoop);
2191 return weakZeroSrcSIVtest(DstCoeff, SrcConst, DstConst,
2192 CurLoop, Level, Result, NewConstraint) ||
2193 gcdMIVtest(Src, Dst, Result);
2194 }
2195 llvm_unreachable("SIV test expected at least one AddRec")::llvm::llvm_unreachable_internal("SIV test expected at least one AddRec"
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/Analysis/DependenceAnalysis.cpp"
, 2195)
;
2196 return false;
2197}
2198
2199
2200// testRDIV -
2201// When we have a pair of subscripts of the form [c1 + a1*i] and [c2 + a2*j]
2202// where i and j are induction variables, c1 and c2 are loop invariant,
2203// and a1 and a2 are constant, we can solve it exactly with an easy adaptation
2204// of the Exact SIV test, the Restricted Double Index Variable (RDIV) test.
2205// It doesn't make sense to talk about distance or direction in this case,
2206// so there's no point in making special versions of the Strong SIV test or
2207// the Weak-crossing SIV test.
2208//
2209// With minor algebra, this test can also be used for things like
2210// [c1 + a1*i + a2*j][c2].
2211//
2212// Return true if dependence disproved.
2213bool DependenceInfo::testRDIV(const SCEV *Src, const SCEV *Dst,
2214 FullDependence &Result) const {
2215 // we have 3 possible situations here:
2216 // 1) [a*i + b] and [c*j + d]
2217 // 2) [a*i + c*j + b] and [d]
2218 // 3) [b] and [a*i + c*j + d]
2219 // We need to find what we've got and get organized
2220
2221 const SCEV *SrcConst, *DstConst;
2222 const SCEV *SrcCoeff, *DstCoeff;
2223 const Loop *SrcLoop, *DstLoop;
2224
2225 LLVM_DEBUG(dbgs() << " src = " << *Src << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << " src = " << *Src <<
"\n"; } } while (false)
;
2226 LLVM_DEBUG(dbgs() << " dst = " << *Dst << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << " dst = " << *Dst <<
"\n"; } } while (false)
;
2227 const SCEVAddRecExpr *SrcAddRec = dyn_cast<SCEVAddRecExpr>(Src);
2228 const SCEVAddRecExpr *DstAddRec = dyn_cast<SCEVAddRecExpr>(Dst);
2229 if (SrcAddRec && DstAddRec) {
2230 SrcConst = SrcAddRec->getStart();
2231 SrcCoeff = SrcAddRec->getStepRecurrence(*SE);
2232 SrcLoop = SrcAddRec->getLoop();
2233 DstConst = DstAddRec->getStart();
2234 DstCoeff = DstAddRec->getStepRecurrence(*SE);
2235 DstLoop = DstAddRec->getLoop();
2236 }
2237 else if (SrcAddRec) {
2238 if (const SCEVAddRecExpr *tmpAddRec =
2239 dyn_cast<SCEVAddRecExpr>(SrcAddRec->getStart())) {
2240 SrcConst = tmpAddRec->getStart();
2241 SrcCoeff = tmpAddRec->getStepRecurrence(*SE);
2242 SrcLoop = tmpAddRec->getLoop();
2243 DstConst = Dst;
2244 DstCoeff = SE->getNegativeSCEV(SrcAddRec->getStepRecurrence(*SE));
2245 DstLoop = SrcAddRec->getLoop();
2246 }
2247 else
2248 llvm_unreachable("RDIV reached by surprising SCEVs")::llvm::llvm_unreachable_internal("RDIV reached by surprising SCEVs"
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/Analysis/DependenceAnalysis.cpp"
, 2248)
;
2249 }
2250 else if (DstAddRec) {
2251 if (const SCEVAddRecExpr *tmpAddRec =
2252 dyn_cast<SCEVAddRecExpr>(DstAddRec->getStart())) {
2253 DstConst = tmpAddRec->getStart();
2254 DstCoeff = tmpAddRec->getStepRecurrence(*SE);
2255 DstLoop = tmpAddRec->getLoop();
2256 SrcConst = Src;
2257 SrcCoeff = SE->getNegativeSCEV(DstAddRec->getStepRecurrence(*SE));
2258 SrcLoop = DstAddRec->getLoop();
2259 }
2260 else
2261 llvm_unreachable("RDIV reached by surprising SCEVs")::llvm::llvm_unreachable_internal("RDIV reached by surprising SCEVs"
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/Analysis/DependenceAnalysis.cpp"
, 2261)
;
2262 }
2263 else
2264 llvm_unreachable("RDIV expected at least one AddRec")::llvm::llvm_unreachable_internal("RDIV expected at least one AddRec"
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/Analysis/DependenceAnalysis.cpp"
, 2264)
;
2265 return exactRDIVtest(SrcCoeff, DstCoeff,
2266 SrcConst, DstConst,
2267 SrcLoop, DstLoop,
2268 Result) ||
2269 gcdMIVtest(Src, Dst, Result) ||
2270 symbolicRDIVtest(SrcCoeff, DstCoeff,
2271 SrcConst, DstConst,
2272 SrcLoop, DstLoop);
2273}
2274
2275
2276// Tests the single-subscript MIV pair (Src and Dst) for dependence.
2277// Return true if dependence disproved.
2278// Can sometimes refine direction vectors.
2279bool DependenceInfo::testMIV(const SCEV *Src, const SCEV *Dst,
2280 const SmallBitVector &Loops,
2281 FullDependence &Result) const {
2282 LLVM_DEBUG(dbgs() << " src = " << *Src << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << " src = " << *Src <<
"\n"; } } while (false)
;
2283 LLVM_DEBUG(dbgs() << " dst = " << *Dst << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << " dst = " << *Dst <<
"\n"; } } while (false)
;
2284 Result.Consistent = false;
2285 return gcdMIVtest(Src, Dst, Result) ||
2286 banerjeeMIVtest(Src, Dst, Loops, Result);
2287}
2288
2289
2290// Given a product, e.g., 10*X*Y, returns the first constant operand,
2291// in this case 10. If there is no constant part, returns NULL.
2292static
2293const SCEVConstant *getConstantPart(const SCEV *Expr) {
2294 if (const auto *Constant = dyn_cast<SCEVConstant>(Expr))
2295 return Constant;
2296 else if (const auto *Product = dyn_cast<SCEVMulExpr>(Expr))
2297 if (const auto *Constant = dyn_cast<SCEVConstant>(Product->getOperand(0)))
2298 return Constant;
2299 return nullptr;
2300}
2301
2302
2303//===----------------------------------------------------------------------===//
2304// gcdMIVtest -
2305// Tests an MIV subscript pair for dependence.
2306// Returns true if any possible dependence is disproved.
2307// Marks the result as inconsistent.
2308// Can sometimes disprove the equal direction for 1 or more loops,
2309// as discussed in Michael Wolfe's book,
2310// High Performance Compilers for Parallel Computing, page 235.
2311//
2312// We spend some effort (code!) to handle cases like
2313// [10*i + 5*N*j + 15*M + 6], where i and j are induction variables,
2314// but M and N are just loop-invariant variables.
2315// This should help us handle linearized subscripts;
2316// also makes this test a useful backup to the various SIV tests.
2317//
2318// It occurs to me that the presence of loop-invariant variables
2319// changes the nature of the test from "greatest common divisor"
2320// to "a common divisor".
2321bool DependenceInfo::gcdMIVtest(const SCEV *Src, const SCEV *Dst,
2322 FullDependence &Result) const {
2323 LLVM_DEBUG(dbgs() << "starting gcd\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "starting gcd\n"; } } while (false)
;
2324 ++GCDapplications;
2325 unsigned BitWidth = SE->getTypeSizeInBits(Src->getType());
2326 APInt RunningGCD = APInt::getNullValue(BitWidth);
2327
2328 // Examine Src coefficients.
2329 // Compute running GCD and record source constant.
2330 // Because we're looking for the constant at the end of the chain,
2331 // we can't quit the loop just because the GCD == 1.
2332 const SCEV *Coefficients = Src;
2333 while (const SCEVAddRecExpr *AddRec =
2334 dyn_cast<SCEVAddRecExpr>(Coefficients)) {
2335 const SCEV *Coeff = AddRec->getStepRecurrence(*SE);
2336 // If the coefficient is the product of a constant and other stuff,
2337 // we can use the constant in the GCD computation.
2338 const auto *Constant = getConstantPart(Coeff);
2339 if (!Constant)
2340 return false;
2341 APInt ConstCoeff = Constant->getAPInt();
2342 RunningGCD = APIntOps::GreatestCommonDivisor(RunningGCD, ConstCoeff.abs());
2343 Coefficients = AddRec->getStart();
2344 }
2345 const SCEV *SrcConst = Coefficients;
2346
2347 // Examine Dst coefficients.
2348 // Compute running GCD and record destination constant.
2349 // Because we're looking for the constant at the end of the chain,
2350 // we can't quit the loop just because the GCD == 1.
2351 Coefficients = Dst;
2352 while (const SCEVAddRecExpr *AddRec =
2353 dyn_cast<SCEVAddRecExpr>(Coefficients)) {
2354 const SCEV *Coeff = AddRec->getStepRecurrence(*SE);
2355 // If the coefficient is the product of a constant and other stuff,
2356 // we can use the constant in the GCD computation.
2357 const auto *Constant = getConstantPart(Coeff);
2358 if (!Constant)
2359 return false;
2360 APInt ConstCoeff = Constant->getAPInt();
2361 RunningGCD = APIntOps::GreatestCommonDivisor(RunningGCD, ConstCoeff.abs());
2362 Coefficients = AddRec->getStart();
2363 }
2364 const SCEV *DstConst = Coefficients;
2365
2366 APInt ExtraGCD = APInt::getNullValue(BitWidth);
2367 const SCEV *Delta = SE->getMinusSCEV(DstConst, SrcConst);
2368 LLVM_DEBUG(dbgs() << " Delta = " << *Delta << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << " Delta = " << *Delta <<
"\n"; } } while (false)
;
2369 const SCEVConstant *Constant = dyn_cast<SCEVConstant>(Delta);
2370 if (const SCEVAddExpr *Sum = dyn_cast<SCEVAddExpr>(Delta)) {
2371 // If Delta is a sum of products, we may be able to make further progress.
2372 for (unsigned Op = 0, Ops = Sum->getNumOperands(); Op < Ops; Op++) {
2373 const SCEV *Operand = Sum->getOperand(Op);
2374 if (isa<SCEVConstant>(Operand)) {
2375 assert(!Constant && "Surprised to find multiple constants")((!Constant && "Surprised to find multiple constants"
) ? static_cast<void> (0) : __assert_fail ("!Constant && \"Surprised to find multiple constants\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/Analysis/DependenceAnalysis.cpp"
, 2375, __PRETTY_FUNCTION__))
;
2376 Constant = cast<SCEVConstant>(Operand);
2377 }
2378 else if (const SCEVMulExpr *Product = dyn_cast<SCEVMulExpr>(Operand)) {
2379 // Search for constant operand to participate in GCD;
2380 // If none found; return false.
2381 const SCEVConstant *ConstOp = getConstantPart(Product);
2382 if (!ConstOp)
2383 return false;
2384 APInt ConstOpValue = ConstOp->getAPInt();
2385 ExtraGCD = APIntOps::GreatestCommonDivisor(ExtraGCD,
2386 ConstOpValue.abs());
2387 }
2388 else
2389 return false;
2390 }
2391 }
2392 if (!Constant)
2393 return false;
2394 APInt ConstDelta = cast<SCEVConstant>(Constant)->getAPInt();
2395 LLVM_DEBUG(dbgs() << " ConstDelta = " << ConstDelta << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << " ConstDelta = " << ConstDelta
<< "\n"; } } while (false)
;
2396 if (ConstDelta == 0)
2397 return false;
2398 RunningGCD = APIntOps::GreatestCommonDivisor(RunningGCD, ExtraGCD);
2399 LLVM_DEBUG(dbgs() << " RunningGCD = " << RunningGCD << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << " RunningGCD = " << RunningGCD
<< "\n"; } } while (false)
;
2400 APInt Remainder = ConstDelta.srem(RunningGCD);
2401 if (Remainder != 0) {
2402 ++GCDindependence;
2403 return true;
2404 }
2405
2406 // Try to disprove equal directions.
2407 // For example, given a subscript pair [3*i + 2*j] and [i' + 2*j' - 1],
2408 // the code above can't disprove the dependence because the GCD = 1.
2409 // So we consider what happen if i = i' and what happens if j = j'.
2410 // If i = i', we can simplify the subscript to [2*i + 2*j] and [2*j' - 1],
2411 // which is infeasible, so we can disallow the = direction for the i level.
2412 // Setting j = j' doesn't help matters, so we end up with a direction vector
2413 // of [<>, *]
2414 //
2415 // Given A[5*i + 10*j*M + 9*M*N] and A[15*i + 20*j*M - 21*N*M + 5],
2416 // we need to remember that the constant part is 5 and the RunningGCD should
2417 // be initialized to ExtraGCD = 30.
2418 LLVM_DEBUG(dbgs() << " ExtraGCD = " << ExtraGCD << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << " ExtraGCD = " << ExtraGCD
<< '\n'; } } while (false)
;
2419
2420 bool Improved = false;
2421 Coefficients = Src;
2422 while (const SCEVAddRecExpr *AddRec =
2423 dyn_cast<SCEVAddRecExpr>(Coefficients)) {
2424 Coefficients = AddRec->getStart();
2425 const Loop *CurLoop = AddRec->getLoop();
2426 RunningGCD = ExtraGCD;
2427 const SCEV *SrcCoeff = AddRec->getStepRecurrence(*SE);
2428 const SCEV *DstCoeff = SE->getMinusSCEV(SrcCoeff, SrcCoeff);
2429 const SCEV *Inner = Src;
2430 while (RunningGCD != 1 && isa<SCEVAddRecExpr>(Inner)) {
2431 AddRec = cast<SCEVAddRecExpr>(Inner);
2432 const SCEV *Coeff = AddRec->getStepRecurrence(*SE);
2433 if (CurLoop == AddRec->getLoop())
2434 ; // SrcCoeff == Coeff
2435 else {
2436 // If the coefficient is the product of a constant and other stuff,
2437 // we can use the constant in the GCD computation.
2438 Constant = getConstantPart(Coeff);
2439 if (!Constant)
2440 return false;
2441 APInt ConstCoeff = Constant->getAPInt();
2442 RunningGCD = APIntOps::GreatestCommonDivisor(RunningGCD, ConstCoeff.abs());
2443 }
2444 Inner = AddRec->getStart();
2445 }
2446 Inner = Dst;
2447 while (RunningGCD != 1 && isa<SCEVAddRecExpr>(Inner)) {
2448 AddRec = cast<SCEVAddRecExpr>(Inner);
2449 const SCEV *Coeff = AddRec->getStepRecurrence(*SE);
2450 if (CurLoop == AddRec->getLoop())
2451 DstCoeff = Coeff;
2452 else {
2453 // If the coefficient is the product of a constant and other stuff,
2454 // we can use the constant in the GCD computation.
2455 Constant = getConstantPart(Coeff);
2456 if (!Constant)
2457 return false;
2458 APInt ConstCoeff = Constant->getAPInt();
2459 RunningGCD = APIntOps::GreatestCommonDivisor(RunningGCD, ConstCoeff.abs());
2460 }
2461 Inner = AddRec->getStart();
2462 }
2463 Delta = SE->getMinusSCEV(SrcCoeff, DstCoeff);
2464 // If the coefficient is the product of a constant and other stuff,
2465 // we can use the constant in the GCD computation.
2466 Constant = getConstantPart(Delta);
2467 if (!Constant)
2468 // The difference of the two coefficients might not be a product
2469 // or constant, in which case we give up on this direction.
2470 continue;
2471 APInt ConstCoeff = Constant->getAPInt();
2472 RunningGCD = APIntOps::GreatestCommonDivisor(RunningGCD, ConstCoeff.abs());
2473 LLVM_DEBUG(dbgs() << "\tRunningGCD = " << RunningGCD << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\tRunningGCD = " << RunningGCD
<< "\n"; } } while (false)
;
2474 if (RunningGCD != 0) {
2475 Remainder = ConstDelta.srem(RunningGCD);
2476 LLVM_DEBUG(dbgs() << "\tRemainder = " << Remainder << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\tRemainder = " << Remainder
<< "\n"; } } while (false)
;
2477 if (Remainder != 0) {
2478 unsigned Level = mapSrcLoop(CurLoop);
2479 Result.DV[Level - 1].Direction &= unsigned(~Dependence::DVEntry::EQ);
2480 Improved = true;
2481 }
2482 }
2483 }
2484 if (Improved)
2485 ++GCDsuccesses;
2486 LLVM_DEBUG(dbgs() << "all done\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "all done\n"; } } while (false)
;
2487 return false;
2488}
2489
2490
2491//===----------------------------------------------------------------------===//
2492// banerjeeMIVtest -
2493// Use Banerjee's Inequalities to test an MIV subscript pair.
2494// (Wolfe, in the race-car book, calls this the Extreme Value Test.)
2495// Generally follows the discussion in Section 2.5.2 of
2496//
2497// Optimizing Supercompilers for Supercomputers
2498// Michael Wolfe
2499//
2500// The inequalities given on page 25 are simplified in that loops are
2501// normalized so that the lower bound is always 0 and the stride is always 1.
2502// For example, Wolfe gives
2503//
2504// LB^<_k = (A^-_k - B_k)^- (U_k - L_k - N_k) + (A_k - B_k)L_k - B_k N_k
2505//
2506// where A_k is the coefficient of the kth index in the source subscript,
2507// B_k is the coefficient of the kth index in the destination subscript,
2508// U_k is the upper bound of the kth index, L_k is the lower bound of the Kth
2509// index, and N_k is the stride of the kth index. Since all loops are normalized
2510// by the SCEV package, N_k = 1 and L_k = 0, allowing us to simplify the
2511// equation to
2512//
2513// LB^<_k = (A^-_k - B_k)^- (U_k - 0 - 1) + (A_k - B_k)0 - B_k 1
2514// = (A^-_k - B_k)^- (U_k - 1) - B_k
2515//
2516// Similar simplifications are possible for the other equations.
2517//
2518// When we can't determine the number of iterations for a loop,
2519// we use NULL as an indicator for the worst case, infinity.
2520// When computing the upper bound, NULL denotes +inf;
2521// for the lower bound, NULL denotes -inf.
2522//
2523// Return true if dependence disproved.
2524bool DependenceInfo::banerjeeMIVtest(const SCEV *Src, const SCEV *Dst,
2525 const SmallBitVector &Loops,
2526 FullDependence &Result) const {
2527 LLVM_DEBUG(dbgs() << "starting Banerjee\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "starting Banerjee\n"; } } while (false
)
;
2528 ++BanerjeeApplications;
2529 LLVM_DEBUG(dbgs() << " Src = " << *Src << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << " Src = " << *Src <<
'\n'; } } while (false)
;
2530 const SCEV *A0;
2531 CoefficientInfo *A = collectCoeffInfo(Src, true, A0);
2532 LLVM_DEBUG(dbgs() << " Dst = " << *Dst << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << " Dst = " << *Dst <<
'\n'; } } while (false)
;
2533 const SCEV *B0;
2534 CoefficientInfo *B = collectCoeffInfo(Dst, false, B0);
2535 BoundInfo *Bound = new BoundInfo[MaxLevels + 1];
2536 const SCEV *Delta = SE->getMinusSCEV(B0, A0);
2537 LLVM_DEBUG(dbgs() << "\tDelta = " << *Delta << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\tDelta = " << *Delta <<
'\n'; } } while (false)
;
2538
2539 // Compute bounds for all the * directions.
2540 LLVM_DEBUG(dbgs() << "\tBounds[*]\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\tBounds[*]\n"; } } while (false)
;
2541 for (unsigned K = 1; K <= MaxLevels; ++K) {
2542 Bound[K].Iterations = A[K].Iterations ? A[K].Iterations : B[K].Iterations;
2543 Bound[K].Direction = Dependence::DVEntry::ALL;
2544 Bound[K].DirSet = Dependence::DVEntry::NONE;
2545 findBoundsALL(A, B, Bound, K);
2546#ifndef NDEBUG
2547 LLVM_DEBUG(dbgs() << "\t " << K << '\t')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\t " << K << '\t'; }
} while (false)
;
2548 if (Bound[K].Lower[Dependence::DVEntry::ALL])
2549 LLVM_DEBUG(dbgs() << *Bound[K].Lower[Dependence::DVEntry::ALL] << '\t')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << *Bound[K].Lower[Dependence::DVEntry
::ALL] << '\t'; } } while (false)
;
2550 else
2551 LLVM_DEBUG(dbgs() << "-inf\t")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "-inf\t"; } } while (false)
;
2552 if (Bound[K].Upper[Dependence::DVEntry::ALL])
2553 LLVM_DEBUG(dbgs() << *Bound[K].Upper[Dependence::DVEntry::ALL] << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << *Bound[K].Upper[Dependence::DVEntry
::ALL] << '\n'; } } while (false)
;
2554 else
2555 LLVM_DEBUG(dbgs() << "+inf\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "+inf\n"; } } while (false)
;
2556#endif
2557 }
2558
2559 // Test the *, *, *, ... case.
2560 bool Disproved = false;
2561 if (testBounds(Dependence::DVEntry::ALL, 0, Bound, Delta)) {
2562 // Explore the direction vector hierarchy.
2563 unsigned DepthExpanded = 0;
2564 unsigned NewDeps = exploreDirections(1, A, B, Bound,
2565 Loops, DepthExpanded, Delta);
2566 if (NewDeps > 0) {
2567 bool Improved = false;
2568 for (unsigned K = 1; K <= CommonLevels; ++K) {
2569 if (Loops[K]) {
2570 unsigned Old = Result.DV[K - 1].Direction;
2571 Result.DV[K - 1].Direction = Old & Bound[K].DirSet;
2572 Improved |= Old != Result.DV[K - 1].Direction;
2573 if (!Result.DV[K - 1].Direction) {
2574 Improved = false;
2575 Disproved = true;
2576 break;
2577 }
2578 }
2579 }
2580 if (Improved)
2581 ++BanerjeeSuccesses;
2582 }
2583 else {
2584 ++BanerjeeIndependence;
2585 Disproved = true;
2586 }
2587 }
2588 else {
2589 ++BanerjeeIndependence;
2590 Disproved = true;
2591 }
2592 delete [] Bound;
2593 delete [] A;
2594 delete [] B;
2595 return Disproved;
2596}
2597
2598
2599// Hierarchically expands the direction vector
2600// search space, combining the directions of discovered dependences
2601// in the DirSet field of Bound. Returns the number of distinct
2602// dependences discovered. If the dependence is disproved,
2603// it will return 0.
2604unsigned DependenceInfo::exploreDirections(unsigned Level, CoefficientInfo *A,
2605 CoefficientInfo *B, BoundInfo *Bound,
2606 const SmallBitVector &Loops,
2607 unsigned &DepthExpanded,
2608 const SCEV *Delta) const {
2609 if (Level > CommonLevels) {
2610 // record result
2611 LLVM_DEBUG(dbgs() << "\t[")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\t["; } } while (false)
;
2612 for (unsigned K = 1; K <= CommonLevels; ++K) {
2613 if (Loops[K]) {
2614 Bound[K].DirSet |= Bound[K].Direction;
2615#ifndef NDEBUG
2616 switch (Bound[K].Direction) {
2617 case Dependence::DVEntry::LT:
2618 LLVM_DEBUG(dbgs() << " <")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << " <"; } } while (false)
;
2619 break;
2620 case Dependence::DVEntry::EQ:
2621 LLVM_DEBUG(dbgs() << " =")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << " ="; } } while (false)
;
2622 break;
2623 case Dependence::DVEntry::GT:
2624 LLVM_DEBUG(dbgs() << " >")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << " >"; } } while (false)
;
2625 break;
2626 case Dependence::DVEntry::ALL:
2627 LLVM_DEBUG(dbgs() << " *")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << " *"; } } while (false)
;
2628 break;
2629 default:
2630 llvm_unreachable("unexpected Bound[K].Direction")::llvm::llvm_unreachable_internal("unexpected Bound[K].Direction"
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/Analysis/DependenceAnalysis.cpp"
, 2630)
;
2631 }
2632#endif
2633 }
2634 }
2635 LLVM_DEBUG(dbgs() << " ]\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << " ]\n"; } } while (false)
;
2636 return 1;
2637 }
2638 if (Loops[Level]) {
2639 if (Level > DepthExpanded) {
2640 DepthExpanded = Level;
2641 // compute bounds for <, =, > at current level
2642 findBoundsLT(A, B, Bound, Level);
2643 findBoundsGT(A, B, Bound, Level);
2644 findBoundsEQ(A, B, Bound, Level);
2645#ifndef NDEBUG
2646 LLVM_DEBUG(dbgs() << "\tBound for level = " << Level << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\tBound for level = " << Level
<< '\n'; } } while (false)
;
2647 LLVM_DEBUG(dbgs() << "\t <\t")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\t <\t"; } } while (false)
;
2648 if (Bound[Level].Lower[Dependence::DVEntry::LT])
2649 LLVM_DEBUG(dbgs() << *Bound[Level].Lower[Dependence::DVEntry::LT]do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << *Bound[Level].Lower[Dependence::DVEntry
::LT] << '\t'; } } while (false)
2650 << '\t')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << *Bound[Level].Lower[Dependence::DVEntry
::LT] << '\t'; } } while (false)
;
2651 else
2652 LLVM_DEBUG(dbgs() << "-inf\t")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "-inf\t"; } } while (false)
;
2653 if (Bound[Level].Upper[Dependence::DVEntry::LT])
2654 LLVM_DEBUG(dbgs() << *Bound[Level].Upper[Dependence::DVEntry::LT]do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << *Bound[Level].Upper[Dependence::DVEntry
::LT] << '\n'; } } while (false)
2655 << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << *Bound[Level].Upper[Dependence::DVEntry
::LT] << '\n'; } } while (false)
;
2656 else
2657 LLVM_DEBUG(dbgs() << "+inf\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "+inf\n"; } } while (false)
;
2658 LLVM_DEBUG(dbgs() << "\t =\t")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\t =\t"; } } while (false)
;
2659 if (Bound[Level].Lower[Dependence::DVEntry::EQ])
2660 LLVM_DEBUG(dbgs() << *Bound[Level].Lower[Dependence::DVEntry::EQ]do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << *Bound[Level].Lower[Dependence::DVEntry
::EQ] << '\t'; } } while (false)
2661 << '\t')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << *Bound[Level].Lower[Dependence::DVEntry
::EQ] << '\t'; } } while (false)
;
2662 else
2663 LLVM_DEBUG(dbgs() << "-inf\t")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "-inf\t"; } } while (false)
;
2664 if (Bound[Level].Upper[Dependence::DVEntry::EQ])
2665 LLVM_DEBUG(dbgs() << *Bound[Level].Upper[Dependence::DVEntry::EQ]do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << *Bound[Level].Upper[Dependence::DVEntry
::EQ] << '\n'; } } while (false)
2666 << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << *Bound[Level].Upper[Dependence::DVEntry
::EQ] << '\n'; } } while (false)
;
2667 else
2668 LLVM_DEBUG(dbgs() << "+inf\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "+inf\n"; } } while (false)
;
2669 LLVM_DEBUG(dbgs() << "\t >\t")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\t >\t"; } } while (false)
;
2670 if (Bound[Level].Lower[Dependence::DVEntry::GT])
2671 LLVM_DEBUG(dbgs() << *Bound[Level].Lower[Dependence::DVEntry::GT]do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << *Bound[Level].Lower[Dependence::DVEntry
::GT] << '\t'; } } while (false)
2672 << '\t')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << *Bound[Level].Lower[Dependence::DVEntry
::GT] << '\t'; } } while (false)
;
2673 else
2674 LLVM_DEBUG(dbgs() << "-inf\t")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "-inf\t"; } } while (false)
;
2675 if (Bound[Level].Upper[Dependence::DVEntry::GT])
2676 LLVM_DEBUG(dbgs() << *Bound[Level].Upper[Dependence::DVEntry::GT]do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << *Bound[Level].Upper[Dependence::DVEntry
::GT] << '\n'; } } while (false)
2677 << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << *Bound[Level].Upper[Dependence::DVEntry
::GT] << '\n'; } } while (false)
;
2678 else
2679 LLVM_DEBUG(dbgs() << "+inf\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "+inf\n"; } } while (false)
;
2680#endif
2681 }
2682
2683 unsigned NewDeps = 0;
2684
2685 // test bounds for <, *, *, ...
2686 if (testBounds(Dependence::DVEntry::LT, Level, Bound, Delta))
2687 NewDeps += exploreDirections(Level + 1, A, B, Bound,
2688 Loops, DepthExpanded, Delta);
2689
2690 // Test bounds for =, *, *, ...
2691 if (testBounds(Dependence::DVEntry::EQ, Level, Bound, Delta))
2692 NewDeps += exploreDirections(Level + 1, A, B, Bound,
2693 Loops, DepthExpanded, Delta);
2694
2695 // test bounds for >, *, *, ...
2696 if (testBounds(Dependence::DVEntry::GT, Level, Bound, Delta))
2697 NewDeps += exploreDirections(Level + 1, A, B, Bound,
2698 Loops, DepthExpanded, Delta);
2699
2700 Bound[Level].Direction = Dependence::DVEntry::ALL;
2701 return NewDeps;
2702 }
2703 else
2704 return exploreDirections(Level + 1, A, B, Bound, Loops, DepthExpanded, Delta);
2705}
2706
2707
2708// Returns true iff the current bounds are plausible.
2709bool DependenceInfo::testBounds(unsigned char DirKind, unsigned Level,
2710 BoundInfo *Bound, const SCEV *Delta) const {
2711 Bound[Level].Direction = DirKind;
2712 if (const SCEV *LowerBound = getLowerBound(Bound))
2713 if (isKnownPredicate(CmpInst::ICMP_SGT, LowerBound, Delta))
2714 return false;
2715 if (const SCEV *UpperBound = getUpperBound(Bound))
2716 if (isKnownPredicate(CmpInst::ICMP_SGT, Delta, UpperBound))
2717 return false;
2718 return true;
2719}
2720
2721
2722// Computes the upper and lower bounds for level K
2723// using the * direction. Records them in Bound.
2724// Wolfe gives the equations
2725//
2726// LB^*_k = (A^-_k - B^+_k)(U_k - L_k) + (A_k - B_k)L_k
2727// UB^*_k = (A^+_k - B^-_k)(U_k - L_k) + (A_k - B_k)L_k
2728//
2729// Since we normalize loops, we can simplify these equations to
2730//
2731// LB^*_k = (A^-_k - B^+_k)U_k
2732// UB^*_k = (A^+_k - B^-_k)U_k
2733//
2734// We must be careful to handle the case where the upper bound is unknown.
2735// Note that the lower bound is always <= 0
2736// and the upper bound is always >= 0.
2737void DependenceInfo::findBoundsALL(CoefficientInfo *A, CoefficientInfo *B,
2738 BoundInfo *Bound, unsigned K) const {
2739 Bound[K].Lower[Dependence::DVEntry::ALL] = nullptr; // Default value = -infinity.
2740 Bound[K].Upper[Dependence::DVEntry::ALL] = nullptr; // Default value = +infinity.
2741 if (Bound[K].Iterations) {
2742 Bound[K].Lower[Dependence::DVEntry::ALL] =
2743 SE->getMulExpr(SE->getMinusSCEV(A[K].NegPart, B[K].PosPart),
2744 Bound[K].Iterations);
2745 Bound[K].Upper[Dependence::DVEntry::ALL] =
2746 SE->getMulExpr(SE->getMinusSCEV(A[K].PosPart, B[K].NegPart),
2747 Bound[K].Iterations);
2748 }
2749 else {
2750 // If the difference is 0, we won't need to know the number of iterations.
2751 if (isKnownPredicate(CmpInst::ICMP_EQ, A[K].NegPart, B[K].PosPart))
2752 Bound[K].Lower[Dependence::DVEntry::ALL] =
2753 SE->getZero(A[K].Coeff->getType());
2754 if (isKnownPredicate(CmpInst::ICMP_EQ, A[K].PosPart, B[K].NegPart))
2755 Bound[K].Upper[Dependence::DVEntry::ALL] =
2756 SE->getZero(A[K].Coeff->getType());
2757 }
2758}
2759
2760
2761// Computes the upper and lower bounds for level K
2762// using the = direction. Records them in Bound.
2763// Wolfe gives the equations
2764//
2765// LB^=_k = (A_k - B_k)^- (U_k - L_k) + (A_k - B_k)L_k
2766// UB^=_k = (A_k - B_k)^+ (U_k - L_k) + (A_k - B_k)L_k
2767//
2768// Since we normalize loops, we can simplify these equations to
2769//
2770// LB^=_k = (A_k - B_k)^- U_k
2771// UB^=_k = (A_k - B_k)^+ U_k
2772//
2773// We must be careful to handle the case where the upper bound is unknown.
2774// Note that the lower bound is always <= 0
2775// and the upper bound is always >= 0.
2776void DependenceInfo::findBoundsEQ(CoefficientInfo *A, CoefficientInfo *B,
2777 BoundInfo *Bound, unsigned K) const {
2778 Bound[K].Lower[Dependence::DVEntry::EQ] = nullptr; // Default value = -infinity.
2779 Bound[K].Upper[Dependence::DVEntry::EQ] = nullptr; // Default value = +infinity.
2780 if (Bound[K].Iterations) {
2781 const SCEV *Delta = SE->getMinusSCEV(A[K].Coeff, B[K].Coeff);
2782 const SCEV *NegativePart = getNegativePart(Delta);
2783 Bound[K].Lower[Dependence::DVEntry::EQ] =
2784 SE->getMulExpr(NegativePart, Bound[K].Iterations);
2785 const SCEV *PositivePart = getPositivePart(Delta);
2786 Bound[K].Upper[Dependence::DVEntry::EQ] =
2787 SE->getMulExpr(PositivePart, Bound[K].Iterations);
2788 }
2789 else {
2790 // If the positive/negative part of the difference is 0,
2791 // we won't need to know the number of iterations.
2792 const SCEV *Delta = SE->getMinusSCEV(A[K].Coeff, B[K].Coeff);
2793 const SCEV *NegativePart = getNegativePart(Delta);
2794 if (NegativePart->isZero())
2795 Bound[K].Lower[Dependence::DVEntry::EQ] = NegativePart; // Zero
2796 const SCEV *PositivePart = getPositivePart(Delta);
2797 if (PositivePart->isZero())
2798 Bound[K].Upper[Dependence::DVEntry::EQ] = PositivePart; // Zero
2799 }
2800}
2801
2802
2803// Computes the upper and lower bounds for level K
2804// using the < direction. Records them in Bound.
2805// Wolfe gives the equations
2806//
2807// LB^<_k = (A^-_k - B_k)^- (U_k - L_k - N_k) + (A_k - B_k)L_k - B_k N_k
2808// UB^<_k = (A^+_k - B_k)^+ (U_k - L_k - N_k) + (A_k - B_k)L_k - B_k N_k
2809//
2810// Since we normalize loops, we can simplify these equations to
2811//
2812// LB^<_k = (A^-_k - B_k)^- (U_k - 1) - B_k
2813// UB^<_k = (A^+_k - B_k)^+ (U_k - 1) - B_k
2814//
2815// We must be careful to handle the case where the upper bound is unknown.
2816void DependenceInfo::findBoundsLT(CoefficientInfo *A, CoefficientInfo *B,
2817 BoundInfo *Bound, unsigned K) const {
2818 Bound[K].Lower[Dependence::DVEntry::LT] = nullptr; // Default value = -infinity.
2819 Bound[K].Upper[Dependence::DVEntry::LT] = nullptr; // Default value = +infinity.
2820 if (Bound[K].Iterations) {
2821 const SCEV *Iter_1 = SE->getMinusSCEV(
2822 Bound[K].Iterations, SE->getOne(Bound[K].Iterations->getType()));
2823 const SCEV *NegPart =
2824 getNegativePart(SE->getMinusSCEV(A[K].NegPart, B[K].Coeff));
2825 Bound[K].Lower[Dependence::DVEntry::LT] =
2826 SE->getMinusSCEV(SE->getMulExpr(NegPart, Iter_1), B[K].Coeff);
2827 const SCEV *PosPart =
2828 getPositivePart(SE->getMinusSCEV(A[K].PosPart, B[K].Coeff));
2829 Bound[K].Upper[Dependence::DVEntry::LT] =
2830 SE->getMinusSCEV(SE->getMulExpr(PosPart, Iter_1), B[K].Coeff);
2831 }
2832 else {
2833 // If the positive/negative part of the difference is 0,
2834 // we won't need to know the number of iterations.
2835 const SCEV *NegPart =
2836 getNegativePart(SE->getMinusSCEV(A[K].NegPart, B[K].Coeff));
2837 if (NegPart->isZero())
2838 Bound[K].Lower[Dependence::DVEntry::LT] = SE->getNegativeSCEV(B[K].Coeff);
2839 const SCEV *PosPart =
2840 getPositivePart(SE->getMinusSCEV(A[K].PosPart, B[K].Coeff));
2841 if (PosPart->isZero())
2842 Bound[K].Upper[Dependence::DVEntry::LT] = SE->getNegativeSCEV(B[K].Coeff);
2843 }
2844}
2845
2846
2847// Computes the upper and lower bounds for level K
2848// using the > direction. Records them in Bound.
2849// Wolfe gives the equations
2850//
2851// LB^>_k = (A_k - B^+_k)^- (U_k - L_k - N_k) + (A_k - B_k)L_k + A_k N_k
2852// UB^>_k = (A_k - B^-_k)^+ (U_k - L_k - N_k) + (A_k - B_k)L_k + A_k N_k
2853//
2854// Since we normalize loops, we can simplify these equations to
2855//
2856// LB^>_k = (A_k - B^+_k)^- (U_k - 1) + A_k
2857// UB^>_k = (A_k - B^-_k)^+ (U_k - 1) + A_k
2858//
2859// We must be careful to handle the case where the upper bound is unknown.
2860void DependenceInfo::findBoundsGT(CoefficientInfo *A, CoefficientInfo *B,
2861 BoundInfo *Bound, unsigned K) const {
2862 Bound[K].Lower[Dependence::DVEntry::GT] = nullptr; // Default value = -infinity.
2863 Bound[K].Upper[Dependence::DVEntry::GT] = nullptr; // Default value = +infinity.
2864 if (Bound[K].Iterations) {
2865 const SCEV *Iter_1 = SE->getMinusSCEV(
2866 Bound[K].Iterations, SE->getOne(Bound[K].Iterations->getType()));
2867 const SCEV *NegPart =
2868 getNegativePart(SE->getMinusSCEV(A[K].Coeff, B[K].PosPart));
2869 Bound[K].Lower[Dependence::DVEntry::GT] =
2870 SE->getAddExpr(SE->getMulExpr(NegPart, Iter_1), A[K].Coeff);
2871 const SCEV *PosPart =
2872 getPositivePart(SE->getMinusSCEV(A[K].Coeff, B[K].NegPart));
2873 Bound[K].Upper[Dependence::DVEntry::GT] =
2874 SE->getAddExpr(SE->getMulExpr(PosPart, Iter_1), A[K].Coeff);
2875 }
2876 else {
2877 // If the positive/negative part of the difference is 0,
2878 // we won't need to know the number of iterations.
2879 const SCEV *NegPart = getNegativePart(SE->getMinusSCEV(A[K].Coeff, B[K].PosPart));
2880 if (NegPart->isZero())
2881 Bound[K].Lower[Dependence::DVEntry::GT] = A[K].Coeff;
2882 const SCEV *PosPart = getPositivePart(SE->getMinusSCEV(A[K].Coeff, B[K].NegPart));
2883 if (PosPart->isZero())
2884 Bound[K].Upper[Dependence::DVEntry::GT] = A[K].Coeff;
2885 }
2886}
2887
2888
2889// X^+ = max(X, 0)
2890const SCEV *DependenceInfo::getPositivePart(const SCEV *X) const {
2891 return SE->getSMaxExpr(X, SE->getZero(X->getType()));
2892}
2893
2894
2895// X^- = min(X, 0)
2896const SCEV *DependenceInfo::getNegativePart(const SCEV *X) const {
2897 return SE->getSMinExpr(X, SE->getZero(X->getType()));
2898}
2899
2900
2901// Walks through the subscript,
2902// collecting each coefficient, the associated loop bounds,
2903// and recording its positive and negative parts for later use.
2904DependenceInfo::CoefficientInfo *
2905DependenceInfo::collectCoeffInfo(const SCEV *Subscript, bool SrcFlag,
2906 const SCEV *&Constant) const {
2907 const SCEV *Zero = SE->getZero(Subscript->getType());
2908 CoefficientInfo *CI = new CoefficientInfo[MaxLevels + 1];
2909 for (unsigned K = 1; K <= MaxLevels; ++K) {
2910 CI[K].Coeff = Zero;
2911 CI[K].PosPart = Zero;
2912 CI[K].NegPart = Zero;
2913 CI[K].Iterations = nullptr;
2914 }
2915 while (const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(Subscript)) {
2916 const Loop *L = AddRec->getLoop();
2917 unsigned K = SrcFlag ? mapSrcLoop(L) : mapDstLoop(L);
2918 CI[K].Coeff = AddRec->getStepRecurrence(*SE);
2919 CI[K].PosPart = getPositivePart(CI[K].Coeff);
2920 CI[K].NegPart = getNegativePart(CI[K].Coeff);
2921 CI[K].Iterations = collectUpperBound(L, Subscript->getType());
2922 Subscript = AddRec->getStart();
2923 }
2924 Constant = Subscript;
2925#ifndef NDEBUG
2926 LLVM_DEBUG(dbgs() << "\tCoefficient Info\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\tCoefficient Info\n"; } } while (
false)
;
2927 for (unsigned K = 1; K <= MaxLevels; ++K) {
2928 LLVM_DEBUG(dbgs() << "\t " << K << "\t" << *CI[K].Coeff)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\t " << K << "\t" <<
*CI[K].Coeff; } } while (false)
;
2929 LLVM_DEBUG(dbgs() << "\tPos Part = ")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\tPos Part = "; } } while (false)
;
2930 LLVM_DEBUG(dbgs() << *CI[K].PosPart)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << *CI[K].PosPart; } } while (false)
;
2931 LLVM_DEBUG(dbgs() << "\tNeg Part = ")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\tNeg Part = "; } } while (false)
;
2932 LLVM_DEBUG(dbgs() << *CI[K].NegPart)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << *CI[K].NegPart; } } while (false)
;
2933 LLVM_DEBUG(dbgs() << "\tUpper Bound = ")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\tUpper Bound = "; } } while (false
)
;
2934 if (CI[K].Iterations)
2935 LLVM_DEBUG(dbgs() << *CI[K].Iterations)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << *CI[K].Iterations; } } while (false
)
;
2936 else
2937 LLVM_DEBUG(dbgs() << "+inf")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "+inf"; } } while (false)
;
2938 LLVM_DEBUG(dbgs() << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << '\n'; } } while (false)
;
2939 }
2940 LLVM_DEBUG(dbgs() << "\t Constant = " << *Subscript << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\t Constant = " << *Subscript
<< '\n'; } } while (false)
;
2941#endif
2942 return CI;
2943}
2944
2945
2946// Looks through all the bounds info and
2947// computes the lower bound given the current direction settings
2948// at each level. If the lower bound for any level is -inf,
2949// the result is -inf.
2950const SCEV *DependenceInfo::getLowerBound(BoundInfo *Bound) const {
2951 const SCEV *Sum = Bound[1].Lower[Bound[1].Direction];
2952 for (unsigned K = 2; Sum && K <= MaxLevels; ++K) {
2953 if (Bound[K].Lower[Bound[K].Direction])
2954 Sum = SE->getAddExpr(Sum, Bound[K].Lower[Bound[K].Direction]);
2955 else
2956 Sum = nullptr;
2957 }
2958 return Sum;
2959}
2960
2961
2962// Looks through all the bounds info and
2963// computes the upper bound given the current direction settings
2964// at each level. If the upper bound at any level is +inf,
2965// the result is +inf.
2966const SCEV *DependenceInfo::getUpperBound(BoundInfo *Bound) const {
2967 const SCEV *Sum = Bound[1].Upper[Bound[1].Direction];
2968 for (unsigned K = 2; Sum && K <= MaxLevels; ++K) {
2969 if (Bound[K].Upper[Bound[K].Direction])
2970 Sum = SE->getAddExpr(Sum, Bound[K].Upper[Bound[K].Direction]);
2971 else
2972 Sum = nullptr;
2973 }
2974 return Sum;
2975}
2976
2977
2978//===----------------------------------------------------------------------===//
2979// Constraint manipulation for Delta test.
2980
2981// Given a linear SCEV,
2982// return the coefficient (the step)
2983// corresponding to the specified loop.
2984// If there isn't one, return 0.
2985// For example, given a*i + b*j + c*k, finding the coefficient
2986// corresponding to the j loop would yield b.
2987const SCEV *DependenceInfo::findCoefficient(const SCEV *Expr,
2988 const Loop *TargetLoop) const {
2989 const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(Expr);
2990 if (!AddRec)
2991 return SE->getZero(Expr->getType());
2992 if (AddRec->getLoop() == TargetLoop)
2993 return AddRec->getStepRecurrence(*SE);
2994 return findCoefficient(AddRec->getStart(), TargetLoop);
2995}
2996
2997
2998// Given a linear SCEV,
2999// return the SCEV given by zeroing out the coefficient
3000// corresponding to the specified loop.
3001// For example, given a*i + b*j + c*k, zeroing the coefficient
3002// corresponding to the j loop would yield a*i + c*k.
3003const SCEV *DependenceInfo::zeroCoefficient(const SCEV *Expr,
3004 const Loop *TargetLoop) const {
3005 const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(Expr);
3006 if (!AddRec)
3007 return Expr; // ignore
3008 if (AddRec->getLoop() == TargetLoop)
3009 return AddRec->getStart();
3010 return SE->getAddRecExpr(zeroCoefficient(AddRec->getStart(), TargetLoop),
3011 AddRec->getStepRecurrence(*SE),
3012 AddRec->getLoop(),
3013 AddRec->getNoWrapFlags());
3014}
3015
3016
3017// Given a linear SCEV Expr,
3018// return the SCEV given by adding some Value to the
3019// coefficient corresponding to the specified TargetLoop.
3020// For example, given a*i + b*j + c*k, adding 1 to the coefficient
3021// corresponding to the j loop would yield a*i + (b+1)*j + c*k.
3022const SCEV *DependenceInfo::addToCoefficient(const SCEV *Expr,
3023 const Loop *TargetLoop,
3024 const SCEV *Value) const {
3025 const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(Expr);
3026 if (!AddRec) // create a new addRec
3027 return SE->getAddRecExpr(Expr,
3028 Value,
3029 TargetLoop,
3030 SCEV::FlagAnyWrap); // Worst case, with no info.
3031 if (AddRec->getLoop() == TargetLoop) {
3032 const SCEV *Sum = SE->getAddExpr(AddRec->getStepRecurrence(*SE), Value);
3033 if (Sum->isZero())
3034 return AddRec->getStart();
3035 return SE->getAddRecExpr(AddRec->getStart(),
3036 Sum,
3037 AddRec->getLoop(),
3038 AddRec->getNoWrapFlags());
3039 }
3040 if (SE->isLoopInvariant(AddRec, TargetLoop))
3041 return SE->getAddRecExpr(AddRec, Value, TargetLoop, SCEV::FlagAnyWrap);
3042 return SE->getAddRecExpr(
3043 addToCoefficient(AddRec->getStart(), TargetLoop, Value),
3044 AddRec->getStepRecurrence(*SE), AddRec->getLoop(),
3045 AddRec->getNoWrapFlags());
3046}
3047
3048
3049// Review the constraints, looking for opportunities
3050// to simplify a subscript pair (Src and Dst).
3051// Return true if some simplification occurs.
3052// If the simplification isn't exact (that is, if it is conservative
3053// in terms of dependence), set consistent to false.
3054// Corresponds to Figure 5 from the paper
3055//
3056// Practical Dependence Testing
3057// Goff, Kennedy, Tseng
3058// PLDI 1991
3059bool DependenceInfo::propagate(const SCEV *&Src, const SCEV *&Dst,
3060 SmallBitVector &Loops,
3061 SmallVectorImpl<Constraint> &Constraints,
3062 bool &Consistent) {
3063 bool Result = false;
3064 for (unsigned LI : Loops.set_bits()) {
3065 LLVM_DEBUG(dbgs() << "\t Constraint[" << LI << "] is")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\t Constraint[" << LI <<
"] is"; } } while (false)
;
3066 LLVM_DEBUG(Constraints[LI].dump(dbgs()))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { Constraints[LI].dump(dbgs()); } } while (false)
;
3067 if (Constraints[LI].isDistance())
3068 Result |= propagateDistance(Src, Dst, Constraints[LI], Consistent);
3069 else if (Constraints[LI].isLine())
3070 Result |= propagateLine(Src, Dst, Constraints[LI], Consistent);
3071 else if (Constraints[LI].isPoint())
3072 Result |= propagatePoint(Src, Dst, Constraints[LI]);
3073 }
3074 return Result;
3075}
3076
3077
3078// Attempt to propagate a distance
3079// constraint into a subscript pair (Src and Dst).
3080// Return true if some simplification occurs.
3081// If the simplification isn't exact (that is, if it is conservative
3082// in terms of dependence), set consistent to false.
3083bool DependenceInfo::propagateDistance(const SCEV *&Src, const SCEV *&Dst,
3084 Constraint &CurConstraint,
3085 bool &Consistent) {
3086 const Loop *CurLoop = CurConstraint.getAssociatedLoop();
3087 LLVM_DEBUG(dbgs() << "\t\tSrc is " << *Src << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\t\tSrc is " << *Src <<
"\n"; } } while (false)
;
3088 const SCEV *A_K = findCoefficient(Src, CurLoop);
3089 if (A_K->isZero())
3090 return false;
3091 const SCEV *DA_K = SE->getMulExpr(A_K, CurConstraint.getD());
3092 Src = SE->getMinusSCEV(Src, DA_K);
3093 Src = zeroCoefficient(Src, CurLoop);
3094 LLVM_DEBUG(dbgs() << "\t\tnew Src is " << *Src << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\t\tnew Src is " << *Src <<
"\n"; } } while (false)
;
3095 LLVM_DEBUG(dbgs() << "\t\tDst is " << *Dst << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\t\tDst is " << *Dst <<
"\n"; } } while (false)
;
3096 Dst = addToCoefficient(Dst, CurLoop, SE->getNegativeSCEV(A_K));
3097 LLVM_DEBUG(dbgs() << "\t\tnew Dst is " << *Dst << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\t\tnew Dst is " << *Dst <<
"\n"; } } while (false)
;
3098 if (!findCoefficient(Dst, CurLoop)->isZero())
3099 Consistent = false;
3100 return true;
3101}
3102
3103
3104// Attempt to propagate a line
3105// constraint into a subscript pair (Src and Dst).
3106// Return true if some simplification occurs.
3107// If the simplification isn't exact (that is, if it is conservative
3108// in terms of dependence), set consistent to false.
3109bool DependenceInfo::propagateLine(const SCEV *&Src, const SCEV *&Dst,
3110 Constraint &CurConstraint,
3111 bool &Consistent) {
3112 const Loop *CurLoop = CurConstraint.getAssociatedLoop();
3113 const SCEV *A = CurConstraint.getA();
3114 const SCEV *B = CurConstraint.getB();
3115 const SCEV *C = CurConstraint.getC();
3116 LLVM_DEBUG(dbgs() << "\t\tA = " << *A << ", B = " << *B << ", C = " << *Cdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\t\tA = " << *A << ", B = "
<< *B << ", C = " << *C << "\n"; } }
while (false)
3117 << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\t\tA = " << *A << ", B = "
<< *B << ", C = " << *C << "\n"; } }
while (false)
;
3118 LLVM_DEBUG(dbgs() << "\t\tSrc = " << *Src << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\t\tSrc = " << *Src <<
"\n"; } } while (false)
;
3119 LLVM_DEBUG(dbgs() << "\t\tDst = " << *Dst << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\t\tDst = " << *Dst <<
"\n"; } } while (false)
;
3120 if (A->isZero()) {
3121 const SCEVConstant *Bconst = dyn_cast<SCEVConstant>(B);
3122 const SCEVConstant *Cconst = dyn_cast<SCEVConstant>(C);
3123 if (!Bconst || !Cconst) return false;
3124 APInt Beta = Bconst->getAPInt();
3125 APInt Charlie = Cconst->getAPInt();
3126 APInt CdivB = Charlie.sdiv(Beta);
3127 assert(Charlie.srem(Beta) == 0 && "C should be evenly divisible by B")((Charlie.srem(Beta) == 0 && "C should be evenly divisible by B"
) ? static_cast<void> (0) : __assert_fail ("Charlie.srem(Beta) == 0 && \"C should be evenly divisible by B\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/Analysis/DependenceAnalysis.cpp"
, 3127, __PRETTY_FUNCTION__))
;
3128 const SCEV *AP_K = findCoefficient(Dst, CurLoop);
3129 // Src = SE->getAddExpr(Src, SE->getMulExpr(AP_K, SE->getConstant(CdivB)));
3130 Src = SE->getMinusSCEV(Src, SE->getMulExpr(AP_K, SE->getConstant(CdivB)));
3131 Dst = zeroCoefficient(Dst, CurLoop);
3132 if (!findCoefficient(Src, CurLoop)->isZero())
3133 Consistent = false;
3134 }
3135 else if (B->isZero()) {
3136 const SCEVConstant *Aconst = dyn_cast<SCEVConstant>(A);
3137 const SCEVConstant *Cconst = dyn_cast<SCEVConstant>(C);
3138 if (!Aconst || !Cconst) return false;
3139 APInt Alpha = Aconst->getAPInt();
3140 APInt Charlie = Cconst->getAPInt();
3141 APInt CdivA = Charlie.sdiv(Alpha);
3142 assert(Charlie.srem(Alpha) == 0 && "C should be evenly divisible by A")((Charlie.srem(Alpha) == 0 && "C should be evenly divisible by A"
) ? static_cast<void> (0) : __assert_fail ("Charlie.srem(Alpha) == 0 && \"C should be evenly divisible by A\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/Analysis/DependenceAnalysis.cpp"
, 3142, __PRETTY_FUNCTION__))
;
3143 const SCEV *A_K = findCoefficient(Src, CurLoop);
3144 Src = SE->getAddExpr(Src, SE->getMulExpr(A_K, SE->getConstant(CdivA)));
3145 Src = zeroCoefficient(Src, CurLoop);
3146 if (!findCoefficient(Dst, CurLoop)->isZero())
3147 Consistent = false;
3148 }
3149 else if (isKnownPredicate(CmpInst::ICMP_EQ, A, B)) {
3150 const SCEVConstant *Aconst = dyn_cast<SCEVConstant>(A);
3151 const SCEVConstant *Cconst = dyn_cast<SCEVConstant>(C);
3152 if (!Aconst || !Cconst) return false;
3153 APInt Alpha = Aconst->getAPInt();
3154 APInt Charlie = Cconst->getAPInt();
3155 APInt CdivA = Charlie.sdiv(Alpha);
3156 assert(Charlie.srem(Alpha) == 0 && "C should be evenly divisible by A")((Charlie.srem(Alpha) == 0 && "C should be evenly divisible by A"
) ? static_cast<void> (0) : __assert_fail ("Charlie.srem(Alpha) == 0 && \"C should be evenly divisible by A\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/Analysis/DependenceAnalysis.cpp"
, 3156, __PRETTY_FUNCTION__))
;
3157 const SCEV *A_K = findCoefficient(Src, CurLoop);
3158 Src = SE->getAddExpr(Src, SE->getMulExpr(A_K, SE->getConstant(CdivA)));
3159 Src = zeroCoefficient(Src, CurLoop);
3160 Dst = addToCoefficient(Dst, CurLoop, A_K);
3161 if (!findCoefficient(Dst, CurLoop)->isZero())
3162 Consistent = false;
3163 }
3164 else {
3165 // paper is incorrect here, or perhaps just misleading
3166 const SCEV *A_K = findCoefficient(Src, CurLoop);
3167 Src = SE->getMulExpr(Src, A);
3168 Dst = SE->getMulExpr(Dst, A);
3169 Src = SE->getAddExpr(Src, SE->getMulExpr(A_K, C));
3170 Src = zeroCoefficient(Src, CurLoop);
3171 Dst = addToCoefficient(Dst, CurLoop, SE->getMulExpr(A_K, B));
3172 if (!findCoefficient(Dst, CurLoop)->isZero())
3173 Consistent = false;
3174 }
3175 LLVM_DEBUG(dbgs() << "\t\tnew Src = " << *Src << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\t\tnew Src = " << *Src <<
"\n"; } } while (false)
;
3176 LLVM_DEBUG(dbgs() << "\t\tnew Dst = " << *Dst << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\t\tnew Dst = " << *Dst <<
"\n"; } } while (false)
;
3177 return true;
3178}
3179
3180
3181// Attempt to propagate a point
3182// constraint into a subscript pair (Src and Dst).
3183// Return true if some simplification occurs.
3184bool DependenceInfo::propagatePoint(const SCEV *&Src, const SCEV *&Dst,
3185 Constraint &CurConstraint) {
3186 const Loop *CurLoop = CurConstraint.getAssociatedLoop();
3187 const SCEV *A_K = findCoefficient(Src, CurLoop);
3188 const SCEV *AP_K = findCoefficient(Dst, CurLoop);
3189 const SCEV *XA_K = SE->getMulExpr(A_K, CurConstraint.getX());
3190 const SCEV *YAP_K = SE->getMulExpr(AP_K, CurConstraint.getY());
3191 LLVM_DEBUG(dbgs() << "\t\tSrc is " << *Src << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\t\tSrc is " << *Src <<
"\n"; } } while (false)
;
3192 Src = SE->getAddExpr(Src, SE->getMinusSCEV(XA_K, YAP_K));
3193 Src = zeroCoefficient(Src, CurLoop);
3194 LLVM_DEBUG(dbgs() << "\t\tnew Src is " << *Src << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\t\tnew Src is " << *Src <<
"\n"; } } while (false)
;
3195 LLVM_DEBUG(dbgs() << "\t\tDst is " << *Dst << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\t\tDst is " << *Dst <<
"\n"; } } while (false)
;
3196 Dst = zeroCoefficient(Dst, CurLoop);
3197 LLVM_DEBUG(dbgs() << "\t\tnew Dst is " << *Dst << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\t\tnew Dst is " << *Dst <<
"\n"; } } while (false)
;
3198 return true;
3199}
3200
3201
3202// Update direction vector entry based on the current constraint.
3203void DependenceInfo::updateDirection(Dependence::DVEntry &Level,
3204 const Constraint &CurConstraint) const {
3205 LLVM_DEBUG(dbgs() << "\tUpdate direction, constraint =")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\tUpdate direction, constraint =";
} } while (false)
;
3206 LLVM_DEBUG(CurConstraint.dump(dbgs()))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { CurConstraint.dump(dbgs()); } } while (false)
;
3207 if (CurConstraint.isAny())
3208 ; // use defaults
3209 else if (CurConstraint.isDistance()) {
3210 // this one is consistent, the others aren't
3211 Level.Scalar = false;
3212 Level.Distance = CurConstraint.getD();
3213 unsigned NewDirection = Dependence::DVEntry::NONE;
3214 if (!SE->isKnownNonZero(Level.Distance)) // if may be zero
3215 NewDirection = Dependence::DVEntry::EQ;
3216 if (!SE->isKnownNonPositive(Level.Distance)) // if may be positive
3217 NewDirection |= Dependence::DVEntry::LT;
3218 if (!SE->isKnownNonNegative(Level.Distance)) // if may be negative
3219 NewDirection |= Dependence::DVEntry::GT;
3220 Level.Direction &= NewDirection;
3221 }
3222 else if (CurConstraint.isLine()) {
3223 Level.Scalar = false;
3224 Level.Distance = nullptr;
3225 // direction should be accurate
3226 }
3227 else if (CurConstraint.isPoint()) {
3228 Level.Scalar = false;
3229 Level.Distance = nullptr;
3230 unsigned NewDirection = Dependence::DVEntry::NONE;
3231 if (!isKnownPredicate(CmpInst::ICMP_NE,
3232 CurConstraint.getY(),
3233 CurConstraint.getX()))
3234 // if X may be = Y
3235 NewDirection |= Dependence::DVEntry::EQ;
3236 if (!isKnownPredicate(CmpInst::ICMP_SLE,
3237 CurConstraint.getY(),
3238 CurConstraint.getX()))
3239 // if Y may be > X
3240 NewDirection |= Dependence::DVEntry::LT;
3241 if (!isKnownPredicate(CmpInst::ICMP_SGE,
3242 CurConstraint.getY(),
3243 CurConstraint.getX()))
3244 // if Y may be < X
3245 NewDirection |= Dependence::DVEntry::GT;
3246 Level.Direction &= NewDirection;
3247 }
3248 else
3249 llvm_unreachable("constraint has unexpected kind")::llvm::llvm_unreachable_internal("constraint has unexpected kind"
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/Analysis/DependenceAnalysis.cpp"
, 3249)
;
3250}
3251
3252/// Check if we can delinearize the subscripts. If the SCEVs representing the
3253/// source and destination array references are recurrences on a nested loop,
3254/// this function flattens the nested recurrences into separate recurrences
3255/// for each loop level.
3256bool DependenceInfo::tryDelinearize(Instruction *Src, Instruction *Dst,
3257 SmallVectorImpl<Subscript> &Pair) {
3258 assert(isLoadOrStore(Src) && "instruction is not load or store")((isLoadOrStore(Src) && "instruction is not load or store"
) ? static_cast<void> (0) : __assert_fail ("isLoadOrStore(Src) && \"instruction is not load or store\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/Analysis/DependenceAnalysis.cpp"
, 3258, __PRETTY_FUNCTION__))
;
3259 assert(isLoadOrStore(Dst) && "instruction is not load or store")((isLoadOrStore(Dst) && "instruction is not load or store"
) ? static_cast<void> (0) : __assert_fail ("isLoadOrStore(Dst) && \"instruction is not load or store\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/Analysis/DependenceAnalysis.cpp"
, 3259, __PRETTY_FUNCTION__))
;
3260 Value *SrcPtr = getLoadStorePointerOperand(Src);
3261 Value *DstPtr = getLoadStorePointerOperand(Dst);
3262
3263 Loop *SrcLoop = LI->getLoopFor(Src->getParent());
3264 Loop *DstLoop = LI->getLoopFor(Dst->getParent());
3265
3266 // Below code mimics the code in Delinearization.cpp
3267 const SCEV *SrcAccessFn =
3268 SE->getSCEVAtScope(SrcPtr, SrcLoop);
3269 const SCEV *DstAccessFn =
3270 SE->getSCEVAtScope(DstPtr, DstLoop);
3271
3272 const SCEVUnknown *SrcBase =
3273 dyn_cast<SCEVUnknown>(SE->getPointerBase(SrcAccessFn));
3274 const SCEVUnknown *DstBase =
3275 dyn_cast<SCEVUnknown>(SE->getPointerBase(DstAccessFn));
3276
3277 if (!SrcBase || !DstBase || SrcBase != DstBase)
3278 return false;
3279
3280 const SCEV *ElementSize = SE->getElementSize(Src);
3281 if (ElementSize != SE->getElementSize(Dst))
3282 return false;
3283
3284 const SCEV *SrcSCEV = SE->getMinusSCEV(SrcAccessFn, SrcBase);
3285 const SCEV *DstSCEV = SE->getMinusSCEV(DstAccessFn, DstBase);
3286
3287 const SCEVAddRecExpr *SrcAR = dyn_cast<SCEVAddRecExpr>(SrcSCEV);
3288 const SCEVAddRecExpr *DstAR = dyn_cast<SCEVAddRecExpr>(DstSCEV);
3289 if (!SrcAR || !DstAR || !SrcAR->isAffine() || !DstAR->isAffine())
3290 return false;
3291
3292 // First step: collect parametric terms in both array references.
3293 SmallVector<const SCEV *, 4> Terms;
3294 SE->collectParametricTerms(SrcAR, Terms);
3295 SE->collectParametricTerms(DstAR, Terms);
3296
3297 // Second step: find subscript sizes.
3298 SmallVector<const SCEV *, 4> Sizes;
3299 SE->findArrayDimensions(Terms, Sizes, ElementSize);
3300
3301 // Third step: compute the access functions for each subscript.
3302 SmallVector<const SCEV *, 4> SrcSubscripts, DstSubscripts;
3303 SE->computeAccessFunctions(SrcAR, SrcSubscripts, Sizes);
3304 SE->computeAccessFunctions(DstAR, DstSubscripts, Sizes);
3305
3306 // Fail when there is only a subscript: that's a linearized access function.
3307 if (SrcSubscripts.size() < 2 || DstSubscripts.size() < 2 ||
3308 SrcSubscripts.size() != DstSubscripts.size())
3309 return false;
3310
3311 int size = SrcSubscripts.size();
3312
3313 // Statically check that the array bounds are in-range. The first subscript we
3314 // don't have a size for and it cannot overflow into another subscript, so is
3315 // always safe. The others need to be 0 <= subscript[i] < bound, for both src
3316 // and dst.
3317 // FIXME: It may be better to record these sizes and add them as constraints
3318 // to the dependency checks.
3319 for (int i = 1; i < size; ++i) {
3320 if (!isKnownNonNegative(SrcSubscripts[i], SrcPtr))
3321 return false;
3322
3323 if (!isKnownLessThan(SrcSubscripts[i], Sizes[i - 1]))
3324 return false;
3325
3326 if (!isKnownNonNegative(DstSubscripts[i], DstPtr))
3327 return false;
3328
3329 if (!isKnownLessThan(DstSubscripts[i], Sizes[i - 1]))
3330 return false;
3331 }
3332
3333 LLVM_DEBUG({do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { { dbgs() << "\nSrcSubscripts: "; for (int i =
0; i < size; i++) dbgs() << *SrcSubscripts[i]; dbgs
() << "\nDstSubscripts: "; for (int i = 0; i < size;
i++) dbgs() << *DstSubscripts[i]; }; } } while (false)
3334 dbgs() << "\nSrcSubscripts: ";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { { dbgs() << "\nSrcSubscripts: "; for (int i =
0; i < size; i++) dbgs() << *SrcSubscripts[i]; dbgs
() << "\nDstSubscripts: "; for (int i = 0; i < size;
i++) dbgs() << *DstSubscripts[i]; }; } } while (false)
3335 for (int i = 0; i < size; i++)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { { dbgs() << "\nSrcSubscripts: "; for (int i =
0; i < size; i++) dbgs() << *SrcSubscripts[i]; dbgs
() << "\nDstSubscripts: "; for (int i = 0; i < size;
i++) dbgs() << *DstSubscripts[i]; }; } } while (false)
3336 dbgs() << *SrcSubscripts[i];do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { { dbgs() << "\nSrcSubscripts: "; for (int i =
0; i < size; i++) dbgs() << *SrcSubscripts[i]; dbgs
() << "\nDstSubscripts: "; for (int i = 0; i < size;
i++) dbgs() << *DstSubscripts[i]; }; } } while (false)
3337 dbgs() << "\nDstSubscripts: ";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { { dbgs() << "\nSrcSubscripts: "; for (int i =
0; i < size; i++) dbgs() << *SrcSubscripts[i]; dbgs
() << "\nDstSubscripts: "; for (int i = 0; i < size;
i++) dbgs() << *DstSubscripts[i]; }; } } while (false)
3338 for (int i = 0; i < size; i++)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { { dbgs() << "\nSrcSubscripts: "; for (int i =
0; i < size; i++) dbgs() << *SrcSubscripts[i]; dbgs
() << "\nDstSubscripts: "; for (int i = 0; i < size;
i++) dbgs() << *DstSubscripts[i]; }; } } while (false)
3339 dbgs() << *DstSubscripts[i];do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { { dbgs() << "\nSrcSubscripts: "; for (int i =
0; i < size; i++) dbgs() << *SrcSubscripts[i]; dbgs
() << "\nDstSubscripts: "; for (int i = 0; i < size;
i++) dbgs() << *DstSubscripts[i]; }; } } while (false)
3340 })do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { { dbgs() << "\nSrcSubscripts: "; for (int i =
0; i < size; i++) dbgs() << *SrcSubscripts[i]; dbgs
() << "\nDstSubscripts: "; for (int i = 0; i < size;
i++) dbgs() << *DstSubscripts[i]; }; } } while (false)
;
3341
3342 // The delinearization transforms a single-subscript MIV dependence test into
3343 // a multi-subscript SIV dependence test that is easier to compute. So we
3344 // resize Pair to contain as many pairs of subscripts as the delinearization
3345 // has found, and then initialize the pairs following the delinearization.
3346 Pair.resize(size);
3347 for (int i = 0; i < size; ++i) {
3348 Pair[i].Src = SrcSubscripts[i];
3349 Pair[i].Dst = DstSubscripts[i];
3350 unifySubscriptType(&Pair[i]);
3351 }
3352
3353 return true;
3354}
3355
3356//===----------------------------------------------------------------------===//
3357
3358#ifndef NDEBUG
3359// For debugging purposes, dump a small bit vector to dbgs().
3360static void dumpSmallBitVector(SmallBitVector &BV) {
3361 dbgs() << "{";
3362 for (unsigned VI : BV.set_bits()) {
3363 dbgs() << VI;
3364 if (BV.find_next(VI) >= 0)
3365 dbgs() << ' ';
3366 }
3367 dbgs() << "}\n";
3368}
3369#endif
3370
3371bool DependenceInfo::invalidate(Function &F, const PreservedAnalyses &PA,
3372 FunctionAnalysisManager::Invalidator &Inv) {
3373 // Check if the analysis itself has been invalidated.
3374 auto PAC = PA.getChecker<DependenceAnalysis>();
3375 if (!PAC.preserved() && !PAC.preservedSet<AllAnalysesOn<Function>>())
3376 return true;
3377
3378 // Check transitive dependencies.
3379 return Inv.invalidate<AAManager>(F, PA) ||
3380 Inv.invalidate<ScalarEvolutionAnalysis>(F, PA) ||
3381 Inv.invalidate<LoopAnalysis>(F, PA);
3382}
3383
3384// depends -
3385// Returns NULL if there is no dependence.
3386// Otherwise, return a Dependence with as many details as possible.
3387// Corresponds to Section 3.1 in the paper
3388//
3389// Practical Dependence Testing
3390// Goff, Kennedy, Tseng
3391// PLDI 1991
3392//
3393// Care is required to keep the routine below, getSplitIteration(),
3394// up to date with respect to this routine.
3395std::unique_ptr<Dependence>
3396DependenceInfo::depends(Instruction *Src, Instruction *Dst,
3397 bool PossiblyLoopIndependent) {
3398 if (Src == Dst)
3399 PossiblyLoopIndependent = false;
3400
3401 if ((!Src->mayReadFromMemory() && !Src->mayWriteToMemory()) ||
3402 (!Dst->mayReadFromMemory() && !Dst->mayWriteToMemory()))
3403 // if both instructions don't reference memory, there's no dependence
3404 return nullptr;
3405
3406 if (!isLoadOrStore(Src) || !isLoadOrStore(Dst)) {
3407 // can only analyze simple loads and stores, i.e., no calls, invokes, etc.
3408 LLVM_DEBUG(dbgs() << "can only handle simple loads and stores\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "can only handle simple loads and stores\n"
; } } while (false)
;
3409 return make_unique<Dependence>(Src, Dst);
3410 }
3411
3412 assert(isLoadOrStore(Src) && "instruction is not load or store")((isLoadOrStore(Src) && "instruction is not load or store"
) ? static_cast<void> (0) : __assert_fail ("isLoadOrStore(Src) && \"instruction is not load or store\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/Analysis/DependenceAnalysis.cpp"
, 3412, __PRETTY_FUNCTION__))
;
3413 assert(isLoadOrStore(Dst) && "instruction is not load or store")((isLoadOrStore(Dst) && "instruction is not load or store"
) ? static_cast<void> (0) : __assert_fail ("isLoadOrStore(Dst) && \"instruction is not load or store\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/Analysis/DependenceAnalysis.cpp"
, 3413, __PRETTY_FUNCTION__))
;
3414 Value *SrcPtr = getLoadStorePointerOperand(Src);
3415 Value *DstPtr = getLoadStorePointerOperand(Dst);
3416
3417 switch (underlyingObjectsAlias(AA, F->getParent()->getDataLayout(),
3418 MemoryLocation::get(Dst),
3419 MemoryLocation::get(Src))) {
3420 case MayAlias:
3421 case PartialAlias:
3422 // cannot analyse objects if we don't understand their aliasing.
3423 LLVM_DEBUG(dbgs() << "can't analyze may or partial alias\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "can't analyze may or partial alias\n"
; } } while (false)
;
3424 return make_unique<Dependence>(Src, Dst);
3425 case NoAlias:
3426 // If the objects noalias, they are distinct, accesses are independent.
3427 LLVM_DEBUG(dbgs() << "no alias\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "no alias\n"; } } while (false)
;
3428 return nullptr;
3429 case MustAlias:
3430 break; // The underlying objects alias; test accesses for dependence.
3431 }
3432
3433 // establish loop nesting levels
3434 establishNestingLevels(Src, Dst);
3435 LLVM_DEBUG(dbgs() << " common nesting levels = " << CommonLevels << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << " common nesting levels = " <<
CommonLevels << "\n"; } } while (false)
;
3436 LLVM_DEBUG(dbgs() << " maximum nesting levels = " << MaxLevels << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << " maximum nesting levels = " <<
MaxLevels << "\n"; } } while (false)
;
3437
3438 FullDependence Result(Src, Dst, PossiblyLoopIndependent, CommonLevels);
3439 ++TotalArrayPairs;
3440
3441 unsigned Pairs = 1;
3442 SmallVector<Subscript, 2> Pair(Pairs);
3443 const SCEV *SrcSCEV = SE->getSCEV(SrcPtr);
3444 const SCEV *DstSCEV = SE->getSCEV(DstPtr);
3445 LLVM_DEBUG(dbgs() << " SrcSCEV = " << *SrcSCEV << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << " SrcSCEV = " << *SrcSCEV <<
"\n"; } } while (false)
;
3446 LLVM_DEBUG(dbgs() << " DstSCEV = " << *DstSCEV << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << " DstSCEV = " << *DstSCEV <<
"\n"; } } while (false)
;
3447 Pair[0].Src = SrcSCEV;
3448 Pair[0].Dst = DstSCEV;
3449
3450 if (Delinearize) {
3451 if (tryDelinearize(Src, Dst, Pair)) {
3452 LLVM_DEBUG(dbgs() << " delinearized\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << " delinearized\n"; } } while (false
)
;
3453 Pairs = Pair.size();
3454 }
3455 }
3456
3457 for (unsigned P = 0; P < Pairs; ++P) {
3458 Pair[P].Loops.resize(MaxLevels + 1);
3459 Pair[P].GroupLoops.resize(MaxLevels + 1);
3460 Pair[P].Group.resize(Pairs);
3461 removeMatchingExtensions(&Pair[P]);
3462 Pair[P].Classification =
3463 classifyPair(Pair[P].Src, LI->getLoopFor(Src->getParent()),
3464 Pair[P].Dst, LI->getLoopFor(Dst->getParent()),
3465 Pair[P].Loops);
3466 Pair[P].GroupLoops = Pair[P].Loops;
3467 Pair[P].Group.set(P);
3468 LLVM_DEBUG(dbgs() << " subscript " << P << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << " subscript " << P <<
"\n"; } } while (false)
;
3469 LLVM_DEBUG(dbgs() << "\tsrc = " << *Pair[P].Src << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\tsrc = " << *Pair[P].Src <<
"\n"; } } while (false)
;
3470 LLVM_DEBUG(dbgs() << "\tdst = " << *Pair[P].Dst << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\tdst = " << *Pair[P].Dst <<
"\n"; } } while (false)
;
3471 LLVM_DEBUG(dbgs() << "\tclass = " << Pair[P].Classification << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\tclass = " << Pair[P].Classification
<< "\n"; } } while (false)
;
3472 LLVM_DEBUG(dbgs() << "\tloops = ")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\tloops = "; } } while (false)
;
3473 LLVM_DEBUG(dumpSmallBitVector(Pair[P].Loops))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dumpSmallBitVector(Pair[P].Loops); } } while (false
)
;
3474 }
3475
3476 SmallBitVector Separable(Pairs);
3477 SmallBitVector Coupled(Pairs);
3478
3479 // Partition subscripts into separable and minimally-coupled groups
3480 // Algorithm in paper is algorithmically better;
3481 // this may be faster in practice. Check someday.
3482 //
3483 // Here's an example of how it works. Consider this code:
3484 //
3485 // for (i = ...) {
3486 // for (j = ...) {
3487 // for (k = ...) {
3488 // for (l = ...) {
3489 // for (m = ...) {
3490 // A[i][j][k][m] = ...;
3491 // ... = A[0][j][l][i + j];
3492 // }
3493 // }
3494 // }
3495 // }
3496 // }
3497 //
3498 // There are 4 subscripts here:
3499 // 0 [i] and [0]
3500 // 1 [j] and [j]
3501 // 2 [k] and [l]
3502 // 3 [m] and [i + j]
3503 //
3504 // We've already classified each subscript pair as ZIV, SIV, etc.,
3505 // and collected all the loops mentioned by pair P in Pair[P].Loops.
3506 // In addition, we've initialized Pair[P].GroupLoops to Pair[P].Loops
3507 // and set Pair[P].Group = {P}.
3508 //
3509 // Src Dst Classification Loops GroupLoops Group
3510 // 0 [i] [0] SIV {1} {1} {0}
3511 // 1 [j] [j] SIV {2} {2} {1}
3512 // 2 [k] [l] RDIV {3,4} {3,4} {2}
3513 // 3 [m] [i + j] MIV {1,2,5} {1,2,5} {3}
3514 //
3515 // For each subscript SI 0 .. 3, we consider each remaining subscript, SJ.
3516 // So, 0 is compared against 1, 2, and 3; 1 is compared against 2 and 3, etc.
3517 //
3518 // We begin by comparing 0 and 1. The intersection of the GroupLoops is empty.
3519 // Next, 0 and 2. Again, the intersection of their GroupLoops is empty.
3520 // Next 0 and 3. The intersection of their GroupLoop = {1}, not empty,
3521 // so Pair[3].Group = {0,3} and Done = false (that is, 0 will not be added
3522 // to either Separable or Coupled).
3523 //
3524 // Next, we consider 1 and 2. The intersection of the GroupLoops is empty.
3525 // Next, 1 and 3. The intersection of their GroupLoops = {2}, not empty,
3526 // so Pair[3].Group = {0, 1, 3} and Done = false.
3527 //
3528 // Next, we compare 2 against 3. The intersection of the GroupLoops is empty.
3529 // Since Done remains true, we add 2 to the set of Separable pairs.
3530 //
3531 // Finally, we consider 3. There's nothing to compare it with,
3532 // so Done remains true and we add it to the Coupled set.
3533 // Pair[3].Group = {0, 1, 3} and GroupLoops = {1, 2, 5}.
3534 //
3535 // In the end, we've got 1 separable subscript and 1 coupled group.
3536 for (unsigned SI = 0; SI < Pairs; ++SI) {
3537 if (Pair[SI].Classification == Subscript::NonLinear) {
3538 // ignore these, but collect loops for later
3539 ++NonlinearSubscriptPairs;
3540 collectCommonLoops(Pair[SI].Src,
3541 LI->getLoopFor(Src->getParent()),
3542 Pair[SI].Loops);
3543 collectCommonLoops(Pair[SI].Dst,
3544 LI->getLoopFor(Dst->getParent()),
3545 Pair[SI].Loops);
3546 Result.Consistent = false;
3547 } else if (Pair[SI].Classification == Subscript::ZIV) {
3548 // always separable
3549 Separable.set(SI);
3550 }
3551 else {
3552 // SIV, RDIV, or MIV, so check for coupled group
3553 bool Done = true;
3554 for (unsigned SJ = SI + 1; SJ < Pairs; ++SJ) {
3555 SmallBitVector Intersection = Pair[SI].GroupLoops;
3556 Intersection &= Pair[SJ].GroupLoops;
3557 if (Intersection.any()) {
3558 // accumulate set of all the loops in group
3559 Pair[SJ].GroupLoops |= Pair[SI].GroupLoops;
3560 // accumulate set of all subscripts in group
3561 Pair[SJ].Group |= Pair[SI].Group;
3562 Done = false;
3563 }
3564 }
3565 if (Done) {
3566 if (Pair[SI].Group.count() == 1) {
3567 Separable.set(SI);
3568 ++SeparableSubscriptPairs;
3569 }
3570 else {
3571 Coupled.set(SI);
3572 ++CoupledSubscriptPairs;
3573 }
3574 }
3575 }
3576 }
3577
3578 LLVM_DEBUG(dbgs() << " Separable = ")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << " Separable = "; } } while (false
)
;
3579 LLVM_DEBUG(dumpSmallBitVector(Separable))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dumpSmallBitVector(Separable); } } while (false)
;
3580 LLVM_DEBUG(dbgs() << " Coupled = ")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << " Coupled = "; } } while (false)
;
3581 LLVM_DEBUG(dumpSmallBitVector(Coupled))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dumpSmallBitVector(Coupled); } } while (false)
;
3582
3583 Constraint NewConstraint;
3584 NewConstraint.setAny(SE);
3585
3586 // test separable subscripts
3587 for (unsigned SI : Separable.set_bits()) {
3588 LLVM_DEBUG(dbgs() << "testing subscript " << SI)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "testing subscript " << SI; }
} while (false)
;
3589 switch (Pair[SI].Classification) {
3590 case Subscript::ZIV:
3591 LLVM_DEBUG(dbgs() << ", ZIV\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << ", ZIV\n"; } } while (false)
;
3592 if (testZIV(Pair[SI].Src, Pair[SI].Dst, Result))
3593 return nullptr;
3594 break;
3595 case Subscript::SIV: {
3596 LLVM_DEBUG(dbgs() << ", SIV\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << ", SIV\n"; } } while (false)
;
3597 unsigned Level;
3598 const SCEV *SplitIter = nullptr;
3599 if (testSIV(Pair[SI].Src, Pair[SI].Dst, Level, Result, NewConstraint,
3600 SplitIter))
3601 return nullptr;
3602 break;
3603 }
3604 case Subscript::RDIV:
3605 LLVM_DEBUG(dbgs() << ", RDIV\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << ", RDIV\n"; } } while (false)
;
3606 if (testRDIV(Pair[SI].Src, Pair[SI].Dst, Result))
3607 return nullptr;
3608 break;
3609 case Subscript::MIV:
3610 LLVM_DEBUG(dbgs() << ", MIV\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << ", MIV\n"; } } while (false)
;
3611 if (testMIV(Pair[SI].Src, Pair[SI].Dst, Pair[SI].Loops, Result))
3612 return nullptr;
3613 break;
3614 default:
3615 llvm_unreachable("subscript has unexpected classification")::llvm::llvm_unreachable_internal("subscript has unexpected classification"
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/Analysis/DependenceAnalysis.cpp"
, 3615)
;
3616 }
3617 }
3618
3619 if (Coupled.count()) {
3620 // test coupled subscript groups
3621 LLVM_DEBUG(dbgs() << "starting on coupled subscripts\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "starting on coupled subscripts\n";
} } while (false)
;
3622 LLVM_DEBUG(dbgs() << "MaxLevels + 1 = " << MaxLevels + 1 << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "MaxLevels + 1 = " << MaxLevels
+ 1 << "\n"; } } while (false)
;
3623 SmallVector<Constraint, 4> Constraints(MaxLevels + 1);
3624 for (unsigned II = 0; II <= MaxLevels; ++II)
3625 Constraints[II].setAny(SE);
3626 for (unsigned SI : Coupled.set_bits()) {
3627 LLVM_DEBUG(dbgs() << "testing subscript group " << SI << " { ")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "testing subscript group " <<
SI << " { "; } } while (false)
;
3628 SmallBitVector Group(Pair[SI].Group);
3629 SmallBitVector Sivs(Pairs);
3630 SmallBitVector Mivs(Pairs);
3631 SmallBitVector ConstrainedLevels(MaxLevels + 1);
3632 SmallVector<Subscript *, 4> PairsInGroup;
3633 for (unsigned SJ : Group.set_bits()) {
3634 LLVM_DEBUG(dbgs() << SJ << " ")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << SJ << " "; } } while (false)
;
3635 if (Pair[SJ].Classification == Subscript::SIV)
3636 Sivs.set(SJ);
3637 else
3638 Mivs.set(SJ);
3639 PairsInGroup.push_back(&Pair[SJ]);
3640 }
3641 unifySubscriptType(PairsInGroup);
3642 LLVM_DEBUG(dbgs() << "}\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "}\n"; } } while (false)
;
3643 while (Sivs.any()) {
3644 bool Changed = false;
3645 for (unsigned SJ : Sivs.set_bits()) {
3646 LLVM_DEBUG(dbgs() << "testing subscript " << SJ << ", SIV\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "testing subscript " << SJ <<
", SIV\n"; } } while (false)
;
3647 // SJ is an SIV subscript that's part of the current coupled group
3648 unsigned Level;
3649 const SCEV *SplitIter = nullptr;
3650 LLVM_DEBUG(dbgs() << "SIV\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "SIV\n"; } } while (false)
;
3651 if (testSIV(Pair[SJ].Src, Pair[SJ].Dst, Level, Result, NewConstraint,
3652 SplitIter))
3653 return nullptr;
3654 ConstrainedLevels.set(Level);
3655 if (intersectConstraints(&Constraints[Level], &NewConstraint)) {
3656 if (Constraints[Level].isEmpty()) {
3657 ++DeltaIndependence;
3658 return nullptr;
3659 }
3660 Changed = true;
3661 }
3662 Sivs.reset(SJ);
3663 }
3664 if (Changed) {
3665 // propagate, possibly creating new SIVs and ZIVs
3666 LLVM_DEBUG(dbgs() << " propagating\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << " propagating\n"; } } while (false
)
;
3667 LLVM_DEBUG(dbgs() << "\tMivs = ")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\tMivs = "; } } while (false)
;
3668 LLVM_DEBUG(dumpSmallBitVector(Mivs))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dumpSmallBitVector(Mivs); } } while (false)
;
3669 for (unsigned SJ : Mivs.set_bits()) {
3670 // SJ is an MIV subscript that's part of the current coupled group
3671 LLVM_DEBUG(dbgs() << "\tSJ = " << SJ << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\tSJ = " << SJ << "\n"
; } } while (false)
;
3672 if (propagate(Pair[SJ].Src, Pair[SJ].Dst, Pair[SJ].Loops,
3673 Constraints, Result.Consistent)) {
3674 LLVM_DEBUG(dbgs() << "\t Changed\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "\t Changed\n"; } } while (false
)
;
3675 ++DeltaPropagations;
3676 Pair[SJ].Classification =
3677 classifyPair(Pair[SJ].Src, LI->getLoopFor(Src->getParent()),
3678 Pair[SJ].Dst, LI->getLoopFor(Dst->getParent()),
3679 Pair[SJ].Loops);
3680 switch (Pair[SJ].Classification) {
3681 case Subscript::ZIV:
3682 LLVM_DEBUG(dbgs() << "ZIV\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "ZIV\n"; } } while (false)
;
3683 if (testZIV(Pair[SJ].Src, Pair[SJ].Dst, Result))
3684 return nullptr;
3685 Mivs.reset(SJ);
3686 break;
3687 case Subscript::SIV:
3688 Sivs.set(SJ);
3689 Mivs.reset(SJ);
3690 break;
3691 case Subscript::RDIV:
3692 case Subscript::MIV:
3693 break;
3694 default:
3695 llvm_unreachable("bad subscript classification")::llvm::llvm_unreachable_internal("bad subscript classification"
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/Analysis/DependenceAnalysis.cpp"
, 3695)
;
3696 }
3697 }
3698 }
3699 }
3700 }
3701
3702 // test & propagate remaining RDIVs
3703 for (unsigned SJ : Mivs.set_bits()) {
3704 if (Pair[SJ].Classification == Subscript::RDIV) {
3705 LLVM_DEBUG(dbgs() << "RDIV test\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "RDIV test\n"; } } while (false)
;
3706 if (testRDIV(Pair[SJ].Src, Pair[SJ].Dst, Result))
3707 return nullptr;
3708 // I don't yet understand how to propagate RDIV results
3709 Mivs.reset(SJ);
3710 }
3711 }
3712
3713 // test remaining MIVs
3714 // This code is temporary.
3715 // Better to somehow test all remaining subscripts simultaneously.
3716 for (unsigned SJ : Mivs.set_bits()) {
3717 if (Pair[SJ].Classification == Subscript::MIV) {
3718 LLVM_DEBUG(dbgs() << "MIV test\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << "MIV test\n"; } } while (false)
;
3719 if (testMIV(Pair[SJ].Src, Pair[SJ].Dst, Pair[SJ].Loops, Result))
3720 return nullptr;
3721 }
3722 else
3723 llvm_unreachable("expected only MIV subscripts at this point")::llvm::llvm_unreachable_internal("expected only MIV subscripts at this point"
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/Analysis/DependenceAnalysis.cpp"
, 3723)
;
3724 }
3725
3726 // update Result.DV from constraint vector
3727 LLVM_DEBUG(dbgs() << " updating\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << " updating\n"; } } while (false)
;
3728 for (unsigned SJ : ConstrainedLevels.set_bits()) {
3729 if (SJ > CommonLevels)
3730 break;
3731 updateDirection(Result.DV[SJ - 1], Constraints[SJ]);
3732 if (Result.DV[SJ - 1].Direction == Dependence::DVEntry::NONE)
3733 return nullptr;
3734 }
3735 }
3736 }
3737
3738 // Make sure the Scalar flags are set correctly.
3739 SmallBitVector CompleteLoops(MaxLevels + 1);
3740 for (unsigned SI = 0; SI < Pairs; ++SI)
3741 CompleteLoops |= Pair[SI].Loops;
3742 for (unsigned II = 1; II <= CommonLevels; ++II)
3743 if (CompleteLoops[II])
3744 Result.DV[II - 1].Scalar = false;
3745
3746 if (PossiblyLoopIndependent) {
3747 // Make sure the LoopIndependent flag is set correctly.
3748 // All directions must include equal, otherwise no
3749 // loop-independent dependence is possible.
3750 for (unsigned II = 1; II <= CommonLevels; ++II) {
3751 if (!(Result.getDirection(II) & Dependence::DVEntry::EQ)) {
3752 Result.LoopIndependent = false;
3753 break;
3754 }
3755 }
3756 }
3757 else {
3758 // On the other hand, if all directions are equal and there's no
3759 // loop-independent dependence possible, then no dependence exists.
3760 bool AllEqual = true;
3761 for (unsigned II = 1; II <= CommonLevels; ++II) {
3762 if (Result.getDirection(II) != Dependence::DVEntry::EQ) {
3763 AllEqual = false;
3764 break;
3765 }
3766 }
3767 if (AllEqual)
3768 return nullptr;
3769 }
3770
3771 return make_unique<FullDependence>(std::move(Result));
3772}
3773
3774
3775
3776//===----------------------------------------------------------------------===//
3777// getSplitIteration -
3778// Rather than spend rarely-used space recording the splitting iteration
3779// during the Weak-Crossing SIV test, we re-compute it on demand.
3780// The re-computation is basically a repeat of the entire dependence test,
3781// though simplified since we know that the dependence exists.
3782// It's tedious, since we must go through all propagations, etc.
3783//
3784// Care is required to keep this code up to date with respect to the routine
3785// above, depends().
3786//
3787// Generally, the dependence analyzer will be used to build
3788// a dependence graph for a function (basically a map from instructions
3789// to dependences). Looking for cycles in the graph shows us loops
3790// that cannot be trivially vectorized/parallelized.
3791//
3792// We can try to improve the situation by examining all the dependences
3793// that make up the cycle, looking for ones we can break.
3794// Sometimes, peeling the first or last iteration of a loop will break
3795// dependences, and we've got flags for those possibilities.
3796// Sometimes, splitting a loop at some other iteration will do the trick,
3797// and we've got a flag for that case. Rather than waste the space to
3798// record the exact iteration (since we rarely know), we provide
3799// a method that calculates the iteration. It's a drag that it must work
3800// from scratch, but wonderful in that it's possible.
3801//
3802// Here's an example:
3803//
3804// for (i = 0; i < 10; i++)
3805// A[i] = ...
3806// ... = A[11 - i]
3807//
3808// There's a loop-carried flow dependence from the store to the load,
3809// found by the weak-crossing SIV test. The dependence will have a flag,
3810// indicating that the dependence can be broken by splitting the loop.
3811// Calling getSplitIteration will return 5.
3812// Splitting the loop breaks the dependence, like so:
3813//
3814// for (i = 0; i <= 5; i++)
3815// A[i] = ...
3816// ... = A[11 - i]
3817// for (i = 6; i < 10; i++)
3818// A[i] = ...
3819// ... = A[11 - i]
3820//
3821// breaks the dependence and allows us to vectorize/parallelize
3822// both loops.
3823const SCEV *DependenceInfo::getSplitIteration(const Dependence &Dep,
3824 unsigned SplitLevel) {
3825 assert(Dep.isSplitable(SplitLevel) &&((Dep.isSplitable(SplitLevel) && "Dep should be splitable at SplitLevel"
) ? static_cast<void> (0) : __assert_fail ("Dep.isSplitable(SplitLevel) && \"Dep should be splitable at SplitLevel\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/Analysis/DependenceAnalysis.cpp"
, 3826, __PRETTY_FUNCTION__))
1
Assuming the condition is true
2
'?' condition is true
3826 "Dep should be splitable at SplitLevel")((Dep.isSplitable(SplitLevel) && "Dep should be splitable at SplitLevel"
) ? static_cast<void> (0) : __assert_fail ("Dep.isSplitable(SplitLevel) && \"Dep should be splitable at SplitLevel\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/Analysis/DependenceAnalysis.cpp"
, 3826, __PRETTY_FUNCTION__))
;
3827 Instruction *Src = Dep.getSrc();
3828 Instruction *Dst = Dep.getDst();
3829 assert(Src->mayReadFromMemory() || Src->mayWriteToMemory())((Src->mayReadFromMemory() || Src->mayWriteToMemory()) ?
static_cast<void> (0) : __assert_fail ("Src->mayReadFromMemory() || Src->mayWriteToMemory()"
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/Analysis/DependenceAnalysis.cpp"
, 3829, __PRETTY_FUNCTION__))
;
3
Assuming the condition is true
3830 assert(Dst->mayReadFromMemory() || Dst->mayWriteToMemory())((Dst->mayReadFromMemory() || Dst->mayWriteToMemory()) ?
static_cast<void> (0) : __assert_fail ("Dst->mayReadFromMemory() || Dst->mayWriteToMemory()"
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/Analysis/DependenceAnalysis.cpp"
, 3830, __PRETTY_FUNCTION__))
;
4
Assuming the condition is false
5
Assuming the condition is true
6
'?' condition is true
3831 assert(isLoadOrStore(Src))((isLoadOrStore(Src)) ? static_cast<void> (0) : __assert_fail
("isLoadOrStore(Src)", "/build/llvm-toolchain-snapshot-9~svn362543/lib/Analysis/DependenceAnalysis.cpp"
, 3831, __PRETTY_FUNCTION__))
;
7
'?' condition is true
3832 assert(isLoadOrStore(Dst))((isLoadOrStore(Dst)) ? static_cast<void> (0) : __assert_fail
("isLoadOrStore(Dst)", "/build/llvm-toolchain-snapshot-9~svn362543/lib/Analysis/DependenceAnalysis.cpp"
, 3832, __PRETTY_FUNCTION__))
;
8
'?' condition is true
3833 Value *SrcPtr = getLoadStorePointerOperand(Src);
3834 Value *DstPtr = getLoadStorePointerOperand(Dst);
3835 assert(underlyingObjectsAlias(AA, F->getParent()->getDataLayout(),((underlyingObjectsAlias(AA, F->getParent()->getDataLayout
(), MemoryLocation::get(Dst), MemoryLocation::get(Src)) == MustAlias
) ? static_cast<void> (0) : __assert_fail ("underlyingObjectsAlias(AA, F->getParent()->getDataLayout(), MemoryLocation::get(Dst), MemoryLocation::get(Src)) == MustAlias"
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/Analysis/DependenceAnalysis.cpp"
, 3837, __PRETTY_FUNCTION__))
9
'?' condition is true
3836 MemoryLocation::get(Dst),((underlyingObjectsAlias(AA, F->getParent()->getDataLayout
(), MemoryLocation::get(Dst), MemoryLocation::get(Src)) == MustAlias
) ? static_cast<void> (0) : __assert_fail ("underlyingObjectsAlias(AA, F->getParent()->getDataLayout(), MemoryLocation::get(Dst), MemoryLocation::get(Src)) == MustAlias"
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/Analysis/DependenceAnalysis.cpp"
, 3837, __PRETTY_FUNCTION__))
3837 MemoryLocation::get(Src)) == MustAlias)((underlyingObjectsAlias(AA, F->getParent()->getDataLayout
(), MemoryLocation::get(Dst), MemoryLocation::get(Src)) == MustAlias
) ? static_cast<void> (0) : __assert_fail ("underlyingObjectsAlias(AA, F->getParent()->getDataLayout(), MemoryLocation::get(Dst), MemoryLocation::get(Src)) == MustAlias"
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/Analysis/DependenceAnalysis.cpp"
, 3837, __PRETTY_FUNCTION__))
;
3838
3839 // establish loop nesting levels
3840 establishNestingLevels(Src, Dst);
3841
3842 FullDependence Result(Src, Dst, false, CommonLevels);
3843
3844 unsigned Pairs = 1;
3845 SmallVector<Subscript, 2> Pair(Pairs);
3846 const SCEV *SrcSCEV = SE->getSCEV(SrcPtr);
3847 const SCEV *DstSCEV = SE->getSCEV(DstPtr);
3848 Pair[0].Src = SrcSCEV;
3849 Pair[0].Dst = DstSCEV;
3850
3851 if (Delinearize) {
10
Assuming the condition is false
11
Taking false branch
3852 if (tryDelinearize(Src, Dst, Pair)) {
3853 LLVM_DEBUG(dbgs() << " delinearized\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("da")) { dbgs() << " delinearized\n"; } } while (false
)
;
3854 Pairs = Pair.size();
3855 }
3856 }
3857
3858 for (unsigned P = 0; P < Pairs; ++P) {
12
Loop condition is true. Entering loop body
3859 Pair[P].Loops.resize(MaxLevels + 1);
3860 Pair[P].GroupLoops.resize(MaxLevels + 1);
3861 Pair[P].Group.resize(Pairs);
3862 removeMatchingExtensions(&Pair[P]);
3863 Pair[P].Classification =
3864 classifyPair(Pair[P].Src, LI->getLoopFor(Src->getParent()),
13
Calling 'DependenceInfo::classifyPair'
3865 Pair[P].Dst, LI->getLoopFor(Dst->getParent()),
3866 Pair[P].Loops);
3867 Pair[P].GroupLoops = Pair[P].Loops;
3868 Pair[P].Group.set(P);
3869 }
3870
3871 SmallBitVector Separable(Pairs);
3872 SmallBitVector Coupled(Pairs);
3873
3874 // partition subscripts into separable and minimally-coupled groups
3875 for (unsigned SI = 0; SI < Pairs; ++SI) {
3876 if (Pair[SI].Classification == Subscript::NonLinear) {
3877 // ignore these, but collect loops for later
3878 collectCommonLoops(Pair[SI].Src,
3879 LI->getLoopFor(Src->getParent()),
3880 Pair[SI].Loops);
3881 collectCommonLoops(Pair[SI].Dst,
3882 LI->getLoopFor(Dst->getParent()),
3883 Pair[SI].Loops);
3884 Result.Consistent = false;
3885 }
3886 else if (Pair[SI].Classification == Subscript::ZIV)
3887 Separable.set(SI);
3888 else {
3889 // SIV, RDIV, or MIV, so check for coupled group
3890 bool Done = true;
3891 for (unsigned SJ = SI + 1; SJ < Pairs; ++SJ) {
3892 SmallBitVector Intersection = Pair[SI].GroupLoops;
3893 Intersection &= Pair[SJ].GroupLoops;
3894 if (Intersection.any()) {
3895 // accumulate set of all the loops in group
3896 Pair[SJ].GroupLoops |= Pair[SI].GroupLoops;
3897 // accumulate set of all subscripts in group
3898 Pair[SJ].Group |= Pair[SI].Group;
3899 Done = false;
3900 }
3901 }
3902 if (Done) {
3903 if (Pair[SI].Group.count() == 1)
3904 Separable.set(SI);
3905 else
3906 Coupled.set(SI);
3907 }
3908 }
3909 }
3910
3911 Constraint NewConstraint;
3912 NewConstraint.setAny(SE);
3913
3914 // test separable subscripts
3915 for (unsigned SI : Separable.set_bits()) {
3916 switch (Pair[SI].Classification) {
3917 case Subscript::SIV: {
3918 unsigned Level;
3919 const SCEV *SplitIter = nullptr;
3920 (void) testSIV(Pair[SI].Src, Pair[SI].Dst, Level,
3921 Result, NewConstraint, SplitIter);
3922 if (Level == SplitLevel) {
3923 assert(SplitIter != nullptr)((SplitIter != nullptr) ? static_cast<void> (0) : __assert_fail
("SplitIter != nullptr", "/build/llvm-toolchain-snapshot-9~svn362543/lib/Analysis/DependenceAnalysis.cpp"
, 3923, __PRETTY_FUNCTION__))
;
3924 return SplitIter;
3925 }
3926 break;
3927 }
3928 case Subscript::ZIV:
3929 case Subscript::RDIV:
3930 case Subscript::MIV:
3931 break;
3932 default:
3933 llvm_unreachable("subscript has unexpected classification")::llvm::llvm_unreachable_internal("subscript has unexpected classification"
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/Analysis/DependenceAnalysis.cpp"
, 3933)
;
3934 }
3935 }
3936
3937 if (Coupled.count()) {
3938 // test coupled subscript groups
3939 SmallVector<Constraint, 4> Constraints(MaxLevels + 1);
3940 for (unsigned II = 0; II <= MaxLevels; ++II)
3941 Constraints[II].setAny(SE);
3942 for (unsigned SI : Coupled.set_bits()) {
3943 SmallBitVector Group(Pair[SI].Group);
3944 SmallBitVector Sivs(Pairs);
3945 SmallBitVector Mivs(Pairs);
3946 SmallBitVector ConstrainedLevels(MaxLevels + 1);
3947 for (unsigned SJ : Group.set_bits()) {
3948 if (Pair[SJ].Classification == Subscript::SIV)
3949 Sivs.set(SJ);
3950 else
3951 Mivs.set(SJ);
3952 }
3953 while (Sivs.any()) {
3954 bool Changed = false;
3955 for (unsigned SJ : Sivs.set_bits()) {
3956 // SJ is an SIV subscript that's part of the current coupled group
3957 unsigned Level;
3958 const SCEV *SplitIter = nullptr;
3959 (void) testSIV(Pair[SJ].Src, Pair[SJ].Dst, Level,
3960 Result, NewConstraint, SplitIter);
3961 if (Level == SplitLevel && SplitIter)
3962 return SplitIter;
3963 ConstrainedLevels.set(Level);
3964 if (intersectConstraints(&Constraints[Level], &NewConstraint))
3965 Changed = true;
3966 Sivs.reset(SJ);
3967 }
3968 if (Changed) {
3969 // propagate, possibly creating new SIVs and ZIVs
3970 for (unsigned SJ : Mivs.set_bits()) {
3971 // SJ is an MIV subscript that's part of the current coupled group
3972 if (propagate(Pair[SJ].Src, Pair[SJ].Dst,
3973 Pair[SJ].Loops, Constraints, Result.Consistent)) {
3974 Pair[SJ].Classification =
3975 classifyPair(Pair[SJ].Src, LI->getLoopFor(Src->getParent()),
3976 Pair[SJ].Dst, LI->getLoopFor(Dst->getParent()),
3977 Pair[SJ].Loops);
3978 switch (Pair[SJ].Classification) {
3979 case Subscript::ZIV:
3980 Mivs.reset(SJ);
3981 break;
3982 case Subscript::SIV:
3983 Sivs.set(SJ);
3984 Mivs.reset(SJ);
3985 break;
3986 case Subscript::RDIV:
3987 case Subscript::MIV:
3988 break;
3989 default:
3990 llvm_unreachable("bad subscript classification")::llvm::llvm_unreachable_internal("bad subscript classification"
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/Analysis/DependenceAnalysis.cpp"
, 3990)
;
3991 }
3992 }
3993 }
3994 }
3995 }
3996 }
3997 }
3998 llvm_unreachable("somehow reached end of routine")::llvm::llvm_unreachable_internal("somehow reached end of routine"
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/Analysis/DependenceAnalysis.cpp"
, 3998)
;
3999 return nullptr;
4000}

/build/llvm-toolchain-snapshot-9~svn362543/include/llvm/ADT/SmallBitVector.h

1//===- llvm/ADT/SmallBitVector.h - 'Normally small' bit vectors -*- C++ -*-===//
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 implements the SmallBitVector class.
10//
11//===----------------------------------------------------------------------===//
12
13#ifndef LLVM_ADT_SMALLBITVECTOR_H
14#define LLVM_ADT_SMALLBITVECTOR_H
15
16#include "llvm/ADT/BitVector.h"
17#include "llvm/ADT/iterator_range.h"
18#include "llvm/Support/MathExtras.h"
19#include <algorithm>
20#include <cassert>
21#include <climits>
22#include <cstddef>
23#include <cstdint>
24#include <limits>
25#include <utility>
26
27namespace llvm {
28
29/// This is a 'bitvector' (really, a variable-sized bit array), optimized for
30/// the case when the array is small. It contains one pointer-sized field, which
31/// is directly used as a plain collection of bits when possible, or as a
32/// pointer to a larger heap-allocated array when necessary. This allows normal
33/// "small" cases to be fast without losing generality for large inputs.
34class SmallBitVector {
35 // TODO: In "large" mode, a pointer to a BitVector is used, leading to an
36 // unnecessary level of indirection. It would be more efficient to use a
37 // pointer to memory containing size, allocation size, and the array of bits.
38 uintptr_t X = 1;
39
40 enum {
41 // The number of bits in this class.
42 NumBaseBits = sizeof(uintptr_t) * CHAR_BIT8,
43
44 // One bit is used to discriminate between small and large mode. The
45 // remaining bits are used for the small-mode representation.
46 SmallNumRawBits = NumBaseBits - 1,
47
48 // A few more bits are used to store the size of the bit set in small mode.
49 // Theoretically this is a ceil-log2. These bits are encoded in the most
50 // significant bits of the raw bits.
51 SmallNumSizeBits = (NumBaseBits == 32 ? 5 :
52 NumBaseBits == 64 ? 6 :
53 SmallNumRawBits),
54
55 // The remaining bits are used to store the actual set in small mode.
56 SmallNumDataBits = SmallNumRawBits - SmallNumSizeBits
57 };
58
59 static_assert(NumBaseBits == 64 || NumBaseBits == 32,
60 "Unsupported word size");
61
62public:
63 using size_type = unsigned;
64
65 // Encapsulation of a single bit.
66 class reference {
67 SmallBitVector &TheVector;
68 unsigned BitPos;
69
70 public:
71 reference(SmallBitVector &b, unsigned Idx) : TheVector(b), BitPos(Idx) {}
72
73 reference(const reference&) = default;
74
75 reference& operator=(reference t) {
76 *this = bool(t);
77 return *this;
78 }
79
80 reference& operator=(bool t) {
81 if (t)
82 TheVector.set(BitPos);
83 else
84 TheVector.reset(BitPos);
85 return *this;
86 }
87
88 operator bool() const {
89 return const_cast<const SmallBitVector &>(TheVector).operator[](BitPos);
90 }
91 };
92
93private:
94 BitVector *getPointer() const {
95 assert(!isSmall())((!isSmall()) ? static_cast<void> (0) : __assert_fail (
"!isSmall()", "/build/llvm-toolchain-snapshot-9~svn362543/include/llvm/ADT/SmallBitVector.h"
, 95, __PRETTY_FUNCTION__))
;
96 return reinterpret_cast<BitVector *>(X);
97 }
98
99 void switchToSmall(uintptr_t NewSmallBits, size_t NewSize) {
100 X = 1;
101 setSmallSize(NewSize);
102 setSmallBits(NewSmallBits);
103 }
104
105 void switchToLarge(BitVector *BV) {
106 X = reinterpret_cast<uintptr_t>(BV);
107 assert(!isSmall() && "Tried to use an unaligned pointer")((!isSmall() && "Tried to use an unaligned pointer") ?
static_cast<void> (0) : __assert_fail ("!isSmall() && \"Tried to use an unaligned pointer\""
, "/build/llvm-toolchain-snapshot-9~svn362543/include/llvm/ADT/SmallBitVector.h"
, 107, __PRETTY_FUNCTION__))
;
108 }
109
110 // Return all the bits used for the "small" representation; this includes
111 // bits for the size as well as the element bits.
112 uintptr_t getSmallRawBits() const {
113 assert(isSmall())((isSmall()) ? static_cast<void> (0) : __assert_fail ("isSmall()"
, "/build/llvm-toolchain-snapshot-9~svn362543/include/llvm/ADT/SmallBitVector.h"
, 113, __PRETTY_FUNCTION__))
;
114 return X >> 1;
115 }
116
117 void setSmallRawBits(uintptr_t NewRawBits) {
118 assert(isSmall())((isSmall()) ? static_cast<void> (0) : __assert_fail ("isSmall()"
, "/build/llvm-toolchain-snapshot-9~svn362543/include/llvm/ADT/SmallBitVector.h"
, 118, __PRETTY_FUNCTION__))
;
119 X = (NewRawBits << 1) | uintptr_t(1);
120 }
121
122 // Return the size.
123 size_t getSmallSize() const { return getSmallRawBits() >> SmallNumDataBits; }
124
125 void setSmallSize(size_t Size) {
126 setSmallRawBits(getSmallBits() | (Size << SmallNumDataBits));
127 }
128
129 // Return the element bits.
130 uintptr_t getSmallBits() const {
131 return getSmallRawBits() & ~(~uintptr_t(0) << getSmallSize());
132 }
133
134 void setSmallBits(uintptr_t NewBits) {
135 setSmallRawBits((NewBits & ~(~uintptr_t(0) << getSmallSize())) |
136 (getSmallSize() << SmallNumDataBits));
137 }
138
139public:
140 /// Creates an empty bitvector.
141 SmallBitVector() = default;
142
143 /// Creates a bitvector of specified number of bits. All bits are initialized
144 /// to the specified value.
145 explicit SmallBitVector(unsigned s, bool t = false) {
146 if (s <= SmallNumDataBits)
15
Taking false branch
147 switchToSmall(t ? ~uintptr_t(0) : 0, s);
148 else
149 switchToLarge(new BitVector(s, t));
16
Memory is allocated
150 }
151
152 /// SmallBitVector copy ctor.
153 SmallBitVector(const SmallBitVector &RHS) {
154 if (RHS.isSmall())
155 X = RHS.X;
156 else
157 switchToLarge(new BitVector(*RHS.getPointer()));
158 }
159
160 SmallBitVector(SmallBitVector &&RHS) : X(RHS.X) {
161 RHS.X = 1;
162 }
163
164 ~SmallBitVector() {
165 if (!isSmall())
166 delete getPointer();
167 }
168
169 using const_set_bits_iterator = const_set_bits_iterator_impl<SmallBitVector>;
170 using set_iterator = const_set_bits_iterator;
171
172 const_set_bits_iterator set_bits_begin() const {
173 return const_set_bits_iterator(*this);
174 }
175
176 const_set_bits_iterator set_bits_end() const {
177 return const_set_bits_iterator(*this, -1);
178 }
179
180 iterator_range<const_set_bits_iterator> set_bits() const {
181 return make_range(set_bits_begin(), set_bits_end());
182 }
183
184 bool isSmall() const { return X & uintptr_t(1); }
185
186 /// Tests whether there are no bits in this bitvector.
187 bool empty() const {
188 return isSmall() ? getSmallSize() == 0 : getPointer()->empty();
189 }
190
191 /// Returns the number of bits in this bitvector.
192 size_t size() const {
193 return isSmall() ? getSmallSize() : getPointer()->size();
194 }
195
196 /// Returns the number of bits which are set.
197 size_type count() const {
198 if (isSmall()) {
199 uintptr_t Bits = getSmallBits();
200 return countPopulation(Bits);
201 }
202 return getPointer()->count();
203 }
204
205 /// Returns true if any bit is set.
206 bool any() const {
207 if (isSmall())
208 return getSmallBits() != 0;
209 return getPointer()->any();
210 }
211
212 /// Returns true if all bits are set.
213 bool all() const {
214 if (isSmall())
215 return getSmallBits() == (uintptr_t(1) << getSmallSize()) - 1;
216 return getPointer()->all();
217 }
218
219 /// Returns true if none of the bits are set.
220 bool none() const {
221 if (isSmall())
222 return getSmallBits() == 0;
223 return getPointer()->none();
224 }
225
226 /// Returns the index of the first set bit, -1 if none of the bits are set.
227 int find_first() const {
228 if (isSmall()) {
229 uintptr_t Bits = getSmallBits();
230 if (Bits == 0)
231 return -1;
232 return countTrailingZeros(Bits);
233 }
234 return getPointer()->find_first();
235 }
236
237 int find_last() const {
238 if (isSmall()) {
239 uintptr_t Bits = getSmallBits();
240 if (Bits == 0)
241 return -1;
242 return NumBaseBits - countLeadingZeros(Bits) - 1;
243 }
244 return getPointer()->find_last();
245 }
246
247 /// Returns the index of the first unset bit, -1 if all of the bits are set.
248 int find_first_unset() const {
249 if (isSmall()) {
250 if (count() == getSmallSize())
251 return -1;
252
253 uintptr_t Bits = getSmallBits();
254 return countTrailingOnes(Bits);
255 }
256 return getPointer()->find_first_unset();
257 }
258
259 int find_last_unset() const {
260 if (isSmall()) {
261 if (count() == getSmallSize())
262 return -1;
263
264 uintptr_t Bits = getSmallBits();
265 // Set unused bits.
266 Bits |= ~uintptr_t(0) << getSmallSize();
267 return NumBaseBits - countLeadingOnes(Bits) - 1;
268 }
269 return getPointer()->find_last_unset();
270 }
271
272 /// Returns the index of the next set bit following the "Prev" bit.
273 /// Returns -1 if the next set bit is not found.
274 int find_next(unsigned Prev) const {
275 if (isSmall()) {
276 uintptr_t Bits = getSmallBits();
277 // Mask off previous bits.
278 Bits &= ~uintptr_t(0) << (Prev + 1);
279 if (Bits == 0 || Prev + 1 >= getSmallSize())
280 return -1;
281 return countTrailingZeros(Bits);
282 }
283 return getPointer()->find_next(Prev);
284 }
285
286 /// Returns the index of the next unset bit following the "Prev" bit.
287 /// Returns -1 if the next unset bit is not found.
288 int find_next_unset(unsigned Prev) const {
289 if (isSmall()) {
290 ++Prev;
291 uintptr_t Bits = getSmallBits();
292 // Mask in previous bits.
293 uintptr_t Mask = (1 << Prev) - 1;
294 Bits |= Mask;
295
296 if (Bits == ~uintptr_t(0) || Prev + 1 >= getSmallSize())
297 return -1;
298 return countTrailingOnes(Bits);
299 }
300 return getPointer()->find_next_unset(Prev);
301 }
302
303 /// find_prev - Returns the index of the first set bit that precedes the
304 /// the bit at \p PriorTo. Returns -1 if all previous bits are unset.
305 int find_prev(unsigned PriorTo) const {
306 if (isSmall()) {
307 if (PriorTo == 0)
308 return -1;
309
310 --PriorTo;
311 uintptr_t Bits = getSmallBits();
312 Bits &= maskTrailingOnes<uintptr_t>(PriorTo + 1);
313 if (Bits == 0)
314 return -1;
315
316 return NumBaseBits - countLeadingZeros(Bits) - 1;
317 }
318 return getPointer()->find_prev(PriorTo);
319 }
320
321 /// Clear all bits.
322 void clear() {
323 if (!isSmall())
324 delete getPointer();
325 switchToSmall(0, 0);
326 }
327
328 /// Grow or shrink the bitvector.
329 void resize(unsigned N, bool t = false) {
330 if (!isSmall()) {
331 getPointer()->resize(N, t);
332 } else if (SmallNumDataBits >= N) {
333 uintptr_t NewBits = t ? ~uintptr_t(0) << getSmallSize() : 0;
334 setSmallSize(N);
335 setSmallBits(NewBits | getSmallBits());
336 } else {
337 BitVector *BV = new BitVector(N, t);
338 uintptr_t OldBits = getSmallBits();
339 for (size_t i = 0, e = getSmallSize(); i != e; ++i)
340 (*BV)[i] = (OldBits >> i) & 1;
341 switchToLarge(BV);
342 }
343 }
344
345 void reserve(unsigned N) {
346 if (isSmall()) {
347 if (N > SmallNumDataBits) {
348 uintptr_t OldBits = getSmallRawBits();
349 size_t SmallSize = getSmallSize();
350 BitVector *BV = new BitVector(SmallSize);
351 for (size_t i = 0; i < SmallSize; ++i)
352 if ((OldBits >> i) & 1)
353 BV->set(i);
354 BV->reserve(N);
355 switchToLarge(BV);
356 }
357 } else {
358 getPointer()->reserve(N);
359 }
360 }
361
362 // Set, reset, flip
363 SmallBitVector &set() {
364 if (isSmall())
365 setSmallBits(~uintptr_t(0));
366 else
367 getPointer()->set();
368 return *this;
369 }
370
371 SmallBitVector &set(unsigned Idx) {
372 if (isSmall()) {
373 assert(Idx <= static_cast<unsigned>(((Idx <= static_cast<unsigned>( std::numeric_limits<
uintptr_t>::digits) && "undefined behavior") ? static_cast
<void> (0) : __assert_fail ("Idx <= static_cast<unsigned>( std::numeric_limits<uintptr_t>::digits) && \"undefined behavior\""
, "/build/llvm-toolchain-snapshot-9~svn362543/include/llvm/ADT/SmallBitVector.h"
, 375, __PRETTY_FUNCTION__))
374 std::numeric_limits<uintptr_t>::digits) &&((Idx <= static_cast<unsigned>( std::numeric_limits<
uintptr_t>::digits) && "undefined behavior") ? static_cast
<void> (0) : __assert_fail ("Idx <= static_cast<unsigned>( std::numeric_limits<uintptr_t>::digits) && \"undefined behavior\""
, "/build/llvm-toolchain-snapshot-9~svn362543/include/llvm/ADT/SmallBitVector.h"
, 375, __PRETTY_FUNCTION__))
375 "undefined behavior")((Idx <= static_cast<unsigned>( std::numeric_limits<
uintptr_t>::digits) && "undefined behavior") ? static_cast
<void> (0) : __assert_fail ("Idx <= static_cast<unsigned>( std::numeric_limits<uintptr_t>::digits) && \"undefined behavior\""
, "/build/llvm-toolchain-snapshot-9~svn362543/include/llvm/ADT/SmallBitVector.h"
, 375, __PRETTY_FUNCTION__))
;
376 setSmallBits(getSmallBits() | (uintptr_t(1) << Idx));
377 }
378 else
379 getPointer()->set(Idx);
380 return *this;
381 }
382
383 /// Efficiently set a range of bits in [I, E)
384 SmallBitVector &set(unsigned I, unsigned E) {
385 assert(I <= E && "Attempted to set backwards range!")((I <= E && "Attempted to set backwards range!") ?
static_cast<void> (0) : __assert_fail ("I <= E && \"Attempted to set backwards range!\""
, "/build/llvm-toolchain-snapshot-9~svn362543/include/llvm/ADT/SmallBitVector.h"
, 385, __PRETTY_FUNCTION__))
;
386 assert(E <= size() && "Attempted to set out-of-bounds range!")((E <= size() && "Attempted to set out-of-bounds range!"
) ? static_cast<void> (0) : __assert_fail ("E <= size() && \"Attempted to set out-of-bounds range!\""
, "/build/llvm-toolchain-snapshot-9~svn362543/include/llvm/ADT/SmallBitVector.h"
, 386, __PRETTY_FUNCTION__))
;
387 if (I == E) return *this;
388 if (isSmall()) {
389 uintptr_t EMask = ((uintptr_t)1) << E;
390 uintptr_t IMask = ((uintptr_t)1) << I;
391 uintptr_t Mask = EMask - IMask;
392 setSmallBits(getSmallBits() | Mask);
393 } else
394 getPointer()->set(I, E);
395 return *this;
396 }
397
398 SmallBitVector &reset() {
399 if (isSmall())
400 setSmallBits(0);
401 else
402 getPointer()->reset();
403 return *this;
404 }
405
406 SmallBitVector &reset(unsigned Idx) {
407 if (isSmall())
408 setSmallBits(getSmallBits() & ~(uintptr_t(1) << Idx));
409 else
410 getPointer()->reset(Idx);
411 return *this;
412 }
413
414 /// Efficiently reset a range of bits in [I, E)
415 SmallBitVector &reset(unsigned I, unsigned E) {
416 assert(I <= E && "Attempted to reset backwards range!")((I <= E && "Attempted to reset backwards range!")
? static_cast<void> (0) : __assert_fail ("I <= E && \"Attempted to reset backwards range!\""
, "/build/llvm-toolchain-snapshot-9~svn362543/include/llvm/ADT/SmallBitVector.h"
, 416, __PRETTY_FUNCTION__))
;
417 assert(E <= size() && "Attempted to reset out-of-bounds range!")((E <= size() && "Attempted to reset out-of-bounds range!"
) ? static_cast<void> (0) : __assert_fail ("E <= size() && \"Attempted to reset out-of-bounds range!\""
, "/build/llvm-toolchain-snapshot-9~svn362543/include/llvm/ADT/SmallBitVector.h"
, 417, __PRETTY_FUNCTION__))
;
418 if (I == E) return *this;
419 if (isSmall()) {
420 uintptr_t EMask = ((uintptr_t)1) << E;
421 uintptr_t IMask = ((uintptr_t)1) << I;
422 uintptr_t Mask = EMask - IMask;
423 setSmallBits(getSmallBits() & ~Mask);
424 } else
425 getPointer()->reset(I, E);
426 return *this;
427 }
428
429 SmallBitVector &flip() {
430 if (isSmall())
431 setSmallBits(~getSmallBits());
432 else
433 getPointer()->flip();
434 return *this;
435 }
436
437 SmallBitVector &flip(unsigned Idx) {
438 if (isSmall())
439 setSmallBits(getSmallBits() ^ (uintptr_t(1) << Idx));
440 else
441 getPointer()->flip(Idx);
442 return *this;
443 }
444
445 // No argument flip.
446 SmallBitVector operator~() const {
447 return SmallBitVector(*this).flip();
448 }
449
450 // Indexing.
451 reference operator[](unsigned Idx) {
452 assert(Idx < size() && "Out-of-bounds Bit access.")((Idx < size() && "Out-of-bounds Bit access.") ? static_cast
<void> (0) : __assert_fail ("Idx < size() && \"Out-of-bounds Bit access.\""
, "/build/llvm-toolchain-snapshot-9~svn362543/include/llvm/ADT/SmallBitVector.h"
, 452, __PRETTY_FUNCTION__))
;
453 return reference(*this, Idx);
454 }
455
456 bool operator[](unsigned Idx) const {
457 assert(Idx < size() && "Out-of-bounds Bit access.")((Idx < size() && "Out-of-bounds Bit access.") ? static_cast
<void> (0) : __assert_fail ("Idx < size() && \"Out-of-bounds Bit access.\""
, "/build/llvm-toolchain-snapshot-9~svn362543/include/llvm/ADT/SmallBitVector.h"
, 457, __PRETTY_FUNCTION__))
;
458 if (isSmall())
459 return ((getSmallBits() >> Idx) & 1) != 0;
460 return getPointer()->operator[](Idx);
461 }
462
463 bool test(unsigned Idx) const {
464 return (*this)[Idx];
465 }
466
467 // Push single bit to end of vector.
468 void push_back(bool Val) {
469 resize(size() + 1, Val);
470 }
471
472 /// Test if any common bits are set.
473 bool anyCommon(const SmallBitVector &RHS) const {
474 if (isSmall() && RHS.isSmall())
475 return (getSmallBits() & RHS.getSmallBits()) != 0;
476 if (!isSmall() && !RHS.isSmall())
477 return getPointer()->anyCommon(*RHS.getPointer());
478
479 for (unsigned i = 0, e = std::min(size(), RHS.size()); i != e; ++i)
480 if (test(i) && RHS.test(i))
481 return true;
482 return false;
483 }
484
485 // Comparison operators.
486 bool operator==(const SmallBitVector &RHS) const {
487 if (size() != RHS.size())
488 return false;
489 if (isSmall() && RHS.isSmall())
490 return getSmallBits() == RHS.getSmallBits();
491 else if (!isSmall() && !RHS.isSmall())
492 return *getPointer() == *RHS.getPointer();
493 else {
494 for (size_t i = 0, e = size(); i != e; ++i) {
495 if ((*this)[i] != RHS[i])
496 return false;
497 }
498 return true;
499 }
500 }
501
502 bool operator!=(const SmallBitVector &RHS) const {
503 return !(*this == RHS);
504 }
505
506 // Intersection, union, disjoint union.
507 // FIXME BitVector::operator&= does not resize the LHS but this does
508 SmallBitVector &operator&=(const SmallBitVector &RHS) {
509 resize(std::max(size(), RHS.size()));
510 if (isSmall() && RHS.isSmall())
511 setSmallBits(getSmallBits() & RHS.getSmallBits());
512 else if (!isSmall() && !RHS.isSmall())
513 getPointer()->operator&=(*RHS.getPointer());
514 else {
515 size_t i, e;
516 for (i = 0, e = std::min(size(), RHS.size()); i != e; ++i)
517 (*this)[i] = test(i) && RHS.test(i);
518 for (e = size(); i != e; ++i)
519 reset(i);
520 }
521 return *this;
522 }
523
524 /// Reset bits that are set in RHS. Same as *this &= ~RHS.
525 SmallBitVector &reset(const SmallBitVector &RHS) {
526 if (isSmall() && RHS.isSmall())
527 setSmallBits(getSmallBits() & ~RHS.getSmallBits());
528 else if (!isSmall() && !RHS.isSmall())
529 getPointer()->reset(*RHS.getPointer());
530 else
531 for (unsigned i = 0, e = std::min(size(), RHS.size()); i != e; ++i)
532 if (RHS.test(i))
533 reset(i);
534
535 return *this;
536 }
537
538 /// Check if (This - RHS) is zero. This is the same as reset(RHS) and any().
539 bool test(const SmallBitVector &RHS) const {
540 if (isSmall() && RHS.isSmall())
541 return (getSmallBits() & ~RHS.getSmallBits()) != 0;
542 if (!isSmall() && !RHS.isSmall())
543 return getPointer()->test(*RHS.getPointer());
544
545 unsigned i, e;
546 for (i = 0, e = std::min(size(), RHS.size()); i != e; ++i)
547 if (test(i) && !RHS.test(i))
548 return true;
549
550 for (e = size(); i != e; ++i)
551 if (test(i))
552 return true;
553
554 return false;
555 }
556
557 SmallBitVector &operator|=(const SmallBitVector &RHS) {
558 resize(std::max(size(), RHS.size()));
559 if (isSmall() && RHS.isSmall())
560 setSmallBits(getSmallBits() | RHS.getSmallBits());
561 else if (!isSmall() && !RHS.isSmall())
562 getPointer()->operator|=(*RHS.getPointer());
563 else {
564 for (size_t i = 0, e = RHS.size(); i != e; ++i)
565 (*this)[i] = test(i) || RHS.test(i);
566 }
567 return *this;
568 }
569
570 SmallBitVector &operator^=(const SmallBitVector &RHS) {
571 resize(std::max(size(), RHS.size()));
572 if (isSmall() && RHS.isSmall())
573 setSmallBits(getSmallBits() ^ RHS.getSmallBits());
574 else if (!isSmall() && !RHS.isSmall())
575 getPointer()->operator^=(*RHS.getPointer());
576 else {
577 for (size_t i = 0, e = RHS.size(); i != e; ++i)
578 (*this)[i] = test(i) != RHS.test(i);
579 }
580 return *this;
581 }
582
583 SmallBitVector &operator<<=(unsigned N) {
584 if (isSmall())
585 setSmallBits(getSmallBits() << N);
586 else
587 getPointer()->operator<<=(N);
588 return *this;
589 }
590
591 SmallBitVector &operator>>=(unsigned N) {
592 if (isSmall())
593 setSmallBits(getSmallBits() >> N);
594 else
595 getPointer()->operator>>=(N);
596 return *this;
597 }
598
599 // Assignment operator.
600 const SmallBitVector &operator=(const SmallBitVector &RHS) {
601 if (isSmall()) {
602 if (RHS.isSmall())
603 X = RHS.X;
604 else
605 switchToLarge(new BitVector(*RHS.getPointer()));
606 } else {
607 if (!RHS.isSmall())
608 *getPointer() = *RHS.getPointer();
609 else {
610 delete getPointer();
611 X = RHS.X;
612 }
613 }
614 return *this;
615 }
616
617 const SmallBitVector &operator=(SmallBitVector &&RHS) {
618 if (this != &RHS) {
619 clear();
620 swap(RHS);
621 }
622 return *this;
623 }
624
625 void swap(SmallBitVector &RHS) {
626 std::swap(X, RHS.X);
627 }
628
629 /// Add '1' bits from Mask to this vector. Don't resize.
630 /// This computes "*this |= Mask".
631 void setBitsInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) {
632 if (isSmall())
633 applyMask<true, false>(Mask, MaskWords);
634 else
635 getPointer()->setBitsInMask(Mask, MaskWords);
636 }
637
638 /// Clear any bits in this vector that are set in Mask. Don't resize.
639 /// This computes "*this &= ~Mask".
640 void clearBitsInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) {
641 if (isSmall())
642 applyMask<false, false>(Mask, MaskWords);
643 else
644 getPointer()->clearBitsInMask(Mask, MaskWords);
645 }
646
647 /// Add a bit to this vector for every '0' bit in Mask. Don't resize.
648 /// This computes "*this |= ~Mask".
649 void setBitsNotInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) {
650 if (isSmall())
651 applyMask<true, true>(Mask, MaskWords);
652 else
653 getPointer()->setBitsNotInMask(Mask, MaskWords);
654 }
655
656 /// Clear a bit in this vector for every '0' bit in Mask. Don't resize.
657 /// This computes "*this &= Mask".
658 void clearBitsNotInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) {
659 if (isSmall())
660 applyMask<false, true>(Mask, MaskWords);
661 else
662 getPointer()->clearBitsNotInMask(Mask, MaskWords);
663 }
664
665private:
666 template <bool AddBits, bool InvertMask>
667 void applyMask(const uint32_t *Mask, unsigned MaskWords) {
668 assert(MaskWords <= sizeof(uintptr_t) && "Mask is larger than base!")((MaskWords <= sizeof(uintptr_t) && "Mask is larger than base!"
) ? static_cast<void> (0) : __assert_fail ("MaskWords <= sizeof(uintptr_t) && \"Mask is larger than base!\""
, "/build/llvm-toolchain-snapshot-9~svn362543/include/llvm/ADT/SmallBitVector.h"
, 668, __PRETTY_FUNCTION__))
;
669 uintptr_t M = Mask[0];
670 if (NumBaseBits == 64)
671 M |= uint64_t(Mask[1]) << 32;
672 if (InvertMask)
673 M = ~M;
674 if (AddBits)
675 setSmallBits(getSmallBits() | M);
676 else
677 setSmallBits(getSmallBits() & ~M);
678 }
679};
680
681inline SmallBitVector
682operator&(const SmallBitVector &LHS, const SmallBitVector &RHS) {
683 SmallBitVector Result(LHS);
684 Result &= RHS;
685 return Result;
686}
687
688inline SmallBitVector
689operator|(const SmallBitVector &LHS, const SmallBitVector &RHS) {
690 SmallBitVector Result(LHS);
691 Result |= RHS;
692 return Result;
693}
694
695inline SmallBitVector
696operator^(const SmallBitVector &LHS, const SmallBitVector &RHS) {
697 SmallBitVector Result(LHS);
698 Result ^= RHS;
699 return Result;
700}
701
702} // end namespace llvm
703
704namespace std {
705
706/// Implement std::swap in terms of BitVector swap.
707inline void
708swap(llvm::SmallBitVector &LHS, llvm::SmallBitVector &RHS) {
709 LHS.swap(RHS);
710}
711
712} // end namespace std
713
714#endif // LLVM_ADT_SMALLBITVECTOR_H