gb_gates.w

来自「模拟器提供了一个简单易用的平台」· W 代码 · 共 1,677 行 · 第 1/5 页

        /* set $l=\null$memory address */
    if (trace_regs) @<Print register contents@>;
    if (l>=size) break; /* stop if memory check occurs */
    for (v=g->vertices+1,m=rom[l];v<=g->vertices+16;v++,m>>=1)
      v->val=m&1; /* store bits of memory word in the input gates */
    gate_eval(g,NULL,NULL); /* do another RISC cycle */
  }
  if (trace_regs) @<Print a footline@>;
  @<Dump the register contents into |risc_state|@>;
  return 0;
}

@ If tracing is requested, we write on the standard output file.

@<Print a headline@>=
{
  for (r=0;r<trace_regs;r++) printf(" r%-2ld ",r); /* register names */
  printf(" P XSNKV MEM\n"); /* |prog|, |extra|, status bits, memory */
}

@ @<Print a footline@>=
printf("Execution terminated with memory address %04lx.\n",l);

@ Here we peek inside the circuit to see what values are about to
be latched.

@<Print register contents@>=
{ for (r=0;r<trace_regs;r++) {
    v=g->vertices+(16*r+47); /* most significant bit of register |r| */
    m=0;
    if (v->typ=='L')
      for (k=0,m=0;k<16;k++,v--) m=2*m+v->alt->val;
    printf("%04lx ",m);
  }
  for (k=0,m=0,v=g->vertices+26;k<10;k++,v--) m=2*m+v->alt->val; /* |prog| */
  x=(g->vertices+31)->alt->val; /* |extra| */
  s=(g->vertices+27)->alt->val; /* |sign| */
  n=(g->vertices+28)->alt->val; /* |nonzero| */
  c=(g->vertices+29)->alt->val; /* |carry| */
  o=(g->vertices+30)->alt->val; /* |overflow| */
  printf("%03lx%c%c%c%c%c ",m<<2,
     x?'X':'.', s?'S':'.', n?'N':'.', c?'K':'.', o?'V':'.');
  if (l>=size) printf("????\n");
  else printf("%04lx\n",rom[l]);
}

@ @<Dump...@>=
for (r=0;r<16;r++) {
  v=g->vertices+(16*r+47); /* most significant bit of register |r| */
  m=0;
  if (v->typ=='L')
    for (k=0,m=0;k<16;k++,v--) m=2*m+v->alt->val;
  risc_state[r]=m;
}
for (k=0,m=0,v=g->vertices+26;k<10;k++,v--) m=2*m+v->alt->val; /* |prog| */
m=4*m+(g->vertices+31)->alt->val; /* |extra| */
m=2*m+(g->vertices+27)->alt->val; /* |sign| */
m=2*m+(g->vertices+28)->alt->val; /* |nonzero| */
m=2*m+(g->vertices+29)->alt->val; /* |carry| */
m=2*m+(g->vertices+30)->alt->val; /* |overflow| */
risc_state[16]=m; /* program register and status bits go here */
risc_state[17]=l;
 /* this is the out-of-range address that caused termination */

@ @<Global variables@>=
unsigned long risc_state[18];

@*Generalized gate graphs. For intermediate computations, it is
convenient to allow two additional types of gates:
{\advance\parindent 2em
\smallskip
\item{|'C'|} denotes a constant gate of value |z.I|.

\smallskip
\item{|'='|} denotes a copy of a previous gate; utility field |alt|
points to that previous gate.

\smallskip}\noindent
Such gates might appear anywhere in the graph, possibly interspersed with
the inputs and latches.

Here is a simple subroutine that prints a symbolic representation of
a generalized gate graph on the standard output file:

@d bit z.I /* field containing the constant value of a |'C'| gate */
@d print_gates p_gates /* abbreviation makes chopped-off name unique */

@<The |print_gates| routine@>=
static void pr_gate(v)
  Vertex *v;
{@+register Arc *a;
  printf("%s = ",v->name);
  switch(v->typ) {
  case 'I':printf("input");@+break;
  case 'L':printf("latch");
    if (v->alt) printf("ed %s",v->alt->name);
    break;
  case '~':printf("~ ");@+break;
  case 'C':printf("constant %ld",v->bit); break;
  case '=':printf("copy of %s",v->alt->name);
  }
  for (a=v->arcs;a;a=a->next) {
    if (a!=v->arcs) printf(" %c ",(char)v->typ);
    printf(a->tip->name);
  }
  printf("\n");
}
@#
void print_gates(g)
  Graph *g;
{@+register Vertex *v;
  register Arc *a;
  for (v=g->vertices;v<g->vertices+g->n;v++) pr_gate(v);
  for (a=g->outs;a;a=a->next)
    if (is_boolean(a->tip)) printf("Output %ld\n",the_boolean(a->tip));
    else printf("Output %s\n",a->tip->name);
}

@ @(gb_gates.h@>=
#define bit @t\quad@> z.I

@ The |reduce| routine takes a generalized graph |g| and uses the identities
$\overline{\overline x}=x$ and
$$\openup1\jot
\vbox{\halign{\hfil$x#0=\null$&$#$,\hfil\quad
             &\hfil$x#1=\null$&$#$,\hfil\quad
             &\hfil$x#x=\null$&$#$,\hfil\quad
             &\hfil$x#\overline x=\null$&$#$,\hfil\cr
\land&0&\land&x&\land&x&\land&0\cr
\lor&x&\lor&1&\lor&x&\lor&1\cr
\oplus&x&\oplus&\overline x&\oplus&0&\oplus&1\cr}}$$
to create an equivalent graph having no
|'C'| or |'='| or obviously redundant gates. The reduced graph also excludes
any gates that are not used directly or indirectly in the computation of
the output values.

@<Internal...@>=
static Graph* reduce(g)
  Graph *g;
{@+register Vertex *u, *v; /* the current vertices of interest */
  register Arc *a, *b; /* the current arcs of interest */
  Arc *aa, *bb; /* their predecessors */
  Vertex *latch_ptr; /* top of the latch list */
  long n=0; /* the number of marked gates */
  Graph *new_graph; /* the reduced gate graph */
  Vertex *next_vert=NULL, *max_next_vert=NULL; /* allocation of new vertices */
  Arc *avail_arc=NULL; /* list of recycled arcs */
  Vertex *sentinel; /* end of the vertices */
  if (g==NULL) panic(missing_operand); /* where is |g|? */
  sentinel=g->vertices+g->n;
  while (1) {
    latch_ptr=NULL;
    for (v=g->vertices;v<sentinel;v++)
      @<Reduce gate |v|, if possible, or put it on the latch list@>;
    @<Check to see if any latch has become constant; if not, |break|@>;
  }
  @<Mark all gates that are used in some output@>;
  @<Copy all marked gates to a new graph@>;
  gb_recycle(g);
  return new_graph;
}

@ We will link latches together via their |v.V| fields.

@<Check to see if any latch has become constant; if not, |break|@>=
{@+char no_constants_yet=1;
  for (v=latch_ptr;v;v=v->v.V) {
    u=v->alt; /* the gate whose value will be latched */
    if (u->typ=='=')
      v->alt=u->alt;
    else if (u->typ=='C') {
      v->typ='C';@+v->bit=u->bit;@+no_constants_yet=0;
    }
  }
  if (no_constants_yet) break;
}

@ @d foo x.V /* link field used to find all the gates later */

@<Reduce gate |v|, if possible, or put it on the latch list@>=
{
  switch(v->typ) {
    case 'L': v->v.V=latch_ptr;@+latch_ptr=v;@+break;
    case 'I': case 'C': break;
    case '=': u=v->alt;
      if (u->typ=='=')
        v->alt=u->alt;
      else if (u->typ=='C') {
        v->bit=u->bit;@+goto make_v_constant;
      }
      break;
    case NOT:@<Try to reduce an inverter, then |goto done|@>;
    case AND:@<Try to reduce an {\sc AND} gate@>;@+goto test_single_arg;
    case OR:@<Try to reduce an {\sc OR} gate@>;@+goto test_single_arg;
    case XOR:@<Try to reduce an {\sc EXCLUSIVE-OR} gate@>;
  test_single_arg: if (v->arcs->next) break;
    v->alt=v->arcs->tip;
  make_v_eq: v->typ='=';@+goto make_v_arcless;
  make_v_1: v->bit=1;@+goto make_v_constant;
  make_v_0: v->bit=0;
  make_v_constant: v->typ='C';
  make_v_arcless: v->arcs=NULL;
  }
v->bar=NULL; /* this field will point to the complement, if computed later */
done: v->foo=v+1; /* this field will link all the vertices together */
}

@ @<Try to reduce an inverter...@>=
u=v->arcs->tip;
if (u->typ=='=')
  u=v->arcs->tip=u->alt;
if (u->typ=='C') {
  v->bit=1-u->bit;@+goto make_v_constant;
}@+else if (u->bar) { /* this inverse already computed */
  v->alt=u->bar;@+goto make_v_eq;
}@+else {
  u->bar=v;@+v->bar=u;@+goto done;
}

@ @<Try to reduce an {\sc AND} gate@>=
for (a=v->arcs,aa=NULL;a;a=a->next) {
  u=a->tip;
  if (u->typ=='=')
    u=a->tip=u->alt;
  if (u->typ=='C') {
    if (u->bit==0) goto make_v_0;
    goto bypass_and;
  }@+else@+for (b=v->arcs;b!=a;b=b->next) {
    if (b->tip==u) goto bypass_and;
    if (b->tip==u->bar) goto make_v_0;
  }
  aa=a;@+continue;
bypass_and: if (aa) aa->next=a->next;
  else v->arcs=a->next;
}
if (v->arcs==NULL) goto make_v_1;

@ @<Try to reduce an {\sc OR} gate@>=
for (a=v->arcs,aa=NULL;a;a=a->next) {
  u=a->tip;
  if (u->typ=='=')
    u=a->tip=u->alt;
  if (u->typ=='C') {
    if (u->bit) goto make_v_1;
    goto bypass_or;
  }@+else@+for (b=v->arcs;b!=a;b=b->next) {
    if (b->tip==u) goto bypass_or;
    if (b->tip==u->bar) goto make_v_1;
  }
  aa=a;@+continue;
bypass_or: if (aa) aa->next=a->next;
  else v->arcs=a->next;
}
if (v->arcs==NULL) goto make_v_0;

@ @<Try to reduce an {\sc EXCLUSIVE-OR} gate@>=
{@+long cmp=0;
  for (a=v->arcs,aa=NULL;a;a=a->next) {
    u=a->tip;
    if (u->typ=='=')
      u=a->tip=u->alt;
    if (u->typ=='C') {
      if (u->bit) cmp=1-cmp;
      goto bypass_xor;
    }@+else@+for (bb=NULL,b=v->arcs;b!=a;b=b->next) {
      if (b->tip==u) goto double_bypass;
      if (b->tip==u->bar) {
        cmp=1-cmp;
        goto double_bypass;
      }
      bb=b;@+ continue;
    double_bypass: if (bb) bb->next=b->next;
      else v->arcs=b->next;
      goto bypass_xor;
    }
    aa=a;@+ continue;
  bypass_xor: if (aa) aa->next=a->next;
    else v->arcs=a->next;
    a->a.A=avail_arc;
    avail_arc=a;
  }
  if (v->arcs==NULL) {
    v->bit=cmp;
    goto make_v_constant;
  }
  if (cmp) @<Complement one argument of |v|@>;
}

@ @<Complement one argument of |v|@>=
{
  for (a=v->arcs;;a=a->next) {
    u=a->tip;
    if (u->bar) break; /* good, the complement is already known */
    if (a->next==NULL) { /* oops, this is our last chance */
      @<Create a new vertex for complement of |u|@>;
      break;
    }
  }
  a->tip=u->bar;
}

@ Here we've come to a subtle point: If a lot of |XOR| gates involve
an input that is set to the constant value~1, the ``reduced'' graph
might actually be larger than the original, in the sense of having
more vertices (although fewer arcs).  Therefore we must have the
ability to allocate new vertices during the reduction phase of
|reduce|. At least one arc has been added to the |avail_arc| list
whenever we reach this portion of the program.

@<Create a new vertex for complement of |u|@>=
if (next_vert==max_next_vert) {
  next_vert=gb_typed_alloc(7,Vertex,g->aux_data);
  if (next_vert==NULL) {
    gb_recycle(g);
    panic(no_room+1); /* can't get auxiliary storage! */
  }
  max_next_vert=next_vert+7;
}
next_vert->typ=NOT;
sprintf(name_buf,"%s~",u->name);
next_vert->name=gb_save_string(name_buf);
next_vert->arcs=avail_arc; /* this is known to be non-|NULL| */
avail_arc->tip=u;
avail_arc=avail_arc->a.A;
next_vert->arcs->next=NULL;
next_vert->bar=u;
next_vert->foo=u->foo;
u->foo=u->bar=next_vert++;

@ During the marking phase, we will use the |w.V| field to link the
list of nodes-to-be-marked. That field will turn out to be non-|NULL|
only in the marked nodes. (We no longer use its former meaning related
to complementation, so we call it |lnk| instead of |bar|.)

@d lnk w.V /* stack link for marking */