Graph coloring, patents

Preston Briggs <>
Tue, 14 Nov 89 11:09:39 CST

          From comp.compilers

Related articles
Graph coloring, patents (Preston Briggs) (1989-11-14)
Re: Graph coloring, patents rfg@ics.UCI.EDU (Ron Guilmette) (1989-11-15)
Re: Graph coloring, patents (1989-11-24)
| List of all articles for this month |

Date: Tue, 14 Nov 89 11:09:39 CST
From: Preston Briggs <>
Newsgroups: comp.compilers
In-Reply-To: <>
Organization: Rice University, Houston

In article <> 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

Post a followup to this message

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