Ensure that ia32 build passes all tests with --use-ssa on.

runtime/vm/flow_graph_allocator.cc

 // Copyright (c) 2012, the Dart project authors.  Please see the AUTHORS file
 // for details. All rights reserved. Use of this source code is governed by a
 // BSD-style license that can be found in the LICENSE file.
 
 #include "vm/flow_graph_allocator.h"
 
 #include "vm/bit_vector.h"
 #include "vm/intermediate_language.h"
 #include "vm/il_printer.h"
 #include "vm/flow_graph_builder.h"
@@ skipping 333 matching lines @@
 LiveRange* FlowGraphAllocator::MakeLiveRangeForTemporary() {
   LiveRange* range = new LiveRange(kTempVirtualRegister);
 #if defined(DEBUG)
   temporaries_.Add(range);
 #endif
   return range;
 }
 
 
 // Block location from the start of the instruction to its end.
-void FlowGraphAllocator::BlockLocation(Location loc, intptr_t pos) {
+void FlowGraphAllocator::BlockLocation(Location loc,
+                                       intptr_t from,
+                                       intptr_t to) {
   ASSERT(loc.IsRegister());
-  ASSERT(IsInstructionStartPosition(pos));
   const Register reg = loc.reg();
   if (blocked_cpu_regs_[reg]) return;
   if (cpu_regs_[reg].length() == 0) {
     LiveRange* range = new LiveRange(kNoVirtualRegister);
     cpu_regs_[reg].Add(range);
     range->set_assigned_location(loc);
 #if defined(DEBUG)
     temporaries_.Add(range);
 #endif
   }
-  cpu_regs_[reg][0]->AddUseInterval(pos, pos + 1);
+  cpu_regs_[reg][0]->AddUseInterval(from, to);
 }
 
 
 void LiveRange::Print() {
   if (first_use_interval() == NULL) {
     return;
   }
 
   OS::Print("  live range v%d [%d, %d) in ", vreg(), Start(), End());
   assigned_location().Print();
@@ skipping 298 matching lines @@
     ASSERT(input->IsUse());  // Can not be a constant currently.
     const intptr_t vreg = input->AsUse()->definition()->ssa_temp_index();
     LiveRange* range = GetLiveRange(vreg);
 
     Location* in_ref = locs->in_slot(j);
 
     if (in_ref->IsRegister()) {
       // Input is expected in a fixed register. Expected shape of
       // live ranges:
       //
-      //                 i  i'
+      //                 j' i  i'
       //      value    --*
-      //      register   [--)
+      //      register   [-----)
       //
       MoveOperands* move =
-          AddMoveAt(pos, *in_ref, Location::PrefersRegister());
-      BlockLocation(*in_ref, pos);
-      range->AddUseInterval(block->start_pos(), pos);
-      range->AddUse(pos, move->src_slot());
+          AddMoveAt(pos - 1, *in_ref, Location::PrefersRegister());
+      BlockLocation(*in_ref, pos - 1, pos + 1);
+      range->AddUseInterval(block->start_pos(), pos - 1);
+      range->AddUse(pos - 1, move->src_slot());
     } else {
       // Normal unallocated input. Expected shape of
       // live ranges:
       //
       //                 i  i'
       //      value    -----*
       //
       ASSERT(in_ref->IsUnallocated());
       range->AddUseInterval(block->start_pos(), pos + 1);
       range->AddUse(pos + 1, in_ref);
     }
   }
 
   // Process temps.
   for (intptr_t j = 0; j < locs->temp_count(); j++) {
     // Expected shape of live range:
     //
     //              i  i'
     //              [--)
     //
 
     Location temp = locs->temp(j);
     if (temp.IsRegister()) {
-      BlockLocation(temp, pos);
+      BlockLocation(temp, pos, pos + 1);
     } else if (temp.IsUnallocated()) {
       LiveRange* range = MakeLiveRangeForTemporary();
       range->AddUseInterval(pos, pos + 1);
       range->AddUse(pos, locs->temp_slot(j));
       AddToUnallocated(range);
     } else {
       UNREACHABLE();
     }
   }
 
   // Block all allocatable registers for calls.
   if (locs->is_call()) {
     // Expected shape of live range:
     //
     //              i  i'
     //              [--)
     //
 
     for (intptr_t reg = 0; reg < kNumberOfCpuRegisters; reg++) {
       BlockLocation(Location::RegisterLocation(static_cast<Register>(reg)),
-                    pos);
+                    pos,
+                    pos + 1);
     }
 
 #if defined(DEBUG)
     // Verify that temps, inputs and output were specified as fixed
     // locations.  Every register is blocked now so attempt to
     // allocate will not succeed.
     for (intptr_t j = 0; j < locs->temp_count(); j++) {
       ASSERT(!locs->temp(j).IsUnallocated());
     }
 
@@ skipping 24 matching lines @@
   Location* out = locs->out_slot();
 
   // Process output and finalize its liverange.
   if (out->IsRegister()) {
     // Fixed output location. Expected shape of live range:
     //
     //                    i  i' j  j'
     //    register        [--)
     //    output             [-------
     //
-    BlockLocation(*out, pos);
+    BlockLocation(*out, pos, pos + 1);
 
     if (range->vreg() == kTempVirtualRegister) return;
 
     // We need to emit move connecting fixed register with another location
     // that will be allocated for this output's live range.
     // Special case: fixed output followed by a fixed input last use.
     UsePosition* use = range->first_use();
 
     // If the value has no uses we don't need to allocate it.
     if (use == NULL) return;
@@ skipping 275 matching lines @@
         (loc->IsRegister() ||
          (loc->IsUnallocated() && loc->IsRegisterBeneficial()))) {
       first_register_beneficial_use_ = use;
       return use;
     }
   }
   return NULL;
 }
 
 
+void AllocationFinger::UpdateAfterSplit(intptr_t first_use_after_split_pos) {
+  if ((first_register_use_ != NULL) &&
+      (first_register_use_->pos() >= first_use_after_split_pos)) {
+    first_register_use_ = NULL;
+  }
+
+  if ((first_register_beneficial_use_ != NULL) &&
+      (first_register_beneficial_use_->pos() >= first_use_after_split_pos)) {
+    first_register_beneficial_use_ = NULL;
+  }
+}
+
+
 intptr_t UseInterval::Intersect(UseInterval* other) {
   if (this->start() <= other->start()) {
     if (other->start() < this->end()) return other->start();
   } else if (this->start() < other->end()) {
     return this->start();
   }
   return kIllegalPosition;
 }
 
 
@@ skipping 21 matching lines @@
 
 LiveRange* LiveRange::SplitAt(intptr_t split_pos) {
   if (Start() == split_pos) return this;
 
   UseInterval* interval = finger_.first_pending_use_interval();
   if (interval == NULL) {
     finger_.Initialize(this);
     interval = finger_.first_pending_use_interval();
   }
 
-  ASSERT(interval->start() < split_pos);
   ASSERT(split_pos < End());
 
   // Corner case. We need to start over to find previous interval.
   if (interval->start() == split_pos) interval = first_use_interval_;
 
   UseInterval* last_before_split = NULL;
   while (interval->end() <= split_pos) {
     last_before_split = interval;
     interval = interval->next();
   }
@@ skipping 41 matching lines @@
                                 first_use_after_split,
                                 first_after_split,
                                 last_use_interval,
                                 next_sibling_);
 
   TRACE_ALLOC(("  split sibling [%d, %d)\n",
                next_sibling_->Start(), next_sibling_->End()));
 
   last_use_interval_ = last_before_split;
   last_use_interval_->next_ = NULL;
+
+  if (first_use_after_split != NULL) {
+    finger_.UpdateAfterSplit(first_use_after_split->pos());
+  }
+
   return next_sibling_;
 }
 
 
 LiveRange* FlowGraphAllocator::SplitBetween(LiveRange* range,
                                             intptr_t from,
                                             intptr_t to) {
   TRACE_ALLOC(("split %d [%d, %d) between [%d, %d)\n",
                range->vreg(), range->Start(), range->End(), from, to));
 
@@ skipping 229 matching lines @@
   intptr_t blocked_at = kMaxPosition;
   const intptr_t start = unallocated->Start();
 
   for (intptr_t i = 0; i < cpu_regs_[reg].length(); i++) {
     LiveRange* allocated = cpu_regs_[reg][i];
 
     UseInterval* first_pending_use_interval =
         allocated->finger()->first_pending_use_interval();
     if (first_pending_use_interval->Contains(start)) {
       // This is an active interval.
-      if (allocated->vreg() <= 0) {
+      if (allocated->vreg() < 0) {
         // This register blocked by an interval that
         // can't be spilled.
         return false;
       }
 
       const UsePosition* use =
         allocated->finger()->FirstRegisterBeneficialUse(unallocated->Start());
 
       if ((use != NULL) && ((use->pos() - start) <= 1)) {
         // This register is blocked by interval that is used
@@ skipping 358 matching lines @@
   NumberInstructions();
 
   DiscoverLoops();
 
   BuildLiveRanges();
 
   if (FLAG_print_ssa_liveness) {
     DumpLiveness();
   }
 
+  if (FLAG_print_ssa_liveranges) {
+    const Function& function = builder_->parsed_function().function();
+
+    OS::Print("-- [before ssa allocator] ranges [%s] ---------\n",
+              function.ToFullyQualifiedCString());
+    PrintLiveRanges();
+    OS::Print("----------------------------------------------\n");
+
+    OS::Print("-- [before ssa allocator] ir [%s] -------------\n",
+              function.ToFullyQualifiedCString());
+    FlowGraphPrinter printer(Function::Handle(), block_order_, true);
+    printer.PrintBlocks();
+    OS::Print("----------------------------------------------\n");
+  }
+
   AllocateCPURegisters();
 
   ResolveControlFlow();
 
   GraphEntryInstr* entry = block_order_[0]->AsGraphEntry();
   ASSERT(entry != NULL);
   entry->set_spill_slot_count(spill_slots_.length());
 
   if (FLAG_print_ssa_liveranges) {
     const Function& function = builder_->parsed_function().function();
 
     OS::Print("-- [after ssa allocator] ranges [%s] ---------\n",
               function.ToFullyQualifiedCString());
     PrintLiveRanges();
     OS::Print("----------------------------------------------\n");
 
     OS::Print("-- [after ssa allocator] ir [%s] -------------\n",
               function.ToFullyQualifiedCString());
     FlowGraphPrinter printer(Function::Handle(), block_order_, true);
     printer.PrintBlocks();
     OS::Print("----------------------------------------------\n");
   }
 }
 
 
 }  // namespace dart