ROSE AST - Traversal
Tips:
Code snippets are shown in one of three ways throughout this environment:
- Code that looks like
this
is sample code snippets that is usually part of an explanation. - Code that appears in box like the one below can be clicked on and it will automatically be typed in to the appropriate terminal window:
vim readme.txt
- Code appearing in windows like the one below is code that you should type in yourself. Usually there will be a unique ID or other bit your need to enter which we cannot supply. Items appearing in <> are the pieces you should substitute based on the instructions.
Add your name here - <name>
Features
This is a tutorial to build your own tool traversing ROSE AST to find things of your interests.
A. Overview
An essential task in compiler development is to walk the AST
to find nodes of interests, in order to gather information and/or modify
AST in the context of building program analysis and transformation..
ROSE includes different
sorts of traversal APIs to help this task.
The goal of this tutorial is to learn how to use a visitor pattern traversal API to walk the AST and find for loops in an input program.
B. Get the source files and makefile
Get the example ROSE-based analyzer traversing AST to find loops. Rename it to be demo.C:
wget https://raw.githubusercontent.com/rose-compiler/rose/develop/tutorial/visitorTraversal.C
mv visitorTraversal.C demo.C
We can look into the example analyzer’s source code:
cat demo.C
Essentially, we can see the following content:
4 #include "rose.h"
5
6 class visitorTraversal : public AstSimpleProcessing
7 {
8 public:
9 visitorTraversal();
10 virtual void visit(SgNode* n);
11 virtual void atTraversalEnd();
12 };
13
14 visitorTraversal::visitorTraversal()
15 {
16 }
17
18 void visitorTraversal::visit(SgNode* n)
19 {
20 if (isSgForStatement(n) != NULL)
21 {
22 printf ("Found a for loop ... \n");
23 }
24 }
25
26 void visitorTraversal::atTraversalEnd()
27 {
28 printf ("Traversal ends here. \n");
29 }
30
31 int
32 main ( int argc, char* argv[] )
33 {
34 // Initialize and check compatibility. See Rose::initialize
35 ROSE_INITIALIZE;
36
37 if (SgProject::get_verbose() > 0)
38 printf ("In visitorTraversal.C: main() \n");
39
40 SgProject* project = frontend(argc,argv);
41 ROSE_ASSERT (project != NULL);
42
43 // Build the traversal object
44 visitorTraversal exampleTraversal;
45
46 // Call the traversal function (member function of AstSimpleProcessing)
47 // starting at the project node of the AST, using a preorder traversal.
48 exampleTraversal.traverseInputFiles(project,preorder);
49
50 return 0;
51 }
A ROSE-based tool initializes ROSE first (at line 35). Then the frontend() function is called to parse an iput code and generate an AST rooted at project
of SgProject type (at line 40).
After that, a traversal object is declared at line 44. The object is used to traverse the input files of the project , using a preorder traversal.
The traversal object is based on a derived visitorTraversal
class at line 6. This derived class has member functions to define what should happen during construction (line 14), visiting a node (line 18), and the end of the traversal (line 26).
Now get a sample makefile to build the source file into an executable file:
wget https://raw.githubusercontent.com/rose-compiler/rose/develop/tutorial/SampleMakefile
We can check the content of the makefile:
cat SampleMakefile
It should have the following content:
...
25 #If the ROSE bin directory is in your path, rose-config can be found automatically
26 ifndef ROSE_HOME
27 ROSE_HOME = $(shell rose-config prefix)
28 endif
29
30 include $(ROSE_HOME)/lib/rose-config.cfg
31
32 # Standard C++ compiler stuff (see rose-config --help)
33 ROSE_CXX = $(shell $(ROSE_HOME)/bin/rose-config ROSE_CXX)
34 ROSE_CPPFLAGS = $(shell $(ROSE_HOME)/bin/rose-config ROSE_CPPFLAGS)
35 ROSE_CXXFLAGS = $(shell $(ROSE_HOME)/bin/rose-config ROSE_CXXFLAGS)
36 ROSE_LDFLAGS = $(shell $(ROSE_HOME)/bin/rose-config ROSE_LDFLAGS)
37 ROSE_LIBDIRS = $(shell $(ROSE_HOME)/bin/rose-config ROSE_LIBDIRS)
38 ROSE_RPATHS = $(shell $(ROSE_HOME)/bin/rose-config ROSE_RPATHS)
39 ROSE_LINK_RPATHS = $(shell $(ROSE_HOME)/bin/rose-config ROSE_LINK_RPATHS)
40
41 MOSTLYCLEANFILES =
42
43 ##############################################################################
44 # Assuming your source code is "demo.C" to build an executable named "demo".
45
46 all: demo
47
48 demo.o: demo.C
49 $(ROSE_CXX) $(ROSE_CPPFLAGS) $(ROSE_CXXFLAGS) -o $@ -c $^
50
51 demo: demo.o
52 $(ROSE_CXX) $(ROSE_CXXFLAGS) -o $@ $^ $(ROSE_LDFLAGS) $(ROSE_LINK_RPATHS) -Wl,-rpath=$(ROSE_HOME)/lib
53
54 MOSTLYCLEANFILES += demo demo.o
55
56 ##############################################################################
57 # Standard boilerplate
58
59 .PHONY: clean
60 clean:
61 rm -f $(MOSTLYCLEANFILES)
The makefile should be self-explanatory. It uses rose-config in the installation path to set various environment variables for compilers, compilation and linking flags, library path, etc.
Get an example input code for the analyzer:
wget https://raw.githubusercontent.com/rose-compiler/rose/develop/tutorial/inputCode_ExampleTraversals.C
The input code has two for-loops at line 20 and 41:
1
2 // Templated class declaration used in template parameter example code
3 template <typename T>
4 class templateClass
5 {
6 public:
7 int x;
8 void foo(int);
9 void foo(double);
10 };
11
12 // Overloaded functions for testing overloaded function resolution
13 void foo(int);
14
15 void foo(double)
16 {
17 int x = 1;
18 int y;
19
20 for (int i=0; i < 4; i++)
21 {
22 int x;
23 }
24
25 // Added to allow non-trivial CFG
26 if (x)
27 y = 2;
28 else
29 y = 3;
30 }
31
32 int main()
33 {
34 foo(42);
35 foo(3.14159265);
36
37 templateClass<char> instantiatedClass;
38 instantiatedClass.foo(7);
39 instantiatedClass.foo(7.0);
40
41 for (int i=0; i < 4; i++)
42 {
43 int x;
44 }
45
46 return 0;
47 }
C. Build the analyzer using the makefile
Prepare the environment variable used to specify where ROSE is installed.
export ROSE_HOME=/home/freecc/install/rose_install
Build the analyzer:
make -f SampleMakefile
There should be an executable file named demo under the current directory:
ls demo
Finally, run the demo analyzer to process the example input code:
./demo -c inputCode_ExampleTraversals.C
The analyzer should find two for loops and report the end of the traveral.
Found a for loop ...
Found a for loop ...
Traversal ends here.
References
For more information about AST traversal, please check
- http://rosecompiler.org/ROSE_Tutorial/ROSE-Tutorial.pdf Chapter 7