[WebAssembly] Support constant offsets on loads and stores

[dschuff]

Summary

Includes the syntax for the immediate offset field of load and store instructions, but doesn't pattern-match anything other than 0 yet.

[dschuff]

lib/Target/WebAssembly/WebAssemblyInstrMemory.td

106

writing the offset operand as 'imm:$off' turns out to be critical here to getting an immediate in the output. If you say just $off or I32:$off you still get a pattern match but it generates an i32.const and uses that instead of putting it directly as an immediate in the store instruction. (The same applies if you use this kind of pattern to match a load, but if you put it directly in the definition for the load as I did here, then it doesn't matter if you use the imm: prefix or not). I'm not sure why that is.

[sunfish]

This looks like a good direction. I like how it uses def : Pat instead of needing custom code in WebAssemblyISelDAGToDAG.cpp :-).

One tricky thing though is that wasm's constant offsets are unsigned, so we can't support negative values. I think we'll need to add a predicate on the pattern-match which checks this. I think it's fine if you'd prefer to just add a FIXME for this for now and we can address it later though. Or if you want to simplify things, we could also defer pattern-matching for constant offsets altogether for now, since framepointer lowering doesn't actually require it.

lib/Target/WebAssembly/WebAssemblyInstrMemory.td

106

If you say I32:$off, it refers to the I32 register class (defined in lib/Target/WebAssembly/WebAssemblyRegisterInfo.td), which effectively says that you need the value in a register of that class, which forces the instruction selector to use an i32.const to get the value into a register. I don't know the rules if you just say $off by itself. I'd suggest using the imm: prefix to avoid trouble :-).

[jfb]

In D15197#301756, @sunfish wrote:

This looks like a good direction. I like how it uses def : Pat instead of needing custom code in WebAssemblyISelDAGToDAG.cpp :-).

Agreed.

One tricky thing though is that wasm's constant offsets are unsigned, so we can't support negative values. I think we'll need to add a predicate on the pattern-match which checks this.

We'll also want to optimize things so that LLVM knows to generate positive offsets instead of negative ones (post-increment as much as possible). Do you know if there's a knob for that? It's just an optimization so maybe just mention it in the list of work to do in the README?

and we can address it later though.

I see what you did there, "address". :o)

[sunfish]

We'll also want to optimize things so that LLVM knows to generate positive offsets instead of negative ones (post-increment as much as possible). Do you know if there's a knob for that? It's just an optimization so maybe just mention it in the list of work to do in the README?

The main hook we can use is WebAssemblyTargetLowering::isLegalAddressingMode, and there's a TODO for it in WebAssemblyInstrMemory.md.

[dschuff]

• Include all loads and stores
• rebase

[dschuff]

Updated to include all loads and stores, and remove the pattern match for now.
I couldn't figure out a way to constrain the match for unsigned immediates with just tablegen yet.

[sunfish]

Sounds good to me.

lib/Target/WebAssembly/WebAssemblyInstrMemory.td

 
 // WebAssembly has i8/i16/i32/i64/f32/f64 memory types, but doesn't have i8/i16
 // local types. These memory-only types instead zero- or sign-extend into local
 // types when loading, and truncate when storing.
 
 let Defs = [ARGUMENTS] in {
 
 // Basic load.
-def LOAD_I32 : I<(outs I32:$dst), (ins I32:$addr),
-                 [(set I32:$dst, (load I32:$addr))],
-                 "i32.load\t$dst, $addr">;
+def LOAD_I32 : I<(outs I32:$dst), (ins I32:$off, I32:$addr),
+                 [(set I32:$dst, (i32 (load (add I32:$addr, (i32 imm:$off)))))],
+                 "i32.load\t$dst, $off($addr)">;
 def LOAD_I64 : I<(outs I64:$dst), (ins I32:$addr),
                  [(set I64:$dst, (load I32:$addr))],
                  "i64.load\t$dst, $addr">;
 def LOAD_F32 : I<(outs F32:$dst), (ins I32:$addr),
                  [(set F32:$dst, (load I32:$addr))],
                  "f32.load\t$dst, $addr">;
 def LOAD_F64 : I<(outs F64:$dst), (ins I32:$addr),
                  [(set F64:$dst, (load I32:$addr))],
def LOAD32_S_I64 : I<(outs I64:$dst), (ins I32:$addr),
                      [(set I64:$dst, (sextloadi32 I32:$addr))],
                      "i64.load32_s\t$dst, $addr">;
 def LOAD32_U_I64 : I<(outs I64:$dst), (ins I32:$addr),
                      [(set I64:$dst, (zextloadi32 I32:$addr))],
                      "i64.load32_u\t$dst, $addr">;
 
 } // Defs = [ARGUMENTS]
 
+// Select loads with no constant offset.
+def : Pat<(i32 (load I32:$addr)), (LOAD_I32 0, $addr)>;
+
 // "Don't care" extending load become zero-extending load.
 def : Pat<(i32 (extloadi8 I32:$addr)),  (LOAD8_U_I32 $addr)>;
 def : Pat<(i32 (extloadi16 I32:$addr)), (LOAD16_U_I32 $addr)>;
 def : Pat<(i64 (extloadi8 I32:$addr)),  (LOAD8_U_I64 $addr)>;
 def : Pat<(i64 (extloadi16 I32:$addr)), (LOAD16_U_I64 $addr)>;
 def : Pat<(i64 (extloadi32 I32:$addr)), (LOAD32_U_I64 $addr)>;
 
 let Defs = [ARGUMENTS] in {
 
 // Basic store.
 // Note that we split the patterns out of the instruction definitions because
 // WebAssembly's stores return their operand value, and tablegen doesn't like
 // instruction definition patterns that don't reference all of the output
 // operands.
 // Note: WebAssembly inverts SelectionDAG's usual operand order.
-def STORE_I32  : I<(outs I32:$dst), (ins I32:$addr, I32:$val), [],
-                   "i32.store\t$dst, $addr, $val">;
+def STORE_I32  : I<(outs I32:$dst), (ins I32:$off, I32:$addr, I32:$val), [],
+                   "i32.store\t$dst, $off($addr), $val">;
 def STORE_I64  : I<(outs I64:$dst), (ins I32:$addr, I64:$val), [],
                    "i64.store\t$dst, $addr, $val">;
 def STORE_F32  : I<(outs F32:$dst), (ins I32:$addr, F32:$val), [],
                    "f32.store\t$dst, $addr, $val">;
 def STORE_F64  : I<(outs F64:$dst), (ins I32:$addr, F64:$val), [],
                    "f64.store\t$dst, $addr, $val">;
 
 } // Defs = [ARGUMENTS]
 
-def : Pat<(store I32:$val, I32:$addr), (STORE_I32 I32:$addr, I32:$val)>;
+def : Pat<(store I32:$val, I32:$addr), (STORE_I32 0, I32:$addr, I32:$val)>;
+def : Pat<(store I32:$val, (add I32:$addr, (i32 imm:$off))),
+          (STORE_I32 imm:$off, I32:$addr, I32:$val)>;
+
+
 def : Pat<(store I64:$val, I32:$addr), (STORE_I64 I32:$addr, I64:$val)>;
 def : Pat<(store F32:$val, I32:$addr), (STORE_F32 I32:$addr, F32:$val)>;
 def : Pat<(store F64:$val, I32:$addr), (STORE_F64 I32:$addr, F64:$val)>;
 
 let Defs = [ARGUMENTS] in {
 
 // Truncating store.
 def STORE8_I32  : I<(outs I32:$dst), (ins I32:$addr, I32:$val), [],

lib/Target/WebAssembly/WebAssemblyStoreResults.cpp

for (auto &MI : MBB)
       case WebAssembly::STORE8_I64:
       case WebAssembly::STORE16_I64:
       case WebAssembly::STORE32_I64:
       case WebAssembly::STORE_F32:
       case WebAssembly::STORE_F64:
       case WebAssembly::STORE_I32:
       case WebAssembly::STORE_I64:
         unsigned ToReg = MI.getOperand(0).getReg();
-        unsigned FromReg = MI.getOperand(2).getReg();
+        unsigned FromReg = MI.getOperand(3).getReg();
         for (auto I = MRI.use_begin(FromReg), E = MRI.use_end(); I != E;) {
           MachineOperand &O = *I++;
           MachineInstr *Where = O.getParent();
           if (Where->getOpcode() == TargetOpcode::PHI)
             Where = Where->getOperand(&O - &Where->getOperand(0) + 1)
                         .getMBB()
                         ->getFirstTerminator();
           if (&MI == Where || !MDT.dominates(&MI, Where))

test/CodeGen/WebAssembly/cfg-stackify.ll

 entry:
   store volatile i32 0, i32* %p
   ret i32 0
 }
 
 ; CHECK-LABEL: minimal_loop:
 ; CHECK-NOT: br
 ; CHECK: BB7_1:
-; CHECK: i32.store $discard=, $0, $pop{{[0-9]+}}{{$}}
+; CHECK: i32.store $discard=, 0($0), $pop{{[0-9]+}}{{$}}
 ; CHECK: br BB7_1{{$}}
 ; CHECK: BB7_2:
 define i32 @minimal_loop(i32* %p) {
 entry:
   store volatile i32 0, i32* %p
   br label %loop
 loop:
   store volatile i32 1, i32* %p

test/CodeGen/WebAssembly/global.ll

 ; RUN: llc < %s -asm-verbose=false | FileCheck %s
 
 ; Test that globals assemble as expected.
 
 target datalayout = "e-p:32:32-i64:64-n32:64-S128"
 target triple = "wasm32-unknown-unknown"
 
 ; CHECK-NOT: llvm.used
 ; CHECK-NOT: llvm.metadata
 @llvm.used = appending global [1 x i32*] [i32* @g], section "llvm.metadata"
 
 ; CHECK: foo:
 ; CHECK: i32.const $push0=, answer{{$}}
-; CHECK-NEXT: i32.load $push1=, $pop0{{$}}
+; CHECK-NEXT: i32.load $push1=, 0($pop0){{$}}
 ; CHECK-NEXT: return $pop1{{$}}
 define i32 @foo() {
   %a = load i32, i32* @answer
   ret i32 %a
 }
 
 ; CHECK-LABEL: call_memcpy:
 ; CHECK-NEXT: .param          i32, i32, i32{{$}}

test/CodeGen/WebAssembly/load.ll

 ; RUN: llc < %s -asm-verbose=false | FileCheck %s
 
 ; Test that basic loads are assembled properly.
 
 target datalayout = "e-p:32:32-i64:64-n32:64-S128"
 target triple = "wasm32-unknown-unknown"
 
 ; CHECK-LABEL: ldi32:
 ; CHECK-NEXT: .param i32{{$}}
 ; CHECK-NEXT: .result i32{{$}}
-; CHECK-NEXT: i32.load $push[[NUM:[0-9]+]]=, $0{{$}}
+; CHECK-NEXT: i32.load $push[[NUM:[0-9]+]]=, 0($0){{$}}
 ; CHECK-NEXT: return $pop[[NUM]]{{$}}
 define i32 @ldi32(i32 *%p) {
   %v = load i32, i32* %p
   ret i32 %v
 }
 
 ; CHECK-LABEL: ldi64:
 ; CHECK-NEXT: .param i32{{$}}

 ; CHECK-NEXT: .param i32{{$}}
 ; CHECK-NEXT: .result f64{{$}}
 ; CHECK-NEXT: f64.load $push[[NUM:[0-9]+]]=, $0{{$}}
 ; CHECK-NEXT: return $pop[[NUM]]{{$}}
 define double @ldf64(double *%p) {
   %v = load double, double* %p
   ret double %v
 }
+
+; Check that a constant offset is folded into a load
+; CHECK-LABEL: ldoff:
+; CHECK: i32.load $push0=, 12($0)
+define i32 @ldoff(i32 *%p) {
+  %addr = getelementptr i32, i32* %p, i32 3
+  %v = load i32, i32* %addr
+  ret i32 %v
+}
+
+; Check that a variable offset is not folded
+; CHECK-LABEL: ldoff_var
+; CHECK: i32.load $push{{[0-9]+}}=, 0($pop{{[0-9]}})
+define i32 @ldoff_var(i32 *%p, i32 %o) {
+  %addr = getelementptr i32, i32* %p, i32 %o
+  %v = load i32, i32* %addr
+  ret i32 %v
+}
 No newline at end of file

test/CodeGen/WebAssembly/store-results.ll

 ; RUN: llc < %s -asm-verbose=false | FileCheck %s
 
 ; Test that the wasm-store-results pass makes users of stored values use the
 ; result of store expressions to reduce get_local/set_local traffic.
 
 target datalayout = "e-p:32:32-i64:64-n32:64-S128"
 target triple = "wasm32-unknown-unknown"
 
 ; CHECK-LABEL: single_block:
 ; CHECK-NOT: .local
 ; CHECK: i32.const $push{{[0-9]+}}=, 0
-; CHECK: i32.store $push[[STORE:[0-9]+]]=, $0, $pop{{[0-9]+}}
+; CHECK: i32.store $push[[STORE:[0-9]+]]=, 0($0), $pop{{[0-9]+}}
 ; CHECK: return $pop[[STORE]]{{$}}
 define i32 @single_block(i32* %p) {
 entry:
   store i32 0, i32* %p
   ret i32 0
 }

test/CodeGen/WebAssembly/store.ll

 ; RUN: llc < %s -asm-verbose=false | FileCheck %s
 
 ; Test that basic stores are assembled properly.
 
 target datalayout = "e-p:32:32-i64:64-n32:64-S128"
 target triple = "wasm32-unknown-unknown"
 
 ; CHECK-LABEL: sti32:
 ; CHECK-NEXT: .param i32, i32{{$}}
-; CHECK-NEXT: i32.store $discard=, $0, $1{{$}}
+; CHECK-NEXT: i32.store $discard=, 0($0), $1{{$}}
 ; CHECK-NEXT: return{{$}}
 define void @sti32(i32 *%p, i32 %v) {
   store i32 %v, i32* %p
   ret void
 }
 
 ; CHECK-LABEL: sti64:
 ; CHECK-NEXT: .param i32, i64{{$}}

 ; CHECK-LABEL: stf64:
 ; CHECK-NEXT: .param i32, f64{{$}}
 ; CHECK-NEXT: f64.store $discard=, $0, $1{{$}}
 ; CHECK-NEXT: return{{$}}
 define void @stf64(double *%p, double %v) {
   store double %v, double* %p
   ret void
 }
+
+; Check that a constant offset is folded into a store
+; CHECK-LABEL: stoff:
+; CHECK: i32.store $discard=, 12($0), $1
+define void @stoff(i32 *%p, i32 %v) {
+  %addr = getelementptr i32, i32* %p, i32 3
+  store i32 %v, i32* %addr
+  ret void
+}