Method of Extracting Implicit Sequential Behavior From Hardware Description Languages

1. FIELD OF THE INVENTION

The present invention relates to the synthesis of circuit hardware from circuit behavior represented by hardware description languages (HDL), and more particularly to the extraction of hardware in the form of a finite state machine architecture from implicitly specified sequential behavior in the HDL description.

2. BACKGROUND OF THE RELATED ART

Electronic manufacturing technology presently allows the creation of monolithic integrated circuits that involve millions of transistors. Due to the sheer number of devices on a single chip, an entire industry has evolved specifically to supply the semiconductor industry with software and hardware tools to automate much of the integrated circuit design process. In particular, significant research and development effort has been directed toward effecting the extraction of circuit hardware, in the form of a hardware netlist, from descriptions of the circuit's behavior using hardware description languages (HDL).

Initially, techniques have been perfected to extract combinational logic circuits including AND gates, OR gates, NAND gates, NOR gates, complex combinations of the foregoing and flip-flops. At the next level, processes have been developed to extract finite state machine (FSM) circuit architectures explicitly described by HDL circuit descriptions.

Related application U.S. Ser. No. 08/376,491, discloses a method of extracting flip-flops from HDL descriptions, which is incorporated herein by this reference. Related application U.S. Ser. No. 08/362,028, discloses a method of extracting FSM architecture from HDL circuit descriptions which explicitly specify sequential circuit behavior, which is incorporated herein by this reference.

FIG. 1 illustrates a general FSM architecture. The general FSM architecture typically comprises an implicit state register (ISR) the output of which designates the current state of the state machine. Flip-flops 100 and 102 form the ISR of the general FSM architecture of FIG. 1. Of course, the number of flip-flops required for the ISR will depend on the number of states of the FSM. The combinational logic block 104 of the FSM architecture produces the "next state" inputs to the ISR flip-flops, which in turn determine the next state of the FSM. The transition to the next state occurs on the next rising edge of the single clock input 106. Combinational logic block 104 also produces outputs which can either be fed back as inputs into combinational logic block 104 simply provide output to other hardware blocks of the circuit or both. The outputs of the FSM are also latched on the rising edge of single clock input 106 and are defined to be of a certain value depending on the value of ISR. Finally, combinational logic block 104 receives as inputs both the previous state of ISR, shown as q0 108 and q1 110, as well as inputs 112, which can emanate from other signals internal or external to the circuit, and are defined by the HDL. The FSM architecture may also include a single reset input 118, which resets the FSM to a known initial state.

FIG. 2 represents an example of a state machine which could be implemented using the general FSM architecture of FIG. 1. The example state machine of FIG. 2 has four states 120, each of which is represented by a value assumed by the ISR. Transition arcs 122 illustrate the possible transitions between states 120 which can legally occur for the example state machine of FIG. 2. Variables 124 represent inputs and outputs of the example FSM which either must assume certain values in order that a particular transition can occur between one state and another (FSM inputs), or must assume a particular value as a result of the transition (FSM outputs). Those of ordinary skill in the art will recognize that there are other more general FSM architectures than the FSM architecture illustrated in FIG. 1. As illustrated by the example state diagram of FIG. 2, in order that the FSM transitions from one state to another, certain conditions must be met. Thus, for the FSM to transition from state 1 (S.sub.1) to state 2 (S.sub.2), the FSM must currently be in S.sub.1 (i.e. the previous state). Also, the variables X, Y, and RESULT may have to assume a particular value before the transition is enabled (i.e. act as inputs). Finally, X and/or Y and/or RESULT may have to assume a particular value subsequent to the transition (i.e. act as FSM outputs).

The state transitions represented by arcs 122 between states 120 can be summarized in the form of a state transition table which defines the legal transitions between the states as well as the conditions (i.e., the necessary values of the variables) requisite to the transition between each state.

As previously discussed, methods have been disclosed by which an FSM architecture can be extracted from the HDL description of a circuit when such state transition conditions are explicitly specified in the HDL description. Although some work has been done in the past in attempting to extract FMS descriptions from languages which are specific to expressing state machine (i.e. sequential) behavior, no one has heretofore provided a method for extracting such behavior from general functional HDLs when such behavior is only implicitly specified.

Because it is desirable to have an integrated tool which can synthesize the hardware implementations of most if not all circuit behavior and with the least amount of restrictions on the modes of expressing that behavior, it is highly desirable to provide a method of inferring hardware implementations of implicitly specified sequential behavior.

The present invention is a method of synthesizing structural netlist in the form of a finite state machine (FSM) from those processes of an HDL circuit description which specify implicit sequential behavior. The method of the invention operates on control flow graphs (CFGs) which represent the control flow of the processes which comprise the HDL functional description of the circuit. CFGs are generated by known HDL parser routines which perform lexical and syntactic analysis of each HDL process to generate a CFG for each such process.

The method of the invention only operates on those CFGs which specify implicit sequential behavior using wait statements or event control statements which are sensitive to a single unique clock edge. Each CFG also represents embedded data-flow information. The data flow is represented by a directed acyclic graph (DAG).

For each CFG having the above-described characteristics, the present invention systematically evaluates the CFG beginning at its source node to build a state transition table (STT) which will define the FSM circuit which implements the behavior described by the HDL process that is represented by the CFG currently being evaluated. The STT describes the implementation details as well as the state diagram of the FSM defines the set of states, the set of transitions which can occur between the states, and a set of labels which are associated with each transition. Each label of the set of labels provides information which defines the values of inputs of the FSM that condition the particular transition as well as the values of outputs of the FSM which must be assumed as a result of a transition. The state transitions, as well as the output expressions are defined by the DAGs representing data-flow dependency.

For the current CFG, the method of the invention extracts the STT by evaluating all executable paths between wait nodes (or event nodes). The CFG is traversed by a breadth-first search algorithm that evaluates each control node of the CFG once all of its activated parent nodes have been evaluated. Each time a wait node is encountered during this process, implicit previous states (IPS) are determined for the wait node under evaluation through a simple depth-first search (DFS) in the opposite direction of the control flow back to any previously evaluated wait states. Further, an extended level maximal set (ELMS) is calculated based on a breadth-first search (BFS) in the opposite direction of the control flow back to each of the implicit previous states. The ELMS is used in conjunction with other known optimization techniques (e.g. common sub-expression elimination, dead-code elimination and life-variable analysis) to minimize the expressions of the variables defining the FSM inputs and outputs.

Thus, each wait node (and sometimes the source code) of the current CFG corresponds to a state of the state machine, and the conditions for transitions from one state to another correspond to the evaluation of all executable paths between the wait nodes which correspond to those states.

Each node of the CFG is evaluated by first computing its node activation, then computing the signal values of all input and output variables v at the current node n, computing the edge activation for each of the successor nodes of n and then evaluating each of the computed edge activations by substituting in signal values for variables v for the current node n into the expression for the computed edge activations.

The evaluation of each node is further dependent upon the type of node that it is. Loop nodes must be either unrolled if the loop is specified using a loop index which defines a finite number of iterations, or expanded if there is no loop index or the loop index is variable and thus does not specify a finite number of iterations. A loop which can be unrolled is unrolled according to known techniques of loop unrolling. If the loop cannot be unrolled, the loop is expanded by replacing the loop node with an if node the conditions for which are the same as for the specified loop condition. The true edge of the if node is connected to a duplicated version of the original loop body, the output edge of which is connected to a second if statement, which replaces the original iterate node of the loop. The second if node is also predicated upon the original loop condition, the true edge of which is connected to a second duplicated version of the original loop body. The edges of both the first and second if nodes representing a false condition, are both input to a first join node. The output of a first join node and the second duplicated version of the original loop body are then connected to a second join node. The expanded loop is then replaced in the original CFG such that the first if node takes the place of the original loop node and the second join node takes the place of the original terminate node. The evaluation process then continues at first if node which replaces the original loop node.

If the current node n is an iterate node, it must be determined whether the loop node associated with the iteration node under evaluation dominates all of the nodes comprising the set of nodes which define implicit previous states. If the answer to this inquiry is no, the behavior cannot be synthesized as a finite state machine and an error message is generated. The method then goes back and attempts to process the next CFG incorporating wait statements sensitive to a unique clock edge.

If the current node n is a simple node, and is also an assignment node, the expression assigned to a particular variable v is evaluated and that value defined by the expression is substituted for the current value of the variable at the particular node n. If the simple node is a source node, a state is added to the STT for the source node (the ISR is assigned a value vals for that node).

If the node is a wait node, a state is added to the STT for that node by assigning a value val.sub.w to the ISR for that node. The set of all IPS values is then computed for the wait node which defines all of the other wait nodes or source node from which execution of the CFG can reach the current wait node n.sub.w. A function f.sub.w is calculated for n.sub.w (i.e., F.sub.n) which is essentially the node activation for the current wait node n.sub.w. The function F.sub.n is evaluated for each node represented in the IPS set by substituting for the variable ISR in the function the value assigned to ISR for each of the nodes in the IPS set. The evaluated function F.sub.n for each node in the IPS set defines the conditions requisite for the transition from the state associated with each of the nodes of the IPS set to the current wait node n.sub.w and each of these transitions along with their requisite conditions is added to the STT. A second function H.sub.w for n.sub.w (i.e. H.sub.n) is computed for all variables v which generates the minimal expression for each variable v at n.sub.w. The function H, is evaluated for all variables v by substituting for the variable ISR the value assigned to ISR for each of the nodes which are members of the IPS set (i.e. all of the parent weight nodes of current-node n.sub.w. The results of this evaluation become the expression of the outputs for each of the transitions from a previous state defined for each node in the IPS set to the current node n.sub.w as a result of that transition.

Thus, the STT which describes the state transitions between each state and another state of the FSM along with the values of inputs which provide a condition for the transition as well as the expressions which define the outputs as a result of those transitions are built systematically as the CFG is evaluated in accordance with the method of the invention.

It should also be noted that the appropriate values of v must be computed and propagated to the current node under evaluation even when it is not a wait node.

FIG. 1 is a diagram of a general finite state machine architecture.

FIG. 2 is a diagram of a state machine using the general finite state machine architecture of FIG. 1.

FIG. 3 is a high level procedural flow diagram of a method of extracting implicit sequential behavior from hardware description languages.

FIG. 4 is a procedural flow diagram of the process for sequentially evaluating control nodes.

FIG. 5 is a procedural flow diagram of the node evaluating step of FIG. 4.

FIG. 6 is a procedural flow diagram of the immediate successor node enabling step of FIG. 4.

FIG. 7 is a detailed procedural flow diagram of the node activation computation step of FIG. 5.

FIG. 6 is a detailed procedural flow diagram of the signal values computation step of FIG. 5.

FIG. 9 is a detailed procedural flow diagram of the edge activation evaluation step of FIG. 5.

FIG. 10 is a detailed procedural flow diagram of the edge activation computation step of FIG. 5.

FIG. 11 is a detailed procedural flow diagram of the loop node evaluation step of FIG. 5.

FIG. 12 is a detailed procedural flow diagram of the iterate node evaluation step of FIG. 5.

FIG. 13 is a detailed procedural flow diagram of the wait node evaluation step of FIG. 5.

FIG. 14 is a detailed procedural flow diagram of the simple node evaluation step of FIG. 5.

FIG. 15 is a detailed procedural flow diagram of the extended level maximal set computation step of FIG. 8.

FIG. 16(a) is a detailed procedural flow diagram of the expand loop step of FIG. 11.

FIG. 16(b) is a diagram of the transformation of the unrollable loop into an expanded loop according to the procedure of FIG. 16(a).

FIG. 17 is a detailed procedural flow diagram of the computation step of implicit previous states of node n of FIG. 12.

FIG. 18 is a detailed procedural flow diagram of the F.sub.n computation step of FIG. 13.

FIG. 19 is a detailed procedural flow diagram of the H.sub.w computation step of FIG. 13.

FIG. 20(a) is a program listing exhibiting the requisite characteristics for permitting extraction of its implicit sequential behavior. FIG. 20(b) is a control flow graph for the process of FIG. 20(a).

FIG. 20(c) is a skeleton state transition table for the process of FIG. 20(a).

FIG. 20(d) is the extracted implicit state machine for the process of FIG. 20(a).

FIG. 20(e) is a simplified state transition table for the process of FIG. 20(a).

FIG. 21(a) is the process of FIG. 20(a) written in Verilog.

FIG. 21(b) is a control flow graph for the process of FIG. 21(a).

FIG. 22 is a hardware logic diagram of the finite state machine generated from the simplified state transition table of FIG. 20(e).

The method of the present invention extracts a hardware implementation of sequential behavior implicitly specified by a functional description of a circuit using a hardware description language (HDL). The hardware implementation is inferred as a finite state machine (FSM) the general architecture of which is described in FIG. 1. For each functional process of the HDL circuit description which implicitly specifies sequential behavior capable of being represented by the FSM architecture of FIG. 1, the method of the present invention infers the details required to implement the process in accordance with the architecture of FIG. 1. Thus, the method of the invention infers the number of unique states of the FSM, as well as the combinational logic circuitry which is capable of producing inputs to the implicit state register (ISR) to produce the next state. This combinational logic generates the next state based on input variables which include values identifying the previous state. Further, the combinational logic circuitry must also produce outputs of the FSM which have values specified by the process.

The method of the present invention accomplishes this result by systematically building a state transition table (STT) which defines all of the states of the FSM, all of the legal transitions between states, the requisite values of any of the inputs which define conditions under which each of the transitions can occur, and the values of the outputs of the FSM which must be produced as a result of each of those transitions. This is accomplished by a systematic evaluation of a control flow graph (CFG) which defines the control flow of the functional process which is capable of implementation in accordance with the architecture of FIG. 1. The method of the present invention is restricted to extracting sequential behavior to that which can be implemented using the FSM architecture of FIG. 1. Thus, this restriction prohibits the extraction of implicit sequential behavior that is not sensitive to a unique clock edge. Further, the outputs of the FSM are registered because they are defined within a process which is sensitive to only one clock edge.

Implicit sequential behavior is typically specified in an HDL description using statements that allow the process to suspend its execution until an event occurs. In one commercially available HDL language, VHDL, this statement is known as a wait statement. In a second commercially available HDL language, Verilog, an event control statement is used. While this description is written from a VHDL standpoint, those of skill in the art will recognize that the method of the present invention is equally applicable to other statements used in other languages such as the event control statement of Verilog. FIG. 3 illustrates a high-level procedural flow diagram for the method of the present invention. Those of skill in the art will recognize that the present invention can be used in conjunction with other known methods of extracting hardware from HDL circuit descriptions in order to fully synthesize a circuit described by the HDL description. Block 20 of FIG. 3 illustrates the process of parsing the HDL description to create CFGs for each process of the HDL description. HDL parsers are well known in the art and are used to perform lexical and syntactic analysis of the HDL processes and to generate control flow graph representations of each of the processes. It is further noted that each CFG contains embedded data-flow information.

Block 30 of FIG. 3 represents the procedure which embodies the method of the present invention. The method of the present invention identifies all of the CFGs having one or more wait statements sensitive to a single unique clock edge. For each of the identified CFGs, the invention extracts an FSM state transition table (STT). Those of skill in the art will recognize that known techniques for extracting explicit sequential behavior as well as combinational logic from the remaining CFGs can be applied in conjunction with the method of the present invention to extract hardware representations of all of the processes comprising the HDL description of the circuit to be synthesized.

Block 40 represents the known step of taking extracted hardware representations generated through the analysis of the CFGs and creating a structural netlist from the available device structures stored in a cell library. Thus, block 40 will take the STT information from block 30, as well as STTs extracted from explicit sequential behavior and output representing extracted combinational behavior to produce a structural netlist of the entire circuit to be synthesized.

FIG. 4 illustrates a procedural flow diagram defining the process by which control nodes comprising the current CFG are sequentially evaluated for purposes of extracting the FSM STT from the implicitly specified sequential behavior of the process represented by the current CFG. Block 300 represents the step of identifying from the set of all CFGs generated by the parsing step of block 20 (FIG. 3) specifying implicit sequential behavior implementable as an FSM. After a node is placed into Queue 1, the node is evaluated in accordance with procedure 308 of FIG. 5. Block 310 represents a procedure for determining which of the unvisited nodes of the current CFG will be evaluated next. Three procedures implement a simple Depth First Search (DFS). The general purpose of procedural flow described in FIG. 4 is to systematically evaluate all of the executable paths between the wait nodes of the current CFG. Each node is systematically evaluated as a function of its node activation as well as the minimal data expressions representing the value of each of the variables of the process at the current node n (i.e. the node currently being evaluated).

The node activation is an expression for a given node that evaluates to true when the node n is active. The edge activation is an expression C.sub.n,j that is associated with each edge of the CFG between node n and any of its successor nodes j. The edge activation is true when control is passed from node n to its successor j. Thus, node activation for a given node n is defined recursively to be as follows: For all wait or source nodes, c.sub.n =1 (i.e., is true). For all other nodes n, c.sub.n =.SIGMA.c.sub.j .multidot.C.sub.j,n where j is the set of all parent nodes of n (i.e. PN.sub.(n)).

Edge activation C.sub.i,n is true for all edges from any node which is not a fork node, a wait node, or a source node. For edges from fork nodes the expression representing the predicate or case selector determines that exactly one of the edge activation expressions is true and all others are false. For a source node or any wait node, the expression representing the edge activation is set to ISR=val.sub.n. ISR is a variable representing the output of the implicit state register, and val.sub.n represents the value of the implicit state register output for node n. A directed path from any node n to node j of a control flow graph is said to be activated if no edge activation of that path is evaluated to be false.

The data expression for any live variable v, specified by the process, and any control node n is denoted de.sub.n (v) is defined recursively as follows:

where j=the set of all parent nodes of n.

Equation (1) shows that the data expression of variable v at a source node is set at its initial value (IV). Equation (2) shows that the data expression of variable v for a wait node is reset to an implicit variable v.sub.- q, which corresponds to the previous value of v set in previous states. Equation (3) shows the data expression of variable v at an assignment node that sets that variable. Equation (4) shows that the data expression of variable v at a node that does not set that variable and is neither a source node nor a wait node is the Boolean sum of the values determined at each of the parent nodes of node n, banded with that parent node's activation. Data expression of dead temporary variables at a node n are set to unknown values. The evaluate node procedure 308 is illustrated in FIG. 5 and operates in accordance with the foregoing definitions. Block 318 represents a procedure for computing the node activation in accordance with the foregoing equations. FIG. 7 illustrates a more detailed procedural flow for the procedure of block 318.

Block 320 of evaluate node n procedure 308 computes the signal values for the live variables at node n in accordance with the above equations. A more detailed procedural flow implementing the compute signal values routine 320 is illustrated in FIG. 8. As can be seen from the flow of FIG. 8, if the current node n is a source or wait node, decision block 348 transfers control to block 346 where all values of variables v are set to initial values in the case of a source node, or values at previous states in the case of a wait node, in accordance with equations (1) and (2) above. If the current node n is neither a join node, a source node or a wait node, control is transferred to block 350 at which all values of v are propagated to the current node n from the previous node just evaluated. If the current node n is a join node, control proceeds to block 340 which computes an extended level maximal set (ELMS) which is determined for each variable v from the current node n. ELMS(v,n) is the set of ancestor nodes that are individually furthest in the direction opposite to the flow from node n in the CFG which has the following properties: First, if a given node s is a member of the ELMS set, the directed path from node s to node n is activated. Second, there can be no activated path from node s to node n through any node m which is a wait node or at which there is an assignment to variable v. Third, all activated paths from any node in IPS(n) to n must pass through a member of the ELMS set. IPS(n) is the set of implicit previous states of node n, which is the set of ancestor wait nodes of n that are individually closest in the direction opposite to the flow from node n in the control flow graph. Members of IPS(n) are either a wait node or a source node and there must be at least one activated path from a member of IPS(n) to n that does not pass through a wait node.

The procedural flow diagram of FIG. 15 shows a more detailed procedural flow for the compute ELMS(v,n) procedure of block 340. Once the ELMS(v,n) has been calculated, control is transferred to block 342 which computes the greatest common factor (GCF(v,n)) in accordance with known techniques. A minimal expression for all variables v at node n can then be generated in accordance with the equation as follows: de.sub.n (v)=.SIGMA.c.sub.j .multidot.de.sub.j (v), where j is each of the nodes of the ELMS(v,n) set. This equation follows because there are no nodes changing any of the variables v from any of the nodes in the ELMS set to node n. It is then possible to factor the activation condition of the node that dominates node n and any node in the ELMS set with respect to the IPS(n) set. This dominator vertex is called the greatest common factor (GCF), which is calculated at block 342 using known techniques.

It should be noted that, while the generation of a minimal expression for v at node n using a level maximal set (LMS) as well as the use of a GCF to further reduce the expression of variables v have been known in the past, the notion of an LMS has been extended to operate in the context of sequential behavior in accordance with the present invention. For background information concerning previously applied optimal variable expressions in a context of combinational logic, reference can be made to the following reference: G. Colon-Bonet et al., "On Optimal Extraction of Combination Logic and Don't Care Sets from Hardware Description Languages," in ICCAD, PP. 308-311, November 1987, which is incorporated herein by this reference.

The evaluate node procedure 308 of FIG. 5 then proceeds to block 322 at which time edge activations are computed for the edges connecting node n to its successor nodes. A more detailed procedural flow is illustrated in FIG. 10 for the compute edge activation procedure 322. It can be seen from FIG. 10 that the compute edge activation procedure 322 implements the above-described definitions of edge activation.

Once edge activation has been computed, in accordance with procedure 322, the evaluate node procedure 308 proceeds to evaluate the edge activations computed by the compute edge activation procedure 322 in light of the current values of the variables as computed by the compute signal values from procedure 320 of FIG. 8. A more detailed procedural flow is illustrated in FIG. 9 for the evaluate edge activation procedure 324.

Upon completion of procedure 324, the evaluate node procedure 308 of FIG. 5 determines at block 326 whether the node activation evaluates to a definitely false condition. If the node activation of current node n evaluates to a definitely false condition, that branch of the CFG will never be executed and therefore need not be implemented in the hardware. If the node activation of current node n is either true or could be evaluated to be true, procedure 308 continues processing at block 328 if the current node n is a loop node, at block 332 if current node n is an iterate node, at block 334 if the current node n is a wait node, or at block 336 if current node n is a simple node.

If current node n is a loop node, control is transferred to the evaluate loop node procedure 328. A more detailed procedural flow for procedure 328 is illustrated in FIG. 11. Procedure 328 first evaluates the loop condition specified by loop node n at block 366. If the expression representing the loop condition is definitely false, processing returns to block 310 of procedure 30, shown in FIG. 4. The procedure represented in block 310, a more detailed illustration of which is shown in FIG. 6, determines along with procedure 30 which control node of the CFG will be processed next.

If the expression representing the loop condition is or can be true, procedure 328 of FIG. 11 proceeds to determine whether the loop can be unrolled, or whether it must be expanded. Loops which have finite numbers of iterations are typically loops which specify non-varying indexes. If the loop can be unrolled, control is transferred to block 372, which proceeds to unroll the loop in accordance with known loop-unrolling techniques. If the loop cannot be unrolled, control is transferred to the expand loop routine 370.

A more detailed of the expand loop procedure 370 is illustrated in FIG. 16a. FIG. 16b illustrates the transformation of the unrollable loop into an expanded loop in accordance with the procedure described in FIG. 16a.

The unrolled or expanded loop is then substituted into the current CFG being evaluated. Control is then transferred back to the procedure of block 310 of FIG. 4 for determination of the next node to be evaluated.

If the current node n is an iterate node, processing continues at block 332 representing the evaluate iterate node procedure. A more detailed illustration of the evaluate iterate node procedure 332 is shown in FIG. 12. Processing continues at block 376, where the IPS set for the current iterate node n is calculated in accordance with the compute IPS procedure illustrated in FIG. 17.

Procedure 376 as illustrated in FIG. 17 discloses an implementation for calculating the implicit previous state IPS set of nodes for n. Once IPS(n) has been computed for the current iterate node n, Block 380 determines whether the top node of the loop with which the current iteration node n is associated, dominates all nodes of the IPS(n) set. If it does not, an error message is output to the user indicating that this particular behavior cannot be synthesized in accordance with the method of the present invention, and control is returned to Block 300 of Procedure 30 (FIG. 4), which proceeds to the next CFG which is a candidate for extraction of implicit sequential behavior. If all nodes of IPS(n) are dominated, processing is returned to Block 310 of Procedure 30 to determine the next node to be evaluated.

If the current node n is a simple node processing continues at Block 336 of evaluate node Procedure 308 (FIG. 5). A more detailed illustration of the evaluate simple node Procedure 336 is shown in FIG. 14. If simple node n is an assigned node, the assignment expression is evaluated and the value of variable v, which is equated with the assignment expression, is updated with a new evaluated expression in accordance with the above-noted equation 4. If simple node n is not an assigned node, but is a source node, a state is added to the STT for the source node. This involves assigning a value to the ISR for the source node, which we define as "val.sub.s. If simple node n is neither an assigned node nor a source node, control is returned to Block 310 of Procedure 30 to determine the next node to be evaluated. No further updating of variables v is necessary, as they have already been propagated to the current node n by the compute signal values routine 320 (FIG. 8).

If the current node n is a weight node, processing continues at Block 334 representing the evaluate weight node routine. A more detailed illustration of the evaluate weight node procedure 334 is illustrated in FIG. 13. Decision Block 335 of Procedure 334 determines whether current weight node n.sub.w is a first duplicated weight node created by the evaluate loop node routine 328. If it is, a state is added to the STT for current weight node n.sub.w. This process also involves the assignment of a value defined as val.sub.n to the ISR. If the current node n.sub.w is a second duplicated weight node of an expanded loop, no state is added to the STT and control proceeds to Block 376. At Block 376, a new IPS set for current weight node n.sub.w is calculated in accordance with Procedure 376 (FIG. 17). The computation of the IPS set for weight node n.sub.w amounts to a determination of any other states thus far identified from which the state in the STT for the current weight node n.sub.w can be reached (i.e., any known transitions from previously identified states to the state represented by the current weight node).

If the IPS(n.sub.w) is an empty set, the values for all variables v at the current node n.sub.w are re-set to a value assigned at a previous state (i.e., de.sub.n (v)=v.sub.- q). Control is then return to Block 310 of Procedure 30 (FIG. 4) for determination of the next node of the current CFG to be evaluated. If the IPS set is not empty, control is transferred to Block 398 which calls a procedure for computing a function f.sub.W for n.sub.W (i.e., F.sub.N).

A more detailed procedure for calculating F.sub.N is illustrated in FIG. 18. Procedure 398 is quite similar to the process by which the node activation for other current nodes were determined by the compute node activation procedure 318 illustrated in FIG. 7. This procedure does in essence calculate the node activation for the weight state. In Block 388 the function F.sub.N is evaluated for each node in the IPS set by substituting for the variable ISR the value assigned to each of those nodes which are members of IPS. Put another way, because the nodes which are members of IPS comprise the set of all parent weight nodes of the current weight node n.sub.W, a substitute for the variable ISR in the equation computed for the function F.sub.n with the assigned value for ISR for each of the parent weight nodes comprising the set IPS (n.sub.W).

Each evaluated expression for F.sub.n for a particular parent weight node of the IPS set defines the condition for transition from the state associated with the parent weight node to the state associated with the current weight node. Block 390 adds each of these expressions to the state transition table (STT) to define the transition which it represents.

Block 392 then calls a procedure to compute a function H.sub.W for the current weight node n.sub.W (i.e., H.sub.N). A more detailed procedural flow for Procedure 392 is illustrated in FIG. 19. As illustrated by FIG. 19, the function H.sub.N is computed for each variable v using the same techniques for generating the minimal expression for the value of v at weight node n.sub.W, as was used to calculate the minimal expression for variable v at a join node.

Once the function H.sub.N has been computed for all variables v in accordance with Procedure 392, control is turned to Block 394 at which point all of the computed expressions for H.sub.N are evaluated by substituting the variable ISR with the value assigned to ISR for each of the parent weight nodes comprising the set IPS (n.sub.W). These evaluated expressions are then included in the STT--each in association with the state transition between the state assigned to each parent weight node of IPS set to the current weight node. Control is then returned to Block 310 of Procedure 30 (FIG. 4), which determines which of the remaining unvisited control nodes of the current CFG will be evaluated next.

FIG. 20(a) illustrates a process exhibiting the requisite characteristics for permitting extraction of its implicit sequential behavior. The process calculates the greatest common denominator between two inputs in one and in two.

FIG. 20(b) illustrates a CFG for the process of FIG. 20(a). FIG. 20(c) illustrates a skeleton STT which shows the three states (S1, S2 and S3) which correspond to weight nodes 1, 9, and 16. Below each state are indicated the conditions which must be extracted from the CFG to define the transition from that state to each of the other states.

FIG. 20(d) shows the extracted expressions defining the conditions for each of the transitions. Line 500 defines the expressions for those variables v which provide conditional inputs to the combinational logic block 104 of FIG. 1 to permit the transition between state S1 and state S2. Of course, one of the conditions is that the ISM is in State 1 prior to the transition. Lines 502 of STT define the values that FSM outputs are to assume upon the transition from state S1 to state S2. Likewise, lines 504 define variables which provide conditional inputs for the transition from state S1 to S3. Lines 506 define the values of variables which provide outputs from the FSM once the transition has occurred. FIG. 20(e) illustrates a simplified STT for the process of FIG. 20(a).

FIG. 21(a) illustrates the same process written in Verilog. FIG. 21(b) is a CFG generated from the Verilog version of the process as shown on FIG. 21(a). The method of the present invention can be used to infer the same state transition table from Verilog as it does from the VHDL version of the process shown in FIG. 20(a).

FIG. 22 illustrates a hardware implementation of the FSM which is generated from the STT of FIG. 20(e).

For additional technical background concerning the extraction of implicit sequential behavior, reference can be made to Giomi; Finite State Machine Extraction from Hardware Description Languages, attached hereto as Appendix A. ##SPC1##