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

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;

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