[Haskell-cafe] some algorithm help with jhc

[Bjorn Lisper]

John Meacham
>I have started working on jhc more recently and have come across some
>places where I think my algorithms could be improved but was not sure
>exactly where to start so thought I would ask the list since perhaps
>someone here has some insight.
>
>After a long time of trying various methods of speeding up the fixpoint
>iteration of my points-to analysis (the current main bottleneck) I
>decided to step back and look at the basic problem again. It turns out I
>can express the problem as one of constraint satisfaction resulting in
>much smaller code (600 lines vs 2000) and 10fold speedups with my
>unoptimized first draft solver.
>
>It is much faster but still not as fast as I'd like. I don't know a lot
>about constraint problems, but my intuiton says this particular problem
>is of a type that should be particularly easy to solve but am uncertain
>where to start in my searching to find a fast algorithm. My constraints
>come in two types of rules.

....

Hi, check out the book Principles of Program Analysis by Nielson, Nielson,
Hankin (http://www2.imm.dtu.dk/~riis/PPA/ppa.html). It has quite some on
constraint solving for program analysis. There are algorithms in that book
for set constraint problems that look quite similar to your problem.

Björn Lisper