Schedule floating control.

src/compiler/schedule.h

 // 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_
 
 #include <vector>
 
 #include "src/v8.h"
@@ skipping 22 matching lines @@
     kNone,       // Control not initialized yet.
     kGoto,       // Goto a single successor block.
     kBranch,     // Branch if true to first successor, otherwise second.
     kReturn,     // Return a value from this method.
     kThrow,      // Throw an exception.
     kCall,       // Call to a possibly deoptimizing or throwing function.
     kDeoptimize  // Deoptimize.
   };
 
   int32_t rpo_number_;       // special RPO number of the block.
+  BasicBlock* dominator_;    // Immediate dominator of the block.
   BasicBlock* loop_header_;  // Pointer to dominating loop header basic block,
                              // NULL if none. For loop headers, this points to
                              // enclosing loop header.
   int32_t loop_depth_;       // loop nesting, 0 is top-level
   int32_t loop_end_;         // end of the loop, if this block is a loop header.
   int32_t code_start_;       // start index of arch-specific code.
   int32_t code_end_;         // end index of arch-specific code.
   bool deferred_;            // {true} if this block is considered the slow
                              // path.
   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.
 
   explicit BasicBlockData(Zone* zone)
       : rpo_number_(-1),
+        dominator_(NULL),
         loop_header_(NULL),
         loop_depth_(0),
         loop_end_(-1),
         code_start_(-1),
         code_end_(-1),
         deferred_(false),
         control_(kNone),
         control_input_(NULL),
         nodes_(NodeVector::allocator_type(zone)) {}
 
@@ skipping 86 matching lines @@
 // 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.
 class Schedule : public GenericGraph<BasicBlock> {
  public:
   explicit Schedule(Zone* zone)
       : GenericGraph<BasicBlock>(zone),
         zone_(zone),
         all_blocks_(BasicBlockVector::allocator_type(zone)),
         nodeid_to_block_(BasicBlockVector::allocator_type(zone)),
-        rpo_order_(BasicBlockVector::allocator_type(zone)),
-        immediate_dominator_(BasicBlockVector::allocator_type(zone)) {
+        rpo_order_(BasicBlockVector::allocator_type(zone)) {
     SetStart(NewBasicBlock());  // entry.
     SetEnd(NewBasicBlock());    // exit.
   }
 
   // Return the block which contains {node}, if any.
   BasicBlock* block(Node* node) const {
     if (node->id() < static_cast<NodeId>(nodeid_to_block_.size())) {
       return nodeid_to_block_[node->id()];
     }
     return NULL;
   }
 
-  BasicBlock* dominator(BasicBlock* block) {
-    return immediate_dominator_[block->id()];
-  }
-
   bool IsScheduled(Node* node) {
     int length = static_cast<int>(nodeid_to_block_.size());
     if (node->id() >= length) return false;
     return nodeid_to_block_[node->id()] != NULL;
   }
 
   BasicBlock* GetBlockById(int block_id) { return all_blocks_[block_id]; }
 
   int BasicBlockCount() const { return NodeCount(); }
   int RpoBlockCount() const { return static_cast<int>(rpo_order_.size()); }
@@ skipping 14 matching lines @@
     BasicBlock* block =
         BasicBlock::New(this, 0, static_cast<BasicBlock**>(NULL));
     all_blocks_.push_back(block);
     return block;
   }
 
   // BasicBlock building: records that a node will later be added to a block but
   // doesn't actually add the node to the block.
   inline void PlanNode(BasicBlock* block, Node* node) {
     if (FLAG_trace_turbo_scheduler) {
-      PrintF("Planning node %d for future add to block %d\n", node->id(),
-             block->id());
+      PrintF("Planning #%d:%s for future add to B%d\n", node->id(),
+             node->op()->mnemonic(), block->id());
     }
     DCHECK(this->block(node) == NULL);
     SetBlockForNode(block, node);
   }
 
   // BasicBlock building: add a node to the end of the block.
   inline void AddNode(BasicBlock* block, Node* node) {
     if (FLAG_trace_turbo_scheduler) {
-      PrintF("Adding node %d to block %d\n", node->id(), block->id());
+      PrintF("Adding #%d:%s to B%d\n", node->id(), node->op()->mnemonic(),
+             block->id());
     }
     DCHECK(this->block(node) == NULL || this->block(node) == block);
     block->nodes_.push_back(node);
     SetBlockForNode(block, node);
   }
 
   // BasicBlock building: add a goto to the end of {block}.
   void AddGoto(BasicBlock* block, BasicBlock* succ) {
     DCHECK(block->control_ == BasicBlock::kNone);
     block->control_ = BasicBlock::kGoto;
     AddSuccessor(block, succ);
   }
 
   // BasicBlock building: add a (branching) call at the end of {block}.
   void AddCall(BasicBlock* block, Node* call, BasicBlock* cont_block,
                BasicBlock* deopt_block) {
     DCHECK(block->control_ == BasicBlock::kNone);
     DCHECK(call->opcode() == IrOpcode::kCall);
     block->control_ = BasicBlock::kCall;
     // Insert the deopt block first so that the RPO order builder picks
     // it first (and thus it ends up late in the RPO order).
     AddSuccessor(block, deopt_block);
     AddSuccessor(block, cont_block);
     SetControlInput(block, call);
+    SetBlockForNode(block, call);
   }
 
   // BasicBlock building: add a branch at the end of {block}.
   void AddBranch(BasicBlock* block, Node* branch, BasicBlock* tblock,
                  BasicBlock* fblock) {
     DCHECK(block->control_ == BasicBlock::kNone);
     DCHECK(branch->opcode() == IrOpcode::kBranch);
     block->control_ = BasicBlock::kBranch;
     AddSuccessor(block, tblock);
     AddSuccessor(block, fblock);
     SetControlInput(block, branch);
+    if (branch->opcode() == IrOpcode::kBranch) {
+      // TODO(titzer): require a Branch node here. (sloppy tests).
+      SetBlockForNode(block, branch);
+    }
   }
 
   // BasicBlock building: add a return at the end of {block}.
   void AddReturn(BasicBlock* block, Node* input) {
-    // TODO(titzer): require a Return node here.
     DCHECK(block->control_ == BasicBlock::kNone);
     block->control_ = BasicBlock::kReturn;
     SetControlInput(block, input);
     if (block != end()) AddSuccessor(block, end());
+    if (input->opcode() == IrOpcode::kReturn) {
+      // TODO(titzer): require a Return node here. (sloppy tests).
+      SetBlockForNode(block, input);
+    }
   }
 
   // BasicBlock building: add a throw at the end of {block}.
   void AddThrow(BasicBlock* block, Node* input) {
     DCHECK(block->control_ == BasicBlock::kNone);
     block->control_ = BasicBlock::kThrow;
     SetControlInput(block, input);
     if (block != end()) AddSuccessor(block, end());
   }
 
@@ skipping 28 matching lines @@
     if (node->id() >= length) {
       nodeid_to_block_.resize(node->id() + 1);
     }
     nodeid_to_block_[node->id()] = block;
   }
 
   Zone* zone_;
   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.
-  BasicBlockVector immediate_dominator_;  // Maps to a block's immediate
-                                          // dominator, indexed by block
-                                          // id.
 };
 
 OStream& operator<<(OStream& os, const Schedule& s);
 }
 }
 }  // namespace v8::internal::compiler
 
 #endif  // V8_COMPILER_SCHEDULE_H_