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