[Sprint 3] Add IncrDecrPass

[germanium32]

Overview

Implement IncrDecrPass, which is an improvement of ArithmeticPass, implemented by Mingi Choi. The IncrDecrPass optimizes the following simple additions to a new given instruction, incr and decr.

1. add %a n -> incr %a n times
2. sub %a n -> decr %a n times
3. add %a -n -> decr %a n times
4. sub %a -n -> incr %a n times

Dependencies of instruction values should be adjusted. Since add/sub costs are 5, whereas incr/decr costs are 1, if a add/sub instruction has a operand with absolute value less than 5, we can optimize it into iterated incr/decr instructions. Expected to work well on loops, since canonical loop structures have an induction variable incremented by 1 each iteration. e.g. %idx = add %i, 1 -> %idx = incr %i

Implementation

First iterate over a basic block, and find all instructions that can be optimized. Detect all patterns with add/sub op0, const, and remind that add is commutative, so check for both operands. Save all optimizable instructions in a container. Iterate over such instructions and replace it with iterated incr/decr instructions. Replace all uses of the original instruction with the lastmost incr/decr instruction, then remove the original instruction.

Iterating step and replacement step are separated, since replacing during iterations resulted in segmentation errors; changing instructions of the BB inside the loop for(Instruction &I : BB) was harmful.

Unit tests (incrdecr/test0*.ll)

1. add %a, 1 and sub %b 2 -> Must optimize
2. sub %a, -3 and add %b -4 -> Must optimize
3. add %a, 5 and sub %b 6 -> Must not optimize
4. add 2, %a and sub 2, %b -> Must optimize the first, Must not optimize the second
5. Same as 4., but in oracle -> Must not optimize(maybe up to now)

[germanium32]

It shows that FileChecks passed; but operation time shows as 0.00s.

I'm not sure that FileChecks are fully operated; although my tests are fairly short. Also, I have checked that FileChecks passed in my local environment.

Can I treat it as success? :)

[sharaelong]

I'm not sure that FileChecks are fully operated; although my tests are fairly short. Also, I have checked that FileChecks passed in my local environment.

Can I treat it as success? :)

Yes I think so =)

[sharaelong]

LGTM!

[willi19]

LGTM But I think codes that check the type of instruction and generate the function can be improved by removing unneccesary copies