Next: Introduction, Previous: (dir), Up: (dir) [Contents][Index]
This is the trivia.balland2006 Reference Manual, version 0.1, generated automatically by Declt version 2.4 "Will Decker" on Wed Jun 20 12:40:54 2018 GMT+0.
| • Introduction: | What trivia.balland2006 is all about | |
| • Systems: | The systems documentation | |
| • Files: | The files documentation | |
| • Packages: | The packages documentation | |
| • Definitions: | The symbols documentation | |
| • Indexes: | Concepts, functions, variables and data types |
* Trivia.Balland2006 [[https://travis-ci.org/guicho271828/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. #+BEGIN_QUOTE 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.#+END_QUOTE ** Usage & Dependencies After loading Trivia, use =(ql:quickload :trivia.balland2006.enabled)= to activate the optimizer. It depends on the following libraries: + [[https://github.com/guicho271828/trivia][Trivia by Me]] :: NON-Optimized Pattern Matching Library + [[https://github.com/guicho271828/type-i][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: #+BEGIN_SRC lisp (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)) #+END_SRC 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: #+BEGIN_SRC lisp (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)))) #+END_SRC *** Interleaving Consider the following match is done under the environment in which `what' is known to be of type `list'. #+BEGIN_SRC lisp (match1 what ((guard1 it (consp it)) body1) ((guard1 it (null it)) body2)) #+END_SRC Since `cons' and `null' are the exhaustive partition of type `list', this can be optimized into #+BEGIN_SRC lisp (match1 what ((guard1 it (consp it)) body1) (_ body2)) #+END_SRC 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): #+BEGIN_QUOTE 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 #+END_QUOTE *** Swapping Above interleaving rule only applies when the two checks are adjacsent. Therefore, we swap the order of patterns. Quoting (Emillie 2006): #+BEGIN_QUOTE 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 #+END_QUOTE ** 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). #+BEGIN_QUOTE 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: #+END_QUOTE : 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.
Next: Files, Previous: Introduction, Up: Top [Contents][Index]
The main system appears first, followed by any subsystem dependency.
| • The trivia.balland2006 system: |
Masataro Asai
LLGPL
Optimizer for Trivia based on (Balland 2006)
0.1
trivia.balland2006.asd (file)
Files are sorted by type and then listed depth-first from the systems components trees.
| • Lisp files: |
| • The trivia.balland2006.asd file: | ||
| • The trivia.balland2006/package.lisp file: | ||
| • The trivia.balland2006/optimizer.lisp file: | ||
| • The trivia.balland2006/column-swapping.lisp file: |
Next: The trivia<dot>balland2006/package<dot>lisp file, Previous: Lisp files, Up: Lisp files [Contents][Index]
/home/quickref/quicklisp/dists/quicklisp/software/trivia.balland2006-20170124-git/trivia.balland2006.asd
trivia.balland2006 (system)
Next: The trivia<dot>balland2006/optimizer<dot>lisp file, Previous: The trivia<dot>balland2006<dot>asd file, Up: Lisp files [Contents][Index]
trivia.balland2006 (system)
package.lisp
Next: The trivia<dot>balland2006/column-swapping<dot>lisp file, Previous: The trivia<dot>balland2006/package<dot>lisp file, Up: Lisp files [Contents][Index]
package.lisp (file)
trivia.balland2006 (system)
optimizer.lisp
Previous: The trivia<dot>balland2006/optimizer<dot>lisp file, Up: Lisp files [Contents][Index]
optimizer.lisp (file)
trivia.balland2006 (system)
column-swapping.lisp
find-tree (function)
Next: Definitions, Previous: Files, Up: Top [Contents][Index]
Packages are listed by definition order.
| • The trivia.balland2006-asd package: | ||
| • The trivia.balland2006 package: |
Next: The trivia<dot>balland2006 package, Previous: Packages, Up: Packages [Contents][Index]
/home/quickref/quicklisp/dists/quicklisp/software/trivia.balland2006-20170124-git/trivia.balland2006.asd
Previous: The trivia<dot>balland2006-asd package, Up: Packages [Contents][Index]
package.lisp (file)
Definitions are sorted by export status, category, package, and then by lexicographic order.
| • Exported definitions: | ||
| • Internal definitions: |
Next: Internal definitions, Previous: Definitions, Up: Definitions [Contents][Index]
| • Exported functions: |
Previous: Exported definitions, Up: Exported definitions [Contents][Index]
optimizer.lisp (file)
optimizer.lisp (file)
optimizer.lisp (file)
optimizer.lisp (file)
optimizer.lisp (file)
optimizer.lisp (file)
column-swapping.lisp (file)
return true if p2 depends on p1
column-swapping.lisp (file)
optimizer.lisp (file)
Previous: Exported definitions, Up: Definitions [Contents][Index]
| • Internal functions: |
Previous: Internal definitions, Up: Internal definitions [Contents][Index]
optimizer.lisp (file)
optimizer.lisp (file)
optimizer.lisp (file)
column-swapping.lisp (file)
optimizer.lisp (file)
optimizer.lisp (file)
optimizer.lisp (file)
optimizer.lisp (file)
optimizer.lisp (file)
optimizer.lisp (file)
Returns true for types under, t1, t2, if under = t1 + t2 and nothing more
optimizer.lisp (file)
Previous: Definitions, Up: Top [Contents][Index]
| • Concept index: | ||
| • Function index: | ||
| • Variable index: | ||
| • Data type index: |
Next: Function index, Previous: Indexes, Up: Indexes [Contents][Index]
| Jump to: | F L T |
|---|
| Jump to: | F L T |
|---|
Next: Variable index, Previous: Concept index, Up: Indexes [Contents][Index]
| Jump to: | A B D F G I P S T |
|---|
| Jump to: | A B D F G I P S T |
|---|
Next: Data type index, Previous: Function index, Up: Indexes [Contents][Index]
Previous: Variable index, Up: Indexes [Contents][Index]
| Jump to: | P S T |
|---|
| Jump to: | P S T |
|---|