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

runtime/vm/intermediate_language_ia32.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_IA32.
 #if defined(TARGET_ARCH_IA32)
 
 #include "vm/intermediate_language.h"
 
 #include "lib/error.h"
 #include "vm/flow_graph_compiler.h"
 #include "vm/locations.h"
 #include "vm/object_store.h"
 #include "vm/stub_code.h"
 
 #define __ compiler->assembler()->
 
 namespace dart {
 
 DECLARE_FLAG(int, optimization_counter_threshold);
 DECLARE_FLAG(bool, trace_functions);
 
 // Generic summary for call instructions that have all arguments pushed
 // on the stack and return the result in a fixed register EAX.
 LocationSummary* Computation::MakeCallSummary() {
-  LocationSummary* result = new LocationSummary(0, 0);
+  LocationSummary* result = new LocationSummary(0, 0, LocationSummary::kCall);
   result->set_out(Location::RegisterLocation(EAX));
   return result;
 }
 
 
 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.
-    __ pushl(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(EAX));
   locs->set_temp(0, Location::RequiresRegister());
@@ skipping 48 matching lines @@
   compiler->AddCurrentDescriptor(PcDescriptors::kReturn,
                                  cid(),
                                  token_index(),
                                  CatchClauseNode::kInvalidTryIndex);
 }
 
 
 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(EAX));
   result->set_temp(0, Location::RegisterLocation(EDX));  // 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(EAX));
     }
     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(EAX));
   }
   return locs;
 }
 
 
 static void EmitSmiEqualityCompare(FlowGraphCompiler* compiler,
@@ skipping 169 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::kNoCall,
+                                                   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(operands_class_id() == kObject);
   return MakeCallSummary();
@@ skipping 124 matching lines @@
                                  try_index(),
                                  function_name,
                                  kNumArguments,
                                  Array::ZoneHandle(),  // No optional arguments.
                                  kNumArgsChecked);
   ASSERT(locs()->out().reg() == EAX);
 }
 
 
 LocationSummary* NativeCallComp::MakeLocationSummary() const {
-  LocationSummary* locs = new LocationSummary(0, 3);
+  LocationSummary* locs = new LocationSummary(0, 3, LocationSummary::kCall);
   locs->set_temp(0, Location::RegisterLocation(EAX));
   locs->set_temp(1, Location::RegisterLocation(ECX));
   locs->set_temp(2, Location::RegisterLocation(EDX));
   locs->set_out(Location::RequiresRegister());
   return locs;
 }
 
 
 void NativeCallComp::EmitNativeCode(FlowGraphCompiler* compiler) {
   ASSERT(locs()->temp(0).reg() == EAX);
@@ skipping 196 matching lines @@
     }
 
     default:
       UNREACHABLE();
       break;
   }
 }
 
 
 LocationSummary* InstanceSetterComp::MakeLocationSummary() const {
-  const intptr_t kNumInputs = 2;
-  return LocationSummary::Make(kNumInputs, Location::NoLocation());
+  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()));
 
-  __ pushl(receiver);
-  __ pushl(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(ECX));
   locs->set_temp(0, Location::RegisterLocation(EDX));
   locs->set_out(Location::RegisterLocation(EAX));
   return locs;
 }
 
 
 void CreateArrayComp::EmitNativeCode(FlowGraphCompiler* compiler) {
   Register temp_reg = locs()->temp(0).reg();
   Register result_reg = locs()->out().reg();
@@ skipping 10 matching lines @@
   __ leal(temp_reg, FieldAddress(result_reg, Array::data_offset()));
   for (int i = ElementCount() - 1; i >= 0; --i) {
     ASSERT(ElementAt(i)->IsUse());
     __ popl(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 34 matching lines @@
     compiler->EmitClassChecksNoSmi(*class_ids(), instance, result, deopt);
   }
 
   __ movl(result, FieldAddress(instance, offset_in_bytes()));
 }
 
 
 LocationSummary* InstantiateTypeArgumentsComp::MakeLocationSummary() const {
   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::RequiresRegister());
   locs->set_temp(0, Location::RequiresRegister());
   locs->set_out(Location::SameAsFirstInput());
   return locs;
 }
 
 
 void InstantiateTypeArgumentsComp::EmitNativeCode(
     FlowGraphCompiler* compiler) {
   Register instantiator_reg = locs()->in(0).reg();
@@ skipping 162 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(EDX));
   locs->set_out(Location::RegisterLocation(EAX));
   return locs;
 }
 
 
 void AllocateContextComp::EmitNativeCode(FlowGraphCompiler* compiler) {
   ASSERT(locs()->temp(0).reg() == EDX);
   ASSERT(locs()->out().reg() == EAX);
 
   __ movl(EDX, 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.
   __ pushl(context_value);
   compiler->GenerateCallRuntime(cid(),
@@ skipping 24 matching lines @@
   ASSERT(!exception_var().is_captured());
   ASSERT(!stacktrace_var().is_captured());
   __ movl(Address(EBP, exception_var().index() * kWordSize),
           kExceptionObjectReg);
   __ movl(Address(EBP, stacktrace_var().index() * kWordSize),
           kStackTraceObjectReg);
 }
 
 
 LocationSummary* CheckStackOverflowComp::MakeLocationSummary() const {
-  return LocationSummary::Make(0, Location::NoLocation());
+  return LocationSummary::Make(0,
+                               Location::NoLocation(),
+                               LocationSummary::kCall);
 }
 
 
 void CheckStackOverflowComp::EmitNativeCode(FlowGraphCompiler* compiler) {
   __ cmpl(ESP,
           Address::Absolute(Isolate::Current()->stack_limit_address()));
   Label no_stack_overflow;
   __ j(ABOVE, &no_stack_overflow);
   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(EAX));
-    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(EAX));
     summary->set_in(1, Location::RegisterLocation(ECX));
     summary->set_out(Location::SameAsFirstInput());
     summary->set_temp(0, Location::RegisterLocation(EBX));
     // Will be used for for sign extension.
@@ skipping 34 matching lines @@
   Register right = comp->locs()->in(1).reg();
   Register result = comp->locs()->out().reg();
   Register temp = comp->locs()->temp(0).reg();
   ASSERT(left == result);
   Label* deopt = compiler->AddDeoptStub(comp->instance_call()->cid(),
                                         comp->instance_call()->token_index(),
                                         comp->instance_call()->try_index(),
                                         kDeoptSmiBinaryOp,
                                         temp,
                                         right);
+  // TODO(vegorov): for many binary operations this pattern can be rearrange

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

rearranged

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

Done.

+  // to save one move.
   __ movl(temp, left);
   __ orl(left, right);
   __ testl(left, Immediate(kSmiTagMask));
   __ j(NOT_ZERO, deopt);
   __ movl(left, temp);
   switch (comp->op_kind()) {
     case Token::kADD: {
       __ addl(left, right);
       __ j(OVERFLOW, deopt);
       break;
@@ skipping 102 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 = EBX;
+  Register right = ECX;
+  Register temp = EDX;
   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());
-  __ pushl(left);
-  __ pushl(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 == EAX);
   __ popl(right);
   __ popl(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 43 matching lines @@
 
 
 LocationSummary* ToDoubleComp::MakeLocationSummary() const {
   const intptr_t kNumInputs = 1;
   if (from() == kDouble) {
     const intptr_t kNumTemps = 1;
     LocationSummary* locs = new LocationSummary(kNumInputs, kNumTemps);
     locs->set_in(0, Location::RequiresRegister());
     locs->set_temp(0, Location::RequiresRegister());
     locs->set_out(Location::SameAsFirstInput());
+    locs->set_temp(0, Location::RequiresRegister());
     return locs;
   } else {
     ASSERT(from() == kSmi);
-    return LocationSummary::Make(kNumInputs, Location::RegisterLocation(EAX));
+    return MakeCallSummary();  // Calls a stub to allocate result.
   }
 }
 
 
 void ToDoubleComp::EmitNativeCode(FlowGraphCompiler* compiler) {
-  Register value = locs()->in(0).reg();
   Register result = locs()->out().reg();
+  Register value = (from() == kDouble) ? locs()->in(0).reg() : EBX;
 
   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) {
     Register temp = locs()->temp(0).reg();
     __ testl(value, Immediate(kSmiTagMask));
     __ j(ZERO, deopt);  // Deoptimize if Smi.
     __ CompareClassId(value, kDouble, temp);
     __ 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.

[Florian Schneider, 2012/06/18 16:50:55]

s/poping/popping/

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

Done.

-  __ pushl(value);
   compiler->GenerateCall(instance_call()->token_index(),
                          instance_call()->try_index(),
                          &label,
                          PcDescriptors::kOther);
   ASSERT(result == EAX);
   __ popl(value);
 
   __ testl(value, Immediate(kSmiTagMask));
   __ j(NOT_ZERO, deopt);  // Deoptimize if not Smi.
   __ SmiUntag(value);
@@ skipping 49 matching lines @@
   }
   __ Bind(&done);
 }
 
 
 }  // namespace dart
 
 #undef __
 
 #endif  // defined TARGET_ARCH_X64