Issue 10960014: Implement range analysis for smi values.

Issue 10960014: Implement range analysis for smi values. (Closed)

Created:
8 years, 3 months ago by Vyacheslav Egorov (Google)

Modified:
8 years, 3 months ago

Reviewers:
Florian Schneider, Kevin Millikin (Google), ngeoffray

CC:
reviews_dartlang.org, ngeoffray

Base URL:
https://dart.googlecode.com/svn/branches/bleeding_edge/dart

Visibility:
Public.

More Reviews

Description

Implement range analysis for smi values. And use it to eliminate overflow checks on + and - operations. Committed: https://code.google.com/p/dart/source/detail?r=12733

Patch Set 5 : addressed majority of comments #

Total comments: 6

Created: 8 years, 3 months ago

Download [raw] [tar.bz2]

	Unified diffs	Side-by-side diffs	Delta from patch set	Stats (+1016 lines, -64 lines)			Patch
M	runtime/vm/compiler.cc	View	1 2 3 4	1 chunk	+6 lines, -0 lines	1 comment	Download
M	runtime/vm/flow_graph_optimizer.h	View	1 2 3 4	2 chunks	+3 lines, -1 line	0 comments	Download
M	runtime/vm/flow_graph_optimizer.cc	View	1 2 3 4	7 chunks	+458 lines, -4 lines	2 comments	Download
M	runtime/vm/il_printer.cc	View	1 2 3 4	4 chunks	+45 lines, -0 lines	0 comments	Download
M	runtime/vm/intermediate_language.h	View	1 2 3 4	14 chunks	+311 lines, -4 lines	1 comment	Download
M	runtime/vm/intermediate_language.cc	View	1 2 3 4	6 chunks	+174 lines, -3 lines	2 comments	Download
M	runtime/vm/intermediate_language_ia32.cc	View	1 2 3 4	3 chunks	+7 lines, -13 lines	0 comments	Download
M	runtime/vm/intermediate_language_x64.cc	View	1 2 3 4	3 chunks	+8 lines, -14 lines	0 comments	Download
D	tests/language/deopt_hoisted_smi_check.dart	View	1 2 3 4	1 chunk	+0 lines, -20 lines	0 comments	Download
A +	tests/language/deopt_hoisted_smi_check_test.dart	View	1 2 3 4	1 chunk	+4 lines, -5 lines	0 comments	Download

Messages

Total messages: 5 (0 generated)

Expand Messages | Collapse Messages

Vyacheslav Egorov (Google)

This is ready for review. Please take a look.

8 years, 3 months ago (2012-09-20 19:00:33 UTC) #1

Florian Schneider

LGTM. The approach looks promising. Please also add TODOs where there are pieces missing. (e.g. ...

8 years, 3 months ago (2012-09-21 08:56:44 UTC) #2

Kevin Millikin (Google)

LGTM with comments. https://codereview.chromium.org/10960014/diff/7001/runtime/vm/flow_graph_optimizer.cc File runtime/vm/flow_graph_optimizer.cc (right): https://codereview.chromium.org/10960014/diff/7001/runtime/vm/flow_graph_optimizer.cc#newcode1223 runtime/vm/flow_graph_optimizer.cc:1223: // Iterate over smi values and ...

8 years, 3 months ago (2012-09-21 08:59:33 UTC) #3

Vyacheslav Egorov (Google)

Addressed comments and landed. Thanks for the review. (Still don't do all in one pass ...

8 years, 3 months ago (2012-09-21 20:08:06 UTC) #4

Addressed comments and landed. Thanks for the review.

(Still don't do all in one pass see comments below, plus accidentally did not
add TODOs).

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

https://codereview.chromium.org/10960014/diff/7001/runtime/vm/compiler.cc#new...
runtime/vm/compiler.cc:208: // TODO(vegorov): move optimistic smis unboxing into
Sminess propagator.
On 2012/09/21 08:56:44, Florian Schneider wrote:
> I don't understand this TODO. Can you make it clearer?

Done.

https://codereview.chromium.org/10960014/diff/7001/runtime/vm/flow_graph_opti...
File runtime/vm/flow_graph_optimizer.cc (right):

https://codereview.chromium.org/10960014/diff/7001/runtime/vm/flow_graph_opti...
runtime/vm/flow_graph_optimizer.cc:1223: // Iterate over smi values and
constraint them at branch successors.
On 2012/09/21 08:59:33, kmillikin wrote:
> constraint ==> constrain wherever used as a verb.

Done.

https://codereview.chromium.org/10960014/diff/7001/runtime/vm/flow_graph_opti...
runtime/vm/flow_graph_optimizer.cc:1235: ConstraintInstr*
ConstraintValue(Definition* defn,
On 2012/09/21 08:59:33, kmillikin wrote:
> ConstraintValue ==> ConstrainValue

Done.

https://codereview.chromium.org/10960014/diff/7001/runtime/vm/flow_graph_opti...
runtime/vm/flow_graph_optimizer.cc:1301: void RangeAnalysis::CollectSmiValues()
{
On 2012/09/21 08:59:33, kmillikin wrote:
> It seems more straightforward to directly insert constraints and mark smi
values
> in the bitvector.  I don't think you need the lists smi_values_ and
smi_checks_.

Agreed. I am going to commit as is and refactor it at a later stage. For now I
would like to keep this phases separated.

https://codereview.chromium.org/10960014/diff/7001/runtime/vm/flow_graph_opti...
runtime/vm/flow_graph_optimizer.cc:1371: if (use->instruction()->WasEliminated()
&&
On 2012/09/21 08:56:44, Florian Schneider wrote:
> Why do you need to skip those?

I don't want to compute ranges for things that are not connected to the graph
and do not affect code generation.

I removed this WasEliminated check and instead now recompute UseLists before I
start range analysis to ensure that they contain only live values.

https://codereview.chromium.org/10960014/diff/7001/runtime/vm/flow_graph_opti...
runtime/vm/flow_graph_optimizer.cc:1371: if (use->instruction()->WasEliminated()
&&
On 2012/09/21 08:59:33, kmillikin wrote:
> Can live phis be WasEliminated?  That's weird.

Our WasEliminated check just checks if previous() != NULL which is not true for
phis. 

In fact WasEliminated should be called IsLinked().

https://codereview.chromium.org/10960014/diff/7001/runtime/vm/flow_graph_opti...
runtime/vm/flow_graph_optimizer.cc:1457: ConstraintInstr*
RangeAnalysis::ConstraintValue(Definition* defn,
On 2012/09/21 08:56:44, Florian Schneider wrote:
> Suggested better name: InsertConstraintFor

Done.

https://codereview.chromium.org/10960014/diff/7001/runtime/vm/flow_graph_opti...
runtime/vm/flow_graph_optimizer.cc:1460: // No need to constraint constants.
On 2012/09/21 08:56:44, Florian Schneider wrote:
> s/constraint/constrain/

Done.

https://codereview.chromium.org/10960014/diff/7001/runtime/vm/flow_graph_opti...
runtime/vm/flow_graph_optimizer.cc:1486: Definition* boundary =
On 2012/09/21 08:59:33, kmillikin wrote:
> Since you test use_index() anyway, it's clearer to skip arithmetic to flip the
> operand:
> 
> if (use->use_index() == 0) {
>   boundary = ...;
>   op_kind = ...;
> } else {
>   boundary = ...;
>   op_kind = ...;
> }

Done.

https://codereview.chromium.org/10960014/diff/7001/runtime/vm/flow_graph_opti...
runtime/vm/flow_graph_optimizer.cc:1536: JoinEntryInstr* join =
block->AsJoinEntry();
On 2012/09/21 08:59:33, kmillikin wrote:
> It also seems like we could do this in the same walk of the graph as inserting
> constraints.

See above comment. I am going to commit as is now.

https://codereview.chromium.org/10960014/diff/7001/runtime/vm/flow_graph_opti...
runtime/vm/flow_graph_optimizer.cc:1576: inactive_worklist_->Clear();
On 2012/09/21 08:59:33, kmillikin wrote:
> This worklist is assumed empty here, right?

We don't pop anything from the worklist. We just process it from start til the
end, so it is not empty.

https://codereview.chromium.org/10960014/diff/7001/runtime/vm/flow_graph_opti...
runtime/vm/flow_graph_optimizer.cc:1610: (use_defn->ssa_temp_index() != -1) &&
On 2012/09/21 08:56:44, Florian Schneider wrote:
> Can we still have a Definition with an ssa_index == -1? We also have
use_kind()
> which has to be kValue in this case.

Yes, unfortunately we do. For example StoreIndexedInstr claims that it is a
definition with use_kind_ kValue but it has no SSA index because it obviously
produces no value.

https://codereview.chromium.org/10960014/diff/7001/runtime/vm/flow_graph_opti...
runtime/vm/flow_graph_optimizer.cc:1612: AddToWorklist(use_defn);
On 2012/09/21 08:59:33, kmillikin wrote:
> The operation of the worklist is not clear.  Here it appears to contain
> definitions that need to be analyzed due to one of their input ranges
changing.
> 
> When initialized it appears to contain definitions whose range has just
changed
> and so need to have their uses analyzed.
> 
> I guess it must work, but it seems to me that the algorithm would just empty
the
> initial worklist without concluding anything new.

Worklist contains definition for which InferRange should be invoked because one
of their inputs changed its range.

Initially we just place everything to the worklist because all ranges changed.

After that this loop will start placing only defs that depend on changed values
to the worklist.

When the fixpoint is reached nothing changes --- all InferRange return false ---
and worklist becomes empty.

https://codereview.chromium.org/10960014/diff/7001/runtime/vm/flow_graph_opti...
runtime/vm/flow_graph_optimizer.cc:1629: // constraints until
On 2012/09/21 08:56:44, Florian Schneider wrote:
> Until what?

Done.

https://codereview.chromium.org/10960014/diff/7001/runtime/vm/flow_graph_opti...
runtime/vm/flow_graph_optimizer.cc:2767: // Nothing to do. Is not used outside
of range analysis.
On 2012/09/21 08:56:44, Florian Schneider wrote:
> Maybe also make it UNREACHABLE()?

Done.

https://codereview.chromium.org/10960014/diff/7001/runtime/vm/intermediate_la...
File runtime/vm/intermediate_language.cc (right):

https://codereview.chromium.org/10960014/diff/7001/runtime/vm/intermediate_la...
runtime/vm/intermediate_language.cc:21: #include "vm/il_printer.h"
On 2012/09/21 08:56:44, Florian Schneider wrote:
> Why this include?

Debugging leftover. Removing.

https://codereview.chromium.org/10960014/diff/7001/runtime/vm/intermediate_la...
runtime/vm/intermediate_language.cc:1942: bool had_unranged_inputs =
has_unranged_inputs_;
On 2012/09/21 08:59:33, kmillikin wrote:
> Simpler to test the old value before changing it:
> 
> if ((range_ != NULL) && !has_unranged_inputs_) {
>   ...
> }
> has_unranged_inputs_ = has_unranged_inputs_ && has_unranged_inputs;
> 
> (Though, I think it should be monotone, so:
> 
> ASSERT(has_unranged_inputs <= has_unranged_inputs_);  // Ha ha.
> has_unranged_inputs_ = has_unranged_inputs;
> 
> )

Agreed. The control flow in this function was previously more convoluted (had
multiple exits) that is why I used an additional variable to keep previous
state.

https://codereview.chromium.org/10960014/diff/7001/runtime/vm/intermediate_la...
runtime/vm/intermediate_language.cc:1957: Range* lrange =
left()->definition()->range();
On 2012/09/21 08:56:44, Florian Schneider wrote:
> lrange and rrange are easy to confuse. How about just left_range and
> right_range?

Done.

https://codereview.chromium.org/10960014/diff/7001/runtime/vm/intermediate_la...
File runtime/vm/intermediate_language.h (right):

https://codereview.chromium.org/10960014/diff/7001/runtime/vm/intermediate_la...
runtime/vm/intermediate_language.h:505: Range* range_;
On 2012/09/21 08:56:44, Florian Schneider wrote:
> It seems that range_ can be made a member of Definition instead of
Instruction.

Done.

https://codereview.chromium.org/10960014/diff/7001/runtime/vm/intermediate_la...
runtime/vm/intermediate_language.h:505: Range* range_;
On 2012/09/21 08:59:33, kmillikin wrote:
> Does it buy us anything to make this a pointer instead of embedded?  The
virtual
> accessor and lazy initialization seems unnecessary.

Pointer allows use also to express _|_ state which is quite important for phi's
join function.

https://codereview.chromium.org/10960014/diff/7001/runtime/vm/intermediate_la...
runtime/vm/intermediate_language.h:956: void Advance() {
On 2012/09/21 08:59:33, kmillikin wrote:
> Simpler:
> 
> void Advance() {
>   ++index_;
>   while (!Done() && Current() == NULL) ++index_;
> }

This is how it looked initially. I just wanted to make a register promotion
manually :-)

    do {
      index_++;
    } while (!Done() && (Current() == NULL))

https://codereview.chromium.org/10960014/diff/7001/runtime/vm/intermediate_la...
runtime/vm/intermediate_language.h:957: if (Done()) return;
On 2012/09/21 08:56:44, Florian Schneider wrote:
> I'd rather write ASSERT(!Done());

Done.

https://codereview.chromium.org/10960014/diff/7001/runtime/vm/intermediate_la...
runtime/vm/intermediate_language.h:1229: bool has_unranged_inputs_;
On 2012/09/21 08:56:44, Florian Schneider wrote:
> Maybe rename to has_inputs_without_range_.

Done.

https://codereview.chromium.org/10960014/diff/7001/runtime/vm/intermediate_la...
runtime/vm/intermediate_language.h:1592: RangeBoundary() : kind_(kUnknown),
value_(0), offs_(0) { }
On 2012/09/21 08:59:33, kmillikin wrote:
> Please burn two characters to spell out 'offset'.
> 
> Alternatively, you could save an additional two and just call this 'of'.
> 
> :)

Done.

https://codereview.chromium.org/10960014/diff/7001/runtime/vm/intermediate_la...
runtime/vm/intermediate_language.h:1622: return
RangeBoundary::FromConstant((min_a < min_b) ? min_a : min_b);
On 2012/09/21 08:59:33, kmillikin wrote:
> You can spell this Utils::Minimum(min_a, min_b)

Done.

https://codereview.chromium.org/10960014/diff/7001/runtime/vm/intermediate_la...
runtime/vm/intermediate_language.h:1645: return (kind_ == other.kind_) &&
(value_ == other.value_);
On 2012/09/21 08:56:44, Florian Schneider wrote:
> && (offs_ == other.offs_)

Nice catch!

https://codereview.chromium.org/10960014/diff/7001/runtime/vm/intermediate_la...
runtime/vm/intermediate_language.h:1689: if (!Smi::IsValid64(result)) {
On 2012/09/21 08:56:44, Florian Schneider wrote:
> I think this should be Smi::IsValid(intptr_t value)

Yes. 64 is a leftover of an experiment.

https://codereview.chromium.org/10960014/diff/7001/runtime/vm/intermediate_la...
runtime/vm/intermediate_language.h:1701: if (!Smi::IsValid64(result)) {
On 2012/09/21 08:56:44, Florian Schneider wrote:
> Use Smi::IsValid(intptr_t value) here too.

Done.

https://codereview.chromium.org/10960014/diff/7001/runtime/vm/intermediate_la...
runtime/vm/intermediate_language.h:1856: virtual Range* range() {
On 2012/09/21 08:59:33, kmillikin wrote:
> This is disconcerting.  Simpler just to treat smi constants like smi
definitions
> in the analysis, implement InferRange for them, and make the range() accessor
> non-virtual.
> 
> Also, I find it disconcerting that we can safely call "range()" for all
> instructions except non-smi constants which ASSERT --- and that just seems to
be
> an artifact of the complicated lazy initialization and not treating smi
> constants as smi definitions.

Initially I wanted to make range() assert when you try to call it for a non-smi
value. But then it fell through. 

I refactored it to initialize range_ in the InferRange which asserts if you try
to apply it to a non-smi value.

https://codereview.chromium.org/10960014/diff/7001/runtime/vm/intermediate_la...
runtime/vm/intermediate_language.h:3495: virtual bool
AttributesEqual(Instruction* other) const;
On 2012/09/21 08:56:44, Florian Schneider wrote:
> You need to update AttributesEqual to check of overflow_ matches.

Yes, thanks for reminding me. I kept this in mind, but I forgot to do that. It
does not matter at this stage though because LICM and CSE precede RangeAnalysis.

https://codereview.chromium.org/10960014/diff/7001/runtime/vm/intermediate_la...
File runtime/vm/intermediate_language_ia32.cc (right):

https://codereview.chromium.org/10960014/diff/7001/runtime/vm/intermediate_la...
runtime/vm/intermediate_language_ia32.cc:1567: __ j(OVERFLOW, deopt);
On 2012/09/21 08:56:44, Florian Schneider wrote:
> if (deopt != NULL) __ j(OVERFLOW, deopt);

Done.

https://codereview.chromium.org/10960014/diff/7001/runtime/vm/intermediate_la...
File runtime/vm/intermediate_language_x64.cc (right):

https://codereview.chromium.org/10960014/diff/7001/runtime/vm/intermediate_la...
runtime/vm/intermediate_language_x64.cc:1595: __ j(OVERFLOW, deopt);
On 2012/09/21 08:56:44, Florian Schneider wrote:
> if (deopt != NULL)

Done.

ngeoffray

8 years, 3 months ago (2012-09-24 21:44:15 UTC) #5

DBC

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

https://codereview.chromium.org/10960014/diff/5009/runtime/vm/compiler.cc#new...
runtime/vm/compiler.cc:210: // making some phis smi.
The first part of the sentence makes you think it's a requirement, but the
second part makes you think it's actually just an optimization.

https://codereview.chromium.org/10960014/diff/5009/runtime/vm/flow_graph_opti...
File runtime/vm/flow_graph_optimizer.cc (right):

https://codereview.chromium.org/10960014/diff/5009/runtime/vm/flow_graph_opti...
runtime/vm/flow_graph_optimizer.cc:1284: // Worklists using during range
propagation.
using -> used

https://codereview.chromium.org/10960014/diff/5009/runtime/vm/flow_graph_opti...
runtime/vm/flow_graph_optimizer.cc:1456: Range* constraint_range,
Weird indentation.

https://codereview.chromium.org/10960014/diff/5009/runtime/vm/intermediate_la...
File runtime/vm/intermediate_language.cc (right):

https://codereview.chromium.org/10960014/diff/5009/runtime/vm/intermediate_la...
runtime/vm/intermediate_language.cc:1957: // If phi's range is growing widen it
in the direction of growth to
growing widen -> growing, widen

https://codereview.chromium.org/10960014/diff/5009/runtime/vm/intermediate_la...
runtime/vm/intermediate_language.cc:1958: // speedup convergence.
What's the check for 'growing' here? At first glance it looks like it is the
(range_ != NULL check), but what about phi instructions that use a loop phi?

https://codereview.chromium.org/10960014/diff/5009/runtime/vm/intermediate_la...
File runtime/vm/intermediate_language.h (right):

https://codereview.chromium.org/10960014/diff/5009/runtime/vm/intermediate_la...
runtime/vm/intermediate_language.h:1222: // Used to determine an interation of a
range analysis after all phi inputs
interation -> iteration

Expand Messages | Collapse Messages