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 787038 : RedundancyElimination::RedundancyElimination(Editor* editor, Zone* zone)
14 1574076 : : AdvancedReducer(editor), node_checks_(zone), zone_(zone) {}
15 :
16 1574078 : RedundancyElimination::~RedundancyElimination() {}
17 :
18 161665822 : Reduction RedundancyElimination::Reduce(Node* node) {
19 85838280 : if (node_checks_.Get(node)) return NoChange();
20 75827542 : 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 762536 : 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 336490 : return TryReuseBoundsCheckForFirstInput(node);
47 : case IrOpcode::kEffectPhi:
48 2104131 : return ReduceEffectPhi(node);
49 : case IrOpcode::kDead:
50 : break;
51 : case IrOpcode::kStart:
52 787039 : return ReduceStart(node);
53 : default:
54 71814923 : return ReduceOtherNode(node);
55 : }
56 : return NoChange();
57 : }
58 :
59 : // static
60 : RedundancyElimination::EffectPathChecks*
61 1316923 : RedundancyElimination::EffectPathChecks::Copy(Zone* zone,
62 : EffectPathChecks const* checks) {
63 1316923 : return new (zone->New(sizeof(EffectPathChecks))) EffectPathChecks(*checks);
64 : }
65 :
66 : // static
67 : RedundancyElimination::EffectPathChecks const*
68 0 : RedundancyElimination::EffectPathChecks::Empty(Zone* zone) {
69 787039 : 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 1813106 : 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 1813106 : Check* that_head = that->head_;
93 1813106 : size_t that_size = that->size_;
94 3737933 : while (that_size > size_) {
95 111721 : that_head = that_head->next;
96 111721 : that_size--;
97 : }
98 1883121 : while (size_ > that_size) {
99 70015 : head_ = head_->next;
100 70015 : size_--;
101 : }
102 :
103 : // Then we go through both lists in lock-step until we find
104 : // the common tail.
105 1818058 : while (head_ != that_head) {
106 : DCHECK_LT(0u, size_);
107 : DCHECK_NOT_NULL(head_);
108 4952 : size_--;
109 4952 : head_ = head_->next;
110 4952 : that_head = that_head->next;
111 : }
112 1813106 : }
113 :
114 : RedundancyElimination::EffectPathChecks const*
115 282342 : RedundancyElimination::EffectPathChecks::AddCheck(Zone* zone,
116 : Node* node) const {
117 282342 : Check* head = new (zone->New(sizeof(Check))) Check(node, head_);
118 : return new (zone->New(sizeof(EffectPathChecks)))
119 564685 : EffectPathChecks(head, size_ + 1);
120 : }
121 :
122 : namespace {
123 :
124 4500703 : bool IsCompatibleCheck(Node const* a, Node const* b) {
125 4500703 : if (a->op() != b->op()) {
126 2291841 : if (a->opcode() == IrOpcode::kCheckInternalizedString &&
127 : b->opcode() == IrOpcode::kCheckString) {
128 : // CheckInternalizedString(node) implies CheckString(node)
129 : } else {
130 : return false;
131 : }
132 : }
133 7086841 : for (int i = a->op()->ValueInputCount(); --i >= 0;) {
134 2423171 : if (a->InputAt(i) != b->InputAt(i)) return false;
135 : }
136 : return true;
137 : }
138 :
139 : } // namespace
140 :
141 521542 : Node* RedundancyElimination::EffectPathChecks::LookupCheck(Node* node) const {
142 4783055 : for (Check const* check = head_; check != nullptr; check = check->next) {
143 4500645 : if (IsCompatibleCheck(check->node, node)) {
144 : DCHECK(!check->node->IsDead());
145 : return check->node;
146 : }
147 : }
148 : return nullptr;
149 : }
150 :
151 147877 : Node* RedundancyElimination::EffectPathChecks::LookupBoundsCheckFor(
152 : Node* node) const {
153 234623 : for (Check const* check = head_; check != nullptr; check = check->next) {
154 246962 : 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 136697435 : RedundancyElimination::PathChecksForEffectNodes::Get(Node* node) const {
164 136697435 : size_t const id = node->id();
165 371207822 : if (id < info_for_node_.size()) return info_for_node_[id];
166 : return nullptr;
167 : }
168 :
169 19057362 : void RedundancyElimination::PathChecksForEffectNodes::Set(
170 19057362 : Node* node, EffectPathChecks const* checks) {
171 19057362 : size_t const id = node->id();
172 38114724 : if (id >= info_for_node_.size()) info_for_node_.resize(id + 1, nullptr);
173 19057364 : info_for_node_[id] = checks;
174 19057364 : }
175 :
176 1044878 : Reduction RedundancyElimination::ReduceCheckNode(Node* node) {
177 762536 : 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 762565 : if (checks == nullptr) return NoChange();
182 : // See if we have another check that dominates us.
183 521541 : if (Node* check = checks->LookupCheck(node)) {
184 239210 : ReplaceWithValue(node, check);
185 : return Replace(check);
186 : }
187 :
188 : // Learn from this check.
189 282342 : return UpdateChecks(node, checks->AddCheck(zone(), node));
190 : }
191 :
192 336491 : 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 336491 : 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 336511 : if (checks == nullptr) return NoChange();
205 :
206 : Node* left = node->InputAt(0);
207 220096 : Node* right = node->InputAt(1);
208 : // Only use bounds checks for increments/decrements by a constant.
209 220096 : if (right->opcode() == IrOpcode::kNumberConstant) {
210 147878 : if (Node* bounds_check = checks->LookupBoundsCheckFor(left)) {
211 : // Only use the bounds checked type if it is better.
212 7926 : if (NodeProperties::GetType(bounds_check)
213 : ->Is(NodeProperties::GetType(left))) {
214 5231 : node->ReplaceInput(0, bounds_check);
215 : }
216 : }
217 : }
218 :
219 220095 : return UpdateChecks(node, checks);
220 : }
221 :
222 5410212 : Reduction RedundancyElimination::ReduceEffectPhi(Node* node) {
223 2104127 : Node* const control = NodeProperties::GetControlInput(node);
224 2104118 : 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 114955 : 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 1989163 : int const input_count = node->op()->EffectInputCount();
234 8647923 : for (int i = 0; i < input_count; ++i) {
235 7331001 : Node* const effect = NodeProperties::GetEffectInput(node, i);
236 7331013 : 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 2633844 : zone(), node_checks_.Get(NodeProperties::GetEffectInput(node, 0)));
243 3130029 : for (int i = 1; i < input_count; ++i) {
244 1813107 : Node* const input = NodeProperties::GetEffectInput(node, i);
245 1813107 : checks->Merge(node_checks_.Get(input));
246 : }
247 1316922 : return UpdateChecks(node, checks);
248 : }
249 :
250 787039 : Reduction RedundancyElimination::ReduceStart(Node* node) {
251 787039 : return UpdateChecks(node, EffectPathChecks::Empty(zone()));
252 : }
253 :
254 71816922 : Reduction RedundancyElimination::ReduceOtherNode(Node* node) {
255 71816922 : if (node->op()->EffectInputCount() == 1) {
256 21506122 : if (node->op()->EffectOutputCount() == 1) {
257 20126692 : 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 20241641 : Reduction RedundancyElimination::TakeChecksFromFirstEffect(Node* node) {
269 : DCHECK_EQ(1, node->op()->EffectOutputCount());
270 20241641 : 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 20241686 : 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 16451103 : return UpdateChecks(node, checks);
278 : }
279 :
280 19057351 : 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 19057351 : if (checks != original) {
286 19057347 : if (original == nullptr || !checks->Equals(original)) {
287 19057351 : 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
|
