nodes.h revision beba9302bec33d72beb582970bf23d056f62641f
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_MIPS64(M) 968 969#define FOR_EACH_CONCRETE_INSTRUCTION_X86(M) 970 971#define FOR_EACH_CONCRETE_INSTRUCTION_X86_64(M) 972 973#define FOR_EACH_CONCRETE_INSTRUCTION(M) \ 974 FOR_EACH_CONCRETE_INSTRUCTION_COMMON(M) \ 975 FOR_EACH_CONCRETE_INSTRUCTION_ARM(M) \ 976 FOR_EACH_CONCRETE_INSTRUCTION_ARM64(M) \ 977 FOR_EACH_CONCRETE_INSTRUCTION_MIPS64(M) \ 978 FOR_EACH_CONCRETE_INSTRUCTION_X86(M) \ 979 FOR_EACH_CONCRETE_INSTRUCTION_X86_64(M) 980 981#define FOR_EACH_INSTRUCTION(M) \ 982 FOR_EACH_CONCRETE_INSTRUCTION(M) \ 983 M(Constant, Instruction) \ 984 M(UnaryOperation, Instruction) \ 985 M(BinaryOperation, Instruction) \ 986 M(Invoke, Instruction) 987 988#define FORWARD_DECLARATION(type, super) class H##type; 989FOR_EACH_INSTRUCTION(FORWARD_DECLARATION) 990#undef FORWARD_DECLARATION 991 992#define DECLARE_INSTRUCTION(type) \ 993 InstructionKind GetKind() const OVERRIDE { return k##type; } \ 994 const char* DebugName() const OVERRIDE { return #type; } \ 995 const H##type* As##type() const OVERRIDE { return this; } \ 996 H##type* As##type() OVERRIDE { return this; } \ 997 bool InstructionTypeEquals(HInstruction* other) const OVERRIDE { \ 998 return other->Is##type(); \ 999 } \ 1000 void Accept(HGraphVisitor* visitor) OVERRIDE 1001 1002template <typename T> class HUseList; 1003 1004template <typename T> 1005class HUseListNode : public ArenaObject<kArenaAllocMisc> { 1006 public: 1007 HUseListNode* GetPrevious() const { return prev_; } 1008 HUseListNode* GetNext() const { return next_; } 1009 T GetUser() const { return user_; } 1010 size_t GetIndex() const { return index_; } 1011 void SetIndex(size_t index) { index_ = index; } 1012 1013 private: 1014 HUseListNode(T user, size_t index) 1015 : user_(user), index_(index), prev_(nullptr), next_(nullptr) {} 1016 1017 T const user_; 1018 size_t index_; 1019 HUseListNode<T>* prev_; 1020 HUseListNode<T>* next_; 1021 1022 friend class HUseList<T>; 1023 1024 DISALLOW_COPY_AND_ASSIGN(HUseListNode); 1025}; 1026 1027template <typename T> 1028class HUseList : public ValueObject { 1029 public: 1030 HUseList() : first_(nullptr) {} 1031 1032 void Clear() { 1033 first_ = nullptr; 1034 } 1035 1036 // Adds a new entry at the beginning of the use list and returns 1037 // the newly created node. 1038 HUseListNode<T>* AddUse(T user, size_t index, ArenaAllocator* arena) { 1039 HUseListNode<T>* new_node = new (arena) HUseListNode<T>(user, index); 1040 if (IsEmpty()) { 1041 first_ = new_node; 1042 } else { 1043 first_->prev_ = new_node; 1044 new_node->next_ = first_; 1045 first_ = new_node; 1046 } 1047 return new_node; 1048 } 1049 1050 HUseListNode<T>* GetFirst() const { 1051 return first_; 1052 } 1053 1054 void Remove(HUseListNode<T>* node) { 1055 DCHECK(node != nullptr); 1056 DCHECK(Contains(node)); 1057 1058 if (node->prev_ != nullptr) { 1059 node->prev_->next_ = node->next_; 1060 } 1061 if (node->next_ != nullptr) { 1062 node->next_->prev_ = node->prev_; 1063 } 1064 if (node == first_) { 1065 first_ = node->next_; 1066 } 1067 } 1068 1069 bool Contains(const HUseListNode<T>* node) const { 1070 if (node == nullptr) { 1071 return false; 1072 } 1073 for (HUseListNode<T>* current = first_; current != nullptr; current = current->GetNext()) { 1074 if (current == node) { 1075 return true; 1076 } 1077 } 1078 return false; 1079 } 1080 1081 bool IsEmpty() const { 1082 return first_ == nullptr; 1083 } 1084 1085 bool HasOnlyOneUse() const { 1086 return first_ != nullptr && first_->next_ == nullptr; 1087 } 1088 1089 size_t SizeSlow() const { 1090 size_t count = 0; 1091 for (HUseListNode<T>* current = first_; current != nullptr; current = current->GetNext()) { 1092 ++count; 1093 } 1094 return count; 1095 } 1096 1097 private: 1098 HUseListNode<T>* first_; 1099}; 1100 1101template<typename T> 1102class HUseIterator : public ValueObject { 1103 public: 1104 explicit HUseIterator(const HUseList<T>& uses) : current_(uses.GetFirst()) {} 1105 1106 bool Done() const { return current_ == nullptr; } 1107 1108 void Advance() { 1109 DCHECK(!Done()); 1110 current_ = current_->GetNext(); 1111 } 1112 1113 HUseListNode<T>* Current() const { 1114 DCHECK(!Done()); 1115 return current_; 1116 } 1117 1118 private: 1119 HUseListNode<T>* current_; 1120 1121 friend class HValue; 1122}; 1123 1124// This class is used by HEnvironment and HInstruction classes to record the 1125// instructions they use and pointers to the corresponding HUseListNodes kept 1126// by the used instructions. 1127template <typename T> 1128class HUserRecord : public ValueObject { 1129 public: 1130 HUserRecord() : instruction_(nullptr), use_node_(nullptr) {} 1131 explicit HUserRecord(HInstruction* instruction) : instruction_(instruction), use_node_(nullptr) {} 1132 1133 HUserRecord(const HUserRecord<T>& old_record, HUseListNode<T>* use_node) 1134 : instruction_(old_record.instruction_), use_node_(use_node) { 1135 DCHECK(instruction_ != nullptr); 1136 DCHECK(use_node_ != nullptr); 1137 DCHECK(old_record.use_node_ == nullptr); 1138 } 1139 1140 HInstruction* GetInstruction() const { return instruction_; } 1141 HUseListNode<T>* GetUseNode() const { return use_node_; } 1142 1143 private: 1144 // Instruction used by the user. 1145 HInstruction* instruction_; 1146 1147 // Corresponding entry in the use list kept by 'instruction_'. 1148 HUseListNode<T>* use_node_; 1149}; 1150 1151// TODO: Add better documentation to this class and maybe refactor with more suggestive names. 1152// - Has(All)SideEffects suggests that all the side effects are present but only ChangesSomething 1153// flag is consider. 1154// - DependsOn suggests that there is a real dependency between side effects but it only 1155// checks DependendsOnSomething flag. 1156// 1157// Represents the side effects an instruction may have. 1158class SideEffects : public ValueObject { 1159 public: 1160 SideEffects() : flags_(0) {} 1161 1162 static SideEffects None() { 1163 return SideEffects(0); 1164 } 1165 1166 static SideEffects All() { 1167 return SideEffects(ChangesSomething().flags_ | DependsOnSomething().flags_); 1168 } 1169 1170 static SideEffects ChangesSomething() { 1171 return SideEffects((1 << kFlagChangesCount) - 1); 1172 } 1173 1174 static SideEffects DependsOnSomething() { 1175 int count = kFlagDependsOnCount - kFlagChangesCount; 1176 return SideEffects(((1 << count) - 1) << kFlagChangesCount); 1177 } 1178 1179 SideEffects Union(SideEffects other) const { 1180 return SideEffects(flags_ | other.flags_); 1181 } 1182 1183 bool HasSideEffects() const { 1184 size_t all_bits_set = (1 << kFlagChangesCount) - 1; 1185 return (flags_ & all_bits_set) != 0; 1186 } 1187 1188 bool HasAllSideEffects() const { 1189 size_t all_bits_set = (1 << kFlagChangesCount) - 1; 1190 return all_bits_set == (flags_ & all_bits_set); 1191 } 1192 1193 bool DependsOn(SideEffects other) const { 1194 size_t depends_flags = other.ComputeDependsFlags(); 1195 return (flags_ & depends_flags) != 0; 1196 } 1197 1198 bool HasDependencies() const { 1199 int count = kFlagDependsOnCount - kFlagChangesCount; 1200 size_t all_bits_set = (1 << count) - 1; 1201 return ((flags_ >> kFlagChangesCount) & all_bits_set) != 0; 1202 } 1203 1204 private: 1205 static constexpr int kFlagChangesSomething = 0; 1206 static constexpr int kFlagChangesCount = kFlagChangesSomething + 1; 1207 1208 static constexpr int kFlagDependsOnSomething = kFlagChangesCount; 1209 static constexpr int kFlagDependsOnCount = kFlagDependsOnSomething + 1; 1210 1211 explicit SideEffects(size_t flags) : flags_(flags) {} 1212 1213 size_t ComputeDependsFlags() const { 1214 return flags_ << kFlagChangesCount; 1215 } 1216 1217 size_t flags_; 1218}; 1219 1220// A HEnvironment object contains the values of virtual registers at a given location. 1221class HEnvironment : public ArenaObject<kArenaAllocMisc> { 1222 public: 1223 HEnvironment(ArenaAllocator* arena, 1224 size_t number_of_vregs, 1225 const DexFile& dex_file, 1226 uint32_t method_idx, 1227 uint32_t dex_pc, 1228 InvokeType invoke_type, 1229 HInstruction* holder) 1230 : vregs_(arena, number_of_vregs), 1231 locations_(arena, number_of_vregs), 1232 parent_(nullptr), 1233 dex_file_(dex_file), 1234 method_idx_(method_idx), 1235 dex_pc_(dex_pc), 1236 invoke_type_(invoke_type), 1237 holder_(holder) { 1238 vregs_.SetSize(number_of_vregs); 1239 for (size_t i = 0; i < number_of_vregs; i++) { 1240 vregs_.Put(i, HUserRecord<HEnvironment*>()); 1241 } 1242 1243 locations_.SetSize(number_of_vregs); 1244 for (size_t i = 0; i < number_of_vregs; ++i) { 1245 locations_.Put(i, Location()); 1246 } 1247 } 1248 1249 HEnvironment(ArenaAllocator* arena, const HEnvironment& to_copy, HInstruction* holder) 1250 : HEnvironment(arena, 1251 to_copy.Size(), 1252 to_copy.GetDexFile(), 1253 to_copy.GetMethodIdx(), 1254 to_copy.GetDexPc(), 1255 to_copy.GetInvokeType(), 1256 holder) {} 1257 1258 void SetAndCopyParentChain(ArenaAllocator* allocator, HEnvironment* parent) { 1259 if (parent_ != nullptr) { 1260 parent_->SetAndCopyParentChain(allocator, parent); 1261 } else { 1262 parent_ = new (allocator) HEnvironment(allocator, *parent, holder_); 1263 parent_->CopyFrom(parent); 1264 if (parent->GetParent() != nullptr) { 1265 parent_->SetAndCopyParentChain(allocator, parent->GetParent()); 1266 } 1267 } 1268 } 1269 1270 void CopyFrom(const GrowableArray<HInstruction*>& locals); 1271 void CopyFrom(HEnvironment* environment); 1272 1273 // Copy from `env`. If it's a loop phi for `loop_header`, copy the first 1274 // input to the loop phi instead. This is for inserting instructions that 1275 // require an environment (like HDeoptimization) in the loop pre-header. 1276 void CopyFromWithLoopPhiAdjustment(HEnvironment* env, HBasicBlock* loop_header); 1277 1278 void SetRawEnvAt(size_t index, HInstruction* instruction) { 1279 vregs_.Put(index, HUserRecord<HEnvironment*>(instruction)); 1280 } 1281 1282 HInstruction* GetInstructionAt(size_t index) const { 1283 return vregs_.Get(index).GetInstruction(); 1284 } 1285 1286 void RemoveAsUserOfInput(size_t index) const; 1287 1288 size_t Size() const { return vregs_.Size(); } 1289 1290 HEnvironment* GetParent() const { return parent_; } 1291 1292 void SetLocationAt(size_t index, Location location) { 1293 locations_.Put(index, location); 1294 } 1295 1296 Location GetLocationAt(size_t index) const { 1297 return locations_.Get(index); 1298 } 1299 1300 uint32_t GetDexPc() const { 1301 return dex_pc_; 1302 } 1303 1304 uint32_t GetMethodIdx() const { 1305 return method_idx_; 1306 } 1307 1308 InvokeType GetInvokeType() const { 1309 return invoke_type_; 1310 } 1311 1312 const DexFile& GetDexFile() const { 1313 return dex_file_; 1314 } 1315 1316 HInstruction* GetHolder() const { 1317 return holder_; 1318 } 1319 1320 private: 1321 // Record instructions' use entries of this environment for constant-time removal. 1322 // It should only be called by HInstruction when a new environment use is added. 1323 void RecordEnvUse(HUseListNode<HEnvironment*>* env_use) { 1324 DCHECK(env_use->GetUser() == this); 1325 size_t index = env_use->GetIndex(); 1326 vregs_.Put(index, HUserRecord<HEnvironment*>(vregs_.Get(index), env_use)); 1327 } 1328 1329 GrowableArray<HUserRecord<HEnvironment*> > vregs_; 1330 GrowableArray<Location> locations_; 1331 HEnvironment* parent_; 1332 const DexFile& dex_file_; 1333 const uint32_t method_idx_; 1334 const uint32_t dex_pc_; 1335 const InvokeType invoke_type_; 1336 1337 // The instruction that holds this environment. Only used in debug mode 1338 // to ensure the graph is consistent. 1339 HInstruction* const holder_; 1340 1341 friend class HInstruction; 1342 1343 DISALLOW_COPY_AND_ASSIGN(HEnvironment); 1344}; 1345 1346class ReferenceTypeInfo : ValueObject { 1347 public: 1348 typedef Handle<mirror::Class> TypeHandle; 1349 1350 static ReferenceTypeInfo Create(TypeHandle type_handle, bool is_exact) 1351 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) { 1352 if (type_handle->IsObjectClass()) { 1353 // Override the type handle to be consistent with the case when we get to 1354 // Top but don't have the Object class available. It avoids having to guess 1355 // what value the type_handle has when it's Top. 1356 return ReferenceTypeInfo(TypeHandle(), is_exact, true); 1357 } else { 1358 return ReferenceTypeInfo(type_handle, is_exact, false); 1359 } 1360 } 1361 1362 static ReferenceTypeInfo CreateTop(bool is_exact) { 1363 return ReferenceTypeInfo(TypeHandle(), is_exact, true); 1364 } 1365 1366 bool IsExact() const { return is_exact_; } 1367 bool IsTop() const { return is_top_; } 1368 bool IsInterface() const SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) { 1369 return !IsTop() && GetTypeHandle()->IsInterface(); 1370 } 1371 1372 Handle<mirror::Class> GetTypeHandle() const { return type_handle_; } 1373 1374 bool IsSupertypeOf(ReferenceTypeInfo rti) const SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) { 1375 if (IsTop()) { 1376 // Top (equivalent for java.lang.Object) is supertype of anything. 1377 return true; 1378 } 1379 if (rti.IsTop()) { 1380 // If we get here `this` is not Top() so it can't be a supertype. 1381 return false; 1382 } 1383 return GetTypeHandle()->IsAssignableFrom(rti.GetTypeHandle().Get()); 1384 } 1385 1386 // Returns true if the type information provide the same amount of details. 1387 // Note that it does not mean that the instructions have the same actual type 1388 // (e.g. tops are equal but they can be the result of a merge). 1389 bool IsEqual(ReferenceTypeInfo rti) SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) { 1390 if (IsExact() != rti.IsExact()) { 1391 return false; 1392 } 1393 if (IsTop() && rti.IsTop()) { 1394 // `Top` means java.lang.Object, so the types are equivalent. 1395 return true; 1396 } 1397 if (IsTop() || rti.IsTop()) { 1398 // If only one is top or object than they are not equivalent. 1399 // NB: We need this extra check because the type_handle of `Top` is invalid 1400 // and we cannot inspect its reference. 1401 return false; 1402 } 1403 1404 // Finally check the types. 1405 return GetTypeHandle().Get() == rti.GetTypeHandle().Get(); 1406 } 1407 1408 private: 1409 ReferenceTypeInfo() : ReferenceTypeInfo(TypeHandle(), false, true) {} 1410 ReferenceTypeInfo(TypeHandle type_handle, bool is_exact, bool is_top) 1411 : type_handle_(type_handle), is_exact_(is_exact), is_top_(is_top) {} 1412 1413 // The class of the object. 1414 TypeHandle type_handle_; 1415 // Whether or not the type is exact or a superclass of the actual type. 1416 // Whether or not we have any information about this type. 1417 bool is_exact_; 1418 // A true value here means that the object type should be java.lang.Object. 1419 // We don't have access to the corresponding mirror object every time so this 1420 // flag acts as a substitute. When true, the TypeHandle refers to a null 1421 // pointer and should not be used. 1422 bool is_top_; 1423}; 1424 1425std::ostream& operator<<(std::ostream& os, const ReferenceTypeInfo& rhs); 1426 1427class HInstruction : public ArenaObject<kArenaAllocMisc> { 1428 public: 1429 explicit HInstruction(SideEffects side_effects) 1430 : previous_(nullptr), 1431 next_(nullptr), 1432 block_(nullptr), 1433 id_(-1), 1434 ssa_index_(-1), 1435 environment_(nullptr), 1436 locations_(nullptr), 1437 live_interval_(nullptr), 1438 lifetime_position_(kNoLifetime), 1439 side_effects_(side_effects), 1440 reference_type_info_(ReferenceTypeInfo::CreateTop(/* is_exact */ false)) {} 1441 1442 virtual ~HInstruction() {} 1443 1444#define DECLARE_KIND(type, super) k##type, 1445 enum InstructionKind { 1446 FOR_EACH_INSTRUCTION(DECLARE_KIND) 1447 }; 1448#undef DECLARE_KIND 1449 1450 HInstruction* GetNext() const { return next_; } 1451 HInstruction* GetPrevious() const { return previous_; } 1452 1453 HInstruction* GetNextDisregardingMoves() const; 1454 HInstruction* GetPreviousDisregardingMoves() const; 1455 1456 HBasicBlock* GetBlock() const { return block_; } 1457 void SetBlock(HBasicBlock* block) { block_ = block; } 1458 bool IsInBlock() const { return block_ != nullptr; } 1459 bool IsInLoop() const { return block_->IsInLoop(); } 1460 bool IsLoopHeaderPhi() { return IsPhi() && block_->IsLoopHeader(); } 1461 1462 virtual size_t InputCount() const = 0; 1463 HInstruction* InputAt(size_t i) const { return InputRecordAt(i).GetInstruction(); } 1464 1465 virtual void Accept(HGraphVisitor* visitor) = 0; 1466 virtual const char* DebugName() const = 0; 1467 1468 virtual Primitive::Type GetType() const { return Primitive::kPrimVoid; } 1469 void SetRawInputAt(size_t index, HInstruction* input) { 1470 SetRawInputRecordAt(index, HUserRecord<HInstruction*>(input)); 1471 } 1472 1473 virtual bool NeedsEnvironment() const { return false; } 1474 virtual uint32_t GetDexPc() const { 1475 LOG(FATAL) << "GetDexPc() cannot be called on an instruction that" 1476 " does not need an environment"; 1477 UNREACHABLE(); 1478 } 1479 virtual bool IsControlFlow() const { return false; } 1480 virtual bool CanThrow() const { return false; } 1481 bool HasSideEffects() const { return side_effects_.HasSideEffects(); } 1482 1483 // Does not apply for all instructions, but having this at top level greatly 1484 // simplifies the null check elimination. 1485 virtual bool CanBeNull() const { 1486 DCHECK_EQ(GetType(), Primitive::kPrimNot) << "CanBeNull only applies to reference types"; 1487 return true; 1488 } 1489 1490 virtual bool CanDoImplicitNullCheckOn(HInstruction* obj) const { 1491 UNUSED(obj); 1492 return false; 1493 } 1494 1495 void SetReferenceTypeInfo(ReferenceTypeInfo reference_type_info) { 1496 DCHECK_EQ(GetType(), Primitive::kPrimNot); 1497 reference_type_info_ = reference_type_info; 1498 } 1499 1500 ReferenceTypeInfo GetReferenceTypeInfo() const { 1501 DCHECK_EQ(GetType(), Primitive::kPrimNot); 1502 return reference_type_info_; 1503 } 1504 1505 void AddUseAt(HInstruction* user, size_t index) { 1506 DCHECK(user != nullptr); 1507 HUseListNode<HInstruction*>* use = 1508 uses_.AddUse(user, index, GetBlock()->GetGraph()->GetArena()); 1509 user->SetRawInputRecordAt(index, HUserRecord<HInstruction*>(user->InputRecordAt(index), use)); 1510 } 1511 1512 void AddEnvUseAt(HEnvironment* user, size_t index) { 1513 DCHECK(user != nullptr); 1514 HUseListNode<HEnvironment*>* env_use = 1515 env_uses_.AddUse(user, index, GetBlock()->GetGraph()->GetArena()); 1516 user->RecordEnvUse(env_use); 1517 } 1518 1519 void RemoveAsUserOfInput(size_t input) { 1520 HUserRecord<HInstruction*> input_use = InputRecordAt(input); 1521 input_use.GetInstruction()->uses_.Remove(input_use.GetUseNode()); 1522 } 1523 1524 const HUseList<HInstruction*>& GetUses() const { return uses_; } 1525 const HUseList<HEnvironment*>& GetEnvUses() const { return env_uses_; } 1526 1527 bool HasUses() const { return !uses_.IsEmpty() || !env_uses_.IsEmpty(); } 1528 bool HasEnvironmentUses() const { return !env_uses_.IsEmpty(); } 1529 bool HasNonEnvironmentUses() const { return !uses_.IsEmpty(); } 1530 bool HasOnlyOneNonEnvironmentUse() const { 1531 return !HasEnvironmentUses() && GetUses().HasOnlyOneUse(); 1532 } 1533 1534 // Does this instruction strictly dominate `other_instruction`? 1535 // Returns false if this instruction and `other_instruction` are the same. 1536 // Aborts if this instruction and `other_instruction` are both phis. 1537 bool StrictlyDominates(HInstruction* other_instruction) const; 1538 1539 int GetId() const { return id_; } 1540 void SetId(int id) { id_ = id; } 1541 1542 int GetSsaIndex() const { return ssa_index_; } 1543 void SetSsaIndex(int ssa_index) { ssa_index_ = ssa_index; } 1544 bool HasSsaIndex() const { return ssa_index_ != -1; } 1545 1546 bool HasEnvironment() const { return environment_ != nullptr; } 1547 HEnvironment* GetEnvironment() const { return environment_; } 1548 // Set the `environment_` field. Raw because this method does not 1549 // update the uses lists. 1550 void SetRawEnvironment(HEnvironment* environment) { 1551 DCHECK(environment_ == nullptr); 1552 DCHECK_EQ(environment->GetHolder(), this); 1553 environment_ = environment; 1554 } 1555 1556 // Set the environment of this instruction, copying it from `environment`. While 1557 // copying, the uses lists are being updated. 1558 void CopyEnvironmentFrom(HEnvironment* environment) { 1559 DCHECK(environment_ == nullptr); 1560 ArenaAllocator* allocator = GetBlock()->GetGraph()->GetArena(); 1561 environment_ = new (allocator) HEnvironment(allocator, *environment, this); 1562 environment_->CopyFrom(environment); 1563 if (environment->GetParent() != nullptr) { 1564 environment_->SetAndCopyParentChain(allocator, environment->GetParent()); 1565 } 1566 } 1567 1568 void CopyEnvironmentFromWithLoopPhiAdjustment(HEnvironment* environment, 1569 HBasicBlock* block) { 1570 DCHECK(environment_ == nullptr); 1571 ArenaAllocator* allocator = GetBlock()->GetGraph()->GetArena(); 1572 environment_ = new (allocator) HEnvironment(allocator, *environment, this); 1573 environment_->CopyFromWithLoopPhiAdjustment(environment, block); 1574 if (environment->GetParent() != nullptr) { 1575 environment_->SetAndCopyParentChain(allocator, environment->GetParent()); 1576 } 1577 } 1578 1579 // Returns the number of entries in the environment. Typically, that is the 1580 // number of dex registers in a method. It could be more in case of inlining. 1581 size_t EnvironmentSize() const; 1582 1583 LocationSummary* GetLocations() const { return locations_; } 1584 void SetLocations(LocationSummary* locations) { locations_ = locations; } 1585 1586 void ReplaceWith(HInstruction* instruction); 1587 void ReplaceInput(HInstruction* replacement, size_t index); 1588 1589 // This is almost the same as doing `ReplaceWith()`. But in this helper, the 1590 // uses of this instruction by `other` are *not* updated. 1591 void ReplaceWithExceptInReplacementAtIndex(HInstruction* other, size_t use_index) { 1592 ReplaceWith(other); 1593 other->ReplaceInput(this, use_index); 1594 } 1595 1596 // Move `this` instruction before `cursor`. 1597 void MoveBefore(HInstruction* cursor); 1598 1599#define INSTRUCTION_TYPE_CHECK(type, super) \ 1600 bool Is##type() const { return (As##type() != nullptr); } \ 1601 virtual const H##type* As##type() const { return nullptr; } \ 1602 virtual H##type* As##type() { return nullptr; } 1603 1604 FOR_EACH_INSTRUCTION(INSTRUCTION_TYPE_CHECK) 1605#undef INSTRUCTION_TYPE_CHECK 1606 1607 // Returns whether the instruction can be moved within the graph. 1608 virtual bool CanBeMoved() const { return false; } 1609 1610 // Returns whether the two instructions are of the same kind. 1611 virtual bool InstructionTypeEquals(HInstruction* other) const { 1612 UNUSED(other); 1613 return false; 1614 } 1615 1616 // Returns whether any data encoded in the two instructions is equal. 1617 // This method does not look at the inputs. Both instructions must be 1618 // of the same type, otherwise the method has undefined behavior. 1619 virtual bool InstructionDataEquals(HInstruction* other) const { 1620 UNUSED(other); 1621 return false; 1622 } 1623 1624 // Returns whether two instructions are equal, that is: 1625 // 1) They have the same type and contain the same data (InstructionDataEquals). 1626 // 2) Their inputs are identical. 1627 bool Equals(HInstruction* other) const; 1628 1629 virtual InstructionKind GetKind() const = 0; 1630 1631 virtual size_t ComputeHashCode() const { 1632 size_t result = GetKind(); 1633 for (size_t i = 0, e = InputCount(); i < e; ++i) { 1634 result = (result * 31) + InputAt(i)->GetId(); 1635 } 1636 return result; 1637 } 1638 1639 SideEffects GetSideEffects() const { return side_effects_; } 1640 1641 size_t GetLifetimePosition() const { return lifetime_position_; } 1642 void SetLifetimePosition(size_t position) { lifetime_position_ = position; } 1643 LiveInterval* GetLiveInterval() const { return live_interval_; } 1644 void SetLiveInterval(LiveInterval* interval) { live_interval_ = interval; } 1645 bool HasLiveInterval() const { return live_interval_ != nullptr; } 1646 1647 bool IsSuspendCheckEntry() const { return IsSuspendCheck() && GetBlock()->IsEntryBlock(); } 1648 1649 // Returns whether the code generation of the instruction will require to have access 1650 // to the current method. Such instructions are: 1651 // (1): Instructions that require an environment, as calling the runtime requires 1652 // to walk the stack and have the current method stored at a specific stack address. 1653 // (2): Object literals like classes and strings, that are loaded from the dex cache 1654 // fields of the current method. 1655 bool NeedsCurrentMethod() const { 1656 return NeedsEnvironment() || IsLoadClass() || IsLoadString(); 1657 } 1658 1659 virtual bool NeedsDexCache() const { return false; } 1660 1661 protected: 1662 virtual const HUserRecord<HInstruction*> InputRecordAt(size_t i) const = 0; 1663 virtual void SetRawInputRecordAt(size_t index, const HUserRecord<HInstruction*>& input) = 0; 1664 1665 private: 1666 void RemoveEnvironmentUser(HUseListNode<HEnvironment*>* use_node) { env_uses_.Remove(use_node); } 1667 1668 HInstruction* previous_; 1669 HInstruction* next_; 1670 HBasicBlock* block_; 1671 1672 // An instruction gets an id when it is added to the graph. 1673 // It reflects creation order. A negative id means the instruction 1674 // has not been added to the graph. 1675 int id_; 1676 1677 // When doing liveness analysis, instructions that have uses get an SSA index. 1678 int ssa_index_; 1679 1680 // List of instructions that have this instruction as input. 1681 HUseList<HInstruction*> uses_; 1682 1683 // List of environments that contain this instruction. 1684 HUseList<HEnvironment*> env_uses_; 1685 1686 // The environment associated with this instruction. Not null if the instruction 1687 // might jump out of the method. 1688 HEnvironment* environment_; 1689 1690 // Set by the code generator. 1691 LocationSummary* locations_; 1692 1693 // Set by the liveness analysis. 1694 LiveInterval* live_interval_; 1695 1696 // Set by the liveness analysis, this is the position in a linear 1697 // order of blocks where this instruction's live interval start. 1698 size_t lifetime_position_; 1699 1700 const SideEffects side_effects_; 1701 1702 // TODO: for primitive types this should be marked as invalid. 1703 ReferenceTypeInfo reference_type_info_; 1704 1705 friend class GraphChecker; 1706 friend class HBasicBlock; 1707 friend class HEnvironment; 1708 friend class HGraph; 1709 friend class HInstructionList; 1710 1711 DISALLOW_COPY_AND_ASSIGN(HInstruction); 1712}; 1713std::ostream& operator<<(std::ostream& os, const HInstruction::InstructionKind& rhs); 1714 1715class HInputIterator : public ValueObject { 1716 public: 1717 explicit HInputIterator(HInstruction* instruction) : instruction_(instruction), index_(0) {} 1718 1719 bool Done() const { return index_ == instruction_->InputCount(); } 1720 HInstruction* Current() const { return instruction_->InputAt(index_); } 1721 void Advance() { index_++; } 1722 1723 private: 1724 HInstruction* instruction_; 1725 size_t index_; 1726 1727 DISALLOW_COPY_AND_ASSIGN(HInputIterator); 1728}; 1729 1730class HInstructionIterator : public ValueObject { 1731 public: 1732 explicit HInstructionIterator(const HInstructionList& instructions) 1733 : instruction_(instructions.first_instruction_) { 1734 next_ = Done() ? nullptr : instruction_->GetNext(); 1735 } 1736 1737 bool Done() const { return instruction_ == nullptr; } 1738 HInstruction* Current() const { return instruction_; } 1739 void Advance() { 1740 instruction_ = next_; 1741 next_ = Done() ? nullptr : instruction_->GetNext(); 1742 } 1743 1744 private: 1745 HInstruction* instruction_; 1746 HInstruction* next_; 1747 1748 DISALLOW_COPY_AND_ASSIGN(HInstructionIterator); 1749}; 1750 1751class HBackwardInstructionIterator : public ValueObject { 1752 public: 1753 explicit HBackwardInstructionIterator(const HInstructionList& instructions) 1754 : instruction_(instructions.last_instruction_) { 1755 next_ = Done() ? nullptr : instruction_->GetPrevious(); 1756 } 1757 1758 bool Done() const { return instruction_ == nullptr; } 1759 HInstruction* Current() const { return instruction_; } 1760 void Advance() { 1761 instruction_ = next_; 1762 next_ = Done() ? nullptr : instruction_->GetPrevious(); 1763 } 1764 1765 private: 1766 HInstruction* instruction_; 1767 HInstruction* next_; 1768 1769 DISALLOW_COPY_AND_ASSIGN(HBackwardInstructionIterator); 1770}; 1771 1772// An embedded container with N elements of type T. Used (with partial 1773// specialization for N=0) because embedded arrays cannot have size 0. 1774template<typename T, intptr_t N> 1775class EmbeddedArray { 1776 public: 1777 EmbeddedArray() : elements_() {} 1778 1779 intptr_t GetLength() const { return N; } 1780 1781 const T& operator[](intptr_t i) const { 1782 DCHECK_LT(i, GetLength()); 1783 return elements_[i]; 1784 } 1785 1786 T& operator[](intptr_t i) { 1787 DCHECK_LT(i, GetLength()); 1788 return elements_[i]; 1789 } 1790 1791 const T& At(intptr_t i) const { 1792 return (*this)[i]; 1793 } 1794 1795 void SetAt(intptr_t i, const T& val) { 1796 (*this)[i] = val; 1797 } 1798 1799 private: 1800 T elements_[N]; 1801}; 1802 1803template<typename T> 1804class EmbeddedArray<T, 0> { 1805 public: 1806 intptr_t length() const { return 0; } 1807 const T& operator[](intptr_t i) const { 1808 UNUSED(i); 1809 LOG(FATAL) << "Unreachable"; 1810 UNREACHABLE(); 1811 } 1812 T& operator[](intptr_t i) { 1813 UNUSED(i); 1814 LOG(FATAL) << "Unreachable"; 1815 UNREACHABLE(); 1816 } 1817}; 1818 1819template<intptr_t N> 1820class HTemplateInstruction: public HInstruction { 1821 public: 1822 HTemplateInstruction<N>(SideEffects side_effects) 1823 : HInstruction(side_effects), inputs_() {} 1824 virtual ~HTemplateInstruction() {} 1825 1826 size_t InputCount() const OVERRIDE { return N; } 1827 1828 protected: 1829 const HUserRecord<HInstruction*> InputRecordAt(size_t i) const OVERRIDE { return inputs_[i]; } 1830 1831 void SetRawInputRecordAt(size_t i, const HUserRecord<HInstruction*>& input) OVERRIDE { 1832 inputs_[i] = input; 1833 } 1834 1835 private: 1836 EmbeddedArray<HUserRecord<HInstruction*>, N> inputs_; 1837 1838 friend class SsaBuilder; 1839}; 1840 1841template<intptr_t N> 1842class HExpression : public HTemplateInstruction<N> { 1843 public: 1844 HExpression<N>(Primitive::Type type, SideEffects side_effects) 1845 : HTemplateInstruction<N>(side_effects), type_(type) {} 1846 virtual ~HExpression() {} 1847 1848 Primitive::Type GetType() const OVERRIDE { return type_; } 1849 1850 protected: 1851 Primitive::Type type_; 1852}; 1853 1854// Represents dex's RETURN_VOID opcode. A HReturnVoid is a control flow 1855// instruction that branches to the exit block. 1856class HReturnVoid : public HTemplateInstruction<0> { 1857 public: 1858 HReturnVoid() : HTemplateInstruction(SideEffects::None()) {} 1859 1860 bool IsControlFlow() const OVERRIDE { return true; } 1861 1862 DECLARE_INSTRUCTION(ReturnVoid); 1863 1864 private: 1865 DISALLOW_COPY_AND_ASSIGN(HReturnVoid); 1866}; 1867 1868// Represents dex's RETURN opcodes. A HReturn is a control flow 1869// instruction that branches to the exit block. 1870class HReturn : public HTemplateInstruction<1> { 1871 public: 1872 explicit HReturn(HInstruction* value) : HTemplateInstruction(SideEffects::None()) { 1873 SetRawInputAt(0, value); 1874 } 1875 1876 bool IsControlFlow() const OVERRIDE { return true; } 1877 1878 DECLARE_INSTRUCTION(Return); 1879 1880 private: 1881 DISALLOW_COPY_AND_ASSIGN(HReturn); 1882}; 1883 1884// The exit instruction is the only instruction of the exit block. 1885// Instructions aborting the method (HThrow and HReturn) must branch to the 1886// exit block. 1887class HExit : public HTemplateInstruction<0> { 1888 public: 1889 HExit() : HTemplateInstruction(SideEffects::None()) {} 1890 1891 bool IsControlFlow() const OVERRIDE { return true; } 1892 1893 DECLARE_INSTRUCTION(Exit); 1894 1895 private: 1896 DISALLOW_COPY_AND_ASSIGN(HExit); 1897}; 1898 1899// Jumps from one block to another. 1900class HGoto : public HTemplateInstruction<0> { 1901 public: 1902 HGoto() : HTemplateInstruction(SideEffects::None()) {} 1903 1904 bool IsControlFlow() const OVERRIDE { return true; } 1905 1906 HBasicBlock* GetSuccessor() const { 1907 return GetBlock()->GetSingleSuccessor(); 1908 } 1909 1910 DECLARE_INSTRUCTION(Goto); 1911 1912 private: 1913 DISALLOW_COPY_AND_ASSIGN(HGoto); 1914}; 1915 1916 1917// Conditional branch. A block ending with an HIf instruction must have 1918// two successors. 1919class HIf : public HTemplateInstruction<1> { 1920 public: 1921 explicit HIf(HInstruction* input) : HTemplateInstruction(SideEffects::None()) { 1922 SetRawInputAt(0, input); 1923 } 1924 1925 bool IsControlFlow() const OVERRIDE { return true; } 1926 1927 HBasicBlock* IfTrueSuccessor() const { 1928 return GetBlock()->GetSuccessors().Get(0); 1929 } 1930 1931 HBasicBlock* IfFalseSuccessor() const { 1932 return GetBlock()->GetSuccessors().Get(1); 1933 } 1934 1935 DECLARE_INSTRUCTION(If); 1936 1937 private: 1938 DISALLOW_COPY_AND_ASSIGN(HIf); 1939}; 1940 1941 1942// Abstract instruction which marks the beginning and/or end of a try block and 1943// links it to the respective exception handlers. Behaves the same as a Goto in 1944// non-exceptional control flow. 1945// Normal-flow successor is stored at index zero, exception handlers under 1946// higher indices in no particular order. 1947class HTryBoundary : public HTemplateInstruction<0> { 1948 public: 1949 HTryBoundary(bool is_entry, bool is_exit) 1950 : HTemplateInstruction(SideEffects::None()), is_entry_(is_entry), is_exit_(is_exit) {} 1951 1952 bool IsControlFlow() const OVERRIDE { return true; } 1953 1954 // Returns the block's non-exceptional successor (index zero). 1955 HBasicBlock* GetNormalFlowSuccessor() const { return GetBlock()->GetSuccessors().Get(0); } 1956 1957 // Returns whether `handler` is among its exception handlers (non-zero index 1958 // successors). 1959 bool HasExceptionHandler(HBasicBlock* handler) const { 1960 DCHECK(handler->IsCatchBlock()); 1961 return GetBlock()->GetSuccessors().Contains(handler, /* start_from */ 1); 1962 } 1963 1964 // Returns whether successor at index `idx` is an exception handler. 1965 bool IsExceptionalSuccessor(size_t idx) const { 1966 DCHECK_LT(idx, GetBlock()->GetSuccessors().Size()); 1967 bool is_handler = (idx != 0); 1968 DCHECK(!is_handler || GetBlock()->GetSuccessors().Get(idx)->IsCatchBlock()); 1969 return is_handler; 1970 } 1971 1972 // If not present already, adds `handler` to its block's list of exception 1973 // handlers. 1974 void AddExceptionHandler(HBasicBlock* handler) { 1975 if (!HasExceptionHandler(handler)) { 1976 GetBlock()->AddSuccessor(handler); 1977 } 1978 } 1979 1980 bool IsTryEntry() const { return is_entry_; } 1981 bool IsTryExit() const { return is_exit_; } 1982 1983 DECLARE_INSTRUCTION(TryBoundary); 1984 1985 private: 1986 // Only for debugging purposes. 1987 bool is_entry_; 1988 bool is_exit_; 1989 1990 // Only set by HGraphBuilder. 1991 void SetIsTryEntry() { is_entry_ = true; } 1992 void SetIsTryExit() { is_exit_ = true; } 1993 1994 friend HGraphBuilder; 1995 1996 DISALLOW_COPY_AND_ASSIGN(HTryBoundary); 1997}; 1998 1999 2000// Deoptimize to interpreter, upon checking a condition. 2001class HDeoptimize : public HTemplateInstruction<1> { 2002 public: 2003 HDeoptimize(HInstruction* cond, uint32_t dex_pc) 2004 : HTemplateInstruction(SideEffects::None()), 2005 dex_pc_(dex_pc) { 2006 SetRawInputAt(0, cond); 2007 } 2008 2009 bool NeedsEnvironment() const OVERRIDE { return true; } 2010 bool CanThrow() const OVERRIDE { return true; } 2011 uint32_t GetDexPc() const OVERRIDE { return dex_pc_; } 2012 2013 DECLARE_INSTRUCTION(Deoptimize); 2014 2015 private: 2016 uint32_t dex_pc_; 2017 2018 DISALLOW_COPY_AND_ASSIGN(HDeoptimize); 2019}; 2020 2021// Represents the ArtMethod that was passed as a first argument to 2022// the method. It is used by instructions that depend on it, like 2023// instructions that work with the dex cache. 2024class HCurrentMethod : public HExpression<0> { 2025 public: 2026 explicit HCurrentMethod(Primitive::Type type) : HExpression(type, SideEffects::None()) {} 2027 2028 DECLARE_INSTRUCTION(CurrentMethod); 2029 2030 private: 2031 DISALLOW_COPY_AND_ASSIGN(HCurrentMethod); 2032}; 2033 2034class HUnaryOperation : public HExpression<1> { 2035 public: 2036 HUnaryOperation(Primitive::Type result_type, HInstruction* input) 2037 : HExpression(result_type, SideEffects::None()) { 2038 SetRawInputAt(0, input); 2039 } 2040 2041 HInstruction* GetInput() const { return InputAt(0); } 2042 Primitive::Type GetResultType() const { return GetType(); } 2043 2044 bool CanBeMoved() const OVERRIDE { return true; } 2045 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 2046 UNUSED(other); 2047 return true; 2048 } 2049 2050 // Try to statically evaluate `operation` and return a HConstant 2051 // containing the result of this evaluation. If `operation` cannot 2052 // be evaluated as a constant, return null. 2053 HConstant* TryStaticEvaluation() const; 2054 2055 // Apply this operation to `x`. 2056 virtual int32_t Evaluate(int32_t x) const = 0; 2057 virtual int64_t Evaluate(int64_t x) const = 0; 2058 2059 DECLARE_INSTRUCTION(UnaryOperation); 2060 2061 private: 2062 DISALLOW_COPY_AND_ASSIGN(HUnaryOperation); 2063}; 2064 2065class HBinaryOperation : public HExpression<2> { 2066 public: 2067 HBinaryOperation(Primitive::Type result_type, 2068 HInstruction* left, 2069 HInstruction* right) : HExpression(result_type, SideEffects::None()) { 2070 SetRawInputAt(0, left); 2071 SetRawInputAt(1, right); 2072 } 2073 2074 HInstruction* GetLeft() const { return InputAt(0); } 2075 HInstruction* GetRight() const { return InputAt(1); } 2076 Primitive::Type GetResultType() const { return GetType(); } 2077 2078 virtual bool IsCommutative() const { return false; } 2079 2080 // Put constant on the right. 2081 // Returns whether order is changed. 2082 bool OrderInputsWithConstantOnTheRight() { 2083 HInstruction* left = InputAt(0); 2084 HInstruction* right = InputAt(1); 2085 if (left->IsConstant() && !right->IsConstant()) { 2086 ReplaceInput(right, 0); 2087 ReplaceInput(left, 1); 2088 return true; 2089 } 2090 return false; 2091 } 2092 2093 // Order inputs by instruction id, but favor constant on the right side. 2094 // This helps GVN for commutative ops. 2095 void OrderInputs() { 2096 DCHECK(IsCommutative()); 2097 HInstruction* left = InputAt(0); 2098 HInstruction* right = InputAt(1); 2099 if (left == right || (!left->IsConstant() && right->IsConstant())) { 2100 return; 2101 } 2102 if (OrderInputsWithConstantOnTheRight()) { 2103 return; 2104 } 2105 // Order according to instruction id. 2106 if (left->GetId() > right->GetId()) { 2107 ReplaceInput(right, 0); 2108 ReplaceInput(left, 1); 2109 } 2110 } 2111 2112 bool CanBeMoved() const OVERRIDE { return true; } 2113 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 2114 UNUSED(other); 2115 return true; 2116 } 2117 2118 // Try to statically evaluate `operation` and return a HConstant 2119 // containing the result of this evaluation. If `operation` cannot 2120 // be evaluated as a constant, return null. 2121 HConstant* TryStaticEvaluation() const; 2122 2123 // Apply this operation to `x` and `y`. 2124 virtual int32_t Evaluate(int32_t x, int32_t y) const = 0; 2125 virtual int64_t Evaluate(int64_t x, int64_t y) const = 0; 2126 2127 // Returns an input that can legally be used as the right input and is 2128 // constant, or null. 2129 HConstant* GetConstantRight() const; 2130 2131 // If `GetConstantRight()` returns one of the input, this returns the other 2132 // one. Otherwise it returns null. 2133 HInstruction* GetLeastConstantLeft() const; 2134 2135 DECLARE_INSTRUCTION(BinaryOperation); 2136 2137 private: 2138 DISALLOW_COPY_AND_ASSIGN(HBinaryOperation); 2139}; 2140 2141class HCondition : public HBinaryOperation { 2142 public: 2143 HCondition(HInstruction* first, HInstruction* second) 2144 : HBinaryOperation(Primitive::kPrimBoolean, first, second), 2145 needs_materialization_(true) {} 2146 2147 bool NeedsMaterialization() const { return needs_materialization_; } 2148 void ClearNeedsMaterialization() { needs_materialization_ = false; } 2149 2150 // For code generation purposes, returns whether this instruction is just before 2151 // `instruction`, and disregard moves in between. 2152 bool IsBeforeWhenDisregardMoves(HInstruction* instruction) const; 2153 2154 DECLARE_INSTRUCTION(Condition); 2155 2156 virtual IfCondition GetCondition() const = 0; 2157 2158 private: 2159 // For register allocation purposes, returns whether this instruction needs to be 2160 // materialized (that is, not just be in the processor flags). 2161 bool needs_materialization_; 2162 2163 DISALLOW_COPY_AND_ASSIGN(HCondition); 2164}; 2165 2166// Instruction to check if two inputs are equal to each other. 2167class HEqual : public HCondition { 2168 public: 2169 HEqual(HInstruction* first, HInstruction* second) 2170 : HCondition(first, second) {} 2171 2172 bool IsCommutative() const OVERRIDE { return true; } 2173 2174 int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE { 2175 return x == y ? 1 : 0; 2176 } 2177 int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE { 2178 return x == y ? 1 : 0; 2179 } 2180 2181 DECLARE_INSTRUCTION(Equal); 2182 2183 IfCondition GetCondition() const OVERRIDE { 2184 return kCondEQ; 2185 } 2186 2187 private: 2188 DISALLOW_COPY_AND_ASSIGN(HEqual); 2189}; 2190 2191class HNotEqual : public HCondition { 2192 public: 2193 HNotEqual(HInstruction* first, HInstruction* second) 2194 : HCondition(first, second) {} 2195 2196 bool IsCommutative() const OVERRIDE { return true; } 2197 2198 int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE { 2199 return x != y ? 1 : 0; 2200 } 2201 int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE { 2202 return x != y ? 1 : 0; 2203 } 2204 2205 DECLARE_INSTRUCTION(NotEqual); 2206 2207 IfCondition GetCondition() const OVERRIDE { 2208 return kCondNE; 2209 } 2210 2211 private: 2212 DISALLOW_COPY_AND_ASSIGN(HNotEqual); 2213}; 2214 2215class HLessThan : public HCondition { 2216 public: 2217 HLessThan(HInstruction* first, HInstruction* second) 2218 : HCondition(first, second) {} 2219 2220 int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE { 2221 return x < y ? 1 : 0; 2222 } 2223 int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE { 2224 return x < y ? 1 : 0; 2225 } 2226 2227 DECLARE_INSTRUCTION(LessThan); 2228 2229 IfCondition GetCondition() const OVERRIDE { 2230 return kCondLT; 2231 } 2232 2233 private: 2234 DISALLOW_COPY_AND_ASSIGN(HLessThan); 2235}; 2236 2237class HLessThanOrEqual : public HCondition { 2238 public: 2239 HLessThanOrEqual(HInstruction* first, HInstruction* second) 2240 : HCondition(first, second) {} 2241 2242 int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE { 2243 return x <= y ? 1 : 0; 2244 } 2245 int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE { 2246 return x <= y ? 1 : 0; 2247 } 2248 2249 DECLARE_INSTRUCTION(LessThanOrEqual); 2250 2251 IfCondition GetCondition() const OVERRIDE { 2252 return kCondLE; 2253 } 2254 2255 private: 2256 DISALLOW_COPY_AND_ASSIGN(HLessThanOrEqual); 2257}; 2258 2259class HGreaterThan : public HCondition { 2260 public: 2261 HGreaterThan(HInstruction* first, HInstruction* second) 2262 : HCondition(first, second) {} 2263 2264 int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE { 2265 return x > y ? 1 : 0; 2266 } 2267 int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE { 2268 return x > y ? 1 : 0; 2269 } 2270 2271 DECLARE_INSTRUCTION(GreaterThan); 2272 2273 IfCondition GetCondition() const OVERRIDE { 2274 return kCondGT; 2275 } 2276 2277 private: 2278 DISALLOW_COPY_AND_ASSIGN(HGreaterThan); 2279}; 2280 2281class HGreaterThanOrEqual : public HCondition { 2282 public: 2283 HGreaterThanOrEqual(HInstruction* first, HInstruction* second) 2284 : HCondition(first, second) {} 2285 2286 int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE { 2287 return x >= y ? 1 : 0; 2288 } 2289 int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE { 2290 return x >= y ? 1 : 0; 2291 } 2292 2293 DECLARE_INSTRUCTION(GreaterThanOrEqual); 2294 2295 IfCondition GetCondition() const OVERRIDE { 2296 return kCondGE; 2297 } 2298 2299 private: 2300 DISALLOW_COPY_AND_ASSIGN(HGreaterThanOrEqual); 2301}; 2302 2303 2304// Instruction to check how two inputs compare to each other. 2305// Result is 0 if input0 == input1, 1 if input0 > input1, or -1 if input0 < input1. 2306class HCompare : public HBinaryOperation { 2307 public: 2308 // The bias applies for floating point operations and indicates how NaN 2309 // comparisons are treated: 2310 enum Bias { 2311 kNoBias, // bias is not applicable (i.e. for long operation) 2312 kGtBias, // return 1 for NaN comparisons 2313 kLtBias, // return -1 for NaN comparisons 2314 }; 2315 2316 HCompare(Primitive::Type type, 2317 HInstruction* first, 2318 HInstruction* second, 2319 Bias bias, 2320 uint32_t dex_pc) 2321 : HBinaryOperation(Primitive::kPrimInt, first, second), bias_(bias), dex_pc_(dex_pc) { 2322 DCHECK_EQ(type, first->GetType()); 2323 DCHECK_EQ(type, second->GetType()); 2324 } 2325 2326 int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE { 2327 return 2328 x == y ? 0 : 2329 x > y ? 1 : 2330 -1; 2331 } 2332 2333 int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE { 2334 return 2335 x == y ? 0 : 2336 x > y ? 1 : 2337 -1; 2338 } 2339 2340 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 2341 return bias_ == other->AsCompare()->bias_; 2342 } 2343 2344 bool IsGtBias() { return bias_ == kGtBias; } 2345 2346 uint32_t GetDexPc() const { return dex_pc_; } 2347 2348 DECLARE_INSTRUCTION(Compare); 2349 2350 private: 2351 const Bias bias_; 2352 const uint32_t dex_pc_; 2353 2354 DISALLOW_COPY_AND_ASSIGN(HCompare); 2355}; 2356 2357// A local in the graph. Corresponds to a Dex register. 2358class HLocal : public HTemplateInstruction<0> { 2359 public: 2360 explicit HLocal(uint16_t reg_number) 2361 : HTemplateInstruction(SideEffects::None()), reg_number_(reg_number) {} 2362 2363 DECLARE_INSTRUCTION(Local); 2364 2365 uint16_t GetRegNumber() const { return reg_number_; } 2366 2367 private: 2368 // The Dex register number. 2369 const uint16_t reg_number_; 2370 2371 DISALLOW_COPY_AND_ASSIGN(HLocal); 2372}; 2373 2374// Load a given local. The local is an input of this instruction. 2375class HLoadLocal : public HExpression<1> { 2376 public: 2377 HLoadLocal(HLocal* local, Primitive::Type type) 2378 : HExpression(type, SideEffects::None()) { 2379 SetRawInputAt(0, local); 2380 } 2381 2382 HLocal* GetLocal() const { return reinterpret_cast<HLocal*>(InputAt(0)); } 2383 2384 DECLARE_INSTRUCTION(LoadLocal); 2385 2386 private: 2387 DISALLOW_COPY_AND_ASSIGN(HLoadLocal); 2388}; 2389 2390// Store a value in a given local. This instruction has two inputs: the value 2391// and the local. 2392class HStoreLocal : public HTemplateInstruction<2> { 2393 public: 2394 HStoreLocal(HLocal* local, HInstruction* value) : HTemplateInstruction(SideEffects::None()) { 2395 SetRawInputAt(0, local); 2396 SetRawInputAt(1, value); 2397 } 2398 2399 HLocal* GetLocal() const { return reinterpret_cast<HLocal*>(InputAt(0)); } 2400 2401 DECLARE_INSTRUCTION(StoreLocal); 2402 2403 private: 2404 DISALLOW_COPY_AND_ASSIGN(HStoreLocal); 2405}; 2406 2407class HConstant : public HExpression<0> { 2408 public: 2409 explicit HConstant(Primitive::Type type) : HExpression(type, SideEffects::None()) {} 2410 2411 bool CanBeMoved() const OVERRIDE { return true; } 2412 2413 virtual bool IsMinusOne() const { return false; } 2414 virtual bool IsZero() const { return false; } 2415 virtual bool IsOne() const { return false; } 2416 2417 DECLARE_INSTRUCTION(Constant); 2418 2419 private: 2420 DISALLOW_COPY_AND_ASSIGN(HConstant); 2421}; 2422 2423class HFloatConstant : public HConstant { 2424 public: 2425 float GetValue() const { return value_; } 2426 2427 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 2428 return bit_cast<uint32_t, float>(other->AsFloatConstant()->value_) == 2429 bit_cast<uint32_t, float>(value_); 2430 } 2431 2432 size_t ComputeHashCode() const OVERRIDE { return static_cast<size_t>(GetValue()); } 2433 2434 bool IsMinusOne() const OVERRIDE { 2435 return bit_cast<uint32_t, float>(value_) == bit_cast<uint32_t, float>((-1.0f)); 2436 } 2437 bool IsZero() const OVERRIDE { 2438 return value_ == 0.0f; 2439 } 2440 bool IsOne() const OVERRIDE { 2441 return bit_cast<uint32_t, float>(value_) == bit_cast<uint32_t, float>(1.0f); 2442 } 2443 bool IsNaN() const { 2444 return std::isnan(value_); 2445 } 2446 2447 DECLARE_INSTRUCTION(FloatConstant); 2448 2449 private: 2450 explicit HFloatConstant(float value) : HConstant(Primitive::kPrimFloat), value_(value) {} 2451 explicit HFloatConstant(int32_t value) 2452 : HConstant(Primitive::kPrimFloat), value_(bit_cast<float, int32_t>(value)) {} 2453 2454 const float value_; 2455 2456 // Only the SsaBuilder and HGraph can create floating-point constants. 2457 friend class SsaBuilder; 2458 friend class HGraph; 2459 DISALLOW_COPY_AND_ASSIGN(HFloatConstant); 2460}; 2461 2462class HDoubleConstant : public HConstant { 2463 public: 2464 double GetValue() const { return value_; } 2465 2466 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 2467 return bit_cast<uint64_t, double>(other->AsDoubleConstant()->value_) == 2468 bit_cast<uint64_t, double>(value_); 2469 } 2470 2471 size_t ComputeHashCode() const OVERRIDE { return static_cast<size_t>(GetValue()); } 2472 2473 bool IsMinusOne() const OVERRIDE { 2474 return bit_cast<uint64_t, double>(value_) == bit_cast<uint64_t, double>((-1.0)); 2475 } 2476 bool IsZero() const OVERRIDE { 2477 return value_ == 0.0; 2478 } 2479 bool IsOne() const OVERRIDE { 2480 return bit_cast<uint64_t, double>(value_) == bit_cast<uint64_t, double>(1.0); 2481 } 2482 bool IsNaN() const { 2483 return std::isnan(value_); 2484 } 2485 2486 DECLARE_INSTRUCTION(DoubleConstant); 2487 2488 private: 2489 explicit HDoubleConstant(double value) : HConstant(Primitive::kPrimDouble), value_(value) {} 2490 explicit HDoubleConstant(int64_t value) 2491 : HConstant(Primitive::kPrimDouble), value_(bit_cast<double, int64_t>(value)) {} 2492 2493 const double value_; 2494 2495 // Only the SsaBuilder and HGraph can create floating-point constants. 2496 friend class SsaBuilder; 2497 friend class HGraph; 2498 DISALLOW_COPY_AND_ASSIGN(HDoubleConstant); 2499}; 2500 2501class HNullConstant : public HConstant { 2502 public: 2503 bool InstructionDataEquals(HInstruction* other ATTRIBUTE_UNUSED) const OVERRIDE { 2504 return true; 2505 } 2506 2507 size_t ComputeHashCode() const OVERRIDE { return 0; } 2508 2509 DECLARE_INSTRUCTION(NullConstant); 2510 2511 private: 2512 HNullConstant() : HConstant(Primitive::kPrimNot) {} 2513 2514 friend class HGraph; 2515 DISALLOW_COPY_AND_ASSIGN(HNullConstant); 2516}; 2517 2518// Constants of the type int. Those can be from Dex instructions, or 2519// synthesized (for example with the if-eqz instruction). 2520class HIntConstant : public HConstant { 2521 public: 2522 int32_t GetValue() const { return value_; } 2523 2524 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 2525 return other->AsIntConstant()->value_ == value_; 2526 } 2527 2528 size_t ComputeHashCode() const OVERRIDE { return GetValue(); } 2529 2530 bool IsMinusOne() const OVERRIDE { return GetValue() == -1; } 2531 bool IsZero() const OVERRIDE { return GetValue() == 0; } 2532 bool IsOne() const OVERRIDE { return GetValue() == 1; } 2533 2534 DECLARE_INSTRUCTION(IntConstant); 2535 2536 private: 2537 explicit HIntConstant(int32_t value) : HConstant(Primitive::kPrimInt), value_(value) {} 2538 2539 const int32_t value_; 2540 2541 friend class HGraph; 2542 ART_FRIEND_TEST(GraphTest, InsertInstructionBefore); 2543 ART_FRIEND_TYPED_TEST(ParallelMoveTest, ConstantLast); 2544 DISALLOW_COPY_AND_ASSIGN(HIntConstant); 2545}; 2546 2547class HLongConstant : public HConstant { 2548 public: 2549 int64_t GetValue() const { return value_; } 2550 2551 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 2552 return other->AsLongConstant()->value_ == value_; 2553 } 2554 2555 size_t ComputeHashCode() const OVERRIDE { return static_cast<size_t>(GetValue()); } 2556 2557 bool IsMinusOne() const OVERRIDE { return GetValue() == -1; } 2558 bool IsZero() const OVERRIDE { return GetValue() == 0; } 2559 bool IsOne() const OVERRIDE { return GetValue() == 1; } 2560 2561 DECLARE_INSTRUCTION(LongConstant); 2562 2563 private: 2564 explicit HLongConstant(int64_t value) : HConstant(Primitive::kPrimLong), value_(value) {} 2565 2566 const int64_t value_; 2567 2568 friend class HGraph; 2569 DISALLOW_COPY_AND_ASSIGN(HLongConstant); 2570}; 2571 2572enum class Intrinsics { 2573#define OPTIMIZING_INTRINSICS(Name, IsStatic) k ## Name, 2574#include "intrinsics_list.h" 2575 kNone, 2576 INTRINSICS_LIST(OPTIMIZING_INTRINSICS) 2577#undef INTRINSICS_LIST 2578#undef OPTIMIZING_INTRINSICS 2579}; 2580std::ostream& operator<<(std::ostream& os, const Intrinsics& intrinsic); 2581 2582class HInvoke : public HInstruction { 2583 public: 2584 size_t InputCount() const OVERRIDE { return inputs_.Size(); } 2585 2586 // Runtime needs to walk the stack, so Dex -> Dex calls need to 2587 // know their environment. 2588 bool NeedsEnvironment() const OVERRIDE { return true; } 2589 2590 void SetArgumentAt(size_t index, HInstruction* argument) { 2591 SetRawInputAt(index, argument); 2592 } 2593 2594 // Return the number of arguments. This number can be lower than 2595 // the number of inputs returned by InputCount(), as some invoke 2596 // instructions (e.g. HInvokeStaticOrDirect) can have non-argument 2597 // inputs at the end of their list of inputs. 2598 uint32_t GetNumberOfArguments() const { return number_of_arguments_; } 2599 2600 Primitive::Type GetType() const OVERRIDE { return return_type_; } 2601 2602 uint32_t GetDexPc() const OVERRIDE { return dex_pc_; } 2603 2604 uint32_t GetDexMethodIndex() const { return dex_method_index_; } 2605 const DexFile& GetDexFile() const { return GetEnvironment()->GetDexFile(); } 2606 2607 InvokeType GetOriginalInvokeType() const { return original_invoke_type_; } 2608 2609 Intrinsics GetIntrinsic() const { 2610 return intrinsic_; 2611 } 2612 2613 void SetIntrinsic(Intrinsics intrinsic) { 2614 intrinsic_ = intrinsic; 2615 } 2616 2617 bool IsFromInlinedInvoke() const { 2618 return GetEnvironment()->GetParent() != nullptr; 2619 } 2620 2621 bool CanThrow() const OVERRIDE { return true; } 2622 2623 DECLARE_INSTRUCTION(Invoke); 2624 2625 protected: 2626 HInvoke(ArenaAllocator* arena, 2627 uint32_t number_of_arguments, 2628 uint32_t number_of_other_inputs, 2629 Primitive::Type return_type, 2630 uint32_t dex_pc, 2631 uint32_t dex_method_index, 2632 InvokeType original_invoke_type) 2633 : HInstruction(SideEffects::All()), 2634 number_of_arguments_(number_of_arguments), 2635 inputs_(arena, number_of_arguments), 2636 return_type_(return_type), 2637 dex_pc_(dex_pc), 2638 dex_method_index_(dex_method_index), 2639 original_invoke_type_(original_invoke_type), 2640 intrinsic_(Intrinsics::kNone) { 2641 uint32_t number_of_inputs = number_of_arguments + number_of_other_inputs; 2642 inputs_.SetSize(number_of_inputs); 2643 } 2644 2645 const HUserRecord<HInstruction*> InputRecordAt(size_t i) const OVERRIDE { return inputs_.Get(i); } 2646 void SetRawInputRecordAt(size_t index, const HUserRecord<HInstruction*>& input) OVERRIDE { 2647 inputs_.Put(index, input); 2648 } 2649 2650 uint32_t number_of_arguments_; 2651 GrowableArray<HUserRecord<HInstruction*> > inputs_; 2652 const Primitive::Type return_type_; 2653 const uint32_t dex_pc_; 2654 const uint32_t dex_method_index_; 2655 const InvokeType original_invoke_type_; 2656 Intrinsics intrinsic_; 2657 2658 private: 2659 DISALLOW_COPY_AND_ASSIGN(HInvoke); 2660}; 2661 2662class HInvokeStaticOrDirect : public HInvoke { 2663 public: 2664 // Requirements of this method call regarding the class 2665 // initialization (clinit) check of its declaring class. 2666 enum class ClinitCheckRequirement { 2667 kNone, // Class already initialized. 2668 kExplicit, // Static call having explicit clinit check as last input. 2669 kImplicit, // Static call implicitly requiring a clinit check. 2670 }; 2671 2672 HInvokeStaticOrDirect(ArenaAllocator* arena, 2673 uint32_t number_of_arguments, 2674 Primitive::Type return_type, 2675 uint32_t dex_pc, 2676 uint32_t dex_method_index, 2677 bool is_recursive, 2678 int32_t string_init_offset, 2679 InvokeType original_invoke_type, 2680 InvokeType invoke_type, 2681 ClinitCheckRequirement clinit_check_requirement) 2682 : HInvoke(arena, 2683 number_of_arguments, 2684 // There is one extra argument for the HCurrentMethod node, and 2685 // potentially one other if the clinit check is explicit. 2686 clinit_check_requirement == ClinitCheckRequirement::kExplicit ? 2u : 1u, 2687 return_type, 2688 dex_pc, 2689 dex_method_index, 2690 original_invoke_type), 2691 invoke_type_(invoke_type), 2692 is_recursive_(is_recursive), 2693 clinit_check_requirement_(clinit_check_requirement), 2694 string_init_offset_(string_init_offset) {} 2695 2696 bool CanDoImplicitNullCheckOn(HInstruction* obj) const OVERRIDE { 2697 UNUSED(obj); 2698 // We access the method via the dex cache so we can't do an implicit null check. 2699 // TODO: for intrinsics we can generate implicit null checks. 2700 return false; 2701 } 2702 2703 InvokeType GetInvokeType() const { return invoke_type_; } 2704 bool IsRecursive() const { return is_recursive_; } 2705 bool NeedsDexCache() const OVERRIDE { return !IsRecursive(); } 2706 bool IsStringInit() const { return string_init_offset_ != 0; } 2707 int32_t GetStringInitOffset() const { return string_init_offset_; } 2708 uint32_t GetCurrentMethodInputIndex() const { return GetNumberOfArguments(); } 2709 2710 // Is this instruction a call to a static method? 2711 bool IsStatic() const { 2712 return GetInvokeType() == kStatic; 2713 } 2714 2715 // Remove the art::HLoadClass instruction set as last input by 2716 // art::PrepareForRegisterAllocation::VisitClinitCheck in lieu of 2717 // the initial art::HClinitCheck instruction (only relevant for 2718 // static calls with explicit clinit check). 2719 void RemoveLoadClassAsLastInput() { 2720 DCHECK(IsStaticWithExplicitClinitCheck()); 2721 size_t last_input_index = InputCount() - 1; 2722 HInstruction* last_input = InputAt(last_input_index); 2723 DCHECK(last_input != nullptr); 2724 DCHECK(last_input->IsLoadClass()) << last_input->DebugName(); 2725 RemoveAsUserOfInput(last_input_index); 2726 inputs_.DeleteAt(last_input_index); 2727 clinit_check_requirement_ = ClinitCheckRequirement::kImplicit; 2728 DCHECK(IsStaticWithImplicitClinitCheck()); 2729 } 2730 2731 // Is this a call to a static method whose declaring class has an 2732 // explicit intialization check in the graph? 2733 bool IsStaticWithExplicitClinitCheck() const { 2734 return IsStatic() && (clinit_check_requirement_ == ClinitCheckRequirement::kExplicit); 2735 } 2736 2737 // Is this a call to a static method whose declaring class has an 2738 // implicit intialization check requirement? 2739 bool IsStaticWithImplicitClinitCheck() const { 2740 return IsStatic() && (clinit_check_requirement_ == ClinitCheckRequirement::kImplicit); 2741 } 2742 2743 DECLARE_INSTRUCTION(InvokeStaticOrDirect); 2744 2745 protected: 2746 const HUserRecord<HInstruction*> InputRecordAt(size_t i) const OVERRIDE { 2747 const HUserRecord<HInstruction*> input_record = HInvoke::InputRecordAt(i); 2748 if (kIsDebugBuild && IsStaticWithExplicitClinitCheck() && (i == InputCount() - 1)) { 2749 HInstruction* input = input_record.GetInstruction(); 2750 // `input` is the last input of a static invoke marked as having 2751 // an explicit clinit check. It must either be: 2752 // - an art::HClinitCheck instruction, set by art::HGraphBuilder; or 2753 // - an art::HLoadClass instruction, set by art::PrepareForRegisterAllocation. 2754 DCHECK(input != nullptr); 2755 DCHECK(input->IsClinitCheck() || input->IsLoadClass()) << input->DebugName(); 2756 } 2757 return input_record; 2758 } 2759 2760 private: 2761 const InvokeType invoke_type_; 2762 const bool is_recursive_; 2763 ClinitCheckRequirement clinit_check_requirement_; 2764 // Thread entrypoint offset for string init method if this is a string init invoke. 2765 // Note that there are multiple string init methods, each having its own offset. 2766 int32_t string_init_offset_; 2767 2768 DISALLOW_COPY_AND_ASSIGN(HInvokeStaticOrDirect); 2769}; 2770 2771class HInvokeVirtual : public HInvoke { 2772 public: 2773 HInvokeVirtual(ArenaAllocator* arena, 2774 uint32_t number_of_arguments, 2775 Primitive::Type return_type, 2776 uint32_t dex_pc, 2777 uint32_t dex_method_index, 2778 uint32_t vtable_index) 2779 : HInvoke(arena, number_of_arguments, 0u, return_type, dex_pc, dex_method_index, kVirtual), 2780 vtable_index_(vtable_index) {} 2781 2782 bool CanDoImplicitNullCheckOn(HInstruction* obj) const OVERRIDE { 2783 // TODO: Add implicit null checks in intrinsics. 2784 return (obj == InputAt(0)) && !GetLocations()->Intrinsified(); 2785 } 2786 2787 uint32_t GetVTableIndex() const { return vtable_index_; } 2788 2789 DECLARE_INSTRUCTION(InvokeVirtual); 2790 2791 private: 2792 const uint32_t vtable_index_; 2793 2794 DISALLOW_COPY_AND_ASSIGN(HInvokeVirtual); 2795}; 2796 2797class HInvokeInterface : public HInvoke { 2798 public: 2799 HInvokeInterface(ArenaAllocator* arena, 2800 uint32_t number_of_arguments, 2801 Primitive::Type return_type, 2802 uint32_t dex_pc, 2803 uint32_t dex_method_index, 2804 uint32_t imt_index) 2805 : HInvoke(arena, number_of_arguments, 0u, return_type, dex_pc, dex_method_index, kInterface), 2806 imt_index_(imt_index) {} 2807 2808 bool CanDoImplicitNullCheckOn(HInstruction* obj) const OVERRIDE { 2809 // TODO: Add implicit null checks in intrinsics. 2810 return (obj == InputAt(0)) && !GetLocations()->Intrinsified(); 2811 } 2812 2813 uint32_t GetImtIndex() const { return imt_index_; } 2814 uint32_t GetDexMethodIndex() const { return dex_method_index_; } 2815 2816 DECLARE_INSTRUCTION(InvokeInterface); 2817 2818 private: 2819 const uint32_t imt_index_; 2820 2821 DISALLOW_COPY_AND_ASSIGN(HInvokeInterface); 2822}; 2823 2824class HNewInstance : public HExpression<1> { 2825 public: 2826 HNewInstance(HCurrentMethod* current_method, 2827 uint32_t dex_pc, 2828 uint16_t type_index, 2829 const DexFile& dex_file, 2830 QuickEntrypointEnum entrypoint) 2831 : HExpression(Primitive::kPrimNot, SideEffects::None()), 2832 dex_pc_(dex_pc), 2833 type_index_(type_index), 2834 dex_file_(dex_file), 2835 entrypoint_(entrypoint) { 2836 SetRawInputAt(0, current_method); 2837 } 2838 2839 uint32_t GetDexPc() const OVERRIDE { return dex_pc_; } 2840 uint16_t GetTypeIndex() const { return type_index_; } 2841 const DexFile& GetDexFile() const { return dex_file_; } 2842 2843 // Calls runtime so needs an environment. 2844 bool NeedsEnvironment() const OVERRIDE { return true; } 2845 // It may throw when called on: 2846 // - interfaces 2847 // - abstract/innaccessible/unknown classes 2848 // TODO: optimize when possible. 2849 bool CanThrow() const OVERRIDE { return true; } 2850 2851 bool CanBeNull() const OVERRIDE { return false; } 2852 2853 QuickEntrypointEnum GetEntrypoint() const { return entrypoint_; } 2854 2855 DECLARE_INSTRUCTION(NewInstance); 2856 2857 private: 2858 const uint32_t dex_pc_; 2859 const uint16_t type_index_; 2860 const DexFile& dex_file_; 2861 const QuickEntrypointEnum entrypoint_; 2862 2863 DISALLOW_COPY_AND_ASSIGN(HNewInstance); 2864}; 2865 2866class HNeg : public HUnaryOperation { 2867 public: 2868 explicit HNeg(Primitive::Type result_type, HInstruction* input) 2869 : HUnaryOperation(result_type, input) {} 2870 2871 int32_t Evaluate(int32_t x) const OVERRIDE { return -x; } 2872 int64_t Evaluate(int64_t x) const OVERRIDE { return -x; } 2873 2874 DECLARE_INSTRUCTION(Neg); 2875 2876 private: 2877 DISALLOW_COPY_AND_ASSIGN(HNeg); 2878}; 2879 2880class HNewArray : public HExpression<2> { 2881 public: 2882 HNewArray(HInstruction* length, 2883 HCurrentMethod* current_method, 2884 uint32_t dex_pc, 2885 uint16_t type_index, 2886 const DexFile& dex_file, 2887 QuickEntrypointEnum entrypoint) 2888 : HExpression(Primitive::kPrimNot, SideEffects::None()), 2889 dex_pc_(dex_pc), 2890 type_index_(type_index), 2891 dex_file_(dex_file), 2892 entrypoint_(entrypoint) { 2893 SetRawInputAt(0, length); 2894 SetRawInputAt(1, current_method); 2895 } 2896 2897 uint32_t GetDexPc() const OVERRIDE { return dex_pc_; } 2898 uint16_t GetTypeIndex() const { return type_index_; } 2899 const DexFile& GetDexFile() const { return dex_file_; } 2900 2901 // Calls runtime so needs an environment. 2902 bool NeedsEnvironment() const OVERRIDE { return true; } 2903 2904 // May throw NegativeArraySizeException, OutOfMemoryError, etc. 2905 bool CanThrow() const OVERRIDE { return true; } 2906 2907 bool CanBeNull() const OVERRIDE { return false; } 2908 2909 QuickEntrypointEnum GetEntrypoint() const { return entrypoint_; } 2910 2911 DECLARE_INSTRUCTION(NewArray); 2912 2913 private: 2914 const uint32_t dex_pc_; 2915 const uint16_t type_index_; 2916 const DexFile& dex_file_; 2917 const QuickEntrypointEnum entrypoint_; 2918 2919 DISALLOW_COPY_AND_ASSIGN(HNewArray); 2920}; 2921 2922class HAdd : public HBinaryOperation { 2923 public: 2924 HAdd(Primitive::Type result_type, HInstruction* left, HInstruction* right) 2925 : HBinaryOperation(result_type, left, right) {} 2926 2927 bool IsCommutative() const OVERRIDE { return true; } 2928 2929 int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE { 2930 return x + y; 2931 } 2932 int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE { 2933 return x + y; 2934 } 2935 2936 DECLARE_INSTRUCTION(Add); 2937 2938 private: 2939 DISALLOW_COPY_AND_ASSIGN(HAdd); 2940}; 2941 2942class HSub : public HBinaryOperation { 2943 public: 2944 HSub(Primitive::Type result_type, HInstruction* left, HInstruction* right) 2945 : HBinaryOperation(result_type, left, right) {} 2946 2947 int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE { 2948 return x - y; 2949 } 2950 int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE { 2951 return x - y; 2952 } 2953 2954 DECLARE_INSTRUCTION(Sub); 2955 2956 private: 2957 DISALLOW_COPY_AND_ASSIGN(HSub); 2958}; 2959 2960class HMul : public HBinaryOperation { 2961 public: 2962 HMul(Primitive::Type result_type, HInstruction* left, HInstruction* right) 2963 : HBinaryOperation(result_type, left, right) {} 2964 2965 bool IsCommutative() const OVERRIDE { return true; } 2966 2967 int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE { return x * y; } 2968 int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE { return x * y; } 2969 2970 DECLARE_INSTRUCTION(Mul); 2971 2972 private: 2973 DISALLOW_COPY_AND_ASSIGN(HMul); 2974}; 2975 2976class HDiv : public HBinaryOperation { 2977 public: 2978 HDiv(Primitive::Type result_type, HInstruction* left, HInstruction* right, uint32_t dex_pc) 2979 : HBinaryOperation(result_type, left, right), dex_pc_(dex_pc) {} 2980 2981 int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE { 2982 // Our graph structure ensures we never have 0 for `y` during constant folding. 2983 DCHECK_NE(y, 0); 2984 // Special case -1 to avoid getting a SIGFPE on x86(_64). 2985 return (y == -1) ? -x : x / y; 2986 } 2987 2988 int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE { 2989 DCHECK_NE(y, 0); 2990 // Special case -1 to avoid getting a SIGFPE on x86(_64). 2991 return (y == -1) ? -x : x / y; 2992 } 2993 2994 uint32_t GetDexPc() const OVERRIDE { return dex_pc_; } 2995 2996 DECLARE_INSTRUCTION(Div); 2997 2998 private: 2999 const uint32_t dex_pc_; 3000 3001 DISALLOW_COPY_AND_ASSIGN(HDiv); 3002}; 3003 3004class HRem : public HBinaryOperation { 3005 public: 3006 HRem(Primitive::Type result_type, HInstruction* left, HInstruction* right, uint32_t dex_pc) 3007 : HBinaryOperation(result_type, left, right), dex_pc_(dex_pc) {} 3008 3009 int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE { 3010 DCHECK_NE(y, 0); 3011 // Special case -1 to avoid getting a SIGFPE on x86(_64). 3012 return (y == -1) ? 0 : x % y; 3013 } 3014 3015 int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE { 3016 DCHECK_NE(y, 0); 3017 // Special case -1 to avoid getting a SIGFPE on x86(_64). 3018 return (y == -1) ? 0 : x % y; 3019 } 3020 3021 uint32_t GetDexPc() const OVERRIDE { return dex_pc_; } 3022 3023 DECLARE_INSTRUCTION(Rem); 3024 3025 private: 3026 const uint32_t dex_pc_; 3027 3028 DISALLOW_COPY_AND_ASSIGN(HRem); 3029}; 3030 3031class HDivZeroCheck : public HExpression<1> { 3032 public: 3033 HDivZeroCheck(HInstruction* value, uint32_t dex_pc) 3034 : HExpression(value->GetType(), SideEffects::None()), dex_pc_(dex_pc) { 3035 SetRawInputAt(0, value); 3036 } 3037 3038 bool CanBeMoved() const OVERRIDE { return true; } 3039 3040 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 3041 UNUSED(other); 3042 return true; 3043 } 3044 3045 bool NeedsEnvironment() const OVERRIDE { return true; } 3046 bool CanThrow() const OVERRIDE { return true; } 3047 3048 uint32_t GetDexPc() const OVERRIDE { return dex_pc_; } 3049 3050 DECLARE_INSTRUCTION(DivZeroCheck); 3051 3052 private: 3053 const uint32_t dex_pc_; 3054 3055 DISALLOW_COPY_AND_ASSIGN(HDivZeroCheck); 3056}; 3057 3058class HShl : public HBinaryOperation { 3059 public: 3060 HShl(Primitive::Type result_type, HInstruction* left, HInstruction* right) 3061 : HBinaryOperation(result_type, left, right) {} 3062 3063 int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE { return x << (y & kMaxIntShiftValue); } 3064 int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE { return x << (y & kMaxLongShiftValue); } 3065 3066 DECLARE_INSTRUCTION(Shl); 3067 3068 private: 3069 DISALLOW_COPY_AND_ASSIGN(HShl); 3070}; 3071 3072class HShr : public HBinaryOperation { 3073 public: 3074 HShr(Primitive::Type result_type, HInstruction* left, HInstruction* right) 3075 : HBinaryOperation(result_type, left, right) {} 3076 3077 int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE { return x >> (y & kMaxIntShiftValue); } 3078 int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE { return x >> (y & kMaxLongShiftValue); } 3079 3080 DECLARE_INSTRUCTION(Shr); 3081 3082 private: 3083 DISALLOW_COPY_AND_ASSIGN(HShr); 3084}; 3085 3086class HUShr : public HBinaryOperation { 3087 public: 3088 HUShr(Primitive::Type result_type, HInstruction* left, HInstruction* right) 3089 : HBinaryOperation(result_type, left, right) {} 3090 3091 int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE { 3092 uint32_t ux = static_cast<uint32_t>(x); 3093 uint32_t uy = static_cast<uint32_t>(y) & kMaxIntShiftValue; 3094 return static_cast<int32_t>(ux >> uy); 3095 } 3096 3097 int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE { 3098 uint64_t ux = static_cast<uint64_t>(x); 3099 uint64_t uy = static_cast<uint64_t>(y) & kMaxLongShiftValue; 3100 return static_cast<int64_t>(ux >> uy); 3101 } 3102 3103 DECLARE_INSTRUCTION(UShr); 3104 3105 private: 3106 DISALLOW_COPY_AND_ASSIGN(HUShr); 3107}; 3108 3109class HAnd : public HBinaryOperation { 3110 public: 3111 HAnd(Primitive::Type result_type, HInstruction* left, HInstruction* right) 3112 : HBinaryOperation(result_type, left, right) {} 3113 3114 bool IsCommutative() const OVERRIDE { return true; } 3115 3116 int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE { return x & y; } 3117 int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE { return x & y; } 3118 3119 DECLARE_INSTRUCTION(And); 3120 3121 private: 3122 DISALLOW_COPY_AND_ASSIGN(HAnd); 3123}; 3124 3125class HOr : public HBinaryOperation { 3126 public: 3127 HOr(Primitive::Type result_type, HInstruction* left, HInstruction* right) 3128 : HBinaryOperation(result_type, left, right) {} 3129 3130 bool IsCommutative() const OVERRIDE { return true; } 3131 3132 int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE { return x | y; } 3133 int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE { return x | y; } 3134 3135 DECLARE_INSTRUCTION(Or); 3136 3137 private: 3138 DISALLOW_COPY_AND_ASSIGN(HOr); 3139}; 3140 3141class HXor : public HBinaryOperation { 3142 public: 3143 HXor(Primitive::Type result_type, HInstruction* left, HInstruction* right) 3144 : HBinaryOperation(result_type, left, right) {} 3145 3146 bool IsCommutative() const OVERRIDE { return true; } 3147 3148 int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE { return x ^ y; } 3149 int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE { return x ^ y; } 3150 3151 DECLARE_INSTRUCTION(Xor); 3152 3153 private: 3154 DISALLOW_COPY_AND_ASSIGN(HXor); 3155}; 3156 3157// The value of a parameter in this method. Its location depends on 3158// the calling convention. 3159class HParameterValue : public HExpression<0> { 3160 public: 3161 HParameterValue(uint8_t index, Primitive::Type parameter_type, bool is_this = false) 3162 : HExpression(parameter_type, SideEffects::None()), index_(index), is_this_(is_this) {} 3163 3164 uint8_t GetIndex() const { return index_; } 3165 3166 bool CanBeNull() const OVERRIDE { return !is_this_; } 3167 3168 bool IsThis() const { return is_this_; } 3169 3170 DECLARE_INSTRUCTION(ParameterValue); 3171 3172 private: 3173 // The index of this parameter in the parameters list. Must be less 3174 // than HGraph::number_of_in_vregs_. 3175 const uint8_t index_; 3176 3177 // Whether or not the parameter value corresponds to 'this' argument. 3178 const bool is_this_; 3179 3180 DISALLOW_COPY_AND_ASSIGN(HParameterValue); 3181}; 3182 3183class HNot : public HUnaryOperation { 3184 public: 3185 explicit HNot(Primitive::Type result_type, HInstruction* input) 3186 : HUnaryOperation(result_type, input) {} 3187 3188 bool CanBeMoved() const OVERRIDE { return true; } 3189 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 3190 UNUSED(other); 3191 return true; 3192 } 3193 3194 int32_t Evaluate(int32_t x) const OVERRIDE { return ~x; } 3195 int64_t Evaluate(int64_t x) const OVERRIDE { return ~x; } 3196 3197 DECLARE_INSTRUCTION(Not); 3198 3199 private: 3200 DISALLOW_COPY_AND_ASSIGN(HNot); 3201}; 3202 3203class HBooleanNot : public HUnaryOperation { 3204 public: 3205 explicit HBooleanNot(HInstruction* input) 3206 : HUnaryOperation(Primitive::Type::kPrimBoolean, input) {} 3207 3208 bool CanBeMoved() const OVERRIDE { return true; } 3209 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 3210 UNUSED(other); 3211 return true; 3212 } 3213 3214 int32_t Evaluate(int32_t x) const OVERRIDE { 3215 DCHECK(IsUint<1>(x)); 3216 return !x; 3217 } 3218 3219 int64_t Evaluate(int64_t x ATTRIBUTE_UNUSED) const OVERRIDE { 3220 LOG(FATAL) << DebugName() << " cannot be used with 64-bit values"; 3221 UNREACHABLE(); 3222 } 3223 3224 DECLARE_INSTRUCTION(BooleanNot); 3225 3226 private: 3227 DISALLOW_COPY_AND_ASSIGN(HBooleanNot); 3228}; 3229 3230class HTypeConversion : public HExpression<1> { 3231 public: 3232 // Instantiate a type conversion of `input` to `result_type`. 3233 HTypeConversion(Primitive::Type result_type, HInstruction* input, uint32_t dex_pc) 3234 : HExpression(result_type, SideEffects::None()), dex_pc_(dex_pc) { 3235 SetRawInputAt(0, input); 3236 DCHECK_NE(input->GetType(), result_type); 3237 } 3238 3239 HInstruction* GetInput() const { return InputAt(0); } 3240 Primitive::Type GetInputType() const { return GetInput()->GetType(); } 3241 Primitive::Type GetResultType() const { return GetType(); } 3242 3243 // Required by the x86 and ARM code generators when producing calls 3244 // to the runtime. 3245 uint32_t GetDexPc() const OVERRIDE { return dex_pc_; } 3246 3247 bool CanBeMoved() const OVERRIDE { return true; } 3248 bool InstructionDataEquals(HInstruction* other ATTRIBUTE_UNUSED) const OVERRIDE { return true; } 3249 3250 // Try to statically evaluate the conversion and return a HConstant 3251 // containing the result. If the input cannot be converted, return nullptr. 3252 HConstant* TryStaticEvaluation() const; 3253 3254 DECLARE_INSTRUCTION(TypeConversion); 3255 3256 private: 3257 const uint32_t dex_pc_; 3258 3259 DISALLOW_COPY_AND_ASSIGN(HTypeConversion); 3260}; 3261 3262static constexpr uint32_t kNoRegNumber = -1; 3263 3264class HPhi : public HInstruction { 3265 public: 3266 HPhi(ArenaAllocator* arena, uint32_t reg_number, size_t number_of_inputs, Primitive::Type type) 3267 : HInstruction(SideEffects::None()), 3268 inputs_(arena, number_of_inputs), 3269 reg_number_(reg_number), 3270 type_(type), 3271 is_live_(false), 3272 can_be_null_(true) { 3273 inputs_.SetSize(number_of_inputs); 3274 } 3275 3276 // Returns a type equivalent to the given `type`, but that a `HPhi` can hold. 3277 static Primitive::Type ToPhiType(Primitive::Type type) { 3278 switch (type) { 3279 case Primitive::kPrimBoolean: 3280 case Primitive::kPrimByte: 3281 case Primitive::kPrimShort: 3282 case Primitive::kPrimChar: 3283 return Primitive::kPrimInt; 3284 default: 3285 return type; 3286 } 3287 } 3288 3289 size_t InputCount() const OVERRIDE { return inputs_.Size(); } 3290 3291 void AddInput(HInstruction* input); 3292 void RemoveInputAt(size_t index); 3293 3294 Primitive::Type GetType() const OVERRIDE { return type_; } 3295 void SetType(Primitive::Type type) { type_ = type; } 3296 3297 bool CanBeNull() const OVERRIDE { return can_be_null_; } 3298 void SetCanBeNull(bool can_be_null) { can_be_null_ = can_be_null; } 3299 3300 uint32_t GetRegNumber() const { return reg_number_; } 3301 3302 void SetDead() { is_live_ = false; } 3303 void SetLive() { is_live_ = true; } 3304 bool IsDead() const { return !is_live_; } 3305 bool IsLive() const { return is_live_; } 3306 3307 // Returns the next equivalent phi (starting from the current one) or null if there is none. 3308 // An equivalent phi is a phi having the same dex register and type. 3309 // It assumes that phis with the same dex register are adjacent. 3310 HPhi* GetNextEquivalentPhiWithSameType() { 3311 HInstruction* next = GetNext(); 3312 while (next != nullptr && next->AsPhi()->GetRegNumber() == reg_number_) { 3313 if (next->GetType() == GetType()) { 3314 return next->AsPhi(); 3315 } 3316 next = next->GetNext(); 3317 } 3318 return nullptr; 3319 } 3320 3321 DECLARE_INSTRUCTION(Phi); 3322 3323 protected: 3324 const HUserRecord<HInstruction*> InputRecordAt(size_t i) const OVERRIDE { return inputs_.Get(i); } 3325 3326 void SetRawInputRecordAt(size_t index, const HUserRecord<HInstruction*>& input) OVERRIDE { 3327 inputs_.Put(index, input); 3328 } 3329 3330 private: 3331 GrowableArray<HUserRecord<HInstruction*> > inputs_; 3332 const uint32_t reg_number_; 3333 Primitive::Type type_; 3334 bool is_live_; 3335 bool can_be_null_; 3336 3337 DISALLOW_COPY_AND_ASSIGN(HPhi); 3338}; 3339 3340class HNullCheck : public HExpression<1> { 3341 public: 3342 HNullCheck(HInstruction* value, uint32_t dex_pc) 3343 : HExpression(value->GetType(), SideEffects::None()), dex_pc_(dex_pc) { 3344 SetRawInputAt(0, value); 3345 } 3346 3347 bool CanBeMoved() const OVERRIDE { return true; } 3348 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 3349 UNUSED(other); 3350 return true; 3351 } 3352 3353 bool NeedsEnvironment() const OVERRIDE { return true; } 3354 3355 bool CanThrow() const OVERRIDE { return true; } 3356 3357 bool CanBeNull() const OVERRIDE { return false; } 3358 3359 uint32_t GetDexPc() const OVERRIDE { return dex_pc_; } 3360 3361 DECLARE_INSTRUCTION(NullCheck); 3362 3363 private: 3364 const uint32_t dex_pc_; 3365 3366 DISALLOW_COPY_AND_ASSIGN(HNullCheck); 3367}; 3368 3369class FieldInfo : public ValueObject { 3370 public: 3371 FieldInfo(MemberOffset field_offset, 3372 Primitive::Type field_type, 3373 bool is_volatile, 3374 uint32_t index, 3375 const DexFile& dex_file) 3376 : field_offset_(field_offset), 3377 field_type_(field_type), 3378 is_volatile_(is_volatile), 3379 index_(index), 3380 dex_file_(dex_file) {} 3381 3382 MemberOffset GetFieldOffset() const { return field_offset_; } 3383 Primitive::Type GetFieldType() const { return field_type_; } 3384 uint32_t GetFieldIndex() const { return index_; } 3385 const DexFile& GetDexFile() const { return dex_file_; } 3386 bool IsVolatile() const { return is_volatile_; } 3387 3388 private: 3389 const MemberOffset field_offset_; 3390 const Primitive::Type field_type_; 3391 const bool is_volatile_; 3392 uint32_t index_; 3393 const DexFile& dex_file_; 3394}; 3395 3396class HInstanceFieldGet : public HExpression<1> { 3397 public: 3398 HInstanceFieldGet(HInstruction* value, 3399 Primitive::Type field_type, 3400 MemberOffset field_offset, 3401 bool is_volatile, 3402 uint32_t field_idx, 3403 const DexFile& dex_file) 3404 : HExpression(field_type, SideEffects::DependsOnSomething()), 3405 field_info_(field_offset, field_type, is_volatile, field_idx, dex_file) { 3406 SetRawInputAt(0, value); 3407 } 3408 3409 bool CanBeMoved() const OVERRIDE { return !IsVolatile(); } 3410 3411 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 3412 HInstanceFieldGet* other_get = other->AsInstanceFieldGet(); 3413 return GetFieldOffset().SizeValue() == other_get->GetFieldOffset().SizeValue(); 3414 } 3415 3416 bool CanDoImplicitNullCheckOn(HInstruction* obj) const OVERRIDE { 3417 return (obj == InputAt(0)) && GetFieldOffset().Uint32Value() < kPageSize; 3418 } 3419 3420 size_t ComputeHashCode() const OVERRIDE { 3421 return (HInstruction::ComputeHashCode() << 7) | GetFieldOffset().SizeValue(); 3422 } 3423 3424 const FieldInfo& GetFieldInfo() const { return field_info_; } 3425 MemberOffset GetFieldOffset() const { return field_info_.GetFieldOffset(); } 3426 Primitive::Type GetFieldType() const { return field_info_.GetFieldType(); } 3427 bool IsVolatile() const { return field_info_.IsVolatile(); } 3428 3429 DECLARE_INSTRUCTION(InstanceFieldGet); 3430 3431 private: 3432 const FieldInfo field_info_; 3433 3434 DISALLOW_COPY_AND_ASSIGN(HInstanceFieldGet); 3435}; 3436 3437class HInstanceFieldSet : public HTemplateInstruction<2> { 3438 public: 3439 HInstanceFieldSet(HInstruction* object, 3440 HInstruction* value, 3441 Primitive::Type field_type, 3442 MemberOffset field_offset, 3443 bool is_volatile, 3444 uint32_t field_idx, 3445 const DexFile& dex_file) 3446 : HTemplateInstruction(SideEffects::ChangesSomething()), 3447 field_info_(field_offset, field_type, is_volatile, field_idx, dex_file), 3448 value_can_be_null_(true) { 3449 SetRawInputAt(0, object); 3450 SetRawInputAt(1, value); 3451 } 3452 3453 bool CanDoImplicitNullCheckOn(HInstruction* obj) const OVERRIDE { 3454 return (obj == InputAt(0)) && GetFieldOffset().Uint32Value() < kPageSize; 3455 } 3456 3457 const FieldInfo& GetFieldInfo() const { return field_info_; } 3458 MemberOffset GetFieldOffset() const { return field_info_.GetFieldOffset(); } 3459 Primitive::Type GetFieldType() const { return field_info_.GetFieldType(); } 3460 bool IsVolatile() const { return field_info_.IsVolatile(); } 3461 HInstruction* GetValue() const { return InputAt(1); } 3462 bool GetValueCanBeNull() const { return value_can_be_null_; } 3463 void ClearValueCanBeNull() { value_can_be_null_ = false; } 3464 3465 DECLARE_INSTRUCTION(InstanceFieldSet); 3466 3467 private: 3468 const FieldInfo field_info_; 3469 bool value_can_be_null_; 3470 3471 DISALLOW_COPY_AND_ASSIGN(HInstanceFieldSet); 3472}; 3473 3474class HArrayGet : public HExpression<2> { 3475 public: 3476 HArrayGet(HInstruction* array, HInstruction* index, Primitive::Type type) 3477 : HExpression(type, SideEffects::DependsOnSomething()) { 3478 SetRawInputAt(0, array); 3479 SetRawInputAt(1, index); 3480 } 3481 3482 bool CanBeMoved() const OVERRIDE { return true; } 3483 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 3484 UNUSED(other); 3485 return true; 3486 } 3487 bool CanDoImplicitNullCheckOn(HInstruction* obj) const OVERRIDE { 3488 UNUSED(obj); 3489 // TODO: We can be smarter here. 3490 // Currently, the array access is always preceded by an ArrayLength or a NullCheck 3491 // which generates the implicit null check. There are cases when these can be removed 3492 // to produce better code. If we ever add optimizations to do so we should allow an 3493 // implicit check here (as long as the address falls in the first page). 3494 return false; 3495 } 3496 3497 void SetType(Primitive::Type type) { type_ = type; } 3498 3499 HInstruction* GetArray() const { return InputAt(0); } 3500 HInstruction* GetIndex() const { return InputAt(1); } 3501 3502 DECLARE_INSTRUCTION(ArrayGet); 3503 3504 private: 3505 DISALLOW_COPY_AND_ASSIGN(HArrayGet); 3506}; 3507 3508class HArraySet : public HTemplateInstruction<3> { 3509 public: 3510 HArraySet(HInstruction* array, 3511 HInstruction* index, 3512 HInstruction* value, 3513 Primitive::Type expected_component_type, 3514 uint32_t dex_pc) 3515 : HTemplateInstruction(SideEffects::ChangesSomething()), 3516 dex_pc_(dex_pc), 3517 expected_component_type_(expected_component_type), 3518 needs_type_check_(value->GetType() == Primitive::kPrimNot), 3519 value_can_be_null_(true) { 3520 SetRawInputAt(0, array); 3521 SetRawInputAt(1, index); 3522 SetRawInputAt(2, value); 3523 } 3524 3525 bool NeedsEnvironment() const OVERRIDE { 3526 // We currently always call a runtime method to catch array store 3527 // exceptions. 3528 return needs_type_check_; 3529 } 3530 3531 // Can throw ArrayStoreException. 3532 bool CanThrow() const OVERRIDE { return needs_type_check_; } 3533 3534 bool CanDoImplicitNullCheckOn(HInstruction* obj) const OVERRIDE { 3535 UNUSED(obj); 3536 // TODO: Same as for ArrayGet. 3537 return false; 3538 } 3539 3540 void ClearNeedsTypeCheck() { 3541 needs_type_check_ = false; 3542 } 3543 3544 void ClearValueCanBeNull() { 3545 value_can_be_null_ = false; 3546 } 3547 3548 bool GetValueCanBeNull() const { return value_can_be_null_; } 3549 bool NeedsTypeCheck() const { return needs_type_check_; } 3550 3551 uint32_t GetDexPc() const OVERRIDE { return dex_pc_; } 3552 3553 HInstruction* GetArray() const { return InputAt(0); } 3554 HInstruction* GetIndex() const { return InputAt(1); } 3555 HInstruction* GetValue() const { return InputAt(2); } 3556 3557 Primitive::Type GetComponentType() const { 3558 // The Dex format does not type floating point index operations. Since the 3559 // `expected_component_type_` is set during building and can therefore not 3560 // be correct, we also check what is the value type. If it is a floating 3561 // point type, we must use that type. 3562 Primitive::Type value_type = GetValue()->GetType(); 3563 return ((value_type == Primitive::kPrimFloat) || (value_type == Primitive::kPrimDouble)) 3564 ? value_type 3565 : expected_component_type_; 3566 } 3567 3568 DECLARE_INSTRUCTION(ArraySet); 3569 3570 private: 3571 const uint32_t dex_pc_; 3572 const Primitive::Type expected_component_type_; 3573 bool needs_type_check_; 3574 bool value_can_be_null_; 3575 3576 DISALLOW_COPY_AND_ASSIGN(HArraySet); 3577}; 3578 3579class HArrayLength : public HExpression<1> { 3580 public: 3581 explicit HArrayLength(HInstruction* array) 3582 : HExpression(Primitive::kPrimInt, SideEffects::None()) { 3583 // Note that arrays do not change length, so the instruction does not 3584 // depend on any write. 3585 SetRawInputAt(0, array); 3586 } 3587 3588 bool CanBeMoved() const OVERRIDE { return true; } 3589 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 3590 UNUSED(other); 3591 return true; 3592 } 3593 bool CanDoImplicitNullCheckOn(HInstruction* obj) const OVERRIDE { 3594 return obj == InputAt(0); 3595 } 3596 3597 DECLARE_INSTRUCTION(ArrayLength); 3598 3599 private: 3600 DISALLOW_COPY_AND_ASSIGN(HArrayLength); 3601}; 3602 3603class HBoundsCheck : public HExpression<2> { 3604 public: 3605 HBoundsCheck(HInstruction* index, HInstruction* length, uint32_t dex_pc) 3606 : HExpression(index->GetType(), SideEffects::None()), dex_pc_(dex_pc) { 3607 DCHECK(index->GetType() == Primitive::kPrimInt); 3608 SetRawInputAt(0, index); 3609 SetRawInputAt(1, length); 3610 } 3611 3612 bool CanBeMoved() const OVERRIDE { return true; } 3613 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 3614 UNUSED(other); 3615 return true; 3616 } 3617 3618 bool NeedsEnvironment() const OVERRIDE { return true; } 3619 3620 bool CanThrow() const OVERRIDE { return true; } 3621 3622 uint32_t GetDexPc() const OVERRIDE { return dex_pc_; } 3623 3624 DECLARE_INSTRUCTION(BoundsCheck); 3625 3626 private: 3627 const uint32_t dex_pc_; 3628 3629 DISALLOW_COPY_AND_ASSIGN(HBoundsCheck); 3630}; 3631 3632/** 3633 * Some DEX instructions are folded into multiple HInstructions that need 3634 * to stay live until the last HInstruction. This class 3635 * is used as a marker for the baseline compiler to ensure its preceding 3636 * HInstruction stays live. `index` represents the stack location index of the 3637 * instruction (the actual offset is computed as index * vreg_size). 3638 */ 3639class HTemporary : public HTemplateInstruction<0> { 3640 public: 3641 explicit HTemporary(size_t index) : HTemplateInstruction(SideEffects::None()), index_(index) {} 3642 3643 size_t GetIndex() const { return index_; } 3644 3645 Primitive::Type GetType() const OVERRIDE { 3646 // The previous instruction is the one that will be stored in the temporary location. 3647 DCHECK(GetPrevious() != nullptr); 3648 return GetPrevious()->GetType(); 3649 } 3650 3651 DECLARE_INSTRUCTION(Temporary); 3652 3653 private: 3654 const size_t index_; 3655 3656 DISALLOW_COPY_AND_ASSIGN(HTemporary); 3657}; 3658 3659class HSuspendCheck : public HTemplateInstruction<0> { 3660 public: 3661 explicit HSuspendCheck(uint32_t dex_pc) 3662 : HTemplateInstruction(SideEffects::None()), dex_pc_(dex_pc), slow_path_(nullptr) {} 3663 3664 bool NeedsEnvironment() const OVERRIDE { 3665 return true; 3666 } 3667 3668 uint32_t GetDexPc() const OVERRIDE { return dex_pc_; } 3669 void SetSlowPath(SlowPathCode* slow_path) { slow_path_ = slow_path; } 3670 SlowPathCode* GetSlowPath() const { return slow_path_; } 3671 3672 DECLARE_INSTRUCTION(SuspendCheck); 3673 3674 private: 3675 const uint32_t dex_pc_; 3676 3677 // Only used for code generation, in order to share the same slow path between back edges 3678 // of a same loop. 3679 SlowPathCode* slow_path_; 3680 3681 DISALLOW_COPY_AND_ASSIGN(HSuspendCheck); 3682}; 3683 3684/** 3685 * Instruction to load a Class object. 3686 */ 3687class HLoadClass : public HExpression<1> { 3688 public: 3689 HLoadClass(HCurrentMethod* current_method, 3690 uint16_t type_index, 3691 const DexFile& dex_file, 3692 bool is_referrers_class, 3693 uint32_t dex_pc) 3694 : HExpression(Primitive::kPrimNot, SideEffects::None()), 3695 type_index_(type_index), 3696 dex_file_(dex_file), 3697 is_referrers_class_(is_referrers_class), 3698 dex_pc_(dex_pc), 3699 generate_clinit_check_(false), 3700 loaded_class_rti_(ReferenceTypeInfo::CreateTop(/* is_exact */ false)) { 3701 SetRawInputAt(0, current_method); 3702 } 3703 3704 bool CanBeMoved() const OVERRIDE { return true; } 3705 3706 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 3707 return other->AsLoadClass()->type_index_ == type_index_; 3708 } 3709 3710 size_t ComputeHashCode() const OVERRIDE { return type_index_; } 3711 3712 uint32_t GetDexPc() const OVERRIDE { return dex_pc_; } 3713 uint16_t GetTypeIndex() const { return type_index_; } 3714 bool IsReferrersClass() const { return is_referrers_class_; } 3715 3716 bool NeedsEnvironment() const OVERRIDE { 3717 // Will call runtime and load the class if the class is not loaded yet. 3718 // TODO: finer grain decision. 3719 return !is_referrers_class_; 3720 } 3721 3722 bool MustGenerateClinitCheck() const { 3723 return generate_clinit_check_; 3724 } 3725 3726 void SetMustGenerateClinitCheck(bool generate_clinit_check) { 3727 generate_clinit_check_ = generate_clinit_check; 3728 } 3729 3730 bool CanCallRuntime() const { 3731 return MustGenerateClinitCheck() || !is_referrers_class_; 3732 } 3733 3734 bool CanThrow() const OVERRIDE { 3735 // May call runtime and and therefore can throw. 3736 // TODO: finer grain decision. 3737 return CanCallRuntime(); 3738 } 3739 3740 ReferenceTypeInfo GetLoadedClassRTI() { 3741 return loaded_class_rti_; 3742 } 3743 3744 void SetLoadedClassRTI(ReferenceTypeInfo rti) { 3745 // Make sure we only set exact types (the loaded class should never be merged). 3746 DCHECK(rti.IsExact()); 3747 loaded_class_rti_ = rti; 3748 } 3749 3750 bool IsResolved() { 3751 return loaded_class_rti_.IsExact(); 3752 } 3753 3754 const DexFile& GetDexFile() { return dex_file_; } 3755 3756 bool NeedsDexCache() const OVERRIDE { return !is_referrers_class_; } 3757 3758 DECLARE_INSTRUCTION(LoadClass); 3759 3760 private: 3761 const uint16_t type_index_; 3762 const DexFile& dex_file_; 3763 const bool is_referrers_class_; 3764 const uint32_t dex_pc_; 3765 // Whether this instruction must generate the initialization check. 3766 // Used for code generation. 3767 bool generate_clinit_check_; 3768 3769 ReferenceTypeInfo loaded_class_rti_; 3770 3771 DISALLOW_COPY_AND_ASSIGN(HLoadClass); 3772}; 3773 3774class HLoadString : public HExpression<1> { 3775 public: 3776 HLoadString(HCurrentMethod* current_method, uint32_t string_index, uint32_t dex_pc) 3777 : HExpression(Primitive::kPrimNot, SideEffects::None()), 3778 string_index_(string_index), 3779 dex_pc_(dex_pc) { 3780 SetRawInputAt(0, current_method); 3781 } 3782 3783 bool CanBeMoved() const OVERRIDE { return true; } 3784 3785 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 3786 return other->AsLoadString()->string_index_ == string_index_; 3787 } 3788 3789 size_t ComputeHashCode() const OVERRIDE { return string_index_; } 3790 3791 uint32_t GetDexPc() const OVERRIDE { return dex_pc_; } 3792 uint32_t GetStringIndex() const { return string_index_; } 3793 3794 // TODO: Can we deopt or debug when we resolve a string? 3795 bool NeedsEnvironment() const OVERRIDE { return false; } 3796 bool NeedsDexCache() const OVERRIDE { return true; } 3797 3798 DECLARE_INSTRUCTION(LoadString); 3799 3800 private: 3801 const uint32_t string_index_; 3802 const uint32_t dex_pc_; 3803 3804 DISALLOW_COPY_AND_ASSIGN(HLoadString); 3805}; 3806 3807/** 3808 * Performs an initialization check on its Class object input. 3809 */ 3810class HClinitCheck : public HExpression<1> { 3811 public: 3812 explicit HClinitCheck(HLoadClass* constant, uint32_t dex_pc) 3813 : HExpression(Primitive::kPrimNot, SideEffects::ChangesSomething()), 3814 dex_pc_(dex_pc) { 3815 SetRawInputAt(0, constant); 3816 } 3817 3818 bool CanBeMoved() const OVERRIDE { return true; } 3819 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 3820 UNUSED(other); 3821 return true; 3822 } 3823 3824 bool NeedsEnvironment() const OVERRIDE { 3825 // May call runtime to initialize the class. 3826 return true; 3827 } 3828 3829 uint32_t GetDexPc() const OVERRIDE { return dex_pc_; } 3830 3831 HLoadClass* GetLoadClass() const { return InputAt(0)->AsLoadClass(); } 3832 3833 DECLARE_INSTRUCTION(ClinitCheck); 3834 3835 private: 3836 const uint32_t dex_pc_; 3837 3838 DISALLOW_COPY_AND_ASSIGN(HClinitCheck); 3839}; 3840 3841class HStaticFieldGet : public HExpression<1> { 3842 public: 3843 HStaticFieldGet(HInstruction* cls, 3844 Primitive::Type field_type, 3845 MemberOffset field_offset, 3846 bool is_volatile, 3847 uint32_t field_idx, 3848 const DexFile& dex_file) 3849 : HExpression(field_type, SideEffects::DependsOnSomething()), 3850 field_info_(field_offset, field_type, is_volatile, field_idx, dex_file) { 3851 SetRawInputAt(0, cls); 3852 } 3853 3854 3855 bool CanBeMoved() const OVERRIDE { return !IsVolatile(); } 3856 3857 bool InstructionDataEquals(HInstruction* other) const OVERRIDE { 3858 HStaticFieldGet* other_get = other->AsStaticFieldGet(); 3859 return GetFieldOffset().SizeValue() == other_get->GetFieldOffset().SizeValue(); 3860 } 3861 3862 size_t ComputeHashCode() const OVERRIDE { 3863 return (HInstruction::ComputeHashCode() << 7) | GetFieldOffset().SizeValue(); 3864 } 3865 3866 const FieldInfo& GetFieldInfo() const { return field_info_; } 3867 MemberOffset GetFieldOffset() const { return field_info_.GetFieldOffset(); } 3868 Primitive::Type GetFieldType() const { return field_info_.GetFieldType(); } 3869 bool IsVolatile() const { return field_info_.IsVolatile(); } 3870 3871 DECLARE_INSTRUCTION(StaticFieldGet); 3872 3873 private: 3874 const FieldInfo field_info_; 3875 3876 DISALLOW_COPY_AND_ASSIGN(HStaticFieldGet); 3877}; 3878 3879class HStaticFieldSet : public HTemplateInstruction<2> { 3880 public: 3881 HStaticFieldSet(HInstruction* cls, 3882 HInstruction* value, 3883 Primitive::Type field_type, 3884 MemberOffset field_offset, 3885 bool is_volatile, 3886 uint32_t field_idx, 3887 const DexFile& dex_file) 3888 : HTemplateInstruction(SideEffects::ChangesSomething()), 3889 field_info_(field_offset, field_type, is_volatile, field_idx, dex_file), 3890 value_can_be_null_(true) { 3891 SetRawInputAt(0, cls); 3892 SetRawInputAt(1, value); 3893 } 3894 3895 const FieldInfo& GetFieldInfo() const { return field_info_; } 3896 MemberOffset GetFieldOffset() const { return field_info_.GetFieldOffset(); } 3897 Primitive::Type GetFieldType() const { return field_info_.GetFieldType(); } 3898 bool IsVolatile() const { return field_info_.IsVolatile(); } 3899 3900 HInstruction* GetValue() const { return InputAt(1); } 3901 bool GetValueCanBeNull() const { return value_can_be_null_; } 3902 void ClearValueCanBeNull() { value_can_be_null_ = false; } 3903 3904 DECLARE_INSTRUCTION(StaticFieldSet); 3905 3906 private: 3907 const FieldInfo field_info_; 3908 bool value_can_be_null_; 3909 3910 DISALLOW_COPY_AND_ASSIGN(HStaticFieldSet); 3911}; 3912 3913// Implement the move-exception DEX instruction. 3914class HLoadException : public HExpression<0> { 3915 public: 3916 HLoadException() : HExpression(Primitive::kPrimNot, SideEffects::None()) {} 3917 3918 DECLARE_INSTRUCTION(LoadException); 3919 3920 private: 3921 DISALLOW_COPY_AND_ASSIGN(HLoadException); 3922}; 3923 3924class HThrow : public HTemplateInstruction<1> { 3925 public: 3926 HThrow(HInstruction* exception, uint32_t dex_pc) 3927 : HTemplateInstruction(SideEffects::None()), dex_pc_(dex_pc) { 3928 SetRawInputAt(0, exception); 3929 } 3930 3931 bool IsControlFlow() const OVERRIDE { return true; } 3932 3933 bool NeedsEnvironment() const OVERRIDE { return true; } 3934 3935 bool CanThrow() const OVERRIDE { return true; } 3936 3937 uint32_t GetDexPc() const OVERRIDE { return dex_pc_; } 3938 3939 DECLARE_INSTRUCTION(Throw); 3940 3941 private: 3942 const uint32_t dex_pc_; 3943 3944 DISALLOW_COPY_AND_ASSIGN(HThrow); 3945}; 3946 3947class HInstanceOf : public HExpression<2> { 3948 public: 3949 HInstanceOf(HInstruction* object, 3950 HLoadClass* constant, 3951 bool class_is_final, 3952 uint32_t dex_pc) 3953 : HExpression(Primitive::kPrimBoolean, SideEffects::None()), 3954 class_is_final_(class_is_final), 3955 must_do_null_check_(true), 3956 dex_pc_(dex_pc) { 3957 SetRawInputAt(0, object); 3958 SetRawInputAt(1, constant); 3959 } 3960 3961 bool CanBeMoved() const OVERRIDE { return true; } 3962 3963 bool InstructionDataEquals(HInstruction* other ATTRIBUTE_UNUSED) const OVERRIDE { 3964 return true; 3965 } 3966 3967 bool NeedsEnvironment() const OVERRIDE { 3968 return false; 3969 } 3970 3971 uint32_t GetDexPc() const OVERRIDE { return dex_pc_; } 3972 3973 bool IsClassFinal() const { return class_is_final_; } 3974 3975 // Used only in code generation. 3976 bool MustDoNullCheck() const { return must_do_null_check_; } 3977 void ClearMustDoNullCheck() { must_do_null_check_ = false; } 3978 3979 DECLARE_INSTRUCTION(InstanceOf); 3980 3981 private: 3982 const bool class_is_final_; 3983 bool must_do_null_check_; 3984 const uint32_t dex_pc_; 3985 3986 DISALLOW_COPY_AND_ASSIGN(HInstanceOf); 3987}; 3988 3989class HBoundType : public HExpression<1> { 3990 public: 3991 HBoundType(HInstruction* input, ReferenceTypeInfo bound_type) 3992 : HExpression(Primitive::kPrimNot, SideEffects::None()), 3993 bound_type_(bound_type) { 3994 DCHECK_EQ(input->GetType(), Primitive::kPrimNot); 3995 SetRawInputAt(0, input); 3996 } 3997 3998 const ReferenceTypeInfo& GetBoundType() const { return bound_type_; } 3999 4000 bool CanBeNull() const OVERRIDE { 4001 // `null instanceof ClassX` always return false so we can't be null. 4002 return false; 4003 } 4004 4005 DECLARE_INSTRUCTION(BoundType); 4006 4007 private: 4008 // Encodes the most upper class that this instruction can have. In other words 4009 // it is always the case that GetBoundType().IsSupertypeOf(GetReferenceType()). 4010 // It is used to bound the type in cases like `if (x instanceof ClassX) {}` 4011 const ReferenceTypeInfo bound_type_; 4012 4013 DISALLOW_COPY_AND_ASSIGN(HBoundType); 4014}; 4015 4016class HCheckCast : public HTemplateInstruction<2> { 4017 public: 4018 HCheckCast(HInstruction* object, 4019 HLoadClass* constant, 4020 bool class_is_final, 4021 uint32_t dex_pc) 4022 : HTemplateInstruction(SideEffects::None()), 4023 class_is_final_(class_is_final), 4024 must_do_null_check_(true), 4025 dex_pc_(dex_pc) { 4026 SetRawInputAt(0, object); 4027 SetRawInputAt(1, constant); 4028 } 4029 4030 bool CanBeMoved() const OVERRIDE { return true; } 4031 4032 bool InstructionDataEquals(HInstruction* other ATTRIBUTE_UNUSED) const OVERRIDE { 4033 return true; 4034 } 4035 4036 bool NeedsEnvironment() const OVERRIDE { 4037 // Instruction may throw a CheckCastError. 4038 return true; 4039 } 4040 4041 bool CanThrow() const OVERRIDE { return true; } 4042 4043 bool MustDoNullCheck() const { return must_do_null_check_; } 4044 void ClearMustDoNullCheck() { must_do_null_check_ = false; } 4045 4046 uint32_t GetDexPc() const OVERRIDE { return dex_pc_; } 4047 4048 bool IsClassFinal() const { return class_is_final_; } 4049 4050 DECLARE_INSTRUCTION(CheckCast); 4051 4052 private: 4053 const bool class_is_final_; 4054 bool must_do_null_check_; 4055 const uint32_t dex_pc_; 4056 4057 DISALLOW_COPY_AND_ASSIGN(HCheckCast); 4058}; 4059 4060class HMemoryBarrier : public HTemplateInstruction<0> { 4061 public: 4062 explicit HMemoryBarrier(MemBarrierKind barrier_kind) 4063 : HTemplateInstruction(SideEffects::None()), 4064 barrier_kind_(barrier_kind) {} 4065 4066 MemBarrierKind GetBarrierKind() { return barrier_kind_; } 4067 4068 DECLARE_INSTRUCTION(MemoryBarrier); 4069 4070 private: 4071 const MemBarrierKind barrier_kind_; 4072 4073 DISALLOW_COPY_AND_ASSIGN(HMemoryBarrier); 4074}; 4075 4076class HMonitorOperation : public HTemplateInstruction<1> { 4077 public: 4078 enum OperationKind { 4079 kEnter, 4080 kExit, 4081 }; 4082 4083 HMonitorOperation(HInstruction* object, OperationKind kind, uint32_t dex_pc) 4084 : HTemplateInstruction(SideEffects::None()), kind_(kind), dex_pc_(dex_pc) { 4085 SetRawInputAt(0, object); 4086 } 4087 4088 // Instruction may throw a Java exception, so we need an environment. 4089 bool NeedsEnvironment() const OVERRIDE { return true; } 4090 bool CanThrow() const OVERRIDE { return true; } 4091 4092 uint32_t GetDexPc() const OVERRIDE { return dex_pc_; } 4093 4094 bool IsEnter() const { return kind_ == kEnter; } 4095 4096 DECLARE_INSTRUCTION(MonitorOperation); 4097 4098 private: 4099 const OperationKind kind_; 4100 const uint32_t dex_pc_; 4101 4102 private: 4103 DISALLOW_COPY_AND_ASSIGN(HMonitorOperation); 4104}; 4105 4106class MoveOperands : public ArenaObject<kArenaAllocMisc> { 4107 public: 4108 MoveOperands(Location source, 4109 Location destination, 4110 Primitive::Type type, 4111 HInstruction* instruction) 4112 : source_(source), destination_(destination), type_(type), instruction_(instruction) {} 4113 4114 Location GetSource() const { return source_; } 4115 Location GetDestination() const { return destination_; } 4116 4117 void SetSource(Location value) { source_ = value; } 4118 void SetDestination(Location value) { destination_ = value; } 4119 4120 // The parallel move resolver marks moves as "in-progress" by clearing the 4121 // destination (but not the source). 4122 Location MarkPending() { 4123 DCHECK(!IsPending()); 4124 Location dest = destination_; 4125 destination_ = Location::NoLocation(); 4126 return dest; 4127 } 4128 4129 void ClearPending(Location dest) { 4130 DCHECK(IsPending()); 4131 destination_ = dest; 4132 } 4133 4134 bool IsPending() const { 4135 DCHECK(!source_.IsInvalid() || destination_.IsInvalid()); 4136 return destination_.IsInvalid() && !source_.IsInvalid(); 4137 } 4138 4139 // True if this blocks a move from the given location. 4140 bool Blocks(Location loc) const { 4141 return !IsEliminated() && source_.OverlapsWith(loc); 4142 } 4143 4144 // A move is redundant if it's been eliminated, if its source and 4145 // destination are the same, or if its destination is unneeded. 4146 bool IsRedundant() const { 4147 return IsEliminated() || destination_.IsInvalid() || source_.Equals(destination_); 4148 } 4149 4150 // We clear both operands to indicate move that's been eliminated. 4151 void Eliminate() { 4152 source_ = destination_ = Location::NoLocation(); 4153 } 4154 4155 bool IsEliminated() const { 4156 DCHECK(!source_.IsInvalid() || destination_.IsInvalid()); 4157 return source_.IsInvalid(); 4158 } 4159 4160 Primitive::Type GetType() const { return type_; } 4161 4162 bool Is64BitMove() const { 4163 return Primitive::Is64BitType(type_); 4164 } 4165 4166 HInstruction* GetInstruction() const { return instruction_; } 4167 4168 private: 4169 Location source_; 4170 Location destination_; 4171 // The type this move is for. 4172 Primitive::Type type_; 4173 // The instruction this move is assocatied with. Null when this move is 4174 // for moving an input in the expected locations of user (including a phi user). 4175 // This is only used in debug mode, to ensure we do not connect interval siblings 4176 // in the same parallel move. 4177 HInstruction* instruction_; 4178}; 4179 4180static constexpr size_t kDefaultNumberOfMoves = 4; 4181 4182class HParallelMove : public HTemplateInstruction<0> { 4183 public: 4184 explicit HParallelMove(ArenaAllocator* arena) 4185 : HTemplateInstruction(SideEffects::None()), moves_(arena, kDefaultNumberOfMoves) {} 4186 4187 void AddMove(Location source, 4188 Location destination, 4189 Primitive::Type type, 4190 HInstruction* instruction) { 4191 DCHECK(source.IsValid()); 4192 DCHECK(destination.IsValid()); 4193 if (kIsDebugBuild) { 4194 if (instruction != nullptr) { 4195 for (size_t i = 0, e = moves_.Size(); i < e; ++i) { 4196 if (moves_.Get(i).GetInstruction() == instruction) { 4197 // Special case the situation where the move is for the spill slot 4198 // of the instruction. 4199 if ((GetPrevious() == instruction) 4200 || ((GetPrevious() == nullptr) 4201 && instruction->IsPhi() 4202 && instruction->GetBlock() == GetBlock())) { 4203 DCHECK_NE(destination.GetKind(), moves_.Get(i).GetDestination().GetKind()) 4204 << "Doing parallel moves for the same instruction."; 4205 } else { 4206 DCHECK(false) << "Doing parallel moves for the same instruction."; 4207 } 4208 } 4209 } 4210 } 4211 for (size_t i = 0, e = moves_.Size(); i < e; ++i) { 4212 DCHECK(!destination.OverlapsWith(moves_.Get(i).GetDestination())) 4213 << "Overlapped destination for two moves in a parallel move: " 4214 << moves_.Get(i).GetSource() << " ==> " << moves_.Get(i).GetDestination() << " and " 4215 << source << " ==> " << destination; 4216 } 4217 } 4218 moves_.Add(MoveOperands(source, destination, type, instruction)); 4219 } 4220 4221 MoveOperands* MoveOperandsAt(size_t index) const { 4222 return moves_.GetRawStorage() + index; 4223 } 4224 4225 size_t NumMoves() const { return moves_.Size(); } 4226 4227 DECLARE_INSTRUCTION(ParallelMove); 4228 4229 private: 4230 GrowableArray<MoveOperands> moves_; 4231 4232 DISALLOW_COPY_AND_ASSIGN(HParallelMove); 4233}; 4234 4235class HGraphVisitor : public ValueObject { 4236 public: 4237 explicit HGraphVisitor(HGraph* graph) : graph_(graph) {} 4238 virtual ~HGraphVisitor() {} 4239 4240 virtual void VisitInstruction(HInstruction* instruction) { UNUSED(instruction); } 4241 virtual void VisitBasicBlock(HBasicBlock* block); 4242 4243 // Visit the graph following basic block insertion order. 4244 void VisitInsertionOrder(); 4245 4246 // Visit the graph following dominator tree reverse post-order. 4247 void VisitReversePostOrder(); 4248 4249 HGraph* GetGraph() const { return graph_; } 4250 4251 // Visit functions for instruction classes. 4252#define DECLARE_VISIT_INSTRUCTION(name, super) \ 4253 virtual void Visit##name(H##name* instr) { VisitInstruction(instr); } 4254 4255 FOR_EACH_INSTRUCTION(DECLARE_VISIT_INSTRUCTION) 4256 4257#undef DECLARE_VISIT_INSTRUCTION 4258 4259 private: 4260 HGraph* const graph_; 4261 4262 DISALLOW_COPY_AND_ASSIGN(HGraphVisitor); 4263}; 4264 4265class HGraphDelegateVisitor : public HGraphVisitor { 4266 public: 4267 explicit HGraphDelegateVisitor(HGraph* graph) : HGraphVisitor(graph) {} 4268 virtual ~HGraphDelegateVisitor() {} 4269 4270 // Visit functions that delegate to to super class. 4271#define DECLARE_VISIT_INSTRUCTION(name, super) \ 4272 void Visit##name(H##name* instr) OVERRIDE { Visit##super(instr); } 4273 4274 FOR_EACH_INSTRUCTION(DECLARE_VISIT_INSTRUCTION) 4275 4276#undef DECLARE_VISIT_INSTRUCTION 4277 4278 private: 4279 DISALLOW_COPY_AND_ASSIGN(HGraphDelegateVisitor); 4280}; 4281 4282class HInsertionOrderIterator : public ValueObject { 4283 public: 4284 explicit HInsertionOrderIterator(const HGraph& graph) : graph_(graph), index_(0) {} 4285 4286 bool Done() const { return index_ == graph_.GetBlocks().Size(); } 4287 HBasicBlock* Current() const { return graph_.GetBlocks().Get(index_); } 4288 void Advance() { ++index_; } 4289 4290 private: 4291 const HGraph& graph_; 4292 size_t index_; 4293 4294 DISALLOW_COPY_AND_ASSIGN(HInsertionOrderIterator); 4295}; 4296 4297class HReversePostOrderIterator : public ValueObject { 4298 public: 4299 explicit HReversePostOrderIterator(const HGraph& graph) : graph_(graph), index_(0) { 4300 // Check that reverse post order of the graph has been built. 4301 DCHECK(!graph.GetReversePostOrder().IsEmpty()); 4302 } 4303 4304 bool Done() const { return index_ == graph_.GetReversePostOrder().Size(); } 4305 HBasicBlock* Current() const { return graph_.GetReversePostOrder().Get(index_); } 4306 void Advance() { ++index_; } 4307 4308 private: 4309 const HGraph& graph_; 4310 size_t index_; 4311 4312 DISALLOW_COPY_AND_ASSIGN(HReversePostOrderIterator); 4313}; 4314 4315class HPostOrderIterator : public ValueObject { 4316 public: 4317 explicit HPostOrderIterator(const HGraph& graph) 4318 : graph_(graph), index_(graph_.GetReversePostOrder().Size()) { 4319 // Check that reverse post order of the graph has been built. 4320 DCHECK(!graph.GetReversePostOrder().IsEmpty()); 4321 } 4322 4323 bool Done() const { return index_ == 0; } 4324 HBasicBlock* Current() const { return graph_.GetReversePostOrder().Get(index_ - 1); } 4325 void Advance() { --index_; } 4326 4327 private: 4328 const HGraph& graph_; 4329 size_t index_; 4330 4331 DISALLOW_COPY_AND_ASSIGN(HPostOrderIterator); 4332}; 4333 4334class HLinearPostOrderIterator : public ValueObject { 4335 public: 4336 explicit HLinearPostOrderIterator(const HGraph& graph) 4337 : order_(graph.GetLinearOrder()), index_(graph.GetLinearOrder().Size()) {} 4338 4339 bool Done() const { return index_ == 0; } 4340 4341 HBasicBlock* Current() const { return order_.Get(index_ -1); } 4342 4343 void Advance() { 4344 --index_; 4345 DCHECK_GE(index_, 0U); 4346 } 4347 4348 private: 4349 const GrowableArray<HBasicBlock*>& order_; 4350 size_t index_; 4351 4352 DISALLOW_COPY_AND_ASSIGN(HLinearPostOrderIterator); 4353}; 4354 4355class HLinearOrderIterator : public ValueObject { 4356 public: 4357 explicit HLinearOrderIterator(const HGraph& graph) 4358 : order_(graph.GetLinearOrder()), index_(0) {} 4359 4360 bool Done() const { return index_ == order_.Size(); } 4361 HBasicBlock* Current() const { return order_.Get(index_); } 4362 void Advance() { ++index_; } 4363 4364 private: 4365 const GrowableArray<HBasicBlock*>& order_; 4366 size_t index_; 4367 4368 DISALLOW_COPY_AND_ASSIGN(HLinearOrderIterator); 4369}; 4370 4371// Iterator over the blocks that art part of the loop. Includes blocks part 4372// of an inner loop. The order in which the blocks are iterated is on their 4373// block id. 4374class HBlocksInLoopIterator : public ValueObject { 4375 public: 4376 explicit HBlocksInLoopIterator(const HLoopInformation& info) 4377 : blocks_in_loop_(info.GetBlocks()), 4378 blocks_(info.GetHeader()->GetGraph()->GetBlocks()), 4379 index_(0) { 4380 if (!blocks_in_loop_.IsBitSet(index_)) { 4381 Advance(); 4382 } 4383 } 4384 4385 bool Done() const { return index_ == blocks_.Size(); } 4386 HBasicBlock* Current() const { return blocks_.Get(index_); } 4387 void Advance() { 4388 ++index_; 4389 for (size_t e = blocks_.Size(); index_ < e; ++index_) { 4390 if (blocks_in_loop_.IsBitSet(index_)) { 4391 break; 4392 } 4393 } 4394 } 4395 4396 private: 4397 const BitVector& blocks_in_loop_; 4398 const GrowableArray<HBasicBlock*>& blocks_; 4399 size_t index_; 4400 4401 DISALLOW_COPY_AND_ASSIGN(HBlocksInLoopIterator); 4402}; 4403 4404// Iterator over the blocks that art part of the loop. Includes blocks part 4405// of an inner loop. The order in which the blocks are iterated is reverse 4406// post order. 4407class HBlocksInLoopReversePostOrderIterator : public ValueObject { 4408 public: 4409 explicit HBlocksInLoopReversePostOrderIterator(const HLoopInformation& info) 4410 : blocks_in_loop_(info.GetBlocks()), 4411 blocks_(info.GetHeader()->GetGraph()->GetReversePostOrder()), 4412 index_(0) { 4413 if (!blocks_in_loop_.IsBitSet(blocks_.Get(index_)->GetBlockId())) { 4414 Advance(); 4415 } 4416 } 4417 4418 bool Done() const { return index_ == blocks_.Size(); } 4419 HBasicBlock* Current() const { return blocks_.Get(index_); } 4420 void Advance() { 4421 ++index_; 4422 for (size_t e = blocks_.Size(); index_ < e; ++index_) { 4423 if (blocks_in_loop_.IsBitSet(blocks_.Get(index_)->GetBlockId())) { 4424 break; 4425 } 4426 } 4427 } 4428 4429 private: 4430 const BitVector& blocks_in_loop_; 4431 const GrowableArray<HBasicBlock*>& blocks_; 4432 size_t index_; 4433 4434 DISALLOW_COPY_AND_ASSIGN(HBlocksInLoopReversePostOrderIterator); 4435}; 4436 4437inline int64_t Int64FromConstant(HConstant* constant) { 4438 DCHECK(constant->IsIntConstant() || constant->IsLongConstant()); 4439 return constant->IsIntConstant() ? constant->AsIntConstant()->GetValue() 4440 : constant->AsLongConstant()->GetValue(); 4441} 4442 4443} // namespace art 4444 4445#endif // ART_COMPILER_OPTIMIZING_NODES_H_ 4446