Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(47)

Side by Side Diff: src/hydrogen.cc

Issue 757143002: Optimize non-mutation Map and Set operations for String keys (Closed) Base URL: https://chromium.googlesource.com/v8/v8.git@master
Patch Set: Replace End calls with IfBuilder destructor Created 6 years ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch
« no previous file with comments | « src/hydrogen.h ('k') | src/hydrogen-instructions.h » ('j') | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
1 // Copyright 2013 the V8 project authors. All rights reserved. 1 // Copyright 2013 the V8 project authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be 2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file. 3 // found in the LICENSE file.
4 4
5 #include "src/hydrogen.h" 5 #include "src/hydrogen.h"
6 6
7 #include <sstream> 7 #include <sstream>
8 8
9 #include "src/v8.h" 9 #include "src/v8.h"
10 10
(...skipping 12086 matching lines...) Expand 10 before | Expand all | Expand 10 after
12097 12097
12098 void HOptimizedGraphBuilder::GenerateMathSqrtRT(CallRuntime* call) { 12098 void HOptimizedGraphBuilder::GenerateMathSqrtRT(CallRuntime* call) {
12099 DCHECK(call->arguments()->length() == 1); 12099 DCHECK(call->arguments()->length() == 1);
12100 CHECK_ALIVE(VisitForValue(call->arguments()->at(0))); 12100 CHECK_ALIVE(VisitForValue(call->arguments()->at(0)));
12101 HValue* value = Pop(); 12101 HValue* value = Pop();
12102 HInstruction* result = NewUncasted<HUnaryMathOperation>(value, kMathSqrt); 12102 HInstruction* result = NewUncasted<HUnaryMathOperation>(value, kMathSqrt);
12103 return ast_context()->ReturnInstruction(result, call->id()); 12103 return ast_context()->ReturnInstruction(result, call->id());
12104 } 12104 }
12105 12105
12106 12106
12107 template <typename CollectionType>
12108 HValue* HOptimizedGraphBuilder::BuildOrderedHashTableFindEntry(HValue* table,
12109 HValue* key,
12110 HValue* hash) {
12111 HValue* num_buckets = Add<HLoadNamedField>(
12112 table, static_cast<HValue*>(NULL),
12113 HObjectAccess::ForOrderedHashTableNumberOfBuckets<CollectionType>());
12114
12115 // Some things that won't change inside the loop
12116 HValue* not_found = Add<HConstant>(CollectionType::kNotFound);
12117 HValue* start_index = Add<HConstant>(CollectionType::kHashTableStartIndex);
12118 HValue* entry_size = Add<HConstant>(CollectionType::kEntrySize);
12119 HValue* chain_offset = Add<HConstant>(CollectionType::kChainOffset);
12120 HValue* key_start = AddUncasted<HAdd>(start_index, num_buckets);
12121 key_start->ClearFlag(HValue::kCanOverflow);
12122
12123 // BuildHashToBucket
12124 HValue* mask = AddUncasted<HSub>(num_buckets, graph()->GetConstant1());
12125 mask->ChangeRepresentation(Representation::Integer32());
12126 mask->ClearFlag(HValue::kCanOverflow);
12127
12128 HValue* bucket = AddUncasted<HBitwise>(Token::BIT_AND, hash, mask);
12129
12130 // BuildHashToEntry
12131 HValue* entry_index = AddUncasted<HAdd>(start_index, bucket);
12132 entry_index->ClearFlag(HValue::kCanOverflow);
12133 HValue* entry =
12134 Add<HLoadKeyed>(table, entry_index, static_cast<HValue*>(NULL),
12135 FAST_ELEMENTS, ALLOW_RETURN_HOLE);
12136 entry->set_type(HType::Smi());
12137
12138 Push(entry);
12139
12140 LoopBuilder loop(this);
12141 loop.BeginBody(1);
12142
12143 entry = Pop();
12144
12145 {
12146 IfBuilder if_not_found(this);
12147 if_not_found.If<HCompareNumericAndBranch>(entry, not_found, Token::EQ);
12148 if_not_found.Then();
12149 Push(entry);
12150 loop.Break();
12151 }
12152
12153 // BuildEntryToIndex
12154 HValue* key_index = AddUncasted<HMul>(entry, entry_size);
12155 key_index->ClearFlag(HValue::kCanOverflow);
12156 key_index = AddUncasted<HAdd>(key_index, key_start);
12157 key_index->ClearFlag(HValue::kCanOverflow);
12158 // BuildKeyAt
12159 HValue* candidate_key =
12160 Add<HLoadKeyed>(table, key_index, static_cast<HValue*>(NULL),
12161 FAST_ELEMENTS, ALLOW_RETURN_HOLE);
12162
12163 {
12164 IfBuilder if_keys_equal(this);
12165 if_keys_equal.If<HIsStringAndBranch>(candidate_key);
12166 if_keys_equal.AndIf<HStringCompareAndBranch>(candidate_key, key,
12167 Token::EQ_STRICT);
12168 if_keys_equal.Then();
12169 Push(key_index);
12170 loop.Break();
12171 }
12172
12173 // BuildChainAt
12174 HValue* chain_index = AddUncasted<HMul>(entry, entry_size);
12175 chain_index->ClearFlag(HValue::kCanOverflow);
12176 chain_index = AddUncasted<HAdd>(chain_index, key_start);
12177 chain_index->ClearFlag(HValue::kCanOverflow);
12178 chain_index = AddUncasted<HAdd>(chain_index, chain_offset);
12179 chain_index->ClearFlag(HValue::kCanOverflow);
12180 entry = Add<HLoadKeyed>(table, chain_index, static_cast<HValue*>(NULL),
12181 FAST_ELEMENTS, ALLOW_RETURN_HOLE);
12182 entry->set_type(HType::Smi());
12183 Push(entry);
12184
12185 loop.EndBody();
12186
12187 return Pop();
12188 }
12189
12190
12191 void HOptimizedGraphBuilder::GenerateMapGet(CallRuntime* call) {
12192 DCHECK(call->arguments()->length() == 2);
12193 CHECK_ALIVE(VisitForValue(call->arguments()->at(0)));
12194 CHECK_ALIVE(VisitForValue(call->arguments()->at(1)));
12195 HValue* key = Pop();
12196 HValue* receiver = Pop();
12197
12198 NoObservableSideEffectsScope no_effects(this);
12199
12200 HIfContinuation continuation;
12201 HValue* hash =
12202 BuildStringHashLoadIfIsStringAndHashComputed(key, &continuation);
12203 {
12204 IfBuilder string_checker(this, &continuation);
12205 string_checker.Then();
12206 {
12207 HValue* table =
12208 Add<HLoadNamedField>(receiver, static_cast<HValue*>(NULL),
12209 HObjectAccess::ForJSCollectionTable());
12210 HValue* key_index =
12211 BuildOrderedHashTableFindEntry<OrderedHashMap>(table, key, hash);
12212 IfBuilder if_found(this);
12213 if_found.If<HCompareNumericAndBranch>(
12214 key_index, Add<HConstant>(OrderedHashMap::kNotFound), Token::NE);
12215 if_found.Then();
12216 {
12217 HValue* value_index = AddUncasted<HAdd>(
12218 key_index, Add<HConstant>(OrderedHashMap::kValueOffset));
12219 value_index->ClearFlag(HValue::kCanOverflow);
12220 Push(Add<HLoadKeyed>(table, value_index, static_cast<HValue*>(NULL),
12221 FAST_ELEMENTS));
12222 }
12223 if_found.Else();
12224 Push(graph()->GetConstantUndefined());
12225 if_found.End();
12226 }
12227 string_checker.Else();
12228 {
12229 Add<HPushArguments>(receiver, key);
12230 Push(Add<HCallRuntime>(call->name(),
12231 Runtime::FunctionForId(Runtime::kMapGet), 2));
12232 }
12233 }
12234
12235 return ast_context()->ReturnValue(Pop());
12236 }
12237
12238
12239 HValue* HOptimizedGraphBuilder::BuildStringHashLoadIfIsStringAndHashComputed(
12240 HValue* object, HIfContinuation* continuation) {
12241 IfBuilder string_checker(this);
12242 string_checker.If<HIsStringAndBranch>(object);
12243 string_checker.And();
12244 HValue* hash = Add<HLoadNamedField>(object, static_cast<HValue*>(NULL),
12245 HObjectAccess::ForStringHashField());
12246 HValue* hash_not_computed_mask = Add<HConstant>(String::kHashNotComputedMask);
12247 HValue* hash_computed_test =
12248 AddUncasted<HBitwise>(Token::BIT_AND, hash, hash_not_computed_mask);
12249 string_checker.If<HCompareNumericAndBranch>(
12250 hash_computed_test, graph()->GetConstant0(), Token::EQ);
12251 string_checker.Then();
12252 HValue* shifted_hash =
12253 AddUncasted<HShr>(hash, Add<HConstant>(String::kHashShift));
12254 string_checker.CaptureContinuation(continuation);
12255 return shifted_hash;
12256 }
12257
12258
12259 template <typename CollectionType>
12260 void HOptimizedGraphBuilder::BuildJSCollectionHas(
12261 CallRuntime* call, const Runtime::Function* c_function) {
12262 DCHECK(call->arguments()->length() == 2);
12263 CHECK_ALIVE(VisitForValue(call->arguments()->at(0)));
12264 CHECK_ALIVE(VisitForValue(call->arguments()->at(1)));
12265 HValue* key = Pop();
12266 HValue* receiver = Pop();
12267
12268 NoObservableSideEffectsScope no_effects(this);
12269
12270 HIfContinuation continuation;
12271 HValue* hash =
12272 BuildStringHashLoadIfIsStringAndHashComputed(key, &continuation);
12273 {
12274 IfBuilder string_checker(this, &continuation);
12275 string_checker.Then();
12276 {
12277 HValue* table =
12278 Add<HLoadNamedField>(receiver, static_cast<HValue*>(NULL),
12279 HObjectAccess::ForJSCollectionTable());
12280 HValue* key_index =
12281 BuildOrderedHashTableFindEntry<CollectionType>(table, key, hash);
12282 {
12283 IfBuilder if_found(this);
12284 if_found.If<HCompareNumericAndBranch>(
12285 key_index, Add<HConstant>(CollectionType::kNotFound), Token::NE);
12286 if_found.Then();
12287 Push(graph()->GetConstantTrue());
12288 if_found.Else();
12289 Push(graph()->GetConstantFalse());
12290 }
12291 }
12292 string_checker.Else();
12293 {
12294 Add<HPushArguments>(receiver, key);
12295 Push(Add<HCallRuntime>(call->name(), c_function, 2));
12296 }
12297 }
12298
12299 return ast_context()->ReturnValue(Pop());
12300 }
12301
12302
12303 void HOptimizedGraphBuilder::GenerateMapHas(CallRuntime* call) {
12304 BuildJSCollectionHas<OrderedHashMap>(
12305 call, Runtime::FunctionForId(Runtime::kMapHas));
12306 }
12307
12308
12309 void HOptimizedGraphBuilder::GenerateSetHas(CallRuntime* call) {
12310 BuildJSCollectionHas<OrderedHashSet>(
12311 call, Runtime::FunctionForId(Runtime::kSetHas));
12312 }
12313
12314
12315 void HOptimizedGraphBuilder::GenerateSetGetSize(CallRuntime* call) {
12316 DCHECK(call->arguments()->length() == 1);
12317 CHECK_ALIVE(VisitForValue(call->arguments()->at(0)));
12318 HValue* receiver = Pop();
12319 HValue* table = Add<HLoadNamedField>(receiver, static_cast<HValue*>(NULL),
12320 HObjectAccess::ForJSCollectionTable());
12321 HInstruction* result = New<HLoadNamedField>(
12322 table, static_cast<HValue*>(NULL),
12323 HObjectAccess::ForOrderedHashTableNumberOfElements<OrderedHashSet>());
12324 return ast_context()->ReturnInstruction(result, call->id());
12325 }
12326
12327
12328 void HOptimizedGraphBuilder::GenerateMapGetSize(CallRuntime* call) {
12329 DCHECK(call->arguments()->length() == 1);
12330 CHECK_ALIVE(VisitForValue(call->arguments()->at(0)));
12331 HValue* receiver = Pop();
12332 HValue* table = Add<HLoadNamedField>(receiver, static_cast<HValue*>(NULL),
12333 HObjectAccess::ForJSCollectionTable());
12334 HInstruction* result = New<HLoadNamedField>(
12335 table, static_cast<HValue*>(NULL),
12336 HObjectAccess::ForOrderedHashTableNumberOfElements<OrderedHashMap>());
12337 return ast_context()->ReturnInstruction(result, call->id());
12338 }
12339
12340
12107 void HOptimizedGraphBuilder::GenerateGetCachedArrayIndex(CallRuntime* call) { 12341 void HOptimizedGraphBuilder::GenerateGetCachedArrayIndex(CallRuntime* call) {
12108 DCHECK(call->arguments()->length() == 1); 12342 DCHECK(call->arguments()->length() == 1);
12109 CHECK_ALIVE(VisitForValue(call->arguments()->at(0))); 12343 CHECK_ALIVE(VisitForValue(call->arguments()->at(0)));
12110 HValue* value = Pop(); 12344 HValue* value = Pop();
12111 HGetCachedArrayIndex* result = New<HGetCachedArrayIndex>(value); 12345 HGetCachedArrayIndex* result = New<HGetCachedArrayIndex>(value);
12112 return ast_context()->ReturnInstruction(result, call->id()); 12346 return ast_context()->ReturnInstruction(result, call->id());
12113 } 12347 }
12114 12348
12115 12349
12116 void HOptimizedGraphBuilder::GenerateFastOneByteArrayJoin(CallRuntime* call) { 12350 void HOptimizedGraphBuilder::GenerateFastOneByteArrayJoin(CallRuntime* call) {
(...skipping 659 matching lines...) Expand 10 before | Expand all | Expand 10 after
12776 if (ShouldProduceTraceOutput()) { 13010 if (ShouldProduceTraceOutput()) {
12777 isolate()->GetHTracer()->TraceHydrogen(name(), graph_); 13011 isolate()->GetHTracer()->TraceHydrogen(name(), graph_);
12778 } 13012 }
12779 13013
12780 #ifdef DEBUG 13014 #ifdef DEBUG
12781 graph_->Verify(false); // No full verify. 13015 graph_->Verify(false); // No full verify.
12782 #endif 13016 #endif
12783 } 13017 }
12784 13018
12785 } } // namespace v8::internal 13019 } } // namespace v8::internal
OLDNEW
« no previous file with comments | « src/hydrogen.h ('k') | src/hydrogen-instructions.h » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698