Re: Finding MAC instructions

"Amit Gupta" <>
18 Jul 2006 01:16:44 -0400

          From comp.compilers

Related articles
Finding MAC instructions (Christian Christmann) (2006-07-16)
Re: Finding MAC instructions (Amit Gupta) (2006-07-18)
Re: Finding MAC instructions (Jeff Kenton) (2006-07-22)
Re: Finding MAC instructions (2006-07-23)
| List of all articles for this month |

From: "Amit Gupta" <>
Newsgroups: comp.compilers
Date: 18 Jul 2006 01:16:44 -0400
References: 06-07-019
Keywords: optimize
Posted-Date: 18 Jul 2006 01:16:44 EDT

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.


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

Post a followup to this message

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