GitLab

If these modules use UniqFM then we get a stack overflow when compiling
modules that use fundeps. I haven't tracked down the actual cause.

This is another gloss on the now-quite-subtle and heavily-documented algorithm
for choosing loop breakers.

This fix, provoked by Roman's NDP library, makes sure that when we are choosing
a loop breaker we only take into account variables free on the *rhs* of a rule
not the *lhs*.

Most of the new lines are comments!

	(Merge to 6.8 branch after testing.)

There were a number of delicate interactions between RULEs and inlining
in GHC 6.6.  I've wanted to fix this for a long time, and some perf
problems in the 6.8 release candidate finally forced me over the edge!

The issues are documented extensively in OccurAnal, Note [Loop breaking
and RULES], and I won't duplicate them here.  (Many of the extra lines in
OccurAnal are comments!)

This patch resolves Trac bugs #1709, #1794, #1763, I believe.

Previously inline candidates were given higher preference as
non-loop-breakers than constructor applications, but the reason for
this was that making a wrapper into a loop-breaker is to be avoided at
all costs.  This patch refines the algorithm slightly so that wrappers
are explicitly avoided by giving them a much higher score, and other
inline candidates are given lower scores than constructor
applications.

This makes almost zero difference to a complete nofib run, so it
amounts to just a tidyup.

Older GHCs can't parse OPTIONS_GHC.
This also changes the URL referenced for the -w options from
WorkingConventions#Warnings to CodingStyle#Warnings for the compiler
modules.

See Note [Inline candidates] in OccurAnal.  We were getting a recursive
loop exposed, which led to infinite inlinings.  Doesn't bite much, but
was obviously wrong.

I've change the "scoring order" for loop breakers, which could possibly
have a performance impact on other programs.  A full nofib run exposed
a 0.00% change in allocation in any nofib program, so I don't think it's
likely, but keep an eye out.

mapAccumL and mapAccumR are in Data.List now.
mapAccumB is unused.

See Note [Recursive rules] in OccurAnal

See Note [Closure conversion] in OccurAnal for details of this
patch (which merely involves *deleting* a test!).  The test case
was produced by Roman, and shows up when doing closure conversion
and vectorisation for data parallelism.  But perhaps other times too.

I recentl changed the scoring system used by dependency analysis for
recursive bindings, that it used the *form* of the RHS of a binding,
rather than just its type. In doing so I inadvertently made recursive
dictionary bindings unravel less well, because I'd missed the case
of 	c = /\a. C (...) (...)

This patch fixes the problem.  A good example is the instance for
Monad (ST s) or Show (ST s a) in GHC.ST.  It's vital for these
dictionaries to be inlinable.

The loop-breaking heuristics were making it a high priority to
avoid choosing a variable as a loop breaker if its *type* was a 
data type.  The reason is that it's very good to be able to "see"
constructor applications.

But it's only good if the constructor application is *visible*, 
so that is what I test for now.  I found a case (when testing 
SpecConstr) where I had a Rec like this:
	rec { lvl = foo Nothing
	      foo = ...
	        RULE foo Nothing = ...
   	    }

Even if lvl has a data type, it's much better to make lvl the loop
breaker, not foo, so that foo's RULE is visible in lvl's RHS.

This big patch completely overhauls the Simplifier.  The simplifier
had grown old and crufty, and was hard to understand and maintain.
This new version is still quite complicated, because the simplifier
does a lot, but it's much easier to understand, for me at least.

It does mean that I have touched almost every line of the simplifier,
so the diff is a large one.

Big changes are these

* When simplifying an Expr we generate a simplified Expr plus a 
  bunch of "floats", which are bindings that have floated out
  of the Expr.  Before, this float stuff was returned separately,
  but not they are embedded in the SimplEnv, which makes the
  plumbing much easier and more robust.  In particular, the
  SimplEnv already meaintains the "in-scope set", and making
  that travel with the floats helps to ensure that we always 
  use the right in-scope set.

  This change has a pervasive effect.

* Rather than simplifying the args of a call before trying rules
  and inlining, we now defer simplifying the args until both
  rules and inlining have failed, so we're going to leave a
  call in the result.  This avoids the risk of repeatedly 
  simplifying an argument, which was handled by funny ad-hoc
  flags before.  
  
  The downside is that we must apply the substitution to the args before
  rule-matching; and if thep rule doesn't match that is wasted work.
  But having any rules at all is the exception not the rule, and the
  substitution is lazy, so we only substitute until a no-match is found.
  The code is much more elegant though.

* A SimplCont is now more zipper-like. It used to have an embedded
  function, but that was a bit hard to think about, and now it's
  nice and consistent. The relevant constructors are StrictArg
  and StrictBind

* Each Rule now has an *arity* (gotten by CoreSyn.ruleArity), which 
  tells how many arguments it matches against.  This entailed adding
  a field ru_nargs to a BuiltinRule.  And that made me look at 
  PrelRules; I did quite a bit of refactoring in the end, so the
  diff in PrelRules looks much biggger than it really is.

* A little refactoring in OccurAnal.  The key change is that in 
  the RHS of	x = y `cast` co
  we regard 'y' as "many", so that it doesn't get inlined into 
  the RHS of x.  This allows x to be inlined elsewhere.  It's 
  very like the existing situation for
		x = Just y
  where we treat 'y' as "many".

This is another attempt to fix the interaction between recursion and
RULES.  I just had it wrong before!  Now the significance of the
flag on IAmALoopBreaker is given in BasicTypes

  | IAmALoopBreaker	-- Used by the occurrence analyser to mark loop-breakers
			-- in a group of recursive definitions
	!RulesOnly	-- True <=> This loop breaker mentions the other binders
			--	    in its recursive group only in its RULES, not
			--	    in its rhs
			--  See OccurAnal Note [RulesOnly]

This is part 2 of the patch that improved the interaction of RULES and
recursion.  It's vital that all Ids that may be referred to from later in
the module are marked 'IAmALoopBreaker' because otherwise we may do
postInlineUnconditionally, and lose the binding altogether. 

So I've added a boolean rules-only flag to IAmALoopBreaker.  Now we can
do inlining for rules-only loop-breakers. 

See Trac #683

This patch improves the interaction of recursion and RULES; at least I
hope it does.   The problem was that a RULE was being treated uniformly like
an "extra RHS". This worked badly when you have a non-recursive definition
that is made recursive only by RULE.

This patch maeks the occurrence analyser know whether a binder is referred to
only from RULES (the RulesOnly constructor in OccInfo).  Then we can ignore
such edges when deciding on the order of bindings in a letrec, and when
setting the LoopBreaker flag.

The remaining potential problem is this:
	rec{ f = ...g...
	   ; g = ...f...
	     RULE g True = ...
	   }

The RULE for g may not be visible in f's rhs.  This is fixable, but not
today.

Fri Aug  4 18:13:20 EDT 2006  Manuel M T Chakravarty <chak@cse.unsw.edu.au>
  * Massive patch for the first months work adding System FC to GHC #30
  
  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.

I have spent altogether too long on my attempt to avoid case-of-case
in situations where it is a Bad Thing.  All the action is in the
case for mkDupableAlt that handles cases with a single alternative.

I've added rather extensive comments, and it finally seems to be working
more or less right.  If you compile (say) GHC/Real.o you'll see quite a
few case-of-cases remain (which didn't happen before), and they mostly look
pretty sensible to me.

Consider
	x = case y of { True -> (p,q); ... }

The occurrence analyser was marking p,q as 'Many', because they args
of a constructor in an RhsCtxt.  But actually they aren't in a RhsCtxt,
and in this case it's better to inline.

Add Id.idHasRules :: Id -> Bool, with the obvious semantics.
This patch makes sense by itself, but it's just a tidy-up.

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.

	~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Simplfy (i.e. substitute) the IdInfo of a recursive group of Ids
before looking at the RHSs of *any* of them.  That way, the rules
are available throughout the letrec, which means we don't have to
be careful about function to put first.

Before, we just simplified the IdInfo of f before looking at f's RHS,
but that's not so good when f and g both have RULES, and both rules
mention the other.

This change makes things simpler, but shouldn't change performance.

Patch from SimonPJ (slightly tweaked by me after checking performance
results):

Fix occasional O(n^2) behaviour in the simplifier.  There was a
possibility that by inlining a binding, we could re-simplify an
arbitrary sized expression.  This patch fixes it by moving the
inlining of arbitrary-sized expressiong to the binding site
(preInlineUnconditionally), so the decision to inline happens before
simplifying the RHS.  To do this, we have to collect more information
during the occurrence analysis phase.

We still make inlining decisions at the call site, but they are always
size-limited, so we can't get quadratic blowup.

WARNING: this is a big commit.  You might want 
	to wait a few days before updating, in case I've 
	broken something.

	However, if any of the changes are what you wanted,
	please check it out and test!

This commit does three main things:

1. A re-organisation of the way that GHC handles bindings in HsSyn.
   This has been a bit of a mess for quite a while.  The key new
   types are

	-- Bindings for a let or where clause
	data HsLocalBinds id
	  = HsValBinds (HsValBinds id)
	  | HsIPBinds  (HsIPBinds id)
	  | EmptyLocalBinds

	-- Value bindings (not implicit parameters)
	data HsValBinds id
	  = ValBindsIn  -- Before typechecking
		(LHsBinds id) [LSig id]	-- Not dependency analysed
					-- Recursive by default

	  | ValBindsOut	-- After typechecking
		[(RecFlag, LHsBinds id)]-- Dependency analysed

2. Implement Mark Jones's idea of increasing polymoprhism
   by using type signatures to cut the strongly-connected components
   of a recursive group.  As a consequence, GHC no longer insists
   on the contexts of the type signatures of a recursive group
   being identical.

   This drove a significant change: the renamer no longer does dependency
   analysis.  Instead, it attaches a free-variable set to each binding,
   so that the type checker can do the dep anal.  Reason: the typechecker
   needs to do *two* analyses:
	one to find the true mutually-recursive groups
		(which we need so we can build the right CoreSyn)
	one to find the groups in which to typecheck, taking
		account of type signatures

3. Implement non-ground SPECIALISE pragmas, as promised, and as
   requested by Remi and Ross.  Certainly, this should fix the 
   current problem with GHC, namely that if you have
	g :: Eq a => a -> b -> b
   then you can now specialise thus
	SPECIALISE g :: Int -> b -> b
    (This didn't use to work.)

   However, it goes further than that.  For example:
	f :: (Eq a, Ix b) => a -> b -> b
   then you can make a partial specialisation
	SPECIALISE f :: (Eq a) => a -> Int -> Int

    In principle, you can specialise f to *any* type that is
    "less polymorphic" (in the sense of subsumption) than f's 
    actual type.  Such as
	SPECIALISE f :: Eq a => [a] -> Int -> Int
    But I haven't tested that.

    I implemented this by doing the specialisation in the typechecker
    and desugarer, rather than leaving around the strange SpecPragmaIds,
    for the specialiser to find.  Indeed, SpecPragmaIds have vanished 
    altogether (hooray).

    Pragmas in general are handled more tidily.  There's a new
    data type HsBinds.Prag, which lives in an AbsBinds, and carries
    pragma info from the typechecker to the desugarer.


Smaller things

- The loop in the renamer goes via RnExpr, instead of RnSource.
  (That makes it more like the type checker.)

- I fixed the thing that was causing 'check_tc' warnings to be 
  emitted.

This big commit does several things at once (aeroplane hacking)
which change the format of interface files.  

	So you'll need to recompile your libraries!

1. The "stupid theta" of a newtype declaration
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Retain the "stupid theta" in a newtype declaration.
For some reason this was being discarded, and putting it
back in meant changing TyCon and IfaceSyn slightly.
   

2. Overlap flags travel with the instance
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Arrange that the ability to support overlap and incoherence
is a property of the *instance declaration* rather than the
module that imports the instance decl.  This allows a library
writer to define overlapping instance decls without the
library client having to know.  

The implementation is that in an Instance we store the
overlap flag, and preseve that across interface files


3. Nuke the "instnce pool" and "rule pool"
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
A major tidy-up and simplification of the way that instances
and rules are sucked in from interface files.  Up till now
an instance decl has been held in a "pool" until its "gates" 
(a set of Names) are in play, when the instance is typechecked
and added to the InstEnv in the ExternalPackageState.  
This is complicated and error-prone; it's easy to suck in 
too few (and miss an instance) or too many (and thereby be
forced to suck in its type constructors, etc).

Now, as we load an instance from an interface files, we 
put it straight in the InstEnv... but the Instance we put in
the InstEnv has some Names (the "rough-match" names) that 
can be used on lookup to say "this Instance can't match".
The detailed dfun is only read lazily, and the rough-match
thing meansn it is'nt poked on until it has a chance of
being needed.

This simply continues the successful idea for Ids, whereby
they are loaded straightaway into the TypeEnv, but their
TyThing is a lazy thunk, not poked on until the thing is looked
up.

Just the same idea applies to Rules.

On the way, I made CoreRule and Instance into full-blown records
with lots of info, with the same kind of key status as TyCon or 
DataCon or Class.  And got rid of IdCoreRule altogether.   
It's all much more solid and uniform, but it meant touching
a *lot* of modules.


4. Allow instance decls in hs-boot files
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Allowing instance decls in hs-boot files is jolly useful, becuase
in a big mutually-recursive bunch of data types, you want to give
the instances with the data type declarations.  To achieve this

* The hs-boot file makes a provisional name for the dict-fun, something
  like $fx9.

* When checking the "mother module", we check that the instance
  declarations line up (by type) and generate bindings for the 
  boot dfuns, such as
	$fx9 = $f2
  where $f2 is the dfun generated by the mother module

* In doing this I decided that it's cleaner to have DFunIds get their
  final External Name at birth.  To do that they need a stable OccName,
  so I have an integer-valued dfun-name-supply in the TcM monad.
  That keeps it simple.

This feature is hardly tested yet.


5. Tidy up tidying, and Iface file generation
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
main/TidyPgm now has two entry points:

  simpleTidyPgm is for hi-boot files, when typechecking only
  (not yet implemented), and potentially when compiling without -O.
  It ignores the bindings, and generates a nice small TypeEnv.

  optTidyPgm is the normal case: compiling with -O.  It generates a
  TypeEnv rich in IdInfo

MkIface.mkIface now only generates a ModIface.  A separate
procedure, MkIface.writeIfaceFile, writes the file out to disk.

Instead of gathering a set of 'candidates' in the occurrence
	analyser, use the isLocalId predicate to identify things
	for which occurrence information is required.  By defn
	isLocalId is true of Ids (whether top level or not) defined
	in this module, and that is exactly what we want.

	The 'candidates set' predated the LocalId invariant, I think.

-----------------------------------------
       Fix a long-standing indirection-zapping bug
	-----------------------------------------

	Merge to STABLE

Up to now we zap indirections as part of the occurence analyser.
But this is bogus.  The indirection zapper does the following:

	x_local = <expression>
	...bindings...
	x_exported = x_local

where x_exported is exported, and x_local is not, then we
replace it with this:

	x_exported = <expression>
	x_local = x_exported
	...bindings...

But this is plain wrong if x_exported has a RULE that mentions
something (f, say) in ...bindings.., because 'f' will then die.

After hacking a few solutions, I've eventually simply made the indirection
zapping into a separate pass (which is cleaner anyway), which wraps the
entire program back into a single Rec if the bad thing can happen.

On the way I've made indirection-zapping work in Recs too, which wasn't the
case before.

* Move the zapper from OccurAnal into SimplCore
* Tidy up the printing of pragmas (PprCore and friends)
* Add a new function Rules.addRules
* Merge rules in the indirection zapper (previously one set was discarded)

----------------------------------------
     New Core invariant: keep case alternatives in sorted order
	----------------------------------------

We now keep the alternatives of a Case in the Core language in sorted
order.  Sorted, that is,
	by constructor tag	for DataAlt
	by literal		for LitAlt

The main reason is that it makes matching and equality testing more robust.
But in fact some lines of code vanished from SimplUtils.mkAlts.


WARNING: no change to interface file formats, but you'll need to recompile
your libraries so that they generate interface files that respect the
invariant.

------------------------------------
	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 a flag -fno-state-hack, which switches off the "state hack".

It's claims that every function over realWorldStatePrimTy is a
one-shot function.  This is pretty true in practice, and makes a big
difference.  For example, consider
	a `thenST` \ r -> ...E...
The early full laziness pass, if it doesn't know that r is one-shot
will pull out E (let's say it doesn't mention r) to give
	let lvl = E in a `thenST` \ r -> ...lvl...
When `thenST` gets inlined, we end up with
	let lvl = E in \s -> case a s of (r, s') -> ...lvl...
and we don't re-inline E.

-----------------------------------------------------
  Fix a subtle loop in the context-reduction machinery
  ----------------------------------------------------

This bug was provoked by a recent change: when trying to prove
a constraint C, TcSimplify.reduce now adds C to the database before
trying to prove C, thus building recursive dictionaries.

Two bugs
a) If we add C's superclasses (which we were) we can now build a
   bogusly-recursive dictionary (see Note [SUPERCLASS-LOOP]).
   Solution: in reduce, add C only (via addIrred NoSCs) and then
   later use addWanted to add its definition plus SCs.

b) Since we can have recursive definitions, the superclass-loop
   handling machinery (findAllDeps) must carry its visited-set
   with it (which it was not doing before)


The main file is TcSimplify; but I modified a bunch of others to
take advantage of new function extendVarSetList

-------------------------------------
  Big upheaval to the way that constructors are named
	-------------------------------------

This commit enshrines the new story for constructor names.  We could never
really get External Core to work nicely before, but now it does.

The story is laid out in detail in the Commentary
	ghc/docs/comm/the-beast/data-types.html
so I will not repeat it here.

	[Manuel: the commentary isn't being updated, apparently.]

However, the net effect is that in Core and in External Core, contructors look
like constructors, and the way things are printed is all consistent.

It is a fairly pervasive change (which is why it has been so long postponed),
but I hope the question is now finally closed.

All the libraries compile etc, and I've run many tests, but doubtless there will
be some dark corners.

------------------------------------
	Improve occurrence analysis a little
	------------------------------------

Consider

		x1 = a0 : []
		x2 = a1 : x1
		x3 = a2 : x2
		g  = f x3

First time round, it looks as if x1 and x2 occur as an arg of a
let(rec)-bound constructor, and hence should not be inlined. (If the
RHS of a let is just (C a b) where C is a constructor, then we like to
keep it that way, with atomic a,b, so that it can be inlined easily at
a 'case'.)

But in this case, x3 is inlined in g's RHS... and now x2 is not an arg
of a let-bound constructor, so it can be inlined, and then x1.   Result:

		g = f (a2 : a1 : a0 : [])

Which is fine.  What is *not* fine is that it has been costing us a
whole simplifier iteration for each element!

This commit adds another little hack to get around the problem: don't treat
constructor RHSs specially if the bound variable looks as if it occurs just
once so it'll be inlined.  This catches the common case very nicely.

It's a pain that we have the atomic-args-for-constructor-RHSs invariant.
But I can't see  how to do without it.