Revision: 24802
Author: [email protected]
Date: Wed Oct 22 11:24:55 2014 UTC
Log: [turbofan] Add support for deferred code.
Branch can now have an optional hint, when the condition is
likely true or false, and if such a hint is present the other
basic block will be marked as deferred and placed at the end
of the function.
We currently use this feature for tagging int32/uint32 in
change lowering, and for load/store bounds checks in simplified
lowering.
TEST=cctest,unittests
[email protected]
Review URL: https://codereview.chromium.org/642883003
https://code.google.com/p/v8/source/detail?r=24802
Modified:
/branches/bleeding_edge/src/compiler/change-lowering.cc
/branches/bleeding_edge/src/compiler/code-generator.cc
/branches/bleeding_edge/src/compiler/code-generator.h
/branches/bleeding_edge/src/compiler/common-operator.cc
/branches/bleeding_edge/src/compiler/common-operator.h
/branches/bleeding_edge/src/compiler/graph-visualizer.cc
/branches/bleeding_edge/src/compiler/instruction-selector.cc
/branches/bleeding_edge/src/compiler/instruction.cc
/branches/bleeding_edge/src/compiler/instruction.h
/branches/bleeding_edge/src/compiler/operator-properties-inl.h
/branches/bleeding_edge/src/compiler/schedule.cc
/branches/bleeding_edge/src/compiler/schedule.h
/branches/bleeding_edge/src/compiler/scheduler.cc
/branches/bleeding_edge/src/compiler/simplified-lowering.cc
/branches/bleeding_edge/test/cctest/compiler/test-scheduler.cc
/branches/bleeding_edge/test/unittests/compiler/common-operator-unittest.cc
=======================================
--- /branches/bleeding_edge/src/compiler/change-lowering.cc Wed Oct 1
11:08:37 2014 UTC
+++ /branches/bleeding_edge/src/compiler/change-lowering.cc Wed Oct 22
11:24:55 2014 UTC
@@ -142,7 +142,8 @@
Node* add = graph()->NewNode(machine()->Int32AddWithOverflow(), val,
val);
Node* ovf = graph()->NewNode(common()->Projection(1), add);
- Node* branch = graph()->NewNode(common()->Branch(), ovf, control);
+ Node* branch =
+ graph()->NewNode(common()->Branch(BranchHint::kTrue), ovf, control);
Node* if_true = graph()->NewNode(common()->IfTrue(), branch);
Node* heap_number = AllocateHeapNumberWithValue(
@@ -215,7 +216,8 @@
Node* cmp = graph()->NewNode(machine()->Uint32LessThanOrEqual(), val,
SmiMaxValueConstant());
- Node* branch = graph()->NewNode(common()->Branch(), cmp, control);
+ Node* branch =
+ graph()->NewNode(common()->Branch(BranchHint::kTrue), cmp, control);
Node* if_true = graph()->NewNode(common()->IfTrue(), branch);
Node* smi = graph()->NewNode(
=======================================
--- /branches/bleeding_edge/src/compiler/code-generator.cc Tue Oct 21
06:59:50 2014 UTC
+++ /branches/bleeding_edge/src/compiler/code-generator.cc Wed Oct 22
11:24:55 2014 UTC
@@ -44,10 +44,20 @@
info->set_prologue_offset(masm()->pc_offset());
AssemblePrologue();
- // Assemble all instructions.
- for (InstructionSequence::const_iterator i = code()->begin();
- i != code()->end(); ++i) {
- AssembleInstruction(*i);
+ // Assemble all non-deferred instructions.
+ for (auto const block : code()->instruction_blocks()) {
+ if (block->IsDeferred()) continue;
+ for (int i = block->code_start(); i < block->code_end(); ++i) {
+ AssembleInstruction(code()->InstructionAt(i));
+ }
+ }
+
+ // Assemble all deferred instructions.
+ for (auto const block : code()->instruction_blocks()) {
+ if (!block->IsDeferred()) continue;
+ for (int i = block->code_start(); i < block->code_end(); ++i) {
+ AssembleInstruction(code()->InstructionAt(i));
+ }
}
FinishCode(masm());
@@ -81,6 +91,12 @@
return result;
}
+
+
+bool CodeGenerator::IsNextInAssemblyOrder(BasicBlock::RpoNumber block)
const {
+ return code()->InstructionBlockAt(current_block_)->ao_number().IsNext(
+ code()->InstructionBlockAt(block)->ao_number());
+}
void CodeGenerator::RecordSafepoint(PointerMap* pointers, Safepoint::Kind
kind,
=======================================
--- /branches/bleeding_edge/src/compiler/code-generator.h Tue Oct 21
06:59:50 2014 UTC
+++ /branches/bleeding_edge/src/compiler/code-generator.h Wed Oct 22
11:24:55 2014 UTC
@@ -39,9 +39,7 @@
// Checks if {block} will appear directly after {current_block_} when
// assembling code, in which case, a fall-through can be used.
- bool IsNextInAssemblyOrder(BasicBlock::RpoNumber block) const {
- return current_block_.IsNext(block);
- }
+ bool IsNextInAssemblyOrder(BasicBlock::RpoNumber block) const;
// Record a safepoint with the given pointer map.
void RecordSafepoint(PointerMap* pointers, Safepoint::Kind kind,
=======================================
--- /branches/bleeding_edge/src/compiler/common-operator.cc Wed Oct 8
07:32:07 2014 UTC
+++ /branches/bleeding_edge/src/compiler/common-operator.cc Wed Oct 22
11:24:55 2014 UTC
@@ -30,6 +30,26 @@
} // namespace
+std::ostream& operator<<(std::ostream& os, BranchHint hint) {
+ switch (hint) {
+ case BranchHint::kNone:
+ return os << "None";
+ case BranchHint::kTrue:
+ return os << "True";
+ case BranchHint::kFalse:
+ return os << "False";
+ }
+ UNREACHABLE();
+ return os;
+}
+
+
+BranchHint BranchHintOf(const Operator* const op) {
+ DCHECK_EQ(IrOpcode::kBranch, op->opcode());
+ return OpParameter<BranchHint>(op);
+}
+
+
size_t hash_value(OutputFrameStateCombine const& sc) {
return base::hash_combine(sc.kind_, sc.parameter_);
}
@@ -74,7 +94,6 @@
#define SHARED_OP_LIST(V) \
V(Dead, Operator::kFoldable, 0, 0) \
V(End, Operator::kFoldable, 0, 1) \
- V(Branch, Operator::kFoldable, 1, 1) \
V(IfTrue, Operator::kFoldable, 0, 1) \
V(IfFalse, Operator::kFoldable, 0, 1) \
V(Throw, Operator::kFoldable, 1, 1) \
@@ -110,6 +129,12 @@
#undef SHARED
+const Operator* CommonOperatorBuilder::Branch(BranchHint hint) {
+ return new (zone()) Operator1<BranchHint>(
+ IrOpcode::kBranch, Operator::kFoldable, 1, 0, "Branch", hint);
+}
+
+
const Operator* CommonOperatorBuilder::Start(int num_formal_parameters) {
// Outputs are formal parameters, plus context, receiver, and JSFunction.
const int value_output_count = num_formal_parameters + 3;
=======================================
--- /branches/bleeding_edge/src/compiler/common-operator.h Tue Oct 7
13:30:28 2014 UTC
+++ /branches/bleeding_edge/src/compiler/common-operator.h Wed Oct 22
11:24:55 2014 UTC
@@ -23,6 +23,16 @@
class Operator;
+// Prediction hint for branches.
+enum class BranchHint : uint8_t { kNone, kTrue, kFalse };
+
+inline size_t hash_value(BranchHint hint) { return
static_cast<size_t>(hint); }
+
+std::ostream& operator<<(std::ostream&, BranchHint);
+
+BranchHint BranchHintOf(const Operator* const);
+
+
// Flag that describes how to combine the current environment with
// the output of a node to obtain a framestate for lazy bailout.
class OutputFrameStateCombine {
@@ -123,7 +133,7 @@
const Operator* Dead();
const Operator* End();
- const Operator* Branch();
+ const Operator* Branch(BranchHint = BranchHint::kNone);
const Operator* IfTrue();
const Operator* IfFalse();
const Operator* Throw();
=======================================
--- /branches/bleeding_edge/src/compiler/graph-visualizer.cc Mon Oct 20
10:19:15 2014 UTC
+++ /branches/bleeding_edge/src/compiler/graph-visualizer.cc Wed Oct 22
11:24:55 2014 UTC
@@ -562,6 +562,7 @@
BasicBlock* current = (*rpo)[i];
Tag block_tag(this, "block");
PrintBlockProperty("name", current->id());
+ PrintStringProperty("deferred",
current->deferred() ? "true" : "false");
PrintIntProperty("from_bci", -1);
PrintIntProperty("to_bci", -1);
=======================================
--- /branches/bleeding_edge/src/compiler/instruction-selector.cc Tue Oct 21
14:44:50 2014 UTC
+++ /branches/bleeding_edge/src/compiler/instruction-selector.cc Wed Oct 22
11:24:55 2014 UTC
@@ -147,7 +147,7 @@
bool InstructionSelector::IsNextInAssemblyOrder(const BasicBlock* block)
const {
- return current_block_->GetRpoNumber().IsNext(block->GetRpoNumber());
+ return current_block_->GetAoNumber().IsNext(block->GetAoNumber());
}
=======================================
--- /branches/bleeding_edge/src/compiler/instruction.cc Tue Oct 21 06:59:50
2014 UTC
+++ /branches/bleeding_edge/src/compiler/instruction.cc Wed Oct 22 11:24:55
2014 UTC
@@ -336,11 +336,13 @@
BasicBlock::RpoNumber::Invalid(), zone),
phis_(zone),
id_(block->id()),
+ ao_number_(block->GetAoNumber()),
rpo_number_(block->GetRpoNumber()),
loop_header_(GetRpo(block->loop_header())),
loop_end_(GetLoopEndRpo(block)),
code_start_(-1),
- code_end_(-1) {
+ code_end_(-1),
+ deferred_(block->deferred()) {
// Map successors and precessors
size_t index = 0;
for (BasicBlock::Successors::const_iterator it =
block->successors_begin();
@@ -604,7 +606,10 @@
const InstructionBlock* block = code.InstructionBlockAt(rpo);
CHECK(block->rpo_number() == rpo);
- os << "RPO#" << block->rpo_number() << ": B" << block->id();
+ os << "RPO#" << block->rpo_number();
+ os << ": AO#" << block->ao_number();
+ os << ": B" << block->id();
+ if (block->IsDeferred()) os << " (deferred)";
if (block->IsLoopHeader()) {
os << " loop blocks: [" << block->rpo_number() << ", "
<< block->loop_end() << ")";
=======================================
--- /branches/bleeding_edge/src/compiler/instruction.h Tue Oct 21 14:41:54
2014 UTC
+++ /branches/bleeding_edge/src/compiler/instruction.h Wed Oct 22 11:24:55
2014 UTC
@@ -794,8 +794,11 @@
int32_t code_end() const { return code_end_; }
void set_code_end(int32_t end) { code_end_ = end; }
+
+ bool IsDeferred() const { return deferred_; }
BasicBlock::Id id() const { return id_; }
+ BasicBlock::RpoNumber ao_number() const { return ao_number_; }
BasicBlock::RpoNumber rpo_number() const { return rpo_number_; }
BasicBlock::RpoNumber loop_header() const { return loop_header_; }
BasicBlock::RpoNumber loop_end() const {
@@ -822,12 +825,14 @@
Predecessors predecessors_;
PhiInstructions phis_;
BasicBlock::Id id_;
+ BasicBlock::RpoNumber ao_number_; // Assembly order number.
// TODO(dcarney): probably dont't need this.
BasicBlock::RpoNumber rpo_number_;
BasicBlock::RpoNumber loop_header_;
BasicBlock::RpoNumber loop_end_;
- int32_t code_start_; // start index of arch-specific code.
- int32_t code_end_; // end index of arch-specific code.
+ int32_t code_start_; // start index of arch-specific code.
+ int32_t code_end_; // end index of arch-specific code.
+ const bool deferred_; // Block contains deferred code.
};
typedef ZoneDeque<Constant> ConstantDeque;
@@ -853,6 +858,10 @@
int VirtualRegisterCount() const { return next_virtual_register_; }
int node_count() const { return static_cast<int>(node_map_.size()); }
+
+ const InstructionBlocks& instruction_blocks() const {
+ return instruction_blocks_;
+ }
int InstructionBlockCount() const {
return static_cast<int>(instruction_blocks_.size());
=======================================
--- /branches/bleeding_edge/src/compiler/operator-properties-inl.h Tue Oct
14 08:59:27 2014 UTC
+++ /branches/bleeding_edge/src/compiler/operator-properties-inl.h Wed Oct
22 11:24:55 2014 UTC
@@ -123,6 +123,8 @@
#define OPCODE_CASE(x) case IrOpcode::k##x:
CONTROL_OP_LIST(OPCODE_CASE)
#undef OPCODE_CASE
+ // Branch operator is special
+ if (op->opcode() == IrOpcode::kBranch) return 1;
// Control operators are Operator1<int>.
return OpParameter<int>(op);
default:
=======================================
--- /branches/bleeding_edge/src/compiler/schedule.cc Wed Oct 22 09:14:48
2014 UTC
+++ /branches/bleeding_edge/src/compiler/schedule.cc Wed Oct 22 11:24:55
2014 UTC
@@ -13,7 +13,9 @@
namespace compiler {
BasicBlock::BasicBlock(Zone* zone, Id id)
- : rpo_number_(-1),
+ : ao_number_(-1),
+ rpo_number_(-1),
+ deferred_(false),
dominator_(NULL),
loop_header_(NULL),
loop_depth_(0),
@@ -240,6 +242,7 @@
for (BasicBlockVectorIter i = rpo->begin(); i != rpo->end(); ++i) {
BasicBlock* block = *i;
os << "--- BLOCK B" << block->id();
+ if (block->deferred()) os << " (deferred)";
if (block->PredecessorCount() != 0) os << " <- ";
bool comma = false;
for (BasicBlock::Predecessors::iterator j =
block->predecessors_begin();
=======================================
--- /branches/bleeding_edge/src/compiler/schedule.h Mon Oct 20 10:19:15
2014 UTC
+++ /branches/bleeding_edge/src/compiler/schedule.h Wed Oct 22 11:24:55
2014 UTC
@@ -139,6 +139,9 @@
Node* control_input() const { return control_input_; }
void set_control_input(Node* control_input);
+
+ bool deferred() const { return deferred_; }
+ void set_deferred(bool deferred) { deferred_ = deferred; }
BasicBlock* dominator() const { return dominator_; }
void set_dominator(BasicBlock* dominator);
@@ -151,6 +154,10 @@
int32_t loop_end() const { return loop_end_; }
void set_loop_end(int32_t loop_end);
+
+ RpoNumber GetAoNumber() const { return RpoNumber::FromInt(ao_number_); }
+ int32_t ao_number() const { return ao_number_; }
+ void set_ao_number(int32_t ao_number) { ao_number_ = ao_number; }
RpoNumber GetRpoNumber() const { return RpoNumber::FromInt(rpo_number_);
}
int32_t rpo_number() const { return rpo_number_; }
@@ -161,7 +168,9 @@
bool LoopContains(BasicBlock* block) const;
private:
+ int32_t ao_number_; // assembly order number of the block.
int32_t rpo_number_; // special RPO number of the block.
+ bool deferred_; // true if the block contains deferred code.
BasicBlock* dominator_; // Immediate dominator of the block.
BasicBlock* loop_header_; // Pointer to dominating loop header basic
block,
// NULL if none. For loop headers, this
points to
=======================================
--- /branches/bleeding_edge/src/compiler/scheduler.cc Tue Oct 21 16:31:51
2014 UTC
+++ /branches/bleeding_edge/src/compiler/scheduler.cc Wed Oct 22 11:24:55
2014 UTC
@@ -277,6 +277,20 @@
TraceConnect(branch, branch_block, successor_blocks[0]);
TraceConnect(branch, branch_block, successor_blocks[1]);
+
+ // Consider branch hints.
+ // TODO(turbofan): Propagate the deferred flag to all blocks dominated
by
+ // this IfTrue/IfFalse later.
+ switch (BranchHintOf(branch->op())) {
+ case BranchHint::kNone:
+ break;
+ case BranchHint::kTrue:
+ successor_blocks[1]->set_deferred(true);
+ break;
+ case BranchHint::kFalse:
+ successor_blocks[0]->set_deferred(true);
+ break;
+ }
schedule_->AddBranch(branch_block, branch, successor_blocks[0],
successor_blocks[1]);
@@ -1194,6 +1208,18 @@
current->loop_header()->id().ToInt(), current->loop_depth());
}
}
+
+ // Compute the assembly order (non-deferred code first, deferred code
+ // afterwards).
+ int32_t number = 0;
+ for (auto block : *final_order) {
+ if (block->deferred()) continue;
+ block->set_ao_number(number++);
+ }
+ for (auto block : *final_order) {
+ if (!block->deferred()) continue;
+ block->set_ao_number(number++);
+ }
#if DEBUG
if (FLAG_trace_turbo_scheduler) PrintRPO(num_loops, loops, final_order);
=======================================
--- /branches/bleeding_edge/src/compiler/simplified-lowering.cc Mon Oct 20
07:56:50 2014 UTC
+++ /branches/bleeding_edge/src/compiler/simplified-lowering.cc Wed Oct 22
11:24:55 2014 UTC
@@ -1027,7 +1027,8 @@
Node* control = node->InputAt(4);
Node* check = graph()->NewNode(machine()->Uint32LessThan(), key,
length);
- Node* branch = graph()->NewNode(common()->Branch(), check, control);
+ Node* branch =
+ graph()->NewNode(common()->Branch(BranchHint::kTrue), check,
control);
Node* if_true = graph()->NewNode(common()->IfTrue(), branch);
Node* load = graph()->NewNode(op, base, index, effect, if_true);
@@ -1098,7 +1099,8 @@
Node* control = node->InputAt(5);
Node* check = graph()->NewNode(machine()->Uint32LessThan(), key,
length);
- Node* branch = graph()->NewNode(common()->Branch(), check, control);
+ Node* branch =
+ graph()->NewNode(common()->Branch(BranchHint::kTrue), check,
control);
Node* if_true = graph()->NewNode(common()->IfTrue(), branch);
Node* store = graph()->NewNode(op, base, index, value, effect,
if_true);
=======================================
--- /branches/bleeding_edge/test/cctest/compiler/test-scheduler.cc Tue Oct
21 12:38:46 2014 UTC
+++ /branches/bleeding_edge/test/cctest/compiler/test-scheduler.cc Wed Oct
22 11:24:55 2014 UTC
@@ -1831,5 +1831,61 @@
ComputeAndVerifySchedule(24, &graph);
}
+
+
+TEST(BranchHintTrue) {
+ HandleAndZoneScope scope;
+ Graph graph(scope.main_zone());
+ CommonOperatorBuilder common(scope.main_zone());
+
+ Node* start = graph.NewNode(common.Start(1));
+ graph.SetStart(start);
+
+ Node* p0 = graph.NewNode(common.Parameter(0), start);
+ Node* tv = graph.NewNode(common.Int32Constant(6));
+ Node* fv = graph.NewNode(common.Int32Constant(7));
+ Node* br = graph.NewNode(common.Branch(BranchHint::kTrue), p0, start);
+ Node* t = graph.NewNode(common.IfTrue(), br);
+ Node* f = graph.NewNode(common.IfFalse(), br);
+ Node* m = graph.NewNode(common.Merge(2), t, f);
+ Node* phi = graph.NewNode(common.Phi(kMachAnyTagged, 2), tv, fv, m);
+ Node* ret = graph.NewNode(common.Return(), phi, start, start);
+ Node* end = graph.NewNode(common.End(), ret, start);
+
+ graph.SetEnd(end);
+
+ Schedule* schedule = ComputeAndVerifySchedule(13, &graph);
+ // Make sure the false block is marked as deferred.
+ CHECK(!schedule->block(t)->deferred());
+ CHECK(schedule->block(f)->deferred());
+}
+
+
+TEST(BranchHintFalse) {
+ HandleAndZoneScope scope;
+ Graph graph(scope.main_zone());
+ CommonOperatorBuilder common(scope.main_zone());
+
+ Node* start = graph.NewNode(common.Start(1));
+ graph.SetStart(start);
+
+ Node* p0 = graph.NewNode(common.Parameter(0), start);
+ Node* tv = graph.NewNode(common.Int32Constant(6));
+ Node* fv = graph.NewNode(common.Int32Constant(7));
+ Node* br = graph.NewNode(common.Branch(BranchHint::kFalse), p0, start);
+ Node* t = graph.NewNode(common.IfTrue(), br);
+ Node* f = graph.NewNode(common.IfFalse(), br);
+ Node* m = graph.NewNode(common.Merge(2), t, f);
+ Node* phi = graph.NewNode(common.Phi(kMachAnyTagged, 2), tv, fv, m);
+ Node* ret = graph.NewNode(common.Return(), phi, start, start);
+ Node* end = graph.NewNode(common.End(), ret, start);
+
+ graph.SetEnd(end);
+
+ Schedule* schedule = ComputeAndVerifySchedule(13, &graph);
+ // Make sure the true block is marked as deferred.
+ CHECK(schedule->block(t)->deferred());
+ CHECK(!schedule->block(f)->deferred());
+}
#endif
=======================================
---
/branches/bleeding_edge/test/unittests/compiler/common-operator-unittest.cc
Wed Oct 8 07:32:07 2014 UTC
+++
/branches/bleeding_edge/test/unittests/compiler/common-operator-unittest.cc
Wed Oct 22 11:24:55 2014 UTC
@@ -47,7 +47,6 @@
}
SHARED(Dead, Operator::kFoldable, 0, 0, 0, 0, 1),
SHARED(End, Operator::kFoldable, 0, 0, 1, 0, 0),
- SHARED(Branch, Operator::kFoldable, 1, 0, 1, 0, 2),
SHARED(IfTrue, Operator::kFoldable, 0, 0, 1, 0, 1),
SHARED(IfFalse, Operator::kFoldable, 0, 0, 1, 0, 1),
SHARED(Throw, Operator::kFoldable, 1, 0, 1, 0, 1),
@@ -160,6 +159,24 @@
} // namespace
+TEST_F(CommonOperatorTest, Branch) {
+ static const BranchHint kHints[] = {BranchHint::kNone, BranchHint::kTrue,
+ BranchHint::kFalse};
+ TRACED_FOREACH(BranchHint, hint, kHints) {
+ const Operator* const op = common()->Branch(hint);
+ EXPECT_EQ(IrOpcode::kBranch, op->opcode());
+ EXPECT_EQ(Operator::kFoldable, op->properties());
+ EXPECT_EQ(1, OperatorProperties::GetValueInputCount(op));
+ EXPECT_EQ(0, OperatorProperties::GetEffectInputCount(op));
+ EXPECT_EQ(1, OperatorProperties::GetControlInputCount(op));
+ EXPECT_EQ(2, OperatorProperties::GetTotalInputCount(op));
+ EXPECT_EQ(0, OperatorProperties::GetValueOutputCount(op));
+ EXPECT_EQ(0, OperatorProperties::GetEffectOutputCount(op));
+ EXPECT_EQ(2, OperatorProperties::GetControlOutputCount(op));
+ }
+}
+
+
TEST_F(CommonOperatorTest, Float32Constant) {
TRACED_FOREACH(float, value, kFloatValues) {
const Operator* op = common()->Float32Constant(value);
--
--
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.
