6

Context

SDCC claims to support C11. I use it to write games on Z80 target (for fun and experience).

C11 defines restrict

C11 specifies the restrict keyword on pointers, which can improve generated code speed (and size often).

In a nutshell, when the programmer adds restrict to a pointer definition, they (the programmer) promises that the memory accessed by this pointer will never overlap with any other memory. It is very often the case in (sane) API usage, but the compiler cannot guess what's sane.

Restrict and retrocomputing

Now, back to our retro world. Analysis and examples in Demystifying The Restrict Keyword analyses this in terms of load scheduling, which doesn't exist in Z80 (no delay, loads and store are committed at the end of all such instructions).

That said, though the example in Wikipedia mentions "'load' may have to wait until preceding 'store' completes", the example still partially makes sense without such notions.

Incidentally, although SDCC implements a number of optimizations, enough to actually produce good Z80 code, SDCC manual does not mention restrict (or even strict aliasing rules).

Question 1

Is restrict actually useful in a Z80 context? Intuitively it does make sense, but perhaps in practice due to the small number of registers it virtually never practically makes sense?

Experiment before asking

  • I compiled the example code on the Wikipedia page about restrict with and without the restrict keyword, the result was exactly the same.
  • I simplified the code using char * instead of size_t *, the code was simpler on both sides.
  • All compilations with sdcc -mz80 --allow-unsafe-read --max-allocs-per-node 100000 and two variants: --opt-code-size and --opt-code-speed.

Result: in all cases, adding restrict keyword did not change generated code at all.

SDCC: read the source before asking

Does SDCC actually meaningfully implement restrict? Checking the source code I can only confirm that it performs some checks (see for example https://sourceforge.net/p/sdcc/code/HEAD/tree/trunk/sdcc/src/SDCCicode.c#l2010 ), but cannot confirm that adding the keyword in source code can actually change generated code in any situation.

Code style

The example in Wikipedia :

void updatePtrs(size_t *ptrA, size_t *ptrB, size_t *val)
{
  *ptrA += *val;
  *ptrB += *val;
}

can be rewritten

void updatePtrs(size_t *ptrA, size_t *ptrB, size_t *val)
{
  size_t v = *val;
  *ptrA += v;
  *ptrB += v;
}

In practice, generated Z80 is slightly better, but restrict still changed nothing. Perhaps writing C in a specific style is what counts in such a context?

(Considerations like "use global variables because Z80 is inefficient dealing with C-style stack and even code that access data at variable location" are generally relevant but that's not what I'm asking for.)

Questions

  • Can anyone confirm what SDCC does with the restrict keyword?
  • Can anyone provide style recommendations specific to the topic or pointer aliasing and the benefit supposedly provided by the restrict keywords when the compiler does not actually support it?
  • 10
    SDCC is an actual product (and so is C11) in active development with up to date versions and support. Questions about it's working should be targeted to their support (forums), not RC.SE (P.S.: Good question and well presented - so if you really want to avoid the primary source, maybe try stack overflow instead?) – Raffzahn Nov 8 at 21:29
  • 1
    Thank you @Raffzahn for your comment. Maybe I can rephrase the question less SDCC-specific and more about whether restrict makes sense on a retro target? – Stéphane Gourichon Nov 8 at 21:32
  • 1
    Neither code example in your question uses restrict so it's not clear how you arrived at the conclusion that restrict doesn't affect code generation. Note that only the first example you gave would benefit from the restrict keyword. Also you've misunderstood Demystifying The Restrict Keyword article, restrict has nothing to do with how CPUs might perform "load scheduling", but how the compiler generates code. "proper use of the restrict keyword gives the compiler enough information to select a more optimal order of loads and stores" (emphasis mine). – Ross Ridge Nov 8 at 22:15
  • 2
    @Tommy Found my error in counting T-states. The code size is the same, but the code written with explicit common variable shaves 3 T-states. So far, restrict is not used by the compiler, manual C style does win. – Stéphane Gourichon Nov 8 at 22:31
  • 2
    "What topics can I ask about here? ... how to use or preserve computing equipment that is no longer manufactured or supported by the manufacturer." - SDCC specifically supports Z80 based retro computers, therefore questions relating to that use are relevant IMO. – Bruce Abbott Nov 11 at 20:36
6

SDCC "supports" the restrict keyword as a requirement of supporting C11. Supporting C11 allows it to compile code written for other modern compilers more easily. Programmers may also use restrict as a means of having the compiler check certain aspects of their work, reducing the number of difficult-to-diagnose bugs they introduce.

Due to the simplicity of the Z80 CPU, the only measures needed to correctly support restrict are recognising the keyword in its correct syntactical context, checking that the preconditions for using restrict are verified to the extent that the C11 standard requires, and issuing diagnostics if the input code does not conform. No changes to code generation are required, in much the same way as for the const keyword.

  • No changes to code generation are required for any implementation of C11 for any target. There's nothing in the standard that says a compiler must implement optimisations in response to restrict. Furthermore there are optimisations you can apply if restrict is used that work as well for the Z80 as any other processor. – JeremyP Nov 12 at 13:35
5

Preface: I just commented in support of my close request, that the question is, in its current way, as well as in any simple rephrasing I could think, of off-topic for RC.SE due its recent nature of C11 as well as SDCC. Both of the questions voiced at the end are about the same non-RC.SE quality.

Following Stéphane's intend for rephrase I came to think that looking at the base and motivation for 'restrict' to be added to C in fact can lead to some RC.SE relevant topic and knowledge - except, it would be a total different question, not any kind of rephrasing.


At the core, restrict is about telling the compiler that, within a given code section (scope), no aliasing of pointers exist. Aliasing means simply that they point to the same (overlapping) memory location.

While this information seams at first of just theoretical relevance, it becomes important when considering that modern (*1) CPUs rely on pipelining, reordering and caching. Within this context it becomes quite helpful for compilers to assume every target accessed by a pointer is guaranteed to be not accessed by any other pointer at the same time.

  • Without restrict, the compiler has to make sure all pointed to access is sequenced and completed, before any other pointed access is done.

  • With restrict, the compiler can interleave access and manipulation of different pointer targets in arbitrary order, leaving room for pipelines and caches to perform well.


[Insert Practical example]

Lets take two operations on an array, handling two elements independently

Array(I) := Array(I) + 1.
Array(J) := Array(J) - 1.

Without telling the compiler that I and J never hold the same value, it has to produce code that finishes accessing the first before touching the second, which might look like this:

LOAD  reg,Array(I)
INC   reg
STORE reg,Array(I)
LOAD  reg,Array(J)
INC   reg
STORE reg,Array(J)

On a pipelined CPU this might stall the execution, as each instruction has to wait for the prior to finish before it can execute. While caching might help a bit, neither reordering nor a write buffer will be of any use here. In fact, this is close to the worst case of code for a modern CP.

By declaring the pointers as independent and never overlapping, the compiler may interleave the code of both lines (and maybe others to come, depending on the pipeline structure), allowing code like:

LOAD  reg1,Array(I)
LOAD  reg2,Array(J)
INC   reg1
INC   reg2
STORE reg1,Array(I)
STORE reg2,Array(J)

Now each instruction gets time to 'settle' before its result is needed, thus allowing pipelined operation. as well as write back buffering and alike.

And yes, interleaving has not been superseded by instruction reordering in (more) modern CPUs, as these mechanics can still not guess dependencies, and checking for addresses can only be done at a (rather) late stage, so not gaining as much as already interleaved code does.


So at the core, restrict is a hint for compilers to allow generation of interleaved code, code 'modern' systems benefit a lot from.

'Modern' is the key word in relation to classic (micro) processors - they do not use pipelining (*2). That's especially true for oldtimers like a Z80 (*3). It doesn't matter if above code is generated interleaved or not, as it would not improve performance at all.

So re-thinking above question in context of RC.SE would mean to ask:

When became CPUs pipelined in a way that benefits from interleaved code?

Which is ratehr trivial. Or put more specific to Stéphane's Z80 case:

Does the Z80 benefit from interleaved code in respect to execution speed?

Which would make a good question - cursed with a rather simple answer:

No.

In case of C11 this means that restrict solves an issue that can not arise on a Z80 at all. Thus SDCC will (and should) not generate different code if present or not.


*1 - Modern feels a bit wrong here, as such features are mainstream since the late 1960s - it just took some time until they reached micros as well - just, I have a hard time to come up with an equally spot on term.

*2 - No, the 6502 does not count, as it's pipeline is more of a prefetch than a real pipeline with separate stages for data access and execution.

*3 - And interestingly as well for first generation RISC CPUs. After all, it was their main design goal to get rid of dependencies between instructions to reduce complexity of pipelined execution. Something that got lost soon after.

  • 2
    Your simple answer "no" is wrong. Consider a[j] = a[i]+1; a[j+1] = a[i]; Without restrict the compiler must re-load i, then reload a[i] to execute the second statement, since maybe i = j, or even a[j] is the same memory address as i and similar things, if a, i, and j are parameters of a function for example!. With restrict the two statements can be optimized for common expressions to give "load a[i] to register, store a[j+1] from register, increment register, store a[j] from register". – alephzero Nov 9 at 0:35
  • 2
    Erm, @alephzero, for one, please read it in whole. Doing so should show that above is about trying to put the question into an RC.SE related framework - done by focusing on the prime issue why restrict was introduced in the first place: to hint possible creation of interleaved code. Your example is about exerting further optimizations that became possible in addition. Now, I do understand the fascination of optimization, but if you want to discuss abilities and strategies of modern compilers, RC.SE might not be the best place – Raffzahn Nov 9 at 3:57
  • 1
    @alephzero is correct. The primary reason for restrict is to allow the compiler to apply optimisations of any type, not just out of order execution. The primary reason, in fact is so the compiler can assume that writing to the content of pointer will not affect the content of another. For example, *p = *q; x = *q;, if p and q are restrict then the compiler can assume it doesn't have to fetch *q again to assign x if *q is in a register. – JeremyP Nov 11 at 16:18
  • 1
    @JeremyP I would ask you as well to read the answer (as well as the comment you're reffering to). There's no point about him being incorrect that further optimizations can be done. It's about answering the base ob this question in respect to historic development - not about what C11 in general and restrict in particular can do. Such would be discussing modern compiler design and most definite off topic here. There is a great audience for such issues on other places, don't you think so? – Raffzahn Nov 12 at 9:29
  • 1
    @Raffzahn I read your answer. It is wrong. The restrict keyword would be useful for a compiler targeting the Z80. Allowing out of order execution is only one of many optimisations that restrict helps. A lot of others are very definitely relevant to the Z80. – JeremyP Nov 12 at 13:30

Not the answer you're looking for? Browse other questions tagged or ask your own question.