ghc/docs/add_to_compiler/howto-add.verb

   1 %************************************************************************
   2 %*                                                                      *
   3 \section{How to add an optimisation pass}
   4 %*                                                                      *
   5 %************************************************************************
   6 \subsection{Summary of the steps required}
   7
   8 Well, with all the preliminaries out of the way, here is all that it
   9 takes to add your optimisation pass to the new glorious Glasgow
  10 Haskell compiler:
  11 \begin{enumerate}
  12 \item
  13 Select the input and output types for your pass; these will very
  14 likely be particular parameterisations of the Core or annotated Core
  15 data types.  There is a small chance you will prefer to work at the
  16 STG-syntax level.  (If these data types are inadequate to this
  17 purpose, {\em please} let us know!)
  18
  19 \item
  20 Depending on exactly how you want your pass to work, set up some
  21 monad-ery, so as to avoid lots of horrible needless plumbing.  The
  22 whole compiler is written in a monadic style, and there are plenty of
  23 examples from which you may steal.  Section~\ref{sec:monadic-style}
  24 gives further details about how you might do this.
  25
  26 \item
  27 Write your optimisation pass, and...
  28
  29 {\em Do} use the existing types in the compiler, e.g., @UniType@,
  30 and the ``approved'' interfaces to them.
  31
  32 {\em Don't} rewrite lots of utility code!  Scattered around in various
  33 sometimes-obvious places, there is considerable code already written
  34 for the mangling and massaging of expressions, types, variables, etc.
  35
  36 Section~\ref{sec:reuse-code} says more about how to re-use existing
  37 compiler bits.
  38
  39 \item
  40 Follow our naming conventions \smiley{} Seriously, it may lead to greater
  41 acceptance of our code and yours if readers find a system written with
  42 at least a veneer of uniformity.
  43 \ToDo{mention Style Guide, if it ever really exists.}
  44
  45 \item
  46 To hook your pass into the compiler, either add something directly to
  47 the @Main@ module of the compiler,\srcloc{main/Main.lhs} or into the
  48 Core-to-Core simplification driver,\srcloc{simplCore/SimplCore.lhs} or
  49 into the STG-to-STG driver.\srcloc{simplStg/SimplStg.lhs}
  50
  51 Also add something to the compilation-system
  52 driver\srcloc{ghc/driver/ghc.lprl}
  53 (called @ghc@ here) so that appropriate user-provided command-line
  54 options will be transmogrified into the correct options fed to the
  55 @Main@ module.
  56
  57 \item
  58 Add some appropriate documentation to the user's guide,
  59 @ghc/docs/users_guide@.
  60
  61 \item
  62 Run your optimisation on {\em real programs}, measure, and improve.
  63 (Separate from this compiler's distribution, we provide a ``NoFib''
  64 suite of ``real Haskell programs'' \cite{partain92a}.  We strongly
  65 encourage their use, so you can more readily compare your work with
  66 others'.)
  67
  68 \item
  69 Send us your contribution so we can add it to the distribution!  We
  70 will be happy to include anything semi-reasonable.
  71 This will practically ensure fame, if
  72 not fortune, and---with a little luck---considerable notoriety.
  73 \end{enumerate}
  74
  75 %************************************************************************
  76 %*                                                                      *
  77 \subsection{Using monadic code}\label{sec:monadic-style}
  78 %*                                                                      *
  79 %************************************************************************
  80
  81 {\em Monads} are one way of structuring functional programs. Phil
  82 Wadler is their champion, and his recent papers on the subject are a
  83 good place to start your investigations.  ``The essence of functional
  84 programming'' even has a section about the use of monads in this
  85 compiler \cite{wadler92a}!  An earlier paper describes ``monad
  86 comprehensions'' \cite{wadler90a}.  For a smaller self-contained
  87 example, see his ``literate typechecker'' \cite{wadler90b}.
  88
  89 We use monads extensively in this compiler, mainly as a way to plumb
  90 state around.  The simplest example is a monad to plumb a
  91 @UniqueSupply@\srcloc{basicTypes/Unique.lhs} (i.e., name supply)
  92 through a function.
  93
  94 \ToDo{Actually describe one monad thing completely.}
  95
  96 We encourage you to use a monadic style, where appropriate, in
  97 the code you add to the compiler.  To this end, here is a list of
  98 monads already in use in the compiler:
  99 \begin{description}
 100 \item[@UniqueSupply@ monad:] \srcloc{basicTypes/Unique.lhs}
 101 To carry a name supply around; do a @getUnique@ when you
 102 need one.  Used in several parts of the compiler.
 103
 104 \item[Typechecker monad:] \srcloc{typecheck/TcMonad.lhs}
 105 Quite a complicated monad; carries around a substitution, some
 106 source-location information, and a @UniqueSupply@; also plumbs
 107 typechecker success/failure back up to the right place.
 108
 109 \item[Desugarer monad:] \srcloc{deSugar/DsMonad.lhs}
 110 Carries around a @UniqueSupply@ and source-location information (to
 111 put in pattern-matching-failure error messages).
 112
 113 \item[Code-generator monad:] \srcloc{codeGen/CgMonad.lhs}
 114 Carries around an environment that maps variables to addressing modes
 115 (e.g., ``in this block, @f@ is at @Node@ offset 3''); also, carries
 116 around stack- and heap-usage information.  Quite tricky plumbing, in
 117 part so that the ``Abstract~C'' output will be produced lazily.
 118
 119 \item[Monad for underlying I/O machinery:] \srcloc{ghc/lib/io/GlaIOMonad.lhs}
 120 This is the basis of our I/O implementation.  See the paper about it
 121 \cite{peyton-jones92b}.
 122 \end{description}
 123
 124 %************************************************************************
 125 %*                                                                      *
 126 \subsection{Adding a new @PrimitiveOp@}\label{sec:add-primop}
 127 %*                                                                      *
 128 %************************************************************************
 129
 130 You may find yourself wanting to add a new
 131 @PrimitiveOp@\srcloc{prelude/PrimOps.lhs} to the compiler's
 132 repertoire: these are the lowest-level operations that cannot be
 133 expressed in Haskell---in our case, things written in C.
 134
 135 What you would need to do to add a new op:
 136 \begin{itemize}
 137 \item
 138 Add it to the @PrimitiveOp@ datatype in @prelude/PrimOps.lhs@; it's
 139 just an enumeration type.
 140 \item
 141 Most importantly, add an entry in the @primOpInfo@ function for your
 142 new primitive.
 143 \item
 144 If you want your primitive to be visible to some other part of the
 145 compiler, export it via the @AbsPrel@\srcloc{prelude/AbsPrel.lhs}
 146 interface (and import it from there).
 147 \item
 148 If you want your primitive to be visible to the user (modulo some
 149 ``show-me-nonstd-names'' compiler flag...), add your primitive to one
 150 or more of the appropriate lists in @buildinNameFuns@, in
 151 @prelude/AbsPrel.lhs@.
 152 \item
 153 If your primitive can be implemented with just a C macro, add it to
 154 @ghc/imports/StgMacros.lh@.  If it needs a C function, put that in
 155 @ghc/runtime/prims/@, somewhere appropriate; you might need to put a
 156 declaration of some kind in a C header file in @ghc/imports/@.
 157 \item
 158 If these steps are not enough, please get in touch.
 159 \end{itemize}
 160
 161 %************************************************************************
 162 %*                                                                      *
 163 \section{How to add a new ``PrimOp'' (primitive operation)}
 164 %*                                                                      *
 165 %************************************************************************
 166
 167 %************************************************************************
 168 %*                                                                      *
 169 \section{How to add a new ``user pragma''}
 170 %*                                                                      *
 171 %************************************************************************
 172
 173 %************************************************************************
 174 %*                                                                      *
 175 \section{GHC utilities and re-usable code}\label{sec:reuse-code}
 176 %*                                                                      *
 177 %************************************************************************
 178
 179 %************************************************************************
 180 %*                                                                      *
 181 \subsection{Reuse existing utilities}
 182 %*                                                                      *
 183 %************************************************************************
 184
 185 Besides the utility functions provided in Haskell's standard prelude,
 186 we have several modules of generally-useful utilities in \mbox{\tt utils/}
 187 (no need to re-invent them!):
 188 \begin{description}
 189 \item[@Maybe@ and @MaybeErr@:]
 190 Two very widely used types (and some operations on them):
 191 \begin{verbatim}
 192 data Maybe    a   = Nothing | Just a
 193 data MaybeErr a b = Succeeded a | Failed b
 194 \end{verbatim}
 195
 196 \item[@Set@:]
 197 A simple implementation of sets (an abstract type).  The things you
 198 want to have @Sets@ of must be in class @Ord@.
 199
 200 \item[@ListSetOps@:]
 201 A module providing operations on lists that have @Set@-sounding names;
 202 e.g., @unionLists@.
 203
 204 \item[@Digraph@:]
 205 A few functions to do with directed graphs, notably finding
 206 strongly-connected components (and cycles).
 207
 208 \item[@Util@:]
 209 General grab-bag of utility functions not provided by the standard
 210 prelude.
 211 \end{description}
 212
 213 Much of the compiler is structured around major datatypes, e.g.,
 214 @UniType@ or @Id@.  These datatypes (often ``abstract''---you can't
 215 see their actual constructors) are packaged with many useful
 216 operations on them.  So, again, look around a little for these
 217 functions before rolling your own.  Section~\ref{sec:reuse-datatypes}
 218 goes into this matter in more detail.
 219
 220 %************************************************************************
 221 %*                                                                      *
 222 \subsection{Use pretty-printing and forcing machinery}
 223 %*                                                                      *
 224 %************************************************************************
 225
 226 All of the non-trivial datatypes in the compiler are in class
 227 @Outputable@, meaning you can pretty-print them (method: @ppr@) or
 228 force them (method: @frc@).
 229
 230 Pretty-printing is by far the more common operation.  @ppr@ takes a
 231 ``style'' as its first argument; it can be one of @PprForUser@,
 232 @PprDebug@, or @PprShowAll@, which---in turn---are intended to show
 233 more and more detail.  For example, @ppr PprForUser@ on a @UniType@
 234 should print a type that would be recognisable to a Haskell user;
 235 @ppr PprDebug@ prints a type in the way an implementer would normally
 236 want to see it (e.g., with all the ``for all...''s), and
 237 @ppr PprShowAll@ prints everything you could ever want to know about that
 238 type.
 239
 240 @ppr@ produces a @Pretty@, which should eventually wend its way to
 241 @main@.  @main@ can then peruse the program's command-line options to
 242 decide on a @PprStyle@ and column width in which to print.  In
 243 particular, it's bad form to @ppShow@ the @Pretty@ into a @String@
 244 deep in the bowels of the compiler, where the user cannot control the
 245 printing.
 246
 247 If you introduce non-trivial datatypes, please make them instances of
 248 class @Outputable@.
 249
 250 %************************************************************************
 251 %*                                                                      *
 252 \subsection{Use existing data types appropriately}\label{sec:reuse-datatypes}
 253 %*                                                                      *
 254 %************************************************************************
 255
 256 The compiler uses many datatypes.  Believe it or not, these have
 257 carefully structured interfaces to the ``outside world''!  Unfortunately,
 258 the current Haskell module system does not let us enforce proper
 259 access to these datatypes to the extent we would prefer.  Here is a
 260 list of datatypes (and their operations) you should feel free to use,
 261 as well as how to access them.
 262
 263 The first major group of datatypes are the ``syntax datatypes,'' the
 264 various ways in which the program text is represented as it makes its
 265 way through the compiler.  These are notable in that you are allowed
 266 to see/make-use-of all of their constructors:
 267 \begin{description}
 268 \item[Prefix form:]\srcloc{reader/PrefixSyn.lhs}  You shouldn't need
 269 this.
 270
 271 \item[Abstract Haskell syntax:]\srcloc{abstractSyn/AbsSyn.lhs}  Access
 272 via the @AbsSyn@ interface.  An example of what you should {\em not}
 273 do is import the @AbsSynFuns@ (or @HsBinds@ or ...) interface
 274 directly.  @AbsSyn@ tells you what you're supposed to see.
 275
 276 \item[Core syntax:]\srcloc{coreSyn/*Core.lhs}  Core syntax is
 277 parameterised, and you should access it {\em via one of the
 278 parameterisations}.  The most common is @PlainCore@; another is
 279 @TaggedCore@.  Don't use @CoreSyn@, though.
 280
 281 \item[STG syntax:]\srcloc{stgSyn/StgSyn.lhs} Access via the @StgSyn@ interface.
 282
 283 \item[Abstract~C syntax:]\srcloc{absCSyn/AbsCSyn.lhs} Access via the
 284 @AbsCSyn@ interface.
 285 \end{description}
 286
 287 The second major group of datatypes are the ``basic entity''
 288 datatypes; these are notable in that you don't need to know their
 289 representation to use them.  Several have already been mentioned:
 290 \begin{description}
 291 \item[UniTypes:]\srcloc{uniType/AbsUniType.lhs} This is a gigantic
 292 interface onto the world of @UniTypes@; accessible via the
 293 @AbsUniType@ interface.  You should import operations on all the {\em
 294 pieces} of @UniTypes@ (@TyVars@, @TyVarTemplates@, @TyCons@,
 295 @Classes@, and @ClassOps@) from here as well---everything for the
 296 ``type world.''
 297
 298 {\em Please don't grab type-related functions from internal modules,
 299 behind @AbsUniType@'s back!}  (Otherwise, we won't discover the
 300 shortcomings of the interface...)
 301
 302 \item[Identifiers:]\srcloc{basicTypes/Id.lhs}  Interface: @Id@.
 303
 304 \item[``Core'' literals:]\srcloc{basicTypes/CoreLit.lhs}  These are
 305 the unboxed literals used in Core syntax onwards.  Interface: @CoreLit@.
 306
 307 \item[Environments:]\srcloc{envs/GenericEnv.lhs}
 308 A generic environment datatype, plus a generally useful set of
 309 operations, is provided via the @GenericEnv@ interface.  We encourage
 310 you to use this, rather than roll your own; then your code will
 311 benefit when we speed up the generic code.  All of the typechecker's
 312 environment stuff (of which there is plenty) is built on @GenericEnv@,
 313 so there are plenty of examples to follow.
 314
 315 \item[@Uniques@:]\srcloc{basicTypes/Unique.lhs} Essentially @Ints@.
 316 When you need something unique for fast comparisons.  Interface:
 317 @Unique@.  This interface also provides a simple @UniqueSupply@ monad;
 318 often just the thing...
 319
 320 \item[Wired-in standard prelude knowledge:]\srcloc{prelude/} The
 321 compiler has to know a lot about the standard prelude.  What it knows
 322 is in the @compiler/prelude@ directory; all the rest of the compiler
 323 gets its prelude knowledge through the @AbsPrel@ interface.
 324
 325 The prelude stuff can get hairy.  There is a separate document about
 326 it.  Check the @ghc/docs/README@ list for a pointer to it...
 327 \end{description}
 328
 329 The above list isn't exhaustive.  By all means, ask if you think
 330 ``Surely a function like {\em this} is in here somewhere...''
 331
 332
 333 %************************************************************************
 334 %*                                                                      *
 335 \section{Cross-module pragmatic info: the mysteries revealed}
 336 %*                                                                      *
 337 %************************************************************************
 338
 339 ToDo: mention wired-in info.
 340
 341 %************************************************************************
 342 %*                                                                      *
 343 \section{GHC hacking tips and ``good practice''}
 344 %*                                                                      *
 345 %************************************************************************
 346
 347 ASSERT
 348
 349 %************************************************************************
 350 %*                                                                      *
 351 \section{Glasgow pragmatics: build trees, etc.}
 352 %*                                                                      *
 353 %************************************************************************