Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(160)

Side by Side Diff: src/hydrogen-bce.cc

Issue 23444083: Make bounds check elimination iterative instead of recursive. (Closed) Base URL: https://v8.googlecode.com/svn/branches/bleeding_edge
Patch Set: Tweak barn owl ears. Created 7 years, 3 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch | Annotate | Revision Log
« no previous file with comments | « src/hydrogen-bce.h ('k') | no next file » | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
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 300 matching lines...) Expand 10 before | Expand all | Expand 10 after
311 Zone* zone) { 311 Zone* zone) {
312 Lookup(key, key->Hash(), true, ZoneAllocationPolicy(zone))->value = data; 312 Lookup(key, key->Hash(), true, ZoneAllocationPolicy(zone))->value = data;
313 } 313 }
314 314
315 315
316 void BoundsCheckTable::Delete(BoundsCheckKey* key) { 316 void BoundsCheckTable::Delete(BoundsCheckKey* key) {
317 Remove(key, key->Hash()); 317 Remove(key, key->Hash());
318 } 318 }
319 319
320 320
321 class HBoundsCheckEliminationState {
322 public:
323 HBasicBlock* block_;
324 BoundsCheckBbData* bb_data_list_;
325 int index_;
326 };
327
328
321 // Eliminates checks in bb and recursively in the dominated blocks. 329 // Eliminates checks in bb and recursively in the dominated blocks.
322 // Also replace the results of check instructions with the original value, if 330 // Also replace the results of check instructions with the original value, if
323 // the result is used. This is safe now, since we don't do code motion after 331 // the result is used. This is safe now, since we don't do code motion after
324 // this point. It enables better register allocation since the value produced 332 // this point. It enables better register allocation since the value produced
325 // by check instructions is really a copy of the original value. 333 // by check instructions is really a copy of the original value.
326 void HBoundsCheckEliminationPhase::EliminateRedundantBoundsChecks( 334 void HBoundsCheckEliminationPhase::EliminateRedundantBoundsChecks(
335 HBasicBlock* entry) {
336 // Allocate the stack.
337 HBoundsCheckEliminationState* stack =
338 zone()->NewArray<HBoundsCheckEliminationState>(graph()->blocks()->length());
339
340 // Explicitly push the entry block.
341 stack[0].block_ = entry;
342 stack[0].bb_data_list_ = PreProcessBlock(entry);
343 stack[0].index_ = 0;
344 int stack_depth = 1;
345
346 // Implement depth-first traversal with a stack.
347 while (stack_depth > 0) {
348 int current = stack_depth - 1;
349 HBoundsCheckEliminationState* state = &stack[current];
350 const ZoneList<HBasicBlock*>* children = state->block_->dominated_blocks();
351
352 if (state->index_ < children->length()) {
353 // Recursively visit children blocks.
354 HBasicBlock* child = children->at(state->index_++);
355 int next = stack_depth++;
356 stack[next].block_ = child;
357 stack[next].bb_data_list_ = PreProcessBlock(child);
358 stack[next].index_ = 0;
359 } else {
360 // Finished with all children; post process the block.
361 PostProcessBlock(state->block_, state->bb_data_list_);
362 stack_depth--;
363 }
364 }
365 }
366
367
368 BoundsCheckBbData* HBoundsCheckEliminationPhase::PreProcessBlock(
327 HBasicBlock* bb) { 369 HBasicBlock* bb) {
328 BoundsCheckBbData* bb_data_list = NULL; 370 BoundsCheckBbData* bb_data_list = NULL;
329 371
330 for (HInstructionIterator it(bb); !it.Done(); it.Advance()) { 372 for (HInstructionIterator it(bb); !it.Done(); it.Advance()) {
331 HInstruction* i = it.Current(); 373 HInstruction* i = it.Current();
332 if (!i->IsBoundsCheck()) continue; 374 if (!i->IsBoundsCheck()) continue;
333 375
334 HBoundsCheck* check = HBoundsCheck::cast(i); 376 HBoundsCheck* check = HBoundsCheck::cast(i);
335 int32_t offset; 377 int32_t offset;
336 BoundsCheckKey* key = 378 BoundsCheckKey* key =
(...skipping 31 matching lines...) Expand 10 before | Expand all | Expand 10 after
368 new_upper_offset, 410 new_upper_offset,
369 bb, 411 bb,
370 data->LowerCheck(), 412 data->LowerCheck(),
371 data->UpperCheck(), 413 data->UpperCheck(),
372 bb_data_list, 414 bb_data_list,
373 data); 415 data);
374 table_.Insert(key, bb_data_list, zone()); 416 table_.Insert(key, bb_data_list, zone());
375 } 417 }
376 } 418 }
377 419
378 for (int i = 0; i < bb->dominated_blocks()->length(); ++i) { 420 return bb_data_list;
379 EliminateRedundantBoundsChecks(bb->dominated_blocks()->at(i)); 421 }
380 }
381 422
382 for (BoundsCheckBbData* data = bb_data_list; 423
383 data != NULL; 424 void HBoundsCheckEliminationPhase::PostProcessBlock(
384 data = data->NextInBasicBlock()) { 425 HBasicBlock* block, BoundsCheckBbData* data) {
426 while (data != NULL) {
385 data->RemoveZeroOperations(); 427 data->RemoveZeroOperations();
386 if (data->FatherInDominatorTree()) { 428 if (data->FatherInDominatorTree()) {
387 table_.Insert(data->Key(), data->FatherInDominatorTree(), zone()); 429 table_.Insert(data->Key(), data->FatherInDominatorTree(), zone());
388 } else { 430 } else {
389 table_.Delete(data->Key()); 431 table_.Delete(data->Key());
390 } 432 }
433 data = data->NextInBasicBlock();
391 } 434 }
392 } 435 }
393 436
394 } } // namespace v8::internal 437 } } // namespace v8::internal
OLDNEW
« no previous file with comments | « src/hydrogen-bce.h ('k') | no next file » | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698