Home | History | Annotate | Download | only in compiler 
      1 // Copyright 2013 the V8 project authors. All rights reserved.
      2 // Use of this source code is governed by a BSD-style license that can be
      3 // found in the LICENSE file.
      4 
      5 #ifndef V8_COMPILER_SCHEDULE_H_
      6 #define V8_COMPILER_SCHEDULE_H_
      7 
      8 #include <vector>
      9 
     10 #include "src/v8.h"
     11 
     12 #include "src/compiler/generic-algorithm.h"
     13 #include "src/compiler/generic-graph.h"
     14 #include "src/compiler/generic-node.h"
     15 #include "src/compiler/generic-node-inl.h"
     16 #include "src/compiler/node.h"
     17 #include "src/compiler/opcodes.h"
     18 #include "src/zone.h"
     19 
     20 namespace v8 {
     21 namespace internal {
     22 namespace compiler {
     23 
     24 class BasicBlock;
     25 class Graph;
     26 class ConstructScheduleData;
     27 class CodeGenerator;  // Because of a namespace bug in clang.
     28 
     29 class BasicBlockData {
     30  public:
     31   // Possible control nodes that can end a block.
     32   enum Control {
     33     kNone,    // Control not initialized yet.
     34     kGoto,    // Goto a single successor block.
     35     kBranch,  // Branch if true to first successor, otherwise second.
     36     kReturn,  // Return a value from this method.
     37     kThrow    // Throw an exception.
     38   };
     39 
     40   int32_t rpo_number_;       // special RPO number of the block.
     41   BasicBlock* dominator_;    // Immediate dominator of the block.
     42   BasicBlock* loop_header_;  // Pointer to dominating loop header basic block,
     43                              // NULL if none. For loop headers, this points to
     44                              // enclosing loop header.
     45   int32_t loop_depth_;       // loop nesting, 0 is top-level
     46   int32_t loop_end_;         // end of the loop, if this block is a loop header.
     47   int32_t code_start_;       // start index of arch-specific code.
     48   int32_t code_end_;         // end index of arch-specific code.
     49   bool deferred_;            // {true} if this block is considered the slow
     50                              // path.
     51   Control control_;          // Control at the end of the block.
     52   Node* control_input_;      // Input value for control.
     53   NodeVector nodes_;         // nodes of this block in forward order.
     54 
     55   explicit BasicBlockData(Zone* zone)
     56       : rpo_number_(-1),
     57         dominator_(NULL),
     58         loop_header_(NULL),
     59         loop_depth_(0),
     60         loop_end_(-1),
     61         code_start_(-1),
     62         code_end_(-1),
     63         deferred_(false),
     64         control_(kNone),
     65         control_input_(NULL),
     66         nodes_(zone) {}
     67 
     68   inline bool IsLoopHeader() const { return loop_end_ >= 0; }
     69   inline bool LoopContains(BasicBlockData* block) const {
     70     // RPO numbers must be initialized.
     71     DCHECK(rpo_number_ >= 0);
     72     DCHECK(block->rpo_number_ >= 0);
     73     if (loop_end_ < 0) return false;  // This is not a loop.
     74     return block->rpo_number_ >= rpo_number_ && block->rpo_number_ < loop_end_;
     75   }
     76   int first_instruction_index() {
     77     DCHECK(code_start_ >= 0);
     78     DCHECK(code_end_ > 0);
     79     DCHECK(code_end_ >= code_start_);
     80     return code_start_;
     81   }
     82   int last_instruction_index() {
     83     DCHECK(code_start_ >= 0);
     84     DCHECK(code_end_ > 0);
     85     DCHECK(code_end_ >= code_start_);
     86     return code_end_ - 1;
     87   }
     88 };
     89 
     90 OStream& operator<<(OStream& os, const BasicBlockData::Control& c);
     91 
     92 // A basic block contains an ordered list of nodes and ends with a control
     93 // node. Note that if a basic block has phis, then all phis must appear as the
     94 // first nodes in the block.
     95 class BasicBlock FINAL : public GenericNode<BasicBlockData, BasicBlock> {
     96  public:
     97   BasicBlock(GenericGraphBase* graph, int input_count)
     98       : GenericNode<BasicBlockData, BasicBlock>(graph, input_count) {}
     99 
    100   typedef Uses Successors;
    101   typedef Inputs Predecessors;
    102 
    103   Successors successors() { return static_cast<Successors>(uses()); }
    104   Predecessors predecessors() { return static_cast<Predecessors>(inputs()); }
    105 
    106   int PredecessorCount() { return InputCount(); }
    107   BasicBlock* PredecessorAt(int index) { return InputAt(index); }
    108 
    109   int SuccessorCount() { return UseCount(); }
    110   BasicBlock* SuccessorAt(int index) { return UseAt(index); }
    111 
    112   int PredecessorIndexOf(BasicBlock* predecessor) {
    113     BasicBlock::Predecessors predecessors = this->predecessors();
    114     for (BasicBlock::Predecessors::iterator i = predecessors.begin();
    115          i != predecessors.end(); ++i) {
    116       if (*i == predecessor) return i.index();
    117     }
    118     return -1;
    119   }
    120 
    121   inline BasicBlock* loop_header() {
    122     return static_cast<BasicBlock*>(loop_header_);
    123   }
    124   inline BasicBlock* ContainingLoop() {
    125     if (IsLoopHeader()) return this;
    126     return static_cast<BasicBlock*>(loop_header_);
    127   }
    128 
    129   typedef NodeVector::iterator iterator;
    130   iterator begin() { return nodes_.begin(); }
    131   iterator end() { return nodes_.end(); }
    132 
    133   typedef NodeVector::const_iterator const_iterator;
    134   const_iterator begin() const { return nodes_.begin(); }
    135   const_iterator end() const { return nodes_.end(); }
    136 
    137   typedef NodeVector::reverse_iterator reverse_iterator;
    138   reverse_iterator rbegin() { return nodes_.rbegin(); }
    139   reverse_iterator rend() { return nodes_.rend(); }
    140 
    141  private:
    142   DISALLOW_COPY_AND_ASSIGN(BasicBlock);
    143 };
    144 
    145 typedef GenericGraphVisit::NullNodeVisitor<BasicBlockData, BasicBlock>
    146     NullBasicBlockVisitor;
    147 
    148 typedef ZoneVector<BasicBlock*> BasicBlockVector;
    149 typedef BasicBlockVector::iterator BasicBlockVectorIter;
    150 typedef BasicBlockVector::reverse_iterator BasicBlockVectorRIter;
    151 
    152 // A schedule represents the result of assigning nodes to basic blocks
    153 // and ordering them within basic blocks. Prior to computing a schedule,
    154 // a graph has no notion of control flow ordering other than that induced
    155 // by the graph's dependencies. A schedule is required to generate code.
    156 class Schedule : public GenericGraph<BasicBlock> {
    157  public:
    158   explicit Schedule(Zone* zone)
    159       : GenericGraph<BasicBlock>(zone),
    160         zone_(zone),
    161         all_blocks_(zone),
    162         nodeid_to_block_(zone),
    163         rpo_order_(zone) {
    164     SetStart(NewBasicBlock());  // entry.
    165     SetEnd(NewBasicBlock());    // exit.
    166   }
    167 
    168   // Return the block which contains {node}, if any.
    169   BasicBlock* block(Node* node) const {
    170     if (node->id() < static_cast<NodeId>(nodeid_to_block_.size())) {
    171       return nodeid_to_block_[node->id()];
    172     }
    173     return NULL;
    174   }
    175 
    176   bool IsScheduled(Node* node) {
    177     int length = static_cast<int>(nodeid_to_block_.size());
    178     if (node->id() >= length) return false;
    179     return nodeid_to_block_[node->id()] != NULL;
    180   }
    181 
    182   BasicBlock* GetBlockById(int block_id) { return all_blocks_[block_id]; }
    183 
    184   int BasicBlockCount() const { return NodeCount(); }
    185   int RpoBlockCount() const { return static_cast<int>(rpo_order_.size()); }
    186 
    187   typedef ContainerPointerWrapper<BasicBlockVector> BasicBlocks;
    188 
    189   // Return a list of all the blocks in the schedule, in arbitrary order.
    190   BasicBlocks all_blocks() { return BasicBlocks(&all_blocks_); }
    191 
    192   // Check if nodes {a} and {b} are in the same block.
    193   inline bool SameBasicBlock(Node* a, Node* b) const {
    194     BasicBlock* block = this->block(a);
    195     return block != NULL && block == this->block(b);
    196   }
    197 
    198   // BasicBlock building: create a new block.
    199   inline BasicBlock* NewBasicBlock() {
    200     BasicBlock* block =
    201         BasicBlock::New(this, 0, static_cast<BasicBlock**>(NULL));
    202     all_blocks_.push_back(block);
    203     return block;
    204   }
    205 
    206   // BasicBlock building: records that a node will later be added to a block but
    207   // doesn't actually add the node to the block.
    208   inline void PlanNode(BasicBlock* block, Node* node) {
    209     if (FLAG_trace_turbo_scheduler) {
    210       PrintF("Planning #%d:%s for future add to B%d\n", node->id(),
    211              node->op()->mnemonic(), block->id());
    212     }
    213     DCHECK(this->block(node) == NULL);
    214     SetBlockForNode(block, node);
    215   }
    216 
    217   // BasicBlock building: add a node to the end of the block.
    218   inline void AddNode(BasicBlock* block, Node* node) {
    219     if (FLAG_trace_turbo_scheduler) {
    220       PrintF("Adding #%d:%s to B%d\n", node->id(), node->op()->mnemonic(),
    221              block->id());
    222     }
    223     DCHECK(this->block(node) == NULL || this->block(node) == block);
    224     block->nodes_.push_back(node);
    225     SetBlockForNode(block, node);
    226   }
    227 
    228   // BasicBlock building: add a goto to the end of {block}.
    229   void AddGoto(BasicBlock* block, BasicBlock* succ) {
    230     DCHECK(block->control_ == BasicBlock::kNone);
    231     block->control_ = BasicBlock::kGoto;
    232     AddSuccessor(block, succ);
    233   }
    234 
    235   // BasicBlock building: add a branch at the end of {block}.
    236   void AddBranch(BasicBlock* block, Node* branch, BasicBlock* tblock,
    237                  BasicBlock* fblock) {
    238     DCHECK(block->control_ == BasicBlock::kNone);
    239     DCHECK(branch->opcode() == IrOpcode::kBranch);
    240     block->control_ = BasicBlock::kBranch;
    241     AddSuccessor(block, tblock);
    242     AddSuccessor(block, fblock);
    243     SetControlInput(block, branch);
    244     if (branch->opcode() == IrOpcode::kBranch) {
    245       // TODO(titzer): require a Branch node here. (sloppy tests).
    246       SetBlockForNode(block, branch);
    247     }
    248   }
    249 
    250   // BasicBlock building: add a return at the end of {block}.
    251   void AddReturn(BasicBlock* block, Node* input) {
    252     DCHECK(block->control_ == BasicBlock::kNone);
    253     block->control_ = BasicBlock::kReturn;
    254     SetControlInput(block, input);
    255     if (block != end()) AddSuccessor(block, end());
    256     if (input->opcode() == IrOpcode::kReturn) {
    257       // TODO(titzer): require a Return node here. (sloppy tests).
    258       SetBlockForNode(block, input);
    259     }
    260   }
    261 
    262   // BasicBlock building: add a throw at the end of {block}.
    263   void AddThrow(BasicBlock* block, Node* input) {
    264     DCHECK(block->control_ == BasicBlock::kNone);
    265     block->control_ = BasicBlock::kThrow;
    266     SetControlInput(block, input);
    267     if (block != end()) AddSuccessor(block, end());
    268   }
    269 
    270   friend class Scheduler;
    271   friend class CodeGenerator;
    272 
    273   void AddSuccessor(BasicBlock* block, BasicBlock* succ) {
    274     succ->AppendInput(zone_, block);
    275   }
    276 
    277   BasicBlockVector* rpo_order() { return &rpo_order_; }
    278 
    279  private:
    280   friend class ScheduleVisualizer;
    281 
    282   void SetControlInput(BasicBlock* block, Node* node) {
    283     block->control_input_ = node;
    284     SetBlockForNode(block, node);
    285   }
    286 
    287   void SetBlockForNode(BasicBlock* block, Node* node) {
    288     int length = static_cast<int>(nodeid_to_block_.size());
    289     if (node->id() >= length) {
    290       nodeid_to_block_.resize(node->id() + 1);
    291     }
    292     nodeid_to_block_[node->id()] = block;
    293   }
    294 
    295   Zone* zone_;
    296   BasicBlockVector all_blocks_;           // All basic blocks in the schedule.
    297   BasicBlockVector nodeid_to_block_;      // Map from node to containing block.
    298   BasicBlockVector rpo_order_;            // Reverse-post-order block list.
    299 };
    300 
    301 OStream& operator<<(OStream& os, const Schedule& s);
    302 }
    303 }
    304 }  // namespace v8::internal::compiler
    305 
    306 #endif  // V8_COMPILER_SCHEDULE_H_
    307