This is an archive of the discontinued LLVM Phabricator instance.

[IPSCCP] Fix a problem with removing labels in a switch with undef condition
ClosedPublic

Authored by bjope on Sep 18 2018, 7:15 AM.

Details

Summary

Before removing basic blocks that ipsccp has considered as dead
all uses of the basic block label must be removed. That is done
by calling ConstantFoldTerminator on the users. An exception
is when the branch condition is an undef value. In such
scenarios ipsccp is using some internal assumptions regarding
which edge in the control flow that should remain, while
ConstantFoldTerminator don't know how to fold the terminator.

The problem addressed here is related to ConstantFoldTerminator's
ability to rewrite a 'switch' into a conditional 'br'. In such
situations ConstantFoldTerminator returns true indicating that
the terminator has been rewritten. However, ipsccp treated the
true value as if the edge to the dead basic block had been
removed. So the code for resolving an undef branch condition
did not trigger, and we ended up with assertion that there were
uses remaining when deleting the basic block.

For ipsccp it is important that the original terminator is kept
untouched by ConstantFoldTerminator when branching on undef values.
Otherwise the logic for which edge that should remain in case of
undef conditions will be messed up.
The solution is to add a parameter to ConstantFoldTerminator
to optionally restrict the folding to leave the terminator untouched
unless it can be folded into an unconditional branch.

Diff Detail

Event Timeline

bjope created this revision.Sep 18 2018, 7:15 AM
efriedma added inline comments.Sep 18 2018, 2:43 PM
lib/Transforms/Scalar/SCCP.cpp
2020

Maybe it would be more straightforward here to figure out the valid successor using isEdgeFeasible(), and explicitly emit the unconditional branch we want, instead of calling ConstantFoldTerminator.

I mean, the patch works as-is, but adding more flags to commonly used APIs like ConstantFoldTerminator makes them more difficult to understand.

bjope updated this revision to Diff 166079.Sep 19 2018, 2:41 AM
  • Got rid of the changes in ConstantFoldTerminator.
  • Now we force folding for indeterminate values before calling ConstantFoldTerminator (so now we only need to call ConstantFoldTerminator one time for the indeterminate case).
bjope updated this revision to Diff 166080.Sep 19 2018, 2:43 AM

Removed a code comment uploaded by mistake in previous diff.

fhahn accepted this revision.Sep 19 2018, 3:23 AM

LGTM

lib/Transforms/Scalar/SCCP.cpp
1891

This is an internal function, not sure if we need a doxygen comment here.

1895

one ; too much

1924

no need for explicit return here.

test/Transforms/SCCP/switch-undef-constantfoldterminator.ll
9

I would drop the reference to the line number in Value.cpp, as it is subject to change.

This revision is now accepted and ready to land.Sep 19 2018, 3:23 AM
fhahn added a comment.Sep 19 2018, 3:25 AM

It's probably worth waiting with committing until tomorrow, in case Eli has any more suggestions

bjope updated this revision to Diff 166084.Sep 19 2018, 4:01 AM

Fixed some mistakes detected by Florian. Thanks alot for those comments!

bjope marked 4 inline comments as done.Sep 19 2018, 4:07 AM
bjope added inline comments.
lib/Transforms/Scalar/SCCP.cpp
2020

I got rid of the changes to ConstantFoldTerminator by always forcing the edge for the indeteminate case before calling ConstantFoldTerminator. Maybe not exactly what you meant by using isEdgeFeasible(), but it makes it possible to still reuse ConstantFoldTerminator for rewriting the terminator into an unconditional branch.

This revision was automatically updated to reflect the committed changes.