Turn the unresolved-references list into a linked list using the VariableProxies themselves

src/ast/scopes.cc

 // Copyright 2012 the V8 project authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "src/ast/scopes.h"
 
 #include "src/accessors.h"
 #include "src/ast/scopeinfo.h"
 #include "src/bootstrapper.h"
 #include "src/messages.h"
@@ skipping 70 matching lines @@
 
 // ----------------------------------------------------------------------------
 // Implementation of Scope
 
 Scope::Scope(Zone* zone, Scope* outer_scope, ScopeType scope_type,
              AstValueFactory* ast_value_factory, FunctionKind function_kind)
     : inner_scopes_(4, zone),
       variables_(zone),
       temps_(4, zone),
       params_(4, zone),
-      unresolved_(16, zone),
+      unresolved_(nullptr),
       decls_(4, zone),
       module_descriptor_(scope_type == MODULE_SCOPE ? new (zone)
                                                           ModuleDescriptor(zone)
                                                     : NULL),
       sloppy_block_function_map_(zone),
       already_resolved_(false),
       ast_value_factory_(ast_value_factory),
       zone_(zone) {
   SetDefaults(scope_type, outer_scope, Handle<ScopeInfo>::null(),
               function_kind);
   // The outermost scope must be a script scope.
   DCHECK(scope_type == SCRIPT_SCOPE || outer_scope != NULL);
 }
 
 Scope::Scope(Zone* zone, Scope* inner_scope, ScopeType scope_type,
              Handle<ScopeInfo> scope_info, AstValueFactory* value_factory)
     : inner_scopes_(4, zone),
       variables_(zone),
       temps_(4, zone),
       params_(4, zone),
-      unresolved_(16, zone),

[adamk, 2016/07/18 16:54:34]

I wonder if it was this 16 that was causing excess peak usage. Otherwise I'd
have expected that adding a word to every VariableProxy would be more expensive.

+      unresolved_(nullptr),
       decls_(4, zone),
       module_descriptor_(NULL),
       sloppy_block_function_map_(zone),
       already_resolved_(true),
       ast_value_factory_(value_factory),
       zone_(zone) {
   SetDefaults(scope_type, NULL, scope_info);
   if (!scope_info.is_null()) {
     num_heap_slots_ = scope_info_->ContextLength();
   }
   // Ensure at least MIN_CONTEXT_SLOTS to indicate a materialized context.
   num_heap_slots_ = Max(num_heap_slots_,
                         static_cast<int>(Context::MIN_CONTEXT_SLOTS));
   AddInnerScope(inner_scope);
 }
 
 Scope::Scope(Zone* zone, Scope* inner_scope,
              const AstRawString* catch_variable_name,
              AstValueFactory* value_factory)
     : inner_scopes_(1, zone),
       variables_(zone),
       temps_(0, zone),
       params_(0, zone),
-      unresolved_(0, zone),
+      unresolved_(nullptr),
       decls_(0, zone),
       module_descriptor_(NULL),
       sloppy_block_function_map_(zone),
       already_resolved_(true),
       ast_value_factory_(value_factory),
       zone_(zone) {
   SetDefaults(CATCH_SCOPE, NULL, Handle<ScopeInfo>::null());
   AddInnerScope(inner_scope);
   ++num_var_;
   num_heap_slots_ = Context::MIN_CONTEXT_SLOTS;
@@ skipping 199 matching lines @@
 
   // Remove this scope from outer scope.
   outer_scope()->RemoveInnerScope(this);
 
   // Reparent inner scopes.
   for (int i = 0; i < inner_scopes_.length(); i++) {
     outer_scope()->AddInnerScope(inner_scopes_[i]);
   }
 
   // Move unresolved variables
-  for (int i = 0; i < unresolved_.length(); i++) {
-    outer_scope()->unresolved_.Add(unresolved_[i], zone());
+  VariableProxy* unresolved = unresolved_;
+  if (outer_scope()->unresolved_ == nullptr) {
+    outer_scope()->unresolved_ = unresolved;
+  } else if (unresolved != nullptr) {
+    while (unresolved->next_unresolved() != nullptr) {
+      unresolved = unresolved->next_unresolved();
+    }
+    unresolved->set_next_unresolved(outer_scope()->unresolved_);
+    outer_scope()->unresolved_ = unresolved_;
   }
 
   PropagateUsageFlagsToScope(outer_scope_);
 
   return NULL;
 }
 
 
 void Scope::ReplaceOuterScope(Scope* outer) {
   DCHECK_NOT_NULL(outer);
@@ skipping 154 matching lines @@
   DCHECK(is_script_scope());
   return variables_.Declare(this,
                             name,
                             DYNAMIC_GLOBAL,
                             Variable::NORMAL,
                             kCreatedInitialized);
 }
 
 
 bool Scope::RemoveUnresolved(VariableProxy* var) {
-  // Most likely (always?) any variable we want to remove
-  // was just added before, so we search backwards.
-  for (int i = unresolved_.length(); i-- > 0;) {
-    if (unresolved_[i] == var) {
-      unresolved_.Remove(i);
+  if (unresolved_ == var) {
+    unresolved_ = var->next_unresolved();
+    var->set_next_unresolved(nullptr);
+    return true;
+  }
+  VariableProxy* current = unresolved_;
+  while (current != nullptr) {
+    VariableProxy* next = current->next_unresolved();
+    if (var == next) {
+      current->set_next_unresolved(next->next_unresolved());
+      var->set_next_unresolved(nullptr);
       return true;
     }
+    current = next;
   }
   return false;
 }
 
 
 Variable* Scope::NewTemporary(const AstRawString* name) {
   DCHECK(!already_resolved());
   Scope* scope = this->ClosureScope();
   Variable* var = new(zone()) Variable(scope,
                                        name,
@@ skipping 266 matching lines @@
   if (scope_info_.is_null()) {
     scope_info_ = ScopeInfo::Create(isolate, zone(), this);
   }
   return scope_info_;
 }
 
 Handle<StringSet> Scope::CollectNonLocals(Handle<StringSet> non_locals) {
   // Collect non-local variables referenced in the scope.
   // TODO(yangguo): store non-local variables explicitly if we can no longer
   //                rely on unresolved_ to find them.
-  for (int i = 0; i < unresolved_.length(); i++) {
-    VariableProxy* proxy = unresolved_[i];
+  for (VariableProxy* proxy = unresolved_; proxy != nullptr;
+       proxy = proxy->next_unresolved()) {
     if (proxy->is_resolved() && proxy->var()->IsStackAllocated()) continue;
     Handle<String> name = proxy->name();
     non_locals = StringSet::Add(non_locals, name);
   }
   for (int i = 0; i < inner_scopes_.length(); i++) {
     non_locals = inner_scopes_[i]->CollectNonLocals(non_locals);
   }
   return non_locals;
 }
 
@@ skipping 374 matching lines @@
 
   return true;
 }
 
 
 bool Scope::ResolveVariablesRecursively(ParseInfo* info,
                                         AstNodeFactory* factory) {
   DCHECK(info->script_scope()->is_script_scope());
 
   // Resolve unresolved variables for this scope.
-  for (int i = 0; i < unresolved_.length(); i++) {
-    if (!ResolveVariable(info, unresolved_[i], factory)) return false;
+  for (VariableProxy* proxy = unresolved_; proxy != nullptr;
+       proxy = proxy->next_unresolved()) {
+    if (!ResolveVariable(info, proxy, factory)) return false;
   }
 
   // Resolve unresolved variables for inner scopes.
   for (int i = 0; i < inner_scopes_.length(); i++) {
     if (!inner_scopes_[i]->ResolveVariablesRecursively(info, factory))
       return false;
   }
 
   return true;
 }
@@ skipping 303 matching lines @@
       function_ != NULL && function_->proxy()->var()->IsContextSlot();
   return num_heap_slots() - Context::MIN_CONTEXT_SLOTS - num_global_slots() -
          (is_function_var_in_context ? 1 : 0);
 }
 
 
 int Scope::ContextGlobalCount() const { return num_global_slots(); }
 
 }  // namespace internal
 }  // namespace v8