aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorNadav Rotem <nrotem@apple.com>2013-06-28 22:07:09 +0000
committerNadav Rotem <nrotem@apple.com>2013-06-28 22:07:09 +0000
commitac2678684689448d1c88f644f3fa88aa4f93997c (patch)
tree8fcb1782712faf5f102e7f3840a5918e2cd1811f
parentc09324483cf8c8904b7250f072d8f64e9b00656e (diff)
downloadexternal_llvm-ac2678684689448d1c88f644f3fa88aa4f93997c.zip
external_llvm-ac2678684689448d1c88f644f3fa88aa4f93997c.tar.gz
external_llvm-ac2678684689448d1c88f644f3fa88aa4f93997c.tar.bz2
SLP Vectorizer: Add support for trees with external users.
To support this we have to insert 'extractelement' instructions to pick the right lane. We had this functionality before but I removed it when we moved to the multi-block design because it was too complicated. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@185230 91177308-0d34-0410-b5e6-96231b3b80d8
-rw-r--r--lib/Transforms/Vectorize/SLPVectorizer.cpp166
-rw-r--r--test/Transforms/SLPVectorizer/X86/cse.ll11
-rw-r--r--test/Transforms/SLPVectorizer/X86/external_user.ll61
-rw-r--r--test/Transforms/SLPVectorizer/X86/phi.ll51
4 files changed, 259 insertions, 30 deletions
diff --git a/lib/Transforms/Vectorize/SLPVectorizer.cpp b/lib/Transforms/Vectorize/SLPVectorizer.cpp
index 35df668..03b9679 100644
--- a/lib/Transforms/Vectorize/SLPVectorizer.cpp
+++ b/lib/Transforms/Vectorize/SLPVectorizer.cpp
@@ -221,6 +221,11 @@ public:
return false;
}
+ void forgetNumbering() {
+ for (Function::iterator it = F->begin(), e = F->end(); it != e; ++it)
+ BlocksNumbers[it].forget();
+ }
+
/// -- Vectorization State --
/// Maps values in the tree to the vector lanes that uses them. This map must
@@ -243,9 +248,20 @@ public:
/// to stop cycles in the graph.
ValueSet VisitedPHIs;
- /// Contains a list of values that are used outside the current tree. This
+ /// Contains a list of values that are used outside the current tree, the
+ /// first element in the bundle and the insertion point for extracts. This
/// set must be reset between runs.
- SetVector<Value *> MultiUserVals;
+ struct UseInfo{
+ UseInfo(Instruction *VL0, int I) :
+ Leader(VL0), LastIndex(I) {}
+ UseInfo() : Leader(0), LastIndex(0) {}
+ /// The first element in the bundle.
+ Instruction *Leader;
+ /// The insertion index.
+ int LastIndex;
+ };
+ MapVector<Instruction*, UseInfo> MultiUserVals;
+ SetVector<Instruction*> ExtractedLane;
/// Holds all of the instructions that we gathered.
SetVector<Instruction *> GatherSeq;
@@ -460,6 +476,7 @@ void FuncSLP::getTreeUses_rec(ArrayRef<Value *> VL, unsigned Depth) {
assert(VL0 && "Invalid instruction");
// Mark instructions with multiple users.
+ int LastIndex = getLastIndex(VL);
for (unsigned i = 0, e = VL.size(); i < e; ++i) {
if (PHINode *PN = dyn_cast<PHINode>(VL[i])) {
unsigned NumUses = 0;
@@ -474,7 +491,8 @@ void FuncSLP::getTreeUses_rec(ArrayRef<Value *> VL, unsigned Depth) {
if (NumUses > 1) {
DEBUG(dbgs() << "SLP: Adding PHI to MultiUserVals "
"because it has " << NumUses << " users:" << *PN << " \n");
- MultiUserVals.insert(PN);
+ UseInfo UI(VL0, 0);
+ MultiUserVals[PN] = UI;
}
continue;
}
@@ -486,7 +504,8 @@ void FuncSLP::getTreeUses_rec(ArrayRef<Value *> VL, unsigned Depth) {
if (Depth && I && I->getNumUses() > 1) {
DEBUG(dbgs() << "SLP: Adding to MultiUserVals "
"because it has " << I->getNumUses() << " users:" << *I << " \n");
- MultiUserVals.insert(I);
+ UseInfo UI(VL0, LastIndex);
+ MultiUserVals[I] = UI;
}
}
@@ -678,6 +697,14 @@ int FuncSLP::getTreeCost_rec(ArrayRef<Value *> VL, unsigned Depth) {
}
}
+
+ // Calculate the extract cost.
+ unsigned ExternalUserExtractCost = 0;
+ for (unsigned i = 0, e = VL.size(); i < e; ++i)
+ if (ExtractedLane.count(cast<Instruction>(VL[i])))
+ ExternalUserExtractCost +=
+ TTI->getVectorInstrCost(Instruction::ExtractElement, VecTy, i);
+
Instruction *VL0 = cast<Instruction>(VL[0]);
switch (Opcode) {
case Instruction::PHI: {
@@ -707,7 +734,7 @@ int FuncSLP::getTreeCost_rec(ArrayRef<Value *> VL, unsigned Depth) {
return GatherCost;
}
- return TotalCost;
+ return TotalCost + ExternalUserExtractCost;
}
case Instruction::ExtractElement: {
if (CanReuseExtract(VL, VL.size(), VecTy))
@@ -737,8 +764,8 @@ int FuncSLP::getTreeCost_rec(ArrayRef<Value *> VL, unsigned Depth) {
}
int Cost = getTreeCost_rec(Operands, Depth + 1);
- if (Cost == FuncSLP::MAX_COST)
- return Cost;
+ if (Cost == MAX_COST)
+ return MAX_COST;
// Calculate the cost of this instruction.
int ScalarCost = VL.size() * TTI->getCastInstrCost(VL0->getOpcode(),
@@ -753,7 +780,7 @@ int FuncSLP::getTreeCost_rec(ArrayRef<Value *> VL, unsigned Depth) {
return GatherCost;
}
- return Cost;
+ return Cost + ExternalUserExtractCost;
}
case Instruction::FCmp:
case Instruction::ICmp: {
@@ -821,7 +848,7 @@ int FuncSLP::getTreeCost_rec(ArrayRef<Value *> VL, unsigned Depth) {
return GatherCost;
}
- return TotalCost;
+ return TotalCost + ExternalUserExtractCost;
}
case Instruction::Load: {
// If we are scalarize the loads, add the cost of forming the vector.
@@ -840,7 +867,7 @@ int FuncSLP::getTreeCost_rec(ArrayRef<Value *> VL, unsigned Depth) {
return GatherCost;
}
- return TotalCost;
+ return TotalCost + ExternalUserExtractCost;
}
case Instruction::Store: {
// We know that we can merge the stores. Calculate the cost.
@@ -860,7 +887,7 @@ int FuncSLP::getTreeCost_rec(ArrayRef<Value *> VL, unsigned Depth) {
return MAX_COST;
int TotalCost = StoreCost + Cost;
- return TotalCost;
+ return TotalCost + ExternalUserExtractCost;
}
default:
// Unable to vectorize unknown instructions.
@@ -874,6 +901,7 @@ int FuncSLP::getTreeCost(ArrayRef<Value *> VL) {
MemBarrierIgnoreList.clear();
LaneMap.clear();
MultiUserVals.clear();
+ ExtractedLane.clear();
MustGather.clear();
VisitedPHIs.clear();
@@ -893,21 +921,58 @@ int FuncSLP::getTreeCost(ArrayRef<Value *> VL) {
// must be scalarized.
getTreeUses_rec(VL, 0);
- // Check that instructions with multiple users can be vectorized. Mark unsafe
- // instructions.
- for (SetVector<Value *>::iterator it = MultiUserVals.begin(),
- e = MultiUserVals.end();
- it != e; ++it) {
+ // Check that instructions with multiple users can be vectorized. Mark
+ // unsafe instructions.
+ for (MapVector<Instruction *, UseInfo>::iterator UI = MultiUserVals.begin(),
+ e = MultiUserVals.end(); UI != e; ++UI) {
+ Instruction *Scalar = UI->first;
+
+ if (MustGather.count(Scalar))
+ continue;
+
+ assert(LaneMap.count(Scalar) && "Unknown scalar");
+ int ScalarLane = LaneMap[Scalar];
+
+ bool ExternalUse = false;
// Check that all of the users of this instr are within the tree.
- for (Value::use_iterator I = (*it)->use_begin(), E = (*it)->use_end();
- I != E; ++I) {
- if (LaneMap.find(*I) == LaneMap.end()) {
- DEBUG(dbgs() << "SLP: Adding to MustExtract "
- "because of an out of tree usage.\n");
- MustGather.insert(*it);
+ for (Value::use_iterator Usr = Scalar->use_begin(),
+ UE = Scalar->use_end(); Usr != UE; ++Usr) {
+ // If this user is within the tree, make sure it is from the same lane.
+ // Notice that we have both in-tree and out-of-tree users.
+ if (LaneMap.count(*Usr)) {
+ if (LaneMap[*Usr] != ScalarLane) {
+ DEBUG(dbgs() << "SLP: Adding to MustExtract "
+ "because of an out-of-lane usage.\n");
+ MustGather.insert(Scalar);
+ break;
+ }
continue;
}
+
+ // We have an out-of-tree user. Check if we can place an 'extract'.
+ Instruction *User = cast<Instruction>(*Usr);
+ // We care about the order only if the user is in the same block.
+ if (User->getParent() == Scalar->getParent()) {
+ int LastLoc = UI->second.LastIndex;
+ BlockNumbering &BN = BlocksNumbers[User->getParent()];
+ int UserIdx = BN.getIndex(User);
+ if (UserIdx <= LastLoc) {
+ DEBUG(dbgs() << "SLP: Adding to MustExtract because of an external "
+ "user that we can't schedule.\n");
+ MustGather.insert(Scalar);
+ break;
+ }
+ }
+ // We have an external user.
+ ExternalUse = true;
+ }
+
+ if (ExternalUse) {
+ // Items that are left in MultiUserVals are to be extracted.
+ // ExtractLane is used for the lookup.
+ ExtractedLane.insert(Scalar);
}
+
}
// Now calculate the cost of vectorizing the tree.
@@ -1238,10 +1303,58 @@ Value *FuncSLP::vectorizeTree(ArrayRef<Value *> VL) {
Builder.SetInsertPoint(getLastInstruction(VL));
Value *V = vectorizeTree_rec(VL);
+ DEBUG(dbgs() << "SLP: Placing 'extracts'\n");
+ for (SetVector<Instruction*>::iterator it = ExtractedLane.begin(), e =
+ ExtractedLane.end(); it != e; ++it) {
+ Instruction *Scalar = *it;
+ DEBUG(dbgs() << "SLP: Looking at " << *Scalar);
+
+ if (!Scalar)
+ continue;
+
+ Instruction *Loc = 0;
+
+ assert(MultiUserVals.count(Scalar) && "Can't find the lane to extract");
+ Instruction *Leader = MultiUserVals[Scalar].Leader;
+
+ // This value is gathered so we don't need to extract from anywhere.
+ if (!VectorizedValues.count(Leader))
+ continue;
+
+ Value *Vec = VectorizedValues[Leader];
+ if (PHINode *PN = dyn_cast<PHINode>(Vec)) {
+ Loc = PN->getParent()->getFirstInsertionPt();
+ } else {
+ Instruction *I = cast<Instruction>(Vec);
+ BasicBlock::iterator L = *I;
+ Loc = ++L;
+ }
+
+ Builder.SetInsertPoint(Loc);
+ assert(LaneMap.count(Scalar) && "Can't find the extracted lane.");
+ int Lane = LaneMap[Scalar];
+ Value *Idx = Builder.getInt32(Lane);
+ Value *Extract = Builder.CreateExtractElement(Vec, Idx);
+
+ bool Replaced = false;;
+ for (Value::use_iterator U = Scalar->use_begin(), UE = Scalar->use_end();
+ U != UE; ++U) {
+ Instruction *UI = cast<Instruction>(*U);
+ // No need to replace instructions that are inside our lane map.
+ if (LaneMap.count(UI))
+ continue;
+
+ UI->replaceUsesOfWith(Scalar ,Extract);
+ Replaced = true;
+ }
+ assert(Replaced && "Must replace at least one outside user");
+ (void)Replaced;
+ }
+
// We moved some instructions around. We have to number them again
// before we can do any analysis.
- for (Function::iterator it = F->begin(), e = F->end(); it != e; ++it)
- BlocksNumbers[it].forget();
+ forgetNumbering();
+
// Clear the state.
MustGather.clear();
VisitedPHIs.clear();
@@ -1251,15 +1364,18 @@ Value *FuncSLP::vectorizeTree(ArrayRef<Value *> VL) {
}
Value *FuncSLP::vectorizeArith(ArrayRef<Value *> Operands) {
+ Instruction *LastInst = getLastInstruction(Operands);
Value *Vec = vectorizeTree(Operands);
// After vectorizing the operands we need to generate extractelement
// instructions and replace all of the uses of the scalar values with
// the values that we extracted from the vectorized tree.
+ Builder.SetInsertPoint(LastInst);
for (unsigned i = 0, e = Operands.size(); i != e; ++i) {
Value *S = Builder.CreateExtractElement(Vec, Builder.getInt32(i));
Operands[i]->replaceAllUsesWith(S);
}
+ forgetNumbering();
return Vec;
}
@@ -1334,6 +1450,8 @@ void FuncSLP::optimizeGatherSequence() {
assert((*v)->getNumUses() == 0 && "Can't remove instructions with uses");
(*v)->eraseFromParent();
}
+
+ forgetNumbering();
}
/// The SLPVectorizer Pass.
diff --git a/test/Transforms/SLPVectorizer/X86/cse.ll b/test/Transforms/SLPVectorizer/X86/cse.ll
index 17b966b..63eaeec 100644
--- a/test/Transforms/SLPVectorizer/X86/cse.ll
+++ b/test/Transforms/SLPVectorizer/X86/cse.ll
@@ -11,13 +11,12 @@ target triple = "i386-apple-macosx10.8.0"
;}
;CHECK: @test
-;CHECK: insertelement <2 x double> undef
-;CHECK-NEXT: insertelement <2 x double>
-;CHECK-NEXT: fadd <2 x double>
+;CHECK: load <2 x double>
+;CHECK: fadd <2 x double>
+;CHECK: store <2 x double>
+;CHECK: insertelement <2 x double>
+;CHECK: fadd <2 x double>
;CHECK: store <2 x double>
-;CHECK: insertelement <2 x double>
-;CHECK-NEXT: fadd <2 x double>
-;CHECK: store <2 x double>
;CHECK: ret i32
define i32 @test(double* nocapture %G) {
diff --git a/test/Transforms/SLPVectorizer/X86/external_user.ll b/test/Transforms/SLPVectorizer/X86/external_user.ll
new file mode 100644
index 0000000..7f032b5
--- /dev/null
+++ b/test/Transforms/SLPVectorizer/X86/external_user.ll
@@ -0,0 +1,61 @@
+; 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"
+
+; double foo(double * restrict b, double * restrict a, int n, int m) {
+; double r=a[1];
+; double g=a[0];
+; double x;
+; for (int i=0; i < 100; i++) {
+; r += 10;
+; g += 10;
+; r *= 4;
+; g *= 4;
+; x = g; <----- external user!
+; r += 4;
+; g += 4;
+; }
+; b[0] = g;
+; b[1] = r;
+;
+; return x; <-- must extract here!
+; }
+
+;CHECK: ext_user
+;CHECK: phi <2 x double>
+;CHECK: fadd <2 x double>
+;CHECK: fmul <2 x double>
+;CHECK: extractelement <2 x double>
+;CHECK: br
+;CHECK: store <2 x double>
+;CHECK: ret double
+
+define double @ext_user(double* noalias nocapture %B, double* noalias nocapture %A, i32 %n, i32 %m) {
+entry:
+ %arrayidx = getelementptr inbounds double* %A, i64 1
+ %0 = load double* %arrayidx, align 8
+ %1 = load double* %A, align 8
+ br label %for.body
+
+for.body: ; preds = %for.body, %entry
+ %i.020 = phi i32 [ 0, %entry ], [ %inc, %for.body ]
+ %G.019 = phi double [ %1, %entry ], [ %add5, %for.body ]
+ %R.018 = phi double [ %0, %entry ], [ %add4, %for.body ]
+ %add = fadd double %R.018, 1.000000e+01
+ %add2 = fadd double %G.019, 1.000000e+01
+ %mul = fmul double %add, 4.000000e+00
+ %mul3 = fmul double %add2, 4.000000e+00
+ %add4 = fadd double %mul, 4.000000e+00
+ %add5 = fadd double %mul3, 4.000000e+00
+ %inc = add nsw i32 %i.020, 1
+ %exitcond = icmp eq i32 %inc, 100
+ br i1 %exitcond, label %for.end, label %for.body
+
+for.end: ; preds = %for.body
+ store double %add5, double* %B, align 8
+ %arrayidx7 = getelementptr inbounds double* %B, i64 1
+ store double %add4, double* %arrayidx7, align 8
+ ret double %mul3
+}
+
diff --git a/test/Transforms/SLPVectorizer/X86/phi.ll b/test/Transforms/SLPVectorizer/X86/phi.ll
index af0b480..1c7f9cc 100644
--- a/test/Transforms/SLPVectorizer/X86/phi.ll
+++ b/test/Transforms/SLPVectorizer/X86/phi.ll
@@ -44,3 +44,54 @@ if.end: ; preds = %entry, %if.else
ret i32 undef
}
+
+;int foo(double * restrict B, double * restrict A, int n, int m) {
+; double R=A[1];
+; double G=A[0];
+; for (int i=0; i < 100; i++) {
+; R += 10;
+; G += 10;
+; R *= 4;
+; G *= 4;
+; R += 4;
+; G += 4;
+; }
+; B[0] = G;
+; B[1] = R;
+; return 0;
+;}
+
+;CHECK: foo2
+;CHECK: load <2 x double>
+;CHECK: phi <2 x double>
+;CHECK: fmul <2 x double>
+;CHECK: store <2 x double>
+;CHECK: ret
+define i32 @foo2(double* noalias nocapture %B, double* noalias nocapture %A, i32 %n, i32 %m) #0 {
+entry:
+ %arrayidx = getelementptr inbounds double* %A, i64 1
+ %0 = load double* %arrayidx, align 8
+ %1 = load double* %A, align 8
+ br label %for.body
+
+for.body: ; preds = %for.body, %entry
+ %i.019 = phi i32 [ 0, %entry ], [ %inc, %for.body ]
+ %G.018 = phi double [ %1, %entry ], [ %add5, %for.body ]
+ %R.017 = phi double [ %0, %entry ], [ %add4, %for.body ]
+ %add = fadd double %R.017, 1.000000e+01
+ %add2 = fadd double %G.018, 1.000000e+01
+ %mul = fmul double %add, 4.000000e+00
+ %mul3 = fmul double %add2, 4.000000e+00
+ %add4 = fadd double %mul, 4.000000e+00
+ %add5 = fadd double %mul3, 4.000000e+00
+ %inc = add nsw i32 %i.019, 1
+ %exitcond = icmp eq i32 %inc, 100
+ br i1 %exitcond, label %for.end, label %for.body
+
+for.end: ; preds = %for.body
+ store double %add5, double* %B, align 8
+ %arrayidx7 = getelementptr inbounds double* %B, i64 1
+ store double %add4, double* %arrayidx7, align 8
+ ret i32 0
+}
+