1. 28 Jan, 2013 1 commit
    • Simon Peyton Jones's avatar
      Pure refactoring · f1fa6eb2
      Simon Peyton Jones authored
      * Move tidyType and friends from TcType to TypeRep
        (It was always wrong to have it in TcType.)
      
      * Move mkCoAxBranch and friends from FamInst to Coercion
      
      * Move pprCoAxBranch and friends from FamInstEnv to Coercion
      
      No change in functionality, though there might be a little
      wibble in error message output, because I combined two different
      functions both called pprCoAxBranch!
      f1fa6eb2
  2. 17 Jan, 2013 1 commit
    • Simon Peyton Jones's avatar
      Major patch to implement the new Demand Analyser · 0831a12e
      Simon Peyton Jones authored
      This patch is the result of Ilya Sergey's internship at MSR.  It
      constitutes a thorough overhaul and simplification of the demand
      analyser.  It makes a solid foundation on which we can now build.
      Main changes are
      
      * Instead of having one combined type for Demand, a Demand is
         now a pair (JointDmd) of
            - a StrDmd and
            - an AbsDmd.
         This allows strictness and absence to be though about quite
         orthogonally, and greatly reduces brain melt-down.
      
      * Similarly in the DmdResult type, it's a pair of
           - a PureResult (indicating only divergence/non-divergence)
           - a CPRResult (which deals only with the CPR property
      
      * In IdInfo, the
          strictnessInfo field contains a StrictSig, not a Maybe StrictSig
          demandInfo     field contains a Demand, not a Maybe Demand
        We don't need Nothing (to indicate no strictness/demand info)
        any more; topSig/topDmd will do.
      
      * Remove "boxity" analysis entirely.  This was an attempt to
        avoid "reboxing", but it added complexity, is extremely
        ad-hoc, and makes very little difference in practice.
      
      * Remove the "unboxing strategy" computation. This was an an
        attempt to ensure that a worker didn't get zillions of
        arguments by unboxing big tuples.  But in fact removing it
        DRAMATICALLY reduces allocation in an inner loop of the
        I/O library (where the threshold argument-count had been
        set just too low).  It's exceptional to have a zillion arguments
        and I don't think it's worth the complexity, especially since
        it turned out to have a serious performance hit.
      
      * Remove quite a bit of ad-hoc cruft
      
      * Move worthSplittingFun, worthSplittingThunk from WorkWrap to
        Demand. This allows JointDmd to be fully abstract, examined
        only inside Demand.
      
      Everything else really follows from these changes.
      
      All of this is really just refactoring, so we don't expect
      big performance changes, but acutally the numbers look quite
      good.  Here is a full nofib run with some highlights identified:
      
              Program           Size    Allocs   Runtime   Elapsed  TotalMem
      --------------------------------------------------------------------------------
               expert          -2.6%    -15.5%      0.00      0.00     +0.0%
                fluid          -2.4%     -7.1%      0.01      0.01     +0.0%
                   gg          -2.5%    -28.9%      0.02      0.02    -33.3%
            integrate          -2.6%     +3.2%     +2.6%     +2.6%     +0.0%
              mandel2          -2.6%     +4.2%      0.01      0.01     +0.0%
             nucleic2          -2.0%    -16.3%      0.11      0.11     +0.0%
                 para          -2.6%    -20.0%    -11.8%    -11.7%     +0.0%
               parser          -2.5%    -17.9%      0.05      0.05     +0.0%
               prolog          -2.6%    -13.0%      0.00      0.00     +0.0%
               puzzle          -2.6%     +2.2%     +0.8%     +0.8%     +0.0%
              sorting          -2.6%    -35.9%      0.00      0.00     +0.0%
             treejoin          -2.6%    -52.2%     -9.8%     -9.9%     +0.0%
      --------------------------------------------------------------------------------
                  Min          -2.7%    -52.2%    -11.8%    -11.7%    -33.3%
                  Max          -1.8%     +4.2%    +10.5%    +10.5%     +7.7%
       Geometric Mean          -2.5%     -2.8%     -0.4%     -0.5%     -0.4%
      
      Things to note
      
      * Binary sizes are smaller. I don't know why, but it's good.
      
      * Allocation is sometiemes a *lot* smaller. I believe that all the big numbers
        (I checked treejoin, gg, sorting) arise from one place, namely a function
        GHC.IO.Encoding.UTF8.utf8_decode, which is strict in two Buffers both of
        which have several arugments.  Not w/w'ing both arguments (which is what
        we did before) has a big effect.  So the big win in actually somewhat
        accidental, gained by removing the "unboxing strategy" code.
      
      * A couple of benchmarks allocate slightly more.  This turns out
        to be due to reboxing (integrate).  But the biggest increase is
        mandel2, and *that* turned out also to be a somewhat accidental
        loss of CSE, and pointed the way to doing better CSE: see Trac
        #7596.
      
      * Runtimes are never very reliable, but seem to improve very slightly.
      
      All in all, a good piece of work.  Thank you Ilya!
      0831a12e
  3. 27 Jun, 2012 1 commit
    • Simon Peyton Jones's avatar
      Add silent superclass parameters (again) · aa1e0976
      Simon Peyton Jones authored
      Silent superclass parameters solve the problem that
      the superclasses of a dicionary construction can easily
      turn out to be (wrongly) bottom.  The problem and solution
      are described in
         Note [Silent superclass arguments] in TcInstDcls
      
      I first implemented this fix (with Dimitrios) in Dec 2010, but removed
      it again in Jun 2011 becuase we thought it wasn't necessary any
      more. (The reason we thought it wasn't necessary is that we'd stopped
      generating derived superclass constraints for *wanteds*.  But we were
      wrong; that didn't solve the superclass-loop problem.)
      
      So we have to re-implement it.  It's not hard.  Main features:
      
        * The IdDetails for a DFunId says how many silent arguments it has
      
        * A DFunUnfolding describes which dictionary args are
          just parameters (DFunLamArg) and which are a function to apply
          to the parameters (DFunPolyArg).  This adds the DFunArg type
          to CoreSyn
      
        * Consequential changes to IfaceSyn.  (Binary hi file format changes
          slightly.)
      
        * TcInstDcls changes to generate the right dfuns
      
        * CoreSubst.exprIsConApp_maybe handles the new DFunUnfolding
      
      The thing taht is *not* done yet is to alter the vectoriser to
      pass the relevant extra argument when building a PA dictionary.
      aa1e0976
  4. 04 Nov, 2011 1 commit
  5. 02 Nov, 2011 1 commit
    • Simon Marlow's avatar
      Overhaul of infrastructure for profiling, coverage (HPC) and breakpoints · 7bb0447d
      Simon Marlow authored
      User visible changes
      ====================
      
      Profilng
      --------
      
      Flags renamed (the old ones are still accepted for now):
      
        OLD            NEW
        ---------      ------------
        -auto-all      -fprof-auto
        -auto          -fprof-exported
        -caf-all       -fprof-cafs
      
      New flags:
      
        -fprof-auto              Annotates all bindings (not just top-level
                                 ones) with SCCs
      
        -fprof-top               Annotates just top-level bindings with SCCs
      
        -fprof-exported          Annotates just exported bindings with SCCs
      
        -fprof-no-count-entries  Do not maintain entry counts when profiling
                                 (can make profiled code go faster; useful with
                                 heap profiling where entry counts are not used)
      
      Cost-centre stacks have a new semantics, which should in most cases
      result in more useful and intuitive profiles.  If you find this not to
      be the case, please let me know.  This is the area where I have been
      experimenting most, and the current solution is probably not the
      final version, however it does address all the outstanding bugs and
      seems to be better than GHC 7.2.
      
      Stack traces
      ------------
      
      +RTS -xc now gives more information.  If the exception originates from
      a CAF (as is common, because GHC tends to lift exceptions out to the
      top-level), then the RTS walks up the stack and reports the stack in
      the enclosing update frame(s).
      
      Result: +RTS -xc is much more useful now - but you still have to
      compile for profiling to get it.  I've played around a little with
      adding 'head []' to GHC itself, and +RTS -xc does pinpoint the problem
      quite accurately.
      
      I plan to add more facilities for stack tracing (e.g. in GHCi) in the
      future.
      
      Coverage (HPC)
      --------------
      
       * derived instances are now coloured yellow if they weren't used
       * likewise record field names
       * entry counts are more accurate (hpc --fun-entry-count)
       * tab width is now correct (markup was previously off in source with
         tabs)
      
      Internal changes
      ================
      
      In Core, the Note constructor has been replaced by
      
              Tick (Tickish b) (Expr b)
      
      which is used to represent all the kinds of source annotation we
      support: profiling SCCs, HPC ticks, and GHCi breakpoints.
      
      Depending on the properties of the Tickish, different transformations
      apply to Tick.  See CoreUtils.mkTick for details.
      
      Tickets
      =======
      
      This commit closes the following tickets, test cases to follow:
      
        - Close #2552: not a bug, but the behaviour is now more intuitive
          (test is T2552)
      
        - Close #680 (test is T680)
      
        - Close #1531 (test is result001)
      
        - Close #949 (test is T949)
      
        - Close #2466: test case has bitrotted (doesn't compile against current
          version of vector-space package)
      7bb0447d
  6. 23 Jun, 2011 1 commit
  7. 19 Apr, 2011 1 commit
    • Simon Peyton Jones's avatar
      This BIG PATCH contains most of the work for the New Coercion Representation · fdf86568
      Simon Peyton Jones authored
      See the paper "Practical aspects of evidence based compilation in System FC"
      
      * Coercion becomes a data type, distinct from Type
      
      * Coercions become value-level things, rather than type-level things,
        (although the value is zero bits wide, like the State token)
        A consequence is that a coerion abstraction increases the arity by 1
        (just like a dictionary abstraction)
      
      * There is a new constructor in CoreExpr, namely Coercion, to inject
        coercions into terms
      fdf86568
  8. 13 Dec, 2010 1 commit
    • simonpj@microsoft.com's avatar
      Fix recursive superclasses (again). Fixes Trac #4809. · a3bab050
      simonpj@microsoft.com authored
      This patch finally deals with the super-delicate question of
      superclases in possibly-recursive dictionaries.  The key idea
      is the DFun Superclass Invariant (see TcInstDcls):
      
           In the body of a DFun, every superclass argument to the
           returned dictionary is
             either   * one of the arguments of the DFun,
             or       * constant, bound at top level
      
      To establish the invariant, we add new "silent" superclass
      argument(s) to each dfun, so that the dfun does not do superclass
      selection internally.  There's a bit of hoo-ha to make sure that
      we don't print those silent arguments in error messages; a knock
      on effect was a change in interface-file format.
      
      A second change is that instead of the complex and fragile
      "self dictionary binding" in TcInstDcls and TcClassDcl,
      using the same mechanism for existential pattern bindings.
      See Note [Subtle interaction of recursion and overlap] in TcInstDcls
      and Note [Binding when looking up instances] in InstEnv.
      
      Main notes are here:
      
        * Note [Silent Superclass Arguments] in TcInstDcls,
          including the DFun Superclass Invariant
      
      Main code changes are:
      
        * The code for MkId.mkDictFunId and mkDictFunTy
      
        * DFunUnfoldings get a little more complicated;
          their arguments are a new type DFunArg (in CoreSyn)
      
        * No "self" argument in tcInstanceMethod
        * No special tcSimplifySuperClasss
        * No "dependents" argument to EvDFunApp
      
      IMPORTANT
         It turns out that it's quite tricky to generate the right
         DFunUnfolding for a specialised dfun, when you use SPECIALISE
         INSTANCE.  For now I've just commented it out (in DsBinds) but
         that'll lose some optimisation, and I need to get back to
         this.
      a3bab050
  9. 25 Oct, 2010 1 commit
  10. 13 Sep, 2010 1 commit
  11. 19 Nov, 2009 1 commit
    • simonpj@microsoft.com's avatar
      Remove the (very) old strictness analyser · 2662dbc5
      simonpj@microsoft.com authored
      I finally got tired of the #ifdef OLD_STRICTNESS stuff.  I had been
      keeping it around in the hope of doing old-to-new comparisions, but
      have failed to do so for many years, so I don't think it's going to
      happen.  This patch deletes the clutter.
      2662dbc5
  12. 29 Oct, 2009 1 commit
    • simonpj@microsoft.com's avatar
      The Big INLINE Patch: totally reorganise way that INLINE pragmas work · 72462499
      simonpj@microsoft.com authored
      This patch has been a long time in gestation and has, as a
      result, accumulated some extra bits and bobs that are only
      loosely related.  I separated the bits that are easy to split
      off, but the rest comes as one big patch, I'm afraid.
      
      Note that:
       * It comes together with a patch to the 'base' library
       * Interface file formats change slightly, so you need to
         recompile all libraries
      
      The patch is mainly giant tidy-up, driven in part by the
      particular stresses of the Data Parallel Haskell project. I don't
      expect a big performance win for random programs.  Still, here are the
      nofib results, relative to the state of affairs without the patch
      
              Program           Size    Allocs   Runtime   Elapsed
      --------------------------------------------------------------------------------
                  Min         -12.7%    -14.5%    -17.5%    -17.8%
                  Max          +4.7%    +10.9%     +9.1%     +8.4%
       Geometric Mean          +0.9%     -0.1%     -5.6%     -7.3%
      
      The +10.9% allocation outlier is rewrite, which happens to have a
      very delicate optimisation opportunity involving an interaction
      of CSE and inlining (see nofib/Simon-nofib-notes). The fact that
      the 'before' case found the optimisation is somewhat accidental.
      Runtimes seem to go down, but I never kno wwhether to really trust
      this number.  Binary sizes wobble a bit, but nothing drastic.
      
      
      The Main Ideas are as follows.
      
      InlineRules
      ~~~~~~~~~~~
      When you say 
            {-# INLINE f #-}
            f x = <rhs>
      you intend that calls (f e) are replaced by <rhs>[e/x] So we
      should capture (\x.<rhs>) in the Unfolding of 'f', and never meddle
      with it.  Meanwhile, we can optimise <rhs> to our heart's content,
      leaving the original unfolding intact in Unfolding of 'f'.
      
      So the representation of an Unfolding has changed quite a bit
      (see CoreSyn).  An INLINE pragma gives rise to an InlineRule 
      unfolding.  
      
      Moreover, it's only used when 'f' is applied to the
      specified number of arguments; that is, the number of argument on 
      the LHS of the '=' sign in the original source definition. 
      For example, (.) is now defined in the libraries like this
         {-# INLINE (.) #-}
         (.) f g = \x -> f (g x)
      so that it'll inline when applied to two arguments. If 'x' appeared
      on the left, thus
         (.) f g x = f (g x)
      it'd only inline when applied to three arguments.  This slightly-experimental
      change was requested by Roman, but it seems to make sense.
      
      Other associated changes
      
      * Moving the deck chairs in DsBinds, which processes the INLINE pragmas
      
      * In the old system an INLINE pragma made the RHS look like
         (Note InlineMe <rhs>)
        The Note switched off optimisation in <rhs>.  But it was quite
        fragile in corner cases. The new system is more robust, I believe.
        In any case, the InlineMe note has disappeared 
      
      * The workerInfo of an Id has also been combined into its Unfolding,
        so it's no longer a separate field of the IdInfo.
      
      * Many changes in CoreUnfold, esp in callSiteInline, which is the critical
        function that decides which function to inline.  Lots of comments added!
      
      * exprIsConApp_maybe has moved to CoreUnfold, since it's so strongly
        associated with "does this expression unfold to a constructor application".
        It can now do some limited beta reduction too, which Roman found 
        was an important.
      
      Instance declarations
      ~~~~~~~~~~~~~~~~~~~~~
      It's always been tricky to get the dfuns generated from instance
      declarations to work out well.  This is particularly important in 
      the Data Parallel Haskell project, and I'm now on my fourth attempt,
      more or less.
      
      There is a detailed description in TcInstDcls, particularly in
      Note [How instance declarations are translated].   Roughly speaking
      we now generate a top-level helper function for every method definition
      in an instance declaration, so that the dfun takes a particularly
      stylised form:
        dfun a d1 d2 = MkD (op1 a d1 d2) (op2 a d1 d2) ...etc...
      
      In fact, it's *so* stylised that we never need to unfold a dfun.
      Instead ClassOps have a special rewrite rule that allows us to
      short-cut dictionary selection.  Suppose dfun :: Ord a -> Ord [a]
                                                  d :: Ord a
      Then   
          compare (dfun a d)  -->   compare_list a d 
      in one rewrite, without first inlining the 'compare' selector
      and the body of the dfun.
      
      To support this
      a) ClassOps have a BuiltInRule (see MkId.dictSelRule)
      b) DFuns have a special form of unfolding (CoreSyn.DFunUnfolding)
         which is exploited in CoreUnfold.exprIsConApp_maybe
      
      Implmenting all this required a root-and-branch rework of TcInstDcls
      and bits of TcClassDcl.
      
      
      Default methods
      ~~~~~~~~~~~~~~~
      If you give an INLINE pragma to a default method, it should be just
      as if you'd written out that code in each instance declaration, including
      the INLINE pragma.  I think that it now *is* so.  As a result, library
      code can be simpler; less duplication.
      
      
      The CONLIKE pragma
      ~~~~~~~~~~~~~~~~~~
      In the DPH project, Roman found cases where he had
      
         p n k = let x = replicate n k
                 in ...(f x)...(g x)....
      
         {-# RULE f (replicate x) = f_rep x #-}
      
      Normally the RULE would not fire, because doing so involves 
      (in effect) duplicating the redex (replicate n k).  A new
      experimental modifier to the INLINE pragma, {-# INLINE CONLIKE
      replicate #-}, allows you to tell GHC to be prepared to duplicate
      a call of this function if it allows a RULE to fire.
      
      See Note [CONLIKE pragma] in BasicTypes
      
      
      Join points
      ~~~~~~~~~~~
      See Note [Case binders and join points] in Simplify
      
      
      Other refactoring
      ~~~~~~~~~~~~~~~~~
      * I moved endPass from CoreLint to CoreMonad, with associated jigglings
      
      * Better pretty-printing of Core
      
      * The top-level RULES (ones that are not rules for locally-defined things)
        are now substituted on every simplifier iteration.  I'm not sure how
        we got away without doing this before.  This entails a bit more plumbing
        in SimplCore.
      
      * The necessary stuff to serialise and deserialise the new
        info across interface files.
      
      * Something about bottoming floats in SetLevels
            Note [Bottoming floats]
      
      * substUnfolding has moved from SimplEnv to CoreSubs, where it belongs
      
      
      --------------------------------------------------------------------------------
              Program           Size    Allocs   Runtime   Elapsed
      --------------------------------------------------------------------------------
                 anna          +2.4%     -0.5%      0.16      0.17
                 ansi          +2.6%     -0.1%      0.00      0.00
                 atom          -3.8%     -0.0%     -1.0%     -2.5%
               awards          +3.0%     +0.7%      0.00      0.00
               banner          +3.3%     -0.0%      0.00      0.00
           bernouilli          +2.7%     +0.0%     -4.6%     -6.9%
                boyer          +2.6%     +0.0%      0.06      0.07
               boyer2          +4.4%     +0.2%      0.01      0.01
                 bspt          +3.2%     +9.6%      0.02      0.02
            cacheprof          +1.4%     -1.0%    -12.2%    -13.6%
             calendar          +2.7%     -1.7%      0.00      0.00
             cichelli          +3.7%     -0.0%      0.13      0.14
              circsim          +3.3%     +0.0%     -2.3%     -9.9%
             clausify          +2.7%     +0.0%      0.05      0.06
        comp_lab_zift          +2.6%     -0.3%     -7.2%     -7.9%
             compress          +3.3%     +0.0%     -8.5%     -9.6%
            compress2          +3.6%     +0.0%    -15.1%    -17.8%
          constraints          +2.7%     -0.6%    -10.0%    -10.7%
         cryptarithm1          +4.5%     +0.0%     -4.7%     -5.7%
         cryptarithm2          +4.3%    -14.5%      0.02      0.02
                  cse          +4.4%     -0.0%      0.00      0.00
                eliza          +2.8%     -0.1%      0.00      0.00
                event          +2.6%     -0.0%     -4.9%     -4.4%
               exp3_8          +2.8%     +0.0%     -4.5%     -9.5%
               expert          +2.7%     +0.3%      0.00      0.00
                  fem          -2.0%     +0.6%      0.04      0.04
                  fft          -6.0%     +1.8%      0.05      0.06
                 fft2          -4.8%     +2.7%      0.13      0.14
             fibheaps          +2.6%     -0.6%      0.05      0.05
                 fish          +4.1%     +0.0%      0.03      0.04
                fluid          -2.1%     -0.2%      0.01      0.01
               fulsom          -4.8%     +9.2%     +9.1%     +8.4%
               gamteb          -7.1%     -1.3%      0.10      0.11
                  gcd          +2.7%     +0.0%      0.05      0.05
          gen_regexps          +3.9%     -0.0%      0.00      0.00
               genfft          +2.7%     -0.1%      0.05      0.06
                   gg          -2.7%     -0.1%      0.02      0.02
                 grep          +3.2%     -0.0%      0.00      0.00
               hidden          -0.5%     +0.0%    -11.9%    -13.3%
                  hpg          -3.0%     -1.8%     +0.0%     -2.4%
                  ida          +2.6%     -1.2%      0.17     -9.0%
                infer          +1.7%     -0.8%      0.08      0.09
              integer          +2.5%     -0.0%     -2.6%     -2.2%
            integrate          -5.0%     +0.0%     -1.3%     -2.9%
              knights          +4.3%     -1.5%      0.01      0.01
                 lcss          +2.5%     -0.1%     -7.5%     -9.4%
                 life          +4.2%     +0.0%     -3.1%     -3.3%
                 lift          +2.4%     -3.2%      0.00      0.00
            listcompr          +4.0%     -1.6%      0.16      0.17
             listcopy          +4.0%     -1.4%      0.17      0.18
             maillist          +4.1%     +0.1%      0.09      0.14
               mandel          +2.9%     +0.0%      0.11      0.12
              mandel2          +4.7%     +0.0%      0.01      0.01
              minimax          +3.8%     -0.0%      0.00      0.00
              mkhprog          +3.2%     -4.2%      0.00      0.00
           multiplier          +2.5%     -0.4%     +0.7%     -1.3%
             nucleic2          -9.3%     +0.0%      0.10      0.10
                 para          +2.9%     +0.1%     -0.7%     -1.2%
            paraffins         -10.4%     +0.0%      0.20     -1.9%
               parser          +3.1%     -0.0%      0.05      0.05
              parstof          +1.9%     -0.0%      0.00      0.01
                  pic          -2.8%     -0.8%      0.01      0.02
                power          +2.1%     +0.1%     -8.5%     -9.0%
               pretty         -12.7%     +0.1%      0.00      0.00
               primes          +2.8%     +0.0%      0.11      0.11
            primetest          +2.5%     -0.0%     -2.1%     -3.1%
               prolog          +3.2%     -7.2%      0.00      0.00
               puzzle          +4.1%     +0.0%     -3.5%     -8.0%
               queens          +2.8%     +0.0%      0.03      0.03
              reptile          +2.2%     -2.2%      0.02      0.02
              rewrite          +3.1%    +10.9%      0.03      0.03
                 rfib          -5.2%     +0.2%      0.03      0.03
                  rsa          +2.6%     +0.0%      0.05      0.06
                  scc          +4.6%     +0.4%      0.00      0.00
                sched          +2.7%     +0.1%      0.03      0.03
                  scs          -2.6%     -0.9%     -9.6%    -11.6%
               simple          -4.0%     +0.4%    -14.6%    -14.9%
                solid          -5.6%     -0.6%     -9.3%    -14.3%
              sorting          +3.8%     +0.0%      0.00      0.00
               sphere          -3.6%     +8.5%      0.15      0.16
               symalg          -1.3%     +0.2%      0.03      0.03
                  tak          +2.7%     +0.0%      0.02      0.02
            transform          +2.0%     -2.9%     -8.0%     -8.8%
             treejoin          +3.1%     +0.0%    -17.5%    -17.8%
            typecheck          +2.9%     -0.3%     -4.6%     -6.6%
              veritas          +3.9%     -0.3%      0.00      0.00
                 wang          -6.2%     +0.0%      0.18     -9.8%
            wave4main         -10.3%     +2.6%     -2.1%     -2.3%
         wheel-sieve1          +2.7%     -0.0%     +0.3%     -0.6%
         wheel-sieve2          +2.7%     +0.0%     -3.7%     -7.5%
                 x2n1          -4.1%     +0.1%      0.03      0.04
      --------------------------------------------------------------------------------
                  Min         -12.7%    -14.5%    -17.5%    -17.8%
                  Max          +4.7%    +10.9%     +9.1%     +8.4%
       Geometric Mean          +0.9%     -0.1%     -5.6%     -7.3%
      72462499
  13. 07 Jul, 2009 1 commit
  14. 13 Jan, 2009 1 commit
    • simonpj@microsoft.com's avatar
      Rewrite CorePrep and improve eta expansion · 62eeda5a
      simonpj@microsoft.com authored
      This patch does two main things
      
      a) Rewrite most of CorePrep to be much easier to understand (I hope!).
         The invariants established by CorePrep are now written out, and
         the code is more perspicuous.  It is surpringly hard to get right,
         and the old code had become quite incomprehensible.
      
      b) Rewrite the eta-expander so that it does a bit of simplifying
         on-the-fly, and thereby guarantees to maintain the CorePrep
         invariants.  This make it much easier to use from CorePrep, and
         is a generally good thing anyway.
      
      A couple of pieces of re-structuring:
      
      *  I moved the eta-expander and arity analysis stuff into a new
         module coreSyn/CoreArity.
      
         Max will find that the type CoreArity.EtaInfo looks strangely 
         familiar.
      
      *  I moved a bunch of comments from Simplify to OccurAnal; that's
         why it looks as though there's a lot of lines changed in those
         modules.
      
      On the way I fixed various things
      
        - Function arguments are eta expanded
             f (map g)  ===>  let s = \x. map g x in f s
      
        - Trac #2368
      
      The result is a modest performance gain, I think mainly due
      to the first of these changes:
      
      --------------------------------------------------------------------------------
              Program           Size    Allocs   Runtime   Elapsed
      --------------------------------------------------------------------------------
                  Min          -1.0%    -17.4%    -19.1%    -46.4%
                  Max          +0.3%     +0.5%     +5.4%    +53.8%
       Geometric Mean          -0.1%     -0.3%     -7.0%    -10.2%
      
      
      62eeda5a
  15. 05 Dec, 2008 1 commit
  16. 29 Mar, 2008 1 commit
  17. 07 Feb, 2008 2 commits
  18. 18 Jan, 2008 1 commit
  19. 04 Sep, 2007 1 commit
  20. 03 Sep, 2007 1 commit
  21. 01 Sep, 2007 1 commit
  22. 22 Aug, 2007 1 commit
  23. 02 Jul, 2007 1 commit
  24. 11 May, 2007 1 commit
  25. 25 Apr, 2007 1 commit
    • simonpj@microsoft.com's avatar
      Retain inline-pragma information on unfoldings in interface files · d33c0b24
      simonpj@microsoft.com authored
      	WARNING: this patch changes interface-file formats slightly
      	 	 you will need to recompile your libraries
      
      Duncan Coutts wanted to export a function that has a NOINLNE pragma
      in a local let-defintion.  This works fine within a module, but was 
      not surviving across the interface-file serialisation.
      
      http://www.haskell.org/pipermail/glasgow-haskell-users/2007-March/012171.html
      
      Regardless of whether or not he's doing something sensible, it seems
      reasonable to try to retain local-binder IdInfo across interface files.
      This initial patch just retains inline-pragma info, on the grounds that
      other IdInfo can be re-inferred at the inline site.
      
      Interface files get a tiny bit bigger, but it seesm slight.
      
      d33c0b24
  26. 11 Oct, 2006 1 commit
    • Simon Marlow's avatar
      Module header tidyup, phase 1 · 49c98d14
      Simon Marlow authored
      This patch is a start on removing import lists and generally tidying
      up the top of each module.  In addition to removing import lists:
      
         - Change DATA.IOREF -> Data.IORef etc.
         - Change List -> Data.List etc.
         - Remove $Id$
         - Update copyrights
         - Re-order imports to put non-GHC imports last
         - Remove some unused and duplicate imports
      49c98d14
  27. 23 Sep, 2006 1 commit
  28. 20 Sep, 2006 1 commit
    • chak@cse.unsw.edu.au.'s avatar
      Complete the evidence generation for GADTs · 15cb792d
      chak@cse.unsw.edu.au. authored
      Mon Sep 18 14:43:22 EDT 2006  Manuel M T Chakravarty <chak@cse.unsw.edu.au>
        * Complete the evidence generation for GADTs
        Sat Aug  5 21:39:51 EDT 2006  Manuel M T Chakravarty <chak@cse.unsw.edu.au>
          * Complete the evidence generation for GADTs
          Thu Jul 13 17:18:07 EDT 2006  simonpj@microsoft.com
            
            This patch completes FC evidence generation for GADTs.
            
            It doesn't work properly yet, because part of the compiler thinks
            	(t1 :=: t2) => t3
            is represented with FunTy/PredTy, while the rest thinks it's represented
            using ForAllTy.  Once that's done things should start to work.
      15cb792d
  29. 04 Aug, 2006 1 commit
  30. 25 May, 2006 1 commit
    • simonpj@microsoft.com's avatar
      Fix egregious and long-standing tidying bug · a5168e30
      simonpj@microsoft.com authored
      A typo in tidyAlt meant that we could get shadowing of occurrence names
      in the output of tidying.  (Specifically, of existentially bound type 
      variables.)  That in turn meant that an IfaceExpr could have shadowing, so
      when the IfaceExpr was read in, it meant something different.
      That in turn led to an obscure crash like:
      	Panic: tcIfaceTyVar
      
      Anyway, this fixes it.  MERGE into 6.4.3.
      
      a5168e30
  31. 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
  32. 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
  33. 28 Apr, 2005 1 commit
    • simonpj's avatar
      [project @ 2005-04-28 10:09:41 by simonpj] · dd313897
      simonpj authored
      This big commit does several things at once (aeroplane hacking)
      which change the format of interface files.  
      
      	So you'll need to recompile your libraries!
      
      1. The "stupid theta" of a newtype declaration
      ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
      Retain the "stupid theta" in a newtype declaration.
      For some reason this was being discarded, and putting it
      back in meant changing TyCon and IfaceSyn slightly.
         
      
      2. Overlap flags travel with the instance
      ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
      Arrange that the ability to support overlap and incoherence
      is a property of the *instance declaration* rather than the
      module that imports the instance decl.  This allows a library
      writer to define overlapping instance decls without the
      library client having to know.  
      
      The implementation is that in an Instance we store the
      overlap flag, and preseve that across interface files
      
      
      3. Nuke the "instnce pool" and "rule pool"
      ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
      A major tidy-up and simplification of the way that instances
      and rules are sucked in from interface files.  Up till now
      an instance decl has been held in a "pool" until its "gates" 
      (a set of Names) are in play, when the instance is typechecked
      and added to the InstEnv in the ExternalPackageState.  
      This is complicated and error-prone; it's easy to suck in 
      too few (and miss an instance) or too many (and thereby be
      forced to suck in its type constructors, etc).
      
      Now, as we load an instance from an interface files, we 
      put it straight in the InstEnv... but the Instance we put in
      the InstEnv has some Names (the "rough-match" names) that 
      can be used on lookup to say "this Instance can't match".
      The detailed dfun is only read lazily, and the rough-match
      thing meansn it is'nt poked on until it has a chance of
      being needed.
      
      This simply continues the successful idea for Ids, whereby
      they are loaded straightaway into the TypeEnv, but their
      TyThing is a lazy thunk, not poked on until the thing is looked
      up.
      
      Just the same idea applies to Rules.
      
      On the way, I made CoreRule and Instance into full-blown records
      with lots of info, with the same kind of key status as TyCon or 
      DataCon or Class.  And got rid of IdCoreRule altogether.   
      It's all much more solid and uniform, but it meant touching
      a *lot* of modules.
      
      
      4. Allow instance decls in hs-boot files
      ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
      Allowing instance decls in hs-boot files is jolly useful, becuase
      in a big mutually-recursive bunch of data types, you want to give
      the instances with the data type declarations.  To achieve this
      
      * The hs-boot file makes a provisional name for the dict-fun, something
        like $fx9.
      
      * When checking the "mother module", we check that the instance
        declarations line up (by type) and generate bindings for the 
        boot dfuns, such as
      	$fx9 = $f2
        where $f2 is the dfun generated by the mother module
      
      * In doing this I decided that it's cleaner to have DFunIds get their
        final External Name at birth.  To do that they need a stable OccName,
        so I have an integer-valued dfun-name-supply in the TcM monad.
        That keeps it simple.
      
      This feature is hardly tested yet.
      
      
      5. Tidy up tidying, and Iface file generation
      ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
      main/TidyPgm now has two entry points:
      
        simpleTidyPgm is for hi-boot files, when typechecking only
        (not yet implemented), and potentially when compiling without -O.
        It ignores the bindings, and generates a nice small TypeEnv.
      
        optTidyPgm is the normal case: compiling with -O.  It generates a
        TypeEnv rich in IdInfo
      
      MkIface.mkIface now only generates a ModIface.  A separate
      procedure, MkIface.writeIfaceFile, writes the file out to disk.
      dd313897
  34. 22 Apr, 2005 1 commit
  35. 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
  36. 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
  37. 25 Nov, 2004 1 commit
    • simonpj's avatar
      [project @ 2004-11-25 11:36:34 by simonpj] · 1f7da302
      simonpj authored
      ------------------------------------------
      	Keep-alive set and Template Haskell quotes
      	------------------------------------------
      
      a) Template Haskell quotes should be able to mention top-leve
         things without resorting to lifting.  Example
      
      	module Foo( foo ) where
      	  f x = x
      	  foo = [| f 4 |]
      
         Here the reference to 'f' is ok; no need to 'lift' it.
         The relevant changes are in TcExpr.tcId
      
      b) However, we must take care not to discard the binding for f,
         so we add it to the 'keep-alive' set for the module.  I've
         now made this into (another) mutable bucket, tcg_keep, 
         in the TcGblEnv
      
      c) That in turn led me to look at the handling of orphan rules;
         as a result I made IdCoreRule into its own data type, which
         has simle but non-local ramifications
      1f7da302
  38. 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
  39. 17 Nov, 2003 1 commit