GitLab

Implements Trac #4299.  Documentation to come.

We still have
    insertList, insertListWith, deleteList
which aren't in Data.Map, and
    foldRightWithKey
which works around the fold(r)WithKey addition and deprecation.

and adjust imports accordingly

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.

The problem was that a strict binding was getting floated
out into a letrec. This only happened when profiling was
on.  It exposed a fragility in the floating strategy.  This
patch makes it more robust.  See
      Note [Avoiding unnecessary floating]

This bug just led to stupid code, which would
later be optimised away, but better not to generate
stupid code in the first place.

See Note [DFun unfoldings] in CoreSyn.  The issue here is that 
you can't tell how many dictionary arguments a DFun needs just
from looking at the Arity of the DFun Id: if the dictionary is
represented by a newtype the arity might include the dictionary
and value arguments of the (single) method.

So we need to record the number of arguments need by the DFun
in the DFunUnfolding itself.  Details in 
   Note [DFun unfoldings] in CoreSyn

This is a long-standing lurking bug. See Note [Lamba-bound unfoldings]
in DmdAnal.

I'm still not really happy with this lambda-bound-unfolding stuff.

preInlineUnconditionally was, in effect, nuking an INLINE pragma, with
very bad effect on runtime in this program.  Fortunately the fix is
very simple.

See Note [InlineRule and preInlineUnconditionally] in SimplUtils.

The simplifier is taking more iterations than it should, because we
were fruitlessly ANF-ing a top-level declaration of form

   x = Ptr "foo"#

to get
 
   x = let v = "foo"# in Ptr v

and then inlining v again.  This patch makes Simplify.makeTrivial 
top-level aware, so that it doesn't ANF if it's going to be undone.

See the long Note [INLINE and default methods].  

This patch changes a couple of data types, with a knock-on effect on
the format of interface files.  A lot of files get touched, but is a
relatively minor change.  The main tiresome bit is the extra plumbing
to communicate default methods between the type checker and the
desugarer.

This patch mainly concerns the plumbing for running
the passes and printing intermediate output

* I was debugging so I added some call-site info
  (that touches a lot of code)

* I used substExpr a bit less in Simplify, hoping to
  make the simplifier a little faster and cleaner

The main purpose of this patch is to add a bunch of new rules
to the coercion optimiser.  They are documented in the (revised)
Appendix of the System FC paper.  

Some code has moved about:

- OptCoercion is now a separate module, mainly because it
  now uses tcMatchTy, which is defined in Unify, so OptCoercion
  must live higehr up in the hierarchy

- Functions that manipulate Kinds has moved from 
  Type.lhs to Coercion.lhs.  Reason: the function typeKind
  now needs to call coercionKind.  And in any case, a Kind is
  a flavour of Type, so it builds on top of Type; indeed Coercions
  and Kinds are both flavours of Type.

  This change required fiddling with a number of imports, hence
  the one-line changes to otherwise-unrelated modules

- The representation of CoTyCons in TyCon has changed.   Instead of
  an extensional representation (a kind checker) there is now an
  intensional representation (namely TyCon.CoTyConDesc).  This was
  needed for one of the new coercion optimisations.

This patch moves a lot of code around, but has zero functionality change.
The idea is that the types

    CoreToDo
    SimplifierSwitch	
    SimplifierMode
    FloatOutSwitches

and 

    the main core-to-core pipeline construction

belong in simplCore/, and *not* in DynFlags.

By default, these two now print *one line* per inlining or rule-firing.

If you want the previous (voluminous) behaviour, use -dverbose-core2core.

This patch does two main things:

1. Adjusts the way we set the Activation for

   a) The wrappers generated by the strictness analyser
      See Note [Wrapper activation] in WorkWrap

   b) The RULEs generated by Specialise and SpecConstr
      See Note [Auto-specialisation and RULES] in Specialise
          Note [Transfer activation] in SpecConstr

2. Refines how we set the phase when simplifying the right
   hand side of an InlineRule.  See
   Note [Simplifying inside InlineRules] in SimplUtils.

Most of the extra lines are comments!  

The merit of (2) is that a bit more stuff happens inside InlineRules,
and that in turn allows better dead-code elimination.

* Fix a bug that meant that 
     (right (inst (forall tv.co) ty)) 
  wasn't getting optimised.  This showed up in the
  compiled code for ByteCodeItbls

* Add a substitution to optCoercion, so that it simultaneously
  substitutes and optimises.  Both call sites wanted this, and
  optCoercion itself can use it, so it seems a win all round.

In CSE we were getting lots of apprarently-unequal expressions with
the same hash code.  In fact they were perfectly equal -- but we were
using a cheap-and-cheerful equality tests for CoreExpr that said False
for any lambda expression!

This patch adds a proper equality test for Core, with alpha-renaming.
It's easy to do, and will avoid silly cases of CSE failing to fire.

We should get less of this:
  WARNING: file compiler/simplCore/CSE.lhs line 326
  extendCSEnv: long list, length 18
from a compiler built with -DDEBUG

  
The idea is to float out bottoming expressions to top level,
abstracting them over any variables they mention, if necessary.  This
is good because it makes functions smaller (and more likely to
inline), by keeping error code out of line. 

See Note [Bottoming floats] in SetLevels.

On the way, this fixes the HPC failures for cg059 and friends.

I've been meaning to do this for some time.  See Maessen's paper 1999
"Bottom extraction: factoring error handling out of functional
programs" (unpublished I think).

Here are the nofib results:


        Program           Size    Allocs   Runtime   Elapsed
--------------------------------------------------------------------------------
            Min          +0.1%     -7.8%    -14.4%    -32.5%
            Max          +0.5%     +0.2%     +1.6%    +13.8%
 Geometric Mean          +0.4%     -0.2%     -4.9%     -6.7%

Module sizes
        -1 s.d.                -----           -2.6%
        +1 s.d.                -----           +2.3%
        Average                -----           -0.2%

Compile times:
        -1 s.d.                -----          -11.4%
        +1 s.d.                -----           +4.3%
        Average                -----           -3.8%

I'm think program sizes have crept up because the base library
is bigger -- module sizes in nofib decrease very slightly.  In turn
I think that may be because the floating generates a call where
there was no call before.  Anyway I think it's acceptable.


The main changes are:

* SetLevels floats out things that exprBotStrictness_maybe 
  identifies as bottom.  Make sure to pin on the right 
  strictness info to the newly created Ids, so that the
  info ends up in interface files.

  Since FloatOut is run twice, we have to be careful that we
  don't treat the function created by the first float-out as
  a candidate for the second; this is what worthFloating does.

  See SetLevels Note [Bottoming floats]
                Note [Bottoming floats: eta expansion]

* Be careful not to inline top-level bottoming functions; this 
  would just undo what the floating transformation achieves.
  See CoreUnfold Note [Do not inline top-level bottoming functions
 
  Ensuring this requires a bit of extra plumbing, but nothing drastic..

* Similarly pre/postInlineUnconditionally should be 
  careful not to re-inline top-level bottoming things!
  See SimplUtils Note [Top-level botomming Ids]
                 Note [Top level and postInlineUnconditionally]

This mades -ddump-simpl-stats print out per-rule and per-id
information by default, rather than requiring -dppr-debug.
On the whole that is what you want.  The -dppr-debug flag
now just controls printing of the log.

Inspired by Trac #3703