Reviewers: jarin,
Description:
Add Schedule::InsertBranch to fuse control flow graphs.
[email protected]
TEST=cctest/test-schedule/TestScheduleInsertBranch
Please review this at https://codereview.chromium.org/675983002/
Base URL: https://v8.googlecode.com/svn/branches/bleeding_edge
Affected files (+78, -9 lines):
M src/compiler/schedule.h
M src/compiler/schedule.cc
M test/cctest/compiler/test-schedule.cc
Index: src/compiler/schedule.cc
diff --git a/src/compiler/schedule.cc b/src/compiler/schedule.cc
index
ede6eaa691cc119ebc8331f2303e249a44a9a469..51400cf04c2d12b71a1b6d1a3126e2da5f69458d
100644
--- a/src/compiler/schedule.cc
+++ b/src/compiler/schedule.cc
@@ -51,7 +51,6 @@ void BasicBlock::AddNode(Node* node) {
nodes_.push_back(node); }
void BasicBlock::set_control(Control control) {
- DCHECK(control_ == BasicBlock::kNone);
control_ = control;
}
@@ -215,12 +214,42 @@ void Schedule::AddThrow(BasicBlock* block, Node*
input) {
}
+void Schedule::InsertBranch(BasicBlock* block, BasicBlock* end, Node*
branch,
+ BasicBlock* tblock, BasicBlock* fblock) {
+ DCHECK(block->control() != BasicBlock::kNone);
+ DCHECK(end->control() == BasicBlock::kNone);
+ end->set_control(block->control());
+ block->set_control(BasicBlock::kBranch);
+ MoveSuccessors(block, end);
+ AddSuccessor(block, tblock);
+ AddSuccessor(block, fblock);
+ if (block->control_input() != NULL) {
+ SetControlInput(end, block->control_input());
+ }
+ SetControlInput(block, branch);
+}
+
+
void Schedule::AddSuccessor(BasicBlock* block, BasicBlock* succ) {
block->AddSuccessor(succ);
succ->AddPredecessor(block);
}
+void Schedule::MoveSuccessors(BasicBlock* from, BasicBlock* to) {
+ for (BasicBlock::Predecessors::iterator i = from->successors_begin();
+ i != from->successors_end(); ++i) {
+ BasicBlock* succ = *i;
+ to->AddSuccessor(succ);
+ for (BasicBlock::Predecessors::iterator j = succ->predecessors_begin();
+ j != succ->predecessors_end(); ++j) {
+ if (*j == from) *j = to;
+ }
+ }
+ from->ClearSuccessors();
+}
+
+
void Schedule::SetControlInput(BasicBlock* block, Node* node) {
block->set_control_input(node);
SetBlockForNode(block, node);
Index: src/compiler/schedule.h
diff --git a/src/compiler/schedule.h b/src/compiler/schedule.h
index
5ff554f821e6545f5666e0b3b5b0325f030885b9..fbb00b0ee8d56aa590fb7d403e84e82e09d38fa8
100644
--- a/src/compiler/schedule.h
+++ b/src/compiler/schedule.h
@@ -95,6 +95,7 @@ class BasicBlock FINAL : public ZoneObject {
}
size_t PredecessorCount() const { return predecessors_.size(); }
BasicBlock* PredecessorAt(size_t index) { return predecessors_[index]; }
+ void ClearPredecessors() { predecessors_.clear(); }
void AddPredecessor(BasicBlock* predecessor);
typedef ZoneVector<BasicBlock*> Successors;
@@ -108,6 +109,7 @@ class BasicBlock FINAL : public ZoneObject {
}
size_t SuccessorCount() const { return successors_.size(); }
BasicBlock* SuccessorAt(size_t index) { return successors_[index]; }
+ void ClearSuccessors() { successors_.clear(); }
void AddSuccessor(BasicBlock* successor);
// Nodes in the basic block.
@@ -240,7 +242,13 @@ class Schedule FINAL : public ZoneObject {
// BasicBlock building: add a throw at the end of {block}.
void AddThrow(BasicBlock* block, Node* input);
+ // BasicBlock mutation: insert a branch into the end of {block}.
+ void InsertBranch(BasicBlock* block, BasicBlock* end, Node* branch,
+ BasicBlock* tblock, BasicBlock* fblock);
+
+ // Exposed publicly for testing only.
void AddSuccessor(BasicBlock* block, BasicBlock* succ);
+ void MoveSuccessors(BasicBlock* from, BasicBlock* to);
BasicBlockVector* rpo_order() { return &rpo_order_; }
const BasicBlockVector* rpo_order() const { return &rpo_order_; }
Index: test/cctest/compiler/test-schedule.cc
diff --git a/test/cctest/compiler/test-schedule.cc
b/test/cctest/compiler/test-schedule.cc
index
63e7c2c2b716b0da72afb148053f8c60678e5fe1..da52a66be5129d3f138d4a8d22aebae2e851d8a8
100644
--- a/test/cctest/compiler/test-schedule.cc
+++ b/test/cctest/compiler/test-schedule.cc
@@ -30,12 +30,11 @@ TEST(TestScheduleAllocation) {
TEST(TestScheduleAddNode) {
HandleAndZoneScope scope;
+ Schedule schedule(scope.main_zone());
Graph graph(scope.main_zone());
Node* n0 = graph.NewNode(&dummy_operator);
Node* n1 = graph.NewNode(&dummy_operator);
- Schedule schedule(scope.main_zone());
-
BasicBlock* entry = schedule.start();
schedule.AddNode(entry, n0);
schedule.AddNode(entry, n1);
@@ -51,8 +50,8 @@ TEST(TestScheduleAddNode) {
TEST(TestScheduleAddGoto) {
HandleAndZoneScope scope;
-
Schedule schedule(scope.main_zone());
+
BasicBlock* entry = schedule.start();
BasicBlock* next = schedule.NewBasicBlock();
@@ -71,16 +70,15 @@ TEST(TestScheduleAddGoto) {
TEST(TestScheduleAddBranch) {
HandleAndZoneScope scope;
Schedule schedule(scope.main_zone());
-
- BasicBlock* entry = schedule.start();
- BasicBlock* tblock = schedule.NewBasicBlock();
- BasicBlock* fblock = schedule.NewBasicBlock();
-
Graph graph(scope.main_zone());
CommonOperatorBuilder common(scope.main_zone());
Node* n0 = graph.NewNode(&dummy_operator);
Node* b = graph.NewNode(common.Branch(), n0);
+ BasicBlock* entry = schedule.start();
+ BasicBlock* tblock = schedule.NewBasicBlock();
+ BasicBlock* fblock = schedule.NewBasicBlock();
+
schedule.AddBranch(entry, b, tblock, fblock);
CHECK_EQ(0, static_cast<int>(entry->PredecessorCount()));
@@ -126,6 +124,40 @@ TEST(TestScheduleAddThrow) {
}
+TEST(TestScheduleInsertBranch) {
+ HandleAndZoneScope scope;
+ Schedule schedule(scope.main_zone());
+ Graph graph(scope.main_zone());
+ CommonOperatorBuilder common(scope.main_zone());
+ Node* n0 = graph.NewNode(&dummy_operator);
+ Node* n1 = graph.NewNode(&dummy_operator);
+ Node* b = graph.NewNode(common.Branch(), n1);
+
+ BasicBlock* entry = schedule.start();
+ BasicBlock* tblock = schedule.NewBasicBlock();
+ BasicBlock* fblock = schedule.NewBasicBlock();
+ BasicBlock* merge = schedule.NewBasicBlock();
+ schedule.AddReturn(entry, n0);
+ schedule.AddGoto(tblock, merge);
+ schedule.AddGoto(fblock, merge);
+
+ schedule.InsertBranch(entry, merge, b, tblock, fblock);
+
+ CHECK_EQ(0, static_cast<int>(entry->PredecessorCount()));
+ CHECK_EQ(2, static_cast<int>(entry->SuccessorCount()));
+ CHECK_EQ(tblock, entry->SuccessorAt(0));
+ CHECK_EQ(fblock, entry->SuccessorAt(1));
+
+ CHECK_EQ(2, static_cast<int>(merge->PredecessorCount()));
+ CHECK_EQ(1, static_cast<int>(merge->SuccessorCount()));
+ CHECK_EQ(schedule.end(), merge->SuccessorAt(0));
+
+ CHECK_EQ(1, static_cast<int>(schedule.end()->PredecessorCount()));
+ CHECK_EQ(0, static_cast<int>(schedule.end()->SuccessorCount()));
+ CHECK_EQ(merge, schedule.end()->PredecessorAt(0));
+}
+
+
TEST(BuildMulNodeGraph) {
HandleAndZoneScope scope;
Schedule schedule(scope.main_zone());
--
--
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/d/optout.
