Re: Difficulty in implementing a GCC plugin for [[invariant]] contract functions in classes/structs without prior experience?

[Gavin Ray via Gcc]

Hey all, I've continued to work on this and have it mostly finished
The implementation is here

GCC [[invariant]] plugin for Design by Contract (WIP) (github.com)


I have posted the final remaining question to StackOverflow in case anyone
knows
It's about how to insert a call to a C++ Member Function, from another
Mem-Fn using the GIMPLE API:

GCC GIMPLE C++ API, how to insert a call to a member-function from another
member-function? - Stack Overflow


Would be grateful for any advice. I asked Iain Buclaw, who maintains GDC,
and he was able to help but doesn't have a ton of expertise in the C++
frontend.
Thanks all

On Thu, Dec 29, 2022 at 1:33 PM Gavin Ray  wrote:

> So I have prototyped the code here, there are two places where I am
> confused:
> GCC [[invariant]] plugin for Design by Contract (WIP) (github.com)
> 
>
> 1. Is it proper to cast like this?
>
> tree args = NULL_TREE;
> tree tmp_tree = NULL_TREE;
> vec** args_ptr = (vec**)&args;
>
> tree call = build_new_method_call(class_type, id, args_ptr, fun->decl,
> LOOKUP_NORMAL, &tmp_tree, tf_warning_or_error);
>
> 2. At the bottom, I want to call "invariant()" before "return", but I'm
> not sure how to phrase this in code. The following doesn't work quite right:
> because you can't compare "gsi_stmt()" and NULL_TREE
>
> // If the last block is a return block, insert the call before the
> return statement.
> if (gsi_stmt(gsi) != NULL_TREE && gimple_code(gsi_stmt(gsi)) ==
> GIMPLE_RETURN)
> gsi_insert_before(&gsi, g, GSI_SAME_STMT);
> else
> gsi_insert_after(&gsi, g, GSI_SAME_STMT);
>
>
>
>
> On Thu, Dec 29, 2022 at 10:37 AM Gavin Ray  wrote:
>
>> Hey all,
>>
>> The feature I appreciate most about the D programming language is its
>> "Design by Contract" feature.
>> Contract programming - Dlang Tour
>> 
>>
>> With the recent merge of Contracts to GCC master, C++ comes close to
>> this, with support for function-based contracts.
>> The most powerful contract though, is the "invariant" contract:
>>
>> *invariant() is a special member function of struct and class types that
>>> allows sanity checking an object's state during its whole lifetime:*
>>
>>
>>>
>>> *- invariant() is called after the constructor has run and before the
>>> destructor is called.*
>>> *- invariant() is called before entering a member function*
>>> *- invariant() is called after exiting a member function.**- Class
>>> invariants are inherited. That means that a derived class invariant will
>>> implicitly call the base class invariant.*
>>
>>
>> I'm very interested in prototyping a GCC plugin to implement support for
>> transforming all member function calls in class/struct types
>> such that a call to the [[invariant]]-annotated function (if any) is
>> placed at the beginning and end of method bodies.
>>
>> Does anyone have any idea whether something like this would be suitable
>> for a first plugin,
>> or if there would be roadblocks/technical challenges to implementing such
>> a thing?
>>
>> I'd be grateful for any advice.
>>
>> Thank you,
>> Gavin =)
>>
>>

stdc_bit_ceil(3) and wrapping

[Alejandro Colomar via Gcc]

Hi Joseph,

I'm implementing a small part of  equivalent code for shadow.  I need 
stdc_bit_ceilul() for a random number generator limited to a range (you've seen 
some of this in the glibc mailing list.



$ grepc -tfd shadow_random_uniform
./libmisc/random.c:76:
unsigned long
shadow_random_uniform(unsigned long upper_bound)
{
unsigned long  r;

do {
r = shadow_random();
r &= bit_ceil_wrapul(upper_bound) - 1;  // optimization
} while (r > upper_bound - 1);

return r;
}


However, I need that it doesn't have undefined behavior if it doesn't fit the 
type, but rather that it wraps around (as the simplest implementation would do, 
BTW).  I've done the following:



$ cat lib/bit.h
#include 


inline int leading_zerosul(unsigned long x);
inline int bit_widthul(unsigned long x);
inline int bit_ceil_wrapul(unsigned long x);


inline int
leading_zerosul(unsigned long x)
{
return (x == 0) ? ULONG_WIDTH : __builtin_clz(x);
}


inline int
bit_widthul(unsigned long x)
{
return ULONG_WIDTH - leading_zerosul(x);
}


/* Similar to stdc_bit_ceilul(), but wrap around instead of UB.  */
inline int
bit_ceil_wrapul(unsigned long x)
{
return 1 << bit_widthul(x - 1);
}



I was wondering if there was any reason to make that UB in the standard, when 
unsigned wrapping has always been well-defined, and this is a case that is 
likely to be implemented with some operation that wraps around, right?  I can't 
imagine of an implementation that invokes UB.  Moreover, as you can see, it is 
useful to make it wrap around in a defined way.


Would you consider either or both of being more generous in the GNU 
implementation and guarantee wrap around, and/or suggest that the standard 
guarantees the wrap around?


And BTW, if any of this code helps you implement that for GNU, please feel free 
to take it.  :)


Cheers,

Alex


--



OpenPGP_signature
Description: OpenPGP digital signature

Re: stdc_bit_ceil(3) and wrapping

[Yann Droneaud]

Hi,

30 décembre 2022 à 20:55 "Alejandro Colomar via Libc-alpha" 
 a écrit:
> 
> I'm implementing a small part of  equivalent code for shadow. I 
> need 
> stdc_bit_ceilul() for a random number generator limited to a range (you've 
> seen 
> some of this in the glibc mailing list.
> 
> $ grepc -tfd shadow_random_uniform
> ./libmisc/random.c:76:
> unsigned long
> shadow_random_uniform(unsigned long upper_bound)
> {
>  unsigned long r;
> 
>  do {
>  r = shadow_random();
>  r &= bit_ceil_wrapul(upper_bound) - 1; // optimization
>  } while (r > upper_bound - 1);
> 
>  return r;
> }
> 

What's wrong with the following ?

if (upper_bound < 2)
return 0;

unsigned long max = upper_bound - 1;
unsigned long mask = ULONG_MAX >> __builtin_clzl(max);

do {
r = shadow_random();
r &= mask;
} while (r > max);

return r;

> However, I need that it doesn't have undefined behavior if it doesn't fit the 
> type, but rather that it wraps around (as the simplest implementation would 
> do, 
> BTW). I've done the following:
> 
> $ cat lib/bit.h
> #include 
> 
> inline int leading_zerosul(unsigned long x);
> inline int bit_widthul(unsigned long x);
> inline int bit_ceil_wrapul(unsigned long x);
> 
> inline int
> leading_zerosul(unsigned long x)
> {
>  return (x == 0) ? ULONG_WIDTH : __builtin_clz(x);
> }
> 
> inline int
> bit_widthul(unsigned long x)
> {
>  return ULONG_WIDTH - leading_zerosul(x);
> }
> 
> /* Similar to stdc_bit_ceilul(), but wrap around instead of UB. */
> inline int
> bit_ceil_wrapul(unsigned long x)
> {
>  return 1 << bit_widthul(x - 1);
> }
> 
> I was wondering if there was any reason to make that UB in the standard, when 
> unsigned wrapping has always been well-defined, and this is a case that is 
> likely to be implemented with some operation that wraps around, right? I 
> can't 
> imagine of an implementation that invokes UB. Moreover, as you can see, it is 
> useful to make it wrap around in a defined way.
> 
> Would you consider either or both of being more generous in the GNU 
> implementation and guarantee wrap around, and/or suggest that the standard 
> guarantees the wrap around?
> 
> And BTW, if any of this code helps you implement that for GNU, please feel 
> free 
> to take it. :)
> 

-- 
Yann Droneaud
OPTEYA

Re: stdc_bit_ceil(3) and wrapping

[Alejandro Colomar via Gcc]

Hi Yann,

On 12/30/22 21:18, Yann Droneaud wrote:

Hi,

30 décembre 2022 à 20:55 "Alejandro Colomar via Libc-alpha" 
 a écrit:


I'm implementing a small part of  equivalent code for shadow. I need
stdc_bit_ceilul() for a random number generator limited to a range (you've seen
some of this in the glibc mailing list.

$ grepc -tfd shadow_random_uniform
./libmisc/random.c:76:
unsigned long
shadow_random_uniform(unsigned long upper_bound)
{
  unsigned long r;

  do {
  r = shadow_random();
  r &= bit_ceil_wrapul(upper_bound) - 1; // optimization
  } while (r > upper_bound - 1);

  return r;
}



What's wrong with the following ?

 if (upper_bound < 2)
 return 0;


If upper_bound is 1, the only valid value is 0, but if it is 0, I prefer it to 
behave as if there was no bound at all, because then it allows a function 
shadow_random_range(min, max) to be implemented as:



/*
 * Return a uniformly-distributed random number in the inclusive range:
 * [min, max]
 */
unsigned long
shadow_random_range(unsigned long min, unsigned long max)
{
return shadow_random_uniform(max - min + 1) + min;
}


That function has no problems when max is ULONG_MAX and min is 0, which is a 
nice feature.



BTW, this is something that might be interesting for both rand(3) and 
arc4random(3) in libc, since it's something that is error-prone to roll your own 
wrapper around the *_uniform() function (for example, shadow had it biased, and 
I'm fixing it).


If you want, I could prepare a patch for glibc.



 unsigned long max = upper_bound - 1;
 unsigned long mask = ULONG_MAX >> __builtin_clzl(max);


I hate coding these magic operations out of a function, when I can give it a 
meaningful name.  That reads to me as a magic trick that many maintainers that 
read it after me will blame me for having to parse it.


Moreover, it requires you to have the special case for 0 at the top, which I 
don't want.




 do {
 r = shadow_random();
 r &= mask;


Moving the calculation of the mask out of the loop is something I had in mind, 
yep.

I also considered reusing the remaining bits if possible, but I prefer to keep 
the code simple, even if it has a few more calls to arc4random(3) underneath.



 } while (r > max);


Yeah, this max is more friendly than my magic -1.  Thanks! :)



 return r;



Cheers,

Alex

--



OpenPGP_signature
Description: OpenPGP digital signature

Re: stdc_bit_ceil(3) and wrapping

[Joseph Myers]

On Fri, 30 Dec 2022, Alejandro Colomar via Gcc wrote:

> I was wondering if there was any reason to make that UB in the standard, when
> unsigned wrapping has always been well-defined, and this is a case that is
> likely to be implemented with some operation that wraps around, right?  I

It's likely to be implemented by a shift, that might be by the number of 
bits in the argument in the overflow case, and shift by the width of the 
argument is undefined behavior; some architectures wrap the shift count 
modulo the width (do you actually want 1 or 0 as the result of 
stdc_bit_ceil?), some wrap the shift count modulo a larger value (e.g. 
treating 1 << 32 as 0 but 1 << 64 as 1) and for some architectures the 
result depends on the particular shift instruction used (meaning undefined 
behavior on the form of the result of an integer expression possibly 
comparing unequal to itself because the compiler duplicated the expression 
and then used different instructions to compute it in different places).

> Would you consider either or both of being more generous in the GNU
> implementation and guarantee wrap around, and/or suggest that the standard
> guarantees the wrap around?

The CD ballot has closed, and this doesn't appear to be one of the 338 
comments raised on that ballot, and I don't really expect time at next 
month's meeting to deal with additional technical comments not on that 
list, when we have only 15 hours to deal with 338 comments.  Once we have 
an issue tracking process for the C standard again (hopefully involving an 
issue tracker that the public can readily submit issues in), I'd suggest 
raising such concerns there (unless there's a CD2 ballot; technical 
comments are best avoided at a DIS ballot if possible).

-- 
Joseph S. Myers
jos...@codesourcery.com

Re: stdc_bit_ceil(3) and wrapping

[Alejandro Colomar via Gcc]

Hi Joseph,

On 12/30/22 21:38, Joseph Myers wrote:

On Fri, 30 Dec 2022, Alejandro Colomar via Gcc wrote:


I was wondering if there was any reason to make that UB in the standard, when
unsigned wrapping has always been well-defined, and this is a case that is
likely to be implemented with some operation that wraps around, right?  I


It's likely to be implemented by a shift, that might be by the number of
bits in the argument in the overflow case, and shift by the width of the
argument is undefined behavior; some architectures wrap the shift count
modulo the width (do you actually want 1 or 0 as the result of
stdc_bit_ceil?), some wrap the shift count modulo a larger value (e.g.
treating 1 << 32 as 0 but 1 << 64 as 1) and for some architectures the
result depends on the particular shift instruction used (meaning undefined
behavior on the form of the result of an integer expression possibly
comparing unequal to itself because the compiler duplicated the expression
and then used different instructions to compute it in different places).


For the C standard, shifts have wrap around semantics for unsigned types:

C2x(N3054)::6.5.7p4:

"
The result of E1 << E2 is E1 left-shifted E2 bit positions; vacated bits are 
filled with zeros.  If E1 has an unsigned type, the value of the result is E1 × 
2E2, wrapped around.  [...]

"

Which reminds me that I forgot to use 1ul << ...

Since the  functions are only provided for unsigned types, there 
should be no problems, right?





Would you consider either or both of being more generous in the GNU
implementation and guarantee wrap around, and/or suggest that the standard
guarantees the wrap around?


The CD ballot has closed, and this doesn't appear to be one of the 338
comments raised on that ballot, and I don't really expect time at next
month's meeting to deal with additional technical comments not on that
list, when we have only 15 hours to deal with 338 comments.  Once we have
an issue tracking process for the C standard again (hopefully involving an
issue tracker that the public can readily submit issues in),


Hopefully.  And a public git repository and mailing list would be awesome  :)

*comes back to reality*


I'd suggest
raising such concerns there (unless there's a CD2 ballot; technical
comments are best avoided at a DIS ballot if possible).


Ahh, no problem.  If it's something to be suggested for C3x or for a small C2y 
fix (like C17 was), that would be fine.


Cheers,

Alex






--



OpenPGP_signature
Description: OpenPGP digital signature

Re: stdc_bit_ceil(3) and wrapping

[Alejandro Colomar via Gcc]

Hi Yann,

On 12/30/22 21:18, Yann Droneaud wrote:

30 décembre 2022 à 20:55 "Alejandro Colomar via Libc-alpha" 
 a écrit:


I'm implementing a small part of  equivalent code for shadow. I need
stdc_bit_ceilul() for a random number generator limited to a range (you've seen
some of this in the glibc mailing list.

$ grepc -tfd shadow_random_uniform
./libmisc/random.c:76:
unsigned long
shadow_random_uniform(unsigned long upper_bound)
{
  unsigned long r;

  do {
  r = shadow_random();
  r &= bit_ceil_wrapul(upper_bound) - 1; // optimization
  } while (r > upper_bound - 1);

  return r;
}



What's wrong with the following ?

 if (upper_bound < 2)
 return 0;

 unsigned long max = upper_bound - 1;
 unsigned long mask = ULONG_MAX >> __builtin_clzl(max);

 do {
 r = shadow_random();
 r &= mask;
 } while (r > max);

 return r;




Based on some of your suggestions, I updated it to be the following:

unsigned long
shadow_random_uniform(unsigned long upper_bound)
{
unsigned long  r, max, mask;

max = upper_bound - 1;
mask = bit_ceilul(upper_bound) - 1;

do {
r = shadow_random();
r &= mask;  // optimization
} while (r > max);

return r;
}


See how upper_bound == 0 acts as if upper_bound had a value one more than the 
maximum representable value in the type, which is a nice property.



Cheers,

Alex

--



OpenPGP_signature
Description: OpenPGP digital signature

Re: stdc_bit_ceil(3) and wrapping

[Joseph Myers]

On Fri, 30 Dec 2022, Alejandro Colomar via Gcc wrote:

> For the C standard, shifts have wrap around semantics for unsigned types:

Only if the shift count is nonnegative and strictly less than the width of 
the type.  This is about shifting by an amount equal to the width of the 
type, which has undefined behavior.

-- 
Joseph S. Myers
jos...@codesourcery.com

Re: stdc_bit_ceil(3) and wrapping

[Alejandro Colomar via Gcc]

On 12/30/22 21:56, Joseph Myers wrote:

On Fri, 30 Dec 2022, Alejandro Colomar via Gcc wrote:


For the C standard, shifts have wrap around semantics for unsigned types:


Only if the shift count is nonnegative and strictly less than the width of
the type.  This is about shifting by an amount equal to the width of the
type, which has undefined behavior.


Ahhh, right, I forgot that detail.  Yep, I need to special-case then.

Thanks!



--



OpenPGP_signature
Description: OpenPGP digital signature

Re: stdc_bit_ceil(3) and wrapping

[Alejandro Colomar via Gcc]

On 12/30/22 22:01, Alejandro Colomar wrote:

On 12/30/22 21:56, Joseph Myers wrote:

On Fri, 30 Dec 2022, Alejandro Colomar via Gcc wrote:


For the C standard, shifts have wrap around semantics for unsigned types:


Only if the shift count is nonnegative and strictly less than the width of
the type.  This is about shifting by an amount equal to the width of the
type, which has undefined behavior.


Ahhh, right, I forgot that detail.  Yep, I need to special-case then.

Thanks!





This should work, I guess (and hopefully, the compiler will remove the special 
case in platforms that don't need it):



$ cat lib/bit.h
#include 


inline int leading_zerosul(unsigned long x);
inline int bit_widthul(unsigned long x);
inline int bit_ceil_wrapul(unsigned long x);


inline int
leading_zerosul(unsigned long x)
{
return (x == 0) ? ULONG_WIDTH : __builtin_clz(x);
}


inline int
bit_widthul(unsigned long x)
{
return ULONG_WIDTH - leading_zerosul(x);
}


/* Similar to stdc_bit_ceilul(), but wrap around instead of UB.  */
inline int
bit_ceil_wrapul(unsigned long x)
{
int b;

b = bit_widthul(x - 1);

return b < ULONG_WIDTH ? 1ul << b : 0;
}


--



OpenPGP_signature
Description: OpenPGP digital signature

Re: stdc_bit_ceil(3) and wrapping

[Alejandro Colomar via Gcc]

Hi Yann,

On 12/30/22 21:33, Alejandro Colomar wrote:

On 12/30/22 21:18, Yann Droneaud wrote:

What's wrong with the following ?


[...]





 unsigned long max = upper_bound - 1;
 unsigned long mask = ULONG_MAX >> __builtin_clzl(max);


I hate coding these magic operations out of a function, when I can give it a 
meaningful name.  That reads to me as a magic trick that many maintainers that 
read it after me will blame me for having to parse it.


Moreover, it requires you to have the special case for 0 at the top, which I 
don't want.


I reconsidered; my -1 was equally magic.  And by calling it 'mask',
ULONG_MAX >> n is something not so magic.

The builtin still has the problem that it requires special-casing 0, so I prefer 
the C23 call, which provides the behavior I want for 0:



unsigned long
shadow_random_uniform(unsigned long upper_bound)
{
unsigned long  r, max, mask;

max = upper_bound - 1;
mask = ULONG_MAX >> leading_zerosul(max);

do {
r = shadow_random();
r &= mask;  // optimization
} while (r > max);

return r;
}


And, now I don't need to add a wrapper around bit_ceil() that removes the UB. 
stdc_leading_zerosul() is just fine for this use case.


Cheers,

Alex

--



OpenPGP_signature
Description: OpenPGP digital signature

gcc-11-20221230 is now available

[GCC Administrator via Gcc]

Snapshot gcc-11-20221230 is now available on
  https://gcc.gnu.org/pub/gcc/snapshots/11-20221230/
and on various mirrors, see http://gcc.gnu.org/mirrors.html for details.

This snapshot has been generated from the GCC 11 git branch
with the following options: git://gcc.gnu.org/git/gcc.git branch 
releases/gcc-11 revision e0d3d87f9e58991426745c156361c6039a4f4587

You'll find:

 gcc-11-20221230.tar.xz   Complete GCC

  SHA256=7d1a6ea3f74ab3d75e172d0dd1cccedab6f27be2b5e28cd49a15702a2cccb195
  SHA1=d162860a250bc47b303ab8fbd94c3017e0147f83

Diffs from 11-20221223 are available in the diffs/ subdirectory.

When a particular snapshot is ready for public consumption the LATEST-11
link is updated and a message is sent to the gcc list.  Please do not use
a snapshot before it has been announced that way.