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