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