graph-assembler.h 36.3 KB
Newer Older
1 2 3 4 5 6 7
// Copyright 2016 the V8 project authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#ifndef V8_COMPILER_GRAPH_ASSEMBLER_H_
#define V8_COMPILER_GRAPH_ASSEMBLER_H_

8
#include "src/codegen/tnode.h"
9
#include "src/compiler/feedback-source.h"
10 11 12 13 14 15 16 17 18
#include "src/compiler/js-graph.h"
#include "src/compiler/node.h"
#include "src/compiler/simplified-operator.h"

namespace v8 {
namespace internal {

class JSGraph;
class Graph;
19 20 21 22 23 24
class Oddball;

// TODO(jgruber): Currently this is too permissive, but at least it lets us
// document which functions expect JS booleans. If a real Boolean type becomes
// possible in the future, use that instead.
using Boolean = Oddball;
25 26 27

namespace compiler {

28 29
class Schedule;
class BasicBlock;
30
class Reducer;
31

32
#define PURE_ASSEMBLER_MACH_UNOP_LIST(V) \
33 34 35
  V(BitcastFloat32ToInt32)               \
  V(BitcastFloat64ToInt64)               \
  V(BitcastInt32ToFloat32)               \
36
  V(BitcastWord32ToWord64)               \
37
  V(BitcastInt64ToFloat64)               \
38
  V(ChangeFloat32ToFloat64)              \
39 40 41
  V(ChangeFloat64ToInt32)                \
  V(ChangeFloat64ToInt64)                \
  V(ChangeFloat64ToUint32)               \
42
  V(ChangeInt32ToFloat64)                \
43
  V(ChangeInt32ToInt64)                  \
44 45 46
  V(ChangeInt64ToFloat64)                \
  V(ChangeUint32ToFloat64)               \
  V(ChangeUint32ToUint64)                \
47 48 49 50
  V(Float64Abs)                          \
  V(Float64ExtractHighWord32)            \
  V(Float64ExtractLowWord32)             \
  V(Float64SilenceNaN)                   \
51
  V(RoundFloat64ToInt32)                 \
52
  V(RoundInt32ToFloat32)                 \
53
  V(TruncateFloat64ToFloat32)            \
54
  V(TruncateFloat64ToWord32)             \
55
  V(TruncateInt64ToInt32)                \
56
  V(Word32ReverseBytes)                  \
57
  V(Word64ReverseBytes)
58

59
#define PURE_ASSEMBLER_MACH_BINOP_LIST(V) \
60 61 62 63 64 65 66 67 68
  V(Float64Add)                           \
  V(Float64Div)                           \
  V(Float64Equal)                         \
  V(Float64InsertHighWord32)              \
  V(Float64InsertLowWord32)               \
  V(Float64LessThan)                      \
  V(Float64LessThanOrEqual)               \
  V(Float64Mod)                           \
  V(Float64Sub)                           \
69
  V(Int32Add)                             \
70
  V(Int32LessThan)                        \
71
  V(Int32LessThanOrEqual)                 \
72 73 74 75 76 77 78
  V(Int32Mul)                             \
  V(Int32Sub)                             \
  V(Int64Sub)                             \
  V(IntAdd)                               \
  V(IntLessThan)                          \
  V(IntMul)                               \
  V(IntSub)                               \
79
  V(Uint32LessThan)                       \
80 81 82
  V(Uint32LessThanOrEqual)                \
  V(Uint64LessThan)                       \
  V(Uint64LessThanOrEqual)                \
83 84
  V(UintLessThan)                         \
  V(Word32And)                            \
85
  V(Word32Equal)                          \
86 87
  V(Word32Or)                             \
  V(Word32Sar)                            \
88
  V(Word32SarShiftOutZeros)               \
89 90 91 92
  V(Word32Shl)                            \
  V(Word32Shr)                            \
  V(Word32Xor)                            \
  V(Word64And)                            \
93
  V(Word64Equal)                          \
94
  V(Word64Or)                             \
95 96 97
  V(Word64Sar)                            \
  V(Word64SarShiftOutZeros)               \
  V(Word64Shl)                            \
98
  V(Word64Shr)                            \
99 100
  V(WordAnd)                              \
  V(WordEqual)                            \
101
  V(WordOr)                               \
102
  V(WordSar)                              \
103
  V(WordSarShiftOutZeros)                 \
104
  V(WordShl)                              \
105
  V(WordShr)                              \
106
  V(WordXor)
107 108 109 110

#define CHECKED_ASSEMBLER_MACH_BINOP_LIST(V) \
  V(Int32AddWithOverflow)                    \
  V(Int32Div)                                \
111 112 113
  V(Int32Mod)                                \
  V(Int32MulWithOverflow)                    \
  V(Int32SubWithOverflow)                    \
114 115
  V(Int64Div)                                \
  V(Int64Mod)                                \
116
  V(Uint32Div)                               \
117 118 119
  V(Uint32Mod)                               \
  V(Uint64Div)                               \
  V(Uint64Mod)
120

121 122 123 124 125 126 127 128 129 130 131
#define JSGRAPH_SINGLETON_CONSTANT_LIST(V)      \
  V(AllocateInOldGenerationStub, Code)          \
  V(AllocateInYoungGenerationStub, Code)        \
  V(AllocateRegularInOldGenerationStub, Code)   \
  V(AllocateRegularInYoungGenerationStub, Code) \
  V(BigIntMap, Map)                             \
  V(BooleanMap, Map)                            \
  V(EmptyString, String)                        \
  V(False, Boolean)                             \
  V(FixedArrayMap, Map)                         \
  V(FixedDoubleArrayMap, Map)                   \
132
  V(WeakFixedArrayMap, Map)                     \
133
  V(HeapNumberMap, Map)                         \
134
  V(MinusOne, Number)                           \
135 136 137 138 139 140
  V(NaN, Number)                                \
  V(NoContext, Object)                          \
  V(Null, Oddball)                              \
  V(One, Number)                                \
  V(TheHole, Oddball)                           \
  V(ToNumberBuiltin, Code)                      \
141
  V(PlainPrimitiveToNumberBuiltin, Code)        \
142 143 144
  V(True, Boolean)                              \
  V(Undefined, Oddball)                         \
  V(Zero, Number)
145

146 147
class GraphAssembler;

148
enum class GraphAssemblerLabelType { kDeferred, kNonDeferred, kLoop };
149 150

// Label with statically known count of incoming branches and phis.
151 152
template <size_t VarCount>
class GraphAssemblerLabel {
153 154 155
 public:
  Node* PhiAt(size_t index);

156 157 158 159 160 161 162
  template <typename T>
  TNode<T> PhiAt(size_t index) {
    // TODO(jgruber): Investigate issues on ptr compression bots and enable.
    // DCHECK(IsMachineRepresentationOf<T>(representations_[index]));
    return TNode<T>::UncheckedCast(PhiAt(index));
  }

163 164 165 166 167 168 169
  GraphAssemblerLabel(GraphAssemblerLabelType type, BasicBlock* basic_block,
                      int loop_nesting_level,
                      const std::array<MachineRepresentation, VarCount>& reps)
      : type_(type),
        basic_block_(basic_block),
        loop_nesting_level_(loop_nesting_level),
        representations_(reps) {}
170

171
  ~GraphAssemblerLabel() { DCHECK(IsBound() || merged_count_ == 0); }
172 173 174 175 176 177 178 179 180

 private:
  friend class GraphAssembler;

  void SetBound() {
    DCHECK(!IsBound());
    is_bound_ = true;
  }
  bool IsBound() const { return is_bound_; }
181 182 183 184
  bool IsDeferred() const {
    return type_ == GraphAssemblerLabelType::kDeferred;
  }
  bool IsLoop() const { return type_ == GraphAssemblerLabelType::kLoop; }
185
  BasicBlock* basic_block() { return basic_block_; }
186 187

  bool is_bound_ = false;
188 189 190
  const GraphAssemblerLabelType type_;
  BasicBlock* const basic_block_;
  const int loop_nesting_level_;
191
  size_t merged_count_ = 0;
192 193
  Node* effect_;
  Node* control_;
194
  std::array<Node*, VarCount> bindings_;
195
  const std::array<MachineRepresentation, VarCount> representations_;
196 197
};

198
using NodeChangedCallback = std::function<void(Node*)>;
199
class V8_EXPORT_PRIVATE GraphAssembler {
200
 public:
201 202
  // Constructs a GraphAssembler. If {schedule} is not null, the graph assembler
  // will maintain the schedule as it updates blocks.
203 204 205 206
  GraphAssembler(
      MachineGraph* jsgraph, Zone* zone,
      base::Optional<NodeChangedCallback> node_changed_callback = base::nullopt,
      Schedule* schedule = nullptr, bool mark_loop_exits = false);
207
  virtual ~GraphAssembler();
208

209 210
  void Reset(BasicBlock* block);
  void InitializeEffectControl(Node* effect, Node* control);
211

212 213
  // Create label.
  template <typename... Reps>
214
  GraphAssemblerLabel<sizeof...(Reps)> MakeLabelFor(
215
      GraphAssemblerLabelType type, Reps... reps) {
216 217 218 219 220 221 222 223 224 225
    std::array<MachineRepresentation, sizeof...(Reps)> reps_array = {reps...};
    return MakeLabel<sizeof...(Reps)>(reps_array, type);
  }

  // As above, but with an std::array of machine representations.
  template <int VarCount>
  GraphAssemblerLabel<VarCount> MakeLabel(
      std::array<MachineRepresentation, VarCount> reps_array,
      GraphAssemblerLabelType type) {
    return GraphAssemblerLabel<VarCount>(
226
        type, NewBasicBlock(type == GraphAssemblerLabelType::kDeferred),
227
        loop_nesting_level_, reps_array);
228 229
  }

230 231
  // Convenience wrapper for creating non-deferred labels.
  template <typename... Reps>
232
  GraphAssemblerLabel<sizeof...(Reps)> MakeLabel(Reps... reps) {
233
    return MakeLabelFor(GraphAssemblerLabelType::kNonDeferred, reps...);
234 235
  }

236 237
  // Convenience wrapper for creating loop labels.
  template <typename... Reps>
238
  GraphAssemblerLabel<sizeof...(Reps)> MakeLoopLabel(Reps... reps) {
239 240 241
    return MakeLabelFor(GraphAssemblerLabelType::kLoop, reps...);
  }

242
  // Convenience wrapper for creating deferred labels.
243
  template <typename... Reps>
244
  GraphAssemblerLabel<sizeof...(Reps)> MakeDeferredLabel(Reps... reps) {
245
    return MakeLabelFor(GraphAssemblerLabelType::kDeferred, reps...);
246 247 248 249
  }

  // Value creation.
  Node* IntPtrConstant(intptr_t value);
250
  Node* UintPtrConstant(uintptr_t value);
251
  Node* Uint32Constant(uint32_t value);
252
  Node* Int32Constant(int32_t value);
253
  Node* Int64Constant(int64_t value);
254
  Node* UniqueIntPtrConstant(intptr_t value);
255 256 257
  Node* Float64Constant(double value);
  Node* Projection(int index, Node* value);
  Node* ExternalConstant(ExternalReference ref);
258

259 260
  Node* Parameter(int index);

261 262
  Node* LoadFramePointer();

263 264
  Node* LoadHeapNumberValue(Node* heap_number);

265 266 267 268 269 270 271 272 273
#define PURE_UNOP_DECL(Name) Node* Name(Node* input);
  PURE_ASSEMBLER_MACH_UNOP_LIST(PURE_UNOP_DECL)
#undef PURE_UNOP_DECL

#define BINOP_DECL(Name) Node* Name(Node* left, Node* right);
  PURE_ASSEMBLER_MACH_BINOP_LIST(BINOP_DECL)
  CHECKED_ASSEMBLER_MACH_BINOP_LIST(BINOP_DECL)
#undef BINOP_DECL

274 275 276 277 278 279
#ifdef V8_MAP_PACKING
  Node* PackMapWord(TNode<Map> map);
  TNode<Map> UnpackMapWord(Node* map_word);
#endif
  TNode<Map> LoadMap(Node* object);

280 281
  Node* DebugBreak();

282 283 284 285 286 287 288 289 290 291 292 293
  // Unreachable nodes are similar to Goto in that they reset effect/control to
  // nullptr and it's thus not possible to append other nodes without first
  // binding a new label.
  // The block_updater_successor label is a crutch to work around block updater
  // weaknesses (see the related comment in ConnectUnreachableToEnd); if the
  // block updater exists, we cannot connect unreachable to end, instead we
  // must preserve the Goto pattern.
  Node* Unreachable(GraphAssemblerLabel<0u>* block_updater_successor = nullptr);
  // This special variant doesn't connect the Unreachable node to end, and does
  // not reset current effect/control. Intended only for special use-cases like
  // lowering DeadValue.
  Node* UnreachableWithoutConnectToEnd();
294

295 296 297
  Node* IntPtrEqual(Node* left, Node* right);
  Node* TaggedEqual(Node* left, Node* right);

298 299 300
  Node* SmiSub(Node* left, Node* right);
  Node* SmiLessThan(Node* left, Node* right);

301
  Node* Float64RoundDown(Node* value);
302
  Node* Float64RoundTruncate(Node* value);
303
  Node* TruncateFloat64ToInt64(Node* value, TruncateKind kind);
304

305
  Node* BitcastWordToTagged(Node* value);
306
  Node* BitcastWordToTaggedSigned(Node* value);
307
  Node* BitcastTaggedToWord(Node* value);
308
  Node* BitcastTaggedToWordForTagAndSmiBits(Node* value);
309
  Node* BitcastMaybeObjectToWord(Node* value);
310 311

  Node* TypeGuard(Type type, Node* value);
312
  Node* Checkpoint(FrameState frame_state);
313

314 315
  TNode<RawPtrT> StackSlot(int size, int alignment);

316
  Node* Store(StoreRepresentation rep, Node* object, Node* offset, Node* value);
317
  Node* Store(StoreRepresentation rep, Node* object, int offset, Node* value);
318
  Node* Load(MachineType type, Node* object, Node* offset);
319
  Node* Load(MachineType type, Node* object, int offset);
320

321 322
  Node* StoreUnaligned(MachineRepresentation rep, Node* object, Node* offset,
                       Node* value);
323
  Node* LoadUnaligned(MachineType type, Node* object, Node* offset);
324

325 326 327 328
  Node* ProtectedStore(MachineRepresentation rep, Node* object, Node* offset,
                       Node* value);
  Node* ProtectedLoad(MachineType type, Node* object, Node* offset);

329 330 331
  Node* Retain(Node* buffer);
  Node* UnsafePointerAdd(Node* base, Node* external);

332 333
  Node* Word32PoisonOnSpeculation(Node* value);

334
  Node* DeoptimizeIf(
335
      DeoptimizeReason reason, FeedbackSource const& feedback, Node* condition,
336 337
      Node* frame_state,
      IsSafetyCheck is_safety_check = IsSafetyCheck::kSafetyCheck);
338 339 340 341
  Node* DeoptimizeIf(
      DeoptimizeKind kind, DeoptimizeReason reason,
      FeedbackSource const& feedback, Node* condition, Node* frame_state,
      IsSafetyCheck is_safety_check = IsSafetyCheck::kSafetyCheck);
342 343 344 345
  Node* DeoptimizeIfNot(
      DeoptimizeKind kind, DeoptimizeReason reason,
      FeedbackSource const& feedback, Node* condition, Node* frame_state,
      IsSafetyCheck is_safety_check = IsSafetyCheck::kSafetyCheck);
346
  Node* DeoptimizeIfNot(
347
      DeoptimizeReason reason, FeedbackSource const& feedback, Node* condition,
348 349
      Node* frame_state,
      IsSafetyCheck is_safety_check = IsSafetyCheck::kSafetyCheck);
350 351 352
  Node* DynamicCheckMapsWithDeoptUnless(Node* condition, Node* slot_index,
                                        Node* map, Node* handler,
                                        Node* frame_state);
353 354 355
  TNode<Object> Call(const CallDescriptor* call_descriptor, int inputs_size,
                     Node** inputs);
  TNode<Object> Call(const Operator* op, int inputs_size, Node** inputs);
356
  template <typename... Args>
357 358
  TNode<Object> Call(const CallDescriptor* call_descriptor, Node* first_arg,
                     Args... args);
359
  template <typename... Args>
360
  TNode<Object> Call(const Operator* op, Node* first_arg, Args... args);
361 362
  void TailCall(const CallDescriptor* call_descriptor, int inputs_size,
                Node** inputs);
363 364

  // Basic control operations.
365 366
  template <size_t VarCount>
  void Bind(GraphAssemblerLabel<VarCount>* label);
367

368 369
  template <typename... Vars>
  void Goto(GraphAssemblerLabel<sizeof...(Vars)>* label, Vars...);
370

371 372 373 374 375 376 377 378 379 380 381 382 383 384 385
  // Branch hints are inferred from if_true/if_false deferred states.
  void BranchWithCriticalSafetyCheck(Node* condition,
                                     GraphAssemblerLabel<0u>* if_true,
                                     GraphAssemblerLabel<0u>* if_false);

  // Branch hints are inferred from if_true/if_false deferred states.
  template <typename... Vars>
  void Branch(Node* condition, GraphAssemblerLabel<sizeof...(Vars)>* if_true,
              GraphAssemblerLabel<sizeof...(Vars)>* if_false, Vars...);

  template <typename... Vars>
  void BranchWithHint(Node* condition,
                      GraphAssemblerLabel<sizeof...(Vars)>* if_true,
                      GraphAssemblerLabel<sizeof...(Vars)>* if_false,
                      BranchHint hint, Vars...);
386 387

  // Control helpers.
388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403

  // {GotoIf(c, l, h)} is equivalent to {BranchWithHint(c, l, templ, h);
  // Bind(templ)}.
  template <typename... Vars>
  void GotoIf(Node* condition, GraphAssemblerLabel<sizeof...(Vars)>* label,
              BranchHint hint, Vars...);

  // {GotoIfNot(c, l, h)} is equivalent to {BranchWithHint(c, templ, l, h);
  // Bind(templ)}.
  // The branch hint refers to the expected outcome of the provided condition,
  // so {GotoIfNot(..., BranchHint::kTrue)} means "optimize for the case where
  // the branch is *not* taken".
  template <typename... Vars>
  void GotoIfNot(Node* condition, GraphAssemblerLabel<sizeof...(Vars)>* label,
                 BranchHint hint, Vars...);

404
  // {GotoIf(c, l)} is equivalent to {Branch(c, l, templ);Bind(templ)}.
405 406 407
  template <typename... Vars>
  void GotoIf(Node* condition, GraphAssemblerLabel<sizeof...(Vars)>* label,
              Vars...);
408

409
  // {GotoIfNot(c, l)} is equivalent to {Branch(c, templ, l);Bind(templ)}.
410
  template <typename... Vars>
411 412
  void GotoIfNot(Node* condition, GraphAssemblerLabel<sizeof...(Vars)>* label,
                 Vars...);
413

414 415 416 417 418 419 420
  bool HasActiveBlock() const {
    // This is false if the current block has been terminated (e.g. by a Goto or
    // Unreachable). In that case, a new label must be bound before we can
    // continue emitting nodes.
    return control() != nullptr;
  }

421
  // Updates current effect and control based on outputs of {node}.
422 423
  V8_INLINE void UpdateEffectControlWith(Node* node) {
    if (node->op()->EffectOutputCount() > 0) {
424
      effect_ = node;
425 426
    }
    if (node->op()->ControlOutputCount() > 0) {
427
      control_ = node;
428 429
    }
  }
430 431 432 433 434

  // Adds {node} to the current position and updates assembler's current effect
  // and control.
  Node* AddNode(Node* node);

435 436 437 438 439
  template <typename T>
  TNode<T> AddNode(Node* node) {
    return TNode<T>::UncheckedCast(AddNode(node));
  }

440 441 442 443 444 445
  // Finalizes the {block} being processed by the assembler, returning the
  // finalized block (which may be different from the original block).
  BasicBlock* FinalizeCurrentBlock(BasicBlock* block);

  void ConnectUnreachableToEnd();

446 447 448 449 450 451 452 453 454 455
  // Add an inline reducers such that nodes added to the graph will be run
  // through the reducers and possibly further lowered. Each reducer should
  // operate on independent node types since once a reducer changes a node we
  // no longer run any other reducers on that node. The reducers should also
  // only generate new nodes that wouldn't be further reduced, as new nodes
  // generated by a reducer won't be passed through the reducers again.
  void AddInlineReducer(Reducer* reducer) {
    inline_reducers_.push_back(reducer);
  }

456 457
  Control control() const { return Control(control_); }
  Effect effect() const { return Effect(effect_); }
458

459
 protected:
460 461
  class BasicBlockUpdater;

462 463
  template <typename... Vars>
  void MergeState(GraphAssemblerLabel<sizeof...(Vars)>* label, Vars... vars);
464 465 466 467 468 469
  BasicBlock* NewBasicBlock(bool deferred);
  void BindBasicBlock(BasicBlock* block);
  void GotoBasicBlock(BasicBlock* block);
  void GotoIfBasicBlock(BasicBlock* block, Node* branch,
                        IrOpcode::Value goto_if);

470
  V8_INLINE Node* AddClonedNode(Node* node);
471

472 473
  MachineGraph* mcgraph() const { return mcgraph_; }
  Graph* graph() const { return mcgraph_->graph(); }
474
  Zone* temp_zone() const { return temp_zone_; }
475 476
  CommonOperatorBuilder* common() const { return mcgraph()->common(); }
  MachineOperatorBuilder* machine() const { return mcgraph()->machine(); }
477

478 479 480 481 482 483
  // Updates machinery for creating {LoopExit,LoopExitEffect,LoopExitValue}
  // nodes on loop exits (which are necessary for loop peeling).
  //
  // All labels created while a LoopScope is live are considered to be inside
  // the loop.
  template <MachineRepresentation... Reps>
484
  class V8_NODISCARD LoopScope final {
485 486 487
   private:
    // The internal scope is only here to increment the graph assembler's
    // nesting level prior to `loop_header_label` creation below.
488
    class V8_NODISCARD LoopScopeInternal {
489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534
     public:
      explicit LoopScopeInternal(GraphAssembler* gasm)
          : previous_loop_nesting_level_(gasm->loop_nesting_level_),
            gasm_(gasm) {
        gasm->loop_nesting_level_++;
      }

      ~LoopScopeInternal() {
        gasm_->loop_nesting_level_--;
        DCHECK_EQ(gasm_->loop_nesting_level_, previous_loop_nesting_level_);
      }

     private:
      const int previous_loop_nesting_level_;
      GraphAssembler* const gasm_;
    };

   public:
    explicit LoopScope(GraphAssembler* gasm)
        : internal_scope_(gasm),
          gasm_(gasm),
          loop_header_label_(gasm->MakeLoopLabel(Reps...)) {
      // This feature may only be used if it has been enabled.
      DCHECK(gasm_->mark_loop_exits_);
      gasm->loop_headers_.push_back(&loop_header_label_.control_);
      DCHECK_EQ(static_cast<int>(gasm_->loop_headers_.size()),
                gasm_->loop_nesting_level_);
    }

    ~LoopScope() {
      DCHECK_EQ(static_cast<int>(gasm_->loop_headers_.size()),
                gasm_->loop_nesting_level_);
      gasm_->loop_headers_.pop_back();
    }

    GraphAssemblerLabel<sizeof...(Reps)>* loop_header_label() {
      return &loop_header_label_;
    }

   private:
    const LoopScopeInternal internal_scope_;
    GraphAssembler* const gasm_;
    GraphAssemblerLabel<sizeof...(Reps)> loop_header_label_;
  };

  // Upon destruction, restores effect and control to the state at construction.
535
  class V8_NODISCARD RestoreEffectControlScope {
536 537 538 539 540 541 542 543 544 545 546 547 548 549 550
   public:
    explicit RestoreEffectControlScope(GraphAssembler* gasm)
        : gasm_(gasm), effect_(gasm->effect()), control_(gasm->control()) {}

    ~RestoreEffectControlScope() {
      gasm_->effect_ = effect_;
      gasm_->control_ = control_;
    }

   private:
    GraphAssembler* const gasm_;
    const Effect effect_;
    const Control control_;
  };

551
 private:
552 553
  class BlockInlineReduction;

554 555 556 557 558 559 560 561 562 563
  template <typename... Vars>
  void BranchImpl(Node* condition,
                  GraphAssemblerLabel<sizeof...(Vars)>* if_true,
                  GraphAssemblerLabel<sizeof...(Vars)>* if_false,
                  BranchHint hint, IsSafetyCheck is_safety_check, Vars...);
  void RecordBranchInBlockUpdater(Node* branch, Node* if_true_control,
                                  Node* if_false_control,
                                  BasicBlock* if_true_block,
                                  BasicBlock* if_false_block);

564
  Zone* temp_zone_;
565
  MachineGraph* mcgraph_;
566 567
  Node* effect_;
  Node* control_;
568 569 570
  // {node_changed_callback_} should be called when a node outside the
  // subgraph created by the graph assembler changes.
  base::Optional<NodeChangedCallback> node_changed_callback_;
571
  std::unique_ptr<BasicBlockUpdater> block_updater_;
572

573 574 575 576 577
  // Inline reducers enable reductions to be performed to nodes as they are
  // added to the graph with the graph assembler.
  ZoneVector<Reducer*> inline_reducers_;
  bool inline_reductions_blocked_;

578 579 580 581 582 583 584 585 586
  // Track loop information in order to properly mark loop exits with
  // {LoopExit,LoopExitEffect,LoopExitValue} nodes. The outermost level has
  // a nesting level of 0. See also GraphAssembler::LoopScope.
  int loop_nesting_level_ = 0;
  ZoneVector<Node**> loop_headers_;

  // Feature configuration. As more features are added, this should be turned
  // into a bitfield.
  const bool mark_loop_exits_;
587 588
};

589 590
template <size_t VarCount>
Node* GraphAssemblerLabel<VarCount>::PhiAt(size_t index) {
591
  DCHECK(IsBound());
592 593
  DCHECK_LT(index, VarCount);
  return bindings_[index];
594 595
}

596 597 598
template <typename... Vars>
void GraphAssembler::MergeState(GraphAssemblerLabel<sizeof...(Vars)>* label,
                                Vars... vars) {
599 600 601
  RestoreEffectControlScope restore_effect_control_scope(this);

  const int merged_count = static_cast<int>(label->merged_count_);
602 603
  static constexpr int kVarCount = sizeof...(vars);
  std::array<Node*, kVarCount> var_array = {vars...};
604 605 606 607 608 609 610 611 612 613 614 615 616 617

  const bool is_loop_exit = label->loop_nesting_level_ != loop_nesting_level_;
  if (is_loop_exit) {
    // This feature may only be used if it has been enabled.
    USE(mark_loop_exits_);
    DCHECK(mark_loop_exits_);
    // Jumping from loops to loops not supported.
    DCHECK(!label->IsLoop());
    // Currently only the simple case of jumping one level is supported.
    DCHECK_EQ(label->loop_nesting_level_, loop_nesting_level_ - 1);
    DCHECK(!loop_headers_.empty());
    DCHECK_NOT_NULL(*loop_headers_.back());

    // Mark this exit to enable loop peeling.
618 619 620
    AddNode(graph()->NewNode(common()->LoopExit(), control(),
                             *loop_headers_.back()));
    AddNode(graph()->NewNode(common()->LoopExitEffect(), effect(), control()));
621
    for (size_t i = 0; i < kVarCount; i++) {
622 623 624
      var_array[i] = AddNode(graph()->NewNode(
          common()->LoopExitValue(MachineRepresentation::kTagged), var_array[i],
          control()));
625 626 627
    }
  }

628 629 630
  if (label->IsLoop()) {
    if (merged_count == 0) {
      DCHECK(!label->IsBound());
631 632 633 634
      label->control_ =
          graph()->NewNode(common()->Loop(2), control(), control());
      label->effect_ = graph()->NewNode(common()->EffectPhi(2), effect(),
                                        effect(), label->control_);
635 636 637
      Node* terminate = graph()->NewNode(common()->Terminate(), label->effect_,
                                         label->control_);
      NodeProperties::MergeControlToEnd(graph(), common(), terminate);
638 639 640 641
      for (size_t i = 0; i < kVarCount; i++) {
        label->bindings_[i] =
            graph()->NewNode(common()->Phi(label->representations_[i], 2),
                             var_array[i], var_array[i], label->control_);
642 643 644 645
      }
    } else {
      DCHECK(label->IsBound());
      DCHECK_EQ(1, merged_count);
646 647
      label->control_->ReplaceInput(1, control());
      label->effect_->ReplaceInput(1, effect());
648 649
      for (size_t i = 0; i < kVarCount; i++) {
        label->bindings_[i]->ReplaceInput(1, var_array[i]);
650
        CHECK(!NodeProperties::IsTyped(var_array[i]));  // Unsupported.
651
      }
652 653
    }
  } else {
654
    DCHECK(!label->IsLoop());
655 656 657
    DCHECK(!label->IsBound());
    if (merged_count == 0) {
      // Just set the control, effect and variables directly.
658 659
      label->control_ = control();
      label->effect_ = effect();
660 661
      for (size_t i = 0; i < kVarCount; i++) {
        label->bindings_[i] = var_array[i];
662 663 664
      }
    } else if (merged_count == 1) {
      // Create merge, effect phi and a phi for each variable.
665 666
      label->control_ =
          graph()->NewNode(common()->Merge(2), label->control_, control());
667
      label->effect_ = graph()->NewNode(common()->EffectPhi(2), label->effect_,
668
                                        effect(), label->control_);
669
      for (size_t i = 0; i < kVarCount; i++) {
670 671
        label->bindings_[i] = graph()->NewNode(
            common()->Phi(label->representations_[i], 2), label->bindings_[i],
672
            var_array[i], label->control_);
673 674 675 676
      }
    } else {
      // Append to the merge, effect phi and phis.
      DCHECK_EQ(IrOpcode::kMerge, label->control_->opcode());
677
      label->control_->AppendInput(graph()->zone(), control());
678 679 680 681
      NodeProperties::ChangeOp(label->control_,
                               common()->Merge(merged_count + 1));

      DCHECK_EQ(IrOpcode::kEffectPhi, label->effect_->opcode());
682
      label->effect_->ReplaceInput(merged_count, effect());
683 684 685 686
      label->effect_->AppendInput(graph()->zone(), label->control_);
      NodeProperties::ChangeOp(label->effect_,
                               common()->EffectPhi(merged_count + 1));

687
      for (size_t i = 0; i < kVarCount; i++) {
688
        DCHECK_EQ(IrOpcode::kPhi, label->bindings_[i]->opcode());
689
        label->bindings_[i]->ReplaceInput(merged_count, var_array[i]);
690 691 692 693
        label->bindings_[i]->AppendInput(graph()->zone(), label->control_);
        NodeProperties::ChangeOp(
            label->bindings_[i],
            common()->Phi(label->representations_[i], merged_count + 1));
694 695 696 697 698 699 700
        if (NodeProperties::IsTyped(label->bindings_[i])) {
          CHECK(NodeProperties::IsTyped(var_array[i]));
          Type old_type = NodeProperties::GetType(label->bindings_[i]);
          Type new_type = Type::Union(
              old_type, NodeProperties::GetType(var_array[i]), graph()->zone());
          NodeProperties::SetType(label->bindings_[i], new_type);
        }
701
      }
702
    }
703
  }
704
  label->merged_count_++;
705 706
}

707 708
template <size_t VarCount>
void GraphAssembler::Bind(GraphAssemblerLabel<VarCount>* label) {
709 710
  DCHECK_NULL(control());
  DCHECK_NULL(effect());
711
  DCHECK_LT(0, label->merged_count_);
712
  DCHECK_EQ(label->loop_nesting_level_, loop_nesting_level_);
713

714 715
  control_ = label->control_;
  effect_ = label->effect_;
716
  BindBasicBlock(label->basic_block());
717 718

  label->SetBound();
719 720 721 722 723 724 725 726 727 728

  if (label->merged_count_ > 1 || label->IsLoop()) {
    AddNode(label->control_);
    AddNode(label->effect_);
    for (size_t i = 0; i < VarCount; i++) {
      AddNode(label->bindings_[i]);
    }
  } else {
    // If the basic block does not have a control node, insert a dummy
    // Merge node, so that other passes have a control node to start from.
729
    control_ = AddNode(graph()->NewNode(common()->Merge(1), control()));
730
  }
731 732
}

733 734 735 736 737 738 739 740 741 742 743 744 745 746 747 748 749 750 751 752 753 754 755 756 757 758 759 760 761 762 763 764 765 766 767 768 769 770 771 772 773 774 775 776 777 778 779 780 781 782 783
template <typename... Vars>
void GraphAssembler::Branch(Node* condition,
                            GraphAssemblerLabel<sizeof...(Vars)>* if_true,
                            GraphAssemblerLabel<sizeof...(Vars)>* if_false,
                            Vars... vars) {
  BranchHint hint = BranchHint::kNone;
  if (if_true->IsDeferred() != if_false->IsDeferred()) {
    hint = if_false->IsDeferred() ? BranchHint::kTrue : BranchHint::kFalse;
  }

  BranchImpl(condition, if_true, if_false, hint, IsSafetyCheck::kNoSafetyCheck,
             vars...);
}

template <typename... Vars>
void GraphAssembler::BranchWithHint(
    Node* condition, GraphAssemblerLabel<sizeof...(Vars)>* if_true,
    GraphAssemblerLabel<sizeof...(Vars)>* if_false, BranchHint hint,
    Vars... vars) {
  BranchImpl(condition, if_true, if_false, hint, IsSafetyCheck::kNoSafetyCheck,
             vars...);
}

template <typename... Vars>
void GraphAssembler::BranchImpl(Node* condition,
                                GraphAssemblerLabel<sizeof...(Vars)>* if_true,
                                GraphAssemblerLabel<sizeof...(Vars)>* if_false,
                                BranchHint hint, IsSafetyCheck is_safety_check,
                                Vars... vars) {
  DCHECK_NOT_NULL(control());

  Node* branch = graph()->NewNode(common()->Branch(hint, is_safety_check),
                                  condition, control());

  Node* if_true_control = control_ =
      graph()->NewNode(common()->IfTrue(), branch);
  MergeState(if_true, vars...);

  Node* if_false_control = control_ =
      graph()->NewNode(common()->IfFalse(), branch);
  MergeState(if_false, vars...);

  if (block_updater_) {
    RecordBranchInBlockUpdater(branch, if_true_control, if_false_control,
                               if_true->basic_block(), if_false->basic_block());
  }

  control_ = nullptr;
  effect_ = nullptr;
}

784 785 786
template <typename... Vars>
void GraphAssembler::Goto(GraphAssemblerLabel<sizeof...(Vars)>* label,
                          Vars... vars) {
787 788
  DCHECK_NOT_NULL(control());
  DCHECK_NOT_NULL(effect());
789
  MergeState(label, vars...);
790 791
  GotoBasicBlock(label->basic_block());

792 793
  control_ = nullptr;
  effect_ = nullptr;
794 795
}

796 797 798
template <typename... Vars>
void GraphAssembler::GotoIf(Node* condition,
                            GraphAssemblerLabel<sizeof...(Vars)>* label,
799
                            BranchHint hint, Vars... vars) {
800
  Node* branch = graph()->NewNode(common()->Branch(hint), condition, control());
801

802
  control_ = graph()->NewNode(common()->IfTrue(), branch);
803 804
  MergeState(label, vars...);

805
  GotoIfBasicBlock(label->basic_block(), branch, IrOpcode::kIfTrue);
806
  control_ = AddNode(graph()->NewNode(common()->IfFalse(), branch));
807 808
}

809
template <typename... Vars>
810 811
void GraphAssembler::GotoIfNot(Node* condition,
                               GraphAssemblerLabel<sizeof...(Vars)>* label,
812
                               BranchHint hint, Vars... vars) {
813
  Node* branch = graph()->NewNode(common()->Branch(hint), condition, control());
814

815
  control_ = graph()->NewNode(common()->IfFalse(), branch);
816 817
  MergeState(label, vars...);

818
  GotoIfBasicBlock(label->basic_block(), branch, IrOpcode::kIfFalse);
819
  control_ = AddNode(graph()->NewNode(common()->IfTrue(), branch));
820 821
}

822 823 824 825 826 827 828 829 830 831 832 833 834 835 836 837 838
template <typename... Vars>
void GraphAssembler::GotoIf(Node* condition,
                            GraphAssemblerLabel<sizeof...(Vars)>* label,
                            Vars... vars) {
  BranchHint hint =
      label->IsDeferred() ? BranchHint::kFalse : BranchHint::kNone;
  return GotoIf(condition, label, hint, vars...);
}

template <typename... Vars>
void GraphAssembler::GotoIfNot(Node* condition,
                               GraphAssemblerLabel<sizeof...(Vars)>* label,
                               Vars... vars) {
  BranchHint hint = label->IsDeferred() ? BranchHint::kTrue : BranchHint::kNone;
  return GotoIfNot(condition, label, hint, vars...);
}

839
template <typename... Args>
840 841
TNode<Object> GraphAssembler::Call(const CallDescriptor* call_descriptor,
                                   Node* first_arg, Args... args) {
842
  const Operator* op = common()->Call(call_descriptor);
843
  return Call(op, first_arg, args...);
844 845 846
}

template <typename... Args>
847 848 849 850
TNode<Object> GraphAssembler::Call(const Operator* op, Node* first_arg,
                                   Args... args) {
  Node* args_array[] = {first_arg, args..., effect(), control()};
  int size = static_cast<int>(1 + sizeof...(args)) + op->EffectInputCount() +
851
             op->ControlInputCount();
852
  return Call(op, size, args_array);
853 854
}

855 856 857 858
class V8_EXPORT_PRIVATE JSGraphAssembler : public GraphAssembler {
 public:
  // Constructs a JSGraphAssembler. If {schedule} is not null, the graph
  // assembler will maintain the schedule as it updates blocks.
859 860 861 862 863 864
  JSGraphAssembler(
      JSGraph* jsgraph, Zone* zone,
      base::Optional<NodeChangedCallback> node_changed_callback = base::nullopt,
      Schedule* schedule = nullptr, bool mark_loop_exits = false)
      : GraphAssembler(jsgraph, zone, node_changed_callback, schedule,
                       mark_loop_exits),
865
        jsgraph_(jsgraph) {}
866 867 868 869 870 871 872 873 874 875 876 877 878 879 880 881 882 883 884 885 886 887 888 889 890 891 892 893 894 895 896 897 898 899 900 901 902 903 904 905 906 907

  Node* SmiConstant(int32_t value);
  TNode<HeapObject> HeapConstant(Handle<HeapObject> object);
  TNode<Object> Constant(const ObjectRef& ref);
  TNode<Number> NumberConstant(double value);
  Node* CEntryStubConstant(int result_size);

#define SINGLETON_CONST_DECL(Name, Type) TNode<Type> Name##Constant();
  JSGRAPH_SINGLETON_CONSTANT_LIST(SINGLETON_CONST_DECL)
#undef SINGLETON_CONST_DECL

#define SINGLETON_CONST_TEST_DECL(Name, ...) \
  TNode<Boolean> Is##Name(TNode<Object> value);
  JSGRAPH_SINGLETON_CONSTANT_LIST(SINGLETON_CONST_TEST_DECL)
#undef SINGLETON_CONST_TEST_DECL

  Node* Allocate(AllocationType allocation, Node* size);
  Node* LoadField(FieldAccess const&, Node* object);
  template <typename T>
  TNode<T> LoadField(FieldAccess const& access, TNode<HeapObject> object) {
    // TODO(jgruber): Investigate issues on ptr compression bots and enable.
    // DCHECK(IsMachineRepresentationOf<T>(
    //     access.machine_type.representation()));
    return TNode<T>::UncheckedCast(LoadField(access, object));
  }
  Node* LoadElement(ElementAccess const&, Node* object, Node* index);
  template <typename T>
  TNode<T> LoadElement(ElementAccess const& access, TNode<HeapObject> object,
                       TNode<Number> index) {
    // TODO(jgruber): Investigate issues on ptr compression bots and enable.
    // DCHECK(IsMachineRepresentationOf<T>(
    //     access.machine_type.representation()));
    return TNode<T>::UncheckedCast(LoadElement(access, object, index));
  }
  Node* StoreField(FieldAccess const&, Node* object, Node* value);
  Node* StoreElement(ElementAccess const&, Node* object, Node* index,
                     Node* value);
  void TransitionAndStoreElement(MapRef double_map, MapRef fast_map,
                                 TNode<HeapObject> object, TNode<Number> index,
                                 TNode<Object> value);
  TNode<Number> StringLength(TNode<String> string);
  TNode<Boolean> ReferenceEqual(TNode<Object> lhs, TNode<Object> rhs);
908
  TNode<Number> PlainPrimitiveToNumber(TNode<Object> value);
909 910 911 912 913 914 915 916 917
  TNode<Number> NumberMin(TNode<Number> lhs, TNode<Number> rhs);
  TNode<Number> NumberMax(TNode<Number> lhs, TNode<Number> rhs);
  TNode<Boolean> NumberLessThan(TNode<Number> lhs, TNode<Number> rhs);
  TNode<Boolean> NumberLessThanOrEqual(TNode<Number> lhs, TNode<Number> rhs);
  TNode<Number> NumberAdd(TNode<Number> lhs, TNode<Number> rhs);
  TNode<Number> NumberSubtract(TNode<Number> lhs, TNode<Number> rhs);
  TNode<String> StringSubstring(TNode<String> string, TNode<Number> from,
                                TNode<Number> to);
  TNode<Boolean> ObjectIsCallable(TNode<Object> value);
918
  TNode<Boolean> ObjectIsUndetectable(TNode<Object> value);
919 920 921
  Node* CheckIf(Node* cond, DeoptimizeReason reason);
  TNode<Boolean> NumberIsFloat64Hole(TNode<Number> value);
  TNode<Boolean> ToBoolean(TNode<Object> value);
922
  TNode<Object> ConvertTaggedHoleToUndefined(TNode<Object> value);
923 924 925 926 927 928 929 930 931 932 933 934 935 936
  TNode<FixedArrayBase> MaybeGrowFastElements(ElementsKind kind,
                                              const FeedbackSource& feedback,
                                              TNode<JSArray> array,
                                              TNode<FixedArrayBase> elements,
                                              TNode<Number> new_length,
                                              TNode<Number> old_length);

  JSGraph* jsgraph() const { return jsgraph_; }
  Isolate* isolate() const { return jsgraph()->isolate(); }
  SimplifiedOperatorBuilder* simplified() const {
    return jsgraph()->simplified();
  }

 protected:
937
  Operator const* PlainPrimitiveToNumberOperator();
938 939 940 941 942 943

 private:
  JSGraph* jsgraph_;
  SetOncePointer<Operator const> to_number_operator_;
};

944 945 946 947 948
}  // namespace compiler
}  // namespace internal
}  // namespace v8

#endif  // V8_COMPILER_GRAPH_ASSEMBLER_H_