# ROSE Compiler Framework/outliner
## Overview

Basic concept: outlining is the process of replacing a block of consecutive statements with a function call to a new function containing those statements. Conceptually, outlining the inverse of inlining.
Use: Outlining is widely used to generate kernel functions to be executed on CPU and/or GPU.
* help implementing programming models such as OpenMP
* support empirical tuning of a code portion by first generating a function out of the code portion.
ROSE provide a builtin translator called AST outliner, which can outline a specified portion of code and generate a function from it.
Official documentation for the AST outliner is located in Chapter 37 Using the AST Outliner with the ROSE Tutorial. pdf.
There are two basic ways to use the outliner.
* Command line method: You can use a command (outline )with options to specify outlining targets, there are two ways to specify which portion of code to outline
** use a special pragma to mark outline targets in the input program, and then call a high-level driver routine to process these pragmas.
** using abstract handle strings (detailed in Chapter 46 of ROSE tutorial) as command line options
* Function call method: call “low-level” outlining routines that operate directly on AST nodes you want to outline

## Installation

Please follow instructions at https://github.com/rose-compiler/rose/wiki/How-to-Set-Up-ROSE
If you are installing from source code, please check https://github.com/rose-compiler/rose/wiki/Install-Rose-From-Source
To install the tool only, type
* make install -C tests/nonsmoke/functional/roseTests/astOutliningTests
The outliner tool will be installed as
* ROSE_INST/bin/outline

## Command line

The tool rose/bin/outline relies on 1) pragmas in input codes or 2) abstract handles specified as command line options to find the target code portion to be outlined.
* The pragma: put #pragam rose_outline right in front of the code portion you want to outline in your input code
* abstract handle: -rose:outline:abstract_handle your_handle_string

### Options

./outline --help | more

### Example use

* outline test.cpp // outline code portions in test.cpp. These code portions are marked by the special rose_outline pragma
* outline -rose:skipfinalCompileStep -rose:outline:new_file test.cpp // skip compiling the generated rose_? file, put the generated function into a new file
Using abstract handles at command lines, no need to insert pragmas into your input codes anymore
* outline -rose:outline:abstract_handle ”ForStatement<position,12>” test3.cpp // outline the for loop located at line 12 of test3.cpp
* outline -rose:outline:abstract_handle ”FunctionDeclaration<name,initialize>::ForStatement<numbering,2>” test2.cpp // outline the 2nd for loop within a function named "initialize" within the test2.cpp file.
/home/liao6/workspace/masterDevClean/buildtree/tests/roseTests/astOutliningTests/outline -rose:outline:new_file -rose:outline:temp_variable -rose:outline:exclude_headers -rose:outline:abstract_handle 'ForStatement<numbering,1>' -c /home/liao6/workspace/masterDevClean/sourcetree/tests/roseTests/astOutliningTests/complexStruct.c

## Programming API

You can build your own translators leveraging the outlining support in ROSE. The programming API is defined in
* Header file: src/midend/programTransformation/astOutlining/
* Namespace: Outliner
A few functions and options are provided:
* Functions: Outliner::outline, Outliner::isOutlineable
* Options

### Internal control variables

Outliner.cc

## Algorithm
### Top-level driver

The outliner uses three methods to find which code portions to outline
* collectPragms for C/C++
* collectFortranTarget for Fortran ,
* collectAbstractHandles using abstract handles
the outline program's top level driver: PragmaInterface.cc
* Outliner::outlineAll (SgProject* project)
** collectPragms for C/C++ or collectFortranTarget for Fortran , or collectAbstractHandles using abstract handles
* outline(SgPragmaDeclaration)
*** outline(SgStatement, func_name)
**** preprocess(s)
**** outlineBlock (s_post, func_name) // Transform.cc The key function here!!
** deleteAST(SgPragmaDeclaration)

### Eligibility Check

Check if a SgNode is eligible for outlining.
* Outliner::isOutlineable src/Check.cc:251
** checkType // only specified SgNode types can be outlined, a list is maintained here
** excluding SgVariableDeclaration
** must enclosed inside a function declaration
*** excluding template instantiation (member) function declaration
** does not refer hidden types ...

### Preprocessing

There are two phases: preprocessing and actual transformation.
* SgBasicBlock* s_post = preprocess (s);
** SgStatement * processPragma (SgPragmaDeclaration* decl) // check if it's an outline pragma (#pragma rose_outline), return the next stmt if so.
** Outliner::preprocess(SgStatement);
*** SgBasicBlock * Outliner::Preprocess::preprocessOutlineTarget (SgStatement* s)
**** normalizeVarDecl
**** createBlock
**** Outliner::Preprocess::transformPreprocIfs
**** Outliner::Preprocess::transformThisExprs
**** Outliner::Preprocess::transformNonLocalControlFlow
**** Outliner::Preprocess::gatherNonLocalDecls; // duplicate function declarations here, e.g. test2005_179.C

### Actual Transformation

Outliner::outline(stmt) --> generateFuncName(s) unique function name Outliner::outline (stmt, func_name)
* Outliner::Transform::outlineBlock (s_post, func_name); // Transform.cc
** Outliner::Transform::collectVars (s, syms); // collect variables to be passed
** Outliner::generateFunction //generate an outlined function, src/midend/programTransformation/astOutlining/GenerateFunc.cc
*** createFuncSkeleton
*** moveStatementsBetweenBlocks (s, func_body); // move statements in the source BB into the function body
*** variableHandling (syms, func, vsym_remap); // append unwrapping statements
**** createParam // create parameters
**** createUnpackDecl // create unpacking statement: int local = parameter, from src/midend/programTransformation/astOutlining/GenerateFunc.cc
**** createPackStmt // transfer local back to the parameter after all local calculation
*** remapVarSyms (vsym_remap, func_body); // variable substitution
** insert from Insert.cc // insert outlined function and its prototype
*** insertFriendDecls
*** insertGlobalPrototype
**** GlobalProtoInserter::insertManually
***** generatePrototype
** generateCall // generate a call to the outlined function
** ASTtools::replaceStatement // replace the original portion with the call
Call stack
For C++ code blocks to be outlined, we have to check access to private members and add necessary friend function declarations
call chain for creation: all inside Insert.cc
* Outliner::insert (SgFunctionDeclaration* func, SgGlobal* scope, SgBasicBlock* target_outlined_code )
** insertFriendDecls (SgFunctionDeclaration* func, SgGlobal* scope, FuncDeclList_t& friends) // what is func here??
*** insertFriendDecl (const SgFunctionDeclaration* func, SgGlobal* scope, SgClassDefinition* cls_def)
**** generateFriendPrototype (const SgFunctionDeclaration* full_decl, SgScopeStatement* scope, SgScopeStatement* class_scope) Insert.cc
The algorithm of insertFriendDecls (SgFunctionDeclaration* func, SgGlobal* scope, FuncDeclList_t& friends)
for the outlined function
* look for references to class private variables, using isProtPrivMember (func)
* look for references to class private member functions, using isProtPrivMember (f_ref)
* save the relevant class definitions into a list
If the outlned function will be created in a new source file. The outliner will copy dependent declarations into the new source file also. The relevant function used is SageInterface::appendStatementWithDependentDeclaration(func,glob_scope,func_orig,exclude_headers);
The code using function is at line 636 of the source file: https://github.com/rose-compiler/rose/blob/weekly/src/midend/programTransformation/astOutlining/Transform.cc

### Variable handling

The variable handling process finds variables used within a code block, and decides how to pass a variable into and outside of an outlined function. It relies on several program analyses to achieve best results.
* scope analysis (in CollectVars.cc): deciding what variables should be passed as function parameter, using visibility of a variable's declaration with respect to the location of the outlined function. If the original declaration is visible to the outlined function, there is no need to pass it as a function parameter.
* collectPointerDereferencingVar: finding variables which should be using pointer deferencing in outlined function(in VarSym.cc): ASTtools::collectPointerDereferencingVarSyms(s,pdSyms);
* side-effect analysis : SageInterface::collectReadOnlyVariables(s,readOnlyVars);
* liveness analysis : SageInterface::getLiveVariables(liv, isSgForStatement(firstStmt), liveIns, liveOuts);
Scope analysis: notations of variable sets and set operations to obtain which variables should be passed as function parameters, implemented in
* U : the set of variables used within the code block (s) to be outined
* L: local variable declared within s
* U-L : variables which should be passed as function parameters into/out of the outlined function
* Q: variables defined within the function enclosing s that are visible at s, but not globally declared beyond the enclosing function. Global variables should not be passed as parameters if the outlined function is put within the same file.
* (U-L) Intersect Q: the variables to be passed into the outlined function
ASTtools::collectPointerDereferencingVarSyms: Collect variables to be replaced by pointer dereferencing (pdSym) in the outlined function
* pdSyms = useByAddressVars + Non-assignableVars + Struct/ClassVars
* use-by-address analysis: collectVarRefsUsingAddress(s, varSetB); e.g. &a
* un-assignable variable analysis: collectVarRefsOfTypeWithoutAssignmentSupport(s,varSetB); variables with types which are not assignable
* class/struct variables: passing by reference is more efficient for them
calculateVariableRestorationSet: decide if some variables need to be restored from their clones in the end of the outlined function, only used when the variable cloning feature is turned on
* check each function parameter
* the parameter should be restored if isWritten && isLiveOut : changed within the outlined function and will be used after the outlined function.
Transform.cc

## Advanced features

Some details for outlining can be specified by using command line options or internal flags of the programming API.
List
* wrap all variables into a data structure: Outliner::useStructureWrapper

### Variable cloning

Option to turn this feature on
* -rose:outline:temp_variable use temp variables to reduce pointer dereferencing for the variables to be passed
The purpose of this feature is to reduce the pointer dereferencing in a code block so the code block can be more easily be optimized later. The transformaiton will use a local variable to obtain the value, then use the local variable to participate in the computation. After that, the local variable's value is transferred back to the pointer value.
Example
local variable's type:
Transform.cc : collect variables

### dlopen

use_dlopen option tells the outliner to use the dlopen to find and call the outlined function stored into a dynamically loadable library.
This option will turn on several other options (inside Outliner.cc Outliner::validateSettings)
* -rose:outline:exclude_headers
* useNewFile= true;
* useParameterWrapper = true;
* temp_variable = true;
compilation and linking instructions: assume the input file is ft.c
* outline -rose:outline:use_dlopen -I/home/liao6/workspace/outliner/build/../sourcetree/projects/autoTuning -c /path/to/ft.c
** this step will generate two files:
** rose_ft.c : the original ft.c file is transformed into this file
** rose_ft_lib.c (outlined function in a shared lib file)
* build the .so file from rose_ft_lib.c
** gcc -I. -g -fPIC -c rose_ft_lib.c
** gcc -g -shared rose_ft_lib.o -o rose_ft_lib.so
** cp rose_ft_lib.so /tmp/.
* link everything together
** the object files should be linked with libautoTuning.a, built from projects/autoTuning/autotuning_lib.c, which in turn defines findFunctionUsingDlopen.
** gcc -o a.out rose_ft.o /roseInstallPath/lib/libautoTuning.a -Wl,--export-dynamic -g -ldl -lm
A full example using dlopen can be found at
* https://github.com/chunhualiao/outliner-demo

## Testing

The ROSE AST outliner has a dedicated testing directory: rose/tests/nonsmoke/functional/roseTests/astOutliningTests
* Some C, C++ and Fortran test input files are prepared there.
* Sample command line options are available in the Makefile.am file within this test directory.
full command line example
* /home/liao6/workspace/rose/buildtree/tests/nonsmoke/functional/roseTests/astOutliningTests/outline -rose:outline:use_dlopen -rose:outline:temp_variable -I/home/liao6/workspace/rose/buildtree/../sourcetree/projects/autoTuning -rose:outline:exclude_headers -rose:outline:output_path . -c /home/liao6/workspace/rose/sourcetree/tests/nonsmoke/functional/roseTests/astOutliningTests/array1.c
To trigger single test , assuming the input file is named inputFile.c:
* make classic_inputFile.c.passed //classic behavior
* make dlopen_inputFile.c.passed // dlopen feature
As you can see, the prefix indicate different options of using the outliner.

## Example input and output
### As a standalone tool

Input file, with a pragma to indicate which code portion to be outlined:

### char* type

Input:
outline --edg:no_warnings -rose:verbose 0 -rose:outline:parameter_wrapper -rose:detect_dangling_pointers 1 -c input.cpp
Output file:

### work with C++ member functions

Input code:
Output code
* add friend declaration for the outlined function so it can access private class members
* pass this pointer to a class object as a function argument
Using -rose:outline:parameter_wrapper , the result will be slightly different:
* all parameters will be wrapped into an array of pointers in the caller function
* the array will be unpacked to retrieve the parameters in the outlined function

### Used for OpenMP Implementation

See more at ROSE_Compiler_Framework/OpenMP_Support.
Below is an example translation:

### Used to Generate CUDA kernels for OpenMP 4.x

Example input and output code for the classic Jacobi OpenMP 4.0 version:
See details at ROSE_Compiler_Framework/OpenMP_Acclerator_Model_Implementation

## Known issues

List
* the message "error in side effect analysis!" when setting Outliner::useStructureWrapper to true. This also happens in the outlineIfs example from the tutorial directory.
** you can ignore this warning message if your translator still works. The outliner uses quite some analyses internally if Outliner::useStructureWrapper is turned on. But some of the analyses may not always handle all situations so they just give up and notify the outliner. The outliner is designed to make conservative decisions in this case and to generate less optimal translated code.

## Publications

A paper describing the internals of the AST outliner, the default paper to cite if you happen to use the AST outliner for your research work
* Chunhua Liao, Daniel J. Quinlan, Richard Vuduc, and Thomas Panas. 2009. Effective source-to-source outlining to support whole program empirical optimization. In Proceedings of the 22nd international conference on Languages and Compilers for Parallel Computing (LCPC'09)
To support generating multi-threaded kernels for CPUs and GPUs
* Chunhua Liao , Daniel J. Quinlan , Thomas Panas , Bronis R. de Supinski, A ROSE-Based OpenMP 3.0 research compiler supporting multiple runtime libraries, Proceedings of the 6th international conference on Beyond Loop Level Parallelism in OpenMP: accelerators, Tasking and more, June 14-16, 2010, Tsukuba, Japan
* C. Liao, Y. Yan, B. R. de Supinski, D. J. Quinlan, and B. Chapman, “Early experiences with the openmp accelerator model,” in Openmp in the era of low power devices and accelerators, Springer, 2013, pp. 84-98.
Being used to support empirical tuning or autotuning
* Shirley Moore, Refactoring and automated performance tuning of computational chemistry application codes, Proceedings of the Winter Simulation Conference, December 09-12, 2012, Berlin, Germany
* Nicholas Chaimov , Scott Biersdorff , Allen D Malony, Tools for machine-learning-based empirical autotuning and specialization, International Journal of High Performance Computing Applications, v.27 n.4, p.403-411, November 2013