Ported various rules for numeric types from GHC.Base. Added new rules
for bitwise operations, shifts and word comparisons.

Simon Peyton Jones authored May 27, 2012 and chak@cse.unsw.edu.au. committed Jun 27, 2012

Silent superclass parameters solve the problem that
the superclasses of a dicionary construction can easily
turn out to be (wrongly) bottom.  The problem and solution
are described in
   Note [Silent superclass arguments] in TcInstDcls

I first implemented this fix (with Dimitrios) in Dec 2010, but removed
it again in Jun 2011 becuase we thought it wasn't necessary any
more. (The reason we thought it wasn't necessary is that we'd stopped
generating derived superclass constraints for *wanteds*.  But we were
wrong; that didn't solve the superclass-loop problem.)

So we have to re-implement it.  It's not hard.  Main features:

  * The IdDetails for a DFunId says how many silent arguments it has

  * A DFunUnfolding describes which dictionary args are
    just parameters (DFunLamArg) and which are a function to apply
    to the parameters (DFunPolyArg).  This adds the DFunArg type
    to CoreSyn

  * Consequential changes to IfaceSyn.  (Binary hi file format changes
    slightly.)

  * TcInstDcls changes to generate the right dfuns

  * CoreSubst.exprIsConApp_maybe handles the new DFunUnfolding

The thing taht is *not* done yet is to alter the vectoriser to
pass the relevant extra argument when building a PA dictionary.

This will let us get at the types of the Id, which in particular means
that for a rule for
    intToInteger :: Int# -> Integer
we can get the "Integer" type, which we can use to build an Integer
literal.

Also add notes about unsafeCoerce

The general thread here is to reduce use of ArgKind after
the type checker; it is so fragile!

This patch should have no user-visible effect.  It implements a
significant internal refactoring of the way that FC axioms are
handled.  The ultimate goal is to put us in a position to implement
"pattern-matching axioms".  But the changes here are only does
refactoring; there is no change in functionality.

Specifically:

 * We now treat data/type family instance declarations very,
   very similarly to types class instance declarations:

   - Renamed InstEnv.Instance as InstEnv.ClsInst, for symmetry with
     FamInstEnv.FamInst.  This change does affect the GHC API, but
     for the better I think.

   - Previously, each family type/data instance declaration gave rise
     to a *TyCon*; typechecking a type/data instance decl produced
     that TyCon.  Now, each type/data instance gives rise to
     a *FamInst*, by direct analogy with each class instance
     declaration giving rise to a ClsInst.

   - Just as each ClsInst contains its evidence, a DFunId, so each FamInst
     contains its evidence, a CoAxiom.  See Note [FamInsts and CoAxioms]
     in FamInstEnv.  The CoAxiom is a System-FC thing, and can relate any
     two types, whereas the FamInst relates directly to the Haskell source
     language construct, and always has a function (F tys) on the LHS.

   - Just as a DFunId has its own declaration in an interface file, so now
     do CoAxioms (see IfaceSyn.IfaceAxiom).

   These changes give rise to almost all the refactoring.

 * We used to have a hack whereby a type family instance produced a dummy
   type synonym, thus
      type instance F Int = Bool -> Bool
   translated to
      axiom FInt :: F Int ~ R:FInt
      type R:FInt = Bool -> Bool
   This was always a hack, and now it's gone.  Instead the type instance
   declaration produces a FamInst, whose axiom has kind
      axiom FInt :: F Int ~ Bool -> Bool
   just as you'd expect.

 * Newtypes are done just as before; they generate a CoAxiom. These
   CoAxioms are "implicit" (do not generate an IfaceAxiom declaration),
   unlike the ones coming from family instance declarations.  See
   Note [Implicit axioms] in TyCon

On the whole the code gets significantly nicer.  There were consequential
tidy-ups in the vectoriser, but I think I got them right.

This big patch implements a kind-polymorphic core for GHC. The current
implementation focuses on making sure that all kind-monomorphic programs still
work in the new core; it is not yet guaranteed that kind-polymorphic programs
(using the new -XPolyKinds flag) will work.

For more information, see http://haskell.org/haskellwiki/GHC/Kinds

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)

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.

It's a hack becuase we have no good reason to be sure that
these functions don't have any CAFs.  We're working on
something better, but this should fix the build (Trac #5485)

In particular, use mkConApp when building the (S# i)
constructors in CorePrep

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.

Basically as documented in http://hackage.haskell.org/trac/ghc/wiki/KindFact,
this patch adds a new kind Constraint such that:

  Show :: * -> Constraint
  (?x::Int) :: Constraint
  (Int ~ a) :: Constraint

And you can write *any* type with kind Constraint to the left of (=>):
even if that type is a type synonym, type variable, indexed type or so on.

The following (somewhat related) changes are also made:
 1. We now box equality evidence. This is required because we want
    to give (Int ~ a) the *lifted* kind Constraint
 2. For similar reasons, implicit parameters can now only be of
    a lifted kind. (?x::Int#) => ty is now ruled out
 3. Implicit parameter constraints are now allowed in superclasses
    and instance contexts (this just falls out as OK with the new
    constraint solver)

Internally the following major changes were made:
 1. There is now no PredTy in the Type data type. Instead
    GHC checks the kind of a type to figure out if it is a predicate
 2. There is now no AClass TyThing: we represent classes as TyThings
    just as a ATyCon (classes had TyCons anyway)
 3. What used to be (~) is now pretty-printed as (~#). The box
    constructor EqBox :: (a ~# b) -> (a ~ b)
 4. The type LCoercion is used internally in the constraint solver
    and type checker to represent coercions with free variables
    of type (a ~ b) rather than (a ~# b)

A coercion variable in a term must be wrapped in a coercion!
(Led to lint errors.)

Hurrah.  At last we can write

   class (F a ~ b) => C a b where { ... }

This fruit of the fact that equalities are now values,
and all evidence is handled uniformly.

The main tricky point is that when translating to Core
an evidence variable 'v' is represented either as
  either   Var v
  or       Coercion (CoVar v)
depending on whether or not v is an equality.  This leads
to a few annoying calls to 'varToCoreExpr'.

We introduced silent superclass parameters as a way to avoid
superclass loops, but we now solve that problem a different
way ("derived" superclass constraints carry no evidence). So
they aren't needed any more.

Apart from being a needless complication, they broke DoCon.
Admittedly in a very obscure way, but still the result is
hard to explain. To see the details see Trac #5051, with
test case typecheck/should_compile/T5051.  (The test is
nice and small!)

* 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

This patch changes things so that such classes rely on the coercion
mechanism for inlining (since the constructor is really just a cast)
rather than on the dfun mechanism, therby removing some needless
runtime indirections.

This clears up an awkward hack for exprIsConApp_maybe, and
works better too.  See Note [Single-method classes] in
TcInstDcls.

This patch finally deals with the super-delicate question of
superclases in possibly-recursive dictionaries.  The key idea
is the DFun Superclass Invariant (see TcInstDcls):

     In the body of a DFun, every superclass argument to the
     returned dictionary is
       either   * one of the arguments of the DFun,
       or       * constant, bound at top level

To establish the invariant, we add new "silent" superclass
argument(s) to each dfun, so that the dfun does not do superclass
selection internally.  There's a bit of hoo-ha to make sure that
we don't print those silent arguments in error messages; a knock
on effect was a change in interface-file format.

A second change is that instead of the complex and fragile
"self dictionary binding" in TcInstDcls and TcClassDcl,
using the same mechanism for existential pattern bindings.
See Note [Subtle interaction of recursion and overlap] in TcInstDcls
and Note [Binding when looking up instances] in InstEnv.

Main notes are here:

  * Note [Silent Superclass Arguments] in TcInstDcls,
    including the DFun Superclass Invariant

Main code changes are:

  * The code for MkId.mkDictFunId and mkDictFunTy

  * DFunUnfoldings get a little more complicated;
    their arguments are a new type DFunArg (in CoreSyn)

  * No "self" argument in tcInstanceMethod
  * No special tcSimplifySuperClasss
  * No "dependents" argument to EvDFunApp

IMPORTANT
   It turns out that it's quite tricky to generate the right
   DFunUnfolding for a specialised dfun, when you use SPECIALISE
   INSTANCE.  For now I've just commented it out (in DsBinds) but
   that'll lose some optimisation, and I need to get back to
   this.

Principally, the SimplifierMode now carries several (currently
four) flags in *all* phases, not just the "Gentle" phase.
This makes things simpler and more uniform.

As usual I did more refactoring than I had intended.

This stuff should go into 7.0.2 in due course, once
we've checked it solves the DPH performance problems.

Implements Trac #4299.  Documentation to come.

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 change involves a little refactoring, so that the default
method Ids are brought into scope earlier, before the value
declarations are compiled.  (Since a value decl may contain
an instance decl in a quote.)

See Note [Default method Ids and Template Haskell] in
TcTyClsDcls.

Warning about useless UNPACK pragmas wasn't as easy as I thought.
I did quite a bit of refactoring, which improved the code by refining
the types somewhat.  In particular notice that in DataCon, we have

    dcStrictMarks   :: [HsBang]
    dcRepStrictness :: [StrictnessMarks]

The former relates to the *source-code* annotation, the latter to
GHC's representation choice.

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.

The main idea is that I'm now treating a single-method dictionary very
much like a multi-method dictionary.  In particular, it respond to
exprIsConApp_maybe, even though newtypes aren't *really* proper
constructors.

See long comments with Note [Single-method classes] for why
this slight hack is justified.

This patch collects a small raft of related changes

* Arrange that during 
     (a) rule matching and 
     (b) uses of exprIsConApp_maybe
  we "look through" unfoldings only if they are active
  in the phase. Doing this for (a) required a bit of 
  extra plumbing in the rule matching code, but I think
  it's worth it.

  One wrinkle is that even if inlining is off (in the 'gentle'
  phase of simplification) during rule matching we want to
  "look through" things with inlinings.  
   See SimplUtils.activeUnfInRule.

  This fixes a long-standing bug, where things that were
  supposed to be (say) NOINLINE, could still be poked into
  via exprIsConApp_maybe. 

* In the above cases, also check for (non-rule) loop breakers; 
  we never look through these.  This fixes a bug that could make
  the simplifier diverge (and did for Roman).  
  Test = simplCore/should_compile/dfun-loop

* Try harder not to choose a DFun as a loop breaker. This is 
  just a small adjustment in the OccurAnal scoring function

* In the scoring function in OccurAnal, look at the InlineRule
  unfolding (if there is one) not the actual RHS, beause the
  former is what'll be inlined.  

* Make the application of any function to dictionary arguments
  CONLIKE.  Thus (f d1 d2) is CONLIKE.  
  Encapsulated in CoreUtils.isExpandableApp
  Reason: see Note [Expandable overloadings] in CoreUtils

* Make case expressions seem slightly smaller in CoreUnfold.
  This reverses an unexpected consequences of charging for
  alternatives.

Refactorings
~~~~~~~~~~~~
* Signficantly refactor the data type for Unfolding (again). 
  The result is much nicer.  

* Add type synonym BasicTypes.CompilerPhase = Int
  and use it

Many of the files touched by this patch are simply knock-on
consequences of these two refactorings.

I finally got tired of the #ifdef OLD_STRICTNESS stuff.  I had been
keeping it around in the hope of doing old-to-new comparisions, but
have failed to do so for many years, so I don't think it's going to
happen.  This patch deletes the clutter.

I'd forgotten the case of single-method classes! I've also improved
the documentation. See
  Note [ClassOp/DFun selection]
  Note [Single-method classes]
both in TcInstDcls