| // Copyright (c) 2018, the Dart project authors. Please see the AUTHORS file |
| // for details. All rights reserved. Use of this source code is governed by a |
| // BSD-style license that can be found in the LICENSE file. |
| |
| #ifndef RUNTIME_VM_COMPILER_BACKEND_LOOPS_H_ |
| #define RUNTIME_VM_COMPILER_BACKEND_LOOPS_H_ |
| |
| #include "vm/allocation.h" |
| #include "vm/compiler/backend/il.h" |
| |
| namespace dart { |
| |
| // Information on a "natural loop" in the flow graph. |
| class LoopInfo : public ZoneAllocated { |
| public: |
| LoopInfo(intptr_t id, BlockEntryInstr* header, BitVector* blocks); |
| |
| // Merges given blocks to this loop. |
| void AddBlocks(BitVector* blocks); |
| |
| // Adds back edge to this loop. |
| void AddBackEdge(BlockEntryInstr* block); |
| |
| // Returns true if given block is backedge of this loop. |
| bool IsBackEdge(BlockEntryInstr* block) const; |
| |
| // Returns true if this loop is nested inside other loop. |
| bool IsIn(LoopInfo* other) const; |
| |
| // Returns the nesting depth of this loop. |
| intptr_t NestingDepth() const; |
| |
| // Getters. |
| intptr_t id() const { return id_; } |
| BlockEntryInstr* header() const { return header_; } |
| const GrowableArray<BlockEntryInstr*>& back_edges() { return back_edges_; } |
| BitVector* blocks() const { return blocks_; } |
| LoopInfo* outer() const { return outer_; } |
| LoopInfo* inner() const { return inner_; } |
| LoopInfo* next() const { return next_; } |
| |
| // For debugging. |
| const char* ToCString() const; |
| |
| private: |
| friend class LoopHierarchy; |
| |
| // Unique id of loop. We use its index in the |
| // loop header array for this. |
| const intptr_t id_; |
| |
| // Header of loop. |
| BlockEntryInstr* header_; |
| |
| // Compact represention of every block in the loop, |
| // indexed by its "preorder_number". |
| BitVector* blocks_; |
| |
| // Back edges of loop (usually one). |
| GrowableArray<BlockEntryInstr*> back_edges_; |
| |
| // Loop hierarchy. |
| LoopInfo* outer_; |
| LoopInfo* inner_; |
| LoopInfo* next_; |
| |
| DISALLOW_COPY_AND_ASSIGN(LoopInfo); |
| }; |
| |
| // Information on the loop hierarchy in the flow graph. |
| class LoopHierarchy : public ZoneAllocated { |
| public: |
| LoopHierarchy(ZoneGrowableArray<BlockEntryInstr*>* headers, |
| const GrowableArray<BlockEntryInstr*>& preorder); |
| |
| // Getters. |
| const ZoneGrowableArray<BlockEntryInstr*>& headers() const { |
| return *headers_; |
| } |
| LoopInfo* top() const { return top_; } |
| |
| // Returns total number of loops in the hierarchy. |
| intptr_t num_loops() const { return headers_->length(); } |
| |
| private: |
| void Build(); |
| void Print(LoopInfo* loop); |
| |
| ZoneGrowableArray<BlockEntryInstr*>* headers_; |
| const GrowableArray<BlockEntryInstr*>& preorder_; |
| LoopInfo* top_; |
| |
| DISALLOW_COPY_AND_ASSIGN(LoopHierarchy); |
| }; |
| |
| } // namespace dart |
| |
| #endif // RUNTIME_VM_COMPILER_BACKEND_LOOPS_H_ |