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