[Sprint 1] Arithmetic pass

[willi19]

Overview

Change five instruction that works the same but have higher cost to the ones with lower cost.

add x x -> mul x 2 shl x c -> mul x (1<<c) ashr x c -> sdiv x (1<<c) lshr x c -> udiv x (1<<c) and x (2^c-1) -> urem x (1<<c)

Implementation

Check each instructions whether it matches the above cases. Except And, change each instruction to matching the one. For And instruction, first check whether constant has the form (2^c-1). If this matches and the size of mask covers the entire size of instruction, than convert instruction to the value\ ex) %y = AND i8 %x 255 => change %y to %x in the same block Or if constant equals to 0, change the instruction to zero value. Otherwise change AND operation to UREM.

Unit tests

First test: Check first four instruction was changed properly. Check it works well with the constant. Then check if it doesn't change the instruction if there are no constant value.

Second test: Check whether compiler changes and instruction properly. Check it works for different input size. (getting sextvalue from i1 change the value so I took care of that case) Check it works for changing instructions to value. Check it does not change instruction when value are not (2^c-1) form Check it does not change instruction when two operands are not constant.

Third test : Merge first and second case with branch to check it works for different basic blocks.

[sharaelong]

Code Review:

1. Variable naming convention is not consistent. For example, in ArithmeticPass.cpp, you used snake_case for auto tmp_itr, but PascalCase in ConstantInt* ConstOp. Also vector ADD, Shl, AShr, ... which types are vector<Instruction *> has all different naming rules. IMO since our project skeleton (and practice session) using PascalCase as far as I remember, our code needs to use PascalCase.
2. Indentation and Bracing is not consistent. For example in line 13 of ArithmeticPass.cpp, if statement has no curly brace for their body. I know it only contains a single body line, but I think it is more good to use curly brace in our project. Also please insert proper spacing to avoid something like this: if(blabla), for(blabla). Not just after keyword, but some mathematical expression needs space too. In BinaryOperator::Create usage, space needed for third arguments. In Line 31, if (cons == UINT64_MAX || (cons & (cons + 1)) == 0) is easier to read. Not important but please remove space in line 65, 74 between variable declaration, and every dyn_cast<ConstantInt> () expression too.
3. I'm not sure about this, but your Value* FirstOp in line 11 is exists for same reason of subsequent Value* FirstOperand variable in processing mul or udiv. So making this variable name all same will increase readability.
4. Comment in line 7, I can't understand its meaning shortly. Please replace name of function like ReplaceInstWithValue() for indicating real name.
5. I hope increasing itr inside of for loop is not a good pattern. Maybe you don't use increased itr inside a for loop, right? How about moving this logic to top line of for loop?

[sharaelong]

From here, it's just my personal opinion:

1. Starting comments with no space is maybe not good for readability. Also I hope you to change Case five to Case 5, and so on. Also in plain text we don't need to capitalize instruction name.
2. Is there any needs for #include <cassert>? If not, remove it from header.
3. Also if using namespace llvm::PatternMatch is maybe unnecessary since we already do using namespace llvm to clarify the codes.

I found a one thing more after above comment: redundant semicolon in line 30 =(

[willi19]

Code Review:

Code Review:

1. Variable naming convention is not consistent. For example, in ArithmeticPass.cpp, you used snake_case for auto tmp_itr, but PascalCase in ConstantInt* ConstOp. Also vector ADD, Shl, AShr, ... which types are vector<Instruction *> has all different naming rules. IMO since our project skeleton (and practice session) using PascalCase as far as I remember, our code needs to use PascalCase.
2. Indentation and Bracing is not consistent. For example in line 13 of ArithmeticPass.cpp, if statement has no curly brace for their body. I know it only contains a single body line, but I think it is more good to use curly brace in our project. Also please insert proper spacing to avoid something like this: if(blabla), for(blabla). Not just after keyword, but some mathematical expression needs space too. In BinaryOperator::Create usage, space needed for third arguments. In Line 31, if (cons == UINT64_MAX || (cons & (cons + 1)) == 0) is easier to read. Not important but please remove space in line 65, 74 between variable declaration, and every dyn_cast<ConstantInt> () expression too.
3. I'm not sure about this, but your Value* FirstOp in line 11 is exists for same reason of subsequent Value* FirstOperand variable in processing mul or udiv. So making this variable name all same will increase readability.
4. Comment in line 7, I can't understand its meaning shortly. Please replace name of function like ReplaceInstWithValue() for indicating real name.
5. I hope increasing itr inside of for loop is not a good pattern. Maybe you don't use increased itr inside a for loop, right? How about moving this logic to top line of for loop?

1. Fixed
2. Fixed
3. Fixed
4. Fixed
5. You mean increase itr in the condition of for loop?

[willi19]

From here, it's just my personal opinion:

1. Starting comments with no space is maybe not good for readability. Also I hope you to change Case five to Case 5, and so on. Also in plain text we don't need to capitalize instruction name.
2. Is there any needs for #include <cassert>? If not, remove it from header.
3. Also if using namespace llvm::PatternMatch is maybe unnecessary since we already do using namespace llvm to clarify the codes.

I found a one thing more after above comment: redundant semicolon in line 30 =(

1. Fixed
2. I removed it
3. Without this, we need to add PatternMatch:: to almost every variable starting with m_ So I think it would be better to use namespace of llvm::PatternMatch