summaryrefslogtreecommitdiff
path: root/compiler/utils/Digraph.hs
Commit message (Collapse)AuthorAgeFilesLines
* Modules: Utils and Data (#13009)Sylvain Henry2020-04-261-524/+0
| | | | | | | Update Haddock submodule Metric Increase: haddock.compiler
* Modules: Types (#13009)Sylvain Henry2020-03-291-2/+2
| | | | | | | Update Haddock submodule Metric Increase: haddock.compiler
* Use concatMap(M) instead of `concat . map` and the monadic variantÖmer Sinan Ağacan2020-02-201-1/+1
|
* Fix typos, via a Levenshtein-style correctorBrian Wignall2020-01-041-1/+1
|
* Fix more typosBrian Wignall2019-12-021-1/+1
|
* Add haddock for Node in Digraph. [skip ci]klebinger.andreas@gmx.at2018-12-071-8/+16
| | | | | | | | | | | | Test Plan: make Reviewers: bgamari Reviewed By: bgamari Subscribers: rwbarton, carter Differential Revision: https://phabricator.haskell.org/D5378
* NCG: New code layout algorithm.Andreas Klebinger2018-11-171-0/+94
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: This patch implements a new code layout algorithm. It has been tested for x86 and is disabled on other platforms. Performance varies slightly be CPU/Machine but in general seems to be better by around 2%. Nofib shows only small differences of about +/- ~0.5% overall depending on flags/machine performance in other benchmarks improved significantly. Other benchmarks includes at least the benchmarks of: aeson, vector, megaparsec, attoparsec, containers, text and xeno. While the magnitude of gains differed three different CPUs where tested with all getting faster although to differing degrees. I tested: Sandy Bridge(Xeon), Haswell, Skylake * Library benchmark results summarized: * containers: ~1.5% faster * aeson: ~2% faster * megaparsec: ~2-5% faster * xml library benchmarks: 0.2%-1.1% faster * vector-benchmarks: 1-4% faster * text: 5.5% faster On average GHC compile times go down, as GHC compiled with the new layout is faster than the overhead introduced by using the new layout algorithm, Things this patch does: * Move code responsilbe for block layout in it's own module. * Move the NcgImpl Class into the NCGMonad module. * Extract a control flow graph from the input cmm. * Update this cfg to keep it in sync with changes during asm codegen. This has been tested on x64 but should work on x86. Other platforms still use the old codelayout. * Assign weights to the edges in the CFG based on type and limited static analysis which are then used for block layout. * Once we have the final code layout eliminate some redundant jumps. In particular turn a sequences of: jne .foo jmp .bar foo: into je bar foo: .. Test Plan: ci Reviewers: bgamari, jmct, jrtc27, simonmar, simonpj, RyanGlScott Reviewed By: RyanGlScott Subscribers: RyanGlScott, trommler, jmct, carter, thomie, rwbarton GHC Trac Issues: #15124 Differential Revision: https://phabricator.haskell.org/D4726
* Remove unused things from utils/DigraphDavid Feuer2018-05-131-89/+2
| | | | | | | | | | | | | | | | | `utils/Digraph` had a bunch of code that wasn't actually being used, much of which wasn't documented at all, some of which was clearly ill-considered, and some of which was documented as being inefficient. Remove all unused code from that module except for the obvious and innocuous `emptyG`. Reviewers: bgamari Reviewed By: bgamari Subscribers: rwbarton, thomie, carter Differential Revision: https://phabricator.haskell.org/D4676
* compiler: introduce custom "GhcPrelude" PreludeHerbert Valerio Riedel2017-09-191-0/+2
| | | | | | | | | | | | | | | | | | 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
* Fix typos in diagnostics, testsuite and commentsGabor Greif2017-09-071-2/+2
|
* Add Outputable instance for NodeMatthew Pickering2017-05-111-0/+3
| | | | | | | | | | Reviewers: austin, bgamari Reviewed By: bgamari Subscribers: rwbarton, thomie Differential Revision: https://phabricator.haskell.org/D3564
* Replace Digraph's Node type synonym with a data typeMatthew Pickering2017-04-041-14/+16
| | | | | | | | | | | | | This refactoring makes it more obvious when we are constructing a Node for the digraph rather than a less useful 3-tuple. Reviewers: austin, goldfire, bgamari, simonmar, dfeuer Reviewed By: dfeuer Subscribers: rwbarton, thomie Differential Revision: https://phabricator.haskell.org/D3414
* Typos in comments (and in a test)Gabor Greif2017-01-091-3/+3
|
* Typos in comments only [ci skip]Gabor Greif2016-11-281-3/+3
|
* Provide Uniquable version of SCCBartosz Nitka2016-06-231-22/+105
| | | | | | | | | | | | | | | | | | | | | | | | | | | 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
* Document SCC determinismBartosz Nitka2016-05-111-0/+15
| | | | | | | | | | | | | | | | | | | | | | 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
* Remove orphan Functor instance of Data.Graph.SCCÖmer Sinan Ağacan2015-11-171-10/+1
| | | | | | | | | | Reviewers: bgamari, austin Reviewed By: austin Subscribers: thomie Differential Revision: https://phabricator.haskell.org/D1481
* Make stronglyConnCompFromEdgedVertices deterministicBartosz Nitka2015-10-221-18/+15
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This makes it so the result of computing SCC's depends on the order the nodes were passed to it, but not on the order on the user provided key type. The key type is usually `Unique` which is known to be nondeterministic. Test Plan: `text` and `aeson` become deterministic after this ./validate Compare compile time for `text`: ``` $ cabal get text && cd text* && cabal sandbox init && cabal install --dependencies-only && time cabal build real 0m59.459s user 0m57.862s sys 0m1.185s $ cabal clean && time cabal build real 1m0.037s user 0m58.350s sys 0m1.199s $ cabal clean && time cabal build real 0m57.634s user 0m56.118s sys 0m1.202s $ cabal get text && cd text* && cabal sandbox init && cabal install --dependencies-only && time cabal build real 0m59.867s user 0m58.176s sys 0m1.188s $ cabal clean && time cabal build real 1m0.157s user 0m58.622s sys 0m1.177s $ cabal clean && time cabal build real 1m0.950s user 0m59.397s sys 0m1.083s ``` Reviewers: ezyang, simonmar, austin, bgamari Reviewed By: simonmar, bgamari Subscribers: thomie Differential Revision: https://phabricator.haskell.org/D1268 GHC Trac Issues: #4012
* Remove graphFromVerticesAndAdjacencyBartosz Nitka2015-09-211-19/+1
| | | | | | | | It's not used anywhere. Reviewed By: austin Differential Revision: https://phabricator.haskell.org/D1266
* Refactor Digraph to use Data.Graph when possibleEdward Z. Yang2015-03-091-263/+45
| | | | | | | | | | | | | | Summary: This just rewrites the IntGraph data type. Signed-off-by: Edward Z. Yang <ezyang@cs.stanford.edu> Test Plan: validate Reviewers: austin Subscribers: thomie Differential Revision: https://phabricator.haskell.org/D708
* Revert "Refactor Digraph to use Data.Graph when possible"Edward Z. Yang2015-03-091-36/+264
| | | | | | | This breaks the build with GHC 7.6 bootstrapping, since the Functor SCC instance is not available. This reverts commit c439af5f5baa2c8af3434652554135230edbf5c3.
* Refactor Digraph to use Data.Graph when possibleEdward Z. Yang2015-03-091-264/+36
| | | | | | | | | | | | | | Summary: This just rewrites the IntGraph data type. Signed-off-by: Edward Z. Yang <ezyang@cs.stanford.edu> Test Plan: validate Reviewers: austin Subscribers: thomie Differential Revision: https://phabricator.haskell.org/D708
* compiler: de-lhs utils/Austin Seipp2014-12-031-0/+652
Signed-off-by: Austin Seipp <austin@well-typed.com>
View Lorry Controller Status