This is an archive of the discontinued LLVM Phabricator instance.

[MachineCopyPropagation] Expose more dead copies across instructions with regmasks
ClosedPublic

Authored by junbuml on Mar 4 2016, 8:26 AM.

Details

Summary

When encountering instructions with regmasks, instead of cleaning up all the
elements in MaybeDeadCopies map, remove only the instructions erased. By keeping
more instruction in MaybeDeadCopies, this change will expose more dead copies
across instructions with regmasks.

Diff Detail

Event Timeline

junbuml updated this revision to Diff 49830.Mar 4 2016, 8:26 AM
junbuml retitled this revision from to [MachineCopyPropagation] Expose more dead copies across instructions with regmasks.
junbuml updated this object.
junbuml added reviewers: MatzeB, qcolombet, mcrosier.
junbuml added a subscriber: llvm-commits.
qcolombet edited edge metadata.Mar 4 2016, 10:15 AM

Hi Jun,

Although I can see how this helps, I wonder if the additional complexity is worth.
Indeed, what cases do we catch here that are not handled by DCE?

Cheers,
-Quentin

Let me try to grep where this change is applied in spec tests.

In my quick test for spec2006 in cortex-a57, I can see that this change is applied in :
xalancbmk, dealII, omnetpp, soplex, namd.

With -O3, I can see that 177 and 330 movs are removed in xalancbmk and dealII, respectively.
Most of them looks like :

mov x20, x0 
bl                           
mov x20, x0

into

bl 
mov x20, x0

That may just mean we need to run an additional DCE pass somewhere else.

Where does the dead move come from?

MatzeB requested changes to this revision.Mar 4 2016, 4:22 PM
MatzeB edited edge metadata.

While I also would not expect to hit this often (I am surprised you found an instance in the SPEC at all), I think this change is small enough and very much in the spirit of the existing MachineCopyProp code, so why not go with it? The current patch however is invalid:

lib/CodeGen/MachineCopyPropagation.cpp
288–306

It seems to me like SmallSetVector::remove() invalidates all iterators into the structure (as it removes elements from an underlying vector and the iterators are just iterators into that vector). May be a good idea to add a SmallSetVector erase(iterator) method that gives returns you a valid iterator similar to SmallVector::erase() or we need a way to deal with it here.

This revision now requires changes to proceed.Mar 4 2016, 4:22 PM

I think this change is small enough and very much in the spirit of the existing MachineCopyProp code, so why not go with it?

I am fine with the code going in, but I want to root cause why we need it in the first place.
Indeed, I would rather not introduce code that lives just because of the mir test.

From my test with spec, the dead copies are just exposed in this pass. In the code below, the second copy is removed as a NOP copy after then the first copy remain just as a dead copy because we currently clear MaybeDeadCopies when encountering an instruction with regmask.

%X19<def> = COPY %X0
%X0<def> = COPY %X19<kill>
BL <ga:@_Unwind_Resume>, %X0<imp-use>

I think removing only the instruction erased is just the right way to follow the original intention of MaybeDeadCopies.

lib/CodeGen/MachineCopyPropagation.cpp
288–306

For me, it seems fine to use remove(), which erase in underlying set_ first and then in vector_, since we actually iterate using vector_ and increase our iterator (DI) right after assigning the current iterator to MaybeDead.

MatzeB added inline comments.Mar 7 2016, 12:02 PM
lib/CodeGen/MachineCopyPropagation.cpp
288–306

increasing the iterator first and then removing works fine for llvm::DenseMap, llvm::SmallPtrSet, etc. but not for vectors!
I rechecked this: std::vector::erase() invalidates all iterators that point to the removed element or behind it including the end() iterator. llvm::SmallVector should behave the same in that respect.

(Just think about a typical vector implementation, iterators are just pointers into the array when you remove elements everything behind will be moved forward, a loop like above will make you miss the element after the one you removed in case of the end you will even wander off into memory behind the vector)

junbuml added inline comments.Mar 7 2016, 12:33 PM
lib/CodeGen/MachineCopyPropagation.cpp
288–306

Thanks for correcting me.

The easiest way to fix in here would be to store the instructions we want to remove in a separate small vector and then erase all of them separately. If it doesn't make sense, I may see if I can add erase() method in SmallSetVector.

Thanks Jun for checking where the copy came from.
That being said, isn't this case already handled?
And if it is not, could you add a test case for it. None of the test cases you are adding reproduce that example.

Thanks,
-Quentin

junbuml updated this revision to Diff 50000.Mar 7 2016, 3:05 PM
junbuml edited edge metadata.

Added test case as Quentin commented.

junbuml added inline comments.Mar 7 2016, 3:09 PM
lib/CodeGen/MachineCopyPropagation.cpp
288–306

Modified the way I iterate the loop; do not increase the iterator when removing an element.

Hi Jun,

Thanks for the additional test case.

The iteration in the loop still looks problematic to me. See my inlined comment.

Thanks,
-Quentin

lib/CodeGen/MachineCopyPropagation.cpp
288–306

This is not clear to me how the iterator makes progress when we remove an element now.
Could you explain what I am missing, please?

junbuml added inline comments.Mar 15 2016, 11:45 AM
lib/CodeGen/MachineCopyPropagation.cpp
288–306

Erasing an element will causes the vector to relocate all the elements after the erased one to their new positions; like one element shift left. So the current iterator will point the right next element after erasing.

qcolombet added inline comments.Mar 15 2016, 11:58 AM
lib/CodeGen/MachineCopyPropagation.cpp
288–306

Is this something the API guarantee?
I was under the impression that although you are right about this behavior, we are actually abusing it by taking advantage of undocumented feature.

Put differently we shouldn’t rely on that behavior unless the API guarantees it. I think this is what Matthias wanted you to go with the additional erase method, i.e., a method what does what you want and is properly documented.

junbuml added inline comments.Mar 15 2016, 12:09 PM
lib/CodeGen/MachineCopyPropagation.cpp
288–306

Okay, I see your point. To be clear let me add a new erase method in SmallSetVector which will return the next element we need to iterate after erasing.

Thanks Quentin for revisiting this.

junbuml updated this revision to Diff 51469.Mar 23 2016, 1:59 PM
junbuml edited edge metadata.

Used the new erase() method added in D18281.

MatzeB accepted this revision.Mar 23 2016, 10:42 PM
MatzeB edited edge metadata.

LGTM

lib/CodeGen/MachineCopyPropagation.cpp
289–290

can these two lines get merged to a single one? (Ignore this if they are actually need more than 80 columns when combined).

This revision is now accepted and ready to land.Mar 23 2016, 10:42 PM

Thanks Matthias for the review.
This will be committed after committing D18281.

lib/CodeGen/MachineCopyPropagation.cpp
289–290

Combining these two lines do not require more than 80 columns, but this is what clang-format suggested.

MatzeB added inline comments.Mar 24 2016, 11:28 AM
lib/CodeGen/MachineCopyPropagation.cpp
289–290

Odd. But feel free to leave it as is then.

junbuml closed this revision.Mar 25 2016, 2:23 PM

Committed in r264462.
Thanks Matthias for the review.