This is an archive of the discontinued LLVM Phabricator instance.

[BranchFolding] Tail common all identical unreachable blocks
ClosedPublic

Authored by rnk on Jan 25 2017, 3:29 PM.

Details

Summary

Blocks ending in unreachable are typically cold because they end the
program or throw an exception, so merging them with other identical
blocks is usually profitable because it reduces the size of cold code.
MachineBlockPlacement generally does not arrange to fall through to such
blocks, so commoning these blocks will not introduce additional
unconditional branches.

Improves code size in MSVC std::string::~string: PR31774

Diff Detail

Repository
rL LLVM

Event Timeline

rnk created this revision.Jan 25 2017, 3:29 PM
hans added inline comments.Jan 25 2017, 3:47 PM
test/CodeGen/ARM/tail-opts.ll
71 ↗(On Diff #85822)

Did you forget filecheck directives for this?

rnk added inline comments.Jan 25 2017, 3:55 PM
test/CodeGen/ARM/tail-opts.ll
71 ↗(On Diff #85822)

Oops, I should've deleted it. I wasn't able to make an effective test out of it because it's really hard to make a 2-instruction return block for ARM. The return sequence is just two instructions usually.

rnk edited the summary of this revision. (Show Details)Jan 26 2017, 11:40 AM
iteratee added inline comments.Jan 30 2017, 3:04 PM
lib/CodeGen/BranchFolding.cpp
521 ↗(On Diff #85822)

Unforturnately there are platforms where this isn't sufficient. I believe ARM is one of them.

rnk added inline comments.Jan 30 2017, 3:07 PM
lib/CodeGen/BranchFolding.cpp
521 ↗(On Diff #85822)

For all the ARM examples I constructed, isReturnBlock appeared to be accurate.

iteratee added inline comments.Jan 30 2017, 3:39 PM
lib/CodeGen/BranchFolding.cpp
521 ↗(On Diff #85822)

OK, I have data.

isReturnBlock is currently insufficient for Thumb (That's why I thought ARM), Hexagon, Mips and XCore.
Arguably, this should go in anyway and those platforms should be fixed.

Funnily enough, this could cause switching away from Thumb to reduce code size.

rengolin added inline comments.
lib/CodeGen/BranchFolding.cpp
521 ↗(On Diff #85822)

Can you be more specific for "insufficient"?

What's the risk/cost? If they're too big, than "fixing it later" might not be a good idea.

Also, who's fixing it?

iteratee added inline comments.Jan 31 2017, 11:09 AM
lib/CodeGen/BranchFolding.cpp
521 ↗(On Diff #85822)

Those platforms don't correctly mark return instructions as returns.

Given that this is a size decrease on all platforms where return instructions are correctly marked, I see no problem with it going in as is.

The platform owners should fix it if they care.

rnk added inline comments.Jan 31 2017, 11:13 AM
lib/CodeGen/BranchFolding.cpp
521 ↗(On Diff #85822)

Can you be more specific for "insufficient"?

It returns false on blocks that end in returns. Grepping through ARMThumbInstrInfo suggests that some but not all returns have the isReturn flag set, so this probably only affects some small number of returns.

What's the risk/cost? If they're too big, than "fixing it later" might not be a good idea.

This change makes us tail merge small identical noreturn blocks (zero successors without a return). The risk is that we tail merge a return block that was duplicated to get better code layout. In practice, I have found it very hard to show a functional difference. The ARM backend will do things like predicating entire small return blocks, making it really hard to construct a test case if you don't know both the ARM ISA and the ARM backend options well.

Also, who's fixing it?

I wasn't going to. The risk is really low. I doubt this transform will ever fire on important code for ARM.

rengolin added inline comments.Jan 31 2017, 11:36 AM
lib/CodeGen/BranchFolding.cpp
521 ↗(On Diff #85822)

I wasn't going to. The risk is really low. I doubt this transform will ever fire on important code for ARM.

Can you add a FIXME to alert the respective back-end owners that their targets are (possibly) negatively affected by the change?

The platform owners should fix it if they care.

This is extremely selfish.

If you find a problem on some architecture that is not your primary, the least you can do is to contact them and get their reviews.

I'm usually responsive and pro-active (as this reply is demonstration), so you can't even use the argument that you tried in the past and failed.

I'm not sure how you came to this conclusion, but I wish you'd be more careful next time.

sdardis added a subscriber: sdardis.Feb 1 2017, 3:23 AM
sdardis added inline comments.
lib/CodeGen/BranchFolding.cpp
521 ↗(On Diff #85822)

isReturnBlock is currently insufficient for Thumb (That's why I thought ARM), Hexagon, Mips and XCore.
Arguably, this should go in anyway and those platforms should be fixed.

Can you file a bug report on this, CCing the code owners of the affected targets?

rnk added a comment.Feb 1 2017, 1:36 PM

Aside from the possible issue with isReturnBlock, are there any comments on the patch functionality?

lib/CodeGen/BranchFolding.cpp
521 ↗(On Diff #85822)

I'm not sure what issue Kyle is seeing. It looks like we have return instructions for ARM, thumb1, and thumb2, so isReturnBlock should work properly:

$ git grep isReturn ../lib/Target/ARM/*.td
../lib/Target/ARM/ARMCallingConv.td:def CSR_AAPCS_ThisReturn : CalleeSavedRegs<(add LR, R11, R10, R9, R8, R7, R6,
../lib/Target/ARM/ARMCallingConv.td:def CSR_iOS_ThisReturn : CalleeSavedRegs<(add LR, R7, R6, R5, R4,
../lib/Target/ARM/ARMCallingConv.td:                                         (sub CSR_AAPCS_ThisReturn, R9))>;
../lib/Target/ARM/ARMInstrInfo.td:let isReturn = 1, isTerminator = 1, isBarrier = 1 in {
../lib/Target/ARM/ARMInstrInfo.td:let isCall = 1, isTerminator = 1, isReturn = 1, isBarrier = 1, Uses = [SP] in {
../lib/Target/ARM/ARMInstrInfo.td:let isReturn = 1, isBarrier = 1, isTerminator = 1, Defs = [PC] in
../lib/Target/ARM/ARMInstrInfo.td:let isReturn = 1, isTerminator = 1, isBarrier = 1, mayLoad = 1,
../lib/Target/ARM/ARMInstrThumb.td:let isReturn = 1, isTerminator = 1, isBarrier = 1 in {
../lib/Target/ARM/ARMInstrThumb.td:let isCall = 1, isTerminator = 1, isReturn = 1, isBarrier = 1 in {
../lib/Target/ARM/ARMInstrThumb.td:let isReturn = 1, isTerminator = 1, isBarrier = 1, mayLoad = 1,
../lib/Target/ARM/ARMInstrThumb2.td:let isReturn = 1, isTerminator = 1, isBarrier = 1, mayLoad = 1,
../lib/Target/ARM/ARMInstrThumb2.td:let isCall = 1, isTerminator = 1, isReturn = 1, isBarrier = 1 in {
../lib/Target/ARM/ARMInstrThumb2.td:let isReturn = 1, isBarrier = 1, isTerminator = 1, Defs = [PC] in
../lib/Target/ARM/ARMInstrThumb2.td:let isReturn = 1, isBarrier = 1, isTerminator = 1, Defs = [PC] in
In D29153#663862, @rnk wrote:

Aside from the possible issue with isReturnBlock, are there any comments on the patch functionality?

No. I'm happy with a FIXME and a bug open, copying the affected target's code owners, and let them decide if this is a bug or not.

This seems low priority enough that we can do on the side, later.

cheers,
--renato

rnk added a comment.Feb 14 2017, 1:07 PM

No. I'm happy with a FIXME and a bug open, copying the affected target's code owners, and let them decide if this is a bug or not.

https://bugs.llvm.org/show_bug.cgi?id=31960

I think extending the check to look for indirect branches as well will be enough to make sure this doesn't go wrong.

rnk added a comment.Feb 14 2017, 1:09 PM

I'm going to go ahead and land this. Most people on the review seem to feel like this is a positive, low risk change, now that we've sorted out the heuristic for what a block ending in unreachable looks like.

This revision was automatically updated to reflect the committed changes.