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