[eeps] EEP XXX: Pattern-test operator

[Erik Søe Sørensen]

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.)
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://erlang.org/pipermail/eeps/attachments/20120419/35b68092/attachment.htm>