Implement a simple register allocator that tries to keep instruction results in registers.

runtime/vm/intermediate_language_x64.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/globals.h"  // Needed here to get TARGET_ARCH_X64.
 #if defined(TARGET_ARCH_X64)
 
 #include "vm/intermediate_language.h"
 
 #include "lib/error.h"
@@ skipping 10 matching lines @@
 DECLARE_FLAG(int, optimization_counter_threshold);
 DECLARE_FLAG(bool, trace_functions);
 
 void BindInstr::EmitNativeCode(FlowGraphCompiler* compiler) {
   computation()->EmitNativeCode(compiler);
   if (locs()->out().kind() == Location::kRegister) {
     // TODO(vegorov): this should really happen only for comparisons fused
     // with branches.  Currrently IR does not provide an easy way to remove
     // instructions from the graph so we just leave fused comparison in it
     // but change its result location to be NoLocation.
-    __ pushq(locs()->out().reg());
+    compiler->frame_register_allocator()->Push(locs()->out().reg(), this);
   }
 }
 
 
 LocationSummary* ReturnInstr::MakeLocationSummary() const {
   const intptr_t kNumInputs = 1;
   const intptr_t kNumTemps = 1;
   LocationSummary* locs = new LocationSummary(kNumInputs, kNumTemps);
   locs->set_in(0, Location::RegisterLocation(RAX));
   locs->set_temp(0, Location::RequiresRegister());
@@ skipping 56 matching lines @@
   compiler->AddCurrentDescriptor(PcDescriptors::kReturn,
                                  cid(),
                                  token_index(),
                                  CatchClauseNode::kInvalidTryIndex);
 }
 
 
 // Generic summary for call instructions that have all arguments pushed
 // on the stack and return the result in a fixed register RAX.
 LocationSummary* Computation::MakeCallSummary() {
-  LocationSummary* result = new LocationSummary(0, 0);
+  LocationSummary* result = new LocationSummary(0, 0, LocationSummary::kCall);
   result->set_out(Location::RegisterLocation(RAX));
   return result;
 }
 
 
 LocationSummary* ClosureCallComp::MakeLocationSummary() const {
   const intptr_t kNumInputs = 0;
   const intptr_t kNumTemps = 1;
-  LocationSummary* result = new LocationSummary(kNumInputs, kNumTemps);
+  LocationSummary* result = new LocationSummary(kNumInputs,
+                                                kNumTemps,
+                                                LocationSummary::kCall);
   result->set_out(Location::RegisterLocation(RAX));
   result->set_temp(0, Location::RegisterLocation(R10));  // Arg. descriptor.
   return result;
 }
 
 
 LocationSummary* LoadLocalComp::MakeLocationSummary() const {
   return LocationSummary::Make(0, Location::RequiresRegister());
 }
 
@@ skipping 63 matching lines @@
                                 kConditionTypeErrorRuntimeEntry);
   // We should never return here.
   __ int3();
 
   __ Bind(&done);
   ASSERT(obj == result);
 }
 
 
 LocationSummary* EqualityCompareComp::MakeLocationSummary() const {
+  const LocationSummary::ContainsBranch contains_branch =
+      is_fused_with_branch() ? LocationSummary::kBranch
+                             : LocationSummary::kNoBranch;
+
   const intptr_t kNumInputs = 2;
   if ((NumTargets() == 1) && (ClassIdAt(0) == kSmi)) {
     const intptr_t kNumTemps = 1;
-    LocationSummary* locs = new LocationSummary(kNumInputs, kNumTemps);
+    LocationSummary* locs = new LocationSummary(kNumInputs,
+                                                kNumTemps,
+                                                LocationSummary::kNoCall,
+                                                contains_branch);
     locs->set_in(0, Location::RequiresRegister());
     locs->set_in(1, Location::RequiresRegister());
     locs->set_temp(0, Location::RequiresRegister());
     if (!is_fused_with_branch()) {
       locs->set_out(Location::RequiresRegister());
     }
     return locs;
   }
   if (NumTargets() > 0) {
     const intptr_t kNumTemps = 1;
-    LocationSummary* locs = new LocationSummary(kNumInputs, kNumTemps);
+    LocationSummary* locs = new LocationSummary(kNumInputs,
+                                                kNumTemps,
+                                                LocationSummary::kCall,
+                                                contains_branch);
     locs->set_in(0, Location::RequiresRegister());
     locs->set_in(1, Location::RequiresRegister());
     locs->set_temp(0, Location::RequiresRegister());
     if (!is_fused_with_branch()) {
       locs->set_out(Location::RegisterLocation(RAX));
     }
     return locs;
   }
   const intptr_t kNumTemps = 0;
-  LocationSummary* locs = new LocationSummary(kNumInputs, kNumTemps);
+  LocationSummary* locs = new LocationSummary(kNumInputs,
+                                              kNumTemps,
+                                              LocationSummary::kCall,
+                                              contains_branch);
   locs->set_in(0, Location::RequiresRegister());
   locs->set_in(1, Location::RequiresRegister());
   if (!is_fused_with_branch()) {
     locs->set_out(Location::RegisterLocation(RAX));
   }
   return locs;
 }
 
 
 static void EmitSmiEqualityCompare(FlowGraphCompiler* compiler,
@@ skipping 170 matching lines @@
 void EqualityCompareComp::EmitNativeCode(FlowGraphCompiler* compiler) {
   if ((NumTargets() == 1) && (ClassIdAt(0) == kSmi)) {
     EmitSmiEqualityCompare(compiler, this);
     return;
   }
   EmitGenericEqualityCompare(compiler, this);
 }
 
 
 LocationSummary* RelationalOpComp::MakeLocationSummary() const {
+  const LocationSummary::ContainsBranch contains_branch =
+      is_fused_with_branch() ? LocationSummary::kBranch
+                             : LocationSummary::kNoBranch;
+
   if (operands_class_id() == kSmi || operands_class_id() == kDouble) {
     const intptr_t kNumInputs = 2;
     const intptr_t kNumTemps = 1;
-    LocationSummary* summary = new LocationSummary(kNumInputs, kNumTemps);
+    LocationSummary* summary = new LocationSummary(kNumInputs,
+                                                   kNumTemps,
+                                                   LocationSummary::kCall,
+                                                   contains_branch);
     summary->set_in(0, Location::RequiresRegister());
     summary->set_in(1, Location::RequiresRegister());
     if (!is_fused_with_branch()) {
       summary->set_out(Location::RequiresRegister());
     }
     summary->set_temp(0, Location::RequiresRegister());
     return summary;
   }
   ASSERT(!is_fused_with_branch());
   ASSERT(operands_class_id() == kObject);
@@ skipping 123 matching lines @@
                                  try_index(),
                                  function_name,
                                  kNumArguments,
                                  Array::ZoneHandle(),  // No optional arguments.
                                  kNumArgsChecked);
   ASSERT(locs()->out().reg() == RAX);
 }
 
 
 LocationSummary* NativeCallComp::MakeLocationSummary() const {
-  LocationSummary* locs = new LocationSummary(0, 3);
+  const intptr_t kNumInputs = 0;
+  const intptr_t kNumTemps = 3;
+  LocationSummary* locs = new LocationSummary(kNumInputs,
+                                              kNumTemps,
+                                              LocationSummary::kCall);
   locs->set_temp(0, Location::RegisterLocation(RAX));
   locs->set_temp(1, Location::RegisterLocation(RBX));
   locs->set_temp(2, Location::RegisterLocation(R10));
   locs->set_out(Location::RequiresRegister());
   return locs;
 }
 
 
 void NativeCallComp::EmitNativeCode(FlowGraphCompiler* compiler) {
   ASSERT(locs()->temp(0).reg() == RAX);
@@ skipping 198 matching lines @@
     }
 
     default:
       UNREACHABLE();
       break;
   }
 }
 
 
 LocationSummary* InstanceSetterComp::MakeLocationSummary() const {
-  const intptr_t kNumInputs = 2;
-  return LocationSummary::Make(kNumInputs, Location::NoLocation());
-  return NULL;
+  return MakeCallSummary();
 }
 
 
 void InstanceSetterComp::EmitNativeCode(FlowGraphCompiler* compiler) {
-  Register receiver = locs()->in(0).reg();
-  Register value = locs()->in(1).reg();
-
-  // Preserve the value (second argument) under the arguments as the result
-  // of the computation, then call the setter.
   const String& function_name =
       String::ZoneHandle(Field::SetterSymbol(field_name()));
 
-  __ pushq(receiver);
-  __ pushq(value);
   compiler->AddCurrentDescriptor(PcDescriptors::kDeopt,
                                  cid(),
                                  token_index(),
                                  try_index());
   const intptr_t kArgumentCount = 2;
   const intptr_t kCheckedArgumentCount = 1;
   compiler->GenerateInstanceCall(cid(),
                                  token_index(),
                                  try_index(),
                                  function_name,
@@ skipping 95 matching lines @@
 }
 
 
 LocationSummary* CreateArrayComp::MakeLocationSummary() const {
   // TODO(regis): The elements of the array could be considered as arguments to
   // CreateArrayComp, thereby making CreateArrayComp a call.
   // For VerifyCallComputation to work, CreateArrayComp would need an
   // ArgumentCount getter and an ArgumentAt getter.
   const intptr_t kNumInputs = 1;
   const intptr_t kNumTemps = 1;
-  LocationSummary* locs = new LocationSummary(kNumInputs, kNumTemps);
+  LocationSummary* locs = new LocationSummary(kNumInputs,
+                                              kNumTemps,
+                                              LocationSummary::kCall);
   locs->set_in(0, Location::RegisterLocation(RBX));
   locs->set_temp(0, Location::RegisterLocation(R10));
   locs->set_out(Location::RegisterLocation(RAX));
   return locs;
 }
 
 
 void CreateArrayComp::EmitNativeCode(FlowGraphCompiler* compiler) {
   Register temp_reg = locs()->temp(0).reg();
   Register result_reg = locs()->out().reg();
@@ skipping 11 matching lines @@
   __ leaq(temp_reg, FieldAddress(result_reg, Array::data_offset()));
   for (int i = ElementCount() - 1; i >= 0; --i) {
     ASSERT(ElementAt(i)->IsUse());
     __ popq(Address(temp_reg, i * kWordSize));
   }
 }
 
 
 LocationSummary* AllocateObjectWithBoundsCheckComp::
     MakeLocationSummary() const {
-  return LocationSummary::Make(2, Location::RequiresRegister());
+  return LocationSummary::Make(2,
+                               Location::RequiresRegister(),
+                               LocationSummary::kCall);
 }
 
 
 void AllocateObjectWithBoundsCheckComp::EmitNativeCode(
     FlowGraphCompiler* compiler) {
   const Class& cls = Class::ZoneHandle(constructor().owner());
   Register type_arguments = locs()->in(0).reg();
   Register instantiator_type_arguments = locs()->in(1).reg();
   Register result = locs()->out().reg();
 
@@ skipping 35 matching lines @@
     compiler->EmitClassChecksNoSmi(*class_ids(), instance, result, deopt);
   }
 
   __ movq(result, FieldAddress(instance, offset_in_bytes()));
 }
 
 
 LocationSummary* InstantiateTypeArgumentsComp::MakeLocationSummary() const {
   const intptr_t kNumInputs = 1;
   const intptr_t kNumTemps = 0;
-  LocationSummary* locs = new LocationSummary(kNumInputs, kNumTemps);
+  LocationSummary* locs = new LocationSummary(kNumInputs,
+                                              kNumTemps,
+                                              LocationSummary::kCall);
   locs->set_in(0, Location::RequiresRegister());
   locs->set_out(Location::SameAsFirstInput());
   return locs;
 }
 
 
 void InstantiateTypeArgumentsComp::EmitNativeCode(
     FlowGraphCompiler* compiler) {
   Register instantiator_reg = locs()->in(0).reg();
   Register result_reg = locs()->out().reg();
@@ skipping 158 matching lines @@
             Immediate(Smi::RawValue(StubCode::kNoInstantiator)));
   }
   __ Bind(&done);
   // instantiator_reg: instantiator or kNoInstantiator.
 }
 
 
 LocationSummary* AllocateContextComp::MakeLocationSummary() const {
   const intptr_t kNumInputs = 0;
   const intptr_t kNumTemps = 1;
-  LocationSummary* locs = new LocationSummary(kNumInputs, kNumTemps);
+  LocationSummary* locs = new LocationSummary(kNumInputs,
+                                              kNumTemps,
+                                              LocationSummary::kCall);
   locs->set_temp(0, Location::RegisterLocation(R10));
   locs->set_out(Location::RegisterLocation(RAX));
   return locs;
 }
 
 
 void AllocateContextComp::EmitNativeCode(FlowGraphCompiler* compiler) {
   ASSERT(locs()->temp(0).reg() == R10);
 
   __ movq(R10, Immediate(num_context_variables()));
   const ExternalLabel label("alloc_context",
                             StubCode::AllocateContextEntryPoint());
   compiler->GenerateCall(token_index(),
                          try_index(),
                          &label,
                          PcDescriptors::kOther);
 }
 
 
 LocationSummary* CloneContextComp::MakeLocationSummary() const {
-  return LocationSummary::Make(1, Location::RequiresRegister());
+  return LocationSummary::Make(1,
+                               Location::RequiresRegister(),
+                               LocationSummary::kCall);
 }
 
 
 void CloneContextComp::EmitNativeCode(FlowGraphCompiler* compiler) {
   Register context_value = locs()->in(0).reg();
   Register result = locs()->out().reg();
 
   __ PushObject(Object::ZoneHandle());  // Make room for the result.
   __ pushq(context_value);
   compiler->GenerateCallRuntime(cid(),
@@ skipping 26 matching lines @@
   __ movq(Address(RBP, exception_var().index() * kWordSize),
           kExceptionObjectReg);
   __ movq(Address(RBP, stacktrace_var().index() * kWordSize),
           kStackTraceObjectReg);
 }
 
 
 LocationSummary* CheckStackOverflowComp::MakeLocationSummary() const {
   const intptr_t kNumInputs = 0;
   const intptr_t kNumTemps = 1;
-  LocationSummary* summary = new LocationSummary(kNumInputs, kNumTemps);
+  // TODO(vegorov): spilling is required only on infrequently executed path.

[srdjan, 2012/06/18 16:33:20]

A quick fix could be to use the deoptimization stub for the this kind of "stack
checks"

[Vyacheslav Egorov (Google), 2012/06/18 17:51:16]

Yes, I agree. 

In V8 we have a generic "deferred code facility for this kind of stuff (calls to
runtime from deferred code are surrounded by register spilling). Call to the
stack overflow runtime routine is done from this deferred code. 

+  LocationSummary* summary = new LocationSummary(kNumInputs,
+                                                 kNumTemps,
+                                                 LocationSummary::kCall);
   summary->set_temp(0, Location::RequiresRegister());
   return summary;
 }
 
 
 void CheckStackOverflowComp::EmitNativeCode(FlowGraphCompiler* compiler) {
   Register temp = locs()->temp(0).reg();
   // Generate stack overflow check.
   __ movq(temp, Immediate(Isolate::Current()->stack_limit_address()));
   __ cmpq(RSP, Address(temp, 0));
   Label no_stack_overflow;
   __ j(ABOVE, &no_stack_overflow, Assembler::kNearJump);
   compiler->GenerateCallRuntime(cid(),
                                 token_index(),
                                 try_index(),
                                 kStackOverflowRuntimeEntry);
   __ Bind(&no_stack_overflow);
 }
 
 
 LocationSummary* BinaryOpComp::MakeLocationSummary() const {
   const intptr_t kNumInputs = 2;
 
   if (operands_type() == kDoubleOperands) {
-    const intptr_t kNumTemps = 1;
-    LocationSummary* summary = new LocationSummary(kNumInputs, kNumTemps);
-    summary->set_in(0, Location::RequiresRegister());
-    summary->set_in(1, Location::RequiresRegister());
-    summary->set_out(Location::RegisterLocation(RAX));
-    summary->set_temp(0, Location::RequiresRegister());
-    return summary;
+    return MakeCallSummary();  // Calls into a stub for allocation.
   }
 
   ASSERT(operands_type() == kSmiOperands);
 
   if (op_kind() == Token::kTRUNCDIV) {
     const intptr_t kNumTemps = 3;
     LocationSummary* summary = new LocationSummary(kNumInputs, kNumTemps);
     summary->set_in(0, Location::RegisterLocation(RAX));
     summary->set_in(1, Location::RegisterLocation(RCX));
     summary->set_out(Location::SameAsFirstInput());
@@ skipping 158 matching lines @@
     }
     default:
       UNREACHABLE();
       break;
   }
 }
 
 
 static void EmitDoubleBinaryOp(FlowGraphCompiler* compiler,
                                BinaryOpComp* comp) {
-  Register left = comp->locs()->in(0).reg();
-  Register right = comp->locs()->in(1).reg();
-  Register temp = comp->locs()->temp(0).reg();
+  Register left = RBX;
+  Register right = RCX;
+  Register temp = RDX;
   Register result = comp->locs()->out().reg();
 
   const Class& double_class = compiler->double_class();
   const Code& stub =
     Code::Handle(StubCode::GetAllocationStubForClass(double_class));
   const ExternalLabel label(double_class.ToCString(), stub.EntryPoint());
-  __ pushq(left);
-  __ pushq(right);
   compiler->GenerateCall(comp->instance_call()->token_index(),
                          comp->instance_call()->try_index(),
                          &label,
                          PcDescriptors::kOther);
   // Newly allocated object is now in the result register (RAX).
   ASSERT(result == RAX);
   __ popq(right);
   __ popq(left);
 
   Label* deopt = compiler->AddDeoptStub(comp->instance_call()->cid(),
@@ skipping 79 matching lines @@
     }
   } else {
     UNREACHABLE();
   }
 }
 
 
 LocationSummary* NumberNegateComp::MakeLocationSummary() const {
   const intptr_t kNumInputs = 1;
   const intptr_t kNumTemps = 1;  // Needed for doubles.
-  LocationSummary* summary = new LocationSummary(kNumInputs, kNumTemps);
+  LocationSummary* summary = new LocationSummary(kNumInputs,
+                                                 kNumTemps,
+                                                 LocationSummary::kCall);
   summary->set_in(0, Location::RequiresRegister());
   summary->set_out(Location::SameAsFirstInput());
   summary->set_temp(0, Location::RequiresRegister());
   return summary;
 }
 
 
 void NumberNegateComp::EmitNativeCode(FlowGraphCompiler* compiler) {
   const ICData& ic_data = *instance_call()->ic_data();
   ASSERT(!ic_data.IsNull());
@@ skipping 45 matching lines @@
 LocationSummary* ToDoubleComp::MakeLocationSummary() const {
   const intptr_t kNumInputs = 1;
   if (from() == kDouble) {
     const intptr_t kNumTemps = 0;
     LocationSummary* locs = new LocationSummary(kNumInputs, kNumTemps);
     locs->set_in(0, Location::RequiresRegister());
     locs->set_out(Location::SameAsFirstInput());
     return locs;
   } else {
     ASSERT(from() == kSmi);
-    return LocationSummary::Make(kNumInputs, Location::RegisterLocation(RAX));
+    return MakeCallSummary();
   }
 }
 
 
 void ToDoubleComp::EmitNativeCode(FlowGraphCompiler* compiler) {
-  Register value = locs()->in(0).reg();
+  Register value = (from() == kDouble) ? locs()->in(0).reg() : RBX;
   Register result = locs()->out().reg();
 
   const DeoptReasonId deopt_reason = (from() == kDouble) ?
       kDeoptDoubleToDouble : kDeoptIntegerToDouble;
   Label* deopt = compiler->AddDeoptStub(instance_call()->cid(),
                                         instance_call()->token_index(),
                                         instance_call()->try_index(),
                                         deopt_reason,
                                         value);
 
   if (from() == kDouble) {
     __ testq(value, Immediate(kSmiTagMask));
     __ j(ZERO, deopt);  // Deoptimize if Smi.
     __ CompareClassId(value, kDouble);
     __ j(NOT_EQUAL, deopt);  // Deoptimize if not Double.
     ASSERT(value == result);
     return;
   }
 
   ASSERT(from() == kSmi);
 
   const Class& double_class = compiler->double_class();
   const Code& stub =
     Code::Handle(StubCode::GetAllocationStubForClass(double_class));
   const ExternalLabel label(double_class.ToCString(), stub.EntryPoint());
 
   // TODO(vegorov): allocate box in the driver loop to avoid pushing and poping.
-  __ pushq(value);
   compiler->GenerateCall(instance_call()->token_index(),
                          instance_call()->try_index(),
                          &label,
                          PcDescriptors::kOther);
   ASSERT(result == RAX);
   __ popq(value);
 
   __ testq(value, Immediate(kSmiTagMask));
   __ j(NOT_ZERO, deopt);  // Deoptimize if not Smi.
   __ SmiUntag(value);
@@ skipping 48 matching lines @@
                                  instance_call()->argument_names());
   }
   __ Bind(&done);
 }
 
 }  // namespace dart
 
 #undef __
 
 #endif  // defined TARGET_ARCH_X64