Any Large Integer Libraries Out There for the ARM?

On 04/26/2012 08:37 PM, Tauno Voipio wrote:
> On 26.4.12 4:52 , David T. Ashley wrote:
>> On Wed, 25 Apr 2012 10:23:50 +0200, Noob<root@127.0.0.1> wrote:
>>
>>> David T. Ashley wrote:
>>>
>>>> By changing to one temporary variable (rather than 3) the compiler
>>>> seems to have shaved out two instructions (one at the start to
>>>> allocate stack space and one at the end to deallocate it).
>>>
>>> In the parameters, you should provide the value of in_u32,
>>> instead of a pointer to the value, because the compiler is
>>> reloading the value every time it is needed.
>>>
>>> You didn't specify. Which CPU(s) are you targeting?
>>
>> The compiler is set for Thumb. (I believe the Cortex-M3 handles only
>> Thumb-2 instructions, which are a superset of Thumb.)
>>
>> The parameter observation is interesting. I'd have to look at the
>> code in more detail (which I won't do now).
>>
>> But you'd think when you have a CPU with 16 registers, maybe 12 of
>> which you are free to use assuming you push a few, the compiler could
>> allocate 4 registers just to buffer the pass-by-reference inputs.
>>
>> DTA
>
> At least GCC does it - R0 to R3.
>

All ARM/Thumb compilers do it, at least if they are conforming to the 
ARM procedure call specifications.

On Thu, 26 Apr 2012 20:41:05 +0200, Arlet Ottens <usenet+5@c-scape.nl>
wrote:
>On 04/26/2012 08:37 PM, Tauno Voipio wrote:
>> On 26.4.12 4:52 , David T. Ashley wrote:
>>> On Wed, 25 Apr 2012 10:23:50 +0200, Noob<root@127.0.0.1> wrote:
>>>
>>>> David T. Ashley wrote:
>>>>
>>>>> By changing to one temporary variable (rather than 3) the compiler
>>>>> seems to have shaved out two instructions (one at the start to
>>>>> allocate stack space and one at the end to deallocate it).
>>>>
>>>> In the parameters, you should provide the value of in_u32,
>>>> instead of a pointer to the value, because the compiler is
>>>> reloading the value every time it is needed.
>>>>
>>>> You didn't specify. Which CPU(s) are you targeting?
>>>
>>> The compiler is set for Thumb. (I believe the Cortex-M3 handles only
>>> Thumb-2 instructions, which are a superset of Thumb.)
>>>
>>> The parameter observation is interesting. I'd have to look at the
>>> code in more detail (which I won't do now).
>>>
>>> But you'd think when you have a CPU with 16 registers, maybe 12 of
>>> which you are free to use assuming you push a few, the compiler could
>>> allocate 4 registers just to buffer the pass-by-reference inputs.
>>>
>>> DTA
>>
>> At least GCC does it - R0 to R3.
>>
>
>All ARM/Thumb compilers do it, at least if they are conforming to the 
>ARM procedure call specifications.

The issue is more subtle.

I gave the compiler a *UINT32 and a *UINT96.  It surely keeps the
pointers in registers.

But when you have a const * input (and it is either const * because
you declared it that way or because the compiler can determine that
you don't modify it), there is really no point in keeping the pointer.

Assuming that you use the object at least once, the compiler should
just use the pointer to put the underlying object in registers and
then forget all about the pointer.

Doesn't seem that hard.

DTA.

On 26.04.2012 21:45, David T. Ashley wrote:
> On Thu, 26 Apr 2012 20:41:05 +0200, Arlet Ottens<usenet+5@c-scape.nl>
> wrote:
>> On 04/26/2012 08:37 PM, Tauno Voipio wrote:
>>> On 26.4.12 4:52 , David T. Ashley wrote:

>>>> But you'd think when you have a CPU with 16 registers, maybe 12 of
>>>> which you are free to use assuming you push a few, the compiler could
>>>> allocate 4 registers just to buffer the pass-by-reference inputs.

It could, but it would not necessarily be a good idea.  Each of the 3 
words of your u96 construct is only read once.  So what could possibly 
be gained (other than some memory bus congestion) by loading them all 
immediately?

> I gave the compiler a *UINT32 and a *UINT96.  It surely keeps the
> pointers in registers.
>
> But when you have a const * input (and it is either const * because
> you declared it that way or because the compiler can determine that
> you don't modify it), there is really no point in keeping the pointer.

I'm afraid you're overlooking the aliasing issue.  Just because _your_ 
function doesn't modify those values doesn't mean they won't change 
mid-stride, which could actually _require_ the function to keep reading 
the original value through the pointer.

E.g. what do you think would happen if I did something (admittedly) 
crazy equivalent to

   uint32_t  mynum[10];
   mul_32_96(/*in32*/mynum + i, /*in96*/ mynum + 1, /*out*/mynum);

i.e. if one of the 4 words of output area is actually in the same place 
as your input?  That way, as soon as you start writing into your output, 
the input might change under your nose.  Note that 'const u32 *foo' 
doesn't really mean "pointer to an immutable value" --- it just means 
that you cannot change the underlying object object via this particular 
pointer.  Const-qualified can point to quite non-const data.

In case you ever read C99 language reference material and wondered what 
all that "restrict" business was about --- you've just found out.

On 26/04/2012 22:59, Hans-Bernhard Br�ker wrote:
> On 26.04.2012 21:45, David T. Ashley wrote:
>> On Thu, 26 Apr 2012 20:41:05 +0200, Arlet Ottens<usenet+5@c-scape.nl>
>> wrote:
>>> On 04/26/2012 08:37 PM, Tauno Voipio wrote:
>>>> On 26.4.12 4:52 , David T. Ashley wrote:
>
>>>>> But you'd think when you have a CPU with 16 registers, maybe 12 of
>>>>> which you are free to use assuming you push a few, the compiler could
>>>>> allocate 4 registers just to buffer the pass-by-reference inputs.
>
> It could, but it would not necessarily be a good idea. Each of the 3
> words of your u96 construct is only read once. So what could possibly be
> gained (other than some memory bus congestion) by loading them all
> immediately?
>
>> I gave the compiler a *UINT32 and a *UINT96. It surely keeps the
>> pointers in registers.
>>
>> But when you have a const * input (and it is either const * because
>> you declared it that way or because the compiler can determine that
>> you don't modify it), there is really no point in keeping the pointer.
>
> I'm afraid you're overlooking the aliasing issue. Just because _your_
> function doesn't modify those values doesn't mean they won't change
> mid-stride, which could actually _require_ the function to keep reading
> the original value through the pointer.
>
> E.g. what do you think would happen if I did something (admittedly)
> crazy equivalent to
>
> uint32_t mynum[10];
> mul_32_96(/*in32*/mynum + i, /*in96*/ mynum + 1, /*out*/mynum);
>
> i.e. if one of the 4 words of output area is actually in the same place
> as your input? That way, as soon as you start writing into your output,
> the input might change under your nose. Note that 'const u32 *foo'
> doesn't really mean "pointer to an immutable value" --- it just means
> that you cannot change the underlying object object via this particular
> pointer. Const-qualified can point to quite non-const data.
>
> In case you ever read C99 language reference material and wondered what
> all that "restrict" business was about --- you've just found out.

Or maybe we should all use Fortran, where "restrict" is implied in such 
cases.

It always bugs me that C compilers are forced to produce poorer code 
just because some sod wants to write code like that.

On Thu, 26 Apr 2012 22:59:09 +0200, Hans-Bernhard Br�ker
<HBBroeker@t-online.de> wrote:
>
>I'm afraid you're overlooking the aliasing issue.  Just because _your_ 
>function doesn't modify those values doesn't mean they won't change 
>mid-stride, which could actually _require_ the function to keep reading 
>the original value through the pointer.
>
>E.g. what do you think would happen if I did something (admittedly) 
>crazy equivalent to
>
>   uint32_t  mynum[10];
>   mul_32_96(/*in32*/mynum + i, /*in96*/ mynum + 1, /*out*/mynum);
>
>i.e. if one of the 4 words of output area is actually in the same place 
>as your input?  That way, as soon as you start writing into your output, 
>the input might change under your nose.  Note that 'const u32 *foo' 
>doesn't really mean "pointer to an immutable value" --- it just means 
>that you cannot change the underlying object object via this particular 
>pointer.  Const-qualified can point to quite non-const data.
>
>In case you ever read C99 language reference material and wondered what 
>all that "restrict" business was about --- you've just found out.

Thanks for the info.

I was not aware of the "restrict" keyword.  This is a C99 addition:

http://en.wikipedia.org/wiki/C99

With some C90 compilers, I've seen various warning notes about
enabling certain optimizations unless certain constraints on pointers
were followed.  This was apparently enough of a common occurrence that
the "restrict" keyword showed up in C99 so that it could be handled in
a more regular framework.

OK, your post constitutes my training for the year.  I try to learn
exactly one new thing every 365.25 days.  I'll print this post and
send it to our HR person and I'm good until 2013 ...

DTA

David T. Ashley wrote:

> I was not aware of the "restrict" keyword.

cf. also http://en.wikipedia.org/wiki/Restrict

> This is a C99 addition: http://en.wikipedia.org/wiki/C99

Those who cannot afford the official standard may grab n1256.pdf

  http://www.open-std.org/jtc1/sc22/WG14/www/docs/n1256.pdf

> With some C90 compilers, I've seen various warning notes about
> enabling certain optimizations unless certain constraints on pointers
> were followed.  This was apparently enough of a common occurrence that
> the "restrict" keyword showed up in C99 so that it could be handled in
> a more regular framework.

AFAIR, gcc supports restrict even in (non-pedantic) C89 mode.

Regards.

On Thu, 26 Apr 2012 22:59:09 +0200
Hans-Bernhard Br&ouml;ker <HBBroeker@t-online.de> wrote:

> I'm afraid you're overlooking the aliasing issue.  Just because
> _your_ function doesn't modify those values doesn't mean they won't
> change mid-stride, which could actually _require_ the function to
> keep reading the original value through the pointer.
> 
> E.g. what do you think would happen if I did something (admittedly) 
> crazy equivalent to
> 
>    uint32_t  mynum[10];
>    mul_32_96(/*in32*/mynum + i, /*in96*/ mynum + 1, /*out*/mynum);

Doesn't the C strict aliasing rule make this unspecified behaviour?
Pointers to different types neither of which are
(signed|unsigned|blank) char and which aren't related by one being an
element of the other are assumed not to alias.

Chris

On Fri, 27 Apr 2012 15:08:41 +0200, Noob <root@127.0.0.1> wrote:

>David T. Ashley wrote:
>
>> I was not aware of the "restrict" keyword.
>
>cf. also http://en.wikipedia.org/wiki/Restrict
>
>> This is a C99 addition: http://en.wikipedia.org/wiki/C99
>
>Those who cannot afford the official standard may grab n1256.pdf
>
>  http://www.open-std.org/jtc1/sc22/WG14/www/docs/n1256.pdf
>
>> With some C90 compilers, I've seen various warning notes about
>> enabling certain optimizations unless certain constraints on pointers
>> were followed.  This was apparently enough of a common occurrence that
>> the "restrict" keyword showed up in C99 so that it could be handled in
>> a more regular framework.
>
>AFAIR, gcc supports restrict even in (non-pedantic) C89 mode.

Could you define "pedantic" in this usage?

I looked up the word in a dictionary and also looked at compiler
options, and the meaning of the word really isn't making sense to me.

What is "pedantic"?

Thanks, DTA

On 27/04/2012 15:55, David T. Ashley wrote:
> On Fri, 27 Apr 2012 15:08:41 +0200, Noob<root@127.0.0.1>  wrote:
>
>> David T. Ashley wrote:
>>
>>> I was not aware of the "restrict" keyword.
>>
>> cf. also http://en.wikipedia.org/wiki/Restrict
>>
>>> This is a C99 addition: http://en.wikipedia.org/wiki/C99
>>
>> Those who cannot afford the official standard may grab n1256.pdf
>>
>>   http://www.open-std.org/jtc1/sc22/WG14/www/docs/n1256.pdf
>>
>>> With some C90 compilers, I've seen various warning notes about
>>> enabling certain optimizations unless certain constraints on pointers
>>> were followed.  This was apparently enough of a common occurrence that
>>> the "restrict" keyword showed up in C99 so that it could be handled in
>>> a more regular framework.
>>
>> AFAIR, gcc supports restrict even in (non-pedantic) C89 mode.
>
> Could you define "pedantic" in this usage?
>
> I looked up the word in a dictionary and also looked at compiler
> options, and the meaning of the word really isn't making sense to me.
>
> What is "pedantic"?
>
> Thanks, DTA

"Pedantic" means "particularly fussy or detailed".  With gcc, using 
"pedantic" means that the compiler will be much stricter about 
supporting the standards, and /only/ the standards.  For example, 
"restrict" and "inline" are keywords in later C standards, but were not 
available in earlier ones.  gcc likes to give you more features than the 
standards demand, so that you can use these features when compiling in 
C89 mode.  But to allow for people who happened to have a function 
called "restrict" and a typedef called "inline", which is legal in C89 
but not C99, you can compile in "pedantic" mode.  (You can still access 
newer features as "__restrict__" or "__inline__" for example.) 
"pedantic" mode is also useful for checking strict standards 
compatibility to aid portability of code.

On 27/04/2012 15:40, Christopher Head wrote:
> On Thu, 26 Apr 2012 22:59:09 +0200
> Hans-Bernhard Br&ouml;ker<HBBroeker@t-online.de>  wrote:
>
>> I'm afraid you're overlooking the aliasing issue.  Just because
>> _your_ function doesn't modify those values doesn't mean they won't
>> change mid-stride, which could actually _require_ the function to
>> keep reading the original value through the pointer.
>>
>> E.g. what do you think would happen if I did something (admittedly)
>> crazy equivalent to
>>
>>     uint32_t  mynum[10];
>>     mul_32_96(/*in32*/mynum + i, /*in96*/ mynum + 1, /*out*/mynum);
>
> Doesn't the C strict aliasing rule make this unspecified behaviour?
> Pointers to different types neither of which are
> (signed|unsigned|blank) char and which aren't related by one being an
> element of the other are assumed not to alias.
>
> Chris

The types in question are 32-bit integers or arrays of 32-bit integers, 
and these /are/ allowed to alias each other (AFAIUI).

mvh.,

David