Path: ...!3.eu.feeder.erje.net!2.eu.feeder.erje.net!feeder.erje.net!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: BGB <cr88192@gmail.com>
Newsgroups: comp.lang.c
Subject: =?UTF-8?Q?Re=3A_technology_discussion_=E2=86=92_does_the_world_need?=
 =?UTF-8?B?IGEgIm5ldyIgQyA/?=
Date: Sun, 7 Jul 2024 14:57:39 -0500
Organization: A noiseless patient Spider
Lines: 419
Message-ID: <v6es1v$fian$1@dont-email.me>
References: <v66eci$2qeee$1@dont-email.me> <v67gt1$2vq6a$2@dont-email.me>
 <v687h2$36i6p$1@dont-email.me> <871q48w98e.fsf@nosuchdomain.example.com>
 <v68dsm$37sg2$1@dont-email.me> <87plrsultu.fsf@bsb.me.uk>
 <v68sft$3a6lh$1@dont-email.me> <87ed87v4wi.fsf@bsb.me.uk>
 <v6adrm$3ljg6$1@dont-email.me> <87v81ita77.fsf@bsb.me.uk>
 <v6d5k0$6rk5$1@dont-email.me> <v6duhl$amlm$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Sun, 07 Jul 2024 21:58:56 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="f7c16b2fffd87ab0346ebf4c8e11259c";
	logging-data="510295"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX18gGRPuPH1NLQvjkvm1JC+/xxspq92lwjE="
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:l5zkfZuYXylNCpi5cksNM78Urxk=
Content-Language: en-US
In-Reply-To: <v6duhl$amlm$1@dont-email.me>
Bytes: 17435

On 7/7/2024 6:35 AM, bart wrote:
> On 07/07/2024 05:28, BGB wrote:
>> On 7/6/2024 5:41 PM, Ben Bacarisse wrote:
>>> BGB <cr88192@gmail.com> writes:
>>>
>>>> On 7/5/2024 5:40 PM, Ben Bacarisse wrote:
>>>>> BGB <cr88192@gmail.com> writes:
>>>>>
>>>>>> On 7/5/2024 6:20 AM, Ben Bacarisse wrote:
>>>>>>> BGB <cr88192@gmail.com> writes:
>>>
>>>>>>>> While eliminating structs could also simplify things; structs 
>>>>>>>> also tend to
>>>>>>>> be a lot more useful.
>>>>>>> Indeed.  And I'd have to use them for this!
>>>>>>>
>>>>>>
>>>>>> Errm, the strategy I would assume is, as noted:
>>>>>>     int a[4][4];
>>>>>>     ...
>>>>>>     l=a[j][k];
>>>>>> Becomes:
>>>>>>     int a[16];
>>>>>>     ...
>>>>>>     l=a[j*4+k];
>>>>> That's what you want to force me to write, but I can use and array of
>>>>> arrays despite your arbitrary ban on them by simply putting the 
>>>>> array in
>>>>> a struct.
>>> ...
>>>> IN most contexts, I don't really see how a struct is preferable to a
>>>> multiply, but either way...
>>>
>>> And I can't see how an array of arrays is harder for your compiler than
>>> an array of structs.  C's indexing requires the compiler to know that
>>> size of the items pointed to.
>>>
>>> I suspect that there is something amiss with your design if you are
>>> considering this limiting in order to simplify the compiler.  A simple
>>> compiler should not care what kind of thing p points to in
>>>
>>>    p[i]
>>>
>>> only what size of object p points to.
>>>
>>
>>
>> When I designed the compiler code, the initial approach for internal 
>> type layout was to bit-pack it into 32 bits, say (a lot of this is 
>> from memory, so maybe wrong):
>> Basic1
>>    (31:28): Layout of Type (0=Basic)
>>    (27:16): Array Size
>>    (15:12): Pointer Level Count
>>    (11: 0): Base Type
>> Basic2
>>    (31:28): Layout of Type (1=Basic2)
>>    (27: 8): Array Size
>>    ( 7: 6): Pointer Level Count
>>    ( 5: 0): Base Type
>> Basic3
>>    (31:28): Layout of Type (2=Basic3)
>>    (27:24): Array Size
>>    (23:20): Pointer Level Count
>>    (19: 0): Base Type
>> Overflow
>>    (31:28): Layout of Type (3=Overflow)
>>    (27:24): MBZ
>>    (23: 0): Index into Type-Overflow Table
>> And, a few other cases...
>>
>>
>> Basic1 was the default, able to express arrays from 0..4095 elements, 
>> with 0..7 levels of pointer indirection, and 0..4095 for the base type.
>>   Where, 0=T, 1=T*, 2=T**, ..., 7=T*******
>>     8=T[], 9=T[][], A=T*[], B=T*[*], C=&T, ...
> 
> That's quite a level of detail. This looks more like an encoding you 
> might devise for a CPU instruction set. And yet you say elsewhere that 
> the whole compiler is 250K lines? So you're not trying to squeeze it 
> into a 16KB ROM or something.
> 

These values are packed inside of register descriptors, of which there 
are multiple in each 3AC op. And, there may be a whole lot of 3AC ops in 
a program. Much bulkier would cause the compiler to use a lot more RAM.


Though, a likely RAM-saving option would be to redesign the compiler 
such that only one function needs to have 3AC loaded at a time. But, for 
some tasks (such as tracing out everything that is reachable), this 
would mean repetitively re-decoding the stack IR for various functions.


Well, and/or building more metadata, such as (for every function) 
building a table of any other functions called, any global variables 
accessed, etc. But, this is just trading one type of memory bulk for 
another.


Like, say, if there are 4000 functions in a program, any metadata that 
needs to be stored per function adds up quickly.


>> It could also be used to encode another type, which was needed for 
>> things like multidimensional arrays and some other complex types. But, 
>> this seemed like an ugly hack... (And was at odds with how I imagined 
>> types working, but seemed like a technical necessity).
> 
> I can see how multi-dim arrays would be troublesome with such a scheme.
> 

Yeah.
It doesn't express them naturally, so I have to hack it.

It can, however, fairly easily express "FooStruct *x;".
But, if one wants, say:
   FooStruct *x[8192];
Then it needs to put it into the type-overflow table.


> My own approach is to use a bunch of parallel arrays (a table of structs 
> didn't appeal). They are populated with the standard types at the lower 
> end, then new types can be added.
> 
> A C type is represented by an index into those arrays. One of those 
> arrays is this (not C):
> 
>   [0:maxtype]int    tttarget              # All names start with 'tt'
> 
> For a pointer, it is contains the index of the target type. For arrays, 
> it is the index of the element type. There is no restriction on nesting, 
> other than 'maxtype' (set to some large number; one day I'll make the 
> limit flexible).
> 

Yeah, dunno...

I guess simpler could have been to do everything via the type-overflow 
table and not have bothered with bit-twiddled type descriptors.

Originally though, the type overflow table was a response to noting that 
there were a lot of situations that could not fit into a bit-packed format.


> 
>> One downside as-is, is that if a given variable is assigned more than 
>> 4096 times in a given function, it can no longer be given a unique ID. 
>> Though uncommon, this is not entirely implausible (with sufficiently 
>> large functions), and there isn't currently any good way to deal with 
>> this (apart from raising a compiler error).
> 
> 
> One of my compiler benchmarks is this program:
> 
>     #include <stdio.h>
> 
>     int main(void) {
>         int a, b=2, c=3, d=4;
> 
>         a=b+c*d;
> 
>         printf("%d\n", a);
>     }
> 
> Except that the 'a=b+c*d;' line is repeated 1M or 2M times, usually 
> within an included file.
> 
> Some compilers (including for other languages) find this challenging.
> 

As-is, if the line were repeated more than 4096 times, it would break my 
compiler absent adding an overflow case for the local variable descriptor.
========== REMAINDER OF ARTICLE TRUNCATED ==========