ZJIT: Implement dead store elimination

[jacob-shops]

Right now, the following Ruby code generates the following HIR.

class C
  def initialize
    @a = 1
    @b = 2
    @c = 3
  end
end

C.new

fn initialize@<compiled>:4:
bb1():
  EntryPoint interpreter
  v1:BasicObject = LoadSelf
  Jump bb3(v1)
bb2():
  EntryPoint JIT(0)
  v4:BasicObject = LoadArg :self@0
  Jump bb3(v4)
bb3(v6:BasicObject):
  v10:Fixnum[1] = Const Value(1)
  PatchPoint SingleRactorMode
  v35:HeapBasicObject = GuardType v6, HeapBasicObject
  v36:CShape = LoadField v35, :_shape_id@0x1000
  v37:CShape[0x1001] = GuardBitEquals v36, CShape(0x1001)
  StoreField v35, :@a@0x1002, v10
  WriteBarrier v35, v10
  v40:CShape[0x1003] = Const CShape(0x1003)
  StoreField v35, :_shape_id@0x1000, v40
  v14:HeapBasicObject = RefineType v6, HeapBasicObject
  v17:Fixnum[2] = Const Value(2)
  PatchPoint SingleRactorMode
  StoreField v14, :@b@0x1004, v17
  WriteBarrier v14, v17
  v47:CShape[0x1005] = Const CShape(0x1005)
  StoreField v14, :_shape_id@0x1000, v47
  v21:HeapBasicObject = RefineType v14, HeapBasicObject
  v24:Fixnum[3] = Const Value(3)
  PatchPoint SingleRactorMode
  StoreField v21, :@c@0x1006, v24
  WriteBarrier v21, v24
  v54:CShape[0x1007] = Const CShape(0x1007)
  StoreField v21, :_shape_id@0x1000, v54
  CheckInterrupts
  Return v24

We would like it to look roughly like the following instead

fn initialize@<compiled>:4:
bb1():
  EntryPoint interpreter
  v1:BasicObject = LoadSelf
  Jump bb3(v1)
bb2():
  EntryPoint JIT(0)
  v4:BasicObject = LoadArg :self@0
  Jump bb3(v4)
bb3(v6:BasicObject):
  v10:Fixnum[1] = Const Value(1)
  PatchPoint SingleRactorMode
  v35:HeapBasicObject = GuardType v6, HeapBasicObject
  v36:CShape = LoadField v35, :_shape_id@0x1000
  v37:CShape[0x1001] = GuardBitEquals v36, CShape(0x1001)
  StoreField v35, :@a@0x1002, v10
  WriteBarrier v35, v10
  v40:CShape[0x1003] = Const CShape(0x1003)
- StoreField v35, :_shape_id@0x1000, v40
  v14:HeapBasicObject = RefineType v6, HeapBasicObject
  v17:Fixnum[2] = Const Value(2)
  PatchPoint SingleRactorMode
  StoreField v14, :@b@0x1004, v17
  WriteBarrier v14, v17
  v47:CShape[0x1005] = Const CShape(0x1005)
- StoreField v14, :_shape_id@0x1000, v47
  v21:HeapBasicObject = RefineType v14, HeapBasicObject
  v24:Fixnum[3] = Const Value(3)
  PatchPoint SingleRactorMode
  StoreField v21, :@c@0x1006, v24
  WriteBarrier v21, v24
  v54:CShape[0x1007] = Const CShape(0x1007)
  StoreField v21, :_shape_id@0x1000, v54
  CheckInterrupts
  Return v24

[jacob-shops]

This pass is similar to load store optimization.

Here's the sketch with which I plan to implement it.

Start at the bottom of a basic block and trace backwards. The last StoreField operation can never be elided because it can be used in other blocks.

However, we can scan backwards to find other StoreFields of the same object and offset. Let's call the first store s0 and the second s1. If there are no loads, aliasing issues, nor effectful operations that write to the object between s0 and s1, then we know that s0 is elidable.

This optimization could use similar type based alias analysis improvements like load-store optimization that we will ignore for now.