Introduce per-isolate cache for compile time constants

runtime/vm/parser.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/parser.h"
 
 #include "lib/invocation_mirror.h"
 #include "platform/utils.h"
 #include "vm/ast_transformer.h"
 #include "vm/bootstrap.h"
 #include "vm/class_finalizer.h"
 #include "vm/compiler.h"
 #include "vm/compiler_stats.h"
 #include "vm/dart_api_impl.h"
 #include "vm/dart_entry.h"
 #include "vm/flags.h"
 #include "vm/growable_array.h"
 #include "vm/handles.h"
+#include "vm/hash_table.h"
 #include "vm/heap.h"
 #include "vm/isolate.h"
 #include "vm/longjump.h"
 #include "vm/native_arguments.h"
 #include "vm/native_entry.h"
 #include "vm/object.h"
 #include "vm/object_store.h"
 #include "vm/os.h"
 #include "vm/regexp_assembler.h"
 #include "vm/report.h"
@@ skipping 11849 matching lines @@
 bool Parser::IsInstantiatorRequired() const {
   ASSERT(!current_function().IsNull());
   if (current_function().is_static() &&
       !current_function().IsInFactoryScope()) {
     return false;
   }
   return current_class().NumTypeParameters() > 0;
 }
 
 
+class ConstMapKeyEqualsTraits {
+ public:
+  static bool IsMatch(const Object& a, const Object& b) {
+    return String::Cast(a).Equals(String::Cast(b));
+  }
+  static uword Hash(const Object& obj) {
+    return String::Cast(obj).Hash();
+  }
+};
+typedef UnorderedHashMap<ConstMapKeyEqualsTraits> ConstantsMap;
+
+
+static void BuildConstMapKey(const Script& script,
+                             intptr_t token_pos,
+                             String* key) {
+  *key = script.url();
+  String& suffix = String::Handle(String::NewFormatted("_%" Pd "", token_pos));

[koda, 2015/08/25 18:27:12]

Add TODO: avoid allocations for lookup by introducing a (script, token_pos)
wrapper type and overloading IsMatch/Hash in the traits (like
Symbols::FromConcat does for string pairs).

[koda, 2015/08/25 18:27:12]

Make private method and then: Handle(Z, ...)

[hausner, 2015/08/25 19:48:51]

We discussed offline, but for those following along at home: it does not help
much to avoid the allocation because if no object is found for this position, it
will be inserted later. Creating the symbol here means we don't have to allocate
it when the constant gets inserted.

[hausner, 2015/08/25 19:48:51]

Done.

[srdjan, 2015/08/25 22:16:19]

String::NewFormatted is allocating a string in new space. We need to avoid that
in order to run the optimizing compiler in a the parallel thread.

+  *key = Symbols::FromConcat(*key, suffix);
+}
+
+
+void Parser::CacheConstantValue(intptr_t token_pos, const Instance& value) {
+  String& key = String::Handle();

[koda, 2015/08/25 18:27:12]

Handle(Z)

[hausner, 2015/08/25 19:48:51]

Done.

+  BuildConstMapKey(script_, token_pos, &key);
+  if (isolate()->object_store()->compile_time_constants() == Array::null()) {
+    const intptr_t kInitialConstMapSize = 16;
+    isolate()->object_store()->set_compile_time_constants(
+        Array::Handle(Z, HashTables::New<ConstantsMap>(kInitialConstMapSize)));

[srdjan, 2015/08/25 22:16:19]

It does not matter for optimizing compiler (since the table will be allocated
inside an unoptimized compilation), but does it make sense to store the HashMap
in old space as it is long lived and will anyhow land in old space?

+  }
+  ConstantsMap constants(isolate()->object_store()->compile_time_constants());
+  constants.UpdateOrInsert(key, value);
+  if (FLAG_compiler_stats) {
+    isolate_->compiler_stats()->num_cached_consts = constants.NumOccupied();
+  }
+  isolate()->object_store()->set_compile_time_constants(constants.Release());
+}
+
+
+bool Parser::GetCachedConstant(intptr_t token_pos, Instance* value) {
+  if (isolate()->object_store()->compile_time_constants() == Array::null()) {
+    return false;
+  }
+  String& key = String::Handle();

[koda, 2015/08/25 18:27:12]

Handle(Z)

[hausner, 2015/08/25 19:48:52]

Done.

+  BuildConstMapKey(script_, token_pos, &key);
+  ConstantsMap constants(isolate()->object_store()->compile_time_constants());
+  bool is_present = false;
+  *value ^= constants.GetOrNull(key, &is_present);
+  ASSERT(constants.Release().raw() ==
+      isolate()->object_store()->compile_time_constants());
+  if (FLAG_compiler_stats && is_present) {
+    isolate_->compiler_stats()->num_const_cache_hits++;
+  }
+  return is_present;
+}
+
+
 RawInstance* Parser::TryCanonicalize(const Instance& instance,
                                      intptr_t token_pos) {
   if (instance.IsNull()) {
     return instance.raw();
   }
   const char* error_str = NULL;
   Instance& result =
       Instance::Handle(Z, instance.CheckAndCanonicalize(&error_str));
   if (result.IsNull()) {
     ReportError(token_pos, "Invalid const object %s", error_str);
@@ skipping 602 matching lines @@
 // Note: if the list literal is empty and the brackets have no whitespace
 // between them, the scanner recognizes the opening and closing bracket
 // as one token of type Token::kINDEX.
 AstNode* Parser::ParseListLiteral(intptr_t type_pos,
                                   bool is_const,
                                   const TypeArguments& type_arguments) {
   TRACE_PARSER("ParseListLiteral");
   ASSERT(type_pos >= 0);
   ASSERT(CurrentToken() == Token::kLBRACK || CurrentToken() == Token::kINDEX);
   const intptr_t literal_pos = TokenPos();
+
+  if (is_const) {
+    Instance& existing_const = Instance::ZoneHandle(Z);
+    if (GetCachedConstant(literal_pos, &existing_const)) {
+      SkipListLiteral();
+      return new(Z) LiteralNode(literal_pos, existing_const);
+    }
+  }
+
   bool is_empty_literal = CurrentToken() == Token::kINDEX;
   ConsumeToken();
 
   AbstractType& element_type = Type::ZoneHandle(Z, Type::DynamicType());
   TypeArguments& list_type_arguments =
       TypeArguments::ZoneHandle(Z, type_arguments.raw());
   // If no type argument vector is provided, leave it as null, which is
   // equivalent to using dynamic as the type argument for the element type.
   if (!list_type_arguments.IsNull()) {
     ASSERT(list_type_arguments.Length() > 0);
@@ skipping 47 matching lines @@
       } else if (CurrentToken() != Token::kRBRACK) {
         ReportError("comma or ']' expected");
       }
     }
     ExpectToken(Token::kRBRACK);
     SetAllowFunctionLiterals(saved_mode);
   }
 
   if (is_const) {
     // Allocate and initialize the const list at compile time.
-    Array& const_list =
-        Array::ZoneHandle(Z, Array::New(element_list.length(), Heap::kOld));
+    Array& const_list = Array::ZoneHandle(Z,
+        Array::New(element_list.length(), Heap::kOld));
     const_list.SetTypeArguments(
         TypeArguments::Handle(Z, list_type_arguments.Canonicalize()));
     Error& malformed_error = Error::Handle(Z);
     for (int i = 0; i < element_list.length(); i++) {
       AstNode* elem = element_list[i];
       // Arguments have been evaluated to a literal value already.
       ASSERT(elem->IsLiteralNode());
       ASSERT(!is_top_level_);  // We cannot check unresolved types.
       if (I->flags().type_checks() &&
           !element_type.IsDynamicType() &&
@@ skipping 11 matching lines @@
                       "a constant of type '%s'",
                       i,
                       String::Handle(Z,
                           element_type.UserVisibleName()).ToCString());
         }
       }
       const_list.SetAt(i, elem->AsLiteralNode()->literal());
     }
     const_list.MakeImmutable();
     const_list ^= TryCanonicalize(const_list, literal_pos);
+    CacheConstantValue(literal_pos, const_list);
     return new(Z) LiteralNode(literal_pos, const_list);
   } else {
     // Factory call at runtime.
     const Class& factory_class =
         Class::Handle(Z, Library::LookupCoreClass(Symbols::List()));
     ASSERT(!factory_class.IsNull());
     const Function& factory_method = Function::ZoneHandle(Z,
         factory_class.LookupFactory(
             Library::PrivateCoreLibName(Symbols::ListLiteralFactory())));
     ASSERT(!factory_method.IsNull());
@@ skipping 73 matching lines @@
 }
 
 
 AstNode* Parser::ParseMapLiteral(intptr_t type_pos,
                                  bool is_const,
                                  const TypeArguments& type_arguments) {
   TRACE_PARSER("ParseMapLiteral");
   ASSERT(type_pos >= 0);
   ASSERT(CurrentToken() == Token::kLBRACE);
   const intptr_t literal_pos = TokenPos();
-  ConsumeToken();
 
+  if (is_const) {
+    Instance& existing_const = Instance::ZoneHandle(Z);
+    if (GetCachedConstant(literal_pos, &existing_const)) {
+      SkipMapLiteral();
+      return new(Z) LiteralNode(literal_pos, existing_const);
+    }
+  }
+
+  ConsumeToken();  // Opening brace.
   AbstractType& key_type = Type::ZoneHandle(Z, Type::DynamicType());
   AbstractType& value_type = Type::ZoneHandle(Z, Type::DynamicType());
   TypeArguments& map_type_arguments =
       TypeArguments::ZoneHandle(Z, type_arguments.raw());
   // If no type argument vector is provided, leave it as null, which is
   // equivalent to using dynamic as the type argument for the both key and value
   // types.
   if (!map_type_arguments.IsNull()) {
     ASSERT(map_type_arguments.Length() > 0);
     // Map literals take two type arguments.
@@ skipping 136 matching lines @@
         EvaluateConstConstructorCall(immutable_map_class,
                                      map_type_arguments,
                                      map_constr,
                                      constr_args));
     if (constructor_result.IsUnhandledException()) {
       ReportErrors(Error::Cast(constructor_result),
                    script_, literal_pos,
                    "error executing const Map constructor");
     } else {
       const Instance& const_instance = Instance::Cast(constructor_result);
+      CacheConstantValue(literal_pos, const_instance);

[Florian Schneider, 2015/08/26 08:58:09]

Are cached constants ever GCed? What if the code that refers to such a constant
gets GCed? Wouldn't you need to traverse the cache to evict the corresponding
constants?

[hausner, 2015/08/26 17:46:14]

No, they are not GCed. But we hold on to these constants through the list of
canonical values (RawClass::constants_) already, so they don't get GCed even
now.

       return new(Z) LiteralNode(
           literal_pos, Instance::ZoneHandle(Z, const_instance.raw()));
     }
   } else {
     // Factory call at runtime.
     const Class& factory_class =
         Class::Handle(Z, Library::LookupCoreClass(Symbols::Map()));
     ASSERT(!factory_class.IsNull());
     const Function& factory_method = Function::ZoneHandle(Z,
         factory_class.LookupFactory(
@@ skipping 523 matching lines @@
   // Make the constructor call.
   AstNode* new_object = NULL;
   if (is_const) {
     if (!constructor.is_const()) {
       const String& external_constructor_name =
           (named_constructor ? constructor_name : type_class_name);
       ReportError("non-const constructor '%s' cannot be used in "
                   "const object creation",
                   external_constructor_name.ToCString());
     }
-    const Object& constructor_result = Object::Handle(Z,
-        EvaluateConstConstructorCall(type_class,
-                                     type_arguments,
-                                     constructor,
-                                     arguments));
-    if (constructor_result.IsUnhandledException()) {
-      // It's a compile-time error if invocation of a const constructor
-      // call fails.
-      ReportErrors(Error::Cast(constructor_result),
-                   script_, new_pos,
-                   "error while evaluating const constructor");
+
+    Instance& const_instance = Instance::ZoneHandle(Z);
+    if (GetCachedConstant(new_pos, &const_instance)) {
+      // Cache hit, nothing else to do.
     } else {
-      // Const constructors can return null in the case where a const native
-      // factory returns a null value. Thus we cannot use a Instance::Cast here.
-      Instance& const_instance = Instance::Handle(Z);
+      Object& constructor_result = Object::Handle(Z,
+          EvaluateConstConstructorCall(type_class,
+                                       type_arguments,
+                                       constructor,
+                                       arguments));
+      if (constructor_result.IsUnhandledException()) {
+        // It's a compile-time error if invocation of a const constructor
+        // call fails.
+        ReportErrors(Error::Cast(constructor_result),
+                     script_, new_pos,
+                     "error while evaluating const constructor");
+      }
       const_instance ^= constructor_result.raw();
-      new_object = new(Z) LiteralNode(
-          new_pos, Instance::ZoneHandle(Z, const_instance.raw()));
-      if (!type_bound.IsNull()) {
-        ASSERT(!type_bound.IsMalformed());
-        Error& malformed_error = Error::Handle(Z);
-        ASSERT(!is_top_level_);  // We cannot check unresolved types.
-        if (!const_instance.IsInstanceOf(type_bound,
-                                         TypeArguments::Handle(Z),
-                                         &malformed_error)) {
-          type_bound = ClassFinalizer::NewFinalizedMalformedType(
-              malformed_error,
-              script_,
-              new_pos,
-              "const factory result is not an instance of '%s'",
-              String::Handle(Z, type_bound.UserVisibleName()).ToCString());
-          new_object = ThrowTypeError(new_pos, type_bound);
-        }
-        type_bound = AbstractType::null();
+      CacheConstantValue(new_pos, const_instance);
+    }
+    new_object = new(Z) LiteralNode(new_pos, const_instance);
+    if (!type_bound.IsNull()) {
+      ASSERT(!type_bound.IsMalformed());
+      Error& malformed_error = Error::Handle(Z);
+      ASSERT(!is_top_level_);  // We cannot check unresolved types.
+      if (!const_instance.IsInstanceOf(type_bound,
+                                       TypeArguments::Handle(Z),
+                                       &malformed_error)) {
+        type_bound = ClassFinalizer::NewFinalizedMalformedType(
+            malformed_error,
+            script_,
+            new_pos,
+            "const factory result is not an instance of '%s'",
+            String::Handle(Z, type_bound.UserVisibleName()).ToCString());
+        new_object = ThrowTypeError(new_pos, type_bound);
       }
+      type_bound = AbstractType::null();
     }
   } else {
     CheckConstructorCallTypeArguments(new_pos, constructor, type_arguments);
     if (!type_arguments.IsNull() &&
         !type_arguments.IsInstantiated() &&
         (current_block_->scope->function_level() > 0)) {
       // Make sure that the instantiator is captured.
       CaptureInstantiator();
     }
     // If the type argument vector is not instantiated, we verify in checked
@@ skipping 738 matching lines @@
 void Parser::SkipQualIdent() {
   ASSERT(IsIdentifier());
   ConsumeToken();
   if (CurrentToken() == Token::kPERIOD) {
     ConsumeToken();  // Consume the kPERIOD token.
     ExpectIdentifier("identifier expected after '.'");
   }
 }
 
 }  // namespace dart