This is an archive of the discontinued LLVM Phabricator instance.

[SimplifyCFG] FoldTwoEntryPHINode(): don't bailout on i1 PHI's if we can hoist a 'not' from incoming values
ClosedPublic

Authored by lebedev.ri on Jul 23 2019, 7:23 AM.

Details

Summary

As it can be seen in the tests in D65143, even though we have formed an '@llvm.umul.with.overflow'
and got rid of potential for division-by-zero, the control flow remains, we still have that branch.

We have this condition:

// Don't fold i1 branches on PHIs which contain binary operators
// These can often be turned into switches and other things.
if (PN->getType()->isIntegerTy(1) &&
    (isa<BinaryOperator>(PN->getIncomingValue(0)) ||
     isa<BinaryOperator>(PN->getIncomingValue(1)) ||
     isa<BinaryOperator>(IfCond)))
  return false;

which was added back in rL121764 to help with select formation i think?

That check prevents us to flatten the CFG here, even though we know
we no longer need that guard and will be able to drop everything
but the '@llvm.umul.with.overflow' + not.

As it can be seen from tests, we end here because the not is being
sinked into the PHI's incoming values by InstCombine,
so we can't workaround this by hoisting it to after PHI.

Thus i suggest that we relax that check to not bailout if we'd get to hoist the not.

Diff Detail

Event Timeline

lebedev.ri created this revision.Jul 23 2019, 7:23 AM

To be noted, i'm fixing this function in particular because it is the pass that folds the case witout not, in -O3
(llvm/test/Transforms/PhaseOrdering/unsigned-multiply-overflow-check.ll, will_not_overflow()).
I suppose the alternative approach would be to teach some other pass that it is okay to hoist this @llvm.umul.with.overflow here.

spatel accepted this revision.Jul 31 2019, 5:19 AM

This looks like a safe easing of the heuristic, so LGTM.
It would be nice if we could lift "IsFreeToInvert()" from InstCombine to some common location and reuse that here as a follow-up. That function goes further than what is proposed here, and I'm not sure how the extra clauses will interact with SimplifyCFG, so that requires some extra tests to see if it behaving as intended in relation this heuristic.

This revision is now accepted and ready to land.Jul 31 2019, 5:19 AM

This looks like a safe easing of the heuristic, so LGTM.

Thank you for the review.

It would be nice if we could lift "IsFreeToInvert()" from InstCombine to some common location and reuse that here as a follow-up. That function goes further than what is proposed here, and I'm not sure how the extra clauses will interact with SimplifyCFG, so that requires some extra tests to see if it behaving as intended in relation this heuristic.

Yeah, they do similar things, but indeed it isn't obvious if it would be a good fit here.

Rebased, NFC.

lebedev.ri edited the summary of this revision. (Show Details)Aug 29 2019, 5:30 AM
This revision was automatically updated to reflect the committed changes.