[GlobalISel] Don't add duplicate successors to MBBs when translating indirectbr

[paquette]

Summary

This fixes a verifier failure on a bot:

http://green.lab.llvm.org/green/job/test-suite-verify-machineinstrs-aarch64-O0-g/

*** Bad machine code: MBB has duplicate entries in its successor list. ***
- function:    foo
- basic block: %bb.5 indirectgoto (0x7fe3d687ca08)

One of the GCC torture suite tests (pr70460.c) has an indirectbr instruction which has duplicate blocks in its destination list.

According to the langref this is allowed:

Blocks are allowed to occur multiple times in the destination list, though this isn’t particularly useful.

(https://www.llvm.org/docs/LangRef.html#indirectbr-instruction)

We don't allow this in MIR. So, when we translate such an instruction, the verifier screams.

This patch makes translateIndirectBr check if a successor has already been added to a block. If the successor is present, it is skipped rather than added twice.

[arsenm]

llvm/lib/CodeGen/GlobalISel/IRTranslator.cpp

843–848

I believe isSuccessor is a linear scan. This should use a pointer set like SelectionDAGBuilder

[paquette]

Use SmallSet like SelectionDAGBuilder does.

[arsenm]

llvm/lib/CodeGen/GlobalISel/IRTranslator.cpp

841

SmallPtrSet, not sure what the differences iss

[paquette]

llvm/lib/CodeGen/GlobalISel/IRTranslator.cpp

841

According to the programmer's manual it sounds like it should basically be the same?

"(and a SmallSet of pointers is transparently implemented with a SmallPtrSet)"

and in SmallSet.h:

/// If this set is of pointer values, transparently switch over to using
/// SmallPtrSet for performance.

I don't mind switching it to SmallPtrSet for clarity though.

llvm/lib/CodeGen/GlobalISel/IRTranslator.cpp

 bool IRTranslator::translateIndirectBr(const User &U,
                                        MachineIRBuilder &MIRBuilder) {
   const IndirectBrInst &BrInst = cast<IndirectBrInst>(U);
 
   const Register Tgt = getOrCreateVReg(*BrInst.getAddress());
   MIRBuilder.buildBrIndirect(Tgt);
 
   // Link successors.
+  SmallPtrSet<const BasicBlock *, 32> AddedSuccessors;
   MachineBasicBlock &CurBB = MIRBuilder.getMBB();
-  for (const BasicBlock *Succ : successors(&BrInst))
+  for (const BasicBlock *Succ : successors(&BrInst)) {
+    // It's legal for indirectbr instructions to have duplicate blocks in the
+    // destination list. We don't allow this in MIR. Skip anything that's
+    // already a successor.
+    if (!AddedSuccessors.insert(Succ).second)
+      continue;
     CurBB.addSuccessor(&getMBB(*Succ));
+  }
 
   return true;
 }
 
 static bool isSwiftError(const Value *V) {
   if (auto Arg = dyn_cast<Argument>(V))
     return Arg->hasSwiftErrorAttr();
   if (auto AI = dyn_cast<AllocaInst>(V))

llvm/test/CodeGen/AArch64/GlobalISel/irtranslator-indirect-br-repeated-block.ll

+; NOTE: Assertions have been autogenerated by utils/update_mir_test_checks.py
+; RUN: llc -O0 -mtriple=aarch64-apple-ios -global-isel -stop-after=irtranslator -verify-machineinstrs %s -o - | FileCheck %s
+;
+; Make sure that we don't duplicate successors/predecessors when translating
+; indirectbr instructions with duplicate block labels.
+
+define void @foo() {
+  ; CHECK-LABEL: name: foo
+  ; CHECK: bb.1 (%ir-block.0):
+  ; CHECK:   successors: %bb.2(0x2aaaaaaa), %bb.4(0x2aaaaaaa), %bb.3(0x2aaaaaaa)
+  ; CHECK:   [[DEF:%[0-9]+]]:_(p0) = G_IMPLICIT_DEF
+  ; CHECK:   G_BRINDIRECT [[DEF]](p0)
+  ; CHECK: bb.2 (%ir-block.1):
+  ; CHECK:   successors:
+  ; CHECK: bb.3 (%ir-block.2):
+  ; CHECK:   successors:
+  ; CHECK: bb.4 (%ir-block.3):
+  ; CHECK:   RET_ReallyLR
+  indirectbr i8* undef, [label %1, label %3, label %2, label %3, label %3]
+1:
+  unreachable
+2:
+  unreachable
+3:
+  ret void
+}