trivia.balland2006

2017-01-24

Trivia.Balland2006

https://travis-ci.org/guicho271828/trivia.balland2006.svg?branch=master

This is an optimizer implementation based on (Balland et.al. 2006).

c.f.

Le Fessant, Fabrice, and Luc Maranget. Optimizing pattern matching. ACM SIGPLAN Notices. Vol. 36. No. 10. ACM, 2001.

Emilie Balland, Pierre-Etienne Moreau. Optimizing pattern matching compilation by program transformation. [Technical Report] 2006, pp.19. <inria-00001127v2>

Usage & Dependencies

After loading Trivia, use (ql:quickload :trivia.balland2006.enabled) to activate the optimizer.

It depends on the following libraries:

Trivia by Me

NON-Optimized Pattern Matching Library

Type-i by Me

Type inference utility for fundamentally 1-arg predicates

alexandria

Alexandria is a collection of portable public domain utilities.

iterate

Jonathan Amsterdam's iterator/gatherer/accumulator facility

Optimizer Details

In (Emillie 2006), their optimization rule reduces the number of assignments (let) and tests (if). However, since current state-of-the-art common lisp implementations (namely, sbcl and ccl) eliminates unnecessary assignments by default, so we do not focus on the assignments in our compiler. Thus, Assignment optimization in Section 3.1, e.g., Constant Propagation, Dead Variable Elimination, Inlining, Let-Fusion are not considered.

The main focus is on reducing the number of conditional check, which may involve a function call and is costly. We implement Section 3.2 Reducing the number of tests, which describes: Fusion, Interleaving, Ifswapping.

Patterns Transformation Rules

The compatibility of test-forms of guard1 pattern is determined in form-to-form basis, and the types are detected from the predicate form. We used :type-i package for this purpose. After the types are detected, one of the following translation rules are applied iteratively.

Fusion

Consider the following match:

(match1 what
  ((guard1 it (consp it)
           (car it) (guard1 x (= 1 x))
           (cdr it) (guard1 y (null y))) body1)
  ((guard1 it (consp it)
           (car it) (guard1 x (stringp x))
           (cdr it) (guard1 y (null y))) body2))

body1 has an environment where

it <-- (consp it) <-- can be infered as type `cons'
car <-- (= 1 car) <-- not inferred right now: an anonymous type e.g. #:ANON0
cdr <-- (null y)  <-- type `null'

body2 has an environment where

it <-- (consp it) <-- can be infered as type `cons'
car <-- (stringp x) <-- can be infered as type `string'
cdr <-- (null y)  <-- type `null'

Since the two checks have type `cons' in common, the first check can be merged. In the above case, the original code is compiled into:

(match what
  ((guard1 it (consp it) (car it) #:car (cdr it) #:cdr)
   (match* (#:car #:cdr)
     (((guard x (= 1 x))     (guard y (null y))) body1)
     (((guard x (stringp x)) (guard y (null y))) body2))))

Interleaving

Consider the following match is done under the environment in which `what' is known to be of type `list'.

(match1 what
  ((guard1 it (consp it)) body1)
  ((guard1 it (null  it)) body2))

Since `cons' and `null' are the exhaustive partition of type `list', this can be optimized into

(match1 what
  ((guard1 it (consp it)) body1)
  (_                      body2))

to avoid checks.

Note: in (Emillie 2006), 2 variations of interleaving rule is proposed, one general case, and the other specialized case if i'1 and i'2 being nop. As a good news, in trivia's context, i'1 and i'2 are always nop, and exactly 1 clause should match at a time.

Note: In order to calculate the applicability of this rule, information about the environment is essential. however, we try not to use cltl2 environment as of now, since it is out of scope of trivia: Conditional expression may be removed using the outside environment, but we focus on the removal of the tests inside trivia.

Quoting (Emillie 2006):

IfInterleaving:

if(c1,i1,i'1); if(c2,i2,nop) ? if(c1,i1,i'1;if(c2,i2,nop)) IF c1?c2
if(c1,i1,nop);if(c2,i2,i'2)  ? if(c2,i2,if(c1,i1,nop);i'2) IF c1?c2

These two rules reduce the number of tests at run time because one of the tests is moved into the ?else? branch of the other. The second rule can be instantiated and used to swap blocks. When i'1 and i'2 are reduced to the instruction nop, the second rule can be simplified into:

if(c1,i1,nop);if(c2,i2,nop)?if(c2,i2,if(c1,i1,nop)) IF c1?c2

Swapping

Above interleaving rule only applies when the two checks are adjacsent. Therefore, we swap the order of patterns.

Quoting (Emillie 2006):

After all, we obtain the following rule corresponding to the swapping of two conditional adjacent blocks. This rule does not optimize the number of tests but is useful to join blocks subject to be merged thanks to a smart strategy.

IfSwapping: if(c1,i1,nop);if(c2,i2,nop)?if(c2,i2,nop);if(c1,i1,nop) IF c1?c2

Transformation Strategy

The quality of the resulting code is affected by the strategy for selecting which rule to apply in what order. We again followed the simple strategy in (Emillie 2006).

Using basic strategy operators such as Innermost(s) (which applies s as many times as possible, starting from the leaves), s1 | s2 (which applies s1 or s2 indifferently), repeat(s) (which applies s as many times as possible, returning the last unfailing result), and r1 ; r2 (which applies s1, and then s2 if s1 did not failed), we can easily define a strategy which describes how the rewrite system OptSys should be applied to normalize a PIL program:

Innermost( repeat(ConstProp | DeadVarElim | Inlining | LetFusion | IfFusion | IfSwapping) ;
           repeat(IfInterleaving))

Now in our implementation this is simplified as follows:

Innermost( repeat( Fusion | Swapping) ; repeat(Interleaving))

Author & Copyright

Copyright (c) 2015 Masataro Asai (guicho2.71828@gmail.com)

Licensed under the LLGPL.

Author
Masataro Asai
License
LLGPL