Thread: [MLton-commit] SF.net SVN: mlton:[7561] mlton/trunk

SourceForge Headquarters 225 Broadway Suite 1600 San Diego, CA 92101 +1 (858) 422-6466

Revision: 7561
          http://mlton.svn.sourceforge.net/mlton/?rev=7561&view=rev
Author:   fluet
Date:     2012-02-25 04:12:59 +0000 (Sat, 25 Feb 2012)
Log Message:
-----------
Fixed bug in redundant SSA optimization.

Thanks to Lars Magnusson for the bug report and example.

The redundant SSA optimization eliminates redundant function and label
arguments; an argument of a function or label is redundant if it is
always the same as another argument of the same function or label.
The analysis finds an equivalence relation on the arguments of a
function or label, such that all arguments in an equivalence class are
redundant with respect to the other arguments in the equivalence
class; the transformation selects one representative of each
equivalence class and drops the binding occurrence of
non-representative variables and renames use occurrences of the
non-representative variables to the representative variable.  The
analysis finds the equivalence classes via a fixed-point analysis.
Each vector of arguments to a function or label is initialized to
equivalence classes that equate all arguments of the same type; one
could start with an equivalence class that equates all arguments, but
arguments of different type cannot be redundant.  Variables bound in
statements are initialized to singleton equivalence classes.  The
fixed-point analysis repeatedly refines these equivalence classes on
the formals by the equivalence classes of the actuals.

The original redundant SSA optimization used a representation of
equivalence classes that was quadratic in the number of arguments to a
function or label.  This was acceptable until the development of a
flattening optimization that would flatten tuples completely; such
full flattening could increase the number of arguments to a function
to > 3000:
  http://mlton.org/pipermail/mlton/2004-February/025131.html
  http://mlton.org/pipermail/mlton/2004-February/025133.html
  http://mlton.org/pipermail/mlton/2004-February/025137.html

Two subsequent revisions of the redundant SSA optimization (r2929 and
r2932) eliminated the quadratic implementation of equivalence classes
and made performance improvements:
  http://mlton.svn.sourceforge.net/viewvc/mlton?view=revision&revision=2929
  http://mlton.svn.sourceforge.net/viewvc/mlton?view=revision&revision=2932
  http://mlton.org/pipermail/mlton/2004-March/025149.html

Unfortunately, the second of these revisions introduced a bug whereby
the analysis failed to terminate with the fixed point; instead, it
could terminate with some non-redundant arguments left in the same
equivalence class.  The transformation would then eliminate a distinct
argument to the function or label, changing the behavior of the
program.

It was not entirely clear how to fix the bug in the last version of
the optimization (corresponding to the second of the above revisions,
with only cosemetic revisions since).  While reverting to the first of
the above revisions eliminated the bug in the example program, there
seemed to be some useful techniques in the second of the above
revisions.

This version of the optimization adopts a more transparently correct
fixed-point analysis, but includes techniques that lead to fast
convergence.  The transparent correctness comes from accumulating a
list of refinements due to the flow of actuals to formals and
repeatedly applying all of the refinements until there are no changes
to the equivalence classes.  The fast convergence comes from
discarding from the list of refinements any refinement where the
formals have been refined to singleton equivalence classes; note that
any function or label with zero or one argument necessarily has its
formal in a singleton equivalence class, and need not be included in
the initial refinement accumulation.  In addition, it was observed
that the "elements" field of Element.Class.t, which recorded the
elements in the equivalence class, was unused.  Eliminating this field
led to a number of additional simplifications.

This version correctly transforms the example program that
demonstrated the bug in the last version; the example program has no
opportunities for redundant argument elimination, but the analysis
requires four iterations to converge to the fixed point.

This version behaves identically to the last version on a self
compile.  A self-compile has 82 non-singleton equivalence classes and
the largest non-singleton equivalence classes are 5 classes of 5
elements.  The analysis requires five iterations to converge to the
fixed point.  The performance of this version is comparable to the
last version.

Revision Links:
--------------
    http://mlton.svn.sourceforge.net/mlton/?rev=2929&view=rev
    http://mlton.svn.sourceforge.net/mlton/?rev=2932&view=rev

Modified Paths:
--------------
    mlton/trunk/doc/changelog
    mlton/trunk/mlton/ssa/redundant.fun

This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.

------------------------------------------------------------------------------
Virtualization & Cloud Management Using Capacity Planning
Cloud computing makes use of virtualization - but cloud computing 
also focuses on allowing computing to be delivered as a service.
http://www.accelacomm.com/jaw/sfnl/114/51521223/
_______________________________________________
MLton-commit mailing list
MLt...@li...; mlt...@ml...
https://lists.sourceforge.net/lists/listinfo/mlton-commit

Thread: [MLton-commit] SF.net SVN: mlton:[7561] mlton/trunk

A whole-program optimizing compiler for Standard ML

mlton-commit