GitLab

Trac #12425 and #12234 showed up a major and long-standing
bug in the occurrence analyser, whereby it could generate
explonentially large program!

There's a lot of commentary on #12425; and it's all described
in Note [Loop breakers, node scoring, and stability]

I did quite a lot of refactoring to make the code comprehensibe
again (its structure had bit-rotted rather), so the patch
looks bigger than it really is.

Hurrah!

I did a nofib run to check that I hadn't inadertently ruined
anything:

--------------------------------------------------------------------------------
        Program           Size    Allocs   Runtime   Elapsed  TotalMem
--------------------------------------------------------------------------------
          fluid          -0.3%     -1.5%      0.01      0.01     +0.0%
         parser          -0.9%     +0.6%      0.04      0.04     +0.0%
         prolog          -0.1%     +1.2%      0.00      0.00     +0.0%

--------------------------------------------------------------------------------
            Min          -0.9%     -1.5%     -8.6%     -8.7%     +0.0%
            Max          +0.1%     +1.2%     +7.7%     +7.8%     +2.4%
 Geometric Mean          -0.2%     -0.0%     -0.2%     -0.3%     +0.0%

I checked what happened in 'prolog'.  It seems that we have a
recursive data structure something like this

   f :: [blah]
   f x = build (\cn.  ...g...  )

   g :: [blah2]
   g y = ....(foldr k z (f y))....

If we inline 'f' into 'g' we get better fusion than the other
way round, but we don't have any way to spot that at the moment.
(I wonder if we could do worker/wrapper for functions returning
a 'build'?)  It was happening before by a fluke.

Anyway I decided to accept this; it's relatively rare I think.

It took me some time to find the right Note for the
fix to #12789.  This comment patch tries to add pointers
from relevant places.

This bug was beautifully characterised in Trac #12776,
which showed a small program for which the inliner went
into an infinite loop.  Eeek.

It turned out to be a genuine and long-standing bug in
the occurrence analyer, specifically in the bit that
identifies loop breakers.  In this line

  pairs | isEmptyVarSet weak_fvs
        = reOrderNodes   0 bndr_set weak_fvs tagged_nodes []
        | otherwise
        = loopBreakNodes 0 bndr_set weak_fvs loop_breaker_edges []

the 'tagged_nodes' should be 'loop_breaker_edges'.
That's it!

The diff looks a lot bigger because I did some work on
comments and variable naming, but that's all it is.  We
were using the wrong set of dependencies!

I'm astonished that this bug has not caused more trouble.
It dates back to at least 2011 and maybe further.

I did this while investigating Trac #12776

as the latter is the official, correct spelling, and the former just a
misspelling accepted by GHC.

Also document in the user’s guide that the alternative spelling is
accepted

This commit was brough to you by HIW 2016.

We want to remove the `Ord Unique` instance because there's
no way to implement it in deterministic way and it's too
easy to use by accident.

We sometimes compute SCC for datatypes whose Ord instance
is implemented in terms of Unique. The Ord constraint on
SCC is just an artifact of some internal data structures.
We can have an alternative implementation with a data
structure that uses Uniquable instead.

This does exactly that and I'm pleased that I didn't have
to introduce any duplication to do that.

Test Plan:
./validate
I looked at performance tests and it's a tiny bit better.

Reviewers: bgamari, simonmar, ezyang, austin, goldfire

Subscribers: thomie

Differential Revision: https://phabricator.haskell.org/D2359

GHC Trac Issues: #4012

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

I've documented the guarantees that stronglyConnCompFromEdgedVertices
provides and commented on the call sites to explain why they are
OK from determinism standpoint. I've changed the functions to
nonDetUFM versions, so that it's explicit they could introduce
nondeterminism.  I haven't defined container (VarSet, NameSet)
specific versions, so that we have less functions to worry about.

Test Plan: this is mostly just documentation,
it should have no runtime effect

Reviewers: bgamari, simonmar, austin, simonpj

Reviewed By: simonpj

Subscribers: thomie

Differential Revision: https://phabricator.haskell.org/D2194

GHC Trac Issues: #4012

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

This reverts commit 28fe0eea due to
various regressions. I’m not sure why my local
./validate --slow
run did not catch this, though.

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.

Differential Revision: https://phabricator.haskell.org/D2070

Fixes Trac #11651.  Merge to 8.0.

Summary:
In the past the canonical way for constructing an SDoc string literal was the
composition `ptext . sLit`.  But for some time now we have function `text` that
does the same.  Plus it has some rules that optimize its runtime behaviour.
This patch takes all uses of `ptext . sLit` in the compiler and replaces them
with calls to `text`.  The main benefits of this patch are clener (shorter) code
and less dependencies between module, because many modules now do not need to
import `FastString`.  I don't expect any performance benefits - we mostly use
SDocs to report errors and it seems there is little to be gained here.

Test Plan: ./validate

Reviewers: bgamari, austin, goldfire, hvr, alanz

Subscribers: goldfire, thomie, mpickering

Differential Revision: https://phabricator.haskell.org/D1784

This implements the ideas originally put forward in
"System FC with Explicit Kind Equality" (ICFP'13).

There are several noteworthy changes with this patch:
 * We now have casts in types. These change the kind
   of a type. See new constructor `CastTy`.

 * All types and all constructors can be promoted.
   This includes GADT constructors. GADT pattern matches
   take place in type family equations. In Core,
   types can now be applied to coercions via the
   `CoercionTy` constructor.

 * Coercions can now be heterogeneous, relating types
   of different kinds. A coercion proving `t1 :: k1 ~ t2 :: k2`
   proves both that `t1` and `t2` are the same and also that
   `k1` and `k2` are the same.

 * The `Coercion` type has been significantly enhanced.
   The documentation in `docs/core-spec/core-spec.pdf` reflects
   the new reality.

 * The type of `*` is now `*`. No more `BOX`.

 * Users can write explicit kind variables in their code,
   anywhere they can write type variables. For backward compatibility,
   automatic inference of kind-variable binding is still permitted.

 * The new extension `TypeInType` turns on the new user-facing
   features.

 * Type families and synonyms are now promoted to kinds. This causes
   trouble with parsing `*`, leading to the somewhat awkward new
   `HsAppsTy` constructor for `HsType`. This is dispatched with in
   the renamer, where the kind `*` can be told apart from a
   type-level multiplication operator. Without `-XTypeInType` the
   old behavior persists. With `-XTypeInType`, you need to import
   `Data.Kind` to get `*`, also known as `Type`.

 * The kind-checking algorithms in TcHsType have been significantly
   rewritten to allow for enhanced kinds.

 * The new features are still quite experimental and may be in flux.

 * TODO: Several open tickets: #11195, #11196, #11197, #11198, #11203.

 * TODO: Update user manual.

Tickets addressed: #9017, #9173, #7961, #10524, #8566, #11142.
Updates Haddock submodule.

Test Plan: validate

Reviewers: simonpj, austin, bgamari

Reviewed By: bgamari

Subscribers: thomie

Differential Revision: https://phabricator.haskell.org/D1319

The only real change is a new type synonym ImpRuleEdges
No significant changes at all

Summary: It looks like during .lhs -> .hs switch the comments were not updated. So doing exactly that.

Reviewers: austin, jstolarek, hvr, goldfire

Reviewed By: austin, jstolarek

Subscribers: thomie, goldfire

Differential Revision: https://phabricator.haskell.org/D621

GHC Trac Issues: #9986

This patch introduces "SourceNote" tickishs that link Core to the
source code that generated it. The idea is to retain these source code
links throughout code transformations so we can eventually relate
object code all the way back to the original source (which we can,
say, encode as DWARF information to allow debugging).  We generate
these SourceNotes like other tickshs in the desugaring phase. The
activating command line flag is "-g", consistent with the flag other
compilers use to decide DWARF generation.

Keeping ticks from getting into the way of Core transformations is
tricky, but doable. The changes in this patch produce identical Core
in all cases I tested -- which at this point is GHC, all libraries and
nofib. Also note that this pass creates *lots* of tick nodes, which we
reduce somewhat by removing duplicated and overlapping source
ticks. This will still cause significant Tick "clumps" - a possible
future optimization could be to make Tick carry a list of Tickishs
instead of one at a time.

(From Phabricator D169)

Signed-off-by: Austin Seipp <austin@well-typed.com>

This patch fixes Trac #9583, a loop in the simplifier.

I thought this was going to be very complicated but it turned out to
be very simple!  The occurrence analyser does something called
"glomming" if the application of imported RULES means that something
that didn't look recursive becomes recursive.  See `Note [Glomming]`
in `OccurAnal`.  Under these circumstances we group all the top-level
bindings into a single massive `Rec`.

But, crucially, I failed to repeat the occurrence analysis on this
glommed set of bindings.  That means that we weren't establishing the
right loop breakers (indeed there were no loop breakers whatsoever),
and that led immediately to the loop. The only surprising this is that
it didn't happen before.

Previously INLINE and INLINEABLE were treated identically, but it's
crucial that we don't choose a wrapper (INLINE) as a loop breaker,
when it is mutually recursive with an INLINEABLE worker.

The "InlineRule" is gone now, so this is just making the comments line
up with the code.  A function does change its name though:
   updModeForInlineRules  -->  updModeForStableUnfoldings

Call sites are much easier to understand than before

Summary:
  1. Respect condition (a) in Note [Binder swap]
  2. Respect condition (b) in Note [Binder swap]
  3. Return usage of any coercion variables in binder swap

Fixes T9440

Test Plan: See #9440

Reviewers: simonpj, austin

Reviewed By: simonpj, austin

Subscribers: simonpj, simonmar, relrod, ezyang, carter

Differential Revision: https://phabricator.haskell.org/D156

GHC Trac Issues: #9440

In some cases, the layout of the LANGUAGE/OPTIONS_GHC lines has been
reorganized, while following the convention, to

- place `{-# LANGUAGE #-}` pragmas at the top of the source file, before
  any `{-# OPTIONS_GHC #-}`-lines.

- Moreover, if the list of language extensions fit into a single
  `{-# LANGUAGE ... -#}`-line (shorter than 80 characters), keep it on one
  line. Otherwise split into `{-# LANGUAGE ... -#}`-lines for each
  individual language extension. In both cases, try to keep the
  enumeration alphabetically ordered.
  (The latter layout is preferable as it's more diff-friendly)

While at it, this also replaces obsolete `{-# OPTIONS ... #-}` pragma
occurences by `{-# OPTIONS_GHC ... #-}` pragmas.

Joachim and I are committing this onto a branch so that we can share it,
but we expect to do a bit more work before merging it onto head.

Nofib staus:
  - Most programs, no change
  - A few improve
  - A couple get worse (cacheprof, tak, rfib)
Investigating the "get worse" set is what's holding up putting this
on head.

The major issue is this.  Consider

    map (f g) ys

where f's demand signature looks like

   f :: <L,C1(C1(U))> -> <L,U> -> .

So 'f' is not saturated.  What demand do we place on g?
Answer
        C(C1(U))
That is, the inner C1 should stay, even though f is not saturated.

I found that this made a significant difference in the demand signatures
inferred in GHC.IO, which uses lots of higher-order exception handlers.

I also had to add used-once demand signatures for some of the
'catch' primops, so that we know their handlers are only called once.

Part of Nick Frisby's patch (c080f727)
for late demand-analysis removed the over-zealous short-cut whereby
strictness wrappers were not spelled out in detail in interface files.

This patch completes the process by
 * removing InlineWrapper from UnfoldingSource
 * removing IfWrapper from IfaceUnfolding

There was a tiny bit of special ad-hocery for wrappers, in OccurAnal,
but fortunately that too turns out to be rendered irrelevant by
the more uniform treatment, and after that there was no need
to remember which functions are wrappers.

cf http://ghc.haskell.org/trac/ghc/wiki/LateDmd