[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:

Failing Tests (66):

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/ARM/cmpxchg-O0.ll
LLVM :: CodeGen/ARM/cmse-expand-bxns-ret.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/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-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/Hexagon/vmpa-halide-test.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/select-i1-vs-i1.ll
LLVM :: CodeGen/RISCV/atomic-cmpxchg-flag.ll
LLVM :: CodeGen/RISCV/atomic-cmpxchg.ll
LLVM :: CodeGen/RISCV/atomic-rmw.ll
LLVM :: CodeGen/RISCV/shrinkwrap.ll
LLVM :: CodeGen/Thumb/thumb-shrink-wrapping.ll
LLVM :: CodeGen/Thumb2/LowOverheadLoops/vpt-blocks.mir
LLVM :: CodeGen/X86/2009-07-15-CoalescerBug.ll
LLVM :: CodeGen/X86/block-placement.mir
LLVM :: CodeGen/X86/callbr-asm-outputs.ll
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
LLVM :: DebugInfo/MIR/ARM/subregister-full-piece.mir
LLVM :: DebugInfo/MIR/X86/live-debug-values-reg-copy.mir
LLVM :: DebugInfo/X86/live-debug-values-constprop.mir

[arsenm]

llvm/lib/CodeGen/MachineVerifier.cpp

84

Probably should add a fixme to remove this when everything passes

2462–2464

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

2451

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

2451

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

2464

does this AliasingRegs shadow AliasingRegs declared on line 2470?

2470

looks like llvm::any_of can be used here?

[efriedma]

llvm/lib/CodeGen/MachineVerifier.cpp

2464

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

2470

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.