[GISel]: Translate phi into generic G_PHI instruction

[aditya_nandakumar]

Summary

Translate phi instructions into generic G_PHI instructions.
This has the same semantic as PHI but has types for operands.
This lets us verify that the G_PHI has compatible types for all operands.
This also allows specifying legalization actions for weird PHI types.

[qcolombet]

Hi Aditya,

Looks mostly good to me.
Could you add a test case for the "verifier" like diagnostic you've added?

The RegisterBankInfo change seems strange to me. See inline comment.

Cheers,
-Quentin

lib/Target/AArch64/AArch64RegisterBankInfo.cpp

423–424

We should need to do that.
Could you describe what happen if you don't?

[aditya_nandakumar]

lib/Target/AArch64/AArch64RegisterBankInfo.cpp

423–424

When it returns the best mapping, it creates for NumOperands (say with 2 PHI values - it's 5). Then it fails the verification of the best mapping.
assert(NumOperands == (isCopyLike(MI) ? 1 : MI.getNumOperands()) && "NumOperands must match, see constructor");
I made the change so G_PHI would have been treated as it were a PHI.

[aditya_nandakumar]

Added test for G_PHI verifier.

[qcolombet]

lib/Target/AArch64/AArch64RegisterBankInfo.cpp

423–424

Ah right, we want to use the generic getInstrMappingImpl, but now G_PHI falls into the isPreISelGenericOpcode category whereas PHI did not.

That being said, all the targets will have the exact same problem therefore, long term, we probably want to have some kind of generic method for this check. Anyhow, that's not really a problem for now and actually we could just skip the check and that would work (as in always calling getInstrMappingImpl and check if the Mapping is valid), though it would a waste of compile time.

Anyway, the current change makes sense and I'd expect you'd need to do the same for x86, amdgpu, and arm.

test/Verifier/test_g_phi.mir

2

Could you add a FileCheck to check we issue the expected error?

29

Could you add a comment on what this test is checking?

[aditya_nandakumar]

Updated based on feedback.

[qcolombet]

LGTM

[aditya_nandakumar]

Committed in r311596

include/llvm/CodeGen/MachineInstr.h

public:
   /// A DBG_VALUE is indirect iff the first operand is a register and
   /// the second operand is an immediate.
   bool isIndirectDebugValue() const {
     return isDebugValue()
       && getOperand(0).isReg()
       && getOperand(1).isImm();
   }
 
-  bool isPHI() const { return getOpcode() == TargetOpcode::PHI; }
+  bool isPHI() const {
+    return getOpcode() == TargetOpcode::PHI ||
+           getOpcode() == TargetOpcode::G_PHI;
+  }
   bool isKill() const { return getOpcode() == TargetOpcode::KILL; }
   bool isImplicitDef() const { return getOpcode()==TargetOpcode::IMPLICIT_DEF; }
   bool isInlineAsm() const { return getOpcode() == TargetOpcode::INLINEASM; }
 
   bool isMSInlineAsm() const {
     return getOpcode() == TargetOpcode::INLINEASM && getInlineAsmDialect();
   }
 
public:
   /// to be eliminated during register allocation (such as copy-like
   /// instructions), or if this instruction doesn't have an execution-time cost.
   bool isTransient() const {
     switch (getOpcode()) {
     default:
       return isMetaInstruction();
     // Copy-like instructions are usually eliminated during register allocation.
     case TargetOpcode::PHI:
+    case TargetOpcode::G_PHI:
     case TargetOpcode::COPY:
     case TargetOpcode::INSERT_SUBREG:
     case TargetOpcode::SUBREG_TO_REG:
     case TargetOpcode::REG_SEQUENCE:
       return true;
     }
   }
 

include/llvm/Target/GenericOpcodes.td

 }
 
 def G_IMPLICIT_DEF : Instruction {
   let OutOperandList = (outs type0:$dst);
   let InOperandList = (ins);
   let hasSideEffects = 0;
 }
 
+def G_PHI : Instruction {
+  let OutOperandList = (outs type0:$dst);
+  let InOperandList = (ins variable_ops);
+  let hasSideEffects = 0;
+}
+
 def G_FRAME_INDEX : Instruction {
   let OutOperandList = (outs type0:$dst);
   let InOperandList = (ins unknown:$src2);
   let hasSideEffects = 0;
 }
 
 def G_GLOBAL_VALUE : Instruction {
   let OutOperandList = (outs type0:$dst);

include/llvm/Target/TargetOpcodes.def

 HANDLE_TARGET_OPCODE(G_OR)
 
 /// Generic bitwise exclusive-or instruction.
 HANDLE_TARGET_OPCODE(G_XOR)
 
 
 HANDLE_TARGET_OPCODE(G_IMPLICIT_DEF)
 
+/// Generic PHI instruction with types.
+HANDLE_TARGET_OPCODE(G_PHI)
+
 /// Generic instruction to materialize the address of an alloca or other
 /// stack-based object.
 HANDLE_TARGET_OPCODE(G_FRAME_INDEX)
 
 /// Generic reference to global value.
 HANDLE_TARGET_OPCODE(G_GLOBAL_VALUE)
 
 /// Generic instruction to extract blocks of bits from the register given

lib/CodeGen/GlobalISel/IRTranslator.cpp

MIRBuilder.buildInstr(TargetOpcode::G_SHUFFLE_VECTOR)
       .addUse(getOrCreateVReg(*U.getOperand(0)))
       .addUse(getOrCreateVReg(*U.getOperand(1)))
       .addUse(getOrCreateVReg(*U.getOperand(2)));
   return true;
 }
 
 bool IRTranslator::translatePHI(const User &U, MachineIRBuilder &MIRBuilder) {
   const PHINode &PI = cast<PHINode>(U);
-  auto MIB = MIRBuilder.buildInstr(TargetOpcode::PHI);
+  auto MIB = MIRBuilder.buildInstr(TargetOpcode::G_PHI);
   MIB.addDef(getOrCreateVReg(PI));
 
   PendingPHIs.emplace_back(&PI, MIB.getInstr());
   return true;
 }
 
 void IRTranslator::finishPendingPhis() {
   for (std::pair<const PHINode *, MachineInstr *> &Phi : PendingPHIs) {

lib/CodeGen/MachineVerifier.cpp

void MachineVerifier::visitMachineInstrBefore(const MachineInstr *MI) {
   case TargetOpcode::G_LOAD:
   case TargetOpcode::G_STORE:
     // Generic loads and stores must have a single MachineMemOperand
     // describing that access.
     if (!MI->hasOneMemOperand())
       report("Generic instruction accessing memory must have one mem operand",
              MI);
     break;
+  case TargetOpcode::G_PHI: {
+    LLT DstTy = MRI->getType(MI->getOperand(0).getReg());
+    if (!DstTy.isValid() ||
+        !std::all_of(MI->operands_begin() + 1, MI->operands_end(),
+                     [this, &DstTy](const MachineOperand &MO) {
+                       if (!MO.isReg())
+                         return true;
+                       LLT Ty = MRI->getType(MO.getReg());
+                       if (!Ty.isValid() || (Ty != DstTy))
+                         return false;
+                       return true;
+                     }))
+      report("Generic Instruction G_PHI has operands with incompatible/missing "
+             "types",
+             MI);
+    break;
+  }
   case TargetOpcode::STATEPOINT:
     if (!MI->getOperand(StatepointOpers::IDPos).isImm() ||
         !MI->getOperand(StatepointOpers::NBytesPos).isImm() ||
         !MI->getOperand(StatepointOpers::NCallArgsPos).isImm())
       report("meta operands to STATEPOINT not constant!", MI);
     break;
 
     auto VerifyStackMapConstant = [&](unsigned Offset) {

lib/Target/AArch64/AArch64InstructionSelector.cpp

bool AArch64InstructionSelector::select(MachineInstr &I) const {
   assert(I.getParent() && "Instruction should be in a basic block!");
   assert(I.getParent()->getParent() && "Instruction should be in a function!");
 
   MachineBasicBlock &MBB = *I.getParent();
   MachineFunction &MF = *MBB.getParent();
   MachineRegisterInfo &MRI = MF.getRegInfo();
 
   unsigned Opcode = I.getOpcode();
-  if (!isPreISelGenericOpcode(I.getOpcode())) {
+  // G_PHI requires same handling as PHI
+  if (!isPreISelGenericOpcode(Opcode) || Opcode == TargetOpcode::G_PHI) {
     // Certain non-generic instructions also need some special handling.
 
     if (Opcode ==  TargetOpcode::LOAD_STACK_GUARD)
       return constrainSelectedInstRegOperands(I, TII, TRI, RBI);
 
-    if (Opcode == TargetOpcode::PHI) {
+    if (Opcode == TargetOpcode::PHI || Opcode == TargetOpcode::G_PHI) {
       const unsigned DefReg = I.getOperand(0).getReg();
       const LLT DefTy = MRI.getType(DefReg);
 
       const TargetRegisterClass *DefRC = nullptr;
       if (TargetRegisterInfo::isPhysicalRegister(DefReg)) {
         DefRC = TRI.getRegClass(DefReg);
       } else {
         const RegClassOrRegBank &RegClassOrBank =
             MRI.getRegClassOrRegBank(DefReg);
 
         DefRC = RegClassOrBank.dyn_cast<const TargetRegisterClass *>();
         if (!DefRC) {
           if (!DefTy.isValid()) {
             DEBUG(dbgs() << "PHI operand has no type, not a gvreg?\n");
             return false;
           }
           const RegisterBank &RB = *RegClassOrBank.get<const RegisterBank *>();
           DefRC = getRegClassForTypeOnBank(DefTy, RB, RBI);
           if (!DefRC) {
             DEBUG(dbgs() << "PHI operand has unexpected size/bank\n");
             return false;
           }
         }
       }
+      I.setDesc(TII.get(TargetOpcode::PHI));
 
       return RBI.constrainGenericRegister(DefReg, *DefRC, MRI);
     }
 
     if (I.isCopy())
       return selectCopy(I, TII, MRI, TRI, RBI);
 
     return true;

lib/Target/AArch64/AArch64LegalizerInfo.cpp

AArch64LegalizerInfo::AArch64LegalizerInfo() {
   const LLT s64 = LLT::scalar(64);
   const LLT v2s32 = LLT::vector(2, 32);
   const LLT v4s32 = LLT::vector(4, 32);
   const LLT v2s64 = LLT::vector(2, 64);
 
   for (auto Ty : {p0, s1, s8, s16, s32, s64})
     setAction({G_IMPLICIT_DEF, Ty}, Legal);
 
+  for (auto Ty : {s16, s32, s64})
+    setAction({G_PHI, Ty}, Legal);
+
   for (unsigned BinOp : {G_ADD, G_SUB, G_MUL, G_AND, G_OR, G_XOR, G_SHL}) {
     // These operations naturally get the right answer when used on
     // GPR32, even if the actual type is narrower.
     for (auto Ty : {s32, s64, v2s32, v4s32, v2s64})
       setAction({BinOp, Ty}, Legal);
 
     for (auto Ty : {s1, s8, s16})
       setAction({BinOp, Ty}, WidenScalar);

lib/Target/AArch64/AArch64RegisterBankInfo.cpp

 const RegisterBankInfo::InstructionMapping &
 AArch64RegisterBankInfo::getInstrMapping(const MachineInstr &MI) const {
   const unsigned Opc = MI.getOpcode();
   const MachineFunction &MF = *MI.getParent()->getParent();
   const MachineRegisterInfo &MRI = MF.getRegInfo();
 
   // Try the default logic for non-generic instructions that are either copies
   // or already have some operands assigned to banks.
-  if (!isPreISelGenericOpcode(Opc)) {
+  if (!isPreISelGenericOpcode(Opc) ||
+      Opc == TargetOpcode::G_PHI) {
     const RegisterBankInfo::InstructionMapping &Mapping =
         getInstrMappingImpl(MI);
     if (Mapping.isValid())
       return Mapping;
   }
 
   switch (Opc) {
     // G_{F|S|U}REM are not listed because they are not legal.

lib/Target/ARM/ARMRegisterBankInfo.cpp

 }
 
 const RegisterBankInfo::InstructionMapping &
 ARMRegisterBankInfo::getInstrMapping(const MachineInstr &MI) const {
   auto Opc = MI.getOpcode();
 
   // Try the default logic for non-generic instructions that are either copies
   // or already have some operands assigned to banks.
-  if (!isPreISelGenericOpcode(Opc)) {
+  if (!isPreISelGenericOpcode(Opc) || Opc == TargetOpcode::G_PHI) {
     const InstructionMapping &Mapping = getInstrMappingImpl(MI);
     if (Mapping.isValid())
       return Mapping;
   }
 
   using namespace TargetOpcode;
 
   const MachineFunction &MF = *MI.getParent()->getParent();

lib/Target/X86/X86RegisterBankInfo.cpp

 const RegisterBankInfo::InstructionMapping &
 X86RegisterBankInfo::getInstrMapping(const MachineInstr &MI) const {
   const MachineFunction &MF = *MI.getParent()->getParent();
   const MachineRegisterInfo &MRI = MF.getRegInfo();
   auto Opc = MI.getOpcode();
 
   // Try the default logic for non-generic instructions that are either copies
   // or already have some operands assigned to banks.
-  if (!isPreISelGenericOpcode(Opc)) {
+  if (!isPreISelGenericOpcode(Opc) || Opc == TargetOpcode::G_PHI) {
     const InstructionMapping &Mapping = getInstrMappingImpl(MI);
     if (Mapping.isValid())
       return Mapping;
   }
 
   switch (Opc) {
   case TargetOpcode::G_ADD:
   case TargetOpcode::G_SUB:

test/CodeGen/AArch64/GlobalISel/arm64-irtranslator.ll

 ; CHECK: %[[regretc100:[0-9]+]](s32) = G_ADD %0, %[[reg1]]
 ; CHECK: G_BR %[[BB_RET]]
 ;
 ; CHECK: [[BB_CASE200]]:
 ; CHECK-NEXT: successors: %[[BB_RET]](0x80000000)
 ; CHECK: %[[regretc200:[0-9]+]](s32) = G_ADD %0, %[[reg2]]
 ;
 ; CHECK: [[BB_RET]]:
-; CHECK-NEXT: %[[regret:[0-9]+]](s32) = PHI %[[regretdefault]](s32), %[[BB_DEFAULT]], %[[regretc100]](s32), %[[BB_CASE100]]
+; CHECK-NEXT: %[[regret:[0-9]+]](s32) = G_PHI %[[regretdefault]](s32), %[[BB_DEFAULT]], %[[regretc100]](s32), %[[BB_CASE100]]
 ; CHECK:  %w0 = COPY %[[regret]](s32)
 ; CHECK:  RET_ReallyLR implicit %w0
 ;
 define i32 @switch(i32 %argc) {
 entry:
   switch i32 %argc, label %default [
     i32 100, label %case100
     i32 200, label %case200

 ; CHECK-NEXT: successors: %{{bb.[0-9]+.next}}(0x40000000), %[[NOTCASE1_BLOCK:bb.[0-9]+.entry]](0x40000000)
 ; CHECK: [[NOTCASE1_BLOCK]]:
 ; CHECK-NEXT: successors: %{{bb.[0-9]+.other}}(0x40000000), %[[NOTCASE57_BLOCK:bb.[0-9]+.entry]](0x40000000)
 ; CHECK: [[NOTCASE57_BLOCK]]:
 ; CHECK-NEXT: successors: %[[PHI_BLOCK:bb.[0-9]+.phi.block]](0x80000000)
 ; CHECK: G_BR %[[PHI_BLOCK]]
 ;
 ; CHECK: [[PHI_BLOCK]]:
-; CHECK-NEXT: PHI %{{.*}}(s32), %[[NOTCASE57_BLOCK:bb.[0-9]+.entry]], %{{.*}}(s32),
+; CHECK-NEXT: G_PHI %{{.*}}(s32), %[[NOTCASE57_BLOCK:bb.[0-9]+.entry]], %{{.*}}(s32),
 ;
 define i32 @test_cfg_remap(i32 %in) {
 entry:
   switch i32 %in, label %phi.block [i32 1, label %next
                                     i32 57, label %other]
 
 next:
   br label %phi.block
 
 other:
   ret i32 undef
 
 phi.block:
   %res = phi i32 [1, %entry], [42, %next]
   ret i32 %res
 }
 
 ; CHECK-LABEL: name: test_cfg_remap_multiple_preds
-; CHECK: PHI [[ENTRY:%.*]](s32), %bb.{{[0-9]+}}.entry, [[ENTRY]](s32), %bb.{{[0-9]+}}.entry
+; CHECK: G_PHI [[ENTRY:%.*]](s32), %bb.{{[0-9]+}}.entry, [[ENTRY]](s32), %bb.{{[0-9]+}}.entry
 define i32 @test_cfg_remap_multiple_preds(i32 %in) {
 entry:
   switch i32 %in, label %odd [i32 1, label %next
                               i32 57, label %other
                               i32 128, label %phi.block
                               i32 256, label %phi.block]
 odd:
   unreachable

 ; CHECK:     G_BR %[[FALSE:bb\.[0-9]+.false]]
 
 ; CHECK: [[TRUE]]:
 ; CHECK:     [[RES1:%[0-9]+]](s32) = G_LOAD
 
 ; CHECK: [[FALSE]]:
 ; CHECK:     [[RES2:%[0-9]+]](s32) = G_LOAD
 
-; CHECK:     [[RES:%[0-9]+]](s32) = PHI [[RES1]](s32), %[[TRUE]], [[RES2]](s32), %[[FALSE]]
+; CHECK:     [[RES:%[0-9]+]](s32) = G_PHI [[RES1]](s32), %[[TRUE]], [[RES2]](s32), %[[FALSE]]
 ; CHECK:     %w0 = COPY [[RES]]
 define i32 @test_phi(i32* %addr1, i32* %addr2, i1 %tst) {
   br i1 %tst, label %true, label %false
 
 true:
   %res1 = load i32, i32* %addr1
   br label %end
 

test/CodeGen/AArch64/GlobalISel/select-phi.mir

+# RUN: llc -mtriple=aarch64-unknown-unknown -o - -global-isel -verify-machineinstrs -run-pass=instruction-select %s | FileCheck %s
+--- |
+  ; ModuleID = '/tmp/test.ll'
+  source_filename = "/tmp/test.ll"
+  target datalayout = "e-m:e-i8:8:32-i16:16:32-i64:64-i128:128-n32:64-S128"
+  target triple = "aarch64-unknown-unknown"
+  
+  define i32 @test_phi(i32 %argc) {
+  entry:
+    %cmp = icmp ugt i32 %argc, 0
+    br i1 %cmp, label %case1, label %case2
+  
+  case1:                                            ; preds = %entry
+    %tmp1 = add i32 %argc, 1
+    br label %return
+  
+  case2:                                            ; preds = %entry
+    %tmp2 = add i32 %argc, 2
+    br label %return
+  
+  return:                                           ; preds = %case2, %case1
+    %res = phi i32 [ %tmp1, %case1 ], [ %tmp2, %case2 ]
+    ret i32 %res
+  }
+
+...
+---
+name:            test_phi
+alignment:       2
+exposesReturnsTwice: false
+legalized:       true
+regBankSelected: true
+selected:        false
+tracksRegLiveness: true
+registers:       
+  - { id: 0, class: gpr, preferred-register: '' }
+  - { id: 1, class: gpr, preferred-register: '' }
+  - { id: 2, class: gpr, preferred-register: '' }
+  - { id: 3, class: gpr, preferred-register: '' }
+  - { id: 4, class: gpr, preferred-register: '' }
+  - { id: 5, class: gpr, preferred-register: '' }
+  - { id: 6, class: gpr, preferred-register: '' }
+  - { id: 7, class: gpr, preferred-register: '' }
+  - { id: 8, class: gpr, preferred-register: '' }
+liveins:         
+body:             |
+  bb.1.entry:
+    successors: %bb.2.case1(0x40000000), %bb.3.case2(0x40000000)
+    liveins: %w0
+    ; CHECK-LABEL: name: test_phi
+    ; CHECK: [[RES:%.*]] = PHI
+  
+    %0(s32) = COPY %w0
+    %1(s32) = G_CONSTANT i32 0
+    %3(s32) = G_CONSTANT i32 1
+    %5(s32) = G_CONSTANT i32 2
+    %8(s32) = G_ICMP intpred(ugt), %0(s32), %1
+    %2(s1) = G_TRUNC %8(s32)
+    G_BRCOND %2(s1), %bb.2.case1
+    G_BR %bb.3.case2
+  
+  bb.2.case1:
+    successors: %bb.4.return(0x80000000)
+  
+    %4(s32) = G_ADD %0, %3
+    G_BR %bb.4.return
+  
+  bb.3.case2:
+    successors: %bb.4.return(0x80000000)
+  
+    %6(s32) = G_ADD %0, %5
+  
+  bb.4.return:
+    %7(s32) = G_PHI %4(s32), %bb.2.case1, %6(s32), %bb.3.case2
+    %w0 = COPY %7(s32)
+    RET_ReallyLR implicit %w0
+
+...

test/Verifier/test_g_phi.mir

+#RUN: not llc -mtriple=aarch64-unknown-unknown -o - -global-isel -run-pass=legalizer -verify-machineinstrs %s 2>&1 | FileCheck %s
+--- |
+  ; ModuleID = 'test.ll'
+  source_filename = "test.ll"
+  target datalayout = "e-m:e-i8:8:32-i16:16:32-i64:64-i128:128-n32:64-S128"
+  target triple = "aarch64-unknown-unknown"
+  
+  define i32 @test_phi(i32 %argc) {
+  entry:
+    %cmp = icmp ugt i32 %argc, 0
+    br i1 %cmp, label %case1, label %case2
+  
+  case1:                                            ; preds = %entry
+    %tmp11 = add i32 %argc, 1
+    br label %return
+  
+  case2:                                            ; preds = %entry
+    %tmp22 = add i32 %argc, 2
+    br label %return
+  
+  return:                                           ; preds = %case2, %case1
+    %res = phi i32 [ %tmp11, %case1 ], [ %tmp22, %case2 ]
+    ret i32 %res
+  }
+
+...
+---
+name:            test_phi
+legalized:       true
+regBankSelected: false
+selected:        false
+tracksRegLiveness: true
+registers:       
+  - { id: 0, class: _, preferred-register: '' }
+  - { id: 1, class: _, preferred-register: '' }
+  - { id: 2, class: _, preferred-register: '' }
+  - { id: 3, class: _, preferred-register: '' }
+  - { id: 4, class: _, preferred-register: '' }
+  - { id: 5, class: _, preferred-register: '' }
+  - { id: 6, class: _, preferred-register: '' }
+  - { id: 7, class: _, preferred-register: '' }
+  - { id: 8, class: _, preferred-register: '' }
+  - { id: 9, class: _, preferred-register: '' }
+liveins:         
+body:             |
+  bb.1.entry:
+    successors: %bb.2.case1(0x40000000), %bb.3.case2(0x40000000)
+    liveins: %w0
+    ; This test makes sure that the Verifier catches G_PHI with mismatching types.
+    ; CHECK: Bad machine code: Generic Instruction G_PHI has operands with incompatible/missing types
+  
+    %0(s32) = COPY %w0
+    %1(s32) = G_CONSTANT i32 0
+    %3(s32) = G_CONSTANT i32 1
+    %5(s32) = G_CONSTANT i32 2
+    %8(s32) = G_ICMP intpred(ugt), %0(s32), %1
+    %2(s1) = G_TRUNC %8(s32)
+    G_BRCOND %2(s1), %bb.2.case1
+    G_BR %bb.3.case2
+  
+  bb.2.case1:
+    successors: %bb.4.return(0x80000000)
+  
+    %4(s32) = G_ADD %0, %3
+    %9(s16) = G_TRUNC %4(s32)
+    G_BR %bb.4.return
+  
+  bb.3.case2:
+    successors: %bb.4.return(0x80000000)
+  
+    %6(s32) = G_ADD %0, %5
+  
+  bb.4.return:
+    %7(s32) = G_PHI %9(s16), %bb.2.case1, %6(s32), %bb.3.case2
+    %w0 = COPY %7(s32)
+    RET_ReallyLR implicit %w0
+
+...