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