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