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