Line data Source code
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 :
13 788477 : RedundancyElimination::RedundancyElimination(Editor* editor, Zone* zone)
14 1576954 : : AdvancedReducer(editor), node_checks_(zone), zone_(zone) {}
15 :
16 1576942 : RedundancyElimination::~RedundancyElimination() {}
17 :
18 161657653 : Reduction RedundancyElimination::Reduce(Node* node) {
19 85832140 : if (node_checks_.Get(node)) return NoChange();
20 75825513 : 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 762309 : 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 338021 : return TryReuseBoundsCheckForFirstInput(node);
47 : case IrOpcode::kEffectPhi:
48 2103362 : return ReduceEffectPhi(node);
49 : case IrOpcode::kDead:
50 : break;
51 : case IrOpcode::kStart:
52 788476 : return ReduceStart(node);
53 : default:
54 71810974 : return ReduceOtherNode(node);
55 : }
56 : return NoChange();
57 : }
58 :
59 : // static
60 : RedundancyElimination::EffectPathChecks*
61 1317600 : RedundancyElimination::EffectPathChecks::Copy(Zone* zone,
62 : EffectPathChecks const* checks) {
63 1317600 : return new (zone->New(sizeof(EffectPathChecks))) EffectPathChecks(*checks);
64 : }
65 :
66 : // static
67 : RedundancyElimination::EffectPathChecks const*
68 0 : RedundancyElimination::EffectPathChecks::Empty(Zone* zone) {
69 788476 : return new (zone->New(sizeof(EffectPathChecks))) EffectPathChecks(nullptr, 0);
70 : }
71 :
72 0 : bool RedundancyElimination::EffectPathChecks::Equals(
73 : EffectPathChecks const* that) const {
74 0 : if (this->size_ != that->size_) return false;
75 0 : Check* this_head = this->head_;
76 0 : Check* that_head = that->head_;
77 0 : while (this_head != that_head) {
78 0 : if (this_head->node != that_head->node) return false;
79 0 : this_head = this_head->next;
80 0 : that_head = that_head->next;
81 : }
82 : return true;
83 : }
84 :
85 1812923 : 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 1812923 : Check* that_head = that->head_;
93 1812923 : size_t that_size = that->size_;
94 3737764 : while (that_size > size_) {
95 111918 : that_head = that_head->next;
96 111918 : that_size--;
97 : }
98 1883324 : while (size_ > that_size) {
99 70401 : head_ = head_->next;
100 70401 : size_--;
101 : }
102 :
103 : // Then we go through both lists in lock-step until we find
104 : // the common tail.
105 1817923 : while (head_ != that_head) {
106 : DCHECK_LT(0u, size_);
107 : DCHECK_NOT_NULL(head_);
108 5000 : size_--;
109 5000 : head_ = head_->next;
110 5000 : that_head = that_head->next;
111 : }
112 1812923 : }
113 :
114 : RedundancyElimination::EffectPathChecks const*
115 282672 : RedundancyElimination::EffectPathChecks::AddCheck(Zone* zone,
116 : Node* node) const {
117 282672 : Check* head = new (zone->New(sizeof(Check))) Check(node, head_);
118 : return new (zone->New(sizeof(EffectPathChecks)))
119 565344 : EffectPathChecks(head, size_ + 1);
120 : }
121 :
122 : namespace {
123 :
124 4488904 : bool IsCompatibleCheck(Node const* a, Node const* b) {
125 4488904 : if (a->op() != b->op()) {
126 2283901 : if (a->opcode() == IrOpcode::kCheckInternalizedString &&
127 : b->opcode() == IrOpcode::kCheckString) {
128 : // CheckInternalizedString(node) implies CheckString(node)
129 : } else {
130 : return false;
131 : }
132 : }
133 7075860 : for (int i = a->op()->ValueInputCount(); --i >= 0;) {
134 2419420 : if (a->InputAt(i) != b->InputAt(i)) return false;
135 : }
136 : return true;
137 : }
138 :
139 : } // namespace
140 :
141 521777 : Node* RedundancyElimination::EffectPathChecks::LookupCheck(Node* node) const {
142 4771416 : for (Check const* check = head_; check != nullptr; check = check->next) {
143 4488667 : if (IsCompatibleCheck(check->node, node)) {
144 : DCHECK(!check->node->IsDead());
145 : return check->node;
146 : }
147 : }
148 : return nullptr;
149 : }
150 :
151 147895 : Node* RedundancyElimination::EffectPathChecks::LookupBoundsCheckFor(
152 : Node* node) const {
153 237576 : for (Check const* check = head_; check != nullptr; check = check->next) {
154 255503 : 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*
163 136665297 : RedundancyElimination::PathChecksForEffectNodes::Get(Node* node) const {
164 136665297 : size_t const id = node->id();
165 371102717 : if (id < info_for_node_.size()) return info_for_node_[id];
166 : return nullptr;
167 : }
168 :
169 19050562 : void RedundancyElimination::PathChecksForEffectNodes::Set(
170 19050562 : Node* node, EffectPathChecks const* checks) {
171 19050562 : size_t const id = node->id();
172 38101124 : if (id >= info_for_node_.size()) info_for_node_.resize(id + 1, nullptr);
173 19050567 : info_for_node_[id] = checks;
174 19050567 : }
175 :
176 1044981 : Reduction RedundancyElimination::ReduceCheckNode(Node* node) {
177 762309 : 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 762327 : if (checks == nullptr) return NoChange();
182 : // See if we have another check that dominates us.
183 521772 : if (Node* check = checks->LookupCheck(node)) {
184 239135 : ReplaceWithValue(node, check);
185 : return Replace(check);
186 : }
187 :
188 : // Learn from this check.
189 282672 : return UpdateChecks(node, checks->AddCheck(zone(), node));
190 : }
191 :
192 338021 : 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 338021 : 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 338017 : if (checks == nullptr) return NoChange();
205 :
206 : Node* left = node->InputAt(0);
207 220796 : Node* right = node->InputAt(1);
208 : // Only use bounds checks for increments/decrements by a constant.
209 220796 : if (right->opcode() == IrOpcode::kNumberConstant) {
210 147892 : if (Node* bounds_check = checks->LookupBoundsCheckFor(left)) {
211 : // Only use the bounds checked type if it is better.
212 7914 : if (NodeProperties::GetType(bounds_check)
213 : ->Is(NodeProperties::GetType(left))) {
214 5226 : node->ReplaceInput(0, bounds_check);
215 : }
216 : }
217 : }
218 :
219 220799 : return UpdateChecks(node, checks);
220 : }
221 :
222 5409567 : Reduction RedundancyElimination::ReduceEffectPhi(Node* node) {
223 2103359 : Node* const control = NodeProperties::GetControlInput(node);
224 2103346 : 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 114738 : 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 1988608 : int const input_count = node->op()->EffectInputCount();
234 8649068 : for (int i = 0; i < input_count; ++i) {
235 7331464 : Node* const effect = NodeProperties::GetEffectInput(node, i);
236 7331478 : 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 2635204 : zone(), node_checks_.Get(NodeProperties::GetEffectInput(node, 0)));
243 3130531 : for (int i = 1; i < input_count; ++i) {
244 1812925 : Node* const input = NodeProperties::GetEffectInput(node, i);
245 1812924 : checks->Merge(node_checks_.Get(input));
246 : }
247 1317606 : return UpdateChecks(node, checks);
248 : }
249 :
250 788476 : Reduction RedundancyElimination::ReduceStart(Node* node) {
251 788477 : return UpdateChecks(node, EffectPathChecks::Empty(zone()));
252 : }
253 :
254 71812783 : Reduction RedundancyElimination::ReduceOtherNode(Node* node) {
255 71812783 : if (node->op()->EffectInputCount() == 1) {
256 21483790 : if (node->op()->EffectOutputCount() == 1) {
257 20105499 : 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 :
268 20220232 : Reduction RedundancyElimination::TakeChecksFromFirstEffect(Node* node) {
269 : DCHECK_EQ(1, node->op()->EffectOutputCount());
270 20220232 : 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 20220267 : 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 16441164 : return UpdateChecks(node, checks);
278 : }
279 :
280 19050544 : 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 19050544 : if (checks != original) {
286 19050537 : if (original == nullptr || !checks->Equals(original)) {
287 19050544 : 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
|
