[LLVMdev] [PATH] Add sub.ovf/mul.ovf intrinsics

[Eli Friedman]

On Tue, Dec 9, 2008 at 9:53 AM, Eli Friedman <eli.friedman at gmail.com> wrote:
> On Tue, Dec 9, 2008 at 6:11 AM, Zoltan Varga <vargaz at gmail.com> wrote:
>>> It would be better to implement a target-independent check for
>>> overflow for the "Legal" case (like how SADDO does). Hacker's > Delight
>>> has some hints on how to do this. It's not easy for the signed case,
>>> but is do-able.
>>
>> It can be lowered to a division + a branch, so it would be
>> inefficient, plus it would
>> be a lot of work to implement it correctly (for me at least).
>
> If you can get the relevant high product (UMUL_LOHI and friends), it's
> a relatively straightforward comparison.  Otherwise, yes, the general
> case is quite tricky; inserting a division here is non-trivial.
>
> There's also the special-case of multiplication by a constant: here,
> the computation can be done with a single straightforward comparison.

Oh, and a few more possibilities:
1) http://www.hackersdelight.org/HDcode/multover.c, for unsigned;
whether this is a good idea depends on the speed of the nlz
implementation.  That version uses branches, but of course it can also
be done by ORing together the comparison results.
2) (C && A) | MulOverflow(B,C) | MulOverflow(A,D) | AddOverflow(B*C,
MulHi(B, D), A*D), where A, B are the two halves of Op1, C, D are the
two halves of Op2, and all operations are in the width of the halves.
This could be useful on x86 for 64-bit multiplies; it's not cheap, but
it can't really get much cheaper (besides the fact that Legalize can't
insert branches, which would be a nice improvement here).  This is
roughly just adding overflow checks to every step of the normal 64-bit
multiply splitting algorithm.
3) (C && A) || ((C?B:D)*(C?C:A) + (B*D>>(Width/2)) >= 2^(Width/2)),
for unsigned, where A, B are the two halves of Op1, C, D are the two
halves of Op2, Width is the width of the original operands, and
everything is done zero-extended in the original width.  Not the
greatest approach, but it's difficult to do much better with just
regular arithmetic and conditionals (besides the divide and compare
approach, which as far as I know isn't feasible here because of the
required chain?).

-Eli