928350 - IonMonkey: call collectRangeInfo before removing the range analysis beta nodes

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[Douglas Crosher [:dougc]]

Bug 894794 moved some uses of range information into the range analysis truncation stage and introduced 'collectRangeInfo'.

However 'collectRangeInfo' is called after removing the beta nodes so the range information that the beta nodes supported is not available to the 'collectRangeInfo' methods.

If the beta nodes were removed after the truncation stage, and after calls to 'collectRangeInfo', then more accurate range information would be available.

Comment 1

[Douglas Crosher [:dougc]]

Attachment: keep the range analysis beta nodes until after calls to collectRangeInfo

Comment 2

[Nicolas B. Pierron [:nbp]]

Comment on attachment 818970 [details] [diff] [review]
keep the range analysis beta nodes until after calls to collectRangeInfo

Review of attachment 818970 [details] [diff] [review]:
-----------------------------------------------------------------

::: js/src/jit/Ion.cpp
@@ +1297,5 @@
>          if (mir->shouldCancel("Range Analysis"))
>              return false;
>  
> +        if (!r.truncate())
> +            return false;

Moving the truncate above the removal of the beta nodes implies that we can no longer have any truncation working across branches because the Beta nodes are blocking the bottom-up propagation of truncation.

We need to either add MBeta::truncate and update removeBetaNodes, or modify AllUsesTruncate to walk across beta nodes.

Comment 3

[Dan Gohman [:sunfish]]

Attachment: range-preserve-beta-nodes.patch

I applied your patch, and then implemented one of nbp's suggestions, adding truncate and isOperandTruncated for MBeta. It mostly works, except that the truncate() phase occasionally inserts an MTruncateToInt32 before an MBeta node in a block, and then removeBetaNodes() doesn't see them. I guess that could be fixed by special-case handling, but it's a little ugly.

What if we instead just moved the collectRangeInfo() calls out of truncate() and into analyze(), at the end? Beta nodes are still around at that point, so we get what we want there, and this avoids interactions between beta nodes and truncate(). Attached is a simple patch which does this, and seems to work.

Comment 4

[Douglas Crosher [:dougc]]

(In reply to Dan Gohman [:sunfish] from comment #3)
...
> What if we instead just moved the collectRangeInfo() calls out of truncate()
> and into analyze(), at the end? Beta nodes are still around at that point,
> so we get what we want there, and this avoids interactions between beta
> nodes and truncate(). Attached is a simple patch which does this, and seems
> to work.

Thank you for looking into this.  It does appear that reworking the calls to collectRangeInfo() might be an easier solution.  The truncate operations can modify the operation result ranges so moving the calls before truncation would not be equivalent and some users might need the truncated range, so perhaps it will be necessary to have pre-truncation and post-truncation collectRangeInfo() methods.  All the current collectRangeInfo() methods appear to be only looking at the input ranges, not the result range, so could all collect range info before truncation.

There appears to be more collection in edge case analysis, and perhaps this might benefit from the range info too.

Comment 5

[Douglas Crosher [:dougc]]

Attachment: Also collectRangeInfo before removing the beta nodes

Comment 6

[Nicolas B. Pierron [:nbp]]

(In reply to Douglas Crosher [:dougc] from comment #4)
> All the current collectRangeInfo() methods
> appear to be only looking at the input ranges, not the result range, so
> could all collect range info before truncation.

Which is exactly its goal.  The goal is to collect all the information about the ranges of each input before the removal of non-effectful logical instructions (same representation, different interpretation), otherwise we might have a logical error and miss the generation of some corner cases.

> The truncate operations can
> modify the operation result ranges so moving the calls before truncation
> would not be equivalent and some users might need the truncated range, so
> perhaps it will be necessary to have pre-truncation and post-truncation
> collectRangeInfo() methods.

Ideally, I think we want to move the collectRangeInfo() before any removal while keeping it after the truncate.
In practice, I do not think it matters yet.

Comment 7

[Douglas Crosher [:dougc]]

Attachment: Also collectRangeInfo before removing the beta nodes

fwiw try again with this approach

Comment 8

[Dan Gohman [:sunfish]]

(In reply to Douglas Crosher [:dougc] from comment #7)
> Created attachment 823200 [details] [diff] [review]
> Also collectRangeInfo before removing the beta nodes
> 
> fwiw try again with this approach

This patch looks good to me, except that it's not clear to me why post-truncation collection is useful. There isn't anything in this patch using it; do you have any examples in mind that would need this?

Comment 9

[Douglas Crosher [:dougc]]

(In reply to Dan Gohman [:sunfish] from comment #8)
> (In reply to Douglas Crosher [:dougc] from comment #7)
> > Created attachment 823200 [details] [diff] [review]
> > Also collectRangeInfo before removing the beta nodes
> > 
> > fwiw try again with this approach
> 
> This patch looks good to me, except that it's not clear to me why
> post-truncation collection is useful. There isn't anything in this patch
> using it; do you have any examples in mind that would need this?

There does not appear to be any immediate use for collecting range information post-truncation, however it seemed more respectful of comment 6 to keep this as an option.  I would be happy to remove this if it helps get something landed.

btw: there might still be some benefit to the approach in your patch - it might help specialize types within branches.  Sorry I have not had time to explore it yet.  I would be happy to split this bug if this helps.

Comment 10

[Dan Gohman [:sunfish]]

(In reply to Douglas Crosher [:dougc] from comment #9)
> (In reply to Dan Gohman [:sunfish] from comment #8)
> > (In reply to Douglas Crosher [:dougc] from comment #7)
> > > Created attachment 823200 [details] [diff] [review]
> > > Also collectRangeInfo before removing the beta nodes
> > > 
> > > fwiw try again with this approach
> > 
> > This patch looks good to me, except that it's not clear to me why
> > post-truncation collection is useful. There isn't anything in this patch
> > using it; do you have any examples in mind that would need this?
> 
> There does not appear to be any immediate use for collecting range
> information post-truncation, however it seemed more respectful of comment 6
> to keep this as an option.  I would be happy to remove this if it helps get
> something landed.

We can always add post-truncation analysis in the future. I'd like to see your current patch without the post-truncation parts. I think it's pretty simple, it implements the feature that this bug is about, and it doesn't obviously restrict flexibility in the future. Nicolas, do you agree?

Comment 11

[Nicolas B. Pierron [:nbp]]

(In reply to Dan Gohman [:sunfish] from comment #10)
> (In reply to Douglas Crosher [:dougc] from comment #9)
> > (In reply to Dan Gohman [:sunfish] from comment #8)
> > > (In reply to Douglas Crosher [:dougc] from comment #7)
> > > > Created attachment 823200 [details] [diff] [review]
> > > > Also collectRangeInfo before removing the beta nodes
> > > > 
> > > > fwiw try again with this approach
> > > 
> > > This patch looks good to me, except that it's not clear to me why
> > > post-truncation collection is useful. There isn't anything in this patch
> > > using it; do you have any examples in mind that would need this?
> > 
> > There does not appear to be any immediate use for collecting range
> > information post-truncation, however it seemed more respectful of comment 6
> > to keep this as an option.  I would be happy to remove this if it helps get
> > something landed.
> 
> We can always add post-truncation analysis in the future. I'd like to see
> your current patch without the post-truncation parts. I think it's pretty
> simple, it implements the feature that this bug is about, and it doesn't
> obviously restrict flexibility in the future. Nicolas, do you agree?

I think the collect-range post-truncation is only useful for instructions which are truncating their operands, as they might change range of their inputs. In any case, even if we have such instruction, we can always wrap the operands to get the same outcome.

So, I guess the post-truncation does not seems that useful after all.
So, if there is any need, we can add it later.

Comment 12

[Douglas Crosher [:dougc]]

Attachment: Replace which is called before removing the beta nodes

Update, removing the post-truncation methods, as requested.

collectRangeInfo has been renamed to collectRangeInfoPreTrunc but could revert this change?

Note that the logic in the methods has been changed slightly.  The intention is to position them work well when called multiple times, intersecting the collected information.  Happy to also keep them as-is.

Comment 13

[Dan Gohman [:sunfish]]

Comment on attachment 8337697 [details] [diff] [review]
Replace  which is called before removing the beta nodes

Review of attachment 8337697 [details] [diff] [review]:
-----------------------------------------------------------------

Renaming collectRangeInfo to collectRangeInfoPreTrunc looks good. Even without post-truncation analysis, this name emphasizes its purpose, to collect information from range analysis before truncation before truncation destroys it.

Changing the methods to intersect any previous information with new information also looks fine. We could potentially have other analyses or front-ends which know how to set some of these flags in the future, and we don't want range analysis overriding an earlier assertion.

::: js/src/jit/RangeAnalysis.cpp
@@ +1946,5 @@
>          }
>  
> +        // First pass at collecting range info - while the beta nodes are still
> +        // around and before truncation.  A later pass is made after truncation
> +        // which may change the operation result range.

The second sentence here is no longer current.

@@ +1963,1 @@
>                          ins->setSkipBoundsCheck(true);

Since you're already making a change here, please add braces around the body of this if, since the condition is still multi-line.

@@ +1969,1 @@
>                          ins->setSkipBoundsCheck(true);

Same here.

Comment 14

[Douglas Crosher [:dougc]]

Attachment: Replace collectRangeInfo with collectRangeInfoPreTrunc and called it before removing the beta nodes

Thank you for the review.  This patch address the feedback and rebases.

Comment 15

[Ryan VanderMeulen [:RyanVM]]

https://hg.mozilla.org/integration/mozilla-inbound/rev/623708981907

Comment 16

[Carsten Book [:Tomcat]]

https://hg.mozilla.org/mozilla-central/rev/623708981907