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