nodes.h revision 2f10a5fb8c236a6786928f0323bd312c3ee9a4cc
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(X86FPNeg, Instruction) \ 1263 M(X86PackedSwitch, Instruction) 1264#endif 1265 1266#define FOR_EACH_CONCRETE_INSTRUCTION_X86_64(M) 1267 1268#define FOR_EACH_CONCRETE_INSTRUCTION(M) \ 1269 FOR_EACH_CONCRETE_INSTRUCTION_COMMON(M) \ 1270 FOR_EACH_CONCRETE_INSTRUCTION_ARM(M) \ 1271 FOR_EACH_CONCRETE_INSTRUCTION_ARM64(M) \ 1272 FOR_EACH_CONCRETE_INSTRUCTION_MIPS(M) \ 1273 FOR_EACH_CONCRETE_INSTRUCTION_MIPS64(M) \ 1274 FOR_EACH_CONCRETE_INSTRUCTION_X86(M) \ 1275 FOR_EACH_CONCRETE_INSTRUCTION_X86_64(M) 1276 1277#define FOR_EACH_ABSTRACT_INSTRUCTION(M) \ 1278 M(Condition, BinaryOperation) \ 1279 M(Constant, Instruction) \ 1280 M(UnaryOperation, Instruction) \ 1281 M(BinaryOperation, Instruction) \ 1282 M(Invoke, Instruction) 1283 1284#define FOR_EACH_INSTRUCTION(M) \ 1285 FOR_EACH_CONCRETE_INSTRUCTION(M) \ 1286 FOR_EACH_ABSTRACT_INSTRUCTION(M) 1287 1288#define FORWARD_DECLARATION(type, super) class H##type; 1289FOR_EACH_INSTRUCTION(FORWARD_DECLARATION) 1290#undef FORWARD_DECLARATION 1291 1292#define DECLARE_INSTRUCTION(type) \ 1293 InstructionKind GetKindInternal() const OVERRIDE { return k##type; } \ 1294 const char* DebugName() const OVERRIDE { return #type; } \ 1295 bool InstructionTypeEquals(HInstruction* other) const OVERRIDE { \ 1296 return other->Is##type(); \ 1297 } \ 1298 void Accept(HGraphVisitor* visitor) OVERRIDE 1299 1300#define DECLARE_ABSTRACT_INSTRUCTION(type) \ 1301 bool Is##type() const { return As##type() != nullptr; } \ 1302 const H##type* As##type() const { return this; } \ 1303 H##type* As##type() { return this; } 1304 1305template <typename T> class HUseList; 1306 1307template <typename T> 1308class HUseListNode : public ArenaObject<kArenaAllocUseListNode> { 1309 public: 1310 HUseListNode* GetPrevious() const { return prev_; } 1311 HUseListNode* GetNext() const { return next_; } 1312 T GetUser() const { return user_; } 1313 size_t GetIndex() const { return index_; } 1314 void SetIndex(size_t index) { index_ = index; } 1315 1316 private: 1317 HUseListNode(T user, size_t index) 1318 : user_(user), index_(index), prev_(nullptr), next_(nullptr) {} 1319 1320 T const user_; 1321 size_t index_; 1322 HUseListNode<T>* prev_; 1323 HUseListNode<T>* next_; 1324 1325 friend class HUseList<T>; 1326 1327 DISALLOW_COPY_AND_ASSIGN(HUseListNode); 1328}; 1329 1330template <typename T> 1331class HUseList : public ValueObject { 1332 public: 1333 HUseList() : first_(nullptr) {} 1334 1335 void Clear() { 1336 first_ = nullptr; 1337 } 1338 1339 // Adds a new entry at the beginning of the use list and returns 1340 // the newly created node. 1341 HUseListNode<T>* AddUse(T user, size_t index, ArenaAllocator* arena) { 1342 HUseListNode<T>* new_node = new (arena) HUseListNode<T>(user, index); 1343 if (IsEmpty()) { 1344 first_ = new_node; 1345 } else { 1346 first_->prev_ = new_node; 1347 new_node->next_ = first_; 1348 first_ = new_node; 1349 } 1350 return new_node; 1351 } 1352 1353 HUseListNode<T>* GetFirst() const { 1354 return first_; 1355 } 1356 1357 void Remove(HUseListNode<T>* node) { 1358 DCHECK(node != nullptr); 1359 DCHECK(Contains(node)); 1360 1361 if (node->prev_ != nullptr) { 1362 node->prev_->next_ = node->next_; 1363 } 1364 if (node->next_ != nullptr) { 1365 node->next_->prev_ = node->prev_; 1366 } 1367 if (node == first_) { 1368 first_ = node->next_; 1369 } 1370 } 1371 1372 bool Contains(const HUseListNode<T>* node) const { 1373 if (node == nullptr) { 1374 return false; 1375 } 1376 for (HUseListNode<T>* current = first_; current != nullptr; current = current->GetNext()) { 1377 if (current == node) { 1378 return true; 1379 } 1380 } 1381 return false; 1382 } 1383 1384 bool IsEmpty() const { 1385 return first_ == nullptr; 1386 } 1387 1388 bool HasOnlyOneUse() const { 1389 return first_ != nullptr && first_->next_ == nullptr; 1390 } 1391 1392 size_t SizeSlow() const { 1393 size_t count = 0; 1394 for (HUseListNode<T>* current = first_; current != nullptr; current = current->GetNext()) { 1395 ++count; 1396 } 1397 return count; 1398 } 1399 1400 private: 1401 HUseListNode<T>* first_; 1402}; 1403 1404template<typename T> 1405class HUseIterator : public ValueObject { 1406 public: 1407 explicit HUseIterator(const HUseList<T>& uses) : current_(uses.GetFirst()) {} 1408 1409 bool Done() const { return current_ == nullptr; } 1410 1411 void Advance() { 1412 DCHECK(!Done()); 1413 current_ = current_->GetNext(); 1414 } 1415 1416 HUseListNode<T>* Current() const { 1417 DCHECK(!Done()); 1418 return current_; 1419 } 1420 1421 private: 1422 HUseListNode<T>* current_; 1423 1424 friend class HValue; 1425}; 1426 1427// This class is used by HEnvironment and HInstruction classes to record the 1428// instructions they use and pointers to the corresponding HUseListNodes kept 1429// by the used instructions. 1430template <typename T> 1431class HUserRecord : public ValueObject { 1432 public: 1433 HUserRecord() : instruction_(nullptr), use_node_(nullptr) {} 1434 explicit HUserRecord(HInstruction* instruction) : instruction_(instruction), use_node_(nullptr) {} 1435 1436 HUserRecord(const HUserRecord<T>& old_record, HUseListNode<T>* use_node) 1437 : instruction_(old_record.instruction_), use_node_(use_node) { 1438 DCHECK(instruction_ != nullptr); 1439 DCHECK(use_node_ != nullptr); 1440 DCHECK(old_record.use_node_ == nullptr); 1441 } 1442 1443 HInstruction* GetInstruction() const { return instruction_; } 1444 HUseListNode<T>* GetUseNode() const { return use_node_; } 1445 1446 private: 1447 // Instruction used by the user. 1448 HInstruction* instruction_; 1449 1450 // Corresponding entry in the use list kept by 'instruction_'. 1451 HUseListNode<T>* use_node_; 1452}; 1453 1454/** 1455 * Side-effects representation. 1456 * 1457 * For write/read dependences on fields/arrays, the dependence analysis uses 1458 * type disambiguation (e.g. a float field write cannot modify the value of an 1459 * integer field read) and the access type (e.g. a reference array write cannot 1460 * modify the value of a reference field read [although it may modify the 1461 * reference fetch prior to reading the field, which is represented by its own 1462 * write/read dependence]). The analysis makes conservative points-to 1463 * assumptions on reference types (e.g. two same typed arrays are assumed to be 1464 * the same, and any reference read depends on any reference read without 1465 * further regard of its type). 1466 * 1467 * The internal representation uses 38-bit and is described in the table below. 1468 * The first line indicates the side effect, and for field/array accesses the 1469 * second line indicates the type of the access (in the order of the 1470 * Primitive::Type enum). 1471 * The two numbered lines below indicate the bit position in the bitfield (read 1472 * vertically). 1473 * 1474 * |Depends on GC|ARRAY-R |FIELD-R |Can trigger GC|ARRAY-W |FIELD-W | 1475 * +-------------+---------+---------+--------------+---------+---------+ 1476 * | |DFJISCBZL|DFJISCBZL| |DFJISCBZL|DFJISCBZL| 1477 * | 3 |333333322|222222221| 1 |111111110|000000000| 1478 * | 7 |654321098|765432109| 8 |765432109|876543210| 1479 * 1480 * Note that, to ease the implementation, 'changes' bits are least significant 1481 * bits, while 'dependency' bits are most significant bits. 1482 */ 1483class SideEffects : public ValueObject { 1484 public: 1485 SideEffects() : flags_(0) {} 1486 1487 static SideEffects None() { 1488 return SideEffects(0); 1489 } 1490 1491 static SideEffects All() { 1492 return SideEffects(kAllChangeBits | kAllDependOnBits); 1493 } 1494 1495 static SideEffects AllChanges() { 1496 return SideEffects(kAllChangeBits); 1497 } 1498 1499 static SideEffects AllDependencies() { 1500 return SideEffects(kAllDependOnBits); 1501 } 1502 1503 static SideEffects AllExceptGCDependency() { 1504 return AllWritesAndReads().Union(SideEffects::CanTriggerGC()); 1505 } 1506 1507 static SideEffects AllWritesAndReads() { 1508 return SideEffects(kAllWrites | kAllReads); 1509 } 1510 1511 static SideEffects AllWrites() { 1512 return SideEffects(kAllWrites); 1513 } 1514 1515 static SideEffects AllReads() { 1516 return SideEffects(kAllReads); 1517 } 1518 1519 static SideEffects FieldWriteOfType(Primitive::Type type, bool is_volatile) { 1520 return is_volatile 1521 ? AllWritesAndReads() 1522 : SideEffects(TypeFlagWithAlias(type, kFieldWriteOffset)); 1523 } 1524 1525 static SideEffects ArrayWriteOfType(Primitive::Type type) { 1526 return SideEffects(TypeFlagWithAlias(type, kArrayWriteOffset)); 1527 } 1528 1529 static SideEffects FieldReadOfType(Primitive::Type type, bool is_volatile) { 1530 return is_volatile 1531 ? AllWritesAndReads() 1532 : SideEffects(TypeFlagWithAlias(type, kFieldReadOffset)); 1533 } 1534 1535 static SideEffects ArrayReadOfType(Primitive::Type type) { 1536 return SideEffects(TypeFlagWithAlias(type, kArrayReadOffset)); 1537 } 1538 1539 static SideEffects CanTriggerGC() { 1540 return SideEffects(1ULL << kCanTriggerGCBit); 1541 } 1542 1543 static SideEffects DependsOnGC() { 1544 return SideEffects(1ULL << kDependsOnGCBit); 1545 } 1546 1547 // Combines the side-effects of this and the other. 1548 SideEffects Union(SideEffects other) const { 1549 return SideEffects(flags_ | other.flags_); 1550 } 1551 1552 SideEffects Exclusion(SideEffects other) const { 1553 return SideEffects(flags_ & ~other.flags_); 1554 } 1555 1556 void Add(SideEffects other) { 1557 flags_ |= other.flags_; 1558 } 1559 1560 bool Includes(SideEffects other) const { 1561 return (other.flags_ & flags_) == other.flags_; 1562 } 1563 1564 bool HasSideEffects() const { 1565 return (flags_ & kAllChangeBits); 1566 } 1567 1568 bool HasDependencies() const { 1569 return (flags_ & kAllDependOnBits); 1570 } 1571 1572 // Returns true if there are no side effects or dependencies. 1573 bool DoesNothing() const { 1574 return flags_ == 0; 1575 } 1576 1577 // Returns true if something is written. 1578 bool DoesAnyWrite() const { 1579 return (flags_ & kAllWrites); 1580 } 1581 1582 // Returns true if something is read. 1583 bool DoesAnyRead() const { 1584 return (flags_ & kAllReads); 1585 } 1586 1587 // Returns true if potentially everything is written and read 1588 // (every type and every kind of access). 1589 bool DoesAllReadWrite() const { 1590 return (flags_ & (kAllWrites | kAllReads)) == (kAllWrites | kAllReads); 1591 } 1592 1593 bool DoesAll() const { 1594 return flags_ == (kAllChangeBits | kAllDependOnBits); 1595 } 1596 1597 // Returns true if `this` may read something written by `other`. 1598 bool MayDependOn(SideEffects other) const { 1599 const uint64_t depends_on_flags = (flags_ & kAllDependOnBits) >> kChangeBits; 1600 return (other.flags_ & depends_on_flags); 1601 } 1602 1603 // Returns string representation of flags (for debugging only). 1604 // Format: |x|DFJISCBZL|DFJISCBZL|y|DFJISCBZL|DFJISCBZL| 1605 std::string ToString() const { 1606 std::string flags = "|"; 1607 for (int s = kLastBit; s >= 0; s--) { 1608 bool current_bit_is_set = ((flags_ >> s) & 1) != 0; 1609 if ((s == kDependsOnGCBit) || (s == kCanTriggerGCBit)) { 1610 // This is a bit for the GC side effect. 1611 if (current_bit_is_set) { 1612 flags += "GC"; 1613 } 1614 flags += "|"; 1615 } else { 1616 // This is a bit for the array/field analysis. 1617 // The underscore character stands for the 'can trigger GC' bit. 1618 static const char *kDebug = "LZBCSIJFDLZBCSIJFD_LZBCSIJFDLZBCSIJFD"; 1619 if (current_bit_is_set) { 1620 flags += kDebug[s]; 1621 } 1622 if ((s == kFieldWriteOffset) || (s == kArrayWriteOffset) || 1623 (s == kFieldReadOffset) || (s == kArrayReadOffset)) { 1624 flags += "|"; 1625 } 1626 } 1627 } 1628 return flags; 1629 } 1630 1631 bool Equals(const SideEffects& other) const { return flags_ == other.flags_; } 1632 1633 private: 1634 static constexpr int kFieldArrayAnalysisBits = 9; 1635 1636 static constexpr int kFieldWriteOffset = 0; 1637 static constexpr int kArrayWriteOffset = kFieldWriteOffset + kFieldArrayAnalysisBits; 1638 static constexpr int kLastBitForWrites = kArrayWriteOffset + kFieldArrayAnalysisBits - 1; 1639 static constexpr int kCanTriggerGCBit = kLastBitForWrites + 1; 1640 1641 static constexpr int kChangeBits = kCanTriggerGCBit + 1; 1642 1643 static constexpr int kFieldReadOffset = kCanTriggerGCBit + 1; 1644 static constexpr int kArrayReadOffset = kFieldReadOffset + kFieldArrayAnalysisBits; 1645 static constexpr int kLastBitForReads = kArrayReadOffset + kFieldArrayAnalysisBits - 1; 1646 static constexpr int kDependsOnGCBit = kLastBitForReads + 1; 1647 1648 static constexpr int kLastBit = kDependsOnGCBit; 1649 static constexpr int kDependOnBits = kLastBit + 1 - kChangeBits; 1650 1651 // Aliases. 1652 1653 static_assert(kChangeBits == kDependOnBits, 1654 "the 'change' bits should match the 'depend on' bits."); 1655 1656 static constexpr uint64_t kAllChangeBits = ((1ULL << kChangeBits) - 1); 1657 static constexpr uint64_t kAllDependOnBits = ((1ULL << kDependOnBits) - 1) << kChangeBits; 1658 static constexpr uint64_t kAllWrites = 1659 ((1ULL << (kLastBitForWrites + 1 - kFieldWriteOffset)) - 1) << kFieldWriteOffset; 1660 static constexpr uint64_t kAllReads = 1661 ((1ULL << (kLastBitForReads + 1 - kFieldReadOffset)) - 1) << kFieldReadOffset; 1662 1663 // Work around the fact that HIR aliases I/F and J/D. 1664 // TODO: remove this interceptor once HIR types are clean 1665 static uint64_t TypeFlagWithAlias(Primitive::Type type, int offset) { 1666 switch (type) { 1667 case Primitive::kPrimInt: 1668 case Primitive::kPrimFloat: 1669 return TypeFlag(Primitive::kPrimInt, offset) | 1670 TypeFlag(Primitive::kPrimFloat, offset); 1671 case Primitive::kPrimLong: 1672 case Primitive::kPrimDouble: 1673 return TypeFlag(Primitive::kPrimLong, offset) | 1674 TypeFlag(Primitive::kPrimDouble, offset); 1675 default: 1676 return TypeFlag(type, offset); 1677 } 1678 } 1679 1680 // Translates type to bit flag. 1681 static uint64_t TypeFlag(Primitive::Type type, int offset) { 1682 CHECK_NE(type, Primitive::kPrimVoid); 1683 const uint64_t one = 1; 1684 const int shift = type; // 0-based consecutive enum 1685 DCHECK_LE(kFieldWriteOffset, shift); 1686 DCHECK_LT(shift, kArrayWriteOffset); 1687 return one << (type + offset); 1688 } 1689 1690 // Private constructor on direct flags value. 1691 explicit SideEffects(uint64_t flags) : flags_(flags) {} 1692 1693 uint64_t flags_; 1694}; 1695 1696// A HEnvironment object contains the values of virtual registers at a given location. 1697class HEnvironment : public ArenaObject<kArenaAllocEnvironment> { 1698 public: 1699 HEnvironment(ArenaAllocator* arena, 1700 size_t number_of_vregs, 1701 const DexFile& dex_file, 1702 uint32_t method_idx, 1703 uint32_t dex_pc, 1704 InvokeType invoke_type, 1705 HInstruction* holder) 1706 : vregs_(number_of_vregs, arena->Adapter(kArenaAllocEnvironmentVRegs)), 1707 locations_(number_of_vregs, arena->Adapter(kArenaAllocEnvironmentLocations)), 1708 parent_(nullptr), 1709 dex_file_(dex_file), 1710 method_idx_(method_idx), 1711 dex_pc_(dex_pc), 1712 invoke_type_(invoke_type), 1713 holder_(holder) { 1714 } 1715 1716 HEnvironment(ArenaAllocator* arena, const HEnvironment& to_copy, HInstruction* holder) 1717 : HEnvironment(arena, 1718 to_copy.Size(), 1719 to_copy.GetDexFile(), 1720 to_copy.GetMethodIdx(), 1721 to_copy.GetDexPc(), 1722 to_copy.GetInvokeType(), 1723 holder) {} 1724 1725 void SetAndCopyParentChain(ArenaAllocator* allocator, HEnvironment* parent) { 1726 if (parent_ != nullptr) { 1727 parent_->SetAndCopyParentChain(allocator, parent); 1728 } else { 1729 parent_ = new (allocator) HEnvironment(allocator, *parent, holder_); 1730 parent_->CopyFrom(parent); 1731 if (parent->GetParent() != nullptr) { 1732 parent_->SetAndCopyParentChain(allocator, parent->GetParent()); 1733 } 1734 } 1735 } 1736 1737 void CopyFrom(const ArenaVector<HInstruction*>& locals); 1738 void CopyFrom(HEnvironment* environment); 1739 1740 // Copy from `env`. If it's a loop phi for `loop_header`, copy the first 1741 // input to the loop phi instead. This is for inserting instructions that 1742 // require an environment (like HDeoptimization) in the loop pre-header. 1743 void CopyFromWithLoopPhiAdjustment(HEnvironment* env, HBasicBlock* loop_header); 1744 1745 void SetRawEnvAt(size_t index, HInstruction* instruction) { 1746 vregs_[index] = HUserRecord<HEnvironment*>(instruction); 1747 } 1748 1749 HInstruction* GetInstructionAt(size_t index) const { 1750 return vregs_[index].GetInstruction(); 1751 } 1752 1753 void RemoveAsUserOfInput(size_t index) const; 1754 1755 size_t Size() const { return vregs_.size(); } 1756 1757 HEnvironment* GetParent() const { return parent_; } 1758 1759 void SetLocationAt(size_t index, Location location) { 1760 locations_[index] = location; 1761 } 1762 1763 Location GetLocationAt(size_t index) const { 1764 return locations_[index]; 1765 } 1766 1767 uint32_t GetDexPc() const { 1768 return dex_pc_; 1769 } 1770 1771 uint32_t GetMethodIdx() const { 1772 return method_idx_; 1773 } 1774 1775 InvokeType GetInvokeType() const { 1776 return invoke_type_; 1777 } 1778 1779 const DexFile& GetDexFile() const { 1780 return dex_file_; 1781 } 1782 1783 HInstruction* GetHolder() const { 1784 return holder_; 1785 } 1786 1787 1788 bool IsFromInlinedInvoke() const { 1789 return GetParent() != nullptr; 1790 } 1791 1792 private: 1793 // Record instructions' use entries of this environment for constant-time removal. 1794 // It should only be called by HInstruction when a new environment use is added. 1795 void RecordEnvUse(HUseListNode<HEnvironment*>* env_use) { 1796 DCHECK(env_use->GetUser() == this); 1797 size_t index = env_use->GetIndex(); 1798 vregs_[index] = HUserRecord<HEnvironment*>(vregs_[index], env_use); 1799 } 1800 1801 ArenaVector<HUserRecord<HEnvironment*>> vregs_; 1802 ArenaVector<Location> locations_; 1803 HEnvironment* parent_; 1804 const DexFile& dex_file_; 1805 const uint32_t method_idx_; 1806 const uint32_t dex_pc_; 1807 const InvokeType invoke_type_; 1808 1809 // The instruction that holds this environment. 1810 HInstruction* const holder_; 1811 1812 friend class HInstruction; 1813 1814 DISALLOW_COPY_AND_ASSIGN(HEnvironment); 1815}; 1816 1817class HInstruction : public ArenaObject<kArenaAllocInstruction> { 1818 public: 1819 HInstruction(SideEffects side_effects, uint32_t dex_pc) 1820 : previous_(nullptr), 1821 next_(nullptr), 1822 block_(nullptr), 1823 dex_pc_(dex_pc), 1824 id_(-1), 1825 ssa_index_(-1), 1826 emitted_at_use_site_(false), 1827 environment_(nullptr), 1828 locations_(nullptr), 1829 live_interval_(nullptr), 1830 lifetime_position_(kNoLifetime), 1831 side_effects_(side_effects), 1832 reference_type_info_(ReferenceTypeInfo::CreateInvalid()) {} 1833 1834 virtual ~HInstruction() {} 1835 1836#define DECLARE_KIND(type, super) k##type, 1837 enum InstructionKind { 1838 FOR_EACH_INSTRUCTION(DECLARE_KIND) 1839 }; 1840#undef DECLARE_KIND 1841 1842 HInstruction* GetNext() const { return next_; } 1843 HInstruction* GetPrevious() const { return previous_; } 1844 1845 HInstruction* GetNextDisregardingMoves() const; 1846 HInstruction* GetPreviousDisregardingMoves() const; 1847 1848 HBasicBlock* GetBlock() const { return block_; } 1849 ArenaAllocator* GetArena() const { return block_->GetGraph()->GetArena(); } 1850 void SetBlock(HBasicBlock* block) { block_ = block; } 1851 bool IsInBlock() const { return block_ != nullptr; } 1852 bool IsInLoop() const { return block_->IsInLoop(); } 1853 bool IsLoopHeaderPhi() const { return IsPhi() && block_->IsLoopHeader(); } 1854 bool IsIrreducibleLoopHeaderPhi() const { 1855 return IsLoopHeaderPhi() && GetBlock()->GetLoopInformation()->IsIrreducible(); 1856 } 1857 1858 virtual size_t InputCount() const = 0; 1859 HInstruction* InputAt(size_t i) const { return InputRecordAt(i).GetInstruction(); } 1860 1861 virtual void Accept(HGraphVisitor* visitor) = 0; 1862 virtual const char* DebugName() const = 0; 1863 1864 virtual Primitive::Type GetType() const { return Primitive::kPrimVoid; } 1865 void SetRawInputAt(size_t index, HInstruction* input) { 1866 SetRawInputRecordAt(index, HUserRecord<HInstruction*>(input)); 1867 } 1868 1869 virtual bool NeedsEnvironment() const { return false; } 1870 1871 uint32_t GetDexPc() const { return dex_pc_; } 1872 1873 virtual bool IsControlFlow() const { return false; } 1874 1875 virtual bool CanThrow() const { return false; } 1876 bool CanThrowIntoCatchBlock() const { return CanThrow() && block_->IsTryBlock(); } 1877 1878 bool HasSideEffects() const { return side_effects_.HasSideEffects(); } 1879 bool DoesAnyWrite() const { return side_effects_.DoesAnyWrite(); } 1880 1881 // Does not apply for all instructions, but having this at top level greatly 1882 // simplifies the null check elimination. 1883 // TODO: Consider merging can_be_null into ReferenceTypeInfo. 1884 virtual bool CanBeNull() const { 1885 DCHECK_EQ(GetType(), Primitive::kPrimNot) << "CanBeNull only applies to reference types"; 1886 return true; 1887 } 1888 1889 virtual bool CanDoImplicitNullCheckOn(HInstruction* obj ATTRIBUTE_UNUSED) const { 1890 return false; 1891 } 1892 1893 virtual bool IsActualObject() const { 1894 return GetType() == Primitive::kPrimNot; 1895 } 1896 1897 void SetReferenceTypeInfo(ReferenceTypeInfo rti); 1898 1899 ReferenceTypeInfo GetReferenceTypeInfo() const { 1900 DCHECK_EQ(GetType(), Primitive::kPrimNot); 1901 return reference_type_info_; 1902 } 1903 1904 void AddUseAt(HInstruction* user, size_t index) { 1905 DCHECK(user != nullptr); 1906 HUseListNode<HInstruction*>* use = 1907 uses_.AddUse(user, index, GetBlock()->GetGraph()->GetArena()); 1908 user->SetRawInputRecordAt(index, HUserRecord<HInstruction*>(user->InputRecordAt(index), use)); 1909 } 1910 1911 void AddEnvUseAt(HEnvironment* user, size_t index) { 1912 DCHECK(user != nullptr); 1913 HUseListNode<HEnvironment*>* env_use = 1914 env_uses_.AddUse(user, index, GetBlock()->GetGraph()->GetArena()); 1915 user->RecordEnvUse(env_use); 1916 } 1917 1918 void RemoveAsUserOfInput(size_t input) { 1919 HUserRecord<HInstruction*> input_use = InputRecordAt(input); 1920 input_use.GetInstruction()->uses_.Remove(input_use.GetUseNode()); 1921 } 1922 1923 const HUseList<HInstruction*>& GetUses() const { return uses_; } 1924 const HUseList<HEnvironment*>& GetEnvUses() const { return env_uses_; } 1925 1926 bool HasUses() const { return !uses_.IsEmpty() || !env_uses_.IsEmpty(); } 1927 bool HasEnvironmentUses() const { return !env_uses_.IsEmpty(); } 1928 bool HasNonEnvironmentUses() const { return !uses_.IsEmpty(); } 1929 bool HasOnlyOneNonEnvironmentUse() const { 1930 return !HasEnvironmentUses() && GetUses().HasOnlyOneUse(); 1931 } 1932 1933 // Does this instruction strictly dominate `other_instruction`? 1934 // Returns false if this instruction and `other_instruction` are the same. 1935 // Aborts if this instruction and `other_instruction` are both phis. 1936 bool StrictlyDominates(HInstruction* other_instruction) const; 1937 1938 int GetId() const { return id_; } 1939 void SetId(int id) { id_ = id; } 1940 1941 int GetSsaIndex() const { return ssa_index_; } 1942 void SetSsaIndex(int ssa_index) { ssa_index_ = ssa_index; } 1943 bool HasSsaIndex() const { return ssa_index_ != -1; } 1944 1945 bool HasEnvironment() const { return environment_ != nullptr; } 1946 HEnvironment* GetEnvironment() const { return environment_; } 1947 // Set the `environment_` field. Raw because this method does not 1948 // update the uses lists. 1949 void SetRawEnvironment(HEnvironment* environment) { 1950 DCHECK(environment_ == nullptr); 1951 DCHECK_EQ(environment->GetHolder(), this); 1952 environment_ = environment; 1953 } 1954 1955 // Set the environment of this instruction, copying it from `environment`. While 1956 // copying, the uses lists are being updated. 1957 void CopyEnvironmentFrom(HEnvironment* environment) { 1958 DCHECK(environment_ == nullptr); 1959 ArenaAllocator* allocator = GetBlock()->GetGraph()->GetArena(); 1960 environment_ = new (allocator) HEnvironment(allocator, *environment, this); 1961 environment_->CopyFrom(environment); 1962 if (environment->GetParent() != nullptr) { 1963 environment_->SetAndCopyParentChain(allocator, environment->GetParent()); 1964 } 1965 } 1966 1967 void CopyEnvironmentFromWithLoopPhiAdjustment(HEnvironment* environment, 1968 HBasicBlock* block) { 1969 DCHECK(environment_ == nullptr); 1970 ArenaAllocator* allocator = GetBlock()->GetGraph()->GetArena(); 1971 environment_ = new (allocator) HEnvironment(allocator, *environment, this); 1972 environment_->CopyFromWithLoopPhiAdjustment(environment, block); 1973 if (environment->GetParent() != nullptr) { 1974 environment_->SetAndCopyParentChain(allocator, environment->GetParent()); 1975 } 1976 } 1977 1978 // Returns the number of entries in the environment. Typically, that is the 1979 // number of dex registers in a method. It could be more in case of inlining. 1980 size_t EnvironmentSize() const; 1981 1982 LocationSummary* GetLocations() const { return locations_; } 1983 void SetLocations(LocationSummary* locations) { locations_ = locations; } 1984 1985 void ReplaceWith(HInstruction* instruction); 1986 void ReplaceInput(HInstruction* replacement, size_t index); 1987 1988 // This is almost the same as doing `ReplaceWith()`. But in this helper, the 1989 // uses of this instruction by `other` are *not* updated. 1990 void ReplaceWithExceptInReplacementAtIndex(HInstruction* other, size_t use_index) { 1991 ReplaceWith(other); 1992 other->ReplaceInput(this, use_index); 1993 } 1994 1995 // Move `this` instruction before `cursor`. 1996 void MoveBefore(HInstruction* cursor); 1997 1998 // Move `this` before its first user and out of any loops. If there is no 1999 // out-of-loop user that dominates all other users, move the instruction 2000 // to the end of the out-of-loop common dominator of the user's blocks. 2001 // 2002 // This can be used only on non-throwing instructions with no side effects that 2003 // have at least one use but no environment uses. 2004 void MoveBeforeFirstUserAndOutOfLoops(); 2005 2006#define INSTRUCTION_TYPE_CHECK(type, super) \ 2007 bool Is##type() const; \ 2008 const H##type* As##type() const; \ 2009 H##type* As##type(); 2010 2011 FOR_EACH_CONCRETE_INSTRUCTION(INSTRUCTION_TYPE_CHECK) 2012#undef INSTRUCTION_TYPE_CHECK 2013 2014#define INSTRUCTION_TYPE_CHECK(type, super) \ 2015 bool Is##type() const { return (As##type() != nullptr); } \ 2016 virtual const H##type* As##type() const { return nullptr; } \ 2017 virtual H##type* As##type() { return nullptr; } 2018 FOR_EACH_ABSTRACT_INSTRUCTION(INSTRUCTION_TYPE_CHECK) 2019#undef INSTRUCTION_TYPE_CHECK 2020 2021 // Returns whether the instruction can be moved within the graph. 2022 virtual bool CanBeMoved() const { return false; } 2023 2024 // Returns whether the two instructions are of the same kind. 2025 virtual bool InstructionTypeEquals(HInstruction* other ATTRIBUTE_UNUSED) const { 2026 return false; 2027 } 2028 2029 // Returns whether any data encoded in the two instructions is equal. 2030 // This method does not look at the inputs. Both instructions must be 2031 // of the same type, otherwise the method has undefined behavior. 2032 virtual bool InstructionDataEquals(HInstruction* other ATTRIBUTE_UNUSED) const { 2033 return false; 2034 } 2035 2036 // Returns whether two instructions are equal, that is: 2037 // 1) They have the same type and contain the same data (InstructionDataEquals). 2038 // 2) Their inputs are identical. 2039 bool Equals(HInstruction* other) const; 2040 2041 // TODO: Remove this indirection when the [[pure]] attribute proposal (n3744) 2042 // is adopted and implemented by our C++ compiler(s). Fow now, we need to hide 2043 // the virtual function because the __attribute__((__pure__)) doesn't really 2044 // apply the strong requirement for virtual functions, preventing optimizations. 2045 InstructionKind GetKind() const PURE; 2046 virtual InstructionKind GetKindInternal() const = 0; 2047 2048 virtual size_t ComputeHashCode() const { 2049 size_t result = GetKind(); 2050 for (size_t i = 0, e = InputCount(); i < e; ++i) { 2051 result = (result * 31) + InputAt(i)->GetId(); 2052 } 2053 return result; 2054 } 2055 2056 SideEffects GetSideEffects() const { return side_effects_; } 2057 void AddSideEffects(SideEffects other) { side_effects_.Add(other); } 2058 2059 size_t GetLifetimePosition() const { return lifetime_position_; } 2060 void SetLifetimePosition(size_t position) { lifetime_position_ = position; } 2061 LiveInterval* GetLiveInterval() const { return live_interval_; } 2062 void SetLiveInterval(LiveInterval* interval) { live_interval_ = interval; } 2063 bool HasLiveInterval() const { return live_interval_ != nullptr; } 2064 2065 bool IsSuspendCheckEntry() const { return IsSuspendCheck() && GetBlock()->IsEntryBlock(); } 2066 2067 // Returns whether the code generation of the instruction will require to have access 2068 // to the current method. Such instructions are: 2069 // (1): Instructions that require an environment, as calling the runtime requires 2070 // to walk the stack and have the current method stored at a specific stack address. 2071 // (2): Object literals like classes and strings, that are loaded from the dex cache 2072 // fields of the current method. 2073 bool NeedsCurrentMethod() const { 2074 return NeedsEnvironment() || IsLoadClass() || IsLoadString(); 2075 } 2076 2077 // Returns whether the code generation of the instruction will require to have access 2078 // to the dex cache of the current method's declaring class via the current method. 2079 virtual bool NeedsDexCacheOfDeclaringClass() const { return false; } 2080 2081 // Does this instruction have any use in an environment before 2082 // control flow hits 'other'? 2083 bool HasAnyEnvironmentUseBefore(HInstruction* other); 2084 2085 // Remove all references to environment uses of this instruction. 2086 // The caller must ensure that this is safe to do. 2087 void RemoveEnvironmentUsers(); 2088 2089 bool IsEmittedAtUseSite() const { return emitted_at_use_site_; } 2090 void MarkEmittedAtUseSite() { emitted_at_use_site_ = true; } 2091 2092 protected: 2093 virtual const HUserRecord<HInstruction*> InputRecordAt(size_t i) const = 0; 2094 virtual void SetRawInputRecordAt(size_t index, const HUserRecord<HInstruction*>& input) = 0; 2095 void SetSideEffects(SideEffects other) { side_effects_ = other; } 2096 2097 private: 2098 void RemoveEnvironmentUser(HUseListNode<HEnvironment*>* use_node) { env_uses_.Remove(use_node); } 2099 2100 HInstruction* previous_; 2101 HInstruction* next_; 2102 HBasicBlock* block_; 2103 const uint32_t dex_pc_; 2104 2105 // An instruction gets an id when it is added to the graph. 2106 // It reflects creation order. A negative id means the instruction 2107 // has not been added to the graph. 2108 int id_; 2109 2110 // When doing liveness analysis, instructions that have uses get an SSA index. 2111 int ssa_index_; 2112 2113 // If set, the machine code for this instruction is assumed to be generated by 2114 // its users. Used by liveness analysis to compute use positions accordingly. 2115 bool emitted_at_use_site_; 2116 2117 // List of instructions that have this instruction as input. 2118 HUseList<HInstruction*> uses_; 2119 2120 // List of environments that contain this instruction. 2121 HUseList<HEnvironment*> env_uses_; 2122 2123 // The environment associated with this instruction. Not null if the instruction 2124 // might jump out of the method. 2125 HEnvironment* environment_; 2126 2127 // Set by the code generator. 2128 LocationSummary* locations_; 2129 2130 // Set by the liveness analysis. 2131 LiveInterval* live_interval_; 2132 2133 // Set by the liveness analysis, this is the position in a linear 2134 // order of blocks where this instruction's live interval start. 2135 size_t lifetime_position_; 2136 2137 SideEffects side_effects_; 2138 2139 // TODO: for primitive types this should be marked as invalid. 2140 ReferenceTypeInfo reference_type_info_; 2141 2142 friend class GraphChecker; 2143 friend class HBasicBlock; 2144 friend class HEnvironment; 2145 friend class HGraph; 2146 friend class HInstructionList; 2147 2148 DISALLOW_COPY_AND_ASSIGN(HInstruction); 2149}; 2150std::ostream& operator<<(std::ostream& os, const HInstruction::InstructionKind& rhs); 2151 2152class HInputIterator : public ValueObject { 2153 public: 2154 explicit HInputIterator(HInstruction* instruction) : instruction_(instruction), index_(0) {} 2155 2156 bool Done() const { return index_ == instruction_->InputCount(); } 2157 HInstruction* Current() const { return instruction_->InputAt(index_); } 2158 void Advance() { index_++; } 2159 2160 private: 2161 HInstruction* instruction_; 2162 size_t index_; 2163 2164 DISALLOW_COPY_AND_ASSIGN(HInputIterator); 2165}; 2166 2167class HInstructionIterator : public ValueObject { 2168 public: 2169 explicit HInstructionIterator(const HInstructionList& instructions) 2170 : instruction_(instructions.first_instruction_) { 2171 next_ = Done() ? nullptr : instruction_->GetNext(); 2172 } 2173 2174 bool Done() const { return instruction_ == nullptr; } 2175 HInstruction* Current() const { return instruction_; } 2176 void Advance() { 2177 instruction_ = next_; 2178 next_ = Done() ? nullptr : instruction_->GetNext(); 2179 } 2180 2181 private: 2182 HInstruction* instruction_; 2183 HInstruction* next_; 2184 2185 DISALLOW_COPY_AND_ASSIGN(HInstructionIterator); 2186}; 2187 2188class HBackwardInstructionIterator : public ValueObject { 2189 public: 2190 explicit HBackwardInstructionIterator(const HInstructionList& instructions) 2191 : instruction_(instructions.last_instruction_) { 2192 next_ = Done() ? nullptr : instruction_->GetPrevious(); 2193 } 2194 2195 bool Done() const { return instruction_ == nullptr; } 2196 HInstruction* Current() const { return instruction_; } 2197 void Advance() { 2198 instruction_ = next_; 2199 next_ = Done() ? nullptr : instruction_->GetPrevious(); 2200 } 2201 2202 private: 2203 HInstruction* instruction_; 2204 HInstruction* next_; 2205 2206 DISALLOW_COPY_AND_ASSIGN(HBackwardInstructionIterator); 2207}; 2208 2209template<size_t N> 2210class HTemplateInstruction: public HInstruction { 2211 public: 2212 HTemplateInstruction<N>(SideEffects side_effects, uint32_t dex_pc) 2213 : HInstruction(side_effects, dex_pc), inputs_() {} 2214 virtual ~HTemplateInstruction() {} 2215 2216 size_t InputCount() const OVERRIDE { return N; } 2217 2218 protected: 2219 const HUserRecord<HInstruction*> InputRecordAt(size_t i) const OVERRIDE { 2220 DCHECK_LT(i, N); 2221 return inputs_[i]; 2222 } 2223 2224 void SetRawInputRecordAt(size_t i, const HUserRecord<HInstruction*>& input) OVERRIDE { 2225 DCHECK_LT(i, N); 2226 inputs_[i] = input; 2227 } 2228 2229 private: 2230 std::array<HUserRecord<HInstruction*>, N> inputs_; 2231 2232 friend class SsaBuilder; 2233}; 2234 2235// HTemplateInstruction specialization for N=0. 2236template<> 2237class HTemplateInstruction<0>: public HInstruction { 2238 public: 2239 explicit HTemplateInstruction<0>(SideEffects side_effects, uint32_t dex_pc) 2240 : HInstruction(side_effects, dex_pc) {} 2241 2242 virtual ~HTemplateInstruction() {} 2243 2244 size_t InputCount() const OVERRIDE { return 0; } 2245 2246 protected: 2247 const HUserRecord<HInstruction*> InputRecordAt(size_t i ATTRIBUTE_UNUSED) const OVERRIDE { 2248 LOG(FATAL) << "Unreachable"; 2249 UNREACHABLE(); 2250 } 2251 2252 void SetRawInputRecordAt(size_t i ATTRIBUTE_UNUSED, 2253 const HUserRecord<HInstruction*>& input ATTRIBUTE_UNUSED) OVERRIDE { 2254 LOG(FATAL) << "Unreachable"; 2255 UNREACHABLE(); 2256 } 2257 2258 private: 2259 friend class SsaBuilder; 2260}; 2261 2262template<intptr_t N> 2263class HExpression : public HTemplateInstruction<N> { 2264 public: 2265 HExpression<N>(Primitive::Type type, SideEffects side_effects, uint32_t dex_pc) 2266 : HTemplateInstruction<N>(side_effects, dex_pc), type_(type) {} 2267 virtual ~HExpression() {} 2268 2269 Primitive::Type GetType() const OVERRIDE { return type_; } 2270 2271 protected: 2272 Primitive::Type type_; 2273}; 2274 2275// Represents dex's RETURN_VOID opcode. A HReturnVoid is a control flow 2276// instruction that branches to the exit block. 2277class HReturnVoid : public HTemplateInstruction<0> { 2278 public: 2279 explicit HReturnVoid(uint32_t dex_pc = kNoDexPc) 2280 : HTemplateInstruction(SideEffects::None(), dex_pc) {} 2281 2282 bool IsControlFlow() const OVERRIDE { return true; } 2283 2284 DECLARE_INSTRUCTION(ReturnVoid); 2285 2286 private: 2287 DISALLOW_COPY_AND_ASSIGN(HReturnVoid); 2288}; 2289 2290// Represents dex's RETURN opcodes. A HReturn is a control flow 2291// instruction that branches to the exit block. 2292class HReturn : public HTemplateInstruction<1> { 2293 public: 2294 explicit HReturn(HInstruction* value, uint32_t dex_pc = kNoDexPc) 2295 : HTemplateInstruction(SideEffects::None(), dex_pc) { 2296 SetRawInputAt(0, value); 2297 } 2298 2299 bool IsControlFlow() const OVERRIDE { return true; } 2300 2301 DECLARE_INSTRUCTION(Return); 2302 2303 private: 2304 DISALLOW_COPY_AND_ASSIGN(HReturn); 2305}; 2306 2307// The exit instruction is the only instruction of the exit block. 2308// Instructions aborting the method (HThrow and HReturn) must branch to the 2309// exit block. 2310class HExit : public HTemplateInstruction<0> { 2311 public: 2312 explicit HExit(uint32_t dex_pc = kNoDexPc) : HTemplateInstruction(SideEffects::None(), dex_pc) {} 2313 2314 bool IsControlFlow() const OVERRIDE { return true; } 2315 2316 DECLARE_INSTRUCTION(Exit); 2317 2318 private: 2319 DISALLOW_COPY_AND_ASSIGN(HExit); 2320}; 2321 2322// Jumps from one block to another. 2323class HGoto : public HTemplateInstruction<0> { 2324 public: 2325 explicit HGoto(uint32_t dex_pc = kNoDexPc) : HTemplateInstruction(SideEffects::None(), dex_pc) {} 2326 2327 bool IsControlFlow() const OVERRIDE { return true; } 2328 2329 HBasicBlock* GetSuccessor() const { 2330 return GetBlock()->GetSingleSuccessor(); 2331 } 2332 2333 DECLARE_INSTRUCTION(Goto); 2334 2335 private: 2336 DISALLOW_COPY_AND_ASSIGN(HGoto); 2337}; 2338 2339class HConstant : public HExpression<0> { 2340 public: 2341 explicit HConstant(Primitive::Type type, uint32_t dex_pc = kNoDexPc) 2342 : HExpression(type, SideEffects::None(), dex_pc) {} 2343 2344 bool CanBeMoved() const OVERRIDE { return true; } 2345 2346 virtual bool IsMinusOne() const { return false; } 2347 virtual bool IsZero() const { return false; } 2348 virtual bool IsOne() const { return false; } 2349 2350 virtual uint64_t GetValueAsUint64() const = 0; 2351 2352 DECLARE_ABSTRACT_INSTRUCTION(Constant); 2353 2354 private: 2355 DISALLOW_COPY_AND_ASSIGN(HConstant); 2356}; 2357 2358class HNullConstant : public HConstant { 2359 public: 2360 bool InstructionDataEquals(HInstruction* other ATTRIBUTE_UNUSED) const OVERRIDE { 2361 return true; 2362 } 2363 2364 uint64_t GetValueAsUint64() const OVERRIDE { return 0; } 2365 2366 size_t ComputeHashCode() const OVERRIDE { return 0; } 2367 2368 DECLARE_INSTRUCTION(NullConstant); 2369 2370 private: 2371 explicit HNullConstant(uint32_t dex_pc = kNoDexPc) : HConstant(Primitive::kPrimNot, dex_pc) {} 2372 2373 friend class HGraph; 2374 DISALLOW_COPY_AND_ASSIGN(HNullConstant); 2375}; 2376 2377// Constants of the type int. Those can be from Dex instructions, or 2378// synthesized (for example with the if-eqz instruction). 2379class HIntConstant : public HConstant { 2380 public: 2381 int32_t GetValue() const { return value_; } 2382 2383 uint64_t GetValueAsUint64() const OVERRIDE { 2384 return static_cast<uint64_t>(static_cast<uint32_t>(value_)); 2385 } 2386 2387 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 2388 DCHECK(other->IsIntConstant()); 2389 return other->AsIntConstant()->value_ == value_; 2390 } 2391 2392 size_t ComputeHashCode() const OVERRIDE { return GetValue(); } 2393 2394 bool IsMinusOne() const OVERRIDE { return GetValue() == -1; } 2395 bool IsZero() const OVERRIDE { return GetValue() == 0; } 2396 bool IsOne() const OVERRIDE { return GetValue() == 1; } 2397 2398 DECLARE_INSTRUCTION(IntConstant); 2399 2400 private: 2401 explicit HIntConstant(int32_t value, uint32_t dex_pc = kNoDexPc) 2402 : HConstant(Primitive::kPrimInt, dex_pc), value_(value) {} 2403 explicit HIntConstant(bool value, uint32_t dex_pc = kNoDexPc) 2404 : HConstant(Primitive::kPrimInt, dex_pc), value_(value ? 1 : 0) {} 2405 2406 const int32_t value_; 2407 2408 friend class HGraph; 2409 ART_FRIEND_TEST(GraphTest, InsertInstructionBefore); 2410 ART_FRIEND_TYPED_TEST(ParallelMoveTest, ConstantLast); 2411 DISALLOW_COPY_AND_ASSIGN(HIntConstant); 2412}; 2413 2414class HLongConstant : public HConstant { 2415 public: 2416 int64_t GetValue() const { return value_; } 2417 2418 uint64_t GetValueAsUint64() const OVERRIDE { return value_; } 2419 2420 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 2421 DCHECK(other->IsLongConstant()); 2422 return other->AsLongConstant()->value_ == value_; 2423 } 2424 2425 size_t ComputeHashCode() const OVERRIDE { return static_cast<size_t>(GetValue()); } 2426 2427 bool IsMinusOne() const OVERRIDE { return GetValue() == -1; } 2428 bool IsZero() const OVERRIDE { return GetValue() == 0; } 2429 bool IsOne() const OVERRIDE { return GetValue() == 1; } 2430 2431 DECLARE_INSTRUCTION(LongConstant); 2432 2433 private: 2434 explicit HLongConstant(int64_t value, uint32_t dex_pc = kNoDexPc) 2435 : HConstant(Primitive::kPrimLong, dex_pc), value_(value) {} 2436 2437 const int64_t value_; 2438 2439 friend class HGraph; 2440 DISALLOW_COPY_AND_ASSIGN(HLongConstant); 2441}; 2442 2443// Conditional branch. A block ending with an HIf instruction must have 2444// two successors. 2445class HIf : public HTemplateInstruction<1> { 2446 public: 2447 explicit HIf(HInstruction* input, uint32_t dex_pc = kNoDexPc) 2448 : HTemplateInstruction(SideEffects::None(), dex_pc) { 2449 SetRawInputAt(0, input); 2450 } 2451 2452 bool IsControlFlow() const OVERRIDE { return true; } 2453 2454 HBasicBlock* IfTrueSuccessor() const { 2455 return GetBlock()->GetSuccessors()[0]; 2456 } 2457 2458 HBasicBlock* IfFalseSuccessor() const { 2459 return GetBlock()->GetSuccessors()[1]; 2460 } 2461 2462 DECLARE_INSTRUCTION(If); 2463 2464 private: 2465 DISALLOW_COPY_AND_ASSIGN(HIf); 2466}; 2467 2468 2469// Abstract instruction which marks the beginning and/or end of a try block and 2470// links it to the respective exception handlers. Behaves the same as a Goto in 2471// non-exceptional control flow. 2472// Normal-flow successor is stored at index zero, exception handlers under 2473// higher indices in no particular order. 2474class HTryBoundary : public HTemplateInstruction<0> { 2475 public: 2476 enum BoundaryKind { 2477 kEntry, 2478 kExit, 2479 }; 2480 2481 explicit HTryBoundary(BoundaryKind kind, uint32_t dex_pc = kNoDexPc) 2482 : HTemplateInstruction(SideEffects::None(), dex_pc), kind_(kind) {} 2483 2484 bool IsControlFlow() const OVERRIDE { return true; } 2485 2486 // Returns the block's non-exceptional successor (index zero). 2487 HBasicBlock* GetNormalFlowSuccessor() const { return GetBlock()->GetSuccessors()[0]; } 2488 2489 ArrayRef<HBasicBlock* const> GetExceptionHandlers() const { 2490 return ArrayRef<HBasicBlock* const>(GetBlock()->GetSuccessors()).SubArray(1u); 2491 } 2492 2493 // Returns whether `handler` is among its exception handlers (non-zero index 2494 // successors). 2495 bool HasExceptionHandler(const HBasicBlock& handler) const { 2496 DCHECK(handler.IsCatchBlock()); 2497 return GetBlock()->HasSuccessor(&handler, 1u /* Skip first successor. */); 2498 } 2499 2500 // If not present already, adds `handler` to its block's list of exception 2501 // handlers. 2502 void AddExceptionHandler(HBasicBlock* handler) { 2503 if (!HasExceptionHandler(*handler)) { 2504 GetBlock()->AddSuccessor(handler); 2505 } 2506 } 2507 2508 bool IsEntry() const { return kind_ == BoundaryKind::kEntry; } 2509 2510 bool HasSameExceptionHandlersAs(const HTryBoundary& other) const; 2511 2512 DECLARE_INSTRUCTION(TryBoundary); 2513 2514 private: 2515 const BoundaryKind kind_; 2516 2517 DISALLOW_COPY_AND_ASSIGN(HTryBoundary); 2518}; 2519 2520// Deoptimize to interpreter, upon checking a condition. 2521class HDeoptimize : public HTemplateInstruction<1> { 2522 public: 2523 // We set CanTriggerGC to prevent any intermediate address to be live 2524 // at the point of the `HDeoptimize`. 2525 HDeoptimize(HInstruction* cond, uint32_t dex_pc) 2526 : HTemplateInstruction(SideEffects::CanTriggerGC(), dex_pc) { 2527 SetRawInputAt(0, cond); 2528 } 2529 2530 bool CanBeMoved() const OVERRIDE { return true; } 2531 bool InstructionDataEquals(HInstruction* other ATTRIBUTE_UNUSED) const OVERRIDE { 2532 return true; 2533 } 2534 bool NeedsEnvironment() const OVERRIDE { return true; } 2535 bool CanThrow() const OVERRIDE { return true; } 2536 2537 DECLARE_INSTRUCTION(Deoptimize); 2538 2539 private: 2540 DISALLOW_COPY_AND_ASSIGN(HDeoptimize); 2541}; 2542 2543// Represents the ArtMethod that was passed as a first argument to 2544// the method. It is used by instructions that depend on it, like 2545// instructions that work with the dex cache. 2546class HCurrentMethod : public HExpression<0> { 2547 public: 2548 explicit HCurrentMethod(Primitive::Type type, uint32_t dex_pc = kNoDexPc) 2549 : HExpression(type, SideEffects::None(), dex_pc) {} 2550 2551 DECLARE_INSTRUCTION(CurrentMethod); 2552 2553 private: 2554 DISALLOW_COPY_AND_ASSIGN(HCurrentMethod); 2555}; 2556 2557// Fetches an ArtMethod from the virtual table or the interface method table 2558// of a class. 2559class HClassTableGet : public HExpression<1> { 2560 public: 2561 enum TableKind { 2562 kVTable, 2563 kIMTable, 2564 }; 2565 HClassTableGet(HInstruction* cls, 2566 Primitive::Type type, 2567 TableKind kind, 2568 size_t index, 2569 uint32_t dex_pc) 2570 : HExpression(type, SideEffects::None(), dex_pc), 2571 index_(index), 2572 table_kind_(kind) { 2573 SetRawInputAt(0, cls); 2574 } 2575 2576 bool CanBeMoved() const OVERRIDE { return true; } 2577 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 2578 return other->AsClassTableGet()->GetIndex() == index_ && 2579 other->AsClassTableGet()->GetTableKind() == table_kind_; 2580 } 2581 2582 TableKind GetTableKind() const { return table_kind_; } 2583 size_t GetIndex() const { return index_; } 2584 2585 DECLARE_INSTRUCTION(ClassTableGet); 2586 2587 private: 2588 // The index of the ArtMethod in the table. 2589 const size_t index_; 2590 const TableKind table_kind_; 2591 2592 DISALLOW_COPY_AND_ASSIGN(HClassTableGet); 2593}; 2594 2595// PackedSwitch (jump table). A block ending with a PackedSwitch instruction will 2596// have one successor for each entry in the switch table, and the final successor 2597// will be the block containing the next Dex opcode. 2598class HPackedSwitch : public HTemplateInstruction<1> { 2599 public: 2600 HPackedSwitch(int32_t start_value, 2601 uint32_t num_entries, 2602 HInstruction* input, 2603 uint32_t dex_pc = kNoDexPc) 2604 : HTemplateInstruction(SideEffects::None(), dex_pc), 2605 start_value_(start_value), 2606 num_entries_(num_entries) { 2607 SetRawInputAt(0, input); 2608 } 2609 2610 bool IsControlFlow() const OVERRIDE { return true; } 2611 2612 int32_t GetStartValue() const { return start_value_; } 2613 2614 uint32_t GetNumEntries() const { return num_entries_; } 2615 2616 HBasicBlock* GetDefaultBlock() const { 2617 // Last entry is the default block. 2618 return GetBlock()->GetSuccessors()[num_entries_]; 2619 } 2620 DECLARE_INSTRUCTION(PackedSwitch); 2621 2622 private: 2623 const int32_t start_value_; 2624 const uint32_t num_entries_; 2625 2626 DISALLOW_COPY_AND_ASSIGN(HPackedSwitch); 2627}; 2628 2629class HUnaryOperation : public HExpression<1> { 2630 public: 2631 HUnaryOperation(Primitive::Type result_type, HInstruction* input, uint32_t dex_pc = kNoDexPc) 2632 : HExpression(result_type, SideEffects::None(), dex_pc) { 2633 SetRawInputAt(0, input); 2634 } 2635 2636 HInstruction* GetInput() const { return InputAt(0); } 2637 Primitive::Type GetResultType() const { return GetType(); } 2638 2639 bool CanBeMoved() const OVERRIDE { return true; } 2640 bool InstructionDataEquals(HInstruction* other ATTRIBUTE_UNUSED) const OVERRIDE { 2641 return true; 2642 } 2643 2644 // Try to statically evaluate `operation` and return a HConstant 2645 // containing the result of this evaluation. If `operation` cannot 2646 // be evaluated as a constant, return null. 2647 HConstant* TryStaticEvaluation() const; 2648 2649 // Apply this operation to `x`. 2650 virtual HConstant* Evaluate(HIntConstant* x) const = 0; 2651 virtual HConstant* Evaluate(HLongConstant* x) const = 0; 2652 2653 DECLARE_ABSTRACT_INSTRUCTION(UnaryOperation); 2654 2655 private: 2656 DISALLOW_COPY_AND_ASSIGN(HUnaryOperation); 2657}; 2658 2659class HBinaryOperation : public HExpression<2> { 2660 public: 2661 HBinaryOperation(Primitive::Type result_type, 2662 HInstruction* left, 2663 HInstruction* right, 2664 SideEffects side_effects = SideEffects::None(), 2665 uint32_t dex_pc = kNoDexPc) 2666 : HExpression(result_type, side_effects, dex_pc) { 2667 SetRawInputAt(0, left); 2668 SetRawInputAt(1, right); 2669 } 2670 2671 HInstruction* GetLeft() const { return InputAt(0); } 2672 HInstruction* GetRight() const { return InputAt(1); } 2673 Primitive::Type GetResultType() const { return GetType(); } 2674 2675 virtual bool IsCommutative() const { return false; } 2676 2677 // Put constant on the right. 2678 // Returns whether order is changed. 2679 bool OrderInputsWithConstantOnTheRight() { 2680 HInstruction* left = InputAt(0); 2681 HInstruction* right = InputAt(1); 2682 if (left->IsConstant() && !right->IsConstant()) { 2683 ReplaceInput(right, 0); 2684 ReplaceInput(left, 1); 2685 return true; 2686 } 2687 return false; 2688 } 2689 2690 // Order inputs by instruction id, but favor constant on the right side. 2691 // This helps GVN for commutative ops. 2692 void OrderInputs() { 2693 DCHECK(IsCommutative()); 2694 HInstruction* left = InputAt(0); 2695 HInstruction* right = InputAt(1); 2696 if (left == right || (!left->IsConstant() && right->IsConstant())) { 2697 return; 2698 } 2699 if (OrderInputsWithConstantOnTheRight()) { 2700 return; 2701 } 2702 // Order according to instruction id. 2703 if (left->GetId() > right->GetId()) { 2704 ReplaceInput(right, 0); 2705 ReplaceInput(left, 1); 2706 } 2707 } 2708 2709 bool CanBeMoved() const OVERRIDE { return true; } 2710 bool InstructionDataEquals(HInstruction* other ATTRIBUTE_UNUSED) const OVERRIDE { 2711 return true; 2712 } 2713 2714 // Try to statically evaluate `operation` and return a HConstant 2715 // containing the result of this evaluation. If `operation` cannot 2716 // be evaluated as a constant, return null. 2717 HConstant* TryStaticEvaluation() const; 2718 2719 // Apply this operation to `x` and `y`. 2720 virtual HConstant* Evaluate(HIntConstant* x, HIntConstant* y) const = 0; 2721 virtual HConstant* Evaluate(HLongConstant* x, HLongConstant* y) const = 0; 2722 virtual HConstant* Evaluate(HIntConstant* x ATTRIBUTE_UNUSED, 2723 HLongConstant* y ATTRIBUTE_UNUSED) const { 2724 VLOG(compiler) << DebugName() << " is not defined for the (int, long) case."; 2725 return nullptr; 2726 } 2727 virtual HConstant* Evaluate(HLongConstant* x ATTRIBUTE_UNUSED, 2728 HIntConstant* y ATTRIBUTE_UNUSED) const { 2729 VLOG(compiler) << DebugName() << " is not defined for the (long, int) case."; 2730 return nullptr; 2731 } 2732 virtual HConstant* Evaluate(HNullConstant* x ATTRIBUTE_UNUSED, 2733 HNullConstant* y ATTRIBUTE_UNUSED) const { 2734 VLOG(compiler) << DebugName() << " is not defined for the (null, null) case."; 2735 return nullptr; 2736 } 2737 2738 // Returns an input that can legally be used as the right input and is 2739 // constant, or null. 2740 HConstant* GetConstantRight() const; 2741 2742 // If `GetConstantRight()` returns one of the input, this returns the other 2743 // one. Otherwise it returns null. 2744 HInstruction* GetLeastConstantLeft() const; 2745 2746 DECLARE_ABSTRACT_INSTRUCTION(BinaryOperation); 2747 2748 private: 2749 DISALLOW_COPY_AND_ASSIGN(HBinaryOperation); 2750}; 2751 2752// The comparison bias applies for floating point operations and indicates how NaN 2753// comparisons are treated: 2754enum class ComparisonBias { 2755 kNoBias, // bias is not applicable (i.e. for long operation) 2756 kGtBias, // return 1 for NaN comparisons 2757 kLtBias, // return -1 for NaN comparisons 2758}; 2759 2760class HCondition : public HBinaryOperation { 2761 public: 2762 HCondition(HInstruction* first, HInstruction* second, uint32_t dex_pc = kNoDexPc) 2763 : HBinaryOperation(Primitive::kPrimBoolean, first, second, SideEffects::None(), dex_pc), 2764 bias_(ComparisonBias::kNoBias) {} 2765 2766 // For code generation purposes, returns whether this instruction is just before 2767 // `instruction`, and disregard moves in between. 2768 bool IsBeforeWhenDisregardMoves(HInstruction* instruction) const; 2769 2770 DECLARE_ABSTRACT_INSTRUCTION(Condition); 2771 2772 virtual IfCondition GetCondition() const = 0; 2773 2774 virtual IfCondition GetOppositeCondition() const = 0; 2775 2776 bool IsGtBias() const { return bias_ == ComparisonBias::kGtBias; } 2777 2778 void SetBias(ComparisonBias bias) { bias_ = bias; } 2779 2780 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 2781 return bias_ == other->AsCondition()->bias_; 2782 } 2783 2784 bool IsFPConditionTrueIfNaN() const { 2785 DCHECK(Primitive::IsFloatingPointType(InputAt(0)->GetType())); 2786 IfCondition if_cond = GetCondition(); 2787 return IsGtBias() ? ((if_cond == kCondGT) || (if_cond == kCondGE)) : (if_cond == kCondNE); 2788 } 2789 2790 bool IsFPConditionFalseIfNaN() const { 2791 DCHECK(Primitive::IsFloatingPointType(InputAt(0)->GetType())); 2792 IfCondition if_cond = GetCondition(); 2793 return IsGtBias() ? ((if_cond == kCondLT) || (if_cond == kCondLE)) : (if_cond == kCondEQ); 2794 } 2795 2796 private: 2797 // Needed if we merge a HCompare into a HCondition. 2798 ComparisonBias bias_; 2799 2800 DISALLOW_COPY_AND_ASSIGN(HCondition); 2801}; 2802 2803// Instruction to check if two inputs are equal to each other. 2804class HEqual : public HCondition { 2805 public: 2806 HEqual(HInstruction* first, HInstruction* second, uint32_t dex_pc = kNoDexPc) 2807 : HCondition(first, second, dex_pc) {} 2808 2809 bool IsCommutative() const OVERRIDE { return true; } 2810 2811 HConstant* Evaluate(HIntConstant* x, HIntConstant* y) const OVERRIDE { 2812 return GetBlock()->GetGraph()->GetIntConstant( 2813 Compute(x->GetValue(), y->GetValue()), GetDexPc()); 2814 } 2815 HConstant* Evaluate(HLongConstant* x, HLongConstant* y) const OVERRIDE { 2816 return GetBlock()->GetGraph()->GetIntConstant( 2817 Compute(x->GetValue(), y->GetValue()), GetDexPc()); 2818 } 2819 HConstant* Evaluate(HNullConstant* x ATTRIBUTE_UNUSED, 2820 HNullConstant* y ATTRIBUTE_UNUSED) const OVERRIDE { 2821 return GetBlock()->GetGraph()->GetIntConstant(1); 2822 } 2823 2824 DECLARE_INSTRUCTION(Equal); 2825 2826 IfCondition GetCondition() const OVERRIDE { 2827 return kCondEQ; 2828 } 2829 2830 IfCondition GetOppositeCondition() const OVERRIDE { 2831 return kCondNE; 2832 } 2833 2834 private: 2835 template <typename T> bool Compute(T x, T y) const { return x == y; } 2836 2837 DISALLOW_COPY_AND_ASSIGN(HEqual); 2838}; 2839 2840class HNotEqual : public HCondition { 2841 public: 2842 HNotEqual(HInstruction* first, HInstruction* second, uint32_t dex_pc = kNoDexPc) 2843 : HCondition(first, second, dex_pc) {} 2844 2845 bool IsCommutative() const OVERRIDE { return true; } 2846 2847 HConstant* Evaluate(HIntConstant* x, HIntConstant* y) const OVERRIDE { 2848 return GetBlock()->GetGraph()->GetIntConstant( 2849 Compute(x->GetValue(), y->GetValue()), GetDexPc()); 2850 } 2851 HConstant* Evaluate(HLongConstant* x, HLongConstant* y) const OVERRIDE { 2852 return GetBlock()->GetGraph()->GetIntConstant( 2853 Compute(x->GetValue(), y->GetValue()), GetDexPc()); 2854 } 2855 HConstant* Evaluate(HNullConstant* x ATTRIBUTE_UNUSED, 2856 HNullConstant* y ATTRIBUTE_UNUSED) const OVERRIDE { 2857 return GetBlock()->GetGraph()->GetIntConstant(0); 2858 } 2859 2860 DECLARE_INSTRUCTION(NotEqual); 2861 2862 IfCondition GetCondition() const OVERRIDE { 2863 return kCondNE; 2864 } 2865 2866 IfCondition GetOppositeCondition() const OVERRIDE { 2867 return kCondEQ; 2868 } 2869 2870 private: 2871 template <typename T> bool Compute(T x, T y) const { return x != y; } 2872 2873 DISALLOW_COPY_AND_ASSIGN(HNotEqual); 2874}; 2875 2876class HLessThan : public HCondition { 2877 public: 2878 HLessThan(HInstruction* first, HInstruction* second, uint32_t dex_pc = kNoDexPc) 2879 : HCondition(first, second, dex_pc) {} 2880 2881 HConstant* Evaluate(HIntConstant* x, HIntConstant* y) const OVERRIDE { 2882 return GetBlock()->GetGraph()->GetIntConstant( 2883 Compute(x->GetValue(), y->GetValue()), GetDexPc()); 2884 } 2885 HConstant* Evaluate(HLongConstant* x, HLongConstant* y) const OVERRIDE { 2886 return GetBlock()->GetGraph()->GetIntConstant( 2887 Compute(x->GetValue(), y->GetValue()), GetDexPc()); 2888 } 2889 2890 DECLARE_INSTRUCTION(LessThan); 2891 2892 IfCondition GetCondition() const OVERRIDE { 2893 return kCondLT; 2894 } 2895 2896 IfCondition GetOppositeCondition() const OVERRIDE { 2897 return kCondGE; 2898 } 2899 2900 private: 2901 template <typename T> bool Compute(T x, T y) const { return x < y; } 2902 2903 DISALLOW_COPY_AND_ASSIGN(HLessThan); 2904}; 2905 2906class HLessThanOrEqual : public HCondition { 2907 public: 2908 HLessThanOrEqual(HInstruction* first, HInstruction* second, uint32_t dex_pc = kNoDexPc) 2909 : HCondition(first, second, dex_pc) {} 2910 2911 HConstant* Evaluate(HIntConstant* x, HIntConstant* y) const OVERRIDE { 2912 return GetBlock()->GetGraph()->GetIntConstant( 2913 Compute(x->GetValue(), y->GetValue()), GetDexPc()); 2914 } 2915 HConstant* Evaluate(HLongConstant* x, HLongConstant* y) const OVERRIDE { 2916 return GetBlock()->GetGraph()->GetIntConstant( 2917 Compute(x->GetValue(), y->GetValue()), GetDexPc()); 2918 } 2919 2920 DECLARE_INSTRUCTION(LessThanOrEqual); 2921 2922 IfCondition GetCondition() const OVERRIDE { 2923 return kCondLE; 2924 } 2925 2926 IfCondition GetOppositeCondition() const OVERRIDE { 2927 return kCondGT; 2928 } 2929 2930 private: 2931 template <typename T> bool Compute(T x, T y) const { return x <= y; } 2932 2933 DISALLOW_COPY_AND_ASSIGN(HLessThanOrEqual); 2934}; 2935 2936class HGreaterThan : public HCondition { 2937 public: 2938 HGreaterThan(HInstruction* first, HInstruction* second, uint32_t dex_pc = kNoDexPc) 2939 : HCondition(first, second, dex_pc) {} 2940 2941 HConstant* Evaluate(HIntConstant* x, HIntConstant* y) const OVERRIDE { 2942 return GetBlock()->GetGraph()->GetIntConstant( 2943 Compute(x->GetValue(), y->GetValue()), GetDexPc()); 2944 } 2945 HConstant* Evaluate(HLongConstant* x, HLongConstant* y) const OVERRIDE { 2946 return GetBlock()->GetGraph()->GetIntConstant( 2947 Compute(x->GetValue(), y->GetValue()), GetDexPc()); 2948 } 2949 2950 DECLARE_INSTRUCTION(GreaterThan); 2951 2952 IfCondition GetCondition() const OVERRIDE { 2953 return kCondGT; 2954 } 2955 2956 IfCondition GetOppositeCondition() const OVERRIDE { 2957 return kCondLE; 2958 } 2959 2960 private: 2961 template <typename T> bool Compute(T x, T y) const { return x > y; } 2962 2963 DISALLOW_COPY_AND_ASSIGN(HGreaterThan); 2964}; 2965 2966class HGreaterThanOrEqual : public HCondition { 2967 public: 2968 HGreaterThanOrEqual(HInstruction* first, HInstruction* second, uint32_t dex_pc = kNoDexPc) 2969 : HCondition(first, second, dex_pc) {} 2970 2971 HConstant* Evaluate(HIntConstant* x, HIntConstant* y) const OVERRIDE { 2972 return GetBlock()->GetGraph()->GetIntConstant( 2973 Compute(x->GetValue(), y->GetValue()), GetDexPc()); 2974 } 2975 HConstant* Evaluate(HLongConstant* x, HLongConstant* y) const OVERRIDE { 2976 return GetBlock()->GetGraph()->GetIntConstant( 2977 Compute(x->GetValue(), y->GetValue()), GetDexPc()); 2978 } 2979 2980 DECLARE_INSTRUCTION(GreaterThanOrEqual); 2981 2982 IfCondition GetCondition() const OVERRIDE { 2983 return kCondGE; 2984 } 2985 2986 IfCondition GetOppositeCondition() const OVERRIDE { 2987 return kCondLT; 2988 } 2989 2990 private: 2991 template <typename T> bool Compute(T x, T y) const { return x >= y; } 2992 2993 DISALLOW_COPY_AND_ASSIGN(HGreaterThanOrEqual); 2994}; 2995 2996class HBelow : public HCondition { 2997 public: 2998 HBelow(HInstruction* first, HInstruction* second, uint32_t dex_pc = kNoDexPc) 2999 : HCondition(first, second, dex_pc) {} 3000 3001 HConstant* Evaluate(HIntConstant* x, HIntConstant* y) const OVERRIDE { 3002 return GetBlock()->GetGraph()->GetIntConstant( 3003 Compute(static_cast<uint32_t>(x->GetValue()), 3004 static_cast<uint32_t>(y->GetValue())), GetDexPc()); 3005 } 3006 HConstant* Evaluate(HLongConstant* x, HLongConstant* y) const OVERRIDE { 3007 return GetBlock()->GetGraph()->GetIntConstant( 3008 Compute(static_cast<uint64_t>(x->GetValue()), 3009 static_cast<uint64_t>(y->GetValue())), GetDexPc()); 3010 } 3011 3012 DECLARE_INSTRUCTION(Below); 3013 3014 IfCondition GetCondition() const OVERRIDE { 3015 return kCondB; 3016 } 3017 3018 IfCondition GetOppositeCondition() const OVERRIDE { 3019 return kCondAE; 3020 } 3021 3022 private: 3023 template <typename T> bool Compute(T x, T y) const { return x < y; } 3024 3025 DISALLOW_COPY_AND_ASSIGN(HBelow); 3026}; 3027 3028class HBelowOrEqual : public HCondition { 3029 public: 3030 HBelowOrEqual(HInstruction* first, HInstruction* second, uint32_t dex_pc = kNoDexPc) 3031 : HCondition(first, second, dex_pc) {} 3032 3033 HConstant* Evaluate(HIntConstant* x, HIntConstant* y) const OVERRIDE { 3034 return GetBlock()->GetGraph()->GetIntConstant( 3035 Compute(static_cast<uint32_t>(x->GetValue()), 3036 static_cast<uint32_t>(y->GetValue())), GetDexPc()); 3037 } 3038 HConstant* Evaluate(HLongConstant* x, HLongConstant* y) const OVERRIDE { 3039 return GetBlock()->GetGraph()->GetIntConstant( 3040 Compute(static_cast<uint64_t>(x->GetValue()), 3041 static_cast<uint64_t>(y->GetValue())), GetDexPc()); 3042 } 3043 3044 DECLARE_INSTRUCTION(BelowOrEqual); 3045 3046 IfCondition GetCondition() const OVERRIDE { 3047 return kCondBE; 3048 } 3049 3050 IfCondition GetOppositeCondition() const OVERRIDE { 3051 return kCondA; 3052 } 3053 3054 private: 3055 template <typename T> bool Compute(T x, T y) const { return x <= y; } 3056 3057 DISALLOW_COPY_AND_ASSIGN(HBelowOrEqual); 3058}; 3059 3060class HAbove : public HCondition { 3061 public: 3062 HAbove(HInstruction* first, HInstruction* second, uint32_t dex_pc = kNoDexPc) 3063 : HCondition(first, second, dex_pc) {} 3064 3065 HConstant* Evaluate(HIntConstant* x, HIntConstant* y) const OVERRIDE { 3066 return GetBlock()->GetGraph()->GetIntConstant( 3067 Compute(static_cast<uint32_t>(x->GetValue()), 3068 static_cast<uint32_t>(y->GetValue())), GetDexPc()); 3069 } 3070 HConstant* Evaluate(HLongConstant* x, HLongConstant* y) const OVERRIDE { 3071 return GetBlock()->GetGraph()->GetIntConstant( 3072 Compute(static_cast<uint64_t>(x->GetValue()), 3073 static_cast<uint64_t>(y->GetValue())), GetDexPc()); 3074 } 3075 3076 DECLARE_INSTRUCTION(Above); 3077 3078 IfCondition GetCondition() const OVERRIDE { 3079 return kCondA; 3080 } 3081 3082 IfCondition GetOppositeCondition() const OVERRIDE { 3083 return kCondBE; 3084 } 3085 3086 private: 3087 template <typename T> bool Compute(T x, T y) const { return x > y; } 3088 3089 DISALLOW_COPY_AND_ASSIGN(HAbove); 3090}; 3091 3092class HAboveOrEqual : public HCondition { 3093 public: 3094 HAboveOrEqual(HInstruction* first, HInstruction* second, uint32_t dex_pc = kNoDexPc) 3095 : HCondition(first, second, dex_pc) {} 3096 3097 HConstant* Evaluate(HIntConstant* x, HIntConstant* y) const OVERRIDE { 3098 return GetBlock()->GetGraph()->GetIntConstant( 3099 Compute(static_cast<uint32_t>(x->GetValue()), 3100 static_cast<uint32_t>(y->GetValue())), GetDexPc()); 3101 } 3102 HConstant* Evaluate(HLongConstant* x, HLongConstant* y) const OVERRIDE { 3103 return GetBlock()->GetGraph()->GetIntConstant( 3104 Compute(static_cast<uint64_t>(x->GetValue()), 3105 static_cast<uint64_t>(y->GetValue())), GetDexPc()); 3106 } 3107 3108 DECLARE_INSTRUCTION(AboveOrEqual); 3109 3110 IfCondition GetCondition() const OVERRIDE { 3111 return kCondAE; 3112 } 3113 3114 IfCondition GetOppositeCondition() const OVERRIDE { 3115 return kCondB; 3116 } 3117 3118 private: 3119 template <typename T> bool Compute(T x, T y) const { return x >= y; } 3120 3121 DISALLOW_COPY_AND_ASSIGN(HAboveOrEqual); 3122}; 3123 3124// Instruction to check how two inputs compare to each other. 3125// Result is 0 if input0 == input1, 1 if input0 > input1, or -1 if input0 < input1. 3126class HCompare : public HBinaryOperation { 3127 public: 3128 HCompare(Primitive::Type type, 3129 HInstruction* first, 3130 HInstruction* second, 3131 ComparisonBias bias, 3132 uint32_t dex_pc) 3133 : HBinaryOperation(Primitive::kPrimInt, 3134 first, 3135 second, 3136 SideEffectsForArchRuntimeCalls(type), 3137 dex_pc), 3138 bias_(bias) { 3139 DCHECK_EQ(type, first->GetType()); 3140 DCHECK_EQ(type, second->GetType()); 3141 } 3142 3143 template <typename T> 3144 int32_t Compute(T x, T y) const { return x == y ? 0 : x > y ? 1 : -1; } 3145 3146 HConstant* Evaluate(HIntConstant* x, HIntConstant* y) const OVERRIDE { 3147 return GetBlock()->GetGraph()->GetIntConstant( 3148 Compute(x->GetValue(), y->GetValue()), GetDexPc()); 3149 } 3150 HConstant* Evaluate(HLongConstant* x, HLongConstant* y) const OVERRIDE { 3151 return GetBlock()->GetGraph()->GetIntConstant( 3152 Compute(x->GetValue(), y->GetValue()), GetDexPc()); 3153 } 3154 3155 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 3156 return bias_ == other->AsCompare()->bias_; 3157 } 3158 3159 ComparisonBias GetBias() const { return bias_; } 3160 3161 bool IsGtBias() { return bias_ == ComparisonBias::kGtBias; } 3162 3163 3164 static SideEffects SideEffectsForArchRuntimeCalls(Primitive::Type type) { 3165 // MIPS64 uses a runtime call for FP comparisons. 3166 return Primitive::IsFloatingPointType(type) ? SideEffects::CanTriggerGC() : SideEffects::None(); 3167 } 3168 3169 DECLARE_INSTRUCTION(Compare); 3170 3171 private: 3172 const ComparisonBias bias_; 3173 3174 DISALLOW_COPY_AND_ASSIGN(HCompare); 3175}; 3176 3177// A local in the graph. Corresponds to a Dex register. 3178class HLocal : public HTemplateInstruction<0> { 3179 public: 3180 explicit HLocal(uint16_t reg_number) 3181 : HTemplateInstruction(SideEffects::None(), kNoDexPc), reg_number_(reg_number) {} 3182 3183 DECLARE_INSTRUCTION(Local); 3184 3185 uint16_t GetRegNumber() const { return reg_number_; } 3186 3187 private: 3188 // The Dex register number. 3189 const uint16_t reg_number_; 3190 3191 DISALLOW_COPY_AND_ASSIGN(HLocal); 3192}; 3193 3194// Load a given local. The local is an input of this instruction. 3195class HLoadLocal : public HExpression<1> { 3196 public: 3197 HLoadLocal(HLocal* local, Primitive::Type type, uint32_t dex_pc = kNoDexPc) 3198 : HExpression(type, SideEffects::None(), dex_pc) { 3199 SetRawInputAt(0, local); 3200 } 3201 3202 HLocal* GetLocal() const { return reinterpret_cast<HLocal*>(InputAt(0)); } 3203 3204 DECLARE_INSTRUCTION(LoadLocal); 3205 3206 private: 3207 DISALLOW_COPY_AND_ASSIGN(HLoadLocal); 3208}; 3209 3210// Store a value in a given local. This instruction has two inputs: the value 3211// and the local. 3212class HStoreLocal : public HTemplateInstruction<2> { 3213 public: 3214 HStoreLocal(HLocal* local, HInstruction* value, uint32_t dex_pc = kNoDexPc) 3215 : HTemplateInstruction(SideEffects::None(), dex_pc) { 3216 SetRawInputAt(0, local); 3217 SetRawInputAt(1, value); 3218 } 3219 3220 HLocal* GetLocal() const { return reinterpret_cast<HLocal*>(InputAt(0)); } 3221 3222 DECLARE_INSTRUCTION(StoreLocal); 3223 3224 private: 3225 DISALLOW_COPY_AND_ASSIGN(HStoreLocal); 3226}; 3227 3228class HFloatConstant : public HConstant { 3229 public: 3230 float GetValue() const { return value_; } 3231 3232 uint64_t GetValueAsUint64() const OVERRIDE { 3233 return static_cast<uint64_t>(bit_cast<uint32_t, float>(value_)); 3234 } 3235 3236 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 3237 DCHECK(other->IsFloatConstant()); 3238 return other->AsFloatConstant()->GetValueAsUint64() == GetValueAsUint64(); 3239 } 3240 3241 size_t ComputeHashCode() const OVERRIDE { return static_cast<size_t>(GetValue()); } 3242 3243 bool IsMinusOne() const OVERRIDE { 3244 return bit_cast<uint32_t, float>(value_) == bit_cast<uint32_t, float>((-1.0f)); 3245 } 3246 bool IsZero() const OVERRIDE { 3247 return value_ == 0.0f; 3248 } 3249 bool IsOne() const OVERRIDE { 3250 return bit_cast<uint32_t, float>(value_) == bit_cast<uint32_t, float>(1.0f); 3251 } 3252 bool IsNaN() const { 3253 return std::isnan(value_); 3254 } 3255 3256 DECLARE_INSTRUCTION(FloatConstant); 3257 3258 private: 3259 explicit HFloatConstant(float value, uint32_t dex_pc = kNoDexPc) 3260 : HConstant(Primitive::kPrimFloat, dex_pc), value_(value) {} 3261 explicit HFloatConstant(int32_t value, uint32_t dex_pc = kNoDexPc) 3262 : HConstant(Primitive::kPrimFloat, dex_pc), value_(bit_cast<float, int32_t>(value)) {} 3263 3264 const float value_; 3265 3266 // Only the SsaBuilder and HGraph can create floating-point constants. 3267 friend class SsaBuilder; 3268 friend class HGraph; 3269 DISALLOW_COPY_AND_ASSIGN(HFloatConstant); 3270}; 3271 3272class HDoubleConstant : public HConstant { 3273 public: 3274 double GetValue() const { return value_; } 3275 3276 uint64_t GetValueAsUint64() const OVERRIDE { return bit_cast<uint64_t, double>(value_); } 3277 3278 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 3279 DCHECK(other->IsDoubleConstant()); 3280 return other->AsDoubleConstant()->GetValueAsUint64() == GetValueAsUint64(); 3281 } 3282 3283 size_t ComputeHashCode() const OVERRIDE { return static_cast<size_t>(GetValue()); } 3284 3285 bool IsMinusOne() const OVERRIDE { 3286 return bit_cast<uint64_t, double>(value_) == bit_cast<uint64_t, double>((-1.0)); 3287 } 3288 bool IsZero() const OVERRIDE { 3289 return value_ == 0.0; 3290 } 3291 bool IsOne() const OVERRIDE { 3292 return bit_cast<uint64_t, double>(value_) == bit_cast<uint64_t, double>(1.0); 3293 } 3294 bool IsNaN() const { 3295 return std::isnan(value_); 3296 } 3297 3298 DECLARE_INSTRUCTION(DoubleConstant); 3299 3300 private: 3301 explicit HDoubleConstant(double value, uint32_t dex_pc = kNoDexPc) 3302 : HConstant(Primitive::kPrimDouble, dex_pc), value_(value) {} 3303 explicit HDoubleConstant(int64_t value, uint32_t dex_pc = kNoDexPc) 3304 : HConstant(Primitive::kPrimDouble, dex_pc), value_(bit_cast<double, int64_t>(value)) {} 3305 3306 const double value_; 3307 3308 // Only the SsaBuilder and HGraph can create floating-point constants. 3309 friend class SsaBuilder; 3310 friend class HGraph; 3311 DISALLOW_COPY_AND_ASSIGN(HDoubleConstant); 3312}; 3313 3314class HNewInstance : public HExpression<2> { 3315 public: 3316 HNewInstance(HInstruction* cls, 3317 HCurrentMethod* current_method, 3318 uint32_t dex_pc, 3319 uint16_t type_index, 3320 const DexFile& dex_file, 3321 bool can_throw, 3322 bool finalizable, 3323 QuickEntrypointEnum entrypoint) 3324 : HExpression(Primitive::kPrimNot, SideEffects::CanTriggerGC(), dex_pc), 3325 type_index_(type_index), 3326 dex_file_(dex_file), 3327 can_throw_(can_throw), 3328 finalizable_(finalizable), 3329 entrypoint_(entrypoint) { 3330 SetRawInputAt(0, cls); 3331 SetRawInputAt(1, current_method); 3332 } 3333 3334 uint16_t GetTypeIndex() const { return type_index_; } 3335 const DexFile& GetDexFile() const { return dex_file_; } 3336 3337 // Calls runtime so needs an environment. 3338 bool NeedsEnvironment() const OVERRIDE { return true; } 3339 3340 // It may throw when called on type that's not instantiable/accessible. 3341 // It can throw OOME. 3342 // TODO: distinguish between the two cases so we can for example allow allocation elimination. 3343 bool CanThrow() const OVERRIDE { return can_throw_ || true; } 3344 3345 bool IsFinalizable() const { return finalizable_; } 3346 3347 bool CanBeNull() const OVERRIDE { return false; } 3348 3349 QuickEntrypointEnum GetEntrypoint() const { return entrypoint_; } 3350 3351 void SetEntrypoint(QuickEntrypointEnum entrypoint) { 3352 entrypoint_ = entrypoint; 3353 } 3354 3355 bool IsStringAlloc() const; 3356 3357 DECLARE_INSTRUCTION(NewInstance); 3358 3359 private: 3360 const uint16_t type_index_; 3361 const DexFile& dex_file_; 3362 const bool can_throw_; 3363 const bool finalizable_; 3364 QuickEntrypointEnum entrypoint_; 3365 3366 DISALLOW_COPY_AND_ASSIGN(HNewInstance); 3367}; 3368 3369enum class Intrinsics { 3370#define OPTIMIZING_INTRINSICS(Name, IsStatic, NeedsEnvironmentOrCache, SideEffects, Exceptions) \ 3371 k ## Name, 3372#include "intrinsics_list.h" 3373 kNone, 3374 INTRINSICS_LIST(OPTIMIZING_INTRINSICS) 3375#undef INTRINSICS_LIST 3376#undef OPTIMIZING_INTRINSICS 3377}; 3378std::ostream& operator<<(std::ostream& os, const Intrinsics& intrinsic); 3379 3380enum IntrinsicNeedsEnvironmentOrCache { 3381 kNoEnvironmentOrCache, // Intrinsic does not require an environment or dex cache. 3382 kNeedsEnvironmentOrCache // Intrinsic requires an environment or requires a dex cache. 3383}; 3384 3385enum IntrinsicSideEffects { 3386 kNoSideEffects, // Intrinsic does not have any heap memory side effects. 3387 kReadSideEffects, // Intrinsic may read heap memory. 3388 kWriteSideEffects, // Intrinsic may write heap memory. 3389 kAllSideEffects // Intrinsic may read or write heap memory, or trigger GC. 3390}; 3391 3392enum IntrinsicExceptions { 3393 kNoThrow, // Intrinsic does not throw any exceptions. 3394 kCanThrow // Intrinsic may throw exceptions. 3395}; 3396 3397class HInvoke : public HInstruction { 3398 public: 3399 size_t InputCount() const OVERRIDE { return inputs_.size(); } 3400 3401 bool NeedsEnvironment() const OVERRIDE; 3402 3403 void SetArgumentAt(size_t index, HInstruction* argument) { 3404 SetRawInputAt(index, argument); 3405 } 3406 3407 // Return the number of arguments. This number can be lower than 3408 // the number of inputs returned by InputCount(), as some invoke 3409 // instructions (e.g. HInvokeStaticOrDirect) can have non-argument 3410 // inputs at the end of their list of inputs. 3411 uint32_t GetNumberOfArguments() const { return number_of_arguments_; } 3412 3413 Primitive::Type GetType() const OVERRIDE { return return_type_; } 3414 3415 uint32_t GetDexMethodIndex() const { return dex_method_index_; } 3416 const DexFile& GetDexFile() const { return GetEnvironment()->GetDexFile(); } 3417 3418 InvokeType GetOriginalInvokeType() const { return original_invoke_type_; } 3419 3420 Intrinsics GetIntrinsic() const { 3421 return intrinsic_; 3422 } 3423 3424 void SetIntrinsic(Intrinsics intrinsic, 3425 IntrinsicNeedsEnvironmentOrCache needs_env_or_cache, 3426 IntrinsicSideEffects side_effects, 3427 IntrinsicExceptions exceptions); 3428 3429 bool IsFromInlinedInvoke() const { 3430 return GetEnvironment()->IsFromInlinedInvoke(); 3431 } 3432 3433 bool CanThrow() const OVERRIDE { return can_throw_; } 3434 3435 bool CanBeMoved() const OVERRIDE { return IsIntrinsic(); } 3436 3437 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 3438 return intrinsic_ != Intrinsics::kNone && intrinsic_ == other->AsInvoke()->intrinsic_; 3439 } 3440 3441 uint32_t* GetIntrinsicOptimizations() { 3442 return &intrinsic_optimizations_; 3443 } 3444 3445 const uint32_t* GetIntrinsicOptimizations() const { 3446 return &intrinsic_optimizations_; 3447 } 3448 3449 bool IsIntrinsic() const { return intrinsic_ != Intrinsics::kNone; } 3450 3451 DECLARE_ABSTRACT_INSTRUCTION(Invoke); 3452 3453 protected: 3454 HInvoke(ArenaAllocator* arena, 3455 uint32_t number_of_arguments, 3456 uint32_t number_of_other_inputs, 3457 Primitive::Type return_type, 3458 uint32_t dex_pc, 3459 uint32_t dex_method_index, 3460 InvokeType original_invoke_type) 3461 : HInstruction( 3462 SideEffects::AllExceptGCDependency(), dex_pc), // Assume write/read on all fields/arrays. 3463 number_of_arguments_(number_of_arguments), 3464 inputs_(number_of_arguments + number_of_other_inputs, 3465 arena->Adapter(kArenaAllocInvokeInputs)), 3466 return_type_(return_type), 3467 dex_method_index_(dex_method_index), 3468 original_invoke_type_(original_invoke_type), 3469 can_throw_(true), 3470 intrinsic_(Intrinsics::kNone), 3471 intrinsic_optimizations_(0) { 3472 } 3473 3474 const HUserRecord<HInstruction*> InputRecordAt(size_t index) const OVERRIDE { 3475 return inputs_[index]; 3476 } 3477 3478 void SetRawInputRecordAt(size_t index, const HUserRecord<HInstruction*>& input) OVERRIDE { 3479 inputs_[index] = input; 3480 } 3481 3482 void SetCanThrow(bool can_throw) { can_throw_ = can_throw; } 3483 3484 uint32_t number_of_arguments_; 3485 ArenaVector<HUserRecord<HInstruction*>> inputs_; 3486 const Primitive::Type return_type_; 3487 const uint32_t dex_method_index_; 3488 const InvokeType original_invoke_type_; 3489 bool can_throw_; 3490 Intrinsics intrinsic_; 3491 3492 // A magic word holding optimizations for intrinsics. See intrinsics.h. 3493 uint32_t intrinsic_optimizations_; 3494 3495 private: 3496 DISALLOW_COPY_AND_ASSIGN(HInvoke); 3497}; 3498 3499class HInvokeUnresolved : public HInvoke { 3500 public: 3501 HInvokeUnresolved(ArenaAllocator* arena, 3502 uint32_t number_of_arguments, 3503 Primitive::Type return_type, 3504 uint32_t dex_pc, 3505 uint32_t dex_method_index, 3506 InvokeType invoke_type) 3507 : HInvoke(arena, 3508 number_of_arguments, 3509 0u /* number_of_other_inputs */, 3510 return_type, 3511 dex_pc, 3512 dex_method_index, 3513 invoke_type) { 3514 } 3515 3516 DECLARE_INSTRUCTION(InvokeUnresolved); 3517 3518 private: 3519 DISALLOW_COPY_AND_ASSIGN(HInvokeUnresolved); 3520}; 3521 3522class HInvokeStaticOrDirect : public HInvoke { 3523 public: 3524 // Requirements of this method call regarding the class 3525 // initialization (clinit) check of its declaring class. 3526 enum class ClinitCheckRequirement { 3527 kNone, // Class already initialized. 3528 kExplicit, // Static call having explicit clinit check as last input. 3529 kImplicit, // Static call implicitly requiring a clinit check. 3530 }; 3531 3532 // Determines how to load the target ArtMethod*. 3533 enum class MethodLoadKind { 3534 // Use a String init ArtMethod* loaded from Thread entrypoints. 3535 kStringInit, 3536 3537 // Use the method's own ArtMethod* loaded by the register allocator. 3538 kRecursive, 3539 3540 // Use ArtMethod* at a known address, embed the direct address in the code. 3541 // Used for app->boot calls with non-relocatable image and for JIT-compiled calls. 3542 kDirectAddress, 3543 3544 // Use ArtMethod* at an address that will be known at link time, embed the direct 3545 // address in the code. If the image is relocatable, emit .patch_oat entry. 3546 // Used for app->boot calls with relocatable image and boot->boot calls, whether 3547 // the image relocatable or not. 3548 kDirectAddressWithFixup, 3549 3550 // Load from resoved methods array in the dex cache using a PC-relative load. 3551 // Used when we need to use the dex cache, for example for invoke-static that 3552 // may cause class initialization (the entry may point to a resolution method), 3553 // and we know that we can access the dex cache arrays using a PC-relative load. 3554 kDexCachePcRelative, 3555 3556 // Use ArtMethod* from the resolved methods of the compiled method's own ArtMethod*. 3557 // Used for JIT when we need to use the dex cache. This is also the last-resort-kind 3558 // used when other kinds are unavailable (say, dex cache arrays are not PC-relative) 3559 // or unimplemented or impractical (i.e. slow) on a particular architecture. 3560 kDexCacheViaMethod, 3561 }; 3562 3563 // Determines the location of the code pointer. 3564 enum class CodePtrLocation { 3565 // Recursive call, use local PC-relative call instruction. 3566 kCallSelf, 3567 3568 // Use PC-relative call instruction patched at link time. 3569 // Used for calls within an oat file, boot->boot or app->app. 3570 kCallPCRelative, 3571 3572 // Call to a known target address, embed the direct address in code. 3573 // Used for app->boot call with non-relocatable image and for JIT-compiled calls. 3574 kCallDirect, 3575 3576 // Call to a target address that will be known at link time, embed the direct 3577 // address in code. If the image is relocatable, emit .patch_oat entry. 3578 // Used for app->boot calls with relocatable image and boot->boot calls, whether 3579 // the image relocatable or not. 3580 kCallDirectWithFixup, 3581 3582 // Use code pointer from the ArtMethod*. 3583 // Used when we don't know the target code. This is also the last-resort-kind used when 3584 // other kinds are unimplemented or impractical (i.e. slow) on a particular architecture. 3585 kCallArtMethod, 3586 }; 3587 3588 struct DispatchInfo { 3589 MethodLoadKind method_load_kind; 3590 CodePtrLocation code_ptr_location; 3591 // The method load data holds 3592 // - thread entrypoint offset for kStringInit method if this is a string init invoke. 3593 // Note that there are multiple string init methods, each having its own offset. 3594 // - the method address for kDirectAddress 3595 // - the dex cache arrays offset for kDexCachePcRel. 3596 uint64_t method_load_data; 3597 uint64_t direct_code_ptr; 3598 }; 3599 3600 HInvokeStaticOrDirect(ArenaAllocator* arena, 3601 uint32_t number_of_arguments, 3602 Primitive::Type return_type, 3603 uint32_t dex_pc, 3604 uint32_t method_index, 3605 MethodReference target_method, 3606 DispatchInfo dispatch_info, 3607 InvokeType original_invoke_type, 3608 InvokeType optimized_invoke_type, 3609 ClinitCheckRequirement clinit_check_requirement) 3610 : HInvoke(arena, 3611 number_of_arguments, 3612 // There is potentially one extra argument for the HCurrentMethod node, and 3613 // potentially one other if the clinit check is explicit, and potentially 3614 // one other if the method is a string factory. 3615 (NeedsCurrentMethodInput(dispatch_info.method_load_kind) ? 1u : 0u) + 3616 (clinit_check_requirement == ClinitCheckRequirement::kExplicit ? 1u : 0u) + 3617 (dispatch_info.method_load_kind == MethodLoadKind::kStringInit ? 1u : 0u), 3618 return_type, 3619 dex_pc, 3620 method_index, 3621 original_invoke_type), 3622 optimized_invoke_type_(optimized_invoke_type), 3623 clinit_check_requirement_(clinit_check_requirement), 3624 target_method_(target_method), 3625 dispatch_info_(dispatch_info) { } 3626 3627 void SetDispatchInfo(const DispatchInfo& dispatch_info) { 3628 bool had_current_method_input = HasCurrentMethodInput(); 3629 bool needs_current_method_input = NeedsCurrentMethodInput(dispatch_info.method_load_kind); 3630 3631 // Using the current method is the default and once we find a better 3632 // method load kind, we should not go back to using the current method. 3633 DCHECK(had_current_method_input || !needs_current_method_input); 3634 3635 if (had_current_method_input && !needs_current_method_input) { 3636 DCHECK_EQ(InputAt(GetSpecialInputIndex()), GetBlock()->GetGraph()->GetCurrentMethod()); 3637 RemoveInputAt(GetSpecialInputIndex()); 3638 } 3639 dispatch_info_ = dispatch_info; 3640 } 3641 3642 void AddSpecialInput(HInstruction* input) { 3643 // We allow only one special input. 3644 DCHECK(!IsStringInit() && !HasCurrentMethodInput()); 3645 DCHECK(InputCount() == GetSpecialInputIndex() || 3646 (InputCount() == GetSpecialInputIndex() + 1 && IsStaticWithExplicitClinitCheck())); 3647 InsertInputAt(GetSpecialInputIndex(), input); 3648 } 3649 3650 bool CanDoImplicitNullCheckOn(HInstruction* obj ATTRIBUTE_UNUSED) const OVERRIDE { 3651 // We access the method via the dex cache so we can't do an implicit null check. 3652 // TODO: for intrinsics we can generate implicit null checks. 3653 return false; 3654 } 3655 3656 bool CanBeNull() const OVERRIDE { 3657 return return_type_ == Primitive::kPrimNot && !IsStringInit(); 3658 } 3659 3660 // Get the index of the special input, if any. 3661 // 3662 // If the invoke HasCurrentMethodInput(), the "special input" is the current 3663 // method pointer; otherwise there may be one platform-specific special input, 3664 // such as PC-relative addressing base. 3665 uint32_t GetSpecialInputIndex() const { return GetNumberOfArguments(); } 3666 3667 InvokeType GetOptimizedInvokeType() const { return optimized_invoke_type_; } 3668 void SetOptimizedInvokeType(InvokeType invoke_type) { 3669 optimized_invoke_type_ = invoke_type; 3670 } 3671 3672 MethodLoadKind GetMethodLoadKind() const { return dispatch_info_.method_load_kind; } 3673 CodePtrLocation GetCodePtrLocation() const { return dispatch_info_.code_ptr_location; } 3674 bool IsRecursive() const { return GetMethodLoadKind() == MethodLoadKind::kRecursive; } 3675 bool NeedsDexCacheOfDeclaringClass() const OVERRIDE; 3676 bool IsStringInit() const { return GetMethodLoadKind() == MethodLoadKind::kStringInit; } 3677 bool HasMethodAddress() const { return GetMethodLoadKind() == MethodLoadKind::kDirectAddress; } 3678 bool HasPcRelativeDexCache() const { 3679 return GetMethodLoadKind() == MethodLoadKind::kDexCachePcRelative; 3680 } 3681 bool HasCurrentMethodInput() const { 3682 // This function can be called only after the invoke has been fully initialized by the builder. 3683 if (NeedsCurrentMethodInput(GetMethodLoadKind())) { 3684 DCHECK(InputAt(GetSpecialInputIndex())->IsCurrentMethod()); 3685 return true; 3686 } else { 3687 DCHECK(InputCount() == GetSpecialInputIndex() || 3688 !InputAt(GetSpecialInputIndex())->IsCurrentMethod()); 3689 return false; 3690 } 3691 } 3692 bool HasDirectCodePtr() const { return GetCodePtrLocation() == CodePtrLocation::kCallDirect; } 3693 MethodReference GetTargetMethod() const { return target_method_; } 3694 void SetTargetMethod(MethodReference method) { target_method_ = method; } 3695 3696 int32_t GetStringInitOffset() const { 3697 DCHECK(IsStringInit()); 3698 return dispatch_info_.method_load_data; 3699 } 3700 3701 uint64_t GetMethodAddress() const { 3702 DCHECK(HasMethodAddress()); 3703 return dispatch_info_.method_load_data; 3704 } 3705 3706 uint32_t GetDexCacheArrayOffset() const { 3707 DCHECK(HasPcRelativeDexCache()); 3708 return dispatch_info_.method_load_data; 3709 } 3710 3711 uint64_t GetDirectCodePtr() const { 3712 DCHECK(HasDirectCodePtr()); 3713 return dispatch_info_.direct_code_ptr; 3714 } 3715 3716 ClinitCheckRequirement GetClinitCheckRequirement() const { return clinit_check_requirement_; } 3717 3718 // Is this instruction a call to a static method? 3719 bool IsStatic() const { 3720 return GetOriginalInvokeType() == kStatic; 3721 } 3722 3723 // Remove the HClinitCheck or the replacement HLoadClass (set as last input by 3724 // PrepareForRegisterAllocation::VisitClinitCheck() in lieu of the initial HClinitCheck) 3725 // instruction; only relevant for static calls with explicit clinit check. 3726 void RemoveExplicitClinitCheck(ClinitCheckRequirement new_requirement) { 3727 DCHECK(IsStaticWithExplicitClinitCheck()); 3728 size_t last_input_index = InputCount() - 1; 3729 HInstruction* last_input = InputAt(last_input_index); 3730 DCHECK(last_input != nullptr); 3731 DCHECK(last_input->IsLoadClass() || last_input->IsClinitCheck()) << last_input->DebugName(); 3732 RemoveAsUserOfInput(last_input_index); 3733 inputs_.pop_back(); 3734 clinit_check_requirement_ = new_requirement; 3735 DCHECK(!IsStaticWithExplicitClinitCheck()); 3736 } 3737 3738 HInstruction* GetAndRemoveThisArgumentOfStringInit() { 3739 DCHECK(IsStringInit()); 3740 size_t index = InputCount() - 1; 3741 HInstruction* input = InputAt(index); 3742 RemoveAsUserOfInput(index); 3743 inputs_.pop_back(); 3744 return input; 3745 } 3746 3747 // Is this a call to a static method whose declaring class has an 3748 // explicit initialization check in the graph? 3749 bool IsStaticWithExplicitClinitCheck() const { 3750 return IsStatic() && (clinit_check_requirement_ == ClinitCheckRequirement::kExplicit); 3751 } 3752 3753 // Is this a call to a static method whose declaring class has an 3754 // implicit intialization check requirement? 3755 bool IsStaticWithImplicitClinitCheck() const { 3756 return IsStatic() && (clinit_check_requirement_ == ClinitCheckRequirement::kImplicit); 3757 } 3758 3759 // Does this method load kind need the current method as an input? 3760 static bool NeedsCurrentMethodInput(MethodLoadKind kind) { 3761 return kind == MethodLoadKind::kRecursive || kind == MethodLoadKind::kDexCacheViaMethod; 3762 } 3763 3764 DECLARE_INSTRUCTION(InvokeStaticOrDirect); 3765 3766 protected: 3767 const HUserRecord<HInstruction*> InputRecordAt(size_t i) const OVERRIDE { 3768 const HUserRecord<HInstruction*> input_record = HInvoke::InputRecordAt(i); 3769 if (kIsDebugBuild && IsStaticWithExplicitClinitCheck() && (i == InputCount() - 1)) { 3770 HInstruction* input = input_record.GetInstruction(); 3771 // `input` is the last input of a static invoke marked as having 3772 // an explicit clinit check. It must either be: 3773 // - an art::HClinitCheck instruction, set by art::HGraphBuilder; or 3774 // - an art::HLoadClass instruction, set by art::PrepareForRegisterAllocation. 3775 DCHECK(input != nullptr); 3776 DCHECK(input->IsClinitCheck() || input->IsLoadClass()) << input->DebugName(); 3777 } 3778 return input_record; 3779 } 3780 3781 void InsertInputAt(size_t index, HInstruction* input); 3782 void RemoveInputAt(size_t index); 3783 3784 private: 3785 InvokeType optimized_invoke_type_; 3786 ClinitCheckRequirement clinit_check_requirement_; 3787 // The target method may refer to different dex file or method index than the original 3788 // invoke. This happens for sharpened calls and for calls where a method was redeclared 3789 // in derived class to increase visibility. 3790 MethodReference target_method_; 3791 DispatchInfo dispatch_info_; 3792 3793 DISALLOW_COPY_AND_ASSIGN(HInvokeStaticOrDirect); 3794}; 3795std::ostream& operator<<(std::ostream& os, HInvokeStaticOrDirect::MethodLoadKind rhs); 3796std::ostream& operator<<(std::ostream& os, HInvokeStaticOrDirect::ClinitCheckRequirement rhs); 3797 3798class HInvokeVirtual : public HInvoke { 3799 public: 3800 HInvokeVirtual(ArenaAllocator* arena, 3801 uint32_t number_of_arguments, 3802 Primitive::Type return_type, 3803 uint32_t dex_pc, 3804 uint32_t dex_method_index, 3805 uint32_t vtable_index) 3806 : HInvoke(arena, number_of_arguments, 0u, return_type, dex_pc, dex_method_index, kVirtual), 3807 vtable_index_(vtable_index) {} 3808 3809 bool CanDoImplicitNullCheckOn(HInstruction* obj) const OVERRIDE { 3810 // TODO: Add implicit null checks in intrinsics. 3811 return (obj == InputAt(0)) && !GetLocations()->Intrinsified(); 3812 } 3813 3814 uint32_t GetVTableIndex() const { return vtable_index_; } 3815 3816 DECLARE_INSTRUCTION(InvokeVirtual); 3817 3818 private: 3819 const uint32_t vtable_index_; 3820 3821 DISALLOW_COPY_AND_ASSIGN(HInvokeVirtual); 3822}; 3823 3824class HInvokeInterface : public HInvoke { 3825 public: 3826 HInvokeInterface(ArenaAllocator* arena, 3827 uint32_t number_of_arguments, 3828 Primitive::Type return_type, 3829 uint32_t dex_pc, 3830 uint32_t dex_method_index, 3831 uint32_t imt_index) 3832 : HInvoke(arena, number_of_arguments, 0u, return_type, dex_pc, dex_method_index, kInterface), 3833 imt_index_(imt_index) {} 3834 3835 bool CanDoImplicitNullCheckOn(HInstruction* obj) const OVERRIDE { 3836 // TODO: Add implicit null checks in intrinsics. 3837 return (obj == InputAt(0)) && !GetLocations()->Intrinsified(); 3838 } 3839 3840 uint32_t GetImtIndex() const { return imt_index_; } 3841 uint32_t GetDexMethodIndex() const { return dex_method_index_; } 3842 3843 DECLARE_INSTRUCTION(InvokeInterface); 3844 3845 private: 3846 const uint32_t imt_index_; 3847 3848 DISALLOW_COPY_AND_ASSIGN(HInvokeInterface); 3849}; 3850 3851class HNeg : public HUnaryOperation { 3852 public: 3853 HNeg(Primitive::Type result_type, HInstruction* input, uint32_t dex_pc = kNoDexPc) 3854 : HUnaryOperation(result_type, input, dex_pc) {} 3855 3856 template <typename T> T Compute(T x) const { return -x; } 3857 3858 HConstant* Evaluate(HIntConstant* x) const OVERRIDE { 3859 return GetBlock()->GetGraph()->GetIntConstant(Compute(x->GetValue()), GetDexPc()); 3860 } 3861 HConstant* Evaluate(HLongConstant* x) const OVERRIDE { 3862 return GetBlock()->GetGraph()->GetLongConstant(Compute(x->GetValue()), GetDexPc()); 3863 } 3864 3865 DECLARE_INSTRUCTION(Neg); 3866 3867 private: 3868 DISALLOW_COPY_AND_ASSIGN(HNeg); 3869}; 3870 3871class HNewArray : public HExpression<2> { 3872 public: 3873 HNewArray(HInstruction* length, 3874 HCurrentMethod* current_method, 3875 uint32_t dex_pc, 3876 uint16_t type_index, 3877 const DexFile& dex_file, 3878 QuickEntrypointEnum entrypoint) 3879 : HExpression(Primitive::kPrimNot, SideEffects::CanTriggerGC(), dex_pc), 3880 type_index_(type_index), 3881 dex_file_(dex_file), 3882 entrypoint_(entrypoint) { 3883 SetRawInputAt(0, length); 3884 SetRawInputAt(1, current_method); 3885 } 3886 3887 uint16_t GetTypeIndex() const { return type_index_; } 3888 const DexFile& GetDexFile() const { return dex_file_; } 3889 3890 // Calls runtime so needs an environment. 3891 bool NeedsEnvironment() const OVERRIDE { return true; } 3892 3893 // May throw NegativeArraySizeException, OutOfMemoryError, etc. 3894 bool CanThrow() const OVERRIDE { return true; } 3895 3896 bool CanBeNull() const OVERRIDE { return false; } 3897 3898 QuickEntrypointEnum GetEntrypoint() const { return entrypoint_; } 3899 3900 DECLARE_INSTRUCTION(NewArray); 3901 3902 private: 3903 const uint16_t type_index_; 3904 const DexFile& dex_file_; 3905 const QuickEntrypointEnum entrypoint_; 3906 3907 DISALLOW_COPY_AND_ASSIGN(HNewArray); 3908}; 3909 3910class HAdd : public HBinaryOperation { 3911 public: 3912 HAdd(Primitive::Type result_type, 3913 HInstruction* left, 3914 HInstruction* right, 3915 uint32_t dex_pc = kNoDexPc) 3916 : HBinaryOperation(result_type, left, right, SideEffects::None(), dex_pc) {} 3917 3918 bool IsCommutative() const OVERRIDE { return true; } 3919 3920 template <typename T> T Compute(T x, T y) const { return x + y; } 3921 3922 HConstant* Evaluate(HIntConstant* x, HIntConstant* y) const OVERRIDE { 3923 return GetBlock()->GetGraph()->GetIntConstant( 3924 Compute(x->GetValue(), y->GetValue()), GetDexPc()); 3925 } 3926 HConstant* Evaluate(HLongConstant* x, HLongConstant* y) const OVERRIDE { 3927 return GetBlock()->GetGraph()->GetLongConstant( 3928 Compute(x->GetValue(), y->GetValue()), GetDexPc()); 3929 } 3930 3931 DECLARE_INSTRUCTION(Add); 3932 3933 private: 3934 DISALLOW_COPY_AND_ASSIGN(HAdd); 3935}; 3936 3937class HSub : public HBinaryOperation { 3938 public: 3939 HSub(Primitive::Type result_type, 3940 HInstruction* left, 3941 HInstruction* right, 3942 uint32_t dex_pc = kNoDexPc) 3943 : HBinaryOperation(result_type, left, right, SideEffects::None(), dex_pc) {} 3944 3945 template <typename T> T Compute(T x, T y) const { return x - y; } 3946 3947 HConstant* Evaluate(HIntConstant* x, HIntConstant* y) const OVERRIDE { 3948 return GetBlock()->GetGraph()->GetIntConstant( 3949 Compute(x->GetValue(), y->GetValue()), GetDexPc()); 3950 } 3951 HConstant* Evaluate(HLongConstant* x, HLongConstant* y) const OVERRIDE { 3952 return GetBlock()->GetGraph()->GetLongConstant( 3953 Compute(x->GetValue(), y->GetValue()), GetDexPc()); 3954 } 3955 3956 DECLARE_INSTRUCTION(Sub); 3957 3958 private: 3959 DISALLOW_COPY_AND_ASSIGN(HSub); 3960}; 3961 3962class HMul : public HBinaryOperation { 3963 public: 3964 HMul(Primitive::Type result_type, 3965 HInstruction* left, 3966 HInstruction* right, 3967 uint32_t dex_pc = kNoDexPc) 3968 : HBinaryOperation(result_type, left, right, SideEffects::None(), dex_pc) {} 3969 3970 bool IsCommutative() const OVERRIDE { return true; } 3971 3972 template <typename T> T Compute(T x, T y) const { return x * y; } 3973 3974 HConstant* Evaluate(HIntConstant* x, HIntConstant* y) const OVERRIDE { 3975 return GetBlock()->GetGraph()->GetIntConstant( 3976 Compute(x->GetValue(), y->GetValue()), GetDexPc()); 3977 } 3978 HConstant* Evaluate(HLongConstant* x, HLongConstant* y) const OVERRIDE { 3979 return GetBlock()->GetGraph()->GetLongConstant( 3980 Compute(x->GetValue(), y->GetValue()), GetDexPc()); 3981 } 3982 3983 DECLARE_INSTRUCTION(Mul); 3984 3985 private: 3986 DISALLOW_COPY_AND_ASSIGN(HMul); 3987}; 3988 3989class HDiv : public HBinaryOperation { 3990 public: 3991 HDiv(Primitive::Type result_type, 3992 HInstruction* left, 3993 HInstruction* right, 3994 uint32_t dex_pc) 3995 : HBinaryOperation(result_type, left, right, SideEffectsForArchRuntimeCalls(), dex_pc) {} 3996 3997 template <typename T> 3998 T Compute(T x, T y) const { 3999 // Our graph structure ensures we never have 0 for `y` during 4000 // constant folding. 4001 DCHECK_NE(y, 0); 4002 // Special case -1 to avoid getting a SIGFPE on x86(_64). 4003 return (y == -1) ? -x : x / y; 4004 } 4005 4006 HConstant* Evaluate(HIntConstant* x, HIntConstant* y) const OVERRIDE { 4007 return GetBlock()->GetGraph()->GetIntConstant( 4008 Compute(x->GetValue(), y->GetValue()), GetDexPc()); 4009 } 4010 HConstant* Evaluate(HLongConstant* x, HLongConstant* y) const OVERRIDE { 4011 return GetBlock()->GetGraph()->GetLongConstant( 4012 Compute(x->GetValue(), y->GetValue()), GetDexPc()); 4013 } 4014 4015 static SideEffects SideEffectsForArchRuntimeCalls() { 4016 // The generated code can use a runtime call. 4017 return SideEffects::CanTriggerGC(); 4018 } 4019 4020 DECLARE_INSTRUCTION(Div); 4021 4022 private: 4023 DISALLOW_COPY_AND_ASSIGN(HDiv); 4024}; 4025 4026class HRem : public HBinaryOperation { 4027 public: 4028 HRem(Primitive::Type result_type, 4029 HInstruction* left, 4030 HInstruction* right, 4031 uint32_t dex_pc) 4032 : HBinaryOperation(result_type, left, right, SideEffectsForArchRuntimeCalls(), dex_pc) {} 4033 4034 template <typename T> 4035 T Compute(T x, T y) const { 4036 // Our graph structure ensures we never have 0 for `y` during 4037 // constant folding. 4038 DCHECK_NE(y, 0); 4039 // Special case -1 to avoid getting a SIGFPE on x86(_64). 4040 return (y == -1) ? 0 : x % y; 4041 } 4042 4043 HConstant* Evaluate(HIntConstant* x, HIntConstant* y) const OVERRIDE { 4044 return GetBlock()->GetGraph()->GetIntConstant( 4045 Compute(x->GetValue(), y->GetValue()), GetDexPc()); 4046 } 4047 HConstant* Evaluate(HLongConstant* x, HLongConstant* y) const OVERRIDE { 4048 return GetBlock()->GetGraph()->GetLongConstant( 4049 Compute(x->GetValue(), y->GetValue()), GetDexPc()); 4050 } 4051 4052 4053 static SideEffects SideEffectsForArchRuntimeCalls() { 4054 return SideEffects::CanTriggerGC(); 4055 } 4056 4057 DECLARE_INSTRUCTION(Rem); 4058 4059 private: 4060 DISALLOW_COPY_AND_ASSIGN(HRem); 4061}; 4062 4063class HDivZeroCheck : public HExpression<1> { 4064 public: 4065 // `HDivZeroCheck` can trigger GC, as it may call the `ArithmeticException` 4066 // constructor. 4067 HDivZeroCheck(HInstruction* value, uint32_t dex_pc) 4068 : HExpression(value->GetType(), SideEffects::CanTriggerGC(), dex_pc) { 4069 SetRawInputAt(0, value); 4070 } 4071 4072 Primitive::Type GetType() const OVERRIDE { return InputAt(0)->GetType(); } 4073 4074 bool CanBeMoved() const OVERRIDE { return true; } 4075 4076 bool InstructionDataEquals(HInstruction* other ATTRIBUTE_UNUSED) const OVERRIDE { 4077 return true; 4078 } 4079 4080 bool NeedsEnvironment() const OVERRIDE { return true; } 4081 bool CanThrow() const OVERRIDE { return true; } 4082 4083 DECLARE_INSTRUCTION(DivZeroCheck); 4084 4085 private: 4086 DISALLOW_COPY_AND_ASSIGN(HDivZeroCheck); 4087}; 4088 4089class HShl : public HBinaryOperation { 4090 public: 4091 HShl(Primitive::Type result_type, 4092 HInstruction* left, 4093 HInstruction* right, 4094 uint32_t dex_pc = kNoDexPc) 4095 : HBinaryOperation(result_type, left, right, SideEffects::None(), dex_pc) {} 4096 4097 template <typename T, typename U, typename V> 4098 T Compute(T x, U y, V max_shift_value) const { 4099 static_assert(std::is_same<V, typename std::make_unsigned<T>::type>::value, 4100 "V is not the unsigned integer type corresponding to T"); 4101 return x << (y & max_shift_value); 4102 } 4103 4104 HConstant* Evaluate(HIntConstant* x, HIntConstant* y) const OVERRIDE { 4105 return GetBlock()->GetGraph()->GetIntConstant( 4106 Compute(x->GetValue(), y->GetValue(), kMaxIntShiftValue), GetDexPc()); 4107 } 4108 // There is no `Evaluate(HIntConstant* x, HLongConstant* y)`, as this 4109 // case is handled as `x << static_cast<int>(y)`. 4110 HConstant* Evaluate(HLongConstant* x, HIntConstant* y) const OVERRIDE { 4111 return GetBlock()->GetGraph()->GetLongConstant( 4112 Compute(x->GetValue(), y->GetValue(), kMaxLongShiftValue), GetDexPc()); 4113 } 4114 HConstant* Evaluate(HLongConstant* x, HLongConstant* y) const OVERRIDE { 4115 return GetBlock()->GetGraph()->GetLongConstant( 4116 Compute(x->GetValue(), y->GetValue(), kMaxLongShiftValue), GetDexPc()); 4117 } 4118 4119 DECLARE_INSTRUCTION(Shl); 4120 4121 private: 4122 DISALLOW_COPY_AND_ASSIGN(HShl); 4123}; 4124 4125class HShr : public HBinaryOperation { 4126 public: 4127 HShr(Primitive::Type result_type, 4128 HInstruction* left, 4129 HInstruction* right, 4130 uint32_t dex_pc = kNoDexPc) 4131 : HBinaryOperation(result_type, left, right, SideEffects::None(), dex_pc) {} 4132 4133 template <typename T, typename U, typename V> 4134 T Compute(T x, U y, V max_shift_value) const { 4135 static_assert(std::is_same<V, typename std::make_unsigned<T>::type>::value, 4136 "V is not the unsigned integer type corresponding to T"); 4137 return x >> (y & max_shift_value); 4138 } 4139 4140 HConstant* Evaluate(HIntConstant* x, HIntConstant* y) const OVERRIDE { 4141 return GetBlock()->GetGraph()->GetIntConstant( 4142 Compute(x->GetValue(), y->GetValue(), kMaxIntShiftValue), GetDexPc()); 4143 } 4144 // There is no `Evaluate(HIntConstant* x, HLongConstant* y)`, as this 4145 // case is handled as `x >> static_cast<int>(y)`. 4146 HConstant* Evaluate(HLongConstant* x, HIntConstant* y) const OVERRIDE { 4147 return GetBlock()->GetGraph()->GetLongConstant( 4148 Compute(x->GetValue(), y->GetValue(), kMaxLongShiftValue), GetDexPc()); 4149 } 4150 HConstant* Evaluate(HLongConstant* x, HLongConstant* y) const OVERRIDE { 4151 return GetBlock()->GetGraph()->GetLongConstant( 4152 Compute(x->GetValue(), y->GetValue(), kMaxLongShiftValue), GetDexPc()); 4153 } 4154 4155 DECLARE_INSTRUCTION(Shr); 4156 4157 private: 4158 DISALLOW_COPY_AND_ASSIGN(HShr); 4159}; 4160 4161class HUShr : public HBinaryOperation { 4162 public: 4163 HUShr(Primitive::Type result_type, 4164 HInstruction* left, 4165 HInstruction* right, 4166 uint32_t dex_pc = kNoDexPc) 4167 : HBinaryOperation(result_type, left, right, SideEffects::None(), dex_pc) {} 4168 4169 template <typename T, typename U, typename V> 4170 T Compute(T x, U y, V max_shift_value) const { 4171 static_assert(std::is_same<V, typename std::make_unsigned<T>::type>::value, 4172 "V is not the unsigned integer type corresponding to T"); 4173 V ux = static_cast<V>(x); 4174 return static_cast<T>(ux >> (y & max_shift_value)); 4175 } 4176 4177 HConstant* Evaluate(HIntConstant* x, HIntConstant* y) const OVERRIDE { 4178 return GetBlock()->GetGraph()->GetIntConstant( 4179 Compute(x->GetValue(), y->GetValue(), kMaxIntShiftValue), GetDexPc()); 4180 } 4181 // There is no `Evaluate(HIntConstant* x, HLongConstant* y)`, as this 4182 // case is handled as `x >>> static_cast<int>(y)`. 4183 HConstant* Evaluate(HLongConstant* x, HIntConstant* y) const OVERRIDE { 4184 return GetBlock()->GetGraph()->GetLongConstant( 4185 Compute(x->GetValue(), y->GetValue(), kMaxLongShiftValue), GetDexPc()); 4186 } 4187 HConstant* Evaluate(HLongConstant* x, HLongConstant* y) const OVERRIDE { 4188 return GetBlock()->GetGraph()->GetLongConstant( 4189 Compute(x->GetValue(), y->GetValue(), kMaxLongShiftValue), GetDexPc()); 4190 } 4191 4192 DECLARE_INSTRUCTION(UShr); 4193 4194 private: 4195 DISALLOW_COPY_AND_ASSIGN(HUShr); 4196}; 4197 4198class HAnd : public HBinaryOperation { 4199 public: 4200 HAnd(Primitive::Type result_type, 4201 HInstruction* left, 4202 HInstruction* right, 4203 uint32_t dex_pc = kNoDexPc) 4204 : HBinaryOperation(result_type, left, right, SideEffects::None(), dex_pc) {} 4205 4206 bool IsCommutative() const OVERRIDE { return true; } 4207 4208 template <typename T, typename U> 4209 auto Compute(T x, U y) const -> decltype(x & y) { return x & y; } 4210 4211 HConstant* Evaluate(HIntConstant* x, HIntConstant* y) const OVERRIDE { 4212 return GetBlock()->GetGraph()->GetIntConstant( 4213 Compute(x->GetValue(), y->GetValue()), GetDexPc()); 4214 } 4215 HConstant* Evaluate(HIntConstant* x, HLongConstant* y) const OVERRIDE { 4216 return GetBlock()->GetGraph()->GetLongConstant( 4217 Compute(x->GetValue(), y->GetValue()), GetDexPc()); 4218 } 4219 HConstant* Evaluate(HLongConstant* x, HIntConstant* y) const OVERRIDE { 4220 return GetBlock()->GetGraph()->GetLongConstant( 4221 Compute(x->GetValue(), y->GetValue()), GetDexPc()); 4222 } 4223 HConstant* Evaluate(HLongConstant* x, HLongConstant* y) const OVERRIDE { 4224 return GetBlock()->GetGraph()->GetLongConstant( 4225 Compute(x->GetValue(), y->GetValue()), GetDexPc()); 4226 } 4227 4228 DECLARE_INSTRUCTION(And); 4229 4230 private: 4231 DISALLOW_COPY_AND_ASSIGN(HAnd); 4232}; 4233 4234class HOr : public HBinaryOperation { 4235 public: 4236 HOr(Primitive::Type result_type, 4237 HInstruction* left, 4238 HInstruction* right, 4239 uint32_t dex_pc = kNoDexPc) 4240 : HBinaryOperation(result_type, left, right, SideEffects::None(), dex_pc) {} 4241 4242 bool IsCommutative() const OVERRIDE { return true; } 4243 4244 template <typename T, typename U> 4245 auto Compute(T x, U y) const -> decltype(x | y) { return x | y; } 4246 4247 HConstant* Evaluate(HIntConstant* x, HIntConstant* y) const OVERRIDE { 4248 return GetBlock()->GetGraph()->GetIntConstant( 4249 Compute(x->GetValue(), y->GetValue()), GetDexPc()); 4250 } 4251 HConstant* Evaluate(HIntConstant* x, HLongConstant* y) const OVERRIDE { 4252 return GetBlock()->GetGraph()->GetLongConstant( 4253 Compute(x->GetValue(), y->GetValue()), GetDexPc()); 4254 } 4255 HConstant* Evaluate(HLongConstant* x, HIntConstant* y) const OVERRIDE { 4256 return GetBlock()->GetGraph()->GetLongConstant( 4257 Compute(x->GetValue(), y->GetValue()), GetDexPc()); 4258 } 4259 HConstant* Evaluate(HLongConstant* x, HLongConstant* y) const OVERRIDE { 4260 return GetBlock()->GetGraph()->GetLongConstant( 4261 Compute(x->GetValue(), y->GetValue()), GetDexPc()); 4262 } 4263 4264 DECLARE_INSTRUCTION(Or); 4265 4266 private: 4267 DISALLOW_COPY_AND_ASSIGN(HOr); 4268}; 4269 4270class HXor : public HBinaryOperation { 4271 public: 4272 HXor(Primitive::Type result_type, 4273 HInstruction* left, 4274 HInstruction* right, 4275 uint32_t dex_pc = kNoDexPc) 4276 : HBinaryOperation(result_type, left, right, SideEffects::None(), dex_pc) {} 4277 4278 bool IsCommutative() const OVERRIDE { return true; } 4279 4280 template <typename T, typename U> 4281 auto Compute(T x, U y) const -> decltype(x ^ y) { return x ^ y; } 4282 4283 HConstant* Evaluate(HIntConstant* x, HIntConstant* y) const OVERRIDE { 4284 return GetBlock()->GetGraph()->GetIntConstant( 4285 Compute(x->GetValue(), y->GetValue()), GetDexPc()); 4286 } 4287 HConstant* Evaluate(HIntConstant* x, HLongConstant* y) const OVERRIDE { 4288 return GetBlock()->GetGraph()->GetLongConstant( 4289 Compute(x->GetValue(), y->GetValue()), GetDexPc()); 4290 } 4291 HConstant* Evaluate(HLongConstant* x, HIntConstant* y) const OVERRIDE { 4292 return GetBlock()->GetGraph()->GetLongConstant( 4293 Compute(x->GetValue(), y->GetValue()), GetDexPc()); 4294 } 4295 HConstant* Evaluate(HLongConstant* x, HLongConstant* y) const OVERRIDE { 4296 return GetBlock()->GetGraph()->GetLongConstant( 4297 Compute(x->GetValue(), y->GetValue()), GetDexPc()); 4298 } 4299 4300 DECLARE_INSTRUCTION(Xor); 4301 4302 private: 4303 DISALLOW_COPY_AND_ASSIGN(HXor); 4304}; 4305 4306class HRor : public HBinaryOperation { 4307 public: 4308 HRor(Primitive::Type result_type, HInstruction* value, HInstruction* distance) 4309 : HBinaryOperation(result_type, value, distance) {} 4310 4311 template <typename T, typename U, typename V> 4312 T Compute(T x, U y, V max_shift_value) const { 4313 static_assert(std::is_same<V, typename std::make_unsigned<T>::type>::value, 4314 "V is not the unsigned integer type corresponding to T"); 4315 V ux = static_cast<V>(x); 4316 if ((y & max_shift_value) == 0) { 4317 return static_cast<T>(ux); 4318 } else { 4319 const V reg_bits = sizeof(T) * 8; 4320 return static_cast<T>(ux >> (y & max_shift_value)) | 4321 (x << (reg_bits - (y & max_shift_value))); 4322 } 4323 } 4324 4325 HConstant* Evaluate(HIntConstant* x, HIntConstant* y) const OVERRIDE { 4326 return GetBlock()->GetGraph()->GetIntConstant( 4327 Compute(x->GetValue(), y->GetValue(), kMaxIntShiftValue), GetDexPc()); 4328 } 4329 HConstant* Evaluate(HLongConstant* x, HIntConstant* y) const OVERRIDE { 4330 return GetBlock()->GetGraph()->GetLongConstant( 4331 Compute(x->GetValue(), y->GetValue(), kMaxLongShiftValue), GetDexPc()); 4332 } 4333 HConstant* Evaluate(HLongConstant* x, HLongConstant* y) const OVERRIDE { 4334 return GetBlock()->GetGraph()->GetLongConstant( 4335 Compute(x->GetValue(), y->GetValue(), kMaxLongShiftValue), GetDexPc()); 4336 } 4337 4338 DECLARE_INSTRUCTION(Ror); 4339 4340 private: 4341 DISALLOW_COPY_AND_ASSIGN(HRor); 4342}; 4343 4344// The value of a parameter in this method. Its location depends on 4345// the calling convention. 4346class HParameterValue : public HExpression<0> { 4347 public: 4348 HParameterValue(const DexFile& dex_file, 4349 uint16_t type_index, 4350 uint8_t index, 4351 Primitive::Type parameter_type, 4352 bool is_this = false) 4353 : HExpression(parameter_type, SideEffects::None(), kNoDexPc), 4354 dex_file_(dex_file), 4355 type_index_(type_index), 4356 index_(index), 4357 is_this_(is_this), 4358 can_be_null_(!is_this) {} 4359 4360 const DexFile& GetDexFile() const { return dex_file_; } 4361 uint16_t GetTypeIndex() const { return type_index_; } 4362 uint8_t GetIndex() const { return index_; } 4363 bool IsThis() const { return is_this_; } 4364 4365 bool CanBeNull() const OVERRIDE { return can_be_null_; } 4366 void SetCanBeNull(bool can_be_null) { can_be_null_ = can_be_null; } 4367 4368 DECLARE_INSTRUCTION(ParameterValue); 4369 4370 private: 4371 const DexFile& dex_file_; 4372 const uint16_t type_index_; 4373 // The index of this parameter in the parameters list. Must be less 4374 // than HGraph::number_of_in_vregs_. 4375 const uint8_t index_; 4376 4377 // Whether or not the parameter value corresponds to 'this' argument. 4378 const bool is_this_; 4379 4380 bool can_be_null_; 4381 4382 DISALLOW_COPY_AND_ASSIGN(HParameterValue); 4383}; 4384 4385class HNot : public HUnaryOperation { 4386 public: 4387 HNot(Primitive::Type result_type, HInstruction* input, uint32_t dex_pc = kNoDexPc) 4388 : HUnaryOperation(result_type, input, dex_pc) {} 4389 4390 bool CanBeMoved() const OVERRIDE { return true; } 4391 bool InstructionDataEquals(HInstruction* other ATTRIBUTE_UNUSED) const OVERRIDE { 4392 return true; 4393 } 4394 4395 template <typename T> T Compute(T x) const { return ~x; } 4396 4397 HConstant* Evaluate(HIntConstant* x) const OVERRIDE { 4398 return GetBlock()->GetGraph()->GetIntConstant(Compute(x->GetValue()), GetDexPc()); 4399 } 4400 HConstant* Evaluate(HLongConstant* x) const OVERRIDE { 4401 return GetBlock()->GetGraph()->GetLongConstant(Compute(x->GetValue()), GetDexPc()); 4402 } 4403 4404 DECLARE_INSTRUCTION(Not); 4405 4406 private: 4407 DISALLOW_COPY_AND_ASSIGN(HNot); 4408}; 4409 4410class HBooleanNot : public HUnaryOperation { 4411 public: 4412 explicit HBooleanNot(HInstruction* input, uint32_t dex_pc = kNoDexPc) 4413 : HUnaryOperation(Primitive::Type::kPrimBoolean, input, dex_pc) {} 4414 4415 bool CanBeMoved() const OVERRIDE { return true; } 4416 bool InstructionDataEquals(HInstruction* other ATTRIBUTE_UNUSED) const OVERRIDE { 4417 return true; 4418 } 4419 4420 template <typename T> bool Compute(T x) const { 4421 DCHECK(IsUint<1>(x)); 4422 return !x; 4423 } 4424 4425 HConstant* Evaluate(HIntConstant* x) const OVERRIDE { 4426 return GetBlock()->GetGraph()->GetIntConstant(Compute(x->GetValue()), GetDexPc()); 4427 } 4428 HConstant* Evaluate(HLongConstant* x ATTRIBUTE_UNUSED) const OVERRIDE { 4429 LOG(FATAL) << DebugName() << " is not defined for long values"; 4430 UNREACHABLE(); 4431 } 4432 4433 DECLARE_INSTRUCTION(BooleanNot); 4434 4435 private: 4436 DISALLOW_COPY_AND_ASSIGN(HBooleanNot); 4437}; 4438 4439class HTypeConversion : public HExpression<1> { 4440 public: 4441 // Instantiate a type conversion of `input` to `result_type`. 4442 HTypeConversion(Primitive::Type result_type, HInstruction* input, uint32_t dex_pc) 4443 : HExpression(result_type, 4444 SideEffectsForArchRuntimeCalls(input->GetType(), result_type), 4445 dex_pc) { 4446 SetRawInputAt(0, input); 4447 DCHECK_NE(input->GetType(), result_type); 4448 } 4449 4450 HInstruction* GetInput() const { return InputAt(0); } 4451 Primitive::Type GetInputType() const { return GetInput()->GetType(); } 4452 Primitive::Type GetResultType() const { return GetType(); } 4453 4454 bool CanBeMoved() const OVERRIDE { return true; } 4455 bool InstructionDataEquals(HInstruction* other ATTRIBUTE_UNUSED) const OVERRIDE { return true; } 4456 4457 // Try to statically evaluate the conversion and return a HConstant 4458 // containing the result. If the input cannot be converted, return nullptr. 4459 HConstant* TryStaticEvaluation() const; 4460 4461 static SideEffects SideEffectsForArchRuntimeCalls(Primitive::Type input_type, 4462 Primitive::Type result_type) { 4463 // Some architectures may not require the 'GC' side effects, but at this point 4464 // in the compilation process we do not know what architecture we will 4465 // generate code for, so we must be conservative. 4466 if ((Primitive::IsFloatingPointType(input_type) && Primitive::IsIntegralType(result_type)) 4467 || (input_type == Primitive::kPrimLong && Primitive::IsFloatingPointType(result_type))) { 4468 return SideEffects::CanTriggerGC(); 4469 } 4470 return SideEffects::None(); 4471 } 4472 4473 DECLARE_INSTRUCTION(TypeConversion); 4474 4475 private: 4476 DISALLOW_COPY_AND_ASSIGN(HTypeConversion); 4477}; 4478 4479static constexpr uint32_t kNoRegNumber = -1; 4480 4481class HPhi : public HInstruction { 4482 public: 4483 HPhi(ArenaAllocator* arena, 4484 uint32_t reg_number, 4485 size_t number_of_inputs, 4486 Primitive::Type type, 4487 uint32_t dex_pc = kNoDexPc) 4488 : HInstruction(SideEffects::None(), dex_pc), 4489 inputs_(number_of_inputs, arena->Adapter(kArenaAllocPhiInputs)), 4490 reg_number_(reg_number), 4491 type_(ToPhiType(type)), 4492 // Phis are constructed live and marked dead if conflicting or unused. 4493 // Individual steps of SsaBuilder should assume that if a phi has been 4494 // marked dead, it can be ignored and will be removed by SsaPhiElimination. 4495 is_live_(true), 4496 can_be_null_(true) { 4497 DCHECK_NE(type_, Primitive::kPrimVoid); 4498 } 4499 4500 // Returns a type equivalent to the given `type`, but that a `HPhi` can hold. 4501 static Primitive::Type ToPhiType(Primitive::Type type) { 4502 switch (type) { 4503 case Primitive::kPrimBoolean: 4504 case Primitive::kPrimByte: 4505 case Primitive::kPrimShort: 4506 case Primitive::kPrimChar: 4507 return Primitive::kPrimInt; 4508 default: 4509 return type; 4510 } 4511 } 4512 4513 bool IsCatchPhi() const { return GetBlock()->IsCatchBlock(); } 4514 4515 size_t InputCount() const OVERRIDE { return inputs_.size(); } 4516 4517 void AddInput(HInstruction* input); 4518 void RemoveInputAt(size_t index); 4519 4520 Primitive::Type GetType() const OVERRIDE { return type_; } 4521 void SetType(Primitive::Type new_type) { 4522 // Make sure that only valid type changes occur. The following are allowed: 4523 // (1) int -> float/ref (primitive type propagation), 4524 // (2) long -> double (primitive type propagation). 4525 DCHECK(type_ == new_type || 4526 (type_ == Primitive::kPrimInt && new_type == Primitive::kPrimFloat) || 4527 (type_ == Primitive::kPrimInt && new_type == Primitive::kPrimNot) || 4528 (type_ == Primitive::kPrimLong && new_type == Primitive::kPrimDouble)); 4529 type_ = new_type; 4530 } 4531 4532 bool CanBeNull() const OVERRIDE { return can_be_null_; } 4533 void SetCanBeNull(bool can_be_null) { can_be_null_ = can_be_null; } 4534 4535 uint32_t GetRegNumber() const { return reg_number_; } 4536 4537 void SetDead() { is_live_ = false; } 4538 void SetLive() { is_live_ = true; } 4539 bool IsDead() const { return !is_live_; } 4540 bool IsLive() const { return is_live_; } 4541 4542 bool IsVRegEquivalentOf(HInstruction* other) const { 4543 return other != nullptr 4544 && other->IsPhi() 4545 && other->AsPhi()->GetBlock() == GetBlock() 4546 && other->AsPhi()->GetRegNumber() == GetRegNumber(); 4547 } 4548 4549 // Returns the next equivalent phi (starting from the current one) or null if there is none. 4550 // An equivalent phi is a phi having the same dex register and type. 4551 // It assumes that phis with the same dex register are adjacent. 4552 HPhi* GetNextEquivalentPhiWithSameType() { 4553 HInstruction* next = GetNext(); 4554 while (next != nullptr && next->AsPhi()->GetRegNumber() == reg_number_) { 4555 if (next->GetType() == GetType()) { 4556 return next->AsPhi(); 4557 } 4558 next = next->GetNext(); 4559 } 4560 return nullptr; 4561 } 4562 4563 DECLARE_INSTRUCTION(Phi); 4564 4565 protected: 4566 const HUserRecord<HInstruction*> InputRecordAt(size_t index) const OVERRIDE { 4567 return inputs_[index]; 4568 } 4569 4570 void SetRawInputRecordAt(size_t index, const HUserRecord<HInstruction*>& input) OVERRIDE { 4571 inputs_[index] = input; 4572 } 4573 4574 private: 4575 ArenaVector<HUserRecord<HInstruction*> > inputs_; 4576 const uint32_t reg_number_; 4577 Primitive::Type type_; 4578 bool is_live_; 4579 bool can_be_null_; 4580 4581 DISALLOW_COPY_AND_ASSIGN(HPhi); 4582}; 4583 4584class HNullCheck : public HExpression<1> { 4585 public: 4586 // `HNullCheck` can trigger GC, as it may call the `NullPointerException` 4587 // constructor. 4588 HNullCheck(HInstruction* value, uint32_t dex_pc) 4589 : HExpression(value->GetType(), SideEffects::CanTriggerGC(), dex_pc) { 4590 SetRawInputAt(0, value); 4591 } 4592 4593 bool CanBeMoved() const OVERRIDE { return true; } 4594 bool InstructionDataEquals(HInstruction* other ATTRIBUTE_UNUSED) const OVERRIDE { 4595 return true; 4596 } 4597 4598 bool NeedsEnvironment() const OVERRIDE { return true; } 4599 4600 bool CanThrow() const OVERRIDE { return true; } 4601 4602 bool CanBeNull() const OVERRIDE { return false; } 4603 4604 4605 DECLARE_INSTRUCTION(NullCheck); 4606 4607 private: 4608 DISALLOW_COPY_AND_ASSIGN(HNullCheck); 4609}; 4610 4611class FieldInfo : public ValueObject { 4612 public: 4613 FieldInfo(MemberOffset field_offset, 4614 Primitive::Type field_type, 4615 bool is_volatile, 4616 uint32_t index, 4617 uint16_t declaring_class_def_index, 4618 const DexFile& dex_file, 4619 Handle<mirror::DexCache> dex_cache) 4620 : field_offset_(field_offset), 4621 field_type_(field_type), 4622 is_volatile_(is_volatile), 4623 index_(index), 4624 declaring_class_def_index_(declaring_class_def_index), 4625 dex_file_(dex_file), 4626 dex_cache_(dex_cache) {} 4627 4628 MemberOffset GetFieldOffset() const { return field_offset_; } 4629 Primitive::Type GetFieldType() const { return field_type_; } 4630 uint32_t GetFieldIndex() const { return index_; } 4631 uint16_t GetDeclaringClassDefIndex() const { return declaring_class_def_index_;} 4632 const DexFile& GetDexFile() const { return dex_file_; } 4633 bool IsVolatile() const { return is_volatile_; } 4634 Handle<mirror::DexCache> GetDexCache() const { return dex_cache_; } 4635 4636 private: 4637 const MemberOffset field_offset_; 4638 const Primitive::Type field_type_; 4639 const bool is_volatile_; 4640 const uint32_t index_; 4641 const uint16_t declaring_class_def_index_; 4642 const DexFile& dex_file_; 4643 const Handle<mirror::DexCache> dex_cache_; 4644}; 4645 4646class HInstanceFieldGet : public HExpression<1> { 4647 public: 4648 HInstanceFieldGet(HInstruction* value, 4649 Primitive::Type field_type, 4650 MemberOffset field_offset, 4651 bool is_volatile, 4652 uint32_t field_idx, 4653 uint16_t declaring_class_def_index, 4654 const DexFile& dex_file, 4655 Handle<mirror::DexCache> dex_cache, 4656 uint32_t dex_pc) 4657 : HExpression(field_type, 4658 SideEffects::FieldReadOfType(field_type, is_volatile), 4659 dex_pc), 4660 field_info_(field_offset, 4661 field_type, 4662 is_volatile, 4663 field_idx, 4664 declaring_class_def_index, 4665 dex_file, 4666 dex_cache) { 4667 SetRawInputAt(0, value); 4668 } 4669 4670 bool CanBeMoved() const OVERRIDE { return !IsVolatile(); } 4671 4672 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 4673 HInstanceFieldGet* other_get = other->AsInstanceFieldGet(); 4674 return GetFieldOffset().SizeValue() == other_get->GetFieldOffset().SizeValue(); 4675 } 4676 4677 bool CanDoImplicitNullCheckOn(HInstruction* obj) const OVERRIDE { 4678 return (obj == InputAt(0)) && GetFieldOffset().Uint32Value() < kPageSize; 4679 } 4680 4681 size_t ComputeHashCode() const OVERRIDE { 4682 return (HInstruction::ComputeHashCode() << 7) | GetFieldOffset().SizeValue(); 4683 } 4684 4685 const FieldInfo& GetFieldInfo() const { return field_info_; } 4686 MemberOffset GetFieldOffset() const { return field_info_.GetFieldOffset(); } 4687 Primitive::Type GetFieldType() const { return field_info_.GetFieldType(); } 4688 bool IsVolatile() const { return field_info_.IsVolatile(); } 4689 4690 DECLARE_INSTRUCTION(InstanceFieldGet); 4691 4692 private: 4693 const FieldInfo field_info_; 4694 4695 DISALLOW_COPY_AND_ASSIGN(HInstanceFieldGet); 4696}; 4697 4698class HInstanceFieldSet : public HTemplateInstruction<2> { 4699 public: 4700 HInstanceFieldSet(HInstruction* object, 4701 HInstruction* value, 4702 Primitive::Type field_type, 4703 MemberOffset field_offset, 4704 bool is_volatile, 4705 uint32_t field_idx, 4706 uint16_t declaring_class_def_index, 4707 const DexFile& dex_file, 4708 Handle<mirror::DexCache> dex_cache, 4709 uint32_t dex_pc) 4710 : HTemplateInstruction(SideEffects::FieldWriteOfType(field_type, is_volatile), 4711 dex_pc), 4712 field_info_(field_offset, 4713 field_type, 4714 is_volatile, 4715 field_idx, 4716 declaring_class_def_index, 4717 dex_file, 4718 dex_cache), 4719 value_can_be_null_(true) { 4720 SetRawInputAt(0, object); 4721 SetRawInputAt(1, value); 4722 } 4723 4724 bool CanDoImplicitNullCheckOn(HInstruction* obj) const OVERRIDE { 4725 return (obj == InputAt(0)) && GetFieldOffset().Uint32Value() < kPageSize; 4726 } 4727 4728 const FieldInfo& GetFieldInfo() const { return field_info_; } 4729 MemberOffset GetFieldOffset() const { return field_info_.GetFieldOffset(); } 4730 Primitive::Type GetFieldType() const { return field_info_.GetFieldType(); } 4731 bool IsVolatile() const { return field_info_.IsVolatile(); } 4732 HInstruction* GetValue() const { return InputAt(1); } 4733 bool GetValueCanBeNull() const { return value_can_be_null_; } 4734 void ClearValueCanBeNull() { value_can_be_null_ = false; } 4735 4736 DECLARE_INSTRUCTION(InstanceFieldSet); 4737 4738 private: 4739 const FieldInfo field_info_; 4740 bool value_can_be_null_; 4741 4742 DISALLOW_COPY_AND_ASSIGN(HInstanceFieldSet); 4743}; 4744 4745class HArrayGet : public HExpression<2> { 4746 public: 4747 HArrayGet(HInstruction* array, 4748 HInstruction* index, 4749 Primitive::Type type, 4750 uint32_t dex_pc, 4751 SideEffects additional_side_effects = SideEffects::None()) 4752 : HExpression(type, 4753 SideEffects::ArrayReadOfType(type).Union(additional_side_effects), 4754 dex_pc) { 4755 SetRawInputAt(0, array); 4756 SetRawInputAt(1, index); 4757 } 4758 4759 bool CanBeMoved() const OVERRIDE { return true; } 4760 bool InstructionDataEquals(HInstruction* other ATTRIBUTE_UNUSED) const OVERRIDE { 4761 return true; 4762 } 4763 bool CanDoImplicitNullCheckOn(HInstruction* obj ATTRIBUTE_UNUSED) const OVERRIDE { 4764 // TODO: We can be smarter here. 4765 // Currently, the array access is always preceded by an ArrayLength or a NullCheck 4766 // which generates the implicit null check. There are cases when these can be removed 4767 // to produce better code. If we ever add optimizations to do so we should allow an 4768 // implicit check here (as long as the address falls in the first page). 4769 return false; 4770 } 4771 4772 bool IsEquivalentOf(HArrayGet* other) const { 4773 bool result = (GetDexPc() == other->GetDexPc()); 4774 if (kIsDebugBuild && result) { 4775 DCHECK_EQ(GetBlock(), other->GetBlock()); 4776 DCHECK_EQ(GetArray(), other->GetArray()); 4777 DCHECK_EQ(GetIndex(), other->GetIndex()); 4778 if (Primitive::IsIntOrLongType(GetType())) { 4779 DCHECK(Primitive::IsFloatingPointType(other->GetType())); 4780 } else { 4781 DCHECK(Primitive::IsFloatingPointType(GetType())); 4782 DCHECK(Primitive::IsIntOrLongType(other->GetType())); 4783 } 4784 } 4785 return result; 4786 } 4787 4788 HInstruction* GetArray() const { return InputAt(0); } 4789 HInstruction* GetIndex() const { return InputAt(1); } 4790 4791 DECLARE_INSTRUCTION(ArrayGet); 4792 4793 private: 4794 DISALLOW_COPY_AND_ASSIGN(HArrayGet); 4795}; 4796 4797class HArraySet : public HTemplateInstruction<3> { 4798 public: 4799 HArraySet(HInstruction* array, 4800 HInstruction* index, 4801 HInstruction* value, 4802 Primitive::Type expected_component_type, 4803 uint32_t dex_pc, 4804 SideEffects additional_side_effects = SideEffects::None()) 4805 : HTemplateInstruction( 4806 SideEffects::ArrayWriteOfType(expected_component_type).Union( 4807 SideEffectsForArchRuntimeCalls(value->GetType())).Union( 4808 additional_side_effects), 4809 dex_pc), 4810 expected_component_type_(expected_component_type), 4811 needs_type_check_(value->GetType() == Primitive::kPrimNot), 4812 value_can_be_null_(true), 4813 static_type_of_array_is_object_array_(false) { 4814 SetRawInputAt(0, array); 4815 SetRawInputAt(1, index); 4816 SetRawInputAt(2, value); 4817 } 4818 4819 bool NeedsEnvironment() const OVERRIDE { 4820 // We call a runtime method to throw ArrayStoreException. 4821 return needs_type_check_; 4822 } 4823 4824 // Can throw ArrayStoreException. 4825 bool CanThrow() const OVERRIDE { return needs_type_check_; } 4826 4827 bool CanDoImplicitNullCheckOn(HInstruction* obj ATTRIBUTE_UNUSED) const OVERRIDE { 4828 // TODO: Same as for ArrayGet. 4829 return false; 4830 } 4831 4832 void ClearNeedsTypeCheck() { 4833 needs_type_check_ = false; 4834 } 4835 4836 void ClearValueCanBeNull() { 4837 value_can_be_null_ = false; 4838 } 4839 4840 void SetStaticTypeOfArrayIsObjectArray() { 4841 static_type_of_array_is_object_array_ = true; 4842 } 4843 4844 bool GetValueCanBeNull() const { return value_can_be_null_; } 4845 bool NeedsTypeCheck() const { return needs_type_check_; } 4846 bool StaticTypeOfArrayIsObjectArray() const { return static_type_of_array_is_object_array_; } 4847 4848 HInstruction* GetArray() const { return InputAt(0); } 4849 HInstruction* GetIndex() const { return InputAt(1); } 4850 HInstruction* GetValue() const { return InputAt(2); } 4851 4852 Primitive::Type GetComponentType() const { 4853 // The Dex format does not type floating point index operations. Since the 4854 // `expected_component_type_` is set during building and can therefore not 4855 // be correct, we also check what is the value type. If it is a floating 4856 // point type, we must use that type. 4857 Primitive::Type value_type = GetValue()->GetType(); 4858 return ((value_type == Primitive::kPrimFloat) || (value_type == Primitive::kPrimDouble)) 4859 ? value_type 4860 : expected_component_type_; 4861 } 4862 4863 Primitive::Type GetRawExpectedComponentType() const { 4864 return expected_component_type_; 4865 } 4866 4867 static SideEffects SideEffectsForArchRuntimeCalls(Primitive::Type value_type) { 4868 return (value_type == Primitive::kPrimNot) ? SideEffects::CanTriggerGC() : SideEffects::None(); 4869 } 4870 4871 DECLARE_INSTRUCTION(ArraySet); 4872 4873 private: 4874 const Primitive::Type expected_component_type_; 4875 bool needs_type_check_; 4876 bool value_can_be_null_; 4877 // Cached information for the reference_type_info_ so that codegen 4878 // does not need to inspect the static type. 4879 bool static_type_of_array_is_object_array_; 4880 4881 DISALLOW_COPY_AND_ASSIGN(HArraySet); 4882}; 4883 4884class HArrayLength : public HExpression<1> { 4885 public: 4886 HArrayLength(HInstruction* array, uint32_t dex_pc) 4887 : HExpression(Primitive::kPrimInt, SideEffects::None(), dex_pc) { 4888 // Note that arrays do not change length, so the instruction does not 4889 // depend on any write. 4890 SetRawInputAt(0, array); 4891 } 4892 4893 bool CanBeMoved() const OVERRIDE { return true; } 4894 bool InstructionDataEquals(HInstruction* other ATTRIBUTE_UNUSED) const OVERRIDE { 4895 return true; 4896 } 4897 bool CanDoImplicitNullCheckOn(HInstruction* obj) const OVERRIDE { 4898 return obj == InputAt(0); 4899 } 4900 4901 DECLARE_INSTRUCTION(ArrayLength); 4902 4903 private: 4904 DISALLOW_COPY_AND_ASSIGN(HArrayLength); 4905}; 4906 4907class HBoundsCheck : public HExpression<2> { 4908 public: 4909 // `HBoundsCheck` can trigger GC, as it may call the `IndexOutOfBoundsException` 4910 // constructor. 4911 HBoundsCheck(HInstruction* index, HInstruction* length, uint32_t dex_pc) 4912 : HExpression(index->GetType(), SideEffects::CanTriggerGC(), dex_pc) { 4913 DCHECK(index->GetType() == Primitive::kPrimInt); 4914 SetRawInputAt(0, index); 4915 SetRawInputAt(1, length); 4916 } 4917 4918 bool CanBeMoved() const OVERRIDE { return true; } 4919 bool InstructionDataEquals(HInstruction* other ATTRIBUTE_UNUSED) const OVERRIDE { 4920 return true; 4921 } 4922 4923 bool NeedsEnvironment() const OVERRIDE { return true; } 4924 4925 bool CanThrow() const OVERRIDE { return true; } 4926 4927 HInstruction* GetIndex() const { return InputAt(0); } 4928 4929 DECLARE_INSTRUCTION(BoundsCheck); 4930 4931 private: 4932 DISALLOW_COPY_AND_ASSIGN(HBoundsCheck); 4933}; 4934 4935/** 4936 * Some DEX instructions are folded into multiple HInstructions that need 4937 * to stay live until the last HInstruction. This class 4938 * is used as a marker for the baseline compiler to ensure its preceding 4939 * HInstruction stays live. `index` represents the stack location index of the 4940 * instruction (the actual offset is computed as index * vreg_size). 4941 */ 4942class HTemporary : public HTemplateInstruction<0> { 4943 public: 4944 explicit HTemporary(size_t index, uint32_t dex_pc = kNoDexPc) 4945 : HTemplateInstruction(SideEffects::None(), dex_pc), index_(index) {} 4946 4947 size_t GetIndex() const { return index_; } 4948 4949 Primitive::Type GetType() const OVERRIDE { 4950 // The previous instruction is the one that will be stored in the temporary location. 4951 DCHECK(GetPrevious() != nullptr); 4952 return GetPrevious()->GetType(); 4953 } 4954 4955 DECLARE_INSTRUCTION(Temporary); 4956 4957 private: 4958 const size_t index_; 4959 DISALLOW_COPY_AND_ASSIGN(HTemporary); 4960}; 4961 4962class HSuspendCheck : public HTemplateInstruction<0> { 4963 public: 4964 explicit HSuspendCheck(uint32_t dex_pc) 4965 : HTemplateInstruction(SideEffects::CanTriggerGC(), dex_pc), slow_path_(nullptr) {} 4966 4967 bool NeedsEnvironment() const OVERRIDE { 4968 return true; 4969 } 4970 4971 void SetSlowPath(SlowPathCode* slow_path) { slow_path_ = slow_path; } 4972 SlowPathCode* GetSlowPath() const { return slow_path_; } 4973 4974 DECLARE_INSTRUCTION(SuspendCheck); 4975 4976 private: 4977 // Only used for code generation, in order to share the same slow path between back edges 4978 // of a same loop. 4979 SlowPathCode* slow_path_; 4980 4981 DISALLOW_COPY_AND_ASSIGN(HSuspendCheck); 4982}; 4983 4984// Pseudo-instruction which provides the native debugger with mapping information. 4985// It ensures that we can generate line number and local variables at this point. 4986class HNativeDebugInfo : public HTemplateInstruction<0> { 4987 public: 4988 explicit HNativeDebugInfo(uint32_t dex_pc) 4989 : HTemplateInstruction<0>(SideEffects::None(), dex_pc) {} 4990 4991 bool NeedsEnvironment() const OVERRIDE { 4992 return true; 4993 } 4994 4995 DECLARE_INSTRUCTION(NativeDebugInfo); 4996 4997 private: 4998 DISALLOW_COPY_AND_ASSIGN(HNativeDebugInfo); 4999}; 5000 5001/** 5002 * Instruction to load a Class object. 5003 */ 5004class HLoadClass : public HExpression<1> { 5005 public: 5006 HLoadClass(HCurrentMethod* current_method, 5007 uint16_t type_index, 5008 const DexFile& dex_file, 5009 bool is_referrers_class, 5010 uint32_t dex_pc, 5011 bool needs_access_check, 5012 bool is_in_dex_cache) 5013 : HExpression(Primitive::kPrimNot, SideEffectsForArchRuntimeCalls(), dex_pc), 5014 type_index_(type_index), 5015 dex_file_(dex_file), 5016 is_referrers_class_(is_referrers_class), 5017 generate_clinit_check_(false), 5018 needs_access_check_(needs_access_check), 5019 is_in_dex_cache_(is_in_dex_cache), 5020 loaded_class_rti_(ReferenceTypeInfo::CreateInvalid()) { 5021 // Referrers class should not need access check. We never inline unverified 5022 // methods so we can't possibly end up in this situation. 5023 DCHECK(!is_referrers_class_ || !needs_access_check_); 5024 SetRawInputAt(0, current_method); 5025 } 5026 5027 bool CanBeMoved() const OVERRIDE { return true; } 5028 5029 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 5030 // Note that we don't need to test for generate_clinit_check_. 5031 // Whether or not we need to generate the clinit check is processed in 5032 // prepare_for_register_allocator based on existing HInvokes and HClinitChecks. 5033 return other->AsLoadClass()->type_index_ == type_index_ && 5034 other->AsLoadClass()->needs_access_check_ == needs_access_check_; 5035 } 5036 5037 size_t ComputeHashCode() const OVERRIDE { return type_index_; } 5038 5039 uint16_t GetTypeIndex() const { return type_index_; } 5040 bool IsReferrersClass() const { return is_referrers_class_; } 5041 bool CanBeNull() const OVERRIDE { return false; } 5042 5043 bool NeedsEnvironment() const OVERRIDE { 5044 return CanCallRuntime(); 5045 } 5046 5047 bool MustGenerateClinitCheck() const { 5048 return generate_clinit_check_; 5049 } 5050 5051 void SetMustGenerateClinitCheck(bool generate_clinit_check) { 5052 // The entrypoint the code generator is going to call does not do 5053 // clinit of the class. 5054 DCHECK(!NeedsAccessCheck()); 5055 generate_clinit_check_ = generate_clinit_check; 5056 } 5057 5058 bool CanCallRuntime() const { 5059 return MustGenerateClinitCheck() || 5060 (!is_referrers_class_ && !is_in_dex_cache_) || 5061 needs_access_check_; 5062 } 5063 5064 bool NeedsAccessCheck() const { 5065 return needs_access_check_; 5066 } 5067 5068 bool CanThrow() const OVERRIDE { 5069 return CanCallRuntime(); 5070 } 5071 5072 ReferenceTypeInfo GetLoadedClassRTI() { 5073 return loaded_class_rti_; 5074 } 5075 5076 void SetLoadedClassRTI(ReferenceTypeInfo rti) { 5077 // Make sure we only set exact types (the loaded class should never be merged). 5078 DCHECK(rti.IsExact()); 5079 loaded_class_rti_ = rti; 5080 } 5081 5082 const DexFile& GetDexFile() { return dex_file_; } 5083 5084 bool NeedsDexCacheOfDeclaringClass() const OVERRIDE { return !is_referrers_class_; } 5085 5086 static SideEffects SideEffectsForArchRuntimeCalls() { 5087 return SideEffects::CanTriggerGC(); 5088 } 5089 5090 bool IsInDexCache() const { return is_in_dex_cache_; } 5091 5092 DECLARE_INSTRUCTION(LoadClass); 5093 5094 private: 5095 const uint16_t type_index_; 5096 const DexFile& dex_file_; 5097 const bool is_referrers_class_; 5098 // Whether this instruction must generate the initialization check. 5099 // Used for code generation. 5100 bool generate_clinit_check_; 5101 const bool needs_access_check_; 5102 const bool is_in_dex_cache_; 5103 5104 ReferenceTypeInfo loaded_class_rti_; 5105 5106 DISALLOW_COPY_AND_ASSIGN(HLoadClass); 5107}; 5108 5109class HLoadString : public HExpression<1> { 5110 public: 5111 HLoadString(HCurrentMethod* current_method, 5112 uint32_t string_index, 5113 uint32_t dex_pc, 5114 bool is_in_dex_cache) 5115 : HExpression(Primitive::kPrimNot, SideEffectsForArchRuntimeCalls(), dex_pc), 5116 string_index_(string_index), 5117 is_in_dex_cache_(is_in_dex_cache) { 5118 SetRawInputAt(0, current_method); 5119 } 5120 5121 bool CanBeMoved() const OVERRIDE { return true; } 5122 5123 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 5124 return other->AsLoadString()->string_index_ == string_index_; 5125 } 5126 5127 size_t ComputeHashCode() const OVERRIDE { return string_index_; } 5128 5129 uint32_t GetStringIndex() const { return string_index_; } 5130 5131 // Will call the runtime if the string is not already in the dex cache. 5132 bool NeedsEnvironment() const OVERRIDE { return !IsInDexCache(); } 5133 5134 bool NeedsDexCacheOfDeclaringClass() const OVERRIDE { return true; } 5135 bool CanBeNull() const OVERRIDE { return false; } 5136 bool IsInDexCache() const { return is_in_dex_cache_; } 5137 bool CanThrow() const OVERRIDE { return !IsInDexCache(); } 5138 5139 static SideEffects SideEffectsForArchRuntimeCalls() { 5140 return SideEffects::CanTriggerGC(); 5141 } 5142 5143 DECLARE_INSTRUCTION(LoadString); 5144 5145 private: 5146 const uint32_t string_index_; 5147 const bool is_in_dex_cache_; 5148 5149 DISALLOW_COPY_AND_ASSIGN(HLoadString); 5150}; 5151 5152/** 5153 * Performs an initialization check on its Class object input. 5154 */ 5155class HClinitCheck : public HExpression<1> { 5156 public: 5157 HClinitCheck(HLoadClass* constant, uint32_t dex_pc) 5158 : HExpression( 5159 Primitive::kPrimNot, 5160 SideEffects::AllChanges(), // Assume write/read on all fields/arrays. 5161 dex_pc) { 5162 SetRawInputAt(0, constant); 5163 } 5164 5165 bool CanBeMoved() const OVERRIDE { return true; } 5166 bool InstructionDataEquals(HInstruction* other ATTRIBUTE_UNUSED) const OVERRIDE { 5167 return true; 5168 } 5169 5170 bool NeedsEnvironment() const OVERRIDE { 5171 // May call runtime to initialize the class. 5172 return true; 5173 } 5174 5175 bool CanThrow() const OVERRIDE { return true; } 5176 5177 HLoadClass* GetLoadClass() const { return InputAt(0)->AsLoadClass(); } 5178 5179 DECLARE_INSTRUCTION(ClinitCheck); 5180 5181 private: 5182 DISALLOW_COPY_AND_ASSIGN(HClinitCheck); 5183}; 5184 5185class HStaticFieldGet : public HExpression<1> { 5186 public: 5187 HStaticFieldGet(HInstruction* cls, 5188 Primitive::Type field_type, 5189 MemberOffset field_offset, 5190 bool is_volatile, 5191 uint32_t field_idx, 5192 uint16_t declaring_class_def_index, 5193 const DexFile& dex_file, 5194 Handle<mirror::DexCache> dex_cache, 5195 uint32_t dex_pc) 5196 : HExpression(field_type, 5197 SideEffects::FieldReadOfType(field_type, is_volatile), 5198 dex_pc), 5199 field_info_(field_offset, 5200 field_type, 5201 is_volatile, 5202 field_idx, 5203 declaring_class_def_index, 5204 dex_file, 5205 dex_cache) { 5206 SetRawInputAt(0, cls); 5207 } 5208 5209 5210 bool CanBeMoved() const OVERRIDE { return !IsVolatile(); } 5211 5212 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 5213 HStaticFieldGet* other_get = other->AsStaticFieldGet(); 5214 return GetFieldOffset().SizeValue() == other_get->GetFieldOffset().SizeValue(); 5215 } 5216 5217 size_t ComputeHashCode() const OVERRIDE { 5218 return (HInstruction::ComputeHashCode() << 7) | GetFieldOffset().SizeValue(); 5219 } 5220 5221 const FieldInfo& GetFieldInfo() const { return field_info_; } 5222 MemberOffset GetFieldOffset() const { return field_info_.GetFieldOffset(); } 5223 Primitive::Type GetFieldType() const { return field_info_.GetFieldType(); } 5224 bool IsVolatile() const { return field_info_.IsVolatile(); } 5225 5226 DECLARE_INSTRUCTION(StaticFieldGet); 5227 5228 private: 5229 const FieldInfo field_info_; 5230 5231 DISALLOW_COPY_AND_ASSIGN(HStaticFieldGet); 5232}; 5233 5234class HStaticFieldSet : public HTemplateInstruction<2> { 5235 public: 5236 HStaticFieldSet(HInstruction* cls, 5237 HInstruction* value, 5238 Primitive::Type field_type, 5239 MemberOffset field_offset, 5240 bool is_volatile, 5241 uint32_t field_idx, 5242 uint16_t declaring_class_def_index, 5243 const DexFile& dex_file, 5244 Handle<mirror::DexCache> dex_cache, 5245 uint32_t dex_pc) 5246 : HTemplateInstruction(SideEffects::FieldWriteOfType(field_type, is_volatile), 5247 dex_pc), 5248 field_info_(field_offset, 5249 field_type, 5250 is_volatile, 5251 field_idx, 5252 declaring_class_def_index, 5253 dex_file, 5254 dex_cache), 5255 value_can_be_null_(true) { 5256 SetRawInputAt(0, cls); 5257 SetRawInputAt(1, value); 5258 } 5259 5260 const FieldInfo& GetFieldInfo() const { return field_info_; } 5261 MemberOffset GetFieldOffset() const { return field_info_.GetFieldOffset(); } 5262 Primitive::Type GetFieldType() const { return field_info_.GetFieldType(); } 5263 bool IsVolatile() const { return field_info_.IsVolatile(); } 5264 5265 HInstruction* GetValue() const { return InputAt(1); } 5266 bool GetValueCanBeNull() const { return value_can_be_null_; } 5267 void ClearValueCanBeNull() { value_can_be_null_ = false; } 5268 5269 DECLARE_INSTRUCTION(StaticFieldSet); 5270 5271 private: 5272 const FieldInfo field_info_; 5273 bool value_can_be_null_; 5274 5275 DISALLOW_COPY_AND_ASSIGN(HStaticFieldSet); 5276}; 5277 5278class HUnresolvedInstanceFieldGet : public HExpression<1> { 5279 public: 5280 HUnresolvedInstanceFieldGet(HInstruction* obj, 5281 Primitive::Type field_type, 5282 uint32_t field_index, 5283 uint32_t dex_pc) 5284 : HExpression(field_type, SideEffects::AllExceptGCDependency(), dex_pc), 5285 field_index_(field_index) { 5286 SetRawInputAt(0, obj); 5287 } 5288 5289 bool NeedsEnvironment() const OVERRIDE { return true; } 5290 bool CanThrow() const OVERRIDE { return true; } 5291 5292 Primitive::Type GetFieldType() const { return GetType(); } 5293 uint32_t GetFieldIndex() const { return field_index_; } 5294 5295 DECLARE_INSTRUCTION(UnresolvedInstanceFieldGet); 5296 5297 private: 5298 const uint32_t field_index_; 5299 5300 DISALLOW_COPY_AND_ASSIGN(HUnresolvedInstanceFieldGet); 5301}; 5302 5303class HUnresolvedInstanceFieldSet : public HTemplateInstruction<2> { 5304 public: 5305 HUnresolvedInstanceFieldSet(HInstruction* obj, 5306 HInstruction* value, 5307 Primitive::Type field_type, 5308 uint32_t field_index, 5309 uint32_t dex_pc) 5310 : HTemplateInstruction(SideEffects::AllExceptGCDependency(), dex_pc), 5311 field_type_(field_type), 5312 field_index_(field_index) { 5313 DCHECK_EQ(field_type, value->GetType()); 5314 SetRawInputAt(0, obj); 5315 SetRawInputAt(1, value); 5316 } 5317 5318 bool NeedsEnvironment() const OVERRIDE { return true; } 5319 bool CanThrow() const OVERRIDE { return true; } 5320 5321 Primitive::Type GetFieldType() const { return field_type_; } 5322 uint32_t GetFieldIndex() const { return field_index_; } 5323 5324 DECLARE_INSTRUCTION(UnresolvedInstanceFieldSet); 5325 5326 private: 5327 const Primitive::Type field_type_; 5328 const uint32_t field_index_; 5329 5330 DISALLOW_COPY_AND_ASSIGN(HUnresolvedInstanceFieldSet); 5331}; 5332 5333class HUnresolvedStaticFieldGet : public HExpression<0> { 5334 public: 5335 HUnresolvedStaticFieldGet(Primitive::Type field_type, 5336 uint32_t field_index, 5337 uint32_t dex_pc) 5338 : HExpression(field_type, SideEffects::AllExceptGCDependency(), dex_pc), 5339 field_index_(field_index) { 5340 } 5341 5342 bool NeedsEnvironment() const OVERRIDE { return true; } 5343 bool CanThrow() const OVERRIDE { return true; } 5344 5345 Primitive::Type GetFieldType() const { return GetType(); } 5346 uint32_t GetFieldIndex() const { return field_index_; } 5347 5348 DECLARE_INSTRUCTION(UnresolvedStaticFieldGet); 5349 5350 private: 5351 const uint32_t field_index_; 5352 5353 DISALLOW_COPY_AND_ASSIGN(HUnresolvedStaticFieldGet); 5354}; 5355 5356class HUnresolvedStaticFieldSet : public HTemplateInstruction<1> { 5357 public: 5358 HUnresolvedStaticFieldSet(HInstruction* value, 5359 Primitive::Type field_type, 5360 uint32_t field_index, 5361 uint32_t dex_pc) 5362 : HTemplateInstruction(SideEffects::AllExceptGCDependency(), dex_pc), 5363 field_type_(field_type), 5364 field_index_(field_index) { 5365 DCHECK_EQ(field_type, value->GetType()); 5366 SetRawInputAt(0, value); 5367 } 5368 5369 bool NeedsEnvironment() const OVERRIDE { return true; } 5370 bool CanThrow() const OVERRIDE { return true; } 5371 5372 Primitive::Type GetFieldType() const { return field_type_; } 5373 uint32_t GetFieldIndex() const { return field_index_; } 5374 5375 DECLARE_INSTRUCTION(UnresolvedStaticFieldSet); 5376 5377 private: 5378 const Primitive::Type field_type_; 5379 const uint32_t field_index_; 5380 5381 DISALLOW_COPY_AND_ASSIGN(HUnresolvedStaticFieldSet); 5382}; 5383 5384// Implement the move-exception DEX instruction. 5385class HLoadException : public HExpression<0> { 5386 public: 5387 explicit HLoadException(uint32_t dex_pc = kNoDexPc) 5388 : HExpression(Primitive::kPrimNot, SideEffects::None(), dex_pc) {} 5389 5390 bool CanBeNull() const OVERRIDE { return false; } 5391 5392 DECLARE_INSTRUCTION(LoadException); 5393 5394 private: 5395 DISALLOW_COPY_AND_ASSIGN(HLoadException); 5396}; 5397 5398// Implicit part of move-exception which clears thread-local exception storage. 5399// Must not be removed because the runtime expects the TLS to get cleared. 5400class HClearException : public HTemplateInstruction<0> { 5401 public: 5402 explicit HClearException(uint32_t dex_pc = kNoDexPc) 5403 : HTemplateInstruction(SideEffects::AllWrites(), dex_pc) {} 5404 5405 DECLARE_INSTRUCTION(ClearException); 5406 5407 private: 5408 DISALLOW_COPY_AND_ASSIGN(HClearException); 5409}; 5410 5411class HThrow : public HTemplateInstruction<1> { 5412 public: 5413 HThrow(HInstruction* exception, uint32_t dex_pc) 5414 : HTemplateInstruction(SideEffects::CanTriggerGC(), dex_pc) { 5415 SetRawInputAt(0, exception); 5416 } 5417 5418 bool IsControlFlow() const OVERRIDE { return true; } 5419 5420 bool NeedsEnvironment() const OVERRIDE { return true; } 5421 5422 bool CanThrow() const OVERRIDE { return true; } 5423 5424 5425 DECLARE_INSTRUCTION(Throw); 5426 5427 private: 5428 DISALLOW_COPY_AND_ASSIGN(HThrow); 5429}; 5430 5431/** 5432 * Implementation strategies for the code generator of a HInstanceOf 5433 * or `HCheckCast`. 5434 */ 5435enum class TypeCheckKind { 5436 kUnresolvedCheck, // Check against an unresolved type. 5437 kExactCheck, // Can do a single class compare. 5438 kClassHierarchyCheck, // Can just walk the super class chain. 5439 kAbstractClassCheck, // Can just walk the super class chain, starting one up. 5440 kInterfaceCheck, // No optimization yet when checking against an interface. 5441 kArrayObjectCheck, // Can just check if the array is not primitive. 5442 kArrayCheck // No optimization yet when checking against a generic array. 5443}; 5444 5445class HInstanceOf : public HExpression<2> { 5446 public: 5447 HInstanceOf(HInstruction* object, 5448 HLoadClass* constant, 5449 TypeCheckKind check_kind, 5450 uint32_t dex_pc) 5451 : HExpression(Primitive::kPrimBoolean, 5452 SideEffectsForArchRuntimeCalls(check_kind), 5453 dex_pc), 5454 check_kind_(check_kind), 5455 must_do_null_check_(true) { 5456 SetRawInputAt(0, object); 5457 SetRawInputAt(1, constant); 5458 } 5459 5460 bool CanBeMoved() const OVERRIDE { return true; } 5461 5462 bool InstructionDataEquals(HInstruction* other ATTRIBUTE_UNUSED) const OVERRIDE { 5463 return true; 5464 } 5465 5466 bool NeedsEnvironment() const OVERRIDE { 5467 return CanCallRuntime(check_kind_); 5468 } 5469 5470 bool IsExactCheck() const { return check_kind_ == TypeCheckKind::kExactCheck; } 5471 5472 TypeCheckKind GetTypeCheckKind() const { return check_kind_; } 5473 5474 // Used only in code generation. 5475 bool MustDoNullCheck() const { return must_do_null_check_; } 5476 void ClearMustDoNullCheck() { must_do_null_check_ = false; } 5477 5478 static bool CanCallRuntime(TypeCheckKind check_kind) { 5479 // Mips currently does runtime calls for any other checks. 5480 return check_kind != TypeCheckKind::kExactCheck; 5481 } 5482 5483 static SideEffects SideEffectsForArchRuntimeCalls(TypeCheckKind check_kind) { 5484 return CanCallRuntime(check_kind) ? SideEffects::CanTriggerGC() : SideEffects::None(); 5485 } 5486 5487 DECLARE_INSTRUCTION(InstanceOf); 5488 5489 private: 5490 const TypeCheckKind check_kind_; 5491 bool must_do_null_check_; 5492 5493 DISALLOW_COPY_AND_ASSIGN(HInstanceOf); 5494}; 5495 5496class HBoundType : public HExpression<1> { 5497 public: 5498 HBoundType(HInstruction* input, uint32_t dex_pc = kNoDexPc) 5499 : HExpression(Primitive::kPrimNot, SideEffects::None(), dex_pc), 5500 upper_bound_(ReferenceTypeInfo::CreateInvalid()), 5501 upper_can_be_null_(true), 5502 can_be_null_(true) { 5503 DCHECK_EQ(input->GetType(), Primitive::kPrimNot); 5504 SetRawInputAt(0, input); 5505 } 5506 5507 // {Get,Set}Upper* should only be used in reference type propagation. 5508 const ReferenceTypeInfo& GetUpperBound() const { return upper_bound_; } 5509 bool GetUpperCanBeNull() const { return upper_can_be_null_; } 5510 void SetUpperBound(const ReferenceTypeInfo& upper_bound, bool can_be_null); 5511 5512 void SetCanBeNull(bool can_be_null) { 5513 DCHECK(upper_can_be_null_ || !can_be_null); 5514 can_be_null_ = can_be_null; 5515 } 5516 5517 bool CanBeNull() const OVERRIDE { return can_be_null_; } 5518 5519 DECLARE_INSTRUCTION(BoundType); 5520 5521 private: 5522 // Encodes the most upper class that this instruction can have. In other words 5523 // it is always the case that GetUpperBound().IsSupertypeOf(GetReferenceType()). 5524 // It is used to bound the type in cases like: 5525 // if (x instanceof ClassX) { 5526 // // uper_bound_ will be ClassX 5527 // } 5528 ReferenceTypeInfo upper_bound_; 5529 // Represents the top constraint that can_be_null_ cannot exceed (i.e. if this 5530 // is false then can_be_null_ cannot be true). 5531 bool upper_can_be_null_; 5532 bool can_be_null_; 5533 5534 DISALLOW_COPY_AND_ASSIGN(HBoundType); 5535}; 5536 5537class HCheckCast : public HTemplateInstruction<2> { 5538 public: 5539 HCheckCast(HInstruction* object, 5540 HLoadClass* constant, 5541 TypeCheckKind check_kind, 5542 uint32_t dex_pc) 5543 : HTemplateInstruction(SideEffects::CanTriggerGC(), dex_pc), 5544 check_kind_(check_kind), 5545 must_do_null_check_(true) { 5546 SetRawInputAt(0, object); 5547 SetRawInputAt(1, constant); 5548 } 5549 5550 bool CanBeMoved() const OVERRIDE { return true; } 5551 5552 bool InstructionDataEquals(HInstruction* other ATTRIBUTE_UNUSED) const OVERRIDE { 5553 return true; 5554 } 5555 5556 bool NeedsEnvironment() const OVERRIDE { 5557 // Instruction may throw a CheckCastError. 5558 return true; 5559 } 5560 5561 bool CanThrow() const OVERRIDE { return true; } 5562 5563 bool MustDoNullCheck() const { return must_do_null_check_; } 5564 void ClearMustDoNullCheck() { must_do_null_check_ = false; } 5565 TypeCheckKind GetTypeCheckKind() const { return check_kind_; } 5566 5567 bool IsExactCheck() const { return check_kind_ == TypeCheckKind::kExactCheck; } 5568 5569 DECLARE_INSTRUCTION(CheckCast); 5570 5571 private: 5572 const TypeCheckKind check_kind_; 5573 bool must_do_null_check_; 5574 5575 DISALLOW_COPY_AND_ASSIGN(HCheckCast); 5576}; 5577 5578class HMemoryBarrier : public HTemplateInstruction<0> { 5579 public: 5580 explicit HMemoryBarrier(MemBarrierKind barrier_kind, uint32_t dex_pc = kNoDexPc) 5581 : HTemplateInstruction( 5582 SideEffects::AllWritesAndReads(), dex_pc), // Assume write/read on all fields/arrays. 5583 barrier_kind_(barrier_kind) {} 5584 5585 MemBarrierKind GetBarrierKind() { return barrier_kind_; } 5586 5587 DECLARE_INSTRUCTION(MemoryBarrier); 5588 5589 private: 5590 const MemBarrierKind barrier_kind_; 5591 5592 DISALLOW_COPY_AND_ASSIGN(HMemoryBarrier); 5593}; 5594 5595class HMonitorOperation : public HTemplateInstruction<1> { 5596 public: 5597 enum OperationKind { 5598 kEnter, 5599 kExit, 5600 }; 5601 5602 HMonitorOperation(HInstruction* object, OperationKind kind, uint32_t dex_pc) 5603 : HTemplateInstruction( 5604 SideEffects::AllExceptGCDependency(), dex_pc), // Assume write/read on all fields/arrays. 5605 kind_(kind) { 5606 SetRawInputAt(0, object); 5607 } 5608 5609 // Instruction may go into runtime, so we need an environment. 5610 bool NeedsEnvironment() const OVERRIDE { return true; } 5611 5612 bool CanThrow() const OVERRIDE { 5613 // Verifier guarantees that monitor-exit cannot throw. 5614 // This is important because it allows the HGraphBuilder to remove 5615 // a dead throw-catch loop generated for `synchronized` blocks/methods. 5616 return IsEnter(); 5617 } 5618 5619 5620 bool IsEnter() const { return kind_ == kEnter; } 5621 5622 DECLARE_INSTRUCTION(MonitorOperation); 5623 5624 private: 5625 const OperationKind kind_; 5626 5627 private: 5628 DISALLOW_COPY_AND_ASSIGN(HMonitorOperation); 5629}; 5630 5631class HSelect : public HExpression<3> { 5632 public: 5633 HSelect(HInstruction* condition, 5634 HInstruction* true_value, 5635 HInstruction* false_value, 5636 uint32_t dex_pc) 5637 : HExpression(HPhi::ToPhiType(true_value->GetType()), SideEffects::None(), dex_pc) { 5638 DCHECK_EQ(HPhi::ToPhiType(true_value->GetType()), HPhi::ToPhiType(false_value->GetType())); 5639 5640 // First input must be `true_value` or `false_value` to allow codegens to 5641 // use the SameAsFirstInput allocation policy. We make it `false_value`, so 5642 // that architectures which implement HSelect as a conditional move also 5643 // will not need to invert the condition. 5644 SetRawInputAt(0, false_value); 5645 SetRawInputAt(1, true_value); 5646 SetRawInputAt(2, condition); 5647 } 5648 5649 HInstruction* GetFalseValue() const { return InputAt(0); } 5650 HInstruction* GetTrueValue() const { return InputAt(1); } 5651 HInstruction* GetCondition() const { return InputAt(2); } 5652 5653 bool CanBeMoved() const OVERRIDE { return true; } 5654 bool InstructionDataEquals(HInstruction* other ATTRIBUTE_UNUSED) const OVERRIDE { return true; } 5655 5656 bool CanBeNull() const OVERRIDE { 5657 return GetTrueValue()->CanBeNull() || GetFalseValue()->CanBeNull(); 5658 } 5659 5660 DECLARE_INSTRUCTION(Select); 5661 5662 private: 5663 DISALLOW_COPY_AND_ASSIGN(HSelect); 5664}; 5665 5666class MoveOperands : public ArenaObject<kArenaAllocMoveOperands> { 5667 public: 5668 MoveOperands(Location source, 5669 Location destination, 5670 Primitive::Type type, 5671 HInstruction* instruction) 5672 : source_(source), destination_(destination), type_(type), instruction_(instruction) {} 5673 5674 Location GetSource() const { return source_; } 5675 Location GetDestination() const { return destination_; } 5676 5677 void SetSource(Location value) { source_ = value; } 5678 void SetDestination(Location value) { destination_ = value; } 5679 5680 // The parallel move resolver marks moves as "in-progress" by clearing the 5681 // destination (but not the source). 5682 Location MarkPending() { 5683 DCHECK(!IsPending()); 5684 Location dest = destination_; 5685 destination_ = Location::NoLocation(); 5686 return dest; 5687 } 5688 5689 void ClearPending(Location dest) { 5690 DCHECK(IsPending()); 5691 destination_ = dest; 5692 } 5693 5694 bool IsPending() const { 5695 DCHECK(source_.IsValid() || destination_.IsInvalid()); 5696 return destination_.IsInvalid() && source_.IsValid(); 5697 } 5698 5699 // True if this blocks a move from the given location. 5700 bool Blocks(Location loc) const { 5701 return !IsEliminated() && source_.OverlapsWith(loc); 5702 } 5703 5704 // A move is redundant if it's been eliminated, if its source and 5705 // destination are the same, or if its destination is unneeded. 5706 bool IsRedundant() const { 5707 return IsEliminated() || destination_.IsInvalid() || source_.Equals(destination_); 5708 } 5709 5710 // We clear both operands to indicate move that's been eliminated. 5711 void Eliminate() { 5712 source_ = destination_ = Location::NoLocation(); 5713 } 5714 5715 bool IsEliminated() const { 5716 DCHECK(!source_.IsInvalid() || destination_.IsInvalid()); 5717 return source_.IsInvalid(); 5718 } 5719 5720 Primitive::Type GetType() const { return type_; } 5721 5722 bool Is64BitMove() const { 5723 return Primitive::Is64BitType(type_); 5724 } 5725 5726 HInstruction* GetInstruction() const { return instruction_; } 5727 5728 private: 5729 Location source_; 5730 Location destination_; 5731 // The type this move is for. 5732 Primitive::Type type_; 5733 // The instruction this move is assocatied with. Null when this move is 5734 // for moving an input in the expected locations of user (including a phi user). 5735 // This is only used in debug mode, to ensure we do not connect interval siblings 5736 // in the same parallel move. 5737 HInstruction* instruction_; 5738}; 5739 5740std::ostream& operator<<(std::ostream& os, const MoveOperands& rhs); 5741 5742static constexpr size_t kDefaultNumberOfMoves = 4; 5743 5744class HParallelMove : public HTemplateInstruction<0> { 5745 public: 5746 explicit HParallelMove(ArenaAllocator* arena, uint32_t dex_pc = kNoDexPc) 5747 : HTemplateInstruction(SideEffects::None(), dex_pc), 5748 moves_(arena->Adapter(kArenaAllocMoveOperands)) { 5749 moves_.reserve(kDefaultNumberOfMoves); 5750 } 5751 5752 void AddMove(Location source, 5753 Location destination, 5754 Primitive::Type type, 5755 HInstruction* instruction) { 5756 DCHECK(source.IsValid()); 5757 DCHECK(destination.IsValid()); 5758 if (kIsDebugBuild) { 5759 if (instruction != nullptr) { 5760 for (const MoveOperands& move : moves_) { 5761 if (move.GetInstruction() == instruction) { 5762 // Special case the situation where the move is for the spill slot 5763 // of the instruction. 5764 if ((GetPrevious() == instruction) 5765 || ((GetPrevious() == nullptr) 5766 && instruction->IsPhi() 5767 && instruction->GetBlock() == GetBlock())) { 5768 DCHECK_NE(destination.GetKind(), move.GetDestination().GetKind()) 5769 << "Doing parallel moves for the same instruction."; 5770 } else { 5771 DCHECK(false) << "Doing parallel moves for the same instruction."; 5772 } 5773 } 5774 } 5775 } 5776 for (const MoveOperands& move : moves_) { 5777 DCHECK(!destination.OverlapsWith(move.GetDestination())) 5778 << "Overlapped destination for two moves in a parallel move: " 5779 << move.GetSource() << " ==> " << move.GetDestination() << " and " 5780 << source << " ==> " << destination; 5781 } 5782 } 5783 moves_.emplace_back(source, destination, type, instruction); 5784 } 5785 5786 MoveOperands* MoveOperandsAt(size_t index) { 5787 return &moves_[index]; 5788 } 5789 5790 size_t NumMoves() const { return moves_.size(); } 5791 5792 DECLARE_INSTRUCTION(ParallelMove); 5793 5794 private: 5795 ArenaVector<MoveOperands> moves_; 5796 5797 DISALLOW_COPY_AND_ASSIGN(HParallelMove); 5798}; 5799 5800} // namespace art 5801 5802#ifdef ART_ENABLE_CODEGEN_arm 5803#include "nodes_arm.h" 5804#endif 5805#ifdef ART_ENABLE_CODEGEN_arm64 5806#include "nodes_arm64.h" 5807#endif 5808#ifdef ART_ENABLE_CODEGEN_x86 5809#include "nodes_x86.h" 5810#endif 5811 5812namespace art { 5813 5814class HGraphVisitor : public ValueObject { 5815 public: 5816 explicit HGraphVisitor(HGraph* graph) : graph_(graph) {} 5817 virtual ~HGraphVisitor() {} 5818 5819 virtual void VisitInstruction(HInstruction* instruction ATTRIBUTE_UNUSED) {} 5820 virtual void VisitBasicBlock(HBasicBlock* block); 5821 5822 // Visit the graph following basic block insertion order. 5823 void VisitInsertionOrder(); 5824 5825 // Visit the graph following dominator tree reverse post-order. 5826 void VisitReversePostOrder(); 5827 5828 HGraph* GetGraph() const { return graph_; } 5829 5830 // Visit functions for instruction classes. 5831#define DECLARE_VISIT_INSTRUCTION(name, super) \ 5832 virtual void Visit##name(H##name* instr) { VisitInstruction(instr); } 5833 5834 FOR_EACH_INSTRUCTION(DECLARE_VISIT_INSTRUCTION) 5835 5836#undef DECLARE_VISIT_INSTRUCTION 5837 5838 private: 5839 HGraph* const graph_; 5840 5841 DISALLOW_COPY_AND_ASSIGN(HGraphVisitor); 5842}; 5843 5844class HGraphDelegateVisitor : public HGraphVisitor { 5845 public: 5846 explicit HGraphDelegateVisitor(HGraph* graph) : HGraphVisitor(graph) {} 5847 virtual ~HGraphDelegateVisitor() {} 5848 5849 // Visit functions that delegate to to super class. 5850#define DECLARE_VISIT_INSTRUCTION(name, super) \ 5851 void Visit##name(H##name* instr) OVERRIDE { Visit##super(instr); } 5852 5853 FOR_EACH_INSTRUCTION(DECLARE_VISIT_INSTRUCTION) 5854 5855#undef DECLARE_VISIT_INSTRUCTION 5856 5857 private: 5858 DISALLOW_COPY_AND_ASSIGN(HGraphDelegateVisitor); 5859}; 5860 5861class HInsertionOrderIterator : public ValueObject { 5862 public: 5863 explicit HInsertionOrderIterator(const HGraph& graph) : graph_(graph), index_(0) {} 5864 5865 bool Done() const { return index_ == graph_.GetBlocks().size(); } 5866 HBasicBlock* Current() const { return graph_.GetBlocks()[index_]; } 5867 void Advance() { ++index_; } 5868 5869 private: 5870 const HGraph& graph_; 5871 size_t index_; 5872 5873 DISALLOW_COPY_AND_ASSIGN(HInsertionOrderIterator); 5874}; 5875 5876class HReversePostOrderIterator : public ValueObject { 5877 public: 5878 explicit HReversePostOrderIterator(const HGraph& graph) : graph_(graph), index_(0) { 5879 // Check that reverse post order of the graph has been built. 5880 DCHECK(!graph.GetReversePostOrder().empty()); 5881 } 5882 5883 bool Done() const { return index_ == graph_.GetReversePostOrder().size(); } 5884 HBasicBlock* Current() const { return graph_.GetReversePostOrder()[index_]; } 5885 void Advance() { ++index_; } 5886 5887 private: 5888 const HGraph& graph_; 5889 size_t index_; 5890 5891 DISALLOW_COPY_AND_ASSIGN(HReversePostOrderIterator); 5892}; 5893 5894class HPostOrderIterator : public ValueObject { 5895 public: 5896 explicit HPostOrderIterator(const HGraph& graph) 5897 : graph_(graph), index_(graph_.GetReversePostOrder().size()) { 5898 // Check that reverse post order of the graph has been built. 5899 DCHECK(!graph.GetReversePostOrder().empty()); 5900 } 5901 5902 bool Done() const { return index_ == 0; } 5903 HBasicBlock* Current() const { return graph_.GetReversePostOrder()[index_ - 1u]; } 5904 void Advance() { --index_; } 5905 5906 private: 5907 const HGraph& graph_; 5908 size_t index_; 5909 5910 DISALLOW_COPY_AND_ASSIGN(HPostOrderIterator); 5911}; 5912 5913class HLinearPostOrderIterator : public ValueObject { 5914 public: 5915 explicit HLinearPostOrderIterator(const HGraph& graph) 5916 : order_(graph.GetLinearOrder()), index_(graph.GetLinearOrder().size()) {} 5917 5918 bool Done() const { return index_ == 0; } 5919 5920 HBasicBlock* Current() const { return order_[index_ - 1u]; } 5921 5922 void Advance() { 5923 --index_; 5924 DCHECK_GE(index_, 0U); 5925 } 5926 5927 private: 5928 const ArenaVector<HBasicBlock*>& order_; 5929 size_t index_; 5930 5931 DISALLOW_COPY_AND_ASSIGN(HLinearPostOrderIterator); 5932}; 5933 5934class HLinearOrderIterator : public ValueObject { 5935 public: 5936 explicit HLinearOrderIterator(const HGraph& graph) 5937 : order_(graph.GetLinearOrder()), index_(0) {} 5938 5939 bool Done() const { return index_ == order_.size(); } 5940 HBasicBlock* Current() const { return order_[index_]; } 5941 void Advance() { ++index_; } 5942 5943 private: 5944 const ArenaVector<HBasicBlock*>& order_; 5945 size_t index_; 5946 5947 DISALLOW_COPY_AND_ASSIGN(HLinearOrderIterator); 5948}; 5949 5950// Iterator over the blocks that art part of the loop. Includes blocks part 5951// of an inner loop. The order in which the blocks are iterated is on their 5952// block id. 5953class HBlocksInLoopIterator : public ValueObject { 5954 public: 5955 explicit HBlocksInLoopIterator(const HLoopInformation& info) 5956 : blocks_in_loop_(info.GetBlocks()), 5957 blocks_(info.GetHeader()->GetGraph()->GetBlocks()), 5958 index_(0) { 5959 if (!blocks_in_loop_.IsBitSet(index_)) { 5960 Advance(); 5961 } 5962 } 5963 5964 bool Done() const { return index_ == blocks_.size(); } 5965 HBasicBlock* Current() const { return blocks_[index_]; } 5966 void Advance() { 5967 ++index_; 5968 for (size_t e = blocks_.size(); index_ < e; ++index_) { 5969 if (blocks_in_loop_.IsBitSet(index_)) { 5970 break; 5971 } 5972 } 5973 } 5974 5975 private: 5976 const BitVector& blocks_in_loop_; 5977 const ArenaVector<HBasicBlock*>& blocks_; 5978 size_t index_; 5979 5980 DISALLOW_COPY_AND_ASSIGN(HBlocksInLoopIterator); 5981}; 5982 5983// Iterator over the blocks that art part of the loop. Includes blocks part 5984// of an inner loop. The order in which the blocks are iterated is reverse 5985// post order. 5986class HBlocksInLoopReversePostOrderIterator : public ValueObject { 5987 public: 5988 explicit HBlocksInLoopReversePostOrderIterator(const HLoopInformation& info) 5989 : blocks_in_loop_(info.GetBlocks()), 5990 blocks_(info.GetHeader()->GetGraph()->GetReversePostOrder()), 5991 index_(0) { 5992 if (!blocks_in_loop_.IsBitSet(blocks_[index_]->GetBlockId())) { 5993 Advance(); 5994 } 5995 } 5996 5997 bool Done() const { return index_ == blocks_.size(); } 5998 HBasicBlock* Current() const { return blocks_[index_]; } 5999 void Advance() { 6000 ++index_; 6001 for (size_t e = blocks_.size(); index_ < e; ++index_) { 6002 if (blocks_in_loop_.IsBitSet(blocks_[index_]->GetBlockId())) { 6003 break; 6004 } 6005 } 6006 } 6007 6008 private: 6009 const BitVector& blocks_in_loop_; 6010 const ArenaVector<HBasicBlock*>& blocks_; 6011 size_t index_; 6012 6013 DISALLOW_COPY_AND_ASSIGN(HBlocksInLoopReversePostOrderIterator); 6014}; 6015 6016inline int64_t Int64FromConstant(HConstant* constant) { 6017 DCHECK(constant->IsIntConstant() || constant->IsLongConstant()); 6018 return constant->IsIntConstant() ? constant->AsIntConstant()->GetValue() 6019 : constant->AsLongConstant()->GetValue(); 6020} 6021 6022inline bool IsSameDexFile(const DexFile& lhs, const DexFile& rhs) { 6023 // For the purposes of the compiler, the dex files must actually be the same object 6024 // if we want to safely treat them as the same. This is especially important for JIT 6025 // as custom class loaders can open the same underlying file (or memory) multiple 6026 // times and provide different class resolution but no two class loaders should ever 6027 // use the same DexFile object - doing so is an unsupported hack that can lead to 6028 // all sorts of weird failures. 6029 return &lhs == &rhs; 6030} 6031 6032#define INSTRUCTION_TYPE_CHECK(type, super) \ 6033 inline bool HInstruction::Is##type() const { return GetKind() == k##type; } \ 6034 inline const H##type* HInstruction::As##type() const { \ 6035 return Is##type() ? down_cast<const H##type*>(this) : nullptr; \ 6036 } \ 6037 inline H##type* HInstruction::As##type() { \ 6038 return Is##type() ? static_cast<H##type*>(this) : nullptr; \ 6039 } 6040 6041 FOR_EACH_CONCRETE_INSTRUCTION(INSTRUCTION_TYPE_CHECK) 6042#undef INSTRUCTION_TYPE_CHECK 6043 6044} // namespace art 6045 6046#endif // ART_COMPILER_OPTIMIZING_NODES_H_ 6047