Repository: bytecodealliance/wasmtime (rust)

Issue:
Divergent behavior between regalloc_algorithm={backtracking,single_pass}
Found via oss-fuzz in https://issues.oss-fuzz.com/issues/387110342 I've minimized this to:

```wasm
(module
  (func (export "")
    call 1
    f64.const 0
    f64.const 0
    f64.ne
    if
    end
    call 0
  )

  (func
    f64.const nan
    f64.const 0
    f64.eq
    if
      loop
      end
    end
  )
)
```

which I can show different behavior with:

```
$ wasmtime run --invoke '' -W fuel=$((1<<62)) -C cranelift-regalloc-algorithm=backtracking foo.wat
Error: failed to run main module `foo.wat`

Caused by:
    0: failed to invoke ``
    1: error while executing at wasm backtrace:
           0: <unknown>!<wasm function 1>
           1:   0x1e - <unknown>!<wasm function 0>
           2:   0x36 - <unknown>!<wasm function 0>
...
         16365:   0x36 - <unknown>!<wasm function 0>
         16366:   0x36 - <unknown>!<wasm function 0>
    2: wasm trap: call stack exhausted
```

That's expected, this infinitely recurses. With `single_pass` though:

```
$ wasmtime run --invoke '' -W fuel=$((1<<62)) -C cranelift-regalloc-algorithm=single_pass foo.wat
Error: failed to run main module `foo.wat`

Caused by:
    0: failed to invoke ``
    1: error while executing at wasm backtrace:
           0:   0x1d - <unknown>!<wasm function 0>
           1:   0x36 - <unknown>!<wasm function 0>
    2: wasm trap: all fuel consumed by WebAssembly
```

Pull request:
Cranelift/s390x: do not use one-way conditional branches.
This is a followup to #10086, this time removing the one-armed branch variant for s390x. This branch was only used as the default-target branch in the `br_table` lowering. This PR incorporates the branch into the `JTSequence` pseudo-instruction. Some care is needed to keep the `ProducesBool` abstraction; it is unwrapped into its `ProducesFlags` and the `JTSequence` becomes a `ConsumesFlags`, so the compare for the jump-table bound (for default target) is not part of the pseudoinst. (This is OK because regalloc-inserted moves never alter flags, by explicit contract; the same reason allows cmp/branch terminators.)

Along the way I noticed that the comments on `JTSequence` claimed that `targets` included the default, but this is (no longer?) the case, as the targets are unwrapped by `jump_table_targets` which peels off the first (default) separately. Aside from comments, this only affected pretty-printing; codegen was correct.

With this, we have no more one-armed branches; hence, this fixes #9980.

<!--
Please make sure you include the following information:

- If this work has been discussed elsewhere, please include a link to that
  conversation. If it was discussed in an issue, just mention "issue #...".

- Explain why this change is needed. If the details are in an issue already,
  this can be brief.

Our development process is documented in the Wasmtime book:
https://docs.wasmtime.dev/contributing-development-process.html

Please ensure all communication follows the code of conduct:
https://github.com/bytecodealliance/wasmtime/blob/main/CODE_OF_CONDUCT.md
-->


Patch:
diff --git a/cranelift/codegen/src/isa/s390x/inst.isle b/cranelift/codegen/src/isa/s390x/inst.isle
index 7fad425ae..361aeded0 100644
--- a/cranelift/codegen/src/isa/s390x/inst.isle
+++ b/cranelift/codegen/src/isa/s390x/inst.isle
@@ -942,21 +942,6 @@
       (cond Cond)
       (trap_code TrapCode))
 
-    ;; A one-way conditional branch, invisible to the CFG processing; used *only* as part of
-    ;; straight-line sequences in code to be emitted.
-    ;;
-    ;; In more detail:
-    ;; - This branch is lowered to a branch at the machine-code level, but does not end a basic
-    ;;   block, and does not create edges in the CFG seen by regalloc.
-    ;; - Thus, it is *only* valid to use as part of a single-in, single-out sequence that is
-    ;;   lowered from a single CLIF instruction. For example, certain arithmetic operations may
-    ;;   use these branches to handle certain conditions, such as overflows, traps, etc.
-    ;;
-    ;; See, e.g., the lowering of `trapif` (conditional trap) for an example.
-    (OneWayCondBr
-      (target MachLabel)
-      (cond Cond))
-
     ;; An indirect branch through a register, augmented with set of all
     ;; possible successors.
     (IndirectBr
@@ -974,7 +959,14 @@
     ;; Jump-table sequence, as one compound instruction (see note in lower.rs
     ;; for rationale).
     (JTSequence
+      ;; The index into the list of targets.
       (ridx Reg)
+      ;; The default target.
+      (default MachLabel)
+      ;; The condition for taking the default target, based on flags
+      ;; when this instruction executes.
+      (default_cond Cond)
+      ;; All other targets.
       (targets BoxVecMachLabel))
 
     ;; Stack probe loop sequence, as one compound instruction.
@@ -2702,16 +2694,18 @@
 (rule (cond_br taken not_taken cond)
       (ConsumesFlags.ConsumesFlagsSideEffect (MInst.CondBr taken not_taken cond)))
 
-;; Helper for emitting `MInst.OneWayCondBr` instructions.
-(decl oneway_cond_br (MachLabel Cond) ConsumesFlags)
-(rule (oneway_cond_br dest cond)
-      (ConsumesFlags.ConsumesFlagsSideEffect (MInst.OneWayCondBr dest cond)))
-
 ;; Helper for emitting `MInst.JTSequence` instructions.
-(decl jt_sequence (Reg BoxVecMachLabel) SideEffectNoResult)
-(rule (jt_sequence ridx targets)
-      (SideEffectNoResult.Inst (MInst.JTSequence ridx targets)))
-
+(decl jt_sequence (Reg MachLabel Cond BoxVecMachLabel) ConsumesFlags)
+(rule (jt_sequence ridx default default_cond targets)
+      (ConsumesFlags.ConsumesFlagsSideEffect (MInst.JTSequence ridx default default_cond targets)))
+
+;; Emit a jump-table sequence based on a boolean condition for the
+;; default label.
+(decl jt_sequence_default_bool (Reg MachLabel ProducesBool BoxVecMachLabel) SideEffectNoResult)
+(rule (jt_sequence_default_bool ridx default (ProducesBool.ProducesBool default_producer default_cond) targets)
+      (with_flags_side_effect
+       default_producer
+       (jt_sequence ridx default default_cond targets)))
 
 ;; Helpers for instruction sequences ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
 
@@ -3358,11 +3352,6 @@
 (rule (cond_br_bool (ProducesBool.ProducesBool producer cond) taken not_taken)
       (with_flags_side_effect producer (cond_br taken not_taken cond)))
 
-;; Emit a one-way conditional branch based on a boolean condition.
-(decl oneway_cond_br_bool (ProducesBool MachLabel) SideEffectNoResult)
-(rule (oneway_cond_br_bool (ProducesBool.ProducesBool producer cond) dest)
-      (with_flags_side_effect producer (oneway_cond_br dest cond)))
-
 ;; Emit a conditional trap based on a boolean condition.
 (decl trap_if_bool (ProducesBool TrapCode) SideEffectNoResult)
 (rule (trap_if_bool (ProducesBool.ProducesBool producer cond) trap_code)
diff --git a/cranelift/codegen/src/isa/s390x/inst/emit.rs b/cranelift/codegen/src/isa/s390x/inst/emit.rs
index 53d383ea5..5e4bbb8fd 100644
--- a/cranelift/codegen/src/isa/s390x/inst/emit.rs
+++ b/cranelift/codegen/src/isa/s390x/inst/emit.rs
@@ -2002,21 +2002,21 @@ impl Inst {
                     match &inst {
                         // Replace a CondBreak with a branch to done_label.
                         &Inst::CondBreak { cond } => {
-                            let inst = Inst::OneWayCondBr {
-                                target: done_label,
-                                cond: *cond,
-                            };
-                            inst.emit_with_alloc_consumer(sink, emit_info, state);
+                            let opcode = 0xc04; // BCRL
+                            sink.use_label_at_offset(
+                                sink.cur_offset(),
+                                done_label,
+                                LabelUse::BranchRIL,
+                            );
+                            put(sink, &enc_ril_c(opcode, cond.bits(), 0));
                         }
                         _ => inst.emit_with_alloc_consumer(sink, emit_info, state),
                     };
                 }
 
-                let inst = Inst::OneWayCondBr {
-                    target: loop_label,
-                    cond,
-                };
-                inst.emit(sink, emit_info, state);
+                let opcode = 0xc04; // BCRL
+                sink.use_label_at_offset(sink.cur_offset(), loop_label, LabelUse::BranchRIL);
+                put(sink, &enc_ril_c(opcode, cond.bits(), 0));
 
                 // Emit label at the end of the loop.
                 sink.bind_label(done_label, &mut state.ctrl_plane);
@@ -3314,11 +3314,6 @@ impl Inst {
                 sink.add_uncond_branch(uncond_off, uncond_off + 6, not_taken);
                 put(sink, &enc_ril_c(opcode, 15, 0));
             }
-            &Inst::OneWayCondBr { target, cond } => {
-                let opcode = 0xc04; // BCRL
-                sink.use_label_at_offset(sink.cur_offset(), target, LabelUse::BranchRIL);
-                put(sink, &enc_ril_c(opcode, cond.bits(), 0));
-            }
             &Inst::Nop0 => {}
             &Inst::Nop2 => {
                 put(sink, &enc_e(0x0707));
@@ -3341,13 +3336,23 @@ impl Inst {
                 put_with_trap(sink, &enc[0..4], trap_code);
                 put(sink, &enc[4..6]);
             }
-            &Inst::JTSequence { ridx, ref targets } => {
+            &Inst::JTSequence {
+                ridx,
+                default,
+                default_cond,
+                ref targets,
+            } => {
                 let table_label = sink.get_label();
 
                 // This sequence is *one* instruction in the vcode, and is expanded only here at
                 // emission time, because we cannot allow the regalloc to insert spills/reloads in
                 // the middle; we depend on hardcoded PC-rel addressing below.
 
+                // Branch to the default target if the given default condition is true.
+                let opcode = 0xc04; // BCRL
+                sink.use_label_at_offset(sink.cur_offset(), default, LabelUse::BranchRIL);
+                put(sink, &enc_ril_c(opcode, default_cond.bits(), 0));
+
                 // Set temp register to address of jump table.
                 let rtmp = writable_spilltmp_reg();
                 let inst = Inst::LoadAddr {
diff --git a/cranelift/codegen/src/isa/s390x/inst/mod.rs b/cranelift/codegen/src/isa/s390x/inst/mod.rs
index 75e7daab7..139255c26 100644
--- a/cranelift/codegen/src/isa/s390x/inst/mod.rs
+++ b/cranelift/codegen/src/isa/s390x/inst/mod.rs
@@ -221,7 +221,6 @@ impl Inst {
             | Inst::Jump { .. }
             | Inst::CondBr { .. }
             | Inst::TrapIf { .. }
-            | Inst::OneWayCondBr { .. }
             | Inst::IndirectBr { .. }
             | Inst::Debugtrap
             | Inst::Trap { .. }
@@ -952,7 +951,7 @@ fn s390x_get_operands(inst: &mut Inst, collector: &mut DenyReuseVisitor<impl Ope
         Inst::IndirectBr { rn, .. } => {
             collector.reg_use(rn);
         }
-        Inst::CondBr { .. } | Inst::OneWayCondBr { .. } => {}
+        Inst::CondBr { .. } => {}
         Inst::Nop0 | Inst::Nop2 => {}
         Inst::Debugtrap => {}
         Inst::Trap { .. } => {}
@@ -1087,10 +1086,6 @@ impl MachInst for Inst {
             &Inst::ReturnCall { .. } | &Inst::ReturnCallInd { .. } => MachTerminator::RetCall,
             &Inst::Jump { .. } => MachTerminator::Uncond,
             &Inst::CondBr { .. } => MachTerminator::Cond,
-            &Inst::OneWayCondBr { .. } => {
-                // Explicitly invisible to CFG processing.
-                MachTerminator::None
-            }
             &Inst::IndirectBr { .. } => MachTerminator::Indirect,
             &Inst::JTSequence { .. } => MachTerminator::Indirect,
             _ => MachTerminator::None,
@@ -3212,11 +3207,6 @@ impl Inst {
                 let cond = cond.pretty_print_default();
                 format!("jg{cond} {taken} ; jg {not_taken}")
             }
-            &Inst::OneWayCondBr { target, cond } => {
-                let target = target.to_string();
-                let cond = cond.pretty_print_default();
-                format!("jg{cond} {target}")
-            }
             &Inst::Debugtrap => ".word 0x0001 # debugtrap".to_string(),
             &Inst::Trap { trap_code } => {
                 format!(".word 0x0000 # trap={trap_code}")
@@ -3225,25 +3215,34 @@ impl Inst {
                 let cond = cond.pretty_print_default();
                 format!("jg{cond} .+2 # trap={trap_code}")
             }
-            &Inst::JTSequence { ridx, ref targets } => {
+            &Inst::JTSequence {
+                ridx,
+                default,
+                default_cond,
+                ref targets,
+            } => {
                 let ridx = pretty_print_reg(ridx);
                 let rtmp = pretty_print_reg(writable_spilltmp_reg().to_reg());
-                // The first entry is the default target, which is not emitted
-                // into the jump table, so we skip it here.  It is only in the
-                // list so MachTerminator will see the potential target.
                 let jt_entries: String = targets
                     .iter()
-                    .skip(1)
                     .map(|label| format!(" {}", label.to_string()))
                     .collect();
                 format!(
                     concat!(
+                        "jg{} {} ; ",
                         "larl {}, 14 ; ",
                         "agf {}, 0({}, {}) ; ",
                         "br {} ; ",
                         "jt_entries{}"
                     ),
-                    rtmp, rtmp, rtmp, ridx, rtmp, jt_entries,
+                    default_cond.pretty_print_default(),
+                    default.to_string(),
+                    rtmp,
+                    rtmp,
+                    rtmp,
+                    ridx,
+                    rtmp,
+                    jt_entries,
                 )
             }
             &Inst::LoadSymbolReloc {
diff --git a/cranelift/codegen/src/isa/s390x/lower.isle b/cranelift/codegen/src/isa/s390x/lower.isle
index 3b403ef5b..f3bcfc6ec 100644
--- a/cranelift/codegen/src/isa/s390x/lower.isle
+++ b/cranelift/codegen/src/isa/s390x/lower.isle
@@ -3729,17 +3729,15 @@
 ;; list of branch targets per index value.
 (rule (lower_branch (br_table val_idx _) (jump_table_targets default targets))
       (let ((idx Reg (put_in_reg_zext64 val_idx))
-            ;; Bounds-check the index and branch to default.
-            ;; This is an internal branch that is not a terminator insn.
-            ;; Instead, the default target is listed a potential target
-            ;; in the final JTSequence, which is the block terminator.
+            ;; Bounds-check the index and create a ProducesBool that
+            ;; denotes the "default target" condition.
             (cond ProducesBool
               (bool (icmpu_uimm32 $I64 idx (jump_table_size targets))
-                    (intcc_as_cond (IntCC.UnsignedGreaterThanOrEqual))))
-            (_ Unit (emit_side_effect (oneway_cond_br_bool cond default))))
+                    (intcc_as_cond (IntCC.UnsignedGreaterThanOrEqual)))))
         ;; Scale the index by the element size, and then emit the
         ;; compound instruction that does:
         ;;
+        ;; [cond branch to default]
         ;; larl %r1, <jt-base>
         ;; agf %r1, 0(%r1, %rScaledIndex)
         ;; br %r1
@@ -3751,7 +3749,8 @@
         ;; PC-rel offset to the jumptable would be incorrect.
         ;; (The alternative is to introduce a relocation pass
         ;; for inlined jumptables, which is much worse, IMHO.)
-        (emit_side_effect (jt_sequence (lshl_imm $I64 idx 2) targets))))
+        (let ((shifted_idx Reg (lshl_imm $I64 idx 2)))
+          (emit_side_effect (jt_sequence_default_bool shifted_idx default cond targets)))))
 
 
 ;;;; Rules for `brif` ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;


Test patch:
diff --git a/cranelift/codegen/src/isa/s390x/inst/emit_tests.rs b/cranelift/codegen/src/isa/s390x/inst/emit_tests.rs
index 7a5841e13..caaec0670 100644
--- a/cranelift/codegen/src/isa/s390x/inst/emit_tests.rs
+++ b/cranelift/codegen/src/isa/s390x/inst/emit_tests.rs
@@ -6713,119 +6713,6 @@ fn test_s390x_binemit() {
         "jg label0",
     ));
 
-    insns.push((
-        Inst::OneWayCondBr {
-            target: MachLabel::from_block(BlockIndex::new(0)),
-            cond: Cond::from_mask(1),
-        },
-        "C01400000000",
-        "jgo label0",
-    ));
-    insns.push((
-        Inst::OneWayCondBr {
-            target: MachLabel::from_block(BlockIndex::new(0)),
-            cond: Cond::from_mask(2),
-        },
-        "C02400000000",
-        "jgh label0",
-    ));
-    insns.push((
-        Inst::OneWayCondBr {
-            target: MachLabel::from_block(BlockIndex::new(0)),
-            cond: Cond::from_mask(3),
-        },
-        "C03400000000",
-        "jgnle label0",
-    ));
-    insns.push((
-        Inst::OneWayCondBr {
-            target: MachLabel::from_block(BlockIndex::new(0)),
-            cond: Cond::from_mask(4),
-        },
-        "C04400000000",
-        "jgl label0",
-    ));
-    insns.push((
-        Inst::OneWayCondBr {
-            target: MachLabel::from_block(BlockIndex::new(0)),
-            cond: Cond::from_mask(5),
-        },
-        "C05400000000",
-        "jgnhe label0",
-    ));
-    insns.push((
-        Inst::OneWayCondBr {
-            target: MachLabel::from_block(BlockIndex::new(0)),
-            cond: Cond::from_mask(6),
-        },
-        "C06400000000",
-        "jglh label0",
-    ));
-    insns.push((
-        Inst::OneWayCondBr {
-            target: MachLabel::from_block(BlockIndex::new(0)),
-            cond: Cond::from_mask(7),
-        },
-        "C07400000000",
-        "jgne label0",
-    ));
-    insns.push((
-        Inst::OneWayCondBr {
-            target: MachLabel::from_block(BlockIndex::new(0)),
-            cond: Cond::from_mask(8),
-        },
-        "C08400000000",
-        "jge label0",
-    ));
-    insns.push((
-        Inst::OneWayCondBr {
-            target: MachLabel::from_block(BlockIndex::new(0)),
-            cond: Cond::from_mask(9),
-        },
-        "C09400000000",
-        "jgnlh label0",
-    ));
-    insns.push((
-        Inst::OneWayCondBr {
-            target: MachLabel::from_block(BlockIndex::new(0)),
-            cond: Cond::from_mask(10),
-        },
-        "C0A400000000",
-        "jghe label0",
-    ));
-    insns.push((
-        Inst::OneWayCondBr {
-            target: MachLabel::from_block(BlockIndex::new(0)),
-            cond: Cond::from_mask(11),
-        },
-        "C0B400000000",
-        "jgnl label0",
-    ));
-    insns.push((
-        Inst::OneWayCondBr {
-            target: MachLabel::from_block(BlockIndex::new(0)),
-            cond: Cond::from_mask(12),
-        },
-        "C0C400000000",
-        "jgle label0",
-    ));
-    insns.push((
-        Inst::OneWayCondBr {
-            target: MachLabel::from_block(BlockIndex::new(0)),
-            cond: Cond::from_mask(13),
-        },
-        "C0D400000000",
-        "jgnh label0",
-    ));
-    insns.push((
-        Inst::OneWayCondBr {
-            target: MachLabel::from_block(BlockIndex::new(0)),
-            cond: Cond::from_mask(14),
-        },
-        "C0E400000000",
-        "jgno label0",
-    ));
-
     insns.push((
         Inst::CondBr {
             taken: MachLabel::from_block(BlockIndex::new(0)),
diff --git a/cranelift/filetests/filetests/isa/s390x/jumptable.clif b/cranelift/filetests/filetests/isa/s390x/jumptable.clif
index 2c71a5019..32acf6ea6 100644
--- a/cranelift/filetests/filetests/isa/s390x/jumptable.clif
+++ b/cranelift/filetests/filetests/isa/s390x/jumptable.clif
@@ -29,34 +29,33 @@ block5(v5: i32):
 ; VCode:
 ; block0:
 ;   llgfr %r3, %r2
+;   sllg %r4, %r3, 2
 ;   clgfi %r3, 3
-;   jghe label4
-;   sllg %r3, %r3, 2
-;   larl %r1, 14 ; agf %r1, 0(%r1, %r3) ; br %r1 ; jt_entries label2 label1
+;   jghe label4 ; larl %r1, 14 ; agf %r1, 0(%r1, %r4) ; br %r1 ; jt_entries label3 label2 label1
 ; block1:
-;   lhi %r5, 3
+;   lhi %r4, 3
 ;   jg label5
 ; block2:
-;   lhi %r5, 2
+;   lhi %r4, 2
 ;   jg label5
 ; block3:
-;   lhi %r5, 1
+;   lhi %r4, 1
 ;   jg label5
 ; block4:
-;   lhi %r5, 4
+;   lhi %r4, 4
 ;   jg label5
 ; block5:
-;   ar %r2, %r5
+;   ar %r2, %r4
 ;   br %r14
 ;
 ; Disassembled:
 ; block0: ; offset 0x0
 ;   llgfr %r3, %r2
+;   sllg %r4, %r3, 2
 ;   clgfi %r3, 3
 ;   jghe 0x4e
-;   sllg %r3, %r3, 2
 ;   larl %r1, 0x24
-;   agf %r1, 0(%r3, %r1)
+;   agf %r1, 0(%r4, %r1)
 ;   br %r1
 ;   .byte 0x00, 0x00
 ;   .byte 0x00, 0x20
@@ -65,17 +64,17 @@ block5(v5: i32):
 ;   .byte 0x00, 0x00
 ;   .byte 0x00, 0x0c
 ; block1: ; offset 0x30
-;   lhi %r5, 3
+;   lhi %r4, 3
 ;   jg 0x52
 ; block2: ; offset 0x3a
-;   lhi %r5, 2
+;   lhi %r4, 2
 ;   jg 0x52
 ; block3: ; offset 0x44
-;   lhi %r5, 1
+;   lhi %r4, 1
 ;   jg 0x52
 ; block4: ; offset 0x4e
-;   lhi %r5, 4
+;   lhi %r4, 4
 ; block5: ; offset 0x52
-;   ar %r2, %r5
+;   ar %r2, %r4
 ;   br %r14