ROSE Compiler Framework/Declaration move tool

Overview

This tool will move variable declarations to their innermost possible used scopes.

For a declaration, find the innermost scope we can move it into, without breaking the code's original semantics.

For a single use place, move to the innermost scope.
For the case of multiple uses, we may need to duplicate the declarations and move to two scopes if there is no variable reuse in between, otherwise, we move the declaration into the innermost common scope of the multiple uses.

Installation

This tool is released as part of the ROSE compiler. Please install ROSE (version 0.9.9.123 or later) by following the instructions at

Installation: During configuration, you might want to specify a prefix path, such as –prefix=/home/youraccount/opt/rose-0.9.9.123. Then, follow the ROSE installation guide to build and install ROSE.

To save time, you can just build/install librose and the tool you are interested in. Note in your build tree:

type "make install-core -j8" # this build librose.so and some core tools

Alternatively, you can install everything, which takes much longer time:

type make install -j8 to install core ROSE libraries and some prebuilt tools.

An executable file moveDeclarationToInnermostScope will be created during the process of building/installing ROSE. The tool will be installed to the path specified by –prefix=ROSE INSTALLATION PATH. Users can use it to process their codes.

The next step is to set environment variables for search paths for ROSE executables (including this move tool ) and shared libraries. Assume you are using bash, put the following lines into a file (e.g. set.rose) and source it (typing source set.rose)

ROSE_INS=/home/youraccount/opt/rose--0.9.9.123
export ROSE_INS
PATH=$ROSE_INS/bin:$PATH
export PATH
LD_LIBRARY_PATH=$ROSE_INS/lib:$LD_LIBRARY_PATH
export LD_LIBRARY_PATH

Now you can use this tool to transform your code. Assume you have a sequential file: file.c, just type moveDeclarationToInnermostScope -c file.c. An output file rose file.c will be generated.

To process multiple files, you need to change your makefile to use moveDeclarationToInnermostScope as the compiler to compile your code. The tool will transform your code first and generate rose_originalFile.C and invoke a backend compiler (usually GCC/G++) to finish the compilation.

User instructions

The translator accepts the following options:

-rose:merge_decl_assign will merge the moved declaration with an immediately followed assignment.
-rose:aggressive : turn on the aggressive mode, which will move declarations with initializers, and across loop boundaries. A warning message will be sent out if the move crosses a loop boundary. Without this option, the tool only moves a declaration without an initializer to be safe.
-rose:debug, which is turned on by default in the testing. Some dot graph files will be generated for scope trees of variables for debugging purpose.
-rose:keep_going will ignore assertions as much as possible (currently on skip the assertion on complex for loop initialization statement list). Without this option, the tool will stop on assertion failures.
-rose:identity will turn off any transformations and act like an identity translator. Useful for debugging purposes.
-rose:trans-tracking will turn on the transformation tracking mode, showing the source statements of a move/merged declaration

Essential output of moveDeclarationToInnermostScope --help

MOVEDECLARATIONTOINNERMOSTSCOPE(1) ROSE Command-line Tools MOVEDECLARATIONTOINNERMOSTSCOPE(1)

Name
moveDeclarationToInnermostScope - This tool moves variable declarations to their innermost possible scopes

Synopsis
moveDeclarationToInnermostScope switches files...

Description
This tool is designed to help parallelizing code by moving variable declarations into their innermost possible scopes (essentially
making many of them private). As a result, less variables need to be shared.

...

The move tool switches
These switches control the move tool.

--[rose:]aggressive
Enable aggressive mode: declarations with initializers will be moved.

--[rose:]debug
Enable the debugging mode.

--[rose:]identity
Enable acting like an identity translator, not doing any transformation at all.

--[rose:]keep_going
Allow the tool to proceed without being stopped by assertions.

--[rose:]merge_decl_assign
After the move, further merge the moved naked variable declaration (without initialization) with a followed variable assignment.

--[rose:]trans-tracking
Enable tracking of transformation steps.

ROSE's built-in switches
--rose:help
Show the old-style ROSE help.

0.9.9.123 Thursday October 12 13:51:28 2017 MOVEDECLARATIONTOINNERMOSTSCOPE(1)

source and tests

Source code

https://github.com/rose-compiler/rose-develop/blob/master/tools/moveDeclarationToInnermostScope.C

Testing:

type "make move_diff_check" within buildtree/tests/nonsmoke/functional/moveDeclarationTool, defined in
https://github.com/rose-compiler/rose-develop/blob/master/tests/nonsmoke/functional/moveDeclarationTool/Makefile.am
test input files are located under https://github.com/rose-compiler/rose-develop/tree/master/tests/nonsmoke/functional/moveDeclarationTool
- 28 files with diff-based correctness checking
- 202 files for token-based unparsing

Example Use

For the following input code, Test.cc

void AccumulateForce(int *idxBound, int *idxList, int len,
                    double *tmp, double *force)
{
   register int ii ;
   register int jj ;
   int count ;
   int *list ;
   int idx ;
   double sum ;
   for (ii=0; ii<len; ++ii) {
      count = idxBound[ii+1] - idxBound[ii] ;
      list = &idxList[idxBound[ii]] ;
      sum = 0.0 ;
      for (jj=0; jj<count; ++jj) {
         idx = list[jj] ;
         sum += tmp[idx] ;
      }
      force[ii] += sum ;
   }
   return ;
}

You can run the move tool as follows to produce the rose_Test.cc output file below:

moveDeclarationToInnermostScope -rose:unparse_tokens -rose:merge_decl_assign -c Test.cc

There are several things to notice about this command line. The moveDeclarationToInnermostScope tool acts as a front-end to an underlying compiler, and the command line options for that compiler will be honored. Here, we also have some ROSE/tool specific command line options. The '-rose:unparse_tokens' option tells ROSE to take extra care to preserve the source-code formatting from the input source file when producing the rose_xxx.cc output file. The '-rose:merge_decl_assign' option is specific to the rescoping tool, and indicates that any moved declarations should try to be combined with pre-existing assignment statements in the target scope.

The output file will look like

void AccumulateForce(int *idxBound, int *idxList, int len,
                    double *tmp, double *force)
{
   for (register int ii = 0; ii<len; ++ii) {
      int count = idxBound[ii + 1] - idxBound[ii];
      int *list = &idxList[idxBound[ii]];
      double sum = 0.0;
      for (register int jj = 0; jj<count; ++jj) {
         int idx = list[jj];
         sum += tmp[idx] ;
      }
      force[ii] += sum ;
   }
   return ;
}

Looking at the transformed source code above, there are several points of interest:

Any qualifiers associated with declarations are preserved when the declaration is moved.
Declarations related to for-loop control variables are moved into the loop header.
Assignments and declarations are merged, due to the presence of the -rose:merge_decl_assign command line option.

Internal Algorithms

Fundamentals

Build a scope tree for each declaration

nodes: DS (declaration scope), IS (intermediate scope), and US (used scope)
edges: parent-child relation between two scopes

Cases for tree shape properties

single straight line tree
- single bottom used scope: move the declaration to the bottom
- multiple used scopes: trim shadowed used scopes, move the declaration to the first used scope
multiple branches for the tree
- has LiveIn between branching sibling nodes: move declaration to the parent scope of the sibling.
- No liveIn between sibling nodes: move declaration to each branching scope
  - unequal depths of target scopes: tentatively move to the equal depth, iteratively move the inserted declarations. worklist algorithm

Relevant source code

Scope_Node* generateScopeTree(SgDeclarationStatement* decl, bool debug = false)

V1: Worklist algorithm

initial worklist = original declarations in the function
while (!worklist.empty())
- decl = worklist.front(); worklist.pop();
- moveDeclarationToInnermostScope(decl, inserted_decls);
- worklist.push_back( each of inserted_decls)

V2: Separated analysis and move

V2: focusing on finding target scopes, since multiple (iterative) declaration moves are unnecessary

if we know the final scopes to be moved into, we can copy-move a declaration to all target scopes in one shot

Algorithm v2:

Analysis: findFinalTargetScopes (declaration, &target_scopes)
- scope_tree_worklist.push(scope_tree);
- while (!scope_tree_worklist.empty())
  - current_scope_tree = scope_tree_worklist.front(); …
  - collectCandidateTargetScopes(decl, current_scope_tree);
    - if (found a bottom scope) target_scopes.push_back(candidate)
    - else scope_tree_worklist.push_back(candiate)
Transformation:
- if (target_scopes.size()>0)
  - copyMoveVariableDeclaration(decl, target_scopes);

call stack

main()

exampleTraversal.traverseWithinFile (s_file, preorder); // move declarations
- visitorTraversal::visit()
if (merge_decl_assign) collectiveMergeDeclarationAndAssignment (inserted_decls); // move declaration with assignments

Limitations and ongoing work

List

Currently a conservative syntactic liveness analysis is used, we are moving it to use a better liveness analysis
the tool only moves local variables declared within a function, not global variables.
- Moving global variables requires global analysis across multiple source files to avoid breaking original semantics.
- Also, often global variables are declared in header files. Transforming header files is still on-going work.