This is an archive of the discontinued LLVM Phabricator instance.

Differential D54411

[Codegen] Merge tail blocks with no successors after block placement
ClosedPublic

Authored by xbolva00 on Nov 11 2018, 6:50 PM.

Details

Reviewers
haicheng
aheejin
craig.topper
rnk
RKSimon
Jim
dmgreen
Commits
rG896ece41e478: [Codegen] Merge tail blocks with no successors after block placement
rL363284: [Codegen] Merge tail blocks with no successors after block placement
Summary

I found the following case having tail blocks with no successors merging opportunities after block placement.

Before block placement:

bb0:

...
bne a0, 0, bb2:

bb1:

mv a0, 1
ret

bb2:

...

bb3:

mv a0, 1
ret

bb4:

mv a0, -1
ret

The conditional branch bne in bb0 is opposite to beq.

After block placement:

bb0:

...
beq a0, 0, bb1

bb2:

...

bb4:

mv a0, -1
ret

bb1:

mv a0, 1
ret

bb3:

mv a0, 1
ret

After block placement, that appears new tail merging opportunity, bb1 and bb3 can be merged as one block. So the conditional constraint for merging tail blocks with no successors should be removed. In my experiment for RISC-V, it decreases code size.

Author of original patch: Jim Lin

Diff Detail

Repository
rL LLVM

Event Timeline

Jim created this revision.Nov 11 2018, 6:50 PM
Herald added subscribers: llvm-commits, PkmX. · View Herald TranscriptNov 11 2018, 6:50 PM
Jim retitled this revision from [Codegen] Merge tail blocks after block placement to [Codegen] Merge tail blocks with no successors after block placement.Nov 11 2018, 6:52 PM
dmgreen added a subscriber: dmgreen.Nov 13 2018, 8:25 AM

Hello. I agree that this looks like an improvement. Can you add a testcase?

kito-cheng added a subscriber: kito-cheng.Nov 14 2018, 12:54 AM
Jim updated this revision to Diff 175614.Nov 27 2018, 9:59 PM

Update test cases.

Tail blocks with no successors can be merged after block placement in test cases.

Herald added subscribers: aheejin, jgravelle-google, sbc100 and 2 others. · View Herald TranscriptNov 27 2018, 9:59 PM
aheejin added inline comments.Nov 28 2018, 5:24 PM
test/CodeGen/WebAssembly/cfg-stackify.ll
544 ↗(On Diff #175614)

You can probably drop this line, because this test is only checking control flow instructions.

Jim added a reviewer: aheejin.Nov 29 2018, 12:03 AM
Jim updated this revision to Diff 175827.Nov 29 2018, 12:43 AM

Remove unnecessary checking in test/CodeGen/WebAssembly/cfg-stackify.ll.

dmgreen added reviewers: craig.topper, rnk, RKSimon.Dec 2 2018, 12:06 PM

I ran a few bootstraps to check compile time (on AArch64). It didn't seem to make any noticable difference there, and this certainly looks like its good for codesize.

Adding some people who may know about x86 tests (which look fine to me, but I'm no expert)

test/CodeGen/X86/loop-search.ll
25 ↗(On Diff #175827)

Looks like this comment can be removed now

test/CodeGen/X86/tail-opts.ll
439 ↗(On Diff #175827)

Can you explain this change? The comment makes it look like it should be the same test as above.

But it somehow has different fall-through branches with the switches?

Jim updated this revision to Diff 176552.Dec 4 2018, 12:01 AM

Remove unused fixme comment in test/CodeGen/X86/loop-search.ll.

aheejin added inline comments.Mar 24 2019, 9:27 AM
test/CodeGen/WebAssembly/cfg-stackify.ll
544 ↗(On Diff #175614)

I'm not sure if you are still planning to land this, but we deleted all OPT check lines in this file in D58953, so I think you should drop all changes to this file.

Herald added a project: Restricted Project. · View Herald TranscriptMar 24 2019, 9:27 AM
xbolva00 added a subscriber: xbolva00.Mar 29 2019, 12:32 AM

Please rebase/update

craig.topper added a comment.Apr 2 2019, 1:46 PM

The X86 changes look ok to me except the open question on tail-opts.ll

RKSimon added inline comments.Apr 3 2019, 2:18 AM
test/CodeGen/X86/tail-opts.ll
439 ↗(On Diff #175827)

icmp with undef will now constant fold in SelectionDAG - you're probably being affected by that

xbolva00 added a comment.Jun 4 2019, 2:14 PM

@Jim are you going to update this patch?

xbolva00 commandeered this revision.Jun 12 2019, 7:33 AM
xbolva00 added a reviewer: Jim.
xbolva00 updated this revision to Diff 204289.Jun 12 2019, 7:44 AM
xbolva00 marked an inline comment as done.

Rebased to master.

Please check it again.

xbolva00 mentioned this in rL363173: [NFC[ Updated tests for D54411.Jun 12 2019, 7:58 AM
xbolva00 mentioned this in rG48365ec3e14a: [NFC[ Updated tests for D54411.
xbolva00 updated this revision to Diff 204296.Jun 12 2019, 8:21 AM

Updated

xbolva00 added a comment.Jun 12 2019, 8:25 AM

@craig.topper , @dmgreen if patch is ok now, please approve it formally. Thanks.

xbolva00 edited the summary of this revision. (Show Details)Jun 12 2019, 8:26 AM
rnk added inline comments.Jun 12 2019, 3:36 PM
lib/CodeGen/BranchFolding.cpp
1077–1078

The fact that you have to update so many tests shows that this comment is incorrect, at the very least.

test/CodeGen/X86/tail-opts.ll
589 ↗(On Diff #204296)

I think we have to fix this test by replacing uses of undef with some new i32 parameter, then it will test the relevant code again.

xbolva00 updated this revision to Diff 204376.Jun 12 2019, 3:47 PM

FIxed review notes by @rnk. Thanks.

xbolva00 updated this revision to Diff 204379.Jun 12 2019, 3:48 PM

Fixed all undefs.

xbolva00 updated this revision to Diff 204382.Jun 12 2019, 4:09 PM

Preserve test logic in tail opts.

Jim added inline comments.Jun 13 2019, 1:22 AM
lib/CodeGen/BranchFolding.cpp
1075

This change is it neccessary?

test/CodeGen/X86/tail-opts.ll
439 ↗(On Diff #175827)

This testcase tests that two tail_call_me can't be merged into one for performance issue.
But bby and bbx are likely the same. This patch makes bby and bbx merge into one.
And make tail_call_me only need one.
So the two comparison of switch in bby and bbx should be changed difference.

This is my testcase to keep tail_call_me tail-duplicated.

define void @two_nosize(i32 %x, i32 %y, i32 %z) nounwind {
entry:
  %0 = icmp eq i32 %x, 0
  br i1 %0, label %bbx, label %bby

bby:
  switch i32 %y, label %bb7 [
    i32 0, label %return
  ]

bb7:
  store volatile i32 0, i32* @XYZ
  tail call void @tail_call_me()
  ret void

bbx:
  switch i32 %z, label %bb12 [
    i32 -1, label %return
  ]

bb12:
  store volatile i32 0, i32* @XYZ
  tail call void @tail_call_me()
  ret void

return:
  ret void
}

Let two comparison compare with 0 or -1. So that tail call tail_call_me can be put on the fall through edge.

xbolva00 marked 2 inline comments as done.Jun 13 2019, 1:50 AM
xbolva00 added inline comments.
lib/CodeGen/BranchFolding.cpp
1075

I think it is fine since we touch this code/function, we should clang-format it too..

test/CodeGen/X86/tail-opts.ll
439 ↗(On Diff #175827)

Thanks for testcase, I will update it.

xbolva00 updated this revision to Diff 204453.Jun 13 2019, 2:09 AM

Updated tail opts with testcase from @Jim. Thanks.

Jim added inline comments.Jun 13 2019, 2:29 AM
test/CodeGen/X86/tail-opts.ll
439 ↗(On Diff #175827)

Thanks.

dmgreen accepted this revision.Jun 13 2019, 4:27 AM

LGTM, if everyone are happy with tests.

Thanks @xbolva00 for pushing this forward, and thanks @Jim for the idea and getting things started!

This revision is now accepted and ready to land.Jun 13 2019, 4:27 AM
xbolva00 added a comment.Jun 13 2019, 4:53 AM

Thanks!

@rnk, @RKSimon fine for you too?

Jim accepted this revision.Jun 13 2019, 5:09 AM

LGTM.

Closed by commit rL363284: [Codegen] Merge tail blocks with no successors after block placement (authored by xbolva00). · Explain WhyJun 13 2019, 11:08 AM
This revision was automatically updated to reflect the committed changes.
Herald added a subscriber: jsji. · View Herald TranscriptJun 13 2019, 11:08 AM
xbolva00 mentioned this in rL363285: [NFC] Updated testcase for D54411/rL363284.Jun 13 2019, 11:10 AM
xbolva00 mentioned this in rGa9d8388e80c2: [NFC] Updated testcase for D54411/rL363284.

Revision Contents

PathSize
lib/
CodeGen/
34 lines

Diff 173270

lib/CodeGen/BranchFolding.cpp

Show First 20 Lines • Show All 1,066 Lines • ▼ Show 20 Lines while (MergePotentials.size() > 1) {
MadeChange = true; MadeChange = true;
} }
return MadeChange; return MadeChange;
} }
bool BranchFolder::TailMergeBlocks(MachineFunction &MF) { bool BranchFolder::TailMergeBlocks(MachineFunction &MF) {
bool MadeChange = false; bool MadeChange = false;
if (!EnableTailMerge) return MadeChange; if (!EnableTailMerge) return MadeChange;
JimUnsubmitted
Not Done
ReplyInline Actions

This change is it neccessary?

Jim: This change is it neccessary?
xbolva00AuthorUnsubmitted
Done
ReplyInline Actions

I think it is fine since we touch this code/function, we should clang-format it too..

xbolva00: I think it is fine since we touch this code/function, we should clang-format it too..
// First find blocks with no successors. // First find blocks with no successors.
// Block placement does not create new tail merging opportunities for these
// blocks.
rnkUnsubmitted
Not Done
ReplyInline Actions

The fact that you have to update so many tests shows that this comment is incorrect, at the very least.

rnk: The fact that you have to update so many tests shows that this comment is incorrect, at the…
if (!AfterBlockPlacement) {
MergePotentials.clear(); MergePotentials.clear();
for (MachineBasicBlock &MBB : MF) { for (MachineBasicBlock &MBB : MF) {
if (MergePotentials.size() == TailMergeThreshold) if (MergePotentials.size() == TailMergeThreshold)
break; break;
if (!TriedMerging.count(&MBB) && MBB.succ_empty()) if (!TriedMerging.count(&MBB) && MBB.succ_empty())
MergePotentials.push_back(MergePotentialsElt(HashEndOfMBB(MBB), &MBB)); MergePotentials.push_back(MergePotentialsElt(HashEndOfMBB(MBB), &MBB));
} }
// If this is a large problem, avoid visiting the same basic blocks // If this is a large problem, avoid visiting the same basic blocks
// multiple times. // multiple times.
if (MergePotentials.size() == TailMergeThreshold) if (MergePotentials.size() == TailMergeThreshold)
for (unsigned i = 0, e = MergePotentials.size(); i != e; ++i) for (unsigned i = 0, e = MergePotentials.size(); i != e; ++i)
TriedMerging.insert(MergePotentials[i].getBlock()); TriedMerging.insert(MergePotentials[i].getBlock());
// See if we can do any tail merging on those. // See if we can do any tail merging on those.
if (MergePotentials.size() >= 2) if (MergePotentials.size() >= 2)
MadeChange |= TryTailMergeBlocks(nullptr, nullptr, MinCommonTailLength); MadeChange |= TryTailMergeBlocks(nullptr, nullptr, MinCommonTailLength);
}
// Look at blocks (IBB) with multiple predecessors (PBB). // Look at blocks (IBB) with multiple predecessors (PBB).
// We change each predecessor to a canonical form, by // We change each predecessor to a canonical form, by
// (1) temporarily removing any unconditional branch from the predecessor // (1) temporarily removing any unconditional branch from the predecessor
// to IBB, and // to IBB, and
// (2) alter conditional branches so they branch to the other block // (2) alter conditional branches so they branch to the other block
// not IBB; this may require adding back an unconditional branch to IBB // not IBB; this may require adding back an unconditional branch to IBB
// later, where there wasn't one coming in. E.g. // later, where there wasn't one coming in. E.g.
▲ Show 20 Lines • Show All 1,027 Lines • Show Last 20 Lines