nodes.h revision ea55b934cff1280318f5514039549799227cfa3d
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 "invoke_type.h" 21#include "locations.h" 22#include "offsets.h" 23#include "primitive.h" 24#include "utils/arena_object.h" 25#include "utils/arena_bit_vector.h" 26#include "utils/growable_array.h" 27 28namespace art { 29 30class HBasicBlock; 31class HEnvironment; 32class HInstruction; 33class HIntConstant; 34class HInvoke; 35class HGraphVisitor; 36class HPhi; 37class HSuspendCheck; 38class LiveInterval; 39class LocationSummary; 40 41static const int kDefaultNumberOfBlocks = 8; 42static const int kDefaultNumberOfSuccessors = 2; 43static const int kDefaultNumberOfPredecessors = 2; 44static const int kDefaultNumberOfDominatedBlocks = 1; 45static const int kDefaultNumberOfBackEdges = 1; 46 47static constexpr uint32_t kMaxIntShiftValue = 0x1f; 48static constexpr uint64_t kMaxLongShiftValue = 0x3f; 49 50enum IfCondition { 51 kCondEQ, 52 kCondNE, 53 kCondLT, 54 kCondLE, 55 kCondGT, 56 kCondGE, 57}; 58 59class HInstructionList { 60 public: 61 HInstructionList() : first_instruction_(nullptr), last_instruction_(nullptr) {} 62 63 void AddInstruction(HInstruction* instruction); 64 void RemoveInstruction(HInstruction* instruction); 65 66 // Return true if this list contains `instruction`. 67 bool Contains(HInstruction* instruction) const; 68 69 // Return true if `instruction1` is found before `instruction2` in 70 // this instruction list and false otherwise. Abort if none 71 // of these instructions is found. 72 bool FoundBefore(const HInstruction* instruction1, 73 const HInstruction* instruction2) const; 74 75 private: 76 HInstruction* first_instruction_; 77 HInstruction* last_instruction_; 78 79 friend class HBasicBlock; 80 friend class HGraph; 81 friend class HInstruction; 82 friend class HInstructionIterator; 83 friend class HBackwardInstructionIterator; 84 85 DISALLOW_COPY_AND_ASSIGN(HInstructionList); 86}; 87 88// Control-flow graph of a method. Contains a list of basic blocks. 89class HGraph : public ArenaObject<kArenaAllocMisc> { 90 public: 91 HGraph(ArenaAllocator* arena, int start_instruction_id = 0) 92 : arena_(arena), 93 blocks_(arena, kDefaultNumberOfBlocks), 94 reverse_post_order_(arena, kDefaultNumberOfBlocks), 95 entry_block_(nullptr), 96 exit_block_(nullptr), 97 maximum_number_of_out_vregs_(0), 98 number_of_vregs_(0), 99 number_of_in_vregs_(0), 100 temporaries_vreg_slots_(0), 101 current_instruction_id_(start_instruction_id) {} 102 103 ArenaAllocator* GetArena() const { return arena_; } 104 const GrowableArray<HBasicBlock*>& GetBlocks() const { return blocks_; } 105 HBasicBlock* GetBlock(size_t id) const { return blocks_.Get(id); } 106 107 HBasicBlock* GetEntryBlock() const { return entry_block_; } 108 HBasicBlock* GetExitBlock() const { return exit_block_; } 109 110 void SetEntryBlock(HBasicBlock* block) { entry_block_ = block; } 111 void SetExitBlock(HBasicBlock* block) { exit_block_ = block; } 112 113 void AddBlock(HBasicBlock* block); 114 115 // Try building the SSA form of this graph, with dominance computation and loop 116 // recognition. Returns whether it was successful in doing all these steps. 117 bool TryBuildingSsa() { 118 BuildDominatorTree(); 119 TransformToSsa(); 120 return AnalyzeNaturalLoops(); 121 } 122 123 void BuildDominatorTree(); 124 void TransformToSsa(); 125 void SimplifyCFG(); 126 127 // Analyze all natural loops in this graph. Returns false if one 128 // loop is not natural, that is the header does not dominate the 129 // back edge. 130 bool AnalyzeNaturalLoops() const; 131 132 // Inline this graph in `outer_graph`, replacing the given `invoke` instruction. 133 void InlineInto(HGraph* outer_graph, HInvoke* invoke); 134 135 void SplitCriticalEdge(HBasicBlock* block, HBasicBlock* successor); 136 void SimplifyLoop(HBasicBlock* header); 137 138 int32_t GetNextInstructionId() { 139 DCHECK_NE(current_instruction_id_, INT32_MAX); 140 return current_instruction_id_++; 141 } 142 143 int32_t GetCurrentInstructionId() const { 144 return current_instruction_id_; 145 } 146 147 void SetCurrentInstructionId(int32_t id) { 148 current_instruction_id_ = id; 149 } 150 151 uint16_t GetMaximumNumberOfOutVRegs() const { 152 return maximum_number_of_out_vregs_; 153 } 154 155 void SetMaximumNumberOfOutVRegs(uint16_t new_value) { 156 maximum_number_of_out_vregs_ = new_value; 157 } 158 159 void UpdateTemporariesVRegSlots(size_t slots) { 160 temporaries_vreg_slots_ = std::max(slots, temporaries_vreg_slots_); 161 } 162 163 size_t GetTemporariesVRegSlots() const { 164 return temporaries_vreg_slots_; 165 } 166 167 void SetNumberOfVRegs(uint16_t number_of_vregs) { 168 number_of_vregs_ = number_of_vregs; 169 } 170 171 uint16_t GetNumberOfVRegs() const { 172 return number_of_vregs_; 173 } 174 175 void SetNumberOfInVRegs(uint16_t value) { 176 number_of_in_vregs_ = value; 177 } 178 179 uint16_t GetNumberOfLocalVRegs() const { 180 return number_of_vregs_ - number_of_in_vregs_; 181 } 182 183 const GrowableArray<HBasicBlock*>& GetReversePostOrder() const { 184 return reverse_post_order_; 185 } 186 187 private: 188 HBasicBlock* FindCommonDominator(HBasicBlock* first, HBasicBlock* second) const; 189 void VisitBlockForDominatorTree(HBasicBlock* block, 190 HBasicBlock* predecessor, 191 GrowableArray<size_t>* visits); 192 void FindBackEdges(ArenaBitVector* visited); 193 void VisitBlockForBackEdges(HBasicBlock* block, 194 ArenaBitVector* visited, 195 ArenaBitVector* visiting); 196 void RemoveInstructionsAsUsersFromDeadBlocks(const ArenaBitVector& visited) const; 197 void RemoveDeadBlocks(const ArenaBitVector& visited) const; 198 void RemoveBlock(HBasicBlock* block) const; 199 200 ArenaAllocator* const arena_; 201 202 // List of blocks in insertion order. 203 GrowableArray<HBasicBlock*> blocks_; 204 205 // List of blocks to perform a reverse post order tree traversal. 206 GrowableArray<HBasicBlock*> reverse_post_order_; 207 208 HBasicBlock* entry_block_; 209 HBasicBlock* exit_block_; 210 211 // The maximum number of virtual registers arguments passed to a HInvoke in this graph. 212 uint16_t maximum_number_of_out_vregs_; 213 214 // The number of virtual registers in this method. Contains the parameters. 215 uint16_t number_of_vregs_; 216 217 // The number of virtual registers used by parameters of this method. 218 uint16_t number_of_in_vregs_; 219 220 // Number of vreg size slots that the temporaries use (used in baseline compiler). 221 size_t temporaries_vreg_slots_; 222 223 // The current id to assign to a newly added instruction. See HInstruction.id_. 224 int32_t current_instruction_id_; 225 226 ART_FRIEND_TEST(GraphTest, IfSuccessorSimpleJoinBlock1); 227 DISALLOW_COPY_AND_ASSIGN(HGraph); 228}; 229 230class HLoopInformation : public ArenaObject<kArenaAllocMisc> { 231 public: 232 HLoopInformation(HBasicBlock* header, HGraph* graph) 233 : header_(header), 234 suspend_check_(nullptr), 235 back_edges_(graph->GetArena(), kDefaultNumberOfBackEdges), 236 // Make bit vector growable, as the number of blocks may change. 237 blocks_(graph->GetArena(), graph->GetBlocks().Size(), true) {} 238 239 HBasicBlock* GetHeader() const { 240 return header_; 241 } 242 243 HSuspendCheck* GetSuspendCheck() const { return suspend_check_; } 244 void SetSuspendCheck(HSuspendCheck* check) { suspend_check_ = check; } 245 bool HasSuspendCheck() const { return suspend_check_ != nullptr; } 246 247 void AddBackEdge(HBasicBlock* back_edge) { 248 back_edges_.Add(back_edge); 249 } 250 251 void RemoveBackEdge(HBasicBlock* back_edge) { 252 back_edges_.Delete(back_edge); 253 } 254 255 bool IsBackEdge(HBasicBlock* block) { 256 for (size_t i = 0, e = back_edges_.Size(); i < e; ++i) { 257 if (back_edges_.Get(i) == block) return true; 258 } 259 return false; 260 } 261 262 size_t NumberOfBackEdges() const { 263 return back_edges_.Size(); 264 } 265 266 HBasicBlock* GetPreHeader() const; 267 268 const GrowableArray<HBasicBlock*>& GetBackEdges() const { 269 return back_edges_; 270 } 271 272 void ClearBackEdges() { 273 back_edges_.Reset(); 274 } 275 276 // Find blocks that are part of this loop. Returns whether the loop is a natural loop, 277 // that is the header dominates the back edge. 278 bool Populate(); 279 280 // Returns whether this loop information contains `block`. 281 // Note that this loop information *must* be populated before entering this function. 282 bool Contains(const HBasicBlock& block) const; 283 284 // Returns whether this loop information is an inner loop of `other`. 285 // Note that `other` *must* be populated before entering this function. 286 bool IsIn(const HLoopInformation& other) const; 287 288 const ArenaBitVector& GetBlocks() const { return blocks_; } 289 290 private: 291 // Internal recursive implementation of `Populate`. 292 void PopulateRecursive(HBasicBlock* block); 293 294 HBasicBlock* header_; 295 HSuspendCheck* suspend_check_; 296 GrowableArray<HBasicBlock*> back_edges_; 297 ArenaBitVector blocks_; 298 299 DISALLOW_COPY_AND_ASSIGN(HLoopInformation); 300}; 301 302static constexpr size_t kNoLifetime = -1; 303static constexpr uint32_t kNoDexPc = -1; 304 305// A block in a method. Contains the list of instructions represented 306// as a double linked list. Each block knows its predecessors and 307// successors. 308 309class HBasicBlock : public ArenaObject<kArenaAllocMisc> { 310 public: 311 explicit HBasicBlock(HGraph* graph, uint32_t dex_pc = kNoDexPc) 312 : graph_(graph), 313 predecessors_(graph->GetArena(), kDefaultNumberOfPredecessors), 314 successors_(graph->GetArena(), kDefaultNumberOfSuccessors), 315 loop_information_(nullptr), 316 dominator_(nullptr), 317 dominated_blocks_(graph->GetArena(), kDefaultNumberOfDominatedBlocks), 318 block_id_(-1), 319 dex_pc_(dex_pc), 320 lifetime_start_(kNoLifetime), 321 lifetime_end_(kNoLifetime), 322 is_catch_block_(false) {} 323 324 const GrowableArray<HBasicBlock*>& GetPredecessors() const { 325 return predecessors_; 326 } 327 328 const GrowableArray<HBasicBlock*>& GetSuccessors() const { 329 return successors_; 330 } 331 332 const GrowableArray<HBasicBlock*>& GetDominatedBlocks() const { 333 return dominated_blocks_; 334 } 335 336 bool IsEntryBlock() const { 337 return graph_->GetEntryBlock() == this; 338 } 339 340 bool IsExitBlock() const { 341 return graph_->GetExitBlock() == this; 342 } 343 344 void AddBackEdge(HBasicBlock* back_edge) { 345 if (loop_information_ == nullptr) { 346 loop_information_ = new (graph_->GetArena()) HLoopInformation(this, graph_); 347 } 348 DCHECK_EQ(loop_information_->GetHeader(), this); 349 loop_information_->AddBackEdge(back_edge); 350 } 351 352 HGraph* GetGraph() const { return graph_; } 353 354 int GetBlockId() const { return block_id_; } 355 void SetBlockId(int id) { block_id_ = id; } 356 357 HBasicBlock* GetDominator() const { return dominator_; } 358 void SetDominator(HBasicBlock* dominator) { dominator_ = dominator; } 359 void AddDominatedBlock(HBasicBlock* block) { dominated_blocks_.Add(block); } 360 361 int NumberOfBackEdges() const { 362 return loop_information_ == nullptr 363 ? 0 364 : loop_information_->NumberOfBackEdges(); 365 } 366 367 HInstruction* GetFirstInstruction() const { return instructions_.first_instruction_; } 368 HInstruction* GetLastInstruction() const { return instructions_.last_instruction_; } 369 const HInstructionList& GetInstructions() const { return instructions_; } 370 const HInstructionList& GetPhis() const { return phis_; } 371 HInstruction* GetFirstPhi() const { return phis_.first_instruction_; } 372 373 void AddSuccessor(HBasicBlock* block) { 374 successors_.Add(block); 375 block->predecessors_.Add(this); 376 } 377 378 void ReplaceSuccessor(HBasicBlock* existing, HBasicBlock* new_block) { 379 size_t successor_index = GetSuccessorIndexOf(existing); 380 DCHECK_NE(successor_index, static_cast<size_t>(-1)); 381 existing->RemovePredecessor(this); 382 new_block->predecessors_.Add(this); 383 successors_.Put(successor_index, new_block); 384 } 385 386 void RemovePredecessor(HBasicBlock* block) { 387 predecessors_.Delete(block); 388 } 389 390 void ClearAllPredecessors() { 391 predecessors_.Reset(); 392 } 393 394 void AddPredecessor(HBasicBlock* block) { 395 predecessors_.Add(block); 396 block->successors_.Add(this); 397 } 398 399 void SwapPredecessors() { 400 DCHECK_EQ(predecessors_.Size(), 2u); 401 HBasicBlock* temp = predecessors_.Get(0); 402 predecessors_.Put(0, predecessors_.Get(1)); 403 predecessors_.Put(1, temp); 404 } 405 406 size_t GetPredecessorIndexOf(HBasicBlock* predecessor) { 407 for (size_t i = 0, e = predecessors_.Size(); i < e; ++i) { 408 if (predecessors_.Get(i) == predecessor) { 409 return i; 410 } 411 } 412 return -1; 413 } 414 415 size_t GetSuccessorIndexOf(HBasicBlock* successor) { 416 for (size_t i = 0, e = successors_.Size(); i < e; ++i) { 417 if (successors_.Get(i) == successor) { 418 return i; 419 } 420 } 421 return -1; 422 } 423 424 void AddInstruction(HInstruction* instruction); 425 void RemoveInstruction(HInstruction* instruction); 426 void InsertInstructionBefore(HInstruction* instruction, HInstruction* cursor); 427 // Replace instruction `initial` with `replacement` within this block. 428 void ReplaceAndRemoveInstructionWith(HInstruction* initial, 429 HInstruction* replacement); 430 void AddPhi(HPhi* phi); 431 void InsertPhiAfter(HPhi* instruction, HPhi* cursor); 432 void RemovePhi(HPhi* phi); 433 434 bool IsLoopHeader() const { 435 return (loop_information_ != nullptr) && (loop_information_->GetHeader() == this); 436 } 437 438 bool IsLoopPreHeaderFirstPredecessor() const { 439 DCHECK(IsLoopHeader()); 440 DCHECK(!GetPredecessors().IsEmpty()); 441 return GetPredecessors().Get(0) == GetLoopInformation()->GetPreHeader(); 442 } 443 444 HLoopInformation* GetLoopInformation() const { 445 return loop_information_; 446 } 447 448 // Set the loop_information_ on this block. This method overrides the current 449 // loop_information if it is an outer loop of the passed loop information. 450 void SetInLoop(HLoopInformation* info) { 451 if (IsLoopHeader()) { 452 // Nothing to do. This just means `info` is an outer loop. 453 } else if (loop_information_ == nullptr) { 454 loop_information_ = info; 455 } else if (loop_information_->Contains(*info->GetHeader())) { 456 // Block is currently part of an outer loop. Make it part of this inner loop. 457 // Note that a non loop header having a loop information means this loop information 458 // has already been populated 459 loop_information_ = info; 460 } else { 461 // Block is part of an inner loop. Do not update the loop information. 462 // Note that we cannot do the check `info->Contains(loop_information_)->GetHeader()` 463 // at this point, because this method is being called while populating `info`. 464 } 465 } 466 467 bool IsInLoop() const { return loop_information_ != nullptr; } 468 469 // Returns wheter this block dominates the blocked passed as parameter. 470 bool Dominates(HBasicBlock* block) const; 471 472 size_t GetLifetimeStart() const { return lifetime_start_; } 473 size_t GetLifetimeEnd() const { return lifetime_end_; } 474 475 void SetLifetimeStart(size_t start) { lifetime_start_ = start; } 476 void SetLifetimeEnd(size_t end) { lifetime_end_ = end; } 477 478 uint32_t GetDexPc() const { return dex_pc_; } 479 480 bool IsCatchBlock() const { return is_catch_block_; } 481 void SetIsCatchBlock() { is_catch_block_ = true; } 482 483 private: 484 HGraph* const graph_; 485 GrowableArray<HBasicBlock*> predecessors_; 486 GrowableArray<HBasicBlock*> successors_; 487 HInstructionList instructions_; 488 HInstructionList phis_; 489 HLoopInformation* loop_information_; 490 HBasicBlock* dominator_; 491 GrowableArray<HBasicBlock*> dominated_blocks_; 492 int block_id_; 493 // The dex program counter of the first instruction of this block. 494 const uint32_t dex_pc_; 495 size_t lifetime_start_; 496 size_t lifetime_end_; 497 bool is_catch_block_; 498 499 friend class HGraph; 500 friend class HInstruction; 501 502 DISALLOW_COPY_AND_ASSIGN(HBasicBlock); 503}; 504 505#define FOR_EACH_CONCRETE_INSTRUCTION(M) \ 506 M(Add, BinaryOperation) \ 507 M(And, BinaryOperation) \ 508 M(ArrayGet, Instruction) \ 509 M(ArrayLength, Instruction) \ 510 M(ArraySet, Instruction) \ 511 M(BoundsCheck, Instruction) \ 512 M(CheckCast, Instruction) \ 513 M(ClinitCheck, Instruction) \ 514 M(Compare, BinaryOperation) \ 515 M(Condition, BinaryOperation) \ 516 M(Div, BinaryOperation) \ 517 M(DivZeroCheck, Instruction) \ 518 M(DoubleConstant, Constant) \ 519 M(Equal, Condition) \ 520 M(Exit, Instruction) \ 521 M(FloatConstant, Constant) \ 522 M(Goto, Instruction) \ 523 M(GreaterThan, Condition) \ 524 M(GreaterThanOrEqual, Condition) \ 525 M(If, Instruction) \ 526 M(InstanceFieldGet, Instruction) \ 527 M(InstanceFieldSet, Instruction) \ 528 M(InstanceOf, Instruction) \ 529 M(IntConstant, Constant) \ 530 M(InvokeInterface, Invoke) \ 531 M(InvokeStaticOrDirect, Invoke) \ 532 M(InvokeVirtual, Invoke) \ 533 M(LessThan, Condition) \ 534 M(LessThanOrEqual, Condition) \ 535 M(LoadClass, Instruction) \ 536 M(LoadException, Instruction) \ 537 M(LoadLocal, Instruction) \ 538 M(LoadString, Instruction) \ 539 M(Local, Instruction) \ 540 M(LongConstant, Constant) \ 541 M(MonitorOperation, Instruction) \ 542 M(Mul, BinaryOperation) \ 543 M(Neg, UnaryOperation) \ 544 M(NewArray, Instruction) \ 545 M(NewInstance, Instruction) \ 546 M(Not, UnaryOperation) \ 547 M(NotEqual, Condition) \ 548 M(NullCheck, Instruction) \ 549 M(Or, BinaryOperation) \ 550 M(ParallelMove, Instruction) \ 551 M(ParameterValue, Instruction) \ 552 M(Phi, Instruction) \ 553 M(Rem, BinaryOperation) \ 554 M(Return, Instruction) \ 555 M(ReturnVoid, Instruction) \ 556 M(Shl, BinaryOperation) \ 557 M(Shr, BinaryOperation) \ 558 M(StaticFieldGet, Instruction) \ 559 M(StaticFieldSet, Instruction) \ 560 M(StoreLocal, Instruction) \ 561 M(Sub, BinaryOperation) \ 562 M(SuspendCheck, Instruction) \ 563 M(Temporary, Instruction) \ 564 M(Throw, Instruction) \ 565 M(TypeConversion, Instruction) \ 566 M(UShr, BinaryOperation) \ 567 M(Xor, BinaryOperation) \ 568 569#define FOR_EACH_INSTRUCTION(M) \ 570 FOR_EACH_CONCRETE_INSTRUCTION(M) \ 571 M(Constant, Instruction) \ 572 M(UnaryOperation, Instruction) \ 573 M(BinaryOperation, Instruction) \ 574 M(Invoke, Instruction) 575 576#define FORWARD_DECLARATION(type, super) class H##type; 577FOR_EACH_INSTRUCTION(FORWARD_DECLARATION) 578#undef FORWARD_DECLARATION 579 580#define DECLARE_INSTRUCTION(type) \ 581 virtual InstructionKind GetKind() const { return k##type; } \ 582 virtual const char* DebugName() const { return #type; } \ 583 virtual const H##type* As##type() const OVERRIDE { return this; } \ 584 virtual H##type* As##type() OVERRIDE { return this; } \ 585 virtual bool InstructionTypeEquals(HInstruction* other) const { \ 586 return other->Is##type(); \ 587 } \ 588 virtual void Accept(HGraphVisitor* visitor) 589 590template <typename T> class HUseList; 591 592template <typename T> 593class HUseListNode : public ArenaObject<kArenaAllocMisc> { 594 public: 595 HUseListNode* GetPrevious() const { return prev_; } 596 HUseListNode* GetNext() const { return next_; } 597 T GetUser() const { return user_; } 598 size_t GetIndex() const { return index_; } 599 600 private: 601 HUseListNode(T user, size_t index) 602 : user_(user), index_(index), prev_(nullptr), next_(nullptr) {} 603 604 T const user_; 605 const size_t index_; 606 HUseListNode<T>* prev_; 607 HUseListNode<T>* next_; 608 609 friend class HUseList<T>; 610 611 DISALLOW_COPY_AND_ASSIGN(HUseListNode); 612}; 613 614template <typename T> 615class HUseList : public ValueObject { 616 public: 617 HUseList() : first_(nullptr) {} 618 619 void Clear() { 620 first_ = nullptr; 621 } 622 623 // Adds a new entry at the beginning of the use list and returns 624 // the newly created node. 625 HUseListNode<T>* AddUse(T user, size_t index, ArenaAllocator* arena) { 626 HUseListNode<T>* new_node = new (arena) HUseListNode<T>(user, index); 627 if (IsEmpty()) { 628 first_ = new_node; 629 } else { 630 first_->prev_ = new_node; 631 new_node->next_ = first_; 632 first_ = new_node; 633 } 634 return new_node; 635 } 636 637 HUseListNode<T>* GetFirst() const { 638 return first_; 639 } 640 641 void Remove(HUseListNode<T>* node) { 642 if (node->prev_ != nullptr) { 643 node->prev_->next_ = node->next_; 644 } 645 if (node->next_ != nullptr) { 646 node->next_->prev_ = node->prev_; 647 } 648 if (node == first_) { 649 first_ = node->next_; 650 } 651 } 652 653 bool IsEmpty() const { 654 return first_ == nullptr; 655 } 656 657 bool HasOnlyOneUse() const { 658 return first_ != nullptr && first_->next_ == nullptr; 659 } 660 661 private: 662 HUseListNode<T>* first_; 663}; 664 665template<typename T> 666class HUseIterator : public ValueObject { 667 public: 668 explicit HUseIterator(const HUseList<T>& uses) : current_(uses.GetFirst()) {} 669 670 bool Done() const { return current_ == nullptr; } 671 672 void Advance() { 673 DCHECK(!Done()); 674 current_ = current_->GetNext(); 675 } 676 677 HUseListNode<T>* Current() const { 678 DCHECK(!Done()); 679 return current_; 680 } 681 682 private: 683 HUseListNode<T>* current_; 684 685 friend class HValue; 686}; 687 688// Represents the side effects an instruction may have. 689class SideEffects : public ValueObject { 690 public: 691 SideEffects() : flags_(0) {} 692 693 static SideEffects None() { 694 return SideEffects(0); 695 } 696 697 static SideEffects All() { 698 return SideEffects(ChangesSomething().flags_ | DependsOnSomething().flags_); 699 } 700 701 static SideEffects ChangesSomething() { 702 return SideEffects((1 << kFlagChangesCount) - 1); 703 } 704 705 static SideEffects DependsOnSomething() { 706 int count = kFlagDependsOnCount - kFlagChangesCount; 707 return SideEffects(((1 << count) - 1) << kFlagChangesCount); 708 } 709 710 SideEffects Union(SideEffects other) const { 711 return SideEffects(flags_ | other.flags_); 712 } 713 714 bool HasSideEffects() const { 715 size_t all_bits_set = (1 << kFlagChangesCount) - 1; 716 return (flags_ & all_bits_set) != 0; 717 } 718 719 bool HasAllSideEffects() const { 720 size_t all_bits_set = (1 << kFlagChangesCount) - 1; 721 return all_bits_set == (flags_ & all_bits_set); 722 } 723 724 bool DependsOn(SideEffects other) const { 725 size_t depends_flags = other.ComputeDependsFlags(); 726 return (flags_ & depends_flags) != 0; 727 } 728 729 bool HasDependencies() const { 730 int count = kFlagDependsOnCount - kFlagChangesCount; 731 size_t all_bits_set = (1 << count) - 1; 732 return ((flags_ >> kFlagChangesCount) & all_bits_set) != 0; 733 } 734 735 private: 736 static constexpr int kFlagChangesSomething = 0; 737 static constexpr int kFlagChangesCount = kFlagChangesSomething + 1; 738 739 static constexpr int kFlagDependsOnSomething = kFlagChangesCount; 740 static constexpr int kFlagDependsOnCount = kFlagDependsOnSomething + 1; 741 742 explicit SideEffects(size_t flags) : flags_(flags) {} 743 744 size_t ComputeDependsFlags() const { 745 return flags_ << kFlagChangesCount; 746 } 747 748 size_t flags_; 749}; 750 751// A HEnvironment object contains the values of virtual registers at a given location. 752class HEnvironment : public ArenaObject<kArenaAllocMisc> { 753 public: 754 HEnvironment(ArenaAllocator* arena, size_t number_of_vregs) 755 : vregs_(arena, number_of_vregs) { 756 vregs_.SetSize(number_of_vregs); 757 for (size_t i = 0; i < number_of_vregs; i++) { 758 vregs_.Put(i, VRegInfo(nullptr, nullptr)); 759 } 760 } 761 762 void CopyFrom(HEnvironment* env); 763 764 void SetRawEnvAt(size_t index, HInstruction* instruction) { 765 vregs_.Put(index, VRegInfo(instruction, nullptr)); 766 } 767 768 // Record instructions' use entries of this environment for constant-time removal. 769 void RecordEnvUse(HUseListNode<HEnvironment*>* env_use) { 770 DCHECK(env_use->GetUser() == this); 771 size_t index = env_use->GetIndex(); 772 VRegInfo info = vregs_.Get(index); 773 DCHECK(info.vreg_ != nullptr); 774 DCHECK(info.node_ == nullptr); 775 vregs_.Put(index, VRegInfo(info.vreg_, env_use)); 776 } 777 778 HInstruction* GetInstructionAt(size_t index) const { 779 return vregs_.Get(index).vreg_; 780 } 781 782 HUseListNode<HEnvironment*>* GetInstructionEnvUseAt(size_t index) const { 783 return vregs_.Get(index).node_; 784 } 785 786 size_t Size() const { return vregs_.Size(); } 787 788 private: 789 struct VRegInfo { 790 HInstruction* vreg_; 791 HUseListNode<HEnvironment*>* node_; 792 793 VRegInfo(HInstruction* instruction, HUseListNode<HEnvironment*>* env_use) 794 : vreg_(instruction), node_(env_use) {} 795 }; 796 797 GrowableArray<VRegInfo> vregs_; 798 799 DISALLOW_COPY_AND_ASSIGN(HEnvironment); 800}; 801 802class HInstruction : public ArenaObject<kArenaAllocMisc> { 803 public: 804 explicit HInstruction(SideEffects side_effects) 805 : previous_(nullptr), 806 next_(nullptr), 807 block_(nullptr), 808 id_(-1), 809 ssa_index_(-1), 810 environment_(nullptr), 811 locations_(nullptr), 812 live_interval_(nullptr), 813 lifetime_position_(kNoLifetime), 814 side_effects_(side_effects) {} 815 816 virtual ~HInstruction() {} 817 818#define DECLARE_KIND(type, super) k##type, 819 enum InstructionKind { 820 FOR_EACH_INSTRUCTION(DECLARE_KIND) 821 }; 822#undef DECLARE_KIND 823 824 HInstruction* GetNext() const { return next_; } 825 HInstruction* GetPrevious() const { return previous_; } 826 827 HInstruction* GetNextDisregardingMoves() const; 828 HInstruction* GetPreviousDisregardingMoves() const; 829 830 HBasicBlock* GetBlock() const { return block_; } 831 void SetBlock(HBasicBlock* block) { block_ = block; } 832 bool IsInBlock() const { return block_ != nullptr; } 833 bool IsInLoop() const { return block_->IsInLoop(); } 834 bool IsLoopHeaderPhi() { return IsPhi() && block_->IsLoopHeader(); } 835 836 virtual size_t InputCount() const = 0; 837 virtual HInstruction* InputAt(size_t i) const = 0; 838 839 virtual void Accept(HGraphVisitor* visitor) = 0; 840 virtual const char* DebugName() const = 0; 841 842 virtual Primitive::Type GetType() const { return Primitive::kPrimVoid; } 843 virtual void SetRawInputAt(size_t index, HInstruction* input) = 0; 844 845 virtual bool NeedsEnvironment() const { return false; } 846 virtual bool IsControlFlow() const { return false; } 847 virtual bool CanThrow() const { return false; } 848 bool HasSideEffects() const { return side_effects_.HasSideEffects(); } 849 850 virtual bool CanDoImplicitNullCheck() const { return false; } 851 852 void AddUseAt(HInstruction* user, size_t index) { 853 uses_.AddUse(user, index, GetBlock()->GetGraph()->GetArena()); 854 } 855 856 void AddEnvUseAt(HEnvironment* user, size_t index) { 857 DCHECK(user != nullptr); 858 HUseListNode<HEnvironment*>* env_use = 859 env_uses_.AddUse(user, index, GetBlock()->GetGraph()->GetArena()); 860 user->RecordEnvUse(env_use); 861 } 862 863 void RemoveUser(HInstruction* user, size_t index); 864 void RemoveEnvironmentUser(HUseListNode<HEnvironment*>* use); 865 866 const HUseList<HInstruction*>& GetUses() { return uses_; } 867 const HUseList<HEnvironment*>& GetEnvUses() { return env_uses_; } 868 869 bool HasUses() const { return !uses_.IsEmpty() || !env_uses_.IsEmpty(); } 870 bool HasEnvironmentUses() const { return !env_uses_.IsEmpty(); } 871 872 // Does this instruction strictly dominate `other_instruction`? 873 // Returns false if this instruction and `other_instruction` are the same. 874 // Aborts if this instruction and `other_instruction` are both phis. 875 bool StrictlyDominates(HInstruction* other_instruction) const; 876 877 int GetId() const { return id_; } 878 void SetId(int id) { id_ = id; } 879 880 int GetSsaIndex() const { return ssa_index_; } 881 void SetSsaIndex(int ssa_index) { ssa_index_ = ssa_index; } 882 bool HasSsaIndex() const { return ssa_index_ != -1; } 883 884 bool HasEnvironment() const { return environment_ != nullptr; } 885 HEnvironment* GetEnvironment() const { return environment_; } 886 void SetEnvironment(HEnvironment* environment) { environment_ = environment; } 887 888 // Returns the number of entries in the environment. Typically, that is the 889 // number of dex registers in a method. It could be more in case of inlining. 890 size_t EnvironmentSize() const; 891 892 LocationSummary* GetLocations() const { return locations_; } 893 void SetLocations(LocationSummary* locations) { locations_ = locations; } 894 895 void ReplaceWith(HInstruction* instruction); 896 void ReplaceInput(HInstruction* replacement, size_t index); 897 898 // Insert `this` instruction in `cursor`'s graph, just before `cursor`. 899 void InsertBefore(HInstruction* cursor); 900 901#define INSTRUCTION_TYPE_CHECK(type, super) \ 902 bool Is##type() const { return (As##type() != nullptr); } \ 903 virtual const H##type* As##type() const { return nullptr; } \ 904 virtual H##type* As##type() { return nullptr; } 905 906 FOR_EACH_INSTRUCTION(INSTRUCTION_TYPE_CHECK) 907#undef INSTRUCTION_TYPE_CHECK 908 909 // Returns whether the instruction can be moved within the graph. 910 virtual bool CanBeMoved() const { return false; } 911 912 // Returns whether the two instructions are of the same kind. 913 virtual bool InstructionTypeEquals(HInstruction* other) const { 914 UNUSED(other); 915 return false; 916 } 917 918 // Returns whether any data encoded in the two instructions is equal. 919 // This method does not look at the inputs. Both instructions must be 920 // of the same type, otherwise the method has undefined behavior. 921 virtual bool InstructionDataEquals(HInstruction* other) const { 922 UNUSED(other); 923 return false; 924 } 925 926 // Returns whether two instructions are equal, that is: 927 // 1) They have the same type and contain the same data (InstructionDataEquals). 928 // 2) Their inputs are identical. 929 bool Equals(HInstruction* other) const; 930 931 virtual InstructionKind GetKind() const = 0; 932 933 virtual size_t ComputeHashCode() const { 934 size_t result = GetKind(); 935 for (size_t i = 0, e = InputCount(); i < e; ++i) { 936 result = (result * 31) + InputAt(i)->GetId(); 937 } 938 return result; 939 } 940 941 SideEffects GetSideEffects() const { return side_effects_; } 942 943 size_t GetLifetimePosition() const { return lifetime_position_; } 944 void SetLifetimePosition(size_t position) { lifetime_position_ = position; } 945 LiveInterval* GetLiveInterval() const { return live_interval_; } 946 void SetLiveInterval(LiveInterval* interval) { live_interval_ = interval; } 947 bool HasLiveInterval() const { return live_interval_ != nullptr; } 948 949 private: 950 HInstruction* previous_; 951 HInstruction* next_; 952 HBasicBlock* block_; 953 954 // An instruction gets an id when it is added to the graph. 955 // It reflects creation order. A negative id means the instruction 956 // has not been added to the graph. 957 int id_; 958 959 // When doing liveness analysis, instructions that have uses get an SSA index. 960 int ssa_index_; 961 962 // List of instructions that have this instruction as input. 963 HUseList<HInstruction*> uses_; 964 965 // List of environments that contain this instruction. 966 HUseList<HEnvironment*> env_uses_; 967 968 // The environment associated with this instruction. Not null if the instruction 969 // might jump out of the method. 970 HEnvironment* environment_; 971 972 // Set by the code generator. 973 LocationSummary* locations_; 974 975 // Set by the liveness analysis. 976 LiveInterval* live_interval_; 977 978 // Set by the liveness analysis, this is the position in a linear 979 // order of blocks where this instruction's live interval start. 980 size_t lifetime_position_; 981 982 const SideEffects side_effects_; 983 984 friend class HBasicBlock; 985 friend class HGraph; 986 friend class HInstructionList; 987 988 DISALLOW_COPY_AND_ASSIGN(HInstruction); 989}; 990std::ostream& operator<<(std::ostream& os, const HInstruction::InstructionKind& rhs); 991 992class HInputIterator : public ValueObject { 993 public: 994 explicit HInputIterator(HInstruction* instruction) : instruction_(instruction), index_(0) {} 995 996 bool Done() const { return index_ == instruction_->InputCount(); } 997 HInstruction* Current() const { return instruction_->InputAt(index_); } 998 void Advance() { index_++; } 999 1000 private: 1001 HInstruction* instruction_; 1002 size_t index_; 1003 1004 DISALLOW_COPY_AND_ASSIGN(HInputIterator); 1005}; 1006 1007class HInstructionIterator : public ValueObject { 1008 public: 1009 explicit HInstructionIterator(const HInstructionList& instructions) 1010 : instruction_(instructions.first_instruction_) { 1011 next_ = Done() ? nullptr : instruction_->GetNext(); 1012 } 1013 1014 bool Done() const { return instruction_ == nullptr; } 1015 HInstruction* Current() const { return instruction_; } 1016 void Advance() { 1017 instruction_ = next_; 1018 next_ = Done() ? nullptr : instruction_->GetNext(); 1019 } 1020 1021 private: 1022 HInstruction* instruction_; 1023 HInstruction* next_; 1024 1025 DISALLOW_COPY_AND_ASSIGN(HInstructionIterator); 1026}; 1027 1028class HBackwardInstructionIterator : public ValueObject { 1029 public: 1030 explicit HBackwardInstructionIterator(const HInstructionList& instructions) 1031 : instruction_(instructions.last_instruction_) { 1032 next_ = Done() ? nullptr : instruction_->GetPrevious(); 1033 } 1034 1035 bool Done() const { return instruction_ == nullptr; } 1036 HInstruction* Current() const { return instruction_; } 1037 void Advance() { 1038 instruction_ = next_; 1039 next_ = Done() ? nullptr : instruction_->GetPrevious(); 1040 } 1041 1042 private: 1043 HInstruction* instruction_; 1044 HInstruction* next_; 1045 1046 DISALLOW_COPY_AND_ASSIGN(HBackwardInstructionIterator); 1047}; 1048 1049// An embedded container with N elements of type T. Used (with partial 1050// specialization for N=0) because embedded arrays cannot have size 0. 1051template<typename T, intptr_t N> 1052class EmbeddedArray { 1053 public: 1054 EmbeddedArray() : elements_() {} 1055 1056 intptr_t GetLength() const { return N; } 1057 1058 const T& operator[](intptr_t i) const { 1059 DCHECK_LT(i, GetLength()); 1060 return elements_[i]; 1061 } 1062 1063 T& operator[](intptr_t i) { 1064 DCHECK_LT(i, GetLength()); 1065 return elements_[i]; 1066 } 1067 1068 const T& At(intptr_t i) const { 1069 return (*this)[i]; 1070 } 1071 1072 void SetAt(intptr_t i, const T& val) { 1073 (*this)[i] = val; 1074 } 1075 1076 private: 1077 T elements_[N]; 1078}; 1079 1080template<typename T> 1081class EmbeddedArray<T, 0> { 1082 public: 1083 intptr_t length() const { return 0; } 1084 const T& operator[](intptr_t i) const { 1085 UNUSED(i); 1086 LOG(FATAL) << "Unreachable"; 1087 UNREACHABLE(); 1088 } 1089 T& operator[](intptr_t i) { 1090 UNUSED(i); 1091 LOG(FATAL) << "Unreachable"; 1092 UNREACHABLE(); 1093 } 1094}; 1095 1096template<intptr_t N> 1097class HTemplateInstruction: public HInstruction { 1098 public: 1099 HTemplateInstruction<N>(SideEffects side_effects) 1100 : HInstruction(side_effects), inputs_() {} 1101 virtual ~HTemplateInstruction() {} 1102 1103 virtual size_t InputCount() const { return N; } 1104 virtual HInstruction* InputAt(size_t i) const { return inputs_[i]; } 1105 1106 protected: 1107 virtual void SetRawInputAt(size_t i, HInstruction* instruction) { 1108 inputs_[i] = instruction; 1109 } 1110 1111 private: 1112 EmbeddedArray<HInstruction*, N> inputs_; 1113 1114 friend class SsaBuilder; 1115}; 1116 1117template<intptr_t N> 1118class HExpression : public HTemplateInstruction<N> { 1119 public: 1120 HExpression<N>(Primitive::Type type, SideEffects side_effects) 1121 : HTemplateInstruction<N>(side_effects), type_(type) {} 1122 virtual ~HExpression() {} 1123 1124 virtual Primitive::Type GetType() const { return type_; } 1125 1126 protected: 1127 Primitive::Type type_; 1128}; 1129 1130// Represents dex's RETURN_VOID opcode. A HReturnVoid is a control flow 1131// instruction that branches to the exit block. 1132class HReturnVoid : public HTemplateInstruction<0> { 1133 public: 1134 HReturnVoid() : HTemplateInstruction(SideEffects::None()) {} 1135 1136 virtual bool IsControlFlow() const { return true; } 1137 1138 DECLARE_INSTRUCTION(ReturnVoid); 1139 1140 private: 1141 DISALLOW_COPY_AND_ASSIGN(HReturnVoid); 1142}; 1143 1144// Represents dex's RETURN opcodes. A HReturn is a control flow 1145// instruction that branches to the exit block. 1146class HReturn : public HTemplateInstruction<1> { 1147 public: 1148 explicit HReturn(HInstruction* value) : HTemplateInstruction(SideEffects::None()) { 1149 SetRawInputAt(0, value); 1150 } 1151 1152 virtual bool IsControlFlow() const { return true; } 1153 1154 DECLARE_INSTRUCTION(Return); 1155 1156 private: 1157 DISALLOW_COPY_AND_ASSIGN(HReturn); 1158}; 1159 1160// The exit instruction is the only instruction of the exit block. 1161// Instructions aborting the method (HThrow and HReturn) must branch to the 1162// exit block. 1163class HExit : public HTemplateInstruction<0> { 1164 public: 1165 HExit() : HTemplateInstruction(SideEffects::None()) {} 1166 1167 virtual bool IsControlFlow() const { return true; } 1168 1169 DECLARE_INSTRUCTION(Exit); 1170 1171 private: 1172 DISALLOW_COPY_AND_ASSIGN(HExit); 1173}; 1174 1175// Jumps from one block to another. 1176class HGoto : public HTemplateInstruction<0> { 1177 public: 1178 HGoto() : HTemplateInstruction(SideEffects::None()) {} 1179 1180 bool IsControlFlow() const OVERRIDE { return true; } 1181 1182 HBasicBlock* GetSuccessor() const { 1183 return GetBlock()->GetSuccessors().Get(0); 1184 } 1185 1186 DECLARE_INSTRUCTION(Goto); 1187 1188 private: 1189 DISALLOW_COPY_AND_ASSIGN(HGoto); 1190}; 1191 1192 1193// Conditional branch. A block ending with an HIf instruction must have 1194// two successors. 1195class HIf : public HTemplateInstruction<1> { 1196 public: 1197 explicit HIf(HInstruction* input) : HTemplateInstruction(SideEffects::None()) { 1198 SetRawInputAt(0, input); 1199 } 1200 1201 bool IsControlFlow() const OVERRIDE { return true; } 1202 1203 HBasicBlock* IfTrueSuccessor() const { 1204 return GetBlock()->GetSuccessors().Get(0); 1205 } 1206 1207 HBasicBlock* IfFalseSuccessor() const { 1208 return GetBlock()->GetSuccessors().Get(1); 1209 } 1210 1211 DECLARE_INSTRUCTION(If); 1212 1213 virtual bool IsIfInstruction() const { return true; } 1214 1215 private: 1216 DISALLOW_COPY_AND_ASSIGN(HIf); 1217}; 1218 1219class HUnaryOperation : public HExpression<1> { 1220 public: 1221 HUnaryOperation(Primitive::Type result_type, HInstruction* input) 1222 : HExpression(result_type, SideEffects::None()) { 1223 SetRawInputAt(0, input); 1224 } 1225 1226 HInstruction* GetInput() const { return InputAt(0); } 1227 Primitive::Type GetResultType() const { return GetType(); } 1228 1229 virtual bool CanBeMoved() const { return true; } 1230 virtual bool InstructionDataEquals(HInstruction* other) const { 1231 UNUSED(other); 1232 return true; 1233 } 1234 1235 // Try to statically evaluate `operation` and return a HConstant 1236 // containing the result of this evaluation. If `operation` cannot 1237 // be evaluated as a constant, return nullptr. 1238 HConstant* TryStaticEvaluation() const; 1239 1240 // Apply this operation to `x`. 1241 virtual int32_t Evaluate(int32_t x) const = 0; 1242 virtual int64_t Evaluate(int64_t x) const = 0; 1243 1244 DECLARE_INSTRUCTION(UnaryOperation); 1245 1246 private: 1247 DISALLOW_COPY_AND_ASSIGN(HUnaryOperation); 1248}; 1249 1250class HBinaryOperation : public HExpression<2> { 1251 public: 1252 HBinaryOperation(Primitive::Type result_type, 1253 HInstruction* left, 1254 HInstruction* right) : HExpression(result_type, SideEffects::None()) { 1255 SetRawInputAt(0, left); 1256 SetRawInputAt(1, right); 1257 } 1258 1259 HInstruction* GetLeft() const { return InputAt(0); } 1260 HInstruction* GetRight() const { return InputAt(1); } 1261 Primitive::Type GetResultType() const { return GetType(); } 1262 1263 virtual bool IsCommutative() { return false; } 1264 1265 virtual bool CanBeMoved() const { return true; } 1266 virtual bool InstructionDataEquals(HInstruction* other) const { 1267 UNUSED(other); 1268 return true; 1269 } 1270 1271 // Try to statically evaluate `operation` and return a HConstant 1272 // containing the result of this evaluation. If `operation` cannot 1273 // be evaluated as a constant, return nullptr. 1274 HConstant* TryStaticEvaluation() const; 1275 1276 // Apply this operation to `x` and `y`. 1277 virtual int32_t Evaluate(int32_t x, int32_t y) const = 0; 1278 virtual int64_t Evaluate(int64_t x, int64_t y) const = 0; 1279 1280 DECLARE_INSTRUCTION(BinaryOperation); 1281 1282 private: 1283 DISALLOW_COPY_AND_ASSIGN(HBinaryOperation); 1284}; 1285 1286class HCondition : public HBinaryOperation { 1287 public: 1288 HCondition(HInstruction* first, HInstruction* second) 1289 : HBinaryOperation(Primitive::kPrimBoolean, first, second), 1290 needs_materialization_(true) {} 1291 1292 virtual bool IsCommutative() { return true; } 1293 1294 bool NeedsMaterialization() const { return needs_materialization_; } 1295 void ClearNeedsMaterialization() { needs_materialization_ = false; } 1296 1297 // For code generation purposes, returns whether this instruction is just before 1298 // `if_`, and disregard moves in between. 1299 bool IsBeforeWhenDisregardMoves(HIf* if_) const; 1300 1301 DECLARE_INSTRUCTION(Condition); 1302 1303 virtual IfCondition GetCondition() const = 0; 1304 1305 private: 1306 // For register allocation purposes, returns whether this instruction needs to be 1307 // materialized (that is, not just be in the processor flags). 1308 bool needs_materialization_; 1309 1310 DISALLOW_COPY_AND_ASSIGN(HCondition); 1311}; 1312 1313// Instruction to check if two inputs are equal to each other. 1314class HEqual : public HCondition { 1315 public: 1316 HEqual(HInstruction* first, HInstruction* second) 1317 : HCondition(first, second) {} 1318 1319 virtual int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE { 1320 return x == y ? 1 : 0; 1321 } 1322 virtual int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE { 1323 return x == y ? 1 : 0; 1324 } 1325 1326 DECLARE_INSTRUCTION(Equal); 1327 1328 virtual IfCondition GetCondition() const { 1329 return kCondEQ; 1330 } 1331 1332 private: 1333 DISALLOW_COPY_AND_ASSIGN(HEqual); 1334}; 1335 1336class HNotEqual : public HCondition { 1337 public: 1338 HNotEqual(HInstruction* first, HInstruction* second) 1339 : HCondition(first, second) {} 1340 1341 virtual int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE { 1342 return x != y ? 1 : 0; 1343 } 1344 virtual int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE { 1345 return x != y ? 1 : 0; 1346 } 1347 1348 DECLARE_INSTRUCTION(NotEqual); 1349 1350 virtual IfCondition GetCondition() const { 1351 return kCondNE; 1352 } 1353 1354 private: 1355 DISALLOW_COPY_AND_ASSIGN(HNotEqual); 1356}; 1357 1358class HLessThan : public HCondition { 1359 public: 1360 HLessThan(HInstruction* first, HInstruction* second) 1361 : HCondition(first, second) {} 1362 1363 virtual int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE { 1364 return x < y ? 1 : 0; 1365 } 1366 virtual int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE { 1367 return x < y ? 1 : 0; 1368 } 1369 1370 DECLARE_INSTRUCTION(LessThan); 1371 1372 virtual IfCondition GetCondition() const { 1373 return kCondLT; 1374 } 1375 1376 private: 1377 DISALLOW_COPY_AND_ASSIGN(HLessThan); 1378}; 1379 1380class HLessThanOrEqual : public HCondition { 1381 public: 1382 HLessThanOrEqual(HInstruction* first, HInstruction* second) 1383 : HCondition(first, second) {} 1384 1385 virtual int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE { 1386 return x <= y ? 1 : 0; 1387 } 1388 virtual int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE { 1389 return x <= y ? 1 : 0; 1390 } 1391 1392 DECLARE_INSTRUCTION(LessThanOrEqual); 1393 1394 virtual IfCondition GetCondition() const { 1395 return kCondLE; 1396 } 1397 1398 private: 1399 DISALLOW_COPY_AND_ASSIGN(HLessThanOrEqual); 1400}; 1401 1402class HGreaterThan : public HCondition { 1403 public: 1404 HGreaterThan(HInstruction* first, HInstruction* second) 1405 : HCondition(first, second) {} 1406 1407 virtual int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE { 1408 return x > y ? 1 : 0; 1409 } 1410 virtual int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE { 1411 return x > y ? 1 : 0; 1412 } 1413 1414 DECLARE_INSTRUCTION(GreaterThan); 1415 1416 virtual IfCondition GetCondition() const { 1417 return kCondGT; 1418 } 1419 1420 private: 1421 DISALLOW_COPY_AND_ASSIGN(HGreaterThan); 1422}; 1423 1424class HGreaterThanOrEqual : public HCondition { 1425 public: 1426 HGreaterThanOrEqual(HInstruction* first, HInstruction* second) 1427 : HCondition(first, second) {} 1428 1429 virtual int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE { 1430 return x >= y ? 1 : 0; 1431 } 1432 virtual int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE { 1433 return x >= y ? 1 : 0; 1434 } 1435 1436 DECLARE_INSTRUCTION(GreaterThanOrEqual); 1437 1438 virtual IfCondition GetCondition() const { 1439 return kCondGE; 1440 } 1441 1442 private: 1443 DISALLOW_COPY_AND_ASSIGN(HGreaterThanOrEqual); 1444}; 1445 1446 1447// Instruction to check how two inputs compare to each other. 1448// Result is 0 if input0 == input1, 1 if input0 > input1, or -1 if input0 < input1. 1449class HCompare : public HBinaryOperation { 1450 public: 1451 // The bias applies for floating point operations and indicates how NaN 1452 // comparisons are treated: 1453 enum Bias { 1454 kNoBias, // bias is not applicable (i.e. for long operation) 1455 kGtBias, // return 1 for NaN comparisons 1456 kLtBias, // return -1 for NaN comparisons 1457 }; 1458 1459 HCompare(Primitive::Type type, HInstruction* first, HInstruction* second, Bias bias) 1460 : HBinaryOperation(Primitive::kPrimInt, first, second), bias_(bias) { 1461 DCHECK_EQ(type, first->GetType()); 1462 DCHECK_EQ(type, second->GetType()); 1463 } 1464 1465 int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE { 1466 return 1467 x == y ? 0 : 1468 x > y ? 1 : 1469 -1; 1470 } 1471 1472 int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE { 1473 return 1474 x == y ? 0 : 1475 x > y ? 1 : 1476 -1; 1477 } 1478 1479 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 1480 return bias_ == other->AsCompare()->bias_; 1481 } 1482 1483 bool IsGtBias() { return bias_ == kGtBias; } 1484 1485 DECLARE_INSTRUCTION(Compare); 1486 1487 private: 1488 const Bias bias_; 1489 1490 DISALLOW_COPY_AND_ASSIGN(HCompare); 1491}; 1492 1493// A local in the graph. Corresponds to a Dex register. 1494class HLocal : public HTemplateInstruction<0> { 1495 public: 1496 explicit HLocal(uint16_t reg_number) 1497 : HTemplateInstruction(SideEffects::None()), reg_number_(reg_number) {} 1498 1499 DECLARE_INSTRUCTION(Local); 1500 1501 uint16_t GetRegNumber() const { return reg_number_; } 1502 1503 private: 1504 // The Dex register number. 1505 const uint16_t reg_number_; 1506 1507 DISALLOW_COPY_AND_ASSIGN(HLocal); 1508}; 1509 1510// Load a given local. The local is an input of this instruction. 1511class HLoadLocal : public HExpression<1> { 1512 public: 1513 HLoadLocal(HLocal* local, Primitive::Type type) 1514 : HExpression(type, SideEffects::None()) { 1515 SetRawInputAt(0, local); 1516 } 1517 1518 HLocal* GetLocal() const { return reinterpret_cast<HLocal*>(InputAt(0)); } 1519 1520 DECLARE_INSTRUCTION(LoadLocal); 1521 1522 private: 1523 DISALLOW_COPY_AND_ASSIGN(HLoadLocal); 1524}; 1525 1526// Store a value in a given local. This instruction has two inputs: the value 1527// and the local. 1528class HStoreLocal : public HTemplateInstruction<2> { 1529 public: 1530 HStoreLocal(HLocal* local, HInstruction* value) : HTemplateInstruction(SideEffects::None()) { 1531 SetRawInputAt(0, local); 1532 SetRawInputAt(1, value); 1533 } 1534 1535 HLocal* GetLocal() const { return reinterpret_cast<HLocal*>(InputAt(0)); } 1536 1537 DECLARE_INSTRUCTION(StoreLocal); 1538 1539 private: 1540 DISALLOW_COPY_AND_ASSIGN(HStoreLocal); 1541}; 1542 1543class HConstant : public HExpression<0> { 1544 public: 1545 explicit HConstant(Primitive::Type type) : HExpression(type, SideEffects::None()) {} 1546 1547 virtual bool CanBeMoved() const { return true; } 1548 1549 DECLARE_INSTRUCTION(Constant); 1550 1551 private: 1552 DISALLOW_COPY_AND_ASSIGN(HConstant); 1553}; 1554 1555class HFloatConstant : public HConstant { 1556 public: 1557 explicit HFloatConstant(float value) : HConstant(Primitive::kPrimFloat), value_(value) {} 1558 1559 float GetValue() const { return value_; } 1560 1561 virtual bool InstructionDataEquals(HInstruction* other) const { 1562 return bit_cast<float, int32_t>(other->AsFloatConstant()->value_) == 1563 bit_cast<float, int32_t>(value_); 1564 } 1565 1566 virtual size_t ComputeHashCode() const { return static_cast<size_t>(GetValue()); } 1567 1568 DECLARE_INSTRUCTION(FloatConstant); 1569 1570 private: 1571 const float value_; 1572 1573 DISALLOW_COPY_AND_ASSIGN(HFloatConstant); 1574}; 1575 1576class HDoubleConstant : public HConstant { 1577 public: 1578 explicit HDoubleConstant(double value) : HConstant(Primitive::kPrimDouble), value_(value) {} 1579 1580 double GetValue() const { return value_; } 1581 1582 virtual bool InstructionDataEquals(HInstruction* other) const { 1583 return bit_cast<double, int64_t>(other->AsDoubleConstant()->value_) == 1584 bit_cast<double, int64_t>(value_); 1585 } 1586 1587 virtual size_t ComputeHashCode() const { return static_cast<size_t>(GetValue()); } 1588 1589 DECLARE_INSTRUCTION(DoubleConstant); 1590 1591 private: 1592 const double value_; 1593 1594 DISALLOW_COPY_AND_ASSIGN(HDoubleConstant); 1595}; 1596 1597// Constants of the type int. Those can be from Dex instructions, or 1598// synthesized (for example with the if-eqz instruction). 1599class HIntConstant : public HConstant { 1600 public: 1601 explicit HIntConstant(int32_t value) : HConstant(Primitive::kPrimInt), value_(value) {} 1602 1603 int32_t GetValue() const { return value_; } 1604 1605 virtual bool InstructionDataEquals(HInstruction* other) const { 1606 return other->AsIntConstant()->value_ == value_; 1607 } 1608 1609 virtual size_t ComputeHashCode() const { return GetValue(); } 1610 1611 DECLARE_INSTRUCTION(IntConstant); 1612 1613 private: 1614 const int32_t value_; 1615 1616 DISALLOW_COPY_AND_ASSIGN(HIntConstant); 1617}; 1618 1619class HLongConstant : public HConstant { 1620 public: 1621 explicit HLongConstant(int64_t value) : HConstant(Primitive::kPrimLong), value_(value) {} 1622 1623 int64_t GetValue() const { return value_; } 1624 1625 virtual bool InstructionDataEquals(HInstruction* other) const { 1626 return other->AsLongConstant()->value_ == value_; 1627 } 1628 1629 virtual size_t ComputeHashCode() const { return static_cast<size_t>(GetValue()); } 1630 1631 DECLARE_INSTRUCTION(LongConstant); 1632 1633 private: 1634 const int64_t value_; 1635 1636 DISALLOW_COPY_AND_ASSIGN(HLongConstant); 1637}; 1638 1639enum class Intrinsics { 1640#define OPTIMIZING_INTRINSICS(Name, IsStatic) k ## Name, 1641#include "intrinsics_list.h" 1642 kNone, 1643 INTRINSICS_LIST(OPTIMIZING_INTRINSICS) 1644#undef INTRINSICS_LIST 1645#undef OPTIMIZING_INTRINSICS 1646}; 1647std::ostream& operator<<(std::ostream& os, const Intrinsics& intrinsic); 1648 1649class HInvoke : public HInstruction { 1650 public: 1651 virtual size_t InputCount() const { return inputs_.Size(); } 1652 virtual HInstruction* InputAt(size_t i) const { return inputs_.Get(i); } 1653 1654 // Runtime needs to walk the stack, so Dex -> Dex calls need to 1655 // know their environment. 1656 bool NeedsEnvironment() const OVERRIDE { return true; } 1657 1658 void SetArgumentAt(size_t index, HInstruction* argument) { 1659 SetRawInputAt(index, argument); 1660 } 1661 1662 virtual void SetRawInputAt(size_t index, HInstruction* input) { 1663 inputs_.Put(index, input); 1664 } 1665 1666 virtual Primitive::Type GetType() const { return return_type_; } 1667 1668 uint32_t GetDexPc() const { return dex_pc_; } 1669 1670 uint32_t GetDexMethodIndex() const { return dex_method_index_; } 1671 1672 Intrinsics GetIntrinsic() { 1673 return intrinsic_; 1674 } 1675 1676 void SetIntrinsic(Intrinsics intrinsic) { 1677 intrinsic_ = intrinsic; 1678 } 1679 1680 DECLARE_INSTRUCTION(Invoke); 1681 1682 protected: 1683 HInvoke(ArenaAllocator* arena, 1684 uint32_t number_of_arguments, 1685 Primitive::Type return_type, 1686 uint32_t dex_pc, 1687 uint32_t dex_method_index) 1688 : HInstruction(SideEffects::All()), 1689 inputs_(arena, number_of_arguments), 1690 return_type_(return_type), 1691 dex_pc_(dex_pc), 1692 dex_method_index_(dex_method_index), 1693 intrinsic_(Intrinsics::kNone) { 1694 inputs_.SetSize(number_of_arguments); 1695 } 1696 1697 GrowableArray<HInstruction*> inputs_; 1698 const Primitive::Type return_type_; 1699 const uint32_t dex_pc_; 1700 const uint32_t dex_method_index_; 1701 Intrinsics intrinsic_; 1702 1703 private: 1704 DISALLOW_COPY_AND_ASSIGN(HInvoke); 1705}; 1706 1707class HInvokeStaticOrDirect : public HInvoke { 1708 public: 1709 HInvokeStaticOrDirect(ArenaAllocator* arena, 1710 uint32_t number_of_arguments, 1711 Primitive::Type return_type, 1712 uint32_t dex_pc, 1713 uint32_t dex_method_index, 1714 InvokeType invoke_type) 1715 : HInvoke(arena, number_of_arguments, return_type, dex_pc, dex_method_index), 1716 invoke_type_(invoke_type) {} 1717 1718 bool CanDoImplicitNullCheck() const OVERRIDE { 1719 // We access the method via the dex cache so we can't do an implicit null check. 1720 // TODO: for intrinsics we can generate implicit null checks. 1721 return false; 1722 } 1723 1724 InvokeType GetInvokeType() const { return invoke_type_; } 1725 1726 DECLARE_INSTRUCTION(InvokeStaticOrDirect); 1727 1728 private: 1729 const InvokeType invoke_type_; 1730 1731 DISALLOW_COPY_AND_ASSIGN(HInvokeStaticOrDirect); 1732}; 1733 1734class HInvokeVirtual : public HInvoke { 1735 public: 1736 HInvokeVirtual(ArenaAllocator* arena, 1737 uint32_t number_of_arguments, 1738 Primitive::Type return_type, 1739 uint32_t dex_pc, 1740 uint32_t dex_method_index, 1741 uint32_t vtable_index) 1742 : HInvoke(arena, number_of_arguments, return_type, dex_pc, dex_method_index), 1743 vtable_index_(vtable_index) {} 1744 1745 bool CanDoImplicitNullCheck() const OVERRIDE { 1746 // TODO: Add implicit null checks in intrinsics. 1747 return !GetLocations()->Intrinsified(); 1748 } 1749 1750 uint32_t GetVTableIndex() const { return vtable_index_; } 1751 1752 DECLARE_INSTRUCTION(InvokeVirtual); 1753 1754 private: 1755 const uint32_t vtable_index_; 1756 1757 DISALLOW_COPY_AND_ASSIGN(HInvokeVirtual); 1758}; 1759 1760class HInvokeInterface : public HInvoke { 1761 public: 1762 HInvokeInterface(ArenaAllocator* arena, 1763 uint32_t number_of_arguments, 1764 Primitive::Type return_type, 1765 uint32_t dex_pc, 1766 uint32_t dex_method_index, 1767 uint32_t imt_index) 1768 : HInvoke(arena, number_of_arguments, return_type, dex_pc, dex_method_index), 1769 imt_index_(imt_index) {} 1770 1771 bool CanDoImplicitNullCheck() const OVERRIDE { 1772 // TODO: Add implicit null checks in intrinsics. 1773 return !GetLocations()->Intrinsified(); 1774 } 1775 1776 uint32_t GetImtIndex() const { return imt_index_; } 1777 uint32_t GetDexMethodIndex() const { return dex_method_index_; } 1778 1779 DECLARE_INSTRUCTION(InvokeInterface); 1780 1781 private: 1782 const uint32_t imt_index_; 1783 1784 DISALLOW_COPY_AND_ASSIGN(HInvokeInterface); 1785}; 1786 1787class HNewInstance : public HExpression<0> { 1788 public: 1789 HNewInstance(uint32_t dex_pc, uint16_t type_index) 1790 : HExpression(Primitive::kPrimNot, SideEffects::None()), 1791 dex_pc_(dex_pc), 1792 type_index_(type_index) {} 1793 1794 uint32_t GetDexPc() const { return dex_pc_; } 1795 uint16_t GetTypeIndex() const { return type_index_; } 1796 1797 // Calls runtime so needs an environment. 1798 bool NeedsEnvironment() const OVERRIDE { return true; } 1799 // It may throw when called on: 1800 // - interfaces 1801 // - abstract/innaccessible/unknown classes 1802 // TODO: optimize when possible. 1803 bool CanThrow() const OVERRIDE { return true; } 1804 1805 DECLARE_INSTRUCTION(NewInstance); 1806 1807 private: 1808 const uint32_t dex_pc_; 1809 const uint16_t type_index_; 1810 1811 DISALLOW_COPY_AND_ASSIGN(HNewInstance); 1812}; 1813 1814class HNeg : public HUnaryOperation { 1815 public: 1816 explicit HNeg(Primitive::Type result_type, HInstruction* input) 1817 : HUnaryOperation(result_type, input) {} 1818 1819 virtual int32_t Evaluate(int32_t x) const OVERRIDE { return -x; } 1820 virtual int64_t Evaluate(int64_t x) const OVERRIDE { return -x; } 1821 1822 DECLARE_INSTRUCTION(Neg); 1823 1824 private: 1825 DISALLOW_COPY_AND_ASSIGN(HNeg); 1826}; 1827 1828class HNewArray : public HExpression<1> { 1829 public: 1830 HNewArray(HInstruction* length, uint32_t dex_pc, uint16_t type_index) 1831 : HExpression(Primitive::kPrimNot, SideEffects::None()), 1832 dex_pc_(dex_pc), 1833 type_index_(type_index) { 1834 SetRawInputAt(0, length); 1835 } 1836 1837 uint32_t GetDexPc() const { return dex_pc_; } 1838 uint16_t GetTypeIndex() const { return type_index_; } 1839 1840 // Calls runtime so needs an environment. 1841 virtual bool NeedsEnvironment() const { return true; } 1842 1843 DECLARE_INSTRUCTION(NewArray); 1844 1845 private: 1846 const uint32_t dex_pc_; 1847 const uint16_t type_index_; 1848 1849 DISALLOW_COPY_AND_ASSIGN(HNewArray); 1850}; 1851 1852class HAdd : public HBinaryOperation { 1853 public: 1854 HAdd(Primitive::Type result_type, HInstruction* left, HInstruction* right) 1855 : HBinaryOperation(result_type, left, right) {} 1856 1857 virtual bool IsCommutative() { return true; } 1858 1859 virtual int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE { 1860 return x + y; 1861 } 1862 virtual int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE { 1863 return x + y; 1864 } 1865 1866 DECLARE_INSTRUCTION(Add); 1867 1868 private: 1869 DISALLOW_COPY_AND_ASSIGN(HAdd); 1870}; 1871 1872class HSub : public HBinaryOperation { 1873 public: 1874 HSub(Primitive::Type result_type, HInstruction* left, HInstruction* right) 1875 : HBinaryOperation(result_type, left, right) {} 1876 1877 virtual int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE { 1878 return x - y; 1879 } 1880 virtual int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE { 1881 return x - y; 1882 } 1883 1884 DECLARE_INSTRUCTION(Sub); 1885 1886 private: 1887 DISALLOW_COPY_AND_ASSIGN(HSub); 1888}; 1889 1890class HMul : public HBinaryOperation { 1891 public: 1892 HMul(Primitive::Type result_type, HInstruction* left, HInstruction* right) 1893 : HBinaryOperation(result_type, left, right) {} 1894 1895 virtual bool IsCommutative() { return true; } 1896 1897 virtual int32_t Evaluate(int32_t x, int32_t y) const { return x * y; } 1898 virtual int64_t Evaluate(int64_t x, int64_t y) const { return x * y; } 1899 1900 DECLARE_INSTRUCTION(Mul); 1901 1902 private: 1903 DISALLOW_COPY_AND_ASSIGN(HMul); 1904}; 1905 1906class HDiv : public HBinaryOperation { 1907 public: 1908 HDiv(Primitive::Type result_type, HInstruction* left, HInstruction* right, uint32_t dex_pc) 1909 : HBinaryOperation(result_type, left, right), dex_pc_(dex_pc) {} 1910 1911 virtual int32_t Evaluate(int32_t x, int32_t y) const { 1912 // Our graph structure ensures we never have 0 for `y` during constant folding. 1913 DCHECK_NE(y, 0); 1914 // Special case -1 to avoid getting a SIGFPE on x86(_64). 1915 return (y == -1) ? -x : x / y; 1916 } 1917 1918 virtual int64_t Evaluate(int64_t x, int64_t y) const { 1919 DCHECK_NE(y, 0); 1920 // Special case -1 to avoid getting a SIGFPE on x86(_64). 1921 return (y == -1) ? -x : x / y; 1922 } 1923 1924 uint32_t GetDexPc() const { return dex_pc_; } 1925 1926 DECLARE_INSTRUCTION(Div); 1927 1928 private: 1929 const uint32_t dex_pc_; 1930 1931 DISALLOW_COPY_AND_ASSIGN(HDiv); 1932}; 1933 1934class HRem : public HBinaryOperation { 1935 public: 1936 HRem(Primitive::Type result_type, HInstruction* left, HInstruction* right, uint32_t dex_pc) 1937 : HBinaryOperation(result_type, left, right), dex_pc_(dex_pc) {} 1938 1939 virtual int32_t Evaluate(int32_t x, int32_t y) const { 1940 DCHECK_NE(y, 0); 1941 // Special case -1 to avoid getting a SIGFPE on x86(_64). 1942 return (y == -1) ? 0 : x % y; 1943 } 1944 1945 virtual int64_t Evaluate(int64_t x, int64_t y) const { 1946 DCHECK_NE(y, 0); 1947 // Special case -1 to avoid getting a SIGFPE on x86(_64). 1948 return (y == -1) ? 0 : x % y; 1949 } 1950 1951 uint32_t GetDexPc() const { return dex_pc_; } 1952 1953 DECLARE_INSTRUCTION(Rem); 1954 1955 private: 1956 const uint32_t dex_pc_; 1957 1958 DISALLOW_COPY_AND_ASSIGN(HRem); 1959}; 1960 1961class HDivZeroCheck : public HExpression<1> { 1962 public: 1963 HDivZeroCheck(HInstruction* value, uint32_t dex_pc) 1964 : HExpression(value->GetType(), SideEffects::None()), dex_pc_(dex_pc) { 1965 SetRawInputAt(0, value); 1966 } 1967 1968 bool CanBeMoved() const OVERRIDE { return true; } 1969 1970 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 1971 UNUSED(other); 1972 return true; 1973 } 1974 1975 bool NeedsEnvironment() const OVERRIDE { return true; } 1976 bool CanThrow() const OVERRIDE { return true; } 1977 1978 uint32_t GetDexPc() const { return dex_pc_; } 1979 1980 DECLARE_INSTRUCTION(DivZeroCheck); 1981 1982 private: 1983 const uint32_t dex_pc_; 1984 1985 DISALLOW_COPY_AND_ASSIGN(HDivZeroCheck); 1986}; 1987 1988class HShl : public HBinaryOperation { 1989 public: 1990 HShl(Primitive::Type result_type, HInstruction* left, HInstruction* right) 1991 : HBinaryOperation(result_type, left, right) {} 1992 1993 int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE { return x << (y & kMaxIntShiftValue); } 1994 int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE { return x << (y & kMaxLongShiftValue); } 1995 1996 DECLARE_INSTRUCTION(Shl); 1997 1998 private: 1999 DISALLOW_COPY_AND_ASSIGN(HShl); 2000}; 2001 2002class HShr : public HBinaryOperation { 2003 public: 2004 HShr(Primitive::Type result_type, HInstruction* left, HInstruction* right) 2005 : HBinaryOperation(result_type, left, right) {} 2006 2007 int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE { return x >> (y & kMaxIntShiftValue); } 2008 int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE { return x >> (y & kMaxLongShiftValue); } 2009 2010 DECLARE_INSTRUCTION(Shr); 2011 2012 private: 2013 DISALLOW_COPY_AND_ASSIGN(HShr); 2014}; 2015 2016class HUShr : public HBinaryOperation { 2017 public: 2018 HUShr(Primitive::Type result_type, HInstruction* left, HInstruction* right) 2019 : HBinaryOperation(result_type, left, right) {} 2020 2021 int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE { 2022 uint32_t ux = static_cast<uint32_t>(x); 2023 uint32_t uy = static_cast<uint32_t>(y) & kMaxIntShiftValue; 2024 return static_cast<int32_t>(ux >> uy); 2025 } 2026 2027 int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE { 2028 uint64_t ux = static_cast<uint64_t>(x); 2029 uint64_t uy = static_cast<uint64_t>(y) & kMaxLongShiftValue; 2030 return static_cast<int64_t>(ux >> uy); 2031 } 2032 2033 DECLARE_INSTRUCTION(UShr); 2034 2035 private: 2036 DISALLOW_COPY_AND_ASSIGN(HUShr); 2037}; 2038 2039class HAnd : public HBinaryOperation { 2040 public: 2041 HAnd(Primitive::Type result_type, HInstruction* left, HInstruction* right) 2042 : HBinaryOperation(result_type, left, right) {} 2043 2044 bool IsCommutative() OVERRIDE { return true; } 2045 2046 int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE { return x & y; } 2047 int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE { return x & y; } 2048 2049 DECLARE_INSTRUCTION(And); 2050 2051 private: 2052 DISALLOW_COPY_AND_ASSIGN(HAnd); 2053}; 2054 2055class HOr : public HBinaryOperation { 2056 public: 2057 HOr(Primitive::Type result_type, HInstruction* left, HInstruction* right) 2058 : HBinaryOperation(result_type, left, right) {} 2059 2060 bool IsCommutative() OVERRIDE { return true; } 2061 2062 int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE { return x | y; } 2063 int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE { return x | y; } 2064 2065 DECLARE_INSTRUCTION(Or); 2066 2067 private: 2068 DISALLOW_COPY_AND_ASSIGN(HOr); 2069}; 2070 2071class HXor : public HBinaryOperation { 2072 public: 2073 HXor(Primitive::Type result_type, HInstruction* left, HInstruction* right) 2074 : HBinaryOperation(result_type, left, right) {} 2075 2076 bool IsCommutative() OVERRIDE { return true; } 2077 2078 int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE { return x ^ y; } 2079 int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE { return x ^ y; } 2080 2081 DECLARE_INSTRUCTION(Xor); 2082 2083 private: 2084 DISALLOW_COPY_AND_ASSIGN(HXor); 2085}; 2086 2087// The value of a parameter in this method. Its location depends on 2088// the calling convention. 2089class HParameterValue : public HExpression<0> { 2090 public: 2091 HParameterValue(uint8_t index, Primitive::Type parameter_type) 2092 : HExpression(parameter_type, SideEffects::None()), index_(index) {} 2093 2094 uint8_t GetIndex() const { return index_; } 2095 2096 DECLARE_INSTRUCTION(ParameterValue); 2097 2098 private: 2099 // The index of this parameter in the parameters list. Must be less 2100 // than HGraph::number_of_in_vregs_; 2101 const uint8_t index_; 2102 2103 DISALLOW_COPY_AND_ASSIGN(HParameterValue); 2104}; 2105 2106class HNot : public HUnaryOperation { 2107 public: 2108 explicit HNot(Primitive::Type result_type, HInstruction* input) 2109 : HUnaryOperation(result_type, input) {} 2110 2111 virtual bool CanBeMoved() const { return true; } 2112 virtual bool InstructionDataEquals(HInstruction* other) const { 2113 UNUSED(other); 2114 return true; 2115 } 2116 2117 virtual int32_t Evaluate(int32_t x) const OVERRIDE { return ~x; } 2118 virtual int64_t Evaluate(int64_t x) const OVERRIDE { return ~x; } 2119 2120 DECLARE_INSTRUCTION(Not); 2121 2122 private: 2123 DISALLOW_COPY_AND_ASSIGN(HNot); 2124}; 2125 2126class HTypeConversion : public HExpression<1> { 2127 public: 2128 // Instantiate a type conversion of `input` to `result_type`. 2129 HTypeConversion(Primitive::Type result_type, HInstruction* input, uint32_t dex_pc) 2130 : HExpression(result_type, SideEffects::None()), dex_pc_(dex_pc) { 2131 SetRawInputAt(0, input); 2132 DCHECK_NE(input->GetType(), result_type); 2133 } 2134 2135 HInstruction* GetInput() const { return InputAt(0); } 2136 Primitive::Type GetInputType() const { return GetInput()->GetType(); } 2137 Primitive::Type GetResultType() const { return GetType(); } 2138 2139 // Required by the x86 and ARM code generators when producing calls 2140 // to the runtime. 2141 uint32_t GetDexPc() const { return dex_pc_; } 2142 2143 bool CanBeMoved() const OVERRIDE { return true; } 2144 bool InstructionDataEquals(HInstruction* other ATTRIBUTE_UNUSED) const OVERRIDE { return true; } 2145 2146 DECLARE_INSTRUCTION(TypeConversion); 2147 2148 private: 2149 const uint32_t dex_pc_; 2150 2151 DISALLOW_COPY_AND_ASSIGN(HTypeConversion); 2152}; 2153 2154class HPhi : public HInstruction { 2155 public: 2156 HPhi(ArenaAllocator* arena, uint32_t reg_number, size_t number_of_inputs, Primitive::Type type) 2157 : HInstruction(SideEffects::None()), 2158 inputs_(arena, number_of_inputs), 2159 reg_number_(reg_number), 2160 type_(type), 2161 is_live_(false) { 2162 inputs_.SetSize(number_of_inputs); 2163 } 2164 2165 virtual size_t InputCount() const { return inputs_.Size(); } 2166 virtual HInstruction* InputAt(size_t i) const { return inputs_.Get(i); } 2167 2168 virtual void SetRawInputAt(size_t index, HInstruction* input) { 2169 inputs_.Put(index, input); 2170 } 2171 2172 void AddInput(HInstruction* input); 2173 2174 virtual Primitive::Type GetType() const { return type_; } 2175 void SetType(Primitive::Type type) { type_ = type; } 2176 2177 uint32_t GetRegNumber() const { return reg_number_; } 2178 2179 void SetDead() { is_live_ = false; } 2180 void SetLive() { is_live_ = true; } 2181 bool IsDead() const { return !is_live_; } 2182 bool IsLive() const { return is_live_; } 2183 2184 DECLARE_INSTRUCTION(Phi); 2185 2186 private: 2187 GrowableArray<HInstruction*> inputs_; 2188 const uint32_t reg_number_; 2189 Primitive::Type type_; 2190 bool is_live_; 2191 2192 DISALLOW_COPY_AND_ASSIGN(HPhi); 2193}; 2194 2195class HNullCheck : public HExpression<1> { 2196 public: 2197 HNullCheck(HInstruction* value, uint32_t dex_pc) 2198 : HExpression(value->GetType(), SideEffects::None()), dex_pc_(dex_pc) { 2199 SetRawInputAt(0, value); 2200 } 2201 2202 virtual bool CanBeMoved() const { return true; } 2203 virtual bool InstructionDataEquals(HInstruction* other) const { 2204 UNUSED(other); 2205 return true; 2206 } 2207 2208 virtual bool NeedsEnvironment() const { return true; } 2209 2210 virtual bool CanThrow() const { return true; } 2211 2212 uint32_t GetDexPc() const { return dex_pc_; } 2213 2214 DECLARE_INSTRUCTION(NullCheck); 2215 2216 private: 2217 const uint32_t dex_pc_; 2218 2219 DISALLOW_COPY_AND_ASSIGN(HNullCheck); 2220}; 2221 2222class FieldInfo : public ValueObject { 2223 public: 2224 FieldInfo(MemberOffset field_offset, Primitive::Type field_type, bool is_volatile) 2225 : field_offset_(field_offset), field_type_(field_type), is_volatile_(is_volatile) {} 2226 2227 MemberOffset GetFieldOffset() const { return field_offset_; } 2228 Primitive::Type GetFieldType() const { return field_type_; } 2229 bool IsVolatile() const { return is_volatile_; } 2230 2231 private: 2232 const MemberOffset field_offset_; 2233 const Primitive::Type field_type_; 2234 const bool is_volatile_; 2235}; 2236 2237class HInstanceFieldGet : public HExpression<1> { 2238 public: 2239 HInstanceFieldGet(HInstruction* value, 2240 Primitive::Type field_type, 2241 MemberOffset field_offset, 2242 bool is_volatile) 2243 : HExpression(field_type, SideEffects::DependsOnSomething()), 2244 field_info_(field_offset, field_type, is_volatile) { 2245 SetRawInputAt(0, value); 2246 } 2247 2248 bool CanBeMoved() const OVERRIDE { return !IsVolatile(); } 2249 2250 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 2251 HInstanceFieldGet* other_get = other->AsInstanceFieldGet(); 2252 return GetFieldOffset().SizeValue() == other_get->GetFieldOffset().SizeValue(); 2253 } 2254 2255 bool CanDoImplicitNullCheck() const OVERRIDE { 2256 return GetFieldOffset().Uint32Value() < kPageSize; 2257 } 2258 2259 size_t ComputeHashCode() const OVERRIDE { 2260 return (HInstruction::ComputeHashCode() << 7) | GetFieldOffset().SizeValue(); 2261 } 2262 2263 const FieldInfo& GetFieldInfo() const { return field_info_; } 2264 MemberOffset GetFieldOffset() const { return field_info_.GetFieldOffset(); } 2265 Primitive::Type GetFieldType() const { return field_info_.GetFieldType(); } 2266 bool IsVolatile() const { return field_info_.IsVolatile(); } 2267 2268 DECLARE_INSTRUCTION(InstanceFieldGet); 2269 2270 private: 2271 const FieldInfo field_info_; 2272 2273 DISALLOW_COPY_AND_ASSIGN(HInstanceFieldGet); 2274}; 2275 2276class HInstanceFieldSet : public HTemplateInstruction<2> { 2277 public: 2278 HInstanceFieldSet(HInstruction* object, 2279 HInstruction* value, 2280 Primitive::Type field_type, 2281 MemberOffset field_offset, 2282 bool is_volatile) 2283 : HTemplateInstruction(SideEffects::ChangesSomething()), 2284 field_info_(field_offset, field_type, is_volatile) { 2285 SetRawInputAt(0, object); 2286 SetRawInputAt(1, value); 2287 } 2288 2289 bool CanDoImplicitNullCheck() const OVERRIDE { 2290 return GetFieldOffset().Uint32Value() < kPageSize; 2291 } 2292 2293 const FieldInfo& GetFieldInfo() const { return field_info_; } 2294 MemberOffset GetFieldOffset() const { return field_info_.GetFieldOffset(); } 2295 Primitive::Type GetFieldType() const { return field_info_.GetFieldType(); } 2296 bool IsVolatile() const { return field_info_.IsVolatile(); } 2297 HInstruction* GetValue() const { return InputAt(1); } 2298 2299 DECLARE_INSTRUCTION(InstanceFieldSet); 2300 2301 private: 2302 const FieldInfo field_info_; 2303 2304 DISALLOW_COPY_AND_ASSIGN(HInstanceFieldSet); 2305}; 2306 2307class HArrayGet : public HExpression<2> { 2308 public: 2309 HArrayGet(HInstruction* array, HInstruction* index, Primitive::Type type) 2310 : HExpression(type, SideEffects::DependsOnSomething()) { 2311 SetRawInputAt(0, array); 2312 SetRawInputAt(1, index); 2313 } 2314 2315 bool CanBeMoved() const OVERRIDE { return true; } 2316 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 2317 UNUSED(other); 2318 return true; 2319 } 2320 bool CanDoImplicitNullCheck() const OVERRIDE { 2321 // TODO: We can be smarter here. 2322 // Currently, the array access is always preceded by an ArrayLength or a NullCheck 2323 // which generates the implicit null check. There are cases when these can be removed 2324 // to produce better code. If we ever add optimizations to do so we should allow an 2325 // implicit check here (as long as the address falls in the first page). 2326 return false; 2327 } 2328 2329 void SetType(Primitive::Type type) { type_ = type; } 2330 2331 HInstruction* GetArray() const { return InputAt(0); } 2332 HInstruction* GetIndex() const { return InputAt(1); } 2333 2334 DECLARE_INSTRUCTION(ArrayGet); 2335 2336 private: 2337 DISALLOW_COPY_AND_ASSIGN(HArrayGet); 2338}; 2339 2340class HArraySet : public HTemplateInstruction<3> { 2341 public: 2342 HArraySet(HInstruction* array, 2343 HInstruction* index, 2344 HInstruction* value, 2345 Primitive::Type expected_component_type, 2346 uint32_t dex_pc) 2347 : HTemplateInstruction(SideEffects::ChangesSomething()), 2348 dex_pc_(dex_pc), 2349 expected_component_type_(expected_component_type), 2350 needs_type_check_(value->GetType() == Primitive::kPrimNot) { 2351 SetRawInputAt(0, array); 2352 SetRawInputAt(1, index); 2353 SetRawInputAt(2, value); 2354 } 2355 2356 bool NeedsEnvironment() const OVERRIDE { 2357 // We currently always call a runtime method to catch array store 2358 // exceptions. 2359 return needs_type_check_; 2360 } 2361 2362 bool CanDoImplicitNullCheck() const OVERRIDE { 2363 // TODO: Same as for ArrayGet. 2364 return false; 2365 } 2366 2367 void ClearNeedsTypeCheck() { 2368 needs_type_check_ = false; 2369 } 2370 2371 bool NeedsTypeCheck() const { return needs_type_check_; } 2372 2373 uint32_t GetDexPc() const { return dex_pc_; } 2374 2375 HInstruction* GetArray() const { return InputAt(0); } 2376 HInstruction* GetIndex() const { return InputAt(1); } 2377 HInstruction* GetValue() const { return InputAt(2); } 2378 2379 Primitive::Type GetComponentType() const { 2380 // The Dex format does not type floating point index operations. Since the 2381 // `expected_component_type_` is set during building and can therefore not 2382 // be correct, we also check what is the value type. If it is a floating 2383 // point type, we must use that type. 2384 Primitive::Type value_type = GetValue()->GetType(); 2385 return ((value_type == Primitive::kPrimFloat) || (value_type == Primitive::kPrimDouble)) 2386 ? value_type 2387 : expected_component_type_; 2388 } 2389 2390 DECLARE_INSTRUCTION(ArraySet); 2391 2392 private: 2393 const uint32_t dex_pc_; 2394 const Primitive::Type expected_component_type_; 2395 bool needs_type_check_; 2396 2397 DISALLOW_COPY_AND_ASSIGN(HArraySet); 2398}; 2399 2400class HArrayLength : public HExpression<1> { 2401 public: 2402 explicit HArrayLength(HInstruction* array) 2403 : HExpression(Primitive::kPrimInt, SideEffects::None()) { 2404 // Note that arrays do not change length, so the instruction does not 2405 // depend on any write. 2406 SetRawInputAt(0, array); 2407 } 2408 2409 bool CanBeMoved() const OVERRIDE { return true; } 2410 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 2411 UNUSED(other); 2412 return true; 2413 } 2414 bool CanDoImplicitNullCheck() const OVERRIDE { return true; } 2415 2416 DECLARE_INSTRUCTION(ArrayLength); 2417 2418 private: 2419 DISALLOW_COPY_AND_ASSIGN(HArrayLength); 2420}; 2421 2422class HBoundsCheck : public HExpression<2> { 2423 public: 2424 HBoundsCheck(HInstruction* index, HInstruction* length, uint32_t dex_pc) 2425 : HExpression(index->GetType(), SideEffects::None()), dex_pc_(dex_pc) { 2426 DCHECK(index->GetType() == Primitive::kPrimInt); 2427 SetRawInputAt(0, index); 2428 SetRawInputAt(1, length); 2429 } 2430 2431 virtual bool CanBeMoved() const { return true; } 2432 virtual bool InstructionDataEquals(HInstruction* other) const { 2433 UNUSED(other); 2434 return true; 2435 } 2436 2437 virtual bool NeedsEnvironment() const { return true; } 2438 2439 virtual bool CanThrow() const { return true; } 2440 2441 uint32_t GetDexPc() const { return dex_pc_; } 2442 2443 DECLARE_INSTRUCTION(BoundsCheck); 2444 2445 private: 2446 const uint32_t dex_pc_; 2447 2448 DISALLOW_COPY_AND_ASSIGN(HBoundsCheck); 2449}; 2450 2451/** 2452 * Some DEX instructions are folded into multiple HInstructions that need 2453 * to stay live until the last HInstruction. This class 2454 * is used as a marker for the baseline compiler to ensure its preceding 2455 * HInstruction stays live. `index` represents the stack location index of the 2456 * instruction (the actual offset is computed as index * vreg_size). 2457 */ 2458class HTemporary : public HTemplateInstruction<0> { 2459 public: 2460 explicit HTemporary(size_t index) : HTemplateInstruction(SideEffects::None()), index_(index) {} 2461 2462 size_t GetIndex() const { return index_; } 2463 2464 Primitive::Type GetType() const OVERRIDE { 2465 // The previous instruction is the one that will be stored in the temporary location. 2466 DCHECK(GetPrevious() != nullptr); 2467 return GetPrevious()->GetType(); 2468 } 2469 2470 DECLARE_INSTRUCTION(Temporary); 2471 2472 private: 2473 const size_t index_; 2474 2475 DISALLOW_COPY_AND_ASSIGN(HTemporary); 2476}; 2477 2478class HSuspendCheck : public HTemplateInstruction<0> { 2479 public: 2480 explicit HSuspendCheck(uint32_t dex_pc) 2481 : HTemplateInstruction(SideEffects::None()), dex_pc_(dex_pc) {} 2482 2483 virtual bool NeedsEnvironment() const { 2484 return true; 2485 } 2486 2487 uint32_t GetDexPc() const { return dex_pc_; } 2488 2489 DECLARE_INSTRUCTION(SuspendCheck); 2490 2491 private: 2492 const uint32_t dex_pc_; 2493 2494 DISALLOW_COPY_AND_ASSIGN(HSuspendCheck); 2495}; 2496 2497/** 2498 * Instruction to load a Class object. 2499 */ 2500class HLoadClass : public HExpression<0> { 2501 public: 2502 HLoadClass(uint16_t type_index, 2503 bool is_referrers_class, 2504 uint32_t dex_pc) 2505 : HExpression(Primitive::kPrimNot, SideEffects::None()), 2506 type_index_(type_index), 2507 is_referrers_class_(is_referrers_class), 2508 dex_pc_(dex_pc), 2509 generate_clinit_check_(false) {} 2510 2511 bool CanBeMoved() const OVERRIDE { return true; } 2512 2513 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 2514 return other->AsLoadClass()->type_index_ == type_index_; 2515 } 2516 2517 size_t ComputeHashCode() const OVERRIDE { return type_index_; } 2518 2519 uint32_t GetDexPc() const { return dex_pc_; } 2520 uint16_t GetTypeIndex() const { return type_index_; } 2521 bool IsReferrersClass() const { return is_referrers_class_; } 2522 2523 bool NeedsEnvironment() const OVERRIDE { 2524 // Will call runtime and load the class if the class is not loaded yet. 2525 // TODO: finer grain decision. 2526 return !is_referrers_class_; 2527 } 2528 2529 bool MustGenerateClinitCheck() const { 2530 return generate_clinit_check_; 2531 } 2532 2533 void SetMustGenerateClinitCheck() { 2534 generate_clinit_check_ = true; 2535 } 2536 2537 bool CanCallRuntime() const { 2538 return MustGenerateClinitCheck() || !is_referrers_class_; 2539 } 2540 2541 DECLARE_INSTRUCTION(LoadClass); 2542 2543 private: 2544 const uint16_t type_index_; 2545 const bool is_referrers_class_; 2546 const uint32_t dex_pc_; 2547 // Whether this instruction must generate the initialization check. 2548 // Used for code generation. 2549 bool generate_clinit_check_; 2550 2551 DISALLOW_COPY_AND_ASSIGN(HLoadClass); 2552}; 2553 2554class HLoadString : public HExpression<0> { 2555 public: 2556 HLoadString(uint32_t string_index, uint32_t dex_pc) 2557 : HExpression(Primitive::kPrimNot, SideEffects::None()), 2558 string_index_(string_index), 2559 dex_pc_(dex_pc) {} 2560 2561 bool CanBeMoved() const OVERRIDE { return true; } 2562 2563 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 2564 return other->AsLoadString()->string_index_ == string_index_; 2565 } 2566 2567 size_t ComputeHashCode() const OVERRIDE { return string_index_; } 2568 2569 uint32_t GetDexPc() const { return dex_pc_; } 2570 uint32_t GetStringIndex() const { return string_index_; } 2571 2572 // TODO: Can we deopt or debug when we resolve a string? 2573 bool NeedsEnvironment() const OVERRIDE { return false; } 2574 2575 DECLARE_INSTRUCTION(LoadString); 2576 2577 private: 2578 const uint32_t string_index_; 2579 const uint32_t dex_pc_; 2580 2581 DISALLOW_COPY_AND_ASSIGN(HLoadString); 2582}; 2583 2584// TODO: Pass this check to HInvokeStaticOrDirect nodes. 2585/** 2586 * Performs an initialization check on its Class object input. 2587 */ 2588class HClinitCheck : public HExpression<1> { 2589 public: 2590 explicit HClinitCheck(HLoadClass* constant, uint32_t dex_pc) 2591 : HExpression(Primitive::kPrimNot, SideEffects::All()), 2592 dex_pc_(dex_pc) { 2593 SetRawInputAt(0, constant); 2594 } 2595 2596 bool CanBeMoved() const OVERRIDE { return true; } 2597 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 2598 UNUSED(other); 2599 return true; 2600 } 2601 2602 bool NeedsEnvironment() const OVERRIDE { 2603 // May call runtime to initialize the class. 2604 return true; 2605 } 2606 2607 uint32_t GetDexPc() const { return dex_pc_; } 2608 2609 HLoadClass* GetLoadClass() const { return InputAt(0)->AsLoadClass(); } 2610 2611 DECLARE_INSTRUCTION(ClinitCheck); 2612 2613 private: 2614 const uint32_t dex_pc_; 2615 2616 DISALLOW_COPY_AND_ASSIGN(HClinitCheck); 2617}; 2618 2619class HStaticFieldGet : public HExpression<1> { 2620 public: 2621 HStaticFieldGet(HInstruction* cls, 2622 Primitive::Type field_type, 2623 MemberOffset field_offset, 2624 bool is_volatile) 2625 : HExpression(field_type, SideEffects::DependsOnSomething()), 2626 field_info_(field_offset, field_type, is_volatile) { 2627 SetRawInputAt(0, cls); 2628 } 2629 2630 2631 bool CanBeMoved() const OVERRIDE { return !IsVolatile(); } 2632 2633 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 2634 HStaticFieldGet* other_get = other->AsStaticFieldGet(); 2635 return GetFieldOffset().SizeValue() == other_get->GetFieldOffset().SizeValue(); 2636 } 2637 2638 size_t ComputeHashCode() const OVERRIDE { 2639 return (HInstruction::ComputeHashCode() << 7) | GetFieldOffset().SizeValue(); 2640 } 2641 2642 const FieldInfo& GetFieldInfo() const { return field_info_; } 2643 MemberOffset GetFieldOffset() const { return field_info_.GetFieldOffset(); } 2644 Primitive::Type GetFieldType() const { return field_info_.GetFieldType(); } 2645 bool IsVolatile() const { return field_info_.IsVolatile(); } 2646 2647 DECLARE_INSTRUCTION(StaticFieldGet); 2648 2649 private: 2650 const FieldInfo field_info_; 2651 2652 DISALLOW_COPY_AND_ASSIGN(HStaticFieldGet); 2653}; 2654 2655class HStaticFieldSet : public HTemplateInstruction<2> { 2656 public: 2657 HStaticFieldSet(HInstruction* cls, 2658 HInstruction* value, 2659 Primitive::Type field_type, 2660 MemberOffset field_offset, 2661 bool is_volatile) 2662 : HTemplateInstruction(SideEffects::ChangesSomething()), 2663 field_info_(field_offset, field_type, is_volatile) { 2664 SetRawInputAt(0, cls); 2665 SetRawInputAt(1, value); 2666 } 2667 2668 const FieldInfo& GetFieldInfo() const { return field_info_; } 2669 MemberOffset GetFieldOffset() const { return field_info_.GetFieldOffset(); } 2670 Primitive::Type GetFieldType() const { return field_info_.GetFieldType(); } 2671 bool IsVolatile() const { return field_info_.IsVolatile(); } 2672 2673 HInstruction* GetValue() const { return InputAt(1); } 2674 2675 DECLARE_INSTRUCTION(StaticFieldSet); 2676 2677 private: 2678 const FieldInfo field_info_; 2679 2680 DISALLOW_COPY_AND_ASSIGN(HStaticFieldSet); 2681}; 2682 2683// Implement the move-exception DEX instruction. 2684class HLoadException : public HExpression<0> { 2685 public: 2686 HLoadException() : HExpression(Primitive::kPrimNot, SideEffects::None()) {} 2687 2688 DECLARE_INSTRUCTION(LoadException); 2689 2690 private: 2691 DISALLOW_COPY_AND_ASSIGN(HLoadException); 2692}; 2693 2694class HThrow : public HTemplateInstruction<1> { 2695 public: 2696 HThrow(HInstruction* exception, uint32_t dex_pc) 2697 : HTemplateInstruction(SideEffects::None()), dex_pc_(dex_pc) { 2698 SetRawInputAt(0, exception); 2699 } 2700 2701 bool IsControlFlow() const OVERRIDE { return true; } 2702 2703 bool NeedsEnvironment() const OVERRIDE { return true; } 2704 2705 uint32_t GetDexPc() const { return dex_pc_; } 2706 2707 DECLARE_INSTRUCTION(Throw); 2708 2709 private: 2710 uint32_t dex_pc_; 2711 2712 DISALLOW_COPY_AND_ASSIGN(HThrow); 2713}; 2714 2715class HInstanceOf : public HExpression<2> { 2716 public: 2717 HInstanceOf(HInstruction* object, 2718 HLoadClass* constant, 2719 bool class_is_final, 2720 uint32_t dex_pc) 2721 : HExpression(Primitive::kPrimBoolean, SideEffects::None()), 2722 class_is_final_(class_is_final), 2723 dex_pc_(dex_pc) { 2724 SetRawInputAt(0, object); 2725 SetRawInputAt(1, constant); 2726 } 2727 2728 bool CanBeMoved() const OVERRIDE { return true; } 2729 2730 bool InstructionDataEquals(HInstruction* other ATTRIBUTE_UNUSED) const OVERRIDE { 2731 return true; 2732 } 2733 2734 bool NeedsEnvironment() const OVERRIDE { 2735 return false; 2736 } 2737 2738 uint32_t GetDexPc() const { return dex_pc_; } 2739 2740 bool IsClassFinal() const { return class_is_final_; } 2741 2742 DECLARE_INSTRUCTION(InstanceOf); 2743 2744 private: 2745 const bool class_is_final_; 2746 const uint32_t dex_pc_; 2747 2748 DISALLOW_COPY_AND_ASSIGN(HInstanceOf); 2749}; 2750 2751class HCheckCast : public HTemplateInstruction<2> { 2752 public: 2753 HCheckCast(HInstruction* object, 2754 HLoadClass* constant, 2755 bool class_is_final, 2756 uint32_t dex_pc) 2757 : HTemplateInstruction(SideEffects::None()), 2758 class_is_final_(class_is_final), 2759 dex_pc_(dex_pc) { 2760 SetRawInputAt(0, object); 2761 SetRawInputAt(1, constant); 2762 } 2763 2764 bool CanBeMoved() const OVERRIDE { return true; } 2765 2766 bool InstructionDataEquals(HInstruction* other ATTRIBUTE_UNUSED) const OVERRIDE { 2767 return true; 2768 } 2769 2770 bool NeedsEnvironment() const OVERRIDE { 2771 // Instruction may throw a CheckCastError. 2772 return true; 2773 } 2774 2775 bool CanThrow() const OVERRIDE { return true; } 2776 2777 uint32_t GetDexPc() const { return dex_pc_; } 2778 2779 bool IsClassFinal() const { return class_is_final_; } 2780 2781 DECLARE_INSTRUCTION(CheckCast); 2782 2783 private: 2784 const bool class_is_final_; 2785 const uint32_t dex_pc_; 2786 2787 DISALLOW_COPY_AND_ASSIGN(HCheckCast); 2788}; 2789 2790class HMonitorOperation : public HTemplateInstruction<1> { 2791 public: 2792 enum OperationKind { 2793 kEnter, 2794 kExit, 2795 }; 2796 2797 HMonitorOperation(HInstruction* object, OperationKind kind, uint32_t dex_pc) 2798 : HTemplateInstruction(SideEffects::None()), kind_(kind), dex_pc_(dex_pc) { 2799 SetRawInputAt(0, object); 2800 } 2801 2802 // Instruction may throw a Java exception, so we need an environment. 2803 bool NeedsEnvironment() const OVERRIDE { return true; } 2804 bool CanThrow() const OVERRIDE { return true; } 2805 2806 uint32_t GetDexPc() const { return dex_pc_; } 2807 2808 bool IsEnter() const { return kind_ == kEnter; } 2809 2810 DECLARE_INSTRUCTION(MonitorOperation); 2811 2812 private: 2813 const OperationKind kind_; 2814 const uint32_t dex_pc_; 2815 2816 private: 2817 DISALLOW_COPY_AND_ASSIGN(HMonitorOperation); 2818}; 2819 2820class MoveOperands : public ArenaObject<kArenaAllocMisc> { 2821 public: 2822 MoveOperands(Location source, Location destination, HInstruction* instruction) 2823 : source_(source), destination_(destination), instruction_(instruction) {} 2824 2825 Location GetSource() const { return source_; } 2826 Location GetDestination() const { return destination_; } 2827 2828 void SetSource(Location value) { source_ = value; } 2829 void SetDestination(Location value) { destination_ = value; } 2830 2831 // The parallel move resolver marks moves as "in-progress" by clearing the 2832 // destination (but not the source). 2833 Location MarkPending() { 2834 DCHECK(!IsPending()); 2835 Location dest = destination_; 2836 destination_ = Location::NoLocation(); 2837 return dest; 2838 } 2839 2840 void ClearPending(Location dest) { 2841 DCHECK(IsPending()); 2842 destination_ = dest; 2843 } 2844 2845 bool IsPending() const { 2846 DCHECK(!source_.IsInvalid() || destination_.IsInvalid()); 2847 return destination_.IsInvalid() && !source_.IsInvalid(); 2848 } 2849 2850 // True if this blocks a move from the given location. 2851 bool Blocks(Location loc) const { 2852 return !IsEliminated() && source_.Equals(loc); 2853 } 2854 2855 // A move is redundant if it's been eliminated, if its source and 2856 // destination are the same, or if its destination is unneeded. 2857 bool IsRedundant() const { 2858 return IsEliminated() || destination_.IsInvalid() || source_.Equals(destination_); 2859 } 2860 2861 // We clear both operands to indicate move that's been eliminated. 2862 void Eliminate() { 2863 source_ = destination_ = Location::NoLocation(); 2864 } 2865 2866 bool IsEliminated() const { 2867 DCHECK(!source_.IsInvalid() || destination_.IsInvalid()); 2868 return source_.IsInvalid(); 2869 } 2870 2871 HInstruction* GetInstruction() const { return instruction_; } 2872 2873 private: 2874 Location source_; 2875 Location destination_; 2876 // The instruction this move is assocatied with. Null when this move is 2877 // for moving an input in the expected locations of user (including a phi user). 2878 // This is only used in debug mode, to ensure we do not connect interval siblings 2879 // in the same parallel move. 2880 HInstruction* instruction_; 2881}; 2882 2883static constexpr size_t kDefaultNumberOfMoves = 4; 2884 2885class HParallelMove : public HTemplateInstruction<0> { 2886 public: 2887 explicit HParallelMove(ArenaAllocator* arena) 2888 : HTemplateInstruction(SideEffects::None()), moves_(arena, kDefaultNumberOfMoves) {} 2889 2890 void AddMove(Location source, Location destination, HInstruction* instruction) { 2891 DCHECK(source.IsValid()); 2892 DCHECK(destination.IsValid()); 2893 // The parallel move resolver does not handle pairs. So we decompose the 2894 // pair locations into two moves. 2895 if (source.IsPair() && destination.IsPair()) { 2896 AddMove(source.ToLow(), destination.ToLow(), instruction); 2897 AddMove(source.ToHigh(), destination.ToHigh(), nullptr); 2898 } else if (source.IsPair()) { 2899 DCHECK(destination.IsDoubleStackSlot()) << destination; 2900 AddMove(source.ToLow(), Location::StackSlot(destination.GetStackIndex()), instruction); 2901 AddMove(source.ToHigh(), Location::StackSlot(destination.GetHighStackIndex(4)), nullptr); 2902 } else if (destination.IsPair()) { 2903 if (source.IsConstant()) { 2904 // We put the same constant in the move. The code generator will handle which 2905 // low or high part to use. 2906 AddMove(source, destination.ToLow(), instruction); 2907 AddMove(source, destination.ToHigh(), nullptr); 2908 } else { 2909 DCHECK(source.IsDoubleStackSlot()); 2910 AddMove(Location::StackSlot(source.GetStackIndex()), destination.ToLow(), instruction); 2911 // TODO: rewrite GetHighStackIndex to not require a word size. It's supposed to 2912 // always be 4. 2913 static constexpr int kHighOffset = 4; 2914 AddMove(Location::StackSlot(source.GetHighStackIndex(kHighOffset)), 2915 destination.ToHigh(), 2916 nullptr); 2917 } 2918 } else { 2919 if (kIsDebugBuild) { 2920 if (instruction != nullptr) { 2921 for (size_t i = 0, e = moves_.Size(); i < e; ++i) { 2922 DCHECK_NE(moves_.Get(i).GetInstruction(), instruction) 2923 << "Doing parallel moves for the same instruction."; 2924 } 2925 } 2926 for (size_t i = 0, e = moves_.Size(); i < e; ++i) { 2927 DCHECK(!destination.Equals(moves_.Get(i).GetDestination())) 2928 << "Same destination for two moves in a parallel move."; 2929 } 2930 } 2931 moves_.Add(MoveOperands(source, destination, instruction)); 2932 } 2933 } 2934 2935 MoveOperands* MoveOperandsAt(size_t index) const { 2936 return moves_.GetRawStorage() + index; 2937 } 2938 2939 size_t NumMoves() const { return moves_.Size(); } 2940 2941 DECLARE_INSTRUCTION(ParallelMove); 2942 2943 private: 2944 GrowableArray<MoveOperands> moves_; 2945 2946 DISALLOW_COPY_AND_ASSIGN(HParallelMove); 2947}; 2948 2949class HGraphVisitor : public ValueObject { 2950 public: 2951 explicit HGraphVisitor(HGraph* graph) : graph_(graph) {} 2952 virtual ~HGraphVisitor() {} 2953 2954 virtual void VisitInstruction(HInstruction* instruction) { UNUSED(instruction); } 2955 virtual void VisitBasicBlock(HBasicBlock* block); 2956 2957 // Visit the graph following basic block insertion order. 2958 void VisitInsertionOrder(); 2959 2960 // Visit the graph following dominator tree reverse post-order. 2961 void VisitReversePostOrder(); 2962 2963 HGraph* GetGraph() const { return graph_; } 2964 2965 // Visit functions for instruction classes. 2966#define DECLARE_VISIT_INSTRUCTION(name, super) \ 2967 virtual void Visit##name(H##name* instr) { VisitInstruction(instr); } 2968 2969 FOR_EACH_INSTRUCTION(DECLARE_VISIT_INSTRUCTION) 2970 2971#undef DECLARE_VISIT_INSTRUCTION 2972 2973 private: 2974 HGraph* const graph_; 2975 2976 DISALLOW_COPY_AND_ASSIGN(HGraphVisitor); 2977}; 2978 2979class HGraphDelegateVisitor : public HGraphVisitor { 2980 public: 2981 explicit HGraphDelegateVisitor(HGraph* graph) : HGraphVisitor(graph) {} 2982 virtual ~HGraphDelegateVisitor() {} 2983 2984 // Visit functions that delegate to to super class. 2985#define DECLARE_VISIT_INSTRUCTION(name, super) \ 2986 virtual void Visit##name(H##name* instr) OVERRIDE { Visit##super(instr); } 2987 2988 FOR_EACH_INSTRUCTION(DECLARE_VISIT_INSTRUCTION) 2989 2990#undef DECLARE_VISIT_INSTRUCTION 2991 2992 private: 2993 DISALLOW_COPY_AND_ASSIGN(HGraphDelegateVisitor); 2994}; 2995 2996class HInsertionOrderIterator : public ValueObject { 2997 public: 2998 explicit HInsertionOrderIterator(const HGraph& graph) : graph_(graph), index_(0) {} 2999 3000 bool Done() const { return index_ == graph_.GetBlocks().Size(); } 3001 HBasicBlock* Current() const { return graph_.GetBlocks().Get(index_); } 3002 void Advance() { ++index_; } 3003 3004 private: 3005 const HGraph& graph_; 3006 size_t index_; 3007 3008 DISALLOW_COPY_AND_ASSIGN(HInsertionOrderIterator); 3009}; 3010 3011class HReversePostOrderIterator : public ValueObject { 3012 public: 3013 explicit HReversePostOrderIterator(const HGraph& graph) : graph_(graph), index_(0) {} 3014 3015 bool Done() const { return index_ == graph_.GetReversePostOrder().Size(); } 3016 HBasicBlock* Current() const { return graph_.GetReversePostOrder().Get(index_); } 3017 void Advance() { ++index_; } 3018 3019 private: 3020 const HGraph& graph_; 3021 size_t index_; 3022 3023 DISALLOW_COPY_AND_ASSIGN(HReversePostOrderIterator); 3024}; 3025 3026class HPostOrderIterator : public ValueObject { 3027 public: 3028 explicit HPostOrderIterator(const HGraph& graph) 3029 : graph_(graph), index_(graph_.GetReversePostOrder().Size()) {} 3030 3031 bool Done() const { return index_ == 0; } 3032 HBasicBlock* Current() const { return graph_.GetReversePostOrder().Get(index_ - 1); } 3033 void Advance() { --index_; } 3034 3035 private: 3036 const HGraph& graph_; 3037 size_t index_; 3038 3039 DISALLOW_COPY_AND_ASSIGN(HPostOrderIterator); 3040}; 3041 3042} // namespace art 3043 3044#endif // ART_COMPILER_OPTIMIZING_NODES_H_ 3045