CSC2107编程设计讲解、辅导data程序、c++编程调试 调试Matlab程序|讲解Java程序
- 首页 >> Python编程 University of Toronto
CSC 488 / CSC2107 Compilers and Interpreters Winter 2021
Assignment 6: LLVM IR Optimization (16%)
Due: April. 1, 2021
In 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 program
to test and determine the rest of your score (if you decide to do the resubmit).
LLVM IR Optimization Workflow in MiniC (cont’d from Assignment 5 Workflow)
After the MiniC compiler IR Bitcode is generated, PassManager in LLVM will chain multiple optimizations
and analysis passes to run together. Command opt is a LLVM tool that directly invoke a pass on a LLVM
IR bitcode. You will work on the src/Alloca2Reg.cpp source file. opt will do a function pass based on
Alloca2Reg library object on the IR bitcode.
alloca2reg Design
Please 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 Optimizes
a Function as your reference of the assignment.
alloca2reg Related Data Structures & LLVM API
Here is a good tutorial on Writing an LLVM Pass as a starting point. Table 1 shows the data structures
in src/Alloca2Reg.cpp. You can add/modify/delete any structures in src/Alloca2Reg.cpp. We only
provide some structures which may be helpful for you to implement alloca2reg. You are recommended to
modify the structures for the open-ended design part.
Table 2 describes related LLVM APIs for alloca2reg.
Open-ended IR optimization design
In 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 above
You can create new source files for your optimizations OR implement it in Alloca2Reg.cpp. If creating
new files, you may modify src/CMakeLists.txt as an additional library object. You should provide your
command of generating IR bitcode when submitting.
1
Name Description
struct Alloca2RegPass Derived struct from llvm::FunctionPass.
Alloca2RegPass::ID = 0 Declares pass identifier used by LLVM to identify pass. This allows LLVM to
avoid using expensive C++ runtime information. LLVM uses ID’s address to
identify a pass, so the initialization value is not important.
Alloca2RegPass::TargetAllocas &
collectTargetAllocas()
Helps to collect all of the alloca instructions which can be removed. Please
look at step 1 from the lecture.
Alloca2RegPass::Post & Pre As mentioned in lecture, in step 2, they hold the representative value of the
variable 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 don’t need to worry about
it. You could check out the link here for more details.
Table 1: Data Structure Description
Name under namespace llvm Description
AllocaInst, StoreInst, LoadInst alloca, store, load instructions
PointerType* 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 and
deletes it.
BasicBlock::begin(), end() Instruction iterator methods
Function::begin(), end() Basic Block iterator methods
PHINode member functions You can search it for your implementation.
Table 2: LLVM API Description
Requirements
• 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 the
assignment 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 with
the -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 marks
for open-ended design will depend on your relative rank. Note that even the slowest implementation
that is functionally correct will receive a passing grade for this assignment.
Compilation and Testing
Please make sure you are using clang 11.0. After compiling your MiniC compiler, you can run:
2
# Under build/ directory
# Generate IR Bitcode
src/minicc -o output.bc
# Run Alloca2Reg pass
opt -O0 -load src/liballoca2reg.so --alloca2reg output.bc -o output_opt.bc
# Generate executable opt/non-opt files
clang output.bc minicio/libminicio.a -o output
clang 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.ll
llvm-dis output_opt.bc -o output_opt.ll
Public Autotester
We have provided a public autotester a6tester.zip on Quercus. After compiling your code, change
asst6.py to your minicc executable file path. Then simply run:
$./asst6.py
OR in verbose mode
$./asst6.py -v
The tester has several MiniC source files. Your compiler will compile the files and the generated executable
files will run without any errors in the tester. Then, compared to your unoptimized version, the tester simply
checks whether the number of alloca instructions were reduced. Finally, you can compare the runtime of
your solution and use the -O3 clang solution as your reference.
Deliverables
In the project folder, compress the whole project content as a zip file. This zip file must match the structure
of 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 due
date). On Markus, please submit:
• code.zip. We will directly unzip your submission, build it from source and run it against public and
private 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 don’t use any flag in the command. Your command is used
for testing your output program speed. Then put your explanation of optimization methods in a
newline.
• sample.c: A sample program which you think performs well under your optimizations. Its complexity
and its performance improvement will be considered for grading.
3
CSC 488 / CSC2107 Compilers and Interpreters Winter 2021
Assignment 6: LLVM IR Optimization (16%)
Due: April. 1, 2021
In 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 program
to test and determine the rest of your score (if you decide to do the resubmit).
LLVM IR Optimization Workflow in MiniC (cont’d from Assignment 5 Workflow)
After the MiniC compiler IR Bitcode is generated, PassManager in LLVM will chain multiple optimizations
and analysis passes to run together. Command opt is a LLVM tool that directly invoke a pass on a LLVM
IR bitcode. You will work on the src/Alloca2Reg.cpp source file. opt will do a function pass based on
Alloca2Reg library object on the IR bitcode.
alloca2reg Design
Please 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 Optimizes
a Function as your reference of the assignment.
alloca2reg Related Data Structures & LLVM API
Here is a good tutorial on Writing an LLVM Pass as a starting point. Table 1 shows the data structures
in src/Alloca2Reg.cpp. You can add/modify/delete any structures in src/Alloca2Reg.cpp. We only
provide some structures which may be helpful for you to implement alloca2reg. You are recommended to
modify the structures for the open-ended design part.
Table 2 describes related LLVM APIs for alloca2reg.
Open-ended IR optimization design
In 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 above
You can create new source files for your optimizations OR implement it in Alloca2Reg.cpp. If creating
new files, you may modify src/CMakeLists.txt as an additional library object. You should provide your
command of generating IR bitcode when submitting.
1
Name Description
struct Alloca2RegPass Derived struct from llvm::FunctionPass.
Alloca2RegPass::ID = 0 Declares pass identifier used by LLVM to identify pass. This allows LLVM to
avoid using expensive C++ runtime information. LLVM uses ID’s address to
identify a pass, so the initialization value is not important.
Alloca2RegPass::TargetAllocas &
collectTargetAllocas()
Helps to collect all of the alloca instructions which can be removed. Please
look at step 1 from the lecture.
Alloca2RegPass::Post & Pre As mentioned in lecture, in step 2, they hold the representative value of the
variable 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 don’t need to worry about
it. You could check out the link here for more details.
Table 1: Data Structure Description
Name under namespace llvm Description
AllocaInst, StoreInst, LoadInst alloca, store, load instructions
PointerType* 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 and
deletes it.
BasicBlock::begin(), end() Instruction iterator methods
Function::begin(), end() Basic Block iterator methods
PHINode member functions You can search it for your implementation.
Table 2: LLVM API Description
Requirements
• 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 the
assignment 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 with
the -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 marks
for open-ended design will depend on your relative rank. Note that even the slowest implementation
that is functionally correct will receive a passing grade for this assignment.
Compilation and Testing
Please make sure you are using clang 11.0. After compiling your MiniC compiler, you can run:
2
# Under build/ directory
# Generate IR Bitcode
src/minicc
# Run Alloca2Reg pass
opt -O0 -load src/liballoca2reg.so --alloca2reg output.bc -o output_opt.bc
# Generate executable opt/non-opt files
clang output.bc minicio/libminicio.a -o output
clang 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.ll
llvm-dis output_opt.bc -o output_opt.ll
Public Autotester
We have provided a public autotester a6tester.zip on Quercus. After compiling your code, change
asst6.py to your minicc executable file path. Then simply run:
$./asst6.py
OR in verbose mode
$./asst6.py -v
The tester has several MiniC source files. Your compiler will compile the files and the generated executable
files will run without any errors in the tester. Then, compared to your unoptimized version, the tester simply
checks whether the number of alloca instructions were reduced. Finally, you can compare the runtime of
your solution and use the -O3 clang solution as your reference.
Deliverables
In the project folder, compress the whole project content as a zip file. This zip file must match the structure
of 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 due
date). On Markus, please submit:
• code.zip. We will directly unzip your submission, build it from source and run it against public and
private 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 don’t use any flag in the command. Your command is used
for testing your output program speed. Then put your explanation of optimization methods in a
newline.
• sample.c: A sample program which you think performs well under your optimizations. Its complexity
and its performance improvement will be considered for grading.
3