[IfConversion] Keep the CFG updated incrementally in IfConvertTriangle
ClosedPublic

Authored by uabelho on May 10 2017, 6:22 AM.

Details

Summary

Instead of using RemoveExtraEdges (which uses analyzeBranch, which cannot
always be trusted) at the end to fixup the CFG we keep the CFG updated as
we go along and remove or add branches and merge blocks.

This way we won't have any problems if the involved MBBs contain
unanalyzable instructions.

This fixes PR32721.

In that case 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).

Diff Detail

Repository
rL LLVM
uabelho created this revision.May 10 2017, 6:22 AM

I have on purpose not attacked IfConvertSimple, IfConvertForkedDiamond
and IfConvertDiamond to keep the size of the patch down, and I haven't seen any
test case where they actually go wrong, but I think they suffer from similar
problems since they also use RemoveExtraEdges/analyzeBranch to fix the CFG at
the end.

If you think this patch changes IfConversion in the right direction then I think
it would be good idea to try to remove the other uses of RemoveExtraEdges as well
later.

I have on purpose not attacked IfConvertSimple, IfConvertForkedDiamond
and IfConvertDiamond to keep the size of the patch down, and I haven't seen any
test case where they actually go wrong, but I think they suffer from similar
problems since they also use RemoveExtraEdges/analyzeBranch to fix the CFG at
the end.

IfConvertForkedDiamond only applies to analyzable branches, so it should be safe.
If you change the others, it would be good to change it as well for consistency.

I'll leave time for others to comment, but overall it looks fine to me.

I have on purpose not attacked IfConvertSimple, IfConvertForkedDiamond
and IfConvertDiamond to keep the size of the patch down, and I haven't seen any
test case where they actually go wrong, but I think they suffer from similar
problems since they also use RemoveExtraEdges/analyzeBranch to fix the CFG at
the end.

IfConvertForkedDiamond only applies to analyzable branches, so it should be safe.

Possible. I haven't tried to provoke it to miscompile due to unanalyzable instructions.

If you change the others, it would be good to change it as well for consistency.

Yes I think so too.

In general I think we should try to avoid uses of analyzeBranch to fix things since it cannot be
trusted in all cases anyway. Doing optimizations based on its result is no problem but the use
in RemoveExtraEdges is problematic.

I'll leave time for others to comment, but overall it looks fine to me.

Thanks!

Btw, without the fix we get the following result from IfConversion for the testcase:

body: |

bb.0:

bb.1:
  successors: %bb.2(0x40000000), %bb.1(0x00000000)

  BX_RET 14, 0

bb.2:

...

So bb.1 has both bb.2 and itself as successors, even if it only contains an unconditional return.

Btw, without the fix we get the following result from IfConversion for the testcase:

body: |

bb.0:

bb.1:
  successors: %bb.2(0x40000000), %bb.1(0x00000000)

  BX_RET 14, 0

bb.2:

...

So bb.1 has both bb.2 and itself as successors, even if it only contains an unconditional return.

This is indeed wrong (but hard to catch with the MachineVerifier so it probably went unnoticed).

I leave the patch review to @iteratee.

test/CodeGen/MIR/ARM/PR32721_ifcvt_triangle_unanalyzable.mir
6 ↗(On Diff #98430)

FYI: The latest MIR parser can finally deduce the successor lists in most cases if you leave them out. It should work for this test.

iteratee accepted this revision.May 11 2017, 11:09 AM

Feel free to send me patches that update the other parts of IfConversion

This revision is now accepted and ready to land.May 11 2017, 11:09 AM
uabelho updated this revision to Diff 98722.May 11 2017, 11:00 PM

Removed the "successors" lists in the test case as suggested by Matthias since
they are computed correctly anyway by the MIr pasrser.

uabelho marked an inline comment as done.May 11 2017, 11:00 PM
uabelho added inline comments.
test/CodeGen/MIR/ARM/PR32721_ifcvt_triangle_unanalyzable.mir
6 ↗(On Diff #98430)

Thanks!

uabelho marked an inline comment as done.May 11 2017, 11:01 PM

Feel free to send me patches that update the other parts of IfConversion

Thanks!

I'll try to find the time to do that!

This revision was automatically updated to reflect the committed changes.