1 // Copyright 2014 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/simplified-lowering.h"
6
7 #include <limits>
8
9 #include "src/base/bits.h"
10 #include "src/code-factory.h"
11 #include "src/compiler/common-operator.h"
12 #include "src/compiler/diamond.h"
13 #include "src/compiler/linkage.h"
14 #include "src/compiler/node-matchers.h"
15 #include "src/compiler/node-properties.h"
16 #include "src/compiler/operator-properties.h"
17 #include "src/compiler/representation-change.h"
18 #include "src/compiler/simplified-operator.h"
19 #include "src/compiler/source-position.h"
20 #include "src/objects.h"
21 #include "src/type-cache.h"
22
23 namespace v8 {
24 namespace internal {
25 namespace compiler {
26
27 // Macro for outputting trace information from representation inference.
28 #define TRACE(...) \
29 do { \
30 if (FLAG_trace_representation) PrintF(__VA_ARGS__); \
31 } while (false)
32
33 // Representation selection and lowering of {Simplified} operators to machine
34 // operators are interwined. We use a fixpoint calculation to compute both the
35 // output representation and the best possible lowering for {Simplified} nodes.
36 // Representation change insertion ensures that all values are in the correct
37 // machine representation after this phase, as dictated by the machine
38 // operators themselves.
39 enum Phase {
40 // 1.) PROPAGATE: Traverse the graph from the end, pushing usage information
41 // backwards from uses to definitions, around cycles in phis, according
42 // to local rules for each operator.
43 // During this phase, the usage information for a node determines the best
44 // possible lowering for each operator so far, and that in turn determines
45 // the output representation.
46 // Therefore, to be correct, this phase must iterate to a fixpoint before
47 // the next phase can begin.
48 PROPAGATE,
49
50 // 2.) LOWER: perform lowering for all {Simplified} nodes by replacing some
51 // operators for some nodes, expanding some nodes to multiple nodes, or
52 // removing some (redundant) nodes.
53 // During this phase, use the {RepresentationChanger} to insert
54 // representation changes between uses that demand a particular
55 // representation and nodes that produce a different representation.
56 LOWER
57 };
58
59
60 namespace {
61
62 // The {UseInfo} class is used to describe a use of an input of a node.
63 //
64 // This information is used in two different ways, based on the phase:
65 //
66 // 1. During propagation, the use info is used to inform the input node
67 // about what part of the input is used (we call this truncation) and what
68 // is the preferred representation.
69 //
70 // 2. During lowering, the use info is used to properly convert the input
71 // to the preferred representation. The preferred representation might be
72 // insufficient to do the conversion (e.g. word32->float64 conv), so we also
73 // need the signedness information to produce the correct value.
74 class UseInfo {
75 public:
UseInfo(MachineRepresentation preferred,Truncation truncation)76 UseInfo(MachineRepresentation preferred, Truncation truncation)
77 : preferred_(preferred), truncation_(truncation) {}
TruncatingWord32()78 static UseInfo TruncatingWord32() {
79 return UseInfo(MachineRepresentation::kWord32, Truncation::Word32());
80 }
TruncatingWord64()81 static UseInfo TruncatingWord64() {
82 return UseInfo(MachineRepresentation::kWord64, Truncation::Word64());
83 }
Bool()84 static UseInfo Bool() {
85 return UseInfo(MachineRepresentation::kBit, Truncation::Bool());
86 }
Float32()87 static UseInfo Float32() {
88 return UseInfo(MachineRepresentation::kFloat32, Truncation::Float32());
89 }
Float64()90 static UseInfo Float64() {
91 return UseInfo(MachineRepresentation::kFloat64, Truncation::Float64());
92 }
PointerInt()93 static UseInfo PointerInt() {
94 return kPointerSize == 4 ? TruncatingWord32() : TruncatingWord64();
95 }
AnyTagged()96 static UseInfo AnyTagged() {
97 return UseInfo(MachineRepresentation::kTagged, Truncation::Any());
98 }
99
100 // Undetermined representation.
Any()101 static UseInfo Any() {
102 return UseInfo(MachineRepresentation::kNone, Truncation::Any());
103 }
None()104 static UseInfo None() {
105 return UseInfo(MachineRepresentation::kNone, Truncation::None());
106 }
107
108 // Truncation to a representation that is smaller than the preferred
109 // one.
Float64TruncatingToWord32()110 static UseInfo Float64TruncatingToWord32() {
111 return UseInfo(MachineRepresentation::kFloat64, Truncation::Word32());
112 }
Word64TruncatingToWord32()113 static UseInfo Word64TruncatingToWord32() {
114 return UseInfo(MachineRepresentation::kWord64, Truncation::Word32());
115 }
AnyTruncatingToBool()116 static UseInfo AnyTruncatingToBool() {
117 return UseInfo(MachineRepresentation::kNone, Truncation::Bool());
118 }
119
preferred() const120 MachineRepresentation preferred() const { return preferred_; }
truncation() const121 Truncation truncation() const { return truncation_; }
122
123 private:
124 MachineRepresentation preferred_;
125 Truncation truncation_;
126 };
127
128
TruncatingUseInfoFromRepresentation(MachineRepresentation rep)129 UseInfo TruncatingUseInfoFromRepresentation(MachineRepresentation rep) {
130 switch (rep) {
131 case MachineRepresentation::kTagged:
132 return UseInfo::AnyTagged();
133 case MachineRepresentation::kFloat64:
134 return UseInfo::Float64();
135 case MachineRepresentation::kFloat32:
136 return UseInfo::Float32();
137 case MachineRepresentation::kWord64:
138 return UseInfo::TruncatingWord64();
139 case MachineRepresentation::kWord8:
140 case MachineRepresentation::kWord16:
141 case MachineRepresentation::kWord32:
142 return UseInfo::TruncatingWord32();
143 case MachineRepresentation::kBit:
144 return UseInfo::Bool();
145 case MachineRepresentation::kNone:
146 break;
147 }
148 UNREACHABLE();
149 return UseInfo::None();
150 }
151
152
UseInfoForBasePointer(const FieldAccess & access)153 UseInfo UseInfoForBasePointer(const FieldAccess& access) {
154 return access.tag() != 0 ? UseInfo::AnyTagged() : UseInfo::PointerInt();
155 }
156
157
UseInfoForBasePointer(const ElementAccess & access)158 UseInfo UseInfoForBasePointer(const ElementAccess& access) {
159 return access.tag() != 0 ? UseInfo::AnyTagged() : UseInfo::PointerInt();
160 }
161
162
163 #ifdef DEBUG
164 // Helpers for monotonicity checking.
MachineRepresentationIsSubtype(MachineRepresentation r1,MachineRepresentation r2)165 bool MachineRepresentationIsSubtype(MachineRepresentation r1,
166 MachineRepresentation r2) {
167 switch (r1) {
168 case MachineRepresentation::kNone:
169 return true;
170 case MachineRepresentation::kBit:
171 return r2 == MachineRepresentation::kBit ||
172 r2 == MachineRepresentation::kTagged;
173 case MachineRepresentation::kWord8:
174 return r2 == MachineRepresentation::kWord8 ||
175 r2 == MachineRepresentation::kWord16 ||
176 r2 == MachineRepresentation::kWord32 ||
177 r2 == MachineRepresentation::kWord64 ||
178 r2 == MachineRepresentation::kFloat32 ||
179 r2 == MachineRepresentation::kFloat64 ||
180 r2 == MachineRepresentation::kTagged;
181 case MachineRepresentation::kWord16:
182 return r2 == MachineRepresentation::kWord16 ||
183 r2 == MachineRepresentation::kWord32 ||
184 r2 == MachineRepresentation::kWord64 ||
185 r2 == MachineRepresentation::kFloat32 ||
186 r2 == MachineRepresentation::kFloat64 ||
187 r2 == MachineRepresentation::kTagged;
188 case MachineRepresentation::kWord32:
189 return r2 == MachineRepresentation::kWord32 ||
190 r2 == MachineRepresentation::kWord64 ||
191 r2 == MachineRepresentation::kFloat64 ||
192 r2 == MachineRepresentation::kTagged;
193 case MachineRepresentation::kWord64:
194 return r2 == MachineRepresentation::kWord64;
195 case MachineRepresentation::kFloat32:
196 return r2 == MachineRepresentation::kFloat32 ||
197 r2 == MachineRepresentation::kFloat64 ||
198 r2 == MachineRepresentation::kTagged;
199 case MachineRepresentation::kFloat64:
200 return r2 == MachineRepresentation::kFloat64 ||
201 r2 == MachineRepresentation::kTagged;
202 case MachineRepresentation::kTagged:
203 return r2 == MachineRepresentation::kTagged;
204 }
205 UNREACHABLE();
206 return false;
207 }
208
209
210 class InputUseInfos {
211 public:
InputUseInfos(Zone * zone)212 explicit InputUseInfos(Zone* zone) : input_use_infos_(zone) {}
213
SetAndCheckInput(Node * node,int index,UseInfo use_info)214 void SetAndCheckInput(Node* node, int index, UseInfo use_info) {
215 if (input_use_infos_.empty()) {
216 input_use_infos_.resize(node->InputCount(), UseInfo::None());
217 }
218 // Check that the new use informatin is a super-type of the old
219 // one.
220 CHECK(IsUseLessGeneral(input_use_infos_[index], use_info));
221 input_use_infos_[index] = use_info;
222 }
223
224 private:
225 ZoneVector<UseInfo> input_use_infos_;
226
IsUseLessGeneral(UseInfo use1,UseInfo use2)227 static bool IsUseLessGeneral(UseInfo use1, UseInfo use2) {
228 return MachineRepresentationIsSubtype(use1.preferred(), use2.preferred()) &&
229 use1.truncation().IsLessGeneralThan(use2.truncation());
230 }
231 };
232
233 #endif // DEBUG
234
235 } // namespace
236
237
238 class RepresentationSelector {
239 public:
240 // Information for each node tracked during the fixpoint.
241 class NodeOutputInfo {
242 public:
NodeOutputInfo(MachineRepresentation representation,Type * type)243 NodeOutputInfo(MachineRepresentation representation, Type* type)
244 : type_(type), representation_(representation) {}
NodeOutputInfo()245 NodeOutputInfo()
246 : type_(Type::None()), representation_(MachineRepresentation::kNone) {}
247
representation() const248 MachineRepresentation representation() const { return representation_; }
type() const249 Type* type() const { return type_; }
250
None()251 static NodeOutputInfo None() {
252 return NodeOutputInfo(MachineRepresentation::kNone, Type::None());
253 }
254
Float32()255 static NodeOutputInfo Float32() {
256 return NodeOutputInfo(MachineRepresentation::kFloat32, Type::Number());
257 }
258
Float64()259 static NodeOutputInfo Float64() {
260 return NodeOutputInfo(MachineRepresentation::kFloat64, Type::Number());
261 }
262
NumberTruncatedToWord32()263 static NodeOutputInfo NumberTruncatedToWord32() {
264 return NodeOutputInfo(MachineRepresentation::kWord32, Type::Number());
265 }
266
Int32()267 static NodeOutputInfo Int32() {
268 return NodeOutputInfo(MachineRepresentation::kWord32, Type::Signed32());
269 }
270
Uint32()271 static NodeOutputInfo Uint32() {
272 return NodeOutputInfo(MachineRepresentation::kWord32, Type::Unsigned32());
273 }
274
Bool()275 static NodeOutputInfo Bool() {
276 return NodeOutputInfo(MachineRepresentation::kBit, Type::Boolean());
277 }
278
Int64()279 static NodeOutputInfo Int64() {
280 // TODO(jarin) Fix once we have a real int64 type.
281 return NodeOutputInfo(MachineRepresentation::kWord64, Type::Internal());
282 }
283
Uint64()284 static NodeOutputInfo Uint64() {
285 // TODO(jarin) Fix once we have a real uint64 type.
286 return NodeOutputInfo(MachineRepresentation::kWord64, Type::Internal());
287 }
288
AnyTagged()289 static NodeOutputInfo AnyTagged() {
290 return NodeOutputInfo(MachineRepresentation::kTagged, Type::Any());
291 }
292
NumberTagged()293 static NodeOutputInfo NumberTagged() {
294 return NodeOutputInfo(MachineRepresentation::kTagged, Type::Number());
295 }
296
Pointer()297 static NodeOutputInfo Pointer() {
298 return NodeOutputInfo(MachineType::PointerRepresentation(), Type::Any());
299 }
300
301 private:
302 Type* type_;
303 MachineRepresentation representation_;
304 };
305
306 class NodeInfo {
307 public:
308 // Adds new use to the node. Returns true if something has changed
309 // and the node has to be requeued.
AddUse(UseInfo info)310 bool AddUse(UseInfo info) {
311 Truncation old_truncation = truncation_;
312 truncation_ = Truncation::Generalize(truncation_, info.truncation());
313 return truncation_ != old_truncation;
314 }
315
set_queued(bool value)316 void set_queued(bool value) { queued_ = value; }
queued() const317 bool queued() const { return queued_; }
set_visited()318 void set_visited() { visited_ = true; }
visited() const319 bool visited() const { return visited_; }
truncation() const320 Truncation truncation() const { return truncation_; }
set_output_type(NodeOutputInfo output)321 void set_output_type(NodeOutputInfo output) { output_ = output; }
322
output_type() const323 Type* output_type() const { return output_.type(); }
representation() const324 MachineRepresentation representation() const {
325 return output_.representation();
326 }
327
328 private:
329 bool queued_ = false; // Bookkeeping for the traversal.
330 bool visited_ = false; // Bookkeeping for the traversal.
331 NodeOutputInfo output_; // Output type and representation.
332 Truncation truncation_ = Truncation::None(); // Information about uses.
333 };
334
RepresentationSelector(JSGraph * jsgraph,Zone * zone,RepresentationChanger * changer,SourcePositionTable * source_positions)335 RepresentationSelector(JSGraph* jsgraph, Zone* zone,
336 RepresentationChanger* changer,
337 SourcePositionTable* source_positions)
338 : jsgraph_(jsgraph),
339 count_(jsgraph->graph()->NodeCount()),
340 info_(count_, zone),
341 #ifdef DEBUG
342 node_input_use_infos_(count_, InputUseInfos(zone), zone),
343 #endif
344 nodes_(zone),
345 replacements_(zone),
346 phase_(PROPAGATE),
347 changer_(changer),
348 queue_(zone),
349 source_positions_(source_positions),
350 type_cache_(TypeCache::Get()) {
351 }
352
Run(SimplifiedLowering * lowering)353 void Run(SimplifiedLowering* lowering) {
354 // Run propagation phase to a fixpoint.
355 TRACE("--{Propagation phase}--\n");
356 phase_ = PROPAGATE;
357 EnqueueInitial(jsgraph_->graph()->end());
358 // Process nodes from the queue until it is empty.
359 while (!queue_.empty()) {
360 Node* node = queue_.front();
361 NodeInfo* info = GetInfo(node);
362 queue_.pop();
363 info->set_queued(false);
364 TRACE(" visit #%d: %s\n", node->id(), node->op()->mnemonic());
365 VisitNode(node, info->truncation(), nullptr);
366 TRACE(" ==> output ");
367 PrintOutputInfo(info);
368 TRACE("\n");
369 }
370
371 // Run lowering and change insertion phase.
372 TRACE("--{Simplified lowering phase}--\n");
373 phase_ = LOWER;
374 // Process nodes from the collected {nodes_} vector.
375 for (NodeVector::iterator i = nodes_.begin(); i != nodes_.end(); ++i) {
376 Node* node = *i;
377 NodeInfo* info = GetInfo(node);
378 TRACE(" visit #%d: %s\n", node->id(), node->op()->mnemonic());
379 // Reuse {VisitNode()} so the representation rules are in one place.
380 SourcePositionTable::Scope scope(
381 source_positions_, source_positions_->GetSourcePosition(node));
382 VisitNode(node, info->truncation(), lowering);
383 }
384
385 // Perform the final replacements.
386 for (NodeVector::iterator i = replacements_.begin();
387 i != replacements_.end(); ++i) {
388 Node* node = *i;
389 Node* replacement = *(++i);
390 node->ReplaceUses(replacement);
391 // We also need to replace the node in the rest of the vector.
392 for (NodeVector::iterator j = i + 1; j != replacements_.end(); ++j) {
393 ++j;
394 if (*j == node) *j = replacement;
395 }
396 }
397 }
398
EnqueueInitial(Node * node)399 void EnqueueInitial(Node* node) {
400 NodeInfo* info = GetInfo(node);
401 info->set_visited();
402 info->set_queued(true);
403 nodes_.push_back(node);
404 queue_.push(node);
405 }
406
407 // Enqueue {use_node}'s {index} input if the {use} contains new information
408 // for that input node. Add the input to {nodes_} if this is the first time
409 // it's been visited.
EnqueueInput(Node * use_node,int index,UseInfo use_info=UseInfo::None ())410 void EnqueueInput(Node* use_node, int index,
411 UseInfo use_info = UseInfo::None()) {
412 Node* node = use_node->InputAt(index);
413 if (phase_ != PROPAGATE) return;
414 NodeInfo* info = GetInfo(node);
415 #ifdef DEBUG
416 // Check monotonicity of input requirements.
417 node_input_use_infos_[use_node->id()].SetAndCheckInput(use_node, index,
418 use_info);
419 #endif // DEBUG
420 if (!info->visited()) {
421 // First visit of this node.
422 info->set_visited();
423 info->set_queued(true);
424 nodes_.push_back(node);
425 queue_.push(node);
426 TRACE(" initial: ");
427 info->AddUse(use_info);
428 PrintTruncation(info->truncation());
429 return;
430 }
431 TRACE(" queue?: ");
432 PrintTruncation(info->truncation());
433 if (info->AddUse(use_info)) {
434 // New usage information for the node is available.
435 if (!info->queued()) {
436 queue_.push(node);
437 info->set_queued(true);
438 TRACE(" added: ");
439 } else {
440 TRACE(" inqueue: ");
441 }
442 PrintTruncation(info->truncation());
443 }
444 }
445
lower()446 bool lower() { return phase_ == LOWER; }
447
EnqueueUses(Node * node)448 void EnqueueUses(Node* node) {
449 for (Edge edge : node->use_edges()) {
450 if (NodeProperties::IsValueEdge(edge)) {
451 Node* const user = edge.from();
452 if (user->id() < count_) {
453 // New type information for the node is available.
454 NodeInfo* info = GetInfo(user);
455 // Enqueue the node only if we are sure it is reachable from
456 // the end and it has not been queued yet.
457 if (info->visited() && !info->queued()) {
458 queue_.push(user);
459 info->set_queued(true);
460 }
461 }
462 }
463 }
464 }
465
SetOutputFromMachineType(Node * node,MachineType machine_type)466 void SetOutputFromMachineType(Node* node, MachineType machine_type) {
467 Type* type = Type::None();
468 switch (machine_type.semantic()) {
469 case MachineSemantic::kNone:
470 type = Type::None();
471 break;
472 case MachineSemantic::kBool:
473 type = Type::Boolean();
474 break;
475 case MachineSemantic::kInt32:
476 type = Type::Signed32();
477 break;
478 case MachineSemantic::kUint32:
479 type = Type::Unsigned32();
480 break;
481 case MachineSemantic::kInt64:
482 // TODO(jarin) Fix once we have proper int64.
483 type = Type::Internal();
484 break;
485 case MachineSemantic::kUint64:
486 // TODO(jarin) Fix once we have proper uint64.
487 type = Type::Internal();
488 break;
489 case MachineSemantic::kNumber:
490 type = Type::Number();
491 break;
492 case MachineSemantic::kAny:
493 type = Type::Any();
494 break;
495 }
496 return SetOutput(node, NodeOutputInfo(machine_type.representation(), type));
497 }
498
SetOutput(Node * node,NodeOutputInfo output_info)499 void SetOutput(Node* node, NodeOutputInfo output_info) {
500 // Every node should have at most one output representation. Note that
501 // phis can have 0, if they have not been used in a representation-inducing
502 // instruction.
503 Type* output_type = output_info.type();
504 if (NodeProperties::IsTyped(node)) {
505 output_type = Type::Intersect(NodeProperties::GetType(node),
506 output_info.type(), jsgraph_->zone());
507 }
508 NodeInfo* info = GetInfo(node);
509 DCHECK(info->output_type()->Is(output_type));
510 DCHECK(MachineRepresentationIsSubtype(info->representation(),
511 output_info.representation()));
512 if (!output_type->Is(info->output_type()) ||
513 output_info.representation() != info->representation()) {
514 EnqueueUses(node);
515 }
516 info->set_output_type(
517 NodeOutputInfo(output_info.representation(), output_type));
518 }
519
BothInputsAreSigned32(Node * node)520 bool BothInputsAreSigned32(Node* node) {
521 DCHECK_EQ(2, node->InputCount());
522 return GetInfo(node->InputAt(0))->output_type()->Is(Type::Signed32()) &&
523 GetInfo(node->InputAt(1))->output_type()->Is(Type::Signed32());
524 }
525
BothInputsAreUnsigned32(Node * node)526 bool BothInputsAreUnsigned32(Node* node) {
527 DCHECK_EQ(2, node->InputCount());
528 return GetInfo(node->InputAt(0))->output_type()->Is(Type::Unsigned32()) &&
529 GetInfo(node->InputAt(1))->output_type()->Is(Type::Unsigned32());
530 }
531
BothInputsAre(Node * node,Type * type)532 bool BothInputsAre(Node* node, Type* type) {
533 DCHECK_EQ(2, node->InputCount());
534 return GetInfo(node->InputAt(0))->output_type()->Is(type) &&
535 GetInfo(node->InputAt(1))->output_type()->Is(type);
536 }
537
ConvertInput(Node * node,int index,UseInfo use)538 void ConvertInput(Node* node, int index, UseInfo use) {
539 Node* input = node->InputAt(index);
540 // In the change phase, insert a change before the use if necessary.
541 if (use.preferred() == MachineRepresentation::kNone)
542 return; // No input requirement on the use.
543 NodeInfo* input_info = GetInfo(input);
544 MachineRepresentation input_rep = input_info->representation();
545 if (input_rep != use.preferred()) {
546 // Output representation doesn't match usage.
547 TRACE(" change: #%d:%s(@%d #%d:%s) ", node->id(), node->op()->mnemonic(),
548 index, input->id(), input->op()->mnemonic());
549 TRACE(" from ");
550 PrintOutputInfo(input_info);
551 TRACE(" to ");
552 PrintUseInfo(use);
553 TRACE("\n");
554 Node* n = changer_->GetRepresentationFor(
555 input, input_info->representation(), input_info->output_type(),
556 use.preferred(), use.truncation());
557 node->ReplaceInput(index, n);
558 }
559 }
560
ProcessInput(Node * node,int index,UseInfo use)561 void ProcessInput(Node* node, int index, UseInfo use) {
562 if (phase_ == PROPAGATE) {
563 EnqueueInput(node, index, use);
564 } else {
565 ConvertInput(node, index, use);
566 }
567 }
568
ProcessRemainingInputs(Node * node,int index)569 void ProcessRemainingInputs(Node* node, int index) {
570 DCHECK_GE(index, NodeProperties::PastValueIndex(node));
571 DCHECK_GE(index, NodeProperties::PastContextIndex(node));
572 for (int i = std::max(index, NodeProperties::FirstEffectIndex(node));
573 i < NodeProperties::PastEffectIndex(node); ++i) {
574 EnqueueInput(node, i); // Effect inputs: just visit
575 }
576 for (int i = std::max(index, NodeProperties::FirstControlIndex(node));
577 i < NodeProperties::PastControlIndex(node); ++i) {
578 EnqueueInput(node, i); // Control inputs: just visit
579 }
580 }
581
582 // The default, most general visitation case. For {node}, process all value,
583 // context, frame state, effect, and control inputs, assuming that value
584 // inputs should have {kRepTagged} representation and can observe all output
585 // values {kTypeAny}.
VisitInputs(Node * node)586 void VisitInputs(Node* node) {
587 int tagged_count = node->op()->ValueInputCount() +
588 OperatorProperties::GetContextInputCount(node->op());
589 // Visit value and context inputs as tagged.
590 for (int i = 0; i < tagged_count; i++) {
591 ProcessInput(node, i, UseInfo::AnyTagged());
592 }
593 // Only enqueue other inputs (framestates, effects, control).
594 for (int i = tagged_count; i < node->InputCount(); i++) {
595 EnqueueInput(node, i);
596 }
597 }
598
599 // Helper for binops of the R x L -> O variety.
VisitBinop(Node * node,UseInfo left_use,UseInfo right_use,NodeOutputInfo output)600 void VisitBinop(Node* node, UseInfo left_use, UseInfo right_use,
601 NodeOutputInfo output) {
602 DCHECK_EQ(2, node->op()->ValueInputCount());
603 ProcessInput(node, 0, left_use);
604 ProcessInput(node, 1, right_use);
605 for (int i = 2; i < node->InputCount(); i++) {
606 EnqueueInput(node, i);
607 }
608 SetOutput(node, output);
609 }
610
611 // Helper for binops of the I x I -> O variety.
VisitBinop(Node * node,UseInfo input_use,NodeOutputInfo output)612 void VisitBinop(Node* node, UseInfo input_use, NodeOutputInfo output) {
613 VisitBinop(node, input_use, input_use, output);
614 }
615
616 // Helper for unops of the I -> O variety.
VisitUnop(Node * node,UseInfo input_use,NodeOutputInfo output)617 void VisitUnop(Node* node, UseInfo input_use, NodeOutputInfo output) {
618 DCHECK_EQ(1, node->InputCount());
619 ProcessInput(node, 0, input_use);
620 SetOutput(node, output);
621 }
622
623 // Helper for leaf nodes.
VisitLeaf(Node * node,NodeOutputInfo output)624 void VisitLeaf(Node* node, NodeOutputInfo output) {
625 DCHECK_EQ(0, node->InputCount());
626 SetOutput(node, output);
627 }
628
629 // Helpers for specific types of binops.
VisitFloat64Binop(Node * node)630 void VisitFloat64Binop(Node* node) {
631 VisitBinop(node, UseInfo::Float64(), NodeOutputInfo::Float64());
632 }
VisitInt32Binop(Node * node)633 void VisitInt32Binop(Node* node) {
634 VisitBinop(node, UseInfo::TruncatingWord32(), NodeOutputInfo::Int32());
635 }
VisitWord32TruncatingBinop(Node * node)636 void VisitWord32TruncatingBinop(Node* node) {
637 VisitBinop(node, UseInfo::TruncatingWord32(),
638 NodeOutputInfo::NumberTruncatedToWord32());
639 }
VisitUint32Binop(Node * node)640 void VisitUint32Binop(Node* node) {
641 VisitBinop(node, UseInfo::TruncatingWord32(), NodeOutputInfo::Uint32());
642 }
VisitInt64Binop(Node * node)643 void VisitInt64Binop(Node* node) {
644 VisitBinop(node, UseInfo::TruncatingWord64(), NodeOutputInfo::Int64());
645 }
VisitUint64Binop(Node * node)646 void VisitUint64Binop(Node* node) {
647 VisitBinop(node, UseInfo::TruncatingWord64(), NodeOutputInfo::Uint64());
648 }
VisitFloat64Cmp(Node * node)649 void VisitFloat64Cmp(Node* node) {
650 VisitBinop(node, UseInfo::Float64(), NodeOutputInfo::Bool());
651 }
VisitInt32Cmp(Node * node)652 void VisitInt32Cmp(Node* node) {
653 VisitBinop(node, UseInfo::TruncatingWord32(), NodeOutputInfo::Bool());
654 }
VisitUint32Cmp(Node * node)655 void VisitUint32Cmp(Node* node) {
656 VisitBinop(node, UseInfo::TruncatingWord32(), NodeOutputInfo::Bool());
657 }
VisitInt64Cmp(Node * node)658 void VisitInt64Cmp(Node* node) {
659 VisitBinop(node, UseInfo::TruncatingWord64(), NodeOutputInfo::Bool());
660 }
VisitUint64Cmp(Node * node)661 void VisitUint64Cmp(Node* node) {
662 VisitBinop(node, UseInfo::TruncatingWord64(), NodeOutputInfo::Bool());
663 }
664
665 // Infer representation for phi-like nodes.
GetOutputInfoForPhi(Node * node,Truncation use)666 NodeOutputInfo GetOutputInfoForPhi(Node* node, Truncation use) {
667 // Compute the type.
668 Type* type = GetInfo(node->InputAt(0))->output_type();
669 for (int i = 1; i < node->op()->ValueInputCount(); ++i) {
670 type = Type::Union(type, GetInfo(node->InputAt(i))->output_type(),
671 jsgraph_->zone());
672 }
673
674 // Compute the representation.
675 MachineRepresentation rep = MachineRepresentation::kTagged;
676 if (type->Is(Type::None())) {
677 rep = MachineRepresentation::kNone;
678 } else if (type->Is(Type::Signed32()) || type->Is(Type::Unsigned32())) {
679 rep = MachineRepresentation::kWord32;
680 } else if (use.TruncatesToWord32()) {
681 rep = MachineRepresentation::kWord32;
682 } else if (type->Is(Type::Boolean())) {
683 rep = MachineRepresentation::kBit;
684 } else if (type->Is(Type::Number())) {
685 rep = MachineRepresentation::kFloat64;
686 } else if (type->Is(Type::Internal())) {
687 // We mark (u)int64 as Type::Internal.
688 // TODO(jarin) This is a workaround for our lack of (u)int64
689 // types. This can be removed once we can represent (u)int64
690 // unambiguously. (At the moment internal objects, such as the hole,
691 // are also Type::Internal()).
692 bool is_word64 = GetInfo(node->InputAt(0))->representation() ==
693 MachineRepresentation::kWord64;
694 #ifdef DEBUG
695 // Check that all the inputs agree on being Word64.
696 for (int i = 1; i < node->op()->ValueInputCount(); i++) {
697 DCHECK_EQ(is_word64, GetInfo(node->InputAt(i))->representation() ==
698 MachineRepresentation::kWord64);
699 }
700 #endif
701 rep = is_word64 ? MachineRepresentation::kWord64
702 : MachineRepresentation::kTagged;
703 }
704 return NodeOutputInfo(rep, type);
705 }
706
707 // Helper for handling selects.
VisitSelect(Node * node,Truncation truncation,SimplifiedLowering * lowering)708 void VisitSelect(Node* node, Truncation truncation,
709 SimplifiedLowering* lowering) {
710 ProcessInput(node, 0, UseInfo::Bool());
711
712 NodeOutputInfo output = GetOutputInfoForPhi(node, truncation);
713 SetOutput(node, output);
714
715 if (lower()) {
716 // Update the select operator.
717 SelectParameters p = SelectParametersOf(node->op());
718 if (output.representation() != p.representation()) {
719 NodeProperties::ChangeOp(node, lowering->common()->Select(
720 output.representation(), p.hint()));
721 }
722 }
723 // Convert inputs to the output representation of this phi, pass the
724 // truncation truncation along.
725 UseInfo input_use(output.representation(), truncation);
726 ProcessInput(node, 1, input_use);
727 ProcessInput(node, 2, input_use);
728 }
729
730 // Helper for handling phis.
VisitPhi(Node * node,Truncation truncation,SimplifiedLowering * lowering)731 void VisitPhi(Node* node, Truncation truncation,
732 SimplifiedLowering* lowering) {
733 NodeOutputInfo output = GetOutputInfoForPhi(node, truncation);
734 SetOutput(node, output);
735
736 int values = node->op()->ValueInputCount();
737 if (lower()) {
738 // Update the phi operator.
739 if (output.representation() != PhiRepresentationOf(node->op())) {
740 NodeProperties::ChangeOp(
741 node, lowering->common()->Phi(output.representation(), values));
742 }
743 }
744
745 // Convert inputs to the output representation of this phi, pass the
746 // truncation truncation along.
747 UseInfo input_use(output.representation(), truncation);
748 for (int i = 0; i < node->InputCount(); i++) {
749 ProcessInput(node, i, i < values ? input_use : UseInfo::None());
750 }
751 }
752
VisitCall(Node * node,SimplifiedLowering * lowering)753 void VisitCall(Node* node, SimplifiedLowering* lowering) {
754 const CallDescriptor* desc = OpParameter<const CallDescriptor*>(node->op());
755 const MachineSignature* sig = desc->GetMachineSignature();
756 int params = static_cast<int>(sig->parameter_count());
757 // Propagate representation information from call descriptor.
758 for (int i = 0; i < node->InputCount(); i++) {
759 if (i == 0) {
760 // The target of the call.
761 ProcessInput(node, i, UseInfo::None());
762 } else if ((i - 1) < params) {
763 ProcessInput(node, i, TruncatingUseInfoFromRepresentation(
764 sig->GetParam(i - 1).representation()));
765 } else {
766 ProcessInput(node, i, UseInfo::None());
767 }
768 }
769
770 if (sig->return_count() > 0) {
771 SetOutputFromMachineType(node, desc->GetMachineSignature()->GetReturn());
772 } else {
773 SetOutput(node, NodeOutputInfo::AnyTagged());
774 }
775 }
776
DeoptValueSemanticOf(Type * type)777 MachineSemantic DeoptValueSemanticOf(Type* type) {
778 CHECK(!type->Is(Type::None()));
779 // We only need signedness to do deopt correctly.
780 if (type->Is(Type::Signed32())) {
781 return MachineSemantic::kInt32;
782 } else if (type->Is(Type::Unsigned32())) {
783 return MachineSemantic::kUint32;
784 } else {
785 return MachineSemantic::kAny;
786 }
787 }
788
VisitStateValues(Node * node)789 void VisitStateValues(Node* node) {
790 if (phase_ == PROPAGATE) {
791 for (int i = 0; i < node->InputCount(); i++) {
792 EnqueueInput(node, i, UseInfo::Any());
793 }
794 } else {
795 Zone* zone = jsgraph_->zone();
796 ZoneVector<MachineType>* types =
797 new (zone->New(sizeof(ZoneVector<MachineType>)))
798 ZoneVector<MachineType>(node->InputCount(), zone);
799 for (int i = 0; i < node->InputCount(); i++) {
800 NodeInfo* input_info = GetInfo(node->InputAt(i));
801 MachineType machine_type(
802 input_info->representation(),
803 DeoptValueSemanticOf(input_info->output_type()));
804 DCHECK(machine_type.representation() !=
805 MachineRepresentation::kWord32 ||
806 machine_type.semantic() == MachineSemantic::kInt32 ||
807 machine_type.semantic() == MachineSemantic::kUint32);
808 (*types)[i] = machine_type;
809 }
810 NodeProperties::ChangeOp(node,
811 jsgraph_->common()->TypedStateValues(types));
812 }
813 SetOutput(node, NodeOutputInfo::AnyTagged());
814 }
815
Int32Op(Node * node)816 const Operator* Int32Op(Node* node) {
817 return changer_->Int32OperatorFor(node->opcode());
818 }
819
Uint32Op(Node * node)820 const Operator* Uint32Op(Node* node) {
821 return changer_->Uint32OperatorFor(node->opcode());
822 }
823
Float64Op(Node * node)824 const Operator* Float64Op(Node* node) {
825 return changer_->Float64OperatorFor(node->opcode());
826 }
827
828 // Dispatching routine for visiting the node {node} with the usage {use}.
829 // Depending on the operator, propagate new usage info to the inputs.
VisitNode(Node * node,Truncation truncation,SimplifiedLowering * lowering)830 void VisitNode(Node* node, Truncation truncation,
831 SimplifiedLowering* lowering) {
832 switch (node->opcode()) {
833 //------------------------------------------------------------------
834 // Common operators.
835 //------------------------------------------------------------------
836 case IrOpcode::kStart:
837 case IrOpcode::kDead:
838 return VisitLeaf(node, NodeOutputInfo::None());
839 case IrOpcode::kParameter: {
840 // TODO(titzer): use representation from linkage.
841 Type* type = NodeProperties::GetType(node);
842 ProcessInput(node, 0, UseInfo::None());
843 SetOutput(node, NodeOutputInfo(MachineRepresentation::kTagged, type));
844 return;
845 }
846 case IrOpcode::kInt32Constant:
847 return VisitLeaf(node, NodeOutputInfo::Int32());
848 case IrOpcode::kInt64Constant:
849 return VisitLeaf(node, NodeOutputInfo::Int64());
850 case IrOpcode::kFloat32Constant:
851 return VisitLeaf(node, NodeOutputInfo::Float32());
852 case IrOpcode::kFloat64Constant:
853 return VisitLeaf(node, NodeOutputInfo::Float64());
854 case IrOpcode::kExternalConstant:
855 return VisitLeaf(node, NodeOutputInfo::Pointer());
856 case IrOpcode::kNumberConstant:
857 return VisitLeaf(node, NodeOutputInfo::NumberTagged());
858 case IrOpcode::kHeapConstant:
859 return VisitLeaf(node, NodeOutputInfo::AnyTagged());
860
861 case IrOpcode::kBranch:
862 ProcessInput(node, 0, UseInfo::Bool());
863 EnqueueInput(node, NodeProperties::FirstControlIndex(node));
864 break;
865 case IrOpcode::kSwitch:
866 ProcessInput(node, 0, UseInfo::TruncatingWord32());
867 EnqueueInput(node, NodeProperties::FirstControlIndex(node));
868 break;
869 case IrOpcode::kSelect:
870 return VisitSelect(node, truncation, lowering);
871 case IrOpcode::kPhi:
872 return VisitPhi(node, truncation, lowering);
873 case IrOpcode::kCall:
874 return VisitCall(node, lowering);
875
876 //------------------------------------------------------------------
877 // JavaScript operators.
878 //------------------------------------------------------------------
879 // For now, we assume that all JS operators were too complex to lower
880 // to Simplified and that they will always require tagged value inputs
881 // and produce tagged value outputs.
882 // TODO(turbofan): it might be possible to lower some JSOperators here,
883 // but that responsibility really lies in the typed lowering phase.
884 #define DEFINE_JS_CASE(x) case IrOpcode::k##x:
885 JS_OP_LIST(DEFINE_JS_CASE)
886 #undef DEFINE_JS_CASE
887 VisitInputs(node);
888 return SetOutput(node, NodeOutputInfo::AnyTagged());
889
890 //------------------------------------------------------------------
891 // Simplified operators.
892 //------------------------------------------------------------------
893 case IrOpcode::kBooleanNot: {
894 if (lower()) {
895 NodeInfo* input_info = GetInfo(node->InputAt(0));
896 if (input_info->representation() == MachineRepresentation::kBit) {
897 // BooleanNot(x: kRepBit) => Word32Equal(x, #0)
898 node->AppendInput(jsgraph_->zone(), jsgraph_->Int32Constant(0));
899 NodeProperties::ChangeOp(node, lowering->machine()->Word32Equal());
900 } else {
901 // BooleanNot(x: kRepTagged) => WordEqual(x, #false)
902 node->AppendInput(jsgraph_->zone(), jsgraph_->FalseConstant());
903 NodeProperties::ChangeOp(node, lowering->machine()->WordEqual());
904 }
905 } else {
906 // No input representation requirement; adapt during lowering.
907 ProcessInput(node, 0, UseInfo::AnyTruncatingToBool());
908 SetOutput(node, NodeOutputInfo::Bool());
909 }
910 break;
911 }
912 case IrOpcode::kBooleanToNumber: {
913 if (lower()) {
914 NodeInfo* input_info = GetInfo(node->InputAt(0));
915 if (input_info->representation() == MachineRepresentation::kBit) {
916 // BooleanToNumber(x: kRepBit) => x
917 DeferReplacement(node, node->InputAt(0));
918 } else {
919 // BooleanToNumber(x: kRepTagged) => WordEqual(x, #true)
920 node->AppendInput(jsgraph_->zone(), jsgraph_->TrueConstant());
921 NodeProperties::ChangeOp(node, lowering->machine()->WordEqual());
922 }
923 } else {
924 // No input representation requirement; adapt during lowering.
925 ProcessInput(node, 0, UseInfo::AnyTruncatingToBool());
926 SetOutput(node, NodeOutputInfo::Int32());
927 }
928 break;
929 }
930 case IrOpcode::kNumberEqual:
931 case IrOpcode::kNumberLessThan:
932 case IrOpcode::kNumberLessThanOrEqual: {
933 // Number comparisons reduce to integer comparisons for integer inputs.
934 if (BothInputsAreSigned32(node)) {
935 // => signed Int32Cmp
936 VisitInt32Cmp(node);
937 if (lower()) NodeProperties::ChangeOp(node, Int32Op(node));
938 } else if (BothInputsAreUnsigned32(node)) {
939 // => unsigned Int32Cmp
940 VisitUint32Cmp(node);
941 if (lower()) NodeProperties::ChangeOp(node, Uint32Op(node));
942 } else {
943 // => Float64Cmp
944 VisitFloat64Cmp(node);
945 if (lower()) NodeProperties::ChangeOp(node, Float64Op(node));
946 }
947 break;
948 }
949 case IrOpcode::kNumberAdd:
950 case IrOpcode::kNumberSubtract: {
951 if (BothInputsAre(node, Type::Signed32()) &&
952 NodeProperties::GetType(node)->Is(Type::Signed32())) {
953 // int32 + int32 = int32
954 // => signed Int32Add/Sub
955 VisitInt32Binop(node);
956 if (lower()) NodeProperties::ChangeOp(node, Int32Op(node));
957 } else if (BothInputsAre(node, type_cache_.kAdditiveSafeInteger) &&
958 truncation.TruncatesToWord32()) {
959 // safe-int + safe-int = x (truncated to int32)
960 // => signed Int32Add/Sub (truncated)
961 VisitWord32TruncatingBinop(node);
962 if (lower()) NodeProperties::ChangeOp(node, Int32Op(node));
963 } else {
964 // => Float64Add/Sub
965 VisitFloat64Binop(node);
966 if (lower()) NodeProperties::ChangeOp(node, Float64Op(node));
967 }
968 break;
969 }
970 case IrOpcode::kNumberMultiply: {
971 if (BothInputsAreSigned32(node)) {
972 if (NodeProperties::GetType(node)->Is(Type::Signed32())) {
973 // Multiply reduces to Int32Mul if the inputs and the output
974 // are integers.
975 VisitInt32Binop(node);
976 if (lower()) NodeProperties::ChangeOp(node, Int32Op(node));
977 break;
978 }
979 if (truncation.TruncatesToWord32() &&
980 NodeProperties::GetType(node)->Is(type_cache_.kSafeInteger)) {
981 // Multiply reduces to Int32Mul if the inputs are integers,
982 // the uses are truncating and the result is in the safe
983 // integer range.
984 VisitWord32TruncatingBinop(node);
985 if (lower()) NodeProperties::ChangeOp(node, Int32Op(node));
986 break;
987 }
988 }
989 // => Float64Mul
990 VisitFloat64Binop(node);
991 if (lower()) NodeProperties::ChangeOp(node, Float64Op(node));
992 break;
993 }
994 case IrOpcode::kNumberDivide: {
995 if (BothInputsAreSigned32(node)) {
996 if (NodeProperties::GetType(node)->Is(Type::Signed32())) {
997 // => signed Int32Div
998 VisitInt32Binop(node);
999 if (lower()) DeferReplacement(node, lowering->Int32Div(node));
1000 break;
1001 }
1002 if (truncation.TruncatesToWord32()) {
1003 // => signed Int32Div
1004 VisitWord32TruncatingBinop(node);
1005 if (lower()) DeferReplacement(node, lowering->Int32Div(node));
1006 break;
1007 }
1008 }
1009 if (BothInputsAreUnsigned32(node) && truncation.TruncatesToWord32()) {
1010 // => unsigned Uint32Div
1011 VisitWord32TruncatingBinop(node);
1012 if (lower()) DeferReplacement(node, lowering->Uint32Div(node));
1013 break;
1014 }
1015 // => Float64Div
1016 VisitFloat64Binop(node);
1017 if (lower()) NodeProperties::ChangeOp(node, Float64Op(node));
1018 break;
1019 }
1020 case IrOpcode::kNumberModulus: {
1021 if (BothInputsAreSigned32(node)) {
1022 if (NodeProperties::GetType(node)->Is(Type::Signed32())) {
1023 // => signed Int32Mod
1024 VisitInt32Binop(node);
1025 if (lower()) DeferReplacement(node, lowering->Int32Mod(node));
1026 break;
1027 }
1028 if (truncation.TruncatesToWord32()) {
1029 // => signed Int32Mod
1030 VisitWord32TruncatingBinop(node);
1031 if (lower()) DeferReplacement(node, lowering->Int32Mod(node));
1032 break;
1033 }
1034 }
1035 if (BothInputsAreUnsigned32(node) && truncation.TruncatesToWord32()) {
1036 // => unsigned Uint32Mod
1037 VisitWord32TruncatingBinop(node);
1038 if (lower()) DeferReplacement(node, lowering->Uint32Mod(node));
1039 break;
1040 }
1041 // => Float64Mod
1042 VisitFloat64Binop(node);
1043 if (lower()) NodeProperties::ChangeOp(node, Float64Op(node));
1044 break;
1045 }
1046 case IrOpcode::kNumberBitwiseOr:
1047 case IrOpcode::kNumberBitwiseXor:
1048 case IrOpcode::kNumberBitwiseAnd: {
1049 VisitInt32Binop(node);
1050 if (lower()) NodeProperties::ChangeOp(node, Int32Op(node));
1051 break;
1052 }
1053 case IrOpcode::kNumberShiftLeft: {
1054 Type* rhs_type = GetInfo(node->InputAt(1))->output_type();
1055 VisitBinop(node, UseInfo::TruncatingWord32(),
1056 UseInfo::TruncatingWord32(), NodeOutputInfo::Int32());
1057 if (lower()) {
1058 lowering->DoShift(node, lowering->machine()->Word32Shl(), rhs_type);
1059 }
1060 break;
1061 }
1062 case IrOpcode::kNumberShiftRight: {
1063 Type* rhs_type = GetInfo(node->InputAt(1))->output_type();
1064 VisitBinop(node, UseInfo::TruncatingWord32(),
1065 UseInfo::TruncatingWord32(), NodeOutputInfo::Int32());
1066 if (lower()) {
1067 lowering->DoShift(node, lowering->machine()->Word32Sar(), rhs_type);
1068 }
1069 break;
1070 }
1071 case IrOpcode::kNumberShiftRightLogical: {
1072 Type* rhs_type = GetInfo(node->InputAt(1))->output_type();
1073 VisitBinop(node, UseInfo::TruncatingWord32(),
1074 UseInfo::TruncatingWord32(), NodeOutputInfo::Uint32());
1075 if (lower()) {
1076 lowering->DoShift(node, lowering->machine()->Word32Shr(), rhs_type);
1077 }
1078 break;
1079 }
1080 case IrOpcode::kNumberToInt32: {
1081 // Just change representation if necessary.
1082 VisitUnop(node, UseInfo::TruncatingWord32(), NodeOutputInfo::Int32());
1083 if (lower()) DeferReplacement(node, node->InputAt(0));
1084 break;
1085 }
1086 case IrOpcode::kNumberToUint32: {
1087 // Just change representation if necessary.
1088 VisitUnop(node, UseInfo::TruncatingWord32(), NodeOutputInfo::Uint32());
1089 if (lower()) DeferReplacement(node, node->InputAt(0));
1090 break;
1091 }
1092 case IrOpcode::kNumberIsHoleNaN: {
1093 VisitUnop(node, UseInfo::Float64(), NodeOutputInfo::Bool());
1094 if (lower()) {
1095 // NumberIsHoleNaN(x) => Word32Equal(Float64ExtractLowWord32(x),
1096 // #HoleNaNLower32)
1097 node->ReplaceInput(0,
1098 jsgraph_->graph()->NewNode(
1099 lowering->machine()->Float64ExtractLowWord32(),
1100 node->InputAt(0)));
1101 node->AppendInput(jsgraph_->zone(),
1102 jsgraph_->Int32Constant(kHoleNanLower32));
1103 NodeProperties::ChangeOp(node, jsgraph_->machine()->Word32Equal());
1104 }
1105 break;
1106 }
1107 case IrOpcode::kPlainPrimitiveToNumber: {
1108 VisitUnop(node, UseInfo::AnyTagged(), NodeOutputInfo::NumberTagged());
1109 if (lower()) {
1110 // PlainPrimitiveToNumber(x) => Call(ToNumberStub, x, no-context)
1111 Operator::Properties properties = node->op()->properties();
1112 Callable callable = CodeFactory::ToNumber(jsgraph_->isolate());
1113 CallDescriptor::Flags flags = CallDescriptor::kNoFlags;
1114 CallDescriptor* desc = Linkage::GetStubCallDescriptor(
1115 jsgraph_->isolate(), jsgraph_->zone(), callable.descriptor(), 0,
1116 flags, properties);
1117 node->InsertInput(jsgraph_->zone(), 0,
1118 jsgraph_->HeapConstant(callable.code()));
1119 node->AppendInput(jsgraph_->zone(), jsgraph_->NoContextConstant());
1120 NodeProperties::ChangeOp(node, jsgraph_->common()->Call(desc));
1121 }
1122 break;
1123 }
1124 case IrOpcode::kReferenceEqual: {
1125 VisitBinop(node, UseInfo::AnyTagged(), NodeOutputInfo::Bool());
1126 if (lower()) {
1127 NodeProperties::ChangeOp(node, lowering->machine()->WordEqual());
1128 }
1129 break;
1130 }
1131 case IrOpcode::kStringEqual: {
1132 VisitBinop(node, UseInfo::AnyTagged(), NodeOutputInfo::Bool());
1133 if (lower()) lowering->DoStringEqual(node);
1134 break;
1135 }
1136 case IrOpcode::kStringLessThan: {
1137 VisitBinop(node, UseInfo::AnyTagged(), NodeOutputInfo::Bool());
1138 if (lower()) lowering->DoStringLessThan(node);
1139 break;
1140 }
1141 case IrOpcode::kStringLessThanOrEqual: {
1142 VisitBinop(node, UseInfo::AnyTagged(), NodeOutputInfo::Bool());
1143 if (lower()) lowering->DoStringLessThanOrEqual(node);
1144 break;
1145 }
1146 case IrOpcode::kAllocate: {
1147 ProcessInput(node, 0, UseInfo::AnyTagged());
1148 ProcessRemainingInputs(node, 1);
1149 SetOutput(node, NodeOutputInfo::AnyTagged());
1150 break;
1151 }
1152 case IrOpcode::kLoadField: {
1153 FieldAccess access = FieldAccessOf(node->op());
1154 ProcessInput(node, 0, UseInfoForBasePointer(access));
1155 ProcessRemainingInputs(node, 1);
1156 SetOutputFromMachineType(node, access.machine_type);
1157 break;
1158 }
1159 case IrOpcode::kStoreField: {
1160 FieldAccess access = FieldAccessOf(node->op());
1161 ProcessInput(node, 0, UseInfoForBasePointer(access));
1162 ProcessInput(node, 1, TruncatingUseInfoFromRepresentation(
1163 access.machine_type.representation()));
1164 ProcessRemainingInputs(node, 2);
1165 SetOutput(node, NodeOutputInfo::None());
1166 break;
1167 }
1168 case IrOpcode::kLoadBuffer: {
1169 BufferAccess access = BufferAccessOf(node->op());
1170 ProcessInput(node, 0, UseInfo::PointerInt()); // buffer
1171 ProcessInput(node, 1, UseInfo::TruncatingWord32()); // offset
1172 ProcessInput(node, 2, UseInfo::TruncatingWord32()); // length
1173 ProcessRemainingInputs(node, 3);
1174
1175 NodeOutputInfo output_info;
1176 if (truncation.TruncatesUndefinedToZeroOrNaN()) {
1177 if (truncation.TruncatesNaNToZero()) {
1178 // If undefined is truncated to a non-NaN number, we can use
1179 // the load's representation.
1180 output_info = NodeOutputInfo(access.machine_type().representation(),
1181 NodeProperties::GetType(node));
1182 } else {
1183 // If undefined is truncated to a number, but the use can
1184 // observe NaN, we need to output at least the float32
1185 // representation.
1186 if (access.machine_type().representation() ==
1187 MachineRepresentation::kFloat32) {
1188 output_info =
1189 NodeOutputInfo(access.machine_type().representation(),
1190 NodeProperties::GetType(node));
1191 } else {
1192 output_info = NodeOutputInfo::Float64();
1193 }
1194 }
1195 } else {
1196 // If undefined is not truncated away, we need to have the tagged
1197 // representation.
1198 output_info = NodeOutputInfo::AnyTagged();
1199 }
1200 SetOutput(node, output_info);
1201 if (lower())
1202 lowering->DoLoadBuffer(node, output_info.representation(), changer_);
1203 break;
1204 }
1205 case IrOpcode::kStoreBuffer: {
1206 BufferAccess access = BufferAccessOf(node->op());
1207 ProcessInput(node, 0, UseInfo::PointerInt()); // buffer
1208 ProcessInput(node, 1, UseInfo::TruncatingWord32()); // offset
1209 ProcessInput(node, 2, UseInfo::TruncatingWord32()); // length
1210 ProcessInput(node, 3,
1211 TruncatingUseInfoFromRepresentation(
1212 access.machine_type().representation())); // value
1213 ProcessRemainingInputs(node, 4);
1214 SetOutput(node, NodeOutputInfo::None());
1215 if (lower()) lowering->DoStoreBuffer(node);
1216 break;
1217 }
1218 case IrOpcode::kLoadElement: {
1219 ElementAccess access = ElementAccessOf(node->op());
1220 ProcessInput(node, 0, UseInfoForBasePointer(access)); // base
1221 ProcessInput(node, 1, UseInfo::TruncatingWord32()); // index
1222 ProcessRemainingInputs(node, 2);
1223 SetOutputFromMachineType(node, access.machine_type);
1224 break;
1225 }
1226 case IrOpcode::kStoreElement: {
1227 ElementAccess access = ElementAccessOf(node->op());
1228 ProcessInput(node, 0, UseInfoForBasePointer(access)); // base
1229 ProcessInput(node, 1, UseInfo::TruncatingWord32()); // index
1230 ProcessInput(node, 2,
1231 TruncatingUseInfoFromRepresentation(
1232 access.machine_type.representation())); // value
1233 ProcessRemainingInputs(node, 3);
1234 SetOutput(node, NodeOutputInfo::None());
1235 break;
1236 }
1237 case IrOpcode::kObjectIsNumber: {
1238 ProcessInput(node, 0, UseInfo::AnyTagged());
1239 SetOutput(node, NodeOutputInfo::Bool());
1240 if (lower()) lowering->DoObjectIsNumber(node);
1241 break;
1242 }
1243 case IrOpcode::kObjectIsSmi: {
1244 ProcessInput(node, 0, UseInfo::AnyTagged());
1245 SetOutput(node, NodeOutputInfo::Bool());
1246 if (lower()) lowering->DoObjectIsSmi(node);
1247 break;
1248 }
1249
1250 //------------------------------------------------------------------
1251 // Machine-level operators.
1252 //------------------------------------------------------------------
1253 case IrOpcode::kLoad: {
1254 // TODO(jarin) Eventually, we should get rid of all machine stores
1255 // from the high-level phases, then this becomes UNREACHABLE.
1256 LoadRepresentation rep = LoadRepresentationOf(node->op());
1257 ProcessInput(node, 0, UseInfo::AnyTagged()); // tagged pointer
1258 ProcessInput(node, 1, UseInfo::PointerInt()); // index
1259 ProcessRemainingInputs(node, 2);
1260 SetOutputFromMachineType(node, rep);
1261 break;
1262 }
1263 case IrOpcode::kStore: {
1264 // TODO(jarin) Eventually, we should get rid of all machine stores
1265 // from the high-level phases, then this becomes UNREACHABLE.
1266 StoreRepresentation rep = StoreRepresentationOf(node->op());
1267 ProcessInput(node, 0, UseInfo::AnyTagged()); // tagged pointer
1268 ProcessInput(node, 1, UseInfo::PointerInt()); // index
1269 ProcessInput(node, 2,
1270 TruncatingUseInfoFromRepresentation(rep.representation()));
1271 ProcessRemainingInputs(node, 3);
1272 SetOutput(node, NodeOutputInfo::None());
1273 break;
1274 }
1275 case IrOpcode::kWord32Shr:
1276 // We output unsigned int32 for shift right because JavaScript.
1277 return VisitBinop(node, UseInfo::TruncatingWord32(),
1278 NodeOutputInfo::Uint32());
1279 case IrOpcode::kWord32And:
1280 case IrOpcode::kWord32Or:
1281 case IrOpcode::kWord32Xor:
1282 case IrOpcode::kWord32Shl:
1283 case IrOpcode::kWord32Sar:
1284 // We use signed int32 as the output type for these word32 operations,
1285 // though the machine bits are the same for either signed or unsigned,
1286 // because JavaScript considers the result from these operations signed.
1287 return VisitBinop(node, UseInfo::TruncatingWord32(),
1288 NodeOutputInfo::Int32());
1289 case IrOpcode::kWord32Equal:
1290 return VisitBinop(node, UseInfo::TruncatingWord32(),
1291 NodeOutputInfo::Bool());
1292
1293 case IrOpcode::kWord32Clz:
1294 return VisitUnop(node, UseInfo::TruncatingWord32(),
1295 NodeOutputInfo::Uint32());
1296
1297 case IrOpcode::kInt32Add:
1298 case IrOpcode::kInt32Sub:
1299 case IrOpcode::kInt32Mul:
1300 case IrOpcode::kInt32MulHigh:
1301 case IrOpcode::kInt32Div:
1302 case IrOpcode::kInt32Mod:
1303 return VisitInt32Binop(node);
1304 case IrOpcode::kUint32Div:
1305 case IrOpcode::kUint32Mod:
1306 case IrOpcode::kUint32MulHigh:
1307 return VisitUint32Binop(node);
1308 case IrOpcode::kInt32LessThan:
1309 case IrOpcode::kInt32LessThanOrEqual:
1310 return VisitInt32Cmp(node);
1311
1312 case IrOpcode::kUint32LessThan:
1313 case IrOpcode::kUint32LessThanOrEqual:
1314 return VisitUint32Cmp(node);
1315
1316 case IrOpcode::kInt64Add:
1317 case IrOpcode::kInt64Sub:
1318 case IrOpcode::kInt64Mul:
1319 case IrOpcode::kInt64Div:
1320 case IrOpcode::kInt64Mod:
1321 return VisitInt64Binop(node);
1322 case IrOpcode::kInt64LessThan:
1323 case IrOpcode::kInt64LessThanOrEqual:
1324 return VisitInt64Cmp(node);
1325
1326 case IrOpcode::kUint64LessThan:
1327 return VisitUint64Cmp(node);
1328
1329 case IrOpcode::kUint64Div:
1330 case IrOpcode::kUint64Mod:
1331 return VisitUint64Binop(node);
1332
1333 case IrOpcode::kWord64And:
1334 case IrOpcode::kWord64Or:
1335 case IrOpcode::kWord64Xor:
1336 case IrOpcode::kWord64Shl:
1337 case IrOpcode::kWord64Shr:
1338 case IrOpcode::kWord64Sar:
1339 return VisitBinop(node, UseInfo::TruncatingWord64(),
1340 NodeOutputInfo::Int64());
1341 case IrOpcode::kWord64Equal:
1342 return VisitBinop(node, UseInfo::TruncatingWord64(),
1343 NodeOutputInfo::Bool());
1344
1345 case IrOpcode::kChangeInt32ToInt64:
1346 return VisitUnop(
1347 node, UseInfo::TruncatingWord32(),
1348 NodeOutputInfo(MachineRepresentation::kWord64, Type::Signed32()));
1349 case IrOpcode::kChangeUint32ToUint64:
1350 return VisitUnop(
1351 node, UseInfo::TruncatingWord32(),
1352 NodeOutputInfo(MachineRepresentation::kWord64, Type::Unsigned32()));
1353 case IrOpcode::kTruncateFloat64ToFloat32:
1354 return VisitUnop(node, UseInfo::Float64(), NodeOutputInfo::Float32());
1355 case IrOpcode::kTruncateFloat64ToInt32:
1356 return VisitUnop(node, UseInfo::Float64(), NodeOutputInfo::Int32());
1357 case IrOpcode::kTruncateInt64ToInt32:
1358 // TODO(titzer): Is kTypeInt32 correct here?
1359 return VisitUnop(node, UseInfo::Word64TruncatingToWord32(),
1360 NodeOutputInfo::Int32());
1361
1362 case IrOpcode::kChangeFloat32ToFloat64:
1363 return VisitUnop(node, UseInfo::Float32(), NodeOutputInfo::Float64());
1364 case IrOpcode::kChangeInt32ToFloat64:
1365 return VisitUnop(
1366 node, UseInfo::TruncatingWord32(),
1367 NodeOutputInfo(MachineRepresentation::kFloat64, Type::Signed32()));
1368 case IrOpcode::kChangeUint32ToFloat64:
1369 return VisitUnop(node, UseInfo::TruncatingWord32(),
1370 NodeOutputInfo(MachineRepresentation::kFloat64,
1371 Type::Unsigned32()));
1372 case IrOpcode::kChangeFloat64ToInt32:
1373 return VisitUnop(node, UseInfo::Float64TruncatingToWord32(),
1374 NodeOutputInfo::Int32());
1375 case IrOpcode::kChangeFloat64ToUint32:
1376 return VisitUnop(node, UseInfo::Float64TruncatingToWord32(),
1377 NodeOutputInfo::Uint32());
1378
1379 case IrOpcode::kFloat64Add:
1380 case IrOpcode::kFloat64Sub:
1381 case IrOpcode::kFloat64Mul:
1382 case IrOpcode::kFloat64Div:
1383 case IrOpcode::kFloat64Mod:
1384 case IrOpcode::kFloat64Min:
1385 return VisitFloat64Binop(node);
1386 case IrOpcode::kFloat64Abs:
1387 case IrOpcode::kFloat64Sqrt:
1388 case IrOpcode::kFloat64RoundDown:
1389 case IrOpcode::kFloat64RoundTruncate:
1390 case IrOpcode::kFloat64RoundTiesAway:
1391 return VisitUnop(node, UseInfo::Float64(), NodeOutputInfo::Float64());
1392 case IrOpcode::kFloat64Equal:
1393 case IrOpcode::kFloat64LessThan:
1394 case IrOpcode::kFloat64LessThanOrEqual:
1395 return VisitFloat64Cmp(node);
1396 case IrOpcode::kFloat64ExtractLowWord32:
1397 case IrOpcode::kFloat64ExtractHighWord32:
1398 return VisitUnop(node, UseInfo::Float64(), NodeOutputInfo::Int32());
1399 case IrOpcode::kFloat64InsertLowWord32:
1400 case IrOpcode::kFloat64InsertHighWord32:
1401 return VisitBinop(node, UseInfo::Float64(), UseInfo::TruncatingWord32(),
1402 NodeOutputInfo::Float64());
1403 case IrOpcode::kLoadStackPointer:
1404 case IrOpcode::kLoadFramePointer:
1405 return VisitLeaf(node, NodeOutputInfo::Pointer());
1406 case IrOpcode::kStateValues:
1407 VisitStateValues(node);
1408 break;
1409 default:
1410 VisitInputs(node);
1411 // Assume the output is tagged.
1412 SetOutput(node, NodeOutputInfo::AnyTagged());
1413 break;
1414 }
1415 }
1416
DeferReplacement(Node * node,Node * replacement)1417 void DeferReplacement(Node* node, Node* replacement) {
1418 TRACE("defer replacement #%d:%s with #%d:%s\n", node->id(),
1419 node->op()->mnemonic(), replacement->id(),
1420 replacement->op()->mnemonic());
1421
1422 if (replacement->id() < count_ &&
1423 GetInfo(node)->output_type()->Is(GetInfo(replacement)->output_type())) {
1424 // Replace with a previously existing node eagerly only if the type is the
1425 // same.
1426 node->ReplaceUses(replacement);
1427 } else {
1428 // Otherwise, we are replacing a node with a representation change.
1429 // Such a substitution must be done after all lowering is done, because
1430 // changing the type could confuse the representation change
1431 // insertion for uses of the node.
1432 replacements_.push_back(node);
1433 replacements_.push_back(replacement);
1434 }
1435 node->NullAllInputs(); // Node is now dead.
1436 }
1437
PrintOutputInfo(NodeInfo * info)1438 void PrintOutputInfo(NodeInfo* info) {
1439 if (FLAG_trace_representation) {
1440 OFStream os(stdout);
1441 os << info->representation() << " (";
1442 info->output_type()->PrintTo(os, Type::SEMANTIC_DIM);
1443 os << ")";
1444 }
1445 }
1446
PrintRepresentation(MachineRepresentation rep)1447 void PrintRepresentation(MachineRepresentation rep) {
1448 if (FLAG_trace_representation) {
1449 OFStream os(stdout);
1450 os << rep;
1451 }
1452 }
1453
PrintTruncation(Truncation truncation)1454 void PrintTruncation(Truncation truncation) {
1455 if (FLAG_trace_representation) {
1456 OFStream os(stdout);
1457 os << truncation.description();
1458 }
1459 }
1460
PrintUseInfo(UseInfo info)1461 void PrintUseInfo(UseInfo info) {
1462 if (FLAG_trace_representation) {
1463 OFStream os(stdout);
1464 os << info.preferred() << ":" << info.truncation().description();
1465 }
1466 }
1467
1468 private:
1469 JSGraph* jsgraph_;
1470 size_t const count_; // number of nodes in the graph
1471 ZoneVector<NodeInfo> info_; // node id -> usage information
1472 #ifdef DEBUG
1473 ZoneVector<InputUseInfos> node_input_use_infos_; // Debug information about
1474 // requirements on inputs.
1475 #endif // DEBUG
1476 NodeVector nodes_; // collected nodes
1477 NodeVector replacements_; // replacements to be done after lowering
1478 Phase phase_; // current phase of algorithm
1479 RepresentationChanger* changer_; // for inserting representation changes
1480 ZoneQueue<Node*> queue_; // queue for traversing the graph
1481 // TODO(danno): RepresentationSelector shouldn't know anything about the
1482 // source positions table, but must for now since there currently is no other
1483 // way to pass down source position information to nodes created during
1484 // lowering. Once this phase becomes a vanilla reducer, it should get source
1485 // position information via the SourcePositionWrapper like all other reducers.
1486 SourcePositionTable* source_positions_;
1487 TypeCache const& type_cache_;
1488
GetInfo(Node * node)1489 NodeInfo* GetInfo(Node* node) {
1490 DCHECK(node->id() >= 0);
1491 DCHECK(node->id() < count_);
1492 return &info_[node->id()];
1493 }
1494 };
1495
1496
SimplifiedLowering(JSGraph * jsgraph,Zone * zone,SourcePositionTable * source_positions)1497 SimplifiedLowering::SimplifiedLowering(JSGraph* jsgraph, Zone* zone,
1498 SourcePositionTable* source_positions)
1499 : jsgraph_(jsgraph),
1500 zone_(zone),
1501 type_cache_(TypeCache::Get()),
1502 source_positions_(source_positions) {}
1503
1504
LowerAllNodes()1505 void SimplifiedLowering::LowerAllNodes() {
1506 RepresentationChanger changer(jsgraph(), jsgraph()->isolate());
1507 RepresentationSelector selector(jsgraph(), zone_, &changer,
1508 source_positions_);
1509 selector.Run(this);
1510 }
1511
1512
DoLoadBuffer(Node * node,MachineRepresentation output_rep,RepresentationChanger * changer)1513 void SimplifiedLowering::DoLoadBuffer(Node* node,
1514 MachineRepresentation output_rep,
1515 RepresentationChanger* changer) {
1516 DCHECK_EQ(IrOpcode::kLoadBuffer, node->opcode());
1517 DCHECK_NE(MachineRepresentation::kNone, output_rep);
1518 MachineType const access_type = BufferAccessOf(node->op()).machine_type();
1519 if (output_rep != access_type.representation()) {
1520 Node* const buffer = node->InputAt(0);
1521 Node* const offset = node->InputAt(1);
1522 Node* const length = node->InputAt(2);
1523 Node* const effect = node->InputAt(3);
1524 Node* const control = node->InputAt(4);
1525 Node* const index =
1526 machine()->Is64()
1527 ? graph()->NewNode(machine()->ChangeUint32ToUint64(), offset)
1528 : offset;
1529
1530 Node* check = graph()->NewNode(machine()->Uint32LessThan(), offset, length);
1531 Node* branch =
1532 graph()->NewNode(common()->Branch(BranchHint::kTrue), check, control);
1533
1534 Node* if_true = graph()->NewNode(common()->IfTrue(), branch);
1535 Node* etrue = graph()->NewNode(machine()->Load(access_type), buffer, index,
1536 effect, if_true);
1537 Node* vtrue = changer->GetRepresentationFor(
1538 etrue, access_type.representation(), NodeProperties::GetType(node),
1539 output_rep, Truncation::None());
1540
1541 Node* if_false = graph()->NewNode(common()->IfFalse(), branch);
1542 Node* efalse = effect;
1543 Node* vfalse;
1544 if (output_rep == MachineRepresentation::kTagged) {
1545 vfalse = jsgraph()->UndefinedConstant();
1546 } else if (output_rep == MachineRepresentation::kFloat64) {
1547 vfalse =
1548 jsgraph()->Float64Constant(std::numeric_limits<double>::quiet_NaN());
1549 } else if (output_rep == MachineRepresentation::kFloat32) {
1550 vfalse =
1551 jsgraph()->Float32Constant(std::numeric_limits<float>::quiet_NaN());
1552 } else {
1553 vfalse = jsgraph()->Int32Constant(0);
1554 }
1555
1556 Node* merge = graph()->NewNode(common()->Merge(2), if_true, if_false);
1557 Node* ephi = graph()->NewNode(common()->EffectPhi(2), etrue, efalse, merge);
1558
1559 // Replace effect uses of {node} with the {ephi}.
1560 NodeProperties::ReplaceUses(node, node, ephi);
1561
1562 // Turn the {node} into a Phi.
1563 node->ReplaceInput(0, vtrue);
1564 node->ReplaceInput(1, vfalse);
1565 node->ReplaceInput(2, merge);
1566 node->TrimInputCount(3);
1567 NodeProperties::ChangeOp(node, common()->Phi(output_rep, 2));
1568 } else {
1569 NodeProperties::ChangeOp(node, machine()->CheckedLoad(access_type));
1570 }
1571 }
1572
1573
DoStoreBuffer(Node * node)1574 void SimplifiedLowering::DoStoreBuffer(Node* node) {
1575 DCHECK_EQ(IrOpcode::kStoreBuffer, node->opcode());
1576 MachineRepresentation const rep =
1577 BufferAccessOf(node->op()).machine_type().representation();
1578 NodeProperties::ChangeOp(node, machine()->CheckedStore(rep));
1579 }
1580
1581
DoObjectIsNumber(Node * node)1582 void SimplifiedLowering::DoObjectIsNumber(Node* node) {
1583 Node* input = NodeProperties::GetValueInput(node, 0);
1584 // TODO(bmeurer): Optimize somewhat based on input type.
1585 Node* check =
1586 graph()->NewNode(machine()->WordEqual(),
1587 graph()->NewNode(machine()->WordAnd(), input,
1588 jsgraph()->IntPtrConstant(kSmiTagMask)),
1589 jsgraph()->IntPtrConstant(kSmiTag));
1590 Node* branch = graph()->NewNode(common()->Branch(), check, graph()->start());
1591 Node* if_true = graph()->NewNode(common()->IfTrue(), branch);
1592 Node* vtrue = jsgraph()->Int32Constant(1);
1593 Node* if_false = graph()->NewNode(common()->IfFalse(), branch);
1594 Node* vfalse = graph()->NewNode(
1595 machine()->WordEqual(),
1596 graph()->NewNode(
1597 machine()->Load(MachineType::AnyTagged()), input,
1598 jsgraph()->IntPtrConstant(HeapObject::kMapOffset - kHeapObjectTag),
1599 graph()->start(), if_false),
1600 jsgraph()->HeapConstant(isolate()->factory()->heap_number_map()));
1601 Node* control = graph()->NewNode(common()->Merge(2), if_true, if_false);
1602 node->ReplaceInput(0, vtrue);
1603 node->AppendInput(graph()->zone(), vfalse);
1604 node->AppendInput(graph()->zone(), control);
1605 NodeProperties::ChangeOp(node, common()->Phi(MachineRepresentation::kBit, 2));
1606 }
1607
1608
DoObjectIsSmi(Node * node)1609 void SimplifiedLowering::DoObjectIsSmi(Node* node) {
1610 node->ReplaceInput(0,
1611 graph()->NewNode(machine()->WordAnd(), node->InputAt(0),
1612 jsgraph()->IntPtrConstant(kSmiTagMask)));
1613 node->AppendInput(graph()->zone(), jsgraph()->IntPtrConstant(kSmiTag));
1614 NodeProperties::ChangeOp(node, machine()->WordEqual());
1615 }
1616
1617
StringComparison(Node * node)1618 Node* SimplifiedLowering::StringComparison(Node* node) {
1619 Operator::Properties properties = node->op()->properties();
1620 Callable callable = CodeFactory::StringCompare(isolate());
1621 CallDescriptor::Flags flags = CallDescriptor::kNoFlags;
1622 CallDescriptor* desc = Linkage::GetStubCallDescriptor(
1623 isolate(), zone(), callable.descriptor(), 0, flags, properties);
1624 return graph()->NewNode(
1625 common()->Call(desc), jsgraph()->HeapConstant(callable.code()),
1626 NodeProperties::GetValueInput(node, 0),
1627 NodeProperties::GetValueInput(node, 1), jsgraph()->NoContextConstant(),
1628 NodeProperties::GetEffectInput(node),
1629 NodeProperties::GetControlInput(node));
1630 }
1631
1632
Int32Div(Node * const node)1633 Node* SimplifiedLowering::Int32Div(Node* const node) {
1634 Int32BinopMatcher m(node);
1635 Node* const zero = jsgraph()->Int32Constant(0);
1636 Node* const minus_one = jsgraph()->Int32Constant(-1);
1637 Node* const lhs = m.left().node();
1638 Node* const rhs = m.right().node();
1639
1640 if (m.right().Is(-1)) {
1641 return graph()->NewNode(machine()->Int32Sub(), zero, lhs);
1642 } else if (m.right().Is(0)) {
1643 return rhs;
1644 } else if (machine()->Int32DivIsSafe() || m.right().HasValue()) {
1645 return graph()->NewNode(machine()->Int32Div(), lhs, rhs, graph()->start());
1646 }
1647
1648 // General case for signed integer division.
1649 //
1650 // if 0 < rhs then
1651 // lhs / rhs
1652 // else
1653 // if rhs < -1 then
1654 // lhs / rhs
1655 // else if rhs == 0 then
1656 // 0
1657 // else
1658 // 0 - lhs
1659 //
1660 // Note: We do not use the Diamond helper class here, because it really hurts
1661 // readability with nested diamonds.
1662 const Operator* const merge_op = common()->Merge(2);
1663 const Operator* const phi_op =
1664 common()->Phi(MachineRepresentation::kWord32, 2);
1665
1666 Node* check0 = graph()->NewNode(machine()->Int32LessThan(), zero, rhs);
1667 Node* branch0 = graph()->NewNode(common()->Branch(BranchHint::kTrue), check0,
1668 graph()->start());
1669
1670 Node* if_true0 = graph()->NewNode(common()->IfTrue(), branch0);
1671 Node* true0 = graph()->NewNode(machine()->Int32Div(), lhs, rhs, if_true0);
1672
1673 Node* if_false0 = graph()->NewNode(common()->IfFalse(), branch0);
1674 Node* false0;
1675 {
1676 Node* check1 = graph()->NewNode(machine()->Int32LessThan(), rhs, minus_one);
1677 Node* branch1 = graph()->NewNode(common()->Branch(), check1, if_false0);
1678
1679 Node* if_true1 = graph()->NewNode(common()->IfTrue(), branch1);
1680 Node* true1 = graph()->NewNode(machine()->Int32Div(), lhs, rhs, if_true1);
1681
1682 Node* if_false1 = graph()->NewNode(common()->IfFalse(), branch1);
1683 Node* false1;
1684 {
1685 Node* check2 = graph()->NewNode(machine()->Word32Equal(), rhs, zero);
1686 Node* branch2 = graph()->NewNode(common()->Branch(), check2, if_false1);
1687
1688 Node* if_true2 = graph()->NewNode(common()->IfTrue(), branch2);
1689 Node* true2 = zero;
1690
1691 Node* if_false2 = graph()->NewNode(common()->IfFalse(), branch2);
1692 Node* false2 = graph()->NewNode(machine()->Int32Sub(), zero, lhs);
1693
1694 if_false1 = graph()->NewNode(merge_op, if_true2, if_false2);
1695 false1 = graph()->NewNode(phi_op, true2, false2, if_false1);
1696 }
1697
1698 if_false0 = graph()->NewNode(merge_op, if_true1, if_false1);
1699 false0 = graph()->NewNode(phi_op, true1, false1, if_false0);
1700 }
1701
1702 Node* merge0 = graph()->NewNode(merge_op, if_true0, if_false0);
1703 return graph()->NewNode(phi_op, true0, false0, merge0);
1704 }
1705
1706
Int32Mod(Node * const node)1707 Node* SimplifiedLowering::Int32Mod(Node* const node) {
1708 Int32BinopMatcher m(node);
1709 Node* const zero = jsgraph()->Int32Constant(0);
1710 Node* const minus_one = jsgraph()->Int32Constant(-1);
1711 Node* const lhs = m.left().node();
1712 Node* const rhs = m.right().node();
1713
1714 if (m.right().Is(-1) || m.right().Is(0)) {
1715 return zero;
1716 } else if (m.right().HasValue()) {
1717 return graph()->NewNode(machine()->Int32Mod(), lhs, rhs, graph()->start());
1718 }
1719
1720 // General case for signed integer modulus, with optimization for (unknown)
1721 // power of 2 right hand side.
1722 //
1723 // if 0 < rhs then
1724 // msk = rhs - 1
1725 // if rhs & msk != 0 then
1726 // lhs % rhs
1727 // else
1728 // if lhs < 0 then
1729 // -(-lhs & msk)
1730 // else
1731 // lhs & msk
1732 // else
1733 // if rhs < -1 then
1734 // lhs % rhs
1735 // else
1736 // zero
1737 //
1738 // Note: We do not use the Diamond helper class here, because it really hurts
1739 // readability with nested diamonds.
1740 const Operator* const merge_op = common()->Merge(2);
1741 const Operator* const phi_op =
1742 common()->Phi(MachineRepresentation::kWord32, 2);
1743
1744 Node* check0 = graph()->NewNode(machine()->Int32LessThan(), zero, rhs);
1745 Node* branch0 = graph()->NewNode(common()->Branch(BranchHint::kTrue), check0,
1746 graph()->start());
1747
1748 Node* if_true0 = graph()->NewNode(common()->IfTrue(), branch0);
1749 Node* true0;
1750 {
1751 Node* msk = graph()->NewNode(machine()->Int32Add(), rhs, minus_one);
1752
1753 Node* check1 = graph()->NewNode(machine()->Word32And(), rhs, msk);
1754 Node* branch1 = graph()->NewNode(common()->Branch(), check1, if_true0);
1755
1756 Node* if_true1 = graph()->NewNode(common()->IfTrue(), branch1);
1757 Node* true1 = graph()->NewNode(machine()->Int32Mod(), lhs, rhs, if_true1);
1758
1759 Node* if_false1 = graph()->NewNode(common()->IfFalse(), branch1);
1760 Node* false1;
1761 {
1762 Node* check2 = graph()->NewNode(machine()->Int32LessThan(), lhs, zero);
1763 Node* branch2 = graph()->NewNode(common()->Branch(BranchHint::kFalse),
1764 check2, if_false1);
1765
1766 Node* if_true2 = graph()->NewNode(common()->IfTrue(), branch2);
1767 Node* true2 = graph()->NewNode(
1768 machine()->Int32Sub(), zero,
1769 graph()->NewNode(machine()->Word32And(),
1770 graph()->NewNode(machine()->Int32Sub(), zero, lhs),
1771 msk));
1772
1773 Node* if_false2 = graph()->NewNode(common()->IfFalse(), branch2);
1774 Node* false2 = graph()->NewNode(machine()->Word32And(), lhs, msk);
1775
1776 if_false1 = graph()->NewNode(merge_op, if_true2, if_false2);
1777 false1 = graph()->NewNode(phi_op, true2, false2, if_false1);
1778 }
1779
1780 if_true0 = graph()->NewNode(merge_op, if_true1, if_false1);
1781 true0 = graph()->NewNode(phi_op, true1, false1, if_true0);
1782 }
1783
1784 Node* if_false0 = graph()->NewNode(common()->IfFalse(), branch0);
1785 Node* false0;
1786 {
1787 Node* check1 = graph()->NewNode(machine()->Int32LessThan(), rhs, minus_one);
1788 Node* branch1 = graph()->NewNode(common()->Branch(BranchHint::kTrue),
1789 check1, if_false0);
1790
1791 Node* if_true1 = graph()->NewNode(common()->IfTrue(), branch1);
1792 Node* true1 = graph()->NewNode(machine()->Int32Mod(), lhs, rhs, if_true1);
1793
1794 Node* if_false1 = graph()->NewNode(common()->IfFalse(), branch1);
1795 Node* false1 = zero;
1796
1797 if_false0 = graph()->NewNode(merge_op, if_true1, if_false1);
1798 false0 = graph()->NewNode(phi_op, true1, false1, if_false0);
1799 }
1800
1801 Node* merge0 = graph()->NewNode(merge_op, if_true0, if_false0);
1802 return graph()->NewNode(phi_op, true0, false0, merge0);
1803 }
1804
1805
Uint32Div(Node * const node)1806 Node* SimplifiedLowering::Uint32Div(Node* const node) {
1807 Uint32BinopMatcher m(node);
1808 Node* const zero = jsgraph()->Uint32Constant(0);
1809 Node* const lhs = m.left().node();
1810 Node* const rhs = m.right().node();
1811
1812 if (m.right().Is(0)) {
1813 return zero;
1814 } else if (machine()->Uint32DivIsSafe() || m.right().HasValue()) {
1815 return graph()->NewNode(machine()->Uint32Div(), lhs, rhs, graph()->start());
1816 }
1817
1818 Node* check = graph()->NewNode(machine()->Word32Equal(), rhs, zero);
1819 Diamond d(graph(), common(), check, BranchHint::kFalse);
1820 Node* div = graph()->NewNode(machine()->Uint32Div(), lhs, rhs, d.if_false);
1821 return d.Phi(MachineRepresentation::kWord32, zero, div);
1822 }
1823
1824
Uint32Mod(Node * const node)1825 Node* SimplifiedLowering::Uint32Mod(Node* const node) {
1826 Uint32BinopMatcher m(node);
1827 Node* const minus_one = jsgraph()->Int32Constant(-1);
1828 Node* const zero = jsgraph()->Uint32Constant(0);
1829 Node* const lhs = m.left().node();
1830 Node* const rhs = m.right().node();
1831
1832 if (m.right().Is(0)) {
1833 return zero;
1834 } else if (m.right().HasValue()) {
1835 return graph()->NewNode(machine()->Uint32Mod(), lhs, rhs, graph()->start());
1836 }
1837
1838 // General case for unsigned integer modulus, with optimization for (unknown)
1839 // power of 2 right hand side.
1840 //
1841 // if rhs then
1842 // msk = rhs - 1
1843 // if rhs & msk != 0 then
1844 // lhs % rhs
1845 // else
1846 // lhs & msk
1847 // else
1848 // zero
1849 //
1850 // Note: We do not use the Diamond helper class here, because it really hurts
1851 // readability with nested diamonds.
1852 const Operator* const merge_op = common()->Merge(2);
1853 const Operator* const phi_op =
1854 common()->Phi(MachineRepresentation::kWord32, 2);
1855
1856 Node* branch0 = graph()->NewNode(common()->Branch(BranchHint::kTrue), rhs,
1857 graph()->start());
1858
1859 Node* if_true0 = graph()->NewNode(common()->IfTrue(), branch0);
1860 Node* true0;
1861 {
1862 Node* msk = graph()->NewNode(machine()->Int32Add(), rhs, minus_one);
1863
1864 Node* check1 = graph()->NewNode(machine()->Word32And(), rhs, msk);
1865 Node* branch1 = graph()->NewNode(common()->Branch(), check1, if_true0);
1866
1867 Node* if_true1 = graph()->NewNode(common()->IfTrue(), branch1);
1868 Node* true1 = graph()->NewNode(machine()->Uint32Mod(), lhs, rhs, if_true1);
1869
1870 Node* if_false1 = graph()->NewNode(common()->IfFalse(), branch1);
1871 Node* false1 = graph()->NewNode(machine()->Word32And(), lhs, msk);
1872
1873 if_true0 = graph()->NewNode(merge_op, if_true1, if_false1);
1874 true0 = graph()->NewNode(phi_op, true1, false1, if_true0);
1875 }
1876
1877 Node* if_false0 = graph()->NewNode(common()->IfFalse(), branch0);
1878 Node* false0 = zero;
1879
1880 Node* merge0 = graph()->NewNode(merge_op, if_true0, if_false0);
1881 return graph()->NewNode(phi_op, true0, false0, merge0);
1882 }
1883
1884
DoShift(Node * node,Operator const * op,Type * rhs_type)1885 void SimplifiedLowering::DoShift(Node* node, Operator const* op,
1886 Type* rhs_type) {
1887 Node* const rhs = NodeProperties::GetValueInput(node, 1);
1888 if (!rhs_type->Is(type_cache_.kZeroToThirtyOne)) {
1889 node->ReplaceInput(1, graph()->NewNode(machine()->Word32And(), rhs,
1890 jsgraph()->Int32Constant(0x1f)));
1891 }
1892 NodeProperties::ChangeOp(node, op);
1893 }
1894
1895
1896 namespace {
1897
ReplaceEffectUses(Node * node,Node * replacement)1898 void ReplaceEffectUses(Node* node, Node* replacement) {
1899 // Requires distinguishing between value and effect edges.
1900 DCHECK(replacement->op()->EffectOutputCount() > 0);
1901 for (Edge edge : node->use_edges()) {
1902 if (NodeProperties::IsEffectEdge(edge)) {
1903 edge.UpdateTo(replacement);
1904 } else {
1905 DCHECK(NodeProperties::IsValueEdge(edge));
1906 }
1907 }
1908 }
1909
1910 } // namespace
1911
1912
DoStringEqual(Node * node)1913 void SimplifiedLowering::DoStringEqual(Node* node) {
1914 Node* comparison = StringComparison(node);
1915 ReplaceEffectUses(node, comparison);
1916 node->ReplaceInput(0, comparison);
1917 node->ReplaceInput(1, jsgraph()->SmiConstant(EQUAL));
1918 node->TrimInputCount(2);
1919 NodeProperties::ChangeOp(node, machine()->WordEqual());
1920 }
1921
1922
DoStringLessThan(Node * node)1923 void SimplifiedLowering::DoStringLessThan(Node* node) {
1924 Node* comparison = StringComparison(node);
1925 ReplaceEffectUses(node, comparison);
1926 node->ReplaceInput(0, comparison);
1927 node->ReplaceInput(1, jsgraph()->SmiConstant(EQUAL));
1928 node->TrimInputCount(2);
1929 NodeProperties::ChangeOp(node, machine()->IntLessThan());
1930 }
1931
1932
DoStringLessThanOrEqual(Node * node)1933 void SimplifiedLowering::DoStringLessThanOrEqual(Node* node) {
1934 Node* comparison = StringComparison(node);
1935 ReplaceEffectUses(node, comparison);
1936 node->ReplaceInput(0, comparison);
1937 node->ReplaceInput(1, jsgraph()->SmiConstant(EQUAL));
1938 node->TrimInputCount(2);
1939 NodeProperties::ChangeOp(node, machine()->IntLessThanOrEqual());
1940 }
1941
1942 } // namespace compiler
1943 } // namespace internal
1944 } // namespace v8
1945