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