1. 15 Sep, 2006 1 commit
    • chak@cse.unsw.edu.au.'s avatar
      Massive patch for the first months work adding System FC to GHC #30 · bb394e57
      chak@cse.unsw.edu.au. authored
      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.
      bb394e57
  2. 09 Aug, 2006 1 commit
  3. 16 Aug, 2006 5 commits
    • simonpj@microsoft.com's avatar
      Get dead-ness right in knownCon · c55001c5
      simonpj@microsoft.com authored
      c55001c5
    • simonpj@microsoft.com's avatar
      Re-factor mkAtomicArgs and completeNonRecX · ad0cc1df
      simonpj@microsoft.com authored
      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.
      ad0cc1df
    • simonpj@microsoft.com's avatar
      Another try at the continuation-swapping stuff · 0e98e80c
      simonpj@microsoft.com authored
      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.
      0e98e80c
    • simonpj@microsoft.com's avatar
      Don't build unnecessary lets in knownCon · eba4dfc2
      simonpj@microsoft.com authored
      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.
      eba4dfc2
    • simonpj@microsoft.com's avatar
      Comments only · 08896210
      simonpj@microsoft.com authored
      08896210
  4. 15 Aug, 2006 1 commit
  5. 14 Aug, 2006 1 commit
    • simonpj@microsoft.com's avatar
      Be more conservative about duplicating continuations · da107045
      simonpj@microsoft.com authored
      Roman found that GHC was duplicating continuations that arose (essentially)
      from uses of 'seq', or strict constructors.  This fixes the problem;
      see the comments mkDupableCont (the Select case with a single alternative).
      
      I'm a little concerned that this may also miss useful case-of-case
      tranformations, so I'd like to know if anyone finds that this patch
      makes performance worse.
      
      To make it a bit more gung-ho, one could check for all the binders
      being dead, before choosing this new, conservative alternative.
      
      da107045
  6. 10 Aug, 2006 3 commits
    • simonpj@microsoft.com's avatar
    • simonpj@microsoft.com's avatar
      Do not repeatedly simplify an argument more than once · c43e5edf
      simonpj@microsoft.com authored
      A very important invariant of the simplifier is that we do not simplify
      an arbitrarily large expression more than once in a single pass. If this
      can happen, then we can get exponential behaviour, when the large expression
      itself has a large sub-expression which is simplified twice, and so on.
      
      GHC has a long-standing bug which allows this repeated simplification to 
      happen.  It shows up when we have a function like this
      
      	f d BIG
      where f's unfolding looks like
      	\x -> case x of (a,b) -> a
      Of course this is v common for overloaded functions.
      
      Before this patch we simplified all the args (d and BIG) before
      deciding to unfold f.  Then we push back the simplified BIG onto the
      continuation stack, inline f, so now we have
      	(case d of (a,b) -> a) BIG
      After we reduce the case a bit, we'll simplify BIG a second time.  And
      that's the problem.
      
      The quick-and-dirty solution is to keep a flag in the ApplyTo continuation
      to say whather the arg has already been simplified.  An alternative would
      be to simplify it when first encountered, but that's a bigger change.
      
      c43e5edf
    • simonpj@microsoft.com's avatar
      Do not call preInlineUnconditionally in simplNonRecX · 3df4d7ee
      simonpj@microsoft.com authored
      This looks to me like a long-standing bug. simplNonRecX was calling
      preInlineUnconditionally, even though it was given an already-simplified
      expression.  Exponential behaviour beckons.
      3df4d7ee
  7. 05 Jun, 2006 1 commit
    • simonpj@microsoft.com's avatar
      Remove InlinePlease and add inline function and RULE · f2dcf256
      simonpj@microsoft.com authored
      For a long time GHC has had some internal mechanism designed to support
      a call-site inline directive, thus
      	inline f xs
      makes f be inlined at the call site even if f is big.
      
      However, the surface syntax seems to have gone, and in any case it
      can be done more neatly using a RULE.
      
      This commit:
        * Removes the InlineCall constructor for Note
          and InlinePlease for SimplCont
      
        * Adds a new known-key Id called 'inline', whose definition in
          GHC.Base is just the identity function
      
        * Adds a built-in RULE in PrelRules that rewrites (inline f) to
          the body of f, if possible
      
        * Adds documentation
      
      NOTE: I have not tested this (aeroplane work).  Give it a try!
      f2dcf256
  8. 22 May, 2006 1 commit
    • simonpj@microsoft.com's avatar
      Inline in a call argument if the caller has RULES · a2c92ccc
      simonpj@microsoft.com authored
      This is an experimental change suggested by Roman.  Consider
      	
      	{-# INLINE f #-}
      	f x y = ...
      
      	....(g (f a b))...
      
      where g has RULES.  Then we'd like to inline f, even though the context of
      the call is otherwise 100% boring -- g is lazy and we know nothing about
      x and y. 
      
      This patch just records in the continuation that f has rules.  And does so
      somewhat recursively...e.g.
      
      	...(g (h (f a b)))...
      
      where g has rules.  
      
      a2c92ccc
  9. 18 May, 2006 1 commit
    • simonpj@microsoft.com's avatar
      Fix a nasty continuation-duplication bug · b812bfb9
      simonpj@microsoft.com authored
      For a long-time mkDupableCont has had a bug that allows it to duplicate
      an arbitrary continuation, which it should not do, of course.
      
      The bug was that in the Select case of mkDupableCont we were calling
      prepareCaseCont, which did not duplicate the continuation if there is
      but a single alternative.  This is quite right in the case of the call
      in rebuildCase, but quite wrong in mkDupableCont.
      
      The bug manifest as follows. In the expression
      	f (case ... of { ..several alts.. })
      (when f is strict), we should transform to
      	f (...transformed arg...)
      The application of f should not be pushed down (see notes with the
      ArgOf case of mkDupableCont.  But that was not happening in an example
      like this (see how the call to f is pushed inwards).
      
      f (a `div` abs (b::Int))
      	--->
          case b_afT of wild_aHa { GHC.Base.I# x_aHc ->
          let {
            $j_sIe :: GHC.Prim.Int# -> GHC.Base.Int
            []
            $j_sIe =
      	\ (ds1_aHr [Nothing OneShot] :: GHC.Prim.Int#) ->
      	  Foo7.f
      	    (case ds1_aHr of ds2_aHq {
      	       __DEFAULT ->
      		 case a_afS of wild1_aHM { GHC.Base.I# x_aHO ->
      		 GHC.Base.I# (GHC.Base.divInt# x_aHO ds2_aHq)
      		 };
      	       0 -> GHC.Err.divZeroError @ GHC.Base.Int
      	     })
          } in 
            case GHC.Prim.>=# x_aHc 0 of wild1_aHe [Dead Nothing] {
      	GHC.Base.False ->
      	  let {
      	    ds1_aHr :: GHC.Prim.Int#
      	    []
      	    ds1_aHr = GHC.Prim.negateInt# x_aHc
      	  } in  $j_sIe ds1_aHr;
      	GHC.Base.True -> $j_sIe x_aHc
            }
          }
      
      b812bfb9
  10. 12 Apr, 2006 1 commit
    • simonpj@microsoft.com's avatar
      Improve pruning of case alternatives to account for GADTs · 2763f56d
      simonpj@microsoft.com authored
      Consider
      
        data T a where
          T1 :: T Int
          T2 :: T Bool
          T3 :: T Char
      
        f :: T Bool -> Int
        f x = case x of
      	  DEFAULT -> ...
      	  T2 -> 3
      
      Here the DEFAULT case covers multiple constructors (T1,T3), but none 
      of them can match a scrutinee of type (T Bool).  So we can prune away
      the default case altogether.
      
      In implementing this, I re-factored this bit of the simplifier, elminiating
      prepareAlts from SimplUtils, and putting all the work into simplAlts in
      Simplify
      
      The proximate cause was a program written by Manuel using PArrays
      2763f56d
  11. 07 Apr, 2006 1 commit
    • Simon Marlow's avatar
      Reorganisation of the source tree · 0065d5ab
      Simon Marlow authored
      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.
      0065d5ab
  12. 01 Mar, 2006 1 commit
  13. 28 Feb, 2006 1 commit
    • simonpj@microsoft.com's avatar
      Simplify the IdInfo before any RHSs · 2317c27b
      simonpj@microsoft.com authored
      	~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
      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.
      2317c27b
  14. 08 Feb, 2006 1 commit
    • simonpj@microsoft.com's avatar
      Do type refinement in TcIface · f5ca07d6
      simonpj@microsoft.com authored
      This commit fixes a bug in 6.4.1 and the HEAD.  Consider this code,
      recorded **in an interface file**
      
          \(x::a) -> case y of 
      	         MkT -> case x of { True -> ... }
      (where MkT forces a=Bool)
      
      In the "case x" we need to know x's type, because we use that
      to find which module to look for "True" in. x's type comes from
      the envt, so we must refine the envt.  
      
      The alternative would be to record more info with an IfaceCase,
      but that would change the interface file format.
      
      (This stuff will go away when we have proper coercions.)
      	
      f5ca07d6
  15. 06 Jan, 2006 1 commit
    • simonmar's avatar
      [project @ 2006-01-06 16:30:17 by simonmar] · 9d7da331
      simonmar authored
      Add support for UTF-8 source files
      
      GHC finally has support for full Unicode in source files.  Source
      files are now assumed to be UTF-8 encoded, and the full range of
      Unicode characters can be used, with classifications recognised using
      the implementation from Data.Char.  This incedentally means that only
      the stage2 compiler will recognise Unicode in source files, because I
      was too lazy to port the unicode classifier code into libcompat.
      
      Additionally, the following synonyms for keywords are now recognised:
      
        forall symbol 	(U+2200)	forall
        right arrow   	(U+2192)	->
        left arrow   		(U+2190)	<-
        horizontal ellipsis 	(U+22EF)	..
      
      there are probably more things we could add here.
      
      This will break some source files if Latin-1 characters are being used.
      In most cases this should result in a UTF-8 decoding error.  Later on
      if we want to support more encodings (perhaps with a pragma to specify
      the encoding), I plan to do it by recoding into UTF-8 before parsing.
      
      Internally, there were some pretty big changes:
      
        - FastStrings are now stored in UTF-8
      
        - Z-encoding has been moved right to the back end.  Previously we
          used to Z-encode every identifier on the way in for simplicity,
          and only decode when we needed to show something to the user.
          Instead, we now keep every string in its UTF-8 encoding, and
          Z-encode right before printing it out.  To avoid Z-encoding the
          same string multiple times, the Z-encoding is cached inside the
          FastString the first time it is requested.
      
          This speeds up the compiler - I've measured some definite
          improvement in parsing at least, and I expect compilations overall
          to be faster too.  It also cleans up a lot of cruft from the
          OccName interface.  Z-encoding is nicely hidden inside the
          Outputable instance for Names & OccNames now.
      
        - StringBuffers are UTF-8 too, and are now represented as
          ForeignPtrs.
      
        - I've put together some test cases, not by any means exhaustive,
          but there are some interesting UTF-8 decoding error cases that
          aren't obvious.  Also, take a look at unicode001.hs for a demo.
      9d7da331
  16. 27 Oct, 2005 1 commit
  17. 17 Oct, 2005 1 commit
  18. 18 Aug, 2005 1 commit
    • simonpj's avatar
      [project @ 2005-08-18 10:25:46 by simonpj] · 70a2631a
      simonpj authored
      1. Remove redundant coerces.  Something that started life as
      	coerce a b <expr>
         might change to
      	coerct Int Int <expr>
         after the types a,b are instantiated.
      
      2. Get rid of the "bad eta expand" message. It can happen entirely legitimately.
         See comments in CoreUtils with eta_expand.
      
      	MERGE TO STABLE
      70a2631a
  19. 12 Aug, 2005 1 commit
    • simonmar's avatar
      [project @ 2005-08-12 10:45:36 by simonmar] · 196ccd21
      simonmar authored
      More inlining changes from SimonPJ & me: The Plan is to avoid relying
      on knowledge of OneOcc occurrences after postInlineUnconditionally, so
      we now attempt to make use of OneOcc as far as possible in in
      pre/postInlineUnconditionally rather than the call site.  Plenty of
      comments in the code with more details.
      
      This change almost always improves performance on nofib; we have one
      program that goes slower, which we'll investigate in due course.
      196ccd21
  20. 10 Aug, 2005 1 commit
  21. 09 Aug, 2005 1 commit
  22. 03 Aug, 2005 1 commit
    • simonmar's avatar
      [project @ 2005-08-03 13:53:35 by simonmar] · cfd9e9b3
      simonmar authored
      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.
      cfd9e9b3
  23. 16 May, 2005 1 commit
  24. 18 Mar, 2005 1 commit
    • simonmar's avatar
      [project @ 2005-03-18 13:37:27 by simonmar] · d1c1b7d0
      simonmar authored
      Flags cleanup.
      
      Basically the purpose of this commit is to move more of the compiler's
      global state into DynFlags, which is moving in the direction we need
      to go for the GHC API which can have multiple active sessions
      supported by a single GHC instance.
      
      Before:
      
      $ grep 'global_var' */*hs | wc -l
           78
      
      After:
      
      $ grep 'global_var' */*hs | wc -l
           27
      
      Well, it's an improvement.  Most of what's left won't really affect
      our ability to host multiple sessions.
      
      Lots of static flags have become dynamic flags (yay!).  Notably lots
      of flags that we used to think of as "driver" flags, like -I and -L,
      are now dynamic.  The most notable static flags left behind are the
      "way" flags, eg. -prof.  It would be nice to fix this, but it isn't
      urgent.
      
      On the way, lots of cleanup has happened.  Everything related to
      static and dynamic flags lives in StaticFlags and DynFlags
      respectively, and they share a common command-line parser library in
      CmdLineParser.  The flags related to modes (--makde, --interactive
      etc.) are now private to the front end: in fact private to Main
      itself, for now.
      d1c1b7d0
  25. 31 Jan, 2005 1 commit
    • simonpj's avatar
      [project @ 2005-01-31 13:25:33 by simonpj] · f25b9225
      simonpj authored
      ---------------------------
      	Types and evaluated-ness in
      	  CoreTidy and CorePrep
      	---------------------------
      
      This commmit fixes two problems.
      
      1.  DataToTagOp requires its argument to be evaluated, otherwise it silently
          gives the wrong answer.  This was not happening because we had
      	case (tag2Enum x) of y -> ...(dataToTag y)...
          and the tag2Enum was being inlined (it's non-speculative), giving
      	...(dataToTag (tag2Enum x))...
      
          Rather than relying on a somewhat-delicate global invariant, CorePrep
          now establishes the invariant that DataToTagOp's argument is evaluated.
          It does so by putting up-to-date is-evaluated information into each
          binder's UnfoldingInfo; not a full unfolding, just the (OtherCon [])
          for evaluated binders.
      
          Then there's a special case for DataToTag where applications are dealt with.
      
          Finally, we make DataToTagOp strict, which it really is.
      
      
      2.  CoreTidy now does GADT refinement as it goes. This is important to ensure that
          each variable occurrence has informative type information, which in turn is
          essential to make exprType work (otherwise it can simply crash).
          [This happened in test gadt/tdpe]
      
          CorePrep has the same problem, but the solution is a little different:
          when looking up in the cloning environment, use the type at the occurrence
          site if we're inside a GADT.  It might be cleaner to use the same story as
          CoreTidy, but then we'd need to keep an in-scope set for type variables.
          No big deal either way.
      f25b9225
  26. 30 Dec, 2004 1 commit
    • simonpj's avatar
      [project @ 2004-12-30 22:14:59 by simonpj] · 7f05f109
      simonpj authored
      Fix to the pre-Xmas simplifier changes, which should make 
      everything work again.  I'd forgotten to attend to this
      corner.  Still not properly tested I fear.
      
      Also remove dead code from SimplEnv, and simplify the remainder (hooray).
      7f05f109
  27. 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
  28. 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
  29. 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
  30. 11 Oct, 2004 1 commit
  31. 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
  32. 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
  33. 26 Sep, 2003 1 commit
  34. 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