<table border="1" cellspacing="0" cellpadding="8">
<tr>
<th>Issue</th>
<td>
<a href=https://github.com/llvm/llvm-project/issues/109468>109468</a>
</td>
</tr>
<tr>
<th>Summary</th>
<td>
[LV][VPlan] Crash due to disagreements on the VPlan cost v.s. legacy cost model
</td>
</tr>
<tr>
<th>Labels</th>
<td>
vectorization
</td>
</tr>
<tr>
<th>Assignees</th>
<td>
</td>
</tr>
<tr>
<th>Reporter</th>
<td>
mshockwave
</td>
</tr>
</table>
<pre>
Given this input:
``` llvm
target datalayout = "e-m:e-p:64:64-i64:64-i128:128-n32:64-S128"
target triple = "riscv64-unknown-linux-gnu"
define void @lshift_significand(i32 %n, ptr %0) {
entry:
br label %for.cond
for.cond: ; preds = %for.cond, %entry
%i.0 = phi i32 [ 0, %entry ], [ 2, %for.cond ]
%add = or i32 %n, %i.0
%cmp1 = icmp eq i32 %add, 0
br i1 %cmp1, label %for.cond, label %for.cond7
for.cond7: ; preds = %for.body9, %for.cond
%i.1 = phi i32 [ %i.0, %for.cond ], [ %inc15, %for.body9 ]
%cmp8 = icmp ult i32 %i.1, 3
br i1 %cmp8, label %for.body9, label %for.end16
for.body9: ; preds = %for.cond7
%sub11 = sub nuw i32 1, %i.1
%idxprom12 = zext i32 %sub11 to i64
%arrayidx13 = getelementptr [3 x i64], ptr %0, i64 0, i64 %idxprom12
store i64 0, ptr %arrayidx13, align 8
%inc15 = add i32 %i.1, 1
br label %for.cond7
for.end16: ; preds = %for.cond7
ret void
}
```
And this command:
``` bash
opt -mcpu=sifive-p470 -O3 -prefer-predicate-over-epilogue=predicate-dont-vectorize -force-tail-folding-style=data-with-evl input.ll -disable-output
```
We'll get the following assertion:
```
llvm/lib/Transforms/Vectorize/LoopVectorize.cpp:7386: VectorizationFactor llvm::LoopVectorizationPlanner::computeBestVF(): Assertion `(BestFactor.Width == LegacyVF.Width || planContainsAdditionalSimplifications(getPlanFor(BestFactor.Width), CostCtx, OrigLoop)) && " VPlan cost model and legacy cost model disagreed"' failed.
```
Preliminary investigation shows that this is caused by the disagreement on (reverse) widen stores. First, this is the trace for VPlan's cost model:
```
LV: Scalar loop costs: 4.
Cost of 1 for VF vscale x 1: induction instruction %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
Cost of 0 for VF vscale x 1: induction instruction %indvars.iv = phi i64 [ %spec.select, %entry ], [ %indvars.iv.next, %for.body9 ]
Cost of 1 for VF vscale x 1: exit condition instruction %exitcond.not = icmp eq i64 %indvars.iv.next, 3
Cost of 0 for VF vscale x 1: EMIT vp<%4> = CANONICAL-INDUCTION ir<0>, vp<%12>
Cost of 0 for VF vscale x 1: EXPLICIT-VECTOR-LENGTH-BASED-IV-PHI vp<%5> = phi ir<0>, vp<%11>
Cost of 0 for VF vscale x 1: EMIT vp<%6> = EXPLICIT-VECTOR-LENGTH vp<%5>, vp<%3>
Cost of 0 for VF vscale x 1: vp<%7> = DERIVED-IV ir<%spec.select> + vp<%5> * ir<1>
Cost of 0 for VF vscale x 1: vp<%8> = SCALAR-STEPS vp<%7>, ir<1>
Cost of 1 for VF vscale x 1: CLONE ir<%1> = sub nuw nsw ir<1>, vp<%8>
Cost of 0 for VF vscale x 1: CLONE ir<%arrayidx13> = getelementptr ir<%0>, ir<0>, ir<%1>
Cost of 0 for VF vscale x 1: vp<%9> = vector-pointer (reverse) ir<%arrayidx13>
Cost of 8 for VF vscale x 1: WIDEN vp.store vp<%9>, ir<0>, vp<%6>
Cost of 0 for VF vscale x 1: SCALAR-CAST vp<%10> = zext vp<%6> to i64
Cost of 0 for VF vscale x 1: EMIT vp<%11> = add vp<%10>, vp<%5>
Cost of 0 for VF vscale x 1: EMIT vp<%12> = add vp<%4>, vp<%0>
Cost of 0 for VF vscale x 1: EMIT branch-on-count vp<%12>, vp<%1>
Cost of 0 for VF vscale x 1: vector loop backedge
Cost for VF vscale x 1: 11
Cost of 1 for VF vscale x 2: induction instruction %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
Cost of 0 for VF vscale x 2: induction instruction %indvars.iv = phi i64 [ %spec.select, %entry ], [ %indvars.iv.next, %for.body9 ]
Cost of 1 for VF vscale x 2: exit condition instruction %exitcond.not = icmp eq i64 %indvars.iv.next, 3
Cost of 0 for VF vscale x 2: EMIT vp<%4> = CANONICAL-INDUCTION ir<0>, vp<%12>
Cost of 0 for VF vscale x 2: EXPLICIT-VECTOR-LENGTH-BASED-IV-PHI vp<%5> = phi ir<0>, vp<%11>
Cost of 0 for VF vscale x 2: EMIT vp<%6> = EXPLICIT-VECTOR-LENGTH vp<%5>, vp<%3>
Cost of 0 for VF vscale x 2: vp<%7> = DERIVED-IV ir<%spec.select> + vp<%5> * ir<1>
Cost of 0 for VF vscale x 2: vp<%8> = SCALAR-STEPS vp<%7>, ir<1>
Cost of 1 for VF vscale x 2: CLONE ir<%1> = sub nuw nsw ir<1>, vp<%8>
Cost of 0 for VF vscale x 2: CLONE ir<%arrayidx13> = getelementptr ir<%0>, ir<0>, ir<%1>
Cost of 0 for VF vscale x 2: vp<%9> = vector-pointer (reverse) ir<%arrayidx13>
Cost of 14 for VF vscale x 2: WIDEN vp.store vp<%9>, ir<0>, vp<%6>
Cost of 0 for VF vscale x 2: SCALAR-CAST vp<%10> = zext vp<%6> to i64
Cost of 0 for VF vscale x 2: EMIT vp<%11> = add vp<%10>, vp<%5>
Cost of 0 for VF vscale x 2: EMIT vp<%12> = add vp<%4>, vp<%0>
Cost of 0 for VF vscale x 2: EMIT branch-on-count vp<%12>, vp<%1>
Cost of 0 for VF vscale x 2: vector loop backedge
Cost for VF vscale x 2: 17
```
With VPlan's cost model, we will eventually choose scalar loop, because when VF=vscale x 1, the final cost is `ceil(11 / 2) = 6`; when VF=vscale x 2, the final cost is `ceil(17 / 4) = 5`. Both of them are larger them the scalar cost, 4.
While with the legacy cost model:
```
LV: Found an estimated cost of 0 for VF 1 For instruction: %indvars.iv = phi i64 [ %spec.select, %entry ], [ %indvars.iv.next, %for.body9 ]
LV: Found an estimated cost of 1 for VF 1 For instruction: %1 = sub nuw nsw i64 1, %indvars.iv
LV: Found an estimated cost of 0 for VF 1 For instruction: %arrayidx13 = getelementptr [3 x i64], ptr %0, i64 0, i64 %1
LV: Found an estimated cost of 1 for VF 1 For instruction: store i64 0, ptr %arrayidx13, align 8
LV: Found an estimated cost of 1 for VF 1 For instruction: %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
LV: Found an estimated cost of 1 for VF 1 For instruction: %exitcond.not = icmp eq i64 %indvars.iv.next, 3
LV: Found an estimated cost of 0 for VF 1 For instruction: br i1 %exitcond.not, label %for.end16, label %for.body9
LV: Scalar loop costs: 4.
LV: Found an estimated cost of 0 for VF vscale x 1 For instruction: %indvars.iv = phi i64 [ %spec.select, %entry ], [ %indvars.iv.next, %for.body9 ]
LV: Found an estimated cost of 1 for VF vscale x 1 For instruction: %1 = sub nuw nsw i64 1, %indvars.iv
LV: Found an estimated cost of 0 for VF vscale x 1 For instruction: %arrayidx13 = getelementptr [3 x i64], ptr %0, i64 0, i64 %1
LV: Found an estimated cost of 7 for VF vscale x 1 For instruction: store i64 0, ptr %arrayidx13, align 8
LV: Found an estimated cost of 1 for VF vscale x 1 For instruction: %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
LV: Found an estimated cost of 1 for VF vscale x 1 For instruction: %exitcond.not = icmp eq i64 %indvars.iv.next, 3
LV: Found an estimated cost of 0 for VF vscale x 1 For instruction: br i1 %exitcond.not, label %for.end16, label %for.body9
LV: Vector loop of width vscale x 1 costs: 5 (assuming a minimum vscale of 2).
LV: Found an estimated cost of 0 for VF vscale x 2 For instruction: %indvars.iv = phi i64 [ %spec.select, %entry ], [ %indvars.iv.next, %for.body9 ]
LV: Found an estimated cost of 1 for VF vscale x 2 For instruction: %1 = sub nuw nsw i64 1, %indvars.iv
LV: Found an estimated cost of 0 for VF vscale x 2 For instruction: %arrayidx13 = getelementptr [3 x i64], ptr %0, i64 0, i64 %1
LV: Found an estimated cost of 13 for VF vscale x 2 For instruction: store i64 0, ptr %arrayidx13, align 8
LV: Found an estimated cost of 1 for VF vscale x 2 For instruction: %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
LV: Found an estimated cost of 1 for VF vscale x 2 For instruction: %exitcond.not = icmp eq i64 %indvars.iv.next, 3
LV: Found an estimated cost of 0 for VF vscale x 2 For instruction: br i1 %exitcond.not, label %for.end16, label %for.body9
LV: Vector loop of width vscale x 2 costs: 4 (assuming a minimum vscale of 2).
LV: Selecting VF: vscale x 2.
```
We will eventually choose VF=vscale x 2.
The key difference is the cost of `store i64 0, ptr %arrayidx13, align 8` v.s. cost of `WIDEN vp.store vp<%9>, ir<0>, vp<%6>`, where the latter is larger than the former by 1.
In both cases (the store instruction in VPlan cost model v.s. legacy cost model) their costs are computed by the base cost of store + the cost of shuffle due to being reverse store. I used debugger to confirm that they used the same shuffle cost, which means that for some reason, VPlan's cost model yield a slightly higher cost for store than that in the legacy cost model.
</pre>
<img width="1px" height="1px" alt="" src="http://email.email.llvm.org/o/eJzUWl9z4ygS_zTkpUsuCfnvQx4cO95NVS4ztcll7u0KS22LGwQ6QHa8n_4KJNlyrEyc2SRzOzXlCNR0_7ppuhsQM4avJeIlGVyRwfyClTZT-jI3mUq-b9kGL5Yq3V3-xjcowWbcAJdFaUk8JeGchFMyDKv_IMQmr_os02u0kDLLBNup0gKJ50AoxSAn8RSDgsTTYd__BHz_ENExiacRHQcyplXfveuj9Iit1bwQ2LDU3CSbYT8o5XeptjIQXJZPwVqW-2HVb4orLhE2iqdA-qEwGV_Zfzvd-YonTKaEjnlMgdCBJHQGhdXuOSR0AmR0VTFBafVurzrAUoNgSxSOcqV0L1EybQvd98VTIPEVFBpTUyM_DKAz16x414wJHfBe6CmLjIMHNriCsE0LZDD37cEV0PpFw9O_O_Biaep5KQ1tHSspLbokLyJPyJO8APxvQ81SjzJs6c2jZoB7c2qFrs5Rl21Gzjhn_uu0ofPPyTP9j-wYndixVrzDZrU9HYFMokGLxIt5ZtckL8YHe5XCNgbjPW-WuMtg4xPb7DU46kWZRsPnFqtIf-ROoxY-Uy6jSntTLkGWW48v2s99VNO6RvpUaJVH1JP_iU97XSomVoFbqS2f0prtePoUxX7EGi0KzFFav3IGVzE8-RGVUQ_LaeZ6Yf_QFt1wN1ZpPJDVYw8CXScTfC1h3J5oN2Eei3P344mIfrRiT9yysvxZRtZofUypWYzmz6Ji1ZzKtIqdicpz5uPB8-i5ZCar-lRhIciToiTx3PAV32BQ9EchBF9iCAqNK9TuT8oTZjFQG9QBFlyodYkknh_epEraYIOJVZr_iRCslE4wsIyLYKVEyuU6MHYn3CAXqYMtt1mAG1EF-J4QEKTcsKXAQJXWxfwu1b4hoSMhwEfmDGGlhFBbLtfAjEFtuZKn2lZNnzDoQvAloYsHzaRZKZ0bQhePDWpCF7dKFft2Lylc7hjFYz8_TT9zYhbMNao0FE9JPG2P9BRfBZMSdfU2UXlRWrxCYx8XxKUZv66mDWpwOOnYva84977x1GbOE5wz3OKaJbvHRdM7mpHRDArB5ExJy7g00zTljhET9zwvhE8zrm0IHa_ROjALpTtEOCR0BjNl7Mw-uccvmq-dNv7NBAgdEjp02Q8eHRtIlLGQqxQFMJmC8NjavW4i1xoxdVmRjmDFuMC01zkt7d-vGgXPuWR6B1xu0Fi-9kqAydTWgM2YrasCAwkrDaaw3HlHaES6kADOnHSscYPaoFNhy1OU1UI3PVhwbaxTtGHlGFjNEudPulKS0JFpqfSSU90-ulm8T5hgGoRShR9jXGe_1tcZFtQKoor5AjYmYQLhCSJHxmVaJl5HLo3V9XMdYtIN06bHNz3pImQTbFxklWa7D2h7slbsaaSGb5F6xOyQxpyYKkuZApOeQYGJfak2OMX9clZ7xTT4xC24-Me7kLq37mVPKntcRTw3yx5FfJZtrv9x8wCbgsQzQgd9El977rPp3Ze7m9n0Nri5m_9z9nDz5Q64JvEsJPG1Y96MiKjrOEvQv77e3sxuHoLH69nDlz-C2-u73x5-D66m99fz4OYx-Pr7zZ7roMHhZ6RTbnS23LaCw4ZxN5ojAG1x8bnSmgGjRtD8-o-bR69hpcgzv3JU9OqZ4nRa0Z6tYzN83Ei9n01vp38E9w_XX--PMPnSoJv3C345u_1yd73HHjUSmqLHL809w5bJxueCPxbQqkRqScfVT0MXtpU5atQo32S4SSOsyulBobi0qJ8F1k6Mx3LG3XK-3cyv72BT9Kryqy32RIm2r56lRD3Zs-n9wdGjsNHIl5tH_t8uN9-yeKL95Lu4fCSpjXvwUyvTB5IT5v1nvMM38V5qJpMsUDJIVCnts6DVjiZn-wtWdZDLfUuWfMd0ja2BnWOi6LV1Rs9MUu-ZGH8gE_6PUiN9JTXCRyVH-lnJkf6i5Hiq4EcmR_pLkiP9wORIPzo5dgj4tORIPyQ5Rv1uQR-VHenHZcfT1fOO2bGD-btlR_ox2ZH-RHb0Y6JR99EHt1n33pTOYIuw5UIAblDakgmxgyRTyiCYw97UES7R75thm6GExwWJ563U7LfECCsumagEcANkGCbIBaHjKAJCF0D9oUA8h6HDFl918aKv8hp5Xv2G14AMwx5cKZs5a9oMc2AaQTC9Rl21HbtaG8fPSWj22LWFMi6cHWzmaU_OJX68iV-oUqbAJKCxPGcW02poe3IjWCjdzrbVafJnFwevAo5eBxydhuVh_3BYeyid3s1E73eEG72TGd588vsehv8rxet7yP_50vAvO8H-XqKN4YWbiO5bi3MP3c6Hegh_f7e1fQbyj1rkZ4j-_NU-Og_dBy76N_nSR67-M4B8Rhh4Dca7xoPHVqmlVrD1FyUtBPsYMXBlOjOmzP29EeRc8rzMG1q18hXOzwcS-rcNJC8j__BA8rLoX1A2xOfB-4xIco4zfUokeRnIp0aSF2B8YiShrWrj7ZHk3q9vR-42TNMW2-7r0W8vbuyebbiOdkIPGcJ33EHKVyvUKBNsrjkby5Jh-Bb3HYaw6Zlee_hPH1EMvbhthhqrfRqzFrUDuN_tMVnf7uscNSx3EB2pdyNh6XaKCTNo3Bz4rWGlTusklMvTC2uvxenOkE6cQF7tLI3fetY39vsb5iUzB_NVwgi9OjKqycrVSiCkJYJVsEQ3z_WBUDWkBzfgr61TXJZrr6yCRMkV13lzvY27isQrxXLcs212vduMJxnkyGR9Je4WiVE5gkZmlP_YquugAHYcRQoMjODrzIodZHydYaV0xcSrVdufWWfBzp10PRsX6WWcTuIJu8DLaESH42E86vcvssvhZEijSZ-NJmG6TBOWjhMcRat4OMFVQll8wS9pSPvhhIY0pJT2e_1lEqWD5WSQMDYe9YekH2LOuOgJscl7Sq8vuDElXkbhpD8cX_gFbPxXhJRu2l9dEErJYH6hL93AYFmuDemHghtrDqwst8J_gnj76NLG4Kqy1mAOM81M1sxf-5sCA6qyRcujun3potTiMrO2cCGC0AWhizW3WbnsJcp_gFJ_h-LgFVr9x6f7hdfOELqoFdxc0v8FAAD__yNIWag">