Re: IR Transformations

donawa@bluebeard.CS.McGill.CA (Chris DONAWA)
Wed, 21 Apr 1993 14:35:53 GMT

          From comp.compilers

Related articles
IR Transformations (1993-04-15)
Re: IR Transformations donawa@bluebeard.CS.McGill.CA (1993-04-21)
| List of all articles for this month |

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 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:

      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.

Post a followup to this message

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