[turbofan] LiveRange structure validation

src/compiler/register-allocator.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/base/adapters.h"
 #include "src/compiler/linkage.h"
 #include "src/compiler/register-allocator.h"
 #include "src/string-stream.h"
 
 namespace v8 {
@@ skipping 1543 matching lines @@
       for (int instr = first; instr <= last;) {
         const InstructionBlock* block = code()->GetInstructionBlock(instr);
         if (!block->IsDeferred()) return false;
         instr = block->last_instruction_index() + 1;
       }
     }
   }
   return true;
 }
 
-
 SpillRange* RegisterAllocationData::AssignSpillRangeToLiveRange(
     TopLevelLiveRange* range) {
   DCHECK(!range->HasSpillOperand());
 
   SpillRange* spill_range = range->GetAllocatedSpillRange();
   if (spill_range == nullptr) {
     DCHECK(!range->IsSplinter());
     spill_range = new (allocation_zone()) SpillRange(range, allocation_zone());
   }
   range->set_spill_type(TopLevelLiveRange::SpillType::kSpillRange);
@@ skipping 754 matching lines @@
   if (it == phi_hints_.end()) return;
   DCHECK(!it->second->IsResolved());
   it->second->ResolveHint(use_pos);
 }
 
 
 void LiveRangeBuilder::Verify() const {
   for (auto& hint : phi_hints_) {
     CHECK(hint.second->IsResolved());
   }
-  for (TopLevelLiveRange* current : data()->live_ranges()) {
-    if (current != nullptr && !current->IsEmpty()) current->Verify();
+  for (const TopLevelLiveRange* current : data()->live_ranges()) {
+    if (current != nullptr && !current->IsEmpty()) {
+      // New LiveRanges should not be split.
+      CHECK_NULL(current->next());
+      // General integrity check.
+      current->Verify();
+      const UseInterval* first = current->first_interval();

[titzer, 2016/03/04 19:43:59]

I think you can simplify this code a bit.

E.g. just peel off the first iteration of the loop so that we first check:
CHECK(NextIntervalStartsInDifferenbBlocks(first));

and then the loop starts at first->next()

[Mircea Trofin, 2016/03/04 20:02:00]

Done.

+      if (first->next() == nullptr) continue;
+
+      for (const UseInterval* i = first; i != nullptr; i = i->next()) {
+        if (i != first) {
+          // Except for the first interval, the other intevals must start at
+          // a block boundary, otherwise data wouldn't flow to them.
+          DCHECK(IntervalStartsAtBlockBoundary(i));
+          // The last instruction of the predecessors of the block the interval
+          // starts must be covered by the range.
+          DCHECK(IntervalPredecessorsCoveredByRange(i, current));
+        }
+        if (i->next() != nullptr) {
+          // Consecutive intervals should not end and start in the same block,
+          // otherwise the intervals should have been joined, because the
+          // variable is live throughout that block.
+          DCHECK(NextIntervalStartsInDifferenbBlocks(i));
+        }
+      }
+    }
   }
 }
 
+bool LiveRangeBuilder::IntervalStartsAtBlockBoundary(
+    const UseInterval* interval) const {
+  LifetimePosition start = interval->start();
+  if (!start.IsFullStart()) return false;
+  int instruction_index = start.ToInstructionIndex();
+  const InstructionBlock* block =
+      data()->code()->GetInstructionBlock(instruction_index);
+  return block->first_instruction_index() == instruction_index;
+}
+
+bool LiveRangeBuilder::IntervalPredecessorsCoveredByRange(
+    const UseInterval* interval, const TopLevelLiveRange* range) const {
+  LifetimePosition start = interval->start();
+  int instruction_index = start.ToInstructionIndex();
+  const InstructionBlock* block =
+      data()->code()->GetInstructionBlock(instruction_index);
+  for (RpoNumber pred_index : block->predecessors()) {
+    const InstructionBlock* predecessor =
+        data()->code()->InstructionBlockAt(pred_index);
+    LifetimePosition last_pos = LifetimePosition::GapFromInstructionIndex(
+        predecessor->last_instruction_index());
+    last_pos = last_pos.NextStart().End();
+    if (!range->Covers(last_pos)) return false;
+  }
+  return true;
+}
+
+bool LiveRangeBuilder::NextIntervalStartsInDifferenbBlocks(
+    const UseInterval* interval) const {
+  DCHECK_NOT_NULL(interval->next());
+  LifetimePosition end = interval->end();
+  LifetimePosition next_start = interval->next()->start();
+  const InstructionBlock* block =
+      data()->code()->GetInstructionBlock(end.ToInstructionIndex());
+  const InstructionBlock* next_block =
+      data()->code()->GetInstructionBlock(next_start.ToInstructionIndex());
+  return block->rpo_number() < next_block->rpo_number();
+}
 
 RegisterAllocator::RegisterAllocator(RegisterAllocationData* data,
                                      RegisterKind kind)
     : data_(data),
       mode_(kind),
       num_registers_(GetRegisterCount(data->config(), kind)),
       num_allocatable_registers_(
           GetAllocatableRegisterCount(data->config(), kind)),
       allocatable_register_codes_(
           GetAllocatableRegisterCodes(data->config(), kind)) {}
@@ skipping 1240 matching lines @@
                            spill_operand);
       }
     }
   }
 }
 
 
 }  // namespace compiler
 }  // namespace internal
 }  // namespace v8