| 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 |