Hi everyone,

This has been something that has been on my mind for a while now, but with my increasingly more complex optimisations being developed for the Free Pascal Compiler and the code becoming an ever bigger spiderweb of conditions, it got me to start wondering... might compiler optimisation be a candidate for AI? Often I try to hand-optimise assembly language to get the same output in fewer cycles (and fewer bytes too if possible), and then see if I can program the compiler to match it.  I can't hope to catch every possible optimisation though, and I wonder if using an AI in some way to develop more efficient machine code has ever been a serious contender for research.  I have heard of stories like the Deepmind AI finding a faster way to multiply matrices, so it seems logical that it can improve instruction processes.

This is probably a lazy question, but what would be a good set of resources when it comes to beginning machine learning, or at the very least building simple models?  When it comes to hardware, I have a couple of 3060 Tis at my disposal for some parallel computation.

Kit

This is an interesting idea indeed.

https://www.researchgate.net/publication/343322212_Automatic_Code_Optimization_With_Machine_Learning_And_Combinatorial_Optimization

https://www.ijresm.com/Vol.2_2019/Vol2_Iss4_April19/IJRESM_V2_I4_149.pdf - Compiler Optimization using Artificial Intelligence

https://arxiv.org/pdf/2110.09610.pdf - A Survey on Machine Learning Techniques for Source Code Analysis

https://openreview.net/forum?id=SKat5ZX5RET - Self-Programming Artificial Intelligence Using Code-Generating Language Models

The above links might give ideas for some googling.

On Thu, Nov 10, 2022 at 3:10 PM J. Gareth Moreton via fpc-devel <

You still need to feed the model with the necessary rules and with necessary training data of both correct and incorrect approaches.

But even then *I* wouldn't want to have any of that black box mambo jumbo in FPC, cause when a bug occurs in the optimizations due to some decision the model made... well... tough luck. With the current approach you need to bash your head a bit against the next wall to find the location of the issue, but with a machine learning approach (let's not call it AI, cause there's nothing “intelligent” about that) you can't even do that. You can only fiddle with what you fed into the model and hope for the best (and wonder why it now fails at a completely different area).

Regards,
Sven

That's fair.  Currently in my eyes it's more of an academic curiosity currently that i would probably take parts of and program conventionally.

Funny how you mention "black box" because recently there was a news article about scientists increasingly not understanding why machine learning is working the way it is with apparent patterns of emergent behaviour.

Kit

Hi,

Well, a few years back I read a paper (maybe it was linked before in the thread no idea), that embraced this, and used a genetic algorithm for optimization, basically, took the default compiler output, and just started to change instructions randomly to see if it performed better... 99,99999% cases it crashed, but eventually there was a version that performed better. So for the next iteration that was taken as baseline. (Of course, with the necessary state-verifications surrounding the code.)

Now, I could still see a billion ways this could fall apart (what if you change input data, so you have to combine it with some fuzzing too for sure?), but it was an interesting idea nevertheless. And of course, unbelievably slow.

Anyway, until a simple memory layout change and pure chances of caching in a live system change can cause huge differences in code performance, sometimes bigger changes than the optimizer can make(!) the entire excercise is largely pointless, IMO. As much as one of course don't want to generate total junk as code, in real world applications there are usually bigger wins to be had just by improving the used algorithms.

(I've seen a talk about this once, where they basically measured GCC's optimizer against caching and code layout changes, and the optimizer's effect was mostly within measurement error, apart from a few big things like register variables... Which is nuts.)

Charlie

I wouldn't advocate a neural network within FPC since, yes, it would be unbelievably slow, very difficult to port and even more difficult to maintain and verify... not just to confirm correct output (e.g. BSR is good as an approximation to the expression "floor(log2(x))", but it has some awkwardness if the input is zero) but also to ensure something undesired (i.e. a backdoor) hasn't been slipped inside the assembly language.  I would be curious to see a neural net be able to improve on small algorithms though.

My slight concern is that the x86 peephole optimizer is becoming pretty bloated now, mostly thanks to my slightly haphazard development (I see a source of improvement in a particular set of circumstances), and while studying a diff of the output, I see another block of assembly language nearby and think 'that could be improved too', and the end result is a massive jungle of "if... then" blocks, which I suppose is the ultimate building block of artificial intelligence (one for Sven... "The Diamond Age" by Neal Stephenson has characters use the term "pseudo intelligence" instead, with the characters remarking that it's more accurate!)

Ultimately I want to look for cleaner and more fundamental solutions since each new feature makes the compiler more bloated. Then again, if you compare the speed and size of the generated binaries between the trunk and a couple of releases ago, the difference is paramount.  I can't remember the proverb that Florian used (in a sense, approving of small peephole optimizer changes), but one I learned in Chinese martial arts would be "the journey of a thousand miles starts with a single step"... lots and lots of small changes that individually are almost pointless, but which build up over time and when you look back at the starting point, the difference becomes very apparent.

To get back to the point, I wouldn't advocate giving FPC a neural network, or any compiler really except as a development aid, with generated results having an implicit "hey, might this work?" for the developer.  Random instruction changes doesn't feel particularly robust though, and I would wonder if a neural net would work out how to change, say "y := x div 3;" to "y := High32Bits(x * $AAAAAAAB) shr 1" ... essentially turning a division by a constant into a multiplication by its reciprocal, which a lot of compilers use (including FPC on x86 and AArch64) to get around the integer division instruction being rather slow.

Kit

J. Gareth Moreton schrieb am Do., 10. Nov.
2022, 23:26:

That and similar articles about this are why I mentioned this ;)

Regards,
Sven

On Thu, Nov 10, 2022 at 8:10 PM J. Gareth Moreton via fpc-devel <

An interersting thought. On a slightly different tangent, could the language rules itself not be codified as a matrix so that one can use matrix algebra to perform node level optimizations via similarity transforms? Alternatively, if you want to test a candidate optimization idea, check if there is a feasible solution using matrix algebra (in other words check if it satisfies all the language rules and the original intent). My simplistic view of Pascal is that the language rules should form a set of linear equations (else the language specification is overly complicated), so linear algebra is ideal for checking if a potential solution satisfies the language rules. Also one could cast a node level optimization as a (similarity?) transformation matrix and apply this to the basic nodes generated by the parser.

So there is perhaps some scope for "simple" algebra before diving into stochastic optimization techniques.

J. Gareth Moreton wrote

My slight concern is that the x86 peephole optimizer is becoming pretty bloated now

An alternative could be to specify the peephole optimizations in a pattern matching format, and then either write a tool that converts them to a bunch of if-then-else statements, or interpret this format directly in the compiler.

Jonas

Or maybe predicting branch taken  taking more into consideration than which node of if..then..else it is.

I'm liking these discussions!

I have done some refactoring, such as attempting to 'factor out' common conditions (sometimes a matching instruction, but also commonly the operand types).  Sometimes I choose not to factor - for example, sometimes I try to compute relatively cheap conditions first and delay things like GetNextInstruction for as long as possible due to its relative slowness (stepping through a linked list).

Pattern matching ideas do sound good honestly - it would especially be good for simple, 2-instruction optimisations, say. That's definitely somehing I want to try somewhere.

Kit