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