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

#ifndef V8_COMPILER_COMMON_OPERATOR_H_
#define V8_COMPILER_COMMON_OPERATOR_H_

8
#include "src/base/compiler-specific.h"
9 10 11
#include "src/codegen/machine-type.h"
#include "src/codegen/reloc-info.h"
#include "src/codegen/string-constants.h"
12
#include "src/compiler/frame-states.h"
13
#include "src/deoptimizer/deoptimize-reason.h"
14
#include "src/globals.h"
15
#include "src/vector-slot-pair.h"
16
#include "src/zone/zone-containers.h"
17
#include "src/zone/zone-handle-set.h"
18 19 20

namespace v8 {
namespace internal {
21 22 23

class StringConstantBase;

24 25
namespace compiler {

26 27
// Forward declarations.
class CallDescriptor;
28
struct CommonOperatorGlobalCache;
29
class Operator;
30
class Type;
31
class Node;
32

33 34 35
// Prediction hint for branches.
enum class BranchHint : uint8_t { kNone, kTrue, kFalse };

36 37 38 39 40 41 42 43 44 45 46 47
inline BranchHint NegateBranchHint(BranchHint hint) {
  switch (hint) {
    case BranchHint::kNone:
      return hint;
    case BranchHint::kTrue:
      return BranchHint::kFalse;
    case BranchHint::kFalse:
      return BranchHint::kTrue;
  }
  UNREACHABLE();
}

48 49
inline size_t hash_value(BranchHint hint) { return static_cast<size_t>(hint); }

50
V8_EXPORT_PRIVATE std::ostream& operator<<(std::ostream&, BranchHint);
51

52 53 54 55 56 57 58 59
enum class IsSafetyCheck : uint8_t {
  kCriticalSafetyCheck,
  kSafetyCheck,
  kNoSafetyCheck
};

// Get the more critical safety check of the two arguments.
IsSafetyCheck CombineSafetyChecks(IsSafetyCheck, IsSafetyCheck);
60 61 62 63 64 65

V8_EXPORT_PRIVATE std::ostream& operator<<(std::ostream&, IsSafetyCheck);
inline size_t hash_value(IsSafetyCheck is_safety_check) {
  return static_cast<size_t>(is_safety_check);
}

66 67 68 69 70 71 72 73 74 75 76 77 78
enum class TrapId : uint32_t {
#define DEF_ENUM(Name, ...) k##Name,
  FOREACH_WASM_TRAPREASON(DEF_ENUM)
#undef DEF_ENUM
      kInvalid
};

inline size_t hash_value(TrapId id) { return static_cast<uint32_t>(id); }

std::ostream& operator<<(std::ostream&, TrapId trap_id);

TrapId TrapIdOf(const Operator* const op);

79 80 81 82 83
struct BranchOperatorInfo {
  BranchHint hint;
  IsSafetyCheck is_safety_check;
};

84
inline size_t hash_value(const BranchOperatorInfo& info) {
85
  return base::hash_combine(info.hint, info.is_safety_check);
86 87 88 89 90 91
}

V8_EXPORT_PRIVATE std::ostream& operator<<(std::ostream&, BranchOperatorInfo);

inline bool operator==(const BranchOperatorInfo& a,
                       const BranchOperatorInfo& b) {
92
  return a.hint == b.hint && a.is_safety_check == b.is_safety_check;
93 94 95
}

V8_EXPORT_PRIVATE const BranchOperatorInfo& BranchOperatorInfoOf(
96
    const Operator* const) V8_WARN_UNUSED_RESULT;
97
V8_EXPORT_PRIVATE BranchHint BranchHintOf(const Operator* const)
98
    V8_WARN_UNUSED_RESULT;
99

100 101 102
// Helper function for return nodes, because returns have a hidden value input.
int ValueInputCountOfReturn(Operator const* const op);

103 104 105
// Parameters for the {Deoptimize} operator.
class DeoptimizeParameters final {
 public:
106
  DeoptimizeParameters(DeoptimizeKind kind, DeoptimizeReason reason,
107 108 109 110 111 112
                       VectorSlotPair const& feedback,
                       IsSafetyCheck is_safety_check)
      : kind_(kind),
        reason_(reason),
        feedback_(feedback),
        is_safety_check_(is_safety_check) {}
113 114 115

  DeoptimizeKind kind() const { return kind_; }
  DeoptimizeReason reason() const { return reason_; }
116
  const VectorSlotPair& feedback() const { return feedback_; }
117
  IsSafetyCheck is_safety_check() const { return is_safety_check_; }
118 119 120 121

 private:
  DeoptimizeKind const kind_;
  DeoptimizeReason const reason_;
122
  VectorSlotPair const feedback_;
123
  IsSafetyCheck is_safety_check_;
124 125 126 127 128 129 130 131
};

bool operator==(DeoptimizeParameters, DeoptimizeParameters);
bool operator!=(DeoptimizeParameters, DeoptimizeParameters);

size_t hast_value(DeoptimizeParameters p);

std::ostream& operator<<(std::ostream&, DeoptimizeParameters p);
132

133
DeoptimizeParameters const& DeoptimizeParametersOf(Operator const* const)
134
    V8_WARN_UNUSED_RESULT;
135

136
IsSafetyCheck IsSafetyCheckOf(const Operator* op) V8_WARN_UNUSED_RESULT;
137

138
class SelectParameters final {
139
 public:
140
  explicit SelectParameters(MachineRepresentation representation,
141
                            BranchHint hint = BranchHint::kNone)
142
      : representation_(representation), hint_(hint) {}
143

144
  MachineRepresentation representation() const { return representation_; }
145 146 147
  BranchHint hint() const { return hint_; }

 private:
148
  const MachineRepresentation representation_;
149 150 151 152 153 154 155 156 157 158
  const BranchHint hint_;
};

bool operator==(SelectParameters const&, SelectParameters const&);
bool operator!=(SelectParameters const&, SelectParameters const&);

size_t hash_value(SelectParameters const& p);

std::ostream& operator<<(std::ostream&, SelectParameters const& p);

159
V8_EXPORT_PRIVATE SelectParameters const& SelectParametersOf(
160
    const Operator* const) V8_WARN_UNUSED_RESULT;
161

162
V8_EXPORT_PRIVATE CallDescriptor const* CallDescriptorOf(const Operator* const)
163
    V8_WARN_UNUSED_RESULT;
164

165
V8_EXPORT_PRIVATE size_t ProjectionIndexOf(const Operator* const)
166
    V8_WARN_UNUSED_RESULT;
167

168
V8_EXPORT_PRIVATE MachineRepresentation
169
PhiRepresentationOf(const Operator* const) V8_WARN_UNUSED_RESULT;
170

171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187
// The {IrOpcode::kParameter} opcode represents an incoming parameter to the
// function. This class bundles the index and a debug name for such operators.
class ParameterInfo final {
 public:
  ParameterInfo(int index, const char* debug_name)
      : index_(index), debug_name_(debug_name) {}

  int index() const { return index_; }
  const char* debug_name() const { return debug_name_; }

 private:
  int index_;
  const char* debug_name_;
};

std::ostream& operator<<(std::ostream&, ParameterInfo const&);

188
V8_EXPORT_PRIVATE int ParameterIndexOf(const Operator* const)
189 190 191
    V8_WARN_UNUSED_RESULT;
const ParameterInfo& ParameterInfoOf(const Operator* const)
    V8_WARN_UNUSED_RESULT;
192

193
struct ObjectStateInfo final : std::pair<uint32_t, int> {
194 195
  ObjectStateInfo(uint32_t object_id, int size)
      : std::pair<uint32_t, int>(object_id, size) {}
196 197 198 199 200 201 202 203
  uint32_t object_id() const { return first; }
  int size() const { return second; }
};
std::ostream& operator<<(std::ostream&, ObjectStateInfo const&);
size_t hash_value(ObjectStateInfo const& p);

struct TypedObjectStateInfo final
    : std::pair<uint32_t, const ZoneVector<MachineType>*> {
204 205 206 207
  TypedObjectStateInfo(uint32_t object_id,
                       const ZoneVector<MachineType>* machine_types)
      : std::pair<uint32_t, const ZoneVector<MachineType>*>(object_id,
                                                            machine_types) {}
208 209 210 211 212 213
  uint32_t object_id() const { return first; }
  const ZoneVector<MachineType>* machine_types() const { return second; }
};
std::ostream& operator<<(std::ostream&, TypedObjectStateInfo const&);
size_t hash_value(TypedObjectStateInfo const& p);

214 215
class RelocatablePtrConstantInfo final {
 public:
216 217 218 219 220 221
  enum Type { kInt32, kInt64 };

  RelocatablePtrConstantInfo(int32_t value, RelocInfo::Mode rmode)
      : value_(value), rmode_(rmode), type_(kInt32) {}
  RelocatablePtrConstantInfo(int64_t value, RelocInfo::Mode rmode)
      : value_(value), rmode_(rmode), type_(kInt64) {}
222 223 224

  intptr_t value() const { return value_; }
  RelocInfo::Mode rmode() const { return rmode_; }
225
  Type type() const { return type_; }
226 227 228 229

 private:
  intptr_t value_;
  RelocInfo::Mode rmode_;
230
  Type type_;
231 232 233 234 235 236
};

bool operator==(RelocatablePtrConstantInfo const& lhs,
                RelocatablePtrConstantInfo const& rhs);
bool operator!=(RelocatablePtrConstantInfo const& lhs,
                RelocatablePtrConstantInfo const& rhs);
237

238
std::ostream& operator<<(std::ostream&, RelocatablePtrConstantInfo const&);
239

240
size_t hash_value(RelocatablePtrConstantInfo const& p);
241

242 243 244 245 246
// Used to define a sparse set of inputs. This can be used to efficiently encode
// nodes that can have a lot of inputs, but where many inputs can have the same
// value.
class SparseInputMask final {
 public:
247
  using BitMaskType = uint32_t;
248 249 250 251 252 253 254 255 256 257 258 259 260 261

  // The mask representing a dense input set.
  static const BitMaskType kDenseBitMask = 0x0;
  // The bits representing the end of a sparse input set.
  static const BitMaskType kEndMarker = 0x1;
  // The mask for accessing a sparse input entry in the bitmask.
  static const BitMaskType kEntryMask = 0x1;

  // The number of bits in the mask, minus one for the end marker.
  static const int kMaxSparseInputs = (sizeof(BitMaskType) * kBitsPerByte - 1);

  // An iterator over a node's sparse inputs.
  class InputIterator final {
   public:
262
    InputIterator() = default;
263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358
    InputIterator(BitMaskType bit_mask, Node* parent);

    Node* parent() const { return parent_; }
    int real_index() const { return real_index_; }

    // Advance the iterator to the next sparse input. Only valid if the iterator
    // has not reached the end.
    void Advance();

    // Get the current sparse input's real node value. Only valid if the
    // current sparse input is real.
    Node* GetReal() const;

    // Get the current sparse input, returning either a real input node if
    // the current sparse input is real, or the given {empty_value} if the
    // current sparse input is empty.
    Node* Get(Node* empty_value) const {
      return IsReal() ? GetReal() : empty_value;
    }

    // True if the current sparse input is a real input node.
    bool IsReal() const;

    // True if the current sparse input is an empty value.
    bool IsEmpty() const { return !IsReal(); }

    // True if the iterator has reached the end of the sparse inputs.
    bool IsEnd() const;

   private:
    BitMaskType bit_mask_;
    Node* parent_;
    int real_index_;
  };

  explicit SparseInputMask(BitMaskType bit_mask) : bit_mask_(bit_mask) {}

  // Provides a SparseInputMask representing a dense input set.
  static SparseInputMask Dense() { return SparseInputMask(kDenseBitMask); }

  BitMaskType mask() const { return bit_mask_; }

  bool IsDense() const { return bit_mask_ == SparseInputMask::kDenseBitMask; }

  // Counts how many real values are in the sparse array. Only valid for
  // non-dense masks.
  int CountReal() const;

  // Returns an iterator over the sparse inputs of {node}.
  InputIterator IterateOverInputs(Node* node);

 private:
  //
  // The sparse input mask has a bitmask specifying if the node's inputs are
  // represented sparsely. If the bitmask value is 0, then the inputs are dense;
  // otherwise, they should be interpreted as follows:
  //
  //   * The bitmask represents which values are real, with 1 for real values
  //     and 0 for empty values.
  //   * The inputs to the node are the real values, in the order of the 1s from
  //     least- to most-significant.
  //   * The top bit of the bitmask is a guard indicating the end of the values,
  //     whether real or empty (and is not representative of a real input
  //     itself). This is used so that we don't have to additionally store a
  //     value count.
  //
  // So, for N 1s in the bitmask, there are N - 1 inputs into the node.
  BitMaskType bit_mask_;
};

bool operator==(SparseInputMask const& lhs, SparseInputMask const& rhs);
bool operator!=(SparseInputMask const& lhs, SparseInputMask const& rhs);

class TypedStateValueInfo final {
 public:
  TypedStateValueInfo(ZoneVector<MachineType> const* machine_types,
                      SparseInputMask sparse_input_mask)
      : machine_types_(machine_types), sparse_input_mask_(sparse_input_mask) {}

  ZoneVector<MachineType> const* machine_types() const {
    return machine_types_;
  }
  SparseInputMask sparse_input_mask() const { return sparse_input_mask_; }

 private:
  ZoneVector<MachineType> const* machine_types_;
  SparseInputMask sparse_input_mask_;
};

bool operator==(TypedStateValueInfo const& lhs, TypedStateValueInfo const& rhs);
bool operator!=(TypedStateValueInfo const& lhs, TypedStateValueInfo const& rhs);

std::ostream& operator<<(std::ostream&, TypedStateValueInfo const&);

size_t hash_value(TypedStateValueInfo const& p);

359 360 361 362 363 364 365 366 367
// Used to mark a region (as identified by BeginRegion/FinishRegion) as either
// JavaScript-observable or not (i.e. allocations are not JavaScript observable
// themselves, but transitioning stores are).
enum class RegionObservability : uint8_t { kObservable, kNotObservable };

size_t hash_value(RegionObservability);

std::ostream& operator<<(std::ostream&, RegionObservability);

368 369
RegionObservability RegionObservabilityOf(Operator const*)
    V8_WARN_UNUSED_RESULT;
370

371 372
std::ostream& operator<<(std::ostream& os,
                         const ZoneVector<MachineType>* types);
373

374
Type TypeGuardTypeOf(Operator const*) V8_WARN_UNUSED_RESULT;
375

376
int OsrValueIndexOf(Operator const*) V8_WARN_UNUSED_RESULT;
377

378
SparseInputMask SparseInputMaskOf(Operator const*) V8_WARN_UNUSED_RESULT;
379

380
ZoneVector<MachineType> const* MachineTypesOf(Operator const*)
381
    V8_WARN_UNUSED_RESULT;
382

383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401
// The ArgumentsElementsState and ArgumentsLengthState can describe the layout
// for backing stores of arguments objects of various types:
//
//                        +------------------------------------+
//  - kUnmappedArguments: | arg0, ... argK-1, argK, ... argN-1 |  {length:N}
//                        +------------------------------------+
//                        +------------------------------------+
//  - kMappedArguments:   | hole, ...   hole, argK, ... argN-1 |  {length:N}
//                        +------------------------------------+
//                                          +------------------+
//  - kRestParameter:                       | argK, ... argN-1 |  {length:N-K}
//                                          +------------------+
//
// Here {K} represents the number for formal parameters of the active function,
// whereas {N} represents the actual number of arguments passed at runtime.
// Note that {N < K} can happen and causes {K} to be capped accordingly.
//
// Also note that it is possible for an arguments object of {kMappedArguments}
// type to carry a backing store of {kUnappedArguments} type when {K == 0}.
402
using ArgumentsStateType = CreateArgumentsType;
403

404
ArgumentsStateType ArgumentsStateTypeOf(Operator const*) V8_WARN_UNUSED_RESULT;
405

406 407
uint32_t ObjectIdOf(Operator const*);

408
MachineRepresentation DeadValueRepresentationOf(Operator const*)
409
    V8_WARN_UNUSED_RESULT;
410

411 412
class IfValueParameters final {
 public:
413 414 415
  IfValueParameters(int32_t value, int32_t comparison_order,
                    BranchHint hint = BranchHint::kNone)
      : value_(value), comparison_order_(comparison_order), hint_(hint) {}
416 417 418

  int32_t value() const { return value_; }
  int32_t comparison_order() const { return comparison_order_; }
419
  BranchHint hint() const { return hint_; }
420 421 422 423

 private:
  int32_t value_;
  int32_t comparison_order_;
424
  BranchHint hint_;
425 426 427 428 429 430 431 432 433 434 435
};

V8_EXPORT_PRIVATE bool operator==(IfValueParameters const&,
                                  IfValueParameters const&);

size_t hash_value(IfValueParameters const&);

V8_EXPORT_PRIVATE std::ostream& operator<<(std::ostream&,
                                           IfValueParameters const&);

V8_EXPORT_PRIVATE IfValueParameters const& IfValueParametersOf(
436
    const Operator* op) V8_WARN_UNUSED_RESULT;
437

438 439
const FrameStateInfo& FrameStateInfoOf(const Operator* op)
    V8_WARN_UNUSED_RESULT;
440

441 442
V8_EXPORT_PRIVATE Handle<HeapObject> HeapConstantOf(const Operator* op)
    V8_WARN_UNUSED_RESULT;
443

444 445 446
const StringConstantBase* StringConstantBaseOf(const Operator* op)
    V8_WARN_UNUSED_RESULT;

447 448
// Interface for building common operators that can be used at any level of IR,
// including JavaScript, mid-level, and low-level.
449 450
class V8_EXPORT_PRIVATE CommonOperatorBuilder final
    : public NON_EXPORTED_BASE(ZoneObject) {
451
 public:
452 453
  explicit CommonOperatorBuilder(Zone* zone);

454
  const Operator* Dead();
455
  const Operator* DeadValue(MachineRepresentation rep);
456
  const Operator* Unreachable();
457
  const Operator* StaticAssert();
458
  const Operator* End(size_t control_input_count);
459 460
  const Operator* Branch(BranchHint = BranchHint::kNone,
                         IsSafetyCheck = IsSafetyCheck::kSafetyCheck);
461 462
  const Operator* IfTrue();
  const Operator* IfFalse();
463
  const Operator* IfSuccess();
464
  const Operator* IfException();
465
  const Operator* Switch(size_t control_output_count);
466 467 468
  const Operator* IfValue(int32_t value, int32_t order = 0,
                          BranchHint hint = BranchHint::kNone);
  const Operator* IfDefault(BranchHint hint = BranchHint::kNone);
469
  const Operator* Throw();
470 471
  const Operator* Deoptimize(DeoptimizeKind kind, DeoptimizeReason reason,
                             VectorSlotPair const& feedback);
472 473 474 475 476 477 478 479
  const Operator* DeoptimizeIf(
      DeoptimizeKind kind, DeoptimizeReason reason,
      VectorSlotPair const& feedback,
      IsSafetyCheck is_safety_check = IsSafetyCheck::kSafetyCheck);
  const Operator* DeoptimizeUnless(
      DeoptimizeKind kind, DeoptimizeReason reason,
      VectorSlotPair const& feedback,
      IsSafetyCheck is_safety_check = IsSafetyCheck::kSafetyCheck);
480 481
  const Operator* TrapIf(TrapId trap_id);
  const Operator* TrapUnless(TrapId trap_id);
482
  const Operator* Return(int value_input_count = 1);
483
  const Operator* Terminate();
484

485
  const Operator* Start(int value_output_count);
486 487
  const Operator* Loop(int control_input_count);
  const Operator* Merge(int control_input_count);
488
  const Operator* Parameter(int index, const char* debug_name = nullptr);
489

490 491 492 493
  const Operator* OsrNormalEntry();
  const Operator* OsrLoopEntry();
  const Operator* OsrValue(int index);

494 495
  const Operator* Int32Constant(int32_t);
  const Operator* Int64Constant(int64_t);
496
  const Operator* Float32Constant(volatile float);
497 498 499
  const Operator* Float64Constant(volatile double);
  const Operator* ExternalConstant(const ExternalReference&);
  const Operator* NumberConstant(volatile double);
500
  const Operator* PointerConstant(intptr_t);
501
  const Operator* HeapConstant(const Handle<HeapObject>&);
502
  const Operator* ObjectId(uint32_t);
503

504 505 506 507 508
  const Operator* RelocatableInt32Constant(int32_t value,
                                           RelocInfo::Mode rmode);
  const Operator* RelocatableInt64Constant(int64_t value,
                                           RelocInfo::Mode rmode);

509 510 511
  const Operator* Select(MachineRepresentation, BranchHint = BranchHint::kNone);
  const Operator* Phi(MachineRepresentation representation,
                      int value_input_count);
512
  const Operator* EffectPhi(int effect_input_count);
513
  const Operator* InductionVariablePhi(int value_input_count);
514 515 516
  const Operator* LoopExit();
  const Operator* LoopExitValue();
  const Operator* LoopExitEffect();
517
  const Operator* Checkpoint();
518
  const Operator* BeginRegion(RegionObservability);
519
  const Operator* FinishRegion();
520 521 522
  const Operator* StateValues(int arguments, SparseInputMask bitmask);
  const Operator* TypedStateValues(const ZoneVector<MachineType>* types,
                                   SparseInputMask bitmask);
523 524
  const Operator* ArgumentsElementsState(ArgumentsStateType type);
  const Operator* ArgumentsLengthState(ArgumentsStateType type);
525 526
  const Operator* ObjectState(uint32_t object_id, int pointer_slots);
  const Operator* TypedObjectState(uint32_t object_id,
527
                                   const ZoneVector<MachineType>* types);
528
  const Operator* FrameState(BailoutId bailout_id,
529
                             OutputFrameStateCombine state_combine,
530
                             const FrameStateFunctionInfo* function_info);
531
  const Operator* Call(const CallDescriptor* call_descriptor);
532
  const Operator* CallWithCallerSavedRegisters(
533 534
      const CallDescriptor* call_descriptor);
  const Operator* TailCall(const CallDescriptor* call_descriptor);
535
  const Operator* Projection(size_t index);
536
  const Operator* Retain();
537
  const Operator* TypeGuard(Type type);
538

539 540 541 542
  // Constructs a new merge or phi operator with the same opcode as {op}, but
  // with {size} inputs.
  const Operator* ResizeMergeOrPhi(const Operator* op, int size);

543 544 545
  // Constructs function info for frame state construction.
  const FrameStateFunctionInfo* CreateFrameStateFunctionInfo(
      FrameStateType type, int parameter_count, int local_count,
546
      Handle<SharedFunctionInfo> shared_info);
547

548 549
  const Operator* MarkAsSafetyCheck(const Operator* op,
                                    IsSafetyCheck safety_check);
550

551 552
  const Operator* DelayedStringConstant(const StringConstantBase* str);

553
 private:
554 555
  Zone* zone() const { return zone_; }

556
  const CommonOperatorGlobalCache& cache_;
557
  Zone* const zone_;
558 559

  DISALLOW_COPY_AND_ASSIGN(CommonOperatorBuilder);
560 561
};

562 563 564
}  // namespace compiler
}  // namespace internal
}  // namespace v8
565 566

#endif  // V8_COMPILER_COMMON_OPERATOR_H_