add an FAQ file
[packages/hoopl.git] / private / icfp09.reviews
1 Dear Prof. Norman Ramsey:
2
3 Final versions of the reviews for your submission
4
5       Dataflow Optimization Made Simple
6
7 are at the bottom of this mail. I hope you will find them
8 useful.
9
10 Please note that in some cases these reviews have been
11 updated since the author response period.  Also, additional
12 reviews may have been received after the response period 
13 ended; if this was the case, the committee took note of the
14 fact that you did not have the opportunity to respond to
15 them.
16
17 Again, if you have any additional questions, please feel free 
18 to contact me.
19
20
21 Sincerely,
22 Andrew Tolmach 
23 PC Chair
24
25 ============================================================================ 
26 ICFP 2009 Reviews for Submission #8
27 ============================================================================ 
28
29 Title: Dataflow Optimization Made Simple
30
31 Authors: Norman Ramsey, Joao Dias and Simon Peyton Jones
32 ============================================================================
33                             REVIEWER #1
34 ============================================================================ 
35
36
37 ---------------------------------------------------------------------------
38 Comments
39 ---------------------------------------------------------------------------
40
41 The authors present "a Haskell library that makes it easy for compiler writers
42 to implement program transformations based on dataflow analyses".
43
44 Although the main goal of the paper is interesting, I think that the authors'
45 proposal is not so general as claimed in the abstract (and 
46 expected for a general Haskell library). 
47
48 >From a theoretical point of view, it does not introduce anything really new
49 (the theoretical basis comes from a POPL'02 paper by Lerner, Grove, and
50 Chambers). 
51
52 >From a practical point of view, I find the following drawbacks:
53
54 1.- Although a general purpose library is claimed to be given, 
55 the development focuses on some few (already known) program analyses 
56 and optimizations which are defined and described for C--, 
57 a particular compiler-target intermediate language  
58 which (as far as I know) is not widely used.
59 Actually, at the end of the abstract it is said that
60 this library is the "workhorse of a new backend for GHC".
61
62 2.- Many types, functions and data structures are not defined in the paper.
63 For instance, the types VarSet or Middle (together with some data constructors
64 like MidAssign, CmmLocal, CmmLoad, etc., and defined functions like aTx, noTx, 
65 etc.) in Figures 3 to 7 seem to be part of the types which are used 
66 in the current implementation of GHC (this is explicit for Middle as one can 
67 read in the but last paragraph of the second column in page 5) or in a full
68 description of the library which is not available anywhere (at least I found
69 no link to any additional information about them). This makes the code in 
70 Figures 3 to 7 more difficult to read and understand and, again, more difficult
71
72 to generalize to compilers of other programming languages different from C—
73
74 3.- It is unclear to me how the optimization of the target code is achieved
75 by using the proposed functions. The focus is on the dataflow graph but 
76 nothing is said about how this graph is obtained from the unoptimized code
77 and how an optimized target code is obtained from the transformed/rewritten
78 graph.
79
80 Overall, the paper is very well-written. I also find interesting the 
81 ideas dropped in the Conclusions, and have no doubt that FP can export 
82 many ideas and techniques  for optimizing compilers of more 'traditional'
83 programming languages.        However, I failed to see how the proposed 
84 library helps to achieve this since, in my opinion, it
85 seems to be conceived just to serve the GHC compiler.
86
87 ============================================================================
88                             REVIEWER #2
89 ============================================================================ 
90
91
92 ---------------------------------------------------------------------------
93 Comments
94 ---------------------------------------------------------------------------
95
96 This paper presents a Haskell library for implementing a general
97 dataflow analysis and optimization through examples and describes 
98 its  implementation. 
99
100 The introductory part of sections 1 - 6 contains a nice introduction
101 to dataflow optimization, and convincing argument on ease of
102 developing variety of dataflow optimizers using the presented
103 library. However, the presented library appears to be a
104 straightforward porting of Ramsey and Dias's dataflow infrastructure
105 based on applicative representation of control flow graph based on
106 Huet's Zipper.        Data representation and the structures of the
107 optimization engine appears to be quite similar, and it is unclear
108 what the new technical contributions are. In addition, the description
109 of the dataflow engine in Section 7 of is not very clear due to lack
110 of proper explanation. For example, readers would have some difficulty
111 in  understanding the importance and relevance of the data types such
112 as "Block", "ZTail" and "Zhead" unless they were already familiar with
113 the underlying Zipper style representation of control flow graph with
114 the corresponding definitions (ie, "block", "head" and "tail") given
115 in Ramsey and Dias's original article. 
116
117 I understand that sometimes republishing a workshop paper in ICFP 
118 would be appropriate especially when the workshop is limit visibility,
119 but this may not be the case. The audience of ML workshop
120 significantly overlap with those of ICFP and that the proceeding of ML
121 2005 has been published in Elsevier's Electronic Notes in Theoretical
122 Computer Science, which is widely available and archival publication. 
123
124 As such, I doubt that this paper contains enough original contribution
125 appropriate for publication in ICFP 2009.
126
127 ============================================================================
128                             REVIEWER #3
129 ============================================================================ 
130
131
132 ---------------------------------------------------------------------------
133 Comments
134 ---------------------------------------------------------------------------
135
136 This paper describes the design and Haskell implementation of a generic library
137 for dataflow analysis and code transformations. Examples of classic dataflow
138 analyses expressed using the library are shown and appear remarkably compact.  
139
140 A distinguishing feature of this library is that it supports combined analysis
141 and transformation, whereas the result of the analysis anticipates the effect
142 of the code transformation.  This follows the approach proposed by Lerner et al
143 in 2002.  It is pointed out that this enables combining several
144 analysis/transformation passes in one, but no example is given.  The only
145 example given where analyze&transform gives better results than
146 analyze-then-transform is dead code elimination by liveness analysis, but as
147 noted in footnote 1 it was already known how to achieve the same result using a
148 standard analyze-only dataflow solver.
149
150 80% of the paper describe the library and its use.  The remaining 20% read more
151 like a lecture on dataflow analysis, presented as inference of (certain classes
152 of) logical assertions.  I wasn't completely convinced by this presentation,
153 which I found less penetrating than D. Schmidt's famous "Data flow analysis is
154 model checking of abstract interpretations".  More generally, it is surprising
155 that abstract interpretation is mentioned nowhere in this paper.
156
157 All in all, this is a well-written paper describing a very solid piece of
158 compiler engineering, but I didn't see a breakthrough.
159
160 Minor comments:
161
162 The example in section 4 is a bit mysterious.  Once the set of variables live
163 across a function call has been computed (by a standard liveness analysis), it
164 is a simple syntactic transformation to insert a spill after each definition
165 (of one of those variables) and a reload before each use; no further dataflow
166 analyses are needed.  Yes, this can give less precise results than the proposed
167 approach if there are multiple definitions of a variable, some live across a
168 call and some not (can this happen in GHC's intermediate code?).  But, still,
169 the hard part about spilling and reloading is to eliminate multiple reloads in
170 areas of code where register pressure is low, e.g.
171
172      x = ...
173
174      spill(x)
175
176      ...
177
178      reload(x)
179
180      y = ... x ...
181
182      // do not reload(x) again if register pressure is low
183
184      z = ... x ...
185
186 I didn't see whether / how the proposed approach could do this.