[libre-riscv-dev] LD/ST address matcher

Luke Kenneth Casson Leighton lkcl at lkcl.net
Mon Jun 3 15:37:29 BST 2019


Am making progress understanding the LD/ST Dependency Matrix, after staring
at it for nearly four hours. More on this later.

Another sub-task is to detect overlapping addresses. Or, at least to work
out if the addresses MIGHT overlap. If the algorithm is overzealous, all it
does is affect performance as the engine has to drop down near to single

Jacob, what sort of LD/ST profile can we expect from Kazan? The reason for
asking is because the simplest algorithm is to check bits 4 through 15 or
so and ignore the bottom 4 bits and everything 16 or above.

The result of doing that would be that a byte LD/ST would hit against a
DWORD 64 bit LD/ST, ie be detected as "needs to be treated as single-issue,
no parallism allowed".

A better algorithm would be to additionally take the bottom 4 bits, and
expand them out into a bitmap.  A byte LD/ST would have 1 bit set, a
misaligned WORD LD/ST would have 4 bits set somewhere on a nonaligned
boundary, and so on.

I believe it would be as simple as:

1/3/0xf/0xff << (offset)

Where offset is:

* bit 3 of the address if the size is 8
* bits 2 to 3 if it is 4
* bits 1 to 3 if size is 2
* bits 0 to 3 if size is 1 byte.

That would create the bitmap, which would work for aligned as well as
misaligned hit/matches.

The alternative is to do an NxN set of range compares, checking the *range*
of address plus size against all other addresses plus sizes.


1 is this even necessary
2 are there any alternative algorithms


crowd-funded eco-conscious hardware: https://www.crowdsupply.com/eoma68

More information about the libre-riscv-dev mailing list