Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(81)

Side by Side Diff: src/compiler/branch-condition-elimination.cc

Issue 1376293005: [turbofan] Redundant branch elimination. (Closed) Base URL: https://chromium.googlesource.com/v8/v8.git@master
Patch Set: Loop test Created 5 years, 2 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch
OLDNEW
(Empty)
1 // Copyright 2015 the V8 project authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4
5 #include "src/compiler/branch-condition-elimination.h"
6
7 #include "src/compiler/js-graph.h"
8 #include "src/compiler/node-properties.h"
9 #include "src/compiler/simplified-operator.h"
10
11 namespace v8 {
12 namespace internal {
13 namespace compiler {
14
15 BranchConditionElimination::BranchConditionElimination(Editor* editor,
16 JSGraph* js_graph,
17 Zone* zone)
18 : AdvancedReducer(editor),
19 node_conditions_(zone, js_graph->graph()->NodeCount()),
20 zone_(zone),
21 dead_(js_graph->graph()->NewNode(js_graph->common()->Dead())) {}
22
23
24 BranchConditionElimination::~BranchConditionElimination() {}
25
26
27 Reduction BranchConditionElimination::Reduce(Node* node) {
28 switch (node->opcode()) {
29 case IrOpcode::kDead:
30 return NoChange();
31 case IrOpcode::kMerge:
32 return ReduceMerge(node);
33 case IrOpcode::kLoop:
34 return ReduceLoop(node);
35 case IrOpcode::kBranch:
36 return ReduceBranch(node);
37 case IrOpcode::kIfFalse:
38 return ReduceIf(node, false);
39 case IrOpcode::kIfTrue:
40 return ReduceIf(node, true);
41 case IrOpcode::kStart:
42 return ReduceStart(node);
43 default:
44 if (node->op()->ControlOutputCount() > 0) {
45 return ReduceOtherControl(node);
46 }
47 break;
48 }
49 return NoChange();
50 }
51
52
53 Reduction BranchConditionElimination::ReduceBranch(Node* node) {
54 Node* condition = node->InputAt(0);
55 Node* control_input = NodeProperties::GetControlInput(node, 0);
56 const ControlPathConditions* from_input = node_conditions_.Get(control_input);
57 if (from_input != nullptr) {
58 Maybe<bool> condition_value = from_input->LookupCondition(condition);
59 // If we know the condition reduce the branch.
60 if (condition_value.IsJust()) {
61 bool known_value = condition_value.FromJust();
62 for (Node* const use : node->uses()) {
63 switch (use->opcode()) {
64 case IrOpcode::kIfTrue:
65 Replace(use, known_value ? control_input : dead());
66 break;
67 case IrOpcode::kIfFalse:
68 Replace(use, known_value ? dead() : control_input);
69 break;
70 default:
71 UNREACHABLE();
72 }
73 }
74 return Replace(dead());
75 }
76 }
77 return TakeConditionsFromFirstControl(node);
78 }
79
80
81 Reduction BranchConditionElimination::ReduceIf(Node* node,
82 bool is_true_branch) {
83 // Add the condition to the list arriving from the input branch.
84 Node* branch = NodeProperties::GetControlInput(node, 0);
85 const ControlPathConditions* from_branch = node_conditions_.Get(branch);
86 // If we do not know anything about the predecessor, do not propagate just
87 // yet because we will have to recompute anyway once we compute the
88 // predecessor.
89 if (from_branch == nullptr) {
90 DCHECK(node_conditions_.Get(node) == nullptr);
91 return NoChange();
92 }
93 Node* condition = branch->InputAt(0);
94 return UpdateConditions(
95 node, from_branch->AddCondition(zone_, condition, is_true_branch));
96 }
97
98
99 Reduction BranchConditionElimination::ReduceLoop(Node* node) {
100 // Here we rely on having only reducible loops:
101 // The loop entry edge always dominates the header, so we just use
102 // the information from the loop entry edge.
103 return TakeConditionsFromFirstControl(node);
104 }
105
106
107 Reduction BranchConditionElimination::ReduceMerge(Node* node) {
108 // Shortcut for the case when we do not know anything about some
109 // input.
110 for (int i = 0; i < node->InputCount(); i++) {
111 if (node_conditions_.Get(node->InputAt(i)) == nullptr) {
112 DCHECK(node_conditions_.Get(node) == nullptr);
113 return NoChange();
114 }
115 }
116
117 // Extract the information into the array.
118 ZoneVector<const ControlPathConditions*> input_conditions(zone_);
119 input_conditions.reserve(node->InputCount());
120 for (int i = 0; i < node->InputCount(); i++) {
121 input_conditions.push_back(node_conditions_.Get(node->InputAt(i)));
122 }
123
124 // Calculate the merged conditions.
125 const ControlPathConditions* conditions =
126 ControlPathConditions::Merge(zone_, input_conditions);
127
128 return UpdateConditions(node, conditions);
129 }
130
131
132 Reduction BranchConditionElimination::ReduceStart(Node* node) {
133 return UpdateConditions(node, ControlPathConditions::Empty(zone_));
134 }
135
136
137 const BranchConditionElimination::ControlPathConditions*
138 BranchConditionElimination::PathConditionsForControlNodes::Get(Node* node) {
139 if (static_cast<size_t>(node->id()) < info_for_node_.size()) {
140 return info_for_node_[node->id()];
141 }
142 return nullptr;
143 }
144
145
146 void BranchConditionElimination::PathConditionsForControlNodes::Set(
147 Node* node, const ControlPathConditions* conditions) {
148 size_t index = static_cast<size_t>(node->id());
149 if (index >= info_for_node_.size()) {
150 info_for_node_.resize(index + 1, nullptr);
151 }
152 info_for_node_[index] = conditions;
153 }
154
155
156 Reduction BranchConditionElimination::ReduceOtherControl(Node* node) {
157 DCHECK_EQ(1, node->op()->ControlInputCount());
158 return TakeConditionsFromFirstControl(node);
159 }
160
161
162 Reduction BranchConditionElimination::TakeConditionsFromFirstControl(
163 Node* node) {
164 // We just propagate the information from the control input (ideally,
165 // we would only revisit control uses if there is change).
166 const ControlPathConditions* from_input =
167 node_conditions_.Get(NodeProperties::GetControlInput(node, 0));
168 return UpdateConditions(node, from_input);
169 }
170
171
172 Reduction BranchConditionElimination::UpdateConditions(
173 Node* node, const ControlPathConditions* conditions) {
174 const ControlPathConditions* original = node_conditions_.Get(node);
175 // Only signal that the node has Changed if the condition information has
176 // changed.
177 if (conditions != original) {
178 if (original == nullptr || *conditions != *original) {
179 node_conditions_.Set(node, conditions);
180 return Changed(node);
181 }
182 }
183 return NoChange();
184 }
185
186
187 bool BranchConditionElimination::BranchCondition::operator<(
188 const BranchCondition& other) const {
189 return condition_->id() < other.condition_->id();
190 }
191
192
193 bool BranchConditionElimination::BranchCondition::operator==(
194 const BranchCondition& other) const {
195 return condition_ == other.condition_ && is_true_ == other.is_true_;
196 }
197
198
199 // static
200 const BranchConditionElimination::ControlPathConditions*
201 BranchConditionElimination::ControlPathConditions::Empty(Zone* zone) {
202 return new (zone->New(sizeof(ControlPathConditions)))
203 ControlPathConditions(zone, 0);
204 }
205
206
207 // static
208 const BranchConditionElimination::ControlPathConditions*
209 BranchConditionElimination::ControlPathConditions::Merge(
210 Zone* zone, const ZoneVector<const ControlPathConditions*>& inputs) {
211 // The resulting list will not be longer than any of the input lists.
212 // We just take the size of the first list for capacity.
213 ControlPathConditions* conditions =
214 new (zone->New(sizeof(ControlPathConditions)))
215 ControlPathConditions(zone, inputs[0]->conditions_.size());
216 // We only take conditions that are known at each input. We use a naive
217 // to calculate that: take all the conditions from the first input that
218 // are present (and have the same value) in all the other inputs.
219 // Note: there are more efficient ways to do this (merge the lists or some
220 // such), but they are more complex.
221 for (auto branch_condition : inputs[0]->conditions_) {
222 bool all_same = true;
223 for (size_t j = 1; j < inputs.size(); j++) {
224 Maybe<bool> value =
225 inputs[j]->LookupCondition(branch_condition.condition_);
226 if (value.IsNothing() || value.FromJust() != branch_condition.is_true_) {
227 all_same = false;
228 break;
229 }
230 }
231 if (all_same) {
232 conditions->conditions_.push_back(branch_condition);
233 }
234 }
235 return conditions;
236 }
237
238
239 const BranchConditionElimination::ControlPathConditions*
240 BranchConditionElimination::ControlPathConditions::AddCondition(
241 Zone* zone, Node* condition, bool is_true) const {
242 BranchCondition new_element(condition, is_true);
243 auto res =
244 std::lower_bound(conditions_.begin(), conditions_.end(), new_element);
245 if (res != conditions_.end() && res->condition_ == condition) {
246 // We found the same condition. We can just return the conditions. Note that
247 // it does not matter if the {is_true} value does not match - that just
248 // means that the current control path is not reachable.
249 return this;
250 }
251 // Build the new conditions.
252 ControlPathConditions* conditions =
253 new (zone->New(sizeof(ControlPathConditions)))
254 ControlPathConditions(zone, conditions_.size() + 1);
255 // Insert all the elements before the condition.
256 conditions->conditions_.insert(conditions->conditions_.end(),
257 conditions_.begin(), res);
258 // Insert the condition.
259 conditions->conditions_.push_back(new_element);
260 // Insert the rest.
261 conditions->conditions_.insert(conditions->conditions_.end(), res,
262 conditions_.end());
263 return conditions;
264 }
265
266
267 Maybe<bool> BranchConditionElimination::ControlPathConditions::LookupCondition(
268 Node* condition) const {
269 BranchCondition element(condition, false);
270 auto res = std::lower_bound(conditions_.begin(), conditions_.end(), element);
271 if (res != conditions_.end() && res->condition_ == condition) {
272 return Just<bool>(res->is_true_);
273 }
274 return Nothing<bool>();
275 }
276
277
278 bool BranchConditionElimination::ControlPathConditions::operator==(
279 const ControlPathConditions& other) const {
280 return conditions_ == other.conditions_;
281 }
282
283 } // namespace compiler
284 } // namespace internal
285 } // namespace v8
OLDNEW

Powered by Google App Engine
This is Rietveld 408576698