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 #ifndef V8_COMPILER_BACKEND_INSTRUCTION_SELECTOR_H_ 6 #define V8_COMPILER_BACKEND_INSTRUCTION_SELECTOR_H_ 7 8 #include <map> 9 10 #include "src/codegen/cpu-features.h" 11 #include "src/common/globals.h" 12 #include "src/compiler/backend/instruction-scheduler.h" 13 #include "src/compiler/backend/instruction.h" 14 #include "src/compiler/common-operator.h" 15 #include "src/compiler/feedback-source.h" 16 #include "src/compiler/linkage.h" 17 #include "src/compiler/machine-operator.h" 18 #include "src/compiler/node.h" 19 #include "src/zone/zone-containers.h" 20 21 namespace v8 { 22 namespace internal { 23 24 class TickCounter; 25 26 namespace compiler { 27 28 // Forward declarations. 29 class BasicBlock; 30 struct CallBuffer; // TODO(bmeurer): Remove this. 31 class Linkage; 32 class OperandGenerator; 33 class SwitchInfo; 34 class StateObjectDeduplicator; 35 36 // The flags continuation is a way to combine a branch or a materialization 37 // of a boolean value with an instruction that sets the flags register. 38 // The whole instruction is treated as a unit by the register allocator, and 39 // thus no spills or moves can be introduced between the flags-setting 40 // instruction and the branch or set it should be combined with. 41 class FlagsContinuation final { 42 public: FlagsContinuation()43 FlagsContinuation() : mode_(kFlags_none) {} 44 45 // Creates a new flags continuation from the given condition and true/false 46 // blocks. ForBranch(FlagsCondition condition,BasicBlock * true_block,BasicBlock * false_block)47 static FlagsContinuation ForBranch(FlagsCondition condition, 48 BasicBlock* true_block, 49 BasicBlock* false_block) { 50 return FlagsContinuation(kFlags_branch, condition, true_block, false_block); 51 } 52 ForBranchAndPoison(FlagsCondition condition,BasicBlock * true_block,BasicBlock * false_block)53 static FlagsContinuation ForBranchAndPoison(FlagsCondition condition, 54 BasicBlock* true_block, 55 BasicBlock* false_block) { 56 return FlagsContinuation(kFlags_branch_and_poison, condition, true_block, 57 false_block); 58 } 59 60 // Creates a new flags continuation for an eager deoptimization exit. ForDeoptimize(FlagsCondition condition,DeoptimizeKind kind,DeoptimizeReason reason,FeedbackSource const & feedback,Node * frame_state)61 static FlagsContinuation ForDeoptimize(FlagsCondition condition, 62 DeoptimizeKind kind, 63 DeoptimizeReason reason, 64 FeedbackSource const& feedback, 65 Node* frame_state) { 66 return FlagsContinuation(kFlags_deoptimize, condition, kind, reason, 67 feedback, frame_state); 68 } 69 70 // Creates a new flags continuation for an eager deoptimization exit. ForDeoptimizeAndPoison(FlagsCondition condition,DeoptimizeKind kind,DeoptimizeReason reason,FeedbackSource const & feedback,Node * frame_state)71 static FlagsContinuation ForDeoptimizeAndPoison( 72 FlagsCondition condition, DeoptimizeKind kind, DeoptimizeReason reason, 73 FeedbackSource const& feedback, Node* frame_state) { 74 return FlagsContinuation(kFlags_deoptimize_and_poison, condition, kind, 75 reason, feedback, frame_state); 76 } 77 78 // Creates a new flags continuation for a boolean value. ForSet(FlagsCondition condition,Node * result)79 static FlagsContinuation ForSet(FlagsCondition condition, Node* result) { 80 return FlagsContinuation(condition, result); 81 } 82 83 // Creates a new flags continuation for a wasm trap. ForTrap(FlagsCondition condition,TrapId trap_id,Node * result)84 static FlagsContinuation ForTrap(FlagsCondition condition, TrapId trap_id, 85 Node* result) { 86 return FlagsContinuation(condition, trap_id, result); 87 } 88 IsNone()89 bool IsNone() const { return mode_ == kFlags_none; } IsBranch()90 bool IsBranch() const { 91 return mode_ == kFlags_branch || mode_ == kFlags_branch_and_poison; 92 } IsDeoptimize()93 bool IsDeoptimize() const { 94 return mode_ == kFlags_deoptimize || mode_ == kFlags_deoptimize_and_poison; 95 } IsPoisoned()96 bool IsPoisoned() const { 97 return mode_ == kFlags_branch_and_poison || 98 mode_ == kFlags_deoptimize_and_poison; 99 } IsSet()100 bool IsSet() const { return mode_ == kFlags_set; } IsTrap()101 bool IsTrap() const { return mode_ == kFlags_trap; } condition()102 FlagsCondition condition() const { 103 DCHECK(!IsNone()); 104 return condition_; 105 } kind()106 DeoptimizeKind kind() const { 107 DCHECK(IsDeoptimize()); 108 return kind_; 109 } reason()110 DeoptimizeReason reason() const { 111 DCHECK(IsDeoptimize()); 112 return reason_; 113 } feedback()114 FeedbackSource const& feedback() const { 115 DCHECK(IsDeoptimize()); 116 return feedback_; 117 } frame_state()118 Node* frame_state() const { 119 DCHECK(IsDeoptimize()); 120 return frame_state_or_result_; 121 } result()122 Node* result() const { 123 DCHECK(IsSet()); 124 return frame_state_or_result_; 125 } trap_id()126 TrapId trap_id() const { 127 DCHECK(IsTrap()); 128 return trap_id_; 129 } true_block()130 BasicBlock* true_block() const { 131 DCHECK(IsBranch()); 132 return true_block_; 133 } false_block()134 BasicBlock* false_block() const { 135 DCHECK(IsBranch()); 136 return false_block_; 137 } 138 Negate()139 void Negate() { 140 DCHECK(!IsNone()); 141 condition_ = NegateFlagsCondition(condition_); 142 } 143 Commute()144 void Commute() { 145 DCHECK(!IsNone()); 146 condition_ = CommuteFlagsCondition(condition_); 147 } 148 Overwrite(FlagsCondition condition)149 void Overwrite(FlagsCondition condition) { condition_ = condition; } 150 OverwriteAndNegateIfEqual(FlagsCondition condition)151 void OverwriteAndNegateIfEqual(FlagsCondition condition) { 152 DCHECK(condition_ == kEqual || condition_ == kNotEqual); 153 bool negate = condition_ == kEqual; 154 condition_ = condition; 155 if (negate) Negate(); 156 } 157 OverwriteUnsignedIfSigned()158 void OverwriteUnsignedIfSigned() { 159 switch (condition_) { 160 case kSignedLessThan: 161 condition_ = kUnsignedLessThan; 162 break; 163 case kSignedLessThanOrEqual: 164 condition_ = kUnsignedLessThanOrEqual; 165 break; 166 case kSignedGreaterThan: 167 condition_ = kUnsignedGreaterThan; 168 break; 169 case kSignedGreaterThanOrEqual: 170 condition_ = kUnsignedGreaterThanOrEqual; 171 break; 172 default: 173 break; 174 } 175 } 176 177 // Encodes this flags continuation into the given opcode. Encode(InstructionCode opcode)178 InstructionCode Encode(InstructionCode opcode) { 179 opcode |= FlagsModeField::encode(mode_); 180 if (mode_ != kFlags_none) { 181 opcode |= FlagsConditionField::encode(condition_); 182 } 183 return opcode; 184 } 185 186 private: FlagsContinuation(FlagsMode mode,FlagsCondition condition,BasicBlock * true_block,BasicBlock * false_block)187 FlagsContinuation(FlagsMode mode, FlagsCondition condition, 188 BasicBlock* true_block, BasicBlock* false_block) 189 : mode_(mode), 190 condition_(condition), 191 true_block_(true_block), 192 false_block_(false_block) { 193 DCHECK(mode == kFlags_branch || mode == kFlags_branch_and_poison); 194 DCHECK_NOT_NULL(true_block); 195 DCHECK_NOT_NULL(false_block); 196 } 197 FlagsContinuation(FlagsMode mode,FlagsCondition condition,DeoptimizeKind kind,DeoptimizeReason reason,FeedbackSource const & feedback,Node * frame_state)198 FlagsContinuation(FlagsMode mode, FlagsCondition condition, 199 DeoptimizeKind kind, DeoptimizeReason reason, 200 FeedbackSource const& feedback, Node* frame_state) 201 : mode_(mode), 202 condition_(condition), 203 kind_(kind), 204 reason_(reason), 205 feedback_(feedback), 206 frame_state_or_result_(frame_state) { 207 DCHECK(mode == kFlags_deoptimize || mode == kFlags_deoptimize_and_poison); 208 DCHECK_NOT_NULL(frame_state); 209 } 210 FlagsContinuation(FlagsCondition condition,Node * result)211 FlagsContinuation(FlagsCondition condition, Node* result) 212 : mode_(kFlags_set), 213 condition_(condition), 214 frame_state_or_result_(result) { 215 DCHECK_NOT_NULL(result); 216 } 217 FlagsContinuation(FlagsCondition condition,TrapId trap_id,Node * result)218 FlagsContinuation(FlagsCondition condition, TrapId trap_id, Node* result) 219 : mode_(kFlags_trap), 220 condition_(condition), 221 frame_state_or_result_(result), 222 trap_id_(trap_id) { 223 DCHECK_NOT_NULL(result); 224 } 225 226 FlagsMode const mode_; 227 FlagsCondition condition_; 228 DeoptimizeKind kind_; // Only valid if mode_ == kFlags_deoptimize* 229 DeoptimizeReason reason_; // Only valid if mode_ == kFlags_deoptimize* 230 FeedbackSource feedback_; // Only valid if mode_ == kFlags_deoptimize* 231 Node* frame_state_or_result_; // Only valid if mode_ == kFlags_deoptimize* 232 // or mode_ == kFlags_set. 233 BasicBlock* true_block_; // Only valid if mode_ == kFlags_branch*. 234 BasicBlock* false_block_; // Only valid if mode_ == kFlags_branch*. 235 TrapId trap_id_; // Only valid if mode_ == kFlags_trap. 236 }; 237 238 // This struct connects nodes of parameters which are going to be pushed on the 239 // call stack with their parameter index in the call descriptor of the callee. 240 struct PushParameter { 241 PushParameter(Node* n = nullptr, 242 LinkageLocation l = LinkageLocation::ForAnyRegister()) nodePushParameter243 : node(n), location(l) {} 244 245 Node* node; 246 LinkageLocation location; 247 }; 248 249 enum class FrameStateInputKind { kAny, kStackSlot }; 250 251 // Instruction selection generates an InstructionSequence for a given Schedule. 252 class V8_EXPORT_PRIVATE InstructionSelector final { 253 public: 254 // Forward declarations. 255 class Features; 256 257 enum SourcePositionMode { kCallSourcePositions, kAllSourcePositions }; 258 enum EnableScheduling { kDisableScheduling, kEnableScheduling }; 259 enum EnableRootsRelativeAddressing { 260 kDisableRootsRelativeAddressing, 261 kEnableRootsRelativeAddressing 262 }; 263 enum EnableSwitchJumpTable { 264 kDisableSwitchJumpTable, 265 kEnableSwitchJumpTable 266 }; 267 enum EnableTraceTurboJson { kDisableTraceTurboJson, kEnableTraceTurboJson }; 268 269 InstructionSelector( 270 Zone* zone, size_t node_count, Linkage* linkage, 271 InstructionSequence* sequence, Schedule* schedule, 272 SourcePositionTable* source_positions, Frame* frame, 273 EnableSwitchJumpTable enable_switch_jump_table, TickCounter* tick_counter, 274 size_t* max_unoptimized_frame_height, size_t* max_pushed_argument_count, 275 SourcePositionMode source_position_mode = kCallSourcePositions, 276 Features features = SupportedFeatures(), 277 EnableScheduling enable_scheduling = FLAG_turbo_instruction_scheduling 278 ? kEnableScheduling 279 : kDisableScheduling, 280 EnableRootsRelativeAddressing enable_roots_relative_addressing = 281 kDisableRootsRelativeAddressing, 282 PoisoningMitigationLevel poisoning_level = 283 PoisoningMitigationLevel::kDontPoison, 284 EnableTraceTurboJson trace_turbo = kDisableTraceTurboJson); 285 286 // Visit code for the entire graph with the included schedule. 287 bool SelectInstructions(); 288 289 void StartBlock(RpoNumber rpo); 290 void EndBlock(RpoNumber rpo); 291 void AddInstruction(Instruction* instr); 292 void AddTerminator(Instruction* instr); 293 294 // =========================================================================== 295 // ============= Architecture-independent code emission methods. ============= 296 // =========================================================================== 297 298 Instruction* Emit(InstructionCode opcode, InstructionOperand output, 299 size_t temp_count = 0, InstructionOperand* temps = nullptr); 300 Instruction* Emit(InstructionCode opcode, InstructionOperand output, 301 InstructionOperand a, size_t temp_count = 0, 302 InstructionOperand* temps = nullptr); 303 Instruction* Emit(InstructionCode opcode, InstructionOperand output, 304 InstructionOperand a, InstructionOperand b, 305 size_t temp_count = 0, InstructionOperand* temps = nullptr); 306 Instruction* Emit(InstructionCode opcode, InstructionOperand output, 307 InstructionOperand a, InstructionOperand b, 308 InstructionOperand c, size_t temp_count = 0, 309 InstructionOperand* temps = nullptr); 310 Instruction* Emit(InstructionCode opcode, InstructionOperand output, 311 InstructionOperand a, InstructionOperand b, 312 InstructionOperand c, InstructionOperand d, 313 size_t temp_count = 0, InstructionOperand* temps = nullptr); 314 Instruction* Emit(InstructionCode opcode, InstructionOperand output, 315 InstructionOperand a, InstructionOperand b, 316 InstructionOperand c, InstructionOperand d, 317 InstructionOperand e, size_t temp_count = 0, 318 InstructionOperand* temps = nullptr); 319 Instruction* Emit(InstructionCode opcode, InstructionOperand output, 320 InstructionOperand a, InstructionOperand b, 321 InstructionOperand c, InstructionOperand d, 322 InstructionOperand e, InstructionOperand f, 323 size_t temp_count = 0, InstructionOperand* temps = nullptr); 324 Instruction* Emit(InstructionCode opcode, size_t output_count, 325 InstructionOperand* outputs, size_t input_count, 326 InstructionOperand* inputs, size_t temp_count = 0, 327 InstructionOperand* temps = nullptr); 328 Instruction* Emit(Instruction* instr); 329 330 // [0-3] operand instructions with no output, uses labels for true and false 331 // blocks of the continuation. 332 Instruction* EmitWithContinuation(InstructionCode opcode, 333 FlagsContinuation* cont); 334 Instruction* EmitWithContinuation(InstructionCode opcode, 335 InstructionOperand a, 336 FlagsContinuation* cont); 337 Instruction* EmitWithContinuation(InstructionCode opcode, 338 InstructionOperand a, InstructionOperand b, 339 FlagsContinuation* cont); 340 Instruction* EmitWithContinuation(InstructionCode opcode, 341 InstructionOperand a, InstructionOperand b, 342 InstructionOperand c, 343 FlagsContinuation* cont); 344 Instruction* EmitWithContinuation(InstructionCode opcode, size_t output_count, 345 InstructionOperand* outputs, 346 size_t input_count, 347 InstructionOperand* inputs, 348 FlagsContinuation* cont); 349 Instruction* EmitWithContinuation( 350 InstructionCode opcode, size_t output_count, InstructionOperand* outputs, 351 size_t input_count, InstructionOperand* inputs, size_t temp_count, 352 InstructionOperand* temps, FlagsContinuation* cont); 353 354 void EmitIdentity(Node* node); 355 356 // =========================================================================== 357 // ============== Architecture-independent CPU feature methods. ============== 358 // =========================================================================== 359 360 class Features final { 361 public: Features()362 Features() : bits_(0) {} Features(unsigned bits)363 explicit Features(unsigned bits) : bits_(bits) {} Features(CpuFeature f)364 explicit Features(CpuFeature f) : bits_(1u << f) {} Features(CpuFeature f1,CpuFeature f2)365 Features(CpuFeature f1, CpuFeature f2) : bits_((1u << f1) | (1u << f2)) {} 366 Contains(CpuFeature f)367 bool Contains(CpuFeature f) const { return (bits_ & (1u << f)); } 368 369 private: 370 unsigned bits_; 371 }; 372 IsSupported(CpuFeature feature)373 bool IsSupported(CpuFeature feature) const { 374 return features_.Contains(feature); 375 } 376 377 // Returns the features supported on the target platform. SupportedFeatures()378 static Features SupportedFeatures() { 379 return Features(CpuFeatures::SupportedFeatures()); 380 } 381 382 // TODO(sigurds) This should take a CpuFeatures argument. 383 static MachineOperatorBuilder::Flags SupportedMachineOperatorFlags(); 384 385 static MachineOperatorBuilder::AlignmentRequirements AlignmentRequirements(); 386 387 bool NeedsPoisoning(IsSafetyCheck safety_check) const; 388 389 // =========================================================================== 390 // ============ Architecture-independent graph covering methods. ============= 391 // =========================================================================== 392 393 // Used in pattern matching during code generation. 394 // Check if {node} can be covered while generating code for the current 395 // instruction. A node can be covered if the {user} of the node has the only 396 // edge and the two are in the same basic block. 397 bool CanCover(Node* user, Node* node) const; 398 // CanCover is not transitive. The counter example are Nodes A,B,C such that 399 // CanCover(A, B) and CanCover(B,C) and B is pure: The the effect level of A 400 // and B might differ. CanCoverTransitively does the additional checks. 401 bool CanCoverTransitively(Node* user, Node* node, Node* node_input) const; 402 403 // Used in pattern matching during code generation. 404 // This function checks that {node} and {user} are in the same basic block, 405 // and that {user} is the only user of {node} in this basic block. This 406 // check guarantees that there are no users of {node} scheduled between 407 // {node} and {user}, and thus we can select a single instruction for both 408 // nodes, if such an instruction exists. This check can be used for example 409 // when selecting instructions for: 410 // n = Int32Add(a, b) 411 // c = Word32Compare(n, 0, cond) 412 // Branch(c, true_label, false_label) 413 // Here we can generate a flag-setting add instruction, even if the add has 414 // uses in other basic blocks, since the flag-setting add instruction will 415 // still generate the result of the addition and not just set the flags. 416 // However, if we had uses of the add in the same basic block, we could have: 417 // n = Int32Add(a, b) 418 // o = OtherOp(n, ...) 419 // c = Word32Compare(n, 0, cond) 420 // Branch(c, true_label, false_label) 421 // where we cannot select the add and the compare together. If we were to 422 // select a flag-setting add instruction for Word32Compare and Int32Add while 423 // visiting Word32Compare, we would then have to select an instruction for 424 // OtherOp *afterwards*, which means we would attempt to use the result of 425 // the add before we have defined it. 426 bool IsOnlyUserOfNodeInSameBlock(Node* user, Node* node) const; 427 428 // Checks if {node} was already defined, and therefore code was already 429 // generated for it. 430 bool IsDefined(Node* node) const; 431 432 // Checks if {node} has any uses, and therefore code has to be generated for 433 // it. 434 bool IsUsed(Node* node) const; 435 436 // Checks if {node} is currently live. IsLive(Node * node)437 bool IsLive(Node* node) const { return !IsDefined(node) && IsUsed(node); } 438 439 // Gets the effect level of {node}. 440 int GetEffectLevel(Node* node) const; 441 442 int GetVirtualRegister(const Node* node); 443 const std::map<NodeId, int> GetVirtualRegistersForTesting() const; 444 445 // Check if we can generate loads and stores of ExternalConstants relative 446 // to the roots register. 447 bool CanAddressRelativeToRootsRegister( 448 const ExternalReference& reference) const; 449 // Check if we can use the roots register to access GC roots. 450 bool CanUseRootsRegister() const; 451 isolate()452 Isolate* isolate() const { return sequence()->isolate(); } 453 instr_origins()454 const ZoneVector<std::pair<int, int>>& instr_origins() const { 455 return instr_origins_; 456 } 457 458 // Expose these SIMD helper functions for testing. CanonicalizeShuffleForTesting(bool inputs_equal,uint8_t * shuffle,bool * needs_swap,bool * is_swizzle)459 static void CanonicalizeShuffleForTesting(bool inputs_equal, uint8_t* shuffle, 460 bool* needs_swap, 461 bool* is_swizzle) { 462 CanonicalizeShuffle(inputs_equal, shuffle, needs_swap, is_swizzle); 463 } 464 TryMatchIdentityForTesting(const uint8_t * shuffle)465 static bool TryMatchIdentityForTesting(const uint8_t* shuffle) { 466 return TryMatchIdentity(shuffle); 467 } 468 template <int LANES> TryMatchDupForTesting(const uint8_t * shuffle,int * index)469 static bool TryMatchDupForTesting(const uint8_t* shuffle, int* index) { 470 return TryMatchDup<LANES>(shuffle, index); 471 } TryMatch32x4ShuffleForTesting(const uint8_t * shuffle,uint8_t * shuffle32x4)472 static bool TryMatch32x4ShuffleForTesting(const uint8_t* shuffle, 473 uint8_t* shuffle32x4) { 474 return TryMatch32x4Shuffle(shuffle, shuffle32x4); 475 } TryMatch16x8ShuffleForTesting(const uint8_t * shuffle,uint8_t * shuffle16x8)476 static bool TryMatch16x8ShuffleForTesting(const uint8_t* shuffle, 477 uint8_t* shuffle16x8) { 478 return TryMatch16x8Shuffle(shuffle, shuffle16x8); 479 } TryMatchConcatForTesting(const uint8_t * shuffle,uint8_t * offset)480 static bool TryMatchConcatForTesting(const uint8_t* shuffle, 481 uint8_t* offset) { 482 return TryMatchConcat(shuffle, offset); 483 } TryMatchBlendForTesting(const uint8_t * shuffle)484 static bool TryMatchBlendForTesting(const uint8_t* shuffle) { 485 return TryMatchBlend(shuffle); 486 } 487 488 private: 489 friend class OperandGenerator; 490 UseInstructionScheduling()491 bool UseInstructionScheduling() const { 492 return (enable_scheduling_ == kEnableScheduling) && 493 InstructionScheduler::SchedulerSupported(); 494 } 495 496 void AppendDeoptimizeArguments(InstructionOperandVector* args, 497 DeoptimizeKind kind, DeoptimizeReason reason, 498 FeedbackSource const& feedback, 499 Node* frame_state); 500 501 void EmitTableSwitch(const SwitchInfo& sw, 502 InstructionOperand const& index_operand); 503 void EmitBinarySearchSwitch(const SwitchInfo& sw, 504 InstructionOperand const& value_operand); 505 506 void TryRename(InstructionOperand* op); 507 int GetRename(int virtual_register); 508 void SetRename(const Node* node, const Node* rename); 509 void UpdateRenames(Instruction* instruction); 510 void UpdateRenamesInPhi(PhiInstruction* phi); 511 512 // Inform the instruction selection that {node} was just defined. 513 void MarkAsDefined(Node* node); 514 515 // Inform the instruction selection that {node} has at least one use and we 516 // will need to generate code for it. 517 void MarkAsUsed(Node* node); 518 519 // Sets the effect level of {node}. 520 void SetEffectLevel(Node* node, int effect_level); 521 522 // Inform the register allocation of the representation of the value produced 523 // by {node}. 524 void MarkAsRepresentation(MachineRepresentation rep, Node* node); MarkAsWord32(Node * node)525 void MarkAsWord32(Node* node) { 526 MarkAsRepresentation(MachineRepresentation::kWord32, node); 527 } MarkAsWord64(Node * node)528 void MarkAsWord64(Node* node) { 529 MarkAsRepresentation(MachineRepresentation::kWord64, node); 530 } MarkAsFloat32(Node * node)531 void MarkAsFloat32(Node* node) { 532 MarkAsRepresentation(MachineRepresentation::kFloat32, node); 533 } MarkAsFloat64(Node * node)534 void MarkAsFloat64(Node* node) { 535 MarkAsRepresentation(MachineRepresentation::kFloat64, node); 536 } MarkAsSimd128(Node * node)537 void MarkAsSimd128(Node* node) { 538 MarkAsRepresentation(MachineRepresentation::kSimd128, node); 539 } MarkAsTagged(Node * node)540 void MarkAsTagged(Node* node) { 541 MarkAsRepresentation(MachineRepresentation::kTagged, node); 542 } MarkAsCompressed(Node * node)543 void MarkAsCompressed(Node* node) { 544 MarkAsRepresentation(MachineRepresentation::kCompressed, node); 545 } 546 547 // Inform the register allocation of the representation of the unallocated 548 // operand {op}. 549 void MarkAsRepresentation(MachineRepresentation rep, 550 const InstructionOperand& op); 551 552 enum CallBufferFlag { 553 kCallCodeImmediate = 1u << 0, 554 kCallAddressImmediate = 1u << 1, 555 kCallTail = 1u << 2, 556 kCallFixedTargetRegister = 1u << 3 557 }; 558 using CallBufferFlags = base::Flags<CallBufferFlag>; 559 560 // Initialize the call buffer with the InstructionOperands, nodes, etc, 561 // corresponding 562 // to the inputs and outputs of the call. 563 // {call_code_immediate} to generate immediate operands to calls of code. 564 // {call_address_immediate} to generate immediate operands to address calls. 565 void InitializeCallBuffer(Node* call, CallBuffer* buffer, 566 CallBufferFlags flags, bool is_tail_call, 567 int stack_slot_delta = 0); 568 bool IsTailCallAddressImmediate(); 569 int GetTempsCountForTailCallFromJSFunction(); 570 571 void UpdateMaxPushedArgumentCount(size_t count); 572 573 FrameStateDescriptor* GetFrameStateDescriptor(Node* node); 574 size_t AddInputsToFrameStateDescriptor(FrameStateDescriptor* descriptor, 575 Node* state, OperandGenerator* g, 576 StateObjectDeduplicator* deduplicator, 577 InstructionOperandVector* inputs, 578 FrameStateInputKind kind, Zone* zone); 579 size_t AddInputsToFrameStateDescriptor(StateValueList* values, 580 InstructionOperandVector* inputs, 581 OperandGenerator* g, 582 StateObjectDeduplicator* deduplicator, 583 Node* node, FrameStateInputKind kind, 584 Zone* zone); 585 size_t AddOperandToStateValueDescriptor(StateValueList* values, 586 InstructionOperandVector* inputs, 587 OperandGenerator* g, 588 StateObjectDeduplicator* deduplicator, 589 Node* input, MachineType type, 590 FrameStateInputKind kind, Zone* zone); 591 592 // =========================================================================== 593 // ============= Architecture-specific graph covering methods. =============== 594 // =========================================================================== 595 596 // Visit nodes in the given block and generate code. 597 void VisitBlock(BasicBlock* block); 598 599 // Visit the node for the control flow at the end of the block, generating 600 // code if necessary. 601 void VisitControl(BasicBlock* block); 602 603 // Visit the node and generate code, if any. 604 void VisitNode(Node* node); 605 606 // Visit the node and generate code for IEEE 754 functions. 607 void VisitFloat64Ieee754Binop(Node*, InstructionCode code); 608 void VisitFloat64Ieee754Unop(Node*, InstructionCode code); 609 610 #define DECLARE_GENERATOR(x) void Visit##x(Node* node); 611 MACHINE_OP_LIST(DECLARE_GENERATOR) 612 MACHINE_SIMD_OP_LIST(DECLARE_GENERATOR) 613 #undef DECLARE_GENERATOR 614 615 // Visit the load node with a value and opcode to replace with. 616 void VisitLoad(Node* node, Node* value, InstructionCode opcode); 617 void VisitLoadTransform(Node* node, Node* value, InstructionCode opcode); 618 void VisitFinishRegion(Node* node); 619 void VisitParameter(Node* node); 620 void VisitIfException(Node* node); 621 void VisitOsrValue(Node* node); 622 void VisitPhi(Node* node); 623 void VisitProjection(Node* node); 624 void VisitConstant(Node* node); 625 void VisitCall(Node* call, BasicBlock* handler = nullptr); 626 void VisitDeoptimizeIf(Node* node); 627 void VisitDeoptimizeUnless(Node* node); 628 void VisitTrapIf(Node* node, TrapId trap_id); 629 void VisitTrapUnless(Node* node, TrapId trap_id); 630 void VisitTailCall(Node* call); 631 void VisitGoto(BasicBlock* target); 632 void VisitBranch(Node* input, BasicBlock* tbranch, BasicBlock* fbranch); 633 void VisitSwitch(Node* node, const SwitchInfo& sw); 634 void VisitDeoptimize(DeoptimizeKind kind, DeoptimizeReason reason, 635 FeedbackSource const& feedback, Node* frame_state); 636 void VisitReturn(Node* ret); 637 void VisitThrow(Node* node); 638 void VisitRetain(Node* node); 639 void VisitUnreachable(Node* node); 640 void VisitStaticAssert(Node* node); 641 void VisitDeadValue(Node* node); 642 643 void VisitStackPointerGreaterThan(Node* node, FlagsContinuation* cont); 644 645 void VisitWordCompareZero(Node* user, Node* value, FlagsContinuation* cont); 646 647 void EmitWordPoisonOnSpeculation(Node* node); 648 649 void EmitPrepareArguments(ZoneVector<compiler::PushParameter>* arguments, 650 const CallDescriptor* call_descriptor, Node* node); 651 void EmitPrepareResults(ZoneVector<compiler::PushParameter>* results, 652 const CallDescriptor* call_descriptor, Node* node); 653 654 bool CanProduceSignalingNaN(Node* node); 655 656 // =========================================================================== 657 // ============= Vector instruction (SIMD) helper fns. ======================= 658 // =========================================================================== 659 660 // Converts a shuffle into canonical form, meaning that the first lane index 661 // is in the range [0 .. 15]. Set |inputs_equal| true if this is an explicit 662 // swizzle. Returns canonicalized |shuffle|, |needs_swap|, and |is_swizzle|. 663 // If |needs_swap| is true, inputs must be swapped. If |is_swizzle| is true, 664 // the second input can be ignored. 665 static void CanonicalizeShuffle(bool inputs_equal, uint8_t* shuffle, 666 bool* needs_swap, bool* is_swizzle); 667 668 // Canonicalize shuffles to make pattern matching simpler. Returns the shuffle 669 // indices, and a boolean indicating if the shuffle is a swizzle (one input). 670 void CanonicalizeShuffle(Node* node, uint8_t* shuffle, bool* is_swizzle); 671 672 // Swaps the two first input operands of the node, to help match shuffles 673 // to specific architectural instructions. 674 void SwapShuffleInputs(Node* node); 675 676 // Tries to match an 8x16 byte shuffle to the identity shuffle, which is 677 // [0 1 ... 15]. This should be called after canonicalizing the shuffle, so 678 // the second identity shuffle, [16 17 .. 31] is converted to the first one. 679 static bool TryMatchIdentity(const uint8_t* shuffle); 680 681 // Tries to match a byte shuffle to a scalar splat operation. Returns the 682 // index of the lane if successful. 683 template <int LANES> TryMatchDup(const uint8_t * shuffle,int * index)684 static bool TryMatchDup(const uint8_t* shuffle, int* index) { 685 const int kBytesPerLane = kSimd128Size / LANES; 686 // Get the first lane's worth of bytes and check that indices start at a 687 // lane boundary and are consecutive. 688 uint8_t lane0[kBytesPerLane]; 689 lane0[0] = shuffle[0]; 690 if (lane0[0] % kBytesPerLane != 0) return false; 691 for (int i = 1; i < kBytesPerLane; ++i) { 692 lane0[i] = shuffle[i]; 693 if (lane0[i] != lane0[0] + i) return false; 694 } 695 // Now check that the other lanes are identical to lane0. 696 for (int i = 1; i < LANES; ++i) { 697 for (int j = 0; j < kBytesPerLane; ++j) { 698 if (lane0[j] != shuffle[i * kBytesPerLane + j]) return false; 699 } 700 } 701 *index = lane0[0] / kBytesPerLane; 702 return true; 703 } 704 705 // Tries to match an 8x16 byte shuffle to an equivalent 32x4 shuffle. If 706 // successful, it writes the 32x4 shuffle word indices. E.g. 707 // [0 1 2 3 8 9 10 11 4 5 6 7 12 13 14 15] == [0 2 1 3] 708 static bool TryMatch32x4Shuffle(const uint8_t* shuffle, uint8_t* shuffle32x4); 709 710 // Tries to match an 8x16 byte shuffle to an equivalent 16x8 shuffle. If 711 // successful, it writes the 16x8 shuffle word indices. E.g. 712 // [0 1 8 9 2 3 10 11 4 5 12 13 6 7 14 15] == [0 4 1 5 2 6 3 7] 713 static bool TryMatch16x8Shuffle(const uint8_t* shuffle, uint8_t* shuffle16x8); 714 715 // Tries to match a byte shuffle to a concatenate operation, formed by taking 716 // 16 bytes from the 32 byte concatenation of the inputs. If successful, it 717 // writes the byte offset. E.g. [4 5 6 7 .. 16 17 18 19] concatenates both 718 // source vectors with offset 4. The shuffle should be canonicalized. 719 static bool TryMatchConcat(const uint8_t* shuffle, uint8_t* offset); 720 721 // Tries to match a byte shuffle to a blend operation, which is a shuffle 722 // where no lanes change position. E.g. [0 9 2 11 .. 14 31] interleaves the 723 // even lanes of the first source with the odd lanes of the second. The 724 // shuffle should be canonicalized. 725 static bool TryMatchBlend(const uint8_t* shuffle); 726 727 // Packs 4 bytes of shuffle into a 32 bit immediate. 728 static int32_t Pack4Lanes(const uint8_t* shuffle); 729 730 // =========================================================================== 731 schedule()732 Schedule* schedule() const { return schedule_; } linkage()733 Linkage* linkage() const { return linkage_; } sequence()734 InstructionSequence* sequence() const { return sequence_; } instruction_zone()735 Zone* instruction_zone() const { return sequence()->zone(); } zone()736 Zone* zone() const { return zone_; } 737 set_instruction_selection_failed()738 void set_instruction_selection_failed() { 739 instruction_selection_failed_ = true; 740 } instruction_selection_failed()741 bool instruction_selection_failed() { return instruction_selection_failed_; } 742 743 void MarkPairProjectionsAsWord32(Node* node); 744 bool IsSourcePositionUsed(Node* node); 745 void VisitWord32AtomicBinaryOperation(Node* node, ArchOpcode int8_op, 746 ArchOpcode uint8_op, 747 ArchOpcode int16_op, 748 ArchOpcode uint16_op, 749 ArchOpcode word32_op); 750 void VisitWord64AtomicBinaryOperation(Node* node, ArchOpcode uint8_op, 751 ArchOpcode uint16_op, 752 ArchOpcode uint32_op, 753 ArchOpcode uint64_op); 754 void VisitWord64AtomicNarrowBinop(Node* node, ArchOpcode uint8_op, 755 ArchOpcode uint16_op, ArchOpcode uint32_op); 756 757 // =========================================================================== 758 759 Zone* const zone_; 760 Linkage* const linkage_; 761 InstructionSequence* const sequence_; 762 SourcePositionTable* const source_positions_; 763 SourcePositionMode const source_position_mode_; 764 Features features_; 765 Schedule* const schedule_; 766 BasicBlock* current_block_; 767 ZoneVector<Instruction*> instructions_; 768 InstructionOperandVector continuation_inputs_; 769 InstructionOperandVector continuation_outputs_; 770 InstructionOperandVector continuation_temps_; 771 BoolVector defined_; 772 BoolVector used_; 773 IntVector effect_level_; 774 IntVector virtual_registers_; 775 IntVector virtual_register_rename_; 776 InstructionScheduler* scheduler_; 777 EnableScheduling enable_scheduling_; 778 EnableRootsRelativeAddressing enable_roots_relative_addressing_; 779 EnableSwitchJumpTable enable_switch_jump_table_; 780 781 PoisoningMitigationLevel poisoning_level_; 782 Frame* frame_; 783 bool instruction_selection_failed_; 784 ZoneVector<std::pair<int, int>> instr_origins_; 785 EnableTraceTurboJson trace_turbo_; 786 TickCounter* const tick_counter_; 787 788 // Store the maximal unoptimized frame height and an maximal number of pushed 789 // arguments (for calls). Later used to apply an offset to stack checks. 790 size_t* max_unoptimized_frame_height_; 791 size_t* max_pushed_argument_count_; 792 }; 793 794 } // namespace compiler 795 } // namespace internal 796 } // namespace v8 797 798 #endif // V8_COMPILER_BACKEND_INSTRUCTION_SELECTOR_H_ 799