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

    <tr>
        <th>Summary</th>
        <td>
            strict weak ordering check fail in SLPVectorizerPass::vectorizeGEPIndices
        </td>
    </tr>

    <tr>
      <th>Labels</th>
      <td>
            new issue
      </td>
    </tr>

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

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

<pre>
    I'm debugging an issue in wamrc, the ahead-of-time WASM compiler for the Web Assembly Micro Runtime (WAMR). For certain inputs, the compiler crashes with

```
assertion __comp(*(__first + __a), *(__first + __b)) failed: Your comparator is not a valid strict-weak ordering
```

Debugging this reveals a crash in LLVM:

```
* thread #1, name = 'wamrc', stop reason = SIGABRT
  * frame #0: 0x00007f2cc2f20981 libc.so.6`raise + 161
    frame #1: 0x00007f2cc2f21df7 libc.so.6`abort + 247
    frame #2: 0x0000561f5ec238ad wamrc`std::__u::__libcpp_verbose_abort(char const*, ...) + 173
    frame #3: 0x0000561f5db1860e wamrc`void std::__u::__check_strict_weak_ordering_sorted<llvm::StoreInst**, llvm::function_ref<bool (llvm::StoreInst*, llvm::StoreInst*)>>(llvm::StoreInst**, llvm::StoreInst**, llvm::function_ref<bool (llvm::StoreInst*, llvm::StoreInst*)>&) + 574
 frame #4: 0x0000561f5da9dc9a wamrc`llvm::SLPVectorizerPass::vectorizeStoreChains(llvm::slpvectorizer::BoUpSLP&) + 826
    frame #5: 0x0000561f5da9ca70 wamrc`llvm::SLPVectorizerPass::runImpl(llvm::Function&, llvm::ScalarEvolution*, llvm::TargetTransformInfo*, llvm::TargetLibraryInfo*, llvm::AAResults*, llvm::LoopInfo*, llvm::DominatorTree*, llvm::AssumptionCache*, llvm::DemandedBits*, llvm::OptimizationRemarkEmitter*) + 1824
    frame #6: 0x0000561f5da9c199 wamrc`llvm::SLPVectorizerPass::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) + 1385
    frame #7: 0x0000561f5b3bd9e2 wamrc`llvm::detail::PassModel<llvm::Function, llvm::SLPVectorizerPass, llvm::AnalysisManager<llvm::Function>>::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) + 18
    frame #8: 0x0000561f5e8aa137 wamrc`llvm::PassManager<llvm::Function, llvm::AnalysisManager<llvm::Function>>::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) + 615
    frame #9: 0x0000561f5b3beee2 wamrc`llvm::detail::PassModel<llvm::Function, llvm::PassManager<llvm::Function, llvm::AnalysisManager<llvm::Function>>, llvm::AnalysisManager<llvm::Function>>::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) + 18
    frame #10: 0x0000561f5e8ad2f8 wamrc`llvm::ModuleToFunctionPassAdaptor::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) + 680
    frame #11: 0x0000561f5b3bf142 wamrc`llvm::detail::PassModel<llvm::Module, llvm::ModuleToFunctionPassAdaptor, llvm::AnalysisManager<llvm::Module>>::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) + 18
    frame #12: 0x0000561f5e8a9197 wamrc`llvm::PassManager<llvm::Module, llvm::AnalysisManager<llvm::Module>>::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) + 743
    frame #13: 0x0000561f5b3b9aa4 wamrc`aot_apply_llvm_new_pass_manager + 6708
    frame #14: 0x0000561f5b37f498 wamrc`aot_compile_wasm + 280
    frame #15: 0x0000561f5b3537d2 wamrc`main + 4290
    frame #16: 0x00007f2cc2f0c3d4 libc.so.6`__libc_start_main + 244
    frame #17: 0x0000561f5b3526aa wamrc`_start + 42
```

The culprit appears to be in [StoreSorter](https://github.com/llvm/llvm-project/blob/main/llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp#L21704), which contains some code that is pretty fishy for a comparison function:

```c++
    if (isa<UndefValue>(V->getValueOperand()) ||
 isa<UndefValue>(V2->getValueOperand()))
      return false;
```

If both StoreInsts are have UndefValue operands, then the ordering between them is not defined, hence why we see the assertion failure.

Would a fix like the following work?

```patch
diff --git a/llvm-project/llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp b/llvm-project/llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp
--- a/llvm-project/llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp
+++ b/llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp
@@ -21671,28 +21671,21 @@ bool SLPVectorizerPass::vectorizeStoreCh
   // compatible (have the same opcode, same parent), otherwise it is
   // definitely not profitable to try to vectorize them.
   auto &&StoreSorter = [this](StoreInst *V, StoreInst *V2) {
-    if (V->getValueOperand()->getType()->getTypeID() <
- V2->getValueOperand()->getType()->getTypeID())
-      return true;
-    if (V->getValueOperand()->getType()->getTypeID() >
- V2->getValueOperand()->getType()->getTypeID())
-      return false;
-    if (V->getPointerOperandType()->getTypeID() <
- V2->getPointerOperandType()->getTypeID())
-      return true;
-    if (V->getPointerOperandType()->getTypeID() >
- V2->getPointerOperandType()->getTypeID())
-      return false;
-    if (V->getValueOperand()->getType()->getScalarSizeInBits() <
- V2->getValueOperand()->getType()->getScalarSizeInBits())
-      return true;
-    if (V->getValueOperand()->getType()->getScalarSizeInBits() >
- V2->getValueOperand()->getType()->getScalarSizeInBits())
-      return false;
-    // UndefValues are compatible with all other values.
-    if (isa<UndefValue>(V->getValueOperand()) ||
- isa<UndefValue>(V2->getValueOperand()))
-      return false;
+    if (auto T1 = V->getValueOperand()->getType()->getTypeID(),
+        T2 = V2->getValueOperand()->getType()->getTypeID();
+        T1 != T2) {
+ return T1 > T2;
+    }
+    if (auto T1 = V->getPointerOperandType()->getTypeID(),
+        T2 = V2->getPointerOperandType()->getTypeID();
+        T1 != T2) {
+ return T1 < T2;
+    }
+    if (auto S1 = V->getValueOperand()->getType()->getScalarSizeInBits(),
+        S2 = V2->getValueOperand()->getType()->getScalarSizeInBits();
+        S1 != S2) {
+      return S1 < S2;
+    }
     if (auto *I1 = dyn_cast<Instruction>(V->getValueOperand()))
       if (auto *I2 = dyn_cast<Instruction>(V2->getValueOperand())) {
 DomTreeNodeBase<llvm::BasicBlock> *NodeI1 =
@@ -21706,14 +21699,8 @@ bool SLPVectorizerPass::vectorizeStoreCh
                "Different nodes should have different DFS numbers");
         if (NodeI1 != NodeI2)
 return NodeI1->getDFSNumIn() < NodeI2->getDFSNumIn();
- InstructionsState S = getSameOpcode({I1, I2}, *TLI);
-        if (S.getOpcode())
-          return false;
         return I1->getOpcode() < I2->getOpcode();
       }
-    if (isa<Constant>(V->getValueOperand()) &&
-        isa<Constant>(V2->getValueOperand()))
-      return false;
 return V->getValueOperand()->getValueID() <
 V2->getValueOperand()->getValueID();
   };
```
</pre>
<img width="1" height="1" alt="" src="http://email.email.llvm.org/o/eJzMWtuO4jgTfhr3jQVKHCDhggsOzQqpe3c0sDP6ryInqRDvJHFkO82yT__LdgiQ0D19GmlakRpsV7nqq4OrHKiUbF8CzNB4gcarO1qrjIuZ_IcWIMVdxJPjbIOIX-AEonq_Z-Ue0xIzKWvArMQHWogYkSVWGWCaAU0GPB0oVgD-Pt8-4pgXFctB4JQLs-Y7RHguJRRRfsSPLBYcf61LQ4BI8H3--BWR6RCvucAxCEVZiVlZ1UqeNmk5xoLKDCQ-MJUhZ66fidM8zpxKCUIxXuIw1CSIBIjMEQnCMGVCKozIAochRWSqOd-ai8zcFKeU5ZAgb47_x2thBKCCKi4wk7jkClP8RHOWYKkEi9XgAPQH5iIBwcp9RyzkzFctkCpjEgt4AppLTK1CGtSHh2-PyJv3lUJkjlUmgCYYEc_VgpdUI-etMCJ-Ywxfj0vFKyyASl6a6e3mj_ni6w45c6yVxakwhMRztGLOv47jOH5K4pikxJkGLs5ZFA8lH07QxBGUSTCouBPXsMBnBm6fgZuk_hUDGnFhYSUjv8uAnBmMJ246hph4AU0a35o4UmnwkTcPw_r0QTOvqvAJRMQlhIY_IkGcUW2gUipj0CUeDofahEZ03-vu7HV2TiI3mDjQ7vzEjVX728cZxD9Ca-9Q2zs82TuUXCjtLcs8fyrs-q3iAjYnoYxc58m0LmPtp6GAFHnLiPNcR8Jz1Jek1zNT5N3r53naF8l_qVhkcrLC2B9pK7QmGHVNQKdJPKWtCS7YPnz5BrHigv0H4guV0g4_ncbMtsuMslJeCSrzql0j7NCC_11tH75ciBWQSdc5xn3JYuo7r5dM1OWmqPIrYdYNrGbrK9BimlNx_8Tz2s53QN1RsQe1E7SUKRfFpkz5M2seWCSoON5cMZ9_BVnnOpt2Zh44r26SrHjBSp3tdgKgz1DKuqi0xEsaZ_35FRS0TCBZsBt7_lUpVrD_qCb_CgUVP-4LphQI6zg2agMy6lpmcsMy7nT6Jsu8zirzkuZHyeQjLelee8_yBtGVf7teMO7K63fkjbwomQK5IW8CirLcftbiPvIE8tu7XntPT893qaGfX41P0EUn6Kb_gFLX82-gYxB5aaffVemJ2_OJad8nAD7VJ34ZWr8ryn3Xcp2-byUkDW6g_MiTOocdP7HW6M0TWikubgtuCd4kdkNy7RqB05Pa7ftG6o7e5xsnMS9lfEnXdyjznGk_CaEbZu1VjAGdutO3pIxbsPwW2vqjXpXqdsvUyIumlI5adSlXIa2q_Bhq3mEJh7CiUoaF3dP6me_0cewWX5Hnp6NpcMW46bfCA5WFreBveGy3Voq8secnZ48tdB-niUdk2qee9DoIJ_aS0VUHYUv-UCoqVNiyI6NeceD2T9sxmdBzRWl5NNL027Od7jHrvBJMYVpVQIXEiuPItLtovDBl5lYX-QKNV4gEmVKVqSvIGpH1nqmsjoYxLxBZG1Pbf4NK8H8gVoiso5xHiKy1EhdrmB5r6zuJyLo90RFZXx3ww7iqEPEeiOs7o6aBPWQsznTro1tmiSUvdKucAFYZVbpRrQQodcQpk9nRdOO06WSZbhHTNqN2284YkYV-LMws1V0AkxR5y7_LBNJvNK-tCwffBsi734MyQ39VIGiZmLbbdNHIX-rHmeNnqMlL5PqxEmAsQNWixCnNJSBv0TfhJsURVxluGxGJqQCc0SfA520xt3ucbhZKc71w6uNwBOoAdrA4NfoJpKyERBNkUMaAD9kRHwBLAHsB0l46pJTltYChFeg7r_MEU5yyf3HOftjFKc9zftBbHbj4gbx1B_iKqjhDzjxhaYoHg732x74zvdN9cPRprJAzHwwGnyibuehY2KeV8518Rg4aOXhA3InvIrIkgY779puLmwWmvX1lg2n90Ea7DSHFotxcXxkP07aVOhnxSgeguYzRXysqoFRNuHKVgTgwCZjp6LziabyMKciPxukqwVOmqN5CcazEUf9rhTL-ObT0tFYcm7NkcpGl7O3QeKEyJm3GauMCIzL_psW5HiE2XnVkDc5B_3x4NxO7YwW9gc3KDmHkLQ2_F-L8NXxsIhhcZQIl6iYRfKa4979K3IvEdUPeL5yVCkSz0xsxfQPxm4F8m2D3nyrYy5C93jT2lmXL_oNNaa8kPuqbtzn-Qi99VoV3--vrVeiaoUlY5zPVHrQXSfHAVIZpntuEh5_MouE1Bh-qJgYfKCeeVU4fPK14JqvuXJNGP5ZUEFmemeu_HbFcP5hjLmU2bF2MiKs57y5SuV7QqGq0udezl6TIX71G9zeF8k8Ufguv92m5fK2W2_da-Lnw6ai-fbetn9mgi8e2xWPbwePSy7cWlO0tUHAHEkTmG4tKcizDmEqFvKWuEkR9vn55OVAv6_Yua_Jz1j8L4kZJvOLFTgD8yRNYUB3FF132gkoWL3Ie_9A-j8hcr7J6XVWIvqNbd3fUVIhTbcLg_QXi1R8iZMXSFHQFiEuegMQyM02BKRmTdm613uKyLiIQEhHSmrllZCE8aWDNbb6RBunGzHZFg95qvf2zLjbl-bRraG7On_L7hTXkVlEFeGsMpj2SFvBXU90GyF9szKvIDdFuZF-m7h42F6yuhN8O96DO1J1kfDshd6da1S75GMVapa52uGRifb13_ix5KRUt1atOH1NjX6l2i8dHjqDT0E_zkZnoVISvyDJXZC0-GpvrjvoumXnJ1JvSO5i5vjd2HC9wx3fZLKKEQOB742gM0zGNR76XQurAJIpGvuO4d2xGHDJyCRk5rue442EyGVE6GU9hlKYQj3VcQUFZPtSxOuRif2d-VjBzieu407ucRpBL88MEQko42B8d6KgYr-7EzPSaUb2XaOTkTCp5ZqOYymFm387iq7fx2Ly4Nd05ZuVPA_qP-y-bMmExyLta5LM33_QYiXWf2qj0NCP_DwAA___xe_GM">