DOC PREVIEW
CMU CS 15745 - assignment- Introduction to LLVM

This preview shows page 1-2 out of 5 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 5 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 5 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 5 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Assignment 1: Introduction to LLVM15-745: Optimizing CompilersDue: 12:00am, Tuesday, January 27We will be using the Low Level Virtual Machine (LLVM) compiler infrastructure developed at theUniversity of Illinois Urbana-Champaign for our project work. We assume you have access to an x86 basedmachine (preferably running Linux, although Windows and Mac OS X should work as well).In this project you will write a simple program analysis and familiarize yourself with the LLVM sourcecode. You will write a liveness dataflow analysis from which you will produce a histogram of simultaneouslylive values.1 Install LLVMFirst download, install, and build the LLVM 2.4 source code from http://llvm.org. Follow the in-structions on the website http://llvm.org/docs/GettingStarted.html for your particularmachine configuration. You do not need to build the gcc frontend from source; you can use the prebuiltbinaries. We recommend that you install the LLVM gcc frontend in a different directory than your ex-isting gcc install (i.e., /usr0/local instead of /usr/local). Do not get the source from SVN; wewill be working off of the 2.4 release. Make sure you can build LLVM from within your preferred devel-opment environment (Eclipse for C++ kind of works, emacs is better if you’re already an expert). Notethat in order use a debugger on the LLVM binaries you will need to pass --enable-debug-runtime--disable-optimized to the configure script.Peruse through the documentation at http://llvm.org/docs/. The LLVM Programmer’s Man-ual (http://llvm.org/docs/ProgrammersManual.html) and Writing an LLVM Pass tutorial(http://llvm.org/docs/WritingAnLLVMPass.html) are particularly useful.2 Create a PassCreate a directory 15745 within the llvm/lib/Analysis directory tree. Copy LivenessHist-togram.cpp (provided with the assignment) into the directory and create a Makefile:LEVEL = ../../..LIBRARYNAME = LivenessHistogramLOADABLE_MODULE = 1# do NOT set LLVMLIBS, the LLVM documentation has this wrong#LLVMLIBS = LLVMCore.a LLVMSupport.a LLVMSystem.ainclude $(LEVEL)/Makefile.common1int g;int erk(int a, int b){int i;int x = g;int ret = 0;for(i = 0; i < b; i++){ret = ret*a;}return ret+x;}(a)@g = weak global i32 0define i32 @erk(i32 %a, i32 %b) {entry:%tmp1 = load i32*@g, align 4%tmp1023 = icmp sgt i32 %b, 0br i1 %tmp1023, label %bb7, label %bb12bb7: ; preds = %bb7, %entry%i.020.0 = phi i32 [0, %entry], [%indvar.next, %bb7]%ret.018.0 = phi i32 [0, %entry], [%tmp4, %bb7]%tmp4 = mul i32 %ret.018.0, %a%indvar.next = add i32 %i.020.0, 1%exitcond = icmp eq i32 %indvar.next, %bbr i1 %exitcond, label %bb12, label %bb7bb12: ; preds = %bb7, %entry%ret.018.1 = phi i32 [0, %entry], [%tmp4, %bb7]%tmp15 = add i32 %ret.018.1, %tmp1ret i32 %tmp15}(b)Figure 1: A simple test case ?? and a slightly simplified print out of the corresponding LLVM bytecode ??.Use this Makefile to build the pass. If you want your pass to build as part of the overall LLVM build you needto add the 15745 directory to the makefile in llvm/lib/Analysis. The provided LivenessHistogrampass implements an LLVM pass that does nothing but print out Hello. Before writing any code, make sureyou can properly run this dummy pass. Create the file test.c from the code in Figure ?? and compile itto optimized LLVM bytecode:/usr0/local/bin/gcc -O -emit-llvm -c test.cInspect the result using llvm-dis:llvm-dis test.oThis will create a file test.o.ll that should look very similar to Figure ??.Now try running the dummy LivenessHistogram pass on the bytecode using the opt command (if youdid not compile with debug information, the shared library will be in the Release directory):opt -load llvm/Debug/lib/LivenessHistogram -liveness-hist test.o -o outIf all goes well you should see Hello print out to stderr.3 Liveness Analysis ImplementationThe next step is to extend LivenessHistogram.cpp to perform a backwards dataflow analysis thatcomputes the live sets of values at each program point and then generates a histogram of the number ofprogram points with a given number of simultaneously live values. This does not actually require a largeamount of code (if you find yourself writing more than 200 lines of code you’re probably doing somethingwrong). However, there is a lot of code to read and understand. Do not put this off to the last minute.The SSA form of LLVM intermediate representation presents some unique challenges when performingthe dataflow analysis.• Values in LLVM are represented by the Value class. In SSA every value is guaranteed to have2only a single definition point so instead of representing values as some distinct variable or pseudo-register class, LLVM represents values defined by instructions by the defining instruction. That is,Instruction is a subclass of Value. There are other subclasses of Value, such as basic blocks(labels), constants, and function arguments. For this assignment we will only track the liveness ofinstruction-defined values and function arguments. That is, when determining what values are usedby an instruction, you will use code like this:User::op_iterator OI, OE;for (OI = insn->op_begin(), OE = insn->op_end(); OI != OE; ++OI){Value*val =*OI;if(isa<Instruction>(val) || isa<Argument>(val)){//val is used by insn}}• φ instructions are not real instructions and need to be handled specially by the liveness analysis. Youshould think of the whole set of φ instructions at the beginning of a block as essentially acting as asingle instruction that defines (kills) all the values written by the φ instructions. Each operand of aφ instruction is only live along the edge from the corresponding predecessor block. In our analysiswe do not consider this operand to be live into the block with the φ instruction, only live out of thecorresponding predecessor block. When computing the liveness histogram, we ignore the programpoints before φ instructions as the liveness sets are not well defined at these points.The liveness sets that should be computed for the example in Figure ?? are shown in Figure ??. Theresulting histogram that should be output is:0: 11: 12: 23: 24: 15: 46: 1This says that there is one program point with no live variables, one program point with one live variable,two program points with two live variables, etc. Your solution should exactly match this output.4 AnalysisWe will now use the results of the LivenessHistogram pass to analyze the effect of various optimizations.First unpack the VersaBench (http://cag.csail.mit.edu/versabench/ benchmark source


View Full Document

CMU CS 15745 - assignment- Introduction to LLVM

Documents in this Course
Lecture

Lecture

14 pages

Lecture

Lecture

19 pages

Lecture

Lecture

8 pages

Lecture

Lecture

5 pages

Lecture

Lecture

6 pages

lecture

lecture

17 pages

Lecture 3

Lecture 3

12 pages

Lecture

Lecture

17 pages

Lecture

Lecture

18 pages

lecture

lecture

14 pages

lecture

lecture

8 pages

lecture

lecture

5 pages

Lecture

Lecture

19 pages

lecture

lecture

10 pages

Lecture

Lecture

20 pages

Lecture

Lecture

8 pages

Lecture

Lecture

7 pages

lecture

lecture

59 pages

Lecture

Lecture

10 pages

Task 2

Task 2

2 pages

Handout

Handout

18 pages

Load more
Download assignment- Introduction to LLVM
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view assignment- Introduction to LLVM and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view assignment- Introduction to LLVM 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?