Prototyping GHC Optimizations with HERMIT


Andrew Farmer
http://andrewfarmer.name

Andy Gill
andygill@ittc.ku.edu

(with Neil Sculthorpe, Nick Frisby, Ed Komp, Ryan Scott, and Adam Howell)

Functional Programming Group
Information and Telecommunication Technology Center
University of Kansas

Haskell Implementors Workshop
September 22, 2013

 

What is HERMIT?

What is HERMIT?

image from http://www.angelfire.com/ks/larrycarter/LC/OldGuardCameron.html

What is HERMIT?

image from http://www.angelfire.com/ks/larrycarter/LC/OldGuardCameron.html

Demo

What does HERMIT provide?

HERMIT's new architecture

Is HERMIT real?

HERMIT requires GHC >= 7.6

  1. cabal update
  2. cabal install hermit
  3. hermit Main.hs

Is HERMIT real?

HERMIT requires GHC >= 7.6

  1. cabal update
  2. cabal install hermit
  3. hermit Main.hs

The hermit command just invokes GHC with some default flags:

% hermit Main.hs
ghc Main.hs -fforce-recomp -O2 -dcore-lint
    -fsimple-list-literals -fexpose-all-unfoldings
    -fplugin=HERMIT
    -fplugin-opt=HERMIT:Main:

 

So What's New?

So What's New?

Github: https://github.com/ku-fpg/hermit

Abstraction

Reverse Script: Haskell '12

consider 'rev
    down
    consider 'rev
    fix-intro

    prune-td (unfold-rule "ww")

    prune-td (unfold '.)
    prune-td (unfold '.)

    prune-td (unfold 'wrap) 
    prune-td (unfold 'wrap)
    prune-td (unfold 'unwrap)
    prune-td (unfold '.)

    bash

    any-bu (case-float-arg)
    prune-td (unfold-rule "repH ++")

    prune-td (unfold-rule "rep-abs-fusion")

    prune-td (unfold 'repH)
    prune-td (unfold '.) 
    bash
    focus (consider case) (eta-expand 'ys)
    any-bu case-float-app
    prune-td (unfold-rule "(:) ++")
    prune-td (unfold-rule "[] ++")
    prune-td (unfold 'fix) 
    bash 
    unshadow

Reverse Script: Haskell '13

binding-of 'rev
ww-result-split-static-arg-unsafe 1 [0] [| absH |] [| repH |]
bash
{ rhs-of 'work
  lam-body
  eta-expand 'acc
  lam-body
  bash-extended-with [ push-unsafe 'repH
                     , forward ww-result-fusion
                     , apply-rules [ "repH ++"
                                   , "repH (:)"
                                   , "repH []"] ]
}
one-td (unfold 'absH)

NeverActive RULES

Recall: GHC RULES are lifted into HERMIT rewrites.

New in GHC 7.8: Specify RULES that are never applied automatically.

{-# RULES 
"monad/left-unit"     [~] forall k x  . return x >>= k  = k x 
"monad/right-unit"    [~] forall m    . m >>= return    = m
"monad/associativity" [~] forall m k h. (m >>= k) >>= h = m >>= \x -> k x >>= h
  #-}

Allow library writers to provide rewrites to HERMIT users.

Plugin DSL

Two concerns:

Plugin DSL

optimize :: ([CommandLineOption] -> OM ()) -> Plugin
plugin :: Plugin
plugin = optimize $ \ options -> phase 0 $ interactive [] options

Plugin DSL: Extending HERMIT

  1. Create a KURE transformation:
betaReduce :: RewriteH CoreExpr
betaReduce = do App (Lam v e1) e2 <- idR
                return $ Let (NonRec v e2) e1
  1. Define a custom dictionary of transformations:
cmds :: [External]
cmds = [ external "my-beta" betaReduce [ "help text" ] ]
  1. Create a HERMIT plugin which uses the dictionary:
plugin :: Plugin
plugin = optimize $ \ options -> phase 0 $ interactive cmds options

Demo

Plugin DSL: Packaging and Using

HERMIT-based GHC Plugins are just Cabal packages.

cabal install hermit-streamfusion

Target program includes RULES and functions needed by plugin.

module Main where

import HERMIT.Optimization.StreamFusion.Vector

...

HERMIT executable can run HERMIT plugins.

hermit Main.hs -opt=HERMIT.Optimization.StreamFusion.Vector +Main

Plugin DSL: Packaging and Using

Or add the relevant flags to a Cabal file.

name:     mypackage
version:  0.0.0.1
synopsis: A package that depends on the vector library.
...

executable MyProgram
    main-is: Main.hs
    build-depends: ...
    ghc-options: -fplugin=HERMIT 
                 -fplugin-opt:HERMIT.Optimization.StreamFusion.Vector:Main:
    ...

 

Who is using HERMIT?

Who is using HERMIT?

Refining LDPC Decoders

Fusing Stream Fusion's concatMap

Coutts (2010) suggests the following transformation.

forall g s. concatMap (\x -> Stream g s) = flatten g (\x -> s)

Not expressible as GHC RULES rewrite!

Practical matter: enabling the rewrite with specific simplification steps.

Plugin: ~150 lines

Application: Simplifying implementation of ADPfusion

Generating Hardware via CCCs

Publications

The HERMIT in the Machine: A Plugin for the Interactive Transformation of GHC Core Language Programs.
A. Farmer, A. Gill, E. Komp, and N. Sculthorpe. In Haskell Symposium, pages 1-12. ACM, 2012.
The HERMIT in the Tree: Mechanizing Program Transformations in the GHC Core Language.
N. Sculthorpe, A. Farmer, and A. Gill. In Proceedings of the 24th Symposium on Implementation and Application of Functional Languages (IFL '12), Oxford, England, 2013.
KURE: A Haskell-Embedded Strategic Programming Language with Custom Closed Universes.
N. Sculthorpe, N. Frisby, and A. Gill. Submitted to the Journal of Functional Programming. 2013.
The HERMIT in the Stream: Fusing Stream Fusion's concatMap.
A. Farmer, C. Höner zu Siederdissen, and A. Gill. Draft.
Optimizing SYB is Easy!.
M. Adams, A. Farmer, and J. Pedro Magalhães. Draft.

 

cabal update
cabal install hermit
hermit Main.hs
(HERMIT requires GHC 7.6)
These slides: http://www.ittc.ku.edu/˜afarmer/hiw-13.html

 

 

Core

data ModGuts  = ModGuts {_ :: [CoreBind], ...}
data CoreBind = NonRec Id CoreExpr
              | Rec [(Id, CoreExpr)]
data CoreExpr = Var Id
              | Lit Literal
              | App CoreExpr CoreExpr
              | Lam Id CoreExpr
              | Let CoreBind CoreExpr
              | Case CoreExpr Id Type [CoreAlt]
              | Cast CoreExpr Coercion
              | Tick (Tickish Id) CoreExpr
              | Type Type
              | Coercion Coercion
type CoreAlt  = (AltCon, [Id], CoreExpr)
data AltCon   = DataAlt DataCon | LitAlt Literal | DEFAULT

Principal KURE Types

data Translate c m a b = Translate { apply :: c -> a -> m b }

-- | A 'Translate' that shares the same source and target type.
type Rewrite c m a = Translate c m a a

The Category Zoo:

instance Functor m           => Functor (Translate c m a)
instance Applicative m       => Applicative (Translate c m a)
instance Alternative m       => Alternative (Translate c m a)
instance Monad m             => Monad (Translate c m a)
instance MonadCatch m        => MonadCatch (Translate c m a)
instance MonadPlus m         => MonadPlus (Translate c m a)
instance Monad m             => Category (Translate c m)
instance MonadCatch m        => CategoryCatch (Translate c m)
instance Monad m             => Arrow (Translate c m)
instance MonadPlus m         => ArrowZero (Translate c m)
instance MonadPlus m         => ArrowPlus (Translate c m)
instance Monad m             => ArrowApply (Translate c m)
instance (Monad m, Monoid b) => Monoid (Translate c m a b)

KURE in HERMIT

-- HERMIT translations all operate over the same context and monad.
type TranslateH a b = Translate Context HermitM a b
type RewriteH   a   = Rewrite Context HermitM a

-- Context: bindings in scope, current ModGuts information
-- HermitM: fresh name supply, expression stash

betaReduce :: RewriteH CoreExpr
betaReduce = do App (Lam v e1) e2 <- idR
                return $ Let (NonRec v e2) e1