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