Next: Speculative Execution Up: Simulation Algorithm Previous: Simulation Algorithm

Control Dependence Analysis

For the CD and CD-MF machines, the control flow constraint is that an instruction cannot execute until after its immediate control dependence branch has executed. Control dependence analysis is performed in two stages. We first compute the control dependences within each procedure by analyzing the object code. Interprocedural control dependences are handled dynamically as the traces are analyzed.

To analyze the control dependences within a procedure, we must first build a control flow graph. We use the MIPS pixie tool to identify the basic block boundaries. We then decode and analyze the instructions from the object file to determine the successors of each basic block. Using the flow graph, the analysis computes all of the immediate control dependences by finding the reverse dominance frontier of each basic block [3]. All of the instructions within a basic block are immediately control dependent on the branches in the reverse dominance frontier of the block.

An instruction may be immediately control dependent on multiple branches. However, each dynamic instance of an instruction only depends immediately on one of these branches. For example, instruction 2 in Figure 2 is control dependent upon both instructions 1 and 5. If control flows from instruction 1 to instruction 2, we need to consider only the dependence on instruction 1. This is accomplished by sequentially numbering each basic block in the trace, and as we analyze the trace, the simulator records for each basic block in the code the sequence number of its most recent instance. The immediate control dependence of an instance of an instruction is simply the branch within its reverse dominance frontier with the latest sequence number.

Interprocedural control dependences are handled by maintaining a stack that contains the control dependence information for each active procedure. This stack records the control dependence for each calling instruction and the sequence number at the start of each procedure. Each procedure simply inherits the control dependence of the instruction that calls that procedure. Without recursion, the control dependence for an instance of an instruction is either the control dependence on the top of the stack or an instance of a branch in its reverse dominance frontier, whichever is most recent.

With recursion, the control dependence for an instruction is either the dependence on the top of the stack or an instance of a branch in its reverse dominance frontier from the same procedure invocation. For expediency, our simulations do not keep track of all the necessary information to accurately compute the control dependence in a recursive procedure. For each basic block in the code, along with the sequence number of its most recent instance, the simulator also remembers the sequence number at the start of its procedure. Recursion is detected when any branch in an instruction's reverse dominance frontier has a procedure sequence number greater than the current procedure. At that point, to provide an upper bound on the control dependence, we simply ignore the control dependence for that instance of the instruction.



Next: Speculative Execution Up: Simulation Algorithm Previous: Simulation Algorithm


Bob Wilson