Review form for CSEM-reviews 2003
=================================

Paper #4, "Addressing Mode Selection" by Erik Eckstein and Berbhard Scholz.

Reviewer: Andrzej Bednarski

Short summary
-------------

The paper presents a method for optimizing memory accesses (using address
registers). The goal of Address Mode Selection (AMS) is to select (optimal)
offsets on entries and exits nodes of the CFG (that involve address registers)
and gain by using cheaper addressing mode instructions, such as for example
post increment instead of memory access followed by an constant addition to
the address register. The authors model the target architecture addressing
modes as cost functions. Then, the cost optimization problem is modeled as 
partitioned boolean quadratic problem. The solution for PBQP, obtained from a
solver, provides optimal (optimized) solution for AMS.

The main contributions
----------------------

The authors solve a difficult problem of address mode selection. The issue is
known to be NP hard, and a little work in that direction has been done. The
papers provide a method for solving AMS optimally for most of the (real
application) codes.

The authors are aware of high complexity of their approach, and thus provide a
heuristic approach for problems that cannot be solved optimally.


Merits and weaknesses
---------------------

Merits:
+ The authors showed that the algorithm produces much better code if compared
  to the baseline code, with acceptable overhead. Further, the algorithm has a
  fall back to heuristic (ReductionN) that copes with more complex and real
  applications.
+ The method is applicable for local and global optimization.
+ Minor overhead for the compiler
+ The algorithm is applicable for single and multi-issue DSPs.

Weaknesses:
- Large code quality improvement suggests weak code for the base line. The
  authors should provide where most of the gains occurred.

Numerical rating
----------------

* Significance: 9
* Originality: 7
* Interest to a journal on programming languages and compiler technology: 10
* Quality of experimental evaluation: 6
* Overall organization: 8
* Presentation (language and style): 8
* Length appropriate: 8
* References appropriate: 9

* Overall evaluation: 8
* Recommendation: Accept
* Your confidence in your review: 7

Comments to the authors
-----------------------

The authors claim an optimal address mode selection - this is optimal with
respect to the cost model that has to be specified by the user. I would
appreciate if the authors would have written to proof for the optimality (at
least steps, if the proof is too long). Also, the author could mention what
is difficult to automatically derive the cost matrices for various variant of
architectures.

Suggestions for improvement
---------------------------

The method seems to be applicable as stand alone in a post pass
optimizations. This will still require to run a scheduling (due to
added/removed instructions).

The figures show a significant improvement with respect to the base line code
quality. Is it because the base line compiler (without ASM) produces "poor"
code, such as in the paper example the use of two instruction (memory access,
and address register increment) instead of one (post increment memory
access).

No cases show a code size increase if optimizing for execution time. This
suggests the case of low code quality mentioned above, since the ASM will
mainly remove instructions.

Could ASM give hints on how to rearrange memory data? - this is another
optimization goal.