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