v8::internal::compiler::Scheduler Class Reference

#include <scheduler.h>

Collaboration diagram for v8::internal::compiler::Scheduler:

Classes
struct	SchedulerData

Static Public Member Functions
static Schedule *	ComputeSchedule (Graph *graph)
static BasicBlockVector *	ComputeSpecialRPO (Schedule *schedule)
static void	ComputeCFG (Graph *graph, Schedule *schedule)

Private Types
enum	Placement { kUnknown , kSchedulable , kFixed }

Private Member Functions
	Scheduler (Zone *zone, Graph *graph, Schedule *schedule)
SchedulerData	DefaultSchedulerData ()
SchedulerData *	GetData (Node *node)
void	BuildCFG ()
Placement	GetPlacement (Node *node)
int	GetRPONumber (BasicBlock *block)
void	GenerateImmediateDominatorTree ()
BasicBlock *	GetCommonDominator (BasicBlock *b1, BasicBlock *b2)
void	ScheduleEarly ()
void	PrepareUses ()
void	ScheduleLate ()
bool	ConnectFloatingControl ()
void	ConnectFloatingControlSubgraph (BasicBlock *block, Node *node)

Private Attributes
Zone *	zone_
Graph *	graph_
Schedule *	schedule_
NodeVectorVector	scheduled_nodes_
NodeVector	schedule_root_nodes_
ZoneVector< SchedulerData >	node_data_
bool	has_floating_control_

Friends
class	CFGBuilder
class	ScheduleEarlyNodeVisitor
class	PrepareUsesVisitor
class	ScheduleLateNodeVisitor

Detailed Description

Definition at line 20 of file scheduler.h.

Member Enumeration Documentation

Placement

enum v8::internal::compiler::Scheduler::Placement

private

Enumerator
kUnknown
kSchedulable
kFixed

Definition at line 34 of file scheduler.h.

{ kUnknown, kSchedulable, kFixed };

Constructor & Destructor Documentation

Scheduler()

v8::internal::compiler::Scheduler::Scheduler ( Zone *  zone, Graph *  graph, Schedule *  schedule  )

private

Definition at line 227 of file scheduler.cc.

    : zone_(zone),
      graph_(graph),
      schedule_(schedule),
      scheduled_nodes_(zone),
      schedule_root_nodes_(zone),
      node_data_(graph_->NodeCount(), DefaultSchedulerData(), zone),
      has_floating_control_(false) {}

Member Function Documentation

BuildCFG()

void v8::internal::compiler::Scheduler::BuildCFG ( )

private

Definition at line 299 of file scheduler.cc.

                         {
  Trace("---------------- CREATING CFG ------------------\n");
  CFGBuilder cfg_builder(zone_, this);
  cfg_builder.Run();
  // Initialize per-block data.
  scheduled_nodes_.resize(schedule_->BasicBlockCount(), NodeVector(zone_));
}

References v8::internal::compiler::Schedule::BasicBlockCount(), v8::internal::compiler::CFGBuilder::Run(), schedule_, scheduled_nodes_, v8::internal::compiler::Trace(), and zone_.

Referenced by ComputeSchedule().

Here is the call graph for this function:

Here is the caller graph for this function:

ComputeCFG()

static void v8::internal::compiler::Scheduler::ComputeCFG ( Graph *  graph, Schedule *  schedule  )

static

ComputeSchedule()

Schedule * v8::internal::compiler::Scheduler::ComputeSchedule ( Graph *  graph )

static

Definition at line 237 of file scheduler.cc.

                                                 {
  Schedule* schedule;
  bool had_floating_control = false;
  do {
    Zone tmp_zone(graph->zone()->isolate());
    schedule = new (graph->zone())
        Schedule(graph->zone(), static_cast<size_t>(graph->NodeCount()));
    Scheduler scheduler(&tmp_zone, graph, schedule);
 
    scheduler.BuildCFG();
 
    Scheduler::ComputeSpecialRPO(schedule);
    scheduler.GenerateImmediateDominatorTree();
 
    scheduler.PrepareUses();
    scheduler.ScheduleEarly();
    scheduler.ScheduleLate();
 
    had_floating_control = scheduler.ConnectFloatingControl();
  } while (had_floating_control);
 
  return schedule;
}

References BuildCFG(), ComputeSpecialRPO(), ConnectFloatingControl(), GenerateImmediateDominatorTree(), v8::internal::Zone::isolate(), v8::internal::compiler::GenericGraphBase::NodeCount(), PrepareUses(), ScheduleEarly(), ScheduleLate(), and v8::internal::compiler::GenericGraphBase::zone().

Referenced by v8::internal::compiler::Pipeline::ComputeSchedule().

Here is the call graph for this function:

Here is the caller graph for this function:

ComputeSpecialRPO()

BasicBlockVector * v8::internal::compiler::Scheduler::ComputeSpecialRPO ( Schedule *  schedule )

static

Definition at line 933 of file scheduler.cc.

                                                                 {
  Zone tmp_zone(schedule->zone()->isolate());
  Zone* zone = &tmp_zone;
  Trace("------------- COMPUTING SPECIAL RPO ---------------\n");
  // RPO should not have been computed for this schedule yet.
  CHECK_EQ(kBlockUnvisited1, schedule->start()->rpo_number_);
  CHECK_EQ(0, static_cast<int>(schedule->rpo_order_.size()));
 
  // Perform an iterative RPO traversal using an explicit stack,
  // recording backedges that form cycles. O(|B|).
  ZoneList<std::pair<BasicBlock*, int> > backedges(1, zone);
  SpecialRPOStackFrame* stack =
      zone->NewArray<SpecialRPOStackFrame>(schedule->BasicBlockCount());
  BasicBlock* entry = schedule->start();
  BlockList* order = NULL;
  int stack_depth = Push(stack, 0, entry, kBlockUnvisited1);
  int num_loops = 0;
 
  while (stack_depth > 0) {
    int current = stack_depth - 1;
    SpecialRPOStackFrame* frame = stack + current;
 
    if (frame->index < frame->block->SuccessorCount()) {
      // Process the next successor.
      BasicBlock* succ = frame->block->SuccessorAt(frame->index++);
      if (succ->rpo_number_ == kBlockVisited1) continue;
      if (succ->rpo_number_ == kBlockOnStack) {
        // The successor is on the stack, so this is a backedge (cycle).
        backedges.Add(
            std::pair<BasicBlock*, int>(frame->block, frame->index - 1), zone);
        if (succ->loop_end_ < 0) {
          // Assign a new loop number to the header if it doesn't have one.
          succ->loop_end_ = num_loops++;
        }
      } else {
        // Push the successor onto the stack.
        DCHECK(succ->rpo_number_ == kBlockUnvisited1);
        stack_depth = Push(stack, stack_depth, succ, kBlockUnvisited1);
      }
    } else {
      // Finished with all successors; pop the stack and add the block.
      order = order->Add(zone, frame->block);
      frame->block->rpo_number_ = kBlockVisited1;
      stack_depth--;
    }
  }
 
  // If no loops were encountered, then the order we computed was correct.
  LoopInfo* loops = NULL;
  if (num_loops != 0) {
    // Otherwise, compute the loop information from the backedges in order
    // to perform a traversal that groups loop bodies together.
    loops = ComputeLoopInfo(zone, stack, num_loops, schedule->BasicBlockCount(),
                            &backedges);
 
    // Initialize the "loop stack". Note the entry could be a loop header.
    LoopInfo* loop = entry->IsLoopHeader() ? &loops[entry->loop_end_] : NULL;
    order = NULL;
 
    // Perform an iterative post-order traversal, visiting loop bodies before
    // edges that lead out of loops. Visits each block once, but linking loop
    // sections together is linear in the loop size, so overall is
    // O(|B| + max(loop_depth) * max(|loop|))
    stack_depth = Push(stack, 0, entry, kBlockUnvisited2);
    while (stack_depth > 0) {
      SpecialRPOStackFrame* frame = stack + (stack_depth - 1);
      BasicBlock* block = frame->block;
      BasicBlock* succ = NULL;
 
      if (frame->index < block->SuccessorCount()) {
        // Process the next normal successor.
        succ = block->SuccessorAt(frame->index++);
      } else if (block->IsLoopHeader()) {
        // Process additional outgoing edges from the loop header.
        if (block->rpo_number_ == kBlockOnStack) {
          // Finish the loop body the first time the header is left on the
          // stack.
          DCHECK(loop != NULL && loop->header == block);
          loop->start = order->Add(zone, block);
          order = loop->end;
          block->rpo_number_ = kBlockVisited2;
          // Pop the loop stack and continue visiting outgoing edges within the
          // the context of the outer loop, if any.
          loop = loop->prev;
          // We leave the loop header on the stack; the rest of this iteration
          // and later iterations will go through its outgoing edges list.
        }
 
        // Use the next outgoing edge if there are any.
        int outgoing_index = frame->index - block->SuccessorCount();
        LoopInfo* info = &loops[block->loop_end_];
        DCHECK(loop != info);
        if (info->outgoing != NULL &&
            outgoing_index < info->outgoing->length()) {
          succ = info->outgoing->at(outgoing_index);
          frame->index++;
        }
      }
 
      if (succ != NULL) {
        // Process the next successor.
        if (succ->rpo_number_ == kBlockOnStack) continue;
        if (succ->rpo_number_ == kBlockVisited2) continue;
        DCHECK(succ->rpo_number_ == kBlockUnvisited2);
        if (loop != NULL && !loop->members->Contains(succ->id())) {
          // The successor is not in the current loop or any nested loop.
          // Add it to the outgoing edges of this loop and visit it later.
          loop->AddOutgoing(zone, succ);
        } else {
          // Push the successor onto the stack.
          stack_depth = Push(stack, stack_depth, succ, kBlockUnvisited2);
          if (succ->IsLoopHeader()) {
            // Push the inner loop onto the loop stack.
            DCHECK(succ->loop_end_ >= 0 && succ->loop_end_ < num_loops);
            LoopInfo* next = &loops[succ->loop_end_];
            next->end = order;
            next->prev = loop;
            loop = next;
          }
        }
      } else {
        // Finished with all successors of the current block.
        if (block->IsLoopHeader()) {
          // If we are going to pop a loop header, then add its entire body.
          LoopInfo* info = &loops[block->loop_end_];
          for (BlockList* l = info->start; true; l = l->next) {
            if (l->next == info->end) {
              l->next = order;
              info->end = order;
              break;
            }
          }
          order = info->start;
        } else {
          // Pop a single node off the stack and add it to the order.
          order = order->Add(zone, block);
          block->rpo_number_ = kBlockVisited2;
        }
        stack_depth--;
      }
    }
  }
 
  // Construct the final order from the list.
  BasicBlockVector* final_order = &schedule->rpo_order_;
  order->Serialize(final_order);
 
  // Compute the correct loop header for every block and set the correct loop
  // ends.
  LoopInfo* current_loop = NULL;
  BasicBlock* current_header = NULL;
  int loop_depth = 0;
  for (BasicBlockVectorIter i = final_order->begin(); i != final_order->end();
       ++i) {
    BasicBlock* current = *i;
    current->loop_header_ = current_header;
    if (current->IsLoopHeader()) {
      loop_depth++;
      current_loop = &loops[current->loop_end_];
      BlockList* end = current_loop->end;
      current->loop_end_ = end == NULL ? static_cast<int>(final_order->size())
                                       : end->block->rpo_number_;
      current_header = current_loop->header;
      Trace("B%d is a loop header, increment loop depth to %d\n", current->id(),
            loop_depth);
    } else {
      while (current_header != NULL &&
             current->rpo_number_ >= current_header->loop_end_) {
        DCHECK(current_header->IsLoopHeader());
        DCHECK(current_loop != NULL);
        current_loop = current_loop->prev;
        current_header = current_loop == NULL ? NULL : current_loop->header;
        --loop_depth;
      }
    }
    current->loop_depth_ = loop_depth;
    if (current->loop_header_ == NULL) {
      Trace("B%d is not in a loop (depth == %d)\n", current->id(),
            current->loop_depth_);
    } else {
      Trace("B%d has loop header B%d, (depth == %d)\n", current->id(),
            current->loop_header_->id(), current->loop_depth_);
    }
  }
 
#if DEBUG
  if (FLAG_trace_turbo_scheduler) PrintRPO(num_loops, loops, final_order);
  VerifySpecialRPO(num_loops, loops, final_order);
#endif
  return final_order;
}

References v8::internal::List< T, AllocationPolicy >::Add(), v8::internal::compiler::BlockList::Add(), v8::internal::compiler::LoopInfo::AddOutgoing(), v8::internal::List< T, AllocationPolicy >::at(), v8::internal::compiler::Schedule::BasicBlockCount(), v8::internal::compiler::SpecialRPOStackFrame::block, v8::internal::compiler::BlockList::block, CHECK_EQ, v8::internal::compiler::ComputeLoopInfo(), v8::internal::BitVector::Contains(), DCHECK, v8::internal::compiler::LoopInfo::end, v8::internal::compiler::LoopInfo::header, v8::internal::compiler::SpecialRPOStackFrame::index, v8::internal::Zone::isolate(), v8::internal::compiler::kBlockOnStack, v8::internal::compiler::kBlockUnvisited1, v8::internal::compiler::kBlockUnvisited2, v8::internal::compiler::kBlockVisited1, v8::internal::compiler::kBlockVisited2, v8::internal::compiler::LoopInfo::members, v8::internal::Zone::NewArray(), v8::internal::compiler::BlockList::next, NULL, v8::internal::compiler::LoopInfo::outgoing, v8::internal::compiler::LoopInfo::prev, v8::internal::compiler::Push(), v8::internal::compiler::Schedule::rpo_order_, v8::internal::compiler::BlockList::Serialize(), v8::internal::compiler::GenericGraph< V >::start(), v8::internal::compiler::LoopInfo::start, v8::internal::compiler::Trace(), and v8::internal::compiler::GenericGraphBase::zone().

Referenced by ComputeSchedule(), and v8::internal::compiler::RawMachineAssembler::Export().

Here is the call graph for this function:

Here is the caller graph for this function:

ConnectFloatingControl()

bool v8::internal::compiler::Scheduler::ConnectFloatingControl ( )

private

Definition at line 631 of file scheduler.cc.

                                       {
  if (!has_floating_control_) return false;
 
  Trace("Connecting floating control...\n");
 
  // Process blocks and instructions backwards to find and connect floating
  // control nodes into the control graph according to the block they were
  // scheduled into.
  int max = static_cast<int>(schedule_->rpo_order()->size());
  for (int i = max - 1; i >= 0; i--) {
    BasicBlock* block = schedule_->rpo_order()->at(i);
    // TODO(titzer): we place at most one floating control structure per
    // basic block because scheduling currently can interleave phis from
    // one subgraph with the merges from another subgraph.
    bool one_placed = false;
    for (int j = static_cast<int>(block->nodes_.size()) - 1; j >= 0; j--) {
      Node* node = block->nodes_[j];
      SchedulerData* data = GetData(node);
      if (data->is_floating_control_ && !data->is_connected_control_ &&
          !one_placed) {
        Trace("  Floating control #%d:%s was scheduled in B%d\n", node->id(),
              node->op()->mnemonic(), block->id());
        ConnectFloatingControlSubgraph(block, node);
        one_placed = true;
      }
    }
  }
 
  return true;
}

References ConnectFloatingControlSubgraph(), GetData(), has_floating_control_, v8::internal::compiler::Scheduler::SchedulerData::is_connected_control_, v8::internal::compiler::Scheduler::SchedulerData::is_floating_control_, v8::internal::compiler::Schedule::rpo_order(), schedule_, and v8::internal::compiler::Trace().

Referenced by ComputeSchedule().

Here is the call graph for this function:

Here is the caller graph for this function:

ConnectFloatingControlSubgraph()

void v8::internal::compiler::Scheduler::ConnectFloatingControlSubgraph ( BasicBlock *  block, Node *  node  )

private

Definition at line 663 of file scheduler.cc.

                                                                           {
  Node* block_start = block->nodes_[0];
  DCHECK(IrOpcode::IsControlOpcode(block_start->opcode()));
  // Find the current "control successor" of the node that starts the block
  // by searching the control uses for a control input edge from a connected
  // control node.
  Node* control_succ = NULL;
  for (UseIter i = block_start->uses().begin(); i != block_start->uses().end();
       ++i) {
    Node::Edge edge = i.edge();
    if (NodeProperties::IsControlEdge(edge) &&
        GetData(edge.from())->is_connected_control_) {
      DCHECK_EQ(NULL, control_succ);
      control_succ = edge.from();
      control_succ->ReplaceInput(edge.index(), end);
    }
  }
  DCHECK_NE(NULL, control_succ);
  Trace("  Inserting floating control end %d:%s between %d:%s -> %d:%s\n",
        end->id(), end->op()->mnemonic(), control_succ->id(),
        control_succ->op()->mnemonic(), block_start->id(),
        block_start->op()->mnemonic());
 
  // Find the "start" node of the control subgraph, which should be the
  // unique node that is itself floating control but has a control input that
  // is not floating.
  Node* start = NULL;
  ZoneQueue<Node*> queue(zone_);
  queue.push(end);
  GetData(end)->is_connected_control_ = true;
  while (!queue.empty()) {
    Node* node = queue.front();
    queue.pop();
    Trace("  Search #%d:%s for control subgraph start\n", node->id(),
          node->op()->mnemonic());
    int max = NodeProperties::PastControlIndex(node);
    for (int i = NodeProperties::FirstControlIndex(node); i < max; i++) {
      Node* input = node->InputAt(i);
      SchedulerData* data = GetData(input);
      if (data->is_floating_control_) {
        // {input} is floating control.
        if (!data->is_connected_control_) {
          // First time seeing {input} during this traversal, queue it.
          queue.push(input);
          data->is_connected_control_ = true;
        }
      } else {
        // Otherwise, {node} is the start node, because it is floating control
        // but is connected to {input} that is not floating control.
        DCHECK_EQ(NULL, start);  // There can be only one.
        start = node;
      }
    }
  }
 
  DCHECK_NE(NULL, start);
  start->ReplaceInput(NodeProperties::FirstControlIndex(start), block_start);
 
  Trace("  Connecting floating control start %d:%s to %d:%s\n", start->id(),
        start->op()->mnemonic(), block_start->id(),
        block_start->op()->mnemonic());
}

References DCHECK, DCHECK_EQ, DCHECK_NE, v8::internal::compiler::NodeProperties::FirstControlIndex(), GetData(), v8::internal::compiler::Scheduler::SchedulerData::is_connected_control_, v8::internal::compiler::Scheduler::SchedulerData::is_floating_control_, v8::internal::compiler::NodeProperties::IsControlEdge(), v8::internal::compiler::IrOpcode::IsControlOpcode(), NULL, v8::internal::compiler::NodeProperties::PastControlIndex(), v8::internal::compiler::Trace(), and zone_.

Referenced by ConnectFloatingControl().

Here is the call graph for this function:

Here is the caller graph for this function:

DefaultSchedulerData()

Scheduler::SchedulerData v8::internal::compiler::Scheduler::DefaultSchedulerData ( )

private

Definition at line 221 of file scheduler.cc.

                                                       {
  SchedulerData def = {0, 0, false, false, kUnknown};
  return def;
}

References kUnknown.

GenerateImmediateDominatorTree()

void v8::internal::compiler::Scheduler::GenerateImmediateDominatorTree ( )

private

Definition at line 323 of file scheduler.cc.

                                               {
  // Build the dominator graph.  TODO(danno): consider using Lengauer & Tarjan's
  // if this becomes really slow.
  Trace("------------ IMMEDIATE BLOCK DOMINATORS -----------\n");
  for (size_t i = 0; i < schedule_->rpo_order_.size(); i++) {
    BasicBlock* current_rpo = schedule_->rpo_order_[i];
    if (current_rpo != schedule_->start()) {
      BasicBlock::Predecessors::iterator current_pred =
          current_rpo->predecessors().begin();
      BasicBlock::Predecessors::iterator end =
          current_rpo->predecessors().end();
      DCHECK(current_pred != end);
      BasicBlock* dominator = *current_pred;
      ++current_pred;
      // For multiple predecessors, walk up the rpo ordering until a common
      // dominator is found.
      int current_rpo_pos = GetRPONumber(current_rpo);
      while (current_pred != end) {
        // Don't examine backwards edges
        BasicBlock* pred = *current_pred;
        if (GetRPONumber(pred) < current_rpo_pos) {
          dominator = GetCommonDominator(dominator, *current_pred);
        }
        ++current_pred;
      }
      current_rpo->dominator_ = dominator;
      Trace("Block %d's idom is %d\n", current_rpo->id(), dominator->id());
    }
  }
}

References DCHECK, GetCommonDominator(), GetRPONumber(), v8::internal::compiler::Schedule::rpo_order_, schedule_, v8::internal::compiler::GenericGraph< V >::start(), and v8::internal::compiler::Trace().

Referenced by ComputeSchedule().

Here is the call graph for this function:

Here is the caller graph for this function:

GetCommonDominator()

BasicBlock * v8::internal::compiler::Scheduler::GetCommonDominator ( BasicBlock *  b1, BasicBlock *  b2  )

private

Definition at line 308 of file scheduler.cc.

                                                                        {
  while (b1 != b2) {
    int b1_rpo = GetRPONumber(b1);
    int b2_rpo = GetRPONumber(b2);
    DCHECK(b1_rpo != b2_rpo);
    if (b1_rpo < b2_rpo) {
      b2 = b2->dominator_;
    } else {
      b1 = b1->dominator_;
    }
  }
  return b1;
}

References DCHECK, and GetRPONumber().

Referenced by GenerateImmediateDominatorTree(), and v8::internal::compiler::ScheduleLateNodeVisitor::Pre().

Here is the call graph for this function:

Here is the caller graph for this function:

GetData()

SchedulerData* v8::internal::compiler::Scheduler::GetData ( Node *  node )

inlineprivate

Definition at line 59 of file scheduler.h.

                                     {
    DCHECK(node->id() < static_cast<int>(node_data_.size()));
    return &node_data_[node->id()];
  }

References DCHECK, and node_data_.

Referenced by ConnectFloatingControl(), ConnectFloatingControlSubgraph(), v8::internal::compiler::CFGBuilder::FixNode(), GetPlacement(), v8::internal::compiler::ScheduleEarlyNodeVisitor::Post(), v8::internal::compiler::PrepareUsesVisitor::PostEdge(), v8::internal::compiler::ScheduleEarlyNodeVisitor::Pre(), v8::internal::compiler::ScheduleLateNodeVisitor::Pre(), v8::internal::compiler::CFGBuilder::Queue(), and v8::internal::compiler::ScheduleLateNodeVisitor::ScheduleNode().

Here is the caller graph for this function:

GetPlacement()

Scheduler::Placement v8::internal::compiler::Scheduler::GetPlacement ( Node *  node )

private

Definition at line 262 of file scheduler.cc.

                                                     {
  SchedulerData* data = GetData(node);
  if (data->placement_ == kUnknown) {  // Compute placement, once, on demand.
    switch (node->opcode()) {
      case IrOpcode::kParameter:
        // Parameters are always fixed to the start node.
        data->placement_ = kFixed;
        break;
      case IrOpcode::kPhi:
      case IrOpcode::kEffectPhi: {
        // Phis and effect phis are fixed if their control inputs are.
        data->placement_ = GetPlacement(NodeProperties::GetControlInput(node));
        break;
      }
#define DEFINE_FLOATING_CONTROL_CASE(V) case IrOpcode::k##V:
        CONTROL_OP_LIST(DEFINE_FLOATING_CONTROL_CASE)
#undef DEFINE_FLOATING_CONTROL_CASE
        {
          // Control nodes that were not control-reachable from end may float.
          data->placement_ = kSchedulable;
          if (!data->is_connected_control_) {
            data->is_floating_control_ = true;
            has_floating_control_ = true;
            Trace("Floating control found: #%d:%s\n", node->id(),
                  node->op()->mnemonic());
          }
          break;
        }
      default:
        data->placement_ = kSchedulable;
        break;
    }
  }
  return data->placement_;
}

References CONTROL_OP_LIST, DEFINE_FLOATING_CONTROL_CASE, v8::internal::compiler::NodeProperties::GetControlInput(), GetData(), has_floating_control_, v8::internal::compiler::Scheduler::SchedulerData::is_connected_control_, v8::internal::compiler::Scheduler::SchedulerData::is_floating_control_, kFixed, kSchedulable, kUnknown, v8::internal::compiler::Scheduler::SchedulerData::placement_, and v8::internal::compiler::Trace().

Referenced by v8::internal::compiler::ScheduleLateNodeVisitor::GetBlockForUse(), v8::internal::compiler::ScheduleEarlyNodeVisitor::Post(), v8::internal::compiler::PrepareUsesVisitor::PostEdge(), v8::internal::compiler::ScheduleEarlyNodeVisitor::Pre(), and v8::internal::compiler::PrepareUsesVisitor::Pre().

Here is the call graph for this function:

Here is the caller graph for this function:

GetRPONumber()

int v8::internal::compiler::Scheduler::GetRPONumber ( BasicBlock *  block )

inlineprivate

Definition at line 68 of file scheduler.h.

                                      {
    DCHECK(block->rpo_number_ >= 0 &&
           block->rpo_number_ < static_cast<int>(schedule_->rpo_order_.size()));
    DCHECK(schedule_->rpo_order_[block->rpo_number_] == block);
    return block->rpo_number_;
  }

References DCHECK, v8::internal::compiler::Schedule::rpo_order_, and schedule_.

Referenced by GenerateImmediateDominatorTree(), and GetCommonDominator().

Here is the caller graph for this function:

PrepareUses()

void v8::internal::compiler::Scheduler::PrepareUses ( )

private

Definition at line 470 of file scheduler.cc.

                            {
  Trace("------------------- PREPARE USES ------------------\n");
  // Count the uses of every node, it will be used to ensure that all of a
  // node's uses are scheduled before the node itself.
  PrepareUsesVisitor prepare_uses(this);
  graph_->VisitNodeInputsFromEnd(&prepare_uses);
}

References graph_, v8::internal::compiler::Trace(), and v8::internal::compiler::Graph::VisitNodeInputsFromEnd().

Referenced by ComputeSchedule().

Here is the call graph for this function:

Here is the caller graph for this function:

ScheduleEarly()

void v8::internal::compiler::Scheduler::ScheduleEarly ( )

private

Definition at line 410 of file scheduler.cc.

                              {
  Trace("------------------- SCHEDULE EARLY ----------------\n");
 
  int fixpoint_count = 0;
  ScheduleEarlyNodeVisitor visitor(this);
  while (visitor.has_changed_rpo_constraints_) {
    visitor.has_changed_rpo_constraints_ = false;
    graph_->VisitNodeInputsFromEnd(&visitor);
    fixpoint_count++;
  }
 
  Trace("It took %d iterations to determine fixpoint\n", fixpoint_count);
}

References graph_, v8::internal::compiler::ScheduleEarlyNodeVisitor::has_changed_rpo_constraints_, v8::internal::compiler::Trace(), and v8::internal::compiler::Graph::VisitNodeInputsFromEnd().

Referenced by ComputeSchedule().

Here is the call graph for this function:

Here is the caller graph for this function:

ScheduleLate()

void v8::internal::compiler::Scheduler::ScheduleLate ( )

private

Definition at line 597 of file scheduler.cc.

                             {
  Trace("------------------- SCHEDULE LATE -----------------\n");
  if (FLAG_trace_turbo_scheduler) {
    Trace("roots: ");
    for (NodeVectorIter i = schedule_root_nodes_.begin();
         i != schedule_root_nodes_.end(); ++i) {
      Trace("#%d:%s ", (*i)->id(), (*i)->op()->mnemonic());
    }
    Trace("\n");
  }
 
  // Schedule: Places nodes in dominator block of all their uses.
  ScheduleLateNodeVisitor schedule_late_visitor(this);
 
  {
    Zone zone(zone_->isolate());
    GenericGraphVisit::Visit<ScheduleLateNodeVisitor,
                             NodeInputIterationTraits<Node> >(
        graph_, &zone, schedule_root_nodes_.begin(), schedule_root_nodes_.end(),
        &schedule_late_visitor);
  }
 
  // Add collected nodes for basic blocks to their blocks in the right order.
  int block_num = 0;
  for (NodeVectorVectorIter i = scheduled_nodes_.begin();
       i != scheduled_nodes_.end(); ++i) {
    for (NodeVectorRIter j = i->rbegin(); j != i->rend(); ++j) {
      schedule_->AddNode(schedule_->all_blocks_.at(block_num), *j);
    }
    block_num++;
  }
}

References v8::internal::compiler::Schedule::AddNode(), v8::internal::compiler::Schedule::all_blocks_, graph_, v8::internal::Zone::isolate(), schedule_, schedule_root_nodes_, scheduled_nodes_, ScheduleLateNodeVisitor, v8::internal::compiler::Trace(), v8::internal::compiler::GenericGraphVisit::Visit(), and zone_.

Referenced by ComputeSchedule().

Here is the call graph for this function:

Here is the caller graph for this function:

Friends And Related Function Documentation

CFGBuilder

friend class CFGBuilder

friend

Definition at line 78 of file scheduler.h.

PrepareUsesVisitor

friend class PrepareUsesVisitor

friend

Definition at line 83 of file scheduler.h.

ScheduleEarlyNodeVisitor

friend class ScheduleEarlyNodeVisitor

friend

Definition at line 80 of file scheduler.h.

ScheduleLateNodeVisitor

friend class ScheduleLateNodeVisitor

friend

Definition at line 86 of file scheduler.h.

Referenced by ScheduleLate().

Member Data Documentation

graph_

Graph* v8::internal::compiler::Scheduler::graph_

private

Definition at line 48 of file scheduler.h.

Referenced by PrepareUses(), v8::internal::compiler::CFGBuilder::Run(), ScheduleEarly(), and ScheduleLate().

has_floating_control_

bool v8::internal::compiler::Scheduler::has_floating_control_

private

Definition at line 53 of file scheduler.h.

Referenced by ConnectFloatingControl(), and GetPlacement().

node_data_

ZoneVector<SchedulerData> v8::internal::compiler::Scheduler::node_data_

private

Definition at line 52 of file scheduler.h.

Referenced by GetData().

schedule_

Schedule* v8::internal::compiler::Scheduler::schedule_

private

Definition at line 49 of file scheduler.h.

Referenced by BuildCFG(), ConnectFloatingControl(), GenerateImmediateDominatorTree(), GetRPONumber(), and ScheduleLate().

schedule_root_nodes_

NodeVector v8::internal::compiler::Scheduler::schedule_root_nodes_

private

Definition at line 51 of file scheduler.h.

Referenced by v8::internal::compiler::CFGBuilder::ConnectBlocks(), v8::internal::compiler::PrepareUsesVisitor::Pre(), and ScheduleLate().

scheduled_nodes_

NodeVectorVector v8::internal::compiler::Scheduler::scheduled_nodes_

private

Definition at line 50 of file scheduler.h.

Referenced by BuildCFG(), ScheduleLate(), and v8::internal::compiler::ScheduleLateNodeVisitor::ScheduleNode().

zone_

Zone* v8::internal::compiler::Scheduler::zone_

private

Definition at line 47 of file scheduler.h.

Referenced by BuildCFG(), ConnectFloatingControlSubgraph(), and ScheduleLate().

---

The documentation for this class was generated from the following files:

• /mnt/V8SourceCode/src/compiler/scheduler.h
• /mnt/V8SourceCode/src/compiler/scheduler.cc