GitLab

(NB: this patch could conceivably require some bits of the 
following SpecConstr patch to compile cleanly.  It's conceptually
independent, but I'm not 100% certain that I've included all
the necessary bits here.)

This patch cleans up the simplifier's handling of various
otimisations for case expressions, notably
  - case elimination (discarding the case altogether)
  - merging identical alternatives
  - discarding impossible alternative
  - merging nested cases

Previously this was partly handled before, and partly after,
simplifying the case alternatives. The trouble with that is
that the dead-ness information on the case binders gets munged
during simplification, and that turned out to mean that 
case elmination essentially never happened -- stupid.

Now I've moved it all to before simplifying the alterntives.
In fact this reduces the amount of code, I think, and it's
certainly tidier.  I don't think there is any loss.

This patch improves prepareRhs, so that it deals better with casts.

We want to deal well cases like this
	v = (f e1 `cast` co) e2
Here we want to make e1,e2 trivial and get
	x1 = e1; x2 = e2; v = (f x1 `cast` co) v2

This really happens in parser libraries, which wrap functions in newtypes.

There was a plain bug in the cast-optimiation code -- a call to
splitCoercionKind_maybe instead of coercionKind!  Result was that
we missed useful opportunities to move casts around.  Trac #995
is an example, but I bet there are more.

This changes the internal representation of TickBoxes,
from
        Note (TickBox "module" n)  <expr>
into

        case tick<module,n> of
          _ -> <expr>

tick has type :: #State #World, when the module and tick numbe
are stored inside IdInfo.

Binary tick boxes change from

         Note (BinaryTickBox "module" t f) <expr>

into

          btick<module,t,f> <expr>

btick has type :: Bool -> Bool, with the module and tick number
stored inside IdInfo.

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 large checkin is the new ghc version of Haskell
Program Coverage, an expression-level coverage tool for Haskell.

Parts:

 - Hpc.[ch] - small runtime support for Hpc; reading/writing *.tix files.
 - Coverage.lhs - Annotates the HsSyn with coverage tickboxes.
  - New Note's in Core,
      - TickBox      -- ticked on entry to sub-expression
      - BinaryTickBox  -- ticked on exit to sub-expression, depending
	       	     -- on the boolean result.

  - New Stg level TickBox (no BinaryTickBoxes, though) 

You can run the coverage tool with -fhpc at compile time. 
Main must be compiled with -fhpc. 
				      

Comment Note [Take care] explains.

mkAtomicArgs is a mess.  A substantial rewrite of Simplify is needed.

Note [Float coercions]
~~~~~~~~~~~~~~~~~~~~~~
When we find the binding
	x = e `cast` co
we'd like to transform it to
	x' = e
	x = x `cast` co		-- A trivial binding
There's a chance that e will be a constructor application or function, or something
like that, so moving the coerion to the usage site may well cancel the coersions
and lead to further optimisation.  Example:

     data family T a :: *
     data instance T Int = T Int

     foo :: Int -> Int -> Int
     foo m n = ...
        where
          x = T m
          go 0 = 0
          go n = case x of { T m -> go (n-m) }
		-- This case should optimise

The substitution used to carry "fragile" OccInfo to call sites via the
DoneId constructor of SimplEnv.SimplSR.  This was always a tricky thing 
to do, and for some time I've been removing the need for it.

Now at last I think we can nuke it altogether.  Hooray.

I did a full nonfib run, and got zero perf changes.

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. 

Note [Case of cast]
~~~~~~~~~~~~~~~~~~~
Consider 	case (v `cast` co) of x { I# ->
		... (case (v `cast` co) of {...}) ...
We'd like to eliminate the inner case.  We can get this neatly by 
arranging that inside the outer case we add the unfolding
	v |-> x `cast` (sym co)
to v.  Then we should inline v at the inner case, cancel the casts, 
and away we go
	
This patch does the job, fixing a performance hole reported by Roman.

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.

Mon Sep 18 17:13:11 EDT 2006  Manuel M T Chakravarty <chak@cse.unsw.edu.au>
  * Fix problem with selectors for GADT records with unboxed fields
  Sun Aug  6 20:47:11 EDT 2006  Manuel M T Chakravarty <chak@cse.unsw.edu.au>
    * Fix problem with selectors for GADT records with unboxed fields
    Wed Aug  2 05:37:38 EDT 2006  kevind@bu.edu

Mon Sep 18 17:04:19 EDT 2006  Manuel M T Chakravarty <chak@cse.unsw.edu.au>
  * fix default case filling-in for GADTs
  Sun Aug  6 20:09:06 EDT 2006  Manuel M T Chakravarty <chak@cse.unsw.edu.au>
    * fix default case filling-in for GADTs
    Fri Jul 28 13:19:40 EDT 2006  kevind@bu.edu

Mon Sep 18 17:02:49 EDT 2006  Manuel M T Chakravarty <chak@cse.unsw.edu.au>
  * fix big-lambda eta expansion, add comments
  Sun Aug  6 20:07:36 EDT 2006  Manuel M T Chakravarty <chak@cse.unsw.edu.au>
    * fix big-lambda eta expansion, add comments
    Fri Jul 28 13:16:51 EDT 2006  kevind@bu.edu

Mon Sep 18 14:51:33 EDT 2006  Manuel M T Chakravarty <chak@cse.unsw.edu.au>
  * fix some coercion kind representation things, extend exprIsConApp_maybe to non-vanilla
  Sat Aug  5 21:48:21 EDT 2006  Manuel M T Chakravarty <chak@cse.unsw.edu.au>
    * fix some coercion kind representation things, extend exprIsConApp_maybe to non-vanilla
    Wed Jul 19 08:06:28 EDT 2006  kevind@bu.edu

Mon Sep 18 14:24:27 EDT 2006  Manuel M T Chakravarty <chak@cse.unsw.edu.au>
  * newtype fixes, coercions for non-recursive newtypes now optional
  Sat Aug  5 21:19:58 EDT 2006  Manuel M T Chakravarty <chak@cse.unsw.edu.au>
    * newtype fixes, coercions for non-recursive newtypes now optional
    Fri Jul  7 06:11:48 EDT 2006  kevind@bu.edu

Sun Aug  6 20:09:58 EDT 2006  Manuel M T Chakravarty <chak@cse.unsw.edu.au>
  * fix out-of-scope variable
  Fri Jul 28 13:40:36 EDT 2006  kevind@bu.edu

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.

This refactoring ensures that when mkAtomicArgs adds new bindings,
it does so using completeNonRecX, which adds unfoldings etc.  More
modular, and saves passes too.

(This was important when getting rules to work right.  We want tob
fire a rule as soon as possible, taking into account all inlinings,
else a less-good rule applies.  That's what I found when doing 
stream fusion anyway.)

Regardless, this is an improvement.

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.

Faced with
	case x of y { (a,b) -> rhs }

where x is bound to (c,d), we were generating
	
	let y = (c,d) in rhs

and thenn hoping to get rid of the y binding by CSE or some such.  It's
better simply not to build it in the first place, by generating

	let y = x in rhs

This patch does the job.