1 /*
2 * *********************************************************************
3 * * Copyright (C) 1988, 1990 Stanford University. *
4 * * Permission to use, copy, modify, and distribute this *
5 * * software and its documentation for any purpose and without *
6 * * fee is hereby granted, provided that the above copyright *
7 * * notice appear in all copies. Stanford University *
8 * * makes no representations about the suitability of this *
9 * * software for any purpose. It is provided "as is" without *
10 * * express or implied warranty. Export of this software outside *
11 * * of the United States of America may require an export license. *
12 * *********************************************************************
13 */
14
15 #include <stdio.h>
16 #include "defs.h"
17 #include "net.h"
18 #include "globals.h"
19 #include "ASSERT.h"
20
21
22 #define TSIZE 16384 /* size of event array, must be power of 2 */
23 #define TMASK (TSIZE - 1)
24
25 typedef struct
26 {
27 evptr flink, blink; /* pointers in doubly-linked list */
28 } evhdr;
29
30
31 public int debug = 0; /* if <>0 print lotsa interesting info */
32
33 public Ulong cur_delta; /* current simulated time */
34 public nptr cur_node; /* node that belongs to current event */
35 public long nevent; /* number of current event */
36
37 public evptr evfree = NULL; /* list of free event structures */
38 public int npending; /* number of pending events */
39 public int spending; /* number of scheduled events */
40
41 private evhdr ev_array[TSIZE]; /* used as head of doubly-linked lists */
42
43 /*
44 * Sets the parameter "list" to contain a pointer to the list of pending
45 * events at time "cur_delta + delta". "end_of_list" contains a pointer to
46 * the end of the list. If there are no events at the indicated time "list"
47 * is set to NULL. The function returns 0 if there are no events past the
48 * "cur_delta + delta", otherwise it returns the delta at which the next
49 * events are found;
50 */
51
pending_events(delta,list,end_of_list)52 public Ulong pending_events( delta, list, end_of_list )
53 Ulong delta;
54 evptr *list, *end_of_list;
55 {
56 evhdr *hdr;
57 register evptr ev;
58
59 *list = NULL;
60
61 delta += cur_delta;
62 hdr = &ev_array[ delta & TMASK ];
63
64 if( hdr->flink == (evptr) hdr or hdr->blink->ntime < delta )
65 goto find_next;
66
67 for( ev = hdr->flink; ev->ntime < delta; ev = ev->flink );
68 if( ev->ntime != delta )
69 goto find_next;
70
71 *list = ev;
72 if( hdr->blink->ntime == ev->ntime )
73 *end_of_list = hdr->blink;
74 else
75 {
76 for( delta = ev->ntime; ev->ntime == delta; ev = ev->flink );
77 *end_of_list = ev->blink;
78 }
79
80 find_next:
81 {
82 register long i, limit;
83 Ulong time;
84
85 time = MAX_TIME;
86 for( i = ++delta, limit = i + TSIZE; i < limit; i++ )
87 {
88 ev = (evptr) &ev_array[ i & TMASK ];
89 if( ev != ev->flink )
90 {
91 if( ev->blink->ntime < delta )
92 continue;
93 for( ev = ev->flink; ev->ntime < delta; ev = ev->flink );
94 if( ev->ntime < limit )
95 {
96 time = ev->ntime;
97 break;
98 }
99 else if( ev->flink->ntime < time )
100 time = ev->flink->ntime;
101 }
102 }
103 delta = ( time != MAX_TIME ) ? time - cur_delta : 0;
104 }
105
106 return( delta );
107 }
108
109
110 /*
111 * find the next event to be processed by scanning event wheel. Return
112 * the list of events to be processed at this time, removing it first
113 * from the time wheel.
114 */
get_next_event(stop_time)115 public evptr get_next_event( stop_time )
116 Ulong stop_time;
117 {
118 register evptr event;
119 Ulong i, time, limit;
120
121 if (npending == 0)
122 return(NULL);
123
124 time = MAX_TIME;
125 for( i = cur_delta, limit = i + TSIZE; i < limit; i++ )
126 {
127 event = (evptr) &ev_array[ i & TMASK ];
128 if( event != event->flink )
129 {
130 if( event->flink->ntime < limit ) /* common case */
131 goto found;
132 if( event->flink->ntime < time )
133 time = event->flink->ntime;
134 }
135 }
136
137 if( time != MAX_TIME )
138 event = (evptr) &ev_array[ time & TMASK ];
139 else
140 {
141 lprintf( stderr, "*** internal error: no events but npending set\n" );
142 return( NULL );
143 }
144
145 found:
146 {
147 evptr evlist = event->flink;
148
149 time = evlist->ntime;
150
151 if( time >= stop_time )
152 return( NULL );
153
154 /* sanity check for incremental simulation mostly */
155 ASSERT( time >= cur_delta )
156 {
157 lprintf( stderr, "time moving back %d -> %d\n", cur_delta,
158 evlist->ntime );
159 }
160
161 cur_delta = time; /* advance simulation time */
162
163 if( event->blink->ntime != time ) /* check tail of list */
164 {
165 do
166 event = event->flink;
167 while( event->ntime == time );
168
169 event = event->blink; /* grab part of the list */
170 evlist->blink->flink = event->flink;
171 event->flink->blink = evlist->blink;
172 evlist->blink = event;
173 event->flink = NULL;
174 }
175 else
176 {
177 event = evlist->blink; /* grab the entire list */
178 event->blink->flink = NULL;
179 evlist->blink = event->blink;
180 event->flink = event->blink = (evptr) event;
181 }
182 return( evlist );
183 }
184 }
185
186
187 /* remove event from node's list of pending events */
188 public
189 #define free_from_node( ev, nd ) \
190 { \
191 if( (nd)->events == (ev) ) \
192 (nd)->events = (ev)->nlink; \
193 else \
194 { \
195 register evptr evp; \
196 for( evp = (nd)->events; evp->nlink != (ev); evp = evp->nlink );\
197 evp->nlink = (ev)->nlink; \
198 } \
199 }
200
201
202 public
203 #define FreeEventList( L ) (L)->blink->flink = evfree, evfree = (L)
204
205
206 /*
207 * remove event from all structures it belongs to and return it to free pool
208 */
free_event(event)209 public void free_event( event )
210 register evptr event;
211 {
212 /* unhook from doubly-linked event list */
213 event->blink->flink = event->flink;
214 event->flink->blink = event->blink;
215 npending--;
216 if (event->type == TIMED_EV) spending--;
217
218 /* add to free storage pool */
219 event->flink = evfree;
220 evfree = event;
221
222 if (event->type != TIMED_EV)
223 free_from_node( event, event->enode );
224 }
225
226 /* get event structure. Allocate a bunch more if we've run out. */
227 #define NEW_EVENT( NEW ) \
228 { \
229 if( ((NEW) = evfree) == NULL ) \
230 (NEW) = (evptr) MallocList( sizeof( struct Event ), 1 );\
231 evfree = (NEW)->flink; \
232 }
233
234
235 /*
236 * Add an event to event list, specifying transition delay and new value.
237 * 0 delay transitions are converted into unit delay transitions (0.01 ns).
238 */
enqueue_event(n,newvalue,delta,rtime)239 public void enqueue_event( n, newvalue, delta, rtime )
240 register nptr n;
241 long delta, rtime;
242 {
243 register evptr marker, new;
244 Ulong etime;
245
246 /* check against numerical errors from new_val routines */
247 ASSERT( delta > 0 and delta < 60000 )
248 {
249 lprintf( stderr, "bad event @ %.2fns: %s ,delay=%ddeltas\n",
250 d2ns( cur_delta ), pnode( n ), delta );
251 delta = rtime = 1;
252 }
253
254 NEW_EVENT( new );
255
256 /* remember facts about this event */
257 new->ntime = etime = cur_delta + delta;
258 new->rtime = rtime;
259 new->enode = n;
260 new->p.cause = cur_node;
261 new->delay = delta;
262 if( newvalue == DECAY ) /* change value to X here */
263 {
264 new->eval = X;
265 new->type = DECAY_EV;
266 }
267 else
268 {
269 new->eval = newvalue;
270 new->type = REVAL; /* for incremental simulation */
271 }
272
273 /* add the new event to the event list at the appropriate entry
274 * in event wheel. Event lists are kept sorted by increasing
275 * event time.
276 */
277 marker = (evptr) & ev_array[ etime & TMASK ];
278
279 /* Check whether we need to insert-sort in the list */
280 if( (marker->blink != marker) and (marker->blink->ntime > etime) )
281 {
282 do { marker = marker->flink; } while( marker->ntime <= etime );
283 }
284
285 /* insert event right before event pointed to by marker */
286 new->flink = marker;
287 new->blink = marker->blink;
288 marker->blink->flink = new;
289 marker->blink = new;
290 npending++;
291
292 /*
293 * thread event onto list of events for this node, keeping it
294 * in sorted order
295 */
296 if( (n->events != NULL) and (n->events->ntime > etime) )
297 {
298 for( marker = n->events; (marker->nlink != NULL) and
299 (marker->nlink->ntime > etime); marker = marker->nlink );
300 new->nlink = marker->nlink;
301 marker->nlink = new;
302 }
303 else
304 {
305 new->nlink = n->events;
306 n->events = new;
307 }
308 }
309
310
311 /* same as enqueue_event, but assumes 0 delay and rise/fall time */
enqueue_input(n,newvalue)312 public void enqueue_input( n, newvalue )
313 register nptr n;
314 {
315 register evptr marker, new;
316 register Ulong etime;
317
318 /* Punt any pending events for this node. */
319 while( n->events != NULL )
320 free_event( n->events );
321
322 NEW_EVENT( new );
323
324 /* remember facts about this event */
325 new->ntime = etime = cur_delta;
326 new->rtime = new->delay = 0;
327 new->enode = new->p.cause = n;
328 new->eval = newvalue;
329 new->type = REVAL; /* anything, doesn't matter */
330
331 /* Add new event to HEAD of list at appropriate entry in event wheel */
332
333 marker = (evptr) & ev_array[ etime & TMASK ];
334 new->flink = marker->flink;
335 new->blink = marker;
336 marker->flink->blink = new;
337 marker->flink = new;
338 npending++;
339
340 /* thread event onto (now empty) list of events for this node */
341 new->nlink = NULL;
342 n->events = new;
343 }
344
345
346 /*
347 * Initialize event structures
348 */
init_event()349 public void init_event()
350 {
351 register int i;
352 register evhdr *event;
353
354 for( i = 0, event = &ev_array[0]; i < TSIZE; i += 1, event += 1 )
355 {
356 event->flink = event->blink = (evptr) event;
357 }
358 npending = 0;
359 spending = 0;
360 nevent = 0;
361 }
362
363
PuntEvent(node,ev)364 public void PuntEvent( node, ev )
365 nptr node;
366 evptr ev;
367 {
368 if( node->nflags & WATCHED )
369 lprintf( stdout,
370 " punting transition of %s -> %c scheduled for %2.2fns\n",
371 node->nname, vchars[ev->eval], d2ns( ev->ntime ) );
372
373 ASSERT( node == ev->enode )
374 {
375 lprintf( stderr, "bad punt @ %d for %s\n", cur_delta, node->nname );
376 node->events = NULL;
377 return;
378 }
379
380 if( ev->type != DECAY_EV ) /* don't save punted decay events */
381 AddPunted( ev->enode, ev, cur_delta );
382 free_event( ev );
383 }
384
385
requeue_events(evlist,thread)386 public void requeue_events( evlist, thread )
387 evptr evlist;
388 int thread;
389 {
390 register Ulong etime;
391 register evptr ev, next, target;
392
393 npending = 0;
394 spending = 0;
395 for( ev = evlist; ev != NULL; ev = next )
396 {
397 next = ev->flink;
398
399 npending++;
400 etime = ev->ntime;
401 target = (evptr) & ev_array[ etime & TMASK ];
402
403 if( (target->blink != target) and (target->blink->ntime > etime) )
404 {
405 do { target = target->flink; } while( target->ntime <= etime );
406 }
407
408 ev->flink = target;
409 ev->blink = target->blink;
410 target->blink->flink = ev;
411 target->blink = ev;
412
413 if (ev->type == TIMED_EV)
414 spending++;
415 else if (thread)
416 {
417 register nptr n = ev->enode;
418 register evptr marker;
419
420 if( (n->events != NULL) and (n->events->ntime > etime) )
421 {
422 for( marker = n->events; (marker->nlink != NULL) and
423 (marker->nlink->ntime > etime); marker = marker->nlink );
424 ev->nlink = marker->nlink;
425 marker->nlink = ev;
426 }
427 else
428 {
429 ev->nlink = n->events;
430 n->events = ev;
431 }
432 }
433 }
434 }
435
436 /* Incremental simulation routines */
437
438 /*
439 * Back the event queues up to time 'btime'. This is the opposite of
440 * advancing the simulation time. Mark all pending events as PENDING,
441 * and re-enqueue them according to their creation-time (ntime - delay).
442 */
443
back_sim_time(btime,is_inc)444 public evptr back_sim_time( btime, is_inc )
445 Ulong btime;
446 int is_inc;
447 {
448 evptr tmplist;
449 register int nevents;
450 register evptr ev, next;
451 register evhdr *hdr, *endhdr;
452
453 nevents = 0;
454 tmplist = NULL;
455
456 /* first empty out the time wheel onto the temporary list */
457 for( endhdr = &ev_array[ TSIZE ], hdr = ev_array; hdr != endhdr ; hdr++ )
458 {
459 for( ev = hdr->flink; ev != (evptr) hdr; ev = next )
460 {
461 next = ev->flink;
462
463 ev->blink->flink = ev->flink; /* remove event */
464 ev->flink->blink = ev->blink;
465 if( is_inc )
466 free_from_node( ev, ev->enode );
467
468 if( (not is_inc) and ev->ntime - ev->delay >= btime )
469 {
470 free_from_node( ev, ev->enode );
471 ev->flink = evfree;
472 evfree = ev;
473 }
474 else
475 {
476 ev->flink = tmplist; /* move it to tmp list */
477 tmplist = ev;
478
479 nevents++;
480 }
481 }
482 }
483
484 if( not is_inc )
485 {
486 requeue_events( tmplist, FALSE );
487 return( NULL );
488 }
489
490 if( is_inc != TRUE ) /* only for fault simulation (is_inc == 2) */
491 {
492 npending = 0;
493 return( tmplist );
494 }
495
496 /* now move the temporary list to the time wheel */
497 for( ev = tmplist; ev != NULL; ev = next )
498 {
499 register Ulong etime;
500 register evptr target;
501
502 next = ev->flink;
503
504 ev->ntime -= ev->delay;
505 if (ev->type != TIMED_EV) ev->type = PENDING;
506 etime = ev->ntime;
507 target = (evptr) & ev_array[ etime & TMASK ];
508
509 if( (target->blink != target) and (target->blink->ntime > etime) )
510 {
511 do { target = target->flink; } while( target->ntime <= etime );
512 }
513
514 ev->flink = target;
515 ev->blink = target->blink;
516 target->blink->flink = ev;
517 target->blink = ev;
518 }
519
520 npending = nevents;
521 return( NULL );
522 }
523
524
525 /*
526 * Enqueue event type 'type' form history entry 'hist' for node 'nd'.
527 * Note that events with type > THREAD are not threaded onto a node's list
528 * of pending events, since we don't want the new_val routines to look at
529 * this event, instead we keep track of these events in the c.event event
530 * of every node. Return FALSE if this history entry is the sentinel
531 * (last_hist), otherwise return TRUE.
532 */
EnqueueHist(nd,hist,type)533 public int EnqueueHist( nd, hist, type )
534 nptr nd;
535 hptr hist;
536 int type;
537 {
538 register evptr marker, new;
539 register Ulong etime;
540
541 if( hist == last_hist ) /* never queue this up */
542 {
543 nd->c.event = NULL;
544 return( FALSE );
545 }
546
547 NEW_EVENT( new );
548
549 /* remember facts about this event */
550 new->ntime = etime = hist->time;
551 new->eval = hist->val;
552 new->enode = nd;
553 new->p.hist = hist;
554 if( hist->punt )
555 {
556 new->delay = hist->t.p.delay;
557 new->rtime = hist->t.p.rtime;
558 }
559 else
560 {
561 new->delay = hist->t.r.delay;
562 new->rtime = hist->t.r.rtime;
563 }
564
565 marker = (evptr) & ev_array[ etime & TMASK ];
566
567 /* Check whether we need to insert-sort in the list */
568 if( (marker->blink != marker) and (marker->blink->ntime > etime) )
569 {
570 do { marker = marker->flink; } while( marker->ntime <= etime );
571 }
572
573 /* insert event right before event pointed to by marker */
574 new->flink = marker;
575 new->blink = marker->blink;
576 marker->blink->flink = new;
577 marker->blink = new;
578 npending++;
579
580 if( hist->inp )
581 type |= IS_INPUT;
582 else if( new->delay == 0 )
583 type |= IS_XINPUT;
584 new->type = type;
585
586 if( type > THREAD )
587 {
588 nd->c.event = new;
589 return( TRUE );
590 }
591
592 if( (nd->events != NULL) and (nd->events->ntime > etime) )
593 {
594 for( marker = nd->events; (marker->nlink != NULL) and
595 (marker->nlink->ntime > etime); marker = marker->nlink );
596 new->nlink = marker->nlink;
597 marker->nlink = new;
598 }
599 else
600 {
601 new->nlink = nd->events;
602 nd->events = new;
603 }
604 return( TRUE );
605 }
606
607 /*
608 * Find a scheduled event in the event queue and return a pointer to it.
609 */
610
FindScheduled(idx)611 public evptr FindScheduled(idx)
612 short idx;
613 {
614 register evptr ev, next;
615 register evhdr *hdr, *endhdr;
616
617 for (endhdr = &ev_array[TSIZE], hdr = ev_array; hdr != endhdr; hdr++)
618 {
619 for (ev = hdr->flink; ev != (evptr) hdr; ev = next)
620 {
621 next = ev->flink;
622 if ((ev->type == TIMED_EV) && (ev->rtime == idx))
623 {
624 return ev;
625 }
626 }
627 }
628 return NULL;
629 }
630
631 /*
632 * Remove a scheduled event from the event queue
633 */
634
DequeueScheduled(idx)635 public void DequeueScheduled(idx)
636 short idx;
637 {
638 register evptr ev;
639
640 ev = FindScheduled(idx);
641 if (ev) free_event(ev);
642 }
643
644 /*
645 * Remove a pending event from the event queue and from the node
646 * that generated it.
647 */
648
DequeueEvent(nd)649 public void DequeueEvent( nd )
650 register nptr nd;
651 {
652 register evptr ev;
653
654 ev = nd->c.event;
655 ev->blink->flink = ev->flink;
656 ev->flink->blink = ev->blink;
657 ev->flink = evfree;
658 evfree = ev;
659 nd->c.event = NULL;
660
661 npending--;
662 }
663
664
DelayEvent(ev,delay)665 public void DelayEvent( ev, delay )
666 evptr ev;
667 long delay;
668 {
669 register evptr marker, new;
670 register nptr nd;
671 Ulong etime;
672
673 nd = ev->enode;
674 NEW_EVENT( new );
675
676 /* remember facts about this event */
677 *new = *ev;
678 new->delay += delay;
679 new->ntime += delay;
680
681 etime = new->ntime;
682
683 marker = (evptr) & ev_array[ etime & TMASK ];
684
685 /* Check whether we need to insert-sort in the list */
686 if( (marker->blink != marker) and (marker->blink->ntime > etime) )
687 {
688 do { marker = marker->flink; } while( marker->ntime <= etime );
689 }
690
691 /* insert event right before event pointed to by marker */
692 new->flink = marker;
693 new->blink = marker->blink;
694 marker->blink->flink = new;
695 marker->blink = new;
696 npending++;
697
698 if( new->type > THREAD )
699 {
700 nd->c.event = new;
701 return;
702 }
703
704 if( (nd->events != NULL) and (nd->events->ntime > etime) )
705 {
706 for( marker = nd->events; (marker->nlink != NULL) and
707 (marker->nlink->ntime > etime); marker = marker->nlink );
708 new->nlink = marker->nlink;
709 marker->nlink = new;
710 }
711 else
712 {
713 new->nlink = nd->events;
714 nd->events = new;
715 }
716 }
717
718
EnqueueOther(type,time)719 public evptr EnqueueOther( type, time )
720 int type;
721 Ulong time;
722 {
723 register evptr marker, new;
724 Ulong etime;
725
726 NEW_EVENT( new );
727
728 new->ntime = etime = time;
729 new->type = type;
730
731 if (new->type == TIMED_EV) spending++;
732
733 marker = (evptr) & ev_array[ etime & TMASK ];
734
735 /* Check whether we need to insert-sort in the list */
736 if( (marker->blink != marker) and (marker->blink->ntime > etime) )
737 {
738 do { marker = marker->flink; } while( marker->ntime <= etime );
739 }
740
741 /* insert event right before event pointed to by marker */
742 new->flink = marker;
743 new->blink = marker->blink;
744 marker->blink->flink = new;
745 marker->blink = new;
746 npending++;
747 return( new );
748 }
749
750
751 /*
752 * Remove any events that may be left from the incremental simulation.
753 */
rm_inc_events(all)754 public void rm_inc_events( all )
755 int all;
756 {
757 register int nevents;
758 register evptr ev, next;
759 register evhdr *hdr, *endhdr;
760
761 nevents = 0;
762
763 for( endhdr = &ev_array[ TSIZE ], hdr = ev_array; hdr != endhdr; hdr++ )
764 {
765 for( ev = hdr->flink; ev != (evptr) hdr; ev = next )
766 {
767 next = ev->flink;
768 if( all or ev->type >= THREAD )
769 {
770 ev->blink->flink = next; /* remove event */
771 ev->flink->blink = ev->blink;
772 ev->flink = evfree;
773 evfree = ev;
774 if( ev->type <= THREAD )
775 free_from_node( ev, ev->enode );
776 }
777 else
778 nevents++;
779 }
780 }
781 npending = nevents;
782 }
783