Miscompilation of trivial loop after NodePushOut and NodePullIn

[haved]

Given the following code

int main() {
    for (int y = 0; y < 1; y++);
    return 0;
}

there is a miscompilation causing an infinite loop when compiled like so:

clang-17 src/main.c -o build/main.ll -S -emit-llvm -Xclang -disable-O0-optnone
opt-17 build/main.ll -o build/main-mem2reg.ll --passes=mem2reg -S
jlm-opt build/main-mem2reg.ll -o build/main-mem2reg-jlmopt.ll --NodePushOut
jlm-opt build/main-mem2reg-jlmopt.ll -o build/main-mem2reg-jlmopt-twice.ll --NodePullIn
clang-17 build/main-mem2reg-jlmopt-twice.ll -o build/jlm-opt-twice

The issue persists if breaking the for-loop into a while-loop.

The issue only appears when invoking NodePushOut and NodePullIn in two separate jlm-optcommands.

Removing any one of these passes causes the issue to disappear.

Compiling main-mem2reg-jlmopt.ll works, so the issue seams to appear in NodePullIn.

The mem2reg is also needed for the issue to appear. For reference, this is the content of main-mem2reg.ll:

; ModuleID = 'build/main.ll'
source_filename = "src/main.c"
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"

; Function Attrs: noinline nounwind uwtable
define dso_local i32 @main() #0 {
  br label %1

1:                                                ; preds = %4, %0
  %.0 = phi i32 [ 0, %0 ], [ %5, %4 ]
  %2 = icmp slt i32 %.0, 1
  br i1 %2, label %3, label %6

3:                                                ; preds = %1
  br label %4

4:                                                ; preds = %3
  %5 = add nsw i32 %.0, 1
  br label %1, !llvm.loop !6

6:                                                ; preds = %1
  ret i32 0
}

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

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

!0 = !{i32 1, !"wchar_size", i32 4}
!1 = !{i32 8, !"PIC Level", i32 2}
!2 = !{i32 7, !"PIE Level", i32 2}
!3 = !{i32 7, !"uwtable", i32 2}
!4 = !{i32 7, !"frame-pointer", i32 2}
!5 = !{!"clang version 17.0.6 ([email protected]:llvm/llvm-project.git 6009708b4367171ccdbf4b5905cb6a803753fe18)"}
!6 = distinct !{!6, !7}
!7 = !{!"llvm.loop.mustprogress"}

Here is the main function from main-mem2reg-jlmopt.ll:

define i32 @main() #0 {
bb1:
  br label %bb2

bb2:                                 ; preds = %bb5, %bb1
  %0 = phi i32 [ 0, %bb1 ], [ %4, %bb5 ]
  %1 = icmp slt i32 %0, 1
  br i1 %1, label %bb4, label %bb3

bb3:                                 ; preds = %bb2
  br label %bb5

bb4:                                 ; preds = %bb2
  %2 = add i32 %0, 1
  br label %bb5

bb5:                                 ; preds = %bb4, %bb3
  %3 = phi i1 [ false, %bb3 ], [ true, %bb4 ]
  %4 = phi i32 [ %0, %bb3 ], [ %2, %bb4 ]
  br i1 %3, label %bb2, label %bb6

bb6:                                 ; preds = %bb5
  ret i32 0
}

And here is the main function from main-mem2reg-jlmopt-twice.ll (this is the one that never terminates):

define i32 @main() #0 {
bb1:
  br label %bb2

bb2:                                 ; preds = %bb8, %bb1
  %0 = phi i32 [ 0, %bb1 ], [ %8, %bb8 ]
  %1 = icmp slt i32 %0, 1
  %2 = add i32 %0, 1
  br i1 %1, label %bb4, label %bb3

bb3:                                 ; preds = %bb2
  br label %bb5

bb4:                                 ; preds = %bb2
  %3 = add i32 %0, 1
  br label %bb5

bb5:                                 ; preds = %bb4, %bb3
  %4 = phi i1 [ false, %bb3 ], [ true, %bb4 ]
  br i1 %4, label %bb7, label %bb6

bb6:                                 ; preds = %bb5
  %5 = select i1 %1, i32 %0, i32 %2
  br label %bb8

bb7:                                 ; preds = %bb5
  %6 = select i1 %1, i32 %0, i32 %2
  br label %bb8

bb8:                                 ; preds = %bb7, %bb6
  %7 = phi i1 [ false, %bb6 ], [ true, %bb7 ]
  %8 = phi i32 [ %0, %bb6 ], [ %6, %bb7 ]
  br i1 %7, label %bb2, label %bb9

bb9:                                 ; preds = %bb8
  ret i32 0
}

[haved]

@phate Just a heads up, this bug is possibly a bit gnarly. I was curious and had a look at the RVSDG, and it might look like it is not the NodePullIn pass that is at fault, but instead the conversion to LLVM IR afterwards.

I'm not 100% certain, as I might have mixed up some boolean values in my head, but it appears as if a trivial delta in the RVSDG was turned into a select with the parameters in the wrong order or something.

[phate]

I can reproduce it.

[phate]

The node pullin optimization only seems to be the trigger, but not the culprit. When I comment out the convert_empty_gamma_node() function in rvsdg2jlm.cpp and convert the RVSDG without the special handling for empty gammas, then the programs created from both assemblies (with and without pullin) terminate.