[MLton] Updates on various student projects

Over the last six months or so, I've supervised a number of student
projects undertaken in the context of MLton. I thought it worthwhile
to give an update on them.


* LLVM Codegen

Brian Leibig (BS/MS student, RIT) successfully completed his capstone
MS Project titled "An LLVM Backend for MLton" in August 2013. This
project explored the design and implementation of an LLVM code
generator, modeled after MLton’s original C code generator. Brian's
final report (including some benchmark results) is available at:
  http://www.cs.rit.edu/~bal6053/msproject/
and the code is available at:
  https://github.com/bleibig/mlton/tree/llvm

The LLVM codegen was relatively easy to develop, though there are few
awkward bits. There is a lot of boilerplate that needs to go into each
textual .ll file (common type definition, common intrinsics
declarations, etc.), but the textual .ll files do not support
CPP-style #include directives; the consequence is that there are a lot
of constant strings left in llvm-codegen.fun. Also, the llvm system
compiler tool ("llc") does not allow one to specify that the "mem2reg"
optimization should be applied, so we need to separately invoke the
llvm optimizer tool ("opt") and the llvm system compiler tool ("llc")
to generate object code.

The LLVM codegen seems to be quite competitive with the native and C
codegens. In Brian's benchmark results, though, it should be pointed
out that the C codegen uses a "-chunkify coalesce4096" strategy (the
default for the C codegen), the native codegen uses a "-chunkify func"
strategy (the default for the native codegens), and the LLVM codegen
uses a "-chunkify one" strategy (the current default for the LLVM
codegen). It probably makes more sense for the LLVM codegen to use the
same chunkify strategy as the C codegen, in order to reduce compile
time on larger projects.  (Also, see
http://sourceforge.net/p/mlton/mailman/message/31219150/ for some
analysis of the various chunkify strategies.)

I'll be working to integrate Brian's llvm branch into MLton's master
branch. The main TODOs are general code review and cleanup and to
allow for the specification of the "llc" and "opt" tools and options
via command line arguments (by way of analogy with the current "-cc"
and "-cc-opt" options).

Longer term TODOs include taking additional advantage of LLVM. We
should be able to use LLVM tail-calls (though, not guaranteed on all
architectures) instead of a trampoline. It might also be possible to
push down some aliasing information for use by LLVM; I've long
suspected that being able to "explain" that (SML) stack locations do
not alias (SML) heap locations would improve the generated code by gcc
or llc/opt.


* Misc. infrastructure improvements

Adam Archambault (BS student, RIT), funded by an internal seed grant,
worked on "MLton: Maintenance and Development" during Spring/Summer
2013. Adam accomplished a number of helpful infrastructure
improvements.

He refactored the transformation passes in the XML, SXML, SSA, SSA2,
and RSSA ILs to match a common signature (see
https://github.com/MLton/mlton/pull/10).

He moved a number of utility structures from the AST IL directory to
the Atoms utility directory; for example, "structure WordSize" is used
pervasively through the compiler, but was being defined as part of the
AST IL (whereas, "structure WordX", also used pervasively through the
compiler, is defined as part of Atoms). This code is available at:
  https://github.com/staniels/mlton/tree/ast-atoms
and should be fairly easy to merge. This work also uncovered that the
treatment of type variables in the AST IL and the type-checking pass
is unsatisfactory and brittle; due to the prenex polymorphism that
characterizes the Damas-Milner type system that underlies the type
system of Standard ML, the type-checker is able to avoid maintaining
an explicit type-variable environment and to avoid alpha- renaming
type variables in the type-checked, annotated CoreML and XML ILs. This
is in contrast to the treatment of all other identifiers, for which
explicit environments are maintained and which are alpha-renamed in
the type-checked, annotated Core and XML ILs.

He refactored the C codegen to simplify the generated code. This code
is available at:
  https://github.com/staniels/mlton/tree/c-codegen-cleanup
The idea was to emit a simple top-level switch dispatch on the
block-index to goto the appropriate block and to emit a simple
unordered set of basic blocks that always use gotos for intra-block
transfers; this is in contrast with the current C codegen that
attempts to perform some amount of layout of blocks to support
"fall-thru" from one block to another and to mix the top-level switch
dispatch on the block-index with non-entry block code. The intuition
is that gcc is as least as well positioned to choose the layout of
basic blocks (since it necessarily constructs a CFG for input code and
chooses a basic block layout). Adam also, compared the performance of
the original and refactored C code generators, and, surprisingly to
me, the original, complex C codegen generally performed better than
the refactored, simple C codegen. I was surprised, since the original,
complex C codegen isn't doing anything particularly sophisticated; it
is essentially just greedily falling thru to un-emitted blocks. I was
hoping that gcc would be able to do better with intra-procedural
loops. I'm still not quite ready to give up on the simplified C
codegen, but it may take a little more tweaking.


* SIMD primitives

Tucker DiNapoli (BS student, University of New Hampshire) participated
in the 2013 Google Summer of Code program with his project titled
"SIMD Support for MLton". This project explored the design of a core
set of SIMD primitives, the implementation of the SIMD primitives in
the C and amd64 code generators, and the application of the SIMD
primitives in an SML library. This code is available at:
  https://github.com/hitchiker42/mlton/tree/master
Tucker did a great job examining the various Intel and AMD SIMD
instruction sets, developing a core set of SIMD primitives, developing
both software (i.e., non SIMD) reference implementations of the
primitives and native (i.e., SIMD) implementations of the primitives
for both the C codegen and the native amd64 codegen. There were a few
difficulties extending the compiler to support SIMD datatypes and
primitives, and there are some rough edges with respect to alignment
of SIMD data (which typically require 16-byte alignment for fast
aligned access), but I'm confident that we'll be able to merge this
work after a little bit more review and cleanup. The primitives are
nicely parameterized over element type and vector width, so it should
be easy to extend to larger SIMD datatypes in the future (e.g.,
Intel's forthcoming AVX-512 extensions). Ultimately, we'd like to
provide a bit more programmer-friendly SIMD Library (e.g., with
convenience functions for conversion from/to appropriate
arity-tuples). Long term would be to develop optimizations that
introduce SIMD primitives into a program; the ICFP'13 paper "Automatic
SIMD Vectorization for Haskell" (Petersen, Orchard, & Glew) would be a
good starting point (not least because their intermediate language is
inspired in part by MLton's SSA IL).


* Multi-entry functions

David Larsen (BS/MS student, RIT) successfully proposed his capstone
MS Thesis titled “Multi-entry Function Calls for MLton” in July 2013.
This thesis is exploring the design, implementation, and application
of a new IL that supports "multi-entry" functions, whereby a function
can be called at one of multiple entry points. Such "multi-entry"
functions can be motivated by the control-flow graph representation of
functions, by allowing multiple entry nodes (just as multiple exit
nodes are often allowed). A “multi-entry” function can be used to
perform call-pattern specialization (ICFP'07; Peyton Jones) and to
improve the performance of mutually tail-recursive functions. David
presented some initial findings at the ACM SIGPLAN Workshop on ML in
September 2013.

More details on this work can be found at:
  http://www.cs.rit.edu/~dcl9934/thesis/
  http://www.cs.rit.edu/~mtf/mlton/multi_entry_ml13_paper.pdf
  http://www.cs.rit.edu/~mtf/mlton/multi_entry_ml13_talk.pdf
and the code can be found at:
  https://github.com/caltry/mlton/tree/multi-entry-funcs
  https://github.com/MatthewFluet/mlton/tree/multi-entry-funcs--opts

Overall, it has been *very* easy to extend the ILs and codegens to
support multi-entry functions.  Most of the SSA and SSA2 optimizations
passes could be updated in under an hour.  Furthermore, it turns out
that the Machine IL was sufficiently low-level that it effectively
already supported multi-entry functions, and none of the codegens have
required modification.

On the positive side, we have found that using multi-entry functions
to turn mutually tail-recursive functions into a single function with
multiple entry points (which can be subsequently optimized by
IntroduceLoops to replace the interprocedural self-tail calls with
intraprocedural jumps) leads to substantial speedups on a crafted
even-odd benchmark
(https://github.com/caltry/mlton/blob/multi-entry-funcs/benchmark/tests/even-odd.sml).
 Similarly, a new optimization that turns a function that immediately
case-analyzes an argument into a function with an entry-point per
constructor and turns calls to that function with a known constructor
to a call to the appropriate entry point seems to have some small
improvements.

Curiously, we also found improvements with a stress-test
transformation that just duplicated each entry-point of a function a
fixed number of times and round-robin transformed calls to the
original entry point to a new entry.  I think that this enabled one of
the flattening passes that required all calls to the function to have
a manifest tuple in order to flatten; by having multiple entry points,
the flattening pass simply requires all calls to an entry point to
have a manifest tuple in order to flatten that entry point.  That is,
multi-entry can enable a very weak form of polyvariance, whereby we
can treat each call site differently.  The logical next step is to
refine the flattening optimization to introduce entry points on demand
for the call-sites that have manifest tuples.

On the negative side, we don't see across the board improvements in
the benchmark.  Particularly disturbing is that we are seeing a lot of
variance due to seemingly innocuous low-level details.  In one
example, we see the 'tak' benchmark have a 30% difference in execution
time due to the choice of assembly label names, which seemingly should
have no effect on the instruction stream executed.

In any case, the implementation cost of multi-entry is so low, that I
think it is worthwhile, even if there aren't a lot of opportunities to
exploit it.

------------------------------------------------------------------------------
Shape the Mobile Experience: Free Subscription
Software experts and developers: Be at the forefront of tech innovation.
Intel(R) Software Adrenaline delivers strategic insight and game-changing 
conversations that shape the rapidly evolving mobile landscape. Sign up now. 
http://pubads.g.doubleclick.net/gampad/clk?id=63431311&iu=/4140/ostg.clktrk
_______________________________________________
MLton-devel mailing list
[email protected]; [email protected]
https://lists.sourceforge.net/lists/listinfo/mlton-devel