Multiplication by constants

Hi folks,


I recently picked up Preston Briggs and Tim Harvey's excellent
paper "Multiplication by Integer Constants"
(ftp://cs.rice.edu/public/preston/optimizer/multiply.ps.gz).
I was interested to compare their more formal approach with
the very simple heuristic I've been using in the GPM code
generators with some success.


Preston's algorithm searches for the cheapest solution using
the binary and factoring methods. As he points out neither
finds optimal solutions for every case and neither dominates
the other. It turns out this is also the case for my heuristic.


It's basically the binary method with a simple factorization.
If the top 3 bits (i, i-1, i-2) of the absolute value of the
multiplier are set then 2^(i+1) is subtracted.
For example, for a multiplier of 939:


  Original algorithm With my heuristic
  ------------------ -----------------
      4 = 1 << 2 16 = 1 << 4
      5 = 4 + 1 17 = 16 + 1
    40 = 5 << 3 68 = 17 << 2
    39 = 40 - 1 85 = 68 + 17
  312 = 39 << 3 1024 = 1 << 10
  313 = 312 + 1 939 = 1024 - 85
1252 = 313 << 2
  939 = 1252 - 313




Looking at all multipliers in 1 .. 2^20 range, my heuristic
improves the total instruction count by 1.5% and only adds 4.7%
to the total number of recursions.


Their algorithm includes a neat memoizing feature so that once an
optimal factorization is found it never has to be calculated again
(for that run). Extending the persistence leads to the (probably
not terribly novel) approach of precalculating all factors (well up
to some limit anyway), using brute force to find optimal sequences.


Has anyone experience with this?


---
Jeffrey Ledermann lederman@dstc.qut.edu.au
                                                        http://www.dstc.qut.edu.au/~lederman/


Faculty of Information Technology
Queensland University of Technology
Box 2434 Brisbane 4001 AUSTRALIA
Ph: +61 7 3864 5337 Fax: +61 7 3864 1282
--

Return to the comp.compilers page.
Search the comp.compilers archives again.