[GISel]: Legalize G_PHIs

[aditya_nandakumar]

Summary

Implemented WidenScalar for G_PHI.

[qcolombet]

Hi Aditya,

Looks mostly good.
Couple of comments inlined + we need more tests and reduce them (e.g., remove the frameInfo stuff and so on).

Cheers,
-Quentin

lib/CodeGen/GlobalISel/LegalizerHelper.cpp

668

NonTermIt may not be an instruction, thus we cannot dereference it.

• Use setInsertPt instead.
• Add a test case with an empty predecessor block

676

No bracket for one line block

690

Can't we merge the two loops and get rid of the temporary NewRegs.

[aditya_nandakumar]

Updated based on Quentin's feedback.

[qcolombet]

Hi Aditya,

The code looks good to me. Minor nitpicks inlined.

Regarding the test cases, could you:

• Add a test case with a cycle on a phi (e.g., a = phi a)
• Add a test case with an empty predecessor
• Add a comment before every test case explaining what we are checking
• Add a test case for s8
• Add a test case with def feeding into two different phis:
  • In the same destination block
    • with the same type
    • with different types
  • In different basic block (one on the true branch, one on the false branch)
    • with the same type
    • with different types

I know that most of these test cases are going to exercise the same code path, but I still like to add more and stranger tests to make sure still things pass if we change the implementation underneath. For instance if we start doing CSE when creating the EXTs.

Cheers,
-Quentin

include/llvm/CodeGen/GlobalISel/MachineIRBuilder.h

433

Add a newline

lib/CodeGen/GlobalISel/MachineIRBuilder.cpp

353

Formatting looks weird. Is this clang-formatted?

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

52

You can get rid of the frameInfo, fixedStack, stack and constants sections

[aditya_nandakumar]

I see that the test cases I thought I updated (and added) are not there (and can't find them in my tree). I'll recreate them and add them to the review again.

lib/CodeGen/GlobalISel/MachineIRBuilder.cpp

353

Yup. This is clang-formatted..

[aditya_nandakumar]

Updated with removed nitpicks, more tests.

[qcolombet]

I miss these test cases:

• Add a test case with def feeding into two different phis:
  • In the same destination block
  • In different basic block (one on the true branch, one on the false branch)

In other words:
bb1:
def =
...
bb2:
... = phi def
... = phi def

and
def =
...
condbr bb2, b33
bb2
... = phi def
bb3
... = phi def

[aditya_nandakumar]

Added 2 more tests (This caught a bug where we broke the invariant of PHI being the first in the BB). Fixed.

[qcolombet]

LGTM.

Few more nitpicks, no need for more reviews.

lib/CodeGen/GlobalISel/LegalizerHelper.cpp

687

Haha, nice catch!

How did this work previously?!
Wouldn't we insert the G_TRUNC before the G_PHI?

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

122

Is there any interest in keeping the IR around?
IMHO, there is not, so I would just go with void funcN(void) { ret void }. (You'll need to remove the references to the IR label from the MI BBs.)

336

Could you check that we insert the G_TRUNC at the right place?

403

Ditto.

[aditya_nandakumar]

lib/CodeGen/GlobalISel/LegalizerHelper.cpp

687

Previously I only had one G_PHI at a time in a test. If we setInsertPt to MI (the G_PHI being legalized) and then
Builder.buildInstr(G_PHI) + arguments
Builder.buildInstr(G_TRUNC),
we would have been fine as G_PHI is still the first instruction in the BB.

With 2 G_PHIs, we would end up with
G_PHI(s16)
G_TRUNC
G_PHI(s16)
G_TRUNC
Which is obviously wrong - so the extra test case exposed this bug :)

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

122

My only use of the IR is that I find it easier to read LLVM-IR than MIR to see what the function is doing. That said, in this test (with a test description), we shouldn't need it. I'll clean this up before pushing.

[aditya_nandakumar]

committed in r311763.

include/llvm/CodeGen/GlobalISel/MachineIRBuilder.h

class MachineIRBuilder {
   }
 
   void addUsesFromArgs(MachineInstrBuilder &MIB) { }
   template<typename UseArgTy, typename ... UseArgsTy>
   void addUsesFromArgs(MachineInstrBuilder &MIB, UseArgTy &&Arg1, UseArgsTy &&... Args) {
     addUseFromArg(MIB, Arg1);
     addUsesFromArgs(MIB, std::forward<UseArgsTy>(Args)...);
   }
+  unsigned getRegFromArg(unsigned Reg) { return Reg; }
+  unsigned getRegFromArg(const MachineInstrBuilder &MIB) {
+    return MIB->getOperand(0).getReg();
+  }
+
 public:
   /// Some constructors for easy use.
   MachineIRBuilder() = default;
   MachineIRBuilder(MachineFunction &MF) { setMF(MF); }
   MachineIRBuilder(MachineInstr &MI)
       : MachineIRBuilder(*MI.getParent()->getParent()) {
     setInstr(MI);
   }
public:
   /// each element is extended individually.
   ///
   /// \pre setBasicBlock or setMI must have been called.
   /// \pre \p Res must be a generic virtual register with scalar or vector type.
   /// \pre \p Op must be a generic virtual register with scalar or vector type.
   /// \pre \p Op must be smaller than \p Res
   ///
   /// \return The newly created instruction.
+
   MachineInstrBuilder buildAnyExt(unsigned Res, unsigned Op);
+  template <typename DstType, typename ArgType>
+  MachineInstrBuilder buildAnyExt(DstType &&Res, ArgType &&Arg) {
+    return buildAnyExt(getDestFromArg(Res), getRegFromArg(Arg));
+  }
 
   /// Build and insert \p Res<def> = G_SEXT \p Op
   ///
   /// G_SEXT produces a register of the specified width, with bits 0 to
   /// sizeof(\p Ty) * 8 set to \p Op. The remaining bits are duplicated from the
   /// high bit of \p Op (i.e. 2s-complement sign extended).
   ///
   /// \pre setBasicBlock or setMI must have been called.
public:
   /// Build and insert \p Res<def> = G_ZEXT \p Op, \p Res = G_TRUNC \p Op, or
   /// \p Res = COPY \p Op depending on the differing sizes of \p Res and \p Op.
   ///  ///
   /// \pre setBasicBlock or setMI must have been called.
   /// \pre \p Res must be a generic virtual register with scalar or vector type.
   /// \pre \p Op must be a generic virtual register with scalar or vector type.
   ///
   /// \return The newly created instruction.
   MachineInstrBuilder buildZExtOrTrunc(unsigned Res, unsigned Op);
 
+  // Build and insert \p Res<def> = G_ANYEXT \p Op, \p Res = G_TRUNC \p Op, or
+  /// \p Res = COPY \p Op depending on the differing sizes of \p Res and \p Op.
+  ///  ///
+  /// \pre setBasicBlock or setMI must have been called.
+  /// \pre \p Res must be a generic virtual register with scalar or vector type.
+  /// \pre \p Op must be a generic virtual register with scalar or vector type.
+  ///
+  /// \return The newly created instruction.
+  template <typename DstTy, typename UseArgTy>
+  MachineInstrBuilder buildAnyExtOrTrunc(DstTy &&Dst, UseArgTy &&Use) {
+    return buildAnyExtOrTrunc(getDestFromArg(Dst), getRegFromArg(Use));
+  }
+  MachineInstrBuilder buildAnyExtOrTrunc(unsigned Res, unsigned Op);
+
+  /// Build and insert \p Res<def> = \p ExtOpc, \p Res = G_TRUNC \p
+  /// Op, or \p Res = COPY \p Op depending on the differing sizes of \p Res and
+  /// \p Op.
+  ///  ///
+  /// \pre setBasicBlock or setMI must have been called.
+  /// \pre \p Res must be a generic virtual register with scalar or vector type.
+  /// \pre \p Op must be a generic virtual register with scalar or vector type.
+  ///
+  /// \return The newly created instruction.
+  MachineInstrBuilder buildExtOrTrunc(unsigned ExtOpc, unsigned Res,
+                                      unsigned Op);
+
   /// Build and insert an appropriate cast between two registers of equal size.
   MachineInstrBuilder buildCast(unsigned Dst, unsigned Src);
 
   /// Build and insert G_BR \p Dest
   ///
   /// G_BR is an unconditional branch to \p Dest.
   ///
   /// \pre setBasicBlock or setMI must have been called.

lib/CodeGen/GlobalISel/LegalizerHelper.cpp

LegalizerHelper::widenScalar(MachineInstr &MI, unsigned TypeIdx, LLT WideTy) {
   }
   case TargetOpcode::G_GEP: {
     assert(TypeIdx == 1 && "unable to legalize pointer of GEP");
     unsigned OffsetExt = MRI.createGenericVirtualRegister(WideTy);
     MIRBuilder.buildSExt(OffsetExt, MI.getOperand(2).getReg());
     MI.getOperand(2).setReg(OffsetExt);
     return Legalized;
   }
+  case TargetOpcode::G_PHI: {
+    assert(TypeIdx == 0 && "Expecting only Idx 0");
+    MachineFunction *MF = MI.getParent()->getParent();
+    auto getExtendedReg = [this, MF, WideTy](unsigned Reg,
+                                             MachineBasicBlock &MBB) {
+      auto FirstTermIt = MBB.getFirstTerminator();
+      MIRBuilder.setInsertPt(MBB, FirstTermIt);
+      MachineInstr *DefMI = MRI.getVRegDef(Reg);
+      MachineInstrBuilder MIB;
+      if (DefMI->getOpcode() == TargetOpcode::G_TRUNC)
+        MIB = MIRBuilder.buildAnyExtOrTrunc(WideTy,
+                                            DefMI->getOperand(1).getReg());
+      else
+        MIB = MIRBuilder.buildAnyExt(WideTy, Reg);
+      return MIB->getOperand(0).getReg();
+    };
+    auto MIB = MIRBuilder.buildInstr(TargetOpcode::G_PHI, WideTy);
+    for (auto OpIt = MI.operands_begin() + 1, OpE = MI.operands_end();
+         OpIt != OpE;) {
+      unsigned Reg = OpIt++->getReg();
+      MachineBasicBlock *OpMBB = OpIt++->getMBB();
+      MIB.addReg(getExtendedReg(Reg, *OpMBB));
+      MIB.addMBB(OpMBB);
+    }
+    auto *MBB = MI.getParent();
+    MIRBuilder.setInsertPt(*MBB, MBB->getFirstNonPHI());
+    MIRBuilder.buildTrunc(MI.getOperand(0).getReg(),
+                          MIB->getOperand(0).getReg());
+    MI.eraseFromParent();
+    return Legalized;
+  }
   }
 }
 
 LegalizerHelper::LegalizeResult
 LegalizerHelper::lower(MachineInstr &MI, unsigned TypeIdx, LLT Ty) {
   using namespace TargetOpcode;
   MIRBuilder.setInstr(MI);
 

lib/CodeGen/GlobalISel/MachineIRBuilder.cpp

MachineInstrBuilder MachineIRBuilder::buildSExt(unsigned Res, unsigned Op) {
   return buildInstr(TargetOpcode::G_SEXT).addDef(Res).addUse(Op);
 }
 
 MachineInstrBuilder MachineIRBuilder::buildZExt(unsigned Res, unsigned Op) {
   validateTruncExt(Res, Op, true);
   return buildInstr(TargetOpcode::G_ZEXT).addDef(Res).addUse(Op);
 }
 
-MachineInstrBuilder MachineIRBuilder::buildSExtOrTrunc(unsigned Res,
-                                                       unsigned Op) {
+MachineInstrBuilder
+MachineIRBuilder::buildExtOrTrunc(unsigned ExtOpc, unsigned Res, unsigned Op) {
+  assert((TargetOpcode::G_ANYEXT == ExtOpc || TargetOpcode::G_ZEXT == ExtOpc ||
+          TargetOpcode::G_SEXT == ExtOpc) &&
+         "Expecting Extending Opc");
   assert(MRI->getType(Res).isScalar() || MRI->getType(Res).isVector());
   assert(MRI->getType(Res).isScalar() == MRI->getType(Op).isScalar());
 
   unsigned Opcode = TargetOpcode::COPY;
   if (MRI->getType(Res).getSizeInBits() > MRI->getType(Op).getSizeInBits())
-    Opcode = TargetOpcode::G_SEXT;
+    Opcode = ExtOpc;
   else if (MRI->getType(Res).getSizeInBits() < MRI->getType(Op).getSizeInBits())
     Opcode = TargetOpcode::G_TRUNC;
   else
     assert(MRI->getType(Res) == MRI->getType(Op));
 
   return buildInstr(Opcode).addDef(Res).addUse(Op);
 }
 
-MachineInstrBuilder MachineIRBuilder::buildZExtOrTrunc(unsigned Res,
+MachineInstrBuilder MachineIRBuilder::buildSExtOrTrunc(unsigned Res,
                                                        unsigned Op) {
-  assert(MRI->getType(Res).isScalar() || MRI->getType(Res).isVector());
-  assert(MRI->getType(Res).isScalar() == MRI->getType(Op).isScalar());
+  return buildExtOrTrunc(TargetOpcode::G_SEXT, Res, Op);
+}
 
-  unsigned Opcode = TargetOpcode::COPY;
-  if (MRI->getType(Res).getSizeInBits() > MRI->getType(Op).getSizeInBits())
-    Opcode = TargetOpcode::G_ZEXT;
-  else if (MRI->getType(Res).getSizeInBits() < MRI->getType(Op).getSizeInBits())
-    Opcode = TargetOpcode::G_TRUNC;
-  else
-    assert(MRI->getType(Res) == MRI->getType(Op));
+MachineInstrBuilder MachineIRBuilder::buildZExtOrTrunc(unsigned Res,
+                                                       unsigned Op) {
+  return buildExtOrTrunc(TargetOpcode::G_ZEXT, Res, Op);
+}
 
-  return buildInstr(Opcode).addDef(Res).addUse(Op);
+MachineInstrBuilder MachineIRBuilder::buildAnyExtOrTrunc(unsigned Res,
+                                                         unsigned Op) {
+  return buildExtOrTrunc(TargetOpcode::G_ANYEXT, Res, Op);
 }
 
 MachineInstrBuilder MachineIRBuilder::buildCast(unsigned Dst, unsigned Src) {
   LLT SrcTy = MRI->getType(Src);
   LLT DstTy = MRI->getType(Dst);
   if (SrcTy == DstTy)
     return buildCopy(Dst, Src);
 

lib/Target/AArch64/AArch64LegalizerInfo.cpp

AArch64LegalizerInfo::AArch64LegalizerInfo() {
   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 (auto Ty : {s1, s8})
+    setAction({G_PHI, Ty}, WidenScalar);
+
   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);

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

+# RUN: llc -mtriple=aarch64-unknown-unknown -global-isel -verify-machineinstrs -run-pass=legalizer %s -o - | 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 @legalize_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
+    %tmp1 = trunc i32 %tmp11 to i1
+    br label %return
+  
+  case2:                                            ; preds = %entry
+    %tmp22 = add i32 %argc, 2
+    %tmp2 = trunc i32 %tmp22 to i1
+    br label %return
+  
+  return:                                           ; preds = %case2, %case1
+    %res = phi i1 [ %tmp1, %case1 ], [ %tmp2, %case2 ]
+    %res_ext = zext i1 %res to i32
+    ret i32 %res_ext
+  }
+
+  define i32 @legalize_phi_empty(i32 %argc) {
+  entry:
+    %cmp = icmp ugt i32 %argc, 0
+    %tmp00 = add i32 %argc, 3
+    %trunc0 = trunc i32 %tmp00 to i1
+    br i1 %cmp, label %case1, label %case2
+
+  case1:                                            ; preds = %entry
+    %tmp11 = add i32 %argc, 1
+    %trunc1 = trunc i32 %tmp11 to i1
+    br label %return
+
+  case2:                                            ; preds = %entry
+    br label %return
+
+  return:                                           ; preds = %case2, %case1
+    %res = phi i1 [ %trunc1, %case1 ], [ %trunc0, %case2 ]
+    %res_ext = zext i1 %res to i32
+    ret i32 %res_ext
+  }
+
+  define i32 @legalize_phi_loop(i32 %argc) {
+  entry:
+    br label %loop_body
+
+  loop_body:                                        ; preds = %loop_body, %entry
+    %counter = phi i8 [ 0, %entry ], [ %inc, %loop_body ]
+    %inc = add i8 %counter, 1
+    %inc_ext = zext i8 %inc to i32
+    %cmp = icmp ugt i32 %inc_ext, %argc
+    br i1 %cmp, label %loop_body, label %return
+
+  return:                                           ; preds = %loop_body
+    %res_ext = zext i8 %inc to i32
+    ret i32 %res_ext
+  }
+
+  define i32 @legalize_phi_cycle(i32 %argc) {
+  entry:
+    br label %loop_body
+
+  loop_body:                                        ; preds = %loop_body, %entry
+    %counter = phi i8 [ 0, %entry ], [ %counter, %loop_body ]
+    %counter_ext = zext i8 %counter to i32
+    %cmp = icmp ugt i32 %counter_ext, %argc
+    br i1 %cmp, label %loop_body, label %return
+
+  return:                                           ; preds = %loop_body
+    ret i32 %counter_ext
+  }
+  define i32 @legalize_phi_same_bb(i32 %argc) {
+  entry:
+    %cmp = icmp ugt i32 %argc, 0
+    %tmp00 = add i32 %argc, 3
+    %trunc0 = trunc i32 %tmp00 to i8
+    br i1 %cmp, label %case1, label %case2
+
+  case1:                                            ; preds = %entry
+    %tmp11 = add i32 %argc, 1
+    %trunc1 = trunc i32 %tmp11 to i8
+    br label %return
+
+  case2:                                            ; preds = %entry
+    br label %return
+
+  return:                                           ; preds = %case2, %case1
+    %res1 = phi i8 [ %trunc1, %case1 ], [ %trunc0, %case2 ]
+    %res2 = phi i8 [ %trunc1, %case1 ], [ 42, %case2 ]
+    %res_ext1 = zext i8 %res1 to i32
+    %res_ext2 = zext i8 %res2 to i32
+    %res = add i32 %res_ext1, %res_ext2
+    ret i32 %res
+  }
+
+  define i32 @legalize_phi_diff_bb(i32 %argc, i32 %argc2) {
+  entry:
+    %cmp = icmp ugt i32 %argc, 0
+    %tmp00 = add i32 %argc, 3
+    %trunc0 = trunc i32 %tmp00 to i8
+    br i1 %cmp, label %case1, label %return
+
+  case1:                                            ; preds = %case1, %entry
+    %phi1 = phi i8 [ %trunc0, %entry ], [ 43, %case1 ]
+    %tmp2 = zext i8 %phi1 to i32
+    %tmp11 = add i32 %tmp2, 1
+    %cmp2 = icmp ugt i32 %tmp11, 44
+    br i1 %cmp2, label %return, label %case1
+
+  return:                                           ; preds = %case1, %entry
+    %res1 = phi i8 [ %phi1, %case1 ], [ %trunc0, %entry ]
+    %res_ext1 = zext i8 %res1 to i32
+    ret i32 %res_ext1
+  }
+
+...
+---
+name:            legalize_phi
+alignment:       2
+exposesReturnsTwice: false
+legalized:       false
+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: '' }
+  - { id: 10, class: _, preferred-register: '' }
+liveins:         
+body:             |
+  bb.1.entry:
+   ; Test that we insert legalization artifacts(Truncs here) into the correct BBs
+   ; while legalizing the G_PHI to s16.
+   ; CHECK-LABEL: name: legalize_phi
+   ; CHECK-LABEL: bb.1.case1:
+   ; CHECK: [[ADD_BB1:%.*]](s32) = G_ADD
+   ; CHECK: [[RES_BB1:%.*]](s16) = G_TRUNC [[ADD_BB1]]
+
+   ; CHECK-LABEL: bb.2.case2:
+   ; CHECK: [[ADD_BB2:%.*]](s32) = G_ADD
+   ; CHECK: [[RES_BB2:%.*]](s16) = G_TRUNC [[ADD_BB2]]
+
+   ; CHECK-LABEL: bb.3.return:
+   ; CHECK: [[RES_PHI:%.*]](s16) = G_PHI [[RES_BB1]](s16), %bb.1.case1, [[RES_BB2]](s16), %bb.2.case2
+   ; CHECK: [[RES:%.*]](s1) = G_TRUNC [[RES_PHI]]
+    successors: %bb.2.case1(0x40000000), %bb.3.case2(0x40000000)
+    liveins: %w0
+  
+    %0(s32) = COPY %w0
+    %1(s32) = G_CONSTANT i32 0
+    %3(s32) = G_CONSTANT i32 1
+    %6(s32) = G_CONSTANT i32 2
+    %2(s1) = G_ICMP intpred(ugt), %0(s32), %1
+    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
+    %5(s1) = G_TRUNC %4(s32)
+    G_BR %bb.4.return
+  
+  bb.3.case2:
+    successors: %bb.4.return(0x80000000)
+  
+    %7(s32) = G_ADD %0, %6
+    %8(s1) = G_TRUNC %7(s32)
+  
+  bb.4.return:
+    %9(s1) = G_PHI %5(s1), %bb.2.case1, %8(s1), %bb.3.case2
+    %10(s32) = G_ZEXT %9(s1)
+    %w0 = COPY %10(s32)
+    RET_ReallyLR implicit %w0
+
+...
+---
+name:            legalize_phi_empty
+alignment:       2
+exposesReturnsTwice: false
+legalized:       false
+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: '' }
+  - { id: 10, class: _, preferred-register: '' }
+liveins:
+body:             |
+  bb.1.entry:
+    successors: %bb.2.case1(0x40000000), %bb.3.case2(0x40000000)
+    liveins: %w0
+   ; Test that we properly legalize a phi with a predecessor that's empty
+   ; CHECK-LABEL: name: legalize_phi_empty
+   ; CHECK-LABEL: bb.0.entry:
+   ; CHECK: [[ENTRY_ADD:%.*]](s32) = G_ADD
+
+   ; CHECK-LABEL: bb.1.case1:
+   ; CHECK: [[ADD_BB1:%.*]](s32) = G_ADD
+   ; CHECK: [[RES_BB1:%.*]](s16) = G_TRUNC [[ADD_BB1]]
+
+   ; CHECK-LABEL: bb.2.case2:
+   ; CHECK: [[RES_BB2:%.*]](s16) = G_TRUNC [[ENTRY_ADD]]
+
+   ; CHECK: [[RES_PHI:%.*]](s16) = G_PHI [[RES_BB1]](s16), %bb.1.case1, [[RES_BB2]](s16), %bb.2.case2
+   ; CHECK: [[RES:%.*]](s1) = G_TRUNC [[RES_PHI]]
+
+    %0(s32) = COPY %w0
+    %1(s32) = G_CONSTANT i32 0
+    %3(s32) = G_CONSTANT i32 3
+    %6(s32) = G_CONSTANT i32 1
+    %2(s1) = G_ICMP intpred(ugt), %0(s32), %1
+    %4(s32) = G_ADD %0, %3
+    %5(s1) = G_TRUNC %4(s32)
+    G_BRCOND %2(s1), %bb.2.case1
+    G_BR %bb.3.case2
+
+  bb.2.case1:
+    successors: %bb.4.return(0x80000000)
+
+    %7(s32) = G_ADD %0, %6
+    %8(s1) = G_TRUNC %7(s32)
+    G_BR %bb.4.return
+
+  bb.3.case2:
+    successors: %bb.4.return(0x80000000)
+
+
+  bb.4.return:
+    %9(s1) = G_PHI %8(s1), %bb.2.case1, %5(s1), %bb.3.case2
+    %10(s32) = G_ZEXT %9(s1)
+    %w0 = COPY %10(s32)
+    RET_ReallyLR implicit %w0
+
+...
+---
+name:            legalize_phi_loop
+alignment:       2
+exposesReturnsTwice: false
+legalized:       false
+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: '' }
+liveins:
+body:             |
+  bb.1.entry:
+    successors: %bb.2.loop_body(0x80000000)
+    liveins: %w0
+   ; Test that we properly legalize a phi that uses a value from the same BB
+   ; CHECK-LABEL: name: legalize_phi_loop
+   ; CHECK-LABEL: bb.0.entry:
+   ; CHECK: [[C0:%.*]](s32) = G_CONSTANT i32 0
+   ; CHECK: [[RES_BB1:%.*]](s16) = G_TRUNC [[C0]]
+
+   ; CHECK-LABEL: bb.1.loop_body:
+   ; CHECK: [[RES_PHI:%.*]](s16) = G_PHI [[RES_BB1]](s16), %bb.0.entry, [[RES_BB2:%.*]](s16), %bb.1.loop_body
+   ; CHECK: [[RES_BB2]](s16) = G_ANYEXT
+    %0(s32) = COPY %w0
+    %2(s8) = G_CONSTANT i8 1
+    %7(s8) = G_CONSTANT i8 0
+
+  bb.2.loop_body:
+    successors: %bb.2.loop_body(0x40000000), %bb.3.return(0x40000000)
+
+    %1(s8) = G_PHI %7(s8), %bb.1.entry, %3(s8), %bb.2.loop_body
+    %3(s8) = G_ADD %1, %2
+    %4(s32) = G_ZEXT %3(s8)
+    %5(s1) = G_ICMP intpred(ugt), %4(s32), %0
+    G_BRCOND %5(s1), %bb.2.loop_body
+
+  bb.3.return:
+    %6(s32) = G_ZEXT %3(s8)
+    %w0 = COPY %6(s32)
+    RET_ReallyLR implicit %w0
+
+...
+---
+name:            legalize_phi_cycle
+alignment:       2
+exposesReturnsTwice: false
+legalized:       false
+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: '' }
+liveins:
+body:             |
+  bb.1.entry:
+    successors: %bb.2.loop_body(0x80000000)
+    liveins: %w0
+   ; Test that we properly legalize a phi that uses itself
+   ; CHECK-LABEL: name: legalize_phi_cycle
+   ; CHECK-LABEL: bb.0.entry:
+   ; CHECK: [[C0:%.*]](s32) = G_CONSTANT i32 0
+   ; CHECK: [[RES_BB1:%.*]](s16) = G_TRUNC [[C0]]
+
+   ; CHECK-LABEL: bb.1.loop_body:
+   ; CHECK: [[RES_PHI:%.*]](s16) = G_PHI [[RES_BB1]](s16), %bb.0.entry, [[RES_BB2:%.*]](s16), %bb.1.loop_body
+   ; CHECK: [[RES_BB2]](s16) = G_ANYEXT
+
+    %0(s32) = COPY %w0
+    %4(s8) = G_CONSTANT i8 0
+
+  bb.2.loop_body:
+    successors: %bb.2.loop_body(0x40000000), %bb.3.return(0x40000000)
+
+    %1(s8) = G_PHI %4(s8), %bb.1.entry, %1(s8), %bb.2.loop_body
+    %2(s32) = G_ZEXT %1(s8)
+    %3(s1) = G_ICMP intpred(ugt), %2(s32), %0
+    G_BRCOND %3(s1), %bb.2.loop_body
+
+  bb.3.return:
+    %w0 = COPY %2(s32)
+    RET_ReallyLR implicit %w0
+
+...
+---
+name:            legalize_phi_same_bb
+alignment:       2
+exposesReturnsTwice: false
+legalized:       false
+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: '' }
+  - { id: 10, class: _, preferred-register: '' }
+  - { id: 11, class: _, preferred-register: '' }
+  - { id: 12, class: _, preferred-register: '' }
+  - { id: 13, class: _, preferred-register: '' }
+  - { id: 14, class: _, preferred-register: '' }
+liveins:
+body:             |
+  bb.1.entry:
+    successors: %bb.2.case1(0x40000000), %bb.3.case2(0x40000000)
+    liveins: %w0
+   ; Make sure that we correctly insert the new legalized G_PHI at the
+   ; correct location (ie make sure G_PHIs are the first insts in the BB).
+   ; CHECK-LABEL: name: legalize_phi_same_bb
+   ; CHECK-LABEL: bb.0.entry:
+   ; CHECK: [[C42:%.*]](s32) = G_CONSTANT i32 42
+   ; CHECK: [[ENTRY_ADD:%.*]](s32) = G_ADD
+
+   ; CHECK-LABEL: bb.1.case1:
+   ; CHECK: [[BB1_ADD:%.*]](s32) = G_ADD
+   ; CHECK: [[RES1_BB1:%.*]](s16) = G_TRUNC [[BB1_ADD]]
+   ; CHECK: [[RES2_BB1:%.*]](s16) = G_TRUNC [[BB1_ADD]]
+
+   ; CHECK-LABEL: bb.2.case2:
+   ; CHECK: [[RES1_BB2:%.*]](s16) = G_TRUNC [[ENTRY_ADD]]
+   ; CHECK: [[RES2_BB2:%.*]](s16) = G_TRUNC [[C42]]
+
+   ; CHECK-LABEL: bb.3.return:
+   ; CHECK: [[RES1_PHI:%.*]](s16) = G_PHI [[RES1_BB1]](s16), %bb.1.case1, [[RES1_BB2]](s16), %bb.2.case2
+   ; CHECK-NEXT: [[RES_PHI:%.*]](s16) = G_PHI [[RES2_BB1]](s16), %bb.1.case1, [[RES2_BB2]](s16), %bb.2.case2
+
+    %0(s32) = COPY %w0
+    %1(s32) = G_CONSTANT i32 0
+    %3(s32) = G_CONSTANT i32 3
+    %6(s32) = G_CONSTANT i32 1
+    %14(s8) = G_CONSTANT i8 42
+    %2(s1) = G_ICMP intpred(ugt), %0(s32), %1
+    %4(s32) = G_ADD %0, %3
+    %5(s8) = G_TRUNC %4(s32)
+    G_BRCOND %2(s1), %bb.2.case1
+    G_BR %bb.3.case2
+
+  bb.2.case1:
+    successors: %bb.4.return(0x80000000)
+
+    %7(s32) = G_ADD %0, %6
+    %8(s8) = G_TRUNC %7(s32)
+    G_BR %bb.4.return
+
+  bb.3.case2:
+    successors: %bb.4.return(0x80000000)
+
+
+  bb.4.return:
+    %9(s8) = G_PHI %8(s8), %bb.2.case1, %5(s8), %bb.3.case2
+    %10(s8) = G_PHI %8(s8), %bb.2.case1, %14(s8), %bb.3.case2
+    %11(s32) = G_ZEXT %9(s8)
+    %12(s32) = G_ZEXT %10(s8)
+    %13(s32) = G_ADD %11, %12
+    %w0 = COPY %13(s32)
+    RET_ReallyLR implicit %w0
+
+...
+---
+name:            legalize_phi_diff_bb
+alignment:       2
+exposesReturnsTwice: false
+legalized:       false
+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: '' }
+  - { id: 10, class: _, preferred-register: '' }
+  - { id: 11, class: _, preferred-register: '' }
+  - { id: 12, class: _, preferred-register: '' }
+  - { id: 13, class: _, preferred-register: '' }
+  - { id: 14, class: _, preferred-register: '' }
+  - { id: 15, class: _, preferred-register: '' }
+liveins:
+body:             |
+  bb.1.entry:
+    successors: %bb.2.case1(0x40000000), %bb.3.return(0x40000000)
+    liveins: %w0, %w1
+   ; Make sure that we correctly legalize PHIs sharing common defs
+   ; in different BBs.
+   ; CHECK-LABEL: name: legalize_phi_diff_bb
+   ; CHECK-LABEL: bb.0.entry:
+   ; CHECK: [[C44:%.*]](s32) = G_CONSTANT i32 44
+   ; CHECK: [[C43:%.*]](s32) = G_CONSTANT i32 43
+   ; CHECK: [[ENTRY_ADD:%.*]](s32) = G_ADD
+   ; CHECK: [[RES_ENTRY:%.*]](s16) = G_TRUNC [[ENTRY_ADD]]
+   ; CHECK: [[RES_ENTRY1:%.*]](s16) = G_TRUNC [[ENTRY_ADD]]
+
+   ; CHECK-LABEL: bb.1.case1:
+   ; CHECK: [[RES1_PHI:%.*]](s16) = G_PHI [[RES_ENTRY]](s16), %bb.0.entry, [[RES_BB1:%.*]](s16), %bb.1.case1
+   ; CHECK: [[RES_BB1:%.*]](s16) = G_TRUNC
+   ; CHECK: [[RES_FOR_BB2:%.*]](s16) = COPY [[RES1_PHI]]
+
+   ; CHECK-LABEL: bb.2.return:
+   ; CHECK: [[RES2_PHI:%.*]](s16) = G_PHI [[RES_FOR_BB2]](s16), %bb.1.case1, [[RES_ENTRY1:%.*]](s16), %bb.0.entry
+
+    %0(s32) = COPY %w0
+    %1(s32) = COPY %w1
+    %2(s32) = G_CONSTANT i32 0
+    %4(s32) = G_CONSTANT i32 3
+    %9(s32) = G_CONSTANT i32 1
+    %11(s32) = G_CONSTANT i32 44
+    %15(s8) = G_CONSTANT i8 43
+    %3(s1) = G_ICMP intpred(ugt), %0(s32), %2
+    %5(s32) = G_ADD %0, %4
+    %6(s8) = G_TRUNC %5(s32)
+    G_BRCOND %3(s1), %bb.2.case1
+    G_BR %bb.3.return
+
+  bb.2.case1:
+    successors: %bb.3.return(0x40000000), %bb.2.case1(0x40000000)
+
+    %7(s8) = G_PHI %6(s8), %bb.1.entry, %15(s8), %bb.2.case1
+    %8(s32) = G_ZEXT %7(s8)
+    %10(s32) = G_ADD %8, %9
+    %12(s1) = G_ICMP intpred(ugt), %10(s32), %11
+    G_BRCOND %12(s1), %bb.3.return
+    G_BR %bb.2.case1
+
+  bb.3.return:
+    %13(s8) = G_PHI %7(s8), %bb.2.case1, %6(s8), %bb.1.entry
+    %14(s32) = G_ZEXT %13(s8)
+    %w0 = COPY %14(s32)
+    RET_ReallyLR implicit %w0
+
+...
+