Hi Chris,

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.

Address review comments; will drop an explanation inline.

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

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.

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

I think I can narrow the conceptual difference between our interpretations down to this:

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.

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?

If I understand correctly, the problem is that calling user_back() might access a container with zero elements, yes? This would appear to be an easy fix -- however IMO you should add reviewers who're familiar with the Reassociate pass better [0]. From a couple of minutes examination it would appear ShouldBreakUpSubtract is only callable from OptimizeInst, and that in turn is guarded by isInstructionTriviallyDead, which I would expect to skip such an instruction. There might be something more complicated broken that someone more familiar with reassociate might spot.

Thanks for the patch, comments inline. A couple of things in general:

LGTM (I'm not very familiar with entry values, so best to see what other reviewers thing too).

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.

Too lazy on the earlier explanation there sorry. To elaborate: I thought I'd accounted for nondeterminism in the two loops in reinsertSunkDebugDefs, but both were a bit broken:

Remove some now needless variables, switch another DenseMap to MapVector. Having fluffed the explanation before, I'll reopen this momentarily with a fuller explanation,

I found a couple of dozens of cases building clang where this patch causes SelectionDAG::transferDbgValues() to move processed debug value past another debug value of the same variable and I'm going to investigate them in details but it can take some time.

For now, I think we could conservatively let such debug values be on their places not changing their order (although it doesn't seem necessarily correct) and add corresponding TODO or FIXME note for further investigation.

Here's a revised patch using SetVector, although it's not at the location I was expecting. As it turns out, the llvm::sort of DebugVariables I was using was actively harmful -- the operator< method of DebugVariable compares pointers, which is fine for DenseMaps, but not for ensuring a consistent order.

I tried out D71279 and D71283 individually and they both seem to fix the problem I saw. I haven't done very wide testing, but the mir-reproducer I had passes. Nice!

This risks changing the order in which variable assignments appear to occur, as there's no consideration of whether the new IROrder goes past a dbg.value intrinsic of the same variable.

D71283 Should (TM) fix it, but, the x86 test that I wrote and which seemed to replicate the issue, now no longer replicates the issue. Which is unfortunate.

(D71279 is a precursor, just getting the second patch up, but I continue to be stuck in the tar pit...)

Misery, not today, but I still think there should be an easy fix. Please do revert this patch though if it's causing difficulties.

Ouch, yeah, I can see exactly why that is: the sunk DBG_VALUE is copied from the old / "original" DBG_VALUE, which in the meantime has been copy-propagated. And through the copy propagation, it grows an extra piece of subregister information.

Reshuffle the loop structure, early continue rather than an indented block. I've also moved the PHI/EHpad test ahead of the domination check for efficiency.

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.

Insert an example into a field comment, to explain the kind of code / DBG_VALUE sequences we want to avoid re-ordering.

This revision splits out the WebAssembly work... however it turns out that that code might not be necessary at all. I tried to put together a test demonstrating what would go wrong without placeDbgValues, but can't replicate any problem. For example, in the following block of wasm mir:

Address review comments -- the "hash" fields were for comparing the contents of the Loc union, as it's now too big to be a value type. I've used memset and memcmp in its place now, which should be a bit clearer.

Bjorn wrote:

Is it possible to do the WebAssembly updates in a separate patch, or is those changes dependent on also changing how CodeGenPrepare works?

NB: I haven't forgotten about this, in particular the concern that the implementation on master right now might not complete. This is next on my list of things to mangle.

(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.

This looks ready to go in, although I've no familiarity with the LLDB tests modified in the latest changed. As far as I can see, this is weakening some of the tests (and expecting more unavailable values) because the mechanism for identifying when a value is unchanged is now more conservative, and we drop more entry values?

Great news everyone, it's placeDbgValues time again!

(This is now reborn as D70672)

Thanks for sticking with this through many revisions; hopefully this time it sticks.

Revision addressing some comments and cutting down on datastructure sizes. Note that I've deleted two tests here: with the additional conflict resolution information, there are some non-live DBG_VALUEs that can be fixed. Specifically, CR_Erase indicating "this was a redundant and dead copy of the other vreg that we're erasing" is something that can be safely resolved.

LGTM!

NB, you'll also want to remove the DebugVariable portions of this patch and assign it as a child revision of D70486, and the tests went missing in the latest revision :o)

This looks good to me and great refactor. To make sure I understand what's going on: by keeping a temporary iterator in ComputeCommonTailLength, and only "committing" the advance to I1/I2 when we're sure we've found some additional identical tail, this avoids all the concerns about I1/I2 ending up pointing at pseudo instructions?

Hokay, here's another take on this problem. To recap, all my previous implementations were broken because of

a) performance problems looking up slot indexes for DBG_VALUEs, and
b) I wasn't aware that the coalescer will merge overlapping live ranges.

which I'll address in order below.

Sitrep on this -- Vedants question about early-exits led to me digging further into the pass, and discovering even more bad assumptions I'd made. I've prototyped something based on Vedants proposal of the other way of doing this; it'll have to wait until next week though.

IMO, this LGTM, with the rider that I think the "empty" method needs to be made safer (see inline).

LGTM, best to leave this 24h in case other debug-info people spot something.

Looks good, with a couple of nits inline. Thanks for tracking this down!

Vedant wrote:

I guess there are a few alternatives to consider that call for changing data structures. Perhaps it makes more sense to start with the approach taken here to address the performance issue and to keep an eye out for any more problems.

Correctly base patch on prior implementation

In D69684#1738039, @aprantl wrote:

I would very much prefer a hard error over anything automagic. I just wanted to make sure no-one else ( @jmorse ) relies on this functionality.

This looks good -- some minor nits inline. Keeping the backup-locations in the live-out sets as special records seems like a good solution for avoiding unwanted control flow effects, as shown with the diamond pattern.

Bjorn wrote inline:

Not sure if the old code cared much about it either, but I always wonder if we forget to consider sub registers when I see code that only looks at getReg() but not getSubReg()

Fold two helpers into one; review comments and formatting

Hi Alok,

LGTM, although it's worth leaving this 24h in case other reviewers have an opinion.

A few nits inline, otherwise great!

Ah well, in that case I think this counts as merged, thanks all!

LGTM

LGTM