[PHIEliminate] skip dbg instruction when LowerPHINode

[yechunliang]

Summary

[PHIEliminate] Move dbg values after phi and label

* If there is the dbg_values between phi and label (after phi and before label),
  DBG_VALUE will block PHI lower after LABEL. Moving all DBG_VALUEs after Labels
  in the function ScheduleDAGSDNodes::EmitSchedule to avoid impacting PHI lowering.

  before:
     phi
     dbg_value
     label
  after: (move dbg_value after label)
     phi
     label
     dbg_value
  then: (phi lowering after label)
     LABEL
     COPY
     DBG_VALUE

  Fix the issue: https://bugs.llvm.org/show_bug.cgi?id=43859

[yechunliang]

update description in test case

[Orlando]

LGTM -- though having given only one LGTM before I'd feel more comfortable waiting for +1.

[probinson]

llvm/lib/CodeGen/PHIElimination.cpp

210

lower -> lowering

222

Hmmm I think this does work, however it looks like the interface to LowerPHINode is strange.

• here we get the prev() of first non-PHI/etc
• LowerPHINode does next() to get first non-PHI/etc to compute AfterPHIsIt

Wouldn't it be simpler to have the caller pass AfterPHIsIt directly?
And easier to understand.

Note this suggestion is an API refactoring that could be done separately, your choice.

llvm/test/CodeGen/X86/phi-node-elimination-dbg-invariant.mir

2 ↗

(On Diff #230637)

lower -> lowering

11 ↗

(On Diff #230637)

without a Debug instruction.

33 ↗

(On Diff #230637)

with a Debug instruction at the top of the specified block.

[bjope]

llvm/test/CodeGen/X86/phi-node-elimination-dbg-invariant.mir

45 ↗

(On Diff #230639)

What if this DBG_VALUE is using %1. I think that could be an interesting test case to add as well.
If we PHI is lowered into a copy that comes after the EH_LABEL, then we probably need to move the DBG_VALUE to make sure it is after the label, to make this correct.

What happens to the DBG_VALUE with the current solution? (it is not shown in the CHECK:s, is it still present before the EH_LABEL?)

[bjope]

llvm/test/CodeGen/X86/phi-node-elimination-dbg-invariant.mir

45 ↗

(On Diff #230639)

Maybe it is better to canonicalize any labels / debug instructions that is present directly after the PHI nodes, by hoisting the labels above the debug instructions, before we lower the PHI nodes.
Assuming that it would be OK to hoist the labels past debug instructions.

For example, if we have:

PHI (1)
PHI (2)
DBG_VALUE (1)
EH_LABEL (1)
DBG_VALUE (2)
GC_LABEL (1)
DBG_LABEL (1)

it would be canonicalized into

PHI (1)
PHI (2)
EH_LABEL (1)
GC_LABEL (1)
DBG_VALUE (1)
DBG_VALUE (2)
DBG_LABEL (1)

And then we can insert the COPY instructions between the labels and debug instruction, such as:

EH_LABEL (1)
GC_LABEL (1)
COPY (1)
COPY (2)
DBG_VALUE (1)
DBG_VALUE (2)
DBG_LABEL (1)

That could solve the potential problem with having DBG_VALUE:s using the value produced by the PHI:s, without introducing use-before-def, as well as dealing with a potential problem with reordering debug instructions.

[yechunliang]

Updated the code and here is the description:

[PHIEliminate] skip dbg instruction when LowerPHINode
 
 - Debug instruction should not impact PHI node lowering when DBG_VALUE exist between PHI and LABEL.
 Eliminating PHI should skip debug instruction and insert copy instruction after LABEL.
 
 - API refactor: delete LastPHIIt and pass the caller with AfterPHIsIt directly to simplify code.
 The previous interface to LowerPHINode is strange:
     a) Before LowerPHINode, we get the prev() of last PHI/etc
     b) LowerPHINode does next() to get first non-PHI/etc to compute AfterPHIsIt
 
 Fix issue: https://bugs.llvm.org/show_bug.cgi?id=43859

[yechunliang]

@probinson @bjope thanks for review.

What happens to the DBG_VALUE with the current solution? (it is not shown in the CHECK:s, is it still present before the EH_LABEL?)

I have added "CHECK: DBG_VALUE %1" in test case, it will present before the EH_LABEL after PHI lowering, I have seen some other case that DBG_VALUEs are exist before EH_LABEL, not sure here it will make a potential problem.

[bjope]

llvm/test/CodeGen/X86/phi-node-elimination-dbg-invariant.mir

37 ↗

(On Diff #230869)

So for the majority of cases with debug info activated (assuming that EH_LABEL is more rare than DBG_VALUE) we get a regression here, since we now start to introduce use-before-def. That is something that we've been trying to get rid of (and hopefully we can add checks in the IR verifier to detect use-before-def for DBG_VALUE instructions in the future).
I don't like that regression.

I think it could be interesting to investigate why lowering of a PHI node results in inserting the COPY:s after labels in the first place.
Could also investigate it it would it be ok to reorder a sequence of labels and DBG_VALUE by moving the labels to the beginning of such a sequence (or if earlier passes shouldn't be allowed to insert a DBG_VALUE between PHI and labels that are supposed to be "before any COPY instructions that PHI lowering could result in".

As the patch looks right now, someone would need to file a PR after landing this about the "regressions" introduced by this patch.

If the debug-invariance is considered a much more serious problem than the use-before-def for DBG_VALUE, then I suggest to at least avoid skipping past debug instructions when there are no labels. E.g. first move forward "SkipPHIsLabelsAndDebug", and then move backward again as long as the instruction is a debug instruction. That would need to be accompanied by some code comments describing what is going on (and probably also a PR since the solution wouldn't be perfect).

Well, another option is ofcourse to try to selectively handle any use-before-def scenario that appears. Trying to move the DBG_VALUE if that is legal, or invalidate it, or rewrite it to use the source register used in the COPY, etc. But that is kind of tricky. Such a solution would involve moving the DBG_VALUE past the label. If it is ok to move DBG_VALUE past the labels then I think that we are back to my earlier idea about hoisting labels before debug instructions when a sequence of labels and debug instructions are found after a PHI.

Maybe @jmorse or @aprantl has other ideas on how to deal with this? Are my comments making sense?

[jmorse]

(Responding to inline comments) I agree with @bjope, this would have a large effect on bunches of PHIs immediately followed by bunches of DBG_VALUEs that refer to them. This is a common case in most of the IR that I look at, mem2reg puts them there, and we'd lose quite a lot of variable coverage.

I like the idea of canonicalising the order of these instructions so that the DBG_VALUEs always follow the other meta instructions. I'm pretty confident we should be able to re-order DBG_VALUEs with other non-debug meta instructions -- I'm not aware of debug facilities depending on EH_LABEL / GC_LABEL in any way, and I don't believe it'd make sense for them to depend on debugging information.

Alternately, it might be easier to study where EH_LABEL / GC_LABEL are created and guarantee that they always come before debug instructions. This might be as simple as having the DBG_VALUE creating code placing DBG_VALUEs after PHIs and labels [0], but I don't know how the *_LABEL things work. There's then the risk that optimisations moving DBG_VALUEs re-introduce this condition, but it would avoid extra computation during PHI elimination.

[0] https://github.com/llvm/llvm-project/blob/742043047c973999eac7734e53f7872973933f24/llvm/lib/CodeGen/SelectionDAG/ScheduleDAGSDNodes.cpp#L935

[yechunliang]

I try to move DBG_VALUE after COPY, but have some doubts:

1. Is there the case that DBG_VALUE be exist after LABELs use %1 definition? if there is, we need to move all DBG_VALUEs, if not, we just need to move DBG_VALUE which located after PHIs.
2. After refactoring by using AfterPHIsIt instead of LastPHIIt, there is the case that the basic block only have two PHIs, AfterPHIslt will be null and pass to LowerPHINode(), not sure if passing argument(null) to a function is safety or not?

If using AfterPHIslt has no potential problem, we could use this for insert point. And we'd better first lower PHIs and then move DBG_VALUE on front of AfterPHIslt.
For example: if we have

PHI (1)
PHI (2)
DBG_VALUE (1)
DBG_VALUE (2)
EH_LABEL (1)
DBG_VALUE (3)
(AfterPHIsIt)

First Lower PHIs on front of AfterPHIsIt

DBG_VALUE (1)
DBG_VALUE (2)
EH_LABEL (1)
DBG_VALUE (3)
COPY 1
COPY 2
(AfterPHIsIt)

Then move DEBUG_VALUE on front of AfterPHIsIt

EH_LABEL (1)
DBG_VALUE (3)
COPY 1
COPY 2
DBG_VALUE (1)
DBG_VALUE (2)
(AfterPHIsIt)

if DBG_VALUE (3) will use %1, we need also move it together.

EH_LABEL (1)
COPY 1
COPY 2
DBG_VALUE (1)
DBG_VALUE (2)
DBG_VALUE (3)
(AfterPHIsIt)

[yechunliang]

Another idea is to add one more helper like getFirstNonPHIsAndLabels(), replace getFirstNonPHI in ScheduleDAGSDNodes.cpp#L935.
Insert dbg_values after PHIs and Labels, so that there will be no dbg_values barrier between PHI and LABELS.

[0] https://github.com/llvm/llvm-project/blob/742043047c973999eac7734e53f7872973933f24/llvm/lib/CodeGen/SelectionDAG/ScheduleDAGSDNodes.cpp#L935

[jmorse]

In D70597#1768869, @yechunliang wrote:

Another idea is to add one more helper like getFirstNonPHIsAndLabels(), replace getFirstNonPHI in ScheduleDAGSDNodes.cpp#L935.
Insert dbg_values after PHIs and Labels, so that there will be no dbg_values barrier between PHI and LABELS.

This sounds good to me -- there's an existing "SkipPHIsLabelsAndDebug" method in MachineBasicBlock, would that be sufficient?

Not creating this scenario in the first place sounds is a good plan.

[yechunliang]

In D70597#1769185, @jmorse wrote:

In D70597#1768869, @yechunliang wrote:

Another idea is to add one more helper like getFirstNonPHIsAndLabels(), replace getFirstNonPHI in ScheduleDAGSDNodes.cpp#L935.
Insert dbg_values after PHIs and Labels, so that there will be no dbg_values barrier between PHI and LABELS.

This sounds good to me -- there's an existing "SkipPHIsLabelsAndDebug" method in MachineBasicBlock, would that be sufficient?

Not creating this scenario in the first place sounds is a good plan.

Yes, SkipPHIsAndLabels is workable as below,
MachineBasicBlock::iterator BBBegin = BB->SkipPHIsAndLabels(BB->begin());

[yechunliang]

After study the history of the PHIElimination code changes, finally, I found this issue had been fixed before, and later the fixing code had been removed when created the SkipPHIsAndLables as new helper.

1. First patch to fix this issue in SkipPHIsAndLabels from PHIElimination.h (using workaround).

https://github.com/llvm/llvm-project/commit/d7eb69364

2. SkipPHIsAndLables had been created as new helper in MachineBasicBlock.cpp ( the fixing code have been removed)

https://github.com/llvm/llvm-project/commit/ef54185724

3. later the function SkipPHIsAndLables from PHIElimination.h have been deleted.

https://github.com/llvm/llvm-project/commit/fbd47dcc5

So the issue happen again. Moving dbg_values after labels at the beginning should be a better solution, and moving dbg_values after labels should have no side effect.

[yechunliang]

description for updated revision:

move dbg values after label for phi elimination

* If there is the dbg_values between phi and label (after phi and before label),
  dbg_values will block PHI to lower after LABELs. To fix this issue, insert
  all dbg_values after Labels in the function ScheduleDAGSDNodes::EmitSchedule,
  Moving dbg_value in the early stage to avoid dbg_value impact PHI lowering.
  before:
     phi
     dbg_value
     label
  after:
     LABEL
     COPY
     DBG_VALUE

  Fix the issue: https://bugs.llvm.org/show_bug.cgi?id=43859

* Re-add some important comments for PHIElimination APIs from original deleted comments.

[bjope]

There are several other passes between isel and phi elimination. So if we now have a rule that there must not be any dbg instructions between PHI-nodes and labels that should be at the beginning of the MBB, then perhaps we need to add a check in MachineVerfier that the new rule is followed by all those passes.

I think that at least PHIElimination::EliminatePHINodes should have an assert on the pre-requisite. Perhaps something like this

assert(std::prev(MBB.SkipPHIsAndLabels(MBB.begin())) == skipDebugInstructionsBackward(MBB.SkipPHIsLabelsAndDebug(MBB.begin()), MBB.begin()))
}

[yechunliang]

@bjope, thanks for comments, that's a good idea, better than remember "No debug in PHI and labels" in mind.

[jmorse]

Great to hear that this is fixing the issue. I agree with Björn, there should be a MachineVerifier check too that DBG_VALUEs are not mixed with labels. That'll make it very easy to detect this issue reoccurring.

llvm/lib/CodeGen/PHIElimination.cpp

210–220

As we've designed the original problem out, and the PHI Elimination pass isn't actually changed now, isn't this comment un-necessary?

If I understand correctly, what we could say here is something like "There should be no PHIs or Labels at all after this point".

llvm/lib/CodeGen/SelectionDAG/ScheduleDAGSDNodes.cpp

944

I think this comment could be shorter, how about, "Always place DBG_VALUEs after all other special start-of-block instructions, to avoid debug data hiding start-of-block instructions."

llvm/test/CodeGen/X86/dbg-changes-codegen-phi-elimination.ll

21

nit: this should have !dbg !9 after it, right? To associate the function with the DISubprogram?

54–55

If these attributes aren't important to the test, they should be removed.

[yechunliang]

Just updated the code [Diff 233770] follow the comments by jmose and bjope.
I try to add below reference code to MachineVerifier::checkPHIOps, but meet a build error. In the function the type of MBB.begin() is const_iterator, but type of SkipPHIsAndLabels argument is (iterator I). How to convert const_iterator to iterator and pass to SkipPHIsAndLabels? Could I write the MachineVerifier as below code?

diff --git a/llvm/lib/CodeGen/MachineVerifier.cpp b/llvm/lib/CodeGen/MachineVerifier.cpp
index ca57e51268e..fbec123a2ec 100644
--- a/llvm/lib/CodeGen/MachineVerifier.cpp
+++ b/llvm/lib/CodeGen/MachineVerifier.cpp
@@ -2273,6 +2273,13 @@ void MachineVerifier::checkPHIOps(const MachineBasicBlock &MBB) {
       }
     }
   }
+
+  // Check there must be no dbg_values between PHI and labels
+  MachineBasicBlock::iterator LastPHIIt =
+    std::prev(MBB.SkipPHIsAndLabels(MBB.begin()));
+  if (LastPHIIt == skipDebugInstructionsBackward(
+          std::prev(MBB.SkipPHIsLabelsAndDebug(MBB.begin())), MBB.begin()))
+    report("Unexpected dbg_values between PHI and labels", &MBB);
 }

llvm/lib/CodeGen/PHIElimination.cpp

210–220

The comments is searched from old commits, and described why need to use LastPHIIt(prev-next), and why need to lower PHI after Label.
This is not related with new patch, I'll remove it.

[jmorse]

I try to add below reference code to MachineVerifier::checkPHIOps, but meet a build error. In the function the type of MBB.begin() is const_iterator, but type of SkipPHIsAndLabels argument is (iterator I). How to convert const_iterator to iterator and pass to SkipPHIsAndLabels? Could I write the MachineVerifier as below code?

Ah, yeah, SkipPHIsAndLabels expects to produce a non-const iterator, and you're calling it from somewhere where everything is const. I suspect (although my C++ fu is poor) that, just like the "begin" and "end" calls in MachineBasicBlock, duplicate methods would be needed, which would seem wasteful. It might be easier to just implement this manually in the verifier.

[yechunliang]

Look like adding one more method for SkipPHIsAndLabels with const_iterator would be more easier. I thought will be more duplicate code to implement SkipPHIsAndLabels and SkipPHIsLabelsAndDebug in MachineVerifier.
As the "No debug in PHI and labels" assert already be added in PHIElimination.cpp, is that safe if we do not add the checking in MachineVerifier?

[jmorse]

Look like adding one more method for SkipPHIsAndLabels with const_iterator would be more easier. I thought will be more duplicate code to implement SkipPHIsAndLabels and SkipPHIsLabelsAndDebug in MachineVerifier.

Fair enough,

As the "No debug in PHI and labels" assert already be added in PHIElimination.cpp, is that safe if we do not add the checking in MachineVerifier?

The assertion is testing that what we're doing is safe at the last possible moment. The machine verifier runs much earlier (and can be run independently over a MIR file, I think), and gives much more context and information about where the problem has happened. It'll save future developers a large amount of time narrowing down problems, and improve the user experience if a bug is encountered. It also makes it easier for us to argue "this MIR file is invalid" if someone disagrees about whether their code is valid.

[yechunliang]

Added checkPHIDbg to check "no dbg_values between PHI and labels" in MachineVerifier.

[yechunliang]

fix code style issue.

[jmorse]

Looking good, this is almost there (see inline),

llvm/lib/CodeGen/MachineVerifier.cpp

2279–2280 ↗

(On Diff #234456)

Good concise comment -- just a nit, could you use DBG_VALUEs instead of dbg_values? (It helps people searching for debug related stuff to keep it consistent).

2286–2291 ↗

(On Diff #234456)

Wouldn't a block that has no PHIs or labels end up returning MBB2.begin()? Applying std::prev to that would break.

I get what you're doing here, and it makes sense -- possibly a better way would be to skipDebugIntructionsForward from the position of SkipPHIsAndLabels instead? You don't need to worry about whether the list of instructions is empty that way, because in the worst case everything will end pointing at MBB2.end().

[jmorse]

I wrote inline:

Wouldn't a block that has no PHIs or labels end up returning MBB2.begin()? Applying std::prev to that would break.

Running check-llvm, there are a bunch of crashes, for example llvm/test/CodeGen/X86/win-catchpad.ll so there's certainly something breaking there.

[yechunliang]

In D70597#1807759, @jmorse wrote:

Running check-llvm, there are a bunch of crashes, for example llvm/test/CodeGen/X86/win-catchpad.ll so there's certainly something breaking there.

The root cause is that the empty MBB have not been considered, so that the MBB.begin() run fails.
I'll update the code and run check-llvm next time before submit patch, thanks.

llvm/lib/CodeGen/MachineVerifier.cpp

2279–2280 ↗

(On Diff #234456)

thanks for comment, I'll fix it.

2286–2291 ↗

(On Diff #234456)

Wouldn't a block that has no PHIs or labels end up returning MBB2.begin()? Applying std::prev to that would break.

there should be at least one PHI on the top of MBB when come into this function. If these is only one PHI instruction, the SkipPHIsAndLabels will return MBB.end(), and std::prev will be MBB.begin(). I though that will not break.

I get what you're doing here, and it makes sense -- possibly a better way would be to skipDebugIntructionsForward from the position of SkipPHIsAndLabels instead? You don't need to worry about whether the list of instructions is empty that way, because in the worst case everything will end pointing at MBB2.end().

Do you mean to use skipDebugInstructionsBackward(SkipPHIsLabelsAndDebug) directly instead of skipDebugInstructionsBackward(std::prev(SkipPHIsLabelsAndDebug))?
If so, here is my explanation: the result of these two function is different. In case there is only PHI and Lables in the BasicBlock, then SkipPHIsAndLabels() will return MBB2.end(), and the std::prev will be last PHI or Label, but when call skipDebugInstructionsBackward(MBB2.end()), it will still return MBB2.end(), not the previous LastPHIIt that we expect. The purpose of this code is first to find the lastPHI, then backward to skip debug if the lastPHI is DEB_VALUE.

[yechunliang]

update patch with:

1. rename dbg_values as DBG_VALUEs to keep consistent.
2. add MBB.empty check at the beginning of MachineVerifier::checkPHIDbg

[jmorse]

LGTM, thanks for working through this. Do you still need patches to be committed for you?

llvm/lib/CodeGen/MachineVerifier.cpp

2286–2291 ↗

(On Diff #234456)

Ah -- I completely missed the guard at the start of the function, right you are. With the check for empty first, I don't get any test failures at all.

[yechunliang]

In D70597#1810125, @jmorse wrote:

LGTM, thanks for working through this. Do you still need patches to be committed for you?

@jmorse, @bjope, @probinson, thank you all for comments and help. All the comments had be followed and fixed. The patch is ready to be landed, it would be thankful if you would help to commit it. Thanks.

[jmorse]

Hi, I'm now getting around to committing this. The developer policy [0] now says I should edit your details into the "Author" field of the commit, I'm using your phabricator-registered email address and "Chris Ye" from your phab profile. If there are buildbot failures when the commit goes up (possibly unrelated to this change), you might get messages to that email address.

I'll keep an eye on the buildbots page [1] to see whether any problems occur.

[0] https://llvm.org/docs/DeveloperPolicy.html
[1] http://lab.llvm.org:8011/console

[jmorse]

Hi Chris,

All the public buildbots passed, however our (Sony) internal build of the compiler-rt unit tests found a problem, where the added PHIElimination assertion fired. I've uploaded a reproducer in [0] extracted from the failing program, when running llc over it I get:

../icedebug/bin/llc extracted2.ll -o extracted.o
llc: /fast/fs/llvm-project/llvm/lib/CodeGen/PHIElimination.cpp:216: bool (anonymous namespace)::PHIElimination::EliminatePHINodes(llvm::MachineFunction &, llvm::MachineBasicBlock &): Assertion `(LastPHIIt == skipDebugInstructionsBackward( std::prev(MBB.SkipPHIsLabelsAndDebug(MBB.begin())), MBB.begin())) && "There must be no DBG_VALUEs between PHI and LABEL"' failed.
Stack dump:
0.      Program arguments: ../icedebug/bin/llc extracted2.ll -o extracted.o
1.      Running pass 'Function Pass Manager' on module 'extracted2.ll'.
2.      Running pass 'Eliminate PHI nodes for register allocation' on function '@_ZN7testing8internal8FilePath22GenerateUniqueFileNameERKS1_S3_PKc'
 #0 0x0000000005f912b9 llvm::sys::PrintStackTrace(llvm::raw_ostream&) /fast/fs/llvm-project/llvm/lib/Support/Unix/Signals.inc:564:11
 #1 0x0000000005f91469 PrintStackTraceSignalHandler(void*) /fast/fs/llvm-project/llvm/lib/Support/Unix/Signals.inc:625:1
 #2 0x0000000005f8fbf6 llvm::sys::RunSignalHandlers() /fast/fs/llvm-project/llvm/lib/Support/Signals.cpp:67:5
 #3 0x0000000005f91bfb SignalHandler(int) /fast/fs/llvm-project/llvm/lib/Support/Unix/Signals.inc:406:1
 #4 0x00007f266e2fa890 __restore_rt (/lib/x86_64-linux-gnu/libpthread.so.0+0x12890)
 #5 0x00007f266cda3e97 raise /build/glibc-OTsEL5/glibc-2.27/signal/../sysdeps/unix/sysv/linux/raise.c:51:0
 #6 0x00007f266cda5801 abort /build/glibc-OTsEL5/glibc-2.27/stdlib/abort.c:81:0
 #7 0x00007f266cd9539a __assert_fail_base /build/glibc-OTsEL5/glibc-2.27/assert/assert.c:89:0
 #8 0x00007f266cd95412 (/lib/x86_64-linux-gnu/libc.so.6+0x30412)
 #9 0x00000000051369f1 (anonymous namespace)::PHIElimination::EliminatePHINodes(llvm::MachineFunction&, llvm::MachineBasicBlock&) /fast/fs/llvm-project/llvm/lib/CodeGen/PHIElimination.cpp:218:3
#10 0x0000000005135d8f (anonymous namespace)::PHIElimination::runOnMachineFunction(llvm::MachineFunction&) /fast/fs/llvm-project/llvm/lib/CodeGen/PHIElimination.cpp:169:16
#11 0x0000000004fbf0ef llvm::MachineFunctionPass::runOnFunction(llvm::Function&) /fast/fs/llvm-project/llvm/lib/CodeGen/MachineFunctionPass.cpp:73:8
#12 0x0000000005503849 llvm::FPPassManager::runOnFunction(llvm::Function&) /fast/fs/llvm-project/llvm/lib/IR/LegacyPassManager.cpp:1481:23
#13 0x0000000005503c55 llvm::FPPassManager::runOnModule(llvm::Module&) /fast/fs/llvm-project/llvm/lib/IR/LegacyPassManager.cpp:1517:16
#14 0x00000000055043b8 (anonymous namespace)::MPPassManager::runOnModule(llvm::Module&) /fast/fs/llvm-project/llvm/lib/IR/LegacyPassManager.cpp:1582:23
#15 0x0000000005503ee5 llvm::legacy::PassManagerImpl::run(llvm::Module&) /fast/fs/llvm-project/llvm/lib/IR/LegacyPassManager.cpp:1694:16
#16 0x0000000005504941 llvm::legacy::PassManager::run(llvm::Module&) /fast/fs/llvm-project/llvm/lib/IR/LegacyPassManager.cpp:1725:3
#17 0x00000000030b4c9b compileModule(char**, llvm::LLVMContext&) /fast/fs/llvm-project/llvm/tools/llc/llc.cpp:611:41
#18 0x00000000030b32c3 main /fast/fs/llvm-project/llvm/tools/llc/llc.cpp:356:13
#19 0x00007f266cd86b97 __libc_start_main /build/glibc-OTsEL5/glibc-2.27/csu/../csu/libc-start.c:344:0
#20 0x00000000030b2a0a _start (../icedebug/bin/llc+0x30b2a0a)
[1]    15520 abort (core dumped)  ../icedebug/bin/llc extracted2.ll -o extracted.o

On ubuntu 18.04.

Would you be able to look at this? It's likely that some earlier faulty pass is re-ordering instructions. The failing block starts with:

%2:gr32 = PHI %17:gr32, %bb.0, %3:gr32, %bb.5, debug-location !15321; llvm/utils/unittest/googletest/src/gtest-filepath.cc:0
DBG_VALUE %2:gr32, $noreg, !"number", !DIExpression(), debug-location !15321; llvm/utils/unittest/googletest/src/gtest-filepath.cc:0 line no:290
DBG_VALUE $noreg, $noreg, !"number", !DIExpression(), debug-location !15321; llvm/utils/unittest/googletest/src/gtest-filepath.cc:0 line no:290
EH_LABEL <mcsymbol .Ltmp0>, debug-location !15502; llvm/utils/unittest/googletest/src/gtest-filepath.cc:292:23

[0] https://raw.githubusercontent.com/jmorse/llvm-project/fgasdf/extracted.ll

[yechunliang]

Checked with extracted.ll, on the block [19]: the dbg.value did not skip "llvm.lifetime" and "%21 add" move after Label by SkipPHIsAndLabels() while ScheduleDAGSDNodes.
And later PASS (after ScheduleDAGSDNodes) removed "call llvm.lifetime.start" and "%21 add", and then left DBG_VALUEs between PHI and LABELs, and make errors.

original IR:

19:                                               ; preds = %27, %4
  %20 = phi i32 [ 0, %4 ], [ %21, %27 ], !dbg !15321
  call void @llvm.dbg.value(metadata i32 %20, metadata !15278, metadata !DIExpression()), !dbg !15321
  call void @llvm.lifetime.start.p0i8(i64 32, i8* nonnull %11) #6, !dbg !15520
  %21 = add nuw nsw i32 %20, 1, !dbg !15521
  call void @llvm.dbg.value(metadata i32 %21, metadata !15278, metadata !DIExpression()), !dbg !15321
  invoke void @_ZN7testing8internal8FilePath12MakeFileNameERKS1_S3_iPKc(%"class.testing::internal::FilePath"* nonnull sret %6, %"class.testing::internal::FilePath"* nonnull dereferenceable(32) %1,    %"class.testing::internal::FilePath"* nonnull dereferenceable(32) %2, i32 %20, i8* %3)
          to label %22 unwind label %31, !dbg !15520

After "X86 DAG->DAG Instruction Selection":

%2:gr32 = PHI %17:gr32, %bb.0, debug-location !15321; llvm/utils/unittest/googletest/src/gtest-filepath.cc:0
  DBG_VALUE %2:gr32, $noreg, !"number", !DIExpression(), debug-location !15321; llvm/utils/unittest/googletest/src/gtest-filepath.cc:0 line no:290
  LIFETIME_START %stack.1, debug-location !15502; llvm/utils/unittest/googletest/src/gtest-filepath.cc:292:23
  %3:gr32 = nuw nsw ADD32ri8 %2:gr32(tied-def 0), 1, implicit-def dead $eflags, debug-location !15503; llvm/utils/unittest/googletest/src/gtest-filepath.cc:292:64
  DBG_VALUE %3:gr32, $noreg, !"number", !DIExpression(), debug-location !15321; llvm/utils/unittest/googletest/src/gtest-filepath.cc:0 line no:290
  EH_LABEL <mcsymbol .Ltmp0>, debug-location !15502; llvm/utils/unittest/googletest/src/gtest-filepath.cc:292:23

After Merge disjoint stack slots

%2:gr32 = PHI %17:gr32, %bb.0, %3:gr32, %bb.5, debug-location !15321; llvm/utils/unittest/googletest/src/gtest-filepath.cc:0
  DBG_VALUE %2:gr32, $noreg, !"number", !DIExpression(), debug-location !15321; llvm/utils/unittest/googletest/src/gtest-filepath.cc:0 line no:290
  %3:gr32 = nuw nsw ADD32ri8 %2:gr32(tied-def 0), 1, implicit-def dead $eflags, debug-location !15503; llvm/utils/unittest/googletest/src/gtest-filepath.cc:292:64
  DBG_VALUE %3:gr32, $noreg, !"number", !DIExpression(), debug-location !15321; llvm/utils/unittest/googletest/src/gtest-filepath.cc:0 line no:290
  EH_LABEL <mcsymbol .Ltmp0>, debug-location !15502; llvm/utils/unittest/googletest/src/gtest-filepath.cc:292:23

After Machine code sinking

%2:gr32 = PHI %17:gr32, %bb.0, %3:gr32, %bb.5, debug-location !15321; llvm/utils/unittest/googletest/src/gtest-filepath.cc:0
  DBG_VALUE %2:gr32, $noreg, !"number", !DIExpression(), debug-location !15321; llvm/utils/unittest/googletest/src/gtest-filepath.cc:0 line no:290
  DBG_VALUE $noreg, $noreg, !"number", !DIExpression(), debug-location !15321; llvm/utils/unittest/googletest/src/gtest-filepath.cc:0 line no:290
  EH_LABEL <mcsymbol .Ltmp0>, debug-location !15502; llvm/utils/unittest/googletest/src/gtest-filepath.cc:292:23

[yechunliang]

We try to move DBG_VALUEs after PHI and LABELs while ScheduleDAGSDNodes on early stage, but there is the the case the DBG_VALUEs exist between PHI and LABELs after Later PASS. Looks like we need to move DBG_VALUEs after LABELs on the beginning of PHIElimination.

[yechunliang]

My proposed code is as below: moving debug instrs after LastPHIIt at the beginning of PHIElimination

void spliceDebugInstructionForward(MachineBasicBlock &MBB,
    MachineBasicBlock::iterator From,
    MachineBasicBlock::iterator To)
{
  if (From == To)
    return;

  MachineBasicBlock::iterator insertBefore = std::next(To);

  for (MachineBasicBlock::iterator Inst = std::prev(To); Inst != From; --Inst) {
    if(Inst->isDebugInstr()) {
      MBB.splice(insertBefore, &MBB, Inst);
      Inst = std::prev(Inst);
    }
  }
}

if (LastPHIIt->isLabel())
  spliceDebugInstructionForward(MBB, MBB.begin(), LastPHIIt);

[jmorse]

Hi, sorry for the long delay,

Checked with extracted.ll, on the block [19]: the dbg.value did not skip "llvm.lifetime" and "%21 add" move after Label by SkipPHIsAndLabels() while ScheduleDAGSDNodes.
And later PASS (after ScheduleDAGSDNodes) removed "call llvm.lifetime.start" and "%21 add", and then left DBG_VALUEs between PHI and LABELs, and make errors.

Ouch, I definitely hadn't thought about other meta instructions. I guess there must be several passes that might move such instructions, and in the solution we followed they would all need to be aware of placing DBG_VALUEs between labels and PHIs, which would be a lot of work.

Looks like we need to move DBG_VALUEs after LABELs on the beginning of PHIElimination.

Yeah, sounds like that's the safest option. Your proposed code looks good, although I suspect the "Inst" iterator could be invalidated / point somewhere else after the call to splice, which might mean you need to copy it before the splice. If you could update that into this patch and give it a test run, it should be good to commit.

[yechunliang]

ok, I'll update the patch later.

[yechunliang]

updated patch:
[PHIEliminate] splice dbg instruction when LowerPHINode
DBG_VALUEs between PHI and LABEL will block PHI lownering after LABEL, move all DBG_VALUEs after Label before PHI lowering.

llvm/lib/CodeGen/PHIElimination.cpp

 
 /// EliminatePHINodes - Eliminate phi nodes by inserting copy instructions in
 /// predecessor basic blocks.
 bool PHIElimination::EliminatePHINodes(MachineFunction &MF,
                                        MachineBasicBlock &MBB) {
   if (MBB.empty() || !MBB.front().isPHI())
     return false;   // Quick exit for basic blocks without PHIs.
 
-  // Get an iterator to the last PHI node.
+  // Get an iterator to the last PHI node or LABEL instruction.
+  // LastPHIIt - Fix PR16508:
+  //   When phis get lowered, destination copies are inserted using an iterator that is
+  //   determined once for all phis in the block, which BuildMI interprets as a request
+  //   to insert an instruction directly before the iterator. In the case of a cyclic
+  //   phi, source copies may also be inserted directly before this iterator, which can
+  //   cause source copies to be inserted before destination copies. The fix is to keep
+  //   an iterator to the last phi and then advance it while lowering each phi in order
+  //   to insert destination copies directly after the phis.
+  // SkipPHIsAndLabels - Copies need to be inserted after phi nodes and
+  //   also after any exception handling labels: in landing pads execution
+  //   starts at the label, so any copies placed before it won't be executed!
   MachineBasicBlock::iterator LastPHIIt =
     std::prev(MBB.SkipPHIsAndLabels(MBB.begin()));
 
   while (MBB.front().isPHI())
     LowerPHINode(MBB, LastPHIIt);
 
   return true;
 }
 
 /// Return true if all defs of VirtReg are implicit-defs.

llvm/lib/CodeGen/SelectionDAG/ScheduleDAGSDNodes.cpp

if (MDNode *MD = DAG->getHeapAllocSite(SU->getNode())) {
       if (NewInsn && NewInsn->isCall())
         NewInsn->setHeapAllocMarker(MF, MD);
     }
   }
 
   // Insert all the dbg_values which have not already been inserted in source
   // order sequence.
   if (HasDbg) {
-    MachineBasicBlock::iterator BBBegin = BB->getFirstNonPHI();
+    // Get first NonPHI and NonLabels, insert dbg_values after both.
+    // Deal with DBG_VALUEs, which are a bit tricky:
+    //  PHI
+    //  DBG_VALUE
+    //  LABEL
+    // and the DBG_VALUE will break PHI elimination when lower after Label,
+    // Here the DBG_VALUE needs to moving after the labels, like this:
+    //  PHI
+    //  LABEL
+    //  DBG_VALUE
+    MachineBasicBlock::iterator BBBegin = BB->SkipPHIsAndLabels(BB->begin());
 
     // Sort the source order instructions and use the order to insert debug
     // values. Use stable_sort so that DBG_VALUEs are inserted in the same order
     // regardless of the host's implementation fo std::sort.
     llvm::stable_sort(Orders, less_first());
     std::stable_sort(DAG->DbgBegin(), DAG->DbgEnd(),
                      [](const SDDbgValue *LHS, const SDDbgValue *RHS) {
                        return LHS->getOrder() < RHS->getOrder();

llvm/test/CodeGen/X86/dbg-changes-codegen-phi-elimination.ll

+; RUN: llc -O0 %s -mtriple=x86_64 -stop-after=phi-node-elimination -o - | FileCheck %s
+
+; If there is the dbg_values between phi and label (after phi and before label),
+; dbg_values will block PHI to lower after LABELs. To fix this issue, insert
+; all dbg_values after Labels in the function ScheduleDAGSDNodes::EmitSchedule,
+; Moving dbg_value in the first place to avoid dbg_value impact PHI lowering.
+; Fix the issue: https://bugs.llvm.org/show_bug.cgi?id=43859
+
+; The purpose of this case is to check two items:
+;   1. reorder dbg_value and insert after label
+;   2. phi could lowering after Labels
+; before:
+;    phi
+;    dbg_value
+;    label
+; after:
+;    LABEL
+;    COPY
+;    DBG_VALUE
+
+define i32 @func(i32 %a0) personality void ()* @personality {
+bb1:
+  %v = icmp slt i32 %a0, 0
+  br i1 %v, label %bb2, label %bb3
+
+bb2:
+  br label %bb3
+
+bb3:
+; CHECK: bb.2.bb3:
+; CHECK: EH_LABEL
+; CHECK-NEXT: %0:gr32 = COPY %7
+; CHECK-NEXT: DBG_VALUE %0
+  %0 = phi i32 [ 2, %bb2 ], [ 1, %bb1 ]
+  call void @llvm.dbg.value(metadata i32 %0, metadata !8, metadata !DIExpression()), !dbg !13
+  invoke void @foo() to label %end unwind label %lpad
+
+end:
+  ret i32 %0
+
+lpad:
+  %1 = landingpad { i8*, i32 }
+           cleanup
+  unreachable
+}
+
+declare void @foo()
+
+declare void @personality()
+
+; Function Attrs: nounwind readnone speculatable willreturn
+declare void @llvm.dbg.value(metadata, metadata, metadata) #0
+
+attributes #0 = { nounwind readnone speculatable willreturn }
+attributes #1 = { nounwind }
+
+!llvm.dbg.cu = !{!0}
+!llvm.module.flags = !{!3, !4, !5, !6}
+!llvm.ident = !{!7}
+
+!0 = distinct !DICompileUnit(language: DW_LANG_C99, file: !1, producer: "clang", isOptimized: false, runtimeVersion: 0, emissionKind: FullDebug, enums: !2)
+!1 = !DIFile(filename: "a.c", directory: "/tmp")
+!2 = !{}
+!3 = !{i32 2, !"Dwarf Version", i32 4}
+!4 = !{i32 2, !"Debug Info Version", i32 3}
+!5 = !{i32 1, !"wchar_size", i32 4}
+!6 = !{i32 1, !"min_enum_size", i32 4}
+!7 = !{!"clang"}
+!8 = !DILocalVariable(name: "c", scope: !9, file: !1, line: 3, type: !12)
+!9 = distinct !DISubprogram(name: "func", scope: !1, file: !1, line: 1, type: !10, scopeLine: 2, flags: DIFlagPrototyped, spFlags: DISPFlagDefinition, unit: !0, retainedNodes: !2)
+!10 = !DISubroutineType(types: !11)
+!11 = !{!12, !12}
+!12 = !DIBasicType(name: "int", size: 32, align: 32, encoding: DW_ATE_signed)
+!13 = !DILocation(line: 3, column: 13, scope: !9)