########################################
#Written by David Tam, 1999.           #
#davidkftam@netscape.net Copyright 1999#
########################################

                  ECE 540S Optimizing Compilers Assignment 3
                  ==========================================

    The first optimization to be implemented was copy propagation. This was
chosen because it was the easiest one to begin with. However, upon testing the
optimization on the sample test cases, I found the optimization to be fairly
useless until other optimizations were applied first. This was due partly to
the pattern in which SUIF translates source code into IR form.

    Copy propagation was implemented in a fairly simple manner. The data flow
solver from assignment 2 was used. The reference solution was used and altered
to suit the conditions. All that was needed was to determine the kill and gen
sets for this particular case. The available copy expression lecture slides
were followed to complete this task (page 24, Topic 4 Optimizations I
Redundancy Elimination). Once the available copy expressions were found for the
entrance of each basic block, they were propagated downwards, from the entrance
of a block towards its exit until terminated by an over-riding definition.

    Once these 'global' available copy expression were propagated, 'local'
available copy expressions (available only within its basic block) were
determined and applied internally. This step was necessary since the method
outlined in the notes did not explicitly cover these cases. Once these steps
were complete, copy propagation was complete.

    Loop-invariant code motion was the next optimization to be applied. Lecture
note pages 8 and 14 under the same topic served as general guidelines to the
implementation. For each loop, the first step involved marking the loop
invariants but not actually performing any code motion. This was done using an
iterative method, where the iteration loop was exited when no further
instructions were marked as loop invariant. In the first pass, all LDP_OP
instructions were automatically marked. As well, all operands of an instruction
were checked to determine if all reaching definitions for the operand were
located outside of the loop. If this was true, then the instruction was marked
as well. Finally, if there was a reaching definition for an operand that
originated from within the loop, this source must be the only definition
reaching the operand and it must also be loop invariant itself. If an
instruction met these conditions, it was marked as well.  To check if a source
was loop invariant, the functions provided by the tutor in misc.c were used.
When an instruction was marked as loop invariant, it was pushed onto a stack
for later use.

    The use of a stack was very critical in obtaining the correct ordering of
instructions in the preheader block. Due to the iterative method of pushing
instructions onto the stack, instructions at the bottom of the stack have no
flow dependency on instructions at the top of the stack. When the instructions
are finally placed into the preheader, the positions of the instructions are
inverted and the proper dependencies are preserved.

    The above steps were repeated until no further instructions were added. The
second step involved popping each loop invariant from the stack and examining
it to determine if it was moveable. If deemed moveable, it was pushed onto the
preheader. These sequence of moves naturally preserved the ordering of
instructions.

    To meet the first condition of code motion (block belonging to instruction
must dominate all exit blocks of loop), each block of the loop was examined. If
at least one successor led to an external block, the current block was
considered an exit block. Checking for dominance simply involved examining the
dominators data structure as provided in the reference solution.

    To meet the second condition of code motion (x is not defined elsewhere in
loop), each block of the loop was examined. Using the get_dst() function
provided in misc.c (supplied by the tutor), this condition was checked.

    To meet the third condition (all uses of x in L can only be reached by that
definition of x), each block was examined. By using the get_srcs() function
provided in misc.c, usage was determined. If usage was detected, reaching
definitions at the entrance of the block were examined. If the only reach
definition originated from the instruction in question, the third condition was
satisfied.

    When all three conditions were satisfied, the instruction was popped off
the stack and pushed into the preheader block. This involved detaching it from
its current position in the instruction linked list and re-attaching it in the
pre-header block.

    Once loop invariant code motion was applied, I attempted to apply copy
propagation again. However, I met some difficulties and was not able to reapply
the optimization despite carefully reinitializing state variables and
rebuilding the flow control graph.