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_INSTRUCTION_SELECTOR_IMPL_H_ 6 #define V8_COMPILER_INSTRUCTION_SELECTOR_IMPL_H_ 7 8 #include "src/compiler/instruction.h" 9 #include "src/compiler/instruction-selector.h" 10 #include "src/compiler/linkage.h" 11 #include "src/compiler/schedule.h" 12 #include "src/macro-assembler.h" 13 14 namespace v8 { 15 namespace internal { 16 namespace compiler { 17 18 // Helper struct containing data about a table or lookup switch. 19 struct SwitchInfo { 20 int32_t min_value; // minimum value of {case_values} 21 int32_t max_value; // maximum value of {case_values} 22 size_t value_range; // |max_value - min_value| + 1 23 size_t case_count; // number of cases 24 int32_t* case_values; // actual case values, unsorted 25 BasicBlock** case_branches; // basic blocks corresponding to case values 26 BasicBlock* default_branch; // default branch target 27 }; 28 29 // A helper class for the instruction selector that simplifies construction of 30 // Operands. This class implements a base for architecture-specific helpers. 31 class OperandGenerator { 32 public: 33 explicit OperandGenerator(InstructionSelector* selector) 34 : selector_(selector) {} 35 36 InstructionOperand NoOutput() { 37 return InstructionOperand(); // Generates an invalid operand. 38 } 39 40 InstructionOperand DefineAsRegister(Node* node) { 41 return Define(node, 42 UnallocatedOperand(UnallocatedOperand::MUST_HAVE_REGISTER, 43 GetVReg(node))); 44 } 45 46 InstructionOperand DefineSameAsFirst(Node* node) { 47 return Define(node, 48 UnallocatedOperand(UnallocatedOperand::SAME_AS_FIRST_INPUT, 49 GetVReg(node))); 50 } 51 52 InstructionOperand DefineAsFixed(Node* node, Register reg) { 53 return Define(node, UnallocatedOperand(UnallocatedOperand::FIXED_REGISTER, 54 reg.code(), GetVReg(node))); 55 } 56 57 template <typename FPRegType> 58 InstructionOperand DefineAsFixed(Node* node, FPRegType reg) { 59 return Define(node, 60 UnallocatedOperand(UnallocatedOperand::FIXED_FP_REGISTER, 61 reg.code(), GetVReg(node))); 62 } 63 64 InstructionOperand DefineAsConstant(Node* node) { 65 selector()->MarkAsDefined(node); 66 int virtual_register = GetVReg(node); 67 sequence()->AddConstant(virtual_register, ToConstant(node)); 68 return ConstantOperand(virtual_register); 69 } 70 71 InstructionOperand DefineAsLocation(Node* node, LinkageLocation location, 72 MachineRepresentation rep) { 73 return Define(node, ToUnallocatedOperand(location, rep, GetVReg(node))); 74 } 75 76 InstructionOperand DefineAsDualLocation(Node* node, 77 LinkageLocation primary_location, 78 LinkageLocation secondary_location) { 79 return Define(node, 80 ToDualLocationUnallocatedOperand( 81 primary_location, secondary_location, GetVReg(node))); 82 } 83 84 InstructionOperand Use(Node* node) { 85 return Use(node, UnallocatedOperand(UnallocatedOperand::NONE, 86 UnallocatedOperand::USED_AT_START, 87 GetVReg(node))); 88 } 89 90 InstructionOperand UseAny(Node* node) { 91 return Use(node, UnallocatedOperand(UnallocatedOperand::ANY, 92 UnallocatedOperand::USED_AT_START, 93 GetVReg(node))); 94 } 95 96 InstructionOperand UseRegister(Node* node) { 97 return Use(node, UnallocatedOperand(UnallocatedOperand::MUST_HAVE_REGISTER, 98 UnallocatedOperand::USED_AT_START, 99 GetVReg(node))); 100 } 101 102 InstructionOperand UseUniqueSlot(Node* node) { 103 return Use(node, UnallocatedOperand(UnallocatedOperand::MUST_HAVE_SLOT, 104 GetVReg(node))); 105 } 106 107 // Use register or operand for the node. If a register is chosen, it won't 108 // alias any temporary or output registers. 109 InstructionOperand UseUnique(Node* node) { 110 return Use(node, 111 UnallocatedOperand(UnallocatedOperand::NONE, GetVReg(node))); 112 } 113 114 // Use a unique register for the node that does not alias any temporary or 115 // output registers. 116 InstructionOperand UseUniqueRegister(Node* node) { 117 return Use(node, UnallocatedOperand(UnallocatedOperand::MUST_HAVE_REGISTER, 118 GetVReg(node))); 119 } 120 121 InstructionOperand UseFixed(Node* node, Register reg) { 122 return Use(node, UnallocatedOperand(UnallocatedOperand::FIXED_REGISTER, 123 reg.code(), GetVReg(node))); 124 } 125 126 template <typename FPRegType> 127 InstructionOperand UseFixed(Node* node, FPRegType reg) { 128 return Use(node, UnallocatedOperand(UnallocatedOperand::FIXED_FP_REGISTER, 129 reg.code(), GetVReg(node))); 130 } 131 132 InstructionOperand UseExplicit(LinkageLocation location) { 133 MachineRepresentation rep = InstructionSequence::DefaultRepresentation(); 134 if (location.IsRegister()) { 135 return ExplicitOperand(LocationOperand::REGISTER, rep, 136 location.AsRegister()); 137 } else { 138 return ExplicitOperand(LocationOperand::STACK_SLOT, rep, 139 location.GetLocation()); 140 } 141 } 142 143 InstructionOperand UseImmediate(Node* node) { 144 return sequence()->AddImmediate(ToConstant(node)); 145 } 146 147 InstructionOperand UseLocation(Node* node, LinkageLocation location, 148 MachineRepresentation rep) { 149 return Use(node, ToUnallocatedOperand(location, rep, GetVReg(node))); 150 } 151 152 // Used to force gap moves from the from_location to the to_location 153 // immediately before an instruction. 154 InstructionOperand UsePointerLocation(LinkageLocation to_location, 155 LinkageLocation from_location) { 156 MachineRepresentation rep = MachineType::PointerRepresentation(); 157 UnallocatedOperand casted_from_operand = 158 UnallocatedOperand::cast(TempLocation(from_location, rep)); 159 selector_->Emit(kArchNop, casted_from_operand); 160 return ToUnallocatedOperand(to_location, rep, 161 casted_from_operand.virtual_register()); 162 } 163 164 InstructionOperand TempRegister() { 165 return UnallocatedOperand(UnallocatedOperand::MUST_HAVE_REGISTER, 166 UnallocatedOperand::USED_AT_START, 167 sequence()->NextVirtualRegister()); 168 } 169 170 InstructionOperand TempDoubleRegister() { 171 UnallocatedOperand op = UnallocatedOperand( 172 UnallocatedOperand::MUST_HAVE_REGISTER, 173 UnallocatedOperand::USED_AT_START, sequence()->NextVirtualRegister()); 174 sequence()->MarkAsRepresentation(MachineRepresentation::kFloat64, 175 op.virtual_register()); 176 return op; 177 } 178 179 InstructionOperand TempRegister(Register reg) { 180 return UnallocatedOperand(UnallocatedOperand::FIXED_REGISTER, reg.code(), 181 InstructionOperand::kInvalidVirtualRegister); 182 } 183 184 InstructionOperand TempImmediate(int32_t imm) { 185 return sequence()->AddImmediate(Constant(imm)); 186 } 187 188 InstructionOperand TempLocation(LinkageLocation location, 189 MachineRepresentation rep) { 190 return ToUnallocatedOperand(location, rep, 191 sequence()->NextVirtualRegister()); 192 } 193 194 InstructionOperand Label(BasicBlock* block) { 195 return sequence()->AddImmediate( 196 Constant(RpoNumber::FromInt(block->rpo_number()))); 197 } 198 199 protected: 200 InstructionSelector* selector() const { return selector_; } 201 InstructionSequence* sequence() const { return selector()->sequence(); } 202 Zone* zone() const { return selector()->instruction_zone(); } 203 204 private: 205 int GetVReg(Node* node) const { return selector_->GetVirtualRegister(node); } 206 207 static Constant ToConstant(const Node* node) { 208 switch (node->opcode()) { 209 case IrOpcode::kInt32Constant: 210 return Constant(OpParameter<int32_t>(node)); 211 case IrOpcode::kInt64Constant: 212 return Constant(OpParameter<int64_t>(node)); 213 case IrOpcode::kFloat32Constant: 214 return Constant(OpParameter<float>(node)); 215 case IrOpcode::kRelocatableInt32Constant: 216 case IrOpcode::kRelocatableInt64Constant: 217 return Constant(OpParameter<RelocatablePtrConstantInfo>(node)); 218 case IrOpcode::kFloat64Constant: 219 case IrOpcode::kNumberConstant: 220 return Constant(OpParameter<double>(node)); 221 case IrOpcode::kExternalConstant: 222 case IrOpcode::kComment: 223 return Constant(OpParameter<ExternalReference>(node)); 224 case IrOpcode::kHeapConstant: 225 return Constant(OpParameter<Handle<HeapObject>>(node)); 226 default: 227 break; 228 } 229 UNREACHABLE(); 230 return Constant(static_cast<int32_t>(0)); 231 } 232 233 UnallocatedOperand Define(Node* node, UnallocatedOperand operand) { 234 DCHECK_NOT_NULL(node); 235 DCHECK_EQ(operand.virtual_register(), GetVReg(node)); 236 selector()->MarkAsDefined(node); 237 return operand; 238 } 239 240 UnallocatedOperand Use(Node* node, UnallocatedOperand operand) { 241 DCHECK_NOT_NULL(node); 242 DCHECK_EQ(operand.virtual_register(), GetVReg(node)); 243 selector()->MarkAsUsed(node); 244 return operand; 245 } 246 247 UnallocatedOperand ToDualLocationUnallocatedOperand( 248 LinkageLocation primary_location, LinkageLocation secondary_location, 249 int virtual_register) { 250 // We only support the primary location being a register and the secondary 251 // one a slot. 252 DCHECK(primary_location.IsRegister() && 253 secondary_location.IsCalleeFrameSlot()); 254 int reg_id = primary_location.AsRegister(); 255 int slot_id = secondary_location.AsCalleeFrameSlot(); 256 return UnallocatedOperand(reg_id, slot_id, virtual_register); 257 } 258 259 UnallocatedOperand ToUnallocatedOperand(LinkageLocation location, 260 MachineRepresentation rep, 261 int virtual_register) { 262 if (location.IsAnyRegister()) { 263 // any machine register. 264 return UnallocatedOperand(UnallocatedOperand::MUST_HAVE_REGISTER, 265 virtual_register); 266 } 267 if (location.IsCallerFrameSlot()) { 268 // a location on the caller frame. 269 return UnallocatedOperand(UnallocatedOperand::FIXED_SLOT, 270 location.AsCallerFrameSlot(), virtual_register); 271 } 272 if (location.IsCalleeFrameSlot()) { 273 // a spill location on this (callee) frame. 274 return UnallocatedOperand(UnallocatedOperand::FIXED_SLOT, 275 location.AsCalleeFrameSlot(), virtual_register); 276 } 277 // a fixed register. 278 if (IsFloatingPoint(rep)) { 279 return UnallocatedOperand(UnallocatedOperand::FIXED_FP_REGISTER, 280 location.AsRegister(), virtual_register); 281 } 282 return UnallocatedOperand(UnallocatedOperand::FIXED_REGISTER, 283 location.AsRegister(), virtual_register); 284 } 285 286 InstructionSelector* selector_; 287 }; 288 289 290 // The flags continuation is a way to combine a branch or a materialization 291 // of a boolean value with an instruction that sets the flags register. 292 // The whole instruction is treated as a unit by the register allocator, and 293 // thus no spills or moves can be introduced between the flags-setting 294 // instruction and the branch or set it should be combined with. 295 class FlagsContinuation final { 296 public: 297 FlagsContinuation() : mode_(kFlags_none) {} 298 299 // Creates a new flags continuation from the given condition and true/false 300 // blocks. 301 FlagsContinuation(FlagsCondition condition, BasicBlock* true_block, 302 BasicBlock* false_block) 303 : mode_(kFlags_branch), 304 condition_(condition), 305 true_block_(true_block), 306 false_block_(false_block) { 307 DCHECK_NOT_NULL(true_block); 308 DCHECK_NOT_NULL(false_block); 309 } 310 311 // Creates a new flags continuation for an eager deoptimization exit. 312 static FlagsContinuation ForDeoptimize(FlagsCondition condition, 313 Node* frame_state) { 314 return FlagsContinuation(kFlags_deoptimize, condition, frame_state); 315 } 316 317 // Creates a new flags continuation for a boolean value. 318 static FlagsContinuation ForSet(FlagsCondition condition, Node* result) { 319 return FlagsContinuation(kFlags_set, condition, result); 320 } 321 322 bool IsNone() const { return mode_ == kFlags_none; } 323 bool IsBranch() const { return mode_ == kFlags_branch; } 324 bool IsDeoptimize() const { return mode_ == kFlags_deoptimize; } 325 bool IsSet() const { return mode_ == kFlags_set; } 326 FlagsCondition condition() const { 327 DCHECK(!IsNone()); 328 return condition_; 329 } 330 Node* frame_state() const { 331 DCHECK(IsDeoptimize()); 332 return frame_state_or_result_; 333 } 334 Node* result() const { 335 DCHECK(IsSet()); 336 return frame_state_or_result_; 337 } 338 BasicBlock* true_block() const { 339 DCHECK(IsBranch()); 340 return true_block_; 341 } 342 BasicBlock* false_block() const { 343 DCHECK(IsBranch()); 344 return false_block_; 345 } 346 347 void Negate() { 348 DCHECK(!IsNone()); 349 condition_ = NegateFlagsCondition(condition_); 350 } 351 352 void Commute() { 353 DCHECK(!IsNone()); 354 condition_ = CommuteFlagsCondition(condition_); 355 } 356 357 void OverwriteAndNegateIfEqual(FlagsCondition condition) { 358 bool negate = condition_ == kEqual; 359 condition_ = condition; 360 if (negate) Negate(); 361 } 362 363 // Encodes this flags continuation into the given opcode. 364 InstructionCode Encode(InstructionCode opcode) { 365 opcode |= FlagsModeField::encode(mode_); 366 if (mode_ != kFlags_none) { 367 opcode |= FlagsConditionField::encode(condition_); 368 } 369 return opcode; 370 } 371 372 private: 373 FlagsContinuation(FlagsMode mode, FlagsCondition condition, 374 Node* frame_state_or_result) 375 : mode_(mode), 376 condition_(condition), 377 frame_state_or_result_(frame_state_or_result) { 378 DCHECK_NOT_NULL(frame_state_or_result); 379 } 380 381 FlagsMode const mode_; 382 FlagsCondition condition_; 383 Node* frame_state_or_result_; // Only valid if mode_ == kFlags_deoptimize 384 // or mode_ == kFlags_set. 385 BasicBlock* true_block_; // Only valid if mode_ == kFlags_branch. 386 BasicBlock* false_block_; // Only valid if mode_ == kFlags_branch. 387 }; 388 389 } // namespace compiler 390 } // namespace internal 391 } // namespace v8 392 393 #endif // V8_COMPILER_INSTRUCTION_SELECTOR_IMPL_H_ 394