[Pipeliner] Incorrect loop carried dependence calculation

[dantrushin]

Summary

SwingSchedulerDAG::isLoopCarriedDep performs incorrect dependence
calculations. In particular, it cannot properly handle negative
offsets like this:

%1 = PHI %0, %2
%x = LD [%1, -6]   // 32-bit load
...
ST %y, [%1, 2]      // 32-bit store
%2 = ADD %1, 4

and case of stride smaller than access size like this:

%1 = PHI %0, %2
%x = LD [%1, 0]        // 32-bit load
...
ST %y, [%1, 2]        // 32-bit store
%2 = ADD %1, 2

[bcahoon]

Thanks for the patch! I've been trying to create a test case, but haven't had much luck.

Thanks,,
Brendon

[dantrushin]

I don't have commit access. Brendon, could you do it for me?

Thanks,
Denis

llvm/lib/CodeGen/MachinePipeliner.cpp

bool SwingSchedulerDAG::isLoopCarriedDep(SUnit *Source, const SDep &Dep,
   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;
+  if (AccessSizeS == MemoryLocation::UnknownSize ||
+      AccessSizeD == MemoryLocation::UnknownSize)
+    return true;
 
+  if (DeltaS != DeltaD || DeltaS < AccessSizeS || DeltaD < AccessSizeD)
     return true;
+
+  return (OffsetS + (int64_t)AccessSizeS < OffsetD + (int64_t)AccessSizeD);
 }
 
 void SwingSchedulerDAG::postprocessDAG() {
   for (auto &M : Mutations)
     M->apply(this);
 }
 
 /// Try to schedule the node at the specified StartCycle and continue