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