[MachineVerifier] Add more checks for registers in live-in lists.

[efriedma]

Summary

Excluding landing pads, a register that's live-in should be live-out of each of its predecessors. Expand the check for this to include allocatable registers, and registers with aliases.

We do a relatively relaxed check for registers with aliases: some register that aliases the register in question must be live-out of each predecessor. In some cases, it might make sense to try to do something more strict, but this is enough to catch a lot of interesting cases.

Currently guarded by a flag because a bunch of targets have at least one regression test failure with this and expensive checks enabled. In particular, there are failures for AArch64, AMDGPU, ARM, Hexagon, Mips, PowerPC, RISC-V, SystemZ, and X86. I'd appreciate if people working with those targets would look into this.

SystemZ only fails on one MIR test, and I think that's a bug in the test, not the backend. The other backends appear to have at least one real bug.

There's a cluster of failures involving code failing to compute live-ins correctly when expanding atomic pseudo-instructions. This affects the ARM, Mips, and RISC-V backend. Might make sense to address them together, even though the code is separate.

For x86, one of the failing tests involves callbr; maybe related to D75098?

Complete list of failures, for reference:

Failed Tests (103):

LLVM :: CodeGen/AArch64/GlobalISel/regbank-assert-sext.mir
LLVM :: CodeGen/AArch64/GlobalISel/regbank-assert-zext.mir
LLVM :: CodeGen/AArch64/framelayout-scavengingslot.mir
LLVM :: CodeGen/AArch64/framelayout-sve-scavengingslot.mir
LLVM :: CodeGen/AArch64/jump-table-duplicate.mir
LLVM :: CodeGen/AArch64/machine-outliner-retaddr-sign-regsave.mir
LLVM :: CodeGen/AMDGPU/constant-fold-imm-immreg.mir
LLVM :: CodeGen/AMDGPU/cross-block-use-is-not-abi-copy.ll
LLVM :: CodeGen/AMDGPU/fold-immediate-operand-shrink.mir
LLVM :: CodeGen/AMDGPU/frame-lowering-fp-adjusted.mir
LLVM :: CodeGen/AMDGPU/global_smrd_cfg.ll
LLVM :: CodeGen/AMDGPU/post-ra-sched-reset.mir
LLVM :: CodeGen/AMDGPU/si-lower-control-flow.mir
LLVM :: CodeGen/AMDGPU/skip-if-dead.ll
LLVM :: CodeGen/ARM/cmse-expand-bxns-ret.mir
LLVM :: CodeGen/ARM/machine-outliner-default.mir
LLVM :: CodeGen/ARM/machine-outliner-lr-regsave.mir
LLVM :: CodeGen/ARM/machine-outliner-stack-use.mir
LLVM :: CodeGen/Hexagon/Atomics.ll
LLVM :: CodeGen/Hexagon/aggr-licm.ll
LLVM :: CodeGen/Hexagon/bit-extract-off.ll
LLVM :: CodeGen/Hexagon/check-subregister-for-latency.ll
LLVM :: CodeGen/Hexagon/concat-vectors-legalize.ll
LLVM :: CodeGen/Hexagon/deflate.ll
LLVM :: CodeGen/Hexagon/frame-offset-overflow.ll
LLVM :: CodeGen/Hexagon/i128-bitop.ll
LLVM :: CodeGen/Hexagon/packetize-impdef-1.ll
LLVM :: CodeGen/Hexagon/reg-scav-imp-use-dbl-vec.ll
LLVM :: CodeGen/Hexagon/reg-scavengebug-2.ll
LLVM :: CodeGen/Hexagon/reg-scavengebug-4.ll
LLVM :: CodeGen/Hexagon/remove_lsr.ll
LLVM :: CodeGen/Hexagon/swp-conv3x3-nested.ll
LLVM :: CodeGen/Hexagon/swp-epilog-phi6.ll
LLVM :: CodeGen/Hexagon/swp-epilog-phi7.ll
LLVM :: CodeGen/Hexagon/swp-order-carried.ll
LLVM :: CodeGen/Hexagon/swp-order-deps6.ll
LLVM :: CodeGen/Hexagon/swp-reuse-phi-4.ll
LLVM :: CodeGen/Hexagon/swp-reuse-phi-6.ll
LLVM :: CodeGen/Hexagon/swp-sigma.ll
LLVM :: CodeGen/Hexagon/v6-spill1.ll
LLVM :: CodeGen/Hexagon/v60-cur.ll
LLVM :: CodeGen/Hexagon/v60-vecpred-spill.ll
LLVM :: CodeGen/Hexagon/v60Vasr.ll
LLVM :: CodeGen/Hexagon/vect-regpairs.ll
LLVM :: CodeGen/Hexagon/vect/vect-cst-v4i8.ll
LLVM :: CodeGen/Hexagon/vect/vect-cst.ll
LLVM :: CodeGen/Hexagon/vect/vect-vsplatb.ll
LLVM :: CodeGen/Hexagon/vect/vect-xor.ll
LLVM :: CodeGen/Mips/atomic-min-max.ll
LLVM :: CodeGen/Mips/atomic.ll
LLVM :: CodeGen/Mips/atomic64.ll
LLVM :: CodeGen/Mips/atomicCmpSwapPW.ll
LLVM :: CodeGen/Mips/micromips-atomic1.ll
LLVM :: CodeGen/PowerPC/ctrloop-sums.ll
LLVM :: CodeGen/PowerPC/ppcf128-freeze.mir
LLVM :: CodeGen/PowerPC/pr46759.ll
LLVM :: CodeGen/PowerPC/select-i1-vs-i1.ll
LLVM :: CodeGen/PowerPC/stack-clash-prologue.ll
LLVM :: CodeGen/PowerPC/urem-seteq-illegal-types.ll
LLVM :: CodeGen/RISCV/atomic-cmpxchg-flag.ll
LLVM :: CodeGen/RISCV/atomic-cmpxchg.ll
LLVM :: CodeGen/RISCV/atomic-rmw.ll
LLVM :: CodeGen/RISCV/atomic-signext.ll
LLVM :: CodeGen/RISCV/shrinkwrap.ll
LLVM :: CodeGen/Thumb/thumb-shrink-wrapping.ll
LLVM :: CodeGen/Thumb2/LowOverheadLoops/dont-remove-loop-update.mir
LLVM :: CodeGen/Thumb2/LowOverheadLoops/emptyblock.mir
LLVM :: CodeGen/Thumb2/LowOverheadLoops/incorrect-sub-16.mir
LLVM :: CodeGen/Thumb2/LowOverheadLoops/incorrect-sub-32.mir
LLVM :: CodeGen/Thumb2/LowOverheadLoops/incorrect-sub-8.mir
LLVM :: CodeGen/Thumb2/LowOverheadLoops/iv-vcmp.mir
LLVM :: CodeGen/Thumb2/LowOverheadLoops/massive.mir
LLVM :: CodeGen/Thumb2/LowOverheadLoops/mov-lr-terminator.mir
LLVM :: CodeGen/Thumb2/LowOverheadLoops/move-def-before-start.mir
LLVM :: CodeGen/Thumb2/LowOverheadLoops/move-start-after-def.mir
LLVM :: CodeGen/Thumb2/LowOverheadLoops/multi-cond-iter-count.mir
LLVM :: CodeGen/Thumb2/LowOverheadLoops/multiblock-massive.mir
LLVM :: CodeGen/Thumb2/LowOverheadLoops/non-masked-store.mir
LLVM :: CodeGen/Thumb2/LowOverheadLoops/safe-retaining.mir
LLVM :: CodeGen/Thumb2/LowOverheadLoops/size-limit.mir
LLVM :: CodeGen/Thumb2/LowOverheadLoops/tail-pred-disabled-in-loloops.ll
LLVM :: CodeGen/Thumb2/LowOverheadLoops/unpredicated-max.mir
LLVM :: CodeGen/Thumb2/LowOverheadLoops/unsafe-retaining.mir
LLVM :: CodeGen/Thumb2/LowOverheadLoops/vaddv.mir
LLVM :: CodeGen/Thumb2/LowOverheadLoops/vcmp-vpst-combination-across-blocks.mir
LLVM :: CodeGen/Thumb2/LowOverheadLoops/vctp-subi3.mir
LLVM :: CodeGen/Thumb2/LowOverheadLoops/vctp-subri.mir
LLVM :: CodeGen/Thumb2/LowOverheadLoops/vctp-subri12.mir
LLVM :: CodeGen/Thumb2/LowOverheadLoops/vpt-blocks.mir
LLVM :: CodeGen/Thumb2/block-placement.mir
LLVM :: CodeGen/Thumb2/mve-blockplacement.ll
LLVM :: CodeGen/Thumb2/mve-postinc-dct.ll
LLVM :: CodeGen/X86/2009-07-15-CoalescerBug.ll
LLVM :: CodeGen/X86/block-placement.mir
LLVM :: CodeGen/X86/cfi-inserter-callee-save-register-2.mir
LLVM :: CodeGen/X86/dbg-changes-codegen-branch-folding2.mir
LLVM :: CodeGen/X86/icall-branch-funnel.ll
LLVM :: CodeGen/X86/implicit-null-checks.mir
LLVM :: CodeGen/X86/implicit-null-chk-reg-rewrite.mir
LLVM :: CodeGen/X86/leaFixup32.mir
LLVM :: CodeGen/X86/leaFixup64.mir
LLVM :: CodeGen/X86/pr38952.mir
LLVM :: CodeGen/X86/win_coreclr_chkstk_liveins.mir

[arsenm]

llvm/lib/CodeGen/MachineVerifier.cpp

84

Probably should add a fixme to remove this when everything passes

2464–2474

Usual pattern uses a for loop with the MCReg* iterators

[ZhangKang]

Some CodeGen Passes or Target Passes has disabled Machine Verification. There are 23 CodeGen passes has disabled Machine Verification in TargetPassConfig.cpp.
If we enable Machine Verification for all passes, we will found more failed cases for liveness, it will expose more bugs..

[efriedma]

There are 23 CodeGen passes has disabled Machine Verification in TargetPassConfig.cpp.

Committed https://github.com/llvm/llvm-project/commit/46a52ff9eda0750ff05311310774d954bcaf3408 to get rid of nine of them.

It looks like AMDGPU, Hexagon, MSP430, and PowerPC have issues with verification after addPreEmitPass. The AMDGPU and Hexagon issues look weird at first glance, but the PowerPC issues looked like simple mistakes with liveness in target-specific passes; you could probably go through and fix them quickly.

[ZhangKang]

This comment was removed by ZhangKang.

llvm/lib/CodeGen/MachineVerifier.cpp

2453

In the file lib/CodeGen/LivePhysRegs.cpp:

57 /// Add uses to the set.
58 void LivePhysRegs::addUses(const MachineInstr &MI) {
59   for (const MachineOperand &MOP : phys_regs_and_masks(MI)) {
60     if (!MOP.isReg() || !MOP.readsReg())
61       continue;
62     addReg(MOP.getReg());
63   }
64 }
65
66 /// Simulates liveness when stepping backwards over an instruction(bundle):
67 /// Remove Defs, add uses. This is the recommended way of calculating liveness.
68 void LivePhysRegs::stepBackward(const MachineInstr &MI) {
69   // Remove defined registers and regmask kills from the set.
70   removeDefs(MI);
71
72   // Add uses to the set.
73   addUses(MI);
74 }

When we calculate the liveness by using the method stepBackend, we have added the reserved registers into the liveness in addUses, but here, we don't track the reserved registers. Are the addUses and the verification correct?

[ZhangKang]

I have create https://reviews.llvm.org/D78657 for PowerPC ppc-expand-isel pass, and I have use your patch to test D78657.
Before using D78657, there are 57 PowerPC cases failed, after using D78657,, 49 cases can pass, and the left 8 cases should be the cases issue.
Your patch is very useful to check the pass and can find the cases issue conveniently.
For powerpc, I think machine-verifier-strict-livein can enable soon.

[efriedma]

llvm/lib/CodeGen/MachineVerifier.cpp

2453

If you look at other APIs, like available(), it intentionally ignores reserved registers. Maybe we should try to do something more complete, but in general it doesn't make sense to track liveness for such registers. (For example, the stack pointer has external constraints on what it can contain, which can't be understood using normal liveness rules.)

[efriedma]

Address review comments

[kparzysz]

I don't have a build with expensive checks enabled at the moment, but I fixed 3 Hexagon testcases that fail with this change and without expensive checks: d8e1dd8b9b6554b750b6727a521c28b58ae79c1f.

[efriedma]

You can quickly get a build that acts like an "expensive checks" build in this context by just commenting out the "#ifdef EXPENSIVE_CHECKS" in llvm/lib/CodeGen/TargetPassConfig.cpp.

[kparzysz]

There are some bugs that I need to fix here. I'll work on this in between other stuff...

[jonpa]

The SystemZ test case seem to contain some bad kill flags - I will fix it shortly.

I wonder why it is now enough to only have one alias of a register live out from each predecessor. I would have expected that if not the same register is live out, then a super register or all of its sub-registers must be live out. As this patch looks now, there could be a subreg missing... Perhaps at least add a comment mentioning this?

[efriedma]

Address review comment

[nickdesaulniers]

llvm/lib/CodeGen/MachineVerifier.cpp

2466

does this AliasingRegs shadow AliasingRegs declared on line 2470?

2472

looks like llvm::any_of can be used here?

[efriedma]

llvm/lib/CodeGen/MachineVerifier.cpp

2466

Oh, oops, I didn't mean to declare it twice.

2472

There isn't any way to construct a range out of an MCRegAliasIterator; there isn't any end iterator.

[efriedma]

Fix review comment

[ZhangKang]

PowerPC failed cases has been cleaned.

[RKSimon]

@efriedma Please can you rebase and update the fail list?

[efriedma]

Updated fail list. Mostly the same except a bunch of PPC failures were fixed. I won't bother uploading the rebased version; this still applies cleanly.

[arsenm]

llvm/lib/CodeGen/MachineVerifier.cpp

2465–2466

Probably should do this in terms of live-in / live-out regunits?

[efriedma]

Updated list of failures; it's now going up...

I guess the only way we're going to actually make any progress on this is to land the verifier check, and explicitly disable it on the failing tests.

[lenary]

Writing a comment here, so others know I'm looking into it: I spent some time looking at the CodeGen/ARM/cmse-expand-bxns-ret.mir test, and trying it from LLVM IR as well - the latter passes, and if I take the mir as printed before the relevant pass from that test, the test fails. I think this is because the isReserved test is different *after* regalloc, where the reserved registers are saved into the MachineRegisterInfo for the MachineFunction. I *think* serializing them when printing the MIR might solve this bug, so I'm looking into implementing that. Not sure when I'll next make progress though.

[arsenm]

I think a better solution is to just stop using live in registers. These should really be tracking live in register units. The register units are the fundamental unit of liveness tracking, register aliases are an old, clunky, error prone broadcast of the information which is really tracked per-regunit

llvm/lib/CodeGen/MachineVerifier.cpp

 #include <cstddef>
 #include <cstdint>
 #include <iterator>
 #include <string>
 #include <utility>
 
 using namespace llvm;
 
+// FIXME: This is a temporary flag while backends are fixed; we shouldn't
+// need to turn off this check.
+static cl::opt<bool> VerifierStrictLivein(
+    "machine-verifier-strict-livein", cl::Hidden,
+    cl::desc("Enable strict verification of basic block live-ins"),
+    cl::init(false));
+
 namespace {
 
   struct MachineVerifier {
     MachineVerifier(Pass *pass, const char *b) : PASS(pass), Banner(b) {}
 
     unsigned verify(MachineFunction &MF);
 
     Pass *const PASS;
if (LiveVars)
     verifyLiveVariables();
   if (LiveInts)
     verifyLiveIntervals();
 
   // Check live-in list of each MBB. If a register is live into MBB, check
   // that the register is in regsLiveOut of each predecessor block. Since
   // this must come from a definition in the predecesssor or its live-in
   // list, this will catch a live-through case where the predecessor does not
-  // have the register in its live-in list.  This currently only checks
-  // registers that have no aliases, are not allocatable and are not
-  // reserved, which could mean a condition code register for instance.
-  if (MRI->tracksLiveness())
-    for (const auto &MBB : *MF)
+  // have the register in its live-in list.
+  if (MRI->tracksLiveness()) {
+    for (const auto &MBB : *MF) {
+      if (MBB.isEHPad())
+        continue;
       for (MachineBasicBlock::RegisterMaskPair P : MBB.liveins()) {
         MCPhysReg LiveInReg = P.PhysReg;
+
+        // We don't track liveness for reserved registers.
+        if (isReserved(LiveInReg))
+          continue;
+
+        // Strict checking of allocatable/aliased registers is controlled by
+        // a flag to deal with regression test failures.
         bool hasAliases = MCRegAliasIterator(LiveInReg, TRI, false).isValid();
-        if (hasAliases || isAllocatable(LiveInReg) || isReserved(LiveInReg))
+        if (!VerifierStrictLivein && (hasAliases || isAllocatable(LiveInReg)))
           continue;
+
         for (const MachineBasicBlock *Pred : MBB.predecessors()) {
           BBInfo &PInfo = MBBInfoMap[Pred];
-          if (!PInfo.regsLiveOut.count(LiveInReg)) {
+          MCRegAliasIterator AliasingRegs(LiveInReg, TRI, true);
+          bool FoundPred = false;
+          for (MCRegAliasIterator AliasingRegs(LiveInReg, TRI, true);
+               AliasingRegs.isValid(); ++AliasingRegs) {
+            if (PInfo.regsLiveOut.count(*AliasingRegs)) {
+              FoundPred = true;
+              break;
+            }
+          }
+          if (!FoundPred) {
             report("Live in register not found to be live out from predecessor.",
                    &MBB);
             errs() << TRI->getName(LiveInReg)
                    << " not found to be live out from "
                    << printMBBReference(*Pred) << "\n";
           }
         }
       }
+    }
+  }
 
   for (auto CSInfo : MF->getCallSitesInfo())
     if (!CSInfo.first->isCall())
       report("Call site info referencing instruction that is not call", MF);
 }
 
 void MachineVerifier::verifyLiveVariables() {
   assert(LiveVars && "Don't call verifyLiveVariables without LiveVars");