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:

    • Node

    Time close: 5:00AM

080411

  • Time open: 800PM

    Developers: Chetan, Stan

    Tasks:

    • Merge code

    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:

    • Fix bugs in defuse

    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:

      None

    Time close: 630PM

080405

  • Time open: 900PM

    Developers: Stan

    Tasks:

    • Fix bugs in defuse

    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:

    • Fix bugs in defuse

    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:

    • None.

    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:

    • Code Merge

    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:

    • None. Booyeah.

    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:

    • None.

    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:

    • None

    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

Edit | Attach | Watch | Print version | History: r36 < r35 < r34 < r33 < r32 | Backlinks | Raw View | Raw edit | More topic actions...
Topic revision: r35 - 2008-04-13 - StanPark
 
  • Edit
  • Attach
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2017 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding URCS? Send feedback