Simplify MachineVerifier's block-successor verification.

[jyknight]

Summary

There's two properties we want to verify:

1. That the successors returned by analyzeBranch are in the CFG successor list, and
2. That there are no extraneous successors are in the CFG successor list.

The previous implementation mostly accomplished this, but in a very
convoluted manner.

[arsenm]

LGTM with nits

llvm/lib/CodeGen/MachineVerifier.cpp

695

Braces

699

Braces

727

Capitalize

[nickdesaulniers]

Admittedly, I found this code to be a rats nest. Thanks for making it slightly neater. LGTM

llvm/lib/CodeGen/MachineVerifier.cpp

695

Why? The body is single statement.

712

It's weird seeing the bool && <sub expr that made up the bool>. Maybe

if (!Cond.empty() && !FBB) {

Then you could lower the declaration of Fallthrough closer to its use below?

[arsenm]

llvm/lib/CodeGen/MachineVerifier.cpp

695

Spanning multiple lines

[aheejin]

llvm/test/CodeGen/WebAssembly/eh-labels.mir

32

In this case, the next BB is an EH pad where we unwind to in case @foo throws, so the bb.2 becomes a fallthrough. Does this patch not handle this case?

[jyknight]

llvm/test/CodeGen/WebAssembly/eh-labels.mir

32

Sorry, I don't follow. There's no magic behavior of "just skip over ehpad blocks and fallthrough into the next block after it."

bb.0 says it falls through into bb.2, but the instruction stream and block layout shows a fall-through into bb.1. That's now properly detected as invalid by the verifier, but was missed before.

Normally, blocks would be placed, so as not to have EHPad blocks in the middle of a potential fallthrough (e.g. moving bb.1 to the end of the function), but given the block placement specified in this test, there should be an explicit jump around the ehpad block.

[jyknight]

Fix nits.

llvm/lib/CodeGen/MachineVerifier.cpp

695

I'm pretty sure that's not an llvm style rule, so I'm going to leave it as is. All the existing code here is like that.

712

I like the first half of your suggestion, so done. But I think the description flows better to leave the definition of fallthrough where it is.

llvm/test/CodeGen/WebAssembly/eh-labels.mir

32

(Or alternatively, if @foo was a noreturn call, then bb.2 should not be marked as a successor of bb.0)

[jyknight]

Oops, actually upload changed version. :)

llvm/lib/CodeGen/MachineVerifier.cpp

void MachineVerifier::visitMachineFunctionBefore() {
 
   // Check that the register use lists are sane.
   MRI->verifyUseLists();
 
   if (!MF->empty())
     verifyStackFrame();
 }
 
-// Does iterator point to a and b as the first two elements?
-static bool matchPair(MachineBasicBlock::const_succ_iterator i,
-                      const MachineBasicBlock *a, const MachineBasicBlock *b) {
-  if (*i == a)
-    return *++i == b;
-  if (*i == b)
-    return *++i == a;
-  return false;
-}
-
 void
 MachineVerifier::visitMachineBasicBlockBefore(const MachineBasicBlock *MBB) {
   FirstTerminator = nullptr;
   FirstNonPHI = nullptr;
 
   if (!MF->getProperties().hasProperty(
       MachineFunctionProperties::Property::NoPHIs) && MRI->tracksLiveness()) {
     // If this block has allocatable physical registers live-in, check that
if (!FunctionBlocks.count(succ))
       report("MBB has successor that isn't part of the function.", MBB);
     if (!MBBInfoMap[succ].Preds.count(MBB)) {
       report("Inconsistent CFG", MBB);
       errs() << "MBB is not in the predecessor list of the successor "
              << printMBBReference(*succ) << ".\n";
     }
   }
 
-  // Count the number of INLINEASM_BR indirect target successors.
-  SmallPtrSet<const MachineBasicBlock*, 4> IndirectTargetSuccs;
-  for (const auto *succ : MBB->successors()) {
-    if (MBB->isInlineAsmBrIndirectTarget(succ))
-      IndirectTargetSuccs.insert(succ);
-    if (!FunctionBlocks.count(succ))
-      report("MBB has successor that isn't part of the function.", MBB);
-    if (!MBBInfoMap[succ].Preds.count(MBB)) {
-      report("Inconsistent CFG", MBB);
-      errs() << "MBB is not in the predecessor list of the successor "
-             << printMBBReference(*succ) << ".\n";
-    }
-  }
-
   // Check the predecessor list.
   for (const MachineBasicBlock *Pred : MBB->predecessors()) {
     if (!FunctionBlocks.count(Pred))
       report("MBB has predecessor that isn't part of the function.", MBB);
     if (!MBBInfoMap[Pred].Succs.count(MBB)) {
       report("Inconsistent CFG", MBB);
       errs() << "MBB is not in the successor list of the predecessor "
              << printMBBReference(*Pred) << ".\n";
MachineVerifier::visitMachineBasicBlockBefore(const MachineBasicBlock *MBB) {
   MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
   SmallVector<MachineOperand, 4> Cond;
   if (!TII->analyzeBranch(*const_cast<MachineBasicBlock *>(MBB), TBB, FBB,
                           Cond)) {
     // Ok, analyzeBranch thinks it knows what's going on with this block. Let's
     // check whether its answers match up with reality.
     if (!TBB && !FBB) {
       // Block falls through to its successor.
-      MachineFunction::const_iterator MBBI = std::next(MBB->getIterator());
-      if (MBBI == MF->end()) {
-        // It's possible that the block legitimately ends with a noreturn
-        // call or an unreachable, in which case it won't actually fall
-        // out the bottom of the function.
-      } else if (MBB->succ_size() == LandingPadSuccs.size() ||
-                 MBB->succ_size() == IndirectTargetSuccs.size()) {
-        // It's possible that the block legitimately ends with a noreturn
-        // call or an unreachable, in which case it won't actually fall
-        // out of the block.
-      } else if ((LandingPadSuccs.size() &&
-                  MBB->succ_size() != 1 + LandingPadSuccs.size()) ||
-                 (IndirectTargetSuccs.size() &&
-                  MBB->succ_size() != 1 + IndirectTargetSuccs.size())) {
-        report("MBB exits via unconditional fall-through but doesn't have "
-               "exactly one CFG successor!", MBB);
-      } else if (!MBB->isSuccessor(&*MBBI)) {
-        report("MBB exits via unconditional fall-through but its successor "
-               "differs from its CFG successor!", MBB);
-      }
       if (!MBB->empty() && MBB->back().isBarrier() &&
           !TII->isPredicated(MBB->back())) {
         report("MBB exits via unconditional fall-through but ends with a "
                "barrier instruction!", MBB);
       }
       if (!Cond.empty()) {
         report("MBB exits via unconditional fall-through but has a condition!",
                MBB);
       }
     } else if (TBB && !FBB && Cond.empty()) {
       // Block unconditionally branches somewhere.
-      // If the block has exactly one successor, that happens to be a
-      // landingpad, accept it as valid control flow.
-      if (MBB->succ_size() != 1+LandingPadSuccs.size() &&
-          (MBB->succ_size() != 1 || LandingPadSuccs.size() != 1 ||
-           *MBB->succ_begin() != *LandingPadSuccs.begin()) &&
-          MBB->succ_size() != 1 + IndirectTargetSuccs.size() &&
-          (MBB->succ_size() != 1 || IndirectTargetSuccs.size() != 1 ||
-           *MBB->succ_begin() != *IndirectTargetSuccs.begin())) {
-        report("MBB exits via unconditional branch but doesn't have "
-               "exactly one CFG successor!", MBB);
-      } else if (!MBB->isSuccessor(TBB)) {
-        report("MBB exits via unconditional branch but the CFG "
-               "successor doesn't match the actual successor!", MBB);
-      }
       if (MBB->empty()) {
         report("MBB exits via unconditional branch but doesn't contain "
                "any instructions!", MBB);
       } else if (!MBB->back().isBarrier()) {
         report("MBB exits via unconditional branch but doesn't end with a "
                "barrier instruction!", MBB);
       } else if (!MBB->back().isTerminator()) {
         report("MBB exits via unconditional branch but the branch isn't a "
                "terminator instruction!", MBB);
       }
     } else if (TBB && !FBB && !Cond.empty()) {
       // Block conditionally branches somewhere, otherwise falls through.
-      MachineFunction::const_iterator MBBI = std::next(MBB->getIterator());
-      if (MBBI == MF->end()) {
-        report("MBB conditionally falls through out of function!", MBB);
-      } else if (MBB->succ_size() == 1) {
-        // A conditional branch with only one successor is weird, but allowed.
-        if (&*MBBI != TBB)
-          report("MBB exits via conditional branch/fall-through but only has "
-                 "one CFG successor!", MBB);
-        else if (TBB != *MBB->succ_begin())
-          report("MBB exits via conditional branch/fall-through but the CFG "
-                 "successor don't match the actual successor!", MBB);
-      } else if (MBB->succ_size() != 2) {
-        report("MBB exits via conditional branch/fall-through but doesn't have "
-               "exactly two CFG successors!", MBB);
-      } else if (!matchPair(MBB->succ_begin(), TBB, &*MBBI)) {
-        report("MBB exits via conditional branch/fall-through but the CFG "
-               "successors don't match the actual successors!", MBB);
-      }
       if (MBB->empty()) {
         report("MBB exits via conditional branch/fall-through but doesn't "
                "contain any instructions!", MBB);
       } else if (MBB->back().isBarrier()) {
         report("MBB exits via conditional branch/fall-through but ends with a "
                "barrier instruction!", MBB);
       } else if (!MBB->back().isTerminator()) {
         report("MBB exits via conditional branch/fall-through but the branch "
                "isn't a terminator instruction!", MBB);
       }
     } else if (TBB && FBB) {
       // Block conditionally branches somewhere, otherwise branches
       // somewhere else.
-      if (MBB->succ_size() == 1) {
-        // A conditional branch with only one successor is weird, but allowed.
-        if (FBB != TBB)
-          report("MBB exits via conditional branch/branch through but only has "
-                 "one CFG successor!", MBB);
-        else if (TBB != *MBB->succ_begin())
-          report("MBB exits via conditional branch/branch through but the CFG "
-                 "successor don't match the actual successor!", MBB);
-      } else if (MBB->succ_size() != 2) {
-        report("MBB exits via conditional branch/branch but doesn't have "
-               "exactly two CFG successors!", MBB);
-      } else if (!matchPair(MBB->succ_begin(), TBB, FBB)) {
-        report("MBB exits via conditional branch/branch but the CFG "
-               "successors don't match the actual successors!", MBB);
-      }
       if (MBB->empty()) {
         report("MBB exits via conditional branch/branch but doesn't "
                "contain any instructions!", MBB);
       } else if (!MBB->back().isBarrier()) {
         report("MBB exits via conditional branch/branch but doesn't end with a "
                "barrier instruction!", MBB);
       } else if (!MBB->back().isTerminator()) {
         report("MBB exits via conditional branch/branch but the branch "
                "isn't a terminator instruction!", MBB);
       }
       if (Cond.empty()) {
         report("MBB exits via conditional branch/branch but there's no "
                "condition!", MBB);
       }
     } else {
       report("analyzeBranch returned invalid data!", MBB);
     }
+
+    // Now check that the successors match up with the answers reported by
+    // analyzeBranch.
+    if (TBB && !MBB->isSuccessor(TBB))
+      report("MBB exits via jump or conditional branch, but its target isn't a "
+             "CFG successor!",
+             MBB);
+    if (FBB && !MBB->isSuccessor(FBB))
+      report("MBB exits via conditional branch, but its target isn't a CFG "
+             "successor!",
+             MBB);
+
+    // There might be a fallthrough to the next block if there's either no
+    // unconditional true branch, or if there's a condition, and one of the
+    // branches is missing.
+    bool Fallthrough = !TBB || (!Cond.empty() && !FBB);
+
+    // A conditional fallthrough must be an actual CFG successor, not
+    // unreachable. (Conversely, an unconditional fallthrough might not really
+    // be a successor, because the block might end in unreachable.)
+    if (!Cond.empty() && !FBB) {
+      MachineFunction::const_iterator MBBI = std::next(MBB->getIterator());
+      if (MBBI == MF->end()) {
+        report("MBB conditionally falls through out of function!", MBB);
+      } else if (!MBB->isSuccessor(&*MBBI))
+        report("MBB exits via conditional branch/fall-through but the CFG "
+               "successors don't match the actual successors!",
+               MBB);
+    }
+
+    // Verify that there aren't any extra un-accounted-for successors.
+    for (const MachineBasicBlock *SuccMBB : MBB->successors()) {
+      // If this successor is one of the branch targets, it's okay.
+      if (SuccMBB == TBB || SuccMBB == FBB)
+        continue;
+      // If we might have a fallthrough, and the successor is the fallthrough
+      // block, that's also ok.
+      if (Fallthrough && SuccMBB == MBB->getNextNode())
+        continue;
+      // Also accept successors which are for exception-handling or might be
+      // inlineasm_br targets.
+      if (SuccMBB->isEHPad() || MBB->isInlineAsmBrIndirectTarget(SuccMBB))
+        continue;
+      report("MBB has unexpected successors which are not branch targets, "
+             "fallthrough, EHPads, or inlineasm_br targets.",
+             MBB);
+    }
   }
 
   regsLive.clear();
   if (MRI->tracksLiveness()) {
     for (const auto &LI : MBB->liveins()) {
       if (!Register::isPhysicalRegister(LI.PhysReg)) {
         report("MBB live-in list contains non-physical register", MBB);
         continue;

llvm/test/CodeGen/Hexagon/cext-opt-range-offset.mir

successors: %bb.3, %bb.4
         %4 = IMPLICIT_DEF
         J2_jumpt %4, %bb.4, implicit-def $pc
         J2_jump %bb.3, implicit-def $pc
 
   bb.3:
     successors: %bb.4
 
   bb.4:
-    successors: %bb.4
         %5 = A2_tfrsi -234944521
         %6 = A2_tfrsi -360185632
         L4_and_memopw_io %6, 0, %5
 ...

llvm/test/CodeGen/WebAssembly/eh-labels.mir

bb.0:
     ; CHECK:      TRY
     ; CHECK-NEXT: EH_LABEL
     ; CHECK-NEXT: CALL @foo
     ; CHECK-NEXT: EH_LABEL
     successors: %bb.1, %bb.2
     EH_LABEL <mcsymbol .Ltmp0>
     CALL @foo, implicit-def dead $arguments, implicit $sp32, implicit $sp64
     EH_LABEL <mcsymbol .Ltmp1>
+    BR %bb.2, implicit-def dead $arguments
 
   bb.1 (landing-pad):
   ; predecessors: %bb.0
     successors: %bb.2
     ; CATCH should be after an EH_LABEL at the beginning of an EH pad
     ; CHECK:      EH_LABEL
     ; CHECK-NEXT: CATCH
     EH_LABEL <mcsymbol .Ltmp2>
     dead %0:i32 = EXTRACT_EXCEPTION_I32 implicit-def dead $arguments
     CATCHRET %bb.2, %bb.0, implicit-def dead $arguments
 
   bb.2:
   ; predecessors: %bb.0, %bb.1
     RETURN implicit-def dead $arguments
 ...

llvm/test/MachineVerifier/verifier-pseudo-terminators.mir

 # RUN: not --crash llc -march=amdgcn -run-pass=verify -o - %s 2>&1 | FileCheck %s
 # REQUIRES: amdgpu-registered-target
 
 # Make sure that mismatched successors are caught when a _term
 # instruction is used
 
-# CHECK: *** Bad machine code: MBB exits via unconditional branch but the CFG successor doesn't match the actual successor! ***
+# CHECK: *** Bad machine code: MBB exits via jump or conditional branch, but its target isn't a CFG successor! ***
+# CHECK: *** Bad machine code: MBB has unexpected successors which are not branch targets, fallthrough, EHPads, or inlineasm_br targets. ***
 
 ---
 name: verifier_pseudo_terminators
 body:             |
   bb.0:
     successors: %bb.1
 
     %0:sreg_64 = S_XOR_B64_term undef %1:sreg_64, undef %2:sreg_64, implicit-def $scc