This is an archive of the discontinued LLVM Phabricator instance.

[MBB LiveIn lists, MachineVerifier, SystemZ] New method isLiveOut() and mverifier improvement.
ClosedPublic

Authored by jonpa on Oct 1 2019, 5:54 AM.

Details

Summary

Continuing the discussion from llvm-dev (http://lists.llvm.org/pipermail/llvm-dev/2019-September/135381.html), I am proposing a patch to address this problem.

Background: The SystemZ backend can optimize compare instructions if it can first find all the users of the CC (condition code).
This can only reasonably be done when all the CC users are in the same basic block (to avoid expensive searching), so the first step is to check if the CC register is live into any successor block (live out) or not.

This check is currently done in SystemZElimCompare.cpp, but it would be better to have a common code method for this with an explicit guarantee that this can be trusted.

This patch adds:

  • New method MachineBasicBlock::isLiveOut() that checks the live-in lists of its successors, to replace SystemZElimCompare.cpp:isCCLiveOut(). The comment for it gives a guarantee that this register is not live out of the block if it returns false, while however there is no check for sub/super-registers.
  • MachineVerifier::visitMachineFunctionAfter() extended to check the live-through case for live-in lists, with tests. This is (currently) only done for registers without aliases and that are neither allocatable or reserved, such as the SystemZ::CC register. My hope is that with this, live-in lists for SystemZ::CC is fully verified, as it adds the missing check for live-through. Currently the MachineVerifier only catches the case of a live-in use without an entry in the live-in list, as "using an undefined physical register".

Diff Detail

Event Timeline

jonpa created this revision.Oct 1 2019, 5:54 AM
bjope added a subscriber: bjope.Oct 22 2019, 12:26 PM
bjope added inline comments.Oct 22 2019, 12:47 PM
lib/CodeGen/MachineBasicBlock.cpp
472 ↗(On Diff #222595)

Afaict this does not work for callee saved registers (nor pristine regs (not used in the entire function), nor when being live out from the exit block). Nor does it work for reserved registers (aren't they always considered live out from the exit block?).

bjope added inline comments.Oct 22 2019, 12:52 PM
lib/CodeGen/MachineBasicBlock.cpp
472 ↗(On Diff #222595)

Well, the description of the function in the header file specifies the condition for the check, so it works as specified. But given the name I suppose it could be an easy mistake to believe that it more general. But maybe isLiveIn() also is limited to a subset of all registers (?), and then this isn't making anything any worse.

jonpa marked 3 inline comments as done.Oct 23 2019, 12:31 AM
jonpa added inline comments.
lib/CodeGen/MachineBasicBlock.cpp
472 ↗(On Diff #222595)

Thanks for taking a look :-)

I was aware that pristine and reserved registers would be excepted from live-in lists, but I hadn't thought about callee saved registers - why would they be excluded? And I think liveness is (in this context) a per function problem, so I don't see that the exit block case is part of it, right?

I would be open to a name change and perhaps an assert against calling this on a pristine/reserved register. But as you said, the specification in the comment is quite clear so it is up to the user determine when this is useful given that information.

bjope added inline comments.Oct 23 2019, 4:05 PM
lib/CodeGen/MachineBasicBlock.cpp
472 ↗(On Diff #222595)

I'm not really saying that those registers should be excluded. My thought were about the result in case this method was called on an exit block. Exit blocks do not have any successors, but they might have lots of live out registers. So only looking at the successor list seemed incomplete. I simply listed registers that are live out from the exit blocks, but currently not being reported as live out.

arsenm added inline comments.Oct 26 2019, 3:41 PM
lib/CodeGen/MachineVerifier.cpp
2328 ↗(On Diff #222595)

I don't think this needs the .c_str()

lib/Target/SystemZ/SystemZElimCompare.cpp
590 ↗(On Diff #222595)

I would expect this pass to use LivePhysRegs instead of checking the block function directly

jonpa updated this revision to Diff 226863.Oct 29 2019, 3:07 AM
jonpa marked 3 inline comments as done.

Patch updated to use LivePhysRegs instead of adding a new method to MachineBasicBlock.

LivePhysRegs::addLiveOuts() now gets the extended comment stating the guarantee that if a register is not added by that method it is not live out.

lib/CodeGen/MachineVerifier.cpp
2328 ↗(On Diff #222595)

It's actually needed since Twine::str() returns a std::string.

Is there a better way to construct the string than using Twine like this? The comment for Twine says it should "never be used directly"... Is this ok or would it be better to have a Twine constructed inside the call to report(), like in MirParser.cpp, for example?

lib/Target/SystemZ/SystemZElimCompare.cpp
590 ↗(On Diff #222595)

I agree it seems even better to use LivePhysRegs::addLiveOuts() since that method is already there.

Looks sensible to me.

lib/CodeGen/MachineVerifier.cpp
2328 ↗(On Diff #226863)

The patterns elsewhere in the verifier use:
report("simple message")
errs() << "fancy message" << WithVariable;

test/MachineVerifier/live-ins-01.mir
9 ↗(On Diff #226863)

You can get rid of this whole section if you remove the reference to the ir in the machine code (highlighted in the next comment).

15 ↗(On Diff #226863)

Remove the part in parentheses here.

22 ↗(On Diff #226863)

Ditto.

test/MachineVerifier/live-ins-02.mir
35 ↗(On Diff #226863)

Could you add a test case with at least one basic block with more than one predecessor.

jonpa updated this revision to Diff 227411.Nov 1 2019, 3:53 AM
jonpa marked 7 inline comments as done.

Patch updated per Quentins review:

  • use report() + errs() for the error message.
  • MIR tests simplified.
  • live-ins-03.mir added with two predecessors out of which one has a corrupt live-in list.

Also: use range-based for loop instead for the predecessors.

Herald added a project: Restricted Project. · View Herald TranscriptNov 1 2019, 3:53 AM
Herald added a subscriber: hiraditya. · View Herald Transcript
jonpa added inline comments.Nov 1 2019, 3:53 AM
lib/CodeGen/MachineVerifier.cpp
2328 ↗(On Diff #226863)

Ah, thanks :-)

test/MachineVerifier/live-ins-01.mir
9 ↗(On Diff #226863)

nice

qcolombet accepted this revision.Nov 1 2019, 9:36 AM

LGTM, thanks!

This revision is now accepted and ready to land.Nov 1 2019, 9:36 AM
jonpa added a comment.Nov 4 2019, 2:58 AM

@uweigand : Does the SystemZ backend change look OK?

@uweigand : Does the SystemZ backend change look OK?

In principle, yes -- however, it seems to be an unrelated change, so it should probably be a separate commit. Also, I don't see why we need a global LivePhysReg variable here, this should really be local to processBlock.

jonpa updated this revision to Diff 227698.Nov 4 2019, 5:36 AM

In principle, yes -- however, it seems to be an unrelated change, so it should probably be a separate commit. Also, I don't see why we need a global LivePhysReg variable here, this should really be local to processBlock.

OK, I can commit the SystemZ changes separately. Changed SystemZElimCompare.cpp to use LivePhysReg locally.

uweigand accepted this revision.Nov 4 2019, 6:33 AM

OK, LGTM.

jonpa closed this revision.Nov 4 2019, 7:25 AM

Thank you for review - committed as b7b170c and bf6744d.

@jonpa This is still causing problems with EXPENSIVE_CHECKS builds please can you take a look? http://lab.llvm.org:8011/builders/llvm-clang-x86_64-expensive-checks-ubuntu/builds/220/

jonpa added a comment.Nov 5 2019, 2:32 AM

@jonpa This is still causing problems with EXPENSIVE_CHECKS builds please can you take a look? http://lab.llvm.org:8011/builders/llvm-clang-x86_64-expensive-checks-ubuntu/builds/220/

It seems that the strengthened MachineVerifier checks have discovered two tests which in fact end up with a corrupt MIR (live-in lists) after optimizations. For the first one I found a simple solution I think, but the second one isn't quite that simple, perhaps:

  • CodeGen/X86/implicit-null-checks.mir

It seems that "Implicit null checks" adds $eflags as live in to bb.1.not_null, which is wrong since the preceding definition of it is dead (by the ADD32rr):

# *** IR Dump Before Implicit null checks ***:
# Machine code for function inc_store_with_dep: IsSSA, NoPHIs, TracksLiveness, NoVRegs
Function Live Ins: $rdi, $rsi

bb.0.entry:
  successors: %bb.2(0x40000000), %bb.1(0x40000000); %bb.2(50.00%), %bb.1(50.00%)
  liveins: $rdi, $rsi
  TEST64rr $rdi, $rdi, implicit-def $eflags
  JCC_1 %bb.2, 4, implicit killed $eflags

bb.1.not_null:
; predecessors: %bb.0
  liveins: $rdi, $rsi
  $esi = ADD32rr killed $esi(tied-def 0), killed $esi, implicit-def dead $eflags
  MOV32mr killed $rdi, 1, $noreg, 16, $noreg, killed $esi
  RETQ

bb.2.is_null:
; predecessors: %bb.0

# After Implicit null checks
# Machine code for function inc_store_with_dep: IsSSA, NoPHIs, TracksLiveness, NoVRegs
Function Live Ins: $rdi, $rsi

bb.0.entry:
  successors: %bb.2(0x40000000), %bb.1(0x40000000); %bb.2(50.00%), %bb.1(50.00%)
  liveins: $rdi, $rsi
  $esi = ADD32rr killed $esi(tied-def 0), killed $esi, implicit-def dead $eflags
  $noreg = FAULTING_OP 3, %bb.2, 1664, $rdi, 1, $noreg, 16, $noreg, $esi
  JMP_1 %bb.1

bb.1.not_null:
; predecessors: %bb.0
  liveins: $rdi, $rsi, $esi, $eflags
  RETQ

bb.2.is_null:
; predecessors: %bb.0

  RETQ

# End machine code for function inc_store_with_dep.

*** Bad machine code: Live in register not found to be live out from predecessor. ***
- function:    inc_store_with_dep
- basic block: %bb.1 not_null (0x6471fe8)
EFLAGS not found to be live out from %bb.0
LLVM ERROR: Found 1 machine code errors.

My idea to fix this is to not add a dead definition from DepMI as live-in to NC.getNotNullSucc():

diff --git a/llvm/lib/CodeGen/ImplicitNullChecks.cpp b/llvm/lib/CodeGen/ImplicitNullChecks.cpp
index b7dcaec..85e49e0 100644
--- a/llvm/lib/CodeGen/ImplicitNullChecks.cpp
+++ b/llvm/lib/CodeGen/ImplicitNullChecks.cpp
@@ -697,7 +697,7 @@ void ImplicitNullChecks::rewriteNullChecks(
 
     if (auto *DepMI = NC.getOnlyDependency()) {
       for (auto &MO : DepMI->operands()) {
-        if (!MO.isReg() || !MO.getReg() || !MO.isDef())
+        if (!MO.isReg() || !MO.getReg() || !MO.isDef() || MO.isDead())
           continue;
         if (!NC.getNotNullSucc()->isLiveIn(MO.getReg()))
           NC.getNotNullSucc()->addLiveIn(MO.getReg());
  • CodeGen/X86/copy-eflags.ll

"X86 EFLAGS copy lowering" transforms the def-use lists of $eflags (to local def-uses) without updating the livein lists of successor blocks:

bb.1.bb1:
  ...
  $eflags = COPY %16:gr32
  JCC_1 %bb.3, 12, implicit $eflags

bb.2.bb1:
; predecessors: %bb.1
  successors: %bb.3(0x80000000); %bb.3(100.00%)
  liveins: $eflags

bb.3.bb1:
; predecessors: %bb.1, %bb.2
  successors: %bb.4(0x40000000), %bb.5(0x40000000); %bb.4(50.00%), %bb.5(50.00%)
  liveins: $eflags
  %2:gr8 = PHI %8:gr8, %bb.2, %0:gr8, %bb.1
  MOV8mr %9:gr32, 1, $noreg, 0, $noreg, %2:gr8 :: (volatile store 1 into %ir.ptr1)
  %20:gr32 = MOV32rm %10:gr32, 1, $noreg, 0, $noreg :: (volatile load 4 from %ir.ptr2)
  JCC_1 %bb.5, 12, implicit $eflags

=>

After X86 EFLAGS copy lowering:

bb.1.bb1:
  TEST8rr %23:gr8, %23:gr8, implicit-def $eflags
  JCC_1 %bb.3, 5, implicit killed $eflags

bb.2.bb1:
; predecessors: %bb.1
  successors: %bb.3(0x80000000); %bb.3(100.00%)
  liveins: $eflags

bb.3.bb1:
; predecessors: %bb.1, %bb.2
  successors: %bb.4(0x40000000), %bb.5(0x40000000); %bb.4(50.00%), %bb.5(50.00%)
  liveins: $eflags
  %2:gr8 = PHI %8:gr8, %bb.2, %0:gr8, %bb.1
  MOV8mr %9:gr32, 1, $noreg, 0, $noreg, %2:gr8 :: (volatile store 1 into %ir.ptr1)
  %20:gr32 = MOV32rm %10:gr32, 1, $noreg, 0, $noreg :: (volatile load 4 from %ir.ptr2)
  TEST8rr %23:gr8, %23:gr8, implicit-def $eflags
  JCC_1 %bb.5, 5, implicit killed $eflags

It seems that since X86FlagsCopyLoweringPass::rewriteCondJmp() does JmpI.findRegisterUseOperand(X86::EFLAGS)->setIsKill(true), it should be safe to assume that EFLAGS is not live out. In that case it should also follow that any successor block will not use a live-in value of EFLAGS. So any successor block should have EFLAGS removed of the live-in list, right?

I am not sure what is the right way to clear EFLAGS of the successor blocks live-in lists. Should it be done in rewriteCondJmp() only or are there other places also that this should be done?

pengfei added a subscriber: pengfei.Nov 6 2019, 9:54 PM

@jonpa Any movement on this? The buildbots are still red - maybe time to revert?

jonpa added a comment.Nov 7 2019, 10:44 AM

@jonpa Any movement on this? The buildbots are still red - maybe time to revert?

I was hoping that someone with knowledge of the X86 would fix the tests now that I pointed out the causes. It would be a shame to revert an improvement to the machine verifier if it now discovers broken tests with expensive checks enabled, I think...

I have made an improvement for the SystemZ backend (https://reviews.llvm.org/D67437) which has already been reviewed which depends on this patch, so it would be really nice to keep this. Would it be possible to temporarily XFAIL those tests only with expensive checks enabled?

I've raised https://bugs.llvm.org/show_bug.cgi?id=43938 but normal practice would be to revert and fix the tests before recommitting.

I HIGHLY recommend you always build with EXPENSIVE_CHECKS enabled if you are working in this area.

I have reverted this by ad3c9d4.

jonpa added a comment.Nov 8 2019, 1:18 AM

I've raised https://bugs.llvm.org/show_bug.cgi?id=43938 but normal practice would be to revert and fix the tests before recommitting.

I HIGHLY recommend you always build with EXPENSIVE_CHECKS enabled if you are working in this area.

You're right - my mistake.

RKSimon reopened this revision.Nov 9 2019, 6:22 AM

Reopening as this was reverted at rGad3c9d4

This revision is now accepted and ready to land.Nov 9 2019, 6:22 AM
RKSimon requested changes to this revision.Nov 9 2019, 6:22 AM
This revision now requires changes to proceed.Nov 9 2019, 6:22 AM

I have suggested a patch for one of the failures: https://reviews.llvm.org/D70434

Does anybody have any comment on how to fix the problem in X86FlagsCopyLoweringPass as described earlier?

craig.topper added a subscriber: chandlerc.

Adding @chandlerc to comment on the X86FlagsCopyLoweringPass

  • CodeGen/X86/copy-eflags.ll

"X86 EFLAGS copy lowering" transforms the def-use lists of $eflags (to local def-uses) without updating the livein lists of successor blocks:

bb.1.bb1:
  ...
  $eflags = COPY %16:gr32
  JCC_1 %bb.3, 12, implicit $eflags

bb.2.bb1:
; predecessors: %bb.1
  successors: %bb.3(0x80000000); %bb.3(100.00%)
  liveins: $eflags

bb.3.bb1:
; predecessors: %bb.1, %bb.2
  successors: %bb.4(0x40000000), %bb.5(0x40000000); %bb.4(50.00%), %bb.5(50.00%)
  liveins: $eflags
  %2:gr8 = PHI %8:gr8, %bb.2, %0:gr8, %bb.1
  MOV8mr %9:gr32, 1, $noreg, 0, $noreg, %2:gr8 :: (volatile store 1 into %ir.ptr1)
  %20:gr32 = MOV32rm %10:gr32, 1, $noreg, 0, $noreg :: (volatile load 4 from %ir.ptr2)
  JCC_1 %bb.5, 12, implicit $eflags

=>

After X86 EFLAGS copy lowering:

bb.1.bb1:
  TEST8rr %23:gr8, %23:gr8, implicit-def $eflags
  JCC_1 %bb.3, 5, implicit killed $eflags

bb.2.bb1:
; predecessors: %bb.1
  successors: %bb.3(0x80000000); %bb.3(100.00%)
  liveins: $eflags

bb.3.bb1:
; predecessors: %bb.1, %bb.2
  successors: %bb.4(0x40000000), %bb.5(0x40000000); %bb.4(50.00%), %bb.5(50.00%)
  liveins: $eflags
  %2:gr8 = PHI %8:gr8, %bb.2, %0:gr8, %bb.1
  MOV8mr %9:gr32, 1, $noreg, 0, $noreg, %2:gr8 :: (volatile store 1 into %ir.ptr1)
  %20:gr32 = MOV32rm %10:gr32, 1, $noreg, 0, $noreg :: (volatile load 4 from %ir.ptr2)
  TEST8rr %23:gr8, %23:gr8, implicit-def $eflags
  JCC_1 %bb.5, 5, implicit killed $eflags

It seems that since X86FlagsCopyLoweringPass::rewriteCondJmp() does JmpI.findRegisterUseOperand(X86::EFLAGS)->setIsKill(true), it should be safe to assume that EFLAGS is not live out. In that case it should also follow that any successor block will not use a live-in value of EFLAGS. So any successor block should have EFLAGS removed of the live-in list, right?

I am not sure what is the right way to clear EFLAGS of the successor blocks live-in lists. Should it be done in rewriteCondJmp() only or are there other places also that this should be done?

I haven't touched this is sometime. The thing I would worry about is whether *all* of the edges into the successor have been rewritten such that EFLAGS no longer needs to live-in. I don't recall whether the code ensures that is the case in a clear point, but if it does, that is the place to update the live-in list. (I suspect it does somewhere, and it is just finding it in order to do the update correctly... my guess is that it'll be at the end because we're operating edge-wise and may not have finished rewriting edges into the successor... but that's just a guess.)

jonpa updated this revision to Diff 236254.Jan 5 2020, 11:29 AM

Since I have done everything I can to remedy this issue in the X86 backend since this was reverted two months ago, I would like to suggest recommitting this patch now with the one failing test function moved out into a new XFAIL:ing test file.

I have suggested an X86 patch for this without getting any review on https://reviews.llvm.org/D71375.

This test case problem has been reported on https://bugs.llvm.org/show_bug.cgi?id=44462.

jonpa added a comment.Jan 8 2020, 5:00 PM

The X86 issue now fixed by ee57469

This revision was not accepted when it landed; it landed in state Needs Review.Jan 8 2020, 5:01 PM
This revision was automatically updated to reflect the committed changes.