Straw poll on shifts with out of range operands

Straw poll on shifts with out of range operands

[Andrew Pinski]

I am in the middle of improving the isolation path pass for shifts
with out of range operands.
There are 3 options we could do really:
1) isolate the path to __builtin_unreachable
2) isolate the path to __builtin_trap
    This is what is currently done for null pointer and divide by zero
3) isolate the path and turn the shift into zero constant
   This happens currently for explicit use in both match (in many
cases) and VRP for others.

All 3 are not hard to implement.
This comes up in the context of https://gcc.gnu.org/PR115636 where the
original requestor thinks it should be #3 but I suspect they didn't
realize it was undefined behavior then.
2 seems the best for user experience.
1 seems like the best for optimizations.
3 is more in line with how other parts of the compiler handle it.

So the question I have is which one should we go for? (is there
another option I missed besides not do anything)

Thanks,
Andrew Pinski

Re: Straw poll on shifts with out of range operands

[Jeff Law]

On 6/25/24 8:44 PM, Andrew Pinski via Gcc wrote:
> I am in the middle of improving the isolation path pass for shifts
> with out of range operands.
> There are 3 options we could do really:
> 1) isolate the path to __builtin_unreachable
> 2) isolate the path to __builtin_trap
>      This is what is currently done for null pointer and divide by zero
> 3) isolate the path and turn the shift into zero constant
>     This happens currently for explicit use in both match (in many
> cases) and VRP for others.
> 
> All 3 are not hard to implement.
> This comes up in the context of https://gcc.gnu.org/PR115636 where the
> original requestor thinks it should be #3 but I suspect they didn't
> realize it was undefined behavior then.
> 2 seems the best for user experience.
> 1 seems like the best for optimizations.
> 3 is more in line with how other parts of the compiler handle it.
> 
> So the question I have is which one should we go for? (is there
> another option I missed besides not do anything)
There was a time when we were thinking about having a knob that would 
allow one to select which of the 3 approaches makes the most sense given 
the expected execution environment.

While I prefer #2, some have (reasonably) argued that it's not 
appropriate behavior for code in a library.

I'm not a fan of #1 because it allows unpredictable code execution. 
Essentially you just fall into whatever code was after the bogus shift 
in the executable and hope for the best.  One day this is going to bite 
us hard from a security standpoint.

#3 isn't great, but it's not terrible either.

Jeff

Re: Straw poll on shifts with out of range operands

[Richard Biener]

On Wed, Jun 26, 2024 at 4:59 AM Jeff Law via Gcc <gcc@gcc.gnu.org> wrote:
>
>
>
> On 6/25/24 8:44 PM, Andrew Pinski via Gcc wrote:
> > I am in the middle of improving the isolation path pass for shifts
> > with out of range operands.
> > There are 3 options we could do really:
> > 1) isolate the path to __builtin_unreachable
> > 2) isolate the path to __builtin_trap
> >      This is what is currently done for null pointer and divide by zero
> > 3) isolate the path and turn the shift into zero constant
> >     This happens currently for explicit use in both match (in many
> > cases) and VRP for others.

How is isolation if we do 3) any useful?  IIRC the path isolation pass
would only look for literal out-of-range shifts?  Or do you plan to use
range info?  If we do 3) why not let range folding deal with this then?

> >
> > All 3 are not hard to implement.
> > This comes up in the context of https://gcc.gnu.org/PR115636 where the
> > original requestor thinks it should be #3 but I suspect they didn't
> > realize it was undefined behavior then.
> > 2 seems the best for user experience.
> > 1 seems like the best for optimizations.
> > 3 is more in line with how other parts of the compiler handle it.
> >
> > So the question I have is which one should we go for? (is there
> > another option I missed besides not do anything)
> There was a time when we were thinking about having a knob that would
> allow one to select which of the 3 approaches makes the most sense given
> the expected execution environment.

Since we do 3) already elsewhere I'd say we should do that by default and
have the other options behind a command-line switch - though we already
have UBSAN for that and that is going to be much more reliable than the late
path isolation done after folding catched most cases via 3)?

> While I prefer #2, some have (reasonably) argued that it's not
> appropriate behavior for code in a library.
>
> I'm not a fan of #1 because it allows unpredictable code execution.
> Essentially you just fall into whatever code was after the bogus shift
> in the executable and hope for the best.  One day this is going to bite
> us hard from a security standpoint.
>
> #3 isn't great, but it's not terrible either.
>
> Jeff

IFNDR on UB? [was: Straw poll on shifts with out of range operands]

[Matthias Kretz]

[-- Attachment #1: Type: text/plain, Size: 3116 bytes --]

On Tuesday, 25 June 2024 21:44:15 CDT Andrew Pinski via Gcc wrote:
> I am in the middle of improving the isolation path pass for shifts
> with out of range operands.
> There are 3 options we could do really:
> 1) isolate the path to __builtin_unreachable
> 2) isolate the path to __builtin_trap
>     This is what is currently done for null pointer and divide by zero
> 3) isolate the path and turn the shift into zero constant
>    This happens currently for explicit use in both match (in many
> cases) and VRP for others.

IIUC, I vote for __builtin_unreachable. However, I understand that there's no 
one-size-fits-all solution here.

Have you considered
4) ill-formed (no diagnostic required)?

I was told yesterday in WG21 session that an implementation is allowed to make 
a program ill-formed on precondition violation/UB. FWIW, I don't believe it. 
But there's an opportunity to be explored here.

Consider the following sketch

  [[gnu::noinline, gnu::error("precondition violation")]]
  void
  __error()
  { __builtin_unreachable(); }

  [[gnu::always_inline]]
  inline void
  __check_precondition(bool cond)
  {
    if (__builtin_constant_p(cond) && !cond)
      __error();
    else if (!cond)
  #ifdef __HARDEN__
      __builtin_trap();
  #else
      __builtin_unreachable();
  #endif
  }

  int
  operator<<(int a, int b) {
    __check_precondition(b >= 0 && b < 32);
    return // actual shift
  }

Then the following is ill-formed, which I think is fairly sensible:

  int f1(int x) { return x << 40; }

But the next example seems questionable:

  // precondition: c == false
  int f2(int x, bool c) { return c ? x << 40 : x; }

until one recognizes that 'f2' is missing a precondition check:

  int f2(int x, bool c) {
    __check_precondition(c == false);
    return c ? x << 40 : x;
  }

I.e. once UB becomes IFNDR, the dreaded time-travel optimizations can't happen 
anymore. Instead precondition checks bubble up because otherwise the program 
is ill-formed.

Again, I don't believe this would be conforming to the C++ standard. But I 
believe it's a very interesting mode to add as a compiler flag.

-fharden=0 (default)
-fharden=1 (make UB ill-formed or unreachable)
-fharden=2 (make UB ill-formed or trap)

If there's interest I'd be willing to look into a patch to libstdc++, building 
upon the above sketch as a starting point. Ultimately, if this becomes a 
viable build mode, I'd like to have a replacement for the [[gnu::error("")]] 
hack with a dedicated builtin.

- Matthias

-- 
──────────────────────────────────────────────────────────────────────────
 Dr. Matthias Kretz                           https://mattkretz.github.io
 GSI Helmholtz Center for Heavy Ion Research               https://gsi.de
 std::simd
──────────────────────────────────────────────────────────────────────────

[-- Attachment #2: This is a digitally signed message part. --]
[-- Type: application/pgp-signature, Size: 488 bytes --]

Re: IFNDR on UB? [was: Straw poll on shifts with out of range operands]

[Martin Uecker]

Am Samstag, dem 29.06.2024 um 08:50 -0500 schrieb Matthias Kretz via Gcc:


...
> I.e. once UB becomes IFNDR, the dreaded time-travel optimizations can't happen 
> anymore. Instead precondition checks bubble up because otherwise the program 
> is ill-formed.

It is not clear to mean what you mean by this?

Note that in C time-travel optimizations are already not allowed.
But I am not sure how this is relevant here as this affects only
observable behavior and the only case where GCC does not seem to
already conform to this is volatile.

Of course, C++ may be different but I suspect that some of the
discussion is confusing compiler bugs with time-travel:

https://developercommunity.visualstudio.com/t/Invalid-optimization-in-CC/10337428?q=muecker



> 
> Again, I don't believe this would be conforming to the C++ standard. But I 
> believe it's a very interesting mode to add as a compiler flag.
> 
> -fharden=0 (default)
> -fharden=1 (make UB ill-formed or unreachable)
> -fharden=2 (make UB ill-formed or trap)
> 
> If there's interest I'd be willing to look into a patch to libstdc++, building 
> upon the above sketch as a starting point. Ultimately, if this becomes a 
> viable build mode, I'd like to have a replacement for the [[gnu::error("")]] 
> hack with a dedicated builtin.

-fharden should never turn this into unreachable.

But I agree that we should have options for different choices. 

IMHO the FEs should insert the conditional traps when requested to
and the middle end could then treat it as UB and more freely
decide what to do.  Also IMHO this should be split up from
UBsan which has specific semantics and upstream dependencies
which are are not always ideal.  (But UBSan could share the
same infrastructure)

Martin

Re: IFNDR on UB? [was: Straw poll on shifts with out of range operands]

[Matthias Kretz]

[-- Attachment #1: Type: text/plain, Size: 3848 bytes --]

On Saturday, 29 June 2024 16:20:55 GMT+2 Martin Uecker wrote:
> Am Samstag, dem 29.06.2024 um 08:50 -0500 schrieb Matthias Kretz via Gcc:
> > I.e. once UB becomes IFNDR, the dreaded time-travel optimizations can't
> > happen anymore. Instead precondition checks bubble up because otherwise
> > the program is ill-formed.
> 
> It is not clear to mean what you mean by this?

It would help if you could point out what is unclear to you. I assume you know 
IFNDR? And I gave an example for the "bubbling up" of precondition checks 
directly above your quoted paragraph.

> Note that in C time-travel optimizations are already not allowed.

Then, calling __builtin_unreachable is non-conforming for C? ... at least in 
the English sense of "this code is impossible to reach", which implies that 
the condition leading up to it must be 'false', allowing time-travel 
optimization. Or how would C define 'unreachable'?

> But I am not sure how this is relevant here as this affects only
> observable behavior and the only case where GCC does not seem to
> already conform to this is volatile.

Now you lost me.

> Of course, C++ may be different but I suspect that some of the
> discussion is confusing compiler bugs with time-travel:

"some of the discussion" is referring to what?

> > Again, I don't believe this would be conforming to the C++ standard. But I
> > believe it's a very interesting mode to add as a compiler flag.
> > 
> > -fharden=0 (default)
> > -fharden=1 (make UB ill-formed or unreachable)
> > -fharden=2 (make UB ill-formed or trap)
> > 
> > If there's interest I'd be willing to look into a patch to libstdc++,
> > building upon the above sketch as a starting point. Ultimately, if this
> > becomes a viable build mode, I'd like to have a replacement for the
> > [[gnu::error("")]] hack with a dedicated builtin.
> 
> -fharden should never turn this into unreachable.

Well, if the default is 'unreachable' and the next step is 'ill-formed or 
unreachable' it's a step up. But I'm all for a better name.

> IMHO the FEs should insert the conditional traps when requested to
> and the middle end could then treat it as UB and more freely
> decide what to do.

Right I was thinking of turning my library-solution hack into a builtin (if it 
shows potential). The behavior of which then depends on a compiler flag. Then 
both library and language UB could invoke that builtin. E.g. 'operator+(int, 
int)' would add '__check_precondition(not __builtin_add_overflow_p(a, b, a));'
With my proposed '-fharden=1 -O2' you'd then get a compilation error on 
'0x7fff'ffff + 1', but no code size increase for all other additions. With 
'-fharden=2 -O2' the 'lea' would turn into an actual 'add' instruction with 
subsequent 'jo' to 'ud2' (on x86).

> Also IMHO this should be split up from
> UBsan which has specific semantics and upstream dependencies
> which are are not always ideal.  (But UBSan could share the
> same infrastructure)

I'm not sure what you're thinking of here. UBsan detects UB at runtime whereas 
my '-fharden=1' proposal is about flagging UB as ill-formed on compile-time. 
So UBsan is a more verbose '-fharden=2' then?

- Matthias

-- 
──────────────────────────────────────────────────────────────────────────
 Dr. Matthias Kretz                           https://mattkretz.github.io
 GSI Helmholtz Center for Heavy Ion Research               https://gsi.de
 std::simd
──────────────────────────────────────────────────────────────────────────

[-- Attachment #2: This is a digitally signed message part. --]
[-- Type: application/pgp-signature, Size: 488 bytes --]

Re: IFNDR on UB? [was: Straw poll on shifts with out of range operands]

[Martin Uecker]

Am Sonntag, dem 30.06.2024 um 05:03 +0200 schrieb Matthias Kretz:
> On Saturday, 29 June 2024 16:20:55 GMT+2 Martin Uecker wrote:
> > Am Samstag, dem 29.06.2024 um 08:50 -0500 schrieb Matthias Kretz via Gcc:
> > > I.e. once UB becomes IFNDR, the dreaded time-travel optimizations can't
> > > happen anymore. Instead precondition checks bubble up because otherwise
> > > the program is ill-formed.
> > 
> > It is not clear to mean what you mean by this?
> 
> It would help if you could point out what is unclear to you. I assume you know 
> IFNDR? And I gave an example for the "bubbling up" of precondition checks 
> directly above your quoted paragraph.

I think I understood it now:  You want to make UB be IFNDR so
that the compiler is allowed to diagnose it at translation
time in certain cases (although this would not generally be
required for IFNDR).

> 
> > Note that in C time-travel optimizations are already not allowed.
> 
> Then, calling __builtin_unreachable is non-conforming for C? ... at least in 
> the English sense of "this code is impossible to reach", which implies that 
> the condition leading up to it must be 'false', allowing time-travel 
> optimization. Or how would C define 'unreachable'?

__builtin_uneachable is an extension, it can do whatever it wants.

But note that compilers do not seem to eliminate the control flow path
leading to it:


https://godbolt.org/z/coq9Yra1j

So even if it is defined in terms of C's UB, these implementations
would still be conforming to C.

> 
> > But I am not sure how this is relevant here as this affects only
> > observable behavior and the only case where GCC does not seem to
> > already conform to this is volatile.
> 
> Now you lost me.

Consider the following example:

int f(int x)
{
 int r = 0;
 if (x < 10)
   r = 1;
 if (x < 10)
   __builtin_unreachable();
 return r;
}

But removing the store to 'r' here as GCC does:

https://godbolt.org/z/h7qqrGsbz

can simply be justified by the "as if" principle as
any other optimization, it does not need to rely on a weird
intepretation that the UB from __builin_unreachable() travels
back in time.

> 
> > Of course, C++ may be different but I suspect that some of the
> > discussion is confusing compiler bugs with time-travel:
> 
> "some of the discussion" is referring to what?

To discussions inside WG21 that seems to believe that it
is important that compilers can do  time-travel optimizations,
when this is actually not the case.

> 
> > > Again, I don't believe this would be conforming to the C++ standard. But I
> > > believe it's a very interesting mode to add as a compiler flag.
> > > 
> > > -fharden=0 (default)
> > > -fharden=1 (make UB ill-formed or unreachable)
> > > -fharden=2 (make UB ill-formed or trap)
> > > 
> > > If there's interest I'd be willing to look into a patch to libstdc++,
> > > building upon the above sketch as a starting point. Ultimately, if this
> > > becomes a viable build mode, I'd like to have a replacement for the
> > > [[gnu::error("")]] hack with a dedicated builtin.
> > 
> > -fharden should never turn this into unreachable.
> 
> Well, if the default is 'unreachable' and the next step is 'ill-formed or 
> unreachable' it's a step up. But I'm all for a better name.

I think it is a good idea. The compiler can optionally treat UB as
a translation time error. We discussed similar ideas in the past
in WG14. But this will only work for very specific instances of UB
under certain conditions.

> 
> > IMHO the FEs should insert the conditional traps when requested to
> > and the middle end could then treat it as UB and more freely
> > decide what to do.
> 
> Right I was thinking of turning my library-solution hack into a builtin (if it 
> shows potential). The behavior of which then depends on a compiler flag. Then 
> both library and language UB could invoke that builtin. E.g. 'operator+(int, 
> int)' would add '__check_precondition(not __builtin_add_overflow_p(a, b, a));'
> With my proposed '-fharden=1 -O2' you'd then get a compilation error on 
> '0x7fff'ffff + 1', but no code size increase for all other additions. With 
> '-fharden=2 -O2' the 'lea' would turn into an actual 'add' instruction with 
> subsequent 'jo' to 'ud2' (on x86).

Yes, I fully agree with this.  
> 
> > Also IMHO this should be split up from
> > UBsan which has specific semantics and upstream dependencies
> > which are are not always ideal.  (But UBSan could share the
> > same infrastructure)
> 
> I'm not sure what you're thinking of here. UBsan detects UB at runtime whereas 
> my '-fharden=1' proposal is about flagging UB as ill-formed on compile-time. 
> So UBsan is a more verbose '-fharden=2' then?

Yes, I was talking about the -fharden=2 case. In principle UBSan
with traps instead of diagnostics would do this. In practice,
I think we need something which is not tied to UBSan.

Martin


> 
> - Matthias
> 

Re: IFNDR on UB? [was: Straw poll on shifts with out of range operands]

[Martin Uecker]

Actually, it is very much aligned with what I want in C.
In general I want to have pragma-based compilation modes
for memory safety:

https://www.open-std.org/jtc1/sc22/wg14/www/docs/n3211.pdf

(Bjarne Stroustrup has a proposal for profiles in C++ which
goes in similar direction I think)

From an implementation point of view, if we annotated all
operations with UB in the front ends with a new

__builtin_undefined()

that - depending on configuration and/or mode - does:

0) nothing
1) expands to __builtin_unreachable()
2) expands to __builtin_trap()  
3) expands to a __builtin_warning (as suggested before
by Martin Sebor) that causes the backend to emit an error
in a very late pass when the __builtin_warning has not
been removed during optimization.

Then this would solve all my problems related to UB.

Martin

Am Sonntag, dem 30.06.2024 um 08:33 +0200 schrieb Martin Uecker via Gcc:
> Am Sonntag, dem 30.06.2024 um 05:03 +0200 schrieb Matthias Kretz:
> > On Saturday, 29 June 2024 16:20:55 GMT+2 Martin Uecker wrote:
> > > Am Samstag, dem 29.06.2024 um 08:50 -0500 schrieb Matthias Kretz via Gcc:
> > > > I.e. once UB becomes IFNDR, the dreaded time-travel optimizations can't
> > > > happen anymore. Instead precondition checks bubble up because otherwise
> > > > the program is ill-formed.
> > > 
> > > It is not clear to mean what you mean by this?
> > 
> > It would help if you could point out what is unclear to you. I assume you know 
> > IFNDR? And I gave an example for the "bubbling up" of precondition checks 
> > directly above your quoted paragraph.
> 
> I think I understood it now:  You want to make UB be IFNDR so
> that the compiler is allowed to diagnose it at translation
> time in certain cases (although this would not generally be
> required for IFNDR).
> 
> > 
> > > Note that in C time-travel optimizations are already not allowed.
> > 
> > Then, calling __builtin_unreachable is non-conforming for C? ... at least in 
> > the English sense of "this code is impossible to reach", which implies that 
> > the condition leading up to it must be 'false', allowing time-travel 
> > optimization. Or how would C define 'unreachable'?
> 
> __builtin_uneachable is an extension, it can do whatever it wants.
> 
> But note that compilers do not seem to eliminate the control flow path
> leading to it:
> 
> 
> https://godbolt.org/z/coq9Yra1j
> 
> So even if it is defined in terms of C's UB, these implementations
> would still be conforming to C.
> 
> > 
> > > But I am not sure how this is relevant here as this affects only
> > > observable behavior and the only case where GCC does not seem to
> > > already conform to this is volatile.
> > 
> > Now you lost me.
> 
> Consider the following example:
> 
> int f(int x)
> {
>  int r = 0;
>  if (x < 10)
>    r = 1;
>  if (x < 10)
>    __builtin_unreachable();
>  return r;
> }
> 
> But removing the store to 'r' here as GCC does:
> 
> https://godbolt.org/z/h7qqrGsbz
> 
> can simply be justified by the "as if" principle as
> any other optimization, it does not need to rely on a weird
> intepretation that the UB from __builin_unreachable() travels
> back in time.
> 
> > 
> > > Of course, C++ may be different but I suspect that some of the
> > > discussion is confusing compiler bugs with time-travel:
> > 
> > "some of the discussion" is referring to what?
> 
> To discussions inside WG21 that seems to believe that it
> is important that compilers can do  time-travel optimizations,
> when this is actually not the case.
> 
> > 
> > > > Again, I don't believe this would be conforming to the C++ standard. But I
> > > > believe it's a very interesting mode to add as a compiler flag.
> > > > 
> > > > -fharden=0 (default)
> > > > -fharden=1 (make UB ill-formed or unreachable)
> > > > -fharden=2 (make UB ill-formed or trap)
> > > > 
> > > > If there's interest I'd be willing to look into a patch to libstdc++,
> > > > building upon the above sketch as a starting point. Ultimately, if this
> > > > becomes a viable build mode, I'd like to have a replacement for the
> > > > [[gnu::error("")]] hack with a dedicated builtin.
> > > 
> > > -fharden should never turn this into unreachable.
> > 
> > Well, if the default is 'unreachable' and the next step is 'ill-formed or 
> > unreachable' it's a step up. But I'm all for a better name.
> 
> I think it is a good idea. The compiler can optionally treat UB as
> a translation time error. We discussed similar ideas in the past
> in WG14. But this will only work for very specific instances of UB
> under certain conditions.
> 
> > 
> > > IMHO the FEs should insert the conditional traps when requested to
> > > and the middle end could then treat it as UB and more freely
> > > decide what to do.
> > 
> > Right I was thinking of turning my library-solution hack into a builtin (if it 
> > shows potential). The behavior of which then depends on a compiler flag. Then 
> > both library and language UB could invoke that builtin. E.g. 'operator+(int, 
> > int)' would add '__check_precondition(not __builtin_add_overflow_p(a, b, a));'
> > With my proposed '-fharden=1 -O2' you'd then get a compilation error on 
> > '0x7fff'ffff + 1', but no code size increase for all other additions. With 
> > '-fharden=2 -O2' the 'lea' would turn into an actual 'add' instruction with 
> > subsequent 'jo' to 'ud2' (on x86).
> 
> Yes, I fully agree with this.  
> > 
> > > Also IMHO this should be split up from
> > > UBsan which has specific semantics and upstream dependencies
> > > which are are not always ideal.  (But UBSan could share the
> > > same infrastructure)
> > 
> > I'm not sure what you're thinking of here. UBsan detects UB at runtime whereas 
> > my '-fharden=1' proposal is about flagging UB as ill-formed on compile-time. 
> > So UBsan is a more verbose '-fharden=2' then?
> 
> Yes, I was talking about the -fharden=2 case. In principle UBSan
> with traps instead of diagnostics would do this. In practice,
> I think we need something which is not tied to UBSan.
> 
> Martin
> 
> 
> > 
> > - Matthias
> > 
>