[SLP] Make sure instructions are ordered when computing spill cost.

[fhahn]

Summary

The entries in VectorizableTree are not necessarily ordered by their
position in basic blocks. Collect them and order them by dominance so
later instructions are guaranteed to be visited first. For instructions
in different basic blocks, we only scan to the beginning of the block,
so their order does not matter, as long as all instructions in a basic
block are grouped together. Using dominance ensures a deterministic order.

The modified test case contains an example where we compute a wrong
spill cost (2) without this patch, even though there is no call between
any instruction in the bundle.

This seems to have limited practical impact, .e.g on X86 with a recent
Intel Xeon CPU with -O3 -march=native -flto on MultiSource,SPEC2000,SPEC2006
there are no binary changes.

[ABataev]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

3769–3778

Can we use a set instead of the vector with sort?

[fhahn]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

3769–3778

We could use set with dominates() as comparator I think. I am not sure if there would be a benefit of doing so for the use locally in the function, but maybe we could use it to keep VectorizableTree in order to start with? Not entirely sure what impact that would have at other places, but it might be worth exploring as follow-up?

[fhahn]

ping

[nikic]

This seems to have limited practical impact, .e.g on X86 with a recent
Intel Xeon CPU with -O3 -march=native -flto on MultiSource,SPEC2000,SPEC2006
there are no binary changes.

That's not particularly surprising, as the spill cost is always zero on X86. AArch64 is the only architecture that defines getCostOfKeepingLiveOverCall().

I had a different patch for this issue in D64523, but your solution to the problem is much simpler :)

[ABataev]

LG

[vdmitrie]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

3777

There is a problem with this predicate function.
MSFT STL implementation of stable_sort asserts that if predicate returned true
then it must return false when operands are swapped.
But (A dom B) == false does not necessarily mean that (B dom A) == true.
Instead: (A dom B) ==true means that (B dom A) == false.
Rewriting it like this solves this issue:

return DT->dominates(B, A);

[xbolva00]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

3777

@fhahn try to fix it and reland.

Seems like this is a reason why a win buildbot failed.

[xbolva00]

Seems like ClamAV has now compile time regression ~ 0.1-0.2 % (http://llvm-compile-time-tracker.com/compare.php?from=3ce57e012110519c1d3a49fc98959a64634d5d8f&to=36e1fc5f68e918ba69ccd9033b38240265617c4e&stat=instructions&details=on)

CMakeFiles/clamscan.dir/libclamav_mspack.c.o 6432M 6472M (+0.62%)
CMakeFiles/clamscan.dir/libclamav_nsis_LZMADecode.c.o 730M 738M (+1.09%)

CMakeFiles/clamscan.dir/libclamav_upx.c.o 1213M 1272M (+4.87%)

cc @nikic

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

int BoUpSLP::getSpillCost() const {
   // query TTI to see if there is a cost to keeping values live over it
   // (for example, if spills and fills are required).
   unsigned BundleWidth = VectorizableTree.front()->Scalars.size();
   int Cost = 0;
 
   SmallPtrSet<Instruction*, 4> LiveValues;
   Instruction *PrevInst = nullptr;
 
+  // The entries in VectorizableTree are not necessarily ordered by their
+  // position in basic blocks. Collect them and order them by dominance so later
+  // instructions are guaranteed to be visited first. For instructions in
+  // different basic blocks, we only scan to the beginning of the block, so
+  // their order does not matter, as long as all instructions in a basic block
+  // are grouped together. Using dominance ensures a deterministic order.
+  SmallVector<Instruction *, 16> OrderedScalars;
   for (const auto &TEPtr : VectorizableTree) {
     Instruction *Inst = dyn_cast<Instruction>(TEPtr->Scalars[0]);
     if (!Inst)
       continue;
+    OrderedScalars.push_back(Inst);
+  }
+  llvm::stable_sort(OrderedScalars, [this](Instruction *A, Instruction *B) {
+    return !DT->dominates(A, B);
+  });
 
+  for (Instruction *Inst : OrderedScalars) {
     if (!PrevInst) {
       PrevInst = Inst;
       continue;
     }
 
     // Update LiveValues.
     LiveValues.erase(PrevInst);
     for (auto &J : PrevInst->operands()) {

llvm/test/Transforms/SLPVectorizer/AArch64/spillcost-order.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -slp-vectorizer -S %s | FileCheck %s
 
 target datalayout = "e-m:o-i64:64-i128:128-n32:64-S128"
 target triple = "arm64-apple-ios13.0.0"
 
 declare i1 @cond()
 declare i32* @get_ptr()
 
 define void @test(i64* %ptr, i64* noalias %res) {
 ; CHECK-LABEL: @test(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
 ; CHECK:       for.body:
 ; CHECK-NEXT:    [[CALL_I_I:%.*]] = call i32* @get_ptr()
-; CHECK-NEXT:    [[L_0_0:%.*]] = load i32, i32* [[CALL_I_I]], align 2
 ; CHECK-NEXT:    [[GEP_1:%.*]] = getelementptr i32, i32* [[CALL_I_I]], i32 2
-; CHECK-NEXT:    [[L_1_0:%.*]] = load i32, i32* [[GEP_1]], align 2
-; CHECK-NEXT:    [[EXT_0_0:%.*]] = zext i32 [[L_0_0]] to i64
-; CHECK-NEXT:    [[EXT_1_0:%.*]] = zext i32 [[L_1_0]] to i64
-; CHECK-NEXT:    [[SUB_1:%.*]] = sub nsw i64 [[EXT_0_0]], [[EXT_1_0]]
 ; CHECK-NEXT:    [[GEP_2:%.*]] = getelementptr i32, i32* [[CALL_I_I]], i32 1
-; CHECK-NEXT:    [[L_0_1:%.*]] = load i32, i32* [[GEP_2]], align 2
+; CHECK-NEXT:    [[TMP0:%.*]] = bitcast i32* [[CALL_I_I]] to <2 x i32>*
+; CHECK-NEXT:    [[TMP1:%.*]] = load <2 x i32>, <2 x i32>* [[TMP0]], align 2
 ; CHECK-NEXT:    [[GEP_3:%.*]] = getelementptr i32, i32* [[CALL_I_I]], i32 3
-; CHECK-NEXT:    [[L_1_1:%.*]] = load i32, i32* [[GEP_3]], align 2
-; CHECK-NEXT:    [[EXT_0_1:%.*]] = zext i32 [[L_0_1]] to i64
-; CHECK-NEXT:    [[EXT_1_1:%.*]] = zext i32 [[L_1_1]] to i64
-; CHECK-NEXT:    [[SUB_2:%.*]] = sub nsw i64 [[EXT_0_1]], [[EXT_1_1]]
-; CHECK-NEXT:    store i64 [[SUB_1]], i64* [[RES:%.*]], align 8
-; CHECK-NEXT:    [[RES_1:%.*]] = getelementptr i64, i64* [[RES]], i64 1
-; CHECK-NEXT:    store i64 [[SUB_2]], i64* [[RES_1]], align 8
+; CHECK-NEXT:    [[TMP2:%.*]] = bitcast i32* [[GEP_1]] to <2 x i32>*
+; CHECK-NEXT:    [[TMP3:%.*]] = load <2 x i32>, <2 x i32>* [[TMP2]], align 2
+; CHECK-NEXT:    [[TMP4:%.*]] = zext <2 x i32> [[TMP1]] to <2 x i64>
+; CHECK-NEXT:    [[TMP5:%.*]] = zext <2 x i32> [[TMP3]] to <2 x i64>
+; CHECK-NEXT:    [[TMP6:%.*]] = sub nsw <2 x i64> [[TMP4]], [[TMP5]]
+; CHECK-NEXT:    [[RES_1:%.*]] = getelementptr i64, i64* [[RES:%.*]], i64 1
+; CHECK-NEXT:    [[TMP7:%.*]] = bitcast i64* [[RES]] to <2 x i64>*
+; CHECK-NEXT:    store <2 x i64> [[TMP6]], <2 x i64>* [[TMP7]], align 8
 ; CHECK-NEXT:    [[C:%.*]] = call i1 @cond()
 ; CHECK-NEXT:    br i1 [[C]], label [[FOR_BODY]], label [[EXIT:%.*]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    ret void
 ;
 entry:
   br label %for.body