Reviewers: Benedikt Meurer,
Description:
[turbofan] Match selects in control reducer (configurable).
[email protected]
BUG=
Please review this at https://codereview.chromium.org/1061303002/
Base URL: https://chromium.googlesource.com/v8/v8.git@master
Affected files (+71, -25 lines):
M src/compiler/control-reducer.h
M src/compiler/control-reducer.cc
M src/compiler/node-matchers.h
M src/compiler/pipeline.cc
Index: src/compiler/control-reducer.cc
diff --git a/src/compiler/control-reducer.cc
b/src/compiler/control-reducer.cc
index
08182703b4bac886e4112ae517f17c822c738df4..8501e432556e6c46966319b097e198157f375d71
100644
--- a/src/compiler/control-reducer.cc
+++ b/src/compiler/control-reducer.cc
@@ -56,7 +56,8 @@ class ControlReducerImpl {
common_(common),
state_(jsgraph->graph()->NodeCount(), kUnvisited, zone_),
stack_(zone_),
- revisit_(zone_) {}
+ revisit_(zone_),
+ max_phis_for_select_(0) {}
Zone* zone_;
JSGraph* jsgraph_;
@@ -64,6 +65,7 @@ class ControlReducerImpl {
ZoneVector<VisitState> state_;
ZoneDeque<Node*> stack_;
ZoneDeque<Node*> revisit_;
+ bool max_phis_for_select_;
void Reduce() {
Push(graph()->end());
@@ -536,7 +538,7 @@ class ControlReducerImpl {
if (live == 0) return dead(); // no remaining inputs.
// Gather phis and effect phis to be edited.
- ZoneVector<Node*> phis(zone_);
+ NodeVector phis(zone_);
for (Node* const use : node->uses()) {
if (NodeProperties::IsPhi(use)) phis.push_back(use);
}
@@ -564,25 +566,49 @@ class ControlReducerImpl {
DCHECK_EQ(live, node->InputCount());
- // Check if it's an unused diamond.
- if (live == 2 && phis.empty()) {
+ // Try to remove dead diamonds or introduce selects.
+ if (live == 2 && CheckPhisForSelect(phis)) {
DiamondMatcher matcher(node);
if (matcher.Matched() && matcher.IfProjectionsAreOwned()) {
- // It's a dead diamond, i.e. neither the IfTrue nor the IfFalse
nodes
- // have uses except for the Merge and the Merge has no Phi or
- // EffectPhi uses, so replace the Merge with the control input of
the
- // diamond.
- TRACE(" DeadDiamond: #%d:Branch #%d:IfTrue #%d:IfFalse\n",
- matcher.Branch()->id(), matcher.IfTrue()->id(),
- matcher.IfFalse()->id());
- // TODO(turbofan): replace single-phi diamonds with selects.
- return NodeProperties::GetControlInput(matcher.Branch());
+ // Dead diamond, i.e. neither the IfTrue nor the IfFalse nodes
+ // have uses except for the Merge. Remove the branch if there
+ // are no phis or replace phis with selects.
+ Node* control = NodeProperties::GetControlInput(matcher.Branch());
+ if (phis.size() == 0) {
+ // No phis. Remove the branch altogether.
+ TRACE(" DeadDiamond: #%d:Branch #%d:IfTrue #%d:IfFalse\n",
+ matcher.Branch()->id(), matcher.IfTrue()->id(),
+ matcher.IfFalse()->id());
+ return control;
+ } else {
+ // A small number of phis. Replace with selects.
+ Node* cond = matcher.Branch()->InputAt(0);
+ for (Node* phi : phis) {
+ Node* select = graph()->NewNode(
+ common_->Select(OpParameter<MachineType>(phi),
+ BranchHintOf(matcher.Branch()->op())),
+ cond, matcher.TrueInputOf(phi), matcher.FalseInputOf(phi));
+ TRACE(" MatchSelect: #%d:Branch #%d:IfTrue #%d:IfFalse ->
#%d\n",
+ matcher.Branch()->id(), matcher.IfTrue()->id(),
+ matcher.IfFalse()->id(), select->id());
+ ReplaceNode(phi, select);
+ }
+ return control;
+ }
}
}
return node;
}
+ bool CheckPhisForSelect(const NodeVector& phis) {
+ if (phis.size() > max_phis_for_select_) return false;
+ for (Node* phi : phis) {
+ if (phi->opcode() != IrOpcode::kPhi) return false; // no EffectPhis.
+ }
+ return true;
+ }
+
// Reduce if projections if the branch has a constant input.
Node* ReduceIfProjection(Node* node, Decision decision) {
Node* branch = node->InputAt(0);
@@ -638,8 +664,10 @@ class ControlReducerImpl {
void ControlReducer::ReduceGraph(Zone* zone, JSGraph* jsgraph,
- CommonOperatorBuilder* common) {
+ CommonOperatorBuilder* common,
+ int max_phis_for_select) {
ControlReducerImpl impl(zone, jsgraph, common);
+ impl.max_phis_for_select_ = max_phis_for_select;
impl.Reduce();
}
@@ -651,9 +679,11 @@ void ControlReducer::TrimGraph(Zone* zone, JSGraph*
jsgraph) {
Node* ControlReducer::ReduceMerge(JSGraph* jsgraph,
- CommonOperatorBuilder* common, Node*
node) {
+ CommonOperatorBuilder* common, Node*
node,
+ int max_phis_for_select) {
Zone zone;
ControlReducerImpl impl(&zone, jsgraph, common);
+ impl.max_phis_for_select_ = max_phis_for_select;
return impl.ReduceMerge(node);
}
Index: src/compiler/control-reducer.h
diff --git a/src/compiler/control-reducer.h b/src/compiler/control-reducer.h
index
bcbd80e9165c6fefea45f531693101ed7ac49ada..1e29e01e85a68d29f02c1992ef9b8a9a1d5a8b6f
100644
--- a/src/compiler/control-reducer.h
+++ b/src/compiler/control-reducer.h
@@ -23,14 +23,15 @@ class ControlReducer {
public:
// Perform branch folding and dead code elimination on the graph.
static void ReduceGraph(Zone* zone, JSGraph* graph,
- CommonOperatorBuilder* builder);
+ CommonOperatorBuilder* builder,
+ int max_phis_for_select = 0);
// Trim nodes in the graph that are not reachable from end.
static void TrimGraph(Zone* zone, JSGraph* graph);
// Reduces a single merge node and attached phis.
static Node* ReduceMerge(JSGraph* graph, CommonOperatorBuilder* builder,
- Node* node);
+ Node* node, int max_phis_for_select = 0);
// Testing interface.
static Node* ReducePhiForTesting(JSGraph* graph,
Index: src/compiler/node-matchers.h
diff --git a/src/compiler/node-matchers.h b/src/compiler/node-matchers.h
index
627829f4b56976a99e35a9ed23767995e1e821e9..6beca7c2c898f32ca0b6df06daddc5b31e0f2a23
100644
--- a/src/compiler/node-matchers.h
+++ b/src/compiler/node-matchers.h
@@ -570,6 +570,20 @@ struct DiamondMatcher : public NodeMatcher {
Node* IfFalse() const { return if_false_; }
Node* Merge() const { return node(); }
+ Node* TrueInputOf(Node* phi) const {
+ DCHECK(IrOpcode::IsPhiOpcode(phi->opcode()));
+ DCHECK_EQ(3, phi->InputCount());
+ DCHECK_EQ(Merge(), phi->InputAt(2));
+ return phi->InputAt(if_true_ == Merge()->InputAt(0) ? 0 : 1);
+ }
+
+ Node* FalseInputOf(Node* phi) const {
+ DCHECK(IrOpcode::IsPhiOpcode(phi->opcode()));
+ DCHECK_EQ(3, phi->InputCount());
+ DCHECK_EQ(Merge(), phi->InputAt(2));
+ return phi->InputAt(if_true_ == Merge()->InputAt(0) ? 1 : 0);
+ }
+
private:
Node* branch_;
Node* if_true_;
Index: src/compiler/pipeline.cc
diff --git a/src/compiler/pipeline.cc b/src/compiler/pipeline.cc
index
b1d7fda9a37b3fad741d75ef78a33c995c707ba7..7b1f61f30e8d858bf7882d0edcbc337cebc01aa8
100644
--- a/src/compiler/pipeline.cc
+++ b/src/compiler/pipeline.cc
@@ -593,22 +593,23 @@ struct ChangeLoweringPhase {
};
-struct ControlReductionPhase {
+struct EarlyControlReductionPhase {
+ static const char* phase_name() { return "early control reduction"; }
void Run(PipelineData* data, Zone* temp_zone) {
SourcePositionTable::Scope pos(data->source_positions(),
SourcePosition::Unknown());
- ControlReducer::ReduceGraph(temp_zone, data->jsgraph(),
data->common());
+ ControlReducer::ReduceGraph(temp_zone, data->jsgraph(),
data->common(), 1);
}
};
-struct EarlyControlReductionPhase : ControlReductionPhase {
- static const char* phase_name() { return "early control reduction"; }
-};
-
-
-struct LateControlReductionPhase : ControlReductionPhase {
+struct LateControlReductionPhase {
static const char* phase_name() { return "late control reduction"; }
+ void Run(PipelineData* data, Zone* temp_zone) {
+ SourcePositionTable::Scope pos(data->source_positions(),
+ SourcePosition::Unknown());
+ ControlReducer::ReduceGraph(temp_zone, data->jsgraph(),
data->common(), 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/d/optout.
