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 |