Skip to content

Commit 74c387f

Browse files
author
Charlie Turner
committedOct 27, 2015
[SLP] Treat SelectInsts as reduction values.
Summary: Certain workloads, in particular sum-of-absdiff loops, can be vectorized using SLP if it can treat select instructions as reduction values. The test case is a bit awkward. The AArch64 cost model needs some tuning to not be so pessimistic about selects. I've had to tweak the SLP threshold here. Reviewers: jmolloy, mzolotukhin, spatel, nadav Subscribers: nadav, mssimpso, aemerson, llvm-commits Differential Revision: http://reviews.llvm.org/D13949 llvm-svn: 251424
1 parent 4a51e5d commit 74c387f

File tree

2 files changed

+80
-6
lines changed

2 files changed

+80
-6
lines changed
 

‎llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

+7-6
Original file line numberDiff line numberDiff line change
@@ -3714,11 +3714,11 @@ class HorizontalReduction {
37143714
return false;
37153715

37163716
// Post order traverse the reduction tree starting at B. We only handle true
3717-
// trees containing only binary operators.
3718-
SmallVector<std::pair<BinaryOperator *, unsigned>, 32> Stack;
3717+
// trees containing only binary operators or selects.
3718+
SmallVector<std::pair<Instruction *, unsigned>, 32> Stack;
37193719
Stack.push_back(std::make_pair(B, 0));
37203720
while (!Stack.empty()) {
3721-
BinaryOperator *TreeN = Stack.back().first;
3721+
Instruction *TreeN = Stack.back().first;
37223722
unsigned EdgeToVist = Stack.back().second++;
37233723
bool IsReducedValue = TreeN->getOpcode() != ReductionOpcode;
37243724

@@ -3754,9 +3754,10 @@ class HorizontalReduction {
37543754

37553755
// Visit left or right.
37563756
Value *NextV = TreeN->getOperand(EdgeToVist);
3757-
BinaryOperator *Next = dyn_cast<BinaryOperator>(NextV);
3758-
if (Next)
3759-
Stack.push_back(std::make_pair(Next, 0));
3757+
// We currently only allow BinaryOperator's and SelectInst's as reduction
3758+
// values in our tree.
3759+
if (isa<BinaryOperator>(NextV) || isa<SelectInst>(NextV))
3760+
Stack.push_back(std::make_pair(cast<Instruction>(NextV), 0));
37603761
else if (NextV != Phi)
37613762
return false;
37623763
}

‎llvm/test/Transforms/SLPVectorizer/AArch64/horizontal.ll

+73
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,73 @@
1+
; RUN: opt -slp-vectorizer -slp-threshold=-6 -slp-vectorize-hor -S < %s | FileCheck %s
2+
3+
; FIXME: The threshold is changed to keep this test case a bit smaller.
4+
; The AArch64 cost model should not give such high costs to select statements.
5+
6+
target datalayout = "e-m:e-i64:64-i128:128-n32:64-S128"
7+
target triple = "aarch64--linux"
8+
9+
; CHECK-LABEL: test_select
10+
; CHECK: load <4 x i32>
11+
; CHECK: load <4 x i32>
12+
; CHECK: select <4 x i1>
13+
define i32 @test_select(i32* noalias nocapture readonly %blk1, i32* noalias nocapture readonly %blk2, i32 %lx, i32 %h) {
14+
entry:
15+
%cmp.22 = icmp sgt i32 %h, 0
16+
br i1 %cmp.22, label %for.body.lr.ph, label %for.end
17+
18+
for.body.lr.ph: ; preds = %entry
19+
%idx.ext = sext i32 %lx to i64
20+
br label %for.body
21+
22+
for.body: ; preds = %for.body, %for.body.lr.ph
23+
%s.026 = phi i32 [ 0, %for.body.lr.ph ], [ %add27, %for.body ]
24+
%j.025 = phi i32 [ 0, %for.body.lr.ph ], [ %inc, %for.body ]
25+
%p2.024 = phi i32* [ %blk2, %for.body.lr.ph ], [ %add.ptr29, %for.body ]
26+
%p1.023 = phi i32* [ %blk1, %for.body.lr.ph ], [ %add.ptr, %for.body ]
27+
%0 = load i32, i32* %p1.023, align 4
28+
%1 = load i32, i32* %p2.024, align 4
29+
%sub = sub nsw i32 %0, %1
30+
%cmp2 = icmp slt i32 %sub, 0
31+
%sub3 = sub nsw i32 0, %sub
32+
%sub3.sub = select i1 %cmp2, i32 %sub3, i32 %sub
33+
%add = add nsw i32 %sub3.sub, %s.026
34+
%arrayidx4 = getelementptr inbounds i32, i32* %p1.023, i64 1
35+
%2 = load i32, i32* %arrayidx4, align 4
36+
%arrayidx5 = getelementptr inbounds i32, i32* %p2.024, i64 1
37+
%3 = load i32, i32* %arrayidx5, align 4
38+
%sub6 = sub nsw i32 %2, %3
39+
%cmp7 = icmp slt i32 %sub6, 0
40+
%sub9 = sub nsw i32 0, %sub6
41+
%v.1 = select i1 %cmp7, i32 %sub9, i32 %sub6
42+
%add11 = add nsw i32 %add, %v.1
43+
%arrayidx12 = getelementptr inbounds i32, i32* %p1.023, i64 2
44+
%4 = load i32, i32* %arrayidx12, align 4
45+
%arrayidx13 = getelementptr inbounds i32, i32* %p2.024, i64 2
46+
%5 = load i32, i32* %arrayidx13, align 4
47+
%sub14 = sub nsw i32 %4, %5
48+
%cmp15 = icmp slt i32 %sub14, 0
49+
%sub17 = sub nsw i32 0, %sub14
50+
%sub17.sub14 = select i1 %cmp15, i32 %sub17, i32 %sub14
51+
%add19 = add nsw i32 %add11, %sub17.sub14
52+
%arrayidx20 = getelementptr inbounds i32, i32* %p1.023, i64 3
53+
%6 = load i32, i32* %arrayidx20, align 4
54+
%arrayidx21 = getelementptr inbounds i32, i32* %p2.024, i64 3
55+
%7 = load i32, i32* %arrayidx21, align 4
56+
%sub22 = sub nsw i32 %6, %7
57+
%cmp23 = icmp slt i32 %sub22, 0
58+
%sub25 = sub nsw i32 0, %sub22
59+
%v.3 = select i1 %cmp23, i32 %sub25, i32 %sub22
60+
%add27 = add nsw i32 %add19, %v.3
61+
%add.ptr = getelementptr inbounds i32, i32* %p1.023, i64 %idx.ext
62+
%add.ptr29 = getelementptr inbounds i32, i32* %p2.024, i64 %idx.ext
63+
%inc = add nuw nsw i32 %j.025, 1
64+
%exitcond = icmp eq i32 %inc, %h
65+
br i1 %exitcond, label %for.end.loopexit, label %for.body
66+
67+
for.end.loopexit: ; preds = %for.body
68+
br label %for.end
69+
70+
for.end: ; preds = %for.end.loopexit, %entry
71+
%s.0.lcssa = phi i32 [ 0, %entry ], [ %add27, %for.end.loopexit ]
72+
ret i32 %s.0.lcssa
73+
}

0 commit comments

Comments
 (0)
Please sign in to comment.