ROSE Compiler Framework/How to create a translator

Translator basically converts one AST to another version of AST. The translation process may add, delete, or modify the information stored in AST.

Overview

A ROSE-based translator usually has the following steps

1. Search for the AST nodes you want to translate.
2. Perform the translation action on the found AST nodes. This action can be one of two major variants

• Updating the existing AST nodes
• Creating new AST nodes to replace the original ones. This is usually cleaner approach than patching up existing AST and is better supported by SageBuilder and SageInterface functions.
• Deep copying existing AST subtrees to duplicate the code. May expression subtrees should not be shared. So deep copy them is required to get the correct AST.
• Optionally update other related information for the translation.

First Step

Get familiar with the ASTs before and after your translation. So you know for sure what your code will deal with and what AST you code will generate.

The best way is to prepare simplest sample codes and carefully examine the whole dot graphs of them.

More details for visualize AST are available at How to visualize AST.

Design considerations

It is usually a good idea to

• separate the searching step from the translation step so one search (traversal) can be reused by all sorts of translations.
• When design the order of searching and translation, be careful about if the translation will negatively impact on the searching
  • Please void pre-order traversal since you may end up modifying AST nodes to be visited later on, similar to the effect of iterator invalidation.
  • please use post-order, or reverse order of pre-order for your traversal hooked up with translation

Searching for the AST node

There are multiple ways to find things you want to translate in AST.

AST Query

• Via AST Query: Node query returns a list of AST nodes in the same type. This is often enough to simple translations

Rose_STL_Container<SgNode*> ProgramHeaderStatementList = NodeQuery::querySubTree (project,V_SgProgramHeaderStatement);
for (Rose_STL_Container<SgNode*>::iterator i = ProgramHeaderStatementList.begin(); i != ProgramHeaderStatementList.end(); i++)
{
    SgProgramHeaderStatement* ProgramHeaderStatement = isSgProgramHeaderStatement(*i);
    ...
}

More information about AST Query can be found at "6 Query Library" of the ROSE User Manual pdf.

AST Traversal

• Through AST traversal: walks through whole AST using different orders (pre-order or post order). Post-order traversal is recommended to avoid modifying things the traversal will hit later on (similar problem as iterator invalidation in C++)
  • The AST traversal gives visit() functions to hook up your translation functions. A switch statement is can be used for handling different types of AST node.

class f2cTraversal : public AstSimpleProcessing
{
  public:
    virtual void visit(SgNode* n);
};

void f2cTraversal::visit(SgNode* n)
{
  switch(n->variantT())
  {
    case V_SgSourceFile:
      {
        SgFile* fileNode = isSgFile(n);
        translateFileName(fileNode);
      }
      break;
    case V_SgProgramHeaderStatement:
      {
        ...
      }
      break;
    default:
      break;
  }
}

More information about AST Traversal can be found at "7 AST Traversal" of the ROSE User manual pdf online.

Performing Translation

Before you write your translator, please read Chapter 32 AST Construction of ROSE tutorial pdf documentation (http://rosecompiler.org/ROSE_Tutorial/ROSE-Tutorial.pdf). It contains essential information for any translation writers.

The translations you want to do often depend on the types of the AST nodes you visit. For example you can have a set of translation functions defined in your namespace

• void translateForLoop(SgForLoop* n)
• void translateFileName(SgFile* n)
• void translateReturnStatement(SgReturnStmt* n), and so on

Other tips

• Reference ROSE doxygen website for information of each AST node: http://rosecompiler.org/ROSE_HTML_Reference/index.html
• Use SageBuilder namespace (http://rosecompiler.org/ROSE_HTML_Reference/namespaceSageBuilder.html) if you want to create new AST node. Update SageBuilder you cannot find the one you need.
• Look up in SageInterface Namespace (http://rosecompiler.org/ROSE_HTML_Reference/namespaceSageInterface.html) for the translation functions you need. If there is none, then write your own function.
• Besides building things from scratch, you can use SageInterface::deepCopy() to copy AST subtree.
• Update the information, or create the new AST node you need.
• Replace the existing AST node with your updated or new AST node.

Updating Tree

• You might need to handle some details, like removing symbol, updating parent, and symbol table.
• Be careful to use deepDelete() and deepCopy(). Some information might not be updated properly. For example, deepDelete might not update your symbol table.

Verify the correctness

You can use wholeAST graph to verify your translation.

All ROSE-based translators should call AstTests::runAllTests(project) after all the transformation is done to make sure the translated AST is correct.

This has a higher standard than just correctly unparsed to compilable code. It is common for an AST to go through unparsing correctly but fail on the sanity check.

More information is at Sanity_check

Sample translators

Here we list a few sample translators which can grow to more sophisticated ones you want.

Find pragmas

/*
toy code
by Liao, 12/14/2007
*/
#include "rose.h"
#include <iostream>
using namespace std;

class visitorTraversal : public AstSimpleProcessing
{
  protected:
    virtual void visit(SgNode* n);
};

void visitorTraversal::visit(SgNode* node)
{
  if (node->variantT() == V_SgPragmaDeclaration) {
      cout << "pragma!" << endl;
  }
}

int main(int argc, char * argv[])
{
  SgProject *project = frontend (argc, argv);
  visitorTraversal myvisitor;
  myvisitor.traverseInputFiles(project,preorder);

  return backend(project);
}

Here is an example project doing pragma parsing and saving the results into AST attributes.

https://github.com/rose-compiler/rose-develop/tree/master/projects/pragmaParsing

Loop transformation

SageInterface namespace (http://rosecompiler.org/ROSE_HTML_Reference/namespaceSageInterface.html) has many translation functions, such as those for loops.

For example, there is a loop tiling function defined in https://github.com/rose-compiler/rose/blob/master/src/frontend/SageIII/sageInterface/sageInterface.C :

//     Tile the n-level (starting from 1) loop of a perfectly nested loop nest using tiling size s.
bool     loopTiling (SgForStatement *loopNest, size_t targetLevel, size_t tileSize)

An example Test translator is provided to test this function:

• https://github.com/rose-compiler/rose/blob/master/tests/roseTests/astInterfaceTests/loopTiling.C

And it has a test input file:

• https://github.com/rose-compiler/rose/blob/master/tests/roseTests/astInterfaceTests/inputloopTiling.C

How to build your translator

See How to set up the makefile for a translator