CSI8105-01 Fall 2021 Assignment 1 Assignment due date: Monday, Dec. 6 2021, 23:59, on LearnUs. Contents 1 Introduction 1 1.1 Policy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Deliverables and submission . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 2 ACC VirtualBox image 2 2.1 Setting up the ACC VM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 2.2 LLVM installations on the ACC VM image . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2.3 Fine-tuning of the ACC VM image configuration and fast compilation . . . . . . . . . . . . . 3 3 Working with LLVM on the provided system image 4 3.1 Pass creation, compilation, and test . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 4 LLVM analysis passes 6 4.1 Function information . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 4.2 Local optimizations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 4.2.1 Implementation hints . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 A Useful LLVM commands and arguments 10 B Troubleshooting 10 B.1 opt is not touching the IR. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 B.2 CMake verbose build option . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1 Introduction 1.1 Policy You will work in groups of preferably two people (but one-person groups will also be accepted) to solve the problems in this assignment. Please turn in a single writeup per group. The writeup must indicate all group members. 1 CSI8105-01 Fall 2021 1.2 Deliverables and submission Please include the following items in an archive labeled with the student ID of one of your members in your group (e.g., 2018010201.tar.gz), and submit this archive in the provided folder on LearnUs. Please make sure that when this archive is extracted, the files appear as follows: ./2018010201/README.txt ./2018010201/FunctionInfo/FunctionInfo.cpp ./2018010201/FunctionInfo/CMakeLists.txt ./2018010201/FunctionInfo/tests/ ./2018010201/LocalOpts/LocalOpts.cpp ./2018010201/LocalOpts/CMakeLists.txt ./2018010201/LocalOpts/tests/ ./2018010201/writeup.pdf 1. A report in PDF format that briefly describes the implementation of both LLVM passes, named writeup.pdf. Please provide the names and student IDs of all group members on the cover-page of the report. 2. The documented source code of your passes in files FunctionInfo.cpp and LocalOpts.cpp plus CMake buildscripts. 3. A README.txt file that contains the commands how to build and run your passes on the provided VM image (see Section 2). 4. Any tests used for validation of your code (in the tests/ subdirectories as outlined above). 2 ACC VirtualBox image To ensure that all assignment code is graded in the same environment using LLVM 13.0.0, you are provided with a 64-bit CentOS 7 virtual machine image, the ACC VM image. You must ensure that your code works in this environment, but you’re not required to do all of your development in it. The ACC VM image can be downloaded from the following Yonsei University GoogleDrive folder. https://drive.google.com/drive/folders/1AKTqD7dnzDYbPJ5M3GnTgAgmG48McYuO?usp=sharing You must be logged in with your Yonsei University email address to access this GoogleDrive folder. If you do not have a Yonsei University email address available, please contact the course instructor with an alternative Gmail address under which you wish to access the folder. 2.1 Setting up the ACC VM VirtualBox is a hypervisor available for several platforms (http://www.virtualbox.org). Please download the hypervisor for your OS (Windows, OS X, Linux, . . . ) and install it on your computer. Along with the ACC VM image named CSI8105_CentOS_7.ova, you are recommended to download the checksum file named CSI8105_CentOS_7.ova.sha512. This checksum file can be used to verify the integrity of the downloaded image. To import the VM image into VirtualBox, launch VirtualBox, select the "File" menu, and click "Import Appliance". You may keep all “Appliance settings”. The import will take several minutes. The size of the provided VM image is 4.12GB. After importing, the VM will consume about 17GB of disk space. Note that the downloaded ova file is no longer needed after the import and can be deleted, to conserve disk space. Advanced Compiler Construction Page 2 of 10 CSI8105-01 Fall 2021 The ACC VM name is CSI8105_CentOS_7. An account with username user and password user has been created. (Please note that in the standard VirtualBox configuration of the ACC VM’s network interface, the ACC VM is only accessible from your local computer. If you change the VM’s setup to make the ACC VM accessible from the internet, please do not forget to use a strong password for the user account.) If you are new to VirtualBox or are interested in convenience features, you’re recommended to take a look at the guide VirtualBox_HowTo.pdf provided in the “Resources” folder on LearnUs. Although the examples in the guide pertain to another course, all information about VirtualBox itself applies to the CSI8105_CentOS_7 VM, too. 2.2 LLVM installations on the ACC VM image The ACC VM image has two different builds of LLVM 13.0.0 installed: 1. Release build: the release build is installed in /opt/llvm/13.0.0_ACC. The binaries of the release build are without debug information and optimized for fast compilation times. The $PATH, $CC and $CXX variables in the VM image have been set to this release build. Thus, clang and opt without a path default to this installation: [user@csi8105 ~]$ opt --version LLVM (http://llvm.org/): LLVM version 13.0.0 Optimized build. Default target: x86_64-unknown-linux-gnu Host CPU: sandybridge 2. Debug build: the debug build is installed in /opt/llvm/13.0.0_dbg_ACC. The binaries of the debug build contain debug information and have been compiled to ease debugging (i.e., debugging of the com- piler itself). Compiling with the debug build takes much longer, and you should use the debug build only when you’re debugging your own passes with LLDB. [user@csi8105 ~]$ /opt/llvm/13.0.0_dbg_ACC/bin/opt --version LLVM (http://llvm.org/): LLVM version 13.0.0 DEBUG build with assertions. Default target: x86_64-unknown-linux-gnu Host CPU: sandybridge The source code of LLVM, CLANG and LLDB that have been used to build the LLVM toolchains in /opt/llvm/ are provided in the home-directory in the directory tarballs/. (Note that you do not need the source code to compile your passes. The source code is provided for your reference only.) To access the source code, you must inflate the corresponding tar archive first, e.g., for LLVM: [user@csi8105 ~]$ cd tarballs [user@csi8105 tarballs]$ tar xf llvm-13.0.0.src.tar.xz 2.3 Fine-tuning of the ACC VM image configuration and fast compilation After importing, the VM uses default settings for the amount of system resources made available from the host OS. To ensure fast compilation speed, you’re recommended to consider and perhaps adjust the following Advanced Compiler Construction Page 3 of 10 CSI8105-01 Fall 2021 settings: 1. Allocate ample memory from your host’s RAM to the VM. With the VM powered down, right-click the VM and select “Settings”. Under the “System” section, adjust the VM’s “Base Memory”. If your host’s RAM capacity allows, allocate 6GB–12GB of RAM to the VM. The memory requirements in excess of the allotted RAM will be provided with the help of the VM’s swap file, which results in longer compilation times. 2. If you are compiling a larger project, e.g., re-compiling the entire LLVM compiler, you should assign multiple cores to your VM. This can be achieved in the “Processor” tab of the “System” section described previously. 3. Always compile with the release build installed under /opt/llvm/13.0.0_ACC. If you’re not sure which version you are using, you can find out as follows. [user@csi8105 ~]$ which clang /opt/llvm/13.0.0_ACC/bin/clang 3 Working with LLVM on the provided system image For this assignment, we’re using the new LLVM pass manager (PM). To avoid clutter, code for the legacy pass manager has been omitted from the following discussion and the code provided with this assignment. Your own passes only have to support the new PM. Please refer to our Lecture 2 on “LLVM Getting started”, in particular the section on “First steps with LLVM”. Further information can be found in the following online documents. • Getting started with the LLVM toolchain • For programming with LLVM, please have a look at the Writing an LLVM Pass tutorial. • Important LLVM programming idioms are explained in the LLVM Programmer’s Manual. • The LLVM Coding Standard explains coding rules and guidelines for LLVM contributors. You’re recom- manded to read the standard, but the standard will not be enforced with our assignments. • The entire LLVM documentation for release 13.0.0 is provided here. • The LLVM Tutor is a set of curated LLVM passes for various analysis and transformation problems. Although not an official part of the LLVM documentation, it is one of the most up-to-date sources of programming examples on LLVM. The provided examples already incorporate the use of the new PM. 3.1 Pass creation, compilation, and test Extract the provided archive ACC_Assignment_1.tgz and change to the FunctionInfo directory: [user@csi8105 ~]$ tar xf ACC_Assignment_1.tgz [user@csi8105 ~]$ cd ACC_Assignment_1/FunctionInfo [user@csi8105 FunctionInfo]$ ls The directory FunctionInfo contains a dummy LLVM pass in file FunctionInfo.cpp. When run, this pass prints status information and exists. In the next section, we will extend this pass to collect interesting information about functions. Advanced Compiler Construction Page 4 of 10 CSI8105-01 Fall 2021 LLVM employs CMake to automate its build. CMake is not a build system, but rather a meta-tool that generates the build system from an input specification. The CMake input specification for our pass is provided in file CMakeLists.txt. For our purpose, it is not required to fully understand the contents of this file, but you’re nevertheless recommended to have a look. We employ an out-of-tree build for our pass, which means that all of our pass’ artifacts (source code, build scripts, etc.) are kept outside of the LLVM project’s source tree. Our build obtains all relevant LLVM header files and LLVM dynamic-link libraries from the used LLVM installation in /opt/llvm. We need a build directory in which CMake will generate the GNU Make Makefile for our pass. From the FunctionInfo directory, please conduct the following three steps. The last step invokes CMake on the parent of the build directory (which is the location of our CMakeLists.txt file). [user@csi8105 FunctionInfo] mkdir build [user@csi8105 FunctionInfo]$ cd build [user@csi8105 build]$ cmake .. -- The C compiler identification is Clang 13.0.0 -- The CXX compiler identification is Clang 13.0.0 -- Detecting C compiler ABI info -- Detecting C compiler ABI info - done -- Check for working C compiler: /opt/llvm/13.0.0_ACC/bin/clang - skipped -- Detecting C compile features -- Detecting C compile features - done -- Detecting CXX compiler ABI info -- Detecting CXX compiler ABI info - done -- Check for working CXX compiler: /opt/llvm/13.0.0_ACC/bin/clang++ - skipped -- Detecting CXX compile features -- Detecting CXX compile features - done -- Found ZLIB: /usr/lib64/libz.so (found version "1.2.7") -- Found LibXml2: /usr/lib64/libxml2.so (found version "2.9.1") -- Configuring done -- Generating done -- Build files have been written to: /home/user/ACC_Assignment_1/FunctionInfo/build Directory build is now ready to compile our pass and we invoke GNU make: [user@csi8105 build]$ make [ 50%] Building CXX object CMakeFiles/FunctionInfo.dir/FunctionInfo.cpp.o [100%] Linking CXX shared library libFunctionInfo.so [100%] Built target FunctionInfo Your build directory should now contain file libFunctionInfo.so, which is the shared library that contains our dummy pass. Next, compile the file factorial.c (see Figure 1) provided in the tests/ directory to LLVM bytecode as follows. (Note that the backslash “\” at the end of the first line is a line continuation, to continue to the next line. If you type everything in one long line, you must omit the backslash.) [user@csi8105 build]$ clang -Xclang -disable-O0-optnone -fno-discard-value-names \ -emit-llvm -c ../tests/factorial.c [user@csi8105 build]$ opt -mem2reg factorial.bc -o factorial.mem2reg.bc [user@csi8105 build]$ llvm-dis factorial.mem2reg.bc The resulting LLVM IR in file factorial.mem2reg.ll should look similar to the one depicted in Figure 2 Advanced Compiler Construction Page 5 of 10 CSI8105-01 Fall 2021 on page 7. Now, try to run the compiled FunctionInfo pass on the LLVM bytecode: [user@csi8105 build]$ opt -load-pass-plugin=./libFunctionInfo.so \ -passes="print" -disable-output factorial.mem2reg.bc Processing module : ----------------- Analysis results: ----------------- Listing 1: Invoking opt from the command line Note that opt requires the path to the pass’ shared library file. Therefore, the “./” (for the current working directory) is prepended to the shared library file name FunctionInfo.so. If all goes well, “Processing module :...” should be printed to stderr. The dummy pass does not conduct any analysis yet, thus no analysis results are output. Table 2 in the appendix on page 10 lists important parameters for your work with LLVM. Many of them have been applied with the above examples already. int g = 5; int f ac to r i a l (int n) { if (n > 1) return n * fac to r i a l (n−1) ; else return 1; } int main(void) { int i , f = 0; for ( i = 1; i < g; i++) { f += fac to r i a l ( i ) ; } return f + g; } Figure 1: C source code from test file factorial.c 4 LLVM analysis passes 4.1 Function information Program analysis collects information about a program which can then be used with program transformations. A compiler pass is the standard mechanism for analyzing and transforming programs in LLVM. We will extend the dummy FunctionInfo pass from the previous section to collect interesting properties about the functions in a program. Your pass should report the following information about all functions that appear in a program: 1. Name 2. Number of arguments (or * if variadic) Advanced Compiler Construction Page 6 of 10 CSI8105-01 Fall 2021 1 @g = dso_local global i32 5 , align 4 2 3 ; Function Attrs : noinline nounwind uwtable 4 define dso_local i32 @factorial ( i32 %n) { 5 entry : 6 %cmp = icmp sgt i32 %n, 1 7 br i1 %cmp, label %if.then, label %if.else 8 9 i f . then : ; preds = %entry 10 %sub = sub nsw i32 %n, 1 11 %call = cal l i32 @factorial ( i32 %sub) 12 %mul = mul nsw i32 %n, %call 13 br label %return 14 15 i f . e l s e : ; preds = %entry 16 br label %return 17 18 return : ; preds = %if.else, %if.then 19 %retval.0 = phi i32 [ %mul, %if.then ] , [ 1 , %if.else ] 20 re t i32 %retval.0 21 } 22 23 ; Function Attrs : noinline nounwind uwtable 24 define dso_local i32 @main( ) { 25 entry : 26 br label %for.cond 27 28 for.cond : ; preds = %for.inc, %entry 29 %i.0 = phi i32 [ 1 , %entry ] , [ %inc, %for.inc ] 30 %f.0 = phi i32 [ 0 , %entry ] , [ %add, %for.inc ] 31 %0 = load i32 , i32* @g, align 4 32 %cmp = icmp s l t i32 %i.0, %0 33 br i1 %cmp, label %for.body, label %for.end 34 35 for.body : ; preds = %for.cond 36 %call = cal l i32 @factorial ( i32 %i.0) 37 %add = add nsw i32 %f.0, %call 38 br label %for.inc 39 40 for . inc : ; preds = %for.body 41 %inc = add nsw i32 %i.0, 1 42 br label %for.cond, ! llvm.loop !4 43 44 for.end : ; preds = %for.cond 45 %1 = load i32 , i32* @g, align 4 46 %add1 = add nsw i32 %f.0, %1 47 re t i32 %add1 48 } Figure 2: LLVM bytecode for file factorial.c Advanced Compiler Construction Page 7 of 10 CSI8105-01 Fall 2021 3. Number of direct call sites in the same LLVM module (i.e., locations where this function is explicitly called by its name, ignoring function pointers). 4. Number of basic blocks 5. Number of instructions The expected numbers for running FunctionInfo on the bytecode from Figure 2 are depicted in Table 1. It is recommended that you debug your pass with more complex source files, because grading will be done with complex programs. Feel free to hand in your additional test source files together with your source code. Name # Args # Calls # Blocks # Instructions factorial 1 2 4 9 main 0 0 5 14 Table 1: Expected FunctionInfo output for the bytecode from Figure 2 You should extend the dummy pass in file FunctionInfo.cpp as follows: • For the LLVM Module &M provided to your pass’ FuncInfo::run method, you must iterate over all functions of M. • For each function, you must iterate over all basic blocks. • For each basic block, iterate over all instructions. • Whenever you find relevant information, your pass shall enter it into a data-structure. • After all functions have been processed, please make sure that the collected analysis information from your global data-structure is output by the provided FuncInfoPrinter::run method. (Please do not change this method.) 4.2 Local optimizations Our second pass is a transformation pass that makes programs run faster. We’re going to implement optimiza- tions on basic blocks as discussed in class (see Lecture 1). Additional information can be found in our course textbook (the Dragon Book) in Section 8.5.4. Although there exist many types of local optimizations, we will focus only on the following local optimizations: 1. Algebraic identities: e.g., x + 0 = 0 + x => x 2. Constant folding: e.g., 3 * 4 => 12 3. Strength reduction: e.g., 2 * x = x * 2 => (x + x) or (x << 1) You may pick two of the above categories. Within each category, please be as general as possible. E.g., do not hard-code 3 * 4 => 12, but rather fold all multiplications of two constants. 4.2.1 Implementation hints • In file LocalOpts/LocalOpts.cpp of the ACC_Assignment_1.tgz archive you find a code skeleton of a transformation pass. Please extend this skeleton for your local optimization pass. You are allowed to add methods, classes etc. to this file, as long as your pass can be used as described below. Advanced Compiler Construction Page 8 of 10 CSI8105-01 Fall 2021 • File LocalOpts/tests/foo.c contains a test function for this pass. You are recommended to provide further test cases for your pass (please refer to Section 1.2). • To build and run the LocalOpts pass, please proceed as described in Section 3.1. • Following the description in file LocalOpts.cpp, your pass can be used as follows. [user@csi8105 build]$ opt -load-pass-plugin ./libLocalOpts.so \ -passes="LocalOpts" infile.bc \ -o outfile.bc • Your pass is not required to produce any diagnostic output nor statistics on the conducted transformations. But you must maintain the Changed flag as described in method LocalOpts::run. • The functionality of your pass will be assessed from the input and output (file infile.bc and file outfile.bc above). • File lib/IR/ConstantFold.cpp of the LLVM source code might be a good starting point on how to detect constants in the IR. Advanced Compiler Construction Page 9 of 10 CSI8105-01 Fall 2021 Appendix A Useful LLVM commands and arguments The following table depcits useful LLVM commands and some of their ommand-line arguments. An exhaustive list of command-line arguments can be retrieved by passing the “--help” command-line argument to the command. Command Options Meaning clang -Xclang
