Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!cs.utexas.edu!think!husc6!spdcc!ima!esegue!compilers-sender
From: preston@rice.edu (Preston Briggs)
Newsgroups: comp.compilers
Subject: Graph coloring, patents
Message-ID: <1989Nov15.010209.11362@esegue.segue.boston.ma.us>
Date: 15 Nov 89 01:02:09 GMT
Sender: compilers-sender@esegue.segue.boston.ma.us
Reply-To: Preston Briggs <preston@rice.edu>
Organization: Rice University, Houston
Lines: 27
Approved: compilers@esegue.segue.boston.ma.us
In-Reply-To: <1989Nov13.203034.1778@esegue.segue.boston.ma.us>

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

-- 
Send compilers articles to compilers@esegue.segue.boston.ma.us
{spdcc | ima | lotus}!esegue.  Meta-mail to compilers-request@esegue.
Please send responses to the author of the message, not the poster.