Generalize bounds checks.

If bounds check 0 <= index < length is not redundant we attempt to
replace it with a sequence of checks that guarantee

          0 <= LowerBound(index) < UpperBound(index) < length

and hoist all of those checks out of the enclosing loop.

Upper/Lower bounds are symbolic arithmetic expressions with +, -, *
operations and are computed based on discovered simple induction variables.

Simple induction variable is a variable that follows the pattern v1 <- phi(v0, v1 + 1)

BUG=
R=fschneider@google.com

Committed: https://code.google.com/p/dart/source/detail?r=40969

[Vyacheslav Egorov (Google), 2014-10-01 17:16:12]

vegorov@google.com changed reviewers:
+ fschneider@google.com

[Vyacheslav Egorov (Google), 2014-10-01 17:16:13]

PTAL

[Florian Schneider, 2014-10-06 16:04:53]

https://codereview.chromium.org/619903002/diff/60001/runtime/vm/flow_graph_ra...
File runtime/vm/flow_graph_range_analysis.cc (right):

https://codereview.chromium.org/619903002/diff/60001/runtime/vm/flow_graph_ra...
runtime/vm/flow_graph_range_analysis.cc:64: //                         v4 is
constrained to [v0, v2 + (v0 - v1)]
I think v4's range should be [v2, v2 + (v1 - v0)]

https://codereview.chromium.org/619903002/diff/60001/runtime/vm/flow_graph_ra...
runtime/vm/flow_graph_range_analysis.cc:70: //                      j is known
to be within [i0, j0 + (L - i0 - 1)]
Shouldn't j be between [j0, j0 + (L - i0 - 1)]?

https://codereview.chromium.org/619903002/diff/60001/runtime/vm/flow_graph_ra...
runtime/vm/flow_graph_range_analysis.cc:221: if (current->Type()->ToCid() ==
kSmiCid) {
Use IsIntegerDefinition here as well.

https://codereview.chromium.org/619903002/diff/60001/runtime/vm/flow_graph_ra...
runtime/vm/flow_graph_range_analysis.cc:265: if ((defn->ssa_temp_index() != -1)
&& IsIntegerDefinition(defn)) {
HasSSATempIndex() && IsIntegerDefinition(defn)

https://codereview.chromium.org/619903002/diff/60001/runtime/vm/flow_graph_ra...
runtime/vm/flow_graph_range_analysis.cc:428: // Mark true_constraint an
artificial use of boundary. This ensures
Update comment after removing the dependency use.

https://codereview.chromium.org/619903002/diff/60001/runtime/vm/flow_graph_ra...
runtime/vm/flow_graph_range_analysis.cc:442: // that constraint's range is
recalculated if boundary's range changes.
Update comment after removing the dependency use.

https://codereview.chromium.org/619903002/diff/60001/runtime/vm/flow_graph_ra...
runtime/vm/flow_graph_range_analysis.cc:461: if
(!IsIntegerDefinition(other_value->definition())) {
Why this code here? When do we have a comparison of an integer definition with
something thats not an integer definition?

https://codereview.chromium.org/619903002/diff/60001/runtime/vm/flow_graph_ra...
runtime/vm/flow_graph_range_analysis.cc:899: bool inputs_are_invariant = true;
Can you factor the code for invariance-computation out and use it here and in
LICM?

https://codereview.chromium.org/619903002/diff/60001/runtime/vm/flow_graph_ra...
runtime/vm/flow_graph_range_analysis.cc:924: instr->deopt_id_ =
last->GetDeoptId();
Maybe also set deopt_id of the environment to be consistent? I know we already
have this discrepancy in LICM and we should fix it there as well.

https://codereview.chromium.org/619903002/diff/60001/runtime/vm/flow_graph_ra...
runtime/vm/flow_graph_range_analysis.cc:930: static BlockEntryInstr*
FindPreHeader(BlockEntryInstr* header) {
I'd make this a member of BlockEntryInstr to avoid duplication of this function
(already defined in flow_graph_optimizer.cc)

https://codereview.chromium.org/619903002/diff/60001/runtime/vm/flow_graph_ra...
runtime/vm/flow_graph_range_analysis.cc:1009:
ConstructLowerBound(check->index()->definition(), check);
Isn't Simplify also needed here? If not, add a comment explaining why.

https://codereview.chromium.org/619903002/diff/60001/runtime/vm/flow_graph_ra...
runtime/vm/flow_graph_range_analysis.cc:1070: OS::Print("  => generalized check
was hoisted into B%" Pd "\n",
Make sure that all success / and failure cases are covered by tests.

https://codereview.chromium.org/619903002/diff/60001/runtime/vm/flow_graph_ra...
runtime/vm/flow_graph_range_analysis.cc:1106: return MakeBinaryOp(Token::kSUB,
symbol, -bound.offset());
Maybe simpler and just use

return MakeBinaryOp(Token::kADD, symbol, bound.offset());

for both cases?

https://codereview.chromium.org/619903002/diff/60001/runtime/vm/flow_graph_ra...
runtime/vm/flow_graph_range_analysis.cc:1215: Instruction* point) {
Indentation

https://codereview.chromium.org/619903002/diff/60001/runtime/vm/flow_graph_ra...
runtime/vm/flow_graph_range_analysis.cc:1239: const intptr_t c = left_const +
right_const;
What happens if c exceeds the smi range?

https://codereview.chromium.org/619903002/diff/60001/runtime/vm/flow_graph_ra...
runtime/vm/flow_graph_range_analysis.cc:1276: const intptr_t c = (left_const -
right_const);
What if c exceeds the smi range here?

https://codereview.chromium.org/619903002/diff/60001/runtime/vm/flow_graph_ra...
runtime/vm/flow_graph_range_analysis.cc:1334: // If possible find a set of
symbols that need to be non-negative to
For readability I'd replace non-negative with >= 0.

https://codereview.chromium.org/619903002/diff/60001/runtime/vm/flow_graph_ra...
runtime/vm/flow_graph_range_analysis.cc:1341: } else if (defn->HasSSATemp()) {
Just do if instead of else-if since there is a return the previous if-statement
ends in a return.

[Vyacheslav Egorov (Google), 2014-10-06 20:30:09]

PTAL

https://codereview.chromium.org/619903002/diff/60001/runtime/vm/flow_graph_ra...
File runtime/vm/flow_graph_range_analysis.cc (right):

https://codereview.chromium.org/619903002/diff/60001/runtime/vm/flow_graph_ra...
runtime/vm/flow_graph_range_analysis.cc:64: //                         v4 is
constrained to [v0, v2 + (v0 - v1)]
On 2014/10/06 16:04:53, Florian Schneider wrote:
> I think v4's range should be [v2, v2 + (v1 - v0)]

Done.

https://codereview.chromium.org/619903002/diff/60001/runtime/vm/flow_graph_ra...
runtime/vm/flow_graph_range_analysis.cc:70: //                      j is known
to be within [i0, j0 + (L - i0 - 1)]
On 2014/10/06 16:04:52, Florian Schneider wrote:
> Shouldn't j be between [j0, j0 + (L - i0 - 1)]?

Done.

https://codereview.chromium.org/619903002/diff/60001/runtime/vm/flow_graph_ra...
runtime/vm/flow_graph_range_analysis.cc:221: if (current->Type()->ToCid() ==
kSmiCid) {
On 2014/10/06 16:04:52, Florian Schneider wrote:
> Use IsIntegerDefinition here as well.

Done.

https://codereview.chromium.org/619903002/diff/60001/runtime/vm/flow_graph_ra...
runtime/vm/flow_graph_range_analysis.cc:265: if ((defn->ssa_temp_index() != -1)
&& IsIntegerDefinition(defn)) {
On 2014/10/06 16:04:53, Florian Schneider wrote:
> HasSSATempIndex() && IsIntegerDefinition(defn)

Done.

https://codereview.chromium.org/619903002/diff/60001/runtime/vm/flow_graph_ra...
runtime/vm/flow_graph_range_analysis.cc:428: // Mark true_constraint an
artificial use of boundary. This ensures
On 2014/10/06 16:04:52, Florian Schneider wrote:
> Update comment after removing the dependency use.

Done.

https://codereview.chromium.org/619903002/diff/60001/runtime/vm/flow_graph_ra...
runtime/vm/flow_graph_range_analysis.cc:442: // that constraint's range is
recalculated if boundary's range changes.
On 2014/10/06 16:04:53, Florian Schneider wrote:
> Update comment after removing the dependency use.

Done.

https://codereview.chromium.org/619903002/diff/60001/runtime/vm/flow_graph_ra...
runtime/vm/flow_graph_range_analysis.cc:461: if
(!IsIntegerDefinition(other_value->definition())) {
On 2014/10/06 16:04:52, Florian Schneider wrote:
> Why this code here? When do we have a comparison of an integer definition with
> something thats not an integer definition?

Imagine comparison with a parameter. Parameter by itself is not an integer
definition so it will not be constrained. 

This returns to the issue with CheckSmi that does not return a value we could
depend on.

https://codereview.chromium.org/619903002/diff/60001/runtime/vm/flow_graph_ra...
runtime/vm/flow_graph_range_analysis.cc:899: bool inputs_are_invariant = true;
On 2014/10/06 16:04:52, Florian Schneider wrote:
> Can you factor the code for invariance-computation out and use it here and in
> LICM?

LICM invariants computation is more involved because it also handles loads. 

I would prefer to refactor this stuff later - when I move Scheduler to a common
place other optimizations could use.

https://codereview.chromium.org/619903002/diff/60001/runtime/vm/flow_graph_ra...
runtime/vm/flow_graph_range_analysis.cc:924: instr->deopt_id_ =
last->GetDeoptId();
On 2014/10/06 16:04:52, Florian Schneider wrote:
> Maybe also set deopt_id of the environment to be consistent? I know we already
> have this discrepancy in LICM and we should fix it there as well.

Done.

https://codereview.chromium.org/619903002/diff/60001/runtime/vm/flow_graph_ra...
runtime/vm/flow_graph_range_analysis.cc:930: static BlockEntryInstr*
FindPreHeader(BlockEntryInstr* header) {
On 2014/10/06 16:04:53, Florian Schneider wrote:
> I'd make this a member of BlockEntryInstr to avoid duplication of this
function
> (already defined in flow_graph_optimizer.cc)

Done.

https://codereview.chromium.org/619903002/diff/60001/runtime/vm/flow_graph_ra...
runtime/vm/flow_graph_range_analysis.cc:1009:
ConstructLowerBound(check->index()->definition(), check);
On 2014/10/06 16:04:53, Florian Schneider wrote:
> Isn't Simplify also needed here? If not, add a comment explaining why.

Done.

https://codereview.chromium.org/619903002/diff/60001/runtime/vm/flow_graph_ra...
runtime/vm/flow_graph_range_analysis.cc:1070: OS::Print("  => generalized check
was hoisted into B%" Pd "\n",
On 2014/10/06 16:04:52, Florian Schneider wrote:
> Make sure that all success / and failure cases are covered by tests.

Done.

https://codereview.chromium.org/619903002/diff/60001/runtime/vm/flow_graph_ra...
runtime/vm/flow_graph_range_analysis.cc:1106: return MakeBinaryOp(Token::kSUB,
symbol, -bound.offset());
On 2014/10/06 16:04:53, Florian Schneider wrote:
> Maybe simpler and just use
> 
> return MakeBinaryOp(Token::kADD, symbol, bound.offset());
> 
> for both cases?

Done.

https://codereview.chromium.org/619903002/diff/60001/runtime/vm/flow_graph_ra...
runtime/vm/flow_graph_range_analysis.cc:1215: Instruction* point) {
On 2014/10/06 16:04:52, Florian Schneider wrote:
> Indentation

Done.

https://codereview.chromium.org/619903002/diff/60001/runtime/vm/flow_graph_ra...
runtime/vm/flow_graph_range_analysis.cc:1239: const intptr_t c = left_const +
right_const;
On 2014/10/06 16:04:52, Florian Schneider wrote:
> What happens if c exceeds the smi range?

Done.

https://codereview.chromium.org/619903002/diff/60001/runtime/vm/flow_graph_ra...
runtime/vm/flow_graph_range_analysis.cc:1276: const intptr_t c = (left_const -
right_const);
On 2014/10/06 16:04:52, Florian Schneider wrote:
> What if c exceeds the smi range here?

Done.

https://codereview.chromium.org/619903002/diff/60001/runtime/vm/flow_graph_ra...
runtime/vm/flow_graph_range_analysis.cc:1334: // If possible find a set of
symbols that need to be non-negative to
On 2014/10/06 16:04:52, Florian Schneider wrote:
> For readability I'd replace non-negative with >= 0.

I am not sure that this improves readability.

https://codereview.chromium.org/619903002/diff/60001/runtime/vm/flow_graph_ra...
runtime/vm/flow_graph_range_analysis.cc:1341: } else if (defn->HasSSATemp()) {
On 2014/10/06 16:04:52, Florian Schneider wrote:
> Just do if instead of else-if since there is a return the previous
if-statement
> ends in a return.

I find `else if` easier to read in general.

[Florian Schneider, 2014-10-07 11:40:49]

LGTM.

https://codereview.chromium.org/619903002/diff/100001/runtime/vm/flow_graph_r...
File runtime/vm/flow_graph_range_analysis.cc (right):

https://codereview.chromium.org/619903002/diff/100001/runtime/vm/flow_graph_r...
runtime/vm/flow_graph_range_analysis.cc:835: T* Emit(T* instruction,
Instruction* post_dominator) {
Maybe rename post_dominator to sink?

https://codereview.chromium.org/619903002/diff/100001/runtime/vm/flow_graph_r...
runtime/vm/flow_graph_range_analysis.cc:854: if (defn->ssa_temp_index() == -1) {
!HasSSATemp()

https://codereview.chromium.org/619903002/diff/100001/runtime/vm/flow_graph_r...
runtime/vm/flow_graph_range_analysis.cc:859:
instruction->InputAt(i)->set_definition(scheduled);
Do we care about stale entries in the use-list of defn?

FlowGraphInsertBefore::InsertBefore will update the use-lists of the
input-definitions. If scheduled is different from defn, the use-list defn will
still contain instruction even though it has been replaced.

https://codereview.chromium.org/619903002/diff/100001/runtime/vm/flow_graph_r...
runtime/vm/flow_graph_range_analysis.cc:861:
instruction->InputAt(i)->set_definition(UnwrapConstraint(defn));
Same issue as above.

https://codereview.chromium.org/619903002/diff/100001/runtime/vm/flow_graph_r...
runtime/vm/flow_graph_range_analysis.cc:1414: Instruction* post_dominator,
I'd rename post_dominator to

CheckArrayBoundInstr* check

https://codereview.chromium.org/619903002/diff/100001/tests/standalone/array_...
File tests/standalone/array_bounds_check_generalization_test.dart (right):

https://codereview.chromium.org/619903002/diff/100001/tests/standalone/array_...
tests/standalone/array_bounds_check_generalization_test.dart:11: for (var i = 0;
i < N; i++) {
Can you add a test with a nested loop as well? e.g.

for (var i = 0; i < N; i++) {
  for (var j = 0; j < M; j++) {
    e += a[i * M + j]
  }
}

[Vyacheslav Egorov (Google), 2014-10-07 18:50:49]

Committed patchset #6 (id:100001) manually as 40969 (presubmit successful).

[Vyacheslav Egorov (Google), 2014-10-07 18:57:27]

https://codereview.chromium.org/619903002/diff/100001/runtime/vm/flow_graph_r...
File runtime/vm/flow_graph_range_analysis.cc (right):

https://codereview.chromium.org/619903002/diff/100001/runtime/vm/flow_graph_r...
runtime/vm/flow_graph_range_analysis.cc:835: T* Emit(T* instruction,
Instruction* post_dominator) {
On 2014/10/07 11:40:48, Florian Schneider wrote:
> Maybe rename post_dominator to sink?

While I really like the name 'sink' and use it internally in the scheduler, I am
not sure that it communicates the meaning precisely. I will keep post_dominator
here, in the public interface, for clarity (for now).

https://codereview.chromium.org/619903002/diff/100001/runtime/vm/flow_graph_r...
runtime/vm/flow_graph_range_analysis.cc:854: if (defn->ssa_temp_index() == -1) {
On 2014/10/07 11:40:48, Florian Schneider wrote:
> !HasSSATemp()

Done.

https://codereview.chromium.org/619903002/diff/100001/runtime/vm/flow_graph_r...
runtime/vm/flow_graph_range_analysis.cc:859:
instruction->InputAt(i)->set_definition(scheduled);
On 2014/10/07 11:40:48, Florian Schneider wrote:
> Do we care about stale entries in the use-list of defn?
> 
> FlowGraphInsertBefore::InsertBefore will update the use-lists of the
> input-definitions. If scheduled is different from defn, the use-list defn will
> still contain instruction even though it has been replaced.

Instruction itself is not in the graph - which means it's uses are not
participating in the use lists until it is scheduled.

This is why it is safe to do this replacement. 

I will add a comment and an assertion.

https://codereview.chromium.org/619903002/diff/100001/runtime/vm/flow_graph_r...
runtime/vm/flow_graph_range_analysis.cc:861:
instruction->InputAt(i)->set_definition(UnwrapConstraint(defn));
On 2014/10/07 11:40:48, Florian Schneider wrote:
> Same issue as above.

Same answer as above :)

https://codereview.chromium.org/619903002/diff/100001/runtime/vm/flow_graph_r...
runtime/vm/flow_graph_range_analysis.cc:1414: Instruction* post_dominator,
On 2014/10/07 11:40:48, Florian Schneider wrote:
> I'd rename post_dominator to
> 
> CheckArrayBoundInstr* check

It does not have to be CheckArrayBoundInstr though. Can be something else and
this code will still continue to work.

https://codereview.chromium.org/619903002/diff/100001/tests/standalone/array_...
File tests/standalone/array_bounds_check_generalization_test.dart (right):

https://codereview.chromium.org/619903002/diff/100001/tests/standalone/array_...
tests/standalone/array_bounds_check_generalization_test.dart:11: for (var i = 0;
i < N; i++) {
On 2014/10/07 11:40:48, Florian Schneider wrote:
> Can you add a test with a nested loop as well? e.g.
> 
> for (var i = 0; i < N; i++) {
>   for (var j = 0; j < M; j++) {
>     e += a[i * M + j]
>   }
> }

Done

[regis, 2014-12-17 22:00:38]

regis@google.com changed reviewers:
+ regis@google.com, srdjan@google.com

[regis, 2014-12-17 22:00:39]

https://codereview.chromium.org/619903002/diff/100001/runtime/vm/intermediate...
File runtime/vm/intermediate_language_ia32.cc (right):

https://codereview.chromium.org/619903002/diff/100001/runtime/vm/intermediate...
runtime/vm/intermediate_language_ia32.cc:5613: }
Slava,

I stumbled upon this code and do not quite understand how it can be correct. If
both index and length are Smi::kMaxValue (highly improbable, but still), then we
will emit a test instruction instead of the compare. We will not deopt, because
index is not negative, but we should.

What am I missing?

Thanks,
Regis