GitLab

Authored-by: David Luposchainsky <dluposchainsky@gmail.com>
Signed-off-by: Austin Seipp <austin@well-typed.com>

I restored part of documentation that describes what is a let-no-escape
and which was deleted 10 months ago together with the old codegen. Then
I removed lots of Literate Haskell clutter (like empty \begin{code} -
\end{code} blocks) and finally decided to remove all the Literate Haskell
markup because there wasn't much of it left, but it made comments so
difficult to read.

Clang doesn't like whitespace between macro and arguments.
Signed-off-by: Austin Seipp <aseipp@pobox.com>

This major patch implements the cardinality analysis described
in our paper "Higher order cardinality analysis". It is joint
work with Ilya Sergey and Dimitrios Vytiniotis.

The basic is augment the absence-analysis part of the demand
analyser so that it can tell when something is used
	 never
	 at most once
 	 some other way

The "at most once" information is used
    a) to enable transformations, and
       in particular to identify one-shot lambdas
    b) to allow updates on thunks to be omitted.

There are two new flags, mainly there so you can do performance
comparisons:
    -fkill-absence   stops GHC doing absence analysis at all
    -fkill-one-shot  stops GHC spotting one-shot lambdas
                     and single-entry thunks

The big changes are:

* The Demand type is substantially refactored.  In particular
  the UseDmd is factored as follows
      data UseDmd
        = UCall Count UseDmd
        | UProd [MaybeUsed]
        | UHead
        | Used

      data MaybeUsed = Abs | Use Count UseDmd

      data Count = One | Many

  Notice that UCall recurses straight to UseDmd, whereas
  UProd goes via MaybeUsed.

  The "Count" embodies the "at most once" or "many" idea.

* The demand analyser itself was refactored a lot

* The previously ad-hoc stuff in the occurrence analyser for foldr and
  build goes away entirely.  Before if we had build (\cn -> ...x... )
  then the "\cn" was hackily made one-shot (by spotting 'build' as
  special.  That's essential to allow x to be inlined.  Now the
  occurrence analyser propagates info gotten from 'build's stricness
  signature (so build isn't special); and that strictness sig is
  in turn derived entirely automatically.  Much nicer!

* The ticky stuff is improved to count single-entry thunks separately.

One shortcoming is that there is no DEBUG way to spot if an
allegedly-single-entry thunk is acually entered more than once.  It
would not be hard to generate a bit of code to check for this, and it
would be reassuring.  But it's fiddly and I have not done it.

Despite all this fuss, the performance numbers are rather under-whelming.
See the paper for more discussion.

       nucleic2          -0.8%    -10.9%      0.10      0.10     +0.0%
         sphere          -0.7%     -1.5%      0.08      0.08     +0.0%
--------------------------------------------------------------------------------
            Min          -4.7%    -10.9%     -9.3%     -9.3%    -50.0%
            Max          -0.4%     +0.5%     +2.2%     +2.3%     +7.4%
 Geometric Mean          -0.8%     -0.2%     -1.3%     -1.3%     -1.8%

I don't quite know how much credence to place in the runtime changes,
but movement seems generally in the right direction.

There's now an internal -dll-split flag, which we use to tell GHC how
the GHC package is split into 2 separate DLLs. This is used by
Packages.isDllName to determine whether a call is within the same
DLL, or whether it is a call to another DLL.

Making Any a type family is the right thing to do, but it messes up
the proxy kind arguments in TypeLits and Singletons, so I'm backing it
out for now.

More thought required!

* Make Any into a type family (which it should always have been)
  This is to support the future introduction of eta rules for
  product types (see email on ghc-users title "PolyKind issue"
  early Sept 2012)

* Add the *internal* data type support for
    (a) closed type families [so that you can't give
        type instance for 'Any']
    (b) injective type families [because Any is really
        injective]
  This amounts to two boolean flags on the SynFamilyTyCon
  constructor of TyCon.SynTyConRhs.

There is some knock-on effect, but all of a routine nature.

It remains to offer source syntax for either closed or
injective families.

When converting from Core to STG, we swith pattern matching on
on a *nullary* unboxed tuple into matching using a PrimAlt on RealWorld#
   case e (RealWorld#) of { DEFAULT -> ... }
This semms messy to me, but it works.  There was a bug in that we were
changing to PrimAlt, but not using a DEFAULT AltCon.

This is done by a 'unarisation' pre-pass at the STG level which
translates away all (live) binders binding something of unboxed
tuple type.

This has the following knock-on effects:
  * The subkind hierarchy is vastly simplified (no UbxTupleKind or ArgKind)
  * Various relaxed type checks in typechecker, 'foreign import prim' etc
  * All case binders may be live at the Core level

This patch allows, for the first time, case expressions with an empty
list of alternatives. Max suggested the idea, and Trac #6067 showed
that it is really quite important.

So I've implemented the idea, fixing #6067. Main changes

 * See Note [Empty case alternatives] in CoreSyn

 * Various foldr1's become foldrs

 * IfaceCase does not record the type of the alternatives.
   I added IfaceECase for empty-alternative cases.

 * Core Lint does not complain about empty cases

 * MkCore.castBottomExpr constructs an empty-alternative case
   expression   (case e of ty {})

 * CoreToStg converts '(case e of {})' to just 'e'

This allows us to import values (i.e. non-functions) with the CAPI.
This means we can access values even if (on some or all platforms)
they are simple #defines.

We only use it for "compiler" sources, i.e. not for libraries.
Many modules have a -fno-warn-tabs kludge for now.

User visible changes
====================

Profilng
--------

Flags renamed (the old ones are still accepted for now):

  OLD            NEW
  ---------      ------------
  -auto-all      -fprof-auto
  -auto          -fprof-exported
  -caf-all       -fprof-cafs

New flags:

  -fprof-auto              Annotates all bindings (not just top-level
                           ones) with SCCs

  -fprof-top               Annotates just top-level bindings with SCCs

  -fprof-exported          Annotates just exported bindings with SCCs

  -fprof-no-count-entries  Do not maintain entry counts when profiling
                           (can make profiled code go faster; useful with
                           heap profiling where entry counts are not used)

Cost-centre stacks have a new semantics, which should in most cases
result in more useful and intuitive profiles.  If you find this not to
be the case, please let me know.  This is the area where I have been
experimenting most, and the current solution is probably not the
final version, however it does address all the outstanding bugs and
seems to be better than GHC 7.2.

Stack traces
------------

+RTS -xc now gives more information.  If the exception originates from
a CAF (as is common, because GHC tends to lift exceptions out to the
top-level), then the RTS walks up the stack and reports the stack in
the enclosing update frame(s).

Result: +RTS -xc is much more useful now - but you still have to
compile for profiling to get it.  I've played around a little with
adding 'head []' to GHC itself, and +RTS -xc does pinpoint the problem
quite accurately.

I plan to add more facilities for stack tracing (e.g. in GHCi) in the
future.

Coverage (HPC)
--------------

 * derived instances are now coloured yellow if they weren't used
 * likewise record field names
 * entry counts are more accurate (hpc --fun-entry-count)
 * tab width is now correct (markup was previously off in source with
   tabs)

Internal changes
================

In Core, the Note constructor has been replaced by

        Tick (Tickish b) (Expr b)

which is used to represent all the kinds of source annotation we
support: profiling SCCs, HPC ticks, and GHCi breakpoints.

Depending on the properties of the Tickish, different transformations
apply to Tick.  See CoreUtils.mkTick for details.

Tickets
=======

This commit closes the following tickets, test cases to follow:

  - Close #2552: not a bug, but the behaviour is now more intuitive
    (test is T2552)

  - Close #680 (test is T680)

  - Close #1531 (test is result001)

  - Close #949 (test is T949)

  - Close #2466: test case has bitrotted (doesn't compile against current
    version of vector-space package)

and comment its invariants in Note [CoreProgram] in CoreSyn

I'm not totally convinced that CoreProgram is the right name
(perhaps CoreTopBinds might better), but it is useful to have
a clue that you are looking at the top-level bindings.

This is only a matter of a type synonym change; no deep
refactoring here.

LitInteger now carries around the id of mkInteger, which it uses
to construct the core to build Integer literals. This way we don't
have to build in info about lots of Ids.

We also no longer have any special-casing for integer-simple, so
there is less code involved.

We now treat them as literals until CorePrep, when we finally
convert them into the real Core representation. This makes it a lot
simpler to implement built-in rules on them.

Fixes Trac #5456, which was a buglet arising from

  commit de9b85fa
  Author: Simon Peyton Jones <simonpj@microsoft.com>
  Date:   Fri Sep 2 17:43:53 2011 +0100

    Export a tiny bit more info with AbstractTyCon (fixes #5424)

It only shows up when compiling with -O0!

These turn out to be a useful special case of splitTyConApp_maybe.

A refactoring only; no change in behaviour

* Fix bugs in the packing and unpacking of data
  constructors with equality predicates in their types

* Remove PredCo altogether; instead, coercions between predicated
  types (like  (Eq a, [a]~b) => blah) are treated as if they
  were precisely their underlying representation type
       Eq a -> ((~) [a] b) -> blah
  in this case

* Similarly, Type.coreView no longer treats equality
  predciates specially.

* Implement the cast-of-coercion optimisation in
  Simplify.simplCoercionF

Numerous other small bug-fixes and refactorings.

Annoyingly, OptCoercion had Windows line endings, and this
patch switches to Unix, so it looks as if every line has changed.

See the paper "Practical aspects of evidence based compilation in System FC"

* Coercion becomes a data type, distinct from Type

* Coercions become value-level things, rather than type-level things,
  (although the value is zero bits wide, like the State token)
  A consequence is that a coerion abstraction increases the arity by 1
  (just like a dictionary abstraction)

* There is a new constructor in CoreExpr, namely Coercion, to inject
  coercions into terms

When this ASSERT tripped in CoreToStg it tried to print out
too much, which tripped the asssertion again.  Result: an
infinite loop with no output at all.  Hard to debug!

The problem arose with this kind of thing

   x = (,) (scc "blah" Nothing)

Then 'x' is marked NoCafRefs by CoreTidy, becuase it has 
arity 1, and doesn't mention any caffy things.

That in turns means that CorePrep must not float out the
sat binding to give

  sat = scc "blah" Nothing
  x = (,) sat

Rather we must generate

  x = \eta. let sat = scc "blah" Nothing 
            in (,) sat eta

URGH! This Caf stuff is such a mess.

This major patch implements the new OutsideIn constraint solving
algorithm in the typecheker, following our JFP paper "Modular type
inference with local assumptions".  

Done with major help from Dimitrios Vytiniotis and Brent Yorgey.

    
   DO NOT MERGE TO GHC 6.12 branch
   (Reason: interface file format change.)

The typechecker needs to instantiate otherwise-unconstraint type variables to
an appropriately-kinded constant type, but we didn't have a supply of 
arbitrarily-kinded tycons for this purpose.  Now we do.

The details are described in Note [Any types] in TysPrim.  The
fundamental change is that there is a new sort of TyCon, namely
AnyTyCon, defined in TyCon.

Ter's a small change to interface-file binary format, because the new
AnyTyCons have to be serialised.

I tided up the handling of uniques a bit too, so that mkUnique is not
exported, so that we can see all the different name spaces in one module.

It adds a third case to StgOp which already hold StgPrimOp and StgFCallOp.
The code generation for the new StgPrimCallOp case is almost exactly the
same as for out-of-line primops. They now share the tailCallPrim function.
In the Core -> STG translation we map foreign calls using the "prim"
calling convention to the StgPrimCallOp case. This is because in Core we
represent prim calls using the ForeignCall stuff. At the STG level however
the prim calls are really much more like primops than foreign calls.

This patch does two main things

a) Rewrite most of CorePrep to be much easier to understand (I hope!).
   The invariants established by CorePrep are now written out, and
   the code is more perspicuous.  It is surpringly hard to get right,
   and the old code had become quite incomprehensible.

b) Rewrite the eta-expander so that it does a bit of simplifying
   on-the-fly, and thereby guarantees to maintain the CorePrep
   invariants.  This make it much easier to use from CorePrep, and
   is a generally good thing anyway.

A couple of pieces of re-structuring:

*  I moved the eta-expander and arity analysis stuff into a new
   module coreSyn/CoreArity.

   Max will find that the type CoreArity.EtaInfo looks strangely 
   familiar.

*  I moved a bunch of comments from Simplify to OccurAnal; that's
   why it looks as though there's a lot of lines changed in those
   modules.

On the way I fixed various things

  - Function arguments are eta expanded
       f (map g)  ===>  let s = \x. map g x in f s

  - Trac #2368

The result is a modest performance gain, I think mainly due
to the first of these changes:

--------------------------------------------------------------------------------
        Program           Size    Allocs   Runtime   Elapsed
--------------------------------------------------------------------------------
            Min          -1.0%    -17.4%    -19.1%    -46.4%
            Max          +0.3%     +0.5%     +5.4%    +53.8%
 Geometric Mean          -0.1%     -0.3%     -7.0%    -10.2%

This biggish patch addresses Trac #2670.  The main effect is to make
record selectors into ordinary functions, whose unfoldings appear in
interface files, in contrast to their previous existence as magic
"implicit Ids".  This means that the usual machinery of optimisation,
analysis, and inlining applies to them, which was failing before when
the selector was somewhat complicated.  (Which it can be when
strictness annotations, unboxing annotations, and GADTs are involved.)

The change involves the following points

* Changes in Var.lhs to the representation of Var.  Now a LocalId can
  have an IdDetails as well as a GlobalId.  In particular, the
  information that an Id is a record selector is kept in the
  IdDetails.  While compiling the current module, the record selector
  *must* be a LocalId, so that it participates properly in compilation
  (free variables etc).

  This led me to change the (hidden) representation of Var, so that there
  is now only one constructor for Id, not two.

* The IdDetails is persisted into interface files, so that an
  importing module can see which Ids are records selectors.

* In TcTyClDecls, we generate the record-selector bindings in renamed,
  but not typechecked form.  In this way, we can get the typechecker
  to add all the types and so on, which is jolly helpful especially
  when GADTs or type families are involved.  Just like derived
  instance declarations.

  This is the big new chunk of 180 lines of code (much of which is
  commentary).  A call to the same function, mkAuxBinds, is needed in
  TcInstDcls for associated types.

* The typechecker therefore has to pin the correct IdDetails on to 
  the record selector, when it typechecks it.  There was a neat way
  to do this, by adding a new sort of signature to HsBinds.Sig, namely
  IdSig.  This contains an Id (with the correct Name, Type, and IdDetails);
  the type checker uses it as the binder for the final binding.  This
  worked out rather easily.

* Record selectors are no longer "implicit ids", which entails changes to
     IfaceSyn.ifaceDeclSubBndrs
     HscTypes.implicitTyThings
     TidyPgm.getImplicitBinds
  (These three functions must agree.)

* MkId.mkRecordSelectorId is deleted entirely, some 300+ lines (incl
  comments) of very error prone code.  Happy days.

* A TyCon no longer contains the list of record selectors: 
  algTcSelIds is gone

The renamer is unaffected, including the way that import and export of
record selectors is handled.

Other small things

* IfaceSyn.ifaceDeclSubBndrs had a fragile test for whether a data
  constructor had a wrapper.  I've replaced that with an explicit flag
  in the interface file. More robust I hope.

* I renamed isIdVar to isId, which touched a few otherwise-unrelated files.

The exported arity of a function must match the arity for the
STG function.  Trac #2844 was a pretty obscure manifestation of
the failure of this invariant. This patch doesn't cure the bug;
rather it adds an assertion to CoreToStg to check the invariant
so we should get an earlier and less obscure warning if this
fails in future.