Mon, 28 Aug 1995 01:40:33 GMT

Related articles |
---|

Multiplication by constants lederman@dstc.qut.edu.au (Jeff Ledermann) (1995-08-28) |

Re: Multiplication by constants preston@tera.com (1995-09-05) |

Re: Multiplication by constants chase@centerline.com (1995-09-12) |

Newsgroups: | comp.compilers |

From: | Jeff Ledermann <lederman@dstc.qut.edu.au> |

Keywords: | arithmetic |

Organization: | Compilers Central |

Date: | Mon, 28 Aug 1995 01:40:33 GMT |

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

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.