Page MenuHomePhabricator

[IfConversion] Maintain the CFG when predicating/merging blocks in IfConvert*
ClosedPublic

Authored by uabelho on Jun 12 2017, 12:24 AM.

Details

Summary

This fixes PR32721 in IfConvertTriangle and possible similar problems in
IfConvertSimple, IfConvertDiamond and IfConvertForkedDiamond.

In PR32721 we had a triangle

EBB
| \
|  |
| TBB
|  /
FBB

where FBB didn't have any successors at all since it ended with an
unconditional return. Then TBB and FBB were be merged into EBB, but EBB
would still keep its successors, and the use of analyzeBranch and
CorrectExtraCFGEdges wouldn't help to remove them since the return
instruction is not analyzable (at least not on ARM).

The edge updating code and branch probability updating code is now pushed
into MergeBlocks() which allows us to share the same update logic between
more callsites. This lets us remove several dependencies on analyzeBranch
and completely eliminate RemoveExtraEdges.

One thing that showed up with this patch was that IfConversion sometimes
left a successor with 0% probability even if there was no branch or
fallthrough to the successor.

One such example from the test case ifcvt_bad_zero_prob_succ.mir. The
indirect branch tBRIND can only jump to bb.1, but without the patch we
got:

bb.0:
  successors: %bb.1(0x80000000)

bb.1:
  successors: %bb.1(0x80000000), %bb.2(0x00000000)
  tBRIND %r1, 1, %cpsr
  B %bb.1

bb.2:

There is no way to jump from bb.1 to bb2, but still there is a 0% edge
from bb.1 to bb.2.

With the patch applied we instead get the expected:

bb.0:
  successors: %bb.1(0x80000000)

bb.1:
  successors: %bb.1(0x80000000)
  tBRIND %r1, 1, %cpsr
  B %bb.1

Since bb.2 had no predecessor at all, it was removed.

Several testcases had to be updated due to this since the removed
successor made the "Branch Probability Basic Block Placement" pass
sometimes place blocks in a different order.

Finally added a couple of new test cases:

  • PR32721_ifcvt_triangle_unanalyzable.mir: Regression test for the original problem dexcribed in PR 32721.
  • ifcvt_triangleWoCvtToNextEdge.mir: Regression test for problem that caused a revert of my first attempt to solve PR 32721.
  • ifcvt_simple_bad_zero_prob_succ.mir: Test case showing the problem where a wrong successor with 0% probability was previously left.
  • ifcvt_[diamond|forked_diamond|simple]_unanalyzable.mir Very simple test cases for the simple and (forked) diamond cases involving unanalyzable branches that can be nice to have as a base if wanting to write more complicated tests.

Diff Detail

Repository
rL LLVM

Event Timeline

uabelho created this revision.Jun 12 2017, 12:24 AM
davide added a subscriber: davide.Jun 12 2017, 12:25 AM

Ok, a new attempt to fix this.

Of course I would like to have done the patch in smaller steps, as I tried in https://reviews.llvm.org/D33037,
but since I came to the conclusion that I needed to attack MergeBlocks I kind of had to update all the different
IfConvert* cases in one go.

It's incredible how complicated the IfConverter is, but at least I feel this is a step in the right direction.

Fire away :)

grosser resigned from this revision.Jun 13 2017, 5:09 AM

Thanks for the contribution!

I don't think I am an expert on the if-converter. If you feel you really need my input, please add me back.

iteratee edited edge metadata.Jun 19 2017, 1:59 PM

Mostly looks good. It will be easier to follow when you factor out the NFC sections and rebase.

lib/CodeGen/IfConversion.cpp
1487 ↗(On Diff #102155)

This section looks like an NFC. Please commit it first, and then rebase this patch on top of it.

1587 ↗(On Diff #102155)

Same for this section. Please factor out the NFC change and commit it first.

uabelho updated this revision to Diff 103165.Jun 20 2017, 12:08 AM

Pulled out a few NFC changes to https://reviews.llvm.org/D34388 according to Kyle's comments and rebased on top of that.

uabelho marked 2 inline comments as done.Jun 20 2017, 12:10 AM

Thanks!

Ping!

Any other comments on this?

kparzysz accepted this revision.Jul 21 2017, 11:13 AM

I've run through some of our tests and they all passed. LGTM

This revision is now accepted and ready to land.Jul 21 2017, 11:13 AM

I've run through some of our tests and they all passed. LGTM

Thank you kparzysz!

I've been on vacation the last month, but I'll try to push this in a few days when I'm up to speed again.

uabelho updated this revision to Diff 110567.Aug 10 2017, 6:28 AM

Rebased the patch to top of tree.

Needed another change in test/CodeGen/PowerPC/logic-ops-on-compares.ll due to a new test
that had been added to that file since last rebase.

This revision was automatically updated to reflect the committed changes.