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