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