MMIX LOGO

mmstort - a tool to compute running times

Table of Content

Content

mmstort

A tool to compute running times

Usage

mmstort [-t]  [-d] [inputfile.mms]

computes the total running time from the instruction counts found in the input file and writes them to standard output. If no input file is given, the input is read from the standard input.

Options

  • -t switch on trace mode: print intermediate results for each input line.
  • -d switch on debug mode. Display the workings of the polynomial parser.

Input file

The input file is expected to be an mms file containing lines of the following form:
[Label] OPCODE Arguments{; OPCODE Arguments}  Count & Comment 
or
[Label] OPCODE Arguments{; OPCODE Arguments}  Comment 
All other lines are considered comments and are ignored.

Lines of the second form are equivalent to lines of the first form with Count=0. Hence we consider below only lines of the first form.

There are also special lines staring with "%%%..." which are described below.

Instruction Counts

The instruction counts are polynomials; that is they may contain variables, constants, addition and multiplications. The exact syntax of these polynomials is given below. In each line, the instruction count is multiplied with the number of oops and mems of the OPCODE in that line; these products are added up to yield the total running time. At the end of the program, the total running time is printed on the standard output.

Bad Guesses

Branch instructions can be annotated with counts for the bad guesses. The syntax is then countA\bg{countB}. Such a branch instruction will contribute countA+2*countB to the total running time.

Example

        LOC     #100
Main    SET     $0,17	                1 & Initialize.
1H	SUB     $0,$0,1	                N & Decrement.
        PBP     $0,1B		        N\bg{1} & Test
        SET     $255,0; TRAP 0,Halt,0   1 &
generates the output:
+2N+9 opps
0 mems
The SET instruction will contribute 1 oops, the SUB instruction N oops, the PBP instruction N+2 oops, and the last line will contribute 1+5 oops (1 for SET and 5 for TRAP).

Syntax of Instruction Counts

The instruction counts are polynomials. The following tokens may exist in polynomials:
constant: [0-9]+(\.[0-9]*)?
variable: [a-zA-Z](subscript|superscript)*
variable: \upsilon|\mu
subscript: _[0-9a-bA-B]
subscript: _{[0-9a-bA-B]+}
superscript: ^\prime
superscript: ^{(\prime)+}
plus: +
minus: -
mul: *
div: /
open: (
close: )
Inside a polynomial the following will be ignored: spaces, "~", "\kern [+-]?[0-9]+(pt|ex|em)", "\rfloor", "\lfloor", "\sum", "\hidewidth", "\fmt{...}". This list has no specific significance. It just contains all the things that I had in my instruction counts while writing the MMIX Supplement and wanted it to be ignored because it concerns just the formatting of the instruction counts or would have made instruction counts unnecessarily complex.

From the tokens above, polynomials are build according to the following rules:

polynomial: polynomial plus factor 
polynomial: polynomial plus factor
polynomial: factor

factor: factor mul atom 
factor: factor div constant
factor: factor atom 
factor: atom

atom: variable
atom: constant
atom: open polynomial close
Polynomials are expanded to be just sums of products and added up in this "normal form".

Special Lines

To restrict the computation of the total running time, the adding up of instruction counts can be switched on and off by lines starting with:
  • %%%on to switch adding on.
  • %%%off to switch adding off.
  • %%%rton to switch adding on.
  • %%%rtoff to switch adding off.
The first two formats of special lines are used in mmstotex to switch on and off the generation of TeX output. Typically it is desirable to restrict the computation of the total running time to the just these lines. If, however, the region needed for the computation of running time is different from the region converted to TeX, the last two formats can be used. These lines are ignored by mmstotex and only are used by mmstort.

Lines of the form:

%%%rt name & polynomial
can be used to check the total running time so far against a given polynomial and to make the given polynomial available by its name in a TeX file. If mmstort encounters such a line, it will look at the two polynomials computed for the oops and mems so far and compare them with the polynomial given. To be specific: let p the polynomial giving the number of oops so far and q be the polynomial of the number of mems so far, then the given polynomial will be compared to the polynomial p*\upsilon +q*\mu. If the polynomials are different, the program will terminate with an error code.

The mmstotex mmstotex program will convert the line above to

\rtref|name|polynomial|
Using the appropriate style file, this control sequence will produce an entry in the reference file such that |name| will evaluate to the given polynomial, which is thus checked against the running time as computed by mmstort.

Sources

mmstort is written as a lex file mmstort.l and a yacc file mmstort.y. The arithmetic with polynomials is implemented in poly.c and poly.h.

Building mmstort

Under Linux, to build mmstort from the source file, you need to generate mmstort.c using flex, then generate mmstort.tab.c and mmstort.tab.h using bison, and finally then compile it together with symtab.c, and link it with the flex library. The c files will need the include file symtab.h.
flex -o mmstort.c  mmstort.l
bison -t -d mmstort.y
gcc  mmstort.c mmstort.tab.c symtab.c poly.c -lfl -o mmstort

Executables

You can download an executable for 32-Bit Linux here: mmstort and for OSX you find it here: mmstort.

Please help to keep this site up to date! If you want to point out important material or projects that are not listed here, if you find errors or want to suggest improvements, please send email to email