Re: IR Transformations

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

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