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