[llvm-dev] multiprecision add/sub

[Bagel via llvm-dev]

My use case is multi-precision arithmetic which is key to efficient
implementation of public-key encryption.  Take the follow routine:

void addm(unsigned *x, unsigned *y, unsigned *z, unsigned n)
{ unsigned carryin;
  unsigned carryout = 0;
  unsigned i;

  for (i=0; i<n; i++)
  {  carryin = carryout;
     z[i] =  __builtin_addc(x[i], y[i], carryin, &carryout);
  }
}

If one looks at the clang IR generated, there are *four* instances of
"llvm.uadd.with.overflow" in the loop.  Somehow this has to be optimized to a
*single* machine instruction add-with-carry.

This isn't currently done (the code for x86-64 is horrible). I think
optimization would be much more simple if the four "llvm.uadd.with.overflow"
were replaced with a single "llvm.addc".

On 03/14/2017 08:45 AM, Nemanja Ivanovic wrote:
> Sorry for the delay in responding.
> The use case is basically for being able to emit instructions that correspond
> to these nodes. For example on Power, we use these instructions that set and
> use the Carry bit for comparisons without using compare instructions.
> One example where we would be able to make use of these would be in
> https://reviews.llvm.org/D28637.
> 
> On Tue, Mar 7, 2017 at 7:56 AM, Mehdi Amini <mehdi.amini at apple.com
> <mailto:mehdi.amini at apple.com>> wrote:
> 
> 
>>     On Feb 21, 2017, at 9:54 PM, Nemanja Ivanovic via llvm-dev
>>     <llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org>> wrote:
>>
>>     I believe that providing additional intrinsics that would directly
>>     produce the ISD::ADDC/ISD::SUBC nodes would provide the additional
>>     advantage of being able to directly produce these nodes for code that
>>     doesn't have anything to do with multiprecision addition/subtraction. I
>>     am not aware of any way currently available to produce IR that will
>>     generate these nodes directly.
> 
>     But what is the use case? What IR pattern it would replace? 
> 
>     — 
>     Mehdi
> 
> 
> 
> 
>>
>>     On Fri, Feb 17, 2017 at 8:52 PM, Bagel via llvm-dev
>>     <llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org>> wrote:
>>
>>         On 02/16/2017 12:08 PM, Stephen Canon wrote:
>>         >> On Feb 16, 2017, at 9:12 AM, Bagel <bagel99 at gmail.com <mailto:bagel99 at gmail.com>
>>         >> <mailto:bagel99 at gmail.com <mailto:bagel99 at gmail.com>>> wrote:
>>         >>
>>         >> I figured that the optimization of this would bedifficult (else it would
>>         >> have already been done :-))
>>         >
>>         > Don’t make this assumption. There’s lots of opportunities for optimization
>>         > scattered around. Some of them are left because they’re genuinely difficult,
>>         > but most either simply haven’t been noticed by anyone, or are known but simply
>>         > haven’t been done because no one has pushed for them (I’m fairly sure that this
>>         > particular optimization falls into that category—folks have known the codegen
>>         > wasn't great since these intrinsics were added, but no one has really
>>         > complained about it, so people have worked on higher-impact stuff).
>>
>>         But I am still curious as to whether the optimization is architecture
>>         independent or must be done again for each backend?
>>
>>         bagel
>>
>>         _______________________________________________
>>         LLVM Developers mailing list
>>         llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org>
>>         http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>>         <http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev>
>>
>>
>>     _______________________________________________
>>     LLVM Developers mailing list
>>     llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org>
>>     http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>>     <http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev>
> 
>