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 { |
(...skipping 22 matching lines...) Expand all Loading... |
33 MarkUnreachableBlocks(); | 33 MarkUnreachableBlocks(); |
34 | 34 |
35 NarrowMintToInt32(); | 35 NarrowMintToInt32(); |
36 | 36 |
37 IntegerInstructionSelector iis(flow_graph_); | 37 IntegerInstructionSelector iis(flow_graph_); |
38 iis.Select(); | 38 iis.Select(); |
39 | 39 |
40 RemoveConstraints(); | 40 RemoveConstraints(); |
41 } | 41 } |
42 | 42 |
43 | |
44 static Definition* UnwrapConstraint(Definition* defn) { | 43 static Definition* UnwrapConstraint(Definition* defn) { |
45 while (defn->IsConstraint()) { | 44 while (defn->IsConstraint()) { |
46 defn = defn->AsConstraint()->value()->definition(); | 45 defn = defn->AsConstraint()->value()->definition(); |
47 } | 46 } |
48 return defn; | 47 return defn; |
49 } | 48 } |
50 | 49 |
51 | |
52 // Simple induction variable is a variable that satisfies the following pattern: | 50 // Simple induction variable is a variable that satisfies the following pattern: |
53 // | 51 // |
54 // v1 <- phi(v0, v1 + 1) | 52 // v1 <- phi(v0, v1 + 1) |
55 // | 53 // |
56 // If there are two simple induction variables in the same block and one of | 54 // If there are two simple induction variables in the same block and one of |
57 // them is constrained - then another one is constrained as well, e.g. | 55 // them is constrained - then another one is constrained as well, e.g. |
58 // from | 56 // from |
59 // | 57 // |
60 // B1: | 58 // B1: |
61 // v3 <- phi(v0, v3 + 1) | 59 // v3 <- phi(v0, v3 + 1) |
(...skipping 39 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
101 | 99 |
102 private: | 100 private: |
103 PhiInstr* phi_; | 101 PhiInstr* phi_; |
104 Definition* initial_value_; | 102 Definition* initial_value_; |
105 BinarySmiOpInstr* increment_; | 103 BinarySmiOpInstr* increment_; |
106 ConstraintInstr* limit_; | 104 ConstraintInstr* limit_; |
107 | 105 |
108 PhiInstr* bound_; | 106 PhiInstr* bound_; |
109 }; | 107 }; |
110 | 108 |
111 | |
112 static ConstraintInstr* FindBoundingConstraint(PhiInstr* phi, | 109 static ConstraintInstr* FindBoundingConstraint(PhiInstr* phi, |
113 Definition* defn) { | 110 Definition* defn) { |
114 ConstraintInstr* limit = NULL; | 111 ConstraintInstr* limit = NULL; |
115 for (ConstraintInstr* constraint = defn->AsConstraint(); constraint != NULL; | 112 for (ConstraintInstr* constraint = defn->AsConstraint(); constraint != NULL; |
116 constraint = constraint->value()->definition()->AsConstraint()) { | 113 constraint = constraint->value()->definition()->AsConstraint()) { |
117 if (constraint->target() == NULL) { | 114 if (constraint->target() == NULL) { |
118 continue; // Only interested in non-artifical constraints. | 115 continue; // Only interested in non-artifical constraints. |
119 } | 116 } |
120 | 117 |
121 Range* constraining_range = constraint->constraint(); | 118 Range* constraining_range = constraint->constraint(); |
122 if (constraining_range->min().Equals(RangeBoundary::MinSmi()) && | 119 if (constraining_range->min().Equals(RangeBoundary::MinSmi()) && |
123 (constraining_range->max().IsSymbol() && | 120 (constraining_range->max().IsSymbol() && |
124 phi->IsDominatedBy(constraining_range->max().symbol()))) { | 121 phi->IsDominatedBy(constraining_range->max().symbol()))) { |
125 limit = constraint; | 122 limit = constraint; |
126 } | 123 } |
127 } | 124 } |
128 | 125 |
129 return limit; | 126 return limit; |
130 } | 127 } |
131 | 128 |
132 | |
133 static InductionVariableInfo* DetectSimpleInductionVariable(PhiInstr* phi) { | 129 static InductionVariableInfo* DetectSimpleInductionVariable(PhiInstr* phi) { |
134 if (phi->Type()->ToCid() != kSmiCid) { | 130 if (phi->Type()->ToCid() != kSmiCid) { |
135 return NULL; | 131 return NULL; |
136 } | 132 } |
137 | 133 |
138 if (phi->InputCount() != 2) { | 134 if (phi->InputCount() != 2) { |
139 return NULL; | 135 return NULL; |
140 } | 136 } |
141 | 137 |
142 BitVector* loop_info = phi->block()->loop_info(); | 138 BitVector* loop_info = phi->block()->loop_info(); |
(...skipping 15 matching lines...) Expand all Loading... |
158 increment->right()->BoundConstant().IsSmi() && | 154 increment->right()->BoundConstant().IsSmi() && |
159 (Smi::Cast(increment->right()->BoundConstant()).Value() == 1)) { | 155 (Smi::Cast(increment->right()->BoundConstant()).Value() == 1)) { |
160 return new InductionVariableInfo( | 156 return new InductionVariableInfo( |
161 phi, initial_value, increment, | 157 phi, initial_value, increment, |
162 FindBoundingConstraint(phi, increment->left()->definition())); | 158 FindBoundingConstraint(phi, increment->left()->definition())); |
163 } | 159 } |
164 | 160 |
165 return NULL; | 161 return NULL; |
166 } | 162 } |
167 | 163 |
168 | |
169 void RangeAnalysis::DiscoverSimpleInductionVariables() { | 164 void RangeAnalysis::DiscoverSimpleInductionVariables() { |
170 GrowableArray<InductionVariableInfo*> loop_variables; | 165 GrowableArray<InductionVariableInfo*> loop_variables; |
171 | 166 |
172 for (BlockIterator block_it = flow_graph_->reverse_postorder_iterator(); | 167 for (BlockIterator block_it = flow_graph_->reverse_postorder_iterator(); |
173 !block_it.Done(); block_it.Advance()) { | 168 !block_it.Done(); block_it.Advance()) { |
174 BlockEntryInstr* block = block_it.Current(); | 169 BlockEntryInstr* block = block_it.Current(); |
175 | 170 |
176 JoinEntryInstr* join = block->AsJoinEntry(); | 171 JoinEntryInstr* join = block->AsJoinEntry(); |
177 if (join != NULL && join->loop_info() != NULL) { | 172 if (join != NULL && join->loop_info() != NULL) { |
178 loop_variables.Clear(); | 173 loop_variables.Clear(); |
(...skipping 25 matching lines...) Expand all Loading... |
204 if (bound != NULL) { | 199 if (bound != NULL) { |
205 for (intptr_t i = 0; i < loop_variables.length(); i++) { | 200 for (intptr_t i = 0; i < loop_variables.length(); i++) { |
206 InductionVariableInfo* info = loop_variables[i]; | 201 InductionVariableInfo* info = loop_variables[i]; |
207 info->set_bound(bound->phi()); | 202 info->set_bound(bound->phi()); |
208 info->phi()->set_induction_variable_info(info); | 203 info->phi()->set_induction_variable_info(info); |
209 } | 204 } |
210 } | 205 } |
211 } | 206 } |
212 } | 207 } |
213 | 208 |
214 | |
215 void RangeAnalysis::CollectValues() { | 209 void RangeAnalysis::CollectValues() { |
216 const GrowableArray<Definition*>& initial = | 210 const GrowableArray<Definition*>& initial = |
217 *flow_graph_->graph_entry()->initial_definitions(); | 211 *flow_graph_->graph_entry()->initial_definitions(); |
218 for (intptr_t i = 0; i < initial.length(); ++i) { | 212 for (intptr_t i = 0; i < initial.length(); ++i) { |
219 Definition* current = initial[i]; | 213 Definition* current = initial[i]; |
220 if (IsIntegerDefinition(current)) { | 214 if (IsIntegerDefinition(current)) { |
221 values_.Add(current); | 215 values_.Add(current); |
222 } | 216 } |
223 } | 217 } |
224 | 218 |
225 for (BlockIterator block_it = flow_graph_->reverse_postorder_iterator(); | 219 for (BlockIterator block_it = flow_graph_->reverse_postorder_iterator(); |
226 !block_it.Done(); block_it.Advance()) { | 220 !block_it.Done(); block_it.Advance()) { |
227 BlockEntryInstr* block = block_it.Current(); | 221 BlockEntryInstr* block = block_it.Current(); |
228 | 222 |
229 | |
230 if (block->IsGraphEntry() || block->IsCatchBlockEntry()) { | 223 if (block->IsGraphEntry() || block->IsCatchBlockEntry()) { |
231 const GrowableArray<Definition*>& initial = | 224 const GrowableArray<Definition*>& initial = |
232 block->IsGraphEntry() | 225 block->IsGraphEntry() |
233 ? *block->AsGraphEntry()->initial_definitions() | 226 ? *block->AsGraphEntry()->initial_definitions() |
234 : *block->AsCatchBlockEntry()->initial_definitions(); | 227 : *block->AsCatchBlockEntry()->initial_definitions(); |
235 for (intptr_t i = 0; i < initial.length(); ++i) { | 228 for (intptr_t i = 0; i < initial.length(); ++i) { |
236 Definition* current = initial[i]; | 229 Definition* current = initial[i]; |
237 if (IsIntegerDefinition(current)) { | 230 if (IsIntegerDefinition(current)) { |
238 values_.Add(current); | 231 values_.Add(current); |
239 } | 232 } |
(...skipping 23 matching lines...) Expand all Loading... |
263 shift_mint_ops_.Add(defn->AsShiftMintOp()); | 256 shift_mint_ops_.Add(defn->AsShiftMintOp()); |
264 } | 257 } |
265 } | 258 } |
266 } else if (current->IsCheckArrayBound()) { | 259 } else if (current->IsCheckArrayBound()) { |
267 bounds_checks_.Add(current->AsCheckArrayBound()); | 260 bounds_checks_.Add(current->AsCheckArrayBound()); |
268 } | 261 } |
269 } | 262 } |
270 } | 263 } |
271 } | 264 } |
272 | 265 |
273 | |
274 // For a comparison operation return an operation for the equivalent flipped | 266 // For a comparison operation return an operation for the equivalent flipped |
275 // comparison: a (op) b === b (op') a. | 267 // comparison: a (op) b === b (op') a. |
276 static Token::Kind FlipComparison(Token::Kind op) { | 268 static Token::Kind FlipComparison(Token::Kind op) { |
277 switch (op) { | 269 switch (op) { |
278 case Token::kEQ: | 270 case Token::kEQ: |
279 return Token::kEQ; | 271 return Token::kEQ; |
280 case Token::kNE: | 272 case Token::kNE: |
281 return Token::kNE; | 273 return Token::kNE; |
282 case Token::kLT: | 274 case Token::kLT: |
283 return Token::kGT; | 275 return Token::kGT; |
284 case Token::kGT: | 276 case Token::kGT: |
285 return Token::kLT; | 277 return Token::kLT; |
286 case Token::kLTE: | 278 case Token::kLTE: |
287 return Token::kGTE; | 279 return Token::kGTE; |
288 case Token::kGTE: | 280 case Token::kGTE: |
289 return Token::kLTE; | 281 return Token::kLTE; |
290 default: | 282 default: |
291 UNREACHABLE(); | 283 UNREACHABLE(); |
292 return Token::kILLEGAL; | 284 return Token::kILLEGAL; |
293 } | 285 } |
294 } | 286 } |
295 | 287 |
296 | |
297 // Given a boundary (right operand) and a comparison operation return | 288 // Given a boundary (right operand) and a comparison operation return |
298 // a symbolic range constraint for the left operand of the comparison assuming | 289 // a symbolic range constraint for the left operand of the comparison assuming |
299 // that it evaluated to true. | 290 // that it evaluated to true. |
300 // For example for the comparison a < b symbol a is constrained with range | 291 // For example for the comparison a < b symbol a is constrained with range |
301 // [Smi::kMinValue, b - 1]. | 292 // [Smi::kMinValue, b - 1]. |
302 Range* RangeAnalysis::ConstraintSmiRange(Token::Kind op, Definition* boundary) { | 293 Range* RangeAnalysis::ConstraintSmiRange(Token::Kind op, Definition* boundary) { |
303 switch (op) { | 294 switch (op) { |
304 case Token::kEQ: | 295 case Token::kEQ: |
305 return new (Z) Range(RangeBoundary::FromDefinition(boundary), | 296 return new (Z) Range(RangeBoundary::FromDefinition(boundary), |
306 RangeBoundary::FromDefinition(boundary)); | 297 RangeBoundary::FromDefinition(boundary)); |
(...skipping 10 matching lines...) Expand all Loading... |
317 RangeBoundary::FromDefinition(boundary)); | 308 RangeBoundary::FromDefinition(boundary)); |
318 case Token::kGTE: | 309 case Token::kGTE: |
319 return new (Z) Range(RangeBoundary::FromDefinition(boundary), | 310 return new (Z) Range(RangeBoundary::FromDefinition(boundary), |
320 RangeBoundary::MaxSmi()); | 311 RangeBoundary::MaxSmi()); |
321 default: | 312 default: |
322 UNREACHABLE(); | 313 UNREACHABLE(); |
323 return NULL; | 314 return NULL; |
324 } | 315 } |
325 } | 316 } |
326 | 317 |
327 | |
328 ConstraintInstr* RangeAnalysis::InsertConstraintFor(Value* use, | 318 ConstraintInstr* RangeAnalysis::InsertConstraintFor(Value* use, |
329 Definition* defn, | 319 Definition* defn, |
330 Range* constraint_range, | 320 Range* constraint_range, |
331 Instruction* after) { | 321 Instruction* after) { |
332 // No need to constrain constants. | 322 // No need to constrain constants. |
333 if (defn->IsConstant()) return NULL; | 323 if (defn->IsConstant()) return NULL; |
334 | 324 |
335 // Check if the value is already constrained to avoid inserting duplicated | 325 // Check if the value is already constrained to avoid inserting duplicated |
336 // constraints. | 326 // constraints. |
337 ConstraintInstr* constraint = after->next()->AsConstraint(); | 327 ConstraintInstr* constraint = after->next()->AsConstraint(); |
338 while (constraint != NULL) { | 328 while (constraint != NULL) { |
339 if ((constraint->value()->definition() == defn) && | 329 if ((constraint->value()->definition() == defn) && |
340 constraint->constraint()->Equals(constraint_range)) { | 330 constraint->constraint()->Equals(constraint_range)) { |
341 return NULL; | 331 return NULL; |
342 } | 332 } |
343 constraint = constraint->next()->AsConstraint(); | 333 constraint = constraint->next()->AsConstraint(); |
344 } | 334 } |
345 | 335 |
346 constraint = new (Z) ConstraintInstr(use->CopyWithType(), constraint_range); | 336 constraint = new (Z) ConstraintInstr(use->CopyWithType(), constraint_range); |
347 | 337 |
348 flow_graph_->InsertAfter(after, constraint, NULL, FlowGraph::kValue); | 338 flow_graph_->InsertAfter(after, constraint, NULL, FlowGraph::kValue); |
349 FlowGraph::RenameDominatedUses(defn, constraint, constraint); | 339 FlowGraph::RenameDominatedUses(defn, constraint, constraint); |
350 constraints_.Add(constraint); | 340 constraints_.Add(constraint); |
351 return constraint; | 341 return constraint; |
352 } | 342 } |
353 | 343 |
354 | |
355 bool RangeAnalysis::ConstrainValueAfterBranch(Value* use, Definition* defn) { | 344 bool RangeAnalysis::ConstrainValueAfterBranch(Value* use, Definition* defn) { |
356 BranchInstr* branch = use->instruction()->AsBranch(); | 345 BranchInstr* branch = use->instruction()->AsBranch(); |
357 RelationalOpInstr* rel_op = branch->comparison()->AsRelationalOp(); | 346 RelationalOpInstr* rel_op = branch->comparison()->AsRelationalOp(); |
358 if ((rel_op != NULL) && (rel_op->operation_cid() == kSmiCid)) { | 347 if ((rel_op != NULL) && (rel_op->operation_cid() == kSmiCid)) { |
359 // Found comparison of two smis. Constrain defn at true and false | 348 // Found comparison of two smis. Constrain defn at true and false |
360 // successors using the other operand as a boundary. | 349 // successors using the other operand as a boundary. |
361 Definition* boundary; | 350 Definition* boundary; |
362 Token::Kind op_kind; | 351 Token::Kind op_kind; |
363 if (use->use_index() == 0) { // Left operand. | 352 if (use->use_index() == 0) { // Left operand. |
364 boundary = rel_op->InputAt(1)->definition(); | 353 boundary = rel_op->InputAt(1)->definition(); |
(...skipping 22 matching lines...) Expand all Loading... |
387 if (false_constraint != NULL) { | 376 if (false_constraint != NULL) { |
388 false_constraint->set_target(branch->false_successor()); | 377 false_constraint->set_target(branch->false_successor()); |
389 } | 378 } |
390 | 379 |
391 return true; | 380 return true; |
392 } | 381 } |
393 | 382 |
394 return false; | 383 return false; |
395 } | 384 } |
396 | 385 |
397 | |
398 void RangeAnalysis::InsertConstraintsFor(Definition* defn) { | 386 void RangeAnalysis::InsertConstraintsFor(Definition* defn) { |
399 for (Value* use = defn->input_use_list(); use != NULL; | 387 for (Value* use = defn->input_use_list(); use != NULL; |
400 use = use->next_use()) { | 388 use = use->next_use()) { |
401 if (use->instruction()->IsBranch()) { | 389 if (use->instruction()->IsBranch()) { |
402 if (ConstrainValueAfterBranch(use, defn)) { | 390 if (ConstrainValueAfterBranch(use, defn)) { |
403 Value* other_value = use->instruction()->InputAt(1 - use->use_index()); | 391 Value* other_value = use->instruction()->InputAt(1 - use->use_index()); |
404 if (!IsIntegerDefinition(other_value->definition())) { | 392 if (!IsIntegerDefinition(other_value->definition())) { |
405 ConstrainValueAfterBranch(other_value, other_value->definition()); | 393 ConstrainValueAfterBranch(other_value, other_value->definition()); |
406 } | 394 } |
407 } | 395 } |
408 } else if (use->instruction()->IsCheckArrayBound()) { | 396 } else if (use->instruction()->IsCheckArrayBound()) { |
409 ConstrainValueAfterCheckArrayBound(use, defn); | 397 ConstrainValueAfterCheckArrayBound(use, defn); |
410 } | 398 } |
411 } | 399 } |
412 } | 400 } |
413 | 401 |
414 | |
415 void RangeAnalysis::ConstrainValueAfterCheckArrayBound(Value* use, | 402 void RangeAnalysis::ConstrainValueAfterCheckArrayBound(Value* use, |
416 Definition* defn) { | 403 Definition* defn) { |
417 CheckArrayBoundInstr* check = use->instruction()->AsCheckArrayBound(); | 404 CheckArrayBoundInstr* check = use->instruction()->AsCheckArrayBound(); |
418 intptr_t use_index = use->use_index(); | 405 intptr_t use_index = use->use_index(); |
419 | 406 |
420 Range* constraint_range = NULL; | 407 Range* constraint_range = NULL; |
421 if (use_index == CheckArrayBoundInstr::kIndexPos) { | 408 if (use_index == CheckArrayBoundInstr::kIndexPos) { |
422 Definition* length = check->length()->definition(); | 409 Definition* length = check->length()->definition(); |
423 constraint_range = new (Z) Range(RangeBoundary::FromConstant(0), | 410 constraint_range = new (Z) Range(RangeBoundary::FromConstant(0), |
424 RangeBoundary::FromDefinition(length, -1)); | 411 RangeBoundary::FromDefinition(length, -1)); |
425 } else { | 412 } else { |
426 ASSERT(use_index == CheckArrayBoundInstr::kLengthPos); | 413 ASSERT(use_index == CheckArrayBoundInstr::kLengthPos); |
427 Definition* index = check->index()->definition(); | 414 Definition* index = check->index()->definition(); |
428 constraint_range = new (Z) | 415 constraint_range = new (Z) |
429 Range(RangeBoundary::FromDefinition(index, 1), RangeBoundary::MaxSmi()); | 416 Range(RangeBoundary::FromDefinition(index, 1), RangeBoundary::MaxSmi()); |
430 } | 417 } |
431 InsertConstraintFor(use, defn, constraint_range, check); | 418 InsertConstraintFor(use, defn, constraint_range, check); |
432 } | 419 } |
433 | 420 |
434 | |
435 void RangeAnalysis::InsertConstraints() { | 421 void RangeAnalysis::InsertConstraints() { |
436 for (intptr_t i = 0; i < values_.length(); i++) { | 422 for (intptr_t i = 0; i < values_.length(); i++) { |
437 InsertConstraintsFor(values_[i]); | 423 InsertConstraintsFor(values_[i]); |
438 } | 424 } |
439 | 425 |
440 for (intptr_t i = 0; i < constraints_.length(); i++) { | 426 for (intptr_t i = 0; i < constraints_.length(); i++) { |
441 InsertConstraintsFor(constraints_[i]); | 427 InsertConstraintsFor(constraints_[i]); |
442 } | 428 } |
443 } | 429 } |
444 | 430 |
445 | |
446 const Range* RangeAnalysis::GetSmiRange(Value* value) const { | 431 const Range* RangeAnalysis::GetSmiRange(Value* value) const { |
447 Definition* defn = value->definition(); | 432 Definition* defn = value->definition(); |
448 const Range* range = defn->range(); | 433 const Range* range = defn->range(); |
449 | 434 |
450 if ((range == NULL) && (defn->Type()->ToCid() != kSmiCid)) { | 435 if ((range == NULL) && (defn->Type()->ToCid() != kSmiCid)) { |
451 // Type propagator determined that reaching type for this use is Smi. | 436 // Type propagator determined that reaching type for this use is Smi. |
452 // However the definition itself is not a smi-definition and | 437 // However the definition itself is not a smi-definition and |
453 // thus it will never have range assigned to it. Just return the widest | 438 // thus it will never have range assigned to it. Just return the widest |
454 // range possible for this value. | 439 // range possible for this value. |
455 // We don't need to handle kMintCid here because all external mints | 440 // We don't need to handle kMintCid here because all external mints |
456 // (e.g. results of loads or function call) can be used only after they | 441 // (e.g. results of loads or function call) can be used only after they |
457 // pass through UnboxInt64Instr which is considered as mint-definition | 442 // pass through UnboxInt64Instr which is considered as mint-definition |
458 // and will have a range assigned to it. | 443 // and will have a range assigned to it. |
459 // Note: that we can't return NULL here because it is used as lattice's | 444 // Note: that we can't return NULL here because it is used as lattice's |
460 // bottom element to indicate that the range was not computed *yet*. | 445 // bottom element to indicate that the range was not computed *yet*. |
461 return &smi_range_; | 446 return &smi_range_; |
462 } | 447 } |
463 | 448 |
464 return range; | 449 return range; |
465 } | 450 } |
466 | 451 |
467 | |
468 const Range* RangeAnalysis::GetIntRange(Value* value) const { | 452 const Range* RangeAnalysis::GetIntRange(Value* value) const { |
469 Definition* defn = value->definition(); | 453 Definition* defn = value->definition(); |
470 const Range* range = defn->range(); | 454 const Range* range = defn->range(); |
471 | 455 |
472 if ((range == NULL) && !defn->Type()->IsInt()) { | 456 if ((range == NULL) && !defn->Type()->IsInt()) { |
473 // Type propagator determined that reaching type for this use is int. | 457 // Type propagator determined that reaching type for this use is int. |
474 // However the definition itself is not a int-definition and | 458 // However the definition itself is not a int-definition and |
475 // thus it will never have range assigned to it. Just return the widest | 459 // thus it will never have range assigned to it. Just return the widest |
476 // range possible for this value. | 460 // range possible for this value. |
477 // It is safe to return Int64 range as this is the widest possible range | 461 // It is safe to return Int64 range as this is the widest possible range |
478 // supported by our unboxing operations - if this definition produces | 462 // supported by our unboxing operations - if this definition produces |
479 // Bigint outside of Int64 we will deoptimize whenever we actually try | 463 // Bigint outside of Int64 we will deoptimize whenever we actually try |
480 // to unbox it. | 464 // to unbox it. |
481 // Note: that we can't return NULL here because it is used as lattice's | 465 // Note: that we can't return NULL here because it is used as lattice's |
482 // bottom element to indicate that the range was not computed *yet*. | 466 // bottom element to indicate that the range was not computed *yet*. |
483 return &int64_range_; | 467 return &int64_range_; |
484 } | 468 } |
485 | 469 |
486 return range; | 470 return range; |
487 } | 471 } |
488 | 472 |
489 | |
490 static bool AreEqualDefinitions(Definition* a, Definition* b) { | 473 static bool AreEqualDefinitions(Definition* a, Definition* b) { |
491 a = UnwrapConstraint(a); | 474 a = UnwrapConstraint(a); |
492 b = UnwrapConstraint(b); | 475 b = UnwrapConstraint(b); |
493 return (a == b) || | 476 return (a == b) || |
494 (a->AllowsCSE() && a->Dependencies().IsNone() && b->AllowsCSE() && | 477 (a->AllowsCSE() && a->Dependencies().IsNone() && b->AllowsCSE() && |
495 b->Dependencies().IsNone() && a->Equals(b)); | 478 b->Dependencies().IsNone() && a->Equals(b)); |
496 } | 479 } |
497 | 480 |
498 | |
499 static bool DependOnSameSymbol(const RangeBoundary& a, const RangeBoundary& b) { | 481 static bool DependOnSameSymbol(const RangeBoundary& a, const RangeBoundary& b) { |
500 return a.IsSymbol() && b.IsSymbol() && | 482 return a.IsSymbol() && b.IsSymbol() && |
501 AreEqualDefinitions(a.symbol(), b.symbol()); | 483 AreEqualDefinitions(a.symbol(), b.symbol()); |
502 } | 484 } |
503 | 485 |
504 | |
505 // Given the current range of a phi and a newly computed range check | 486 // Given the current range of a phi and a newly computed range check |
506 // if it is growing towards negative infinity, if it does widen it to | 487 // if it is growing towards negative infinity, if it does widen it to |
507 // MinSmi. | 488 // MinSmi. |
508 static RangeBoundary WidenMin(const Range* range, | 489 static RangeBoundary WidenMin(const Range* range, |
509 const Range* new_range, | 490 const Range* new_range, |
510 RangeBoundary::RangeSize size) { | 491 RangeBoundary::RangeSize size) { |
511 RangeBoundary min = range->min(); | 492 RangeBoundary min = range->min(); |
512 RangeBoundary new_min = new_range->min(); | 493 RangeBoundary new_min = new_range->min(); |
513 | 494 |
514 if (min.IsSymbol()) { | 495 if (min.IsSymbol()) { |
(...skipping 38 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
553 } | 534 } |
554 | 535 |
555 max = Range::ConstantMax(range, size); | 536 max = Range::ConstantMax(range, size); |
556 new_max = Range::ConstantMax(new_range, size); | 537 new_max = Range::ConstantMax(new_range, size); |
557 | 538 |
558 return (max.ConstantValue() >= new_max.ConstantValue()) | 539 return (max.ConstantValue() >= new_max.ConstantValue()) |
559 ? max | 540 ? max |
560 : RangeBoundary::MaxConstant(size); | 541 : RangeBoundary::MaxConstant(size); |
561 } | 542 } |
562 | 543 |
563 | |
564 // Given the current range of a phi and a newly computed range check | 544 // Given the current range of a phi and a newly computed range check |
565 // if we can perform narrowing: use newly computed minimum to improve precision | 545 // if we can perform narrowing: use newly computed minimum to improve precision |
566 // of the computed range. We do it only if current minimum was widened and is | 546 // of the computed range. We do it only if current minimum was widened and is |
567 // equal to MinSmi. | 547 // equal to MinSmi. |
568 // Newly computed minimum is expected to be greater or equal than old one as | 548 // Newly computed minimum is expected to be greater or equal than old one as |
569 // we are running after widening phase. | 549 // we are running after widening phase. |
570 static RangeBoundary NarrowMin(const Range* range, | 550 static RangeBoundary NarrowMin(const Range* range, |
571 const Range* new_range, | 551 const Range* new_range, |
572 RangeBoundary::RangeSize size) { | 552 RangeBoundary::RangeSize size) { |
573 const RangeBoundary min = Range::ConstantMin(range, size); | 553 const RangeBoundary min = Range::ConstantMin(range, size); |
574 const RangeBoundary new_min = Range::ConstantMin(new_range, size); | 554 const RangeBoundary new_min = Range::ConstantMin(new_range, size); |
575 if (min.ConstantValue() > new_min.ConstantValue()) return range->min(); | 555 if (min.ConstantValue() > new_min.ConstantValue()) return range->min(); |
576 | 556 |
577 // TODO(vegorov): consider using negative infinity to indicate widened bound. | 557 // TODO(vegorov): consider using negative infinity to indicate widened bound. |
578 return range->min().IsMinimumOrBelow(size) ? new_range->min() : range->min(); | 558 return range->min().IsMinimumOrBelow(size) ? new_range->min() : range->min(); |
579 } | 559 } |
580 | 560 |
581 | |
582 // Given the current range of a phi and a newly computed range check | 561 // Given the current range of a phi and a newly computed range check |
583 // if we can perform narrowing: use newly computed maximum to improve precision | 562 // if we can perform narrowing: use newly computed maximum to improve precision |
584 // of the computed range. We do it only if current maximum was widened and is | 563 // of the computed range. We do it only if current maximum was widened and is |
585 // equal to MaxSmi. | 564 // equal to MaxSmi. |
586 // Newly computed maximum is expected to be less or equal than old one as | 565 // Newly computed maximum is expected to be less or equal than old one as |
587 // we are running after widening phase. | 566 // we are running after widening phase. |
588 static RangeBoundary NarrowMax(const Range* range, | 567 static RangeBoundary NarrowMax(const Range* range, |
589 const Range* new_range, | 568 const Range* new_range, |
590 RangeBoundary::RangeSize size) { | 569 RangeBoundary::RangeSize size) { |
591 const RangeBoundary max = Range::ConstantMax(range, size); | 570 const RangeBoundary max = Range::ConstantMax(range, size); |
592 const RangeBoundary new_max = Range::ConstantMax(new_range, size); | 571 const RangeBoundary new_max = Range::ConstantMax(new_range, size); |
593 if (max.ConstantValue() < new_max.ConstantValue()) return range->max(); | 572 if (max.ConstantValue() < new_max.ConstantValue()) return range->max(); |
594 | 573 |
595 // TODO(vegorov): consider using positive infinity to indicate widened bound. | 574 // TODO(vegorov): consider using positive infinity to indicate widened bound. |
596 return range->max().IsMaximumOrAbove(size) ? new_range->max() : range->max(); | 575 return range->max().IsMaximumOrAbove(size) ? new_range->max() : range->max(); |
597 } | 576 } |
598 | 577 |
599 | |
600 char RangeAnalysis::OpPrefix(JoinOperator op) { | 578 char RangeAnalysis::OpPrefix(JoinOperator op) { |
601 switch (op) { | 579 switch (op) { |
602 case WIDEN: | 580 case WIDEN: |
603 return 'W'; | 581 return 'W'; |
604 case NARROW: | 582 case NARROW: |
605 return 'N'; | 583 return 'N'; |
606 case NONE: | 584 case NONE: |
607 return 'I'; | 585 return 'I'; |
608 } | 586 } |
609 UNREACHABLE(); | 587 UNREACHABLE(); |
610 return ' '; | 588 return ' '; |
611 } | 589 } |
612 | 590 |
613 | |
614 static RangeBoundary::RangeSize RangeSizeForPhi(Definition* phi) { | 591 static RangeBoundary::RangeSize RangeSizeForPhi(Definition* phi) { |
615 ASSERT(phi->IsPhi()); | 592 ASSERT(phi->IsPhi()); |
616 if (phi->Type()->ToCid() == kSmiCid) { | 593 if (phi->Type()->ToCid() == kSmiCid) { |
617 return RangeBoundary::kRangeBoundarySmi; | 594 return RangeBoundary::kRangeBoundarySmi; |
618 } else if (phi->representation() == kUnboxedInt32) { | 595 } else if (phi->representation() == kUnboxedInt32) { |
619 return RangeBoundary::kRangeBoundaryInt32; | 596 return RangeBoundary::kRangeBoundaryInt32; |
620 } else if (phi->Type()->IsInt()) { | 597 } else if (phi->Type()->IsInt()) { |
621 return RangeBoundary::kRangeBoundaryInt64; | 598 return RangeBoundary::kRangeBoundaryInt64; |
622 } else { | 599 } else { |
623 UNREACHABLE(); | 600 UNREACHABLE(); |
624 return RangeBoundary::kRangeBoundaryInt64; | 601 return RangeBoundary::kRangeBoundaryInt64; |
625 } | 602 } |
626 } | 603 } |
627 | 604 |
628 | |
629 bool RangeAnalysis::InferRange(JoinOperator op, | 605 bool RangeAnalysis::InferRange(JoinOperator op, |
630 Definition* defn, | 606 Definition* defn, |
631 intptr_t iteration) { | 607 intptr_t iteration) { |
632 Range range; | 608 Range range; |
633 defn->InferRange(this, &range); | 609 defn->InferRange(this, &range); |
634 | 610 |
635 if (!Range::IsUnknown(&range)) { | 611 if (!Range::IsUnknown(&range)) { |
636 if (!Range::IsUnknown(defn->range()) && defn->IsPhi()) { | 612 if (!Range::IsUnknown(defn->range()) && defn->IsPhi()) { |
637 const RangeBoundary::RangeSize size = RangeSizeForPhi(defn); | 613 const RangeBoundary::RangeSize size = RangeSizeForPhi(defn); |
638 if (op == WIDEN) { | 614 if (op == WIDEN) { |
(...skipping 14 matching lines...) Expand all Loading... |
653 } | 629 } |
654 #endif // !PRODUCT | 630 #endif // !PRODUCT |
655 defn->set_range(range); | 631 defn->set_range(range); |
656 return true; | 632 return true; |
657 } | 633 } |
658 } | 634 } |
659 | 635 |
660 return false; | 636 return false; |
661 } | 637 } |
662 | 638 |
663 | |
664 void RangeAnalysis::CollectDefinitions(BitVector* set) { | 639 void RangeAnalysis::CollectDefinitions(BitVector* set) { |
665 for (BlockIterator block_it = flow_graph_->reverse_postorder_iterator(); | 640 for (BlockIterator block_it = flow_graph_->reverse_postorder_iterator(); |
666 !block_it.Done(); block_it.Advance()) { | 641 !block_it.Done(); block_it.Advance()) { |
667 BlockEntryInstr* block = block_it.Current(); | 642 BlockEntryInstr* block = block_it.Current(); |
668 | 643 |
669 JoinEntryInstr* join = block->AsJoinEntry(); | 644 JoinEntryInstr* join = block->AsJoinEntry(); |
670 if (join != NULL) { | 645 if (join != NULL) { |
671 for (PhiIterator it(join); !it.Done(); it.Advance()) { | 646 for (PhiIterator it(join); !it.Done(); it.Advance()) { |
672 PhiInstr* phi = it.Current(); | 647 PhiInstr* phi = it.Current(); |
673 if (set->Contains(phi->ssa_temp_index())) { | 648 if (set->Contains(phi->ssa_temp_index())) { |
674 definitions_.Add(phi); | 649 definitions_.Add(phi); |
675 } | 650 } |
676 } | 651 } |
677 } | 652 } |
678 | 653 |
679 for (ForwardInstructionIterator it(block); !it.Done(); it.Advance()) { | 654 for (ForwardInstructionIterator it(block); !it.Done(); it.Advance()) { |
680 Definition* defn = it.Current()->AsDefinition(); | 655 Definition* defn = it.Current()->AsDefinition(); |
681 if ((defn != NULL) && defn->HasSSATemp() && | 656 if ((defn != NULL) && defn->HasSSATemp() && |
682 set->Contains(defn->ssa_temp_index())) { | 657 set->Contains(defn->ssa_temp_index())) { |
683 definitions_.Add(defn); | 658 definitions_.Add(defn); |
684 } | 659 } |
685 } | 660 } |
686 } | 661 } |
687 } | 662 } |
688 | 663 |
689 | |
690 void RangeAnalysis::Iterate(JoinOperator op, intptr_t max_iterations) { | 664 void RangeAnalysis::Iterate(JoinOperator op, intptr_t max_iterations) { |
691 // TODO(vegorov): switch to worklist if this becomes performance bottleneck. | 665 // TODO(vegorov): switch to worklist if this becomes performance bottleneck. |
692 intptr_t iteration = 0; | 666 intptr_t iteration = 0; |
693 bool changed; | 667 bool changed; |
694 do { | 668 do { |
695 changed = false; | 669 changed = false; |
696 for (intptr_t i = 0; i < definitions_.length(); i++) { | 670 for (intptr_t i = 0; i < definitions_.length(); i++) { |
697 Definition* defn = definitions_[i]; | 671 Definition* defn = definitions_[i]; |
698 if (InferRange(op, defn, iteration)) { | 672 if (InferRange(op, defn, iteration)) { |
699 changed = true; | 673 changed = true; |
700 } | 674 } |
701 } | 675 } |
702 | 676 |
703 iteration++; | 677 iteration++; |
704 } while (changed && (iteration < max_iterations)); | 678 } while (changed && (iteration < max_iterations)); |
705 } | 679 } |
706 | 680 |
707 | |
708 void RangeAnalysis::InferRanges() { | 681 void RangeAnalysis::InferRanges() { |
709 if (FLAG_trace_range_analysis) { | 682 if (FLAG_trace_range_analysis) { |
710 FlowGraphPrinter::PrintGraph("Range Analysis (BEFORE)", flow_graph_); | 683 FlowGraphPrinter::PrintGraph("Range Analysis (BEFORE)", flow_graph_); |
711 } | 684 } |
712 Zone* zone = flow_graph_->zone(); | 685 Zone* zone = flow_graph_->zone(); |
713 // Initialize bitvector for quick filtering of int values. | 686 // Initialize bitvector for quick filtering of int values. |
714 BitVector* set = | 687 BitVector* set = |
715 new (zone) BitVector(zone, flow_graph_->current_ssa_temp_index()); | 688 new (zone) BitVector(zone, flow_graph_->current_ssa_temp_index()); |
716 for (intptr_t i = 0; i < values_.length(); i++) { | 689 for (intptr_t i = 0; i < values_.length(); i++) { |
717 set->Add(values_[i]->ssa_temp_index()); | 690 set->Add(values_[i]->ssa_temp_index()); |
(...skipping 36 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
754 // to phis to compute more accurate range. | 727 // to phis to compute more accurate range. |
755 // Narrowing only improves those boundaries that were widened up to | 728 // Narrowing only improves those boundaries that were widened up to |
756 // range boundary and leaves other boundaries intact. | 729 // range boundary and leaves other boundaries intact. |
757 Iterate(NARROW, kMaxInt32); | 730 Iterate(NARROW, kMaxInt32); |
758 | 731 |
759 if (FLAG_trace_range_analysis) { | 732 if (FLAG_trace_range_analysis) { |
760 FlowGraphPrinter::PrintGraph("Range Analysis (AFTER)", flow_graph_); | 733 FlowGraphPrinter::PrintGraph("Range Analysis (AFTER)", flow_graph_); |
761 } | 734 } |
762 } | 735 } |
763 | 736 |
764 | |
765 void RangeAnalysis::AssignRangesRecursively(Definition* defn) { | 737 void RangeAnalysis::AssignRangesRecursively(Definition* defn) { |
766 if (!Range::IsUnknown(defn->range())) { | 738 if (!Range::IsUnknown(defn->range())) { |
767 return; | 739 return; |
768 } | 740 } |
769 | 741 |
770 if (!IsIntegerDefinition(defn)) { | 742 if (!IsIntegerDefinition(defn)) { |
771 return; | 743 return; |
772 } | 744 } |
773 | 745 |
774 for (intptr_t i = 0; i < defn->InputCount(); i++) { | 746 for (intptr_t i = 0; i < defn->InputCount(); i++) { |
775 Definition* input_defn = defn->InputAt(i)->definition(); | 747 Definition* input_defn = defn->InputAt(i)->definition(); |
776 if (!input_defn->HasSSATemp() || input_defn->IsConstant()) { | 748 if (!input_defn->HasSSATemp() || input_defn->IsConstant()) { |
777 AssignRangesRecursively(input_defn); | 749 AssignRangesRecursively(input_defn); |
778 } | 750 } |
779 } | 751 } |
780 | 752 |
781 Range new_range; | 753 Range new_range; |
782 defn->InferRange(this, &new_range); | 754 defn->InferRange(this, &new_range); |
783 if (!Range::IsUnknown(&new_range)) { | 755 if (!Range::IsUnknown(&new_range)) { |
784 defn->set_range(new_range); | 756 defn->set_range(new_range); |
785 } | 757 } |
786 } | 758 } |
787 | 759 |
788 | |
789 // Scheduler is a helper class that inserts floating control-flow less | 760 // Scheduler is a helper class that inserts floating control-flow less |
790 // subgraphs into the flow graph. | 761 // subgraphs into the flow graph. |
791 // It always attempts to schedule instructions into the loop preheader in the | 762 // It always attempts to schedule instructions into the loop preheader in the |
792 // way similar to LICM optimization pass. | 763 // way similar to LICM optimization pass. |
793 // Scheduler supports rollback - that is it keeps track of instructions it | 764 // Scheduler supports rollback - that is it keeps track of instructions it |
794 // schedules and can remove all instructions it inserted from the graph. | 765 // schedules and can remove all instructions it inserted from the graph. |
795 class Scheduler { | 766 class Scheduler { |
796 public: | 767 public: |
797 explicit Scheduler(FlowGraph* flow_graph) | 768 explicit Scheduler(FlowGraph* flow_graph) |
798 : flow_graph_(flow_graph), | 769 : flow_graph_(flow_graph), |
(...skipping 109 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
908 emitted_.Add(instr); | 879 emitted_.Add(instr); |
909 } | 880 } |
910 | 881 |
911 FlowGraph* flow_graph_; | 882 FlowGraph* flow_graph_; |
912 Map map_; | 883 Map map_; |
913 const ZoneGrowableArray<BlockEntryInstr*>& loop_headers_; | 884 const ZoneGrowableArray<BlockEntryInstr*>& loop_headers_; |
914 GrowableArray<BlockEntryInstr*> pre_headers_; | 885 GrowableArray<BlockEntryInstr*> pre_headers_; |
915 GrowableArray<Instruction*> emitted_; | 886 GrowableArray<Instruction*> emitted_; |
916 }; | 887 }; |
917 | 888 |
918 | |
919 // If bounds check 0 <= index < length is not redundant we attempt to | 889 // If bounds check 0 <= index < length is not redundant we attempt to |
920 // replace it with a sequence of checks that guarantee | 890 // replace it with a sequence of checks that guarantee |
921 // | 891 // |
922 // 0 <= LowerBound(index) < UpperBound(index) < length | 892 // 0 <= LowerBound(index) < UpperBound(index) < length |
923 // | 893 // |
924 // and hoist all of those checks out of the enclosing loop. | 894 // and hoist all of those checks out of the enclosing loop. |
925 // | 895 // |
926 // Upper/Lower bounds are symbolic arithmetic expressions with +, -, * | 896 // Upper/Lower bounds are symbolic arithmetic expressions with +, -, * |
927 // operations. | 897 // operations. |
928 class BoundsCheckGeneralizer { | 898 class BoundsCheckGeneralizer { |
(...skipping 146 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1075 } | 1045 } |
1076 | 1046 |
1077 private: | 1047 private: |
1078 BinarySmiOpInstr* MakeBinaryOp(Token::Kind op_kind, | 1048 BinarySmiOpInstr* MakeBinaryOp(Token::Kind op_kind, |
1079 Definition* left, | 1049 Definition* left, |
1080 Definition* right) { | 1050 Definition* right) { |
1081 return new BinarySmiOpInstr(op_kind, new Value(left), new Value(right), | 1051 return new BinarySmiOpInstr(op_kind, new Value(left), new Value(right), |
1082 Thread::kNoDeoptId); | 1052 Thread::kNoDeoptId); |
1083 } | 1053 } |
1084 | 1054 |
1085 | |
1086 BinarySmiOpInstr* MakeBinaryOp(Token::Kind op_kind, | 1055 BinarySmiOpInstr* MakeBinaryOp(Token::Kind op_kind, |
1087 Definition* left, | 1056 Definition* left, |
1088 intptr_t right) { | 1057 intptr_t right) { |
1089 ConstantInstr* constant_right = | 1058 ConstantInstr* constant_right = |
1090 flow_graph_->GetConstant(Smi::Handle(Smi::New(right))); | 1059 flow_graph_->GetConstant(Smi::Handle(Smi::New(right))); |
1091 return MakeBinaryOp(op_kind, left, constant_right); | 1060 return MakeBinaryOp(op_kind, left, constant_right); |
1092 } | 1061 } |
1093 | 1062 |
1094 Definition* RangeBoundaryToDefinition(const RangeBoundary& bound) { | 1063 Definition* RangeBoundaryToDefinition(const RangeBoundary& bound) { |
1095 Definition* symbol = UnwrapConstraint(bound.symbol()); | 1064 Definition* symbol = UnwrapConstraint(bound.symbol()); |
(...skipping 340 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1436 f->Print(")"); | 1405 f->Print(")"); |
1437 } else if (index_bound->IsConstant()) { | 1406 } else if (index_bound->IsConstant()) { |
1438 f->Print("%" Pd "", | 1407 f->Print("%" Pd "", |
1439 Smi::Cast(index_bound->AsConstant()->value()).Value()); | 1408 Smi::Cast(index_bound->AsConstant()->value()).Value()); |
1440 } else { | 1409 } else { |
1441 f->Print("v%" Pd "", index_bound->ssa_temp_index()); | 1410 f->Print("v%" Pd "", index_bound->ssa_temp_index()); |
1442 } | 1411 } |
1443 f->Print(" {%s}", Range::ToCString(index_bound->range())); | 1412 f->Print(" {%s}", Range::ToCString(index_bound->range())); |
1444 } | 1413 } |
1445 | 1414 |
1446 | |
1447 static const char* IndexBoundToCString(Definition* index_bound) { | 1415 static const char* IndexBoundToCString(Definition* index_bound) { |
1448 char buffer[1024]; | 1416 char buffer[1024]; |
1449 BufferFormatter f(buffer, sizeof(buffer)); | 1417 BufferFormatter f(buffer, sizeof(buffer)); |
1450 PrettyPrintIndexBoundRecursively(&f, index_bound); | 1418 PrettyPrintIndexBoundRecursively(&f, index_bound); |
1451 return Thread::Current()->zone()->MakeCopyOfString(buffer); | 1419 return Thread::Current()->zone()->MakeCopyOfString(buffer); |
1452 } | 1420 } |
1453 #endif // !PRODUCT | 1421 #endif // !PRODUCT |
1454 | 1422 |
1455 RangeAnalysis* range_analysis_; | 1423 RangeAnalysis* range_analysis_; |
1456 FlowGraph* flow_graph_; | 1424 FlowGraph* flow_graph_; |
1457 Scheduler scheduler_; | 1425 Scheduler scheduler_; |
1458 }; | 1426 }; |
1459 | 1427 |
1460 | |
1461 void RangeAnalysis::EliminateRedundantBoundsChecks() { | 1428 void RangeAnalysis::EliminateRedundantBoundsChecks() { |
1462 if (FLAG_array_bounds_check_elimination) { | 1429 if (FLAG_array_bounds_check_elimination) { |
1463 const Function& function = flow_graph_->function(); | 1430 const Function& function = flow_graph_->function(); |
1464 // Generalization only if we have not deoptimized on a generalized | 1431 // Generalization only if we have not deoptimized on a generalized |
1465 // check earlier, or we're compiling precompiled code (no | 1432 // check earlier, or we're compiling precompiled code (no |
1466 // optimistic hoisting of checks possible) | 1433 // optimistic hoisting of checks possible) |
1467 const bool try_generalization = | 1434 const bool try_generalization = |
1468 function.allows_bounds_check_generalization() && !FLAG_precompiled_mode; | 1435 function.allows_bounds_check_generalization() && !FLAG_precompiled_mode; |
1469 | 1436 |
1470 BoundsCheckGeneralizer generalizer(this, flow_graph_); | 1437 BoundsCheckGeneralizer generalizer(this, flow_graph_); |
1471 | 1438 |
1472 for (intptr_t i = 0; i < bounds_checks_.length(); i++) { | 1439 for (intptr_t i = 0; i < bounds_checks_.length(); i++) { |
1473 CheckArrayBoundInstr* check = bounds_checks_[i]; | 1440 CheckArrayBoundInstr* check = bounds_checks_[i]; |
1474 RangeBoundary array_length = | 1441 RangeBoundary array_length = |
1475 RangeBoundary::FromDefinition(check->length()->definition()); | 1442 RangeBoundary::FromDefinition(check->length()->definition()); |
1476 if (check->IsRedundant(array_length)) { | 1443 if (check->IsRedundant(array_length)) { |
1477 check->RemoveFromGraph(); | 1444 check->RemoveFromGraph(); |
1478 } else if (try_generalization) { | 1445 } else if (try_generalization) { |
1479 generalizer.TryGeneralize(check, array_length); | 1446 generalizer.TryGeneralize(check, array_length); |
1480 } | 1447 } |
1481 } | 1448 } |
1482 | 1449 |
1483 if (FLAG_trace_range_analysis) { | 1450 if (FLAG_trace_range_analysis) { |
1484 FlowGraphPrinter::PrintGraph("RangeAnalysis (ABCE)", flow_graph_); | 1451 FlowGraphPrinter::PrintGraph("RangeAnalysis (ABCE)", flow_graph_); |
1485 } | 1452 } |
1486 } | 1453 } |
1487 } | 1454 } |
1488 | 1455 |
1489 | |
1490 void RangeAnalysis::MarkUnreachableBlocks() { | 1456 void RangeAnalysis::MarkUnreachableBlocks() { |
1491 for (intptr_t i = 0; i < constraints_.length(); i++) { | 1457 for (intptr_t i = 0; i < constraints_.length(); i++) { |
1492 if (Range::IsUnknown(constraints_[i]->range())) { | 1458 if (Range::IsUnknown(constraints_[i]->range())) { |
1493 TargetEntryInstr* target = constraints_[i]->target(); | 1459 TargetEntryInstr* target = constraints_[i]->target(); |
1494 if (target == NULL) { | 1460 if (target == NULL) { |
1495 // TODO(vegorov): replace Constraint with an uncoditional | 1461 // TODO(vegorov): replace Constraint with an uncoditional |
1496 // deoptimization and kill all dominated dead code. | 1462 // deoptimization and kill all dominated dead code. |
1497 continue; | 1463 continue; |
1498 } | 1464 } |
1499 | 1465 |
(...skipping 14 matching lines...) Expand all Loading... |
1514 FlowGraphPrinter::ShouldPrint(flow_graph_->function())) { | 1480 FlowGraphPrinter::ShouldPrint(flow_graph_->function())) { |
1515 THR_Print("Range analysis: False unreachable (B%" Pd ")\n", | 1481 THR_Print("Range analysis: False unreachable (B%" Pd ")\n", |
1516 branch->false_successor()->block_id()); | 1482 branch->false_successor()->block_id()); |
1517 } | 1483 } |
1518 branch->set_constant_target(branch->true_successor()); | 1484 branch->set_constant_target(branch->true_successor()); |
1519 } | 1485 } |
1520 } | 1486 } |
1521 } | 1487 } |
1522 } | 1488 } |
1523 | 1489 |
1524 | |
1525 void RangeAnalysis::RemoveConstraints() { | 1490 void RangeAnalysis::RemoveConstraints() { |
1526 for (intptr_t i = 0; i < constraints_.length(); i++) { | 1491 for (intptr_t i = 0; i < constraints_.length(); i++) { |
1527 Definition* def = constraints_[i]->value()->definition(); | 1492 Definition* def = constraints_[i]->value()->definition(); |
1528 // Some constraints might be constraining constraints. Unwind the chain of | 1493 // Some constraints might be constraining constraints. Unwind the chain of |
1529 // constraints until we reach the actual definition. | 1494 // constraints until we reach the actual definition. |
1530 while (def->IsConstraint()) { | 1495 while (def->IsConstraint()) { |
1531 def = def->AsConstraint()->value()->definition(); | 1496 def = def->AsConstraint()->value()->definition(); |
1532 } | 1497 } |
1533 constraints_[i]->ReplaceUsesWith(def); | 1498 constraints_[i]->ReplaceUsesWith(def); |
1534 constraints_[i]->RemoveFromGraph(); | 1499 constraints_[i]->RemoveFromGraph(); |
1535 } | 1500 } |
1536 } | 1501 } |
1537 | 1502 |
1538 | |
1539 static void NarrowBinaryMintOp(BinaryMintOpInstr* mint_op) { | 1503 static void NarrowBinaryMintOp(BinaryMintOpInstr* mint_op) { |
1540 if (RangeUtils::Fits(mint_op->range(), RangeBoundary::kRangeBoundaryInt32) && | 1504 if (RangeUtils::Fits(mint_op->range(), RangeBoundary::kRangeBoundaryInt32) && |
1541 RangeUtils::Fits(mint_op->left()->definition()->range(), | 1505 RangeUtils::Fits(mint_op->left()->definition()->range(), |
1542 RangeBoundary::kRangeBoundaryInt32) && | 1506 RangeBoundary::kRangeBoundaryInt32) && |
1543 RangeUtils::Fits(mint_op->right()->definition()->range(), | 1507 RangeUtils::Fits(mint_op->right()->definition()->range(), |
1544 RangeBoundary::kRangeBoundaryInt32) && | 1508 RangeBoundary::kRangeBoundaryInt32) && |
1545 BinaryInt32OpInstr::IsSupported(mint_op->op_kind(), mint_op->left(), | 1509 BinaryInt32OpInstr::IsSupported(mint_op->op_kind(), mint_op->left(), |
1546 mint_op->right())) { | 1510 mint_op->right())) { |
1547 BinaryInt32OpInstr* int32_op = new BinaryInt32OpInstr( | 1511 BinaryInt32OpInstr* int32_op = new BinaryInt32OpInstr( |
1548 mint_op->op_kind(), mint_op->left()->CopyWithType(), | 1512 mint_op->op_kind(), mint_op->left()->CopyWithType(), |
1549 mint_op->right()->CopyWithType(), mint_op->DeoptimizationTarget()); | 1513 mint_op->right()->CopyWithType(), mint_op->DeoptimizationTarget()); |
1550 int32_op->set_range(*mint_op->range()); | 1514 int32_op->set_range(*mint_op->range()); |
1551 int32_op->set_can_overflow(false); | 1515 int32_op->set_can_overflow(false); |
1552 mint_op->ReplaceWith(int32_op, NULL); | 1516 mint_op->ReplaceWith(int32_op, NULL); |
1553 } | 1517 } |
1554 } | 1518 } |
1555 | 1519 |
1556 | |
1557 static void NarrowShiftMintOp(ShiftMintOpInstr* mint_op) { | 1520 static void NarrowShiftMintOp(ShiftMintOpInstr* mint_op) { |
1558 if (RangeUtils::Fits(mint_op->range(), RangeBoundary::kRangeBoundaryInt32) && | 1521 if (RangeUtils::Fits(mint_op->range(), RangeBoundary::kRangeBoundaryInt32) && |
1559 RangeUtils::Fits(mint_op->left()->definition()->range(), | 1522 RangeUtils::Fits(mint_op->left()->definition()->range(), |
1560 RangeBoundary::kRangeBoundaryInt32) && | 1523 RangeBoundary::kRangeBoundaryInt32) && |
1561 RangeUtils::Fits(mint_op->right()->definition()->range(), | 1524 RangeUtils::Fits(mint_op->right()->definition()->range(), |
1562 RangeBoundary::kRangeBoundaryInt32) && | 1525 RangeBoundary::kRangeBoundaryInt32) && |
1563 BinaryInt32OpInstr::IsSupported(mint_op->op_kind(), mint_op->left(), | 1526 BinaryInt32OpInstr::IsSupported(mint_op->op_kind(), mint_op->left(), |
1564 mint_op->right())) { | 1527 mint_op->right())) { |
1565 BinaryInt32OpInstr* int32_op = new BinaryInt32OpInstr( | 1528 BinaryInt32OpInstr* int32_op = new BinaryInt32OpInstr( |
1566 mint_op->op_kind(), mint_op->left()->CopyWithType(), | 1529 mint_op->op_kind(), mint_op->left()->CopyWithType(), |
1567 mint_op->right()->CopyWithType(), mint_op->DeoptimizationTarget()); | 1530 mint_op->right()->CopyWithType(), mint_op->DeoptimizationTarget()); |
1568 int32_op->set_range(*mint_op->range()); | 1531 int32_op->set_range(*mint_op->range()); |
1569 int32_op->set_can_overflow(false); | 1532 int32_op->set_can_overflow(false); |
1570 mint_op->ReplaceWith(int32_op, NULL); | 1533 mint_op->ReplaceWith(int32_op, NULL); |
1571 } | 1534 } |
1572 } | 1535 } |
1573 | 1536 |
1574 | |
1575 void RangeAnalysis::NarrowMintToInt32() { | 1537 void RangeAnalysis::NarrowMintToInt32() { |
1576 for (intptr_t i = 0; i < binary_mint_ops_.length(); i++) { | 1538 for (intptr_t i = 0; i < binary_mint_ops_.length(); i++) { |
1577 NarrowBinaryMintOp(binary_mint_ops_[i]); | 1539 NarrowBinaryMintOp(binary_mint_ops_[i]); |
1578 } | 1540 } |
1579 | 1541 |
1580 for (intptr_t i = 0; i < shift_mint_ops_.length(); i++) { | 1542 for (intptr_t i = 0; i < shift_mint_ops_.length(); i++) { |
1581 NarrowShiftMintOp(shift_mint_ops_[i]); | 1543 NarrowShiftMintOp(shift_mint_ops_[i]); |
1582 } | 1544 } |
1583 } | 1545 } |
1584 | 1546 |
1585 | |
1586 IntegerInstructionSelector::IntegerInstructionSelector(FlowGraph* flow_graph) | 1547 IntegerInstructionSelector::IntegerInstructionSelector(FlowGraph* flow_graph) |
1587 : flow_graph_(flow_graph) { | 1548 : flow_graph_(flow_graph) { |
1588 ASSERT(flow_graph_ != NULL); | 1549 ASSERT(flow_graph_ != NULL); |
1589 zone_ = flow_graph_->zone(); | 1550 zone_ = flow_graph_->zone(); |
1590 selected_uint32_defs_ = | 1551 selected_uint32_defs_ = |
1591 new (zone_) BitVector(zone_, flow_graph_->current_ssa_temp_index()); | 1552 new (zone_) BitVector(zone_, flow_graph_->current_ssa_temp_index()); |
1592 } | 1553 } |
1593 | 1554 |
1594 | |
1595 void IntegerInstructionSelector::Select() { | 1555 void IntegerInstructionSelector::Select() { |
1596 if (FLAG_trace_integer_ir_selection) { | 1556 if (FLAG_trace_integer_ir_selection) { |
1597 THR_Print("---- starting integer ir selection -------\n"); | 1557 THR_Print("---- starting integer ir selection -------\n"); |
1598 } | 1558 } |
1599 FindPotentialUint32Definitions(); | 1559 FindPotentialUint32Definitions(); |
1600 FindUint32NarrowingDefinitions(); | 1560 FindUint32NarrowingDefinitions(); |
1601 Propagate(); | 1561 Propagate(); |
1602 ReplaceInstructions(); | 1562 ReplaceInstructions(); |
1603 if (FLAG_support_il_printer && FLAG_trace_integer_ir_selection) { | 1563 if (FLAG_support_il_printer && FLAG_trace_integer_ir_selection) { |
1604 THR_Print("---- after integer ir selection -------\n"); | 1564 THR_Print("---- after integer ir selection -------\n"); |
1605 FlowGraphPrinter printer(*flow_graph_); | 1565 FlowGraphPrinter printer(*flow_graph_); |
1606 printer.PrintBlocks(); | 1566 printer.PrintBlocks(); |
1607 } | 1567 } |
1608 } | 1568 } |
1609 | 1569 |
1610 | |
1611 bool IntegerInstructionSelector::IsPotentialUint32Definition(Definition* def) { | 1570 bool IntegerInstructionSelector::IsPotentialUint32Definition(Definition* def) { |
1612 // TODO(johnmccutchan): Consider Smi operations, to avoid unnecessary tagging | 1571 // TODO(johnmccutchan): Consider Smi operations, to avoid unnecessary tagging |
1613 // & untagged of intermediate results. | 1572 // & untagged of intermediate results. |
1614 // TODO(johnmccutchan): Consider phis. | 1573 // TODO(johnmccutchan): Consider phis. |
1615 return def->IsBoxInt64() || def->IsUnboxInt64() || def->IsBinaryMintOp() || | 1574 return def->IsBoxInt64() || def->IsUnboxInt64() || def->IsBinaryMintOp() || |
1616 def->IsShiftMintOp() || def->IsUnaryMintOp(); | 1575 def->IsShiftMintOp() || def->IsUnaryMintOp(); |
1617 } | 1576 } |
1618 | 1577 |
1619 | |
1620 void IntegerInstructionSelector::FindPotentialUint32Definitions() { | 1578 void IntegerInstructionSelector::FindPotentialUint32Definitions() { |
1621 if (FLAG_trace_integer_ir_selection) { | 1579 if (FLAG_trace_integer_ir_selection) { |
1622 THR_Print("++++ Finding potential Uint32 definitions:\n"); | 1580 THR_Print("++++ Finding potential Uint32 definitions:\n"); |
1623 } | 1581 } |
1624 | 1582 |
1625 for (BlockIterator block_it = flow_graph_->reverse_postorder_iterator(); | 1583 for (BlockIterator block_it = flow_graph_->reverse_postorder_iterator(); |
1626 !block_it.Done(); block_it.Advance()) { | 1584 !block_it.Done(); block_it.Advance()) { |
1627 BlockEntryInstr* block = block_it.Current(); | 1585 BlockEntryInstr* block = block_it.Current(); |
1628 | 1586 |
1629 for (ForwardInstructionIterator instr_it(block); !instr_it.Done(); | 1587 for (ForwardInstructionIterator instr_it(block); !instr_it.Done(); |
1630 instr_it.Advance()) { | 1588 instr_it.Advance()) { |
1631 Instruction* current = instr_it.Current(); | 1589 Instruction* current = instr_it.Current(); |
1632 Definition* defn = current->AsDefinition(); | 1590 Definition* defn = current->AsDefinition(); |
1633 if ((defn != NULL) && defn->HasSSATemp()) { | 1591 if ((defn != NULL) && defn->HasSSATemp()) { |
1634 if (IsPotentialUint32Definition(defn)) { | 1592 if (IsPotentialUint32Definition(defn)) { |
1635 if (FLAG_support_il_printer && FLAG_trace_integer_ir_selection) { | 1593 if (FLAG_support_il_printer && FLAG_trace_integer_ir_selection) { |
1636 THR_Print("Adding %s\n", current->ToCString()); | 1594 THR_Print("Adding %s\n", current->ToCString()); |
1637 } | 1595 } |
1638 potential_uint32_defs_.Add(defn); | 1596 potential_uint32_defs_.Add(defn); |
1639 } | 1597 } |
1640 } | 1598 } |
1641 } | 1599 } |
1642 } | 1600 } |
1643 } | 1601 } |
1644 | 1602 |
1645 | |
1646 // BinaryMintOp masks and stores into unsigned typed arrays that truncate the | 1603 // BinaryMintOp masks and stores into unsigned typed arrays that truncate the |
1647 // value into a Uint32 range. | 1604 // value into a Uint32 range. |
1648 bool IntegerInstructionSelector::IsUint32NarrowingDefinition(Definition* def) { | 1605 bool IntegerInstructionSelector::IsUint32NarrowingDefinition(Definition* def) { |
1649 if (def->IsBinaryMintOp()) { | 1606 if (def->IsBinaryMintOp()) { |
1650 BinaryMintOpInstr* op = def->AsBinaryMintOp(); | 1607 BinaryMintOpInstr* op = def->AsBinaryMintOp(); |
1651 // Must be a mask operation. | 1608 // Must be a mask operation. |
1652 if (op->op_kind() != Token::kBIT_AND) { | 1609 if (op->op_kind() != Token::kBIT_AND) { |
1653 return false; | 1610 return false; |
1654 } | 1611 } |
1655 Range* range = op->range(); | 1612 Range* range = op->range(); |
1656 if ((range == NULL) || | 1613 if ((range == NULL) || |
1657 !range->IsWithin(0, static_cast<int64_t>(kMaxUint32))) { | 1614 !range->IsWithin(0, static_cast<int64_t>(kMaxUint32))) { |
1658 return false; | 1615 return false; |
1659 } | 1616 } |
1660 return true; | 1617 return true; |
1661 } | 1618 } |
1662 // TODO(johnmccutchan): Add typed array stores. | 1619 // TODO(johnmccutchan): Add typed array stores. |
1663 return false; | 1620 return false; |
1664 } | 1621 } |
1665 | 1622 |
1666 | |
1667 void IntegerInstructionSelector::FindUint32NarrowingDefinitions() { | 1623 void IntegerInstructionSelector::FindUint32NarrowingDefinitions() { |
1668 ASSERT(selected_uint32_defs_ != NULL); | 1624 ASSERT(selected_uint32_defs_ != NULL); |
1669 if (FLAG_trace_integer_ir_selection) { | 1625 if (FLAG_trace_integer_ir_selection) { |
1670 THR_Print("++++ Selecting Uint32 definitions:\n"); | 1626 THR_Print("++++ Selecting Uint32 definitions:\n"); |
1671 THR_Print("++++ Initial set:\n"); | 1627 THR_Print("++++ Initial set:\n"); |
1672 } | 1628 } |
1673 for (intptr_t i = 0; i < potential_uint32_defs_.length(); i++) { | 1629 for (intptr_t i = 0; i < potential_uint32_defs_.length(); i++) { |
1674 Definition* defn = potential_uint32_defs_[i]; | 1630 Definition* defn = potential_uint32_defs_[i]; |
1675 if (IsUint32NarrowingDefinition(defn)) { | 1631 if (IsUint32NarrowingDefinition(defn)) { |
1676 if (FLAG_support_il_printer && FLAG_trace_integer_ir_selection) { | 1632 if (FLAG_support_il_printer && FLAG_trace_integer_ir_selection) { |
1677 THR_Print("Adding %s\n", defn->ToCString()); | 1633 THR_Print("Adding %s\n", defn->ToCString()); |
1678 } | 1634 } |
1679 selected_uint32_defs_->Add(defn->ssa_temp_index()); | 1635 selected_uint32_defs_->Add(defn->ssa_temp_index()); |
1680 } | 1636 } |
1681 } | 1637 } |
1682 } | 1638 } |
1683 | 1639 |
1684 | |
1685 bool IntegerInstructionSelector::AllUsesAreUint32Narrowing(Value* list_head) { | 1640 bool IntegerInstructionSelector::AllUsesAreUint32Narrowing(Value* list_head) { |
1686 for (Value::Iterator it(list_head); !it.Done(); it.Advance()) { | 1641 for (Value::Iterator it(list_head); !it.Done(); it.Advance()) { |
1687 Value* use = it.Current(); | 1642 Value* use = it.Current(); |
1688 Definition* defn = use->instruction()->AsDefinition(); | 1643 Definition* defn = use->instruction()->AsDefinition(); |
1689 if ((defn == NULL) || !defn->HasSSATemp() || | 1644 if ((defn == NULL) || !defn->HasSSATemp() || |
1690 !selected_uint32_defs_->Contains(defn->ssa_temp_index())) { | 1645 !selected_uint32_defs_->Contains(defn->ssa_temp_index())) { |
1691 return false; | 1646 return false; |
1692 } | 1647 } |
1693 } | 1648 } |
1694 return true; | 1649 return true; |
1695 } | 1650 } |
1696 | 1651 |
1697 | |
1698 bool IntegerInstructionSelector::CanBecomeUint32(Definition* def) { | 1652 bool IntegerInstructionSelector::CanBecomeUint32(Definition* def) { |
1699 ASSERT(IsPotentialUint32Definition(def)); | 1653 ASSERT(IsPotentialUint32Definition(def)); |
1700 if (def->IsBoxInt64()) { | 1654 if (def->IsBoxInt64()) { |
1701 // If a BoxInt64's input is a candidate, the box is a candidate. | 1655 // If a BoxInt64's input is a candidate, the box is a candidate. |
1702 Definition* box_input = def->AsBoxInt64()->value()->definition(); | 1656 Definition* box_input = def->AsBoxInt64()->value()->definition(); |
1703 return selected_uint32_defs_->Contains(box_input->ssa_temp_index()); | 1657 return selected_uint32_defs_->Contains(box_input->ssa_temp_index()); |
1704 } | 1658 } |
1705 // A right shift with an input outside of Uint32 range cannot be converted | 1659 // A right shift with an input outside of Uint32 range cannot be converted |
1706 // because we need the high bits. | 1660 // because we need the high bits. |
1707 if (def->IsShiftMintOp()) { | 1661 if (def->IsShiftMintOp()) { |
1708 ShiftMintOpInstr* op = def->AsShiftMintOp(); | 1662 ShiftMintOpInstr* op = def->AsShiftMintOp(); |
1709 if (op->op_kind() == Token::kSHR) { | 1663 if (op->op_kind() == Token::kSHR) { |
1710 Definition* shift_input = op->left()->definition(); | 1664 Definition* shift_input = op->left()->definition(); |
1711 ASSERT(shift_input != NULL); | 1665 ASSERT(shift_input != NULL); |
1712 Range* range = shift_input->range(); | 1666 Range* range = shift_input->range(); |
1713 if ((range == NULL) || | 1667 if ((range == NULL) || |
1714 !range->IsWithin(0, static_cast<int64_t>(kMaxUint32))) { | 1668 !range->IsWithin(0, static_cast<int64_t>(kMaxUint32))) { |
1715 return false; | 1669 return false; |
1716 } | 1670 } |
1717 } | 1671 } |
1718 } | 1672 } |
1719 if (!def->HasUses()) { | 1673 if (!def->HasUses()) { |
1720 // No uses, skip. | 1674 // No uses, skip. |
1721 return false; | 1675 return false; |
1722 } | 1676 } |
1723 return AllUsesAreUint32Narrowing(def->input_use_list()) && | 1677 return AllUsesAreUint32Narrowing(def->input_use_list()) && |
1724 AllUsesAreUint32Narrowing(def->env_use_list()); | 1678 AllUsesAreUint32Narrowing(def->env_use_list()); |
1725 } | 1679 } |
1726 | 1680 |
1727 | |
1728 void IntegerInstructionSelector::Propagate() { | 1681 void IntegerInstructionSelector::Propagate() { |
1729 ASSERT(selected_uint32_defs_ != NULL); | 1682 ASSERT(selected_uint32_defs_ != NULL); |
1730 bool changed = true; | 1683 bool changed = true; |
1731 intptr_t iteration = 0; | 1684 intptr_t iteration = 0; |
1732 while (changed) { | 1685 while (changed) { |
1733 if (FLAG_trace_integer_ir_selection) { | 1686 if (FLAG_trace_integer_ir_selection) { |
1734 THR_Print("+++ Iteration: %" Pd "\n", iteration++); | 1687 THR_Print("+++ Iteration: %" Pd "\n", iteration++); |
1735 } | 1688 } |
1736 changed = false; | 1689 changed = false; |
1737 for (intptr_t i = 0; i < potential_uint32_defs_.length(); i++) { | 1690 for (intptr_t i = 0; i < potential_uint32_defs_.length(); i++) { |
(...skipping 15 matching lines...) Expand all Loading... |
1753 // Haven't reached fixed point yet. | 1706 // Haven't reached fixed point yet. |
1754 changed = true; | 1707 changed = true; |
1755 } | 1708 } |
1756 } | 1709 } |
1757 } | 1710 } |
1758 if (FLAG_trace_integer_ir_selection) { | 1711 if (FLAG_trace_integer_ir_selection) { |
1759 THR_Print("Reached fixed point\n"); | 1712 THR_Print("Reached fixed point\n"); |
1760 } | 1713 } |
1761 } | 1714 } |
1762 | 1715 |
1763 | |
1764 Definition* IntegerInstructionSelector::ConstructReplacementFor( | 1716 Definition* IntegerInstructionSelector::ConstructReplacementFor( |
1765 Definition* def) { | 1717 Definition* def) { |
1766 // Should only see mint definitions. | 1718 // Should only see mint definitions. |
1767 ASSERT(IsPotentialUint32Definition(def)); | 1719 ASSERT(IsPotentialUint32Definition(def)); |
1768 // Should not see constant instructions. | 1720 // Should not see constant instructions. |
1769 ASSERT(!def->IsConstant()); | 1721 ASSERT(!def->IsConstant()); |
1770 if (def->IsBinaryMintOp()) { | 1722 if (def->IsBinaryMintOp()) { |
1771 BinaryMintOpInstr* op = def->AsBinaryMintOp(); | 1723 BinaryMintOpInstr* op = def->AsBinaryMintOp(); |
1772 Token::Kind op_kind = op->op_kind(); | 1724 Token::Kind op_kind = op->op_kind(); |
1773 Value* left = op->left()->CopyWithType(); | 1725 Value* left = op->left()->CopyWithType(); |
(...skipping 19 matching lines...) Expand all Loading... |
1793 Token::Kind op_kind = op->op_kind(); | 1745 Token::Kind op_kind = op->op_kind(); |
1794 Value* left = op->left()->CopyWithType(); | 1746 Value* left = op->left()->CopyWithType(); |
1795 Value* right = op->right()->CopyWithType(); | 1747 Value* right = op->right()->CopyWithType(); |
1796 intptr_t deopt_id = op->DeoptimizationTarget(); | 1748 intptr_t deopt_id = op->DeoptimizationTarget(); |
1797 return new (Z) ShiftUint32OpInstr(op_kind, left, right, deopt_id); | 1749 return new (Z) ShiftUint32OpInstr(op_kind, left, right, deopt_id); |
1798 } | 1750 } |
1799 UNREACHABLE(); | 1751 UNREACHABLE(); |
1800 return NULL; | 1752 return NULL; |
1801 } | 1753 } |
1802 | 1754 |
1803 | |
1804 void IntegerInstructionSelector::ReplaceInstructions() { | 1755 void IntegerInstructionSelector::ReplaceInstructions() { |
1805 if (FLAG_trace_integer_ir_selection) { | 1756 if (FLAG_trace_integer_ir_selection) { |
1806 THR_Print("++++ Replacing instructions:\n"); | 1757 THR_Print("++++ Replacing instructions:\n"); |
1807 } | 1758 } |
1808 for (intptr_t i = 0; i < potential_uint32_defs_.length(); i++) { | 1759 for (intptr_t i = 0; i < potential_uint32_defs_.length(); i++) { |
1809 Definition* defn = potential_uint32_defs_[i]; | 1760 Definition* defn = potential_uint32_defs_[i]; |
1810 if (!selected_uint32_defs_->Contains(defn->ssa_temp_index())) { | 1761 if (!selected_uint32_defs_->Contains(defn->ssa_temp_index())) { |
1811 // Not a candidate. | 1762 // Not a candidate. |
1812 continue; | 1763 continue; |
1813 } | 1764 } |
1814 Definition* replacement = ConstructReplacementFor(defn); | 1765 Definition* replacement = ConstructReplacementFor(defn); |
1815 ASSERT(replacement != NULL); | 1766 ASSERT(replacement != NULL); |
1816 if (FLAG_support_il_printer && FLAG_trace_integer_ir_selection) { | 1767 if (FLAG_support_il_printer && FLAG_trace_integer_ir_selection) { |
1817 THR_Print("Replacing %s with %s\n", defn->ToCString(), | 1768 THR_Print("Replacing %s with %s\n", defn->ToCString(), |
1818 replacement->ToCString()); | 1769 replacement->ToCString()); |
1819 } | 1770 } |
1820 if (!Range::IsUnknown(defn->range())) { | 1771 if (!Range::IsUnknown(defn->range())) { |
1821 replacement->set_range(*defn->range()); | 1772 replacement->set_range(*defn->range()); |
1822 } | 1773 } |
1823 defn->ReplaceWith(replacement, NULL); | 1774 defn->ReplaceWith(replacement, NULL); |
1824 ASSERT(flow_graph_->VerifyUseLists()); | 1775 ASSERT(flow_graph_->VerifyUseLists()); |
1825 } | 1776 } |
1826 } | 1777 } |
1827 | 1778 |
1828 | |
1829 RangeBoundary RangeBoundary::FromDefinition(Definition* defn, int64_t offs) { | 1779 RangeBoundary RangeBoundary::FromDefinition(Definition* defn, int64_t offs) { |
1830 if (defn->IsConstant() && defn->AsConstant()->value().IsSmi()) { | 1780 if (defn->IsConstant() && defn->AsConstant()->value().IsSmi()) { |
1831 return FromConstant(Smi::Cast(defn->AsConstant()->value()).Value() + offs); | 1781 return FromConstant(Smi::Cast(defn->AsConstant()->value()).Value() + offs); |
1832 } | 1782 } |
1833 return RangeBoundary(kSymbol, reinterpret_cast<intptr_t>(defn), offs); | 1783 return RangeBoundary(kSymbol, reinterpret_cast<intptr_t>(defn), offs); |
1834 } | 1784 } |
1835 | 1785 |
1836 | |
1837 RangeBoundary RangeBoundary::LowerBound() const { | 1786 RangeBoundary RangeBoundary::LowerBound() const { |
1838 if (IsInfinity()) { | 1787 if (IsInfinity()) { |
1839 return NegativeInfinity(); | 1788 return NegativeInfinity(); |
1840 } | 1789 } |
1841 if (IsConstant()) return *this; | 1790 if (IsConstant()) return *this; |
1842 return Add(Range::ConstantMinSmi(symbol()->range()), | 1791 return Add(Range::ConstantMinSmi(symbol()->range()), |
1843 RangeBoundary::FromConstant(offset_), NegativeInfinity()); | 1792 RangeBoundary::FromConstant(offset_), NegativeInfinity()); |
1844 } | 1793 } |
1845 | 1794 |
1846 | |
1847 RangeBoundary RangeBoundary::UpperBound() const { | 1795 RangeBoundary RangeBoundary::UpperBound() const { |
1848 if (IsInfinity()) { | 1796 if (IsInfinity()) { |
1849 return PositiveInfinity(); | 1797 return PositiveInfinity(); |
1850 } | 1798 } |
1851 if (IsConstant()) return *this; | 1799 if (IsConstant()) return *this; |
1852 | 1800 |
1853 return Add(Range::ConstantMaxSmi(symbol()->range()), | 1801 return Add(Range::ConstantMaxSmi(symbol()->range()), |
1854 RangeBoundary::FromConstant(offset_), PositiveInfinity()); | 1802 RangeBoundary::FromConstant(offset_), PositiveInfinity()); |
1855 } | 1803 } |
1856 | 1804 |
1857 | |
1858 RangeBoundary RangeBoundary::Add(const RangeBoundary& a, | 1805 RangeBoundary RangeBoundary::Add(const RangeBoundary& a, |
1859 const RangeBoundary& b, | 1806 const RangeBoundary& b, |
1860 const RangeBoundary& overflow) { | 1807 const RangeBoundary& overflow) { |
1861 if (a.IsInfinity() || b.IsInfinity()) return overflow; | 1808 if (a.IsInfinity() || b.IsInfinity()) return overflow; |
1862 | 1809 |
1863 ASSERT(a.IsConstant() && b.IsConstant()); | 1810 ASSERT(a.IsConstant() && b.IsConstant()); |
1864 if (Utils::WillAddOverflow(a.ConstantValue(), b.ConstantValue())) { | 1811 if (Utils::WillAddOverflow(a.ConstantValue(), b.ConstantValue())) { |
1865 return overflow; | 1812 return overflow; |
1866 } | 1813 } |
1867 | 1814 |
1868 int64_t result = a.ConstantValue() + b.ConstantValue(); | 1815 int64_t result = a.ConstantValue() + b.ConstantValue(); |
1869 | 1816 |
1870 return RangeBoundary::FromConstant(result); | 1817 return RangeBoundary::FromConstant(result); |
1871 } | 1818 } |
1872 | 1819 |
1873 | |
1874 RangeBoundary RangeBoundary::Sub(const RangeBoundary& a, | 1820 RangeBoundary RangeBoundary::Sub(const RangeBoundary& a, |
1875 const RangeBoundary& b, | 1821 const RangeBoundary& b, |
1876 const RangeBoundary& overflow) { | 1822 const RangeBoundary& overflow) { |
1877 if (a.IsInfinity() || b.IsInfinity()) return overflow; | 1823 if (a.IsInfinity() || b.IsInfinity()) return overflow; |
1878 ASSERT(a.IsConstant() && b.IsConstant()); | 1824 ASSERT(a.IsConstant() && b.IsConstant()); |
1879 if (Utils::WillSubOverflow(a.ConstantValue(), b.ConstantValue())) { | 1825 if (Utils::WillSubOverflow(a.ConstantValue(), b.ConstantValue())) { |
1880 return overflow; | 1826 return overflow; |
1881 } | 1827 } |
1882 | 1828 |
1883 int64_t result = a.ConstantValue() - b.ConstantValue(); | 1829 int64_t result = a.ConstantValue() - b.ConstantValue(); |
1884 | 1830 |
1885 return RangeBoundary::FromConstant(result); | 1831 return RangeBoundary::FromConstant(result); |
1886 } | 1832 } |
1887 | 1833 |
1888 | |
1889 bool RangeBoundary::SymbolicAdd(const RangeBoundary& a, | 1834 bool RangeBoundary::SymbolicAdd(const RangeBoundary& a, |
1890 const RangeBoundary& b, | 1835 const RangeBoundary& b, |
1891 RangeBoundary* result) { | 1836 RangeBoundary* result) { |
1892 if (a.IsSymbol() && b.IsConstant()) { | 1837 if (a.IsSymbol() && b.IsConstant()) { |
1893 if (Utils::WillAddOverflow(a.offset(), b.ConstantValue())) { | 1838 if (Utils::WillAddOverflow(a.offset(), b.ConstantValue())) { |
1894 return false; | 1839 return false; |
1895 } | 1840 } |
1896 | 1841 |
1897 const int64_t offset = a.offset() + b.ConstantValue(); | 1842 const int64_t offset = a.offset() + b.ConstantValue(); |
1898 | 1843 |
1899 *result = RangeBoundary::FromDefinition(a.symbol(), offset); | 1844 *result = RangeBoundary::FromDefinition(a.symbol(), offset); |
1900 return true; | 1845 return true; |
1901 } else if (b.IsSymbol() && a.IsConstant()) { | 1846 } else if (b.IsSymbol() && a.IsConstant()) { |
1902 return SymbolicAdd(b, a, result); | 1847 return SymbolicAdd(b, a, result); |
1903 } | 1848 } |
1904 return false; | 1849 return false; |
1905 } | 1850 } |
1906 | 1851 |
1907 | |
1908 bool RangeBoundary::SymbolicSub(const RangeBoundary& a, | 1852 bool RangeBoundary::SymbolicSub(const RangeBoundary& a, |
1909 const RangeBoundary& b, | 1853 const RangeBoundary& b, |
1910 RangeBoundary* result) { | 1854 RangeBoundary* result) { |
1911 if (a.IsSymbol() && b.IsConstant()) { | 1855 if (a.IsSymbol() && b.IsConstant()) { |
1912 if (Utils::WillSubOverflow(a.offset(), b.ConstantValue())) { | 1856 if (Utils::WillSubOverflow(a.offset(), b.ConstantValue())) { |
1913 return false; | 1857 return false; |
1914 } | 1858 } |
1915 | 1859 |
1916 const int64_t offset = a.offset() - b.ConstantValue(); | 1860 const int64_t offset = a.offset() - b.ConstantValue(); |
1917 | 1861 |
1918 *result = RangeBoundary::FromDefinition(a.symbol(), offset); | 1862 *result = RangeBoundary::FromDefinition(a.symbol(), offset); |
1919 return true; | 1863 return true; |
1920 } | 1864 } |
1921 return false; | 1865 return false; |
1922 } | 1866 } |
1923 | 1867 |
1924 | |
1925 bool RangeBoundary::Equals(const RangeBoundary& other) const { | 1868 bool RangeBoundary::Equals(const RangeBoundary& other) const { |
1926 if (IsConstant() && other.IsConstant()) { | 1869 if (IsConstant() && other.IsConstant()) { |
1927 return ConstantValue() == other.ConstantValue(); | 1870 return ConstantValue() == other.ConstantValue(); |
1928 } else if (IsInfinity() && other.IsInfinity()) { | 1871 } else if (IsInfinity() && other.IsInfinity()) { |
1929 return kind() == other.kind(); | 1872 return kind() == other.kind(); |
1930 } else if (IsSymbol() && other.IsSymbol()) { | 1873 } else if (IsSymbol() && other.IsSymbol()) { |
1931 return (offset() == other.offset()) && DependOnSameSymbol(*this, other); | 1874 return (offset() == other.offset()) && DependOnSameSymbol(*this, other); |
1932 } else if (IsUnknown() && other.IsUnknown()) { | 1875 } else if (IsUnknown() && other.IsUnknown()) { |
1933 return true; | 1876 return true; |
1934 } | 1877 } |
1935 return false; | 1878 return false; |
1936 } | 1879 } |
1937 | 1880 |
1938 | |
1939 RangeBoundary RangeBoundary::Shl(const RangeBoundary& value_boundary, | 1881 RangeBoundary RangeBoundary::Shl(const RangeBoundary& value_boundary, |
1940 int64_t shift_count, | 1882 int64_t shift_count, |
1941 const RangeBoundary& overflow) { | 1883 const RangeBoundary& overflow) { |
1942 ASSERT(value_boundary.IsConstant()); | 1884 ASSERT(value_boundary.IsConstant()); |
1943 ASSERT(shift_count >= 0); | 1885 ASSERT(shift_count >= 0); |
1944 int64_t limit = 64 - shift_count; | 1886 int64_t limit = 64 - shift_count; |
1945 int64_t value = value_boundary.ConstantValue(); | 1887 int64_t value = value_boundary.ConstantValue(); |
1946 | 1888 |
1947 if ((value == 0) || (shift_count == 0) || | 1889 if ((value == 0) || (shift_count == 0) || |
1948 ((limit > 0) && Utils::IsInt(static_cast<int>(limit), value))) { | 1890 ((limit > 0) && Utils::IsInt(static_cast<int>(limit), value))) { |
1949 // Result stays in 64 bit range. | 1891 // Result stays in 64 bit range. |
1950 int64_t result = value << shift_count; | 1892 int64_t result = value << shift_count; |
1951 return RangeBoundary(result); | 1893 return RangeBoundary(result); |
1952 } | 1894 } |
1953 | 1895 |
1954 return overflow; | 1896 return overflow; |
1955 } | 1897 } |
1956 | 1898 |
1957 | |
1958 static RangeBoundary CanonicalizeBoundary(const RangeBoundary& a, | 1899 static RangeBoundary CanonicalizeBoundary(const RangeBoundary& a, |
1959 const RangeBoundary& overflow) { | 1900 const RangeBoundary& overflow) { |
1960 if (a.IsConstant() || a.IsInfinity()) { | 1901 if (a.IsConstant() || a.IsInfinity()) { |
1961 return a; | 1902 return a; |
1962 } | 1903 } |
1963 | 1904 |
1964 int64_t offset = a.offset(); | 1905 int64_t offset = a.offset(); |
1965 Definition* symbol = a.symbol(); | 1906 Definition* symbol = a.symbol(); |
1966 | 1907 |
1967 bool changed; | 1908 bool changed; |
(...skipping 41 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
2009 | 1950 |
2010 default: | 1951 default: |
2011 break; | 1952 break; |
2012 } | 1953 } |
2013 } | 1954 } |
2014 } while (changed); | 1955 } while (changed); |
2015 | 1956 |
2016 return RangeBoundary::FromDefinition(symbol, offset); | 1957 return RangeBoundary::FromDefinition(symbol, offset); |
2017 } | 1958 } |
2018 | 1959 |
2019 | |
2020 static bool CanonicalizeMaxBoundary(RangeBoundary* a) { | 1960 static bool CanonicalizeMaxBoundary(RangeBoundary* a) { |
2021 if (!a->IsSymbol()) return false; | 1961 if (!a->IsSymbol()) return false; |
2022 | 1962 |
2023 Range* range = a->symbol()->range(); | 1963 Range* range = a->symbol()->range(); |
2024 if ((range == NULL) || !range->max().IsSymbol()) return false; | 1964 if ((range == NULL) || !range->max().IsSymbol()) return false; |
2025 | 1965 |
2026 | |
2027 if (Utils::WillAddOverflow(range->max().offset(), a->offset())) { | 1966 if (Utils::WillAddOverflow(range->max().offset(), a->offset())) { |
2028 *a = RangeBoundary::PositiveInfinity(); | 1967 *a = RangeBoundary::PositiveInfinity(); |
2029 return true; | 1968 return true; |
2030 } | 1969 } |
2031 | 1970 |
2032 const int64_t offset = range->max().offset() + a->offset(); | 1971 const int64_t offset = range->max().offset() + a->offset(); |
2033 | 1972 |
2034 *a = CanonicalizeBoundary( | 1973 *a = CanonicalizeBoundary( |
2035 RangeBoundary::FromDefinition(range->max().symbol(), offset), | 1974 RangeBoundary::FromDefinition(range->max().symbol(), offset), |
2036 RangeBoundary::PositiveInfinity()); | 1975 RangeBoundary::PositiveInfinity()); |
2037 | 1976 |
2038 return true; | 1977 return true; |
2039 } | 1978 } |
2040 | 1979 |
2041 | |
2042 static bool CanonicalizeMinBoundary(RangeBoundary* a) { | 1980 static bool CanonicalizeMinBoundary(RangeBoundary* a) { |
2043 if (!a->IsSymbol()) return false; | 1981 if (!a->IsSymbol()) return false; |
2044 | 1982 |
2045 Range* range = a->symbol()->range(); | 1983 Range* range = a->symbol()->range(); |
2046 if ((range == NULL) || !range->min().IsSymbol()) return false; | 1984 if ((range == NULL) || !range->min().IsSymbol()) return false; |
2047 | 1985 |
2048 if (Utils::WillAddOverflow(range->min().offset(), a->offset())) { | 1986 if (Utils::WillAddOverflow(range->min().offset(), a->offset())) { |
2049 *a = RangeBoundary::NegativeInfinity(); | 1987 *a = RangeBoundary::NegativeInfinity(); |
2050 return true; | 1988 return true; |
2051 } | 1989 } |
(...skipping 24 matching lines...) Expand all Loading... |
2076 if (DependOnSameSymbol(canonical_a, canonical_b)) { | 2014 if (DependOnSameSymbol(canonical_a, canonical_b)) { |
2077 *a = canonical_a; | 2015 *a = canonical_a; |
2078 *b = canonical_b; | 2016 *b = canonical_b; |
2079 return true; | 2017 return true; |
2080 } | 2018 } |
2081 } while (op(&canonical_a) || op(&canonical_b)); | 2019 } while (op(&canonical_a) || op(&canonical_b)); |
2082 | 2020 |
2083 return false; | 2021 return false; |
2084 } | 2022 } |
2085 | 2023 |
2086 | |
2087 RangeBoundary RangeBoundary::JoinMin(RangeBoundary a, | 2024 RangeBoundary RangeBoundary::JoinMin(RangeBoundary a, |
2088 RangeBoundary b, | 2025 RangeBoundary b, |
2089 RangeBoundary::RangeSize size) { | 2026 RangeBoundary::RangeSize size) { |
2090 if (a.Equals(b)) { | 2027 if (a.Equals(b)) { |
2091 return b; | 2028 return b; |
2092 } | 2029 } |
2093 | 2030 |
2094 if (CanonicalizeForComparison(&a, &b, &CanonicalizeMinBoundary, | 2031 if (CanonicalizeForComparison(&a, &b, &CanonicalizeMinBoundary, |
2095 RangeBoundary::NegativeInfinity())) { | 2032 RangeBoundary::NegativeInfinity())) { |
2096 return (a.offset() <= b.offset()) ? a : b; | 2033 return (a.offset() <= b.offset()) ? a : b; |
2097 } | 2034 } |
2098 | 2035 |
2099 const int64_t inf_a = a.LowerBound(size); | 2036 const int64_t inf_a = a.LowerBound(size); |
2100 const int64_t inf_b = b.LowerBound(size); | 2037 const int64_t inf_b = b.LowerBound(size); |
2101 const int64_t sup_a = a.UpperBound(size); | 2038 const int64_t sup_a = a.UpperBound(size); |
2102 const int64_t sup_b = b.UpperBound(size); | 2039 const int64_t sup_b = b.UpperBound(size); |
2103 | 2040 |
2104 if ((sup_a <= inf_b) && !a.LowerBound().Overflowed(size)) { | 2041 if ((sup_a <= inf_b) && !a.LowerBound().Overflowed(size)) { |
2105 return a; | 2042 return a; |
2106 } else if ((sup_b <= inf_a) && !b.LowerBound().Overflowed(size)) { | 2043 } else if ((sup_b <= inf_a) && !b.LowerBound().Overflowed(size)) { |
2107 return b; | 2044 return b; |
2108 } else { | 2045 } else { |
2109 return RangeBoundary::FromConstant(Utils::Minimum(inf_a, inf_b)); | 2046 return RangeBoundary::FromConstant(Utils::Minimum(inf_a, inf_b)); |
2110 } | 2047 } |
2111 } | 2048 } |
2112 | 2049 |
2113 | |
2114 RangeBoundary RangeBoundary::JoinMax(RangeBoundary a, | 2050 RangeBoundary RangeBoundary::JoinMax(RangeBoundary a, |
2115 RangeBoundary b, | 2051 RangeBoundary b, |
2116 RangeBoundary::RangeSize size) { | 2052 RangeBoundary::RangeSize size) { |
2117 if (a.Equals(b)) { | 2053 if (a.Equals(b)) { |
2118 return b; | 2054 return b; |
2119 } | 2055 } |
2120 | 2056 |
2121 if (CanonicalizeForComparison(&a, &b, &CanonicalizeMaxBoundary, | 2057 if (CanonicalizeForComparison(&a, &b, &CanonicalizeMaxBoundary, |
2122 RangeBoundary::PositiveInfinity())) { | 2058 RangeBoundary::PositiveInfinity())) { |
2123 return (a.offset() >= b.offset()) ? a : b; | 2059 return (a.offset() >= b.offset()) ? a : b; |
2124 } | 2060 } |
2125 | 2061 |
2126 const int64_t inf_a = a.LowerBound(size); | 2062 const int64_t inf_a = a.LowerBound(size); |
2127 const int64_t inf_b = b.LowerBound(size); | 2063 const int64_t inf_b = b.LowerBound(size); |
2128 const int64_t sup_a = a.UpperBound(size); | 2064 const int64_t sup_a = a.UpperBound(size); |
2129 const int64_t sup_b = b.UpperBound(size); | 2065 const int64_t sup_b = b.UpperBound(size); |
2130 | 2066 |
2131 if ((sup_a <= inf_b) && !b.UpperBound().Overflowed(size)) { | 2067 if ((sup_a <= inf_b) && !b.UpperBound().Overflowed(size)) { |
2132 return b; | 2068 return b; |
2133 } else if ((sup_b <= inf_a) && !a.UpperBound().Overflowed(size)) { | 2069 } else if ((sup_b <= inf_a) && !a.UpperBound().Overflowed(size)) { |
2134 return a; | 2070 return a; |
2135 } else { | 2071 } else { |
2136 return RangeBoundary::FromConstant(Utils::Maximum(sup_a, sup_b)); | 2072 return RangeBoundary::FromConstant(Utils::Maximum(sup_a, sup_b)); |
2137 } | 2073 } |
2138 } | 2074 } |
2139 | 2075 |
2140 | |
2141 RangeBoundary RangeBoundary::IntersectionMin(RangeBoundary a, RangeBoundary b) { | 2076 RangeBoundary RangeBoundary::IntersectionMin(RangeBoundary a, RangeBoundary b) { |
2142 ASSERT(!a.IsPositiveInfinity() && !b.IsPositiveInfinity()); | 2077 ASSERT(!a.IsPositiveInfinity() && !b.IsPositiveInfinity()); |
2143 ASSERT(!a.IsUnknown() && !b.IsUnknown()); | 2078 ASSERT(!a.IsUnknown() && !b.IsUnknown()); |
2144 | 2079 |
2145 if (a.Equals(b)) { | 2080 if (a.Equals(b)) { |
2146 return a; | 2081 return a; |
2147 } | 2082 } |
2148 | 2083 |
2149 if (a.IsMinimumOrBelow(RangeBoundary::kRangeBoundarySmi)) { | 2084 if (a.IsMinimumOrBelow(RangeBoundary::kRangeBoundarySmi)) { |
2150 return b; | 2085 return b; |
2151 } else if (b.IsMinimumOrBelow(RangeBoundary::kRangeBoundarySmi)) { | 2086 } else if (b.IsMinimumOrBelow(RangeBoundary::kRangeBoundarySmi)) { |
2152 return a; | 2087 return a; |
2153 } | 2088 } |
2154 | 2089 |
2155 if (CanonicalizeForComparison(&a, &b, &CanonicalizeMinBoundary, | 2090 if (CanonicalizeForComparison(&a, &b, &CanonicalizeMinBoundary, |
2156 RangeBoundary::NegativeInfinity())) { | 2091 RangeBoundary::NegativeInfinity())) { |
2157 return (a.offset() >= b.offset()) ? a : b; | 2092 return (a.offset() >= b.offset()) ? a : b; |
2158 } | 2093 } |
2159 | 2094 |
2160 const int64_t inf_a = a.SmiLowerBound(); | 2095 const int64_t inf_a = a.SmiLowerBound(); |
2161 const int64_t inf_b = b.SmiLowerBound(); | 2096 const int64_t inf_b = b.SmiLowerBound(); |
2162 | 2097 |
2163 return (inf_a >= inf_b) ? a : b; | 2098 return (inf_a >= inf_b) ? a : b; |
2164 } | 2099 } |
2165 | 2100 |
2166 | |
2167 RangeBoundary RangeBoundary::IntersectionMax(RangeBoundary a, RangeBoundary b) { | 2101 RangeBoundary RangeBoundary::IntersectionMax(RangeBoundary a, RangeBoundary b) { |
2168 ASSERT(!a.IsNegativeInfinity() && !b.IsNegativeInfinity()); | 2102 ASSERT(!a.IsNegativeInfinity() && !b.IsNegativeInfinity()); |
2169 ASSERT(!a.IsUnknown() && !b.IsUnknown()); | 2103 ASSERT(!a.IsUnknown() && !b.IsUnknown()); |
2170 | 2104 |
2171 if (a.Equals(b)) { | 2105 if (a.Equals(b)) { |
2172 return a; | 2106 return a; |
2173 } | 2107 } |
2174 | 2108 |
2175 if (a.IsMaximumOrAbove(RangeBoundary::kRangeBoundarySmi)) { | 2109 if (a.IsMaximumOrAbove(RangeBoundary::kRangeBoundarySmi)) { |
2176 return b; | 2110 return b; |
2177 } else if (b.IsMaximumOrAbove(RangeBoundary::kRangeBoundarySmi)) { | 2111 } else if (b.IsMaximumOrAbove(RangeBoundary::kRangeBoundarySmi)) { |
2178 return a; | 2112 return a; |
2179 } | 2113 } |
2180 | 2114 |
2181 if (CanonicalizeForComparison(&a, &b, &CanonicalizeMaxBoundary, | 2115 if (CanonicalizeForComparison(&a, &b, &CanonicalizeMaxBoundary, |
2182 RangeBoundary::PositiveInfinity())) { | 2116 RangeBoundary::PositiveInfinity())) { |
2183 return (a.offset() <= b.offset()) ? a : b; | 2117 return (a.offset() <= b.offset()) ? a : b; |
2184 } | 2118 } |
2185 | 2119 |
2186 const int64_t sup_a = a.SmiUpperBound(); | 2120 const int64_t sup_a = a.SmiUpperBound(); |
2187 const int64_t sup_b = b.SmiUpperBound(); | 2121 const int64_t sup_b = b.SmiUpperBound(); |
2188 | 2122 |
2189 return (sup_a <= sup_b) ? a : b; | 2123 return (sup_a <= sup_b) ? a : b; |
2190 } | 2124 } |
2191 | 2125 |
2192 | |
2193 int64_t RangeBoundary::ConstantValue() const { | 2126 int64_t RangeBoundary::ConstantValue() const { |
2194 ASSERT(IsConstant()); | 2127 ASSERT(IsConstant()); |
2195 return value_; | 2128 return value_; |
2196 } | 2129 } |
2197 | 2130 |
2198 | |
2199 bool Range::IsPositive() const { | 2131 bool Range::IsPositive() const { |
2200 return OnlyGreaterThanOrEqualTo(0); | 2132 return OnlyGreaterThanOrEqualTo(0); |
2201 } | 2133 } |
2202 | 2134 |
2203 | |
2204 bool Range::OnlyLessThanOrEqualTo(int64_t val) const { | 2135 bool Range::OnlyLessThanOrEqualTo(int64_t val) const { |
2205 const RangeBoundary upper_bound = max().UpperBound(); | 2136 const RangeBoundary upper_bound = max().UpperBound(); |
2206 return !upper_bound.IsPositiveInfinity() && | 2137 return !upper_bound.IsPositiveInfinity() && |
2207 (upper_bound.ConstantValue() <= val); | 2138 (upper_bound.ConstantValue() <= val); |
2208 } | 2139 } |
2209 | 2140 |
2210 | |
2211 bool Range::OnlyGreaterThanOrEqualTo(int64_t val) const { | 2141 bool Range::OnlyGreaterThanOrEqualTo(int64_t val) const { |
2212 const RangeBoundary lower_bound = min().LowerBound(); | 2142 const RangeBoundary lower_bound = min().LowerBound(); |
2213 return !lower_bound.IsNegativeInfinity() && | 2143 return !lower_bound.IsNegativeInfinity() && |
2214 (lower_bound.ConstantValue() >= val); | 2144 (lower_bound.ConstantValue() >= val); |
2215 } | 2145 } |
2216 | 2146 |
2217 | |
2218 // Inclusive. | 2147 // Inclusive. |
2219 bool Range::IsWithin(int64_t min_int, int64_t max_int) const { | 2148 bool Range::IsWithin(int64_t min_int, int64_t max_int) const { |
2220 return OnlyGreaterThanOrEqualTo(min_int) && OnlyLessThanOrEqualTo(max_int); | 2149 return OnlyGreaterThanOrEqualTo(min_int) && OnlyLessThanOrEqualTo(max_int); |
2221 } | 2150 } |
2222 | 2151 |
2223 | |
2224 bool Range::Overlaps(int64_t min_int, int64_t max_int) const { | 2152 bool Range::Overlaps(int64_t min_int, int64_t max_int) const { |
2225 RangeBoundary lower = min().LowerBound(); | 2153 RangeBoundary lower = min().LowerBound(); |
2226 RangeBoundary upper = max().UpperBound(); | 2154 RangeBoundary upper = max().UpperBound(); |
2227 const int64_t this_min = | 2155 const int64_t this_min = |
2228 lower.IsNegativeInfinity() ? RangeBoundary::kMin : lower.ConstantValue(); | 2156 lower.IsNegativeInfinity() ? RangeBoundary::kMin : lower.ConstantValue(); |
2229 const int64_t this_max = | 2157 const int64_t this_max = |
2230 upper.IsPositiveInfinity() ? RangeBoundary::kMax : upper.ConstantValue(); | 2158 upper.IsPositiveInfinity() ? RangeBoundary::kMax : upper.ConstantValue(); |
2231 if ((this_min <= min_int) && (min_int <= this_max)) return true; | 2159 if ((this_min <= min_int) && (min_int <= this_max)) return true; |
2232 if ((this_min <= max_int) && (max_int <= this_max)) return true; | 2160 if ((this_min <= max_int) && (max_int <= this_max)) return true; |
2233 if ((min_int < this_min) && (max_int > this_max)) return true; | 2161 if ((min_int < this_min) && (max_int > this_max)) return true; |
2234 return false; | 2162 return false; |
2235 } | 2163 } |
2236 | 2164 |
2237 | |
2238 bool Range::IsUnsatisfiable() const { | 2165 bool Range::IsUnsatisfiable() const { |
2239 // Infinity case: [+inf, ...] || [..., -inf] | 2166 // Infinity case: [+inf, ...] || [..., -inf] |
2240 if (min().IsPositiveInfinity() || max().IsNegativeInfinity()) { | 2167 if (min().IsPositiveInfinity() || max().IsNegativeInfinity()) { |
2241 return true; | 2168 return true; |
2242 } | 2169 } |
2243 // Constant case: For example [0, -1]. | 2170 // Constant case: For example [0, -1]. |
2244 if (Range::ConstantMin(this).ConstantValue() > | 2171 if (Range::ConstantMin(this).ConstantValue() > |
2245 Range::ConstantMax(this).ConstantValue()) { | 2172 Range::ConstantMax(this).ConstantValue()) { |
2246 return true; | 2173 return true; |
2247 } | 2174 } |
2248 // Symbol case: For example [v+1, v]. | 2175 // Symbol case: For example [v+1, v]. |
2249 return DependOnSameSymbol(min(), max()) && min().offset() > max().offset(); | 2176 return DependOnSameSymbol(min(), max()) && min().offset() > max().offset(); |
2250 } | 2177 } |
2251 | 2178 |
2252 | |
2253 void Range::Clamp(RangeBoundary::RangeSize size) { | 2179 void Range::Clamp(RangeBoundary::RangeSize size) { |
2254 min_ = min_.Clamp(size); | 2180 min_ = min_.Clamp(size); |
2255 max_ = max_.Clamp(size); | 2181 max_ = max_.Clamp(size); |
2256 } | 2182 } |
2257 | 2183 |
2258 | |
2259 void Range::ClampToConstant(RangeBoundary::RangeSize size) { | 2184 void Range::ClampToConstant(RangeBoundary::RangeSize size) { |
2260 min_ = min_.LowerBound().Clamp(size); | 2185 min_ = min_.LowerBound().Clamp(size); |
2261 max_ = max_.UpperBound().Clamp(size); | 2186 max_ = max_.UpperBound().Clamp(size); |
2262 } | 2187 } |
2263 | 2188 |
2264 | |
2265 void Range::Shl(const Range* left, | 2189 void Range::Shl(const Range* left, |
2266 const Range* right, | 2190 const Range* right, |
2267 RangeBoundary* result_min, | 2191 RangeBoundary* result_min, |
2268 RangeBoundary* result_max) { | 2192 RangeBoundary* result_max) { |
2269 ASSERT(left != NULL); | 2193 ASSERT(left != NULL); |
2270 ASSERT(right != NULL); | 2194 ASSERT(right != NULL); |
2271 ASSERT(result_min != NULL); | 2195 ASSERT(result_min != NULL); |
2272 ASSERT(result_max != NULL); | 2196 ASSERT(result_max != NULL); |
2273 RangeBoundary left_max = Range::ConstantMax(left); | 2197 RangeBoundary left_max = Range::ConstantMax(left); |
2274 RangeBoundary left_min = Range::ConstantMin(left); | 2198 RangeBoundary left_min = Range::ConstantMin(left); |
2275 // A negative shift count always deoptimizes (and throws), so the minimum | 2199 // A negative shift count always deoptimizes (and throws), so the minimum |
2276 // shift count is zero. | 2200 // shift count is zero. |
2277 int64_t right_max = Utils::Maximum(Range::ConstantMax(right).ConstantValue(), | 2201 int64_t right_max = Utils::Maximum(Range::ConstantMax(right).ConstantValue(), |
2278 static_cast<int64_t>(0)); | 2202 static_cast<int64_t>(0)); |
2279 int64_t right_min = Utils::Maximum(Range::ConstantMin(right).ConstantValue(), | 2203 int64_t right_min = Utils::Maximum(Range::ConstantMin(right).ConstantValue(), |
2280 static_cast<int64_t>(0)); | 2204 static_cast<int64_t>(0)); |
2281 | 2205 |
2282 *result_min = RangeBoundary::Shl( | 2206 *result_min = RangeBoundary::Shl( |
2283 left_min, left_min.ConstantValue() > 0 ? right_min : right_max, | 2207 left_min, left_min.ConstantValue() > 0 ? right_min : right_max, |
2284 left_min.ConstantValue() > 0 ? RangeBoundary::PositiveInfinity() | 2208 left_min.ConstantValue() > 0 ? RangeBoundary::PositiveInfinity() |
2285 : RangeBoundary::NegativeInfinity()); | 2209 : RangeBoundary::NegativeInfinity()); |
2286 | 2210 |
2287 *result_max = RangeBoundary::Shl( | 2211 *result_max = RangeBoundary::Shl( |
2288 left_max, left_max.ConstantValue() > 0 ? right_max : right_min, | 2212 left_max, left_max.ConstantValue() > 0 ? right_max : right_min, |
2289 left_max.ConstantValue() > 0 ? RangeBoundary::PositiveInfinity() | 2213 left_max.ConstantValue() > 0 ? RangeBoundary::PositiveInfinity() |
2290 : RangeBoundary::NegativeInfinity()); | 2214 : RangeBoundary::NegativeInfinity()); |
2291 } | 2215 } |
2292 | 2216 |
2293 | |
2294 void Range::Shr(const Range* left, | 2217 void Range::Shr(const Range* left, |
2295 const Range* right, | 2218 const Range* right, |
2296 RangeBoundary* result_min, | 2219 RangeBoundary* result_min, |
2297 RangeBoundary* result_max) { | 2220 RangeBoundary* result_max) { |
2298 RangeBoundary left_max = Range::ConstantMax(left); | 2221 RangeBoundary left_max = Range::ConstantMax(left); |
2299 RangeBoundary left_min = Range::ConstantMin(left); | 2222 RangeBoundary left_min = Range::ConstantMin(left); |
2300 // A negative shift count always deoptimizes (and throws), so the minimum | 2223 // A negative shift count always deoptimizes (and throws), so the minimum |
2301 // shift count is zero. | 2224 // shift count is zero. |
2302 int64_t right_max = Utils::Maximum(Range::ConstantMax(right).ConstantValue(), | 2225 int64_t right_max = Utils::Maximum(Range::ConstantMax(right).ConstantValue(), |
2303 static_cast<int64_t>(0)); | 2226 static_cast<int64_t>(0)); |
2304 int64_t right_min = Utils::Maximum(Range::ConstantMin(right).ConstantValue(), | 2227 int64_t right_min = Utils::Maximum(Range::ConstantMin(right).ConstantValue(), |
2305 static_cast<int64_t>(0)); | 2228 static_cast<int64_t>(0)); |
2306 | 2229 |
2307 *result_min = RangeBoundary::Shr( | 2230 *result_min = RangeBoundary::Shr( |
2308 left_min, left_min.ConstantValue() > 0 ? right_max : right_min); | 2231 left_min, left_min.ConstantValue() > 0 ? right_max : right_min); |
2309 | 2232 |
2310 *result_max = RangeBoundary::Shr( | 2233 *result_max = RangeBoundary::Shr( |
2311 left_max, left_max.ConstantValue() > 0 ? right_min : right_max); | 2234 left_max, left_max.ConstantValue() > 0 ? right_min : right_max); |
2312 } | 2235 } |
2313 | 2236 |
2314 | |
2315 void Range::And(const Range* left_range, | 2237 void Range::And(const Range* left_range, |
2316 const Range* right_range, | 2238 const Range* right_range, |
2317 RangeBoundary* result_min, | 2239 RangeBoundary* result_min, |
2318 RangeBoundary* result_max) { | 2240 RangeBoundary* result_max) { |
2319 ASSERT(left_range != NULL); | 2241 ASSERT(left_range != NULL); |
2320 ASSERT(right_range != NULL); | 2242 ASSERT(right_range != NULL); |
2321 ASSERT(result_min != NULL); | 2243 ASSERT(result_min != NULL); |
2322 ASSERT(result_max != NULL); | 2244 ASSERT(result_max != NULL); |
2323 | 2245 |
2324 if (Range::ConstantMin(right_range).ConstantValue() >= 0) { | 2246 if (Range::ConstantMin(right_range).ConstantValue() >= 0) { |
2325 *result_min = RangeBoundary::FromConstant(0); | 2247 *result_min = RangeBoundary::FromConstant(0); |
2326 *result_max = Range::ConstantMax(right_range); | 2248 *result_max = Range::ConstantMax(right_range); |
2327 return; | 2249 return; |
2328 } | 2250 } |
2329 | 2251 |
2330 if (Range::ConstantMin(left_range).ConstantValue() >= 0) { | 2252 if (Range::ConstantMin(left_range).ConstantValue() >= 0) { |
2331 *result_min = RangeBoundary::FromConstant(0); | 2253 *result_min = RangeBoundary::FromConstant(0); |
2332 *result_max = Range::ConstantMax(left_range); | 2254 *result_max = Range::ConstantMax(left_range); |
2333 return; | 2255 return; |
2334 } | 2256 } |
2335 | 2257 |
2336 BitwiseOp(left_range, right_range, result_min, result_max); | 2258 BitwiseOp(left_range, right_range, result_min, result_max); |
2337 } | 2259 } |
2338 | 2260 |
2339 | |
2340 static int BitSize(const Range* range) { | 2261 static int BitSize(const Range* range) { |
2341 const int64_t min = Range::ConstantMin(range).ConstantValue(); | 2262 const int64_t min = Range::ConstantMin(range).ConstantValue(); |
2342 const int64_t max = Range::ConstantMax(range).ConstantValue(); | 2263 const int64_t max = Range::ConstantMax(range).ConstantValue(); |
2343 return Utils::Maximum(Utils::BitLength(min), Utils::BitLength(max)); | 2264 return Utils::Maximum(Utils::BitLength(min), Utils::BitLength(max)); |
2344 } | 2265 } |
2345 | 2266 |
2346 | |
2347 void Range::BitwiseOp(const Range* left_range, | 2267 void Range::BitwiseOp(const Range* left_range, |
2348 const Range* right_range, | 2268 const Range* right_range, |
2349 RangeBoundary* result_min, | 2269 RangeBoundary* result_min, |
2350 RangeBoundary* result_max) { | 2270 RangeBoundary* result_max) { |
2351 const int bitsize = Utils::Maximum(BitSize(left_range), BitSize(right_range)); | 2271 const int bitsize = Utils::Maximum(BitSize(left_range), BitSize(right_range)); |
2352 | 2272 |
2353 if (left_range->IsPositive() && right_range->IsPositive()) { | 2273 if (left_range->IsPositive() && right_range->IsPositive()) { |
2354 *result_min = RangeBoundary::FromConstant(0); | 2274 *result_min = RangeBoundary::FromConstant(0); |
2355 } else { | 2275 } else { |
2356 *result_min = | 2276 *result_min = |
2357 RangeBoundary::FromConstant(-(static_cast<int64_t>(1) << bitsize)); | 2277 RangeBoundary::FromConstant(-(static_cast<int64_t>(1) << bitsize)); |
2358 } | 2278 } |
2359 | 2279 |
2360 *result_max = | 2280 *result_max = |
2361 RangeBoundary::FromConstant((static_cast<uint64_t>(1) << bitsize) - 1); | 2281 RangeBoundary::FromConstant((static_cast<uint64_t>(1) << bitsize) - 1); |
2362 } | 2282 } |
2363 | 2283 |
2364 | |
2365 static bool IsArrayLength(Definition* defn) { | 2284 static bool IsArrayLength(Definition* defn) { |
2366 if (defn == NULL) { | 2285 if (defn == NULL) { |
2367 return false; | 2286 return false; |
2368 } | 2287 } |
2369 LoadFieldInstr* load = UnwrapConstraint(defn)->AsLoadField(); | 2288 LoadFieldInstr* load = UnwrapConstraint(defn)->AsLoadField(); |
2370 return (load != NULL) && load->IsImmutableLengthLoad(); | 2289 return (load != NULL) && load->IsImmutableLengthLoad(); |
2371 } | 2290 } |
2372 | 2291 |
2373 | |
2374 void Range::Add(const Range* left_range, | 2292 void Range::Add(const Range* left_range, |
2375 const Range* right_range, | 2293 const Range* right_range, |
2376 RangeBoundary* result_min, | 2294 RangeBoundary* result_min, |
2377 RangeBoundary* result_max, | 2295 RangeBoundary* result_max, |
2378 Definition* left_defn) { | 2296 Definition* left_defn) { |
2379 ASSERT(left_range != NULL); | 2297 ASSERT(left_range != NULL); |
2380 ASSERT(right_range != NULL); | 2298 ASSERT(right_range != NULL); |
2381 ASSERT(result_min != NULL); | 2299 ASSERT(result_min != NULL); |
2382 ASSERT(result_max != NULL); | 2300 ASSERT(result_max != NULL); |
2383 | 2301 |
(...skipping 10 matching lines...) Expand all Loading... |
2394 right_range->min().LowerBound(), | 2312 right_range->min().LowerBound(), |
2395 RangeBoundary::NegativeInfinity()); | 2313 RangeBoundary::NegativeInfinity()); |
2396 } | 2314 } |
2397 if (!RangeBoundary::SymbolicAdd(left_max, right_range->max(), result_max)) { | 2315 if (!RangeBoundary::SymbolicAdd(left_max, right_range->max(), result_max)) { |
2398 *result_max = RangeBoundary::Add(right_range->max().UpperBound(), | 2316 *result_max = RangeBoundary::Add(right_range->max().UpperBound(), |
2399 left_range->max().UpperBound(), | 2317 left_range->max().UpperBound(), |
2400 RangeBoundary::PositiveInfinity()); | 2318 RangeBoundary::PositiveInfinity()); |
2401 } | 2319 } |
2402 } | 2320 } |
2403 | 2321 |
2404 | |
2405 void Range::Sub(const Range* left_range, | 2322 void Range::Sub(const Range* left_range, |
2406 const Range* right_range, | 2323 const Range* right_range, |
2407 RangeBoundary* result_min, | 2324 RangeBoundary* result_min, |
2408 RangeBoundary* result_max, | 2325 RangeBoundary* result_max, |
2409 Definition* left_defn) { | 2326 Definition* left_defn) { |
2410 ASSERT(left_range != NULL); | 2327 ASSERT(left_range != NULL); |
2411 ASSERT(right_range != NULL); | 2328 ASSERT(right_range != NULL); |
2412 ASSERT(result_min != NULL); | 2329 ASSERT(result_min != NULL); |
2413 ASSERT(result_max != NULL); | 2330 ASSERT(result_max != NULL); |
2414 | 2331 |
(...skipping 10 matching lines...) Expand all Loading... |
2425 right_range->max().UpperBound(), | 2342 right_range->max().UpperBound(), |
2426 RangeBoundary::NegativeInfinity()); | 2343 RangeBoundary::NegativeInfinity()); |
2427 } | 2344 } |
2428 if (!RangeBoundary::SymbolicSub(left_max, right_range->min(), result_max)) { | 2345 if (!RangeBoundary::SymbolicSub(left_max, right_range->min(), result_max)) { |
2429 *result_max = RangeBoundary::Sub(left_range->max().UpperBound(), | 2346 *result_max = RangeBoundary::Sub(left_range->max().UpperBound(), |
2430 right_range->min().LowerBound(), | 2347 right_range->min().LowerBound(), |
2431 RangeBoundary::PositiveInfinity()); | 2348 RangeBoundary::PositiveInfinity()); |
2432 } | 2349 } |
2433 } | 2350 } |
2434 | 2351 |
2435 | |
2436 void Range::Mul(const Range* left_range, | 2352 void Range::Mul(const Range* left_range, |
2437 const Range* right_range, | 2353 const Range* right_range, |
2438 RangeBoundary* result_min, | 2354 RangeBoundary* result_min, |
2439 RangeBoundary* result_max) { | 2355 RangeBoundary* result_max) { |
2440 ASSERT(left_range != NULL); | 2356 ASSERT(left_range != NULL); |
2441 ASSERT(right_range != NULL); | 2357 ASSERT(right_range != NULL); |
2442 ASSERT(result_min != NULL); | 2358 ASSERT(result_min != NULL); |
2443 ASSERT(result_max != NULL); | 2359 ASSERT(result_max != NULL); |
2444 | 2360 |
2445 const int64_t left_max = ConstantAbsMax(left_range); | 2361 const int64_t left_max = ConstantAbsMax(left_range); |
(...skipping 26 matching lines...) Expand all Loading... |
2472 OnlyNegativeOrZero(*left_range, *right_range)) { | 2388 OnlyNegativeOrZero(*left_range, *right_range)) { |
2473 *result_min = RangeBoundary::FromConstant(0); | 2389 *result_min = RangeBoundary::FromConstant(0); |
2474 *result_max = RangeBoundary::PositiveInfinity(); | 2390 *result_max = RangeBoundary::PositiveInfinity(); |
2475 return; | 2391 return; |
2476 } | 2392 } |
2477 | 2393 |
2478 *result_min = RangeBoundary::NegativeInfinity(); | 2394 *result_min = RangeBoundary::NegativeInfinity(); |
2479 *result_max = RangeBoundary::PositiveInfinity(); | 2395 *result_max = RangeBoundary::PositiveInfinity(); |
2480 } | 2396 } |
2481 | 2397 |
2482 | |
2483 // Both the a and b ranges are >= 0. | 2398 // Both the a and b ranges are >= 0. |
2484 bool Range::OnlyPositiveOrZero(const Range& a, const Range& b) { | 2399 bool Range::OnlyPositiveOrZero(const Range& a, const Range& b) { |
2485 return a.OnlyGreaterThanOrEqualTo(0) && b.OnlyGreaterThanOrEqualTo(0); | 2400 return a.OnlyGreaterThanOrEqualTo(0) && b.OnlyGreaterThanOrEqualTo(0); |
2486 } | 2401 } |
2487 | 2402 |
2488 | |
2489 // Both the a and b ranges are <= 0. | 2403 // Both the a and b ranges are <= 0. |
2490 bool Range::OnlyNegativeOrZero(const Range& a, const Range& b) { | 2404 bool Range::OnlyNegativeOrZero(const Range& a, const Range& b) { |
2491 return a.OnlyLessThanOrEqualTo(0) && b.OnlyLessThanOrEqualTo(0); | 2405 return a.OnlyLessThanOrEqualTo(0) && b.OnlyLessThanOrEqualTo(0); |
2492 } | 2406 } |
2493 | 2407 |
2494 | |
2495 // Return the maximum absolute value included in range. | 2408 // Return the maximum absolute value included in range. |
2496 int64_t Range::ConstantAbsMax(const Range* range) { | 2409 int64_t Range::ConstantAbsMax(const Range* range) { |
2497 if (range == NULL) { | 2410 if (range == NULL) { |
2498 return RangeBoundary::kMax; | 2411 return RangeBoundary::kMax; |
2499 } | 2412 } |
2500 const int64_t abs_min = Utils::Abs(Range::ConstantMin(range).ConstantValue()); | 2413 const int64_t abs_min = Utils::Abs(Range::ConstantMin(range).ConstantValue()); |
2501 const int64_t abs_max = Utils::Abs(Range::ConstantMax(range).ConstantValue()); | 2414 const int64_t abs_max = Utils::Abs(Range::ConstantMax(range).ConstantValue()); |
2502 return Utils::Maximum(abs_min, abs_max); | 2415 return Utils::Maximum(abs_min, abs_max); |
2503 } | 2416 } |
2504 | 2417 |
2505 | |
2506 // Return the minimum absolute value included in range. | 2418 // Return the minimum absolute value included in range. |
2507 int64_t Range::ConstantAbsMin(const Range* range) { | 2419 int64_t Range::ConstantAbsMin(const Range* range) { |
2508 if (range == NULL) { | 2420 if (range == NULL) { |
2509 return 0; | 2421 return 0; |
2510 } | 2422 } |
2511 const int64_t abs_min = Utils::Abs(Range::ConstantMin(range).ConstantValue()); | 2423 const int64_t abs_min = Utils::Abs(Range::ConstantMin(range).ConstantValue()); |
2512 const int64_t abs_max = Utils::Abs(Range::ConstantMax(range).ConstantValue()); | 2424 const int64_t abs_max = Utils::Abs(Range::ConstantMax(range).ConstantValue()); |
2513 return Utils::Minimum(abs_min, abs_max); | 2425 return Utils::Minimum(abs_min, abs_max); |
2514 } | 2426 } |
2515 | 2427 |
2516 | |
2517 void Range::BinaryOp(const Token::Kind op, | 2428 void Range::BinaryOp(const Token::Kind op, |
2518 const Range* left_range, | 2429 const Range* left_range, |
2519 const Range* right_range, | 2430 const Range* right_range, |
2520 Definition* left_defn, | 2431 Definition* left_defn, |
2521 Range* result) { | 2432 Range* result) { |
2522 ASSERT(left_range != NULL); | 2433 ASSERT(left_range != NULL); |
2523 ASSERT(right_range != NULL); | 2434 ASSERT(right_range != NULL); |
2524 | 2435 |
2525 // Both left and right ranges are finite. | 2436 // Both left and right ranges are finite. |
2526 ASSERT(left_range->IsFinite()); | 2437 ASSERT(left_range->IsFinite()); |
(...skipping 37 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
2564 *result = Range(RangeBoundary::NegativeInfinity(), | 2475 *result = Range(RangeBoundary::NegativeInfinity(), |
2565 RangeBoundary::PositiveInfinity()); | 2476 RangeBoundary::PositiveInfinity()); |
2566 return; | 2477 return; |
2567 } | 2478 } |
2568 | 2479 |
2569 ASSERT(!min.IsUnknown() && !max.IsUnknown()); | 2480 ASSERT(!min.IsUnknown() && !max.IsUnknown()); |
2570 | 2481 |
2571 *result = Range(min, max); | 2482 *result = Range(min, max); |
2572 } | 2483 } |
2573 | 2484 |
2574 | |
2575 void Definition::set_range(const Range& range) { | 2485 void Definition::set_range(const Range& range) { |
2576 if (range_ == NULL) { | 2486 if (range_ == NULL) { |
2577 range_ = new Range(); | 2487 range_ = new Range(); |
2578 } | 2488 } |
2579 *range_ = range; | 2489 *range_ = range; |
2580 } | 2490 } |
2581 | 2491 |
2582 | |
2583 void Definition::InferRange(RangeAnalysis* analysis, Range* range) { | 2492 void Definition::InferRange(RangeAnalysis* analysis, Range* range) { |
2584 if (Type()->ToCid() == kSmiCid) { | 2493 if (Type()->ToCid() == kSmiCid) { |
2585 *range = Range::Full(RangeBoundary::kRangeBoundarySmi); | 2494 *range = Range::Full(RangeBoundary::kRangeBoundarySmi); |
2586 } else if (IsMintDefinition()) { | 2495 } else if (IsMintDefinition()) { |
2587 *range = Range::Full(RangeBoundary::kRangeBoundaryInt64); | 2496 *range = Range::Full(RangeBoundary::kRangeBoundaryInt64); |
2588 } else if (IsInt32Definition()) { | 2497 } else if (IsInt32Definition()) { |
2589 *range = Range::Full(RangeBoundary::kRangeBoundaryInt32); | 2498 *range = Range::Full(RangeBoundary::kRangeBoundaryInt32); |
2590 } else if (Type()->IsInt()) { | 2499 } else if (Type()->IsInt()) { |
2591 *range = Range::Full(RangeBoundary::kRangeBoundaryInt64); | 2500 *range = Range::Full(RangeBoundary::kRangeBoundaryInt64); |
2592 } else { | 2501 } else { |
2593 // Only Smi and Mint supported. | 2502 // Only Smi and Mint supported. |
2594 UNREACHABLE(); | 2503 UNREACHABLE(); |
2595 } | 2504 } |
2596 } | 2505 } |
2597 | 2506 |
2598 | |
2599 static bool DependsOnSymbol(const RangeBoundary& a, Definition* symbol) { | 2507 static bool DependsOnSymbol(const RangeBoundary& a, Definition* symbol) { |
2600 return a.IsSymbol() && (UnwrapConstraint(a.symbol()) == symbol); | 2508 return a.IsSymbol() && (UnwrapConstraint(a.symbol()) == symbol); |
2601 } | 2509 } |
2602 | 2510 |
2603 | |
2604 // Given the range and definition update the range so that | 2511 // Given the range and definition update the range so that |
2605 // it covers both original range and definitions range. | 2512 // it covers both original range and definitions range. |
2606 // | 2513 // |
2607 // The following should also hold: | 2514 // The following should also hold: |
2608 // | 2515 // |
2609 // [_|_, _|_] U a = a U [_|_, _|_] = a | 2516 // [_|_, _|_] U a = a U [_|_, _|_] = a |
2610 // | 2517 // |
2611 static void Join(Range* range, | 2518 static void Join(Range* range, |
2612 Definition* defn, | 2519 Definition* defn, |
2613 const Range* defn_range, | 2520 const Range* defn_range, |
(...skipping 37 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
2651 // The range is fully above defn's range. Keep the maximum and | 2558 // The range is fully above defn's range. Keep the maximum and |
2652 // expand the minimum. | 2559 // expand the minimum. |
2653 range->set_min(other.min()); | 2560 range->set_min(other.min()); |
2654 } else { | 2561 } else { |
2655 // Can't compare ranges as whole. Join minimum and maximum separately. | 2562 // Can't compare ranges as whole. Join minimum and maximum separately. |
2656 *range = Range(RangeBoundary::JoinMin(range->min(), other.min(), size), | 2563 *range = Range(RangeBoundary::JoinMin(range->min(), other.min(), size), |
2657 RangeBoundary::JoinMax(range->max(), other.max(), size)); | 2564 RangeBoundary::JoinMax(range->max(), other.max(), size)); |
2658 } | 2565 } |
2659 } | 2566 } |
2660 | 2567 |
2661 | |
2662 // A definition dominates a phi if its block dominates the phi's block | 2568 // A definition dominates a phi if its block dominates the phi's block |
2663 // and the two blocks are different. | 2569 // and the two blocks are different. |
2664 static bool DominatesPhi(BlockEntryInstr* a, BlockEntryInstr* phi_block) { | 2570 static bool DominatesPhi(BlockEntryInstr* a, BlockEntryInstr* phi_block) { |
2665 return a->Dominates(phi_block) && (a != phi_block); | 2571 return a->Dominates(phi_block) && (a != phi_block); |
2666 } | 2572 } |
2667 | 2573 |
2668 | |
2669 // When assigning range to a phi we must take care to avoid self-reference | 2574 // When assigning range to a phi we must take care to avoid self-reference |
2670 // cycles when phi's range depends on the phi itself. | 2575 // cycles when phi's range depends on the phi itself. |
2671 // To prevent such cases we impose additional restriction on symbols that | 2576 // To prevent such cases we impose additional restriction on symbols that |
2672 // can be used as boundaries for phi's range: they must dominate | 2577 // can be used as boundaries for phi's range: they must dominate |
2673 // phi's definition. | 2578 // phi's definition. |
2674 static RangeBoundary EnsureAcyclicSymbol(BlockEntryInstr* phi_block, | 2579 static RangeBoundary EnsureAcyclicSymbol(BlockEntryInstr* phi_block, |
2675 const RangeBoundary& a, | 2580 const RangeBoundary& a, |
2676 const RangeBoundary& limit) { | 2581 const RangeBoundary& limit) { |
2677 if (!a.IsSymbol() || DominatesPhi(a.symbol()->GetBlock(), phi_block)) { | 2582 if (!a.IsSymbol() || DominatesPhi(a.symbol()->GetBlock(), phi_block)) { |
2678 return a; | 2583 return a; |
2679 } | 2584 } |
2680 | 2585 |
2681 // Symbol does not dominate phi. Try unwrapping constraint and check again. | 2586 // Symbol does not dominate phi. Try unwrapping constraint and check again. |
2682 Definition* unwrapped = UnwrapConstraint(a.symbol()); | 2587 Definition* unwrapped = UnwrapConstraint(a.symbol()); |
2683 if ((unwrapped != a.symbol()) && | 2588 if ((unwrapped != a.symbol()) && |
2684 DominatesPhi(unwrapped->GetBlock(), phi_block)) { | 2589 DominatesPhi(unwrapped->GetBlock(), phi_block)) { |
2685 return RangeBoundary::FromDefinition(unwrapped, a.offset()); | 2590 return RangeBoundary::FromDefinition(unwrapped, a.offset()); |
2686 } | 2591 } |
2687 | 2592 |
2688 return limit; | 2593 return limit; |
2689 } | 2594 } |
2690 | 2595 |
2691 | |
2692 static const Range* GetInputRange(RangeAnalysis* analysis, | 2596 static const Range* GetInputRange(RangeAnalysis* analysis, |
2693 RangeBoundary::RangeSize size, | 2597 RangeBoundary::RangeSize size, |
2694 Value* input) { | 2598 Value* input) { |
2695 switch (size) { | 2599 switch (size) { |
2696 case RangeBoundary::kRangeBoundarySmi: | 2600 case RangeBoundary::kRangeBoundarySmi: |
2697 return analysis->GetSmiRange(input); | 2601 return analysis->GetSmiRange(input); |
2698 case RangeBoundary::kRangeBoundaryInt32: | 2602 case RangeBoundary::kRangeBoundaryInt32: |
2699 return input->definition()->range(); | 2603 return input->definition()->range(); |
2700 case RangeBoundary::kRangeBoundaryInt64: | 2604 case RangeBoundary::kRangeBoundaryInt64: |
2701 return analysis->GetIntRange(input); | 2605 return analysis->GetIntRange(input); |
2702 default: | 2606 default: |
2703 UNREACHABLE(); | 2607 UNREACHABLE(); |
2704 return NULL; | 2608 return NULL; |
2705 } | 2609 } |
2706 } | 2610 } |
2707 | 2611 |
2708 | |
2709 void PhiInstr::InferRange(RangeAnalysis* analysis, Range* range) { | 2612 void PhiInstr::InferRange(RangeAnalysis* analysis, Range* range) { |
2710 const RangeBoundary::RangeSize size = RangeSizeForPhi(this); | 2613 const RangeBoundary::RangeSize size = RangeSizeForPhi(this); |
2711 for (intptr_t i = 0; i < InputCount(); i++) { | 2614 for (intptr_t i = 0; i < InputCount(); i++) { |
2712 Value* input = InputAt(i); | 2615 Value* input = InputAt(i); |
2713 Join(range, input->definition(), GetInputRange(analysis, size, input), | 2616 Join(range, input->definition(), GetInputRange(analysis, size, input), |
2714 size); | 2617 size); |
2715 } | 2618 } |
2716 | 2619 |
2717 BlockEntryInstr* phi_block = GetBlock(); | 2620 BlockEntryInstr* phi_block = GetBlock(); |
2718 range->set_min( | 2621 range->set_min( |
2719 EnsureAcyclicSymbol(phi_block, range->min(), RangeBoundary::MinSmi())); | 2622 EnsureAcyclicSymbol(phi_block, range->min(), RangeBoundary::MinSmi())); |
2720 range->set_max( | 2623 range->set_max( |
2721 EnsureAcyclicSymbol(phi_block, range->max(), RangeBoundary::MaxSmi())); | 2624 EnsureAcyclicSymbol(phi_block, range->max(), RangeBoundary::MaxSmi())); |
2722 } | 2625 } |
2723 | 2626 |
2724 | |
2725 void ConstantInstr::InferRange(RangeAnalysis* analysis, Range* range) { | 2627 void ConstantInstr::InferRange(RangeAnalysis* analysis, Range* range) { |
2726 if (value_.IsSmi()) { | 2628 if (value_.IsSmi()) { |
2727 int64_t value = Smi::Cast(value_).Value(); | 2629 int64_t value = Smi::Cast(value_).Value(); |
2728 *range = Range(RangeBoundary::FromConstant(value), | 2630 *range = Range(RangeBoundary::FromConstant(value), |
2729 RangeBoundary::FromConstant(value)); | 2631 RangeBoundary::FromConstant(value)); |
2730 } else if (value_.IsMint()) { | 2632 } else if (value_.IsMint()) { |
2731 int64_t value = Mint::Cast(value_).value(); | 2633 int64_t value = Mint::Cast(value_).value(); |
2732 *range = Range(RangeBoundary::FromConstant(value), | 2634 *range = Range(RangeBoundary::FromConstant(value), |
2733 RangeBoundary::FromConstant(value)); | 2635 RangeBoundary::FromConstant(value)); |
2734 } else { | 2636 } else { |
2735 // Only Smi and Mint supported. | 2637 // Only Smi and Mint supported. |
2736 UNREACHABLE(); | 2638 UNREACHABLE(); |
2737 } | 2639 } |
2738 } | 2640 } |
2739 | 2641 |
2740 | |
2741 void ConstraintInstr::InferRange(RangeAnalysis* analysis, Range* range) { | 2642 void ConstraintInstr::InferRange(RangeAnalysis* analysis, Range* range) { |
2742 const Range* value_range = analysis->GetSmiRange(value()); | 2643 const Range* value_range = analysis->GetSmiRange(value()); |
2743 if (Range::IsUnknown(value_range)) { | 2644 if (Range::IsUnknown(value_range)) { |
2744 return; | 2645 return; |
2745 } | 2646 } |
2746 | 2647 |
2747 // TODO(vegorov) check if precision of the analysis can be improved by | 2648 // TODO(vegorov) check if precision of the analysis can be improved by |
2748 // recognizing intersections of the form: | 2649 // recognizing intersections of the form: |
2749 // | 2650 // |
2750 // (..., S+x] ^ [S+x, ...) = [S+x, S+x] | 2651 // (..., S+x] ^ [S+x, ...) = [S+x, S+x] |
2751 // | 2652 // |
2752 Range result = value_range->Intersect(constraint()); | 2653 Range result = value_range->Intersect(constraint()); |
2753 | 2654 |
2754 if (result.IsUnsatisfiable()) { | 2655 if (result.IsUnsatisfiable()) { |
2755 return; | 2656 return; |
2756 } | 2657 } |
2757 | 2658 |
2758 *range = result; | 2659 *range = result; |
2759 } | 2660 } |
2760 | 2661 |
2761 | |
2762 void LoadFieldInstr::InferRange(RangeAnalysis* analysis, Range* range) { | 2662 void LoadFieldInstr::InferRange(RangeAnalysis* analysis, Range* range) { |
2763 switch (recognized_kind()) { | 2663 switch (recognized_kind()) { |
2764 case MethodRecognizer::kObjectArrayLength: | 2664 case MethodRecognizer::kObjectArrayLength: |
2765 case MethodRecognizer::kImmutableArrayLength: | 2665 case MethodRecognizer::kImmutableArrayLength: |
2766 *range = Range(RangeBoundary::FromConstant(0), | 2666 *range = Range(RangeBoundary::FromConstant(0), |
2767 RangeBoundary::FromConstant(Array::kMaxElements)); | 2667 RangeBoundary::FromConstant(Array::kMaxElements)); |
2768 break; | 2668 break; |
2769 | 2669 |
2770 case MethodRecognizer::kTypedDataLength: | 2670 case MethodRecognizer::kTypedDataLength: |
2771 *range = Range(RangeBoundary::FromConstant(0), RangeBoundary::MaxSmi()); | 2671 *range = Range(RangeBoundary::FromConstant(0), RangeBoundary::MaxSmi()); |
2772 break; | 2672 break; |
2773 | 2673 |
2774 case MethodRecognizer::kStringBaseLength: | 2674 case MethodRecognizer::kStringBaseLength: |
2775 *range = Range(RangeBoundary::FromConstant(0), | 2675 *range = Range(RangeBoundary::FromConstant(0), |
2776 RangeBoundary::FromConstant(String::kMaxElements)); | 2676 RangeBoundary::FromConstant(String::kMaxElements)); |
2777 break; | 2677 break; |
2778 | 2678 |
2779 default: | 2679 default: |
2780 Definition::InferRange(analysis, range); | 2680 Definition::InferRange(analysis, range); |
2781 } | 2681 } |
2782 } | 2682 } |
2783 | 2683 |
2784 | |
2785 void LoadIndexedInstr::InferRange(RangeAnalysis* analysis, Range* range) { | 2684 void LoadIndexedInstr::InferRange(RangeAnalysis* analysis, Range* range) { |
2786 switch (class_id()) { | 2685 switch (class_id()) { |
2787 case kTypedDataInt8ArrayCid: | 2686 case kTypedDataInt8ArrayCid: |
2788 *range = Range(RangeBoundary::FromConstant(-128), | 2687 *range = Range(RangeBoundary::FromConstant(-128), |
2789 RangeBoundary::FromConstant(127)); | 2688 RangeBoundary::FromConstant(127)); |
2790 break; | 2689 break; |
2791 case kTypedDataUint8ArrayCid: | 2690 case kTypedDataUint8ArrayCid: |
2792 case kTypedDataUint8ClampedArrayCid: | 2691 case kTypedDataUint8ClampedArrayCid: |
2793 case kExternalTypedDataUint8ArrayCid: | 2692 case kExternalTypedDataUint8ArrayCid: |
2794 case kExternalTypedDataUint8ClampedArrayCid: | 2693 case kExternalTypedDataUint8ClampedArrayCid: |
(...skipping 23 matching lines...) Expand all Loading... |
2818 case kTwoByteStringCid: | 2717 case kTwoByteStringCid: |
2819 *range = Range(RangeBoundary::FromConstant(0), | 2718 *range = Range(RangeBoundary::FromConstant(0), |
2820 RangeBoundary::FromConstant(0xFFFF)); | 2719 RangeBoundary::FromConstant(0xFFFF)); |
2821 break; | 2720 break; |
2822 default: | 2721 default: |
2823 Definition::InferRange(analysis, range); | 2722 Definition::InferRange(analysis, range); |
2824 break; | 2723 break; |
2825 } | 2724 } |
2826 } | 2725 } |
2827 | 2726 |
2828 | |
2829 void LoadCodeUnitsInstr::InferRange(RangeAnalysis* analysis, Range* range) { | 2727 void LoadCodeUnitsInstr::InferRange(RangeAnalysis* analysis, Range* range) { |
2830 ASSERT(RawObject::IsStringClassId(class_id())); | 2728 ASSERT(RawObject::IsStringClassId(class_id())); |
2831 switch (class_id()) { | 2729 switch (class_id()) { |
2832 case kOneByteStringCid: | 2730 case kOneByteStringCid: |
2833 case kTwoByteStringCid: | 2731 case kTwoByteStringCid: |
2834 case kExternalOneByteStringCid: | 2732 case kExternalOneByteStringCid: |
2835 case kExternalTwoByteStringCid: | 2733 case kExternalTwoByteStringCid: |
2836 *range = Range(RangeBoundary::FromConstant(0), | 2734 *range = Range(RangeBoundary::FromConstant(0), |
2837 RangeBoundary::FromConstant(kMaxUint32)); | 2735 RangeBoundary::FromConstant(kMaxUint32)); |
2838 break; | 2736 break; |
2839 default: | 2737 default: |
2840 UNREACHABLE(); | 2738 UNREACHABLE(); |
2841 break; | 2739 break; |
2842 } | 2740 } |
2843 } | 2741 } |
2844 | 2742 |
2845 | |
2846 void IfThenElseInstr::InferRange(RangeAnalysis* analysis, Range* range) { | 2743 void IfThenElseInstr::InferRange(RangeAnalysis* analysis, Range* range) { |
2847 const intptr_t min = Utils::Minimum(if_true_, if_false_); | 2744 const intptr_t min = Utils::Minimum(if_true_, if_false_); |
2848 const intptr_t max = Utils::Maximum(if_true_, if_false_); | 2745 const intptr_t max = Utils::Maximum(if_true_, if_false_); |
2849 *range = | 2746 *range = |
2850 Range(RangeBoundary::FromConstant(min), RangeBoundary::FromConstant(max)); | 2747 Range(RangeBoundary::FromConstant(min), RangeBoundary::FromConstant(max)); |
2851 } | 2748 } |
2852 | 2749 |
2853 | |
2854 static RangeBoundary::RangeSize RepresentationToRangeSize(Representation r) { | 2750 static RangeBoundary::RangeSize RepresentationToRangeSize(Representation r) { |
2855 switch (r) { | 2751 switch (r) { |
2856 case kTagged: | 2752 case kTagged: |
2857 return RangeBoundary::kRangeBoundarySmi; | 2753 return RangeBoundary::kRangeBoundarySmi; |
2858 case kUnboxedInt32: | 2754 case kUnboxedInt32: |
2859 return RangeBoundary::kRangeBoundaryInt32; | 2755 return RangeBoundary::kRangeBoundaryInt32; |
2860 case kUnboxedMint: | 2756 case kUnboxedMint: |
2861 return RangeBoundary::kRangeBoundaryInt64; | 2757 return RangeBoundary::kRangeBoundaryInt64; |
2862 default: | 2758 default: |
2863 UNREACHABLE(); | 2759 UNREACHABLE(); |
2864 return RangeBoundary::kRangeBoundarySmi; | 2760 return RangeBoundary::kRangeBoundarySmi; |
2865 } | 2761 } |
2866 } | 2762 } |
2867 | 2763 |
2868 | |
2869 void BinaryIntegerOpInstr::InferRangeHelper(const Range* left_range, | 2764 void BinaryIntegerOpInstr::InferRangeHelper(const Range* left_range, |
2870 const Range* right_range, | 2765 const Range* right_range, |
2871 Range* range) { | 2766 Range* range) { |
2872 // TODO(vegorov): canonicalize BinaryIntegerOp to always have constant on the | 2767 // TODO(vegorov): canonicalize BinaryIntegerOp to always have constant on the |
2873 // right and a non-constant on the left. | 2768 // right and a non-constant on the left. |
2874 if (Range::IsUnknown(left_range) || Range::IsUnknown(right_range)) { | 2769 if (Range::IsUnknown(left_range) || Range::IsUnknown(right_range)) { |
2875 return; | 2770 return; |
2876 } | 2771 } |
2877 | 2772 |
2878 Range::BinaryOp(op_kind(), left_range, right_range, left()->definition(), | 2773 Range::BinaryOp(op_kind(), left_range, right_range, left()->definition(), |
2879 range); | 2774 range); |
2880 ASSERT(!Range::IsUnknown(range)); | 2775 ASSERT(!Range::IsUnknown(range)); |
2881 | 2776 |
2882 const RangeBoundary::RangeSize range_size = | 2777 const RangeBoundary::RangeSize range_size = |
2883 RepresentationToRangeSize(representation()); | 2778 RepresentationToRangeSize(representation()); |
2884 | 2779 |
2885 // Calculate overflowed status before clamping if operation is | 2780 // Calculate overflowed status before clamping if operation is |
2886 // not truncating. | 2781 // not truncating. |
2887 if (!is_truncating()) { | 2782 if (!is_truncating()) { |
2888 set_can_overflow(!range->Fits(range_size)); | 2783 set_can_overflow(!range->Fits(range_size)); |
2889 } | 2784 } |
2890 | 2785 |
2891 range->Clamp(range_size); | 2786 range->Clamp(range_size); |
2892 } | 2787 } |
2893 | 2788 |
2894 | |
2895 static void CacheRange(Range** slot, | 2789 static void CacheRange(Range** slot, |
2896 const Range* range, | 2790 const Range* range, |
2897 RangeBoundary::RangeSize size) { | 2791 RangeBoundary::RangeSize size) { |
2898 if (range != NULL) { | 2792 if (range != NULL) { |
2899 if (*slot == NULL) { | 2793 if (*slot == NULL) { |
2900 *slot = new Range(); | 2794 *slot = new Range(); |
2901 } | 2795 } |
2902 **slot = *range; | 2796 **slot = *range; |
2903 | 2797 |
2904 // Eliminate any symbolic dependencies from the range information. | 2798 // Eliminate any symbolic dependencies from the range information. |
2905 (*slot)->ClampToConstant(size); | 2799 (*slot)->ClampToConstant(size); |
2906 } else if (*slot != NULL) { | 2800 } else if (*slot != NULL) { |
2907 **slot = Range(); // Clear cached range information. | 2801 **slot = Range(); // Clear cached range information. |
2908 } | 2802 } |
2909 } | 2803 } |
2910 | 2804 |
2911 | |
2912 void BinarySmiOpInstr::InferRange(RangeAnalysis* analysis, Range* range) { | 2805 void BinarySmiOpInstr::InferRange(RangeAnalysis* analysis, Range* range) { |
2913 const Range* right_smi_range = analysis->GetSmiRange(right()); | 2806 const Range* right_smi_range = analysis->GetSmiRange(right()); |
2914 // TODO(vegorov) completely remove this once GetSmiRange is eliminated. | 2807 // TODO(vegorov) completely remove this once GetSmiRange is eliminated. |
2915 if (op_kind() == Token::kSHR || op_kind() == Token::kSHL || | 2808 if (op_kind() == Token::kSHR || op_kind() == Token::kSHL || |
2916 op_kind() == Token::kMOD || op_kind() == Token::kTRUNCDIV) { | 2809 op_kind() == Token::kMOD || op_kind() == Token::kTRUNCDIV) { |
2917 CacheRange(&right_range_, right_smi_range, | 2810 CacheRange(&right_range_, right_smi_range, |
2918 RangeBoundary::kRangeBoundarySmi); | 2811 RangeBoundary::kRangeBoundarySmi); |
2919 } | 2812 } |
2920 InferRangeHelper(analysis->GetSmiRange(left()), right_smi_range, range); | 2813 InferRangeHelper(analysis->GetSmiRange(left()), right_smi_range, range); |
2921 } | 2814 } |
2922 | 2815 |
2923 | |
2924 void BinaryInt32OpInstr::InferRange(RangeAnalysis* analysis, Range* range) { | 2816 void BinaryInt32OpInstr::InferRange(RangeAnalysis* analysis, Range* range) { |
2925 InferRangeHelper(analysis->GetSmiRange(left()), | 2817 InferRangeHelper(analysis->GetSmiRange(left()), |
2926 analysis->GetSmiRange(right()), range); | 2818 analysis->GetSmiRange(right()), range); |
2927 } | 2819 } |
2928 | 2820 |
2929 | |
2930 void BinaryMintOpInstr::InferRange(RangeAnalysis* analysis, Range* range) { | 2821 void BinaryMintOpInstr::InferRange(RangeAnalysis* analysis, Range* range) { |
2931 InferRangeHelper(left()->definition()->range(), | 2822 InferRangeHelper(left()->definition()->range(), |
2932 right()->definition()->range(), range); | 2823 right()->definition()->range(), range); |
2933 } | 2824 } |
2934 | 2825 |
2935 | |
2936 void ShiftMintOpInstr::InferRange(RangeAnalysis* analysis, Range* range) { | 2826 void ShiftMintOpInstr::InferRange(RangeAnalysis* analysis, Range* range) { |
2937 CacheRange(&shift_range_, right()->definition()->range(), | 2827 CacheRange(&shift_range_, right()->definition()->range(), |
2938 RangeBoundary::kRangeBoundaryInt64); | 2828 RangeBoundary::kRangeBoundaryInt64); |
2939 InferRangeHelper(left()->definition()->range(), | 2829 InferRangeHelper(left()->definition()->range(), |
2940 right()->definition()->range(), range); | 2830 right()->definition()->range(), range); |
2941 } | 2831 } |
2942 | 2832 |
2943 | |
2944 void BoxIntegerInstr::InferRange(RangeAnalysis* analysis, Range* range) { | 2833 void BoxIntegerInstr::InferRange(RangeAnalysis* analysis, Range* range) { |
2945 const Range* value_range = value()->definition()->range(); | 2834 const Range* value_range = value()->definition()->range(); |
2946 if (!Range::IsUnknown(value_range)) { | 2835 if (!Range::IsUnknown(value_range)) { |
2947 *range = *value_range; | 2836 *range = *value_range; |
2948 } | 2837 } |
2949 } | 2838 } |
2950 | 2839 |
2951 | |
2952 void UnboxInt32Instr::InferRange(RangeAnalysis* analysis, Range* range) { | 2840 void UnboxInt32Instr::InferRange(RangeAnalysis* analysis, Range* range) { |
2953 if (value()->Type()->ToCid() == kSmiCid) { | 2841 if (value()->Type()->ToCid() == kSmiCid) { |
2954 const Range* value_range = analysis->GetSmiRange(value()); | 2842 const Range* value_range = analysis->GetSmiRange(value()); |
2955 if (!Range::IsUnknown(value_range)) { | 2843 if (!Range::IsUnknown(value_range)) { |
2956 *range = *value_range; | 2844 *range = *value_range; |
2957 } | 2845 } |
2958 } else if (RangeAnalysis::IsIntegerDefinition(value()->definition())) { | 2846 } else if (RangeAnalysis::IsIntegerDefinition(value()->definition())) { |
2959 const Range* value_range = analysis->GetIntRange(value()); | 2847 const Range* value_range = analysis->GetIntRange(value()); |
2960 if (!Range::IsUnknown(value_range)) { | 2848 if (!Range::IsUnknown(value_range)) { |
2961 *range = *value_range; | 2849 *range = *value_range; |
2962 } | 2850 } |
2963 } else if (value()->Type()->ToCid() == kSmiCid) { | 2851 } else if (value()->Type()->ToCid() == kSmiCid) { |
2964 *range = Range::Full(RangeBoundary::kRangeBoundarySmi); | 2852 *range = Range::Full(RangeBoundary::kRangeBoundarySmi); |
2965 } else { | 2853 } else { |
2966 *range = Range::Full(RangeBoundary::kRangeBoundaryInt32); | 2854 *range = Range::Full(RangeBoundary::kRangeBoundaryInt32); |
2967 } | 2855 } |
2968 } | 2856 } |
2969 | 2857 |
2970 | |
2971 void UnboxUint32Instr::InferRange(RangeAnalysis* analysis, Range* range) { | 2858 void UnboxUint32Instr::InferRange(RangeAnalysis* analysis, Range* range) { |
2972 const Range* value_range = NULL; | 2859 const Range* value_range = NULL; |
2973 | 2860 |
2974 if (value()->Type()->ToCid() == kSmiCid) { | 2861 if (value()->Type()->ToCid() == kSmiCid) { |
2975 value_range = analysis->GetSmiRange(value()); | 2862 value_range = analysis->GetSmiRange(value()); |
2976 } else if (RangeAnalysis::IsIntegerDefinition(value()->definition())) { | 2863 } else if (RangeAnalysis::IsIntegerDefinition(value()->definition())) { |
2977 value_range = analysis->GetIntRange(value()); | 2864 value_range = analysis->GetIntRange(value()); |
2978 } else { | 2865 } else { |
2979 *range = Range(RangeBoundary::FromConstant(0), | 2866 *range = Range(RangeBoundary::FromConstant(0), |
2980 RangeBoundary::FromConstant(kMaxUint32)); | 2867 RangeBoundary::FromConstant(kMaxUint32)); |
2981 return; | 2868 return; |
2982 } | 2869 } |
2983 | 2870 |
2984 if (!Range::IsUnknown(value_range)) { | 2871 if (!Range::IsUnknown(value_range)) { |
2985 if (value_range->IsPositive()) { | 2872 if (value_range->IsPositive()) { |
2986 *range = *value_range; | 2873 *range = *value_range; |
2987 } else { | 2874 } else { |
2988 *range = Range(RangeBoundary::FromConstant(0), | 2875 *range = Range(RangeBoundary::FromConstant(0), |
2989 RangeBoundary::FromConstant(kMaxUint32)); | 2876 RangeBoundary::FromConstant(kMaxUint32)); |
2990 } | 2877 } |
2991 } | 2878 } |
2992 } | 2879 } |
2993 | 2880 |
2994 | |
2995 void UnboxInt64Instr::InferRange(RangeAnalysis* analysis, Range* range) { | 2881 void UnboxInt64Instr::InferRange(RangeAnalysis* analysis, Range* range) { |
2996 const Range* value_range = value()->definition()->range(); | 2882 const Range* value_range = value()->definition()->range(); |
2997 if (value_range != NULL) { | 2883 if (value_range != NULL) { |
2998 *range = *value_range; | 2884 *range = *value_range; |
2999 } else if (!value()->definition()->IsMintDefinition() && | 2885 } else if (!value()->definition()->IsMintDefinition() && |
3000 (value()->definition()->Type()->ToCid() != kSmiCid)) { | 2886 (value()->definition()->Type()->ToCid() != kSmiCid)) { |
3001 *range = Range::Full(RangeBoundary::kRangeBoundaryInt64); | 2887 *range = Range::Full(RangeBoundary::kRangeBoundaryInt64); |
3002 } | 2888 } |
3003 } | 2889 } |
3004 | 2890 |
3005 | |
3006 void UnboxedIntConverterInstr::InferRange(RangeAnalysis* analysis, | 2891 void UnboxedIntConverterInstr::InferRange(RangeAnalysis* analysis, |
3007 Range* range) { | 2892 Range* range) { |
3008 ASSERT((from() == kUnboxedInt32) || (from() == kUnboxedMint) || | 2893 ASSERT((from() == kUnboxedInt32) || (from() == kUnboxedMint) || |
3009 (from() == kUnboxedUint32)); | 2894 (from() == kUnboxedUint32)); |
3010 ASSERT((to() == kUnboxedInt32) || (to() == kUnboxedMint) || | 2895 ASSERT((to() == kUnboxedInt32) || (to() == kUnboxedMint) || |
3011 (to() == kUnboxedUint32)); | 2896 (to() == kUnboxedUint32)); |
3012 const Range* value_range = value()->definition()->range(); | 2897 const Range* value_range = value()->definition()->range(); |
3013 if (Range::IsUnknown(value_range)) { | 2898 if (Range::IsUnknown(value_range)) { |
3014 return; | 2899 return; |
3015 } | 2900 } |
3016 | 2901 |
3017 if (to() == kUnboxedUint32) { | 2902 if (to() == kUnboxedUint32) { |
3018 // TODO(vegorov): improve range information for unboxing to Uint32. | 2903 // TODO(vegorov): improve range information for unboxing to Uint32. |
3019 *range = | 2904 *range = |
3020 Range(RangeBoundary::FromConstant(0), | 2905 Range(RangeBoundary::FromConstant(0), |
3021 RangeBoundary::FromConstant(static_cast<int64_t>(kMaxUint32))); | 2906 RangeBoundary::FromConstant(static_cast<int64_t>(kMaxUint32))); |
3022 } else { | 2907 } else { |
3023 *range = *value_range; | 2908 *range = *value_range; |
3024 if (to() == kUnboxedInt32) { | 2909 if (to() == kUnboxedInt32) { |
3025 range->Clamp(RangeBoundary::kRangeBoundaryInt32); | 2910 range->Clamp(RangeBoundary::kRangeBoundaryInt32); |
3026 } | 2911 } |
3027 } | 2912 } |
3028 } | 2913 } |
3029 | 2914 |
3030 | |
3031 bool CheckArrayBoundInstr::IsRedundant(const RangeBoundary& length) { | 2915 bool CheckArrayBoundInstr::IsRedundant(const RangeBoundary& length) { |
3032 Range* index_range = index()->definition()->range(); | 2916 Range* index_range = index()->definition()->range(); |
3033 | 2917 |
3034 // Range of the index is unknown can't decide if the check is redundant. | 2918 // Range of the index is unknown can't decide if the check is redundant. |
3035 if (index_range == NULL) { | 2919 if (index_range == NULL) { |
3036 if (!(index()->BindsToConstant() && index()->BoundConstant().IsSmi())) { | 2920 if (!(index()->BindsToConstant() && index()->BoundConstant().IsSmi())) { |
3037 return false; | 2921 return false; |
3038 } | 2922 } |
3039 | 2923 |
3040 Range range; | 2924 Range range; |
(...skipping 33 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
3074 if (DependOnSameSymbol(max, canonical_length)) { | 2958 if (DependOnSameSymbol(max, canonical_length)) { |
3075 return max.offset() < canonical_length.offset(); | 2959 return max.offset() < canonical_length.offset(); |
3076 } | 2960 } |
3077 } while (CanonicalizeMaxBoundary(&max) || | 2961 } while (CanonicalizeMaxBoundary(&max) || |
3078 CanonicalizeMinBoundary(&canonical_length)); | 2962 CanonicalizeMinBoundary(&canonical_length)); |
3079 | 2963 |
3080 // Failed to prove that maximum is bounded with array length. | 2964 // Failed to prove that maximum is bounded with array length. |
3081 return false; | 2965 return false; |
3082 } | 2966 } |
3083 | 2967 |
3084 | |
3085 } // namespace dart | 2968 } // namespace dart |
OLD | NEW |