******************************************************************************
Paper: Tree Dependence Analysis (Submission #107)
Authors: Yusheng Weijiang, Shruthi Balakrishna, Jianqiao Liu and Milind Kulkarni
Contact authors: yweijian@purdue.edu, milind@purdue.edu
******************************************************************************

This README details how to set up and run the analysis framework presented in Tree Dependence Analysis. Note that the evaluation in the paper (i) demonstrates the ability of our automatic analysis to prove that transformations are legal for tree programs, and (ii) shows that we can achieve substantial performance improvements by transforming those programs. Point (i) constitutes the major technical contribution of the paper. The transformations we evaluate were presented in prior work, and hence we do not present them as part of our artifact evaluation submission (though we do include some transformed versions of the benchmarks, if there is interest). This document focuses on using the analysis framework to verify transformation correctness.

Included is the VirtualBox image for a box that has our analysis running on it. The base image was obtained from a third party website to speed up the process of setting up the VM by not having to actually do a clean install of Ubuntu. The username and password to everything in the VM should both be ‘adminuser’. The following readme is also included inside the machine:

Documents contains two TreeSplicer directories and a z3 directory. TreeSplicer-run-benchmarks/apps/ contains the 5 benchmarks used in the paper in both untransformed and point blocked versions. These are not important for the analysis but we believed they would be useful to include, to see the effects of performing point-blocking. TreeSplicer-transform-analysis should be used to run the actual dependence analysis.

This analysis was built on the framework of TreeSplicer as described in the paper. TreeSplicer itself will try to produce various transformed versions of the code. However, this work only modified the analysis portion of TreeSplicer to add tree dependence analysis to verify the legality of these transformations; we removed the transformation portion of the framework (the original framework, without tree dependence analysis, is available at https://engineering.purdue.edu/plcl/treesplicer/)

In order to run the analysis, you can go into the TreeSplicer-transform-analysis folder and run the following command:

ant clean-app -Dapp=APPNAME ; ant transform-app -Dapp=APPNAME

TreeSplicer will not do anything if any output file already exists, so it must be cleaned first. The names of the apps are: barneshut, bst, linkedlist, kdtree, skewheap, inctree, badlist. The first five benchmarks are the same as those used in the paper. Tree dependence analysis will successfully verify the soundness of point blocking for these five benchmarks, using the conditional analysis (Section 6 of the submitted paper).

In addition to the five benchmarks from the paper, we included inctree and badlist to demonstrate other aspects of tree dependence analysis.

1) inctree is a modified version of bst that fills out a bst in the same way as the original benchmark, but the actual recursive call that is analyzed simply traverses the tree, incrementing each node as it is visited. It is included to show that for a tree traversal that only reads and writes to nodes it is currently visiting, then the benchmark will pass the first stage of the benchmark and no potential problematic collisions between accesses will actually be found. In other words, tree dependence analysis does not need to use the conditional analysis. The path-insensitive analysis from Section 5 of the submitted paper suffices.

2) badlist is a benchmark that is a modified version of linkedlist, where if a child of the current node being traversed exists, the value of the child is added to the value of the current node. This will clearly produce different results depending on whether multiple traversals happen fully one after the other or if the code is transformed in a way that each traversal visits the root, then each traversal visits the second node, then each traversal visits the third, etc. This is included to show that the dependence analysis will correctly determine when the benchmark is not safe to transform.

Some notes on the analysis:

-All the code for the dependence analysis happens in /src/transform/RecursiveStructureAnalysis.java

-The function that performs the recursive traversal in the benchmarks is named traversal_transform, and our analysis specifically looks at functions named this. TreeSplicer originally detected recursive calls automatically, but it was changed so that we could always ensure it looked at a specific function no matter what we did in the function.

-In the lists of collisions produced by the analysis, one of the accesses will always be marked with an asterisk. The marked function is the field that is higher in the tree. This means that when the marked access is performed, a node higher in the tree should have already performed the unmarked access by reading/writing down into one of its children.

-As it is currently configured, the data being passed to z3 is put into the apps folder. To save disk space, this is set to use the filename 'conditionset0.smt2' for every call to z3, and that file is overwritten once for every z3 invocation. To actually see every z3 file produced, comment out the line that says 'String filename = "conditionset0.smt2";' and uncomment out the line next to it that actually sets a filename based on which set of conditions is being analyzed.

----

Note that Point Blocking itself is not a claimed contribution of our work. However, if you wish to run the benchmarks (both transformed and untransformed) in the TreeSplicer-run-benchmarks directory, you should navigate into either apps/base/ or apps/block/ and do the following:

javac APPNAME/*.java -d classes/
java -cp classes/ util.Launcher --blocksize BLOCKSIZE APPNAME.Main ARGS

Running this without args should output which args are needed. For blocksize we tested with the benchmarks fully blocked, so blocksize = input size. Do note that the benchmarks to run are slightly different than the analyzed benchmarks, as tree dependence analysis requires specific constraints in the type of code analyzed (this mostly just requires unfolding branching statements, rather than using temporary variables). The launcher in TreeSplicer performs the timing of the benchmarks, so it is best to run them this way.