From 1d2ad834f2ff2bc5620dbba83dce6d2477023429 Mon Sep 17 00:00:00 2001 From: Nadav Rotem Date: Sat, 20 Apr 2013 06:13:47 +0000 Subject: [PATCH] SLPVectorizer: Improve the cost model for loop invariant broadcast values. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@179930 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Transforms/Vectorize/SLPVectorizer.cpp | 2 +- lib/Transforms/Vectorize/VecUtils.cpp | 31 ++++++-- lib/Transforms/Vectorize/VecUtils.h | 6 +- .../SLPVectorizer/X86/loopinvariant.ll | 73 +++++++++++++++++++ 4 files changed, 101 insertions(+), 11 deletions(-) create mode 100644 test/Transforms/SLPVectorizer/X86/loopinvariant.ll diff --git a/lib/Transforms/Vectorize/SLPVectorizer.cpp b/lib/Transforms/Vectorize/SLPVectorizer.cpp index a9ec243bc01..024dd337ac1 100644 --- a/lib/Transforms/Vectorize/SLPVectorizer.cpp +++ b/lib/Transforms/Vectorize/SLPVectorizer.cpp @@ -83,7 +83,7 @@ struct SLPVectorizer : public FunctionPass { // Use the bollom up slp vectorizer to construct chains that start with // he store instructions. - BoUpSLP R(BB, SE, DL, TTI, AA); + BoUpSLP R(BB, SE, DL, TTI, AA, LI->getLoopFor(BB)); // Vectorize trees that end at reductions. BBChanged |= vectorizeReductions(BB, R); diff --git a/lib/Transforms/Vectorize/VecUtils.cpp b/lib/Transforms/Vectorize/VecUtils.cpp index c08bed71706..244af394b1c 100644 --- a/lib/Transforms/Vectorize/VecUtils.cpp +++ b/lib/Transforms/Vectorize/VecUtils.cpp @@ -18,6 +18,7 @@ #include "llvm/Analysis/ScalarEvolutionExpressions.h" #include "llvm/Analysis/TargetTransformInfo.h" #include "llvm/Analysis/Verifier.h" +#include "llvm/Analysis/LoopInfo.h" #include "llvm/IR/Constants.h" #include "llvm/IR/DataLayout.h" #include "llvm/IR/Function.h" @@ -44,8 +45,8 @@ static const unsigned RecursionMaxDepth = 6; namespace llvm { BoUpSLP::BoUpSLP(BasicBlock *Bb, ScalarEvolution *S, DataLayout *Dl, - TargetTransformInfo *Tti, AliasAnalysis *Aa) : - BB(Bb), SE(S), DL(Dl), TTI(Tti), AA(Aa) { + TargetTransformInfo *Tti, AliasAnalysis *Aa, Loop *Lp) : + BB(Bb), SE(S), DL(Dl), TTI(Tti), AA(Aa), L(Lp) { numberInstructions(); } @@ -121,7 +122,7 @@ bool BoUpSLP::vectorizeStoreChain(ValueList &Chain, int CostThreshold) { if (Cost < CostThreshold) { DEBUG(dbgs() << "SLP: Decided to vectorize cost=" << Cost << "\n"); vectorizeTree(Operands, VF); - i += VF; + i += VF - 1; Changed = true; } } @@ -381,13 +382,15 @@ int BoUpSLP::getTreeCost_rec(ValueList &VL, unsigned Depth) { // Check if all of the operands are constants. bool AllConst = true; bool AllSameScalar = true; + bool MustScalarizeFlag = false; for (unsigned i = 0, e = VL.size(); i < e; ++i) { AllConst &= isa(VL[i]); AllSameScalar &= (VL[0] == VL[i]); // Must have a single use. Instruction *I = dyn_cast(VL[i]); - // This instruction is outside the basic block or if it is a known hazard. - if (MustScalarize.count(VL[i]) || (I && I->getParent() != BB)) + MustScalarizeFlag |= MustScalarize.count(VL[i]); + // This instruction is outside the basic block. + if (I && I->getParent() != BB) return getScalarizationCost(VecTy); } @@ -395,11 +398,23 @@ int BoUpSLP::getTreeCost_rec(ValueList &VL, unsigned Depth) { if (AllConst) return 0; // If all of the operands are identical we can broadcast them. - if (AllSameScalar) + Instruction *VL0 = dyn_cast(VL[0]); + if (AllSameScalar) { + // If we are in a loop, and this is not an instruction (e.g. constant or + // argument) or the instruction is defined outside the loop then assume + // that the cost is zero. + if (L && (!VL0 || !L->contains(VL0))) + return 0; + + // We need to broadcast the scalar. return TTI->getShuffleCost(TargetTransformInfo::SK_Broadcast, VecTy, 0); + } + + // If this is not a constant, or a scalar from outside the loop then we + // need to scalarize it. + if (MustScalarizeFlag) + return getScalarizationCost(VecTy); - // Scalarize unknown structures. - Instruction *VL0 = dyn_cast(VL[0]); if (!VL0) return getScalarizationCost(VecTy); assert(VL0->getParent() == BB && "Wrong BB"); diff --git a/lib/Transforms/Vectorize/VecUtils.h b/lib/Transforms/Vectorize/VecUtils.h index 3f6866407a6..c756bd3968d 100644 --- a/lib/Transforms/Vectorize/VecUtils.h +++ b/lib/Transforms/Vectorize/VecUtils.h @@ -27,6 +27,7 @@ class BasicBlock; class Instruction; class Type; class VectorType; class StoreInst; class Value; class ScalarEvolution; class DataLayout; class TargetTransformInfo; class AliasAnalysis; +class Loop; /// Bottom Up SLP vectorization utility class. struct BoUpSLP { @@ -37,7 +38,7 @@ struct BoUpSLP { // \brief C'tor. BoUpSLP(BasicBlock *Bb, ScalarEvolution *Se, DataLayout *Dl, - TargetTransformInfo *Tti, AliasAnalysis *Aa); + TargetTransformInfo *Tti, AliasAnalysis *Aa, Loop *Lp); /// \brief Take the pointer operand from the Load/Store instruction. /// \returns NULL if this is not a valid Load/Store instruction. @@ -112,7 +113,7 @@ private: /// \returns a vector from a collection of scalars in \p VL. Value *Scalarize(ValueList &VL, VectorType *Ty); - + private: /// Maps instructions to numbers and back. SmallDenseMap InstrIdx; @@ -155,6 +156,7 @@ private: DataLayout *DL; TargetTransformInfo *TTI; AliasAnalysis *AA; + Loop *L; }; } // end of namespace diff --git a/test/Transforms/SLPVectorizer/X86/loopinvariant.ll b/test/Transforms/SLPVectorizer/X86/loopinvariant.ll new file mode 100644 index 00000000000..329a349af81 --- /dev/null +++ b/test/Transforms/SLPVectorizer/X86/loopinvariant.ll @@ -0,0 +1,73 @@ +; RUN: opt < %s -basicaa -slp-vectorizer -dce -S -mtriple=x86_64-apple-macosx10.8.0 -mcpu=corei7-avx | FileCheck %s + +target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128" +target triple = "x86_64-apple-macosx10.8.0" + +;CHECK: @foo +;CHECK: load <4 x i32> +;CHECK: add <4 x i32> +;CHECK: store <4 x i32> +;CHECK: load <4 x i32> +;CHECK: add <4 x i32> +;CHECK: store <4 x i32> +;CHECK: ret +define i32 @foo(i32* nocapture %A, i32 %n) #0 { +entry: + %cmp62 = icmp sgt i32 %n, 0 + br i1 %cmp62, label %for.body, label %for.end + +for.body: ; preds = %entry, %for.body + %indvars.iv = phi i64 [ %indvars.iv.next, %for.body ], [ 0, %entry ] + %arrayidx = getelementptr inbounds i32* %A, i64 %indvars.iv + %0 = load i32* %arrayidx, align 4, !tbaa !0 + %add1 = add nsw i32 %0, %n + store i32 %add1, i32* %arrayidx, align 4, !tbaa !0 + %1 = or i64 %indvars.iv, 1 + %arrayidx4 = getelementptr inbounds i32* %A, i64 %1 + %2 = load i32* %arrayidx4, align 4, !tbaa !0 + %add5 = add nsw i32 %2, %n + store i32 %add5, i32* %arrayidx4, align 4, !tbaa !0 + %3 = or i64 %indvars.iv, 2 + %arrayidx8 = getelementptr inbounds i32* %A, i64 %3 + %4 = load i32* %arrayidx8, align 4, !tbaa !0 + %add9 = add nsw i32 %4, %n + store i32 %add9, i32* %arrayidx8, align 4, !tbaa !0 + %5 = or i64 %indvars.iv, 3 + %arrayidx12 = getelementptr inbounds i32* %A, i64 %5 + %6 = load i32* %arrayidx12, align 4, !tbaa !0 + %add13 = add nsw i32 %6, %n + store i32 %add13, i32* %arrayidx12, align 4, !tbaa !0 + %7 = or i64 %indvars.iv, 4 + %arrayidx16 = getelementptr inbounds i32* %A, i64 %7 + %8 = load i32* %arrayidx16, align 4, !tbaa !0 + %add17 = add nsw i32 %8, %n + store i32 %add17, i32* %arrayidx16, align 4, !tbaa !0 + %9 = or i64 %indvars.iv, 5 + %arrayidx20 = getelementptr inbounds i32* %A, i64 %9 + %10 = load i32* %arrayidx20, align 4, !tbaa !0 + %add21 = add nsw i32 %10, %n + store i32 %add21, i32* %arrayidx20, align 4, !tbaa !0 + %11 = or i64 %indvars.iv, 6 + %arrayidx24 = getelementptr inbounds i32* %A, i64 %11 + %12 = load i32* %arrayidx24, align 4, !tbaa !0 + %add25 = add nsw i32 %12, %n + store i32 %add25, i32* %arrayidx24, align 4, !tbaa !0 + %13 = or i64 %indvars.iv, 7 + %arrayidx28 = getelementptr inbounds i32* %A, i64 %13 + %14 = load i32* %arrayidx28, align 4, !tbaa !0 + %add29 = add nsw i32 %14, %n + store i32 %add29, i32* %arrayidx28, align 4, !tbaa !0 + %indvars.iv.next = add i64 %indvars.iv, 8 + %15 = trunc i64 %indvars.iv.next to i32 + %cmp = icmp slt i32 %15, %n + br i1 %cmp, label %for.body, label %for.end + +for.end: ; preds = %for.body, %entry + ret i32 undef +} + +attributes #0 = { nounwind ssp uwtable "less-precise-fpmad"="false" "no-frame-pointer-elim"="true" "no-frame-pointer-elim-non-leaf"="true" "no-infs-fp-math"="false" "no-nans-fp-math"="false" "unsafe-fp-math"="false" "use-soft-float"="false" } + +!0 = metadata !{metadata !"int", metadata !1} +!1 = metadata !{metadata !"omnipotent char", metadata !2} +!2 = metadata !{metadata !"Simple C/C++ TBAA"} -- 2.34.1