It would be silly to implement the original Chaitin colouring
allocator in gcc today. It is by now thoroughly outdated. While the
gcc allocator is not brilliant, it is certainly better than a straight
implementation of the original Chaitin allocator.
Chaitin's contribution is not what appears in that patent, but that it
gives a nice abstract description of the register allocation problem
as it was conceived in the late 70's. However, it completely omits
issues which are now understood to be significant for performance of
generated code on modern load/store architectures. Even ignoring this,
the algorithm presented in the patent can be significantly improved
with some simple changes (which are themselves the subject of a patent
by Rice University).
If someone was seeking to completely reimplement the gcc/egcs register
allocator, they should look at register allocation papers published
more recently; of course, they should bear patent encumberment in mind
as they do so.
This just goes to show that 17 years is too long for a software patent
in an active research field. By the time it expires, its value is
purely historical, thus the patent system has achieved nothing.
Dave Wragg
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.rutgers.edu
Please read the FAQ at http://www.tux.org/lkml/