Splitting builtin support between the IR and the backend

[chuggafan]

As per the title, I think it would be paramount to split the builtins support between the backend and the middleend, the reason that I propose this is fourfold:

1. By splitting the support to the middleend initially, we will be able to optimize the register usage for individual uses, preventing the expensive calling convention setups for fastcall.
2. Depending on the architecture, if there is no instruction-level support, we could theoretically insert an IR-level block for what we want to do and have the optimizer work with that.
3. Some builtins are platform specific, if we mark those builtins in the middle-end we can spit them out and say "Not supported for this platform" and error out because of it
4. Continuing with 4, when there IS a platform specific builtin, we can optimize how we get into a valid state for it and execute the individual instruction, allowing us to support sse intrinsics without having expensive move-arounds (related to Adding the new SSE instructions as intrinsics #304 in a way).

This is a rather hefty issue so I definitely think this belongs sometime after milestone 4, possibly after milestone 5.

[LADSoft]

yeah it sounds good...

[chuggafan]

We could even add an IR stage for the frontend now that I think about it, because some builtins are special for each stage such as the template and constexpr ones HAVE to be in the frontend, whilst the middle-end can work with the "generic" IR stuff and transform the IR builtins into either platform-independent code or platform-specific code, and the backend can take the platform-specific builtins and spit out a lowered version.

Makes things easy if we place it all in one spot, I think.

[LADSoft]

yeah, I was thinking today of adding an attribute [[occ::intrinsic]] to mark intrinsic functions and classes in the front end. But that is mostly for processing things that can't easily or efficiently done with templates... I will probably rehash the two builtin templates that way before long. But still an 'intrinsic' flag could be used to mark that something special must be done when working with a prototype...

[chuggafan]

I don't think an [[occ::intrinsic]] is needed... maybe our current system technically works well? It could probably do with a bit more special casing... thinking about it more should probably be in our interest.

[LADSoft]

when we talk about the middle and backend, it seems like we are mostly talking about function-style builtins. The front end can have template and class builtins as well... so maybe if we do something simple like pass function calls out of the front end in a more compact format, the middle layer can do one of three things with it before doing optimizations. Either it could be streamed in to the intermediate code the way the front end does it now, it could be replaced with some sequence of intermediate code instructions in the middle layer, or it could be passed on to the backend with some minor changes.

[chuggafan]

Yep, sounds about right for what I think should happen.

[chuggafan]

So, I've been thinking of "how in the hell do I accomplish this"
I don't think it's going to be easy, but I think there's going to be several stages involved for a total "gcc/llvm-like" builtin support, where builtins can have full access to the middle-end optimizer pre-register allocation so that we can get rid of doing mandatory register allocation in the backend for doing a call to a function.

My proposal is that we're going to need several layers interoperating at once:

1. Front-end for selecting what we have as options
   ** Sadly, this is NOT an easy task, nor is it quick to implement, let's take an example, AVX-512 support, just because you're supporting "AVX-512" doesn't mean you support all of the extensions to it, this table from wikipedia shows just how ridiculous this support really is. https://en.wikipedia.org/wiki/AVX-512#CPUs_with_AVX-512 where older CPUs can support different things to newer CPUs and thus you must rely on "feature bits" instead of saying "We have a version X of instruction set Y"

2. Front-end support for the buitlins themselves
   ** A simple way, currently, to do this is to do a combination of the following:

   1. Produce a keyword that is shoved into an ARCH_ASM document.
   2. Only enable this keyword in the presence of a correct target architecture
   3. Have this keyword generate a multi-part IR instruction
   • This IR instruction NEEDS to note that it's a builtin IR instruction, what architecture it's for, THEN what instruction it is, I believe, under the current framework, so that we can ensure we don't mix stuff badly later on (I don't even want to THINK of the possibility of mixing architectures here)

3. This "multi-part" IR instruction is fed into the middle-end optimizer like any other IR instruction for IR optimization

4. The "multi-part" IR instruction, depending on if it's a "generic" enough IR instruction, can then generate either generic IR instructions to implement the same thing (e.g. a "count leading zeros" can be implemented in any number of ways)

5. The backend will then have specific ARCH_ASM registered optimization passes for being able to do things like

6. The backend finally lowers the generated IR

What do you think of this proposal?
I think a main show-stopper is actually implementing the various selection toggles for the CPUs in a way that can be extended into the future, though I suspect it will slap me in the face in the coming weeks while I'm at work.

[LADSoft]

I wasn't sure what you meant in #5 as it seems truncated, I suppose you meant that certain of the new IR instructions would have to be resolved by the backend not the optimizer...

i think this proposal sounds solid.

There are a lot of details especially with configuring the parser.... seems like you'd have to have the feature bits themselves parsed out but don't know how that would be done....

I think though we might have to have a 'generic' IR instruction with an opcode or something. Maybe a flag indicating whether the instruction is targeted at the optimizer or the backend.... don't know offhand that it would be useful but might eventually come in handy....

[chuggafan]

Yhea, I accidentally truncated bullet point 5.
The main issue with feature-bits and parsing it will be:

The custom architecture support in the front-end for declaring what we do and don't have (We need to only activate x86 flag declarations in x86 mode).
The other problem is: amd64 has more than 64 "flags" for instruction support already, sadly. So we would need to make a somewhat generic method for determining what flag is set where for an architecture and then deal with that as the time comes....
Maybe a class enum where each time a flag is set we product an enum of a specific type after a certain point, so when we extend the classes and type-cast the holding type we get the platform-specific flag holder and then type-cast downwards so that it's both generic and can have the information be recovered later? 🤔

Anyways, my idea for the IR instruction is literally to insert an i_ops rigtht before the msil i_ops called i_backend_specific, which will denote that it's a backend-specific IR operation, and then make it a multi-part operation with archtecture-callout + the actual specific instruction that gets sent to the ARCH specific backend for lowering.
LLVM does it similar but also different to my proposal here, I just checked, e.g. _mm_pause compiles to this IR which is a call to the function llvm.x86.sse2.pause (similarly, the crc32 functions compile down to something else that's a call as shown here , I think something like my proposal which is similar would be more than acceptable here. (though in llvm it seems it's all implemented as function calls that get lowered to the backend IR instructions afterwards which then get register allocation done to it)

Ultimately we really want the backend-instruction for intrinsic generation made so that we can allocate the registers after we insert our special-instructions, which is the heart of this project in my view.

[chuggafan]

I think an update to this that would satisfy me is actually just the current builtin support, but with automatic register selection. This would remove the problem I currently have with needing to do the header/footer for setup/teardown in the rotate functions, etc. and allows for me to take advantage of theoretical IR instructions (hopefully) for doing moving to/from packed/unpacked vector stuffs, which would be nice for if/when we make the compiler vectorizing years down the line or if anyone ever wants to contribute something like that...

I need to sit down and just make a plan and then execute, but I also need to finish up my current work...

[LADSoft]

so you are looking at adding custom intermediate instructions for various things and letting the normal register allocation and so forth work on that? Then maybe having custom code generation in the back end?

[chuggafan]

Hmmmm more thinking of this in relation to #1112
Let's say we want to implement __builtin_memcpy. This is something I think that can be illustrated what I want out of "Middle IR" builtin support. In this case, we have the gen.cpp asm_assnblock IR transform. We could, in theory, translate a call to memcpy into a set of the currently existing calls:

1. Known short
2. Known medium
3. Known long/Unknown (calls memcpy
   With this change we can speed up the common memcpy or even memset call to zero. This is the kind of thing I want our "middle IR" to take care of. Anything platform-independent in theory that can be lowered to platform-specialized code.

The final section is something like __m128i support, where we have SSE intrinsics that get optimized around like normal code alongside, say, uint64_t.
I need to sit down and think, because I want my #1112 refsrc to be compilable even if it doesn't make too much sense, just to keep as much as possible "in C" so-to-speak.
I should probably swap to rolling asm inside of the impl and then use the generated prologue/epilogue but whatever.

[LADSoft]

as far as things like the memcpy, there was support for that in the older compiler. Idon't know if i moved it forward then deleted it or just didn't move it forward...

but yeah, we could 'mark' each keyword we add with some flags saying what the target for processing it is... either the middle layer (occopt) or the end (occ). That would speeed up the determiniation of who would look at it... for the Intermediate Code I might suggest a generic instruction (e.g. something like builtins for the builtin library function) that is then qualified with a subfield telling which builtin to be compiling for... Im not sure what the best way is to hold the argumments given that many of these funcgtions have more than the intermediate code structure can handle... the obvious one is to continue the way we've been going and just 'push' arguments the same way you would push them for functions, then let the middle layer or backend replace the pushes with a saner sequence of code similar to the way the existing builtins work... i don't know if this is the besgt way to go but on the other hand whenever we get to x64 we will be required to do such conversions for standard function calls anyway (as per the abi).

[chuggafan]

I mean, we could go the LLVM route.
https://mcyoung.xyz/2023/08/01/llvm-ir/
I think bundling up function calls with their SSA form might allow us to lower the arguments easier.
I was originally thinking of us doing an IR-level "paramadj" where we adjust all the parameters (in that IR call) before we make the IR callout to a function, but the LLVM-style also works.
Currently according to the .icd files we assign temporaries and then declare them parameters before a call, we can instead assign temporaries as parameters in one IR instruction and assign the SSA result in one "IR-level" instruction, (I think we do that already).

Example of the param adjustment as we currently do it:

	BLOCK 3
	DBG Block START
; Line 69:	    { 

	DBG Block START
; Line 70:	        return memcpy_basic(s1, s2, sz); 

	T10(EAX).UI =   _sz:LINK(12).UI
	PARM	T10(EAX).UI
	T11(EAX).A =   _s2:LINK(8).A
	PARM	T11(EAX).A
	T12(EAX).A =   _s1:LINK(4).A
	PARM	T12(EAX).A
	TAG
	GOSUB	#_memcpy_basic:PC.UI
	T13(EAX).A =   RV.T0(EAX).A
	PARMADJ	#C.N
	RV.T1(EAX).A =   T13(EAX).A
	GOTO	L_23:PC
; Line 71:	    } 

My basic idea:

PARAMSETUP (a.A, b.A, c.UI)
CALL #_memcpy_basic:PC.UI
T13.A = RV.A

An LLVM-style (minus all of the decorators LLVM throws around everywhere:

T{whatever} = call _memcpy_basic(a.A, b.A, c.UI)

[LADSoft]

that might make things a lot cleaner in the various cases where we have to parse through an argument list....