Subversion Repositories eco32

% This file is part of the MMIXware package (c) Donald E Knuth 1999

% This file is part of the MMIXware package (c) Donald E Knuth 1999

@i boilerplate.w %<< legal stuff: PLEASE READ IT BEFORE MAKING ANY CHANGES!

@i boilerplate.w %<< legal stuff: PLEASE READ IT BEFORE MAKING ANY CHANGES!

\def\title{MMIX-PIPE}

\def\title{MMIX-PIPE}

\def\MMIX{\.{MMIX}}

\def\MMIX{\.{MMIX}}

\def\NNIX{\hbox{\mc NNIX}}

\def\NNIX{\hbox{\mc NNIX}}

\def\Hex#1{\hbox{$^{\scriptscriptstyle\#}$\tt#1}} % experimental hex constant

\def\Hex#1{\hbox{$^{\scriptscriptstyle\#}$\tt#1}} % experimental hex constant

@s and normal @q unreserve a C++ keyword @>

@s and normal @q unreserve a C++ keyword @>

@s or normal @q unreserve a C++ keyword @>

@s or normal @q unreserve a C++ keyword @>

@s bool normal @q unreserve a C++ keyword @>

@s bool normal @q unreserve a C++ keyword @>

@s xor normal @q unreserve a C++ keyword @>

@s xor normal @q unreserve a C++ keyword @>

@* Introduction. This program is the heart of the meta-simulator for the

@* Introduction. This program is the heart of the meta-simulator for the

ultra-configurable \MMIX\ pipeline: It defines the |MMIX_run| routine, which

ultra-configurable \MMIX\ pipeline: It defines the |MMIX_run| routine, which

does most of the

does most of the

work. Another routine, |MMIX_init|, is also defined here, and so is a header

work. Another routine, |MMIX_init|, is also defined here, and so is a header

file called \.{mmix\_pipe.h}. The header file is used by the main routine and

file called \.{mmix\_pipe.h}. The header file is used by the main routine and

by other routines like |MMIX_config|, which are compiled separately.

by other routines like |MMIX_config|, which are compiled separately.

Readers of this program should be familiar with the explanation of \MMIX\

Readers of this program should be familiar with the explanation of \MMIX\

architecture as presented in the main program module for {\mc MMMIX}.

architecture as presented in the main program module for {\mc MMMIX}.

A lot of subtle things can happen when instructions are executed in parallel.

A lot of subtle things can happen when instructions are executed in parallel.

Therefore this simulator ranks among the most interesting and instructive

Therefore this simulator ranks among the most interesting and instructive

programs in the author's experience. The author has tried his best to make

programs in the author's experience. The author has tried his best to make

everything correct \dots\ but the chances for error are great. Anyone who

everything correct \dots\ but the chances for error are great. Anyone who

discovers a bug is therefore urged to report it as soon as possible to

discovers a bug is therefore urged to report it as soon as possible to

\.{knuth-bug@@cs.stanford.edu}; then the program will be as useful as

\.{knuth-bug@@cs.stanford.edu}; then the program will be as useful as

possible. Rewards will be paid to bug-finders! (Except for bugs in version~0.)

possible. Rewards will be paid to bug-finders! (Except for bugs in version~0.)

It sort of boggles the mind when one realizes that the present program might

It sort of boggles the mind when one realizes that the present program might

someday be translated by a \CEE/~compiler for \MMIX\ and used to simulate

someday be translated by a \CEE/~compiler for \MMIX\ and used to simulate

{\it itself}.

{\it itself}.

@ This high-performance prototype of \MMIX\ achieves its efficiency by

@ This high-performance prototype of \MMIX\ achieves its efficiency by

means of ``pipelining,'' a technique of overlapping that is explained

means of ``pipelining,'' a technique of overlapping that is explained

for the related \.{DLX} computer in Chapter~3 of Hennessy \char`\&\ Patterson's

for the related \.{DLX} computer in Chapter~3 of Hennessy \char`\&\ Patterson's

book {\sl Computer Architecture\/} (second edition). Other techniques

book {\sl Computer Architecture\/} (second edition). Other techniques

such as ``dynamic scheduling'' and ``multiple issue,'' explained in

such as ``dynamic scheduling'' and ``multiple issue,'' explained in

Chapter~4 of that book, are used too.

Chapter~4 of that book, are used too.

One good way to visualize the procedure is to imagine that somebody has

One good way to visualize the procedure is to imagine that somebody has

organized a high-tech car repair shop according to similar principles.

organized a high-tech car repair shop according to similar principles.

There are eight independent functional units, which we can think of as

There are eight independent functional units, which we can think of as

eight groups of auto mechanics, each specializing in a particular task;

eight groups of auto mechanics, each specializing in a particular task;

each group has its own workspace with room to deal with one car at a time.

each group has its own workspace with room to deal with one car at a time.

Group~F (the ``fetch'' group) is in charge of rounding up customers and

Group~F (the ``fetch'' group) is in charge of rounding up customers and

getting them to enter the assembly-line garage in an orderly fashion.

getting them to enter the assembly-line garage in an orderly fashion.

Group~D (the ``decode and dispatch'' group) does the initial vehicle

Group~D (the ``decode and dispatch'' group) does the initial vehicle

inspection and

inspection and

writes up an order that explains what kind of servicing is required.

writes up an order that explains what kind of servicing is required.

The vehicles go next to one of the four ``execution'' groups:

The vehicles go next to one of the four ``execution'' groups:

Group~X handles routine maintenance, while groups XF, XM, and XD are

Group~X handles routine maintenance, while groups XF, XM, and XD are

specialists in more complex tasks that tend to take longer. (The XF

specialists in more complex tasks that tend to take longer. (The XF

people are good at floating the points, while the XM and XD groups are

people are good at floating the points, while the XM and XD groups are

experts in multilink suspensions and differentials.) When the relevant X~group

experts in multilink suspensions and differentials.) When the relevant X~group

has finished its work, cars drive to M~station, where they send or receive

has finished its work, cars drive to M~station, where they send or receive

messages and possibly pay money to members of the ``memory'' group. Finally

messages and possibly pay money to members of the ``memory'' group. Finally

all necessary parts are installed by members of group~W, the ``write''

all necessary parts are installed by members of group~W, the ``write''

group, and the car leaves the shop. Everything is tightly organized so

group, and the car leaves the shop. Everything is tightly organized so

that in most cases the cars move in synchronized fashion from station

that in most cases the cars move in synchronized fashion from station

to station, at regular 100-nanocentury intervals. % about 5.3 minutes

to station, at regular 100-nanocentury intervals. % about 5.3 minutes

In a similar way, most \MMIX\ instructions can be handled in a five-stage

In a similar way, most \MMIX\ instructions can be handled in a five-stage

pipeline, F--D--X--M--W, with X replaced by XF for floating-point

pipeline, F--D--X--M--W, with X replaced by XF for floating-point

addition or conversion, or by XM for multiplication, or by XD for

addition or conversion, or by XM for multiplication, or by XD for

division or square root. Each stage ideally takes one clock cycle,

division or square root. Each stage ideally takes one clock cycle,

although XF, XM, and (especially) XD are slower. If the instructions enter

although XF, XM, and (especially) XD are slower. If the instructions enter

in a suitable pattern, we might see one instruction being fetched,

in a suitable pattern, we might see one instruction being fetched,

another being decoded, and up to four being executed, while another is accessing

another being decoded, and up to four being executed, while another is accessing

memory, and yet another is finishing up by writing new information into

memory, and yet another is finishing up by writing new information into

registers; all this is going on simultaneously during one clock cycle. Pipelining

registers; all this is going on simultaneously during one clock cycle. Pipelining

with eight separate stages might therefore make the machine run

with eight separate stages might therefore make the machine run

up to 8 times as fast as it could if each instruction were being dealt with

up to 8 times as fast as it could if each instruction were being dealt with

individually and without overlap. (Well, perfect speedup turns out to

individually and without overlap. (Well, perfect speedup turns out to

be impossible, because of the shared M and~W stages; the theory of

be impossible, because of the shared M and~W stages; the theory of

knapsack programming, to be discussed in Section~7.7 of {\sl The Art

knapsack programming, to be discussed in Section~7.7 of {\sl The Art

of Computer Programming}, tells us that the maximal achievable speedup is

of Computer Programming}, tells us that the maximal achievable speedup is

at most $8-1/p-1/q-1/r$ when XF, XM, and~XD have delays bounded by $p$,

at most $8-1/p-1/q-1/r$ when XF, XM, and~XD have delays bounded by $p$,

$q$, and~$r$ cycles. But we can achieve a factor of more than~7

$q$, and~$r$ cycles. But we can achieve a factor of more than~7

if we are very lucky.)

if we are very lucky.)

Consider, for example, the \.{ADD} instruction. This instruction enters

Consider, for example, the \.{ADD} instruction. This instruction enters

the computer's processing unit in F stage, taking only one clock cycle if

the computer's processing unit in F stage, taking only one clock cycle if

it is in the cache of instructions recently seen. Then the D~stage

it is in the cache of instructions recently seen. Then the D~stage

recognizes the command as an \.{ADD} and acquires the current values

recognizes the command as an \.{ADD} and acquires the current values

of \$Y and \$Z; meanwhile, of course, another instruction is being fetched

of \$Y and \$Z; meanwhile, of course, another instruction is being fetched

by~F.

by~F.

On the next clock cycle, the X stage adds the values together.

On the next clock cycle, the X stage adds the values together.

This prepares the way for the M stage to watch for overflow and to

This prepares the way for the M stage to watch for overflow and to

get ready for any exceptional action that might be needed with respect

get ready for any exceptional action that might be needed with respect

to the settings of special register~rA\null.

to the settings of special register~rA\null.

Finally, on the fifth clock cycle, the sum is either written into~\$X

Finally, on the fifth clock cycle, the sum is either written into~\$X

or the trip handler for integer overflow is invoked.

or the trip handler for integer overflow is invoked.

Although this process has taken five clock

Although this process has taken five clock

cycles (that is, $5\upsilon$),

cycles (that is, $5\upsilon$),

the net increase in running time has been only~$1\upsilon$.

the net increase in running time has been only~$1\upsilon$.

Of course congestion can occur, inside a computer as in a repair shop.

Of course congestion can occur, inside a computer as in a repair shop.

For example, auto parts might not be readily available; or a car might

For example, auto parts might not be readily available; or a car might

have to sit in D station while waiting to move to XM, thereby blocking

have to sit in D station while waiting to move to XM, thereby blocking

somebody else from moving from F to~D.  Sometimes there won't

somebody else from moving from F to~D.  Sometimes there won't

necessarily be a steady stream of customers.  In such cases the

necessarily be a steady stream of customers.  In such cases the

employees in some parts of the shop will occasionally be idle.  But we

employees in some parts of the shop will occasionally be idle.  But we

assume that they always do their jobs as fast as possible, given the

assume that they always do their jobs as fast as possible, given the

sequence of customers that they encounter. With a clever person

sequence of customers that they encounter. With a clever person

setting up appointments---translation: with a clever

setting up appointments---translation: with a clever

programmer and/or compiler arranging \MMIX\ instructions---the

programmer and/or compiler arranging \MMIX\ instructions---the

organization can often be expected to run at nearly peak capacity.

organization can often be expected to run at nearly peak capacity.

In fact, this program is designed for experiments with many kinds of

In fact, this program is designed for experiments with many kinds of

pipelines, potentially using additional functional units (such as

pipelines, potentially using additional functional units (such as

several independent X~groups), and potentially fetching, dispatching, and

several independent X~groups), and potentially fetching, dispatching, and

executing several nonconflicting instructions simultaneously.

executing several nonconflicting instructions simultaneously.

Such complications

Such complications

make this program more difficult than a simple pipeline simulator

make this program more difficult than a simple pipeline simulator

would be, but they also make it a lot more instructive because we

would be, but they also make it a lot more instructive because we

can get a better understanding of the issues involved if we are

can get a better understanding of the issues involved if we are

required to treat them in greater generality.

required to treat them in greater generality.

@ Here's the overall structure of the present program module.

@ Here's the overall structure of the present program module.

@c

@c

#include 

#include 

#include 

#include 

#include 

#include 

#include "abstime.h"

#include "abstime.h"

@h@#

@h@#

@
@;

@
@;

@@;

@@;

@@;

@@;

@@;

@@;

@@;

@@;

@@;

@@;

@@;

@@;

@@;

@@;

@ The identifier \&{Extern} is used in {\mc MMIX-PIPE} to

@ The identifier \&{Extern} is used in {\mc MMIX-PIPE} to

declare variables that are accessed in other modules. Actually

declare variables that are accessed in other modules. Actually

all appearances of `\&{Extern}' are defined to be blank here, but

all appearances of `\&{Extern}' are defined to be blank here, but

`\&{Extern}' will become `\&{extern}' in the header file.

`\&{Extern}' will become `\&{extern}' in the header file.

@d Extern  /* blank for us, \&{extern} for them */

@d Extern  /* blank for us, \&{extern} for them */

@f Extern extern

@f Extern extern

@=

@=

Extern int verbose; /* controls the level of diagnostic output */

Extern int verbose; /* controls the level of diagnostic output */

@ The header file repeats the basic definitions and declarations.

@ The header file repeats the basic definitions and declarations.

@(mmix-pipe.h@>=

@(mmix-pipe.h@>=

#define Extern extern

#define Extern extern

@
@;

@
@;

@@;

@@;

@@;

@@;

@@;

@@;

@ Subroutines of this program are declared first with a prototype,

@ Subroutines of this program are declared first with a prototype,

as in {\mc ANSI C}, then with an old-style \CEE/ function definition.

as in {\mc ANSI C}, then with an old-style \CEE/ function definition.

The following preprocessor commands make this work correctly with both

The following preprocessor commands make this work correctly with both

new-style and old-style compilers.

new-style and old-style compilers.

@^prototypes for functions@>

@^prototypes for functions@>

@
=

@
=

#ifdef __STDC__

#ifdef __STDC__

#define ARGS(list) list

#define ARGS(list) list

#else

#else

#define ARGS(list) ()

#define ARGS(list) ()

#endif

#endif

@ Some of the names that are natural for this program are in

@ Some of the names that are natural for this program are in

conflict with library names on at least

conflict with library names on at least

one of the host computers in the author's tests. So we

one of the host computers in the author's tests. So we

bypass the library names here.

bypass the library names here.

@
=

@
=

#define random my_random

#define random my_random

#define fsqrt my_fsqrt

#define fsqrt my_fsqrt

#define div my_div

#define div my_div

@ The amount of verbosity depends on the following bit codes.

@ The amount of verbosity depends on the following bit codes.

@
=

@
=

#define issue_bit (1<<0)

#define issue_bit (1<<0)

   /* show control blocks when issued, deissued, committed */

   /* show control blocks when issued, deissued, committed */

#define pipe_bit (1<<1)

#define pipe_bit (1<<1)

   /* show the pipeline and locks on every cycle */

   /* show the pipeline and locks on every cycle */

#define coroutine_bit (1<<2)

#define coroutine_bit (1<<2)

   /* show the coroutines when started on every cycle */

   /* show the coroutines when started on every cycle */

#define schedule_bit (1<<3)

#define schedule_bit (1<<3)

   /* show the coroutines when scheduled */

   /* show the coroutines when scheduled */

#define uninit_mem_bit (1<<4)

#define uninit_mem_bit (1<<4)

   /* complain when reading from an uninitialized chunk of memory */

   /* complain when reading from an uninitialized chunk of memory */

#define interactive_read_bit (1<<5)

#define interactive_read_bit (1<<5)

   /* prompt user when reading from I/O location */

   /* prompt user when reading from I/O location */

#define show_spec_bit (1<<6)

#define show_spec_bit (1<<6)

   /* display special read/write transactions as they happen */

   /* display special read/write transactions as they happen */

#define show_pred_bit (1<<7)

#define show_pred_bit (1<<7)

   /* display branch prediction details */

   /* display branch prediction details */

#define show_wholecache_bit (1<<8)

#define show_wholecache_bit (1<<8)

   /* display cache blocks even when their key tag is invalid */

   /* display cache blocks even when their key tag is invalid */

@ The |MMIX_init()| routine should be called exactly once, after

@ The |MMIX_init()| routine should be called exactly once, after

|MMIX_config()| has done its work but before the simulator starts to execute

|MMIX_config()| has done its work but before the simulator starts to execute

any programs. Then |MMIX_run| can be called as often as the user likes.

any programs. Then |MMIX_run| can be called as often as the user likes.

@s octa int

@s octa int

@=

@=

Extern void MMIX_init @,@,@[ARGS((void))@];

Extern void MMIX_init @,@,@[ARGS((void))@];

Extern void MMIX_run @,@,@[ARGS((int cycs, octa breakpoint))@];

Extern void MMIX_run @,@,@[ARGS((int cycs, octa breakpoint))@];

@ @=

@ @=

void MMIX_init()

void MMIX_init()

{

{

  register int i,j;

  register int i,j;

  @;

  @;

}

}

@#

@#

void MMIX_run(cycs,breakpoint)

void MMIX_run(cycs,breakpoint)

  int cycs;

  int cycs;

  octa breakpoint;

  octa breakpoint;

{

{

  @;

  @;

  while (cycs) {

  while (cycs) {

    if (verbose&(issue_bit|pipe_bit|coroutine_bit|schedule_bit))

    if (verbose&(issue_bit|pipe_bit|coroutine_bit|schedule_bit))

      printf("*** Cycle %d\n", ticks.l);

      printf("*** Cycle %d\n", ticks.l);

    @;

    @;

    if (verbose&pipe_bit) {

    if (verbose&pipe_bit) {

      print_pipe();@+ print_locks();

      print_pipe();@+ print_locks();

    }

    }

    if (breakpoint_hit||halted) {

    if (breakpoint_hit||halted) {

      if (breakpoint_hit)

      if (breakpoint_hit)

        printf("Breakpoint instruction fetched at time %d\n",ticks.l-1);

        printf("Breakpoint instruction fetched at time %d\n",ticks.l-1);

      if (halted) printf("Halted at time %d\n", ticks.l-1);

      if (halted) printf("Halted at time %d\n", ticks.l-1);

      break;

      break;

    }

    }

    cycs--;

    cycs--;

  }

  }

 cease:;

 cease:;

}

}

@ @=

@ @=

typedef enum {@!false, @!true, @!wow}@+bool; /* slightly extended booleans */

typedef enum {@!false, @!true, @!wow}@+bool; /* slightly extended booleans */

@ @=

@ @=

register int i,j,m;

register int i,j,m;

bool breakpoint_hit=false;

bool breakpoint_hit=false;

bool halted=false;

bool halted=false;

@ Error messages that abort this program are called panic messages.

@ Error messages that abort this program are called panic messages.

The macro called |confusion| will never be needed unless this program is

The macro called |confusion| will never be needed unless this program is

internally inconsistent.

internally inconsistent.

@d errprint0(f) fprintf(stderr,f)

@d errprint0(f) fprintf(stderr,f)

@d errprint1(f,a) fprintf(stderr,f,a)

@d errprint1(f,a) fprintf(stderr,f,a)

@d errprint2(f,a,b) fprintf(stderr,f,a,b)

@d errprint2(f,a,b) fprintf(stderr,f,a,b)

@d panic(x)@+ {@+errprint0("Panic: ");@+x;@+errprint0("!\n");@+expire();@+}

@d panic(x)@+ {@+errprint0("Panic: ");@+x;@+errprint0("!\n");@+expire();@+}

@d confusion(m) errprint1("This can't happen: %s",m)

@d confusion(m) errprint1("This can't happen: %s",m)

@.This can't happen@>

@.This can't happen@>

@=

@=

static void expire @,@,@[ARGS((void))@];

static void expire @,@,@[ARGS((void))@];

@ @=

@ @=

static void expire() /* the last gasp before dying */

static void expire() /* the last gasp before dying */

{

{

  if (ticks.h) errprint2("(Clock time is %dH+%d.)\n",ticks.h,ticks.l);

  if (ticks.h) errprint2("(Clock time is %dH+%d.)\n",ticks.h,ticks.l);

  else errprint1("(Clock time is %d.)\n",ticks.l);

  else errprint1("(Clock time is %d.)\n",ticks.l);

@.Clock time is...@>

@.Clock time is...@>

  exit(-2);

  exit(-2);

}

}

@ The data structures of this program are not precisely equivalent to

@ The data structures of this program are not precisely equivalent to

logical gates that could be implemented directly in silicon;

logical gates that could be implemented directly in silicon;

we will use data structures and

we will use data structures and

algorithms appropriate to the \CEE/ programming language. For example,

algorithms appropriate to the \CEE/ programming language. For example,

we'll use pointers and arrays, instead of buses and ports and latches. However,

we'll use pointers and arrays, instead of buses and ports and latches. However,

the net effect of our data structures and algorithms is intended to

the net effect of our data structures and algorithms is intended to

be equivalent to the net effect of a silicon implementation. The methods

be equivalent to the net effect of a silicon implementation. The methods

used below are essentially equivalent to those used in real machines today,

used below are essentially equivalent to those used in real machines today,

except that diagnostic facilities are added so that we can readily

except that diagnostic facilities are added so that we can readily

watch what is happening.

watch what is happening.

Each functional unit in the \MMIX\ pipeline is programmed here as a coroutine

Each functional unit in the \MMIX\ pipeline is programmed here as a coroutine

in~\CEE/. At every clock cycle, we will call on each active coroutine to do one

in~\CEE/. At every clock cycle, we will call on each active coroutine to do one

phase of its operation; in terms of the repair-station analogy

phase of its operation; in terms of the repair-station analogy

described in the main program,

described in the main program,

this corresponds to getting each group of

this corresponds to getting each group of

auto mechanics to do one unit of operation on a car.

auto mechanics to do one unit of operation on a car.

The coroutines are performed sequentially, although

The coroutines are performed sequentially, although

a real pipeline would have them act in parallel.

a real pipeline would have them act in parallel.

We will not ``cheat'' by letting one coroutine access a value early in its

We will not ``cheat'' by letting one coroutine access a value early in its

cycle that another one computes late in its cycle, unless computer hardware

cycle that another one computes late in its cycle, unless computer hardware

could ``cheat'' in an equivalent way.

could ``cheat'' in an equivalent way.

@* Low-level routines. Where should we begin? It is tempting to start with a

@* Low-level routines. Where should we begin? It is tempting to start with a

global view of the simulator and then to break it down into component parts.

global view of the simulator and then to break it down into component parts.

But that task is too daunting, because there are so many unknowns about what

But that task is too daunting, because there are so many unknowns about what

basic ingredients ought to be combined when we construct the larger

basic ingredients ought to be combined when we construct the larger

components. So let us look first at the primitive operations on which

components. So let us look first at the primitive operations on which

the superstructure will be built. Once we have created some infrastructure,

the superstructure will be built. Once we have created some infrastructure,

we'll be able to proceed with confidence to the larger tasks ahead.

we'll be able to proceed with confidence to the larger tasks ahead.

@ This program for the 64-bit \MMIX\ architecture is based on 32-bit integer

@ This program for the 64-bit \MMIX\ architecture is based on 32-bit integer

arithmetic, because nearly every computer available to the author at the time

arithmetic, because nearly every computer available to the author at the time

of writing (1998--1999) was limited in that way.

of writing (1998--1999) was limited in that way.

Details of the basic arithmetic appear in a separate program module

Details of the basic arithmetic appear in a separate program module

called {\mc MMIX-ARITH}, because the same routines are needed also

called {\mc MMIX-ARITH}, because the same routines are needed also

for the assembler and for the non-pipelined simulator. The

for the assembler and for the non-pipelined simulator. The

definition of type \&{tetra} should be changed, if necessary, to conform with

definition of type \&{tetra} should be changed, if necessary, to conform with

the definitions found there.

the definitions found there.

@^system dependencies@>

@^system dependencies@>

@=

@=

typedef unsigned int tetra;

typedef unsigned int tetra;

  /* for systems conforming to the LP-64 data model */

  /* for systems conforming to the LP-64 data model */

typedef struct { tetra h,l;} octa; /* two tetrabytes make one octabyte */

typedef struct { tetra h,l;} octa; /* two tetrabytes make one octabyte */

@ @=

@ @=

static void print_octa @,@,@[ARGS((octa))@];

static void print_octa @,@,@[ARGS((octa))@];

@ @=

@ @=

static void print_octa(o)

static void print_octa(o)

  octa o;

  octa o;

{

{

  if (o.h) printf("%x%08x",o.h,o.l);@+

  if (o.h) printf("%x%08x",o.h,o.l);@+

  else printf("%x",o.l);

  else printf("%x",o.l);

}

}

@ @=

@ @=

extern octa zero_octa; /* |zero_octa.h=zero_octa.l=0| */

extern octa zero_octa; /* |zero_octa.h=zero_octa.l=0| */

extern octa neg_one; /* |neg_one.h=neg_one.l=-1| */

extern octa neg_one; /* |neg_one.h=neg_one.l=-1| */

extern octa aux; /* auxiliary output of a subroutine */

extern octa aux; /* auxiliary output of a subroutine */

extern bool overflow; /* set by certain subroutines for signed arithmetic */

extern bool overflow; /* set by certain subroutines for signed arithmetic */

extern int exceptions; /* bits set by floating point operations */

extern int exceptions; /* bits set by floating point operations */

extern int cur_round; /* the current rounding mode */

extern int cur_round; /* the current rounding mode */

@ Most of the subroutines in {\mc MMIX-ARITH} return an octabyte as

@ Most of the subroutines in {\mc MMIX-ARITH} return an octabyte as

a function of two octabytes; for example, |oplus(y,z)| returns the

a function of two octabytes; for example, |oplus(y,z)| returns the

sum of octabytes |y| and~|z|. Multiplication returns the high

sum of octabytes |y| and~|z|. Multiplication returns the high

half of a product in the global variable~|aux|; division returns

half of a product in the global variable~|aux|; division returns

the remainder in~|aux|.

the remainder in~|aux|.

@=

@=

extern octa oplus @,@,@[ARGS((octa y,octa z))@];

extern octa oplus @,@,@[ARGS((octa y,octa z))@];

  /* unsigned $y+z$ */

  /* unsigned $y+z$ */

extern octa ominus @,@,@[ARGS((octa y,octa z))@];

extern octa ominus @,@,@[ARGS((octa y,octa z))@];

  /* unsigned $y-z$ */

  /* unsigned $y-z$ */

extern octa incr @,@,@[ARGS((octa y,int delta))@];

extern octa incr @,@,@[ARGS((octa y,int delta))@];

  /* unsigned $y+\delta$ ($\delta$ is signed) */

  /* unsigned $y+\delta$ ($\delta$ is signed) */

extern octa oand @,@,@[ARGS((octa y,octa z))@];

extern octa oand @,@,@[ARGS((octa y,octa z))@];

  /* $y\land z$ */

  /* $y\land z$ */

extern octa oandn @,@,@[ARGS((octa y,octa z))@];

extern octa oandn @,@,@[ARGS((octa y,octa z))@];

  /* $y\land \bar z$ */

  /* $y\land \bar z$ */

extern octa shift_left @,@,@[ARGS((octa y,int s))@];

extern octa shift_left @,@,@[ARGS((octa y,int s))@];

  /* $y\LL s$, $0\le s\le64$ */

  /* $y\LL s$, $0\le s\le64$ */

extern octa shift_right @,@,@[ARGS((octa y,int s,int uns))@];

extern octa shift_right @,@,@[ARGS((octa y,int s,int uns))@];

  /* $y\GG s$, signed if |!uns| */

  /* $y\GG s$, signed if |!uns| */

extern octa omult @,@,@[ARGS((octa y,octa z))@];

extern octa omult @,@,@[ARGS((octa y,octa z))@];

  /* unsigned $(|aux|,x)=y\times z$ */

  /* unsigned $(|aux|,x)=y\times z$ */

extern octa signed_omult @,@,@[ARGS((octa y,octa z))@];

extern octa signed_omult @,@,@[ARGS((octa y,octa z))@];

  /* signed $x=y\times z$, setting |overflow| */

  /* signed $x=y\times z$, setting |overflow| */

extern octa odiv @,@,@[ARGS((octa x,octa y,octa z))@];

extern octa odiv @,@,@[ARGS((octa x,octa y,octa z))@];

  /* unsigned $(x,y)/z$; $|aux|=(x,y)\bmod z$ */

  /* unsigned $(x,y)/z$; $|aux|=(x,y)\bmod z$ */

extern octa signed_odiv @,@,@[ARGS((octa y,octa z))@];

extern octa signed_odiv @,@,@[ARGS((octa y,octa z))@];

  /* signed $y/z$, when $z\ne0$; $|aux|=y\bmod z$ */

  /* signed $y/z$, when $z\ne0$; $|aux|=y\bmod z$ */

extern int count_bits @,@,@[ARGS((tetra z))@];

extern int count_bits @,@,@[ARGS((tetra z))@];

  /* $x=\nu(z)$ */

  /* $x=\nu(z)$ */

extern tetra byte_diff @,@,@[ARGS((tetra y,tetra z))@];

extern tetra byte_diff @,@,@[ARGS((tetra y,tetra z))@];

  /* half of \.{BDIF} */

  /* half of \.{BDIF} */

extern tetra wyde_diff @,@,@[ARGS((tetra y,tetra z))@];

extern tetra wyde_diff @,@,@[ARGS((tetra y,tetra z))@];

  /* half of \.{WDIF} */

  /* half of \.{WDIF} */

extern octa bool_mult @,@,@[ARGS((octa y,octa z,bool xor))@];

extern octa bool_mult @,@,@[ARGS((octa y,octa z,bool xor))@];

  /* \.{MOR} or \.{MXOR} */

  /* \.{MOR} or \.{MXOR} */

extern octa load_sf @,@,@[ARGS((tetra z))@];

extern octa load_sf @,@,@[ARGS((tetra z))@];

  /* load short float */

  /* load short float */

extern tetra store_sf @,@,@[ARGS((octa x))@];

extern tetra store_sf @,@,@[ARGS((octa x))@];

  /* store short float */

  /* store short float */

extern octa fplus @,@,@[ARGS((octa y,octa z))@];

extern octa fplus @,@,@[ARGS((octa y,octa z))@];

  /* floating point $x=y\oplus z$ */

  /* floating point $x=y\oplus z$ */

extern octa fmult @,@,@[ARGS((octa y ,octa z))@];

extern octa fmult @,@,@[ARGS((octa y ,octa z))@];

  /* floating point $x=y\otimes z$ */

  /* floating point $x=y\otimes z$ */

extern octa fdivide @,@,@[ARGS((octa y,octa z))@];

extern octa fdivide @,@,@[ARGS((octa y,octa z))@];

  /* floating point $x=y\oslash z$ */

  /* floating point $x=y\oslash z$ */

extern octa froot @,@,@[ARGS((octa,int))@];

extern octa froot @,@,@[ARGS((octa,int))@];

  /* floating point $x=\sqrt z$ */

  /* floating point $x=\sqrt z$ */

extern octa fremstep @,@,@[ARGS((octa y,octa z,int delta))@];

extern octa fremstep @,@,@[ARGS((octa y,octa z,int delta))@];

  /* floating point $x\,{\rm rem}\,z=y\,{\rm rem}\,z$ */

  /* floating point $x\,{\rm rem}\,z=y\,{\rm rem}\,z$ */

extern octa fintegerize @,@,@[ARGS((octa z,int mode))@];

extern octa fintegerize @,@,@[ARGS((octa z,int mode))@];

  /* floating point $x={\rm round}(z)$ */

  /* floating point $x={\rm round}(z)$ */

extern int fcomp @,@,@[ARGS((octa y,octa z))@];

extern int fcomp @,@,@[ARGS((octa y,octa z))@];

  /* $-1$, 0, 1, or 2 if $yz$, $y\parallel z$ */

  /* $-1$, 0, 1, or 2 if $yz$, $y\parallel z$ */

extern int fepscomp @,@,@[ARGS((octa y,octa z,octa eps,int sim))@];

extern int fepscomp @,@,@[ARGS((octa y,octa z,octa eps,int sim))@];

  /* $x=|sim|?\ [y\sim z\ (\epsilon)]:\ [y\approx z\ (\epsilon)]$ */

  /* $x=|sim|?\ [y\sim z\ (\epsilon)]:\ [y\approx z\ (\epsilon)]$ */

extern octa floatit @,@,@[ARGS((octa z,int mode,int unsgnd,int shrt))@];

extern octa floatit @,@,@[ARGS((octa z,int mode,int unsgnd,int shrt))@];

  /* fix to float */

  /* fix to float */

extern octa fixit @,@,@[ARGS((octa z,int mode))@];

extern octa fixit @,@,@[ARGS((octa z,int mode))@];

  /* float to fix */

  /* float to fix */

@ We had better check that our 32-bit assumption holds.

@ We had better check that our 32-bit assumption holds.

@=

@=

if (shift_left(neg_one,1).h!=0xffffffff)

if (shift_left(neg_one,1).h!=0xffffffff)

  panic(errprint0("Incorrect implementation of type tetra"));

  panic(errprint0("Incorrect implementation of type tetra"));

@.Incorrect implementation...@>

@.Incorrect implementation...@>

@* Coroutines. As stated earlier, this program can be regarded as a system of

@* Coroutines. As stated earlier, this program can be regarded as a system of

interacting coroutines. Coroutines---sometimes called threads---are more or

interacting coroutines. Coroutines---sometimes called threads---are more or

less independent processes that share and pass data and control back and

less independent processes that share and pass data and control back and

forth. They correspond to the individual workers in an organization.

forth. They correspond to the individual workers in an organization.

We don't need the full power of recursive coroutines, in which new threads are

We don't need the full power of recursive coroutines, in which new threads are

spawned dynamically and have independent stacks for computation; we are, after

spawned dynamically and have independent stacks for computation; we are, after

all, simulating a fixed piece of hardware. The total number of coroutines we

all, simulating a fixed piece of hardware. The total number of coroutines we

deal with is established once and for all by the |MMIX_config| routine, and

deal with is established once and for all by the |MMIX_config| routine, and

each coroutine has a fixed amount of local data.

each coroutine has a fixed amount of local data.

The simulation operates one clock tick at a time, by executing all

The simulation operates one clock tick at a time, by executing all

coroutines scheduled for time~$t$ before advancing to time~$t+1$. The

coroutines scheduled for time~$t$ before advancing to time~$t+1$. The

coroutines at time~$t$ may decide to become dormant or they may reschedule

coroutines at time~$t$ may decide to become dormant or they may reschedule

themselves and/or other coroutines for future times.

themselves and/or other coroutines for future times.

Each coroutine has a symbolic |name| for diagnostic purposes (e.g.,

Each coroutine has a symbolic |name| for diagnostic purposes (e.g.,

\.{ALU1}); a nonnegative |stage| number (e.g., 2~for the second stage

\.{ALU1}); a nonnegative |stage| number (e.g., 2~for the second stage

of a pipeline); a pointer to the next coroutine scheduled at the same time (or

of a pipeline); a pointer to the next coroutine scheduled at the same time (or

|NULL| if the coroutine is unscheduled); a pointer to a lock variable

|NULL| if the coroutine is unscheduled); a pointer to a lock variable

(or |NULL| if no lock is currently relevant);

(or |NULL| if no lock is currently relevant);

and a reference to a control block containing the data to be processed.

and a reference to a control block containing the data to be processed.

@s control_struct int

@s control_struct int

@=

@=

typedef struct coroutine_struct {

typedef struct coroutine_struct {

 char *name; /* symbolic identification of a coroutine */

 char *name; /* symbolic identification of a coroutine */

 int stage; /* its rank */

 int stage; /* its rank */

 struct coroutine_struct *next; /* its successor */

 struct coroutine_struct *next; /* its successor */

 struct coroutine_struct **lockloc; /* what it might be locking */

 struct coroutine_struct **lockloc; /* what it might be locking */

 struct control_struct *ctl; /* its data */

 struct control_struct *ctl; /* its data */

} coroutine;

} coroutine;

@ @=

@ @=

static void print_coroutine_id @,@,@[ARGS((coroutine*))@];

static void print_coroutine_id @,@,@[ARGS((coroutine*))@];

static void errprint_coroutine_id @,@,@[ARGS((coroutine*))@];

static void errprint_coroutine_id @,@,@[ARGS((coroutine*))@];

@ @=

@ @=

static void print_coroutine_id(c)

static void print_coroutine_id(c)

  coroutine *c;

  coroutine *c;

{

{

  if (c) printf("%s:%d",c->name,c->stage);

  if (c) printf("%s:%d",c->name,c->stage);

  else printf("??");

  else printf("??");

}

}

@#

@#

static void errprint_coroutine_id(c)

static void errprint_coroutine_id(c)

  coroutine *c;

  coroutine *c;

{

{

  if (c) errprint2("%s:%d",c->name,c->stage);

  if (c) errprint2("%s:%d",c->name,c->stage);

  else errprint0("??");

  else errprint0("??");

@.??@>

@.??@>

}

}

@ Coroutine control is masterminded by a ring of queues, one each for

@ Coroutine control is masterminded by a ring of queues, one each for

times $t$, $t+1$, \dots, $t+|ring_size|-1$, when $t$ is the current

times $t$, $t+1$, \dots, $t+|ring_size|-1$, when $t$ is the current

clock time.

clock time.

All scheduling is first-come-first-served, except that coroutines with higher

All scheduling is first-come-first-served, except that coroutines with higher

|stage| numbers have priority. We want to process the later stages of a

|stage| numbers have priority. We want to process the later stages of a

pipeline first, in this sequential implementation, for the same reason that a

pipeline first, in this sequential implementation, for the same reason that a

car must drive from M~station into W~station before another car can enter

car must drive from M~station into W~station before another car can enter

M~station.

M~station.

Each queue is a circular list of \&{coroutine} nodes, linked together by their

Each queue is a circular list of \&{coroutine} nodes, linked together by their

|next| fields. A list head~$h$ with |stage=max_stage| comes at the end and the

|next| fields. A list head~$h$ with |stage=max_stage| comes at the end and the

beginning of the queue. (All |stage| numbers of legitimate coroutines

beginning of the queue. (All |stage| numbers of legitimate coroutines

are less than~|max_stage|.) The queued items are |h->next|, |h->next->next|,

are less than~|max_stage|.) The queued items are |h->next|, |h->next->next|,

etc., from back to front, and we have |c->stage<=c->next->stage| unless |c=h|.

etc., from back to front, and we have |c->stage<=c->next->stage| unless |c=h|.

Initially all queues are empty.

Initially all queues are empty.

@=

@=

{@+register coroutine *p;

{@+register coroutine *p;

  for (p=ring;pnext=p;

  for (p=ring;pnext=p;

}

}

@ To schedule a coroutine |c| with positive delay |d

@ To schedule a coroutine |c| with positive delay |d

|schedule(c,d,s)|. (The |s| parameter is used only if scheduling is

|schedule(c,d,s)|. (The |s| parameter is used only if scheduling is

being logged; it does not affect the computation, but we will

being logged; it does not affect the computation, but we will

generally set |s| to the state at which the scheduled coroutine will begin.)

generally set |s| to the state at which the scheduled coroutine will begin.)

@=

@=

static void schedule @,@,@[ARGS((coroutine*,int,int))@];

static void schedule @,@,@[ARGS((coroutine*,int,int))@];

@ @=

@ @=

static void schedule(c,d,s)

static void schedule(c,d,s)

  coroutine *c;

  coroutine *c;

  int d,s;

  int d,s;

{

{

  register int tt=(cur_time+d)%ring_size;

  register int tt=(cur_time+d)%ring_size;

  register coroutine *p=&ring[tt]; /* start at the list head */

  register coroutine *p=&ring[tt]; /* start at the list head */

  if (d<=0 || d>=ring_size) /* do a sanity check */

  if (d<=0 || d>=ring_size) /* do a sanity check */

   panic(confusion("Scheduling ");errprint_coroutine_id(c);

   panic(confusion("Scheduling ");errprint_coroutine_id(c);

         errprint1(" with delay %d",d));

         errprint1(" with delay %d",d));

  while (p->next->stagestage) p=p->next;

  while (p->next->stagestage) p=p->next;

  c->next = p->next;

  c->next = p->next;

  p->next = c;

  p->next = c;

  if (verbose&schedule_bit) {

  if (verbose&schedule_bit) {

    printf(" scheduling ");@+print_coroutine_id(c);

    printf(" scheduling ");@+print_coroutine_id(c);

    printf(" at time %d, state %d\n",ticks.l+d,s);

    printf(" at time %d, state %d\n",ticks.l+d,s);

  }

  }

}

}

@ @=

@ @=

Extern int ring_size; /* set by |MMIX_config|, must be sufficiently large */

Extern int ring_size; /* set by |MMIX_config|, must be sufficiently large */

Extern coroutine *ring;

Extern coroutine *ring;

Extern int cur_time;

Extern int cur_time;

@ The all-important |ctl| field of a coroutine, which contains the

@ The all-important |ctl| field of a coroutine, which contains the

data being manipulated, will be explained below. One of its key

data being manipulated, will be explained below. One of its key

components is the |state| field, which helps to specify the next

components is the |state| field, which helps to specify the next

actions the coroutine will perform. When we schedule a coroutine for

actions the coroutine will perform. When we schedule a coroutine for

a new task, we often want it to begin in state~0.

a new task, we often want it to begin in state~0.

@=

@=

static void startup @,@,@[ARGS((coroutine*,int))@];

static void startup @,@,@[ARGS((coroutine*,int))@];

@ @=

@ @=

static void startup(c,d)

static void startup(c,d)

  coroutine *c;

  coroutine *c;

  int d;

  int d;

{

{

  c->ctl->state=0;

  c->ctl->state=0;

  schedule(c,d,0);

  schedule(c,d,0);

}

}

@ The following routine removes a coroutine from whatever queue it's in.

@ The following routine removes a coroutine from whatever queue it's in.

The case |c->next=c| is also permitted; such a self-loop can occur when a

The case |c->next=c| is also permitted; such a self-loop can occur when a

coroutine goes to sleep and expects to be awakened (that is, scheduled)

coroutine goes to sleep and expects to be awakened (that is, scheduled)

by another coroutine. Sleeping coroutines have important data in their

by another coroutine. Sleeping coroutines have important data in their

|ctl| field; they are therefore quite different from unscheduled

|ctl| field; they are therefore quite different from unscheduled

or ``unemployed'' coroutines, which have |c->next=NULL|. An unemployed

or ``unemployed'' coroutines, which have |c->next=NULL|. An unemployed

coroutine is not assumed to have any valid data in its |ctl| field.

coroutine is not assumed to have any valid data in its |ctl| field.

@=

@=

static void unschedule @,@,@[ARGS((coroutine*))@];

static void unschedule @,@,@[ARGS((coroutine*))@];

@ @=

@ @=

static void unschedule(c)

static void unschedule(c)

  coroutine *c;

  coroutine *c;

{@+register coroutine *p;

{@+register coroutine *p;

  if (c->next) {

  if (c->next) {

    for (p=c; p->next!=c; p=p->next) ;

    for (p=c; p->next!=c; p=p->next) ;

    p->next = c->next;

    p->next = c->next;

    c->next=NULL;

    c->next=NULL;

    if (verbose&schedule_bit) {

    if (verbose&schedule_bit) {

      printf(" unscheduling ");@+print_coroutine_id(c);@+printf("\n");

      printf(" unscheduling ");@+print_coroutine_id(c);@+printf("\n");

    }

    }

  }

  }

}

}

@ When it is time to process all coroutines that have queued up for a

@ When it is time to process all coroutines that have queued up for a

particular time~|t|, we empty the queue called |ring[t]| and link its items in

particular time~|t|, we empty the queue called |ring[t]| and link its items in

the opposite order (from front to back). The following subroutine uses the

the opposite order (from front to back). The following subroutine uses the

well known algorithm discussed in exercise 2.2.3--7 of {\sl The Art

well known algorithm discussed in exercise 2.2.3--7 of {\sl The Art

of Computer Programming}.

of Computer Programming}.

@=

@=

static coroutine *queuelist @,@,@[ARGS((int))@];

static coroutine *queuelist @,@,@[ARGS((int))@];

@ @=

@ @=

static coroutine* queuelist(t)

static coroutine* queuelist(t)

  int t;

  int t;

{@+register coroutine *p, *q=&sentinel, *r;

{@+register coroutine *p, *q=&sentinel, *r;

  for (p=ring[t].next;p!=&ring[t];p=r) {

  for (p=ring[t].next;p!=&ring[t];p=r) {

    r=p->next;

    r=p->next;

    p->next=q;

    p->next=q;

    q=p;

    q=p;

  }

  }

  ring[t].next=&ring[t];

  ring[t].next=&ring[t];

  sentinel.next=q;

  sentinel.next=q;

  return q;

  return q;

}

}

@ @=

@ @=

coroutine sentinel; /* dummy coroutine at origin of circular list */

coroutine sentinel; /* dummy coroutine at origin of circular list */

@ Coroutines often start working on tasks that are {\it speculative}, in the

@ Coroutines often start working on tasks that are {\it speculative}, in the

sense that we want certain results to be ready if they prove to be

sense that we want certain results to be ready if they prove to be

useful; we understand that speculative computations might not actually

useful; we understand that speculative computations might not actually

be needed. Therefore a coroutine might need to be aborted before it

be needed. Therefore a coroutine might need to be aborted before it

has finished its work.

has finished its work.

All coroutines must be written in such a way that important data structures

All coroutines must be written in such a way that important data structures

remain intact even when the coroutine is abruptly terminated. In particular,

remain intact even when the coroutine is abruptly terminated. In particular,

we need to be sure that ``locks'' on shared resources are restored to

we need to be sure that ``locks'' on shared resources are restored to

an unlocked state when a coroutine holding the lock is aborted.

an unlocked state when a coroutine holding the lock is aborted.

A \&{lockvar} variable is |NULL| when it is unlocked; otherwise it

A \&{lockvar} variable is |NULL| when it is unlocked; otherwise it

points to the coroutine responsible for unlocking~it.

points to the coroutine responsible for unlocking~it.

@d set_lock(c,l) {@+l=c;@+(c)->lockloc=&(l);@+}

@d set_lock(c,l) {@+l=c;@+(c)->lockloc=&(l);@+}

@d release_lock(c,l) {@+l=NULL;@+ (c)->lockloc=NULL;@+}

@d release_lock(c,l) {@+l=NULL;@+ (c)->lockloc=NULL;@+}

@=

@=

typedef coroutine *lockvar;

typedef coroutine *lockvar;

@ @=

@ @=

Extern void print_locks @,@,@[ARGS((void))@];

Extern void print_locks @,@,@[ARGS((void))@];

@ @=

@ @=

void print_locks()

void print_locks()

{

{

  print_cache_locks(ITcache);

  print_cache_locks(ITcache);

  print_cache_locks(DTcache);

  print_cache_locks(DTcache);

  print_cache_locks(Icache);

  print_cache_locks(Icache);

  print_cache_locks(Dcache);

  print_cache_locks(Dcache);

  print_cache_locks(Scache);

  print_cache_locks(Scache);

  if (mem_lock) printf("mem locked by %s:%d\n",mem_lock->name,mem_lock->stage);

  if (mem_lock) printf("mem locked by %s:%d\n",mem_lock->name,mem_lock->stage);

  if (dispatch_lock) printf("dispatch locked by %s:%d\n",

  if (dispatch_lock) printf("dispatch locked by %s:%d\n",

                    dispatch_lock->name,dispatch_lock->stage);

                    dispatch_lock->name,dispatch_lock->stage);

  if (wbuf_lock) printf("head of write buffer locked by %s:%d\n",

  if (wbuf_lock) printf("head of write buffer locked by %s:%d\n",

                    wbuf_lock->name,wbuf_lock->stage);

                    wbuf_lock->name,wbuf_lock->stage);

  if (clean_lock) printf("cleaner locked by %s:%d\n",

  if (clean_lock) printf("cleaner locked by %s:%d\n",

                    clean_lock->name,clean_lock->stage);

                    clean_lock->name,clean_lock->stage);

  if (speed_lock) printf("write buffer flush locked by %s:%d\n",

  if (speed_lock) printf("write buffer flush locked by %s:%d\n",

                    speed_lock->name,speed_lock->stage);

                    speed_lock->name,speed_lock->stage);

}

}

@ Many of the quantities we deal with are speculative values

@ Many of the quantities we deal with are speculative values

that might not yet have been certified as part of the ``real''

that might not yet have been certified as part of the ``real''

calculation; in fact, they might not yet have been calculated.

calculation; in fact, they might not yet have been calculated.

A \&{spec} consists of a 64-bit quantity |o| and a pointer~|p| to

A \&{spec} consists of a 64-bit quantity |o| and a pointer~|p| to

a \&{specnode}. The value~|o| is meaningful only if the

a \&{specnode}. The value~|o| is meaningful only if the

pointer~|p| is~|NULL|; otherwise |p| points to a source of further information.

pointer~|p| is~|NULL|; otherwise |p| points to a source of further information.

A \&{specnode} is a 64-bit quantity |o| together with links to other

A \&{specnode} is a 64-bit quantity |o| together with links to other

\&{specnode}s

\&{specnode}s

that are above it or below it in a doubly linked list. An additional

that are above it or below it in a doubly linked list. An additional

|known| bit tells whether the |o|~field has been calculated. There also is

|known| bit tells whether the |o|~field has been calculated. There also is

a 64-bit |addr| field, to identify the list and give further information.

a 64-bit |addr| field, to identify the list and give further information.

A \&{specnode} list keeps track of speculative values related to a specific

A \&{specnode} list keeps track of speculative values related to a specific

register or to all of main memory; we will discuss such lists in detail~later.

register or to all of main memory; we will discuss such lists in detail~later.

@s specnode_struct int

@s specnode_struct int

@=

@=

typedef struct {

typedef struct {

  octa o;

  octa o;

  struct specnode_struct *p;

  struct specnode_struct *p;

} spec;

} spec;

@#

@#

typedef struct specnode_struct {

typedef struct specnode_struct {

  octa o;

  octa o;

  bool known;

  bool known;

  octa addr;

  octa addr;

  struct specnode_struct *up,*down;

  struct specnode_struct *up,*down;

} specnode;

} specnode;

@ @=

@ @=

spec zero_spec; /* |zero_spec.o.h=zero_spec.o.l=0| and |zero_spec.p=NULL| */

spec zero_spec; /* |zero_spec.o.h=zero_spec.o.l=0| and |zero_spec.p=NULL| */

@ @=

@ @=

static void print_spec @,@,@[ARGS((spec))@];

static void print_spec @,@,@[ARGS((spec))@];

@ @=

@ @=

static void print_spec(s)

static void print_spec(s)

  spec s;

  spec s;

{

{

  if (!s.p) print_octa(s.o);

  if (!s.p) print_octa(s.o);

  else {

  else {

    printf(">");@+ print_specnode_id(s.p->addr);

    printf(">");@+ print_specnode_id(s.p->addr);

  }

  }

}

}

@#

@#

static void print_specnode(s)

static void print_specnode(s)

  specnode s;

  specnode s;

{

{

  if (s.known) {@+print_octa(s.o);@+printf("!");@+}

  if (s.known) {@+print_octa(s.o);@+printf("!");@+}

  else if (s.o.h || s.o.l) {@+print_octa(s.o);@+printf("?");@+}

  else if (s.o.h || s.o.l) {@+print_octa(s.o);@+printf("?");@+}

  else printf("?");

  else printf("?");

  print_specnode_id(s.addr);

  print_specnode_id(s.addr);

}

}

@ The analog of an automobile in our simulator is a block of data called

@ The analog of an automobile in our simulator is a block of data called

\&{control}, which represents all the relevant facts about an \MMIX\

\&{control}, which represents all the relevant facts about an \MMIX\

instruction.  We can think of it as the work order attached to a car's

instruction.  We can think of it as the work order attached to a car's

windshield. Each group of employees updates the work order as the car moves

windshield. Each group of employees updates the work order as the car moves

through the shop.

through the shop.

A \&{control} record contains the original location of an instruction,

A \&{control} record contains the original location of an instruction,

and its four bytes OP~X~Y~Z. An instruction has up to four inputs, which are

and its four bytes OP~X~Y~Z. An instruction has up to four inputs, which are

\&{spec} records called |y|, |z|, |b| and~|ra|; it also has up to three

\&{spec} records called |y|, |z|, |b| and~|ra|; it also has up to three

outputs, which are \&{specnode} records called |x|, |a|, and~|rl|.

outputs, which are \&{specnode} records called |x|, |a|, and~|rl|.

(We usually don't mention the special input~|ra| or the special output~|rl|,

(We usually don't mention the special input~|ra| or the special output~|rl|,

which refer to \.{MMIX}'s internal registers rA and~rL.) For example, the

which refer to \.{MMIX}'s internal registers rA and~rL.) For example, the

main inputs to a \.{DIVU} command are \$Y, \$Z, and~rD; the outputs are the

main inputs to a \.{DIVU} command are \$Y, \$Z, and~rD; the outputs are the

quotient~\$X and the remainder~rR. The inputs to a

quotient~\$X and the remainder~rR. The inputs to a

\.{STO} command are \$Y, \$Z, and~\$X; there is one ``output,'' and

\.{STO} command are \$Y, \$Z, and~\$X; there is one ``output,'' and

the field~|x.addr| will be set to the physical address of the memory location

the field~|x.addr| will be set to the physical address of the memory location

corresponding to virtual address $\rm \$Y+\$Z$.

corresponding to virtual address $\rm \$Y+\$Z$.

Each \&{control} block also points to the coroutine that owns it, if any.

Each \&{control} block also points to the coroutine that owns it, if any.

And it has various other fields that contain other tidbits of information;

And it has various other fields that contain other tidbits of information;

for example, we have already mentioned

for example, we have already mentioned

the |state|~field, which often governs a coroutine's actions. The |i|~field,

the |state|~field, which often governs a coroutine's actions. The |i|~field,

which contains an internal operation code number, is generally used together

which contains an internal operation code number, is generally used together

with |state| to switch between alternative computational steps. If, for

with |state| to switch between alternative computational steps. If, for

example, the |op|~field is \.{SUB} or \.{SUBI} or \.{NEG} or \.{NEGI},

example, the |op|~field is \.{SUB} or \.{SUBI} or \.{NEG} or \.{NEGI},

the internal opcode~|i| will be simply~|sub|.

the internal opcode~|i| will be simply~|sub|.

We shall define all the fields of \&{control} records

We shall define all the fields of \&{control} records

now and discuss them later.

now and discuss them later.

An actual hardware implementation of \MMIX\ wouldn't need all the information

An actual hardware implementation of \MMIX\ wouldn't need all the information

we are putting into a \&{control} block. Some of that information would

we are putting into a \&{control} block. Some of that information would

typically be latched between stages of a pipeline; other portions would

typically be latched between stages of a pipeline; other portions would

probably appear in so-called ``rename registers.''

probably appear in so-called ``rename registers.''

@^rename registers@>

@^rename registers@>

We simulate rename registers only indirectly,

We simulate rename registers only indirectly,

by counting how many registers of that

by counting how many registers of that

kind would be in use if we were mimicking low-level hardware details more

kind would be in use if we were mimicking low-level hardware details more

precisely. The |go| field is a \&{specnode} for convenience in programming,

precisely. The |go| field is a \&{specnode} for convenience in programming,

although we use only its |known| and |o| subfields. It generally contains

although we use only its |known| and |o| subfields. It generally contains

the address of the subsequent instruction.

the address of the subsequent instruction.

@s mmix_opcode int

@s mmix_opcode int

@s internal_opcode int

@s internal_opcode int

@=

@=

@@;

@@;

typedef struct control_struct {

typedef struct control_struct {

 octa loc; /* virtual address where an instruction originated */

 octa loc; /* virtual address where an instruction originated */

 mmix_opcode op;@+ unsigned char xx,yy,zz; /* the original instruction bytes */

 mmix_opcode op;@+ unsigned char xx,yy,zz; /* the original instruction bytes */

 spec y,z,b,ra; /* inputs */

 spec y,z,b,ra; /* inputs */

 specnode x,a,go,rl; /* outputs */

 specnode x,a,go,rl; /* outputs */

 coroutine *owner; /* a coroutine whose |ctl| this is */

 coroutine *owner; /* a coroutine whose |ctl| this is */

 internal_opcode i; /* internal opcode */

 internal_opcode i; /* internal opcode */

 int state; /* internal mindset */

 int state; /* internal mindset */

 bool usage; /* should rU be increased? */

 bool usage; /* should rU be increased? */

 bool need_b; /* should we stall until |b.p==NULL|? */

 bool need_b; /* should we stall until |b.p==NULL|? */

 bool need_ra; /* should we stall until |ra.p==NULL|? */

 bool need_ra; /* should we stall until |ra.p==NULL|? */

 bool ren_x; /* does |x| correspond to a rename register? */

 bool ren_x; /* does |x| correspond to a rename register? */

 bool mem_x; /* does |x| correspond to a memory write? */

 bool mem_x; /* does |x| correspond to a memory write? */

 bool ren_a; /* does |a| correspond to a rename register? */

 bool ren_a; /* does |a| correspond to a rename register? */

 bool set_l; /* does |rl| correspond to a new value of rL? */

 bool set_l; /* does |rl| correspond to a new value of rL? */

 bool interim; /* does this instruction need to be reissued on interrupt? */

 bool interim; /* does this instruction need to be reissued on interrupt? */

 unsigned int arith_exc; /* arithmetic exceptions for event bits of rA */

 unsigned int arith_exc; /* arithmetic exceptions for event bits of rA */

 unsigned int hist; /* history bits for use in branch prediction */

 unsigned int hist; /* history bits for use in branch prediction */

 int denin,denout; /* execution time penalties for subnormal handling */

 int denin,denout; /* execution time penalties for subnormal handling */

 octa cur_O,cur_S; /* speculative rO and rS before this instruction */

 octa cur_O,cur_S; /* speculative rO and rS before this instruction */

 unsigned int interrupt; /* does this instruction generate an interrupt? */

 unsigned int interrupt; /* does this instruction generate an interrupt? */

 void *ptr_a, *ptr_b, *ptr_c; /* generic pointers for miscellaneous use */

 void *ptr_a, *ptr_b, *ptr_c; /* generic pointers for miscellaneous use */

} control;

} control;

@ @=

@ @=

static void print_control_block @,@,@[ARGS((control*))@];

static void print_control_block @,@,@[ARGS((control*))@];

@ @=

@ @=

static void print_control_block(c)

static void print_control_block(c)

  control *c;

  control *c;

{

{

  octa default_go;

  octa default_go;

  if (c->loc.h || c->loc.l || c->op || c->xx || c->yy || c->zz || c->owner) {

  if (c->loc.h || c->loc.l || c->op || c->xx || c->yy || c->zz || c->owner) {

    print_octa(c->loc);

    print_octa(c->loc);

    printf(": %02x%02x%02x%02x(%s)",c->op,c->xx,c->yy,c->zz,

    printf(": %02x%02x%02x%02x(%s)",c->op,c->xx,c->yy,c->zz,

              internal_op_name[c->i]);

              internal_op_name[c->i]);

  }

  }

  if (c->usage) printf("*");

  if (c->usage) printf("*");

  if (c->interim) printf("+");

  if (c->interim) printf("+");

  if (c->y.o.h || c->y.o.l || c->y.p) {@+printf(" y=");@+print_spec(c->y);@+}

  if (c->y.o.h || c->y.o.l || c->y.p) {@+printf(" y=");@+print_spec(c->y);@+}

  if (c->z.o.h || c->z.o.l || c->z.p) {@+printf(" z=");@+print_spec(c->z);@+}

  if (c->z.o.h || c->z.o.l || c->z.p) {@+printf(" z=");@+print_spec(c->z);@+}

  if (c->b.o.h || c->b.o.l || c->b.p || c->need_b) {

  if (c->b.o.h || c->b.o.l || c->b.p || c->need_b) {

    printf(" b=");@+print_spec(c->b);

    printf(" b=");@+print_spec(c->b);

    if (c->need_b) printf("*");

    if (c->need_b) printf("*");

  }

  }

  if (c->need_ra) {@+printf(" rA=");@+print_spec(c->ra);@+}

  if (c->need_ra) {@+printf(" rA=");@+print_spec(c->ra);@+}

  if (c->ren_x || c->mem_x) {@+printf(" x=");@+print_specnode(c->x);@+}

  if (c->ren_x || c->mem_x) {@+printf(" x=");@+print_specnode(c->x);@+}

  else if (c->x.o.h || c->x.o.l) {

  else if (c->x.o.h || c->x.o.l) {

    printf(" x=");@+print_octa(c->x.o);@+printf("%c",c->x.known? '!': '?');

    printf(" x=");@+print_octa(c->x.o);@+printf("%c",c->x.known? '!': '?');

  }

  }

  if (c->ren_a) {@+printf(" a=");@+print_specnode(c->a);@+}

  if (c->ren_a) {@+printf(" a=");@+print_specnode(c->a);@+}

  if (c->set_l) {@+printf(" rL=");@+print_specnode(c->rl);@+}

  if (c->set_l) {@+printf(" rL=");@+print_specnode(c->rl);@+}

  if (c->interrupt) {@+printf(" int=");@+print_bits(c->interrupt);@+}

  if (c->interrupt) {@+printf(" int=");@+print_bits(c->interrupt);@+}

  if (c->arith_exc) {@+printf(" exc=");@+print_bits(c->arith_exc<<8);@+}

  if (c->arith_exc) {@+printf(" exc=");@+print_bits(c->arith_exc<<8);@+}

  default_go=incr(c->loc,4);

  default_go=incr(c->loc,4);

  if (c->go.o.l!=default_go.l || c->go.o.h!=default_go.h) {

  if (c->go.o.l!=default_go.l || c->go.o.h!=default_go.h) {

    printf(" ->");@+print_octa(c->go.o);

    printf(" ->");@+print_octa(c->go.o);

  }

  }

  if (verbose&show_pred_bit) printf(" hist=%x",c->hist);

  if (verbose&show_pred_bit) printf(" hist=%x",c->hist);

  if (c->i==pop) {

  if (c->i==pop) {

     printf(" rS="); print_octa(c->cur_S);

     printf(" rS="); print_octa(c->cur_S);

     printf(" rO="); print_octa(c->cur_O);

     printf(" rO="); print_octa(c->cur_O);

  }

  }

  printf(" state=%d",c->state);

  printf(" state=%d",c->state);

}

}

@* Lists. Here is a (boring) list of all the \MMIX\ opcodes, in order.

@* Lists. Here is a (boring) list of all the \MMIX\ opcodes, in order.

@=

@=

typedef enum{@/

typedef enum{@/

@!TRAP,@!FCMP,@!FUN,@!FEQL,@!FADD,@!FIX,@!FSUB,@!FIXU,@/

@!TRAP,@!FCMP,@!FUN,@!FEQL,@!FADD,@!FIX,@!FSUB,@!FIXU,@/

@!FLOT,@!FLOTI,@!FLOTU,@!FLOTUI,@!SFLOT,@!SFLOTI,@!SFLOTU,@!SFLOTUI,@/

@!FLOT,@!FLOTI,@!FLOTU,@!FLOTUI,@!SFLOT,@!SFLOTI,@!SFLOTU,@!SFLOTUI,@/

@!FMUL,@!FCMPE,@!FUNE,@!FEQLE,@!FDIV,@!FSQRT,@!FREM,@!FINT,@/

@!FMUL,@!FCMPE,@!FUNE,@!FEQLE,@!FDIV,@!FSQRT,@!FREM,@!FINT,@/

@!MUL,@!MULI,@!MULU,@!MULUI,@!DIV,@!DIVI,@!DIVU,@!DIVUI,@/

@!MUL,@!MULI,@!MULU,@!MULUI,@!DIV,@!DIVI,@!DIVU,@!DIVUI,@/

@!ADD,@!ADDI,@!ADDU,@!ADDUI,@!SUB,@!SUBI,@!SUBU,@!SUBUI,@/

@!ADD,@!ADDI,@!ADDU,@!ADDUI,@!SUB,@!SUBI,@!SUBU,@!SUBUI,@/

@!IIADDU,@!IIADDUI,@!IVADDU,@!IVADDUI,@!VIIIADDU,@!VIIIADDUI,@!XVIADDU,@!XVIADDUI,@/

@!IIADDU,@!IIADDUI,@!IVADDU,@!IVADDUI,@!VIIIADDU,@!VIIIADDUI,@!XVIADDU,@!XVIADDUI,@/

@!CMP,@!CMPI,@!CMPU,@!CMPUI,@!NEG,@!NEGI,@!NEGU,@!NEGUI,@/

@!CMP,@!CMPI,@!CMPU,@!CMPUI,@!NEG,@!NEGI,@!NEGU,@!NEGUI,@/

@!SL,@!SLI,@!SLU,@!SLUI,@!SR,@!SRI,@!SRU,@!SRUI,@/

@!SL,@!SLI,@!SLU,@!SLUI,@!SR,@!SRI,@!SRU,@!SRUI,@/

@!BN,@!BNB,@!BZ,@!BZB,@!BP,@!BPB,@!BOD,@!BODB,@/

@!BN,@!BNB,@!BZ,@!BZB,@!BP,@!BPB,@!BOD,@!BODB,@/

@!BNN,@!BNNB,@!BNZ,@!BNZB,@!BNP,@!BNPB,@!BEV,@!BEVB,@/

@!BNN,@!BNNB,@!BNZ,@!BNZB,@!BNP,@!BNPB,@!BEV,@!BEVB,@/

@!PBN,@!PBNB,@!PBZ,@!PBZB,@!PBP,@!PBPB,@!PBOD,@!PBODB,@/

@!PBN,@!PBNB,@!PBZ,@!PBZB,@!PBP,@!PBPB,@!PBOD,@!PBODB,@/

@!PBNN,@!PBNNB,@!PBNZ,@!PBNZB,@!PBNP,@!PBNPB,@!PBEV,@!PBEVB,@/

@!PBNN,@!PBNNB,@!PBNZ,@!PBNZB,@!PBNP,@!PBNPB,@!PBEV,@!PBEVB,@/

@!CSN,@!CSNI,@!CSZ,@!CSZI,@!CSP,@!CSPI,@!CSOD,@!CSODI,@/

@!CSN,@!CSNI,@!CSZ,@!CSZI,@!CSP,@!CSPI,@!CSOD,@!CSODI,@/

@!CSNN,@!CSNNI,@!CSNZ,@!CSNZI,@!CSNP,@!CSNPI,@!CSEV,@!CSEVI,@/

@!CSNN,@!CSNNI,@!CSNZ,@!CSNZI,@!CSNP,@!CSNPI,@!CSEV,@!CSEVI,@/

@!ZSN,@!ZSNI,@!ZSZ,@!ZSZI,@!ZSP,@!ZSPI,@!ZSOD,@!ZSODI,@/

@!ZSN,@!ZSNI,@!ZSZ,@!ZSZI,@!ZSP,@!ZSPI,@!ZSOD,@!ZSODI,@/

@!ZSNN,@!ZSNNI,@!ZSNZ,@!ZSNZI,@!ZSNP,@!ZSNPI,@!ZSEV,@!ZSEVI,@/

@!ZSNN,@!ZSNNI,@!ZSNZ,@!ZSNZI,@!ZSNP,@!ZSNPI,@!ZSEV,@!ZSEVI,@/

@!LDB,@!LDBI,@!LDBU,@!LDBUI,@!LDW,@!LDWI,@!LDWU,@!LDWUI,@/

@!LDB,@!LDBI,@!LDBU,@!LDBUI,@!LDW,@!LDWI,@!LDWU,@!LDWUI,@/

@!LDT,@!LDTI,@!LDTU,@!LDTUI,@!LDO,@!LDOI,@!LDOU,@!LDOUI,@/

@!LDT,@!LDTI,@!LDTU,@!LDTUI,@!LDO,@!LDOI,@!LDOU,@!LDOUI,@/

@!LDSF,@!LDSFI,@!LDHT,@!LDHTI,@!CSWAP,@!CSWAPI,@!LDUNC,@!LDUNCI,@/

@!LDSF,@!LDSFI,@!LDHT,@!LDHTI,@!CSWAP,@!CSWAPI,@!LDUNC,@!LDUNCI,@/

@!LDVTS,@!LDVTSI,@!PRELD,@!PRELDI,@!PREGO,@!PREGOI,@!GO,@!GOI,@/

@!LDVTS,@!LDVTSI,@!PRELD,@!PRELDI,@!PREGO,@!PREGOI,@!GO,@!GOI,@/

@!STB,@!STBI,@!STBU,@!STBUI,@!STW,@!STWI,@!STWU,@!STWUI,@/

@!STB,@!STBI,@!STBU,@!STBUI,@!STW,@!STWI,@!STWU,@!STWUI,@/

@!STT,@!STTI,@!STTU,@!STTUI,@!STO,@!STOI,@!STOU,@!STOUI,@/

@!STT,@!STTI,@!STTU,@!STTUI,@!STO,@!STOI,@!STOU,@!STOUI,@/

@!STSF,@!STSFI,@!STHT,@!STHTI,@!STCO,@!STCOI,@!STUNC,@!STUNCI,@/

@!STSF,@!STSFI,@!STHT,@!STHTI,@!STCO,@!STCOI,@!STUNC,@!STUNCI,@/

@!SYNCD,@!SYNCDI,@!PREST,@!PRESTI,@!SYNCID,@!SYNCIDI,@!PUSHGO,@!PUSHGOI,@/

@!SYNCD,@!SYNCDI,@!PREST,@!PRESTI,@!SYNCID,@!SYNCIDI,@!PUSHGO,@!PUSHGOI,@/

@!OR,@!ORI,@!ORN,@!ORNI,@!NOR,@!NORI,@!XOR,@!XORI,@/

@!OR,@!ORI,@!ORN,@!ORNI,@!NOR,@!NORI,@!XOR,@!XORI,@/

@!AND,@!ANDI,@!ANDN,@!ANDNI,@!NAND,@!NANDI,@!NXOR,@!NXORI,@/

@!AND,@!ANDI,@!ANDN,@!ANDNI,@!NAND,@!NANDI,@!NXOR,@!NXORI,@/

@!BDIF,@!BDIFI,@!WDIF,@!WDIFI,@!TDIF,@!TDIFI,@!ODIF,@!ODIFI,@/

@!BDIF,@!BDIFI,@!WDIF,@!WDIFI,@!TDIF,@!TDIFI,@!ODIF,@!ODIFI,@/

@!MUX,@!MUXI,@!SADD,@!SADDI,@!MOR,@!MORI,@!MXOR,@!MXORI,@/

@!MUX,@!MUXI,@!SADD,@!SADDI,@!MOR,@!MORI,@!MXOR,@!MXORI,@/

@!SETH,@!SETMH,@!SETML,@!SETL,@!INCH,@!INCMH,@!INCML,@!INCL,@/

@!SETH,@!SETMH,@!SETML,@!SETL,@!INCH,@!INCMH,@!INCML,@!INCL,@/

@!ORH,@!ORMH,@!ORML,@!ORL,@!ANDNH,@!ANDNMH,@!ANDNML,@!ANDNL,@/

@!ORH,@!ORMH,@!ORML,@!ORL,@!ANDNH,@!ANDNMH,@!ANDNML,@!ANDNL,@/

@!JMP,@!JMPB,@!PUSHJ,@!PUSHJB,@!GETA,@!GETAB,@!PUT,@!PUTI,@/

@!JMP,@!JMPB,@!PUSHJ,@!PUSHJB,@!GETA,@!GETAB,@!PUT,@!PUTI,@/

@!POP,@!RESUME,@!SAVE,@!UNSAVE,@!SYNC,@!SWYM,@!GET,@!TRIP}@+@!mmix_opcode;

@!POP,@!RESUME,@!SAVE,@!UNSAVE,@!SYNC,@!SWYM,@!GET,@!TRIP}@+@!mmix_opcode;

@ @=

@ @=

char *opcode_name[]={

char *opcode_name[]={

"TRAP","FCMP","FUN","FEQL","FADD","FIX","FSUB","FIXU",@/

"TRAP","FCMP","FUN","FEQL","FADD","FIX","FSUB","FIXU",@/

"FLOT","FLOTI","FLOTU","FLOTUI","SFLOT","SFLOTI","SFLOTU","SFLOTUI",@/

"FLOT","FLOTI","FLOTU","FLOTUI","SFLOT","SFLOTI","SFLOTU","SFLOTUI",@/

"FMUL","FCMPE","FUNE","FEQLE","FDIV","FSQRT","FREM","FINT",@/

"FMUL","FCMPE","FUNE","FEQLE","FDIV","FSQRT","FREM","FINT",@/

"MUL","MULI","MULU","MULUI","DIV","DIVI","DIVU","DIVUI",@/

"MUL","MULI","MULU","MULUI","DIV","DIVI","DIVU","DIVUI",@/

"ADD","ADDI","ADDU","ADDUI","SUB","SUBI","SUBU","SUBUI",@/

"ADD","ADDI","ADDU","ADDUI","SUB","SUBI","SUBU","SUBUI",@/

"2ADDU","2ADDUI","4ADDU","4ADDUI","8ADDU","8ADDUI","16ADDU","16ADDUI",@/

"2ADDU","2ADDUI","4ADDU","4ADDUI","8ADDU","8ADDUI","16ADDU","16ADDUI",@/

"CMP","CMPI","CMPU","CMPUI","NEG","NEGI","NEGU","NEGUI",@/

"CMP","CMPI","CMPU","CMPUI","NEG","NEGI","NEGU","NEGUI",@/

"SL","SLI","SLU","SLUI","SR","SRI","SRU","SRUI",@/

"SL","SLI","SLU","SLUI","SR","SRI","SRU","SRUI",@/

"BN","BNB","BZ","BZB","BP","BPB","BOD","BODB",@/

"BN","BNB","BZ","BZB","BP","BPB","BOD","BODB",@/

"BNN","BNNB","BNZ","BNZB","BNP","BNPB","BEV","BEVB",@/

"BNN","BNNB","BNZ","BNZB","BNP","BNPB","BEV","BEVB",@/

"PBN","PBNB","PBZ","PBZB","PBP","PBPB","PBOD","PBODB",@/

"PBN","PBNB","PBZ","PBZB","PBP","PBPB","PBOD","PBODB",@/

"PBNN","PBNNB","PBNZ","PBNZB","PBNP","PBNPB","PBEV","PBEVB",@/

"PBNN","PBNNB","PBNZ","PBNZB","PBNP","PBNPB","PBEV","PBEVB",@/

"CSN","CSNI","CSZ","CSZI","CSP","CSPI","CSOD","CSODI",@/

"CSN","CSNI","CSZ","CSZI","CSP","CSPI","CSOD","CSODI",@/

"CSNN","CSNNI","CSNZ","CSNZI","CSNP","CSNPI","CSEV","CSEVI",@/

"CSNN","CSNNI","CSNZ","CSNZI","CSNP","CSNPI","CSEV","CSEVI",@/

"ZSN","ZSNI","ZSZ","ZSZI","ZSP","ZSPI","ZSOD","ZSODI",@/

"ZSN","ZSNI","ZSZ","ZSZI","ZSP","ZSPI","ZSOD","ZSODI",@/

"ZSNN","ZSNNI","ZSNZ","ZSNZI","ZSNP","ZSNPI","ZSEV","ZSEVI",@/

"ZSNN","ZSNNI","ZSNZ","ZSNZI","ZSNP","ZSNPI","ZSEV","ZSEVI",@/

"LDB","LDBI","LDBU","LDBUI","LDW","LDWI","LDWU","LDWUI",@/

"LDB","LDBI","LDBU","LDBUI","LDW","LDWI","LDWU","LDWUI",@/

"LDT","LDTI","LDTU","LDTUI","LDO","LDOI","LDOU","LDOUI",@/

"LDT","LDTI","LDTU","LDTUI","LDO","LDOI","LDOU","LDOUI",@/

"LDSF","LDSFI","LDHT","LDHTI","CSWAP","CSWAPI","LDUNC","LDUNCI",@/

"LDSF","LDSFI","LDHT","LDHTI","CSWAP","CSWAPI","LDUNC","LDUNCI",@/

"LDVTS","LDVTSI","PRELD","PRELDI","PREGO","PREGOI","GO","GOI",@/

"LDVTS","LDVTSI","PRELD","PRELDI","PREGO","PREGOI","GO","GOI",@/

"STB","STBI","STBU","STBUI","STW","STWI","STWU","STWUI",@/

"STB","STBI","STBU","STBUI","STW","STWI","STWU","STWUI",@/

"STT","STTI","STTU","STTUI","STO","STOI","STOU","STOUI",@/

"STT","STTI","STTU","STTUI","STO","STOI","STOU","STOUI",@/

"STSF","STSFI","STHT","STHTI","STCO","STCOI","STUNC","STUNCI",@/

"STSF","STSFI","STHT","STHTI","STCO","STCOI","STUNC","STUNCI",@/

"SYNCD","SYNCDI","PREST","PRESTI","SYNCID","SYNCIDI","PUSHGO","PUSHGOI",@/

"SYNCD","SYNCDI","PREST","PRESTI","SYNCID","SYNCIDI","PUSHGO","PUSHGOI",@/

"OR","ORI","ORN","ORNI","NOR","NORI","XOR","XORI",@/

"OR","ORI","ORN","ORNI","NOR","NORI","XOR","XORI",@/

"AND","ANDI","ANDN","ANDNI","NAND","NANDI","NXOR","NXORI",@/

"AND","ANDI","ANDN","ANDNI","NAND","NANDI","NXOR","NXORI",@/

"BDIF","BDIFI","WDIF","WDIFI","TDIF","TDIFI","ODIF","ODIFI",@/

"BDIF","BDIFI","WDIF","WDIFI","TDIF","TDIFI","ODIF","ODIFI",@/

"MUX","MUXI","SADD","SADDI","MOR","MORI","MXOR","MXORI",@/

"MUX","MUXI","SADD","SADDI","MOR","MORI","MXOR","MXORI",@/

"SETH","SETMH","SETML","SETL","INCH","INCMH","INCML","INCL",@/

"SETH","SETMH","SETML","SETL","INCH","INCMH","INCML","INCL",@/

"ORH","ORMH","ORML","ORL","ANDNH","ANDNMH","ANDNML","ANDNL",@/

"ORH","ORMH","ORML","ORL","ANDNH","ANDNMH","ANDNML","ANDNL",@/

"JMP","JMPB","PUSHJ","PUSHJB","GETA","GETAB","PUT","PUTI",@/

"JMP","JMPB","PUSHJ","PUSHJB","GETA","GETAB","PUT","PUTI",@/

"POP","RESUME","SAVE","UNSAVE","SYNC","SWYM","GET","TRIP"};

"POP","RESUME","SAVE","UNSAVE","SYNC","SWYM","GET","TRIP"};

@ And here is a (likewise boring) list of all the internal opcodes.

@ And here is a (likewise boring) list of all the internal opcodes.

The smallest numbers, less than or equal to |max_pipe_op|, correspond

The smallest numbers, less than or equal to |max_pipe_op|, correspond

to operations for which arbitrary pipeline delays can be configured

to operations for which arbitrary pipeline delays can be configured

with |MMIX_config|. The largest numbers, greater than |max_real_command|,

with |MMIX_config|. The largest numbers, greater than |max_real_command|,

correspond to internally

correspond to internally

generated operations that have no official OP code; for example,

generated operations that have no official OP code; for example,

there are internal operations to shift the $\gamma$ pointer in the

there are internal operations to shift the $\gamma$ pointer in the

register stack, and to compute page table entries.

register stack, and to compute page table entries.

@=

@=

#define max_pipe_op feps

#define max_pipe_op feps

#define max_real_command trip

#define max_real_command trip

typedef enum{@/

typedef enum{@/

@!mul0, /* multiplication by zero */

@!mul0, /* multiplication by zero */

@!mul1, /* multiplication by 1--8 bits */

@!mul1, /* multiplication by 1--8 bits */

@!mul2, /* multiplication by 9--16 bits */

@!mul2, /* multiplication by 9--16 bits */

@!mul3, /* multiplication by 17--24 bits */

@!mul3, /* multiplication by 17--24 bits */

@!mul4, /* multiplication by 25--32 bits */

@!mul4, /* multiplication by 25--32 bits */

@!mul5, /* multiplication by 33--40 bits */

@!mul5, /* multiplication by 33--40 bits */

@!mul6, /* multiplication by 41--48 bits */

@!mul6, /* multiplication by 41--48 bits */

@!mul7, /* multiplication by 49--56 bits */

@!mul7, /* multiplication by 49--56 bits */

@!mul8, /* multiplication by 57--64 bits */

@!mul8, /* multiplication by 57--64 bits */

@!div, /* \.{DIV[U][I]} */

@!div, /* \.{DIV[U][I]} */

@!sh, /* \.{S[L,R][U][I]} */

@!sh, /* \.{S[L,R][U][I]} */

@!mux, /* \.{MUX[I]} */

@!mux, /* \.{MUX[I]} */

@!sadd, /* \.{SADD[I]} */

@!sadd, /* \.{SADD[I]} */

@!mor, /* \.{M[X]OR[I]} */

@!mor, /* \.{M[X]OR[I]} */

@!fadd, /* \.{FADD}, \.{FSUB} */

@!fadd, /* \.{FADD}, \.{FSUB} */

@!fmul, /* \.{FMUL} */

@!fmul, /* \.{FMUL} */

@!fdiv, /* \.{FDIV} */

@!fdiv, /* \.{FDIV} */

@!fsqrt, /* \.{FSQRT} */

@!fsqrt, /* \.{FSQRT} */

@!fint, /* \.{FINT} */

@!fint, /* \.{FINT} */

@!fix, /* \.{FIX[U]} */

@!fix, /* \.{FIX[U]} */

@!flot, /* \.{[S]FLOT[U][I]} */

@!flot, /* \.{[S]FLOT[U][I]} */

@!feps, /* \.{FCMPE}, \.{FUNE}, \.{FEQLE} */

@!feps, /* \.{FCMPE}, \.{FUNE}, \.{FEQLE} */

@!fcmp, /* \.{FCMP} */

@!fcmp, /* \.{FCMP} */

@!funeq, /* \.{FUN}, \.{FEQL} */

@!funeq, /* \.{FUN}, \.{FEQL} */

@!fsub, /* \.{FSUB} */

@!fsub, /* \.{FSUB} */

@!frem, /* \.{FREM} */

@!frem, /* \.{FREM} */

@!mul, /* \.{MUL[I]} */

@!mul, /* \.{MUL[I]} */

@!mulu, /* \.{MULU[I]} */

@!mulu, /* \.{MULU[I]} */

@!divu, /* \.{DIVU[I]} */

@!divu, /* \.{DIVU[I]} */

@!add, /* \.{ADD[I]} */

@!add, /* \.{ADD[I]} */

@!addu, /* \.{[2,4,8,16,]ADDU[I]}, \.{INC[M][H,L]} */

@!addu, /* \.{[2,4,8,16,]ADDU[I]}, \.{INC[M][H,L]} */

@!sub, /* \.{SUB[I]}, \.{NEG[I]} */

@!sub, /* \.{SUB[I]}, \.{NEG[I]} */

@!subu, /* \.{SUBU[I]}, \.{NEGU[I]} */

@!subu, /* \.{SUBU[I]}, \.{NEGU[I]} */

@!set, /* \.{SET[M][H,L]}, \.{GETA[B]} */

@!set, /* \.{SET[M][H,L]}, \.{GETA[B]} */

@!or, /* \.{OR[I]}, \.{OR[M][H,L]} */

@!or, /* \.{OR[I]}, \.{OR[M][H,L]} */

@!orn, /* \.{ORN[I]} */

@!orn, /* \.{ORN[I]} */

@!nor, /* \.{NOR[I]} */

@!nor, /* \.{NOR[I]} */

@!and, /* \.{AND[I]} */

@!and, /* \.{AND[I]} */

@!andn, /* \.{ANDN[I]}, \.{ANDN[M][H,L]} */