[turbofan] decouple register allocation from schedule and graph

src/compiler/instruction.cc

 // Copyright 2014 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.
 
 #include "src/compiler/instruction.h"
 
 #include "src/compiler/common-operator.h"
 #include "src/compiler/generic-node-inl.h"
 #include "src/compiler/graph.h"
 
@@ skipping 299 matching lines @@
       return os << static_cast<const void*>(
                        constant.ToExternalReference().address());
     case Constant::kHeapObject:
       return os << Brief(*constant.ToHeapObject());
   }
   UNREACHABLE();
   return os;
 }
 
 
+static BasicBlock::RpoNumber GetRpo(BasicBlock* block) {
+  if (block == NULL) return BasicBlock::RpoNumber::Invalid();
+  return block->GetRpoNumber();
+}
+
+
+static BasicBlock::RpoNumber GetLoopEndRpo(const BasicBlock* block) {
+  if (!block->IsLoopHeader()) return BasicBlock::RpoNumber::Invalid();
+  return BasicBlock::RpoNumber::FromInt(block->loop_end());
+}
+
+
+InstructionBlock::InstructionBlock(Zone* zone, const BasicBlock* block)
+    : successors_(block->SuccessorCount(), BasicBlock::RpoNumber::Invalid(),
+                  zone),
+      predecessors_(block->PredecessorCount(), BasicBlock::RpoNumber::Invalid(),
+                    zone),
+      phis_(zone),
+      rpo_number_(block->GetRpoNumber()),
+      loop_header_(GetRpo(block->loop_header())),
+      loop_end_(GetLoopEndRpo(block)),
+      code_start_(-1),
+      code_end_(-1) {
+  // Map successors and precessors
+  size_t index = 0;
+  for (BasicBlock::Successors::const_iterator it = block->successors_begin();
+       it != block->successors_end(); ++it, ++index) {
+    successors_[index] = (*it)->GetRpoNumber();
+  }
+  index = 0;
+  for (BasicBlock::Predecessors::const_iterator
+           it = block->predecessors_begin();
+       it != block->predecessors_end(); ++it, ++index) {
+    predecessors_[index] = (*it)->GetRpoNumber();
+  }
+}
+
+
+size_t InstructionBlock::PredecessorIndexOf(
+    BasicBlock::RpoNumber rpo_number) const {
+  size_t j = 0;
+  for (InstructionBlock::Predecessors::const_iterator i = predecessors_.begin();
+       i != predecessors_.end(); ++i, ++j) {
+    if (*i == rpo_number) break;
+  }
+  return j;
+}
+
+
+static void InitializeInstructionBlocks(Zone* zone, const Schedule* schedule,
+                                        InstructionBlocks* blocks) {
+  DCHECK(blocks->size() == schedule->rpo_order()->size());
+  size_t rpo_number = 0;
+  for (BasicBlockVector::const_iterator it = schedule->rpo_order()->begin();
+       it != schedule->rpo_order()->end(); ++it, ++rpo_number) {
+    DCHECK_EQ(NULL, (*blocks)[rpo_number]);
+    DCHECK((*it)->GetRpoNumber().ToSize() == rpo_number);
+    (*blocks)[rpo_number] = new (zone) InstructionBlock(zone, *it);
+  }
+}
+
+
 InstructionSequence::InstructionSequence(Linkage* linkage, Graph* graph,
                                          Schedule* schedule)
-    : zone_(schedule->zone()),
+    : zone_(schedule->zone()),  // TODO(dcarney): new zone.
       node_count_(graph->NodeCount()),
       node_map_(zone()->NewArray<int>(node_count_)),
-      block_data_(static_cast<int>(schedule->BasicBlockCount()), zone()),
+      instruction_blocks_(static_cast<int>(schedule->rpo_order()->size()), NULL,
+                          zone()),
       linkage_(linkage),
       schedule_(schedule),
       constants_(ConstantMap::key_compare(),
                  ConstantMap::allocator_type(zone())),
       immediates_(zone()),
       instructions_(zone()),
       next_virtual_register_(0),
       pointer_maps_(zone()),
       doubles_(std::less<int>(), VirtualRegisterSet::allocator_type(zone())),
       references_(std::less<int>(), VirtualRegisterSet::allocator_type(zone())),
       deoptimization_entries_(zone()) {
   for (int i = 0; i < node_count_; ++i) {
     node_map_[i] = -1;
   }
+  InitializeInstructionBlocks(zone(), schedule, &instruction_blocks_);
 }
 
 
 int InstructionSequence::GetVirtualRegister(const Node* node) {
   if (node_map_[node->id()] == -1) {
     node_map_[node->id()] = NextVirtualRegister();
   }
   return node_map_[node->id()];
 }
 
@@ skipping 51 matching lines @@
     DCHECK_LE(0, instruction_index);
     Instruction* instruction = InstructionAt(instruction_index--);
     if (instruction->IsBlockStart()) {
       return schedule()->rpo_order()->at(
           BlockStartInstruction::cast(instruction)->rpo_number().ToSize());
     }
   }
 }
 
 
+const InstructionBlock* InstructionSequence::GetInstructionBlock(
+    int instruction_index) const {
+  // TODO(turbofan): Optimize this.
+  for (;;) {
+    DCHECK_LE(0, instruction_index);
+    Instruction* instruction = InstructionAt(instruction_index--);
+    if (instruction->IsBlockStart()) {
+      return instruction_blocks_
+          [BlockStartInstruction::cast(instruction)->rpo_number().ToSize()];
+    }
+  }
+}
+
+
 bool InstructionSequence::IsReference(int virtual_register) const {
   return references_.find(virtual_register) != references_.end();
 }
 
 
 bool InstructionSequence::IsDouble(int virtual_register) const {
   return doubles_.find(virtual_register) != doubles_.end();
 }
 
 
@@ skipping 164 matching lines @@
       os << " B" << (*iter)->id();
     }
     os << "\n";
   }
   return os;
 }
 
 }  // namespace compiler
 }  // namespace internal
 }  // namespace v8