Superscalar Stack Processor: Optimization

The continuation of a series of articles exploring the idea of ​​a superscalar processor with
OoO and the frontend of a stacked machine. The topic of this article is optimization of memory accesses.

Previous articles:
1 - description of work on a linear piece
2 - function calls, save registers
3 - function calls, inside view


Until now, we have not paid attention to the weak point of all stacked machines - excessive memory accesses.

In fact, when the naive code generator of the stack machine wants to get the value of the variable 'a', it writes the instruction 'push a'. The stack processor does not provide opportunities to refer to an already-calculated expression or its part.

For register processors, the compiler solves this problem by introducing temporary variables with possible placement in registers. It is worthwhile to come up with a similar mechanism for our outwardly non-register architecture.

However, it’s almost not necessary to invent anything, “everything has already been stolen before us” (C).

• introduce bookmarks
• bookmark - a register that the compiler can access by number, register numbers and bookmarks are not required to match, although this would make life easier
• the compiler for each function determines the number of bookmarks that it is going to have
• when the function starts, the required number of registers is highlighted under bookmarks, they cannot be freed until the function is completed
• bookmarks fall inside the register window and the FILL / SPILL mechanism acts on them
• if the compiler considers the calculated value to be valuable, it sets the bookmark, for example, with the instruction 'bmk 1', which means: the value on the top of the stack is now considered bookmark number 1. Does this copy the value to the bookmark register N1 or does the register responsible for this bookmark, not important, implementation details
• when in the future the compiler needs a value from this tab, he can use it, for example, like this: 'add_bmk 1', i.e. the value from the top of the stack will be summed with the value of bookmark 1 and replaced by this value
• from the point of view of the processor backend, the good old mop of summing two registers in the third will be generated
• there is a need for a second line of arithmetic and logical instructions (add-> add_bmk, mul-> mull_bmk, cmp-> cmp_bmk), but it's worth it
• or more general option - any of the arguments or the result of three (two) -adress instructions can be a bookmark
• you can imagine the dynamic selection of bookmarks, without highlighting their maximum number in order to optimize the number of registers used, but this (at first glance) looks too cruel to the hardware

As a result, the compiler has two relatively new resources for optimization.

The first is the identification and placement of bookmarks, the number of which can be quite large, it is not limited by the number of available registers for the lack of such. By and large, this is the equivalent of local variables located on the “fast” stack.

The second is an equivalent transformation of expressions to a form in which internal parallelism is maximally manifested. The compiler tries to reduce the height of expression trees by growing in breadth.

Well, let's not forget about traditional optimization techniques that are not oriented to registers and their distribution.

In order to understand how this can be implemented, take a look at the
possibilities that the LLVM assembler provides us. We are not going to really ignore the entire “cultural layer” accumulated in this area.

LLVM

int a(int m, int n)
{
    if (m == 0)
        return n + 1;
    if (n == 0)
        return a(m - 1, 1);
    return a(m - 1, a(m, n - 1));
}

Here we see only the control flow instructions, there are no places where the specificity of the stack machine could manifest itself (except for such a calculation + -1).

What about the “butterfly” FFT, (this is more likely from the data flow area)?

The body of the nested LLVM assembler loops
(clang -c bc -O3 --target = xcore -emit-llvm -S -o b_o3.ll) looks like this:

In the form of a dependency graph between instructions, it looks like this:

Offhand, each vertex of the tree from which more than one edge comes out is a candidate for the title of a bookmark. At least in terms of floating point computing.

In any case, the implementation of the described architecture in LLVM does not look like a hopeless event.

Dot file, suddenly come in handy:

Epilogue

So we came to the preliminary finish.
We figured out why a new architecture is needed, and suggested a solution.
Initially, the question was whether this architecture meets the set requirements.
And now we can answer, yes, at least in that small part C, which we managed to verify, we got

• expected hardware simplification
• externally invisible scalability in the number of registers
• as well as the number of functional devices
• potential compiler simplification

At first (amateurish) glance, fundamental problems are not visible that impede the implementation of such an architecture in hardware.

We intentionally did not consider such things as:

• floating point calculations, do they need a separate stack, ...
• saving processor state when switching context
• interruptions
• ...

All these questions are important, but less fundamental.
And at the moment, the author considers his task completed.