1 // Copyright 2016 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/redundancy-elimination.h"
6
7 #include "src/compiler/node-properties.h"
8 #include "src/compiler/simplified-operator.h"
9
10 namespace v8 {
11 namespace internal {
12 namespace compiler {
13
RedundancyElimination(Editor * editor,Zone * zone)14 RedundancyElimination::RedundancyElimination(Editor* editor, Zone* zone)
15 : AdvancedReducer(editor), node_checks_(zone), zone_(zone) {}
16
~RedundancyElimination()17 RedundancyElimination::~RedundancyElimination() {}
18
Reduce(Node * node)19 Reduction RedundancyElimination::Reduce(Node* node) {
20 if (node_checks_.Get(node)) return NoChange();
21 switch (node->opcode()) {
22 case IrOpcode::kCheckBounds:
23 case IrOpcode::kCheckEqualsInternalizedString:
24 case IrOpcode::kCheckEqualsSymbol:
25 case IrOpcode::kCheckFloat64Hole:
26 case IrOpcode::kCheckHeapObject:
27 case IrOpcode::kCheckIf:
28 case IrOpcode::kCheckInternalizedString:
29 case IrOpcode::kCheckNotTaggedHole:
30 case IrOpcode::kCheckNumber:
31 case IrOpcode::kCheckReceiver:
32 case IrOpcode::kCheckSmi:
33 case IrOpcode::kCheckString:
34 case IrOpcode::kCheckSymbol:
35 case IrOpcode::kCheckedFloat64ToInt32:
36 case IrOpcode::kCheckedInt32Add:
37 case IrOpcode::kCheckedInt32Div:
38 case IrOpcode::kCheckedInt32Mod:
39 case IrOpcode::kCheckedInt32Mul:
40 case IrOpcode::kCheckedInt32Sub:
41 case IrOpcode::kCheckedInt32ToTaggedSigned:
42 case IrOpcode::kCheckedTaggedSignedToInt32:
43 case IrOpcode::kCheckedTaggedToFloat64:
44 case IrOpcode::kCheckedTaggedToInt32:
45 case IrOpcode::kCheckedTaggedToTaggedPointer:
46 case IrOpcode::kCheckedTaggedToTaggedSigned:
47 case IrOpcode::kCheckedTruncateTaggedToWord32:
48 case IrOpcode::kCheckedUint32Div:
49 case IrOpcode::kCheckedUint32Mod:
50 case IrOpcode::kCheckedUint32ToInt32:
51 case IrOpcode::kCheckedUint32ToTaggedSigned:
52 return ReduceCheckNode(node);
53 case IrOpcode::kSpeculativeNumberAdd:
54 case IrOpcode::kSpeculativeNumberSubtract:
55 case IrOpcode::kSpeculativeSafeIntegerAdd:
56 case IrOpcode::kSpeculativeSafeIntegerSubtract:
57 // For increments and decrements by a constant, try to learn from the last
58 // bounds check.
59 return TryReuseBoundsCheckForFirstInput(node);
60 case IrOpcode::kEffectPhi:
61 return ReduceEffectPhi(node);
62 case IrOpcode::kDead:
63 break;
64 case IrOpcode::kStart:
65 return ReduceStart(node);
66 default:
67 return ReduceOtherNode(node);
68 }
69 return NoChange();
70 }
71
72 // static
73 RedundancyElimination::EffectPathChecks*
Copy(Zone * zone,EffectPathChecks const * checks)74 RedundancyElimination::EffectPathChecks::Copy(Zone* zone,
75 EffectPathChecks const* checks) {
76 return new (zone->New(sizeof(EffectPathChecks))) EffectPathChecks(*checks);
77 }
78
79 // static
80 RedundancyElimination::EffectPathChecks const*
Empty(Zone * zone)81 RedundancyElimination::EffectPathChecks::Empty(Zone* zone) {
82 return new (zone->New(sizeof(EffectPathChecks))) EffectPathChecks(nullptr, 0);
83 }
84
Equals(EffectPathChecks const * that) const85 bool RedundancyElimination::EffectPathChecks::Equals(
86 EffectPathChecks const* that) const {
87 if (this->size_ != that->size_) return false;
88 Check* this_head = this->head_;
89 Check* that_head = that->head_;
90 while (this_head != that_head) {
91 if (this_head->node != that_head->node) return false;
92 this_head = this_head->next;
93 that_head = that_head->next;
94 }
95 return true;
96 }
97
Merge(EffectPathChecks const * that)98 void RedundancyElimination::EffectPathChecks::Merge(
99 EffectPathChecks const* that) {
100 // Change the current check list to a longest common tail of this check
101 // list and the other list.
102
103 // First, we throw away the prefix of the longer list, so that
104 // we have lists of the same length.
105 Check* that_head = that->head_;
106 size_t that_size = that->size_;
107 while (that_size > size_) {
108 that_head = that_head->next;
109 that_size--;
110 }
111 while (size_ > that_size) {
112 head_ = head_->next;
113 size_--;
114 }
115
116 // Then we go through both lists in lock-step until we find
117 // the common tail.
118 while (head_ != that_head) {
119 DCHECK_LT(0u, size_);
120 DCHECK_NOT_NULL(head_);
121 size_--;
122 head_ = head_->next;
123 that_head = that_head->next;
124 }
125 }
126
127 RedundancyElimination::EffectPathChecks const*
AddCheck(Zone * zone,Node * node) const128 RedundancyElimination::EffectPathChecks::AddCheck(Zone* zone,
129 Node* node) const {
130 Check* head = new (zone->New(sizeof(Check))) Check(node, head_);
131 return new (zone->New(sizeof(EffectPathChecks)))
132 EffectPathChecks(head, size_ + 1);
133 }
134
135 namespace {
136
137 // Does check {a} subsume check {b}?
CheckSubsumes(Node const * a,Node const * b)138 bool CheckSubsumes(Node const* a, Node const* b) {
139 if (a->op() != b->op()) {
140 if (a->opcode() == IrOpcode::kCheckInternalizedString &&
141 b->opcode() == IrOpcode::kCheckString) {
142 // CheckInternalizedString(node) implies CheckString(node)
143 } else if (a->opcode() != b->opcode()) {
144 return false;
145 } else {
146 switch (a->opcode()) {
147 case IrOpcode::kCheckBounds:
148 case IrOpcode::kCheckSmi:
149 case IrOpcode::kCheckString:
150 case IrOpcode::kCheckNumber:
151 break;
152 case IrOpcode::kCheckedInt32ToTaggedSigned:
153 case IrOpcode::kCheckedTaggedSignedToInt32:
154 case IrOpcode::kCheckedTaggedToTaggedPointer:
155 case IrOpcode::kCheckedTaggedToTaggedSigned:
156 case IrOpcode::kCheckedUint32ToInt32:
157 case IrOpcode::kCheckedUint32ToTaggedSigned:
158 break;
159 case IrOpcode::kCheckedFloat64ToInt32:
160 case IrOpcode::kCheckedTaggedToInt32: {
161 const CheckMinusZeroParameters& ap =
162 CheckMinusZeroParametersOf(a->op());
163 const CheckMinusZeroParameters& bp =
164 CheckMinusZeroParametersOf(b->op());
165 if (ap.mode() != bp.mode()) {
166 return false;
167 }
168 break;
169 }
170 default:
171 DCHECK(!IsCheckedWithFeedback(a->op()));
172 return false;
173 }
174 }
175 }
176 for (int i = a->op()->ValueInputCount(); --i >= 0;) {
177 if (a->InputAt(i) != b->InputAt(i)) return false;
178 }
179 return true;
180 }
181
182 } // namespace
183
LookupCheck(Node * node) const184 Node* RedundancyElimination::EffectPathChecks::LookupCheck(Node* node) const {
185 for (Check const* check = head_; check != nullptr; check = check->next) {
186 if (CheckSubsumes(check->node, node)) {
187 DCHECK(!check->node->IsDead());
188 return check->node;
189 }
190 }
191 return nullptr;
192 }
193
LookupBoundsCheckFor(Node * node) const194 Node* RedundancyElimination::EffectPathChecks::LookupBoundsCheckFor(
195 Node* node) const {
196 for (Check const* check = head_; check != nullptr; check = check->next) {
197 if (check->node->opcode() == IrOpcode::kCheckBounds &&
198 check->node->InputAt(0) == node) {
199 return check->node;
200 }
201 }
202 return nullptr;
203 }
204
205 RedundancyElimination::EffectPathChecks const*
Get(Node * node) const206 RedundancyElimination::PathChecksForEffectNodes::Get(Node* node) const {
207 size_t const id = node->id();
208 if (id < info_for_node_.size()) return info_for_node_[id];
209 return nullptr;
210 }
211
Set(Node * node,EffectPathChecks const * checks)212 void RedundancyElimination::PathChecksForEffectNodes::Set(
213 Node* node, EffectPathChecks const* checks) {
214 size_t const id = node->id();
215 if (id >= info_for_node_.size()) info_for_node_.resize(id + 1, nullptr);
216 info_for_node_[id] = checks;
217 }
218
ReduceCheckNode(Node * node)219 Reduction RedundancyElimination::ReduceCheckNode(Node* node) {
220 Node* const effect = NodeProperties::GetEffectInput(node);
221 EffectPathChecks const* checks = node_checks_.Get(effect);
222 // If we do not know anything about the predecessor, do not propagate just yet
223 // because we will have to recompute anyway once we compute the predecessor.
224 if (checks == nullptr) return NoChange();
225 // See if we have another check that dominates us.
226 if (Node* check = checks->LookupCheck(node)) {
227 ReplaceWithValue(node, check);
228 return Replace(check);
229 }
230
231 // Learn from this check.
232 return UpdateChecks(node, checks->AddCheck(zone(), node));
233 }
234
TryReuseBoundsCheckForFirstInput(Node * node)235 Reduction RedundancyElimination::TryReuseBoundsCheckForFirstInput(Node* node) {
236 DCHECK(node->opcode() == IrOpcode::kSpeculativeNumberAdd ||
237 node->opcode() == IrOpcode::kSpeculativeNumberSubtract ||
238 node->opcode() == IrOpcode::kSpeculativeSafeIntegerAdd ||
239 node->opcode() == IrOpcode::kSpeculativeSafeIntegerSubtract);
240
241 DCHECK_EQ(1, node->op()->EffectInputCount());
242 DCHECK_EQ(1, node->op()->EffectOutputCount());
243
244 Node* const effect = NodeProperties::GetEffectInput(node);
245 EffectPathChecks const* checks = node_checks_.Get(effect);
246
247 // If we do not know anything about the predecessor, do not propagate just yet
248 // because we will have to recompute anyway once we compute the predecessor.
249 if (checks == nullptr) return NoChange();
250
251 Node* left = node->InputAt(0);
252 Node* right = node->InputAt(1);
253 // Only use bounds checks for increments/decrements by a constant.
254 if (right->opcode() == IrOpcode::kNumberConstant) {
255 if (Node* bounds_check = checks->LookupBoundsCheckFor(left)) {
256 // Only use the bounds checked type if it is better.
257 if (NodeProperties::GetType(bounds_check)
258 .Is(NodeProperties::GetType(left))) {
259 node->ReplaceInput(0, bounds_check);
260 }
261 }
262 }
263
264 return UpdateChecks(node, checks);
265 }
266
ReduceEffectPhi(Node * node)267 Reduction RedundancyElimination::ReduceEffectPhi(Node* node) {
268 Node* const control = NodeProperties::GetControlInput(node);
269 if (control->opcode() == IrOpcode::kLoop) {
270 // Here we rely on having only reducible loops:
271 // The loop entry edge always dominates the header, so we can just use
272 // the information from the loop entry edge.
273 return TakeChecksFromFirstEffect(node);
274 }
275 DCHECK_EQ(IrOpcode::kMerge, control->opcode());
276
277 // Shortcut for the case when we do not know anything about some input.
278 int const input_count = node->op()->EffectInputCount();
279 for (int i = 0; i < input_count; ++i) {
280 Node* const effect = NodeProperties::GetEffectInput(node, i);
281 if (node_checks_.Get(effect) == nullptr) return NoChange();
282 }
283
284 // Make a copy of the first input's checks and merge with the checks
285 // from other inputs.
286 EffectPathChecks* checks = EffectPathChecks::Copy(
287 zone(), node_checks_.Get(NodeProperties::GetEffectInput(node, 0)));
288 for (int i = 1; i < input_count; ++i) {
289 Node* const input = NodeProperties::GetEffectInput(node, i);
290 checks->Merge(node_checks_.Get(input));
291 }
292 return UpdateChecks(node, checks);
293 }
294
ReduceStart(Node * node)295 Reduction RedundancyElimination::ReduceStart(Node* node) {
296 return UpdateChecks(node, EffectPathChecks::Empty(zone()));
297 }
298
ReduceOtherNode(Node * node)299 Reduction RedundancyElimination::ReduceOtherNode(Node* node) {
300 if (node->op()->EffectInputCount() == 1) {
301 if (node->op()->EffectOutputCount() == 1) {
302 return TakeChecksFromFirstEffect(node);
303 } else {
304 // Effect terminators should be handled specially.
305 return NoChange();
306 }
307 }
308 DCHECK_EQ(0, node->op()->EffectInputCount());
309 DCHECK_EQ(0, node->op()->EffectOutputCount());
310 return NoChange();
311 }
312
TakeChecksFromFirstEffect(Node * node)313 Reduction RedundancyElimination::TakeChecksFromFirstEffect(Node* node) {
314 DCHECK_EQ(1, node->op()->EffectOutputCount());
315 Node* const effect = NodeProperties::GetEffectInput(node);
316 EffectPathChecks const* checks = node_checks_.Get(effect);
317 // If we do not know anything about the predecessor, do not propagate just yet
318 // because we will have to recompute anyway once we compute the predecessor.
319 if (checks == nullptr) return NoChange();
320 // We just propagate the information from the effect input (ideally,
321 // we would only revisit effect uses if there is change).
322 return UpdateChecks(node, checks);
323 }
324
UpdateChecks(Node * node,EffectPathChecks const * checks)325 Reduction RedundancyElimination::UpdateChecks(Node* node,
326 EffectPathChecks const* checks) {
327 EffectPathChecks const* original = node_checks_.Get(node);
328 // Only signal that the {node} has Changed, if the information about {checks}
329 // has changed wrt. the {original}.
330 if (checks != original) {
331 if (original == nullptr || !checks->Equals(original)) {
332 node_checks_.Set(node, checks);
333 return Changed(node);
334 }
335 }
336 return NoChange();
337 }
338
339 } // namespace compiler
340 } // namespace internal
341 } // namespace v8
342