########################################
#Written by David Tam, 1999. #
#davidkftam@netscape.net Copyright 1999#
########################################
ECE 540 - Optimizing Compilers
Assignment 1
Control Flow Analysis
Friday, February 19, 1999
David Tam
-------------------------------------------------------------------------------
For the first part of the assignment, one pass through the instruction
linked list and two passes through the basic block linked list were used to
generate basic blocks, allocate bit vectors for the successor and predecessor
list, and find all successors and predecessors. The basic block element
consisted of a block number, pointer to first instruction in block, pointer to
last instruction in block, successor bit vector, predecessor bit vector, proper
dominator bit vector, immediate dominator variable, and pointer to next basic
block in linked list.
In the first pass through the instructions, basic blocks were created, a
block number was assigned, the first and last instruction pointers of the block
were assigned, and labels were entered into a hash table. At the end of the
first pass, the total number of blocks was known. Next, a pass was made through
the basic block linked list to allocate bit vectors of appropriate size for
predecessor, successor, and proper dominator lists. Finally, a second pass was
made through the basic block list to find all successors and predecessors. For
each block, the last instruction pointer was used to locate the last
instruction in the block. This instruction was examined to determine the
successors of the block. If it was a branch instruction, its target labels were
used to query the hash table and determine successor block numbers. These
numbers were entered into the successor bit vector. At the same time,
predecessors were determined by going to each of the successor block's
predecessor list and adding the current block to it.
For the second part of the assignment the immediate dominator for each
block was determined using the method given in the lecture notes. First, all
dominators for each block was determined using the recurrence relation method
given on page 11 of the lecture slides titled "Topic 2 Control Flow Analysis".
This involved traversing the block list many times until no changes to the
dominator lists were detected. These results were made proper and placed into
the proper dominator list of each block. Finally, the immediate dominators were
found using the method given on page 14 of the lecture slides. This method
involved eliminating proper dominators of the block that were also being
properly dominated by another proper dominator of the block.
For the third part of the assignment, loops were found by first determining
back edges of each block. This was easily determined by finding successors that
were also proper dominators of the block. Once a back edge had been found,
blocks involved in the loop were determined using the method given on page 21
of the lecture slides. This method was altered slightly to ensure there were no
other entry points into the candidate loop. For each block involved in the
loop, its predecessors must be dominated by the loop header block and NOT
dominated by the loop tail block. This list of loop blocks and the tail were
stored in a bit vector and an integer variable contained in the loop header
block.
The basic block linked list was traversed once more to insert loop
preheaders. If a block contained a valid loop tail number, it was a loop header
block. Surgery was performed on both the instruction linked list and the basic
block linked list. A new label instruction was inserted immediately before the
loop header instruction. Next, a new basic block for the new label instruction
was attached to the end of the basic block linked list. Information from the
header block was transferred to the preheader block. This included the
dominators list, immediate dominator, predecessors not involved in the loop,
list of loop blocks, and loop tail number. Additional changes to the header
block included adjusting its immediate dominator to be the preheader block.
Blocks in the predecessor list of the preheader were adjusted so its
successor list included the new preheader but excluded the old header. As well,
any blocks that were properly dominated by the header were now also properly
dominated by the preheader. Changes to other blocks were made to reflect this
new situation. As well, changes were made such that any header or preheader
blocks that included the previous header in its list of loop blocks now
required the addition of the new preheader block to the list. This last change
was needed to accurately output nested loops.
Changes in the instructions were also made to reflect the addition of the
new label instruction. Some, but not all, references to the old header label
were changed to reference the new preheader label. These references were found
by looking in the predecessor list in the preheader. For each predecessor
block, the last instruction of the block was adjusted appropriately.
Finding the maximal tail of each loop was not implemented because of time
constraints. However, an implementation idea will be described. A new bit
vector in the header or preheader can be used to hold the list of loop tails.
Once loop-finding for all blocks is complete, the maximal loop tail can be
determined using a depth first search and stored in the loop tail variable.
(
geocities.com/siliconvalley/campus/9640/4thYear) (
geocities.com/siliconvalley/campus/9640) (
geocities.com/siliconvalley/campus) (
geocities.com/siliconvalley)