From: Hal Finkel Date: Wed, 15 Oct 2014 17:35:01 +0000 (+0000) Subject: [SLPVectorize] Basic ephemeral-value awareness X-Git-Url: http://plrg.eecs.uci.edu/git/?p=oota-llvm.git;a=commitdiff_plain;h=6c15862fd32a272b9ab1833de2cc8858e9036388 [SLPVectorize] Basic ephemeral-value awareness The SLP vectorizer should not vectorize ephemeral values. These are used to express information to the optimizer, and vectorizing them does not lead to faster code (because the ephemeral values are dropped prior to code generation, vectorized or not), and obscures the information the instructions are attempting to communicate (the logic that interprets the arguments to @llvm.assume generically does not understand vectorized conditions). Also, uses by ephemeral values are free (because they, and the necessary extractelement instructions, will be dropped prior to code generation). git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@219816 91177308-0d34-0410-b5e6-96231b3b80d8 --- diff --git a/lib/Transforms/Vectorize/SLPVectorizer.cpp b/lib/Transforms/Vectorize/SLPVectorizer.cpp index 76b46779535..16ba3167e8b 100644 --- a/lib/Transforms/Vectorize/SLPVectorizer.cpp +++ b/lib/Transforms/Vectorize/SLPVectorizer.cpp @@ -21,6 +21,8 @@ #include "llvm/ADT/SetVector.h" #include "llvm/ADT/Statistic.h" #include "llvm/Analysis/AliasAnalysis.h" +#include "llvm/Analysis/AssumptionTracker.h" +#include "llvm/Analysis/CodeMetrics.h" #include "llvm/Analysis/LoopInfo.h" #include "llvm/Analysis/ScalarEvolution.h" #include "llvm/Analysis/ScalarEvolutionExpressions.h" @@ -396,10 +398,12 @@ public: BoUpSLP(Function *Func, ScalarEvolution *Se, const DataLayout *Dl, TargetTransformInfo *Tti, TargetLibraryInfo *TLi, AliasAnalysis *Aa, - LoopInfo *Li, DominatorTree *Dt) + LoopInfo *Li, DominatorTree *Dt, AssumptionTracker *AT) : NumLoadsWantToKeepOrder(0), NumLoadsWantToChangeOrder(0), F(Func), SE(Se), DL(Dl), TTI(Tti), TLI(TLi), AA(Aa), LI(Li), DT(Dt), - Builder(Se->getContext()) {} + Builder(Se->getContext()) { + CodeMetrics::collectEphemeralValues(F, AT, EphValues); + } /// \brief Vectorize the tree that starts with the elements in \p VL. /// Returns the vectorized root. @@ -555,6 +559,9 @@ private: /// This list holds pairs of (Internal Scalar : External User). UserList ExternalUses; + /// Values used only by @llvm.assume calls. + SmallPtrSet EphValues; + /// Holds all of the instructions that we gathered. SetVector GatherSeq; /// A list of blocks that we are going to CSE. @@ -988,6 +995,16 @@ void BoUpSLP::buildTree_rec(ArrayRef VL, unsigned Depth) { // We now know that this is a vector of instructions of the same type from // the same block. + // Don't vectorize ephemeral values. + for (unsigned i = 0, e = VL.size(); i != e; ++i) { + if (EphValues.count(VL[i])) { + DEBUG(dbgs() << "SLP: The instruction (" << *VL[i] << + ") is ephemeral.\n"); + newTreeEntry(VL, false); + return; + } + } + // Check if this is a duplicate of another entry. if (ScalarToTreeEntry.count(VL[0])) { int Idx = ScalarToTreeEntry[VL[0]]; @@ -1710,6 +1727,12 @@ int BoUpSLP::getTreeCost() { if (!ExtractCostCalculated.insert(I->Scalar)) continue; + // Uses by ephemeral values are free (because the ephemeral value will be + // removed prior to code generation, and so the extraction will be + // removed as well). + if (EphValues.count(I->User)) + continue; + VectorType *VecTy = VectorType::get(I->Scalar->getType(), BundleWidth); ExtractCost += TTI->getVectorInstrCost(Instruction::ExtractElement, VecTy, I->Lane); @@ -2810,6 +2833,7 @@ struct SLPVectorizer : public FunctionPass { AliasAnalysis *AA; LoopInfo *LI; DominatorTree *DT; + AssumptionTracker *AT; bool runOnFunction(Function &F) override { if (skipOptnoneFunction(F)) @@ -2823,6 +2847,7 @@ struct SLPVectorizer : public FunctionPass { AA = &getAnalysis(); LI = &getAnalysis(); DT = &getAnalysis().getDomTree(); + AT = &getAnalysis(); StoreRefs.clear(); bool Changed = false; @@ -2845,7 +2870,7 @@ struct SLPVectorizer : public FunctionPass { // Use the bottom up slp vectorizer to construct chains that start with // store instructions. - BoUpSLP R(&F, SE, DL, TTI, TLI, AA, LI, DT); + BoUpSLP R(&F, SE, DL, TTI, TLI, AA, LI, DT, AT); // Scan the blocks in the function in post order. for (po_iterator it = po_begin(&F.getEntryBlock()), @@ -2872,6 +2897,7 @@ struct SLPVectorizer : public FunctionPass { void getAnalysisUsage(AnalysisUsage &AU) const override { FunctionPass::getAnalysisUsage(AU); + AU.addRequired(); AU.addRequired(); AU.addRequired(); AU.addRequired(); @@ -3746,6 +3772,7 @@ static const char lv_name[] = "SLP Vectorizer"; INITIALIZE_PASS_BEGIN(SLPVectorizer, SV_NAME, lv_name, false, false) INITIALIZE_AG_DEPENDENCY(AliasAnalysis) INITIALIZE_AG_DEPENDENCY(TargetTransformInfo) +INITIALIZE_PASS_DEPENDENCY(AssumptionTracker) INITIALIZE_PASS_DEPENDENCY(ScalarEvolution) INITIALIZE_PASS_DEPENDENCY(LoopSimplify) INITIALIZE_PASS_END(SLPVectorizer, SV_NAME, lv_name, false, false) diff --git a/test/Transforms/SLPVectorizer/X86/insert-element-build-vector.ll b/test/Transforms/SLPVectorizer/X86/insert-element-build-vector.ll index 9eda29f101a..0221613b970 100644 --- a/test/Transforms/SLPVectorizer/X86/insert-element-build-vector.ll +++ b/test/Transforms/SLPVectorizer/X86/insert-element-build-vector.ll @@ -35,6 +35,49 @@ define <4 x float> @simple_select(<4 x float> %a, <4 x float> %b, <4 x i32> %c) ret <4 x float> %rd } +declare void @llvm.assume(i1) nounwind + +; This entire tree is ephemeral, don't vectorize any of it. +define <4 x float> @simple_select_eph(<4 x float> %a, <4 x float> %b, <4 x i32> %c) #0 { +; CHECK-LABEL: @simple_select_eph( +; CHECK-NOT: icmp ne <4 x i32> +; CHECK-NOT: select <4 x i1> + %c0 = extractelement <4 x i32> %c, i32 0 + %c1 = extractelement <4 x i32> %c, i32 1 + %c2 = extractelement <4 x i32> %c, i32 2 + %c3 = extractelement <4 x i32> %c, i32 3 + %a0 = extractelement <4 x float> %a, i32 0 + %a1 = extractelement <4 x float> %a, i32 1 + %a2 = extractelement <4 x float> %a, i32 2 + %a3 = extractelement <4 x float> %a, i32 3 + %b0 = extractelement <4 x float> %b, i32 0 + %b1 = extractelement <4 x float> %b, i32 1 + %b2 = extractelement <4 x float> %b, i32 2 + %b3 = extractelement <4 x float> %b, i32 3 + %cmp0 = icmp ne i32 %c0, 0 + %cmp1 = icmp ne i32 %c1, 0 + %cmp2 = icmp ne i32 %c2, 0 + %cmp3 = icmp ne i32 %c3, 0 + %s0 = select i1 %cmp0, float %a0, float %b0 + %s1 = select i1 %cmp1, float %a1, float %b1 + %s2 = select i1 %cmp2, float %a2, float %b2 + %s3 = select i1 %cmp3, float %a3, float %b3 + %ra = insertelement <4 x float> undef, float %s0, i32 0 + %rb = insertelement <4 x float> %ra, float %s1, i32 1 + %rc = insertelement <4 x float> %rb, float %s2, i32 2 + %rd = insertelement <4 x float> %rc, float %s3, i32 3 + %q0 = extractelement <4 x float> %rd, i32 0 + %q1 = extractelement <4 x float> %rd, i32 1 + %q2 = extractelement <4 x float> %rd, i32 2 + %q3 = extractelement <4 x float> %rd, i32 3 + %q4 = fadd float %q0, %q1 + %q5 = fadd float %q2, %q3 + %q6 = fadd float %q4, %q5 + %qi = fcmp olt float %q6, %q5 + call void @llvm.assume(i1 %qi) + ret <4 x float> undef +} + ; Insert in an order different from the vector indices to make sure it ; doesn't matter define <4 x float> @simple_select_insert_out_of_order(<4 x float> %a, <4 x float> %b, <4 x i32> %c) #0 {