Electronics & Programming

develissimo

Open Source electronics development and programming

  • You are not logged in.
  • Root
  • » SDCC
  • » [Sdcc-user] A better register allocator for the Z80 [RSS Feed]

#1 Jan. 10, 2011 19:41:03

Philipp K.
Registered: 2009-11-02
Reputation: +  0  -
Profile   Send e-mail  

[Sdcc-user] A better register allocator for the Z80


-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

An sdcc version that has a new register allocator can be found athttp://colecovision.eu/stuff/sdcc-optralloc-2011-1-10.tar.gzIt passes all regression tests, and the generated code is significantly
better than what current sdcc generates.

To compile it you need a C++ compiler, such as g++ and the boost
libraries (on Debian / Ubunut apt-get install libboost-dev should do).

Please test it and tell me about any bugs encountered, and the
differences in code size and speed compared to "standard" sdcc.

Philipp

P.S.: The new register allocator is currently used in the Z80 port only.
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.10 (GNU/Linux)
Comment: Using GnuPG with Mozilla -http://enigmail.mozdev.org/iEYEARECAAYFAk0rYC8ACgkQbtUV+xsoLpr5bACglCW5oUfJNwHYEobRaVdAkvlc
01wAn1ZPHH+8Ujprch6mp9kIAaHC54Ur
=+1Im
-----END PGP SIGNATURE-----


Sdcc-user mailing list
Sdcc-user@lists.sourceforge.nethttps://lists.sourceforge.net/lists/listinfo/sdcc-user

Offline

#2 Jan. 10, 2011 19:59:25

Maarten B.
Registered: 2009-11-02
Reputation: +  0  -
Profile   Send e-mail  

[Sdcc-user] A better register allocator for the Z80


Philipp,

Why not just commit this to subversion? We are nowhere
near a release so this should not hurt too much. And you
even claim it passes all current regression tests. I see
no reason to keep this separate.

Maarten

> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
> An sdcc version that has a new register allocator can be found at
>
>http://colecovision.eu/stuff/sdcc-optralloc-2011-1-10.tar.gz>
> It passes all regression tests, and the generated code is significantly
> better than what current sdcc generates.
>
> To compile it you need a C++ compiler, such as g++ and the boost
> libraries (on Debian / Ubunut apt-get install libboost-dev should do).
>
> Please test it and tell me about any bugs encountered, and the
> differences in code size and speed compared to "standard" sdcc.
>
> Philipp
>
> P.S.: The new register allocator is currently used in the Z80 port only.
> -----BEGIN PGP SIGNATURE-----
> Version: GnuPG v1.4.10 (GNU/Linux)
> Comment: Using GnuPG with Mozilla -http://enigmail.mozdev.org/>
> iEYEARECAAYFAk0rYC8ACgkQbtUV+xsoLpr5bACglCW5oUfJNwHYEobRaVdAkvlc
> 01wAn1ZPHH+8Ujprch6mp9kIAaHC54Ur
> =+1Im
> -----END PGP SIGNATURE-----
>
>
> Sdcc-user mailing list
> Sdcc-u***@*ists.sourceforge.net
>https://lists.sourceforge.net/lists/listinfo/sdcc-user>




Sdcc-user mailing list
Sdcc-user@lists.sourceforge.nethttps://lists.sourceforge.net/lists/listinfo/sdcc-user

Offline

#3 Jan. 10, 2011 20:07:49

Lin R.
Registered: 2009-11-02
Reputation: +  0  -
Profile   Send e-mail  

[Sdcc-user] A better register allocator for the Z80


I have many assemble code written in SDCC C calling method, like function
return val in hl, do those need to be changed?

Woodyhttp://palmmicro.com/woody/----- Original Message -----
From: "Philipp Klaus Krause" <p***@*pth.de>
To: "Sdcc-User" <sdcc-u***@*ists.sourceforge.net>
Sent: Tuesday, January 11, 2011 3:38 AM
Subject: A better register allocator for the Z80


> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
> An sdcc version that has a new register allocator can be found at
>
>http://colecovision.eu/stuff/sdcc-optralloc-2011-1-10.tar.gz>
> It passes all regression tests, and the generated code is significantly
> better than what current sdcc generates.
>
> To compile it you need a C++ compiler, such as g++ and the boost
> libraries (on Debian / Ubunut apt-get install libboost-dev should do).
>
> Please test it and tell me about any bugs encountered, and the
> differences in code size and speed compared to "standard" sdcc.
>
> Philipp
>
> P.S.: The new register allocator is currently used in the Z80 port only.
> -----BEGIN PGP SIGNATURE-----
> Version: GnuPG v1.4.10 (GNU/Linux)
> Comment: Using GnuPG with Mozilla -http://enigmail.mozdev.org/>
> iEYEARECAAYFAk0rYC8ACgkQbtUV+xsoLpr5bACglCW5oUfJNwHYEobRaVdAkvlc
> 01wAn1ZPHH+8Ujprch6mp9kIAaHC54Ur
> =+1Im
> -----END PGP SIGNATURE-----
>
>
> Sdcc-user mailing list
> Sdcc-u***@*ists.sourceforge.net
>https://lists.sourceforge.net/lists/listinfo/sdcc-user
Sdcc-user mailing list
Sdcc-user@lists.sourceforge.nethttps://lists.sourceforge.net/lists/listinfo/sdcc-user

Offline

#4 Jan. 10, 2011 20:16:43

Philipp K.
Registered: 2009-11-02
Reputation: +  0  -
Profile   Send e-mail  

[Sdcc-user] A better register allocator for the Z80


-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Am 10.01.2011 21:05, schrieb Lin Rongrong:
> I have many assemble code written in SDCC C calling method, like function
> return val in hl, do those need to be changed?

No. The calling convention remains unchanged.

Philipp
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.10 (GNU/Linux)
Comment: Using GnuPG with Mozilla -http://enigmail.mozdev.org/iEYEARECAAYFAk0raMsACgkQbtUV+xsoLpqwvQCgqveFViMgw10OeReSiONixKTX
m5MAn0T5uFWiONQeBDLmexWCuEea7gEr
=TyU4
-----END PGP SIGNATURE-----


Sdcc-user mailing list
Sdcc-user@lists.sourceforge.nethttps://lists.sourceforge.net/lists/listinfo/sdcc-user

Offline

#5 Jan. 10, 2011 20:57:24

Philipp K.
Registered: 2009-11-02
Reputation: +  0  -
Profile   Send e-mail  

[Sdcc-user] A better register allocator for the Z80


-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Am 10.01.2011 20:57, schrieb Maarten Brock:
> Philipp,
>
> Why not just commit this to subversion? We are nowhere
> near a release so this should not hurt too much. And you
> even claim it passes all current regression tests. I see
> no reason to keep this separate.
>
> Maarten

There are some problems:

1) It uses C++, and the boost libraries. This creates build dependencies
on a C++ compiler and boost. IMO this should be discussed on sdcc-devel
first.

2) There is lots of ugly glue between sdcc and the new register
allocator. This should be cleaned up (including fixing #3152684 and
#3150686).

3) IMO it should see some testing first since it's such a huge beast
(larger than the rest of the Z80 port combined).

4) The register allocator is still rather incomplete. E.g. it currently
uses only the 4 registers bc and de. It uses the old register allocator
as a kind of preprocessor for hl and a.

5) There still are many problems with this register allocator, which
don't result in bad code being generated, but make it worse than it
could be.

6) The underlying ideas are much more powerful than what this first
implementation provides. I've placed slides of a talk I gave at the
universities of Frankfurt and Passau athttp://colecovision.eu/stuff/Vortrag-Register-2010-11-6.pdfThis
implementation is mostly just a first prototype, and I intend to rewrite
most of it.

7) The underlying ideas are not accepted in the compiler construction
community. I submitted a paper to the Compiler Construction 2010
conference, which was rejected rather harshly: " this paper will
remain, yet another time, a purely theoretical paper with no influence
on register allocation.", " results will remain uncited or unused
", " impractical for use in a real compiler.", " the
algorithm is only of theoretical value.", etc.

8) Peephole rules probably should be changed to reflect changes in code
generated by sdcc.

Nevertheless: A full implementation will take a lot more time, and the
current one is already a huge improvement over the current register
allocator (and thus is valuable in itself). It probably should be
committed after some more clean-up.

Philipp
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.10 (GNU/Linux)
Comment: Using GnuPG with Mozilla -http://enigmail.mozdev.org/iEYEARECAAYFAk0rcjsACgkQbtUV+xsoLpoH2ACfR64OJ0JmLJl4I9m1nQgpm/5S
olEAn0q9E94g5JuErgLomE9Cxi9LIhQB
=OGst
-----END PGP SIGNATURE-----


Sdcc-user mailing list
Sdcc-user@lists.sourceforge.nethttps://lists.sourceforge.net/lists/listinfo/sdcc-user

Offline

#6 Jan. 10, 2011 23:26:14

Frieder F.
Registered: 2009-11-02
Reputation: +  0  -
Profile   Send e-mail  

[Sdcc-user] A better register allocator for the Z80


Hi Philipp,

Am 10.01.2011 21:55, schrieb Philipp Klaus Krause:
> Am 10.01.2011 20:57, schrieb Maarten Brock:
>> Philipp,
>
>> Why not just commit this to subversion? We are nowhere
>> near a release so this should not hurt too much. And you
>> even claim it passes all current regression tests. I see
>> no reason to keep this separate.
>
>> Maarten
>
> There are some problems:
>
> ...
>
> 7) The underlying ideas are not accepted in the compiler construction
> community. I submitted a paper to the Compiler Construction 2010
> conference, which was rejected rather harshly: " this paper will
> remain, yet another time, a purely theoretical paper with no influence
> on register allocation.", " results will remain uncited or unused
> ", " impractical for use in a real compiler.", " the
> algorithm is only of theoretical value.", etc.

" impractical for use in a real compiler."
would look like a problem. Is this just a statement?


Harsh wording sometimes is an indication for lack of argument.
The "yet another time" fragment might be an indication
that the reasoning has not been fair.
Tasks SDCC has to solve often have to fit into 64kByte
(with obviously the code size per function fitting
into _much_ less).
And there possibly (..) could be the fallback of:

OhHaveABreakMyNotYetPerfectNPHardRegisterAllocationCodeBurned \
MoreThan10ToThePowerOf7CPUCyclesForThisVeryFunctionIFeelBad \
AboutThatNPHardStuffWouldYouPleaseCompareMyAdmittedly \
SuboptimalResultsToTheOldFashionedRegisterAllocationCode \
AndEventuallyUseThat_UnlessTheUserWantsMeToPulverizeAnother \
10ToThePowerOf9CPUCyclesIWouldPreferToTackleTheNextFunctionNow


Greetings,
Frieder


Sdcc-user mailing list
Sdcc-user@lists.sourceforge.nethttps://lists.sourceforge.net/lists/listinfo/sdcc-user

Offline

#7 Jan. 11, 2011 22:32:05

Philipp K.
Registered: 2009-11-02
Reputation: +  0  -
Profile   Send e-mail  

[Sdcc-user] A better register allocator for the Z80


-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

An updated and improved version of sdcc with the new register allocator
can be found at:http://colecovision.eu/stuff/sdcc-optralloc-2011-1-11.tar.gzImprovements over yesterday's version:

* Coalescing support
* Cleaner interface to sdcc
* Configurable parameter --max-allocs-per-node <number>, higher numbers
mean better code, but slower compilation. Default is 8192, which seems
to give speed comparable to the old allocator.

Here's some data from a random application (which contains more data
than code, so the real improvement in the generated code is much bigger
than these numbers suggest):

Old register allocator:
32768 bytes

New register allocator, --max-allocs-per-node 8192:
32600 bytes

New register allocator, --max-allocs-per-node 16384:
32507 bytes

New register allocator, --max-allocs-per-node 65536:
32296 bytes

New register allocator, --max-allocs-per-node 262144:
32296 byte

Philipp

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.10 (GNU/Linux)
Comment: Using GnuPG with Mozilla -http://enigmail.mozdev.org/iEYEARECAAYFAk0s2dAACgkQbtUV+xsoLpraJwCfd5SNHZEIj30tpFAh+se9aWN0
iqwAoODYnaTCEsHeEE7lyRy+HqQQh2uJ
=q1b8
-----END PGP SIGNATURE-----


Sdcc-user mailing list
Sdcc-user@lists.sourceforge.nethttps://lists.sourceforge.net/lists/listinfo/sdcc-user

Offline

#8 Jan. 11, 2011 22:50:27

Philipp K.
Registered: 2009-11-02
Reputation: +  0  -
Profile   Send e-mail  

[Sdcc-user] A better register allocator for the Z80


-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Am 11.01.2011 00:24, schrieb Frieder Ferlemann:
>> 7) The underlying ideas are not accepted in the compiler construction
>> community. I submitted a paper to the Compiler Construction 2010
>> conference, which was rejected rather harshly: " this paper will
>> remain, yet another time, a purely theoretical paper with no influence
>> on register allocation.", " results will remain uncited or unused
>> ", " impractical for use in a real compiler.", " the
>> algorithm is only of theoretical value.", etc.
>
> " impractical for use in a real compiler."
> would look like a problem. Is this just a statement?

Well, I do not agree with that statement. There now is a working
prototype implementation in sdcc's Z80 backend that can generate much
better code than the old register allocator.
However I have to admit that my approach probably would not be a good
one for architectures that have many registers, since runtime is
exponential in the number of registers (when aiming for optimal code,
i.e. setting --max-allocs-per-node to INT_MAX).

IMO my approach is a good one for sdcc: When developing for embedded
system aiming for compact or even optimal code is much more important
than on bigger systems, where memory is plenty. And sdcc's targets
typically do not have many register.

Philipp
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.10 (GNU/Linux)
Comment: Using GnuPG with Mozilla -http://enigmail.mozdev.org/iEYEARECAAYFAk0s3ksACgkQbtUV+xsoLppiTACgw0XUPh7eYQaitMFzgAitYkEx
aKwAoIW/AA+SPRfiRPO0oYbTOsmjCZDE
=CcHi
-----END PGP SIGNATURE-----


Sdcc-user mailing list
Sdcc-user@lists.sourceforge.nethttps://lists.sourceforge.net/lists/listinfo/sdcc-user

Offline

#9 Jan. 11, 2011 22:58:43

Frieder F.
Registered: 2009-11-02
Reputation: +  0  -
Profile   Send e-mail  

[Sdcc-user] A better register allocator for the Z80


Hi Philipp,

Am 11.01.2011 23:29, schrieb Philipp Klaus Krause:
> Here's some data from a random application (which contains more data
> than code, so the real improvement in the generated code is much bigger
> than these numbers suggest):
>
> Old register allocator:
> 32768 bytes
>
> New register allocator, --max-allocs-per-node 8192:
> 32600 bytes
>
> New register allocator, --max-allocs-per-node 16384:
> 32507 bytes

Could you compare to the regression test suite?
Not typical either, but a) has larger coverage and b) is known?

Would look like:
Summary for 'ucz80': 0 failures, 5880 tests, 847 test cases, 2208772 bytes,
5844603 ticks

(as f.e. available fromhttp://sdcc.sourceforge.net/snap.php(the hopefully
green icons to the right))

Greetings,
Frieder


Sdcc-user mailing list
Sdcc-user@lists.sourceforge.nethttps://lists.sourceforge.net/lists/listinfo/sdcc-user

Offline

#10 Jan. 11, 2011 23:34:18

Philipp K.
Registered: 2009-11-02
Reputation: +  0  -
Profile   Send e-mail  

[Sdcc-user] A better register allocator for the Z80


-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Am 11.01.2011 23:56, schrieb Frieder Ferlemann:

> Could you compare to the regression test suite?
> Not typical either, but a) has larger coverage and b) is known?

On my system:
Old register allocator:
Summary for 'ucz80': 0 failures, 5880 tests, 847 test cases, 2208784
bytes, 5844603 ticks

New register allocator, --max-allocs-per-node 8192:
Summary for 'ucz80': 0 failures, 5911 tests, 851 test cases, 2058904
bytes, 6121208 ticks

Any idea why the number of tests differs (the new register allocator
really is the only change)?

I will make another comparison later using the benchamrk athttp://sourceforge.net/apps/trac/sdcc/wiki/Philipp%27s%20TODO%20listwhich I have used for this purpose in the past.

Philipp
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.10 (GNU/Linux)
Comment: Using GnuPG with Mozilla -http://enigmail.mozdev.org/iEYEARECAAYFAk0s6HkACgkQbtUV+xsoLppNsACfRSRbvBav3rBBy1miZtvrj6/G
h74AoIfBu3pLu+EhOMqS/XZmgFc/HII1
=ZfiK
-----END PGP SIGNATURE-----


Sdcc-user mailing list
Sdcc-user@lists.sourceforge.nethttps://lists.sourceforge.net/lists/listinfo/sdcc-user

Offline

  • Root
  • » SDCC
  • » [Sdcc-user] A better register allocator for the Z80 [RSS Feed]

Board footer

Moderator control

Enjoy the 18th of August
PoweredBy

The Forums are managed by develissimo stuff members, if you find any issues or misplaced content please help us to fix it. Thank you! Tell us via Contact Options
Leave a Message
Welcome to Develissimo Live Support