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