GitLab

a) When generating specialisations, include the types in the name
   of the rule, to avoid having rules with duplicate names.
   (The rule name is used to put rules in canonical order for
   fingerprinting.)

b) In Specialise and SpecConstr use a new function Rules.pprRulesForUser
   to print rules in canonical order.  This reduces unnecessary wobbling
   in test output, notably in T2486

The uniques that come out in dumpStyle make it harder to compare
output in the testsuite.  And the rules are tidied, so uniques
are not necessary.  If you want the uniques, use -dppr-debug.

In SpecConstr.isValue, we recorded a ConVal for a big-lambda,
which seems wrong. I came across this when implementing System IF.
The code now reads:

  isValue env (Lam b e)
    | isTyVar b = case isValue env e of
  		    Just _  -> Just LambdaVal	-- NB!
  		    Nothing -> Nothing
    | otherwise = Just LambdaVal

This patch makes a significant improvement to SpecConstr, based on
Roman's experience with using it for stream fusion.  The main change is
this:

  * For local (not-top-level) declarations, seed the specialisation 
    loop from the calls in the body of the 'let'.

See Note [Local recursive groups] for discussion and example.  Top-level
declarations are treated just as before.

Other changes in this patch:

  * New flag -fspec-constr-count=N sets the maximum number of specialisations
    for any single function to N.  -fno-spec-constr-count removes the limit.

  * Refactoring in specLoop and friends; new algebraic data types 
    OneSpec and SpecInfo instead of the tuples that were there before

  * Be less keen to specialise on variables that are simply in scope.
    Example
      f p q = letrec g a y = ...g....  in g q p
    We probably do not want to specialise 'g' for calls with exactly
    the arguments 'q' and 'p', since we know nothing about them.

Work around various problems caused by some of the monadification patches
not being applied.

This patch addresses a problem that Roman found in SpecConstr.  Consider:

foo :: Maybe Int -> Maybe Int -> Int
foo a b = let j b = foo a b
           in
           case b of
             Nothing -> ...
             Just n  -> case a of
                          Just m  -> ... j (Just (n+1)) ...
                          Nothing -> ... j (Just (n-1)) ...

We want to make specialised versions for 'foo' for the patterns
	Nothing  (Just v)
	(Just a) (Just b)

Two problems, caused by the join point j.  First, j does not
scrutinise b, so j won't be specialised f for the (Just v) pattern.
Second, j is defined where the free var 'a' is not evaluated.

Both are solved by brutally inlining j at its call sites.  This risks
major code bloat, but it's relatively quick to implement.  The flag
	-fspec-inline-join-points
causes brutal inlining for a 
	non-recursive binding
	of a function
	whose RHS contains calls
	of a recursive function

The (experimental) flag is static for now, and I have not even
documented it properly.

This patch replaces -fspec-threshold by -fspec-constr-threshold and
-fliberate-case-threshold. The thresholds can be disabled by
-fno-spec-constr-threshold and -fno-liberate-case-threshold.

The Cast case of the rule-matcher was simply wrong.

This patch fixes it; see Trac #1746.

I also fixed the rule generation in SpecConstr to generate a wild-card
for the cast expression, which we don't want to match on.  This makes
the rule more widely applicable; it wasn't the cause of the bug.

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.

Consider
  lvl = Just True

  foo :: Maybe Bool -> Int -> Int
  foo (Just True) i = i
  foo _           i = foo lvl i

SpecConstr should specialise foo, but it wasn't doing so (spotted
by Roman).

Reason: lvl's unfolding wasn't in the cloned version of lvl.
Solution: extend the value environment to record top-level bindings too

At the same time I made it work if 'lvl' is a lambda, in which case it
is again worth specialisg.  This meant renaming ConEnv to ValueEnv,
and adding a case for 'LambdaVal'.

(To make specialisation on lambdas work properly, we have to do lambda
lifting as well, but this gets part of the way, and fixes a bug too.)

This has been a long-standing ToDo.

These bugs produced a core-lint error when compiling 
GHC.PArr with -O2.  Roman found and fixed them; this
patch also includes some type synonyms to make things a
bit clearer.

This patch improves the SpecConstr pass, by 
  a) making it work with join points
  b) making it generate specialisations transitively

As part of it, SpecConstr now carries a substitution with it, which
runs over the whole program as it goes.  This turned out to be 
a big win; simplified the implementation quite a bit.

I have *disabled* the specialisation on lambdas; it's pretty fragile,
and sometimes generates more and more specialisations. Something to
come back to, perhaps.

I rejigged the flag-handling a bit.  Now the specification of passes
in DynFlags is a bit nicer; see
	- optLevelFlags top-level data structure
	- runWhen function
	- CoreDoPasses constructor

There are now command-line flags
	-fspec-constr
	-fliberate-case
	-fspec-threshold=N
which do the obvious thing.  -O2 switches on both spec-constr and liberate-case.
You can use -fno-liberate-case, -fno-spec-constr after -O2 to switch them off again.

The spec-threshold applies to both these transformations; default value 200 for now.

Roman found cases where it was important to do SpecConstr for
mutually-recursive definitions.  Here is one:
	foo :: Maybe Int -> Int
	foo Nothing  = 0
	foo (Just 0) = foo Nothing
	foo (Just n) = foo (Just (n-1))
By the time SpecConstr gets to it, it looks like this:
	lvl = foo Nothing
	foo Nothing  = 0
	foo (Just 0) = lvl
	foo (Just n) = foo (Just (n-1))

Happily, it turns out to be rather straightforward to generalise the
transformation to mutually-recursive functions.  Look, ma, only 4 
extra lines of ocde!

For totally stupid reasons, SpecConstr didn't work for the (particularly
easy) case of nullary constructors like True and False.  I just had some
equations in the wrong order, so that a Var case came first, which 
matches a nullary constructor, with the constructor-application case
afterwards.

The fix is easy.  I did a bit of refactoring at the same time.

SpecConstr was conservative about avoiding reboxing (see Note [Reboxing])
but that meant it lost useful opportunities.  This patch makes it much
more aggressive, but at the risk of doing some reboxing.

Actually, the strictness analyser has the same property (it's possible
for it to generate reboxing code, and thus increase allocation), but we
don't worry so much about that.  Maybe we should.

Ideally, one would do some more sophisticated analysis that spotted
the reboxing cases without excluding the useful ones.  

But meanwhile, let's try this. 

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 patch teaches SpecConstr about casts; see Note [SpecConstr for casts]

This patch enables argToPat to look through let expressions

e.g.	f (let v = rhs in \y -> ...v...)

Here we can specialise for f (\y -> ...) because the rule-matcher will
look through the let.

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

argToPat is a crucial function for SpecConstr, because it decides
what patterns are worth specialising.  I was being much too gung-ho about
constants.  This patch makes it much better.

I was forgetting the non-pattern-matched type args of a constructor.