Compilers - Finding MAC instructions

Author

Finding MAC instructions

Christian Christmann

2006-07-16, 4:00 am

Hi,

for a project I want to extend our comiler (more accurately, our
code generator) for a DSP by generating optimized code using
DSP-specific instructions like the MAC (multiply accumulte).

Our compiler framework consists of a high- and a low-level
intermediate represetation and translates C code.

Could you give me any hints how potential high-level language
candidates (in C) can be recognized (and realized in assembler
by the efficient MAC instructions).
Do I need to take information from our low-level IR into account
or does it suffice to consider code in the target-specific
(assembly-like) low-level IR?

I appreciate your help since I could not find any information
about this specific topic on the internet.

Best regards,
Christian

Amit Gupta

2006-07-18, 4:01 am

Your problem falls into two categories:
1. Expression Restructuring
2. Mapping to MAC operations.

A naive (but useful) preprocessing step would be to greedily select
obvious mac operations. This is easier done at high-level language
flow graph before it is converted to IR representation. The useful
thing is here is, you can catch the designer intent, before conversion
to IR modifies the control graph. You can probably go through some
papers on tree-height-reduction(THR) or operator strength reduction
algorithms to get an idea about it ( I am speaking from the vlsi-cad
background, where mapping to specific architecture/instruction is
widely used).

An important part of your scheme would be, how to do expression
restructuring. e.g., if you have (d = ac + cb + d), you can
restructure it to (d = (a+ b)*c + d)), where you can use the mac
operation. If you have lots of time in hand, I believe a simulated
annealing framework can do good restructuring. Otherwise, you can
devise some algorithm based on windowing which tries to change maximum
number of operations into mac instruction.

I believe, your problem falls into NP or higher class, and therefore it
is difficult to get an exact algorithm for this problem.

-Amit

Christian Christmann wrote:
> Hi,
>
> for a project I want to extend our comiler (more accurately, our
> code generator) for a DSP by generating optimized code using
> DSP-specific instructions like the MAC (multiply accumulte).

Jeff Kenton

2006-07-22, 10:01 pm

Christian Christmann wrote:
> for a project I want to extend our comiler (more accurately, our
> code generator) for a DSP by generating optimized code using
> DSP-specific instructions like the MAC (multiply accumulte).

Sounds like something that could be done in the peephole optimization
stage, possibly preceded by re-organization of operations (as a
previous poster suggested).

jeff

Henry Spencer

2006-07-23, 7:01 pm

Amit Gupta <emailamit@gmail.com> wrote:
>A naive (but useful) preprocessing step would be to greedily select
>obvious mac operations. This is easier done at high-level language
>flow graph before it is converted to IR representation. The useful
>thing is here is, you can catch the designer intent...

A general observation: programmers strongly prefer *predictability* in
such things, especially in floating-point representations, where
overly- enthusiastic expression restructuring can totally ruin code
that was carefully designed to have good rounding properties.

A float MAC, which usually does only one rounding rather than two, is
very much a two-edged sword: it can be a very useful tool, but it can
also make devastating messes. For example, multiplying a complex
number by its conjugate mathematically gives a real -- the imaginary
part is exactly zero -- and that is also true of IEEE floating-point
arithmetic... provided FMAC is *NOT* used in ways that mess up the
symmetry of the expressions. Yes, doing fewer roundings can worsen
rounding errors!

(This is an example of a general floating-point principle:
intermediate results are often correlated with each other in subtle
ways that are important to good results. Optimizations which can
disrupt such correlations are dangerous, even if, in isolation, it
might seem that they should improve the error properties of the code.)

If the compiler is going to try hard to find places where a MAC can be
used, there must be a way to tell it "hands off" for carefully-crafted
code, *without* disabling other important optimizations.

Similarly, there should be a way to tell the compiler that it *must*
use a MAC in this particular expression, and it should warn you if
it's unable to do so. People who want to do this are likely to care
very much about speed, and so they can't just call a library function
(unless the compiler is *required* to inline it).
--
spsystems.net is temporarily off the air; | Henry Spencer
mail to henry at zoo.utoronto.ca instead. | henry@spsystems.net

Sponsored Links