Re: Understanding core2core optimisation pipeline
I'm resurrecting this 3-month old thread as I have some more questions about cardinality analysis. 1. I'm still a bit confused about terminology. Demand analysis, strictness analysis, cardinality analysis - do these three terms mean exactly the same thing? If no, then what are the differences? 2. First pass of full laziness is followed by floating in. At that stage we have not yet run the demand analysis and yet the code that does the floating-in checks whether a binder is one-shot (FloatIn.okToFloatInside called by FloatIn.fiExpr AnnLam case). This suggests that cardinality analysis is done earlier (but when?) and that demand analysis is not the same thing as cardinality analysis. 3. Does demand analyser perform any transformations? Or does it only annotate Core with demand information that can be used by subsequent passes? 4. BasicTypes module defines: data OneShotInfo = NoOneShotInfo -- ^ No information | ProbOneShot -- ^ The lambda is probably applied at most once | OneShotLam -- ^ The lambda is applied at most once. Do I understand correctly that `NoOneShotInfo` really means no information, ie. a binding annotated with this might in fact be one shot? If so, then do we have means of saying that a binding is certainly not a one-shot binding? 5. What is the purpose of SetLevels.lvlMFE function? Janek
The wiki page just went live:
https://ghc.haskell.org/trac/ghc/wiki/Commentary/Compiler/Core2CorePipeline
It's not yet perfect but it should be a good start.
Roughtly, a complete run of the simplifier means "run the simplifier repeatedly until nothing further happens". The iterations are the successive iterations of this loop. Currently there's a (rather arbitrary) limit of four such iterations before we give up and declare victory.
A limit or a default value for that limit?
To Ilya:
If you grep for the "late_dmd_anal" option variable in the compiler/simplCore/SimplCore.lhs module, you'll see that it triggers a phase close to the endo of getCoreToDo's tasks, which contains, in particular, the "CoreDoStrictness" pass. This is the "late" phase.
The paper said that the late pass is run to detect single-entry thunks and the reason why it is run late in the pipeline is that if it were run earlier this information could be invalidated by the transformations. But in the source code I see that this late pass is followed by the simplifier, which can invalidate the information. Also, the documentation for -flate-dmd-anal says: "We found some opportunities for discovering strictness that were not visible earlier; and optimisations like -fspec-constr can create functions with unused arguments which are eliminated by late demand analysis". This says nothing about single-netry thunks. So, is the single-entry thunk optimisation performed by GHC?
Janek
I implemented -flate-dmd-anal last year
Here's some outdated notes about my initial implementation. I share it in
order to indicate what thoughts were in my mind at the time (eg re
motivation).
https://ghc.haskell.org/trac/ghc/wiki/Frisby2013Q1#LateStrictnessWW
Aha! More up-to-date info here, including links to some of the older,
motivating tickets.
https://ghc.haskell.org/trac/ghc/ticket/7782
https://ghc.haskell.org/trac/ghc/wiki/LateDmd
Also, I now suspect this pass is risky: I think it may enter unused
arguments. I realize I didn't understand that stuff well enough at the
time. This definitely deserves some attention if people are using the flag.
To answer your question directly: I do not recall explicitly considering
single-entry thunks when implementing -flate-dmd-anal.
HTH.
On Thu, Oct 30, 2014 at 7:15 AM, Jan Stolarek
I'm resurrecting this 3-month old thread as I have some more questions about cardinality analysis.
1. I'm still a bit confused about terminology. Demand analysis, strictness analysis, cardinality analysis - do these three terms mean exactly the same thing? If no, then what are the differences?
2. First pass of full laziness is followed by floating in. At that stage we have not yet run the demand analysis and yet the code that does the floating-in checks whether a binder is one-shot (FloatIn.okToFloatInside called by FloatIn.fiExpr AnnLam case). This suggests that cardinality analysis is done earlier (but when?) and that demand analysis is not the same thing as cardinality analysis.
3. Does demand analyser perform any transformations? Or does it only annotate Core with demand information that can be used by subsequent passes?
4. BasicTypes module defines:
data OneShotInfo = NoOneShotInfo -- ^ No information | ProbOneShot -- ^ The lambda is probably applied at most once | OneShotLam -- ^ The lambda is applied at most once.
Do I understand correctly that `NoOneShotInfo` really means no information, ie. a binding annotated with this might in fact be one shot? If so, then do we have means of saying that a binding is certainly not a one-shot binding?
5. What is the purpose of SetLevels.lvlMFE function?
Janek
The wiki page just went live:
https://ghc.haskell.org/trac/ghc/wiki/Commentary/Compiler/Core2CorePipeline
It's not yet perfect but it should be a good start.
Roughtly, a complete run of the simplifier means "run the simplifier repeatedly until nothing further happens". The iterations are the successive iterations of this loop. Currently there's a (rather
arbitrary)
limit of four such iterations before we give up and declare victory.
A limit or a default value for that limit?
To Ilya:
If you grep for the "late_dmd_anal" option variable in the compiler/simplCore/SimplCore.lhs module, you'll see that it triggers a phase close to the endo of getCoreToDo's tasks, which contains, in particular, the "CoreDoStrictness" pass. This is the "late" phase.
The paper said that the late pass is run to detect single-entry thunks and the reason why it is run late in the pipeline is that if it were run earlier this information could be invalidated by the transformations. But in the source code I see that this late pass is followed by the simplifier, which can invalidate the information. Also, the documentation for -flate-dmd-anal says: "We found some opportunities for discovering strictness that were not visible earlier; and optimisations like -fspec-constr can create functions with unused arguments which are eliminated by late demand analysis". This says nothing about single-netry thunks. So, is the single-entry thunk optimisation performed by GHC?
Janek
ghc-devs mailing list ghc-devs@haskell.org http://www.haskell.org/mailman/listinfo/ghc-devs
Jan As people respond on this thread, would you be willing to capture what you learn in a wiki page in the Commentary? That way, your successor would have at least those questions answered right away. Somewhere under here https://ghc.haskell.org/trac/ghc/wiki/Commentary/Compiler would be good. | 1. I'm still a bit confused about terminology. Demand analysis, | strictness analysis, cardinality analysis - do these three terms mean | exactly the same thing? If no, then what are the differences? Strictness and demand analysis are the same. Cardinality analysis, strictness/demand analysis, and CPR analysis, are all different analyses, but they are all carried out by the same piece of code, namely DmdAnal. | 2. First pass of full laziness is followed by floating in. At that | stage we have not yet run the demand analysis and yet the code that | does the floating-in checks whether a binder is one-shot | (FloatIn.okToFloatInside called by FloatIn.fiExpr AnnLam case). This | suggests that cardinality analysis is done earlier (but when?) and | that demand analysis is not the same thing as cardinality analysis. Imported functions (eg foldr or build) have strictness and cardinality analysis info in their interface file signatures. That can in turn drive the attachment of one-shot info to binders. See one_shots = argsOneShots (idStrictness fun) n_val_args -- See Note [Use one-shot info] line 1345 of OccurAnal. | 3. Does demand analyser perform any transformations? Or does it only | annotate Core with demand information that can be used by subsequent | passes? The demand analyser simply annotates Core It is immediately followed by the worker/wrapper transformation, which uses the strictness annotations to transform Core using the w/w idea. | 4. BasicTypes module defines: | | data OneShotInfo = NoOneShotInfo -- ^ No information | | ProbOneShot -- ^ The lambda is probably applied | at most once | | OneShotLam -- ^ The lambda is applied at most | once. | | Do I understand correctly that `NoOneShotInfo` really means no | information, ie. a binding annotated with this might in fact be one | shot? Correct | If so, then do we have means of saying that a binding is | certainly not a one-shot binding? We do not. | 5. What is the purpose of SetLevels.lvlMFE function? It decides what level to float an expression out to. Simon |
Thank you for answers.
As people respond on this thread, would you be willing to capture what you learn in a wiki page in the Commentary? I already created such a wiki page some time ago:
Imported functions (eg foldr or build) have strictness and cardinality analysis info in their interface file signatures. That can in turn drive the attachment of one-shot info to binders. See one_shots = argsOneShots (idStrictness fun) n_val_args -- See Note [Use one-shot info] line 1345 of OccurAnal. And if we don't import anything then we're assuming NoOneShotInfo, which means we don't float in
https://ghc.haskell.org/trac/ghc/wiki/Commentary/Compiler/Core2CorePipeline But, since there are things I don't yet understant, this page is still incomplete. past lambdas? Janek
| And if we don't import anything then we're assuming NoOneShotInfo, | which means we don't float in past lambdas? correct
participants (3)
-
Jan Stolarek -
Nicolas Frisby -
Simon Peyton Jones