OLD | NEW |
1 // Copyright (c) 2014, the Dart project authors. Please see the AUTHORS file | 1 // Copyright (c) 2014, the Dart project authors. Please see the AUTHORS file |
2 // for details. All rights reserved. Use of this source code is governed by a | 2 // for details. All rights reserved. Use of this source code is governed by a |
3 // BSD-style license that can be found in the LICENSE file. | 3 // BSD-style license that can be found in the LICENSE file. |
4 | 4 |
5 #include "vm/flow_graph_range_analysis.h" | 5 #include "vm/flow_graph_range_analysis.h" |
6 | 6 |
7 #include "vm/bit_vector.h" | 7 #include "vm/bit_vector.h" |
8 #include "vm/il_printer.h" | 8 #include "vm/il_printer.h" |
9 | 9 |
10 namespace dart { | 10 namespace dart { |
11 | 11 |
12 DEFINE_FLAG(bool, array_bounds_check_elimination, true, | 12 DEFINE_FLAG(bool, array_bounds_check_elimination, true, |
13 "Eliminate redundant bounds checks."); | 13 "Eliminate redundant bounds checks."); |
14 DEFINE_FLAG(bool, trace_range_analysis, false, "Trace range analysis progress"); | 14 DEFINE_FLAG(bool, trace_range_analysis, false, "Trace range analysis progress"); |
15 DEFINE_FLAG(bool, trace_integer_ir_selection, false, | 15 DEFINE_FLAG(bool, trace_integer_ir_selection, false, |
16 "Print integer IR selection optimization pass."); | 16 "Print integer IR selection optimization pass."); |
17 DECLARE_FLAG(bool, trace_constant_propagation); | 17 DECLARE_FLAG(bool, trace_constant_propagation); |
18 | 18 |
19 // Quick access to the locally defined isolate() method. | 19 // Quick access to the locally defined isolate() and zone() methods. |
20 #define I (isolate()) | 20 #define I (isolate()) |
| 21 #define Z (zone()) |
21 | 22 |
22 void RangeAnalysis::Analyze() { | 23 void RangeAnalysis::Analyze() { |
23 CollectValues(); | 24 CollectValues(); |
24 InsertConstraints(); | 25 InsertConstraints(); |
25 DiscoverSimpleInductionVariables(); | 26 DiscoverSimpleInductionVariables(); |
26 InferRanges(); | 27 InferRanges(); |
27 EliminateRedundantBoundsChecks(); | 28 EliminateRedundantBoundsChecks(); |
28 MarkUnreachableBlocks(); | 29 MarkUnreachableBlocks(); |
29 | 30 |
30 NarrowMintToInt32(); | 31 NarrowMintToInt32(); |
(...skipping 306 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
337 | 338 |
338 | 339 |
339 // Given a boundary (right operand) and a comparison operation return | 340 // Given a boundary (right operand) and a comparison operation return |
340 // a symbolic range constraint for the left operand of the comparison assuming | 341 // a symbolic range constraint for the left operand of the comparison assuming |
341 // that it evaluated to true. | 342 // that it evaluated to true. |
342 // For example for the comparison a < b symbol a is constrained with range | 343 // For example for the comparison a < b symbol a is constrained with range |
343 // [Smi::kMinValue, b - 1]. | 344 // [Smi::kMinValue, b - 1]. |
344 Range* RangeAnalysis::ConstraintSmiRange(Token::Kind op, Definition* boundary) { | 345 Range* RangeAnalysis::ConstraintSmiRange(Token::Kind op, Definition* boundary) { |
345 switch (op) { | 346 switch (op) { |
346 case Token::kEQ: | 347 case Token::kEQ: |
347 return new(I) Range(RangeBoundary::FromDefinition(boundary), | 348 return new(Z) Range(RangeBoundary::FromDefinition(boundary), |
348 RangeBoundary::FromDefinition(boundary)); | 349 RangeBoundary::FromDefinition(boundary)); |
349 case Token::kNE: | 350 case Token::kNE: |
350 return new(I) Range(Range::Full(RangeBoundary::kRangeBoundarySmi)); | 351 return new(Z) Range(Range::Full(RangeBoundary::kRangeBoundarySmi)); |
351 case Token::kLT: | 352 case Token::kLT: |
352 return new(I) Range(RangeBoundary::MinSmi(), | 353 return new(Z) Range(RangeBoundary::MinSmi(), |
353 RangeBoundary::FromDefinition(boundary, -1)); | 354 RangeBoundary::FromDefinition(boundary, -1)); |
354 case Token::kGT: | 355 case Token::kGT: |
355 return new(I) Range(RangeBoundary::FromDefinition(boundary, 1), | 356 return new(Z) Range(RangeBoundary::FromDefinition(boundary, 1), |
356 RangeBoundary::MaxSmi()); | 357 RangeBoundary::MaxSmi()); |
357 case Token::kLTE: | 358 case Token::kLTE: |
358 return new(I) Range(RangeBoundary::MinSmi(), | 359 return new(Z) Range(RangeBoundary::MinSmi(), |
359 RangeBoundary::FromDefinition(boundary)); | 360 RangeBoundary::FromDefinition(boundary)); |
360 case Token::kGTE: | 361 case Token::kGTE: |
361 return new(I) Range(RangeBoundary::FromDefinition(boundary), | 362 return new(Z) Range(RangeBoundary::FromDefinition(boundary), |
362 RangeBoundary::MaxSmi()); | 363 RangeBoundary::MaxSmi()); |
363 default: | 364 default: |
364 UNREACHABLE(); | 365 UNREACHABLE(); |
365 return NULL; | 366 return NULL; |
366 } | 367 } |
367 } | 368 } |
368 | 369 |
369 | 370 |
370 ConstraintInstr* RangeAnalysis::InsertConstraintFor(Value* use, | 371 ConstraintInstr* RangeAnalysis::InsertConstraintFor(Value* use, |
371 Definition* defn, | 372 Definition* defn, |
372 Range* constraint_range, | 373 Range* constraint_range, |
373 Instruction* after) { | 374 Instruction* after) { |
374 // No need to constrain constants. | 375 // No need to constrain constants. |
375 if (defn->IsConstant()) return NULL; | 376 if (defn->IsConstant()) return NULL; |
376 | 377 |
377 // Check if the value is already constrained to avoid inserting duplicated | 378 // Check if the value is already constrained to avoid inserting duplicated |
378 // constraints. | 379 // constraints. |
379 ConstraintInstr* constraint = after->next()->AsConstraint(); | 380 ConstraintInstr* constraint = after->next()->AsConstraint(); |
380 while (constraint != NULL) { | 381 while (constraint != NULL) { |
381 if ((constraint->value()->definition() == defn) && | 382 if ((constraint->value()->definition() == defn) && |
382 constraint->constraint()->Equals(constraint_range)) { | 383 constraint->constraint()->Equals(constraint_range)) { |
383 return NULL; | 384 return NULL; |
384 } | 385 } |
385 constraint = constraint->next()->AsConstraint(); | 386 constraint = constraint->next()->AsConstraint(); |
386 } | 387 } |
387 | 388 |
388 constraint = new(I) ConstraintInstr( | 389 constraint = new(Z) ConstraintInstr( |
389 use->CopyWithType(), constraint_range); | 390 use->CopyWithType(), constraint_range); |
390 | 391 |
391 flow_graph_->InsertAfter(after, constraint, NULL, FlowGraph::kValue); | 392 flow_graph_->InsertAfter(after, constraint, NULL, FlowGraph::kValue); |
392 RenameDominatedUses(defn, constraint, constraint); | 393 RenameDominatedUses(defn, constraint, constraint); |
393 constraints_.Add(constraint); | 394 constraints_.Add(constraint); |
394 return constraint; | 395 return constraint; |
395 } | 396 } |
396 | 397 |
397 | 398 |
398 bool RangeAnalysis::ConstrainValueAfterBranch(Value* use, Definition* defn) { | 399 bool RangeAnalysis::ConstrainValueAfterBranch(Value* use, Definition* defn) { |
(...skipping 63 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
462 | 463 |
463 void RangeAnalysis::ConstrainValueAfterCheckArrayBound( | 464 void RangeAnalysis::ConstrainValueAfterCheckArrayBound( |
464 Value* use, | 465 Value* use, |
465 Definition* defn) { | 466 Definition* defn) { |
466 CheckArrayBoundInstr* check = use->instruction()->AsCheckArrayBound(); | 467 CheckArrayBoundInstr* check = use->instruction()->AsCheckArrayBound(); |
467 intptr_t use_index = use->use_index(); | 468 intptr_t use_index = use->use_index(); |
468 | 469 |
469 Range* constraint_range = NULL; | 470 Range* constraint_range = NULL; |
470 if (use_index == CheckArrayBoundInstr::kIndexPos) { | 471 if (use_index == CheckArrayBoundInstr::kIndexPos) { |
471 Definition* length = check->length()->definition(); | 472 Definition* length = check->length()->definition(); |
472 constraint_range = new(I) Range( | 473 constraint_range = new(Z) Range( |
473 RangeBoundary::FromConstant(0), | 474 RangeBoundary::FromConstant(0), |
474 RangeBoundary::FromDefinition(length, -1)); | 475 RangeBoundary::FromDefinition(length, -1)); |
475 } else { | 476 } else { |
476 ASSERT(use_index == CheckArrayBoundInstr::kLengthPos); | 477 ASSERT(use_index == CheckArrayBoundInstr::kLengthPos); |
477 Definition* index = check->index()->definition(); | 478 Definition* index = check->index()->definition(); |
478 constraint_range = new(I) Range( | 479 constraint_range = new(Z) Range( |
479 RangeBoundary::FromDefinition(index, 1), | 480 RangeBoundary::FromDefinition(index, 1), |
480 RangeBoundary::MaxSmi()); | 481 RangeBoundary::MaxSmi()); |
481 } | 482 } |
482 InsertConstraintFor(use, defn, constraint_range, check); | 483 InsertConstraintFor(use, defn, constraint_range, check); |
483 } | 484 } |
484 | 485 |
485 | 486 |
486 void RangeAnalysis::InsertConstraints() { | 487 void RangeAnalysis::InsertConstraints() { |
487 for (intptr_t i = 0; i < values_.length(); i++) { | 488 for (intptr_t i = 0; i < values_.length(); i++) { |
488 InsertConstraintsFor(values_[i]); | 489 InsertConstraintsFor(values_[i]); |
(...skipping 1157 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1646 NarrowBinaryMintOp(binary_mint_ops_[i]); | 1647 NarrowBinaryMintOp(binary_mint_ops_[i]); |
1647 } | 1648 } |
1648 | 1649 |
1649 for (intptr_t i = 0; i < shift_mint_ops_.length(); i++) { | 1650 for (intptr_t i = 0; i < shift_mint_ops_.length(); i++) { |
1650 NarrowShiftMintOp(shift_mint_ops_[i]); | 1651 NarrowShiftMintOp(shift_mint_ops_[i]); |
1651 } | 1652 } |
1652 } | 1653 } |
1653 | 1654 |
1654 | 1655 |
1655 IntegerInstructionSelector::IntegerInstructionSelector(FlowGraph* flow_graph) | 1656 IntegerInstructionSelector::IntegerInstructionSelector(FlowGraph* flow_graph) |
1656 : flow_graph_(flow_graph), | 1657 : flow_graph_(flow_graph) { |
1657 isolate_(NULL) { | |
1658 ASSERT(flow_graph_ != NULL); | 1658 ASSERT(flow_graph_ != NULL); |
1659 isolate_ = flow_graph_->isolate(); | 1659 zone_ = flow_graph_->zone(); |
1660 ASSERT(isolate_ != NULL); | |
1661 Zone* zone = flow_graph_->zone(); | |
1662 selected_uint32_defs_ = | 1660 selected_uint32_defs_ = |
1663 new(zone) BitVector(zone, flow_graph_->current_ssa_temp_index()); | 1661 new(zone_) BitVector(zone_, flow_graph_->current_ssa_temp_index()); |
1664 } | 1662 } |
1665 | 1663 |
1666 | 1664 |
1667 void IntegerInstructionSelector::Select() { | 1665 void IntegerInstructionSelector::Select() { |
1668 if (FLAG_trace_integer_ir_selection) { | 1666 if (FLAG_trace_integer_ir_selection) { |
1669 ISL_Print("---- starting integer ir selection -------\n"); | 1667 ISL_Print("---- starting integer ir selection -------\n"); |
1670 } | 1668 } |
1671 FindPotentialUint32Definitions(); | 1669 FindPotentialUint32Definitions(); |
1672 FindUint32NarrowingDefinitions(); | 1670 FindUint32NarrowingDefinitions(); |
1673 Propagate(); | 1671 Propagate(); |
(...skipping 172 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1846 // Should only see mint definitions. | 1844 // Should only see mint definitions. |
1847 ASSERT(IsPotentialUint32Definition(def)); | 1845 ASSERT(IsPotentialUint32Definition(def)); |
1848 // Should not see constant instructions. | 1846 // Should not see constant instructions. |
1849 ASSERT(!def->IsConstant()); | 1847 ASSERT(!def->IsConstant()); |
1850 if (def->IsBinaryMintOp()) { | 1848 if (def->IsBinaryMintOp()) { |
1851 BinaryMintOpInstr* op = def->AsBinaryMintOp(); | 1849 BinaryMintOpInstr* op = def->AsBinaryMintOp(); |
1852 Token::Kind op_kind = op->op_kind(); | 1850 Token::Kind op_kind = op->op_kind(); |
1853 Value* left = op->left()->CopyWithType(); | 1851 Value* left = op->left()->CopyWithType(); |
1854 Value* right = op->right()->CopyWithType(); | 1852 Value* right = op->right()->CopyWithType(); |
1855 intptr_t deopt_id = op->DeoptimizationTarget(); | 1853 intptr_t deopt_id = op->DeoptimizationTarget(); |
1856 return new(I) BinaryUint32OpInstr(op_kind, left, right, deopt_id); | 1854 return new(Z) BinaryUint32OpInstr(op_kind, left, right, deopt_id); |
1857 } else if (def->IsBoxInt64()) { | 1855 } else if (def->IsBoxInt64()) { |
1858 Value* value = def->AsBoxInt64()->value()->CopyWithType(); | 1856 Value* value = def->AsBoxInt64()->value()->CopyWithType(); |
1859 return new(I) BoxUint32Instr(value); | 1857 return new(Z) BoxUint32Instr(value); |
1860 } else if (def->IsUnboxInt64()) { | 1858 } else if (def->IsUnboxInt64()) { |
1861 UnboxInstr* unbox = def->AsUnboxInt64(); | 1859 UnboxInstr* unbox = def->AsUnboxInt64(); |
1862 Value* value = unbox->value()->CopyWithType(); | 1860 Value* value = unbox->value()->CopyWithType(); |
1863 intptr_t deopt_id = unbox->DeoptimizationTarget(); | 1861 intptr_t deopt_id = unbox->DeoptimizationTarget(); |
1864 return new(I) UnboxUint32Instr(value, deopt_id); | 1862 return new(Z) UnboxUint32Instr(value, deopt_id); |
1865 } else if (def->IsUnaryMintOp()) { | 1863 } else if (def->IsUnaryMintOp()) { |
1866 UnaryMintOpInstr* op = def->AsUnaryMintOp(); | 1864 UnaryMintOpInstr* op = def->AsUnaryMintOp(); |
1867 Token::Kind op_kind = op->op_kind(); | 1865 Token::Kind op_kind = op->op_kind(); |
1868 Value* value = op->value()->CopyWithType(); | 1866 Value* value = op->value()->CopyWithType(); |
1869 intptr_t deopt_id = op->DeoptimizationTarget(); | 1867 intptr_t deopt_id = op->DeoptimizationTarget(); |
1870 return new(I) UnaryUint32OpInstr(op_kind, value, deopt_id); | 1868 return new(Z) UnaryUint32OpInstr(op_kind, value, deopt_id); |
1871 } else if (def->IsShiftMintOp()) { | 1869 } else if (def->IsShiftMintOp()) { |
1872 ShiftMintOpInstr* op = def->AsShiftMintOp(); | 1870 ShiftMintOpInstr* op = def->AsShiftMintOp(); |
1873 Token::Kind op_kind = op->op_kind(); | 1871 Token::Kind op_kind = op->op_kind(); |
1874 Value* left = op->left()->CopyWithType(); | 1872 Value* left = op->left()->CopyWithType(); |
1875 Value* right = op->right()->CopyWithType(); | 1873 Value* right = op->right()->CopyWithType(); |
1876 intptr_t deopt_id = op->DeoptimizationTarget(); | 1874 intptr_t deopt_id = op->DeoptimizationTarget(); |
1877 return new(I) ShiftUint32OpInstr(op_kind, left, right, deopt_id); | 1875 return new(Z) ShiftUint32OpInstr(op_kind, left, right, deopt_id); |
1878 } | 1876 } |
1879 UNREACHABLE(); | 1877 UNREACHABLE(); |
1880 return NULL; | 1878 return NULL; |
1881 } | 1879 } |
1882 | 1880 |
1883 | 1881 |
1884 void IntegerInstructionSelector::ReplaceInstructions() { | 1882 void IntegerInstructionSelector::ReplaceInstructions() { |
1885 if (FLAG_trace_integer_ir_selection) { | 1883 if (FLAG_trace_integer_ir_selection) { |
1886 ISL_Print("++++ Replacing instructions:\n"); | 1884 ISL_Print("++++ Replacing instructions:\n"); |
1887 } | 1885 } |
(...skipping 1276 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
3164 } | 3162 } |
3165 } while (CanonicalizeMaxBoundary(&max) || | 3163 } while (CanonicalizeMaxBoundary(&max) || |
3166 CanonicalizeMinBoundary(&canonical_length)); | 3164 CanonicalizeMinBoundary(&canonical_length)); |
3167 | 3165 |
3168 // Failed to prove that maximum is bounded with array length. | 3166 // Failed to prove that maximum is bounded with array length. |
3169 return false; | 3167 return false; |
3170 } | 3168 } |
3171 | 3169 |
3172 | 3170 |
3173 } // namespace dart | 3171 } // namespace dart |
OLD | NEW |