Graph coloring, patents

In article <1989Nov13.203034.1778@esegue.segue.boston.ma.us> I wrote:


>Do any of the IBM PC-class C compilers do global optimizations?
>Global constant propagation? Graph coloring register allocation?


>[The Metaware compilers are reputed to do graph coloring, though it's a
>trick to make it work on something as asymmetrical as a 286. Also, I wonder
>if one can do useful graph coloring without infringing IBM's patents. -John]


For graph coloring, you could get a license from IBM, though I'm not sure
about the fees (I recall they are based on a percentage of something, but
that's a rumor). An alternative approach would be to use Chow's priority-
based scheme (unless it's been patented also); it's drastically different than
Chaitin's version.


I don't know which is more effective. I suspect (with no evidence) that
Chow's method will be better on constrained machines (not many registers) and
Chaitin's better otherwise. Neither seems worthwhile without some global
optimization to provide grist for the mill.


Preston Briggs
preston@titan.rice.edu

Return to the comp.compilers page.
Search the comp.compilers archives again.