nodes.h revision 3ff386aafefd5282bb76c8a50506a70a4321e698
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; 30 31static const int kDefaultNumberOfBlocks = 8; 32static const int kDefaultNumberOfSuccessors = 2; 33static const int kDefaultNumberOfPredecessors = 2; 34static const int kDefaultNumberOfBackEdges = 1; 35 36// Control-flow graph of a method. Contains a list of basic blocks. 37class HGraph : public ArenaObject { 38 public: 39 explicit HGraph(ArenaAllocator* arena) 40 : arena_(arena), 41 blocks_(arena, kDefaultNumberOfBlocks), 42 dominator_order_(arena, kDefaultNumberOfBlocks), 43 current_instruction_id_(0) { } 44 45 ArenaAllocator* arena() const { return arena_; } 46 const GrowableArray<HBasicBlock*>* blocks() const { return &blocks_; } 47 48 HBasicBlock* entry_block() const { return entry_block_; } 49 HBasicBlock* exit_block() const { return exit_block_; } 50 51 void set_entry_block(HBasicBlock* block) { entry_block_ = block; } 52 void set_exit_block(HBasicBlock* block) { exit_block_ = block; } 53 54 void AddBlock(HBasicBlock* block); 55 void BuildDominatorTree(); 56 57 int GetNextInstructionId() { 58 return current_instruction_id_++; 59 } 60 61 private: 62 HBasicBlock* FindCommonDominator(HBasicBlock* first, HBasicBlock* second) const; 63 void VisitBlockForDominatorTree(HBasicBlock* block, 64 HBasicBlock* predecessor, 65 GrowableArray<size_t>* visits); 66 void FindBackEdges(ArenaBitVector* visited) const; 67 void VisitBlockForBackEdges(HBasicBlock* block, 68 ArenaBitVector* visited, 69 ArenaBitVector* visiting) const; 70 void RemoveDeadBlocks(const ArenaBitVector& visited) const; 71 72 ArenaAllocator* const arena_; 73 74 // List of blocks in insertion order. 75 GrowableArray<HBasicBlock*> blocks_; 76 77 // List of blocks to perform a pre-order dominator tree traversal. 78 GrowableArray<HBasicBlock*> dominator_order_; 79 80 HBasicBlock* entry_block_; 81 HBasicBlock* exit_block_; 82 83 // The current id to assign to a newly added instruction. See HInstruction.id_. 84 int current_instruction_id_; 85 86 DISALLOW_COPY_AND_ASSIGN(HGraph); 87}; 88 89class HLoopInformation : public ArenaObject { 90 public: 91 HLoopInformation(HBasicBlock* header, HGraph* graph) 92 : header_(header), 93 back_edges_(graph->arena(), kDefaultNumberOfBackEdges) { } 94 95 void AddBackEdge(HBasicBlock* back_edge) { 96 back_edges_.Add(back_edge); 97 } 98 99 int NumberOfBackEdges() const { 100 return back_edges_.Size(); 101 } 102 103 private: 104 HBasicBlock* header_; 105 GrowableArray<HBasicBlock*> back_edges_; 106 107 DISALLOW_COPY_AND_ASSIGN(HLoopInformation); 108}; 109 110// A block in a method. Contains the list of instructions represented 111// as a double linked list. Each block knows its predecessors and 112// successors. 113class HBasicBlock : public ArenaObject { 114 public: 115 explicit HBasicBlock(HGraph* graph) 116 : graph_(graph), 117 predecessors_(graph->arena(), kDefaultNumberOfPredecessors), 118 successors_(graph->arena(), kDefaultNumberOfSuccessors), 119 first_instruction_(nullptr), 120 last_instruction_(nullptr), 121 loop_information_(nullptr), 122 dominator_(nullptr), 123 block_id_(-1) { } 124 125 const GrowableArray<HBasicBlock*>* predecessors() const { 126 return &predecessors_; 127 } 128 129 const GrowableArray<HBasicBlock*>* successors() const { 130 return &successors_; 131 } 132 133 void AddBackEdge(HBasicBlock* back_edge) { 134 if (loop_information_ == nullptr) { 135 loop_information_ = new (graph_->arena()) HLoopInformation(this, graph_); 136 } 137 loop_information_->AddBackEdge(back_edge); 138 } 139 140 HGraph* graph() const { return graph_; } 141 142 int block_id() const { return block_id_; } 143 void set_block_id(int id) { block_id_ = id; } 144 145 HBasicBlock* dominator() const { return dominator_; } 146 void set_dominator(HBasicBlock* dominator) { dominator_ = dominator; } 147 148 int NumberOfBackEdges() const { 149 return loop_information_ == nullptr 150 ? 0 151 : loop_information_->NumberOfBackEdges(); 152 } 153 154 HInstruction* first_instruction() const { return first_instruction_; } 155 HInstruction* last_instruction() const { return last_instruction_; } 156 157 void AddSuccessor(HBasicBlock* block) { 158 successors_.Add(block); 159 block->predecessors_.Add(this); 160 } 161 162 void RemovePredecessor(HBasicBlock* block) { 163 predecessors_.Delete(block); 164 } 165 166 void AddInstruction(HInstruction* instruction); 167 168 private: 169 HGraph* const graph_; 170 GrowableArray<HBasicBlock*> predecessors_; 171 GrowableArray<HBasicBlock*> successors_; 172 HInstruction* first_instruction_; 173 HInstruction* last_instruction_; 174 HLoopInformation* loop_information_; 175 HBasicBlock* dominator_; 176 int block_id_; 177 178 DISALLOW_COPY_AND_ASSIGN(HBasicBlock); 179}; 180 181#define FOR_EACH_INSTRUCTION(M) \ 182 M(Equal) \ 183 M(Exit) \ 184 M(Goto) \ 185 M(If) \ 186 M(IntConstant) \ 187 M(LoadLocal) \ 188 M(Local) \ 189 M(ReturnVoid) \ 190 M(StoreLocal) \ 191 192#define DECLARE_INSTRUCTION(type) \ 193 virtual void Accept(HGraphVisitor* visitor); \ 194 virtual const char* DebugName() const { return #type; } \ 195 196class HUseListNode : public ArenaObject { 197 public: 198 HUseListNode(HInstruction* instruction, HUseListNode* tail) 199 : instruction_(instruction), tail_(tail) { } 200 201 HUseListNode* tail() const { return tail_; } 202 HInstruction* instruction() const { return instruction_; } 203 204 private: 205 HInstruction* const instruction_; 206 HUseListNode* const tail_; 207 208 DISALLOW_COPY_AND_ASSIGN(HUseListNode); 209}; 210 211class HInstruction : public ArenaObject { 212 public: 213 HInstruction() : previous_(nullptr), next_(nullptr), block_(nullptr), id_(-1), uses_(nullptr) { } 214 virtual ~HInstruction() { } 215 216 HInstruction* next() const { return next_; } 217 HInstruction* previous() const { return previous_; } 218 219 HBasicBlock* block() const { return block_; } 220 void set_block(HBasicBlock* block) { block_ = block; } 221 222 virtual intptr_t InputCount() const = 0; 223 virtual HInstruction* InputAt(intptr_t i) const = 0; 224 225 virtual void Accept(HGraphVisitor* visitor) = 0; 226 virtual const char* DebugName() const = 0; 227 228 void AddUse(HInstruction* user) { 229 uses_ = new (block_->graph()->arena()) HUseListNode(user, uses_); 230 } 231 232 HUseListNode* uses() const { return uses_; } 233 234 bool HasUses() const { return uses_ != nullptr; } 235 236 int id() const { return id_; } 237 void set_id(int id) { id_ = id; } 238 239 private: 240 HInstruction* previous_; 241 HInstruction* next_; 242 HBasicBlock* block_; 243 244 // An instruction gets an id when it is added to the graph. 245 // It reflects creation order. A negative id means the instruction 246 // has not beed added to the graph. 247 int id_; 248 249 HUseListNode* uses_; 250 251 friend class HBasicBlock; 252 253 DISALLOW_COPY_AND_ASSIGN(HInstruction); 254}; 255 256class HUseIterator : public ValueObject { 257 public: 258 explicit HUseIterator(HInstruction* instruction) : current_(instruction->uses()) { } 259 260 bool Done() const { return current_ == nullptr; } 261 262 void Advance() { 263 DCHECK(!Done()); 264 current_ = current_->tail(); 265 } 266 267 HInstruction* Current() const { 268 DCHECK(!Done()); 269 return current_->instruction(); 270 } 271 272 private: 273 HUseListNode* current_; 274 275 friend class HValue; 276}; 277 278class HInputIterator : public ValueObject { 279 public: 280 explicit HInputIterator(HInstruction* instruction) : instruction_(instruction), index_(0) { } 281 282 bool Done() const { return index_ == instruction_->InputCount(); } 283 HInstruction* Current() const { return instruction_->InputAt(index_); } 284 void Advance() { index_++; } 285 286 private: 287 HInstruction* instruction_; 288 int index_; 289 290 DISALLOW_COPY_AND_ASSIGN(HInputIterator); 291}; 292 293class HInstructionIterator : public ValueObject { 294 public: 295 explicit HInstructionIterator(HBasicBlock* block) 296 : instruction_(block->first_instruction()) { 297 next_ = Done() ? nullptr : instruction_->next(); 298 } 299 300 bool Done() const { return instruction_ == nullptr; } 301 HInstruction* Current() const { return instruction_; } 302 void Advance() { 303 instruction_ = next_; 304 next_ = Done() ? nullptr : instruction_->next(); 305 } 306 307 private: 308 HInstruction* instruction_; 309 HInstruction* next_; 310}; 311 312// An embedded container with N elements of type T. Used (with partial 313// specialization for N=0) because embedded arrays cannot have size 0. 314template<typename T, intptr_t N> 315class EmbeddedArray { 316 public: 317 EmbeddedArray() : elements_() { } 318 319 intptr_t length() const { return N; } 320 321 const T& operator[](intptr_t i) const { 322 DCHECK_LT(i, length()); 323 return elements_[i]; 324 } 325 326 T& operator[](intptr_t i) { 327 DCHECK_LT(i, length()); 328 return elements_[i]; 329 } 330 331 const T& At(intptr_t i) const { 332 return (*this)[i]; 333 } 334 335 void SetAt(intptr_t i, const T& val) { 336 (*this)[i] = val; 337 } 338 339 private: 340 T elements_[N]; 341}; 342 343template<typename T> 344class EmbeddedArray<T, 0> { 345 public: 346 intptr_t length() const { return 0; } 347 const T& operator[](intptr_t i) const { 348 LOG(FATAL) << "Unreachable"; 349 static T sentinel = 0; 350 return sentinel; 351 } 352 T& operator[](intptr_t i) { 353 LOG(FATAL) << "Unreachable"; 354 static T sentinel = 0; 355 return sentinel; 356 } 357}; 358 359template<intptr_t N> 360class HTemplateInstruction: public HInstruction { 361 public: 362 HTemplateInstruction<N>() : inputs_() { } 363 virtual ~HTemplateInstruction() { } 364 365 virtual intptr_t InputCount() const { return N; } 366 virtual HInstruction* InputAt(intptr_t i) const { return inputs_[i]; } 367 368 protected: 369 void SetRawInputAt(intptr_t i, HInstruction* instruction) { 370 inputs_[i] = instruction; 371 } 372 373 private: 374 EmbeddedArray<HInstruction*, N> inputs_; 375}; 376 377// Represents dex's RETURN_VOID opcode. A HReturnVoid is a control flow 378// instruction that branches to the exit block. 379class HReturnVoid : public HTemplateInstruction<0> { 380 public: 381 HReturnVoid() { } 382 383 DECLARE_INSTRUCTION(ReturnVoid) 384 385 private: 386 DISALLOW_COPY_AND_ASSIGN(HReturnVoid); 387}; 388 389// The exit instruction is the only instruction of the exit block. 390// Instructions aborting the method (HTrow and HReturn) must branch to the 391// exit block. 392class HExit : public HTemplateInstruction<0> { 393 public: 394 HExit() { } 395 396 DECLARE_INSTRUCTION(Exit) 397 398 private: 399 DISALLOW_COPY_AND_ASSIGN(HExit); 400}; 401 402// Jumps from one block to another. 403class HGoto : public HTemplateInstruction<0> { 404 public: 405 HGoto() { } 406 407 HBasicBlock* GetSuccessor() const { 408 return block()->successors()->Get(0); 409 } 410 411 DECLARE_INSTRUCTION(Goto) 412 413 private: 414 DISALLOW_COPY_AND_ASSIGN(HGoto); 415}; 416 417// Conditional branch. A block ending with an HIf instruction must have 418// two successors. 419class HIf : public HTemplateInstruction<1> { 420 public: 421 explicit HIf(HInstruction* input) { 422 SetRawInputAt(0, input); 423 } 424 425 DECLARE_INSTRUCTION(If) 426 427 private: 428 DISALLOW_COPY_AND_ASSIGN(HIf); 429}; 430 431// Instruction to check if two inputs are equal to each other. 432class HEqual : public HTemplateInstruction<2> { 433 public: 434 HEqual(HInstruction* first, HInstruction* second) { 435 SetRawInputAt(0, first); 436 SetRawInputAt(1, second); 437 } 438 439 DECLARE_INSTRUCTION(Equal) 440 441 private: 442 DISALLOW_COPY_AND_ASSIGN(HEqual); 443}; 444 445// A local in the graph. Corresponds to a Dex register. 446class HLocal : public HTemplateInstruction<0> { 447 public: 448 explicit HLocal(uint16_t reg_number) : reg_number_(reg_number) { } 449 450 DECLARE_INSTRUCTION(Local) 451 452 private: 453 // The register number in Dex. 454 uint16_t reg_number_; 455 456 DISALLOW_COPY_AND_ASSIGN(HLocal); 457}; 458 459// Load a given local. The local is an input of this instruction. 460class HLoadLocal : public HTemplateInstruction<1> { 461 public: 462 explicit HLoadLocal(HLocal* local) { 463 SetRawInputAt(0, local); 464 } 465 466 DECLARE_INSTRUCTION(LoadLocal) 467 468 private: 469 DISALLOW_COPY_AND_ASSIGN(HLoadLocal); 470}; 471 472// Store a value in a given local. This instruction has two inputs: the value 473// and the local. 474class HStoreLocal : public HTemplateInstruction<2> { 475 public: 476 HStoreLocal(HLocal* local, HInstruction* value) { 477 SetRawInputAt(0, local); 478 SetRawInputAt(1, value); 479 } 480 481 DECLARE_INSTRUCTION(StoreLocal) 482 483 private: 484 DISALLOW_COPY_AND_ASSIGN(HStoreLocal); 485}; 486 487// Constants of the type int. Those can be from Dex instructions, or 488// synthesized (for example with the if-eqz instruction). 489class HIntConstant : public HTemplateInstruction<0> { 490 public: 491 explicit HIntConstant(int32_t value) : value_(value) { } 492 493 DECLARE_INSTRUCTION(IntConstant) 494 495 private: 496 const int32_t value_; 497 498 DISALLOW_COPY_AND_ASSIGN(HIntConstant); 499}; 500 501class HGraphVisitor : public ValueObject { 502 public: 503 explicit HGraphVisitor(HGraph* graph) : graph_(graph) { } 504 virtual ~HGraphVisitor() { } 505 506 virtual void VisitInstruction(HInstruction* instruction) { } 507 virtual void VisitBasicBlock(HBasicBlock* block); 508 509 void VisitInsertionOrder(); 510 511 HGraph* graph() const { return graph_; } 512 513 // Visit functions for instruction classes. 514#define DECLARE_VISIT_INSTRUCTION(name) \ 515 virtual void Visit##name(H##name* instr) { VisitInstruction(instr); } 516 517 FOR_EACH_INSTRUCTION(DECLARE_VISIT_INSTRUCTION) 518 519#undef DECLARE_VISIT_INSTRUCTION 520 521 private: 522 HGraph* graph_; 523 524 DISALLOW_COPY_AND_ASSIGN(HGraphVisitor); 525}; 526 527} // namespace art 528 529#endif // ART_COMPILER_OPTIMIZING_NODES_H_ 530