Recognize pattern (a << b) & c with c being a positive Smi and allow left shift to truncate the res…

Recognize pattern (a << b) & c with c being a positive Smi and allow left shift to truncate the result.
Committed: https://code.google.com/p/dart/source/detail?r=18859

[Vyacheslav Egorov (Google), 2013-02-20 00:37:06]

LGTM with comments addresses

I think it might have fit into Canonicalize pass but I have no strong feelings
about it. We do have some Canonicalize methods that consider more than a single
instruction.

https://codereview.chromium.org/12218181/diff/12001/runtime/vm/flow_graph_opt...
File runtime/vm/flow_graph_optimizer.cc (right):

https://codereview.chromium.org/12218181/diff/12001/runtime/vm/flow_graph_opt...
runtime/vm/flow_graph_optimizer.cc:193: // Both left and right may have only one
use.
The constant can have many uses it does not invalidate optimization.  You can
add a check here.

https://codereview.chromium.org/12218181/diff/12001/runtime/vm/flow_graph_opt...
runtime/vm/flow_graph_optimizer.cc:199: }
This does not check for environment uses. I think it will fail on something
like:

class A { foo(x) { print(x & 0xf); } }
class B { foo(x) { print(x); } }

bar (o) {
  o.foo(1 << 32);
} 

final a = new A(), b = new B();
for (var i = 0; i < 10000; i++) bar(a);
bar(b);

(if it does fail on this please add this to test suite).

https://codereview.chromium.org/12218181/diff/12001/runtime/vm/intermediate_l...
File runtime/vm/intermediate_language.cc (right):

https://codereview.chromium.org/12218181/diff/12001/runtime/vm/intermediate_l...
runtime/vm/intermediate_language.cc:138: BinarySmiOpInstr* other_op =
other->AsBinarySmiOp();
I think this should check for equality of the truncation flag.

https://codereview.chromium.org/12218181/diff/12001/runtime/vm/intermediate_l...
runtime/vm/intermediate_language.cc:859: return overflow_;
I think this can be just return true;

https://codereview.chromium.org/12218181/diff/12001/runtime/vm/intermediate_l...
File runtime/vm/intermediate_language_ia32.cc (right):

https://codereview.chromium.org/12218181/diff/12001/runtime/vm/intermediate_l...
runtime/vm/intermediate_language_ia32.cc:2040: }
Consider:

 2029       if (!is_truncating) {
 2032         Register temp = locs.temp(0).reg();
 2033         __ movl(temp, left);
 2034         __ shll(left, Immediate(value));
 2035         __ sarl(left, Immediate(value));
 2036         __ cmpl(left, temp);
 2037         __ j(NOT_EQUAL, deopt);  // Overflow.
               }
 2038         // Shift for result now we know there is no overflow.
 2039         __ shll(left, Immediate(value));

https://codereview.chromium.org/12218181/diff/12001/runtime/vm/intermediate_l...
runtime/vm/intermediate_language_ia32.cc:2164: summary->set_temp(0,
Location::RequiresRegister());
You can use summary->AddTemp() for simplicity. They you will not need
kNumTemps...

https://codereview.chromium.org/12218181/diff/12001/tests/standalone/left_shi...
File tests/standalone/left_shift_bit_and_op_test.dart (right):

https://codereview.chromium.org/12218181/diff/12001/tests/standalone/left_shi...
tests/standalone/left_shift_bit_and_op_test.dart:34: class A {
Please add a test that tests when (a << c) has multiple uses (one test for
normal ones, one test for environment ones).

[srdjan, 2013-02-21 00:47:17]

PTAL, moved the optimization before inlining. Also eagerly eliminate some Smi
checks (we can do more elimination in order to reduce number of allocated data
structures).

https://codereview.chromium.org/12218181/diff/12001/runtime/vm/flow_graph_opt...
File runtime/vm/flow_graph_optimizer.cc (right):

https://codereview.chromium.org/12218181/diff/12001/runtime/vm/flow_graph_opt...
runtime/vm/flow_graph_optimizer.cc:193: // Both left and right may have only one
use.
On 2013/02/20 00:37:06, Vyacheslav Egorov (Google) wrote:
> The constant can have many uses it does not invalidate optimization.  You can
> add a check here.

Done.

https://codereview.chromium.org/12218181/diff/12001/runtime/vm/flow_graph_opt...
runtime/vm/flow_graph_optimizer.cc:199: }
On 2013/02/20 00:37:06, Vyacheslav Egorov (Google) wrote:
> This does not check for environment uses. I think it will fail on something
> like:
> 
> class A { foo(x) { print(x & 0xf); } }
> class B { foo(x) { print(x); } }
> 
> bar (o) {
>   o.foo(1 << 32);
> } 
> 
> final a = new A(), b = new B();
> for (var i = 0; i < 10000; i++) bar(a);
> bar(b);
> 
> (if it does fail on this please add this to test suite).

It fails, thanks. Added to test suite. Punted on fixing it by moving this
optimization before inlining.
We need to figure out how to use environment uses in order to prevent the issue
above.

https://codereview.chromium.org/12218181/diff/12001/runtime/vm/intermediate_l...
File runtime/vm/intermediate_language.cc (right):

https://codereview.chromium.org/12218181/diff/12001/runtime/vm/intermediate_l...
runtime/vm/intermediate_language.cc:138: BinarySmiOpInstr* other_op =
other->AsBinarySmiOp();
On 2013/02/20 00:37:06, Vyacheslav Egorov (Google) wrote:
> I think this should check for equality of the truncation flag.

Done.

https://codereview.chromium.org/12218181/diff/12001/runtime/vm/intermediate_l...
runtime/vm/intermediate_language.cc:859: return overflow_;
On 2013/02/20 00:37:06, Vyacheslav Egorov (Google) wrote:
> I think this can be just return true;

Done.

https://codereview.chromium.org/12218181/diff/12001/runtime/vm/intermediate_l...
File runtime/vm/intermediate_language_ia32.cc (right):

https://codereview.chromium.org/12218181/diff/12001/runtime/vm/intermediate_l...
runtime/vm/intermediate_language_ia32.cc:2040: }
On 2013/02/20 00:37:06, Vyacheslav Egorov (Google) wrote:
> Consider:
> 
>  2029       if (!is_truncating) {
>  2032         Register temp = locs.temp(0).reg();
>  2033         __ movl(temp, left);
>  2034         __ shll(left, Immediate(value));
>  2035         __ sarl(left, Immediate(value));
>  2036         __ cmpl(left, temp);
>  2037         __ j(NOT_EQUAL, deopt);  // Overflow.
>                }
>  2038         // Shift for result now we know there is no overflow.
>  2039         __ shll(left, Immediate(value));
>  

Done.

[Florian Schneider, 2013-02-21 10:30:47]

DBC:

https://codereview.chromium.org/12218181/diff/20002/runtime/vm/intermediate_l...
File runtime/vm/intermediate_language.h (right):

https://codereview.chromium.org/12218181/diff/20002/runtime/vm/intermediate_l...
runtime/vm/intermediate_language.h:245: return (next_use_ == NULL) &&
(previous_use_ == NULL);
We have env_use_list to keep track of environment uses, so checking if the
definition has exactly one input use (and no environment uses) can be done
using:

return next_use_ == NULL
    && previous_use_ == NULL
    && definition_->env_use_list() == NULL;

[Kevin Millikin (Google), 2013-02-21 12:44:35]

More drive bys :)

https://codereview.chromium.org/12218181/diff/20002/runtime/vm/flow_graph_opt...
File runtime/vm/flow_graph_optimizer.cc (right):

https://codereview.chromium.org/12218181/diff/20002/runtime/vm/flow_graph_opt...
runtime/vm/flow_graph_optimizer.cc:189: void
FlowGraphOptimizer::OptimizeLeftShiftBitAndSmiOp(
I also think this kind of function is clearer if it takes the definition of left
and right as arguments, not a use of the definition.  Bonuses:

* You don't have to worry about copying or forgetting to copy use list nodes and
other issues of ownership.  Just make a new one!

* AsSmiLeftShiftInstruction and AsPositiveSmiConstValue aren't so bizarre.  As
it is, they coerce a use of a definition into a definition, which is not a
subclass of use of a defintion, so they do not actually fit the "AsXXX" pattern
and that seems warty.

https://codereview.chromium.org/12218181/diff/20002/runtime/vm/intermediate_l...
File runtime/vm/intermediate_language.h (right):

https://codereview.chromium.org/12218181/diff/20002/runtime/vm/intermediate_l...
runtime/vm/intermediate_language.h:245: return (next_use_ == NULL) &&
(previous_use_ == NULL);
On 2013/02/21 10:30:47, Florian Schneider wrote:
> We have env_use_list to keep track of environment uses, so checking if the
> definition has exactly one input use (and no environment uses) can be done
> using:
> 
> return next_use_ == NULL
>     && previous_use_ == NULL
>     && definition_->env_use_list() == NULL;

Drive by to the drive by.  I think it's more natural to just write:

return (definition()->input_use_list() == this) &&
  (next_use() == NULL) &&
  (definition()->env_use_list() == NULL);

Both your definition and the original answer true for use list nodes held in
instructions that have been removed from the graph, which just seems like a
strange behavior.

[Vyacheslav Egorov (Google), 2013-02-21 14:45:50]

tentative lgtm

https://codereview.chromium.org/12218181/diff/20002/runtime/vm/compiler.cc
File runtime/vm/compiler.cc (right):

https://codereview.chromium.org/12218181/diff/20002/runtime/vm/compiler.cc#ne...
runtime/vm/compiler.cc:183: // TODO(srdjan): Move de before inlinining until
environmenr use list can
"Moved", "environment" .

I find it very fragile. I could not come up with a way to break but it does not
mean there is none.

Florian & Kevin are sharing the same sentiment. I think we should discuss what
must be done to guarantee that we can use environment use list.

https://codereview.chromium.org/12218181/diff/20002/runtime/vm/flow_graph_opt...
File runtime/vm/flow_graph_optimizer.cc (right):

https://codereview.chromium.org/12218181/diff/20002/runtime/vm/flow_graph_opt...
runtime/vm/flow_graph_optimizer.cc:1038: if (left->Type()->ToCid() != kSmiCid) {
I suggest to create a method that inserts a check:

AddCheckSmi(...)

[srdjan, 2013-02-21 15:56:27]

https://codereview.chromium.org/12218181/diff/20002/runtime/vm/intermediate_l...
File runtime/vm/intermediate_language.h (right):

https://codereview.chromium.org/12218181/diff/20002/runtime/vm/intermediate_l...
runtime/vm/intermediate_language.h:245: return (next_use_ == NULL) &&
(previous_use_ == NULL);
On 2013/02/21 12:44:35, kmillikin wrote:
> On 2013/02/21 10:30:47, Florian Schneider wrote:
> > We have env_use_list to keep track of environment uses, so checking if the
> > definition has exactly one input use (and no environment uses) can be done
> > using:
> > 
> > return next_use_ == NULL
> >     && previous_use_ == NULL
> >     && definition_->env_use_list() == NULL;
> 
> Drive by to the drive by.  I think it's more natural to just write:
> 
> return (definition()->input_use_list() == this) &&
>   (next_use() == NULL) &&
>   (definition()->env_use_list() == NULL);
> 
> Both your definition and the original answer true for use list nodes held in
> instructions that have been removed from the graph, which just seems like a
> strange behavior.

We remove environment use list lazily in register allocator, i.e., env_use_list
is most of the time non-null.

[srdjan, 2013-02-21 21:55:31]

https://codereview.chromium.org/12218181/diff/12001/runtime/vm/intermediate_l...
File runtime/vm/intermediate_language_ia32.cc (right):

https://codereview.chromium.org/12218181/diff/12001/runtime/vm/intermediate_l...
runtime/vm/intermediate_language_ia32.cc:2164: summary->set_temp(0,
Location::RequiresRegister());
On 2013/02/20 00:37:06, Vyacheslav Egorov (Google) wrote:
> You can use summary->AddTemp() for simplicity. They you will not need
> kNumTemps... 

Done.

https://codereview.chromium.org/12218181/diff/20002/runtime/vm/compiler.cc
File runtime/vm/compiler.cc (right):

https://codereview.chromium.org/12218181/diff/20002/runtime/vm/compiler.cc#ne...
runtime/vm/compiler.cc:183: // TODO(srdjan): Move de before inlinining until
environmenr use list can
On 2013/02/21 14:45:50, Vyacheslav Egorov (Google) wrote:
> "Moved", "environment" .
> 
> I find it very fragile. I could not come up with a way to break but it does
not
> mean there is none.
> 
> Florian & Kevin are sharing the same sentiment. I think we should discuss what
> must be done to guarantee that we can use environment use list. 

Fixed spelling.  As discussed, added a flag (truncating_left_shift) to quickly
turn it off and reasoned that it is probably safe to do it before inlining.

https://codereview.chromium.org/12218181/diff/20002/runtime/vm/flow_graph_opt...
File runtime/vm/flow_graph_optimizer.cc (right):

https://codereview.chromium.org/12218181/diff/20002/runtime/vm/flow_graph_opt...
runtime/vm/flow_graph_optimizer.cc:189: void
FlowGraphOptimizer::OptimizeLeftShiftBitAndSmiOp(
On 2013/02/21 12:44:35, kmillikin wrote:
> I also think this kind of function is clearer if it takes the definition of
left
> and right as arguments, not a use of the definition.  Bonuses:
> 
> * You don't have to worry about copying or forgetting to copy use list nodes
and
> other issues of ownership.  Just make a new one!
> 
> * AsSmiLeftShiftInstruction and AsPositiveSmiConstValue aren't so bizarre.  As
> it is, they coerce a use of a definition into a definition, which is not a
> subclass of use of a defintion, so they do not actually fit the "AsXXX"
pattern
> and that seems warty.

Done.

https://codereview.chromium.org/12218181/diff/20002/runtime/vm/flow_graph_opt...
runtime/vm/flow_graph_optimizer.cc:1038: if (left->Type()->ToCid() != kSmiCid) {
On 2013/02/21 14:45:50, Vyacheslav Egorov (Google) wrote:
> I suggest to create a method that inserts a check:
> 
> AddCheckSmi(...)

Done.

[srdjan, 2013-02-21 22:24:51]

Committed patchset #8 manually as r18859 (presubmit successful).