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

Unified 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 side-by-side diff with in-line comments
Download patch
« no previous file with comments | « src/hydrogen-bce.h ('k') | no next file » | no next file with comments »
Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
Index: src/hydrogen-bce.cc
diff --git a/src/hydrogen-bce.cc b/src/hydrogen-bce.cc
index 7c81ec145cbd4e73dc289259c369ed234395a4d5..869db54a2f496576bd01c3eb9d0cdb6f2d721133 100644
--- a/src/hydrogen-bce.cc
+++ b/src/hydrogen-bce.cc
@@ -318,12 +318,54 @@ void BoundsCheckTable::Delete(BoundsCheckKey* key) {
}
+class HBoundsCheckEliminationState {
+ public:
+ HBasicBlock* block_;
+ BoundsCheckBbData* bb_data_list_;
+ int index_;
+};
+
+
// Eliminates checks in bb and recursively in the dominated blocks.
// Also replace the results of check instructions with the original value, if
// the result is used. This is safe now, since we don't do code motion after
// this point. It enables better register allocation since the value produced
// by check instructions is really a copy of the original value.
void HBoundsCheckEliminationPhase::EliminateRedundantBoundsChecks(
+ HBasicBlock* entry) {
+ // Allocate the stack.
+ HBoundsCheckEliminationState* stack =
+ zone()->NewArray<HBoundsCheckEliminationState>(graph()->blocks()->length());
+
+ // Explicitly push the entry block.
+ stack[0].block_ = entry;
+ stack[0].bb_data_list_ = PreProcessBlock(entry);
+ stack[0].index_ = 0;
+ int stack_depth = 1;
+
+ // Implement depth-first traversal with a stack.
+ while (stack_depth > 0) {
+ int current = stack_depth - 1;
+ HBoundsCheckEliminationState* state = &stack[current];
+ const ZoneList<HBasicBlock*>* children = state->block_->dominated_blocks();
+
+ if (state->index_ < children->length()) {
+ // Recursively visit children blocks.
+ HBasicBlock* child = children->at(state->index_++);
+ int next = stack_depth++;
+ stack[next].block_ = child;
+ stack[next].bb_data_list_ = PreProcessBlock(child);
+ stack[next].index_ = 0;
+ } else {
+ // Finished with all children; post process the block.
+ PostProcessBlock(state->block_, state->bb_data_list_);
+ stack_depth--;
+ }
+ }
+}
+
+
+BoundsCheckBbData* HBoundsCheckEliminationPhase::PreProcessBlock(
HBasicBlock* bb) {
BoundsCheckBbData* bb_data_list = NULL;
@@ -375,19 +417,20 @@ void HBoundsCheckEliminationPhase::EliminateRedundantBoundsChecks(
}
}
- for (int i = 0; i < bb->dominated_blocks()->length(); ++i) {
- EliminateRedundantBoundsChecks(bb->dominated_blocks()->at(i));
- }
+ return bb_data_list;
+}
+
- for (BoundsCheckBbData* data = bb_data_list;
- data != NULL;
- data = data->NextInBasicBlock()) {
+void HBoundsCheckEliminationPhase::PostProcessBlock(
+ HBasicBlock* block, BoundsCheckBbData* data) {
+ while (data != NULL) {
data->RemoveZeroOperations();
if (data->FatherInDominatorTree()) {
table_.Insert(data->Key(), data->FatherInDominatorTree(), zone());
} else {
table_.Delete(data->Key());
}
+ data = data->NextInBasicBlock();
}
}
« 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