summaryrefslogtreecommitdiff
path: root/compiler/simplCore/OccurAnal.lhs
Commit message (Collapse)AuthorAgeFilesLines
* compiler: de-lhs simplCore/Austin Seipp2014-12-031-1885/+0
| | | | Signed-off-by: Austin Seipp <austin@well-typed.com>
* Add comments explaining ProbOneShotSimon Peyton Jones2014-11-041-2/+2
|
* Fix comment typos: lll -> ll, THe -> TheJan Stolarek2014-10-141-1/+1
|
* Ensure that loop breakers are computed when glommingSimon Peyton Jones2014-09-231-12/+30
| | | | | | | | | | | | | | | | | 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.
* When finding loop breakers, distinguish INLINE from INLINEABLESimon Peyton Jones2014-08-291-36/+19
| | | | | | 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.
* Comments, white space, and rename "InlineRule" to "stable unfolding"Simon Peyton Jones2014-08-291-5/+5
| | | | | | 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
* Define mapUnionVarSet, and use itSimon Peyton Jones2014-08-291-5/+5
| | | | Call sites are much easier to understand than before
* This note's name has been fixedGabor Greif2014-08-191-1/+1
|
* Fix three problems with occurrence analysis on case alternatives.Andrew Farmer2014-08-181-21/+32
| | | | | | | | | | | | | | | | | | | | | 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
* Add LANGUAGE pragmas to compiler/ source filesHerbert Valerio Riedel2014-05-151-1/+2
| | | | | | | | | | | | | | | | | | 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.
* Squash some spelling issuesGabor Greif2014-01-261-3/+3
|
* Comment typos onlyGabor Greif2014-01-101-1/+1
|
* Improve the handling of used-once stuffSimon Peyton Jones2013-12-121-34/+31
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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.
* TyposKrzysztof Gogolewski2013-10-121-1/+1
|
* Remove the final vestiges of InlineWrappersSimon Peyton Jones2013-09-021-33/+37
| | | | | | | | | | | | | | | Part of Nick Frisby's patch (c080f727ba5f83921b842fcff71e9066adbdc250) 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.
* Fix comment typos that interfere with syntax highlightingPatrick Palka2013-08-301-1/+1
|
* simplified the .hi format and added the -flate-dmd-anal flag (fixes #7782)Nicolas Frisby2013-08-291-1/+1
| | | | cf http://ghc.haskell.org/trac/ghc/wiki/LateDmd
* Implement cardinality analysisSimon Peyton Jones2013-06-061-101/+107
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This major patch implements the cardinality analysis described in our paper "Higher order cardinality analysis". It is joint work with Ilya Sergey and Dimitrios Vytiniotis. The basic is augment the absence-analysis part of the demand analyser so that it can tell when something is used never at most once some other way The "at most once" information is used a) to enable transformations, and in particular to identify one-shot lambdas b) to allow updates on thunks to be omitted. There are two new flags, mainly there so you can do performance comparisons: -fkill-absence stops GHC doing absence analysis at all -fkill-one-shot stops GHC spotting one-shot lambdas and single-entry thunks The big changes are: * The Demand type is substantially refactored. In particular the UseDmd is factored as follows data UseDmd = UCall Count UseDmd | UProd [MaybeUsed] | UHead | Used data MaybeUsed = Abs | Use Count UseDmd data Count = One | Many Notice that UCall recurses straight to UseDmd, whereas UProd goes via MaybeUsed. The "Count" embodies the "at most once" or "many" idea. * The demand analyser itself was refactored a lot * The previously ad-hoc stuff in the occurrence analyser for foldr and build goes away entirely. Before if we had build (\cn -> ...x... ) then the "\cn" was hackily made one-shot (by spotting 'build' as special. That's essential to allow x to be inlined. Now the occurrence analyser propagates info gotten from 'build's stricness signature (so build isn't special); and that strictness sig is in turn derived entirely automatically. Much nicer! * The ticky stuff is improved to count single-entry thunks separately. One shortcoming is that there is no DEBUG way to spot if an allegedly-single-entry thunk is acually entered more than once. It would not be hard to generate a bit of code to check for this, and it would be reassuring. But it's fiddly and I have not done it. Despite all this fuss, the performance numbers are rather under-whelming. See the paper for more discussion. nucleic2 -0.8% -10.9% 0.10 0.10 +0.0% sphere -0.7% -1.5% 0.08 0.08 +0.0% -------------------------------------------------------------------------------- Min -4.7% -10.9% -9.3% -9.3% -50.0% Max -0.4% +0.5% +2.2% +2.3% +7.4% Geometric Mean -0.8% -0.2% -1.3% -1.3% -1.8% I don't quite know how much credence to place in the runtime changes, but movement seems generally in the right direction.
* Make 'SPECIALISE instance' work againSimon Peyton Jones2013-05-301-1/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This is a long-standing regression (Trac #7797), which meant that in particular the Eq [Char] instance does not get specialised. (The *methods* do, but the dictionary itself doesn't.) So when you call a function f :: Eq a => blah on a string type (ie a=[Char]), 7.6 passes a dictionary of un-specialised methods. This only matters when calling an overloaded function from a specialised context, but that does matter in some programs. I remember (though I cannot find the details) that Nick Frisby discovered this to be the source of some pretty solid performanc regresisons. Anyway it works now. The key change is that a DFunUnfolding now takes a form that is both simpler than before (the DFunArg type is eliminated) and more general: data Unfolding = ... | DFunUnfolding { -- The Unfolding of a DFunId -- See Note [DFun unfoldings] -- df = /\a1..am. \d1..dn. MkD t1 .. tk -- (op1 a1..am d1..dn) -- (op2 a1..am d1..dn) df_bndrs :: [Var], -- The bound variables [a1..m],[d1..dn] df_con :: DataCon, -- The dictionary data constructor (never a newtype datacon) df_args :: [CoreExpr] -- Args of the data con: types, superclasses and methods, } -- in positional order That in turn allowed me to re-enable the DFunUnfolding specialisation in DsBinds. Lots of details here in TcInstDcls: Note [SPECIALISE instance pragmas] I also did some refactoring, in particular to pass the InScopeSet to exprIsConApp_maybe (which in turn means it has to go to a RuleFun). NB: Interface file format has changed!
* improve dead code elimination in CorePrep (fixes #7796)Nicolas Frisby2013-03-281-13/+25
|
* Improve comments about dead code (thanks to Nick Frisby)Simon Peyton Jones2013-03-271-22/+13
|
* Merge branch 'refs/heads/vect-avoid' into vect-avoid-mergeManuel M T Chakravarty2013-02-061-6/+10
|\ | | | | | | | | | | | | | | | | Conflicts: compiler/rename/RnSource.lhs compiler/simplCore/OccurAnal.lhs compiler/vectorise/Vectorise/Exp.hs NB: Merging instead of rebasing for a change. During rebase Git got confused due to the lack of the submodules in my quite old fork.
| * Fix tidying of vectorised codeManuel M T Chakravarty2013-02-041-5/+10
| | | | | | | | | | * We need to keep the vectorised version of a variable alive while the original is alive. * This implies that the vectorised version needs to get into the iface if the original appears in an unfolding.
* | Comments onlySimon Peyton Jones2013-01-281-2/+2
| |
* | Simplify the binder-swap transformationSimon Peyton Jones2012-12-241-209/+46
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | The occurrence analyser implements the "binder-swap" transformation, described in Note [Binder swap] in OccAnal. For some reason I had implemeted an extremely complicated version, I believe intended to get as much as possible done in single simplifier pass. But it turned out (Trac #7258) that the 'getProxies' bit of this complicated code scaled rather non-linearly, and all by itself could consume half of the entire compile time. The patch dramatically simplifies the transformation, so that we simply swizzle case x of y { I# v -> e } to case x of y { I# v -> let x = y in e } I can't see any reason not to do this * Compiler allocation for #7258 with 200 fields goes down by 25% and compile time by 20% * The nofib figures do not budge * Quite a bit of complicated code goes away
* | Comments onlySimon Peyton Jones2012-10-311-5/+8
| |
* | Merge branch 'master' of http://darcs.haskell.org/ghcSimon Peyton Jones2012-10-221-257/+250
|\ \
| * | Fix typoIan Lynagh2012-10-201-1/+1
| | |
| * | Whitespace only in simplCore/OccurAnal.lhsIan Lynagh2012-10-191-256/+249
| |/
* | Deprecate Rank2Types and PolymorphicComponents, in favour of RankNTypesSimon Peyton Jones2012-10-191-1/+1
|/ | | | | We agreed that it's not worth the bother of trying to maintain all these distinct flags; RankNTypes will do the job fine. Trac #6032.
* Change how macros like ASSERT are definedIan Lynagh2012-06-051-1/+1
| | | | | By using Haskell's debugIsOn rather than CPP's "#ifdef DEBUG", we don't need to kludge things to keep the warning checker happy etc.
* Allow cases with empty alterantivesSimon Peyton Jones2012-05-021-1/+1
| | | | | | | | | | | | | | | | | | | | | | This patch allows, for the first time, case expressions with an empty list of alternatives. Max suggested the idea, and Trac #6067 showed that it is really quite important. So I've implemented the idea, fixing #6067. Main changes * See Note [Empty case alternatives] in CoreSyn * Various foldr1's become foldrs * IfaceCase does not record the type of the alternatives. I added IfaceECase for empty-alternative cases. * Core Lint does not complain about empty cases * MkCore.castBottomExpr constructs an empty-alternative case expression (case e of ty {}) * CoreToStg converts '(case e of {})' to just 'e'
* Fix Trac #5952, by changing the Outputable TyCon instance,Simon Peyton Jones2012-04-051-4/+5
| | | | | | | | | so that it does not print a quote in front of a promoted TyCon in a Kind. I also systematically renamed PromotedTypeTyCon --> PromotedTyCon PromotedDataTyCon --> PromotedDataCon
* Attempt to detect loops through imported function RULEsMax Bolingbroke2012-03-301-9/+102
| | | | | | | | | | | | This is motivated by the fact that before this change marking e.g. GHC.List.filter as INLINABLE caused the compiler to diverge when you tried to make use of the function. The response is to say that a RULE on an imported function introduces a dependency edge between the FVs of its LHS and RHS for the purposes of computing loop breakers. This will not perfectly prevent all those potential inlinings that could cause the compiler to non-terminate, but it works well enough for the particular case we are interested in.
* Revert "Add -faggressive-primops plus refactoring in CoreUtils" (#5780)Simon Marlow2012-01-161-2/+2
| | | | This reverts commit 601c983dd0bada6b49bdadd8f172fd4eacac4b0c.
* Add -faggressive-primops plus refactoring in CoreUtilsSimon Peyton Jones2012-01-131-2/+2
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | I'm experimenting with making GHC a bit more aggressive about a) dropping case expressions if the result is unused Simplify.rebuildCase, CaseElim equation b) floating case expressions inwards FloatIn.fiExpr, AnnCase In both cases the new behaviour is gotten with a static (debug) flag -faggressive-primops. The extra "aggression" is to allow discarding and floating in for side-effecting operations. See the new, extensive Note [PrimOp can_fail and has_side_effects] in PrimoOp. When discarding a case with unused binders, in the lifted-type case it's definitely ok if the scrutinee terminates; previously we were checking exprOkForSpeculation, which is significantly worse. So I wanted a new function CoreUtils.exprCertainlyTerminates. In doing this I ended up with a significant refactoring in CoreUtils. The new structure has quite a lot of nice sharing: exprIsCheap = exprIsCheap' isHNFApp exprIsExpandable = exprIsCheap' isConLikeApp exprIsHNF = exprIsHNFlike isHNFApp exprIsConLike = exprIsHNFlike isConLikeApp exprCertainlyTerminates = exprIsHNFlike isTerminatingApp
* GHC gets a new constraint solver. More efficient and smaller in size.Dimitrios Vytiniotis2011-11-161-2/+2
|
* Use -fwarn-tabs when validatingIan Lynagh2011-11-041-0/+7
| | | | | We only use it for "compiler" sources, i.e. not for libraries. Many modules have a -fno-warn-tabs kludge for now.
* Overhaul of infrastructure for profiling, coverage (HPC) and breakpointsSimon Marlow2011-11-021-12/+16
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | User visible changes ==================== Profilng -------- Flags renamed (the old ones are still accepted for now): OLD NEW --------- ------------ -auto-all -fprof-auto -auto -fprof-exported -caf-all -fprof-cafs New flags: -fprof-auto Annotates all bindings (not just top-level ones) with SCCs -fprof-top Annotates just top-level bindings with SCCs -fprof-exported Annotates just exported bindings with SCCs -fprof-no-count-entries Do not maintain entry counts when profiling (can make profiled code go faster; useful with heap profiling where entry counts are not used) Cost-centre stacks have a new semantics, which should in most cases result in more useful and intuitive profiles. If you find this not to be the case, please let me know. This is the area where I have been experimenting most, and the current solution is probably not the final version, however it does address all the outstanding bugs and seems to be better than GHC 7.2. Stack traces ------------ +RTS -xc now gives more information. If the exception originates from a CAF (as is common, because GHC tends to lift exceptions out to the top-level), then the RTS walks up the stack and reports the stack in the enclosing update frame(s). Result: +RTS -xc is much more useful now - but you still have to compile for profiling to get it. I've played around a little with adding 'head []' to GHC itself, and +RTS -xc does pinpoint the problem quite accurately. I plan to add more facilities for stack tracing (e.g. in GHCi) in the future. Coverage (HPC) -------------- * derived instances are now coloured yellow if they weren't used * likewise record field names * entry counts are more accurate (hpc --fun-entry-count) * tab width is now correct (markup was previously off in source with tabs) Internal changes ================ In Core, the Note constructor has been replaced by Tick (Tickish b) (Expr b) which is used to represent all the kinds of source annotation we support: profiling SCCs, HPC ticks, and GHCi breakpoints. Depending on the properties of the Tickish, different transformations apply to Tick. See CoreUtils.mkTick for details. Tickets ======= This commit closes the following tickets, test cases to follow: - Close #2552: not a bug, but the behaviour is now more intuitive (test is T2552) - Close #680 (test is T680) - Close #1531 (test is result001) - Close #949 (test is T949) - Close #2466: test case has bitrotted (doesn't compile against current version of vector-space package)
* Make a new type synonym CoreProgram = [CoreBind]Simon Peyton Jones2011-09-231-1/+1
| | | | | | | | | | | and comment its invariants in Note [CoreProgram] in CoreSyn I'm not totally convinced that CoreProgram is the right name (perhaps CoreTopBinds might better), but it is useful to have a clue that you are looking at the top-level bindings. This is only a matter of a type synonym change; no deep refactoring here.
* change how Integer's are handled in CoreIan Lynagh2011-09-131-1/+1
| | | | | | We now treat them as literals until CorePrep, when we finally convert them into the real Core representation. This makes it a lot simpler to implement built-in rules on them.
* Fix reversed test in OccurAnal (introduced in recent commit 428f8c3d)Simon Peyton Jones2011-08-021-10/+12
|
* Further simplification to OccurAnal, concerning "weak loop breakers"Simon Peyton Jones2011-08-011-34/+50
| | | | Fixes Trac #5359.
* The implementation of "weak loop breakers" was being too cleverSimon Peyton Jones2011-07-251-42/+58
| | | | | | | | | | The too-clever-ness meant that a variable could just go out of scope; this happened in building System.Consol.Haskeline.Backend.Terminfo in the haskeline library. This patch makes the weak-loopbreaker computation simpler, and a bit more conserative; which fixes the bug, and doesn't make any difference to the code in the end.
* Simplify the treatment of RULES in OccurAnalSimon Peyton Jones2011-07-211-359/+433
| | | | | | | | | | I realised that my recently-added cunning stuff about RULES for imported Ids was simply wrong, so this patch removes it. See Note [Rules for imported functions], which explains it all. This patch also does quite a bit of refactoring in the treatment of loop breakers.
* Take vectorisation declarations into account during the initial occurrence ↵Manuel M T Chakravarty2011-06-101-4/+5
| | | | analysis (right after desugaring).
* Don't discard usage info from coercion bindings!Simon Peyton Jones2011-05-091-5/+0
|
* This BIG PATCH contains most of the work for the New Coercion RepresentationSimon Peyton Jones2011-04-191-45/+56
| | | | | | | | | | | | | | See the paper "Practical aspects of evidence based compilation in System FC" * Coercion becomes a data type, distinct from Type * Coercions become value-level things, rather than type-level things, (although the value is zero bits wide, like the State token) A consequence is that a coerion abstraction increases the arity by 1 (just like a dictionary abstraction) * There is a new constructor in CoreExpr, namely Coercion, to inject coercions into terms
* Really zap case-binder occurrence info: solves #5028Ian Lynagh2011-04-011-3/+2
| | | | | | Converted from a darcs patch from Max Bolingbroke: Fri Apr 1 11:39:49 BST 2011 Max Bolingbroke <batterseapower@hotmail.com> * Really zap case-binder occurrence info: solves #5028
* Fix Trac #5028: zap occ info when doing the binder swapsimonpj@microsoft.com2011-03-211-5/+20
| | | | | | This fixes the Lint error, but still risks leaving stupid let { x=y } bindings in the code. But no time to fix that today. (Leave the ticket open for that reason.)
View Lorry Controller Status