oynk - perform scalar optimizations and analysis on old SUIF programs.
oynk [ options ] infile outfile
The program oynk performs scalar optimizations and analysis. It reads old SUIF procedures from infile, and writes the resulting analyzed and optimized procedure into outfile. Optimizations are indicate by the -P option.
Oynk processes its input in several phases. The phases can be run internally, which means that the intermediate output of each phase is kept internal to oynk and never written out; internal phases communicate through internal data structures. Some phases can be used externally where the output of a phase is immediately written out as a SUIF file. External phases must reread the SUIF file. Internal execution is more efficient but external execution provides for more debugging and experimentation.
Some phases are automatically invoked before and after a user-requested phase. The automatic phases are necessary because they build the data structures necessary for most oynk functions and they perform cleanup and rewrites.
Every time that oynk executes, it runs a phase called structure that performs control flow analysis, assigns a unique integer to each node, and does some rudimentary constant propagation pertaining to branch labels. The result of structure is a control flow graph that is necessary for later phases.
Many phases require value numbering, an algorithm that identifies similar expressions and gives them a number or name. The phase sig performs this numbering. If you are interested in how this is done, you should consult the Red Dragon Book.
To request a phase, you give the flag -P<phase-name>; there is no space between the P and <phase-name>, e.g. -Pconst. Right now, oynk recognizes the following <phase-names>
sig Run only sig and write out the output. Without debugging flags, this is essentially a no-op, but with the -D flag, it is a convenient method to find out what control-flow graph oynk is processing, and which expressions oynk considers congruent.
Run constant propagation, simplify the code, and write out a SUIF file. Constant propagation only applies to integers, constant addresses, and branch labels. This phase also does limited copy propagation. The phase dstore always follows const internally.
The opposite of ivar. Rewrites induction variables in FOR loops in terms of the loop induction variable. This strength increasing transformation is useful in making dependence analysis more precise.
Dead store elimination. This phase will eliminate dead induction variables.
reg Run global register allocation.
Run availability using both iterative and interval analysis, and then compare their results.
Run the anticipation problem; this invokes avail first.
pp Run the placement possible problem; both avail and anticip are automatically invoked before this phase.
Clean up code after pp. This causes the entire code motion suite to be run: avail, anticip, and pp.
sr Strength reduction. This optimization turns affine combinations of loop indices into induction variables.
Reassociate array indexing expressions to improve strength reduction and dependency analysis.
If the -P flag is not given then slive, or code motion is assumed. The code motion algorithm is based on Morel-Renvoise formulation of partial redundancy elimination.
Oynk also recognizes other flags:
-T give phase timings, and other performace data. For each procedure, it gives the name of the procedure followed by the number of forward irreducibilites, and the number of reverse irreducibilites, and the word structure. Following this line are a series of lines, one for each of the phases executed on that procedure. The format of the lines are:
1. the user time in seconds
2. the system time in seconds.
3. the value of sbrk() after execution of the phase. This information indicates, very roughly, the memory requirement for the phase. 4. the number of nodes in the flow graph. 5. the string ``->''
6. the number of nodes in the ``reduced'' flow graph. 7. the number of iterations required to compute the phase's data. 8. the name of the phase.
-Fsu Reorder expressions using Sethi-Ullman numbering. This is a rewriting phase which occurs as SUIF is being written out.
-D This is the major debugging flag. It causes each SUIF instruction to be annotated with information from each phase. You should be aware that this can increase the size of the SUIF files dramatically.
-g Prints out the control flow graph in a very difficult to understand manner. If you need this, please consult with me.
Set the debugging level. The interpretation of this level is dependent on the phase.
sharlit(1), oynk(1), moo(1)
S. Tjiang and J. Hennessy. Sharlit: A tool for building optimizers. In SIGPLAN Conference on Programming Language Design and Implementation, 1992, pp 82-93.
S. Tjiang. Automatic Generation of Data-flow Analyzers: A tool for building optimizers Ph.D. Thesis, Stanford University, July 1993.
Oynk should be rewritten to accept new SUIF; moo is a start of this.
Oynk was written by Steven Tjiang.