########################################
#Written by David Tam, 1999. #
#davidkftam@netscape.net Copyright 1999#
########################################
ECE 540S Optimizing Compilers Assignment #2 -- Data Flow Analysis
=================================================================
The reference implementation of assignment #1 was used to create the
initial flow control graph. The definition and expression sets were implemented
as linked lists while all others were implemented as arrays of pointer to bit
vectors.
The definition set was created by traversing each basic block and
determining if each instruction's op_code designated the instruction as a
definition. If this was the case, the destination register type was checked to
ensure it was a pseudo register. Once all of these conditions were met, the
instruction was added to the definition set.
To find the RD kill set for each block, each definition (comparer) was
compared to all other definitions (comparees). If the comparer and comparee
defined the same variables AND were in different blocks, the comparee was added
to the kill set of the comparer's basic block.
The RD gen set for each basic block was generated by traversing each
definition in the definition set. For each definition (comparer) the definition
set was traversed again to find duplicate definitions (comparees). If the
definitions were equivalent AND resided in the same block AND the comparee's
instruction number was greater than the comparer's then the comparer was NOT
added to the gen set of its corresponding basic block; otherwise it was added.
To find expressions, each instruction block had its set of instructions
examined. If the op_code of the instruction qualified the instruction as an
expression, and the destination register was of temporary or pseudo type, the
expression was added to the set.
The VBE eval set was found with the help of the expression set and a
modified version of the definition set. The modified definition set included
definitions assigned to pseudo and temporary registers. For each expression in
the expression set, each definition in the modified definition set was examined
to determine if the definition was (1) in the same block as the expression and
(2) had an instruction number less than the expression's instruction number. If
above two conditions were met, then the expression was NOT included in the eval
set of its corresponding basic block; otherwise is was included.
The VBE kill set was found by traversing the definition set. For each
definition, the expression set was traversed. If the expression was not in the
same block as the definition, the expression's operands were examined. If any
of the operands matched the variable defined in the definition, the expression
was added to the kill set of the definition's basic block.
The generic data flow solver was implemented using the method shown on page
21 of lecture slides entitled "Topic 3 Data Flow Analysis". The solver required
a kill set and gen set to operate. These were set appropriately for determining
the RD out and VBE out sets. As well, parameters for forward/backward flow, and
any/all path must be set in order to call the data flow solver function. The
inheritance equation was the only significant variable factor so it was
implemented in a separate function. The forward/backward flow parameter
determined whether to examine predecessors or successors of the current block,
while the any/all path parameter determined whether to use the and_bits() or
or_bits() function. However, the synthesis function did not require any
modifications.
(
geocities.com/siliconvalley/campus/9640/4thYear) (
geocities.com/siliconvalley/campus/9640) (
geocities.com/siliconvalley/campus) (
geocities.com/siliconvalley)