Major overhaul of the Simplifier
authorsimonpj@microsoft.com <unknown>
Wed, 1 Nov 2006 16:43:29 +0000 (16:43 +0000)
committersimonpj@microsoft.com <unknown>
Wed, 1 Nov 2006 16:43:29 +0000 (16:43 +0000)
commit7a327c1297615a9498e7117a0017b09ff2458d53
treecbcdf9ea0463b2ab73f4041d5145bdafd1d1c4ee
parent326d5e5a5f9a52ea38917041d7b5f00cc8e21191
Major overhaul of the Simplifier

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".
compiler/coreSyn/CoreSyn.lhs
compiler/prelude/PrelRules.lhs
compiler/simplCore/OccurAnal.lhs
compiler/simplCore/SimplEnv.lhs
compiler/simplCore/SimplUtils.lhs
compiler/simplCore/Simplify.lhs
compiler/specialise/Rules.lhs
compiler/specialise/SpecConstr.lhs
compiler/typecheck/TcGadt.lhs