Superscalar Stacking Processor: Optimization

Continuation of a series of articles that analyze the idea of ​​a superscalar processor
OoO and stack machine frontend . The topic of this article is the optimization of memory accesses.

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


Until now, we have not paid attention to the weak point of all stack machines — redundant memory accesses.
')
In fact, when the naive Kodo generator of a stack machine wants to get the value of the variable 'a', it writes the instruction 'push a'. There is no possibility to refer to an already computed expression or its piece by the stack processor.

For register processors, the compiler solves this problem by introducing temporary variables with possible placement in registers. It is worth inventing a similar mechanism for our seemingly non-register architecture.

However, there is almost no need to invent something, “everything is already stolen before us” (C).

• we will enter the device of bookmarks (bookmarks)
• bookmark - the register to which the compiler can refer to the number, register and bookmark numbers are not required to match, although it would simplify life
• the compiler for each function determines the number of bookmarks that it is going to have
• at the start of the function, the required number of registers is allocated under the bookmarks;
• bookmarks get inside the register window and are acted upon by the FILL / SPILL mechanism
• if the compiler considers the calculated value to be valuable, then it sets the bookmark, for example, with the instruction 'bmk 1', which means: the value at the top of the stack is now considered bookmark number 1. Does the value copy to the bookmark register N1 or is the register responsible for this bookmark, no matter implementation details
• when in the future the compiler needs the value from this tab, it 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 tab 1 and replaced with this value
• from the point of view of the processor backend, the good old mop summation of the two registers into the third one 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 a more general variant - any of the arguments or the result of the three (two) -address instructions can be bookmarked
• You can imagine the dynamic allocation of bookmarks, without allocating the maximum number of bookmarks in order to optimize the number of registers used, but this (at first glance) looks too cruel in relation to the gland

As a result, the compiler has two conditionally 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 to the number of available registers for the lack thereof. By and large, this is the equivalent of local variables located in 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 the traditional optimization techniques that are not focused on registers and their distribution.

In order to figure out how this can be implemented, take a look at those
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 instructions of the control flow; there are no places where the specificity of the stack machine could manifest itself (except for such a calculation + -1).

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

Body of the most nested loops assembler LLVM
(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 extends is a candidate for the title of a bookmark. At least in terms of floating point calculations.

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

Here we come to the preliminary finish.
Understood why you need a new architecture, offered a solution.
Initially, the question was whether this architecture meets the requirements.
And now we can answer, yes, at least in that small part of C, which we managed to verify, we received

• expected hardware simplification
• outwardly imperceptible scalability by the number of registers
• as well as the number of functional devices
• potential compiler simplification

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

We intentionally did not consider such things as:

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

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