Arthur J. O'Dwyer

tiopt, the TI-83 Basic optimizer

Intro | Options | Distribution
Main | TI-83 | Source files

What tiopt can (and can't) do

The program tiopt is a tool for the optimization of programs written in TI-83 Basic. It can read programs saved in the .83P format, and produce output in .83P format, ASCII text designed for human readers, or ASCII text using the same encoding as the export function in TI's own GraphLink software. As of this writing, tiopt cannot take ASCII text as input.

Once it has read in a valid program, tiopt can optimize the program in several ways. These optimizations are listed in the "Options" section below.

It is important to realize that tiopt is not a substitute for hand-optimization! I am trying very hard to get tiopt to recognize common inefficiencies and optimizations of the search-and-replace kind, but TI-83 Basic is a very complicated and high-level language compared to, say, assembly language. Therefore, it is prohibitively hard to make a computer program understand all the ways a human programmer could rearrange code to make use of the Ans variable, or subprograms, or when rounding errors must be considered, and so on. Only you, the human programmer, can make these high-level decisions.

As I wrote above, tiopt is intended to be a tool for source code optimization. I plan to incorporate several ways for tiopt and the human programmer to have a "dialogue" about the meaning of a given program — for example, in the current implementation, the programmer can instruct tiopt about the variables read and written by external subprograms, and tiopt can tell the programmer which variables may safely be coalesced.


Download the source from this directory.

Options and optimizations

As of this writing, the tiopt program supports the following optimizations and tools:

Read .82P, .83P, or .8XP

By default, if the input file cannot be read as a TI-83 Basic program, tiopt will try to read it two more times, as a TI-83+ Basic program file and as a TI-82 Basic program file. However, since I don't own either of those calculators, I haven't been able to update mnem.h to deal with all the added TI-83+ symbols. Programs that use non–TI-83 symbols may cause tiopt to behave unpredictably.

The TI-84 and TI-84+ use the same program format as the TI-83+, so tiopt should be able to read them too.

Write .83P or .8XP

When tiopt is asked to write a binary file as output, if the output filename ends in ".8XP" (case-insensitive), tiopt will write a TI-83+ program file. In all other cases, tiopt will write a TI-83 program file.

To convert a program losslessly from .83P to .8XP, simply run tiopt input.83p output.8xp. When converting a program in the opposite direction, from .8XP to .83P, the conversion might be imperfect if the input program uses symbols or commands that are not available on the TI-83. tiopt will try to do something sensible in those cases.

The default lossy conversion for the TI-83+'s small alphabetic letters is to convert them into their visual equivalents on the TI-83. For example, the TI-83+'s "small letter A" maps to the TI-83's statistics variable "a". However, since not all small letters have TI-83 equivalents, this can lead to unattractive strings such as Disp "HeLLO wOrLd!". Use the option -fupper to map all TI-83+ small letters to upper case on the TI-83.

Change comment text: --comment text

Every .83P or .8XP file contains a 42-byte comment field that is stored in the computer file, but not preserved in the calculator's RAM. The TI-83 GraphLink software automatically fills in this comment field with the date and time the program was downloaded over the link; the TI-83+ GraphLink software leaves the field empty.

To change the text in the comment field to something else, use the option --comment text. If text is shorter than 42 characters, it will be padded with zeros. If it is longer than 42 characters, tiopt will give an error.

Pretty-printing: --print

If the --print option is given, then the program will be pretty-printed in plain ASCII text to the given output file (or to stdout if no output filename is given). "Pretty-printing" means line numbers, indentation, and a syntax designed to be more human-readable than TI GraphLink's default (e.g., "e\->\L1(1)" instead of "\e\\->\L\1\(1)", and an underscore to represent a space at the end of a line).

The --print option can optionally be followed by a string consisting only of the characters EINein. If that string is present, then the program text will be pretty-printed

The default settings are eIN.

Program hints: --hint filename

This option is currently only useful in conjunction with the --liveness option (see the next subsection). The specified file should consist of records of the form

  prgmFOO
  Reads: ABC
  Reads: BED
  Writes: AZ, [, Ans
  Exists: I
Each of the "reads/writes/exists" fields must be on its own line. Fields may be omitted. Duplicate fields combine; that is, in the above example prgmFOO reads A, B, C, D, and E. Variable names may be run together, or separated by spaces and an optional comma. Comment lines are introduced by "#".

The "Reads:" field lists the variables that are used as input by the named program; i.e., variables which should be considered live into a call to the named program.

The "Writes:" field lists the variables that are overwritten by the named program; i.e., variables which might be used as the output of the program, but also might just be trashed. Any values they had going into the program will be considered destroyed when the program returns.

The "Exists:" field lists those variables that the named program expects to exist on entry; for example, the named program will try to use them in IS>( or DS<( commands without assigning a value to them first. If you don't understand the ramifications of this field, you can almost certainly leave it out.

If your program calls itself recursively, it is a good idea to include a record for it in the hints file. Otherwise, tiopt will try to figure things out on its own, and it will probably get them wrong.

If you don't supply a hints file, or call a program that's not in the hints file, then tiopt will assume that the program does nothing of importance — reads no variables and writes no variables. This can cause --liveness to give bad results, but it won't hurt any non-liveness-related optimizations.

Variable liveness: --liveness

This option is still under development. Essentially, it keeps track of all 27 single-letter variables as well as the magic Ans variable; in the program

  3\->\A
  4\->\B
  Disp A
the variable A is assigned a value in line 1, and that value is used in line 3. Therefore, A is considered "alive" in lines 1 and 2. The variable B is not "alive" at all, since its value is never used; line 2 might as well be deleted.

The optimizer wouldn't delete line 2 by itself yet, but passing the --liveness option to tiopt will at least print a table of the lines in the program and their "live-out sets" (i.e., which variables are alive between the current line and its successors).

If two variables are never live in the same line, then tiopt will report that fact — since if their live ranges don't overlap, you might as well combine ("coalesce") them into a single variable, to reduce your memory footprint. Again, tiopt will not automatically coalesce variables for you; you have to tell it specifically.

If a variable is live in one part of the program and then again in an unrelated part of the program, it might be beneficial to perform "live-range splitting" on that variable — to split its two uses into two different variables. Consider this silly program:

  1\->\A
  2\->\B
  Disp A
  4\->\C
  Disp B
  3\->\A
  Disp A
  Disp C
Obviously, we should compress this to "Disp 1,2,3,4"; but that's a job for a human programmer at the moment. However, we can still reduce its memory footprint by observing that A has two distinct live ranges, renaming the second A to B, and then safely renaming C to A.
  1\->\A
  2\->\B
  Disp A
  4\->\A
  Disp B
  3\->\B
  Disp B
  Disp A
After all this discussion, it may seem anticlimactic to reveal that tiopt does not currently do live-range splitting. It's definitely a useful optimization, though.

Variable renaming: -vXY, --rename-var X Y

Once you have identified a variable to rename (see the above subsection), you can tell tiopt to perform the renaming by passing the --rename-var option with two arguments: the original variable name, and the new variable name. (Use "[" for theta.)

Variable renamings are performed simultaneously, not in sequence, so "-vXY -vYZ -vZX" will correctly rotate the names of variables X, Y, and Z.

One caveat: This option does not even attempt to deal with the expr() built-in function. If you write "42\->\X:Disp expr("X")" and then rename X to Y, you'll get "42\->\Y:Disp expr("X")". There is no way to deal with this problem that doesn't involve heuristics; consider the pathological program "HELLO":Disp Ans,expr(Ans) for an extreme example.

Variable renaming: --rename-var L1 LNEW

The same --rename-var option works to rename variables other than the simple real variables, such as lists, strings, matrices, Pics, and GDBs. (The short form -vXY does not work for these kinds of variables.) The following variable names are recognized:

Notice that it is possible to rename variables to things like L40 and Str127. This is an undocumented feature of the TI-83 family of calculators. While tiopt can manipulate these "hidden" variables, and the calculator itself can handle them during execution, they will not display properly in GraphLink or in the calculator's program editor.

As above, variable renamings are performed simultaneously, and the option does not replace variable names inside string literals.

Label renaming: -l X Y, --rename-label X Y

Passing the --rename-label option will rename label X to Y throughout the program, in Goto, Lbl, and Menu( commands. Labels in TI-83 Basic consist of one or two alphanumeric characters. The space between the two label names is required, since otherwise "-lL1 P" would be ambiguous. As above, use "[" for theta.

As with variable renaming (see above), labels are renamed simultaneously, so passing multiple -l options will swap or rotate labels correctly.

Optimize parentheses: -fparens

The optimizer can tell when closing parentheses, quotation marks, and brackets are redundant, and will remove them for you if you pass the -P option.

Optimize blank lines: -fblank-lines

The optimizer will remove useless blank lines from your program automatically if you pass any optimization options; otherwise, it will leave the blank lines untouched, the way you wrote them.

Optimize labels: -L, -fshrink-labels

The optimizer can look for two-byte labels (e.g., "Lbl A2") and automatically rename them using the names of any of the 37 one-byte labels you haven't used yet. It will also delete any unreferenced Lbl lines at the same time. These optimizations are enabled by the -L option.

Optimize expressions: -E, -fexprs

This option is still under development. Essentially, tiopt will try to manipulate the form of your program's arithmetic expressions to make them smaller; for example, using "If Bnot(A" instead of "If (A=0) and B".

As I mentioned above, but this might be a good point to reiterate: tiopt is no substitute for good coding! There are expression optimizations that tiopt will not recognize but a good human programmer will, such as "max(A={1,2,4,8" for "A=1 or A=2 or A=4 or A=8". Also, tiopt uses a dumb brute-force algorithm for selecting expression optimizations, so every potential optimization added to its list will make the optimization process slower. This optimization is definitely in need of improvement, but it's low on my to-do list.

Omega tail hoisting: -fomega

This optimization is still under development.

Omega tail hoisting looks for lines of code in the program with multiple predecessors, all of which are exactly identical. Then it deletes all the predecessor lines and inserts a single copy of the duplicated line immediately before the target. For example, the program

  If A:Then
    "FOO
    Disp Ans
  Else
    If B:Then
      "BAR
      Disp Ans
    Else
      "BAZ
      Disp Ans
    End
  End
would be omega-tail-hoisted to become
  If A:Then
    "FOO
  Else
    If B:Then
      "BAR
    Else
      "BAZ
    End
  End
  Disp Ans

The opposite of omega tail hoisting is alpha hoisting, in which lines with multiple identical successors are transformed in the same way. The optimizer does not yet implement alpha hoisting, and it's not a high priority, since alpha redundancy is typically very easy for a human to spot and avoid while writing the program. Omega redundancy is harder to catch without tiopt's mechanical assistance.

The optimizer does not keep track of the values of variables, so it cannot tell that programs such as

  If A=1:Disp "HELLO
  If A=2:Disp "HELLO
  If A=3:Disp "HELLO
contain redundancy. For all tiopt knows, that program might print "HELLO" three times!

Full optimization: -O, -Omax

The -Omax option simply turns on all the above optimizations at once.

The -O option turns on only those optimizations that do not require global liveness analysis.


Download the source from this directory.

Distribution

If you find any of this information or source code useful, please take it and use it however you like; I ask only that you attribute to me — in some way, however minor — the things I wrote. In particular, I could see the .83P parsing code being useful to someone, and I wouldn't want that person to have to reinvent the wheel when my "wheel" is readily available.

If you find a bug in tiopt, or have comments, questions, or feature requests, I'd like to hear about it! You can find my e-mail address on my Web site, or through my profile on ticalc.org.

Some of the TI-84 and TI-84+ token information came from TokenReader, a program by Joris Roos. Any mistakes in the token information are probably my fault.

The information on undocumented variable tokens came from Xtravar by Brendan Fletcher. Any mistakes are probably my fault.


This page was last updated    28 October 2007
All original code, images and documentation on this page are freely distributable. Please keep them that way.