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