” CSC2107编程设计 写作、 辅导data程序University of TorontoCSC 488 / CSC2107 Compilers and Interpreters Winter 2021Assignment 6: LLVM IR Optimization (16%)Due: April. 1, 2021In this assignment, you will work on 2 parts for LLVM IR optimization in the MiniC Compiler: Memory to Register Promotion (alloca2reg) (10 marks out of 16) Open-ended IR optimization design (6 marks out of 16)Note that for the open-ended IR optimization part, we will use the resubmission as the final programto test and determine the rest of your score (if you decide to do the resubmit).LLVM IR Optimization Workflow in MiniC (contd from Assignment 5 Workflow)After the MiniC compiler IR Bitcode is generated, PassManager in LLVM will chain multiple optimizationsand analysis passes to Run together. Command opt is a LLVM tool that directly invoke a pass on a LLVMIR bitcode. You will work on the src/Alloca2Reg.cpp source file. opt will do a function pass based onAlloca2Reg library object on the IR bitcode.alloca2reg DesignPlease review Safely Promote Local Variable to Registers section from the lecture (under Files/Slides/Optimizations.pdf).It shows the detailed design steps. Lecture also provides a link How LLVM Optimizesa Function as your reference of the assignment.alloca2reg Related Data Structures LLVM APIHere is a good tutorial on Writing an LLVM Pass as a starting point. Table 1 shows the data structuresin src/Alloca2Reg.cpp. You can add/modify/delete any structures in src/Alloca2Reg.cpp. We onlyprovide some structures which may be helpful for you to implement alloca2reg. You are recommended tomodify the structures for the open-ended design part.Table 2 describes related LLVM APIs for alloca2reg.Open-ended IR optimization designIn lecture, you were introduced to optimization methods such as machine dependent/independent optimizations.This section gives you some more resources for reference. LLVM Tutorial: Writing an Optimization for LLVM How LLVM Optimizes a Function as mentioned above Writing an LLVM Pass as mentioned aboveYou can create new source files for your optimizations OR implement it in Alloca2Reg.cpp. If creatingnew files, you may modify src/CMakeLists.txt as an additional library object. You should provide yourcommand of generating IR bitcode when submitting.1Name Descriptionstruct Alloca2RegPass Derived struct from llvm::FunctionPass.Alloca2RegPass::ID = 0 Declares pass identifier used by LLVM to identify pass. This allows LLVM toavoid using expensive C++ runtime information. LLVM uses IDs address toidentify a pass, so the initialization value is not important.Alloca2RegPass::TargetAllocas collectTargetAllocas()Helps to collect all of the alloca instructions which can be removed. Pleaselook at step 1 from the lecture.Alloca2RegPass::Post Pre As mentioned in lecture, in step 2, they hold the representative value of thevariable at the end of the basic block BB.Alloca2RegPass::RunOnFunction() Overrides an abstract virtual method inherited from llvm::FunctionPass.Other variables To run an LLVM Pass automatically with clang. You dont need to worry aboutit. You could check out the link here for more details.Table 1: Data Structure DescriptionName under namespace llvm DescriptionAllocaInst, StoreInst, LoadInst alloca, store, load instructionsPointerType* AllocaInst::getType() Overload to return most specific pointer type.Type* PointerType::getElementType() Return the type of the element which PointerType points to.bool Type::isIntegerTy() Return true if the type is integer type.Value* StoreInst::, LoadInst::getPointerOperand() Get the pointer operand.Value* StoreInst::getValueOperand() Get the value operand.Instruction::eraseFromParent() This method unlinks this from the containing basic block anddeletes it.BasicBlock::begin(), end() Instruction iterator methodsFunction::begin(), end() Basic Block iterator methodsPHINode member functions You can search it for your implementation.Table 2: LLVM API DescriptionRequirements The functionality of your output program should be correct. Your output program should remove all of the alloca instructions which can be removed. Your output program must reach a baseline speed under the -O0 flag. The baseline speed is theassignment 6 sample solution with only the alloca2reg optimization. As a reference, under these specs(Memory: 16GB 2400 MHz DDR4 CPU: 2.6GHz 6-Core Intel Core i7), the A6 sample solution withthe -O0 flag running the queen_time.c test case with input=13 50 times consumes 68.46 seconds.clang-11 with -O3 flag consumes 50.69 seconds. The test script is provided as asst6.py. Your open-ended design speed/performance will be competing with the rest of the class. The marksfor open-ended design will depend on your relative rank. Note that even the slowest implementationthat is functionally correct will receive a passing grade for this assignment.Compilation and TestingPlease make sure you are Using clang 11.0. After compiling your MiniC compiler, you can run:2# Under build/ directory# Generate IR Bitcodesrc/minicc YourInput.c -o output.bc# Run Alloca2Reg passopt -O0 -load src/liballoca2reg.so –alloca2reg output.bc -o output_opt.bc# Generate executable opt/non-opt filesclang output.bc minicio/libminicio.a -o outputclang output_opt.bc minicio/libminicio.a -o output_opt# Run the executable opt/non-opt files./output./output_opt# Generate IR assembly code (Important for debugging!)llvm-dis output.bc -o output.llllvm-dis output_opt.bc -o output_opt.llPublic AutotesterWe have provided a public Autotester a6tester.zip on Quercus. After compiling your code, changeasst6.py to your minicc executable file path. Then simply run:$./asst6.pyOR in verbose mode$./asst6.py -vThe tester has several MiniC source files. Your compiler will compile the files and the generated executablefiles will run without any errors in the tester. Then, compared to your unoptimized version, the tester simplychecks whether the number of Alloca instructions were reduced. Finally, you can compare the runtime ofyour solution and use the -O3 clang solution as your reference.DeliverablesIn the project folder, compress the whole project content as a zip file. This zip file must match the structureof the skeleton code, and it must compile in our A1 environment, or you may receive a 0 on the automarker.Note that there is only one deadline for the open-ended part of the assignment (1 week after the first duedate). On Markus, please submit: code.zip. We will directly unzip your submission, build it from source and run it against public andprivate tests. explanation.txt: Put your command for generating output_opt.bc in the first line, i.e., opt-O0 -load ….. You must use -O0 or dont use any flag in the command. Your command is usedfor testing your output program speed. Then put your explanation of optimization methods in anewline. sample.c: A sample program Which you think performs well under your optimizations. Its complexityand its performance improvement will be considered for grading.请加QQ：99515681 或邮箱：99515681@qq.com WX：codehelp
“
添加老师微信回复‘’官网 辅导‘’获取专业老师帮助，或点击联系老师1对1在线指导。
