nodes.h revision bab4ed7057799a4fadc6283108ab56f389d117d4
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* arena() const { return arena_; } 47 const GrowableArray<HBasicBlock*>* blocks() const { return &blocks_; } 48 49 HBasicBlock* entry_block() const { return entry_block_; } 50 HBasicBlock* exit_block() const { return exit_block_; } 51 52 void set_entry_block(HBasicBlock* block) { entry_block_ = block; } 53 void set_exit_block(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->arena(), 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->arena(), kDefaultNumberOfPredecessors), 119 successors_(graph->arena(), 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*>* predecessors() const { 127 return &predecessors_; 128 } 129 130 const GrowableArray<HBasicBlock*>* successors() const { 131 return &successors_; 132 } 133 134 void AddBackEdge(HBasicBlock* back_edge) { 135 if (loop_information_ == nullptr) { 136 loop_information_ = new (graph_->arena()) HLoopInformation(this, graph_); 137 } 138 loop_information_->AddBackEdge(back_edge); 139 } 140 141 HGraph* graph() const { return graph_; } 142 143 int block_id() const { return block_id_; } 144 void set_block_id(int id) { block_id_ = id; } 145 146 HBasicBlock* dominator() const { return dominator_; } 147 void set_dominator(HBasicBlock* dominator) { dominator_ = dominator; } 148 149 int NumberOfBackEdges() const { 150 return loop_information_ == nullptr 151 ? 0 152 : loop_information_->NumberOfBackEdges(); 153 } 154 155 HInstruction* first_instruction() const { return first_instruction_; } 156 HInstruction* last_instruction() 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(Equal) \ 184 M(Exit) \ 185 M(Goto) \ 186 M(If) \ 187 M(IntConstant) \ 188 M(LoadLocal) \ 189 M(Local) \ 190 M(Return) \ 191 M(ReturnVoid) \ 192 M(StoreLocal) \ 193 194#define FORWARD_DECLARATION(type) class H##type; 195FOR_EACH_INSTRUCTION(FORWARD_DECLARATION) 196#undef FORWARD_DECLARATION 197 198#define DECLARE_INSTRUCTION(type) \ 199 virtual void Accept(HGraphVisitor* visitor); \ 200 virtual const char* DebugName() const { return #type; } \ 201 virtual H##type* As##type() { return this; } \ 202 203class HUseListNode : public ArenaObject { 204 public: 205 HUseListNode(HInstruction* instruction, HUseListNode* tail) 206 : instruction_(instruction), tail_(tail) { } 207 208 HUseListNode* tail() const { return tail_; } 209 HInstruction* instruction() const { return instruction_; } 210 211 private: 212 HInstruction* const instruction_; 213 HUseListNode* const tail_; 214 215 DISALLOW_COPY_AND_ASSIGN(HUseListNode); 216}; 217 218class HInstruction : public ArenaObject { 219 public: 220 HInstruction() 221 : previous_(nullptr), 222 next_(nullptr), 223 block_(nullptr), 224 id_(-1), 225 uses_(nullptr), 226 locations_(nullptr) { } 227 228 virtual ~HInstruction() { } 229 230 HInstruction* next() const { return next_; } 231 HInstruction* previous() const { return previous_; } 232 233 HBasicBlock* block() const { return block_; } 234 void set_block(HBasicBlock* block) { block_ = block; } 235 236 virtual intptr_t InputCount() const = 0; 237 virtual HInstruction* InputAt(intptr_t i) const = 0; 238 239 virtual void Accept(HGraphVisitor* visitor) = 0; 240 virtual const char* DebugName() const = 0; 241 242 void AddUse(HInstruction* user) { 243 uses_ = new (block_->graph()->arena()) HUseListNode(user, uses_); 244 } 245 246 HUseListNode* uses() const { return uses_; } 247 248 bool HasUses() const { return uses_ != nullptr; } 249 250 int id() const { return id_; } 251 void set_id(int id) { id_ = id; } 252 253 LocationSummary* locations() const { return locations_; } 254 void set_locations(LocationSummary* locations) { locations_ = locations; } 255 256#define INSTRUCTION_TYPE_CHECK(type) \ 257 virtual H##type* As##type() { return nullptr; } 258 259 FOR_EACH_INSTRUCTION(INSTRUCTION_TYPE_CHECK) 260#undef INSTRUCTION_TYPE_CHECK 261 262 private: 263 HInstruction* previous_; 264 HInstruction* next_; 265 HBasicBlock* block_; 266 267 // An instruction gets an id when it is added to the graph. 268 // It reflects creation order. A negative id means the instruction 269 // has not beed added to the graph. 270 int id_; 271 272 HUseListNode* uses_; 273 274 // Set by the code generator. 275 LocationSummary* locations_; 276 277 friend class HBasicBlock; 278 279 DISALLOW_COPY_AND_ASSIGN(HInstruction); 280}; 281 282class HUseIterator : public ValueObject { 283 public: 284 explicit HUseIterator(HInstruction* instruction) : current_(instruction->uses()) { } 285 286 bool Done() const { return current_ == nullptr; } 287 288 void Advance() { 289 DCHECK(!Done()); 290 current_ = current_->tail(); 291 } 292 293 HInstruction* Current() const { 294 DCHECK(!Done()); 295 return current_->instruction(); 296 } 297 298 private: 299 HUseListNode* current_; 300 301 friend class HValue; 302}; 303 304class HInputIterator : public ValueObject { 305 public: 306 explicit HInputIterator(HInstruction* instruction) : instruction_(instruction), index_(0) { } 307 308 bool Done() const { return index_ == instruction_->InputCount(); } 309 HInstruction* Current() const { return instruction_->InputAt(index_); } 310 void Advance() { index_++; } 311 312 private: 313 HInstruction* instruction_; 314 int index_; 315 316 DISALLOW_COPY_AND_ASSIGN(HInputIterator); 317}; 318 319class HInstructionIterator : public ValueObject { 320 public: 321 explicit HInstructionIterator(HBasicBlock* block) 322 : instruction_(block->first_instruction()) { 323 next_ = Done() ? nullptr : instruction_->next(); 324 } 325 326 bool Done() const { return instruction_ == nullptr; } 327 HInstruction* Current() const { return instruction_; } 328 void Advance() { 329 instruction_ = next_; 330 next_ = Done() ? nullptr : instruction_->next(); 331 } 332 333 private: 334 HInstruction* instruction_; 335 HInstruction* next_; 336}; 337 338// An embedded container with N elements of type T. Used (with partial 339// specialization for N=0) because embedded arrays cannot have size 0. 340template<typename T, intptr_t N> 341class EmbeddedArray { 342 public: 343 EmbeddedArray() : elements_() { } 344 345 intptr_t length() const { return N; } 346 347 const T& operator[](intptr_t i) const { 348 DCHECK_LT(i, length()); 349 return elements_[i]; 350 } 351 352 T& operator[](intptr_t i) { 353 DCHECK_LT(i, length()); 354 return elements_[i]; 355 } 356 357 const T& At(intptr_t i) const { 358 return (*this)[i]; 359 } 360 361 void SetAt(intptr_t i, const T& val) { 362 (*this)[i] = val; 363 } 364 365 private: 366 T elements_[N]; 367}; 368 369template<typename T> 370class EmbeddedArray<T, 0> { 371 public: 372 intptr_t length() const { return 0; } 373 const T& operator[](intptr_t i) const { 374 LOG(FATAL) << "Unreachable"; 375 static T sentinel = 0; 376 return sentinel; 377 } 378 T& operator[](intptr_t i) { 379 LOG(FATAL) << "Unreachable"; 380 static T sentinel = 0; 381 return sentinel; 382 } 383}; 384 385template<intptr_t N> 386class HTemplateInstruction: public HInstruction { 387 public: 388 HTemplateInstruction<N>() : inputs_() { } 389 virtual ~HTemplateInstruction() { } 390 391 virtual intptr_t InputCount() const { return N; } 392 virtual HInstruction* InputAt(intptr_t i) const { return inputs_[i]; } 393 394 protected: 395 void SetRawInputAt(intptr_t i, HInstruction* instruction) { 396 inputs_[i] = instruction; 397 } 398 399 private: 400 EmbeddedArray<HInstruction*, N> inputs_; 401}; 402 403// Represents dex's RETURN_VOID opcode. A HReturnVoid is a control flow 404// instruction that branches to the exit block. 405class HReturnVoid : public HTemplateInstruction<0> { 406 public: 407 HReturnVoid() { } 408 409 DECLARE_INSTRUCTION(ReturnVoid) 410 411 private: 412 DISALLOW_COPY_AND_ASSIGN(HReturnVoid); 413}; 414 415// Represents dex's RETURN opcodes. A HReturn is a control flow 416// instruction that branches to the exit block. 417class HReturn : public HTemplateInstruction<1> { 418 public: 419 explicit HReturn(HInstruction* value) { 420 SetRawInputAt(0, value); 421 } 422 423 DECLARE_INSTRUCTION(Return) 424 425 private: 426 DISALLOW_COPY_AND_ASSIGN(HReturn); 427}; 428 429// The exit instruction is the only instruction of the exit block. 430// Instructions aborting the method (HTrow and HReturn) must branch to the 431// exit block. 432class HExit : public HTemplateInstruction<0> { 433 public: 434 HExit() { } 435 436 DECLARE_INSTRUCTION(Exit) 437 438 private: 439 DISALLOW_COPY_AND_ASSIGN(HExit); 440}; 441 442// Jumps from one block to another. 443class HGoto : public HTemplateInstruction<0> { 444 public: 445 HGoto() { } 446 447 HBasicBlock* GetSuccessor() const { 448 return block()->successors()->Get(0); 449 } 450 451 DECLARE_INSTRUCTION(Goto) 452 453 private: 454 DISALLOW_COPY_AND_ASSIGN(HGoto); 455}; 456 457// Conditional branch. A block ending with an HIf instruction must have 458// two successors. 459class HIf : public HTemplateInstruction<1> { 460 public: 461 explicit HIf(HInstruction* input) { 462 SetRawInputAt(0, input); 463 } 464 465 HBasicBlock* IfTrueSuccessor() const { 466 return block()->successors()->Get(0); 467 } 468 469 HBasicBlock* IfFalseSuccessor() const { 470 return block()->successors()->Get(1); 471 } 472 473 DECLARE_INSTRUCTION(If) 474 475 private: 476 DISALLOW_COPY_AND_ASSIGN(HIf); 477}; 478 479// Instruction to check if two inputs are equal to each other. 480class HEqual : public HTemplateInstruction<2> { 481 public: 482 HEqual(HInstruction* first, HInstruction* second) { 483 SetRawInputAt(0, first); 484 SetRawInputAt(1, second); 485 } 486 487 DECLARE_INSTRUCTION(Equal) 488 489 private: 490 DISALLOW_COPY_AND_ASSIGN(HEqual); 491}; 492 493// A local in the graph. Corresponds to a Dex register. 494class HLocal : public HTemplateInstruction<0> { 495 public: 496 explicit HLocal(uint16_t reg_number) : reg_number_(reg_number) { } 497 498 DECLARE_INSTRUCTION(Local) 499 500 uint16_t reg_number() const { return reg_number_; } 501 502 private: 503 // The Dex register number. 504 const uint16_t reg_number_; 505 506 DISALLOW_COPY_AND_ASSIGN(HLocal); 507}; 508 509// Load a given local. The local is an input of this instruction. 510class HLoadLocal : public HTemplateInstruction<1> { 511 public: 512 explicit HLoadLocal(HLocal* local) { 513 SetRawInputAt(0, local); 514 } 515 516 HLocal* GetLocal() const { return reinterpret_cast<HLocal*>(InputAt(0)); } 517 518 DECLARE_INSTRUCTION(LoadLocal) 519 520 private: 521 DISALLOW_COPY_AND_ASSIGN(HLoadLocal); 522}; 523 524// Store a value in a given local. This instruction has two inputs: the value 525// and the local. 526class HStoreLocal : public HTemplateInstruction<2> { 527 public: 528 HStoreLocal(HLocal* local, HInstruction* value) { 529 SetRawInputAt(0, local); 530 SetRawInputAt(1, value); 531 } 532 533 HLocal* GetLocal() const { return reinterpret_cast<HLocal*>(InputAt(0)); } 534 535 DECLARE_INSTRUCTION(StoreLocal) 536 537 private: 538 DISALLOW_COPY_AND_ASSIGN(HStoreLocal); 539}; 540 541// Constants of the type int. Those can be from Dex instructions, or 542// synthesized (for example with the if-eqz instruction). 543class HIntConstant : public HTemplateInstruction<0> { 544 public: 545 explicit HIntConstant(int32_t value) : value_(value) { } 546 547 int32_t value() const { return value_; } 548 549 DECLARE_INSTRUCTION(IntConstant) 550 551 private: 552 const int32_t value_; 553 554 DISALLOW_COPY_AND_ASSIGN(HIntConstant); 555}; 556 557class HGraphVisitor : public ValueObject { 558 public: 559 explicit HGraphVisitor(HGraph* graph) : graph_(graph) { } 560 virtual ~HGraphVisitor() { } 561 562 virtual void VisitInstruction(HInstruction* instruction) { } 563 virtual void VisitBasicBlock(HBasicBlock* block); 564 565 void VisitInsertionOrder(); 566 567 HGraph* graph() const { return graph_; } 568 569 // Visit functions for instruction classes. 570#define DECLARE_VISIT_INSTRUCTION(name) \ 571 virtual void Visit##name(H##name* instr) { VisitInstruction(instr); } 572 573 FOR_EACH_INSTRUCTION(DECLARE_VISIT_INSTRUCTION) 574 575#undef DECLARE_VISIT_INSTRUCTION 576 577 private: 578 HGraph* graph_; 579 580 DISALLOW_COPY_AND_ASSIGN(HGraphVisitor); 581}; 582 583} // namespace art 584 585#endif // ART_COMPILER_OPTIMIZING_NODES_H_ 586