Use type information to eliminate unnecessary bitwise-and operations.

Use type information to eliminate unnecessary bitwise-and operations.

BUG=

[dougc, 2015-04-20 11:19:45]

dtc-v8@scieneer.com changed reviewers:
+ titzer@chromium.org

[dougc, 2015-04-20 11:55:23]

This is a WIP patch with a request for help on how appropriate this solution is?

The goal is to elimination a redundant bitwise-and operation e.g.
(a&0xff)&0xffff => a&0xff, but for more general cases in which the bitwise-and
operation is derived to be redundant by type information. Such masking is added
with asm.js pointer-masking patterns and is sometimes redundant. The code writer
can not always assume that the mask can be avoided because the type derivation
capabilities vary between JS implementations.

Is js-typed-lowering an appropriate place to perform this operation?

Can it be assumed that a constant has already been canonicalized to the rhs at
this point?

Embarrassingly the patch only transforms the mask to -1 which allows it to be
optimized away later. It would be preferred to Replace the node with one of its
arguments if this could work, but an attempt to do so causes a later validation
check failure, so I could use some help here too?

[titzer, 2015-04-20 12:20:40]

https://codereview.chromium.org/1095063002/diff/1/src/compiler/js-typed-lower...
File src/compiler/js-typed-lowering.cc (right):

https://codereview.chromium.org/1095063002/diff/1/src/compiler/js-typed-lower...
src/compiler/js-typed-lowering.cc:373: Reduction
JSTypedLowering::ReduceBitwiseAnd(Node* node) {
I think you want to move this optimization to machine-operator-reducer. That
will make it more general and also avoid the problem you see below. 

JSTypedLowering has accumulated a lot of optimizations, but its primary role is
to replace JS nodes with simplified or machine operators, whereas
machine-operator-reducer has exactly one job, which is to optimize machine-level
operations.

https://codereview.chromium.org/1095063002/diff/1/src/compiler/js-typed-lower...
src/compiler/js-typed-lowering.cc:398: if (lhs_type->Min() >= 0 &&
lhs_type->Max() <= value) {
Yep, the problem is that JS operators have value and effect edges that aren't
handled correctly by this lowering, thus the validation problems.

[dougc, 2015-09-13 12:10:03]

On 2015/04/20 12:20:40, titzer wrote:
>
https://codereview.chromium.org/1095063002/diff/1/src/compiler/js-typed-lower...
> File src/compiler/js-typed-lowering.cc (right):
> 
>
https://codereview.chromium.org/1095063002/diff/1/src/compiler/js-typed-lower...
> src/compiler/js-typed-lowering.cc:373: Reduction
> JSTypedLowering::ReduceBitwiseAnd(Node* node) {
> I think you want to move this optimization to machine-operator-reducer. That
> will make it more general and also avoid the problem you see below. 

Tried this suggestion, moving this to machine-operator-reducer. It works in
part, but there are some issues that suggest this is too later to make use of
this type information.

For example, for one error there is a bit-and operation being used that appears
to be testing the low bit of a value that is the result of converting true or
false to a number, which I presume is checking for a tagged number. The type
information gives the input as having the range 0 to 1, so bit-and-ing this
input with 1 is redundant and is eliminated. But the bit-and is being applied to
a lower level representation, to a tagged number, which is not the value that
the type information applies to and this generates bad code. Does this sound
right? Does it suggest another appropriate phase to perform transforms that
depend on type information? Or should the transform be guarding against being
applied to possibly tagger values?

[titzer, 2015-09-17 18:49:12]

On 2015/09/13 12:10:03, dougc wrote:
> On 2015/04/20 12:20:40, titzer wrote:
> >
>
https://codereview.chromium.org/1095063002/diff/1/src/compiler/js-typed-lower...
> > File src/compiler/js-typed-lowering.cc (right):
> > 
> >
>
https://codereview.chromium.org/1095063002/diff/1/src/compiler/js-typed-lower...
> > src/compiler/js-typed-lowering.cc:373: Reduction
> > JSTypedLowering::ReduceBitwiseAnd(Node* node) {
> > I think you want to move this optimization to machine-operator-reducer. That
> > will make it more general and also avoid the problem you see below. 
> 
> Tried this suggestion, moving this to machine-operator-reducer. It works in
> part, but there are some issues that suggest this is too later to make use of
> this type information.
> 
> For example, for one error there is a bit-and operation being used that
appears
> to be testing the low bit of a value that is the result of converting true or
> false to a number, which I presume is checking for a tagged number. The type
> information gives the input as having the range 0 to 1, so bit-and-ing this
> input with 1 is redundant and is eliminated. But the bit-and is being applied
to
> a lower level representation, to a tagged number, which is not the value that
> the type information applies to and this generates bad code. Does this sound
> right? Does it suggest another appropriate phase to perform transforms that
> depend on type information? Or should the transform be guarding against being
> applied to possibly tagger values?

Ah, yes. The range information is in terms of "semantic integer ranges" and not
in terms of raw machine ranges. So the and's with 1 that you are seeing are tag
checks. We will have to know the correct representation for this optimization to
make sense.

[titzer, 2016-03-10 10:13:09]

titzer@chromium.org changed reviewers:
- titzer@chromium.org