[eeps] EEP XXX: Pattern-test operator

[Robert Virding]

The actual pattern match compiler does a pretty straight forward
compilation of guards. It the optimiser which does some very weird
things and seems pretty incomprehensible. One though I had when doing
the pattern match compiler was whether we could instead move patterns
in the head explicitly into the guard, have everything there, and work
on that. That would optimise things like type tests in the guard. And
in the case variable binding. There was a paper describing this but I
can't remember it's name or author.

I would personally like to have variable binding in the guards. I have
a current use for it, so hurry up. :-)

Robert

On 19 April 2012 00:00, Erik Søe Sørensen <eriksoe@REDACTED> wrote:
> Guards seem to be given a rather stepmotherly treatment in the compiler...
> whether any decent code is generated appear to be entirely up to the mercy
> of the peephole optimizer. That's worse than I'd imagined.
>
> For instance,
>   g3(X) when X=:=foo orelse
>          X=:=bar orelse
>          X=:=baz -> ok.
> generates the rather asymmetric
>
> {select_val,{x,0},{f,11},{list,[{atom,foo},{f,12},{atom,bar},{f,12}]}}.
>     {label,11}.
>       {test,is_eq_exact,{f,9},[{x,0},{atom,baz}]}.
>     {label,12}.
>       {move,{atom,ok},{x,0}}.
>       return.
>
> And worse, in some cases like
>   h(X,Y) when (X=:=a andalso Y>0) -> aa;
>   h(X,Y) when (X=:=b andalso Y>0) -> bb;
>   h(X,Y) when (X=:=c andalso Y>0) -> cc.
> the size of the generated code is quadratic in the size of the source code:
>     {select_val,{x,0},
>                 {f,29},
>                 {list,[{atom,a},{f,31},{atom,b},{f,33},{atom,c},{f,35}]}}.
>   {label,31}.
>     {test,is_lt,{f,32},[{integer,0},{x,1}]}.
>     {move,{atom,aa},{x,0}}.
>     return.
>   {label,32}.
>     {select_val,{x,0},{f,29},{list,[{atom,b},{f,33},{atom,c},{f,35}]}}.
>   {label,33}.
>     {test,is_lt,{f,34},[{integer,0},{x,1}]}.
>     {move,{atom,bb},{x,0}}.
>     return.
>   {label,34}.
>     {test,is_eq_exact,{f,29},[{x,0},{atom,c}]}.
>   {label,35}.
>     {test,is_lt,{f,29},[{integer,0},{x,1}]}.
>     {move,{atom,cc},{x,0}}.
>     return.
> (Notice the tables in the select_val instructions.)
>
> This bad behaviour happens after the transition to beam code (in
> beam_dead:combine_eqs(), afaict).
> Looks like guards really would like to be taken into account during pattern
> match compilation... (no offence, Dijkstra).
>
> Anyway, the first roadblock appears to be that at the time when match
> compilation occurs (at the core->kernel representation transition), guards
> have already been flattened, meaning that what was at guard top-level in the
> source code is more difficult to find.
> For this reason, I'm considering a representation change of Core's clauses -
> from
>   -record(c_clause, {anno=[], pats,       % pats :: [Tree],
>                      guard,               % guard :: Tree,
>                      body}).              % body :: Tree
> to
>   -record(c_clause, {anno=[], pats,
>                      guard_pats :: [{Tree, Tree}], % {ExprToTest, Pattern}
>                      guard_exp :: Tree,
>                      body}).
> such that the guard is split into a part that can integrated into the
> pattern matching step, and a remainder that can't.
> For instance, the guard "when Y > 0, element(1,X) =:= foo" would be
> represented as
>   guard_pats = [{E1, P1}], guard_exp=E2
> where E1 = repr. of "element(1,X)", P1 = repr. of "'foo'", and E2 = repr. of
> "Y > 0".
>
> Handling "P ?= E" at guard top level would then follow quite naturally: by
> including {E,P} in guard_pats.
> (As for scoping, it is handled in an earlier phase.)
> Integrating type tests need a bit more, but that can be left for later if
> necessary.
>
> /Erik
>
> Den 18. apr. 2012 14.54 skrev Erik Søe Sørensen <eriksoe@REDACTED>:
> [snip]
>
>> Handling 'orelse' might be tricky, though; the current approach for ';'
>> appears to be to simply duplicate the clause and let a downstream optimizer
>> recognize the duplication, so I suppose that will work for 'orelse' as well.
>> (Looking at generated code, I notice that 'orelse' and 'andalso' in guards
>> gives rise (in R14B03) to some surprising - and suboptimal - code.)
>
>
>
>
> _______________________________________________
> eeps mailing list
> eeps@REDACTED
> http://erlang.org/mailman/listinfo/eeps
>