[SWP] Recognize mem carried dep with different base

[thopre]

Summary

The loop-carried dependency detection logic in isLoopCarriedDep relies
on the load and store using the same definition for the base register.
This misses the case of post-increment loads and stores whose base
register are different PHI initialized from the same initial value.

This commit extends the logic to accept the load and store having
different PHI base address provided that they had the same initial value
when entering the loop and are incremented by the same amount in each
loop.

[thopre]

Remove IR block in test

[thopre]

llvm/test/CodeGen/Hexagon/swp-carried-dep3.mir

58

The loadrh_io + this A2_addi is meant to represent a postinc MIR load. Likewise for the S2_storeh_io and the A2_addi on the line before. This is the usecase we are facing on the Graphcore IPU.

If there's a way to reproduce the same either on Hexagon or PowerPC I'm happy to amend the testcase.

[bcahoon]

llvm/lib/CodeGen/MachinePipeliner.cpp

2301

I don't think this is needed because computeDelta performs this check. However, this isn't really related to your change...

llvm/test/CodeGen/Hexagon/swp-carried-dep3.mir

15

It looks like this is the same output without your patch. Can you add a test, or change this one, that shows the effect of the patch?

53

If the offset is changed from -8 to 0, then there is no loop carried dependence with your patch.

BTW, if you want to use post-increment instructions it would be
%19:intregs, %22:intregs = L2_loadrh_pi %21, 2 :: (load (s16))

55

The post-increment version is
%9:intregs = S2_storerh_pi %4, 2, killed %20 :: (store (s16))

[thopre]

Modify tests as per suggestion and checked it shows a difference with and without diff

[thopre]

llvm/lib/CodeGen/MachinePipeliner.cpp

2301

Do you want me to remove that then?

llvm/test/CodeGen/Hexagon/swp-carried-dep3.mir

15

I had checked that the code was being hit with the earlier version of the testcase but hadn't really understood the CHECK lines. I've verify that the updated test does indeed show a difference with and without the patch.

[bcahoon]

llvm/lib/CodeGen/MachinePipeliner.cpp

2301

I don't think that needs to be done with this patch. Maybe a separate NFC patch.

llvm/test/CodeGen/Hexagon/swp-carried-dep3.mir

15

I don't think the nodeset that includes SU(4) and SU(6) is affected by by this patch?

I believe the patch eliminates Nodeset that includes SU(5) and SU(7) because the patch eliminates the need for a loop carried dependence. If so, then I think the test should check that the Nodeset with SU(5) and SU(7) is no longer created.

[thopre]

Rewrite CHECK lines

[thopre]

llvm/test/CodeGen/Hexagon/swp-carried-dep3.mir

15

You're absolutely right:

--- swp-carried-dep3.withoutpatch.log   2022-10-31 11:17:38.775837761 +0000
+++ swp-carried-dep3.withpatch.log      2022-10-31 11:06:53.083501068 +0000
@@ -228,10 +228,6 @@ SU(8):   %17:intregs = M2_acci %19:intre
    SU(6) %20:intregs = A2_addi %18:intregs, 10
    SU(7) %13:intregs = S2_storerh_pi %12:intregs(tied-def 0), 2, %20:intregs :: (store (s16))
 
-  Rec NodeSet Num nodes 2 rec 0 mov 0 depth 2 col 0
-   SU(5) %19:intregs, %15:intregs = L2_loadrh_pi %14:intregs(tied-def 1), 2 :: (load (s16))
-   SU(7) %13:intregs = S2_storerh_pi %12:intregs(tied-def 0), 2, %20:intregs :: (store (s16))
-
   NodeSet Num nodes 3 rec 1 mov 0 depth 2 col 0
    SU(4) %18:intregs, %11:intregs = L2_loadrh_pi %10:intregs(tied-def 1), 2 :: (load (s16))
    SU(6) %20:intregs = A2_addi %18:intregs, 10

[sgundapa]

llvm/lib/CodeGen/MachinePipeliner.cpp

2282

Too late to comment, but I believe this if condition will mark wrong loop carried dependences.

Eg:
SU(0): %62:intregs = PHI %12:intregs, %bb.8, %85:intregs, %bb.9
SU(1): %63:intregs = L2_loadrh_io %62:intregs, 0 :: (load (s16) from %ir.arrayidx.phi)
......
......
......
SU(5): %85:intregs = S2_storerh_pi %62:intregs(tied-def 0), 8, %66:intregs :: (store (s16) into %ir.arrayidx.phi)
.......
.......
SU(10): S2_storerh_io %85:intregs, -6, %72:intregs :: (store (s16) into %ir.arrayidx.phi + 2)

SU1-SU10 will me marked as an LCD

[thopre]

llvm/lib/CodeGen/MachinePipeliner.cpp

2282

Indeed, I've created https://reviews.llvm.org/D140168 to fix that. Thanks!

llvm/lib/CodeGen/MachinePipeliner.cpp

if (!TII->getMemOperandWithOffset(*SI, BaseOpS, OffsetS, OffsetSIsScalable,
                                     TRI) ||
       !TII->getMemOperandWithOffset(*DI, BaseOpD, OffsetD, OffsetDIsScalable,
                                     TRI))
     return true;
 
   assert(!OffsetSIsScalable && !OffsetDIsScalable &&
          "Expected offsets to be byte offsets");
 
-  if (!BaseOpS->isIdenticalTo(*BaseOpD))
+  MachineInstr *DefS = MRI.getVRegDef(BaseOpS->getReg());
+  MachineInstr *DefD = MRI.getVRegDef(BaseOpD->getReg());
+  if (!DefS || !DefD || !DefS->isPHI() || !DefD->isPHI())
+    return true;
+
+  unsigned InitValS = 0;
+  unsigned LoopValS = 0;
+  unsigned InitValD = 0;
+  unsigned LoopValD = 0;
+  getPhiRegs(*DefS, BB, InitValS, LoopValS);
+  getPhiRegs(*DefD, BB, InitValD, LoopValD);
+  MachineInstr *InitDefS = MRI.getVRegDef(InitValS);
+  MachineInstr *InitDefD = MRI.getVRegDef(InitValD);
+
+  if (!InitDefS->isIdenticalTo(*InitDefD))
     return true;
 
   // Check that the base register is incremented by a constant value for each
   // iteration.
-  MachineInstr *Def = MRI.getVRegDef(BaseOpS->getReg());
-  if (!Def || !Def->isPHI())
-    return true;
-  unsigned InitVal = 0;
-  unsigned LoopVal = 0;
-  getPhiRegs(*Def, BB, InitVal, LoopVal);
-  MachineInstr *LoopDef = MRI.getVRegDef(LoopVal);
+  MachineInstr *LoopDefS = MRI.getVRegDef(LoopValS);
   int D = 0;
-  if (!LoopDef || !TII->getIncrementValue(*LoopDef, D))
+  if (!LoopDefS || !TII->getIncrementValue(*LoopDefS, 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 (AccessSizeS == MemoryLocation::UnknownSize ||

llvm/test/CodeGen/Hexagon/swp-carried-dep3.mir

+# RUN: llc -mtriple=hexagon -run-pass pipeliner -debug-only=pipeliner %s -o /dev/null 2>&1 -pipeliner-experimental-cg=true | FileCheck %s
+# REQUIRES: asserts
+
+# Test that the loop carried dependence check correctly identifies a recurrence
+# when load and store use distinct increment for their pointer.
+
+# CHECK: Rec NodeSet
+# CHECK: Rec NodeSet
+# CHECK: Rec NodeSet
+# CHECK: Rec NodeSet
+# CHECK: Rec NodeSet
+# CHECK-NEXT: SU(5)
+# CHECK-NEXT: SU(7)
+
+--- |
+
+  %struct.A = type { i16, i16 }
+
+  define i32 @test(%struct.A* noalias nocapture %s, i16* noalias nocapture readonly %r, i32 %n) {
+  entry:
+    %cmp19 = icmp eq i32 %n, 2
+    br i1 %cmp19, label %for.end, label %for.body.preheader
+
+  for.body.preheader:
+    %0 = add i32 %n, -2
+    %cgep = getelementptr %struct.A, %struct.A* %s, i32 2, i32 1
+    %scevgep1 = bitcast i16* %cgep to %struct.A*
+    %cgep9 = getelementptr i16, i16* %r, i32 2
+    br label %for.body
+
+  for.body:
+    %lsr.iv7 = phi i16* [ %cgep9, %for.body.preheader ], [ %cgep12, %for.body ]
+    %lsr.iv2 = phi %struct.A* [ %scevgep1, %for.body.preheader ], [ %cgep11, %for.body ]
+    %lsr.iv = phi i32 [ %0, %for.body.preheader ], [ %lsr.iv.next, %for.body ]
+    %sum.020 = phi i32 [ %add7, %for.body ], [ 0, %for.body.preheader ]
+    %lsr.iv24 = bitcast %struct.A* %lsr.iv2 to i16*
+    %1 = load i16, i16* %lsr.iv7, align 2
+    %conv = sext i16 %1 to i32
+    %cgep10 = getelementptr i16, i16* %lsr.iv24, i32 -4
+    %2 = load i16, i16* %cgep10, align 2
+    %conv2 = sext i16 %2 to i32
+    %add = add i16 %1, 10
+    store i16 %add, i16* %lsr.iv24, align 2
+    %add6 = add i32 %sum.020, %conv
+    %add7 = add i32 %add6, %conv2
+    %lsr.iv.next = add i32 %lsr.iv, -1
+    %cmp = icmp eq i32 %lsr.iv.next, 0
+    %cgep11 = getelementptr %struct.A, %struct.A* %lsr.iv2, i32 1
+    %cgep12 = getelementptr i16, i16* %lsr.iv7, i32 1
+    br i1 %cmp, label %for.end, label %for.body
+
+  for.end:
+    %sum.0.lcssa = phi i32 [ 0, %entry ], [ %add7, %for.body ]
+    ret i32 %sum.0.lcssa
+  }
+
+...
+---
+name:            test
+tracksRegLiveness: true
+
+body:             |
+  bb.0:
+    successors: %bb.3, %bb.1
+    liveins: $r0, $r1, $r2
+
+    %14:intregs = COPY $r2
+    %13:intregs = COPY $r1
+    %12:intregs = COPY $r0
+    %16:predregs = C2_cmpeqi %14, 2
+    %15:intregs = A2_tfrsi 0
+    J2_jumpt killed %16, %bb.3, implicit-def dead $pc
+    J2_jump %bb.1, implicit-def dead $pc
+
+  bb.1:
+    successors: %bb.2
+
+    %0:intregs = A2_addi %14, -2
+    %1:intregs = A2_addi %12, 10
+    %2:intregs = A2_addi %13, 4
+    %17:intregs = A2_tfrsi 0
+    %23:intregs = COPY %0
+    J2_loop0r %bb.2, %23, implicit-def $lc0, implicit-def $sa0, implicit-def $usr
+
+  bb.2 (machine-block-address-taken):
+    successors: %bb.3, %bb.2
+
+    %3:intregs = PHI %2, %bb.1, %10, %bb.2
+    %4:intregs = PHI %1, %bb.1, %9, %bb.2
+    %21:intregs = PHI %1, %bb.1, %22, %bb.2
+    %6:intregs = PHI %17, %bb.1, %7, %bb.2
+    %18:intregs, %10:intregs = L2_loadrh_pi %3, 2 :: (load (s16) from %ir.lsr.iv7)
+    %19:intregs = L2_loadrh_io %21, -8 :: (load (s16) from %ir.cgep10)
+    %20:intregs = A2_addi %18, 10
+    S2_storerh_io %4, 0, killed %20 :: (store (s16) into %ir.lsr.iv24)
+    %7:intregs = M2_acci %19, %6, %18
+    %9:intregs = A2_addi %4, 4
+    %22:intregs = A2_addi %21, 4
+    ENDLOOP0 %bb.2, implicit-def $pc, implicit-def $lc0, implicit $sa0, implicit $lc0
+    J2_jump %bb.3, implicit-def dead $pc
+
+  bb.3:
+    %11:intregs = PHI %15, %bb.0, %7, %bb.2
+    $r0 = COPY %11
+    PS_jmpret $r31, implicit-def dead $pc, implicit $r0
+
+...