gb_gates.w

模拟器提供了一个简单易用的平台

\.K and~\.V, as follows: Shifting left sets \.K to~1 if and
only if at least one of the bits shifted off the left was nonzero,
and sets \.V to~1 if and only if the corresponding multiplication
would cause overflow.
Shifting right~1 sets \.K to the value of the bit
shifted out, and sets \.V to~0;
shifting right~4 sets \.K to the value of the last
bit shifted out, and sets \.V to the logical {\sc OR} of the other three
lost bits. The same values of \.K and \.V arise from cyclic or unsigned
shifts as from ordinary shifts.

When $\.{OP}=1$ and $\.{MOD}=8$, the source value is added to the
destination register. This sets \.S, \.N, and \.V as you would expect;
and it sets \.K to the carry you would get if you were treating the operands
as 16-bit unsigned integers. Another addition operation, having
$\.{MOD}=9$, is similar, but the current value of \.K is also added to
the result; in this case, the new value of \.N will be zero if and only if
the 15 non-sign bits of the result are zero and the previous values of
\.S and~\.N were also zero. This means
that you can use the first addition operation on the lower
halves of a 32-bit number and the second operation on the upper halves,
thereby obtaining a correct 32-bit result, with appropriate sign,
nonzero, carry, and overflow bits set.
Higher precision (48 bits, 64 bits, etc.)~can be obtained in a similar way.

When $\.{OP}=1$ and $\.{MOD}=10$, the source value is subtracted
from the destination register. Again, \.S, \.N, \.K, and \.V are set;
the \.K value in this case represents the ``borrow'' bit.
An auxiliary subtraction operation, having $\.{MOD}=11$, subtracts
also the current value of \.K, thereby allowing for correct 32-bit subtraction.

The operations for $\.{OP}=1$ and $\.{MOD}=12$, 13, and~14 are
``reserved for future expansion.'' Actually they will never change, however,
since this RISC chip is purely academic. If you check out the logic
below, you will find that they simply set the destination register and
the four status bits all to zero.

A final operation, called \.{JUMP}, will be explained momentarily.
It has $\.{OP}=1$ and $\.{MOD}=15$. It does not affect \.S, \.N, \.K, or~\.V.

If the RISC is made with fewer than 16 registers, the higher-numbered ones
will effectively contain zero whenever their values are fetched.
But if you use them as destination registers, you will set
\.S, \.N, \.K, and~\.V as if actual numbers were being stored.

Register 0 is different from the other 15 registers: It is the location
of the current instruction. Therefore if you change the contents of
register~0, you are changing the control flow of the program. If you
do not change register~0, it automatically increases by~1.

Special treatment occurs when $\.A=3$ and $\.{SRC}=0$.
In such a case, the normal rules given above say that the source value
should be the contents of the memory location specified by register~0. But
that memory location holds the current instruction; so the machine
uses the {\sl following\/} location instead, as a 16-bit source
operand. If the contents of register~0 are not changed by such a
two-word instruction, register~0 will increase by~2 instead of~1.

We have now discussed everything about the machine except the operation
of the \.{JUMP} command. This command moves the source value to
register~0, thereby changing the flow of control. Furthermore, if
$\.{DST}\ne0$, it also sets register \.{DST} to the location of the
instruction following the \.{JUMP}. Assembly language programmers will
recognize this as a convenient way to jump to a subroutine.

Example programs can be found in the {\sc TAKE\_\,RISC} module, which includes
a simple subroutine for multiplication and division.

@ A few auxiliary functions will ameliorate the task of constructing
the RISC logic. First comes a routine that ``christens'' a new gate,
assigning it a name and a type. The name is constructed from a prefix
and a serial number, where the prefix indicates the current portion of
logic being created.

@<Internal...@>=
static Vertex* new_vert(t)
  char t; /* the type of the new gate */
{@+register Vertex *v;
  v=next_vert++;
  if (count<0) v->name=gb_save_string(prefix);
  else {
    sprintf(name_buf,"%s%ld",prefix,count);
    v->name=gb_save_string(name_buf);
    count++;
  }
  v->typ=t;
  return v;
}

@ @d start_prefix(s) strcpy(prefix,s);@+count=0
@d numeric_prefix(a,b) sprintf(prefix,"%c%ld:",a,b);@+count=0;

@<Private...@>=
static Vertex* next_vert; /* the first vertex not yet assigned a name */
static char prefix[5]; /* prefix string for vertex names */
static long count; /* serial number for vertex names */
static char name_buf[100]; /* place to form vertex names */

@ Here are some trivial routines to create gates with 2, 3, or more
arguments. The arcs from such a gate to its inputs are assigned length 100.
Other routines, defined below,
assign length~1 to the arc between an inverter and its unique
input. This convention makes the lengths of shortest paths in the resulting
network a bit more interesting than they would otherwise be.

@d DELAY 100L

@<Internal...@>=
static Vertex* make2(t,v1,v2)
  char t; /* the type of the new gate */
  Vertex *v1,*v2;
{@+register Vertex *v=new_vert(t);
  gb_new_arc(v,v1,DELAY);
  gb_new_arc(v,v2,DELAY);
  return v;
}
@#
static Vertex* make3(t,v1,v2,v3)
  char t; /* the type of the new gate */
  Vertex *v1,*v2,*v3;
{@+register Vertex *v=new_vert(t);
  gb_new_arc(v,v1,DELAY);
  gb_new_arc(v,v2,DELAY);
  gb_new_arc(v,v3,DELAY);
  return v;
}
@#
static Vertex* make4(t,v1,v2,v3,v4)
  char t; /* the type of the new gate */
  Vertex *v1,*v2,*v3,*v4;
{@+register Vertex *v=new_vert(t);
  gb_new_arc(v,v1,DELAY);
  gb_new_arc(v,v2,DELAY);
  gb_new_arc(v,v3,DELAY);
  gb_new_arc(v,v4,DELAY);
  return v;
}
@#
static Vertex* make5(t,v1,v2,v3,v4,v5)
  char t; /* the type of the new gate */
  Vertex *v1,*v2,*v3,*v4,*v5;
{@+register Vertex *v=new_vert(t);
  gb_new_arc(v,v1,DELAY);
  gb_new_arc(v,v2,DELAY);
  gb_new_arc(v,v3,DELAY);
  gb_new_arc(v,v4,DELAY);
  gb_new_arc(v,v5,DELAY);
  return v;
}

@ We use utility field |w.V| to store a pointer to the complement
of a gate, if that complement has been formed. This trick prevents the creation
of excessive gates that are equivalent to each other. The following subroutine
returns a pointer to the complement of a given gate.

@d bar w.V /* field pointing to complement, if known to exist */
@d even_comp(s,v) ((s)&1? v: comp(v))

@<Internal...@>=
static Vertex* comp(v)
  Vertex *v;
{@+register Vertex *u;
  if (v->bar) return v->bar;
  u=next_vert++;
  u->bar=v;@+v->bar=u;
  sprintf(name_buf,"%s~",v->name);
  u->name=gb_save_string(name_buf);
  u->typ=NOT;
  gb_new_arc(u,v,1L);
  return u;
}

@ To create a gate for the {\sc EXCLUSIVE-OR} of two arguments, we can
either construct the {\sc OR} of two {\sc AND}s or the {\sc AND} of two
{\sc OR}s. We choose the former alternative:

@<Internal...@>=
static Vertex* make_xor(u,v)
  Vertex *u,*v;
{@+register Vertex *t1,*t2;
  t1=make2(AND,u,comp(v));
  t2=make2(AND,comp(u),v);
  return make2(OR,t1,t2);
}

@ OK, let's get going.

@<Initialize |new_graph|...@>=
if (regs<2 || regs>16) regs=16;
new_graph=gb_new_graph(1400+115*regs);
if (new_graph==NULL)
  panic(no_room); /* out of memory before we're even started */
sprintf(new_graph->id,"risc(%lu)",regs);
strcpy(new_graph->util_types,"ZZZIIVZZZZZZZA");
next_vert=new_graph->vertices;

@ @<Add the RISC data to |new_graph|@>=
@<Create the inputs and latches@>;
@<Create gates for instruction decoding@>;
@<Create gates for fetching the source value@>;
@<Create gates for the general logic operation@>;
@<Create gates for the conditional load operations@>;
@<Create gates for the arithmetic operations@>;
@<Create gates that bring everything together properly@>;
if (next_vert!=new_graph->vertices+new_graph->n)
  panic(impossible); /* oops, we miscounted; this should be impossible */

@ Internal names will make it convenient to refer to the most important
gates. Here are the names of inputs and latches.

@<Local variables for |risc|@>=
Vertex *run_bit; /* the \.{RUN} input */
Vertex *mem[16]; /* 16 bits of input from read-only memory */
Vertex *prog; /* first of 10 bits in the program register */
Vertex *sign; /* the latched value of \.S */
Vertex *nonzero; /* the latched value of \.N */
Vertex *carry; /* the latched value of \.K */
Vertex *overflow; /* the latched value of \.V */
Vertex *extra; /* latched status bit: are we doing an extra memory cycle? */
Vertex *reg[16]; /* the least-significant bit of a given register */

@ @d first_of(n,t) new_vert(t);@+for (k=1;k<n;k++)@+new_vert(t);

@<Create the inputs and latches@>=
strcpy(prefix,"RUN");@+count=-1;@+run_bit=new_vert('I');
start_prefix("M");@+for (k=0;k<16;k++)@+mem[k]=new_vert('I');
start_prefix("P");@+prog=first_of(10,'L');
strcpy(prefix,"S");@+count=-1;@+sign=new_vert('L');
strcpy(prefix,"N");@+nonzero=new_vert('L');
strcpy(prefix,"K");@+carry=new_vert('L');
strcpy(prefix,"V");@+overflow=new_vert('L');
strcpy(prefix,"X");@+extra=new_vert('L');
for (r=0;r<regs;r++) {
  numeric_prefix('R',r);
  reg[r]=first_of(16,'L');
}

@ The order of evaluation of function arguments is not defined in \CEE/,
so we introduce a few macros that force left-to-right order.

@d do2(result,t,v1,v2)
     {@+t1=v1;@+t2=v2;
     result=make2(t,t1,t2);@+}
@d do3(result,t,v1,v2,v3)
     {@+t1=v1;@+t2=v2;@+t3=v3;
     result=make3(t,t1,t2,t3);@+}
@d do4(result,t,v1,v2,v3,v4)
     {@+t1=v1;@+t2=v2;@+t3=v3;@+t4=v4;
     result=make4(t,t1,t2,t3,t4);@+}
@d do5(result,t,v1,v2,v3,v4,v5)
     {@+t1=v1;@+t2=v2;@+t3=v3;@+t4=v4;@+t5=v5;
     result=make5(t,t1,t2,t3,t4,t5);@+}

@<Local variables for |risc|@>=
Vertex *t1,*t2,*t3,*t4,*t5; /* temporary holds to force evaluation order */
Vertex *tmp[16]; /* additional holding places for partial results */
Vertex *imm; /* is the source value immediate (a given constant)? */
Vertex *rel; /* is the source value relative to the
                  current destination register? */
Vertex *dir; /* should the source value be fetched directly
                  from a source register? */
Vertex *ind; /* should the source value be fetched indirectly from memory? */
Vertex *op; /* least significant bit of \.{OP} */
Vertex *cond; /* most significant bit of \.{OP} */
Vertex *mod[4]; /* the \.{MOD} bits */
Vertex *dest[4]; /* the \.{DEST} bits */

@ The sixth line of the program here can be translated into the logic
equation
$$ |op|=(|extra|\land|prog|)\lor(\mskip1mu\overline{|extra|}\land|mem[6]|)\,.$$
Once you see why, you'll be able to read the rest of this curious code.

@<Create gates for instruction decoding@>=
start_prefix("D");
do3(imm,AND,comp(extra),comp(mem[4]),comp(mem[5])); /* $\.A=0$ */
do3(rel,AND,comp(extra),mem[4],comp(mem[5])); /* $\.A=1$ */
do3(dir,AND,comp(extra),comp(mem[4]),mem[5]); /* $\.A=2$ */
do3(ind,AND,comp(extra),mem[4],mem[5]); /* $\.A=3$ */
do2(op,OR,make2(AND,extra,prog),make2(AND,comp(extra),mem[6]));
do2(cond,OR,make2(AND,extra,prog+1),make2(AND,comp(extra),mem[7]));
for (k=0;k<4;k++) {
  do2(mod[k],OR,make2(AND,extra,prog+2+k),make2(AND,comp(extra),mem[8+k]));
  do2(dest[k],OR,make2(AND,extra,prog+6+k),make2(AND,comp(extra),mem[12+k]));
}

@ @<Create gates for fetching the source value@>=
start_prefix("F");
@<Set |old_dest| to the present value of the destination register@>;
@<Set |old_src| to the present value of the source register@>;
@<Set |inc_dest| to |old_dest| plus \.{SRC}@>;
for (k=0;k<16;k++)@/
  do4(source[k],OR,
    make2(AND,imm,mem[k<4?k:3]),
    make2(AND,rel,inc_dest[k]),@|
    make2(AND,dir,old_src[k]),
    make2(AND,extra,mem[k]));

@ Here and in the immediately following section we create {\sc OR}
gates |old_dest[k]| and |old_src[k]| that might have as many as
16~inputs. (The actual number of inputs is |regs|.) All other
gates in the network will have at most five inputs.

@<Set |old_dest| to the present value of the destination register@>=
for (r=0;r<regs;r++) @/
  do4(dest_match[r],AND,even_comp(r,dest[0]),even_comp(r>>1,dest[1]),@|
                          even_comp(r>>2,dest[2]),even_comp(r>>3,dest[3]));
for (k=0;k<16;k++) {
  for (r=0;r<regs;r++)@/
    tmp[r]=make2(AND,dest_match[r],reg[r]+k);
  old_dest[k]=new_vert(OR);
  for (r=0;r<regs;r++) gb_new_arc(old_dest[k],tmp[r],DELAY);
}

@ @<Set |old_src| to the present value of the source register@>=
for (k=0;k<16;k++) {
  for (r=0;r<regs;r++)@/
    do5(tmp[r],AND,reg[r]+k,even_comp(r,mem[0]),even_comp(r>>1,mem[1]),
                            even_comp(r>>2,mem[2]),even_comp(r>>3,mem[3]));
  old_src[k]=new_vert(OR);
  for (r=0;r<regs;r++) gb_new_arc(old_src[k],tmp[r],DELAY);
}

@ @<Local variables for |risc|@>=
Vertex *dest_match[16]; /* |dest_match[r]==1| iff $\.{DST}=r$ */
Vertex *old_dest[16]; /* contents of destination register before operation */
Vertex *old_src[16]; /* contents of source register before operation */
Vertex *inc_dest[16]; /* |old_dest| plus the \.{SRC} field */
Vertex *source[16]; /* source value for the operation */
Vertex *log[16]; /* result of general logic operation */
Vertex *shift[18]; /* result of shift operation, with carry and overflow */
Vertex *sum[18]; /* |old_dest| plus |source| plus optional carry */
Vertex *diff[18]; /* |old_dest| minus |source| minus optional borrow */
Vertex *next_loc[16]; /* contents of register 0, plus 1 */
Vertex *next_next_loc[16]; /* contents of register 0, plus 2 */
Vertex *result[18]; /* result of operating on |old_dest| and |source| */