Introduce per-isolate cache for compile time constants

runtime/vm/parser.cc

Index: runtime/vm/parser.cc
diff --git a/runtime/vm/parser.cc b/runtime/vm/parser.cc
index 286fbe7c97da52bdfd5ff7d32fafc8f6d5d81e9f..f83dd78df2da91c2ff65dbfc575d935f66be2849 100644
--- a/runtime/vm/parser.cc
+++ b/runtime/vm/parser.cc
@@ -16,6 +16,7 @@
 #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"
@@ -11885,6 +11886,62 @@ bool Parser::IsInstantiatorRequired() const {
 }
 
 
+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()) {
@@ -12507,6 +12564,15 @@ AstNode* Parser::ParseListLiteral(intptr_t type_pos,
   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();
 
@@ -12574,8 +12640,8 @@ AstNode* Parser::ParseListLiteral(intptr_t type_pos,
 
   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);
@@ -12607,6 +12673,7 @@ AstNode* Parser::ParseListLiteral(intptr_t type_pos,
     }
     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.
@@ -12700,8 +12767,16 @@ AstNode* Parser::ParseMapLiteral(intptr_t type_pos,
   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 =
@@ -12858,6 +12933,7 @@ AstNode* Parser::ParseMapLiteral(intptr_t type_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()));
     }
@@ -13401,41 +13477,43 @@ AstNode* Parser::ParseNewOperator(Token::Kind op_kind) {
                   "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);