I have been working on a C/C++ like compiler. One feature supported in the compiler is naked switches. A naked switch omits the range checking code that is normally associated with the switch statement. Omitting this code can improve performance at the risk of a crash if invalid cases are processed. I am wondering if there is a similar option in other C compilers? Or would this just be an automatic optimization at high levels?

Normal Switch:

; switch(x) {
ldo $t0,64[$fp]
sge $t1,$t0,#1 ; x varies between 1 and 12
sle $t2,$t0,#12
and $t1,$t1,$t2
beq $t1,TestSwitch_89
sub $t0,$t0,#1
sll $t0,$t0,#4
ldo $t0,TestSwitch_116[$t0]
jmp $t0

Naked Switch
; switch(x; naked) {
ldo $t0,64[$fp]
sub $t0,$t0,#1
sll $t0,$t0,#4
ldo $t0,TestSwitch_144[$t0]
jmp $t0

On 08/07/2021 00:39, Robert Finch wrote:
> I have been working on a C/C++ like compiler. One feature supported in the compiler is naked switches. A naked switch omits the range checking code that is normally associated with the switch statement. Omitting this code can improve performance at the risk of a crash if invalid cases are processed. I am wondering if there is a similar option in other C compilers? Or would this just be an automatic optimization at high levels?
>
> Normal Switch:
>
> ; switch(x) {
> ldo $t0,64[$fp]
> sge $t1,$t0,#1 ; x varies between 1 and 12
> sle $t2,$t0,#12
> and $t1,$t1,$t2
> beq $t1,TestSwitch_89
> sub $t0,$t0,#1
> sll $t0,$t0,#4
> ldo $t0,TestSwitch_116[$t0]
> jmp $t0
>
> Naked Switch
> ; switch(x; naked) {
> ldo $t0,64[$fp]
> sub $t0,$t0,#1
> sll $t0,$t0,#4
> ldo $t0,TestSwitch_144[$t0]
> jmp $t0
>

How much faster does this make it? Because I think that when I tried it
on x64, it made no measurable difference. (Maybe the branch predictor
dealt with it.)

(On x64 also, if there are fewer than about 8 jumptable entries, it was
faster just to do sequential tests.)

Note that I do a single test, not two, after adjusting the index
expression to be 0-based which is necessary as the jumptable is biased.
So for your 1-12 range, I adjust to 0-11 and do an unsigned comparison
with 11, which is two instructions.

As to what an optimising compiler could do, it could be anything at all,
including optimising the whole switch out of existence.

On 2021-07-07, Robert Finch <robfi680@gmail.com> wrote:
> I have been working on a C/C++ like compiler. One feature supported in
> the compiler is naked switches. A naked switch omits the range
> checking code that is normally associated with the switch statement.
> Omitting this code can improve performance at the risk of a crash if
> invalid cases are processed. I am wondering if there is a similar
> option in other C compilers? Or would this just be an automatic
> optimization at high levels?

I've not heard of such an option. Some modern compilers aggressively
optimize on the assumption that there is no undefined behavior.

Now, I will tell you a fantasy.

A conforming C implementation is free to assume that no undefined
behavior occurs because in that case no requirements apply.

For instance, if it is obvious that some pieces of code can only be
reached if the program has invoked undefined behavior, then that code
can be removed as if it were unreachable. There is no requirement that
anything work at all after undefined behavior.

This concept allows you to encode assertions about properties like this:

#define undefined_behavior (0/0)

if (x < 1 || x > 12)
perpetrate_undefined_behavior();

switch (x)

Because undefined behavior happens if x is outside the range 1 to 12,
the assumption that the program is free of undefined behavior logically
implies that x is not outside of that range.

Therefore, the if statement can be optimized away, and the switch
statement.

A simpler way to express the above situation is this:

switch (x) {
// ... cases 1 to 12 ..
break;
// out of range cases:
default: 0/0; // division by zero: undefined
}

Basically we divert the out-of-range cases to an obvious, explicitly
defined undefined behavior. Then we hope that the compiler infers that,
since undefined does not happen, x can be assumed not to be outside of
the 1 to 12 range, and so why bother checking.

How well that works in practice, you have to determine experimentally.

Experimentally, I'm not able to get GCC to eliminate the check for x
being above 9 in this code:

switch (x) {
case 0: return "zero";
case 1: return "one";
case 2: return "two";
case 3: return "three";
case 4: return "four";
case 5: return "five";
case 6: return "six";
case 7: return "seven";
case 8: return "eight";
case 9: return "nine";
default: exit(x/0);
}

The best that happens is that x is compared to 9, and if it is above,
a branch takes place to a label, where the "ud2" instruction is executed.
There is no division and no call to exit.

Basically, this "optimize based on defined behavior" business is the
programmer's enemy. It will not do the obvious optimizations you want,
but it will shoot you in the foot when you accidentally introduce some
undefined behavior, or use some formally undefined "classic" idiom that
has nevertheless worked on pretty much every compiler over forty yeras.

Now, GCC even has a way to explicitly assert "if we reach this point
in the program, the behavior is undefined". Even that is not getting rid
of the range test for me:

const char *fun(int x)
{ switch (x) {
case 0: return "zero";
case 1: return "one";
case 2: return "two";
case 3: return "three";
case 4: return "four";
case 5: return "five";
case 6: return "six";
case 7: return "seven";
case 8: return "eight";
case 9: return "nine";
default: __builtin_unreachable();
}
}

Worse, gcc (version 7.5.0 on Ubuntu 18) is not emitting the ud2
instruction in this case, as it does for a null pointer dereference or
division by zero. It just generates code that returns from the function.

Maybe there is some option you're supposed to use for this, but I can't
find it.

On 08/07/2021 03:57, Kaz Kylheku wrote:
> On 2021-07-07, Robert Finch <robfi680@gmail.com> wrote:
>> I have been working on a C/C++ like compiler. One feature supported in
>> the compiler is naked switches. A naked switch omits the range
>> checking code that is normally associated with the switch statement.
>> Omitting this code can improve performance at the risk of a crash if
>> invalid cases are processed. I am wondering if there is a similar
>> option in other C compilers? Or would this just be an automatic
>> optimization at high levels?
>
> I've not heard of such an option.

Nor have I. I'd suggest that it is a /really/ bad idea, since it
changes the semantics of the language. It would be possible to have it
as a feature written in a way that screams "this is not a switch
statement as you know it", calling it "__naked_switch(...)" or
something. But it would be simpler, clearer, safer, more portable and
more flexible to implement "__builtin_unreachable" as you suggest here.

> Some modern compilers aggressively
> optimize on the assumption that there is no undefined behavior.
>
> Now, I will tell you a fantasy.
>

It is no fantasy. Some people really get their knickers in a twist
about it, but IMHO it is a good thing.

> A conforming C implementation is free to assume that no undefined
> behavior occurs because in that case no requirements apply.
>
> For instance, if it is obvious that some pieces of code can only be
> reached if the program has invoked undefined behavior, then that code
> can be removed as if it were unreachable. There is no requirement that
> anything work at all after undefined behavior.
>
> This concept allows you to encode assertions about properties like this:
>
> #define undefined_behavior (0/0)
>
> if (x < 1 || x > 12)
> perpetrate_undefined_behavior();
>
> switch (x)
>
> Because undefined behavior happens if x is outside the range 1 to 12,
> the assumption that the program is free of undefined behavior logically
> implies that x is not outside of that range.
>
> Therefore, the if statement can be optimized away, and the switch
> statement.
>
> A simpler way to express the above situation is this:
>
> switch (x) {
> // ... cases 1 to 12 ..
> break;
> // out of range cases:
> default: 0/0; // division by zero: undefined
> }
>
> Basically we divert the out-of-range cases to an obvious, explicitly
> defined undefined behavior. Then we hope that the compiler infers that,
> since undefined does not happen, x can be assumed not to be outside of
> the 1 to 12 range, and so why bother checking.
>
> How well that works in practice, you have to determine experimentally.
>
> Experimentally, I'm not able to get GCC to eliminate the check for x
> being above 9 in this code:
>
>
> switch (x) {
> case 0: return "zero";
> case 1: return "one";
> case 2: return "two";
> case 3: return "three";
> case 4: return "four";
> case 5: return "five";
> case 6: return "six";
> case 7: return "seven";
> case 8: return "eight";
> case 9: return "nine";
> default: exit(x/0);
> }
>
> The best that happens is that x is compared to 9, and if it is above,
> a branch takes place to a label, where the "ud2" instruction is executed.
> There is no division and no call to exit.
>

You might think "0 / 0" would be a good case for undefined behaviour
(and therefore "can't happen" optimisations), but it's not really. On
many targets, actually executing "0 / 0" will cause a specific exception
or trap behaviour. And while the C standards say nothing about what
will happen here, and call it "undefined behaviour", target-specific
details and implementation-specific details may vary. The same applies
to anything else undefined in the C standards, such as dereferencing a
null pointer.

In addition, compilers often try to be helpful. If it appears that you
have accidentally tried to do something impossible at run-time,
executing an implementation-specific "trap" instruction is a good choice
- it gives the developer a better chance of finding the problem and
limiting the damage than happily launching nasal demons. So gcc
generates "ud2" instructions sometimes for x86, and similar instructions
for other processors. (You can get this intentionally with
"__builtin_trap()".)

So the best choice is a compiler-specific explicit "undefined behaviour"
indicator, since there is no standard feature here. For gcc and
compatible compilers, that is (as you know), __builtin_unreachable().

> Basically, this "optimize based on defined behavior" business is the
> programmer's enemy. It will not do the obvious optimizations you want,
> but it will shoot you in the foot when you accidentally introduce some
> undefined behavior, or use some formally undefined "classic" idiom that
> has nevertheless worked on pretty much every compiler over forty yeras.
>
> Now, GCC even has a way to explicitly assert "if we reach this point
> in the program, the behavior is undefined". Even that is not getting rid
> of the range test for me:
>
> const char *fun(int x)
> {
> switch (x) {
> case 0: return "zero";
> case 1: return "one";
> case 2: return "two";
> case 3: return "three";
> case 4: return "four";
> case 5: return "five";
> case 6: return "six";
> case 7: return "seven";
> case 8: return "eight";
> case 9: return "nine";
> default: __builtin_unreachable();
> }
> }
>
> Worse, gcc (version 7.5.0 on Ubuntu 18) is not emitting the ud2
> instruction in this case, as it does for a null pointer dereference or
> division by zero. It just generates code that returns from the function.
>
> Maybe there is some option you're supposed to use for this, but I can't
> find it.
>

The trick is to use gcc 8 or newer :-)

Robert Finch <robfi680@gmail.com> writes:
> I have been working on a C/C++ like compiler. One feature supported in
> the compiler is naked switches. A naked switch omits the range
> checking code that is normally associated with the switch
> statement. Omitting this code can improve performance at the risk of a
> crash if invalid cases are processed. I am wondering if there is a
> similar option in other C compilers? Or would this just be an
> automatic optimization at high levels?

What range checking code are you referring to? Can you give an example
in C that demonstrates the change in behavior? How does a default:
label affect it?

> Normal Switch:
>
> ; switch(x) {
> ldo $t0,64[$fp]
> sge $t1,$t0,#1 ; x varies between 1 and 12
> sle $t2,$t0,#12
> and $t1,$t1,$t2
> beq $t1,TestSwitch_89
> sub $t0,$t0,#1
> sll $t0,$t0,#4
> ldo $t0,TestSwitch_116[$t0]
> jmp $t0
>
> Naked Switch
> ; switch(x; naked) {
> ldo $t0,64[$fp]
> sub $t0,$t0,#1
> sll $t0,$t0,#4
> ldo $t0,TestSwitch_144[$t0]
> jmp $t0
>

--
Keith Thompson (The_Other_Keith) Keith.S.Thompson+u@gmail.com
Working, but not speaking, for Philips
void Void(void) { Void(); } /* The recursive call of the void */

On Thursday, 8 July 2021 at 09:00:40 UTC+1, Keith Thompson wrote:
> Robert Finch <robf...@gmail.com> writes:
> > I have been working on a C/C++ like compiler. One feature supported in
> > the compiler is naked switches. A naked switch omits the range
> > checking code that is normally associated with the switch
> > statement. Omitting this code can improve performance at the risk of a
> > crash if invalid cases are processed. I am wondering if there is a
> > similar option in other C compilers? Or would this just be an
> > automatic optimization at high levels?
> What range checking code are you referring to? Can you give an example
> in C that demonstrates the change in behavior? How does a default:
>
Normal switch

foo(int x)
{ switch(x)
{
case 1: printf("one\n"); break;
case 2: printf("two\n"); break;
case 3:: printf("three\n"); break;
case 4: printf("four\n"): break;
default: printf("x is in error\n"); break;
}
}

That will compile to something like the following
if(x < 1 || x > 4) x -= 5;
x -= 1;
goto jumptable[x]

Namke switch

foo(int x)
{ nakedswitch(x)
{
case 1: printf("one\n"); break;
case 2: printf("two\n"); break;
case 3:: printf("three\n"); break;
case 4: printf("four\n"): break;
}
}

would compile to the following
/* jumptable[0] = NULL; */
goto jumptable[x];

so x is unchecked. If it is out of range, the program crashes.

On Thursday, July 8, 2021 at 6:25:26 AM UTC-4, Malcolm McLean wrote:
> On Thursday, 8 July 2021 at 09:00:40 UTC+1, Keith Thompson wrote:
> > Robert Finch <robf...@gmail.com> writes:
> > > I have been working on a C/C++ like compiler. One feature supported in
> > > the compiler is naked switches. A naked switch omits the range
> > > checking code that is normally associated with the switch
> > > statement. Omitting this code can improve performance at the risk of a
> > > crash if invalid cases are processed. I am wondering if there is a
> > > similar option in other C compilers? Or would this just be an
> > > automatic optimization at high levels?
> > What range checking code are you referring to? Can you give an example
> > in C that demonstrates the change in behavior? How does a default:
> >
> Normal switch
>
> foo(int x)
> {
> switch(x)
> {
> case 1: printf("one\n"); break;
> case 2: printf("two\n"); break;
> case 3:: printf("three\n"); break;
> case 4: printf("four\n"): break;
> default: printf("x is in error\n"); break;
> }
> }
>
> That will compile to something like the following
> if(x < 1 || x > 4) x -= 5;
> x -= 1;
> goto jumptable[x]
>
> Namke switch
>
> foo(int x)
> {
> nakedswitch(x)
> {
> case 1: printf("one\n"); break;
> case 2: printf("two\n"); break;
> case 3:: printf("three\n"); break;
> case 4: printf("four\n"): break;
> }
> }
>
> would compile to the following
> /* jumptable[0] = NULL; */
> goto jumptable[x];
>
> so x is unchecked. If it is out of range, the program crashes.

That is basically how it is working. There is still a default statement for unimplemented values between the min and max. The table entry may as well point somewhere useful.
There were two goals with this, a) a performance optimization and b) code size optimization. I am dealing with small roms in an FPGA so bytes count. The processor is also rather slow <40MHz.

On 08/07/2021 14:58, Robert Finch wrote:
> On Thursday, July 8, 2021 at 6:25:26 AM UTC-4, Malcolm McLean wrote:
>> On Thursday, 8 July 2021 at 09:00:40 UTC+1, Keith Thompson wrote:
>>> Robert Finch <robf...@gmail.com> writes:
>>>> I have been working on a C/C++ like compiler. One feature supported in
>>>> the compiler is naked switches. A naked switch omits the range
>>>> checking code that is normally associated with the switch
>>>> statement. Omitting this code can improve performance at the risk of a
>>>> crash if invalid cases are processed. I am wondering if there is a
>>>> similar option in other C compilers? Or would this just be an
>>>> automatic optimization at high levels?
>>> What range checking code are you referring to? Can you give an example
>>> in C that demonstrates the change in behavior? How does a default:
>>>
>> Normal switch
>>
>> foo(int x)
>> {
>> switch(x)
>> {
>> case 1: printf("one\n"); break;
>> case 2: printf("two\n"); break;
>> case 3:: printf("three\n"); break;
>> case 4: printf("four\n"): break;
>> default: printf("x is in error\n"); break;
>> }
>> }
>>
>> That will compile to something like the following
>> if(x < 1 || x > 4) x -= 5;
>> x -= 1;
>> goto jumptable[x]
>>
>> Namke switch
>>
>> foo(int x)
>> {
>> nakedswitch(x)
>> {
>> case 1: printf("one\n"); break;
>> case 2: printf("two\n"); break;
>> case 3:: printf("three\n"); break;
>> case 4: printf("four\n"): break;
>> }
>> }
>>
>> would compile to the following
>> /* jumptable[0] = NULL; */
>> goto jumptable[x];
>>
>> so x is unchecked. If it is out of range, the program crashes.
>
> That is basically how it is working. There is still a default statement for unimplemented values between the min and max. The table entry may as well point somewhere useful.
> There were two goals with this, a) a performance optimization and b) code size optimization. I am dealing with small roms in an FPGA so bytes count. The processor is also rather slow <40MHz.
>

So, this just like array index bounds checking. A bounds check can be
omitted if you're sure the index is within range.

Except that in C, bounds aren't checked anyway. However most /correct/
programs won't have out-of-bounds indices.

You can probably omit the switch bounds check if it makes a difference,
if you are equally sure the index will be within range.

If not, then it might be best left in. Although you can try the single
unsigned comparison if the hardware allows.

On 08/07/2021 15:58, Robert Finch wrote:
> On Thursday, July 8, 2021 at 6:25:26 AM UTC-4, Malcolm McLean wrote:
>> On Thursday, 8 July 2021 at 09:00:40 UTC+1, Keith Thompson wrote:
>>> Robert Finch <robf...@gmail.com> writes:
>>>> I have been working on a C/C++ like compiler. One feature supported in
>>>> the compiler is naked switches. A naked switch omits the range
>>>> checking code that is normally associated with the switch
>>>> statement. Omitting this code can improve performance at the risk of a
>>>> crash if invalid cases are processed. I am wondering if there is a
>>>> similar option in other C compilers? Or would this just be an
>>>> automatic optimization at high levels?

>
> That is basically how it is working. There is still a default
> statement for unimplemented values between the min and max. The table
> entry may as well point somewhere useful. There were two goals with
> this, a) a performance optimization and b) code size optimization. I
> am dealing with small roms in an FPGA so bytes count. The processor
> is also rather slow <40MHz.
>
>

You wrote that you "have been working on a C/C++ like compiler" - do you
mean you have been /using/ such a compiler, or you have been /writing/
such a compiler?

As I mentioned earlier, I think a "naked switch" like this is a terrible
idea. It is not something I have seen on other compilers, and I've used
quite a large number over the years for far smaller and slower devices
than you are describing here.

The way you handle this with gcc has already been covered - you use
__builtin_unreachable() to tell the compiler how to optimise for "this
can't happen" cases. clang supports __builtin_unreachable() too, and
MSVC has "__assume(false)" that has the same effect.

On 08/07/2021 16:52, David Brown wrote:
> On 08/07/2021 15:58, Robert Finch wrote:
>> On Thursday, July 8, 2021 at 6:25:26 AM UTC-4, Malcolm McLean wrote:
>>> On Thursday, 8 July 2021 at 09:00:40 UTC+1, Keith Thompson wrote:
>>>> Robert Finch <robf...@gmail.com> writes:
>>>>> I have been working on a C/C++ like compiler. One feature supported in
>>>>> the compiler is naked switches. A naked switch omits the range
>>>>> checking code that is normally associated with the switch
>>>>> statement. Omitting this code can improve performance at the risk of a
>>>>> crash if invalid cases are processed. I am wondering if there is a
>>>>> similar option in other C compilers? Or would this just be an
>>>>> automatic optimization at high levels?
>
>
>>
>> That is basically how it is working. There is still a default
>> statement for unimplemented values between the min and max. The table
>> entry may as well point somewhere useful. There were two goals with
>> this, a) a performance optimization and b) code size optimization. I
>> am dealing with small roms in an FPGA so bytes count. The processor
>> is also rather slow <40MHz.
>>
>>
>
> You wrote that you "have been working on a C/C++ like compiler" - do you
> mean you have been /using/ such a compiler, or you have been /writing/
> such a compiler?
>
> As I mentioned earlier, I think a "naked switch" like this is a terrible
> idea.

I've considered having something like that. I'd have called it 'uswitch'.

It was never done because:

* The range check wasn't really much of an overhead on x64 (the indexed
jump is)

* I could never be sure that the switch index would always be inside the
range of the minimum and maximum values of the switch cases

* It seemed a bit naff

But I wouldn't find it objectionable if it helps out on a slower
processor. After all array indices are not checked either as I said in
my last post.

It is not something I have seen on other compilers, and I've used
> quite a large number over the years for far smaller and slower devices
> than you are describing here.
>
> The way you handle this with gcc has already been covered - you use
> __builtin_unreachable() to tell the compiler how to optimise for "this
> can't happen" cases. clang supports __builtin_unreachable() too, and
> MSVC has "__assume(false)" that has the same effect.
>

How would that work in that case? There doesn't appear to be a bit of
code to hang that onto, unless you specifically create an empty block
for the purpose, guarded by the same sort of range check you want to avoid.

If you mean putting it on the default: case of the switch, then that is
not the same thing: if you know your switch index values are in the
range 1 to 5 include, you may have case labels for 1, 3 and 5, and want
default handling for 2 and 4, which /is/ reachable.

You just don't want the unnecessary check for being within 1 to 5.

>You wrote that you "have been working on a C/C++ like compiler" - do you
>mean you have been /using/ such a compiler, or you have been /writing/
>such a compiler?

I have been using it for simple demos, actually running the compiled code sometime. It has been revamped for several different custom processors, but is still a work in progress.

>As I mentioned earlier, I think a "naked switch" like this is a terrible
>idea. It is not something I have seen on other compilers, and I've used
>quite a large number over the years for far smaller and slower devices
>than you are describing here.

It is a bad idea in terms of allowing program crashes. But then there are naked functions.

CC64 supports a number of “features” not found in standard C. But I call it a “C” like compiler because it can compile most C code without changes. I used it to compile the standard C library. Stills lots of bugs in the compiler though.

One feature I like is the ability to manipulate bit slices.

int a, b;

a = b[10:1];

Sets a equal to bits 1 to 10 of b. A bit slice can be distinguished from an array index by the colon. Compiles painlessly directly to field manipulation instructions and gets rid of code like:
a = (b >> 1) & 0x3ff;
Where the compiler really has to work to determine the bit operations.
enum allows the stride to be specified. enum(-1) { a,b,c }; will set the values to 0, -1, -2, .etc.
&&& means the same as && except that optimization of both side of the &&& is safe to do. There is also ||| and ?? operators.
In theory (not tried yet) classes with single inheritance and overloaded methods are supported. No templates or operator overloading though. Constructors / destructors not implemented yet.

On 2021-07-07, Robert Finch <robfi680@gmail.com> wrote:
> I have been working on a C/C++ like compiler. One feature supported in
> the compiler is naked switches. A naked switch omits the range
> checking code that is normally associated with the switch statement.
> Omitting this code can improve performance at the risk of a crash if
> invalid cases are processed. I am wondering if there is a similar
> option in other C compilers? Or would this just be an automatic
> optimization at high levels?

GNU C has the feature that labels can be treated as data; they
can be stored in variables/objects and used to perform a goto.

Thus GNU C has two computed-goto mechanisms: the regular switch
which branches to a fixed case label via a computed value,
and the literal computed goto, which branchews to a label pointer
retrieved from an object.

GNU C code can construct an array, which is populated with goto labels,
and then use it as a completely usafe, unchecked jump table.

It looks something like:

void *table[] = { &&L1, &&L2, &&L3, ... };

goto *table[x];

L1:
// code
goto somewhere;

L2;
// code
goto somewhere;

This not only ensures that there is no range check, but ensures that the
run-time representation of the control flow is a jump table in the first
place, as a matter of the program's expressed abstractc semantics rather
than optimization.

You could dress this up with some macros:

SWITCH(x, table, ENUM_FOO, ENUM_BAR, ENUM_XYZZY)
CASE(ENUM_FOO) statement;
CASE(ENUM_BAR) statement;
CASE(ENUM_XYZZY) { compound statement }
ENDSWITCH;

How to implement? Use some convoluted C99+ preprocessor tricks, which
I'm 95% certain are possible, to spin the first macro into the output:

void *table[] = { &&L_ENUM_FOO, &&L_ENUM_BAR, &&L_ENUM_XYZZY };
goto *table[x];

The CASE macros are easy:

#define CASE(LAB) if (0) L_ ## LAB:

The if (0) ensures that control falls through cases that are entered
from above without a goto. Thus when each case statement terminates, it
will fall through to the bottom, skipping all subsequent cases.

The ENDSWITCH macro does nothing; but it allows us to retarget
the macros to an ordinary switch statement if we are not on GCC/clang:

#define SWITCH(EXPR, TABLE, LAB ...) switch (x) {

#define CASE(LAB) if (0) case LAB:

#define ENDSWITCH }

Nothing tested in this article. :)

On 08/07/2021 18:18, Robert Finch wrote:
>> You wrote that you "have been working on a C/C++ like compiler" - do you
>> mean you have been /using/ such a compiler, or you have been /writing/
>> such a compiler?
>
> I have been using it for simple demos, actually running the compiled code sometime. It has been revamped for several different custom processors, but is still a work in progress.
>
>> As I mentioned earlier, I think a "naked switch" like this is a terrible
>> idea. It is not something I have seen on other compilers, and I've used
>> quite a large number over the years for far smaller and slower devices
>> than you are describing here.
>
> It is a bad idea in terms of allowing program crashes. But then there are naked functions.
>
> CC64 supports a number of “features” not found in standard C. But I call it a “C” like compiler because it can compile most C code without changes. I used it to compile the standard C library. Stills lots of bugs in the compiler though.
>
> One feature I like is the ability to manipulate bit slices.
>
> int a, b;
>
> a = b[10:1];
>
> Sets a equal to bits 1 to 10 of b. A bit slice can be distinguished from an array index by the colon. Compiles painlessly directly to field manipulation instructions and gets rid of code like:
> a = (b >> 1) & 0x3ff;
> Where the compiler really has to work to determine the bit operations.

I support such bit operations in my non-C languages, and I'm surprised
they are not more widely available because they are so handy.

I guess that in C, programmers just have to keep reinventing the same
macros for such purposes.

For your example, I'd use:

a = b.[1..10] # for one language, has to be in this order
a = b.[1] # extract a single bit

Without the dot, these would be regular slicing or indexing operations.

> enum allows the stride to be specified. enum(-1) { a,b,c }; will set the values to 0, -1, -2, .etc.

That would be a good idea, if I could think of a use-case! (But the
reverse ordering of your example could be a problem.)

On 2021-07-08, Robert Finch <robfi680@gmail.com> wrote:
>>You wrote that you "have been working on a C/C++ like compiler" - do you
>>mean you have been /using/ such a compiler, or you have been /writing/
>>such a compiler?
>
> I have been using it for simple demos, actually running the compiled code sometime. It has been revamped for several different custom processors, but is still a work in progress.
>
>>As I mentioned earlier, I think a "naked switch" like this is a terrible
>>idea. It is not something I have seen on other compilers, and I've used
>>quite a large number over the years for far smaller and slower devices
>>than you are describing here.
>
> It is a bad idea in terms of allowing program crashes. But then there are naked functions.
>
> CC64 supports a number of “features” not found in standard C. But I call it a “C” like compiler because it can compile most C code without changes. I used it to compile the standard C library. Stills lots of bugs in the compiler though.
>
> One feature I like is the ability to manipulate bit slices.
>
> int a, b;
>
> a = b[10:1];
>
> Sets a equal to bits 1 to 10 of b. A bit slice can be distinguished
> from an array index by the colon. Compiles painlessly directly to
> field manipulation instructions and gets rid of code like: a = (b >>
> 1) & 0x3ff;

A macro can do this:

a = BIT(b,10,1);

and works everywhere. What you need is a typeof extension to make it
work with different integer types while retaining efficiency, otherwise
you're looking at making it assume 64 bit, or saddling it with a type
name argument.

(typeof is a more valuable, not to mention simpler, extension; it is
useful in all kinds of macros.)

The _Generic mechanism in C11 can also be used to make BIT work
with diferent types.

--
TXR Programming Language: http://nongnu.org/txr
Cygnal: Cygwin Native Application Library: http://kylheku.com/cygnal

Kaz Kylheku <563-365-8930@kylheku.com> writes:
>On 2021-07-07, Robert Finch <robfi680@gmail.com> wrote:
>> I have been working on a C/C++ like compiler. One feature supported in
>> the compiler is naked switches. A naked switch omits the range
>> checking code that is normally associated with the switch statement.
>> Omitting this code can improve performance at the risk of a crash if
>> invalid cases are processed. I am wondering if there is a similar
>> option in other C compilers? Or would this just be an automatic
>> optimization at high levels?
>
>GNU C has the feature that labels can be treated as data; they
>can be stored in variables/objects and used to perform a goto.

GCC generally generates optimal code sequences for switch
statements; from simple sequenced branches for small case
counts to jump tables for larger case counts.

On 2021-07-08, Scott Lurndal <scott@slp53.sl.home> wrote:
> Kaz Kylheku <563-365-8930@kylheku.com> writes:
>>On 2021-07-07, Robert Finch <robfi680@gmail.com> wrote:
>>> I have been working on a C/C++ like compiler. One feature supported in
>>> the compiler is naked switches. A naked switch omits the range
>>> checking code that is normally associated with the switch statement.
>>> Omitting this code can improve performance at the risk of a crash if
>>> invalid cases are processed. I am wondering if there is a similar
>>> option in other C compilers? Or would this just be an automatic
>>> optimization at high levels?
>>
>>GNU C has the feature that labels can be treated as data; they
>>can be stored in variables/objects and used to perform a goto.
>
> GCC generally generates optimal code sequences for switch
> statements; from simple sequenced branches for small case
> counts to jump tables for larger case counts.

Elsewhere in the thread, I was not able to coax GCC into eliminating the
range test and branch prior to the table switch, even if the default:
case of the switch was __builtin_unreachable().

Since two instructions can be removed form the code, it must not be
optimal.

--
TXR Programming Language: http://nongnu.org/txr
Cygnal: Cygwin Native Application Library: http://kylheku.com/cygnal

Robert Finch <robfi680@gmail.com> writes:
> On Thursday, July 8, 2021 at 6:25:26 AM UTC-4, Malcolm McLean wrote:
>> On Thursday, 8 July 2021 at 09:00:40 UTC+1, Keith Thompson wrote:
>> > Robert Finch <robf...@gmail.com> writes:
>> > > I have been working on a C/C++ like compiler. One feature supported in
>> > > the compiler is naked switches. A naked switch omits the range
>> > > checking code that is normally associated with the switch
>> > > statement. Omitting this code can improve performance at the risk of a
>> > > crash if invalid cases are processed. I am wondering if there is a
>> > > similar option in other C compilers? Or would this just be an
>> > > automatic optimization at high levels?
>> > What range checking code are you referring to? Can you give an example
>> > in C that demonstrates the change in behavior? How does a default:
>> >
>> Normal switch
>>
>> foo(int x)
>> {
>> switch(x)
>> {
>> case 1: printf("one\n"); break;
>> case 2: printf("two\n"); break;
>> case 3:: printf("three\n"); break;
>> case 4: printf("four\n"): break;
>> default: printf("x is in error\n"); break;
>> }
>> }
>>
>> That will compile to something like the following
>> if(x < 1 || x > 4) x -= 5;
>> x -= 1;
>> goto jumptable[x]

That's a normal switch, not a naked one, and the if/goto code is not
equivalent to the switch. If x is 42, the switch statement will print
"x is in error"; the if/goto code (assuming "goto jumptable[x]" has the
obvious meaning) has undefined behavior. Or did you intend this to
be a naked switch?

>> Namke switch
>>
>> foo(int x)
>> {
>> nakedswitch(x)
>> {
>> case 1: printf("one\n"); break;
>> case 2: printf("two\n"); break;
>> case 3:: printf("three\n"); break;
>> case 4: printf("four\n"): break;
>> }
>> }
>>
>> would compile to the following
>> /* jumptable[0] = NULL; */
>> goto jumptable[x];
>>
>> so x is unchecked. If it is out of range, the program crashes.
>
> That is basically how it is working. There is still a default
> statement for unimplemented values between the min and max. The table
> entry may as well point somewhere useful. There were two goals with
> this, a) a performance optimization and b) code size optimization. I
> am dealing with small roms in an FPGA so bytes count. The processor is
> also rather slow <40MHz.

So here's my understanding of how nakedswitch might be defined:

If there is no default: label, then it acts like a normal switch *except
that* if the value of x is less than the smallest case value or greater
than the largest case value, the behavior is undefined. Is that the intent?

If there is a default: value, then ... what?

And both examples use contiguous ranges of values. How would this
behave?

int x = 15;
nakedswitch(x) {
case 10: puts("ten"); break;
case 20: puts("twenty"); break;
}

There are no "range checks" in the defined behavior of a C switch
statement, and no requirement that they be implemented using a jump
table.

(What I'm looking for is a definition of the *behavior* of a
nakedswitch, including the exact situations where the behavior is
undefined.)

Many years ago, I used a Pascal compiler that always compiled case
statements to a jump table. When I wrote a case statement with cases 1,
10, 100, 1000, 10000, it crashed the compiler. gcc, for example, will
generate the equivalent of either a jump table or an if/else chain
depending on the values.

--
Keith Thompson (The_Other_Keith) Keith.S.Thompson+u@gmail.com
Working, but not speaking, for Philips
void Void(void) { Void(); } /* The recursive call of the void */

Kaz Kylheku <563-365-8930@kylheku.com> writes:
>On 2021-07-08, Scott Lurndal <scott@slp53.sl.home> wrote:
>> Kaz Kylheku <563-365-8930@kylheku.com> writes:
>>>On 2021-07-07, Robert Finch <robfi680@gmail.com> wrote:
>>>> I have been working on a C/C++ like compiler. One feature supported in
>>>> the compiler is naked switches. A naked switch omits the range
>>>> checking code that is normally associated with the switch statement.
>>>> Omitting this code can improve performance at the risk of a crash if
>>>> invalid cases are processed. I am wondering if there is a similar
>>>> option in other C compilers? Or would this just be an automatic
>>>> optimization at high levels?
>>>
>>>GNU C has the feature that labels can be treated as data; they
>>>can be stored in variables/objects and used to perform a goto.
>>
>> GCC generally generates optimal code sequences for switch
>> statements; from simple sequenced branches for small case
>> counts to jump tables for larger case counts.
>
>Elsewhere in the thread, I was not able to coax GCC into eliminating the
>range test and branch prior to the table switch, even if the default:
>case of the switch was __builtin_unreachable().
>
>Since two instructions can be removed form the code, it must not be
>optimal.

Do the instructions actually affect performance? Unlikely, given
modern branch predictors.

And vectoring through a bogus entry in a jump table should be
avoided.

Robert Finch <robfi680@gmail.com> writes:
> A naked switch omits the range checking code th=
>at is normally associated with the switch statement.

This seems to be confusing semantics with implementations.

There is no range associated with a switch statement.

When writing /implementations/ of switch statement,
sometimes, some implementators might believe that for
some cases of switch statement implementations, range
checks in the compiled code are required.

I'd prefer a compiler that adds unneeded code only when
asked to do so by a command line option.

>
> > enum allows the stride to be specified. enum(-1) { a,b,c }; will set the values to 0, -1, -2, .etc.
> That would be a good idea, if I could think of a use-case! (But the
> reverse ordering of your example could be a problem.)

It was needed to return negative values for error codes from functions. I got tired of having to set all the values manually.
I had another case where the values needed to be spaced out.
Another case may be power of two values. 1,2,4,8,16,32,.... but I do not have a good way to specify this yet.

On Thursday, July 8, 2021 at 1:47:12 PM UTC-4, Kaz Kylheku wrote:
> A macro can do this:
>
> a = BIT(b,10,1);
>
> and works everywhere. What you need is a typeof extension to make it
> work with different integer types while retaining efficiency, otherwise
> you're looking at making it assume 64 bit, or saddling it with a type
> name argument.

One should not have to write macros for commonly used language elements.

> (typeof is a more valuable, not to mention simpler, extension; it is
> useful in all kinds of macros.)

In CC64 there is a typenum() keyword that does almost the same thing. It returns a 16-bit hash-code for the type allowing RTTI. Someday I will get around to modifying it to typeof.
Otherwise with bit-slicing it ignores the type, assuming the bit slice can be done. It works only on the primitive types.

> TXR Programming Language: http://nongnu.org/txr
> Cygnal: Cygwin Native Application Library: http://kylheku.com/cygnal

On 2021-07-08, Scott Lurndal <scott@slp53.sl.home> wrote:
> Kaz Kylheku <563-365-8930@kylheku.com> writes:
>>On 2021-07-08, Scott Lurndal <scott@slp53.sl.home> wrote:
>>> Kaz Kylheku <563-365-8930@kylheku.com> writes:
>>>>On 2021-07-07, Robert Finch <robfi680@gmail.com> wrote:
>>>>> I have been working on a C/C++ like compiler. One feature supported in
>>>>> the compiler is naked switches. A naked switch omits the range
>>>>> checking code that is normally associated with the switch statement.
>>>>> Omitting this code can improve performance at the risk of a crash if
>>>>> invalid cases are processed. I am wondering if there is a similar
>>>>> option in other C compilers? Or would this just be an automatic
>>>>> optimization at high levels?
>>>>
>>>>GNU C has the feature that labels can be treated as data; they
>>>>can be stored in variables/objects and used to perform a goto.
>>>
>>> GCC generally generates optimal code sequences for switch
>>> statements; from simple sequenced branches for small case
>>> counts to jump tables for larger case counts.
>>
>>Elsewhere in the thread, I was not able to coax GCC into eliminating the
>>range test and branch prior to the table switch, even if the default:
>>case of the switch was __builtin_unreachable().
>>
>>Since two instructions can be removed form the code, it must not be
>>optimal.
>
> Do the instructions actually affect performance? Unlikely, given
> modern branch predictors.

If the branch instruction is deleted, then it doesn't require branch
prediction.

Branch prediction isn't free; it requires a cache of information.
Any time you put something in it, something else gets bumped.

Not emitting the compare and branch instruction also means that the code
sequence is two instructions shorter. That has to save something.

Size matters. Two instructions less means room for two more instructions
from somewhere else to fit into the instruction cache.

--
TXR Programming Language: http://nongnu.org/txr
Cygnal: Cygwin Native Application Library: http://kylheku.com/cygnal

On 08/07/2021 18:51, Bart wrote:
> On 08/07/2021 16:52, David Brown wrote:
>> On 08/07/2021 15:58, Robert Finch wrote:
>>> On Thursday, July 8, 2021 at 6:25:26 AM UTC-4, Malcolm McLean wrote:
>>>> On Thursday, 8 July 2021 at 09:00:40 UTC+1, Keith Thompson wrote:
>>>>> Robert Finch <robf...@gmail.com> writes:
>>>>>> I have been working on a C/C++ like compiler. One feature
>>>>>> supported in
>>>>>> the compiler is naked switches. A naked switch omits the range
>>>>>> checking code that is normally associated with the switch
>>>>>> statement. Omitting this code can improve performance at the risk
>>>>>> of a
>>>>>> crash if invalid cases are processed. I am wondering if there is a
>>>>>> similar option in other C compilers? Or would this just be an
>>>>>> automatic optimization at high levels?
>>
>>
>>>
>>> That is basically how it is working. There is still a default
>>> statement for unimplemented values between the min and max. The table
>>> entry may as well point somewhere useful. There were two goals with
>>> this, a) a performance optimization and b) code size optimization. I
>>> am dealing with small roms in an FPGA so bytes count. The processor
>>> is also rather slow <40MHz.
>>>
>>>
>>
>> You wrote that you "have been working on a C/C++ like compiler" - do you
>> mean you have been /using/ such a compiler, or you have been /writing/
>> such a compiler?
>>
>> As I mentioned earlier, I think a "naked switch" like this is a terrible
>> idea.
>
> I've considered having something like that. I'd have called it 'uswitch'.
>
> It was never done because:
>
> * The range check wasn't really much of an overhead on x64 (the indexed
> jump is)
>
> * I could never be sure that the switch index would always be inside the
> range of the minimum and maximum values of the switch cases
>
> * It seemed a bit naff
>
> But I wouldn't find it objectionable if it helps out on a slower
> processor. After all array indices are not checked either as I said in
> my last post.
>

The critical difference is the semantics of the C language - array
indexes are not checked automatically in C, the range in a switch /is/
checked because a switch is defined in the language to do nothing if the
value does not match any of the cases.

If you are making a different language, you can pick different rules.

I've seen many compilers that have odd non-standard behaviour "to make C
simpler" or "to get better code on this little processor". IME, it is
/always/ a mistake. I've seen "const" used to mean "this is in flash",
changes to the integer promotion rules, and other "improvements". The
result is always mixups and misunderstandings, incompatibilities and
people writing poorer code that is harder to follow, less portable /and/
gives less efficient results on the smart-arse toolchain.

If you are making a C compiler, make a /C/ compiler. If you want to get
better results, make your optimisation smarter. If you want to give
users something extra to squeeze a little more out of the target, give
them something /useful/, /clear/, and /optional/. The answer here is
__builtin_unreachable(), or __assume if you prefer MSVC's solution.

>   It is not something I have seen on other compilers, and I've used
>> quite a large number over the years for far smaller and slower devices
>> than you are describing here.
>>
>> The way you handle this with gcc has already been covered - you use
>> __builtin_unreachable() to tell the compiler how to optimise for "this
>> can't happen" cases.  clang supports __builtin_unreachable() too, and
>> MSVC has "__assume(false)" that has the same effect.
>>
>
> How would that work in that case? There doesn't appear to be a bit of
> code to hang that onto, unless you specifically create an empty block
> for the purpose, guarded by the same sort of range check you want to avoid.

The normal situation would be :

switch (x) {
case 1 : handle1(); break;
case 2 : handle2(); break;
case 4 : handle4(); break;
default : __builtin_unreachable(); // gcc
default : __assume(0); // msvc
}

If you want to say x == 3 is a "do nothing" situation, but you want to
tell the compiler it doesn't need to check for x < 1 or x > 4, then you
do so simply and clearly:

if ((x < 1) || (x > 4)) __builtin_unreachable(); // gcc
__assume((x >= 1) && (x <= 4)); // msvc

switch (x) {
case 1 : handle1(); break;
case 2 : handle2(); break;
case 4 : handle4(); break;
}

Compare that to someone looking at "uswitch" and wondering what that
might possibly mean, or trying to guess if it is safe to pass 3 as x, or
figuring out if the code is correct and efficient when you have the
cases in a different order.

Once you have __builtin_unreachable() or __assume(), you have a tool
that can be re-used in all sorts of other situations instead of just one
minor use-case with little impact. And this tool is useful for giving
the compiler more information, and for documenting the programmer's
intentions and assumptions.

You can also use a macro or inline function here, along the lines of :

#if DEBUGMODE
#define impossible() send_bug_report_to_programmer()
#else
#define impossible() __builtin_unreachable()
#endif

Now you have a combined debugging tool, documentation tool, and more
efficient code.

>
> If you mean putting it on the default: case of the switch, then that is
> not the same thing: if you know your switch index values are in the
> range 1 to 5 include, you may have case labels for 1, 3 and 5, and want
> default handling for 2 and 4, which /is/ reachable.
>
> You just don't want the unnecessary check for being within 1 to 5.

Put the check where you want the check to happen.

On 09/07/2021 00:45, Robert Finch wrote:
> On Thursday, July 8, 2021 at 1:47:12 PM UTC-4, Kaz Kylheku wrote:
>> A macro can do this:
>>
>> a = BIT(b,10,1);
>>
>> and works everywhere. What you need is a typeof extension to make it
>> work with different integer types while retaining efficiency, otherwise
>> you're looking at making it assume 64 bit, or saddling it with a type
>> name argument.
>
> One should not have to write macros for commonly used language elements.

Your extension is not commonly used, because it only exists in your
tool. People who need to do a lot of bit slicing and don't like masking
and shifting (or struct bit-fields) should not have trouble defining:

#define BIT(x, top, bottom) \
(((x) >> (bottom)) & ((1llu << ((top) - (bottom) + 1)) - 1))

Yes, the parenthesis you need for macros are ugly, but you only need to
get it right once, and now you can read your bit-fields.

Having said that, it is not at all unreasonable for an embedded compiler
to ship with extra headers, which would be an excellent place to put
macros like this for user convenience. It would be simpler and clearer
to C programmers who are not used to your extensions. This is the
technique used by other embedded compilers.

I'm not saying the extension is not useful, or bad in itself - but I
dislike adding extensions when it is perfectly possible to get the same
results without changing the language. You need very good reasons for
adding non-portable extensions. And when you do so, you should aim to
do it in a way that is familiar or portable, clear, flexible, and can
provide many benefits instead of needing lots of specialised extensions.

To make a macro (or inline function) that lets you /change/ the
bit-field is more difficult. As Kaz says, doing that efficiently would
need _Generic (standard C, but not everyone has moved to C11) or a
"typeof" extension. My recommendation here would be to implement
"typeof" in roughly the same way as gcc, clang, icc, Metroworks, and
other compilers, and roughly as it has been proposed as a new feature
for future C standards. Then make your macros (or, better, static
inline functions) in a header that you ship with the compiler.

>
>> (typeof is a more valuable, not to mention simpler, extension; it is
>> useful in all kinds of macros.)
>
> In CC64 there is a typenum() keyword that does almost the same
> thing. It returns a 16-bit hash-code for the type allowing RTTI. Someday I will
> get around to modifying it to typeof.

Your "typenum" might be useful, but it is not at all the same thing as
"typeof" : <https://gcc.gnu.org/onlinedocs/gcc/Typeof.html>

> Otherwise with bit-slicing it ignores the type, assuming the bit
> slice can be done. It works only on the primitive types.
>

(Please get a real newsreader and a real newsserver, rather than google
groups - amongst other benefits it would avoid the need to re-format
your posts due to GG's inability to follow Usenet standards.)

On 08/07/2021 20:40, Keith Thompson wrote:

> Many years ago, I used a Pascal compiler that always compiled case
> statements to a jump table. When I wrote a case statement with cases 1,
> 10, 100, 1000, 10000, it crashed the compiler. gcc, for example, will
> generate the equivalent of either a jump table or an if/else chain
> depending on the values.
>

gcc has a lot more options than that. For example :

int floo(int x) {
if ((x < 1) || (x > 4)) __builtin_unreachable();
switch (x) {
case 1 : return 100;
case 2 : return 200;
case 3 : return 300;
case 4 : return 400;
}
return 0;
}

With this, the assembly generated by gcc (on x86) is equivalent to :

int floo(int x) {
int y = 100;
if (x < 2) return y;
return x * y;
}

(On other targets where multiplication is cheaper than the conditional,
it may omit that check.)

And with a sparse switch, the if/else pattern generated is a binary tree
rather than a linear chain.

There are lots of options for implementing switches.