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