Standard Oil Group Page


This is the project page for the Standard Oil Group for the CSC255 compiler competition. Our group consists of Ian Christopher, Dennis Huo, Eric Bluestein and Ryan Schmitt. We are using the Ruby track (urcc).

First Meeting

  • Decided on a name and track to follow
  • Looked over control flow graph code to use
  • Assigned optimizations to different people
  • SVN chosen as a version control

Subversion set up

Notes and Requests

  • For constant prop, delete "if (3 < 0 ) goto L1" and "if (3 > 0 ) goto L1" in to "goto L1" (get rid of goto after?)
  • For function inlining, watch out for recursion
  • 4/3 Thanks to MASHS, we have dynamic counting.
  • 4/8 printf-printf optimization added. Helps with tax.c
  • children_copy is a copy - if you are deleting or adding things beware because this is our only connection to the children of a node.

Requests regarding style

  • Indentation: tabs should be used for this, and not spaces. A principal advantage of this is that we can all use one tab per level of indentation, and then individually specify our respective editors' tab widths according to our preferences.
  • Function length: Ideally, a function in its entirety should fit into a single screen. This makes it easier to read the code and helps keep the complexity of any given region of code manageable. I saw one function that was 170 lines long; this makes it very difficult to get a sense, at a glance, of everything the function is responsible for, which variables it declares, etc.
  • Logic: Some of the if-statements I've seen are hundreds of characters long, which makes it very difficult to tell what that statement is deciding and whether it's written correctly; complicated conditionals can give rise to a plurality of subtle bugs. Breaking them up into multiple lines helps, but it's often best to assign the logic to a separate boolean function with an informative name.
  • Names: I'm seeing mixtures of camelCase and names_with_underscores. It appears that camelCase is fashionable these days, and is standard in things like .NET, but honestly I fucking hate it and I read somewhere that they did a study showing that camelCase is harder to read. It might be best to just use one or the other, at least within any given function (since I'm seeing both conventions used within the same scope).

Loop Unrolling

Checked in code that completely unrolls simple loops (loop body only has one basic block) where the induction variable and number of iterations can be determined statically. If the following conditions are met, the loop should be identified and unrolled completely, otherwise the loop should be unmodified:

  • the control condition of the loop has exactly 1 induction variable, which is compared to a constant (assuming rolling will be run AFTER constant propagation.)
  • the induction variable is initialized to some constant in the block preceding the loop control
  • the induction variable is assigned to exactly once during the loop, and the algorithm is able to determine how it is modified during this assignment (addition or subtraction of any constant, or multiplication or division by any constant)

In addition, if none of the operations inside the loop use the loop index, it is not necessary to increment it between each copy of the loop body inserted during unrolling. Instead, the loop index is updated once at the very end of the unrolled loop so that it contains the value it would have contained if the loop were actually executed before control proceeds past the loop.

CFG optimizer (V1)

  • Based on simple patterns in the control flow graph, try to make the cfg the best it can be. Basics done on 4/2
  • More documentation to follow, but it seems robust enough. Needs to be run with Value numbering iteratively - CFGopt can get ride of if statements, so less dependences.
  • Hopefully, I will find some way to get ride of unnecessary loops in the future
  • Im curious about the improvement. Code that cant be reached should be deleted and overall fewer jumps --> better execution time, but we dont care about that. Additionally, (apparently) we dont count labels/goto statements. Still helps with removing unnecessary if-statements, etc.
  • Try this for an example:
int main(){
        int a, b, c, d, e, f;

        a = 0;
        b = 1;
        c = 2;
        d = 3;
        e = 4;
        f = 5;
        a = a + 1;
        b = a * b;
        if( b > 0 ){
                c = b;
        printf("ANSWER: %d\n", d);

CFG optimizer (V2)

  • More robustness, and a few more special cases dealt with. Tested on all the public cases.
  • Seems to remove a substantial number of gotos and labels. Basically, this help the execution runtime but because we dont count the dynamic number of labels or gotos, it only has minimal effects on our count-based evaluation.

Value Numbering

  • To take advantage of dead code elimination, aggressive value numbering is being applied.
  • The key to eliminating redundant code is to propagate value numbers into return, conditional, and call statements.
  • Call statements include the rhs of assign statements as well as lone expr_stmts.
  • In general, we cannot assign call statements to the same value number, even if they are called with the same value number parameters and are deterministic, due to the existance of global "state". A hack to get around this is to add a tag to completely quarantined functions, where global variables don't appear within; any fully "deterministic" functions can be value numbered in the same way as OpExprs.

Dead Loop Elimination

  • After standard dead code elimination, loops remain due to having their induction variable in the body, marked "absolutely useful" due to being present in the loop condition
  • Using two-phase "usefulness propagation", an initial usefulness pass is made using an initial worklist of only returns, global assignments, and function calls (no conditionals). Then, the CFG is searched for single-path loops possessing no useful statements within their body; if such a loop is found, the conditional is not added to the worklist. In the re-propagation from the useful conditionals, the loop induction variables are left out, and are safely eliminated if they cannot escape through other means.

Function Inlining

  • Aggressive function inlining is used to save the extra function-call and return statement, as well as to allow potential value-number propagation into the loop body.
  • Since extended basic blocks are used, local value numbers are effectively imported into the body of inlined functions, allowing significant dead code elimination.
  • Inlining parameterized function calls initially increases the statement count, since each parameter must be copied explicitly into temporary variables. Dead code elimination in subsequent passes eliminates the extra copy assignments.

Sources of Bugs

  • Almost all bugs to date are either due to not checking the type of node, or comparing a c_dump to a variable name
  • Array references can be broken due to using c_dump, since it prints the full "V[i_0]", which isn't found when the statement is searched by array name or with an alias of the index, such as "V[i_2]" or "V".
  • If the usage of "c_dump" is encountered or the idion func.each do |block|, we should strive to verify the c_dump works correctly, and add a check for "block.is_a?(Ast::Block)" before continuing

Advanced Value Numbering

  • Support for array value numbering has been added.
  • Due to the contest rules, disallowing <array> = <array> or func_call(<array>) or return <array>, a "special" set of array value numbers is maintained alongside standard ones.
  • Normally, in the assignment "a = b", we set the value number replacement as the RHS, so that dead code can likely eliminate "a" by short circuiting all future usages to the original value number, found in "b". However, if we have "a = V[i]", we would like to always use "V[i]" as the replacement, but we aren't allowed to propagate this array access into function calls, array-assignments, or return statements. Thus, we record "V[i]" in the "special" aliases, and force function calls, etc., to use the LHS, while allowing assignment statements innto variable accesses to replace the RHS with the special "V[i]". Thus, if the copy-out from the array was not used for a function call, return statement, or array-copy, the temporary LHS in the original can be eliminated by DCE.
  • Although it is counterintuitive to replace equivalent value numbers with the longer "expression statement" rather than the lhs variable access, it allows DCE to find unnecessary temporary variables;

a = b + c

d = a

e = d


Generates a def-use chain which claims all statements are useful. However, if we replace value numbers with the RHS,

a = b + c

d = b + c

e = b + c


Then DCE eliminates all but the last two statements. Again, RHS OpExpr values are treated as "special" in the same way RHS array accesses are.

Pseudo-Dominator Blocks

  • Although it was not feasible to spend time converting the code into SSA form, the framework for building dominator blocks was already in place.
  • The only reason SSA is needed is due to phi functions for value numbers killed in predecessors between the current block and its immediate dominator
  • We can simply ignore killed value numbers, but still import all "untouched" value numbers from the block's immediate dominator

Array Bug in Dead Code Elimination

  • Allowing dead code elimination to eliminate arrays proved difficult, since any array access may potentially use any array definition, if the indices are not known statically. However, it was out of the question to mark all array usages as "absolutely useful", since this would prevent the dead loops in multiply.c from being removed.
  • In the majority of cases, limiting array def-use chains to the "last" array-write was able to pass the test cases. However, once aggressive inlining and loop unrolling techniques were used, array initializations often had the form of several consecutive array assignments, with the actual def-use chains difficult to determine.
  • The solution was to apply a third "use-propagation" phase, after I/O and function propagation, but before conditional-goto propagation. An initial pass is made to propagate usefullness only from I/O and function calls. Then, a pass-through is made to determine which arrays are used in those statements. As a heuristic, any array access in an absolutely useful statement renders ALL writes into that array absolutely useful.

Secondary Loop Unrolling

  • To aid in the cases of simple loops, a second loop unrolling technique has been implemented, where loops are unrolled linearly from the beginning of the induction variable. The loop body remains intact, but the induction variable is initialized just beyond a fixed unrolling point, and the loop body is copied and inserted before the induction variable initialization.
  • The loop is unrolled incrementally in each pass, to allow DCE and constant propagation between passes. For each copied out section, range checks are eliminated and any references to the induction variable are turned into NumConsts. In particular, in cases such as:

for(i = 0; i < 10; i++)

a[i] = i*512;

The loop body would normally require a temporary variable, since the RHS is an OpExpr involving a VarAcc and a NumConst. When unrolled, after further constant propagation, the RHS expression is collapsed into a NumConst, allowing the temporary variable to be eliminated, and the code to transform into

a[0] = 512;

a[1] = 1024;


  • Unsatisfiable loop ranges are eliminated in subsequent passes.


-- IanChristopher - 27 Mar 2009

Edit | Attach | Watch | Print version | History: r15 < r14 < r13 < r12 < r11 | Backlinks | Raw View | Raw edit | More topic actions...
Topic revision: r13 - 2009-04-12 - DennisHuo
  • 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