[AggressiveAntiDepBreaker] Don't change aliased registers of liveins to alive in StartBlock

[cycheng]

Summary

Current AADB will set aliased registers of liveins to alive in StartBlock, but this is unreasonable, because we will lose rename chances for any rename-able registers of liveins if any of their aliased registers are not be defined.

To correct this, in StartBlock, we only change livein registers to alive, but not include their alias registers.

I've tested the patch on PowerPC, bootstrap test, spec2006 test, llvm test, all result are correct.

[cycheng]

Fix test case to create correct live-in registers for next.bb that can demonstrate the issue.

[hfinkel]

lib/CodeGen/AggressiveAntiDepBreaker.cpp

153–187

Can you please add a comment here:

// We only need to consider the live-out registers themselves, not all aliases, because...

[cycheng]

[Discussion in mail]

Nemanja:
Take basic block BB1 and its successor BB2. If there is a definition of register R in BB1 and R is live-in for BB2, then it's OK to rename definitions/uses of R's aliases in BB1. Of course, it is not OK to rename R (the physical register) in BB1. Or am I misreading this?

CY:
Yes, we can rename R's aliases in BB1, my point is: in StartBlock, we only need to set R to live, but not its aliases, so, the question becomes: is my point correct?

Using your case, the incorrect scenario will be:

R's aliases are defined in BB1, and
these define are implicit used in BB2 through R, and
these define are renamed in BB1

So, assume r is an alias of R, then:

BB1:
  def r (last def) <= can we rename this? No, because its alias 'R' is group 0
  def R (last def, group = 0)

BB2:
  live-ins: R
  use R

So, current AADB guards for us that incorrect scenario is not going to happen.

[cycheng]

[Discussion in mail]

Hal:
I think the real question here is, can you have:

BB1:
  def r
  use r

BB2:
  live-ins: R
  use R

or something along those lines? If so, does this work correctly?

CY:
Case1 is work, but Case2 should also work.

Assume r is super register of R.

Case1:

BB1:
  def R => def: R=g0 (Now, R is dead, i.e. enter into new life cycle)
  use R => use: R=g0 (because R is live)
  def r => def: r=gM -> g0 (via R)
  use r => use: g0->gM (last use)

BB2:
  live-ins: R
  use R

Case2:

BB1:
ln1  def r => def: r=gN->gN+1 (via R) (Can be renamed.)
ln2  use r => use: g0->gN (last use) R->gN+1 (last use)
ln3
ln4  def R => def: R=gM (Can be renamed.)
ln5  use R => use: R=g0->gM (last use)
ln6
ln7  def R => def: R=g0 (Now, R is dead, i.e. enter into new life cycle, also update aliases' live-info, so aliases are dead)
ln8  use R => use: R=g0 (because R is live, and init group is 0)

BB2:
  live-ins: R
  use R

I think if BB2 only uses R, then it is fine to rename r in BB1, if BB2 uses r, then r should be one of the live-ins.

[cycheng]

Add explanation in StartBlock to address Hal's review comment.

[cycheng]

Hello everyone, any comments on this patch?

lib/CodeGen/AggressiveAntiDepBreaker.cpp

void AggressiveAntiDepBreaker::StartBlock(MachineBasicBlock *BB) {
   bool IsReturnBlock = BB->isReturnBlock();
   std::vector<unsigned> &KillIndices = State->GetKillIndices();
   std::vector<unsigned> &DefIndices = State->GetDefIndices();
 
   // Examine the live-in regs of all successors.
   for (MachineBasicBlock::succ_iterator SI = BB->succ_begin(),
          SE = BB->succ_end(); SI != SE; ++SI)
     for (const auto &LI : (*SI)->liveins()) {
-      for (MCRegAliasIterator AI(LI.PhysReg, TRI, true); AI.isValid(); ++AI) {
-        unsigned Reg = *AI;
-        State->UnionGroups(Reg, 0);
-        KillIndices[Reg] = BB->size();
-        DefIndices[Reg] = ~0u;
-      }
-    }
+      // We only need to consider the live-out registers themselves, not all
+      // aliases, because we can get more rename chances for live-out registers
+      // in BB.
+      //
+      // Why this is correct? Consider the following cases:
+      //
+      // Assume r is alias of R, if R is live-out, can rename r cause incorrect
+      // result?
+      //
+      // case 1:                   case 2:
+      // BB1:                      BB1:
+      //   def R: R=g0               def r: r=gN->gN+1 (via R) (Can be renamed.)
+      //   use R: R=g0               use r: g0->gN (last use) R->gN+1 (last use)
+      //   def r: r=gM->g0 (via R)
+      //   use r: g0->gM (last use)  def R: R=gM (Can be renamed.)
+      //                             use R: R=g0->gM (last use)
+      // BB2:
+      //   live-ins: R               def R: R=g0
+      //   use R                     use R: R=g0
+      //
+      //                           BB2:
+      //                             live-ins: R
+      //                             use R
+      //
+      // In case 1, AADB can't rename r (or any of R's alias), because R is
+      // still live, and is group0.
+      //
+      // In case 2, if r is sub-register of R, then it is fine to rename r.
+      // If r is super-register of R, but in BB2, we only use R, it is still
+      // fine to rename r in BB1; if r is also used in BB2, then r should be
+      // live-out, too.
+      unsigned Reg = LI.PhysReg;
 
   // Mark live-out callee-saved registers. In a return block this is
   // all callee-saved registers. In non-return this is any
   // callee-saved register that is not saved in the prolog.
   const MachineFrameInfo *MFI = MF.getFrameInfo();
   BitVector Pristine = MFI->getPristineRegs(MF);
   for (const MCPhysReg *I = TRI->getCalleeSavedRegs(&MF); *I; ++I) {
     unsigned Reg = *I;

test/CodeGen/PowerPC/ppc64-aadb.ll

+; RUN: llc < %s -break-anti-dependencies=all -march=ppc64 -mcpu=pwr8 \
+; RUN:   -print-before=post-RA-sched -o /dev/null | \
+; RUN:   FileCheck %s -check-prefix=CHECK-BEFORE-POST-RA
+; RUN: llc < %s -break-anti-dependencies=all -march=ppc64 -mcpu=pwr8 \
+; RUN:   -verify-machineinstrs | FileCheck %s
+
+; Create a scenario that next.bb uses many variables (VSX registers) comes
+; from bb, in this case, they are: %0 %1 %2 %3 %add15. These use will prevent
+; original Aggressive Anti-Dependency Breaker from renaming many false
+; dependency VSX registers in bb.
+;
+; We correct this behaviour and use this test case to guard the new behaviour.
+define double @aadb(double* nocapture readonly %d, i32 signext %val) #0 {
+bb:
+  %0 = load double, double* %d
+  %arrayidx1 = getelementptr inbounds double, double* %d, i64 1
+  %1 = load double, double* %arrayidx1
+  %arrayidx2 = getelementptr inbounds double, double* %d, i64 2
+  %2 = load double, double* %arrayidx2
+  %arrayidx3 = getelementptr inbounds double, double* %d, i64 3
+  %3 = load double, double* %arrayidx3
+  %add = fadd double %0, %1
+  %add4 = fadd double %2, %3
+  %sub = fsub double %add, %add4
+  %mul = fmul double %0, %1
+  %add5 = fadd double %mul, %sub
+  %mul6 = fmul double %0, %2
+  %add7 = fadd double %mul6, %add5
+  %mul8 = fmul double %0, %3
+  %sub9 = fsub double %add7, %mul8
+  %mul10 = fmul double %1, %2
+  %sub11 = fsub double %sub9, %mul10
+  %mul12 = fmul double %1, %3
+  %sub13 = fsub double %sub11, %mul12
+  %mul14 = fmul double %2, %3
+  %add15 = fadd double %mul14, %sub13
+  %tobool = icmp eq i32 %val, 0
+  br i1 %tobool, label %end, label %next.bb
+
+; Check whether live-in registers are as our expectation before post-RA-sched.
+; CHECK-BEFORE-POST-RA: %F5<def>
+; CHECK-BEFORE-POST-RA: %F1<def>
+; CHECK-BEFORE-POST-RA: %CR0<def>
+; CHECK-BEFORE-POST-RA: BB#1
+; CHECK-BEFORE-POST-RA: Live Ins: %F0 %F1 %F2 %F3 %F4 %F5 %X3
+
+; CHECK-LABEL: aadb
+; CHECK: BB#0
+; CHECK-DAG: xsadddp 1
+; CHECK-DAG: xsadddp 5
+; CHECK-DAG: xsmuldp 9
+; CHECK-DAG: xsmuldp 10
+; CHECK-DAG: xsmuldp 11
+; CHECK-DAG: xsmuldp 12
+; CHECK-DAG: xsmuldp 13
+
+next.bb:
+  %arrayidx16 = getelementptr inbounds double, double* %d, i64 4
+  %4 = load double, double* %arrayidx16
+  %arrayidx17 = getelementptr inbounds double, double* %d, i64 5
+  %5 = load double, double* %arrayidx17
+  %mul18 = fmul double %4, %5
+  %sub19 = fsub double %0, %1
+  %sub20 = fsub double %mul18, %sub19
+  %sub21 = fsub double %2, %3
+  %sub22 = fsub double %sub20, %sub21
+  %add24 = fadd double %mul14, %sub22
+  %add25 = fadd double %add15, %add24
+  br label %end
+
+end:
+  %result.0 = phi double [ %add25, %next.bb ], [ %add15, %bb ]
+  ret double %result.0
+}