######################################## #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.