# ROSE Compiler Framework/Declaration move tool

ROSE tools>

## 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)
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

## 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
You can run the move tool as follows to produce the rose_Test.cc output file below:
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
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

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.