CSC455 - Compilers
Team: Peanut Butter Tortoise
"Slow and steady wins the race."
Team Members : Roles
- Chetan Bhole : Team Lead, Developer, Tester
- Stan Park : Developer, Integrator, Tester, Reporter
- Amal Fahad : Developer, GCC Guru
Project Vision
- Eat peanut butter.
- Beat hare.
Project Plan
Performance is secondary. The main goal is to try to have correct code.
The following is the current tentative plan:
- Decide how we will fuse the code created by different team members.
- Find bugs that were present in the system.
- Rectify bugs.
- Brainstorm for ideas for improving performance of the system.
Session Summaries
080412
-
Time open: 1:00AM
Developers: Chetan
Tasks:
- Finish the case for multiply
- Remove bug for passing variable as index in array
Change log:
- Finished the code for multiply like cases that don't have any printfs in the code
- Removed bug for passing variables in array (wasn't condiering PARM_DECL)
Open issues:
Time close: 5:00AM
080411
-
Time open: 800PM
Developers: Chetan, Stan
Tasks:
Change log:
- Merged branches in merge_output()
- Merged Chetan's rem_red_code() pass. Currently not working.
Open issues:
- rem_red_code() doesn't alter the CFG as expected.
- num_uses now returns incorrect value. For Chetan's value numbering, the use_stmt must have exactly one parent with exactly one use for the propagation to be correct. Modify num_uses to return this information. Possibly add a function num_parents.
Time close: 1000PM
-
Time open: 350PM
Developers: Stan
Tasks:
- Simplify type-casting stmts
Change log:
- Added function simple_cast():
- Combines statements of the form "a.0 = a; a.1 = (cast) a.0;" to "a.1 = (cast) a;"
Open issues:
- num_uses now returns incorrect value. For Chetan's value numbering, the use_stmt must have exactly one parent with exactly one use for the propagation to be correct. Modify num_uses to return this information. Possibly add a function num_parents.
Time close: 442PM
080409
-
Time open: 200PM
Developers: Chetan, Stan
Tasks:
- Fix bugs in defuse
- Finish builtin_puts merge
Change log:
- In merge_output():
- Finished merging for output sequences of only builtin_puts
- In find_uses():
- Stmt of the format "x = fn()" are initially marked.
Open issues:
- Some function calls are now doubled since dead code marks extra stmts. Chetan needs to remove these himself when doing value numbering.
- num_uses now returns incorrect value. For Chetan's value numbering, the use_stmt must have exactly one parent with exactly one use for the propagation to be correct. Modify num_uses to return this information. Possibly add a function num_parents.
Time close: 322PM
080408
-
Time open: 800PM
Developers: Stan
Tasks:
Change log:
- In find_uses():
- Added TREE_CODE checks for relational ops and logical ops in a MODIFY_EXPR. Should fix case of infinite loop.
- Added function merge_output() to merge builtin_puts and printf. NOT WORKING.
Open issues: - merge_output() causes internal compiler fault.
- num_uses now returns incorrect value. For Chetan's value numbering, the use_stmt must have exactly one parent with exactly one use for the propagation to be correct. Modify num_uses to return this information. Possibly add a function num_parents.
Time close: 1038PM
-
Time open: 600PM
Developers: Chetan
Tasks:
- Make sure code is legal and add array optimizations
Change log:
- Removed possible areas where arrays are propagated which will make the code illegal.
- Added code to allow passing variables in global array indices.
Open issues:
Time close: 630PM
080405
-
Time open: 900PM
Developers: Stan
Tasks:
Change log:
- In find_uses():
- Due to variable propagation, array references can be found in an IF condition. find_uses doesn't check for array in a COND_EXPR. Fixed.
- Added handling for VAR_DECL instead of a relational expression in COND_EXPR
- Commented out Amal's const prop into COND_EXPRs sicne it seems to be causing some problems.
Open issues: - num_uses now returns incorrect value. For Chetan's value numbering, the use_stmt must have exactly one parent with exactly one use for the propagation to be correct. Modify num_uses to return this information. Possibly add a function num_parents.
Time close: 1021PM
080404
-
Time open: 800PM
Developers: Stan
Tasks:
Change log:
- Added #define BUF 100 for Amal's char arrays.
- In find_uses():
- Added finer grained defuse for arrays in MODIFY_EXPR case
- Doesn't immediately add defining block to path list anymore. If a block is its own successor, we want to reiterate through it to catch uses before the def (loops). This resolves a case of an infinite loop.
Open issues: - num_uses now returns incorrect value. For Chetan's value numbering, the use_stmt must have exactly one parent with exactly one use for the propagation to be correct. Modify num_uses to return this information. Possibly add a function num_parents.
Time close: 1051PM
-
Time open: 700PM
Attendees: Amal, Chetan, Stan
Minute taker: Stan
Agenda:
- Discuss open issues
- Results from hidden benchmarks
Discussion: - Infinite loop on hidden test case may be from deleting a var that is used repeatedly in a loop
Conclusions: - Should implement but currently low priority: merging output stmts
Open issues: - Unable to reproduce internal compiler error and runtime seg fault.
Time close: 800PM
-
Time: 300AM
Developers: Amal
Tasks:
- Generate Gimple code revision
Change log:
Open issues:
- Sort insertion:
- handle cases like i.0= i; x= arr[i.0] this is appear like 6 times in the insertsort function
- Tax
- D.1234 =line1+line2; printf (" ",D1.1234 ) is it easy to handle though ?
- d = 7350; again d=7350; should be removed although these two statements appeared in two different blocks .
- Trivia :
- x/1 should be handled, what about x+0, x-0, x*1 is it already handled by the compiler or not
- cases like a.0/a.0 converted to a/a , but that didn't change to 1, other cases where we have c/c was converted correctly to 1
- c= 500+500 should be folded, where the statement was c+500
Time close: ?
-- Adjusted formatting.
StanPark - 04 Apr 2008
080401
-
Time: 900PM
Attendees/Developers: Amal, Chetan, Stan
Minute taker: Stan
Agenda:
Discussion/Change log:
- Merged
- Made minor change to initialization of "main_bb_extension". Was causing seg fault when run with the other passes
Conclusions: - automaton 100
- binrep 73
- fibonacci 1068
- jacobi 11511837
- mandel 6259678
- moving edge 1309
- multiply 152
- sort 10974
- sort_insertion 2913
- tax 135
- trivia 49
Open issues:
Time close: 1002PM
080330
-
Time open: 1000PM
Developers:Chetan
Tasks:
- Correct more bugs in value numbering
- Remove chain effects
- Look into combining _buildin_puts and printf
Change log:
- Corrected the value numbering to work properly and optimize to handle constants.
- Added code in the value numbering to propagate variables on the condition that atleast one of the statements in of the type x=y or return(x).
Open issues:
- Still need to use Stan's defuse_count to propagate functions and binary operator expressions used only once.
- Still need to look into _buildin_puts and printf.
Time close: 1030PM
-
Time open: 900PM
Developer: Amal
Constant propagation part:
the code I have now is able to:
-
propagate constant within a block
- propagate a constant between continuous blocks as long as it appears in the set of all previous blocks of our block, and being assigned the same value in all, and not being killed in any of them
- also check if any of the function arguments might be substituted with a constant.
- handle a case:
- b=10;
- c=5;
- a=b+c;
the code I have will generate a=10 and add a to the set of the constant list , and the const_propagation function will be called again just in case a occur some where else later and can be substitute again by 10.
what I need handle also :
- handle the global variable
- and check the code on the different open test cases
-
Time open: 840PM
Developers:Stan
Tasks:
- Modify defuse construction to add information about number of uses
- Add pass to fold "a & 1" and "a/a"
- Write specific test cases to exercise the passes.
Change log:
- Added "static int num_defuses(defuse_list_t *defuse_list, tree used)": Given a stmt "used", which is assumed to be of the form "x = a", returns the number of uses of "a"
- Added "static void mega_fold(void)": Pass to handle folding for "a/a", "a&1", "1&a", "a%a". All code for manipulation is in place but only "&" works.
Open issues: - Cannot currently determine the type of the operands in "/" and "%" so the folding isn't carried out.
Time close: 1050PM
-
Time open: 745PM
Attendees: Amal, Chetan, Stan
Minute taker: Stan
Agenda:
- Discuss current status of const prop and VN
- Identify some cases for further optimatization
Discussion: - GCC will fold binary exprs involving 0 and 1 except for "a & 1" and "a/a"
- VN for individual variables, more like propagation for particular variables
Conclusions: - AI[4] for Stan: Add a pass to handle "a & 1" and "a/a"
- AI[5] for Stan: Modify defuse construction to include information needed by Chetan's variable propagation.
Open issues: - VN isn't handling both operands of a binary expr
Time close: 834PM
080329
-
Time open: 940PM
Developers: Stan
Tasks:
- Add optimization pass to remove stmts of the format "x=x" which are generated by VN but not removed by dead code elimination.
Change log:
- Added pass "self_assign()" which removes stmts of the format "x=x"
Open issues:
Time close: 945PM
-
Time: 700PM
Attendees: Amal, Chetan, Stan
Minute taker: Stan
Agenda:
- Go over pre-pass gimple code to look for missed optimizations.
Discussion:
- Constant prop is not folding stmts
- Unary ops not handled in VN
- AI[1] complete. Benchmark results posted earlier.
Conclusions:
- AI[2] for ALL: fix bugs in current optimizations
- AI[3] for Stan: develop comprehensive test program to try to exercise the optimizations.
Open issues:
- DVN or SVN?
- Additional optimizations?
- Need more peanut butter.
Time close: 749PM
-
Time open: 300PM
Developers: Stan
Tasks:
- Merge updated VN and const prop
- Make defuse and dead code marking more intelligent for arrays
- Recheck some benchmarks
Change log:
- Updated Chetan's VN
- Updated Amal's const prop
- Modified find_uses():
- When checking for the uses of an array, added comparison for base array equality
- Made function calls a def kill for globals
- Made function call with pass-by-ref a def kill
- Modified defuse_list_el_t:
- Added "int global" flag
- Added "int array" flag
- Modified dead_code_elim:
- Removed auto-marking for array accesses
- Added marking for global defs
- trivia benchmark count: 76 -> 73
Open issues: - jacobi, multiply, and sort benchmarks are unchanged
Time close: 416PM
-- StanPark - 29 Mar 2008
080328
-
Time open: 500PM
Developers: Chetan
Change log:
- Corrected value numbering to take care of global variables.
- Removed a bug to now detect constants in the modify expression.
- Created gimple output files for the given open test cases to analyse for optimization
Open issues: - Will we need to take care of value numbering for functions other than printf and scanf for the test cases?
Time close: 515PM
-- ChetanBhole - 28 Mar 2008
080326
-
Time open: 800PM
Developers: Chetan, Stan
Tasks:
- Merge code for open benchmarking.
Change log:
- Added Chetan's value numbering to Stan's. Due to bugs, benchmarks were produced using only Stan's code.
Open issues: - Chetan has unresolved bugs in value numbering.
Time close: 831PM
-- StanPark - 26 Mar 2008
-
Time open: 700PM
Attendees: Amal, Chetan, Stan
Minute taker: Stan
Agenda:
- Code merge for initial benchmarks
Discussion: - Use of VEC or linked lists.
- Use of global structures for holding data flow information
Conclusions:
- AI[1] for Stan, Chetan: For initial benchmarking, use Stan's dead code and constant prop and Chetan's value numbering as well as running Stan's and Chetan's code bases separately.
- Amal will try VEC but has Stan's code for linked lists if necessary.
- Try to keep each pass as independent as possible for debugging purposes, so each pass will keep its own bookkeeping structures.
- AI[2] for ALL: Fix bugs in all passes.
Open issues:
- DVN or SVN?
- Fix bugs in all passes.
- Additional optimizations?
- Need more peanut butter.
Time close: 751PM
080325
-
Time open: 630PM
Attendees: Chetan, Amal, Stan
Minute taker: Stan
Agenda:
- Who has working optimizations
- Code merging
Discussion: - Chetan has value numbering. Bugs:
- Doesn't include initial constants
- Globals
- Function parameters
- Amal has constant prop. Bugs:
- Constants only propagate from the immediate predecessor
- Stan has dead code elimination. Bugs:
- Immediately marks array accesses
Conclusions:
Open issues:
- DVN or SVN?
- Fix bugs in all passes.
- Additional optimizations?
- Need more peanut butter.
Time close: 706PM
-- StanPark - 25 Mar 2008
080324
Tag and Naushad stole our idea of having a motto. And they may claim that we will claim that it is stolen. --
StanPark - 24 Mar 2008
080323
Made this wiki page today. --
StanPark - 23 Mar 2008
Topic revision: r36 - 18 Apr 2008 - 01:45:18 -
StanPark