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 jimy@cae.wisc.edu (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

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.