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