summaryrefslogtreecommitdiff
path: root/compiler/coreSyn/TrieMap.hs
Commit message (Collapse)AuthorAgeFilesLines
* Improve typechecking of instance defaultsSimon Peyton Jones2016-06-241-1/+2
| | | | | | | | | | | | | | | | | | | | | | | | | In an instance declaration when you don't specify the code for a method, GHC fills in from the default binding in the class. The type of the default method can legitmiately be ambiguous --- see Note [Default methods in instances] in TcInstDcls --- so typechecking it can be tricky. Trac #12220 showed that although we were dealing with that ambiguity for /vanilla/ default methods, we were not doing so for /generic/ default methods. Moreover we were dealing with it clumsily, by generating post-typechecked code. This patch fixes the bug AND deletes code! We now use the same code path for both vanilla and generic default methods; and generate /pre-typechecked/ code in both cases. The key trick is that we can use Visible Type Application to deal with the ambiguity, which wasn't possible before. Hooray. There is a small hit to performance in compiler/perf/T1969 which consists of nothing BUT instance declarations with several default methods to fill, which we now have to typecheck. The actual hit is from 724 -> 756 or 4% in that extreme example. Real world programs have vastly fewer instance decls.
* Re-add FunTy (big patch)Simon Peyton Jones2016-06-151-8/+8
| | | | | | | | | | | | | | | | | | | | | | With TypeInType Richard combined ForAllTy and FunTy, but that was often awkward, and yielded little benefit becuase in practice the two were always treated separately. This patch re-introduces FunTy. Specfically * New type data TyVarBinder = TvBndr TyVar VisibilityFlag This /always/ has a TyVar it. In many places that's just what what we want, so there are /lots/ of TyBinder -> TyVarBinder changes * TyBinder still exists: data TyBinder = Named TyVarBinder | Anon Type * data Type = ForAllTy TyVarBinder Type | FunTy Type Type | .... There are a LOT of knock-on changes, but they are all routine. The Haddock submodule needs to be updated too
* Kill non-deterministic foldUFM in TrieMap and TcAppMapBartosz Nitka2016-05-041-32/+100
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: foldUFM introduces unnecessary non-determinism that actually leads to different generated code as explained in Note [TrieMap determinism]. As we're switching from UniqFM to UniqDFM here you might be concerned about performance. There's nothing that ./validate detects. nofib reports no change in Compile Allocations, but Compile Time got better on some tests and worse on some, yielding this summary: -1 s.d. ----- -3.8% +1 s.d. ----- +5.4% Average ----- +0.7% This is not a fair comparison as the order of Uniques changes what GHC is actually doing. One benefit from making this deterministic is also that it will make the performance results more stable. Full nofib results: P108 Test Plan: ./validate, nofib Reviewers: goldfire, simonpj, simonmar, austin, bgamari Reviewed By: simonpj Subscribers: thomie Differential Revision: https://phabricator.haskell.org/D2169 GHC Trac Issues: #4012
* TrieMap: Minor documentation fixÖmer Sinan Ağacan2016-01-091-2/+9
|
* Add kind equalities to GHC.Richard Eisenberg2015-12-111-292/+140
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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.
* Typos in commentsGabor Greif2015-07-311-1/+1
|
* Cite the TrieMap idea [skip-ci]Edward Z. Yang2015-03-021-0/+6
| | | | Signed-off-by: Edward Z. Yang <ezyang@cs.stanford.edu>
* Newtype CoreMap and TypeMap so their keys are user-friendly.Edward Z. Yang2015-01-091-84/+117
| | | | | | | | | | | | | | Summary: Signed-off-by: Edward Z. Yang <ezyang@cs.stanford.edu> Test Plan: validate Reviewers: simonpj, austin Subscribers: carter, thomie Differential Revision: https://phabricator.haskell.org/D612 GHC Trac Issues: #9960
* Inline all of the .*[TCE] methods, and then rename .*[TCE]X to vacated name.Edward Z. Yang2015-01-091-180/+183
| | | | Signed-off-by: Edward Z. Yang <ezyang@cs.stanford.edu>
* Miscellaneous improvements to TrieMap, from D608 code review.Edward Z. Yang2015-01-091-48/+74
| | | | | | | | | | | | | | | | | | | | | | | Summary: - Add SPECIALIZE pragmas for the lkG/xtG/mapG/fdG family of functions - Rename wrapEmptyXX to just emptyXX - New deBruijnize function for initializing DeBruijn elements - Some extra documentation Signed-off-by: Edward Z. Yang <ezyang@cs.stanford.edu> Test Plan: validate Reviewers: simonpj, austin Subscribers: carter, thomie Differential Revision: https://phabricator.haskell.org/D611 GHC Trac Issues: #9960
* Apply GenMap to CoreMap and CoercionMap.Edward Z. Yang2015-01-081-79/+183
| | | | | | | | | | | | | | | | | | | Summary: The biggest chore is the Eq (DeBrujin a) instances (all the more a chore because we already have an implementation of them, but a CmEnv is not an RnEnv2), but otherwise a fairly mechanical transformation. Signed-off-by: Edward Z. Yang <ezyang@cs.stanford.edu> Test Plan: validate Reviewers: simonpj, austin Subscribers: carter, thomie Differential Revision: https://phabricator.haskell.org/D609 GHC Trac Issues: #9960
* Add 'DeBruijn' constructor, which generalizes "key modulo alpha-renaming."Edward Z. Yang2015-01-081-109/+104
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: We need equality over Types, etc; and this equality has to be modulo alpha renaming. Previously, we baked CmEnv into the generic "empty, singleton, many" structure. This isn't great, really GenMap should be more generic than that. The insight: we've defined the key wrong: the key should be *equipped* with the alpha-renaming information (CmEnv) and a TrieMap queried with this. This is what the DeBruijn constructor does. Now, when we define TrieMap instances, we don't have to synthesize an emptyCME to pass to the helper functions: we have all the information we need. To make a recursive call, we construct a new DeBruijn with the updated CME and then call lookupTM on that. We can even define a plain old Eq instance on DeBruijn respecting alpha-renaming. There are number of other good knock-on effects. This patch does add a bit of boxing and unboxing, but nothing the optimizer shouldn't be able to eliminate. Signed-off-by: Edward Z. Yang <ezyang@cs.stanford.edu> Test Plan: validate Reviewers: simonpj, austin Subscribers: carter, thomie Differential Revision: https://phabricator.haskell.org/D608 GHC Trac Issues: #9960
* Generalize TrieMap compression to GenMap.Edward Z. Yang2015-01-071-49/+154
| | | | | | | | | | | | | | | | | I still haven't applied the optimization to anything besides TypeMap. Summary: Signed-off-by: Edward Z. Yang <ezyang@cs.stanford.edu> Depends On: D606 Reviewers: simonpj, austin Subscribers: carter, thomie Differential Revision: https://phabricator.haskell.org/D607 GHC Trac Issues: #9960
* Compress TypeMap TrieMap leaves with singleton constructor.Edward Z. Yang2015-01-071-1/+58
| | | | | | | | | | | | | | | | | | | | | | | | | Suppose we have a handful H of entries in a TrieMap, each with a very large key, size K. If you fold over such a TrieMap you'd expect time O(H). That would certainly be true of an association list! But with TrieMap we actually have to navigate down a long singleton structure to get to the elements, so it takes time O(K*H). The point of a TrieMap is that you need to navigate to the point where only one key remains, and then things should be fast. This is a starting point: we can improve the patch by generalizing the singleton constructor so it applies to CoercionMap and CoreMap; I'll do this in a later commit. Summary: Signed-off-by: Edward Z. Yang <ezyang@cs.stanford.edu> Test Plan: validate Reviewers: simonpj, austin Subscribers: carter, thomie Differential Revision: https://phabricator.haskell.org/D606 GHC Trac Issues: #9960
* Remove redundant constraints in the compiler itself, found by ↵Simon Peyton Jones2015-01-061-2/+2
| | | | -fwarn-redundant-constraints
* Add a provenance field to universal coercions.Iavor S. Diatchki2014-12-171-2/+5
| | | | | | | | | | | Universal coercions allow casting between arbitrary types, so it is a good idea to keep track where they came from, which now we can do by using the provenance field in `UnivCo`. This is also handy for type-checker plugins that provide functionality beyond what's expressible by GHC's standard coercions: such plugins can generate universal coercions, but they should still tag them, so that if something goes wrong we can link the casts to the plugin.
* Comments on TrieMap and unifier.Edward Z. Yang2014-12-041-0/+7
| | | | Signed-off-by: Edward Z. Yang <ezyang@cs.stanford.edu>
* compiler: de-lhs coreSyn/Austin Seipp2014-12-031-0/+829
Signed-off-by: Austin Seipp <austin@well-typed.com>
View Lorry Controller Status