Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(202)

Side by Side Diff: runtime/vm/flow_graph_range_analysis.cc

Issue 982873004: Thread/Isolate refactoring: new(Isolate) -> new(Zone) (Closed) Base URL: http://dart.googlecode.com/svn/branches/bleeding_edge/dart/
Patch Set: Created 5 years, 9 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch | Annotate | Revision Log
OLDNEW
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
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
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
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
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
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
OLDNEW

Powered by Google App Engine
This is Rietveld 408576698