diff --git a/llvm/lib/Transforms/Vectorize/LoopVectorize.cpp b/llvm/lib/Transforms/Vectorize/LoopVectorize.cpp --- a/llvm/lib/Transforms/Vectorize/LoopVectorize.cpp +++ b/llvm/lib/Transforms/Vectorize/LoopVectorize.cpp @@ -115,6 +115,7 @@ #include "llvm/IR/IntrinsicInst.h" #include "llvm/IR/Intrinsics.h" #include "llvm/IR/LLVMContext.h" +#include "llvm/IR/MDBuilder.h" #include "llvm/IR/Metadata.h" #include "llvm/IR/Module.h" #include "llvm/IR/Operator.h" @@ -200,9 +201,10 @@ "enable-masked-interleaved-mem-accesses", cl::init(false), cl::Hidden, cl::desc("Enable vectorization on masked interleaved memory accesses in a loop")); -/// We don't interleave loops with a known constant trip count below this -/// number. -static const unsigned TinyTripCountInterleaveThreshold = 128; +static cl::opt TinyTripCountInterleaveThreshold( + "tiny-trip-count-interleave-threshold", cl::init(128), cl::Hidden, + cl::desc("We don't interleave loops with a estimated constant trip count " + "below this number")); static cl::opt ForceTargetNumScalarRegs( "force-target-num-scalar-regs", cl::init(0), cl::Hidden, @@ -502,6 +504,9 @@ /// Fix the non-induction PHIs in the OrigPHIsToFix vector. void fixNonInductionPHIs(void); + /// Update profile info of the vector and prolog/epilog loops. + void fixProfileInfo(); + protected: friend class LoopVectorizationPlanner; @@ -3457,6 +3462,8 @@ // Remove redundant induction instructions. cse(LoopVectorBody); + + fixProfileInfo(); } void InnerLoopVectorizer::fixCrossIterationPHIs() { @@ -3966,6 +3973,66 @@ } } +// Update profile info since expected TC of vectorized loop is less by VFxUF +// than original TC. At the same time original loop becomes prolog/epilog loop +// and may not have more than VFxUF iterations. +void InnerLoopVectorizer::fixProfileInfo() { + uint64_t OrigTakenCount = 0; + uint64_t OrigFallThroughCount = 0; + Loop *OrigLoop = LI->getLoopFor(LoopScalarBody); + auto *OrigBackBranchI = OrigLoop->getLoopLatch()->getTerminator(); + if (OrigBackBranchI->extractProfMetadata(OrigTakenCount, + OrigFallThroughCount) && + OrigFallThroughCount != 0) { + Loop *VecLoop = LI->getLoopFor(LoopVectorBody); + MDBuilder MDB(OrigBackBranchI->getContext()); + auto *VectorBackBranchI = VecLoop->getLoopLatch()->getTerminator(); + bool IsTrueBackEdgeOrigLoop = + OrigLoop->contains(*succ_begin(OrigLoop->getLoopLatch())); + bool IsTrueBackEdgeVecLoop = + VecLoop->contains(*succ_begin(VecLoop->getLoopLatch())); + + if (!IsTrueBackEdgeOrigLoop) + std::swap(OrigTakenCount, OrigFallThroughCount); + + // Uses of OrigIterCount bellow should not be simplified as it will + // produce a different value. In other words: (A mod N) * B != (A*B) mod N + const uint64_t OrigIterCount = OrigTakenCount / OrigFallThroughCount; + // Calculate taken and fall through counts for vector loop. + uint64_t VecTakenCount = (OrigIterCount / (VF * UF)) * OrigFallThroughCount; + uint64_t VecFallThrough = OrigFallThroughCount; + // Now calculate counters for prolog/epilog loop. + OrigTakenCount = (OrigIterCount % (VF * UF)) * OrigFallThroughCount; + + // Adjust number of iterations in vector and epilog loops if epilog + // iterations executed as part of the main loop. + if (OrigTakenCount != 0 && Cost->foldTailByMasking()) { + ++VecTakenCount; + OrigTakenCount = 0; + } + // Bottom test is never reached if loop has zero iterations. + if (VecTakenCount == 0) + VecFallThrough = 0; + // Bottom test is never reached if loop has zero iterations. + if (OrigTakenCount == 0) + OrigFallThroughCount = 0; + // Make a swap if back edge is taken when condition "false". + if (!IsTrueBackEdgeVecLoop) + std::swap(VecTakenCount, VecFallThrough); + // Set new profile metadata. + VectorBackBranchI->setMetadata( + LLVMContext::MD_prof, + MDB.createBranchWeights(VecTakenCount, VecFallThrough)); + // Make a swap if back edge is taken when condition "false". + if (!IsTrueBackEdgeOrigLoop) + std::swap(OrigTakenCount, OrigFallThroughCount); + // Set new profile metadata. + OrigBackBranchI->setMetadata( + LLVMContext::MD_prof, + MDB.createBranchWeights(OrigTakenCount, OrigFallThroughCount)); + } +} + void InnerLoopVectorizer::widenPHIInstruction(Instruction *PN, unsigned UF, unsigned VF) { PHINode *P = cast(PN); @@ -5143,8 +5210,8 @@ return 1; // Do not interleave loops with a relatively small trip count. - unsigned TC = PSE.getSE()->getSmallConstantTripCount(TheLoop); - if (TC > 1 && TC < TinyTripCountInterleaveThreshold) + auto BestKnownTC = getSmallBestKnownTC(*PSE.getSE(), TheLoop); + if (BestKnownTC && *BestKnownTC < TinyTripCountInterleaveThreshold) return 1; unsigned TargetNumRegisters = TTI.getNumberOfRegisters(VF > 1); @@ -5197,10 +5264,8 @@ // If the trip count is constant, limit the interleave count to be less than // the trip count divided by VF. - if (TC > 0) { - assert(TC >= VF && "VF exceeds trip count?"); - if ((TC / VF) < MaxInterleaveCount) - MaxInterleaveCount = (TC / VF); + if (BestKnownTC) { + MaxInterleaveCount = std::min(*BestKnownTC / VF, MaxInterleaveCount); } // If we did not calculate the cost for VF (because the user selected the VF) diff --git a/llvm/test/Transforms/LoopVectorize/X86/no_fpmath_with_hotness.ll b/llvm/test/Transforms/LoopVectorize/X86/no_fpmath_with_hotness.ll --- a/llvm/test/Transforms/LoopVectorize/X86/no_fpmath_with_hotness.ll +++ b/llvm/test/Transforms/LoopVectorize/X86/no_fpmath_with_hotness.ll @@ -3,7 +3,7 @@ ; CHECK: remark: no_fpmath.c:6:11: loop not vectorized: cannot prove it is safe to reorder floating-point operations (hotness: 300) ; CHECK: remark: no_fpmath.c:6:14: loop not vectorized -; CHECK: remark: no_fpmath.c:17:14: vectorized loop (vectorization width: 2, interleaved count: 2) (hotness: 300) +; CHECK: remark: no_fpmath.c:17:14: vectorized loop (vectorization width: 2, interleaved count: 1) (hotness: 300) target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128" target triple = "x86_64-apple-macosx10.10.0" diff --git a/llvm/test/Transforms/LoopVectorize/check-prof-info.ll b/llvm/test/Transforms/LoopVectorize/check-prof-info.ll new file mode 100644 --- /dev/null +++ b/llvm/test/Transforms/LoopVectorize/check-prof-info.ll @@ -0,0 +1,97 @@ +; NOTE: Assertions have been autogenerated by utils/update_test_checks.py +; RUN: opt -passes="print,loop-vectorize" -force-vector-width=4 -force-vector-interleave=1 -S < %s | FileCheck %s +; RUN: opt -passes="print,loop-vectorize" -prefer-predicate-over-epilog=true -force-vector-width=4 -force-vector-interleave=1 -S < %s | FileCheck %s -check-prefix=CHECK-MASKED + +target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128" +target triple = "x86_64-unknown-linux-gnu" + +@a = dso_local global [1024 x i32] zeroinitializer, align 16 +@b = dso_local global [1024 x i32] zeroinitializer, align 16 + +; Check correctness of profile info for vectorization without epilog. +; Function Attrs: nofree norecurse nounwind uwtable +define dso_local void @_Z3foov() local_unnamed_addr #0 { +; CHECK-LABEL: @_Z3foov( +; CHECK: [[VECTOR_BODY:vector\.body]]: +; CHECK: br i1 [[TMP:%.*]], label [[MIDDLE_BLOCK:%.*]], label %[[VECTOR_BODY]], !prof [[LP1_256:\!.*]], +; CHECK: [[FOR_BODY:for\.body]]: +; CHECK: br i1 [[EXITCOND:%.*]], label [[FOR_END_LOOPEXIT:%.*]], label %[[FOR_BODY]], !prof [[LP0_0:\!.*]], +; CHECK-MASKED: [[VECTOR_BODY:vector\.body]]: +; CHECK-MASKED: br i1 [[TMP:%.*]], label [[MIDDLE_BLOCK:%.*]], label %[[VECTOR_BODY]], !prof [[LP1_256:\!.*]], +; CHECK-MASKED: [[FOR_BODY:for\.body]]: +; CHECK-MASKED: br i1 [[EXITCOND:%.*]], label [[FOR_END_LOOPEXIT:%.*]], label %[[FOR_BODY]], !prof [[LP0_0:\!.*]], +; +entry: + br label %for.body + +for.cond.cleanup: ; preds = %for.body + ret void + +for.body: ; preds = %for.body, %entry + %indvars.iv = phi i64 [ 0, %entry ], [ %indvars.iv.next, %for.body ] + %arrayidx = getelementptr inbounds [1024 x i32], [1024 x i32]* @b, i64 0, i64 %indvars.iv + %0 = load i32, i32* %arrayidx, align 4, !tbaa !2 + %1 = trunc i64 %indvars.iv to i32 + %mul = mul nsw i32 %0, %1 + %arrayidx2 = getelementptr inbounds [1024 x i32], [1024 x i32]* @a, i64 0, i64 %indvars.iv + %2 = load i32, i32* %arrayidx2, align 4, !tbaa !2 + %add = add nsw i32 %2, %mul + store i32 %add, i32* %arrayidx2, align 4, !tbaa !2 + %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1 + %exitcond = icmp eq i64 %indvars.iv.next, 1024 + br i1 %exitcond, label %for.cond.cleanup, label %for.body, !prof !6 +} + +; Check correctness of profile info for vectorization with epilog. +; Function Attrs: nofree norecurse nounwind uwtable +define dso_local void @_Z3foo2v() local_unnamed_addr #0 { +; CHECK-LABEL: @_Z3foo2v( +; CHECK: [[VECTOR_BODY:vector\.body]]: +; CHECK: br i1 [[TMP:%.*]], label [[MIDDLE_BLOCK:%.*]], label %[[VECTOR_BODY]], !prof [[LP1_256:\!.*]], +; CHECK: [[FOR_BODY:for\.body]]: +; CHECK: br i1 [[EXITCOND:%.*]], label [[FOR_END_LOOPEXIT:%.*]], label %[[FOR_BODY]], !prof [[LP1_3:\!.*]], +; CHECK-MASKED: [[VECTOR_BODY:vector\.body]]: +; CHECK-MASKED: br i1 [[TMP:%.*]], label [[MIDDLE_BLOCK:%.*]], label %[[VECTOR_BODY]], !prof [[LP1_257:\!.*]], +; CHECK-MASKED: [[FOR_BODY:for\.body]]: +; CHECK-MASKED: br i1 [[EXITCOND:%.*]], label [[FOR_END_LOOPEXIT:%.*]], label %[[FOR_BODY]], !prof [[LP0_0:\!.*]], +; +entry: + br label %for.body + +for.cond.cleanup: ; preds = %for.body + ret void + +for.body: ; preds = %for.body, %entry + %indvars.iv = phi i64 [ 0, %entry ], [ %indvars.iv.next, %for.body ] + %arrayidx = getelementptr inbounds [1024 x i32], [1024 x i32]* @b, i64 0, i64 %indvars.iv + %0 = load i32, i32* %arrayidx, align 4, !tbaa !2 + %1 = trunc i64 %indvars.iv to i32 + %mul = mul nsw i32 %0, %1 + %arrayidx2 = getelementptr inbounds [1024 x i32], [1024 x i32]* @a, i64 0, i64 %indvars.iv + %2 = load i32, i32* %arrayidx2, align 4, !tbaa !2 + %add = add nsw i32 %2, %mul + store i32 %add, i32* %arrayidx2, align 4, !tbaa !2 + %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1 + %exitcond = icmp eq i64 %indvars.iv.next, 1027 + br i1 %exitcond, label %for.cond.cleanup, label %for.body, !prof !7 +} + +attributes #0 = { "use-soft-float"="false" } + +!llvm.module.flags = !{!0} +!llvm.ident = !{!1} + +; CHECK: [[LP1_256]] = !{!"branch_weights", i32 1, i32 256} +; CHECK: [[LP0_0]] = !{!"branch_weights", i32 0, i32 0} +; CHECK-MASKED: [[LP0_0]] = !{!"branch_weights", i32 0, i32 0} +; CHECK: [[LP1_3]] = !{!"branch_weights", i32 1, i32 3} +; CHECK-MASKED: [[LP1_257]] = !{!"branch_weights", i32 1, i32 257} + +!0 = !{i32 1, !"wchar_size", i32 4} +!1 = !{!"clang version 10.0.0 (https://github.com/llvm/llvm-project c292b5b5e059e6ce3e6449e6827ef7e1037c21c4)"} +!2 = !{!3, !3, i64 0} +!3 = !{!"int", !4, i64 0} +!4 = !{!"omnipotent char", !5, i64 0} +!5 = !{!"Simple C++ TBAA"} +!6 = !{!"branch_weights", i32 1, i32 1024} +!7 = !{!"branch_weights", i32 1, i32 1027} diff --git a/llvm/test/Transforms/LoopVectorize/hot_short_tc_loop.ll b/llvm/test/Transforms/LoopVectorize/hot_short_tc_loop.ll --- a/llvm/test/Transforms/LoopVectorize/hot_short_tc_loop.ll +++ b/llvm/test/Transforms/LoopVectorize/hot_short_tc_loop.ll @@ -13,12 +13,16 @@ ; Function Attrs: uwtable define dso_local void @_Z3fooi(i32 %M) local_unnamed_addr #0 !prof !11 { +; CHECK-LABEL: @_Z3fooi( +; CHECK: [[VECTOR_BODY:vector\.body]]: ; CHECK: [[WIDE_LOAD:%.*]] = load <4 x i32>, <4 x i32>* [[TMP15:%.*]] ; CHECK: [[TMP18:%.*]] = mul nsw <4 x i32> [[WIDE_LOAD]], [[VEC_IND6:%.*]] ; CHECK: [[WIDE_LOAD10:%.*]] = load <4 x i32>, <4 x i32>* [[TMP23:%.*]] ; CHECK: [[TMP26:%.*]] = add nsw <4 x i32> [[WIDE_LOAD10]], [[TMP18]] ; CHECK: store <4 x i32> [[TMP26]], <4 x i32>* [[TMP28:%.*]] -; +; CHECK: br i1 [[TMP30:%.*]], label [[MIDDLE_BLOCK:%.*]], label %[[VECTOR_BODY]], !prof [[LP12:\!.*]], +; CHECK: [[SCAL_BODY:for\.body4\.us]]: +; CHECK: br i1 [[EXITCOND:%.*]], label [[FOR_COND1_FOR_COND_CLEANUP3_CRIT_EDGE_US:%.*]], label %[[SCAL_BODY]], !prof [[LP15:\!.*]], entry: %a = alloca [5 x i32], align 16 %b = alloca [5 x i32], align 16 @@ -74,6 +78,7 @@ ; Function Attrs: uwtable define dso_local void @_Z3fooi2() local_unnamed_addr #0 !prof !11 { +; CHECK-LABEL: @_Z3fooi2( ; CHECK: [[WIDE_LOAD:%.*]] = load <4 x i32>, <4 x i32>* [[TMP15:%.*]] ; CHECK: [[TMP18:%.*]] = mul nsw <4 x i32> [[WIDE_LOAD]], [[VEC_IND6:%.*]] ; CHECK: [[WIDE_LOAD10:%.*]] = load <4 x i32>, <4 x i32>* [[TMP23:%.*]] @@ -118,11 +123,14 @@ ; Function Attrs: uwtable define dso_local void @_Z3fooi3(i32 %M) local_unnamed_addr #0 !prof !11 { +; CHECK-LABEL: @_Z3fooi3( +; CHECK: [[SCAL_BODY:for\.body4\.us]]: ; CHECK: [[TMP2:%.*]] = load i32, i32* [[ARRAYIDX_US:%.*]] ; CHECK: [[MUL_US:%.*]] = mul nsw i32 [[TMP2]], [[TMP3:%.*]] ; CHECK: [[TMP4:%.*]] = load i32, i32* [[ARRAYIDX6_US:%.*]] ; CHECK: [[ADD_US:%.*]] = add nsw i32 [[TMP4]], [[MUL_US]] ; CHECK: store i32 [[ADD_US]], i32* [[ARRAYIDX6_US]] +; CHECK: br i1 [[EXITCOND:%.*]], label [[FOR_COND1_FOR_COND_CLEANUP3_CRIT_EDGE_US:%.*]], label %[[SCAL_BODY]], !prof [[LP26:\!.*]] ; entry: %a = alloca [5 x i32], align 16 @@ -188,6 +196,10 @@ !llvm.module.flags = !{!0} !llvm.ident = !{!1} +; CHECK: [[LP12]] = !{!"branch_weights", i32 0, i32 0} +; CHECK: [[LP15]] = !{!"branch_weights", i32 999, i32 4995} +; CHECK: [[LP26]] = !{!"branch_weights", i32 9, i32 45} + !0 = !{i32 1, !"wchar_size", i32 4} !1 = !{!"clang version 10.0.0 (https://github.com/llvm/llvm-project f379dd57b978c4e1483d721f422c79e3c0c5ccdc)"} !2 = !{!3, !3, i64 0} diff --git a/llvm/test/Transforms/LoopVectorize/interleave_short_tc.ll b/llvm/test/Transforms/LoopVectorize/interleave_short_tc.ll new file mode 100644 --- /dev/null +++ b/llvm/test/Transforms/LoopVectorize/interleave_short_tc.ll @@ -0,0 +1,70 @@ +; Check that we won't interleave by more than "best known" estimated trip count. + +; The loop is expected to be vectorized by 4 and interleaving suppresed due to +; short trip count which is controled by "tiny-trip-count-interleave-threshold". +; RUN: opt -passes=loop-vectorize -force-vector-width=4 -vectorizer-min-trip-count=4 -S < %s | FileCheck %s +; +; The loop is expected to be vectorized by 4 and computed interleaving factor is 1. +; Thus the resulting step is 4. +; RUN: opt -passes=loop-vectorize -force-vector-width=4 -vectorizer-min-trip-count=4 -tiny-trip-count-interleave-threshold=4 -S < %s | FileCheck %s + +; The loop is expected to be vectorized by 2 and computed interleaving factor is 2. +; Thus the resulting step is 4. +; RUN: opt -passes=loop-vectorize -force-vector-width=2 -vectorizer-min-trip-count=4 -tiny-trip-count-interleave-threshold=4 -S < %s | FileCheck %s + +; Check that we won't interleave by more than "best known" estimated trip count. + +target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128" +target triple = "x86_64-unknown-linux-gnu" + +@a = dso_local global [5 x i32] zeroinitializer, align 16 +@b = dso_local global [5 x i32] zeroinitializer, align 16 + +; Function Attrs: nofree norecurse nounwind uwtable +define dso_local void @_Z3fooi(i32 %M) local_unnamed_addr #0 { +; CHECK-LABEL: @_Z3fooi( +; CHECK: [[VECTOR_BODY:vector\.body]]: +; CHECK: [[INDEX:%.*]] = phi i64 [ 0, [[VECTOR_PH:%.*]] ], [ [[INDEX_NEXT:%.*]], %[[VECTOR_BODY]] ] +; CHECK: [[INDEX_NEXT]] = add i64 [[INDEX]], 4 +; +entry: + %cmp8 = icmp sgt i32 %M, 0 + br i1 %cmp8, label %for.body.preheader, label %for.cond.cleanup + +for.body.preheader: ; preds = %entry + %wide.trip.count = zext i32 %M to i64 + br label %for.body + +for.cond.cleanup.loopexit: ; preds = %for.body + br label %for.cond.cleanup + +for.cond.cleanup: ; preds = %for.cond.cleanup.loopexit, %entry + ret void + +for.body: ; preds = %for.body, %for.body.preheader + %indvars.iv = phi i64 [ 0, %for.body.preheader ], [ %indvars.iv.next, %for.body ] + %arrayidx = getelementptr inbounds [5 x i32], [5 x i32]* @b, i64 0, i64 %indvars.iv + %0 = load i32, i32* %arrayidx, align 4, !tbaa !2 + %1 = trunc i64 %indvars.iv to i32 + %mul = mul nsw i32 %0, %1 + %arrayidx2 = getelementptr inbounds [5 x i32], [5 x i32]* @a, i64 0, i64 %indvars.iv + %2 = load i32, i32* %arrayidx2, align 4, !tbaa !2 + %add = add nsw i32 %2, %mul + store i32 %add, i32* %arrayidx2, align 4, !tbaa !2 + %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1 + %exitcond = icmp eq i64 %indvars.iv.next, %wide.trip.count + br i1 %exitcond, label %for.cond.cleanup.loopexit, label %for.body, !prof !6 +} + +attributes #0 = { "use-soft-float"="false" } + +!llvm.module.flags = !{!0} +!llvm.ident = !{!1} + +!0 = !{i32 1, !"wchar_size", i32 4} +!1 = !{!"clang version 10.0.0 (https://github.com/llvm/llvm-project c292b5b5e059e6ce3e6449e6827ef7e1037c21c4)"} +!2 = !{!3, !3, i64 0} +!3 = !{!"int", !4, i64 0} +!4 = !{!"omnipotent char", !5, i64 0} +!5 = !{!"Simple C++ TBAA"} +!6 = !{!"branch_weights", i32 1, i32 5} diff --git a/llvm/test/Transforms/LoopVectorize/tripcount.ll b/llvm/test/Transforms/LoopVectorize/tripcount.ll --- a/llvm/test/Transforms/LoopVectorize/tripcount.ll +++ b/llvm/test/Transforms/LoopVectorize/tripcount.ll @@ -61,8 +61,10 @@ ; but has a high trip count per invocation. Vectorize it. ; CHECK-LABEL: @foo_low_trip_count3( -; CHECK: vector.body: - +; CHECK: [[VECTOR_BODY:vector\.body]]: +; CHECK: br i1 [[TMP9:%.*]], label [[MIDDLE_BLOCK:%.*]], label %[[VECTOR_BODY]], !prof [[LP3:\!.*]], +; CHECK: [[FOR_BODY:for\.body]]: +; CHECK: br i1 [[EXITCOND:%.*]], label [[FOR_END_LOOPEXIT:%.*]], label %[[FOR_BODY]], !prof [[LP6:\!.*]], entry: br i1 %cond, label %for.preheader, label %for.end, !prof !2 @@ -205,6 +207,9 @@ ret i32 0 } +; CHECK: [[LP3]] = !{!"branch_weights", i32 10, i32 2500} +; CHECK: [[LP6]] = !{!"branch_weights", i32 0, i32 0} + !0 = !{!"function_entry_count", i64 100} !1 = !{!"branch_weights", i32 100, i32 0} !2 = !{!"branch_weights", i32 10, i32 90}