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 12 matching lines...) Expand all Loading... |
23 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY | 23 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY |
24 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT | 24 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |
25 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE | 25 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE |
26 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. | 26 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
27 | 27 |
28 #include "hydrogen-bce.h" | 28 #include "hydrogen-bce.h" |
29 | 29 |
30 namespace v8 { | 30 namespace v8 { |
31 namespace internal { | 31 namespace internal { |
32 | 32 |
| 33 |
33 // We try to "factor up" HBoundsCheck instructions towards the root of the | 34 // We try to "factor up" HBoundsCheck instructions towards the root of the |
34 // dominator tree. | 35 // dominator tree. |
35 // For now we handle checks where the index is like "exp + int32value". | 36 // For now we handle checks where the index is like "exp + int32value". |
36 // If in the dominator tree we check "exp + v1" and later (dominated) | 37 // If in the dominator tree we check "exp + v1" and later (dominated) |
37 // "exp + v2", if v2 <= v1 we can safely remove the second check, and if | 38 // "exp + v2", if v2 <= v1 we can safely remove the second check, and if |
38 // v2 > v1 we can use v2 in the 1st check and again remove the second. | 39 // v2 > v1 we can use v2 in the 1st check and again remove the second. |
39 // To do so we keep a dictionary of all checks where the key if the pair | 40 // To do so we keep a dictionary of all checks where the key if the pair |
40 // "exp, length". | 41 // "exp, length". |
41 // The class BoundsCheckKey represents this key. | 42 // The class BoundsCheckKey represents this key. |
42 class BoundsCheckKey : public ZoneObject { | 43 class BoundsCheckKey : public ZoneObject { |
(...skipping 123 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
166 int32_t new_offset) { | 167 int32_t new_offset) { |
167 ASSERT(new_check->index()->representation().IsSmiOrInteger32()); | 168 ASSERT(new_check->index()->representation().IsSmiOrInteger32()); |
168 bool keep_new_check = false; | 169 bool keep_new_check = false; |
169 | 170 |
170 if (new_offset > upper_offset_) { | 171 if (new_offset > upper_offset_) { |
171 upper_offset_ = new_offset; | 172 upper_offset_ = new_offset; |
172 if (HasSingleCheck()) { | 173 if (HasSingleCheck()) { |
173 keep_new_check = true; | 174 keep_new_check = true; |
174 upper_check_ = new_check; | 175 upper_check_ = new_check; |
175 } else { | 176 } else { |
176 TightenCheck(upper_check_, new_check); | 177 TightenCheck(upper_check_, new_check, new_offset); |
177 UpdateUpperOffsets(upper_check_, upper_offset_); | 178 UpdateUpperOffsets(upper_check_, upper_offset_); |
178 } | 179 } |
179 } else if (new_offset < lower_offset_) { | 180 } else if (new_offset < lower_offset_) { |
180 lower_offset_ = new_offset; | 181 lower_offset_ = new_offset; |
181 if (HasSingleCheck()) { | 182 if (HasSingleCheck()) { |
182 keep_new_check = true; | 183 keep_new_check = true; |
183 lower_check_ = new_check; | 184 lower_check_ = new_check; |
184 } else { | 185 } else { |
185 TightenCheck(lower_check_, new_check); | 186 TightenCheck(lower_check_, new_check, new_offset); |
186 UpdateLowerOffsets(lower_check_, lower_offset_); | 187 UpdateLowerOffsets(lower_check_, lower_offset_); |
187 } | 188 } |
188 } else { | 189 } else { |
189 // Should never have called CoverCheck() in this case. | 190 // Should never have called CoverCheck() in this case. |
190 UNREACHABLE(); | 191 UNREACHABLE(); |
191 } | 192 } |
192 | 193 |
193 if (!keep_new_check) { | 194 if (!keep_new_check) { |
| 195 if (FLAG_trace_bce) { |
| 196 OS::Print("Eliminating check #%d after tightening\n", |
| 197 new_check->id()); |
| 198 } |
194 new_check->block()->graph()->isolate()->counters()-> | 199 new_check->block()->graph()->isolate()->counters()-> |
195 bounds_checks_eliminated()->Increment(); | 200 bounds_checks_eliminated()->Increment(); |
196 new_check->DeleteAndReplaceWith(new_check->ActualValue()); | 201 new_check->DeleteAndReplaceWith(new_check->ActualValue()); |
197 } else { | 202 } else { |
198 HBoundsCheck* first_check = new_check == lower_check_ ? upper_check_ | 203 HBoundsCheck* first_check = new_check == lower_check_ ? upper_check_ |
199 : lower_check_; | 204 : lower_check_; |
| 205 if (FLAG_trace_bce) { |
| 206 OS::Print("Moving second check #%d after first check #%d\n", |
| 207 new_check->id(), first_check->id()); |
| 208 } |
200 // The length is guaranteed to be live at first_check. | 209 // The length is guaranteed to be live at first_check. |
201 ASSERT(new_check->length() == first_check->length()); | 210 ASSERT(new_check->length() == first_check->length()); |
202 HInstruction* old_position = new_check->next(); | 211 HInstruction* old_position = new_check->next(); |
203 new_check->Unlink(); | 212 new_check->Unlink(); |
204 new_check->InsertAfter(first_check); | 213 new_check->InsertAfter(first_check); |
205 MoveIndexIfNecessary(new_check->index(), new_check, old_position); | 214 MoveIndexIfNecessary(new_check->index(), new_check, old_position); |
206 } | 215 } |
207 } | 216 } |
208 | 217 |
209 BoundsCheckBbData(BoundsCheckKey* key, | 218 BoundsCheckBbData(BoundsCheckKey* key, |
(...skipping 58 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
268 HConstant::cast(left_input)->Unlink(); | 277 HConstant::cast(left_input)->Unlink(); |
269 HConstant::cast(left_input)->InsertBefore(index); | 278 HConstant::cast(left_input)->InsertBefore(index); |
270 } | 279 } |
271 if (must_move_right_input) { | 280 if (must_move_right_input) { |
272 HConstant::cast(right_input)->Unlink(); | 281 HConstant::cast(right_input)->Unlink(); |
273 HConstant::cast(right_input)->InsertBefore(index); | 282 HConstant::cast(right_input)->InsertBefore(index); |
274 } | 283 } |
275 } | 284 } |
276 | 285 |
277 void TightenCheck(HBoundsCheck* original_check, | 286 void TightenCheck(HBoundsCheck* original_check, |
278 HBoundsCheck* tighter_check) { | 287 HBoundsCheck* tighter_check, |
| 288 int32_t new_offset) { |
279 ASSERT(original_check->length() == tighter_check->length()); | 289 ASSERT(original_check->length() == tighter_check->length()); |
280 MoveIndexIfNecessary(tighter_check->index(), original_check, tighter_check); | 290 MoveIndexIfNecessary(tighter_check->index(), original_check, tighter_check); |
281 original_check->ReplaceAllUsesWith(original_check->index()); | 291 original_check->ReplaceAllUsesWith(original_check->index()); |
282 original_check->SetOperandAt(0, tighter_check->index()); | 292 original_check->SetOperandAt(0, tighter_check->index()); |
| 293 if (FLAG_trace_bce) { |
| 294 OS::Print("Tightened check #%d with offset %d from #%d\n", |
| 295 original_check->id(), new_offset, tighter_check->id()); |
| 296 } |
283 } | 297 } |
284 | 298 |
285 DISALLOW_COPY_AND_ASSIGN(BoundsCheckBbData); | 299 DISALLOW_COPY_AND_ASSIGN(BoundsCheckBbData); |
286 }; | 300 }; |
287 | 301 |
288 | 302 |
289 static bool BoundsCheckKeyMatch(void* key1, void* key2) { | 303 static bool BoundsCheckKeyMatch(void* key1, void* key2) { |
290 BoundsCheckKey* k1 = static_cast<BoundsCheckKey*>(key1); | 304 BoundsCheckKey* k1 = static_cast<BoundsCheckKey*>(key1); |
291 BoundsCheckKey* k2 = static_cast<BoundsCheckKey*>(key2); | 305 BoundsCheckKey* k2 = static_cast<BoundsCheckKey*>(key2); |
292 return k1->IndexBase() == k2->IndexBase() && k1->Length() == k2->Length(); | 306 return k1->IndexBase() == k2->IndexBase() && k1->Length() == k2->Length(); |
(...skipping 89 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
382 if (data == NULL) { | 396 if (data == NULL) { |
383 bb_data_list = new(zone()) BoundsCheckBbData(key, | 397 bb_data_list = new(zone()) BoundsCheckBbData(key, |
384 offset, | 398 offset, |
385 offset, | 399 offset, |
386 bb, | 400 bb, |
387 check, | 401 check, |
388 check, | 402 check, |
389 bb_data_list, | 403 bb_data_list, |
390 NULL); | 404 NULL); |
391 *data_p = bb_data_list; | 405 *data_p = bb_data_list; |
| 406 if (FLAG_trace_bce) { |
| 407 OS::Print("Fresh bounds check data for block #%d: [%d]\n", |
| 408 bb->block_id(), offset); |
| 409 } |
392 } else if (data->OffsetIsCovered(offset)) { | 410 } else if (data->OffsetIsCovered(offset)) { |
393 bb->graph()->isolate()->counters()-> | 411 bb->graph()->isolate()->counters()-> |
394 bounds_checks_eliminated()->Increment(); | 412 bounds_checks_eliminated()->Increment(); |
| 413 if (FLAG_trace_bce) { |
| 414 OS::Print("Eliminating bounds check #%d, offset %d is covered\n", |
| 415 check->id(), offset); |
| 416 } |
395 check->DeleteAndReplaceWith(check->ActualValue()); | 417 check->DeleteAndReplaceWith(check->ActualValue()); |
396 } else if (data->BasicBlock() == bb) { | 418 } else if (data->BasicBlock() == bb) { |
| 419 // TODO(jkummerow): I think the following logic would be preferable: |
| 420 // if (data->Basicblock() == bb || |
| 421 // graph()->use_optimistic_licm() || |
| 422 // bb->IsLoopSuccessorDominator()) { |
| 423 // data->CoverCheck(check, offset) |
| 424 // } else { |
| 425 // /* add pristine BCBbData like in (data == NULL) case above */ |
| 426 // } |
| 427 // Even better would be: distinguish between read-only dominator-imposed |
| 428 // knowledge and modifiable upper/lower checks. |
| 429 // What happens currently is that the first bounds check in a dominated |
| 430 // block will stay around while any further checks are hoisted out, |
| 431 // which doesn't make sense. Investigate/fix this in a future CL. |
397 data->CoverCheck(check, offset); | 432 data->CoverCheck(check, offset); |
398 } else if (graph()->use_optimistic_licm() || | 433 } else if (graph()->use_optimistic_licm() || |
399 bb->IsLoopSuccessorDominator()) { | 434 bb->IsLoopSuccessorDominator()) { |
400 int32_t new_lower_offset = offset < data->LowerOffset() | 435 int32_t new_lower_offset = offset < data->LowerOffset() |
401 ? offset | 436 ? offset |
402 : data->LowerOffset(); | 437 : data->LowerOffset(); |
403 int32_t new_upper_offset = offset > data->UpperOffset() | 438 int32_t new_upper_offset = offset > data->UpperOffset() |
404 ? offset | 439 ? offset |
405 : data->UpperOffset(); | 440 : data->UpperOffset(); |
406 bb_data_list = new(zone()) BoundsCheckBbData(key, | 441 bb_data_list = new(zone()) BoundsCheckBbData(key, |
407 new_lower_offset, | 442 new_lower_offset, |
408 new_upper_offset, | 443 new_upper_offset, |
409 bb, | 444 bb, |
410 data->LowerCheck(), | 445 data->LowerCheck(), |
411 data->UpperCheck(), | 446 data->UpperCheck(), |
412 bb_data_list, | 447 bb_data_list, |
413 data); | 448 data); |
| 449 if (FLAG_trace_bce) { |
| 450 OS::Print("Updated bounds check data for block #%d: [%d - %d]\n", |
| 451 bb->block_id(), new_lower_offset, new_upper_offset); |
| 452 } |
414 table_.Insert(key, bb_data_list, zone()); | 453 table_.Insert(key, bb_data_list, zone()); |
415 } | 454 } |
416 } | 455 } |
417 | 456 |
418 return bb_data_list; | 457 return bb_data_list; |
419 } | 458 } |
420 | 459 |
421 | 460 |
422 void HBoundsCheckEliminationPhase::PostProcessBlock( | 461 void HBoundsCheckEliminationPhase::PostProcessBlock( |
423 HBasicBlock* block, BoundsCheckBbData* data) { | 462 HBasicBlock* block, BoundsCheckBbData* data) { |
424 while (data != NULL) { | 463 while (data != NULL) { |
425 if (data->FatherInDominatorTree()) { | 464 if (data->FatherInDominatorTree()) { |
426 table_.Insert(data->Key(), data->FatherInDominatorTree(), zone()); | 465 table_.Insert(data->Key(), data->FatherInDominatorTree(), zone()); |
427 } else { | 466 } else { |
428 table_.Delete(data->Key()); | 467 table_.Delete(data->Key()); |
429 } | 468 } |
430 data = data->NextInBasicBlock(); | 469 data = data->NextInBasicBlock(); |
431 } | 470 } |
432 } | 471 } |
433 | 472 |
434 } } // namespace v8::internal | 473 } } // namespace v8::internal |
OLD | NEW |