On Friday, December 24, 2021 at 9:37:14 PM UTC-7, Ivan Godard wrote:
> On 12/24/2021 10:17 AM, MitchAlsup wrote:

> > There is NO JUSTIFIABLE reason that an instruction is not entirely
> > self-contained!

> Really? I suppose that might be true for OOO that is emulating
> sequential execution, but what about VLIW and other wide multi-issue?

> Chopping off the variable and large parts so they can be recognized in
> parallel lets the issue width no longer depend on how many constants you
> have.

This is the sort of thing I've been fooling around with finding a way to
achieve. To avoid too much complexity, my recent designs all involved
a self-contained 256-bit block which combined as many fixed-length
instructions as possible with the variable or large parts they needed.

John Savard

On Thursday, December 30, 2021 at 3:07:59 PM UTC-6, Thomas Koenig wrote:
> Marcus <m.de...@this.bitsnbites.eu> schrieb:
> > On 2021-12-30, EricP wrote:
>
> >> C,C++ and a bunch of languages explicitly define booleans as 0 or 1
> >> so this definition won't be optimal for those languages.
> >> VAX Fortran used 0,-1 for LOGICAL but I don't know if that
> >> was defined by the language or implementation dependant.
> It is implementation defined.
>
> With GNU Fortran, the choice was made to only allow 0 and 1.
> Anything else, and you're likely to end up with random results
> with LOGICAL variables.
>
> One reason for that was that gcc, still a C-centric compiler, is
> geared toward _Bool. Fortran has followed, because the C interop
> sort of prescribes that.
> > As a software developer I'm painfully aware of this. I decided not to
> > care too much about it, though. Really, most software that relies on
> > this property of C should be frowned upon. E.g. expressions like:
> >
> > a = b + (c == d);
> >
> > ...aren't really good programming practice.
> Agreed.
> > I have seen a few places where the compiler does conversions from -1 to
> > +1 (but those have mostly been due to missing/bad pattern matching in
> > the machine description).
> What is the assembly for
>
> _Bool foo (int a, int b)
> {
> return a > b;
> }
>
> for your architecture at a reasonable optimization level?
< O=0
ENTRY foo
foo:
CMP R1,R1,R2
EXT R1,R1,#<GT>
RET

On 12/30/2021 4:37 PM, MitchAlsup wrote:
> On Thursday, December 30, 2021 at 3:07:59 PM UTC-6, Thomas Koenig wrote:
>> Marcus <m.de...@this.bitsnbites.eu> schrieb:
>>> On 2021-12-30, EricP wrote:
>>
>>>> C,C++ and a bunch of languages explicitly define booleans as 0 or 1
>>>> so this definition won't be optimal for those languages.
>>>> VAX Fortran used 0,-1 for LOGICAL but I don't know if that
>>>> was defined by the language or implementation dependant.
>> It is implementation defined.
>>
>> With GNU Fortran, the choice was made to only allow 0 and 1.
>> Anything else, and you're likely to end up with random results
>> with LOGICAL variables.
>>
>> One reason for that was that gcc, still a C-centric compiler, is
>> geared toward _Bool. Fortran has followed, because the C interop
>> sort of prescribes that.
>>> As a software developer I'm painfully aware of this. I decided not to
>>> care too much about it, though. Really, most software that relies on
>>> this property of C should be frowned upon. E.g. expressions like:
>>>
>>> a = b + (c == d);
>>>
>>> ...aren't really good programming practice.
>> Agreed.
>>> I have seen a few places where the compiler does conversions from -1 to
>>> +1 (but those have mostly been due to missing/bad pattern matching in
>>> the machine description).
>> What is the assembly for
>>
>> _Bool foo (int a, int b)
>> {
>> return a > b;
>> }
>>
>> for your architecture at a reasonable optimization level?
> < O=0
> ENTRY foo
> foo:
> CMP R1,R1,R2
> EXT R1,R1,#<GT>
> RET

My case:
foo:
CMPGT R5, R4
MOVT R2
RTS

CMPGT updates SR.T based on the compare.
MOVT copies SR.T to a register.
MOVNT copies !SR.T to a register.

On 30 Dec 2021, Niklas Holsti wrote
(in article <j36lq7Ff1hsU1@mid.individual.net>):

> On 2021-12-30 22:34, MitchAlsup wrote:
> > On Thursday, December 30, 2021 at 1:47:36 PM UTC-6, Marcus wrote:
> > > On 2021-12-30, EricP wrote:
>
> [snip]
>
> > > > C,C++ and a bunch of languages explicitly define booleans as 0 or 1
> > > > so this definition won't be optimal for those languages.
> > > > VAX Fortran used 0,-1 for LOGICAL but I don't know if that
> > > > was defined by the language or implementation dependant.
> > <
> > IIRC Pascal uses 0 and -1
>
> Pascal-the-language has a "boolean" type, with values False and True. I
> believe the machine representation of those values is
> implementation-defined.

Pascal requires that false< true, that true = succ(false), that false =
pred(true),
that ord(false) = 0, and that ord(true) = 1, where succ(), pred() and ord()
are
equivalent to Boolean'Succ(),Boolean'Pred() and Boolean'Pos() in Ada.
This does not enforce representations of 0 and 1, but it's a pretty strong
hint!

--
Bill Findlay

On Thursday, December 30, 2021 at 5:45:28 PM UTC-6, Bill Findlay wrote:
> On 30 Dec 2021, Niklas Holsti wrote
> (in article <j36lq7...@mid.individual.net>):
> > On 2021-12-30 22:34, MitchAlsup wrote:
> > > On Thursday, December 30, 2021 at 1:47:36 PM UTC-6, Marcus wrote:
> > > > On 2021-12-30, EricP wrote:
> >
> > [snip]
> >
> > > > > C,C++ and a bunch of languages explicitly define booleans as 0 or 1
> > > > > so this definition won't be optimal for those languages.
> > > > > VAX Fortran used 0,-1 for LOGICAL but I don't know if that
> > > > > was defined by the language or implementation dependant.
> > > <
> > > IIRC Pascal uses 0 and -1
> >
> > Pascal-the-language has a "boolean" type, with values False and True. I
> > believe the machine representation of those values is
> > implementation-defined.
> Pascal requires that false< true, that true = succ(false), that false =
> pred(true),
> that ord(false) = 0, and that ord(true) = 1, where succ(), pred() and ord()
> are
> equivalent to Boolean'Succ(),Boolean'Pred() and Boolean'Pos() in Ada.
> This does not enforce representations of 0 and 1, but it's a pretty strong
> hint!
<
There are sorts of ring-sum arithmetics which can emulate these requirements;
just not very many that can be efficiently calculated in 2-s complement.
>
> --
> Bill Findlay

On 12/30/2021 10:29 AM, MitchAlsup wrote:
> On Thursday, December 30, 2021 at 6:12:31 AM UTC-6, Marcus wrote:
>> On 2021-12-24, MitchAlsup wrote:
>>> On Friday, December 24, 2021 at 11:00:14 AM UTC-6, Anton Ertl wrote:
>>
>> [snip]
>>
>>>>
>>>> It's pretty obvious that a small implementation of RV64G is smaller
>>>> than a small implementation of A64, and adding the C extension to a
>>>> small implementation of RV64G (to turn it to RV64GC) is reported in
>>>> the talk IIRC (it's on the order of 700 transistors, so still cheap),
>>>> so you can get a small RV64GC cheaper than a small A64 implementation
>>>> and have similar code density.
>>> <
>>> Once you have constructed the register file(s), the integer, memory, and
>>> floating point units, the size of the fetcher and decoder is immaterial
>>> (noise).
>>> <
>>
>> How about branch misprediction penalty? My assumption is that a more
>> complex decoder is likely to require more pipeline stages in the front
>> end, which is likely to hurt when you get branch mispredictions, right?
> <
> The more pipeline stages one has, the less cost a decoder is.
> <
> The wider the pipeline, the higher the relative misprediction costs.
> <
> On the other hand, My team in 1990 figured out how to execute a predicted
> branch in cycle k and be inserting instructions into the execution window
> form the mispredicted direction in cycle k+1. You CAN make the repair
> cost zero cycles, you still eat the delay to calculation of mispredict cycles.

Well, sort of. You are expecting that both-paths predecode will catch
most of the misses, and that's true when the misses are from wrong
loop-counts. But it's not true for data-dependent open code, nor for a
lot of switches, or any poly code in general when the target fanout
exceeds the predecodable fanout. Short pipes help with everything.

On 12/30/2021 1:14 PM, Niklas Holsti wrote:
> On 2021-12-30 22:34, MitchAlsup wrote:
>> On Thursday, December 30, 2021 at 1:47:36 PM UTC-6, Marcus wrote:
>>> On 2021-12-30, EricP wrote:
>
>    [snip]
>
>>>> C,C++ and a bunch of languages explicitly define booleans as 0 or 1
>>>> so this definition won't be optimal for those languages.
>>>> VAX Fortran used 0,-1 for LOGICAL but I don't know if that
>>>> was defined by the language or implementation dependant.
>> <
>> IIRC Pascal uses 0 and -1
>
>
> Pascal-the-language has a "boolean" type, with values False and True. I
> believe the machine representation of those values is
> implementation-defined.
>
> Ada-the-language also has a "Boolean" type, with values False and True,
> but it is defined as an enumeration type with the default representation
> of such types, which means that False is represented as 0 and True as 1.

Yeah. IIRC, that was one I had to beat Jean-Claude up about.

On 12/30/2021 1:07 PM, Thomas Koenig wrote:

> What is the assembly for
>
> _Bool foo (int a, int b)
> {
> return a > b;
> }
>
> for your architecture at a reasonable optimization level?

F("foo") %0 %1;
retn(b0 %2) ^9, // L3C2F0
gtrsb(b0 %0, b1 %1) %2 ^8;
// L3C11F0=/home/ivan/mill/specializer/src/test1.c
//0: |i v%1 v%0 |o ^%0 ^%1 |d v%2 |w ^%2

Optlevel -O0, two instructions, one bundle, one cycle.

On 2021-12-30 22:07, Thomas Koenig wrote:
> Marcus <m.delete@this.bitsnbites.eu> schrieb:
>> On 2021-12-30, EricP wrote:
>
>>> C,C++ and a bunch of languages explicitly define booleans as 0 or 1
>>> so this definition won't be optimal for those languages.
>>> VAX Fortran used 0,-1 for LOGICAL but I don't know if that
>>> was defined by the language or implementation dependant.
>
> It is implementation defined.
>
> With GNU Fortran, the choice was made to only allow 0 and 1.
> Anything else, and you're likely to end up with random results
> with LOGICAL variables.
>
> One reason for that was that gcc, still a C-centric compiler, is
> geared toward _Bool. Fortran has followed, because the C interop
> sort of prescribes that.
>
>> As a software developer I'm painfully aware of this. I decided not to
>> care too much about it, though. Really, most software that relies on
>> this property of C should be frowned upon. E.g. expressions like:
>>
>> a = b + (c == d);
>>
>> ...aren't really good programming practice.
>
> Agreed.
>
>> I have seen a few places where the compiler does conversions from -1 to
>> +1 (but those have mostly been due to missing/bad pattern matching in
>> the machine description).
>
> What is the assembly for
>
> _Bool foo (int a, int b)
> {
> return a > b;
> }
>
> for your architecture at a reasonable optimization level?
>

As a matter of fact, you can now try out MRISC32 on Compiler Explorer
(support was added about a week ago): https://godbolt.org/z/z9sK3MYeM

MRISC32:
slt r1,r2,r1
sub r1,z,r1
ret

Two instructions: compare + convert from -1 to +1.

But I'm not too concerned. MIPS and RISC-V can do that in a single
instruction, but most popular architectures require at least two
instructions.

x86:
cmp edi, esi
setg al
ret

ARMv8:
cmp w0, w1
cset w0, gt
ret

ARMv7:
mov r2, #0
cmp r0, r1
movgt r2, #1
mov r0, r2
bx lr

POWER:
subf 3,3,4
srdi 3,3,63
blr

....etc.

/Marcus

Ivan Godard <ivan@millcomputing.com> schrieb:
> On 12/30/2021 1:07 PM, Thomas Koenig wrote:
>
>> What is the assembly for
>>
>> _Bool foo (int a, int b)
>> {
>> return a > b;
>> }
>>
>> for your architecture at a reasonable optimization level?
>
> F("foo") %0 %1;
> retn(b0 %2) ^9, // L3C2F0
> gtrsb(b0 %0, b1 %1) %2 ^8;
> // L3C11F0=/home/ivan/mill/specializer/src/test1.c
> //0: |i v%1 v%0 |o ^%0 ^%1 |d v%2 |w ^%2

Could you decipher this for the non-initialized? :-)

Marcus <m.delete@this.bitsnbites.eu> schrieb:
> On 2021-12-30 22:07, Thomas Koenig wrote:

>> What is the assembly for
>>
>> _Bool foo (int a, int b)
>> {
>> return a > b;
>> }
>>
>> for your architecture at a reasonable optimization level?
>>
>
> As a matter of fact, you can now try out MRISC32 on Compiler Explorer
> (support was added about a week ago): https://godbolt.org/z/z9sK3MYeM

That is so cool, I think I will throw some code at it and
see how this works out :-)

>
> MRISC32:
> slt r1,r2,r1
> sub r1,z,r1
> ret
>
> Two instructions: compare + convert from -1 to +1.

Looks good.

>
> But I'm not too concerned. MIPS and RISC-V can do that in a single
> instruction, but most popular architectures require at least two
> instructions.

It is actually quite interesting to see the different approaches
the different architectures do

> x86:
> cmp edi, esi
> setg al
> ret

Setting a register from a condition code...

> ARMv8:
> cmp w0, w1
> cset w0, gt
> ret

Same thing here.

> ARMv7:
> mov r2, #0
> cmp r0, r1
> movgt r2, #1
> mov r0, r2
> bx lr

Set the register, compare, set another register, and copy
the register to the return register.

gcc does

cmp r0, r1
ite le
movle r0, #0
movgt r0, #1
bx lr

which looks a little bit better (especially since ite seems
to be a pseudo-op in 32-bit mode, if I read that correctly).

> POWER:
> subf 3,3,4
> srdi 3,3,63
> blr

Subtract and right shift of the sign bit. That's another
way of doing this, I guess. When I saw this, I thought
"Somebody must have been feeling hackish"...

Marcus wrote:
> On 2021-12-30, EricP wrote:
>> C,C++ and a bunch of languages explicitly define booleans as 0 or 1
>> so this definition won't be optimal for those languages.
>> VAX Fortran used 0,-1 for LOGICAL but I don't know if that
>> was defined by the language or implementation dependant.

-1 is better than 1, it can be used as a mask.

>
> As a software developer I'm painfully aware of this. I decided not to
> care too much about it, though. Really, most software that relies on
> this property of C should be frowned upon. E.g. expressions like:
>
>   a = b + (c == d);
>
> ...aren't really good programming practice.

No! Please tell me it ain't so!

I use that type of constructs all over the place when writing branchless
code/doing table lookups etc.

The Dec 24th Advent of Code puzzle had a miniature ALU with no MOV, so
it used "x MUL 0" to zero out x, then x ADD N to actually set it to a
value. X EQL W returned 1/0, which was subsequently used in
multiplications to stand in for branches.

Terje

--
- <Terje.Mathisen at tmsw.no>
"almost all programming can be viewed as an exercise in caching"

On 2021-12-31, Terje Mathisen wrote:
> Marcus wrote:
>> On 2021-12-30, EricP wrote:
>>> C,C++ and a bunch of languages explicitly define booleans as 0 or 1
>>> so this definition won't be optimal for those languages.
>>> VAX Fortran used 0,-1 for LOGICAL but I don't know if that
>>> was defined by the language or implementation dependant.
>
> -1 is better than 1, it can be used as a mask.
>
>>
>> As a software developer I'm painfully aware of this. I decided not to
>> care too much about it, though. Really, most software that relies on
>> this property of C should be frowned upon. E.g. expressions like:
>>
>>    a = b + (c == d);
>>
>> ...aren't really good programming practice.
>
> No! Please tell me it ain't so!

:-)

>
> I use that type of constructs all over the place when writing branchless
> code/doing table lookups etc.

I think that you'll find that the following code produces the exact same
result:

int a;
if (c == d) {
a = b + 1;
} else {
a = b;
}

It too is completely branchless.

My main gripe with the former version is the implicit type conversion
(boolean to integer), and that I don't like to see logical operands and
arithmetic operands mixed in the same expression. Another slightly more
readable version, IMO, would be:

a = b + (c == d ? 1 : 0);

See: https://godbolt.org/z/K7ndn57T1

>
> The Dec 24th Advent of Code puzzle had a miniature ALU with no MOV, so
> it used "x MUL 0" to zero out x, then x ADD N to actually set it to a
> value. X EQL W returned 1/0, which was subsequently used in
> multiplications to stand in for branches.
>
> Terje
>

Marcus <m.delete@this.bitsnbites.eu> schrieb:

> As a matter of fact, you can now try out MRISC32 on Compiler Explorer
> (support was added about a week ago): https://godbolt.org/z/z9sK3MYeM

I could not help but start experimenting with that :-)

I seen no vectorization for

void foo(int * const restrict a, int * const restrict b, int * restrict c, int n)
{ for (int i=0; i<n; i++)
c[i] = a[i]+b[i];
}

and -fopt-info-vec-missed tells me, at https://godbolt.org/z/vPM3KTrnz ,
<source>:3:20: missed: couldn't vectorize loop
<source>:3:20: missed: not vectorized: unsupported data-type

so it seems some more delving into gcc's secret internals
will be required...

Thomas Koenig <tkoenig@netcologne.de> wrote:
> Marcus <m.delete@this.bitsnbites.eu> schrieb:
>> On 2021-12-30 22:07, Thomas Koenig wrote:
>
>>> What is the assembly for
>>>
>>> _Bool foo (int a, int b)
>>> {
>>> return a > b;
>>> }
>>>
>>> for your architecture at a reasonable optimization level?
>>>
>>
>> As a matter of fact, you can now try out MRISC32 on Compiler Explorer
>> (support was added about a week ago): https://godbolt.org/z/z9sK3MYeM
>
>> POWER:
>> subf 3,3,4
>> srdi 3,3,63
>> blr
>
> Subtract and right shift of the sign bit. That's another
> way of doing this, I guess. When I saw this, I thought
> "Somebody must have been feeling hackish"...

Is it even correct? Surely that's (b - a < 0), not (a > b). I think
it'd return true for foo(-0x7fffffff, 0x7fffffff). But I don't know
the POWER ISA at all well, so pls ignore if this is cleverer than I
think. :-).

Andrew.

On 2021-12-31, Thomas Koenig wrote:
> Marcus <m.delete@this.bitsnbites.eu> schrieb:
>
>> As a matter of fact, you can now try out MRISC32 on Compiler Explorer
>> (support was added about a week ago): https://godbolt.org/z/z9sK3MYeM
>
> I could not help but start experimenting with that :-)
>
> I seen no vectorization for
>
> void foo(int * const restrict a, int * const restrict b, int * restrict c, int n)
> {
> for (int i=0; i<n; i++)
> c[i] = a[i]+b[i];
> }
>
> and -fopt-info-vec-missed tells me, at https://godbolt.org/z/vPM3KTrnz ,
> <source>:3:20: missed: couldn't vectorize loop
> <source>:3:20: missed: not vectorized: unsupported data-type
>
> so it seems some more delving into gcc's secret internals
> will be required...
>

Yup! Vectorization is not at all implemented (the compiler doesn't even
know how to use the vector registers), so it's one of the more
interesting improvements to be done to the MRISC32 GCC machine
description.

Since I'm not a compiler guy (at all), I'm pretty happy that I've gotten
this far. Auto-vectorization is not on the near term roadmap,
unfortunately (things like better C++ support is higher up on the prio
list). Also, the vector part of the ISA is not really finalized yet.

Inline assembler is the solution for MRISC32 vector code. E.g:

https://github.com/mbitsnbites/mc1-doom/blob/master/src/r_draw.c#L89

/Marcus

On 12/31/2021 2:28 AM, Thomas Koenig wrote:
> Ivan Godard <ivan@millcomputing.com> schrieb:
>> On 12/30/2021 1:07 PM, Thomas Koenig wrote:
>>
>>> What is the assembly for
>>>
>>> _Bool foo (int a, int b)
>>> {
>>> return a > b;
>>> }
>>>
>>> for your architecture at a reasonable optimization level?
>>
>> F("foo") %0 %1;
>> retn(b0 %2) ^9, // L3C2F0
>> gtrsb(b0 %0, b1 %1) %2 ^8;
>> // L3C11F0=/home/ivan/mill/specializer/src/test1.c
>> //0: |i v%1 v%0 |o ^%0 ^%1 |d v%2 |w ^%2
>
> Could you decipher this for the non-initialized? :-)

Sorry, it has all the annotations turned on, so the reader can see the
belt flow. A key:
L3C1F0 etc: source position (line # etc)
bN: belt reference to the Nth mot recent drop
%N: SSA # for drop
^N: instruction number in ebb
N: cycle number in ebb
|X: phase X (i: immPhase, o: opPhase d: dropPhase
w: writerPhase)
v%N: a drop of %N
^%N: an eval of %N

Removing all the annotations, you get:
F("foo");
retn(b0),gtrsb(b0, b1);

On Friday, December 31, 2021 at 2:43:28 PM UTC+2, a...@littlepinkcloud.invalid wrote:
> Thomas Koenig <tko...@netcologne.de> wrote:
> > Marcus <m.de...@this.bitsnbites.eu> schrieb:
> >> On 2021-12-30 22:07, Thomas Koenig wrote:
> >
> >>> What is the assembly for
> >>>
> >>> _Bool foo (int a, int b)
> >>> {
> >>> return a > b;
> >>> }
> >>>
> >>> for your architecture at a reasonable optimization level?
> >>>
> >>
> >> As a matter of fact, you can now try out MRISC32 on Compiler Explorer
> >> (support was added about a week ago): https://godbolt.org/z/z9sK3MYeM
> >
> >> POWER:
> >> subf 3,3,4
> >> srdi 3,3,63
> >> blr
> >
> > Subtract and right shift of the sign bit. That's another
> > way of doing this, I guess. When I saw this, I thought
> > "Somebody must have been feeling hackish"...
> Is it even correct? Surely that's (b - a < 0), not (a > b). I think
> it'd return true for foo(-0x7fffffff, 0x7fffffff). But I don't know
> the POWER ISA at all well, so pls ignore if this is cleverer than I
> think. :-).
>
> Andrew.

It's about ABI rather than ISA.
If the ABI specifies that 32-bit signed integers parameters that are passed in registers are sign-extened by caller then it is correct.

Marcus wrote:
> On 2021-12-31, Terje Mathisen wrote:
>> Marcus wrote:
>>> On 2021-12-30, EricP wrote:
>>>> C,C++ and a bunch of languages explicitly define booleans as 0 or 1
>>>> so this definition won't be optimal for those languages.
>>>> VAX Fortran used 0,-1 for LOGICAL but I don't know if that
>>>> was defined by the language or implementation dependant.
>>
>> -1 is better than 1, it can be used as a mask.
>>
>>>
>>> As a software developer I'm painfully aware of this. I decided not to
>>> care too much about it, though. Really, most software that relies on
>>> this property of C should be frowned upon. E.g. expressions like:
>>>
>>>    a = b + (c == d);
>>>
>>> ...aren't really good programming practice.
>>
>> No! Please tell me it ain't so!
>
> :-)
>
>>
>> I use that type of constructs all over the place when writing
>> branchless code/doing table lookups etc.
>
> I think that you'll find that the following code produces the exact same
> result:
>
>     int a;
>     if (c == d) {
>         a = b + 1;
>     } else {
>         a = b;
>     }
>
> It too is completely branchless.

In my use of these constructs, the code has typically been written in
asm, with no helpful peephole optimizer to return it to the form I
intended. :-)

I use another form in branchless conversion of julian day number to
y/m/d, i.e. subtraction and arithmetic shift right to convert the result
into a 0/-1 mask.

>
> My main gripe with the former version is the implicit type conversion
> (boolean to integer), and that I don't like to see logical operands and

bool is a newfangled construct, it all used to be just zero/non-zero ints...

> arithmetic operands mixed in the same expression. Another slightly more
> readable version, IMO, would be:
>
>     a = b + (c == d ? 1 : 0);
>
> See: https://godbolt.org/z/K7ndn57T1

I do like the way trigrams keep all the logic in a single assignment.

Terje

--
- <Terje.Mathisen at tmsw.no>
"almost all programming can be viewed as an exercise in caching"

On 31/12/2021 13:37, Marcus wrote:
> On 2021-12-31, Terje Mathisen wrote:
>> Marcus wrote:
>>> On 2021-12-30, EricP wrote:
>>>> C,C++ and a bunch of languages explicitly define booleans as 0 or 1
>>>> so this definition won't be optimal for those languages.
>>>> VAX Fortran used 0,-1 for LOGICAL but I don't know if that
>>>> was defined by the language or implementation dependant.
>>
>> -1 is better than 1, it can be used as a mask.
>>
>>>
>>> As a software developer I'm painfully aware of this. I decided not to
>>> care too much about it, though. Really, most software that relies on
>>> this property of C should be frowned upon. E.g. expressions like:
>>>
>>>    a = b + (c == d);
>>>
>>> ...aren't really good programming practice.
>>
>> No! Please tell me it ain't so!
>
> :-)
>
>>
>> I use that type of constructs all over the place when writing
>> branchless code/doing table lookups etc.
>
> I think that you'll find that the following code produces the exact same
> result:
>
>     int a;
>     if (c == d) {
>         a = b + 1;
>     } else {
>         a = b;
>     }
>
> It too is completely branchless.

Given a good enough compiler, it is branchless. I am a big fan of using
good optimising compilers, so that you can write your source code in the
way you think is clearest and best, and let the compiler worry about the
details of the low-level code optimisations. But it is still useful to
remember that you can't always assume a good compiler.

Also note that on some processors, branched code can be faster than
branchless equivalents.

>
> My main gripe with the former version is the implicit type conversion
> (boolean to integer), and that I don't like to see logical operands and
> arithmetic operands mixed in the same expression.

Some languages have booleans as an integral part of the language and
distinct from arithmetic types. C is not such a language. The
relational operators are defined to give "int" results, and guarantee
that "c == d" will evaluate to 0 or 1. There is no type conversion
here, implicit or otherwise.

C does have a "bool" type (or, more precisely, "_Bool"), but it was
added late (C99) and changing the operators would be a breaking change.

So "a = b + (c == d);" is not, in fact, mixing logical operands and
arithmetic operands in C - it's all arithmetic as far as the language is
concerned.

(You can well argue that the programmer's intention, or the appearance
of the code, is mixing logical and arithmetic operands. And I'd agree -
it's not a style I feel comfortably and clearly expresses the
programmer's intent. It might be appropriate in some circumstances.)

C++ has "bool" built-in, and relational operators (other than the new
spaceship operator) return bool. But for compatibility with C, bool
expressions are implicitly converted to int as needed, and the value is
guaranteed.

(Similarly, the result of "a && b" is an "int" in C, and a "bool" in C++.)

> Another slightly more
> readable version, IMO, would be:
>
>     a = b + (c == d ? 1 : 0);
>
> See: https://godbolt.org/z/K7ndn57T1
>
>>
>> The Dec 24th Advent of Code puzzle had a miniature ALU with no MOV, so
>> it used "x MUL 0" to zero out x, then x ADD N to actually set it to a
>> value. X EQL W returned 1/0, which was subsequently used in
>> multiplications to stand in for branches.
>>
>> Terje
>>
>

I figured I’d throw Thor cc64 compiler output to the mix:

int foo (register int a, register int b)
{ return a > b;
}

Gives:
_foo:
enter 0
slt a0,a1,a0
leave 0

As can been seen I have not got the compiler removing the ENTER and
LEAVE yet, which could be done when only argument registers are used
in the function.

Terje Mathisen wrote:
> Marcus wrote:
>> On 2021-12-30, EricP wrote:
>>> C,C++ and a bunch of languages explicitly define booleans as 0 or 1
>>> so this definition won't be optimal for those languages.
>>> VAX Fortran used 0,-1 for LOGICAL but I don't know if that
>>> was defined by the language or implementation dependant.
>
> -1 is better than 1, it can be used as a mask.

One or the other usage has to do a negate.
The question is which usage, boolean or mask, is more common?
In general it is boolean so it is mask user that should do the negate.

There is a lot of C code that expects that a = b < c; produces 0 or 1.
So if CMP produces a -1 then a C compiler would always generate a NEG too.

For boolean expressions in IF statements the NEG is unnecessary
if the branch tests zero/non-zero and so it might be optimized away.
But that requires the compiler code gen knowing that boolean expressions
in IF statements are not quite the same as other boolean expressions
(and we give a special dispensation to & and | operators on booleans).
Similar rational optimizes any for CMOV conditionals.

It seems easier to have the mask user pay for the NEG.

On Friday, December 31, 2021 at 10:05:12 AM UTC-6, EricP wrote:
> Terje Mathisen wrote:
> > Marcus wrote:
> >> On 2021-12-30, EricP wrote:
> >>> C,C++ and a bunch of languages explicitly define booleans as 0 or 1
> >>> so this definition won't be optimal for those languages.
> >>> VAX Fortran used 0,-1 for LOGICAL but I don't know if that
> >>> was defined by the language or implementation dependant.
> >
> > -1 is better than 1, it can be used as a mask.
> One or the other usage has to do a negate.
<
Which is why it is best for the ISA to have the ability to produce both
0:-1 and 0:+1 and let each language decide for itself which sequence
is best.
<
> The question is which usage, boolean or mask, is more common?
> In general it is boolean so it is mask user that should do the negate.
<
My 66000 even has the instruction to use the mask as a conditional operator
giving an effective bit-by-bit multiplexer ((a&c)|(b&~c)) along with the form
that uses the condition as a selector ((a&!!c)|(a&!c)).
>
> There is a lot of C code that expects that a = b < c; produces 0 or 1.
> So if CMP produces a -1 then a C compiler would always generate a NEG too.
<
s/always/mostly/
<
>
> For boolean expressions in IF statements the NEG is unnecessary
> if the branch tests zero/non-zero and so it might be optimized away.
<
For floating point, one has to give careful consideration to NaNs so that
even after condition inversion that the NaNs go into the else-clause.
<
> But that requires the compiler code gen knowing that boolean expressions
> in IF statements are not quite the same as other boolean expressions
> (and we give a special dispensation to & and | operators on booleans).
> Similar rational optimizes any for CMOV conditionals.
>
> It seems easier to have the mask user pay for the NEG.

EricP wrote:
> Terje Mathisen wrote:
>> Marcus wrote:
>>> On 2021-12-30, EricP wrote:
>>>> C,C++ and a bunch of languages explicitly define booleans as 0 or 1
>>>> so this definition won't be optimal for those languages.
>>>> VAX Fortran used 0,-1 for LOGICAL but I don't know if that
>>>> was defined by the language or implementation dependant.
>>
>> -1 is better than 1, it can be used as a mask.
>
> One or the other usage has to do a negate.
> The question is which usage, boolean or mask, is more common?
> In general it is boolean so it is mask user that should do the negate.
>
> There is a lot of C code that expects that a = b < c; produces 0 or 1.
> So if CMP produces a -1 then a C compiler would always generate a NEG too.
>
> For boolean expressions in IF statements the NEG is unnecessary
> if the branch tests zero/non-zero and so it might be optimized away.
> But that requires the compiler code gen knowing that boolean expressions
> in IF statements are not quite the same as other boolean expressions
> (and we give a special dispensation to & and | operators on booleans).
> Similar rational optimizes any for CMOV conditionals.
>
> It seems easier to have the mask user pay for the NEG.

It is of course _far_ too late to change it in C (or most existing
languages/compilers), but please notice that all the SIMD vector
instruction sets I have seen tend to use 0/-1, specifically because that
is usable as a mask.

x86 also has a movemask* opcode which extracts the top bit from each
element and pack them together into an integer register, this makes it
suitable to verify "Any matching element?" after first doing a SIMD compare.

Terje

--
- <Terje.Mathisen at tmsw.no>
"almost all programming can be viewed as an exercise in caching"

On 12/31/2021 7:27 AM, Terje Mathisen wrote:
> Marcus wrote:
>> On 2021-12-31, Terje Mathisen wrote:
>>> Marcus wrote:
>>>> On 2021-12-30, EricP wrote:
>>>>> C,C++ and a bunch of languages explicitly define booleans as 0 or 1
>>>>> so this definition won't be optimal for those languages.
>>>>> VAX Fortran used 0,-1 for LOGICAL but I don't know if that
>>>>> was defined by the language or implementation dependant.
>>>
>>> -1 is better than 1, it can be used as a mask.
>>>

(!x-1)

>>>>
>>>> As a software developer I'm painfully aware of this. I decided not to
>>>> care too much about it, though. Really, most software that relies on
>>>> this property of C should be frowned upon. E.g. expressions like:
>>>>
>>>>    a = b + (c == d);
>>>>
>>>> ...aren't really good programming practice.
>>>
>>> No! Please tell me it ain't so!
>>
>> :-)
>>
>>>
>>> I use that type of constructs all over the place when writing
>>> branchless code/doing table lookups etc.
>>
>> I think that you'll find that the following code produces the exact same
>> result:
>>
>>      int a;
>>      if (c == d) {
>>          a = b + 1;
>>      } else {
>>          a = b;
>>      }
>>
>> It too is completely branchless.
>
> In my use of these constructs, the code has typically been written in
> asm, with no helpful peephole optimizer to return it to the form I
> intended. :-)
>

The use of an "if()" branch this way, while (likely) branchless in my
case, could be less efficient in many cases due to implementing both
branches via predicated ops rather than by putting the value into a
register.

Say:
a = b + (c == d);

Could be handled as:
CMPEQ R5, R6
MOVT R7
ADD R4, R7, R2

( Using ADC here is possible, but BGBCC will not do so. Something like
"ADC R4, 0, R2" would allow doing it in 2 instructions, but no encoding
exists for this. )

If Branch:
CMPEQ R5, R6
ADD?T R4, 1, R2
MOV?F R4, R2

But, not much difference in this case in terms of clock cycles (it would
be a little worse if a branch were used, but this is part of why I ended
up adding predicated ops in the first place...).

One can't nest them or use complex conditionals, but this isn't usually
a big issue.

Granted, predicated ops are a relative minority (say, only ~ 6% of
constant loads end up predicated, fewer in other categories, ...), but
they can save more cycles than implied by their fairly limited range of
use-cases.

> I use another form in branchless conversion of julian day number to
> y/m/d, i.e. subtraction and arithmetic shift right to convert the result
> into a 0/-1 mask.
>

We need to convince the world to going over to define units of time in
terms of megaseconds and gigaseconds.

Like, one could describe themselves as an ancient vampire who has been
on this Earth for a little over 1 gigasecond...

>>
>> My main gripe with the former version is the implicit type conversion
>> (boolean to integer), and that I don't like to see logical operands and
>
> bool is a newfangled construct, it all used to be just zero/non-zero
> ints...
>

Yeah, _Bool can be defined as:
Integer type whose only defined values are 0 or 1.
Storage size is whatever is both small and convenient.

In BGBCC, the _Bool type basically reduces to an alias for 'unsigned
char', differing in a few contexts, but generally equivalent.

Using 1 bit storage could be more compact, but in many cases trying to
bit-pack these values would be slower than using bytes (and for
bit-packed flags one is probably much better off using
"if(flags&FOO_FLAG)" or similar).

IIRC, there is special case logic in the compiler for casting to _Bool.
So, (_Bool)(expr) => ((expr)!=0)

>> arithmetic operands mixed in the same expression. Another slightly more
>> readable version, IMO, would be:
>>
>>      a = b + (c == d ? 1 : 0);
>>
>> See: https://godbolt.org/z/K7ndn57T1
>
> I do like the way trigrams keep all the logic in a single assignment.
>
> Terje
>