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