Add anti- and output loop carried dependences in SwingScheduler

[ning4827]

Summary

Consider anti- and output dependences in the addLoopCarriedDependences function

[bcahoon]

Hi Ning,

Just a couple of minor comments, but I think the change looks good. I tried your example, provided in an earlier version, but it doesn't have any output or anti dependences by the time it gets to the pipeliner. The load of a[i-1] gets optimized away. I used the following to compile it, so perhaps some other command-line options are needed?

clang -fno-unroll-loops -target hexagon -O2 example.c -o example.s -S

But, I did noticee that a lit test, test/CodeGen/Hexagon/vect/vect-v4i16.ll, fails with the patch due to extra output dependence edges. It contains a loop that is no longer pipelined. The code generation is different, so the checks in the test fail. I think it's fine, for this lit test to remove the checks:
; CHECK: memuh(r{{[0-9]+}}+#6)
; CHECK: combine(r{{[0-9]+}},r{{[0-9]+}})

and leave the check for the vaddh, which shows that the test is vectorized.

Thanks,
Brendon

lib/CodeGen/MachinePipeliner.cpp

1026

Update the command to reflect the new functionality.

1052

Change the variable name, Load, since this can be either a load or store.

[ning4827]

Change the variable name and update the comments

[ning4827]

Fix the lit test

[ning4827]

Thanks Brendon for the comments. I have updated the diff. Let me know if it's okay.

Best,
Ning

In D38691#896376, @bcahoon wrote:

Hi Ning,

Just a couple of minor comments, but I think the change looks good. I tried your example, provided in an earlier version, but it doesn't have any output or anti dependences by the time it gets to the pipeliner. The load of a[i-1] gets optimized away. I used the following to compile it, so perhaps some other command-line options are needed?

I worked on another platform and didn't realize that a[i-1] will be optimized away on Hexagon..

clang -fno-unroll-loops -target hexagon -O2 example.c -o example.s -S

But, I did noticee that a lit test, test/CodeGen/Hexagon/vect/vect-v4i16.ll, fails with the patch due to extra output dependence edges. It contains a loop that is no longer pipelined. The code generation is different, so the checks in the test fail. I think it's fine, for this lit test to remove the checks:
; CHECK: memuh(r{{[0-9]+}}+#6)
; CHECK: combine(r{{[0-9]+}},r{{[0-9]+}})

and leave the check for the vaddh, which shows that the test is vectorized.

Thanks,
Brendon

[ning4827]

Add back the changes on pipliner

[bcahoon]

Sorry for the delay in responding. I've been trying to create a simple test case for this patch, but no luck yet. Otherwise, the patch looks good to me. Thanks!

[bcahoon]

Hi Ning,

Let me know if you need me to commit this patch. Or, if you're able to commit it, then that would be great too.

Thanks,
Brendon

[ning4827]

Hi Brendon,

As a first-time llvm patch uploader, I don't think I can commit.. :-)
Thank you for reviewing this patch and to commit it.

Best,
Ning

In D38691#915665, @bcahoon wrote:

Hi Ning,

Let me know if you need me to commit this patch. Or, if you're able to commit it, then that would be great too.

Thanks,
Brendon

lib/CodeGen/MachinePipeliner.cpp

static void getUnderlyingObjects(MachineInstr *MI,
   if (!MI->hasOneMemOperand())
     return;
   MachineMemOperand *MM = *MI->memoperands_begin();
   if (!MM->getValue())
     return;
   GetUnderlyingObjects(const_cast<Value *>(MM->getValue()), Objs, DL);
 }
 
 /// Add a chain edge between a load and store if the store can be an
 /// alias of the load on a subsequent iteration, i.e., a loop carried
-/// dependence. This code is very similar to the code in ScheduleDAGInstrs
+/// dependence. 
+/// Similarly, add a chain edge between a store and load or between a
+/// store and store.
+/// This code is very similar to the code in ScheduleDAGInstrs
 /// but that code doesn't create loop carried dependences.
 void SwingSchedulerDAG::addLoopCarriedDependences(AliasAnalysis *AA) {
-  MapVector<Value *, SmallVector<SUnit *, 4>> PendingLoads;
+  MapVector<Value *, SmallVector<SUnit *, 8>> PendingLoadsStores;
   for (auto &SU : SUnits) {
     MachineInstr &MI = *SU.getInstr();
     if (isDependenceBarrier(MI, AA))
-      PendingLoads.clear();
-    else if (MI.mayLoad()) {
-      SmallVector<Value *, 4> Objs;
-      getUnderlyingObjects(&MI, Objs, MF.getDataLayout());
-      for (auto V : Objs) {
-        SmallVector<SUnit *, 4> &SUs = PendingLoads[V];
-        SUs.push_back(&SU);
-      }
-    } else if (MI.mayStore()) {
-      SmallVector<Value *, 4> Objs;
-      getUnderlyingObjects(&MI, Objs, MF.getDataLayout());
-      for (auto V : Objs) {
-        MapVector<Value *, SmallVector<SUnit *, 4>>::iterator I =
-            PendingLoads.find(V);
-        if (I == PendingLoads.end())
+      PendingLoadsStores.clear();
+    else if (!MI.mayLoad() && !MI.mayStore())
+      continue;
+
+    SmallVector<Value *, 8> Objs;
+      SmallVector<SUnit *, 8> &SUs = PendingLoadsStores[V];
+
+      MapVector<Value *, SmallVector<SUnit *, 8>>::iterator I =
+          PendingLoadsStores.find(V);
+      if (I == PendingLoadsStores.end())
+        continue;
+      for (auto LdSt : I->second) {
+        if (isSuccOrder(LdSt, &SU))
           continue;
-        for (auto Load : I->second) {
-          if (isSuccOrder(Load, &SU))
-            continue;
-          MachineInstr &LdMI = *Load->getInstr();
-          // First, perform the cheaper check that compares the base register.
-          // If they are the same and the load offset is less than the store
-          // offset, then mark the dependence as loop carried potentially.
-          unsigned BaseReg1, BaseReg2;
-          int64_t Offset1, Offset2;
-          if (!TII->getMemOpBaseRegImmOfs(LdMI, BaseReg1, Offset1, TRI) ||
-              !TII->getMemOpBaseRegImmOfs(MI, BaseReg2, Offset2, TRI)) {
-            SU.addPred(SDep(Load, SDep::Barrier));
-            continue;            
-          }
-          if (BaseReg1 == BaseReg2 && (int)Offset1 < (int)Offset2) {
-            assert(TII->areMemAccessesTriviallyDisjoint(LdMI, MI, AA) &&
-                   "What happened to the chain edge?");
-            SU.addPred(SDep(Load, SDep::Barrier));
-            continue;
-          }
-          // Second, the more expensive check that uses alias analysis on the
-          // base registers. If they alias, and the load offset is less than
-          // the store offset, the mark the dependence as loop carried.
-          if (!AA) {
-            SU.addPred(SDep(Load, SDep::Barrier));
-            continue;
-          }
-          MachineMemOperand *MMO1 = *LdMI.memoperands_begin();
-          MachineMemOperand *MMO2 = *MI.memoperands_begin();
-          if (!MMO1->getValue() || !MMO2->getValue()) {
-            SU.addPred(SDep(Load, SDep::Barrier));
-            continue;
-          }
-          if (MMO1->getValue() == MMO2->getValue() &&
-              MMO1->getOffset() <= MMO2->getOffset()) {
-            SU.addPred(SDep(Load, SDep::Barrier));
-            continue;
-          }
-          AliasResult AAResult = AA->alias(
-              MemoryLocation(MMO1->getValue(), MemoryLocation::UnknownSize,
-                             MMO1->getAAInfo()),
-              MemoryLocation(MMO2->getValue(), MemoryLocation::UnknownSize,
-                             MMO2->getAAInfo()));
+
+        MachineInstr &LdStMI = *LdSt->getInstr();
+        if ((LdStMI.mayLoad() && MI.mayLoad()) || &LdStMI == &MI)
+
+        if (!TII->getMemOpBaseRegImmOfs(LdStMI, BaseReg1, Offset1, TRI) ||
+          SU.addPred(SDep(LdSt, SDep::Barrier));
+          continue;
+          assert(TII->areMemAccessesTriviallyDisjoint(LdStMI, MI, AA) &&
+          SU.addPred(SDep(LdSt, SDep::Barrier));
+          SU.addPred(SDep(LdSt, SDep::Barrier));
+        MachineMemOperand *MMO1 = *LdStMI.memoperands_begin();
+          SU.addPred(SDep(LdSt, SDep::Barrier));
+          SU.addPred(SDep(LdSt, SDep::Barrier));
 
-          if (AAResult != NoAlias)
-            SU.addPred(SDep(Load, SDep::Barrier));
-        }
+          SU.addPred(SDep(LdSt, SDep::Barrier));
       }
     }
   }
 }
 
 /// Update the phi dependences to the DAG because ScheduleDAGInstrs no longer
 /// processes dependences for PHIs. This function adds true dependences
 /// from a PHI to a use, and a loop carried dependence from the use to the

test/CodeGen/Hexagon/vect/vect-v4i16.ll

 ; RUN: llc -march=hexagon -mcpu=hexagonv5 -disable-hsdr < %s | FileCheck %s
 
 ; Check that store is post-incremented.
-; CHECK: memuh(r{{[0-9]+}}+#6)
-; CHECK: combine(r{{[0-9]+}},r{{[0-9]+}})
 ; CHECK: vaddh
 
 target datalayout = "e-p:32:32:32-i64:64:64-i32:32:32-i16:16:16-i1:32:32-f64:64:64-f32:32:32-v64:64:64-v32:32:32-a0:0-n16:32"
 target triple = "hexagon"
 
 define void @matrix_add_const(i32 %N, i16* nocapture %A, i16 signext %val) #0 {
 entry:
   %cmp5 = icmp eq i32 %N, 0