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