| 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 253 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 264 } | 264 } |
| 265 } | 265 } |
| 266 } else if (current->IsCheckArrayBound()) { | 266 } else if (current->IsCheckArrayBound()) { |
| 267 bounds_checks_.Add(current->AsCheckArrayBound()); | 267 bounds_checks_.Add(current->AsCheckArrayBound()); |
| 268 } | 268 } |
| 269 } | 269 } |
| 270 } | 270 } |
| 271 } | 271 } |
| 272 | 272 |
| 273 | 273 |
| 274 // Returns true if use is dominated by the given instruction. | |
| 275 // Note: uses that occur at instruction itself are not dominated by it. | |
| 276 static bool IsDominatedUse(Instruction* dom, Value* use) { | |
| 277 BlockEntryInstr* dom_block = dom->GetBlock(); | |
| 278 | |
| 279 Instruction* instr = use->instruction(); | |
| 280 | |
| 281 PhiInstr* phi = instr->AsPhi(); | |
| 282 if (phi != NULL) { | |
| 283 return dom_block->Dominates(phi->block()->PredecessorAt(use->use_index())); | |
| 284 } | |
| 285 | |
| 286 BlockEntryInstr* use_block = instr->GetBlock(); | |
| 287 if (use_block == dom_block) { | |
| 288 // Fast path for the case of block entry. | |
| 289 if (dom_block == dom) return true; | |
| 290 | |
| 291 for (Instruction* curr = dom->next(); curr != NULL; curr = curr->next()) { | |
| 292 if (curr == instr) return true; | |
| 293 } | |
| 294 | |
| 295 return false; | |
| 296 } | |
| 297 | |
| 298 return dom_block->Dominates(use_block); | |
| 299 } | |
| 300 | |
| 301 | |
| 302 void RangeAnalysis::RenameDominatedUses(Definition* def, | |
| 303 Instruction* dom, | |
| 304 Definition* other) { | |
| 305 for (Value::Iterator it(def->input_use_list()); !it.Done(); it.Advance()) { | |
| 306 Value* use = it.Current(); | |
| 307 | |
| 308 // Skip dead phis. | |
| 309 PhiInstr* phi = use->instruction()->AsPhi(); | |
| 310 ASSERT((phi == NULL) || phi->is_alive()); | |
| 311 if (IsDominatedUse(dom, use)) { | |
| 312 use->BindTo(other); | |
| 313 } | |
| 314 } | |
| 315 } | |
| 316 | |
| 317 | |
| 318 // For a comparison operation return an operation for the equivalent flipped | 274 // For a comparison operation return an operation for the equivalent flipped |
| 319 // comparison: a (op) b === b (op') a. | 275 // comparison: a (op) b === b (op') a. |
| 320 static Token::Kind FlipComparison(Token::Kind op) { | 276 static Token::Kind FlipComparison(Token::Kind op) { |
| 321 switch (op) { | 277 switch (op) { |
| 322 case Token::kEQ: | 278 case Token::kEQ: |
| 323 return Token::kEQ; | 279 return Token::kEQ; |
| 324 case Token::kNE: | 280 case Token::kNE: |
| 325 return Token::kNE; | 281 return Token::kNE; |
| 326 case Token::kLT: | 282 case Token::kLT: |
| 327 return Token::kGT; | 283 return Token::kGT; |
| (...skipping 55 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 383 if ((constraint->value()->definition() == defn) && | 339 if ((constraint->value()->definition() == defn) && |
| 384 constraint->constraint()->Equals(constraint_range)) { | 340 constraint->constraint()->Equals(constraint_range)) { |
| 385 return NULL; | 341 return NULL; |
| 386 } | 342 } |
| 387 constraint = constraint->next()->AsConstraint(); | 343 constraint = constraint->next()->AsConstraint(); |
| 388 } | 344 } |
| 389 | 345 |
| 390 constraint = new (Z) ConstraintInstr(use->CopyWithType(), constraint_range); | 346 constraint = new (Z) ConstraintInstr(use->CopyWithType(), constraint_range); |
| 391 | 347 |
| 392 flow_graph_->InsertAfter(after, constraint, NULL, FlowGraph::kValue); | 348 flow_graph_->InsertAfter(after, constraint, NULL, FlowGraph::kValue); |
| 393 RenameDominatedUses(defn, constraint, constraint); | 349 FlowGraph::RenameDominatedUses(defn, constraint, constraint); |
| 394 constraints_.Add(constraint); | 350 constraints_.Add(constraint); |
| 395 return constraint; | 351 return constraint; |
| 396 } | 352 } |
| 397 | 353 |
| 398 | 354 |
| 399 bool RangeAnalysis::ConstrainValueAfterBranch(Value* use, Definition* defn) { | 355 bool RangeAnalysis::ConstrainValueAfterBranch(Value* use, Definition* defn) { |
| 400 BranchInstr* branch = use->instruction()->AsBranch(); | 356 BranchInstr* branch = use->instruction()->AsBranch(); |
| 401 RelationalOpInstr* rel_op = branch->comparison()->AsRelationalOp(); | 357 RelationalOpInstr* rel_op = branch->comparison()->AsRelationalOp(); |
| 402 if ((rel_op != NULL) && (rel_op->operation_cid() == kSmiCid)) { | 358 if ((rel_op != NULL) && (rel_op->operation_cid() == kSmiCid)) { |
| 403 // Found comparison of two smis. Constrain defn at true and false | 359 // Found comparison of two smis. Constrain defn at true and false |
| (...skipping 2686 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 3090 } | 3046 } |
| 3091 } while (CanonicalizeMaxBoundary(&max) || | 3047 } while (CanonicalizeMaxBoundary(&max) || |
| 3092 CanonicalizeMinBoundary(&canonical_length)); | 3048 CanonicalizeMinBoundary(&canonical_length)); |
| 3093 | 3049 |
| 3094 // Failed to prove that maximum is bounded with array length. | 3050 // Failed to prove that maximum is bounded with array length. |
| 3095 return false; | 3051 return false; |
| 3096 } | 3052 } |
| 3097 | 3053 |
| 3098 | 3054 |
| 3099 } // namespace dart | 3055 } // namespace dart |
| OLD | NEW |