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