1 // Copyright 2019 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/csa-load-elimination.h"
6
7 #include "src/compiler/common-operator.h"
8 #include "src/compiler/node-matchers.h"
9 #include "src/compiler/node-properties.h"
10 #include "src/compiler/simplified-operator.h"
11
12 namespace v8 {
13 namespace internal {
14 namespace compiler {
15
Reduce(Node * node)16 Reduction CsaLoadElimination::Reduce(Node* node) {
17 if (FLAG_trace_turbo_load_elimination) {
18 if (node->op()->EffectInputCount() > 0) {
19 PrintF(" visit #%d:%s", node->id(), node->op()->mnemonic());
20 if (node->op()->ValueInputCount() > 0) {
21 PrintF("(");
22 for (int i = 0; i < node->op()->ValueInputCount(); ++i) {
23 if (i > 0) PrintF(", ");
24 Node* const value = NodeProperties::GetValueInput(node, i);
25 PrintF("#%d:%s", value->id(), value->op()->mnemonic());
26 }
27 PrintF(")");
28 }
29 PrintF("\n");
30 for (int i = 0; i < node->op()->EffectInputCount(); ++i) {
31 Node* const effect = NodeProperties::GetEffectInput(node, i);
32 if (AbstractState const* const state = node_states_.Get(effect)) {
33 PrintF(" state[%i]: #%d:%s\n", i, effect->id(),
34 effect->op()->mnemonic());
35 state->Print();
36 } else {
37 PrintF(" no state[%i]: #%d:%s\n", i, effect->id(),
38 effect->op()->mnemonic());
39 }
40 }
41 }
42 }
43 switch (node->opcode()) {
44 case IrOpcode::kLoadFromObject:
45 return ReduceLoadFromObject(node, ObjectAccessOf(node->op()));
46 case IrOpcode::kStoreToObject:
47 return ReduceStoreToObject(node, ObjectAccessOf(node->op()));
48 case IrOpcode::kDebugBreak:
49 case IrOpcode::kAbortCSAAssert:
50 // Avoid changing optimizations in the presence of debug instructions.
51 return PropagateInputState(node);
52 case IrOpcode::kCall:
53 return ReduceCall(node);
54 case IrOpcode::kEffectPhi:
55 return ReduceEffectPhi(node);
56 case IrOpcode::kDead:
57 break;
58 case IrOpcode::kStart:
59 return ReduceStart(node);
60 default:
61 return ReduceOtherNode(node);
62 }
63 return NoChange();
64 }
65
66 namespace CsaLoadEliminationHelpers {
67
IsCompatible(MachineRepresentation r1,MachineRepresentation r2)68 bool IsCompatible(MachineRepresentation r1, MachineRepresentation r2) {
69 if (r1 == r2) return true;
70 return IsAnyTagged(r1) && IsAnyTagged(r2);
71 }
72
ObjectMayAlias(Node * a,Node * b)73 bool ObjectMayAlias(Node* a, Node* b) {
74 if (a != b) {
75 if (b->opcode() == IrOpcode::kAllocate) {
76 std::swap(a, b);
77 }
78 if (a->opcode() == IrOpcode::kAllocate) {
79 switch (b->opcode()) {
80 case IrOpcode::kAllocate:
81 case IrOpcode::kHeapConstant:
82 case IrOpcode::kParameter:
83 return false;
84 default:
85 break;
86 }
87 }
88 }
89 return true;
90 }
91
OffsetMayAlias(Node * offset1,MachineRepresentation repr1,Node * offset2,MachineRepresentation repr2)92 bool OffsetMayAlias(Node* offset1, MachineRepresentation repr1, Node* offset2,
93 MachineRepresentation repr2) {
94 IntPtrMatcher matcher1(offset1);
95 IntPtrMatcher matcher2(offset2);
96 // If either of the offsets is variable, accesses may alias
97 if (!matcher1.HasResolvedValue() || !matcher2.HasResolvedValue()) {
98 return true;
99 }
100 // Otherwise, we return whether accesses overlap
101 intptr_t start1 = matcher1.ResolvedValue();
102 intptr_t end1 = start1 + ElementSizeInBytes(repr1);
103 intptr_t start2 = matcher2.ResolvedValue();
104 intptr_t end2 = start2 + ElementSizeInBytes(repr2);
105 return !(end1 <= start2 || end2 <= start1);
106 }
107
108 } // namespace CsaLoadEliminationHelpers
109
110 namespace Helpers = CsaLoadEliminationHelpers;
111
Merge(AbstractState const * that,Zone * zone)112 void CsaLoadElimination::AbstractState::Merge(AbstractState const* that,
113 Zone* zone) {
114 FieldInfo empty_info;
115 for (std::pair<Field, FieldInfo> entry : field_infos_) {
116 if (that->field_infos_.Get(entry.first) != entry.second) {
117 field_infos_.Set(entry.first, empty_info);
118 }
119 }
120 }
121
122 CsaLoadElimination::AbstractState const*
KillField(Node * kill_object,Node * kill_offset,MachineRepresentation kill_repr,Zone * zone) const123 CsaLoadElimination::AbstractState::KillField(Node* kill_object,
124 Node* kill_offset,
125 MachineRepresentation kill_repr,
126 Zone* zone) const {
127 FieldInfo empty_info;
128 AbstractState* that = zone->New<AbstractState>(*this);
129 for (std::pair<Field, FieldInfo> entry : that->field_infos_) {
130 Field field = entry.first;
131 MachineRepresentation field_repr = entry.second.representation;
132 if (Helpers::OffsetMayAlias(kill_offset, kill_repr, field.second,
133 field_repr) &&
134 Helpers::ObjectMayAlias(kill_object, field.first)) {
135 that->field_infos_.Set(field, empty_info);
136 }
137 }
138 return that;
139 }
140
141 CsaLoadElimination::AbstractState const*
AddField(Node * object,Node * offset,CsaLoadElimination::FieldInfo info,Zone * zone) const142 CsaLoadElimination::AbstractState::AddField(Node* object, Node* offset,
143 CsaLoadElimination::FieldInfo info,
144 Zone* zone) const {
145 AbstractState* that = zone->New<AbstractState>(*this);
146 that->field_infos_.Set({object, offset}, info);
147 return that;
148 }
149
Lookup(Node * object,Node * offset) const150 CsaLoadElimination::FieldInfo CsaLoadElimination::AbstractState::Lookup(
151 Node* object, Node* offset) const {
152 if (object->IsDead()) {
153 return {};
154 }
155 return field_infos_.Get({object, offset});
156 }
157
Print() const158 void CsaLoadElimination::AbstractState::Print() const {
159 for (std::pair<Field, FieldInfo> entry : field_infos_) {
160 Field field = entry.first;
161 Node* object = field.first;
162 Node* offset = field.second;
163 FieldInfo info = entry.second;
164 PrintF(" #%d+#%d:%s -> #%d:%s [repr=%s]\n", object->id(), offset->id(),
165 object->op()->mnemonic(), info.value->id(),
166 info.value->op()->mnemonic(),
167 MachineReprToString(info.representation));
168 }
169 }
170
ReduceLoadFromObject(Node * node,ObjectAccess const & access)171 Reduction CsaLoadElimination::ReduceLoadFromObject(Node* node,
172 ObjectAccess const& access) {
173 Node* object = NodeProperties::GetValueInput(node, 0);
174 Node* offset = NodeProperties::GetValueInput(node, 1);
175 Node* effect = NodeProperties::GetEffectInput(node);
176 AbstractState const* state = node_states_.Get(effect);
177 if (state == nullptr) return NoChange();
178
179 MachineRepresentation representation = access.machine_type.representation();
180 FieldInfo lookup_result = state->Lookup(object, offset);
181 if (!lookup_result.IsEmpty()) {
182 // Make sure we don't reuse values that were recorded with a different
183 // representation or resurrect dead {replacement} nodes.
184 Node* replacement = lookup_result.value;
185 if (Helpers::IsCompatible(representation, lookup_result.representation) &&
186 !replacement->IsDead()) {
187 ReplaceWithValue(node, replacement, effect);
188 return Replace(replacement);
189 }
190 }
191 FieldInfo info(node, representation);
192 state = state->AddField(object, offset, info, zone());
193
194 return UpdateState(node, state);
195 }
196
ReduceStoreToObject(Node * node,ObjectAccess const & access)197 Reduction CsaLoadElimination::ReduceStoreToObject(Node* node,
198 ObjectAccess const& access) {
199 Node* object = NodeProperties::GetValueInput(node, 0);
200 Node* offset = NodeProperties::GetValueInput(node, 1);
201 Node* value = NodeProperties::GetValueInput(node, 2);
202 Node* effect = NodeProperties::GetEffectInput(node);
203 AbstractState const* state = node_states_.Get(effect);
204 if (state == nullptr) return NoChange();
205
206 FieldInfo info(value, access.machine_type.representation());
207 state = state->KillField(object, offset, info.representation, zone());
208 state = state->AddField(object, offset, info, zone());
209
210 return UpdateState(node, state);
211 }
212
ReduceEffectPhi(Node * node)213 Reduction CsaLoadElimination::ReduceEffectPhi(Node* node) {
214 Node* const effect0 = NodeProperties::GetEffectInput(node, 0);
215 Node* const control = NodeProperties::GetControlInput(node);
216 AbstractState const* state0 = node_states_.Get(effect0);
217 if (state0 == nullptr) return NoChange();
218 if (control->opcode() == IrOpcode::kLoop) {
219 // Here we rely on having only reducible loops:
220 // The loop entry edge always dominates the header, so we can just take
221 // the state from the first input, and compute the loop state based on it.
222 AbstractState const* state = ComputeLoopState(node, state0);
223 return UpdateState(node, state);
224 }
225 DCHECK_EQ(IrOpcode::kMerge, control->opcode());
226
227 // Shortcut for the case when we do not know anything about some input.
228 int const input_count = node->op()->EffectInputCount();
229 for (int i = 1; i < input_count; ++i) {
230 Node* const effect = NodeProperties::GetEffectInput(node, i);
231 if (node_states_.Get(effect) == nullptr) return NoChange();
232 }
233
234 // Make a copy of the first input's state and merge with the state
235 // from other inputs.
236 AbstractState* state = zone()->New<AbstractState>(*state0);
237 for (int i = 1; i < input_count; ++i) {
238 Node* const input = NodeProperties::GetEffectInput(node, i);
239 state->Merge(node_states_.Get(input), zone());
240 }
241 return UpdateState(node, state);
242 }
243
ReduceStart(Node * node)244 Reduction CsaLoadElimination::ReduceStart(Node* node) {
245 return UpdateState(node, empty_state());
246 }
247
ReduceCall(Node * node)248 Reduction CsaLoadElimination::ReduceCall(Node* node) {
249 Node* value = NodeProperties::GetValueInput(node, 0);
250 ExternalReferenceMatcher m(value);
251 if (m.Is(ExternalReference::check_object_type())) {
252 return PropagateInputState(node);
253 }
254 return ReduceOtherNode(node);
255 }
256
ReduceOtherNode(Node * node)257 Reduction CsaLoadElimination::ReduceOtherNode(Node* node) {
258 if (node->op()->EffectInputCount() == 1) {
259 if (node->op()->EffectOutputCount() == 1) {
260 Node* const effect = NodeProperties::GetEffectInput(node);
261 AbstractState const* state = node_states_.Get(effect);
262 // If we do not know anything about the predecessor, do not propagate
263 // just yet because we will have to recompute anyway once we compute
264 // the predecessor.
265 if (state == nullptr) return NoChange();
266 // Check if this {node} has some uncontrolled side effects.
267 if (!node->op()->HasProperty(Operator::kNoWrite)) {
268 state = empty_state();
269 }
270 return UpdateState(node, state);
271 } else {
272 return NoChange();
273 }
274 }
275 DCHECK_EQ(0, node->op()->EffectInputCount());
276 DCHECK_EQ(0, node->op()->EffectOutputCount());
277 return NoChange();
278 }
279
UpdateState(Node * node,AbstractState const * state)280 Reduction CsaLoadElimination::UpdateState(Node* node,
281 AbstractState const* state) {
282 AbstractState const* original = node_states_.Get(node);
283 // Only signal that the {node} has Changed, if the information about {state}
284 // has changed wrt. the {original}.
285 if (state != original) {
286 if (original == nullptr || !state->Equals(original)) {
287 node_states_.Set(node, state);
288 return Changed(node);
289 }
290 }
291 return NoChange();
292 }
293
PropagateInputState(Node * node)294 Reduction CsaLoadElimination::PropagateInputState(Node* node) {
295 Node* const effect = NodeProperties::GetEffectInput(node);
296 AbstractState const* state = node_states_.Get(effect);
297 if (state == nullptr) return NoChange();
298 return UpdateState(node, state);
299 }
300
ComputeLoopState(Node * node,AbstractState const * state) const301 CsaLoadElimination::AbstractState const* CsaLoadElimination::ComputeLoopState(
302 Node* node, AbstractState const* state) const {
303 DCHECK_EQ(node->opcode(), IrOpcode::kEffectPhi);
304 Node* const control = NodeProperties::GetControlInput(node);
305 ZoneQueue<Node*> queue(zone());
306 ZoneSet<Node*> visited(zone());
307 visited.insert(node);
308 for (int i = 1; i < control->InputCount(); ++i) {
309 queue.push(node->InputAt(i));
310 }
311 while (!queue.empty()) {
312 Node* const current = queue.front();
313 queue.pop();
314 if (visited.insert(current).second) {
315 if (!current->op()->HasProperty(Operator::kNoWrite)) {
316 return empty_state();
317 }
318 for (int i = 0; i < current->op()->EffectInputCount(); ++i) {
319 queue.push(NodeProperties::GetEffectInput(current, i));
320 }
321 }
322 }
323 return state;
324 }
325
common() const326 CommonOperatorBuilder* CsaLoadElimination::common() const {
327 return jsgraph()->common();
328 }
329
graph() const330 Graph* CsaLoadElimination::graph() const { return jsgraph()->graph(); }
331
isolate() const332 Isolate* CsaLoadElimination::isolate() const { return jsgraph()->isolate(); }
333
334 } // namespace compiler
335 } // namespace internal
336 } // namespace v8
337