For the following function
void printchar( unsigned char c );
void printnibble( unsigned char x ) {
x = x & 0xf;
if ( x > 10 )
x += 'a' - 10;
else
x += '0';
printchar( x );
}
Compiled using:
; SDCC TD- 4.4.1 #14768 (MINGW64)
sdcc -mz80 --reserve-regs-iy --opt-code-size --fverbose-asm --max-allocs-per-node2000000 --peep-return -c
Produces the verbose output which follows here, but before, to point to the problem, the shorter version:
; Function printnibble
; ---------------------------------
_printnibble::
and a, #0x0f
ld c, a
cp a, #0x0b
jr C, 00102$
ld a, c
add a, #0x57
ld c, a
jr 00103$
00102$:
ld a, c
add a, #0x30
ld c, a
00103$:
ld a, c
jp _printchar
Here it's clear that the register C is unnecessarily used throughout in spite of "cp" being non destructive and the possibility to keep the results in A all the time, as the previous values are not supposed to "live" (except through the comparison).
; ---------------------------------
; Function printnibble
; ---------------------------------
; Register assignment is optimal.
; Stack space usage: 0 bytes.
_printnibble::
; genReceive
; genMove_o size 1
;check-expired.c:117: x = x & 0xf;
; genAnd
and a, #0x0f
; genMove_o size 1
;check-expired.c:119: x += 'a' - 10;
; genCast
; genMove_o size 1
ld c, a
; genMove_o size 0
;check-expired.c:118: if ( x > 10 )
; genCmpGt
; common peephole 6c removed dead cp a, #0x0a
cp a, #0x0b
; common peephole 163 changed absolute to relative conditional jump.
jr C, 00102$
; skipping generated iCode
;check-expired.c:119: x += 'a' - 10;
; genPlus
ld a, c
add a, #0x57
ld c, a
; genGoto
; common peephole 162 changed absolute to relative unconditional jump.
jr 00103$
; genLabel
00102$:
;check-expired.c:121: x += '0';
; genPlus
ld a, c
add a, #0x30
ld c, a
; genLabel
00103$:
;check-expired.c:122: printchar( x );
; genSend
; genMove_o size 1
ld a, c
; genMove_o size 0
; genCall
; genLabel
; common peephole 158 removed unused label 00104$.
;check-expired.c:123: }
; genEndFunction
jp _printchar
; common peephole 152 removed unused ret.
Ticket moved from /p/sdcc/bugs/3724/
Can't be converted:
Suboptimal code generation is not a bug. It can be a feature request though to fix it.
Many thanks, I apologize for not understanding that until now.
This one is then, I think, also not a bug:
https://sourceforge.net/p/sdcc/bugs/3723/
Yes. It is moved to the feature request tracker now.
A different example of an unnecessary load:
A result, in short:
The
ld a, h
remains in spite of the fact that A is clearly not used, as thecalcx
needs only HL.The verbose output:
I am not familiar enough with the possibilities of peep hole defs, but I've tried also to add it to see if I understand it enough to remove it tat way:
where
peep-my.def
contains only:but I don't see that it was used. And I have believed that the removal of loads to the unused registers is anyways something that already exists?
Peephole optimizer rule 1 should have eliminated that:
I guess we get a false negative on notUsed here, possibly notUsed accuracy suffers due to the jp fromt tail-call optimization; when I find time I might look into it to see if that is really the issue and if it is easy to improve notUsed accuracy here. Another question is why codegen originally used c and a here, instead of going directly with h.
P.S.: I'm a bit busy right now, I hope to find time to look into z80 stuff in the second half of next week.
Last edit: Maarten Brock 2024-04-06
I hope I haven't made everything more confusing, I thought that these two are different symptoms with possible different causes, one in the top post, involving
c
, and a different one with that "notUsed" ofa
, but I also thought maybe they both fit "unnecessary use of (an) additional register" title and can be checked at the same time.I don't make these posts with any expectations for some prompt reactions, the generated code for my C is anyway very, very useful, and, most importantly, gives the correct end results. Many thanks for your work! I just thought that if I report some of my observations, maybe it will eventually help as some pointers where some improvements are possible, and that only if that's so, and whenever that happens.
isUsed( 'a' )
definitely doesn't behave as I'd expect:Starting with the following code:
The begin of the generated function is:
Now if I add what I believe is wrong peep rule:
It will be
But using what I think is a correct rule (with
notUsed('a')
)I get then (showing first the short asm of the whole function):
Note that the value to be used later is kept in C, not in A, and that A is not supposed to be considered alive after that function call with no arguments, but which returns a byte.
Which also means that the point when
notUsed('a')
becomes wrong can't be a tail call optimization, as this call here is a "simple" one.Tangentially, I can contribute these peephole rules to make these
set
andres
,(hl)
cases for all possible bits, if the peep rules are the right point at all to implement such transformations in SDCC generally, and (I assume) if the "notUsed('a')" can be relied upon.Last edit: Janko Stamenović 2024-04-07
If you want to debug issues in notUsed() for a z80-related port, enable the D macro for debugging output in line 35 of src/z80/peep.c.
Now with
Version 4.4.1 #14808 (Linux)
I can addnotUsed('a')
in the rule which matches what it should be substituted and make the rule happen!So this whole branch of this topic about the use of A register starting with the post with
unsigned calcIncH( unsigned x )
and including the posts about the use ofnotUsed('a')
in the rules is...solved in #14808
🥳
Another example of unnecessary use, here of the stack locations (
Version 4.4.1 #14792 (MINGW64)
)(Like always, I know that even better implementations possible in assembly, but here it's only about what could be reasonably expected from SDCC, and I hope that an unnecessary use illustrated here is avoidable) (Edit: the function is just an experiment to see what SDCC generates, otherwise not used by me, and this report is just to preserve an information where the improvements are maybe possible):
produces (full verbose output follows afterwards):
note unnecessary
ld -3 (ix), a
ld -2 (ix), #0x00
ld a, -3 (ix)
inside of the 00101$: loop, which are also never used afterwards:Last edit: Janko Stamenović 2024-04-13
One more, maybe only a bit more obvious, example of unnecessary use of the stack to use the value which is already in A, Additionally, here the assignments of A introduced into the loop could be seen, which are better to happen outside of it:
Note
ld a, #0x01
andxor a, a
which aren't executed only on the loop exit but even if the loop continues:The kinds of functions I'm playing are library-like. For this one the compiler has nicely managed to not de-reference the src1 and src2 pointers more than once, so IMO it's a pity that the end result is as it is, as it seems that there is potential for more. Like before, I'm just trying to provide some samples of what could maybe be improved and I think this kind of issues is now reasonably covered here, and there's no need for more similar.
First the short listing (note
ld -1 (ix), a
andld a, -1 (ix)
(unnecessary) andld a, #0x01
andxor a, a
(making the loop longer)) then follows verbose:Verbose:
Just to report that, in spite of my hopes that #14808 maybe solved this one too, the code:
compiled using
Version 4.4.1 #14808 (Linux)
still produces the use of the register C "for no reason".:The verbose output follows where I understand now that the register allocator decided that C is needed to do that addition of value #'a'-10 (see
;ic:25:
) which was then generated asld a, c add a, #0x57
. I'll try to understand more for myself in the next few days, now that I've learned something related to the fixes for #14808.Last edit: Janko Stamenović 2024-04-18
iTemp0 is in a, conflicts with iTemp 13, so iTemp 13 can't be in a.
In this case, we'd get better code if iTemp0 was just replaced by iTemp13 in the comparison, but that isn't true in general: imagine a situation where iTemp13 should be spilt for whatever reason (e.g. function calls in the branches of the if). Then being able to use iTemp0, and thus the value still in a in the comparison results in better code.
Maybe it would be possible to tell the register allocator that iTemp0 and iTemp13 are actually the same, and can thus both reside in the same register?
I think now we come to these subjects which I touched speaking about what's live where and when? The way I would understand all this: in each line where in the source "x" gets a new value (as a lval) there indeed must be a new iTemp imagined, but the same assignment to lval makes the previous iTemp "dead"?
How I'd understand it:
For the register allocator used by most ports, including z80: use --dump-graphs, the file named
*.dumpralloccfg*
is a control-flow graph at the time of register allocation annotated with live-ranges.Each node is labeled like: "x, y: a, b, …". The first number is just a numbering of the nodes, the second one is the number of the corresponding iCode (e.g. what you see in --i-code-in-asm output as "ic:23" would have a node label. "x, 23: a, b, …". The numbers after the colon are the variable bytes alive there (the numbers correspond to the numbers of the nodes in the conflict graph).
I'm trying to think at the level before the actual generation: If I write the C code like this, it is obvious that x is not used when both if branches come back together:
but I still get for that input:
And to improve the naming of the "temporary" variables, for this input the C register still preserves the value of x1 as soon as that one is created:
An actual output, with my comments added to it:
There's clearly both analysis of what can be reused and the reuse of the same register for different variables (compared to the names in the starting source), but still creating some unnecessary use?
Last edit: Janko Stamenović 2024-04-19
Yes, sdcc should have used a for y here. Now, in [r14810], it does.
Related
Commit: [r14810]
Thanks! I learn so much, especially as I will be able to learn from the changes.
Now with #14810 the C register is still used to preserve x1 which is in A already:
the output, with my comments added:
Last edit: Janko Stamenović 2024-04-19
So now with #14810 the C register is used for
iTemp13
, but why isiTemp13
there at all?The i-Code seen in the verbose output for
introduces iTemp13 to keep the copy of the iTemp1 which has the value of x1, but I don't understand why:
Here iTemp1 (which is == x1) (I'll keep them not marked as code intentionally so that they could wrap):
;ic:4: iTemp1 [k4 lr4:6 so:0]{ ia0 a2p0 re1 rm0 nos0 ru0 dp0}{unsigned-char fixed}[a ] = iTemp0 [k2 lr3:4 so:0]{ ia0 a2p0 re1 rm0 nos0 ru0 dp0}{unsigned-char fixed}{ sir@ _printnibble_x_10000_2}[a ] & 0xf {unsigned-char literal}
Here iTemp13
;ic:25: iTemp13 [k20 lr5:11 so:0]{ ia0 a2p0 re0 rm0 nos0 ru0 dp0}{signed-char fixed}[c ] = (signed-char register)iTemp1 [k4 lr4:6 so:0]{ ia0 a2p0 re1 rm0 nos0 ru0 dp0}{unsigned-char fixed}[a ]
Then this iTemp13 is used in both if branches to do the add-constant. And both branches then assign to the same iTemp6.
;ic:12: iTemp6 [k10 lr8:13 so:0]{ ia0 a2p0 re1 rm0 nos0 ru0 dp0}{unsigned-char fixed}[a ] = iTemp13 [k20 lr5:11 so:0]{ ia0 a2p0 re0 rm0 nos0 ru0 dp0}{signed-char fixed}[c ] + 0x57 {signed-char literal}
;ic:17: iTemp6 [k10 lr8:13 so:0]{ ia0 a2p0 re1 rm0 nos0 ru0 dp0}{unsigned-char fixed}[a ] = iTemp13 [k20 lr5:11 so:0]{ ia0 a2p0 re0 rm0 nos0 ru0 dp0}{signed-char fixed}[c ] + 0x30 {signed-char literal}
And the ralloccon graph does say that iTemp13 can't be the same register as iTemp1 (edge between nodes 1 and 2, where 1 is iTemo1, and 2 is iTemp13)
But: WHY? Why should
iTemp13
exist at all? I can't understand where it comes from.I understand that given that input register allocator decides that it has to use C for
iTemp13
, and that it can't use A.But what and why introduced that
iTemp13
, which is, by the way{signed-char fixed}
and used to add{signed-char literal}
in both branches of theif
, maybe that is a clue?Last edit: Janko Stamenović 2024-04-19
And the answer was indeed "the signs": if I rewrite the input to
Then I do get
So, finally, starting from the initial example and with #14810 adding one cast is needed to remove the C register use:
removing that cast will introduce the use of register C
(deleted #14808 dump as now there's #14810)
Last edit: Janko Stamenović 2024-04-19