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/int64-lowering.h"
6#include "src/compiler/common-operator.h"
7#include "src/compiler/diamond.h"
8#include "src/compiler/graph.h"
9#include "src/compiler/linkage.h"
10#include "src/compiler/machine-operator.h"
11#include "src/compiler/node-matchers.h"
12#include "src/compiler/node-properties.h"
13
14#include "src/compiler/node.h"
15#include "src/objects-inl.h"
16#include "src/wasm/wasm-module.h"
17#include "src/zone/zone.h"
18
19namespace v8 {
20namespace internal {
21namespace compiler {
22
23Int64Lowering::Int64Lowering(Graph* graph, MachineOperatorBuilder* machine,
24                             CommonOperatorBuilder* common, Zone* zone,
25                             Signature<MachineRepresentation>* signature)
26    : zone_(zone),
27      graph_(graph),
28      machine_(machine),
29      common_(common),
30      state_(graph, 3),
31      stack_(zone),
32      replacements_(nullptr),
33      signature_(signature),
34      placeholder_(graph->NewNode(common->Parameter(-2, "placeholder"),
35                                  graph->start())) {
36  DCHECK_NOT_NULL(graph);
37  DCHECK_NOT_NULL(graph->end());
38  replacements_ = zone->NewArray<Replacement>(graph->NodeCount());
39  memset(replacements_, 0, sizeof(Replacement) * graph->NodeCount());
40}
41
42void Int64Lowering::LowerGraph() {
43  if (!machine()->Is32()) {
44    return;
45  }
46  stack_.push_back({graph()->end(), 0});
47  state_.Set(graph()->end(), State::kOnStack);
48
49  while (!stack_.empty()) {
50    NodeState& top = stack_.back();
51    if (top.input_index == top.node->InputCount()) {
52      // All inputs of top have already been lowered, now lower top.
53      stack_.pop_back();
54      state_.Set(top.node, State::kVisited);
55      LowerNode(top.node);
56    } else {
57      // Push the next input onto the stack.
58      Node* input = top.node->InputAt(top.input_index++);
59      if (state_.Get(input) == State::kUnvisited) {
60        if (input->opcode() == IrOpcode::kPhi) {
61          // To break cycles with phi nodes we push phis on a separate stack so
62          // that they are processed after all other nodes.
63          PreparePhiReplacement(input);
64          stack_.push_front({input, 0});
65        } else if (input->opcode() == IrOpcode::kEffectPhi ||
66                   input->opcode() == IrOpcode::kLoop) {
67          stack_.push_front({input, 0});
68        } else {
69          stack_.push_back({input, 0});
70        }
71        state_.Set(input, State::kOnStack);
72      }
73    }
74  }
75}
76
77static int GetParameterIndexAfterLowering(
78    Signature<MachineRepresentation>* signature, int old_index) {
79  int result = old_index;
80  for (int i = 0; i < old_index; i++) {
81    if (signature->GetParam(i) == MachineRepresentation::kWord64) {
82      result++;
83    }
84  }
85  return result;
86}
87
88int Int64Lowering::GetParameterCountAfterLowering(
89    Signature<MachineRepresentation>* signature) {
90  // GetParameterIndexAfterLowering(parameter_count) returns the parameter count
91  // after lowering.
92  return GetParameterIndexAfterLowering(
93      signature, static_cast<int>(signature->parameter_count()));
94}
95
96static int GetReturnCountAfterLowering(
97    Signature<MachineRepresentation>* signature) {
98  int result = static_cast<int>(signature->return_count());
99  for (int i = 0; i < static_cast<int>(signature->return_count()); i++) {
100    if (signature->GetReturn(i) == MachineRepresentation::kWord64) {
101      result++;
102    }
103  }
104  return result;
105}
106
107void Int64Lowering::GetIndexNodes(Node* index, Node*& index_low,
108                                  Node*& index_high) {
109  if (HasReplacementLow(index)) {
110    index = GetReplacementLow(index);
111  }
112#if defined(V8_TARGET_LITTLE_ENDIAN)
113  index_low = index;
114  index_high = graph()->NewNode(machine()->Int32Add(), index,
115                                graph()->NewNode(common()->Int32Constant(4)));
116#elif defined(V8_TARGET_BIG_ENDIAN)
117  index_low = graph()->NewNode(machine()->Int32Add(), index,
118                               graph()->NewNode(common()->Int32Constant(4)));
119  index_high = index;
120#endif
121}
122
123#if defined(V8_TARGET_LITTLE_ENDIAN)
124const int Int64Lowering::kLowerWordOffset = 0;
125const int Int64Lowering::kHigherWordOffset = 4;
126#elif defined(V8_TARGET_BIG_ENDIAN)
127const int Int64Lowering::kLowerWordOffset = 4;
128const int Int64Lowering::kHigherWordOffset = 0;
129#endif
130
131void Int64Lowering::LowerNode(Node* node) {
132  switch (node->opcode()) {
133    case IrOpcode::kInt64Constant: {
134      int64_t value = OpParameter<int64_t>(node);
135      Node* low_node = graph()->NewNode(
136          common()->Int32Constant(static_cast<int32_t>(value & 0xFFFFFFFF)));
137      Node* high_node = graph()->NewNode(
138          common()->Int32Constant(static_cast<int32_t>(value >> 32)));
139      ReplaceNode(node, low_node, high_node);
140      break;
141    }
142    case IrOpcode::kLoad:
143    case IrOpcode::kUnalignedLoad: {
144      MachineRepresentation rep;
145      if (node->opcode() == IrOpcode::kLoad) {
146        rep = LoadRepresentationOf(node->op()).representation();
147      } else {
148        DCHECK(node->opcode() == IrOpcode::kUnalignedLoad);
149        rep = UnalignedLoadRepresentationOf(node->op()).representation();
150      }
151
152      if (rep == MachineRepresentation::kWord64) {
153        Node* base = node->InputAt(0);
154        Node* index = node->InputAt(1);
155        Node* index_low;
156        Node* index_high;
157        GetIndexNodes(index, index_low, index_high);
158        const Operator* load_op;
159
160        if (node->opcode() == IrOpcode::kLoad) {
161          load_op = machine()->Load(MachineType::Int32());
162        } else {
163          DCHECK(node->opcode() == IrOpcode::kUnalignedLoad);
164          load_op = machine()->UnalignedLoad(MachineType::Int32());
165        }
166
167        Node* high_node;
168        if (node->InputCount() > 2) {
169          Node* effect_high = node->InputAt(2);
170          Node* control_high = node->InputAt(3);
171          high_node = graph()->NewNode(load_op, base, index_high, effect_high,
172                                       control_high);
173          // change the effect change from old_node --> old_effect to
174          // old_node --> high_node --> old_effect.
175          node->ReplaceInput(2, high_node);
176        } else {
177          high_node = graph()->NewNode(load_op, base, index_high);
178        }
179        node->ReplaceInput(1, index_low);
180        NodeProperties::ChangeOp(node, load_op);
181        ReplaceNode(node, node, high_node);
182      } else {
183        DefaultLowering(node);
184      }
185      break;
186    }
187    case IrOpcode::kStore:
188    case IrOpcode::kUnalignedStore: {
189      MachineRepresentation rep;
190      if (node->opcode() == IrOpcode::kStore) {
191        rep = StoreRepresentationOf(node->op()).representation();
192      } else {
193        DCHECK(node->opcode() == IrOpcode::kUnalignedStore);
194        rep = UnalignedStoreRepresentationOf(node->op());
195      }
196
197      if (rep == MachineRepresentation::kWord64) {
198        // We change the original store node to store the low word, and create
199        // a new store node to store the high word. The effect and control edges
200        // are copied from the original store to the new store node, the effect
201        // edge of the original store is redirected to the new store.
202        Node* base = node->InputAt(0);
203        Node* index = node->InputAt(1);
204        Node* index_low;
205        Node* index_high;
206        GetIndexNodes(index, index_low, index_high);
207        Node* value = node->InputAt(2);
208        DCHECK(HasReplacementLow(value));
209        DCHECK(HasReplacementHigh(value));
210
211        const Operator* store_op;
212        if (node->opcode() == IrOpcode::kStore) {
213          WriteBarrierKind write_barrier_kind =
214              StoreRepresentationOf(node->op()).write_barrier_kind();
215          store_op = machine()->Store(StoreRepresentation(
216              MachineRepresentation::kWord32, write_barrier_kind));
217        } else {
218          DCHECK(node->opcode() == IrOpcode::kUnalignedStore);
219          store_op = machine()->UnalignedStore(MachineRepresentation::kWord32);
220        }
221
222        Node* high_node;
223        if (node->InputCount() > 3) {
224          Node* effect_high = node->InputAt(3);
225          Node* control_high = node->InputAt(4);
226          high_node = graph()->NewNode(store_op, base, index_high,
227                                       GetReplacementHigh(value), effect_high,
228                                       control_high);
229          node->ReplaceInput(3, high_node);
230
231        } else {
232          high_node = graph()->NewNode(store_op, base, index_high,
233                                       GetReplacementHigh(value));
234        }
235
236        node->ReplaceInput(1, index_low);
237        node->ReplaceInput(2, GetReplacementLow(value));
238        NodeProperties::ChangeOp(node, store_op);
239        ReplaceNode(node, node, high_node);
240      } else {
241        DefaultLowering(node, true);
242      }
243      break;
244    }
245    case IrOpcode::kStart: {
246      int parameter_count = GetParameterCountAfterLowering(signature());
247      // Only exchange the node if the parameter count actually changed.
248      if (parameter_count != static_cast<int>(signature()->parameter_count())) {
249        int delta =
250            parameter_count - static_cast<int>(signature()->parameter_count());
251        int new_output_count = node->op()->ValueOutputCount() + delta;
252        NodeProperties::ChangeOp(node, common()->Start(new_output_count));
253      }
254      break;
255    }
256    case IrOpcode::kParameter: {
257      DCHECK(node->InputCount() == 1);
258      // Only exchange the node if the parameter count actually changed. We do
259      // not even have to do the default lowering because the the start node,
260      // the only input of a parameter node, only changes if the parameter count
261      // changes.
262      if (GetParameterCountAfterLowering(signature()) !=
263          static_cast<int>(signature()->parameter_count())) {
264        int old_index = ParameterIndexOf(node->op());
265        int new_index = GetParameterIndexAfterLowering(signature(), old_index);
266        NodeProperties::ChangeOp(node, common()->Parameter(new_index));
267
268        Node* high_node = nullptr;
269        if (signature()->GetParam(old_index) ==
270            MachineRepresentation::kWord64) {
271          high_node = graph()->NewNode(common()->Parameter(new_index + 1),
272                                       graph()->start());
273        }
274        ReplaceNode(node, node, high_node);
275      }
276      break;
277    }
278    case IrOpcode::kReturn: {
279      DefaultLowering(node);
280      int new_return_count = GetReturnCountAfterLowering(signature());
281      if (static_cast<int>(signature()->return_count()) != new_return_count) {
282        NodeProperties::ChangeOp(node, common()->Return(new_return_count));
283      }
284      break;
285    }
286    case IrOpcode::kCall: {
287      // TODO(turbofan): Make WASM code const-correct wrt. CallDescriptor.
288      CallDescriptor* descriptor =
289          const_cast<CallDescriptor*>(CallDescriptorOf(node->op()));
290      if (DefaultLowering(node) ||
291          (descriptor->ReturnCount() == 1 &&
292           descriptor->GetReturnType(0) == MachineType::Int64())) {
293        // We have to adjust the call descriptor.
294        const Operator* op = common()->Call(
295            wasm::ModuleEnv::GetI32WasmCallDescriptor(zone(), descriptor));
296        NodeProperties::ChangeOp(node, op);
297      }
298      if (descriptor->ReturnCount() == 1 &&
299          descriptor->GetReturnType(0) == MachineType::Int64()) {
300        // We access the additional return values through projections.
301        Node* low_node =
302            graph()->NewNode(common()->Projection(0), node, graph()->start());
303        Node* high_node =
304            graph()->NewNode(common()->Projection(1), node, graph()->start());
305        ReplaceNode(node, low_node, high_node);
306      }
307      break;
308    }
309    case IrOpcode::kWord64And: {
310      DCHECK(node->InputCount() == 2);
311      Node* left = node->InputAt(0);
312      Node* right = node->InputAt(1);
313
314      Node* low_node =
315          graph()->NewNode(machine()->Word32And(), GetReplacementLow(left),
316                           GetReplacementLow(right));
317      Node* high_node =
318          graph()->NewNode(machine()->Word32And(), GetReplacementHigh(left),
319                           GetReplacementHigh(right));
320      ReplaceNode(node, low_node, high_node);
321      break;
322    }
323    case IrOpcode::kTruncateInt64ToInt32: {
324      DCHECK(node->InputCount() == 1);
325      Node* input = node->InputAt(0);
326      ReplaceNode(node, GetReplacementLow(input), nullptr);
327      node->NullAllInputs();
328      break;
329    }
330    case IrOpcode::kInt64Add: {
331      DCHECK(node->InputCount() == 2);
332
333      Node* right = node->InputAt(1);
334      node->ReplaceInput(1, GetReplacementLow(right));
335      node->AppendInput(zone(), GetReplacementHigh(right));
336
337      Node* left = node->InputAt(0);
338      node->ReplaceInput(0, GetReplacementLow(left));
339      node->InsertInput(zone(), 1, GetReplacementHigh(left));
340
341      NodeProperties::ChangeOp(node, machine()->Int32PairAdd());
342      // We access the additional return values through projections.
343      Node* low_node =
344          graph()->NewNode(common()->Projection(0), node, graph()->start());
345      Node* high_node =
346          graph()->NewNode(common()->Projection(1), node, graph()->start());
347      ReplaceNode(node, low_node, high_node);
348      break;
349    }
350    case IrOpcode::kInt64Sub: {
351      DCHECK(node->InputCount() == 2);
352
353      Node* right = node->InputAt(1);
354      node->ReplaceInput(1, GetReplacementLow(right));
355      node->AppendInput(zone(), GetReplacementHigh(right));
356
357      Node* left = node->InputAt(0);
358      node->ReplaceInput(0, GetReplacementLow(left));
359      node->InsertInput(zone(), 1, GetReplacementHigh(left));
360
361      NodeProperties::ChangeOp(node, machine()->Int32PairSub());
362      // We access the additional return values through projections.
363      Node* low_node =
364          graph()->NewNode(common()->Projection(0), node, graph()->start());
365      Node* high_node =
366          graph()->NewNode(common()->Projection(1), node, graph()->start());
367      ReplaceNode(node, low_node, high_node);
368      break;
369    }
370    case IrOpcode::kInt64Mul: {
371      DCHECK(node->InputCount() == 2);
372
373      Node* right = node->InputAt(1);
374      node->ReplaceInput(1, GetReplacementLow(right));
375      node->AppendInput(zone(), GetReplacementHigh(right));
376
377      Node* left = node->InputAt(0);
378      node->ReplaceInput(0, GetReplacementLow(left));
379      node->InsertInput(zone(), 1, GetReplacementHigh(left));
380
381      NodeProperties::ChangeOp(node, machine()->Int32PairMul());
382      // We access the additional return values through projections.
383      Node* low_node =
384          graph()->NewNode(common()->Projection(0), node, graph()->start());
385      Node* high_node =
386          graph()->NewNode(common()->Projection(1), node, graph()->start());
387      ReplaceNode(node, low_node, high_node);
388      break;
389    }
390    case IrOpcode::kWord64Or: {
391      DCHECK(node->InputCount() == 2);
392      Node* left = node->InputAt(0);
393      Node* right = node->InputAt(1);
394
395      Node* low_node =
396          graph()->NewNode(machine()->Word32Or(), GetReplacementLow(left),
397                           GetReplacementLow(right));
398      Node* high_node =
399          graph()->NewNode(machine()->Word32Or(), GetReplacementHigh(left),
400                           GetReplacementHigh(right));
401      ReplaceNode(node, low_node, high_node);
402      break;
403    }
404    case IrOpcode::kWord64Xor: {
405      DCHECK(node->InputCount() == 2);
406      Node* left = node->InputAt(0);
407      Node* right = node->InputAt(1);
408
409      Node* low_node =
410          graph()->NewNode(machine()->Word32Xor(), GetReplacementLow(left),
411                           GetReplacementLow(right));
412      Node* high_node =
413          graph()->NewNode(machine()->Word32Xor(), GetReplacementHigh(left),
414                           GetReplacementHigh(right));
415      ReplaceNode(node, low_node, high_node);
416      break;
417    }
418    case IrOpcode::kWord64Shl: {
419      // TODO(turbofan): if the shift count >= 32, then we can set the low word
420      // of the output to 0 and just calculate the high word.
421      DCHECK(node->InputCount() == 2);
422      Node* shift = node->InputAt(1);
423      if (HasReplacementLow(shift)) {
424        // We do not have to care about the high word replacement, because
425        // the shift can only be between 0 and 63 anyways.
426        node->ReplaceInput(1, GetReplacementLow(shift));
427      }
428
429      Node* value = node->InputAt(0);
430      node->ReplaceInput(0, GetReplacementLow(value));
431      node->InsertInput(zone(), 1, GetReplacementHigh(value));
432
433      NodeProperties::ChangeOp(node, machine()->Word32PairShl());
434      // We access the additional return values through projections.
435      Node* low_node =
436          graph()->NewNode(common()->Projection(0), node, graph()->start());
437      Node* high_node =
438          graph()->NewNode(common()->Projection(1), node, graph()->start());
439      ReplaceNode(node, low_node, high_node);
440      break;
441    }
442    case IrOpcode::kWord64Shr: {
443      // TODO(turbofan): if the shift count >= 32, then we can set the low word
444      // of the output to 0 and just calculate the high word.
445      DCHECK(node->InputCount() == 2);
446      Node* shift = node->InputAt(1);
447      if (HasReplacementLow(shift)) {
448        // We do not have to care about the high word replacement, because
449        // the shift can only be between 0 and 63 anyways.
450        node->ReplaceInput(1, GetReplacementLow(shift));
451      }
452
453      Node* value = node->InputAt(0);
454      node->ReplaceInput(0, GetReplacementLow(value));
455      node->InsertInput(zone(), 1, GetReplacementHigh(value));
456
457      NodeProperties::ChangeOp(node, machine()->Word32PairShr());
458      // We access the additional return values through projections.
459      Node* low_node =
460          graph()->NewNode(common()->Projection(0), node, graph()->start());
461      Node* high_node =
462          graph()->NewNode(common()->Projection(1), node, graph()->start());
463      ReplaceNode(node, low_node, high_node);
464      break;
465    }
466    case IrOpcode::kWord64Sar: {
467      // TODO(turbofan): if the shift count >= 32, then we can set the low word
468      // of the output to 0 and just calculate the high word.
469      DCHECK(node->InputCount() == 2);
470      Node* shift = node->InputAt(1);
471      if (HasReplacementLow(shift)) {
472        // We do not have to care about the high word replacement, because
473        // the shift can only be between 0 and 63 anyways.
474        node->ReplaceInput(1, GetReplacementLow(shift));
475      }
476
477      Node* value = node->InputAt(0);
478      node->ReplaceInput(0, GetReplacementLow(value));
479      node->InsertInput(zone(), 1, GetReplacementHigh(value));
480
481      NodeProperties::ChangeOp(node, machine()->Word32PairSar());
482      // We access the additional return values through projections.
483      Node* low_node =
484          graph()->NewNode(common()->Projection(0), node, graph()->start());
485      Node* high_node =
486          graph()->NewNode(common()->Projection(1), node, graph()->start());
487      ReplaceNode(node, low_node, high_node);
488      break;
489    }
490    case IrOpcode::kWord64Equal: {
491      DCHECK(node->InputCount() == 2);
492      Node* left = node->InputAt(0);
493      Node* right = node->InputAt(1);
494
495      // TODO(wasm): Use explicit comparisons and && here?
496      Node* replacement = graph()->NewNode(
497          machine()->Word32Equal(),
498          graph()->NewNode(
499              machine()->Word32Or(),
500              graph()->NewNode(machine()->Word32Xor(), GetReplacementLow(left),
501                               GetReplacementLow(right)),
502              graph()->NewNode(machine()->Word32Xor(), GetReplacementHigh(left),
503                               GetReplacementHigh(right))),
504          graph()->NewNode(common()->Int32Constant(0)));
505
506      ReplaceNode(node, replacement, nullptr);
507      break;
508    }
509    case IrOpcode::kInt64LessThan: {
510      LowerComparison(node, machine()->Int32LessThan(),
511                      machine()->Uint32LessThan());
512      break;
513    }
514    case IrOpcode::kInt64LessThanOrEqual: {
515      LowerComparison(node, machine()->Int32LessThan(),
516                      machine()->Uint32LessThanOrEqual());
517      break;
518    }
519    case IrOpcode::kUint64LessThan: {
520      LowerComparison(node, machine()->Uint32LessThan(),
521                      machine()->Uint32LessThan());
522      break;
523    }
524    case IrOpcode::kUint64LessThanOrEqual: {
525      LowerComparison(node, machine()->Uint32LessThan(),
526                      machine()->Uint32LessThanOrEqual());
527      break;
528    }
529    case IrOpcode::kChangeInt32ToInt64: {
530      DCHECK(node->InputCount() == 1);
531      Node* input = node->InputAt(0);
532      if (HasReplacementLow(input)) {
533        input = GetReplacementLow(input);
534      }
535      // We use SAR to preserve the sign in the high word.
536      ReplaceNode(
537          node, input,
538          graph()->NewNode(machine()->Word32Sar(), input,
539                           graph()->NewNode(common()->Int32Constant(31))));
540      node->NullAllInputs();
541      break;
542    }
543    case IrOpcode::kChangeUint32ToUint64: {
544      DCHECK(node->InputCount() == 1);
545      Node* input = node->InputAt(0);
546      if (HasReplacementLow(input)) {
547        input = GetReplacementLow(input);
548      }
549      ReplaceNode(node, input, graph()->NewNode(common()->Int32Constant(0)));
550      node->NullAllInputs();
551      break;
552    }
553    case IrOpcode::kBitcastInt64ToFloat64: {
554      DCHECK(node->InputCount() == 1);
555      Node* input = node->InputAt(0);
556      Node* stack_slot = graph()->NewNode(
557          machine()->StackSlot(MachineRepresentation::kWord64));
558
559      Node* store_high_word = graph()->NewNode(
560          machine()->Store(
561              StoreRepresentation(MachineRepresentation::kWord32,
562                                  WriteBarrierKind::kNoWriteBarrier)),
563          stack_slot,
564          graph()->NewNode(common()->Int32Constant(kHigherWordOffset)),
565          GetReplacementHigh(input), graph()->start(), graph()->start());
566
567      Node* store_low_word = graph()->NewNode(
568          machine()->Store(
569              StoreRepresentation(MachineRepresentation::kWord32,
570                                  WriteBarrierKind::kNoWriteBarrier)),
571          stack_slot,
572          graph()->NewNode(common()->Int32Constant(kLowerWordOffset)),
573          GetReplacementLow(input), store_high_word, graph()->start());
574
575      Node* load =
576          graph()->NewNode(machine()->Load(MachineType::Float64()), stack_slot,
577                           graph()->NewNode(common()->Int32Constant(0)),
578                           store_low_word, graph()->start());
579
580      ReplaceNode(node, load, nullptr);
581      break;
582    }
583    case IrOpcode::kBitcastFloat64ToInt64: {
584      DCHECK(node->InputCount() == 1);
585      Node* input = node->InputAt(0);
586      if (HasReplacementLow(input)) {
587        input = GetReplacementLow(input);
588      }
589      Node* stack_slot = graph()->NewNode(
590          machine()->StackSlot(MachineRepresentation::kWord64));
591      Node* store = graph()->NewNode(
592          machine()->Store(
593              StoreRepresentation(MachineRepresentation::kFloat64,
594                                  WriteBarrierKind::kNoWriteBarrier)),
595          stack_slot, graph()->NewNode(common()->Int32Constant(0)), input,
596          graph()->start(), graph()->start());
597
598      Node* high_node = graph()->NewNode(
599          machine()->Load(MachineType::Int32()), stack_slot,
600          graph()->NewNode(common()->Int32Constant(kHigherWordOffset)), store,
601          graph()->start());
602
603      Node* low_node = graph()->NewNode(
604          machine()->Load(MachineType::Int32()), stack_slot,
605          graph()->NewNode(common()->Int32Constant(kLowerWordOffset)), store,
606          graph()->start());
607      ReplaceNode(node, low_node, high_node);
608      break;
609    }
610    case IrOpcode::kWord64Ror: {
611      DCHECK(node->InputCount() == 2);
612      Node* input = node->InputAt(0);
613      Node* shift = HasReplacementLow(node->InputAt(1))
614                        ? GetReplacementLow(node->InputAt(1))
615                        : node->InputAt(1);
616      Int32Matcher m(shift);
617      if (m.HasValue()) {
618        // Precondition: 0 <= shift < 64.
619        int32_t shift_value = m.Value() & 0x3f;
620        if (shift_value == 0) {
621          ReplaceNode(node, GetReplacementLow(input),
622                      GetReplacementHigh(input));
623        } else if (shift_value == 32) {
624          ReplaceNode(node, GetReplacementHigh(input),
625                      GetReplacementLow(input));
626        } else {
627          Node* low_input;
628          Node* high_input;
629          if (shift_value < 32) {
630            low_input = GetReplacementLow(input);
631            high_input = GetReplacementHigh(input);
632          } else {
633            low_input = GetReplacementHigh(input);
634            high_input = GetReplacementLow(input);
635          }
636          int32_t masked_shift_value = shift_value & 0x1f;
637          Node* masked_shift =
638              graph()->NewNode(common()->Int32Constant(masked_shift_value));
639          Node* inv_shift = graph()->NewNode(
640              common()->Int32Constant(32 - masked_shift_value));
641
642          Node* low_node = graph()->NewNode(
643              machine()->Word32Or(),
644              graph()->NewNode(machine()->Word32Shr(), low_input, masked_shift),
645              graph()->NewNode(machine()->Word32Shl(), high_input, inv_shift));
646          Node* high_node = graph()->NewNode(
647              machine()->Word32Or(), graph()->NewNode(machine()->Word32Shr(),
648                                                      high_input, masked_shift),
649              graph()->NewNode(machine()->Word32Shl(), low_input, inv_shift));
650          ReplaceNode(node, low_node, high_node);
651        }
652      } else {
653        Node* safe_shift = shift;
654        if (!machine()->Word32ShiftIsSafe()) {
655          safe_shift =
656              graph()->NewNode(machine()->Word32And(), shift,
657                               graph()->NewNode(common()->Int32Constant(0x1f)));
658        }
659
660        // By creating this bit-mask with SAR and SHL we do not have to deal
661        // with shift == 0 as a special case.
662        Node* inv_mask = graph()->NewNode(
663            machine()->Word32Shl(),
664            graph()->NewNode(machine()->Word32Sar(),
665                             graph()->NewNode(common()->Int32Constant(
666                                 std::numeric_limits<int32_t>::min())),
667                             safe_shift),
668            graph()->NewNode(common()->Int32Constant(1)));
669
670        Node* bit_mask =
671            graph()->NewNode(machine()->Word32Xor(), inv_mask,
672                             graph()->NewNode(common()->Int32Constant(-1)));
673
674        // We have to mask the shift value for this comparison. If
675        // !machine()->Word32ShiftIsSafe() then the masking should already be
676        // part of the graph.
677        Node* masked_shift6 = shift;
678        if (machine()->Word32ShiftIsSafe()) {
679          masked_shift6 =
680              graph()->NewNode(machine()->Word32And(), shift,
681                               graph()->NewNode(common()->Int32Constant(0x3f)));
682        }
683
684        Diamond lt32(
685            graph(), common(),
686            graph()->NewNode(machine()->Int32LessThan(), masked_shift6,
687                             graph()->NewNode(common()->Int32Constant(32))));
688
689        // The low word and the high word can be swapped either at the input or
690        // at the output. We swap the inputs so that shift does not have to be
691        // kept for so long in a register.
692        Node* input_low =
693            lt32.Phi(MachineRepresentation::kWord32, GetReplacementLow(input),
694                     GetReplacementHigh(input));
695        Node* input_high =
696            lt32.Phi(MachineRepresentation::kWord32, GetReplacementHigh(input),
697                     GetReplacementLow(input));
698
699        Node* rotate_low =
700            graph()->NewNode(machine()->Word32Ror(), input_low, safe_shift);
701        Node* rotate_high =
702            graph()->NewNode(machine()->Word32Ror(), input_high, safe_shift);
703
704        Node* low_node = graph()->NewNode(
705            machine()->Word32Or(),
706            graph()->NewNode(machine()->Word32And(), rotate_low, bit_mask),
707            graph()->NewNode(machine()->Word32And(), rotate_high, inv_mask));
708
709        Node* high_node = graph()->NewNode(
710            machine()->Word32Or(),
711            graph()->NewNode(machine()->Word32And(), rotate_high, bit_mask),
712            graph()->NewNode(machine()->Word32And(), rotate_low, inv_mask));
713
714        ReplaceNode(node, low_node, high_node);
715      }
716      break;
717    }
718    case IrOpcode::kWord64Clz: {
719      DCHECK(node->InputCount() == 1);
720      Node* input = node->InputAt(0);
721      Diamond d(
722          graph(), common(),
723          graph()->NewNode(machine()->Word32Equal(), GetReplacementHigh(input),
724                           graph()->NewNode(common()->Int32Constant(0))));
725
726      Node* low_node = d.Phi(
727          MachineRepresentation::kWord32,
728          graph()->NewNode(machine()->Int32Add(),
729                           graph()->NewNode(machine()->Word32Clz(),
730                                            GetReplacementLow(input)),
731                           graph()->NewNode(common()->Int32Constant(32))),
732          graph()->NewNode(machine()->Word32Clz(), GetReplacementHigh(input)));
733      ReplaceNode(node, low_node, graph()->NewNode(common()->Int32Constant(0)));
734      break;
735    }
736    case IrOpcode::kWord64Ctz: {
737      DCHECK(node->InputCount() == 1);
738      DCHECK(machine()->Word32Ctz().IsSupported());
739      Node* input = node->InputAt(0);
740      Diamond d(
741          graph(), common(),
742          graph()->NewNode(machine()->Word32Equal(), GetReplacementLow(input),
743                           graph()->NewNode(common()->Int32Constant(0))));
744      Node* low_node =
745          d.Phi(MachineRepresentation::kWord32,
746                graph()->NewNode(machine()->Int32Add(),
747                                 graph()->NewNode(machine()->Word32Ctz().op(),
748                                                  GetReplacementHigh(input)),
749                                 graph()->NewNode(common()->Int32Constant(32))),
750                graph()->NewNode(machine()->Word32Ctz().op(),
751                                 GetReplacementLow(input)));
752      ReplaceNode(node, low_node, graph()->NewNode(common()->Int32Constant(0)));
753      break;
754    }
755    case IrOpcode::kWord64Popcnt: {
756      DCHECK(node->InputCount() == 1);
757      Node* input = node->InputAt(0);
758      // We assume that a Word64Popcnt node only has been created if
759      // Word32Popcnt is actually supported.
760      DCHECK(machine()->Word32Popcnt().IsSupported());
761      ReplaceNode(node, graph()->NewNode(
762                            machine()->Int32Add(),
763                            graph()->NewNode(machine()->Word32Popcnt().op(),
764                                             GetReplacementLow(input)),
765                            graph()->NewNode(machine()->Word32Popcnt().op(),
766                                             GetReplacementHigh(input))),
767                  graph()->NewNode(common()->Int32Constant(0)));
768      break;
769    }
770    case IrOpcode::kPhi: {
771      MachineRepresentation rep = PhiRepresentationOf(node->op());
772      if (rep == MachineRepresentation::kWord64) {
773        // The replacement nodes have already been created, we only have to
774        // replace placeholder nodes.
775        Node* low_node = GetReplacementLow(node);
776        Node* high_node = GetReplacementHigh(node);
777        for (int i = 0; i < node->op()->ValueInputCount(); i++) {
778          low_node->ReplaceInput(i, GetReplacementLow(node->InputAt(i)));
779          high_node->ReplaceInput(i, GetReplacementHigh(node->InputAt(i)));
780        }
781      } else {
782        DefaultLowering(node);
783      }
784      break;
785    }
786    case IrOpcode::kProjection: {
787      Node* call = node->InputAt(0);
788      DCHECK_EQ(IrOpcode::kCall, call->opcode());
789      CallDescriptor* descriptor =
790          const_cast<CallDescriptor*>(CallDescriptorOf(call->op()));
791      for (size_t i = 0; i < descriptor->ReturnCount(); i++) {
792        if (descriptor->GetReturnType(i) == MachineType::Int64()) {
793          UNREACHABLE();  // TODO(titzer): implement multiple i64 returns.
794        }
795      }
796      break;
797    }
798    case IrOpcode::kWord64ReverseBytes: {
799      Node* input = node->InputAt(0);
800      ReplaceNode(node, graph()->NewNode(machine()->Word32ReverseBytes().op(),
801                                         GetReplacementHigh(input)),
802                  graph()->NewNode(machine()->Word32ReverseBytes().op(),
803                                   GetReplacementLow(input)));
804      break;
805    }
806
807    default: { DefaultLowering(node); }
808  }
809}  // NOLINT(readability/fn_size)
810
811void Int64Lowering::LowerComparison(Node* node, const Operator* high_word_op,
812                                    const Operator* low_word_op) {
813  DCHECK(node->InputCount() == 2);
814  Node* left = node->InputAt(0);
815  Node* right = node->InputAt(1);
816  Node* replacement = graph()->NewNode(
817      machine()->Word32Or(),
818      graph()->NewNode(high_word_op, GetReplacementHigh(left),
819                       GetReplacementHigh(right)),
820      graph()->NewNode(
821          machine()->Word32And(),
822          graph()->NewNode(machine()->Word32Equal(), GetReplacementHigh(left),
823                           GetReplacementHigh(right)),
824          graph()->NewNode(low_word_op, GetReplacementLow(left),
825                           GetReplacementLow(right))));
826
827  ReplaceNode(node, replacement, nullptr);
828}
829
830bool Int64Lowering::DefaultLowering(Node* node, bool low_word_only) {
831  bool something_changed = false;
832  for (int i = NodeProperties::PastValueIndex(node) - 1; i >= 0; i--) {
833    Node* input = node->InputAt(i);
834    if (HasReplacementLow(input)) {
835      something_changed = true;
836      node->ReplaceInput(i, GetReplacementLow(input));
837    }
838    if (!low_word_only && HasReplacementHigh(input)) {
839      something_changed = true;
840      node->InsertInput(zone(), i + 1, GetReplacementHigh(input));
841    }
842  }
843  return something_changed;
844}
845
846void Int64Lowering::ReplaceNode(Node* old, Node* new_low, Node* new_high) {
847  // if new_low == nullptr, then also new_high == nullptr.
848  DCHECK(new_low != nullptr || new_high == nullptr);
849  replacements_[old->id()].low = new_low;
850  replacements_[old->id()].high = new_high;
851}
852
853bool Int64Lowering::HasReplacementLow(Node* node) {
854  return replacements_[node->id()].low != nullptr;
855}
856
857Node* Int64Lowering::GetReplacementLow(Node* node) {
858  Node* result = replacements_[node->id()].low;
859  DCHECK(result);
860  return result;
861}
862
863bool Int64Lowering::HasReplacementHigh(Node* node) {
864  return replacements_[node->id()].high != nullptr;
865}
866
867Node* Int64Lowering::GetReplacementHigh(Node* node) {
868  Node* result = replacements_[node->id()].high;
869  DCHECK(result);
870  return result;
871}
872
873void Int64Lowering::PreparePhiReplacement(Node* phi) {
874  MachineRepresentation rep = PhiRepresentationOf(phi->op());
875  if (rep == MachineRepresentation::kWord64) {
876    // We have to create the replacements for a phi node before we actually
877    // lower the phi to break potential cycles in the graph. The replacements of
878    // input nodes do not exist yet, so we use a placeholder node to pass the
879    // graph verifier.
880    int value_count = phi->op()->ValueInputCount();
881    Node** inputs_low = zone()->NewArray<Node*>(value_count + 1);
882    Node** inputs_high = zone()->NewArray<Node*>(value_count + 1);
883    for (int i = 0; i < value_count; i++) {
884      inputs_low[i] = placeholder_;
885      inputs_high[i] = placeholder_;
886    }
887    inputs_low[value_count] = NodeProperties::GetControlInput(phi, 0);
888    inputs_high[value_count] = NodeProperties::GetControlInput(phi, 0);
889    ReplaceNode(phi,
890                graph()->NewNode(
891                    common()->Phi(MachineRepresentation::kWord32, value_count),
892                    value_count + 1, inputs_low, false),
893                graph()->NewNode(
894                    common()->Phi(MachineRepresentation::kWord32, value_count),
895                    value_count + 1, inputs_high, false));
896  }
897}
898}  // namespace compiler
899}  // namespace internal
900}  // namespace v8
901