Re: Automatic "code-pattern" recognition, in DSP codes using RAINCODE

Darius Blasband <darius@raincode.com>
11 Jul 2005 06:58:55 -0400

          From comp.compilers

Related articles
Automatic "code-pattern" recognition, in DSP codes Miguel.CasasSanchez@ucd.ie (=?ISO-8859-15?Q?Miguel_Cas=E1s-S=E1nchez?=) (2005-07-05)
Re: Automatic "code-pattern" recognition, in DSP codes using RAINCODE darius@raincode.com (Darius Blasband) (2005-07-11)
| List of all articles for this month |

From: Darius Blasband <darius@raincode.com>
Newsgroups: comp.compilers
Date: 11 Jul 2005 06:58:55 -0400
Organization: Compilers Central
References: 05-07-024
Keywords: DSP, analysis

Miguel Casás-Sánchez wrote:
>
> I was wondering if somebody has ever heard about something like
> "automatic typical DSP-like kernel recognition", for example, as the
> compiler reads the program and sets up the data and control graphs,
> recognise that
>
> for(i=0, acc = 0; i < N; i++) {
> acc = h[n] * X[N-n];
> }
>
> can be a FIR filter, that may be substituted as a whole by a fir()
> library function call, most optimised.
>


Ok, please find below a complete working solution, using RainCode
(http://www.raincode.com) based on syntactical tree matching. It is kind
of verbose, but successfully translates:




#define size 5


int main(void)
{
          int i, acc, h[size], X[size];


      for(i=0, acc = 0; i < size; i++)
            acc += h[i] * X[size-i];


}






into:






int main(void)
{
      int i, acc, h[5], X[5];
        acc= fic(h, X, 5);
}




Please note that it runs a preprocessor, so "size" is replaced by 5 in
the translated code. The script could be extended to recognize different
forms of the algorithms (parts of the tree matching patterns could be
factorized and reused for this), but it would already be usable as is,
if the two arrays and/or the array size are expressed in more complex
ways, such as:


        fix(node[i]->arr, node[indi[j]]->arr, MAX_INT - 2)






PROCEDURE TERMINATE
VAR resultvar, vect1, vect2, vectsize;
BEGIN
          FOR IN ROOT.SubNodes DO
                IF MatchScalarProduct(IN X, TO vect1, TO vect2, TO vectsize, TO
resultvar) THEN
                        PATCH.ReplaceNt(X, Im(resultvar) & "= fic("&Im(vect1)&", "
                                                                                                              &Im(vect2)&", "
                                                                                                              &Im(vectsize)&");");
                END;
          END;
          PATCH.Save(ROOT.SourceName&".patched");
END;


PROCEDURE Im(nt)
BEGIN
          RESULT := LIST.ToString(PATCH.NtImage(nt)," ");
END;


LOGIC PROCEDURE MatchScalarProduct(statement, vect1, vect2, vectsize,
resultvar)
VAR index;
BEGIN
          statement
                == NT ForStatement {
                            Param => NT ForParam {
                                                      Init => NT CommaExpression {
                                                                              First => NT AssignmentExpression {
                                                                                                                  Left => index,
                                                                                                                  Op => Equal,
                                                                                                                  Right => NT
IntegerLiteral {


Image => "0"
                                                                                                                                    }
                                                                                                          },
                                                                              Others =>{
                                                                                                          NT
AssignmentExpression {
                                                                                                                  Left => resultvar,
                                                                                                                  Op => Equal,
                                                                                                                  Right => NT
IntegerLiteral {


Image => "0"
                                                                                                                                    }
                                                                                                          }
                                                                                                }
                                                                      },
                                                      TestExpression => NT BinaryExpression {
                                                                                                  Left => index,
                                                                                                  Op => Less,
                                                                                                  Right => vectsize
                                                                                          },
                                                      IncExpression => NT UnaryExpression {
                                                                                                  Expression => index,
                                                                                                  Op => IncOp
                                                                                          }
                                              },
                              Statement => NT ExpressionStatement {
                                                            Expression => NT AssignmentExpression {
                                                                                                  Left => resultvar,
                                                                                                  Op => AddAssign,
                                                                                                  Right => NT
BinaryExpression {
                                                                                                                            Op => Star,
                                                                                                                            Left =>
NT BracketExpression {


      Arg => vect1,


      IndexExpr => index
                                                                                                                                              },
                                                                                                                            Right =>
NT BracketExpression {


      Arg => vect2,


      IndexExpr => NT BinaryExpression {


                                      Op => Minus,


                                      Left => vectsize,


                                      Right => index


                                }
                                                                                                                                              }
                                                                                                                    }
                                                                                        }
                                                        }
                      }
END;


Post a followup to this message

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