Interested in a PLAGIARISM-FREE paper based on these particular instructions?...with 100% confidentiality?

Order Now

Assignment 4: Dataflow Fall Semester 2017 Corresponding Lecture: Lesson 5 (Dataflow Analysis) Objective This assignment will familiarize you with writing static program analyses using LLVM. LLVM is a collection of compiler and analysis toolchain utilities widely used in the software analysis community. You will use LLVM to implement two intra-procedural dataflow analyses, one forward (reaching definitions analysis) and one backward (liveness analysis). Resources ● LLVM Webpage: http://llvm.org ● Getting Started with LLVM: http://releases.llvm.org/3.6.2/docs/GettingStarted.html http://releases.llvm.org/3.6.2/docs/GettingStarted.html#anexample- using-the-llvm-tool-chain ● LLVM Documentation: http://releases.llvm.org/3.6.2/docs/index.html http://releases.llvm.org/3.6.2/docs/ProgrammersManual.html http://releases.llvm.org/3.6.2/docs/LangRef.html http://llvm.org/doxygen/index.html ● C++ Pointers Tutorial: http://www.cplusplus.com/doc/tutorial/pointers/ Setup 1. Download and extract the assignment code found on T-Square in the file dataflow.zip . 2. Navigate to dataflow/build and run the following commands: cmake .. make clean make (You should now see libDataflowPass.so under dataflow/build/Dataflow .) 3. Go to the dataflow/example directory and compile the programs we will analyze with the following commands: clang -emit-llvm ArrayDemo.c -c -o ArrayDemo.bc clang -emit-llvm Greatest.c -c -o Greatest.bc 4. Run the Dataflow pass using the commands below to ensure everything works as expected for the test program ArrayDemo.c . These commands print the results of reaching definition analysis and liveness analysis (they are empty sets because the analyses are only stubs) as the dataflow facts for each instruction. opt -load ../build/Dataflow/libDataflowPass.so -ReachDef /dev/null opt -load ../build/Dataflow/libDataflowPass.so -Liveness /dev/null Assignment Instructions Complete the doAnalysis method in ReachDefAnalysis.cpp and LivenessAnalysis.cpp (located in dataflow/Dataflow/ ) to implement the two analyses. Do not write your analysis code outside of these files, as these files are the only ones you will submit. You may use the C++ Standard Template Library (STL) with LLVM. Your code will need to iterate over the program points in the input function and store the computed dataflow facts in DataflowAnalysis::inMap and DataflowAnalysis::outMap . Both analyses inherit from the base class DataflowAnalysis , which you can find in the header file DataflowAnalysis.h located in the directory dataflow/Dataflow/ . Besides including useful classes such as SetVector and ValueMap , DataflowAnalysis.h also defines usefl utility functions such as getPredecessors , getSuccessors , and isDef . The file Printer.cpp (also in the same directory) demonstrates the API by printing the definitions, uses, predecessors, and successors of each instruction. You can execute it using the command: opt -load ../build/Dataflow/libDataflowPass.so -Printer /dev/null After completing the two doAnalysis methods, re-build the analyses using the commands from setup Step 2, and then rerun the analyses using the commands from setup Step 4 to obtain the output of your analyses on the ArrayDemo.c program. If your implementation is correct, your output will match the example output in ArrayDemo_ReachDef and ArrayDemo_Liveness (both found in dataflow/example/ ). The order of elements in the in and out sets does not matter, but the number of elements and the values should match exactly. We have also included another program, Greatest.c , and it’s expected outputs for testing your implementation. You can use commands similar to those the final set-up instruction step to analyze this program. Assignment Documentation These entries in the programmer’s manual are relevant to the analyses you will write: ● Using isa to check whether a pointer points to an instance of a particular type. http://llvm.org/docs/ProgrammersManual.html#the-isa-cast-and-dyn-c ast-templates ● Enumerating basic blocks and instructions in a function: http://releases.llvm.org/3.6.2/docs/ProgrammersManual.html#basic-i nspection-and-traversal-routines http://releases.llvm.org/3.6.2/docs/ProgrammersManual.html# iterating-over-predecessors-successors-of-blocks ● Important classes: http://releases.llvm.org/3.6.2/docs/ProgrammersManual.html#thevalue- class http://releases.llvm.org/3.6.2/docs/ProgrammersManual.html#theuser- class http://releases.llvm.org/3.6.2/docs/ProgrammersManual.html#theinstruction- class http://llvm.org/docs/doxygen/html/classllvm_1_1ValueMap.html http://llvm.org/docs/doxygen/html/classllvm_1_1SetVector.html Additional tips ● Instead of source code, LLVM uses its own intermediate representation (bitcode files) compiled from source files. These intermediate representations are in the static single assignment (SSA) form. Since each variable is only defined once, LLVM represents each variable directly using the instruction defining it. In fact, the Instruction class is a subtype of the Value class. You can check whether an instruction defines a variable by checking getType()->isVoidTy() . ● ValueMap has a similar interface to that of std::map ( http://www.cplusplus.com/ reference/map/map/ ). For example, you can access or insert an element using the [] operator: ValueMap vm; Instruction* I = /*…*/; vm[I] = 5; // inserts to the map printf(“%d”, vm[I]); // accesses vm[I] You will not need to insert any new elements into DataflowAnalysis::inMap or DataflowAnalysis::outMap because the sets for holding dataflow facts already exist (see DataflowAnalysis.cpp ). ● SetVector is likewise similar to std::vector ( http://www.cplusplus.com/ reference/vector/vector/ ) except that it does not permit inserting duplicate elements. Note that the == operator returns false for two SetVector objects containing the same elements in different orders. Note also that functions in from the STL ( http://www.cplusplus.com/reference/algorithm/ ) work with SetVector . For example: SetVector sv; for( int i = 0; i < 5; i++ ) sv.insert(i); sv.insert(0); // has no effect printf("%u", (int)sv.size()); // prints 5 if (std::all_of(sv.begin(), sv.end(), isPositive)) // all_of is from printf(“All numbers in sv are positive!”); assuming isPositive is defined elsewhere as: bool isPositive(int i) {return i > 0;} Items to Submit 1. (50 points) LivenessAnalysis.cpp 2. (50 points) ReachDefAnalysis.cpp Submit the files separately, not in an archive. Grading Criteria ● We will generally award credit using the following formula. If the correct output set for Analysis X contains n entries and your output set contains a of those correct entries and b spurious entries, then you will receive max(0, ( a – b )/ n ) of the points for Analysis X (this is floating-point division, not integer division, of course). ● You will also receive a deduction if your code doesn’t terminate within two minutes. (If your code for an analysis doesn’t terminate at all, you will receive no credit for that analysis.) ● While efficiency is important, it is entirely secondary to correctness. Though you may lose some points for an inefficient yet correct algorithm, you will not gain points for an efficient yet incorrect algorithm.

Assignment 4: Dataflow
Fall Semester 2017

Corresponding Lecture: Lesson 5 (Dataflow Analysis)
Objective
This assignment will familiarize you with writing static program analyses using LLVM. LLVM
is a collection of compiler and analysis toolchain utilities widely used in the software analysis
community. You will use LLVM to implement two intra-procedural dataflow analyses, one
forward (reaching definitions analysis) and one backward (liveness analysis).
Resources
● LLVM Webpage:
http://llvm.org
● Getting Started with LLVM:
http://releases.llvm.org/3.6.2/docs/GettingStarted.html
http://releases.llvm.org/3.6.2/docs/GettingStarted.html#anexample-
using-the-llvm-tool-chain
● LLVM Documentation:
http://releases.llvm.org/3.6.2/docs/index.html
http://releases.llvm.org/3.6.2/docs/ProgrammersManual.html
http://releases.llvm.org/3.6.2/docs/LangRef.html
http://llvm.org/doxygen/index.html
● C++ Pointers Tutorial:
http://www.cplusplus.com/doc/tutorial/pointers/
Setup
1. Download and extract the assignment code found on T-Square in the file dataflow.zip .
2. Navigate to dataflow/build and run the following commands:
cmake ..
make clean
make
(You should now see libDataflowPass.so under dataflow/build/Dataflow .)
3. Go to the dataflow/example directory and compile the programs we will analyze with
the following commands:
clang -emit-llvm ArrayDemo.c -c -o ArrayDemo.bc
clang -emit-llvm Greatest.c -c -o Greatest.bc
4. Run the Dataflow pass using the commands below to ensure everything works as
expected for the test program ArrayDemo.c . These commands print the results of
reaching definition analysis and liveness analysis (they are empty sets because the
analyses are only stubs) as the dataflow facts for each instruction.
opt -load ../build/Dataflow/libDataflowPass.so -ReachDef < ArrayDemo.bc > /dev/null
opt -load ../build/Dataflow/libDataflowPass.so -Liveness < ArrayDemo.bc > /dev/null
Assignment Instructions
Complete the doAnalysis method in ReachDefAnalysis.cpp and LivenessAnalysis.cpp
(located in dataflow/Dataflow/ ) to implement the two analyses. Do not write your analysis
code outside of these files, as these files are the only ones you will submit.
You may use the C++ Standard Template Library (STL) with LLVM.
Your code will need to iterate over the program points in the input function and store the
computed dataflow facts in DataflowAnalysis::inMap and DataflowAnalysis::outMap . Both
analyses inherit from the base class DataflowAnalysis , which you can find in the header file
DataflowAnalysis.h located in the directory dataflow/Dataflow/ . Besides including useful
classes such as SetVector and ValueMap , DataflowAnalysis.h also defines usefl utility
functions such as getPredecessors , getSuccessors , and isDef .
The file Printer.cpp (also in the same directory) demonstrates the API by printing the
definitions, uses, predecessors, and successors of each instruction. You can execute it using the
command:
opt -load ../build/Dataflow/libDataflowPass.so -Printer < ArrayDemo.bc > /dev/null
After completing the two doAnalysis methods, re-build the analyses using the commands from
setup Step 2, and then rerun the analyses using the commands from setup Step 4 to obtain the
output of your analyses on the ArrayDemo.c program. If your implementation is correct, your
output will match the example output in ArrayDemo_ReachDef and ArrayDemo_Liveness (both
found in dataflow/example/ ). The order of elements in the in and out sets does not matter, but
the number of elements and the values should match exactly.
We have also included another program, Greatest.c , and it’s expected outputs for testing your
implementation. You can use commands similar to those the final set-up instruction step to
analyze this program.
Assignment Documentation
These entries in the programmer’s manual are relevant to the analyses you will write:
● Using isa<> to check whether a pointer points to an instance of a particular type.
http://llvm.org/docs/ProgrammersManual.html#the-isa-cast-and-dyn-c
ast-templates
● Enumerating basic blocks and instructions in a function:
http://releases.llvm.org/3.6.2/docs/ProgrammersManual.html#basic-i
nspection-and-traversal-routines
http://releases.llvm.org/3.6.2/docs/ProgrammersManual.html#
iterating-over-predecessors-successors-of-blocks
● Important classes:
http://releases.llvm.org/3.6.2/docs/ProgrammersManual.html#thevalue-
class
http://releases.llvm.org/3.6.2/docs/ProgrammersManual.html#theuser-
class
http://releases.llvm.org/3.6.2/docs/ProgrammersManual.html#theinstruction-
class
http://llvm.org/docs/doxygen/html/classllvm_1_1ValueMap.html
http://llvm.org/docs/doxygen/html/classllvm_1_1SetVector.html
Additional tips
● Instead of source code, LLVM uses its own intermediate representation (bitcode files)
compiled from source files. These intermediate representations are in the static single
assignment (SSA) form. Since each variable is only defined once, LLVM represents
each variable directly using the instruction defining it. In fact, the Instruction class is
a subtype of the Value class. You can check whether an instruction defines a variable by
checking getType()->isVoidTy() .
● ValueMap has a similar interface to that of std::map ( http://www.cplusplus.com/
reference/map/map/ ). For example, you can access or insert an element using the []
operator:
ValueMap<Instruction*, int> vm;
Instruction* I = /*…*/;
vm[I] = 5; // inserts <I, 5> to the map
printf(“%d”, vm[I]); // accesses vm[I]
You will not need to insert any new elements into DataflowAnalysis::inMap or
DataflowAnalysis::outMap because the sets for holding dataflow facts already exist
(see DataflowAnalysis.cpp ).
● SetVector is likewise similar to std::vector ( http://www.cplusplus.com/
reference/vector/vector/ ) except that it does not permit inserting duplicate
elements. Note that the == operator returns false for two SetVector objects containing
the same elements in different orders. Note also that functions in <algorithm> from the
STL ( http://www.cplusplus.com/reference/algorithm/ ) work with SetVector . For
example:
SetVector<int> sv;
for( int i = 0; i < 5; i++ )
sv.insert(i);
sv.insert(0); // has no effect
printf(“%u”, (int)sv.size()); // prints 5
if (std::all_of(sv.begin(), sv.end(), isPositive))
// all_of is from <algorithm>
printf(“All numbers in sv are positive!”);
assuming isPositive is defined elsewhere as:
bool isPositive(int i) {return i > 0;}
Items to Submit
1. (50 points) LivenessAnalysis.cpp
2. (50 points) ReachDefAnalysis.cpp
Submit the files separately, not in an archive.
Grading Criteria
● We will generally award credit using the following formula. If the correct output set for
Analysis X contains n entries and your output set contains a of those correct entries and
b spurious entries, then you will receive max(0, ( a – b )/ n ) of the points for Analysis X
(this is floating-point division, not integer division, of course).
● You will also receive a deduction if your code doesn’t terminate within two minutes. (If
your code for an analysis doesn’t terminate at all, you will receive no credit for that
analysis.)
● While efficiency is important, it is entirely secondary to correctness. Though you may
lose some points for an inefficient yet correct algorithm, you will not gain points for an
efficient yet incorrect algorithm.

Interested in a PLAGIARISM-FREE paper based on these particular instructions?...with 100% confidentiality?

Order Now