LCOV - code coverage report
Current view: top level - src/interpreter - constant-array-builder.cc (source / functions) Hit Total Coverage
Test: app.info Lines: 98 115 85.2 %
Date: 2017-04-26 Functions: 25 31 80.6 %

          Line data    Source code
       1             : // Copyright 2015 the V8 project authors. All rights reserved.
       2             : // Use of this source code is governed by a BSD-style license that can be
       3             : // found in the LICENSE file.
       4             : 
       5             : #include "src/interpreter/constant-array-builder.h"
       6             : 
       7             : #include <functional>
       8             : #include <set>
       9             : 
      10             : #include "src/ast/ast-value-factory.h"
      11             : #include "src/ast/ast.h"
      12             : #include "src/ast/scopes.h"
      13             : #include "src/base/functional.h"
      14             : #include "src/isolate.h"
      15             : #include "src/objects-inl.h"
      16             : 
      17             : namespace v8 {
      18             : namespace internal {
      19             : namespace interpreter {
      20             : 
      21           0 : ConstantArrayBuilder::ConstantArraySlice::ConstantArraySlice(
      22             :     Zone* zone, size_t start_index, size_t capacity, OperandSize operand_size)
      23             :     : start_index_(start_index),
      24             :       capacity_(capacity),
      25             :       reserved_(0),
      26             :       operand_size_(operand_size),
      27     6314798 :       constants_(zone) {}
      28             : 
      29           0 : void ConstantArrayBuilder::ConstantArraySlice::Reserve() {
      30             :   DCHECK_GT(available(), 0u);
      31     3053527 :   reserved_++;
      32             :   DCHECK_LE(reserved_, capacity() - constants_.size());
      33           0 : }
      34             : 
      35           0 : void ConstantArrayBuilder::ConstantArraySlice::Unreserve() {
      36             :   DCHECK_GT(reserved_, 0u);
      37     3053530 :   reserved_--;
      38           0 : }
      39             : 
      40           0 : size_t ConstantArrayBuilder::ConstantArraySlice::Allocate(
      41    12380537 :     ConstantArrayBuilder::Entry entry) {
      42             :   DCHECK_GT(available(), 0u);
      43           0 :   size_t index = constants_.size();
      44             :   DCHECK_LT(index, capacity());
      45    12380531 :   constants_.push_back(entry);
      46    12380537 :   return index + start_index();
      47             : }
      48             : 
      49           0 : ConstantArrayBuilder::Entry& ConstantArrayBuilder::ConstantArraySlice::At(
      50     3994782 :     size_t index) {
      51             :   DCHECK_GE(index, start_index());
      52             :   DCHECK_LT(index, start_index() + size());
      53     3994782 :   return constants_[index - start_index()];
      54             : }
      55             : 
      56           0 : const ConstantArrayBuilder::Entry& ConstantArrayBuilder::ConstantArraySlice::At(
      57           0 :     size_t index) const {
      58             :   DCHECK_GE(index, start_index());
      59             :   DCHECK_LT(index, start_index() + size());
      60    12555885 :   return constants_[index - start_index()];
      61             : }
      62             : 
      63             : #if DEBUG
      64             : void ConstantArrayBuilder::ConstantArraySlice::CheckAllElementsAreUnique(
      65             :     Isolate* isolate) const {
      66             :   std::set<Object*> elements;
      67             :   for (const Entry& entry : constants_) {
      68             :     Handle<Object> handle = entry.ToHandle(isolate);
      69             :     if (elements.find(*handle) != elements.end()) {
      70             :       std::ostringstream os;
      71             :       os << "Duplicate constant found: " << Brief(*handle) << std::endl;
      72             :       // Print all the entries in the slice to help debug duplicates.
      73             :       size_t i = start_index();
      74             :       for (const Entry& prev_entry : constants_) {
      75             :         os << i++ << ": " << Brief(*prev_entry.ToHandle(isolate)) << std::endl;
      76             :       }
      77             :       FATAL(os.str().c_str());
      78             :     }
      79             :     elements.insert(*handle);
      80             :   }
      81             : }
      82             : #endif
      83             : 
      84             : STATIC_CONST_MEMBER_DEFINITION const size_t ConstantArrayBuilder::k8BitCapacity;
      85             : STATIC_CONST_MEMBER_DEFINITION const size_t
      86             :     ConstantArrayBuilder::k16BitCapacity;
      87             : STATIC_CONST_MEMBER_DEFINITION const size_t
      88             :     ConstantArrayBuilder::k32BitCapacity;
      89             : 
      90     2104926 : ConstantArrayBuilder::ConstantArrayBuilder(Zone* zone)
      91             :     : constants_map_(16, base::KeyEqualityMatcher<intptr_t>(),
      92             :                      ZoneAllocationPolicy(zone)),
      93             :       smi_map_(zone),
      94             :       smi_pairs_(zone),
      95             : #define INIT_SINGLETON_ENTRY_FIELD(NAME, LOWER_NAME) LOWER_NAME##_(-1),
      96             :       SINGLETON_CONSTANT_ENTRY_TYPES(INIT_SINGLETON_ENTRY_FIELD)
      97             : #undef INIT_SINGLETON_ENTRY_FIELD
      98     4209848 :           zone_(zone) {
      99             :   idx_slice_[0] =
     100     2104934 :       new (zone) ConstantArraySlice(zone, 0, k8BitCapacity, OperandSize::kByte);
     101             :   idx_slice_[1] = new (zone) ConstantArraySlice(
     102     2104933 :       zone, k8BitCapacity, k16BitCapacity, OperandSize::kShort);
     103             :   idx_slice_[2] = new (zone) ConstantArraySlice(
     104     2104931 :       zone, k8BitCapacity + k16BitCapacity, k32BitCapacity, OperandSize::kQuad);
     105     2104931 : }
     106             : 
     107     2114511 : size_t ConstantArrayBuilder::size() const {
     108             :   size_t i = arraysize(idx_slice_);
     109     8791140 :   while (i > 0) {
     110     8106960 :     ConstantArraySlice* slice = idx_slice_[--i];
     111     6334539 :     if (slice->size() > 0) {
     112     1772421 :       return slice->start_index() + slice->size();
     113             :     }
     114             :   }
     115      684180 :   return idx_slice_[0]->size();
     116             : }
     117             : 
     118     4303327 : ConstantArrayBuilder::ConstantArraySlice* ConstantArrayBuilder::IndexToSlice(
     119             :     size_t index) const {
     120     5006891 :   for (ConstantArraySlice* slice : idx_slice_) {
     121     5006891 :     if (index <= slice->max_index()) {
     122             :       return slice;
     123             :     }
     124             :   }
     125           0 :   UNREACHABLE();
     126             :   return nullptr;
     127             : }
     128             : 
     129      308545 : MaybeHandle<Object> ConstantArrayBuilder::At(size_t index,
     130             :                                              Isolate* isolate) const {
     131      308545 :   const ConstantArraySlice* slice = IndexToSlice(index);
     132             :   DCHECK_LT(index, slice->capacity());
     133      308545 :   if (index < slice->start_index() + slice->size()) {
     134      308289 :     const Entry& entry = slice->At(index);
     135      308289 :     if (!entry.IsDeferred()) return entry.ToHandle(isolate);
     136             :   }
     137             :   return MaybeHandle<Object>();
     138             : }
     139             : 
     140     2103833 : Handle<FixedArray> ConstantArrayBuilder::ToFixedArray(Isolate* isolate) {
     141             :   Handle<FixedArray> fixed_array = isolate->factory()->NewFixedArrayWithHoles(
     142     2103833 :       static_cast<int>(size()), PretenureFlag::TENURED);
     143             :   int array_index = 0;
     144    16462875 :   for (const ConstantArraySlice* slice : idx_slice_) {
     145             :     DCHECK_EQ(slice->reserved(), 0);
     146             :     DCHECK(array_index == 0 ||
     147             :            base::bits::IsPowerOfTwo32(static_cast<uint32_t>(array_index)));
     148             : #if DEBUG
     149             :     // Different slices might contain the same element due to reservations, but
     150             :     // all elements within a slice should be unique. If this DCHECK fails, then
     151             :     // the AST nodes are not being internalized within a CanonicalHandleScope.
     152             :     slice->CheckAllElementsAreUnique(isolate);
     153             : #endif
     154             :     // Copy objects from slice into array.
     155    28710470 :     for (size_t i = 0; i < slice->size(); ++i) {
     156             :       fixed_array->set(array_index++,
     157    48990378 :                        *slice->At(slice->start_index() + i).ToHandle(isolate));
     158             :     }
     159             :     // Leave holes where reservations led to unused slots.
     160     2107639 :     size_t padding = slice->capacity() - slice->size();
     161     2107639 :     if (static_cast<size_t>(fixed_array->length() - array_index) <= padding) {
     162             :       break;
     163             :     }
     164        3798 :     array_index += padding;
     165             :   }
     166             :   DCHECK_GE(array_index, fixed_array->length());
     167     2103841 :   return fixed_array;
     168             : }
     169             : 
     170       32640 : size_t ConstantArrayBuilder::Insert(Smi* smi) {
     171             :   auto entry = smi_map_.find(smi);
     172       32640 :   if (entry == smi_map_.end()) {
     173       32640 :     return AllocateReservedEntry(smi);
     174             :   }
     175           0 :   return entry->second;
     176             : }
     177             : 
     178    11202964 : size_t ConstantArrayBuilder::Insert(const AstRawString* raw_string) {
     179             :   return constants_map_
     180             :       .LookupOrInsert(reinterpret_cast<intptr_t>(raw_string),
     181             :                       raw_string->hash(),
     182    14226122 :                       [&]() { return AllocateIndex(Entry(raw_string)); },
     183    33608891 :                       ZoneAllocationPolicy(zone_))
     184    22405926 :       ->value;
     185             : }
     186             : 
     187      861815 : size_t ConstantArrayBuilder::Insert(const AstValue* heap_number) {
     188             :   // This method only accepts heap numbers. Other types of ast value should
     189             :   // either be passed through as raw values (in the case of strings), use the
     190             :   // singleton Insert methods (in the case of symbols), or skip the constant
     191             :   // pool entirely and use bytecodes with immediate values (Smis, booleans,
     192             :   // undefined, etc.).
     193             :   DCHECK(heap_number->IsHeapNumber());
     194             :   return constants_map_
     195             :       .LookupOrInsert(reinterpret_cast<intptr_t>(heap_number),
     196             :                       static_cast<uint32_t>(base::hash_value(heap_number)),
     197     1723114 :                       [&]() { return AllocateIndex(Entry(heap_number)); },
     198     3447260 :                       ZoneAllocationPolicy(zone_))
     199     1723630 :       ->value;
     200             : }
     201             : 
     202      184273 : size_t ConstantArrayBuilder::Insert(const Scope* scope) {
     203             :   return constants_map_
     204             :       .LookupOrInsert(reinterpret_cast<intptr_t>(scope),
     205             :                       static_cast<uint32_t>(base::hash_value(scope)),
     206      368542 :                       [&]() { return AllocateIndex(Entry(scope)); },
     207      737092 :                       ZoneAllocationPolicy(zone_))
     208      368546 :       ->value;
     209             : }
     210             : 
     211             : #define INSERT_ENTRY(NAME, LOWER_NAME)              \
     212             :   size_t ConstantArrayBuilder::Insert##NAME() {     \
     213             :     if (LOWER_NAME##_ < 0) {                        \
     214             :       LOWER_NAME##_ = AllocateIndex(Entry::NAME()); \
     215             :     }                                               \
     216             :     return LOWER_NAME##_;                           \
     217             :   }
     218       94262 : SINGLETON_CONSTANT_ENTRY_TYPES(INSERT_ENTRY)
     219             : #undef INSERT_ENTRY
     220             : 
     221    12380531 : ConstantArrayBuilder::index_t ConstantArrayBuilder::AllocateIndex(
     222             :     ConstantArrayBuilder::Entry entry) {
     223    13948014 :   for (size_t i = 0; i < arraysize(idx_slice_); ++i) {
     224    27896028 :     if (idx_slice_[i]->available() > 0) {
     225    12380537 :       return static_cast<index_t>(idx_slice_[i]->Allocate(entry));
     226             :     }
     227             :   }
     228           0 :   UNREACHABLE();
     229             :   return kMaxUInt32;
     230             : }
     231             : 
     232             : ConstantArrayBuilder::ConstantArraySlice*
     233     3055237 : ConstantArrayBuilder::OperandSizeToSlice(OperandSize operand_size) const {
     234             :   ConstantArraySlice* slice = nullptr;
     235     3055237 :   switch (operand_size) {
     236             :     case OperandSize::kNone:
     237           0 :       UNREACHABLE();
     238             :       break;
     239             :     case OperandSize::kByte:
     240     2800552 :       slice = idx_slice_[0];
     241     2800552 :       break;
     242             :     case OperandSize::kShort:
     243      189142 :       slice = idx_slice_[1];
     244      189142 :       break;
     245             :     case OperandSize::kQuad:
     246       65543 :       slice = idx_slice_[2];
     247       65543 :       break;
     248             :   }
     249             :   DCHECK(slice->operand_size() == operand_size);
     250     3055237 :   return slice;
     251             : }
     252             : 
     253     3994775 : size_t ConstantArrayBuilder::InsertDeferred() {
     254     3994775 :   return AllocateIndex(Entry::Deferred());
     255             : }
     256             : 
     257     3994782 : void ConstantArrayBuilder::SetDeferredAt(size_t index, Handle<Object> object) {
     258     3994782 :   ConstantArraySlice* slice = IndexToSlice(index);
     259     3994782 :   return slice->At(index).SetDeferred(object);
     260             : }
     261             : 
     262     3053527 : OperandSize ConstantArrayBuilder::CreateReservedEntry() {
     263     3373391 :   for (size_t i = 0; i < arraysize(idx_slice_); ++i) {
     264     9800309 :     if (idx_slice_[i]->available() > 0) {
     265             :       idx_slice_[i]->Reserve();
     266             :       return idx_slice_[i]->operand_size();
     267             :     }
     268             :   }
     269           0 :   UNREACHABLE();
     270             :   return OperandSize::kNone;
     271             : }
     272             : 
     273      157444 : ConstantArrayBuilder::index_t ConstantArrayBuilder::AllocateReservedEntry(
     274             :     Smi* value) {
     275      314888 :   index_t index = static_cast<index_t>(AllocateIndex(Entry(value)));
     276      157444 :   smi_map_[value] = index;
     277      157444 :   return index;
     278             : }
     279             : 
     280      126255 : size_t ConstantArrayBuilder::CommitReservedEntry(OperandSize operand_size,
     281             :                                                  Smi* value) {
     282             :   DiscardReservedEntry(operand_size);
     283             :   size_t index;
     284             :   auto entry = smi_map_.find(value);
     285      126255 :   if (entry == smi_map_.end()) {
     286      124548 :     index = AllocateReservedEntry(value);
     287             :   } else {
     288        1707 :     ConstantArraySlice* slice = OperandSizeToSlice(operand_size);
     289        1707 :     index = entry->second;
     290        1707 :     if (index > slice->max_index()) {
     291             :       // The object is already in the constant array, but may have an
     292             :       // index too big for the reserved operand_size. So, duplicate
     293             :       // entry with the smaller operand size.
     294         256 :       index = AllocateReservedEntry(value);
     295             :     }
     296             :     DCHECK_LE(index, slice->max_index());
     297             :   }
     298      126255 :   return index;
     299             : }
     300             : 
     301     2927275 : void ConstantArrayBuilder::DiscardReservedEntry(OperandSize operand_size) {
     302     3053530 :   OperandSizeToSlice(operand_size)->Unreserve();
     303     2927275 : }
     304             : 
     305    12523244 : Handle<Object> ConstantArrayBuilder::Entry::ToHandle(Isolate* isolate) const {
     306    12523244 :   switch (tag_) {
     307             :     case Tag::kDeferred:
     308             :       // We shouldn't have any deferred entries by now.
     309           0 :       UNREACHABLE();
     310             :       return Handle<Object>::null();
     311             :     case Tag::kHandle:
     312     3994781 :       return handle_;
     313             :     case Tag::kSmi:
     314      454914 :       return handle(smi_, isolate);
     315             :     case Tag::kRawString:
     316     7111983 :       return raw_string_->string();
     317             :     case Tag::kHeapNumber:
     318             :       DCHECK(heap_number_->IsHeapNumber());
     319      935327 :       return heap_number_->value();
     320             :     case Tag::kScope:
     321      184259 :       return scope_->scope_info();
     322             : #define ENTRY_LOOKUP(Name, name) \
     323             :   case Tag::k##Name:             \
     324             :     return isolate->factory()->name();
     325       69437 :       SINGLETON_CONSTANT_ENTRY_TYPES(ENTRY_LOOKUP);
     326             : #undef ENTRY_LOOKUP
     327             :   }
     328           0 :   UNREACHABLE();
     329             :   return Handle<Object>::null();
     330             : }
     331             : 
     332             : }  // namespace interpreter
     333             : }  // namespace internal
     334             : }  // namespace v8

Generated by: LCOV version 1.10