develooper Front page | perl.perl6.internals | Postings from September 2005

Optimizer Documentation

Thread Next
Curtis Rawls
September 1, 2005 17:44
Optimizer Documentation
Message ID:
As part of my Summer of Code project, I wanted to improve the
documentation of the optimizer.  This was especially relevant for me
since I had to learn it my self by trial and error and asking
questions.  So here is my first draft of the optimizer documentation. 
 I tried to include the most important information for someone new to
the project or this area.

I would appreciate some Parroters to take a look, whether you are
familiar with this area of Parrot or not, since it is most useful to
newcomers.  Which parts are/are not interesting/relevant?  Does it
raise any pertinent questions that are not answered?  Anything
missing?  Anything just plain wrong?

Also, this is in plain text format.  What is the standard way to
convert a document to POD format?


----Begin Optimizer Documentation-----


This document describes how the IMCC optimizer works.

The objective of the IMCC optimizer is to take a PASM function as
input and  apply code-improving transformations to it to be more
efficient, i.e. improving execution time and reducing code size.  It
must do this while preserving the same code behavior.

The optimizer uses a number of data structures to build a model of the
code to be optimized.


The IMC_Unit structure contains all the information known about a
function.    It is passed in to each optimizer method.


Each instruction line has an Instruction structure.  Pointers to the
first and last Instruction are stored in IMC_Unit.  Instructions are
stored as a linked list.  To iterate through all Instructions, use:

Instruction *ins;
for (ins = unit->instructions; ins; ins = ins->next) {


Basic blocks are the most important structure for optimization.  A
basic block identifies a block of instructions that will all execute
in sequence without jumps into or out of that block.  All labels will
appear at the beginning of a block, and all conditional or
unconditional jumps will appear at the end.  Basic_block structures
are stored as an array of pointers, each with an index that denotes
their position in the array.  Block 0 is implicitly the top block.  To
iterate through all Basic_blocks, use:

int i;
for (i = 0; i < unit->n_basic_blocks; i++) {


Edges denote the flow of control between Basic_blocks.  Edges and
Basic_blocks together make up the basic CFG.  Each Basic_block has
*pred_list and *succ_list pointer to the first predecessor edge and
successor edge, respectively.  Each edge has a *to and *from pointer
to the  Basic_blocks it joins.  To iterate through all predecessor
Edges, use:

Edge *pred;
for (pred = to->pred_list; pred; pred=pred->pred_next) {


Loop_info structures denote the presence of loops in the instructions.
 They are found by identifying backedges, where control passes from a
tail block to the head of the loop.  Loop_info stores the header,
preheader, exit blocks, and depth of the loop.


Set is a useful structure for defining sets of integers, which map to
indexes of structures.  This is used most often to create sets of
Basic_blocks.  Dominators, dominance frontiers, and loops use Set.  A
Set must be a defined size, and cannot grow or shrink.  Most standard
set operations are implemented: add, contains, copy, equal, union, and

Optimizations are organized into an optimization loop within
imc_reg_alloc() in reg_alloc.c.  The ordering is based on the amount
of CFG information needed by each group of optimizations:
pre_optimize(), cfg_optimize(), and optimize().  Each optimization
function (group and individual) returns an int, with TRUE denoting
that an optimization has been performed and a change to the code has
been made.  The power of the optimizer is that performing one
optimization may often allow another to be performed as well.  Once
all optimizations have been run without changes, the optimizer is

The optimizer loop works as follows:
1.  Run all pre_optimize() optimizations until none make a change.
2.  Build basic block info.
3.  Run all cfg_optimize() optimizations.  If one makes a change, go to step 1.
4.  Build all other CFG info (dominators, loops, life analysis).
5.  Run all optimize() optimizations.  If one makes a change, go to step 1.

Two cfg_optimize() or optimize() optimizations cannot be run in a row.
 This is because most of these make the CFG information invalid when a
change is performed, and the CFG must be rebuilt.

Pre optimizer

Optimizations using only Instruction info, no CFG constructed.

strength_reduce() - converts an expensive instruction to a simpler one

if_branch() - Convert if/branch/label constructs to a simpler form

CFG optimizer

Optimizations using Basic_block info.  These functions invalidate the
CFG when a change is made.

branch_branch() - Replaces a branch directly to another branch with a
single branch to the end of the chain

unused_label() - Removes unused labels

dead_code_remove() - Removes unreachable code


constant_propagation() - conservative constant propagation, i.e.
replaces "1 + 2" with "3"

clone_remove() - remove a clone, TURNED OFF

used_once() - removes an instruction when the register written is only
used once (only appears in that instruction)

loop_optimization() - move an invariant instruction outside of the
loop, TURNED OFF (not currently working)

Thread Next Perl Programming lists via nntp and http.
Comments to Ask Bjørn Hansen at | Group listing | About