nodes.h revision 72bceff11a98cc1ecdb64a6fae16c521f99ec6a7
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 "locations.h" 21#include "offsets.h" 22#include "primitive.h" 23#include "utils/allocation.h" 24#include "utils/arena_bit_vector.h" 25#include "utils/growable_array.h" 26 27namespace art { 28 29class HBasicBlock; 30class HEnvironment; 31class HInstruction; 32class HIntConstant; 33class HGraphVisitor; 34class HPhi; 35class LiveInterval; 36class LocationSummary; 37 38static const int kDefaultNumberOfBlocks = 8; 39static const int kDefaultNumberOfSuccessors = 2; 40static const int kDefaultNumberOfPredecessors = 2; 41static const int kDefaultNumberOfBackEdges = 1; 42 43enum IfCondition { 44 kCondEQ, 45 kCondNE, 46 kCondLT, 47 kCondLE, 48 kCondGT, 49 kCondGE, 50}; 51 52class HInstructionList { 53 public: 54 HInstructionList() : first_instruction_(nullptr), last_instruction_(nullptr) {} 55 56 void AddInstruction(HInstruction* instruction); 57 void RemoveInstruction(HInstruction* instruction); 58 59 // Return true if `instruction1` is found before `instruction2` in 60 // this instruction list and false otherwise. Abort if none 61 // of these instructions is found. 62 bool FoundBefore(const HInstruction* instruction1, 63 const HInstruction* instruction2) const; 64 65 private: 66 HInstruction* first_instruction_; 67 HInstruction* last_instruction_; 68 69 friend class HBasicBlock; 70 friend class HInstructionIterator; 71 friend class HBackwardInstructionIterator; 72 73 DISALLOW_COPY_AND_ASSIGN(HInstructionList); 74}; 75 76// Control-flow graph of a method. Contains a list of basic blocks. 77class HGraph : public ArenaObject { 78 public: 79 explicit HGraph(ArenaAllocator* arena) 80 : arena_(arena), 81 blocks_(arena, kDefaultNumberOfBlocks), 82 reverse_post_order_(arena, kDefaultNumberOfBlocks), 83 maximum_number_of_out_vregs_(0), 84 number_of_vregs_(0), 85 number_of_in_vregs_(0), 86 number_of_temporaries_(0), 87 current_instruction_id_(0) {} 88 89 ArenaAllocator* GetArena() const { return arena_; } 90 const GrowableArray<HBasicBlock*>& GetBlocks() const { return blocks_; } 91 92 HBasicBlock* GetEntryBlock() const { return entry_block_; } 93 HBasicBlock* GetExitBlock() const { return exit_block_; } 94 95 void SetEntryBlock(HBasicBlock* block) { entry_block_ = block; } 96 void SetExitBlock(HBasicBlock* block) { exit_block_ = block; } 97 98 void AddBlock(HBasicBlock* block); 99 100 void BuildDominatorTree(); 101 void TransformToSSA(); 102 void SimplifyCFG(); 103 104 // Find all natural loops in this graph. Aborts computation and returns false 105 // if one loop is not natural, that is the header does not dominate the back 106 // edge. 107 bool FindNaturalLoops() const; 108 109 void SplitCriticalEdge(HBasicBlock* block, HBasicBlock* successor); 110 void SimplifyLoop(HBasicBlock* header); 111 112 int GetNextInstructionId() { 113 return current_instruction_id_++; 114 } 115 116 uint16_t GetMaximumNumberOfOutVRegs() const { 117 return maximum_number_of_out_vregs_; 118 } 119 120 void UpdateMaximumNumberOfOutVRegs(uint16_t new_value) { 121 maximum_number_of_out_vregs_ = std::max(new_value, maximum_number_of_out_vregs_); 122 } 123 124 void UpdateNumberOfTemporaries(size_t count) { 125 number_of_temporaries_ = std::max(count, number_of_temporaries_); 126 } 127 128 size_t GetNumberOfTemporaries() const { 129 return number_of_temporaries_; 130 } 131 132 void SetNumberOfVRegs(uint16_t number_of_vregs) { 133 number_of_vregs_ = number_of_vregs; 134 } 135 136 uint16_t GetNumberOfVRegs() const { 137 return number_of_vregs_; 138 } 139 140 void SetNumberOfInVRegs(uint16_t value) { 141 number_of_in_vregs_ = value; 142 } 143 144 uint16_t GetNumberOfInVRegs() const { 145 return number_of_in_vregs_; 146 } 147 148 uint16_t GetNumberOfLocalVRegs() const { 149 return number_of_vregs_ - number_of_in_vregs_; 150 } 151 152 const GrowableArray<HBasicBlock*>& GetReversePostOrder() const { 153 return reverse_post_order_; 154 } 155 156 private: 157 HBasicBlock* FindCommonDominator(HBasicBlock* first, HBasicBlock* second) const; 158 void VisitBlockForDominatorTree(HBasicBlock* block, 159 HBasicBlock* predecessor, 160 GrowableArray<size_t>* visits); 161 void FindBackEdges(ArenaBitVector* visited); 162 void VisitBlockForBackEdges(HBasicBlock* block, 163 ArenaBitVector* visited, 164 ArenaBitVector* visiting); 165 void RemoveDeadBlocks(const ArenaBitVector& visited) const; 166 167 ArenaAllocator* const arena_; 168 169 // List of blocks in insertion order. 170 GrowableArray<HBasicBlock*> blocks_; 171 172 // List of blocks to perform a reverse post order tree traversal. 173 GrowableArray<HBasicBlock*> reverse_post_order_; 174 175 HBasicBlock* entry_block_; 176 HBasicBlock* exit_block_; 177 178 // The maximum number of virtual registers arguments passed to a HInvoke in this graph. 179 uint16_t maximum_number_of_out_vregs_; 180 181 // The number of virtual registers in this method. Contains the parameters. 182 uint16_t number_of_vregs_; 183 184 // The number of virtual registers used by parameters of this method. 185 uint16_t number_of_in_vregs_; 186 187 // The number of temporaries that will be needed for the baseline compiler. 188 size_t number_of_temporaries_; 189 190 // The current id to assign to a newly added instruction. See HInstruction.id_. 191 int current_instruction_id_; 192 193 DISALLOW_COPY_AND_ASSIGN(HGraph); 194}; 195 196class HLoopInformation : public ArenaObject { 197 public: 198 HLoopInformation(HBasicBlock* header, HGraph* graph) 199 : header_(header), 200 back_edges_(graph->GetArena(), kDefaultNumberOfBackEdges), 201 blocks_(graph->GetArena(), graph->GetBlocks().Size(), false) {} 202 203 HBasicBlock* GetHeader() const { 204 return header_; 205 } 206 207 void AddBackEdge(HBasicBlock* back_edge) { 208 back_edges_.Add(back_edge); 209 } 210 211 void RemoveBackEdge(HBasicBlock* back_edge) { 212 back_edges_.Delete(back_edge); 213 } 214 215 bool IsBackEdge(HBasicBlock* block) { 216 for (size_t i = 0, e = back_edges_.Size(); i < e; ++i) { 217 if (back_edges_.Get(i) == block) return true; 218 } 219 return false; 220 } 221 222 int NumberOfBackEdges() const { 223 return back_edges_.Size(); 224 } 225 226 HBasicBlock* GetPreHeader() const; 227 228 const GrowableArray<HBasicBlock*>& GetBackEdges() const { 229 return back_edges_; 230 } 231 232 void ClearBackEdges() { 233 back_edges_.Reset(); 234 } 235 236 // Find blocks that are part of this loop. Returns whether the loop is a natural loop, 237 // that is the header dominates the back edge. 238 bool Populate(); 239 240 // Returns whether this loop information contains `block`. 241 // Note that this loop information *must* be populated before entering this function. 242 bool Contains(const HBasicBlock& block) const; 243 244 // Returns whether this loop information is an inner loop of `other`. 245 // Note that `other` *must* be populated before entering this function. 246 bool IsIn(const HLoopInformation& other) const; 247 248 const ArenaBitVector& GetBlocks() const { return blocks_; } 249 250 private: 251 // Internal recursive implementation of `Populate`. 252 void PopulateRecursive(HBasicBlock* block); 253 254 HBasicBlock* header_; 255 GrowableArray<HBasicBlock*> back_edges_; 256 ArenaBitVector blocks_; 257 258 DISALLOW_COPY_AND_ASSIGN(HLoopInformation); 259}; 260 261static constexpr size_t kNoLifetime = -1; 262 263// A block in a method. Contains the list of instructions represented 264// as a double linked list. Each block knows its predecessors and 265// successors. 266class HBasicBlock : public ArenaObject { 267 public: 268 explicit HBasicBlock(HGraph* graph) 269 : graph_(graph), 270 predecessors_(graph->GetArena(), kDefaultNumberOfPredecessors), 271 successors_(graph->GetArena(), kDefaultNumberOfSuccessors), 272 loop_information_(nullptr), 273 dominator_(nullptr), 274 block_id_(-1), 275 lifetime_start_(kNoLifetime), 276 lifetime_end_(kNoLifetime) {} 277 278 const GrowableArray<HBasicBlock*>& GetPredecessors() const { 279 return predecessors_; 280 } 281 282 const GrowableArray<HBasicBlock*>& GetSuccessors() const { 283 return successors_; 284 } 285 286 void AddBackEdge(HBasicBlock* back_edge) { 287 if (loop_information_ == nullptr) { 288 loop_information_ = new (graph_->GetArena()) HLoopInformation(this, graph_); 289 } 290 DCHECK_EQ(loop_information_->GetHeader(), this); 291 loop_information_->AddBackEdge(back_edge); 292 } 293 294 HGraph* GetGraph() const { return graph_; } 295 296 int GetBlockId() const { return block_id_; } 297 void SetBlockId(int id) { block_id_ = id; } 298 299 HBasicBlock* GetDominator() const { return dominator_; } 300 void SetDominator(HBasicBlock* dominator) { dominator_ = dominator; } 301 302 int NumberOfBackEdges() const { 303 return loop_information_ == nullptr 304 ? 0 305 : loop_information_->NumberOfBackEdges(); 306 } 307 308 HInstruction* GetFirstInstruction() const { return instructions_.first_instruction_; } 309 HInstruction* GetLastInstruction() const { return instructions_.last_instruction_; } 310 const HInstructionList& GetInstructions() const { return instructions_; } 311 const HInstructionList& GetPhis() const { return phis_; } 312 HInstruction* GetFirstPhi() const { return phis_.first_instruction_; } 313 314 void AddSuccessor(HBasicBlock* block) { 315 successors_.Add(block); 316 block->predecessors_.Add(this); 317 } 318 319 void ReplaceSuccessor(HBasicBlock* existing, HBasicBlock* new_block) { 320 size_t successor_index = GetSuccessorIndexOf(existing); 321 DCHECK_NE(successor_index, static_cast<size_t>(-1)); 322 existing->RemovePredecessor(this); 323 new_block->predecessors_.Add(this); 324 successors_.Put(successor_index, new_block); 325 } 326 327 void RemovePredecessor(HBasicBlock* block) { 328 predecessors_.Delete(block); 329 } 330 331 void ClearAllPredecessors() { 332 predecessors_.Reset(); 333 } 334 335 void AddPredecessor(HBasicBlock* block) { 336 predecessors_.Add(block); 337 block->successors_.Add(this); 338 } 339 340 size_t GetPredecessorIndexOf(HBasicBlock* predecessor) { 341 for (size_t i = 0, e = predecessors_.Size(); i < e; ++i) { 342 if (predecessors_.Get(i) == predecessor) { 343 return i; 344 } 345 } 346 return -1; 347 } 348 349 size_t GetSuccessorIndexOf(HBasicBlock* successor) { 350 for (size_t i = 0, e = successors_.Size(); i < e; ++i) { 351 if (successors_.Get(i) == successor) { 352 return i; 353 } 354 } 355 return -1; 356 } 357 358 void AddInstruction(HInstruction* instruction); 359 void RemoveInstruction(HInstruction* instruction); 360 void InsertInstructionBefore(HInstruction* instruction, HInstruction* cursor); 361 // Replace instruction `initial` with `replacement` within this block. 362 void ReplaceAndRemoveInstructionWith(HInstruction* initial, 363 HInstruction* replacement); 364 void AddPhi(HPhi* phi); 365 void RemovePhi(HPhi* phi); 366 367 bool IsLoopHeader() const { 368 return (loop_information_ != nullptr) && (loop_information_->GetHeader() == this); 369 } 370 371 HLoopInformation* GetLoopInformation() const { 372 return loop_information_; 373 } 374 375 // Set the loop_information_ on this block. This method overrides the current 376 // loop_information if it is an outer loop of the passed loop information. 377 void SetInLoop(HLoopInformation* info) { 378 if (IsLoopHeader()) { 379 // Nothing to do. This just means `info` is an outer loop. 380 } else if (loop_information_ == nullptr) { 381 loop_information_ = info; 382 } else if (loop_information_->Contains(*info->GetHeader())) { 383 // Block is currently part of an outer loop. Make it part of this inner loop. 384 // Note that a non loop header having a loop information means this loop information 385 // has already been populated 386 loop_information_ = info; 387 } else { 388 // Block is part of an inner loop. Do not update the loop information. 389 // Note that we cannot do the check `info->Contains(loop_information_)->GetHeader()` 390 // at this point, because this method is being called while populating `info`. 391 } 392 } 393 394 bool IsInLoop() const { return loop_information_ != nullptr; } 395 396 // Returns wheter this block dominates the blocked passed as parameter. 397 bool Dominates(HBasicBlock* block) const; 398 399 size_t GetLifetimeStart() const { return lifetime_start_; } 400 size_t GetLifetimeEnd() const { return lifetime_end_; } 401 402 void SetLifetimeStart(size_t start) { lifetime_start_ = start; } 403 void SetLifetimeEnd(size_t end) { lifetime_end_ = end; } 404 405 private: 406 HGraph* const graph_; 407 GrowableArray<HBasicBlock*> predecessors_; 408 GrowableArray<HBasicBlock*> successors_; 409 HInstructionList instructions_; 410 HInstructionList phis_; 411 HLoopInformation* loop_information_; 412 HBasicBlock* dominator_; 413 int block_id_; 414 size_t lifetime_start_; 415 size_t lifetime_end_; 416 417 DISALLOW_COPY_AND_ASSIGN(HBasicBlock); 418}; 419 420#define FOR_EACH_CONCRETE_INSTRUCTION(M) \ 421 M(Add) \ 422 M(Condition) \ 423 M(Equal) \ 424 M(NotEqual) \ 425 M(LessThan) \ 426 M(LessThanOrEqual) \ 427 M(GreaterThan) \ 428 M(GreaterThanOrEqual) \ 429 M(Exit) \ 430 M(Goto) \ 431 M(If) \ 432 M(IntConstant) \ 433 M(InvokeStatic) \ 434 M(InvokeVirtual) \ 435 M(LoadLocal) \ 436 M(Local) \ 437 M(LongConstant) \ 438 M(NewInstance) \ 439 M(Not) \ 440 M(ParameterValue) \ 441 M(ParallelMove) \ 442 M(Phi) \ 443 M(Return) \ 444 M(ReturnVoid) \ 445 M(StoreLocal) \ 446 M(Sub) \ 447 M(Compare) \ 448 M(InstanceFieldGet) \ 449 M(InstanceFieldSet) \ 450 M(ArrayGet) \ 451 M(ArraySet) \ 452 M(ArrayLength) \ 453 M(BoundsCheck) \ 454 M(NullCheck) \ 455 M(Temporary) \ 456 M(SuspendCheck) \ 457 458#define FOR_EACH_INSTRUCTION(M) \ 459 FOR_EACH_CONCRETE_INSTRUCTION(M) \ 460 M(Constant) \ 461 M(BinaryOperation) 462 463#define FORWARD_DECLARATION(type) class H##type; 464FOR_EACH_INSTRUCTION(FORWARD_DECLARATION) 465#undef FORWARD_DECLARATION 466 467#define DECLARE_INSTRUCTION(type) \ 468 virtual const char* DebugName() const { return #type; } \ 469 virtual const H##type* As##type() const OVERRIDE { return this; } \ 470 virtual H##type* As##type() OVERRIDE { return this; } \ 471 virtual bool InstructionTypeEquals(HInstruction* other) const { \ 472 return other->Is##type(); \ 473 } \ 474 virtual void Accept(HGraphVisitor* visitor) 475 476template <typename T> 477class HUseListNode : public ArenaObject { 478 public: 479 HUseListNode(T* user, size_t index, HUseListNode* tail) 480 : user_(user), index_(index), tail_(tail) {} 481 482 HUseListNode* GetTail() const { return tail_; } 483 T* GetUser() const { return user_; } 484 size_t GetIndex() const { return index_; } 485 486 void SetTail(HUseListNode<T>* node) { tail_ = node; } 487 488 private: 489 T* const user_; 490 const size_t index_; 491 HUseListNode<T>* tail_; 492 493 DISALLOW_COPY_AND_ASSIGN(HUseListNode); 494}; 495 496// Represents the side effects an instruction may have. 497class SideEffects : public ValueObject { 498 public: 499 static SideEffects None() { 500 return SideEffects(0); 501 } 502 503 static SideEffects All() { 504 return SideEffects(ChangesSomething().flags_ | DependsOnSomething().flags_); 505 } 506 507 static SideEffects ChangesSomething() { 508 return SideEffects((1 << kFlagChangesCount) - 1); 509 } 510 511 static SideEffects DependsOnSomething() { 512 int count = kFlagDependsOnCount - kFlagChangesCount; 513 return SideEffects(((1 << count) - 1) << kFlagChangesCount); 514 } 515 516 bool HasSideEffects() const { 517 size_t all_bits_set = (1 << kFlagChangesCount) - 1; 518 return (flags_ & all_bits_set) != 0; 519 } 520 521 private: 522 static constexpr int kFlagChangesSomething = 0; 523 static constexpr int kFlagChangesCount = kFlagChangesSomething + 1; 524 525 static constexpr int kFlagDependsOnSomething = kFlagChangesCount; 526 static constexpr int kFlagDependsOnCount = kFlagDependsOnSomething + 1; 527 528 private: 529 explicit SideEffects(size_t flags) : flags_(flags) {} 530 531 const size_t flags_; 532}; 533 534class HInstruction : public ArenaObject { 535 public: 536 explicit HInstruction(SideEffects side_effects) 537 : previous_(nullptr), 538 next_(nullptr), 539 block_(nullptr), 540 id_(-1), 541 ssa_index_(-1), 542 uses_(nullptr), 543 env_uses_(nullptr), 544 environment_(nullptr), 545 locations_(nullptr), 546 live_interval_(nullptr), 547 lifetime_position_(kNoLifetime), 548 side_effects_(side_effects) {} 549 550 virtual ~HInstruction() {} 551 552 HInstruction* GetNext() const { return next_; } 553 HInstruction* GetPrevious() const { return previous_; } 554 555 HBasicBlock* GetBlock() const { return block_; } 556 void SetBlock(HBasicBlock* block) { block_ = block; } 557 bool IsInBlock() const { return block_ != nullptr; } 558 bool IsInLoop() const { return block_->IsInLoop(); } 559 bool IsLoopHeaderPhi() { return IsPhi() && block_->IsLoopHeader(); } 560 561 virtual size_t InputCount() const = 0; 562 virtual HInstruction* InputAt(size_t i) const = 0; 563 564 virtual void Accept(HGraphVisitor* visitor) = 0; 565 virtual const char* DebugName() const = 0; 566 567 virtual Primitive::Type GetType() const { return Primitive::kPrimVoid; } 568 virtual void SetRawInputAt(size_t index, HInstruction* input) = 0; 569 570 virtual bool NeedsEnvironment() const { return false; } 571 virtual bool IsControlFlow() const { return false; } 572 bool HasSideEffects() const { return side_effects_.HasSideEffects(); } 573 574 void AddUseAt(HInstruction* user, size_t index) { 575 uses_ = new (block_->GetGraph()->GetArena()) HUseListNode<HInstruction>(user, index, uses_); 576 } 577 578 void AddEnvUseAt(HEnvironment* user, size_t index) { 579 env_uses_ = new (block_->GetGraph()->GetArena()) HUseListNode<HEnvironment>( 580 user, index, env_uses_); 581 } 582 583 void RemoveUser(HInstruction* user, size_t index); 584 585 HUseListNode<HInstruction>* GetUses() const { return uses_; } 586 HUseListNode<HEnvironment>* GetEnvUses() const { return env_uses_; } 587 588 bool HasUses() const { return uses_ != nullptr || env_uses_ != nullptr; } 589 bool HasEnvironmentUses() const { return env_uses_ != nullptr; } 590 591 size_t NumberOfUses() const { 592 // TODO: Optimize this method if it is used outside of the HGraphVisualizer. 593 size_t result = 0; 594 HUseListNode<HInstruction>* current = uses_; 595 while (current != nullptr) { 596 current = current->GetTail(); 597 ++result; 598 } 599 return result; 600 } 601 602 // Does this instruction dominate `other_instruction`? Aborts if 603 // this instruction and `other_instruction` are both phis. 604 bool Dominates(HInstruction* other_instruction) const; 605 606 int GetId() const { return id_; } 607 void SetId(int id) { id_ = id; } 608 609 int GetSsaIndex() const { return ssa_index_; } 610 void SetSsaIndex(int ssa_index) { ssa_index_ = ssa_index; } 611 bool HasSsaIndex() const { return ssa_index_ != -1; } 612 613 bool HasEnvironment() const { return environment_ != nullptr; } 614 HEnvironment* GetEnvironment() const { return environment_; } 615 void SetEnvironment(HEnvironment* environment) { environment_ = environment; } 616 617 // Returns the number of entries in the environment. Typically, that is the 618 // number of dex registers in a method. It could be more in case of inlining. 619 size_t EnvironmentSize() const; 620 621 LocationSummary* GetLocations() const { return locations_; } 622 void SetLocations(LocationSummary* locations) { locations_ = locations; } 623 624 void ReplaceWith(HInstruction* instruction); 625 626 bool HasOnlyOneUse() const { 627 return uses_ != nullptr && uses_->GetTail() == nullptr; 628 } 629 630#define INSTRUCTION_TYPE_CHECK(type) \ 631 bool Is##type() const { return (As##type() != nullptr); } \ 632 virtual const H##type* As##type() const { return nullptr; } \ 633 virtual H##type* As##type() { return nullptr; } 634 635 FOR_EACH_INSTRUCTION(INSTRUCTION_TYPE_CHECK) 636#undef INSTRUCTION_TYPE_CHECK 637 638 // Returns whether the instruction can be moved within the graph. 639 virtual bool CanBeMoved() const { return false; } 640 641 // Returns whether the two instructions are of the same kind. 642 virtual bool InstructionTypeEquals(HInstruction* other) const { return false; } 643 644 // Returns whether any data encoded in the two instructions is equal. 645 // This method does not look at the inputs. Both instructions must be 646 // of the same type, otherwise the method has undefined behavior. 647 virtual bool InstructionDataEquals(HInstruction* other) const { return false; } 648 649 // Returns whether two instructions are equal, that is: 650 // 1) They have the same type and contain the same data, 651 // 2) Their inputs are identical. 652 bool Equals(HInstruction* other) const; 653 654 size_t GetLifetimePosition() const { return lifetime_position_; } 655 void SetLifetimePosition(size_t position) { lifetime_position_ = position; } 656 LiveInterval* GetLiveInterval() const { return live_interval_; } 657 void SetLiveInterval(LiveInterval* interval) { live_interval_ = interval; } 658 bool HasLiveInterval() const { return live_interval_ != nullptr; } 659 660 private: 661 HInstruction* previous_; 662 HInstruction* next_; 663 HBasicBlock* block_; 664 665 // An instruction gets an id when it is added to the graph. 666 // It reflects creation order. A negative id means the instruction 667 // has not been added to the graph. 668 int id_; 669 670 // When doing liveness analysis, instructions that have uses get an SSA index. 671 int ssa_index_; 672 673 // List of instructions that have this instruction as input. 674 HUseListNode<HInstruction>* uses_; 675 676 // List of environments that contain this instruction. 677 HUseListNode<HEnvironment>* env_uses_; 678 679 // The environment associated with this instruction. Not null if the instruction 680 // might jump out of the method. 681 HEnvironment* environment_; 682 683 // Set by the code generator. 684 LocationSummary* locations_; 685 686 // Set by the liveness analysis. 687 LiveInterval* live_interval_; 688 689 // Set by the liveness analysis, this is the position in a linear 690 // order of blocks where this instruction's live interval start. 691 size_t lifetime_position_; 692 693 const SideEffects side_effects_; 694 695 friend class HBasicBlock; 696 friend class HInstructionList; 697 698 DISALLOW_COPY_AND_ASSIGN(HInstruction); 699}; 700 701template<typename T> 702class HUseIterator : public ValueObject { 703 public: 704 explicit HUseIterator(HUseListNode<T>* uses) : current_(uses) {} 705 706 bool Done() const { return current_ == nullptr; } 707 708 void Advance() { 709 DCHECK(!Done()); 710 current_ = current_->GetTail(); 711 } 712 713 HUseListNode<T>* Current() const { 714 DCHECK(!Done()); 715 return current_; 716 } 717 718 private: 719 HUseListNode<T>* current_; 720 721 friend class HValue; 722}; 723 724// A HEnvironment object contains the values of virtual registers at a given location. 725class HEnvironment : public ArenaObject { 726 public: 727 HEnvironment(ArenaAllocator* arena, size_t number_of_vregs) : vregs_(arena, number_of_vregs) { 728 vregs_.SetSize(number_of_vregs); 729 for (size_t i = 0; i < number_of_vregs; i++) { 730 vregs_.Put(i, nullptr); 731 } 732 } 733 734 void Populate(const GrowableArray<HInstruction*>& env) { 735 for (size_t i = 0; i < env.Size(); i++) { 736 HInstruction* instruction = env.Get(i); 737 vregs_.Put(i, instruction); 738 if (instruction != nullptr) { 739 instruction->AddEnvUseAt(this, i); 740 } 741 } 742 } 743 744 void SetRawEnvAt(size_t index, HInstruction* instruction) { 745 vregs_.Put(index, instruction); 746 } 747 748 HInstruction* GetInstructionAt(size_t index) const { 749 return vregs_.Get(index); 750 } 751 752 GrowableArray<HInstruction*>* GetVRegs() { 753 return &vregs_; 754 } 755 756 size_t Size() const { return vregs_.Size(); } 757 758 private: 759 GrowableArray<HInstruction*> vregs_; 760 761 DISALLOW_COPY_AND_ASSIGN(HEnvironment); 762}; 763 764class HInputIterator : public ValueObject { 765 public: 766 explicit HInputIterator(HInstruction* instruction) : instruction_(instruction), index_(0) {} 767 768 bool Done() const { return index_ == instruction_->InputCount(); } 769 HInstruction* Current() const { return instruction_->InputAt(index_); } 770 void Advance() { index_++; } 771 772 private: 773 HInstruction* instruction_; 774 size_t index_; 775 776 DISALLOW_COPY_AND_ASSIGN(HInputIterator); 777}; 778 779class HInstructionIterator : public ValueObject { 780 public: 781 explicit HInstructionIterator(const HInstructionList& instructions) 782 : instruction_(instructions.first_instruction_) { 783 next_ = Done() ? nullptr : instruction_->GetNext(); 784 } 785 786 bool Done() const { return instruction_ == nullptr; } 787 HInstruction* Current() const { return instruction_; } 788 void Advance() { 789 instruction_ = next_; 790 next_ = Done() ? nullptr : instruction_->GetNext(); 791 } 792 793 private: 794 HInstruction* instruction_; 795 HInstruction* next_; 796 797 DISALLOW_COPY_AND_ASSIGN(HInstructionIterator); 798}; 799 800class HBackwardInstructionIterator : public ValueObject { 801 public: 802 explicit HBackwardInstructionIterator(const HInstructionList& instructions) 803 : instruction_(instructions.last_instruction_) { 804 next_ = Done() ? nullptr : instruction_->GetPrevious(); 805 } 806 807 bool Done() const { return instruction_ == nullptr; } 808 HInstruction* Current() const { return instruction_; } 809 void Advance() { 810 instruction_ = next_; 811 next_ = Done() ? nullptr : instruction_->GetPrevious(); 812 } 813 814 private: 815 HInstruction* instruction_; 816 HInstruction* next_; 817 818 DISALLOW_COPY_AND_ASSIGN(HBackwardInstructionIterator); 819}; 820 821// An embedded container with N elements of type T. Used (with partial 822// specialization for N=0) because embedded arrays cannot have size 0. 823template<typename T, intptr_t N> 824class EmbeddedArray { 825 public: 826 EmbeddedArray() : elements_() {} 827 828 intptr_t GetLength() const { return N; } 829 830 const T& operator[](intptr_t i) const { 831 DCHECK_LT(i, GetLength()); 832 return elements_[i]; 833 } 834 835 T& operator[](intptr_t i) { 836 DCHECK_LT(i, GetLength()); 837 return elements_[i]; 838 } 839 840 const T& At(intptr_t i) const { 841 return (*this)[i]; 842 } 843 844 void SetAt(intptr_t i, const T& val) { 845 (*this)[i] = val; 846 } 847 848 private: 849 T elements_[N]; 850}; 851 852template<typename T> 853class EmbeddedArray<T, 0> { 854 public: 855 intptr_t length() const { return 0; } 856 const T& operator[](intptr_t i) const { 857 LOG(FATAL) << "Unreachable"; 858 static T sentinel = 0; 859 return sentinel; 860 } 861 T& operator[](intptr_t i) { 862 LOG(FATAL) << "Unreachable"; 863 static T sentinel = 0; 864 return sentinel; 865 } 866}; 867 868template<intptr_t N> 869class HTemplateInstruction: public HInstruction { 870 public: 871 HTemplateInstruction<N>(SideEffects side_effects) 872 : HInstruction(side_effects), inputs_() {} 873 virtual ~HTemplateInstruction() {} 874 875 virtual size_t InputCount() const { return N; } 876 virtual HInstruction* InputAt(size_t i) const { return inputs_[i]; } 877 878 protected: 879 virtual void SetRawInputAt(size_t i, HInstruction* instruction) { 880 inputs_[i] = instruction; 881 } 882 883 private: 884 EmbeddedArray<HInstruction*, N> inputs_; 885 886 friend class SsaBuilder; 887}; 888 889template<intptr_t N> 890class HExpression : public HTemplateInstruction<N> { 891 public: 892 HExpression<N>(Primitive::Type type, SideEffects side_effects) 893 : HTemplateInstruction<N>(side_effects), type_(type) {} 894 virtual ~HExpression() {} 895 896 virtual Primitive::Type GetType() const { return type_; } 897 898 private: 899 const Primitive::Type type_; 900}; 901 902// Represents dex's RETURN_VOID opcode. A HReturnVoid is a control flow 903// instruction that branches to the exit block. 904class HReturnVoid : public HTemplateInstruction<0> { 905 public: 906 HReturnVoid() : HTemplateInstruction(SideEffects::None()) {} 907 908 virtual bool IsControlFlow() const { return true; } 909 910 DECLARE_INSTRUCTION(ReturnVoid); 911 912 private: 913 DISALLOW_COPY_AND_ASSIGN(HReturnVoid); 914}; 915 916// Represents dex's RETURN opcodes. A HReturn is a control flow 917// instruction that branches to the exit block. 918class HReturn : public HTemplateInstruction<1> { 919 public: 920 explicit HReturn(HInstruction* value) : HTemplateInstruction(SideEffects::None()) { 921 SetRawInputAt(0, value); 922 } 923 924 virtual bool IsControlFlow() const { return true; } 925 926 DECLARE_INSTRUCTION(Return); 927 928 private: 929 DISALLOW_COPY_AND_ASSIGN(HReturn); 930}; 931 932// The exit instruction is the only instruction of the exit block. 933// Instructions aborting the method (HTrow and HReturn) must branch to the 934// exit block. 935class HExit : public HTemplateInstruction<0> { 936 public: 937 HExit() : HTemplateInstruction(SideEffects::None()) {} 938 939 virtual bool IsControlFlow() const { return true; } 940 941 DECLARE_INSTRUCTION(Exit); 942 943 private: 944 DISALLOW_COPY_AND_ASSIGN(HExit); 945}; 946 947// Jumps from one block to another. 948class HGoto : public HTemplateInstruction<0> { 949 public: 950 HGoto() : HTemplateInstruction(SideEffects::None()) {} 951 952 virtual bool IsControlFlow() const { return true; } 953 954 HBasicBlock* GetSuccessor() const { 955 return GetBlock()->GetSuccessors().Get(0); 956 } 957 958 DECLARE_INSTRUCTION(Goto); 959 960 private: 961 DISALLOW_COPY_AND_ASSIGN(HGoto); 962}; 963 964 965// Conditional branch. A block ending with an HIf instruction must have 966// two successors. 967class HIf : public HTemplateInstruction<1> { 968 public: 969 explicit HIf(HInstruction* input) : HTemplateInstruction(SideEffects::None()) { 970 SetRawInputAt(0, input); 971 } 972 973 virtual bool IsControlFlow() const { return true; } 974 975 HBasicBlock* IfTrueSuccessor() const { 976 return GetBlock()->GetSuccessors().Get(0); 977 } 978 979 HBasicBlock* IfFalseSuccessor() const { 980 return GetBlock()->GetSuccessors().Get(1); 981 } 982 983 DECLARE_INSTRUCTION(If); 984 985 virtual bool IsIfInstruction() const { return true; } 986 987 private: 988 DISALLOW_COPY_AND_ASSIGN(HIf); 989}; 990 991class HBinaryOperation : public HExpression<2> { 992 public: 993 HBinaryOperation(Primitive::Type result_type, 994 HInstruction* left, 995 HInstruction* right) : HExpression(result_type, SideEffects::None()) { 996 SetRawInputAt(0, left); 997 SetRawInputAt(1, right); 998 } 999 1000 HInstruction* GetLeft() const { return InputAt(0); } 1001 HInstruction* GetRight() const { return InputAt(1); } 1002 Primitive::Type GetResultType() const { return GetType(); } 1003 1004 virtual bool IsCommutative() { return false; } 1005 1006 virtual bool CanBeMoved() const { return true; } 1007 virtual bool InstructionDataEquals(HInstruction* other) const { return true; } 1008 1009 DECLARE_INSTRUCTION(BinaryOperation); 1010 1011 private: 1012 DISALLOW_COPY_AND_ASSIGN(HBinaryOperation); 1013}; 1014 1015class HCondition : public HBinaryOperation { 1016 public: 1017 HCondition(HInstruction* first, HInstruction* second) 1018 : HBinaryOperation(Primitive::kPrimBoolean, first, second) {} 1019 1020 virtual bool IsCommutative() { return true; } 1021 bool NeedsMaterialization() const; 1022 1023 DECLARE_INSTRUCTION(Condition); 1024 1025 virtual IfCondition GetCondition() const = 0; 1026 1027 private: 1028 DISALLOW_COPY_AND_ASSIGN(HCondition); 1029}; 1030 1031// Instruction to check if two inputs are equal to each other. 1032class HEqual : public HCondition { 1033 public: 1034 HEqual(HInstruction* first, HInstruction* second) 1035 : HCondition(first, second) {} 1036 1037 DECLARE_INSTRUCTION(Equal); 1038 1039 virtual IfCondition GetCondition() const { 1040 return kCondEQ; 1041 } 1042 1043 private: 1044 DISALLOW_COPY_AND_ASSIGN(HEqual); 1045}; 1046 1047class HNotEqual : public HCondition { 1048 public: 1049 HNotEqual(HInstruction* first, HInstruction* second) 1050 : HCondition(first, second) {} 1051 1052 DECLARE_INSTRUCTION(NotEqual); 1053 1054 virtual IfCondition GetCondition() const { 1055 return kCondNE; 1056 } 1057 1058 private: 1059 DISALLOW_COPY_AND_ASSIGN(HNotEqual); 1060}; 1061 1062class HLessThan : public HCondition { 1063 public: 1064 HLessThan(HInstruction* first, HInstruction* second) 1065 : HCondition(first, second) {} 1066 1067 DECLARE_INSTRUCTION(LessThan); 1068 1069 virtual IfCondition GetCondition() const { 1070 return kCondLT; 1071 } 1072 1073 private: 1074 DISALLOW_COPY_AND_ASSIGN(HLessThan); 1075}; 1076 1077class HLessThanOrEqual : public HCondition { 1078 public: 1079 HLessThanOrEqual(HInstruction* first, HInstruction* second) 1080 : HCondition(first, second) {} 1081 1082 DECLARE_INSTRUCTION(LessThanOrEqual); 1083 1084 virtual IfCondition GetCondition() const { 1085 return kCondLE; 1086 } 1087 1088 private: 1089 DISALLOW_COPY_AND_ASSIGN(HLessThanOrEqual); 1090}; 1091 1092class HGreaterThan : public HCondition { 1093 public: 1094 HGreaterThan(HInstruction* first, HInstruction* second) 1095 : HCondition(first, second) {} 1096 1097 DECLARE_INSTRUCTION(GreaterThan); 1098 1099 virtual IfCondition GetCondition() const { 1100 return kCondGT; 1101 } 1102 1103 private: 1104 DISALLOW_COPY_AND_ASSIGN(HGreaterThan); 1105}; 1106 1107class HGreaterThanOrEqual : public HCondition { 1108 public: 1109 HGreaterThanOrEqual(HInstruction* first, HInstruction* second) 1110 : HCondition(first, second) {} 1111 1112 DECLARE_INSTRUCTION(GreaterThanOrEqual); 1113 1114 virtual IfCondition GetCondition() const { 1115 return kCondGE; 1116 } 1117 1118 private: 1119 DISALLOW_COPY_AND_ASSIGN(HGreaterThanOrEqual); 1120}; 1121 1122 1123// Instruction to check how two inputs compare to each other. 1124// Result is 0 if input0 == input1, 1 if input0 > input1, or -1 if input0 < input1. 1125class HCompare : public HBinaryOperation { 1126 public: 1127 HCompare(Primitive::Type type, HInstruction* first, HInstruction* second) 1128 : HBinaryOperation(Primitive::kPrimInt, first, second) { 1129 DCHECK_EQ(type, first->GetType()); 1130 DCHECK_EQ(type, second->GetType()); 1131 } 1132 1133 DECLARE_INSTRUCTION(Compare); 1134 1135 private: 1136 DISALLOW_COPY_AND_ASSIGN(HCompare); 1137}; 1138 1139// A local in the graph. Corresponds to a Dex register. 1140class HLocal : public HTemplateInstruction<0> { 1141 public: 1142 explicit HLocal(uint16_t reg_number) 1143 : HTemplateInstruction(SideEffects::None()), reg_number_(reg_number) {} 1144 1145 DECLARE_INSTRUCTION(Local); 1146 1147 uint16_t GetRegNumber() const { return reg_number_; } 1148 1149 private: 1150 // The Dex register number. 1151 const uint16_t reg_number_; 1152 1153 DISALLOW_COPY_AND_ASSIGN(HLocal); 1154}; 1155 1156// Load a given local. The local is an input of this instruction. 1157class HLoadLocal : public HExpression<1> { 1158 public: 1159 explicit HLoadLocal(HLocal* local, Primitive::Type type) 1160 : HExpression(type, SideEffects::None()) { 1161 SetRawInputAt(0, local); 1162 } 1163 1164 HLocal* GetLocal() const { return reinterpret_cast<HLocal*>(InputAt(0)); } 1165 1166 DECLARE_INSTRUCTION(LoadLocal); 1167 1168 private: 1169 DISALLOW_COPY_AND_ASSIGN(HLoadLocal); 1170}; 1171 1172// Store a value in a given local. This instruction has two inputs: the value 1173// and the local. 1174class HStoreLocal : public HTemplateInstruction<2> { 1175 public: 1176 HStoreLocal(HLocal* local, HInstruction* value) : HTemplateInstruction(SideEffects::None()) { 1177 SetRawInputAt(0, local); 1178 SetRawInputAt(1, value); 1179 } 1180 1181 HLocal* GetLocal() const { return reinterpret_cast<HLocal*>(InputAt(0)); } 1182 1183 DECLARE_INSTRUCTION(StoreLocal); 1184 1185 private: 1186 DISALLOW_COPY_AND_ASSIGN(HStoreLocal); 1187}; 1188 1189class HConstant : public HExpression<0> { 1190 public: 1191 explicit HConstant(Primitive::Type type) : HExpression(type, SideEffects::None()) {} 1192 1193 virtual bool CanBeMoved() const { return true; } 1194 1195 DECLARE_INSTRUCTION(Constant); 1196 1197 private: 1198 DISALLOW_COPY_AND_ASSIGN(HConstant); 1199}; 1200 1201// Constants of the type int. Those can be from Dex instructions, or 1202// synthesized (for example with the if-eqz instruction). 1203class HIntConstant : public HConstant { 1204 public: 1205 explicit HIntConstant(int32_t value) : HConstant(Primitive::kPrimInt), value_(value) {} 1206 1207 int32_t GetValue() const { return value_; } 1208 1209 virtual bool InstructionDataEquals(HInstruction* other) const { 1210 return other->AsIntConstant()->value_ == value_; 1211 } 1212 1213 DECLARE_INSTRUCTION(IntConstant); 1214 1215 private: 1216 const int32_t value_; 1217 1218 DISALLOW_COPY_AND_ASSIGN(HIntConstant); 1219}; 1220 1221class HLongConstant : public HConstant { 1222 public: 1223 explicit HLongConstant(int64_t value) : HConstant(Primitive::kPrimLong), value_(value) {} 1224 1225 int64_t GetValue() const { return value_; } 1226 1227 virtual bool InstructionDataEquals(HInstruction* other) const { 1228 return other->AsLongConstant()->value_ == value_; 1229 } 1230 1231 DECLARE_INSTRUCTION(LongConstant); 1232 1233 private: 1234 const int64_t value_; 1235 1236 DISALLOW_COPY_AND_ASSIGN(HLongConstant); 1237}; 1238 1239class HInvoke : public HInstruction { 1240 public: 1241 HInvoke(ArenaAllocator* arena, 1242 uint32_t number_of_arguments, 1243 Primitive::Type return_type, 1244 uint32_t dex_pc) 1245 : HInstruction(SideEffects::All()), 1246 inputs_(arena, number_of_arguments), 1247 return_type_(return_type), 1248 dex_pc_(dex_pc) { 1249 inputs_.SetSize(number_of_arguments); 1250 } 1251 1252 virtual size_t InputCount() const { return inputs_.Size(); } 1253 virtual HInstruction* InputAt(size_t i) const { return inputs_.Get(i); } 1254 1255 // Runtime needs to walk the stack, so Dex -> Dex calls need to 1256 // know their environment. 1257 virtual bool NeedsEnvironment() const { return true; } 1258 1259 void SetArgumentAt(size_t index, HInstruction* argument) { 1260 SetRawInputAt(index, argument); 1261 } 1262 1263 virtual void SetRawInputAt(size_t index, HInstruction* input) { 1264 inputs_.Put(index, input); 1265 } 1266 1267 virtual Primitive::Type GetType() const { return return_type_; } 1268 1269 uint32_t GetDexPc() const { return dex_pc_; } 1270 1271 protected: 1272 GrowableArray<HInstruction*> inputs_; 1273 const Primitive::Type return_type_; 1274 const uint32_t dex_pc_; 1275 1276 private: 1277 DISALLOW_COPY_AND_ASSIGN(HInvoke); 1278}; 1279 1280class HInvokeStatic : public HInvoke { 1281 public: 1282 HInvokeStatic(ArenaAllocator* arena, 1283 uint32_t number_of_arguments, 1284 Primitive::Type return_type, 1285 uint32_t dex_pc, 1286 uint32_t index_in_dex_cache) 1287 : HInvoke(arena, number_of_arguments, return_type, dex_pc), 1288 index_in_dex_cache_(index_in_dex_cache) {} 1289 1290 uint32_t GetIndexInDexCache() const { return index_in_dex_cache_; } 1291 1292 DECLARE_INSTRUCTION(InvokeStatic); 1293 1294 private: 1295 const uint32_t index_in_dex_cache_; 1296 1297 DISALLOW_COPY_AND_ASSIGN(HInvokeStatic); 1298}; 1299 1300class HInvokeVirtual : public HInvoke { 1301 public: 1302 HInvokeVirtual(ArenaAllocator* arena, 1303 uint32_t number_of_arguments, 1304 Primitive::Type return_type, 1305 uint32_t dex_pc, 1306 uint32_t vtable_index) 1307 : HInvoke(arena, number_of_arguments, return_type, dex_pc), 1308 vtable_index_(vtable_index) {} 1309 1310 uint32_t GetVTableIndex() const { return vtable_index_; } 1311 1312 DECLARE_INSTRUCTION(InvokeVirtual); 1313 1314 private: 1315 const uint32_t vtable_index_; 1316 1317 DISALLOW_COPY_AND_ASSIGN(HInvokeVirtual); 1318}; 1319 1320class HNewInstance : public HExpression<0> { 1321 public: 1322 HNewInstance(uint32_t dex_pc, uint16_t type_index) 1323 : HExpression(Primitive::kPrimNot, SideEffects::None()), 1324 dex_pc_(dex_pc), 1325 type_index_(type_index) {} 1326 1327 uint32_t GetDexPc() const { return dex_pc_; } 1328 uint16_t GetTypeIndex() const { return type_index_; } 1329 1330 // Calls runtime so needs an environment. 1331 virtual bool NeedsEnvironment() const { return true; } 1332 1333 DECLARE_INSTRUCTION(NewInstance); 1334 1335 private: 1336 const uint32_t dex_pc_; 1337 const uint16_t type_index_; 1338 1339 DISALLOW_COPY_AND_ASSIGN(HNewInstance); 1340}; 1341 1342class HAdd : public HBinaryOperation { 1343 public: 1344 HAdd(Primitive::Type result_type, HInstruction* left, HInstruction* right) 1345 : HBinaryOperation(result_type, left, right) {} 1346 1347 virtual bool IsCommutative() { return true; } 1348 1349 DECLARE_INSTRUCTION(Add); 1350 1351 private: 1352 DISALLOW_COPY_AND_ASSIGN(HAdd); 1353}; 1354 1355class HSub : public HBinaryOperation { 1356 public: 1357 HSub(Primitive::Type result_type, HInstruction* left, HInstruction* right) 1358 : HBinaryOperation(result_type, left, right) {} 1359 1360 virtual bool IsCommutative() { return false; } 1361 1362 DECLARE_INSTRUCTION(Sub); 1363 1364 private: 1365 DISALLOW_COPY_AND_ASSIGN(HSub); 1366}; 1367 1368// The value of a parameter in this method. Its location depends on 1369// the calling convention. 1370class HParameterValue : public HExpression<0> { 1371 public: 1372 HParameterValue(uint8_t index, Primitive::Type parameter_type) 1373 : HExpression(parameter_type, SideEffects::None()), index_(index) {} 1374 1375 uint8_t GetIndex() const { return index_; } 1376 1377 DECLARE_INSTRUCTION(ParameterValue); 1378 1379 private: 1380 // The index of this parameter in the parameters list. Must be less 1381 // than HGraph::number_of_in_vregs_; 1382 const uint8_t index_; 1383 1384 DISALLOW_COPY_AND_ASSIGN(HParameterValue); 1385}; 1386 1387class HNot : public HExpression<1> { 1388 public: 1389 explicit HNot(HInstruction* input) : HExpression(Primitive::kPrimBoolean, SideEffects::None()) { 1390 SetRawInputAt(0, input); 1391 } 1392 1393 virtual bool CanBeMoved() const { return true; } 1394 virtual bool InstructionDataEquals(HInstruction* other) const { return true; } 1395 1396 DECLARE_INSTRUCTION(Not); 1397 1398 private: 1399 DISALLOW_COPY_AND_ASSIGN(HNot); 1400}; 1401 1402class HPhi : public HInstruction { 1403 public: 1404 HPhi(ArenaAllocator* arena, uint32_t reg_number, size_t number_of_inputs, Primitive::Type type) 1405 : HInstruction(SideEffects::None()), 1406 inputs_(arena, number_of_inputs), 1407 reg_number_(reg_number), 1408 type_(type), 1409 is_live_(false) { 1410 inputs_.SetSize(number_of_inputs); 1411 } 1412 1413 virtual size_t InputCount() const { return inputs_.Size(); } 1414 virtual HInstruction* InputAt(size_t i) const { return inputs_.Get(i); } 1415 1416 virtual void SetRawInputAt(size_t index, HInstruction* input) { 1417 inputs_.Put(index, input); 1418 } 1419 1420 void AddInput(HInstruction* input); 1421 1422 virtual Primitive::Type GetType() const { return type_; } 1423 void SetType(Primitive::Type type) { type_ = type; } 1424 1425 uint32_t GetRegNumber() const { return reg_number_; } 1426 1427 void SetDead() { is_live_ = false; } 1428 void SetLive() { is_live_ = true; } 1429 bool IsDead() const { return !is_live_; } 1430 bool IsLive() const { return is_live_; } 1431 1432 DECLARE_INSTRUCTION(Phi); 1433 1434 private: 1435 GrowableArray<HInstruction*> inputs_; 1436 const uint32_t reg_number_; 1437 Primitive::Type type_; 1438 bool is_live_; 1439 1440 DISALLOW_COPY_AND_ASSIGN(HPhi); 1441}; 1442 1443class HNullCheck : public HExpression<1> { 1444 public: 1445 HNullCheck(HInstruction* value, uint32_t dex_pc) 1446 : HExpression(value->GetType(), SideEffects::None()), dex_pc_(dex_pc) { 1447 SetRawInputAt(0, value); 1448 } 1449 1450 virtual bool CanBeMoved() const { return true; } 1451 virtual bool InstructionDataEquals(HInstruction* other) const { return true; } 1452 1453 virtual bool NeedsEnvironment() const { return true; } 1454 1455 uint32_t GetDexPc() const { return dex_pc_; } 1456 1457 DECLARE_INSTRUCTION(NullCheck); 1458 1459 private: 1460 const uint32_t dex_pc_; 1461 1462 DISALLOW_COPY_AND_ASSIGN(HNullCheck); 1463}; 1464 1465class FieldInfo : public ValueObject { 1466 public: 1467 explicit FieldInfo(MemberOffset field_offset, Primitive::Type field_type) 1468 : field_offset_(field_offset), field_type_(field_type) {} 1469 1470 MemberOffset GetFieldOffset() const { return field_offset_; } 1471 Primitive::Type GetFieldType() const { return field_type_; } 1472 1473 private: 1474 const MemberOffset field_offset_; 1475 const Primitive::Type field_type_; 1476}; 1477 1478class HInstanceFieldGet : public HExpression<1> { 1479 public: 1480 HInstanceFieldGet(HInstruction* value, 1481 Primitive::Type field_type, 1482 MemberOffset field_offset) 1483 : HExpression(field_type, SideEffects::DependsOnSomething()), 1484 field_info_(field_offset, field_type) { 1485 SetRawInputAt(0, value); 1486 } 1487 1488 virtual bool CanBeMoved() const { return true; } 1489 virtual bool InstructionDataEquals(HInstruction* other) const { 1490 size_t other_offset = other->AsInstanceFieldGet()->GetFieldOffset().SizeValue(); 1491 return other_offset == GetFieldOffset().SizeValue(); 1492 } 1493 1494 MemberOffset GetFieldOffset() const { return field_info_.GetFieldOffset(); } 1495 Primitive::Type GetFieldType() const { return field_info_.GetFieldType(); } 1496 1497 DECLARE_INSTRUCTION(InstanceFieldGet); 1498 1499 private: 1500 const FieldInfo field_info_; 1501 1502 DISALLOW_COPY_AND_ASSIGN(HInstanceFieldGet); 1503}; 1504 1505class HInstanceFieldSet : public HTemplateInstruction<2> { 1506 public: 1507 HInstanceFieldSet(HInstruction* object, 1508 HInstruction* value, 1509 Primitive::Type field_type, 1510 MemberOffset field_offset) 1511 : HTemplateInstruction(SideEffects::ChangesSomething()), 1512 field_info_(field_offset, field_type) { 1513 SetRawInputAt(0, object); 1514 SetRawInputAt(1, value); 1515 } 1516 1517 MemberOffset GetFieldOffset() const { return field_info_.GetFieldOffset(); } 1518 Primitive::Type GetFieldType() const { return field_info_.GetFieldType(); } 1519 1520 DECLARE_INSTRUCTION(InstanceFieldSet); 1521 1522 private: 1523 const FieldInfo field_info_; 1524 1525 DISALLOW_COPY_AND_ASSIGN(HInstanceFieldSet); 1526}; 1527 1528class HArrayGet : public HExpression<2> { 1529 public: 1530 HArrayGet(HInstruction* array, HInstruction* index, Primitive::Type type) 1531 : HExpression(type, SideEffects::DependsOnSomething()) { 1532 SetRawInputAt(0, array); 1533 SetRawInputAt(1, index); 1534 } 1535 1536 virtual bool CanBeMoved() const { return true; } 1537 virtual bool InstructionDataEquals(HInstruction* other) const { return true; } 1538 1539 DECLARE_INSTRUCTION(ArrayGet); 1540 1541 private: 1542 DISALLOW_COPY_AND_ASSIGN(HArrayGet); 1543}; 1544 1545class HArraySet : public HTemplateInstruction<3> { 1546 public: 1547 HArraySet(HInstruction* array, 1548 HInstruction* index, 1549 HInstruction* value, 1550 Primitive::Type component_type, 1551 uint32_t dex_pc) 1552 : HTemplateInstruction(SideEffects::ChangesSomething()), 1553 dex_pc_(dex_pc), 1554 component_type_(component_type) { 1555 SetRawInputAt(0, array); 1556 SetRawInputAt(1, index); 1557 SetRawInputAt(2, value); 1558 } 1559 1560 virtual bool NeedsEnvironment() const { 1561 // We currently always call a runtime method to catch array store 1562 // exceptions. 1563 return InputAt(2)->GetType() == Primitive::kPrimNot; 1564 } 1565 1566 uint32_t GetDexPc() const { return dex_pc_; } 1567 1568 Primitive::Type GetComponentType() const { return component_type_; } 1569 1570 DECLARE_INSTRUCTION(ArraySet); 1571 1572 private: 1573 const uint32_t dex_pc_; 1574 const Primitive::Type component_type_; 1575 1576 DISALLOW_COPY_AND_ASSIGN(HArraySet); 1577}; 1578 1579class HArrayLength : public HExpression<1> { 1580 public: 1581 explicit HArrayLength(HInstruction* array) 1582 : HExpression(Primitive::kPrimInt, SideEffects::None()) { 1583 // Note that arrays do not change length, so the instruction does not 1584 // depend on any write. 1585 SetRawInputAt(0, array); 1586 } 1587 1588 virtual bool CanBeMoved() const { return true; } 1589 virtual bool InstructionDataEquals(HInstruction* other) const { return true; } 1590 1591 DECLARE_INSTRUCTION(ArrayLength); 1592 1593 private: 1594 DISALLOW_COPY_AND_ASSIGN(HArrayLength); 1595}; 1596 1597class HBoundsCheck : public HExpression<2> { 1598 public: 1599 HBoundsCheck(HInstruction* index, HInstruction* length, uint32_t dex_pc) 1600 : HExpression(index->GetType(), SideEffects::None()), dex_pc_(dex_pc) { 1601 DCHECK(index->GetType() == Primitive::kPrimInt); 1602 SetRawInputAt(0, index); 1603 SetRawInputAt(1, length); 1604 } 1605 1606 virtual bool CanBeMoved() const { return true; } 1607 virtual bool InstructionDataEquals(HInstruction* other) const { return true; } 1608 1609 virtual bool NeedsEnvironment() const { return true; } 1610 1611 uint32_t GetDexPc() const { return dex_pc_; } 1612 1613 DECLARE_INSTRUCTION(BoundsCheck); 1614 1615 private: 1616 const uint32_t dex_pc_; 1617 1618 DISALLOW_COPY_AND_ASSIGN(HBoundsCheck); 1619}; 1620 1621/** 1622 * Some DEX instructions are folded into multiple HInstructions that need 1623 * to stay live until the last HInstruction. This class 1624 * is used as a marker for the baseline compiler to ensure its preceding 1625 * HInstruction stays live. `index` is the temporary number that is used 1626 * for knowing the stack offset where to store the instruction. 1627 */ 1628class HTemporary : public HTemplateInstruction<0> { 1629 public: 1630 explicit HTemporary(size_t index) : HTemplateInstruction(SideEffects::None()), index_(index) {} 1631 1632 size_t GetIndex() const { return index_; } 1633 1634 DECLARE_INSTRUCTION(Temporary); 1635 1636 private: 1637 const size_t index_; 1638 1639 DISALLOW_COPY_AND_ASSIGN(HTemporary); 1640}; 1641 1642class HSuspendCheck : public HTemplateInstruction<0> { 1643 public: 1644 explicit HSuspendCheck(uint32_t dex_pc) 1645 : HTemplateInstruction(SideEffects::ChangesSomething()), dex_pc_(dex_pc) {} 1646 1647 virtual bool NeedsEnvironment() const { 1648 return true; 1649 } 1650 1651 uint32_t GetDexPc() const { return dex_pc_; } 1652 1653 DECLARE_INSTRUCTION(SuspendCheck); 1654 1655 private: 1656 const uint32_t dex_pc_; 1657 1658 DISALLOW_COPY_AND_ASSIGN(HSuspendCheck); 1659}; 1660 1661class MoveOperands : public ArenaObject { 1662 public: 1663 MoveOperands(Location source, Location destination) 1664 : source_(source), destination_(destination) {} 1665 1666 Location GetSource() const { return source_; } 1667 Location GetDestination() const { return destination_; } 1668 1669 void SetSource(Location value) { source_ = value; } 1670 void SetDestination(Location value) { destination_ = value; } 1671 1672 // The parallel move resolver marks moves as "in-progress" by clearing the 1673 // destination (but not the source). 1674 Location MarkPending() { 1675 DCHECK(!IsPending()); 1676 Location dest = destination_; 1677 destination_ = Location::NoLocation(); 1678 return dest; 1679 } 1680 1681 void ClearPending(Location dest) { 1682 DCHECK(IsPending()); 1683 destination_ = dest; 1684 } 1685 1686 bool IsPending() const { 1687 DCHECK(!source_.IsInvalid() || destination_.IsInvalid()); 1688 return destination_.IsInvalid() && !source_.IsInvalid(); 1689 } 1690 1691 // True if this blocks a move from the given location. 1692 bool Blocks(Location loc) const { 1693 return !IsEliminated() && source_.Equals(loc); 1694 } 1695 1696 // A move is redundant if it's been eliminated, if its source and 1697 // destination are the same, or if its destination is unneeded. 1698 bool IsRedundant() const { 1699 return IsEliminated() || destination_.IsInvalid() || source_.Equals(destination_); 1700 } 1701 1702 // We clear both operands to indicate move that's been eliminated. 1703 void Eliminate() { 1704 source_ = destination_ = Location::NoLocation(); 1705 } 1706 1707 bool IsEliminated() const { 1708 DCHECK(!source_.IsInvalid() || destination_.IsInvalid()); 1709 return source_.IsInvalid(); 1710 } 1711 1712 private: 1713 Location source_; 1714 Location destination_; 1715 1716 DISALLOW_COPY_AND_ASSIGN(MoveOperands); 1717}; 1718 1719static constexpr size_t kDefaultNumberOfMoves = 4; 1720 1721class HParallelMove : public HTemplateInstruction<0> { 1722 public: 1723 explicit HParallelMove(ArenaAllocator* arena) 1724 : HTemplateInstruction(SideEffects::None()), moves_(arena, kDefaultNumberOfMoves) {} 1725 1726 void AddMove(MoveOperands* move) { 1727 moves_.Add(move); 1728 } 1729 1730 MoveOperands* MoveOperandsAt(size_t index) const { 1731 return moves_.Get(index); 1732 } 1733 1734 size_t NumMoves() const { return moves_.Size(); } 1735 1736 DECLARE_INSTRUCTION(ParallelMove); 1737 1738 private: 1739 GrowableArray<MoveOperands*> moves_; 1740 1741 DISALLOW_COPY_AND_ASSIGN(HParallelMove); 1742}; 1743 1744class HGraphVisitor : public ValueObject { 1745 public: 1746 explicit HGraphVisitor(HGraph* graph) : graph_(graph) {} 1747 virtual ~HGraphVisitor() {} 1748 1749 virtual void VisitInstruction(HInstruction* instruction) {} 1750 virtual void VisitBasicBlock(HBasicBlock* block); 1751 1752 void VisitInsertionOrder(); 1753 1754 HGraph* GetGraph() const { return graph_; } 1755 1756 // Visit functions for instruction classes. 1757#define DECLARE_VISIT_INSTRUCTION(name) \ 1758 virtual void Visit##name(H##name* instr) { VisitInstruction(instr); } 1759 1760 FOR_EACH_INSTRUCTION(DECLARE_VISIT_INSTRUCTION) 1761 1762#undef DECLARE_VISIT_INSTRUCTION 1763 1764 private: 1765 HGraph* graph_; 1766 1767 DISALLOW_COPY_AND_ASSIGN(HGraphVisitor); 1768}; 1769 1770class HInsertionOrderIterator : public ValueObject { 1771 public: 1772 explicit HInsertionOrderIterator(const HGraph& graph) : graph_(graph), index_(0) {} 1773 1774 bool Done() const { return index_ == graph_.GetBlocks().Size(); } 1775 HBasicBlock* Current() const { return graph_.GetBlocks().Get(index_); } 1776 void Advance() { ++index_; } 1777 1778 private: 1779 const HGraph& graph_; 1780 size_t index_; 1781 1782 DISALLOW_COPY_AND_ASSIGN(HInsertionOrderIterator); 1783}; 1784 1785class HReversePostOrderIterator : public ValueObject { 1786 public: 1787 explicit HReversePostOrderIterator(const HGraph& graph) : graph_(graph), index_(0) {} 1788 1789 bool Done() const { return index_ == graph_.GetReversePostOrder().Size(); } 1790 HBasicBlock* Current() const { return graph_.GetReversePostOrder().Get(index_); } 1791 void Advance() { ++index_; } 1792 1793 private: 1794 const HGraph& graph_; 1795 size_t index_; 1796 1797 DISALLOW_COPY_AND_ASSIGN(HReversePostOrderIterator); 1798}; 1799 1800class HPostOrderIterator : public ValueObject { 1801 public: 1802 explicit HPostOrderIterator(const HGraph& graph) 1803 : graph_(graph), index_(graph_.GetReversePostOrder().Size()) {} 1804 1805 bool Done() const { return index_ == 0; } 1806 HBasicBlock* Current() const { return graph_.GetReversePostOrder().Get(index_ - 1); } 1807 void Advance() { --index_; } 1808 1809 private: 1810 const HGraph& graph_; 1811 size_t index_; 1812 1813 DISALLOW_COPY_AND_ASSIGN(HPostOrderIterator); 1814}; 1815 1816} // namespace art 1817 1818#endif // ART_COMPILER_OPTIMIZING_NODES_H_ 1819