Re: Compiler optimization of division and remainder

Henry G. Baker <hbaker@netcom.com> wrote:
>On another newsgroup, a poster claimed that some compilers could
>optimize a program which used both a/b and a%b (both quotient and
>remainder with the _same_ arguments) in such a way that the compiler
>would perform only a single hardware division operation and arrange to
>use both the quotient and remainder from this single operation.


richard@atheist.tamu.edu (Richard Henderson) wrote:
> In GCC, platforms that support this operation include a "divmod"
> pattern in the machine description. This pattern forces both
> operations to appear in the RTL so that, during CSE, when the
> optimizer goes looking for where the value of the second operation
> might already exist, it finds the value that was created previously.
>
> The GCC texinfo documentation has a short blurb, but perusing the
> source in and around expand_divmod() in expmed.c and the divmod
> patterns in the config/*/*.md files will likely be more instructive.


Thanks to everyone who responded -- the information was quite helpful.


Here's what I think I learned:


1. The MIPS compilers appear to support this kind of an optimization in the
_assembler_!


2. An ARM C compiler apparently does this in the compiler.


3. GCC compilers are capable of doing this in the compiler.


4. Apparently some Fortran compilers _may_ do a similar trick by
calling the routine sincos if both sin(x) and cos(x) are called with
the same arguments.


5. Common subexpression _will_ work if it's done late enough in the
game, so that the compiler can recognize that the division is
performed twice. However, this is pretty late in the game, and many
compiler's CSE's will have already finished by the time this stuff is
generated. But I guess with RISC machines there are other similar
things where a very late CSE will help, so this isn't so bad.


However, running the CSE too late may not help the sincos example,
although the ARM apparently generates a call to a library division
subroutine (at least in the case mentioned by a person who replied to
my posting), so perhaps their compiler would be able to handle the
sincos example.


So maybe you need at least _two_ CSE phases -- one fairly early in the
game and one fairly late in the game -- or perhaps this is one of
those optimizations that want to be run _before AND after_ everything,
so you need to keep running optimizations 'until convergence' --
assuming that optimizations don't undo one another.


---


I still haven't received (or found myself) any published _papers_ which
would describe/advocate this sort of thing.


--
www/ftp directory:
ftp://ftp.netcom.com/pub/hb/hbaker/home.html
--

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