GitLab

This bug is the cause of Trac #1092.  The fix is easy
by making the RnEnv2 implementation do the right thing.
See Note [rnBndrLR] in VarEnv.

Test case is simplCore/should_compile/rule1

This patch is a start on removing import lists and generally tidying
up the top of each module.  In addition to removing import lists:

   - Change DATA.IOREF -> Data.IORef etc.
   - Change List -> Data.List etc.
   - Remove $Id$
   - Update copyrights
   - Re-order imports to put non-GHC imports last
   - Remove some unused and duplicate imports

Fri Aug  4 15:11:01 EDT 2006  Manuel M T Chakravarty <chak@cse.unsw.edu.au>
  * Massive patch for the first months work adding System FC to GHC #1
  Broken up massive patch -=chak
  Original log message:  
  This is (sadly) all done in one patch to avoid Darcs bugs.
  It's not complete work... more FC stuff to come.  A compiler
  using just this patch will fail dismally.

Consider this example (provided by Roman)

	foo :: Int -> Maybe Int -> Int
	foo 0 (Just n) = n
	foo m (Just n) = foo (m-n) (Just n)

SpecConstr sees this fragment:

	case w_smT of wild_Xf [Just A] {
	  Data.Maybe.Nothing -> lvl_smf;
	  Data.Maybe.Just n_acT [Just S(L)] ->
	    case n_acT of wild1_ams [Just A] { GHC.Base.I# y_amr [Just L] ->
	    $wfoo_smW (GHC.Prim.-# ds_Xmb y_amr) wild_Xf
	    }};

and correctly generates the rule

	RULES: "SC:$wfoo1" [0] __forall {y_amr [Just L] :: GHC.Prim.Int#
					  sc_snn :: GHC.Prim.Int#}
	  $wfoo_smW sc_snn (Data.Maybe.Just @ GHC.Base.Int (GHC.Base.I# y_amr))
	  = $s$wfoo_sno y_amr sc_snn ;]

BUT we must ensure that this rule matches in the original function!
Note that the call to $wfoo is
	    $wfoo_smW (GHC.Prim.-# ds_Xmb y_amr) wild_Xf

During matching we expand wild_Xf to (Just n_acT).  But then we must also
expand n_acT to (I# y_amr).  And we can only do that if we look up n_acT
in the in-scope set, because in wild_Xf's unfolding it won't have an unfolding
at all. 

Happily, fixing the bug is easy: add a call to 'lookupRnInScope' in the 
(Var v2) case of 'match'.

Consider a RULE like
	forall arr. splitD (joinD arr) = arr

Until now, this rule would not match code of form
	splitD (let { d = ... } in joinD (...d...))
because the 'let' got in the way.

This patch makes the rule-matcher robust to lets.  See comments with
the Let case of Rules.match.

This improvement is highly desirable in the fusion rules for NDP
stuff that Roman is working on, where we are doing fusion of *overloaded*
functions (which may look lazy).  The let expression that Roman tripped
up on was a dictioary binding.

Most of the other users of the fptools build system have migrated to
Cabal, and with the move to darcs we can now flatten the source tree
without losing history, so here goes.

The main change is that the ghc/ subdir is gone, and most of what it
contained is now at the top level.  The build system now makes no
pretense at being multi-project, it is just the GHC build system.

No doubt this will break many things, and there will be a period of
instability while we fix the dependencies.  A straightforward build
should work, but I haven't yet fixed binary/source distributions.
Changes to the Building Guide will follow, too.

This very large commit adds impredicativity to GHC, plus
numerous other small things.
  
*** WARNING: I have compiled all the libraries, and
***	     a stage-2 compiler, and everything seems
***	     fine.  But don't grab this patch if you 
***	     can't tolerate a hiccup if something is
***	     broken.
  
The big picture is this:

a) GHC handles impredicative polymorphism, as described in the
   "Boxy types: type inference for higher-rank types and
   impredicativity" paper

b) GHC handles GADTs in the new simplified (and very sligtly less
   epxrssive) way described in the
   "Simple unification-based type inference for GADTs" paper

  
But there are lots of smaller changes, and since it was pre-Darcs
they are not individually recorded.
  
Some things to watch out for:
  
c)   The story on lexically-scoped type variables has changed, as per
     my email.  I append the story below for completeness, but I 
     am still not happy with it, and it may change again.  In particular,
     the new story does not allow a pattern-bound scoped type variable
     to be wobbly, so (\(x::[a]) -> ...) is usually rejected.  This is
     more restrictive than before, and we might loosen up again.
  
d)   A consequence of adding impredicativity is that GHC is a bit less
     gung ho about converting automatically between
  	(ty1 -> forall a. ty2)    and    (forall a. ty1 -> ty2)
     In particular, you may need to eta-expand some functions to make
     typechecking work again.
   
     Furthermore, functions are now invariant in their argument types,
     rather than being contravariant.  Again, the main consequence is
     that you may occasionally need to eta-expand function arguments when
     using higher-rank polymorphism.
  

Please test, and let me know of any hiccups


Scoped type variables in GHC
~~~~~~~~~~~~~~~~~~~~~~~~~~~~
	January 2006

0) Terminology.
   
   A *pattern binding* is of the form
	pat = rhs

   A *function binding* is of the form
	f pat1 .. patn = rhs

   A binding of the formm
	var = rhs
   is treated as a (degenerate) *function binding*.


   A *declaration type signature* is a separate type signature for a
   let-bound or where-bound variable:
	f :: Int -> Int

   A *pattern type signature* is a signature in a pattern: 
	\(x::a) -> x
	f (x::a) = x

   A *result type signature* is a signature on the result of a
   function definition:
	f :: forall a. [a] -> a
	head (x:xs) :: a = x

   The form
	x :: a = rhs
   is treated as a (degnerate) function binding with a result
   type signature, not as a pattern binding.

1) The main invariants:

     A) A lexically-scoped type variable always names a (rigid)
 	type variable (not an arbitrary type).  THIS IS A CHANGE.
        Previously, a scoped type variable named an arbitrary *type*.

     B) A type signature always describes a rigid type (since
	its free (scoped) type variables name rigid type variables).
	This is also a change, a consequence of (A).

     C) Distinct lexically-scoped type variables name distinct
	rigid type variables.  This choice is open; 

2) Scoping

2(a) If a declaration type signature has an explicit forall, those type
   variables are brought into scope in the right hand side of the 
   corresponding binding (plus, for function bindings, the patterns on
   the LHS).  
	f :: forall a. a -> [a]
	f (x::a) = [x :: a, x]
   Both occurences of 'a' in the second line are bound by 
   the 'forall a' in the first line

   A declaration type signature *without* an explicit top-level forall
   is implicitly quantified over all the type variables that are
   mentioned in the type but not already in scope.  GHC's current
   rule is that this implicit quantification does *not* bring into scope
   any new scoped type variables.
	f :: a -> a
	f x = ...('a' is not in scope here)...
   This gives compatibility with Haskell 98

2(b) A pattern type signature implicitly brings into scope any type
   variables mentioned in the type that are not already into scope.
   These are called *pattern-bound type variables*.
	g :: a -> a -> [a]
	g (x::a) (y::a) = [y :: a, x]
   The pattern type signature (x::a) brings 'a' into scope.
   The 'a' in the pattern (y::a) is bound, as is the occurrence on 
   the RHS.  

   A pattern type siganture is the only way you can bring existentials 
   into scope.
	data T where
	  MkT :: forall a. a -> (a->Int) -> T

	f x = case x of
		MkT (x::a) f -> f (x::a)

2a) QUESTION
	class C a where
	  op :: forall b. b->a->a

	instance C (T p q) where
	  op = <rhs>
    Clearly p,q are in scope in <rhs>, but is 'b'?  Not at the moment.
    Nor can you add a type signature for op in the instance decl.
    You'd have to say this:
	instance C (T p q) where
	  op = let op' :: forall b. ...
	           op' = <rhs>
	       in op'

3) A pattern-bound type variable is allowed only if the pattern's
   expected type is rigid.  Otherwise we don't know exactly *which*
   skolem the scoped type variable should be bound to, and that means
   we can't do GADT refinement.  This is invariant (A), and it is a 
   big change from the current situation.

	f (x::a) = x	-- NO; pattern type is wobbly
	
	g1 :: b -> b
	g1 (x::b) = x	-- YES, because the pattern type is rigid

	g2 :: b -> b
	g2 (x::c) = x	-- YES, same reason

	h :: forall b. b -> b
	h (x::b) = x	-- YES, but the inner b is bound

	k :: forall b. b -> b
	k (x::c) = x	-- NO, it can't be both b and c

3a) You cannot give different names for the same type variable in the same scope
    (Invariant (C)):

	f1 :: p -> p -> p		-- NO; because 'a' and 'b' would be
	f1 (x::a) (y::b) = (x::a)	--     bound to the same type variable

	f2 :: p -> p -> p		-- OK; 'a' is bound to the type variable
	f2 (x::a) (y::a) = (x::a)	--     over which f2 is quantified
					-- NB: 'p' is not lexically scoped

	f3 :: forall p. p -> p -> p	-- NO: 'p' is now scoped, and is bound to
	f3 (x::a) (y::a) = (x::a)	--     to the same type varialble as 'a'

	f4 :: forall p. p -> p -> p	-- OK: 'p' is now scoped, and its occurences
	f4 (x::p) (y::p) = (x::p)	--     in the patterns are bound by the forall


3b) You can give a different name to the same type variable in different
    disjoint scopes, just as you can (if you want) give diferent names to 
    the same value parameter

	g :: a -> Bool -> Maybe a
	g (x::p) True  = Just x  :: Maybe p
	g (y::q) False = Nothing :: Maybe q

3c) Scoped type variables respect alpha renaming. For example, 
    function f2 from (3a) above could also be written:
	f2' :: p -> p -> p
	f2' (x::b) (y::b) = x::b
   where the scoped type variable is called 'b' instead of 'a'.


4) Result type signatures obey the same rules as pattern types signatures.
   In particular, they can bind a type variable only if the result type is rigid

	f x :: a = x	-- NO

	g :: b -> b
	g x :: b = x	-- YES; binds b in rhs

5) A *pattern type signature* in a *pattern binding* cannot bind a 
   scoped type variable

	(x::a, y) = ...		-- Legal only if 'a' is already in scope

   Reason: in type checking, the "expected type" of the LHS pattern is
   always wobbly, so we can't bind a rigid type variable.  (The exception
   would be for an existential type variable, but existentials are not
   allowed in pattern bindings either.)
 
   Even this is illegal
	f :: forall a. a -> a
	f x = let ((y::b)::a, z) = ... 
	      in 
   Here it looks as if 'b' might get a rigid binding; but you can't bind
   it to the same skolem as a.

6) Explicitly-forall'd type variables in the *declaration type signature(s)*
   for a *pattern binding* do not scope AT ALL.

	x :: forall a. a->a	  -- NO; the forall a does 
	Just (x::a->a) = Just id  --     not scope at all

	y :: forall a. a->a
	Just y = Just (id :: a->a)  -- NO; same reason

   THIS IS A CHANGE, but one I bet that very few people will notice.
   Here's why:

	strange :: forall b. (b->b,b->b)
	strange = (id,id)

	x1 :: forall a. a->a
	y1 :: forall b. b->b
	(x1,y1) = strange

    This is legal Haskell 98 (modulo the forall). If both 'a' and 'b'
    both scoped over the RHS, they'd get unified and so cannot stand
    for distinct type variables. One could *imagine* allowing this:
   
	x2 :: forall a. a->a
	y2 :: forall a. a->a
	(x2,y2) = strange

    using the very same type variable 'a' in both signatures, so that
    a single 'a' scopes over the RHS.  That seems defensible, but odd,
    because though there are two type signatures, they introduce just
    *one* scoped type variable, a.

7) Possible extension.  We might consider allowing
	\(x :: [ _ ]) -> <expr>
    where "_" is a wild card, to mean "x has type list of something", without
    naming the something.

Flags cleanup.

Basically the purpose of this commit is to move more of the compiler's
global state into DynFlags, which is moving in the direction we need
to go for the GHC API which can have multiple active sessions
supported by a single GHC instance.

Before:

$ grep 'global_var' */*hs | wc -l
     78

After:

$ grep 'global_var' */*hs | wc -l
     27

Well, it's an improvement.  Most of what's left won't really affect
our ability to host multiple sessions.

Lots of static flags have become dynamic flags (yay!).  Notably lots
of flags that we used to think of as "driver" flags, like -I and -L,
are now dynamic.  The most notable static flags left behind are the
"way" flags, eg. -prof.  It would be nice to fix this, but it isn't
urgent.

On the way, lots of cleanup has happened.  Everything related to
static and dynamic flags lives in StaticFlags and DynFlags
respectively, and they share a common command-line parser library in
CmdLineParser.  The flags related to modes (--makde, --interactive
etc.) are now private to the front end: in fact private to Main
itself, for now.

Fix to the pre-Xmas simplifier changes, which should make 
everything work again.  I'd forgotten to attend to this
corner.  Still not properly tested I fear.

Also remove dead code from SimplEnv, and simplify the remainder (hooray).

--------------------------------
	Deal properly with dual-renaming
	--------------------------------

When comparing types and terms, and during matching, we are faced
with 
	\x.e1	~   \y.e2

There are many pitfalls here, and GHC has never done the job properly.
Now, at last it does, using a new abstraction VarEnv.RnEnv2.  See
comments there for how it works.

There are lots of consequential changes to use the new stuff, especially
in 
	types/Type (type comparison), 
	types/Unify (matching on types)
	coreSyn/CoreUtils (equality on expressions), 
	specialise/Rules (matching).

I'm not 100% certain of that I've covered all the bases, so let me
know if something unexpected happens after you update.  Maybe wait until
a nightly build has worked ok first!

------------------------------------
	Add Generalised Algebraic Data Types
	------------------------------------

This rather big commit adds support for GADTs.  For example,

    data Term a where
 	  Lit :: Int -> Term Int
	  App :: Term (a->b) -> Term a -> Term b
	  If  :: Term Bool -> Term a -> Term a
	  ..etc..

    eval :: Term a -> a
    eval (Lit i) = i
    eval (App a b) = eval a (eval b)
    eval (If p q r) | eval p    = eval q
    		    | otherwise = eval r


Lots and lots of of related changes throughout the compiler to make
this fit nicely.

One important change, only loosely related to GADTs, is that skolem
constants in the typechecker are genuinely immutable and constant, so
we often get better error messages from the type checker.  See
TcType.TcTyVarDetails.

There's a new module types/Unify.lhs, which has purely-functional
unification and matching for Type. This is used both in the typechecker
(for type refinement of GADTs) and in Core Lint (also for type refinement).

Add type sig

Add elemSubstEnv

More renamer stuff

Add an access function substEnvEnv

Simon's Marktoberdorf Commits

1.  Tidy up the renaming story for "system binders", such as
dictionary functions, default methods, constructor workers etc.  These
are now documented in HsDecls.  The main effect of the change, apart
from tidying up, is to make the *type-checker* (instead of the
renamer) generate names for dict-funs and default-methods.  This is
good because Sergei's generic-class stuff generates new classes at
typecheck time.


2.  Fix the CSE pass so it does not require the no-shadowing invariant.
Keith discovered that the simplifier occasionally returns a result
with shadowing.  After much fiddling around (which has improved the
code in the simplifier a bit) I found that it is nearly impossible to
arrange that it really does do no-shadowing.  So I gave up and fixed
the CSE pass (which is the only one to rely on it) instead.


3. Fix a performance bug in the simplifier.  The change is in
SimplUtils.interestingArg.  It computes whether an argment should 
be considered "interesting"; if a function is applied to an interesting
argument, we are more likely to inline that function.
Consider this case
	let x = 3 in f x
The 'x' argument was considered "uninteresting" for a silly reason.
Since x only occurs once, it was unconditionally substituted, but
interestingArg didn't take account of that case.  Now it does.

I also made interestingArg a bit more liberal.  Let's see if we
get too much inlining now.


4.  In the occurrence analyser, we were choosing a bad loop breaker.
Here's the comment that's now in OccurAnal.reOrderRec

    score ((bndr, rhs), _, _)
	| exprIsTrivial rhs 	   = 3	-- Practically certain to be inlined
		-- Used to have also: && not (isExportedId bndr)
		-- But I found this sometimes cost an extra iteration when we have
		--	rec { d = (a,b); a = ...df...; b = ...df...; df = d }
		-- where df is the exported dictionary. Then df makes a really
		-- bad choice for loop breaker

I also increased the score for bindings with a non-functional type, so that
dictionaries have a better chance of getting inlined early


5. Add a hash code to the InScopeSet (and make it properly abstract)
This should make uniqAway a lot more robust.  Simple experiments suggest
that uniqAway no longer gets into the long iteration chains that it used
to.


6.  Fix a bug in the inliner that made the simplifier tend to get into
a loop where it would keep iterating ("4 iterations, bailing out" message).
In SimplUtils.mkRhsTyLam we float bindings out past a big lambda, thus:
	x = /\ b -> let g = \x -> f x x
		    in E
becomes
	g* = /\a -> \x -> f x x
	x = /\ b -> let g = g* b in E
	
It's essential that we don't simply inling g* back into the RHS of g,
else we will be back to square 1.  The inliner is meant not to do this
because there's no benefit to the inlining, but the size calculation
was a little off in CoreUnfold.


7.  In SetLevels we were bogus-ly building a Subst with an empty in-scope
set, so a WARNING popped up when compiling some modules.  (knights/ChessSetList
was the example that tickled it.)  Now in fact the warning wasn't an error,
but the Right Thing to do is to carry down a proper Subst in SetLevels, so
that is what I have now done.  It is very little more expensive.

This commit completely re-does the kind-inference mechanism.
Previously it was inter-wound with type inference, but that was
always hard to understand, and it finally broke when we started
checking for ambiguity when type-checking a type signature (details
irrelevant).

So now kind inference is more clearly separated, so that it never
takes place at the same time as type inference.  The biggest change
is in TcTyClsDecls, which does the kind inference for a group of
type and class declarations.  It now contains comments to explain
how it all works.

There are also comments in TypeRep which describes the slightly
tricky way in which we deal with the fact that kind 'type' (written
'*') actually has 'boxed type' and 'unboxed type' as sub-kinds.
The whole thing is a bit of a hack, because we don't really have 
sub-kinding, but it's less of a hack than before.

A lot of general tidying up happened at the same time.
In particular, I removed some dead code here and there

This utterly gigantic commit is what I've been up to in background
mode in the last couple of months.  Originally the main goal
was to get rid of Con (staturated constant applications)
in the CoreExpr type, but one thing led to another, and I kept
postponing actually committing.   Sorry.

	Simon, 23 March 2000


I've tested it pretty thoroughly, but doubtless things will break.

Here are the highlights

* Con is gone; the CoreExpr type is simpler
* NoRepLits have gone
* Better usage info in interface files => less recompilation
* Result type signatures work
* CCall primop is tidied up
* Constant folding now done by Rules
* Lots of hackery in the simplifier
* Improvements in CPR and strictness analysis

Many bug fixes including

* Sergey's DoCon compiles OK; no loop in the strictness analyser
* Volker Wysk's programs don't crash the CPR analyser

I have not done much on measuring compilation times and binary sizes;
they could have got worse.  I think performance has got significantly
better, though, in most cases.


Removing the Con form of Core expressions
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
The big thing is that

  For every constructor C there are now *two* Ids:

	C is the constructor's *wrapper*. It evaluates and unboxes arguments
	before calling $wC.  It has a perfectly ordinary top-level defn
	in the module defining the data type.

	$wC is the constructor's *worker*.  It is like a primop that simply
	allocates and builds the constructor value.  Its arguments are the
	actual representation arguments of the constructor.
	Its type may be different to C, because:
		- useless dict args are dropped
		- strict args may be flattened

  For every primop P there is *one* Id, its (curried) Id

  Neither contructor worker Id nor the primop Id have a defminition anywhere.
  Instead they are saturated during the core-to-STG pass, and the code generator
  generates code for them directly. The STG language still has saturated
  primops and constructor applications.

* The Const type disappears, along with Const.lhs.  The literal part
  of Const.lhs reappears as Literal.lhs.  Much tidying up in here,
  to bring all the range checking into this one module.

* I got rid of NoRep literals entirely.  They just seem to be too much trouble.

* Because Con's don't exist any more, the funny C { args } syntax
  disappears from inteface files.


Parsing
~~~~~~~
* Result type signatures now work
	f :: Int -> Int = \x -> x
	-- The Int->Int is the type of f

	g x y :: Int = x+y
	-- The Int is the type of the result of (g x y)


Recompilation checking and make
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
* The .hi file for a modules is not touched if it doesn't change.  (It used to
  be touched regardless, forcing a chain of recompilations.)  The penalty for this
  is that we record exported things just as if they were mentioned in the body of
  the module.  And the penalty for that is that we may recompile a module when
  the only things that have changed are the things it is passing on without using.
  But it seems like a good trade.

* -recomp is on by default

Foreign declarations
~~~~~~~~~~~~~~~~~~~~
* If you say
	foreign export zoo :: Int -> IO Int
  then you get a C produre called 'zoo', not 'zzoo' as before.
  I've also added a check that complains if you export (or import) a C
  procedure whose name isn't legal C.


Code generation and labels
~~~~~~~~~~~~~~~~~~~~~~~~~~
* Now that constructor workers and wrappers have distinct names, there's
  no need to have a Foo_static_closure and a Foo_closure for constructor Foo.
  I nuked the entire StaticClosure story.  This has effects in some of
  the RTS headers (i.e. s/static_closure/closure/g)


Rules, constant folding
~~~~~~~~~~~~~~~~~~~~~~~
* Constant folding becomes just another rewrite rule, attached to the Id for the
  PrimOp.   To achieve this, there's a new form of Rule, a BuiltinRule (see CoreSyn.lhs).
  The prelude rules are in prelude/PrelRules.lhs, while simplCore/ConFold.lhs has gone.

* Appending of constant strings now works, using fold/build fusion, plus
  the rewrite rule
	unpack "foo" c (unpack "baz" c n)  =  unpack "foobaz" c n
  Implemented in PrelRules.lhs

* The CCall primop is tidied up quite a bit.  There is now a data type CCall,
  defined in PrimOp, that packages up the info needed for a particular CCall.
  There is a new Id for each new ccall, with an big "occurrence name"
	{__ccall "foo" gc Int# -> Int#}
  In interface files, this is parsed as a single Id, which is what it is, really.

Miscellaneous
~~~~~~~~~~~~~
* There were numerous places where the host compiler's
  minInt/maxInt was being used as the target machine's minInt/maxInt.
  I nuked all of these; everything is localised to inIntRange and inWordRange,
  in Literal.lhs

* Desugaring record updates was broken: it didn't generate correct matches when
  used withe records with fancy unboxing etc.  It now uses matchWrapper.

* Significant tidying up in codeGen/SMRep.lhs

* Add __word, __word64, __int64 terminals to signal the obvious types
  in interface files.  Add the ability to print word values in hex into
  C code.

* PrimOp.lhs is no longer part of a loop.  Remove PrimOp.hi-boot*


Types
~~~~~
* isProductTyCon no longer returns False for recursive products, nor
  for unboxed products; you have to test for these separately.
  There's no reason not to do CPR for recursive product types, for example.
  Ditto splitProductType_maybe.

Simplification
~~~~~~~~~~~~~~~
* New -fno-case-of-case flag for the simplifier.  We use this in the first run
  of the simplifier, where it helps to stop messing up expressions that
  the (subsequent) full laziness pass would otherwise find float out.
  It's much more effective than previous half-baked hacks in inlining.

  Actually, it turned out that there were three places in Simplify.lhs that
  needed to know use this flag.

* Make the float-in pass push duplicatable bindings into the branches of
  a case expression, in the hope that we never have to allocate them.
  (see FloatIn.sepBindsByDropPoint)

* Arrange that top-level bottoming Ids get a NOINLINE pragma
  This reduced gratuitous inlining of error messages.
  But arrange that such things still get w/w'd.

* Arrange that a strict argument position is regarded as an 'interesting'
  context, so that if we see
	foldr k z (g x)
  then we'll be inclined to inline g; this can expose a build.

* There was a missing case in CoreUtils.exprEtaExpandArity that meant
  we were missing some obvious cases for eta expansion
  Also improve the code when handling applications.

* Make record selectors (identifiable by their IdFlavour) into "cheap" operations.
	  [The change is a 2-liner in CoreUtils.exprIsCheap]
  This means that record selection may be inlined into function bodies, which
  greatly improves the arities of overloaded functions.

* Make a cleaner job of inlining "lone variables".  There was some distributed
  cunning, but I've centralised it all now in SimplUtils.analyseCont, which
  analyses the context of a call to decide whether it is "interesting".

* Don't specialise very small functions in Specialise.specDefn
  It's better to inline it.  Rather like the worker/wrapper case.

* Be just a little more aggressive when floating out of let rhss.
  See comments with Simplify.wantToExpose
  A small change with an occasional big effect.

* Make the inline-size computation think that
	case x of I# x -> ...
  is *free*.


CPR analysis
~~~~~~~~~~~~
* Fix what was essentially a bug in CPR analysis.  Consider

	letrec f x = let g y = let ... in f e1
		     in
		     if ... then (a,b) else g x

  g has the CPR property if f does; so when generating the final annotated
  RHS for f, we must use an envt in which f is bound to its final abstract
  value.  This wasn't happening.  Instead, f was given the CPR tag but g
  wasn't; but of course the w/w pass gives rotten results in that case!!
  (Because f's CPR-ness relied on g's.)

  On they way I tidied up the code in CprAnalyse.  It's quite a bit shorter.

  The fact that some data constructors return a constructed product shows
  up in their CPR info (MkId.mkDataConId) not in CprAnalyse.lhs



Strictness analysis and worker/wrapper
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
* BIG THING: pass in the demand to StrictAnal.saExpr.  This affects situations
  like
	f (let x = e1 in (x,x))
  where f turns out to have strictness u(SS), say.  In this case we can
  mark x as demanded, and use a case expression for it.

  The situation before is that we didn't "know" that there is the u(SS)
  demand on the argument, so we simply computed that the body of the let
  expression is lazy in x, and marked x as lazily-demanded.  Then even after
  f was w/w'd we got

	let x = e1 in case (x,x) of (a,b) -> $wf a b

  and hence

	let x = e1 in $wf a b

  I found a much more complicated situation in spectral/sphere/Main.shade,
  which improved quite a bit with this change.

* Moved the StrictnessInfo type from IdInfo to Demand.  It's the logical
  place for it, and helps avoid module loops

* Do worker/wrapper for coerces even if the arity is zero.  Thus:
	stdout = coerce Handle (..blurg..)
  ==>
	wibble = (...blurg...)
	stdout = coerce Handle wibble
  This is good because I found places where we were saying
	case coerce t stdout of { MVar a ->
	...
	case coerce t stdout of { MVar b ->
	...
  and the redundant case wasn't getting eliminated because of the coerce.

A regrettably-gigantic commit that puts in place what Simon PJ
has been up to for the last month or so, on and off.

The basic idea was to restore unfoldings to *occurrences* of
variables without introducing a space leak.  I wanted to make
sure things improved relative to 4.04, and that proved depressingly
hard.  On the way I discovered several quite serious bugs in the
simplifier.

Here's a summary of what's gone on.
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
* No commas between for-alls in RULES.  This makes the for-alls have
  the same syntax as in types.

* Arrange that simplConArgs works in one less pass than before.
  This exposed a bug: a bogus call to completeBeta.

* Add a top-level flag in CoreUnfolding, used in callSiteInline

* Extend w/w to use etaExpandArity, so it does eta/coerce expansion

* Implement inline phases.   The meaning of the inline pragmas is
  described in CoreUnfold.lhs.  You can say things like
	{#- INLINE 2 build #-}
  to mean "inline build in phase 2"

* Don't float anything out of an INLINE.
  Don't float things to top level unless they also escape a value lambda.
	[see comments with SetLevels.lvlMFE
  Without at least one of these changes, I found that
	{-# INLINE concat #-}
	concat = __inline (/\a -> foldr (++) [])
  was getting floated to
	concat = __inline( /\a -> lvl a )
	lvl = ...inlined version of foldr...

  Subsequently I found that not floating constants out of an INLINE
  gave really bad code like
	__inline (let x = e in \y -> ...)
  so I now let things float out of INLINE

* Implement the "reverse-mapping" idea for CSE; actually it turned out to be easier
  to implement it in SetLevels, and may benefit full laziness too.

* It's a good idea to inline inRange. Consider

	index (l,h) i = case inRange (l,h) i of
		  	  True ->  l+i
			  False -> error
  inRange itself isn't strict in h, but if it't inlined then 'index'
  *does* become strict in h.  Interesting!

* Big change to the way unfoldings and occurrence info is propagated in the simplifier
  The plan is described in Subst.lhs with the Subst type
  Occurrence info is now in a separate IdInfo field than user pragmas

* I found that
	(coerce T (coerce S (\x.e))) y
  didn't simplify in one round. First we get to
	(\x.e) y
  and only then do the beta. Solution: cancel the coerces in the continuation

* Amazingly, CoreUnfold wasn't counting the cost of a function an application.

* Disable rules in initial simplifier run.  Otherwise full laziness
  doesn't get a chance to lift out a MFE before a rule (e.g. fusion)
  zaps it.  queens is a case in point

* Improve float-out stuff significantly.  The big change is that if we have

	\x -> ... /\a -> ...let p = ..a.. in let q = ...p...

  where p's rhs doesn't x, we abstract a from p, so that we can get p past x.
  (We did that before.)  But we also substitute (p a) for p in q, and then
  we can do the same thing for q.  (We didn't do that, so q got stuck.)
  This is much better.  It involves doing a substitution "as we go" in SetLevels,
  though.

This commit makes a start at implementing polymorphic usage
annotations.

* The module Type has now been split into TypeRep, containing the
  representation Type(..) and other information for `friends' only,
  and Type, providing the public interface to Type.  Due to a bug in
  the interface-file slurping prior to ghc-4.04, {-# SOURCE #-}
  dependencies must unfortunately still refer to TypeRep even though
  they are not friends.

* Unfoldings in interface files now print as __U instead of __u.
  UpdateInfo now prints as __UA instead of __U.

* A new sort of variables, UVar, in their own namespace, uvName, has
  been introduced for usage variables.

* Usage binders __fuall uv have been introduced.  Usage annotations
  are now __u - ty (used once), __u ! ty (used possibly many times),
  __u uv ty (used uv times), where uv is a UVar.  __o and __m have
  gone.  All this still lives only in a TyNote, *for now* (but not for
  much longer).

* Variance calculation for TyCons has moved from
  typecheck/TcTyClsDecls to types/Variance.

* Usage annotation and inference are now done together in a single
  pass.  Provision has been made for inferring polymorphic usage
  annotations (with __fuall) but this has not yet been implemented.
  Watch this space!

RULES-NOTES

(this is number 4 of 9 commits to be applied together)

  The major purpose of this commit is to introduce usage information
  and usage analysis into the compiler, per the paper _Once Upon a
  Polymorphic Type_ (Keith Wansbrough and Simon Peyton Jones, POPL'99,
  and Glasgow TR-1998-19).

  Usage information has been added to types, in the form of a new kind
  of NoteTy: (UsgNote UsageAnn(UsOnce|UsMany|UsVar UVar)).  Usages
  print as __o (once), __m (many, usually omitted), or (not in
  interface files) __uvxxxx.  Usage annotations should only appear at
  certain places in a type (see the paper).  The `default' annotation
  is __m, and so an omitted annotation implies __m.  Utility functions
  for handling usage annotations are provided in Type.

  If the compiler is built with -DUSMANY (a flag intended for use in
  debugging by KSW only), __m are *required* and may not be omitted.

  The major constraint is that type arguments (eg to mkAppTy) must be
  unannotated on top.  To maintain this invariant, many functions
  required the insertion of Type.unUsgTy (removing annot from top of a
  type) or UsageSPUtils.unannotTy (removing all annotations from a
  type).  A function returning usage-annotated types for primops has
  been added to PrimOp.

  A new kind of Note, (TermUsg UsageAnn), has been added to annotate
  Terms.  This note is *not* printed in interface files, and for the
  present does not escape the internals of the usage inference engine.

Another big commit from Simon.  Actually, the last one
didn't all go into the main trunk; because of a CVS glitch it
ended up in the wrong branch.

So this commit includes:

* Scoped type variables
* Warnings for unused variables should work now (they didn't before)
* Simplifier improvements:
	- Much better treatment of strict arguments
	- Better treatment of bottoming Ids
	- No need for w/w split for fns that are merely strict
	- Fewer iterations needed, I hope
* Less gratuitous renaming in interface files and abs C
* OccName is a separate module, and is an abstract data type

I think the whole Prelude and Exts libraries compile correctly.
Something isn't quite right about typechecking existentials though.

Move 4.01 onto the main trunk.