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

    <tr>
        <th>Summary</th>
        <td>
            [Attributor] Heap2Stack incorrectly performs transformation in the presence of tail calls, leading to DSE deleting everything
        </td>
    </tr>

    <tr>
      <th>Labels</th>
      <td>
      </td>
    </tr>

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

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

<pre>
    Here's a simple toy example which heap-allocates a string, adds a null terminator to it and passes it to `puts`:

<https://godbolt.org/z/hxYc3Pb1d> (full example on godbolt, shortened here in the issue for brevity)
```llvm
@.str = private constant [7 x i8] c"Hello, "

define i32 @main() {
entry:
  %0 = call ptr @malloc(i64 8)
  call void @llvm.memcpy.p0.p0.i64(ptr %0, ptr @.str, i64 7, i1 false)
  %1 = getelementptr inbounds i8, ptr %0, i64 7
  store i8 0, ptr %1
  call void @puts(ptr %0)
  call void @free(ptr %0)
  ret i32 0
}
declare void @puts(ptr noalias nocapture readonly) #0
attributes #0 = { nofree nounwind }
```

Simply running `opt` on this with -O3, does *some* things, such as adding attributes, but largely the code stays the same.
However, enabling the attributor, which also enables heap2stack, correctly converts this heap alloc to a stack alloc, leading to much better optimizations, resulting in the following:

<https://godbolt.org/z/a3j4PxdxY>
```llvm
define noundef i32 @main() local_unnamed_addr #0 {
entry:
  %.h2s1 = alloca [8 x i8], align 1
  call void @llvm.memcpy.p0.p0.i64(ptr nocapture nofree noundef nonnull writeonly align 1 dereferenceable(7) %.h2s1, ptr noundef nonnull readonly align 1 dereferenceable(7) @.str, i64 noundef 7, i1 noundef false) #2
  %0 = getelementptr inbounds i8, ptr %.h2s1, i64 7
  store i8 0, ptr %0, align 1
  call void @puts(ptr nocapture nofree noundef nonnull readonly %.h2s1) #3
  ret i32 0
}
```

However, marking one of the calls as a `tail` call in the original, which is valid because `tail` only guarantees stability of the stack, and the original only deals with the heap, results in the exact same optimization, which is now invalid because the stack is being modified.
Indeed, Dead Store Elimination goes ahead and deletes basically the whole function, leading to changed semantics (the puts is now writing a null pointer, instead of the "hello" string that is expected).

<https://godbolt.org/z/rKTdrKPMv>
```llvm
define noundef i32 @main() local_unnamed_addr #0 {
entry:
  %.h2s1 = alloca [8 x i8], align 1
  tail call void @puts(ptr nocapture nofree noundef nonnull readonly %.h2s1) #1
  ret i32 0
}
```

Note that opt itself will never produce this, as it inserts `tail` annotations way later than the annotator does its job, I only ever encountered this because I was manually running passes out of order for experimentation sake.
I don't know what the policy is on passes breaking due to messing about like that, but this seems like quite a substantial break.
</pre>
<img width="1px" height="1px" alt="" src="http://email.email.llvm.org/o/eJzNV01z2zYQ_TXSBRMNRcqWdNDBiZOxJ9M2M-4lpwxILEXEIKASoGXl1_ctQEpyqsZNp4fOyBY_gN23i31vV6VTh80ddTTJl15I4XW7MySCOwh6lvF63-iqEQ3J3RtpjKtkoLgydNpuJ_k7IZXiB7Y3RgTqWm1lcB1sCB2EtErspPfYgzs8m1xnuz54fE2Km0l2O8nG_8W7JoSd58f5B3y2TpXOhJnr4ObDN_w1z5-r4lM5V5PivZjkq5pdjjidFcMOBuUb1wWypIC8I6GtCA2-vO9J1EBXdvSkw2GSrwfvwBM_xjy1w6NFNkOUYlLcil2nnxC4qJz1QdogJldvl-JZ6NXk6lZUkzy_IySHPeP6PCxFtbbwXOQCBlupLYDDrZgs36YVZEN3OCZDwMBVFp1WyLfYMQLeyLnHVn29EKsjbJEWPTmteBWDn7XUVrvDbJfxB8uxKRqBWcY3GOTQ-JbtLePFXNTSeDqzjS3ziGRLgQy1QMq7tS1db3HoiH40OBhP1obtHmWAyFciO1s2vwg8lsQ5zsvx1R3R5WUdhZjjbMj98nZMf2UkUFxwZJ00Wnp8V3IXeizqSCpnzSEeT14MtmRAqZc9lz0_jAnB4WEfw8FXb_caZX70eayl8zp4YGYdRNdbC94wDdwu4D_XbWi0F3sdGvHmt4JzpVx0duNdi3hveIHd-ljXPcgI0CAdmzlh45e4EIh2S3DE5V45RTgFefDx1suWZgnNndvTE8UCICtLw7Z4yWjPxVeJ-igKl1YBFOtADpPVIy-oXNdRFeAOxIC94FMsvErEimXKs1hggxhK-J0wyHP06ETL8ZQUIBwCCdGt_iaDBst4XUe-N4FXDvytHUzsWXd-Wjtk8XXx6Vk9f4Z2_C3lB7LykeLyAmlZ_8wXnCFSqb7gELqhJn5A5lmT-0SjpJ-sHatRO6KAGr214jIxfsToU-GelSLjts5GNd53OhAX9OhCKIhhjT9bEZ8nDC1TsSeUI0-_NzQS41U7L3VlNDPqy3g_6gznLv-L7P0TsTmifV1wstdS_EISXsnoMREnDDGK4jUduqgJZyxsZffIhe5Qfq5O7AVIH7nOahGkNiwXEfpAB9fpLbqtOXEV3HtCrAqUqmTv6XxnxL3tZYf-RaAySFlqgyY4OjzSmpv2uf20VRGOLckUv2SOn0jqR0xox1WIUvOCzy8gWrfH8pdAjwB4QUmci9YpXWtSg2bd4yRIsaFbnIJ4iIf93ug4cOjY_nkyafglR6BQRSzapfSas5Y0cd84DAt1b6sR1pkaVY20W8wMnlokSVcswivexTUyImdWRe1NI8_OaeQz1TyGA_Y-5BOTQJOmgnwYl_BYBrZDzzvoJkeznv2kkHUff1fdx0-_PP3vhYwL77-n2vxfUe1XFyhlH1WJUdSTqVHL8GOZghjwnOoriu0rhhLnVRxobGpnLJLWupBalNjLA_otty5YTuU_vMaEGXs4HImvrmSL94lF0Rt0E9FiI6nUMEcW3MOmhxjYPhbsOC0ME7RDf0dtuQ7yG6dYLqNOs1QmBnj5OHb4ewDAYS-DeIxFy6HHSnZGVweuQawf7GIYllF9VE-xKZP3scJL9mj0Y0rdOGJExJ6o9endHz3aDHf5vozDsYZiRJOzKW3m19fLolhdLbKp2hRqXazlNOhgaIPquTmNGxij73i2eEgaYE-jBUJErHAWoFyeL1Owg-DsIEDchyLrxorz3xH79uF90gO-5yM4xJFq2ndm8x3hoG99Oatci5tIqPT1BhXyFYBwG39FwMOHq9VysZg2G5XVq6t6XdWr67yss2Kdzxe0yJVaXy0KyvKpkSUZzxEjzqne5Fmez-fZPJ8XSMysQhtcrhdLpSoq1bwCUyBA2sxi9wf1p90mYih7TIEYCrQP_vQShwjeEY32ZR_w62fTHVpNZhrRbiLUPwH35XTJ">