<table border="1" cellspacing="0" cellpadding="8">
    <tr>
        <th>Issue</th>
        <td>
            <a href=https://github.com/llvm/llvm-project/issues/62327>62327</a>
        </td>
    </tr>

    <tr>
        <th>Summary</th>
        <td>
            SLP doesn't account for constant materialisation costs in phi nodes
        </td>
    </tr>

    <tr>
      <th>Labels</th>
      <td>
            llvm:SLPVectorizer
      </td>
    </tr>

    <tr>
      <th>Assignees</th>
      <td>
      </td>
    </tr>

    <tr>
      <th>Reporter</th>
      <td>
          bubba
      </td>
    </tr>
</table>

<pre>
    Currently SLP does not vectorise the following function on RISC-V, as it correctly works out that the cost of materialising the constants for the vectorised case outweighs the scalar cost
```llvm
define void @g(ptr %p, i1 %c) {
  %p.0 = getelementptr i8, ptr %p
  %p.1 = getelementptr i8, ptr %p, i32 1
  br i1 %c, label %forward, label %backward
forward:
  store i8 1, ptr %p.0
  store i8 -1, ptr %p.1
  br label %end
backward:
 store i8 -1, ptr %p.0
  store i8 1, ptr %p.1
  br label %end
end:
  ret void
}
```

```
0.
Operand 0:
  i8 1
  i8 -1
Operand 1:
    %p.0 = getelementptr i8, ptr %p
    %p.1 = getelementptr i8, ptr %p, i32 1
Scalars: 
    store i8 1, ptr %p.0, align 1
    store i8 -1, ptr %p.1, align 1
State: Vectorize
MainOp: store i8 1, ptr %p.0, align 1
AltOp:   store i8 1, ptr %p.0, align 1
VectorizedValue: NULL
ReuseShuffleIndices: Empty
ReorderIndices: 
UserTreeIndices: 
SLP: Costs:
SLP:     ReuseShuffleCost = 0
SLP: VectorCost = 4
SLP:     ScalarCost = 2
SLP:     ReuseShuffleCost + VecCost - ScalarCost = 2
```

However if we move the constants `1` and `-1` into phi nodes, then SLP doesn't cost them at all and unprofitably vectorizes the code:

```llvm
define void @f(ptr %p, i1 %c) {
 %p.0 = getelementptr i8, ptr %p
  %p.1 = getelementptr i8, ptr %p, i32 1
  br i1 %c, label %a, label %b
a:
  br label %d
b:
  br label %d
d:
  %x = phi i8 [1, %a], [-1, %b]
  %y = phi i8 [-1, %a], [1, %b]
  store i8 %x, ptr %p.0
  store i8 %y, ptr %p.1
  ret void
}
```

```llvm
0.
Operand 0:
    %x = phi i8 [ 1, %a ], [ -1, %b ]
    %y = phi i8 [ -1, %a ], [ 1, %b ]
Operand 1:
 %p.0 = getelementptr i8, ptr %p
    %p.1 = getelementptr i8, ptr %p, i32 1
Scalars: 
    store i8 %x, ptr %p.0, align 1
    store i8 %y, ptr %p.1, align 1
State: Vectorize
MainOp:   store i8 %x, ptr %p.0, align 1
AltOp:   store i8 %x, ptr %p.0, align 1
VectorizedValue: NULL
ReuseShuffleIndices: Empty
ReorderIndices: 
UserTreeIndices: 
SLP: Costs:
SLP:     ReuseShuffleCost = 0
SLP:     VectorCost = 1
SLP:     ScalarCost = 2
SLP:     ReuseShuffleCost + VecCost - ScalarCost = -1
```

Although the resulting code from these two functions are different, the vector of `<1, -1>`  and/or `<-1, 1>` will need to be materialised in both cases:

```
f: # @f
        .cfi_startproc
# %bb.0:
        vsetivli        zero, 2, e8, mf8, ta, ma
        vid.v   v8
        andi    a1, a1, 1
        vadd.vv v8, v8, v8
        beqz    a1, .LBB0_2
# %bb.1:
        vrsub.vi        v8, v8, 1
        vse8.v  v8, (a0)
        ret
.LBB0_2:                                # %b
        vadd.vi v8, v8, -1
        vse8.v  v8, (a0)
        ret
.Lfunc_end0:
        .size   f, .Lfunc_end0-f
        .cfi_endproc
                                        # -- End function
        .globl  g                               # -- Begin function g
        .p2align        2
        .type   g,@function
g: # @g
        .cfi_startproc
# %bb.0:
        andi    a1, a1, 1
        beqz    a1, .LBB1_2
# %bb.1:                                # %forward
        vsetivli        zero, 2, e8, mf8, ta, ma
        vid.v   v8
        vadd.vv v8, v8, v8
        vrsub.vi        v8, v8, 1
        vse8.v  v8, (a0)
        ret
.LBB1_2:                                # %backward
        vsetivli        zero, 2, e8, mf8, ta, ma
        vid.v   v8
        vadd.vv v8, v8, v8
        vadd.vi v8, v8, -1
        vse8.v  v8, (a0)
        ret
```

So whilst we currently account for the cost of constants via `OperandValueInfo` in `getArithmeticInstrCost`/`getMemoryOpCost`, we don't factor in phi nodes which aren't themselves constants, but have constant operands. 

I believe this is related to the discussion at https://reviews.llvm.org/D126885, as there are three ways I can think of doing this:

1) Update `getOperandInfo` to account for phi nodes and mark them as `OK_[Non]UniformConstantValue` to trick TTI into including the cost for constant materialisation, despite them not really being constant (This would also only work for the reciprocal cost since we would only be costing for one of the N possible incoming values)
2) Modify `OperandValueInfo` to somehow store information that a constant/multiple constants will need to be materialised and should be costed by the TTI (the same idea as 1) above, but more explicit)
3) Reintroduce the `getConstBuildVectorInstrCost` TTI hook from the earlier version of D126885, and invoke it whenever we encounter a phi node of constants in `getEntryCost`.

cc) @preames @alexey-bataev @RKSimon 
</pre>
<img width="1px" height="1px" alt="" src="http://email.email.llvm.org/o/eJzUONlu27zST0PfDGzI9BL7wheJ0-APvi4fmra3BSWNLP6hSB-Ssus-_cGQsiQ7TpoUPZsRRBI5K2encE5uNOKKzW7Y7HYgal8au0rrNBWD1OSH1bq2FrVXB3h4_zfkBh1o42GHmTdWOgRfIhRGKbOXegNFrTMvjQaj4fP9w3r4jfE1CAfSQ2asxYxI7Y19dGBqD74UPpDIjPNgCqiERyuFko7IxR3tvNDeQWFsWGmZ55AJh0Roj3JTurDrMqGEDQRZcsuSazZP4p9Suyou5VhIjbAzMgc2TTaML7beAuOzLckrx_SaMb4EdnUTUSDsjhJgk1vYoEeFFWpPaHJBSC2BPvj41-DEb8JhfMRLbcd_DUqkqOirMHYvbH6ylorsMSwG1CPE5PpIynljEeQCxn2Oo-TJ_vAUoC9Lywx1w6fl2jJ6js5TRm_hQy-dLhZ9sFdj06vbM-M2n5cWk1F8ftqiFTqHpEc2yNS9D8enoOMe6Js94Hd94CF4sGOTa-hIPWtLii8lN7rT4yXDnkM_eOGROH2LQfUT4_oHIfWnLW28mvG18hHjDcK2XPNvQtVBkI9f37-Pm5-xdvhQ1kWh8F7nMsNwJu-qrT8cIYzN0fY24_pXh_aLRXyy8fD-b_pYG-dda9pmkX59lgQUTJecgEWR283pExrRfC0AfwUTfkNkw_vwGfyLjv5_Zo87tCAL2CNUZodnKZPNkzGbJ0C-zObJMHxI7Q1sSwna5OjIJr5E3SZ4zfiVjwnZl1iB8CCUCiRqvbWmkF6k6nBMwz_RNUxzbI_0tZm3eE3m_c8mXnGaciO06OWFfvI6psiXt_t5jfHZjyArGUQugM1uQtAEzrPb8Dq7GR7XUlrrUA9nqMMLuJdQ2wAl9r_I2cTmctr-rZzc-cJLefniwUCrHXTqQXc20NPw4vF0sCcULhC4UAD-K7L_BXu9WAAuGO_tJeBt_C_VgVeg_Q-WAvqdlYPxv7ocHDuUi0F2rXxp6k0ZErJFVytPbTSlZiisqWideva9aTt1B8Ii5LIokBr9pho0yZ06cmIxWQe3GY7Z5B1VECoGjN8Z2-zGsDru7qVSoBFz8AZS7PX0mIPUkBpfhs7dPVcvmoY2GItPYqFo4JajrJDfnRfWb63JmmUC4rM0HSU9ksudQy93SrJk-ROtIRk5_cMQf1URHj4k-Ep0WDIf7ei5aJeEzomIiMHTKNvCizwf7RoMvob2_xEgxX_8bLFH729uku_8XO7xidzW1eloJ89IjvuKLUYdR8YXImF82e5bbGafI7fG1V74HUU5U-tchuFvCUHO9h11fmKdkQupZlnEY2lhhme2Rp13lv6VGn11hkN4p_PW0zuqG2VSxZLl5nVEbnAjdTfabjpCWx5SGEuWvFv0hy2ptWF8TY57wn3Tc-nN77j0i574xNHGlx3tlb5wHCj_eDj9MmL-bACM3xQAJzP1v1frPxZxF4vDg4F9KZXzNCtk7b2OyDJTa9_erhxvYrohYicF5fmmJQrV-V4XJo4StLNBf22lLyv0MrvXzodyRez5Xdz-gJWxh0_bdn1NQuQmzhqFCMVG6m4qIVGzkmpTBKFJxKHaoesEIypp7aEUu27mARPFdCPoK38PKSqJYUCSDqQDi0r4WKNI7Vy6rHaOAlx4KL3fhurE7xi_s7iTuHcjal1Hxm4Yv7sd8_liMWtut3yJFkMh9aVFhL04OLiHTGhipx_pPHMTb7TkedUb07TzdZsLj81hNid9PGRvTozUnRE1qJWwj82cFsa9T399Z7Obj0az2e1XLQtjq3VzNLGvigS9ldkjfPlyH6dBqTNV592Vm4us2kPtSrgIyYyvIUe3lR4jb208WBRKHSDF2HI0mIwvvtCJ702tchDKGTC6uQNsfc5iJin1CRV5O6kzJA-JWAEhjXKFW0bqTDTSqRL2R9ga52SqkPQwFYHsSFfXBgenM_5gclkcnnNlb8CZCkuzP7atmg4v6BvvKUWrFeN3FfVWW9Uftl_se8hWrgzqNJpgDukhKEBmYHwRbi9FhSBzFGTO4BkiNTs8unpFguGPrZKZ9K12E4L7jFJ7a_I6i5cA0ZWC7W9qqfLYqPajM_AtjXlse0NAYZVECzu0IRRMAX1P19S_7cwjgvSwL1GH24c9Aurgn2hBtP55mkTaTPFOe3toJBj14yCLY_802VoUFTp6FQp_4GGYCi9wRwuf_3qQldEwyFeTfDlZigGuxvMFn0yms6vloFzNrhYzMZ7OlunVZC74fMInRTrNk4lYzJJ8XAzkiid8kkz5dDxOlpPlaCoWPOXFgs_mV_N5lrJpgpWQqg33gXSuxtWcT_jVIMzyLlyYcx5m2Qk18-30YhnnbHY7sCvaHKb1xrFpoqTzXf4YeOkVrk4vXPoh_lzcBb9xJ4lyUFu1Ok1XG-nLOh1lpmL8LogYH8OtNf-PGXlv0MgxfheU-mcAAAD__1k966g">