1 /* 2 * Copyright (C) 2017 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 #ifndef ART_COMPILER_OPTIMIZING_NODES_VECTOR_H_ 18 #define ART_COMPILER_OPTIMIZING_NODES_VECTOR_H_ 19 20 // This #include should never be used by compilation, because this header file (nodes_vector.h) 21 // is included in the header file nodes.h itself. However it gives editing tools better context. 22 #include "nodes.h" 23 24 namespace art { 25 26 // Memory alignment, represented as an offset relative to a base, where 0 <= offset < base, 27 // and base is a power of two. For example, the value Alignment(16, 0) means memory is 28 // perfectly aligned at a 16-byte boundary, whereas the value Alignment(16, 4) means 29 // memory is always exactly 4 bytes above such a boundary. 30 class Alignment { 31 public: 32 Alignment(size_t base, size_t offset) : base_(base), offset_(offset) { 33 DCHECK_LT(offset, base); 34 DCHECK(IsPowerOfTwo(base)); 35 } 36 37 // Returns true if memory is at least aligned at the given boundary. 38 // Assumes requested base is power of two. 39 bool IsAlignedAt(size_t base) const { 40 DCHECK_NE(0u, base); 41 DCHECK(IsPowerOfTwo(base)); 42 return ((offset_ | base_) & (base - 1u)) == 0; 43 } 44 45 size_t Base() const { return base_; } 46 47 size_t Offset() const { return offset_; } 48 49 std::string ToString() const { 50 return "ALIGN(" + std::to_string(base_) + "," + std::to_string(offset_) + ")"; 51 } 52 53 bool operator==(const Alignment& other) const { 54 return base_ == other.base_ && offset_ == other.offset_; 55 } 56 57 private: 58 size_t base_; 59 size_t offset_; 60 }; 61 62 // 63 // Definitions of abstract vector operations in HIR. 64 // 65 66 // Abstraction of a vector operation, i.e., an operation that performs 67 // GetVectorLength() x GetPackedType() operations simultaneously. 68 class HVecOperation : public HVariableInputSizeInstruction { 69 public: 70 // A SIMD operation looks like a FPU location. 71 // TODO: we could introduce SIMD types in HIR. 72 static constexpr DataType::Type kSIMDType = DataType::Type::kFloat64; 73 74 HVecOperation(InstructionKind kind, 75 ArenaAllocator* allocator, 76 DataType::Type packed_type, 77 SideEffects side_effects, 78 size_t number_of_inputs, 79 size_t vector_length, 80 uint32_t dex_pc) 81 : HVariableInputSizeInstruction(kind, 82 kSIMDType, 83 side_effects, 84 dex_pc, 85 allocator, 86 number_of_inputs, 87 kArenaAllocVectorNode), 88 vector_length_(vector_length) { 89 SetPackedField<PackedTypeField>(packed_type); 90 DCHECK_LT(1u, vector_length); 91 } 92 93 // Returns the number of elements packed in a vector. 94 size_t GetVectorLength() const { 95 return vector_length_; 96 } 97 98 // Returns the number of bytes in a full vector. 99 size_t GetVectorNumberOfBytes() const { 100 return vector_length_ * DataType::Size(GetPackedType()); 101 } 102 103 // Returns the true component type packed in a vector. 104 DataType::Type GetPackedType() const { 105 return GetPackedField<PackedTypeField>(); 106 } 107 108 // Assumes vector nodes cannot be moved by default. Each concrete implementation 109 // that can be moved should override this method and return true. 110 // 111 // Note: similar approach is used for instruction scheduling (if it is turned on for the target): 112 // by default HScheduler::IsSchedulable returns false for a particular HVecOperation. 113 // HScheduler${ARCH}::IsSchedulable can be overridden to return true for an instruction (see 114 // scheduler_arm64.h for example) if it is safe to schedule it; in this case one *must* also 115 // look at/update HScheduler${ARCH}::IsSchedulingBarrier for this instruction. 116 // 117 // Note: For newly introduced vector instructions HScheduler${ARCH}::IsSchedulingBarrier must be 118 // altered to return true if the instruction might reside outside the SIMD loop body since SIMD 119 // registers are not kept alive across vector loop boundaries (yet). 120 bool CanBeMoved() const override { return false; } 121 122 // Tests if all data of a vector node (vector length and packed type) is equal. 123 // Each concrete implementation that adds more fields should test equality of 124 // those fields in its own method *and* call all super methods. 125 bool InstructionDataEquals(const HInstruction* other) const override { 126 DCHECK(other->IsVecOperation()); 127 const HVecOperation* o = other->AsVecOperation(); 128 return GetVectorLength() == o->GetVectorLength() && GetPackedType() == o->GetPackedType(); 129 } 130 131 // Maps an integral type to the same-size signed type and leaves other types alone. 132 static DataType::Type ToSignedType(DataType::Type type) { 133 switch (type) { 134 case DataType::Type::kBool: // 1-byte storage unit 135 case DataType::Type::kUint8: 136 return DataType::Type::kInt8; 137 case DataType::Type::kUint16: 138 return DataType::Type::kInt16; 139 default: 140 DCHECK(type != DataType::Type::kVoid && type != DataType::Type::kReference) << type; 141 return type; 142 } 143 } 144 145 // Maps an integral type to the same-size unsigned type and leaves other types alone. 146 static DataType::Type ToUnsignedType(DataType::Type type) { 147 switch (type) { 148 case DataType::Type::kBool: // 1-byte storage unit 149 case DataType::Type::kInt8: 150 return DataType::Type::kUint8; 151 case DataType::Type::kInt16: 152 return DataType::Type::kUint16; 153 default: 154 DCHECK(type != DataType::Type::kVoid && type != DataType::Type::kReference) << type; 155 return type; 156 } 157 } 158 159 // Maps an integral type to the same-size (un)signed type. Leaves other types alone. 160 static DataType::Type ToProperType(DataType::Type type, bool is_unsigned) { 161 return is_unsigned ? ToUnsignedType(type) : ToSignedType(type); 162 } 163 164 // Helper method to determine if an instruction returns a SIMD value. 165 // TODO: This method is needed until we introduce SIMD as proper type. 166 static bool ReturnsSIMDValue(HInstruction* instruction) { 167 if (instruction->IsVecOperation()) { 168 return !instruction->IsVecExtractScalar(); // only scalar returning vec op 169 } else if (instruction->IsPhi()) { 170 // Vectorizer only uses Phis in reductions, so checking for a 2-way phi 171 // with a direct vector operand as second argument suffices. 172 return 173 instruction->GetType() == kSIMDType && 174 instruction->InputCount() == 2 && 175 instruction->InputAt(1)->IsVecOperation(); 176 } 177 return false; 178 } 179 180 DECLARE_ABSTRACT_INSTRUCTION(VecOperation); 181 182 protected: 183 // Additional packed bits. 184 static constexpr size_t kFieldPackedType = HInstruction::kNumberOfGenericPackedBits; 185 static constexpr size_t kFieldPackedTypeSize = 186 MinimumBitsToStore(static_cast<size_t>(DataType::Type::kLast)); 187 static constexpr size_t kNumberOfVectorOpPackedBits = kFieldPackedType + kFieldPackedTypeSize; 188 static_assert(kNumberOfVectorOpPackedBits <= kMaxNumberOfPackedBits, "Too many packed fields."); 189 using PackedTypeField = BitField<DataType::Type, kFieldPackedType, kFieldPackedTypeSize>; 190 191 DEFAULT_COPY_CONSTRUCTOR(VecOperation); 192 193 private: 194 const size_t vector_length_; 195 }; 196 197 // Abstraction of a unary vector operation. 198 class HVecUnaryOperation : public HVecOperation { 199 public: 200 HVecUnaryOperation(InstructionKind kind, 201 ArenaAllocator* allocator, 202 HInstruction* input, 203 DataType::Type packed_type, 204 size_t vector_length, 205 uint32_t dex_pc) 206 : HVecOperation(kind, 207 allocator, 208 packed_type, 209 SideEffects::None(), 210 /* number_of_inputs= */ 1, 211 vector_length, 212 dex_pc) { 213 SetRawInputAt(0, input); 214 } 215 216 HInstruction* GetInput() const { return InputAt(0); } 217 218 DECLARE_ABSTRACT_INSTRUCTION(VecUnaryOperation); 219 220 protected: 221 DEFAULT_COPY_CONSTRUCTOR(VecUnaryOperation); 222 }; 223 224 // Abstraction of a binary vector operation. 225 class HVecBinaryOperation : public HVecOperation { 226 public: 227 HVecBinaryOperation(InstructionKind kind, 228 ArenaAllocator* allocator, 229 HInstruction* left, 230 HInstruction* right, 231 DataType::Type packed_type, 232 size_t vector_length, 233 uint32_t dex_pc) 234 : HVecOperation(kind, 235 allocator, 236 packed_type, 237 SideEffects::None(), 238 /* number_of_inputs= */ 2, 239 vector_length, 240 dex_pc) { 241 SetRawInputAt(0, left); 242 SetRawInputAt(1, right); 243 } 244 245 HInstruction* GetLeft() const { return InputAt(0); } 246 HInstruction* GetRight() const { return InputAt(1); } 247 248 DECLARE_ABSTRACT_INSTRUCTION(VecBinaryOperation); 249 250 protected: 251 DEFAULT_COPY_CONSTRUCTOR(VecBinaryOperation); 252 }; 253 254 // Abstraction of a vector operation that references memory, with an alignment. 255 // The Android runtime guarantees elements have at least natural alignment. 256 class HVecMemoryOperation : public HVecOperation { 257 public: 258 HVecMemoryOperation(InstructionKind kind, 259 ArenaAllocator* allocator, 260 DataType::Type packed_type, 261 SideEffects side_effects, 262 size_t number_of_inputs, 263 size_t vector_length, 264 uint32_t dex_pc) 265 : HVecOperation(kind, 266 allocator, 267 packed_type, 268 side_effects, 269 number_of_inputs, 270 vector_length, 271 dex_pc), 272 alignment_(DataType::Size(packed_type), 0) { 273 DCHECK_GE(number_of_inputs, 2u); 274 } 275 276 void SetAlignment(Alignment alignment) { alignment_ = alignment; } 277 278 Alignment GetAlignment() const { return alignment_; } 279 280 HInstruction* GetArray() const { return InputAt(0); } 281 HInstruction* GetIndex() const { return InputAt(1); } 282 283 bool InstructionDataEquals(const HInstruction* other) const override { 284 DCHECK(other->IsVecMemoryOperation()); 285 const HVecMemoryOperation* o = other->AsVecMemoryOperation(); 286 return HVecOperation::InstructionDataEquals(o) && GetAlignment() == o->GetAlignment(); 287 } 288 289 DECLARE_ABSTRACT_INSTRUCTION(VecMemoryOperation); 290 291 protected: 292 DEFAULT_COPY_CONSTRUCTOR(VecMemoryOperation); 293 294 private: 295 Alignment alignment_; 296 }; 297 298 // Packed type consistency checker ("same vector length" integral types may mix freely). 299 // Tests relaxed type consistency in which packed same-size integral types can co-exist, 300 // but other type mixes are an error. 301 inline static bool HasConsistentPackedTypes(HInstruction* input, DataType::Type type) { 302 if (input->IsPhi()) { 303 return input->GetType() == HVecOperation::kSIMDType; // carries SIMD 304 } 305 DCHECK(input->IsVecOperation()); 306 DataType::Type input_type = input->AsVecOperation()->GetPackedType(); 307 DCHECK_EQ(HVecOperation::ToUnsignedType(input_type) == HVecOperation::ToUnsignedType(type), 308 HVecOperation::ToSignedType(input_type) == HVecOperation::ToSignedType(type)); 309 return HVecOperation::ToSignedType(input_type) == HVecOperation::ToSignedType(type); 310 } 311 312 // 313 // Definitions of concrete unary vector operations in HIR. 314 // 315 316 // Replicates the given scalar into a vector, 317 // viz. replicate(x) = [ x, .. , x ]. 318 class HVecReplicateScalar final : public HVecUnaryOperation { 319 public: 320 HVecReplicateScalar(ArenaAllocator* allocator, 321 HInstruction* scalar, 322 DataType::Type packed_type, 323 size_t vector_length, 324 uint32_t dex_pc) 325 : HVecUnaryOperation( 326 kVecReplicateScalar, allocator, scalar, packed_type, vector_length, dex_pc) { 327 DCHECK(!ReturnsSIMDValue(scalar)); 328 } 329 330 // A replicate needs to stay in place, since SIMD registers are not 331 // kept alive across vector loop boundaries (yet). 332 bool CanBeMoved() const override { return false; } 333 334 DECLARE_INSTRUCTION(VecReplicateScalar); 335 336 protected: 337 DEFAULT_COPY_CONSTRUCTOR(VecReplicateScalar); 338 }; 339 340 // Extracts a particular scalar from the given vector, 341 // viz. extract[ x1, .. , xn ] = x_i. 342 // 343 // TODO: for now only i == 1 case supported. 344 class HVecExtractScalar final : public HVecUnaryOperation { 345 public: 346 HVecExtractScalar(ArenaAllocator* allocator, 347 HInstruction* input, 348 DataType::Type packed_type, 349 size_t vector_length, 350 size_t index, 351 uint32_t dex_pc) 352 : HVecUnaryOperation( 353 kVecExtractScalar, allocator, input, packed_type, vector_length, dex_pc) { 354 DCHECK(HasConsistentPackedTypes(input, packed_type)); 355 DCHECK_LT(index, vector_length); 356 DCHECK_EQ(index, 0u); 357 // Yields a single component in the vector. 358 // Overrides the kSIMDType set by the VecOperation constructor. 359 SetPackedField<TypeField>(packed_type); 360 } 361 362 // An extract needs to stay in place, since SIMD registers are not 363 // kept alive across vector loop boundaries (yet). 364 bool CanBeMoved() const override { return false; } 365 366 DECLARE_INSTRUCTION(VecExtractScalar); 367 368 protected: 369 DEFAULT_COPY_CONSTRUCTOR(VecExtractScalar); 370 }; 371 372 // Reduces the given vector into the first element as sum/min/max, 373 // viz. sum-reduce[ x1, .. , xn ] = [ y, ---- ], where y = sum xi 374 // and the "-" denotes "don't care" (implementation dependent). 375 class HVecReduce final : public HVecUnaryOperation { 376 public: 377 enum ReductionKind { 378 kSum = 1, 379 kMin = 2, 380 kMax = 3 381 }; 382 383 HVecReduce(ArenaAllocator* allocator, 384 HInstruction* input, 385 DataType::Type packed_type, 386 size_t vector_length, 387 ReductionKind reduction_kind, 388 uint32_t dex_pc) 389 : HVecUnaryOperation(kVecReduce, allocator, input, packed_type, vector_length, dex_pc), 390 reduction_kind_(reduction_kind) { 391 DCHECK(HasConsistentPackedTypes(input, packed_type)); 392 } 393 394 ReductionKind GetReductionKind() const { return reduction_kind_; } 395 396 bool CanBeMoved() const override { return true; } 397 398 bool InstructionDataEquals(const HInstruction* other) const override { 399 DCHECK(other->IsVecReduce()); 400 const HVecReduce* o = other->AsVecReduce(); 401 return HVecOperation::InstructionDataEquals(o) && GetReductionKind() == o->GetReductionKind(); 402 } 403 404 DECLARE_INSTRUCTION(VecReduce); 405 406 protected: 407 DEFAULT_COPY_CONSTRUCTOR(VecReduce); 408 409 private: 410 const ReductionKind reduction_kind_; 411 }; 412 413 // Converts every component in the vector, 414 // viz. cnv[ x1, .. , xn ] = [ cnv(x1), .. , cnv(xn) ]. 415 class HVecCnv final : public HVecUnaryOperation { 416 public: 417 HVecCnv(ArenaAllocator* allocator, 418 HInstruction* input, 419 DataType::Type packed_type, 420 size_t vector_length, 421 uint32_t dex_pc) 422 : HVecUnaryOperation(kVecCnv, allocator, input, packed_type, vector_length, dex_pc) { 423 DCHECK(input->IsVecOperation()); 424 DCHECK_NE(GetInputType(), GetResultType()); // actual convert 425 } 426 427 DataType::Type GetInputType() const { return InputAt(0)->AsVecOperation()->GetPackedType(); } 428 DataType::Type GetResultType() const { return GetPackedType(); } 429 430 bool CanBeMoved() const override { return true; } 431 432 DECLARE_INSTRUCTION(VecCnv); 433 434 protected: 435 DEFAULT_COPY_CONSTRUCTOR(VecCnv); 436 }; 437 438 // Negates every component in the vector, 439 // viz. neg[ x1, .. , xn ] = [ -x1, .. , -xn ]. 440 class HVecNeg final : public HVecUnaryOperation { 441 public: 442 HVecNeg(ArenaAllocator* allocator, 443 HInstruction* input, 444 DataType::Type packed_type, 445 size_t vector_length, 446 uint32_t dex_pc) 447 : HVecUnaryOperation(kVecNeg, allocator, input, packed_type, vector_length, dex_pc) { 448 DCHECK(HasConsistentPackedTypes(input, packed_type)); 449 } 450 451 bool CanBeMoved() const override { return true; } 452 453 DECLARE_INSTRUCTION(VecNeg); 454 455 protected: 456 DEFAULT_COPY_CONSTRUCTOR(VecNeg); 457 }; 458 459 // Takes absolute value of every component in the vector, 460 // viz. abs[ x1, .. , xn ] = [ |x1|, .. , |xn| ] 461 // for signed operand x. 462 class HVecAbs final : public HVecUnaryOperation { 463 public: 464 HVecAbs(ArenaAllocator* allocator, 465 HInstruction* input, 466 DataType::Type packed_type, 467 size_t vector_length, 468 uint32_t dex_pc) 469 : HVecUnaryOperation(kVecAbs, allocator, input, packed_type, vector_length, dex_pc) { 470 DCHECK(HasConsistentPackedTypes(input, packed_type)); 471 } 472 473 bool CanBeMoved() const override { return true; } 474 475 DECLARE_INSTRUCTION(VecAbs); 476 477 protected: 478 DEFAULT_COPY_CONSTRUCTOR(VecAbs); 479 }; 480 481 // Bitwise- or boolean-nots every component in the vector, 482 // viz. not[ x1, .. , xn ] = [ ~x1, .. , ~xn ], or 483 // not[ x1, .. , xn ] = [ !x1, .. , !xn ] for boolean. 484 class HVecNot final : public HVecUnaryOperation { 485 public: 486 HVecNot(ArenaAllocator* allocator, 487 HInstruction* input, 488 DataType::Type packed_type, 489 size_t vector_length, 490 uint32_t dex_pc) 491 : HVecUnaryOperation(kVecNot, allocator, input, packed_type, vector_length, dex_pc) { 492 DCHECK(input->IsVecOperation()); 493 } 494 495 bool CanBeMoved() const override { return true; } 496 497 DECLARE_INSTRUCTION(VecNot); 498 499 protected: 500 DEFAULT_COPY_CONSTRUCTOR(VecNot); 501 }; 502 503 // 504 // Definitions of concrete binary vector operations in HIR. 505 // 506 507 // Adds every component in the two vectors, 508 // viz. [ x1, .. , xn ] + [ y1, .. , yn ] = [ x1 + y1, .. , xn + yn ]. 509 class HVecAdd final : public HVecBinaryOperation { 510 public: 511 HVecAdd(ArenaAllocator* allocator, 512 HInstruction* left, 513 HInstruction* right, 514 DataType::Type packed_type, 515 size_t vector_length, 516 uint32_t dex_pc) 517 : HVecBinaryOperation(kVecAdd, allocator, left, right, packed_type, vector_length, dex_pc) { 518 DCHECK(HasConsistentPackedTypes(left, packed_type)); 519 DCHECK(HasConsistentPackedTypes(right, packed_type)); 520 } 521 522 bool CanBeMoved() const override { return true; } 523 524 DECLARE_INSTRUCTION(VecAdd); 525 526 protected: 527 DEFAULT_COPY_CONSTRUCTOR(VecAdd); 528 }; 529 530 // Adds every component in the two vectors using saturation arithmetic, 531 // viz. [ x1, .. , xn ] + [ y1, .. , yn ] = [ x1 +_sat y1, .. , xn +_sat yn ] 532 // for either both signed or both unsigned operands x, y (reflected in packed_type). 533 class HVecSaturationAdd final : public HVecBinaryOperation { 534 public: 535 HVecSaturationAdd(ArenaAllocator* allocator, 536 HInstruction* left, 537 HInstruction* right, 538 DataType::Type packed_type, 539 size_t vector_length, 540 uint32_t dex_pc) 541 : HVecBinaryOperation( 542 kVecSaturationAdd, allocator, left, right, packed_type, vector_length, dex_pc) { 543 DCHECK(HasConsistentPackedTypes(left, packed_type)); 544 DCHECK(HasConsistentPackedTypes(right, packed_type)); 545 } 546 547 bool CanBeMoved() const override { return true; } 548 549 DECLARE_INSTRUCTION(VecSaturationAdd); 550 551 protected: 552 DEFAULT_COPY_CONSTRUCTOR(VecSaturationAdd); 553 }; 554 555 // Performs halving add on every component in the two vectors, viz. 556 // rounded [ x1, .. , xn ] hradd [ y1, .. , yn ] = [ (x1 + y1 + 1) >> 1, .. , (xn + yn + 1) >> 1 ] 557 // truncated [ x1, .. , xn ] hadd [ y1, .. , yn ] = [ (x1 + y1) >> 1, .. , (xn + yn ) >> 1 ] 558 // for either both signed or both unsigned operands x, y (reflected in packed_type). 559 class HVecHalvingAdd final : public HVecBinaryOperation { 560 public: 561 HVecHalvingAdd(ArenaAllocator* allocator, 562 HInstruction* left, 563 HInstruction* right, 564 DataType::Type packed_type, 565 size_t vector_length, 566 bool is_rounded, 567 uint32_t dex_pc) 568 : HVecBinaryOperation( 569 kVecHalvingAdd, allocator, left, right, packed_type, vector_length, dex_pc) { 570 DCHECK(HasConsistentPackedTypes(left, packed_type)); 571 DCHECK(HasConsistentPackedTypes(right, packed_type)); 572 SetPackedFlag<kFieldHAddIsRounded>(is_rounded); 573 } 574 575 bool IsRounded() const { return GetPackedFlag<kFieldHAddIsRounded>(); } 576 577 bool CanBeMoved() const override { return true; } 578 579 bool InstructionDataEquals(const HInstruction* other) const override { 580 DCHECK(other->IsVecHalvingAdd()); 581 const HVecHalvingAdd* o = other->AsVecHalvingAdd(); 582 return HVecOperation::InstructionDataEquals(o) && IsRounded() == o->IsRounded(); 583 } 584 585 DECLARE_INSTRUCTION(VecHalvingAdd); 586 587 protected: 588 DEFAULT_COPY_CONSTRUCTOR(VecHalvingAdd); 589 590 private: 591 // Additional packed bits. 592 static constexpr size_t kFieldHAddIsRounded = HVecOperation::kNumberOfVectorOpPackedBits; 593 static constexpr size_t kNumberOfHAddPackedBits = kFieldHAddIsRounded + 1; 594 static_assert(kNumberOfHAddPackedBits <= kMaxNumberOfPackedBits, "Too many packed fields."); 595 }; 596 597 // Subtracts every component in the two vectors, 598 // viz. [ x1, .. , xn ] - [ y1, .. , yn ] = [ x1 - y1, .. , xn - yn ]. 599 class HVecSub final : public HVecBinaryOperation { 600 public: 601 HVecSub(ArenaAllocator* allocator, 602 HInstruction* left, 603 HInstruction* right, 604 DataType::Type packed_type, 605 size_t vector_length, 606 uint32_t dex_pc) 607 : HVecBinaryOperation(kVecSub, allocator, left, right, packed_type, vector_length, dex_pc) { 608 DCHECK(HasConsistentPackedTypes(left, packed_type)); 609 DCHECK(HasConsistentPackedTypes(right, packed_type)); 610 } 611 612 bool CanBeMoved() const override { return true; } 613 614 DECLARE_INSTRUCTION(VecSub); 615 616 protected: 617 DEFAULT_COPY_CONSTRUCTOR(VecSub); 618 }; 619 620 // Subtracts every component in the two vectors using saturation arithmetic, 621 // viz. [ x1, .. , xn ] + [ y1, .. , yn ] = [ x1 -_sat y1, .. , xn -_sat yn ] 622 // for either both signed or both unsigned operands x, y (reflected in packed_type). 623 class HVecSaturationSub final : public HVecBinaryOperation { 624 public: 625 HVecSaturationSub(ArenaAllocator* allocator, 626 HInstruction* left, 627 HInstruction* right, 628 DataType::Type packed_type, 629 size_t vector_length, 630 uint32_t dex_pc) 631 : HVecBinaryOperation( 632 kVecSaturationSub, allocator, left, right, packed_type, vector_length, dex_pc) { 633 DCHECK(HasConsistentPackedTypes(left, packed_type)); 634 DCHECK(HasConsistentPackedTypes(right, packed_type)); 635 } 636 637 bool CanBeMoved() const override { return true; } 638 639 DECLARE_INSTRUCTION(VecSaturationSub); 640 641 protected: 642 DEFAULT_COPY_CONSTRUCTOR(VecSaturationSub); 643 }; 644 645 // Multiplies every component in the two vectors, 646 // viz. [ x1, .. , xn ] * [ y1, .. , yn ] = [ x1 * y1, .. , xn * yn ]. 647 class HVecMul final : public HVecBinaryOperation { 648 public: 649 HVecMul(ArenaAllocator* allocator, 650 HInstruction* left, 651 HInstruction* right, 652 DataType::Type packed_type, 653 size_t vector_length, 654 uint32_t dex_pc) 655 : HVecBinaryOperation(kVecMul, allocator, left, right, packed_type, vector_length, dex_pc) { 656 DCHECK(HasConsistentPackedTypes(left, packed_type)); 657 DCHECK(HasConsistentPackedTypes(right, packed_type)); 658 } 659 660 bool CanBeMoved() const override { return true; } 661 662 DECLARE_INSTRUCTION(VecMul); 663 664 protected: 665 DEFAULT_COPY_CONSTRUCTOR(VecMul); 666 }; 667 668 // Divides every component in the two vectors, 669 // viz. [ x1, .. , xn ] / [ y1, .. , yn ] = [ x1 / y1, .. , xn / yn ]. 670 class HVecDiv final : public HVecBinaryOperation { 671 public: 672 HVecDiv(ArenaAllocator* allocator, 673 HInstruction* left, 674 HInstruction* right, 675 DataType::Type packed_type, 676 size_t vector_length, 677 uint32_t dex_pc) 678 : HVecBinaryOperation(kVecDiv, allocator, left, right, packed_type, vector_length, dex_pc) { 679 DCHECK(HasConsistentPackedTypes(left, packed_type)); 680 DCHECK(HasConsistentPackedTypes(right, packed_type)); 681 } 682 683 bool CanBeMoved() const override { return true; } 684 685 DECLARE_INSTRUCTION(VecDiv); 686 687 protected: 688 DEFAULT_COPY_CONSTRUCTOR(VecDiv); 689 }; 690 691 // Takes minimum of every component in the two vectors, 692 // viz. MIN( [ x1, .. , xn ] , [ y1, .. , yn ]) = [ min(x1, y1), .. , min(xn, yn) ] 693 // for either both signed or both unsigned operands x, y (reflected in packed_type). 694 class HVecMin final : public HVecBinaryOperation { 695 public: 696 HVecMin(ArenaAllocator* allocator, 697 HInstruction* left, 698 HInstruction* right, 699 DataType::Type packed_type, 700 size_t vector_length, 701 uint32_t dex_pc) 702 : HVecBinaryOperation(kVecMin, allocator, left, right, packed_type, vector_length, dex_pc) { 703 DCHECK(HasConsistentPackedTypes(left, packed_type)); 704 DCHECK(HasConsistentPackedTypes(right, packed_type)); 705 } 706 707 bool CanBeMoved() const override { return true; } 708 709 DECLARE_INSTRUCTION(VecMin); 710 711 protected: 712 DEFAULT_COPY_CONSTRUCTOR(VecMin); 713 }; 714 715 // Takes maximum of every component in the two vectors, 716 // viz. MAX( [ x1, .. , xn ] , [ y1, .. , yn ]) = [ max(x1, y1), .. , max(xn, yn) ] 717 // for either both signed or both unsigned operands x, y (reflected in packed_type). 718 class HVecMax final : public HVecBinaryOperation { 719 public: 720 HVecMax(ArenaAllocator* allocator, 721 HInstruction* left, 722 HInstruction* right, 723 DataType::Type packed_type, 724 size_t vector_length, 725 uint32_t dex_pc) 726 : HVecBinaryOperation(kVecMax, allocator, left, right, packed_type, vector_length, dex_pc) { 727 DCHECK(HasConsistentPackedTypes(left, packed_type)); 728 DCHECK(HasConsistentPackedTypes(right, packed_type)); 729 } 730 731 bool CanBeMoved() const override { return true; } 732 733 DECLARE_INSTRUCTION(VecMax); 734 735 protected: 736 DEFAULT_COPY_CONSTRUCTOR(VecMax); 737 }; 738 739 // Bitwise-ands every component in the two vectors, 740 // viz. [ x1, .. , xn ] & [ y1, .. , yn ] = [ x1 & y1, .. , xn & yn ]. 741 class HVecAnd final : public HVecBinaryOperation { 742 public: 743 HVecAnd(ArenaAllocator* allocator, 744 HInstruction* left, 745 HInstruction* right, 746 DataType::Type packed_type, 747 size_t vector_length, 748 uint32_t dex_pc) 749 : HVecBinaryOperation(kVecAnd, allocator, left, right, packed_type, vector_length, dex_pc) { 750 DCHECK(left->IsVecOperation() && right->IsVecOperation()); 751 } 752 753 bool CanBeMoved() const override { return true; } 754 755 DECLARE_INSTRUCTION(VecAnd); 756 757 protected: 758 DEFAULT_COPY_CONSTRUCTOR(VecAnd); 759 }; 760 761 // Bitwise-and-nots every component in the two vectors, 762 // viz. [ x1, .. , xn ] and-not [ y1, .. , yn ] = [ ~x1 & y1, .. , ~xn & yn ]. 763 class HVecAndNot final : public HVecBinaryOperation { 764 public: 765 HVecAndNot(ArenaAllocator* allocator, 766 HInstruction* left, 767 HInstruction* right, 768 DataType::Type packed_type, 769 size_t vector_length, 770 uint32_t dex_pc) 771 : HVecBinaryOperation( 772 kVecAndNot, allocator, left, right, packed_type, vector_length, dex_pc) { 773 DCHECK(left->IsVecOperation() && right->IsVecOperation()); 774 } 775 776 bool CanBeMoved() const override { return true; } 777 778 DECLARE_INSTRUCTION(VecAndNot); 779 780 protected: 781 DEFAULT_COPY_CONSTRUCTOR(VecAndNot); 782 }; 783 784 // Bitwise-ors every component in the two vectors, 785 // viz. [ x1, .. , xn ] | [ y1, .. , yn ] = [ x1 | y1, .. , xn | yn ]. 786 class HVecOr final : public HVecBinaryOperation { 787 public: 788 HVecOr(ArenaAllocator* allocator, 789 HInstruction* left, 790 HInstruction* right, 791 DataType::Type packed_type, 792 size_t vector_length, 793 uint32_t dex_pc) 794 : HVecBinaryOperation(kVecOr, allocator, left, right, packed_type, vector_length, dex_pc) { 795 DCHECK(left->IsVecOperation() && right->IsVecOperation()); 796 } 797 798 bool CanBeMoved() const override { return true; } 799 800 DECLARE_INSTRUCTION(VecOr); 801 802 protected: 803 DEFAULT_COPY_CONSTRUCTOR(VecOr); 804 }; 805 806 // Bitwise-xors every component in the two vectors, 807 // viz. [ x1, .. , xn ] ^ [ y1, .. , yn ] = [ x1 ^ y1, .. , xn ^ yn ]. 808 class HVecXor final : public HVecBinaryOperation { 809 public: 810 HVecXor(ArenaAllocator* allocator, 811 HInstruction* left, 812 HInstruction* right, 813 DataType::Type packed_type, 814 size_t vector_length, 815 uint32_t dex_pc) 816 : HVecBinaryOperation(kVecXor, allocator, left, right, packed_type, vector_length, dex_pc) { 817 DCHECK(left->IsVecOperation() && right->IsVecOperation()); 818 } 819 820 bool CanBeMoved() const override { return true; } 821 822 DECLARE_INSTRUCTION(VecXor); 823 824 protected: 825 DEFAULT_COPY_CONSTRUCTOR(VecXor); 826 }; 827 828 // Logically shifts every component in the vector left by the given distance, 829 // viz. [ x1, .. , xn ] << d = [ x1 << d, .. , xn << d ]. 830 class HVecShl final : public HVecBinaryOperation { 831 public: 832 HVecShl(ArenaAllocator* allocator, 833 HInstruction* left, 834 HInstruction* right, 835 DataType::Type packed_type, 836 size_t vector_length, 837 uint32_t dex_pc) 838 : HVecBinaryOperation(kVecShl, allocator, left, right, packed_type, vector_length, dex_pc) { 839 DCHECK(HasConsistentPackedTypes(left, packed_type)); 840 } 841 842 bool CanBeMoved() const override { return true; } 843 844 DECLARE_INSTRUCTION(VecShl); 845 846 protected: 847 DEFAULT_COPY_CONSTRUCTOR(VecShl); 848 }; 849 850 // Arithmetically shifts every component in the vector right by the given distance, 851 // viz. [ x1, .. , xn ] >> d = [ x1 >> d, .. , xn >> d ]. 852 class HVecShr final : public HVecBinaryOperation { 853 public: 854 HVecShr(ArenaAllocator* allocator, 855 HInstruction* left, 856 HInstruction* right, 857 DataType::Type packed_type, 858 size_t vector_length, 859 uint32_t dex_pc) 860 : HVecBinaryOperation(kVecShr, allocator, left, right, packed_type, vector_length, dex_pc) { 861 DCHECK(HasConsistentPackedTypes(left, packed_type)); 862 } 863 864 bool CanBeMoved() const override { return true; } 865 866 DECLARE_INSTRUCTION(VecShr); 867 868 protected: 869 DEFAULT_COPY_CONSTRUCTOR(VecShr); 870 }; 871 872 // Logically shifts every component in the vector right by the given distance, 873 // viz. [ x1, .. , xn ] >>> d = [ x1 >>> d, .. , xn >>> d ]. 874 class HVecUShr final : public HVecBinaryOperation { 875 public: 876 HVecUShr(ArenaAllocator* allocator, 877 HInstruction* left, 878 HInstruction* right, 879 DataType::Type packed_type, 880 size_t vector_length, 881 uint32_t dex_pc) 882 : HVecBinaryOperation(kVecUShr, allocator, left, right, packed_type, vector_length, dex_pc) { 883 DCHECK(HasConsistentPackedTypes(left, packed_type)); 884 } 885 886 bool CanBeMoved() const override { return true; } 887 888 DECLARE_INSTRUCTION(VecUShr); 889 890 protected: 891 DEFAULT_COPY_CONSTRUCTOR(VecUShr); 892 }; 893 894 // 895 // Definitions of concrete miscellaneous vector operations in HIR. 896 // 897 898 // Assigns the given scalar elements to a vector, 899 // viz. set( array(x1, .. , xn) ) = [ x1, .. , xn ] if n == m, 900 // set( array(x1, .. , xm) ) = [ x1, .. , xm, 0, .. , 0 ] if m < n. 901 class HVecSetScalars final : public HVecOperation { 902 public: 903 HVecSetScalars(ArenaAllocator* allocator, 904 HInstruction* scalars[], 905 DataType::Type packed_type, 906 size_t vector_length, 907 size_t number_of_scalars, 908 uint32_t dex_pc) 909 : HVecOperation(kVecSetScalars, 910 allocator, 911 packed_type, 912 SideEffects::None(), 913 number_of_scalars, 914 vector_length, 915 dex_pc) { 916 for (size_t i = 0; i < number_of_scalars; i++) { 917 DCHECK(!ReturnsSIMDValue(scalars[i])); 918 SetRawInputAt(0, scalars[i]); 919 } 920 } 921 922 // Setting scalars needs to stay in place, since SIMD registers are not 923 // kept alive across vector loop boundaries (yet). 924 bool CanBeMoved() const override { return false; } 925 926 DECLARE_INSTRUCTION(VecSetScalars); 927 928 protected: 929 DEFAULT_COPY_CONSTRUCTOR(VecSetScalars); 930 }; 931 932 // Multiplies every component in the two vectors, adds the result vector to the accumulator vector, 933 // viz. [ a1, .. , an ] + [ x1, .. , xn ] * [ y1, .. , yn ] = [ a1 + x1 * y1, .. , an + xn * yn ]. 934 // For floating point types, Java rounding behavior must be preserved; the products are rounded to 935 // the proper precision before being added. "Fused" multiply-add operations available on several 936 // architectures are not usable since they would violate Java language rules. 937 class HVecMultiplyAccumulate final : public HVecOperation { 938 public: 939 HVecMultiplyAccumulate(ArenaAllocator* allocator, 940 InstructionKind op, 941 HInstruction* accumulator, 942 HInstruction* mul_left, 943 HInstruction* mul_right, 944 DataType::Type packed_type, 945 size_t vector_length, 946 uint32_t dex_pc) 947 : HVecOperation(kVecMultiplyAccumulate, 948 allocator, 949 packed_type, 950 SideEffects::None(), 951 /* number_of_inputs= */ 3, 952 vector_length, 953 dex_pc), 954 op_kind_(op) { 955 DCHECK(op == InstructionKind::kAdd || op == InstructionKind::kSub); 956 DCHECK(HasConsistentPackedTypes(accumulator, packed_type)); 957 DCHECK(HasConsistentPackedTypes(mul_left, packed_type)); 958 DCHECK(HasConsistentPackedTypes(mul_right, packed_type)); 959 // Remove the following if we add an architecture that supports floating point multiply-add 960 // with Java-compatible rounding. 961 DCHECK(DataType::IsIntegralType(packed_type)); 962 SetRawInputAt(0, accumulator); 963 SetRawInputAt(1, mul_left); 964 SetRawInputAt(2, mul_right); 965 } 966 967 bool CanBeMoved() const override { return true; } 968 969 bool InstructionDataEquals(const HInstruction* other) const override { 970 DCHECK(other->IsVecMultiplyAccumulate()); 971 const HVecMultiplyAccumulate* o = other->AsVecMultiplyAccumulate(); 972 return HVecOperation::InstructionDataEquals(o) && GetOpKind() == o->GetOpKind(); 973 } 974 975 InstructionKind GetOpKind() const { return op_kind_; } 976 977 DECLARE_INSTRUCTION(VecMultiplyAccumulate); 978 979 protected: 980 DEFAULT_COPY_CONSTRUCTOR(VecMultiplyAccumulate); 981 982 private: 983 // Indicates if this is a MADD or MSUB. 984 const InstructionKind op_kind_; 985 }; 986 987 // Takes the absolute difference of two vectors, and adds the results to 988 // same-precision or wider-precision components in the accumulator, 989 // viz. SAD([ a1, .. , am ], [ x1, .. , xn ], [ y1, .. , yn ]) = 990 // [ a1 + sum abs(xi-yi), .. , am + sum abs(xj-yj) ], 991 // for m <= n, non-overlapping sums, and signed operands x, y. 992 class HVecSADAccumulate final : public HVecOperation { 993 public: 994 HVecSADAccumulate(ArenaAllocator* allocator, 995 HInstruction* accumulator, 996 HInstruction* sad_left, 997 HInstruction* sad_right, 998 DataType::Type packed_type, 999 size_t vector_length, 1000 uint32_t dex_pc) 1001 : HVecOperation(kVecSADAccumulate, 1002 allocator, 1003 packed_type, 1004 SideEffects::None(), 1005 /* number_of_inputs= */ 3, 1006 vector_length, 1007 dex_pc) { 1008 DCHECK(HasConsistentPackedTypes(accumulator, packed_type)); 1009 DCHECK(sad_left->IsVecOperation()); 1010 DCHECK(sad_right->IsVecOperation()); 1011 DCHECK_EQ(ToSignedType(sad_left->AsVecOperation()->GetPackedType()), 1012 ToSignedType(sad_right->AsVecOperation()->GetPackedType())); 1013 SetRawInputAt(0, accumulator); 1014 SetRawInputAt(1, sad_left); 1015 SetRawInputAt(2, sad_right); 1016 } 1017 1018 DECLARE_INSTRUCTION(VecSADAccumulate); 1019 1020 protected: 1021 DEFAULT_COPY_CONSTRUCTOR(VecSADAccumulate); 1022 }; 1023 1024 // Performs dot product of two vectors and adds the result to wider precision components in 1025 // the accumulator. 1026 // 1027 // viz. DOT_PRODUCT([ a1, .. , am], [ x1, .. , xn ], [ y1, .. , yn ]) = 1028 // [ a1 + sum(xi * yi), .. , am + sum(xj * yj) ], 1029 // for m <= n, non-overlapping sums, 1030 // for either both signed or both unsigned operands x, y. 1031 // 1032 // Notes: 1033 // - packed type reflects the type of sum reduction, not the type of the operands. 1034 // - IsZeroExtending() is used to determine the kind of signed/zero extension to be 1035 // performed for the operands. 1036 // 1037 // TODO: Support types other than kInt32 for packed type. 1038 class HVecDotProd final : public HVecOperation { 1039 public: 1040 HVecDotProd(ArenaAllocator* allocator, 1041 HInstruction* accumulator, 1042 HInstruction* left, 1043 HInstruction* right, 1044 DataType::Type packed_type, 1045 bool is_zero_extending, 1046 size_t vector_length, 1047 uint32_t dex_pc) 1048 : HVecOperation(kVecDotProd, 1049 allocator, 1050 packed_type, 1051 SideEffects::None(), 1052 /* number_of_inputs= */ 3, 1053 vector_length, 1054 dex_pc) { 1055 DCHECK(HasConsistentPackedTypes(accumulator, packed_type)); 1056 DCHECK(DataType::IsIntegralType(packed_type)); 1057 DCHECK(left->IsVecOperation()); 1058 DCHECK(right->IsVecOperation()); 1059 DCHECK_EQ(ToSignedType(left->AsVecOperation()->GetPackedType()), 1060 ToSignedType(right->AsVecOperation()->GetPackedType())); 1061 SetRawInputAt(0, accumulator); 1062 SetRawInputAt(1, left); 1063 SetRawInputAt(2, right); 1064 SetPackedFlag<kFieldHDotProdIsZeroExtending>(is_zero_extending); 1065 } 1066 1067 bool IsZeroExtending() const { return GetPackedFlag<kFieldHDotProdIsZeroExtending>(); } 1068 1069 bool CanBeMoved() const override { return true; } 1070 1071 DECLARE_INSTRUCTION(VecDotProd); 1072 1073 protected: 1074 DEFAULT_COPY_CONSTRUCTOR(VecDotProd); 1075 1076 private: 1077 // Additional packed bits. 1078 static constexpr size_t kFieldHDotProdIsZeroExtending = 1079 HVecOperation::kNumberOfVectorOpPackedBits; 1080 static constexpr size_t kNumberOfHDotProdPackedBits = kFieldHDotProdIsZeroExtending + 1; 1081 static_assert(kNumberOfHDotProdPackedBits <= kMaxNumberOfPackedBits, "Too many packed fields."); 1082 }; 1083 1084 // Loads a vector from memory, viz. load(mem, 1) 1085 // yield the vector [ mem(1), .. , mem(n) ]. 1086 class HVecLoad final : public HVecMemoryOperation { 1087 public: 1088 HVecLoad(ArenaAllocator* allocator, 1089 HInstruction* base, 1090 HInstruction* index, 1091 DataType::Type packed_type, 1092 SideEffects side_effects, 1093 size_t vector_length, 1094 bool is_string_char_at, 1095 uint32_t dex_pc) 1096 : HVecMemoryOperation(kVecLoad, 1097 allocator, 1098 packed_type, 1099 side_effects, 1100 /* number_of_inputs= */ 2, 1101 vector_length, 1102 dex_pc) { 1103 SetRawInputAt(0, base); 1104 SetRawInputAt(1, index); 1105 SetPackedFlag<kFieldIsStringCharAt>(is_string_char_at); 1106 } 1107 1108 bool IsStringCharAt() const { return GetPackedFlag<kFieldIsStringCharAt>(); } 1109 1110 bool CanBeMoved() const override { return true; } 1111 1112 bool InstructionDataEquals(const HInstruction* other) const override { 1113 DCHECK(other->IsVecLoad()); 1114 const HVecLoad* o = other->AsVecLoad(); 1115 return HVecMemoryOperation::InstructionDataEquals(o) && IsStringCharAt() == o->IsStringCharAt(); 1116 } 1117 1118 DECLARE_INSTRUCTION(VecLoad); 1119 1120 protected: 1121 DEFAULT_COPY_CONSTRUCTOR(VecLoad); 1122 1123 private: 1124 // Additional packed bits. 1125 static constexpr size_t kFieldIsStringCharAt = HVecOperation::kNumberOfVectorOpPackedBits; 1126 static constexpr size_t kNumberOfVecLoadPackedBits = kFieldIsStringCharAt + 1; 1127 static_assert(kNumberOfVecLoadPackedBits <= kMaxNumberOfPackedBits, "Too many packed fields."); 1128 }; 1129 1130 // Stores a vector to memory, viz. store(m, 1, [x1, .. , xn] ) 1131 // sets mem(1) = x1, .. , mem(n) = xn. 1132 class HVecStore final : public HVecMemoryOperation { 1133 public: 1134 HVecStore(ArenaAllocator* allocator, 1135 HInstruction* base, 1136 HInstruction* index, 1137 HInstruction* value, 1138 DataType::Type packed_type, 1139 SideEffects side_effects, 1140 size_t vector_length, 1141 uint32_t dex_pc) 1142 : HVecMemoryOperation(kVecStore, 1143 allocator, 1144 packed_type, 1145 side_effects, 1146 /* number_of_inputs= */ 3, 1147 vector_length, 1148 dex_pc) { 1149 DCHECK(HasConsistentPackedTypes(value, packed_type)); 1150 SetRawInputAt(0, base); 1151 SetRawInputAt(1, index); 1152 SetRawInputAt(2, value); 1153 } 1154 1155 // A store needs to stay in place. 1156 bool CanBeMoved() const override { return false; } 1157 1158 DECLARE_INSTRUCTION(VecStore); 1159 1160 protected: 1161 DEFAULT_COPY_CONSTRUCTOR(VecStore) 1162 }; 1163 1164 } // namespace art 1165 1166 #endif // ART_COMPILER_OPTIMIZING_NODES_VECTOR_H_ 1167