nodes.h revision 69aa60163989c33a008115205d39732a76ecc1dc
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 "base/arena_containers.h" 21#include "base/arena_object.h" 22#include "dex/compiler_enums.h" 23#include "entrypoints/quick/quick_entrypoints_enum.h" 24#include "handle.h" 25#include "handle_scope.h" 26#include "invoke_type.h" 27#include "locations.h" 28#include "mirror/class.h" 29#include "offsets.h" 30#include "primitive.h" 31#include "utils/arena_bit_vector.h" 32#include "utils/growable_array.h" 33 34namespace art { 35 36class GraphChecker; 37class HBasicBlock; 38class HCurrentMethod; 39class HDoubleConstant; 40class HEnvironment; 41class HFloatConstant; 42class HGraphVisitor; 43class HInstruction; 44class HIntConstant; 45class HInvoke; 46class HLongConstant; 47class HNullConstant; 48class HPhi; 49class HSuspendCheck; 50class LiveInterval; 51class LocationSummary; 52class SlowPathCode; 53class SsaBuilder; 54 55static const int kDefaultNumberOfBlocks = 8; 56static const int kDefaultNumberOfSuccessors = 2; 57static const int kDefaultNumberOfPredecessors = 2; 58static const int kDefaultNumberOfDominatedBlocks = 1; 59static const int kDefaultNumberOfBackEdges = 1; 60 61static constexpr uint32_t kMaxIntShiftValue = 0x1f; 62static constexpr uint64_t kMaxLongShiftValue = 0x3f; 63 64static constexpr uint32_t kUnknownFieldIndex = static_cast<uint32_t>(-1); 65 66static constexpr InvokeType kInvalidInvokeType = static_cast<InvokeType>(-1); 67 68enum IfCondition { 69 kCondEQ, 70 kCondNE, 71 kCondLT, 72 kCondLE, 73 kCondGT, 74 kCondGE, 75}; 76 77class HInstructionList { 78 public: 79 HInstructionList() : first_instruction_(nullptr), last_instruction_(nullptr) {} 80 81 void AddInstruction(HInstruction* instruction); 82 void RemoveInstruction(HInstruction* instruction); 83 84 // Insert `instruction` before/after an existing instruction `cursor`. 85 void InsertInstructionBefore(HInstruction* instruction, HInstruction* cursor); 86 void InsertInstructionAfter(HInstruction* instruction, HInstruction* cursor); 87 88 // Return true if this list contains `instruction`. 89 bool Contains(HInstruction* instruction) const; 90 91 // Return true if `instruction1` is found before `instruction2` in 92 // this instruction list and false otherwise. Abort if none 93 // of these instructions is found. 94 bool FoundBefore(const HInstruction* instruction1, 95 const HInstruction* instruction2) const; 96 97 bool IsEmpty() const { return first_instruction_ == nullptr; } 98 void Clear() { first_instruction_ = last_instruction_ = nullptr; } 99 100 // Update the block of all instructions to be `block`. 101 void SetBlockOfInstructions(HBasicBlock* block) const; 102 103 void AddAfter(HInstruction* cursor, const HInstructionList& instruction_list); 104 void Add(const HInstructionList& instruction_list); 105 106 // Return the number of instructions in the list. This is an expensive operation. 107 size_t CountSize() const; 108 109 private: 110 HInstruction* first_instruction_; 111 HInstruction* last_instruction_; 112 113 friend class HBasicBlock; 114 friend class HGraph; 115 friend class HInstruction; 116 friend class HInstructionIterator; 117 friend class HBackwardInstructionIterator; 118 119 DISALLOW_COPY_AND_ASSIGN(HInstructionList); 120}; 121 122// Control-flow graph of a method. Contains a list of basic blocks. 123class HGraph : public ArenaObject<kArenaAllocMisc> { 124 public: 125 HGraph(ArenaAllocator* arena, 126 const DexFile& dex_file, 127 uint32_t method_idx, 128 bool should_generate_constructor_barrier, 129 InstructionSet instruction_set, 130 InvokeType invoke_type = kInvalidInvokeType, 131 bool debuggable = false, 132 int start_instruction_id = 0) 133 : arena_(arena), 134 blocks_(arena, kDefaultNumberOfBlocks), 135 reverse_post_order_(arena, kDefaultNumberOfBlocks), 136 linear_order_(arena, kDefaultNumberOfBlocks), 137 entry_block_(nullptr), 138 exit_block_(nullptr), 139 maximum_number_of_out_vregs_(0), 140 number_of_vregs_(0), 141 number_of_in_vregs_(0), 142 temporaries_vreg_slots_(0), 143 has_bounds_checks_(false), 144 debuggable_(debuggable), 145 current_instruction_id_(start_instruction_id), 146 dex_file_(dex_file), 147 method_idx_(method_idx), 148 invoke_type_(invoke_type), 149 in_ssa_form_(false), 150 should_generate_constructor_barrier_(should_generate_constructor_barrier), 151 instruction_set_(instruction_set), 152 cached_null_constant_(nullptr), 153 cached_int_constants_(std::less<int32_t>(), arena->Adapter()), 154 cached_float_constants_(std::less<int32_t>(), arena->Adapter()), 155 cached_long_constants_(std::less<int64_t>(), arena->Adapter()), 156 cached_double_constants_(std::less<int64_t>(), arena->Adapter()), 157 cached_current_method_(nullptr) {} 158 159 ArenaAllocator* GetArena() const { return arena_; } 160 const GrowableArray<HBasicBlock*>& GetBlocks() const { return blocks_; } 161 HBasicBlock* GetBlock(size_t id) const { return blocks_.Get(id); } 162 163 HBasicBlock* GetEntryBlock() const { return entry_block_; } 164 HBasicBlock* GetExitBlock() const { return exit_block_; } 165 bool HasExitBlock() const { return exit_block_ != nullptr; } 166 167 void SetEntryBlock(HBasicBlock* block) { entry_block_ = block; } 168 void SetExitBlock(HBasicBlock* block) { exit_block_ = block; } 169 170 void AddBlock(HBasicBlock* block); 171 172 // Try building the SSA form of this graph, with dominance computation and loop 173 // recognition. Returns whether it was successful in doing all these steps. 174 bool TryBuildingSsa() { 175 BuildDominatorTree(); 176 // The SSA builder requires loops to all be natural. Specifically, the dead phi 177 // elimination phase checks the consistency of the graph when doing a post-order 178 // visit for eliminating dead phis: a dead phi can only have loop header phi 179 // users remaining when being visited. 180 if (!AnalyzeNaturalLoops()) return false; 181 TransformToSsa(); 182 in_ssa_form_ = true; 183 return true; 184 } 185 186 void BuildDominatorTree(); 187 void TransformToSsa(); 188 void SimplifyCFG(); 189 190 // Analyze all natural loops in this graph. Returns false if one 191 // loop is not natural, that is the header does not dominate the 192 // back edge. 193 bool AnalyzeNaturalLoops() const; 194 195 // Inline this graph in `outer_graph`, replacing the given `invoke` instruction. 196 void InlineInto(HGraph* outer_graph, HInvoke* invoke); 197 198 // Removes `block` from the graph. 199 void DeleteDeadBlock(HBasicBlock* block); 200 201 void SplitCriticalEdge(HBasicBlock* block, HBasicBlock* successor); 202 void SimplifyLoop(HBasicBlock* header); 203 204 int32_t GetNextInstructionId() { 205 DCHECK_NE(current_instruction_id_, INT32_MAX); 206 return current_instruction_id_++; 207 } 208 209 int32_t GetCurrentInstructionId() const { 210 return current_instruction_id_; 211 } 212 213 void SetCurrentInstructionId(int32_t id) { 214 current_instruction_id_ = id; 215 } 216 217 uint16_t GetMaximumNumberOfOutVRegs() const { 218 return maximum_number_of_out_vregs_; 219 } 220 221 void SetMaximumNumberOfOutVRegs(uint16_t new_value) { 222 maximum_number_of_out_vregs_ = new_value; 223 } 224 225 void UpdateMaximumNumberOfOutVRegs(uint16_t other_value) { 226 maximum_number_of_out_vregs_ = std::max(maximum_number_of_out_vregs_, other_value); 227 } 228 229 void UpdateTemporariesVRegSlots(size_t slots) { 230 temporaries_vreg_slots_ = std::max(slots, temporaries_vreg_slots_); 231 } 232 233 size_t GetTemporariesVRegSlots() const { 234 DCHECK(!in_ssa_form_); 235 return temporaries_vreg_slots_; 236 } 237 238 void SetNumberOfVRegs(uint16_t number_of_vregs) { 239 number_of_vregs_ = number_of_vregs; 240 } 241 242 uint16_t GetNumberOfVRegs() const { 243 DCHECK(!in_ssa_form_); 244 return number_of_vregs_; 245 } 246 247 void SetNumberOfInVRegs(uint16_t value) { 248 number_of_in_vregs_ = value; 249 } 250 251 uint16_t GetNumberOfLocalVRegs() const { 252 DCHECK(!in_ssa_form_); 253 return number_of_vregs_ - number_of_in_vregs_; 254 } 255 256 const GrowableArray<HBasicBlock*>& GetReversePostOrder() const { 257 return reverse_post_order_; 258 } 259 260 const GrowableArray<HBasicBlock*>& GetLinearOrder() const { 261 return linear_order_; 262 } 263 264 bool HasBoundsChecks() const { 265 return has_bounds_checks_; 266 } 267 268 void SetHasBoundsChecks(bool value) { 269 has_bounds_checks_ = value; 270 } 271 272 bool ShouldGenerateConstructorBarrier() const { 273 return should_generate_constructor_barrier_; 274 } 275 276 bool IsDebuggable() const { return debuggable_; } 277 278 // Returns a constant of the given type and value. If it does not exist 279 // already, it is created and inserted into the graph. This method is only for 280 // integral types. 281 HConstant* GetConstant(Primitive::Type type, int64_t value); 282 HNullConstant* GetNullConstant(); 283 HIntConstant* GetIntConstant(int32_t value) { 284 return CreateConstant(value, &cached_int_constants_); 285 } 286 HLongConstant* GetLongConstant(int64_t value) { 287 return CreateConstant(value, &cached_long_constants_); 288 } 289 HFloatConstant* GetFloatConstant(float value) { 290 return CreateConstant(bit_cast<int32_t, float>(value), &cached_float_constants_); 291 } 292 HDoubleConstant* GetDoubleConstant(double value) { 293 return CreateConstant(bit_cast<int64_t, double>(value), &cached_double_constants_); 294 } 295 296 HCurrentMethod* GetCurrentMethod(); 297 298 HBasicBlock* FindCommonDominator(HBasicBlock* first, HBasicBlock* second) const; 299 300 const DexFile& GetDexFile() const { 301 return dex_file_; 302 } 303 304 uint32_t GetMethodIdx() const { 305 return method_idx_; 306 } 307 308 InvokeType GetInvokeType() const { 309 return invoke_type_; 310 } 311 312 private: 313 void VisitBlockForDominatorTree(HBasicBlock* block, 314 HBasicBlock* predecessor, 315 GrowableArray<size_t>* visits); 316 void FindBackEdges(ArenaBitVector* visited); 317 void VisitBlockForBackEdges(HBasicBlock* block, 318 ArenaBitVector* visited, 319 ArenaBitVector* visiting); 320 void RemoveInstructionsAsUsersFromDeadBlocks(const ArenaBitVector& visited) const; 321 void RemoveDeadBlocks(const ArenaBitVector& visited); 322 323 template <class InstructionType, typename ValueType> 324 InstructionType* CreateConstant(ValueType value, 325 ArenaSafeMap<ValueType, InstructionType*>* cache) { 326 // Try to find an existing constant of the given value. 327 InstructionType* constant = nullptr; 328 auto cached_constant = cache->find(value); 329 if (cached_constant != cache->end()) { 330 constant = cached_constant->second; 331 } 332 333 // If not found or previously deleted, create and cache a new instruction. 334 if (constant == nullptr || constant->GetBlock() == nullptr) { 335 constant = new (arena_) InstructionType(value); 336 cache->Overwrite(value, constant); 337 InsertConstant(constant); 338 } 339 return constant; 340 } 341 342 void InsertConstant(HConstant* instruction); 343 344 // Cache a float constant into the graph. This method should only be 345 // called by the SsaBuilder when creating "equivalent" instructions. 346 void CacheFloatConstant(HFloatConstant* constant); 347 348 // See CacheFloatConstant comment. 349 void CacheDoubleConstant(HDoubleConstant* constant); 350 351 ArenaAllocator* const arena_; 352 353 // List of blocks in insertion order. 354 GrowableArray<HBasicBlock*> blocks_; 355 356 // List of blocks to perform a reverse post order tree traversal. 357 GrowableArray<HBasicBlock*> reverse_post_order_; 358 359 // List of blocks to perform a linear order tree traversal. 360 GrowableArray<HBasicBlock*> linear_order_; 361 362 HBasicBlock* entry_block_; 363 HBasicBlock* exit_block_; 364 365 // The maximum number of virtual registers arguments passed to a HInvoke in this graph. 366 uint16_t maximum_number_of_out_vregs_; 367 368 // The number of virtual registers in this method. Contains the parameters. 369 uint16_t number_of_vregs_; 370 371 // The number of virtual registers used by parameters of this method. 372 uint16_t number_of_in_vregs_; 373 374 // Number of vreg size slots that the temporaries use (used in baseline compiler). 375 size_t temporaries_vreg_slots_; 376 377 // Has bounds checks. We can totally skip BCE if it's false. 378 bool has_bounds_checks_; 379 380 // Indicates whether the graph should be compiled in a way that 381 // ensures full debuggability. If false, we can apply more 382 // aggressive optimizations that may limit the level of debugging. 383 const bool debuggable_; 384 385 // The current id to assign to a newly added instruction. See HInstruction.id_. 386 int32_t current_instruction_id_; 387 388 // The dex file from which the method is from. 389 const DexFile& dex_file_; 390 391 // The method index in the dex file. 392 const uint32_t method_idx_; 393 394 // If inlined, this encodes how the callee is being invoked. 395 const InvokeType invoke_type_; 396 397 // Whether the graph has been transformed to SSA form. Only used 398 // in debug mode to ensure we are not using properties only valid 399 // for non-SSA form (like the number of temporaries). 400 bool in_ssa_form_; 401 402 const bool should_generate_constructor_barrier_; 403 404 const InstructionSet instruction_set_; 405 406 // Cached constants. 407 HNullConstant* cached_null_constant_; 408 ArenaSafeMap<int32_t, HIntConstant*> cached_int_constants_; 409 ArenaSafeMap<int32_t, HFloatConstant*> cached_float_constants_; 410 ArenaSafeMap<int64_t, HLongConstant*> cached_long_constants_; 411 ArenaSafeMap<int64_t, HDoubleConstant*> cached_double_constants_; 412 413 HCurrentMethod* cached_current_method_; 414 415 friend class SsaBuilder; // For caching constants. 416 friend class SsaLivenessAnalysis; // For the linear order. 417 ART_FRIEND_TEST(GraphTest, IfSuccessorSimpleJoinBlock1); 418 DISALLOW_COPY_AND_ASSIGN(HGraph); 419}; 420 421class HLoopInformation : public ArenaObject<kArenaAllocMisc> { 422 public: 423 HLoopInformation(HBasicBlock* header, HGraph* graph) 424 : header_(header), 425 suspend_check_(nullptr), 426 back_edges_(graph->GetArena(), kDefaultNumberOfBackEdges), 427 // Make bit vector growable, as the number of blocks may change. 428 blocks_(graph->GetArena(), graph->GetBlocks().Size(), true) {} 429 430 HBasicBlock* GetHeader() const { 431 return header_; 432 } 433 434 void SetHeader(HBasicBlock* block) { 435 header_ = block; 436 } 437 438 HSuspendCheck* GetSuspendCheck() const { return suspend_check_; } 439 void SetSuspendCheck(HSuspendCheck* check) { suspend_check_ = check; } 440 bool HasSuspendCheck() const { return suspend_check_ != nullptr; } 441 442 void AddBackEdge(HBasicBlock* back_edge) { 443 back_edges_.Add(back_edge); 444 } 445 446 void RemoveBackEdge(HBasicBlock* back_edge) { 447 back_edges_.Delete(back_edge); 448 } 449 450 bool IsBackEdge(const HBasicBlock& block) const { 451 for (size_t i = 0, e = back_edges_.Size(); i < e; ++i) { 452 if (back_edges_.Get(i) == &block) return true; 453 } 454 return false; 455 } 456 457 size_t NumberOfBackEdges() const { 458 return back_edges_.Size(); 459 } 460 461 HBasicBlock* GetPreHeader() const; 462 463 const GrowableArray<HBasicBlock*>& GetBackEdges() const { 464 return back_edges_; 465 } 466 467 // Returns the lifetime position of the back edge that has the 468 // greatest lifetime position. 469 size_t GetLifetimeEnd() const; 470 471 void ReplaceBackEdge(HBasicBlock* existing, HBasicBlock* new_back_edge) { 472 for (size_t i = 0, e = back_edges_.Size(); i < e; ++i) { 473 if (back_edges_.Get(i) == existing) { 474 back_edges_.Put(i, new_back_edge); 475 return; 476 } 477 } 478 UNREACHABLE(); 479 } 480 481 // Finds blocks that are part of this loop. Returns whether the loop is a natural loop, 482 // that is the header dominates the back edge. 483 bool Populate(); 484 485 // Reanalyzes the loop by removing loop info from its blocks and re-running 486 // Populate(). If there are no back edges left, the loop info is completely 487 // removed as well as its SuspendCheck instruction. It must be run on nested 488 // inner loops first. 489 void Update(); 490 491 // Returns whether this loop information contains `block`. 492 // Note that this loop information *must* be populated before entering this function. 493 bool Contains(const HBasicBlock& block) const; 494 495 // Returns whether this loop information is an inner loop of `other`. 496 // Note that `other` *must* be populated before entering this function. 497 bool IsIn(const HLoopInformation& other) const; 498 499 const ArenaBitVector& GetBlocks() const { return blocks_; } 500 501 void Add(HBasicBlock* block); 502 void Remove(HBasicBlock* block); 503 504 private: 505 // Internal recursive implementation of `Populate`. 506 void PopulateRecursive(HBasicBlock* block); 507 508 HBasicBlock* header_; 509 HSuspendCheck* suspend_check_; 510 GrowableArray<HBasicBlock*> back_edges_; 511 ArenaBitVector blocks_; 512 513 DISALLOW_COPY_AND_ASSIGN(HLoopInformation); 514}; 515 516static constexpr size_t kNoLifetime = -1; 517static constexpr uint32_t kNoDexPc = -1; 518 519// A block in a method. Contains the list of instructions represented 520// as a double linked list. Each block knows its predecessors and 521// successors. 522 523class HBasicBlock : public ArenaObject<kArenaAllocMisc> { 524 public: 525 explicit HBasicBlock(HGraph* graph, uint32_t dex_pc = kNoDexPc) 526 : graph_(graph), 527 predecessors_(graph->GetArena(), kDefaultNumberOfPredecessors), 528 successors_(graph->GetArena(), kDefaultNumberOfSuccessors), 529 loop_information_(nullptr), 530 dominator_(nullptr), 531 dominated_blocks_(graph->GetArena(), kDefaultNumberOfDominatedBlocks), 532 block_id_(-1), 533 dex_pc_(dex_pc), 534 lifetime_start_(kNoLifetime), 535 lifetime_end_(kNoLifetime), 536 is_catch_block_(false) {} 537 538 const GrowableArray<HBasicBlock*>& GetPredecessors() const { 539 return predecessors_; 540 } 541 542 const GrowableArray<HBasicBlock*>& GetSuccessors() const { 543 return successors_; 544 } 545 546 const GrowableArray<HBasicBlock*>& GetDominatedBlocks() const { 547 return dominated_blocks_; 548 } 549 550 bool IsEntryBlock() const { 551 return graph_->GetEntryBlock() == this; 552 } 553 554 bool IsExitBlock() const { 555 return graph_->GetExitBlock() == this; 556 } 557 558 bool IsSingleGoto() const; 559 560 void AddBackEdge(HBasicBlock* back_edge) { 561 if (loop_information_ == nullptr) { 562 loop_information_ = new (graph_->GetArena()) HLoopInformation(this, graph_); 563 } 564 DCHECK_EQ(loop_information_->GetHeader(), this); 565 loop_information_->AddBackEdge(back_edge); 566 } 567 568 HGraph* GetGraph() const { return graph_; } 569 void SetGraph(HGraph* graph) { graph_ = graph; } 570 571 int GetBlockId() const { return block_id_; } 572 void SetBlockId(int id) { block_id_ = id; } 573 574 HBasicBlock* GetDominator() const { return dominator_; } 575 void SetDominator(HBasicBlock* dominator) { dominator_ = dominator; } 576 void AddDominatedBlock(HBasicBlock* block) { dominated_blocks_.Add(block); } 577 void RemoveDominatedBlock(HBasicBlock* block) { dominated_blocks_.Delete(block); } 578 void ReplaceDominatedBlock(HBasicBlock* existing, HBasicBlock* new_block) { 579 for (size_t i = 0, e = dominated_blocks_.Size(); i < e; ++i) { 580 if (dominated_blocks_.Get(i) == existing) { 581 dominated_blocks_.Put(i, new_block); 582 return; 583 } 584 } 585 LOG(FATAL) << "Unreachable"; 586 UNREACHABLE(); 587 } 588 589 int NumberOfBackEdges() const { 590 return loop_information_ == nullptr 591 ? 0 592 : loop_information_->NumberOfBackEdges(); 593 } 594 595 HInstruction* GetFirstInstruction() const { return instructions_.first_instruction_; } 596 HInstruction* GetLastInstruction() const { return instructions_.last_instruction_; } 597 const HInstructionList& GetInstructions() const { return instructions_; } 598 HInstruction* GetFirstPhi() const { return phis_.first_instruction_; } 599 HInstruction* GetLastPhi() const { return phis_.last_instruction_; } 600 const HInstructionList& GetPhis() const { return phis_; } 601 602 void AddSuccessor(HBasicBlock* block) { 603 successors_.Add(block); 604 block->predecessors_.Add(this); 605 } 606 607 void ReplaceSuccessor(HBasicBlock* existing, HBasicBlock* new_block) { 608 size_t successor_index = GetSuccessorIndexOf(existing); 609 DCHECK_NE(successor_index, static_cast<size_t>(-1)); 610 existing->RemovePredecessor(this); 611 new_block->predecessors_.Add(this); 612 successors_.Put(successor_index, new_block); 613 } 614 615 void ReplacePredecessor(HBasicBlock* existing, HBasicBlock* new_block) { 616 size_t predecessor_index = GetPredecessorIndexOf(existing); 617 DCHECK_NE(predecessor_index, static_cast<size_t>(-1)); 618 existing->RemoveSuccessor(this); 619 new_block->successors_.Add(this); 620 predecessors_.Put(predecessor_index, new_block); 621 } 622 623 void RemovePredecessor(HBasicBlock* block) { 624 predecessors_.Delete(block); 625 } 626 627 void RemoveSuccessor(HBasicBlock* block) { 628 successors_.Delete(block); 629 } 630 631 void ClearAllPredecessors() { 632 predecessors_.Reset(); 633 } 634 635 void AddPredecessor(HBasicBlock* block) { 636 predecessors_.Add(block); 637 block->successors_.Add(this); 638 } 639 640 void SwapPredecessors() { 641 DCHECK_EQ(predecessors_.Size(), 2u); 642 HBasicBlock* temp = predecessors_.Get(0); 643 predecessors_.Put(0, predecessors_.Get(1)); 644 predecessors_.Put(1, temp); 645 } 646 647 void SwapSuccessors() { 648 DCHECK_EQ(successors_.Size(), 2u); 649 HBasicBlock* temp = successors_.Get(0); 650 successors_.Put(0, successors_.Get(1)); 651 successors_.Put(1, temp); 652 } 653 654 size_t GetPredecessorIndexOf(HBasicBlock* predecessor) { 655 for (size_t i = 0, e = predecessors_.Size(); i < e; ++i) { 656 if (predecessors_.Get(i) == predecessor) { 657 return i; 658 } 659 } 660 return -1; 661 } 662 663 size_t GetSuccessorIndexOf(HBasicBlock* successor) { 664 for (size_t i = 0, e = successors_.Size(); i < e; ++i) { 665 if (successors_.Get(i) == successor) { 666 return i; 667 } 668 } 669 return -1; 670 } 671 672 // Split the block into two blocks just after `cursor`. Returns the newly 673 // created block. Note that this method just updates raw block information, 674 // like predecessors, successors, dominators, and instruction list. It does not 675 // update the graph, reverse post order, loop information, nor make sure the 676 // blocks are consistent (for example ending with a control flow instruction). 677 HBasicBlock* SplitAfter(HInstruction* cursor); 678 679 // Merge `other` at the end of `this`. Successors and dominated blocks of 680 // `other` are changed to be successors and dominated blocks of `this`. Note 681 // that this method does not update the graph, reverse post order, loop 682 // information, nor make sure the blocks are consistent (for example ending 683 // with a control flow instruction). 684 void MergeWithInlined(HBasicBlock* other); 685 686 // Replace `this` with `other`. Predecessors, successors, and dominated blocks 687 // of `this` are moved to `other`. 688 // Note that this method does not update the graph, reverse post order, loop 689 // information, nor make sure the blocks are consistent (for example ending 690 // with a control flow instruction). 691 void ReplaceWith(HBasicBlock* other); 692 693 // Merge `other` at the end of `this`. This method updates loops, reverse post 694 // order, links to predecessors, successors, dominators and deletes the block 695 // from the graph. The two blocks must be successive, i.e. `this` the only 696 // predecessor of `other` and vice versa. 697 void MergeWith(HBasicBlock* other); 698 699 // Disconnects `this` from all its predecessors, successors and dominator, 700 // removes it from all loops it is included in and eventually from the graph. 701 // The block must not dominate any other block. Predecessors and successors 702 // are safely updated. 703 void DisconnectAndDelete(); 704 705 void AddInstruction(HInstruction* instruction); 706 // Insert `instruction` before/after an existing instruction `cursor`. 707 void InsertInstructionBefore(HInstruction* instruction, HInstruction* cursor); 708 void InsertInstructionAfter(HInstruction* instruction, HInstruction* cursor); 709 // Replace instruction `initial` with `replacement` within this block. 710 void ReplaceAndRemoveInstructionWith(HInstruction* initial, 711 HInstruction* replacement); 712 void AddPhi(HPhi* phi); 713 void InsertPhiAfter(HPhi* instruction, HPhi* cursor); 714 // RemoveInstruction and RemovePhi delete a given instruction from the respective 715 // instruction list. With 'ensure_safety' set to true, it verifies that the 716 // instruction is not in use and removes it from the use lists of its inputs. 717 void RemoveInstruction(HInstruction* instruction, bool ensure_safety = true); 718 void RemovePhi(HPhi* phi, bool ensure_safety = true); 719 void RemoveInstructionOrPhi(HInstruction* instruction, bool ensure_safety = true); 720 721 bool IsLoopHeader() const { 722 return IsInLoop() && (loop_information_->GetHeader() == this); 723 } 724 725 bool IsLoopPreHeaderFirstPredecessor() const { 726 DCHECK(IsLoopHeader()); 727 DCHECK(!GetPredecessors().IsEmpty()); 728 return GetPredecessors().Get(0) == GetLoopInformation()->GetPreHeader(); 729 } 730 731 HLoopInformation* GetLoopInformation() const { 732 return loop_information_; 733 } 734 735 // Set the loop_information_ on this block. Overrides the current 736 // loop_information if it is an outer loop of the passed loop information. 737 // Note that this method is called while creating the loop information. 738 void SetInLoop(HLoopInformation* info) { 739 if (IsLoopHeader()) { 740 // Nothing to do. This just means `info` is an outer loop. 741 } else if (!IsInLoop()) { 742 loop_information_ = info; 743 } else if (loop_information_->Contains(*info->GetHeader())) { 744 // Block is currently part of an outer loop. Make it part of this inner loop. 745 // Note that a non loop header having a loop information means this loop information 746 // has already been populated 747 loop_information_ = info; 748 } else { 749 // Block is part of an inner loop. Do not update the loop information. 750 // Note that we cannot do the check `info->Contains(loop_information_)->GetHeader()` 751 // at this point, because this method is being called while populating `info`. 752 } 753 } 754 755 // Raw update of the loop information. 756 void SetLoopInformation(HLoopInformation* info) { 757 loop_information_ = info; 758 } 759 760 bool IsInLoop() const { return loop_information_ != nullptr; } 761 762 // Returns whether this block dominates the blocked passed as parameter. 763 bool Dominates(HBasicBlock* block) const; 764 765 size_t GetLifetimeStart() const { return lifetime_start_; } 766 size_t GetLifetimeEnd() const { return lifetime_end_; } 767 768 void SetLifetimeStart(size_t start) { lifetime_start_ = start; } 769 void SetLifetimeEnd(size_t end) { lifetime_end_ = end; } 770 771 uint32_t GetDexPc() const { return dex_pc_; } 772 773 bool IsCatchBlock() const { return is_catch_block_; } 774 void SetIsCatchBlock() { is_catch_block_ = true; } 775 776 bool EndsWithControlFlowInstruction() const; 777 bool EndsWithIf() const; 778 bool HasSinglePhi() const; 779 780 private: 781 HGraph* graph_; 782 GrowableArray<HBasicBlock*> predecessors_; 783 GrowableArray<HBasicBlock*> successors_; 784 HInstructionList instructions_; 785 HInstructionList phis_; 786 HLoopInformation* loop_information_; 787 HBasicBlock* dominator_; 788 GrowableArray<HBasicBlock*> dominated_blocks_; 789 int block_id_; 790 // The dex program counter of the first instruction of this block. 791 const uint32_t dex_pc_; 792 size_t lifetime_start_; 793 size_t lifetime_end_; 794 bool is_catch_block_; 795 796 friend class HGraph; 797 friend class HInstruction; 798 799 DISALLOW_COPY_AND_ASSIGN(HBasicBlock); 800}; 801 802// Iterates over the LoopInformation of all loops which contain 'block' 803// from the innermost to the outermost. 804class HLoopInformationOutwardIterator : public ValueObject { 805 public: 806 explicit HLoopInformationOutwardIterator(const HBasicBlock& block) 807 : current_(block.GetLoopInformation()) {} 808 809 bool Done() const { return current_ == nullptr; } 810 811 void Advance() { 812 DCHECK(!Done()); 813 current_ = current_->GetPreHeader()->GetLoopInformation(); 814 } 815 816 HLoopInformation* Current() const { 817 DCHECK(!Done()); 818 return current_; 819 } 820 821 private: 822 HLoopInformation* current_; 823 824 DISALLOW_COPY_AND_ASSIGN(HLoopInformationOutwardIterator); 825}; 826 827#define FOR_EACH_CONCRETE_INSTRUCTION(M) \ 828 M(Add, BinaryOperation) \ 829 M(And, BinaryOperation) \ 830 M(ArrayGet, Instruction) \ 831 M(ArrayLength, Instruction) \ 832 M(ArraySet, Instruction) \ 833 M(BooleanNot, UnaryOperation) \ 834 M(BoundsCheck, Instruction) \ 835 M(BoundType, Instruction) \ 836 M(CheckCast, Instruction) \ 837 M(ClinitCheck, Instruction) \ 838 M(Compare, BinaryOperation) \ 839 M(Condition, BinaryOperation) \ 840 M(CurrentMethod, Instruction) \ 841 M(Deoptimize, Instruction) \ 842 M(Div, BinaryOperation) \ 843 M(DivZeroCheck, Instruction) \ 844 M(DoubleConstant, Constant) \ 845 M(Equal, Condition) \ 846 M(Exit, Instruction) \ 847 M(FloatConstant, Constant) \ 848 M(Goto, Instruction) \ 849 M(GreaterThan, Condition) \ 850 M(GreaterThanOrEqual, Condition) \ 851 M(If, Instruction) \ 852 M(InstanceFieldGet, Instruction) \ 853 M(InstanceFieldSet, Instruction) \ 854 M(InstanceOf, Instruction) \ 855 M(IntConstant, Constant) \ 856 M(InvokeInterface, Invoke) \ 857 M(InvokeStaticOrDirect, Invoke) \ 858 M(InvokeVirtual, Invoke) \ 859 M(LessThan, Condition) \ 860 M(LessThanOrEqual, Condition) \ 861 M(LoadClass, Instruction) \ 862 M(LoadException, Instruction) \ 863 M(LoadLocal, Instruction) \ 864 M(LoadString, Instruction) \ 865 M(Local, Instruction) \ 866 M(LongConstant, Constant) \ 867 M(MemoryBarrier, Instruction) \ 868 M(MonitorOperation, Instruction) \ 869 M(Mul, BinaryOperation) \ 870 M(Neg, UnaryOperation) \ 871 M(NewArray, Instruction) \ 872 M(NewInstance, Instruction) \ 873 M(Not, UnaryOperation) \ 874 M(NotEqual, Condition) \ 875 M(NullConstant, Instruction) \ 876 M(NullCheck, Instruction) \ 877 M(Or, BinaryOperation) \ 878 M(ParallelMove, Instruction) \ 879 M(ParameterValue, Instruction) \ 880 M(Phi, Instruction) \ 881 M(Rem, BinaryOperation) \ 882 M(Return, Instruction) \ 883 M(ReturnVoid, Instruction) \ 884 M(Shl, BinaryOperation) \ 885 M(Shr, BinaryOperation) \ 886 M(StaticFieldGet, Instruction) \ 887 M(StaticFieldSet, Instruction) \ 888 M(StoreLocal, Instruction) \ 889 M(Sub, BinaryOperation) \ 890 M(SuspendCheck, Instruction) \ 891 M(Temporary, Instruction) \ 892 M(Throw, Instruction) \ 893 M(TypeConversion, Instruction) \ 894 M(UShr, BinaryOperation) \ 895 M(Xor, BinaryOperation) \ 896 897#define FOR_EACH_INSTRUCTION(M) \ 898 FOR_EACH_CONCRETE_INSTRUCTION(M) \ 899 M(Constant, Instruction) \ 900 M(UnaryOperation, Instruction) \ 901 M(BinaryOperation, Instruction) \ 902 M(Invoke, Instruction) 903 904#define FORWARD_DECLARATION(type, super) class H##type; 905FOR_EACH_INSTRUCTION(FORWARD_DECLARATION) 906#undef FORWARD_DECLARATION 907 908#define DECLARE_INSTRUCTION(type) \ 909 InstructionKind GetKind() const OVERRIDE { return k##type; } \ 910 const char* DebugName() const OVERRIDE { return #type; } \ 911 const H##type* As##type() const OVERRIDE { return this; } \ 912 H##type* As##type() OVERRIDE { return this; } \ 913 bool InstructionTypeEquals(HInstruction* other) const OVERRIDE { \ 914 return other->Is##type(); \ 915 } \ 916 void Accept(HGraphVisitor* visitor) OVERRIDE 917 918template <typename T> class HUseList; 919 920template <typename T> 921class HUseListNode : public ArenaObject<kArenaAllocMisc> { 922 public: 923 HUseListNode* GetPrevious() const { return prev_; } 924 HUseListNode* GetNext() const { return next_; } 925 T GetUser() const { return user_; } 926 size_t GetIndex() const { return index_; } 927 void SetIndex(size_t index) { index_ = index; } 928 929 private: 930 HUseListNode(T user, size_t index) 931 : user_(user), index_(index), prev_(nullptr), next_(nullptr) {} 932 933 T const user_; 934 size_t index_; 935 HUseListNode<T>* prev_; 936 HUseListNode<T>* next_; 937 938 friend class HUseList<T>; 939 940 DISALLOW_COPY_AND_ASSIGN(HUseListNode); 941}; 942 943template <typename T> 944class HUseList : public ValueObject { 945 public: 946 HUseList() : first_(nullptr) {} 947 948 void Clear() { 949 first_ = nullptr; 950 } 951 952 // Adds a new entry at the beginning of the use list and returns 953 // the newly created node. 954 HUseListNode<T>* AddUse(T user, size_t index, ArenaAllocator* arena) { 955 HUseListNode<T>* new_node = new (arena) HUseListNode<T>(user, index); 956 if (IsEmpty()) { 957 first_ = new_node; 958 } else { 959 first_->prev_ = new_node; 960 new_node->next_ = first_; 961 first_ = new_node; 962 } 963 return new_node; 964 } 965 966 HUseListNode<T>* GetFirst() const { 967 return first_; 968 } 969 970 void Remove(HUseListNode<T>* node) { 971 DCHECK(node != nullptr); 972 DCHECK(Contains(node)); 973 974 if (node->prev_ != nullptr) { 975 node->prev_->next_ = node->next_; 976 } 977 if (node->next_ != nullptr) { 978 node->next_->prev_ = node->prev_; 979 } 980 if (node == first_) { 981 first_ = node->next_; 982 } 983 } 984 985 bool Contains(const HUseListNode<T>* node) const { 986 if (node == nullptr) { 987 return false; 988 } 989 for (HUseListNode<T>* current = first_; current != nullptr; current = current->GetNext()) { 990 if (current == node) { 991 return true; 992 } 993 } 994 return false; 995 } 996 997 bool IsEmpty() const { 998 return first_ == nullptr; 999 } 1000 1001 bool HasOnlyOneUse() const { 1002 return first_ != nullptr && first_->next_ == nullptr; 1003 } 1004 1005 size_t SizeSlow() const { 1006 size_t count = 0; 1007 for (HUseListNode<T>* current = first_; current != nullptr; current = current->GetNext()) { 1008 ++count; 1009 } 1010 return count; 1011 } 1012 1013 private: 1014 HUseListNode<T>* first_; 1015}; 1016 1017template<typename T> 1018class HUseIterator : public ValueObject { 1019 public: 1020 explicit HUseIterator(const HUseList<T>& uses) : current_(uses.GetFirst()) {} 1021 1022 bool Done() const { return current_ == nullptr; } 1023 1024 void Advance() { 1025 DCHECK(!Done()); 1026 current_ = current_->GetNext(); 1027 } 1028 1029 HUseListNode<T>* Current() const { 1030 DCHECK(!Done()); 1031 return current_; 1032 } 1033 1034 private: 1035 HUseListNode<T>* current_; 1036 1037 friend class HValue; 1038}; 1039 1040// This class is used by HEnvironment and HInstruction classes to record the 1041// instructions they use and pointers to the corresponding HUseListNodes kept 1042// by the used instructions. 1043template <typename T> 1044class HUserRecord : public ValueObject { 1045 public: 1046 HUserRecord() : instruction_(nullptr), use_node_(nullptr) {} 1047 explicit HUserRecord(HInstruction* instruction) : instruction_(instruction), use_node_(nullptr) {} 1048 1049 HUserRecord(const HUserRecord<T>& old_record, HUseListNode<T>* use_node) 1050 : instruction_(old_record.instruction_), use_node_(use_node) { 1051 DCHECK(instruction_ != nullptr); 1052 DCHECK(use_node_ != nullptr); 1053 DCHECK(old_record.use_node_ == nullptr); 1054 } 1055 1056 HInstruction* GetInstruction() const { return instruction_; } 1057 HUseListNode<T>* GetUseNode() const { return use_node_; } 1058 1059 private: 1060 // Instruction used by the user. 1061 HInstruction* instruction_; 1062 1063 // Corresponding entry in the use list kept by 'instruction_'. 1064 HUseListNode<T>* use_node_; 1065}; 1066 1067// TODO: Add better documentation to this class and maybe refactor with more suggestive names. 1068// - Has(All)SideEffects suggests that all the side effects are present but only ChangesSomething 1069// flag is consider. 1070// - DependsOn suggests that there is a real dependency between side effects but it only 1071// checks DependendsOnSomething flag. 1072// 1073// Represents the side effects an instruction may have. 1074class SideEffects : public ValueObject { 1075 public: 1076 SideEffects() : flags_(0) {} 1077 1078 static SideEffects None() { 1079 return SideEffects(0); 1080 } 1081 1082 static SideEffects All() { 1083 return SideEffects(ChangesSomething().flags_ | DependsOnSomething().flags_); 1084 } 1085 1086 static SideEffects ChangesSomething() { 1087 return SideEffects((1 << kFlagChangesCount) - 1); 1088 } 1089 1090 static SideEffects DependsOnSomething() { 1091 int count = kFlagDependsOnCount - kFlagChangesCount; 1092 return SideEffects(((1 << count) - 1) << kFlagChangesCount); 1093 } 1094 1095 SideEffects Union(SideEffects other) const { 1096 return SideEffects(flags_ | other.flags_); 1097 } 1098 1099 bool HasSideEffects() const { 1100 size_t all_bits_set = (1 << kFlagChangesCount) - 1; 1101 return (flags_ & all_bits_set) != 0; 1102 } 1103 1104 bool HasAllSideEffects() const { 1105 size_t all_bits_set = (1 << kFlagChangesCount) - 1; 1106 return all_bits_set == (flags_ & all_bits_set); 1107 } 1108 1109 bool DependsOn(SideEffects other) const { 1110 size_t depends_flags = other.ComputeDependsFlags(); 1111 return (flags_ & depends_flags) != 0; 1112 } 1113 1114 bool HasDependencies() const { 1115 int count = kFlagDependsOnCount - kFlagChangesCount; 1116 size_t all_bits_set = (1 << count) - 1; 1117 return ((flags_ >> kFlagChangesCount) & all_bits_set) != 0; 1118 } 1119 1120 private: 1121 static constexpr int kFlagChangesSomething = 0; 1122 static constexpr int kFlagChangesCount = kFlagChangesSomething + 1; 1123 1124 static constexpr int kFlagDependsOnSomething = kFlagChangesCount; 1125 static constexpr int kFlagDependsOnCount = kFlagDependsOnSomething + 1; 1126 1127 explicit SideEffects(size_t flags) : flags_(flags) {} 1128 1129 size_t ComputeDependsFlags() const { 1130 return flags_ << kFlagChangesCount; 1131 } 1132 1133 size_t flags_; 1134}; 1135 1136// A HEnvironment object contains the values of virtual registers at a given location. 1137class HEnvironment : public ArenaObject<kArenaAllocMisc> { 1138 public: 1139 HEnvironment(ArenaAllocator* arena, 1140 size_t number_of_vregs, 1141 const DexFile& dex_file, 1142 uint32_t method_idx, 1143 uint32_t dex_pc, 1144 InvokeType invoke_type, 1145 HInstruction* holder) 1146 : vregs_(arena, number_of_vregs), 1147 locations_(arena, number_of_vregs), 1148 parent_(nullptr), 1149 dex_file_(dex_file), 1150 method_idx_(method_idx), 1151 dex_pc_(dex_pc), 1152 invoke_type_(invoke_type), 1153 holder_(holder) { 1154 vregs_.SetSize(number_of_vregs); 1155 for (size_t i = 0; i < number_of_vregs; i++) { 1156 vregs_.Put(i, HUserRecord<HEnvironment*>()); 1157 } 1158 1159 locations_.SetSize(number_of_vregs); 1160 for (size_t i = 0; i < number_of_vregs; ++i) { 1161 locations_.Put(i, Location()); 1162 } 1163 } 1164 1165 HEnvironment(ArenaAllocator* arena, const HEnvironment& to_copy, HInstruction* holder) 1166 : HEnvironment(arena, 1167 to_copy.Size(), 1168 to_copy.GetDexFile(), 1169 to_copy.GetMethodIdx(), 1170 to_copy.GetDexPc(), 1171 to_copy.GetInvokeType(), 1172 holder) {} 1173 1174 void SetAndCopyParentChain(ArenaAllocator* allocator, HEnvironment* parent) { 1175 if (parent_ != nullptr) { 1176 parent_->SetAndCopyParentChain(allocator, parent); 1177 } else { 1178 parent_ = new (allocator) HEnvironment(allocator, *parent, holder_); 1179 parent_->CopyFrom(parent); 1180 if (parent->GetParent() != nullptr) { 1181 parent_->SetAndCopyParentChain(allocator, parent->GetParent()); 1182 } 1183 } 1184 } 1185 1186 void CopyFrom(const GrowableArray<HInstruction*>& locals); 1187 void CopyFrom(HEnvironment* environment); 1188 1189 // Copy from `env`. If it's a loop phi for `loop_header`, copy the first 1190 // input to the loop phi instead. This is for inserting instructions that 1191 // require an environment (like HDeoptimization) in the loop pre-header. 1192 void CopyFromWithLoopPhiAdjustment(HEnvironment* env, HBasicBlock* loop_header); 1193 1194 void SetRawEnvAt(size_t index, HInstruction* instruction) { 1195 vregs_.Put(index, HUserRecord<HEnvironment*>(instruction)); 1196 } 1197 1198 HInstruction* GetInstructionAt(size_t index) const { 1199 return vregs_.Get(index).GetInstruction(); 1200 } 1201 1202 void RemoveAsUserOfInput(size_t index) const; 1203 1204 size_t Size() const { return vregs_.Size(); } 1205 1206 HEnvironment* GetParent() const { return parent_; } 1207 1208 void SetLocationAt(size_t index, Location location) { 1209 locations_.Put(index, location); 1210 } 1211 1212 Location GetLocationAt(size_t index) const { 1213 return locations_.Get(index); 1214 } 1215 1216 uint32_t GetDexPc() const { 1217 return dex_pc_; 1218 } 1219 1220 uint32_t GetMethodIdx() const { 1221 return method_idx_; 1222 } 1223 1224 InvokeType GetInvokeType() const { 1225 return invoke_type_; 1226 } 1227 1228 const DexFile& GetDexFile() const { 1229 return dex_file_; 1230 } 1231 1232 HInstruction* GetHolder() const { 1233 return holder_; 1234 } 1235 1236 private: 1237 // Record instructions' use entries of this environment for constant-time removal. 1238 // It should only be called by HInstruction when a new environment use is added. 1239 void RecordEnvUse(HUseListNode<HEnvironment*>* env_use) { 1240 DCHECK(env_use->GetUser() == this); 1241 size_t index = env_use->GetIndex(); 1242 vregs_.Put(index, HUserRecord<HEnvironment*>(vregs_.Get(index), env_use)); 1243 } 1244 1245 GrowableArray<HUserRecord<HEnvironment*> > vregs_; 1246 GrowableArray<Location> locations_; 1247 HEnvironment* parent_; 1248 const DexFile& dex_file_; 1249 const uint32_t method_idx_; 1250 const uint32_t dex_pc_; 1251 const InvokeType invoke_type_; 1252 1253 // The instruction that holds this environment. Only used in debug mode 1254 // to ensure the graph is consistent. 1255 HInstruction* const holder_; 1256 1257 friend class HInstruction; 1258 1259 DISALLOW_COPY_AND_ASSIGN(HEnvironment); 1260}; 1261 1262class ReferenceTypeInfo : ValueObject { 1263 public: 1264 typedef Handle<mirror::Class> TypeHandle; 1265 1266 static ReferenceTypeInfo Create(TypeHandle type_handle, bool is_exact) 1267 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) { 1268 if (type_handle->IsObjectClass()) { 1269 // Override the type handle to be consistent with the case when we get to 1270 // Top but don't have the Object class available. It avoids having to guess 1271 // what value the type_handle has when it's Top. 1272 return ReferenceTypeInfo(TypeHandle(), is_exact, true); 1273 } else { 1274 return ReferenceTypeInfo(type_handle, is_exact, false); 1275 } 1276 } 1277 1278 static ReferenceTypeInfo CreateTop(bool is_exact) { 1279 return ReferenceTypeInfo(TypeHandle(), is_exact, true); 1280 } 1281 1282 bool IsExact() const { return is_exact_; } 1283 bool IsTop() const { return is_top_; } 1284 1285 Handle<mirror::Class> GetTypeHandle() const { return type_handle_; } 1286 1287 bool IsSupertypeOf(ReferenceTypeInfo rti) const SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) { 1288 if (IsTop()) { 1289 // Top (equivalent for java.lang.Object) is supertype of anything. 1290 return true; 1291 } 1292 if (rti.IsTop()) { 1293 // If we get here `this` is not Top() so it can't be a supertype. 1294 return false; 1295 } 1296 return GetTypeHandle()->IsAssignableFrom(rti.GetTypeHandle().Get()); 1297 } 1298 1299 // Returns true if the type information provide the same amount of details. 1300 // Note that it does not mean that the instructions have the same actual type 1301 // (e.g. tops are equal but they can be the result of a merge). 1302 bool IsEqual(ReferenceTypeInfo rti) SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) { 1303 if (IsExact() != rti.IsExact()) { 1304 return false; 1305 } 1306 if (IsTop() && rti.IsTop()) { 1307 // `Top` means java.lang.Object, so the types are equivalent. 1308 return true; 1309 } 1310 if (IsTop() || rti.IsTop()) { 1311 // If only one is top or object than they are not equivalent. 1312 // NB: We need this extra check because the type_handle of `Top` is invalid 1313 // and we cannot inspect its reference. 1314 return false; 1315 } 1316 1317 // Finally check the types. 1318 return GetTypeHandle().Get() == rti.GetTypeHandle().Get(); 1319 } 1320 1321 private: 1322 ReferenceTypeInfo() : ReferenceTypeInfo(TypeHandle(), false, true) {} 1323 ReferenceTypeInfo(TypeHandle type_handle, bool is_exact, bool is_top) 1324 : type_handle_(type_handle), is_exact_(is_exact), is_top_(is_top) {} 1325 1326 // The class of the object. 1327 TypeHandle type_handle_; 1328 // Whether or not the type is exact or a superclass of the actual type. 1329 // Whether or not we have any information about this type. 1330 bool is_exact_; 1331 // A true value here means that the object type should be java.lang.Object. 1332 // We don't have access to the corresponding mirror object every time so this 1333 // flag acts as a substitute. When true, the TypeHandle refers to a null 1334 // pointer and should not be used. 1335 bool is_top_; 1336}; 1337 1338std::ostream& operator<<(std::ostream& os, const ReferenceTypeInfo& rhs); 1339 1340class HInstruction : public ArenaObject<kArenaAllocMisc> { 1341 public: 1342 explicit HInstruction(SideEffects side_effects) 1343 : previous_(nullptr), 1344 next_(nullptr), 1345 block_(nullptr), 1346 id_(-1), 1347 ssa_index_(-1), 1348 environment_(nullptr), 1349 locations_(nullptr), 1350 live_interval_(nullptr), 1351 lifetime_position_(kNoLifetime), 1352 side_effects_(side_effects), 1353 reference_type_info_(ReferenceTypeInfo::CreateTop(/* is_exact */ false)) {} 1354 1355 virtual ~HInstruction() {} 1356 1357#define DECLARE_KIND(type, super) k##type, 1358 enum InstructionKind { 1359 FOR_EACH_INSTRUCTION(DECLARE_KIND) 1360 }; 1361#undef DECLARE_KIND 1362 1363 HInstruction* GetNext() const { return next_; } 1364 HInstruction* GetPrevious() const { return previous_; } 1365 1366 HInstruction* GetNextDisregardingMoves() const; 1367 HInstruction* GetPreviousDisregardingMoves() const; 1368 1369 HBasicBlock* GetBlock() const { return block_; } 1370 void SetBlock(HBasicBlock* block) { block_ = block; } 1371 bool IsInBlock() const { return block_ != nullptr; } 1372 bool IsInLoop() const { return block_->IsInLoop(); } 1373 bool IsLoopHeaderPhi() { return IsPhi() && block_->IsLoopHeader(); } 1374 1375 virtual size_t InputCount() const = 0; 1376 HInstruction* InputAt(size_t i) const { return InputRecordAt(i).GetInstruction(); } 1377 1378 virtual void Accept(HGraphVisitor* visitor) = 0; 1379 virtual const char* DebugName() const = 0; 1380 1381 virtual Primitive::Type GetType() const { return Primitive::kPrimVoid; } 1382 void SetRawInputAt(size_t index, HInstruction* input) { 1383 SetRawInputRecordAt(index, HUserRecord<HInstruction*>(input)); 1384 } 1385 1386 virtual bool NeedsEnvironment() const { return false; } 1387 virtual uint32_t GetDexPc() const { 1388 LOG(FATAL) << "GetDexPc() cannot be called on an instruction that" 1389 " does not need an environment"; 1390 UNREACHABLE(); 1391 } 1392 virtual bool IsControlFlow() const { return false; } 1393 virtual bool CanThrow() const { return false; } 1394 bool HasSideEffects() const { return side_effects_.HasSideEffects(); } 1395 1396 // Does not apply for all instructions, but having this at top level greatly 1397 // simplifies the null check elimination. 1398 virtual bool CanBeNull() const { 1399 DCHECK_EQ(GetType(), Primitive::kPrimNot) << "CanBeNull only applies to reference types"; 1400 return true; 1401 } 1402 1403 virtual bool CanDoImplicitNullCheckOn(HInstruction* obj) const { 1404 UNUSED(obj); 1405 return false; 1406 } 1407 1408 void SetReferenceTypeInfo(ReferenceTypeInfo reference_type_info) { 1409 DCHECK_EQ(GetType(), Primitive::kPrimNot); 1410 reference_type_info_ = reference_type_info; 1411 } 1412 1413 ReferenceTypeInfo GetReferenceTypeInfo() const { 1414 DCHECK_EQ(GetType(), Primitive::kPrimNot); 1415 return reference_type_info_; 1416 } 1417 1418 void AddUseAt(HInstruction* user, size_t index) { 1419 DCHECK(user != nullptr); 1420 HUseListNode<HInstruction*>* use = 1421 uses_.AddUse(user, index, GetBlock()->GetGraph()->GetArena()); 1422 user->SetRawInputRecordAt(index, HUserRecord<HInstruction*>(user->InputRecordAt(index), use)); 1423 } 1424 1425 void AddEnvUseAt(HEnvironment* user, size_t index) { 1426 DCHECK(user != nullptr); 1427 HUseListNode<HEnvironment*>* env_use = 1428 env_uses_.AddUse(user, index, GetBlock()->GetGraph()->GetArena()); 1429 user->RecordEnvUse(env_use); 1430 } 1431 1432 void RemoveAsUserOfInput(size_t input) { 1433 HUserRecord<HInstruction*> input_use = InputRecordAt(input); 1434 input_use.GetInstruction()->uses_.Remove(input_use.GetUseNode()); 1435 } 1436 1437 const HUseList<HInstruction*>& GetUses() const { return uses_; } 1438 const HUseList<HEnvironment*>& GetEnvUses() const { return env_uses_; } 1439 1440 bool HasUses() const { return !uses_.IsEmpty() || !env_uses_.IsEmpty(); } 1441 bool HasEnvironmentUses() const { return !env_uses_.IsEmpty(); } 1442 bool HasNonEnvironmentUses() const { return !uses_.IsEmpty(); } 1443 bool HasOnlyOneNonEnvironmentUse() const { 1444 return !HasEnvironmentUses() && GetUses().HasOnlyOneUse(); 1445 } 1446 1447 // Does this instruction strictly dominate `other_instruction`? 1448 // Returns false if this instruction and `other_instruction` are the same. 1449 // Aborts if this instruction and `other_instruction` are both phis. 1450 bool StrictlyDominates(HInstruction* other_instruction) const; 1451 1452 int GetId() const { return id_; } 1453 void SetId(int id) { id_ = id; } 1454 1455 int GetSsaIndex() const { return ssa_index_; } 1456 void SetSsaIndex(int ssa_index) { ssa_index_ = ssa_index; } 1457 bool HasSsaIndex() const { return ssa_index_ != -1; } 1458 1459 bool HasEnvironment() const { return environment_ != nullptr; } 1460 HEnvironment* GetEnvironment() const { return environment_; } 1461 // Set the `environment_` field. Raw because this method does not 1462 // update the uses lists. 1463 void SetRawEnvironment(HEnvironment* environment) { 1464 DCHECK(environment_ == nullptr); 1465 DCHECK_EQ(environment->GetHolder(), this); 1466 environment_ = environment; 1467 } 1468 1469 // Set the environment of this instruction, copying it from `environment`. While 1470 // copying, the uses lists are being updated. 1471 void CopyEnvironmentFrom(HEnvironment* environment) { 1472 DCHECK(environment_ == nullptr); 1473 ArenaAllocator* allocator = GetBlock()->GetGraph()->GetArena(); 1474 environment_ = new (allocator) HEnvironment(allocator, *environment, this); 1475 environment_->CopyFrom(environment); 1476 if (environment->GetParent() != nullptr) { 1477 environment_->SetAndCopyParentChain(allocator, environment->GetParent()); 1478 } 1479 } 1480 1481 void CopyEnvironmentFromWithLoopPhiAdjustment(HEnvironment* environment, 1482 HBasicBlock* block) { 1483 DCHECK(environment_ == nullptr); 1484 ArenaAllocator* allocator = GetBlock()->GetGraph()->GetArena(); 1485 environment_ = new (allocator) HEnvironment(allocator, *environment, this); 1486 environment_->CopyFromWithLoopPhiAdjustment(environment, block); 1487 if (environment->GetParent() != nullptr) { 1488 environment_->SetAndCopyParentChain(allocator, environment->GetParent()); 1489 } 1490 } 1491 1492 // Returns the number of entries in the environment. Typically, that is the 1493 // number of dex registers in a method. It could be more in case of inlining. 1494 size_t EnvironmentSize() const; 1495 1496 LocationSummary* GetLocations() const { return locations_; } 1497 void SetLocations(LocationSummary* locations) { locations_ = locations; } 1498 1499 void ReplaceWith(HInstruction* instruction); 1500 void ReplaceInput(HInstruction* replacement, size_t index); 1501 1502 // This is almost the same as doing `ReplaceWith()`. But in this helper, the 1503 // uses of this instruction by `other` are *not* updated. 1504 void ReplaceWithExceptInReplacementAtIndex(HInstruction* other, size_t use_index) { 1505 ReplaceWith(other); 1506 other->ReplaceInput(this, use_index); 1507 } 1508 1509 // Move `this` instruction before `cursor`. 1510 void MoveBefore(HInstruction* cursor); 1511 1512#define INSTRUCTION_TYPE_CHECK(type, super) \ 1513 bool Is##type() const { return (As##type() != nullptr); } \ 1514 virtual const H##type* As##type() const { return nullptr; } \ 1515 virtual H##type* As##type() { return nullptr; } 1516 1517 FOR_EACH_INSTRUCTION(INSTRUCTION_TYPE_CHECK) 1518#undef INSTRUCTION_TYPE_CHECK 1519 1520 // Returns whether the instruction can be moved within the graph. 1521 virtual bool CanBeMoved() const { return false; } 1522 1523 // Returns whether the two instructions are of the same kind. 1524 virtual bool InstructionTypeEquals(HInstruction* other) const { 1525 UNUSED(other); 1526 return false; 1527 } 1528 1529 // Returns whether any data encoded in the two instructions is equal. 1530 // This method does not look at the inputs. Both instructions must be 1531 // of the same type, otherwise the method has undefined behavior. 1532 virtual bool InstructionDataEquals(HInstruction* other) const { 1533 UNUSED(other); 1534 return false; 1535 } 1536 1537 // Returns whether two instructions are equal, that is: 1538 // 1) They have the same type and contain the same data (InstructionDataEquals). 1539 // 2) Their inputs are identical. 1540 bool Equals(HInstruction* other) const; 1541 1542 virtual InstructionKind GetKind() const = 0; 1543 1544 virtual size_t ComputeHashCode() const { 1545 size_t result = GetKind(); 1546 for (size_t i = 0, e = InputCount(); i < e; ++i) { 1547 result = (result * 31) + InputAt(i)->GetId(); 1548 } 1549 return result; 1550 } 1551 1552 SideEffects GetSideEffects() const { return side_effects_; } 1553 1554 size_t GetLifetimePosition() const { return lifetime_position_; } 1555 void SetLifetimePosition(size_t position) { lifetime_position_ = position; } 1556 LiveInterval* GetLiveInterval() const { return live_interval_; } 1557 void SetLiveInterval(LiveInterval* interval) { live_interval_ = interval; } 1558 bool HasLiveInterval() const { return live_interval_ != nullptr; } 1559 1560 bool IsSuspendCheckEntry() const { return IsSuspendCheck() && GetBlock()->IsEntryBlock(); } 1561 1562 // Returns whether the code generation of the instruction will require to have access 1563 // to the current method. Such instructions are: 1564 // (1): Instructions that require an environment, as calling the runtime requires 1565 // to walk the stack and have the current method stored at a specific stack address. 1566 // (2): Object literals like classes and strings, that are loaded from the dex cache 1567 // fields of the current method. 1568 bool NeedsCurrentMethod() const { 1569 return NeedsEnvironment() || IsLoadClass() || IsLoadString(); 1570 } 1571 1572 virtual bool NeedsDexCache() const { return false; } 1573 1574 protected: 1575 virtual const HUserRecord<HInstruction*> InputRecordAt(size_t i) const = 0; 1576 virtual void SetRawInputRecordAt(size_t index, const HUserRecord<HInstruction*>& input) = 0; 1577 1578 private: 1579 void RemoveEnvironmentUser(HUseListNode<HEnvironment*>* use_node) { env_uses_.Remove(use_node); } 1580 1581 HInstruction* previous_; 1582 HInstruction* next_; 1583 HBasicBlock* block_; 1584 1585 // An instruction gets an id when it is added to the graph. 1586 // It reflects creation order. A negative id means the instruction 1587 // has not been added to the graph. 1588 int id_; 1589 1590 // When doing liveness analysis, instructions that have uses get an SSA index. 1591 int ssa_index_; 1592 1593 // List of instructions that have this instruction as input. 1594 HUseList<HInstruction*> uses_; 1595 1596 // List of environments that contain this instruction. 1597 HUseList<HEnvironment*> env_uses_; 1598 1599 // The environment associated with this instruction. Not null if the instruction 1600 // might jump out of the method. 1601 HEnvironment* environment_; 1602 1603 // Set by the code generator. 1604 LocationSummary* locations_; 1605 1606 // Set by the liveness analysis. 1607 LiveInterval* live_interval_; 1608 1609 // Set by the liveness analysis, this is the position in a linear 1610 // order of blocks where this instruction's live interval start. 1611 size_t lifetime_position_; 1612 1613 const SideEffects side_effects_; 1614 1615 // TODO: for primitive types this should be marked as invalid. 1616 ReferenceTypeInfo reference_type_info_; 1617 1618 friend class GraphChecker; 1619 friend class HBasicBlock; 1620 friend class HEnvironment; 1621 friend class HGraph; 1622 friend class HInstructionList; 1623 1624 DISALLOW_COPY_AND_ASSIGN(HInstruction); 1625}; 1626std::ostream& operator<<(std::ostream& os, const HInstruction::InstructionKind& rhs); 1627 1628class HInputIterator : public ValueObject { 1629 public: 1630 explicit HInputIterator(HInstruction* instruction) : instruction_(instruction), index_(0) {} 1631 1632 bool Done() const { return index_ == instruction_->InputCount(); } 1633 HInstruction* Current() const { return instruction_->InputAt(index_); } 1634 void Advance() { index_++; } 1635 1636 private: 1637 HInstruction* instruction_; 1638 size_t index_; 1639 1640 DISALLOW_COPY_AND_ASSIGN(HInputIterator); 1641}; 1642 1643class HInstructionIterator : public ValueObject { 1644 public: 1645 explicit HInstructionIterator(const HInstructionList& instructions) 1646 : instruction_(instructions.first_instruction_) { 1647 next_ = Done() ? nullptr : instruction_->GetNext(); 1648 } 1649 1650 bool Done() const { return instruction_ == nullptr; } 1651 HInstruction* Current() const { return instruction_; } 1652 void Advance() { 1653 instruction_ = next_; 1654 next_ = Done() ? nullptr : instruction_->GetNext(); 1655 } 1656 1657 private: 1658 HInstruction* instruction_; 1659 HInstruction* next_; 1660 1661 DISALLOW_COPY_AND_ASSIGN(HInstructionIterator); 1662}; 1663 1664class HBackwardInstructionIterator : public ValueObject { 1665 public: 1666 explicit HBackwardInstructionIterator(const HInstructionList& instructions) 1667 : instruction_(instructions.last_instruction_) { 1668 next_ = Done() ? nullptr : instruction_->GetPrevious(); 1669 } 1670 1671 bool Done() const { return instruction_ == nullptr; } 1672 HInstruction* Current() const { return instruction_; } 1673 void Advance() { 1674 instruction_ = next_; 1675 next_ = Done() ? nullptr : instruction_->GetPrevious(); 1676 } 1677 1678 private: 1679 HInstruction* instruction_; 1680 HInstruction* next_; 1681 1682 DISALLOW_COPY_AND_ASSIGN(HBackwardInstructionIterator); 1683}; 1684 1685// An embedded container with N elements of type T. Used (with partial 1686// specialization for N=0) because embedded arrays cannot have size 0. 1687template<typename T, intptr_t N> 1688class EmbeddedArray { 1689 public: 1690 EmbeddedArray() : elements_() {} 1691 1692 intptr_t GetLength() const { return N; } 1693 1694 const T& operator[](intptr_t i) const { 1695 DCHECK_LT(i, GetLength()); 1696 return elements_[i]; 1697 } 1698 1699 T& operator[](intptr_t i) { 1700 DCHECK_LT(i, GetLength()); 1701 return elements_[i]; 1702 } 1703 1704 const T& At(intptr_t i) const { 1705 return (*this)[i]; 1706 } 1707 1708 void SetAt(intptr_t i, const T& val) { 1709 (*this)[i] = val; 1710 } 1711 1712 private: 1713 T elements_[N]; 1714}; 1715 1716template<typename T> 1717class EmbeddedArray<T, 0> { 1718 public: 1719 intptr_t length() const { return 0; } 1720 const T& operator[](intptr_t i) const { 1721 UNUSED(i); 1722 LOG(FATAL) << "Unreachable"; 1723 UNREACHABLE(); 1724 } 1725 T& operator[](intptr_t i) { 1726 UNUSED(i); 1727 LOG(FATAL) << "Unreachable"; 1728 UNREACHABLE(); 1729 } 1730}; 1731 1732template<intptr_t N> 1733class HTemplateInstruction: public HInstruction { 1734 public: 1735 HTemplateInstruction<N>(SideEffects side_effects) 1736 : HInstruction(side_effects), inputs_() {} 1737 virtual ~HTemplateInstruction() {} 1738 1739 size_t InputCount() const OVERRIDE { return N; } 1740 1741 protected: 1742 const HUserRecord<HInstruction*> InputRecordAt(size_t i) const OVERRIDE { return inputs_[i]; } 1743 1744 void SetRawInputRecordAt(size_t i, const HUserRecord<HInstruction*>& input) OVERRIDE { 1745 inputs_[i] = input; 1746 } 1747 1748 private: 1749 EmbeddedArray<HUserRecord<HInstruction*>, N> inputs_; 1750 1751 friend class SsaBuilder; 1752}; 1753 1754template<intptr_t N> 1755class HExpression : public HTemplateInstruction<N> { 1756 public: 1757 HExpression<N>(Primitive::Type type, SideEffects side_effects) 1758 : HTemplateInstruction<N>(side_effects), type_(type) {} 1759 virtual ~HExpression() {} 1760 1761 Primitive::Type GetType() const OVERRIDE { return type_; } 1762 1763 protected: 1764 Primitive::Type type_; 1765}; 1766 1767// Represents dex's RETURN_VOID opcode. A HReturnVoid is a control flow 1768// instruction that branches to the exit block. 1769class HReturnVoid : public HTemplateInstruction<0> { 1770 public: 1771 HReturnVoid() : HTemplateInstruction(SideEffects::None()) {} 1772 1773 bool IsControlFlow() const OVERRIDE { return true; } 1774 1775 DECLARE_INSTRUCTION(ReturnVoid); 1776 1777 private: 1778 DISALLOW_COPY_AND_ASSIGN(HReturnVoid); 1779}; 1780 1781// Represents dex's RETURN opcodes. A HReturn is a control flow 1782// instruction that branches to the exit block. 1783class HReturn : public HTemplateInstruction<1> { 1784 public: 1785 explicit HReturn(HInstruction* value) : HTemplateInstruction(SideEffects::None()) { 1786 SetRawInputAt(0, value); 1787 } 1788 1789 bool IsControlFlow() const OVERRIDE { return true; } 1790 1791 DECLARE_INSTRUCTION(Return); 1792 1793 private: 1794 DISALLOW_COPY_AND_ASSIGN(HReturn); 1795}; 1796 1797// The exit instruction is the only instruction of the exit block. 1798// Instructions aborting the method (HThrow and HReturn) must branch to the 1799// exit block. 1800class HExit : public HTemplateInstruction<0> { 1801 public: 1802 HExit() : HTemplateInstruction(SideEffects::None()) {} 1803 1804 bool IsControlFlow() const OVERRIDE { return true; } 1805 1806 DECLARE_INSTRUCTION(Exit); 1807 1808 private: 1809 DISALLOW_COPY_AND_ASSIGN(HExit); 1810}; 1811 1812// Jumps from one block to another. 1813class HGoto : public HTemplateInstruction<0> { 1814 public: 1815 HGoto() : HTemplateInstruction(SideEffects::None()) {} 1816 1817 bool IsControlFlow() const OVERRIDE { return true; } 1818 1819 HBasicBlock* GetSuccessor() const { 1820 return GetBlock()->GetSuccessors().Get(0); 1821 } 1822 1823 DECLARE_INSTRUCTION(Goto); 1824 1825 private: 1826 DISALLOW_COPY_AND_ASSIGN(HGoto); 1827}; 1828 1829 1830// Conditional branch. A block ending with an HIf instruction must have 1831// two successors. 1832class HIf : public HTemplateInstruction<1> { 1833 public: 1834 explicit HIf(HInstruction* input) : HTemplateInstruction(SideEffects::None()) { 1835 SetRawInputAt(0, input); 1836 } 1837 1838 bool IsControlFlow() const OVERRIDE { return true; } 1839 1840 HBasicBlock* IfTrueSuccessor() const { 1841 return GetBlock()->GetSuccessors().Get(0); 1842 } 1843 1844 HBasicBlock* IfFalseSuccessor() const { 1845 return GetBlock()->GetSuccessors().Get(1); 1846 } 1847 1848 DECLARE_INSTRUCTION(If); 1849 1850 private: 1851 DISALLOW_COPY_AND_ASSIGN(HIf); 1852}; 1853 1854// Deoptimize to interpreter, upon checking a condition. 1855class HDeoptimize : public HTemplateInstruction<1> { 1856 public: 1857 HDeoptimize(HInstruction* cond, uint32_t dex_pc) 1858 : HTemplateInstruction(SideEffects::None()), 1859 dex_pc_(dex_pc) { 1860 SetRawInputAt(0, cond); 1861 } 1862 1863 bool NeedsEnvironment() const OVERRIDE { return true; } 1864 bool CanThrow() const OVERRIDE { return true; } 1865 uint32_t GetDexPc() const OVERRIDE { return dex_pc_; } 1866 1867 DECLARE_INSTRUCTION(Deoptimize); 1868 1869 private: 1870 uint32_t dex_pc_; 1871 1872 DISALLOW_COPY_AND_ASSIGN(HDeoptimize); 1873}; 1874 1875// Represents the ArtMethod that was passed as a first argument to 1876// the method. It is used by instructions that depend on it, like 1877// instructions that work with the dex cache. 1878class HCurrentMethod : public HExpression<0> { 1879 public: 1880 explicit HCurrentMethod(Primitive::Type type) : HExpression(type, SideEffects::None()) {} 1881 1882 DECLARE_INSTRUCTION(CurrentMethod); 1883 1884 private: 1885 DISALLOW_COPY_AND_ASSIGN(HCurrentMethod); 1886}; 1887 1888class HUnaryOperation : public HExpression<1> { 1889 public: 1890 HUnaryOperation(Primitive::Type result_type, HInstruction* input) 1891 : HExpression(result_type, SideEffects::None()) { 1892 SetRawInputAt(0, input); 1893 } 1894 1895 HInstruction* GetInput() const { return InputAt(0); } 1896 Primitive::Type GetResultType() const { return GetType(); } 1897 1898 bool CanBeMoved() const OVERRIDE { return true; } 1899 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 1900 UNUSED(other); 1901 return true; 1902 } 1903 1904 // Try to statically evaluate `operation` and return a HConstant 1905 // containing the result of this evaluation. If `operation` cannot 1906 // be evaluated as a constant, return null. 1907 HConstant* TryStaticEvaluation() const; 1908 1909 // Apply this operation to `x`. 1910 virtual int32_t Evaluate(int32_t x) const = 0; 1911 virtual int64_t Evaluate(int64_t x) const = 0; 1912 1913 DECLARE_INSTRUCTION(UnaryOperation); 1914 1915 private: 1916 DISALLOW_COPY_AND_ASSIGN(HUnaryOperation); 1917}; 1918 1919class HBinaryOperation : public HExpression<2> { 1920 public: 1921 HBinaryOperation(Primitive::Type result_type, 1922 HInstruction* left, 1923 HInstruction* right) : HExpression(result_type, SideEffects::None()) { 1924 SetRawInputAt(0, left); 1925 SetRawInputAt(1, right); 1926 } 1927 1928 HInstruction* GetLeft() const { return InputAt(0); } 1929 HInstruction* GetRight() const { return InputAt(1); } 1930 Primitive::Type GetResultType() const { return GetType(); } 1931 1932 virtual bool IsCommutative() const { return false; } 1933 1934 // Put constant on the right. 1935 // Returns whether order is changed. 1936 bool OrderInputsWithConstantOnTheRight() { 1937 HInstruction* left = InputAt(0); 1938 HInstruction* right = InputAt(1); 1939 if (left->IsConstant() && !right->IsConstant()) { 1940 ReplaceInput(right, 0); 1941 ReplaceInput(left, 1); 1942 return true; 1943 } 1944 return false; 1945 } 1946 1947 // Order inputs by instruction id, but favor constant on the right side. 1948 // This helps GVN for commutative ops. 1949 void OrderInputs() { 1950 DCHECK(IsCommutative()); 1951 HInstruction* left = InputAt(0); 1952 HInstruction* right = InputAt(1); 1953 if (left == right || (!left->IsConstant() && right->IsConstant())) { 1954 return; 1955 } 1956 if (OrderInputsWithConstantOnTheRight()) { 1957 return; 1958 } 1959 // Order according to instruction id. 1960 if (left->GetId() > right->GetId()) { 1961 ReplaceInput(right, 0); 1962 ReplaceInput(left, 1); 1963 } 1964 } 1965 1966 bool CanBeMoved() const OVERRIDE { return true; } 1967 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 1968 UNUSED(other); 1969 return true; 1970 } 1971 1972 // Try to statically evaluate `operation` and return a HConstant 1973 // containing the result of this evaluation. If `operation` cannot 1974 // be evaluated as a constant, return null. 1975 HConstant* TryStaticEvaluation() const; 1976 1977 // Apply this operation to `x` and `y`. 1978 virtual int32_t Evaluate(int32_t x, int32_t y) const = 0; 1979 virtual int64_t Evaluate(int64_t x, int64_t y) const = 0; 1980 1981 // Returns an input that can legally be used as the right input and is 1982 // constant, or null. 1983 HConstant* GetConstantRight() const; 1984 1985 // If `GetConstantRight()` returns one of the input, this returns the other 1986 // one. Otherwise it returns null. 1987 HInstruction* GetLeastConstantLeft() const; 1988 1989 DECLARE_INSTRUCTION(BinaryOperation); 1990 1991 private: 1992 DISALLOW_COPY_AND_ASSIGN(HBinaryOperation); 1993}; 1994 1995class HCondition : public HBinaryOperation { 1996 public: 1997 HCondition(HInstruction* first, HInstruction* second) 1998 : HBinaryOperation(Primitive::kPrimBoolean, first, second), 1999 needs_materialization_(true) {} 2000 2001 bool NeedsMaterialization() const { return needs_materialization_; } 2002 void ClearNeedsMaterialization() { needs_materialization_ = false; } 2003 2004 // For code generation purposes, returns whether this instruction is just before 2005 // `instruction`, and disregard moves in between. 2006 bool IsBeforeWhenDisregardMoves(HInstruction* instruction) const; 2007 2008 DECLARE_INSTRUCTION(Condition); 2009 2010 virtual IfCondition GetCondition() const = 0; 2011 2012 private: 2013 // For register allocation purposes, returns whether this instruction needs to be 2014 // materialized (that is, not just be in the processor flags). 2015 bool needs_materialization_; 2016 2017 DISALLOW_COPY_AND_ASSIGN(HCondition); 2018}; 2019 2020// Instruction to check if two inputs are equal to each other. 2021class HEqual : public HCondition { 2022 public: 2023 HEqual(HInstruction* first, HInstruction* second) 2024 : HCondition(first, second) {} 2025 2026 bool IsCommutative() const OVERRIDE { return true; } 2027 2028 int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE { 2029 return x == y ? 1 : 0; 2030 } 2031 int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE { 2032 return x == y ? 1 : 0; 2033 } 2034 2035 DECLARE_INSTRUCTION(Equal); 2036 2037 IfCondition GetCondition() const OVERRIDE { 2038 return kCondEQ; 2039 } 2040 2041 private: 2042 DISALLOW_COPY_AND_ASSIGN(HEqual); 2043}; 2044 2045class HNotEqual : public HCondition { 2046 public: 2047 HNotEqual(HInstruction* first, HInstruction* second) 2048 : HCondition(first, second) {} 2049 2050 bool IsCommutative() const OVERRIDE { return true; } 2051 2052 int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE { 2053 return x != y ? 1 : 0; 2054 } 2055 int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE { 2056 return x != y ? 1 : 0; 2057 } 2058 2059 DECLARE_INSTRUCTION(NotEqual); 2060 2061 IfCondition GetCondition() const OVERRIDE { 2062 return kCondNE; 2063 } 2064 2065 private: 2066 DISALLOW_COPY_AND_ASSIGN(HNotEqual); 2067}; 2068 2069class HLessThan : public HCondition { 2070 public: 2071 HLessThan(HInstruction* first, HInstruction* second) 2072 : HCondition(first, second) {} 2073 2074 int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE { 2075 return x < y ? 1 : 0; 2076 } 2077 int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE { 2078 return x < y ? 1 : 0; 2079 } 2080 2081 DECLARE_INSTRUCTION(LessThan); 2082 2083 IfCondition GetCondition() const OVERRIDE { 2084 return kCondLT; 2085 } 2086 2087 private: 2088 DISALLOW_COPY_AND_ASSIGN(HLessThan); 2089}; 2090 2091class HLessThanOrEqual : public HCondition { 2092 public: 2093 HLessThanOrEqual(HInstruction* first, HInstruction* second) 2094 : HCondition(first, second) {} 2095 2096 int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE { 2097 return x <= y ? 1 : 0; 2098 } 2099 int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE { 2100 return x <= y ? 1 : 0; 2101 } 2102 2103 DECLARE_INSTRUCTION(LessThanOrEqual); 2104 2105 IfCondition GetCondition() const OVERRIDE { 2106 return kCondLE; 2107 } 2108 2109 private: 2110 DISALLOW_COPY_AND_ASSIGN(HLessThanOrEqual); 2111}; 2112 2113class HGreaterThan : public HCondition { 2114 public: 2115 HGreaterThan(HInstruction* first, HInstruction* second) 2116 : HCondition(first, second) {} 2117 2118 int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE { 2119 return x > y ? 1 : 0; 2120 } 2121 int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE { 2122 return x > y ? 1 : 0; 2123 } 2124 2125 DECLARE_INSTRUCTION(GreaterThan); 2126 2127 IfCondition GetCondition() const OVERRIDE { 2128 return kCondGT; 2129 } 2130 2131 private: 2132 DISALLOW_COPY_AND_ASSIGN(HGreaterThan); 2133}; 2134 2135class HGreaterThanOrEqual : public HCondition { 2136 public: 2137 HGreaterThanOrEqual(HInstruction* first, HInstruction* second) 2138 : HCondition(first, second) {} 2139 2140 int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE { 2141 return x >= y ? 1 : 0; 2142 } 2143 int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE { 2144 return x >= y ? 1 : 0; 2145 } 2146 2147 DECLARE_INSTRUCTION(GreaterThanOrEqual); 2148 2149 IfCondition GetCondition() const OVERRIDE { 2150 return kCondGE; 2151 } 2152 2153 private: 2154 DISALLOW_COPY_AND_ASSIGN(HGreaterThanOrEqual); 2155}; 2156 2157 2158// Instruction to check how two inputs compare to each other. 2159// Result is 0 if input0 == input1, 1 if input0 > input1, or -1 if input0 < input1. 2160class HCompare : public HBinaryOperation { 2161 public: 2162 // The bias applies for floating point operations and indicates how NaN 2163 // comparisons are treated: 2164 enum Bias { 2165 kNoBias, // bias is not applicable (i.e. for long operation) 2166 kGtBias, // return 1 for NaN comparisons 2167 kLtBias, // return -1 for NaN comparisons 2168 }; 2169 2170 HCompare(Primitive::Type type, HInstruction* first, HInstruction* second, Bias bias) 2171 : HBinaryOperation(Primitive::kPrimInt, first, second), bias_(bias) { 2172 DCHECK_EQ(type, first->GetType()); 2173 DCHECK_EQ(type, second->GetType()); 2174 } 2175 2176 int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE { 2177 return 2178 x == y ? 0 : 2179 x > y ? 1 : 2180 -1; 2181 } 2182 2183 int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE { 2184 return 2185 x == y ? 0 : 2186 x > y ? 1 : 2187 -1; 2188 } 2189 2190 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 2191 return bias_ == other->AsCompare()->bias_; 2192 } 2193 2194 bool IsGtBias() { return bias_ == kGtBias; } 2195 2196 DECLARE_INSTRUCTION(Compare); 2197 2198 private: 2199 const Bias bias_; 2200 2201 DISALLOW_COPY_AND_ASSIGN(HCompare); 2202}; 2203 2204// A local in the graph. Corresponds to a Dex register. 2205class HLocal : public HTemplateInstruction<0> { 2206 public: 2207 explicit HLocal(uint16_t reg_number) 2208 : HTemplateInstruction(SideEffects::None()), reg_number_(reg_number) {} 2209 2210 DECLARE_INSTRUCTION(Local); 2211 2212 uint16_t GetRegNumber() const { return reg_number_; } 2213 2214 private: 2215 // The Dex register number. 2216 const uint16_t reg_number_; 2217 2218 DISALLOW_COPY_AND_ASSIGN(HLocal); 2219}; 2220 2221// Load a given local. The local is an input of this instruction. 2222class HLoadLocal : public HExpression<1> { 2223 public: 2224 HLoadLocal(HLocal* local, Primitive::Type type) 2225 : HExpression(type, SideEffects::None()) { 2226 SetRawInputAt(0, local); 2227 } 2228 2229 HLocal* GetLocal() const { return reinterpret_cast<HLocal*>(InputAt(0)); } 2230 2231 DECLARE_INSTRUCTION(LoadLocal); 2232 2233 private: 2234 DISALLOW_COPY_AND_ASSIGN(HLoadLocal); 2235}; 2236 2237// Store a value in a given local. This instruction has two inputs: the value 2238// and the local. 2239class HStoreLocal : public HTemplateInstruction<2> { 2240 public: 2241 HStoreLocal(HLocal* local, HInstruction* value) : HTemplateInstruction(SideEffects::None()) { 2242 SetRawInputAt(0, local); 2243 SetRawInputAt(1, value); 2244 } 2245 2246 HLocal* GetLocal() const { return reinterpret_cast<HLocal*>(InputAt(0)); } 2247 2248 DECLARE_INSTRUCTION(StoreLocal); 2249 2250 private: 2251 DISALLOW_COPY_AND_ASSIGN(HStoreLocal); 2252}; 2253 2254class HConstant : public HExpression<0> { 2255 public: 2256 explicit HConstant(Primitive::Type type) : HExpression(type, SideEffects::None()) {} 2257 2258 bool CanBeMoved() const OVERRIDE { return true; } 2259 2260 virtual bool IsMinusOne() const { return false; } 2261 virtual bool IsZero() const { return false; } 2262 virtual bool IsOne() const { return false; } 2263 2264 DECLARE_INSTRUCTION(Constant); 2265 2266 private: 2267 DISALLOW_COPY_AND_ASSIGN(HConstant); 2268}; 2269 2270class HFloatConstant : public HConstant { 2271 public: 2272 float GetValue() const { return value_; } 2273 2274 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 2275 return bit_cast<uint32_t, float>(other->AsFloatConstant()->value_) == 2276 bit_cast<uint32_t, float>(value_); 2277 } 2278 2279 size_t ComputeHashCode() const OVERRIDE { return static_cast<size_t>(GetValue()); } 2280 2281 bool IsMinusOne() const OVERRIDE { 2282 return bit_cast<uint32_t, float>(value_) == bit_cast<uint32_t, float>((-1.0f)); 2283 } 2284 bool IsZero() const OVERRIDE { 2285 return value_ == 0.0f; 2286 } 2287 bool IsOne() const OVERRIDE { 2288 return bit_cast<uint32_t, float>(value_) == bit_cast<uint32_t, float>(1.0f); 2289 } 2290 bool IsNaN() const { 2291 return std::isnan(value_); 2292 } 2293 2294 DECLARE_INSTRUCTION(FloatConstant); 2295 2296 private: 2297 explicit HFloatConstant(float value) : HConstant(Primitive::kPrimFloat), value_(value) {} 2298 explicit HFloatConstant(int32_t value) 2299 : HConstant(Primitive::kPrimFloat), value_(bit_cast<float, int32_t>(value)) {} 2300 2301 const float value_; 2302 2303 // Only the SsaBuilder and HGraph can create floating-point constants. 2304 friend class SsaBuilder; 2305 friend class HGraph; 2306 DISALLOW_COPY_AND_ASSIGN(HFloatConstant); 2307}; 2308 2309class HDoubleConstant : public HConstant { 2310 public: 2311 double GetValue() const { return value_; } 2312 2313 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 2314 return bit_cast<uint64_t, double>(other->AsDoubleConstant()->value_) == 2315 bit_cast<uint64_t, double>(value_); 2316 } 2317 2318 size_t ComputeHashCode() const OVERRIDE { return static_cast<size_t>(GetValue()); } 2319 2320 bool IsMinusOne() const OVERRIDE { 2321 return bit_cast<uint64_t, double>(value_) == bit_cast<uint64_t, double>((-1.0)); 2322 } 2323 bool IsZero() const OVERRIDE { 2324 return value_ == 0.0; 2325 } 2326 bool IsOne() const OVERRIDE { 2327 return bit_cast<uint64_t, double>(value_) == bit_cast<uint64_t, double>(1.0); 2328 } 2329 bool IsNaN() const { 2330 return std::isnan(value_); 2331 } 2332 2333 DECLARE_INSTRUCTION(DoubleConstant); 2334 2335 private: 2336 explicit HDoubleConstant(double value) : HConstant(Primitive::kPrimDouble), value_(value) {} 2337 explicit HDoubleConstant(int64_t value) 2338 : HConstant(Primitive::kPrimDouble), value_(bit_cast<double, int64_t>(value)) {} 2339 2340 const double value_; 2341 2342 // Only the SsaBuilder and HGraph can create floating-point constants. 2343 friend class SsaBuilder; 2344 friend class HGraph; 2345 DISALLOW_COPY_AND_ASSIGN(HDoubleConstant); 2346}; 2347 2348class HNullConstant : public HConstant { 2349 public: 2350 bool InstructionDataEquals(HInstruction* other ATTRIBUTE_UNUSED) const OVERRIDE { 2351 return true; 2352 } 2353 2354 size_t ComputeHashCode() const OVERRIDE { return 0; } 2355 2356 DECLARE_INSTRUCTION(NullConstant); 2357 2358 private: 2359 HNullConstant() : HConstant(Primitive::kPrimNot) {} 2360 2361 friend class HGraph; 2362 DISALLOW_COPY_AND_ASSIGN(HNullConstant); 2363}; 2364 2365// Constants of the type int. Those can be from Dex instructions, or 2366// synthesized (for example with the if-eqz instruction). 2367class HIntConstant : public HConstant { 2368 public: 2369 int32_t GetValue() const { return value_; } 2370 2371 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 2372 return other->AsIntConstant()->value_ == value_; 2373 } 2374 2375 size_t ComputeHashCode() const OVERRIDE { return GetValue(); } 2376 2377 bool IsMinusOne() const OVERRIDE { return GetValue() == -1; } 2378 bool IsZero() const OVERRIDE { return GetValue() == 0; } 2379 bool IsOne() const OVERRIDE { return GetValue() == 1; } 2380 2381 DECLARE_INSTRUCTION(IntConstant); 2382 2383 private: 2384 explicit HIntConstant(int32_t value) : HConstant(Primitive::kPrimInt), value_(value) {} 2385 2386 const int32_t value_; 2387 2388 friend class HGraph; 2389 ART_FRIEND_TEST(GraphTest, InsertInstructionBefore); 2390 ART_FRIEND_TYPED_TEST(ParallelMoveTest, ConstantLast); 2391 DISALLOW_COPY_AND_ASSIGN(HIntConstant); 2392}; 2393 2394class HLongConstant : public HConstant { 2395 public: 2396 int64_t GetValue() const { return value_; } 2397 2398 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 2399 return other->AsLongConstant()->value_ == value_; 2400 } 2401 2402 size_t ComputeHashCode() const OVERRIDE { return static_cast<size_t>(GetValue()); } 2403 2404 bool IsMinusOne() const OVERRIDE { return GetValue() == -1; } 2405 bool IsZero() const OVERRIDE { return GetValue() == 0; } 2406 bool IsOne() const OVERRIDE { return GetValue() == 1; } 2407 2408 DECLARE_INSTRUCTION(LongConstant); 2409 2410 private: 2411 explicit HLongConstant(int64_t value) : HConstant(Primitive::kPrimLong), value_(value) {} 2412 2413 const int64_t value_; 2414 2415 friend class HGraph; 2416 DISALLOW_COPY_AND_ASSIGN(HLongConstant); 2417}; 2418 2419enum class Intrinsics { 2420#define OPTIMIZING_INTRINSICS(Name, IsStatic) k ## Name, 2421#include "intrinsics_list.h" 2422 kNone, 2423 INTRINSICS_LIST(OPTIMIZING_INTRINSICS) 2424#undef INTRINSICS_LIST 2425#undef OPTIMIZING_INTRINSICS 2426}; 2427std::ostream& operator<<(std::ostream& os, const Intrinsics& intrinsic); 2428 2429class HInvoke : public HInstruction { 2430 public: 2431 size_t InputCount() const OVERRIDE { return inputs_.Size(); } 2432 2433 // Runtime needs to walk the stack, so Dex -> Dex calls need to 2434 // know their environment. 2435 bool NeedsEnvironment() const OVERRIDE { return true; } 2436 2437 void SetArgumentAt(size_t index, HInstruction* argument) { 2438 SetRawInputAt(index, argument); 2439 } 2440 2441 // Return the number of arguments. This number can be lower than 2442 // the number of inputs returned by InputCount(), as some invoke 2443 // instructions (e.g. HInvokeStaticOrDirect) can have non-argument 2444 // inputs at the end of their list of inputs. 2445 uint32_t GetNumberOfArguments() const { return number_of_arguments_; } 2446 2447 Primitive::Type GetType() const OVERRIDE { return return_type_; } 2448 2449 uint32_t GetDexPc() const OVERRIDE { return dex_pc_; } 2450 2451 uint32_t GetDexMethodIndex() const { return dex_method_index_; } 2452 const DexFile& GetDexFile() const { return GetEnvironment()->GetDexFile(); } 2453 2454 InvokeType GetOriginalInvokeType() const { return original_invoke_type_; } 2455 2456 Intrinsics GetIntrinsic() const { 2457 return intrinsic_; 2458 } 2459 2460 void SetIntrinsic(Intrinsics intrinsic) { 2461 intrinsic_ = intrinsic; 2462 } 2463 2464 bool IsInlined() const { 2465 return GetEnvironment()->GetParent() != nullptr; 2466 } 2467 2468 bool CanThrow() const OVERRIDE { return true; } 2469 2470 DECLARE_INSTRUCTION(Invoke); 2471 2472 protected: 2473 HInvoke(ArenaAllocator* arena, 2474 uint32_t number_of_arguments, 2475 uint32_t number_of_other_inputs, 2476 Primitive::Type return_type, 2477 uint32_t dex_pc, 2478 uint32_t dex_method_index, 2479 InvokeType original_invoke_type) 2480 : HInstruction(SideEffects::All()), 2481 number_of_arguments_(number_of_arguments), 2482 inputs_(arena, number_of_arguments), 2483 return_type_(return_type), 2484 dex_pc_(dex_pc), 2485 dex_method_index_(dex_method_index), 2486 original_invoke_type_(original_invoke_type), 2487 intrinsic_(Intrinsics::kNone) { 2488 uint32_t number_of_inputs = number_of_arguments + number_of_other_inputs; 2489 inputs_.SetSize(number_of_inputs); 2490 } 2491 2492 const HUserRecord<HInstruction*> InputRecordAt(size_t i) const OVERRIDE { return inputs_.Get(i); } 2493 void SetRawInputRecordAt(size_t index, const HUserRecord<HInstruction*>& input) OVERRIDE { 2494 inputs_.Put(index, input); 2495 } 2496 2497 uint32_t number_of_arguments_; 2498 GrowableArray<HUserRecord<HInstruction*> > inputs_; 2499 const Primitive::Type return_type_; 2500 const uint32_t dex_pc_; 2501 const uint32_t dex_method_index_; 2502 const InvokeType original_invoke_type_; 2503 Intrinsics intrinsic_; 2504 2505 private: 2506 DISALLOW_COPY_AND_ASSIGN(HInvoke); 2507}; 2508 2509class HInvokeStaticOrDirect : public HInvoke { 2510 public: 2511 // Requirements of this method call regarding the class 2512 // initialization (clinit) check of its declaring class. 2513 enum class ClinitCheckRequirement { 2514 kNone, // Class already initialized. 2515 kExplicit, // Static call having explicit clinit check as last input. 2516 kImplicit, // Static call implicitly requiring a clinit check. 2517 }; 2518 2519 HInvokeStaticOrDirect(ArenaAllocator* arena, 2520 uint32_t number_of_arguments, 2521 Primitive::Type return_type, 2522 uint32_t dex_pc, 2523 uint32_t dex_method_index, 2524 bool is_recursive, 2525 int32_t string_init_offset, 2526 InvokeType original_invoke_type, 2527 InvokeType invoke_type, 2528 ClinitCheckRequirement clinit_check_requirement) 2529 : HInvoke(arena, 2530 number_of_arguments, 2531 // There is one extra argument for the HCurrentMethod node, and 2532 // potentially one other if the clinit check is explicit. 2533 clinit_check_requirement == ClinitCheckRequirement::kExplicit ? 2u : 1u, 2534 return_type, 2535 dex_pc, 2536 dex_method_index, 2537 original_invoke_type), 2538 invoke_type_(invoke_type), 2539 is_recursive_(is_recursive), 2540 clinit_check_requirement_(clinit_check_requirement), 2541 string_init_offset_(string_init_offset) {} 2542 2543 bool CanDoImplicitNullCheckOn(HInstruction* obj) const OVERRIDE { 2544 UNUSED(obj); 2545 // We access the method via the dex cache so we can't do an implicit null check. 2546 // TODO: for intrinsics we can generate implicit null checks. 2547 return false; 2548 } 2549 2550 InvokeType GetInvokeType() const { return invoke_type_; } 2551 bool IsRecursive() const { return is_recursive_; } 2552 bool NeedsDexCache() const OVERRIDE { return !IsRecursive(); } 2553 bool IsStringInit() const { return string_init_offset_ != 0; } 2554 int32_t GetStringInitOffset() const { return string_init_offset_; } 2555 uint32_t GetCurrentMethodInputIndex() const { return GetNumberOfArguments(); } 2556 2557 // Is this instruction a call to a static method? 2558 bool IsStatic() const { 2559 return GetInvokeType() == kStatic; 2560 } 2561 2562 // Remove the art::HLoadClass instruction set as last input by 2563 // art::PrepareForRegisterAllocation::VisitClinitCheck in lieu of 2564 // the initial art::HClinitCheck instruction (only relevant for 2565 // static calls with explicit clinit check). 2566 void RemoveLoadClassAsLastInput() { 2567 DCHECK(IsStaticWithExplicitClinitCheck()); 2568 size_t last_input_index = InputCount() - 1; 2569 HInstruction* last_input = InputAt(last_input_index); 2570 DCHECK(last_input != nullptr); 2571 DCHECK(last_input->IsLoadClass()) << last_input->DebugName(); 2572 RemoveAsUserOfInput(last_input_index); 2573 inputs_.DeleteAt(last_input_index); 2574 clinit_check_requirement_ = ClinitCheckRequirement::kImplicit; 2575 DCHECK(IsStaticWithImplicitClinitCheck()); 2576 } 2577 2578 // Is this a call to a static method whose declaring class has an 2579 // explicit intialization check in the graph? 2580 bool IsStaticWithExplicitClinitCheck() const { 2581 return IsStatic() && (clinit_check_requirement_ == ClinitCheckRequirement::kExplicit); 2582 } 2583 2584 // Is this a call to a static method whose declaring class has an 2585 // implicit intialization check requirement? 2586 bool IsStaticWithImplicitClinitCheck() const { 2587 return IsStatic() && (clinit_check_requirement_ == ClinitCheckRequirement::kImplicit); 2588 } 2589 2590 DECLARE_INSTRUCTION(InvokeStaticOrDirect); 2591 2592 protected: 2593 const HUserRecord<HInstruction*> InputRecordAt(size_t i) const OVERRIDE { 2594 const HUserRecord<HInstruction*> input_record = HInvoke::InputRecordAt(i); 2595 if (kIsDebugBuild && IsStaticWithExplicitClinitCheck() && (i == InputCount() - 1)) { 2596 HInstruction* input = input_record.GetInstruction(); 2597 // `input` is the last input of a static invoke marked as having 2598 // an explicit clinit check. It must either be: 2599 // - an art::HClinitCheck instruction, set by art::HGraphBuilder; or 2600 // - an art::HLoadClass instruction, set by art::PrepareForRegisterAllocation. 2601 DCHECK(input != nullptr); 2602 DCHECK(input->IsClinitCheck() || input->IsLoadClass()) << input->DebugName(); 2603 } 2604 return input_record; 2605 } 2606 2607 private: 2608 const InvokeType invoke_type_; 2609 const bool is_recursive_; 2610 ClinitCheckRequirement clinit_check_requirement_; 2611 // Thread entrypoint offset for string init method if this is a string init invoke. 2612 // Note that there are multiple string init methods, each having its own offset. 2613 int32_t string_init_offset_; 2614 2615 DISALLOW_COPY_AND_ASSIGN(HInvokeStaticOrDirect); 2616}; 2617 2618class HInvokeVirtual : public HInvoke { 2619 public: 2620 HInvokeVirtual(ArenaAllocator* arena, 2621 uint32_t number_of_arguments, 2622 Primitive::Type return_type, 2623 uint32_t dex_pc, 2624 uint32_t dex_method_index, 2625 uint32_t vtable_index) 2626 : HInvoke(arena, number_of_arguments, 0u, return_type, dex_pc, dex_method_index, kVirtual), 2627 vtable_index_(vtable_index) {} 2628 2629 bool CanDoImplicitNullCheckOn(HInstruction* obj) const OVERRIDE { 2630 // TODO: Add implicit null checks in intrinsics. 2631 return (obj == InputAt(0)) && !GetLocations()->Intrinsified(); 2632 } 2633 2634 uint32_t GetVTableIndex() const { return vtable_index_; } 2635 2636 DECLARE_INSTRUCTION(InvokeVirtual); 2637 2638 private: 2639 const uint32_t vtable_index_; 2640 2641 DISALLOW_COPY_AND_ASSIGN(HInvokeVirtual); 2642}; 2643 2644class HInvokeInterface : public HInvoke { 2645 public: 2646 HInvokeInterface(ArenaAllocator* arena, 2647 uint32_t number_of_arguments, 2648 Primitive::Type return_type, 2649 uint32_t dex_pc, 2650 uint32_t dex_method_index, 2651 uint32_t imt_index) 2652 : HInvoke(arena, number_of_arguments, 0u, return_type, dex_pc, dex_method_index, kInterface), 2653 imt_index_(imt_index) {} 2654 2655 bool CanDoImplicitNullCheckOn(HInstruction* obj) const OVERRIDE { 2656 // TODO: Add implicit null checks in intrinsics. 2657 return (obj == InputAt(0)) && !GetLocations()->Intrinsified(); 2658 } 2659 2660 uint32_t GetImtIndex() const { return imt_index_; } 2661 uint32_t GetDexMethodIndex() const { return dex_method_index_; } 2662 2663 DECLARE_INSTRUCTION(InvokeInterface); 2664 2665 private: 2666 const uint32_t imt_index_; 2667 2668 DISALLOW_COPY_AND_ASSIGN(HInvokeInterface); 2669}; 2670 2671class HNewInstance : public HExpression<1> { 2672 public: 2673 HNewInstance(HCurrentMethod* current_method, 2674 uint32_t dex_pc, 2675 uint16_t type_index, 2676 const DexFile& dex_file, 2677 QuickEntrypointEnum entrypoint) 2678 : HExpression(Primitive::kPrimNot, SideEffects::None()), 2679 dex_pc_(dex_pc), 2680 type_index_(type_index), 2681 dex_file_(dex_file), 2682 entrypoint_(entrypoint) { 2683 SetRawInputAt(0, current_method); 2684 } 2685 2686 uint32_t GetDexPc() const OVERRIDE { return dex_pc_; } 2687 uint16_t GetTypeIndex() const { return type_index_; } 2688 const DexFile& GetDexFile() const { return dex_file_; } 2689 2690 // Calls runtime so needs an environment. 2691 bool NeedsEnvironment() const OVERRIDE { return true; } 2692 // It may throw when called on: 2693 // - interfaces 2694 // - abstract/innaccessible/unknown classes 2695 // TODO: optimize when possible. 2696 bool CanThrow() const OVERRIDE { return true; } 2697 2698 bool CanBeNull() const OVERRIDE { return false; } 2699 2700 QuickEntrypointEnum GetEntrypoint() const { return entrypoint_; } 2701 2702 DECLARE_INSTRUCTION(NewInstance); 2703 2704 private: 2705 const uint32_t dex_pc_; 2706 const uint16_t type_index_; 2707 const DexFile& dex_file_; 2708 const QuickEntrypointEnum entrypoint_; 2709 2710 DISALLOW_COPY_AND_ASSIGN(HNewInstance); 2711}; 2712 2713class HNeg : public HUnaryOperation { 2714 public: 2715 explicit HNeg(Primitive::Type result_type, HInstruction* input) 2716 : HUnaryOperation(result_type, input) {} 2717 2718 int32_t Evaluate(int32_t x) const OVERRIDE { return -x; } 2719 int64_t Evaluate(int64_t x) const OVERRIDE { return -x; } 2720 2721 DECLARE_INSTRUCTION(Neg); 2722 2723 private: 2724 DISALLOW_COPY_AND_ASSIGN(HNeg); 2725}; 2726 2727class HNewArray : public HExpression<2> { 2728 public: 2729 HNewArray(HInstruction* length, 2730 HCurrentMethod* current_method, 2731 uint32_t dex_pc, 2732 uint16_t type_index, 2733 const DexFile& dex_file, 2734 QuickEntrypointEnum entrypoint) 2735 : HExpression(Primitive::kPrimNot, SideEffects::None()), 2736 dex_pc_(dex_pc), 2737 type_index_(type_index), 2738 dex_file_(dex_file), 2739 entrypoint_(entrypoint) { 2740 SetRawInputAt(0, length); 2741 SetRawInputAt(1, current_method); 2742 } 2743 2744 uint32_t GetDexPc() const OVERRIDE { return dex_pc_; } 2745 uint16_t GetTypeIndex() const { return type_index_; } 2746 const DexFile& GetDexFile() const { return dex_file_; } 2747 2748 // Calls runtime so needs an environment. 2749 bool NeedsEnvironment() const OVERRIDE { return true; } 2750 2751 // May throw NegativeArraySizeException, OutOfMemoryError, etc. 2752 bool CanThrow() const OVERRIDE { return true; } 2753 2754 bool CanBeNull() const OVERRIDE { return false; } 2755 2756 QuickEntrypointEnum GetEntrypoint() const { return entrypoint_; } 2757 2758 DECLARE_INSTRUCTION(NewArray); 2759 2760 private: 2761 const uint32_t dex_pc_; 2762 const uint16_t type_index_; 2763 const DexFile& dex_file_; 2764 const QuickEntrypointEnum entrypoint_; 2765 2766 DISALLOW_COPY_AND_ASSIGN(HNewArray); 2767}; 2768 2769class HAdd : public HBinaryOperation { 2770 public: 2771 HAdd(Primitive::Type result_type, HInstruction* left, HInstruction* right) 2772 : HBinaryOperation(result_type, left, right) {} 2773 2774 bool IsCommutative() const OVERRIDE { return true; } 2775 2776 int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE { 2777 return x + y; 2778 } 2779 int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE { 2780 return x + y; 2781 } 2782 2783 DECLARE_INSTRUCTION(Add); 2784 2785 private: 2786 DISALLOW_COPY_AND_ASSIGN(HAdd); 2787}; 2788 2789class HSub : public HBinaryOperation { 2790 public: 2791 HSub(Primitive::Type result_type, HInstruction* left, HInstruction* right) 2792 : HBinaryOperation(result_type, left, right) {} 2793 2794 int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE { 2795 return x - y; 2796 } 2797 int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE { 2798 return x - y; 2799 } 2800 2801 DECLARE_INSTRUCTION(Sub); 2802 2803 private: 2804 DISALLOW_COPY_AND_ASSIGN(HSub); 2805}; 2806 2807class HMul : public HBinaryOperation { 2808 public: 2809 HMul(Primitive::Type result_type, HInstruction* left, HInstruction* right) 2810 : HBinaryOperation(result_type, left, right) {} 2811 2812 bool IsCommutative() const OVERRIDE { return true; } 2813 2814 int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE { return x * y; } 2815 int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE { return x * y; } 2816 2817 DECLARE_INSTRUCTION(Mul); 2818 2819 private: 2820 DISALLOW_COPY_AND_ASSIGN(HMul); 2821}; 2822 2823class HDiv : public HBinaryOperation { 2824 public: 2825 HDiv(Primitive::Type result_type, HInstruction* left, HInstruction* right, uint32_t dex_pc) 2826 : HBinaryOperation(result_type, left, right), dex_pc_(dex_pc) {} 2827 2828 int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE { 2829 // Our graph structure ensures we never have 0 for `y` during constant folding. 2830 DCHECK_NE(y, 0); 2831 // Special case -1 to avoid getting a SIGFPE on x86(_64). 2832 return (y == -1) ? -x : x / y; 2833 } 2834 2835 int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE { 2836 DCHECK_NE(y, 0); 2837 // Special case -1 to avoid getting a SIGFPE on x86(_64). 2838 return (y == -1) ? -x : x / y; 2839 } 2840 2841 uint32_t GetDexPc() const OVERRIDE { return dex_pc_; } 2842 2843 DECLARE_INSTRUCTION(Div); 2844 2845 private: 2846 const uint32_t dex_pc_; 2847 2848 DISALLOW_COPY_AND_ASSIGN(HDiv); 2849}; 2850 2851class HRem : public HBinaryOperation { 2852 public: 2853 HRem(Primitive::Type result_type, HInstruction* left, HInstruction* right, uint32_t dex_pc) 2854 : HBinaryOperation(result_type, left, right), dex_pc_(dex_pc) {} 2855 2856 int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE { 2857 DCHECK_NE(y, 0); 2858 // Special case -1 to avoid getting a SIGFPE on x86(_64). 2859 return (y == -1) ? 0 : x % y; 2860 } 2861 2862 int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE { 2863 DCHECK_NE(y, 0); 2864 // Special case -1 to avoid getting a SIGFPE on x86(_64). 2865 return (y == -1) ? 0 : x % y; 2866 } 2867 2868 uint32_t GetDexPc() const OVERRIDE { return dex_pc_; } 2869 2870 DECLARE_INSTRUCTION(Rem); 2871 2872 private: 2873 const uint32_t dex_pc_; 2874 2875 DISALLOW_COPY_AND_ASSIGN(HRem); 2876}; 2877 2878class HDivZeroCheck : public HExpression<1> { 2879 public: 2880 HDivZeroCheck(HInstruction* value, uint32_t dex_pc) 2881 : HExpression(value->GetType(), SideEffects::None()), dex_pc_(dex_pc) { 2882 SetRawInputAt(0, value); 2883 } 2884 2885 bool CanBeMoved() const OVERRIDE { return true; } 2886 2887 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 2888 UNUSED(other); 2889 return true; 2890 } 2891 2892 bool NeedsEnvironment() const OVERRIDE { return true; } 2893 bool CanThrow() const OVERRIDE { return true; } 2894 2895 uint32_t GetDexPc() const OVERRIDE { return dex_pc_; } 2896 2897 DECLARE_INSTRUCTION(DivZeroCheck); 2898 2899 private: 2900 const uint32_t dex_pc_; 2901 2902 DISALLOW_COPY_AND_ASSIGN(HDivZeroCheck); 2903}; 2904 2905class HShl : public HBinaryOperation { 2906 public: 2907 HShl(Primitive::Type result_type, HInstruction* left, HInstruction* right) 2908 : HBinaryOperation(result_type, left, right) {} 2909 2910 int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE { return x << (y & kMaxIntShiftValue); } 2911 int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE { return x << (y & kMaxLongShiftValue); } 2912 2913 DECLARE_INSTRUCTION(Shl); 2914 2915 private: 2916 DISALLOW_COPY_AND_ASSIGN(HShl); 2917}; 2918 2919class HShr : public HBinaryOperation { 2920 public: 2921 HShr(Primitive::Type result_type, HInstruction* left, HInstruction* right) 2922 : HBinaryOperation(result_type, left, right) {} 2923 2924 int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE { return x >> (y & kMaxIntShiftValue); } 2925 int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE { return x >> (y & kMaxLongShiftValue); } 2926 2927 DECLARE_INSTRUCTION(Shr); 2928 2929 private: 2930 DISALLOW_COPY_AND_ASSIGN(HShr); 2931}; 2932 2933class HUShr : public HBinaryOperation { 2934 public: 2935 HUShr(Primitive::Type result_type, HInstruction* left, HInstruction* right) 2936 : HBinaryOperation(result_type, left, right) {} 2937 2938 int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE { 2939 uint32_t ux = static_cast<uint32_t>(x); 2940 uint32_t uy = static_cast<uint32_t>(y) & kMaxIntShiftValue; 2941 return static_cast<int32_t>(ux >> uy); 2942 } 2943 2944 int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE { 2945 uint64_t ux = static_cast<uint64_t>(x); 2946 uint64_t uy = static_cast<uint64_t>(y) & kMaxLongShiftValue; 2947 return static_cast<int64_t>(ux >> uy); 2948 } 2949 2950 DECLARE_INSTRUCTION(UShr); 2951 2952 private: 2953 DISALLOW_COPY_AND_ASSIGN(HUShr); 2954}; 2955 2956class HAnd : public HBinaryOperation { 2957 public: 2958 HAnd(Primitive::Type result_type, HInstruction* left, HInstruction* right) 2959 : HBinaryOperation(result_type, left, right) {} 2960 2961 bool IsCommutative() const OVERRIDE { return true; } 2962 2963 int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE { return x & y; } 2964 int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE { return x & y; } 2965 2966 DECLARE_INSTRUCTION(And); 2967 2968 private: 2969 DISALLOW_COPY_AND_ASSIGN(HAnd); 2970}; 2971 2972class HOr : public HBinaryOperation { 2973 public: 2974 HOr(Primitive::Type result_type, HInstruction* left, HInstruction* right) 2975 : HBinaryOperation(result_type, left, right) {} 2976 2977 bool IsCommutative() const OVERRIDE { return true; } 2978 2979 int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE { return x | y; } 2980 int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE { return x | y; } 2981 2982 DECLARE_INSTRUCTION(Or); 2983 2984 private: 2985 DISALLOW_COPY_AND_ASSIGN(HOr); 2986}; 2987 2988class HXor : public HBinaryOperation { 2989 public: 2990 HXor(Primitive::Type result_type, HInstruction* left, HInstruction* right) 2991 : HBinaryOperation(result_type, left, right) {} 2992 2993 bool IsCommutative() const OVERRIDE { return true; } 2994 2995 int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE { return x ^ y; } 2996 int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE { return x ^ y; } 2997 2998 DECLARE_INSTRUCTION(Xor); 2999 3000 private: 3001 DISALLOW_COPY_AND_ASSIGN(HXor); 3002}; 3003 3004// The value of a parameter in this method. Its location depends on 3005// the calling convention. 3006class HParameterValue : public HExpression<0> { 3007 public: 3008 HParameterValue(uint8_t index, Primitive::Type parameter_type, bool is_this = false) 3009 : HExpression(parameter_type, SideEffects::None()), index_(index), is_this_(is_this) {} 3010 3011 uint8_t GetIndex() const { return index_; } 3012 3013 bool CanBeNull() const OVERRIDE { return !is_this_; } 3014 3015 bool IsThis() const { return is_this_; } 3016 3017 DECLARE_INSTRUCTION(ParameterValue); 3018 3019 private: 3020 // The index of this parameter in the parameters list. Must be less 3021 // than HGraph::number_of_in_vregs_. 3022 const uint8_t index_; 3023 3024 // Whether or not the parameter value corresponds to 'this' argument. 3025 const bool is_this_; 3026 3027 DISALLOW_COPY_AND_ASSIGN(HParameterValue); 3028}; 3029 3030class HNot : public HUnaryOperation { 3031 public: 3032 explicit HNot(Primitive::Type result_type, HInstruction* input) 3033 : HUnaryOperation(result_type, input) {} 3034 3035 bool CanBeMoved() const OVERRIDE { return true; } 3036 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 3037 UNUSED(other); 3038 return true; 3039 } 3040 3041 int32_t Evaluate(int32_t x) const OVERRIDE { return ~x; } 3042 int64_t Evaluate(int64_t x) const OVERRIDE { return ~x; } 3043 3044 DECLARE_INSTRUCTION(Not); 3045 3046 private: 3047 DISALLOW_COPY_AND_ASSIGN(HNot); 3048}; 3049 3050class HBooleanNot : public HUnaryOperation { 3051 public: 3052 explicit HBooleanNot(HInstruction* input) 3053 : HUnaryOperation(Primitive::Type::kPrimBoolean, input) {} 3054 3055 bool CanBeMoved() const OVERRIDE { return true; } 3056 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 3057 UNUSED(other); 3058 return true; 3059 } 3060 3061 int32_t Evaluate(int32_t x) const OVERRIDE { 3062 DCHECK(IsUint<1>(x)); 3063 return !x; 3064 } 3065 3066 int64_t Evaluate(int64_t x ATTRIBUTE_UNUSED) const OVERRIDE { 3067 LOG(FATAL) << DebugName() << " cannot be used with 64-bit values"; 3068 UNREACHABLE(); 3069 } 3070 3071 DECLARE_INSTRUCTION(BooleanNot); 3072 3073 private: 3074 DISALLOW_COPY_AND_ASSIGN(HBooleanNot); 3075}; 3076 3077class HTypeConversion : public HExpression<1> { 3078 public: 3079 // Instantiate a type conversion of `input` to `result_type`. 3080 HTypeConversion(Primitive::Type result_type, HInstruction* input, uint32_t dex_pc) 3081 : HExpression(result_type, SideEffects::None()), dex_pc_(dex_pc) { 3082 SetRawInputAt(0, input); 3083 DCHECK_NE(input->GetType(), result_type); 3084 } 3085 3086 HInstruction* GetInput() const { return InputAt(0); } 3087 Primitive::Type GetInputType() const { return GetInput()->GetType(); } 3088 Primitive::Type GetResultType() const { return GetType(); } 3089 3090 // Required by the x86 and ARM code generators when producing calls 3091 // to the runtime. 3092 uint32_t GetDexPc() const OVERRIDE { return dex_pc_; } 3093 3094 bool CanBeMoved() const OVERRIDE { return true; } 3095 bool InstructionDataEquals(HInstruction* other ATTRIBUTE_UNUSED) const OVERRIDE { return true; } 3096 3097 // Try to statically evaluate the conversion and return a HConstant 3098 // containing the result. If the input cannot be converted, return nullptr. 3099 HConstant* TryStaticEvaluation() const; 3100 3101 DECLARE_INSTRUCTION(TypeConversion); 3102 3103 private: 3104 const uint32_t dex_pc_; 3105 3106 DISALLOW_COPY_AND_ASSIGN(HTypeConversion); 3107}; 3108 3109static constexpr uint32_t kNoRegNumber = -1; 3110 3111class HPhi : public HInstruction { 3112 public: 3113 HPhi(ArenaAllocator* arena, uint32_t reg_number, size_t number_of_inputs, Primitive::Type type) 3114 : HInstruction(SideEffects::None()), 3115 inputs_(arena, number_of_inputs), 3116 reg_number_(reg_number), 3117 type_(type), 3118 is_live_(false), 3119 can_be_null_(true) { 3120 inputs_.SetSize(number_of_inputs); 3121 } 3122 3123 // Returns a type equivalent to the given `type`, but that a `HPhi` can hold. 3124 static Primitive::Type ToPhiType(Primitive::Type type) { 3125 switch (type) { 3126 case Primitive::kPrimBoolean: 3127 case Primitive::kPrimByte: 3128 case Primitive::kPrimShort: 3129 case Primitive::kPrimChar: 3130 return Primitive::kPrimInt; 3131 default: 3132 return type; 3133 } 3134 } 3135 3136 size_t InputCount() const OVERRIDE { return inputs_.Size(); } 3137 3138 void AddInput(HInstruction* input); 3139 void RemoveInputAt(size_t index); 3140 3141 Primitive::Type GetType() const OVERRIDE { return type_; } 3142 void SetType(Primitive::Type type) { type_ = type; } 3143 3144 bool CanBeNull() const OVERRIDE { return can_be_null_; } 3145 void SetCanBeNull(bool can_be_null) { can_be_null_ = can_be_null; } 3146 3147 uint32_t GetRegNumber() const { return reg_number_; } 3148 3149 void SetDead() { is_live_ = false; } 3150 void SetLive() { is_live_ = true; } 3151 bool IsDead() const { return !is_live_; } 3152 bool IsLive() const { return is_live_; } 3153 3154 // Returns the next equivalent phi (starting from the current one) or null if there is none. 3155 // An equivalent phi is a phi having the same dex register and type. 3156 // It assumes that phis with the same dex register are adjacent. 3157 HPhi* GetNextEquivalentPhiWithSameType() { 3158 HInstruction* next = GetNext(); 3159 while (next != nullptr && next->AsPhi()->GetRegNumber() == reg_number_) { 3160 if (next->GetType() == GetType()) { 3161 return next->AsPhi(); 3162 } 3163 next = next->GetNext(); 3164 } 3165 return nullptr; 3166 } 3167 3168 DECLARE_INSTRUCTION(Phi); 3169 3170 protected: 3171 const HUserRecord<HInstruction*> InputRecordAt(size_t i) const OVERRIDE { return inputs_.Get(i); } 3172 3173 void SetRawInputRecordAt(size_t index, const HUserRecord<HInstruction*>& input) OVERRIDE { 3174 inputs_.Put(index, input); 3175 } 3176 3177 private: 3178 GrowableArray<HUserRecord<HInstruction*> > inputs_; 3179 const uint32_t reg_number_; 3180 Primitive::Type type_; 3181 bool is_live_; 3182 bool can_be_null_; 3183 3184 DISALLOW_COPY_AND_ASSIGN(HPhi); 3185}; 3186 3187class HNullCheck : public HExpression<1> { 3188 public: 3189 HNullCheck(HInstruction* value, uint32_t dex_pc) 3190 : HExpression(value->GetType(), SideEffects::None()), dex_pc_(dex_pc) { 3191 SetRawInputAt(0, value); 3192 } 3193 3194 bool CanBeMoved() const OVERRIDE { return true; } 3195 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 3196 UNUSED(other); 3197 return true; 3198 } 3199 3200 bool NeedsEnvironment() const OVERRIDE { return true; } 3201 3202 bool CanThrow() const OVERRIDE { return true; } 3203 3204 bool CanBeNull() const OVERRIDE { return false; } 3205 3206 uint32_t GetDexPc() const OVERRIDE { return dex_pc_; } 3207 3208 DECLARE_INSTRUCTION(NullCheck); 3209 3210 private: 3211 const uint32_t dex_pc_; 3212 3213 DISALLOW_COPY_AND_ASSIGN(HNullCheck); 3214}; 3215 3216class FieldInfo : public ValueObject { 3217 public: 3218 FieldInfo(MemberOffset field_offset, 3219 Primitive::Type field_type, 3220 bool is_volatile, 3221 uint32_t index, 3222 const DexFile& dex_file) 3223 : field_offset_(field_offset), 3224 field_type_(field_type), 3225 is_volatile_(is_volatile), 3226 index_(index), 3227 dex_file_(dex_file) {} 3228 3229 MemberOffset GetFieldOffset() const { return field_offset_; } 3230 Primitive::Type GetFieldType() const { return field_type_; } 3231 uint32_t GetFieldIndex() const { return index_; } 3232 const DexFile& GetDexFile() const { return dex_file_; } 3233 bool IsVolatile() const { return is_volatile_; } 3234 3235 private: 3236 const MemberOffset field_offset_; 3237 const Primitive::Type field_type_; 3238 const bool is_volatile_; 3239 uint32_t index_; 3240 const DexFile& dex_file_; 3241}; 3242 3243class HInstanceFieldGet : public HExpression<1> { 3244 public: 3245 HInstanceFieldGet(HInstruction* value, 3246 Primitive::Type field_type, 3247 MemberOffset field_offset, 3248 bool is_volatile, 3249 uint32_t field_idx, 3250 const DexFile& dex_file) 3251 : HExpression(field_type, SideEffects::DependsOnSomething()), 3252 field_info_(field_offset, field_type, is_volatile, field_idx, dex_file) { 3253 SetRawInputAt(0, value); 3254 } 3255 3256 bool CanBeMoved() const OVERRIDE { return !IsVolatile(); } 3257 3258 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 3259 HInstanceFieldGet* other_get = other->AsInstanceFieldGet(); 3260 return GetFieldOffset().SizeValue() == other_get->GetFieldOffset().SizeValue(); 3261 } 3262 3263 bool CanDoImplicitNullCheckOn(HInstruction* obj) const OVERRIDE { 3264 return (obj == InputAt(0)) && GetFieldOffset().Uint32Value() < kPageSize; 3265 } 3266 3267 size_t ComputeHashCode() const OVERRIDE { 3268 return (HInstruction::ComputeHashCode() << 7) | GetFieldOffset().SizeValue(); 3269 } 3270 3271 const FieldInfo& GetFieldInfo() const { return field_info_; } 3272 MemberOffset GetFieldOffset() const { return field_info_.GetFieldOffset(); } 3273 Primitive::Type GetFieldType() const { return field_info_.GetFieldType(); } 3274 bool IsVolatile() const { return field_info_.IsVolatile(); } 3275 3276 DECLARE_INSTRUCTION(InstanceFieldGet); 3277 3278 private: 3279 const FieldInfo field_info_; 3280 3281 DISALLOW_COPY_AND_ASSIGN(HInstanceFieldGet); 3282}; 3283 3284class HInstanceFieldSet : public HTemplateInstruction<2> { 3285 public: 3286 HInstanceFieldSet(HInstruction* object, 3287 HInstruction* value, 3288 Primitive::Type field_type, 3289 MemberOffset field_offset, 3290 bool is_volatile, 3291 uint32_t field_idx, 3292 const DexFile& dex_file) 3293 : HTemplateInstruction(SideEffects::ChangesSomething()), 3294 field_info_(field_offset, field_type, is_volatile, field_idx, dex_file), 3295 value_can_be_null_(true) { 3296 SetRawInputAt(0, object); 3297 SetRawInputAt(1, value); 3298 } 3299 3300 bool CanDoImplicitNullCheckOn(HInstruction* obj) const OVERRIDE { 3301 return (obj == InputAt(0)) && GetFieldOffset().Uint32Value() < kPageSize; 3302 } 3303 3304 const FieldInfo& GetFieldInfo() const { return field_info_; } 3305 MemberOffset GetFieldOffset() const { return field_info_.GetFieldOffset(); } 3306 Primitive::Type GetFieldType() const { return field_info_.GetFieldType(); } 3307 bool IsVolatile() const { return field_info_.IsVolatile(); } 3308 HInstruction* GetValue() const { return InputAt(1); } 3309 bool GetValueCanBeNull() const { return value_can_be_null_; } 3310 void ClearValueCanBeNull() { value_can_be_null_ = false; } 3311 3312 DECLARE_INSTRUCTION(InstanceFieldSet); 3313 3314 private: 3315 const FieldInfo field_info_; 3316 bool value_can_be_null_; 3317 3318 DISALLOW_COPY_AND_ASSIGN(HInstanceFieldSet); 3319}; 3320 3321class HArrayGet : public HExpression<2> { 3322 public: 3323 HArrayGet(HInstruction* array, HInstruction* index, Primitive::Type type) 3324 : HExpression(type, SideEffects::DependsOnSomething()) { 3325 SetRawInputAt(0, array); 3326 SetRawInputAt(1, index); 3327 } 3328 3329 bool CanBeMoved() const OVERRIDE { return true; } 3330 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 3331 UNUSED(other); 3332 return true; 3333 } 3334 bool CanDoImplicitNullCheckOn(HInstruction* obj) const OVERRIDE { 3335 UNUSED(obj); 3336 // TODO: We can be smarter here. 3337 // Currently, the array access is always preceded by an ArrayLength or a NullCheck 3338 // which generates the implicit null check. There are cases when these can be removed 3339 // to produce better code. If we ever add optimizations to do so we should allow an 3340 // implicit check here (as long as the address falls in the first page). 3341 return false; 3342 } 3343 3344 void SetType(Primitive::Type type) { type_ = type; } 3345 3346 HInstruction* GetArray() const { return InputAt(0); } 3347 HInstruction* GetIndex() const { return InputAt(1); } 3348 3349 DECLARE_INSTRUCTION(ArrayGet); 3350 3351 private: 3352 DISALLOW_COPY_AND_ASSIGN(HArrayGet); 3353}; 3354 3355class HArraySet : public HTemplateInstruction<3> { 3356 public: 3357 HArraySet(HInstruction* array, 3358 HInstruction* index, 3359 HInstruction* value, 3360 Primitive::Type expected_component_type, 3361 uint32_t dex_pc) 3362 : HTemplateInstruction(SideEffects::ChangesSomething()), 3363 dex_pc_(dex_pc), 3364 expected_component_type_(expected_component_type), 3365 needs_type_check_(value->GetType() == Primitive::kPrimNot), 3366 value_can_be_null_(true) { 3367 SetRawInputAt(0, array); 3368 SetRawInputAt(1, index); 3369 SetRawInputAt(2, value); 3370 } 3371 3372 bool NeedsEnvironment() const OVERRIDE { 3373 // We currently always call a runtime method to catch array store 3374 // exceptions. 3375 return needs_type_check_; 3376 } 3377 3378 // Can throw ArrayStoreException. 3379 bool CanThrow() const OVERRIDE { return needs_type_check_; } 3380 3381 bool CanDoImplicitNullCheckOn(HInstruction* obj) const OVERRIDE { 3382 UNUSED(obj); 3383 // TODO: Same as for ArrayGet. 3384 return false; 3385 } 3386 3387 void ClearNeedsTypeCheck() { 3388 needs_type_check_ = false; 3389 } 3390 3391 void ClearValueCanBeNull() { 3392 value_can_be_null_ = false; 3393 } 3394 3395 bool GetValueCanBeNull() const { return value_can_be_null_; } 3396 bool NeedsTypeCheck() const { return needs_type_check_; } 3397 3398 uint32_t GetDexPc() const OVERRIDE { return dex_pc_; } 3399 3400 HInstruction* GetArray() const { return InputAt(0); } 3401 HInstruction* GetIndex() const { return InputAt(1); } 3402 HInstruction* GetValue() const { return InputAt(2); } 3403 3404 Primitive::Type GetComponentType() const { 3405 // The Dex format does not type floating point index operations. Since the 3406 // `expected_component_type_` is set during building and can therefore not 3407 // be correct, we also check what is the value type. If it is a floating 3408 // point type, we must use that type. 3409 Primitive::Type value_type = GetValue()->GetType(); 3410 return ((value_type == Primitive::kPrimFloat) || (value_type == Primitive::kPrimDouble)) 3411 ? value_type 3412 : expected_component_type_; 3413 } 3414 3415 DECLARE_INSTRUCTION(ArraySet); 3416 3417 private: 3418 const uint32_t dex_pc_; 3419 const Primitive::Type expected_component_type_; 3420 bool needs_type_check_; 3421 bool value_can_be_null_; 3422 3423 DISALLOW_COPY_AND_ASSIGN(HArraySet); 3424}; 3425 3426class HArrayLength : public HExpression<1> { 3427 public: 3428 explicit HArrayLength(HInstruction* array) 3429 : HExpression(Primitive::kPrimInt, SideEffects::None()) { 3430 // Note that arrays do not change length, so the instruction does not 3431 // depend on any write. 3432 SetRawInputAt(0, array); 3433 } 3434 3435 bool CanBeMoved() const OVERRIDE { return true; } 3436 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 3437 UNUSED(other); 3438 return true; 3439 } 3440 bool CanDoImplicitNullCheckOn(HInstruction* obj) const OVERRIDE { 3441 return obj == InputAt(0); 3442 } 3443 3444 DECLARE_INSTRUCTION(ArrayLength); 3445 3446 private: 3447 DISALLOW_COPY_AND_ASSIGN(HArrayLength); 3448}; 3449 3450class HBoundsCheck : public HExpression<2> { 3451 public: 3452 HBoundsCheck(HInstruction* index, HInstruction* length, uint32_t dex_pc) 3453 : HExpression(index->GetType(), SideEffects::None()), dex_pc_(dex_pc) { 3454 DCHECK(index->GetType() == Primitive::kPrimInt); 3455 SetRawInputAt(0, index); 3456 SetRawInputAt(1, length); 3457 } 3458 3459 bool CanBeMoved() const OVERRIDE { return true; } 3460 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 3461 UNUSED(other); 3462 return true; 3463 } 3464 3465 bool NeedsEnvironment() const OVERRIDE { return true; } 3466 3467 bool CanThrow() const OVERRIDE { return true; } 3468 3469 uint32_t GetDexPc() const OVERRIDE { return dex_pc_; } 3470 3471 DECLARE_INSTRUCTION(BoundsCheck); 3472 3473 private: 3474 const uint32_t dex_pc_; 3475 3476 DISALLOW_COPY_AND_ASSIGN(HBoundsCheck); 3477}; 3478 3479/** 3480 * Some DEX instructions are folded into multiple HInstructions that need 3481 * to stay live until the last HInstruction. This class 3482 * is used as a marker for the baseline compiler to ensure its preceding 3483 * HInstruction stays live. `index` represents the stack location index of the 3484 * instruction (the actual offset is computed as index * vreg_size). 3485 */ 3486class HTemporary : public HTemplateInstruction<0> { 3487 public: 3488 explicit HTemporary(size_t index) : HTemplateInstruction(SideEffects::None()), index_(index) {} 3489 3490 size_t GetIndex() const { return index_; } 3491 3492 Primitive::Type GetType() const OVERRIDE { 3493 // The previous instruction is the one that will be stored in the temporary location. 3494 DCHECK(GetPrevious() != nullptr); 3495 return GetPrevious()->GetType(); 3496 } 3497 3498 DECLARE_INSTRUCTION(Temporary); 3499 3500 private: 3501 const size_t index_; 3502 3503 DISALLOW_COPY_AND_ASSIGN(HTemporary); 3504}; 3505 3506class HSuspendCheck : public HTemplateInstruction<0> { 3507 public: 3508 explicit HSuspendCheck(uint32_t dex_pc) 3509 : HTemplateInstruction(SideEffects::None()), dex_pc_(dex_pc), slow_path_(nullptr) {} 3510 3511 bool NeedsEnvironment() const OVERRIDE { 3512 return true; 3513 } 3514 3515 uint32_t GetDexPc() const OVERRIDE { return dex_pc_; } 3516 void SetSlowPath(SlowPathCode* slow_path) { slow_path_ = slow_path; } 3517 SlowPathCode* GetSlowPath() const { return slow_path_; } 3518 3519 DECLARE_INSTRUCTION(SuspendCheck); 3520 3521 private: 3522 const uint32_t dex_pc_; 3523 3524 // Only used for code generation, in order to share the same slow path between back edges 3525 // of a same loop. 3526 SlowPathCode* slow_path_; 3527 3528 DISALLOW_COPY_AND_ASSIGN(HSuspendCheck); 3529}; 3530 3531/** 3532 * Instruction to load a Class object. 3533 */ 3534class HLoadClass : public HExpression<1> { 3535 public: 3536 HLoadClass(HCurrentMethod* current_method, 3537 uint16_t type_index, 3538 const DexFile& dex_file, 3539 bool is_referrers_class, 3540 uint32_t dex_pc) 3541 : HExpression(Primitive::kPrimNot, SideEffects::None()), 3542 type_index_(type_index), 3543 dex_file_(dex_file), 3544 is_referrers_class_(is_referrers_class), 3545 dex_pc_(dex_pc), 3546 generate_clinit_check_(false), 3547 loaded_class_rti_(ReferenceTypeInfo::CreateTop(/* is_exact */ false)) { 3548 SetRawInputAt(0, current_method); 3549 } 3550 3551 bool CanBeMoved() const OVERRIDE { return true; } 3552 3553 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 3554 return other->AsLoadClass()->type_index_ == type_index_; 3555 } 3556 3557 size_t ComputeHashCode() const OVERRIDE { return type_index_; } 3558 3559 uint32_t GetDexPc() const OVERRIDE { return dex_pc_; } 3560 uint16_t GetTypeIndex() const { return type_index_; } 3561 bool IsReferrersClass() const { return is_referrers_class_; } 3562 3563 bool NeedsEnvironment() const OVERRIDE { 3564 // Will call runtime and load the class if the class is not loaded yet. 3565 // TODO: finer grain decision. 3566 return !is_referrers_class_; 3567 } 3568 3569 bool MustGenerateClinitCheck() const { 3570 return generate_clinit_check_; 3571 } 3572 3573 void SetMustGenerateClinitCheck(bool generate_clinit_check) { 3574 generate_clinit_check_ = generate_clinit_check; 3575 } 3576 3577 bool CanCallRuntime() const { 3578 return MustGenerateClinitCheck() || !is_referrers_class_; 3579 } 3580 3581 bool CanThrow() const OVERRIDE { 3582 // May call runtime and and therefore can throw. 3583 // TODO: finer grain decision. 3584 return !is_referrers_class_; 3585 } 3586 3587 ReferenceTypeInfo GetLoadedClassRTI() { 3588 return loaded_class_rti_; 3589 } 3590 3591 void SetLoadedClassRTI(ReferenceTypeInfo rti) { 3592 // Make sure we only set exact types (the loaded class should never be merged). 3593 DCHECK(rti.IsExact()); 3594 loaded_class_rti_ = rti; 3595 } 3596 3597 bool IsResolved() { 3598 return loaded_class_rti_.IsExact(); 3599 } 3600 3601 const DexFile& GetDexFile() { return dex_file_; } 3602 3603 bool NeedsDexCache() const OVERRIDE { return !is_referrers_class_; } 3604 3605 DECLARE_INSTRUCTION(LoadClass); 3606 3607 private: 3608 const uint16_t type_index_; 3609 const DexFile& dex_file_; 3610 const bool is_referrers_class_; 3611 const uint32_t dex_pc_; 3612 // Whether this instruction must generate the initialization check. 3613 // Used for code generation. 3614 bool generate_clinit_check_; 3615 3616 ReferenceTypeInfo loaded_class_rti_; 3617 3618 DISALLOW_COPY_AND_ASSIGN(HLoadClass); 3619}; 3620 3621class HLoadString : public HExpression<1> { 3622 public: 3623 HLoadString(HCurrentMethod* current_method, uint32_t string_index, uint32_t dex_pc) 3624 : HExpression(Primitive::kPrimNot, SideEffects::None()), 3625 string_index_(string_index), 3626 dex_pc_(dex_pc) { 3627 SetRawInputAt(0, current_method); 3628 } 3629 3630 bool CanBeMoved() const OVERRIDE { return true; } 3631 3632 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 3633 return other->AsLoadString()->string_index_ == string_index_; 3634 } 3635 3636 size_t ComputeHashCode() const OVERRIDE { return string_index_; } 3637 3638 uint32_t GetDexPc() const OVERRIDE { return dex_pc_; } 3639 uint32_t GetStringIndex() const { return string_index_; } 3640 3641 // TODO: Can we deopt or debug when we resolve a string? 3642 bool NeedsEnvironment() const OVERRIDE { return false; } 3643 bool NeedsDexCache() const OVERRIDE { return true; } 3644 3645 DECLARE_INSTRUCTION(LoadString); 3646 3647 private: 3648 const uint32_t string_index_; 3649 const uint32_t dex_pc_; 3650 3651 DISALLOW_COPY_AND_ASSIGN(HLoadString); 3652}; 3653 3654/** 3655 * Performs an initialization check on its Class object input. 3656 */ 3657class HClinitCheck : public HExpression<1> { 3658 public: 3659 explicit HClinitCheck(HLoadClass* constant, uint32_t dex_pc) 3660 : HExpression(Primitive::kPrimNot, SideEffects::ChangesSomething()), 3661 dex_pc_(dex_pc) { 3662 SetRawInputAt(0, constant); 3663 } 3664 3665 bool CanBeMoved() const OVERRIDE { return true; } 3666 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 3667 UNUSED(other); 3668 return true; 3669 } 3670 3671 bool NeedsEnvironment() const OVERRIDE { 3672 // May call runtime to initialize the class. 3673 return true; 3674 } 3675 3676 uint32_t GetDexPc() const OVERRIDE { return dex_pc_; } 3677 3678 HLoadClass* GetLoadClass() const { return InputAt(0)->AsLoadClass(); } 3679 3680 DECLARE_INSTRUCTION(ClinitCheck); 3681 3682 private: 3683 const uint32_t dex_pc_; 3684 3685 DISALLOW_COPY_AND_ASSIGN(HClinitCheck); 3686}; 3687 3688class HStaticFieldGet : public HExpression<1> { 3689 public: 3690 HStaticFieldGet(HInstruction* cls, 3691 Primitive::Type field_type, 3692 MemberOffset field_offset, 3693 bool is_volatile, 3694 uint32_t field_idx, 3695 const DexFile& dex_file) 3696 : HExpression(field_type, SideEffects::DependsOnSomething()), 3697 field_info_(field_offset, field_type, is_volatile, field_idx, dex_file) { 3698 SetRawInputAt(0, cls); 3699 } 3700 3701 3702 bool CanBeMoved() const OVERRIDE { return !IsVolatile(); } 3703 3704 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 3705 HStaticFieldGet* other_get = other->AsStaticFieldGet(); 3706 return GetFieldOffset().SizeValue() == other_get->GetFieldOffset().SizeValue(); 3707 } 3708 3709 size_t ComputeHashCode() const OVERRIDE { 3710 return (HInstruction::ComputeHashCode() << 7) | GetFieldOffset().SizeValue(); 3711 } 3712 3713 const FieldInfo& GetFieldInfo() const { return field_info_; } 3714 MemberOffset GetFieldOffset() const { return field_info_.GetFieldOffset(); } 3715 Primitive::Type GetFieldType() const { return field_info_.GetFieldType(); } 3716 bool IsVolatile() const { return field_info_.IsVolatile(); } 3717 3718 DECLARE_INSTRUCTION(StaticFieldGet); 3719 3720 private: 3721 const FieldInfo field_info_; 3722 3723 DISALLOW_COPY_AND_ASSIGN(HStaticFieldGet); 3724}; 3725 3726class HStaticFieldSet : public HTemplateInstruction<2> { 3727 public: 3728 HStaticFieldSet(HInstruction* cls, 3729 HInstruction* value, 3730 Primitive::Type field_type, 3731 MemberOffset field_offset, 3732 bool is_volatile, 3733 uint32_t field_idx, 3734 const DexFile& dex_file) 3735 : HTemplateInstruction(SideEffects::ChangesSomething()), 3736 field_info_(field_offset, field_type, is_volatile, field_idx, dex_file), 3737 value_can_be_null_(true) { 3738 SetRawInputAt(0, cls); 3739 SetRawInputAt(1, value); 3740 } 3741 3742 const FieldInfo& GetFieldInfo() const { return field_info_; } 3743 MemberOffset GetFieldOffset() const { return field_info_.GetFieldOffset(); } 3744 Primitive::Type GetFieldType() const { return field_info_.GetFieldType(); } 3745 bool IsVolatile() const { return field_info_.IsVolatile(); } 3746 3747 HInstruction* GetValue() const { return InputAt(1); } 3748 bool GetValueCanBeNull() const { return value_can_be_null_; } 3749 void ClearValueCanBeNull() { value_can_be_null_ = false; } 3750 3751 DECLARE_INSTRUCTION(StaticFieldSet); 3752 3753 private: 3754 const FieldInfo field_info_; 3755 bool value_can_be_null_; 3756 3757 DISALLOW_COPY_AND_ASSIGN(HStaticFieldSet); 3758}; 3759 3760// Implement the move-exception DEX instruction. 3761class HLoadException : public HExpression<0> { 3762 public: 3763 HLoadException() : HExpression(Primitive::kPrimNot, SideEffects::None()) {} 3764 3765 DECLARE_INSTRUCTION(LoadException); 3766 3767 private: 3768 DISALLOW_COPY_AND_ASSIGN(HLoadException); 3769}; 3770 3771class HThrow : public HTemplateInstruction<1> { 3772 public: 3773 HThrow(HInstruction* exception, uint32_t dex_pc) 3774 : HTemplateInstruction(SideEffects::None()), dex_pc_(dex_pc) { 3775 SetRawInputAt(0, exception); 3776 } 3777 3778 bool IsControlFlow() const OVERRIDE { return true; } 3779 3780 bool NeedsEnvironment() const OVERRIDE { return true; } 3781 3782 bool CanThrow() const OVERRIDE { return true; } 3783 3784 uint32_t GetDexPc() const OVERRIDE { return dex_pc_; } 3785 3786 DECLARE_INSTRUCTION(Throw); 3787 3788 private: 3789 const uint32_t dex_pc_; 3790 3791 DISALLOW_COPY_AND_ASSIGN(HThrow); 3792}; 3793 3794class HInstanceOf : public HExpression<2> { 3795 public: 3796 HInstanceOf(HInstruction* object, 3797 HLoadClass* constant, 3798 bool class_is_final, 3799 uint32_t dex_pc) 3800 : HExpression(Primitive::kPrimBoolean, SideEffects::None()), 3801 class_is_final_(class_is_final), 3802 must_do_null_check_(true), 3803 dex_pc_(dex_pc) { 3804 SetRawInputAt(0, object); 3805 SetRawInputAt(1, constant); 3806 } 3807 3808 bool CanBeMoved() const OVERRIDE { return true; } 3809 3810 bool InstructionDataEquals(HInstruction* other ATTRIBUTE_UNUSED) const OVERRIDE { 3811 return true; 3812 } 3813 3814 bool NeedsEnvironment() const OVERRIDE { 3815 return false; 3816 } 3817 3818 uint32_t GetDexPc() const OVERRIDE { return dex_pc_; } 3819 3820 bool IsClassFinal() const { return class_is_final_; } 3821 3822 // Used only in code generation. 3823 bool MustDoNullCheck() const { return must_do_null_check_; } 3824 void ClearMustDoNullCheck() { must_do_null_check_ = false; } 3825 3826 DECLARE_INSTRUCTION(InstanceOf); 3827 3828 private: 3829 const bool class_is_final_; 3830 bool must_do_null_check_; 3831 const uint32_t dex_pc_; 3832 3833 DISALLOW_COPY_AND_ASSIGN(HInstanceOf); 3834}; 3835 3836class HBoundType : public HExpression<1> { 3837 public: 3838 HBoundType(HInstruction* input, ReferenceTypeInfo bound_type) 3839 : HExpression(Primitive::kPrimNot, SideEffects::None()), 3840 bound_type_(bound_type) { 3841 DCHECK_EQ(input->GetType(), Primitive::kPrimNot); 3842 SetRawInputAt(0, input); 3843 } 3844 3845 const ReferenceTypeInfo& GetBoundType() const { return bound_type_; } 3846 3847 bool CanBeNull() const OVERRIDE { 3848 // `null instanceof ClassX` always return false so we can't be null. 3849 return false; 3850 } 3851 3852 DECLARE_INSTRUCTION(BoundType); 3853 3854 private: 3855 // Encodes the most upper class that this instruction can have. In other words 3856 // it is always the case that GetBoundType().IsSupertypeOf(GetReferenceType()). 3857 // It is used to bound the type in cases like `if (x instanceof ClassX) {}` 3858 const ReferenceTypeInfo bound_type_; 3859 3860 DISALLOW_COPY_AND_ASSIGN(HBoundType); 3861}; 3862 3863class HCheckCast : public HTemplateInstruction<2> { 3864 public: 3865 HCheckCast(HInstruction* object, 3866 HLoadClass* constant, 3867 bool class_is_final, 3868 uint32_t dex_pc) 3869 : HTemplateInstruction(SideEffects::None()), 3870 class_is_final_(class_is_final), 3871 must_do_null_check_(true), 3872 dex_pc_(dex_pc) { 3873 SetRawInputAt(0, object); 3874 SetRawInputAt(1, constant); 3875 } 3876 3877 bool CanBeMoved() const OVERRIDE { return true; } 3878 3879 bool InstructionDataEquals(HInstruction* other ATTRIBUTE_UNUSED) const OVERRIDE { 3880 return true; 3881 } 3882 3883 bool NeedsEnvironment() const OVERRIDE { 3884 // Instruction may throw a CheckCastError. 3885 return true; 3886 } 3887 3888 bool CanThrow() const OVERRIDE { return true; } 3889 3890 bool MustDoNullCheck() const { return must_do_null_check_; } 3891 void ClearMustDoNullCheck() { must_do_null_check_ = false; } 3892 3893 uint32_t GetDexPc() const OVERRIDE { return dex_pc_; } 3894 3895 bool IsClassFinal() const { return class_is_final_; } 3896 3897 DECLARE_INSTRUCTION(CheckCast); 3898 3899 private: 3900 const bool class_is_final_; 3901 bool must_do_null_check_; 3902 const uint32_t dex_pc_; 3903 3904 DISALLOW_COPY_AND_ASSIGN(HCheckCast); 3905}; 3906 3907class HMemoryBarrier : public HTemplateInstruction<0> { 3908 public: 3909 explicit HMemoryBarrier(MemBarrierKind barrier_kind) 3910 : HTemplateInstruction(SideEffects::None()), 3911 barrier_kind_(barrier_kind) {} 3912 3913 MemBarrierKind GetBarrierKind() { return barrier_kind_; } 3914 3915 DECLARE_INSTRUCTION(MemoryBarrier); 3916 3917 private: 3918 const MemBarrierKind barrier_kind_; 3919 3920 DISALLOW_COPY_AND_ASSIGN(HMemoryBarrier); 3921}; 3922 3923class HMonitorOperation : public HTemplateInstruction<1> { 3924 public: 3925 enum OperationKind { 3926 kEnter, 3927 kExit, 3928 }; 3929 3930 HMonitorOperation(HInstruction* object, OperationKind kind, uint32_t dex_pc) 3931 : HTemplateInstruction(SideEffects::None()), kind_(kind), dex_pc_(dex_pc) { 3932 SetRawInputAt(0, object); 3933 } 3934 3935 // Instruction may throw a Java exception, so we need an environment. 3936 bool NeedsEnvironment() const OVERRIDE { return true; } 3937 bool CanThrow() const OVERRIDE { return true; } 3938 3939 uint32_t GetDexPc() const OVERRIDE { return dex_pc_; } 3940 3941 bool IsEnter() const { return kind_ == kEnter; } 3942 3943 DECLARE_INSTRUCTION(MonitorOperation); 3944 3945 private: 3946 const OperationKind kind_; 3947 const uint32_t dex_pc_; 3948 3949 private: 3950 DISALLOW_COPY_AND_ASSIGN(HMonitorOperation); 3951}; 3952 3953class MoveOperands : public ArenaObject<kArenaAllocMisc> { 3954 public: 3955 MoveOperands(Location source, 3956 Location destination, 3957 Primitive::Type type, 3958 HInstruction* instruction) 3959 : source_(source), destination_(destination), type_(type), instruction_(instruction) {} 3960 3961 Location GetSource() const { return source_; } 3962 Location GetDestination() const { return destination_; } 3963 3964 void SetSource(Location value) { source_ = value; } 3965 void SetDestination(Location value) { destination_ = value; } 3966 3967 // The parallel move resolver marks moves as "in-progress" by clearing the 3968 // destination (but not the source). 3969 Location MarkPending() { 3970 DCHECK(!IsPending()); 3971 Location dest = destination_; 3972 destination_ = Location::NoLocation(); 3973 return dest; 3974 } 3975 3976 void ClearPending(Location dest) { 3977 DCHECK(IsPending()); 3978 destination_ = dest; 3979 } 3980 3981 bool IsPending() const { 3982 DCHECK(!source_.IsInvalid() || destination_.IsInvalid()); 3983 return destination_.IsInvalid() && !source_.IsInvalid(); 3984 } 3985 3986 // True if this blocks a move from the given location. 3987 bool Blocks(Location loc) const { 3988 return !IsEliminated() && source_.OverlapsWith(loc); 3989 } 3990 3991 // A move is redundant if it's been eliminated, if its source and 3992 // destination are the same, or if its destination is unneeded. 3993 bool IsRedundant() const { 3994 return IsEliminated() || destination_.IsInvalid() || source_.Equals(destination_); 3995 } 3996 3997 // We clear both operands to indicate move that's been eliminated. 3998 void Eliminate() { 3999 source_ = destination_ = Location::NoLocation(); 4000 } 4001 4002 bool IsEliminated() const { 4003 DCHECK(!source_.IsInvalid() || destination_.IsInvalid()); 4004 return source_.IsInvalid(); 4005 } 4006 4007 bool Is64BitMove() const { 4008 return Primitive::Is64BitType(type_); 4009 } 4010 4011 HInstruction* GetInstruction() const { return instruction_; } 4012 4013 private: 4014 Location source_; 4015 Location destination_; 4016 // The type this move is for. 4017 Primitive::Type type_; 4018 // The instruction this move is assocatied with. Null when this move is 4019 // for moving an input in the expected locations of user (including a phi user). 4020 // This is only used in debug mode, to ensure we do not connect interval siblings 4021 // in the same parallel move. 4022 HInstruction* instruction_; 4023}; 4024 4025static constexpr size_t kDefaultNumberOfMoves = 4; 4026 4027class HParallelMove : public HTemplateInstruction<0> { 4028 public: 4029 explicit HParallelMove(ArenaAllocator* arena) 4030 : HTemplateInstruction(SideEffects::None()), moves_(arena, kDefaultNumberOfMoves) {} 4031 4032 void AddMove(Location source, 4033 Location destination, 4034 Primitive::Type type, 4035 HInstruction* instruction) { 4036 DCHECK(source.IsValid()); 4037 DCHECK(destination.IsValid()); 4038 if (kIsDebugBuild) { 4039 if (instruction != nullptr) { 4040 for (size_t i = 0, e = moves_.Size(); i < e; ++i) { 4041 if (moves_.Get(i).GetInstruction() == instruction) { 4042 // Special case the situation where the move is for the spill slot 4043 // of the instruction. 4044 if ((GetPrevious() == instruction) 4045 || ((GetPrevious() == nullptr) 4046 && instruction->IsPhi() 4047 && instruction->GetBlock() == GetBlock())) { 4048 DCHECK_NE(destination.GetKind(), moves_.Get(i).GetDestination().GetKind()) 4049 << "Doing parallel moves for the same instruction."; 4050 } else { 4051 DCHECK(false) << "Doing parallel moves for the same instruction."; 4052 } 4053 } 4054 } 4055 } 4056 for (size_t i = 0, e = moves_.Size(); i < e; ++i) { 4057 DCHECK(!destination.OverlapsWith(moves_.Get(i).GetDestination())) 4058 << "Overlapped destination for two moves in a parallel move: " 4059 << moves_.Get(i).GetSource() << " ==> " << moves_.Get(i).GetDestination() << " and " 4060 << source << " ==> " << destination; 4061 } 4062 } 4063 moves_.Add(MoveOperands(source, destination, type, instruction)); 4064 } 4065 4066 MoveOperands* MoveOperandsAt(size_t index) const { 4067 return moves_.GetRawStorage() + index; 4068 } 4069 4070 size_t NumMoves() const { return moves_.Size(); } 4071 4072 DECLARE_INSTRUCTION(ParallelMove); 4073 4074 private: 4075 GrowableArray<MoveOperands> moves_; 4076 4077 DISALLOW_COPY_AND_ASSIGN(HParallelMove); 4078}; 4079 4080class HGraphVisitor : public ValueObject { 4081 public: 4082 explicit HGraphVisitor(HGraph* graph) : graph_(graph) {} 4083 virtual ~HGraphVisitor() {} 4084 4085 virtual void VisitInstruction(HInstruction* instruction) { UNUSED(instruction); } 4086 virtual void VisitBasicBlock(HBasicBlock* block); 4087 4088 // Visit the graph following basic block insertion order. 4089 void VisitInsertionOrder(); 4090 4091 // Visit the graph following dominator tree reverse post-order. 4092 void VisitReversePostOrder(); 4093 4094 HGraph* GetGraph() const { return graph_; } 4095 4096 // Visit functions for instruction classes. 4097#define DECLARE_VISIT_INSTRUCTION(name, super) \ 4098 virtual void Visit##name(H##name* instr) { VisitInstruction(instr); } 4099 4100 FOR_EACH_INSTRUCTION(DECLARE_VISIT_INSTRUCTION) 4101 4102#undef DECLARE_VISIT_INSTRUCTION 4103 4104 private: 4105 HGraph* const graph_; 4106 4107 DISALLOW_COPY_AND_ASSIGN(HGraphVisitor); 4108}; 4109 4110class HGraphDelegateVisitor : public HGraphVisitor { 4111 public: 4112 explicit HGraphDelegateVisitor(HGraph* graph) : HGraphVisitor(graph) {} 4113 virtual ~HGraphDelegateVisitor() {} 4114 4115 // Visit functions that delegate to to super class. 4116#define DECLARE_VISIT_INSTRUCTION(name, super) \ 4117 void Visit##name(H##name* instr) OVERRIDE { Visit##super(instr); } 4118 4119 FOR_EACH_INSTRUCTION(DECLARE_VISIT_INSTRUCTION) 4120 4121#undef DECLARE_VISIT_INSTRUCTION 4122 4123 private: 4124 DISALLOW_COPY_AND_ASSIGN(HGraphDelegateVisitor); 4125}; 4126 4127class HInsertionOrderIterator : public ValueObject { 4128 public: 4129 explicit HInsertionOrderIterator(const HGraph& graph) : graph_(graph), index_(0) {} 4130 4131 bool Done() const { return index_ == graph_.GetBlocks().Size(); } 4132 HBasicBlock* Current() const { return graph_.GetBlocks().Get(index_); } 4133 void Advance() { ++index_; } 4134 4135 private: 4136 const HGraph& graph_; 4137 size_t index_; 4138 4139 DISALLOW_COPY_AND_ASSIGN(HInsertionOrderIterator); 4140}; 4141 4142class HReversePostOrderIterator : public ValueObject { 4143 public: 4144 explicit HReversePostOrderIterator(const HGraph& graph) : graph_(graph), index_(0) { 4145 // Check that reverse post order of the graph has been built. 4146 DCHECK(!graph.GetReversePostOrder().IsEmpty()); 4147 } 4148 4149 bool Done() const { return index_ == graph_.GetReversePostOrder().Size(); } 4150 HBasicBlock* Current() const { return graph_.GetReversePostOrder().Get(index_); } 4151 void Advance() { ++index_; } 4152 4153 private: 4154 const HGraph& graph_; 4155 size_t index_; 4156 4157 DISALLOW_COPY_AND_ASSIGN(HReversePostOrderIterator); 4158}; 4159 4160class HPostOrderIterator : public ValueObject { 4161 public: 4162 explicit HPostOrderIterator(const HGraph& graph) 4163 : graph_(graph), index_(graph_.GetReversePostOrder().Size()) { 4164 // Check that reverse post order of the graph has been built. 4165 DCHECK(!graph.GetReversePostOrder().IsEmpty()); 4166 } 4167 4168 bool Done() const { return index_ == 0; } 4169 HBasicBlock* Current() const { return graph_.GetReversePostOrder().Get(index_ - 1); } 4170 void Advance() { --index_; } 4171 4172 private: 4173 const HGraph& graph_; 4174 size_t index_; 4175 4176 DISALLOW_COPY_AND_ASSIGN(HPostOrderIterator); 4177}; 4178 4179class HLinearPostOrderIterator : public ValueObject { 4180 public: 4181 explicit HLinearPostOrderIterator(const HGraph& graph) 4182 : order_(graph.GetLinearOrder()), index_(graph.GetLinearOrder().Size()) {} 4183 4184 bool Done() const { return index_ == 0; } 4185 4186 HBasicBlock* Current() const { return order_.Get(index_ -1); } 4187 4188 void Advance() { 4189 --index_; 4190 DCHECK_GE(index_, 0U); 4191 } 4192 4193 private: 4194 const GrowableArray<HBasicBlock*>& order_; 4195 size_t index_; 4196 4197 DISALLOW_COPY_AND_ASSIGN(HLinearPostOrderIterator); 4198}; 4199 4200class HLinearOrderIterator : public ValueObject { 4201 public: 4202 explicit HLinearOrderIterator(const HGraph& graph) 4203 : order_(graph.GetLinearOrder()), index_(0) {} 4204 4205 bool Done() const { return index_ == order_.Size(); } 4206 HBasicBlock* Current() const { return order_.Get(index_); } 4207 void Advance() { ++index_; } 4208 4209 private: 4210 const GrowableArray<HBasicBlock*>& order_; 4211 size_t index_; 4212 4213 DISALLOW_COPY_AND_ASSIGN(HLinearOrderIterator); 4214}; 4215 4216// Iterator over the blocks that art part of the loop. Includes blocks part 4217// of an inner loop. The order in which the blocks are iterated is on their 4218// block id. 4219class HBlocksInLoopIterator : public ValueObject { 4220 public: 4221 explicit HBlocksInLoopIterator(const HLoopInformation& info) 4222 : blocks_in_loop_(info.GetBlocks()), 4223 blocks_(info.GetHeader()->GetGraph()->GetBlocks()), 4224 index_(0) { 4225 if (!blocks_in_loop_.IsBitSet(index_)) { 4226 Advance(); 4227 } 4228 } 4229 4230 bool Done() const { return index_ == blocks_.Size(); } 4231 HBasicBlock* Current() const { return blocks_.Get(index_); } 4232 void Advance() { 4233 ++index_; 4234 for (size_t e = blocks_.Size(); index_ < e; ++index_) { 4235 if (blocks_in_loop_.IsBitSet(index_)) { 4236 break; 4237 } 4238 } 4239 } 4240 4241 private: 4242 const BitVector& blocks_in_loop_; 4243 const GrowableArray<HBasicBlock*>& blocks_; 4244 size_t index_; 4245 4246 DISALLOW_COPY_AND_ASSIGN(HBlocksInLoopIterator); 4247}; 4248 4249inline int64_t Int64FromConstant(HConstant* constant) { 4250 DCHECK(constant->IsIntConstant() || constant->IsLongConstant()); 4251 return constant->IsIntConstant() ? constant->AsIntConstant()->GetValue() 4252 : constant->AsLongConstant()->GetValue(); 4253} 4254 4255} // namespace art 4256 4257#endif // ART_COMPILER_OPTIMIZING_NODES_H_ 4258