From cd2bc96808241f0f0382fdefdaa33e4cf6bf2d75 Mon Sep 17 00:00:00 2001 From: bmeurer Date: Fri, 23 Jan 2015 01:55:33 -0800 Subject: [PATCH] [turbofan] Move GetCommonDominator to BasicBlock. Also add some unittests for the dominator stuff. R=mstarzinger@chromium.org Review URL: https://codereview.chromium.org/865393004 Cr-Commit-Position: refs/heads/master@{#26241} --- src/compiler/schedule.cc | 23 +++++++++--- src/compiler/schedule.h | 4 ++ src/compiler/scheduler.cc | 22 ++--------- src/compiler/scheduler.h | 1 - test/unittests/compiler/schedule-unittest.cc | 55 ++++++++++++++++++++++++++++ 5 files changed, 81 insertions(+), 24 deletions(-) diff --git a/src/compiler/schedule.cc b/src/compiler/schedule.cc index 0622386..b956261 100644 --- a/src/compiler/schedule.cc +++ b/src/compiler/schedule.cc @@ -18,13 +18,13 @@ BasicBlock::BasicBlock(Zone* zone, Id id) rpo_number_(-1), deferred_(false), dominator_depth_(-1), - dominator_(NULL), - rpo_next_(NULL), - loop_header_(NULL), - loop_end_(NULL), + dominator_(nullptr), + rpo_next_(nullptr), + loop_header_(nullptr), + loop_end_(nullptr), loop_depth_(0), control_(kNone), - control_input_(NULL), + control_input_(nullptr), nodes_(zone), successors_(zone), predecessors_(zone), @@ -82,6 +82,19 @@ void BasicBlock::set_loop_header(BasicBlock* loop_header) { } +// static +BasicBlock* BasicBlock::GetCommonDominator(BasicBlock* b1, BasicBlock* b2) { + while (b1 != b2) { + if (b1->dominator_depth() < b2->dominator_depth()) { + b2 = b2->dominator(); + } else { + b1 = b1->dominator(); + } + } + return b1; +} + + std::ostream& operator<<(std::ostream& os, const BasicBlock::Control& c) { switch (c) { case BasicBlock::kNone: diff --git a/src/compiler/schedule.h b/src/compiler/schedule.h index 15c4812..a142bae 100644 --- a/src/compiler/schedule.h +++ b/src/compiler/schedule.h @@ -163,6 +163,10 @@ class BasicBlock FINAL : public ZoneObject { inline bool IsLoopHeader() const { return loop_end_ != NULL; } bool LoopContains(BasicBlock* block) const; + // Computes the immediate common dominator of {b1} and {b2}. The worst time + // complexity is O(N) where N is the height of the dominator tree. + static BasicBlock* GetCommonDominator(BasicBlock* b1, BasicBlock* b2); + private: int32_t loop_number_; // loop number of the block. int32_t rpo_number_; // special RPO number of the block. diff --git a/src/compiler/scheduler.cc b/src/compiler/scheduler.cc index 59a0140..57696b7 100644 --- a/src/compiler/scheduler.cc +++ b/src/compiler/scheduler.cc @@ -208,20 +208,6 @@ void Scheduler::DecrementUnscheduledUseCount(Node* node, int index, } -BasicBlock* Scheduler::GetCommonDominator(BasicBlock* b1, BasicBlock* b2) { - while (b1 != b2) { - int32_t b1_depth = b1->dominator_depth(); - int32_t b2_depth = b2->dominator_depth(); - if (b1_depth < b2_depth) { - b2 = b2->dominator(); - } else { - b1 = b1->dominator(); - } - } - return b1; -} - - // ----------------------------------------------------------------------------- // Phase 1: Build control-flow graph. @@ -1042,7 +1028,7 @@ void Scheduler::PropagateImmediateDominators(BasicBlock* block) { for (++pred; pred != end; ++pred) { // Don't examine backwards edges. if ((*pred)->dominator_depth() < 0) continue; - dominator = GetCommonDominator(dominator, *pred); + dominator = BasicBlock::GetCommonDominator(dominator, *pred); } block->set_dominator(dominator); block->set_dominator_depth(dominator->dominator_depth() + 1); @@ -1195,7 +1181,7 @@ class ScheduleEarlyNodeVisitor { #if DEBUG bool InsideSameDominatorChain(BasicBlock* b1, BasicBlock* b2) { - BasicBlock* dominator = scheduler_->GetCommonDominator(b1, b2); + BasicBlock* dominator = BasicBlock::GetCommonDominator(b1, b2); return dominator == b1 || dominator == b2; } #endif @@ -1277,7 +1263,7 @@ class ScheduleLateNodeVisitor { // The schedule early block dominates the schedule late block. BasicBlock* min_block = scheduler_->GetData(node)->minimum_block_; - DCHECK_EQ(min_block, scheduler_->GetCommonDominator(block, min_block)); + DCHECK_EQ(min_block, BasicBlock::GetCommonDominator(block, min_block)); Trace("Schedule late of #%d:%s is B%d at loop depth %d, minimum = B%d\n", node->id(), node->op()->mnemonic(), block->id().ToInt(), block->loop_depth(), min_block->id().ToInt()); @@ -1319,7 +1305,7 @@ class ScheduleLateNodeVisitor { BasicBlock* use_block = GetBlockForUse(edge); block = block == NULL ? use_block : use_block == NULL ? block - : scheduler_->GetCommonDominator( + : BasicBlock::GetCommonDominator( block, use_block); } return block; diff --git a/src/compiler/scheduler.h b/src/compiler/scheduler.h index 886b755..b4cea23 100644 --- a/src/compiler/scheduler.h +++ b/src/compiler/scheduler.h @@ -80,7 +80,6 @@ class Scheduler { void IncrementUnscheduledUseCount(Node* node, int index, Node* from); void DecrementUnscheduledUseCount(Node* node, int index, Node* from); - BasicBlock* GetCommonDominator(BasicBlock* b1, BasicBlock* b2); void PropagateImmediateDominators(BasicBlock* block); // Phase 1: Build control-flow graph. diff --git a/test/unittests/compiler/schedule-unittest.cc b/test/unittests/compiler/schedule-unittest.cc index fc94884..22debd3 100644 --- a/test/unittests/compiler/schedule-unittest.cc +++ b/test/unittests/compiler/schedule-unittest.cc @@ -13,6 +13,61 @@ namespace v8 { namespace internal { namespace compiler { +typedef TestWithZone BasicBlockTest; + + +TEST_F(BasicBlockTest, Constructor) { + int const id = random_number_generator()->NextInt(); + BasicBlock b(zone(), BasicBlock::Id::FromInt(id)); + EXPECT_FALSE(b.deferred()); + EXPECT_GT(0, b.dominator_depth()); + EXPECT_EQ(nullptr, b.dominator()); + EXPECT_EQ(nullptr, b.rpo_next()); + EXPECT_EQ(id, b.id().ToInt()); +} + + +TEST_F(BasicBlockTest, GetCommonDominator1) { + BasicBlock b(zone(), BasicBlock::Id::FromInt(0)); + EXPECT_EQ(&b, BasicBlock::GetCommonDominator(&b, &b)); +} + + +TEST_F(BasicBlockTest, GetCommonDominator2) { + BasicBlock b0(zone(), BasicBlock::Id::FromInt(0)); + BasicBlock b1(zone(), BasicBlock::Id::FromInt(1)); + BasicBlock b2(zone(), BasicBlock::Id::FromInt(2)); + b0.set_dominator_depth(0); + b1.set_dominator(&b0); + b1.set_dominator_depth(1); + b2.set_dominator(&b1); + b2.set_dominator_depth(2); + EXPECT_EQ(&b0, BasicBlock::GetCommonDominator(&b0, &b1)); + EXPECT_EQ(&b0, BasicBlock::GetCommonDominator(&b0, &b2)); + EXPECT_EQ(&b0, BasicBlock::GetCommonDominator(&b1, &b0)); + EXPECT_EQ(&b0, BasicBlock::GetCommonDominator(&b2, &b0)); + EXPECT_EQ(&b1, BasicBlock::GetCommonDominator(&b1, &b2)); + EXPECT_EQ(&b1, BasicBlock::GetCommonDominator(&b2, &b1)); +} + + +TEST_F(BasicBlockTest, GetCommonDominator3) { + BasicBlock b0(zone(), BasicBlock::Id::FromInt(0)); + BasicBlock b1(zone(), BasicBlock::Id::FromInt(1)); + BasicBlock b2(zone(), BasicBlock::Id::FromInt(2)); + BasicBlock b3(zone(), BasicBlock::Id::FromInt(3)); + b0.set_dominator_depth(0); + b1.set_dominator(&b0); + b1.set_dominator_depth(1); + b2.set_dominator(&b0); + b2.set_dominator_depth(1); + b3.set_dominator(&b2); + b3.set_dominator_depth(2); + EXPECT_EQ(&b0, BasicBlock::GetCommonDominator(&b1, &b3)); + EXPECT_EQ(&b0, BasicBlock::GetCommonDominator(&b3, &b1)); +} + + typedef TestWithZone ScheduleTest; -- 2.7.4