Code Generation

When an event is chosen via the function during a type I transition, the compiler emits the code corresponding to that event. To ensure that the code associated with a event is executed only when the dynamic conditions are right, the code is predicated by a condition that is evaluated at run time. The compiler introduces a run-time boolean variable for each vertex in the event graph that is maintained throughout the program execution such that it reflects whether the corresponding event is sensitized. Likewise, for each static simulation state a trigger variable is introduced to indicate if the event to be executed during that state has been triggered. Code is generated to set or reset these variables after each event. When a type II transition is taken, code can be emitted to increment the global simulation clock.

We observe that the naive static simulation described above may generate an infinite list of states on some event graphs. This may happen under two circumstances:

1. The static simulation may never reach a state whose set of ready events is empty. The algorithm described so far could keep taking type I transitions forever. This will occur, for example, when simulating circuits with unclocked feedback.

2. Similarly, the static simulation may never reach a state whose delayed events is empty. This occurs in synchronous designs as the clock signals change continuously until some dynamic condition occurs (see Figure 1).

We use the general method of finding fixed points to solve both of these problems. The technique is based on the observation that the set of possible static simulation states is finite.

Proof: For a given , the sets and are finite. The following relations must hold: , , and where . The latter equation is derived by observing that for all delayed events triggered by edge , . (That is, the remaining time to wait cannot be greater than the original delay in the program.) Thus there are only a finite number of possible , , and sets. As discussed earlier, we limit the possible values in to constants that appear in the program and unary operators on these constants. Thus there are a finite number of possible sets, and a finite number of possible static simulation states.

Our compiler algorithm is as follows. Whenever the compiler generates a new state , it compares with all the previously generated states. We are guaranteed by Theorem 1 that either the simulation will eventually terminate or we will find two matching states. If there is no match, the static simulation proceeds as discussed above. Otherwise, let be the matched state. The sequence of static simulation states following must be exactly the same sequence that follows . Thus, it is not necessary to continue to simulate statically, since the compiler can produce the equivalent code sequence by inserting a branch operation from to , thus creating a loop consisting of events .

Once a loop has been found, it is necessary to remove elements from the current and so that static simulation may continue. We remove the elements corresponding to events executed during the loop. This set of events also allows us to construct the exit condition for the loop, since it is only when none of these events are ready to be triggered that the loop may exit.

After finding a loop we continue simulation until we find another loop or until simulation is complete (a type III transition is taken). In general, loops consisting only of type I transitions will be generated first (unclocked feedback) and enclosed by loops consisting type I and II transitions (clocked feedback).