From 7d1e09e79fa908dd5333373b67a119d6bb9487f3 Mon Sep 17 00:00:00 2001 From: Adam Nemet Date: Tue, 3 Nov 2015 21:39:52 +0000 Subject: [PATCH] [LAA] LLE 3/6: Rename InterestingDependence to Dependences, NFC Summary: We now collect all types of dependences including lexically forward deps not just "interesting" ones. Reviewers: hfinkel Subscribers: rengolin, llvm-commits Differential Revision: http://reviews.llvm.org/D13256 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@251985 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/Analysis/LoopAccessAnalysis.h | 34 ++++++------- lib/Analysis/LoopAccessAnalysis.cpp | 48 ++++++++----------- lib/Transforms/Scalar/LoopDistribute.cpp | 11 ++--- .../forward-loop-carried.ll | 2 +- .../forward-loop-independent.ll | 2 +- .../pointer-with-unknown-bounds.ll | 2 +- .../resort-to-memchecks-only.ll | 4 +- .../LoopAccessAnalysis/safe-no-checks.ll | 2 +- .../stride-access-dependence.ll | 28 +++++------ .../underlying-objects-2.ll | 2 +- .../unsafe-and-rt-checks.ll | 2 +- 11 files changed, 63 insertions(+), 74 deletions(-) diff --git a/include/llvm/Analysis/LoopAccessAnalysis.h b/include/llvm/Analysis/LoopAccessAnalysis.h index ea080bc7f87..1df04d6b627 100644 --- a/include/llvm/Analysis/LoopAccessAnalysis.h +++ b/include/llvm/Analysis/LoopAccessAnalysis.h @@ -141,7 +141,7 @@ public: // read and write of A[i]), LAA will locally deem the dependence "safe" // without querying the MemoryDepChecker. Therefore we can miss // enumerating loop-independent forward dependences in - // getInterestingDependences. Note that as soon as there are different + // getDependences. Note that as soon as there are different // indices used to access the same array, the MemoryDepChecker *is* // queried and the dependence list is complete. Forward, @@ -173,9 +173,6 @@ public: /// \brief Dependence types that don't prevent vectorization. static bool isSafeForVectorization(DepType Type); - /// \brief Dependence types that can be queried from the analysis. - static bool isInterestingDependence(DepType Type); - /// \brief Lexically backward dependence types. bool isPossiblyBackward() const; @@ -189,7 +186,7 @@ public: SCEVUnionPredicate &Preds) : SE(Se), InnermostLoop(L), AccessIdx(0), ShouldRetryWithRuntimeCheck(false), SafeForVectorization(true), - RecordInterestingDependences(true), Preds(Preds) {} + RecordDependences(true), Preds(Preds) {} /// \brief Register the location (instructions are given increasing numbers) /// of a write access. @@ -227,14 +224,14 @@ public: /// vectorize the loop with a dynamic array access check. bool shouldRetryWithRuntimeCheck() { return ShouldRetryWithRuntimeCheck; } - /// \brief Returns the interesting dependences. If null is returned we - /// exceeded the MaxInterestingDependence threshold and this information is - /// not available. - const SmallVectorImpl *getInterestingDependences() const { - return RecordInterestingDependences ? &InterestingDependences : nullptr; + /// \brief Returns the memory dependences. If null is returned we exceeded + /// the MaxDependences threshold and this information is not + /// available. + const SmallVectorImpl *getDependences() const { + return RecordDependences ? &Dependences : nullptr; } - void clearInterestingDependences() { InterestingDependences.clear(); } + void clearDependences() { Dependences.clear(); } /// \brief The vector of memory access instructions. The indices are used as /// instruction identifiers in the Dependence class. @@ -270,15 +267,14 @@ private: /// vectorization. bool SafeForVectorization; - //// \brief True if InterestingDependences reflects the dependences in the - //// loop. If false we exceeded MaxInterestingDependence and - //// InterestingDependences is invalid. - bool RecordInterestingDependences; + //// \brief True if Dependences reflects the dependences in the + //// loop. If false we exceeded MaxDependences and + //// Dependences is invalid. + bool RecordDependences; - /// \brief Interesting memory dependences collected during the analysis as - /// defined by isInterestingDependence. Only valid if - /// RecordInterestingDependences is true. - SmallVector InterestingDependences; + /// \brief Memory dependences collected during the analysis. Only valid if + /// RecordDependences is true. + SmallVector Dependences; /// \brief Check whether there is a plausible dependence between the two /// accesses. diff --git a/lib/Analysis/LoopAccessAnalysis.cpp b/lib/Analysis/LoopAccessAnalysis.cpp index 80d6575a9c2..fd85a908ffb 100644 --- a/lib/Analysis/LoopAccessAnalysis.cpp +++ b/lib/Analysis/LoopAccessAnalysis.cpp @@ -58,12 +58,12 @@ static cl::opt MemoryCheckMergeThreshold( /// Maximum SIMD width. const unsigned VectorizerParams::MaxVectorWidth = 64; -/// \brief We collect interesting dependences up to this threshold. -static cl::opt MaxInterestingDependence( - "max-interesting-dependences", cl::Hidden, - cl::desc("Maximum number of interesting dependences collected by " - "loop-access analysis (default = 100)"), - cl::init(100)); +/// \brief We collect dependences up to this threshold. +static cl::opt + MaxDependences("max-dependences", cl::Hidden, + cl::desc("Maximum number of dependences collected by " + "loop-access analysis (default = 100)"), + cl::init(100)); bool VectorizerParams::isInterleaveForced() { return ::VectorizationInterleave.getNumOccurrences() > 0; @@ -468,7 +468,7 @@ public: /// We decided that no dependence analysis would be used. Reset the state. void resetDepChecks(MemoryDepChecker &DepChecker) { CheckDeps.clear(); - DepChecker.clearInterestingDependences(); + DepChecker.clearDependences(); } MemAccessInfoSet &getDependenciesToCheck() { return CheckDeps; } @@ -910,10 +910,6 @@ bool MemoryDepChecker::Dependence::isSafeForVectorization(DepType Type) { llvm_unreachable("unexpected DepType!"); } -bool MemoryDepChecker::Dependence::isInterestingDependence(DepType Type) { - return Type != NoDep; -} - bool MemoryDepChecker::Dependence::isPossiblyBackward() const { switch (Type) { case NoDep: @@ -1229,22 +1225,21 @@ bool MemoryDepChecker::areDepsSafe(DepCandidates &AccessSets, isDependent(*A.first, A.second, *B.first, B.second, Strides); SafeForVectorization &= Dependence::isSafeForVectorization(Type); - // Gather dependences unless we accumulated MaxInterestingDependence + // Gather dependences unless we accumulated MaxDependences // dependences. In that case return as soon as we find the first // unsafe dependence. This puts a limit on this quadratic // algorithm. - if (RecordInterestingDependences) { - if (Dependence::isInterestingDependence(Type)) - InterestingDependences.push_back( - Dependence(A.second, B.second, Type)); - - if (InterestingDependences.size() >= MaxInterestingDependence) { - RecordInterestingDependences = false; - InterestingDependences.clear(); + if (RecordDependences) { + if (Type != Dependence::NoDep) + Dependences.push_back(Dependence(A.second, B.second, Type)); + + if (Dependences.size() >= MaxDependences) { + RecordDependences = false; + Dependences.clear(); DEBUG(dbgs() << "Too many dependences, stopped recording\n"); } } - if (!RecordInterestingDependences && !SafeForVectorization) + if (!RecordDependences && !SafeForVectorization) return false; } ++OI; @@ -1253,8 +1248,7 @@ bool MemoryDepChecker::areDepsSafe(DepCandidates &AccessSets, } } - DEBUG(dbgs() << "Total Interesting Dependences: " - << InterestingDependences.size() << "\n"); + DEBUG(dbgs() << "Total Dependences: " << Dependences.size() << "\n"); return SafeForVectorization; } @@ -1749,14 +1743,14 @@ void LoopAccessInfo::print(raw_ostream &OS, unsigned Depth) const { if (Report) OS.indent(Depth) << "Report: " << Report->str() << "\n"; - if (auto *InterestingDependences = DepChecker.getInterestingDependences()) { - OS.indent(Depth) << "Interesting Dependences:\n"; - for (auto &Dep : *InterestingDependences) { + if (auto *Dependences = DepChecker.getDependences()) { + OS.indent(Depth) << "Dependences:\n"; + for (auto &Dep : *Dependences) { Dep.print(OS, Depth + 2, DepChecker.getMemoryInstructions()); OS << "\n"; } } else - OS.indent(Depth) << "Too many interesting dependences, not recorded\n"; + OS.indent(Depth) << "Too many dependences, not recorded\n"; // List the pair of accesses need run-time checks to prove independence. PtrRtChecking.print(OS, Depth); diff --git a/lib/Transforms/Scalar/LoopDistribute.cpp b/lib/Transforms/Scalar/LoopDistribute.cpp index a7769644203..1584f0fa3eb 100644 --- a/lib/Transforms/Scalar/LoopDistribute.cpp +++ b/lib/Transforms/Scalar/LoopDistribute.cpp @@ -546,11 +546,11 @@ public: MemoryInstructionDependences( const SmallVectorImpl &Instructions, - const SmallVectorImpl &InterestingDependences) { + const SmallVectorImpl &Dependences) { Accesses.append(Instructions.begin(), Instructions.end()); DEBUG(dbgs() << "Backward dependences:\n"); - for (auto &Dep : InterestingDependences) + for (auto &Dep : Dependences) if (Dep.isPossiblyBackward()) { // Note that the designations source and destination follow the program // order, i.e. source is always first. (The direction is given by the @@ -674,9 +674,8 @@ private: DEBUG(dbgs() << "Skipping; memory operations are safe for vectorization"); return false; } - auto *InterestingDependences = - LAI.getDepChecker().getInterestingDependences(); - if (!InterestingDependences || InterestingDependences->empty()) { + auto *Dependences = LAI.getDepChecker().getDependences(); + if (!Dependences || Dependences->empty()) { DEBUG(dbgs() << "Skipping; No unsafe dependences to isolate"); return false; } @@ -704,7 +703,7 @@ private: // NumUnsafeDependencesActive reaches 0. const MemoryDepChecker &DepChecker = LAI.getDepChecker(); MemoryInstructionDependences MID(DepChecker.getMemoryInstructions(), - *InterestingDependences); + *Dependences); int NumUnsafeDependencesActive = 0; for (auto &InstDep : MID) { diff --git a/test/Analysis/LoopAccessAnalysis/forward-loop-carried.ll b/test/Analysis/LoopAccessAnalysis/forward-loop-carried.ll index 138762c2a66..e18ec2357fd 100644 --- a/test/Analysis/LoopAccessAnalysis/forward-loop-carried.ll +++ b/test/Analysis/LoopAccessAnalysis/forward-loop-carried.ll @@ -9,7 +9,7 @@ target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128" define void @f(i32* %A, i32* %B, i32* %C, i64 %N) { -; CHECK: Interesting Dependences: +; CHECK: Dependences: ; CHECK-NEXT: Forward: ; CHECK-NEXT: store i32 %a_p1, i32* %Aidx_ahead, align 4 -> ; CHECK-NEXT: %a = load i32, i32* %Aidx, align 4 diff --git a/test/Analysis/LoopAccessAnalysis/forward-loop-independent.ll b/test/Analysis/LoopAccessAnalysis/forward-loop-independent.ll index c5573aee579..e1ba674ce80 100644 --- a/test/Analysis/LoopAccessAnalysis/forward-loop-independent.ll +++ b/test/Analysis/LoopAccessAnalysis/forward-loop-independent.ll @@ -22,7 +22,7 @@ target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128" define void @f(i32* noalias %A, i32* noalias %B, i32* noalias %C, i64 %N) { -; CHECK: Interesting Dependences: +; CHECK: Dependences: ; CHECK-NEXT: Forward: ; CHECK-NEXT: store i32 %b_p1, i32* %Aidx, align 4 -> ; CHECK-NEXT: %a = load i32, i32* %Aidx, align 4 diff --git a/test/Analysis/LoopAccessAnalysis/pointer-with-unknown-bounds.ll b/test/Analysis/LoopAccessAnalysis/pointer-with-unknown-bounds.ll index 5348cfe0542..20b7fb2c633 100644 --- a/test/Analysis/LoopAccessAnalysis/pointer-with-unknown-bounds.ll +++ b/test/Analysis/LoopAccessAnalysis/pointer-with-unknown-bounds.ll @@ -12,7 +12,7 @@ target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128" ; CHECK: for.body: ; CHECK: Report: unsafe dependent memory operations in loop ; CHECK-NOT: Report: cannot identify array bounds -; CHECK: Interesting Dependences: +; CHECK: Dependences: ; CHECK: Unknown: ; CHECK: %loadA = load i16, i16* %arrayidxA, align 2 -> ; CHECK: store i16 %mul, i16* %arrayidxA, align 2 diff --git a/test/Analysis/LoopAccessAnalysis/resort-to-memchecks-only.ll b/test/Analysis/LoopAccessAnalysis/resort-to-memchecks-only.ll index e7305173dd9..9412028fc70 100644 --- a/test/Analysis/LoopAccessAnalysis/resort-to-memchecks-only.ll +++ b/test/Analysis/LoopAccessAnalysis/resort-to-memchecks-only.ll @@ -2,7 +2,7 @@ ; We give up analyzing the dependences in this loop due to non-constant ; distance between A[i+offset] and A[i] and add memchecks to prove -; independence. Make sure that no interesting dependences are reported in +; independence. Make sure that no dependences are reported in ; this case. ; ; for (i = 0; i < n; i++) @@ -12,7 +12,7 @@ target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128" target triple = "x86_64-apple-macosx10.10.0" ; CHECK: Memory dependences are safe with run-time checks -; CHECK-NEXT: Interesting Dependences: +; CHECK-NEXT: Dependences: ; CHECK-NEXT: Run-time memory checks: ; CHECK-NEXT: 0: ; CHECK-NEXT: Comparing group diff --git a/test/Analysis/LoopAccessAnalysis/safe-no-checks.ll b/test/Analysis/LoopAccessAnalysis/safe-no-checks.ll index 069135e8525..d85258f75aa 100644 --- a/test/Analysis/LoopAccessAnalysis/safe-no-checks.ll +++ b/test/Analysis/LoopAccessAnalysis/safe-no-checks.ll @@ -11,7 +11,7 @@ target triple = "x86_64-apple-macosx10.10.0" ; store of A[i]; ; CHECK: Memory dependences are safe{{$}} -; CHECK-NEXT: Interesting Dependences: +; CHECK-NEXT: Dependences: ; CHECK-NEXT: Forward: ; CHECK-NEXT: %loadA_plus_2 = load i16, i16* %arrayidxA_plus_2, align 2 -> ; CHECK-NEXT: store i16 %mul1, i16* %arrayidxA, align 2 diff --git a/test/Analysis/LoopAccessAnalysis/stride-access-dependence.ll b/test/Analysis/LoopAccessAnalysis/stride-access-dependence.ll index 73573566295..5fc353e70cf 100644 --- a/test/Analysis/LoopAccessAnalysis/stride-access-dependence.ll +++ b/test/Analysis/LoopAccessAnalysis/stride-access-dependence.ll @@ -13,7 +13,7 @@ target datalayout = "e-m:e-i64:64-i128:128-n32:64-S128" ; CHECK: function 'nodep_Read_Write': ; CHECK-NEXT: for.body: ; CHECK-NEXT: Memory dependences are safe -; CHECK-NEXT: Interesting Dependences: +; CHECK-NEXT: Dependences: ; CHECK-NEXT: Run-time memory checks: define void @nodep_Read_Write(i32* nocapture %A) { @@ -49,7 +49,7 @@ for.body: ; preds = %entry, %for.body ; CHECK: function 'nodep_Write_Read': ; CHECK-NEXT: for.body: ; CHECK-NEXT: Memory dependences are safe -; CHECK-NEXT: Interesting Dependences: +; CHECK-NEXT: Dependences: ; CHECK-NEXT: Run-time memory checks: define i32 @nodep_Write_Read(i32* nocapture %A) { @@ -84,7 +84,7 @@ for.body: ; preds = %entry, %for.body ; CHECK: function 'nodep_Write_Write': ; CHECK-NEXT: for.body: ; CHECK-NEXT: Memory dependences are safe -; CHECK-NEXT: Interesting Dependences: +; CHECK-NEXT: Dependences: ; CHECK-NEXT: Run-time memory checks: define void @nodep_Write_Write(i32* nocapture %A) { @@ -118,7 +118,7 @@ for.body: ; preds = %entry, %for.body ; CHECK: function 'unsafe_Read_Write': ; CHECK-NEXT: for.body: ; CHECK-NEXT: Report: unsafe dependent memory operations in loop -; CHECK-NEXT: Interesting Dependences: +; CHECK-NEXT: Dependences: ; CHECK-NEXT: Backward: ; CHECK-NEXT: %0 = load i32, i32* %arrayidx, align 4 -> ; CHECK-NEXT: store i32 %add, i32* %arrayidx3, align 4 @@ -157,7 +157,7 @@ for.body: ; preds = %entry, %for.body ; CHECK: function 'unsafe_Write_Read': ; CHECK-NEXT: for.body: ; CHECK-NEXT: Report: unsafe dependent memory operations in loop -; CHECK-NEXT: Interesting Dependences: +; CHECK-NEXT: Dependences: ; CHECK-NEXT: Backward: ; CHECK-NEXT: store i32 %0, i32* %arrayidx, align 4 -> ; CHECK-NEXT: %1 = load i32, i32* %arrayidx2, align 4 @@ -193,7 +193,7 @@ for.body: ; preds = %entry, %for.body ; CHECK: function 'unsafe_Write_Write': ; CHECK-NEXT: for.body: ; CHECK-NEXT: Report: unsafe dependent memory operations in loop -; CHECK-NEXT: Interesting Dependences: +; CHECK-NEXT: Dependences: ; CHECK-NEXT: Backward: ; CHECK-NEXT: store i32 %0, i32* %arrayidx, align 4 -> ; CHECK-NEXT: store i32 %2, i32* %arrayidx3, align 4 @@ -230,7 +230,7 @@ for.body: ; preds = %entry, %for.body ; CHECK: function 'vectorizable_Read_Write': ; CHECK-NEXT: for.body: ; CHECK-NEXT: Memory dependences are safe -; CHECK-NEXT: Interesting Dependences: +; CHECK-NEXT: Dependences: ; CHECK-NEXT: BackwardVectorizable: ; CHECK-NEXT: %0 = load i32, i32* %arrayidx, align 4 -> ; CHECK-NEXT: store i32 %add, i32* %arrayidx2, align 4 @@ -269,7 +269,7 @@ for.body: ; preds = %entry, %for.body ; CHECK: function 'vectorizable_Write_Read': ; CHECK-NEXT: for.body: ; CHECK-NEXT: Memory dependences are safe -; CHECK-NEXT: Interesting Dependences: +; CHECK-NEXT: Dependences: ; CHECK-NEXT: BackwardVectorizable: ; CHECK-NEXT: store i32 %0, i32* %arrayidx, align 4 -> ; CHECK-NEXT: %1 = load i32, i32* %arrayidx2, align 4 @@ -307,7 +307,7 @@ for.body: ; preds = %entry, %for.body ; CHECK: function 'vectorizable_Write_Write': ; CHECK-NEXT: for.body: ; CHECK-NEXT: Memory dependences are safe -; CHECK-NEXT: Interesting Dependences: +; CHECK-NEXT: Dependences: ; CHECK-NEXT: BackwardVectorizable: ; CHECK-NEXT: store i32 %0, i32* %arrayidx, align 4 -> ; CHECK-NEXT: store i32 %2, i32* %arrayidx2, align 4 @@ -346,7 +346,7 @@ for.body: ; preds = %entry, %for.body ; CHECK: function 'vectorizable_unscaled_Read_Write': ; CHECK-NEXT: for.body: ; CHECK-NEXT: Report: unsafe dependent memory operations in loop -; CHECK-NEXT: Interesting Dependences: +; CHECK-NEXT: Dependences: ; CHECK-NEXT: BackwardVectorizableButPreventsForwarding: ; CHECK-NEXT: %2 = load i32, i32* %arrayidx, align 4 -> ; CHECK-NEXT: store i32 %add, i32* %arrayidx2, align 4 @@ -387,7 +387,7 @@ for.body: ; preds = %entry, %for.body ; CHECK: for function 'vectorizable_unscaled_Write_Read': ; CHECK-NEXT: for.body: ; CHECK-NEXT: Memory dependences are safe -; CHECK-NEXT: Interesting Dependences: +; CHECK-NEXT: Dependences: ; CHECK-NEXT: BackwardVectorizable: ; CHECK-NEXT: store i32 %2, i32* %arrayidx, align 4 -> ; CHECK-NEXT: %3 = load i32, i32* %arrayidx2, align 4 @@ -425,7 +425,7 @@ for.body: ; preds = %entry, %for.body ; CHECK: function 'unsafe_unscaled_Read_Write': ; CHECK-NEXT: for.body: ; CHECK-NEXT: Report: unsafe dependent memory operations in loop -; CHECK-NEXT: Interesting Dependences: +; CHECK-NEXT: Dependences: ; CHECK-NEXT: Backward: ; CHECK-NEXT: %2 = load i32, i32* %arrayidx, align 4 -> ; CHECK-NEXT: store i32 %add, i32* %arrayidx2, align 4 @@ -455,7 +455,7 @@ for.body: ; preds = %entry, %for.body ; CHECK: function 'unsafe_unscaled_Read_Write2': ; CHECK-NEXT: for.body: ; CHECK-NEXT: Report: unsafe dependent memory operations in loop -; CHECK-NEXT: Interesting Dependences: +; CHECK-NEXT: Dependences: ; CHECK-NEXT: Backward: ; CHECK-NEXT: %2 = load i32, i32* %arrayidx, align 4 -> ; CHECK-NEXT: store i32 %add, i32* %arrayidx2, align 4 @@ -505,7 +505,7 @@ for.body: ; preds = %entry, %for.body ; CHECK: function 'interleaved_stores': ; CHECK-NEXT: for.body: ; CHECK-NEXT: Report: unsafe dependent memory operations in loop -; CHECK-NEXT: Interesting Dependences: +; CHECK-NEXT: Dependences: ; CHECK-NEXT: Backward: ; CHECK-NEXT: store i32 %4, i32* %arrayidx5, align 4 -> ; CHECK-NEXT: store i32 %4, i32* %arrayidx9, align 4 diff --git a/test/Analysis/LoopAccessAnalysis/underlying-objects-2.ll b/test/Analysis/LoopAccessAnalysis/underlying-objects-2.ll index d0bed68188d..d388151365f 100644 --- a/test/Analysis/LoopAccessAnalysis/underlying-objects-2.ll +++ b/test/Analysis/LoopAccessAnalysis/underlying-objects-2.ll @@ -38,7 +38,7 @@ target triple = "x86_64-apple-macosx10.10.0" ; CHECK: for_j.body: ; CHECK-NEXT: Report: unsafe dependent memory operations in loop -; CHECK-NEXT: Interesting Dependences: +; CHECK-NEXT: Dependences: ; CHECK-NEXT: Backward: ; CHECK-NEXT: %loadB = load i8, i8* %gepB, align 1 -> ; CHECK-NEXT: store i8 2, i8* %gepB_plus_one, align 1 diff --git a/test/Analysis/LoopAccessAnalysis/unsafe-and-rt-checks.ll b/test/Analysis/LoopAccessAnalysis/unsafe-and-rt-checks.ll index 237cbc8b987..7157b954c5b 100644 --- a/test/Analysis/LoopAccessAnalysis/unsafe-and-rt-checks.ll +++ b/test/Analysis/LoopAccessAnalysis/unsafe-and-rt-checks.ll @@ -8,7 +8,7 @@ target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128" target triple = "x86_64-apple-macosx10.10.0" ; CHECK: Report: unsafe dependent memory operations in loop -; CHECK-NEXT: Interesting Dependences: +; CHECK-NEXT: Dependences: ; CHECK-NEXT: Backward: ; CHECK-NEXT: %loadA = load i16, i16* %arrayidxA, align 2 -> ; CHECK-NEXT: store i16 %mul1, i16* %arrayidxA_plus_2, align 2 -- 2.34.1