Changes between Version 1 and Version 2 of Commentary/Compiler/StrictnessAnalysis


Ignore:
Timestamp:
Oct 17, 2006 1:55:06 PM (8 years ago)
Author:
kirsten
Comment:

explain dmdTransform and dmdTypes

Legend:

Unmodified
Added
Removed
Modified
  • Commentary/Compiler/StrictnessAnalysis

    v1 v2  
    6262For a compound data value, the {{{Demands}}} type describes demands on its components. {{{Poly}}} means that we don't know anything about the expression's type. {{{Prod}}} says "this expression has a product type, and the demands on its components consist of the demands in the following list". If the {{{Coercion}}} is supplied, that means that this expression must be cast using the given coercion before it is evaluated. (!ToDo: explain this more.) 
    6363 
    64 (!ToDo: explain why all the above information is important, and what {{{DmdTypes}}} are.) 
     64(!ToDo: explain why all the above information is important) 
     65 
     66Though any expression can have a {{{Demand}}} associated with it, another datatype, {{{DmdType}}}, is associated with a function body. 
     67 
     68{{{ 
     69data DmdType = DmdType  
     70                    DmdEnv       
     71                    [Demand]     
     72                    DmdResult 
     73}}} 
     74A {{{DmdType}}} consists of a {{{DmdEnv}}} (which provides demands for all explicitly mentioned free variables in a functions body), a list of {{{Demand}}}s on the function's arguments, and a {{{DmdResult}}}, which indicates whether this function returns an explicitly constructed product: 
     75 
     76{{{ 
     77data DmdResult = TopRes -- Nothing known         
     78               | RetCPR -- Returns a constructed product 
     79               | BotRes -- Diverges or errors 
     80}}} 
     81 
     82The {{{dmdTransform}}} function takes a strictness environment, an [wiki:Commentary/Compiler/NameType Id] corresponding to a function, and a {{{Demand}}} representing demand on the function -- in a particular context -- and returns a {{{DmdType}}}, representing the function's demand type in this context. 
     83{{{ 
     84dmdTransform :: SigEnv           
     85             -> Id               
     86             -> Demand           
     87             -> DmdType          
     88}}} 
     89Strictness analysis is implemented as a backwards analysis, so {{{dmdTransform}}} takes the demand on a function's result (which was inferred based on how the function's result is used) and uses that to compute the demand type of this particular occurrence of the function itself. 
     90 
     91{{{dmdTransform}}} has four cases, depending on whether the function being analyzed is a [wiki:Commentary/Compiler/EntityTypes data constructor] worker, an imported (global) function, a local {{{let}}}-bound function, or "anything else" (e.g., a local lambda-bound function). 
     92 
     93The data constructor case checks whether this particular constructor call is saturated. If not, it returns {{{topDmdType}}}, indicating that we know nothing about the demand type. If so, it returns a {{{DmdType}}} with an empty environment (since there are no free variables), a list of arg-demands based on the {{{Demand}}} that was passed in to {{{dmdTransform}}} (that is, the demand on the result of the data constructor call), and a {{{DmdResult}}} taken from the constructor Id's strictness signature. 
     94 
     95There are a couple of tricky things about the list of arg-demands: 
     96 * If the result demand (i.e., the passed-in demand) has its box demanded, then we want to make sure the box is demanded in each of the demands for the args. (!ToDo: this may not be true) 
     97 * If the result demand is not strict, we want to use ''n'' copies of {{{topDmd}}} as the list of arg-demands, where ''n'' is this data constructor's arity. 
     98 
     99(!ToDo: explain the other cases of {{{dmdTransform}}})