MIR Serialization: Serialize machine basic block operands.

This commit serializes machine basic block operands. The
machine basic block operands use the following syntax:

  %bb.<id>[.<name>]

This commit also modifies the YAML representation for the
machine basic blocks - a new, required field 'id' is added
to the MBB YAML mapping.

The id is used to resolve the MBB references to the
actual MBBs. And while the name of the MBB can be
included in a MBB reference, this name isn't used to
resolve MBB references - as it's possible that multiple
MBBs will reference the same BB and thus they will have the
same name. If the name is specified, the parser will verify
that it is equal to the name of the MBB with the specified id.

Reviewers: Duncan P. N. Exon Smith

Differential Revision: http://reviews.llvm.org/D10608

llvm-svn: 240792

25 files changed, 417 insertions, 39 deletions

diff --git a/llvm/include/llvm/CodeGen/MIRYamlMapping.h b/llvm/include/llvm/CodeGen/MIRYamlMapping.h
index 891a01ecb48..bb8df6307d5 100644
--- a/llvm/include/llvm/CodeGen/MIRYamlMapping.h
+++ b/llvm/include/llvm/CodeGen/MIRYamlMapping.h
@@ -64,6 +64,7 @@ namespace llvm {
 namespace yaml {
 
 struct MachineBasicBlock {
+  unsigned ID;
   std::string Name;
   unsigned Alignment = 0;
   bool IsLandingPad = false;
@@ -75,6 +76,7 @@ struct MachineBasicBlock {
 
 template <> struct MappingTraits<MachineBasicBlock> {
   static void mapping(IO &YamlIO, MachineBasicBlock &MBB) {
+    YamlIO.mapRequired("id", MBB.ID);
     YamlIO.mapOptional("name", MBB.Name,
                        std::string()); // Don't print out an empty name.
     YamlIO.mapOptional("alignment", MBB.Alignment);
diff --git a/llvm/lib/CodeGen/MIRParser/MILexer.cpp b/llvm/lib/CodeGen/MIRParser/MILexer.cpp
index 3383d1f5cf5..57e5ffe4353 100644
--- a/llvm/lib/CodeGen/MIRParser/MILexer.cpp
+++ b/llvm/lib/CodeGen/MIRParser/MILexer.cpp
@@ -35,7 +35,7 @@ public:
 
   char peek(int I = 0) const { return End - Ptr <= I ? 0 : Ptr[I]; }
 
-  void advance() { ++Ptr; }
+  void advance(unsigned I = 1) { Ptr += I; }
 
   StringRef remaining() const { return StringRef(Ptr, End - Ptr); }
 
@@ -70,12 +70,39 @@ static Cursor lexIdentifier(Cursor C, MIToken &Token) {
   return C;
 }
 
+static Cursor lexMachineBasicBlock(
+    Cursor C, MIToken &Token,
+    function_ref<void(StringRef::iterator Loc, const Twine &)> ErrorCallback) {
+  auto Range = C;
+  C.advance(4); // Skip '%bb.'
+  if (!isdigit(C.peek())) {
+    Token = MIToken(MIToken::Error, C.remaining());
+    ErrorCallback(C.location(), "expected a number after '%bb.'");
+    return C;
+  }
+  auto NumberRange = C;
+  while (isdigit(C.peek()))
+    C.advance();
+  StringRef Number = NumberRange.upto(C);
+  unsigned StringOffset = 4 + Number.size(); // Drop '%bb.<id>'
+  if (C.peek() == '.') {
+    C.advance(); // Skip '.'
+    ++StringOffset;
+    while (isIdentifierChar(C.peek()))
+      C.advance();
+  }
+  Token = MIToken(MIToken::MachineBasicBlock, Range.upto(C), APSInt(Number),
+                  StringOffset);
+  return C;
+}
+
 static Cursor lexPercent(Cursor C, MIToken &Token) {
   auto Range = C;
   C.advance(); // Skip '%'
   while (isIdentifierChar(C.peek()))
     C.advance();
-  Token = MIToken(MIToken::NamedRegister, Range.upto(C));
+  Token = MIToken(MIToken::NamedRegister, Range.upto(C),
+                  /*StringOffset=*/1); // Drop the '%'
   return C;
 }
 
@@ -119,8 +146,11 @@ StringRef llvm::lexMIToken(
   auto Char = C.peek();
   if (isalpha(Char) || Char == '_')
     return lexIdentifier(C, Token).remaining();
-  if (Char == '%')
+  if (Char == '%') {
+    if (C.remaining().startswith("%bb."))
+      return lexMachineBasicBlock(C, Token, ErrorCallback).remaining();
     return lexPercent(C, Token).remaining();
+  }
   if (isdigit(Char) || (Char == '-' && isdigit(C.peek(1))))
     return lexIntegerLiteral(C, Token).remaining();
   MIToken::TokenKind Kind = symbolToken(Char);
diff --git a/llvm/lib/CodeGen/MIRParser/MILexer.h b/llvm/lib/CodeGen/MIRParser/MILexer.h
index f9cc97cb34e..adfe0e20192 100644
--- a/llvm/lib/CodeGen/MIRParser/MILexer.h
+++ b/llvm/lib/CodeGen/MIRParser/MILexer.h
@@ -39,6 +39,7 @@ struct MIToken {
     // Identifier tokens
     Identifier,
     NamedRegister,
+    MachineBasicBlock,
 
     // Other tokens
     IntegerLiteral
@@ -46,14 +47,17 @@ struct MIToken {
 
 private:
   TokenKind Kind;
+  unsigned StringOffset;
   StringRef Range;
   APSInt IntVal;
 
 public:
-  MIToken(TokenKind Kind, StringRef Range) : Kind(Kind), Range(Range) {}
+  MIToken(TokenKind Kind, StringRef Range, unsigned StringOffset = 0)
+      : Kind(Kind), StringOffset(StringOffset), Range(Range) {}
 
-  MIToken(TokenKind Kind, StringRef Range, const APSInt &IntVal)
-      : Kind(Kind), Range(Range), IntVal(IntVal) {}
+  MIToken(TokenKind Kind, StringRef Range, const APSInt &IntVal,
+          unsigned StringOffset = 0)
+      : Kind(Kind), StringOffset(StringOffset), Range(Range), IntVal(IntVal) {}
 
   TokenKind kind() const { return Kind; }
 
@@ -69,9 +73,13 @@ public:
 
   StringRef::iterator location() const { return Range.begin(); }
 
-  StringRef stringValue() const { return Range; }
+  StringRef stringValue() const { return Range.drop_front(StringOffset); }
 
   const APSInt &integerValue() const { return IntVal; }
+
+  bool hasIntegerValue() const {
+    return Kind == IntegerLiteral || Kind == MachineBasicBlock;
+  }
 };
 
 /// Consume a single machine instruction token in the given source and return
diff --git a/llvm/lib/CodeGen/MIRParser/MIParser.cpp b/llvm/lib/CodeGen/MIRParser/MIParser.cpp
index 07aac674ffb..61a7dfc68b5 100644
--- a/llvm/lib/CodeGen/MIRParser/MIParser.cpp
+++ b/llvm/lib/CodeGen/MIRParser/MIParser.cpp
@@ -32,6 +32,8 @@ class MIParser {
   SMDiagnostic &Error;
   StringRef Source, CurrentSource;
   MIToken Token;
+  /// Maps from basic block numbers to MBBs.
+  const DenseMap<unsigned, MachineBasicBlock *> &MBBSlots;
   /// Maps from instruction names to op codes.
   StringMap<unsigned> Names2InstrOpCodes;
   /// Maps from register names to registers.
@@ -39,7 +41,8 @@ class MIParser {
 
 public:
   MIParser(SourceMgr &SM, MachineFunction &MF, SMDiagnostic &Error,
-           StringRef Source);
+           StringRef Source,
+           const DenseMap<unsigned, MachineBasicBlock *> &MBBSlots);
 
   void lex();
 
@@ -58,9 +61,15 @@ public:
   bool parseRegister(unsigned &Reg);
   bool parseRegisterOperand(MachineOperand &Dest, bool IsDef = false);
   bool parseImmediateOperand(MachineOperand &Dest);
+  bool parseMBBOperand(MachineOperand &Dest);
   bool parseMachineOperand(MachineOperand &Dest);
 
 private:
+  /// Convert the integer literal in the current token into an unsigned integer.
+  ///
+  /// Return true if an error occurred.
+  bool getUnsigned(unsigned &Result);
+
   void initNames2InstrOpCodes();
 
   /// Try to convert an instruction name to an opcode. Return true if the
@@ -79,9 +88,10 @@ private:
 } // end anonymous namespace
 
 MIParser::MIParser(SourceMgr &SM, MachineFunction &MF, SMDiagnostic &Error,
-                   StringRef Source)
+                   StringRef Source,
+                   const DenseMap<unsigned, MachineBasicBlock *> &MBBSlots)
     : SM(SM), MF(MF), Error(Error), Source(Source), CurrentSource(Source),
-      Token(MIToken::Error, StringRef()) {}
+      Token(MIToken::Error, StringRef()), MBBSlots(MBBSlots) {}
 
 void MIParser::lex() {
   CurrentSource = lexMIToken(
@@ -178,7 +188,7 @@ bool MIParser::parseRegister(unsigned &Reg) {
     Reg = 0;
     break;
   case MIToken::NamedRegister: {
-    StringRef Name = Token.stringValue().drop_front(1); // Drop the '%'
+    StringRef Name = Token.stringValue();
     if (getRegisterByName(Name, Reg))
       return error(Twine("unknown register name '") + Name + "'");
     break;
@@ -212,6 +222,34 @@ bool MIParser::parseImmediateOperand(MachineOperand &Dest) {
   return false;
 }
 
+bool MIParser::getUnsigned(unsigned &Result) {
+  assert(Token.hasIntegerValue() && "Expected a token with an integer value");
+  const uint64_t Limit = uint64_t(std::numeric_limits<unsigned>::max()) + 1;
+  uint64_t Val64 = Token.integerValue().getLimitedValue(Limit);
+  if (Val64 == Limit)
+    return error("expected 32-bit integer (too large)");
+  Result = Val64;
+  return false;
+}
+
+bool MIParser::parseMBBOperand(MachineOperand &Dest) {
+  assert(Token.is(MIToken::MachineBasicBlock));
+  unsigned Number;
+  if (getUnsigned(Number))
+    return true;
+  auto MBBInfo = MBBSlots.find(Number);
+  if (MBBInfo == MBBSlots.end())
+    return error(Twine("use of undefined machine basic block #") +
+                 Twine(Number));
+  MachineBasicBlock *MBB = MBBInfo->second;
+  if (!Token.stringValue().empty() && Token.stringValue() != MBB->getName())
+    return error(Twine("the name of machine basic block #") + Twine(Number) +
+                 " isn't '" + Token.stringValue() + "'");
+  Dest = MachineOperand::CreateMBB(MBB);
+  lex();
+  return false;
+}
+
 bool MIParser::parseMachineOperand(MachineOperand &Dest) {
   switch (Token.kind()) {
   case MIToken::underscore:
@@ -219,6 +257,8 @@ bool MIParser::parseMachineOperand(MachineOperand &Dest) {
     return parseRegisterOperand(Dest);
   case MIToken::IntegerLiteral:
     return parseImmediateOperand(Dest);
+  case MIToken::MachineBasicBlock:
+    return parseMBBOperand(Dest);
   case MIToken::Error:
     return true;
   default:
@@ -271,7 +311,9 @@ bool MIParser::getRegisterByName(StringRef RegName, unsigned &Reg) {
   return false;
 }
 
-MachineInstr *llvm::parseMachineInstr(SourceMgr &SM, MachineFunction &MF,
-                                      StringRef Src, SMDiagnostic &Error) {
-  return MIParser(SM, MF, Error, Src).parse();
+MachineInstr *
+llvm::parseMachineInstr(SourceMgr &SM, MachineFunction &MF, StringRef Src,
+                        const DenseMap<unsigned, MachineBasicBlock *> &MBBSlots,
+                        SMDiagnostic &Error) {
+  return MIParser(SM, MF, Error, Src, MBBSlots).parse();
 }
diff --git a/llvm/lib/CodeGen/MIRParser/MIParser.h b/llvm/lib/CodeGen/MIRParser/MIParser.h
index b55d70a199b..5bb0570856c 100644
--- a/llvm/lib/CodeGen/MIRParser/MIParser.h
+++ b/llvm/lib/CodeGen/MIRParser/MIParser.h
@@ -14,17 +14,21 @@
 #ifndef LLVM_LIB_CODEGEN_MIRPARSER_MIPARSER_H
 #define LLVM_LIB_CODEGEN_MIRPARSER_MIPARSER_H
 
+#include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/StringRef.h"
 
 namespace llvm {
 
+class MachineBasicBlock;
 class MachineInstr;
 class MachineFunction;
 class SMDiagnostic;
 class SourceMgr;
 
-MachineInstr *parseMachineInstr(SourceMgr &SM, MachineFunction &MF,
-                                StringRef Src, SMDiagnostic &Error);
+MachineInstr *
+parseMachineInstr(SourceMgr &SM, MachineFunction &MF, StringRef Src,
+                  const DenseMap<unsigned, MachineBasicBlock *> &MBBSlots,
+                  SMDiagnostic &Error);
 
 } // end namespace llvm
 
diff --git a/llvm/lib/CodeGen/MIRParser/MIRParser.cpp b/llvm/lib/CodeGen/MIRParser/MIRParser.cpp
index 1803116b417..79b2ee6c948 100644
--- a/llvm/lib/CodeGen/MIRParser/MIRParser.cpp
+++ b/llvm/lib/CodeGen/MIRParser/MIRParser.cpp
@@ -14,6 +14,7 @@
 
 #include "llvm/CodeGen/MIRParser/MIRParser.h"
 #include "MIParser.h"
+#include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/ADT/StringMap.h"
 #include "llvm/ADT/STLExtras.h"
@@ -81,8 +82,10 @@ public:
   /// Initialize the machine basic block using it's YAML representation.
   ///
   /// Return true if an error occurred.
-  bool initializeMachineBasicBlock(MachineFunction &MF, MachineBasicBlock &MBB,
-                                   const yaml::MachineBasicBlock &YamlMBB);
+  bool initializeMachineBasicBlock(
+      MachineFunction &MF, MachineBasicBlock &MBB,
+      const yaml::MachineBasicBlock &YamlMBB,
+      const DenseMap<unsigned, MachineBasicBlock *> &MBBSlots);
 
   bool initializeRegisterInfo(MachineRegisterInfo &RegInfo,
                               const yaml::MachineFunction &YamlMF);
@@ -220,6 +223,7 @@ bool MIRParserImpl::initializeMachineFunction(MachineFunction &MF) {
     return true;
 
   const auto &F = *MF.getFunction();
+  DenseMap<unsigned, MachineBasicBlock *> MBBSlots;
   for (const auto &YamlMBB : YamlMF.BasicBlocks) {
     const BasicBlock *BB = nullptr;
     if (!YamlMBB.Name.empty()) {
@@ -231,7 +235,18 @@ bool MIRParserImpl::initializeMachineFunction(MachineFunction &MF) {
     }
     auto *MBB = MF.CreateMachineBasicBlock(BB);
     MF.insert(MF.end(), MBB);
-    if (initializeMachineBasicBlock(MF, *MBB, YamlMBB))
+    bool WasInserted = MBBSlots.insert(std::make_pair(YamlMBB.ID, MBB)).second;
+    if (!WasInserted)
+      return error(Twine("redefinition of machine basic block with id #") +
+                   Twine(YamlMBB.ID));
+  }
+
+  // Initialize the machine basic blocks after creating them all so that the
+  // machine instructions parser can resolve the MBB references.
+  unsigned I = 0;
+  for (const auto &YamlMBB : YamlMF.BasicBlocks) {
+    if (initializeMachineBasicBlock(MF, *MF.getBlockNumbered(I++), YamlMBB,
+                                    MBBSlots))
       return true;
   }
   return false;
@@ -239,7 +254,8 @@ bool MIRParserImpl::initializeMachineFunction(MachineFunction &MF) {
 
 bool MIRParserImpl::initializeMachineBasicBlock(
     MachineFunction &MF, MachineBasicBlock &MBB,
-    const yaml::MachineBasicBlock &YamlMBB) {
+    const yaml::MachineBasicBlock &YamlMBB,
+    const DenseMap<unsigned, MachineBasicBlock *> &MBBSlots) {
   MBB.setAlignment(YamlMBB.Alignment);
   if (YamlMBB.AddressTaken)
     MBB.setHasAddressTaken();
@@ -247,7 +263,7 @@ bool MIRParserImpl::initializeMachineBasicBlock(
   // Parse the instructions.
   for (const auto &MISource : YamlMBB.Instructions) {
     SMDiagnostic Error;
-    if (auto *MI = parseMachineInstr(SM, MF, MISource.Value, Error)) {
+    if (auto *MI = parseMachineInstr(SM, MF, MISource.Value, MBBSlots, Error)) {
       MBB.insert(MBB.end(), MI);
       continue;
     }
diff --git a/llvm/lib/CodeGen/MIRPrinter.cpp b/llvm/lib/CodeGen/MIRPrinter.cpp
index 5d13890e1ab..f9595f88b0b 100644
--- a/llvm/lib/CodeGen/MIRPrinter.cpp
+++ b/llvm/lib/CodeGen/MIRPrinter.cpp
@@ -81,7 +81,15 @@ void MIRPrinter::print(const MachineFunction &MF) {
   YamlMF.ExposesReturnsTwice = MF.exposesReturnsTwice();
   YamlMF.HasInlineAsm = MF.hasInlineAsm();
   convert(YamlMF, MF.getRegInfo());
+
+  int I = 0;
   for (const auto &MBB : MF) {
+    // TODO: Allow printing of non sequentially numbered MBBs.
+    // This is currently needed as the basic block references get their index
+    // from MBB.getNumber(), thus it should be sequential so that the parser can
+    // map back to the correct MBBs when parsing the output.
+    assert(MBB.getNumber() == I++ &&
+           "Can't print MBBs that aren't sequentially numbered");
     yaml::MachineBasicBlock YamlMBB;
     convert(YamlMBB, MBB);
     YamlMF.BasicBlocks.push_back(YamlMBB);
@@ -99,6 +107,8 @@ void MIRPrinter::convert(yaml::MachineFunction &MF,
 
 void MIRPrinter::convert(yaml::MachineBasicBlock &YamlMBB,
                          const MachineBasicBlock &MBB) {
+  assert(MBB.getNumber() >= 0 && "Invalid MBB number");
+  YamlMBB.ID = (unsigned)MBB.getNumber();
   // TODO: Serialize unnamed BB references.
   if (const auto *BB = MBB.getBasicBlock())
     YamlMBB.Name = BB->hasName() ? BB->getName() : "<unnamed bb>";
@@ -173,6 +183,13 @@ void MIPrinter::print(const MachineOperand &Op, const TargetRegisterInfo *TRI) {
   case MachineOperand::MO_Immediate:
     OS << Op.getImm();
     break;
+  case MachineOperand::MO_MachineBasicBlock:
+    OS << "%bb." << Op.getMBB()->getNumber();
+    if (const auto *BB = Op.getMBB()->getBasicBlock()) {
+      if (BB->hasName())
+        OS << '.' << BB->getName();
+    }
+    break;
   default:
     // TODO: Print the other machine operands.
     llvm_unreachable("Can't print this machine operand at the moment");
diff --git a/llvm/test/CodeGen/MIR/X86/expected-machine-operand.mir b/llvm/test/CodeGen/MIR/X86/expected-machine-operand.mir
index 685f3bfe31a..3725c93cd3e 100644
--- a/llvm/test/CodeGen/MIR/X86/expected-machine-operand.mir
+++ b/llvm/test/CodeGen/MIR/X86/expected-machine-operand.mir
@@ -11,7 +11,8 @@
 ---
 name:            foo
 body:
- - name:         entry
+ - id:           0
+   name:         entry
    instructions:
      # CHECK: [[@LINE+1]]:24: expected a machine operand
      - '%eax = XOR32rr ='
diff --git a/llvm/test/CodeGen/MIR/X86/expected-number-after-bb.mir b/llvm/test/CodeGen/MIR/X86/expected-number-after-bb.mir
new file mode 100644
index 00000000000..f4248a76be4
--- /dev/null
+++ b/llvm/test/CodeGen/MIR/X86/expected-number-after-bb.mir
@@ -0,0 +1,37 @@
+# RUN: not llc -march=x86-64 -start-after branch-folder -stop-after branch-folder -o /dev/null %s 2>&1 | FileCheck %s
+
+--- |
+
+  define i32 @foo(i32* %p) {
+  entry:
+    %a = load i32, i32* %p
+    %b = icmp sle i32 %a, 10
+    br i1 %b, label %yes, label %nah
+
+  yes:
+    ret i32 0
+
+  nah:
+    ret i32 %a
+  }
+
+...
+---
+name:            foo
+body:
+ - id: 0
+   name:   entry
+   instructions:
+     - '%eax = MOV32rm %rdi, 1, _, 0, _'
+     - 'CMP32ri8 %eax, 10'
+     # CHECK: [[@LINE+1]]:18: expected a number after '%bb.'
+     - 'JG_1 %bb.nah'
+ - id: 1
+   name: yes
+   instructions:
+     - '%eax = MOV32r0'
+ - id: 2
+   name: nah
+   instructions:
+     - 'RETQ %eax'
+...
diff --git a/llvm/test/CodeGen/MIR/X86/immediate-operands.mir b/llvm/test/CodeGen/MIR/X86/immediate-operands.mir
index 6cb3152e7e4..5d4956f539d 100644
--- a/llvm/test/CodeGen/MIR/X86/immediate-operands.mir
+++ b/llvm/test/CodeGen/MIR/X86/immediate-operands.mir
@@ -18,7 +18,8 @@
 # CHECK: name: foo
 name:            foo
 body:
- - name:         entry
+ - id:           0
+   name:         entry
    instructions:
      # CHECK:      - '%eax = MOV32ri 42'
      # CHECK-NEXT: - 'RETQ %eax'
@@ -29,7 +30,8 @@ body:
 # CHECK: name: bar
 name:            bar
 body:
- - name:         entry
+ - id:           0
+   name:         entry
    instructions:
      # CHECK:      - '%eax = MOV32ri -11'
      # CHECK-NEXT: - 'RETQ %eax'
diff --git a/llvm/test/CodeGen/MIR/X86/large-index-number-error.mir b/llvm/test/CodeGen/MIR/X86/large-index-number-error.mir
new file mode 100644
index 00000000000..61a5bdfe2ed
--- /dev/null
+++ b/llvm/test/CodeGen/MIR/X86/large-index-number-error.mir
@@ -0,0 +1,35 @@
+# RUN: not llc -march=x86-64 -start-after branch-folder -stop-after branch-folder -o /dev/null %s 2>&1 | FileCheck %s
+
+--- |
+
+  define i32 @foo(i32* %p) {
+  entry:
+    %a = load i32, i32* %p
+    %b = icmp sle i32 %a, 10
+    br i1 %b, label %0, label %1
+
+  ; <label>:0
+    ret i32 0
+
+  ; <label>:1
+    ret i32 %a
+  }
+
+...
+---
+name:            foo
+body:
+ - id: 0
+   name: entry
+   instructions:
+     - '%eax = MOV32rm %rdi, 1, _, 0, _'
+     - 'CMP32ri8 %eax, 10'
+     # CHECK: [[@LINE+1]]:14: expected 32-bit integer (too large)
+     - 'JG_1 %bb.123456789123456'
+ - id: 1
+   instructions:
+     - '%eax = MOV32r0'
+ - id: 2
+   instructions:
+     - 'RETQ %eax'
+...
diff --git a/llvm/test/CodeGen/MIR/X86/machine-basic-block-operands.mir b/llvm/test/CodeGen/MIR/X86/machine-basic-block-operands.mir
new file mode 100644
index 00000000000..9d1bd0bd58a
--- /dev/null
+++ b/llvm/test/CodeGen/MIR/X86/machine-basic-block-operands.mir
@@ -0,0 +1,75 @@
+# RUN: llc -march=x86-64 -start-after branch-folder -stop-after branch-folder -o /dev/null %s | FileCheck %s
+# This test ensures that the MIR parser parses machine basic block operands.
+
+--- |
+
+  define i32 @foo(i32* %p) {
+  entry:
+    %a = load i32, i32* %p
+    %0 = icmp sle i32 %a, 10
+    br i1 %0, label %less, label %exit
+
+  less:
+    ret i32 0
+
+  exit:
+    ret i32 %a
+  }
+
+  define i32 @bar(i32* %p) {
+  entry:
+    %a = load i32, i32* %p
+    %b = icmp sle i32 %a, 10
+    br i1 %b, label %0, label %1
+
+  ; <label>:0
+    ret i32 0
+
+  ; <label>:1
+    ret i32 %a
+  }
+
+...
+---
+# CHECK: name: foo
+name:            foo
+body:
+ # CHECK: name: entry
+ - id:              0
+   name:            entry
+   instructions:
+     - '%eax = MOV32rm %rdi, 1, _, 0, _'
+     # CHECK:      - 'CMP32ri8 %eax, 10
+     # CHECK-NEXT: - 'JG_1 %bb.2.exit
+     - 'CMP32ri8 %eax, 10'
+     - 'JG_1 %bb.2.exit'
+ # CHECK: name: less
+ - id:              1
+   name:            less
+   instructions:
+     - '%eax = MOV32r0'
+ - id:              2
+   name:            exit
+   instructions:
+     - 'RETQ %eax'
+...
+---
+# CHECK: name: bar
+name:            bar
+body:
+ # CHECK: name: entry
+ - id: 0
+   name: entry
+   instructions:
+     - '%eax = MOV32rm %rdi, 1, _, 0, _'
+     # CHECK:      - 'CMP32ri8 %eax, 10
+     # CHECK-NEXT: - 'JG_1 %bb.2
+     - 'CMP32ri8 %eax, 10'
+     - 'JG_1 %bb.3'
+ - id: 1
+   instructions:
+     - '%eax = MOV32r0'
+ - id: 3
+   instructions:
+     - 'RETQ %eax'
+...
diff --git a/llvm/test/CodeGen/MIR/X86/machine-instructions.mir b/llvm/test/CodeGen/MIR/X86/machine-instructions.mir
index a78cd57e9b6..b743198cf27 100644
--- a/llvm/test/CodeGen/MIR/X86/machine-instructions.mir
+++ b/llvm/test/CodeGen/MIR/X86/machine-instructions.mir
@@ -15,7 +15,8 @@
 # CHECK: name: inc
 name:            inc
 body:
- - name:         entry
+ - id:           0
+   name:         entry
    instructions:
      # CHECK:      - IMUL32rri8
      # CHECK-NEXT: - RETQ
diff --git a/llvm/test/CodeGen/MIR/X86/missing-comma.mir b/llvm/test/CodeGen/MIR/X86/missing-comma.mir
index dc06a87dc4b..54c67ac6c91 100644
--- a/llvm/test/CodeGen/MIR/X86/missing-comma.mir
+++ b/llvm/test/CodeGen/MIR/X86/missing-comma.mir
@@ -11,7 +11,8 @@
 ---
 name:            foo
 body:
- - name:         entry
+ - id:           0
+   name:         entry
    instructions:
      # CHECK: [[@LINE+1]]:29: expected ',' before the next machine operand
      - '%eax = XOR32rr %eax %eflags'
diff --git a/llvm/test/CodeGen/MIR/X86/missing-instruction.mir b/llvm/test/CodeGen/MIR/X86/missing-instruction.mir
index e18b667bae4..8d11ab5eaab 100644
--- a/llvm/test/CodeGen/MIR/X86/missing-instruction.mir
+++ b/llvm/test/CodeGen/MIR/X86/missing-instruction.mir
@@ -11,7 +11,8 @@
 ---
 name:            foo
 body:
- - name:         entry
+ - id:           0
+   name:         entry
    instructions:
      # CHECK: [[@LINE+1]]:9: expected a machine instruction
      - ''
diff --git a/llvm/test/CodeGen/MIR/X86/named-registers.mir b/llvm/test/CodeGen/MIR/X86/named-registers.mir
index 38edc17fa32..5defb8489e1 100644
--- a/llvm/test/CodeGen/MIR/X86/named-registers.mir
+++ b/llvm/test/CodeGen/MIR/X86/named-registers.mir
@@ -13,7 +13,8 @@
 # CHECK: name: foo
 name:            foo
 body:
- - name:         entry
+ - id:           0
+   name:         entry
    instructions:
      # CHECK:      - '%eax = MOV32r0
      # CHECK-NEXT: - 'RETQ %eax
diff --git a/llvm/test/CodeGen/MIR/X86/null-register-operands.mir b/llvm/test/CodeGen/MIR/X86/null-register-operands.mir
index 7946649cfb1..55c0ceb3a60 100644
--- a/llvm/test/CodeGen/MIR/X86/null-register-operands.mir
+++ b/llvm/test/CodeGen/MIR/X86/null-register-operands.mir
@@ -14,7 +14,8 @@
 # CHECK: name: deref
 name:            deref
 body:
- - name:         entry
+ - id:           0
+   name:         entry
    instructions:
      # CHECK:      - '%eax = MOV32rm %rdi, 1, _, 0, _'
      # CHECK-NEXT: - 'RETQ %eax'
diff --git a/llvm/test/CodeGen/MIR/X86/unknown-instruction.mir b/llvm/test/CodeGen/MIR/X86/unknown-instruction.mir
index 0d1db9f9a3f..4e58ca6bad4 100644
--- a/llvm/test/CodeGen/MIR/X86/unknown-instruction.mir
+++ b/llvm/test/CodeGen/MIR/X86/unknown-instruction.mir
@@ -13,7 +13,8 @@
 ---
 name:            foo
 body:
- - name:         entry
+ - id:           0
+   name:         entry
    instructions:
      # CHECK: [[@LINE+1]]:8: unknown machine instruction name 'retJust0'
      - retJust0
diff --git a/llvm/test/CodeGen/MIR/X86/unknown-machine-basic-block.mir b/llvm/test/CodeGen/MIR/X86/unknown-machine-basic-block.mir
new file mode 100644
index 00000000000..5bc979a83ea
--- /dev/null
+++ b/llvm/test/CodeGen/MIR/X86/unknown-machine-basic-block.mir
@@ -0,0 +1,38 @@
+# RUN: not llc -march=x86-64 -start-after branch-folder -stop-after branch-folder -o /dev/null %s 2>&1 | FileCheck %s
+# This test ensures that an error is reported when an invalid machine basic
+# block index is used.
+
+
+--- |
+
+  define i32 @foo(i32* %p) {
+  entry:
+    %a = load i32, i32* %p
+    %b = icmp sle i32 %a, 10
+    br i1 %b, label %0, label %1
+
+  ; <label>:0
+    ret i32 0
+
+  ; <label>:1
+    ret i32 %a
+  }
+
+...
+---
+name:            foo
+body:
+ - id: 0
+   name:         entry
+   instructions:
+     - '%eax = MOV32rm %rdi, 1, _, 0, _'
+     - 'CMP32ri8 %eax, 10'
+     # CHECK: [[@LINE+1]]:14: use of undefined machine basic block #4
+     - 'JG_1 %bb.4'
+ - id: 1
+   instructions:
+     - '%eax = MOV32r0'
+ - id: 2
+   instructions:
+     - 'RETQ %eax'
+...
diff --git a/llvm/test/CodeGen/MIR/X86/unknown-named-machine-basic-block.mir b/llvm/test/CodeGen/MIR/X86/unknown-named-machine-basic-block.mir
new file mode 100644
index 00000000000..cd8c5402256
--- /dev/null
+++ b/llvm/test/CodeGen/MIR/X86/unknown-named-machine-basic-block.mir
@@ -0,0 +1,39 @@
+# RUN: not llc -march=x86-64 -start-after branch-folder -stop-after branch-folder -o /dev/null %s 2>&1 | FileCheck %s
+# This test ensures that an error is reported when an unknown named machine
+# basic block is encountered.
+
+--- |
+
+  define i32 @foo(i32* %p) {
+  entry:
+    %a = load i32, i32* %p
+    %0 = icmp sle i32 %a, 10
+    br i1 %0, label %less, label %exit
+
+  less:
+    ret i32 0
+
+  exit:
+    ret i32 %a
+  }
+
+...
+---
+name:            foo
+body:
+ - id:              0
+   name:            entry
+   instructions:
+     - '%eax = MOV32rm %rdi, 1, _, 0, _'
+     - 'CMP32ri8 %eax, 10'
+     # CHECK: [[@LINE+1]]:14: the name of machine basic block #2 isn't 'hit'
+     - 'JG_1 %bb.2.hit'
+ - id:              1
+   name:            less
+   instructions:
+     - '%eax = MOV32r0'
+ - id:              2
+   name:            exit
+   instructions:
+     - 'RETQ %eax'
+...
diff --git a/llvm/test/CodeGen/MIR/X86/unknown-register.mir b/llvm/test/CodeGen/MIR/X86/unknown-register.mir
index 59284f99a6d..ce40ee809bf 100644
--- a/llvm/test/CodeGen/MIR/X86/unknown-register.mir
+++ b/llvm/test/CodeGen/MIR/X86/unknown-register.mir
@@ -13,7 +13,8 @@
 ---
 name:            foo
 body:
- - name:         entry
+ - id:           0
+   name:         entry
    instructions:
      # CHECK: [[@LINE+1]]:9: unknown register name 'xax'
      - '%xax = MOV32r0'
diff --git a/llvm/test/CodeGen/MIR/X86/unrecognized-character.mir b/llvm/test/CodeGen/MIR/X86/unrecognized-character.mir
index 0fd504fb5bb..3b4fb1a9fc6 100644
--- a/llvm/test/CodeGen/MIR/X86/unrecognized-character.mir
+++ b/llvm/test/CodeGen/MIR/X86/unrecognized-character.mir
@@ -11,7 +11,8 @@
 ---
 name:            foo
 body:
- - name:         entry
+ - id:           0
+   name:         entry
    instructions:
      # CHECK: [[@LINE+1]]:9: unexpected character '`'
      - '` RETQ'
diff --git a/llvm/test/CodeGen/MIR/basic-blocks.mir b/llvm/test/CodeGen/MIR/basic-blocks.mir
index 43d87507d5d..17313047576 100644
--- a/llvm/test/CodeGen/MIR/basic-blocks.mir
+++ b/llvm/test/CodeGen/MIR/basic-blocks.mir
@@ -17,27 +17,33 @@
 ---
 # CHECK: name: foo
 # CHECK: body:
-# CHECK-NEXT: - name: entry
+# CHECK-NEXT: - id: 0
+# CHECK-NEXT:   name: entry
 # CHECK-NEXT:   alignment: 0
 # CHECK-NEXT:   isLandingPad: false
 # CHECK-NEXT:   addressTaken: false
 name:            foo
 body:
- - name:         entry
+ - id:           0
+   name:         entry
 ...
 ---
 # CHECK: name: bar
 # CHECK: body:
-# CHECK-NEXT: - name: start
+# CHECK-NEXT: - id: 0
+# CHECK-NEXT:   name: start
 # CHECK-NEXT:   alignment: 4
 # CHECK-NEXT:   isLandingPad: false
 # CHECK-NEXT:   addressTaken: false
-# CHECK-NEXT: - alignment: 0
+# CHECK-NEXT: - id: 1
+# CHECK-NEXT:   alignment: 0
 # CHECK-NEXT:   isLandingPad: false
 # CHECK-NEXT:   addressTaken: true
 name:            bar
 body:
- - name:         start
+ - id:           0
+   name:         start
    alignment:    4
- - addressTaken: true
+ - id:           1
+   addressTaken: true
 ...
diff --git a/llvm/test/CodeGen/MIR/machine-basic-block-redefinition-error.mir b/llvm/test/CodeGen/MIR/machine-basic-block-redefinition-error.mir
new file mode 100644
index 00000000000..deac3b0b69b
--- /dev/null
+++ b/llvm/test/CodeGen/MIR/machine-basic-block-redefinition-error.mir
@@ -0,0 +1,17 @@
+# RUN: not llc -start-after branch-folder -stop-after branch-folder -o /dev/null %s 2>&1 | FileCheck %s
+
+--- |
+
+  define i32 @foo() {
+  entry:
+    ret i32 0
+  }
+
+...
+---
+name:            foo
+body:
+  # CHECK: redefinition of machine basic block with id #0
+  - id:       0
+  - id:       0
+...
diff --git a/llvm/test/CodeGen/MIR/machine-basic-block-unknown-name.mir b/llvm/test/CodeGen/MIR/machine-basic-block-unknown-name.mir
index 4c363c69edb..ed675c5edbc 100644
--- a/llvm/test/CodeGen/MIR/machine-basic-block-unknown-name.mir
+++ b/llvm/test/CodeGen/MIR/machine-basic-block-unknown-name.mir
@@ -14,5 +14,6 @@
 name:            foo
 body:
   # CHECK: basic block 'entrie' is not defined in the function 'foo'
-  - name:         entrie
+  - id:          0
+    name:        entrie
 ...