On Friday, December 16, 2022 at 11:34:01 AM UTC-6, BGB wrote:
> On 12/16/2022 10:43 AM, MitchAlsup wrote:
> > On Friday, December 16, 2022 at 10:23:00 AM UTC-6, BGB wrote:
> >> On 12/16/2022 10:00 AM, Thomas Koenig wrote:
> >>> BGB <cr8...@gmail.com> schrieb:
> >>>> On 12/15/2022 1:07 AM, Thomas Koenig wrote:
> >>>>> BGB <cr8...@gmail.com> schrieb:
> >>>>>
> >>>>> (argument list)
> >>>>>
> >>>>>> So, it looks like (looking at a few different programs):
> >>>>>> 4: ~79.2%
> >>>>>> 8: ~98.6%
> >>>>>> 15: ~99.9%
> >>>>>> 16: ~99.9%
> >>>>>> 18: 100%
> >>>>>
> >>>>> Did you ever take a look at LAPACK, or CLAPACK? Those are _long_
> >>>>> argument lists...
> >>>>>
> >>>>> For example, dgerfsx has 22 arguments (unless I miscounted) plus
> >>>>> two hidden character length arguments.
> >>>>
> >>>> None of my code has quite that many.
> >>>> The longest argument list currently is in my GLQuake port, mostly due to
> >>>> an 18 argument function being used in TKRA-GL.
> >>>>
> >>>> But, I guess one could debate if there are many codebases which deviate
> >>>> strongly from this, having a lot more long argument lists than short ones.
> >>>>
> >>>> Between Doom, ROTT, Quake, etc, specifics vary slightly, but the overall
> >>>> pattern remains pretty similar.
> >>>>
> >>>> So, it seems like:
> >>>> 8 will be sufficient "most of the time";
> >>>> 16 is slightly better;
> >>>> 24 or 32 would be needed to entirely eliminate the existence of stack
> >>>> arguments.
> >>>
> >>> You don't have experience with other people using your compiler,
> >>> I presume.
> >>>
> >>> If somebody puts an artificial limitation like that into a widely
> >>> used ABI or compiler, then somebody out there will run across that
> >>> limitation and post a bug report.
> >>>
> >>> Some people fuzz compilers as a hobby.
> >> There are no hard limit on the number of arguments in BGBCC.
> >>
> > In My 66000 ABI there is a limit of 8 register passed arguments (and results)
> > the rest are passed on the stack. An unconcerned programmer does not
> > need to even see that there is a limit. The performance aware programmer
> > will see higher performance with 8 or fewer arguments.
<
> The number of register arguments is limited by the ABI mode in question.
> The total maximum number of arguments is unbounded.
>
>
> I haven't yet settled on which ABI I will make the official ABI for XG2
> mode.
>
>
> While arguably "more register arguments is better", "more spill space is
> not better". Burning 256 bytes of the stack (rather than 128 bytes) for
> every non-leaf function seems to offset any gains from passing more
> arguments in registers (since, as noted, more than 8 is uncommon; at
> least for code using 64-bit pointers).
<
The amount of excess space on My 66000 stack is 0 bytes. The amount of
space in local_data_area is "whatever the compiler wants". The compiler
allocates 0 bytes that are not used.
<
As to "more is always better"; I am not so sure. With 8 registers used to pass
arguments, and 16 (including FP and SP) preserved registers, there are 8
freely used temporaries for leaf functions to "do stuff" without overhead.
If you increased the register arguments to 16 without addressing the free
temporaries, you end up having to save/restore some registers in order
to "do stuff", and based on your statistics, these account for only 1.4%
of subroutines.
<
>
> This almost makes a stronger case for not providing any spill space.
<
Which I do not.
> >>
> >> More, it is a case of avoiding stack arguments (entirely, if-possible)
> >> is better for performance in a strictly in-order machine.
> >>
> >> As for the ABI, it is sort of like:
> >> First 8 (or 16) arguments are passed in registers;
> >> Any remaining arguments are passed on the stack.
> >>
> >> There is also a spill space for the register arguments (in the 64-bit
> >> ABI), with the remaining arguments being after the spill space.
> > <
> > I worked out positions for the register and memory based arguments
> > such that the stack has "no excess space allocated" and "you can concatenate"
> > the register and memory spaces using ENTER--and indeed, this is how
> > varargs works.
<
> I wanted to go over to a "you can naively spill the registers to the
> stack and get back to a linear argument list like on x86" model.
<
While you can't do it naïvely, there is a straightforward way to achieve
this goal of a vector of arguments for varargs--and in My 66000 you
can achieve this at the cost of 0 extra instructions !
>
> The original ABI did not do this, so the "va_list" structure is more of
> a snapshot of all the argument registers followed by a pointer to the
> first non-register argument (as was needed for the original ABI).
>
It is even worse with multiple register files.
>
> As noted, the design for my ABI was somewhat influenced by the Windows
> X64 ABI (well, and also the Windows CE SH-4 ABI, from which it was also
> partially derived).
>
> There was also the Hitachi ABI, and GCC's SH-4 ABI, where ironically all
> were "similar but different", as even with the same ISA, seemingly no
> two parties can agree as to what exactly the C ABI rules should be...
>
>
> Would hope it would stay more consistent in my case, but seemingly I
> can't agree with myself as to what exactly the C ABI rules should be in
> some cases (hence why, annoyingly, the ABI has fragmented into
> sub-variants).
<
Auld lang syne ?

On 12/16/2022 2:28 PM, MitchAlsup wrote:
> On Friday, December 16, 2022 at 11:34:01 AM UTC-6, BGB wrote:
>> On 12/16/2022 10:43 AM, MitchAlsup wrote:
>>> On Friday, December 16, 2022 at 10:23:00 AM UTC-6, BGB wrote:
>>>> On 12/16/2022 10:00 AM, Thomas Koenig wrote:
>>>>> BGB <cr8...@gmail.com> schrieb:
>>>>>> On 12/15/2022 1:07 AM, Thomas Koenig wrote:
>>>>>>> BGB <cr8...@gmail.com> schrieb:
>>>>>>>
>>>>>>> (argument list)
>>>>>>>
>>>>>>>> So, it looks like (looking at a few different programs):
>>>>>>>> 4: ~79.2%
>>>>>>>> 8: ~98.6%
>>>>>>>> 15: ~99.9%
>>>>>>>> 16: ~99.9%
>>>>>>>> 18: 100%
>>>>>>>
>>>>>>> Did you ever take a look at LAPACK, or CLAPACK? Those are _long_
>>>>>>> argument lists...
>>>>>>>
>>>>>>> For example, dgerfsx has 22 arguments (unless I miscounted) plus
>>>>>>> two hidden character length arguments.
>>>>>>
>>>>>> None of my code has quite that many.
>>>>>> The longest argument list currently is in my GLQuake port, mostly due to
>>>>>> an 18 argument function being used in TKRA-GL.
>>>>>>
>>>>>> But, I guess one could debate if there are many codebases which deviate
>>>>>> strongly from this, having a lot more long argument lists than short ones.
>>>>>>
>>>>>> Between Doom, ROTT, Quake, etc, specifics vary slightly, but the overall
>>>>>> pattern remains pretty similar.
>>>>>>
>>>>>> So, it seems like:
>>>>>> 8 will be sufficient "most of the time";
>>>>>> 16 is slightly better;
>>>>>> 24 or 32 would be needed to entirely eliminate the existence of stack
>>>>>> arguments.
>>>>>
>>>>> You don't have experience with other people using your compiler,
>>>>> I presume.
>>>>>
>>>>> If somebody puts an artificial limitation like that into a widely
>>>>> used ABI or compiler, then somebody out there will run across that
>>>>> limitation and post a bug report.
>>>>>
>>>>> Some people fuzz compilers as a hobby.
>>>> There are no hard limit on the number of arguments in BGBCC.
>>>>
>>> In My 66000 ABI there is a limit of 8 register passed arguments (and results)
>>> the rest are passed on the stack. An unconcerned programmer does not
>>> need to even see that there is a limit. The performance aware programmer
>>> will see higher performance with 8 or fewer arguments.
> <
>> The number of register arguments is limited by the ABI mode in question.
>> The total maximum number of arguments is unbounded.
>>
>>
>> I haven't yet settled on which ABI I will make the official ABI for XG2
>> mode.
>>
>>
>> While arguably "more register arguments is better", "more spill space is
>> not better". Burning 256 bytes of the stack (rather than 128 bytes) for
>> every non-leaf function seems to offset any gains from passing more
>> arguments in registers (since, as noted, more than 8 is uncommon; at
>> least for code using 64-bit pointers).
> <
> The amount of excess space on My 66000 stack is 0 bytes. The amount of
> space in local_data_area is "whatever the compiler wants". The compiler
> allocates 0 bytes that are not used.
> <
> As to "more is always better"; I am not so sure. With 8 registers used to pass
> arguments, and 16 (including FP and SP) preserved registers, there are 8
> freely used temporaries for leaf functions to "do stuff" without overhead.
> If you increased the register arguments to 16 without addressing the free
> temporaries, you end up having to save/restore some registers in order
> to "do stuff", and based on your statistics, these account for only 1.4%
> of subroutines.
> <

Probably true.

Though, should have been 128 vs 64, not 256 vs 128.

It would appear that 8 may be a better option than 16, even with 64 GPRs
(and ~ 30 usable scratch registers).

So, a small extra cost for 1.5% of functions (them needing to use stack
arguments past the first 8), may not be worth a relatively small cost
being paid by every other function (mostly in terms of bigger stack
frames reducing the effectiveness of the 9-bit load/store displacement).

This is since addressing is relative to the bottom of the stack, and
thus has to address over the callee's spill space and similar.

If the stack frame exceeds the range of a 9-bit displacement, this also
means a penalty for accessing any variables stored in the spill space,
since these may now require using a bigger displacement to cross the
stack frame (vs had they been stored along with the other local
variables and similar, in my case typically closer to the bottom of the
stack frame).

>>
>> This almost makes a stronger case for not providing any spill space.
> <
> Which I do not.

It varies a bit.

There seem to be two different camps for ABI design:

SysV style ABIs:
Typically no spill space;
Structures are passed by copying them in registers or on the stack;
(They often decompose structures into registers, ...)
...

Microsoft Style:
Typically provide a spill space,
usually equal to the number of register arguments;
Typically pass and return structures by reference;
...

I had noted that the official RISC-V ABI seems to follow SysV patterns.

MS seems to list a Machine ID for RISC-V in PE/COFF, but no ABI spec to
be found, so it is uncertain if they adopted the RISC-V ABI as-is or
have their own.

I have found exceptions to both patterns though:
SysV MIPS ABI has a spill space for arguments;
The MS ARMv8 ABI seems to follow SysV patterns;
( I am guessing they adopted ARM's ABI as-is?... )
...

I can note that the BJX2 ABI mostly follows patterns similar to the
Microsoft style ABIs.

Eg:
Spill space (in 64b/128b variants);
Structures passed by reference (if > 16B);
Struct return by copying to caller-supplied pointer (if > 16B);
...

>>>>
>>>> More, it is a case of avoiding stack arguments (entirely, if-possible)
>>>> is better for performance in a strictly in-order machine.
>>>>
>>>> As for the ABI, it is sort of like:
>>>> First 8 (or 16) arguments are passed in registers;
>>>> Any remaining arguments are passed on the stack.
>>>>
>>>> There is also a spill space for the register arguments (in the 64-bit
>>>> ABI), with the remaining arguments being after the spill space.
>>> <
>>> I worked out positions for the register and memory based arguments
>>> such that the stack has "no excess space allocated" and "you can concatenate"
>>> the register and memory spaces using ENTER--and indeed, this is how
>>> varargs works.
> <
>> I wanted to go over to a "you can naively spill the registers to the
>> stack and get back to a linear argument list like on x86" model.
> <
> While you can't do it naïvely, there is a straightforward way to achieve
> this goal of a vector of arguments for varargs--and in My 66000 you
> can achieve this at the cost of 0 extra instructions !

In the 8-arg case, it can be done with 4 MOV.X instructions.

>>
>> The original ABI did not do this, so the "va_list" structure is more of
>> a snapshot of all the argument registers followed by a pointer to the
>> first non-register argument (as was needed for the original ABI).
>>
> It is even worse with multiple register files.

Yeah.

>>
>> As noted, the design for my ABI was somewhat influenced by the Windows
>> X64 ABI (well, and also the Windows CE SH-4 ABI, from which it was also
>> partially derived).
>>
>> There was also the Hitachi ABI, and GCC's SH-4 ABI, where ironically all
>> were "similar but different", as even with the same ISA, seemingly no
>> two parties can agree as to what exactly the C ABI rules should be...
>>
>>
>> Would hope it would stay more consistent in my case, but seemingly I
>> can't agree with myself as to what exactly the C ABI rules should be in
>> some cases (hence why, annoyingly, the ABI has fragmented into
>> sub-variants).
> <
> Auld lang syne ?

On Friday, December 16, 2022 at 8:22:22 PM UTC-6, BGB wrote:
> On 12/16/2022 2:28 PM, MitchAlsup wrote:
>> There seem to be two different camps for ABI design:
>
> SysV style ABIs:
> Typically no spill space;
> Structures are passed by copying them in registers or on the stack;
> (They often decompose structures into registers, ...)
> ...
>
> Microsoft Style:
> Typically provide a spill space,
> usually equal to the number of register arguments;
> Typically pass and return structures by reference;
> ...
>
>
> I had noted that the official RISC-V ABI seems to follow SysV patterns.
<
MIPS has a spill space............And I see now that RISC-V has corrected that.......
>
snip
> > While you can't do it naïvely, there is a straightforward way to achieve
> > this goal of a vector of arguments for varargs--and in My 66000 you
> > can achieve this at the cost of 0 extra instructions !
<
> In the 8-arg case, it can be done with 4 MOV.X instructions.
<
Preserving some registers, and allocating a stack costs me 1 instruction.
<
ENTER R26,R0,#local_data_area_size
<
Pushing the register arguments, preserving some registers, and allocating
a stack still costs only 1 instruction !
<
ENTER R26,R9,#local_data_area_size
<
You do it in 4 more instructions, I do it in an already existing instruction.
>
>
> It seems though that in many cases, things are built around things that
> happened in the past, either their own lives, or by interpreting various
> texts and deriving rules from them, looking to various sources for
> precedent on which to base their decisions, ...
>
>
> But, when there is a line of development, then some patterns are likely
> to exist here. Like, if one tries to design some of their tech initially
> by trying to imitate stuff from, say, "Windows CE on a Sega Dreamcast",
> then things will tend to follow patterns.
>
> If one takes the ISA, and at first doubles, and then later doubles
> again, the number of CPU registers, the patterns may still hold.
>
> Say:
> R4..R7
> Became:
> R4..R7, R20..R23
> Becomes:
> R4..R7, R20..R23, R36..R39, R52..R55
<
This is why you have to get it right the first time.
>
> But, the stack pointer still remains awkwardly stuck at R15, as to move
> it basically causes everything else to fall apart.
>
Because they did not get it right the first time.
>

On 12/16/2022 10:01 AM, Scott Lurndal wrote:
> Thomas Koenig <tkoenig@netcologne.de> writes:
>> BGB <cr88192@gmail.com> schrieb:
>>
>>> Then again, I guess it was interesting to observe that some types of
>>> optimizations which help on BJX2 also help on x86-64, despite x86-64
>>> having not enough registers to actually make use of the optimization as
>>> expressed (x86-64 seems to be able to pretend as-if the stack
>>> spills/fills were registers).
>>
>> This is as old as optimizing compilers. The very first FORTRAN
>> compiler assumed that there was an infinite amount of index
>> registers, which it then later on assigned to the three that were
>> actually available.
>>

I was thinking more in the sense that it seems to behave as-if it could
load from memory into a register in 1 cycle, even if realistically this
should take ~ 4 cycles on x86-64.

Say, one x86-64, one can do a version of a piece of logic:
2 operations at a time, using 10 variables;
4 operations at a time, using 20 variables.

x86-64 has 16 registers, so one would expect the 10 variable version to
be faster than the 20 variable version. But, one may observe the 20
variable case is still faster.

Contrast, a lot of 90s era code seems to use small loops using as few
variables as possible to process one item at a time, which tends to be
slower (on both x86-64 and BJX2) than aggressively unrolling the loop
and doing a bunch of items in parallel (often using significantly more
working variables; and writing code that resembles ASM if written in C
syntax).

>>> Meanwhile, I am left needing to use lots of registers, and occasional
>>> optimizations which try to side-step a few (store then load) cases, then
>>> recently needing to fix a bug where one of these optimizations broke due
>>> to a type-handling issue in my compiler (was using the type of the value
>>> stored to an array, rather than the type of the value as loaded from the
>>> array).
>>
>> Did you actually look at optimizing register allocation algorithms?
>> http://web.cecs.pdx.edu/~mperkows/temp/register-allocation.pdf is one
>> of the first search results that Google (well, Startpage) returns.
>> You should really look into graph coloring.
>
> I'd recommend starting with the Dragon book, which discusses register
> allocation fairly extensively, in multiple contexts.

I had just sort of came up with something over time.

Might need to look into some more stuff...

In my compilers, I mostly used fairly simple/naive strategy:
Maintain a list of "live" variables;
If a variable is accessed, and not in the list, add it to list and load
it from memory (if used as a source variable);
If no free spots in the list, find something to evict (LRU style);
Write all non-statically-assigned dirty variables back to memory at the
end of the basic block (and set their entries back to empty).

So, variables will typically be loaded each time when they are first
used, with a blob of stack spills at the end of the block.

The demand-loaded variables often come with a 3-cycle or so penalty (to
avoid this requires loading them before they are used).

Though, not particularly optimal, attempts to improve on this have not
generally been successful (either making things worse, or causing the
program to break).

A lot of my JITs also used this strategy, just working on "traces".

Then, with a few options:
The N most-used variables get assigned to the first N spots in the list
for the entire function;
If we have more registers than variables (both locals and temporaries),
everything gets static-assigned.

Performance is generally better when more of the variables can be
static-assigned.

Say, if you have 30 callee-saved registers and 20 variables, well then,
every variable can get its own register for the scope of the function,
and the spill-and-fill disappears (at least for local variables and
similar).

Even if not perfect, it still seems better than the "-O0" or "/O0"
strategies in GCC and MSVC, which do everything as "Load; Load; Op; Store".

But, yeah, by "-O1" or "-O2" GCC's code generation tends to somewhat
beat my compiler on this front (or even MSVC's).

But, yeah, I have noted that other compilers tend to be more effective here.

The WEXifier can try to help (by trying to shuffle the instructions
around after-the-fact; in machine-code form), but its effectiveness is
in turn limited (and having lots of registers and giving every variable
its own register makes the WEXifier's job easier, vs trying to reuse
registers within the basic-block; but avoiding register reuse within a
block does increase register pressure slightly).

There are also high level transforms, like say:
foo->x = a;
foo->y = b;
...
c = foo->x + foo->y;
One might be tempted to try to transform the last expression to:
c = a + b;

But, a bunch of extra checks are needed to try to exclude cases where
this is not valid (such as a depended-on variable being modified, ...).

And, as noted, the 'foo->x' still needs to return the type of 'foo->x'
and not the type of 'a'.

This transform was generally being done in the front-end in this case
(where bugs here were changing the types "as seen by the C code").

This mapping was being done with a sort of lookup table operating mostly
at the level of local variables (and "reducing" expressions in terms of
AST nodes).

In a few of my past languages (namely the original BGBScript), a similar
strategy was also used for type-inference (before later switching
primarily to explicit declared types); and also for constant-propagation.

Say:
a=3;
b=4;
c=a+b;
And the compiler realizes it can rewrite the last expression to:
c=7;

This strategy was also generally limited to a single basic-block at a
time (the contents of the table being "forgotten" at the end of each block).

....

On 12/16/2022 8:58 PM, MitchAlsup wrote:
> On Friday, December 16, 2022 at 8:22:22 PM UTC-6, BGB wrote:
>> On 12/16/2022 2:28 PM, MitchAlsup wrote:
>>> There seem to be two different camps for ABI design:
>>
>> SysV style ABIs:
>> Typically no spill space;
>> Structures are passed by copying them in registers or on the stack;
>> (They often decompose structures into registers, ...)
>> ...
>>
>> Microsoft Style:
>> Typically provide a spill space,
>> usually equal to the number of register arguments;
>> Typically pass and return structures by reference;
>> ...
>>
>>
>> I had noted that the official RISC-V ABI seems to follow SysV patterns.
> <
> MIPS has a spill space............And I see now that RISC-V has corrected that.......

But, not found any clear information as to why a spill space is either
good or bad (apart from the issue of not scaling up very well by putting
more strain on the displacement distance).

Effect on performance either way seems to be fairly small, though it
does seem to effect code density.

For things like trying to wrangle function argument lists across an RPC
mechanism, the spill-space makes things easier.

Some descriptions of the Windows X64 ABI also made a case for why
spill-space was a good thing.

I have ABI variants both with and without a spill-space.
Was using the "no spill space" variant for code built with
"sizeof(void*)==4".

>>
> snip
>>> While you can't do it naïvely, there is a straightforward way to achieve
>>> this goal of a vector of arguments for varargs--and in My 66000 you
>>> can achieve this at the cost of 0 extra instructions !
> <
>> In the 8-arg case, it can be done with 4 MOV.X instructions.
> <
> Preserving some registers, and allocating a stack costs me 1 instruction.
> <
> ENTER R26,R0,#local_data_area_size
> <
> Pushing the register arguments, preserving some registers, and allocating
> a stack still costs only 1 instruction !
> <
> ENTER R26,R9,#local_data_area_size
> <
> You do it in 4 more instructions, I do it in an already existing instruction.

I don't have fancy instructions here.

I have MOV.X and ADD and similar...

Say:
MOV LR, R18
MOV GBR, R19
ADD -128, SP
MOV.X R18, (SP, 112)
MOV.X R8, (SP, 64)
MOV.X R10, (SP, 80)
MOV.X R12, (SP, 96)
...

If I were doing it again, might want LR and GBR in GPR space, so that I
could use MOV.X to store and reload them directly.

>>
>>
>> It seems though that in many cases, things are built around things that
>> happened in the past, either their own lives, or by interpreting various
>> texts and deriving rules from them, looking to various sources for
>> precedent on which to base their decisions, ...
>>
>>
>> But, when there is a line of development, then some patterns are likely
>> to exist here. Like, if one tries to design some of their tech initially
>> by trying to imitate stuff from, say, "Windows CE on a Sega Dreamcast",
>> then things will tend to follow patterns.
>>
>> If one takes the ISA, and at first doubles, and then later doubles
>> again, the number of CPU registers, the patterns may still hold.
>>
>> Say:
>> R4..R7
>> Became:
>> R4..R7, R20..R23
>> Becomes:
>> R4..R7, R20..R23, R36..R39, R52..R55
> <
> This is why you have to get it right the first time.

Whole thing started out with 16 registers, then doubled it twice.
No obvious "better" option than to repeat the existing pattern 2 or 4 times.

The strategy does allow one to determine if a register is callee saved
fairly easily:
if(regID&8)
{ callee-saved }
else
{ scratch }

Except for a few special cases.

With argument registers following a pattern:
zz01zz

A lot of other ISA's will require using ad-hoc lookup tables here.

>>
>> But, the stack pointer still remains awkwardly stuck at R15, as to move
>> it basically causes everything else to fall apart.
>>
> Because they did not get it right the first time.
>>
>

Yeah, there are reasons a lot of my considered full-ISA redesigns had
things like, say:
R0=ZR/PC (ZR|PC depends on context)
R1=LR
R2=SP
R3=GBR

But, XG2 was not a sufficient redesign for me to consider this, so XG2
keeps using the existing BJX2 register map (it is essentially being
treated more like an alt-mode encoding scheme rather than an entirely
separate ISA).

Though, strictly speaking, there is not a whole lot left in XG2 (at the
level of encoding or semantics) that actually cares which register is
being used as the stack pointer (most of this was in the 16-bit ops with
hard-wired implicit registers, which are N/E in XG2 mode).

Though, in the near term, this is unlikely to change short of other
architectural changes.

....

On 12/16/2022 9:56 AM, Thomas Koenig wrote:
> BGB <cr88192@gmail.com> schrieb:
>
>> Then again, I guess it was interesting to observe that some types of
>> optimizations which help on BJX2 also help on x86-64, despite x86-64
>> having not enough registers to actually make use of the optimization as
>> expressed (x86-64 seems to be able to pretend as-if the stack
>> spills/fills were registers).
>
> This is as old as optimizing compilers. The very first FORTRAN
> compiler assumed that there was an infinite amount of index
> registers, which it then later on assigned to the three that were
> actually available.
>
>> Meanwhile, I am left needing to use lots of registers, and occasional
>> optimizations which try to side-step a few (store then load) cases, then
>> recently needing to fix a bug where one of these optimizations broke due
>> to a type-handling issue in my compiler (was using the type of the value
>> stored to an array, rather than the type of the value as loaded from the
>> array).
>
> Did you actually look at optimizing register allocation algorithms?
> http://web.cecs.pdx.edu/~mperkows/temp/register-allocation.pdf is one
> of the first search results that Google (well, Startpage) returns.
> You should really look into graph coloring.

Looks some at the linked PDF.

Yeah, BGBCC doesn't do anything like this.

Only two levels:
Within a given basic-block;
Or, global for the whole function.

Would have to figure out how to try to glue on something like graph
coloring, seems like a more advanced type of optimization than most of
the stuff I had been doing...

And, well, the "maybe stupid" assumption that if one typically has more
registers in the ISA than local variables and temporaries in the
function, they can static-assign everything and mostly sweep the
register-allocation issues under the carpet.

Well, pros/cons...

There are also issues, like trying to weed out the sources that are
generating a bunch of spurious (and frivolous) RegReg MOVs (one can fix
them in one case, and find more frivolous MOVs somewhere else, or a
bunch of otherwise unnecessary sign or zero extension operations, ...).

Then again, I guess it remains as an open question of what performance
would look like if my optimizer didn't suck...

Then again, I guess no one is claiming that writing a "good quality" C
compiler is particularly fast or easy (getting something that "sorta
works" hacked together isn't too bad; getting it to generate decent
quality output and relatively bug-free is a whole different issue).

....

On Saturday, December 17, 2022 at 12:23:44 AM UTC-5, BGB wrote:
> On 12/16/2022 9:56 AM, Thomas Koenig wrote:
> > BGB <cr8...@gmail.com> schrieb:
> >
> >> Then again, I guess it was interesting to observe that some types of
> >> optimizations which help on BJX2 also help on x86-64, despite x86-64
> >> having not enough registers to actually make use of the optimization as
> >> expressed (x86-64 seems to be able to pretend as-if the stack
> >> spills/fills were registers).
> >
> > This is as old as optimizing compilers. The very first FORTRAN
> > compiler assumed that there was an infinite amount of index
> > registers, which it then later on assigned to the three that were
> > actually available.
> >
> >> Meanwhile, I am left needing to use lots of registers, and occasional
> >> optimizations which try to side-step a few (store then load) cases, then
> >> recently needing to fix a bug where one of these optimizations broke due
> >> to a type-handling issue in my compiler (was using the type of the value
> >> stored to an array, rather than the type of the value as loaded from the
> >> array).
> >
> > Did you actually look at optimizing register allocation algorithms?
> > http://web.cecs.pdx.edu/~mperkows/temp/register-allocation.pdf is one
> > of the first search results that Google (well, Startpage) returns.
> > You should really look into graph coloring.
> Looks some at the linked PDF.
>
> Yeah, BGBCC doesn't do anything like this.
>
> Only two levels:
> Within a given basic-block;
> Or, global for the whole function.
>
> Would have to figure out how to try to glue on something like graph
> coloring, seems like a more advanced type of optimization than most of
> the stuff I had been doing...
>
>
> And, well, the "maybe stupid" assumption that if one typically has more
> registers in the ISA than local variables and temporaries in the
> function, they can static-assign everything and mostly sweep the
> register-allocation issues under the carpet.
>
> Well, pros/cons...
>
>
> There are also issues, like trying to weed out the sources that are
> generating a bunch of spurious (and frivolous) RegReg MOVs (one can fix
> them in one case, and find more frivolous MOVs somewhere else, or a
> bunch of otherwise unnecessary sign or zero extension operations, ...).
>
>
> Then again, I guess it remains as an open question of what performance
> would look like if my optimizer didn't suck...
>
>
> Then again, I guess no one is claiming that writing a "good quality" C
> compiler is particularly fast or easy (getting something that "sorta
> works" hacked together isn't too bad; getting it to generate decent
> quality output and relatively bug-free is a whole different issue).
>
>
> ...
Yes. I came to realize that compilers are quite an undertaking. I only work
on the compiler periodically now, preferring to use VBCC. Had a look at
GCC and LLVM.

Here is another link on color-graphing. I spent quite a bit of time reading and
re-reading this until I was able to come up with a yet to get working properly
color graphing allocator for my compiler. I think there are issues with register
spills and reloads. Then I found out that if there are enough registers > 16
maybe color graphing is not so necessary.

https://www.cs.utexas.edu/users/mckinley/380C/lecs/briggs-thesis-1992.pdf

I believe a linear scan allocator is another common allocator.

I have the code for the allocator in my Github account. It is quite complex,
written in c++.

The allocator I currently use simply counts register usages, giving more counts
for registers used in a loop. And prioritizes register allocations that way.

On Saturday, December 17, 2022 at 3:49:46 AM UTC-5, robf...@gmail.com wrote:
> On Saturday, December 17, 2022 at 12:23:44 AM UTC-5, BGB wrote:
> > On 12/16/2022 9:56 AM, Thomas Koenig wrote:
> > > BGB <cr8...@gmail.com> schrieb:
> > >
> > >> Then again, I guess it was interesting to observe that some types of
> > >> optimizations which help on BJX2 also help on x86-64, despite x86-64
> > >> having not enough registers to actually make use of the optimization as
> > >> expressed (x86-64 seems to be able to pretend as-if the stack
> > >> spills/fills were registers).
> > >
> > > This is as old as optimizing compilers. The very first FORTRAN
> > > compiler assumed that there was an infinite amount of index
> > > registers, which it then later on assigned to the three that were
> > > actually available.
> > >
> > >> Meanwhile, I am left needing to use lots of registers, and occasional
> > >> optimizations which try to side-step a few (store then load) cases, then
> > >> recently needing to fix a bug where one of these optimizations broke due
> > >> to a type-handling issue in my compiler (was using the type of the value
> > >> stored to an array, rather than the type of the value as loaded from the
> > >> array).
> > >
> > > Did you actually look at optimizing register allocation algorithms?
> > > http://web.cecs.pdx.edu/~mperkows/temp/register-allocation.pdf is one
> > > of the first search results that Google (well, Startpage) returns.
> > > You should really look into graph coloring.
> > Looks some at the linked PDF.
> >
> > Yeah, BGBCC doesn't do anything like this.
> >
> > Only two levels:
> > Within a given basic-block;
> > Or, global for the whole function.
> >
> > Would have to figure out how to try to glue on something like graph
> > coloring, seems like a more advanced type of optimization than most of
> > the stuff I had been doing...
> >
> >
> > And, well, the "maybe stupid" assumption that if one typically has more
> > registers in the ISA than local variables and temporaries in the
> > function, they can static-assign everything and mostly sweep the
> > register-allocation issues under the carpet.
> >
> > Well, pros/cons...
> >
> >
> > There are also issues, like trying to weed out the sources that are
> > generating a bunch of spurious (and frivolous) RegReg MOVs (one can fix
> > them in one case, and find more frivolous MOVs somewhere else, or a
> > bunch of otherwise unnecessary sign or zero extension operations, ...).
> >
> >
> > Then again, I guess it remains as an open question of what performance
> > would look like if my optimizer didn't suck...
> >
> >
> > Then again, I guess no one is claiming that writing a "good quality" C
> > compiler is particularly fast or easy (getting something that "sorta
> > works" hacked together isn't too bad; getting it to generate decent
> > quality output and relatively bug-free is a whole different issue).
> >
> >
> > ...
> Yes. I came to realize that compilers are quite an undertaking. I only work
> on the compiler periodically now, preferring to use VBCC. Had a look at
> GCC and LLVM.
>
> Here is another link on color-graphing. I spent quite a bit of time reading and
> re-reading this until I was able to come up with a yet to get working properly
> color graphing allocator for my compiler. I think there are issues with register
> spills and reloads. Then I found out that if there are enough registers > 16
> maybe color graphing is not so necessary.
>
> https://www.cs.utexas.edu/users/mckinley/380C/lecs/briggs-thesis-1992.pdf
>
> I believe a linear scan allocator is another common allocator.
>
> I have the code for the allocator in my Github account. It is quite complex,
> written in c++.
>
> The allocator I currently use simply counts register usages, giving more counts
> for registers used in a loop. And prioritizes register allocations that way.

That should be expression usages.

Terje Mathisen <terje.mathisen@tmsw.no> writes:

> Tim Rentsch wrote:
>
>> MitchAlsup <MitchAlsup@aol.com> writes:
>>
>> [...]
>>
>>> There was a recent poll on some site and 56% of Americans do not
>>> think that Arabic numerals should be taught in schools, too; and
>>> 15% don't have an opinion.
>>> https://www.snopes.com/fact-check/teaching-arabic-numerals/
>>> We are well on the way to Idiocracy.
>>
>> That isn't idiocy; it's illiteracy. Those aren't the same thing.
>> Don't make the mistake of thinking someone is stupid when all they
>> are is ignorant.
>
> I was going to agree with you, but realized that "willful ignorance"
> cannot be as easily (if ever?) forgiven.

My comment is about people who happen to be ignorant, not about
people who choose to remain ignorant.

Furthermore, it is still the case that one shouldn't _assume_ that
someone is stupid just because they are ignorant. If later
information shows signs of willful ignorance, the question of
intelligence can always be revisited (or even just visited).

Note by the way that most of the people responding to this survey
probably didn't choose to be ignorant of the essential fact that
our number symbols are indeed Arabic numerals. And it isn't
obvious that including that bit of knowledge in the educational
curriculum would yield any significant benefit. It's more
important to teach people how to think than to fill their heads
with zillions of miscellaneous facts (and it's disappointing that
this basic truth is not more widely recognized).

BGB <cr88192@gmail.com> writes:

> On 12/15/2022 4:13 AM, Anton Ertl wrote:
>
>> MitchAlsup <MitchAlsup@aol.com> writes:
>>
>>> Had your base port been from LLVM instead of GCC this likely would not
>>> have happened.
>>> GCC is more of a K&R (anything goes) while LLVM is more of a C-done-right
>>> (ADA-style)
>>
>> On what evidence do you base this claim?
>>
>> And why would "C-done-right" be "ADA-style"? My take on C done right
>> is that a compiler maintains backwards compatibility with earlier
>> versions, while others think that C done right punishes the sinners
>> who write code that performs undefined behaviour as much as possible
>> by compiling it to unintended code (best even if there is no
>> performance advantage to that). I don't have Ada experience, but the
>> general image is compile-time errors and run-time errors; I would not
>> expect the latter from GCC or Clang.
>>
>> What I have experienced from Clang is that a common bit-rotation idiom
>> is compiled to 0 for rot(x,0) (for variable x) without compile-time or
>> run-time warning or error, because it exercises undefined behaviour
>> for a rotation count of 0, while gcc produced the intended behaviour.
>
> Yeah. Both GCC and LLVM are playing fast and loose with C semantics.

The construct in question is undefined behavior. You may not
like what GCC and LLVM do with it, but they are not in any
way shape or form violating C semantics.

On Friday, December 16, 2022 at 9:26:52 PM UTC-6, BGB wrote:
> On 12/16/2022 10:01 AM, Scott Lurndal wrote:
> > Thomas Koenig <tko...@netcologne.de> writes:
> >> BGB <cr8...@gmail.com> schrieb:
> >>
> >>> Then again, I guess it was interesting to observe that some types of
> >>> optimizations which help on BJX2 also help on x86-64, despite x86-64
> >>> having not enough registers to actually make use of the optimization as
> >>> expressed (x86-64 seems to be able to pretend as-if the stack
> >>> spills/fills were registers).
> >>
> >> This is as old as optimizing compilers. The very first FORTRAN
> >> compiler assumed that there was an infinite amount of index
> >> registers, which it then later on assigned to the three that were
> >> actually available.
> >>
> I was thinking more in the sense that it seems to behave as-if it could
> load from memory into a register in 1 cycle, even if realistically this
> should take ~ 4 cycles on x86-64.
>
One can organize a pipeline such that inbound memory access appears
to take no cycles at all. Fetch-Decode-AGEN-LDAlign-Calculate-WriteBack.
Memory reference instructions are presented to the cache (or memory
pipeline in order) memory is accessed, aligned and then made available
to some calculation instruction as an operand, writeback can send the result
of the calculation into the cache (ST) as required.
<
I have called this the 360 pipeline <organization> in the past. One could call
it the LD-OP pipeline just as easily. The 360/91 pipeline is just an extreme
version (without cache).
<
On a machine such as Gould 32/<and> various interlocks were applied
between calculate and AGEN such that the correct AGENs were performed.
And, here, inbound memory references that hit in the cache actually do take
ZERO extra cycles.
>
> Say, one x86-64, one can do a version of a piece of logic:
> 2 operations at a time, using 10 variables;
> 4 operations at a time, using 20 variables.
>
> x86-64 has 16 registers, so one would expect the 10 variable version to
> be faster than the 20 variable version. But, one may observe the 20
> variable case is still faster.
<
The architecture of x86 is so fucked up at this point in time that budding
architects should avoid being influenced by any of its features.
>

On Friday, December 16, 2022 at 10:45:39 PM UTC-6, BGB wrote:
> On 12/16/2022 8:58 PM, MitchAlsup wrote:
> > On Friday, December 16, 2022 at 8:22:22 PM UTC-6, BGB wrote:
> >> On 12/16/2022 2:28 PM, MitchAlsup wrote:
> >>> There seem to be two different camps for ABI design:
> >>
> >> SysV style ABIs:
> >> Typically no spill space;
> >> Structures are passed by copying them in registers or on the stack;
> >> (They often decompose structures into registers, ...)
> >> ...
> >>
> >> Microsoft Style:
> >> Typically provide a spill space,
> >> usually equal to the number of register arguments;
> >> Typically pass and return structures by reference;
> >> ...
> >>
> >>
> >> I had noted that the official RISC-V ABI seems to follow SysV patterns..
> > <
> > MIPS has a spill space............And I see now that RISC-V has corrected that.......
> But, not found any clear information as to why a spill space is either
> good or bad (apart from the issue of not scaling up very well by putting
> more strain on the displacement distance).
>
> Effect on performance either way seems to be fairly small, though it
> does seem to effect code density.
>
> For things like trying to wrangle function argument lists across an RPC
> mechanism, the spill-space makes things easier.
>
> Some descriptions of the Windows X64 ABI also made a case for why
> spill-space was a good thing.
>
>
> I have ABI variants both with and without a spill-space.
> Was using the "no spill space" variant for code built with
> "sizeof(void*)==4".
> >>
> > snip
> >>> While you can't do it naïvely, there is a straightforward way to achieve
> >>> this goal of a vector of arguments for varargs--and in My 66000 you
> >>> can achieve this at the cost of 0 extra instructions !
> > <
> >> In the 8-arg case, it can be done with 4 MOV.X instructions.
> > <
> > Preserving some registers, and allocating a stack costs me 1 instruction.
> > <
> > ENTER R26,R0,#local_data_area_size
> > <
> > Pushing the register arguments, preserving some registers, and allocating
> > a stack still costs only 1 instruction !
> > <
> > ENTER R26,R9,#local_data_area_size
> > <
> > You do it in 4 more instructions, I do it in an already existing instruction.
> I don't have fancy instructions here.
<
In my best Ivan voice: "Fix it" !
> snip
> > <
> > This is why you have to get it right the first time.
> Whole thing started out with 16 registers, then doubled it twice.
> No obvious "better" option than to repeat the existing pattern 2 or 4 times.
<
So, you admit you got it wrong the first time, and now you are patching and
patching.......
>
> The strategy does allow one to determine if a register is callee saved
> fairly easily:
> if(regID&8)
> { callee-saved }
> else
> { scratch }
<
if(regID & 16)
{ preserved }
else
{ argument or temporary }
<
It is also easier to remember that R16..R32 are all preserved than R8..R15 and
R24..R32 (for the human)
>
> Except for a few special cases.
<
No special cases for me......
>

On 12/17/2022 9:53 AM, MitchAlsup wrote:
> On Friday, December 16, 2022 at 9:26:52 PM UTC-6, BGB wrote:
>> On 12/16/2022 10:01 AM, Scott Lurndal wrote:
>>> Thomas Koenig <tko...@netcologne.de> writes:
>>>> BGB <cr8...@gmail.com> schrieb:
>>>>
>>>>> Then again, I guess it was interesting to observe that some types of
>>>>> optimizations which help on BJX2 also help on x86-64, despite x86-64
>>>>> having not enough registers to actually make use of the optimization as
>>>>> expressed (x86-64 seems to be able to pretend as-if the stack
>>>>> spills/fills were registers).
>>>>
>>>> This is as old as optimizing compilers. The very first FORTRAN
>>>> compiler assumed that there was an infinite amount of index
>>>> registers, which it then later on assigned to the three that were
>>>> actually available.
>>>>
>> I was thinking more in the sense that it seems to behave as-if it could
>> load from memory into a register in 1 cycle, even if realistically this
>> should take ~ 4 cycles on x86-64.
>>
> One can organize a pipeline such that inbound memory access appears
> to take no cycles at all. Fetch-Decode-AGEN-LDAlign-Calculate-WriteBack.
> Memory reference instructions are presented to the cache (or memory
> pipeline in order) memory is accessed, aligned and then made available
> to some calculation instruction as an operand, writeback can send the result
> of the calculation into the cache (ST) as required.
> <
> I have called this the 360 pipeline <organization> in the past. One could call
> it the LD-OP pipeline just as easily. The 360/91 pipeline is just an extreme
> version (without cache).
> <
> On a machine such as Gould 32/<and> various interlocks were applied
> between calculate and AGEN such that the correct AGENs were performed.
> And, here, inbound memory references that hit in the cache actually do take
> ZERO extra cycles.

IIRC, had read somewhere before that many x86's had handled things like:
ADD EAX, [ECX]
By breaking them into multiple uOps, one for the Load and another for
the Op, and then using a more RISC-like pipeline internally.

This does not seem true at least for the Ryzen.

For Piledriver, would have been more believable, as performance-related
behavior did seem pretty close to what I would expect (theoretically)
from a 3-wide in-order superscalar.

But, Ryzen seems to have changed something, and got a pretty big speedup
here (the estimated model would be something like a 4-wide superscalar
where nearly every operation takes ~ 1 clock cycle).

For some tasks (mostly for stuff written in ASM) have beaten my Ryzen in
terms of work per clock-cycle, mostly because a lot of tasks seem to fit
my ISA design better than they fit into x86-64 / SSE.

Partly this is due to things like 3R ops, ability to load FP values as
immediate, or even "simple things" like less awkward vector shuffles, ...

For C code, or Dhrystone, it is a different matter. Seem to be taking
roughly twice as many instructions for each run through Dhrystone if
compared with GCC + RISC-V.

Where everything is going? I don't know.

>>
>> Say, one x86-64, one can do a version of a piece of logic:
>> 2 operations at a time, using 10 variables;
>> 4 operations at a time, using 20 variables.
>>
>> x86-64 has 16 registers, so one would expect the 10 variable version to
>> be faster than the 20 variable version. But, one may observe the 20
>> variable case is still faster.
> <
> The architecture of x86 is so fucked up at this point in time that budding
> architects should avoid being influenced by any of its features.

Probably true.

Also tested, and it seems like (sadly) my "make ISA variant that
natively does 64 GPRs, enable 64 GPRs everywhere" strategy doesn't seem
to be working out as well as I had hoped.

In particularly it has a hump where, say:
Selectively enable R32..R63, slight code-size reduction and speed increase;
Enable R32..R63 for every function, binary size gets bigger, performance
gets worse.

It appears the issue with this strategy isn't just about the encoding
orthogonality (since using R32..R63 should no longer be as much of an
issue with XG2).

I suspect the added overhead of saving/restoring more registers in the
prolog/epilog sequences is offsetting the gains in many cases.

According to Tim Rentsch <tr.17687@z991.linuxsc.com>:
>>>> There was a recent poll on some site and 56% of Americans do not
>>>> think that Arabic numerals should be taught in schools, too; and
>>>> 15% don't have an opinion. ...

>Note by the way that most of the people responding to this survey
>probably didn't choose to be ignorant of the essential fact that
>our number symbols are indeed Arabic numerals.

They are and they aren't. While we call our familar digits Arabic
numerals, there is a quite different set of Arabic digits used in
written Arabic. You can see them in this code chart, U+0660 to U+0669:

https://en.wikipedia.org/wiki/Arabic_(Unicode_block)

I was in Abu Dhabi for a conference a few years ago and indeed the
numbers on the speed limit signs used those digits.

While I agree it's pretty lame that apparently a majority of Americans
don't know that we call our digits Arabic numerals, I can have a fair
amount of sympathy that there's no need to teach the Arabic digits
that Arabs currently use.

--
Regards,
John Levine, johnl@taugh.com, Primary Perpetrator of "The Internet for Dummies",
Please consider the environment before reading this e-mail. https://jl.ly

On Saturday, December 17, 2022 at 12:40:38 PM UTC-6, John Levine wrote:
> According to Tim Rentsch <tr.1...@z991.linuxsc.com>:
> >>>> There was a recent poll on some site and 56% of Americans do not
> >>>> think that Arabic numerals should be taught in schools, too; and
> >>>> 15% don't have an opinion. ...
<
> >Note by the way that most of the people responding to this survey
> >probably didn't choose to be ignorant of the essential fact that
> >our number symbols are indeed Arabic numerals.
<
I was taught in 3,4,5 th grades that the 0..9 digits we used were Arabic
numerals. So, at least for my generation, you could not get out of grade
school without being told this fact. Most quickly forgot....................sigh
<
> They are and they aren't. While we call our familar digits Arabic
> numerals, there is a quite different set of Arabic digits used in
> written Arabic. You can see them in this code chart, U+0660 to U+0669:
>
> https://en.wikipedia.org/wiki/Arabic_(Unicode_block)
>
> I was in Abu Dhabi for a conference a few years ago and indeed the
> numbers on the speed limit signs used those digits.
>
> While I agree it's pretty lame that apparently a majority of Americans
> don't know that we call our digits Arabic numerals, I can have a fair
> amount of sympathy that there's no need to teach the Arabic digits
> that Arabs currently use.
>
> --
> Regards,
> John Levine, jo...@taugh.com, Primary Perpetrator of "The Internet for Dummies",
> Please consider the environment before reading this e-mail. https://jl.ly

On 12/17/2022 2:49 AM, robf...@gmail.com wrote:
> On Saturday, December 17, 2022 at 12:23:44 AM UTC-5, BGB wrote:
>> On 12/16/2022 9:56 AM, Thomas Koenig wrote:
>>> BGB <cr8...@gmail.com> schrieb:
>>>
>>>> Then again, I guess it was interesting to observe that some types of
>>>> optimizations which help on BJX2 also help on x86-64, despite x86-64
>>>> having not enough registers to actually make use of the optimization as
>>>> expressed (x86-64 seems to be able to pretend as-if the stack
>>>> spills/fills were registers).
>>>
>>> This is as old as optimizing compilers. The very first FORTRAN
>>> compiler assumed that there was an infinite amount of index
>>> registers, which it then later on assigned to the three that were
>>> actually available.
>>>
>>>> Meanwhile, I am left needing to use lots of registers, and occasional
>>>> optimizations which try to side-step a few (store then load) cases, then
>>>> recently needing to fix a bug where one of these optimizations broke due
>>>> to a type-handling issue in my compiler (was using the type of the value
>>>> stored to an array, rather than the type of the value as loaded from the
>>>> array).
>>>
>>> Did you actually look at optimizing register allocation algorithms?
>>> http://web.cecs.pdx.edu/~mperkows/temp/register-allocation.pdf is one
>>> of the first search results that Google (well, Startpage) returns.
>>> You should really look into graph coloring.
>> Looks some at the linked PDF.
>>
>> Yeah, BGBCC doesn't do anything like this.
>>
>> Only two levels:
>> Within a given basic-block;
>> Or, global for the whole function.
>>
>> Would have to figure out how to try to glue on something like graph
>> coloring, seems like a more advanced type of optimization than most of
>> the stuff I had been doing...
>>
>>
>> And, well, the "maybe stupid" assumption that if one typically has more
>> registers in the ISA than local variables and temporaries in the
>> function, they can static-assign everything and mostly sweep the
>> register-allocation issues under the carpet.
>>
>> Well, pros/cons...
>>
>>
>> There are also issues, like trying to weed out the sources that are
>> generating a bunch of spurious (and frivolous) RegReg MOVs (one can fix
>> them in one case, and find more frivolous MOVs somewhere else, or a
>> bunch of otherwise unnecessary sign or zero extension operations, ...).
>>
>>
>> Then again, I guess it remains as an open question of what performance
>> would look like if my optimizer didn't suck...
>>
>>
>> Then again, I guess no one is claiming that writing a "good quality" C
>> compiler is particularly fast or easy (getting something that "sorta
>> works" hacked together isn't too bad; getting it to generate decent
>> quality output and relatively bug-free is a whole different issue).
>>
>>
>> ...
> Yes. I came to realize that compilers are quite an undertaking. I only work
> on the compiler periodically now, preferring to use VBCC. Had a look at
> GCC and LLVM.
>

OK. Had not heard of or looked at VBCC.

As noted, I am using BGBCC for my project, which was written by me,
originally back in the late 2000s (when I was still taking college
classes, still early 20s at the time).

First version kinda "really sucked" and didn't go much beyond fairly
trivial test programs (at the time it was mostly beyond my debugging
skills).

Also this first version was trying to generate x86 code directly from
the stack IR, which was a bad idea. It wasn't until the 2010s that most
of my VM projects would switch over to translating from a stack model to
a 3AC IR, and then either interpreting or JIT'ing based on this (the 3AC
model giving a big speedup over trying to run a stack-machine model
directly).

> Here is another link on color-graphing. I spent quite a bit of time reading and
> re-reading this until I was able to come up with a yet to get working properly
> color graphing allocator for my compiler. I think there are issues with register
> spills and reloads. Then I found out that if there are enough registers > 16
> maybe color graphing is not so necessary.
>
> https://www.cs.utexas.edu/users/mckinley/380C/lecs/briggs-thesis-1992.pdf
>
> I believe a linear scan allocator is another common allocator.
>
> I have the code for the allocator in my Github account. It is quite complex,
> written in c++.
>
> The allocator I currently use simply counts register usages, giving more counts
> for registers used in a loop. And prioritizes register allocations that way.

Similar in my case.

In the "frame layout" step, it goes and looks at all the IR ops, counts
usage count, with a 1+x^2 multiplier based on loop nesting level
(recorded in the IL/IR for each label).

So:
a=0; //multiplier = 1 (level=0)
for(i=0; i<10; i++)
{
b=2; //multiplier = 2 (level=1)
for(j=0; j<10; j++)
{
c=3; //multiplier = 5 (level=2)
}
}

The variables in the function are ranked based on their total counts,
with the "top N" statically assigned to variables.

The N is variable here, where N has a theoretical hard-limit (based on
the number of available registers, minus a certain minimum).

Subtracted minimum is, say:
4 if no SIMD ops;
7 if SIMD ops.

Basically, need to keep at least enough registers free to be able to
load the working values for a 3R operation (else the compiler may end up
backed into a corner where it is unable to allocate dynamic registers
for things, and has no option other than to abort).

As noted:
R8..R14, Limit=3 or 0 (*)
R8..R14, R24..R31: Limit=11 or 8.
R8..R14, R24..R31, R40..R47, R55..R63: Limit=27 or 24.

With the limit being increased for leaf functions (where one can also
allocate variables into scratch registers).

*: For 16 GPR machines, it may make sense to use only dynamic
allocation. This is what my code-generators on x86-64 and ARM had
typically done (works well enough on x86, but my attempts to generate
code for ARM have tended to result in performance that is "decidedly
awful").

The value for N is determined based on finding the point where the sum
of the current and preceding variables crosses 1/16 of the total count
for all variables (*).

Except where the hard-limit is greater than the total variables, where
it then sets N to the to the number of variables in the function.

*: I am looking at my code, but the logic of how it works is not making
sense to me at the moment (seems suspect).

Intuitively would have made more sense to compare the sum of
current-and-preceding against the sum of all future variables, say:
if(current>((total-current)*magicScale)) { N=i; break; }

Presumably I knew what I was doing at the time, but seems like for
whatever reason, the logic escapes me at the moment.

MitchAlsup wrote:
[snip]
> One can organize a pipeline such that inbound memory access appears
> to take no cycles at all. Fetch-Decode-AGEN-LDAlign-Calculate-WriteBack.
> Memory reference instructions are presented to the cache (or memory
> pipeline in order) memory is accessed, aligned and then made available
> to some calculation instruction as an operand, writeback can send the result
> of the calculation into the cache (ST) as required.

Of course, that does not apply to loaded values used for
addressing other values in memory (pointers and indexes).

For some special cases one can avoid/defer address generation by
addressing the cache by the offset (this even allows hoisting the
load operation ahead of register read). E.g., Knapsack cache
(indexed by offset from global pointer), signature cache (object
base pointer address is base of cache), or possibly stack cache
(most proposals do use address generation but one could avoid that
at the cost of utilization, e.g., inverting offsets for every
other stack frame would allow two (possibly partial) frames to be
trivially addressed in a direct-mapped stack cache).

(Special casing base address value access to provide the least
significant bits — even excluding three or more least significant
bits if objects, stack, etc. pointers have 8+ byte alignment —
which might shave a little latency at the cost of area and power.)

Summed-address memory is another technique for reducing cache
access latency. (Of course, Itanium provided only post-increment
loads, so address generation did not add latency — not that such
is an example of a good design choice.)

ORing (or XORing) the offset with the base address has been
proposed, but that seems likely to be a poor choice.

(Interestingly, Intel already penalized carry-out past a certain
point in address generation — or so I seem to recall reading.)

> I have called this the 360 pipeline <organization> in the past. One could call
> it the LD-OP pipeline just as easily. The 360/91 pipeline is just an extreme
> version (without cache).

The term I read (which applies generally to delaying some
operations relative to others) is "skewed pipeline".

> On a machine such as Gould 32/<and> various interlocks were applied
> between calculate and AGEN such that the correct AGENs were performed.
> And, here, inbound memory references that hit in the cache actually do take
> ZERO extra cycles.

While the specific trick of skewed-pipelining is probably simple
enough to be reinvented, it still seems sad that so much
cleverness of the past is not remembered (documented for easy
reference).

Anton Ertl wrote:
[snip]
> If you want a delay-1-cycle instruction, this should be possible even
> in an OoO machine: when that instruction is processed, the clock is
> not gated through to the rest of the execution engine for one cycle.
> Of course, with an OoO engine, you cannot really predict which
> instructions are affected by the additional cycle. The question is:
> Why would anyone use such an instruction?

MIPS defined a superscalar nop. MIPS64™ Architecture For
Programmers, Volume II: The MIPS64™ Instruction Set, Revision 2.00
(June 9, 2003) descripes Superscalar No Operation (SSNOP) thus:

Purpose:
Break superscalar issue on a superscalar processor.

Description:
SSNOP is the assembly idiom used to denote superscalar no
operation. The actual instruction is interpreted by the hardware
as SLL r0, r0, 1.

This instruction alters the instruction issue behavior on a
superscalar processor by forcing the SSNOP instruction to single-
issue. The processor must then end the current instruction issue
between the instruction previous to the SSNOP and the SSNOP. The
SSNOP then issues alone in the next issue slot.

On a single-issue processor, this instruction is a NOP that takes
an issue slot.

....

Programming Notes:
SSNOP is intended for use primarily to allow the programmer
control over CP0 hazards by converting instructions into cycles in
a superscalar processor. For example, to insert at least two
cycles between an MTC0 and an ERET, one would use the following
sequence:

mtc0
ssnop
ssnop
eret
x,y

Based on the normal issues rules of the processor, the MTC0 issues
in cycle T. Because the SSNOP instructions must issue alone, they
may issue no earlier than cycle T+1 and cycle T+2, respectively.
Finally, the ERET issues no earlier than cycle T+3. Note that
although the instruction after an SSNOP may issue no earlier than
the cycle after the SSNOP is issued, that instruction may issue
later. This is because other implementation-dependent issue rules
may apply that prevent an issue in the next cycle. Processors
should not introduce any unnecessary delay in issuing SSNOP
instructions.

A less code bloating alternative was introduced later: Execution
Hazard Barrier (EHB):

Purpose:
To stop instruction execution until all execution hazards have
been cleared.

Description:
EHB is the assembly idiom used to denote execution hazard barrier.
The actual instruction is interpreted by the hardware as SLL r0,
r0, 3.

This instruction alters the instruction issue behavior on a
pipelined processor by stopping execution until all execution
hazards have been cleared. Other than those that might be created
as a consequence of setting StatusCU0, there are no execution
hazards visible to an unprivileged program running in User Mode.
All execution hazards created by previous instructions are cleared
for instructions executed immediately following the EHB, even if
the EHB is executed in the delay slot of a branch or jump. The EHB
instruction does not clear instruction hazards - such hazards are
cleared by the JALR.HB, JR.HB, and ERET instructions.

....

Programming Notes:
In MIPS64 Release 2 implementations, this instruction resolves all
execution hazards. On a superscalar processor, EHB has alters the
instruction issue behavior in a manner identical to SSNOP. For
backward compatibility with Release 1 implementations, the last of
a sequence of SSNOPs can be replaced by an EHB. In Release 1
implementations, the EHB will be treated as an SSNOP, thereby
preserving the semantics of the sequence. In Release 2
implementations, replacing the final SSNOP with an EHB should have
no performance effect because a properly sizedsequence of SSNOPs
will have already cleared the hazard. As EHB becomes the standard
in MIPS implementations, the previous SSNOPs can be removed,
leaving only the EHB.

On 12/17/2022 8:53 AM, Tim Rentsch wrote:
> Terje Mathisen <terje.mathisen@tmsw.no> writes:
>
>> Tim Rentsch wrote:
>>
>>> MitchAlsup <MitchAlsup@aol.com> writes:
>>>
>>> [...]
>>>
>>>> There was a recent poll on some site and 56% of Americans do not
>>>> think that Arabic numerals should be taught in schools, too; and
>>>> 15% don't have an opinion.
>>>> https://www.snopes.com/fact-check/teaching-arabic-numerals/
>>>> We are well on the way to Idiocracy.
>>>
>>> That isn't idiocy; it's illiteracy. Those aren't the same thing.
>>> Don't make the mistake of thinking someone is stupid when all they
>>> are is ignorant.
>>
>> I was going to agree with you, but realized that "willful ignorance"
>> cannot be as easily (if ever?) forgiven.
>
> My comment is about people who happen to be ignorant, not about
> people who choose to remain ignorant.
>
> Furthermore, it is still the case that one shouldn't _assume_ that
> someone is stupid just because they are ignorant. If later
> information shows signs of willful ignorance, the question of
> intelligence can always be revisited (or even just visited).
>

And then there is also...

Whatever, exactly, is going on in the minds of YECs (Young Earth
Creationists).
Like, all the sort of extreme contortions they go through, to try to
make the world (and the universe as a whole) try to fit into a 6K year
timeline...

Like, this can be ruled out mostly on the basis of plausibility.

Well, then again, there are also groups set on the idea that there was
once a technologically advanced civilization among the Native Americans,
but that they had a war and (somehow forgot?) and reverted back to a
hunter/gatherer lifestyle.

....

> Note by the way that most of the people responding to this survey
> probably didn't choose to be ignorant of the essential fact that
> our number symbols are indeed Arabic numerals. And it isn't
> obvious that including that bit of knowledge in the educational
> curriculum would yield any significant benefit. It's more
> important to teach people how to think than to fill their heads
> with zillions of miscellaneous facts (and it's disappointing that
> this basic truth is not more widely recognized).

Yeah.

School system is seemingly more about making people do busywork,
memorize random trivia, and then accept the superiority of being a "busy
worker bee" for the corporate overlords, than anything else...

I was left as someone who had generally far too much anxiety to really
put much effort into all the meaningless busywork, and had doubts about
the "inherent goodness" of a world based on the control of a smallish
number of large corporations.

Had also sort of believed at the time that society was probably going to
collapse relatively soon anyways.

Granted, the "2008 financial crisis" happened a few years after I got
out of high-school, but this wasn't quite the level of collapse I had
imagined. Even as such, things still don't look entirely stable (say,
what will people do if/when inflation goes out of control and the USD
becomes essentially worthless?...).

Though, the shake-up could either lead to:
Many corporations die off;
The "overlord" situation gets worse, if those who remain largely take
over many of the roles traditionally held by the US government (their
ability to retain authority or control in many areas being less certain
in the case of a full economic collapse).

Like, say, what if much of the western US is no longer "US" per se, but
instead mostly split up between areas ruled over by Apple and
Microsoft?... ( Well, say, with UT/NV/AZ/... becoming part of an LDS
theocracy? ... ).

....

On Saturday, December 17, 2022 at 1:33:31 PM UTC-6, Paul A. Clayton wrote:
> MitchAlsup wrote:
> [snip]
> > One can organize a pipeline such that inbound memory access appears
> > to take no cycles at all. Fetch-Decode-AGEN-LDAlign-Calculate-WriteBack..
> > Memory reference instructions are presented to the cache (or memory
> > pipeline in order) memory is accessed, aligned and then made available
> > to some calculation instruction as an operand, writeback can send the result
> > of the calculation into the cache (ST) as required.
> Of course, that does not apply to loaded values used for
> addressing other values in memory (pointers and indexes).
>
> For some special cases one can avoid/defer address generation by
> addressing the cache by the offset (this even allows hoisting the
> load operation ahead of register read). E.g., Knapsack cache
> (indexed by offset from global pointer), signature cache (object
> base pointer address is base of cache), or possibly stack cache
> (most proposals do use address generation but one could avoid that
> at the cost of utilization, e.g., inverting offsets for every
> other stack frame would allow two (possibly partial) frames to be
> trivially addressed in a direct-mapped stack cache).
>
> (Special casing base address value access to provide the least
> significant bits — even excluding three or more least significant
> bits if objects, stack, etc. pointers have 8+ byte alignment —
> which might shave a little latency at the cost of area and power.)
>
> Summed-address memory is another technique for reducing cache
> access latency. (Of course, Itanium provided only post-increment
> loads, so address generation did not add latency — not that such
> is an example of a good design choice.)
>
> ORing (or XORing) the offset with the base address has been
> proposed, but that seems likely to be a poor choice.
>
> (Interestingly, Intel already penalized carry-out past a certain
> point in address generation — or so I seem to recall reading.)
> > I have called this the 360 pipeline <organization> in the past. One could call
> > it the LD-OP pipeline just as easily. The 360/91 pipeline is just an extreme
> > version (without cache).
> The term I read (which applies generally to delaying some
> operations relative to others) is "skewed pipeline".
> > On a machine such as Gould 32/<and> various interlocks were applied
> > between calculate and AGEN such that the correct AGENs were performed.
> > And, here, inbound memory references that hit in the cache actually do take
> > ZERO extra cycles.
<
> While the specific trick of skewed-pipelining is probably simple
> enough to be reinvented, it still seems sad that so much
> cleverness of the past is not remembered (documented for easy
> reference).
<
The real shame is that none of the new trainees to bother to look the old
stuff up.
<
Those who do not remember history are doomed to repeat it.
<
Apparently this holds double for Computer Science.................

On 12/17/2022 9:46 AM, Tim Rentsch wrote:
> BGB <cr88192@gmail.com> writes:
>
>> On 12/15/2022 4:13 AM, Anton Ertl wrote:
>>
>>> MitchAlsup <MitchAlsup@aol.com> writes:
>>>
>>>> Had your base port been from LLVM instead of GCC this likely would not
>>>> have happened.
>>>> GCC is more of a K&R (anything goes) while LLVM is more of a C-done-right
>>>> (ADA-style)
>>>
>>> On what evidence do you base this claim?
>>>
>>> And why would "C-done-right" be "ADA-style"? My take on C done right
>>> is that a compiler maintains backwards compatibility with earlier
>>> versions, while others think that C done right punishes the sinners
>>> who write code that performs undefined behaviour as much as possible
>>> by compiling it to unintended code (best even if there is no
>>> performance advantage to that). I don't have Ada experience, but the
>>> general image is compile-time errors and run-time errors; I would not
>>> expect the latter from GCC or Clang.
>>>
>>> What I have experienced from Clang is that a common bit-rotation idiom
>>> is compiled to 0 for rot(x,0) (for variable x) without compile-time or
>>> run-time warning or error, because it exercises undefined behaviour
>>> for a rotation count of 0, while gcc produced the intended behaviour.
>>
>> Yeah. Both GCC and LLVM are playing fast and loose with C semantics.
>
> The construct in question is undefined behavior. You may not
> like what GCC and LLVM do with it, but they are not in any
> way shape or form violating C semantics.

Saying something is "undefined behavior" is kind of a weak argument IMO
when it has otherwise "perfectly reasonable" behavior that "most older
compilers supported, and most C code from that era accepted as canonical".

Undefined Behavior more makes sense for the programmer to take note of,
when there might be implementation differences between compilers.
Compilers treating UB as license to do whatever, is not ideal, except in
cases where the depended on semantics are "clearly unreasonable".

>The real shame is that none of the new trainees to bother to look the old
>stuff up.
><
>Those who do not remember history are doomed to repeat it.
><
It is ego I think. Maybe lacking humility? It takes a bit to recognize that
maybe someone else could have done a better job than oneself. Personally,
I like to find out if someone else has done the thing I am after, then just
copy the ideas as a starting point. Trying to be innovative. The world is
bigger than just me.

Even those who do remember history are also likely doomed to repeat it.

BGB <cr88192@gmail.com> schrieb:
> On 12/17/2022 9:46 AM, Tim Rentsch wrote:

>> The construct in question is undefined behavior. You may not
>> like what GCC and LLVM do with it, but they are not in any
>> way shape or form violating C semantics.
>
> Saying something is "undefined behavior" is kind of a weak argument IMO
> when it has otherwise "perfectly reasonable" behavior that "most older
> compilers supported, and most C code from that era accepted as canonical".

I don't suppose you have ever written code to a specification, have you?

A specification, in this case the C standard, is binding on both sides:
The compiler writer has to adhere to it (or else it's a compiler bug),
and the user has to adhere to it (or else it's a bug in the program).

The C standard allows extensions. You can rely on these _for
that particular compiler and version_ if, and only if, they are
described in the compiler's documentation. For example, a compiler
may document that int has two's complement, and is four bytes long.

If it is _not_ described in the compiler's documentation and given
as "undefined behavior" by the standard, well... undefined behavior
is what you get, which means that anything can happen.

> Undefined Behavior more makes sense for the programmer to take note of,
> when there might be implementation differences between compilers.
> Compilers treating UB as license to do whatever, is not ideal, except in
> cases where the depended on semantics are "clearly unreasonable".

Again, try to understand what a specification is.

On 17/12/2022 15:53, Tim Rentsch wrote:
> Terje Mathisen <terje.mathisen@tmsw.no> writes:
>
>> Tim Rentsch wrote:
>>
>>> MitchAlsup <MitchAlsup@aol.com> writes:
>>>
>>> [...]
>>>
>>>> There was a recent poll on some site and 56% of Americans do not
>>>> think that Arabic numerals should be taught in schools, too; and
>>>> 15% don't have an opinion.
>>>> https://www.snopes.com/fact-check/teaching-arabic-numerals/
>>>> We are well on the way to Idiocracy.
>>>
>>> That isn't idiocy; it's illiteracy. Those aren't the same thing.
>>> Don't make the mistake of thinking someone is stupid when all they
>>> are is ignorant.
>>
>> I was going to agree with you, but realized that "willful ignorance"
>> cannot be as easily (if ever?) forgiven.
>
> My comment is about people who happen to be ignorant, not about
> people who choose to remain ignorant.
>
> Furthermore, it is still the case that one shouldn't _assume_ that
> someone is stupid just because they are ignorant. If later
> information shows signs of willful ignorance, the question of
> intelligence can always be revisited (or even just visited).
>
> Note by the way that most of the people responding to this survey
> probably didn't choose to be ignorant of the essential fact that
> our number symbols are indeed Arabic numerals. And it isn't
> obvious that including that bit of knowledge in the educational
> curriculum would yield any significant benefit. It's more
> important to teach people how to think than to fill their heads
> with zillions of miscellaneous facts (and it's disappointing that
> this basic truth is not more widely recognized).

To my mind, the key issue is not whether people do or do not know that
the normal digit system in the West is known as "Arabic numerals".
(Though I do think it is a useful thing to know, at least as a
distinction from "Roman numerals".)

The important point is that people are holding opinions, and sharing
opinions, on a topic they know nothing about. Instead of answering "I
don't know" when they don't know what "Arabic numerals" are, they jump
to a conclusion that is based at least partially on prejudice.

It's easy to fix ignorance - just teach people. It is a lot harder to
fix the long-ingrained lack of critical thinking and self-awareness that
has been idolised as "the right to your opinion" in modern times, and
has then been amplified by social media.

On 12/18/2022 1:38 AM, Thomas Koenig wrote:
> BGB <cr88192@gmail.com> schrieb:
>> On 12/17/2022 9:46 AM, Tim Rentsch wrote:
>
>>> The construct in question is undefined behavior. You may not
>>> like what GCC and LLVM do with it, but they are not in any
>>> way shape or form violating C semantics.
>>
>> Saying something is "undefined behavior" is kind of a weak argument IMO
>> when it has otherwise "perfectly reasonable" behavior that "most older
>> compilers supported, and most C code from that era accepted as canonical".
>
> I don't suppose you have ever written code to a specification, have you?
>
> A specification, in this case the C standard, is binding on both sides:
> The compiler writer has to adhere to it (or else it's a compiler bug),
> and the user has to adhere to it (or else it's a bug in the program).
>
> The C standard allows extensions. You can rely on these _for
> that particular compiler and version_ if, and only if, they are
> described in the compiler's documentation. For example, a compiler
> may document that int has two's complement, and is four bytes long.
>
> If it is _not_ described in the compiler's documentation and given
> as "undefined behavior" by the standard, well... undefined behavior
> is what you get, which means that anything can happen.
>
>> Undefined Behavior more makes sense for the programmer to take note of,
>> when there might be implementation differences between compilers.
>> Compilers treating UB as license to do whatever, is not ideal, except in
>> cases where the depended on semantics are "clearly unreasonable".
>
> Again, try to understand what a specification is.

I think it may be useful in this discussion to differentiate between
behavior that is documented in the specification as "undefined", and
behavior that is not documented in the specification at all, but a
particular compiler may implement in a particular way. Let's call the
latter "undocumented" to make the difference clear.

If a user relies on some behavior that is documented as undefined, then,
to me, he has no valid complaints if it changes, and the implementer is
not at fault.

On the other hand, if a user relies on some undocumented behavior, then,
to me, there is some responsibility on the part of the
specification/compiler writers to clarify the situation. If only one
interpretation is common, then it should be documented in the
spec/compiler documentation. In the case where multiple behaviors are
used, the documentation should make it clear which is being used.

--
- Stephen Fuld
(e-mail address disguised to prevent spam)