Bug 142966 – Optimize typed array access with a masked index

• Status: RESOLVED
• Resolution: WONTFIX
• Component: JavaScriptCore

[dougc]

Emscripten now has an experimental mode that emits heap accesses as a[(i & mask) + c >> n] which keeps the index within bounds and is easy for the JS compiler to match and to optimize away bounds checks. The technique is also used in the asm.js jump tables as a[i&mask]. The technique is not asm.js specific and can be used in general JS code. The masked index can often be hoisted using Value Numbering etc, and a small constant offset can be emitted in the load or store instruction addressing mode.

[dougc]

Created attachment 249234 [details]
Optimize away bounds checks when given masked typed array indexes.

This is a proof-of-concept patch that implements this optimization for the Speculative-JIT and FTL.

The function indexInBounds has been added that matches the index masking patterns and determines if the index is within bounds. This has currently just been placed at the start of DFGConstantFoldingPhase.cpp, and I could use help on the appropriate file for such functions?

I noticed that the constant folding of CheckInBounds was not running consistently because the cfaFoundConstants block flag was not being set. The patch attempts to fix this by reworking the CheckInBounds handling in DFGAbstractInterpreterInlines.h.

Optimization of (i & -1) to identity has been added in strength reduction, and it appears that BitXor would be more appropriately grouped with BitXor. For Emscripten generated code it might be important to be able to efficiently optimize away the masking when the masks are set to -1.

Feedback and help with this first patch welcomed.

[dougc]

Created attachment 249235 [details]
Optimize away bounds checks when given masked typed array indexes.

Fix the patch to be relative to the source root.

[dougc]

Created attachment 249236 [details]
Optimize away bounds checks when given masked typed array indexes

Fix the missing prototype for indexInBounds(). Just place it in DFGAbstractInterpreterInlines.h for now.

[Filip Pizlo]

Comment on attachment 249236 [details]
Optimize away bounds checks when given masked typed array indexes

View in context: https://bugs.webkit.org/attachment.cgi?id=249236&action=review

Looks pretty good so far, but please move the helper to a more appropriate place.  And please don't remove the old flow-sensitive CheckInBounds elimination.

> Source/JavaScriptCore/dfg/DFGAbstractInterpreterInlines.h:2301
> +bool indexInBounds(Node* indexNode, int32_t length);

This declaration should be anywhere but here.  It's wrong to declare a method in X.h and define it in Y.h - at the very least, the header in which it's declared should correspond to the compilation module in which it is defined.  It's also wrong to make declarations in Inlines.h files; those are reserved for definitions of inline functions.  This isn't an inline function, and it's not a definition.

We often put such universal helpers in Graph.  You can continue this pattern.  Just add a method to Graph called indexInBounds().

> Source/JavaScriptCore/dfg/DFGConstantFoldingPhase.cpp:46
> +// Pattern match an array index expression returning true if it is known to be within
> +// bounds otherwise false. This matches a constant index, or a masked index with an
> +// optional constant offset, and optionally right shifted.
> +bool indexInBounds(Node* indexNode, int32_t length)

See above.  This definition is also in the wrong place.  It's an anti-pattern to define helpers inside the compilation module for a phase.  (We do make this mistake sometimes, but I'd really rather we stop doing it.)

We usually put such helpers in Graph.h/cpp.

> Source/JavaScriptCore/dfg/DFGConstantFoldingPhase.cpp:269
> -                JSValue left = m_state.forNode(node->child1()).value();
> +                // The length is obtained in strength reduction.
>                  JSValue right = m_state.forNode(node->child2()).value();
> -                if (left && right && left.isInt32() && right.isInt32()
> -                    && static_cast<uint32_t>(left.asInt32()) < static_cast<uint32_t>(right.asInt32())) {
> +                if (!right || !right.isInt32())
> +                    break;
> +                // Array length is known.
> +                int32_t length = right.asInt32();
> +                if (indexInBounds(node->child1().node(), length)) {

It appears that you're relying on the left child being folded to a constant, rather than it being proved constant.  There is a small difference, but it's a difference we prefer to deal with head-on.  The constant folder can theoretically produce flow-sensitive constants.  For example, a node may be constant only along some control flow path.  In that case, this will miss CheckInBounds where the index was such a partial constant.

Can you bring back the old folding rule, that did handle the flow-sensitive case?  I believe it's just a matter of not removing the old "if (left && right && left.isInt32() && right.isInt32() && static_cast<uint32_t>(left.asInt32()) < static_cast<uint32_t>(right.asInt32())..." thing.

[Filip Pizlo]

Comment on attachment 249236 [details]
Optimize away bounds checks when given masked typed array indexes

View in context: https://bugs.webkit.org/attachment.cgi?id=249236&action=review

> Source/JavaScriptCore/dfg/DFGConstantFoldingPhase.cpp:57
> +        JSValue shiftValue = indexNode->child2().node()->value.value();

It is an antipattern to access the abstract value of a node directly.  You should use AbstractInterpreter::forNode(node).  Also, we usually access the inferred constant value using m_value, not value().

> Source/JavaScriptCore/dfg/DFGConstantFoldingPhase.cpp:68
> +        JSValue offsetValue = indexNode->child2().node()->value.value();

Ditto.

> Source/JavaScriptCore/dfg/DFGConstantFoldingPhase.cpp:93
> +    JSValue maskValue = indexNode->child2().node()->value.value();

Ditto.

[Filip Pizlo]

Closing this.  My understanding is that this is not the direction that emscripten is taking.