graph-assembler.h 19.2 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/compiler/feedback-source.h"
9 10 11 12 13 14 15 16 17 18 19 20
#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;

namespace compiler {

21 22 23
class Schedule;
class BasicBlock;

24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48
#define PURE_ASSEMBLER_MACH_UNOP_LIST(V) \
  V(ChangeInt32ToInt64)                  \
  V(ChangeInt32ToFloat64)                \
  V(ChangeInt64ToFloat64)                \
  V(ChangeUint32ToFloat64)               \
  V(ChangeUint32ToUint64)                \
  V(ChangeFloat64ToInt32)                \
  V(ChangeFloat64ToInt64)                \
  V(ChangeFloat64ToUint32)               \
  V(TruncateInt64ToInt32)                \
  V(RoundFloat64ToInt32)                 \
  V(TruncateFloat64ToInt64)              \
  V(TruncateFloat64ToWord32)             \
  V(Float64ExtractLowWord32)             \
  V(Float64ExtractHighWord32)            \
  V(BitcastInt32ToFloat32)               \
  V(BitcastInt64ToFloat64)               \
  V(BitcastFloat32ToInt32)               \
  V(BitcastFloat64ToInt64)               \
  V(Float64Abs)                          \
  V(Word32ReverseBytes)                  \
  V(Word64ReverseBytes)                  \
  V(Float64SilenceNaN)                   \
  V(ChangeTaggedToCompressed)

49 50 51 52 53 54
#define PURE_ASSEMBLER_MACH_BINOP_LIST(V) \
  V(WordShl)                              \
  V(WordSar)                              \
  V(WordAnd)                              \
  V(Word32Or)                             \
  V(Word32And)                            \
55
  V(Word32Xor)                            \
56 57
  V(Word32Shr)                            \
  V(Word32Shl)                            \
58
  V(Word32Sar)                            \
59
  V(Word64And)                            \
60 61
  V(IntAdd)                               \
  V(IntSub)                               \
62
  V(IntMul)                               \
63
  V(IntLessThan)                          \
64
  V(UintLessThan)                         \
65 66 67 68 69
  V(Int32Add)                             \
  V(Int32Sub)                             \
  V(Int32Mul)                             \
  V(Int32LessThanOrEqual)                 \
  V(Uint32LessThan)                       \
70 71 72
  V(Uint32LessThanOrEqual)                \
  V(Uint64LessThan)                       \
  V(Uint64LessThanOrEqual)                \
73
  V(Int32LessThan)                        \
74
  V(Int64Sub)                             \
75 76
  V(Float64Add)                           \
  V(Float64Sub)                           \
77
  V(Float64Div)                           \
78 79 80 81
  V(Float64Mod)                           \
  V(Float64Equal)                         \
  V(Float64LessThan)                      \
  V(Float64LessThanOrEqual)               \
82 83
  V(Float64InsertLowWord32)               \
  V(Float64InsertHighWord32)              \
84
  V(Word32Equal)                          \
85
  V(Word64Equal)                          \
86 87 88 89 90 91 92 93 94 95 96
  V(WordEqual)

#define CHECKED_ASSEMBLER_MACH_BINOP_LIST(V) \
  V(Int32AddWithOverflow)                    \
  V(Int32SubWithOverflow)                    \
  V(Int32MulWithOverflow)                    \
  V(Int32Mod)                                \
  V(Int32Div)                                \
  V(Uint32Mod)                               \
  V(Uint32Div)

97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114
#define JSGRAPH_SINGLETON_CONSTANT_LIST(V)        \
  V(TrueConstant)                                 \
  V(FalseConstant)                                \
  V(NullConstant)                                 \
  V(BigIntMapConstant)                            \
  V(BooleanMapConstant)                           \
  V(HeapNumberMapConstant)                        \
  V(NoContextConstant)                            \
  V(EmptyStringConstant)                          \
  V(UndefinedConstant)                            \
  V(TheHoleConstant)                              \
  V(FixedArrayMapConstant)                        \
  V(FixedDoubleArrayMapConstant)                  \
  V(ToNumberBuiltinConstant)                      \
  V(AllocateInYoungGenerationStubConstant)        \
  V(AllocateRegularInYoungGenerationStubConstant) \
  V(AllocateInOldGenerationStubConstant)          \
  V(AllocateRegularInOldGenerationStubConstant)
115

116 117
class GraphAssembler;

118
enum class GraphAssemblerLabelType { kDeferred, kNonDeferred, kLoop };
119 120

// Label with statically known count of incoming branches and phis.
121 122
template <size_t VarCount>
class GraphAssemblerLabel {
123 124 125 126
 public:
  Node* PhiAt(size_t index);

  template <typename... Reps>
127 128 129
  explicit GraphAssemblerLabel(GraphAssemblerLabelType type,
                               BasicBlock* basic_block, Reps... reps)
      : type_(type), basic_block_(basic_block) {
130 131 132 133 134 135 136 137
    STATIC_ASSERT(VarCount == sizeof...(reps));
    MachineRepresentation reps_array[] = {MachineRepresentation::kNone,
                                          reps...};
    for (size_t i = 0; i < VarCount; i++) {
      representations_[i] = reps_array[i + 1];
    }
  }

138
  ~GraphAssemblerLabel() { DCHECK(IsBound() || merged_count_ == 0); }
139 140 141 142 143 144 145 146 147

 private:
  friend class GraphAssembler;

  void SetBound() {
    DCHECK(!IsBound());
    is_bound_ = true;
  }
  bool IsBound() const { return is_bound_; }
148 149 150 151
  bool IsDeferred() const {
    return type_ == GraphAssemblerLabelType::kDeferred;
  }
  bool IsLoop() const { return type_ == GraphAssemblerLabelType::kLoop; }
152
  BasicBlock* basic_block() { return basic_block_; }
153 154

  bool is_bound_ = false;
155
  GraphAssemblerLabelType const type_;
156
  BasicBlock* basic_block_;
157
  size_t merged_count_ = 0;
158 159 160
  Node* effect_;
  Node* control_;
  Node* bindings_[VarCount + 1];
161 162 163 164 165
  MachineRepresentation representations_[VarCount + 1];
};

class GraphAssembler {
 public:
166 167 168
  // Constructs a GraphAssembler. If {schedule} is not null, the graph assembler
  // will maintain the schedule as it updates blocks.
  GraphAssembler(JSGraph* jsgraph, Zone* zone, Schedule* schedule = nullptr);
169
  ~GraphAssembler();
170

171 172
  void Reset(BasicBlock* block);
  void InitializeEffectControl(Node* effect, Node* control);
173

174 175
  // Create label.
  template <typename... Reps>
176
  GraphAssemblerLabel<sizeof...(Reps)> MakeLabelFor(
177
      GraphAssemblerLabelType type, Reps... reps) {
178 179 180
    return GraphAssemblerLabel<sizeof...(Reps)>(
        type, NewBasicBlock(type == GraphAssemblerLabelType::kDeferred),
        reps...);
181 182
  }

183 184
  // Convenience wrapper for creating non-deferred labels.
  template <typename... Reps>
185
  GraphAssemblerLabel<sizeof...(Reps)> MakeLabel(Reps... reps) {
186
    return MakeLabelFor(GraphAssemblerLabelType::kNonDeferred, reps...);
187 188
  }

189 190
  // Convenience wrapper for creating loop labels.
  template <typename... Reps>
191
  GraphAssemblerLabel<sizeof...(Reps)> MakeLoopLabel(Reps... reps) {
192 193 194
    return MakeLabelFor(GraphAssemblerLabelType::kLoop, reps...);
  }

195
  // Convenience wrapper for creating deferred labels.
196
  template <typename... Reps>
197
  GraphAssemblerLabel<sizeof...(Reps)> MakeDeferredLabel(Reps... reps) {
198
    return MakeLabelFor(GraphAssemblerLabelType::kDeferred, reps...);
199 200 201 202
  }

  // Value creation.
  Node* IntPtrConstant(intptr_t value);
203
  Node* Uint32Constant(uint32_t value);
204
  Node* Int32Constant(int32_t value);
205
  Node* Int64Constant(int64_t value);
206
  Node* UniqueIntPtrConstant(intptr_t value);
207 208 209 210
  Node* SmiConstant(int32_t value);
  Node* Float64Constant(double value);
  Node* Projection(int index, Node* value);
  Node* HeapConstant(Handle<HeapObject> object);
211
  Node* NumberConstant(double value);
212 213
  Node* CEntryStubConstant(int result_size);
  Node* ExternalConstant(ExternalReference ref);
214

215 216
  Node* LoadFramePointer();

217 218 219
#define SINGLETON_CONST_DECL(Name) Node* Name();
  JSGRAPH_SINGLETON_CONSTANT_LIST(SINGLETON_CONST_DECL)
#undef SINGLETON_CONST_DECL
220 221 222 223 224 225 226 227 228 229

#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

230 231 232
  // Debugging
  Node* DebugBreak();

233 234
  Node* Unreachable();

235 236 237
  Node* IntPtrEqual(Node* left, Node* right);
  Node* TaggedEqual(Node* left, Node* right);

238 239 240
  Node* SmiSub(Node* left, Node* right);
  Node* SmiLessThan(Node* left, Node* right);

241
  Node* Float64RoundDown(Node* value);
242
  Node* Float64RoundTruncate(Node* value);
243 244

  Node* ToNumber(Node* value);
245
  Node* BitcastWordToTagged(Node* value);
246
  Node* BitcastTaggedToWord(Node* value);
247
  Node* BitcastTaggedToWordForTagAndSmiBits(Node* value);
248
  Node* Allocate(AllocationType allocation, Node* size);
249 250 251 252 253 254 255
  Node* LoadField(FieldAccess const&, Node* object);
  Node* LoadElement(ElementAccess const&, Node* object, Node* index);
  Node* StoreField(FieldAccess const&, Node* object, Node* value);
  Node* StoreElement(ElementAccess const&, Node* object, Node* index,
                     Node* value);

  Node* Store(StoreRepresentation rep, Node* object, Node* offset, Node* value);
256
  Node* Load(MachineType type, Node* object, Node* offset);
257

258 259
  Node* StoreUnaligned(MachineRepresentation rep, Node* object, Node* offset,
                       Node* value);
260
  Node* LoadUnaligned(MachineType type, Node* object, Node* offset);
261

262 263 264
  Node* Retain(Node* buffer);
  Node* UnsafePointerAdd(Node* base, Node* external);

265 266
  Node* Word32PoisonOnSpeculation(Node* value);

267
  Node* DeoptimizeIf(
268
      DeoptimizeReason reason, FeedbackSource const& feedback, Node* condition,
269 270
      Node* frame_state,
      IsSafetyCheck is_safety_check = IsSafetyCheck::kSafetyCheck);
271
  Node* DeoptimizeIfNot(
272
      DeoptimizeReason reason, FeedbackSource const& feedback, Node* condition,
273 274
      Node* frame_state,
      IsSafetyCheck is_safety_check = IsSafetyCheck::kSafetyCheck);
275
  template <typename... Args>
276
  Node* Call(const CallDescriptor* call_descriptor, Args... args);
277 278
  template <typename... Args>
  Node* Call(const Operator* op, Args... args);
279 280

  // Basic control operations.
281 282
  template <size_t VarCount>
  void Bind(GraphAssemblerLabel<VarCount>* label);
283

284 285
  template <typename... Vars>
  void Goto(GraphAssemblerLabel<sizeof...(Vars)>* label, Vars...);
286

287
  void Branch(Node* condition, GraphAssemblerLabel<0u>* if_true,
288 289
              GraphAssemblerLabel<0u>* if_false,
              IsSafetyCheck is_safety_check = IsSafetyCheck::kNoSafetyCheck);
290 291 292

  // Control helpers.
  // {GotoIf(c, l)} is equivalent to {Branch(c, l, templ);Bind(templ)}.
293 294 295
  template <typename... Vars>
  void GotoIf(Node* condition, GraphAssemblerLabel<sizeof...(Vars)>* label,
              Vars...);
296

297
  // {GotoIfNot(c, l)} is equivalent to {Branch(c, templ, l);Bind(templ)}.
298
  template <typename... Vars>
299 300
  void GotoIfNot(Node* condition, GraphAssemblerLabel<sizeof...(Vars)>* label,
                 Vars...);
301

302
  // Updates current effect and control based on outputs of {node}.
303 304 305 306 307 308 309 310
  V8_INLINE void UpdateEffectControlWith(Node* node) {
    if (node->op()->EffectOutputCount() > 0) {
      current_effect_ = node;
    }
    if (node->op()->ControlOutputCount() > 0) {
      current_control_ = node;
    }
  }
311 312 313 314 315 316 317 318 319 320 321 322 323

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

  // 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();

  Node* current_control() { return current_control_; }
  Node* current_effect() { return current_effect_; }
324 325

 private:
326 327
  class BasicBlockUpdater;

328 329
  template <typename... Vars>
  void MergeState(GraphAssemblerLabel<sizeof...(Vars)>* label, Vars... vars);
330 331 332 333 334 335
  BasicBlock* NewBasicBlock(bool deferred);
  void BindBasicBlock(BasicBlock* block);
  void GotoBasicBlock(BasicBlock* block);
  void GotoIfBasicBlock(BasicBlock* block, Node* branch,
                        IrOpcode::Value goto_if);

336
  V8_INLINE Node* AddClonedNode(Node* node);
337 338 339 340

  Operator const* ToNumberOperator();

  JSGraph* jsgraph() const { return jsgraph_; }
341
  Isolate* isolate() const { return jsgraph_->isolate(); }
342 343 344 345 346 347 348 349 350 351 352 353 354
  Graph* graph() const { return jsgraph_->graph(); }
  Zone* temp_zone() const { return temp_zone_; }
  CommonOperatorBuilder* common() const { return jsgraph()->common(); }
  MachineOperatorBuilder* machine() const { return jsgraph()->machine(); }
  SimplifiedOperatorBuilder* simplified() const {
    return jsgraph()->simplified();
  }

  SetOncePointer<Operator const> to_number_operator_;
  Zone* temp_zone_;
  JSGraph* jsgraph_;
  Node* current_effect_;
  Node* current_control_;
355
  std::unique_ptr<BasicBlockUpdater> block_updater_;
356 357
};

358 359
template <size_t VarCount>
Node* GraphAssemblerLabel<VarCount>::PhiAt(size_t index) {
360
  DCHECK(IsBound());
361 362
  DCHECK_LT(index, VarCount);
  return bindings_[index];
363 364
}

365 366 367 368
template <typename... Vars>
void GraphAssembler::MergeState(GraphAssemblerLabel<sizeof...(Vars)>* label,
                                Vars... vars) {
  int merged_count = static_cast<int>(label->merged_count_);
369
  Node* var_array[] = {nullptr, vars...};
370 371 372 373 374 375 376
  if (label->IsLoop()) {
    if (merged_count == 0) {
      DCHECK(!label->IsBound());
      label->control_ = graph()->NewNode(common()->Loop(2), current_control_,
                                         current_control_);
      label->effect_ = graph()->NewNode(common()->EffectPhi(2), current_effect_,
                                        current_effect_, label->control_);
377 378 379
      Node* terminate = graph()->NewNode(common()->Terminate(), label->effect_,
                                         label->control_);
      NodeProperties::MergeControlToEnd(graph(), common(), terminate);
380 381 382 383 384 385 386 387 388 389 390 391 392
      for (size_t i = 0; i < sizeof...(vars); i++) {
        label->bindings_[i] = graph()->NewNode(
            common()->Phi(label->representations_[i], 2), var_array[i + 1],
            var_array[i + 1], label->control_);
      }
    } else {
      DCHECK(label->IsBound());
      DCHECK_EQ(1, merged_count);
      label->control_->ReplaceInput(1, current_control_);
      label->effect_->ReplaceInput(1, current_effect_);
      for (size_t i = 0; i < sizeof...(vars); i++) {
        label->bindings_[i]->ReplaceInput(1, var_array[i + 1]);
      }
393 394
    }
  } else {
395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435
    DCHECK(!label->IsBound());
    if (merged_count == 0) {
      // Just set the control, effect and variables directly.
      DCHECK(!label->IsBound());
      label->control_ = current_control_;
      label->effect_ = current_effect_;
      for (size_t i = 0; i < sizeof...(vars); i++) {
        label->bindings_[i] = var_array[i + 1];
      }
    } else if (merged_count == 1) {
      // Create merge, effect phi and a phi for each variable.
      label->control_ = graph()->NewNode(common()->Merge(2), label->control_,
                                         current_control_);
      label->effect_ = graph()->NewNode(common()->EffectPhi(2), label->effect_,
                                        current_effect_, label->control_);
      for (size_t i = 0; i < sizeof...(vars); i++) {
        label->bindings_[i] = graph()->NewNode(
            common()->Phi(label->representations_[i], 2), label->bindings_[i],
            var_array[i + 1], label->control_);
      }
    } else {
      // Append to the merge, effect phi and phis.
      DCHECK_EQ(IrOpcode::kMerge, label->control_->opcode());
      label->control_->AppendInput(graph()->zone(), current_control_);
      NodeProperties::ChangeOp(label->control_,
                               common()->Merge(merged_count + 1));

      DCHECK_EQ(IrOpcode::kEffectPhi, label->effect_->opcode());
      label->effect_->ReplaceInput(merged_count, current_effect_);
      label->effect_->AppendInput(graph()->zone(), label->control_);
      NodeProperties::ChangeOp(label->effect_,
                               common()->EffectPhi(merged_count + 1));

      for (size_t i = 0; i < sizeof...(vars); i++) {
        DCHECK_EQ(IrOpcode::kPhi, label->bindings_[i]->opcode());
        label->bindings_[i]->ReplaceInput(merged_count, var_array[i + 1]);
        label->bindings_[i]->AppendInput(graph()->zone(), label->control_);
        NodeProperties::ChangeOp(
            label->bindings_[i],
            common()->Phi(label->representations_[i], merged_count + 1));
      }
436
    }
437
  }
438
  label->merged_count_++;
439 440
}

441 442
template <size_t VarCount>
void GraphAssembler::Bind(GraphAssemblerLabel<VarCount>* label) {
443 444 445
  DCHECK_NULL(current_control_);
  DCHECK_NULL(current_effect_);
  DCHECK_LT(0, label->merged_count_);
446

447 448
  current_control_ = label->control_;
  current_effect_ = label->effect_;
449
  BindBasicBlock(label->basic_block());
450 451

  label->SetBound();
452 453 454 455 456 457 458 459 460 461 462 463 464

  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.
    current_control_ =
        AddNode(graph()->NewNode(common()->Merge(1), current_control_));
  }
465 466
}

467 468 469
template <typename... Vars>
void GraphAssembler::Goto(GraphAssemblerLabel<sizeof...(Vars)>* label,
                          Vars... vars) {
470 471 472
  DCHECK_NOT_NULL(current_control_);
  DCHECK_NOT_NULL(current_effect_);
  MergeState(label, vars...);
473 474
  GotoBasicBlock(label->basic_block());

475 476 477 478
  current_control_ = nullptr;
  current_effect_ = nullptr;
}

479 480 481 482
template <typename... Vars>
void GraphAssembler::GotoIf(Node* condition,
                            GraphAssemblerLabel<sizeof...(Vars)>* label,
                            Vars... vars) {
483 484 485 486 487 488 489 490
  BranchHint hint =
      label->IsDeferred() ? BranchHint::kFalse : BranchHint::kNone;
  Node* branch =
      graph()->NewNode(common()->Branch(hint), condition, current_control_);

  current_control_ = graph()->NewNode(common()->IfTrue(), branch);
  MergeState(label, vars...);

491 492
  GotoIfBasicBlock(label->basic_block(), branch, IrOpcode::kIfTrue);
  current_control_ = AddNode(graph()->NewNode(common()->IfFalse(), branch));
493 494
}

495
template <typename... Vars>
496 497 498
void GraphAssembler::GotoIfNot(Node* condition,
                               GraphAssemblerLabel<sizeof...(Vars)>* label,
                               Vars... vars) {
499 500 501 502 503 504 505
  BranchHint hint = label->IsDeferred() ? BranchHint::kTrue : BranchHint::kNone;
  Node* branch =
      graph()->NewNode(common()->Branch(hint), condition, current_control_);

  current_control_ = graph()->NewNode(common()->IfFalse(), branch);
  MergeState(label, vars...);

506 507
  GotoIfBasicBlock(label->basic_block(), branch, IrOpcode::kIfFalse);
  current_control_ = AddNode(graph()->NewNode(common()->IfTrue(), branch));
508 509 510
}

template <typename... Args>
511 512 513
Node* GraphAssembler::Call(const CallDescriptor* call_descriptor,
                           Args... args) {
  const Operator* op = common()->Call(call_descriptor);
514 515 516 517 518 519
  return Call(op, args...);
}

template <typename... Args>
Node* GraphAssembler::Call(const Operator* op, Args... args) {
  DCHECK_EQ(IrOpcode::kCall, op->opcode());
520 521 522 523 524 525
  Node* args_array[] = {args..., current_effect_, current_control_};
  int size = static_cast<int>(sizeof...(args)) + op->EffectInputCount() +
             op->ControlInputCount();
  Node* call = graph()->NewNode(op, size, args_array);
  DCHECK_EQ(0, op->ControlOutputCount());
  current_effect_ = call;
526
  return AddNode(call);
527 528 529 530 531 532 533
}

}  // namespace compiler
}  // namespace internal
}  // namespace v8

#endif  // V8_COMPILER_GRAPH_ASSEMBLER_H_