Revision: 16842
Author: [email protected]
Date: Thu Sep 19 16:26:14 2013 UTC
Log: Make bounds check elimination iterative instead of recursive.
BUG=289706
[email protected]
Review URL: https://codereview.chromium.org/23444083
http://code.google.com/p/v8/source/detail?r=16842
Modified:
/branches/bleeding_edge/src/hydrogen-bce.cc
/branches/bleeding_edge/src/hydrogen-bce.h
=======================================
--- /branches/bleeding_edge/src/hydrogen-bce.cc Wed Jul 31 16:41:51 2013 UTC
+++ /branches/bleeding_edge/src/hydrogen-bce.cc Thu Sep 19 16:26:14 2013 UTC
@@ -318,12 +318,54 @@
}
+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 @@
}
}
- 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();
}
}
=======================================
--- /branches/bleeding_edge/src/hydrogen-bce.h Mon Jul 8 08:36:28 2013 UTC
+++ /branches/bleeding_edge/src/hydrogen-bce.h Thu Sep 19 16:26:14 2013 UTC
@@ -60,6 +60,8 @@
private:
void EliminateRedundantBoundsChecks(HBasicBlock* bb);
+ BoundsCheckBbData* PreProcessBlock(HBasicBlock* bb);
+ void PostProcessBlock(HBasicBlock* bb, BoundsCheckBbData* data);
BoundsCheckTable table_;
--
--
v8-dev mailing list
[email protected]
http://groups.google.com/group/v8-dev
---
You received this message because you are subscribed to the Google Groups "v8-dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
For more options, visit https://groups.google.com/groups/opt_out.
