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