Eliminate temporary locals for some expressions

runtime/vm/flow_graph_builder.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_builder.h"
 
 #include "lib/invocation_mirror.h"
 #include "vm/ast_printer.h"
 #include "vm/code_descriptors.h"
 #include "vm/dart_entry.h"
@@ skipping 39 matching lines @@
     // All parameters are copied if any parameter is.
     num_non_copied_params_((num_copied_params_ == 0)
         ? parsed_function.function().num_fixed_parameters()
         : 0),
     num_stack_locals_(parsed_function.num_stack_locals()),
     exit_collector_(exit_collector),
     last_used_block_id_(0),  // 0 is used for the graph entry.
     context_level_(0),
     last_used_try_index_(CatchClauseNode::kInvalidTryIndex),
     try_index_(CatchClauseNode::kInvalidTryIndex),
-    graph_entry_(NULL) { }
+    graph_entry_(NULL),
+    args_pushed_(0) { }
 
 
 void FlowGraphBuilder::AddCatchEntry(CatchBlockEntryInstr* entry) {
   graph_entry_->AddCatchEntry(entry);
 }
 
 
 void InlineExitCollector::PrepareGraphs(FlowGraph* callee_graph) {
   ASSERT(callee_graph->graph_entry()->SuccessorCount() == 1);
   ASSERT(callee_graph->max_block_id() > caller_graph_->max_block_id());
@@ skipping 278 matching lines @@
   }
   temp_index_ = other_fragment.temp_index();
 }
 
 
 Value* EffectGraphVisitor::Bind(Definition* definition) {
   ASSERT(is_open());
   DeallocateTempIndex(definition->InputCount());
   definition->set_use_kind(Definition::kValue);
   definition->set_temp_index(AllocateTempIndex());
+  owner_->add_args_pushed(-definition->ArgumentCount());
   if (is_empty()) {
     entry_ = definition;
   } else {
     exit()->LinkTo(definition);
   }
   exit_ = definition;
   return new Value(definition);
 }
 
 
 void EffectGraphVisitor::Do(Definition* definition) {
   ASSERT(is_open());
   DeallocateTempIndex(definition->InputCount());
   definition->set_use_kind(Definition::kEffect);
+  owner_->add_args_pushed(-definition->ArgumentCount());
   if (is_empty()) {
     entry_ = definition;
   } else {
     exit()->LinkTo(definition);
   }
   exit_ = definition;
 }
 
 
 void EffectGraphVisitor::AddInstruction(Instruction* instruction) {
   ASSERT(is_open());
   ASSERT(instruction->IsPushArgument() || !instruction->IsDefinition());
   ASSERT(!instruction->IsBlockEntry());
   DeallocateTempIndex(instruction->InputCount());
+  owner_->add_args_pushed(-instruction->ArgumentCount());
   if (is_empty()) {
     entry_ = exit_ = instruction;
   } else {
     exit()->LinkTo(instruction);
     exit_ = instruction;
   }
 }
 
 
 void EffectGraphVisitor::AddReturnExit(intptr_t token_pos, Value* value) {
@@ skipping 99 matching lines @@
   }
 
   // 3. Set the exit to the graph to be the false successor of the test, a
   // fresh target node
 
   exit_ = test_fragment.CreateFalseSuccessor();
 }
 
 
 PushArgumentInstr* EffectGraphVisitor::PushArgument(Value* value) {
+  owner_->add_args_pushed(1);
   PushArgumentInstr* result = new PushArgumentInstr(value);
   AddInstruction(result);
   return result;
 }
 
 
 Definition* EffectGraphVisitor::BuildStoreTemp(const LocalVariable& local,
                                                Value* value) {
   ASSERT(!local.is_captured());
   return new StoreLocalInstr(local, value);
@@ skipping 1301 matching lines @@
     ArgumentDefinitionTestNode* node) {
   InlineBailout("EffectGraphVisitor::VisitArgumentDefinitionTestNode");
   Definition* load = BuildLoadLocal(node->saved_arguments_descriptor());
   Value* arguments_descriptor = Bind(load);
   ArgumentDefinitionTestInstr* arg_def_test =
       new ArgumentDefinitionTestInstr(node, arguments_descriptor);
   ReturnDefinition(arg_def_test);
 }
 
 
+intptr_t EffectGraphVisitor::GetCurrentTempLocalIndex() const {
+  return kFirstLocalSlotFromFp
+      - owner()->num_stack_locals()
+      - owner()->num_copied_params()
+      - owner()->args_pushed()
+      - temp_index() + 1;
+}
+
+
+class TempLocalScope : public ValueObject {
+ public:
+  TempLocalScope(EffectGraphVisitor* visitor, Value* value)
+      : visitor_(visitor) {
+        ASSERT(value->definition()->temp_index() == visitor->temp_index() - 1);

[srdjan, 2013/05/28 13:30:43]

weird indent of body

[Florian Schneider, 2013/05/30 09:29:31]

Done.

+        intptr_t index = visitor->GetCurrentTempLocalIndex();
+        char name[64];
+        OS::SNPrint(name, 64, ":tmp_local%"Pd, index);
+        var_ = new LocalVariable(0, String::ZoneHandle(Symbols::New(name)),
+                                 Type::ZoneHandle(Type::DynamicType()));
+        var_->set_index(index);
+        visitor->Do(new PushTempInstr(value));
+        visitor->AllocateTempIndex();
+      }
+
+  LocalVariable* var() const { return var_; }
+
+  ~TempLocalScope() {
+    Value* result = visitor_->Bind(new LoadLocalInstr(*var_));
+    visitor_->DeallocateTempIndex(1);
+    visitor_->ReturnDefinition(new DropTempsInstr(1, result));
+  }
+
+ private:
+  EffectGraphVisitor* visitor_;
+  Value* value_;
+  LocalVariable* var_;
+};
+
+
+void EffectGraphVisitor::VisitLetNode(LetNode* node) {
+  intptr_t num_temps = node->num_temps();
+  for (intptr_t i = 0; i < num_temps; ++i) {
+    ValueGraphVisitor for_value(owner(), temp_index());
+    node->temp_expressions()[i]->Visit(&for_value);
+    Append(for_value);
+    Value* temp_val = for_value.value();
+    node->temp(i)->set_index(GetCurrentTempLocalIndex());
+    Do(new PushTempInstr(temp_val));
+    AllocateTempIndex();
+  }
+
+  ValueGraphVisitor for_value(owner(), temp_index());
+  node->body()->Visit(&for_value);
+  Append(for_value);
+  Value* result_value = for_value.value();
+  DeallocateTempIndex(num_temps);
+  ReturnDefinition(new DropTempsInstr(num_temps, result_value));

[Kevin Millikin (Google), 2013/05/29 11:28:23]

It's a bit unfortunate that DropTempsInstr has a use of the value on top the the
expression stack --- it serves as a renaming instruction for this value.  I
can't imagine a case where it would be any other value, due to the semantics of
LetNode and TempLocalScope.

I wish DropTempsInstr were not a definition with uses, but rather an instruction
with side effects and we could just use the original definition instead of this
one.  That would allow us to do the right thing for let in effect context (i.e.,
visit the last subexpression in effect context).

Is it the non-optimizing register allocator that won't allow a value to be live
across a purely side-effecting instruction?  If so, that seems like a huge wart
that should be fixed.

[Florian Schneider, 2013/05/30 09:29:31]

I generally agree, but making them just Instructions (as opposed to Definition)
adds quite a bit of complexity. We could generate more compact code for the case
of effect contexts. I'll add a TODO for now.

+}
+
+
 void EffectGraphVisitor::VisitArrayNode(ArrayNode* node) {
   const AbstractTypeArguments& type_args =
       AbstractTypeArguments::ZoneHandle(node->type().arguments());
   Value* element_type = BuildInstantiatedTypeArguments(node->token_pos(),
                                                        type_args);
   CreateArrayInstr* create = new CreateArrayInstr(node->token_pos(),
                                                   node->length(),
                                                   node->type(),
                                                   element_type);
   Value* array_val = Bind(create);
-  Definition* store = BuildStoreTemp(node->temp_local(), array_val);
-  Do(store);
 
-  const intptr_t class_id = create->Type()->ToCid();
-  const intptr_t deopt_id = Isolate::kNoDeoptId;
-  for (int i = 0; i < node->length(); ++i) {
-    Value* array = Bind(
-        new LoadLocalInstr(node->temp_local()));
-    Value* index = Bind(new ConstantInstr(Smi::ZoneHandle(Smi::New(i))));
-    ValueGraphVisitor for_value(owner(), temp_index());
-    node->ElementAt(i)->Visit(&for_value);
-    Append(for_value);
-    // No store barrier needed for constants.
-    const StoreBarrierType emit_store_barrier =
-        for_value.value()->BindsToConstant()
-            ? kNoStoreBarrier
-            : kEmitStoreBarrier;
-    intptr_t index_scale = FlowGraphCompiler::ElementSizeFor(class_id);
-    StoreIndexedInstr* store = new StoreIndexedInstr(
-        array, index, for_value.value(),
-        emit_store_barrier, index_scale, class_id, deopt_id);
-    Do(store);
+  { TempLocalScope tmp(this, array_val);
+    const intptr_t class_id = create->Type()->ToCid();
+    const intptr_t deopt_id = Isolate::kNoDeoptId;
+    for (int i = 0; i < node->length(); ++i) {
+      Value* array = Bind(new LoadLocalInstr(*tmp.var()));
+      Value* index = Bind(new ConstantInstr(Smi::ZoneHandle(Smi::New(i))));
+      ValueGraphVisitor for_value(owner(), temp_index());
+      node->ElementAt(i)->Visit(&for_value);
+      Append(for_value);
+      // No store barrier needed for constants.
+      const StoreBarrierType emit_store_barrier =
+          for_value.value()->BindsToConstant()
+              ? kNoStoreBarrier
+              : kEmitStoreBarrier;
+      intptr_t index_scale = FlowGraphCompiler::ElementSizeFor(class_id);
+      StoreIndexedInstr* store = new StoreIndexedInstr(
+          array, index, for_value.value(),
+          emit_store_barrier, index_scale, class_id, deopt_id);
+      Do(store);
+    }
   }
-
-  ReturnDefinition(new LoadLocalInstr(node->temp_local()));
 }
 
 
 void EffectGraphVisitor::VisitClosureNode(ClosureNode* node) {
   const Function& function = node->function();
 
   if (function.IsImplicitStaticClosureFunction()) {
     Instance& closure = Instance::ZoneHandle();
     closure ^= function.implicit_static_closure();
     if (closure.IsNull()) {
@@ skipping 453 matching lines @@
     // No instantiator required.
     Value* instantiator_val = Bind(new ConstantInstr(
         Smi::ZoneHandle(Smi::New(StubCode::kNoInstantiator))));
     call_arguments->Add(PushArgument(instantiator_val));
     return;
   }
 
   // The type arguments are uninstantiated. We use expression_temp_var to save
   // the instantiator type arguments because they have two uses.
   ASSERT(owner()->parsed_function().expression_temp_var() != NULL);
-  const LocalVariable& temp = *owner()->parsed_function().expression_temp_var();
   const Class& instantiator_class = Class::Handle(
       owner()->parsed_function().function().Owner());
   Value* type_arguments_val = BuildInstantiatorTypeArguments(
       node->token_pos(), instantiator_class, NULL);
 
   const bool use_instantiator_type_args =
       node->type_arguments().IsUninstantiatedIdentity() ||
       node->type_arguments().CanShareInstantiatorTypeArguments(
           instantiator_class);
 
   if (!use_instantiator_type_args) {
     const intptr_t len = node->type_arguments().Length();
     if (node->type_arguments().IsRawInstantiatedRaw(len)) {
       type_arguments_val =
-          Bind(BuildStoreTemp(temp, type_arguments_val));
+          Bind(BuildStoreExprTemp(type_arguments_val));
       type_arguments_val = Bind(
           new ExtractConstructorTypeArgumentsInstr(
               node->token_pos(),
               node->type_arguments(),
               instantiator_class,
               type_arguments_val));
     } else {
-      Do(BuildStoreTemp(temp, type_arguments_val));
+      Do(BuildStoreExprTemp(type_arguments_val));
       type_arguments_val = Bind(new ConstantInstr(node->type_arguments()));
     }
   }
   call_arguments->Add(PushArgument(type_arguments_val));
 
   Value* instantiator_val = NULL;
   if (!use_instantiator_type_args) {
-    instantiator_val = Bind(BuildLoadLocal(temp));
+    instantiator_val = Bind(BuildLoadExprTemp());
     const intptr_t len = node->type_arguments().Length();
     if (node->type_arguments().IsRawInstantiatedRaw(len)) {
       instantiator_val =
           Bind(new ExtractConstructorInstantiatorInstr(node,
                                                        instantiator_class,
                                                        instantiator_val));
     }
   } else {
     // No instantiator required.
     instantiator_val = Bind(new ConstantInstr(
@@ skipping 11 matching lines @@
 
   // t_n contains the allocated and initialized object.
   //   t_n      <- AllocateObject(class)
   //   t_n      <- StoreLocal(temp, t_n);
   //   t_n+1    <- ctor-arg
   //   t_n+2... <- constructor arguments start here
   //   StaticCall(constructor, t_n, t_n+1, ...)
   //   tn       <- LoadLocal(temp)
 
   Value* allocate = BuildObjectAllocation(node);
-  Value* allocated_value = Bind(BuildStoreTemp(
-      node->allocated_object_var(),
-      allocate));
-  PushArgumentInstr* push_allocated_value = PushArgument(allocated_value);
-  BuildConstructorCall(node, push_allocated_value);
-  Definition* load_allocated = BuildLoadLocal(
-      node->allocated_object_var());
-  allocated_value = Bind(load_allocated);
-  ReturnValue(allocated_value);
+  { TempLocalScope tmp(this, allocate);
+    Value* allocated_tmp = Bind(new LoadLocalInstr(*tmp.var()));
+    PushArgumentInstr* push_allocated_value = PushArgument(allocated_tmp);
+    BuildConstructorCall(node, push_allocated_value);
+  }
 }
 
 
 void EffectGraphVisitor::VisitInstanceGetterNode(InstanceGetterNode* node) {
   ValueGraphVisitor for_receiver(owner(), temp_index());
   node->receiver()->Visit(&for_receiver);
   Append(for_receiver);
   PushArgumentInstr* push_receiver = PushArgument(for_receiver.value());
   ZoneGrowableArray<PushArgumentInstr*>* arguments =
       new ZoneGrowableArray<PushArgumentInstr*>(1);
@@ skipping 846 matching lines @@
   arguments->Add(new LiteralNode(args_pos, method_name));
   // The second argument is the arguments descriptor of the original method.
   const Array& args_descriptor =
       Array::ZoneHandle(ArgumentsDescriptor::New(method_arguments->length(),
                                                  method_arguments->names()));
   arguments->Add(new LiteralNode(args_pos, args_descriptor));
   // The third argument is an array containing the original method arguments,
   // including the receiver.
   ArrayNode* args_array = new ArrayNode(
       args_pos,
-      Type::ZoneHandle(Type::ArrayType()),
-      *owner()->parsed_function().array_literal_var());
+      Type::ZoneHandle(Type::ArrayType()));
   for (intptr_t i = 0; i < method_arguments->length(); i++) {
     args_array->AddElement(method_arguments->NodeAt(i));
   }
   arguments->Add(args_array);
   ZoneGrowableArray<PushArgumentInstr*>* allocation_args =
       new ZoneGrowableArray<PushArgumentInstr*>(arguments->length());
   BuildPushArguments(*arguments, allocation_args);
   StaticCallInstr* allocation = new StaticCallInstr(args_pos,
                                                     allocation_function,
                                                     Array::ZoneHandle(),
@@ skipping 174 matching lines @@
   intptr_t len = OS::SNPrint(NULL, 0, kFormat, function_name, reason) + 1;
   char* chars = Isolate::Current()->current_zone()->Alloc<char>(len);
   OS::SNPrint(chars, len, kFormat, function_name, reason);
   const Error& error = Error::Handle(
       LanguageError::New(String::Handle(String::New(chars))));
   Isolate::Current()->long_jump_base()->Jump(1, error);
 }
 
 
 }  // namespace dart