Wed, 21 Apr 1993 14:35:53 GMT

Related articles |
---|

IR Transformations jimy@cae.wisc.edu (1993-04-15) |

Re: IR Transformations donawa@bluebeard.CS.McGill.CA (1993-04-21) |

Newsgroups: | comp.compilers |

From: | donawa@bluebeard.CS.McGill.CA (Chris DONAWA) |

Keywords: | code |

Organization: | SOCS, McGill University, Montreal, Canada |

References: | 93-04-058 |

Date: | Wed, 21 Apr 1993 14:35:53 GMT |

jimy@cae.wisc.edu wrote:

*: Could anyone give me pointers to papers on the subject of IR*

*: transformations to suit code generation?*

*: More specificaly, suppose we want to generate code for x = 2 * a; The*

*: problem is how to know, at the IR level (before code is generated), that*

*: the above expression can be rewritten as x = a + a (assuming + is cheaper*

*: than *). The problem is that the above transformation may be context*

*: dependent and not always desirable. In other words, sometimes 2*a may be*

*: covered cheaper than a+a, e.g. by a shift left, which some processors*

For the lower level intermediate representation in our C compiler (the

McCAT C compiler), we use Bernstein's algorithm for integer

multiplications with constants. The work is described in:

@Article{Bernstein86,

Author = "Robert Bernstein",

Title = "Multiplication by Integer Constants",

Journal = "Software--Practice and Experience",

Volume = 16,

Number = 7,

Pages = "641-652",

Month = "July",

Year = 1986

*}*

Essentially any integer multiplied by and integer constant can be replaced

by a series of shift/add/subtraction combinations. The algorithm tries to

find the best combination that does not exceed a cost (specified by you,

ususally the cost of an integer multiply).

There are some slight typos in the implementation. Preston Briggs posted

a corrected version of the algorithm, which formed the basis of our

converter. If you'd like I can mail it to interested folks, or make it

available for ftp.

--

Christopher M. Donawa

Advanced Compilers, Architectures and Parallel Systems Group (ACAPS)

McGill University, Montreal PQ.

donawa@cs.mcgill.ca

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.