mmstort  a tool to compute running times 

Content

mmstortA tool to compute running timesUsagemmstort [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
Input fileThe input file is expected to be an mms file containing lines of the following form:[Label] OPCODE Arguments{; OPCODE Arguments} Count & Commentor [Label] OPCODE Arguments{; OPCODE Arguments} CommentAll 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 CountsThe 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 GuessesBranch 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.ExampleLOC #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 CountsThe instruction counts are polynomials. The following tokens may exist in polynomials:constant: [09]+(\.[09]*)? variable: [azAZ](subscriptsuperscript)* variable: \upsilon\mu subscript: _[09abAB] subscript: _{[09abAB]+} superscript: ^\prime superscript: ^{(\prime)+} plus: + minus:  mul: * div: / open: ( close: )Inside a polynomial the following will be ignored: spaces, "~", "\kern [+]?[09]+(ptexem)", "\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 LinesTo restrict the computation of the total running time, the adding up of instruction counts can be switched on and off by lines starting with:
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 \rtrefnamepolynomialUsing 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. Sourcesmmstort 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 mmstortUnder 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 ExecutablesYou can download an executable for 32Bit 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