1. 12 Feb, 2020 1 commit
    • Sebastian Graf's avatar
      Separate CPR analysis from the Demand analyser · 059c3c9d
      Sebastian Graf authored
      The reasons for that can be found in the wiki:
      https://gitlab.haskell.org/ghc/ghc/wikis/nested-cpr/split-off-cpr
      
      We now run CPR after demand analysis (except for after the final demand
      analysis run just before code gen). CPR got its own dump flags
      (`-ddump-cpr-anal`, `-ddump-cpr-signatures`), but not its own flag to
      activate/deactivate. It will run with `-fstrictness`/`-fworker-wrapper`.
      
      As explained on the wiki page, this step is necessary for a sane Nested
      CPR analysis. And it has quite positive impact on compiler performance:
      
      Metric Decrease:
          T9233
          T9675
          T9961
          T15263
      059c3c9d
  2. 27 Jan, 2020 1 commit
  3. 25 Jan, 2020 1 commit
    • Sebastian Graf's avatar
      PmCheck: Formulate as translation between Clause Trees · 8038cbd9
      Sebastian Graf authored
      We used to check `GrdVec`s arising from multiple clauses and guards in
      isolation. That resulted in a split between `pmCheck` and
      `pmCheckGuards`, the implementations of which were similar, but subtly
      different in detail. Also the throttling mechanism described in
      `Note [Countering exponential blowup]` ultimately got quite complicated
      because it had to cater for both checking functions.
      
      This patch realises that pattern match checking doesn't just consider
      single guarded RHSs, but that it's always a whole set of clauses, each
      of which can have multiple guarded RHSs in turn. We do so by
      translating a list of `Match`es to a `GrdTree`:
      
      ```haskell
      data GrdTree
        = Rhs !RhsInfo
        | Guard !PmGrd !GrdTree      -- captures lef-to-right  match semantics
        | Sequence !GrdTree !GrdTree -- captures top-to-bottom match semantics
        | Empty                      -- For -XEmptyCase, neutral element of Sequence
      ```
      
      Then we have a function `checkGrdTree` that matches a given `GrdTree`
      against an incoming set of values, represented by `Deltas`:
      
      ```haskell
      checkGrdTree :: GrdTree -> Deltas -> CheckResult
      ...
      ```
      
      Throttling is isolated to the `Sequence` case and becomes as easy as one
      would expect: When the union of uncovered values becomes too big, just
      return the original incoming `Deltas` instead (which is always a
      superset of the union, thus a sound approximation).
      
      The returned `CheckResult` contains two things:
      
      1. The set of values that were not covered by any of the clauses, for
         exhaustivity warnings.
      2. The `AnnotatedTree` that enriches the syntactic structure of the
         input program with divergence and inaccessibility information.
      
      This is `AnnotatedTree`:
      
      ```haskell
      data AnnotatedTree
        = AccessibleRhs !RhsInfo
        | InaccessibleRhs !RhsInfo
        | MayDiverge !AnnotatedTree
        | SequenceAnn !AnnotatedTree !AnnotatedTree
        | EmptyAnn
      ```
      
      Crucially, `MayDiverge` asserts that the tree may force diverging
      values, so not all of its wrapped clauses can be redundant.
      
      While the set of uncovered values can be used to generate the missing
      equations for warning messages, redundant and proper inaccessible
      equations can be extracted from `AnnotatedTree` by
      `redundantAndInaccessibleRhss`.
      
      For this to work properly, the interface to the Oracle had to change.
      There's only `addPmCts` now, which takes a bag of `PmCt`s. There's a
      whole bunch of `PmCt` variants to replace the different oracle functions
      from before.
      
      The new `AnnotatedTree` structure allows for more accurate warning
      reporting (as evidenced by a number of changes spread throughout GHC's
      code base), thus we fix #17465.
      
      Fixes #17646 on the go.
      
      Metric Decrease:
          T11822
          T9233
          PmSeriesS
          haddock.compiler
      8038cbd9
  4. 13 Jan, 2020 1 commit
  5. 28 Nov, 2019 1 commit
  6. 01 May, 2019 1 commit
    • Sebastian Graf's avatar
      Compute demand signatures assuming idArity · 014ed644
      Sebastian Graf authored
      This does four things:
      
      1. Look at `idArity` instead of manifest lambdas to decide whether to use LetUp
      2. Compute the strictness signature in LetDown assuming at least `idArity`
         incoming arguments
      3. Remove the special case for trivial RHSs, which is subsumed by 2
      4. Don't perform the W/W split when doing so would eta expand a binding.
         Otherwise we would eta expand PAPs, causing unnecessary churn in the
         Simplifier.
      
      NoFib Results
      
      --------------------------------------------------------------------------------
              Program         Allocs    Instrs
      --------------------------------------------------------------------------------
       fannkuch-redux          +0.3%      0.0%
                   gg          -0.0%     -0.1%
             maillist          +0.2%     +0.2%
              minimax           0.0%     +0.8%
               pretty           0.0%     -0.1%
              reptile          -0.0%     -1.2%
      --------------------------------------------------------------------------------
                  Min          -0.0%     -1.2%
                  Max          +0.3%     +0.8%
       Geometric Mean          +0.0%     -0.0%
      014ed644
  7. 15 Mar, 2019 1 commit
  8. 02 Feb, 2019 1 commit
  9. 01 Feb, 2019 1 commit
  10. 12 Dec, 2018 1 commit
    • Simon Peyton Jones's avatar
      Improvements to demand analysis · d77501cd
      Simon Peyton Jones authored
      This patch collects a few improvements triggered by Trac #15696,
      and fixing Trac #16029
      
      * Stop making toCleanDmd behave specially for unlifted types.
        This special case was the cause of stupid behaviour in Trac
        #16029.  And to my joy I discovered the let/app invariant
        rendered it unnecessary.  (Maybe the special case pre-dated
        the let/app invariant.)
      
        Result: less special-case handling in the compiler, and
        better perf for the compiled code.
      
      * In WwLib.mkWWstr_one, treat seqDmd like U(AAA).  It was not
        being so treated before, which again led to stupid code.
      
      * Update and improve Notes
      
      There are .stderr test wibbles because we get slightly different
      strictness signatures for an argumment of unlifted type:
          <L,U> rather than <S,U>        for Int#
          <S,U> rather than <S(S),U(U)>  for Int
      d77501cd
  11. 23 Nov, 2018 1 commit
    • Sebastian Graf's avatar
      Implement late lambda lift · b2950e03
      Sebastian Graf authored
      Summary:
      This implements a selective lambda-lifting pass late in the STG
      pipeline.
      
      Lambda lifting has the effect of avoiding closure allocation at the cost
      of having to make former free vars available at call sites, possibly
      enlarging closures surrounding call sites in turn.
      
      We identify beneficial cases by means of an analysis that estimates
      closure growth.
      
      There's a Wiki page at
      https://ghc.haskell.org/trac/ghc/wiki/LateLamLift.
      
      Reviewers: simonpj, bgamari, simonmar
      
      Reviewed By: simonpj
      
      Subscribers: rwbarton, carter
      
      GHC Trac Issues: #9476
      
      Differential Revision: https://phabricator.haskell.org/D5224
      b2950e03
  12. 15 Oct, 2018 1 commit
  13. 21 Aug, 2018 1 commit
    • Simon Peyton Jones's avatar
      Set strictness correctly for JoinIds · ce6ce788
      Simon Peyton Jones authored
      We were failing to keep correct strictness info when eta-expanding
      join points; Trac #15517.   The situation was something like
      
        \q v eta ->
           let j x = error "blah
               -- STR Lx   bottoming!
           in case y of
                 A -> j x eta
                 B -> blah
                 C -> j x eta
      
      So we spot j as a join point and eta-expand it.  But we must
      also adjust the stricness info, else it vlaimes to bottom after
      one arg is applied but now it has become two.
      
      I fixed this in two places:
      
       - In CoreOpt.joinPointBinding_maybe, adjust strictness info
      
       - In SimplUtils.tryEtaExpandRhs, return consistent values
         for arity and bottom-ness
      ce6ce788
  14. 19 Sep, 2017 1 commit
    • Herbert Valerio Riedel's avatar
      compiler: introduce custom "GhcPrelude" Prelude · f63bc730
      Herbert Valerio Riedel authored
      This switches the compiler/ component to get compiled with
      -XNoImplicitPrelude and a `import GhcPrelude` is inserted in all
      modules.
      
      This is motivated by the upcoming "Prelude" re-export of
      `Semigroup((<>))` which would cause lots of name clashes in every
      modulewhich imports also `Outputable`
      
      Reviewers: austin, goldfire, bgamari, alanz, simonmar
      
      Reviewed By: bgamari
      
      Subscribers: goldfire, rwbarton, thomie, mpickering, bgamari
      
      Differential Revision: https://phabricator.haskell.org/D3989
      f63bc730
  15. 13 Sep, 2017 1 commit
    • Ben Gamari's avatar
      Model divergence of retry# as ThrowsExn, not Diverges · 10a1a478
      Ben Gamari authored
      The demand signature of the retry# primop previously had a Diverges
      result.  However, this caused the demand analyser to conclude that a
      program of the shape,
      
          catchRetry# (... >> retry#)
      
      would diverge. Of course, this is plainly wrong; catchRetry#'s sole
      reason to exist is to "catch" the "exception" thrown by retry#. While
      catchRetry#'s demand signature correctly had the ExnStr flag set on its
      first argument, indicating that it should catch divergence, the logic
      associated with this flag doesn't apply to Diverges results. This
      resulted in #14171.
      
      The solution here is to treat the divergence of retry# as an exception.
      Namely, give it a result type of ThrowsExn rather than Diverges.
      
      Updates stm submodule for tests.
      
      Test Plan: Validate with T14171
      
      Reviewers: simonpj, austin
      
      Subscribers: rwbarton, thomie
      
      GHC Trac Issues: #14171, #8091
      
      Differential Revision: https://phabricator.haskell.org/D3919
      10a1a478
  16. 20 Jul, 2017 1 commit
  17. 19 Jul, 2017 1 commit
    • Ben Gamari's avatar
      dmdAnal: Ensure that ExnStr flag isn't dropped inappropriately · c940e3b9
      Ben Gamari authored
      This fixes #13977 and consequently #13615. Here an optimization in the
      demand analyser was too liberal, causing us to drop the ExnStr flag and
      consequently resulting in incorrect demand signatures. This manifested
      as a segmentation fault in #13615 as we incorrectly concluded that an
      application of catchRetry# would bottom.
      
      Specifically, we had
      
          orElse' :: STM a -> STM a -> STM a
          orElse' x = catchRetry# x y
            where y = {- some action -}
      
      Where the catchRetry# primop places a demand of <xC(S),1*C1(U)> on its
      first argument. However, due to #13977 the demand analyser would assign
      a demand of <C(S),1*C1(U)> on the first argument of orElse'. Note the
      missing `x`.
      
          case orElse' bottomingAction anotherAction of { x -> Just x }
      
      being transformed to,
      
          case orElse' bottomingAction anotherAction of {}
      
      by the simplifier. This would naturally blow up when orElse' returned at
      runtime, causing the segmentation fault described in #13615.
      
      Test Plan: Validate, perhaps add a testcase
      
      Reviewers: austin, simonpj
      
      Reviewed By: simonpj
      
      Subscribers: rwbarton, thomie
      
      GHC Trac Issues: #13977, #13615
      
      Differential Revision: https://phabricator.haskell.org/D3756
      c940e3b9
  18. 02 Jun, 2017 1 commit
    • Ryan Scott's avatar
      Use lengthIs and friends in more places · a786b136
      Ryan Scott authored
      While investigating #12545, I discovered several places in the code
      that performed length-checks like so:
      
      ```
      length ts == 4
      ```
      
      This is not ideal, since the length of `ts` could be much longer than 4,
      and we'd be doing way more work than necessary! There are already a slew
      of helper functions in `Util` such as `lengthIs` that are designed to do
      this efficiently, so I found every place where they ought to be used and
      did just that. I also defined a couple more utility functions for list
      length that were common patterns (e.g., `ltLength`).
      
      Test Plan: ./validate
      
      Reviewers: austin, hvr, goldfire, bgamari, simonmar
      
      Reviewed By: bgamari, simonmar
      
      Subscribers: goldfire, rwbarton, thomie
      
      Differential Revision: https://phabricator.haskell.org/D3622
      a786b136
  19. 01 Apr, 2017 1 commit
    • rwbarton's avatar
      Stamp out space leaks from demand analysis · f2b10f35
      rwbarton authored
      This reduces peak memory usage by ~30% on my test case (DynFlags),
      and (probably as a result of reduced GC work) decreases compilation
      time by a few percent as well.
      
      Also fix a bug in seqStrDmd so that demeand info is fully evaluated.
      
      Reviewers: simonpj, austin, bgamari
      
      Reviewed By: bgamari
      
      Subscribers: dfeuer, thomie
      
      Differential Revision: https://phabricator.haskell.org/D3400
      f2b10f35
  20. 14 Mar, 2017 1 commit
  21. 08 Mar, 2017 1 commit
  22. 06 Mar, 2017 1 commit
  23. 01 Mar, 2017 1 commit
    • David Feuer's avatar
      Change catch# demand signature · 701256df
      David Feuer authored
      * Give `catch#` a lazy demand signature, to make it more honest.
      
      * Make `catchException` and `catchAny` force their arguments so they
      actually behave as advertised.
      
      * Use `catch` rather than `catchException` in `forkIO`, `forkOn`, and
      `forkOS` to avoid losing exceptions.
      
      Fixes #13330
      
      Reviewers: rwbarton, simonpj, simonmar, bgamari, hvr, austin
      
      Subscribers: thomie
      
      Differential Revision: https://phabricator.haskell.org/D3244
      701256df
  24. 23 Feb, 2017 1 commit
  25. 09 Feb, 2017 1 commit
  26. 03 Feb, 2017 1 commit
  27. 01 Feb, 2017 1 commit
  28. 23 Jan, 2017 1 commit
  29. 18 Jan, 2017 1 commit
  30. 25 Aug, 2016 2 commits
    • Joachim Breitner's avatar
      WwLib: Add strictness signature to "let x = absentError …" · faaf3139
      Joachim Breitner authored
      indicating that it is bottom. This should help making the "empty cases"
      lint error give less false alarms.
      faaf3139
    • Joachim Breitner's avatar
      DmdAnal: Add a final, safe iteration · 8d92b88d
      Joachim Breitner authored
      this fixes #12368.
      
      It also refactors dmdFix a bit, removes some redundancies (such as
      passing around an strictness signature right next to an id, when that id
      is guaranteed to have been annotated with that strictness signature).
      
      Note that when fixed-point iteration does not terminate, we
      conservatively delete their strictness signatures (set them to nopSig).
      But this loses the information on how its strict free variables are
      used!
      
      Lazily used variables already escape via lazy_fvs. We ensure that in the
      case of an aborted fixed-point iteration, also the strict variables are
      put there (with a conservative demand of topDmd).
      
      Differential Revision: https://phabricator.haskell.org/D2392
      8d92b88d
  31. 01 Jul, 2016 1 commit
  32. 22 Jun, 2016 1 commit
  33. 17 Jun, 2016 1 commit
  34. 24 May, 2016 1 commit
    • niteria's avatar
      Document some benign nondeterminism · 4c6e69d5
      niteria authored
      I've changed the functions to their nonDet equivalents and explained
      why they're OK there. This allowed me to remove foldNameSet,
      foldVarEnv, foldVarEnv_Directly, foldVarSet and foldUFM_Directly.
      
      Test Plan: ./validate, there should be no change in behavior
      
      Reviewers: simonpj, simonmar, austin, goldfire, bgamari
      
      Reviewed By: bgamari
      
      Subscribers: thomie
      
      Differential Revision: https://phabricator.haskell.org/D2244
      
      GHC Trac Issues: #4012
      4c6e69d5
  35. 14 Apr, 2016 1 commit
    • Joachim Breitner's avatar
      Add a final demand analyzer run right before TidyCore · f4fd98c7
      Joachim Breitner authored
      in order to have precise used-once information in the exported
      strictness signatures, as well as precise used-once information on
      thunks. This avoids the bad effects of #11731.
      
      The subsequent worker-wrapper pass is responsible for removing the
      demand environment part of the strictness signature. It does not run
      after the final demand analyzer pass, so remove this also in CoreTidy.
      
      The subsequent worker-wrapper pass is also responsible for removing
      used-once-information from the demands and strictness signatures, as
      these might not be preserved by the simplifier. This is _not_ done by
      CoreTidy, because we _do_ want this information, as produced by the last
      round of the demand analyzer, to be available to the code generator.
      
      Differential Revision: https://phabricator.haskell.org/D2073
      f4fd98c7
  36. 06 Apr, 2016 1 commit
    • Joachim Breitner's avatar
      Demand Analyzer: Do not set OneShot information (second try) · 0f58d348
      Joachim Breitner authored
      as suggested in ticket:11770#comment:1. This code was buggy
      (#11770), and the occurrence analyzer does the same job anyways.
      
      This also elaborates the notes in the occurrence analyzer accordingly.
      
      Previously, the worker/wrapper code would go through lengths to transfer
      the oneShot annotations from the original function to both the worker
      and the wrapper. We now simply transfer the demand on the worker, and
      let the subsequent occurrence analyzer push this onto the lambda
      binders.
      
      This also requires the occurrence analyzer to do this more reliably.
      Previously, it would not hand out OneShot annotatoins to things that
      would not `certainly_inline` (and it might not have mattered, as the
      Demand Analysis might have handed out the annotations). Now we hand out
      one-shot annotations unconditionally.
      
      Differential Revision: https://phabricator.haskell.org/D2085
      0f58d348
  37. 31 Mar, 2016 1 commit
  38. 29 Mar, 2016 2 commits