|IR Transformations firstname.lastname@example.org (1993-04-15)|
|Re: IR Transformations donawa@bluebeard.CS.McGill.CA (1993-04-21)|
|From:||donawa@bluebeard.CS.McGill.CA (Chris DONAWA)|
|Organization:||SOCS, McGill University, Montreal, Canada|
|Date:||Wed, 21 Apr 1993 14:35:53 GMT|
: 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:
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.
Return to the
Search the comp.compilers archives again.