Hi, Here is the next iteration of the patch. The only comment not addressed is this one:> 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). I was subscribed to llvmdev in 'digest' mode, so the reply might not be correctly handled by mailers. Sorry about that. Zoltan -------------- next part -------------- A non-text attachment was scrubbed... Name: llvm-ovf.diff Type: text/x-diff Size: 37849 bytes Desc: not available URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20081209/705e4402/attachment.diff>
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. -Eli
On Tue, Dec 9, 2008 at 6:11 AM, Zoltan Varga <vargaz at gmail.com> wrote:> Hi, > > Here is the next iteration of the patch. The only comment not > addressed is this one: >Thanks! It's looking good.>> 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). >Okay. It would be tricky. Please put a "FIXME" in there indicating that it would be nice to have at some point. It's okay to submit this. -bw
Hi,
Attached is the final version of the patch, adding the requested
FIXME. If this is ok, can
somebody check it in ?
thanks
Zoltan
On Tue, Dec 9, 2008 at 9:58 PM, Bill Wendling <isanbard at gmail.com>
wrote:> On Tue, Dec 9, 2008 at 6:11 AM, Zoltan Varga <vargaz at gmail.com>
wrote:
>> Hi,
>>
>> Here is the next iteration of the patch. The only comment not
>> addressed is this one:
>>
> Thanks! It's looking good.
>
>>> 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).
>>
> Okay. It would be tricky. Please put a "FIXME" in there
indicating
> that it would be nice to have at some point. It's okay to submit this.
>
> -bw
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: llvm-ovf.diff
Type: text/x-diff
Size: 37966 bytes
Desc: not available
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20081209/cd928d07/attachment.diff>
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