[MachinePipeliner] Store-After-Store order dependency is not considered

[komalon1]

See reproducer in: https://godbolt.org/z/vEv5r6Md7
We have 2 aliased stores in the loop that have order dependency:

SU(5):   STBX8 %19:g8rc, %7:g8rc_and_g8rc_nox0, %18:g8rc :: (store (s8) into %ir.17)
  # preds left       : 1
  # succs left       : 1
  # rdefs left       : 0
  Latency            : 1
  Depth              : 6
  Height             : 0
  Predecessors:
    SU(4): Data Latency=2 Reg=%18
  Successors:
    SU(11): Ord  Latency=0 Memory

and

SU(11):   STBX8 %25:g8rc, %8:g8rc_and_g8rc_nox0, %24:g8rc :: (store (s8) into %ir.18)
  # preds left       : 2
  # succs left       : 0
  # rdefs left       : 0
  Latency            : 1
  Depth              : 12
  Height             : 0
  Predecessors:
    SU(10): Data Latency=2 Reg=%24
    SU(5): Ord  Latency=0 Memory

But the pipeliner schedules the two stores at different stages (cycle 6, cycle 13, II=4) which is illegal:

Inst (5)   STBX8 %19:g8rc, %7:g8rc_and_g8rc_nox0, %18:g8rc :: (store (s8) into %ir.17)

	es:        6 ls: 7fffffff me: 7fffffff ms: 80000000
Trying to insert node between 6 and 9 II: 4
	insert at cycle 6   STBX8 %19:g8rc, %7:g8rc_and_g8rc_nox0, %18:g8rc :: (store (s8) into %ir.17)

Inst (11)   STBX8 %25:g8rc, %8:g8rc_and_g8rc_nox0, %24:g8rc :: (store (s8) into %ir.18)

	es:        d ls: 7fffffff me: 7fffffff ms: 80000000
Trying to insert node between 13 and 16 II: 4
	insert at cycle 13   STBX8 %25:g8rc, %8:g8rc_and_g8rc_nox0, %24:g8rc :: (store (s8) into %ir.18)

[bcahoon]

One potential solution - #72575

[bcahoon]

Hi @komalon1, can you provide more details about reported issue? In the comments for the patch, #72575, there is a valid question about why the generated schedule for the test case is an error.

[komalon1]

@bcahoon
The issue is that the 2 stores are aliased, and may write to the same locations. Let's assume they point to the same base address. So in the example I gave in which the II = 4, the 1st store is scheduled at cycle 6, and the 2nd store scheduled at cycle 13 the generated code would look something like:

Prologue1: (cycles [0-3])
  {}
Prologue2: (cycles [4-7])
  {store1} // (let's assume store idx = 0, stored value = 0)
Prologue3: (cycles [8-11])
  {store1} // (let's assume store idx = 0, stored value = 1)
Steady-state:
  {store2 (cycle 13)} // (let's assume store idx = 0, stored value = 2)
  {store1 (cycle 14)} // (let's assume store idx != 0)
Epilogue1:
  {store2} // (let's assume store idx != 0)
Epilogue2:
  {store2} // (let's assume store idx != 0)

As can be seen, we would expect the the value in index=0 would be 1, but since the 1st store bypassed the 2nd store by an iteration, the stored value would be 2, due to the 2nd store happening the first time only in the stead-state.