This is an archive of the discontinued LLVM Phabricator instance.

[DAGCombiner] Optimize SMULO/UMULO if we can prove that overflow is impossible.
ClosedPublic

Authored by craig.topper on Feb 21 2021, 11:58 AM.

Details

Summary

Using ComputeNumSignBits or computeKnownBits we might be able
to determine that overflow is impossible.

This especially helps after type legalization if the type was
promoted from a type with half the bits or more. Type legalization
conservatively creates a promoted smulo/umulo and an overflow
check for the promoted bits. The overflow from the promoted
smulo/umulo is ORed with the result of the promoted bits
overflow check. Proving that the promoted smulo/umulo can never
overflow will leave us with just the promoted bits overflow check.

Diff Detail

Event Timeline

craig.topper created this revision.Feb 21 2021, 11:58 AM
craig.topper requested review of this revision.Feb 21 2021, 11:58 AM
Herald added a project: Restricted Project. · View Herald TranscriptFeb 21 2021, 11:58 AM
Herald added a subscriber: MaskRay. · View Herald Transcript
RKSimon added inline comments.Feb 21 2021, 1:17 PM
llvm/test/CodeGen/X86/xmulo.ll
11 ↗(On Diff #325329)

Are we missing constant folding?

craig.topper added inline comments.Feb 21 2021, 2:59 PM
llvm/test/CodeGen/X86/xmulo.ll
11 ↗(On Diff #325329)

Looks like it. Doesn't look like we have it for ADDO either.

craig.topper added inline comments.Feb 23 2021, 12:16 PM
llvm/test/CodeGen/X86/xmulo.ll
11 ↗(On Diff #325329)

Is that a blocker for this patch?

RKSimon added inline comments.Feb 24 2021, 3:14 AM
llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp
4678

Is it worth moving this to something like:

KnownBits KnownBits::umul_ov(const KnownBits &LHS,const KnownBits &RHS,llvm:Optional<bool> &Overflow)
llvm/test/CodeGen/X86/xmulo.ll
11 ↗(On Diff #325329)

I've put very basic constant folding support in rG8082bfe7e58d89f6f065fab101db3481516afdbe

craig.topper added inline comments.Feb 24 2021, 11:07 AM
llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp
4678

Are you suggesting to merge this with computeForMul? Just calling APInt::umul_ov doesn't give you the right known bits for the data result. So we would need the logic from computeForMul.

craig.topper added inline comments.Feb 24 2021, 11:11 AM
llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp
4678

ValueTracking's computeOverflowForUnsignedMul converts KnownBits to ConstantRange and goes through ConstantRange::unsignedMulMayOverflow

RKSimon accepted this revision.Feb 26 2021, 2:31 PM

LGTM - hopefully we can merge the mulo knownbits implementations over time (having just tried to do this for shifts I know how many weird issues can arise though....).

This revision is now accepted and ready to land.Feb 26 2021, 2:31 PM