On Thursday, May 27, 2021 at 1:01:18 PM UTC+3, Terje Mathisen wrote:
> David Brown wrote:
> > On 27/05/2021 08:10, Ivan Godard wrote:
> >> On 5/26/2021 10:52 PM, Terje Mathisen wrote:
> >>>
> >>> I.e. Intel's add_carryx_u64() returns both the full adder result and
> >>> the outgoing carry.
> >>>
> >>> Terje
> >>>
> >>
> >> Which is regrettable when without restrict and inlining, and doubtful
> >> even then.
> >>
> >> A more modern approach is to make the two values into a struct and
> >> return that. A good modern compiler will tuple-ize that into two
> >> registers. Can't speak for gcc, gave up long ago, but LLVM does and
> >> needs neither restrict nor inline.
> >
> > Modern compilers don't need the function marked as "inline", nor do they
> > need the qualifier "restrict" added - if they can see the function
> > definition when it is used, they inline automatically where appropriate.
> > That means either using LTO, or having the function within the file you
> > are using it, or having it in a header marked as either "inline" or
> > "static" (or both) to avoid duplicate definitions when linking.
> >
> > Using a struct to give multiple values as a return is, of course, a
> > perfectly good alternative - one that many people (including me) prefer.
> > gcc will follow the same pattern as clang here about how to return the
> > struct, because it is required by the ABI (and IIRC both compilers have
> > switches to let you use non-standard methods if you prefer).
> >
> > While it's common in C to pass a pointer to where the results should go
> > in cases like this, struct returns are not new - look at the "div"
> > function in the C standard library for an example as old as C.
> >
> I should have noted that it really doesn't matter in the case of those
> intrinsics: Unless you go out of your way by declaring the additional
> return as a pointer to a non-local variable, most (all?) compilers who
> know about the intrinsic will in fact generate optimal code.
>

Until few months ago gcc generated very bad code for this intrinsic.
It seems, they fixed it between 10 and 11. Now they are on par with lllvm and MSVc, if not ahead.

Unfortunately, it only works on iAMD64. I know no easy way to achieve the same from C or C++ on aarch64 or Power or SPARC, despite all three featuring similar instructions

> I.e. 128-bit unsigned add
>
> u8 carry;
> carry = _addcarryx_u64(alo, blo, &sumlo);
> _addcarryx_u64(ahi, bhi, &sumhi);
>
> will compile into something like this (assuming RDX:RAX for a, RCX:RBX
> for b and the return back in RDX:RAX):
>
> add rax,rbx
> adc rdx,rcx
>
> I.e. optimal code needing just the minimum possible 2 cycles of latency.
>
> With the new ADCX/ADOX instructions you can even do two (long) chains of
> additions at the same time, but to use them you have to zero out the
> Overflow and Carry flags before you start:
>
> ; RSI -> first accumulator
> ; [RSI+RBX] -> second accumulator
> ; [RSI+RDI] -> first addend
> ; [RSI+RBP] -> second addend
> ; RCX = loop count
>
> xor rax,rax ; Clear C & O flags
> nextpair:
> jrcxz done
> mov rax,[rsi]
> mov rdx,[rsi+rbx]
> adcx rax,[rsi+rdi]
> adox rdx,[rsi+rbp]
> mov [rsi],rax
> mov [rsi+rbx],rdx
> lea rsi,[rsi+8]
> lea rcx,[rcx-1]
> jmp nextpair
> done:
>
> This is 4 loads and 2 stores per iteration, so possible to run in 2
> cycles on a wide enough cpu (with everything in $L1).
>
> Please note that this setup (ab)uses the flags pretty badly!
>
> ADCX will _only_ update Carry
> ADOX will _only_ update Overflow
> MOV & LEA does not update any flags
> JRCXZ neither updates nor test any flags, it is the only conditional
> branch with this distinction, but it has to be used as an inverted loop
> exit test.
> Terje
>
> --
> - <Terje.Mathisen at tmsw.no>
> "almost all programming can be viewed as an exercise in caching"

On Thursday, May 27, 2021 at 1:44:28 PM UTC+3, Thomas Koenig wrote:
> Terje Mathisen <terje.m...@tmsw.no> schrieb:
> > I.e. 128-bit unsigned add
> >
> > u8 carry;
> > carry = _addcarryx_u64(alo, blo, &sumlo);
> > _addcarryx_u64(ahi, bhi, &sumhi);
> >
> > will compile into something like this (assuming RDX:RAX for a, RCX:RBX
> > for b and the return back in RDX:RAX):
> >
> > add rax,rbx
> > adc rdx,rcx
> With gcc (and clang), this is not needed, there a __int128_t
> and a __uint128_t type.

Not needed in a very specific case of 128-bit. But useful for wider type.

> It is rather poorly supported, though;
> you cannot, for example, specify 128-bit integer constants in
> C directly.
>
> For Fortran, it is just another integer type (kind=16), which
> is fully uspported.

Thomas Koenig wrote:
> Terje Mathisen <terje.mathisen@tmsw.no> schrieb:
>
>> I.e. 128-bit unsigned add
>>
>> u8 carry;
>> carry = _addcarryx_u64(alo, blo, &sumlo);
>> _addcarryx_u64(ahi, bhi, &sumhi);
>>
>> will compile into something like this (assuming RDX:RAX for a, RCX:RBX
>> for b and the return back in RDX:RAX):
>>
>> add rax,rbx
>> adc rdx,rcx
>
> With gcc (and clang), this is not needed, there a __int128_t
> and a __uint128_t type. It is rather poorly supported, though;
> you cannot, for example, specify 128-bit integer constants in
> C directly.

But you can use it to implement intermediate-size integers, like 512-bit
RSA variables by accessing the hi/lo parts to chain them together?

I.e. use them to add two 64-bit values and get the carry alongside the sum?

u128 sum128 = (u128) a64 + (u128) b64;

This still, btw, does not provide a full adder since you also need the
ability to pass in two 64-bit inputs and the incoming carry.

>
> For Fortran, it is just another integer type (kind=16), which
> is fully uspported.
>
Nice. :-)

Terje

--
- <Terje.Mathisen at tmsw.no>
"almost all programming can be viewed as an exercise in caching"

Michael S wrote:
> On Thursday, May 27, 2021 at 1:44:28 PM UTC+3, Thomas Koenig wrote:
>> Terje Mathisen <terje.m...@tmsw.no> schrieb:
>>> I.e. 128-bit unsigned add
>>>
>>> u8 carry;
>>> carry = _addcarryx_u64(alo, blo, &sumlo);
>>> _addcarryx_u64(ahi, bhi, &sumhi);

Mea Culpa! I forgot the incoming carry argument to those instructions,
it should have been

u8 carry = 0;
carry = _addcarryx_u64(carry, alo, blo, &sumlo);
_addcarryx_u64(carry, ahi, bhi, &sumhi);

>>>
>>> will compile into something like this (assuming RDX:RAX for a, RCX:RBX
>>> for b and the return back in RDX:RAX):
>>>
>>> add rax,rbx
>>> adc rdx,rcx
>> With gcc (and clang), this is not needed, there a __int128_t
>> and a __uint128_t type.
>
> Not needed in a very specific case of 128-bit. But useful for wider type.

Yeah, absolutely right.

My example above would trivially extend to 256-bit ints like this, where
using the compiler support for u128 would be a poor second choice:

u8 carry = 0;
carry = _addcarryx_u64(carry, a0, b0, &sum0);
carry = _addcarryx_u64(carry, a1, b1, &sum1);
carry = _addcarryx_u64(carry, a2, b2, &sum2);
carry = _addcarryx_u64(carry, a3, b3, &sum3);

(Carry set on output could be used as an error indication unless
wraparound was intended, and this is probably the case for crypto.)

>
>> It is rather poorly supported, though;
>> you cannot, for example, specify 128-bit integer constants in
>> C directly.

So effectively you have to use pairs of 64-bit hex constants in orer to
keep it manageable.

Terje

--
- <Terje.Mathisen at tmsw.no>
"almost all programming can be viewed as an exercise in caching"

Ivan Godard wrote:
> On 5/26/2021 11:51 PM, Niklas Holsti wrote:
>>
>> Furthermore, just to be complete, the subtraction operator "-" may
>> have been overloaded so that the computation T'(A+B) - C produces a
>> different type, which would then be the type required for X.
>>
>> Conversely, the type of X can determine which of many overloadings of
>> "-" is chosen for this computation: one that produces a result of the
>> same type as X, while taking arguments of type T and the type of C.
>> Here Ada goes further than C++; AIUI, in C++ overloading is resolved
>> based only on the argument types.

That's Ada's top-down overload resolution.
In addition to the routine or operator arguments, which bottom-up
resolution considers, top-down also considers whether the routine
is a procedure or function, and if a function then the return type.

> Yeah, I did that. It mostly follows the coercion rules of Mary2, which
> in turn were derived from Algol68. The semantics differed in one way:
> Mary2 used first-found in a search of overloads in as-declared order,
> while Ada (and C++) search all overloads and complain of ambiguities.

Long ago when I was playing with hobby language design I thought this
was a nice idea so I added top-down overload resolution to the language.

Then I tried to build it. It is insanely complex.
Because of things like default argument values,
named associations that can change the arg order,
and I had variable (ellipsis) arg lists too,
the routine signatures are totally variable,
combined with multiple nested and package name spaces,
the search space potentially explodes exponentially.

Eventually removed it from the language and went
with traditional bottom-up overload resolution.

From what I later read back then, the successful Ada overload resolvers
did a bottom up pass first to prune the lists of possibilities.
Then a top down pass to resolve the leftovers and check for ambiguities.
That's still damn complicated, just less explode-y.

On Thursday, May 27, 2021 at 12:52:50 AM UTC-5, Terje Mathisen wrote:
> Ivan Godard wrote:
> > On 5/26/2021 10:04 AM, MitchAlsup wrote:
> >> On Wednesday, May 26, 2021 at 10:53:02 AM UTC-5, Stephen Fuld wrote:
> >>> On 5/21/2021 3:59 PM, MitchAlsup wrote:
> >>>> On Friday, May 21, 2021 at 5:00:17 PM UTC-5, Stephen Fuld wrote:
> >>>>> On 5/21/2021 12:40 PM, EricP wrote:
> >>>>>> Stephen Fuld wrote:
> >>>>>>> On 5/20/2021 9:34 AM, MitchAlsup wrote:
> >>>>>>>> On Thursday, May 20, 2021 at 10:08:32 AM UTC-5, Stephen Fuld wrote:
> >>>>>>>>> On 5/19/2021 11:40 PM, Niklas Holsti wrote:
> >>>>>>>>>> On 2021-05-20 3:40, Stephen Fuld wrote:
> >>>>>>>>>>> On 5/19/2021 8:47 AM, EricP wrote:
> >>>>>>>>
> >>>>>>>>> Fair enough. This sort of gets back to the question of whether
> >>>>>>>>> to add a
> >>>>>>>>> feature like this as an attribute of the variable (e.g. range)
> >>>>>>>>> or of
> >>>>>>>>> the
> >>>>>>>>> operation (e.g. bignum). I think there are arguments for each.
> >>>>>>>>>
> >>>>>>>>> BTW, I am unsure of what the requirement is here. Suppose you
> >>>>>>>>> have a
> >>>>>>>>> variable with a range of 10-90. Do you want saturation at 90?
> >>>>>>>>> That is
> >>>>>>>> <
> >>>>>>>> If the value to be written is outside of the range [10..90] you
> >>>>>>>> raise an
> >>>>>>>> exception. The raised exception decides what to do.
> >>>>>>>
> >>>>>>> Certainly true for the non-saturating case, and is what Ada does. My
> >>>>>>> question is if you define saturating variables, what to do if you
> >>>>>>> somehow define the variable with a range *and* saturating.
> >>>>>>
> >>>>>> Any variables that are smaller than the machine register size are
> >>>>>> promoted to that size by either sign or zero extension.
> >>>>>>
> >>>>>> Expressions are executed using signed or unsigned checked or
> >>>>>> saturating
> >>>>>> operations at that machine size. This detects intermediate signed or
> >>>>>> unsigned overflows of the machine size results.
> >>>>>>
> >>>>>> I have instructions for trap on unsigned carry or signed overflow.
> >>>>>> I have an ADGO Add Generate Overflow and ADGC Add Generate Carry
> >>>>>> to set a 1 in the output register for overflow or carry.
> >>>>>> Then a LIC Load Immediate Conditional loads saturation limit values.
> >>>>>> One could have arithmetic instructions that saturate.
> >>>>>>
> >>>>>> The result is copied back to the variable. If there are
> >>>>>> constraints on
> >>>>>> the variable different from the limits on the physical register
> >>>>>> then those are range checked and either saturated or trapped.
> >>>>>> A CMPGT and CMPLT with a LIC loads upper or lower saturation value..
> >>>>>>
> >>>>>> Note that setting limits on variable to be in the range 10..90 does
> >>>>>> not mean that expression intermediate results are within that range.
> >>>>>> It means an expression EITHER produces the arithmetically correct
> >>>>>> result
> >>>>>> in that range, or it saturates or traps.
> >>>> <
> >>>>> That is certainly one way to do it. All the different ways have
> >>>>> drawbacks. Mitch pointed out some of the ones for you choice in his
> >>>>> followup.
> >>>>>
> >>>>> I don't know enough to have strong feelings as to the best choice. As
> >>>>> Thomas Koening said earlier in this thread, it takes a lot of thought.
> >>>> <
> >>>> This brings to mind that the whole concept of arithmetic exceptions is
> >>>> fundamentally flawed.
> >>>> <
> >>>> It is not the arithmetic that should be checked for out-of-range values
> >>>> it is the depositing of values into containers that should be checked.
> >>> While I generally agree, there is apparently some use for checking
> >>> intermediate results in calculations. Then the question becomes what is
> >>> the best way, language syntax wise (i.e. not a question of ISA, as there
> >>> are several ways to do that depending upon ISA) to indicate that.
> >>>
> >>> Note that I am going to consider this in terms a generalized range
> >>> restriction à la Ada Range attributes, as resolving this for that case
> >>> automatically includes the cases of overflow of byte sized variables in
> >>> 64 bit registers, etc.
> >>>
> >>> Perhaps the easiest way to indicate this is the break the calculation
> >>> into individual steps, storing the intermediate results, thus triggering
> >>> the range checks.
> >>>
> >>> Lets use a simple example.
> >>>
> >>> X = A + B - C where A+B might be out of range, but after C is subtracted
> >>> X is within range.
> >>>
> >>> You could code this as
> >>>
> >>> X = A + B
> >>> X = X - C
> >> <
> >> In general, I am a great fan of shorter assignment statements (as above)
> >> and while there are more assignments, there may be fewer instructions
> >> created, and the programmer himself can see the common sub-expressions..
> >>>
> >>> Of course, the compiler would have to recognize that X had a range and
> >>> actually do the check, even if it doesn't actually do the first store..
> >>>
> >>> Another alternative is the use a "function" to indicate that the check
> >>> should be done. This is a generalization of the cast mechanism in C.
> >>>
> >>> i.e. something like
> >>>
> >>> X = Rangechk (A + B) - C ; Rangechk tests the bounds of X
> >>>
> >>>
> >>> Another alternative is back to the discussion of whether the checking of
> >>> intermediate values should be a property of the variable (like Range
> >>> itself) or the calculation. If it is a property of the variable you
> >>> could have syntax to indicate that, i.e. add RangeIVC (for intermediate
> >>> value checked), which would indicate to check the intermediate values
> >>> for any expression that assigns a value to the variable with that
> >>> attribute.
> >>>
> >>> I don't have a strong feeling about what is the best solution, and there
> >>> may be better ones than what I have suggested.
> >> <
> >> May I suggest a whip instead of a language addition !! That is the code
> >> review process should not allow x = a + b - c; into production code if
> >> there is any reason to believe it can behave maliciously !! or unbox
> >> the nasal demons of destruction !
> >> <
> >> There are codes which depend on the HW not caring that something
> >> has lost precision on one end (integral) or the other (FP). For example
> >> Knuth's TwoSum::
> >> <
> >> {double, double} TwoSum( double a, double b )
> >> { // Knuth
> >> x = a + b ;
> >> q = x - a ;
> >> r = x - q ;
> >> s = b - q ;
> >> t = a - r ;
> >> y = s + t ;
> >> return { x, y };
> >> }
> >> <
> >> This subroutine performs addition and puts all of the bits of a+b that
> >> fit into x, and all of the bits that do not fit into y, branchlessly. The
> >> numerical analyst went to great trouble to align all the arithmetic
> >> so that precisely this would be the result.
> >> <
> >> An "optimizing" might come to the conclusion that q == b and ruin
> >> the whole sequence !!
> >> <
> >> On the other hand I designed My 66000 so that one can write this as::
> >> <
> >> {double, double} TwoSum( double a, double b )
> >> {
> >> return {double, double} = a + b;
> >> }
> >
> >
> > Does your actual compiler currently accept this as source? If not, what
> > do you actually have to write to get the requisite machine code from
> > your implemented compiler?
> The traditional C way, as exemplified by lots of compiler intrinsics, is
> to use a pointer to any additional return values:
>
> double AugmentedAddition(double a, double b, double *lopart)
> {
> // Knuth
> x = a + b ;
> q = x - a ;
> r = x - q ;
> s = b - q ;
> t = a - r ;
> *lopart = s + t ;
> return x;
> }
<
Unnecessary:: x and y have the properties::
x contains all of the bits (properly rounded) that made it into a+b
y contains all of the bits that did not make it into x.
<
In the case a and b are disjoint (exponents differ by more than 53)
x gets the larger magnitude, and y gets the smaller magnitude.
That is:: there are no "lopart" left.
>
> I.e. Intel's add_carryx_u64() returns both the full adder result and the
> outgoing carry.
> Terje
>
> --
> - <Terje.Mathisen at tmsw.no>
> "almost all programming can be viewed as an exercise in caching"

Terje Mathisen <terje.mathisen@tmsw.no> schrieb:
> Thomas Koenig wrote:
>> Terje Mathisen <terje.mathisen@tmsw.no> schrieb:
>>
>>> I.e. 128-bit unsigned add
>>>
>>> u8 carry;
>>> carry = _addcarryx_u64(alo, blo, &sumlo);
>>> _addcarryx_u64(ahi, bhi, &sumhi);
>>>
>>> will compile into something like this (assuming RDX:RAX for a, RCX:RBX
>>> for b and the return back in RDX:RAX):
>>>
>>> add rax,rbx
>>> adc rdx,rcx
>>
>> With gcc (and clang), this is not needed, there a __int128_t
>> and a __uint128_t type. It is rather poorly supported, though;
>> you cannot, for example, specify 128-bit integer constants in
>> C directly.
>
> But you can use it to implement intermediate-size integers, like 512-bit
> RSA variables by accessing the hi/lo parts to chain them together?

Sure.

> I.e. use them to add two 64-bit values and get the carry alongside the sum?

You could use __builtin_add_overflow for that, instead:

int main()
{ int n1, n2;
__uint128_t a, b, res;
scanf ("%d %d", &n1, &n2);
a = ((__uint128_t) 1) << n1;
b = ((__uint128_t) 1) << n2;
if (__builtin_add_overflow (a, b, &res))
printf ("Overflow!\n");
else
printf ("No overflow!\n");
return 0;
}

and then chain this further. However, if your hardware does
not support 128-bit integers natively, you are probably better
off using 64-bit words and use the carry that way. There
is no particular advantage to using 128-bit types, and
at least gcc has some issues with register allocation for
those types.

The best way would probably be to use 64-bit unsigned ints,
and then to do

int c_old; c_new;
c_old = 0;
for (i=0; i<n; i++) {
c_new = __builtin_add_overflow (a[i], b[i], res+i);
res[i] += c_old;
c_old = c_new;
}

For doing a high /low multiplication, you can indeed use the 128-bit
types:

__uint128_t tmp;
uint64_t high, low;
tmp = (__uint128_t) a * (__uint128_t) b;
low = tmp;
high = tmp >> 64;

Anton Ertl <anton@mips.complang.tuwien.ac.at> schrieb:

> Gcc has had -freg-struct-return for at least 30 years, but it's
> incompatible with the way PCC returned structs, so you cannot link
> code that uses reg-struct-return with code that uses pcc-struct-return
> if there is such a return between code using different conventions.

The Itanium ABI fixed that.

Rather than quote chapter and verse, here is a short example:

$ cat ret.c
typedef struct foo
{ int a;
int b;
} foo;

foo bar()
{ return ((foo){.a = 42, .b=21});
} $ gcc -O3 -S ret.c
$ cat ret.s
.file "ret.c"
.text
.p2align 4
.globl bar
.type bar, @function
bar:
..LFB0:
.cfi_startproc
movabsq $90194313258, %rax
ret
.cfi_endproc
..LFE0:
.size bar, .-bar
.ident "GCC: (GNU) 12.0.0 20210525 (experimental) [master revision e87559d202d:f4e6da6e8ac:36ec54aac7da134441c83248e14825381b8d6f17]"
.section .note.GNU-stack,"",@progbits

> Then I tried to build it. It is insanely complex.
> Because of things like default argument values,
> named associations that can change the arg order,
> and I had variable (ellipsis) arg lists too,
> the routine signatures are totally variable,
> combined with multiple nested and package name spaces,
> the search space potentially explodes exponentially.

Indeed, it can get terribly complex. I think in terms of design, this
complexity is a problem not just for the implementation but for the
human reader as well.

So you generally want to tweak your language design in order to reduce
this complexity.

One way to do that, for example, is it to make it so overloading
resolution does not affect types, it only chooses which implementation
to call (or signal an error if there's no candidate that matches).
This is what was happens for example with Haskell's single-parameter
type classes.

Stefan

On Thursday, May 27, 2021 at 2:39:45 PM UTC-5, Stefan Monnier wrote:
> > Then I tried to build it. It is insanely complex.
> > Because of things like default argument values,
> > named associations that can change the arg order,
> > and I had variable (ellipsis) arg lists too,
> > the routine signatures are totally variable,
> > combined with multiple nested and package name spaces,
> > the search space potentially explodes exponentially.
> Indeed, it can get terribly complex. I think in terms of design, this
> complexity is a problem not just for the implementation but for the
> human reader as well.
>
> So you generally want to tweak your language design in order to reduce
> this complexity.
>
> One way to do that, for example, is it to make it so overloading
> resolution does not affect types, it only chooses which implementation
> to call (or signal an error if there's no candidate that matches).
<
There should be another error if more than on implementations match.
<
> This is what was happens for example with Haskell's single-parameter
> type classes.
>
>
> Stefan

MitchAlsup wrote:
> On Thursday, May 27, 2021 at 12:52:50 AM UTC-5, Terje Mathisen wrote:
>> Ivan Godard wrote:
>>> On 5/26/2021 10:04 AM, MitchAlsup wrote:
>>>> On Wednesday, May 26, 2021 at 10:53:02 AM UTC-5, Stephen Fuld wrote:
>>>>> On 5/21/2021 3:59 PM, MitchAlsup wrote:
>>>>>> On Friday, May 21, 2021 at 5:00:17 PM UTC-5, Stephen Fuld wrote:
>>>>>>> On 5/21/2021 12:40 PM, EricP wrote:
>>>>>>>> Stephen Fuld wrote:
>>>>>>>>> On 5/20/2021 9:34 AM, MitchAlsup wrote:
>>>>>>>>>> On Thursday, May 20, 2021 at 10:08:32 AM UTC-5, Stephen Fuld wrote:
>>>>>>>>>>> On 5/19/2021 11:40 PM, Niklas Holsti wrote:
>>>>>>>>>>>> On 2021-05-20 3:40, Stephen Fuld wrote:
>>>>>>>>>>>>> On 5/19/2021 8:47 AM, EricP wrote:
>>>>>>>>>>
>>>>>>>>>>> Fair enough. This sort of gets back to the question of whether
>>>>>>>>>>> to add a
>>>>>>>>>>> feature like this as an attribute of the variable (e.g. range)
>>>>>>>>>>> or of
>>>>>>>>>>> the
>>>>>>>>>>> operation (e.g. bignum). I think there are arguments for each.
>>>>>>>>>>>
>>>>>>>>>>> BTW, I am unsure of what the requirement is here. Suppose you
>>>>>>>>>>> have a
>>>>>>>>>>> variable with a range of 10-90. Do you want saturation at 90?
>>>>>>>>>>> That is
>>>>>>>>>> <
>>>>>>>>>> If the value to be written is outside of the range [10..90] you
>>>>>>>>>> raise an
>>>>>>>>>> exception. The raised exception decides what to do.
>>>>>>>>>
>>>>>>>>> Certainly true for the non-saturating case, and is what Ada does. My
>>>>>>>>> question is if you define saturating variables, what to do if you
>>>>>>>>> somehow define the variable with a range *and* saturating.
>>>>>>>>
>>>>>>>> Any variables that are smaller than the machine register size are
>>>>>>>> promoted to that size by either sign or zero extension.
>>>>>>>>
>>>>>>>> Expressions are executed using signed or unsigned checked or
>>>>>>>> saturating
>>>>>>>> operations at that machine size. This detects intermediate signed or
>>>>>>>> unsigned overflows of the machine size results.
>>>>>>>>
>>>>>>>> I have instructions for trap on unsigned carry or signed overflow.
>>>>>>>> I have an ADGO Add Generate Overflow and ADGC Add Generate Carry
>>>>>>>> to set a 1 in the output register for overflow or carry.
>>>>>>>> Then a LIC Load Immediate Conditional loads saturation limit values.
>>>>>>>> One could have arithmetic instructions that saturate.
>>>>>>>>
>>>>>>>> The result is copied back to the variable. If there are
>>>>>>>> constraints on
>>>>>>>> the variable different from the limits on the physical register
>>>>>>>> then those are range checked and either saturated or trapped.
>>>>>>>> A CMPGT and CMPLT with a LIC loads upper or lower saturation value.
>>>>>>>>
>>>>>>>> Note that setting limits on variable to be in the range 10..90 does
>>>>>>>> not mean that expression intermediate results are within that range.
>>>>>>>> It means an expression EITHER produces the arithmetically correct
>>>>>>>> result
>>>>>>>> in that range, or it saturates or traps.
>>>>>> <
>>>>>>> That is certainly one way to do it. All the different ways have
>>>>>>> drawbacks. Mitch pointed out some of the ones for you choice in his
>>>>>>> followup.
>>>>>>>
>>>>>>> I don't know enough to have strong feelings as to the best choice. As
>>>>>>> Thomas Koening said earlier in this thread, it takes a lot of thought.
>>>>>> <
>>>>>> This brings to mind that the whole concept of arithmetic exceptions is
>>>>>> fundamentally flawed.
>>>>>> <
>>>>>> It is not the arithmetic that should be checked for out-of-range values
>>>>>> it is the depositing of values into containers that should be checked.
>>>>> While I generally agree, there is apparently some use for checking
>>>>> intermediate results in calculations. Then the question becomes what is
>>>>> the best way, language syntax wise (i.e. not a question of ISA, as there
>>>>> are several ways to do that depending upon ISA) to indicate that.
>>>>>
>>>>> Note that I am going to consider this in terms a generalized range
>>>>> restriction à la Ada Range attributes, as resolving this for that case
>>>>> automatically includes the cases of overflow of byte sized variables in
>>>>> 64 bit registers, etc.
>>>>>
>>>>> Perhaps the easiest way to indicate this is the break the calculation
>>>>> into individual steps, storing the intermediate results, thus triggering
>>>>> the range checks.
>>>>>
>>>>> Lets use a simple example.
>>>>>
>>>>> X = A + B - C where A+B might be out of range, but after C is subtracted
>>>>> X is within range.
>>>>>
>>>>> You could code this as
>>>>>
>>>>> X = A + B
>>>>> X = X - C
>>>> <
>>>> In general, I am a great fan of shorter assignment statements (as above)
>>>> and while there are more assignments, there may be fewer instructions
>>>> created, and the programmer himself can see the common sub-expressions.
>>>>>
>>>>> Of course, the compiler would have to recognize that X had a range and
>>>>> actually do the check, even if it doesn't actually do the first store.
>>>>>
>>>>> Another alternative is the use a "function" to indicate that the check
>>>>> should be done. This is a generalization of the cast mechanism in C.
>>>>>
>>>>> i.e. something like
>>>>>
>>>>> X = Rangechk (A + B) - C ; Rangechk tests the bounds of X
>>>>>
>>>>>
>>>>> Another alternative is back to the discussion of whether the checking of
>>>>> intermediate values should be a property of the variable (like Range
>>>>> itself) or the calculation. If it is a property of the variable you
>>>>> could have syntax to indicate that, i.e. add RangeIVC (for intermediate
>>>>> value checked), which would indicate to check the intermediate values
>>>>> for any expression that assigns a value to the variable with that
>>>>> attribute.
>>>>>
>>>>> I don't have a strong feeling about what is the best solution, and there
>>>>> may be better ones than what I have suggested.
>>>> <
>>>> May I suggest a whip instead of a language addition !! That is the code
>>>> review process should not allow x = a + b - c; into production code if
>>>> there is any reason to believe it can behave maliciously !! or unbox
>>>> the nasal demons of destruction !
>>>> <
>>>> There are codes which depend on the HW not caring that something
>>>> has lost precision on one end (integral) or the other (FP). For example
>>>> Knuth's TwoSum::
>>>> <
>>>> {double, double} TwoSum( double a, double b )
>>>> { // Knuth
>>>> x = a + b ;
>>>> q = x - a ;
>>>> r = x - q ;
>>>> s = b - q ;
>>>> t = a - r ;
>>>> y = s + t ;
>>>> return { x, y };
>>>> }
>>>> <
>>>> This subroutine performs addition and puts all of the bits of a+b that
>>>> fit into x, and all of the bits that do not fit into y, branchlessly. The
>>>> numerical analyst went to great trouble to align all the arithmetic
>>>> so that precisely this would be the result.
>>>> <
>>>> An "optimizing" might come to the conclusion that q == b and ruin
>>>> the whole sequence !!
>>>> <
>>>> On the other hand I designed My 66000 so that one can write this as::
>>>> <
>>>> {double, double} TwoSum( double a, double b )
>>>> {
>>>> return {double, double} = a + b;
>>>> }
>>>
>>>
>>> Does your actual compiler currently accept this as source? If not, what
>>> do you actually have to write to get the requisite machine code from
>>> your implemented compiler?
>> The traditional C way, as exemplified by lots of compiler intrinsics, is
>> to use a pointer to any additional return values:
>>
>> double AugmentedAddition(double a, double b, double *lopart)
>> {
>> // Knuth
>> x = a + b ;
>> q = x - a ;
>> r = x - q ;
>> s = b - q ;
>> t = a - r ;
>> *lopart = s + t ;
>> return x;
>> }
> <
> Unnecessary:: x and y have the properties::
> x contains all of the bits (properly rounded) that made it into a+b
> y contains all of the bits that did not make it into x.
> <
> In the case a and b are disjoint (exponents differ by more than 53)
> x gets the larger magnitude, and y gets the smaller magnitude.
> That is:: there are no "lopart" left.

Thomas Koenig wrote:
> Terje Mathisen <terje.mathisen@tmsw.no> schrieb:
>> Thomas Koenig wrote:
>>> Terje Mathisen <terje.mathisen@tmsw.no> schrieb:
>>>
>>>> I.e. 128-bit unsigned add
>>>>
>>>> u8 carry;
>>>> carry = _addcarryx_u64(alo, blo, &sumlo);
>>>> _addcarryx_u64(ahi, bhi, &sumhi);
>>>>
>>>> will compile into something like this (assuming RDX:RAX for a, RCX:RBX
>>>> for b and the return back in RDX:RAX):
>>>>
>>>> add rax,rbx
>>>> adc rdx,rcx
>>>
>>> With gcc (and clang), this is not needed, there a __int128_t
>>> and a __uint128_t type. It is rather poorly supported, though;
>>> you cannot, for example, specify 128-bit integer constants in
>>> C directly.
>>
>> But you can use it to implement intermediate-size integers, like 512-bit
>> RSA variables by accessing the hi/lo parts to chain them together?
>
> Sure.
>
>> I.e. use them to add two 64-bit values and get the carry alongside the sum?
>
> You could use __builtin_add_overflow for that, instead:
>
> int main()
> {
> int n1, n2;
> __uint128_t a, b, res;
> scanf ("%d %d", &n1, &n2);
> a = ((__uint128_t) 1) << n1;
> b = ((__uint128_t) 1) << n2;
> if (__builtin_add_overflow (a, b, &res))
> printf ("Overflow!\n");
> else
> printf ("No overflow!\n");
> return 0;
> }
>
> and then chain this further. However, if your hardware does
> not support 128-bit integers natively, you are probably better
> off using 64-bit words and use the carry that way. There
> is no particular advantage to using 128-bit types, and
> at least gcc has some issues with register allocation for
> those types.
>
> The best way would probably be to use 64-bit unsigned ints,
> and then to do
>
> int c_old; c_new;
> c_old = 0;
> for (i=0; i<n; i++) {
> c_new = __builtin_add_overflow (a[i], b[i], res+i);
> res[i] += c_old;

That does not work:

You have to also handle the case where res[i] += c_old causes a new carry!

I.e. you need

c0 = __builtin_add_overflow (a[i], b[i], &temp);
c1 = __builtin_add_overflow (temp, c_old, res+i);
c_old = c0 | c1;

> For doing a high /low multiplication, you can indeed use the 128-bit
> types:
>
> __uint128_t tmp;
> uint64_t high, low;
> tmp = (__uint128_t) a * (__uint128_t) b;
> low = tmp;
> high = tmp >> 64;
>
Hopefully the compiler will recognize this and make the two last lines NOPs.

Terje

--
- <Terje.Mathisen at tmsw.no>
"almost all programming can be viewed as an exercise in caching"

Terje Mathisen <terje.mathisen@tmsw.no> schrieb:
> Thomas Koenig wrote:
>> Terje Mathisen <terje.mathisen@tmsw.no> schrieb:
>>> Thomas Koenig wrote:
>>>> Terje Mathisen <terje.mathisen@tmsw.no> schrieb:
>>>>
>>>>> I.e. 128-bit unsigned add
>>>>>
>>>>> u8 carry;
>>>>> carry = _addcarryx_u64(alo, blo, &sumlo);
>>>>> _addcarryx_u64(ahi, bhi, &sumhi);
>>>>>
>>>>> will compile into something like this (assuming RDX:RAX for a, RCX:RBX
>>>>> for b and the return back in RDX:RAX):
>>>>>
>>>>> add rax,rbx
>>>>> adc rdx,rcx
>>>>
>>>> With gcc (and clang), this is not needed, there a __int128_t
>>>> and a __uint128_t type. It is rather poorly supported, though;
>>>> you cannot, for example, specify 128-bit integer constants in
>>>> C directly.
>>>
>>> But you can use it to implement intermediate-size integers, like 512-bit
>>> RSA variables by accessing the hi/lo parts to chain them together?
>>
>> Sure.
>>
>>> I.e. use them to add two 64-bit values and get the carry alongside the sum?
>>
>> You could use __builtin_add_overflow for that, instead:
>>
>> int main()
>> {
>> int n1, n2;
>> __uint128_t a, b, res;
>> scanf ("%d %d", &n1, &n2);
>> a = ((__uint128_t) 1) << n1;
>> b = ((__uint128_t) 1) << n2;
>> if (__builtin_add_overflow (a, b, &res))
>> printf ("Overflow!\n");
>> else
>> printf ("No overflow!\n");
>> return 0;
>> }
>>
>> and then chain this further. However, if your hardware does
>> not support 128-bit integers natively, you are probably better
>> off using 64-bit words and use the carry that way. There
>> is no particular advantage to using 128-bit types, and
>> at least gcc has some issues with register allocation for
>> those types.
>>
>> The best way would probably be to use 64-bit unsigned ints,
>> and then to do
>>
>> int c_old; c_new;
>> c_old = 0;
>> for (i=0; i<n; i++) {
>> c_new = __builtin_add_overflow (a[i], b[i], res+i);
>> res[i] += c_old;
>
> That does not work:
>
> You have to also handle the case where res[i] += c_old causes a new carry!

How?

(Assuming 8-bit to save on some typing)

If a[i] and b[i] are both 0xff, the maximum sum is 0x1fe. Then,
c_new is 1, res is 0xfe, and adding c_old, which has a maximum of 1,
can go to 0xff as a maximum.

Or am I missing something?

Thomas Koenig <tkoenig@netcologne.de> schrieb:
> Terje Mathisen <terje.mathisen@tmsw.no> schrieb:
>> Thomas Koenig wrote:
>>> Terje Mathisen <terje.mathisen@tmsw.no> schrieb:
>>>> Thomas Koenig wrote:
>>>>> Terje Mathisen <terje.mathisen@tmsw.no> schrieb:
>>>>>
>>>>>> I.e. 128-bit unsigned add
>>>>>>
>>>>>> u8 carry;
>>>>>> carry = _addcarryx_u64(alo, blo, &sumlo);
>>>>>> _addcarryx_u64(ahi, bhi, &sumhi);
>>>>>>
>>>>>> will compile into something like this (assuming RDX:RAX for a, RCX:RBX
>>>>>> for b and the return back in RDX:RAX):
>>>>>>
>>>>>> add rax,rbx
>>>>>> adc rdx,rcx
>>>>>
>>>>> With gcc (and clang), this is not needed, there a __int128_t
>>>>> and a __uint128_t type. It is rather poorly supported, though;
>>>>> you cannot, for example, specify 128-bit integer constants in
>>>>> C directly.
>>>>
>>>> But you can use it to implement intermediate-size integers, like 512-bit
>>>> RSA variables by accessing the hi/lo parts to chain them together?
>>>
>>> Sure.
>>>
>>>> I.e. use them to add two 64-bit values and get the carry alongside the sum?
>>>
>>> You could use __builtin_add_overflow for that, instead:
>>>
>>> int main()
>>> {
>>> int n1, n2;
>>> __uint128_t a, b, res;
>>> scanf ("%d %d", &n1, &n2);
>>> a = ((__uint128_t) 1) << n1;
>>> b = ((__uint128_t) 1) << n2;
>>> if (__builtin_add_overflow (a, b, &res))
>>> printf ("Overflow!\n");
>>> else
>>> printf ("No overflow!\n");
>>> return 0;
>>> }
>>>
>>> and then chain this further. However, if your hardware does
>>> not support 128-bit integers natively, you are probably better
>>> off using 64-bit words and use the carry that way. There
>>> is no particular advantage to using 128-bit types, and
>>> at least gcc has some issues with register allocation for
>>> those types.
>>>
>>> The best way would probably be to use 64-bit unsigned ints,
>>> and then to do
>>>
>>> int c_old; c_new;
>>> c_old = 0;
>>> for (i=0; i<n; i++) {
>>> c_new = __builtin_add_overflow (a[i], b[i], res+i);
>>> res[i] += c_old;
>>
>> That does not work:
>>
>> You have to also handle the case where res[i] += c_old causes a new carry!
>
> How?
>
> (Assuming 8-bit to save on some typing)
>
> If a[i] and b[i] are both 0xff, the maximum sum is 0x1fe. Then,
> c_new is 1, res is 0xfe, and adding c_old, which has a maximum of 1,
> can go to 0xff as a maximum.
>
> Or am I missing something?

Never mind, I found my error myself :-)

Thomas Koenig wrote:
> Terje Mathisen <terje.mathisen@tmsw.no> schrieb:
>> Thomas Koenig wrote:
>>> Terje Mathisen <terje.mathisen@tmsw.no> schrieb:
>>>> Thomas Koenig wrote:
>>>>> Terje Mathisen <terje.mathisen@tmsw.no> schrieb:
>>>>>
>>>>>> I.e. 128-bit unsigned add
>>>>>>
>>>>>> u8 carry;
>>>>>> carry = _addcarryx_u64(alo, blo, &sumlo);
>>>>>> _addcarryx_u64(ahi, bhi, &sumhi);
>>>>>>
>>>>>> will compile into something like this (assuming RDX:RAX for a, RCX:RBX
>>>>>> for b and the return back in RDX:RAX):
>>>>>>
>>>>>> add rax,rbx
>>>>>> adc rdx,rcx
>>>>>
>>>>> With gcc (and clang), this is not needed, there a __int128_t
>>>>> and a __uint128_t type. It is rather poorly supported, though;
>>>>> you cannot, for example, specify 128-bit integer constants in
>>>>> C directly.
>>>>
>>>> But you can use it to implement intermediate-size integers, like 512-bit
>>>> RSA variables by accessing the hi/lo parts to chain them together?
>>>
>>> Sure.
>>>
>>>> I.e. use them to add two 64-bit values and get the carry alongside the sum?
>>>
>>> You could use __builtin_add_overflow for that, instead:
>>>
>>> int main()
>>> {
>>> int n1, n2;
>>> __uint128_t a, b, res;
>>> scanf ("%d %d", &n1, &n2);
>>> a = ((__uint128_t) 1) << n1;
>>> b = ((__uint128_t) 1) << n2;
>>> if (__builtin_add_overflow (a, b, &res))
>>> printf ("Overflow!\n");
>>> else
>>> printf ("No overflow!\n");
>>> return 0;
>>> }
>>>
>>> and then chain this further. However, if your hardware does
>>> not support 128-bit integers natively, you are probably better
>>> off using 64-bit words and use the carry that way. There
>>> is no particular advantage to using 128-bit types, and
>>> at least gcc has some issues with register allocation for
>>> those types.
>>>
>>> The best way would probably be to use 64-bit unsigned ints,
>>> and then to do
>>>
>>> int c_old; c_new;
>>> c_old = 0;
>>> for (i=0; i<n; i++) {
>>> c_new = __builtin_add_overflow (a[i], b[i], res+i);
>>> res[i] += c_old;
>>
>> That does not work:
>>
>> You have to also handle the case where res[i] += c_old causes a new carry!
>
> How?
>
> (Assuming 8-bit to save on some typing)
>
> If a[i] and b[i] are both 0xff, the maximum sum is 0x1fe. Then,
> c_new is 1, res is 0xfe, and adding c_old, which has a maximum of 1,
> can go to 0xff as a maximum.
>
> Or am I missing something?
>
Yes:

Assume a[i] = 0x80, b[i] = 0x7f, and res[i] becomes 0xff. Adding c_old
(== 1) increments this to 0x100, so c_new must be set.

I.e. there really isn't a good way to do full 3-in 2-out adders without
having an actual full adder available. :-(

I see you already figured this out, but I'm still posting to illustrate
that it is hard to do long chain carry propagation without having the
moral equivalent of ADC.

Itanium tried to avoid it by having both ADD and ADD1, which differs
only in the setting of the incoming carry bit to the adder, but requires
you to execute both of them and select the correct result based on the
incoming carry, using eitehr predicates or a pick() operation.

This is effectively the same as a fast HW adder where you duplicate some
effort in order to get the final result fast enough to not impact your
cycle time. Splitting a 64-bit add into 3 32-bit adds gives you 50%
overhead, splitting each of these into 3 16-bit adds increase the
overhead to 125%.

Terje

--
- <Terje.Mathisen at tmsw.no>
"almost all programming can be viewed as an exercise in caching"

Thomas Koenig <tkoenig@netcologne.de> writes:
>Terje Mathisen <terje.mathisen@tmsw.no> schrieb:
>> Thomas Koenig wrote:
>>> int c_old; c_new;
>>> c_old = 0;
>>> for (i=0; i<n; i++) {
>>> c_new = __builtin_add_overflow (a[i], b[i], res+i);
>>> res[i] += c_old;
>>
>> That does not work:
>>
>> You have to also handle the case where res[i] += c_old causes a new carry!
>
>How?
>
>(Assuming 8-bit to save on some typing)
>
>If a[i] and b[i] are both 0xff, the maximum sum is 0x1fe. Then,
>c_new is 1, res is 0xfe, and adding c_old, which has a maximum of 1,
>can go to 0xff as a maximum.
>
>Or am I missing something?

You found it yourself, but just so that others don't have to search,
the problem is when a[i]+b[i] is 0xff, and c_old is 1. Then c_new is
0, but should be 1.

- anton
--
'Anyone trying for "industrial quality" ISA should avoid undefined behavior.'
Mitch Alsup, <c17fcd89-f024-40e7-a594-88a85ac10d20o@googlegroups.com>

Terje Mathisen <terje.mathisen@tmsw.no> schrieb:

> I see you already figured this out, but I'm still posting to illustrate
> that it is hard to do long chain carry propagation without having the
> moral equivalent of ADC.

I just browsed around a bit, and I found that, on x86 at least, you
can use _addcarryx_u64.

clang gets this right: https://gcc.godbolt.org/z/b9dTn8aWj
whereas gcc currently does not, as you can see in
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=79173 .

Thomas Koenig <tkoenig@netcologne.de> writes:
>Anton Ertl <anton@mips.complang.tuwien.ac.at> schrieb:
>
>> Gcc has had -freg-struct-return for at least 30 years, but it's
>> incompatible with the way PCC returned structs, so you cannot link
>> code that uses reg-struct-return with code that uses pcc-struct-return
>> if there is such a return between code using different conventions.
>
>The Itanium ABI fixed that.
>
>Rather than quote chapter and verse, here is a short example:
>
>$ cat ret.c
>typedef struct foo
>{
> int a;
> int b;
>} foo;
>
>foo bar()
>{
> return ((foo){.a = 42, .b=21});
>}

produces
....
> movabsq $90194313258, %rax
> ret

Does not look like IA-64 code to me. But I guess that like IA-64, AMD64
profitted from not having had a PCC port. It's interesting that the
struct is returned in a single register and has to be picked apart by
the caller.

For comparison, here's the same code for IA-32:

00000000 <bar>:
0: 8b 44 24 04 mov 0x4(%esp),%eax
4: c7 00 2a 00 00 00 movl $0x2a,(%eax)
a: c7 40 04 15 00 00 00 movl $0x15,0x4(%eax)
11: c2 04 00 ret $0x4

Aarch64:
0 000000000000000 <bar>:
0: d2800540 mov x0, #0x2a // #42
4: f2c002a0 movk x0, #0x15, lsl #32
8: d65f03c0 ret

ARM gnueabi:

....
bar:
@ args = 0, pretend = 0, frame = 0
@ frame_needed = 0, uses_anonymous_args = 0
@ link register save eliminated.
ldr r2, .L3
mov r3, r0
..LPIC0:
add r2, pc, r2
ldm r2, {r0, r1}
stm r3, {r0, r1}
mov r0, r3
bx lr
..L4:
.align 2
..L3:
.word .LANCHOR0-(.LPIC0+8)
.size bar, .-bar
.section .rodata
.align 2
.set .LANCHOR0,. + 0
..LC0:
.word 42
.word 21

Even with the PCC struct-return, this could be made much shorter.
It's also interesting that with all the different ABIs for ARM (and
this one even being called gnueabi), they kept PCC struct-return even
for the newer ones.

Overall, the older architectures use PCC struct-return, the newer ones
return small structs in registers.

- anton
--
'Anyone trying for "industrial quality" ISA should avoid undefined behavior.'
Mitch Alsup, <c17fcd89-f024-40e7-a594-88a85ac10d20o@googlegroups.com>

Anton Ertl <anton@mips.complang.tuwien.ac.at> schrieb:
> Thomas Koenig <tkoenig@netcologne.de> writes:
>>Anton Ertl <anton@mips.complang.tuwien.ac.at> schrieb:
>>
>>> Gcc has had -freg-struct-return for at least 30 years, but it's
>>> incompatible with the way PCC returned structs, so you cannot link
>>> code that uses reg-struct-return with code that uses pcc-struct-return
>>> if there is such a return between code using different conventions.
>>
>>The Itanium ABI fixed that.
>>
>>Rather than quote chapter and verse, here is a short example:
>>
>>$ cat ret.c
>>typedef struct foo
>>{
>> int a;
>> int b;
>>} foo;
>>
>>foo bar()
>>{
>> return ((foo){.a = 42, .b=21});
>>}
>
> produces
> ...
>> movabsq $90194313258, %rax
>> ret
>
> Does not look like IA-64 code to me.

Sorry for the jargon.

The official document is named the

System V Application Binary Interface
AMD64 Architecture Processor Supplement

which you can google for. The ABI especially for C++
was taken from the Itanium ABI, which you can find at
https://itanium-cxx-abi.github.io/cxx-abi/ , so people refer to the
whole thing as the "Itanium ABI" although that is not 100% correct.

Thomas Koenig wrote:
> Terje Mathisen <terje.mathisen@tmsw.no> schrieb:
>
>> I see you already figured this out, but I'm still posting to illustrate
>> that it is hard to do long chain carry propagation without having the
>> moral equivalent of ADC.
>
> I just browsed around a bit, and I found that, on x86 at least, you
> can use _addcarryx_u64.

Right, this was the intrinsic I used for both of my 128 and 256-bit
examples.
>
> clang gets this right: https://gcc.godbolt.org/z/b9dTn8aWj
> whereas gcc currently does not, as you can see in
> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=79173 .
>
clang is very swiftly leaving gcc well behind for all new development.

Terje

--
- <Terje.Mathisen at tmsw.no>
"almost all programming can be viewed as an exercise in caching"

On Friday, May 28, 2021 at 3:07:47 PM UTC-5, Terje Mathisen wrote:
> Thomas Koenig wrote:
> > Terje Mathisen <terje.m...@tmsw.no> schrieb:
> >
> >> I see you already figured this out, but I'm still posting to illustrate
> >> that it is hard to do long chain carry propagation without having the
> >> moral equivalent of ADC.
> >
> > I just browsed around a bit, and I found that, on x86 at least, you
> > can use _addcarryx_u64.
> Right, this was the intrinsic I used for both of my 128 and 256-bit
> examples.
> >
> > clang gets this right: https://gcc.godbolt.org/z/b9dTn8aWj
> > whereas gcc currently does not, as you can see in
> > https://gcc.gnu.org/bugzilla/show_bug.cgi?id=79173 .
> >
> clang is very swiftly leaving gcc well behind for all new development.
<
Is that because GCC has grown into an impossible monster,
.....that because GCC licensing requirements
or that more people have jumped onto clang
.....that clang is easier to develop ??
<
> Terje
>
> --
> - <Terje.Mathisen at tmsw.no>
> "almost all programming can be viewed as an exercise in caching"

MitchAlsup <MitchAlsup@aol.com> schrieb:
> On Friday, May 28, 2021 at 3:07:47 PM UTC-5, Terje Mathisen wrote:
>> Thomas Koenig wrote:
>> > Terje Mathisen <terje.m...@tmsw.no> schrieb:
>> >
>> >> I see you already figured this out, but I'm still posting to illustrate
>> >> that it is hard to do long chain carry propagation without having the
>> >> moral equivalent of ADC.
>> >
>> > I just browsed around a bit, and I found that, on x86 at least, you
>> > can use _addcarryx_u64.
>> Right, this was the intrinsic I used for both of my 128 and 256-bit
>> examples.
>> >
>> > clang gets this right: https://gcc.godbolt.org/z/b9dTn8aWj
>> > whereas gcc currently does not, as you can see in
>> > https://gcc.gnu.org/bugzilla/show_bug.cgi?id=79173 .
>> >
>> clang is very swiftly leaving gcc well behind for all new development.
><
> Is that because GCC has grown into an impossible monster,
> ....that because GCC licensing requirements

Partly. Clang seems to have a lot of big companies behind it,
companies like Google and Apple.

However, don't count out gcc yet. It just so happens that people
take more note when clang outperforms gcc than the other way around.

And I'm still waiting for their version of a working Fortran
compiler, despite the big bucks going into it. Writing a scalarizer
_is_ hard, I have to say that in their defense.

Terje Mathisen <terje.mathisen@tmsw.no> writes:
>Thomas Koenig wrote:
>> I just browsed around a bit, and I found that, on x86 at least, you
>> can use _addcarryx_u64.

If you want to be compiler-dependent instead of
architecture-and-compiler-dependent, there is also

https://gcc.gnu.org/onlinedocs/gcc/Integer-Overflow-Builtins.html

>clang is very swiftly leaving gcc well behind for all new development.

For our not-so-new development, clang is swiftly leaving gcc behind in
compilation slowness. Building the latest Gforth snapshot on a Ryzen
5800X, I see

gcc10 clang11
./configure ./configure CC=clang
real 18.114s 22.961s
user 5.863s 9.329s
sys 1.858s 3.668s

make -j make -j
real 11.930s 33m22.542s
user 53.876s 143m45.884s
sys 3.110s 22.699s

While gcc tends to compile slower over the releases, I think it will
take many releases to catch up with clang in this metric.

The run time of the clang-produced code tends to be long, too:

Time in seconds user time
sieve bubble matrix fib fft
0.056 0.055 0.034 0.047 0.021 Ryzen 5800X gcc-10
1.100 0.933 0.970 1.265 0.560 Ryzen 5800X clang-11

I looked at the generated code, and for a primitive like + which can
be done in 4 instructions and which gcc-10 does in 5 instructions:

563FB2DED3BF: add r13,$08
563FB2DED3C3: add r15,$08
563FB2DED3C7: add r8,$00[r13]
563FB2DED3CB: mov rcx,-$08[r15]
563FB2DED3CF: jmp ecx

clang-11 produces 183 instructions for +. This reminds me of a
problem that gcc had in gcc-3.0 and 3.1, and which they fixed
subsequently.

- anton

>
>Terje
>
>--
>- <Terje.Mathisen at tmsw.no>
>"almost all programming can be viewed as an exercise in caching"

--
'Anyone trying for "industrial quality" ISA should avoid undefined behavior.'
Mitch Alsup, <c17fcd89-f024-40e7-a594-88a85ac10d20o@googlegroups.com>

Thomas Koenig <tkoenig@netcologne.de> writes:
>The ABI especially for C++
>was taken from the Itanium ABI, which you can find at
>https://itanium-cxx-abi.github.io/cxx-abi/ , so people refer to the
>whole thing as the "Itanium ABI" although that is not 100% correct.

Thanks. I am not into C++, so I have never heard about "Itanium ABI"
before. A quick skim did not reveal anything about struct returns.
It looks to me like this C++ ABI is based on the regular ABI (C and
Fortran features), and defines various C++ things in terms of that,
and that's why it can transcend individual architectures.

- anton
--
'Anyone trying for "industrial quality" ISA should avoid undefined behavior.'
Mitch Alsup, <c17fcd89-f024-40e7-a594-88a85ac10d20o@googlegroups.com>

On Friday, May 28, 2021 at 11:07:47 PM UTC+3, Terje Mathisen wrote:
> Thomas Koenig wrote:
> > Terje Mathisen <terje.m...@tmsw.no> schrieb:
> >
> >> I see you already figured this out, but I'm still posting to illustrate
> >> that it is hard to do long chain carry propagation without having the
> >> moral equivalent of ADC.
> >
> > I just browsed around a bit, and I found that, on x86 at least, you
> > can use _addcarryx_u64.
> Right, this was the intrinsic I used for both of my 128 and 256-bit
> examples.
> >
> > clang gets this right: https://gcc.godbolt.org/z/b9dTn8aWj
> > whereas gcc currently does not, as you can see in
> > https://gcc.gnu.org/bugzilla/show_bug.cgi?id=79173 .
> >
> clang is very swiftly leaving gcc well behind for all new development.
> Terje
>

That is not what I observed when comparing that state of AVX2 vectorizers in clang10 vs gcc10.
gcc is sometimes o.k., sometimes bad and relatively rarely idiotic. clang is quite often idiotic.
And in gcc, when you see that vectorizer went idiotic, all you need to do is to compile with -O2, which produces solid scalar code.
In clang, to get the same effect, you have to use specialist's flag -fno-vectorize or something like that. I don't think that majority of devs, esp scientists, even heard about its existence.

> --
> - <Terje.Mathisen at tmsw.no>
> "almost all programming can be viewed as an exercise in caching"