| Commit message (Collapse) | Author | Age | Files | Lines |
|---|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
Here we introduce a new data structure, RoughMap, inspired by the
previous `RoughTc` matching mechanism for checking instance matches.
This allows [Fam]InstEnv to be implemented as a trie indexed by these
RoughTc signatures, reducing the complexity of instance lookup and
FamInstEnv merging (done during the family instance conflict test)
from O(n) to O(log n).
The critical performance improvement currently realised by this patch is
in instance matching. In particular the RoughMap mechanism allows us to
discount many potential instances which will never match for constraints
involving type variables (see Note [Matching a RoughMap]). In realistic
code bases matchInstEnv was accounting for 50% of typechecker time due
to redundant work checking instances when simplifying instance contexts
when deriving instances. With this patch the cost is significantly
reduced.
The larger constants in InstEnv creation do mean that a few small
tests regress in allocations slightly. However, the runtime of T19703 is
reduced by a factor of 4. Moreover, the compilation time of the Cabal
library is slightly improved.
A couple of test cases are included which demonstrate significant
improvements in compile time with this patch.
This unfortunately does not fix the testcase provided in #19703 but does
fix #20933
-------------------------
Metric Decrease:
T12425
Metric Increase:
T13719
T9872a
T9872d
hard_hole_fits
-------------------------
Co-authored-by: Matthew Pickering <matthewtpickering@gmail.com>
|
| |
|
|
| |
This was an oversight from !6718
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
This patch specifies and simplifies the module cycle compilation
in upsweep. How things work are described in the Note [Upsweep]
Note [Upsweep]
~~~~~~~~~~~~~~
Upsweep takes a 'ModuleGraph' as input, computes a build plan and then executes
the plan in order to compile the project.
The first step is computing the build plan from a 'ModuleGraph'.
The output of this step is a `[BuildPlan]`, which is a topologically sorted plan for
how to build all the modules.
```
data BuildPlan = SingleModule ModuleGraphNode -- A simple, single module all alone but *might* have an hs-boot file which isn't part of a cycle
| ResolvedCycle [ModuleGraphNode] -- A resolved cycle, linearised by hs-boot files
| UnresolvedCycle [ModuleGraphNode] -- An actual cycle, which wasn't resolved by hs-boot files
```
The plan is computed in two steps:
Step 1: Topologically sort the module graph without hs-boot files. This returns a [SCC ModuleGraphNode] which contains
cycles.
Step 2: For each cycle, topologically sort the modules in the cycle *with* the relevant hs-boot files. This should
result in an acyclic build plan if the hs-boot files are sufficient to resolve the cycle.
The `[BuildPlan]` is then interpreted by the `interpretBuildPlan` function.
* `SingleModule nodes` are compiled normally by either the upsweep_inst or upsweep_mod functions.
* `ResolvedCycles` need to compiled "together" so that the information which ends up in
the interface files at the end is accurate (and doesn't contain temporary information from
the hs-boot files.)
- During the initial compilation, a `KnotVars` is created which stores an IORef TypeEnv for
each module of the loop. These IORefs are gradually updated as the loop completes and provide
the required laziness to typecheck the module loop.
- At the end of typechecking, all the interface files are typechecked again in
the retypecheck loop. This time, the knot-tying is done by the normal laziness
based tying, so the environment is run without the KnotVars.
* UnresolvedCycles are indicative of a proper cycle, unresolved by hs-boot files
and are reported as an error to the user.
The main trickiness of `interpretBuildPlan` is deciding which version of a dependency
is visible from each module. For modules which are not in a cycle, there is just
one version of a module, so that is always used. For modules in a cycle, there are two versions of
'HomeModInfo'.
1. Internal to loop: The version created whilst compiling the loop by upsweep_mod.
2. External to loop: The knot-tied version created by typecheckLoop.
Whilst compiling a module inside the loop, we need to use the (1). For a module which
is outside of the loop which depends on something from in the loop, the (2) version
is used.
As the plan is interpreted, which version of a HomeModInfo is visible is updated
by updating a map held in a state monad. So after a loop has finished being compiled,
the visible module is the one created by typecheckLoop and the internal version is not
used again.
This plan also ensures the most important invariant to do with module loops:
> If you depend on anything within a module loop, before you can use the dependency,
the whole loop has to finish compiling.
The end result of `interpretBuildPlan` is a `[MakeAction]`, which are pairs
of `IO a` actions and a `MVar (Maybe a)`, somewhere to put the result of running
the action. This list is topologically sorted, so can be run in order to compute
the whole graph.
As well as this `interpretBuildPlan` also outputs an `IO [Maybe (Maybe HomeModInfo)]` which
can be queried at the end to get the result of all modules at the end, with their proper
visibility. For example, if any module in a loop fails then all modules in that loop will
report as failed because the visible node at the end will be the result of retypechecking
those modules together.
Along the way we also fix a number of other bugs in the driver:
* Unify upsweep and parUpsweep.
* Fix #19937 (static points, ghci and -j)
* Adds lots of module loop tests due to Divam.
Also related to #20030
Co-authored-by: Divam Narula <dfordivam@gmail.com>
-------------------------
Metric Decrease:
T10370
-------------------------
|
| | |
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
mode backpack edges
Backpack instantiations need to be typechecked to make sure that the
arguments fit the parameters. `tcRnInstantiateSignature` checks
instantiations with concrete modules, while `tcRnCheckUnit` checks
instantiations with free holes (signatures in the current modules).
Before this change, it worked that `tcRnInstantiateSignature` was called
after typechecking the argument module, see `HscMain.hsc_typecheck`,
while `tcRnCheckUnit` was called in `unsweep'` where-bound in
`GhcMake.upsweep`. `tcRnCheckUnit` was called once per each
instantiation once all the argument sigs were processed. This was done
with simple "to do" and "already done" accumulators in the fold.
`parUpsweep` did not implement the change.
With this change, `tcRnCheckUnit` instead is associated with its own
node in the `ModuleGraph`. Nodes are now:
```haskell
data ModuleGraphNode
-- | Instantiation nodes track the instantiation of other units
-- (backpack dependencies) with the holes (signatures) of the current package.
= InstantiationNode InstantiatedUnit
-- | There is a module summary node for each module, signature, and boot module being built.
| ModuleNode ExtendedModSummary
```
instead of just `ModSummary`; the `InstantiationNode` case is the
instantiation of a unit to be checked. The dependencies of such nodes
are the same "free holes" as was checked with the accumulator before.
Both versions of upsweep on such a node call `tcRnCheckUnit`.
There previously was an `implicitRequirements` function which would
crawl through every non-current-unit module dep to look for all free
holes (signatures) to add as dependencies in `GHC.Driver.Make`. But this
is no good: we shouldn't be looking for transitive anything when
building the graph: the graph should only have immediate edges and the
scheduler takes care that all transitive requirements are met.
So `GHC.Driver.Make` stopped using `implicitRequirements`, and instead
uses a new `implicitRequirementsShallow`, which just returns the
outermost instantiation node (or module name if the immediate dependency
is itself a signature). The signature dependencies are just treated like
any other imported module, but the module ones then go in a list stored
in the `ModuleNode` next to the `ModSummary` as the "extra backpack
dependencies". When `downsweep` creates the mod summaries, it adds this
information too.
------
There is one code quality, and possible correctness thing left: In
addition to `implicitRequirements` there is `findExtraSigImports`, which
says something like "if you are an instantiation argument (you are
substituted or a signature), you need to import its things too". This
is a little non-local so I am not quite sure how to get rid of it in
`GHC.Driver.Make`, but we probably should eventually.
First though, let's try to make a test case that observes that we don't
do this, lest it actually be unneeded. Until then, I'm happy to leave it
as is.
------
Beside the ability to use `-j`, the other major user-visibile side
effect of this change is that that the --make progress log now includes
"Instantiating" messages for these new nodes. Those also are numbered
like module nodes and count towards the total.
------
Fixes #17188
Updates hackage submomdule
Metric Increase:
T12425
T13035
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
This patch reverts the change introduced with
587dcccfdfa7a319e27300a4f3885071060b1f8e and restores the previous
default output of GHC (i.e., show source path and object path for each
compiled module).
The -fhide-source-paths flag can be used to hide these paths and reduce
the line
noise.
Reviewers: gracjan, nomeata, austin, bgamari, simonmar, hvr
Reviewed By: hvr
Subscribers: thomie
Differential Revision: https://phabricator.haskell.org/D2728
GHC Trac Issues: #12851
|
| |
|
|
|
|
|
|
|
|
|
|
| |
Reviewers: simonmar, mpickering, austin, bgamari
Reviewed By: bgamari
Subscribers: mpickering, nomeata, thomie
Differential Revision: https://phabricator.haskell.org/D2679
GHC Trac Issues: #12807
|
|
|
Signed-off-by: Edward Z. Yang <ezyang@cs.stanford.edu>
|
