Target hooks for custom COPY insertion.

[alex-t]

Summary

PHI Elimination pass relies on TargetInstrInfo::isBlockPrologue/isTerminator target hooks to determine the COPY insertion points.
In some cases this is not sufficient. Divergent control flow requires instructions that belong to block prologue and consume registers defined by the PHI node in the same block.
2 new hooks were added to allow target to override the default COPY placement if necessary or fall through to the base class method otherwise.

[vpykhtin]

llvm/lib/CodeGen/PHIElimination.cpp

280

return inserted instruction and assign iterator to it to AfterPHIsIt

410

returned InsertPos and NewSrcInstr is the same, use only returned value, remove reference arg from the interface.

llvm/lib/Target/AMDGPU/SIInstrInfo.cpp

6398

use the same name for LastPHIIt arg as in the declaration

6400

auto

6407

search first user from the beginning of the block?

llvm/lib/Target/AMDGPU/SIInstrInfo.h

957

void -> MachineInstr*, remove reference to InsPt

963

remove reference from InsPt

[lebedev.ri]

Would be good to have test coverage either in the same patch or have dependent patch explicitly marked as such.

[arsenm]

llvm/include/llvm/CodeGen/TargetInstrInfo.h

1647

Should use Register instead of unsigned

[alex-t]

In D67101#1655941, @lebedev.ri wrote:

Would be good to have test coverage either in the same patch or have dependent patch explicitly marked as such.

The patch really changes AMDGPU PHI elimination and leaves other targets behavior unaffected.
So the test that I will add make sense for AMDGPU only.
Is it okay?

[lebedev.ri]

In D67101#1655973, @alex-t wrote:

In D67101#1655941, @lebedev.ri wrote:

Would be good to have test coverage either in the same patch or have dependent patch explicitly marked as such.

The patch really changes AMDGPU PHI elimination and leaves other targets behavior unaffected.
So the test that I will add make sense for AMDGPU only.
Is it okay?

Absolutely.

[alex-t]

Changed according to the reviewers requests. Tests added.

[vpykhtin]

LGTM.

[MaskRay]

llvm/include/llvm/CodeGen/TargetInstrInfo.h

1642

Delete to

1652

Delete to

[RKSimon]

@alex-t This is failing on EXPENSIVE_CHECKS builds: http://lab.llvm.org:8011/builders/llvm-clang-x86_64-expensive-checks-win/builds/19594/steps/test-check-all/logs/stdio

[alex-t]

In D67101#1665906, @RKSimon wrote:

@alex-t This is failing on EXPENSIVE_CHECKS builds: http://lab.llvm.org:8011/builders/llvm-clang-x86_64-expensive-checks-win/builds/19594/steps/test-check-all/logs/stdio

Will fix ASAP

[alex-t]

Commit was reverted due to the EXPENSIVE_CHECKS failure.
Issue fixed

[rampitec]

llvm/lib/Target/AMDGPU/SIInstrInfo.cpp

6417

So you think it is always scalar and always 64 bit?

[alex-t]

Empty block handling added

[alex-t]

llvm/lib/Target/AMDGPU/SIInstrInfo.cpp

6417

Since only case is SI_CF yes.

[alex-t]

llvm/lib/Target/AMDGPU/SIInstrInfo.cpp

6417

Oh... yes. in WAVE32 it will be S_MOV_B32_term

[alex-t]

Wave32/Wave64 cases

[rampitec]

llvm/lib/Target/AMDGPU/SIInstrInfo.cpp

6422

impdef is just exec, you do not need to use exec_lo.

llvm/lib/Target/AMDGPU/SILowerControlFlow.cpp

190

S_MOV_B64?

[rampitec]

llvm/lib/Target/AMDGPU/SIInstrInfo.cpp

6417

What ensures that is just SI_CF? Why it cannot be some another PHI?

[alex-t]

Changed according the reviewer's request + some refactoring done.

[rampitec]

LGTM

llvm/include/llvm/CodeGen/TargetInstrInfo.h

 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/DenseMapInfo.h"
 #include "llvm/ADT/None.h"
 #include "llvm/CodeGen/LiveRegUnits.h"
 #include "llvm/CodeGen/MachineBasicBlock.h"
 #include "llvm/CodeGen/MachineCombinerPattern.h"
 #include "llvm/CodeGen/MachineFunction.h"
 #include "llvm/CodeGen/MachineInstr.h"
+#include "llvm/CodeGen/MachineInstrBuilder.h"
 #include "llvm/CodeGen/MachineLoopInfo.h"
 #include "llvm/CodeGen/MachineOperand.h"
 #include "llvm/CodeGen/MachineOutliner.h"
 #include "llvm/CodeGen/PseudoSourceValue.h"
 #include "llvm/CodeGen/VirtRegMap.h"
 #include "llvm/MC/MCInstrInfo.h"
 #include "llvm/Support/BranchProbability.h"
 #include "llvm/Support/ErrorHandling.h"
public:
 
   /// True if the instruction is bound to the top of its basic block and no
   /// other instructions shall be inserted before it. This can be implemented
   /// to prevent register allocator to insert spills before such instructions.
   virtual bool isBasicBlockPrologue(const MachineInstr &MI) const {
     return false;
   }
 
+  /// During PHI eleimination lets target to make necessary checks and
+  /// insert the copy to the PHI destination register in a target specific
+  /// manner.
+  virtual MachineInstr *createPHIDestinationCopy(
+      MachineBasicBlock &MBB, MachineBasicBlock::iterator InsPt,
+      const DebugLoc &DL, Register Src, Register Dst) const {
+    return BuildMI(MBB, InsPt, DL, get(TargetOpcode::COPY), Dst)
+        .addReg(Src);
+  }
+
+  /// During PHI eleimination lets target to make necessary checks and
+  /// insert the copy to the PHI destination register in a target specific
+  /// manner.
+  virtual MachineInstr *createPHISourceCopy(MachineBasicBlock &MBB,
+                                            MachineBasicBlock::iterator InsPt,
+                                            const DebugLoc &DL, Register Src,
+                                            Register SrcSubReg,
+                                            Register Dst) const {
+    return BuildMI(MBB, InsPt, DL, get(TargetOpcode::COPY), Dst)
+        .addReg(Src, 0, SrcSubReg);
+  }
+
   /// Returns a \p outliner::OutlinedFunction struct containing target-specific
   /// information for a set of outlining candidates.
   virtual outliner::OutlinedFunction getOutliningCandidateInfo(
       std::vector<outliner::Candidate> &RepeatedSequenceLocs) const {
     llvm_unreachable(
         "Target didn't implement TargetInstrInfo::getOutliningCandidateInfo!");
   }
 

llvm/lib/CodeGen/PHIElimination.cpp

 #include "llvm/CodeGen/MachineFunctionPass.h"
 #include "llvm/CodeGen/MachineInstr.h"
 #include "llvm/CodeGen/MachineInstrBuilder.h"
 #include "llvm/CodeGen/MachineLoopInfo.h"
 #include "llvm/CodeGen/MachineOperand.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
 #include "llvm/CodeGen/SlotIndexes.h"
 #include "llvm/CodeGen/TargetInstrInfo.h"
+#include "llvm/CodeGen/TargetLowering.h"
 #include "llvm/CodeGen/TargetOpcodes.h"
+#include "llvm/CodeGen/TargetPassConfig.h"
 #include "llvm/CodeGen/TargetRegisterInfo.h"
 #include "llvm/CodeGen/TargetSubtargetInfo.h"
 #include "llvm/Pass.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
 #include <cassert>
 #include <iterator>
void PHIElimination::LowerPHINode(MachineBasicBlock &MBB,
   // Create a new register for the incoming PHI arguments.
   MachineFunction &MF = *MBB.getParent();
   unsigned IncomingReg = 0;
   bool reusedIncoming = false;  // Is IncomingReg reused from an earlier PHI?
 
   // Insert a register to register copy at the top of the current block (but
   // after any remaining phi nodes) which copies the new incoming register
   // into the phi node destination.
+  MachineInstr *PHICopy = nullptr;
   const TargetInstrInfo *TII = MF.getSubtarget().getInstrInfo();
   if (allPhiOperandsUndefined(*MPhi, *MRI))
     // If all sources of a PHI node are implicit_def or undef uses, just emit an
     // implicit_def instead of a copy.
-    BuildMI(MBB, AfterPHIsIt, MPhi->getDebugLoc(),
+    PHICopy = BuildMI(MBB, AfterPHIsIt, MPhi->getDebugLoc(),
             TII->get(TargetOpcode::IMPLICIT_DEF), DestReg);
   else {
     // Can we reuse an earlier PHI node? This only happens for critical edges,
     // typically those created by tail duplication.
     unsigned &entry = LoweredPHIs[MPhi];
     if (entry) {
       // An identical PHI node was already lowered. Reuse the incoming register.
       IncomingReg = entry;
       reusedIncoming = true;
       ++NumReused;
       LLVM_DEBUG(dbgs() << "Reusing " << printReg(IncomingReg) << " for "
                         << *MPhi);
     } else {
       const TargetRegisterClass *RC = MF.getRegInfo().getRegClass(DestReg);
       entry = IncomingReg = MF.getRegInfo().createVirtualRegister(RC);
     }
-    BuildMI(MBB, AfterPHIsIt, MPhi->getDebugLoc(),
-            TII->get(TargetOpcode::COPY), DestReg)
-      .addReg(IncomingReg);
+    // Give the target possiblity to handle special cases fallthrough otherwise
+    PHICopy = TII->createPHIDestinationCopy(MBB, AfterPHIsIt, MPhi->getDebugLoc(),
+                                  IncomingReg, DestReg);
   }
 
   // Update live variable information if there is any.
   if (LV) {
-    MachineInstr &PHICopy = *std::prev(AfterPHIsIt);
-
     if (IncomingReg) {
       LiveVariables::VarInfo &VI = LV->getVarInfo(IncomingReg);
 
       // Increment use count of the newly created virtual register.
       LV->setPHIJoin(IncomingReg);
 
       // When we are reusing the incoming register, it may already have been
       // killed in this block. The old kill will also have been inserted at
       // AfterPHIsIt, so it appears before the current PHICopy.
       if (reusedIncoming)
         if (MachineInstr *OldKill = VI.findKill(&MBB)) {
           LLVM_DEBUG(dbgs() << "Remove old kill from " << *OldKill);
           LV->removeVirtualRegisterKilled(IncomingReg, *OldKill);
           LLVM_DEBUG(MBB.dump());
         }
 
       // Add information to LiveVariables to know that the incoming value is
       // killed.  Note that because the value is defined in several places (once
       // each for each incoming block), the "def" block and instruction fields
       // for the VarInfo is not filled in.
-      LV->addVirtualRegisterKilled(IncomingReg, PHICopy);
+      LV->addVirtualRegisterKilled(IncomingReg, *PHICopy);
     }
 
     // Since we are going to be deleting the PHI node, if it is the last use of
     // any registers, or if the value itself is dead, we need to move this
     // information over to the new copy we just inserted.
     LV->removeVirtualRegistersKilled(*MPhi);
 
     // If the result is dead, update LV.
     if (isDead) {
-      LV->addVirtualRegisterDead(DestReg, PHICopy);
+      LV->addVirtualRegisterDead(DestReg, *PHICopy);
       LV->removeVirtualRegisterDead(DestReg, *MPhi);
     }
   }
 
   // Update LiveIntervals for the new copy or implicit def.
   if (LIS) {
-    SlotIndex DestCopyIndex =
-        LIS->InsertMachineInstrInMaps(*std::prev(AfterPHIsIt));
+    SlotIndex DestCopyIndex = LIS->InsertMachineInstrInMaps(*PHICopy);
 
     SlotIndex MBBStartIndex = LIS->getMBBStartIdx(&MBB);
     if (IncomingReg) {
       // Add the region from the beginning of MBB to the copy instruction to
       // IncomingReg's live interval.
       LiveInterval &IncomingLI = LIS->createEmptyInterval(IncomingReg);
       VNInfo *IncomingVNI = IncomingLI.getVNInfoAt(MBBStartIndex);
       if (!IncomingVNI)
if (!reusedIncoming && IncomingReg) {
                               TII->get(TargetOpcode::IMPLICIT_DEF),
                               IncomingReg);
 
         // Clean up the old implicit-def, if there even was one.
         if (MachineInstr *DefMI = MRI->getVRegDef(SrcReg))
           if (DefMI->isImplicitDef())
             ImpDefs.insert(DefMI);
       } else {
-        NewSrcInstr = BuildMI(opBlock, InsertPos, MPhi->getDebugLoc(),
-                            TII->get(TargetOpcode::COPY), IncomingReg)
-                        .addReg(SrcReg, 0, SrcSubReg);
+        NewSrcInstr =
+            TII->createPHISourceCopy(opBlock, InsertPos, MPhi->getDebugLoc(),
+                                     SrcReg, SrcSubReg, IncomingReg);
       }
     }
 
     // We only need to update the LiveVariables kill of SrcReg if this was the
     // last PHI use of SrcReg to be lowered on this CFG edge and it is not live
     // out of the predecessor. We can also ignore undef sources.
     if (LV && !SrcUndef &&
         !VRegPHIUseCount[BBVRegPair(opBlock.getNumber(), SrcReg)] &&
if (LV && !SrcUndef &&
             --KillInst;
             if (KillInst->isDebugInstr())
               continue;
             if (KillInst->readsRegister(SrcReg))
               break;
           }
         } else {
           // We just inserted this copy.
-          KillInst = std::prev(InsertPos);
+          KillInst = NewSrcInstr;
         }
       }
       assert(KillInst->readsRegister(SrcReg) && "Cannot find kill instruction");
 
       // Finally, mark it killed.
       LV->addVirtualRegisterKilled(SrcReg, *KillInst);
 
       // This vreg no longer lives all of the way through opBlock.

llvm/lib/Target/AMDGPU/SIInstrInfo.h

public:
   CreateTargetPostRAHazardRecognizer(const InstrItineraryData *II,
                                  const ScheduleDAG *DAG) const override;
 
   ScheduleHazardRecognizer *
   CreateTargetPostRAHazardRecognizer(const MachineFunction &MF) const override;
 
   bool isBasicBlockPrologue(const MachineInstr &MI) const override;
 
+  MachineInstr *createPHIDestinationCopy(MachineBasicBlock &MBB,
+                                         MachineBasicBlock::iterator InsPt,
+                                         const DebugLoc &DL, Register Src,
+                                         Register Dst) const override;
+
+  MachineInstr *createPHISourceCopy(MachineBasicBlock &MBB,
+                                    MachineBasicBlock::iterator InsPt,
+                                    const DebugLoc &DL, Register Src,
+                                    Register SrcSubReg,
+                                    Register Dst) const override;
+
   /// Return a partially built integer add instruction without carry.
   /// Caller must add source operands.
   /// For pre-GFX9 it will generate unused carry destination operand.
   /// TODO: After GFX9 it should return a no-carry operation.
   MachineInstrBuilder getAddNoCarry(MachineBasicBlock &MBB,
                                     MachineBasicBlock::iterator I,
                                     const DebugLoc &DL,
                                     unsigned DestReg) const;

llvm/lib/Target/AMDGPU/SIInstrInfo.cpp

for (auto I = std::next(DefMI.getIterator()); ; ++I) {
     if (I->readsRegister(VReg))
       if (--NumUseInst == 0)
         return false;
 
     if (I->modifiesRegister(AMDGPU::EXEC, TRI))
       return true;
   }
 }
+
+MachineInstr *SIInstrInfo::createPHIDestinationCopy(
+    MachineBasicBlock &MBB, MachineBasicBlock::iterator LastPHIIt,
+    const DebugLoc &DL, Register Src, Register Dst) const {
+  auto Cur = MBB.begin();
+  do {
+    if (!Cur->isPHI() && Cur->readsRegister(Dst))
+      return BuildMI(MBB, Cur, DL, get(TargetOpcode::COPY), Dst).addReg(Src);
+    ++Cur;
+  } while (Cur != MBB.end() && Cur != LastPHIIt);
+
+  return TargetInstrInfo::createPHIDestinationCopy(MBB, LastPHIIt, DL, Src,
+                                                   Dst);
+}
+
+MachineInstr *SIInstrInfo::createPHISourceCopy(
+    MachineBasicBlock &MBB, MachineBasicBlock::iterator InsPt,
+    const DebugLoc &DL, Register Src, Register SrcSubReg, Register Dst) const {
+  if (InsPt != MBB.end() && InsPt->isPseudo() && InsPt->definesRegister(Src)) {
+    InsPt++;
+    return BuildMI(MBB, InsPt, InsPt->getDebugLoc(),
+                   get(AMDGPU::S_MOV_B64_term), Dst)
+        .addReg(Src, 0, SrcSubReg)
+        .addReg(AMDGPU::EXEC, RegState::Implicit);
+  }
+  return TargetInstrInfo::createPHISourceCopy(MBB, InsPt, DL, Src, SrcSubReg,
+                                              Dst);
+}

llvm/lib/Target/AMDGPU/SILowerControlFlow.cpp

void SILowerControlFlow::emitIf(MachineInstr &MI) {
   MachineBasicBlock::iterator I(&MI);
 
   MachineOperand &SaveExec = MI.getOperand(0);
   MachineOperand &Cond = MI.getOperand(1);
   assert(SaveExec.getSubReg() == AMDGPU::NoSubRegister &&
          Cond.getSubReg() == AMDGPU::NoSubRegister);
 
   Register SaveExecReg = SaveExec.getReg();
+  MachineBasicBlock::iterator J = std::next(I);
+  if (J != MBB.end() && J->getOpcode() == AMDGPU::S_MOV_B64_term &&
+      J->getOperand(1).isReg() && J->getOperand(1).getReg() == SaveExecReg) {
+    SaveExecReg = J->getOperand(0).getReg();
+    J->eraseFromParent();
+  }
 
   MachineOperand &ImpDefSCC = MI.getOperand(4);
   assert(ImpDefSCC.getReg() == AMDGPU::SCC && ImpDefSCC.isDef());
 
   // If there is only one use of save exec register and that use is SI_END_CF,
   // we can optimize SI_IF by returning the full saved exec mask instead of
   // just cleared bits.
   bool SimpleIf = isSimpleIf(MI, MRI, TII);
if (LIS) {
     LIS->InsertMachineInstrInMaps(*Branch);
   }
 
   MI.eraseFromParent();
 }
 
 void SILowerControlFlow::emitEndCf(MachineInstr &MI) {
   MachineBasicBlock &MBB = *MI.getParent();
+  MachineRegisterInfo &MRI = MBB.getParent()->getRegInfo();
+  unsigned CFMask = MI.getOperand(0).getReg();
+  MachineInstr *Def = MRI.getUniqueVRegDef(CFMask);
   const DebugLoc &DL = MI.getDebugLoc();
 
-  MachineBasicBlock::iterator InsPt = MBB.begin();
-  MachineInstr *NewMI =
-      BuildMI(MBB, InsPt, DL, TII->get(OrOpc), Exec)
+  MachineBasicBlock::iterator InsPt =
+      Def && Def->getParent() == &MBB ? std::next(MachineBasicBlock::iterator(Def))
+                               : MBB.begin();
+  MachineInstr *NewMI = BuildMI(MBB, InsPt, DL, TII->get(OrOpc), Exec)
                             .addReg(Exec)
                             .add(MI.getOperand(0));
 
   if (LIS)
     LIS->ReplaceMachineInstrInMaps(MI, *NewMI);
 
   MI.eraseFromParent();
 
   if (LIS)
     LIS->handleMove(*NewMI);

llvm/test/CodeGen/AMDGPU/phi-elimination-assertion.mir

body:             |
   bb.3:
     dead %3:sreg_32_xm0 = PHI undef %2, %bb.2, undef %1, %bb.1
     %4:sreg_32_xm0 = PHI %2, %bb.2, %1, %bb.1
     S_NOP 0, implicit %4
 ...
 
 # CHECK-LABEL: name:            foo
 # CHECK:   bb.3:
-# CHECK-NEXT:     %3:sreg_32_xm0 = COPY killed %4
 # CHECK-NEXT:     dead %2:sreg_32_xm0 = IMPLICIT_DEF
+# CHECK-NEXT:     %3:sreg_32_xm0 = COPY killed %4
 # CHECK-NEXT:     S_NOP 0, implicit killed %3
 
 
 ################################################################################
 # Similar test as above, but with swapped order for the PHI nodes.
 # With this PHI node order we did not hit the assert, but we used to get
 #
 #  bb.3:

llvm/test/CodeGen/AMDGPU/phi-elimination-end-cf.mir

+# RUN: llc -mtriple amdgcn -run-pass livevars -run-pass phi-node-elimination -verify-machineinstrs -o - %s | FileCheck %s
+
+# CHECK-LABEL:  phi-cf-test
+# CHECK: bb.0:
+# CHECK:     [[COND:%[0-9]+]]:sreg_64 = V_CMP_EQ_U32_e64
+# CHECK:     [[IF_SOURCE0:%[0-9]+]]:sreg_64 = SI_IF [[COND]], %bb.1, implicit-def dead $exec, implicit-def dead $scc, implicit $exec
+# CHECK:     [[IF_INPUT_REG:%[0-9]+]]:sreg_64 =  S_MOV_B64_term killed [[IF_SOURCE0]], implicit $exec
+
+# CHECK: bb.1:
+# CHECK:     [[END_CF_ARG:%[0-9]+]]:sreg_64 = COPY killed [[IF_INPUT_REG]]
+# CHECK:     SI_END_CF killed [[END_CF_ARG]], implicit-def dead $exec, implicit-def dead $scc, implicit $exec
+
+# CHECK: bb.2:
+# CHECK:     [[IF_SOURCE1:%[0-9]+]]:sreg_64 = SI_IF [[COND]], %bb.1, implicit-def dead $exec, implicit-def dead $scc, implicit $exec
+# CHECK:     [[IF_INPUT_REG]]:sreg_64 =  S_MOV_B64_term killed [[IF_SOURCE1]], implicit $exec
+
+
+...
+---
+name:            phi-cf-test
+tracksRegLiveness: true
+body:             |
+
+  bb.0:
+    successors: %bb.3(0x40000000), %bb.2(0x40000000)
+    liveins: $vgpr0
+
+    %5:vgpr_32(s32) = COPY $vgpr0
+    %0:sreg_64 = V_CMP_EQ_U32_e64 0, %5(s32), implicit $exec
+    %18:vgpr_32 = V_MOV_B32_e32 0, implicit $exec
+    %22:sreg_64 = SI_IF %0, %bb.2, implicit-def dead $exec, implicit-def dead $scc, implicit $exec
+    S_BRANCH %bb.3
+
+  bb.2:
+    successors: %bb.3(0x80000000)
+
+    %24:sreg_64 = PHI %20, %bb.3, %22, %bb.0
+    %23:vgpr_32 = PHI %19, %bb.3, %18, %bb.0
+    SI_END_CF %24, implicit-def dead $exec, implicit-def dead $scc, implicit $exec
+    %3:vgpr_32, dead %10:sreg_64 = nsw V_ADD_I32_e64 1, %23, 0, implicit $exec
+
+  bb.3:
+    successors: %bb.3(0x40000000), %bb.2(0x40000000)
+
+    %4:vgpr_32 = PHI %19, %bb.3, %3, %bb.2, %18, %bb.0
+    %15:sreg_32_xm0 = S_MOV_B32 61440
+    %16:sreg_32_xm0 = S_MOV_B32 -1
+    %17:sreg_128 = REG_SEQUENCE undef %14:sreg_32_xm0, %subreg.sub0, undef %12:sreg_32_xm0, %subreg.sub1, %16, %subreg.sub2, %15, %subreg.sub3
+    BUFFER_STORE_DWORD_OFFSET %4, %17, 0, 0, 0, 0, 0, 0, implicit $exec :: (volatile store 4 into `i32 addrspace(1)* undef`, addrspace 1)
+    %19:vgpr_32 = COPY %4
+    %20:sreg_64 = SI_IF %0, %bb.2, implicit-def dead $exec, implicit-def dead $scc, implicit $exec
+    S_BRANCH %bb.3
+
+...