CC64 Compiler
Page 3 of 3

Author:  robfinch [ Tue Aug 28, 2018 3:40 am ]
Post subject:  Re: CC64 Compiler

The compiler continues to evolve. Color graphing still doesn’t work yet but a lot of code is written. To do are the insertions of spill and load code. I’m not sure I entirely understand parts of it so there was some guesswork involved. I’ve found the pseudo-code in the Briggs thesis helpful. Just detailed enough to get the idea.

Declare() is a monster function comprised of several hundred LOC used in declaration parsing. It does a wide variety of miscellaneous things required for parsing the declaration. So, I’m trying to break it up into several smaller functions to make it more manageable.
Been rearranging (refactoring?) the code somewhat today. Organizing parts of the parsing, optimization, and code generation to be underneath other classes. I’m not sure this is a wise choice. For instance rather than have a file called ParseEverything, parsing is broken up and falls under expression processing (ENODE.cpp), statement (Statement.cpp) processing and declaration parsing. This is based on the primary object that the parsing method is working with. It’s a matter of what’s the most convenient to work with. It was convenient for instance to have all the optimization code in one file.

Author:  robfinch [ Wed Aug 29, 2018 5:08 am ]
Post subject:  Re: CC64 Compiler

Global variables are slowly being moved so they are class members. Currently the compiler optimizes and generates code for functions one at a time as it’s parsing declarations. An eventual goal is to make it possible to do whole program optimizations. There are a lot of global variables that could really just be members of the ‘Function’ class or other classes.
Right now, the compiler uses a ton of memory (approx. 20MB) just to compile in it’s function by function basis. But with a machine with gigabytes of ram perhaps some more state could be retained in the compiler for whole program optimizations.

Author:  robfinch [ Sat Sep 01, 2018 3:49 am ]
Post subject:  Re: CC64 Compiler

Played around with some of the CC64 language constructs. CC64 allows use of the ‘then’ keyword in an if statement. It now accepts a syntax where the brackets around the if expression are not required if a ‘then’ is used.
A do-once loop construct was invented by allowing the ‘while’ at the end of a do loop to be omitted. In that case the body of the loop will be executed only a single time, unless… there’s a continue statement within the body of the do statement. Continue will cause a loop back to the top. Inserting a break statement causes the do to be broken as per usual operation. All statements are effectively ‘do’ (done) statements except the ‘do’ is missing.

So the following code prints “hello” only one time.
do {
} // no while


do printf(“Hello”);

Using a ‘do’ increases the loop depth tracked by the compiler. It may be used to help prioritize register allocations, giving a boost in priority to operations performed within the ‘do’.
Note that following a do-once loop with the while loop is confusing. The ‘while’ keyword will associate with an immediately previous ‘do’ statement because it looks like a ‘do-while’ statement to the compiler. So, to follow a do-once with a while loop an extra statement separator (’;’) is required.

I've been having fun debugging the register allocator. Something isn't working quite right yet. I suspect it has to do with the interference graph. There isn't enough interferences so the allocator uses too few registers.

Author:  robfinch [ Sun Sep 02, 2018 2:49 am ]
Post subject:  Re: CC64 Compiler

Slowly ironing out the bugs in the color graphing register allocator.
A problem that held me up for quite a while was iterating backwards through the basic blocks, a loop termination condition wasn’t correct so only a single instruction was examined out of the block. It was a single character typo difficult to spot by inspection. It was also difficult to find by stepping through code.
I finally got the register allocator to assign different colors to different live ranges. Another problem was clearing the set of used colors was being done inside a loop and it should have been outside.
Yet another problem was reconsidering already colored ranges in subsequent passes of the colorizer. Too much state was effectively reset.
I didn’t implement the renumber stage of allocator. Instead of going by a set of values, the virtual registers numbers are used directly. This takes significantly more memory in the interference graph which then has a lot of unused space. However, the amount of memory in use (20MB) is still small compared to the amount of memory in the workstation. I’ve found in recent times that I have a tendency to use memory hungry algorithms that are simplified versions of final ones.

It’s almost working. I still have to polish off the spill and fill code.
I’ve noticed the allocator does a ton of stores and loads in larger routines. I’m not sure it’s worth the extra memory overhead. There likely is something wrong with the code yet. Compiling the code also seems sluggish compared to the simpler allocator. Still it only takes less than a second to compile a file.
I have an ulterior motive for getting color graphing working. If it works well enough maybe a machine with only 16 regs could be in the works.

Author:  BigEd [ Sun Sep 02, 2018 5:33 am ]
Post subject:  Re: CC64 Compiler

Interesting - it feels like register allocation was a very hot topic at one point, although maybe the best known approaches have stabilised now. As you say, with improved compiler technology, maybe a simpler/cheaper/smaller CPU will suffice.

Author:  robfinch [ Sun Sep 02, 2018 7:34 am ]
Post subject:  Re: CC64 Compiler

I have come. I have conquered. The register allocator was one thing I wanted to understand, and I think I have a pretty good handle on it now. I await for a GC book to arrive in the mail. I follow comp.arch. One of the latest topics there is superconducting computers. I wonder if they could be implemented using room-temperature super-conductors.

Author:  BigEd [ Sun Sep 02, 2018 7:36 am ]
Post subject:  Re: CC64 Compiler

I realise there's another point lurking in your adventure: if you make a CPU with too many resources for the compiler to use, you may have something more complex/large/costly than you should have. At least, until the compiler catches up.

Author:  robfinch [ Mon Sep 03, 2018 3:19 am ]
Post subject:  Re: CC64 Compiler

Labels on the mind tonight.
Creating the control flow graph has to find labels. In my simple implementation it calls a routine called ‘FindLabel’ which searches the entire peep list of instructions for the label. Well that’s inefficient and slow. So, I switched it to looking up the label in a table of labels which uses the label number as it’s index. This is just directly reading a single word without having to search. The cost is the label table has to be built, but it turns out there’s a place to do this when the optimizer is checking for unreferenced labels.
Upgraded the O(n^2) algorithm for removal of unreferenced labels to O(n). When I initially wrote it I didn’t worry too much about it as functions are generally small <100 LOC.
I’ve made several improvements to the compiler but I’ve yet to notice much difference in speed. It’s likely limited by loading of the file to be compiled.

Author:  robfinch [ Fri Sep 07, 2018 3:19 am ]
Post subject:  Re: CC64 Compiler

Tonight’s issue was that I created a do-once construct but didn’t update the optimizer to process it. This left a block of un-optimized code in the output. It took a bit of tracing to track down.

Author:  robfinch [ Sat Sep 08, 2018 2:17 am ]
Post subject:  Re: CC64 Compiler

Changed the expression parser so that it places immediate operands as the second operand (swaps order if necessary) for multiply and add operations. This allows the compiler to use immediate mode rather than loading a value into a register first. This is a very simple optimization which is done at parse time and so available even if optimization is turned off. In theory the optimizer already does this swapping around but it seems to sometimes miss opportunities depending on the order of expression nodes.

I put some time into the eventual creation of an LLVM version.

Author:  robfinch [ Sun Sep 09, 2018 9:12 pm ]
Post subject:  Re: CC64 Compiler

Spent much of the last two days (excepting a barbeque get-together, and some other mudane tasks) trying to get cmake to recognize commands. This is needed to build LLVM. I started working on table definitions for FT64. LLVM seems fairly reasonable to learn.

Continuing on with CC64: I loaded the instruction table into Excel, sorted it, then copied it back to the source code. I found several duplicated opcodes as a result. Sorting the opcode table is in preparation for being able to parse assembly language text. Looking up the mnemonics is going to use a simple binary search as opposed to a trie search since the mnemonics are already available to be used for output.

Page 3 of 3 All times are UTC
Powered by phpBB® Forum Software © phpBB Group