schedule.h 11.5 KB
Newer Older
1 2 3 4 5 6 7
// Copyright 2013 the V8 project authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#ifndef V8_COMPILER_SCHEDULE_H_
#define V8_COMPILER_SCHEDULE_H_

8
#include <iosfwd>
9

10 11
#include "src/base/compiler-specific.h"
#include "src/globals.h"
12
#include "src/zone/zone-containers.h"
13 14 15 16 17

namespace v8 {
namespace internal {
namespace compiler {

18
// Forward declarations.
19
class BasicBlock;
20
class BasicBlockInstrumentor;
21 22 23 24 25
class Node;

typedef ZoneVector<BasicBlock*> BasicBlockVector;
typedef ZoneVector<Node*> NodeVector;

26 27 28
// A basic block contains an ordered list of nodes and ends with a control
// node. Note that if a basic block has phis, then all phis must appear as the
// first nodes in the block.
29 30
class V8_EXPORT_PRIVATE BasicBlock final
    : public NON_EXPORTED_BASE(ZoneObject) {
31 32 33
 public:
  // Possible control nodes that can end a block.
  enum Control {
34 35 36 37 38 39 40
    kNone,        // Control not initialized yet.
    kGoto,        // Goto a single successor block.
    kCall,        // Call with continuation as first successor, exception
                  // second.
    kBranch,      // Branch if true to first successor, otherwise second.
    kSwitch,      // Table dispatch to one of the successor blocks.
    kDeoptimize,  // Return a value from this method.
41
    kTailCall,    // Tail call another method from this method.
42 43
    kReturn,      // Return a value from this method.
    kThrow        // Throw an exception.
44 45
  };

46 47 48 49 50 51
  class Id {
   public:
    int ToInt() const { return static_cast<int>(index_); }
    size_t ToSize() const { return index_; }
    static Id FromSize(size_t index) { return Id(index); }
    static Id FromInt(int index) { return Id(static_cast<size_t>(index)); }
52

53 54 55 56
   private:
    explicit Id(size_t index) : index_(index) {}
    size_t index_;
  };
57

58 59 60
  BasicBlock(Zone* zone, Id id);

  Id id() const { return id_; }
61 62 63 64 65 66
#if DEBUG
  void set_debug_info(AssemblerDebugInfo debug_info) {
    debug_info_ = debug_info;
  }
  AssemblerDebugInfo debug_info() const { return debug_info_; }
#endif  // DEBUG
67

68 69
  void Print();

70 71 72
  // Predecessors.
  BasicBlockVector& predecessors() { return predecessors_; }
  const BasicBlockVector& predecessors() const { return predecessors_; }
73 74
  size_t PredecessorCount() const { return predecessors_.size(); }
  BasicBlock* PredecessorAt(size_t index) { return predecessors_[index]; }
75
  void ClearPredecessors() { predecessors_.clear(); }
76
  void AddPredecessor(BasicBlock* predecessor);
77

78 79 80
  // Successors.
  BasicBlockVector& successors() { return successors_; }
  const BasicBlockVector& successors() const { return successors_; }
81 82
  size_t SuccessorCount() const { return successors_.size(); }
  BasicBlock* SuccessorAt(size_t index) { return successors_[index]; }
83
  void ClearSuccessors() { successors_.clear(); }
84
  void AddSuccessor(BasicBlock* successor);
85

86
  // Nodes in the basic block.
87 88 89
  typedef Node* value_type;
  bool empty() const { return nodes_.empty(); }
  size_t size() const { return nodes_.size(); }
90 91
  Node* NodeAt(size_t index) { return nodes_[index]; }
  size_t NodeCount() const { return nodes_.size(); }
92

93 94 95
  value_type& front() { return nodes_.front(); }
  value_type const& front() const { return nodes_.front(); }

96 97 98 99
  typedef NodeVector::iterator iterator;
  iterator begin() { return nodes_.begin(); }
  iterator end() { return nodes_.end(); }

100 101
  void RemoveNode(iterator it) { nodes_.erase(it); }

102 103 104 105 106 107 108 109
  typedef NodeVector::const_iterator const_iterator;
  const_iterator begin() const { return nodes_.begin(); }
  const_iterator end() const { return nodes_.end(); }

  typedef NodeVector::reverse_iterator reverse_iterator;
  reverse_iterator rbegin() { return nodes_.rbegin(); }
  reverse_iterator rend() { return nodes_.rend(); }

110 111 112 113 114 115 116 117 118 119 120 121 122 123
  void AddNode(Node* node);
  template <class InputIterator>
  void InsertNodes(iterator insertion_point, InputIterator insertion_start,
                   InputIterator insertion_end) {
    nodes_.insert(insertion_point, insertion_start, insertion_end);
  }

  // Accessors.
  Control control() const { return control_; }
  void set_control(Control control);

  Node* control_input() const { return control_input_; }
  void set_control_input(Node* control_input);

124 125 126
  bool deferred() const { return deferred_; }
  void set_deferred(bool deferred) { deferred_ = deferred; }

127
  int32_t dominator_depth() const { return dominator_depth_; }
128
  void set_dominator_depth(int32_t depth) { dominator_depth_ = depth; }
129

130
  BasicBlock* dominator() const { return dominator_; }
131
  void set_dominator(BasicBlock* dominator) { dominator_ = dominator; }
132

133 134 135
  BasicBlock* rpo_next() const { return rpo_next_; }
  void set_rpo_next(BasicBlock* rpo_next) { rpo_next_ = rpo_next; }

136 137 138
  BasicBlock* loop_header() const { return loop_header_; }
  void set_loop_header(BasicBlock* loop_header);

139 140 141
  BasicBlock* loop_end() const { return loop_end_; }
  void set_loop_end(BasicBlock* loop_end);

142 143 144
  int32_t loop_depth() const { return loop_depth_; }
  void set_loop_depth(int32_t loop_depth);

145 146
  int32_t loop_number() const { return loop_number_; }
  void set_loop_number(int32_t loop_number) { loop_number_ = loop_number; }
147

148 149 150 151
  int32_t rpo_number() const { return rpo_number_; }
  void set_rpo_number(int32_t rpo_number);

  // Loop membership helpers.
152
  inline bool IsLoopHeader() const { return loop_end_ != nullptr; }
153 154
  bool LoopContains(BasicBlock* block) const;

155 156 157 158
  // Computes the immediate common dominator of {b1} and {b2}. The worst time
  // complexity is O(N) where N is the height of the dominator tree.
  static BasicBlock* GetCommonDominator(BasicBlock* b1, BasicBlock* b2);

159
 private:
160
  int32_t loop_number_;      // loop number of the block.
161
  int32_t rpo_number_;       // special RPO number of the block.
162
  bool deferred_;            // true if the block contains deferred code.
163
  int32_t dominator_depth_;  // Depth within the dominator tree.
164
  BasicBlock* dominator_;    // Immediate dominator of the block.
165
  BasicBlock* rpo_next_;     // Link to next block in special RPO order.
166
  BasicBlock* loop_header_;  // Pointer to dominating loop header basic block,
167 168
  // nullptr if none. For loop headers, this points to
  // enclosing loop header.
169 170
  BasicBlock* loop_end_;  // end of the loop, if this block is a loop header.
  int32_t loop_depth_;    // loop nesting, 0 is top-level
171

172 173 174
  Control control_;      // Control at the end of the block.
  Node* control_input_;  // Input value for control.
  NodeVector nodes_;     // nodes of this block in forward order.
175

176 177
  BasicBlockVector successors_;
  BasicBlockVector predecessors_;
178 179 180
#if DEBUG
  AssemblerDebugInfo debug_info_;
#endif
181 182
  Id id_;

183 184 185
  DISALLOW_COPY_AND_ASSIGN(BasicBlock);
};

186
std::ostream& operator<<(std::ostream&, const BasicBlock&);
187 188
std::ostream& operator<<(std::ostream&, const BasicBlock::Control&);
std::ostream& operator<<(std::ostream&, const BasicBlock::Id&);
189 190 191 192 193

// A schedule represents the result of assigning nodes to basic blocks
// and ordering them within basic blocks. Prior to computing a schedule,
// a graph has no notion of control flow ordering other than that induced
// by the graph's dependencies. A schedule is required to generate code.
194
class V8_EXPORT_PRIVATE Schedule final : public NON_EXPORTED_BASE(ZoneObject) {
195
 public:
196
  explicit Schedule(Zone* zone, size_t node_count_hint = 0);
197 198

  // Return the block which contains {node}, if any.
199
  BasicBlock* block(Node* node) const;
200

201 202
  bool IsScheduled(Node* node);
  BasicBlock* GetBlockById(BasicBlock::Id block_id);
203

204 205
  size_t BasicBlockCount() const { return all_blocks_.size(); }
  size_t RpoBlockCount() const { return rpo_order_.size(); }
206 207

  // Check if nodes {a} and {b} are in the same block.
208
  bool SameBasicBlock(Node* a, Node* b) const;
209 210

  // BasicBlock building: create a new block.
211
  BasicBlock* NewBasicBlock();
212 213 214

  // BasicBlock building: records that a node will later be added to a block but
  // doesn't actually add the node to the block.
215
  void PlanNode(BasicBlock* block, Node* node);
216 217

  // BasicBlock building: add a node to the end of the block.
218
  void AddNode(BasicBlock* block, Node* node);
219 220

  // BasicBlock building: add a goto to the end of {block}.
221
  void AddGoto(BasicBlock* block, BasicBlock* succ);
222

223 224 225 226
  // BasicBlock building: add a call at the end of {block}.
  void AddCall(BasicBlock* block, Node* call, BasicBlock* success_block,
               BasicBlock* exception_block);

227 228
  // BasicBlock building: add a branch at the end of {block}.
  void AddBranch(BasicBlock* block, Node* branch, BasicBlock* tblock,
229
                 BasicBlock* fblock);
230

231 232 233 234
  // BasicBlock building: add a switch at the end of {block}.
  void AddSwitch(BasicBlock* block, Node* sw, BasicBlock** succ_blocks,
                 size_t succ_count);

235 236 237
  // BasicBlock building: add a deoptimize at the end of {block}.
  void AddDeoptimize(BasicBlock* block, Node* input);

238 239 240
  // BasicBlock building: add a tailcall at the end of {block}.
  void AddTailCall(BasicBlock* block, Node* input);

241
  // BasicBlock building: add a return at the end of {block}.
242
  void AddReturn(BasicBlock* block, Node* input);
243 244

  // BasicBlock building: add a throw at the end of {block}.
245
  void AddThrow(BasicBlock* block, Node* input);
246

247 248 249 250
  // BasicBlock mutation: insert a branch into the end of {block}.
  void InsertBranch(BasicBlock* block, BasicBlock* end, Node* branch,
                    BasicBlock* tblock, BasicBlock* fblock);

251 252 253 254
  // BasicBlock mutation: insert a switch into the end of {block}.
  void InsertSwitch(BasicBlock* block, BasicBlock* end, Node* sw,
                    BasicBlock** succ_blocks, size_t succ_count);

255 256 257 258
  // Exposed publicly for testing only.
  void AddSuccessorForTesting(BasicBlock* block, BasicBlock* succ) {
    return AddSuccessor(block, succ);
  }
259

260
  const BasicBlockVector* all_blocks() const { return &all_blocks_; }
261
  BasicBlockVector* rpo_order() { return &rpo_order_; }
262
  const BasicBlockVector* rpo_order() const { return &rpo_order_; }
263

264 265 266
  BasicBlock* start() { return start_; }
  BasicBlock* end() { return end_; }

267
  Zone* zone() const { return zone_; }
268

269
 private:
270
  friend class Scheduler;
271
  friend class BasicBlockInstrumentor;
272 273
  friend class RawMachineAssembler;

274
  // For CSA/Torque: Ensure properties of the CFG assumed by further stages.
275
  void EnsureCFGWellFormedness();
276 277 278 279
  // For CSA/Torque: Eliminates unnecessary phi nodes, including phis with a
  // single input. The latter is necessary to ensure the property required for
  // SSA deconstruction that the target block of a control flow split has no
  // phis.
280
  void EliminateRedundantPhiNodes();
281
  // Ensure split-edge form for a hand-assembled schedule.
282 283 284
  void EnsureSplitEdgeForm(BasicBlock* block);
  // Ensure entry into a deferred block happens from a single hot block.
  void EnsureDeferredCodeSingleEntryPoint(BasicBlock* block);
285 286
  // Move Phi operands to newly created merger blocks
  void MovePhis(BasicBlock* from, BasicBlock* to);
287 288
  // Copy deferred block markers down as far as possible
  void PropagateDeferredMark();
289

290 291 292
  void AddSuccessor(BasicBlock* block, BasicBlock* succ);
  void MoveSuccessors(BasicBlock* from, BasicBlock* to);

293 294
  void SetControlInput(BasicBlock* block, Node* node);
  void SetBlockForNode(BasicBlock* block, Node* node);
295 296

  Zone* zone_;
297 298 299
  BasicBlockVector all_blocks_;       // All basic blocks in the schedule.
  BasicBlockVector nodeid_to_block_;  // Map from node to containing block.
  BasicBlockVector rpo_order_;        // Reverse-post-order block list.
300 301
  BasicBlock* start_;
  BasicBlock* end_;
302 303

  DISALLOW_COPY_AND_ASSIGN(Schedule);
304 305
};

306
V8_EXPORT_PRIVATE std::ostream& operator<<(std::ostream&, const Schedule&);
307 308 309 310

}  // namespace compiler
}  // namespace internal
}  // namespace v8
311 312

#endif  // V8_COMPILER_SCHEDULE_H_