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