GitLab

This documents nondeterminism in code generation and removes
the nondeterministic ufmToList function. In the future someone
will have to use nonDetEltsUFM (with proper explanation)
or pprUFM.

This documents nondeterminism in code generation and removes
the nondeterministic ufmToList function. In the future someone
will have to use nonDetUFMToList (with proper explanation)
or pprUFMWithKeys.

These get annoying when `undefined` is actually used as placeholder in WIP code.
Some of these were also completely redundant (just call `deAnnotate'` instead of
`deAnnotate` etc.).

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

This impacts at least the order in which version macros are
generated. It's pretty hard to track what kind of nondeterminism
is benign and this should have no performance impact as the number
of packages should be relatively small.

Test Plan: ./validate

Reviewers: simonmar, austin, bgamari, ezyang

Reviewed By: ezyang

Subscribers: thomie

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

GHC Trac Issues: #4012

I planned to just say that we don't care about this part.
Turns out I was able to document away the uses in the codegenerator.

Test Plan: ./validate

Reviewers: simonmar, austin, bgamari

Subscribers: thomie

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

GHC Trac Issues: #4012

Summary: Like explained in the comment it's OK here.

Test Plan: ./validate

Reviewers: simonmar, austin, bgamari

Subscribers: thomie

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

GHC Trac Issues: #4012

This isn't strictly necessary for deterministic ABIs.
The results of eltsHpt are consumed in two ways:
1) they determine the order of linking
2) if you track the data flow all the family instances get put in
   FamInstEnvs, so the nondeterministic order is forgotten.
3) same for VectInfo stuff
4) same for Annotations

The problem is that I haven't found a nice way to do 2. in
a local way and 1. is nice to have if we went for deterministic
object files. Besides these maps are keyed on ModuleNames so they
should be small relative to other things and the overhead should
be negligible.

As a bonus we also get more specific names.

Test Plan: ./validate

Reviewers: bgamari, austin, hvr, ezyang, simonmar

Reviewed By: simonmar

Subscribers: thomie

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

GHC Trac Issues: #4012

This lets us kill fsEnvElts function which is nondeterministic.
We also get better guarantees than just comments.
We don't do lookups, but I believe a set is needed for deduplication.

Test Plan: ./validate

Reviewers: bgamari, mpickering, austin, simonmar

Reviewed By: simonmar

Subscribers: thomie

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

GHC Trac Issues: #4012

Summary:
Deriving `Typeable` has been a no-op since GHC 7.10, and now that we
require 7.10+ to build GHC, we can remove all the redundant `deriving Typeable`
statements in GHC.

Test Plan: ./validate

Reviewers: goldfire, austin, hvr, bgamari

Reviewed By: austin, hvr, bgamari

Subscribers: thomie

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

This kills two instances of varSetElems that turned out to be
nondeterministic. I've tried to untangle this before, but it's
a bit hard with the fixDs in the middle. Fortunately I now have
a test case that proves that we need determinism here.

Test Plan: ./validate, new testcase

Reviewers: simonpj, simonmar, austin, bgamari

Reviewed By: bgamari

Subscribers: thomie

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

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

This appears to cause validation issues on,

    TEST="T11108 T9071 T11076 T7600 T7672 T8329 T10420 T10322 T8308 T4114a
    T4114c T10602 T10110 T9204 T2435 T9838 T4114d T10233 T8696 T1735 T5281
    T6056 T10134 T9580 T6018 T9762 T8103"

With compiler panics of the form,

    Compile failed (status 256) errors were:
    ghc: panic! (the 'impossible' happened)
      (GHC version 8.1.20160523 for x86_64-unknown-linux):
            Binary.readBinMem: decompression failed
    CallStack (from HasCallStack):
      error, called at compiler/utils/Binary.hs:192:16 in ghc:Binary

    Please report this as a GHC bug:  http://www.haskell.org/ghc/reportabug

This reverts commit d9cb7a8a.

Compress all interface files generated by the compiler with LZ4. While
being only a tiny amount of code, LZ4 is both fast at compression and
decompression, and has good compression ratios.

Non-scientific size test: size of stage2 compiler .hi files:

`find ./compiler/stage2 -type f -iname '*.hi' -exec du -ch {} + | grep total$`

Without this patch: 22MB of .hi files for stage2.
With this patch: 9.2MB of .hi files for stage2.
Signed-off-by: Austin Seipp <austin@well-typed.com>

Reviewed By: bgamari

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

The order inert_model and intert_eqs fold affects the order that the
typechecker looks at things. I've been able to experimentally confirm
that the order of equalities and the order of the model matter for
determinism. This is just a straigthforward replacement of
nondeterministic VarEnv for deterministic DVarEnv.

Test Plan: ./validate

Reviewers: simonpj, goldfire, austin, bgamari, simonmar

Reviewed By: simonmar

Subscribers: thomie

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

GHC Trac Issues: #4012

Nondeterminism doesn't matter in these places and pprUFM makes
it obvious. I've flipped the order of arguments for convenience.

Test Plan: ./validate

Reviewers: simonmar, bgamari, austin, simonpj

Reviewed By: simonpj

Subscribers: thomie

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

GHC Trac Issues: #4012

We need the order of specialized binds and rules to be deterministic,
so we use a deterministic set here.

Test Plan: ./validate

Reviewers: simonmar, bgamari, austin, simonpj

Reviewed By: simonpj

Subscribers: thomie

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

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

Both Traversable and Foldable can introduce non-determinism
and because of typeclass overloading it's implicit and not
obvious at the call site. This removes the instances, so that
they can't accidentally be used.

Test Plan: ./validate

Reviewers: austin, goldfire, bgamari, simonmar, simonpj

Reviewed By: simonpj

Subscribers: thomie

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

GHC Trac Issues: #4012

It uses `eltsUFM` so it can introduce nondeterminism, but it isn't used
so we can delete it.

Test Plan: it builds

Reviewers: simonpj, goldfire, simonmar, austin, bgamari

Reviewed By: austin, bgamari

Subscribers: thomie

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

GHC Trac Issues: #4012

foldFsEnv is nondeterministic in the general case and since it's
unused we can just remove it.

Note [Unsound mapUniqSet] explains why it got removed.

Test Plan: build ghc

Reviewers: simonpj, austin, bgamari

Reviewed By: bgamari

Subscribers: thomie, simonmar

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

There are couple of places where we do `foldUniqSet` just to
compute `any` or `all`. `foldUniqSet` is non-deterministic in the
general case and `any` and `all` also read nicer.

Test Plan: ./validate

Reviewers: simonmar, goldfire, simonpj, bgamari, austin

Reviewed By: simonpj

Subscribers: thomie

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

GHC Trac Issues: #4012

varSetElemsWellScoped introduces unnecessary non-determinism in
inferred type signatures.
Removing this instance required changing the representation of
TcDepVars to use deterministic sets.
This is the last occurence of varSetElemsWellScoped, allowing me to
finally remove it.

Test Plan:
./validate
I will update the expected outputs when commiting, some reordering
of type variables in types is expected.

Reviewers: goldfire, simonpj, austin, bgamari

Reviewed By: simonpj

Subscribers: thomie, simonmar

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

GHC Trac Issues: #4012

This change takes us one step closer to being able to remove
`varSetElemsWellScoped`. The end goal is to make every source
of non-determinism obvious at the source level, so that when
we achieve determinism it doesn't get broken accidentally.

Test Plan: compile GHC

Reviewers: simonmar, goldfire, simonpj, austin, bgamari

Reviewed By: simonpj

Subscribers: thomie

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

GHC Trac Issues: #4012

This is from Simon's suggestion:

* `tyCoVarsOfTypesAcc` is a terrible name for a function with a
  perfectly decent type `[Type] -> FV`. Maybe `tyCoFVsOfTypes`?
  Similarly others

* `runFVList` is also terrible, but also has a decent type.
  Maybe just `fvVarList` (and `fvVarSet` for `runFVSet`).

* `someVars` could be `mkFVs :: [Var] -> FV`.

Test Plan: Validate

Reviewers: gridaphobe, austin

Reviewed By: austin

Subscribers: thomie

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

as they (especially their id info with absence information) clutter the
output too much. They come back with debug_on.

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

DEC OSF/1 (aka Tru64 UNIX) has been discontinued a few years ago already[1].

This removes the undoubtedly bitrotten support for `OSOsf3 :: OS` from GHC's
code-base.

Support for `ArchAlpha :: Arch` may be removed at some later point, as there
may still be users out there running a more or less recent Linux/alpha
distribution on their more-than-a-decade old Alpha hardware...

 [1]: https://en.wikipedia.org/wiki/Tru64_UNIX

This works in conjunction with D2036 to allow useful debug output before
DynFlags has been initializated.

See #11755.

Reviewers: austin

Reviewed By: austin

Subscribers: thomie, gridaphobe

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

GHC Trac Issues: #11755

This adds timings and allocation figures to the compiler's output when
run with `-v2` in an effort to ease performance analysis.

Todo:
  * Documentation
  * Where else should we add these?
  * Perhaps we should remove some of the now-arguably-redundant
    `showPass` occurrences where they are
  * Must we force more?
  * Perhaps we should place this behind a `-ftimings` instead of `-v2`

Test Plan: `ghc -v2 Test.hs`, look at the output

Reviewers: hvr, goldfire, simonmar, austin

Reviewed By: simonmar

Subscribers: angerman, michalt, niteria, ezyang, thomie

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

Test Plan:
  * Validate
  * try `env -i ghc`
  * try `env -i runghc HelloWorld.hs`

Reviewers: austin

Subscribers: thomie, ezyang

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

GHC Trac Issues: #11678

See Note [TYPE] in TysPrim. There are still some outstanding
pieces in #11471 though, so this doesn't actually nail the bug.

This commit also contains a few performance improvements:

* Short-cut equality checking of nullary type syns

* Compare types before kinds in eqType

* INLINE coreViewOneStarKind

* Store tycon binders separately from kinds.

This resulted in a ~10% performance improvement in compiling
the Cabal package. No change in functionality other than
performance. (This affects the interface file format, though.)

This commit updates the haddock submodule.

Currently, `-XDeriveFoldable` and `-XDeriveTraversable` generate
unnecessary `mempty` and `pure` expressions when it traverses of an
argument of a constructor whose type does not mention the last type
parameter. Not only is this inefficient, but it prevents `Traversable`
from being derivable for datatypes with unlifted arguments (see
Trac #11174).

The solution to this problem is to adopt a slight change to the
algorithms for `-XDeriveFoldable` and `-XDeriveTraversable`, which is
described in [this wiki
page](https://ghc.haskell.org/trac/ghc/wiki/Commentary/Compiler/DeriveFu
nctor#Proposal:alternativestrategyforderivingFoldableandTraversable).
The wiki page also describes why we don't apply the same changes to the
algorithm for `-XDeriveFunctor`.

This is techincally a breaking change for users of `-XDeriveFoldable`
and `-XDeriveTraversable`, since if someone was using a law-breaking
`Monoid` instance with a derived `Foldable` instance (i.e., one where `x
<> mempty` does not equal `x`) or a law-breaking `Applicative` instance
with a derived `Traversable` instance, then the new generated code could
result in different behavior. I suspect the number of scenarios like
this is very small, and the onus really should be on those users to fix
up their `Monoid`/`Applicative` instances.

Fixes #11174.

Test Plan: ./validate

Reviewers: hvr, simonpj, austin, bgamari

Reviewed By: simonpj, bgamari

Subscribers: thomie

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

GHC Trac Issues: #11174

Reviewers: austin, thomie

Subscribers: thomie

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

Summary:
Serialization of BCOs is slow, but we can parallelise it when using
ghci -j<n>.  It parallelises nicely, saving multiple seconds off the
link time in a large example I have.

Test Plan:
* validate
* `ghci -fexternal-interpreter` in `nofib/real/anna`

Reviewers: niteria, bgamari, ezyang, austin, hvr, erikd

Subscribers: thomie

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

GHC Trac Issues: #11100

Reviewers: austin, bgamari

Reviewed By: bgamari

Subscribers: thomie

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

The idea here is described in [wiki:Typechecker]. Briefly,
this refactor keeps solid track of "synthesis" mode vs
"checking" in GHC's bidirectional type-checking algorithm.
When in synthesis mode, the expected type is just an IORef
to write to.

In addition, this patch does a significant reworking of
RebindableSyntax, allowing much more freedom in the types
of the rebindable operators. For example, we can now have
`negate :: Int -> Bool` and
`(>>=) :: m a -> (forall x. a x -> m b) -> m b`. The magic
is in tcSyntaxOp.

This addresses tickets #11397, #11452, and #11458.

Tests:
  typecheck/should_compile/{RebindHR,RebindNegate,T11397,T11458}
  th/T11452

This adds sanity checks to `substTy` that implement:

> when calling substTy subst ty it should be the case that the in-scope
> set in the substitution is a superset of
> * The free vars of the range of the substitution
> * The free vars of ty minus the domain of the substitution

and replaces violators with unchecked version. The violators were found
by running the GHC test suite.

This ensures that I can work on this incrementally and that what I fix won't
be undone by some other change.

It also includes a couple of fixes that I've already done.

Test Plan: ./validate

Reviewers: simonmar, goldfire, simonpj, austin, bgamari

Reviewed By: simonpj, bgamari

Subscribers: thomie

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

GHC Trac Issues: #11371