Re: [ANN] Clue 0.1.1

[Mike Pall <mikelu-0807@...>]

David Given wrote:
> Mike Pall wrote:
> [...]
> > But LJ2 is of course fully compatible to Lua at the source level.
> > So if you want to use it as a backend, you need to transform the
> > BB graph into Lua source with standard control flow constructs.
> > See Muchnick, chapter 7.7: "Structural Analysis".
> 
> I hadn't even considered that it was possible to do that in all cases
> --- I'll go and look into it (because it'll solve major problems with
> the other language backends such as Javascript).

The basic idea is to construct a depth-first spanning tree for the
graph and then do a postorder matching against the supported
region types. You may discover some irreducible cases that need
special handling.

> Can you suggest any other references? Muchnick's book seems to be rather
> hard to get hold of (and is apparently notoriously full of bugs, but
> that's another matter).

You can get a Chinese copy of most of these textbooks for a few
dollars (same content in English, just with a Chinese cover). And
I wouldn't say it's full of bugs, but then I rarely read the code
examples. The biggest problem is that it's rather ancient by
todays standards (e.g. it mentions SSA only in passing). AFAIK
there is no up-to-date, comprehensive textbook on modern compiler
design.

The references given for chapter 7.7 are:

[Shar80] Sharir, Micha. Structural Analysis: A New Approach to
Flow Analysis in Optimizing Compilers, Computer Languages, Vol. 5,
Nos. 3/4, 1980, pp. 141-153

[Rose77] Rosen, Barry K. High-Level Data Flow Analysis, CACM,
Vol. 20, No. 10, Oct. 1977, pp. 712-724

[Rose79] Rosen, Barry K. Data Flow Analysis for Procedural
Languages, JACM, Vol. 26, No. 2, Apr. 1977, pp. 322-344

[SchS79] Schwartz, Jacob T. and Micha Sharir. A Design for
Optimizations of the Bitvectoring Class, Comp. Sci. Rept. No. 17,
Courant Inst. of Math. Sci., New York Univ., New York, NY, 1979

[JaiT88] Jain, Sunil and Carol Thompson. An Efficient Approach to
Data Flow Analysis in a Multiple Pass Global Optimizer, in
[PLDI88], pp. 154-163

Unfortunately most of them are behind paywalls. You may want to
check the cited-by papers to find newer treatments of the same
topic.

For a deeper understanding of the issues at hand, I also recommend
reading this (but it's only applicable to goto-free languages):

Marc M. Brandis and Hans-Peter Moessenboeck, Single-Pass
Generation of Static Single Assignment Form for Structured
Languages, ACM TOPLAS, Vol. 16, No. 6, Nov. 1994, pp 1684-1698
http://citeseer.ist.psu.edu/brandis94singlepas.html

--Mike