nodes.h revision cc42be074ed15235426cdbcb34f357ead2be2caf
1/* 2 * Copyright (C) 2014 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_H_ 18#define ART_COMPILER_OPTIMIZING_NODES_H_ 19 20#include <algorithm> 21#include <array> 22#include <type_traits> 23 24#include "base/arena_bit_vector.h" 25#include "base/arena_containers.h" 26#include "base/arena_object.h" 27#include "base/array_ref.h" 28#include "base/stl_util.h" 29#include "base/transform_array_ref.h" 30#include "dex_file.h" 31#include "entrypoints/quick/quick_entrypoints_enum.h" 32#include "handle.h" 33#include "handle_scope.h" 34#include "invoke_type.h" 35#include "intrinsics_enum.h" 36#include "locations.h" 37#include "method_reference.h" 38#include "mirror/class.h" 39#include "offsets.h" 40#include "primitive.h" 41#include "utils/intrusive_forward_list.h" 42 43namespace art { 44 45class GraphChecker; 46class HBasicBlock; 47class HCurrentMethod; 48class HDoubleConstant; 49class HEnvironment; 50class HFloatConstant; 51class HGraphBuilder; 52class HGraphVisitor; 53class HInstruction; 54class HIntConstant; 55class HInvoke; 56class HLongConstant; 57class HNullConstant; 58class HPhi; 59class HSuspendCheck; 60class HTryBoundary; 61class LiveInterval; 62class LocationSummary; 63class SlowPathCode; 64class SsaBuilder; 65 66namespace mirror { 67class DexCache; 68} // namespace mirror 69 70static const int kDefaultNumberOfBlocks = 8; 71static const int kDefaultNumberOfSuccessors = 2; 72static const int kDefaultNumberOfPredecessors = 2; 73static const int kDefaultNumberOfExceptionalPredecessors = 0; 74static const int kDefaultNumberOfDominatedBlocks = 1; 75static const int kDefaultNumberOfBackEdges = 1; 76 77// The maximum (meaningful) distance (31) that can be used in an integer shift/rotate operation. 78static constexpr int32_t kMaxIntShiftDistance = 0x1f; 79// The maximum (meaningful) distance (63) that can be used in a long shift/rotate operation. 80static constexpr int32_t kMaxLongShiftDistance = 0x3f; 81 82static constexpr uint32_t kUnknownFieldIndex = static_cast<uint32_t>(-1); 83static constexpr uint16_t kUnknownClassDefIndex = static_cast<uint16_t>(-1); 84 85static constexpr InvokeType kInvalidInvokeType = static_cast<InvokeType>(-1); 86 87static constexpr uint32_t kNoDexPc = -1; 88 89inline bool IsSameDexFile(const DexFile& lhs, const DexFile& rhs) { 90 // For the purposes of the compiler, the dex files must actually be the same object 91 // if we want to safely treat them as the same. This is especially important for JIT 92 // as custom class loaders can open the same underlying file (or memory) multiple 93 // times and provide different class resolution but no two class loaders should ever 94 // use the same DexFile object - doing so is an unsupported hack that can lead to 95 // all sorts of weird failures. 96 return &lhs == &rhs; 97} 98 99enum IfCondition { 100 // All types. 101 kCondEQ, // == 102 kCondNE, // != 103 // Signed integers and floating-point numbers. 104 kCondLT, // < 105 kCondLE, // <= 106 kCondGT, // > 107 kCondGE, // >= 108 // Unsigned integers. 109 kCondB, // < 110 kCondBE, // <= 111 kCondA, // > 112 kCondAE, // >= 113 // First and last aliases. 114 kCondFirst = kCondEQ, 115 kCondLast = kCondAE, 116}; 117 118enum GraphAnalysisResult { 119 kAnalysisSkipped, 120 kAnalysisInvalidBytecode, 121 kAnalysisFailThrowCatchLoop, 122 kAnalysisFailAmbiguousArrayOp, 123 kAnalysisSuccess, 124}; 125 126class HInstructionList : public ValueObject { 127 public: 128 HInstructionList() : first_instruction_(nullptr), last_instruction_(nullptr) {} 129 130 void AddInstruction(HInstruction* instruction); 131 void RemoveInstruction(HInstruction* instruction); 132 133 // Insert `instruction` before/after an existing instruction `cursor`. 134 void InsertInstructionBefore(HInstruction* instruction, HInstruction* cursor); 135 void InsertInstructionAfter(HInstruction* instruction, HInstruction* cursor); 136 137 // Return true if this list contains `instruction`. 138 bool Contains(HInstruction* instruction) const; 139 140 // Return true if `instruction1` is found before `instruction2` in 141 // this instruction list and false otherwise. Abort if none 142 // of these instructions is found. 143 bool FoundBefore(const HInstruction* instruction1, 144 const HInstruction* instruction2) const; 145 146 bool IsEmpty() const { return first_instruction_ == nullptr; } 147 void Clear() { first_instruction_ = last_instruction_ = nullptr; } 148 149 // Update the block of all instructions to be `block`. 150 void SetBlockOfInstructions(HBasicBlock* block) const; 151 152 void AddAfter(HInstruction* cursor, const HInstructionList& instruction_list); 153 void AddBefore(HInstruction* cursor, const HInstructionList& instruction_list); 154 void Add(const HInstructionList& instruction_list); 155 156 // Return the number of instructions in the list. This is an expensive operation. 157 size_t CountSize() const; 158 159 private: 160 HInstruction* first_instruction_; 161 HInstruction* last_instruction_; 162 163 friend class HBasicBlock; 164 friend class HGraph; 165 friend class HInstruction; 166 friend class HInstructionIterator; 167 friend class HBackwardInstructionIterator; 168 169 DISALLOW_COPY_AND_ASSIGN(HInstructionList); 170}; 171 172class ReferenceTypeInfo : ValueObject { 173 public: 174 typedef Handle<mirror::Class> TypeHandle; 175 176 static ReferenceTypeInfo Create(TypeHandle type_handle, bool is_exact); 177 178 static ReferenceTypeInfo Create(TypeHandle type_handle) REQUIRES_SHARED(Locks::mutator_lock_) { 179 return Create(type_handle, type_handle->CannotBeAssignedFromOtherTypes()); 180 } 181 182 static ReferenceTypeInfo CreateUnchecked(TypeHandle type_handle, bool is_exact) { 183 return ReferenceTypeInfo(type_handle, is_exact); 184 } 185 186 static ReferenceTypeInfo CreateInvalid() { return ReferenceTypeInfo(); } 187 188 static bool IsValidHandle(TypeHandle handle) { 189 return handle.GetReference() != nullptr; 190 } 191 192 bool IsValid() const { 193 return IsValidHandle(type_handle_); 194 } 195 196 bool IsExact() const { return is_exact_; } 197 198 bool IsObjectClass() const REQUIRES_SHARED(Locks::mutator_lock_) { 199 DCHECK(IsValid()); 200 return GetTypeHandle()->IsObjectClass(); 201 } 202 203 bool IsStringClass() const REQUIRES_SHARED(Locks::mutator_lock_) { 204 DCHECK(IsValid()); 205 return GetTypeHandle()->IsStringClass(); 206 } 207 208 bool IsObjectArray() const REQUIRES_SHARED(Locks::mutator_lock_) { 209 DCHECK(IsValid()); 210 return IsArrayClass() && GetTypeHandle()->GetComponentType()->IsObjectClass(); 211 } 212 213 bool IsInterface() const REQUIRES_SHARED(Locks::mutator_lock_) { 214 DCHECK(IsValid()); 215 return GetTypeHandle()->IsInterface(); 216 } 217 218 bool IsArrayClass() const REQUIRES_SHARED(Locks::mutator_lock_) { 219 DCHECK(IsValid()); 220 return GetTypeHandle()->IsArrayClass(); 221 } 222 223 bool IsPrimitiveArrayClass() const REQUIRES_SHARED(Locks::mutator_lock_) { 224 DCHECK(IsValid()); 225 return GetTypeHandle()->IsPrimitiveArray(); 226 } 227 228 bool IsNonPrimitiveArrayClass() const REQUIRES_SHARED(Locks::mutator_lock_) { 229 DCHECK(IsValid()); 230 return GetTypeHandle()->IsArrayClass() && !GetTypeHandle()->IsPrimitiveArray(); 231 } 232 233 bool CanArrayHold(ReferenceTypeInfo rti) const REQUIRES_SHARED(Locks::mutator_lock_) { 234 DCHECK(IsValid()); 235 if (!IsExact()) return false; 236 if (!IsArrayClass()) return false; 237 return GetTypeHandle()->GetComponentType()->IsAssignableFrom(rti.GetTypeHandle().Get()); 238 } 239 240 bool CanArrayHoldValuesOf(ReferenceTypeInfo rti) const REQUIRES_SHARED(Locks::mutator_lock_) { 241 DCHECK(IsValid()); 242 if (!IsExact()) return false; 243 if (!IsArrayClass()) return false; 244 if (!rti.IsArrayClass()) return false; 245 return GetTypeHandle()->GetComponentType()->IsAssignableFrom( 246 rti.GetTypeHandle()->GetComponentType()); 247 } 248 249 Handle<mirror::Class> GetTypeHandle() const { return type_handle_; } 250 251 bool IsSupertypeOf(ReferenceTypeInfo rti) const REQUIRES_SHARED(Locks::mutator_lock_) { 252 DCHECK(IsValid()); 253 DCHECK(rti.IsValid()); 254 return GetTypeHandle()->IsAssignableFrom(rti.GetTypeHandle().Get()); 255 } 256 257 bool IsStrictSupertypeOf(ReferenceTypeInfo rti) const REQUIRES_SHARED(Locks::mutator_lock_) { 258 DCHECK(IsValid()); 259 DCHECK(rti.IsValid()); 260 return GetTypeHandle().Get() != rti.GetTypeHandle().Get() && 261 GetTypeHandle()->IsAssignableFrom(rti.GetTypeHandle().Get()); 262 } 263 264 // Returns true if the type information provide the same amount of details. 265 // Note that it does not mean that the instructions have the same actual type 266 // (because the type can be the result of a merge). 267 bool IsEqual(ReferenceTypeInfo rti) const REQUIRES_SHARED(Locks::mutator_lock_) { 268 if (!IsValid() && !rti.IsValid()) { 269 // Invalid types are equal. 270 return true; 271 } 272 if (!IsValid() || !rti.IsValid()) { 273 // One is valid, the other not. 274 return false; 275 } 276 return IsExact() == rti.IsExact() 277 && GetTypeHandle().Get() == rti.GetTypeHandle().Get(); 278 } 279 280 private: 281 ReferenceTypeInfo() : type_handle_(TypeHandle()), is_exact_(false) {} 282 ReferenceTypeInfo(TypeHandle type_handle, bool is_exact) 283 : type_handle_(type_handle), is_exact_(is_exact) { } 284 285 // The class of the object. 286 TypeHandle type_handle_; 287 // Whether or not the type is exact or a superclass of the actual type. 288 // Whether or not we have any information about this type. 289 bool is_exact_; 290}; 291 292std::ostream& operator<<(std::ostream& os, const ReferenceTypeInfo& rhs); 293 294// Control-flow graph of a method. Contains a list of basic blocks. 295class HGraph : public ArenaObject<kArenaAllocGraph> { 296 public: 297 HGraph(ArenaAllocator* arena, 298 const DexFile& dex_file, 299 uint32_t method_idx, 300 bool should_generate_constructor_barrier, 301 InstructionSet instruction_set, 302 InvokeType invoke_type = kInvalidInvokeType, 303 bool debuggable = false, 304 bool osr = false, 305 int start_instruction_id = 0) 306 : arena_(arena), 307 blocks_(arena->Adapter(kArenaAllocBlockList)), 308 reverse_post_order_(arena->Adapter(kArenaAllocReversePostOrder)), 309 linear_order_(arena->Adapter(kArenaAllocLinearOrder)), 310 entry_block_(nullptr), 311 exit_block_(nullptr), 312 maximum_number_of_out_vregs_(0), 313 number_of_vregs_(0), 314 number_of_in_vregs_(0), 315 temporaries_vreg_slots_(0), 316 has_bounds_checks_(false), 317 has_try_catch_(false), 318 has_irreducible_loops_(false), 319 debuggable_(debuggable), 320 current_instruction_id_(start_instruction_id), 321 dex_file_(dex_file), 322 method_idx_(method_idx), 323 invoke_type_(invoke_type), 324 in_ssa_form_(false), 325 should_generate_constructor_barrier_(should_generate_constructor_barrier), 326 instruction_set_(instruction_set), 327 cached_null_constant_(nullptr), 328 cached_int_constants_(std::less<int32_t>(), arena->Adapter(kArenaAllocConstantsMap)), 329 cached_float_constants_(std::less<int32_t>(), arena->Adapter(kArenaAllocConstantsMap)), 330 cached_long_constants_(std::less<int64_t>(), arena->Adapter(kArenaAllocConstantsMap)), 331 cached_double_constants_(std::less<int64_t>(), arena->Adapter(kArenaAllocConstantsMap)), 332 cached_current_method_(nullptr), 333 inexact_object_rti_(ReferenceTypeInfo::CreateInvalid()), 334 osr_(osr) { 335 blocks_.reserve(kDefaultNumberOfBlocks); 336 } 337 338 // Acquires and stores RTI of inexact Object to be used when creating HNullConstant. 339 void InitializeInexactObjectRTI(VariableSizedHandleScope* handles); 340 341 ArenaAllocator* GetArena() const { return arena_; } 342 const ArenaVector<HBasicBlock*>& GetBlocks() const { return blocks_; } 343 344 bool IsInSsaForm() const { return in_ssa_form_; } 345 void SetInSsaForm() { in_ssa_form_ = true; } 346 347 HBasicBlock* GetEntryBlock() const { return entry_block_; } 348 HBasicBlock* GetExitBlock() const { return exit_block_; } 349 bool HasExitBlock() const { return exit_block_ != nullptr; } 350 351 void SetEntryBlock(HBasicBlock* block) { entry_block_ = block; } 352 void SetExitBlock(HBasicBlock* block) { exit_block_ = block; } 353 354 void AddBlock(HBasicBlock* block); 355 356 void ComputeDominanceInformation(); 357 void ClearDominanceInformation(); 358 void ClearLoopInformation(); 359 void FindBackEdges(ArenaBitVector* visited); 360 GraphAnalysisResult BuildDominatorTree(); 361 void SimplifyCFG(); 362 void SimplifyCatchBlocks(); 363 364 // Analyze all natural loops in this graph. Returns a code specifying that it 365 // was successful or the reason for failure. The method will fail if a loop 366 // is a throw-catch loop, i.e. the header is a catch block. 367 GraphAnalysisResult AnalyzeLoops() const; 368 369 // Iterate over blocks to compute try block membership. Needs reverse post 370 // order and loop information. 371 void ComputeTryBlockInformation(); 372 373 // Inline this graph in `outer_graph`, replacing the given `invoke` instruction. 374 // Returns the instruction to replace the invoke expression or null if the 375 // invoke is for a void method. Note that the caller is responsible for replacing 376 // and removing the invoke instruction. 377 HInstruction* InlineInto(HGraph* outer_graph, HInvoke* invoke); 378 379 // Update the loop and try membership of `block`, which was spawned from `reference`. 380 // In case `reference` is a back edge, `replace_if_back_edge` notifies whether `block` 381 // should be the new back edge. 382 void UpdateLoopAndTryInformationOfNewBlock(HBasicBlock* block, 383 HBasicBlock* reference, 384 bool replace_if_back_edge); 385 386 // Need to add a couple of blocks to test if the loop body is entered and 387 // put deoptimization instructions, etc. 388 void TransformLoopHeaderForBCE(HBasicBlock* header); 389 390 // Removes `block` from the graph. Assumes `block` has been disconnected from 391 // other blocks and has no instructions or phis. 392 void DeleteDeadEmptyBlock(HBasicBlock* block); 393 394 // Splits the edge between `block` and `successor` while preserving the 395 // indices in the predecessor/successor lists. If there are multiple edges 396 // between the blocks, the lowest indices are used. 397 // Returns the new block which is empty and has the same dex pc as `successor`. 398 HBasicBlock* SplitEdge(HBasicBlock* block, HBasicBlock* successor); 399 400 void SplitCriticalEdge(HBasicBlock* block, HBasicBlock* successor); 401 void SimplifyLoop(HBasicBlock* header); 402 403 int32_t GetNextInstructionId() { 404 DCHECK_NE(current_instruction_id_, INT32_MAX); 405 return current_instruction_id_++; 406 } 407 408 int32_t GetCurrentInstructionId() const { 409 return current_instruction_id_; 410 } 411 412 void SetCurrentInstructionId(int32_t id) { 413 DCHECK_GE(id, current_instruction_id_); 414 current_instruction_id_ = id; 415 } 416 417 uint16_t GetMaximumNumberOfOutVRegs() const { 418 return maximum_number_of_out_vregs_; 419 } 420 421 void SetMaximumNumberOfOutVRegs(uint16_t new_value) { 422 maximum_number_of_out_vregs_ = new_value; 423 } 424 425 void UpdateMaximumNumberOfOutVRegs(uint16_t other_value) { 426 maximum_number_of_out_vregs_ = std::max(maximum_number_of_out_vregs_, other_value); 427 } 428 429 void UpdateTemporariesVRegSlots(size_t slots) { 430 temporaries_vreg_slots_ = std::max(slots, temporaries_vreg_slots_); 431 } 432 433 size_t GetTemporariesVRegSlots() const { 434 DCHECK(!in_ssa_form_); 435 return temporaries_vreg_slots_; 436 } 437 438 void SetNumberOfVRegs(uint16_t number_of_vregs) { 439 number_of_vregs_ = number_of_vregs; 440 } 441 442 uint16_t GetNumberOfVRegs() const { 443 return number_of_vregs_; 444 } 445 446 void SetNumberOfInVRegs(uint16_t value) { 447 number_of_in_vregs_ = value; 448 } 449 450 uint16_t GetNumberOfInVRegs() const { 451 return number_of_in_vregs_; 452 } 453 454 uint16_t GetNumberOfLocalVRegs() const { 455 DCHECK(!in_ssa_form_); 456 return number_of_vregs_ - number_of_in_vregs_; 457 } 458 459 const ArenaVector<HBasicBlock*>& GetReversePostOrder() const { 460 return reverse_post_order_; 461 } 462 463 const ArenaVector<HBasicBlock*>& GetLinearOrder() const { 464 return linear_order_; 465 } 466 467 bool HasBoundsChecks() const { 468 return has_bounds_checks_; 469 } 470 471 void SetHasBoundsChecks(bool value) { 472 has_bounds_checks_ = value; 473 } 474 475 bool ShouldGenerateConstructorBarrier() const { 476 return should_generate_constructor_barrier_; 477 } 478 479 bool IsDebuggable() const { return debuggable_; } 480 481 // Returns a constant of the given type and value. If it does not exist 482 // already, it is created and inserted into the graph. This method is only for 483 // integral types. 484 HConstant* GetConstant(Primitive::Type type, int64_t value, uint32_t dex_pc = kNoDexPc); 485 486 // TODO: This is problematic for the consistency of reference type propagation 487 // because it can be created anytime after the pass and thus it will be left 488 // with an invalid type. 489 HNullConstant* GetNullConstant(uint32_t dex_pc = kNoDexPc); 490 491 HIntConstant* GetIntConstant(int32_t value, uint32_t dex_pc = kNoDexPc) { 492 return CreateConstant(value, &cached_int_constants_, dex_pc); 493 } 494 HLongConstant* GetLongConstant(int64_t value, uint32_t dex_pc = kNoDexPc) { 495 return CreateConstant(value, &cached_long_constants_, dex_pc); 496 } 497 HFloatConstant* GetFloatConstant(float value, uint32_t dex_pc = kNoDexPc) { 498 return CreateConstant(bit_cast<int32_t, float>(value), &cached_float_constants_, dex_pc); 499 } 500 HDoubleConstant* GetDoubleConstant(double value, uint32_t dex_pc = kNoDexPc) { 501 return CreateConstant(bit_cast<int64_t, double>(value), &cached_double_constants_, dex_pc); 502 } 503 504 HCurrentMethod* GetCurrentMethod(); 505 506 const DexFile& GetDexFile() const { 507 return dex_file_; 508 } 509 510 uint32_t GetMethodIdx() const { 511 return method_idx_; 512 } 513 514 InvokeType GetInvokeType() const { 515 return invoke_type_; 516 } 517 518 InstructionSet GetInstructionSet() const { 519 return instruction_set_; 520 } 521 522 bool IsCompilingOsr() const { return osr_; } 523 524 bool HasTryCatch() const { return has_try_catch_; } 525 void SetHasTryCatch(bool value) { has_try_catch_ = value; } 526 527 bool HasIrreducibleLoops() const { return has_irreducible_loops_; } 528 void SetHasIrreducibleLoops(bool value) { has_irreducible_loops_ = value; } 529 530 ArtMethod* GetArtMethod() const { return art_method_; } 531 void SetArtMethod(ArtMethod* method) { art_method_ = method; } 532 533 // Returns an instruction with the opposite boolean value from 'cond'. 534 // The instruction has been inserted into the graph, either as a constant, or 535 // before cursor. 536 HInstruction* InsertOppositeCondition(HInstruction* cond, HInstruction* cursor); 537 538 ReferenceTypeInfo GetInexactObjectRti() const { return inexact_object_rti_; } 539 540 private: 541 void RemoveInstructionsAsUsersFromDeadBlocks(const ArenaBitVector& visited) const; 542 void RemoveDeadBlocks(const ArenaBitVector& visited); 543 544 template <class InstructionType, typename ValueType> 545 InstructionType* CreateConstant(ValueType value, 546 ArenaSafeMap<ValueType, InstructionType*>* cache, 547 uint32_t dex_pc = kNoDexPc) { 548 // Try to find an existing constant of the given value. 549 InstructionType* constant = nullptr; 550 auto cached_constant = cache->find(value); 551 if (cached_constant != cache->end()) { 552 constant = cached_constant->second; 553 } 554 555 // If not found or previously deleted, create and cache a new instruction. 556 // Don't bother reviving a previously deleted instruction, for simplicity. 557 if (constant == nullptr || constant->GetBlock() == nullptr) { 558 constant = new (arena_) InstructionType(value, dex_pc); 559 cache->Overwrite(value, constant); 560 InsertConstant(constant); 561 } 562 return constant; 563 } 564 565 void InsertConstant(HConstant* instruction); 566 567 // Cache a float constant into the graph. This method should only be 568 // called by the SsaBuilder when creating "equivalent" instructions. 569 void CacheFloatConstant(HFloatConstant* constant); 570 571 // See CacheFloatConstant comment. 572 void CacheDoubleConstant(HDoubleConstant* constant); 573 574 ArenaAllocator* const arena_; 575 576 // List of blocks in insertion order. 577 ArenaVector<HBasicBlock*> blocks_; 578 579 // List of blocks to perform a reverse post order tree traversal. 580 ArenaVector<HBasicBlock*> reverse_post_order_; 581 582 // List of blocks to perform a linear order tree traversal. Unlike the reverse 583 // post order, this order is not incrementally kept up-to-date. 584 ArenaVector<HBasicBlock*> linear_order_; 585 586 HBasicBlock* entry_block_; 587 HBasicBlock* exit_block_; 588 589 // The maximum number of virtual registers arguments passed to a HInvoke in this graph. 590 uint16_t maximum_number_of_out_vregs_; 591 592 // The number of virtual registers in this method. Contains the parameters. 593 uint16_t number_of_vregs_; 594 595 // The number of virtual registers used by parameters of this method. 596 uint16_t number_of_in_vregs_; 597 598 // Number of vreg size slots that the temporaries use (used in baseline compiler). 599 size_t temporaries_vreg_slots_; 600 601 // Has bounds checks. We can totally skip BCE if it's false. 602 bool has_bounds_checks_; 603 604 // Flag whether there are any try/catch blocks in the graph. We will skip 605 // try/catch-related passes if false. 606 bool has_try_catch_; 607 608 // Flag whether there are any irreducible loops in the graph. 609 bool has_irreducible_loops_; 610 611 // Indicates whether the graph should be compiled in a way that 612 // ensures full debuggability. If false, we can apply more 613 // aggressive optimizations that may limit the level of debugging. 614 const bool debuggable_; 615 616 // The current id to assign to a newly added instruction. See HInstruction.id_. 617 int32_t current_instruction_id_; 618 619 // The dex file from which the method is from. 620 const DexFile& dex_file_; 621 622 // The method index in the dex file. 623 const uint32_t method_idx_; 624 625 // If inlined, this encodes how the callee is being invoked. 626 const InvokeType invoke_type_; 627 628 // Whether the graph has been transformed to SSA form. Only used 629 // in debug mode to ensure we are not using properties only valid 630 // for non-SSA form (like the number of temporaries). 631 bool in_ssa_form_; 632 633 const bool should_generate_constructor_barrier_; 634 635 const InstructionSet instruction_set_; 636 637 // Cached constants. 638 HNullConstant* cached_null_constant_; 639 ArenaSafeMap<int32_t, HIntConstant*> cached_int_constants_; 640 ArenaSafeMap<int32_t, HFloatConstant*> cached_float_constants_; 641 ArenaSafeMap<int64_t, HLongConstant*> cached_long_constants_; 642 ArenaSafeMap<int64_t, HDoubleConstant*> cached_double_constants_; 643 644 HCurrentMethod* cached_current_method_; 645 646 // The ArtMethod this graph is for. Note that for AOT, it may be null, 647 // for example for methods whose declaring class could not be resolved 648 // (such as when the superclass could not be found). 649 ArtMethod* art_method_; 650 651 // Keep the RTI of inexact Object to avoid having to pass stack handle 652 // collection pointer to passes which may create NullConstant. 653 ReferenceTypeInfo inexact_object_rti_; 654 655 // Whether we are compiling this graph for on stack replacement: this will 656 // make all loops seen as irreducible and emit special stack maps to mark 657 // compiled code entries which the interpreter can directly jump to. 658 const bool osr_; 659 660 friend class SsaBuilder; // For caching constants. 661 friend class SsaLivenessAnalysis; // For the linear order. 662 friend class HInliner; // For the reverse post order. 663 ART_FRIEND_TEST(GraphTest, IfSuccessorSimpleJoinBlock1); 664 DISALLOW_COPY_AND_ASSIGN(HGraph); 665}; 666 667class HLoopInformation : public ArenaObject<kArenaAllocLoopInfo> { 668 public: 669 HLoopInformation(HBasicBlock* header, HGraph* graph) 670 : header_(header), 671 suspend_check_(nullptr), 672 irreducible_(false), 673 contains_irreducible_loop_(false), 674 back_edges_(graph->GetArena()->Adapter(kArenaAllocLoopInfoBackEdges)), 675 // Make bit vector growable, as the number of blocks may change. 676 blocks_(graph->GetArena(), graph->GetBlocks().size(), true, kArenaAllocLoopInfoBackEdges) { 677 back_edges_.reserve(kDefaultNumberOfBackEdges); 678 } 679 680 bool IsIrreducible() const { return irreducible_; } 681 bool ContainsIrreducibleLoop() const { return contains_irreducible_loop_; } 682 683 void Dump(std::ostream& os); 684 685 HBasicBlock* GetHeader() const { 686 return header_; 687 } 688 689 void SetHeader(HBasicBlock* block) { 690 header_ = block; 691 } 692 693 HSuspendCheck* GetSuspendCheck() const { return suspend_check_; } 694 void SetSuspendCheck(HSuspendCheck* check) { suspend_check_ = check; } 695 bool HasSuspendCheck() const { return suspend_check_ != nullptr; } 696 697 void AddBackEdge(HBasicBlock* back_edge) { 698 back_edges_.push_back(back_edge); 699 } 700 701 void RemoveBackEdge(HBasicBlock* back_edge) { 702 RemoveElement(back_edges_, back_edge); 703 } 704 705 bool IsBackEdge(const HBasicBlock& block) const { 706 return ContainsElement(back_edges_, &block); 707 } 708 709 size_t NumberOfBackEdges() const { 710 return back_edges_.size(); 711 } 712 713 HBasicBlock* GetPreHeader() const; 714 715 const ArenaVector<HBasicBlock*>& GetBackEdges() const { 716 return back_edges_; 717 } 718 719 // Returns the lifetime position of the back edge that has the 720 // greatest lifetime position. 721 size_t GetLifetimeEnd() const; 722 723 void ReplaceBackEdge(HBasicBlock* existing, HBasicBlock* new_back_edge) { 724 ReplaceElement(back_edges_, existing, new_back_edge); 725 } 726 727 // Finds blocks that are part of this loop. 728 void Populate(); 729 730 // Returns whether this loop information contains `block`. 731 // Note that this loop information *must* be populated before entering this function. 732 bool Contains(const HBasicBlock& block) const; 733 734 // Returns whether this loop information is an inner loop of `other`. 735 // Note that `other` *must* be populated before entering this function. 736 bool IsIn(const HLoopInformation& other) const; 737 738 // Returns true if instruction is not defined within this loop. 739 bool IsDefinedOutOfTheLoop(HInstruction* instruction) const; 740 741 const ArenaBitVector& GetBlocks() const { return blocks_; } 742 743 void Add(HBasicBlock* block); 744 void Remove(HBasicBlock* block); 745 746 void ClearAllBlocks() { 747 blocks_.ClearAllBits(); 748 } 749 750 bool HasBackEdgeNotDominatedByHeader() const; 751 752 bool IsPopulated() const { 753 return blocks_.GetHighestBitSet() != -1; 754 } 755 756 bool DominatesAllBackEdges(HBasicBlock* block); 757 758 private: 759 // Internal recursive implementation of `Populate`. 760 void PopulateRecursive(HBasicBlock* block); 761 void PopulateIrreducibleRecursive(HBasicBlock* block, ArenaBitVector* finalized); 762 763 HBasicBlock* header_; 764 HSuspendCheck* suspend_check_; 765 bool irreducible_; 766 bool contains_irreducible_loop_; 767 ArenaVector<HBasicBlock*> back_edges_; 768 ArenaBitVector blocks_; 769 770 DISALLOW_COPY_AND_ASSIGN(HLoopInformation); 771}; 772 773// Stores try/catch information for basic blocks. 774// Note that HGraph is constructed so that catch blocks cannot simultaneously 775// be try blocks. 776class TryCatchInformation : public ArenaObject<kArenaAllocTryCatchInfo> { 777 public: 778 // Try block information constructor. 779 explicit TryCatchInformation(const HTryBoundary& try_entry) 780 : try_entry_(&try_entry), 781 catch_dex_file_(nullptr), 782 catch_type_index_(DexFile::kDexNoIndex16) { 783 DCHECK(try_entry_ != nullptr); 784 } 785 786 // Catch block information constructor. 787 TryCatchInformation(uint16_t catch_type_index, const DexFile& dex_file) 788 : try_entry_(nullptr), 789 catch_dex_file_(&dex_file), 790 catch_type_index_(catch_type_index) {} 791 792 bool IsTryBlock() const { return try_entry_ != nullptr; } 793 794 const HTryBoundary& GetTryEntry() const { 795 DCHECK(IsTryBlock()); 796 return *try_entry_; 797 } 798 799 bool IsCatchBlock() const { return catch_dex_file_ != nullptr; } 800 801 bool IsCatchAllTypeIndex() const { 802 DCHECK(IsCatchBlock()); 803 return catch_type_index_ == DexFile::kDexNoIndex16; 804 } 805 806 uint16_t GetCatchTypeIndex() const { 807 DCHECK(IsCatchBlock()); 808 return catch_type_index_; 809 } 810 811 const DexFile& GetCatchDexFile() const { 812 DCHECK(IsCatchBlock()); 813 return *catch_dex_file_; 814 } 815 816 private: 817 // One of possibly several TryBoundary instructions entering the block's try. 818 // Only set for try blocks. 819 const HTryBoundary* try_entry_; 820 821 // Exception type information. Only set for catch blocks. 822 const DexFile* catch_dex_file_; 823 const uint16_t catch_type_index_; 824}; 825 826static constexpr size_t kNoLifetime = -1; 827static constexpr uint32_t kInvalidBlockId = static_cast<uint32_t>(-1); 828 829// A block in a method. Contains the list of instructions represented 830// as a double linked list. Each block knows its predecessors and 831// successors. 832 833class HBasicBlock : public ArenaObject<kArenaAllocBasicBlock> { 834 public: 835 explicit HBasicBlock(HGraph* graph, uint32_t dex_pc = kNoDexPc) 836 : graph_(graph), 837 predecessors_(graph->GetArena()->Adapter(kArenaAllocPredecessors)), 838 successors_(graph->GetArena()->Adapter(kArenaAllocSuccessors)), 839 loop_information_(nullptr), 840 dominator_(nullptr), 841 dominated_blocks_(graph->GetArena()->Adapter(kArenaAllocDominated)), 842 block_id_(kInvalidBlockId), 843 dex_pc_(dex_pc), 844 lifetime_start_(kNoLifetime), 845 lifetime_end_(kNoLifetime), 846 try_catch_information_(nullptr) { 847 predecessors_.reserve(kDefaultNumberOfPredecessors); 848 successors_.reserve(kDefaultNumberOfSuccessors); 849 dominated_blocks_.reserve(kDefaultNumberOfDominatedBlocks); 850 } 851 852 const ArenaVector<HBasicBlock*>& GetPredecessors() const { 853 return predecessors_; 854 } 855 856 const ArenaVector<HBasicBlock*>& GetSuccessors() const { 857 return successors_; 858 } 859 860 ArrayRef<HBasicBlock* const> GetNormalSuccessors() const; 861 ArrayRef<HBasicBlock* const> GetExceptionalSuccessors() const; 862 863 bool HasSuccessor(const HBasicBlock* block, size_t start_from = 0u) { 864 return ContainsElement(successors_, block, start_from); 865 } 866 867 const ArenaVector<HBasicBlock*>& GetDominatedBlocks() const { 868 return dominated_blocks_; 869 } 870 871 bool IsEntryBlock() const { 872 return graph_->GetEntryBlock() == this; 873 } 874 875 bool IsExitBlock() const { 876 return graph_->GetExitBlock() == this; 877 } 878 879 bool IsSingleGoto() const; 880 bool IsSingleTryBoundary() const; 881 882 // Returns true if this block emits nothing but a jump. 883 bool IsSingleJump() const { 884 HLoopInformation* loop_info = GetLoopInformation(); 885 return (IsSingleGoto() || IsSingleTryBoundary()) 886 // Back edges generate a suspend check. 887 && (loop_info == nullptr || !loop_info->IsBackEdge(*this)); 888 } 889 890 void AddBackEdge(HBasicBlock* back_edge) { 891 if (loop_information_ == nullptr) { 892 loop_information_ = new (graph_->GetArena()) HLoopInformation(this, graph_); 893 } 894 DCHECK_EQ(loop_information_->GetHeader(), this); 895 loop_information_->AddBackEdge(back_edge); 896 } 897 898 HGraph* GetGraph() const { return graph_; } 899 void SetGraph(HGraph* graph) { graph_ = graph; } 900 901 uint32_t GetBlockId() const { return block_id_; } 902 void SetBlockId(int id) { block_id_ = id; } 903 uint32_t GetDexPc() const { return dex_pc_; } 904 905 HBasicBlock* GetDominator() const { return dominator_; } 906 void SetDominator(HBasicBlock* dominator) { dominator_ = dominator; } 907 void AddDominatedBlock(HBasicBlock* block) { dominated_blocks_.push_back(block); } 908 909 void RemoveDominatedBlock(HBasicBlock* block) { 910 RemoveElement(dominated_blocks_, block); 911 } 912 913 void ReplaceDominatedBlock(HBasicBlock* existing, HBasicBlock* new_block) { 914 ReplaceElement(dominated_blocks_, existing, new_block); 915 } 916 917 void ClearDominanceInformation(); 918 919 int NumberOfBackEdges() const { 920 return IsLoopHeader() ? loop_information_->NumberOfBackEdges() : 0; 921 } 922 923 HInstruction* GetFirstInstruction() const { return instructions_.first_instruction_; } 924 HInstruction* GetLastInstruction() const { return instructions_.last_instruction_; } 925 const HInstructionList& GetInstructions() const { return instructions_; } 926 HInstruction* GetFirstPhi() const { return phis_.first_instruction_; } 927 HInstruction* GetLastPhi() const { return phis_.last_instruction_; } 928 const HInstructionList& GetPhis() const { return phis_; } 929 930 HInstruction* GetFirstInstructionDisregardMoves() const; 931 932 void AddSuccessor(HBasicBlock* block) { 933 successors_.push_back(block); 934 block->predecessors_.push_back(this); 935 } 936 937 void ReplaceSuccessor(HBasicBlock* existing, HBasicBlock* new_block) { 938 size_t successor_index = GetSuccessorIndexOf(existing); 939 existing->RemovePredecessor(this); 940 new_block->predecessors_.push_back(this); 941 successors_[successor_index] = new_block; 942 } 943 944 void ReplacePredecessor(HBasicBlock* existing, HBasicBlock* new_block) { 945 size_t predecessor_index = GetPredecessorIndexOf(existing); 946 existing->RemoveSuccessor(this); 947 new_block->successors_.push_back(this); 948 predecessors_[predecessor_index] = new_block; 949 } 950 951 // Insert `this` between `predecessor` and `successor. This method 952 // preserves the indicies, and will update the first edge found between 953 // `predecessor` and `successor`. 954 void InsertBetween(HBasicBlock* predecessor, HBasicBlock* successor) { 955 size_t predecessor_index = successor->GetPredecessorIndexOf(predecessor); 956 size_t successor_index = predecessor->GetSuccessorIndexOf(successor); 957 successor->predecessors_[predecessor_index] = this; 958 predecessor->successors_[successor_index] = this; 959 successors_.push_back(successor); 960 predecessors_.push_back(predecessor); 961 } 962 963 void RemovePredecessor(HBasicBlock* block) { 964 predecessors_.erase(predecessors_.begin() + GetPredecessorIndexOf(block)); 965 } 966 967 void RemoveSuccessor(HBasicBlock* block) { 968 successors_.erase(successors_.begin() + GetSuccessorIndexOf(block)); 969 } 970 971 void ClearAllPredecessors() { 972 predecessors_.clear(); 973 } 974 975 void AddPredecessor(HBasicBlock* block) { 976 predecessors_.push_back(block); 977 block->successors_.push_back(this); 978 } 979 980 void SwapPredecessors() { 981 DCHECK_EQ(predecessors_.size(), 2u); 982 std::swap(predecessors_[0], predecessors_[1]); 983 } 984 985 void SwapSuccessors() { 986 DCHECK_EQ(successors_.size(), 2u); 987 std::swap(successors_[0], successors_[1]); 988 } 989 990 size_t GetPredecessorIndexOf(HBasicBlock* predecessor) const { 991 return IndexOfElement(predecessors_, predecessor); 992 } 993 994 size_t GetSuccessorIndexOf(HBasicBlock* successor) const { 995 return IndexOfElement(successors_, successor); 996 } 997 998 HBasicBlock* GetSinglePredecessor() const { 999 DCHECK_EQ(GetPredecessors().size(), 1u); 1000 return GetPredecessors()[0]; 1001 } 1002 1003 HBasicBlock* GetSingleSuccessor() const { 1004 DCHECK_EQ(GetSuccessors().size(), 1u); 1005 return GetSuccessors()[0]; 1006 } 1007 1008 // Returns whether the first occurrence of `predecessor` in the list of 1009 // predecessors is at index `idx`. 1010 bool IsFirstIndexOfPredecessor(HBasicBlock* predecessor, size_t idx) const { 1011 DCHECK_EQ(GetPredecessors()[idx], predecessor); 1012 return GetPredecessorIndexOf(predecessor) == idx; 1013 } 1014 1015 // Create a new block between this block and its predecessors. The new block 1016 // is added to the graph, all predecessor edges are relinked to it and an edge 1017 // is created to `this`. Returns the new empty block. Reverse post order or 1018 // loop and try/catch information are not updated. 1019 HBasicBlock* CreateImmediateDominator(); 1020 1021 // Split the block into two blocks just before `cursor`. Returns the newly 1022 // created, latter block. Note that this method will add the block to the 1023 // graph, create a Goto at the end of the former block and will create an edge 1024 // between the blocks. It will not, however, update the reverse post order or 1025 // loop and try/catch information. 1026 HBasicBlock* SplitBefore(HInstruction* cursor); 1027 1028 // Split the block into two blocks just before `cursor`. Returns the newly 1029 // created block. Note that this method just updates raw block information, 1030 // like predecessors, successors, dominators, and instruction list. It does not 1031 // update the graph, reverse post order, loop information, nor make sure the 1032 // blocks are consistent (for example ending with a control flow instruction). 1033 HBasicBlock* SplitBeforeForInlining(HInstruction* cursor); 1034 1035 // Similar to `SplitBeforeForInlining` but does it after `cursor`. 1036 HBasicBlock* SplitAfterForInlining(HInstruction* cursor); 1037 1038 // Merge `other` at the end of `this`. Successors and dominated blocks of 1039 // `other` are changed to be successors and dominated blocks of `this`. Note 1040 // that this method does not update the graph, reverse post order, loop 1041 // information, nor make sure the blocks are consistent (for example ending 1042 // with a control flow instruction). 1043 void MergeWithInlined(HBasicBlock* other); 1044 1045 // Replace `this` with `other`. Predecessors, successors, and dominated blocks 1046 // of `this` are moved to `other`. 1047 // Note that this method does not update the graph, reverse post order, loop 1048 // information, nor make sure the blocks are consistent (for example ending 1049 // with a control flow instruction). 1050 void ReplaceWith(HBasicBlock* other); 1051 1052 // Merge `other` at the end of `this`. This method updates loops, reverse post 1053 // order, links to predecessors, successors, dominators and deletes the block 1054 // from the graph. The two blocks must be successive, i.e. `this` the only 1055 // predecessor of `other` and vice versa. 1056 void MergeWith(HBasicBlock* other); 1057 1058 // Disconnects `this` from all its predecessors, successors and dominator, 1059 // removes it from all loops it is included in and eventually from the graph. 1060 // The block must not dominate any other block. Predecessors and successors 1061 // are safely updated. 1062 void DisconnectAndDelete(); 1063 1064 void AddInstruction(HInstruction* instruction); 1065 // Insert `instruction` before/after an existing instruction `cursor`. 1066 void InsertInstructionBefore(HInstruction* instruction, HInstruction* cursor); 1067 void InsertInstructionAfter(HInstruction* instruction, HInstruction* cursor); 1068 // Replace instruction `initial` with `replacement` within this block. 1069 void ReplaceAndRemoveInstructionWith(HInstruction* initial, 1070 HInstruction* replacement); 1071 void AddPhi(HPhi* phi); 1072 void InsertPhiAfter(HPhi* instruction, HPhi* cursor); 1073 // RemoveInstruction and RemovePhi delete a given instruction from the respective 1074 // instruction list. With 'ensure_safety' set to true, it verifies that the 1075 // instruction is not in use and removes it from the use lists of its inputs. 1076 void RemoveInstruction(HInstruction* instruction, bool ensure_safety = true); 1077 void RemovePhi(HPhi* phi, bool ensure_safety = true); 1078 void RemoveInstructionOrPhi(HInstruction* instruction, bool ensure_safety = true); 1079 1080 bool IsLoopHeader() const { 1081 return IsInLoop() && (loop_information_->GetHeader() == this); 1082 } 1083 1084 bool IsLoopPreHeaderFirstPredecessor() const { 1085 DCHECK(IsLoopHeader()); 1086 return GetPredecessors()[0] == GetLoopInformation()->GetPreHeader(); 1087 } 1088 1089 bool IsFirstPredecessorBackEdge() const { 1090 DCHECK(IsLoopHeader()); 1091 return GetLoopInformation()->IsBackEdge(*GetPredecessors()[0]); 1092 } 1093 1094 HLoopInformation* GetLoopInformation() const { 1095 return loop_information_; 1096 } 1097 1098 // Set the loop_information_ on this block. Overrides the current 1099 // loop_information if it is an outer loop of the passed loop information. 1100 // Note that this method is called while creating the loop information. 1101 void SetInLoop(HLoopInformation* info) { 1102 if (IsLoopHeader()) { 1103 // Nothing to do. This just means `info` is an outer loop. 1104 } else if (!IsInLoop()) { 1105 loop_information_ = info; 1106 } else if (loop_information_->Contains(*info->GetHeader())) { 1107 // Block is currently part of an outer loop. Make it part of this inner loop. 1108 // Note that a non loop header having a loop information means this loop information 1109 // has already been populated 1110 loop_information_ = info; 1111 } else { 1112 // Block is part of an inner loop. Do not update the loop information. 1113 // Note that we cannot do the check `info->Contains(loop_information_)->GetHeader()` 1114 // at this point, because this method is being called while populating `info`. 1115 } 1116 } 1117 1118 // Raw update of the loop information. 1119 void SetLoopInformation(HLoopInformation* info) { 1120 loop_information_ = info; 1121 } 1122 1123 bool IsInLoop() const { return loop_information_ != nullptr; } 1124 1125 TryCatchInformation* GetTryCatchInformation() const { return try_catch_information_; } 1126 1127 void SetTryCatchInformation(TryCatchInformation* try_catch_information) { 1128 try_catch_information_ = try_catch_information; 1129 } 1130 1131 bool IsTryBlock() const { 1132 return try_catch_information_ != nullptr && try_catch_information_->IsTryBlock(); 1133 } 1134 1135 bool IsCatchBlock() const { 1136 return try_catch_information_ != nullptr && try_catch_information_->IsCatchBlock(); 1137 } 1138 1139 // Returns the try entry that this block's successors should have. They will 1140 // be in the same try, unless the block ends in a try boundary. In that case, 1141 // the appropriate try entry will be returned. 1142 const HTryBoundary* ComputeTryEntryOfSuccessors() const; 1143 1144 bool HasThrowingInstructions() const; 1145 1146 // Returns whether this block dominates the blocked passed as parameter. 1147 bool Dominates(HBasicBlock* block) const; 1148 1149 size_t GetLifetimeStart() const { return lifetime_start_; } 1150 size_t GetLifetimeEnd() const { return lifetime_end_; } 1151 1152 void SetLifetimeStart(size_t start) { lifetime_start_ = start; } 1153 void SetLifetimeEnd(size_t end) { lifetime_end_ = end; } 1154 1155 bool EndsWithControlFlowInstruction() const; 1156 bool EndsWithIf() const; 1157 bool EndsWithTryBoundary() const; 1158 bool HasSinglePhi() const; 1159 1160 private: 1161 HGraph* graph_; 1162 ArenaVector<HBasicBlock*> predecessors_; 1163 ArenaVector<HBasicBlock*> successors_; 1164 HInstructionList instructions_; 1165 HInstructionList phis_; 1166 HLoopInformation* loop_information_; 1167 HBasicBlock* dominator_; 1168 ArenaVector<HBasicBlock*> dominated_blocks_; 1169 uint32_t block_id_; 1170 // The dex program counter of the first instruction of this block. 1171 const uint32_t dex_pc_; 1172 size_t lifetime_start_; 1173 size_t lifetime_end_; 1174 TryCatchInformation* try_catch_information_; 1175 1176 friend class HGraph; 1177 friend class HInstruction; 1178 1179 DISALLOW_COPY_AND_ASSIGN(HBasicBlock); 1180}; 1181 1182// Iterates over the LoopInformation of all loops which contain 'block' 1183// from the innermost to the outermost. 1184class HLoopInformationOutwardIterator : public ValueObject { 1185 public: 1186 explicit HLoopInformationOutwardIterator(const HBasicBlock& block) 1187 : current_(block.GetLoopInformation()) {} 1188 1189 bool Done() const { return current_ == nullptr; } 1190 1191 void Advance() { 1192 DCHECK(!Done()); 1193 current_ = current_->GetPreHeader()->GetLoopInformation(); 1194 } 1195 1196 HLoopInformation* Current() const { 1197 DCHECK(!Done()); 1198 return current_; 1199 } 1200 1201 private: 1202 HLoopInformation* current_; 1203 1204 DISALLOW_COPY_AND_ASSIGN(HLoopInformationOutwardIterator); 1205}; 1206 1207#define FOR_EACH_CONCRETE_INSTRUCTION_COMMON(M) \ 1208 M(Above, Condition) \ 1209 M(AboveOrEqual, Condition) \ 1210 M(Add, BinaryOperation) \ 1211 M(And, BinaryOperation) \ 1212 M(ArrayGet, Instruction) \ 1213 M(ArrayLength, Instruction) \ 1214 M(ArraySet, Instruction) \ 1215 M(Below, Condition) \ 1216 M(BelowOrEqual, Condition) \ 1217 M(BooleanNot, UnaryOperation) \ 1218 M(BoundsCheck, Instruction) \ 1219 M(BoundType, Instruction) \ 1220 M(CheckCast, Instruction) \ 1221 M(ClassTableGet, Instruction) \ 1222 M(ClearException, Instruction) \ 1223 M(ClinitCheck, Instruction) \ 1224 M(Compare, BinaryOperation) \ 1225 M(CurrentMethod, Instruction) \ 1226 M(Deoptimize, Instruction) \ 1227 M(Div, BinaryOperation) \ 1228 M(DivZeroCheck, Instruction) \ 1229 M(DoubleConstant, Constant) \ 1230 M(Equal, Condition) \ 1231 M(Exit, Instruction) \ 1232 M(FloatConstant, Constant) \ 1233 M(Goto, Instruction) \ 1234 M(GreaterThan, Condition) \ 1235 M(GreaterThanOrEqual, Condition) \ 1236 M(If, Instruction) \ 1237 M(InstanceFieldGet, Instruction) \ 1238 M(InstanceFieldSet, Instruction) \ 1239 M(InstanceOf, Instruction) \ 1240 M(IntConstant, Constant) \ 1241 M(InvokeUnresolved, Invoke) \ 1242 M(InvokeInterface, Invoke) \ 1243 M(InvokeStaticOrDirect, Invoke) \ 1244 M(InvokeVirtual, Invoke) \ 1245 M(LessThan, Condition) \ 1246 M(LessThanOrEqual, Condition) \ 1247 M(LoadClass, Instruction) \ 1248 M(LoadException, Instruction) \ 1249 M(LoadString, Instruction) \ 1250 M(LongConstant, Constant) \ 1251 M(MemoryBarrier, Instruction) \ 1252 M(MonitorOperation, Instruction) \ 1253 M(Mul, BinaryOperation) \ 1254 M(NativeDebugInfo, Instruction) \ 1255 M(Neg, UnaryOperation) \ 1256 M(NewArray, Instruction) \ 1257 M(NewInstance, Instruction) \ 1258 M(Not, UnaryOperation) \ 1259 M(NotEqual, Condition) \ 1260 M(NullConstant, Instruction) \ 1261 M(NullCheck, Instruction) \ 1262 M(Or, BinaryOperation) \ 1263 M(PackedSwitch, Instruction) \ 1264 M(ParallelMove, Instruction) \ 1265 M(ParameterValue, Instruction) \ 1266 M(Phi, Instruction) \ 1267 M(Rem, BinaryOperation) \ 1268 M(Return, Instruction) \ 1269 M(ReturnVoid, Instruction) \ 1270 M(Ror, BinaryOperation) \ 1271 M(Shl, BinaryOperation) \ 1272 M(Shr, BinaryOperation) \ 1273 M(StaticFieldGet, Instruction) \ 1274 M(StaticFieldSet, Instruction) \ 1275 M(UnresolvedInstanceFieldGet, Instruction) \ 1276 M(UnresolvedInstanceFieldSet, Instruction) \ 1277 M(UnresolvedStaticFieldGet, Instruction) \ 1278 M(UnresolvedStaticFieldSet, Instruction) \ 1279 M(Select, Instruction) \ 1280 M(Sub, BinaryOperation) \ 1281 M(SuspendCheck, Instruction) \ 1282 M(Throw, Instruction) \ 1283 M(TryBoundary, Instruction) \ 1284 M(TypeConversion, Instruction) \ 1285 M(UShr, BinaryOperation) \ 1286 M(Xor, BinaryOperation) \ 1287 1288/* 1289 * Instructions, shared across several (not all) architectures. 1290 */ 1291#if !defined(ART_ENABLE_CODEGEN_arm) && !defined(ART_ENABLE_CODEGEN_arm64) 1292#define FOR_EACH_CONCRETE_INSTRUCTION_SHARED(M) 1293#else 1294#define FOR_EACH_CONCRETE_INSTRUCTION_SHARED(M) \ 1295 M(BitwiseNegatedRight, Instruction) \ 1296 M(MultiplyAccumulate, Instruction) \ 1297 M(IntermediateAddress, Instruction) 1298#endif 1299 1300#ifndef ART_ENABLE_CODEGEN_arm 1301#define FOR_EACH_CONCRETE_INSTRUCTION_ARM(M) 1302#else 1303#define FOR_EACH_CONCRETE_INSTRUCTION_ARM(M) \ 1304 M(ArmDexCacheArraysBase, Instruction) 1305#endif 1306 1307#ifndef ART_ENABLE_CODEGEN_arm64 1308#define FOR_EACH_CONCRETE_INSTRUCTION_ARM64(M) 1309#else 1310#define FOR_EACH_CONCRETE_INSTRUCTION_ARM64(M) \ 1311 M(Arm64DataProcWithShifterOp, Instruction) 1312#endif 1313 1314#ifndef ART_ENABLE_CODEGEN_mips 1315#define FOR_EACH_CONCRETE_INSTRUCTION_MIPS(M) 1316#else 1317#define FOR_EACH_CONCRETE_INSTRUCTION_MIPS(M) \ 1318 M(MipsComputeBaseMethodAddress, Instruction) \ 1319 M(MipsDexCacheArraysBase, Instruction) \ 1320 M(MipsPackedSwitch, Instruction) 1321#endif 1322 1323#define FOR_EACH_CONCRETE_INSTRUCTION_MIPS64(M) 1324 1325#ifndef ART_ENABLE_CODEGEN_x86 1326#define FOR_EACH_CONCRETE_INSTRUCTION_X86(M) 1327#else 1328#define FOR_EACH_CONCRETE_INSTRUCTION_X86(M) \ 1329 M(X86ComputeBaseMethodAddress, Instruction) \ 1330 M(X86LoadFromConstantTable, Instruction) \ 1331 M(X86FPNeg, Instruction) \ 1332 M(X86PackedSwitch, Instruction) 1333#endif 1334 1335#define FOR_EACH_CONCRETE_INSTRUCTION_X86_64(M) 1336 1337#define FOR_EACH_CONCRETE_INSTRUCTION(M) \ 1338 FOR_EACH_CONCRETE_INSTRUCTION_COMMON(M) \ 1339 FOR_EACH_CONCRETE_INSTRUCTION_SHARED(M) \ 1340 FOR_EACH_CONCRETE_INSTRUCTION_ARM(M) \ 1341 FOR_EACH_CONCRETE_INSTRUCTION_ARM64(M) \ 1342 FOR_EACH_CONCRETE_INSTRUCTION_MIPS(M) \ 1343 FOR_EACH_CONCRETE_INSTRUCTION_MIPS64(M) \ 1344 FOR_EACH_CONCRETE_INSTRUCTION_X86(M) \ 1345 FOR_EACH_CONCRETE_INSTRUCTION_X86_64(M) 1346 1347#define FOR_EACH_ABSTRACT_INSTRUCTION(M) \ 1348 M(Condition, BinaryOperation) \ 1349 M(Constant, Instruction) \ 1350 M(UnaryOperation, Instruction) \ 1351 M(BinaryOperation, Instruction) \ 1352 M(Invoke, Instruction) 1353 1354#define FOR_EACH_INSTRUCTION(M) \ 1355 FOR_EACH_CONCRETE_INSTRUCTION(M) \ 1356 FOR_EACH_ABSTRACT_INSTRUCTION(M) 1357 1358#define FORWARD_DECLARATION(type, super) class H##type; 1359FOR_EACH_INSTRUCTION(FORWARD_DECLARATION) 1360#undef FORWARD_DECLARATION 1361 1362#define DECLARE_INSTRUCTION(type) \ 1363 InstructionKind GetKindInternal() const OVERRIDE { return k##type; } \ 1364 const char* DebugName() const OVERRIDE { return #type; } \ 1365 bool InstructionTypeEquals(const HInstruction* other) const OVERRIDE { \ 1366 return other->Is##type(); \ 1367 } \ 1368 void Accept(HGraphVisitor* visitor) OVERRIDE 1369 1370#define DECLARE_ABSTRACT_INSTRUCTION(type) \ 1371 bool Is##type() const { return As##type() != nullptr; } \ 1372 const H##type* As##type() const { return this; } \ 1373 H##type* As##type() { return this; } 1374 1375template <typename T> 1376class HUseListNode : public ArenaObject<kArenaAllocUseListNode> { 1377 public: 1378 T GetUser() const { return user_; } 1379 size_t GetIndex() const { return index_; } 1380 void SetIndex(size_t index) { index_ = index; } 1381 1382 // Hook for the IntrusiveForwardList<>. 1383 // TODO: Hide this better. 1384 IntrusiveForwardListHook hook; 1385 1386 private: 1387 HUseListNode(T user, size_t index) 1388 : user_(user), index_(index) {} 1389 1390 T const user_; 1391 size_t index_; 1392 1393 friend class HInstruction; 1394 1395 DISALLOW_COPY_AND_ASSIGN(HUseListNode); 1396}; 1397 1398template <typename T> 1399using HUseList = IntrusiveForwardList<HUseListNode<T>>; 1400 1401// This class is used by HEnvironment and HInstruction classes to record the 1402// instructions they use and pointers to the corresponding HUseListNodes kept 1403// by the used instructions. 1404template <typename T> 1405class HUserRecord : public ValueObject { 1406 public: 1407 HUserRecord() : instruction_(nullptr), before_use_node_() {} 1408 explicit HUserRecord(HInstruction* instruction) : instruction_(instruction), before_use_node_() {} 1409 1410 HUserRecord(const HUserRecord<T>& old_record, typename HUseList<T>::iterator before_use_node) 1411 : HUserRecord(old_record.instruction_, before_use_node) {} 1412 HUserRecord(HInstruction* instruction, typename HUseList<T>::iterator before_use_node) 1413 : instruction_(instruction), before_use_node_(before_use_node) { 1414 DCHECK(instruction_ != nullptr); 1415 } 1416 1417 HInstruction* GetInstruction() const { return instruction_; } 1418 typename HUseList<T>::iterator GetBeforeUseNode() const { return before_use_node_; } 1419 typename HUseList<T>::iterator GetUseNode() const { return ++GetBeforeUseNode(); } 1420 1421 private: 1422 // Instruction used by the user. 1423 HInstruction* instruction_; 1424 1425 // Iterator before the corresponding entry in the use list kept by 'instruction_'. 1426 typename HUseList<T>::iterator before_use_node_; 1427}; 1428 1429// Helper class that extracts the input instruction from HUserRecord<HInstruction*>. 1430// This is used for HInstruction::GetInputs() to return a container wrapper providing 1431// HInstruction* values even though the underlying container has HUserRecord<>s. 1432struct HInputExtractor { 1433 HInstruction* operator()(HUserRecord<HInstruction*>& record) const { 1434 return record.GetInstruction(); 1435 } 1436 const HInstruction* operator()(const HUserRecord<HInstruction*>& record) const { 1437 return record.GetInstruction(); 1438 } 1439}; 1440 1441using HInputsRef = TransformArrayRef<HUserRecord<HInstruction*>, HInputExtractor>; 1442using HConstInputsRef = TransformArrayRef<const HUserRecord<HInstruction*>, HInputExtractor>; 1443 1444/** 1445 * Side-effects representation. 1446 * 1447 * For write/read dependences on fields/arrays, the dependence analysis uses 1448 * type disambiguation (e.g. a float field write cannot modify the value of an 1449 * integer field read) and the access type (e.g. a reference array write cannot 1450 * modify the value of a reference field read [although it may modify the 1451 * reference fetch prior to reading the field, which is represented by its own 1452 * write/read dependence]). The analysis makes conservative points-to 1453 * assumptions on reference types (e.g. two same typed arrays are assumed to be 1454 * the same, and any reference read depends on any reference read without 1455 * further regard of its type). 1456 * 1457 * The internal representation uses 38-bit and is described in the table below. 1458 * The first line indicates the side effect, and for field/array accesses the 1459 * second line indicates the type of the access (in the order of the 1460 * Primitive::Type enum). 1461 * The two numbered lines below indicate the bit position in the bitfield (read 1462 * vertically). 1463 * 1464 * |Depends on GC|ARRAY-R |FIELD-R |Can trigger GC|ARRAY-W |FIELD-W | 1465 * +-------------+---------+---------+--------------+---------+---------+ 1466 * | |DFJISCBZL|DFJISCBZL| |DFJISCBZL|DFJISCBZL| 1467 * | 3 |333333322|222222221| 1 |111111110|000000000| 1468 * | 7 |654321098|765432109| 8 |765432109|876543210| 1469 * 1470 * Note that, to ease the implementation, 'changes' bits are least significant 1471 * bits, while 'dependency' bits are most significant bits. 1472 */ 1473class SideEffects : public ValueObject { 1474 public: 1475 SideEffects() : flags_(0) {} 1476 1477 static SideEffects None() { 1478 return SideEffects(0); 1479 } 1480 1481 static SideEffects All() { 1482 return SideEffects(kAllChangeBits | kAllDependOnBits); 1483 } 1484 1485 static SideEffects AllChanges() { 1486 return SideEffects(kAllChangeBits); 1487 } 1488 1489 static SideEffects AllDependencies() { 1490 return SideEffects(kAllDependOnBits); 1491 } 1492 1493 static SideEffects AllExceptGCDependency() { 1494 return AllWritesAndReads().Union(SideEffects::CanTriggerGC()); 1495 } 1496 1497 static SideEffects AllWritesAndReads() { 1498 return SideEffects(kAllWrites | kAllReads); 1499 } 1500 1501 static SideEffects AllWrites() { 1502 return SideEffects(kAllWrites); 1503 } 1504 1505 static SideEffects AllReads() { 1506 return SideEffects(kAllReads); 1507 } 1508 1509 static SideEffects FieldWriteOfType(Primitive::Type type, bool is_volatile) { 1510 return is_volatile 1511 ? AllWritesAndReads() 1512 : SideEffects(TypeFlag(type, kFieldWriteOffset)); 1513 } 1514 1515 static SideEffects ArrayWriteOfType(Primitive::Type type) { 1516 return SideEffects(TypeFlag(type, kArrayWriteOffset)); 1517 } 1518 1519 static SideEffects FieldReadOfType(Primitive::Type type, bool is_volatile) { 1520 return is_volatile 1521 ? AllWritesAndReads() 1522 : SideEffects(TypeFlag(type, kFieldReadOffset)); 1523 } 1524 1525 static SideEffects ArrayReadOfType(Primitive::Type type) { 1526 return SideEffects(TypeFlag(type, kArrayReadOffset)); 1527 } 1528 1529 static SideEffects CanTriggerGC() { 1530 return SideEffects(1ULL << kCanTriggerGCBit); 1531 } 1532 1533 static SideEffects DependsOnGC() { 1534 return SideEffects(1ULL << kDependsOnGCBit); 1535 } 1536 1537 // Combines the side-effects of this and the other. 1538 SideEffects Union(SideEffects other) const { 1539 return SideEffects(flags_ | other.flags_); 1540 } 1541 1542 SideEffects Exclusion(SideEffects other) const { 1543 return SideEffects(flags_ & ~other.flags_); 1544 } 1545 1546 void Add(SideEffects other) { 1547 flags_ |= other.flags_; 1548 } 1549 1550 bool Includes(SideEffects other) const { 1551 return (other.flags_ & flags_) == other.flags_; 1552 } 1553 1554 bool HasSideEffects() const { 1555 return (flags_ & kAllChangeBits); 1556 } 1557 1558 bool HasDependencies() const { 1559 return (flags_ & kAllDependOnBits); 1560 } 1561 1562 // Returns true if there are no side effects or dependencies. 1563 bool DoesNothing() const { 1564 return flags_ == 0; 1565 } 1566 1567 // Returns true if something is written. 1568 bool DoesAnyWrite() const { 1569 return (flags_ & kAllWrites); 1570 } 1571 1572 // Returns true if something is read. 1573 bool DoesAnyRead() const { 1574 return (flags_ & kAllReads); 1575 } 1576 1577 // Returns true if potentially everything is written and read 1578 // (every type and every kind of access). 1579 bool DoesAllReadWrite() const { 1580 return (flags_ & (kAllWrites | kAllReads)) == (kAllWrites | kAllReads); 1581 } 1582 1583 bool DoesAll() const { 1584 return flags_ == (kAllChangeBits | kAllDependOnBits); 1585 } 1586 1587 // Returns true if `this` may read something written by `other`. 1588 bool MayDependOn(SideEffects other) const { 1589 const uint64_t depends_on_flags = (flags_ & kAllDependOnBits) >> kChangeBits; 1590 return (other.flags_ & depends_on_flags); 1591 } 1592 1593 // Returns string representation of flags (for debugging only). 1594 // Format: |x|DFJISCBZL|DFJISCBZL|y|DFJISCBZL|DFJISCBZL| 1595 std::string ToString() const { 1596 std::string flags = "|"; 1597 for (int s = kLastBit; s >= 0; s--) { 1598 bool current_bit_is_set = ((flags_ >> s) & 1) != 0; 1599 if ((s == kDependsOnGCBit) || (s == kCanTriggerGCBit)) { 1600 // This is a bit for the GC side effect. 1601 if (current_bit_is_set) { 1602 flags += "GC"; 1603 } 1604 flags += "|"; 1605 } else { 1606 // This is a bit for the array/field analysis. 1607 // The underscore character stands for the 'can trigger GC' bit. 1608 static const char *kDebug = "LZBCSIJFDLZBCSIJFD_LZBCSIJFDLZBCSIJFD"; 1609 if (current_bit_is_set) { 1610 flags += kDebug[s]; 1611 } 1612 if ((s == kFieldWriteOffset) || (s == kArrayWriteOffset) || 1613 (s == kFieldReadOffset) || (s == kArrayReadOffset)) { 1614 flags += "|"; 1615 } 1616 } 1617 } 1618 return flags; 1619 } 1620 1621 bool Equals(const SideEffects& other) const { return flags_ == other.flags_; } 1622 1623 private: 1624 static constexpr int kFieldArrayAnalysisBits = 9; 1625 1626 static constexpr int kFieldWriteOffset = 0; 1627 static constexpr int kArrayWriteOffset = kFieldWriteOffset + kFieldArrayAnalysisBits; 1628 static constexpr int kLastBitForWrites = kArrayWriteOffset + kFieldArrayAnalysisBits - 1; 1629 static constexpr int kCanTriggerGCBit = kLastBitForWrites + 1; 1630 1631 static constexpr int kChangeBits = kCanTriggerGCBit + 1; 1632 1633 static constexpr int kFieldReadOffset = kCanTriggerGCBit + 1; 1634 static constexpr int kArrayReadOffset = kFieldReadOffset + kFieldArrayAnalysisBits; 1635 static constexpr int kLastBitForReads = kArrayReadOffset + kFieldArrayAnalysisBits - 1; 1636 static constexpr int kDependsOnGCBit = kLastBitForReads + 1; 1637 1638 static constexpr int kLastBit = kDependsOnGCBit; 1639 static constexpr int kDependOnBits = kLastBit + 1 - kChangeBits; 1640 1641 // Aliases. 1642 1643 static_assert(kChangeBits == kDependOnBits, 1644 "the 'change' bits should match the 'depend on' bits."); 1645 1646 static constexpr uint64_t kAllChangeBits = ((1ULL << kChangeBits) - 1); 1647 static constexpr uint64_t kAllDependOnBits = ((1ULL << kDependOnBits) - 1) << kChangeBits; 1648 static constexpr uint64_t kAllWrites = 1649 ((1ULL << (kLastBitForWrites + 1 - kFieldWriteOffset)) - 1) << kFieldWriteOffset; 1650 static constexpr uint64_t kAllReads = 1651 ((1ULL << (kLastBitForReads + 1 - kFieldReadOffset)) - 1) << kFieldReadOffset; 1652 1653 // Translates type to bit flag. 1654 static uint64_t TypeFlag(Primitive::Type type, int offset) { 1655 CHECK_NE(type, Primitive::kPrimVoid); 1656 const uint64_t one = 1; 1657 const int shift = type; // 0-based consecutive enum 1658 DCHECK_LE(kFieldWriteOffset, shift); 1659 DCHECK_LT(shift, kArrayWriteOffset); 1660 return one << (type + offset); 1661 } 1662 1663 // Private constructor on direct flags value. 1664 explicit SideEffects(uint64_t flags) : flags_(flags) {} 1665 1666 uint64_t flags_; 1667}; 1668 1669// A HEnvironment object contains the values of virtual registers at a given location. 1670class HEnvironment : public ArenaObject<kArenaAllocEnvironment> { 1671 public: 1672 HEnvironment(ArenaAllocator* arena, 1673 size_t number_of_vregs, 1674 const DexFile& dex_file, 1675 uint32_t method_idx, 1676 uint32_t dex_pc, 1677 InvokeType invoke_type, 1678 HInstruction* holder) 1679 : vregs_(number_of_vregs, arena->Adapter(kArenaAllocEnvironmentVRegs)), 1680 locations_(number_of_vregs, arena->Adapter(kArenaAllocEnvironmentLocations)), 1681 parent_(nullptr), 1682 dex_file_(dex_file), 1683 method_idx_(method_idx), 1684 dex_pc_(dex_pc), 1685 invoke_type_(invoke_type), 1686 holder_(holder) { 1687 } 1688 1689 HEnvironment(ArenaAllocator* arena, const HEnvironment& to_copy, HInstruction* holder) 1690 : HEnvironment(arena, 1691 to_copy.Size(), 1692 to_copy.GetDexFile(), 1693 to_copy.GetMethodIdx(), 1694 to_copy.GetDexPc(), 1695 to_copy.GetInvokeType(), 1696 holder) {} 1697 1698 void SetAndCopyParentChain(ArenaAllocator* allocator, HEnvironment* parent) { 1699 if (parent_ != nullptr) { 1700 parent_->SetAndCopyParentChain(allocator, parent); 1701 } else { 1702 parent_ = new (allocator) HEnvironment(allocator, *parent, holder_); 1703 parent_->CopyFrom(parent); 1704 if (parent->GetParent() != nullptr) { 1705 parent_->SetAndCopyParentChain(allocator, parent->GetParent()); 1706 } 1707 } 1708 } 1709 1710 void CopyFrom(const ArenaVector<HInstruction*>& locals); 1711 void CopyFrom(HEnvironment* environment); 1712 1713 // Copy from `env`. If it's a loop phi for `loop_header`, copy the first 1714 // input to the loop phi instead. This is for inserting instructions that 1715 // require an environment (like HDeoptimization) in the loop pre-header. 1716 void CopyFromWithLoopPhiAdjustment(HEnvironment* env, HBasicBlock* loop_header); 1717 1718 void SetRawEnvAt(size_t index, HInstruction* instruction) { 1719 vregs_[index] = HUserRecord<HEnvironment*>(instruction); 1720 } 1721 1722 HInstruction* GetInstructionAt(size_t index) const { 1723 return vregs_[index].GetInstruction(); 1724 } 1725 1726 void RemoveAsUserOfInput(size_t index) const; 1727 1728 size_t Size() const { return vregs_.size(); } 1729 1730 HEnvironment* GetParent() const { return parent_; } 1731 1732 void SetLocationAt(size_t index, Location location) { 1733 locations_[index] = location; 1734 } 1735 1736 Location GetLocationAt(size_t index) const { 1737 return locations_[index]; 1738 } 1739 1740 uint32_t GetDexPc() const { 1741 return dex_pc_; 1742 } 1743 1744 uint32_t GetMethodIdx() const { 1745 return method_idx_; 1746 } 1747 1748 InvokeType GetInvokeType() const { 1749 return invoke_type_; 1750 } 1751 1752 const DexFile& GetDexFile() const { 1753 return dex_file_; 1754 } 1755 1756 HInstruction* GetHolder() const { 1757 return holder_; 1758 } 1759 1760 1761 bool IsFromInlinedInvoke() const { 1762 return GetParent() != nullptr; 1763 } 1764 1765 private: 1766 ArenaVector<HUserRecord<HEnvironment*>> vregs_; 1767 ArenaVector<Location> locations_; 1768 HEnvironment* parent_; 1769 const DexFile& dex_file_; 1770 const uint32_t method_idx_; 1771 const uint32_t dex_pc_; 1772 const InvokeType invoke_type_; 1773 1774 // The instruction that holds this environment. 1775 HInstruction* const holder_; 1776 1777 friend class HInstruction; 1778 1779 DISALLOW_COPY_AND_ASSIGN(HEnvironment); 1780}; 1781 1782class HInstruction : public ArenaObject<kArenaAllocInstruction> { 1783 public: 1784 HInstruction(SideEffects side_effects, uint32_t dex_pc) 1785 : previous_(nullptr), 1786 next_(nullptr), 1787 block_(nullptr), 1788 dex_pc_(dex_pc), 1789 id_(-1), 1790 ssa_index_(-1), 1791 packed_fields_(0u), 1792 environment_(nullptr), 1793 locations_(nullptr), 1794 live_interval_(nullptr), 1795 lifetime_position_(kNoLifetime), 1796 side_effects_(side_effects), 1797 reference_type_handle_(ReferenceTypeInfo::CreateInvalid().GetTypeHandle()) { 1798 SetPackedFlag<kFlagReferenceTypeIsExact>(ReferenceTypeInfo::CreateInvalid().IsExact()); 1799 } 1800 1801 virtual ~HInstruction() {} 1802 1803#define DECLARE_KIND(type, super) k##type, 1804 enum InstructionKind { 1805 FOR_EACH_INSTRUCTION(DECLARE_KIND) 1806 }; 1807#undef DECLARE_KIND 1808 1809 HInstruction* GetNext() const { return next_; } 1810 HInstruction* GetPrevious() const { return previous_; } 1811 1812 HInstruction* GetNextDisregardingMoves() const; 1813 HInstruction* GetPreviousDisregardingMoves() const; 1814 1815 HBasicBlock* GetBlock() const { return block_; } 1816 ArenaAllocator* GetArena() const { return block_->GetGraph()->GetArena(); } 1817 void SetBlock(HBasicBlock* block) { block_ = block; } 1818 bool IsInBlock() const { return block_ != nullptr; } 1819 bool IsInLoop() const { return block_->IsInLoop(); } 1820 bool IsLoopHeaderPhi() const { return IsPhi() && block_->IsLoopHeader(); } 1821 bool IsIrreducibleLoopHeaderPhi() const { 1822 return IsLoopHeaderPhi() && GetBlock()->GetLoopInformation()->IsIrreducible(); 1823 } 1824 1825 virtual ArrayRef<HUserRecord<HInstruction*>> GetInputRecords() = 0; 1826 1827 ArrayRef<const HUserRecord<HInstruction*>> GetInputRecords() const { 1828 // One virtual method is enough, just const_cast<> and then re-add the const. 1829 return ArrayRef<const HUserRecord<HInstruction*>>( 1830 const_cast<HInstruction*>(this)->GetInputRecords()); 1831 } 1832 1833 HInputsRef GetInputs() { 1834 return MakeTransformArrayRef(GetInputRecords(), HInputExtractor()); 1835 } 1836 1837 HConstInputsRef GetInputs() const { 1838 return MakeTransformArrayRef(GetInputRecords(), HInputExtractor()); 1839 } 1840 1841 size_t InputCount() const { return GetInputRecords().size(); } 1842 HInstruction* InputAt(size_t i) const { return InputRecordAt(i).GetInstruction(); } 1843 1844 void SetRawInputAt(size_t index, HInstruction* input) { 1845 SetRawInputRecordAt(index, HUserRecord<HInstruction*>(input)); 1846 } 1847 1848 virtual void Accept(HGraphVisitor* visitor) = 0; 1849 virtual const char* DebugName() const = 0; 1850 1851 virtual Primitive::Type GetType() const { return Primitive::kPrimVoid; } 1852 1853 virtual bool NeedsEnvironment() const { return false; } 1854 1855 uint32_t GetDexPc() const { return dex_pc_; } 1856 1857 virtual bool IsControlFlow() const { return false; } 1858 1859 virtual bool CanThrow() const { return false; } 1860 bool CanThrowIntoCatchBlock() const { return CanThrow() && block_->IsTryBlock(); } 1861 1862 bool HasSideEffects() const { return side_effects_.HasSideEffects(); } 1863 bool DoesAnyWrite() const { return side_effects_.DoesAnyWrite(); } 1864 1865 // Does not apply for all instructions, but having this at top level greatly 1866 // simplifies the null check elimination. 1867 // TODO: Consider merging can_be_null into ReferenceTypeInfo. 1868 virtual bool CanBeNull() const { 1869 DCHECK_EQ(GetType(), Primitive::kPrimNot) << "CanBeNull only applies to reference types"; 1870 return true; 1871 } 1872 1873 virtual bool CanDoImplicitNullCheckOn(HInstruction* obj ATTRIBUTE_UNUSED) const { 1874 return false; 1875 } 1876 1877 virtual bool IsActualObject() const { 1878 return GetType() == Primitive::kPrimNot; 1879 } 1880 1881 void SetReferenceTypeInfo(ReferenceTypeInfo rti); 1882 1883 ReferenceTypeInfo GetReferenceTypeInfo() const { 1884 DCHECK_EQ(GetType(), Primitive::kPrimNot); 1885 return ReferenceTypeInfo::CreateUnchecked(reference_type_handle_, 1886 GetPackedFlag<kFlagReferenceTypeIsExact>()); 1887 } 1888 1889 void AddUseAt(HInstruction* user, size_t index) { 1890 DCHECK(user != nullptr); 1891 // Note: fixup_end remains valid across push_front(). 1892 auto fixup_end = uses_.empty() ? uses_.begin() : ++uses_.begin(); 1893 HUseListNode<HInstruction*>* new_node = 1894 new (GetBlock()->GetGraph()->GetArena()) HUseListNode<HInstruction*>(user, index); 1895 uses_.push_front(*new_node); 1896 FixUpUserRecordsAfterUseInsertion(fixup_end); 1897 } 1898 1899 void AddEnvUseAt(HEnvironment* user, size_t index) { 1900 DCHECK(user != nullptr); 1901 // Note: env_fixup_end remains valid across push_front(). 1902 auto env_fixup_end = env_uses_.empty() ? env_uses_.begin() : ++env_uses_.begin(); 1903 HUseListNode<HEnvironment*>* new_node = 1904 new (GetBlock()->GetGraph()->GetArena()) HUseListNode<HEnvironment*>(user, index); 1905 env_uses_.push_front(*new_node); 1906 FixUpUserRecordsAfterEnvUseInsertion(env_fixup_end); 1907 } 1908 1909 void RemoveAsUserOfInput(size_t input) { 1910 HUserRecord<HInstruction*> input_use = InputRecordAt(input); 1911 HUseList<HInstruction*>::iterator before_use_node = input_use.GetBeforeUseNode(); 1912 input_use.GetInstruction()->uses_.erase_after(before_use_node); 1913 input_use.GetInstruction()->FixUpUserRecordsAfterUseRemoval(before_use_node); 1914 } 1915 1916 void RemoveAsUserOfAllInputs() { 1917 for (const HUserRecord<HInstruction*>& input_use : GetInputRecords()) { 1918 HUseList<HInstruction*>::iterator before_use_node = input_use.GetBeforeUseNode(); 1919 input_use.GetInstruction()->uses_.erase_after(before_use_node); 1920 input_use.GetInstruction()->FixUpUserRecordsAfterUseRemoval(before_use_node); 1921 } 1922 } 1923 1924 const HUseList<HInstruction*>& GetUses() const { return uses_; } 1925 const HUseList<HEnvironment*>& GetEnvUses() const { return env_uses_; } 1926 1927 bool HasUses() const { return !uses_.empty() || !env_uses_.empty(); } 1928 bool HasEnvironmentUses() const { return !env_uses_.empty(); } 1929 bool HasNonEnvironmentUses() const { return !uses_.empty(); } 1930 bool HasOnlyOneNonEnvironmentUse() const { 1931 return !HasEnvironmentUses() && GetUses().HasExactlyOneElement(); 1932 } 1933 1934 bool IsRemovable() const { 1935 return 1936 !HasSideEffects() && 1937 !CanThrow() && 1938 !IsSuspendCheck() && 1939 !IsControlFlow() && 1940 !IsNativeDebugInfo() && 1941 !IsParameterValue() && 1942 // If we added an explicit barrier then we should keep it. 1943 !IsMemoryBarrier(); 1944 } 1945 1946 bool IsDeadAndRemovable() const { 1947 return IsRemovable() && !HasUses(); 1948 } 1949 1950 // Does this instruction strictly dominate `other_instruction`? 1951 // Returns false if this instruction and `other_instruction` are the same. 1952 // Aborts if this instruction and `other_instruction` are both phis. 1953 bool StrictlyDominates(HInstruction* other_instruction) const; 1954 1955 int GetId() const { return id_; } 1956 void SetId(int id) { id_ = id; } 1957 1958 int GetSsaIndex() const { return ssa_index_; } 1959 void SetSsaIndex(int ssa_index) { ssa_index_ = ssa_index; } 1960 bool HasSsaIndex() const { return ssa_index_ != -1; } 1961 1962 bool HasEnvironment() const { return environment_ != nullptr; } 1963 HEnvironment* GetEnvironment() const { return environment_; } 1964 // Set the `environment_` field. Raw because this method does not 1965 // update the uses lists. 1966 void SetRawEnvironment(HEnvironment* environment) { 1967 DCHECK(environment_ == nullptr); 1968 DCHECK_EQ(environment->GetHolder(), this); 1969 environment_ = environment; 1970 } 1971 1972 void InsertRawEnvironment(HEnvironment* environment) { 1973 DCHECK(environment_ != nullptr); 1974 DCHECK_EQ(environment->GetHolder(), this); 1975 DCHECK(environment->GetParent() == nullptr); 1976 environment->parent_ = environment_; 1977 environment_ = environment; 1978 } 1979 1980 void RemoveEnvironment(); 1981 1982 // Set the environment of this instruction, copying it from `environment`. While 1983 // copying, the uses lists are being updated. 1984 void CopyEnvironmentFrom(HEnvironment* environment) { 1985 DCHECK(environment_ == nullptr); 1986 ArenaAllocator* allocator = GetBlock()->GetGraph()->GetArena(); 1987 environment_ = new (allocator) HEnvironment(allocator, *environment, this); 1988 environment_->CopyFrom(environment); 1989 if (environment->GetParent() != nullptr) { 1990 environment_->SetAndCopyParentChain(allocator, environment->GetParent()); 1991 } 1992 } 1993 1994 void CopyEnvironmentFromWithLoopPhiAdjustment(HEnvironment* environment, 1995 HBasicBlock* block) { 1996 DCHECK(environment_ == nullptr); 1997 ArenaAllocator* allocator = GetBlock()->GetGraph()->GetArena(); 1998 environment_ = new (allocator) HEnvironment(allocator, *environment, this); 1999 environment_->CopyFromWithLoopPhiAdjustment(environment, block); 2000 if (environment->GetParent() != nullptr) { 2001 environment_->SetAndCopyParentChain(allocator, environment->GetParent()); 2002 } 2003 } 2004 2005 // Returns the number of entries in the environment. Typically, that is the 2006 // number of dex registers in a method. It could be more in case of inlining. 2007 size_t EnvironmentSize() const; 2008 2009 LocationSummary* GetLocations() const { return locations_; } 2010 void SetLocations(LocationSummary* locations) { locations_ = locations; } 2011 2012 void ReplaceWith(HInstruction* instruction); 2013 void ReplaceInput(HInstruction* replacement, size_t index); 2014 2015 // This is almost the same as doing `ReplaceWith()`. But in this helper, the 2016 // uses of this instruction by `other` are *not* updated. 2017 void ReplaceWithExceptInReplacementAtIndex(HInstruction* other, size_t use_index) { 2018 ReplaceWith(other); 2019 other->ReplaceInput(this, use_index); 2020 } 2021 2022 // Move `this` instruction before `cursor`. 2023 void MoveBefore(HInstruction* cursor); 2024 2025 // Move `this` before its first user and out of any loops. If there is no 2026 // out-of-loop user that dominates all other users, move the instruction 2027 // to the end of the out-of-loop common dominator of the user's blocks. 2028 // 2029 // This can be used only on non-throwing instructions with no side effects that 2030 // have at least one use but no environment uses. 2031 void MoveBeforeFirstUserAndOutOfLoops(); 2032 2033#define INSTRUCTION_TYPE_CHECK(type, super) \ 2034 bool Is##type() const; \ 2035 const H##type* As##type() const; \ 2036 H##type* As##type(); 2037 2038 FOR_EACH_CONCRETE_INSTRUCTION(INSTRUCTION_TYPE_CHECK) 2039#undef INSTRUCTION_TYPE_CHECK 2040 2041#define INSTRUCTION_TYPE_CHECK(type, super) \ 2042 bool Is##type() const { return (As##type() != nullptr); } \ 2043 virtual const H##type* As##type() const { return nullptr; } \ 2044 virtual H##type* As##type() { return nullptr; } 2045 FOR_EACH_ABSTRACT_INSTRUCTION(INSTRUCTION_TYPE_CHECK) 2046#undef INSTRUCTION_TYPE_CHECK 2047 2048 // Returns whether the instruction can be moved within the graph. 2049 virtual bool CanBeMoved() const { return false; } 2050 2051 // Returns whether the two instructions are of the same kind. 2052 virtual bool InstructionTypeEquals(const HInstruction* other ATTRIBUTE_UNUSED) const { 2053 return false; 2054 } 2055 2056 // Returns whether any data encoded in the two instructions is equal. 2057 // This method does not look at the inputs. Both instructions must be 2058 // of the same type, otherwise the method has undefined behavior. 2059 virtual bool InstructionDataEquals(const HInstruction* other ATTRIBUTE_UNUSED) const { 2060 return false; 2061 } 2062 2063 // Returns whether two instructions are equal, that is: 2064 // 1) They have the same type and contain the same data (InstructionDataEquals). 2065 // 2) Their inputs are identical. 2066 bool Equals(const HInstruction* other) const; 2067 2068 // TODO: Remove this indirection when the [[pure]] attribute proposal (n3744) 2069 // is adopted and implemented by our C++ compiler(s). Fow now, we need to hide 2070 // the virtual function because the __attribute__((__pure__)) doesn't really 2071 // apply the strong requirement for virtual functions, preventing optimizations. 2072 InstructionKind GetKind() const PURE; 2073 virtual InstructionKind GetKindInternal() const = 0; 2074 2075 virtual size_t ComputeHashCode() const { 2076 size_t result = GetKind(); 2077 for (const HInstruction* input : GetInputs()) { 2078 result = (result * 31) + input->GetId(); 2079 } 2080 return result; 2081 } 2082 2083 SideEffects GetSideEffects() const { return side_effects_; } 2084 void SetSideEffects(SideEffects other) { side_effects_ = other; } 2085 void AddSideEffects(SideEffects other) { side_effects_.Add(other); } 2086 2087 size_t GetLifetimePosition() const { return lifetime_position_; } 2088 void SetLifetimePosition(size_t position) { lifetime_position_ = position; } 2089 LiveInterval* GetLiveInterval() const { return live_interval_; } 2090 void SetLiveInterval(LiveInterval* interval) { live_interval_ = interval; } 2091 bool HasLiveInterval() const { return live_interval_ != nullptr; } 2092 2093 bool IsSuspendCheckEntry() const { return IsSuspendCheck() && GetBlock()->IsEntryBlock(); } 2094 2095 // Returns whether the code generation of the instruction will require to have access 2096 // to the current method. Such instructions are: 2097 // (1): Instructions that require an environment, as calling the runtime requires 2098 // to walk the stack and have the current method stored at a specific stack address. 2099 // (2): HCurrentMethod, potentially used by HInvokeStaticOrDirect, HLoadString, or HLoadClass 2100 // to access the dex cache. 2101 bool NeedsCurrentMethod() const { 2102 return NeedsEnvironment() || IsCurrentMethod(); 2103 } 2104 2105 // Returns whether the code generation of the instruction will require to have access 2106 // to the dex cache of the current method's declaring class via the current method. 2107 virtual bool NeedsDexCacheOfDeclaringClass() const { return false; } 2108 2109 // Does this instruction have any use in an environment before 2110 // control flow hits 'other'? 2111 bool HasAnyEnvironmentUseBefore(HInstruction* other); 2112 2113 // Remove all references to environment uses of this instruction. 2114 // The caller must ensure that this is safe to do. 2115 void RemoveEnvironmentUsers(); 2116 2117 bool IsEmittedAtUseSite() const { return GetPackedFlag<kFlagEmittedAtUseSite>(); } 2118 void MarkEmittedAtUseSite() { SetPackedFlag<kFlagEmittedAtUseSite>(true); } 2119 2120 protected: 2121 // If set, the machine code for this instruction is assumed to be generated by 2122 // its users. Used by liveness analysis to compute use positions accordingly. 2123 static constexpr size_t kFlagEmittedAtUseSite = 0u; 2124 static constexpr size_t kFlagReferenceTypeIsExact = kFlagEmittedAtUseSite + 1; 2125 static constexpr size_t kNumberOfGenericPackedBits = kFlagReferenceTypeIsExact + 1; 2126 static constexpr size_t kMaxNumberOfPackedBits = sizeof(uint32_t) * kBitsPerByte; 2127 2128 const HUserRecord<HInstruction*> InputRecordAt(size_t i) const { 2129 return GetInputRecords()[i]; 2130 } 2131 2132 void SetRawInputRecordAt(size_t index, const HUserRecord<HInstruction*>& input) { 2133 ArrayRef<HUserRecord<HInstruction*>> input_records = GetInputRecords(); 2134 input_records[index] = input; 2135 } 2136 2137 uint32_t GetPackedFields() const { 2138 return packed_fields_; 2139 } 2140 2141 template <size_t flag> 2142 bool GetPackedFlag() const { 2143 return (packed_fields_ & (1u << flag)) != 0u; 2144 } 2145 2146 template <size_t flag> 2147 void SetPackedFlag(bool value = true) { 2148 packed_fields_ = (packed_fields_ & ~(1u << flag)) | ((value ? 1u : 0u) << flag); 2149 } 2150 2151 template <typename BitFieldType> 2152 typename BitFieldType::value_type GetPackedField() const { 2153 return BitFieldType::Decode(packed_fields_); 2154 } 2155 2156 template <typename BitFieldType> 2157 void SetPackedField(typename BitFieldType::value_type value) { 2158 DCHECK(IsUint<BitFieldType::size>(static_cast<uintptr_t>(value))); 2159 packed_fields_ = BitFieldType::Update(value, packed_fields_); 2160 } 2161 2162 private: 2163 void FixUpUserRecordsAfterUseInsertion(HUseList<HInstruction*>::iterator fixup_end) { 2164 auto before_use_node = uses_.before_begin(); 2165 for (auto use_node = uses_.begin(); use_node != fixup_end; ++use_node) { 2166 HInstruction* user = use_node->GetUser(); 2167 size_t input_index = use_node->GetIndex(); 2168 user->SetRawInputRecordAt(input_index, HUserRecord<HInstruction*>(this, before_use_node)); 2169 before_use_node = use_node; 2170 } 2171 } 2172 2173 void FixUpUserRecordsAfterUseRemoval(HUseList<HInstruction*>::iterator before_use_node) { 2174 auto next = ++HUseList<HInstruction*>::iterator(before_use_node); 2175 if (next != uses_.end()) { 2176 HInstruction* next_user = next->GetUser(); 2177 size_t next_index = next->GetIndex(); 2178 DCHECK(next_user->InputRecordAt(next_index).GetInstruction() == this); 2179 next_user->SetRawInputRecordAt(next_index, HUserRecord<HInstruction*>(this, before_use_node)); 2180 } 2181 } 2182 2183 void FixUpUserRecordsAfterEnvUseInsertion(HUseList<HEnvironment*>::iterator env_fixup_end) { 2184 auto before_env_use_node = env_uses_.before_begin(); 2185 for (auto env_use_node = env_uses_.begin(); env_use_node != env_fixup_end; ++env_use_node) { 2186 HEnvironment* user = env_use_node->GetUser(); 2187 size_t input_index = env_use_node->GetIndex(); 2188 user->vregs_[input_index] = HUserRecord<HEnvironment*>(this, before_env_use_node); 2189 before_env_use_node = env_use_node; 2190 } 2191 } 2192 2193 void FixUpUserRecordsAfterEnvUseRemoval(HUseList<HEnvironment*>::iterator before_env_use_node) { 2194 auto next = ++HUseList<HEnvironment*>::iterator(before_env_use_node); 2195 if (next != env_uses_.end()) { 2196 HEnvironment* next_user = next->GetUser(); 2197 size_t next_index = next->GetIndex(); 2198 DCHECK(next_user->vregs_[next_index].GetInstruction() == this); 2199 next_user->vregs_[next_index] = HUserRecord<HEnvironment*>(this, before_env_use_node); 2200 } 2201 } 2202 2203 HInstruction* previous_; 2204 HInstruction* next_; 2205 HBasicBlock* block_; 2206 const uint32_t dex_pc_; 2207 2208 // An instruction gets an id when it is added to the graph. 2209 // It reflects creation order. A negative id means the instruction 2210 // has not been added to the graph. 2211 int id_; 2212 2213 // When doing liveness analysis, instructions that have uses get an SSA index. 2214 int ssa_index_; 2215 2216 // Packed fields. 2217 uint32_t packed_fields_; 2218 2219 // List of instructions that have this instruction as input. 2220 HUseList<HInstruction*> uses_; 2221 2222 // List of environments that contain this instruction. 2223 HUseList<HEnvironment*> env_uses_; 2224 2225 // The environment associated with this instruction. Not null if the instruction 2226 // might jump out of the method. 2227 HEnvironment* environment_; 2228 2229 // Set by the code generator. 2230 LocationSummary* locations_; 2231 2232 // Set by the liveness analysis. 2233 LiveInterval* live_interval_; 2234 2235 // Set by the liveness analysis, this is the position in a linear 2236 // order of blocks where this instruction's live interval start. 2237 size_t lifetime_position_; 2238 2239 SideEffects side_effects_; 2240 2241 // The reference handle part of the reference type info. 2242 // The IsExact() flag is stored in packed fields. 2243 // TODO: for primitive types this should be marked as invalid. 2244 ReferenceTypeInfo::TypeHandle reference_type_handle_; 2245 2246 friend class GraphChecker; 2247 friend class HBasicBlock; 2248 friend class HEnvironment; 2249 friend class HGraph; 2250 friend class HInstructionList; 2251 2252 DISALLOW_COPY_AND_ASSIGN(HInstruction); 2253}; 2254std::ostream& operator<<(std::ostream& os, const HInstruction::InstructionKind& rhs); 2255 2256class HInstructionIterator : public ValueObject { 2257 public: 2258 explicit HInstructionIterator(const HInstructionList& instructions) 2259 : instruction_(instructions.first_instruction_) { 2260 next_ = Done() ? nullptr : instruction_->GetNext(); 2261 } 2262 2263 bool Done() const { return instruction_ == nullptr; } 2264 HInstruction* Current() const { return instruction_; } 2265 void Advance() { 2266 instruction_ = next_; 2267 next_ = Done() ? nullptr : instruction_->GetNext(); 2268 } 2269 2270 private: 2271 HInstruction* instruction_; 2272 HInstruction* next_; 2273 2274 DISALLOW_COPY_AND_ASSIGN(HInstructionIterator); 2275}; 2276 2277class HBackwardInstructionIterator : public ValueObject { 2278 public: 2279 explicit HBackwardInstructionIterator(const HInstructionList& instructions) 2280 : instruction_(instructions.last_instruction_) { 2281 next_ = Done() ? nullptr : instruction_->GetPrevious(); 2282 } 2283 2284 bool Done() const { return instruction_ == nullptr; } 2285 HInstruction* Current() const { return instruction_; } 2286 void Advance() { 2287 instruction_ = next_; 2288 next_ = Done() ? nullptr : instruction_->GetPrevious(); 2289 } 2290 2291 private: 2292 HInstruction* instruction_; 2293 HInstruction* next_; 2294 2295 DISALLOW_COPY_AND_ASSIGN(HBackwardInstructionIterator); 2296}; 2297 2298template<size_t N> 2299class HTemplateInstruction: public HInstruction { 2300 public: 2301 HTemplateInstruction<N>(SideEffects side_effects, uint32_t dex_pc) 2302 : HInstruction(side_effects, dex_pc), inputs_() {} 2303 virtual ~HTemplateInstruction() {} 2304 2305 using HInstruction::GetInputRecords; // Keep the const version visible. 2306 ArrayRef<HUserRecord<HInstruction*>> GetInputRecords() OVERRIDE FINAL { 2307 return ArrayRef<HUserRecord<HInstruction*>>(inputs_); 2308 } 2309 2310 private: 2311 std::array<HUserRecord<HInstruction*>, N> inputs_; 2312 2313 friend class SsaBuilder; 2314}; 2315 2316// HTemplateInstruction specialization for N=0. 2317template<> 2318class HTemplateInstruction<0>: public HInstruction { 2319 public: 2320 explicit HTemplateInstruction<0>(SideEffects side_effects, uint32_t dex_pc) 2321 : HInstruction(side_effects, dex_pc) {} 2322 2323 virtual ~HTemplateInstruction() {} 2324 2325 using HInstruction::GetInputRecords; // Keep the const version visible. 2326 ArrayRef<HUserRecord<HInstruction*>> GetInputRecords() OVERRIDE FINAL { 2327 return ArrayRef<HUserRecord<HInstruction*>>(); 2328 } 2329 2330 private: 2331 friend class SsaBuilder; 2332}; 2333 2334template<intptr_t N> 2335class HExpression : public HTemplateInstruction<N> { 2336 public: 2337 HExpression<N>(Primitive::Type type, SideEffects side_effects, uint32_t dex_pc) 2338 : HTemplateInstruction<N>(side_effects, dex_pc) { 2339 this->template SetPackedField<TypeField>(type); 2340 } 2341 virtual ~HExpression() {} 2342 2343 Primitive::Type GetType() const OVERRIDE { 2344 return TypeField::Decode(this->GetPackedFields()); 2345 } 2346 2347 protected: 2348 static constexpr size_t kFieldType = HInstruction::kNumberOfGenericPackedBits; 2349 static constexpr size_t kFieldTypeSize = 2350 MinimumBitsToStore(static_cast<size_t>(Primitive::kPrimLast)); 2351 static constexpr size_t kNumberOfExpressionPackedBits = kFieldType + kFieldTypeSize; 2352 static_assert(kNumberOfExpressionPackedBits <= HInstruction::kMaxNumberOfPackedBits, 2353 "Too many packed fields."); 2354 using TypeField = BitField<Primitive::Type, kFieldType, kFieldTypeSize>; 2355}; 2356 2357// Represents dex's RETURN_VOID opcode. A HReturnVoid is a control flow 2358// instruction that branches to the exit block. 2359class HReturnVoid FINAL : public HTemplateInstruction<0> { 2360 public: 2361 explicit HReturnVoid(uint32_t dex_pc = kNoDexPc) 2362 : HTemplateInstruction(SideEffects::None(), dex_pc) {} 2363 2364 bool IsControlFlow() const OVERRIDE { return true; } 2365 2366 DECLARE_INSTRUCTION(ReturnVoid); 2367 2368 private: 2369 DISALLOW_COPY_AND_ASSIGN(HReturnVoid); 2370}; 2371 2372// Represents dex's RETURN opcodes. A HReturn is a control flow 2373// instruction that branches to the exit block. 2374class HReturn FINAL : public HTemplateInstruction<1> { 2375 public: 2376 explicit HReturn(HInstruction* value, uint32_t dex_pc = kNoDexPc) 2377 : HTemplateInstruction(SideEffects::None(), dex_pc) { 2378 SetRawInputAt(0, value); 2379 } 2380 2381 bool IsControlFlow() const OVERRIDE { return true; } 2382 2383 DECLARE_INSTRUCTION(Return); 2384 2385 private: 2386 DISALLOW_COPY_AND_ASSIGN(HReturn); 2387}; 2388 2389class HPhi FINAL : public HInstruction { 2390 public: 2391 HPhi(ArenaAllocator* arena, 2392 uint32_t reg_number, 2393 size_t number_of_inputs, 2394 Primitive::Type type, 2395 uint32_t dex_pc = kNoDexPc) 2396 : HInstruction(SideEffects::None(), dex_pc), 2397 inputs_(number_of_inputs, arena->Adapter(kArenaAllocPhiInputs)), 2398 reg_number_(reg_number) { 2399 SetPackedField<TypeField>(ToPhiType(type)); 2400 DCHECK_NE(GetType(), Primitive::kPrimVoid); 2401 // Phis are constructed live and marked dead if conflicting or unused. 2402 // Individual steps of SsaBuilder should assume that if a phi has been 2403 // marked dead, it can be ignored and will be removed by SsaPhiElimination. 2404 SetPackedFlag<kFlagIsLive>(true); 2405 SetPackedFlag<kFlagCanBeNull>(true); 2406 } 2407 2408 // Returns a type equivalent to the given `type`, but that a `HPhi` can hold. 2409 static Primitive::Type ToPhiType(Primitive::Type type) { 2410 return Primitive::PrimitiveKind(type); 2411 } 2412 2413 bool IsCatchPhi() const { return GetBlock()->IsCatchBlock(); } 2414 2415 using HInstruction::GetInputRecords; // Keep the const version visible. 2416 ArrayRef<HUserRecord<HInstruction*>> GetInputRecords() OVERRIDE FINAL { 2417 return ArrayRef<HUserRecord<HInstruction*>>(inputs_); 2418 } 2419 2420 void AddInput(HInstruction* input); 2421 void RemoveInputAt(size_t index); 2422 2423 Primitive::Type GetType() const OVERRIDE { return GetPackedField<TypeField>(); } 2424 void SetType(Primitive::Type new_type) { 2425 // Make sure that only valid type changes occur. The following are allowed: 2426 // (1) int -> float/ref (primitive type propagation), 2427 // (2) long -> double (primitive type propagation). 2428 DCHECK(GetType() == new_type || 2429 (GetType() == Primitive::kPrimInt && new_type == Primitive::kPrimFloat) || 2430 (GetType() == Primitive::kPrimInt && new_type == Primitive::kPrimNot) || 2431 (GetType() == Primitive::kPrimLong && new_type == Primitive::kPrimDouble)); 2432 SetPackedField<TypeField>(new_type); 2433 } 2434 2435 bool CanBeNull() const OVERRIDE { return GetPackedFlag<kFlagCanBeNull>(); } 2436 void SetCanBeNull(bool can_be_null) { SetPackedFlag<kFlagCanBeNull>(can_be_null); } 2437 2438 uint32_t GetRegNumber() const { return reg_number_; } 2439 2440 void SetDead() { SetPackedFlag<kFlagIsLive>(false); } 2441 void SetLive() { SetPackedFlag<kFlagIsLive>(true); } 2442 bool IsDead() const { return !IsLive(); } 2443 bool IsLive() const { return GetPackedFlag<kFlagIsLive>(); } 2444 2445 bool IsVRegEquivalentOf(const HInstruction* other) const { 2446 return other != nullptr 2447 && other->IsPhi() 2448 && other->AsPhi()->GetBlock() == GetBlock() 2449 && other->AsPhi()->GetRegNumber() == GetRegNumber(); 2450 } 2451 2452 // Returns the next equivalent phi (starting from the current one) or null if there is none. 2453 // An equivalent phi is a phi having the same dex register and type. 2454 // It assumes that phis with the same dex register are adjacent. 2455 HPhi* GetNextEquivalentPhiWithSameType() { 2456 HInstruction* next = GetNext(); 2457 while (next != nullptr && next->AsPhi()->GetRegNumber() == reg_number_) { 2458 if (next->GetType() == GetType()) { 2459 return next->AsPhi(); 2460 } 2461 next = next->GetNext(); 2462 } 2463 return nullptr; 2464 } 2465 2466 DECLARE_INSTRUCTION(Phi); 2467 2468 private: 2469 static constexpr size_t kFieldType = HInstruction::kNumberOfGenericPackedBits; 2470 static constexpr size_t kFieldTypeSize = 2471 MinimumBitsToStore(static_cast<size_t>(Primitive::kPrimLast)); 2472 static constexpr size_t kFlagIsLive = kFieldType + kFieldTypeSize; 2473 static constexpr size_t kFlagCanBeNull = kFlagIsLive + 1; 2474 static constexpr size_t kNumberOfPhiPackedBits = kFlagCanBeNull + 1; 2475 static_assert(kNumberOfPhiPackedBits <= kMaxNumberOfPackedBits, "Too many packed fields."); 2476 using TypeField = BitField<Primitive::Type, kFieldType, kFieldTypeSize>; 2477 2478 ArenaVector<HUserRecord<HInstruction*>> inputs_; 2479 const uint32_t reg_number_; 2480 2481 DISALLOW_COPY_AND_ASSIGN(HPhi); 2482}; 2483 2484// The exit instruction is the only instruction of the exit block. 2485// Instructions aborting the method (HThrow and HReturn) must branch to the 2486// exit block. 2487class HExit FINAL : public HTemplateInstruction<0> { 2488 public: 2489 explicit HExit(uint32_t dex_pc = kNoDexPc) : HTemplateInstruction(SideEffects::None(), dex_pc) {} 2490 2491 bool IsControlFlow() const OVERRIDE { return true; } 2492 2493 DECLARE_INSTRUCTION(Exit); 2494 2495 private: 2496 DISALLOW_COPY_AND_ASSIGN(HExit); 2497}; 2498 2499// Jumps from one block to another. 2500class HGoto FINAL : public HTemplateInstruction<0> { 2501 public: 2502 explicit HGoto(uint32_t dex_pc = kNoDexPc) : HTemplateInstruction(SideEffects::None(), dex_pc) {} 2503 2504 bool IsControlFlow() const OVERRIDE { return true; } 2505 2506 HBasicBlock* GetSuccessor() const { 2507 return GetBlock()->GetSingleSuccessor(); 2508 } 2509 2510 DECLARE_INSTRUCTION(Goto); 2511 2512 private: 2513 DISALLOW_COPY_AND_ASSIGN(HGoto); 2514}; 2515 2516class HConstant : public HExpression<0> { 2517 public: 2518 explicit HConstant(Primitive::Type type, uint32_t dex_pc = kNoDexPc) 2519 : HExpression(type, SideEffects::None(), dex_pc) {} 2520 2521 bool CanBeMoved() const OVERRIDE { return true; } 2522 2523 // Is this constant -1 in the arithmetic sense? 2524 virtual bool IsMinusOne() const { return false; } 2525 // Is this constant 0 in the arithmetic sense? 2526 virtual bool IsArithmeticZero() const { return false; } 2527 // Is this constant a 0-bit pattern? 2528 virtual bool IsZeroBitPattern() const { return false; } 2529 // Is this constant 1 in the arithmetic sense? 2530 virtual bool IsOne() const { return false; } 2531 2532 virtual uint64_t GetValueAsUint64() const = 0; 2533 2534 DECLARE_ABSTRACT_INSTRUCTION(Constant); 2535 2536 private: 2537 DISALLOW_COPY_AND_ASSIGN(HConstant); 2538}; 2539 2540class HNullConstant FINAL : public HConstant { 2541 public: 2542 bool InstructionDataEquals(const HInstruction* other ATTRIBUTE_UNUSED) const OVERRIDE { 2543 return true; 2544 } 2545 2546 uint64_t GetValueAsUint64() const OVERRIDE { return 0; } 2547 2548 size_t ComputeHashCode() const OVERRIDE { return 0; } 2549 2550 // The null constant representation is a 0-bit pattern. 2551 virtual bool IsZeroBitPattern() const { return true; } 2552 2553 DECLARE_INSTRUCTION(NullConstant); 2554 2555 private: 2556 explicit HNullConstant(uint32_t dex_pc = kNoDexPc) : HConstant(Primitive::kPrimNot, dex_pc) {} 2557 2558 friend class HGraph; 2559 DISALLOW_COPY_AND_ASSIGN(HNullConstant); 2560}; 2561 2562// Constants of the type int. Those can be from Dex instructions, or 2563// synthesized (for example with the if-eqz instruction). 2564class HIntConstant FINAL : public HConstant { 2565 public: 2566 int32_t GetValue() const { return value_; } 2567 2568 uint64_t GetValueAsUint64() const OVERRIDE { 2569 return static_cast<uint64_t>(static_cast<uint32_t>(value_)); 2570 } 2571 2572 bool InstructionDataEquals(const HInstruction* other) const OVERRIDE { 2573 DCHECK(other->IsIntConstant()) << other->DebugName(); 2574 return other->AsIntConstant()->value_ == value_; 2575 } 2576 2577 size_t ComputeHashCode() const OVERRIDE { return GetValue(); } 2578 2579 bool IsMinusOne() const OVERRIDE { return GetValue() == -1; } 2580 bool IsArithmeticZero() const OVERRIDE { return GetValue() == 0; } 2581 bool IsZeroBitPattern() const OVERRIDE { return GetValue() == 0; } 2582 bool IsOne() const OVERRIDE { return GetValue() == 1; } 2583 2584 // Integer constants are used to encode Boolean values as well, 2585 // where 1 means true and 0 means false. 2586 bool IsTrue() const { return GetValue() == 1; } 2587 bool IsFalse() const { return GetValue() == 0; } 2588 2589 DECLARE_INSTRUCTION(IntConstant); 2590 2591 private: 2592 explicit HIntConstant(int32_t value, uint32_t dex_pc = kNoDexPc) 2593 : HConstant(Primitive::kPrimInt, dex_pc), value_(value) {} 2594 explicit HIntConstant(bool value, uint32_t dex_pc = kNoDexPc) 2595 : HConstant(Primitive::kPrimInt, dex_pc), value_(value ? 1 : 0) {} 2596 2597 const int32_t value_; 2598 2599 friend class HGraph; 2600 ART_FRIEND_TEST(GraphTest, InsertInstructionBefore); 2601 ART_FRIEND_TYPED_TEST(ParallelMoveTest, ConstantLast); 2602 DISALLOW_COPY_AND_ASSIGN(HIntConstant); 2603}; 2604 2605class HLongConstant FINAL : public HConstant { 2606 public: 2607 int64_t GetValue() const { return value_; } 2608 2609 uint64_t GetValueAsUint64() const OVERRIDE { return value_; } 2610 2611 bool InstructionDataEquals(const HInstruction* other) const OVERRIDE { 2612 DCHECK(other->IsLongConstant()) << other->DebugName(); 2613 return other->AsLongConstant()->value_ == value_; 2614 } 2615 2616 size_t ComputeHashCode() const OVERRIDE { return static_cast<size_t>(GetValue()); } 2617 2618 bool IsMinusOne() const OVERRIDE { return GetValue() == -1; } 2619 bool IsArithmeticZero() const OVERRIDE { return GetValue() == 0; } 2620 bool IsZeroBitPattern() const OVERRIDE { return GetValue() == 0; } 2621 bool IsOne() const OVERRIDE { return GetValue() == 1; } 2622 2623 DECLARE_INSTRUCTION(LongConstant); 2624 2625 private: 2626 explicit HLongConstant(int64_t value, uint32_t dex_pc = kNoDexPc) 2627 : HConstant(Primitive::kPrimLong, dex_pc), value_(value) {} 2628 2629 const int64_t value_; 2630 2631 friend class HGraph; 2632 DISALLOW_COPY_AND_ASSIGN(HLongConstant); 2633}; 2634 2635class HFloatConstant FINAL : public HConstant { 2636 public: 2637 float GetValue() const { return value_; } 2638 2639 uint64_t GetValueAsUint64() const OVERRIDE { 2640 return static_cast<uint64_t>(bit_cast<uint32_t, float>(value_)); 2641 } 2642 2643 bool InstructionDataEquals(const HInstruction* other) const OVERRIDE { 2644 DCHECK(other->IsFloatConstant()) << other->DebugName(); 2645 return other->AsFloatConstant()->GetValueAsUint64() == GetValueAsUint64(); 2646 } 2647 2648 size_t ComputeHashCode() const OVERRIDE { return static_cast<size_t>(GetValue()); } 2649 2650 bool IsMinusOne() const OVERRIDE { 2651 return bit_cast<uint32_t, float>(value_) == bit_cast<uint32_t, float>((-1.0f)); 2652 } 2653 bool IsArithmeticZero() const OVERRIDE { 2654 return std::fpclassify(value_) == FP_ZERO; 2655 } 2656 bool IsArithmeticPositiveZero() const { 2657 return IsArithmeticZero() && !std::signbit(value_); 2658 } 2659 bool IsArithmeticNegativeZero() const { 2660 return IsArithmeticZero() && std::signbit(value_); 2661 } 2662 bool IsZeroBitPattern() const OVERRIDE { 2663 return bit_cast<uint32_t, float>(value_) == bit_cast<uint32_t, float>(0.0f); 2664 } 2665 bool IsOne() const OVERRIDE { 2666 return bit_cast<uint32_t, float>(value_) == bit_cast<uint32_t, float>(1.0f); 2667 } 2668 bool IsNaN() const { 2669 return std::isnan(value_); 2670 } 2671 2672 DECLARE_INSTRUCTION(FloatConstant); 2673 2674 private: 2675 explicit HFloatConstant(float value, uint32_t dex_pc = kNoDexPc) 2676 : HConstant(Primitive::kPrimFloat, dex_pc), value_(value) {} 2677 explicit HFloatConstant(int32_t value, uint32_t dex_pc = kNoDexPc) 2678 : HConstant(Primitive::kPrimFloat, dex_pc), value_(bit_cast<float, int32_t>(value)) {} 2679 2680 const float value_; 2681 2682 // Only the SsaBuilder and HGraph can create floating-point constants. 2683 friend class SsaBuilder; 2684 friend class HGraph; 2685 DISALLOW_COPY_AND_ASSIGN(HFloatConstant); 2686}; 2687 2688class HDoubleConstant FINAL : public HConstant { 2689 public: 2690 double GetValue() const { return value_; } 2691 2692 uint64_t GetValueAsUint64() const OVERRIDE { return bit_cast<uint64_t, double>(value_); } 2693 2694 bool InstructionDataEquals(const HInstruction* other) const OVERRIDE { 2695 DCHECK(other->IsDoubleConstant()) << other->DebugName(); 2696 return other->AsDoubleConstant()->GetValueAsUint64() == GetValueAsUint64(); 2697 } 2698 2699 size_t ComputeHashCode() const OVERRIDE { return static_cast<size_t>(GetValue()); } 2700 2701 bool IsMinusOne() const OVERRIDE { 2702 return bit_cast<uint64_t, double>(value_) == bit_cast<uint64_t, double>((-1.0)); 2703 } 2704 bool IsArithmeticZero() const OVERRIDE { 2705 return std::fpclassify(value_) == FP_ZERO; 2706 } 2707 bool IsArithmeticPositiveZero() const { 2708 return IsArithmeticZero() && !std::signbit(value_); 2709 } 2710 bool IsArithmeticNegativeZero() const { 2711 return IsArithmeticZero() && std::signbit(value_); 2712 } 2713 bool IsZeroBitPattern() const OVERRIDE { 2714 return bit_cast<uint64_t, double>(value_) == bit_cast<uint64_t, double>((0.0)); 2715 } 2716 bool IsOne() const OVERRIDE { 2717 return bit_cast<uint64_t, double>(value_) == bit_cast<uint64_t, double>(1.0); 2718 } 2719 bool IsNaN() const { 2720 return std::isnan(value_); 2721 } 2722 2723 DECLARE_INSTRUCTION(DoubleConstant); 2724 2725 private: 2726 explicit HDoubleConstant(double value, uint32_t dex_pc = kNoDexPc) 2727 : HConstant(Primitive::kPrimDouble, dex_pc), value_(value) {} 2728 explicit HDoubleConstant(int64_t value, uint32_t dex_pc = kNoDexPc) 2729 : HConstant(Primitive::kPrimDouble, dex_pc), value_(bit_cast<double, int64_t>(value)) {} 2730 2731 const double value_; 2732 2733 // Only the SsaBuilder and HGraph can create floating-point constants. 2734 friend class SsaBuilder; 2735 friend class HGraph; 2736 DISALLOW_COPY_AND_ASSIGN(HDoubleConstant); 2737}; 2738 2739// Conditional branch. A block ending with an HIf instruction must have 2740// two successors. 2741class HIf FINAL : public HTemplateInstruction<1> { 2742 public: 2743 explicit HIf(HInstruction* input, uint32_t dex_pc = kNoDexPc) 2744 : HTemplateInstruction(SideEffects::None(), dex_pc) { 2745 SetRawInputAt(0, input); 2746 } 2747 2748 bool IsControlFlow() const OVERRIDE { return true; } 2749 2750 HBasicBlock* IfTrueSuccessor() const { 2751 return GetBlock()->GetSuccessors()[0]; 2752 } 2753 2754 HBasicBlock* IfFalseSuccessor() const { 2755 return GetBlock()->GetSuccessors()[1]; 2756 } 2757 2758 DECLARE_INSTRUCTION(If); 2759 2760 private: 2761 DISALLOW_COPY_AND_ASSIGN(HIf); 2762}; 2763 2764 2765// Abstract instruction which marks the beginning and/or end of a try block and 2766// links it to the respective exception handlers. Behaves the same as a Goto in 2767// non-exceptional control flow. 2768// Normal-flow successor is stored at index zero, exception handlers under 2769// higher indices in no particular order. 2770class HTryBoundary FINAL : public HTemplateInstruction<0> { 2771 public: 2772 enum class BoundaryKind { 2773 kEntry, 2774 kExit, 2775 kLast = kExit 2776 }; 2777 2778 explicit HTryBoundary(BoundaryKind kind, uint32_t dex_pc = kNoDexPc) 2779 : HTemplateInstruction(SideEffects::None(), dex_pc) { 2780 SetPackedField<BoundaryKindField>(kind); 2781 } 2782 2783 bool IsControlFlow() const OVERRIDE { return true; } 2784 2785 // Returns the block's non-exceptional successor (index zero). 2786 HBasicBlock* GetNormalFlowSuccessor() const { return GetBlock()->GetSuccessors()[0]; } 2787 2788 ArrayRef<HBasicBlock* const> GetExceptionHandlers() const { 2789 return ArrayRef<HBasicBlock* const>(GetBlock()->GetSuccessors()).SubArray(1u); 2790 } 2791 2792 // Returns whether `handler` is among its exception handlers (non-zero index 2793 // successors). 2794 bool HasExceptionHandler(const HBasicBlock& handler) const { 2795 DCHECK(handler.IsCatchBlock()); 2796 return GetBlock()->HasSuccessor(&handler, 1u /* Skip first successor. */); 2797 } 2798 2799 // If not present already, adds `handler` to its block's list of exception 2800 // handlers. 2801 void AddExceptionHandler(HBasicBlock* handler) { 2802 if (!HasExceptionHandler(*handler)) { 2803 GetBlock()->AddSuccessor(handler); 2804 } 2805 } 2806 2807 BoundaryKind GetBoundaryKind() const { return GetPackedField<BoundaryKindField>(); } 2808 bool IsEntry() const { return GetBoundaryKind() == BoundaryKind::kEntry; } 2809 2810 bool HasSameExceptionHandlersAs(const HTryBoundary& other) const; 2811 2812 DECLARE_INSTRUCTION(TryBoundary); 2813 2814 private: 2815 static constexpr size_t kFieldBoundaryKind = kNumberOfGenericPackedBits; 2816 static constexpr size_t kFieldBoundaryKindSize = 2817 MinimumBitsToStore(static_cast<size_t>(BoundaryKind::kLast)); 2818 static constexpr size_t kNumberOfTryBoundaryPackedBits = 2819 kFieldBoundaryKind + kFieldBoundaryKindSize; 2820 static_assert(kNumberOfTryBoundaryPackedBits <= kMaxNumberOfPackedBits, 2821 "Too many packed fields."); 2822 using BoundaryKindField = BitField<BoundaryKind, kFieldBoundaryKind, kFieldBoundaryKindSize>; 2823 2824 DISALLOW_COPY_AND_ASSIGN(HTryBoundary); 2825}; 2826 2827// Deoptimize to interpreter, upon checking a condition. 2828class HDeoptimize FINAL : public HTemplateInstruction<1> { 2829 public: 2830 // We set CanTriggerGC to prevent any intermediate address to be live 2831 // at the point of the `HDeoptimize`. 2832 HDeoptimize(HInstruction* cond, uint32_t dex_pc) 2833 : HTemplateInstruction(SideEffects::CanTriggerGC(), dex_pc) { 2834 SetRawInputAt(0, cond); 2835 } 2836 2837 bool CanBeMoved() const OVERRIDE { return true; } 2838 bool InstructionDataEquals(const HInstruction* other ATTRIBUTE_UNUSED) const OVERRIDE { 2839 return true; 2840 } 2841 bool NeedsEnvironment() const OVERRIDE { return true; } 2842 bool CanThrow() const OVERRIDE { return true; } 2843 2844 DECLARE_INSTRUCTION(Deoptimize); 2845 2846 private: 2847 DISALLOW_COPY_AND_ASSIGN(HDeoptimize); 2848}; 2849 2850// Represents the ArtMethod that was passed as a first argument to 2851// the method. It is used by instructions that depend on it, like 2852// instructions that work with the dex cache. 2853class HCurrentMethod FINAL : public HExpression<0> { 2854 public: 2855 explicit HCurrentMethod(Primitive::Type type, uint32_t dex_pc = kNoDexPc) 2856 : HExpression(type, SideEffects::None(), dex_pc) {} 2857 2858 DECLARE_INSTRUCTION(CurrentMethod); 2859 2860 private: 2861 DISALLOW_COPY_AND_ASSIGN(HCurrentMethod); 2862}; 2863 2864// Fetches an ArtMethod from the virtual table or the interface method table 2865// of a class. 2866class HClassTableGet FINAL : public HExpression<1> { 2867 public: 2868 enum class TableKind { 2869 kVTable, 2870 kIMTable, 2871 kLast = kIMTable 2872 }; 2873 HClassTableGet(HInstruction* cls, 2874 Primitive::Type type, 2875 TableKind kind, 2876 size_t index, 2877 uint32_t dex_pc) 2878 : HExpression(type, SideEffects::None(), dex_pc), 2879 index_(index) { 2880 SetPackedField<TableKindField>(kind); 2881 SetRawInputAt(0, cls); 2882 } 2883 2884 bool CanBeMoved() const OVERRIDE { return true; } 2885 bool InstructionDataEquals(const HInstruction* other) const OVERRIDE { 2886 return other->AsClassTableGet()->GetIndex() == index_ && 2887 other->AsClassTableGet()->GetPackedFields() == GetPackedFields(); 2888 } 2889 2890 TableKind GetTableKind() const { return GetPackedField<TableKindField>(); } 2891 size_t GetIndex() const { return index_; } 2892 2893 DECLARE_INSTRUCTION(ClassTableGet); 2894 2895 private: 2896 static constexpr size_t kFieldTableKind = kNumberOfExpressionPackedBits; 2897 static constexpr size_t kFieldTableKindSize = 2898 MinimumBitsToStore(static_cast<size_t>(TableKind::kLast)); 2899 static constexpr size_t kNumberOfClassTableGetPackedBits = kFieldTableKind + kFieldTableKindSize; 2900 static_assert(kNumberOfClassTableGetPackedBits <= kMaxNumberOfPackedBits, 2901 "Too many packed fields."); 2902 using TableKindField = BitField<TableKind, kFieldTableKind, kFieldTableKind>; 2903 2904 // The index of the ArtMethod in the table. 2905 const size_t index_; 2906 2907 DISALLOW_COPY_AND_ASSIGN(HClassTableGet); 2908}; 2909 2910// PackedSwitch (jump table). A block ending with a PackedSwitch instruction will 2911// have one successor for each entry in the switch table, and the final successor 2912// will be the block containing the next Dex opcode. 2913class HPackedSwitch FINAL : public HTemplateInstruction<1> { 2914 public: 2915 HPackedSwitch(int32_t start_value, 2916 uint32_t num_entries, 2917 HInstruction* input, 2918 uint32_t dex_pc = kNoDexPc) 2919 : HTemplateInstruction(SideEffects::None(), dex_pc), 2920 start_value_(start_value), 2921 num_entries_(num_entries) { 2922 SetRawInputAt(0, input); 2923 } 2924 2925 bool IsControlFlow() const OVERRIDE { return true; } 2926 2927 int32_t GetStartValue() const { return start_value_; } 2928 2929 uint32_t GetNumEntries() const { return num_entries_; } 2930 2931 HBasicBlock* GetDefaultBlock() const { 2932 // Last entry is the default block. 2933 return GetBlock()->GetSuccessors()[num_entries_]; 2934 } 2935 DECLARE_INSTRUCTION(PackedSwitch); 2936 2937 private: 2938 const int32_t start_value_; 2939 const uint32_t num_entries_; 2940 2941 DISALLOW_COPY_AND_ASSIGN(HPackedSwitch); 2942}; 2943 2944class HUnaryOperation : public HExpression<1> { 2945 public: 2946 HUnaryOperation(Primitive::Type result_type, HInstruction* input, uint32_t dex_pc = kNoDexPc) 2947 : HExpression(result_type, SideEffects::None(), dex_pc) { 2948 SetRawInputAt(0, input); 2949 } 2950 2951 HInstruction* GetInput() const { return InputAt(0); } 2952 Primitive::Type GetResultType() const { return GetType(); } 2953 2954 bool CanBeMoved() const OVERRIDE { return true; } 2955 bool InstructionDataEquals(const HInstruction* other ATTRIBUTE_UNUSED) const OVERRIDE { 2956 return true; 2957 } 2958 2959 // Try to statically evaluate `this` and return a HConstant 2960 // containing the result of this evaluation. If `this` cannot 2961 // be evaluated as a constant, return null. 2962 HConstant* TryStaticEvaluation() const; 2963 2964 // Apply this operation to `x`. 2965 virtual HConstant* Evaluate(HIntConstant* x) const = 0; 2966 virtual HConstant* Evaluate(HLongConstant* x) const = 0; 2967 virtual HConstant* Evaluate(HFloatConstant* x) const = 0; 2968 virtual HConstant* Evaluate(HDoubleConstant* x) const = 0; 2969 2970 DECLARE_ABSTRACT_INSTRUCTION(UnaryOperation); 2971 2972 private: 2973 DISALLOW_COPY_AND_ASSIGN(HUnaryOperation); 2974}; 2975 2976class HBinaryOperation : public HExpression<2> { 2977 public: 2978 HBinaryOperation(Primitive::Type result_type, 2979 HInstruction* left, 2980 HInstruction* right, 2981 SideEffects side_effects = SideEffects::None(), 2982 uint32_t dex_pc = kNoDexPc) 2983 : HExpression(result_type, side_effects, dex_pc) { 2984 SetRawInputAt(0, left); 2985 SetRawInputAt(1, right); 2986 } 2987 2988 HInstruction* GetLeft() const { return InputAt(0); } 2989 HInstruction* GetRight() const { return InputAt(1); } 2990 Primitive::Type GetResultType() const { return GetType(); } 2991 2992 virtual bool IsCommutative() const { return false; } 2993 2994 // Put constant on the right. 2995 // Returns whether order is changed. 2996 bool OrderInputsWithConstantOnTheRight() { 2997 HInstruction* left = InputAt(0); 2998 HInstruction* right = InputAt(1); 2999 if (left->IsConstant() && !right->IsConstant()) { 3000 ReplaceInput(right, 0); 3001 ReplaceInput(left, 1); 3002 return true; 3003 } 3004 return false; 3005 } 3006 3007 // Order inputs by instruction id, but favor constant on the right side. 3008 // This helps GVN for commutative ops. 3009 void OrderInputs() { 3010 DCHECK(IsCommutative()); 3011 HInstruction* left = InputAt(0); 3012 HInstruction* right = InputAt(1); 3013 if (left == right || (!left->IsConstant() && right->IsConstant())) { 3014 return; 3015 } 3016 if (OrderInputsWithConstantOnTheRight()) { 3017 return; 3018 } 3019 // Order according to instruction id. 3020 if (left->GetId() > right->GetId()) { 3021 ReplaceInput(right, 0); 3022 ReplaceInput(left, 1); 3023 } 3024 } 3025 3026 bool CanBeMoved() const OVERRIDE { return true; } 3027 bool InstructionDataEquals(const HInstruction* other ATTRIBUTE_UNUSED) const OVERRIDE { 3028 return true; 3029 } 3030 3031 // Try to statically evaluate `this` and return a HConstant 3032 // containing the result of this evaluation. If `this` cannot 3033 // be evaluated as a constant, return null. 3034 HConstant* TryStaticEvaluation() const; 3035 3036 // Apply this operation to `x` and `y`. 3037 virtual HConstant* Evaluate(HNullConstant* x ATTRIBUTE_UNUSED, 3038 HNullConstant* y ATTRIBUTE_UNUSED) const { 3039 LOG(FATAL) << DebugName() << " is not defined for the (null, null) case."; 3040 UNREACHABLE(); 3041 } 3042 virtual HConstant* Evaluate(HIntConstant* x, HIntConstant* y) const = 0; 3043 virtual HConstant* Evaluate(HLongConstant* x, HLongConstant* y) const = 0; 3044 virtual HConstant* Evaluate(HLongConstant* x ATTRIBUTE_UNUSED, 3045 HIntConstant* y ATTRIBUTE_UNUSED) const { 3046 LOG(FATAL) << DebugName() << " is not defined for the (long, int) case."; 3047 UNREACHABLE(); 3048 } 3049 virtual HConstant* Evaluate(HFloatConstant* x, HFloatConstant* y) const = 0; 3050 virtual HConstant* Evaluate(HDoubleConstant* x, HDoubleConstant* y) const = 0; 3051 3052 // Returns an input that can legally be used as the right input and is 3053 // constant, or null. 3054 HConstant* GetConstantRight() const; 3055 3056 // If `GetConstantRight()` returns one of the input, this returns the other 3057 // one. Otherwise it returns null. 3058 HInstruction* GetLeastConstantLeft() const; 3059 3060 DECLARE_ABSTRACT_INSTRUCTION(BinaryOperation); 3061 3062 private: 3063 DISALLOW_COPY_AND_ASSIGN(HBinaryOperation); 3064}; 3065 3066// The comparison bias applies for floating point operations and indicates how NaN 3067// comparisons are treated: 3068enum class ComparisonBias { 3069 kNoBias, // bias is not applicable (i.e. for long operation) 3070 kGtBias, // return 1 for NaN comparisons 3071 kLtBias, // return -1 for NaN comparisons 3072 kLast = kLtBias 3073}; 3074 3075std::ostream& operator<<(std::ostream& os, const ComparisonBias& rhs); 3076 3077class HCondition : public HBinaryOperation { 3078 public: 3079 HCondition(HInstruction* first, HInstruction* second, uint32_t dex_pc = kNoDexPc) 3080 : HBinaryOperation(Primitive::kPrimBoolean, first, second, SideEffects::None(), dex_pc) { 3081 SetPackedField<ComparisonBiasField>(ComparisonBias::kNoBias); 3082 } 3083 3084 // For code generation purposes, returns whether this instruction is just before 3085 // `instruction`, and disregard moves in between. 3086 bool IsBeforeWhenDisregardMoves(HInstruction* instruction) const; 3087 3088 DECLARE_ABSTRACT_INSTRUCTION(Condition); 3089 3090 virtual IfCondition GetCondition() const = 0; 3091 3092 virtual IfCondition GetOppositeCondition() const = 0; 3093 3094 bool IsGtBias() const { return GetBias() == ComparisonBias::kGtBias; } 3095 bool IsLtBias() const { return GetBias() == ComparisonBias::kLtBias; } 3096 3097 ComparisonBias GetBias() const { return GetPackedField<ComparisonBiasField>(); } 3098 void SetBias(ComparisonBias bias) { SetPackedField<ComparisonBiasField>(bias); } 3099 3100 bool InstructionDataEquals(const HInstruction* other) const OVERRIDE { 3101 return GetPackedFields() == other->AsCondition()->GetPackedFields(); 3102 } 3103 3104 bool IsFPConditionTrueIfNaN() const { 3105 DCHECK(Primitive::IsFloatingPointType(InputAt(0)->GetType())) << InputAt(0)->GetType(); 3106 IfCondition if_cond = GetCondition(); 3107 if (if_cond == kCondNE) { 3108 return true; 3109 } else if (if_cond == kCondEQ) { 3110 return false; 3111 } 3112 return ((if_cond == kCondGT) || (if_cond == kCondGE)) && IsGtBias(); 3113 } 3114 3115 bool IsFPConditionFalseIfNaN() const { 3116 DCHECK(Primitive::IsFloatingPointType(InputAt(0)->GetType())) << InputAt(0)->GetType(); 3117 IfCondition if_cond = GetCondition(); 3118 if (if_cond == kCondEQ) { 3119 return true; 3120 } else if (if_cond == kCondNE) { 3121 return false; 3122 } 3123 return ((if_cond == kCondLT) || (if_cond == kCondLE)) && IsGtBias(); 3124 } 3125 3126 protected: 3127 // Needed if we merge a HCompare into a HCondition. 3128 static constexpr size_t kFieldComparisonBias = kNumberOfExpressionPackedBits; 3129 static constexpr size_t kFieldComparisonBiasSize = 3130 MinimumBitsToStore(static_cast<size_t>(ComparisonBias::kLast)); 3131 static constexpr size_t kNumberOfConditionPackedBits = 3132 kFieldComparisonBias + kFieldComparisonBiasSize; 3133 static_assert(kNumberOfConditionPackedBits <= kMaxNumberOfPackedBits, "Too many packed fields."); 3134 using ComparisonBiasField = 3135 BitField<ComparisonBias, kFieldComparisonBias, kFieldComparisonBiasSize>; 3136 3137 template <typename T> 3138 int32_t Compare(T x, T y) const { return x > y ? 1 : (x < y ? -1 : 0); } 3139 3140 template <typename T> 3141 int32_t CompareFP(T x, T y) const { 3142 DCHECK(Primitive::IsFloatingPointType(InputAt(0)->GetType())) << InputAt(0)->GetType(); 3143 DCHECK_NE(GetBias(), ComparisonBias::kNoBias); 3144 // Handle the bias. 3145 return std::isunordered(x, y) ? (IsGtBias() ? 1 : -1) : Compare(x, y); 3146 } 3147 3148 // Return an integer constant containing the result of a condition evaluated at compile time. 3149 HIntConstant* MakeConstantCondition(bool value, uint32_t dex_pc) const { 3150 return GetBlock()->GetGraph()->GetIntConstant(value, dex_pc); 3151 } 3152 3153 private: 3154 DISALLOW_COPY_AND_ASSIGN(HCondition); 3155}; 3156 3157// Instruction to check if two inputs are equal to each other. 3158class HEqual FINAL : public HCondition { 3159 public: 3160 HEqual(HInstruction* first, HInstruction* second, uint32_t dex_pc = kNoDexPc) 3161 : HCondition(first, second, dex_pc) {} 3162 3163 bool IsCommutative() const OVERRIDE { return true; } 3164 3165 HConstant* Evaluate(HNullConstant* x ATTRIBUTE_UNUSED, 3166 HNullConstant* y ATTRIBUTE_UNUSED) const OVERRIDE { 3167 return MakeConstantCondition(true, GetDexPc()); 3168 } 3169 HConstant* Evaluate(HIntConstant* x, HIntConstant* y) const OVERRIDE { 3170 return MakeConstantCondition(Compute(x->GetValue(), y->GetValue()), GetDexPc()); 3171 } 3172 // In the following Evaluate methods, a HCompare instruction has 3173 // been merged into this HEqual instruction; evaluate it as 3174 // `Compare(x, y) == 0`. 3175 HConstant* Evaluate(HLongConstant* x, HLongConstant* y) const OVERRIDE { 3176 return MakeConstantCondition(Compute(Compare(x->GetValue(), y->GetValue()), 0), 3177 GetDexPc()); 3178 } 3179 HConstant* Evaluate(HFloatConstant* x, HFloatConstant* y) const OVERRIDE { 3180 return MakeConstantCondition(Compute(CompareFP(x->GetValue(), y->GetValue()), 0), GetDexPc()); 3181 } 3182 HConstant* Evaluate(HDoubleConstant* x, HDoubleConstant* y) const OVERRIDE { 3183 return MakeConstantCondition(Compute(CompareFP(x->GetValue(), y->GetValue()), 0), GetDexPc()); 3184 } 3185 3186 DECLARE_INSTRUCTION(Equal); 3187 3188 IfCondition GetCondition() const OVERRIDE { 3189 return kCondEQ; 3190 } 3191 3192 IfCondition GetOppositeCondition() const OVERRIDE { 3193 return kCondNE; 3194 } 3195 3196 private: 3197 template <typename T> static bool Compute(T x, T y) { return x == y; } 3198 3199 DISALLOW_COPY_AND_ASSIGN(HEqual); 3200}; 3201 3202class HNotEqual FINAL : public HCondition { 3203 public: 3204 HNotEqual(HInstruction* first, HInstruction* second, uint32_t dex_pc = kNoDexPc) 3205 : HCondition(first, second, dex_pc) {} 3206 3207 bool IsCommutative() const OVERRIDE { return true; } 3208 3209 HConstant* Evaluate(HNullConstant* x ATTRIBUTE_UNUSED, 3210 HNullConstant* y ATTRIBUTE_UNUSED) const OVERRIDE { 3211 return MakeConstantCondition(false, GetDexPc()); 3212 } 3213 HConstant* Evaluate(HIntConstant* x, HIntConstant* y) const OVERRIDE { 3214 return MakeConstantCondition(Compute(x->GetValue(), y->GetValue()), GetDexPc()); 3215 } 3216 // In the following Evaluate methods, a HCompare instruction has 3217 // been merged into this HNotEqual instruction; evaluate it as 3218 // `Compare(x, y) != 0`. 3219 HConstant* Evaluate(HLongConstant* x, HLongConstant* y) const OVERRIDE { 3220 return MakeConstantCondition(Compute(Compare(x->GetValue(), y->GetValue()), 0), GetDexPc()); 3221 } 3222 HConstant* Evaluate(HFloatConstant* x, HFloatConstant* y) const OVERRIDE { 3223 return MakeConstantCondition(Compute(CompareFP(x->GetValue(), y->GetValue()), 0), GetDexPc()); 3224 } 3225 HConstant* Evaluate(HDoubleConstant* x, HDoubleConstant* y) const OVERRIDE { 3226 return MakeConstantCondition(Compute(CompareFP(x->GetValue(), y->GetValue()), 0), GetDexPc()); 3227 } 3228 3229 DECLARE_INSTRUCTION(NotEqual); 3230 3231 IfCondition GetCondition() const OVERRIDE { 3232 return kCondNE; 3233 } 3234 3235 IfCondition GetOppositeCondition() const OVERRIDE { 3236 return kCondEQ; 3237 } 3238 3239 private: 3240 template <typename T> static bool Compute(T x, T y) { return x != y; } 3241 3242 DISALLOW_COPY_AND_ASSIGN(HNotEqual); 3243}; 3244 3245class HLessThan FINAL : public HCondition { 3246 public: 3247 HLessThan(HInstruction* first, HInstruction* second, uint32_t dex_pc = kNoDexPc) 3248 : HCondition(first, second, dex_pc) {} 3249 3250 HConstant* Evaluate(HIntConstant* x, HIntConstant* y) const OVERRIDE { 3251 return MakeConstantCondition(Compute(x->GetValue(), y->GetValue()), GetDexPc()); 3252 } 3253 // In the following Evaluate methods, a HCompare instruction has 3254 // been merged into this HLessThan instruction; evaluate it as 3255 // `Compare(x, y) < 0`. 3256 HConstant* Evaluate(HLongConstant* x, HLongConstant* y) const OVERRIDE { 3257 return MakeConstantCondition(Compute(Compare(x->GetValue(), y->GetValue()), 0), GetDexPc()); 3258 } 3259 HConstant* Evaluate(HFloatConstant* x, HFloatConstant* y) const OVERRIDE { 3260 return MakeConstantCondition(Compute(CompareFP(x->GetValue(), y->GetValue()), 0), GetDexPc()); 3261 } 3262 HConstant* Evaluate(HDoubleConstant* x, HDoubleConstant* y) const OVERRIDE { 3263 return MakeConstantCondition(Compute(CompareFP(x->GetValue(), y->GetValue()), 0), GetDexPc()); 3264 } 3265 3266 DECLARE_INSTRUCTION(LessThan); 3267 3268 IfCondition GetCondition() const OVERRIDE { 3269 return kCondLT; 3270 } 3271 3272 IfCondition GetOppositeCondition() const OVERRIDE { 3273 return kCondGE; 3274 } 3275 3276 private: 3277 template <typename T> static bool Compute(T x, T y) { return x < y; } 3278 3279 DISALLOW_COPY_AND_ASSIGN(HLessThan); 3280}; 3281 3282class HLessThanOrEqual FINAL : public HCondition { 3283 public: 3284 HLessThanOrEqual(HInstruction* first, HInstruction* second, uint32_t dex_pc = kNoDexPc) 3285 : HCondition(first, second, dex_pc) {} 3286 3287 HConstant* Evaluate(HIntConstant* x, HIntConstant* y) const OVERRIDE { 3288 return MakeConstantCondition(Compute(x->GetValue(), y->GetValue()), GetDexPc()); 3289 } 3290 // In the following Evaluate methods, a HCompare instruction has 3291 // been merged into this HLessThanOrEqual instruction; evaluate it as 3292 // `Compare(x, y) <= 0`. 3293 HConstant* Evaluate(HLongConstant* x, HLongConstant* y) const OVERRIDE { 3294 return MakeConstantCondition(Compute(Compare(x->GetValue(), y->GetValue()), 0), GetDexPc()); 3295 } 3296 HConstant* Evaluate(HFloatConstant* x, HFloatConstant* y) const OVERRIDE { 3297 return MakeConstantCondition(Compute(CompareFP(x->GetValue(), y->GetValue()), 0), GetDexPc()); 3298 } 3299 HConstant* Evaluate(HDoubleConstant* x, HDoubleConstant* y) const OVERRIDE { 3300 return MakeConstantCondition(Compute(CompareFP(x->GetValue(), y->GetValue()), 0), GetDexPc()); 3301 } 3302 3303 DECLARE_INSTRUCTION(LessThanOrEqual); 3304 3305 IfCondition GetCondition() const OVERRIDE { 3306 return kCondLE; 3307 } 3308 3309 IfCondition GetOppositeCondition() const OVERRIDE { 3310 return kCondGT; 3311 } 3312 3313 private: 3314 template <typename T> static bool Compute(T x, T y) { return x <= y; } 3315 3316 DISALLOW_COPY_AND_ASSIGN(HLessThanOrEqual); 3317}; 3318 3319class HGreaterThan FINAL : public HCondition { 3320 public: 3321 HGreaterThan(HInstruction* first, HInstruction* second, uint32_t dex_pc = kNoDexPc) 3322 : HCondition(first, second, dex_pc) {} 3323 3324 HConstant* Evaluate(HIntConstant* x, HIntConstant* y) const OVERRIDE { 3325 return MakeConstantCondition(Compute(x->GetValue(), y->GetValue()), GetDexPc()); 3326 } 3327 // In the following Evaluate methods, a HCompare instruction has 3328 // been merged into this HGreaterThan instruction; evaluate it as 3329 // `Compare(x, y) > 0`. 3330 HConstant* Evaluate(HLongConstant* x, HLongConstant* y) const OVERRIDE { 3331 return MakeConstantCondition(Compute(Compare(x->GetValue(), y->GetValue()), 0), GetDexPc()); 3332 } 3333 HConstant* Evaluate(HFloatConstant* x, HFloatConstant* y) const OVERRIDE { 3334 return MakeConstantCondition(Compute(CompareFP(x->GetValue(), y->GetValue()), 0), GetDexPc()); 3335 } 3336 HConstant* Evaluate(HDoubleConstant* x, HDoubleConstant* y) const OVERRIDE { 3337 return MakeConstantCondition(Compute(CompareFP(x->GetValue(), y->GetValue()), 0), GetDexPc()); 3338 } 3339 3340 DECLARE_INSTRUCTION(GreaterThan); 3341 3342 IfCondition GetCondition() const OVERRIDE { 3343 return kCondGT; 3344 } 3345 3346 IfCondition GetOppositeCondition() const OVERRIDE { 3347 return kCondLE; 3348 } 3349 3350 private: 3351 template <typename T> static bool Compute(T x, T y) { return x > y; } 3352 3353 DISALLOW_COPY_AND_ASSIGN(HGreaterThan); 3354}; 3355 3356class HGreaterThanOrEqual FINAL : public HCondition { 3357 public: 3358 HGreaterThanOrEqual(HInstruction* first, HInstruction* second, uint32_t dex_pc = kNoDexPc) 3359 : HCondition(first, second, dex_pc) {} 3360 3361 HConstant* Evaluate(HIntConstant* x, HIntConstant* y) const OVERRIDE { 3362 return MakeConstantCondition(Compute(x->GetValue(), y->GetValue()), GetDexPc()); 3363 } 3364 // In the following Evaluate methods, a HCompare instruction has 3365 // been merged into this HGreaterThanOrEqual instruction; evaluate it as 3366 // `Compare(x, y) >= 0`. 3367 HConstant* Evaluate(HLongConstant* x, HLongConstant* y) const OVERRIDE { 3368 return MakeConstantCondition(Compute(Compare(x->GetValue(), y->GetValue()), 0), GetDexPc()); 3369 } 3370 HConstant* Evaluate(HFloatConstant* x, HFloatConstant* y) const OVERRIDE { 3371 return MakeConstantCondition(Compute(CompareFP(x->GetValue(), y->GetValue()), 0), GetDexPc()); 3372 } 3373 HConstant* Evaluate(HDoubleConstant* x, HDoubleConstant* y) const OVERRIDE { 3374 return MakeConstantCondition(Compute(CompareFP(x->GetValue(), y->GetValue()), 0), GetDexPc()); 3375 } 3376 3377 DECLARE_INSTRUCTION(GreaterThanOrEqual); 3378 3379 IfCondition GetCondition() const OVERRIDE { 3380 return kCondGE; 3381 } 3382 3383 IfCondition GetOppositeCondition() const OVERRIDE { 3384 return kCondLT; 3385 } 3386 3387 private: 3388 template <typename T> static bool Compute(T x, T y) { return x >= y; } 3389 3390 DISALLOW_COPY_AND_ASSIGN(HGreaterThanOrEqual); 3391}; 3392 3393class HBelow FINAL : public HCondition { 3394 public: 3395 HBelow(HInstruction* first, HInstruction* second, uint32_t dex_pc = kNoDexPc) 3396 : HCondition(first, second, dex_pc) {} 3397 3398 HConstant* Evaluate(HIntConstant* x, HIntConstant* y) const OVERRIDE { 3399 return MakeConstantCondition(Compute(x->GetValue(), y->GetValue()), GetDexPc()); 3400 } 3401 HConstant* Evaluate(HLongConstant* x, HLongConstant* y) const OVERRIDE { 3402 return MakeConstantCondition(Compute(x->GetValue(), y->GetValue()), GetDexPc()); 3403 } 3404 HConstant* Evaluate(HFloatConstant* x ATTRIBUTE_UNUSED, 3405 HFloatConstant* y ATTRIBUTE_UNUSED) const OVERRIDE { 3406 LOG(FATAL) << DebugName() << " is not defined for float values"; 3407 UNREACHABLE(); 3408 } 3409 HConstant* Evaluate(HDoubleConstant* x ATTRIBUTE_UNUSED, 3410 HDoubleConstant* y ATTRIBUTE_UNUSED) const OVERRIDE { 3411 LOG(FATAL) << DebugName() << " is not defined for double values"; 3412 UNREACHABLE(); 3413 } 3414 3415 DECLARE_INSTRUCTION(Below); 3416 3417 IfCondition GetCondition() const OVERRIDE { 3418 return kCondB; 3419 } 3420 3421 IfCondition GetOppositeCondition() const OVERRIDE { 3422 return kCondAE; 3423 } 3424 3425 private: 3426 template <typename T> static bool Compute(T x, T y) { 3427 return MakeUnsigned(x) < MakeUnsigned(y); 3428 } 3429 3430 DISALLOW_COPY_AND_ASSIGN(HBelow); 3431}; 3432 3433class HBelowOrEqual FINAL : public HCondition { 3434 public: 3435 HBelowOrEqual(HInstruction* first, HInstruction* second, uint32_t dex_pc = kNoDexPc) 3436 : HCondition(first, second, dex_pc) {} 3437 3438 HConstant* Evaluate(HIntConstant* x, HIntConstant* y) const OVERRIDE { 3439 return MakeConstantCondition(Compute(x->GetValue(), y->GetValue()), GetDexPc()); 3440 } 3441 HConstant* Evaluate(HLongConstant* x, HLongConstant* y) const OVERRIDE { 3442 return MakeConstantCondition(Compute(x->GetValue(), y->GetValue()), GetDexPc()); 3443 } 3444 HConstant* Evaluate(HFloatConstant* x ATTRIBUTE_UNUSED, 3445 HFloatConstant* y ATTRIBUTE_UNUSED) const OVERRIDE { 3446 LOG(FATAL) << DebugName() << " is not defined for float values"; 3447 UNREACHABLE(); 3448 } 3449 HConstant* Evaluate(HDoubleConstant* x ATTRIBUTE_UNUSED, 3450 HDoubleConstant* y ATTRIBUTE_UNUSED) const OVERRIDE { 3451 LOG(FATAL) << DebugName() << " is not defined for double values"; 3452 UNREACHABLE(); 3453 } 3454 3455 DECLARE_INSTRUCTION(BelowOrEqual); 3456 3457 IfCondition GetCondition() const OVERRIDE { 3458 return kCondBE; 3459 } 3460 3461 IfCondition GetOppositeCondition() const OVERRIDE { 3462 return kCondA; 3463 } 3464 3465 private: 3466 template <typename T> static bool Compute(T x, T y) { 3467 return MakeUnsigned(x) <= MakeUnsigned(y); 3468 } 3469 3470 DISALLOW_COPY_AND_ASSIGN(HBelowOrEqual); 3471}; 3472 3473class HAbove FINAL : public HCondition { 3474 public: 3475 HAbove(HInstruction* first, HInstruction* second, uint32_t dex_pc = kNoDexPc) 3476 : HCondition(first, second, dex_pc) {} 3477 3478 HConstant* Evaluate(HIntConstant* x, HIntConstant* y) const OVERRIDE { 3479 return MakeConstantCondition(Compute(x->GetValue(), y->GetValue()), GetDexPc()); 3480 } 3481 HConstant* Evaluate(HLongConstant* x, HLongConstant* y) const OVERRIDE { 3482 return MakeConstantCondition(Compute(x->GetValue(), y->GetValue()), GetDexPc()); 3483 } 3484 HConstant* Evaluate(HFloatConstant* x ATTRIBUTE_UNUSED, 3485 HFloatConstant* y ATTRIBUTE_UNUSED) const OVERRIDE { 3486 LOG(FATAL) << DebugName() << " is not defined for float values"; 3487 UNREACHABLE(); 3488 } 3489 HConstant* Evaluate(HDoubleConstant* x ATTRIBUTE_UNUSED, 3490 HDoubleConstant* y ATTRIBUTE_UNUSED) const OVERRIDE { 3491 LOG(FATAL) << DebugName() << " is not defined for double values"; 3492 UNREACHABLE(); 3493 } 3494 3495 DECLARE_INSTRUCTION(Above); 3496 3497 IfCondition GetCondition() const OVERRIDE { 3498 return kCondA; 3499 } 3500 3501 IfCondition GetOppositeCondition() const OVERRIDE { 3502 return kCondBE; 3503 } 3504 3505 private: 3506 template <typename T> static bool Compute(T x, T y) { 3507 return MakeUnsigned(x) > MakeUnsigned(y); 3508 } 3509 3510 DISALLOW_COPY_AND_ASSIGN(HAbove); 3511}; 3512 3513class HAboveOrEqual FINAL : public HCondition { 3514 public: 3515 HAboveOrEqual(HInstruction* first, HInstruction* second, uint32_t dex_pc = kNoDexPc) 3516 : HCondition(first, second, dex_pc) {} 3517 3518 HConstant* Evaluate(HIntConstant* x, HIntConstant* y) const OVERRIDE { 3519 return MakeConstantCondition(Compute(x->GetValue(), y->GetValue()), GetDexPc()); 3520 } 3521 HConstant* Evaluate(HLongConstant* x, HLongConstant* y) const OVERRIDE { 3522 return MakeConstantCondition(Compute(x->GetValue(), y->GetValue()), GetDexPc()); 3523 } 3524 HConstant* Evaluate(HFloatConstant* x ATTRIBUTE_UNUSED, 3525 HFloatConstant* y ATTRIBUTE_UNUSED) const OVERRIDE { 3526 LOG(FATAL) << DebugName() << " is not defined for float values"; 3527 UNREACHABLE(); 3528 } 3529 HConstant* Evaluate(HDoubleConstant* x ATTRIBUTE_UNUSED, 3530 HDoubleConstant* y ATTRIBUTE_UNUSED) const OVERRIDE { 3531 LOG(FATAL) << DebugName() << " is not defined for double values"; 3532 UNREACHABLE(); 3533 } 3534 3535 DECLARE_INSTRUCTION(AboveOrEqual); 3536 3537 IfCondition GetCondition() const OVERRIDE { 3538 return kCondAE; 3539 } 3540 3541 IfCondition GetOppositeCondition() const OVERRIDE { 3542 return kCondB; 3543 } 3544 3545 private: 3546 template <typename T> static bool Compute(T x, T y) { 3547 return MakeUnsigned(x) >= MakeUnsigned(y); 3548 } 3549 3550 DISALLOW_COPY_AND_ASSIGN(HAboveOrEqual); 3551}; 3552 3553// Instruction to check how two inputs compare to each other. 3554// Result is 0 if input0 == input1, 1 if input0 > input1, or -1 if input0 < input1. 3555class HCompare FINAL : public HBinaryOperation { 3556 public: 3557 // Note that `comparison_type` is the type of comparison performed 3558 // between the comparison's inputs, not the type of the instantiated 3559 // HCompare instruction (which is always Primitive::kPrimInt). 3560 HCompare(Primitive::Type comparison_type, 3561 HInstruction* first, 3562 HInstruction* second, 3563 ComparisonBias bias, 3564 uint32_t dex_pc) 3565 : HBinaryOperation(Primitive::kPrimInt, 3566 first, 3567 second, 3568 SideEffectsForArchRuntimeCalls(comparison_type), 3569 dex_pc) { 3570 SetPackedField<ComparisonBiasField>(bias); 3571 DCHECK_EQ(comparison_type, Primitive::PrimitiveKind(first->GetType())); 3572 DCHECK_EQ(comparison_type, Primitive::PrimitiveKind(second->GetType())); 3573 } 3574 3575 template <typename T> 3576 int32_t Compute(T x, T y) const { return x > y ? 1 : (x < y ? -1 : 0); } 3577 3578 template <typename T> 3579 int32_t ComputeFP(T x, T y) const { 3580 DCHECK(Primitive::IsFloatingPointType(InputAt(0)->GetType())) << InputAt(0)->GetType(); 3581 DCHECK_NE(GetBias(), ComparisonBias::kNoBias); 3582 // Handle the bias. 3583 return std::isunordered(x, y) ? (IsGtBias() ? 1 : -1) : Compute(x, y); 3584 } 3585 3586 HConstant* Evaluate(HIntConstant* x, HIntConstant* y) const OVERRIDE { 3587 // Note that there is no "cmp-int" Dex instruction so we shouldn't 3588 // reach this code path when processing a freshly built HIR 3589 // graph. However HCompare integer instructions can be synthesized 3590 // by the instruction simplifier to implement IntegerCompare and 3591 // IntegerSignum intrinsics, so we have to handle this case. 3592 return MakeConstantComparison(Compute(x->GetValue(), y->GetValue()), GetDexPc()); 3593 } 3594 HConstant* Evaluate(HLongConstant* x, HLongConstant* y) const OVERRIDE { 3595 return MakeConstantComparison(Compute(x->GetValue(), y->GetValue()), GetDexPc()); 3596 } 3597 HConstant* Evaluate(HFloatConstant* x, HFloatConstant* y) const OVERRIDE { 3598 return MakeConstantComparison(ComputeFP(x->GetValue(), y->GetValue()), GetDexPc()); 3599 } 3600 HConstant* Evaluate(HDoubleConstant* x, HDoubleConstant* y) const OVERRIDE { 3601 return MakeConstantComparison(ComputeFP(x->GetValue(), y->GetValue()), GetDexPc()); 3602 } 3603 3604 bool InstructionDataEquals(const HInstruction* other) const OVERRIDE { 3605 return GetPackedFields() == other->AsCompare()->GetPackedFields(); 3606 } 3607 3608 ComparisonBias GetBias() const { return GetPackedField<ComparisonBiasField>(); } 3609 3610 // Does this compare instruction have a "gt bias" (vs an "lt bias")? 3611 // Only meaningful for floating-point comparisons. 3612 bool IsGtBias() const { 3613 DCHECK(Primitive::IsFloatingPointType(InputAt(0)->GetType())) << InputAt(0)->GetType(); 3614 return GetBias() == ComparisonBias::kGtBias; 3615 } 3616 3617 static SideEffects SideEffectsForArchRuntimeCalls(Primitive::Type type ATTRIBUTE_UNUSED) { 3618 // Comparisons do not require a runtime call in any back end. 3619 return SideEffects::None(); 3620 } 3621 3622 DECLARE_INSTRUCTION(Compare); 3623 3624 protected: 3625 static constexpr size_t kFieldComparisonBias = kNumberOfExpressionPackedBits; 3626 static constexpr size_t kFieldComparisonBiasSize = 3627 MinimumBitsToStore(static_cast<size_t>(ComparisonBias::kLast)); 3628 static constexpr size_t kNumberOfComparePackedBits = 3629 kFieldComparisonBias + kFieldComparisonBiasSize; 3630 static_assert(kNumberOfComparePackedBits <= kMaxNumberOfPackedBits, "Too many packed fields."); 3631 using ComparisonBiasField = 3632 BitField<ComparisonBias, kFieldComparisonBias, kFieldComparisonBiasSize>; 3633 3634 // Return an integer constant containing the result of a comparison evaluated at compile time. 3635 HIntConstant* MakeConstantComparison(int32_t value, uint32_t dex_pc) const { 3636 DCHECK(value == -1 || value == 0 || value == 1) << value; 3637 return GetBlock()->GetGraph()->GetIntConstant(value, dex_pc); 3638 } 3639 3640 private: 3641 DISALLOW_COPY_AND_ASSIGN(HCompare); 3642}; 3643 3644class HNewInstance FINAL : public HExpression<2> { 3645 public: 3646 HNewInstance(HInstruction* cls, 3647 HCurrentMethod* current_method, 3648 uint32_t dex_pc, 3649 uint16_t type_index, 3650 const DexFile& dex_file, 3651 bool needs_access_check, 3652 bool finalizable, 3653 QuickEntrypointEnum entrypoint) 3654 : HExpression(Primitive::kPrimNot, SideEffects::CanTriggerGC(), dex_pc), 3655 type_index_(type_index), 3656 dex_file_(dex_file), 3657 entrypoint_(entrypoint) { 3658 SetPackedFlag<kFlagNeedsAccessCheck>(needs_access_check); 3659 SetPackedFlag<kFlagFinalizable>(finalizable); 3660 SetRawInputAt(0, cls); 3661 SetRawInputAt(1, current_method); 3662 } 3663 3664 uint16_t GetTypeIndex() const { return type_index_; } 3665 const DexFile& GetDexFile() const { return dex_file_; } 3666 3667 // Calls runtime so needs an environment. 3668 bool NeedsEnvironment() const OVERRIDE { return true; } 3669 3670 // Can throw errors when out-of-memory or if it's not instantiable/accessible. 3671 bool CanThrow() const OVERRIDE { return true; } 3672 3673 // Needs to call into runtime to make sure it's instantiable/accessible. 3674 bool NeedsAccessCheck() const { return GetPackedFlag<kFlagNeedsAccessCheck>(); } 3675 3676 bool IsFinalizable() const { return GetPackedFlag<kFlagFinalizable>(); } 3677 3678 bool CanBeNull() const OVERRIDE { return false; } 3679 3680 QuickEntrypointEnum GetEntrypoint() const { return entrypoint_; } 3681 3682 void SetEntrypoint(QuickEntrypointEnum entrypoint) { 3683 entrypoint_ = entrypoint; 3684 } 3685 3686 bool IsStringAlloc() const; 3687 3688 DECLARE_INSTRUCTION(NewInstance); 3689 3690 private: 3691 static constexpr size_t kFlagNeedsAccessCheck = kNumberOfExpressionPackedBits; 3692 static constexpr size_t kFlagFinalizable = kFlagNeedsAccessCheck + 1; 3693 static constexpr size_t kNumberOfNewInstancePackedBits = kFlagFinalizable + 1; 3694 static_assert(kNumberOfNewInstancePackedBits <= kMaxNumberOfPackedBits, 3695 "Too many packed fields."); 3696 3697 const uint16_t type_index_; 3698 const DexFile& dex_file_; 3699 QuickEntrypointEnum entrypoint_; 3700 3701 DISALLOW_COPY_AND_ASSIGN(HNewInstance); 3702}; 3703 3704enum IntrinsicNeedsEnvironmentOrCache { 3705 kNoEnvironmentOrCache, // Intrinsic does not require an environment or dex cache. 3706 kNeedsEnvironmentOrCache // Intrinsic requires an environment or requires a dex cache. 3707}; 3708 3709enum IntrinsicSideEffects { 3710 kNoSideEffects, // Intrinsic does not have any heap memory side effects. 3711 kReadSideEffects, // Intrinsic may read heap memory. 3712 kWriteSideEffects, // Intrinsic may write heap memory. 3713 kAllSideEffects // Intrinsic may read or write heap memory, or trigger GC. 3714}; 3715 3716enum IntrinsicExceptions { 3717 kNoThrow, // Intrinsic does not throw any exceptions. 3718 kCanThrow // Intrinsic may throw exceptions. 3719}; 3720 3721class HInvoke : public HInstruction { 3722 public: 3723 bool NeedsEnvironment() const OVERRIDE; 3724 3725 using HInstruction::GetInputRecords; // Keep the const version visible. 3726 ArrayRef<HUserRecord<HInstruction*>> GetInputRecords() OVERRIDE { 3727 return ArrayRef<HUserRecord<HInstruction*>>(inputs_); 3728 } 3729 3730 void SetArgumentAt(size_t index, HInstruction* argument) { 3731 SetRawInputAt(index, argument); 3732 } 3733 3734 // Return the number of arguments. This number can be lower than 3735 // the number of inputs returned by InputCount(), as some invoke 3736 // instructions (e.g. HInvokeStaticOrDirect) can have non-argument 3737 // inputs at the end of their list of inputs. 3738 uint32_t GetNumberOfArguments() const { return number_of_arguments_; } 3739 3740 Primitive::Type GetType() const OVERRIDE { return GetPackedField<ReturnTypeField>(); } 3741 3742 uint32_t GetDexMethodIndex() const { return dex_method_index_; } 3743 const DexFile& GetDexFile() const { return GetEnvironment()->GetDexFile(); } 3744 3745 InvokeType GetInvokeType() const { 3746 return GetPackedField<InvokeTypeField>(); 3747 } 3748 3749 Intrinsics GetIntrinsic() const { 3750 return intrinsic_; 3751 } 3752 3753 void SetIntrinsic(Intrinsics intrinsic, 3754 IntrinsicNeedsEnvironmentOrCache needs_env_or_cache, 3755 IntrinsicSideEffects side_effects, 3756 IntrinsicExceptions exceptions); 3757 3758 bool IsFromInlinedInvoke() const { 3759 return GetEnvironment()->IsFromInlinedInvoke(); 3760 } 3761 3762 bool CanThrow() const OVERRIDE { return GetPackedFlag<kFlagCanThrow>(); } 3763 3764 bool CanBeMoved() const OVERRIDE { return IsIntrinsic(); } 3765 3766 bool InstructionDataEquals(const HInstruction* other) const OVERRIDE { 3767 return intrinsic_ != Intrinsics::kNone && intrinsic_ == other->AsInvoke()->intrinsic_; 3768 } 3769 3770 uint32_t* GetIntrinsicOptimizations() { 3771 return &intrinsic_optimizations_; 3772 } 3773 3774 const uint32_t* GetIntrinsicOptimizations() const { 3775 return &intrinsic_optimizations_; 3776 } 3777 3778 bool IsIntrinsic() const { return intrinsic_ != Intrinsics::kNone; } 3779 3780 ArtMethod* GetResolvedMethod() const { return resolved_method_; } 3781 3782 DECLARE_ABSTRACT_INSTRUCTION(Invoke); 3783 3784 protected: 3785 static constexpr size_t kFieldInvokeType = kNumberOfGenericPackedBits; 3786 static constexpr size_t kFieldInvokeTypeSize = 3787 MinimumBitsToStore(static_cast<size_t>(kMaxInvokeType)); 3788 static constexpr size_t kFieldReturnType = 3789 kFieldInvokeType + kFieldInvokeTypeSize; 3790 static constexpr size_t kFieldReturnTypeSize = 3791 MinimumBitsToStore(static_cast<size_t>(Primitive::kPrimLast)); 3792 static constexpr size_t kFlagCanThrow = kFieldReturnType + kFieldReturnTypeSize; 3793 static constexpr size_t kNumberOfInvokePackedBits = kFlagCanThrow + 1; 3794 static_assert(kNumberOfInvokePackedBits <= kMaxNumberOfPackedBits, "Too many packed fields."); 3795 using InvokeTypeField = BitField<InvokeType, kFieldInvokeType, kFieldInvokeTypeSize>; 3796 using ReturnTypeField = BitField<Primitive::Type, kFieldReturnType, kFieldReturnTypeSize>; 3797 3798 HInvoke(ArenaAllocator* arena, 3799 uint32_t number_of_arguments, 3800 uint32_t number_of_other_inputs, 3801 Primitive::Type return_type, 3802 uint32_t dex_pc, 3803 uint32_t dex_method_index, 3804 ArtMethod* resolved_method, 3805 InvokeType invoke_type) 3806 : HInstruction( 3807 SideEffects::AllExceptGCDependency(), dex_pc), // Assume write/read on all fields/arrays. 3808 number_of_arguments_(number_of_arguments), 3809 resolved_method_(resolved_method), 3810 inputs_(number_of_arguments + number_of_other_inputs, 3811 arena->Adapter(kArenaAllocInvokeInputs)), 3812 dex_method_index_(dex_method_index), 3813 intrinsic_(Intrinsics::kNone), 3814 intrinsic_optimizations_(0) { 3815 SetPackedField<ReturnTypeField>(return_type); 3816 SetPackedField<InvokeTypeField>(invoke_type); 3817 SetPackedFlag<kFlagCanThrow>(true); 3818 } 3819 3820 void SetCanThrow(bool can_throw) { SetPackedFlag<kFlagCanThrow>(can_throw); } 3821 3822 uint32_t number_of_arguments_; 3823 ArtMethod* const resolved_method_; 3824 ArenaVector<HUserRecord<HInstruction*>> inputs_; 3825 const uint32_t dex_method_index_; 3826 Intrinsics intrinsic_; 3827 3828 // A magic word holding optimizations for intrinsics. See intrinsics.h. 3829 uint32_t intrinsic_optimizations_; 3830 3831 private: 3832 DISALLOW_COPY_AND_ASSIGN(HInvoke); 3833}; 3834 3835class HInvokeUnresolved FINAL : public HInvoke { 3836 public: 3837 HInvokeUnresolved(ArenaAllocator* arena, 3838 uint32_t number_of_arguments, 3839 Primitive::Type return_type, 3840 uint32_t dex_pc, 3841 uint32_t dex_method_index, 3842 InvokeType invoke_type) 3843 : HInvoke(arena, 3844 number_of_arguments, 3845 0u /* number_of_other_inputs */, 3846 return_type, 3847 dex_pc, 3848 dex_method_index, 3849 nullptr, 3850 invoke_type) { 3851 } 3852 3853 DECLARE_INSTRUCTION(InvokeUnresolved); 3854 3855 private: 3856 DISALLOW_COPY_AND_ASSIGN(HInvokeUnresolved); 3857}; 3858 3859class HInvokeStaticOrDirect FINAL : public HInvoke { 3860 public: 3861 // Requirements of this method call regarding the class 3862 // initialization (clinit) check of its declaring class. 3863 enum class ClinitCheckRequirement { 3864 kNone, // Class already initialized. 3865 kExplicit, // Static call having explicit clinit check as last input. 3866 kImplicit, // Static call implicitly requiring a clinit check. 3867 kLast = kImplicit 3868 }; 3869 3870 // Determines how to load the target ArtMethod*. 3871 enum class MethodLoadKind { 3872 // Use a String init ArtMethod* loaded from Thread entrypoints. 3873 kStringInit, 3874 3875 // Use the method's own ArtMethod* loaded by the register allocator. 3876 kRecursive, 3877 3878 // Use ArtMethod* at a known address, embed the direct address in the code. 3879 // Used for app->boot calls with non-relocatable image and for JIT-compiled calls. 3880 kDirectAddress, 3881 3882 // Use ArtMethod* at an address that will be known at link time, embed the direct 3883 // address in the code. If the image is relocatable, emit .patch_oat entry. 3884 // Used for app->boot calls with relocatable image and boot->boot calls, whether 3885 // the image relocatable or not. 3886 kDirectAddressWithFixup, 3887 3888 // Load from resolved methods array in the dex cache using a PC-relative load. 3889 // Used when we need to use the dex cache, for example for invoke-static that 3890 // may cause class initialization (the entry may point to a resolution method), 3891 // and we know that we can access the dex cache arrays using a PC-relative load. 3892 kDexCachePcRelative, 3893 3894 // Use ArtMethod* from the resolved methods of the compiled method's own ArtMethod*. 3895 // Used for JIT when we need to use the dex cache. This is also the last-resort-kind 3896 // used when other kinds are unavailable (say, dex cache arrays are not PC-relative) 3897 // or unimplemented or impractical (i.e. slow) on a particular architecture. 3898 kDexCacheViaMethod, 3899 }; 3900 3901 // Determines the location of the code pointer. 3902 enum class CodePtrLocation { 3903 // Recursive call, use local PC-relative call instruction. 3904 kCallSelf, 3905 3906 // Use PC-relative call instruction patched at link time. 3907 // Used for calls within an oat file, boot->boot or app->app. 3908 kCallPCRelative, 3909 3910 // Call to a known target address, embed the direct address in code. 3911 // Used for app->boot call with non-relocatable image and for JIT-compiled calls. 3912 kCallDirect, 3913 3914 // Call to a target address that will be known at link time, embed the direct 3915 // address in code. If the image is relocatable, emit .patch_oat entry. 3916 // Used for app->boot calls with relocatable image and boot->boot calls, whether 3917 // the image relocatable or not. 3918 kCallDirectWithFixup, 3919 3920 // Use code pointer from the ArtMethod*. 3921 // Used when we don't know the target code. This is also the last-resort-kind used when 3922 // other kinds are unimplemented or impractical (i.e. slow) on a particular architecture. 3923 kCallArtMethod, 3924 }; 3925 3926 struct DispatchInfo { 3927 MethodLoadKind method_load_kind; 3928 CodePtrLocation code_ptr_location; 3929 // The method load data holds 3930 // - thread entrypoint offset for kStringInit method if this is a string init invoke. 3931 // Note that there are multiple string init methods, each having its own offset. 3932 // - the method address for kDirectAddress 3933 // - the dex cache arrays offset for kDexCachePcRel. 3934 uint64_t method_load_data; 3935 uint64_t direct_code_ptr; 3936 }; 3937 3938 HInvokeStaticOrDirect(ArenaAllocator* arena, 3939 uint32_t number_of_arguments, 3940 Primitive::Type return_type, 3941 uint32_t dex_pc, 3942 uint32_t method_index, 3943 ArtMethod* resolved_method, 3944 DispatchInfo dispatch_info, 3945 InvokeType invoke_type, 3946 MethodReference target_method, 3947 ClinitCheckRequirement clinit_check_requirement) 3948 : HInvoke(arena, 3949 number_of_arguments, 3950 // There is potentially one extra argument for the HCurrentMethod node, and 3951 // potentially one other if the clinit check is explicit, and potentially 3952 // one other if the method is a string factory. 3953 (NeedsCurrentMethodInput(dispatch_info.method_load_kind) ? 1u : 0u) + 3954 (clinit_check_requirement == ClinitCheckRequirement::kExplicit ? 1u : 0u), 3955 return_type, 3956 dex_pc, 3957 method_index, 3958 resolved_method, 3959 invoke_type), 3960 target_method_(target_method), 3961 dispatch_info_(dispatch_info) { 3962 SetPackedField<ClinitCheckRequirementField>(clinit_check_requirement); 3963 } 3964 3965 void SetDispatchInfo(const DispatchInfo& dispatch_info) { 3966 bool had_current_method_input = HasCurrentMethodInput(); 3967 bool needs_current_method_input = NeedsCurrentMethodInput(dispatch_info.method_load_kind); 3968 3969 // Using the current method is the default and once we find a better 3970 // method load kind, we should not go back to using the current method. 3971 DCHECK(had_current_method_input || !needs_current_method_input); 3972 3973 if (had_current_method_input && !needs_current_method_input) { 3974 DCHECK_EQ(InputAt(GetSpecialInputIndex()), GetBlock()->GetGraph()->GetCurrentMethod()); 3975 RemoveInputAt(GetSpecialInputIndex()); 3976 } 3977 dispatch_info_ = dispatch_info; 3978 } 3979 3980 void AddSpecialInput(HInstruction* input) { 3981 // We allow only one special input. 3982 DCHECK(!IsStringInit() && !HasCurrentMethodInput()); 3983 DCHECK(InputCount() == GetSpecialInputIndex() || 3984 (InputCount() == GetSpecialInputIndex() + 1 && IsStaticWithExplicitClinitCheck())); 3985 InsertInputAt(GetSpecialInputIndex(), input); 3986 } 3987 3988 using HInstruction::GetInputRecords; // Keep the const version visible. 3989 ArrayRef<HUserRecord<HInstruction*>> GetInputRecords() OVERRIDE { 3990 ArrayRef<HUserRecord<HInstruction*>> input_records = HInvoke::GetInputRecords(); 3991 if (kIsDebugBuild && IsStaticWithExplicitClinitCheck()) { 3992 DCHECK(!input_records.empty()); 3993 DCHECK_GT(input_records.size(), GetNumberOfArguments()); 3994 HInstruction* last_input = input_records.back().GetInstruction(); 3995 // Note: `last_input` may be null during arguments setup. 3996 if (last_input != nullptr) { 3997 // `last_input` is the last input of a static invoke marked as having 3998 // an explicit clinit check. It must either be: 3999 // - an art::HClinitCheck instruction, set by art::HGraphBuilder; or 4000 // - an art::HLoadClass instruction, set by art::PrepareForRegisterAllocation. 4001 DCHECK(last_input->IsClinitCheck() || last_input->IsLoadClass()) << last_input->DebugName(); 4002 } 4003 } 4004 return input_records; 4005 } 4006 4007 bool CanDoImplicitNullCheckOn(HInstruction* obj ATTRIBUTE_UNUSED) const OVERRIDE { 4008 // We access the method via the dex cache so we can't do an implicit null check. 4009 // TODO: for intrinsics we can generate implicit null checks. 4010 return false; 4011 } 4012 4013 bool CanBeNull() const OVERRIDE { 4014 return GetPackedField<ReturnTypeField>() == Primitive::kPrimNot && !IsStringInit(); 4015 } 4016 4017 // Get the index of the special input, if any. 4018 // 4019 // If the invoke HasCurrentMethodInput(), the "special input" is the current 4020 // method pointer; otherwise there may be one platform-specific special input, 4021 // such as PC-relative addressing base. 4022 uint32_t GetSpecialInputIndex() const { return GetNumberOfArguments(); } 4023 bool HasSpecialInput() const { return GetNumberOfArguments() != InputCount(); } 4024 4025 MethodLoadKind GetMethodLoadKind() const { return dispatch_info_.method_load_kind; } 4026 CodePtrLocation GetCodePtrLocation() const { return dispatch_info_.code_ptr_location; } 4027 bool IsRecursive() const { return GetMethodLoadKind() == MethodLoadKind::kRecursive; } 4028 bool NeedsDexCacheOfDeclaringClass() const OVERRIDE; 4029 bool IsStringInit() const { return GetMethodLoadKind() == MethodLoadKind::kStringInit; } 4030 bool HasMethodAddress() const { return GetMethodLoadKind() == MethodLoadKind::kDirectAddress; } 4031 bool HasPcRelativeDexCache() const { 4032 return GetMethodLoadKind() == MethodLoadKind::kDexCachePcRelative; 4033 } 4034 bool HasCurrentMethodInput() const { 4035 // This function can be called only after the invoke has been fully initialized by the builder. 4036 if (NeedsCurrentMethodInput(GetMethodLoadKind())) { 4037 DCHECK(InputAt(GetSpecialInputIndex())->IsCurrentMethod()); 4038 return true; 4039 } else { 4040 DCHECK(InputCount() == GetSpecialInputIndex() || 4041 !InputAt(GetSpecialInputIndex())->IsCurrentMethod()); 4042 return false; 4043 } 4044 } 4045 bool HasDirectCodePtr() const { return GetCodePtrLocation() == CodePtrLocation::kCallDirect; } 4046 4047 QuickEntrypointEnum GetStringInitEntryPoint() const { 4048 DCHECK(IsStringInit()); 4049 return static_cast<QuickEntrypointEnum>(dispatch_info_.method_load_data); 4050 } 4051 4052 uint64_t GetMethodAddress() const { 4053 DCHECK(HasMethodAddress()); 4054 return dispatch_info_.method_load_data; 4055 } 4056 4057 uint32_t GetDexCacheArrayOffset() const { 4058 DCHECK(HasPcRelativeDexCache()); 4059 return dispatch_info_.method_load_data; 4060 } 4061 4062 uint64_t GetDirectCodePtr() const { 4063 DCHECK(HasDirectCodePtr()); 4064 return dispatch_info_.direct_code_ptr; 4065 } 4066 4067 ClinitCheckRequirement GetClinitCheckRequirement() const { 4068 return GetPackedField<ClinitCheckRequirementField>(); 4069 } 4070 4071 // Is this instruction a call to a static method? 4072 bool IsStatic() const { 4073 return GetInvokeType() == kStatic; 4074 } 4075 4076 MethodReference GetTargetMethod() const { 4077 return target_method_; 4078 } 4079 4080 // Remove the HClinitCheck or the replacement HLoadClass (set as last input by 4081 // PrepareForRegisterAllocation::VisitClinitCheck() in lieu of the initial HClinitCheck) 4082 // instruction; only relevant for static calls with explicit clinit check. 4083 void RemoveExplicitClinitCheck(ClinitCheckRequirement new_requirement) { 4084 DCHECK(IsStaticWithExplicitClinitCheck()); 4085 size_t last_input_index = inputs_.size() - 1u; 4086 HInstruction* last_input = inputs_.back().GetInstruction(); 4087 DCHECK(last_input != nullptr); 4088 DCHECK(last_input->IsLoadClass() || last_input->IsClinitCheck()) << last_input->DebugName(); 4089 RemoveAsUserOfInput(last_input_index); 4090 inputs_.pop_back(); 4091 SetPackedField<ClinitCheckRequirementField>(new_requirement); 4092 DCHECK(!IsStaticWithExplicitClinitCheck()); 4093 } 4094 4095 // Is this a call to a static method whose declaring class has an 4096 // explicit initialization check in the graph? 4097 bool IsStaticWithExplicitClinitCheck() const { 4098 return IsStatic() && (GetClinitCheckRequirement() == ClinitCheckRequirement::kExplicit); 4099 } 4100 4101 // Is this a call to a static method whose declaring class has an 4102 // implicit intialization check requirement? 4103 bool IsStaticWithImplicitClinitCheck() const { 4104 return IsStatic() && (GetClinitCheckRequirement() == ClinitCheckRequirement::kImplicit); 4105 } 4106 4107 // Does this method load kind need the current method as an input? 4108 static bool NeedsCurrentMethodInput(MethodLoadKind kind) { 4109 return kind == MethodLoadKind::kRecursive || kind == MethodLoadKind::kDexCacheViaMethod; 4110 } 4111 4112 DECLARE_INSTRUCTION(InvokeStaticOrDirect); 4113 4114 protected: 4115 void InsertInputAt(size_t index, HInstruction* input); 4116 void RemoveInputAt(size_t index); 4117 4118 private: 4119 static constexpr size_t kFieldClinitCheckRequirement = kNumberOfInvokePackedBits; 4120 static constexpr size_t kFieldClinitCheckRequirementSize = 4121 MinimumBitsToStore(static_cast<size_t>(ClinitCheckRequirement::kLast)); 4122 static constexpr size_t kNumberOfInvokeStaticOrDirectPackedBits = 4123 kFieldClinitCheckRequirement + kFieldClinitCheckRequirementSize; 4124 static_assert(kNumberOfInvokeStaticOrDirectPackedBits <= kMaxNumberOfPackedBits, 4125 "Too many packed fields."); 4126 using ClinitCheckRequirementField = BitField<ClinitCheckRequirement, 4127 kFieldClinitCheckRequirement, 4128 kFieldClinitCheckRequirementSize>; 4129 4130 // Cached values of the resolved method, to avoid needing the mutator lock. 4131 MethodReference target_method_; 4132 DispatchInfo dispatch_info_; 4133 4134 DISALLOW_COPY_AND_ASSIGN(HInvokeStaticOrDirect); 4135}; 4136std::ostream& operator<<(std::ostream& os, HInvokeStaticOrDirect::MethodLoadKind rhs); 4137std::ostream& operator<<(std::ostream& os, HInvokeStaticOrDirect::ClinitCheckRequirement rhs); 4138 4139class HInvokeVirtual FINAL : public HInvoke { 4140 public: 4141 HInvokeVirtual(ArenaAllocator* arena, 4142 uint32_t number_of_arguments, 4143 Primitive::Type return_type, 4144 uint32_t dex_pc, 4145 uint32_t dex_method_index, 4146 ArtMethod* resolved_method, 4147 uint32_t vtable_index) 4148 : HInvoke(arena, 4149 number_of_arguments, 4150 0u, 4151 return_type, 4152 dex_pc, 4153 dex_method_index, 4154 resolved_method, 4155 kVirtual), 4156 vtable_index_(vtable_index) {} 4157 4158 bool CanDoImplicitNullCheckOn(HInstruction* obj) const OVERRIDE { 4159 // TODO: Add implicit null checks in intrinsics. 4160 return (obj == InputAt(0)) && !GetLocations()->Intrinsified(); 4161 } 4162 4163 uint32_t GetVTableIndex() const { return vtable_index_; } 4164 4165 DECLARE_INSTRUCTION(InvokeVirtual); 4166 4167 private: 4168 // Cached value of the resolved method, to avoid needing the mutator lock. 4169 const uint32_t vtable_index_; 4170 4171 DISALLOW_COPY_AND_ASSIGN(HInvokeVirtual); 4172}; 4173 4174class HInvokeInterface FINAL : public HInvoke { 4175 public: 4176 HInvokeInterface(ArenaAllocator* arena, 4177 uint32_t number_of_arguments, 4178 Primitive::Type return_type, 4179 uint32_t dex_pc, 4180 uint32_t dex_method_index, 4181 ArtMethod* resolved_method, 4182 uint32_t imt_index) 4183 : HInvoke(arena, 4184 number_of_arguments, 4185 0u, 4186 return_type, 4187 dex_pc, 4188 dex_method_index, 4189 resolved_method, 4190 kInterface), 4191 imt_index_(imt_index) {} 4192 4193 bool CanDoImplicitNullCheckOn(HInstruction* obj) const OVERRIDE { 4194 // TODO: Add implicit null checks in intrinsics. 4195 return (obj == InputAt(0)) && !GetLocations()->Intrinsified(); 4196 } 4197 4198 uint32_t GetImtIndex() const { return imt_index_; } 4199 uint32_t GetDexMethodIndex() const { return dex_method_index_; } 4200 4201 DECLARE_INSTRUCTION(InvokeInterface); 4202 4203 private: 4204 // Cached value of the resolved method, to avoid needing the mutator lock. 4205 const uint32_t imt_index_; 4206 4207 DISALLOW_COPY_AND_ASSIGN(HInvokeInterface); 4208}; 4209 4210class HNeg FINAL : public HUnaryOperation { 4211 public: 4212 HNeg(Primitive::Type result_type, HInstruction* input, uint32_t dex_pc = kNoDexPc) 4213 : HUnaryOperation(result_type, input, dex_pc) { 4214 DCHECK_EQ(result_type, Primitive::PrimitiveKind(input->GetType())); 4215 } 4216 4217 template <typename T> static T Compute(T x) { return -x; } 4218 4219 HConstant* Evaluate(HIntConstant* x) const OVERRIDE { 4220 return GetBlock()->GetGraph()->GetIntConstant(Compute(x->GetValue()), GetDexPc()); 4221 } 4222 HConstant* Evaluate(HLongConstant* x) const OVERRIDE { 4223 return GetBlock()->GetGraph()->GetLongConstant(Compute(x->GetValue()), GetDexPc()); 4224 } 4225 HConstant* Evaluate(HFloatConstant* x) const OVERRIDE { 4226 return GetBlock()->GetGraph()->GetFloatConstant(Compute(x->GetValue()), GetDexPc()); 4227 } 4228 HConstant* Evaluate(HDoubleConstant* x) const OVERRIDE { 4229 return GetBlock()->GetGraph()->GetDoubleConstant(Compute(x->GetValue()), GetDexPc()); 4230 } 4231 4232 DECLARE_INSTRUCTION(Neg); 4233 4234 private: 4235 DISALLOW_COPY_AND_ASSIGN(HNeg); 4236}; 4237 4238class HNewArray FINAL : public HExpression<2> { 4239 public: 4240 HNewArray(HInstruction* length, 4241 HCurrentMethod* current_method, 4242 uint32_t dex_pc, 4243 uint16_t type_index, 4244 const DexFile& dex_file, 4245 QuickEntrypointEnum entrypoint) 4246 : HExpression(Primitive::kPrimNot, SideEffects::CanTriggerGC(), dex_pc), 4247 type_index_(type_index), 4248 dex_file_(dex_file), 4249 entrypoint_(entrypoint) { 4250 SetRawInputAt(0, length); 4251 SetRawInputAt(1, current_method); 4252 } 4253 4254 uint16_t GetTypeIndex() const { return type_index_; } 4255 const DexFile& GetDexFile() const { return dex_file_; } 4256 4257 // Calls runtime so needs an environment. 4258 bool NeedsEnvironment() const OVERRIDE { return true; } 4259 4260 // May throw NegativeArraySizeException, OutOfMemoryError, etc. 4261 bool CanThrow() const OVERRIDE { return true; } 4262 4263 bool CanBeNull() const OVERRIDE { return false; } 4264 4265 QuickEntrypointEnum GetEntrypoint() const { return entrypoint_; } 4266 4267 DECLARE_INSTRUCTION(NewArray); 4268 4269 private: 4270 const uint16_t type_index_; 4271 const DexFile& dex_file_; 4272 const QuickEntrypointEnum entrypoint_; 4273 4274 DISALLOW_COPY_AND_ASSIGN(HNewArray); 4275}; 4276 4277class HAdd FINAL : public HBinaryOperation { 4278 public: 4279 HAdd(Primitive::Type result_type, 4280 HInstruction* left, 4281 HInstruction* right, 4282 uint32_t dex_pc = kNoDexPc) 4283 : HBinaryOperation(result_type, left, right, SideEffects::None(), dex_pc) {} 4284 4285 bool IsCommutative() const OVERRIDE { return true; } 4286 4287 template <typename T> static T Compute(T x, T y) { return x + y; } 4288 4289 HConstant* Evaluate(HIntConstant* x, HIntConstant* y) const OVERRIDE { 4290 return GetBlock()->GetGraph()->GetIntConstant( 4291 Compute(x->GetValue(), y->GetValue()), GetDexPc()); 4292 } 4293 HConstant* Evaluate(HLongConstant* x, HLongConstant* y) const OVERRIDE { 4294 return GetBlock()->GetGraph()->GetLongConstant( 4295 Compute(x->GetValue(), y->GetValue()), GetDexPc()); 4296 } 4297 HConstant* Evaluate(HFloatConstant* x, HFloatConstant* y) const OVERRIDE { 4298 return GetBlock()->GetGraph()->GetFloatConstant( 4299 Compute(x->GetValue(), y->GetValue()), GetDexPc()); 4300 } 4301 HConstant* Evaluate(HDoubleConstant* x, HDoubleConstant* y) const OVERRIDE { 4302 return GetBlock()->GetGraph()->GetDoubleConstant( 4303 Compute(x->GetValue(), y->GetValue()), GetDexPc()); 4304 } 4305 4306 DECLARE_INSTRUCTION(Add); 4307 4308 private: 4309 DISALLOW_COPY_AND_ASSIGN(HAdd); 4310}; 4311 4312class HSub FINAL : public HBinaryOperation { 4313 public: 4314 HSub(Primitive::Type result_type, 4315 HInstruction* left, 4316 HInstruction* right, 4317 uint32_t dex_pc = kNoDexPc) 4318 : HBinaryOperation(result_type, left, right, SideEffects::None(), dex_pc) {} 4319 4320 template <typename T> static T Compute(T x, T y) { return x - y; } 4321 4322 HConstant* Evaluate(HIntConstant* x, HIntConstant* y) const OVERRIDE { 4323 return GetBlock()->GetGraph()->GetIntConstant( 4324 Compute(x->GetValue(), y->GetValue()), GetDexPc()); 4325 } 4326 HConstant* Evaluate(HLongConstant* x, HLongConstant* y) const OVERRIDE { 4327 return GetBlock()->GetGraph()->GetLongConstant( 4328 Compute(x->GetValue(), y->GetValue()), GetDexPc()); 4329 } 4330 HConstant* Evaluate(HFloatConstant* x, HFloatConstant* y) const OVERRIDE { 4331 return GetBlock()->GetGraph()->GetFloatConstant( 4332 Compute(x->GetValue(), y->GetValue()), GetDexPc()); 4333 } 4334 HConstant* Evaluate(HDoubleConstant* x, HDoubleConstant* y) const OVERRIDE { 4335 return GetBlock()->GetGraph()->GetDoubleConstant( 4336 Compute(x->GetValue(), y->GetValue()), GetDexPc()); 4337 } 4338 4339 DECLARE_INSTRUCTION(Sub); 4340 4341 private: 4342 DISALLOW_COPY_AND_ASSIGN(HSub); 4343}; 4344 4345class HMul FINAL : public HBinaryOperation { 4346 public: 4347 HMul(Primitive::Type result_type, 4348 HInstruction* left, 4349 HInstruction* right, 4350 uint32_t dex_pc = kNoDexPc) 4351 : HBinaryOperation(result_type, left, right, SideEffects::None(), dex_pc) {} 4352 4353 bool IsCommutative() const OVERRIDE { return true; } 4354 4355 template <typename T> static T Compute(T x, T y) { return x * y; } 4356 4357 HConstant* Evaluate(HIntConstant* x, HIntConstant* y) const OVERRIDE { 4358 return GetBlock()->GetGraph()->GetIntConstant( 4359 Compute(x->GetValue(), y->GetValue()), GetDexPc()); 4360 } 4361 HConstant* Evaluate(HLongConstant* x, HLongConstant* y) const OVERRIDE { 4362 return GetBlock()->GetGraph()->GetLongConstant( 4363 Compute(x->GetValue(), y->GetValue()), GetDexPc()); 4364 } 4365 HConstant* Evaluate(HFloatConstant* x, HFloatConstant* y) const OVERRIDE { 4366 return GetBlock()->GetGraph()->GetFloatConstant( 4367 Compute(x->GetValue(), y->GetValue()), GetDexPc()); 4368 } 4369 HConstant* Evaluate(HDoubleConstant* x, HDoubleConstant* y) const OVERRIDE { 4370 return GetBlock()->GetGraph()->GetDoubleConstant( 4371 Compute(x->GetValue(), y->GetValue()), GetDexPc()); 4372 } 4373 4374 DECLARE_INSTRUCTION(Mul); 4375 4376 private: 4377 DISALLOW_COPY_AND_ASSIGN(HMul); 4378}; 4379 4380class HDiv FINAL : public HBinaryOperation { 4381 public: 4382 HDiv(Primitive::Type result_type, 4383 HInstruction* left, 4384 HInstruction* right, 4385 uint32_t dex_pc) 4386 : HBinaryOperation(result_type, left, right, SideEffects::None(), dex_pc) {} 4387 4388 template <typename T> 4389 T ComputeIntegral(T x, T y) const { 4390 DCHECK(!Primitive::IsFloatingPointType(GetType())) << GetType(); 4391 // Our graph structure ensures we never have 0 for `y` during 4392 // constant folding. 4393 DCHECK_NE(y, 0); 4394 // Special case -1 to avoid getting a SIGFPE on x86(_64). 4395 return (y == -1) ? -x : x / y; 4396 } 4397 4398 template <typename T> 4399 T ComputeFP(T x, T y) const { 4400 DCHECK(Primitive::IsFloatingPointType(GetType())) << GetType(); 4401 return x / y; 4402 } 4403 4404 HConstant* Evaluate(HIntConstant* x, HIntConstant* y) const OVERRIDE { 4405 return GetBlock()->GetGraph()->GetIntConstant( 4406 ComputeIntegral(x->GetValue(), y->GetValue()), GetDexPc()); 4407 } 4408 HConstant* Evaluate(HLongConstant* x, HLongConstant* y) const OVERRIDE { 4409 return GetBlock()->GetGraph()->GetLongConstant( 4410 ComputeIntegral(x->GetValue(), y->GetValue()), GetDexPc()); 4411 } 4412 HConstant* Evaluate(HFloatConstant* x, HFloatConstant* y) const OVERRIDE { 4413 return GetBlock()->GetGraph()->GetFloatConstant( 4414 ComputeFP(x->GetValue(), y->GetValue()), GetDexPc()); 4415 } 4416 HConstant* Evaluate(HDoubleConstant* x, HDoubleConstant* y) const OVERRIDE { 4417 return GetBlock()->GetGraph()->GetDoubleConstant( 4418 ComputeFP(x->GetValue(), y->GetValue()), GetDexPc()); 4419 } 4420 4421 DECLARE_INSTRUCTION(Div); 4422 4423 private: 4424 DISALLOW_COPY_AND_ASSIGN(HDiv); 4425}; 4426 4427class HRem FINAL : public HBinaryOperation { 4428 public: 4429 HRem(Primitive::Type result_type, 4430 HInstruction* left, 4431 HInstruction* right, 4432 uint32_t dex_pc) 4433 : HBinaryOperation(result_type, left, right, SideEffects::None(), dex_pc) {} 4434 4435 template <typename T> 4436 T ComputeIntegral(T x, T y) const { 4437 DCHECK(!Primitive::IsFloatingPointType(GetType())) << GetType(); 4438 // Our graph structure ensures we never have 0 for `y` during 4439 // constant folding. 4440 DCHECK_NE(y, 0); 4441 // Special case -1 to avoid getting a SIGFPE on x86(_64). 4442 return (y == -1) ? 0 : x % y; 4443 } 4444 4445 template <typename T> 4446 T ComputeFP(T x, T y) const { 4447 DCHECK(Primitive::IsFloatingPointType(GetType())) << GetType(); 4448 return std::fmod(x, y); 4449 } 4450 4451 HConstant* Evaluate(HIntConstant* x, HIntConstant* y) const OVERRIDE { 4452 return GetBlock()->GetGraph()->GetIntConstant( 4453 ComputeIntegral(x->GetValue(), y->GetValue()), GetDexPc()); 4454 } 4455 HConstant* Evaluate(HLongConstant* x, HLongConstant* y) const OVERRIDE { 4456 return GetBlock()->GetGraph()->GetLongConstant( 4457 ComputeIntegral(x->GetValue(), y->GetValue()), GetDexPc()); 4458 } 4459 HConstant* Evaluate(HFloatConstant* x, HFloatConstant* y) const OVERRIDE { 4460 return GetBlock()->GetGraph()->GetFloatConstant( 4461 ComputeFP(x->GetValue(), y->GetValue()), GetDexPc()); 4462 } 4463 HConstant* Evaluate(HDoubleConstant* x, HDoubleConstant* y) const OVERRIDE { 4464 return GetBlock()->GetGraph()->GetDoubleConstant( 4465 ComputeFP(x->GetValue(), y->GetValue()), GetDexPc()); 4466 } 4467 4468 DECLARE_INSTRUCTION(Rem); 4469 4470 private: 4471 DISALLOW_COPY_AND_ASSIGN(HRem); 4472}; 4473 4474class HDivZeroCheck FINAL : public HExpression<1> { 4475 public: 4476 // `HDivZeroCheck` can trigger GC, as it may call the `ArithmeticException` 4477 // constructor. 4478 HDivZeroCheck(HInstruction* value, uint32_t dex_pc) 4479 : HExpression(value->GetType(), SideEffects::CanTriggerGC(), dex_pc) { 4480 SetRawInputAt(0, value); 4481 } 4482 4483 Primitive::Type GetType() const OVERRIDE { return InputAt(0)->GetType(); } 4484 4485 bool CanBeMoved() const OVERRIDE { return true; } 4486 4487 bool InstructionDataEquals(const HInstruction* other ATTRIBUTE_UNUSED) const OVERRIDE { 4488 return true; 4489 } 4490 4491 bool NeedsEnvironment() const OVERRIDE { return true; } 4492 bool CanThrow() const OVERRIDE { return true; } 4493 4494 DECLARE_INSTRUCTION(DivZeroCheck); 4495 4496 private: 4497 DISALLOW_COPY_AND_ASSIGN(HDivZeroCheck); 4498}; 4499 4500class HShl FINAL : public HBinaryOperation { 4501 public: 4502 HShl(Primitive::Type result_type, 4503 HInstruction* value, 4504 HInstruction* distance, 4505 uint32_t dex_pc = kNoDexPc) 4506 : HBinaryOperation(result_type, value, distance, SideEffects::None(), dex_pc) { 4507 DCHECK_EQ(result_type, Primitive::PrimitiveKind(value->GetType())); 4508 DCHECK_EQ(Primitive::kPrimInt, Primitive::PrimitiveKind(distance->GetType())); 4509 } 4510 4511 template <typename T> 4512 static T Compute(T value, int32_t distance, int32_t max_shift_distance) { 4513 return value << (distance & max_shift_distance); 4514 } 4515 4516 HConstant* Evaluate(HIntConstant* value, HIntConstant* distance) const OVERRIDE { 4517 return GetBlock()->GetGraph()->GetIntConstant( 4518 Compute(value->GetValue(), distance->GetValue(), kMaxIntShiftDistance), GetDexPc()); 4519 } 4520 HConstant* Evaluate(HLongConstant* value, HIntConstant* distance) const OVERRIDE { 4521 return GetBlock()->GetGraph()->GetLongConstant( 4522 Compute(value->GetValue(), distance->GetValue(), kMaxLongShiftDistance), GetDexPc()); 4523 } 4524 HConstant* Evaluate(HLongConstant* value ATTRIBUTE_UNUSED, 4525 HLongConstant* distance ATTRIBUTE_UNUSED) const OVERRIDE { 4526 LOG(FATAL) << DebugName() << " is not defined for the (long, long) case."; 4527 UNREACHABLE(); 4528 } 4529 HConstant* Evaluate(HFloatConstant* value ATTRIBUTE_UNUSED, 4530 HFloatConstant* distance ATTRIBUTE_UNUSED) const OVERRIDE { 4531 LOG(FATAL) << DebugName() << " is not defined for float values"; 4532 UNREACHABLE(); 4533 } 4534 HConstant* Evaluate(HDoubleConstant* value ATTRIBUTE_UNUSED, 4535 HDoubleConstant* distance ATTRIBUTE_UNUSED) const OVERRIDE { 4536 LOG(FATAL) << DebugName() << " is not defined for double values"; 4537 UNREACHABLE(); 4538 } 4539 4540 DECLARE_INSTRUCTION(Shl); 4541 4542 private: 4543 DISALLOW_COPY_AND_ASSIGN(HShl); 4544}; 4545 4546class HShr FINAL : public HBinaryOperation { 4547 public: 4548 HShr(Primitive::Type result_type, 4549 HInstruction* value, 4550 HInstruction* distance, 4551 uint32_t dex_pc = kNoDexPc) 4552 : HBinaryOperation(result_type, value, distance, SideEffects::None(), dex_pc) { 4553 DCHECK_EQ(result_type, Primitive::PrimitiveKind(value->GetType())); 4554 DCHECK_EQ(Primitive::kPrimInt, Primitive::PrimitiveKind(distance->GetType())); 4555 } 4556 4557 template <typename T> 4558 static T Compute(T value, int32_t distance, int32_t max_shift_distance) { 4559 return value >> (distance & max_shift_distance); 4560 } 4561 4562 HConstant* Evaluate(HIntConstant* value, HIntConstant* distance) const OVERRIDE { 4563 return GetBlock()->GetGraph()->GetIntConstant( 4564 Compute(value->GetValue(), distance->GetValue(), kMaxIntShiftDistance), GetDexPc()); 4565 } 4566 HConstant* Evaluate(HLongConstant* value, HIntConstant* distance) const OVERRIDE { 4567 return GetBlock()->GetGraph()->GetLongConstant( 4568 Compute(value->GetValue(), distance->GetValue(), kMaxLongShiftDistance), GetDexPc()); 4569 } 4570 HConstant* Evaluate(HLongConstant* value ATTRIBUTE_UNUSED, 4571 HLongConstant* distance ATTRIBUTE_UNUSED) const OVERRIDE { 4572 LOG(FATAL) << DebugName() << " is not defined for the (long, long) case."; 4573 UNREACHABLE(); 4574 } 4575 HConstant* Evaluate(HFloatConstant* value ATTRIBUTE_UNUSED, 4576 HFloatConstant* distance ATTRIBUTE_UNUSED) const OVERRIDE { 4577 LOG(FATAL) << DebugName() << " is not defined for float values"; 4578 UNREACHABLE(); 4579 } 4580 HConstant* Evaluate(HDoubleConstant* value ATTRIBUTE_UNUSED, 4581 HDoubleConstant* distance ATTRIBUTE_UNUSED) const OVERRIDE { 4582 LOG(FATAL) << DebugName() << " is not defined for double values"; 4583 UNREACHABLE(); 4584 } 4585 4586 DECLARE_INSTRUCTION(Shr); 4587 4588 private: 4589 DISALLOW_COPY_AND_ASSIGN(HShr); 4590}; 4591 4592class HUShr FINAL : public HBinaryOperation { 4593 public: 4594 HUShr(Primitive::Type result_type, 4595 HInstruction* value, 4596 HInstruction* distance, 4597 uint32_t dex_pc = kNoDexPc) 4598 : HBinaryOperation(result_type, value, distance, SideEffects::None(), dex_pc) { 4599 DCHECK_EQ(result_type, Primitive::PrimitiveKind(value->GetType())); 4600 DCHECK_EQ(Primitive::kPrimInt, Primitive::PrimitiveKind(distance->GetType())); 4601 } 4602 4603 template <typename T> 4604 static T Compute(T value, int32_t distance, int32_t max_shift_distance) { 4605 typedef typename std::make_unsigned<T>::type V; 4606 V ux = static_cast<V>(value); 4607 return static_cast<T>(ux >> (distance & max_shift_distance)); 4608 } 4609 4610 HConstant* Evaluate(HIntConstant* value, HIntConstant* distance) const OVERRIDE { 4611 return GetBlock()->GetGraph()->GetIntConstant( 4612 Compute(value->GetValue(), distance->GetValue(), kMaxIntShiftDistance), GetDexPc()); 4613 } 4614 HConstant* Evaluate(HLongConstant* value, HIntConstant* distance) const OVERRIDE { 4615 return GetBlock()->GetGraph()->GetLongConstant( 4616 Compute(value->GetValue(), distance->GetValue(), kMaxLongShiftDistance), GetDexPc()); 4617 } 4618 HConstant* Evaluate(HLongConstant* value ATTRIBUTE_UNUSED, 4619 HLongConstant* distance ATTRIBUTE_UNUSED) const OVERRIDE { 4620 LOG(FATAL) << DebugName() << " is not defined for the (long, long) case."; 4621 UNREACHABLE(); 4622 } 4623 HConstant* Evaluate(HFloatConstant* value ATTRIBUTE_UNUSED, 4624 HFloatConstant* distance ATTRIBUTE_UNUSED) const OVERRIDE { 4625 LOG(FATAL) << DebugName() << " is not defined for float values"; 4626 UNREACHABLE(); 4627 } 4628 HConstant* Evaluate(HDoubleConstant* value ATTRIBUTE_UNUSED, 4629 HDoubleConstant* distance ATTRIBUTE_UNUSED) const OVERRIDE { 4630 LOG(FATAL) << DebugName() << " is not defined for double values"; 4631 UNREACHABLE(); 4632 } 4633 4634 DECLARE_INSTRUCTION(UShr); 4635 4636 private: 4637 DISALLOW_COPY_AND_ASSIGN(HUShr); 4638}; 4639 4640class HAnd FINAL : public HBinaryOperation { 4641 public: 4642 HAnd(Primitive::Type result_type, 4643 HInstruction* left, 4644 HInstruction* right, 4645 uint32_t dex_pc = kNoDexPc) 4646 : HBinaryOperation(result_type, left, right, SideEffects::None(), dex_pc) {} 4647 4648 bool IsCommutative() const OVERRIDE { return true; } 4649 4650 template <typename T> static T Compute(T x, T y) { return x & y; } 4651 4652 HConstant* Evaluate(HIntConstant* x, HIntConstant* y) const OVERRIDE { 4653 return GetBlock()->GetGraph()->GetIntConstant( 4654 Compute(x->GetValue(), y->GetValue()), GetDexPc()); 4655 } 4656 HConstant* Evaluate(HLongConstant* x, HLongConstant* y) const OVERRIDE { 4657 return GetBlock()->GetGraph()->GetLongConstant( 4658 Compute(x->GetValue(), y->GetValue()), GetDexPc()); 4659 } 4660 HConstant* Evaluate(HFloatConstant* x ATTRIBUTE_UNUSED, 4661 HFloatConstant* y ATTRIBUTE_UNUSED) const OVERRIDE { 4662 LOG(FATAL) << DebugName() << " is not defined for float values"; 4663 UNREACHABLE(); 4664 } 4665 HConstant* Evaluate(HDoubleConstant* x ATTRIBUTE_UNUSED, 4666 HDoubleConstant* y ATTRIBUTE_UNUSED) const OVERRIDE { 4667 LOG(FATAL) << DebugName() << " is not defined for double values"; 4668 UNREACHABLE(); 4669 } 4670 4671 DECLARE_INSTRUCTION(And); 4672 4673 private: 4674 DISALLOW_COPY_AND_ASSIGN(HAnd); 4675}; 4676 4677class HOr FINAL : public HBinaryOperation { 4678 public: 4679 HOr(Primitive::Type result_type, 4680 HInstruction* left, 4681 HInstruction* right, 4682 uint32_t dex_pc = kNoDexPc) 4683 : HBinaryOperation(result_type, left, right, SideEffects::None(), dex_pc) {} 4684 4685 bool IsCommutative() const OVERRIDE { return true; } 4686 4687 template <typename T> static T Compute(T x, T y) { return x | y; } 4688 4689 HConstant* Evaluate(HIntConstant* x, HIntConstant* y) const OVERRIDE { 4690 return GetBlock()->GetGraph()->GetIntConstant( 4691 Compute(x->GetValue(), y->GetValue()), GetDexPc()); 4692 } 4693 HConstant* Evaluate(HLongConstant* x, HLongConstant* y) const OVERRIDE { 4694 return GetBlock()->GetGraph()->GetLongConstant( 4695 Compute(x->GetValue(), y->GetValue()), GetDexPc()); 4696 } 4697 HConstant* Evaluate(HFloatConstant* x ATTRIBUTE_UNUSED, 4698 HFloatConstant* y ATTRIBUTE_UNUSED) const OVERRIDE { 4699 LOG(FATAL) << DebugName() << " is not defined for float values"; 4700 UNREACHABLE(); 4701 } 4702 HConstant* Evaluate(HDoubleConstant* x ATTRIBUTE_UNUSED, 4703 HDoubleConstant* y ATTRIBUTE_UNUSED) const OVERRIDE { 4704 LOG(FATAL) << DebugName() << " is not defined for double values"; 4705 UNREACHABLE(); 4706 } 4707 4708 DECLARE_INSTRUCTION(Or); 4709 4710 private: 4711 DISALLOW_COPY_AND_ASSIGN(HOr); 4712}; 4713 4714class HXor FINAL : public HBinaryOperation { 4715 public: 4716 HXor(Primitive::Type result_type, 4717 HInstruction* left, 4718 HInstruction* right, 4719 uint32_t dex_pc = kNoDexPc) 4720 : HBinaryOperation(result_type, left, right, SideEffects::None(), dex_pc) {} 4721 4722 bool IsCommutative() const OVERRIDE { return true; } 4723 4724 template <typename T> static T Compute(T x, T y) { return x ^ y; } 4725 4726 HConstant* Evaluate(HIntConstant* x, HIntConstant* y) const OVERRIDE { 4727 return GetBlock()->GetGraph()->GetIntConstant( 4728 Compute(x->GetValue(), y->GetValue()), GetDexPc()); 4729 } 4730 HConstant* Evaluate(HLongConstant* x, HLongConstant* y) const OVERRIDE { 4731 return GetBlock()->GetGraph()->GetLongConstant( 4732 Compute(x->GetValue(), y->GetValue()), GetDexPc()); 4733 } 4734 HConstant* Evaluate(HFloatConstant* x ATTRIBUTE_UNUSED, 4735 HFloatConstant* y ATTRIBUTE_UNUSED) const OVERRIDE { 4736 LOG(FATAL) << DebugName() << " is not defined for float values"; 4737 UNREACHABLE(); 4738 } 4739 HConstant* Evaluate(HDoubleConstant* x ATTRIBUTE_UNUSED, 4740 HDoubleConstant* y ATTRIBUTE_UNUSED) const OVERRIDE { 4741 LOG(FATAL) << DebugName() << " is not defined for double values"; 4742 UNREACHABLE(); 4743 } 4744 4745 DECLARE_INSTRUCTION(Xor); 4746 4747 private: 4748 DISALLOW_COPY_AND_ASSIGN(HXor); 4749}; 4750 4751class HRor FINAL : public HBinaryOperation { 4752 public: 4753 HRor(Primitive::Type result_type, HInstruction* value, HInstruction* distance) 4754 : HBinaryOperation(result_type, value, distance) { 4755 DCHECK_EQ(result_type, Primitive::PrimitiveKind(value->GetType())); 4756 DCHECK_EQ(Primitive::kPrimInt, Primitive::PrimitiveKind(distance->GetType())); 4757 } 4758 4759 template <typename T> 4760 static T Compute(T value, int32_t distance, int32_t max_shift_value) { 4761 typedef typename std::make_unsigned<T>::type V; 4762 V ux = static_cast<V>(value); 4763 if ((distance & max_shift_value) == 0) { 4764 return static_cast<T>(ux); 4765 } else { 4766 const V reg_bits = sizeof(T) * 8; 4767 return static_cast<T>(ux >> (distance & max_shift_value)) | 4768 (value << (reg_bits - (distance & max_shift_value))); 4769 } 4770 } 4771 4772 HConstant* Evaluate(HIntConstant* value, HIntConstant* distance) const OVERRIDE { 4773 return GetBlock()->GetGraph()->GetIntConstant( 4774 Compute(value->GetValue(), distance->GetValue(), kMaxIntShiftDistance), GetDexPc()); 4775 } 4776 HConstant* Evaluate(HLongConstant* value, HIntConstant* distance) const OVERRIDE { 4777 return GetBlock()->GetGraph()->GetLongConstant( 4778 Compute(value->GetValue(), distance->GetValue(), kMaxLongShiftDistance), GetDexPc()); 4779 } 4780 HConstant* Evaluate(HLongConstant* value ATTRIBUTE_UNUSED, 4781 HLongConstant* distance ATTRIBUTE_UNUSED) const OVERRIDE { 4782 LOG(FATAL) << DebugName() << " is not defined for the (long, long) case."; 4783 UNREACHABLE(); 4784 } 4785 HConstant* Evaluate(HFloatConstant* value ATTRIBUTE_UNUSED, 4786 HFloatConstant* distance ATTRIBUTE_UNUSED) const OVERRIDE { 4787 LOG(FATAL) << DebugName() << " is not defined for float values"; 4788 UNREACHABLE(); 4789 } 4790 HConstant* Evaluate(HDoubleConstant* value ATTRIBUTE_UNUSED, 4791 HDoubleConstant* distance ATTRIBUTE_UNUSED) const OVERRIDE { 4792 LOG(FATAL) << DebugName() << " is not defined for double values"; 4793 UNREACHABLE(); 4794 } 4795 4796 DECLARE_INSTRUCTION(Ror); 4797 4798 private: 4799 DISALLOW_COPY_AND_ASSIGN(HRor); 4800}; 4801 4802// The value of a parameter in this method. Its location depends on 4803// the calling convention. 4804class HParameterValue FINAL : public HExpression<0> { 4805 public: 4806 HParameterValue(const DexFile& dex_file, 4807 uint16_t type_index, 4808 uint8_t index, 4809 Primitive::Type parameter_type, 4810 bool is_this = false) 4811 : HExpression(parameter_type, SideEffects::None(), kNoDexPc), 4812 dex_file_(dex_file), 4813 type_index_(type_index), 4814 index_(index) { 4815 SetPackedFlag<kFlagIsThis>(is_this); 4816 SetPackedFlag<kFlagCanBeNull>(!is_this); 4817 } 4818 4819 const DexFile& GetDexFile() const { return dex_file_; } 4820 uint16_t GetTypeIndex() const { return type_index_; } 4821 uint8_t GetIndex() const { return index_; } 4822 bool IsThis() const { return GetPackedFlag<kFlagIsThis>(); } 4823 4824 bool CanBeNull() const OVERRIDE { return GetPackedFlag<kFlagCanBeNull>(); } 4825 void SetCanBeNull(bool can_be_null) { SetPackedFlag<kFlagCanBeNull>(can_be_null); } 4826 4827 DECLARE_INSTRUCTION(ParameterValue); 4828 4829 private: 4830 // Whether or not the parameter value corresponds to 'this' argument. 4831 static constexpr size_t kFlagIsThis = kNumberOfExpressionPackedBits; 4832 static constexpr size_t kFlagCanBeNull = kFlagIsThis + 1; 4833 static constexpr size_t kNumberOfParameterValuePackedBits = kFlagCanBeNull + 1; 4834 static_assert(kNumberOfParameterValuePackedBits <= kMaxNumberOfPackedBits, 4835 "Too many packed fields."); 4836 4837 const DexFile& dex_file_; 4838 const uint16_t type_index_; 4839 // The index of this parameter in the parameters list. Must be less 4840 // than HGraph::number_of_in_vregs_. 4841 const uint8_t index_; 4842 4843 DISALLOW_COPY_AND_ASSIGN(HParameterValue); 4844}; 4845 4846class HNot FINAL : public HUnaryOperation { 4847 public: 4848 HNot(Primitive::Type result_type, HInstruction* input, uint32_t dex_pc = kNoDexPc) 4849 : HUnaryOperation(result_type, input, dex_pc) {} 4850 4851 bool CanBeMoved() const OVERRIDE { return true; } 4852 bool InstructionDataEquals(const HInstruction* other ATTRIBUTE_UNUSED) const OVERRIDE { 4853 return true; 4854 } 4855 4856 template <typename T> static T Compute(T x) { return ~x; } 4857 4858 HConstant* Evaluate(HIntConstant* x) const OVERRIDE { 4859 return GetBlock()->GetGraph()->GetIntConstant(Compute(x->GetValue()), GetDexPc()); 4860 } 4861 HConstant* Evaluate(HLongConstant* x) const OVERRIDE { 4862 return GetBlock()->GetGraph()->GetLongConstant(Compute(x->GetValue()), GetDexPc()); 4863 } 4864 HConstant* Evaluate(HFloatConstant* x ATTRIBUTE_UNUSED) const OVERRIDE { 4865 LOG(FATAL) << DebugName() << " is not defined for float values"; 4866 UNREACHABLE(); 4867 } 4868 HConstant* Evaluate(HDoubleConstant* x ATTRIBUTE_UNUSED) const OVERRIDE { 4869 LOG(FATAL) << DebugName() << " is not defined for double values"; 4870 UNREACHABLE(); 4871 } 4872 4873 DECLARE_INSTRUCTION(Not); 4874 4875 private: 4876 DISALLOW_COPY_AND_ASSIGN(HNot); 4877}; 4878 4879class HBooleanNot FINAL : public HUnaryOperation { 4880 public: 4881 explicit HBooleanNot(HInstruction* input, uint32_t dex_pc = kNoDexPc) 4882 : HUnaryOperation(Primitive::Type::kPrimBoolean, input, dex_pc) {} 4883 4884 bool CanBeMoved() const OVERRIDE { return true; } 4885 bool InstructionDataEquals(const HInstruction* other ATTRIBUTE_UNUSED) const OVERRIDE { 4886 return true; 4887 } 4888 4889 template <typename T> static bool Compute(T x) { 4890 DCHECK(IsUint<1>(x)) << x; 4891 return !x; 4892 } 4893 4894 HConstant* Evaluate(HIntConstant* x) const OVERRIDE { 4895 return GetBlock()->GetGraph()->GetIntConstant(Compute(x->GetValue()), GetDexPc()); 4896 } 4897 HConstant* Evaluate(HLongConstant* x ATTRIBUTE_UNUSED) const OVERRIDE { 4898 LOG(FATAL) << DebugName() << " is not defined for long values"; 4899 UNREACHABLE(); 4900 } 4901 HConstant* Evaluate(HFloatConstant* x ATTRIBUTE_UNUSED) const OVERRIDE { 4902 LOG(FATAL) << DebugName() << " is not defined for float values"; 4903 UNREACHABLE(); 4904 } 4905 HConstant* Evaluate(HDoubleConstant* x ATTRIBUTE_UNUSED) const OVERRIDE { 4906 LOG(FATAL) << DebugName() << " is not defined for double values"; 4907 UNREACHABLE(); 4908 } 4909 4910 DECLARE_INSTRUCTION(BooleanNot); 4911 4912 private: 4913 DISALLOW_COPY_AND_ASSIGN(HBooleanNot); 4914}; 4915 4916class HTypeConversion FINAL : public HExpression<1> { 4917 public: 4918 // Instantiate a type conversion of `input` to `result_type`. 4919 HTypeConversion(Primitive::Type result_type, HInstruction* input, uint32_t dex_pc) 4920 : HExpression(result_type, SideEffects::None(), dex_pc) { 4921 SetRawInputAt(0, input); 4922 // Invariant: We should never generate a conversion to a Boolean value. 4923 DCHECK_NE(Primitive::kPrimBoolean, result_type); 4924 } 4925 4926 HInstruction* GetInput() const { return InputAt(0); } 4927 Primitive::Type GetInputType() const { return GetInput()->GetType(); } 4928 Primitive::Type GetResultType() const { return GetType(); } 4929 4930 bool CanBeMoved() const OVERRIDE { return true; } 4931 bool InstructionDataEquals(const HInstruction* other ATTRIBUTE_UNUSED) const OVERRIDE { 4932 return true; 4933 } 4934 4935 // Try to statically evaluate the conversion and return a HConstant 4936 // containing the result. If the input cannot be converted, return nullptr. 4937 HConstant* TryStaticEvaluation() const; 4938 4939 DECLARE_INSTRUCTION(TypeConversion); 4940 4941 private: 4942 DISALLOW_COPY_AND_ASSIGN(HTypeConversion); 4943}; 4944 4945static constexpr uint32_t kNoRegNumber = -1; 4946 4947class HNullCheck FINAL : public HExpression<1> { 4948 public: 4949 // `HNullCheck` can trigger GC, as it may call the `NullPointerException` 4950 // constructor. 4951 HNullCheck(HInstruction* value, uint32_t dex_pc) 4952 : HExpression(value->GetType(), SideEffects::CanTriggerGC(), dex_pc) { 4953 SetRawInputAt(0, value); 4954 } 4955 4956 bool CanBeMoved() const OVERRIDE { return true; } 4957 bool InstructionDataEquals(const HInstruction* other ATTRIBUTE_UNUSED) const OVERRIDE { 4958 return true; 4959 } 4960 4961 bool NeedsEnvironment() const OVERRIDE { return true; } 4962 4963 bool CanThrow() const OVERRIDE { return true; } 4964 4965 bool CanBeNull() const OVERRIDE { return false; } 4966 4967 4968 DECLARE_INSTRUCTION(NullCheck); 4969 4970 private: 4971 DISALLOW_COPY_AND_ASSIGN(HNullCheck); 4972}; 4973 4974class FieldInfo : public ValueObject { 4975 public: 4976 FieldInfo(MemberOffset field_offset, 4977 Primitive::Type field_type, 4978 bool is_volatile, 4979 uint32_t index, 4980 uint16_t declaring_class_def_index, 4981 const DexFile& dex_file, 4982 Handle<mirror::DexCache> dex_cache) 4983 : field_offset_(field_offset), 4984 field_type_(field_type), 4985 is_volatile_(is_volatile), 4986 index_(index), 4987 declaring_class_def_index_(declaring_class_def_index), 4988 dex_file_(dex_file), 4989 dex_cache_(dex_cache) {} 4990 4991 MemberOffset GetFieldOffset() const { return field_offset_; } 4992 Primitive::Type GetFieldType() const { return field_type_; } 4993 uint32_t GetFieldIndex() const { return index_; } 4994 uint16_t GetDeclaringClassDefIndex() const { return declaring_class_def_index_;} 4995 const DexFile& GetDexFile() const { return dex_file_; } 4996 bool IsVolatile() const { return is_volatile_; } 4997 Handle<mirror::DexCache> GetDexCache() const { return dex_cache_; } 4998 4999 private: 5000 const MemberOffset field_offset_; 5001 const Primitive::Type field_type_; 5002 const bool is_volatile_; 5003 const uint32_t index_; 5004 const uint16_t declaring_class_def_index_; 5005 const DexFile& dex_file_; 5006 const Handle<mirror::DexCache> dex_cache_; 5007}; 5008 5009class HInstanceFieldGet FINAL : public HExpression<1> { 5010 public: 5011 HInstanceFieldGet(HInstruction* value, 5012 Primitive::Type field_type, 5013 MemberOffset field_offset, 5014 bool is_volatile, 5015 uint32_t field_idx, 5016 uint16_t declaring_class_def_index, 5017 const DexFile& dex_file, 5018 Handle<mirror::DexCache> dex_cache, 5019 uint32_t dex_pc) 5020 : HExpression(field_type, SideEffects::FieldReadOfType(field_type, is_volatile), dex_pc), 5021 field_info_(field_offset, 5022 field_type, 5023 is_volatile, 5024 field_idx, 5025 declaring_class_def_index, 5026 dex_file, 5027 dex_cache) { 5028 SetRawInputAt(0, value); 5029 } 5030 5031 bool CanBeMoved() const OVERRIDE { return !IsVolatile(); } 5032 5033 bool InstructionDataEquals(const HInstruction* other) const OVERRIDE { 5034 const HInstanceFieldGet* other_get = other->AsInstanceFieldGet(); 5035 return GetFieldOffset().SizeValue() == other_get->GetFieldOffset().SizeValue(); 5036 } 5037 5038 bool CanDoImplicitNullCheckOn(HInstruction* obj) const OVERRIDE { 5039 return (obj == InputAt(0)) && art::CanDoImplicitNullCheckOn(GetFieldOffset().Uint32Value()); 5040 } 5041 5042 size_t ComputeHashCode() const OVERRIDE { 5043 return (HInstruction::ComputeHashCode() << 7) | GetFieldOffset().SizeValue(); 5044 } 5045 5046 const FieldInfo& GetFieldInfo() const { return field_info_; } 5047 MemberOffset GetFieldOffset() const { return field_info_.GetFieldOffset(); } 5048 Primitive::Type GetFieldType() const { return field_info_.GetFieldType(); } 5049 bool IsVolatile() const { return field_info_.IsVolatile(); } 5050 5051 DECLARE_INSTRUCTION(InstanceFieldGet); 5052 5053 private: 5054 const FieldInfo field_info_; 5055 5056 DISALLOW_COPY_AND_ASSIGN(HInstanceFieldGet); 5057}; 5058 5059class HInstanceFieldSet FINAL : public HTemplateInstruction<2> { 5060 public: 5061 HInstanceFieldSet(HInstruction* object, 5062 HInstruction* value, 5063 Primitive::Type field_type, 5064 MemberOffset field_offset, 5065 bool is_volatile, 5066 uint32_t field_idx, 5067 uint16_t declaring_class_def_index, 5068 const DexFile& dex_file, 5069 Handle<mirror::DexCache> dex_cache, 5070 uint32_t dex_pc) 5071 : HTemplateInstruction(SideEffects::FieldWriteOfType(field_type, is_volatile), dex_pc), 5072 field_info_(field_offset, 5073 field_type, 5074 is_volatile, 5075 field_idx, 5076 declaring_class_def_index, 5077 dex_file, 5078 dex_cache) { 5079 SetPackedFlag<kFlagValueCanBeNull>(true); 5080 SetRawInputAt(0, object); 5081 SetRawInputAt(1, value); 5082 } 5083 5084 bool CanDoImplicitNullCheckOn(HInstruction* obj) const OVERRIDE { 5085 return (obj == InputAt(0)) && art::CanDoImplicitNullCheckOn(GetFieldOffset().Uint32Value()); 5086 } 5087 5088 const FieldInfo& GetFieldInfo() const { return field_info_; } 5089 MemberOffset GetFieldOffset() const { return field_info_.GetFieldOffset(); } 5090 Primitive::Type GetFieldType() const { return field_info_.GetFieldType(); } 5091 bool IsVolatile() const { return field_info_.IsVolatile(); } 5092 HInstruction* GetValue() const { return InputAt(1); } 5093 bool GetValueCanBeNull() const { return GetPackedFlag<kFlagValueCanBeNull>(); } 5094 void ClearValueCanBeNull() { SetPackedFlag<kFlagValueCanBeNull>(false); } 5095 5096 DECLARE_INSTRUCTION(InstanceFieldSet); 5097 5098 private: 5099 static constexpr size_t kFlagValueCanBeNull = kNumberOfGenericPackedBits; 5100 static constexpr size_t kNumberOfInstanceFieldSetPackedBits = kFlagValueCanBeNull + 1; 5101 static_assert(kNumberOfInstanceFieldSetPackedBits <= kMaxNumberOfPackedBits, 5102 "Too many packed fields."); 5103 5104 const FieldInfo field_info_; 5105 5106 DISALLOW_COPY_AND_ASSIGN(HInstanceFieldSet); 5107}; 5108 5109class HArrayGet FINAL : public HExpression<2> { 5110 public: 5111 HArrayGet(HInstruction* array, 5112 HInstruction* index, 5113 Primitive::Type type, 5114 uint32_t dex_pc, 5115 bool is_string_char_at = false) 5116 : HExpression(type, SideEffects::ArrayReadOfType(type), dex_pc) { 5117 SetPackedFlag<kFlagIsStringCharAt>(is_string_char_at); 5118 SetRawInputAt(0, array); 5119 SetRawInputAt(1, index); 5120 } 5121 5122 bool CanBeMoved() const OVERRIDE { return true; } 5123 bool InstructionDataEquals(const HInstruction* other ATTRIBUTE_UNUSED) const OVERRIDE { 5124 return true; 5125 } 5126 bool CanDoImplicitNullCheckOn(HInstruction* obj ATTRIBUTE_UNUSED) const OVERRIDE { 5127 // TODO: We can be smarter here. 5128 // Currently, the array access is always preceded by an ArrayLength or a NullCheck 5129 // which generates the implicit null check. There are cases when these can be removed 5130 // to produce better code. If we ever add optimizations to do so we should allow an 5131 // implicit check here (as long as the address falls in the first page). 5132 return false; 5133 } 5134 5135 bool IsEquivalentOf(HArrayGet* other) const { 5136 bool result = (GetDexPc() == other->GetDexPc()); 5137 if (kIsDebugBuild && result) { 5138 DCHECK_EQ(GetBlock(), other->GetBlock()); 5139 DCHECK_EQ(GetArray(), other->GetArray()); 5140 DCHECK_EQ(GetIndex(), other->GetIndex()); 5141 if (Primitive::IsIntOrLongType(GetType())) { 5142 DCHECK(Primitive::IsFloatingPointType(other->GetType())) << other->GetType(); 5143 } else { 5144 DCHECK(Primitive::IsFloatingPointType(GetType())) << GetType(); 5145 DCHECK(Primitive::IsIntOrLongType(other->GetType())) << other->GetType(); 5146 } 5147 } 5148 return result; 5149 } 5150 5151 bool IsStringCharAt() const { return GetPackedFlag<kFlagIsStringCharAt>(); } 5152 5153 HInstruction* GetArray() const { return InputAt(0); } 5154 HInstruction* GetIndex() const { return InputAt(1); } 5155 5156 DECLARE_INSTRUCTION(ArrayGet); 5157 5158 private: 5159 // We treat a String as an array, creating the HArrayGet from String.charAt() 5160 // intrinsic in the instruction simplifier. We can always determine whether 5161 // a particular HArrayGet is actually a String.charAt() by looking at the type 5162 // of the input but that requires holding the mutator lock, so we prefer to use 5163 // a flag, so that code generators don't need to do the locking. 5164 static constexpr size_t kFlagIsStringCharAt = kNumberOfExpressionPackedBits; 5165 static constexpr size_t kNumberOfArrayGetPackedBits = kFlagIsStringCharAt + 1; 5166 static_assert(kNumberOfArrayGetPackedBits <= HInstruction::kMaxNumberOfPackedBits, 5167 "Too many packed fields."); 5168 5169 DISALLOW_COPY_AND_ASSIGN(HArrayGet); 5170}; 5171 5172class HArraySet FINAL : public HTemplateInstruction<3> { 5173 public: 5174 HArraySet(HInstruction* array, 5175 HInstruction* index, 5176 HInstruction* value, 5177 Primitive::Type expected_component_type, 5178 uint32_t dex_pc) 5179 : HTemplateInstruction(SideEffects::None(), dex_pc) { 5180 SetPackedField<ExpectedComponentTypeField>(expected_component_type); 5181 SetPackedFlag<kFlagNeedsTypeCheck>(value->GetType() == Primitive::kPrimNot); 5182 SetPackedFlag<kFlagValueCanBeNull>(true); 5183 SetPackedFlag<kFlagStaticTypeOfArrayIsObjectArray>(false); 5184 SetRawInputAt(0, array); 5185 SetRawInputAt(1, index); 5186 SetRawInputAt(2, value); 5187 // Make a best guess now, may be refined during SSA building. 5188 ComputeSideEffects(); 5189 } 5190 5191 bool NeedsEnvironment() const OVERRIDE { 5192 // We call a runtime method to throw ArrayStoreException. 5193 return NeedsTypeCheck(); 5194 } 5195 5196 // Can throw ArrayStoreException. 5197 bool CanThrow() const OVERRIDE { return NeedsTypeCheck(); } 5198 5199 bool CanDoImplicitNullCheckOn(HInstruction* obj ATTRIBUTE_UNUSED) const OVERRIDE { 5200 // TODO: Same as for ArrayGet. 5201 return false; 5202 } 5203 5204 void ClearNeedsTypeCheck() { 5205 SetPackedFlag<kFlagNeedsTypeCheck>(false); 5206 } 5207 5208 void ClearValueCanBeNull() { 5209 SetPackedFlag<kFlagValueCanBeNull>(false); 5210 } 5211 5212 void SetStaticTypeOfArrayIsObjectArray() { 5213 SetPackedFlag<kFlagStaticTypeOfArrayIsObjectArray>(true); 5214 } 5215 5216 bool GetValueCanBeNull() const { return GetPackedFlag<kFlagValueCanBeNull>(); } 5217 bool NeedsTypeCheck() const { return GetPackedFlag<kFlagNeedsTypeCheck>(); } 5218 bool StaticTypeOfArrayIsObjectArray() const { 5219 return GetPackedFlag<kFlagStaticTypeOfArrayIsObjectArray>(); 5220 } 5221 5222 HInstruction* GetArray() const { return InputAt(0); } 5223 HInstruction* GetIndex() const { return InputAt(1); } 5224 HInstruction* GetValue() const { return InputAt(2); } 5225 5226 Primitive::Type GetComponentType() const { 5227 // The Dex format does not type floating point index operations. Since the 5228 // `expected_component_type_` is set during building and can therefore not 5229 // be correct, we also check what is the value type. If it is a floating 5230 // point type, we must use that type. 5231 Primitive::Type value_type = GetValue()->GetType(); 5232 return ((value_type == Primitive::kPrimFloat) || (value_type == Primitive::kPrimDouble)) 5233 ? value_type 5234 : GetRawExpectedComponentType(); 5235 } 5236 5237 Primitive::Type GetRawExpectedComponentType() const { 5238 return GetPackedField<ExpectedComponentTypeField>(); 5239 } 5240 5241 void ComputeSideEffects() { 5242 Primitive::Type type = GetComponentType(); 5243 SetSideEffects(SideEffects::ArrayWriteOfType(type).Union( 5244 SideEffectsForArchRuntimeCalls(type))); 5245 } 5246 5247 static SideEffects SideEffectsForArchRuntimeCalls(Primitive::Type value_type) { 5248 return (value_type == Primitive::kPrimNot) ? SideEffects::CanTriggerGC() : SideEffects::None(); 5249 } 5250 5251 DECLARE_INSTRUCTION(ArraySet); 5252 5253 private: 5254 static constexpr size_t kFieldExpectedComponentType = kNumberOfGenericPackedBits; 5255 static constexpr size_t kFieldExpectedComponentTypeSize = 5256 MinimumBitsToStore(static_cast<size_t>(Primitive::kPrimLast)); 5257 static constexpr size_t kFlagNeedsTypeCheck = 5258 kFieldExpectedComponentType + kFieldExpectedComponentTypeSize; 5259 static constexpr size_t kFlagValueCanBeNull = kFlagNeedsTypeCheck + 1; 5260 // Cached information for the reference_type_info_ so that codegen 5261 // does not need to inspect the static type. 5262 static constexpr size_t kFlagStaticTypeOfArrayIsObjectArray = kFlagValueCanBeNull + 1; 5263 static constexpr size_t kNumberOfArraySetPackedBits = 5264 kFlagStaticTypeOfArrayIsObjectArray + 1; 5265 static_assert(kNumberOfArraySetPackedBits <= kMaxNumberOfPackedBits, "Too many packed fields."); 5266 using ExpectedComponentTypeField = 5267 BitField<Primitive::Type, kFieldExpectedComponentType, kFieldExpectedComponentTypeSize>; 5268 5269 DISALLOW_COPY_AND_ASSIGN(HArraySet); 5270}; 5271 5272class HArrayLength FINAL : public HExpression<1> { 5273 public: 5274 HArrayLength(HInstruction* array, uint32_t dex_pc, bool is_string_length = false) 5275 : HExpression(Primitive::kPrimInt, SideEffects::None(), dex_pc) { 5276 SetPackedFlag<kFlagIsStringLength>(is_string_length); 5277 // Note that arrays do not change length, so the instruction does not 5278 // depend on any write. 5279 SetRawInputAt(0, array); 5280 } 5281 5282 bool CanBeMoved() const OVERRIDE { return true; } 5283 bool InstructionDataEquals(const HInstruction* other ATTRIBUTE_UNUSED) const OVERRIDE { 5284 return true; 5285 } 5286 bool CanDoImplicitNullCheckOn(HInstruction* obj) const OVERRIDE { 5287 return obj == InputAt(0); 5288 } 5289 5290 bool IsStringLength() const { return GetPackedFlag<kFlagIsStringLength>(); } 5291 5292 DECLARE_INSTRUCTION(ArrayLength); 5293 5294 private: 5295 // We treat a String as an array, creating the HArrayLength from String.length() 5296 // or String.isEmpty() intrinsic in the instruction simplifier. We can always 5297 // determine whether a particular HArrayLength is actually a String.length() by 5298 // looking at the type of the input but that requires holding the mutator lock, so 5299 // we prefer to use a flag, so that code generators don't need to do the locking. 5300 static constexpr size_t kFlagIsStringLength = kNumberOfExpressionPackedBits; 5301 static constexpr size_t kNumberOfArrayLengthPackedBits = kFlagIsStringLength + 1; 5302 static_assert(kNumberOfArrayLengthPackedBits <= HInstruction::kMaxNumberOfPackedBits, 5303 "Too many packed fields."); 5304 5305 DISALLOW_COPY_AND_ASSIGN(HArrayLength); 5306}; 5307 5308class HBoundsCheck FINAL : public HExpression<2> { 5309 public: 5310 // `HBoundsCheck` can trigger GC, as it may call the `IndexOutOfBoundsException` 5311 // constructor. 5312 HBoundsCheck(HInstruction* index, 5313 HInstruction* length, 5314 uint32_t dex_pc, 5315 uint32_t string_char_at_method_index = DexFile::kDexNoIndex) 5316 : HExpression(index->GetType(), SideEffects::CanTriggerGC(), dex_pc), 5317 string_char_at_method_index_(string_char_at_method_index) { 5318 DCHECK_EQ(Primitive::kPrimInt, Primitive::PrimitiveKind(index->GetType())); 5319 SetRawInputAt(0, index); 5320 SetRawInputAt(1, length); 5321 } 5322 5323 bool CanBeMoved() const OVERRIDE { return true; } 5324 bool InstructionDataEquals(const HInstruction* other ATTRIBUTE_UNUSED) const OVERRIDE { 5325 return true; 5326 } 5327 5328 bool NeedsEnvironment() const OVERRIDE { return true; } 5329 5330 bool CanThrow() const OVERRIDE { return true; } 5331 5332 bool IsStringCharAt() const { return GetStringCharAtMethodIndex() != DexFile::kDexNoIndex; } 5333 uint32_t GetStringCharAtMethodIndex() const { return string_char_at_method_index_; } 5334 5335 HInstruction* GetIndex() const { return InputAt(0); } 5336 5337 DECLARE_INSTRUCTION(BoundsCheck); 5338 5339 private: 5340 // We treat a String as an array, creating the HBoundsCheck from String.charAt() 5341 // intrinsic in the instruction simplifier. We want to include the String.charAt() 5342 // in the stack trace if we actually throw the StringIndexOutOfBoundsException, 5343 // so we need to create an HEnvironment which will be translated to an InlineInfo 5344 // indicating the extra stack frame. Since we add this HEnvironment quite late, 5345 // in the PrepareForRegisterAllocation pass, we need to remember the method index 5346 // from the invoke as we don't want to look again at the dex bytecode. 5347 uint32_t string_char_at_method_index_; // DexFile::kDexNoIndex if regular array. 5348 5349 DISALLOW_COPY_AND_ASSIGN(HBoundsCheck); 5350}; 5351 5352class HSuspendCheck FINAL : public HTemplateInstruction<0> { 5353 public: 5354 explicit HSuspendCheck(uint32_t dex_pc = kNoDexPc) 5355 : HTemplateInstruction(SideEffects::CanTriggerGC(), dex_pc), slow_path_(nullptr) {} 5356 5357 bool NeedsEnvironment() const OVERRIDE { 5358 return true; 5359 } 5360 5361 void SetSlowPath(SlowPathCode* slow_path) { slow_path_ = slow_path; } 5362 SlowPathCode* GetSlowPath() const { return slow_path_; } 5363 5364 DECLARE_INSTRUCTION(SuspendCheck); 5365 5366 private: 5367 // Only used for code generation, in order to share the same slow path between back edges 5368 // of a same loop. 5369 SlowPathCode* slow_path_; 5370 5371 DISALLOW_COPY_AND_ASSIGN(HSuspendCheck); 5372}; 5373 5374// Pseudo-instruction which provides the native debugger with mapping information. 5375// It ensures that we can generate line number and local variables at this point. 5376class HNativeDebugInfo : public HTemplateInstruction<0> { 5377 public: 5378 explicit HNativeDebugInfo(uint32_t dex_pc) 5379 : HTemplateInstruction<0>(SideEffects::None(), dex_pc) {} 5380 5381 bool NeedsEnvironment() const OVERRIDE { 5382 return true; 5383 } 5384 5385 DECLARE_INSTRUCTION(NativeDebugInfo); 5386 5387 private: 5388 DISALLOW_COPY_AND_ASSIGN(HNativeDebugInfo); 5389}; 5390 5391/** 5392 * Instruction to load a Class object. 5393 */ 5394class HLoadClass FINAL : public HInstruction { 5395 public: 5396 // Determines how to load the Class. 5397 enum class LoadKind { 5398 // Use the Class* from the method's own ArtMethod*. 5399 kReferrersClass, 5400 5401 // Use boot image Class* address that will be known at link time. 5402 // Used for boot image classes referenced by boot image code in non-PIC mode. 5403 kBootImageLinkTimeAddress, 5404 5405 // Use PC-relative boot image Class* address that will be known at link time. 5406 // Used for boot image classes referenced by boot image code in PIC mode. 5407 kBootImageLinkTimePcRelative, 5408 5409 // Use a known boot image Class* address, embedded in the code by the codegen. 5410 // Used for boot image classes referenced by apps in AOT- and JIT-compiled code. 5411 // Note: codegen needs to emit a linker patch if indicated by compiler options' 5412 // GetIncludePatchInformation(). 5413 kBootImageAddress, 5414 5415 // Load from the resolved types array at an absolute address. 5416 // Used for classes outside the boot image referenced by JIT-compiled code. 5417 kDexCacheAddress, 5418 5419 // Load from resolved types array in the dex cache using a PC-relative load. 5420 // Used for classes outside boot image when we know that we can access 5421 // the dex cache arrays using a PC-relative load. 5422 kDexCachePcRelative, 5423 5424 // Load from resolved types array accessed through the class loaded from 5425 // the compiled method's own ArtMethod*. This is the default access type when 5426 // all other types are unavailable. 5427 kDexCacheViaMethod, 5428 5429 kLast = kDexCacheViaMethod 5430 }; 5431 5432 HLoadClass(HCurrentMethod* current_method, 5433 uint16_t type_index, 5434 const DexFile& dex_file, 5435 bool is_referrers_class, 5436 uint32_t dex_pc, 5437 bool needs_access_check, 5438 bool is_in_dex_cache, 5439 bool is_in_boot_image) 5440 : HInstruction(SideEffectsForArchRuntimeCalls(), dex_pc), 5441 special_input_(HUserRecord<HInstruction*>(current_method)), 5442 type_index_(type_index), 5443 dex_file_(dex_file), 5444 loaded_class_rti_(ReferenceTypeInfo::CreateInvalid()) { 5445 // Referrers class should not need access check. We never inline unverified 5446 // methods so we can't possibly end up in this situation. 5447 DCHECK(!is_referrers_class || !needs_access_check); 5448 5449 SetPackedField<LoadKindField>( 5450 is_referrers_class ? LoadKind::kReferrersClass : LoadKind::kDexCacheViaMethod); 5451 SetPackedFlag<kFlagNeedsAccessCheck>(needs_access_check); 5452 SetPackedFlag<kFlagIsInDexCache>(is_in_dex_cache); 5453 SetPackedFlag<kFlagIsInBootImage>(is_in_boot_image); 5454 SetPackedFlag<kFlagGenerateClInitCheck>(false); 5455 } 5456 5457 void SetLoadKindWithAddress(LoadKind load_kind, uint64_t address) { 5458 DCHECK(HasAddress(load_kind)); 5459 load_data_.address = address; 5460 SetLoadKindInternal(load_kind); 5461 } 5462 5463 void SetLoadKindWithTypeReference(LoadKind load_kind, 5464 const DexFile& dex_file, 5465 uint32_t type_index) { 5466 DCHECK(HasTypeReference(load_kind)); 5467 DCHECK(IsSameDexFile(dex_file_, dex_file)); 5468 DCHECK_EQ(type_index_, type_index); 5469 SetLoadKindInternal(load_kind); 5470 } 5471 5472 void SetLoadKindWithDexCacheReference(LoadKind load_kind, 5473 const DexFile& dex_file, 5474 uint32_t element_index) { 5475 DCHECK(HasDexCacheReference(load_kind)); 5476 DCHECK(IsSameDexFile(dex_file_, dex_file)); 5477 load_data_.dex_cache_element_index = element_index; 5478 SetLoadKindInternal(load_kind); 5479 } 5480 5481 LoadKind GetLoadKind() const { 5482 return GetPackedField<LoadKindField>(); 5483 } 5484 5485 bool CanBeMoved() const OVERRIDE { return true; } 5486 5487 bool InstructionDataEquals(const HInstruction* other) const; 5488 5489 size_t ComputeHashCode() const OVERRIDE { return type_index_; } 5490 5491 bool CanBeNull() const OVERRIDE { return false; } 5492 5493 bool NeedsEnvironment() const OVERRIDE { 5494 return CanCallRuntime(); 5495 } 5496 5497 void SetMustGenerateClinitCheck(bool generate_clinit_check) { 5498 // The entrypoint the code generator is going to call does not do 5499 // clinit of the class. 5500 DCHECK(!NeedsAccessCheck()); 5501 SetPackedFlag<kFlagGenerateClInitCheck>(generate_clinit_check); 5502 } 5503 5504 bool CanCallRuntime() const { 5505 return MustGenerateClinitCheck() || 5506 (!IsReferrersClass() && !IsInDexCache()) || 5507 NeedsAccessCheck(); 5508 } 5509 5510 5511 bool CanThrow() const OVERRIDE { 5512 return CanCallRuntime(); 5513 } 5514 5515 ReferenceTypeInfo GetLoadedClassRTI() { 5516 return loaded_class_rti_; 5517 } 5518 5519 void SetLoadedClassRTI(ReferenceTypeInfo rti) { 5520 // Make sure we only set exact types (the loaded class should never be merged). 5521 DCHECK(rti.IsExact()); 5522 loaded_class_rti_ = rti; 5523 } 5524 5525 uint32_t GetTypeIndex() const { return type_index_; } 5526 const DexFile& GetDexFile() const { return dex_file_; } 5527 5528 uint32_t GetDexCacheElementOffset() const; 5529 5530 uint64_t GetAddress() const { 5531 DCHECK(HasAddress(GetLoadKind())); 5532 return load_data_.address; 5533 } 5534 5535 bool NeedsDexCacheOfDeclaringClass() const OVERRIDE { return !IsReferrersClass(); } 5536 5537 static SideEffects SideEffectsForArchRuntimeCalls() { 5538 return SideEffects::CanTriggerGC(); 5539 } 5540 5541 bool IsReferrersClass() const { return GetLoadKind() == LoadKind::kReferrersClass; } 5542 bool NeedsAccessCheck() const { return GetPackedFlag<kFlagNeedsAccessCheck>(); } 5543 bool IsInDexCache() const { return GetPackedFlag<kFlagIsInDexCache>(); } 5544 bool IsInBootImage() const { return GetPackedFlag<kFlagIsInBootImage>(); } 5545 bool MustGenerateClinitCheck() const { return GetPackedFlag<kFlagGenerateClInitCheck>(); } 5546 5547 void MarkInDexCache() { 5548 SetPackedFlag<kFlagIsInDexCache>(true); 5549 DCHECK(!NeedsEnvironment()); 5550 RemoveEnvironment(); 5551 SetSideEffects(SideEffects::None()); 5552 } 5553 5554 void MarkInBootImage() { 5555 SetPackedFlag<kFlagIsInBootImage>(true); 5556 } 5557 5558 void AddSpecialInput(HInstruction* special_input); 5559 5560 using HInstruction::GetInputRecords; // Keep the const version visible. 5561 ArrayRef<HUserRecord<HInstruction*>> GetInputRecords() OVERRIDE FINAL { 5562 return ArrayRef<HUserRecord<HInstruction*>>( 5563 &special_input_, (special_input_.GetInstruction() != nullptr) ? 1u : 0u); 5564 } 5565 5566 Primitive::Type GetType() const OVERRIDE { 5567 return Primitive::kPrimNot; 5568 } 5569 5570 DECLARE_INSTRUCTION(LoadClass); 5571 5572 private: 5573 static constexpr size_t kFlagNeedsAccessCheck = kNumberOfGenericPackedBits; 5574 static constexpr size_t kFlagIsInDexCache = kFlagNeedsAccessCheck + 1; 5575 static constexpr size_t kFlagIsInBootImage = kFlagIsInDexCache + 1; 5576 // Whether this instruction must generate the initialization check. 5577 // Used for code generation. 5578 static constexpr size_t kFlagGenerateClInitCheck = kFlagIsInBootImage + 1; 5579 static constexpr size_t kFieldLoadKind = kFlagGenerateClInitCheck + 1; 5580 static constexpr size_t kFieldLoadKindSize = 5581 MinimumBitsToStore(static_cast<size_t>(LoadKind::kLast)); 5582 static constexpr size_t kNumberOfLoadClassPackedBits = kFieldLoadKind + kFieldLoadKindSize; 5583 static_assert(kNumberOfLoadClassPackedBits < kMaxNumberOfPackedBits, "Too many packed fields."); 5584 using LoadKindField = BitField<LoadKind, kFieldLoadKind, kFieldLoadKindSize>; 5585 5586 static bool HasTypeReference(LoadKind load_kind) { 5587 return load_kind == LoadKind::kBootImageLinkTimeAddress || 5588 load_kind == LoadKind::kBootImageLinkTimePcRelative || 5589 load_kind == LoadKind::kDexCacheViaMethod || 5590 load_kind == LoadKind::kReferrersClass; 5591 } 5592 5593 static bool HasAddress(LoadKind load_kind) { 5594 return load_kind == LoadKind::kBootImageAddress || load_kind == LoadKind::kDexCacheAddress; 5595 } 5596 5597 static bool HasDexCacheReference(LoadKind load_kind) { 5598 return load_kind == LoadKind::kDexCachePcRelative; 5599 } 5600 5601 void SetLoadKindInternal(LoadKind load_kind); 5602 5603 // The special input is the HCurrentMethod for kDexCacheViaMethod or kReferrersClass. 5604 // For other load kinds it's empty or possibly some architecture-specific instruction 5605 // for PC-relative loads, i.e. kDexCachePcRelative or kBootImageLinkTimePcRelative. 5606 HUserRecord<HInstruction*> special_input_; 5607 5608 const uint16_t type_index_; 5609 const DexFile& dex_file_; 5610 5611 union { 5612 uint32_t dex_cache_element_index; // Only for dex cache reference. 5613 uint64_t address; // Up to 64-bit, needed for kDexCacheAddress on 64-bit targets. 5614 } load_data_; 5615 5616 ReferenceTypeInfo loaded_class_rti_; 5617 5618 DISALLOW_COPY_AND_ASSIGN(HLoadClass); 5619}; 5620std::ostream& operator<<(std::ostream& os, HLoadClass::LoadKind rhs); 5621 5622// Note: defined outside class to see operator<<(., HLoadClass::LoadKind). 5623inline uint32_t HLoadClass::GetDexCacheElementOffset() const { 5624 DCHECK(HasDexCacheReference(GetLoadKind())) << GetLoadKind(); 5625 return load_data_.dex_cache_element_index; 5626} 5627 5628// Note: defined outside class to see operator<<(., HLoadClass::LoadKind). 5629inline void HLoadClass::AddSpecialInput(HInstruction* special_input) { 5630 // The special input is used for PC-relative loads on some architectures, 5631 // including literal pool loads, which are PC-relative too. 5632 DCHECK(GetLoadKind() == LoadKind::kBootImageLinkTimePcRelative || 5633 GetLoadKind() == LoadKind::kDexCachePcRelative || 5634 GetLoadKind() == LoadKind::kBootImageLinkTimeAddress || 5635 GetLoadKind() == LoadKind::kBootImageAddress) << GetLoadKind(); 5636 DCHECK(special_input_.GetInstruction() == nullptr); 5637 special_input_ = HUserRecord<HInstruction*>(special_input); 5638 special_input->AddUseAt(this, 0); 5639} 5640 5641class HLoadString FINAL : public HInstruction { 5642 public: 5643 // Determines how to load the String. 5644 enum class LoadKind { 5645 // Use boot image String* address that will be known at link time. 5646 // Used for boot image strings referenced by boot image code in non-PIC mode. 5647 kBootImageLinkTimeAddress, 5648 5649 // Use PC-relative boot image String* address that will be known at link time. 5650 // Used for boot image strings referenced by boot image code in PIC mode. 5651 kBootImageLinkTimePcRelative, 5652 5653 // Use a known boot image String* address, embedded in the code by the codegen. 5654 // Used for boot image strings referenced by apps in AOT- and JIT-compiled code. 5655 // Note: codegen needs to emit a linker patch if indicated by compiler options' 5656 // GetIncludePatchInformation(). 5657 kBootImageAddress, 5658 5659 // Load from the resolved strings array at an absolute address. 5660 // Used for strings outside the boot image referenced by JIT-compiled code. 5661 kDexCacheAddress, 5662 5663 // Load from an entry in the .bss section using a PC-relative load. 5664 // Used for strings outside boot image when .bss is accessible with a PC-relative load. 5665 kBssEntry, 5666 5667 // Load from resolved strings array accessed through the class loaded from 5668 // the compiled method's own ArtMethod*. This is the default access type when 5669 // all other types are unavailable. 5670 kDexCacheViaMethod, 5671 5672 kLast = kDexCacheViaMethod 5673 }; 5674 5675 HLoadString(HCurrentMethod* current_method, 5676 uint32_t string_index, 5677 const DexFile& dex_file, 5678 uint32_t dex_pc) 5679 : HInstruction(SideEffectsForArchRuntimeCalls(), dex_pc), 5680 special_input_(HUserRecord<HInstruction*>(current_method)), 5681 string_index_(string_index) { 5682 SetPackedFlag<kFlagIsInDexCache>(false); 5683 SetPackedField<LoadKindField>(LoadKind::kDexCacheViaMethod); 5684 load_data_.dex_file_ = &dex_file; 5685 } 5686 5687 void SetLoadKindWithAddress(LoadKind load_kind, uint64_t address) { 5688 DCHECK(HasAddress(load_kind)); 5689 load_data_.address = address; 5690 SetLoadKindInternal(load_kind); 5691 } 5692 5693 void SetLoadKindWithStringReference(LoadKind load_kind, 5694 const DexFile& dex_file, 5695 uint32_t string_index) { 5696 DCHECK(HasStringReference(load_kind)); 5697 load_data_.dex_file_ = &dex_file; 5698 string_index_ = string_index; 5699 SetLoadKindInternal(load_kind); 5700 } 5701 5702 LoadKind GetLoadKind() const { 5703 return GetPackedField<LoadKindField>(); 5704 } 5705 5706 const DexFile& GetDexFile() const; 5707 5708 uint32_t GetStringIndex() const { 5709 DCHECK(HasStringReference(GetLoadKind()) || /* For slow paths. */ !IsInDexCache()); 5710 return string_index_; 5711 } 5712 5713 uint64_t GetAddress() const { 5714 DCHECK(HasAddress(GetLoadKind())); 5715 return load_data_.address; 5716 } 5717 5718 bool CanBeMoved() const OVERRIDE { return true; } 5719 5720 bool InstructionDataEquals(const HInstruction* other) const OVERRIDE; 5721 5722 size_t ComputeHashCode() const OVERRIDE { return string_index_; } 5723 5724 // Will call the runtime if we need to load the string through 5725 // the dex cache and the string is not guaranteed to be there yet. 5726 bool NeedsEnvironment() const OVERRIDE { 5727 LoadKind load_kind = GetLoadKind(); 5728 if (load_kind == LoadKind::kBootImageLinkTimeAddress || 5729 load_kind == LoadKind::kBootImageLinkTimePcRelative || 5730 load_kind == LoadKind::kBootImageAddress) { 5731 return false; 5732 } 5733 return !IsInDexCache(); 5734 } 5735 5736 bool NeedsDexCacheOfDeclaringClass() const OVERRIDE { 5737 return GetLoadKind() == LoadKind::kDexCacheViaMethod; 5738 } 5739 5740 bool CanBeNull() const OVERRIDE { return false; } 5741 bool CanThrow() const OVERRIDE { return NeedsEnvironment(); } 5742 5743 static SideEffects SideEffectsForArchRuntimeCalls() { 5744 return SideEffects::CanTriggerGC(); 5745 } 5746 5747 bool IsInDexCache() const { return GetPackedFlag<kFlagIsInDexCache>(); } 5748 5749 void MarkInDexCache() { 5750 SetPackedFlag<kFlagIsInDexCache>(true); 5751 DCHECK(!NeedsEnvironment()); 5752 RemoveEnvironment(); 5753 SetSideEffects(SideEffects::None()); 5754 } 5755 5756 void AddSpecialInput(HInstruction* special_input); 5757 5758 using HInstruction::GetInputRecords; // Keep the const version visible. 5759 ArrayRef<HUserRecord<HInstruction*>> GetInputRecords() OVERRIDE FINAL { 5760 return ArrayRef<HUserRecord<HInstruction*>>( 5761 &special_input_, (special_input_.GetInstruction() != nullptr) ? 1u : 0u); 5762 } 5763 5764 Primitive::Type GetType() const OVERRIDE { 5765 return Primitive::kPrimNot; 5766 } 5767 5768 DECLARE_INSTRUCTION(LoadString); 5769 5770 private: 5771 static constexpr size_t kFlagIsInDexCache = kNumberOfGenericPackedBits; 5772 static constexpr size_t kFieldLoadKind = kFlagIsInDexCache + 1; 5773 static constexpr size_t kFieldLoadKindSize = 5774 MinimumBitsToStore(static_cast<size_t>(LoadKind::kLast)); 5775 static constexpr size_t kNumberOfLoadStringPackedBits = kFieldLoadKind + kFieldLoadKindSize; 5776 static_assert(kNumberOfLoadStringPackedBits <= kMaxNumberOfPackedBits, "Too many packed fields."); 5777 using LoadKindField = BitField<LoadKind, kFieldLoadKind, kFieldLoadKindSize>; 5778 5779 static bool HasStringReference(LoadKind load_kind) { 5780 return load_kind == LoadKind::kBootImageLinkTimeAddress || 5781 load_kind == LoadKind::kBootImageLinkTimePcRelative || 5782 load_kind == LoadKind::kBssEntry || 5783 load_kind == LoadKind::kDexCacheViaMethod; 5784 } 5785 5786 static bool HasAddress(LoadKind load_kind) { 5787 return load_kind == LoadKind::kBootImageAddress || load_kind == LoadKind::kDexCacheAddress; 5788 } 5789 5790 void SetLoadKindInternal(LoadKind load_kind); 5791 5792 // The special input is the HCurrentMethod for kDexCacheViaMethod. 5793 // For other load kinds it's empty or possibly some architecture-specific instruction 5794 // for PC-relative loads, i.e. kDexCachePcRelative or kBootImageLinkTimePcRelative. 5795 HUserRecord<HInstruction*> special_input_; 5796 5797 // String index serves also as the hash code and it's also needed for slow-paths, 5798 // so it must not be overwritten with other load data. 5799 uint32_t string_index_; 5800 5801 union { 5802 const DexFile* dex_file_; // For string reference. 5803 uint64_t address; // Up to 64-bit, needed for kDexCacheAddress on 64-bit targets. 5804 } load_data_; 5805 5806 DISALLOW_COPY_AND_ASSIGN(HLoadString); 5807}; 5808std::ostream& operator<<(std::ostream& os, HLoadString::LoadKind rhs); 5809 5810// Note: defined outside class to see operator<<(., HLoadString::LoadKind). 5811inline const DexFile& HLoadString::GetDexFile() const { 5812 DCHECK(HasStringReference(GetLoadKind())) << GetLoadKind(); 5813 return *load_data_.dex_file_; 5814} 5815 5816// Note: defined outside class to see operator<<(., HLoadString::LoadKind). 5817inline void HLoadString::AddSpecialInput(HInstruction* special_input) { 5818 // The special input is used for PC-relative loads on some architectures, 5819 // including literal pool loads, which are PC-relative too. 5820 DCHECK(GetLoadKind() == LoadKind::kBootImageLinkTimePcRelative || 5821 GetLoadKind() == LoadKind::kBssEntry || 5822 GetLoadKind() == LoadKind::kBootImageLinkTimeAddress || 5823 GetLoadKind() == LoadKind::kBootImageAddress) << GetLoadKind(); 5824 // HLoadString::GetInputRecords() returns an empty array at this point, 5825 // so use the GetInputRecords() from the base class to set the input record. 5826 DCHECK(special_input_.GetInstruction() == nullptr); 5827 special_input_ = HUserRecord<HInstruction*>(special_input); 5828 special_input->AddUseAt(this, 0); 5829} 5830 5831/** 5832 * Performs an initialization check on its Class object input. 5833 */ 5834class HClinitCheck FINAL : public HExpression<1> { 5835 public: 5836 HClinitCheck(HLoadClass* constant, uint32_t dex_pc) 5837 : HExpression( 5838 Primitive::kPrimNot, 5839 SideEffects::AllChanges(), // Assume write/read on all fields/arrays. 5840 dex_pc) { 5841 SetRawInputAt(0, constant); 5842 } 5843 5844 bool CanBeMoved() const OVERRIDE { return true; } 5845 bool InstructionDataEquals(const HInstruction* other ATTRIBUTE_UNUSED) const OVERRIDE { 5846 return true; 5847 } 5848 5849 bool NeedsEnvironment() const OVERRIDE { 5850 // May call runtime to initialize the class. 5851 return true; 5852 } 5853 5854 bool CanThrow() const OVERRIDE { return true; } 5855 5856 HLoadClass* GetLoadClass() const { return InputAt(0)->AsLoadClass(); } 5857 5858 DECLARE_INSTRUCTION(ClinitCheck); 5859 5860 private: 5861 DISALLOW_COPY_AND_ASSIGN(HClinitCheck); 5862}; 5863 5864class HStaticFieldGet FINAL : public HExpression<1> { 5865 public: 5866 HStaticFieldGet(HInstruction* cls, 5867 Primitive::Type field_type, 5868 MemberOffset field_offset, 5869 bool is_volatile, 5870 uint32_t field_idx, 5871 uint16_t declaring_class_def_index, 5872 const DexFile& dex_file, 5873 Handle<mirror::DexCache> dex_cache, 5874 uint32_t dex_pc) 5875 : HExpression(field_type, SideEffects::FieldReadOfType(field_type, is_volatile), dex_pc), 5876 field_info_(field_offset, 5877 field_type, 5878 is_volatile, 5879 field_idx, 5880 declaring_class_def_index, 5881 dex_file, 5882 dex_cache) { 5883 SetRawInputAt(0, cls); 5884 } 5885 5886 5887 bool CanBeMoved() const OVERRIDE { return !IsVolatile(); } 5888 5889 bool InstructionDataEquals(const HInstruction* other) const OVERRIDE { 5890 const HStaticFieldGet* other_get = other->AsStaticFieldGet(); 5891 return GetFieldOffset().SizeValue() == other_get->GetFieldOffset().SizeValue(); 5892 } 5893 5894 size_t ComputeHashCode() const OVERRIDE { 5895 return (HInstruction::ComputeHashCode() << 7) | GetFieldOffset().SizeValue(); 5896 } 5897 5898 const FieldInfo& GetFieldInfo() const { return field_info_; } 5899 MemberOffset GetFieldOffset() const { return field_info_.GetFieldOffset(); } 5900 Primitive::Type GetFieldType() const { return field_info_.GetFieldType(); } 5901 bool IsVolatile() const { return field_info_.IsVolatile(); } 5902 5903 DECLARE_INSTRUCTION(StaticFieldGet); 5904 5905 private: 5906 const FieldInfo field_info_; 5907 5908 DISALLOW_COPY_AND_ASSIGN(HStaticFieldGet); 5909}; 5910 5911class HStaticFieldSet FINAL : public HTemplateInstruction<2> { 5912 public: 5913 HStaticFieldSet(HInstruction* cls, 5914 HInstruction* value, 5915 Primitive::Type field_type, 5916 MemberOffset field_offset, 5917 bool is_volatile, 5918 uint32_t field_idx, 5919 uint16_t declaring_class_def_index, 5920 const DexFile& dex_file, 5921 Handle<mirror::DexCache> dex_cache, 5922 uint32_t dex_pc) 5923 : HTemplateInstruction(SideEffects::FieldWriteOfType(field_type, is_volatile), dex_pc), 5924 field_info_(field_offset, 5925 field_type, 5926 is_volatile, 5927 field_idx, 5928 declaring_class_def_index, 5929 dex_file, 5930 dex_cache) { 5931 SetPackedFlag<kFlagValueCanBeNull>(true); 5932 SetRawInputAt(0, cls); 5933 SetRawInputAt(1, value); 5934 } 5935 5936 const FieldInfo& GetFieldInfo() const { return field_info_; } 5937 MemberOffset GetFieldOffset() const { return field_info_.GetFieldOffset(); } 5938 Primitive::Type GetFieldType() const { return field_info_.GetFieldType(); } 5939 bool IsVolatile() const { return field_info_.IsVolatile(); } 5940 5941 HInstruction* GetValue() const { return InputAt(1); } 5942 bool GetValueCanBeNull() const { return GetPackedFlag<kFlagValueCanBeNull>(); } 5943 void ClearValueCanBeNull() { SetPackedFlag<kFlagValueCanBeNull>(false); } 5944 5945 DECLARE_INSTRUCTION(StaticFieldSet); 5946 5947 private: 5948 static constexpr size_t kFlagValueCanBeNull = kNumberOfGenericPackedBits; 5949 static constexpr size_t kNumberOfStaticFieldSetPackedBits = kFlagValueCanBeNull + 1; 5950 static_assert(kNumberOfStaticFieldSetPackedBits <= kMaxNumberOfPackedBits, 5951 "Too many packed fields."); 5952 5953 const FieldInfo field_info_; 5954 5955 DISALLOW_COPY_AND_ASSIGN(HStaticFieldSet); 5956}; 5957 5958class HUnresolvedInstanceFieldGet FINAL : public HExpression<1> { 5959 public: 5960 HUnresolvedInstanceFieldGet(HInstruction* obj, 5961 Primitive::Type field_type, 5962 uint32_t field_index, 5963 uint32_t dex_pc) 5964 : HExpression(field_type, SideEffects::AllExceptGCDependency(), dex_pc), 5965 field_index_(field_index) { 5966 SetRawInputAt(0, obj); 5967 } 5968 5969 bool NeedsEnvironment() const OVERRIDE { return true; } 5970 bool CanThrow() const OVERRIDE { return true; } 5971 5972 Primitive::Type GetFieldType() const { return GetType(); } 5973 uint32_t GetFieldIndex() const { return field_index_; } 5974 5975 DECLARE_INSTRUCTION(UnresolvedInstanceFieldGet); 5976 5977 private: 5978 const uint32_t field_index_; 5979 5980 DISALLOW_COPY_AND_ASSIGN(HUnresolvedInstanceFieldGet); 5981}; 5982 5983class HUnresolvedInstanceFieldSet FINAL : public HTemplateInstruction<2> { 5984 public: 5985 HUnresolvedInstanceFieldSet(HInstruction* obj, 5986 HInstruction* value, 5987 Primitive::Type field_type, 5988 uint32_t field_index, 5989 uint32_t dex_pc) 5990 : HTemplateInstruction(SideEffects::AllExceptGCDependency(), dex_pc), 5991 field_index_(field_index) { 5992 SetPackedField<FieldTypeField>(field_type); 5993 DCHECK_EQ(Primitive::PrimitiveKind(field_type), Primitive::PrimitiveKind(value->GetType())); 5994 SetRawInputAt(0, obj); 5995 SetRawInputAt(1, value); 5996 } 5997 5998 bool NeedsEnvironment() const OVERRIDE { return true; } 5999 bool CanThrow() const OVERRIDE { return true; } 6000 6001 Primitive::Type GetFieldType() const { return GetPackedField<FieldTypeField>(); } 6002 uint32_t GetFieldIndex() const { return field_index_; } 6003 6004 DECLARE_INSTRUCTION(UnresolvedInstanceFieldSet); 6005 6006 private: 6007 static constexpr size_t kFieldFieldType = HInstruction::kNumberOfGenericPackedBits; 6008 static constexpr size_t kFieldFieldTypeSize = 6009 MinimumBitsToStore(static_cast<size_t>(Primitive::kPrimLast)); 6010 static constexpr size_t kNumberOfUnresolvedStaticFieldSetPackedBits = 6011 kFieldFieldType + kFieldFieldTypeSize; 6012 static_assert(kNumberOfUnresolvedStaticFieldSetPackedBits <= HInstruction::kMaxNumberOfPackedBits, 6013 "Too many packed fields."); 6014 using FieldTypeField = BitField<Primitive::Type, kFieldFieldType, kFieldFieldTypeSize>; 6015 6016 const uint32_t field_index_; 6017 6018 DISALLOW_COPY_AND_ASSIGN(HUnresolvedInstanceFieldSet); 6019}; 6020 6021class HUnresolvedStaticFieldGet FINAL : public HExpression<0> { 6022 public: 6023 HUnresolvedStaticFieldGet(Primitive::Type field_type, 6024 uint32_t field_index, 6025 uint32_t dex_pc) 6026 : HExpression(field_type, SideEffects::AllExceptGCDependency(), dex_pc), 6027 field_index_(field_index) { 6028 } 6029 6030 bool NeedsEnvironment() const OVERRIDE { return true; } 6031 bool CanThrow() const OVERRIDE { return true; } 6032 6033 Primitive::Type GetFieldType() const { return GetType(); } 6034 uint32_t GetFieldIndex() const { return field_index_; } 6035 6036 DECLARE_INSTRUCTION(UnresolvedStaticFieldGet); 6037 6038 private: 6039 const uint32_t field_index_; 6040 6041 DISALLOW_COPY_AND_ASSIGN(HUnresolvedStaticFieldGet); 6042}; 6043 6044class HUnresolvedStaticFieldSet FINAL : public HTemplateInstruction<1> { 6045 public: 6046 HUnresolvedStaticFieldSet(HInstruction* value, 6047 Primitive::Type field_type, 6048 uint32_t field_index, 6049 uint32_t dex_pc) 6050 : HTemplateInstruction(SideEffects::AllExceptGCDependency(), dex_pc), 6051 field_index_(field_index) { 6052 SetPackedField<FieldTypeField>(field_type); 6053 DCHECK_EQ(Primitive::PrimitiveKind(field_type), Primitive::PrimitiveKind(value->GetType())); 6054 SetRawInputAt(0, value); 6055 } 6056 6057 bool NeedsEnvironment() const OVERRIDE { return true; } 6058 bool CanThrow() const OVERRIDE { return true; } 6059 6060 Primitive::Type GetFieldType() const { return GetPackedField<FieldTypeField>(); } 6061 uint32_t GetFieldIndex() const { return field_index_; } 6062 6063 DECLARE_INSTRUCTION(UnresolvedStaticFieldSet); 6064 6065 private: 6066 static constexpr size_t kFieldFieldType = HInstruction::kNumberOfGenericPackedBits; 6067 static constexpr size_t kFieldFieldTypeSize = 6068 MinimumBitsToStore(static_cast<size_t>(Primitive::kPrimLast)); 6069 static constexpr size_t kNumberOfUnresolvedStaticFieldSetPackedBits = 6070 kFieldFieldType + kFieldFieldTypeSize; 6071 static_assert(kNumberOfUnresolvedStaticFieldSetPackedBits <= HInstruction::kMaxNumberOfPackedBits, 6072 "Too many packed fields."); 6073 using FieldTypeField = BitField<Primitive::Type, kFieldFieldType, kFieldFieldTypeSize>; 6074 6075 const uint32_t field_index_; 6076 6077 DISALLOW_COPY_AND_ASSIGN(HUnresolvedStaticFieldSet); 6078}; 6079 6080// Implement the move-exception DEX instruction. 6081class HLoadException FINAL : public HExpression<0> { 6082 public: 6083 explicit HLoadException(uint32_t dex_pc = kNoDexPc) 6084 : HExpression(Primitive::kPrimNot, SideEffects::None(), dex_pc) {} 6085 6086 bool CanBeNull() const OVERRIDE { return false; } 6087 6088 DECLARE_INSTRUCTION(LoadException); 6089 6090 private: 6091 DISALLOW_COPY_AND_ASSIGN(HLoadException); 6092}; 6093 6094// Implicit part of move-exception which clears thread-local exception storage. 6095// Must not be removed because the runtime expects the TLS to get cleared. 6096class HClearException FINAL : public HTemplateInstruction<0> { 6097 public: 6098 explicit HClearException(uint32_t dex_pc = kNoDexPc) 6099 : HTemplateInstruction(SideEffects::AllWrites(), dex_pc) {} 6100 6101 DECLARE_INSTRUCTION(ClearException); 6102 6103 private: 6104 DISALLOW_COPY_AND_ASSIGN(HClearException); 6105}; 6106 6107class HThrow FINAL : public HTemplateInstruction<1> { 6108 public: 6109 HThrow(HInstruction* exception, uint32_t dex_pc) 6110 : HTemplateInstruction(SideEffects::CanTriggerGC(), dex_pc) { 6111 SetRawInputAt(0, exception); 6112 } 6113 6114 bool IsControlFlow() const OVERRIDE { return true; } 6115 6116 bool NeedsEnvironment() const OVERRIDE { return true; } 6117 6118 bool CanThrow() const OVERRIDE { return true; } 6119 6120 6121 DECLARE_INSTRUCTION(Throw); 6122 6123 private: 6124 DISALLOW_COPY_AND_ASSIGN(HThrow); 6125}; 6126 6127/** 6128 * Implementation strategies for the code generator of a HInstanceOf 6129 * or `HCheckCast`. 6130 */ 6131enum class TypeCheckKind { 6132 kUnresolvedCheck, // Check against an unresolved type. 6133 kExactCheck, // Can do a single class compare. 6134 kClassHierarchyCheck, // Can just walk the super class chain. 6135 kAbstractClassCheck, // Can just walk the super class chain, starting one up. 6136 kInterfaceCheck, // No optimization yet when checking against an interface. 6137 kArrayObjectCheck, // Can just check if the array is not primitive. 6138 kArrayCheck, // No optimization yet when checking against a generic array. 6139 kLast = kArrayCheck 6140}; 6141 6142std::ostream& operator<<(std::ostream& os, TypeCheckKind rhs); 6143 6144class HInstanceOf FINAL : public HExpression<2> { 6145 public: 6146 HInstanceOf(HInstruction* object, 6147 HLoadClass* constant, 6148 TypeCheckKind check_kind, 6149 uint32_t dex_pc) 6150 : HExpression(Primitive::kPrimBoolean, 6151 SideEffectsForArchRuntimeCalls(check_kind), 6152 dex_pc) { 6153 SetPackedField<TypeCheckKindField>(check_kind); 6154 SetPackedFlag<kFlagMustDoNullCheck>(true); 6155 SetRawInputAt(0, object); 6156 SetRawInputAt(1, constant); 6157 } 6158 6159 bool CanBeMoved() const OVERRIDE { return true; } 6160 6161 bool InstructionDataEquals(const HInstruction* other ATTRIBUTE_UNUSED) const OVERRIDE { 6162 return true; 6163 } 6164 6165 bool NeedsEnvironment() const OVERRIDE { 6166 return CanCallRuntime(GetTypeCheckKind()); 6167 } 6168 6169 // Used only in code generation. 6170 bool MustDoNullCheck() const { return GetPackedFlag<kFlagMustDoNullCheck>(); } 6171 void ClearMustDoNullCheck() { SetPackedFlag<kFlagMustDoNullCheck>(false); } 6172 TypeCheckKind GetTypeCheckKind() const { return GetPackedField<TypeCheckKindField>(); } 6173 bool IsExactCheck() const { return GetTypeCheckKind() == TypeCheckKind::kExactCheck; } 6174 6175 static bool CanCallRuntime(TypeCheckKind check_kind) { 6176 // Mips currently does runtime calls for any other checks. 6177 return check_kind != TypeCheckKind::kExactCheck; 6178 } 6179 6180 static SideEffects SideEffectsForArchRuntimeCalls(TypeCheckKind check_kind) { 6181 return CanCallRuntime(check_kind) ? SideEffects::CanTriggerGC() : SideEffects::None(); 6182 } 6183 6184 DECLARE_INSTRUCTION(InstanceOf); 6185 6186 private: 6187 static constexpr size_t kFieldTypeCheckKind = kNumberOfExpressionPackedBits; 6188 static constexpr size_t kFieldTypeCheckKindSize = 6189 MinimumBitsToStore(static_cast<size_t>(TypeCheckKind::kLast)); 6190 static constexpr size_t kFlagMustDoNullCheck = kFieldTypeCheckKind + kFieldTypeCheckKindSize; 6191 static constexpr size_t kNumberOfInstanceOfPackedBits = kFlagMustDoNullCheck + 1; 6192 static_assert(kNumberOfInstanceOfPackedBits <= kMaxNumberOfPackedBits, "Too many packed fields."); 6193 using TypeCheckKindField = BitField<TypeCheckKind, kFieldTypeCheckKind, kFieldTypeCheckKindSize>; 6194 6195 DISALLOW_COPY_AND_ASSIGN(HInstanceOf); 6196}; 6197 6198class HBoundType FINAL : public HExpression<1> { 6199 public: 6200 explicit HBoundType(HInstruction* input, uint32_t dex_pc = kNoDexPc) 6201 : HExpression(Primitive::kPrimNot, SideEffects::None(), dex_pc), 6202 upper_bound_(ReferenceTypeInfo::CreateInvalid()) { 6203 SetPackedFlag<kFlagUpperCanBeNull>(true); 6204 SetPackedFlag<kFlagCanBeNull>(true); 6205 DCHECK_EQ(input->GetType(), Primitive::kPrimNot); 6206 SetRawInputAt(0, input); 6207 } 6208 6209 // {Get,Set}Upper* should only be used in reference type propagation. 6210 const ReferenceTypeInfo& GetUpperBound() const { return upper_bound_; } 6211 bool GetUpperCanBeNull() const { return GetPackedFlag<kFlagUpperCanBeNull>(); } 6212 void SetUpperBound(const ReferenceTypeInfo& upper_bound, bool can_be_null); 6213 6214 void SetCanBeNull(bool can_be_null) { 6215 DCHECK(GetUpperCanBeNull() || !can_be_null); 6216 SetPackedFlag<kFlagCanBeNull>(can_be_null); 6217 } 6218 6219 bool CanBeNull() const OVERRIDE { return GetPackedFlag<kFlagCanBeNull>(); } 6220 6221 DECLARE_INSTRUCTION(BoundType); 6222 6223 private: 6224 // Represents the top constraint that can_be_null_ cannot exceed (i.e. if this 6225 // is false then CanBeNull() cannot be true). 6226 static constexpr size_t kFlagUpperCanBeNull = kNumberOfExpressionPackedBits; 6227 static constexpr size_t kFlagCanBeNull = kFlagUpperCanBeNull + 1; 6228 static constexpr size_t kNumberOfBoundTypePackedBits = kFlagCanBeNull + 1; 6229 static_assert(kNumberOfBoundTypePackedBits <= kMaxNumberOfPackedBits, "Too many packed fields."); 6230 6231 // Encodes the most upper class that this instruction can have. In other words 6232 // it is always the case that GetUpperBound().IsSupertypeOf(GetReferenceType()). 6233 // It is used to bound the type in cases like: 6234 // if (x instanceof ClassX) { 6235 // // uper_bound_ will be ClassX 6236 // } 6237 ReferenceTypeInfo upper_bound_; 6238 6239 DISALLOW_COPY_AND_ASSIGN(HBoundType); 6240}; 6241 6242class HCheckCast FINAL : public HTemplateInstruction<2> { 6243 public: 6244 HCheckCast(HInstruction* object, 6245 HLoadClass* constant, 6246 TypeCheckKind check_kind, 6247 uint32_t dex_pc) 6248 : HTemplateInstruction(SideEffects::CanTriggerGC(), dex_pc) { 6249 SetPackedField<TypeCheckKindField>(check_kind); 6250 SetPackedFlag<kFlagMustDoNullCheck>(true); 6251 SetRawInputAt(0, object); 6252 SetRawInputAt(1, constant); 6253 } 6254 6255 bool CanBeMoved() const OVERRIDE { return true; } 6256 6257 bool InstructionDataEquals(const HInstruction* other ATTRIBUTE_UNUSED) const OVERRIDE { 6258 return true; 6259 } 6260 6261 bool NeedsEnvironment() const OVERRIDE { 6262 // Instruction may throw a CheckCastError. 6263 return true; 6264 } 6265 6266 bool CanThrow() const OVERRIDE { return true; } 6267 6268 bool MustDoNullCheck() const { return GetPackedFlag<kFlagMustDoNullCheck>(); } 6269 void ClearMustDoNullCheck() { SetPackedFlag<kFlagMustDoNullCheck>(false); } 6270 TypeCheckKind GetTypeCheckKind() const { return GetPackedField<TypeCheckKindField>(); } 6271 bool IsExactCheck() const { return GetTypeCheckKind() == TypeCheckKind::kExactCheck; } 6272 6273 DECLARE_INSTRUCTION(CheckCast); 6274 6275 private: 6276 static constexpr size_t kFieldTypeCheckKind = kNumberOfGenericPackedBits; 6277 static constexpr size_t kFieldTypeCheckKindSize = 6278 MinimumBitsToStore(static_cast<size_t>(TypeCheckKind::kLast)); 6279 static constexpr size_t kFlagMustDoNullCheck = kFieldTypeCheckKind + kFieldTypeCheckKindSize; 6280 static constexpr size_t kNumberOfCheckCastPackedBits = kFlagMustDoNullCheck + 1; 6281 static_assert(kNumberOfCheckCastPackedBits <= kMaxNumberOfPackedBits, "Too many packed fields."); 6282 using TypeCheckKindField = BitField<TypeCheckKind, kFieldTypeCheckKind, kFieldTypeCheckKindSize>; 6283 6284 DISALLOW_COPY_AND_ASSIGN(HCheckCast); 6285}; 6286 6287/** 6288 * @brief Memory barrier types (see "The JSR-133 Cookbook for Compiler Writers"). 6289 * @details We define the combined barrier types that are actually required 6290 * by the Java Memory Model, rather than using exactly the terminology from 6291 * the JSR-133 cookbook. These should, in many cases, be replaced by acquire/release 6292 * primitives. Note that the JSR-133 cookbook generally does not deal with 6293 * store atomicity issues, and the recipes there are not always entirely sufficient. 6294 * The current recipe is as follows: 6295 * -# Use AnyStore ~= (LoadStore | StoreStore) ~= release barrier before volatile store. 6296 * -# Use AnyAny barrier after volatile store. (StoreLoad is as expensive.) 6297 * -# Use LoadAny barrier ~= (LoadLoad | LoadStore) ~= acquire barrier after each volatile load. 6298 * -# Use StoreStore barrier after all stores but before return from any constructor whose 6299 * class has final fields. 6300 * -# Use NTStoreStore to order non-temporal stores with respect to all later 6301 * store-to-memory instructions. Only generated together with non-temporal stores. 6302 */ 6303enum MemBarrierKind { 6304 kAnyStore, 6305 kLoadAny, 6306 kStoreStore, 6307 kAnyAny, 6308 kNTStoreStore, 6309 kLastBarrierKind = kNTStoreStore 6310}; 6311std::ostream& operator<<(std::ostream& os, const MemBarrierKind& kind); 6312 6313class HMemoryBarrier FINAL : public HTemplateInstruction<0> { 6314 public: 6315 explicit HMemoryBarrier(MemBarrierKind barrier_kind, uint32_t dex_pc = kNoDexPc) 6316 : HTemplateInstruction( 6317 SideEffects::AllWritesAndReads(), dex_pc) { // Assume write/read on all fields/arrays. 6318 SetPackedField<BarrierKindField>(barrier_kind); 6319 } 6320 6321 MemBarrierKind GetBarrierKind() { return GetPackedField<BarrierKindField>(); } 6322 6323 DECLARE_INSTRUCTION(MemoryBarrier); 6324 6325 private: 6326 static constexpr size_t kFieldBarrierKind = HInstruction::kNumberOfGenericPackedBits; 6327 static constexpr size_t kFieldBarrierKindSize = 6328 MinimumBitsToStore(static_cast<size_t>(kLastBarrierKind)); 6329 static constexpr size_t kNumberOfMemoryBarrierPackedBits = 6330 kFieldBarrierKind + kFieldBarrierKindSize; 6331 static_assert(kNumberOfMemoryBarrierPackedBits <= kMaxNumberOfPackedBits, 6332 "Too many packed fields."); 6333 using BarrierKindField = BitField<MemBarrierKind, kFieldBarrierKind, kFieldBarrierKindSize>; 6334 6335 DISALLOW_COPY_AND_ASSIGN(HMemoryBarrier); 6336}; 6337 6338class HMonitorOperation FINAL : public HTemplateInstruction<1> { 6339 public: 6340 enum class OperationKind { 6341 kEnter, 6342 kExit, 6343 kLast = kExit 6344 }; 6345 6346 HMonitorOperation(HInstruction* object, OperationKind kind, uint32_t dex_pc) 6347 : HTemplateInstruction( 6348 SideEffects::AllExceptGCDependency(), // Assume write/read on all fields/arrays. 6349 dex_pc) { 6350 SetPackedField<OperationKindField>(kind); 6351 SetRawInputAt(0, object); 6352 } 6353 6354 // Instruction may go into runtime, so we need an environment. 6355 bool NeedsEnvironment() const OVERRIDE { return true; } 6356 6357 bool CanThrow() const OVERRIDE { 6358 // Verifier guarantees that monitor-exit cannot throw. 6359 // This is important because it allows the HGraphBuilder to remove 6360 // a dead throw-catch loop generated for `synchronized` blocks/methods. 6361 return IsEnter(); 6362 } 6363 6364 OperationKind GetOperationKind() const { return GetPackedField<OperationKindField>(); } 6365 bool IsEnter() const { return GetOperationKind() == OperationKind::kEnter; } 6366 6367 DECLARE_INSTRUCTION(MonitorOperation); 6368 6369 private: 6370 static constexpr size_t kFieldOperationKind = HInstruction::kNumberOfGenericPackedBits; 6371 static constexpr size_t kFieldOperationKindSize = 6372 MinimumBitsToStore(static_cast<size_t>(OperationKind::kLast)); 6373 static constexpr size_t kNumberOfMonitorOperationPackedBits = 6374 kFieldOperationKind + kFieldOperationKindSize; 6375 static_assert(kNumberOfMonitorOperationPackedBits <= HInstruction::kMaxNumberOfPackedBits, 6376 "Too many packed fields."); 6377 using OperationKindField = BitField<OperationKind, kFieldOperationKind, kFieldOperationKindSize>; 6378 6379 private: 6380 DISALLOW_COPY_AND_ASSIGN(HMonitorOperation); 6381}; 6382 6383class HSelect FINAL : public HExpression<3> { 6384 public: 6385 HSelect(HInstruction* condition, 6386 HInstruction* true_value, 6387 HInstruction* false_value, 6388 uint32_t dex_pc) 6389 : HExpression(HPhi::ToPhiType(true_value->GetType()), SideEffects::None(), dex_pc) { 6390 DCHECK_EQ(HPhi::ToPhiType(true_value->GetType()), HPhi::ToPhiType(false_value->GetType())); 6391 6392 // First input must be `true_value` or `false_value` to allow codegens to 6393 // use the SameAsFirstInput allocation policy. We make it `false_value`, so 6394 // that architectures which implement HSelect as a conditional move also 6395 // will not need to invert the condition. 6396 SetRawInputAt(0, false_value); 6397 SetRawInputAt(1, true_value); 6398 SetRawInputAt(2, condition); 6399 } 6400 6401 HInstruction* GetFalseValue() const { return InputAt(0); } 6402 HInstruction* GetTrueValue() const { return InputAt(1); } 6403 HInstruction* GetCondition() const { return InputAt(2); } 6404 6405 bool CanBeMoved() const OVERRIDE { return true; } 6406 bool InstructionDataEquals(const HInstruction* other ATTRIBUTE_UNUSED) const OVERRIDE { 6407 return true; 6408 } 6409 6410 bool CanBeNull() const OVERRIDE { 6411 return GetTrueValue()->CanBeNull() || GetFalseValue()->CanBeNull(); 6412 } 6413 6414 DECLARE_INSTRUCTION(Select); 6415 6416 private: 6417 DISALLOW_COPY_AND_ASSIGN(HSelect); 6418}; 6419 6420class MoveOperands : public ArenaObject<kArenaAllocMoveOperands> { 6421 public: 6422 MoveOperands(Location source, 6423 Location destination, 6424 Primitive::Type type, 6425 HInstruction* instruction) 6426 : source_(source), destination_(destination), type_(type), instruction_(instruction) {} 6427 6428 Location GetSource() const { return source_; } 6429 Location GetDestination() const { return destination_; } 6430 6431 void SetSource(Location value) { source_ = value; } 6432 void SetDestination(Location value) { destination_ = value; } 6433 6434 // The parallel move resolver marks moves as "in-progress" by clearing the 6435 // destination (but not the source). 6436 Location MarkPending() { 6437 DCHECK(!IsPending()); 6438 Location dest = destination_; 6439 destination_ = Location::NoLocation(); 6440 return dest; 6441 } 6442 6443 void ClearPending(Location dest) { 6444 DCHECK(IsPending()); 6445 destination_ = dest; 6446 } 6447 6448 bool IsPending() const { 6449 DCHECK(source_.IsValid() || destination_.IsInvalid()); 6450 return destination_.IsInvalid() && source_.IsValid(); 6451 } 6452 6453 // True if this blocks a move from the given location. 6454 bool Blocks(Location loc) const { 6455 return !IsEliminated() && source_.OverlapsWith(loc); 6456 } 6457 6458 // A move is redundant if it's been eliminated, if its source and 6459 // destination are the same, or if its destination is unneeded. 6460 bool IsRedundant() const { 6461 return IsEliminated() || destination_.IsInvalid() || source_.Equals(destination_); 6462 } 6463 6464 // We clear both operands to indicate move that's been eliminated. 6465 void Eliminate() { 6466 source_ = destination_ = Location::NoLocation(); 6467 } 6468 6469 bool IsEliminated() const { 6470 DCHECK(!source_.IsInvalid() || destination_.IsInvalid()); 6471 return source_.IsInvalid(); 6472 } 6473 6474 Primitive::Type GetType() const { return type_; } 6475 6476 bool Is64BitMove() const { 6477 return Primitive::Is64BitType(type_); 6478 } 6479 6480 HInstruction* GetInstruction() const { return instruction_; } 6481 6482 private: 6483 Location source_; 6484 Location destination_; 6485 // The type this move is for. 6486 Primitive::Type type_; 6487 // The instruction this move is assocatied with. Null when this move is 6488 // for moving an input in the expected locations of user (including a phi user). 6489 // This is only used in debug mode, to ensure we do not connect interval siblings 6490 // in the same parallel move. 6491 HInstruction* instruction_; 6492}; 6493 6494std::ostream& operator<<(std::ostream& os, const MoveOperands& rhs); 6495 6496static constexpr size_t kDefaultNumberOfMoves = 4; 6497 6498class HParallelMove FINAL : public HTemplateInstruction<0> { 6499 public: 6500 explicit HParallelMove(ArenaAllocator* arena, uint32_t dex_pc = kNoDexPc) 6501 : HTemplateInstruction(SideEffects::None(), dex_pc), 6502 moves_(arena->Adapter(kArenaAllocMoveOperands)) { 6503 moves_.reserve(kDefaultNumberOfMoves); 6504 } 6505 6506 void AddMove(Location source, 6507 Location destination, 6508 Primitive::Type type, 6509 HInstruction* instruction) { 6510 DCHECK(source.IsValid()); 6511 DCHECK(destination.IsValid()); 6512 if (kIsDebugBuild) { 6513 if (instruction != nullptr) { 6514 for (const MoveOperands& move : moves_) { 6515 if (move.GetInstruction() == instruction) { 6516 // Special case the situation where the move is for the spill slot 6517 // of the instruction. 6518 if ((GetPrevious() == instruction) 6519 || ((GetPrevious() == nullptr) 6520 && instruction->IsPhi() 6521 && instruction->GetBlock() == GetBlock())) { 6522 DCHECK_NE(destination.GetKind(), move.GetDestination().GetKind()) 6523 << "Doing parallel moves for the same instruction."; 6524 } else { 6525 DCHECK(false) << "Doing parallel moves for the same instruction."; 6526 } 6527 } 6528 } 6529 } 6530 for (const MoveOperands& move : moves_) { 6531 DCHECK(!destination.OverlapsWith(move.GetDestination())) 6532 << "Overlapped destination for two moves in a parallel move: " 6533 << move.GetSource() << " ==> " << move.GetDestination() << " and " 6534 << source << " ==> " << destination; 6535 } 6536 } 6537 moves_.emplace_back(source, destination, type, instruction); 6538 } 6539 6540 MoveOperands* MoveOperandsAt(size_t index) { 6541 return &moves_[index]; 6542 } 6543 6544 size_t NumMoves() const { return moves_.size(); } 6545 6546 DECLARE_INSTRUCTION(ParallelMove); 6547 6548 private: 6549 ArenaVector<MoveOperands> moves_; 6550 6551 DISALLOW_COPY_AND_ASSIGN(HParallelMove); 6552}; 6553 6554} // namespace art 6555 6556#if defined(ART_ENABLE_CODEGEN_arm) || defined(ART_ENABLE_CODEGEN_arm64) 6557#include "nodes_shared.h" 6558#endif 6559#ifdef ART_ENABLE_CODEGEN_arm 6560#include "nodes_arm.h" 6561#endif 6562#ifdef ART_ENABLE_CODEGEN_arm64 6563#include "nodes_arm64.h" 6564#endif 6565#ifdef ART_ENABLE_CODEGEN_mips 6566#include "nodes_mips.h" 6567#endif 6568#ifdef ART_ENABLE_CODEGEN_x86 6569#include "nodes_x86.h" 6570#endif 6571 6572namespace art { 6573 6574class HGraphVisitor : public ValueObject { 6575 public: 6576 explicit HGraphVisitor(HGraph* graph) : graph_(graph) {} 6577 virtual ~HGraphVisitor() {} 6578 6579 virtual void VisitInstruction(HInstruction* instruction ATTRIBUTE_UNUSED) {} 6580 virtual void VisitBasicBlock(HBasicBlock* block); 6581 6582 // Visit the graph following basic block insertion order. 6583 void VisitInsertionOrder(); 6584 6585 // Visit the graph following dominator tree reverse post-order. 6586 void VisitReversePostOrder(); 6587 6588 HGraph* GetGraph() const { return graph_; } 6589 6590 // Visit functions for instruction classes. 6591#define DECLARE_VISIT_INSTRUCTION(name, super) \ 6592 virtual void Visit##name(H##name* instr) { VisitInstruction(instr); } 6593 6594 FOR_EACH_INSTRUCTION(DECLARE_VISIT_INSTRUCTION) 6595 6596#undef DECLARE_VISIT_INSTRUCTION 6597 6598 private: 6599 HGraph* const graph_; 6600 6601 DISALLOW_COPY_AND_ASSIGN(HGraphVisitor); 6602}; 6603 6604class HGraphDelegateVisitor : public HGraphVisitor { 6605 public: 6606 explicit HGraphDelegateVisitor(HGraph* graph) : HGraphVisitor(graph) {} 6607 virtual ~HGraphDelegateVisitor() {} 6608 6609 // Visit functions that delegate to to super class. 6610#define DECLARE_VISIT_INSTRUCTION(name, super) \ 6611 void Visit##name(H##name* instr) OVERRIDE { Visit##super(instr); } 6612 6613 FOR_EACH_INSTRUCTION(DECLARE_VISIT_INSTRUCTION) 6614 6615#undef DECLARE_VISIT_INSTRUCTION 6616 6617 private: 6618 DISALLOW_COPY_AND_ASSIGN(HGraphDelegateVisitor); 6619}; 6620 6621class HInsertionOrderIterator : public ValueObject { 6622 public: 6623 explicit HInsertionOrderIterator(const HGraph& graph) : graph_(graph), index_(0) {} 6624 6625 bool Done() const { return index_ == graph_.GetBlocks().size(); } 6626 HBasicBlock* Current() const { return graph_.GetBlocks()[index_]; } 6627 void Advance() { ++index_; } 6628 6629 private: 6630 const HGraph& graph_; 6631 size_t index_; 6632 6633 DISALLOW_COPY_AND_ASSIGN(HInsertionOrderIterator); 6634}; 6635 6636class HReversePostOrderIterator : public ValueObject { 6637 public: 6638 explicit HReversePostOrderIterator(const HGraph& graph) : graph_(graph), index_(0) { 6639 // Check that reverse post order of the graph has been built. 6640 DCHECK(!graph.GetReversePostOrder().empty()); 6641 } 6642 6643 bool Done() const { return index_ == graph_.GetReversePostOrder().size(); } 6644 HBasicBlock* Current() const { return graph_.GetReversePostOrder()[index_]; } 6645 void Advance() { ++index_; } 6646 6647 private: 6648 const HGraph& graph_; 6649 size_t index_; 6650 6651 DISALLOW_COPY_AND_ASSIGN(HReversePostOrderIterator); 6652}; 6653 6654class HPostOrderIterator : public ValueObject { 6655 public: 6656 explicit HPostOrderIterator(const HGraph& graph) 6657 : graph_(graph), index_(graph_.GetReversePostOrder().size()) { 6658 // Check that reverse post order of the graph has been built. 6659 DCHECK(!graph.GetReversePostOrder().empty()); 6660 } 6661 6662 bool Done() const { return index_ == 0; } 6663 HBasicBlock* Current() const { return graph_.GetReversePostOrder()[index_ - 1u]; } 6664 void Advance() { --index_; } 6665 6666 private: 6667 const HGraph& graph_; 6668 size_t index_; 6669 6670 DISALLOW_COPY_AND_ASSIGN(HPostOrderIterator); 6671}; 6672 6673// Iterator over the blocks that art part of the loop. Includes blocks part 6674// of an inner loop. The order in which the blocks are iterated is on their 6675// block id. 6676class HBlocksInLoopIterator : public ValueObject { 6677 public: 6678 explicit HBlocksInLoopIterator(const HLoopInformation& info) 6679 : blocks_in_loop_(info.GetBlocks()), 6680 blocks_(info.GetHeader()->GetGraph()->GetBlocks()), 6681 index_(0) { 6682 if (!blocks_in_loop_.IsBitSet(index_)) { 6683 Advance(); 6684 } 6685 } 6686 6687 bool Done() const { return index_ == blocks_.size(); } 6688 HBasicBlock* Current() const { return blocks_[index_]; } 6689 void Advance() { 6690 ++index_; 6691 for (size_t e = blocks_.size(); index_ < e; ++index_) { 6692 if (blocks_in_loop_.IsBitSet(index_)) { 6693 break; 6694 } 6695 } 6696 } 6697 6698 private: 6699 const BitVector& blocks_in_loop_; 6700 const ArenaVector<HBasicBlock*>& blocks_; 6701 size_t index_; 6702 6703 DISALLOW_COPY_AND_ASSIGN(HBlocksInLoopIterator); 6704}; 6705 6706// Iterator over the blocks that art part of the loop. Includes blocks part 6707// of an inner loop. The order in which the blocks are iterated is reverse 6708// post order. 6709class HBlocksInLoopReversePostOrderIterator : public ValueObject { 6710 public: 6711 explicit HBlocksInLoopReversePostOrderIterator(const HLoopInformation& info) 6712 : blocks_in_loop_(info.GetBlocks()), 6713 blocks_(info.GetHeader()->GetGraph()->GetReversePostOrder()), 6714 index_(0) { 6715 if (!blocks_in_loop_.IsBitSet(blocks_[index_]->GetBlockId())) { 6716 Advance(); 6717 } 6718 } 6719 6720 bool Done() const { return index_ == blocks_.size(); } 6721 HBasicBlock* Current() const { return blocks_[index_]; } 6722 void Advance() { 6723 ++index_; 6724 for (size_t e = blocks_.size(); index_ < e; ++index_) { 6725 if (blocks_in_loop_.IsBitSet(blocks_[index_]->GetBlockId())) { 6726 break; 6727 } 6728 } 6729 } 6730 6731 private: 6732 const BitVector& blocks_in_loop_; 6733 const ArenaVector<HBasicBlock*>& blocks_; 6734 size_t index_; 6735 6736 DISALLOW_COPY_AND_ASSIGN(HBlocksInLoopReversePostOrderIterator); 6737}; 6738 6739inline int64_t Int64FromConstant(HConstant* constant) { 6740 if (constant->IsIntConstant()) { 6741 return constant->AsIntConstant()->GetValue(); 6742 } else if (constant->IsLongConstant()) { 6743 return constant->AsLongConstant()->GetValue(); 6744 } else { 6745 DCHECK(constant->IsNullConstant()) << constant->DebugName(); 6746 return 0; 6747 } 6748} 6749 6750#define INSTRUCTION_TYPE_CHECK(type, super) \ 6751 inline bool HInstruction::Is##type() const { return GetKind() == k##type; } \ 6752 inline const H##type* HInstruction::As##type() const { \ 6753 return Is##type() ? down_cast<const H##type*>(this) : nullptr; \ 6754 } \ 6755 inline H##type* HInstruction::As##type() { \ 6756 return Is##type() ? static_cast<H##type*>(this) : nullptr; \ 6757 } 6758 6759 FOR_EACH_CONCRETE_INSTRUCTION(INSTRUCTION_TYPE_CHECK) 6760#undef INSTRUCTION_TYPE_CHECK 6761 6762// Create space in `blocks` for adding `number_of_new_blocks` entries 6763// starting at location `at`. Blocks after `at` are moved accordingly. 6764inline void MakeRoomFor(ArenaVector<HBasicBlock*>* blocks, 6765 size_t number_of_new_blocks, 6766 size_t after) { 6767 DCHECK_LT(after, blocks->size()); 6768 size_t old_size = blocks->size(); 6769 size_t new_size = old_size + number_of_new_blocks; 6770 blocks->resize(new_size); 6771 std::copy_backward(blocks->begin() + after + 1u, blocks->begin() + old_size, blocks->end()); 6772} 6773 6774} // namespace art 6775 6776#endif // ART_COMPILER_OPTIMIZING_NODES_H_ 6777