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