[WebAssembly] multivalue stackify fix

[samparker]

Summary

Suggested fix for bugs: https://github.com/llvm/llvm-project/issues/58297, https://github.com/llvm/llvm-project/issues/55136

Add a check that we're not attempting to move a multivalue instruction past any of it's users.

[sbc100]

llvm/test/CodeGen/WebAssembly/multivalue-dont-move-def-bug.ll

4 ↗

(On Diff #474710)

Did you mean to use the wasi target here? We normally use unknown-unknown for testing generic stuff

[samparker]

llvm/test/CodeGen/WebAssembly/multivalue-dont-move-def-bug.ll

4 ↗

(On Diff #474710)

Okay, fair enough, I just copied it from the github issue... I'll make the change.

[samparker]

Updated target triple.

[tlively]

llvm/lib/Target/WebAssembly/WebAssemblyRegStackify.cpp

339–340

This doesn't sound quite right. As a counterexample, consider

a, b = foo
bar a
baz b

Here we have a subsequent def (of b) used by a different instruction (baz), but we can still stackify by moving baz before bar.

It would be good to reduce the test case to figure out more precisely what the problem is and come up with a more precise solution. Maybe the problem is that baz and bar (or rather their equivalents in the test) cannot be reordered?

[tlively]

I don't know if you've seen it, but we have a multivalue-stackify.py script that tries to exhaustively enumerate multivalue sequences up to a certain size then filter out the uninteresting ones. The output is checked in as the multivalue-stackify.ll test. It may be worth playing around with that script so that it generates programs that exhibit this problem.

[samparker]

llvm/lib/Target/WebAssembly/WebAssemblyRegStackify.cpp

339–340

Maybe my comment doesn't make complete sense... But just to clarify, we move the def, not the user, right? And we only attempt to move considering the first def?

So I think your example is the pattern that the existing code will handle just fine: we won't attempt to move anything?

IIUC, the case that currently isn't handled is this:

a, b = foo
baz b
bar a

The existing code only looks at bar and will attempt to sink foo past baz, producing broken code. I'll convert to the test to a MIR which should demonstrate that this is precisely what's going on.

If I'm misunderstanding, please shout!

[samparker]

Using mir test and updated comment.

[samparker]

I don't know if you've seen it, but we have a multivalue-stackify.py script that tries to exhaustively enumerate multivalue sequences up to a certain size then filter out the uninteresting ones.

Cool! My python isn't great tbh... but looking through the generated test, I would have thought that f141 may have triggered this bug:

%t0 = call {i32, i32} @op_0_to_2()
%t1 = extractvalue {i32, i32} %t0, 1
call void @op_1_to_0(i32 %t1)
%t2 = extractvalue {i32, i32} %t0, 0
call void @op_1_to_0(i32 %t2)
ret void

%0:i32, %1:i32 = CALL @op_0_to_2, implicit-def dead $arguments, implicit $sp32, implicit $sp64, implicit-def dead $arguments, implicit $sp32, implicit $sp64
CALL @op_1_to_0, %1, implicit-def dead $arguments, implicit $sp32, implicit $sp64, implicit-def dead $arguments, implicit $sp32, implicit $sp64
CALL @op_1_to_0, %0, implicit-def dead $arguments, implicit $sp32, implicit $sp64, implicit-def dead $arguments, implicit $sp32, implicit $sp64
RETURN implicit-def dead $arguments

Is it the fact that the users are calls and this prevents a move from being attempted..?

[tlively]

In D137824#3924406, @samparker wrote:

I don't know if you've seen it, but we have a multivalue-stackify.py script that tries to exhaustively enumerate multivalue sequences up to a certain size then filter out the uninteresting ones.

Cool! My python isn't great tbh... but looking through the generated test, I would have thought that f141 may have triggered this bug:

%t0 = call {i32, i32} @op_0_to_2()
%t1 = extractvalue {i32, i32} %t0, 1
call void @op_1_to_0(i32 %t1)
%t2 = extractvalue {i32, i32} %t0, 0
call void @op_1_to_0(i32 %t2)
ret void

%0:i32, %1:i32 = CALL @op_0_to_2, implicit-def dead $arguments, implicit $sp32, implicit $sp64, implicit-def dead $arguments, implicit $sp32, implicit $sp64
CALL @op_1_to_0, %1, implicit-def dead $arguments, implicit $sp32, implicit $sp64, implicit-def dead $arguments, implicit $sp32, implicit $sp64
CALL @op_1_to_0, %0, implicit-def dead $arguments, implicit $sp32, implicit $sp64, implicit-def dead $arguments, implicit $sp32, implicit $sp64
RETURN implicit-def dead $arguments

Is it the fact that the users are calls and this prevents a move from being attempted..?

Yeah, I suspect you're right that the function calls are inhibiting the moves. It would be nice to find a way around that, but looking at the code it looks like it will refuse to reorder a pair of calls no matter what attributes the callee has. I suppose we could add a debug-only flag to change that behavior, but it's probably not worth it. Maybe the script could emit instructions other than function calls instead...

Anyway, mostly LGTM with the exception that it would be good to make the test even easier to read.

llvm/lib/Target/WebAssembly/WebAssemblyRegStackify.cpp

339–340

Maybe my comment doesn't make complete sense... But just to clarify, we move the def, not the user, right? And we only attempt to move considering the first def?

Ah, you're right. I had forgotten that we're moving defs here.

llvm/test/CodeGen/WebAssembly/multivalue-dont-move-def-past-use.mir

10

Is it possible to come up with a reproducer with a single basic block? Either way, it would be helpful to add comments highlighting the important pieces of the test. There's enough going on here that it's difficult to figure out which parts are important just by looking at it.

[samparker]

llvm/test/CodeGen/WebAssembly/multivalue-dont-move-def-past-use.mir

10

Yeah, good point. I'll take the reproducer from here since trying to simplify fp128 lowering is too much work!

[samparker]

Using smaller reproducer.

[tlively]

LGTM, thanks!

llvm/lib/Target/WebAssembly/WebAssemblyRegStackify.cpp

static bool isSafeToMove(const MachineOperand *Def, const MachineOperand *Use,
   // same instruction as subsequent defs.
   if (Def != DefI->defs().begin())
     return false;
 
   // If any subsequent def is used prior to the current value by the same
   // instruction in which the current value is used, we cannot
   // stackify. Stackifying in this case would require that def moving below the
   // current def in the stack, which cannot be achieved, even with locals.
+  // Also ensure we don't sink the def past any other prior uses.
   for (const auto &SubsequentDef : drop_begin(DefI->defs())) {
-    for (const auto &PriorUse : UseI->uses()) {
+    auto I = std::next(MachineBasicBlock::const_iterator(DefI));
+    auto E = std::next(MachineBasicBlock::const_iterator(UseI));
+    for (; I != E; ++I) {
+      for (const auto &PriorUse : I->uses()) {
         if (&PriorUse == Use)
           break;
         if (PriorUse.isReg() && SubsequentDef.getReg() == PriorUse.getReg())
           return false;
       }
     }
+  }
 
   // If moving is a semantic nop, it is always allowed
   const MachineBasicBlock *MBB = DefI->getParent();
   auto NextI = std::next(MachineBasicBlock::const_iterator(DefI));
   for (auto E = MBB->end(); NextI != E && NextI->isDebugInstr(); ++NextI)
     ;
   if (NextI == Insert)
     return true;

llvm/test/CodeGen/WebAssembly/multivalue-dont-move-def-past-use.mir

+# NOTE: Assertions have been autogenerated by utils/update_mir_test_checks.py
+# RUN: llc -mtriple=wasm32-unknown-unknown -mattr=+multivalue -run-pass=wasm-reg-stackify -verify-machineinstrs %s -o - | FileCheck %s
+--- |
+  target datalayout = "e-m:e-p:32:32-p10:8:8-p20:8:8-i64:64-n32:64-S128-ni:1:10:20"
+  target triple = "wasm32-unknown-unknown"
+
+  @d = hidden local_unnamed_addr global double 0.000000e+00, align 8
+  @c = hidden local_unnamed_addr global i32 0, align 4
+
+  define hidden fp128 @e() local_unnamed_addr #0 {
+    %1 = load double, ptr @d, align 8
+    %2 = fcmp une double %1, 0.000000e+00
+    br i1 %2, label %9, label %3
+
+  3:                                                ; preds = %0
+    %4 = load i32, ptr @c, align 4
+    %5 = icmp eq i32 %4, 0
+    %6 = fptosi double %1 to i32
+    %7 = sitofp i32 %6 to fp128
+    %8 = select i1 %5, fp128 0xL00000000000000000000000000000000, fp128 %7
+    br label %9
+
+  9:                                                ; preds = %3, %0
+    %10 = phi fp128 [ %8, %3 ], [ 0xL00000000000000000000000000000000, %0 ]
+    ret fp128 %10
+  }
+
+  attributes #0 = { "target-features"="+multivalue,+mutable-globals,+sign-ext," }
+
+  !llvm.module.flags = !{!0, !1, !2}
+
+  !0 = !{i32 1, !"wasm-feature-multivalue", i32 43}
+  !1 = !{i32 1, !"wasm-feature-mutable-globals", i32 43}
+  !2 = !{i32 1, !"wasm-feature-sign-ext", i32 43}
+
+...
+---
+name:            e
+alignment:       1
+exposesReturnsTwice: false
+legalized:       false
+regBankSelected: false
+selected:        false
+failedISel:      false
+tracksRegLiveness: true
+hasWinCFI:       false
+callsEHReturn:   false
+callsUnwindInit: false
+hasEHCatchret:   false
+hasEHScopes:     false
+hasEHFunclets:   false
+failsVerification: false
+tracksDebugUserValues: false
+registers:
+  - { id: 0, class: f64, preferred-register: '' }
+  - { id: 1, class: i64, preferred-register: '' }
+  - { id: 2, class: i64, preferred-register: '' }
+  - { id: 3, class: i64, preferred-register: '' }
+  - { id: 4, class: i64, preferred-register: '' }
+  - { id: 5, class: i64, preferred-register: '' }
+  - { id: 6, class: i64, preferred-register: '' }
+  - { id: 7, class: i32, preferred-register: '' }
+  - { id: 8, class: f64, preferred-register: '' }
+  - { id: 9, class: i32, preferred-register: '' }
+  - { id: 10, class: i32, preferred-register: '' }
+  - { id: 11, class: i32, preferred-register: '' }
+  - { id: 12, class: i32, preferred-register: '' }
+  - { id: 13, class: i64, preferred-register: '' }
+  - { id: 14, class: i64, preferred-register: '' }
+  - { id: 15, class: i64, preferred-register: '' }
+  - { id: 16, class: f64, preferred-register: '' }
+  - { id: 17, class: f64, preferred-register: '' }
+  - { id: 18, class: i32, preferred-register: '' }
+  - { id: 19, class: i32, preferred-register: '' }
+  - { id: 20, class: i32, preferred-register: '' }
+  - { id: 21, class: i32, preferred-register: '' }
+  - { id: 22, class: i32, preferred-register: '' }
+  - { id: 23, class: i64, preferred-register: '' }
+  - { id: 24, class: i64, preferred-register: '' }
+liveins:
+  - { reg: '$arguments', virtual-reg: '' }
+frameInfo:
+  isFrameAddressTaken: false
+  isReturnAddressTaken: false
+  hasStackMap:     false
+  hasPatchPoint:   false
+  stackSize:       0
+  offsetAdjustment: 0
+  maxAlignment:    1
+  adjustsStack:    false
+  hasCalls:        true
+  stackProtector:  ''
+  functionContext: ''
+  maxCallFrameSize: 0
+  cvBytesOfCalleeSavedRegisters: 0
+  hasOpaqueSPAdjustment: false
+  hasVAStart:      false
+  hasMustTailInVarArgFunc: false
+  hasTailCall:     false
+  localFrameSize:  0
+  savePoint:       ''
+  restorePoint:    ''
+fixedStack:      []
+stack:           []
+callSites:       []
+debugValueSubstitutions: []
+constants:       []
+machineFunctionInfo:
+  params:          [  ]
+  results:         [ i64, i64 ]
+  isCFGStackified: false
+  wasmEHFuncInfo:  {}
+body:             |
+  ; CHECK-LABEL: name: e
+  ; CHECK: bb.0 (%ir-block.0):
+  ; CHECK-NEXT:   successors: %bb.5(0x50000000), %bb.1(0x30000000)
+  ; CHECK-NEXT:   liveins: $arguments, $value_stack
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT:   [[CONST_I64_:%[0-9]+]]:i64 = CONST_I64 0, implicit-def dead $arguments
+  ; CHECK-NEXT:   [[CONST_I64_1:%[0-9]+]]:i64 = CONST_I64 0, implicit-def dead $arguments
+  ; CHECK-NEXT:   [[CONST_I32_:%[0-9]+]]:i32 = CONST_I32 0, implicit-def dead $arguments, implicit-def $value_stack, implicit $value_stack
+  ; CHECK-NEXT:   [[LOAD_F64_A32_:%[0-9]+]]:f64 = LOAD_F64_A32 3, @d, [[CONST_I32_]], implicit-def dead $arguments, implicit-def $value_stack, implicit $value_stack :: (dereferenceable load (s64) from @d)
+  ; CHECK-NEXT:   [[TEE_F64_:%[0-9]+]]:f64, [[TEE_F64_1:%[0-9]+]]:f64 = TEE_F64 [[LOAD_F64_A32_]], implicit-def $arguments, implicit-def $value_stack, implicit $value_stack
+  ; CHECK-NEXT:   [[CONST_F64_:%[0-9]+]]:f64 = CONST_F64 double 0.000000e+00, implicit-def dead $arguments, implicit-def $value_stack, implicit $value_stack
+  ; CHECK-NEXT:   [[NE_F64_:%[0-9]+]]:i32 = NE_F64 [[TEE_F64_]], [[CONST_F64_]], implicit-def dead $arguments, implicit-def $value_stack, implicit $value_stack
+  ; CHECK-NEXT:   BR_IF %bb.5, [[NE_F64_]], implicit-def $arguments, implicit-def $value_stack, implicit $value_stack
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT: bb.1 (%ir-block.3):
+  ; CHECK-NEXT:   successors: %bb.3(0x40000000), %bb.2(0x40000000)
+  ; CHECK-NEXT:   liveins: $value_stack
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT:   [[CONST_I32_1:%[0-9]+]]:i32 = CONST_I32 0, implicit-def dead $arguments, implicit-def $value_stack, implicit $value_stack
+  ; CHECK-NEXT:   [[LOAD_I32_A32_:%[0-9]+]]:i32 = LOAD_I32_A32 2, @c, [[CONST_I32_1]], implicit-def dead $arguments, implicit-def $value_stack, implicit $value_stack :: (dereferenceable load (s32) from @c)
+  ; CHECK-NEXT:   [[ABS_F64_:%[0-9]+]]:f64 = ABS_F64 [[TEE_F64_1]], implicit-def dead $arguments, implicit-def $value_stack, implicit $value_stack
+  ; CHECK-NEXT:   [[CONST_F64_1:%[0-9]+]]:f64 = CONST_F64 double 0x41E0000000000000, implicit-def dead $arguments, implicit-def $value_stack, implicit $value_stack
+  ; CHECK-NEXT:   [[LT_F64_:%[0-9]+]]:i32 = LT_F64 [[ABS_F64_]], [[CONST_F64_1]], implicit-def dead $arguments, implicit-def $value_stack, implicit $value_stack
+  ; CHECK-NEXT:   [[EQZ_I32_:%[0-9]+]]:i32 = EQZ_I32 [[LT_F64_]], implicit-def dead $arguments, implicit-def $value_stack, implicit $value_stack
+  ; CHECK-NEXT:   BR_IF %bb.3, [[EQZ_I32_]], implicit-def dead $arguments, implicit-def $value_stack, implicit $value_stack
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT: bb.2 (%ir-block.3):
+  ; CHECK-NEXT:   successors: %bb.4(0x80000000)
+  ; CHECK-NEXT:   liveins: $value_stack
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT:   [[I32_TRUNC_S_F64_:%[0-9]+]]:i32 = I32_TRUNC_S_F64 [[TEE_F64_1]], implicit-def dead $arguments
+  ; CHECK-NEXT:   BR %bb.4, implicit-def $arguments
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT: bb.3 (%ir-block.3):
+  ; CHECK-NEXT:   successors: %bb.4(0x80000000)
+  ; CHECK-NEXT:   liveins: $value_stack
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT:   [[CONST_I32_2:%[0-9]+]]:i32 = CONST_I32 -2147483648, implicit-def dead $arguments
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT: bb.4 (%ir-block.3):
+  ; CHECK-NEXT:   successors: %bb.5(0x80000000)
+  ; CHECK-NEXT:   liveins: $value_stack
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT:   [[CALL:%[0-9]+]]:i64, [[CALL1:%[0-9]+]]:i64 = CALL &__floatsitf, [[CONST_I32_2]], implicit-def dead $arguments, implicit $sp32, implicit $sp64, implicit-def dead $arguments, implicit $sp32, implicit $sp64
+  ; CHECK-NEXT:   [[CONST_I64_2:%[0-9]+]]:i64 = CONST_I64 0, implicit-def dead $arguments, implicit-def $value_stack, implicit $value_stack
+  ; CHECK-NEXT:   [[SELECT_I64_:%[0-9]+]]:i64 = SELECT_I64 [[CALL1]], [[CONST_I64_2]], [[LOAD_I32_A32_]], implicit-def dead $arguments, implicit-def $value_stack, implicit $value_stack
+  ; CHECK-NEXT:   [[CONST_I64_2:%[0-9]+]]:i64 = CONST_I64 0, implicit-def dead $arguments, implicit-def $value_stack, implicit $value_stack
+  ; CHECK-NEXT:   [[SELECT_I64_1:%[0-9]+]]:i64 = SELECT_I64 [[CALL]], [[CONST_I64_2]], [[LOAD_I32_A32_]], implicit-def dead $arguments, implicit-def $value_stack, implicit $value_stack
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT: bb.5 (%ir-block.9):
+  ; CHECK-NEXT:   liveins: $value_stack
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT:   RETURN [[SELECT_I64_1]], [[SELECT_I64_]], implicit-def dead $arguments
+  bb.0 (%ir-block.0):
+    successors: %bb.5(0x50000000), %bb.1(0x30000000)
+    liveins: $arguments
+
+    %7:i32 = CONST_I32 0, implicit-def dead $arguments
+    %0:f64 = LOAD_F64_A32 3, @d, %7, implicit-def dead $arguments :: (dereferenceable load (s64) from @d)
+    %8:f64 = CONST_F64 double 0.000000e+00, implicit-def dead $arguments
+    %9:i32 = NE_F64 %0, %8, implicit-def dead $arguments
+    %23:i64 = CONST_I64 0, implicit-def dead $arguments
+    %24:i64 = CONST_I64 0, implicit-def dead $arguments
+    BR_IF %bb.5, %9, implicit-def $arguments
+
+  bb.1 (%ir-block.3):
+    successors: %bb.3(0x40000000), %bb.2(0x40000000)
+
+    %11:i32 = LOAD_I32_A32 2, @c, %7, implicit-def dead $arguments :: (dereferenceable load (s32) from @c)
+    %16:f64 = ABS_F64 %0, implicit-def dead $arguments
+    %17:f64 = CONST_F64 double 0x41E0000000000000, implicit-def dead $arguments
+    %18:i32 = LT_F64 %16, %17, implicit-def dead $arguments
+    %19:i32 = EQZ_I32 %18, implicit-def dead $arguments
+    BR_IF %bb.3, %19, implicit-def dead $arguments
+
+  bb.2 (%ir-block.3):
+    successors: %bb.4(0x80000000)
+
+    %22:i32 = I32_TRUNC_S_F64 %0, implicit-def dead $arguments
+    BR %bb.4, implicit-def $arguments
+
+  bb.3 (%ir-block.3):
+    successors: %bb.4(0x80000000)
+
+    %22:i32 = CONST_I32 -2147483648, implicit-def dead $arguments
+
+  bb.4 (%ir-block.3):
+    successors: %bb.5(0x80000000)
+
+    %13:i64 = CONST_I64 0, implicit-def dead $arguments
+    %14:i64, %15:i64 = CALL &__floatsitf, %22, implicit-def dead $arguments, implicit $sp32, implicit $sp64, implicit-def dead $arguments, implicit $sp32, implicit $sp64
+    %24:i64 = SELECT_I64 %15, %13, %11, implicit-def dead $arguments
+    %23:i64 = SELECT_I64 %14, %13, %11, implicit-def dead $arguments
+
+  bb.5 (%ir-block.9):
+    RETURN %23, %24, implicit-def dead $arguments
+
+...