nodes.h revision d8ee737fdbf380c5bb90c9270c8d1087ac23e76c
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 "utils/allocation.h" 21#include "utils/arena_bit_vector.h" 22#include "utils/growable_array.h" 23 24namespace art { 25 26class HBasicBlock; 27class HInstruction; 28class HIntConstant; 29class HGraphVisitor; 30class LocationSummary; 31 32static const int kDefaultNumberOfBlocks = 8; 33static const int kDefaultNumberOfSuccessors = 2; 34static const int kDefaultNumberOfPredecessors = 2; 35static const int kDefaultNumberOfBackEdges = 1; 36 37// Control-flow graph of a method. Contains a list of basic blocks. 38class HGraph : public ArenaObject { 39 public: 40 explicit HGraph(ArenaAllocator* arena) 41 : arena_(arena), 42 blocks_(arena, kDefaultNumberOfBlocks), 43 dominator_order_(arena, kDefaultNumberOfBlocks), 44 current_instruction_id_(0) { } 45 46 ArenaAllocator* GetArena() const { return arena_; } 47 const GrowableArray<HBasicBlock*>* GetBlocks() const { return &blocks_; } 48 49 HBasicBlock* GetEntryBlock() const { return entry_block_; } 50 HBasicBlock* GetExitBlock() const { return exit_block_; } 51 52 void SetEntryBlock(HBasicBlock* block) { entry_block_ = block; } 53 void SetExitBlock(HBasicBlock* block) { exit_block_ = block; } 54 55 void AddBlock(HBasicBlock* block); 56 void BuildDominatorTree(); 57 58 int GetNextInstructionId() { 59 return current_instruction_id_++; 60 } 61 62 private: 63 HBasicBlock* FindCommonDominator(HBasicBlock* first, HBasicBlock* second) const; 64 void VisitBlockForDominatorTree(HBasicBlock* block, 65 HBasicBlock* predecessor, 66 GrowableArray<size_t>* visits); 67 void FindBackEdges(ArenaBitVector* visited) const; 68 void VisitBlockForBackEdges(HBasicBlock* block, 69 ArenaBitVector* visited, 70 ArenaBitVector* visiting) const; 71 void RemoveDeadBlocks(const ArenaBitVector& visited) const; 72 73 ArenaAllocator* const arena_; 74 75 // List of blocks in insertion order. 76 GrowableArray<HBasicBlock*> blocks_; 77 78 // List of blocks to perform a pre-order dominator tree traversal. 79 GrowableArray<HBasicBlock*> dominator_order_; 80 81 HBasicBlock* entry_block_; 82 HBasicBlock* exit_block_; 83 84 // The current id to assign to a newly added instruction. See HInstruction.id_. 85 int current_instruction_id_; 86 87 DISALLOW_COPY_AND_ASSIGN(HGraph); 88}; 89 90class HLoopInformation : public ArenaObject { 91 public: 92 HLoopInformation(HBasicBlock* header, HGraph* graph) 93 : header_(header), 94 back_edges_(graph->GetArena(), kDefaultNumberOfBackEdges) { } 95 96 void AddBackEdge(HBasicBlock* back_edge) { 97 back_edges_.Add(back_edge); 98 } 99 100 int NumberOfBackEdges() const { 101 return back_edges_.Size(); 102 } 103 104 private: 105 HBasicBlock* header_; 106 GrowableArray<HBasicBlock*> back_edges_; 107 108 DISALLOW_COPY_AND_ASSIGN(HLoopInformation); 109}; 110 111// A block in a method. Contains the list of instructions represented 112// as a double linked list. Each block knows its predecessors and 113// successors. 114class HBasicBlock : public ArenaObject { 115 public: 116 explicit HBasicBlock(HGraph* graph) 117 : graph_(graph), 118 predecessors_(graph->GetArena(), kDefaultNumberOfPredecessors), 119 successors_(graph->GetArena(), kDefaultNumberOfSuccessors), 120 first_instruction_(nullptr), 121 last_instruction_(nullptr), 122 loop_information_(nullptr), 123 dominator_(nullptr), 124 block_id_(-1) { } 125 126 const GrowableArray<HBasicBlock*>* GetPredecessors() const { 127 return &predecessors_; 128 } 129 130 const GrowableArray<HBasicBlock*>* GetSuccessors() const { 131 return &successors_; 132 } 133 134 void AddBackEdge(HBasicBlock* back_edge) { 135 if (loop_information_ == nullptr) { 136 loop_information_ = new (graph_->GetArena()) HLoopInformation(this, graph_); 137 } 138 loop_information_->AddBackEdge(back_edge); 139 } 140 141 HGraph* GetGraph() const { return graph_; } 142 143 int GetBlockId() const { return block_id_; } 144 void SetBlockId(int id) { block_id_ = id; } 145 146 HBasicBlock* GetDominator() const { return dominator_; } 147 void SetDominator(HBasicBlock* dominator) { dominator_ = dominator; } 148 149 int NumberOfBackEdges() const { 150 return loop_information_ == nullptr 151 ? 0 152 : loop_information_->NumberOfBackEdges(); 153 } 154 155 HInstruction* GetFirstInstruction() const { return first_instruction_; } 156 HInstruction* GetLastInstruction() const { return last_instruction_; } 157 158 void AddSuccessor(HBasicBlock* block) { 159 successors_.Add(block); 160 block->predecessors_.Add(this); 161 } 162 163 void RemovePredecessor(HBasicBlock* block) { 164 predecessors_.Delete(block); 165 } 166 167 void AddInstruction(HInstruction* instruction); 168 169 private: 170 HGraph* const graph_; 171 GrowableArray<HBasicBlock*> predecessors_; 172 GrowableArray<HBasicBlock*> successors_; 173 HInstruction* first_instruction_; 174 HInstruction* last_instruction_; 175 HLoopInformation* loop_information_; 176 HBasicBlock* dominator_; 177 int block_id_; 178 179 DISALLOW_COPY_AND_ASSIGN(HBasicBlock); 180}; 181 182#define FOR_EACH_INSTRUCTION(M) \ 183 M(Add) \ 184 M(Equal) \ 185 M(Exit) \ 186 M(Goto) \ 187 M(If) \ 188 M(IntConstant) \ 189 M(InvokeStatic) \ 190 M(LoadLocal) \ 191 M(Local) \ 192 M(Return) \ 193 M(ReturnVoid) \ 194 M(StoreLocal) \ 195 196#define FORWARD_DECLARATION(type) class H##type; 197FOR_EACH_INSTRUCTION(FORWARD_DECLARATION) 198#undef FORWARD_DECLARATION 199 200#define DECLARE_INSTRUCTION(type) \ 201 virtual void Accept(HGraphVisitor* visitor); \ 202 virtual const char* DebugName() const { return #type; } \ 203 virtual H##type* As##type() { return this; } \ 204 205class HUseListNode : public ArenaObject { 206 public: 207 HUseListNode(HInstruction* instruction, HUseListNode* tail) 208 : instruction_(instruction), tail_(tail) { } 209 210 HUseListNode* GetTail() const { return tail_; } 211 HInstruction* GetInstruction() const { return instruction_; } 212 213 private: 214 HInstruction* const instruction_; 215 HUseListNode* const tail_; 216 217 DISALLOW_COPY_AND_ASSIGN(HUseListNode); 218}; 219 220class HInstruction : public ArenaObject { 221 public: 222 HInstruction() 223 : previous_(nullptr), 224 next_(nullptr), 225 block_(nullptr), 226 id_(-1), 227 uses_(nullptr), 228 locations_(nullptr) { } 229 230 virtual ~HInstruction() { } 231 232 HInstruction* GetNext() const { return next_; } 233 HInstruction* GetPrevious() const { return previous_; } 234 235 HBasicBlock* GetBlock() const { return block_; } 236 void SetBlock(HBasicBlock* block) { block_ = block; } 237 238 virtual intptr_t InputCount() const = 0; 239 virtual HInstruction* InputAt(intptr_t i) const = 0; 240 241 virtual void Accept(HGraphVisitor* visitor) = 0; 242 virtual const char* DebugName() const = 0; 243 244 void AddUse(HInstruction* user) { 245 uses_ = new (block_->GetGraph()->GetArena()) HUseListNode(user, uses_); 246 } 247 248 HUseListNode* GetUses() const { return uses_; } 249 250 bool HasUses() const { return uses_ != nullptr; } 251 252 int GetId() const { return id_; } 253 void SetId(int id) { id_ = id; } 254 255 LocationSummary* GetLocations() const { return locations_; } 256 void SetLocations(LocationSummary* locations) { locations_ = locations; } 257 258#define INSTRUCTION_TYPE_CHECK(type) \ 259 virtual H##type* As##type() { return nullptr; } 260 261 FOR_EACH_INSTRUCTION(INSTRUCTION_TYPE_CHECK) 262#undef INSTRUCTION_TYPE_CHECK 263 264 private: 265 HInstruction* previous_; 266 HInstruction* next_; 267 HBasicBlock* block_; 268 269 // An instruction gets an id when it is added to the graph. 270 // It reflects creation order. A negative id means the instruction 271 // has not beed added to the graph. 272 int id_; 273 274 HUseListNode* uses_; 275 276 // Set by the code generator. 277 LocationSummary* locations_; 278 279 friend class HBasicBlock; 280 281 DISALLOW_COPY_AND_ASSIGN(HInstruction); 282}; 283 284class HUseIterator : public ValueObject { 285 public: 286 explicit HUseIterator(HInstruction* instruction) : current_(instruction->GetUses()) { } 287 288 bool Done() const { return current_ == nullptr; } 289 290 void Advance() { 291 DCHECK(!Done()); 292 current_ = current_->GetTail(); 293 } 294 295 HInstruction* Current() const { 296 DCHECK(!Done()); 297 return current_->GetInstruction(); 298 } 299 300 private: 301 HUseListNode* current_; 302 303 friend class HValue; 304}; 305 306class HInputIterator : public ValueObject { 307 public: 308 explicit HInputIterator(HInstruction* instruction) : instruction_(instruction), index_(0) { } 309 310 bool Done() const { return index_ == instruction_->InputCount(); } 311 HInstruction* Current() const { return instruction_->InputAt(index_); } 312 void Advance() { index_++; } 313 314 private: 315 HInstruction* instruction_; 316 int index_; 317 318 DISALLOW_COPY_AND_ASSIGN(HInputIterator); 319}; 320 321class HInstructionIterator : public ValueObject { 322 public: 323 explicit HInstructionIterator(HBasicBlock* block) 324 : instruction_(block->GetFirstInstruction()) { 325 next_ = Done() ? nullptr : instruction_->GetNext(); 326 } 327 328 bool Done() const { return instruction_ == nullptr; } 329 HInstruction* Current() const { return instruction_; } 330 void Advance() { 331 instruction_ = next_; 332 next_ = Done() ? nullptr : instruction_->GetNext(); 333 } 334 335 private: 336 HInstruction* instruction_; 337 HInstruction* next_; 338}; 339 340// An embedded container with N elements of type T. Used (with partial 341// specialization for N=0) because embedded arrays cannot have size 0. 342template<typename T, intptr_t N> 343class EmbeddedArray { 344 public: 345 EmbeddedArray() : elements_() { } 346 347 intptr_t GetLength() const { return N; } 348 349 const T& operator[](intptr_t i) const { 350 DCHECK_LT(i, GetLength()); 351 return elements_[i]; 352 } 353 354 T& operator[](intptr_t i) { 355 DCHECK_LT(i, GetLength()); 356 return elements_[i]; 357 } 358 359 const T& At(intptr_t i) const { 360 return (*this)[i]; 361 } 362 363 void SetAt(intptr_t i, const T& val) { 364 (*this)[i] = val; 365 } 366 367 private: 368 T elements_[N]; 369}; 370 371template<typename T> 372class EmbeddedArray<T, 0> { 373 public: 374 intptr_t length() const { return 0; } 375 const T& operator[](intptr_t i) const { 376 LOG(FATAL) << "Unreachable"; 377 static T sentinel = 0; 378 return sentinel; 379 } 380 T& operator[](intptr_t i) { 381 LOG(FATAL) << "Unreachable"; 382 static T sentinel = 0; 383 return sentinel; 384 } 385}; 386 387template<intptr_t N> 388class HTemplateInstruction: public HInstruction { 389 public: 390 HTemplateInstruction<N>() : inputs_() { } 391 virtual ~HTemplateInstruction() { } 392 393 virtual intptr_t InputCount() const { return N; } 394 virtual HInstruction* InputAt(intptr_t i) const { return inputs_[i]; } 395 396 protected: 397 void SetRawInputAt(intptr_t i, HInstruction* instruction) { 398 inputs_[i] = instruction; 399 } 400 401 private: 402 EmbeddedArray<HInstruction*, N> inputs_; 403}; 404 405// Represents dex's RETURN_VOID opcode. A HReturnVoid is a control flow 406// instruction that branches to the exit block. 407class HReturnVoid : public HTemplateInstruction<0> { 408 public: 409 HReturnVoid() { } 410 411 DECLARE_INSTRUCTION(ReturnVoid) 412 413 private: 414 DISALLOW_COPY_AND_ASSIGN(HReturnVoid); 415}; 416 417// Represents dex's RETURN opcodes. A HReturn is a control flow 418// instruction that branches to the exit block. 419class HReturn : public HTemplateInstruction<1> { 420 public: 421 explicit HReturn(HInstruction* value) { 422 SetRawInputAt(0, value); 423 } 424 425 DECLARE_INSTRUCTION(Return) 426 427 private: 428 DISALLOW_COPY_AND_ASSIGN(HReturn); 429}; 430 431// The exit instruction is the only instruction of the exit block. 432// Instructions aborting the method (HTrow and HReturn) must branch to the 433// exit block. 434class HExit : public HTemplateInstruction<0> { 435 public: 436 HExit() { } 437 438 DECLARE_INSTRUCTION(Exit) 439 440 private: 441 DISALLOW_COPY_AND_ASSIGN(HExit); 442}; 443 444// Jumps from one block to another. 445class HGoto : public HTemplateInstruction<0> { 446 public: 447 HGoto() { } 448 449 HBasicBlock* GetSuccessor() const { 450 return GetBlock()->GetSuccessors()->Get(0); 451 } 452 453 DECLARE_INSTRUCTION(Goto) 454 455 private: 456 DISALLOW_COPY_AND_ASSIGN(HGoto); 457}; 458 459// Conditional branch. A block ending with an HIf instruction must have 460// two successors. 461class HIf : public HTemplateInstruction<1> { 462 public: 463 explicit HIf(HInstruction* input) { 464 SetRawInputAt(0, input); 465 } 466 467 HBasicBlock* IfTrueSuccessor() const { 468 return GetBlock()->GetSuccessors()->Get(0); 469 } 470 471 HBasicBlock* IfFalseSuccessor() const { 472 return GetBlock()->GetSuccessors()->Get(1); 473 } 474 475 DECLARE_INSTRUCTION(If) 476 477 private: 478 DISALLOW_COPY_AND_ASSIGN(HIf); 479}; 480 481class HBinaryOperation : public HTemplateInstruction<2> { 482 public: 483 HBinaryOperation(Primitive::Type result_type, 484 HInstruction* left, 485 HInstruction* right) : result_type_(result_type) { 486 SetRawInputAt(0, left); 487 SetRawInputAt(1, right); 488 } 489 490 HInstruction* GetLeft() const { return InputAt(0); } 491 HInstruction* GetRight() const { return InputAt(1); } 492 Primitive::Type GetResultType() const { return result_type_; } 493 494 virtual bool IsCommutative() { return false; } 495 496 private: 497 const Primitive::Type result_type_; 498 499 DISALLOW_COPY_AND_ASSIGN(HBinaryOperation); 500}; 501 502 503// Instruction to check if two inputs are equal to each other. 504class HEqual : public HBinaryOperation { 505 public: 506 HEqual(HInstruction* first, HInstruction* second) 507 : HBinaryOperation(Primitive::kPrimBoolean, first, second) {} 508 509 virtual bool IsCommutative() { return true; } 510 511 DECLARE_INSTRUCTION(Equal) 512 513 private: 514 DISALLOW_COPY_AND_ASSIGN(HEqual); 515}; 516 517// A local in the graph. Corresponds to a Dex register. 518class HLocal : public HTemplateInstruction<0> { 519 public: 520 explicit HLocal(uint16_t reg_number) : reg_number_(reg_number) { } 521 522 DECLARE_INSTRUCTION(Local) 523 524 uint16_t GetRegNumber() const { return reg_number_; } 525 526 private: 527 // The Dex register number. 528 const uint16_t reg_number_; 529 530 DISALLOW_COPY_AND_ASSIGN(HLocal); 531}; 532 533// Load a given local. The local is an input of this instruction. 534class HLoadLocal : public HTemplateInstruction<1> { 535 public: 536 explicit HLoadLocal(HLocal* local) { 537 SetRawInputAt(0, local); 538 } 539 540 HLocal* GetLocal() const { return reinterpret_cast<HLocal*>(InputAt(0)); } 541 542 DECLARE_INSTRUCTION(LoadLocal) 543 544 private: 545 DISALLOW_COPY_AND_ASSIGN(HLoadLocal); 546}; 547 548// Store a value in a given local. This instruction has two inputs: the value 549// and the local. 550class HStoreLocal : public HTemplateInstruction<2> { 551 public: 552 HStoreLocal(HLocal* local, HInstruction* value) { 553 SetRawInputAt(0, local); 554 SetRawInputAt(1, value); 555 } 556 557 HLocal* GetLocal() const { return reinterpret_cast<HLocal*>(InputAt(0)); } 558 559 DECLARE_INSTRUCTION(StoreLocal) 560 561 private: 562 DISALLOW_COPY_AND_ASSIGN(HStoreLocal); 563}; 564 565// Constants of the type int. Those can be from Dex instructions, or 566// synthesized (for example with the if-eqz instruction). 567class HIntConstant : public HTemplateInstruction<0> { 568 public: 569 explicit HIntConstant(int32_t value) : value_(value) { } 570 571 int32_t GetValue() const { return value_; } 572 573 DECLARE_INSTRUCTION(IntConstant) 574 575 private: 576 const int32_t value_; 577 578 DISALLOW_COPY_AND_ASSIGN(HIntConstant); 579}; 580 581class HInvoke : public HInstruction { 582 public: 583 HInvoke(ArenaAllocator* arena, uint32_t number_of_arguments, int32_t dex_pc) 584 : inputs_(arena, number_of_arguments), 585 dex_pc_(dex_pc) { 586 inputs_.SetSize(number_of_arguments); 587 } 588 589 virtual intptr_t InputCount() const { return inputs_.Size(); } 590 virtual HInstruction* InputAt(intptr_t i) const { return inputs_.Get(i); } 591 592 int32_t GetDexPc() const { return dex_pc_; } 593 594 protected: 595 GrowableArray<HInstruction*> inputs_; 596 const int32_t dex_pc_; 597 598 private: 599 DISALLOW_COPY_AND_ASSIGN(HInvoke); 600}; 601 602class HInvokeStatic : public HInvoke { 603 public: 604 HInvokeStatic(ArenaAllocator* arena, uint32_t number_of_arguments, int32_t dex_pc, int32_t index_in_dex_cache) 605 : HInvoke(arena, number_of_arguments, dex_pc), index_in_dex_cache_(index_in_dex_cache) { } 606 607 uint32_t GetIndexInDexCache() const { return index_in_dex_cache_; } 608 609 DECLARE_INSTRUCTION(InvokeStatic) 610 611 private: 612 uint32_t index_in_dex_cache_; 613 614 DISALLOW_COPY_AND_ASSIGN(HInvokeStatic); 615}; 616 617class HAdd : public HBinaryOperation { 618 public: 619 HAdd(Primitive::Type result_type, HInstruction* left, HInstruction* right) 620 : HBinaryOperation(result_type, left, right) {} 621 622 virtual bool IsCommutative() { return true; } 623 624 DECLARE_INSTRUCTION(Add); 625 626 private: 627 DISALLOW_COPY_AND_ASSIGN(HAdd); 628}; 629 630class HGraphVisitor : public ValueObject { 631 public: 632 explicit HGraphVisitor(HGraph* graph) : graph_(graph) { } 633 virtual ~HGraphVisitor() { } 634 635 virtual void VisitInstruction(HInstruction* instruction) { } 636 virtual void VisitBasicBlock(HBasicBlock* block); 637 638 void VisitInsertionOrder(); 639 640 HGraph* GetGraph() const { return graph_; } 641 642 // Visit functions for instruction classes. 643#define DECLARE_VISIT_INSTRUCTION(name) \ 644 virtual void Visit##name(H##name* instr) { VisitInstruction(instr); } 645 646 FOR_EACH_INSTRUCTION(DECLARE_VISIT_INSTRUCTION) 647 648#undef DECLARE_VISIT_INSTRUCTION 649 650 private: 651 HGraph* graph_; 652 653 DISALLOW_COPY_AND_ASSIGN(HGraphVisitor); 654}; 655 656} // namespace art 657 658#endif // ART_COMPILER_OPTIMIZING_NODES_H_ 659