Reviewers: titzer,
Description:
Merged r16842 into 3.21 branch.
Make bounds check elimination iterative instead of recursive.
BUG=289706
[email protected]
Please review this at https://codereview.chromium.org/26165003/
SVN Base: https://v8.googlecode.com/svn/branches/3.21
Affected files (+52, -7 lines):
M src/hydrogen-bce.h
M src/hydrogen-bce.cc
M src/version.cc
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();
}
}
Index: src/hydrogen-bce.h
diff --git a/src/hydrogen-bce.h b/src/hydrogen-bce.h
index
d91997bda011775d92a66eb9c2c9acbf581d4491..c55dea7b7a5133b62b0e4fa81f1e4b3fa3022279
100644
--- a/src/hydrogen-bce.h
+++ b/src/hydrogen-bce.h
@@ -60,6 +60,8 @@ class HBoundsCheckEliminationPhase : public HPhase {
private:
void EliminateRedundantBoundsChecks(HBasicBlock* bb);
+ BoundsCheckBbData* PreProcessBlock(HBasicBlock* bb);
+ void PostProcessBlock(HBasicBlock* bb, BoundsCheckBbData* data);
BoundsCheckTable table_;
Index: src/version.cc
diff --git a/src/version.cc b/src/version.cc
index
ce8c40946d8e84c67e951248c534f592b0374318..a65b54f674c7195b03f611f75ec6041b66de0b12
100644
--- a/src/version.cc
+++ b/src/version.cc
@@ -35,7 +35,7 @@
#define MAJOR_VERSION 3
#define MINOR_VERSION 21
#define BUILD_NUMBER 18
-#define PATCH_LEVEL 2
+#define PATCH_LEVEL 3
// Use 1 for candidates and 0 otherwise.
// (Boolean macro values are not supported by all preprocessors.)
#define IS_CANDIDATE_VERSION 0
--
--
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.
