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

    <tr>
        <th>Summary</th>
        <td>
            DSE in -O2 pipeline miscompiles but not when run alone
        </td>
    </tr>

    <tr>
      <th>Labels</th>
      <td>
            miscompilation,
            llvm:optimizations
      </td>
    </tr>

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

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

<pre>
    This is a weird bug and I need help debugging it.

See this C program (from @regehr):
```c
struct a {
   char b;
   long c
};
int *d;
static struct a e;
void(f)();
void g() {
   long *h = &e;
   *h = 0;
   *d = 0;
   e.b = 4;
   f();
   for (; e.b;)
     ;
}
```

Compile that with `clang -O2 -c -w -emit-llvm -fno-strict-aliasing -mllvm -print-after-all` and you get a miscompilation.
However, if we run `opt -dse` on the IR that is given to DSE in clang's pipeline there's no miscompilation.
The IR is:
```llvm
target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
target triple = "x86_64-unknown-linux-gnu"

%struct.a = type { i8, i64 }

@e = internal unnamed_addr global %struct.a zeroinitializer, align 8
@d = dso_local local_unnamed_addr global ptr null, align 8

; Function Attrs: nounwind uwtable
define dso_local void @g() local_unnamed_addr #0 {
entry:
  store i64 0, ptr @e, align 8
  %0 = load ptr, ptr @d, align 8
  store i32 0, ptr %0, align 4
  store i8 4, ptr @e, align 8
  tail call void (...) @f() #2
  %.pr = load i8, ptr @e, align 8
  %tobool.not = icmp eq i8 %.pr, 0
  br i1 %tobool.not, label %for.end, label %for.cond.preheader, !llvm.loop !5

for.cond.preheader:                               ; preds = %entry
  br label %for.cond

for.cond:                                         ; preds = %for.cond, %for.cond.preheader
  br label %for.cond

for.end:                                          ; preds = %entry
  ret void
}

declare void @f(...) local_unnamed_addr #1
```

Running both DSEs in debug mode (the one in clang pipeline and the opt freestanding one), there's a diff in the output:
```diff
 Trying to eliminate MemoryDefs killed by 3 = MemoryDef(2) (  store i8 4, ptr @e, align 8)
   trying to get dominating access
-   visiting 2 = MemoryDef(1)->liveOnEntry (  store i32 0, ptr %0, align 4)
+   visiting 2 = MemoryDef(1) (  store i32 0, ptr %0, align 4)
    visiting 1 = MemoryDef(liveOnEntry) (  store i64 0, ptr @e, align 8)
   Checking for reads of 1 = MemoryDef(liveOnEntry) (  store i64 0, ptr @e, align 8)
-   3 = MemoryDef(2)->1 (  store i8 4, ptr @e, align 8)
+   2 = MemoryDef(1) (  store i32 0, ptr %0, align 4)
+   3 = MemoryDef(2) (  store i8 4, ptr @e, align 8)
     ... skipping killing def/dom access
-   2 = MemoryDef(1)->liveOnEntry (  store i32 0, ptr %0, align 4)
  Checking if we can kill 1 = MemoryDef(liveOnEntry) (  store i64 0, ptr @e, align 8)
 DSE: Partial overwrite: DeadLoc [0, 8) KillingLoc [0, 1)
 DSE: Partial overwrite a dead load [0, 8) by a killing store [0, 1)
-DSE: Merge Stores:
-  Dead:   store i64 0, ptr @e, align 8
-  Killing:   store i8 4, ptr @e, align 8
-  Merged Value: 4
+  trying to get dominating access
+   visiting 0 = MemoryDef(liveOnEntry)
+   ...  found LiveOnEntryDef
+  finished walk
 Trying to eliminate MemoryDefs that write the already existing value
 Trying to eliminate MemoryDefs at the end of the function
```

To me, this suggested there was something wrong in MemorySSA, as `liveOnEntry` is different. But I printed MemSSA at the entry of DSE and they are both equal:
```llvm
define dso_local void @g() local_unnamed_addr #0 {
entry:
; 1 = MemoryDef(liveOnEntry)
  store i64 0, ptr @e, align 8
; MemoryUse(1)
  %0 = load ptr, ptr @d, align 8
; 2 = MemoryDef(1)
  store i32 0, ptr %0, align 4
; 3 = MemoryDef(2)
  store i8 4, ptr @e, align 8
; 4 = MemoryDef(3)
  tail call void (...) @f() #2
; MemoryUse(4)
  %.pr = load i8, ptr @e, align 8
  %tobool.not = icmp eq i8 %.pr, 0
  br i1 %tobool.not, label %for.end, label %for.cond.preheader, !llvm.loop !5

for.cond.preheader:                               ; preds = %entry
  br label %for.cond

for.cond:                                         ; preds = %for.cond.preheader, %for.cond
  br label %for.cond

for.end:                                          ; preds = %entry
  ret void
}
```

So I have no clue what's causing the difference in the execution.
Any ideas?

cc @alinas @fhahn @aeubanks @nikic @preames 
</pre>
<img width="1px" height="1px" alt="" src="http://email.email.llvm.org/o/eJztWFlz47gR_jXUC4oqHpIsP-jBY48rU9mtTa0neZ0CyaaEmAK4IGiN5tfna0AHdcRHaraSh7hUNNkAvm70iUZhqu3i60p1Aj8pNqRsJYp-KaSuxBehiSqxoqYVFYG6VHoplBtHyUOU3IXnE5FwDHAvWmuWVq5FlM1ra_B_klha0spG2W2U7-ZHsyT8yvDdOduXDryjm0-BIoQoV9KKIsqPlMaA9W5JdPNwGFLagd9ddSB0TjpVigMsHUZejKpYNJYmm3uZBiNiGYgncniugF-JKH_Ay4yGMh0GkjNqdUmlceGJkyGxPpODScay_kDiJTyC8f0gwPdTWQen-hwa5d6sW9WwYaQTG-UgJhTeSOwm_i0TcSnijYhprVzcNC9rEdfaxFCZKl0sGyU7NnS8DmOthZJjWTuyGGyA5L1ja3qxJFbxWnWlZwjNG73zjr-YDb0QTH8vVA3HErbXLIVpnYirjhjGaEhI4svvQVA40VK9EIhGPDx9FkoLL3OU3XSiVS01SvOeyJInaXOd9deAqbpLp-MdBZKTlqWvpJONxF7czsQZxWuso7jNbmDBuzzzD_5MTz_5bTbxj1jtX-o5L0qzeazn_DLbr8HYU8rmzk74Q-ctDLXj_X0--4aJvX7WZqNj7Lf_Hi91f1i1e2bT4N9j6Ve6bUvst0LNvb5nE3H0j_CcJIEJTElWy0b0Wss1Vd9kVVmxbEwB2hD3B1mjtHIK_vAj2BFvSy3mB8Tg5lVnvjWmxHL__HYNuHVW6B6-c4ESnvD2x16XbENx55xly8G8vd4oeFq_cbJoKMytqGYvOHL1wQtp9vF7RYooy5NjXJN2dntwDYFUYSx5pSUsH8vK6rqQlUN7mvg9N0ZWPHEwv7oyf4ecZwNkQBxnTs5mzkF5XQQnVSOwwf2-s_l4PPZpa5LU-wyW5dlA5HFrj0IHD3l9j84UxjRjbUJMqHLdCvqDpQtovCrZzy-sUOnpKh5vZEHeoZDQxqSrC1ppdAUsWpGsgntFWcrhOW6MafljOnSRK0vykBL__R-7FaZX3S68psHyR8EvBLrG8W0-r3A8gPj9Xdv4B6Shjwnzxv4tso8viWf1ZBdlyLzwyH1w1UdHux5f6SvV6HdM5oJSGBQiJPaOM7s_UIi1qYidmMuAQVjvU_4x3XOp8aOoG7UlQn3XFaNhuq_k94OKIEWl6ppR_JLetb27LAI8Z6eFr3bLWCg44LZWWjoSv9La2O0D1Z14Vk2DE1CxFbnX4WEIImch1ObvCd5BDXcHjr78GM-UKbIsqevCvBgTX1Sn_EB2wToFYBzlnxtUy9_0Z7bqiSSvJZy9KFH26W0mH0YVQ8z0AnMg8Dn6a-l3gH6_ovKZwfmgZBFCnTD1z-fEBrhuctZ7-lG7B2X_JB0HsJ_mkEIgsEX3rNqW9couz_8rxnyEf1445p_jjwPThvNiKbUX5k9wI-QgTqR_k5aPN8LgnLqxyhETH-BTv5hSRNNPHshX1L8GpQzp6dtwnI6AFgrvCR4SijxoOkh-iRvvcH8lnBTFE886nmhhCJY01IP3nmCwaLeTk3VvnTqwzMtQiX_Ipvdamgxc8V0Z7SzdJG_YdLiI3RPh3qMQ_HKcxKuOk3AmVN0KEm5k8_y-3B56I28nLhay4WyyFfRddV7EF7_Xd0EBiCFQnzkZ8Wu9O82-UhW_onuhUL7Q-HTorlHbqArVDPsAzawJg2C8sdyIoqwFpk9Pd95IHTdUQ8WhpwIW1zdgaDcWn9DXfBG-gwM0VmPpUVyOUwjMvdauzMIvwdwXavqjl81rHdTPPonzceWtWP_omZ0xA9rf0XKGTPWfneYZ6Xrm--hpn5GuZ-8PdgMMNLkAygdAH-sWzpU1OVXW__uI_34fcb7TM47_S33EtZz3ZJCNVvKF-O6mRH4VG2Rhf3QvZe9vnTgz7RNYSfujPH2nsh9c8dzprVAoriiIj0MGZcn-CFfUnBzh5Cu50p5EfSH1sydq9az8PGwKqakTI1qks1mW5lmazkfVIq9u81s5cso1tNjdRPG92aEpOVw7YXGBFMsuvlmR9pdcskFrMupts1g51_qSnT3it1Ru1RewyBofPo2Gf3FrzT-phBoeVdf1KPLZ4_Rmms1Hq0WZTKZVgQid1rdE09tZWkia5el8mhXlPLkdeWN3C5weoiw7vQ3jSyPvJJlnlt-hhULx-uEHOx6dPozUIkuyLLlNECf43YxpXqbZbCZniazL8ibn8F4jjYx9TBm7HNmFlxrtW4fBBuWyOw7KrkMaIPISAV_2bmXsQvfatI1pqRv5PS78Bv8Fen9z-Q">