Register allocation tweaks:

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 492 matching lines @@
     if (!use->location_slot()->Equals(Location::Any())) {
       return false;
     }
     use = use->next();
   }
 
   return true;
 }
 
 
+// Returns true if all uses of the given range have Any allocation policy.
+static bool HasOnlyUnconstrainedUses(LiveRange* range) {
+  UsePosition* use = range->first_use();
+  while (use != NULL) {
+    if (!use->location_slot()->Equals(Location::Any())) {
+      return false;
+    }
+    use = use->next();
+  }
+  return true;
+}
+
+
 void FlowGraphAllocator::BuildLiveRanges() {
   const intptr_t block_count = postorder_.length();
   ASSERT(postorder_.Last()->IsGraphEntry());
   BitVector* current_interference_set = NULL;
   for (intptr_t i = 0; i < (block_count - 1); i++) {
     BlockEntryInstr* block = postorder_[i];
 
     BlockInfo* block_info = BlockInfoAt(block->start_pos());
 
     // For every SSA value that is live out of this block, create an interval
     // that covers the whole block.  It will be shortened if we encounter a
     // definition of this value in this block.
     for (BitVector::Iterator it(live_out_[i]); !it.Done(); it.Advance()) {
       LiveRange* range = GetLiveRange(it.Current());
       range->AddUseInterval(block->start_pos(), block->end_pos());
     }
 
     BlockInfo* loop_header = block_info->loop_header();
     if ((loop_header != NULL) && (loop_header->last_block() == block)) {
       current_interference_set =
           new BitVector(flow_graph_.max_virtual_register_number());
       ASSERT(loop_header->backedge_interference() == NULL);
+      // All values flowing into the loop header are live at the back-edge and
+      // can interfere with phi moves.
+      current_interference_set->AddAll(
+          live_in_[loop_header->entry()->postorder_number()]);
       loop_header->set_backedge_interference(
           current_interference_set);
     }
 
     // Connect outgoing phi-moves that were created in NumberInstructions
     // and find last instruction that contributes to liveness.
     Instruction* current = ConnectOutgoingPhiMoves(block,
                                                    current_interference_set);
 
     // Now process all instructions in reverse order.
@@ skipping 276 matching lines @@
 
 
 // Create and update live ranges corresponding to instruction's inputs,
 // temporaries and output.
 void FlowGraphAllocator::ProcessOneInstruction(BlockEntryInstr* block,
                                                Instruction* current,
                                                BitVector* interference_set) {
   LocationSummary* locs = current->locs();
 
   Definition* def = current->AsDefinition();
-  if ((def != NULL) &&
-      (def->AsConstant() != NULL) &&
-      ((def->ssa_temp_index() == -1) ||
-       (GetLiveRange(def->ssa_temp_index())->first_use() == NULL))) {
+  if ((def != NULL) && (def->AsConstant() != NULL)) {
+    LiveRange* range = (def->ssa_temp_index() != -1) ?
+        GetLiveRange(def->ssa_temp_index()) : NULL;
+
     // Drop definitions of constants that have no uses.
-    locs->set_out(Location::NoLocation());
-    return;
+    if ((range == NULL) || (range->first_use() == NULL)) {
+      locs->set_out(Location::NoLocation());
+      return;
+    }
+
+    // If this constant has only unconstrained uses convert them all
+    // to use the constant directly and drop this definition.
+    // TODO(vegorov) improve allocation when we have enough registers to keep

[Florian Schneider, 2013/03/21 13:17:06]

insert : after the TODO(vegorov).

[Vyacheslav Egorov (Google), 2013/03/22 11:30:35]

Done.

+    // constants used in the loop in them.
+    if (HasOnlyUnconstrainedUses(range)) {
+      const Object& value = def->AsConstant()->value();
+      range->set_assigned_location(Location::Constant(value));
+      range->set_spill_slot(Location::Constant(value));
+      range->finger()->Initialize(range);
+      ConvertAllUses(range);
+
+      locs->set_out(Location::NoLocation());
+      return;
+    }
   }
 
   const intptr_t pos = current->lifetime_position();
   ASSERT(IsInstructionStartPosition(pos));
 
   // Number of input locations and number of input operands have to agree.
   ASSERT(locs->input_count() == current->InputCount());
 
   // Normalize same-as-first-input output if input is specified as
   // fixed register.
@@ skipping 854 matching lines @@
     if (!blocked_registers_[hint.register_code()]) {
       free_until = FirstIntersectionWithAllocated(hint.register_code(),
                                                   unallocated);
       candidate = hint.register_code();
     }
 
     TRACE_ALLOC(OS::Print("found hint %s for v%"Pd": free until %"Pd"\n",
                           hint.Name(),
                           unallocated->vreg(),
                           free_until));
-  } else if (free_until != kMaxPosition) {
+  } else {
     for (intptr_t reg = 0; reg < NumberOfRegisters(); ++reg) {
       if (!blocked_registers_[reg] && (registers_[reg].length() == 0)) {
         candidate = reg;
         free_until = kMaxPosition;
         break;
       }
     }
   }
 
+  ASSERT(0 <= kMaxPosition);
+  if (free_until != kMaxPosition) {
+    for (intptr_t reg = 0; reg < NumberOfRegisters(); ++reg) {
+      if (blocked_registers_[reg] || (reg == candidate)) continue;
+      const intptr_t intersection =
+          FirstIntersectionWithAllocated(reg, unallocated);
+      if (intersection > free_until) {
+        candidate = reg;
+        free_until = intersection;
+        if (free_until == kMaxPosition) break;
+      }
+    }
+  }
+
+  // All registers are blocked by active ranges.
+  if (free_until <= unallocated->Start()) return false;
+
   // We have a very good candidate (either hinted to us or completely free).
   // If we are in a loop try to reduce number of moves on the back edge by
   // searching for a candidate that does not interfere with phis on the back
   // edge.
   BlockInfo* loop_header = BlockInfoAt(unallocated->Start())->loop_header();
   if ((unallocated->vreg() >= 0) &&
       (loop_header != NULL) &&
       (free_until >= loop_header->last_block()->end_pos()) &&
       loop_header->backedge_interference()->Contains(unallocated->vreg())) {
     ASSERT(static_cast<intptr_t>(kNumberOfFpuRegisters) <=
@@ skipping 39 matching lines @@
           TRACE_ALLOC(OS::Print(
               "found %s for v%"Pd" with no interference on the back edge\n",
               MakeRegisterLocation(candidate, kUnboxedDouble).Name(),
               candidate));
           break;
         }
       }
     }
   }
 
-  ASSERT(0 <= kMaxPosition);
-  if (free_until != kMaxPosition) {
-    for (intptr_t reg = 0; reg < NumberOfRegisters(); ++reg) {
-      if (blocked_registers_[reg] || (reg == candidate)) continue;
-      const intptr_t intersection =
-          FirstIntersectionWithAllocated(reg, unallocated);
-      if (intersection > free_until) {
-        candidate = reg;
-        free_until = intersection;
-        if (free_until == kMaxPosition) break;
-      }
-    }
-  }
-
-  // All registers are blocked by active ranges.
-  if (free_until <= unallocated->Start()) return false;
-
   TRACE_ALLOC(OS::Print("assigning free register "));
   TRACE_ALLOC(MakeRegisterLocation(candidate, kUnboxedDouble).Print());
   TRACE_ALLOC(OS::Print(" to v%"Pd"\n", unallocated->vreg()));
 
   if (free_until != kMaxPosition) {
     // There was an intersection. Split unallocated.
     TRACE_ALLOC(OS::Print("  splitting at %"Pd"\n", free_until));
     LiveRange* tail = unallocated->SplitAt(free_until);
     AddToUnallocated(tail);
   }
@@ skipping 695 matching lines @@
     OS::Print("-- [after ssa allocator] ir [%s] -------------\n",
               function.ToFullyQualifiedCString());
     FlowGraphPrinter printer(flow_graph_, true);
     printer.PrintBlocks();
     OS::Print("----------------------------------------------\n");
   }
 }
 
 
 }  // namespace dart