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

    <tr>
        <th>Summary</th>
        <td>
            CodeGenPrepare Results in Incorrect Answer
        </td>
    </tr>

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

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

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

<pre>
    Consider the program written here https://godbolt.org/z/aWzvY6o88 (reproduced below)
```c
#include <stdio.h>

int A = 1103515245;

int main() {
  printf("%ld\n", (A * 12345) % ((long)2147483647));
  return 0;
}
```

Semantically the multiplication between A and `12345` is an integer and when it overflows, it should wrap around to be a negative number for a final result of -740563387. GCC gets this correct, as well as Clang at O0.

However, inspecting further, we find this is not the case at Clang O1 or above and it prints instead 1406926604. This bug occurs within the CodegenPrepare pass, as we see below.

```llvm
*** IR Dump Before CodeGen Prepare (codegenprepare) *** (function: main)
; ModuleID = '<source>'
source_filename = "<source>"
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"

@A = dso_local local_unnamed_addr global i32 1103515245, align 4
@.str = private unnamed_addr constant [5 x i8] c"%ld\0A\00", align 1

; Function Attrs: mustprogress nofree norecurse nounwind uwtable
define dso_local noundef i32 @main() local_unnamed_addr #0 {
  %1 = load i32, i32* @A, align 4, !tbaa !4
  %2 = mul nsw i32 %1, 12345
  %3 = sext i32 %2 to i64
  %4 = srem i64 %3, 2147483647
  %5 = call i32 (i8*, ...) @printf(i8* noundef nonnull dereferenceable(1) getelementptr inbounds ([5 x i8], [5 x i8]* @.str, i64 0, i64 0), i64 noundef %4)
  ret i32 0
}

; Function Attrs: nofree nounwind
declare dso_local noundef i32 @printf(i8* nocapture noundef readonly, ...) local_unnamed_addr #1

attributes #0 = { mustprogress nofree norecurse nounwind uwtable "frame-pointer"="none" "min-legal-vector-width"="0" "no-trapping-math"="true" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+cx8,+fxsr,+mmx,+sse,+sse2,+x87" "tune-cpu"="generic" }
attributes #1 = { nofree nounwind "frame-pointer"="none" "no-trapping-math"="true" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+cx8,+fxsr,+mmx,+sse,+sse2,+x87" "tune-cpu"="generic" }

!llvm.module.flags = !{!0, !1, !2}
!llvm.ident = !{!3}

!0 = !{i32 7, !"Dwarf Version", i32 4}
!1 = !{i32 1, !"wchar_size", i32 4}
!2 = !{i32 7, !"uwtable", i32 1}
!3 = !{!"clang version 14.0.0 (https://github.com/llvm/llvm-project.git 329fda39c507e8740978d10458451dcdb21563be)"}
!4 = !{!5, !5, i64 0}
!5 = !{!"int", !6, i64 0}
!6 = !{!"omnipotent char", !7, i64 0}
!7 = !{!"Simple C++ TBAA"}
*** IR Dump After CodeGen Prepare (codegenprepare) *** (function: main)
; ModuleID = '<source>'
source_filename = "<source>"
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"

@A = dso_local local_unnamed_addr global i32 1103515245, align 4
@.str = private unnamed_addr constant [5 x i8] c"%ld\0A\00", align 1

; Function Attrs: mustprogress nofree norecurse nounwind uwtable
define dso_local noundef i32 @main() local_unnamed_addr #0 {
  %1 = load i32, i32* @A, align 4, !tbaa !4
  %2 = sext i32 %1 to i64
  %3 = mul nsw i64 %2, 12345
  %4 = srem i64 %3, 2147483647
  %5 = call i32 (i8*, ...) @printf(i8* noundef nonnull dereferenceable(1) getelementptr inbounds ([5 x i8], [5 x i8]* @.str, i64 0, i64 0), i64 noundef %4)
  ret i32 0
}

; Function Attrs: nofree nounwind
declare dso_local noundef i32 @printf(i8* nocapture noundef readonly, ...) local_unnamed_addr #1

attributes #0 = { mustprogress nofree norecurse nounwind uwtable "frame-pointer"="none" "min-legal-vector-width"="0" "no-trapping-math"="true" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+cx8,+fxsr,+mmx,+sse,+sse2,+x87" "tune-cpu"="generic" }
attributes #1 = { nofree nounwind "frame-pointer"="none" "no-trapping-math"="true" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+cx8,+fxsr,+mmx,+sse,+sse2,+x87" "tune-cpu"="generic" }

!llvm.module.flags = !{!0, !1, !2}
!llvm.ident = !{!3}

!0 = !{i32 7, !"Dwarf Version", i32 4}
!1 = !{i32 1, !"wchar_size", i32 4}
!2 = !{i32 7, !"uwtable", i32 1}
!3 = !{!"clang version 14.0.0 (https://github.com/llvm/llvm-project.git 329fda39c507e8740978d10458451dcdb21563be)"}
!4 = !{!5, !5, i64 0}
!5 = !{!"int", !6, i64 0}
!6 = !{!"omnipotent char", !7, i64 0}
!7 = !{!"Simple C++ TBAA"}
```

Specifically this pass moves the multiply below the sign extension instruction, resulting in the incorrect value shown here. This alone is the cause of the issue as shown executing the pre codegenprepare (https://godbolt.org/z/9naj3cfd4) getting the correct value and the post codegen prepare getting the incorrect value (https://godbolt.org/z/xEE3WGMnK). This is able to cause Rodinia to get incorrect values (as this code is minimized from there).

cc @ftynse @jdofert @ivanradanov
</pre>
<img width="1px" height="1px" alt="" src="http://email.email.llvm.org/o/eJztWVuP27YS_jXeF8KGRFmW_OAH726SExwULZKgxXlaUBJlM6VIg6Rsb359P1IXS7vbg_Y5C8gyJc4MZ4bfXEwXunrePWhlRcUNcUdOTkYfDGvIxQjnuCJHbjg5Oneyi2S_oB9xHXRVaOlW2hzw9AMf9seP8_82Os_JguaGQ0bVlrwiBZf6sqDbRfS4iPaLTdRdZf9ME6FK2VacLJIH6yqhV8dF8qGfDXehHNlj-pHEcZSkcUrX6SK5f0nSMKGwNJYii6yfJbAFc3V4Txc0ldUifVBh_OAVhVy6JzFNINIz0pQE2lxqBcu2NF5n6zzZrDNvAq5klGy4a40i0U2V7PGFkVMVv_KGKSdKJuVz8HLTSidOEm-c0Ap-chcOZ-8JUxUBc6fUJiLC4hWBGfyADfKzlyMIhSP6zE0N91pvDZ7tUbcS04adCDO6BanTkEwYUfyAdc6cqLYpIKbWEEVqoZiEJRa6EF2TZbaO0k2S5NmKfHp4IAfuLJSFBqU2hpfOL8QsuXAp_feDZOpAmCO_Rqupsf_RFw7dglrKnsAoQFe3BoaHtxfu16462biUdsEpJbPcy-sE_xoTr2YBO4PdMDHsp_VSHWcVidfRZks3m2i9It-8rKI9EF2WrYGSAtJVEPugKzhP_QZcMmD5xKwdLSGW8w6lMxPGTZTy3Axg7S_y-Qt5bJsTuefwYyf-E7ZkkA_8lN2Kp-5Nh62BG9N1q0q_7QioHrhDgCT35BeEjuSfHwPmFzTzkaFbU3IfGHgMhN2bp1pIrljDe1o6p6UdrWMGO0kq5phkz7p1AzVfNtCAL080A473CQ03_xjPH_1osw63pRgGde6ZYpovVe4Hm4EHc1_jLuSm6zsDvI-aXvPNEwhb9afSF7WUQrXX5UG1I1d_X0dd8FdWP0mN-CHh_tQqb3f1xKrKkIPUBWZEQqdJwm-xFAdF1qOslXUmiAOQzsxxMhNTIg06hClZpPcpuRKRL9JHUk5yB4TgFvUZpJMez_TFBn7sd5fsnTM27HFrXUir3Hqw1waYU4COB6ofteriw6G9OFZI3kmqOEKET-z2ZHgZrIQpk4T3hkeQWaNpIoQBcTBcasQNRITg9F97L2w_dVbIjbErGPPf64kIGkQgdRFlL50ikOsZunR1o0wCpeVXN5BRn4w8eG5E647I8MZPBDYva5J1b7RpoPX5sxeYY3do0Hu1WoUIW0djug9zo8eUVqoFIyocr_FRJQ9-pnnsGQFOLnnDlTsBHUIVns2GSjDBQXDL7Dl4ziMq-BIGRJPBdhgPSnh7xzgP9SMYEr2sHv8HRiNyOrwMOCmlzzp_C5RXTinZCbWLj3QGqVQr-Tzx5duImiGdQStRtI7bHmw-rrP7f4l1nwpqdBtIQtrXOBOSGJxLsWnYIb_TtBFIEKhgcnlGLdFmeRGVO46UUU-m9NKh9p1QbJYNmxA40w6iEN_ln0vo5zpJRVsDEUsrfvCRPO9pu7y1LE_tOIWstQSEZ_M1Z96ddiRa0PvyCiEPGNRXa7pR01y7gbV8HNBudM2zQWar-GxFVBFuRBmmB4zMXR-Prn-Bj3_k25_GaUMRj31FXzWhyK5qyQ62L0mxT5c0jvr8F_ff9Cah50WnrNycKXm9TDSh8JGY9fKg1OOFmZr8zo31PQAdcjFS72Sp-AV_fOO_lEdmngb3v8VM_37xocjcOOMpZzI3DGRlaMbOnbZouVbRKvLJ8cVPArRbbbEqdYOH0DR1Xx423wGbFQhIQrd1xZJtmUYZz9FtbrO8iqN1mq_TuCqrgsboPwse0ufM8eu5WmlvT3rLuBPi9JUNgP_Y9aNReYtp84pJN0qcgHlstnf4TUD2poDslYCvovEdjwcrLvLtfr-fm_WyodzXiNL3fvK9n_yp-slplxi_7hKTedPZNYr0rabzvZ987yff-8n3fvK9n3zvJ3_GfvLNg-cTL0U9HjwLG44_SaPP3E4Pop-7Q9Dwyvq6jaLMVdgif9pq2q7BhKLdebE_0e2PV4Xqj4fJmcmW-3PoS_e3QX8qyyTygz_n7c54W-RtXXes1oKB2Z6HX5HWg-jujwhQzxrfN2Dy6p-IrWLfk7Ku1n0pHsXNlWTh-BmLaOuGVciwzJTtpXX_QIXrhw_JH59-Uf-FCr0LvBd8eUJ30zngi66EEsy_8M3si1VCt8DGw_cqeA9lSzQI0orURjdeufBTYHZuXZa-RNfuWWENjL5XGqnV-SEaVGVYxZQ-31W7pNomW3bnhJN81__iGH5wfAk77I_ZyedRrz26L27uWiN3_y5S8Ri2Gbn5Y7oBru-Ou00UVUVaF1mdFEVcVKyMGM15lPMkj8pNficZ4Gh3aJB8TeGXDike7enjndjRCGV6g3Yxj_M0XfEyK4osS6M8j-OkSmAtRz8rVyG_YmPuzC6oVLQHi0kprLO3SQQEEM95WA7yWeuO2uwuttGW27uw9C6o_he47dDP">