LCOV - code coverage report
Current view: top level - src/compiler - schedule.h (source / functions) Hit Total Coverage
Test: app.info Lines: 17 17 100.0 %
Date: 2017-04-26 Functions: 0 0 -

          Line data    Source code
       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 <iosfwd>
       9             : 
      10             : #include "src/base/compiler-specific.h"
      11             : #include "src/globals.h"
      12             : #include "src/zone/zone-containers.h"
      13             : 
      14             : namespace v8 {
      15             : namespace internal {
      16             : namespace compiler {
      17             : 
      18             : // Forward declarations.
      19             : class BasicBlock;
      20             : class BasicBlockInstrumentor;
      21             : class Node;
      22             : 
      23             : typedef ZoneVector<BasicBlock*> BasicBlockVector;
      24             : typedef ZoneVector<Node*> NodeVector;
      25             : 
      26             : // A basic block contains an ordered list of nodes and ends with a control
      27             : // node. Note that if a basic block has phis, then all phis must appear as the
      28             : // first nodes in the block.
      29             : class V8_EXPORT_PRIVATE BasicBlock final
      30             :     : public NON_EXPORTED_BASE(ZoneObject) {
      31             :  public:
      32             :   // Possible control nodes that can end a block.
      33             :   enum Control {
      34             :     kNone,        // Control not initialized yet.
      35             :     kGoto,        // Goto a single successor block.
      36             :     kCall,        // Call with continuation as first successor, exception
      37             :                   // second.
      38             :     kBranch,      // Branch if true to first successor, otherwise second.
      39             :     kSwitch,      // Table dispatch to one of the successor blocks.
      40             :     kDeoptimize,  // Return a value from this method.
      41             :     kTailCall,    // Tail call another method from this method.
      42             :     kReturn,      // Return a value from this method.
      43             :     kThrow        // Throw an exception.
      44             :   };
      45             : 
      46             :   class Id {
      47             :    public:
      48     6060269 :     int ToInt() const { return static_cast<int>(index_); }
      49    12870449 :     size_t ToSize() const { return index_; }
      50             :     static Id FromSize(size_t index) { return Id(index); }
      51    12869800 :     static Id FromInt(int index) { return Id(static_cast<size_t>(index)); }
      52             : 
      53             :    private:
      54             :     explicit Id(size_t index) : index_(index) {}
      55             :     size_t index_;
      56             :   };
      57             : 
      58             :   BasicBlock(Zone* zone, Id id);
      59             : 
      60             :   Id id() const { return id_; }
      61             : #if DEBUG
      62             :   void set_debug_info(AssemblerDebugInfo debug_info) {
      63             :     debug_info_ = debug_info;
      64             :   }
      65             :   AssemblerDebugInfo debug_info() const { return debug_info_; }
      66             : #endif  // DEBUG
      67             : 
      68             :   // Predecessors.
      69             :   BasicBlockVector& predecessors() { return predecessors_; }
      70             :   const BasicBlockVector& predecessors() const { return predecessors_; }
      71    37834094 :   size_t PredecessorCount() const { return predecessors_.size(); }
      72    27184066 :   BasicBlock* PredecessorAt(size_t index) { return predecessors_[index]; }
      73             :   void ClearPredecessors() { predecessors_.clear(); }
      74             :   void AddPredecessor(BasicBlock* predecessor);
      75             : 
      76             :   // Successors.
      77             :   BasicBlockVector& successors() { return successors_; }
      78             :   const BasicBlockVector& successors() const { return successors_; }
      79    85909550 :   size_t SuccessorCount() const { return successors_.size(); }
      80    66216574 :   BasicBlock* SuccessorAt(size_t index) { return successors_[index]; }
      81             :   void ClearSuccessors() { successors_.clear(); }
      82             :   void AddSuccessor(BasicBlock* successor);
      83             : 
      84             :   // Nodes in the basic block.
      85             :   typedef Node* value_type;
      86             :   bool empty() const { return nodes_.empty(); }
      87             :   size_t size() const { return nodes_.size(); }
      88    42014010 :   Node* NodeAt(size_t index) { return nodes_[index]; }
      89    39049120 :   size_t NodeCount() const { return nodes_.size(); }
      90             : 
      91             :   value_type& front() { return nodes_.front(); }
      92             :   value_type const& front() const { return nodes_.front(); }
      93             : 
      94             :   typedef NodeVector::iterator iterator;
      95             :   iterator begin() { return nodes_.begin(); }
      96             :   iterator end() { return nodes_.end(); }
      97             : 
      98             :   typedef NodeVector::const_iterator const_iterator;
      99             :   const_iterator begin() const { return nodes_.begin(); }
     100             :   const_iterator end() const { return nodes_.end(); }
     101             : 
     102             :   typedef NodeVector::reverse_iterator reverse_iterator;
     103             :   reverse_iterator rbegin() { return nodes_.rbegin(); }
     104             :   reverse_iterator rend() { return nodes_.rend(); }
     105             : 
     106             :   void AddNode(Node* node);
     107             :   template <class InputIterator>
     108             :   void InsertNodes(iterator insertion_point, InputIterator insertion_start,
     109             :                    InputIterator insertion_end) {
     110          56 :     nodes_.insert(insertion_point, insertion_start, insertion_end);
     111             :   }
     112             : 
     113             :   // Accessors.
     114             :   Control control() const { return control_; }
     115             :   void set_control(Control control);
     116             : 
     117             :   Node* control_input() const { return control_input_; }
     118             :   void set_control_input(Node* control_input);
     119             : 
     120             :   bool deferred() const { return deferred_; }
     121    28983111 :   void set_deferred(bool deferred) { deferred_ = deferred; }
     122             : 
     123             :   int32_t dominator_depth() const { return dominator_depth_; }
     124    38167585 :   void set_dominator_depth(int32_t depth) { dominator_depth_ = depth; }
     125             : 
     126             :   BasicBlock* dominator() const { return dominator_; }
     127    37204117 :   void set_dominator(BasicBlock* dominator) { dominator_ = dominator; }
     128             : 
     129             :   BasicBlock* rpo_next() const { return rpo_next_; }
     130    22449005 :   void set_rpo_next(BasicBlock* rpo_next) { rpo_next_ = rpo_next; }
     131             : 
     132             :   BasicBlock* loop_header() const { return loop_header_; }
     133             :   void set_loop_header(BasicBlock* loop_header);
     134             : 
     135             :   BasicBlock* loop_end() const { return loop_end_; }
     136             :   void set_loop_end(BasicBlock* loop_end);
     137             : 
     138             :   int32_t loop_depth() const { return loop_depth_; }
     139             :   void set_loop_depth(int32_t loop_depth);
     140             : 
     141             :   int32_t loop_number() const { return loop_number_; }
     142      147231 :   void set_loop_number(int32_t loop_number) { loop_number_ = loop_number; }
     143             : 
     144             :   int32_t rpo_number() const { return rpo_number_; }
     145             :   void set_rpo_number(int32_t rpo_number);
     146             : 
     147             :   // Loop membership helpers.
     148             :   inline bool IsLoopHeader() const { return loop_end_ != nullptr; }
     149             :   bool LoopContains(BasicBlock* block) const;
     150             : 
     151             :   // Computes the immediate common dominator of {b1} and {b2}. The worst time
     152             :   // complexity is O(N) where N is the height of the dominator tree.
     153             :   static BasicBlock* GetCommonDominator(BasicBlock* b1, BasicBlock* b2);
     154             : 
     155             :  private:
     156             :   int32_t loop_number_;      // loop number of the block.
     157             :   int32_t rpo_number_;       // special RPO number of the block.
     158             :   bool deferred_;            // true if the block contains deferred code.
     159             :   int32_t dominator_depth_;  // Depth within the dominator tree.
     160             :   BasicBlock* dominator_;    // Immediate dominator of the block.
     161             :   BasicBlock* rpo_next_;     // Link to next block in special RPO order.
     162             :   BasicBlock* loop_header_;  // Pointer to dominating loop header basic block,
     163             :   // nullptr if none. For loop headers, this points to
     164             :   // enclosing loop header.
     165             :   BasicBlock* loop_end_;     // end of the loop, if this block is a loop header.
     166             :   int32_t loop_depth_;       // loop nesting, 0 is top-level
     167             : 
     168             :   Control control_;          // Control at the end of the block.
     169             :   Node* control_input_;      // Input value for control.
     170             :   NodeVector nodes_;         // nodes of this block in forward order.
     171             : 
     172             :   BasicBlockVector successors_;
     173             :   BasicBlockVector predecessors_;
     174             : #if DEBUG
     175             :   AssemblerDebugInfo debug_info_;
     176             : #endif
     177             :   Id id_;
     178             : 
     179             :   DISALLOW_COPY_AND_ASSIGN(BasicBlock);
     180             : };
     181             : 
     182             : std::ostream& operator<<(std::ostream&, const BasicBlock&);
     183             : std::ostream& operator<<(std::ostream&, const BasicBlock::Control&);
     184             : std::ostream& operator<<(std::ostream&, const BasicBlock::Id&);
     185             : 
     186             : 
     187             : // A schedule represents the result of assigning nodes to basic blocks
     188             : // and ordering them within basic blocks. Prior to computing a schedule,
     189             : // a graph has no notion of control flow ordering other than that induced
     190             : // by the graph's dependencies. A schedule is required to generate code.
     191             : class V8_EXPORT_PRIVATE Schedule final : public NON_EXPORTED_BASE(ZoneObject) {
     192             :  public:
     193             :   explicit Schedule(Zone* zone, size_t node_count_hint = 0);
     194             : 
     195             :   // Return the block which contains {node}, if any.
     196             :   BasicBlock* block(Node* node) const;
     197             : 
     198             :   bool IsScheduled(Node* node);
     199             :   BasicBlock* GetBlockById(BasicBlock::Id block_id);
     200             : 
     201    18597642 :   size_t BasicBlockCount() const { return all_blocks_.size(); }
     202          28 :   size_t RpoBlockCount() const { return rpo_order_.size(); }
     203             : 
     204             :   // Check if nodes {a} and {b} are in the same block.
     205             :   bool SameBasicBlock(Node* a, Node* b) const;
     206             : 
     207             :   // BasicBlock building: create a new block.
     208             :   BasicBlock* NewBasicBlock();
     209             : 
     210             :   // BasicBlock building: records that a node will later be added to a block but
     211             :   // doesn't actually add the node to the block.
     212             :   void PlanNode(BasicBlock* block, Node* node);
     213             : 
     214             :   // BasicBlock building: add a node to the end of the block.
     215             :   void AddNode(BasicBlock* block, Node* node);
     216             : 
     217             :   // BasicBlock building: add a goto to the end of {block}.
     218             :   void AddGoto(BasicBlock* block, BasicBlock* succ);
     219             : 
     220             :   // BasicBlock building: add a call at the end of {block}.
     221             :   void AddCall(BasicBlock* block, Node* call, BasicBlock* success_block,
     222             :                BasicBlock* exception_block);
     223             : 
     224             :   // BasicBlock building: add a branch at the end of {block}.
     225             :   void AddBranch(BasicBlock* block, Node* branch, BasicBlock* tblock,
     226             :                  BasicBlock* fblock);
     227             : 
     228             :   // BasicBlock building: add a switch at the end of {block}.
     229             :   void AddSwitch(BasicBlock* block, Node* sw, BasicBlock** succ_blocks,
     230             :                  size_t succ_count);
     231             : 
     232             :   // BasicBlock building: add a deoptimize at the end of {block}.
     233             :   void AddDeoptimize(BasicBlock* block, Node* input);
     234             : 
     235             :   // BasicBlock building: add a tailcall at the end of {block}.
     236             :   void AddTailCall(BasicBlock* block, Node* input);
     237             : 
     238             :   // BasicBlock building: add a return at the end of {block}.
     239             :   void AddReturn(BasicBlock* block, Node* input);
     240             : 
     241             :   // BasicBlock building: add a throw at the end of {block}.
     242             :   void AddThrow(BasicBlock* block, Node* input);
     243             : 
     244             :   // BasicBlock mutation: insert a branch into the end of {block}.
     245             :   void InsertBranch(BasicBlock* block, BasicBlock* end, Node* branch,
     246             :                     BasicBlock* tblock, BasicBlock* fblock);
     247             : 
     248             :   // BasicBlock mutation: insert a switch into the end of {block}.
     249             :   void InsertSwitch(BasicBlock* block, BasicBlock* end, Node* sw,
     250             :                     BasicBlock** succ_blocks, size_t succ_count);
     251             : 
     252             :   // Exposed publicly for testing only.
     253             :   void AddSuccessorForTesting(BasicBlock* block, BasicBlock* succ) {
     254             :     return AddSuccessor(block, succ);
     255             :   }
     256             : 
     257             :   const BasicBlockVector* all_blocks() const { return &all_blocks_; }
     258             :   BasicBlockVector* rpo_order() { return &rpo_order_; }
     259             :   const BasicBlockVector* rpo_order() const { return &rpo_order_; }
     260             : 
     261             :   BasicBlock* start() { return start_; }
     262             :   BasicBlock* end() { return end_; }
     263             : 
     264             :   Zone* zone() const { return zone_; }
     265             : 
     266             :  private:
     267             :   friend class Scheduler;
     268             :   friend class BasicBlockInstrumentor;
     269             :   friend class RawMachineAssembler;
     270             : 
     271             :   // Ensure properties of the CFG assumed by further stages.
     272             :   void EnsureCFGWellFormedness();
     273             :   // Ensure split-edge form for a hand-assembled schedule.
     274             :   void EnsureSplitEdgeForm(BasicBlock* block);
     275             :   // Ensure entry into a deferred block happens from a single hot block.
     276             :   void EnsureDeferredCodeSingleEntryPoint(BasicBlock* block);
     277             :   // Copy deferred block markers down as far as possible
     278             :   void PropagateDeferredMark();
     279             : 
     280             :   void AddSuccessor(BasicBlock* block, BasicBlock* succ);
     281             :   void MoveSuccessors(BasicBlock* from, BasicBlock* to);
     282             : 
     283             :   void SetControlInput(BasicBlock* block, Node* node);
     284             :   void SetBlockForNode(BasicBlock* block, Node* node);
     285             : 
     286             :   Zone* zone_;
     287             :   BasicBlockVector all_blocks_;           // All basic blocks in the schedule.
     288             :   BasicBlockVector nodeid_to_block_;      // Map from node to containing block.
     289             :   BasicBlockVector rpo_order_;            // Reverse-post-order block list.
     290             :   BasicBlock* start_;
     291             :   BasicBlock* end_;
     292             : 
     293             :   DISALLOW_COPY_AND_ASSIGN(Schedule);
     294             : };
     295             : 
     296             : V8_EXPORT_PRIVATE std::ostream& operator<<(std::ostream&, const Schedule&);
     297             : 
     298             : }  // namespace compiler
     299             : }  // namespace internal
     300             : }  // namespace v8
     301             : 
     302             : #endif  // V8_COMPILER_SCHEDULE_H_

Generated by: LCOV version 1.10