[GlobalISel] Add support for indirectbr

[kristof.beyls]

Summary

In this patch, support for handling indirectbr in GlobalISel is added.
Both generic and AArch64-specific support is added.

This makes SingleSource/Regression/C/2004-03-15-IndirectGoto in the test-suite compile without error with "-mllvm -global-isel=true -mllvm -global-isel-abort=1".
However, this patch alone doesn't make that test pass at execution time: apparently there is still something wrong with the relocations produced for addresses of basic blocks. But that seems to be an independently missing feature/bug in globalisel, so something for another patch.

I'm especially interested in any feedback on the best way to cover this in the regression tests. Maybe also a test should be added to check if a br instruction actually gets generated in the AArch64 assembly output? But there don't seem to be any such tests already under test/CodeGen/AArch64/GlobalISel?

[rovka]

Hi,

I'd also add a test case to arm64-instructionselect.mir.
I'm not aware of any end-to-end tests for global-isel on AArch64, but it's not too late to start adding some. Maybe @qcolombet, @ab or @t.p.northover can chime in on this?

Diana

lib/CodeGen/GlobalISel/MachineIRBuilder.cpp

160

Nit: I think addUse would be more consistent with the rest of the file.

lib/Target/AArch64/AArch64InstructionSelector.cpp

563

constrainSelectedInstRegOperands?

[kristof.beyls]

Thanks for the feedback Diana!

I've taken into account all your comments in this new revision, and I've also rebased to ToT.

[dsanders]

Maybe also a test should be added to check if a br instruction actually gets generated in the AArch64 assembly output? But there don't seem to be any such tests already under test/CodeGen/AArch64/GlobalISel?

arm64-instructionselect.mir does the main part of this. For example, it checks that an s32 G_ADD is selected to ADDWrr.

I'm not aware of any tests that directly check that ADDWrr emits the correct assembly though and I think we should add some. At the moment, SelectionDAG tests are covering it but they don't separate the assembly printing from the instruction selection.

I'm not aware of any end-to-end tests for global-isel on AArch64, but it's not too late to start adding some. Maybe @qcolombet, @ab or @t.p.northover can chime in on this?

I think it's preferable to test each pass separately as far as possible. End-to-end tests are easy to write but discourage the modular testing that GlobalISel enables and can be hard to maintain since small changes can cascade into big output differences. That said, we'll need some end-to-end testing eventually to check the overall code generator emits good output. I expect the test-suite repo will be used for this.

[kristof.beyls]

In D28079#635120, @dsanders wrote:

Maybe also a test should be added to check if a br instruction actually gets generated in the AArch64 assembly output? But there don't seem to be any such tests already under test/CodeGen/AArch64/GlobalISel?

arm64-instructionselect.mir does the main part of this. For example, it checks that an s32 G_ADD is selected to ADDWrr.

I'm not aware of any tests that directly check that ADDWrr emits the correct assembly though and I think we should add some. At the moment, SelectionDAG tests are covering it but they don't separate the assembly printing from the instruction selection.

I'm not aware of any end-to-end tests for global-isel on AArch64, but it's not too late to start adding some. Maybe @qcolombet, @ab or @t.p.northover can chime in on this?

I think it's preferable to test each pass separately as far as possible. End-to-end tests are easy to write but discourage the modular testing that GlobalISel enables and can be hard to maintain since small changes can cascade into big output differences. That said, we'll need some end-to-end testing eventually to check the overall code generator emits good output. I expect the test-suite repo will be used for this.

Right, so if I understand correctly, we're completely missing target-specific MachineInstr-to-assembly testing. My gut feel is that using the test-suite to test this mapping is not sufficient as compilers just don't generate a lot of the instructions in most instruction sets, when compiling standard C/C++ code. So correct translation of a lot of instructions just will not be tested with test-suite testing alone.
(Side question: the short-hand (G)MIR is used for generic MachineInstr. Is there already a short-hand to denote target-specific MachineInstr? Would (T)MIR work for that?)
This seems to imply that (as an end result), we'd want the following regression tests:

1. LLVM-IR -> (G)MIR (seemingly the tests for this are in test/CodeGen/AArch64/GlobalISel/arm64-irtranslator.ll. This seems to be somewhat target-independent. But only somewhat.)
2. (G)MIR -> (T)MIR (seemingly the tests for this are in test/CodeGen/AArch64/GlobalISel/arm64-instructionselect.mir)
3. (T)MIR -> assembly (no tests at all for this at the moment).

I'd be happy to try and create tests for 3., up to the same level of completeness as the tests for 1. and 2., if this seems the right approach, so that we get the same level of basic regression testing for the 3 translation steps.

Maybe the existing tests for LLVM-IR -> assembly translation are good enough for end-to-end testing? My gut feel is that in the long run we should keep some/most/all of them too, but I haven't looked into them in detail from a GlobalISel point-of-view yet.

[dsanders]

In D28079#635275, @kristof.beyls wrote:

In D28079#635120, @dsanders wrote:

Maybe also a test should be added to check if a br instruction actually gets generated in the AArch64 assembly output? But there don't seem to be any such tests already under test/CodeGen/AArch64/GlobalISel?

arm64-instructionselect.mir does the main part of this. For example, it checks that an s32 G_ADD is selected to ADDWrr.

I'm not aware of any tests that directly check that ADDWrr emits the correct assembly though and I think we should add some. At the moment, SelectionDAG tests are covering it but they don't separate the assembly printing from the instruction selection.

I'm not aware of any end-to-end tests for global-isel on AArch64, but it's not too late to start adding some. Maybe @qcolombet, @ab or @t.p.northover can chime in on this?

I think it's preferable to test each pass separately as far as possible. End-to-end tests are easy to write but discourage the modular testing that GlobalISel enables and can be hard to maintain since small changes can cascade into big output differences. That said, we'll need some end-to-end testing eventually to check the overall code generator emits good output. I expect the test-suite repo will be used for this.

Right, so if I understand correctly, we're completely missing target-specific MachineInstr-to-assembly testing.

It's not tested explicitly but the CodeGen tests for SelectionDAG and FastISel provide some coverage because llc has to print the assembly. We should be able to improve on that.

My gut feel is that using the test-suite to test this mapping is not sufficient as compilers just don't generate a lot of the instructions in most instruction sets, when compiling standard C/C++ code. So correct translation of a lot of instructions just will not be tested with test-suite testing alone.

I agree, it would be good to test this mapping independently now that it's possible to do so. It would be more thorough and would also have exposed some bugs in the Mips target much quicker than they were actually discovered. There were lots of subtarget-specific MCInst's that had the same assembly but different encodings and this was causing assembly tests to falsely pass even though the wrong instruction was being selected.

(Side question: the short-hand (G)MIR is used for generic MachineInstr. Is there already a short-hand to denote target-specific MachineInstr? Would (T)MIR work for that?)

There's MCInst for the MC layer (assembly/disassembly/etc). but we also need a way of referring to (G)MIR that is either partially or fully target specific. (T)MIR sounds good to me.

While we're asking about the short-hand: What's the conventional short-hand for the generic MIR? I've been switching between gMIR, GMIR, GenericMIR, and a few others according to what other people are using but I'm not sure if there's any consensus on which one is right.

This seems to imply that (as an end result), we'd want the following regression tests:

1. LLVM-IR -> (G)MIR (seemingly the tests for this are in test/CodeGen/AArch64/GlobalISel/arm64-irtranslator.ll. This seems to be somewhat target-independent. But only somewhat.)
2. (G)MIR -> (T)MIR (seemingly the tests for this are in test/CodeGen/AArch64/GlobalISel/arm64-instructionselect.mir)
3. (T)MIR -> assembly (no tests at all for this at the moment).

I think there should also be some (G)MIR -> (G)MIR stages to cover the legalizer (e.g. legalize-*.mir) and register bank selection as well as a target-specific set of (T)MIR -> (T)MIR stages for pseudo-expansion, etc.

I'd be happy to try and create tests for 3., up to the same level of completeness as the tests for 1. and 2., if this seems the right approach, so that we get the same level of basic regression testing for the 3 translation steps.

That would be great!

Maybe the existing tests for LLVM-IR -> assembly translation are good enough for end-to-end testing? My gut feel is that in the long run we should keep some/most/all of them too, but I haven't looked into them in detail from a GlobalISel point-of-view yet.

Removing tests makes me nervous so I'd lean towards keeping them too. I'm not sure how good the current test coverage is either but I'll have a think on how I can find out. I might be able to log which rules fire and have a tablegen-erated tool report coverage holes.

[qcolombet]

Hi,

Regarding (G)MIR vs. (T)MIR or whatever, I would stick to MIR for intermediate MachineInstr representation without generic opcode and Generic MachineInstr (or GMIR) when generic opcode are present. The story behind (G)MIR is that this is a*always* a target specific representation (because MachineInstr are always bound to a target) but can optionally (thus parenthesis) contain generic opcodes.

Therefore the difference between (G)MIR and MIR is the latter cannot have generic opcodes whereas the former can, but again in both cases the representation is target depend.

The bottom line is please don't add another naming convention.

Cheers,
-Quentin

[qcolombet]

I'd be happy to try and create tests for 3., up to the same level of completeness as the tests for 1. and 2., if this seems the right approach, so that we get the same level of basic regression testing for the 3 translation steps.

That should already be possible with something like:
llc -start-after=instruction-select

One caveat, this is possible that the mir testing will need some additional work for that to succeed. Indeed, we still have a few issue with that regarding how the pass manager initialize some of the passes that are implicitly instantiated (e.g., https://llvm.org/bugs/show_bug.cgi?id=30324).

Q.

[qcolombet]

test/CodeGen/AArch64/GlobalISel/arm64-instructionselect.mir

1931 ↗

(On Diff #82536)

I think we miss a check of %0 = COPY %x0

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

133

Get rid of implicit naming please.

test/CodeGen/X86/implicit-null-checks.mir

322 ↗

(On Diff #82536)

This is an unrelated change, right?

[kristof.beyls]

In D28079#636013, @qcolombet wrote:

Hi,

Regarding (G)MIR vs. (T)MIR or whatever, I would stick to MIR for intermediate MachineInstr representation without generic opcode and Generic MachineInstr (or GMIR) when generic opcode are present. The story behind (G)MIR is that this is a*always* a target specific representation (because MachineInstr are always bound to a target) but can optionally (thus parenthesis) contain generic opcodes.

Therefore the difference between (G)MIR and MIR is the latter cannot have generic opcodes whereas the former can, but again in both cases the representation is target depend.

The bottom line is please don't add another naming convention.

Cheers,
-Quentin

Having the convention that MIR represents MachineInstr representation that cannot have generic opcodes is fine for me - I was just wondering what the convention was. Thanks for explaining, Quentin.

I've also addressed all your other remarks; thanks for the feedback!

test/CodeGen/X86/implicit-null-checks.mir

322 ↗

(On Diff #82536)

The hard-coded 260 in the test seems to be a specific TargetOpcode value. Since this patch adds a new TargetOpcode (G_BRINDIRECT), the value changes, but obviously only if you build LLVM with GlobalISel enabled.

I followed Tim's lead from
http://llvm.org/viewvc/llvm-project?view=revision&revision=274774 to fix the test in the same way as another test in this same file that had the same issue at that time. I've believed Tim's word that these tests don't care about the internal opcode number.

[kristof.beyls]

Updating patch to ToT.
I believe this is ready to be committed, but am waiting for an LGTM from someone.

Regarding adding a test for the MIR->assembly path: I indeed hit https://llvm.org/bugs/show_bug.cgi?id=30324 when trying to do so.
I've got the least-hacky patch I could come up with to fix that up for review at https://reviews.llvm.org/D28513.
I don't think it's worthwhile to block indirectbr support on that though: we already lack MIR->assembly tests for all the other instructions already handled by GlobalISel, so can just add that test for indirectbr when we add those tests for all the other instructions too.

[rovka]

I don't see anything wrong with this, I think you can go ahead and commit.

include/llvm/CodeGen/GlobalISel/IRTranslator.h

private:
   /// \pre \p U is a binary operation.
   bool translateBinaryOp(unsigned Opcode, const User &U,
                          MachineIRBuilder &MIRBuilder);
 
   /// Translate branch (br) instruction.
   /// \pre \p U is a branch instruction.
   bool translateBr(const User &U, MachineIRBuilder &MIRBuilder);
 
+  bool translateIndirectBr(const User &U, MachineIRBuilder &MIRBuilder);
+
   bool translateExtractValue(const User &U, MachineIRBuilder &MIRBuilder);
 
   bool translateInsertValue(const User &U, MachineIRBuilder &MIRBuilder);
 
   bool translateSelect(const User &U, MachineIRBuilder &MIRBuilder);
 
   bool translateGetElementPtr(const User &U, MachineIRBuilder &MIRBuilder);
 
private:
   }
 
 
   // Stubs to keep the compiler happy while we implement the rest of the
   // translation.
   bool translateSwitch(const User &U, MachineIRBuilder &MIRBuilder) {
     return false;
   }
-  bool translateIndirectBr(const User &U, MachineIRBuilder &MIRBuilder) {
-    return false;
-  }
   bool translateResume(const User &U, MachineIRBuilder &MIRBuilder) {
     return false;
   }
   bool translateCleanupRet(const User &U, MachineIRBuilder &MIRBuilder) {
     return false;
   }
   bool translateCatchRet(const User &U, MachineIRBuilder &MIRBuilder) {
     return false;

include/llvm/CodeGen/GlobalISel/MachineIRBuilder.h

public:
   ///      type. At the beginning of legalization, this will be a single
   ///      bit (s1). Targets with interesting flags registers may change
   ///      this. For a wider type, whether the branch is taken must only
   ///      depend on bit 0 (for now).
   ///
   /// \return The newly created instruction.
   MachineInstrBuilder buildBrCond(unsigned Tst, MachineBasicBlock &BB);
 
+  /// Build and insert G_BRINDIRECT \p Tgt
+  ///
+  /// G_BRINDIRECT is an indirect branch to \p Tgt.
+  ///
+  /// \pre setBasicBlock or setMI must have been called.
+  /// \pre \p Tgt must be a generic virtual register with pointer type.
+  ///
+  /// \return a MachineInstrBuilder for the newly created instruction.
+  MachineInstrBuilder buildBrIndirect(unsigned Tgt);
+
   /// Build and insert \p Res = G_CONSTANT \p Val
   ///
   /// G_CONSTANT is an integer constant with the specified size and value. \p
   /// Val will be extended or truncated to the size of \p Reg.
   ///
   /// \pre setBasicBlock or setMI must have been called.
   /// \pre \p Res must be a generic virtual register with scalar or pointer
   ///      type.

include/llvm/Target/GenericOpcodes.td

 def G_BRCOND : Instruction {
   let OutOperandList = (outs);
   let InOperandList = (ins type0:$tst, unknown:$truebb);
   let hasSideEffects = 0;
   let isBranch = 1;
   let isTerminator = 1;
 }
 
+// Generic indirect branch.
+def G_BRINDIRECT : Instruction {
+  let OutOperandList = (outs);
+  let InOperandList = (ins type0:$src1);
+  let hasSideEffects = 0;
+  let isBranch = 1;
+  let isTerminator = 1;
+}
+
 // TODO: Add the other generic opcodes.

include/llvm/Target/TargetOpcodes.def

 HANDLE_TARGET_OPCODE(G_LOAD)
 
 /// Generic store.
 HANDLE_TARGET_OPCODE(G_STORE)
 
 /// Generic conditional branch instruction.
 HANDLE_TARGET_OPCODE(G_BRCOND)
 
+/// Generic indirect branch instruction.
+HANDLE_TARGET_OPCODE(G_BRINDIRECT)
+
 /// Generic intrinsic use (without side effects).
 HANDLE_TARGET_OPCODE(G_INTRINSIC)
 
 /// Generic intrinsic use (with side effects).
 HANDLE_TARGET_OPCODE(G_INTRINSIC_W_SIDE_EFFECTS)
 
 /// Generic extension allowing rubbish in high bits.
 HANDLE_TARGET_OPCODE(G_ANYEXT)

lib/CodeGen/GlobalISel/IRTranslator.cpp

bool IRTranslator::translateBr(const User &U, MachineIRBuilder &MIRBuilder) {
 
   // Link successors.
   MachineBasicBlock &CurBB = MIRBuilder.getMBB();
   for (const BasicBlock *Succ : BrInst.successors())
     CurBB.addSuccessor(&getOrCreateBB(*Succ));
   return true;
 }
 
+bool IRTranslator::translateIndirectBr(const User &U,
+                                       MachineIRBuilder &MIRBuilder) {
+  const IndirectBrInst &BrInst = cast<IndirectBrInst>(U);
+
+  const unsigned Tgt = getOrCreateVReg(*BrInst.getAddress());
+  MIRBuilder.buildBrIndirect(Tgt);
+
+  // Link successors.
+  MachineBasicBlock &CurBB = MIRBuilder.getMBB();
+  for (const BasicBlock *Succ : BrInst.successors())
+    CurBB.addSuccessor(&getOrCreateBB(*Succ));
+
+  return true;
+}
+
 bool IRTranslator::translateLoad(const User &U, MachineIRBuilder &MIRBuilder) {
   const LoadInst &LI = cast<LoadInst>(U);
 
   if (!TPC->isGlobalISelAbortEnabled() && LI.isAtomic())
     return false;
 
   assert(!LI.isAtomic() && "only non-atomic loads are supported at the moment");
   auto Flags = LI.isVolatile() ? MachineMemOperand::MOVolatile

lib/CodeGen/GlobalISel/MachineIRBuilder.cpp

return buildInstr(TargetOpcode::G_MUL)
       .addUse(Op0)
       .addUse(Op1);
 }
 
 MachineInstrBuilder MachineIRBuilder::buildBr(MachineBasicBlock &Dest) {
   return buildInstr(TargetOpcode::G_BR).addMBB(&Dest);
 }
 
+MachineInstrBuilder MachineIRBuilder::buildBrIndirect(unsigned Tgt) {
+  return buildInstr(TargetOpcode::G_BRINDIRECT).addReg(Tgt);
+}
+
 MachineInstrBuilder MachineIRBuilder::buildCopy(unsigned Res, unsigned Op) {
   return buildInstr(TargetOpcode::COPY).addDef(Res).addUse(Op);
 }
 
 MachineInstrBuilder MachineIRBuilder::buildConstant(unsigned Res,
                                                     const ConstantInt &Val) {
   LLT Ty = MRI->getType(Res);
 

lib/Target/AArch64/AArch64InstructionSelector.cpp

auto MIB = BuildMI(MBB, I, I.getDebugLoc(), TII.get(AArch64::TBNZW))
                    .addUse(CondReg)
                    .addImm(/*bit offset=*/0)
                    .addMBB(DestMBB);
 
     I.eraseFromParent();
     return constrainSelectedInstRegOperands(*MIB.getInstr(), TII, TRI, RBI);
   }
 
+  case TargetOpcode::G_BRINDIRECT: {
+    I.setDesc(TII.get(AArch64::BR));
+    return true;
+  }
+
   case TargetOpcode::G_FCONSTANT:
   case TargetOpcode::G_CONSTANT: {
     const bool isFP = Opcode == TargetOpcode::G_FCONSTANT;
 
     const LLT s32 = LLT::scalar(32);
     const LLT s64 = LLT::scalar(64);
     const LLT p0 = LLT::pointer(0, 64);
 

lib/Target/AArch64/AArch64LegalizerInfo.cpp

for (auto Ty : { s32, s64 }) {
     setAction({G_FPTOUI, 1, Ty}, Legal);
     setAction({G_SITOFP, 0, Ty}, Legal);
     setAction({G_UITOFP, 0, Ty}, Legal);
   }
 
   // Control-flow
   for (auto Ty : {s1, s8, s16, s32})
     setAction({G_BRCOND, Ty}, Legal);
+  setAction({G_BRINDIRECT, p0}, Legal);
 
   // Select
   for (auto Ty : {s1, s8, s16, s32, s64})
     setAction({G_SELECT, Ty}, Legal);
 
   setAction({G_SELECT, 1, s1}, Legal);
 
   // Pointer-handling

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

define void @condbr(i1* %tstaddr) {
   %tst = load i1, i1* %tstaddr
   br i1 %tst, label %true, label %false
 true:
   ret void
 false:
   ret void
 }
 
+; Tests for indirect br.
+; CHECK-LABEL: name: indirectbr
+; CHECK: body:
+;
+; ABI/constant lowering and IR-level entry basic block.
+; CHECK: {{bb.[0-9]+}}:
+; Make sure we have one successor
+; CHECK-NEXT: successors: %[[BB_L1:bb.[0-9]+]](0x80000000)
+; CHECK: G_BR %[[BB_L1]]
+;
+; Check basic block L1 has 2 successors: BBL1 and BBL2
+; CHECK: [[BB_L1]]:
+; CHECK-NEXT: successors: %[[BB_L1]](0x40000000),
+; CHECK:                  %[[BB_L2:bb.[0-9]+]](0x40000000)
+; CHECK: G_BRINDIRECT %{{[0-9]+}}(p0)
+;
+; Check basic block L2 is the return basic block
+; CHECK: [[BB_L2]]:
+; CHECK-NEXT: RET_ReallyLR
+
+@indirectbr.L = internal unnamed_addr constant [3 x i8*] [i8* blockaddress(@indirectbr, %L1), i8* blockaddress(@indirectbr, %L2), i8* null], align 8
+
+define void @indirectbr() {
+entry:
+  br label %L1
+L1:                                               ; preds = %entry, %L1
+  %i.0 = phi i32 [ 0, %entry ], [ %inc, %L1 ]
+  %inc = add i32 %i.0, 1
+  %idxprom = zext i32 %i.0 to i64
+  %arrayidx = getelementptr inbounds [3 x i8*], [3 x i8*]* @indirectbr.L, i64 0, i64 %idxprom
+  %0 = load i8*, i8** %arrayidx, align 8
+  indirectbr i8* %0, [label %L1, label %L2]
+L2:                                               ; preds = %L1
+  ret void
+}
+
 ; Tests for or.
 ; CHECK-LABEL: name: ori64
 ; CHECK: [[ARG1:%[0-9]+]](s64) = COPY %x0
 ; CHECK-NEXT: [[ARG2:%[0-9]+]](s64) = COPY %x1
 ; CHECK-NEXT: [[RES:%[0-9]+]](s64) = G_OR [[ARG1]], [[ARG2]]
 ; CHECK-NEXT: %x0 = COPY [[RES]]
 ; CHECK-NEXT: RET_ReallyLR implicit %x0
 define i64 @ori64(i64 %arg1, i64 %arg2) {