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