Memory writes overlap in the pipelined loop

[yan_luo]

Summary

The original loop is like:

%15 = …

LOOP:

%26 = PHI %15, %31 
…
STORE -> [%26 + 32, %26 + 32 + 64]  <- 64 is the access size
…
STORE -> [%26 + 0, %26 + 0 + 64]
…
STORE -> [%26 + 62, %26 + 62 + 64]
…
STORE -> [%26 + 94, %26 + 94 + 64]
…
%31 = ADD %26, 124

LOOP_END

The software pipelined loop is like:

%15 = …
%234 = COPY %15

PROLOG:

…
STORE -> [%234 + 32, %234 + 32 + 64]
…
STORE -> [%234 + 0, %234 + 0 + 64]
…
STORE -> [%234 + 62, %234 + 62 + 64]
…
%227 = ADD %234, 124

KERNEL:

%291 = PHI %227, %241
%292 = PHI %15, %291
…
%303 = COPY %291
%241 = ADD %303, 124
…
STORE -> [%303 + 32, %303 + 32 + 64]
…
STORE -> [%303 + 0, %303 + 0 + 64]
…
STORE -> [%292 + 94, %292 + 94 + 64] <- !!!
…
STORE -> [%303 + 62, %303 + 62 + 64]

…
KERNEL_END
EPILOG:

%299 = PHI %15, %303
STORE -> [%299 + 94, %299 + 94 + 64]

The new content in [offset 0, offset 0 + 64] in the next iteration is overwritten by the write [offset 94, offset94 + 64] in the previous iteration. The loop carried dependency could also exist between store and store instructions.

[lebedev.ri]

Test?

[yan_luo]

Currently I only have an in-house benchmark for this. Not sure I can share this, but if Brendon confirms this is a correct fix, I will try to come up with a reproducible testcase.

[lebedev.ri]

This needs to be a test somewhere in llvm/test/CodeGen/?arch?/.
Not sure if it should be an IR test, or MIR test.

[yan_luo]

It seems that Hexagon is the only target that is using SWP in the upstream. Not sure a reproducible testcase at our side is also reproducible in the Hexagon target. But I will give it a try.

[bcahoon]

Hi Yan,

Thanks for the patch! I agree that the change is needed. Let me see if I can generate a Hexagon test case also.

Thanks,
Brendon

lib/CodeGen/MachinePipeliner.cpp

3135 ↗

(On Diff #189544)

I think the following is equivalent:

if (!DI->mayStore())

return false;

[yan_luo]

Only need to check mayStore() on DI.

[lebedev.ri]

lib/CodeGen/MachinePipeliner.cpp

3134–3135 ↗

(On Diff #189727)

The diff should not be relative to the previously uploaded patch.

[yan_luo]

Updated the diff.

[dantrushin]

llvm/lib/CodeGen/MachinePipeliner.cpp

3170

BTW, is this code correct?
I would expect something like

(OffsetS + DeltaS) <= (OffsetD + AccessSizeD) && (OffsetS + AccessSizeS + Delta) >= OffsetD

Am I missing something?

[bcahoon]

llvm/lib/CodeGen/MachinePipeliner.cpp

3170

This is wrong. I need to upstream our change to this, which is:

return DeltaS != DeltaD || OffsetS + AccessSizeS < OffsetD + AccessSizeD;

to replace the if-else and return.

llvm/lib/CodeGen/MachinePipeliner.cpp

if (!isSucc)
     std::swap(SI, DI);
   assert(SI != nullptr && DI != nullptr && "Expecting SUnit with an MI.");
 
   // Assume ordered loads and stores may have a loop carried dependence.
   if (SI->hasUnmodeledSideEffects() || DI->hasUnmodeledSideEffects() ||
       SI->hasOrderedMemoryRef() || DI->hasOrderedMemoryRef())
     return true;
 
-  // Only chain dependences between a load and store can be loop carried.
-  if (!DI->mayStore() || !SI->mayLoad())
+  if (!DI->mayStore())
     return false;
 
   unsigned DeltaS, DeltaD;
   if (!computeDelta(*SI, DeltaS) || !computeDelta(*DI, DeltaD))
     return true;
 
   MachineOperand *BaseOpS, *BaseOpD;
   int64_t OffsetS, OffsetD;
if (!LoopDef || !TII->getIncrementValue(*LoopDef, D))
     return true;
 
   uint64_t AccessSizeS = (*SI->memoperands_begin())->getSize();
   uint64_t AccessSizeD = (*DI->memoperands_begin())->getSize();
 
   // This is the main test, which checks the offset values and the loop
   // increment value to determine if the accesses may be loop carried.
   if (OffsetS >= OffsetD)
     return OffsetS + AccessSizeS > DeltaS;
   else
     return OffsetD + AccessSizeD > DeltaD;
 
   return true;
 }
 
 void SwingSchedulerDAG::postprocessDAG() {
   for (auto &M : Mutations)