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.