Page MenuHomePhabricator

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

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

Details

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

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

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.

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 updated this revision to Diff 175827.Nov 29 2018, 12:43 AM

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

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

Please rebase/update

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

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

@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
1076–1077 ↗(On Diff #204296)

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
1074 ↗(On Diff #204382)

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
1074 ↗(On Diff #204382)

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

Thanks!

@rnk, @RKSimon fine for you too?

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

LGTM.

This revision was automatically updated to reflect the committed changes.