mmstort - a tool to compute running times
Content
mmstort
A tool to compute running timesUsage
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 memsThe 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 closePolynomials 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.
Lines of the form:
%%%rt name & polynomialcan 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
