Introducing variables in jit

zherczeg commented 3 months ago

It turned out whatever register allocation we implement, full data dependency tracking is needed. This patch extends the current data dependency tracking to full tracking. To limit the memory consumption increase, this data is deleted before the code generation, because it is not needed anymore. Various analyses are also moved earlier.

zherczeg commented 2 months ago

This patch is another work which is getting big again. The concept is, it defines a variable for every operation result, and tries to track these variables. It gets the type, constraints (e.g. a callback happens when the variable is alive) and live range of a variable.

It generates the output from the code below:

  (func (export "call1")(param i32)(result i32 i64)(local i32 i64 f32 f64)
      i32.const 10
      call $called

      local.set 4
      local.set 3
      local.set 2
      local.set 1

      ;; Phase 1
      local.get 1
      local.get 2
      i32.wrap_i64
      i32.add

      local.get 3
      i32.trunc_f32_s
      i32.add

      local.get 4
      i32.trunc_f64_s
      i32.add

      ;; Phase 2
      local.get 1
      i64.extend_i32_s
      local.get 2
      i64.add

      local.get 3
      i64.trunc_f32_s
      i64.add

      local.get 4
      i64.trunc_f64_s
      i64.add
  )

[[[[[[[  Function   0  ]]]]]]]
0: (0x575b6710) Opcode: Const32
  Unused
  Result[0]: 0.I32 (O:7) [0-0]
1: (0x575b6490) Opcode: Call
  Param[0]: 0.I32 (O:7)
  Result[0]: 1.I32 (O:8) [1-5]
  Result[1]: 2.I64 (O:9) [1-4]
  Result[2]: 3.F32 (O:11) [1-3]
  Result[3]: 4.F64 (O:12) [1-2]
2: (0x575b6860) Opcode: Move64
  Param[0]: 4.F64 (O:12)
  Result[0]: 5.I64 (O:5) [2-16] CallBack
3: (0x575b66b0) Opcode: Move32
  Param[0]: 3.F32 (O:11)
  Result[0]: 6.I32 (O:4) [3-14]
4: (0x575b6450) Opcode: Move64
  Param[0]: 2.I64 (O:9)
  Result[0]: 7.I64 (O:2) [4-13]
5: (0x575b6340) Opcode: Move32
  Param[0]: 1.I32 (O:8)
  Result[0]: 8.I32 (O:1) [5-12]
6: (0x575b71c0) Opcode: I32WrapI64
  Param[0]: 7.I64 (O:2)
  Result[0]: 9.I32 (O:9) [6-7]
7: (0x575b64c0) Opcode: I32Add
  Param[0]: 8.I32 (O:1)
  Param[1]: 9.I32 (O:9)
  Result[0]: 10.I32 (O:8) [7-9]
8: (0x575b69b0) Opcode: I32TruncF32S
  Param[0]: 6.I32 (O:4)
  Result[0]: 11.I32 (O:9) [8-9]
9: (0x575b6760) Opcode: I32Add
  Param[0]: 10.I32 (O:8)
  Param[1]: 11.I32 (O:9)
  Result[0]: 12.I32 (O:8) [9-11]
10: (0x575b8a80) Opcode: I32TruncF64S
  Param[0]: 5.I64 (O:5)
  Result[0]: 13.I32 (O:9) [10-11]
11: (0x575b65d0) Opcode: I32Add
  Param[0]: 12.I32 (O:8)
  Param[1]: 13.I32 (O:9)
  Result[0]: 14.I32 (O:8) [11-18] CallBack
12: (0x575b8ab0) Opcode: I64ExtendI32S
  Param[0]: 8.I32 (O:1)
  Result[0]: 15.I64 (O:9) [12-13]
13: (0x575b6610) Opcode: I64Add
  Param[0]: 15.I64 (O:9)
  Param[1]: 7.I64 (O:2)
  Result[0]: 16.I64 (O:9) [13-15] CallBack
14: (0x575b8ae0) Opcode: I64TruncF32S
  Param[0]: 6.I32 (O:4)
  Result[0]: 17.I64 (O:11) [14-15]
15: (0x575b6b50) Opcode: I64Add
  Param[0]: 16.I64 (O:9)
  Param[1]: 17.I64 (O:11)
  Result[0]: 18.I64 (O:9) [15-17] CallBack
16: (0x575b8b10) Opcode: I64TruncF64S
  Param[0]: 5.I64 (O:5)
  Result[0]: 19.I64 (O:11) [16-17]
17: (0x575b69e0) Opcode: I64Add
  Param[0]: 18.I64 (O:9)
  Param[1]: 19.I64 (O:11)
  Result[0]: 20.I64 (O:9) [17-18]
18: (0x575b8b40) Opcode: End
  Param[0]: 14.I32 (O:8)
  Param[1]: 20.I64 (O:9)

It is visible that it cannot correctly detect moves:

3: (0x575b66b0) Opcode: Move32
  Param[0]: 3.F32 (O:11)
  Result[0]: 6.I32 (O:4) [3-14]

I am thinking for some time whether these could be tracked, but move "chains" could make this difficult. It would be good to introduce an int/float variant for moves. The other, non-typed operations could be detected with maximum of 1 step in this case.

zherczeg commented 2 months ago

@clover2123 could you review this patch. It is another big patch, thank you for the effort!

The big step is introducing variables. A variable is assigned to the result of every WebAssembly instruction, program parameter, catch tag, etc. These variables are represented by numbers starting from 0. The live range and constraints (e.g. only saved registers can be assigned to this variable) for each variable is tracked. I also tried to reduce memory consumption with simplified structures.

This change is very complex, I am sure there are bugs in there, but they can be fixed later. I think the patch is well rounded now.

clover2123 commented 2 months ago

2: (0x575b6860) Opcode: Move64
  Param[0]: 4.F64 (O:12)
  Result[0]: 5.I64 (O:5) [2-16] CallBack

This is one portion of your example presented above. I have a few questions about this format.

What is CallBack here?
What does [2-16] mean? is this the live range of each variable (result variable)? If so, [2-16] represents that this variable is live from 2nd instruction to 16th instruction, right?
Lastly, what is (O:12) and (O:5)?

zherczeg commented 2 months ago

Your guesses were correct.

Callback is a constraint, it means during the live range of the variable at least one instruction calls a helper function, so scratch register cannot be assigned to the variable.
[2-16] is the live range, so the variable must be exists between the 2nd and 16st instruction, inclusive.
O means offset (I means immediate). O:16 represents that the original location of the variable on the stack has offset 16. When a register will be assigned to the variable, this stack area is not used.

zherczeg commented 1 month ago

No problem. Thank you!

Samsung / walrus

Introducing variables in jit #236