| OLD | NEW |
| 1 // Copyright 2013 the V8 project authors. All rights reserved. | 1 // Copyright 2013 the V8 project authors. All rights reserved. |
| 2 // Redistribution and use in source and binary forms, with or without | 2 // Redistribution and use in source and binary forms, with or without |
| 3 // modification, are permitted provided that the following conditions are | 3 // modification, are permitted provided that the following conditions are |
| 4 // met: | 4 // met: |
| 5 // | 5 // |
| 6 // * Redistributions of source code must retain the above copyright | 6 // * Redistributions of source code must retain the above copyright |
| 7 // notice, this list of conditions and the following disclaimer. | 7 // notice, this list of conditions and the following disclaimer. |
| 8 // * Redistributions in binary form must reproduce the above | 8 // * Redistributions in binary form must reproduce the above |
| 9 // copyright notice, this list of conditions and the following | 9 // copyright notice, this list of conditions and the following |
| 10 // disclaimer in the documentation and/or other materials provided | 10 // disclaimer in the documentation and/or other materials provided |
| (...skipping 84 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 95 private: | 95 private: |
| 96 HBasicBlock* block_; | 96 HBasicBlock* block_; |
| 97 bool is_start_; | 97 bool is_start_; |
| 98 bool is_proper_exit_; | 98 bool is_proper_exit_; |
| 99 bool is_in_loop_; | 99 bool is_in_loop_; |
| 100 bool has_check_; | 100 bool has_check_; |
| 101 InductionVariableLimitUpdate additional_limit_; | 101 InductionVariableLimitUpdate additional_limit_; |
| 102 int current_dominated_block_; | 102 int current_dominated_block_; |
| 103 }; | 103 }; |
| 104 | 104 |
| 105 HGraph* graph() { return graph_; } | 105 HGraph* graph() const { return graph_; } |
| 106 HBasicBlock* loop_header() { return loop_header_; } | 106 Counters* counters() const { return graph()->isolate()->counters(); } |
| 107 Element* at(int index) { return &(elements_.at(index)); } | 107 HBasicBlock* loop_header() const { return loop_header_; } |
| 108 Element* at(HBasicBlock* block) { return at(block->block_id()); } | 108 Element* at(int index) const { return &(elements_.at(index)); } |
| 109 Element* at(HBasicBlock* block) const { return at(block->block_id()); } |
| 109 | 110 |
| 110 void AddCheckAt(HBasicBlock* block) { | 111 void AddCheckAt(HBasicBlock* block) { |
| 111 at(block->block_id())->set_has_check(); | 112 at(block->block_id())->set_has_check(); |
| 112 } | 113 } |
| 113 | 114 |
| 114 /* | 115 /* |
| 115 * Initializes the table for a given loop (identified by its induction | 116 * Initializes the table for a given loop (identified by its induction |
| 116 * variable). | 117 * variable). |
| 117 */ | 118 */ |
| 118 void InitializeLoop(InductionVariableData* data) { | 119 void InitializeLoop(InductionVariableData* data) { |
| (...skipping 132 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 251 if (hoistability == NOT_HOISTABLE || | 252 if (hoistability == NOT_HOISTABLE || |
| 252 (hoistability == OPTIMISTICALLY_HOISTABLE && | 253 (hoistability == OPTIMISTICALLY_HOISTABLE && |
| 253 !graph()->use_optimistic_licm())) { | 254 !graph()->use_optimistic_licm())) { |
| 254 return; | 255 return; |
| 255 } | 256 } |
| 256 | 257 |
| 257 // We will do the hoisting, but we must see if the limit is "limit" or if | 258 // We will do the hoisting, but we must see if the limit is "limit" or if |
| 258 // all checks are done on constants: if all check are done against the same | 259 // all checks are done on constants: if all check are done against the same |
| 259 // constant limit we will use that instead of the induction limit. | 260 // constant limit we will use that instead of the induction limit. |
| 260 bool has_upper_constant_limit = true; | 261 bool has_upper_constant_limit = true; |
| 261 InductionVariableData::InductionVariableCheck* current_check = check; | |
| 262 int32_t upper_constant_limit = | 262 int32_t upper_constant_limit = |
| 263 current_check != NULL && current_check->HasUpperLimit() ? | 263 check != NULL && check->HasUpperLimit() ? check->upper_limit() : 0; |
| 264 current_check->upper_limit() : 0; | 264 for (InductionVariableData::InductionVariableCheck* current_check = check; |
| 265 while (current_check != NULL) { | 265 current_check != NULL; |
| 266 if (check->HasUpperLimit()) { | 266 current_check = current_check->next()) { |
| 267 if (check->upper_limit() != upper_constant_limit) { | 267 has_upper_constant_limit = |
| 268 has_upper_constant_limit = false; | 268 has_upper_constant_limit && |
| 269 } | 269 check->HasUpperLimit() && |
| 270 } else { | 270 check->upper_limit() == upper_constant_limit; |
| 271 has_upper_constant_limit = false; | 271 counters()->bounds_checks_eliminated()->Increment(); |
| 272 } | |
| 273 | |
| 274 current_check->check()->block()->graph()->isolate()->counters()-> | |
| 275 bounds_checks_eliminated()->Increment(); | |
| 276 current_check->check()->set_skip_check(); | 272 current_check->check()->set_skip_check(); |
| 277 current_check = current_check->next(); | |
| 278 } | 273 } |
| 279 | 274 |
| 280 // Choose the appropriate limit. | 275 // Choose the appropriate limit. |
| 281 Zone* zone = graph()->zone(); | 276 Zone* zone = graph()->zone(); |
| 282 HValue* context = graph()->GetInvalidContext(); | 277 HValue* context = graph()->GetInvalidContext(); |
| 283 HValue* limit = data->limit(); | 278 HValue* limit = data->limit(); |
| 284 if (has_upper_constant_limit) { | 279 if (has_upper_constant_limit) { |
| 285 HConstant* new_limit = HConstant::New(zone, context, | 280 HConstant* new_limit = HConstant::New(zone, context, |
| 286 upper_constant_limit); | 281 upper_constant_limit); |
| 287 new_limit->InsertBefore(pre_header->end()); | 282 new_limit->InsertBefore(pre_header->end()); |
| 288 limit = new_limit; | 283 limit = new_limit; |
| 289 } | 284 } |
| 290 | 285 |
| 291 // If necessary, redefine the limit in the preheader. | 286 // If necessary, redefine the limit in the preheader. |
| 292 if (limit->IsInteger32Constant() && | 287 if (limit->IsInteger32Constant() && |
| 293 limit->block() != pre_header && | 288 limit->block() != pre_header && |
| 294 !limit->block()->Dominates(pre_header)) { | 289 !limit->block()->Dominates(pre_header)) { |
| 295 HConstant* new_limit = HConstant::New(zone, context, | 290 HConstant* new_limit = HConstant::New(zone, context, |
| 296 limit->GetInteger32Constant()); | 291 limit->GetInteger32Constant()); |
| 297 new_limit->InsertBefore(pre_header->end()); | 292 new_limit->InsertBefore(pre_header->end()); |
| 298 limit = new_limit; | 293 limit = new_limit; |
| 299 } | 294 } |
| 300 | 295 |
| 301 // Do the hoisting. | 296 // Do the hoisting. |
| 302 HBoundsCheck* hoisted_check = HBoundsCheck::New( | 297 HBoundsCheck* hoisted_check = HBoundsCheck::New( |
| 303 zone, context, limit, check->check()->length()); | 298 zone, context, limit, check->check()->length()); |
| 304 hoisted_check->InsertBefore(pre_header->end()); | 299 hoisted_check->InsertBefore(pre_header->end()); |
| 305 hoisted_check->set_allow_equality(true); | 300 hoisted_check->set_allow_equality(true); |
| 306 hoisted_check->block()->graph()->isolate()->counters()-> | 301 counters()->bounds_checks_hoisted()->Increment(); |
| 307 bounds_checks_hoisted()->Increment(); | |
| 308 } | 302 } |
| 309 | 303 |
| 310 void CollectInductionVariableData(HBasicBlock* bb) { | 304 void CollectInductionVariableData(HBasicBlock* bb) { |
| 311 bool additional_limit = false; | 305 bool additional_limit = false; |
| 312 | 306 |
| 313 for (int i = 0; i < bb->phis()->length(); i++) { | 307 for (int i = 0; i < bb->phis()->length(); i++) { |
| 314 HPhi* phi = bb->phis()->at(i); | 308 HPhi* phi = bb->phis()->at(i); |
| 315 phi->DetectInductionVariable(); | 309 phi->DetectInductionVariable(); |
| 316 } | 310 } |
| 317 | 311 |
| (...skipping 16 matching lines...) Expand all Loading... |
| 334 if (!phi->IsInductionVariable()) continue; | 328 if (!phi->IsInductionVariable()) continue; |
| 335 InductionVariableData* data = phi->induction_variable_data(); | 329 InductionVariableData* data = phi->induction_variable_data(); |
| 336 | 330 |
| 337 // For now ignore loops decrementing the index. | 331 // For now ignore loops decrementing the index. |
| 338 if (data->increment() <= 0) continue; | 332 if (data->increment() <= 0) continue; |
| 339 if (!data->LowerLimitIsNonNegativeConstant()) continue; | 333 if (!data->LowerLimitIsNonNegativeConstant()) continue; |
| 340 | 334 |
| 341 // TODO(mmassi): skip OSR values for check->length(). | 335 // TODO(mmassi): skip OSR values for check->length(). |
| 342 if (check->length() == data->limit() || | 336 if (check->length() == data->limit() || |
| 343 check->length() == data->additional_upper_limit()) { | 337 check->length() == data->additional_upper_limit()) { |
| 344 check->block()->graph()->isolate()->counters()-> | 338 counters()->bounds_checks_eliminated()->Increment(); |
| 345 bounds_checks_eliminated()->Increment(); | |
| 346 check->set_skip_check(); | 339 check->set_skip_check(); |
| 347 continue; | 340 continue; |
| 348 } | 341 } |
| 349 | 342 |
| 350 if (!phi->IsLimitedInductionVariable()) continue; | 343 if (!phi->IsLimitedInductionVariable()) continue; |
| 351 | 344 |
| 352 int32_t limit = data->ComputeUpperLimit(decomposition.and_mask, | 345 int32_t limit = data->ComputeUpperLimit(decomposition.and_mask, |
| 353 decomposition.or_mask); | 346 decomposition.or_mask); |
| 354 phi->induction_variable_data()->AddCheck(check, limit); | 347 phi->induction_variable_data()->AddCheck(check, limit); |
| 355 } | 348 } |
| (...skipping 44 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 400 | 393 |
| 401 void HBoundsCheckHoistingPhase::HoistRedundantBoundsChecks() { | 394 void HBoundsCheckHoistingPhase::HoistRedundantBoundsChecks() { |
| 402 InductionVariableBlocksTable table(graph()); | 395 InductionVariableBlocksTable table(graph()); |
| 403 table.CollectInductionVariableData(graph()->entry_block()); | 396 table.CollectInductionVariableData(graph()->entry_block()); |
| 404 for (int i = 0; i < graph()->blocks()->length(); i++) { | 397 for (int i = 0; i < graph()->blocks()->length(); i++) { |
| 405 table.EliminateRedundantBoundsChecks(graph()->blocks()->at(i)); | 398 table.EliminateRedundantBoundsChecks(graph()->blocks()->at(i)); |
| 406 } | 399 } |
| 407 } | 400 } |
| 408 | 401 |
| 409 } } // namespace v8::internal | 402 } } // namespace v8::internal |
| 410 | |
| OLD | NEW |