Keep list of uses sorted when building it.

runtime/vm/flow_graph_allocator.cc

 // Copyright (c) 2013, 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.h"
@@ skipping 246 matching lines @@
   // Process initial definitions, ie, constants and incoming parameters.
   for (intptr_t i = 0; i < graph_entry_->initial_definitions()->length(); i++) {
     Definition* def = (*graph_entry_->initial_definitions())[i];
     const intptr_t vreg = def->ssa_temp_index();
     kill_[graph_entry_->postorder_number()]->Add(vreg);
     live_in_[graph_entry_->postorder_number()]->Remove(vreg);
   }
 }
 
 
-void LiveRange::AddUse(intptr_t pos, Location* location_slot) {
+UsePosition* LiveRange::AddUse(intptr_t pos, Location* location_slot) {

[srdjan, 2014/09/25 16:32:43]

Who is using result of LiveRange::AddUse?

   ASSERT(location_slot != NULL);
   ASSERT((first_use_interval_->start_ <= pos) &&
          (pos <= first_use_interval_->end_));
-  if ((uses_ != NULL) &&
-      (uses_->pos() == pos) &&
-      (uses_->location_slot() == location_slot)) {
-    return;
+  if (uses_ != NULL) {
+    if ((uses_->pos() == pos) &&
+        (uses_->location_slot() == location_slot)) {
+      return uses_;
+    } else if (uses_->pos() < pos) {
+      // If an instruction at position P is using the same value both as
+      // a fixed register input and a non-fixed input (in this order) we will
+      // add uses both at position P-1 and *then* P which will make
+      // uses_ unsorted unless we account for it here.
+      UsePosition* insert_after = uses_;
+      while ((insert_after->next() != NULL) &&
+             (insert_after->next()->pos() < pos)) {
+        insert_after = insert_after->next();
+      }
+
+      UsePosition* insert_before = insert_after->next();
+      while (insert_before != NULL && (insert_before->pos() == pos)) {
+        if (insert_before->location_slot() == location_slot) {
+          return insert_before;
+        }
+        insert_before = insert_before->next();
+      }
+
+      insert_after->set_next(
+          new UsePosition(pos, insert_after->next(), location_slot));
+      return insert_after->next();
+    }
   }
   uses_ = new UsePosition(pos, uses_, location_slot);
+  return uses_;
 }
 
 
 void LiveRange::AddSafepoint(intptr_t pos, LocationSummary* locs) {
   ASSERT(IsInstructionStartPosition(pos));
   SafepointPosition* safepoint =
       new SafepointPosition(ToInstructionEnd(pos), locs);
 
   if (first_safepoint_ == NULL) {
     ASSERT(last_safepoint_ == NULL);
     first_safepoint_ = last_safepoint_ = safepoint;
   } else {
     ASSERT(last_safepoint_ != NULL);
     // We assume that safepoints list is sorted by position and that
     // safepoints are added in this order.
     ASSERT(last_safepoint_->pos() < pos);
     last_safepoint_->set_next(safepoint);
     last_safepoint_ = safepoint;
   }
 }
 
 
 void LiveRange::AddHintedUse(intptr_t pos,
                              Location* location_slot,
                              Location* hint) {
   ASSERT(hint != NULL);
-  AddUse(pos, location_slot);
-  uses_->set_hint(hint);
+  AddUse(pos, location_slot)->set_hint(hint);
 }
 
 
 void LiveRange::AddUseInterval(intptr_t start, intptr_t end) {
   ASSERT(start < end);
 
   // Live ranges are being build by visiting instructions in post-order.
   // This implies that use intervals will be prepended in a monotonically
   // decreasing order.
   if (first_use_interval() != NULL) {
@@ skipping 777 matching lines @@
     ASSERT(input != NULL);
     // Output register will contain a value of the first input at instruction's
     // start. Expected shape of live ranges:
     //
     //                 i  i'
     //    input #0   --*
     //    output       [----
     //
     ASSERT(in_ref->Equals(Location::RequiresRegister()) ||
            in_ref->Equals(Location::RequiresFpuRegister()));
-
-    // TODO(johnmccutchan): Without this I get allocated a register instead
-    // of an FPU register. Figure out why.
-
     *out = *in_ref;
     // Create move that will copy value between input and output.
     MoveOperands* move = AddMoveAt(pos,
                                    Location::RequiresRegister(),
                                    Location::Any());
 
     // Add uses to the live range of the input.
     LiveRange* input_range = GetLiveRange(input_vreg);
     input_range->AddUseInterval(block->start_pos(), pos);
     input_range->AddUse(pos, move->src_slot());
@@ skipping 448 matching lines @@
   first_register_use_ = range->first_use();
   first_register_beneficial_use_ = range->first_use();
   first_hinted_use_ = range->first_use();
 }
 
 
 bool AllocationFinger::Advance(const intptr_t start) {
   UseInterval* a = first_pending_use_interval_;
   while (a != NULL && a->end() <= start) a = a->next();
   first_pending_use_interval_ = a;
-  if (first_pending_use_interval_ == NULL) {
-    return true;
-  }
-  return false;
+  return (first_pending_use_interval_ == NULL);
 }
 
 
 Location AllocationFinger::FirstHint() {
   UsePosition* use = first_hinted_use_;
 
   while (use != NULL) {
     if (use->HasHint()) return use->hint();
     use = use->next();
   }
@@ skipping 82 matching lines @@
       a = a->next();
     } else {
       u = u->next();
     }
   }
 
   return kMaxPosition;
 }
 
 
-LiveRange* LiveRange::MakeTemp(intptr_t pos, Location* location_slot) {
-  UNREACHABLE();
-  return NULL;
-}
-
-
 template<typename PositionType>
 PositionType* SplitListOfPositions(PositionType** head,
                                    intptr_t split_pos,
                                    bool split_at_start) {
   PositionType* last_before_split = NULL;
   PositionType* pos = *head;
   if (split_at_start) {
     while ((pos != NULL) && (pos->pos() < split_pos)) {
       last_before_split = pos;
       pos = pos->next();
@@ skipping 1249 matching lines @@
     OS::Print("-- [after ssa allocator] ir [%s] -------------\n",
               function.ToFullyQualifiedCString());
     FlowGraphPrinter printer(flow_graph_, true);
     printer.PrintBlocks();
     OS::Print("----------------------------------------------\n");
   }
 }
 
 
 }  // namespace dart