[Sprint 3] Add OraclePass

[willi19]

Overview

Since most of the load, store are happening in for-loop, it would be efficient to move whole for loop with load and store to oracle function.

Implementation

1. Find valid loop
2. Look for operand that are defined outside of the loop and put it as argument
3. Generate oracle based on 2.
4. Copy loop into oracle function
5. Operand of copied instruction of loop is from the orignal. So convert to copied one
6. Change branch that enter original for loop to call oracle & branch to end of the loop
7. Remove original for loop

Unit tests

test01.ll => No optimization, oracle function cannot have call or longer than 50 lines. Every loop satisfy this cond so no optimization happen test02.ll => Should optimize test03.ll => No optimization, cause there are no loop with load or store. There is a loop without load and store so this should not move to oracle

Performance

matmul1 input5-cost.log 0.4896418882319951 matmul1 input7-cost.log 0.4837628832882261 matmul1 input2-cost.log 0.6464572007739795 matmul1 input4-cost.log 0.4944946818415051 matmul1 input6-cost.log 0.4852459861421685 matmul1 input3-cost.log 0.5316552923804262 matmul1 input8-cost.log 0.4896418882319951 matmul1 input1-cost.log 0.9501661129568106 merge_sort input5-cost.log 1.007393296828535 merge_sort input2-cost.log 1.0103473191036867 merge_sort input4-cost.log 1.007911601404685 merge_sort input6-cost.log 1.0044103812310001 merge_sort input3-cost.log 1.0045544700155222 merge_sort input1-cost.log 1.0162365675739273 bubble_sort input5-cost.log 0.40557775429398185 bubble_sort input7-cost.log 0.3933638405582217 bubble_sort input2-cost.log 0.40616183171591236 bubble_sort input6-cost.log 0.3967040554817657 bubble_sort input3-cost.log 0.39441221417262123 bubble_sort input1-cost.log 0.510891903000411 radix_sort input5-cost.log 0.8863374299649541 radix_sort input2-cost.log 0.8944562427013684 radix_sort input4-cost.log 0.8893038511097177 radix_sort input6-cost.log 0.8848540589566496 radix_sort input3-cost.log 0.8907462332964294 radix_sort input1-cost.log 0.9281306715063521 friend input50-cost.log 0.9488636363636364 friend input19-cost.log 0.950415864301225 friend input5-cost.log 0.9321676213445885 friend input13-cost.log 0.951937984496124 friend input15-cost.log 0.9398522687302145 friend input22-cost.log 0.9503847169185514 friend input46-cost.log 0.9223552547675103 friend input21-cost.log 0.9503883289261408 friend input70-cost.log 0.9397963564491174 friend input38-cost.log 0.9223492534993567 friend input7-cost.log 0.9363147466742145 friend input11-cost.log 0.9393530997304582 friend input40-cost.log 0.9226186446415273 friend input28-cost.log 0.9409460611506647 friend input66-cost.log 0.9389764790468365 friend input72-cost.log 0.9397597605336137 friend input68-cost.log 0.9488636363636364 friend input62-cost.log 0.9387815118013848 friend input2-cost.log 0.9392838609237156 friend input10-cost.log 0.9393530997304582 friend input35-cost.log 0.9409645722633929 friend input37-cost.log 0.9409256783610941 friend input16-cost.log 0.9474243228890069 friend input71-cost.log 0.9397593645752761 friend input42-cost.log 0.9321676213445885 friend input47-cost.log 0.9225987113378705 friend input25-cost.log 0.9503864803879207 friend input41-cost.log 0.9223509114854919 friend input57-cost.log 0.9381903257761726 friend input60-cost.log 0.9380228247226716 friend input36-cost.log 0.9411475697490788 friend input4-cost.log 0.9392838609237156 friend input51-cost.log 0.9568743088831552 friend input67-cost.log 0.9387344238617241 friend input6-cost.log 0.9321676213445885 friend input3-cost.log 0.9392838609237156 friend input17-cost.log 0.9461312438785504 friend input18-cost.log 0.950456553162128 friend input34-cost.log 0.9409912102384974 friend input20-cost.log 0.9504078578408706 friend input64-cost.log 0.9385296127606125 friend input63-cost.log 0.9392869626004894 friend input30-cost.log 0.9411151342927858 friend input26-cost.log 0.9503927049013944 friend input8-cost.log 0.935326842837274 friend input23-cost.log 0.9504058685847538 friend input39-cost.log 0.9223492534993567 friend input48-cost.log 0.9223537423330291 friend input32-cost.log 0.9409111163227016 friend input52-cost.log 0.9495689655172413 friend input49-cost.log 0.9612307692307692 friend input54-cost.log 0.9321676213445885 friend input1-cost.log 0.9488636363636364 friend input65-cost.log 0.9378347899633493 friend input31-cost.log 0.9409192928815903 friend input14-cost.log 0.9457439112611526 friend input29-cost.log 0.9409132006709909 friend input33-cost.log 0.9421981458728917 friend input27-cost.log 0.9503838800716171 friend input56-cost.log 0.9503838800716171 friend input24-cost.log 0.9504015551257105 friend input69-cost.log 0.9397816175543936 friend input44-cost.log 0.9224107048084067 friend input53-cost.log 0.9495689655172413 friend input58-cost.log 0.9384008160007096 friend input12-cost.log 0.9488636363636364 friend input9-cost.log 0.9366628830874006 friend input43-cost.log 0.9224415553435115 friend input45-cost.log 0.9223529083346516 friend input55-cost.log 0.9393530997304582 friend input61-cost.log 0.9392242425468226 friend input59-cost.log 0.938806813366854 wall input5-cost.log 0.9959790299905367 wall input7-cost.log 0.9776315789473684 wall input2-cost.log 0.9999904197582905 wall input4-cost.log 0.9969183466355357 wall input6-cost.log 0.9959925909294671 wall input3-cost.log 0.9995462272952524 wall input8-cost.log 0.9776315789473684 wall input1-cost.log 0.9776315789473684 wall input9-cost.log 0.9991258395782225 game input5-cost.log 0.9876399201417708 game input7-cost.log 0.9964453721770961 game input11-cost.log 0.9998447997931414 game input2-cost.log 0.9999113231344745 game input10-cost.log 0.9996541039219969 game input4-cost.log 0.9972315452149345 game input6-cost.log 0.9998965934776195 game input3-cost.log 0.9999059192179035 game input8-cost.log 0.9976775672764288 game input1-cost.log 1.000405165864776 game input12-cost.log 0.9960600172711571 game input9-cost.log 0.9998782699486503

[sharaelong]

Did you check if the number of outer operand exceeds 16, maximum number of function argument?

[germanium32]

Some additional features might be beneficial or either mandatory:

1. Check priority between loops
2. (For other passes) Modify some interactions regarding oracle: such as increasing instruction count / adding function call

[willi19]

Some additional features might be beneficial or either mandatory:

1. Check priority between loops
2. (For other passes) Modify some interactions regarding oracle: such as increasing instruction count / adding function call

We will work for this in wrap-up! Currently this is my thought of evaluating loop

1) Depth : nested loop have probability to run n times more than just loop. So for program with big input, it is very efficient to select nested loop. Taking inner loop might seem inefficient due to overhead of calling oracle. However number of oracle is propotional to n while total load or store instruction is propotional to n**2. So the most prior should be on selecting nested loop with most depth. Also we need to check loop runs constant time. 2) Number of load or store. 3) Overhead - storing returning values.

I think the biggest numer of loops that can be in oracle function is 2. Since we should add instruction to guide which loop to select and basic block for end of the loop and most loop have length more than 15 so it is very unlikely three loop can go inside the loop. So we need to find 2 loop that can maximize 1), 2) and 3)

Also we need to optimize the loop that register is used outside. We need to return those value or store and load it.

[willi19]

Did you check if the number of outer operand exceeds 16, maximum number of function argument?

Fixed it.