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