1. 24 Dec, 2004 1 commit
    • simonpj's avatar
      [project @ 2004-12-24 16:14:36 by simonpj] · 339d5220
      simonpj authored
      ---------------------------
                Refactor the simplifier
        	---------------------------
      
      Driven by a GADT bug, I have refactored the simpifier, and the way GHC
      treats substitutions.  I hope I have gotten it right.  Be cautious about updating.
      
      * coreSyn/Subst.lhs has gone
      
      * coreSyn/CoreSubst replaces it, except that it's quite a bit simpler
      
      * simplCore/SimplEnv is added, and contains the simplifier-specific substitution
        stuff
      
      Previously Subst was trying to be all things to all men, and that was making
      it Too Complicated.
      
      There may be a little more code now, but it's much easier to understand.
      339d5220
  2. 22 Dec, 2004 1 commit
    • simonpj's avatar
      [project @ 2004-12-22 12:06:13 by simonpj] · d7c402a3
      simonpj authored
      ----------------------------------------
           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.
      d7c402a3
  3. 20 Dec, 2004 1 commit
    • simonpj's avatar
      [project @ 2004-12-20 17:16:24 by simonpj] · c45a0ac5
      simonpj authored
      --------------------------------
      	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!
      c45a0ac5
  4. 11 Oct, 2004 1 commit
  5. 04 Oct, 2004 1 commit
    • simonpj's avatar
      [project @ 2004-10-04 15:51:00 by simonpj] · f469905a
      simonpj authored
      ------------------------------------
      	Part-fix an awkward interaction
      	between case-of-case and GADTs
      	------------------------------------
      
      Consider
      	data T a where
      	  MkT :: a -> b -> T a
      
      	f = /\a. \(w::a).
      	   case (case ...) of
      		  MkT a' b (p::a') (q::b) -> [p,w]
      
      The danger is that we'll make a join point
      
      	j a' p = [p,w]
      
      and that's ill-typed, because (p::a') but (w::a).
      
      Solution so far: don't abstract over a', because the type refinement
      maps [a' -> a] .  Ultimately that won't work when real refinement goes on.
      
      Then we must abstract over any refined free variables.  Hmm.  Maybe we
      could just abstract over *all* free variables, thereby lambda-lifting
      the join point?   We should try this.
      f469905a
  6. 30 Sep, 2004 1 commit
    • simonpj's avatar
      [project @ 2004-09-30 10:35:15 by simonpj] · 23f40f0e
      simonpj authored
      ------------------------------------
      	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).
      23f40f0e
  7. 26 Sep, 2003 1 commit
  8. 23 Sep, 2003 1 commit
    • simonpj's avatar
      [project @ 2003-09-23 15:15:02 by simonpj] · 6c4a98d3
      simonpj authored
      --------------------------
           Move demand-zapping code to where it belongs
      	   --------------------------
      
      A rather subtle point in the simplifier concerns the zapping of demand-info
      when the RHS of a binding is a value.  This used to be tucked away inside
      IdInfo where it was hard to find.  This commit moves the code to Simplify,
      so it occurs where you'd look for it.  Along with copious comments.
      
      See the zapDemandInfo in Simplify.completeLazyBind
      6c4a98d3
  9. 11 Sep, 2003 1 commit
  10. 06 May, 2003 1 commit
  11. 11 Apr, 2003 1 commit
  12. 10 Apr, 2003 2 commits
    • simonpj's avatar
      [project @ 2003-04-10 16:52:26 by simonpj] · 50c98638
      simonpj authored
      Wibble to arity fix
      50c98638
    • simonpj's avatar
      [project @ 2003-04-10 14:44:18 by simonpj] · de0864de
      simonpj authored
      ----------------------------------
             Fix a long-standing eta-reduction bug
      	----------------------------------
      
      Consider the stupid definition
      
      	f = \x -> f x
      
      We were erroneously eta-reducing this to
      
      	f = f
      
      (unsound because they'd be distinguishable by `seq`)
      
      The reason was that simplLazyBind was exposing the arity of
      a recursive function to its own RHS, when all it was really
      trying to do was expose the *rules* for the function.
      
      Easily fixed.   This fixes some
      
      	"Bad eta expand"
      
      warnings.  Good all round.  In particular, fixes rn006.
      de0864de
  13. 20 Feb, 2003 1 commit
    • simonpj's avatar
      [project @ 2003-02-20 18:33:50 by simonpj] · 56b5a8b8
      simonpj authored
      -------------------------------------
            Add Core Notes and the {-# CORE #-} pragma
      	-------------------------------------
      
      This is an idea of Hal Daume's. The key point is that Notes in Core
      are augmented thus:
      
        data Note
          = SCC CostCentre
          | ...
          | CoreNote String     -- NEW
      
      These notes can be injected via a Haskell-source pragma:
      
         f x = ({-# CORE "foo" #-} show) ({-# CORE "bar" #-} x)
      
      This wraps a (Note (CoreNote "foo")) around the 'show' variable,
      and a similar note around the argument to 'show'.
      
      These notes are basically ignored by GHC, but are emitted into
      External Core, where they may convey useful information.
      
      Exactly how code involving these notes is munged by the simplifier
      isn't very well defined.  We'll see how it pans out.  Meanwhile
      the impact on the rest of the compiler is minimal.
      56b5a8b8
  14. 12 Feb, 2003 1 commit
    • simonpj's avatar
      [project @ 2003-02-12 15:01:31 by simonpj] · 42b63073
      simonpj authored
      -------------------------------------
        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.
      42b63073
  15. 19 Nov, 2002 1 commit
    • simonpj's avatar
      [project @ 2002-11-19 15:57:10 by simonpj] · 0316a9e6
      simonpj authored
      -----------------------------------------------
      	Fix a terrible and long-standing strictness bug
      	-----------------------------------------------
      
      		MERGE TO STABLE
      
      Simplify.simplifyArg was floating out lets from a lazy argument.
      Not only is this unprofitable, but it can actually be wrong it
      the floated let has a strict-demand flag on it.  (Simplify.simplLazyBind
      goes to some trouble to check for this case.)
      
      The situation is this
      
      	lazy_fn (let v = <expensive> in str_fn v v)
      
      Here, the strictness analyser may put a 'demanded' flag on
      v, and if is is *then* floated we'll get
      
      	let v* = <expensive>
      	in
      	lazy_fn (str_fn v v)
      
      and then <expensive> will always be evaluated.
      
      This bug has been in the compiler at least a year (since Sept 01), but
      in fact it's quite hard to make a test case for it, because the same
      bug meant that the let was floated out *before* strictness analysis
      giving
      
      	let v = <expensive>
      	in
      	lazy_fn (str_fn v v)
      
      and now v won't get a strict-demand flag.  So it's only if the let
      shows up (by inlining) after strictness analysis but not before.
      0316a9e6
  16. 02 Sep, 2002 1 commit
  17. 29 Apr, 2002 1 commit
    • simonmar's avatar
      [project @ 2002-04-29 14:03:38 by simonmar] · b085ee40
      simonmar authored
      FastString cleanup, stage 1.
      
      The FastString type is no longer a mixture of hashed strings and
      literal strings, it contains hashed strings only with O(1) comparison
      (except for UnicodeStr, but that will also go away in due course).  To
      create a literal instance of FastString, use FSLIT("..").
      
      By far the most common use of the old literal version of FastString
      was in the pattern
      
      	  ptext SLIT("...")
      
      this combination still works, although it doesn't go via FastString
      any more.  The next stage will be to remove the need to use this
      special combination at all, using a RULE.
      
      To convert a FastString into an SDoc, now use 'ftext' instead of
      'ptext'.
      
      I've also removed all the FAST_STRING related macros from HsVersions.h
      except for SLIT and FSLIT, just use the relevant functions from
      FastString instead.
      b085ee40
  18. 24 Apr, 2002 1 commit
  19. 22 Apr, 2002 1 commit
    • simonpj's avatar
      [project @ 2002-04-22 16:06:35 by simonpj] · dbfe93e6
      simonpj authored
      CPR control
      
      1.  Remove -fno-cpr, add -fcpr-off which is a simple static flag
          for switching the new CPR analysis off altogether.
          (The "-fno" machinery is rather complicated.)
      
      2.  Rejig SimplCore a little so that the "old strictness analyser"
          runs both the old strictness analyser and the old CPR analyser,
          which makes it more like the new strictness/CPR analyser.
      
          (How much longer we keep the old strictness/CPR analyser in the
          compiler at all I don't know.  It's just for comparision purposes
          when we write the paper.)
      dbfe93e6
  20. 11 Apr, 2002 1 commit
    • simonpj's avatar
      [project @ 2002-04-11 12:03:29 by simonpj] · a7b95beb
      simonpj authored
      -------------------
      	Mainly derived Read
      	-------------------
      
      This commit is a tangle of several things that somehow got wound up
      together, I'm afraid.
      
      
      The main course
      ~~~~~~~~~~~~~~~
      Replace the derived-Read machinery with Koen's cunning new parser
      combinator library.   The result should be
      	* much smaller code sizes from derived Read
      	* faster execution of derived Read
      
      WARNING: I have not thoroughly tested this stuff; I'd be glad if you did!
      	 All the hard work is done, but there may be a few nits.
      
      The Read class gets two new methods, not exposed
      in the H98 inteface of course:
        class Read a where
          readsPrec    :: Int -> ReadS a
          readList     :: ReadS [a]
          readPrec     :: ReadPrec a		-- NEW
          readListPrec :: ReadPrec [a]	-- NEW
      
      There are the following new libraries:
      
        Text.ParserCombinators.ReadP		Koens combinator parser
        Text.ParserCombinators.ReadPrec	Ditto, but with precedences
      
        Text.Read.Lex				An emasculated lexical analyser
      					that provides the functionality
      					of H98 'lex'
      
      TcGenDeriv is changed to generate code that uses the new libraries.
      The built-in instances of Read (List, Maybe, tuples, etc) use the new
      libraries.
      
      
      Other stuff
      ~~~~~~~~~~~
      1. Some fixes the the plumbing of external-core generation. Sigbjorn
      did most of the work earlier, but this commit completes the renaming and
      typechecking plumbing.
      
      2. Runtime error-generation functions, such as GHC.Err.recSelErr,
      GHC.Err.recUpdErr, etc, now take an Addr#, pointing to a UTF8-encoded
      C string, instead of a Haskell string.  This makes the *calls* to these
      functions easier to generate, and smaller too, which is a good thing.
      
      In particular, it means that MkId.mkRecordSelectorId doesn't need to
      be passed "unpackCStringId", which was GRUESOME; and that in turn means
      that tcTypeAndClassDecls doesn't need to be passed unf_env, which is
      a very worthwhile cleanup.   Win/win situation.
      
      3.  GHC now faithfully translates do-notation using ">>" for statements
      with no binding, just as the report says.  While I was there I tidied
      up HsDo to take a list of Ids instead of 3 (but now 4) separate Ids.
      Saves a bit of code here and there.  Also introduced Inst.newMethodFromName
      to package a common idiom.
      a7b95beb
  21. 05 Apr, 2002 1 commit
  22. 04 Mar, 2002 1 commit
    • simonmar's avatar
      [project @ 2002-03-04 17:01:26 by simonmar] · 0171936c
      simonmar authored
      Binary Interface Files - stage 1
      --------------------------------
      
      This commit changes the default interface file format from text to
      binary, in order to improve compilation performace.
      
      To view an interface file, use 'ghc --show-iface Foo.hi'.
      
      utils/Binary.hs is the basic Binary I/O library, based on the nhc98
      binary I/O library but much stripped-down and working in terms of
      bytes rather than bits, and with some special features for GHC: it
      remembers which Module is being emitted to avoid dumping too many
      qualified names, and it keeps track of a "dictionary" of FastStrings
      so that we don't dump the same FastString more than once into the
      binary file.  I'll make a generic version of this for the libraries at
      some point.
      
      main/BinIface.hs contains most of the Binary instances.  Some
      instances are in the same module as the data type (RdrName, Name,
      OccName in particular).  Most instances were generated using a
      modified version of DrIFT, which I'll commit later.  However, editing
      them by hand isn't hard (certainly easier than modifying
      ParseIface.y).
      
      The first thing in a binary interface is the interface version, so
      nice error messages will be generated if the binary format changes and
      you still have old interfaces lying around.  The version also now
      includes the "way" as an extra sanity check.
      
      Other changes
      -------------
      
      I don't like the way FastStrings contain both hashed strings (with
      O(1) comparison) and literal C strings (with O(n) comparison).  So as
      a first step to separating these I made serveral "literal" type
      strings into hashed strings.  SLIT() still generates a literal, and
      now FSLIT() generates a hashed string.  With DEBUG on, you'll get a
      warning if you try to compare any SLIT()s with anything, and the
      compiler will fall over if you try to dump any literal C strings into
      an interface file (usually indicating a use of SLIT() which should be
      FSLIT()).
      
      mkSysLocal no longer re-encodes its FastString argument each time it
      is called.
      
      I also fixed the -pgm options so that the argument can now optionally
      be separted from the option.
      
      Bugfix: PrelNames declared Names for several comparison primops, eg.
      eqCharName, eqIntName etc. but these had different uniques from the
      real primop names.  I've moved these to PrimOps and defined them using
      mkPrimOpIdName instead, and deleted some for which we don't have real
      primops (Manuel: please check that things still work for you after
      this change).
      0171936c
  23. 15 Feb, 2002 1 commit
    • simonpj's avatar
      [project @ 2002-02-15 09:32:18 by simonpj] · 87a229b8
      simonpj authored
      -------------------------------------------------
      	Fix an interesting case-alternatives filtering bug
      	-------------------------------------------------
      
      This bug, shown up by Krasimir's ObjectIO suite, caused the
      simplifier to encounter a case expression like
      	case x of { x:xs -> True; [] -> False }
      in a context where x could not possibly be either a (:) or []!
      Case expressions in the enclosing scope dealt with it...
      So the alternative-filtering removed all the alternatives, leaving
      a case expression with no branches, which GHC didn't like one little
      bit.
      
      The actual bug was elsewhere; it was because we should sometimes
      filter out the DEFAULT alternative, and we weren't doing that.
      To fix it, I pulled the alternative-filtering code out of Simplify
      and put it in SimplUtils.prepareAlts.  It's nice now.
      87a229b8
  24. 14 Dec, 2001 1 commit
    • simonpj's avatar
      [project @ 2001-12-14 17:24:03 by simonpj] · 5f087cf4
      simonpj authored
      -------------------------
      	Performance tuning things
      	-------------------------
      
      I did some nofib tests, and fixed a number of performance problems.
      
      1.  Things were getting floated to top level, and that prevented
      some useful fusion happening.
      	y = build g
      	x = foldr k z y
      
      Fixed by arranging that we only get really keen on floating to top
      level in the second run of the let-float-out pass.
      
      
      2.  Some fettling up on the let-floater itself.  It had some parameters
      that weren't even being used!  And it was stupidly floating things out
      of a one-shot lambda, and the float-in pass didn't float them back in.
      I think I fixed both of these problems.
      
      
      3.  The eta-reducer was not eta-reducing (/\a -> g a) to g.  In general
      it has to be a bit careful because "seq" means that (\x -> g x) is
      not in general the same as g ---- but it *is* the same for a type lambda.
      
      This turned out to be important in rule matching, where the foldr/build
      rule was not firing because the LHS of the rule looked like
      	foldr k z (/\ a -> g a) = ...
      which never matched!  Result, no fusion to speak of!
      
      
      4.  The simplifier was a bit too gung ho about inlining used-once
      things bound to constructor args.  The comment is with Simplify.simplNonRecX.
      5f087cf4
  25. 06 Dec, 2001 1 commit
  26. 05 Dec, 2001 2 commits
  27. 19 Nov, 2001 2 commits
    • simonpj's avatar
      [project @ 2001-11-19 16:34:12 by simonpj] · 53ce311e
      simonpj authored
      Tidy up imports
      53ce311e
    • simonpj's avatar
      [project @ 2001-11-19 14:23:52 by simonpj] · d8af6b8c
      simonpj authored
      --------------------------------------
      	Yet another cut at the DmdAnal domains
      	--------------------------------------
      
      This version of the domain for demand analysis was developed
      in discussion with Peter Sestoft, so I think it might at last
      be more or less right!
      
      Our idea is mentally to separate
      	strictness analysis
      from
      	absence and boxity analysis
      
      Then we combine them back into a single domain.  The latter
      is all you see in the compiler (the Demand type, as before)
      but we understand it better now.
      d8af6b8c
  28. 16 Nov, 2001 1 commit
    • simonpj's avatar
      [project @ 2001-11-16 15:42:26 by simonpj] · 772ffb22
      simonpj authored
      ---------------------------------------
      	Add continuation splitting to Simplify
      	---------------------------------------
      
      When the simplifier finds a 'case', it calls mkDupableAlt
      to make the "continuation" (that is, the context of the
      case expression) duplicatable, so that it can push it into
      the case branches.  This is crucial for the case-of-case
      transformation.
      
      But it turns out that it's a bad idea to do that when
      the context is "I'm the argument of a strict function".  Consider
      
      	f (case x of { True -> False; False -> True }) arg2
      
      where f is a strict function.  Then we *could* (and were)
      transforming to
      
      	let $j a = f a arg2
      	in
      	case x of { True -> $j False; False -> $j True }
      
      But this is in general a terribly bad thing to do.
      See the example in comments with Simplify.mkDupableCont.
      772ffb22
  29. 01 Nov, 2001 2 commits
    • simonpj's avatar
      [project @ 2001-11-01 13:20:05 by simonpj] · 51666a19
      simonpj authored
      ---------------------------------------
      	Fix a unboxed-binding bug in SpecConstr
      	---------------------------------------
      
      	[HEAD only]
      
      This fixes a rather obscure bug in the constructor
      specialiser discovered by Ralf Hinze.  It was
      generating a specialised version of the function
      with no arguments --- and the function returned an
      unboxed type.
      
      Solution: same as for worker-wrapper; add a dummy
      argument.
      
      Several files are affected because I added
      CoreUtils.mkPiTypes, as a useful helper function.
      51666a19
    • simonpj's avatar
      [project @ 2001-11-01 10:33:58 by simonpj] · 883d5ca9
      simonpj authored
      ----------------------------------
      	Fix a bug in Simplify.mkDupableAlt
      	----------------------------------
      
      	[This is the HEAD commit; I've fixed
      	 the branch separately.]
      
      This fixes a funResultTy panic that Koen encountered.
      
      The reason was that the simplifier was doing a
      case-of-case where the result had a polymorphic type.
      This in turn showed up because of a newtype (now
      transparent) with a forall inside it.
      
      The fix is very easy; can't think how I got it wrong
      in the first place.
      883d5ca9
  30. 24 Oct, 2001 1 commit
  31. 22 Oct, 2001 1 commit
  32. 18 Oct, 2001 3 commits
    • simonpj's avatar
      [project @ 2001-10-18 16:29:12 by simonpj] · 685e04e4
      simonpj authored
      ----------------------------------------------
      	The CoreTidy/CorePrep/CoreToStg saga continues
      	[actually, this commit mostly completes the job]
      	----------------------------------------------
      
      			DO NOT MERGE!
      
      * CorePrep injects implicit bindings, not the type checker,
        nor CgConTbls.   (This way, all the code generators see
        them, so no need to fiddle with the byte code generator.)
      
        As a result, all bindings in the module are for LocalIds,
        at least until CoreTidy.   This is a Big Win.
      
        Hence remove nasty isImplicitId test in update_bndr in
        SimplCore and DmdAnal
      
      * hasNoBinding is no longer true of a dataConId (worker).
        There's an implicit curried binding for it.
      
      * Remove yukky test in exprIsTrivial that did not regard
        a hasNoBinding Id as trivial; similarly in SimplUtils.tryEtaReduce
      
      * In CoreTidy, get the names to avoid from the type env.
        That way it includes implicit bindings too.
      
      * CoreTidy set the Arity of a top-level Id permanently;
        it's up to the rest of the compiler to respect it.
        Notably, CorePrep uses etaExpand to make the manifest arity
        match the claimed arity.
      
      * As a result, nuke CgArity, so that CgInfo now contains only
        CafInfo.  The CafInfo is knot-tied as before.
      
      
      Other things
      
      * In Simplify.simplLazyBind, be a bit keener to float bindings
        out if it's a top-level binding.
      685e04e4
    • simonpj's avatar
      [project @ 2001-10-18 10:03:58 by simonpj] · d8d54df6
      simonpj authored
      Comments only
      d8d54df6
    • simonpj's avatar
      [project @ 2001-10-18 08:22:06 by simonpj] · 4c6ea37b
      simonpj authored
      Wibble to case fiddling; dont merge
      4c6ea37b
  33. 17 Oct, 2001 1 commit
  34. 04 Oct, 2001 1 commit