Request of new __attribute__ for switch statements (elimination of the bounds check)

Request of new __attribute__ for switch statements (elimination of the bounds check)

[Kevin Lawton]

All,

For implementation of machine simulators, it's quite common
to have completely populated switch statements on byte values:

  unsigned char byte;

  switch (byte) {
    case 0:
    case 1:
    ...
    case 255:
    }

But I don't know of any way to tell the compiler to _not_ generate
a bounds check on the switch variable 'byte'.  All of the target
space is covered.

To solve this, could we add an attribute to switch?

  switch (byte) __attribute (( no-bounds-check )) {
    ...
    }

This would also be useful for cases, where it is known that
all possible targets are covered with case statements, yet
they don't appear to be fully populated to the compiler
(it's known only to the programmer that the logic prevents
certain values).

Thanks,
-Kevin

__________________________________________________
Do you Yahoo!?
New DSL Internet Access from SBC & Yahoo!
http://sbc.yahoo.com

Re: Request of new __attribute__ for switch statements (elimination of the bounds check)

[Ralph Loader]

A more general feature would be a __builtin_not_reached() that informs
the compiler that a particular code path will never be executed and can
be removed at compile time.

Then the example below could be achieved by adding 

   default: __builtin_not_reached();

to the switch statement.

Ralph.

On Sat, 2002-10-12 at 08:05, Kevin Lawton wrote:
> All,
> 
> For implementation of machine simulators, it's quite common
> to have completely populated switch statements on byte values:
> 
>   unsigned char byte;
> 
>   switch (byte) {
>     case 0:
>     case 1:
>     ...
>     case 255:
>     }
> 
> But I don't know of any way to tell the compiler to _not_ generate
> a bounds check on the switch variable 'byte'.  All of the target
> space is covered.
> 
> To solve this, could we add an attribute to switch?
> 
>   switch (byte) __attribute (( no-bounds-check )) {
>     ...
>     }
> 
> This would also be useful for cases, where it is known that
> all possible targets are covered with case statements, yet
> they don't appear to be fully populated to the compiler
> (it's known only to the programmer that the logic prevents
> certain values).
> 
> Thanks,
> -Kevin
> 
> __________________________________________________
> Do you Yahoo!?
> New DSL Internet Access from SBC & Yahoo!
> http://sbc.yahoo.com
> 

Re: Request of new __attribute__ for switch statements (elimination of the bounds check)

[Richard Zidlicky]

On Fri, Oct 11, 2002 at 12:05:21PM -0700, Kevin Lawton wrote:
> All,
> 
> For implementation of machine simulators, it's quite common
> to have completely populated switch statements on byte values:
> 
>   unsigned char byte;
> 
>   switch (byte) {
>     case 0:
>     case 1:
>     ...
>     case 255:
>     }
> 
> But I don't know of any way to tell the compiler to _not_ generate
> a bounds check on the switch variable 'byte'.  All of the target
> space is covered.

did you look into using gcc's computed goto? 

Richard

Re: Request of new __attribute__ for switch statements (elimination of the bounds check)

[Dale Johannesen]

>> For implementation of machine simulators, it's quite common
>> to have completely populated switch statements on byte values:
>>
>>   unsigned char byte;
>>
>>   switch (byte) {
>>     case 0:
>>     case 1:
>>     ...
>>     case 255:
>>     }
>>
>> But I don't know of any way to tell the compiler to _not_ generate
>> a bounds check on the switch variable 'byte'.  All of the target
>> space is covered.

There is a value-range-propagation branch that will do it.  Comes at a
considerable cost in compile time though.

Re: Request of new __attribute__ for switch statements (elimination of the bounds check)

[Jamie Lokier]

I would prefer to have an attribute on enumurated types that says a
value of that type is always one of the enum values:

  enum __attribute__ ((strict_enum)) { CAT, FISH, RABBIT } Pet;

(It would be appropriate to add a warning when an enum with this
attribute is converted to an integer).

Then any switch statement, without adornment, would be able to assume
a value of that type is in the range.  _If_ every enum label is
mentioned in the switch, there is no need for the bounds check.  (GCC
already checks enum labels in a switch if `-Wswitch' is used, which
may be helpful).

There would be no bounds in check in code like this:

  Pet my_pet;
  /* ... */
  switch (my_pet) {
    case CAT:    /* ... */
    case FISH:   /* ... */
    case RABBIT: /* ... */
  }

The reason I like this is that this attribute could improve the
performance of the many programs which use enums, while keeping the
GCC-specific attribute in the place where it is least intrusive.
Also, many more programs _could_ be changed easily to use enums in
place of #defines, and it would be nice to offer a potential
performance enhancement for those programs too.

You can use this attribute to achieve Kevin's goal of faster threaded
interpretation, but it is a bit ugly.  For a byte-code dispatch, you'd
have to define an enum with 256 scratch names, and cast your byte to
that type in the switch.  For a sparse dispatch, you'd have to use a
different enum type.  It's a bit ugly but might be ok with macros.

Anyway, I prefer the enum attribute simply because it is useful for
many programs in a way which is doesn't intrude on most of the code,
i.e. there are usually more switch statements than type definitions.
E.g. GCC itself could benefit (lots of switch statements there!).

enjoy,
-- Jamie

Re: Request of new __attribute__ for switch statements (elimination of the bounds check)

[Zack Weinberg]

On Tue, Oct 15, 2002 at 02:41:01AM +0100, Jamie Lokier wrote:
> I would prefer to have an attribute on enumurated types that says a
> value of that type is always one of the enum values:
> 
>   enum __attribute__ ((strict_enum)) { CAT, FISH, RABBIT } Pet;
> 
> (It would be appropriate to add a warning when an enum with this
> attribute is converted to an integer).
> 
> Then any switch statement, without adornment, would be able to assume
> a value of that type is in the range.  _If_ every enum label is
> mentioned in the switch, there is no need for the bounds check.  (GCC
> already checks enum labels in a switch if `-Wswitch' is used, which
> may be helpful).

If there is an enumerated type that doesn't exhaust the domain of its
underlying integral type, then I confidently expect that a data
corruption bug will cause the switch to receive a selector outside the
domain of the enumeration; in that case I want there to be a
default:abort() in there so it gets caught early.

This does not mean that your idea is a bad one; the attribute could be
used for stricter type checking and more effective warnings, which is
a good thing.  I just don't like the idea of using it to optimize out
bounds checks.  (Instead, how about transforming your example

>   Pet my_pet;
>   /* ... */
>   switch (my_pet) {
>     case CAT:    /* ... */
>     case FISH:   /* ... */
>     case RABBIT: /* ... */
>   }

by inserting the default:abort() for the programmer?)

> You can use this attribute to achieve Kevin's goal of faster threaded
> interpretation, but it is a bit ugly.  For a byte-code dispatch, you'd
> have to define an enum with 256 scratch names, and cast your byte to
> that type in the switch.  For a sparse dispatch, you'd have to use a
> different enum type.  It's a bit ugly but might be ok with macros.

I would far rather solve this problem by having us notice when a
dispatch switch() really has exhausted the domain of the integral
type of its argument (before conversion to int).

zw

Re: Request of new __attribute__ for switch statements (elimination of the bounds check)

[Michael Matz]

Hi,

On Tue, 15 Oct 2002, Jamie Lokier wrote:

> [... strict enum proposal ...]
>
> (It would be appropriate to add a warning when an enum with this
> attribute is converted to an integer).

That's not the problematic direction.  I can't see why converting such an
enum to an integer would be dangerous.  But converting _to_ such an enum
should get a warning.


Ciao,
Michael.

Re: Request of new __attribute__ for switch statements (elimination of the bounds check)

[Michael Matz]

Hi,

On Mon, 14 Oct 2002, Zack Weinberg wrote:

> If there is an enumerated type that doesn't exhaust the domain of its
> underlying integral type, then I confidently expect that a data
> corruption bug will cause the switch to receive a selector outside the
> domain of the enumeration; in that case I want there to be a
> default:abort() in there so it gets caught early.

Well, if you have data corruption, hmm, well, you're screwed ;-)  The same
happens, when you access a pointer retrieved from corrupted memory.

> This does not mean that your idea is a bad one; the attribute could be
> used for stricter type checking and more effective warnings, which is
> a good thing.  I just don't like the idea of using it to optimize out
> bounds checks.

Why not?  Possibility for data corruption is no argument for not doing
things.  Remember also, that there are other syntactic means to enable
certain optimizations, 'restrict' or __builtin_expect for example.

>  (Instead, how about transforming your example
>
> >   Pet my_pet;
> >   /* ... */
> >   switch (my_pet) {
> >     case CAT:    /* ... */
> >     case FISH:   /* ... */
> >     case RABBIT: /* ... */
> >   }
>
> by inserting the default:abort() for the programmer?)

That's possible too.  This behaviour could be even conditionalized on
optimization level.  So that -O0 would insert the abort() and higher ones
would optimize better (this anyway is already partially done, because
branches leading to calls of abort() type are given very low probability).

> > You can use this attribute to achieve Kevin's goal of faster threaded
> > interpretation, but it is a bit ugly.  For a byte-code dispatch, you'd
> > have to define an enum with 256 scratch names, and cast your byte to
> > that type in the switch.  For a sparse dispatch, you'd have to use a
> > different enum type.  It's a bit ugly but might be ok with macros.
>
> I would far rather solve this problem by having us notice when a
> dispatch switch() really has exhausted the domain of the integral
> type of its argument (before conversion to int).

Of course.  For the case at hand (the exhaustive switch on char) this nice
feature would be overkill.


Ciao,
Michael.

Re: Request of new __attribute__ for switch statements (elimination of the bounds check)

[Jamie Lokier]

Michael Matz wrote:
> On Tue, 15 Oct 2002, Jamie Lokier wrote:
> > [... strict enum proposal ...]
> >
> > (It would be appropriate to add a warning when an enum with this
> > attribute is converted to an integer).
> 
> That's not the problematic direction.  I can't see why converting such an
> enum to an integer would be dangerous.  But converting _to_ such an enum
> should get a warning.

Good point.  (I was thinking of enum arithmetic like `CAT | DOG' being
disallowed for strict enums -- I believe that is defined for standard enums).

-- Jamie

Re: Request of new __attribute__ for switch statements (elimination of the bounds check)

[Kevin Lawton]

For the most efficient solution here, if one could
narrow down to being compiled only on GCC, I'd use
computed gotos.  This gets rid of the limit check altogether
and let's me calculate the branch address as early as
possible to optimize the CPU's speculation.  The compiler
may be able to do some of this however.

But the real issue is in trying to play nice with non-GCC
compilers.  If whatever solution implemented, requires
anything extensions other than something that can
disappear easily with a macro (like the __attribute__ directives
can), then nothing has been solved.

The __attibute_ angle is simple, I can exactly tell the
compiler when I care to have it applied (maybe only one
case in all the code), and it disappears quickly with
an #ifdef'd macro.  Which makes it play nice with "other"
compilers.

-Kevin

--- Jamie Lokier <egcs@tantalophile.demon.co.uk> wrote:
> Michael Matz wrote:
> > On Tue, 15 Oct 2002, Jamie Lokier wrote:
> > > [... strict enum proposal ...]
> > >
> > > (It would be appropriate to add a warning when an enum with this
> > > attribute is converted to an integer).
> > 
> > That's not the problematic direction.  I can't see why converting such an
> > enum to an integer would be dangerous.  But converting _to_ such an enum
> > should get a warning.
> 
> Good point.  (I was thinking of enum arithmetic like `CAT | DOG' being
> disallowed for strict enums -- I believe that is defined for standard enums).
> 
> -- Jamie


__________________________________________________
Do you Yahoo!?
New DSL Internet Access from SBC & Yahoo!
http://sbc.yahoo.com

Re: Request of new __attribute__ for switch statements (elimination of the bounds check)

[Michael Matz]

Hi,

On Tue, 15 Oct 2002, Jamie Lokier wrote:

> > > (It would be appropriate to add a warning when an enum with this
> > > attribute is converted to an integer).
> >
> > That's not the problematic direction.  I can't see why converting such an
> > enum to an integer would be dangerous.  But converting _to_ such an enum
> > should get a warning.
>
> Good point.  (I was thinking of enum arithmetic like `CAT | DOG' being
> disallowed for strict enums -- I believe that is defined for standard enums).

For the type system I would use the following argumentation (biased to C
not C++):  First observe that strict enum are not an integer type (in
difference to normal ISO C enums), but can be implicitely converted to
one.  Additionally strict enum shall not be arithmetic types (makes sense,
because we want to disallow arithmetics on this thing). Per 6.5.x (the
definitions of the different operators) all interesting operators operate
on arithmetic types.  Ergo the only way to interpret 'BLA | BLUBB' is,
that both strict enums are (implicitely) converted to an integer type,
which makes the whole expression have integer type.  That is you could
write: "unsigned int x = BLA | BLUBB;" without a warning, and I think
that's Ok.  What you _can't_ do then is "enum E_strict e = BLA | BLUBB;"
because the RHS arithmetic expression can't be implicitely converted to an
E_strict.  One would need an explicit cast, and that should get a warning.

Does that make sense?


Ciao,
Michael.

Re: Request of new __attribute__ for switch statements (elimination of the bounds check)

[Jamie Lokier]

Michael Matz wrote:
> Does that make sense?

Yes it does.

cheers,
-- Jamie

Re: Request of new __attribute__ for switch statements (elimination of the bounds check)

[Jamie Lokier]

Kevin Lawton wrote:
> The __attibute_ angle is simple, I can exactly tell the
> compiler when I care to have it applied (maybe only one
> case in all the code), and it disappears quickly with
> an #ifdef'd macro.  Which makes it play nice with "other"
> compilers.

If your proposal is actually implemented, could it please be changed
so that the attribute goes _inside_ the switch parentheses?

Then it can be used to optimise "variant type" macros without having
to uglify thousands of switch statements in a program (just the macro
definitions).  To use a few example from GCC itself, these kind of
can all be optimised in this way:

    switch (TREE_CODE (t)) { /* ... */ }
    switch (GET_CODE (rtx)) { /* ... */ }
    switch (GET_MODE (rtx)) { /* ... */ }

(I'm not sure you'd want to optimise these in GCC because of the risk
of bugs, but there are programs which use similar macros where it is
more desirable to optimise).

-- Jamie

Re: Request of new __attribute__ for switch statements (elimination of the bounds check)

[Zack Weinberg]

On Tue, Oct 15, 2002 at 04:32:34PM +0200, Michael Matz wrote:
> Well, if you have data corruption, hmm, well, you're screwed ;-)  The same
> happens, when you access a pointer retrieved from corrupted memory.

Sure.  The question is how _soon_ you will be screwed to the point
that the program crashes.  Ideally this happens as soon after the
actual data corruption event as possible.

(If I had a nickel for every time I've wanted a "step backward"
command in gdb...)

> > This does not mean that your idea is a bad one; the attribute could be
> > used for stricter type checking and more effective warnings, which is
> > a good thing.  I just don't like the idea of using it to optimize out
> > bounds checks.
> 
> Why not?  Possibility for data corruption is no argument for not doing
> things.  Remember also, that there are other syntactic means to enable
> certain optimizations, 'restrict' or __builtin_expect for example.

It's just that I see removing the bounds checks on a switch statement
as a marginal optimization compared to the risk.  I've never seen a
switch be the bottleneck in anything.

Your mileage may vary.

zw

Re: Request of new __attribute__ for switch statements (elimination of the bounds check)

[Dale Johannesen]

On Tuesday, October 15, 2002, at 05:49  PM, Zack Weinberg wrote:
> It's just that I see removing the bounds checks on a switch statement
> as a marginal optimization compared to the risk.  I've never seen a
> switch be the bottleneck in anything.

I have.  However, it was a switch on (x&7) with 8 cases, not an enum.
I do not think new syntax is the right way to fix this case, which
demonstrates an optimizer deficiency.

Re: Request of new __attribute__ for switch statements (elimination of the bounds check)

[Kevin Lawton]

--- Zack Weinberg <zack@codesourcery.com> wrote:

> Sure.  The question is how _soon_ you will be screwed to the point
> that the program crashes.  Ideally this happens as soon after the
> actual data corruption event as possible.

The question is, will the compiler allow a coder to
eliminate the check or not.  The idea is that a coder
may have confidence in the case targets.  Thinking
past that doesn't solve anything.

If we wanted to stop people from shooting theirselves
in the feet, we wouldn't allow them to use C.  At
any rate, sometimes it's even possible to prove the
case targets are populated:

  switch (a & 0x3) {
    case 0: ...
    case 1: ...
    case 2: ...
    case 3: ...
    }

This is a request for a feature for high performance programs.
Basically, I want to be able to make my own decisions because
the compiler is too brain dead to.


> It's just that I see removing the bounds checks on a switch statement
> as a marginal optimization compared to the risk.  I've never seen a
> switch be the bottleneck in anything.

Listen, when you do it 10 million times a second, you start caring.

There's nothing marginal about it.  If people don't want to
use extensions, they shouldn't.  I see it as really that
simple.

-Kevin

__________________________________________________
Do you Yahoo!?
New DSL Internet Access from SBC & Yahoo!
http://sbc.yahoo.com

Re: Request of new __attribute__ for switch statements (elimination of the bounds check)

[Tim Hollebeek]

On Tue, Oct 15, 2002 at 06:38:10PM -0700, Kevin Lawton wrote:
> 
> --- Zack Weinberg <zack@codesourcery.com> wrote:
> 
> > Sure.  The question is how _soon_ you will be screwed to the point
> > that the program crashes.  Ideally this happens as soon after the
> > actual data corruption event as possible.
> 
[snip]
> 
> If we wanted to stop people from shooting theirselves
> in the feet, we wouldn't allow them to use C.  At
> any rate, sometimes it's even possible to prove the
> case targets are populated:
> 
>   switch (a & 0x3) {

then ask for the compiler to understand and DTRT with this syntax,
instead of some funky attribute.

Sure, recognizing "switch ((expr) & (integral constant 2^n-1))" only
works for tables that are powers of two, but I suspect that would
already go quite a ways towards what many people need.

BTW, the "if you don't like the extension, don't use it" argument
doesn't wash.  Extensions have a non-trivial maintenance burden that
has to be supported by the gcc development team, and that's a far more
valuable resource than a few cycles in a few people's code.

Re: Request of new __attribute__ for switch statements (elimination of the bounds check)

[Joseph S. Myers]

On Tue, 15 Oct 2002, Zack Weinberg wrote:

> (If I had a nickel for every time I've wanted a "step backward"
> command in gdb...)

<http://www.uwsg.iu.edu/hypermail/linux/kernel/9901.2/0531.html>:

#  I have enough information available in the proxy ptrace filter to
#  implement PTRACE_SINGLESTEP_BACKWARDS. How would you like to have that
#  capability in gdb? "Execute backwards until this data watchpoint
#  changes." Imagine a graphical debugger with a scrollbar for time,
#  where the top is "beginning of execution" and the bottom is "end of
#  execution."

(AFAIK there still isn't a useful "step backwards" capability based on
this technology.)

-- 
Joseph S. Myers
jsm28@cam.ac.uk

Re: Request of new __attribute__ for switch statements (elimination of the bounds check)

[Michael Matz]

Hi,

On Tue, 15 Oct 2002, Tim Hollebeek wrote:

> > If we wanted to stop people from shooting theirselves
> > in the feet, we wouldn't allow them to use C.  At
> > any rate, sometimes it's even possible to prove the
> > case targets are populated:
> >
> >   switch (a & 0x3) {
>
> then ask for the compiler to understand and DTRT with this syntax,
> instead of some funky attribute.

Although remember that we have two cases in this thread.  Things like
fully populated "switch (a & A_CONSTANT)" or "switch (a_char)", which
clearly should be optimized by the compiler itself without syntantic help.

And that "switch (an_enum)" thing, also "fully populated" in the sense
that all enumeration values are mentioned.  But due to the definition of
C/C++ this isn't fully populated, because an enum variable is equivalent
to a var of it's base int type, and can hold values without a name.  For
that we would need a syntactic mean to differentiate between standard
enums (named int constants) and real ones (a set).


Ciao,
Michael.

Re: Request of new __attribute__ for switch statements (elimination of the bounds check)

[Fergus Henderson]

On 16-Oct-2002, Joseph S. Myers <jsm28@cam.ac.uk> wrote:
> On Tue, 15 Oct 2002, Zack Weinberg wrote:
> 
> > (If I had a nickel for every time I've wanted a "step backward"
> > command in gdb...)
> 
> <http://www.uwsg.iu.edu/hypermail/linux/kernel/9901.2/0531.html>:

FWIW, Mercury and Ocaml both have debuggers that support backwards execution.
It is certainly a very useful feature.

-- 
Fergus Henderson <fjh@cs.mu.oz.au>  |  "I have always known that the pursuit
The University of Melbourne         |  of excellence is a lethal habit"
WWW: <http://www.cs.mu.oz.au/~fjh>  |     -- the last words of T. S. Garp.

Re: Request of new __attribute__ for switch statements (elimination of the bounds check)

[Daniel Jacobowitz]

On Wed, Oct 16, 2002 at 09:23:40AM +0100, Joseph S. Myers wrote:
> On Tue, 15 Oct 2002, Zack Weinberg wrote:
> 
> > (If I had a nickel for every time I've wanted a "step backward"
> > command in gdb...)
> 
> <http://www.uwsg.iu.edu/hypermail/linux/kernel/9901.2/0531.html>:
> 
> #  I have enough information available in the proxy ptrace filter to
> #  implement PTRACE_SINGLESTEP_BACKWARDS. How would you like to have that
> #  capability in gdb? "Execute backwards until this data watchpoint
> #  changes." Imagine a graphical debugger with a scrollbar for time,
> #  where the top is "beginning of execution" and the bottom is "end of
> #  execution."
> 
> (AFAIK there still isn't a useful "step backwards" capability based on
> this technology.)

Well, it can be a bogglingly hard computational problem to do this in
any program which does significant computation. From what I can see
this works by recording the state of the program at system calls and
the effects of system calls on the process.

One downside of using this information for step-backwards would be,
you'd need to replay from the last syscall checkpoint up to the point
you want to step backwards from.  Which would probably involve keeping
a tremendous amount of data (in order to know what memory looked like
at the last checkpoint) and working out the effect of a possibly large
number of instructions since that last syscall point.

Also note that it says it doesn't support signals or shared memory. 
They break the complete-control model that it uses to run replays.  I
suspect it has problems with a lot of recent forms of IPC, too.

I've got to give Michael credit, this is an amazing hack he put
together.  I don't know that it scales in the modern world, though.

-- 
Daniel Jacobowitz
MontaVista Software                         Debian GNU/Linux Developer

Re: Request of new __attribute__ for switch statements (elimination of the bounds check)

[Hartmut Schirmer]

> "Tim Hollebeek"  wrote:
> On Tue, Oct 15, 2002 at 06:38:10PM -0700, Kevin Lawton wrote:
> >
> > --- Zack Weinberg <zack@codesourcery.com> wrote:
> >
> > > Sure.  The question is how _soon_ you will be screwed to the point
> > > that the program crashes.  Ideally this happens as soon after the
> > > actual data corruption event as possible.
> >
> [snip]
> >
> > If we wanted to stop people from shooting theirselves
> > in the feet, we wouldn't allow them to use C.  At
> > any rate, sometimes it's even possible to prove the
> > case targets are populated:
> >
> >   switch (a & 0x3) {
>
> then ask for the compiler to understand and DTRT with this syntax,
> instead of some funky attribute.
>
> Sure, recognizing "switch ((expr) & (integral constant 2^n-1))" only
> works for tables that are powers of two, but I suspect that would
> already go quite a ways towards what many people need.

Other nice things to have:
- warn about unreachable case values
- removed unreachable code

gcc need not be perfect on this. Just checking easy available
properties of  the switch value would be a great help.

Hartmut

Re: Request of new __attribute__ for switch statements (elimination of the bounds check)

[Tim Hollebeek]

> > >   switch (a & 0x3) {
> >
> > then ask for the compiler to understand and DTRT with this syntax,
> > instead of some funky attribute.
> 
> Although remember that we have two cases in this thread.  Things like
> fully populated "switch (a & A_CONSTANT)" or "switch (a_char)", which
> clearly should be optimized by the compiler itself without syntantic help.
> 
> And that "switch (an_enum)" thing, also "fully populated" in the sense
> that all enumeration values are mentioned.

Cases like that that are performance critical, not a factor of two,
and cannot be expanded to a factor of two?  I don't buy it.

Remember, we already have -Wswitch, and default: abort(), which are
adequate for all but the most performance intensive cases.

-Tim

Re: Request of new __attribute__ for switch statements (elimination of the bounds check)

[Richard Henderson]

On Tue, Oct 15, 2002 at 06:02:30PM -0700, Dale Johannesen wrote:
> I have.  However, it was a switch on (x&7) with 8 cases, not an enum.
> I do not think new syntax is the right way to fix this case, which
> demonstrates an optimizer deficiency.

I agree.  And it does seem like we shouldn't need VRP to handle
the cases where a small type or a range-limiting operation (such
as & or %) is used in the switch selector directly.


r~

Re: Request of new __attribute__ for switch statements (elimination of the bounds check)

[Michael Matz]

Hi,

On Wed, 16 Oct 2002, Tim Hollebeek wrote:

> > And that "switch (an_enum)" thing, also "fully populated" in the sense
> > that all enumeration values are mentioned.
>
> Cases like that that are performance critical, not a factor of two,
> and cannot be expanded to a factor of two?  I don't buy it.

Why should they have to be expanded to ^2?  That's also syntactic sugar
(because semantically not needed), and doesn't express exactly what one
wants (which is a real set of values), besides cluttering up the switch
statement (consider an "enum {BASE=0, OTHER=0x7fff};" which strictly would
need to check two values only, whereas with your work-around would need to
check 0x8000 of them).  The extension of strict enums would not have
application _only_ in optimizations but also in type checking.

> Remember, we already have -Wswitch, and default: abort(), which are

"default: abort()" is an even more hidden hint for optimization than an
explicit attribute on an enum to be strict.  That also can be used for
optimization hint, but isn't quite like not having a default case at all
(after all if you write "default: abort();" that's only a hint to the
compiler that this case is extremely unlikely, whereas with an strict enum
you ensure to the compiler, that non-enumerated values are _impossible_).

> adequate for all but the most performance intensive cases.

Sure, but I don't see, how such a meta type (strict enums) is useless, as
language mean _and_ as optimization hint.  C IMHO actually lacks a real
set type (it's already usefull to support one-element subset variables,
instead of fully featured subset vars like Pascal), and this extension, if
well thought out (I don't think there are too many issues) could actually
find its way to ISO C.

That having said, this strict enum proposal is just hot air unless someone
begins to implement it.  I don't know enough about the frontends to do
this currently.


Ciao,
Michael.

Re: Request of new __attribute__ for switch statements (elimination of the bounds check)

[Robert Dewar]

> FWIW, Mercury and Ocaml both have debuggers that support backwards execution.
> It is certainly a very useful feature.

The ideal form of this is hardware emulators that store the last n-thousand
bus cycles and allow reverse execution based on this trace.

Re: Request of new __attribute__ for switch statements (elimination of the bounds check)

[Zack Weinberg]

On Tue, Oct 15, 2002 at 09:41:21PM -0400, Robert Dewar wrote:
> > > It's just that I see removing the bounds checks on a switch statement
> > > as a marginal optimization compared to the risk.  I've never seen a
> > > switch be the bottleneck in anything.
> 
> I find this a remkarable attitude for a C compiler :-)
> 
> Even Ada allows the programmer to remove all checks if that is what the
> programmer wants!
> 
> After all in a safety critical program, such checks would not be permitted,
> because you simply cannot have a check that always succeeds, and whose
> failure branch is therefore deactivated code.

Good point.  I withdraw this objection.

zw

Re: Request of new __attribute__ for switch statements (elimination of the bounds check)

[Robert Dewar]

> > It's just that I see removing the bounds checks on a switch statement
> > as a marginal optimization compared to the risk.  I've never seen a
> > switch be the bottleneck in anything.

I find this a remkarable attitude for a C compiler :-)

Even Ada allows the programmer to remove all checks if that is what the
programmer wants!

After all in a safety critical program, such checks would not be permitted,
because you simply cannot have a check that always succeeds, and whose
failure branch is therefore deactivated code.

Re: Request of new __attribute__ for switch statements (elimination of the bounds check)

[Mattias Engdegård]

>There is a value-range-propagation branch that will do it.  Comes at a
>considerable cost in compile time though.

VRP, while definitely desirable for other reasons, should not be needed just
for determining that the range test for a fully populated switch can be
skipped. Even stuff like 

    switch (x & 127) { case 0: ... case 127: ... }

should not need full VRP, or am I mistaken?

Both Sun WorkShop C and Intel C understand this code right away with no extra
hints. Microsoft Visual C needs the hint __assume(0) in the default: branch,
but at least it's possible to eliminate the range test that way.

Re: Request of new __attribute__ for switch statements (elimination of the bounds check)

[Alexandre Oliva]

On Oct 11, 2002, Kevin Lawton <kevinlawton2001@yahoo.com> wrote:

> I haven't tried turning the last case into the default, but I
> can't see how that eliminates a check, so I'm not clear on the
> win there.

it (kind of) turns:

if (x == 255) goto case_255;
...
else if (x == 0) goto case_0;
else /* do nothing */;

into

if ((unsigned)x >= 255) goto case_255;
...
else if (x == 0) goto case_0;


Admittedly, this is still not as efficient as the compiler knowing
that x is in [0,255] and just loading the jump from a jump table, but
it's already some improvement.

-- 
Alexandre Oliva   Enjoy Guarana', see http://www.ic.unicamp.br/~oliva/
Red Hat GCC Developer                 aoliva@{redhat.com, gcc.gnu.org}
CS PhD student at IC-Unicamp        oliva@{lsd.ic.unicamp.br, gnu.org}
Free Software Evangelist                Professional serial bug killer

Re: Request of new __attribute__ for switch statements (elimination of the bounds check)

[Kevin Lawton]

--- Robert Dewar <dewar@gnat.com> wrote:
> <<But I don't know of any way to tell the compiler to _not_ generate
> a bounds check on the switch variable 'byte'.  All of the target
> space is covered.
> 
> To solve this, could we add an attribute to switch?
> 
>   switch (byte) __attribute (( no-bounds-check )) {
>     ...
>     }
> >>
> 
> Surely this is NOT the solution in a case when it is obvious that no
> check is needed. We have noticed this junk check being a problem in
> GNAT, and what we do is to turn the last case into a default, but this
> of course is definitely not optimial.


It may not always be easy for the compiler to know.  If GCC
could eliminate the unnecessary check for the obvious cases,
that'd be great.

But such an attribute (or whatever method you propose) is needed
when the programmer knows more about the data flow than the
compiler.  Which for high performance programs, tends to be
quite a few.

I haven't tried turning the last case into the default, but I
can't see how that eliminates a check, so I'm not clear on the
win there.

-Kevin

__________________________________________________
Do you Yahoo!?
New DSL Internet Access from SBC & Yahoo!
http://sbc.yahoo.com

Re: Request of new __attribute__ for switch statements (elimination of the bounds check)

[Robert Dewar]

<<But I don't know of any way to tell the compiler to _not_ generate
a bounds check on the switch variable 'byte'.  All of the target
space is covered.

To solve this, could we add an attribute to switch?

  switch (byte) __attribute (( no-bounds-check )) {
    ...
    }
>>

Surely this is NOT the solution in a case when it is obvious that no
check is needed. We have noticed this junk check being a problem in
GNAT, and what we do is to turn the last case into a default, but this
of course is definitely not optimial.