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