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

Side by Side Diff: src/hydrogen-check-elimination.cc

Issue 141653009: Check elimination improvement: propagation of state through phis is supported, CheckMap narrowing i… (Closed) Base URL: https://v8.googlecode.com/svn/branches/bleeding_edge
Patch Set: Review notes applied Created 6 years, 10 months 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 | Annotate | Revision Log
« no previous file with comments | « src/hydrogen.cc ('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 // Redistribution and use in source and binary forms, with or without 2 // Redistribution and use in source and binary forms, with or without
3 // modification, are permitted provided that the following conditions are 3 // modification, are permitted provided that the following conditions are
4 // met: 4 // met:
5 // 5 //
6 // * Redistributions of source code must retain the above copyright 6 // * Redistributions of source code must retain the above copyright
7 // notice, this list of conditions and the following disclaimer. 7 // notice, this list of conditions and the following disclaimer.
8 // * Redistributions in binary form must reproduce the above 8 // * Redistributions in binary form must reproduce the above
9 // copyright notice, this list of conditions and the following 9 // copyright notice, this list of conditions and the following
10 // disclaimer in the documentation and/or other materials provided 10 // disclaimer in the documentation and/or other materials provided
(...skipping 30 matching lines...) Expand all
41 // For code de-uglification. 41 // For code de-uglification.
42 #define TRACE(x) if (FLAG_trace_check_elimination) PrintF x 42 #define TRACE(x) if (FLAG_trace_check_elimination) PrintF x
43 43
44 namespace v8 { 44 namespace v8 {
45 namespace internal { 45 namespace internal {
46 46
47 typedef UniqueSet<Map>* MapSet; 47 typedef UniqueSet<Map>* MapSet;
48 48
49 struct HCheckTableEntry { 49 struct HCheckTableEntry {
50 HValue* object_; // The object being approximated. NULL => invalid entry. 50 HValue* object_; // The object being approximated. NULL => invalid entry.
51 HValue* check_; // The last check instruction. 51 HInstruction* check_; // The last check instruction.
52 MapSet maps_; // The set of known maps for the object. 52 MapSet maps_; // The set of known maps for the object.
53 }; 53 };
54 54
55 55
56 // The main datastructure used during check elimination, which stores a 56 // The main data structure used during check elimination, which stores a
57 // set of known maps for each object. 57 // set of known maps for each object.
58 class HCheckTable : public ZoneObject { 58 class HCheckTable : public ZoneObject {
59 public: 59 public:
60 static const int kMaxTrackedObjects = 10; 60 static const int kMaxTrackedObjects = 10;
61 61
62 explicit HCheckTable(HCheckEliminationPhase* phase) 62 explicit HCheckTable(HCheckEliminationPhase* phase)
63 : phase_(phase), 63 : phase_(phase),
64 cursor_(0), 64 cursor_(0),
65 size_(0) { 65 size_(0) {
66 } 66 }
(...skipping 56 matching lines...) Expand 10 before | Expand all | Expand 10 after
123 HCheckTableEntry* old_entry = &entries_[i]; 123 HCheckTableEntry* old_entry = &entries_[i];
124 HCheckTableEntry* new_entry = &copy->entries_[i]; 124 HCheckTableEntry* new_entry = &copy->entries_[i];
125 // TODO(titzer): keep the check if this block dominates the successor? 125 // TODO(titzer): keep the check if this block dominates the successor?
126 new_entry->object_ = old_entry->object_; 126 new_entry->object_ = old_entry->object_;
127 new_entry->check_ = NULL; 127 new_entry->check_ = NULL;
128 new_entry->maps_ = old_entry->maps_->Copy(phase_->zone()); 128 new_entry->maps_ = old_entry->maps_->Copy(phase_->zone());
129 } 129 }
130 copy->cursor_ = cursor_; 130 copy->cursor_ = cursor_;
131 copy->size_ = size_; 131 copy->size_ = size_;
132 132
133 // Create entries for succ block's phis.
134 if (succ->phis()->length() > 0) {
135 int pred_index = succ->PredecessorIndexOf(from_block);
136 for (int phi_index = 0;
137 phi_index < succ->phis()->length();
138 ++phi_index) {
139 HPhi* phi = succ->phis()->at(phi_index);
140 HValue* phi_operand = phi->OperandAt(pred_index);
141
142 HCheckTableEntry* pred_entry = copy->Find(phi_operand);
143 if (pred_entry != NULL) {
144 // Create an entry for a phi in the table.
145 copy->Insert(phi, NULL, pred_entry->maps_->Copy(phase_->zone()));
146 }
147 }
148 }
149
133 // Branch-sensitive analysis for certain comparisons may add more facts 150 // Branch-sensitive analysis for certain comparisons may add more facts
134 // to the state for the successor on the true branch. 151 // to the state for the successor on the true branch.
135 bool learned = false; 152 bool learned = false;
136 HControlInstruction* end = succ->predecessors()->at(0)->end(); 153 HControlInstruction* end = succ->predecessors()->at(0)->end();
137 if (succ->predecessors()->length() == 1 && end->SuccessorAt(0) == succ) { 154 if (succ->predecessors()->length() == 1 && end->SuccessorAt(0) == succ) {
138 if (end->IsCompareMap()) { 155 if (end->IsCompareMap()) {
139 // Learn on the true branch of if(CompareMap(x)). 156 // Learn on the true branch of if(CompareMap(x)).
140 HCompareMap* cmp = HCompareMap::cast(end); 157 HCompareMap* cmp = HCompareMap::cast(end);
141 HValue* object = cmp->value()->ActualValue(); 158 HValue* object = cmp->value()->ActualValue();
142 HCheckTableEntry* entry = copy->Find(object); 159 HCheckTableEntry* entry = copy->Find(object);
(...skipping 35 matching lines...) Expand 10 before | Expand all | Expand 10 after
178 learned ? "learned" : "copied", 195 learned ? "learned" : "copied",
179 from_block->block_id()); 196 from_block->block_id());
180 copy->Print(); 197 copy->Print();
181 } 198 }
182 199
183 return copy; 200 return copy;
184 } 201 }
185 202
186 // Global analysis: Merge this state with the other incoming state. 203 // Global analysis: Merge this state with the other incoming state.
187 HCheckTable* Merge(HBasicBlock* succ, HCheckTable* that, 204 HCheckTable* Merge(HBasicBlock* succ, HCheckTable* that,
188 HBasicBlock* that_block, Zone* zone) { 205 HBasicBlock* pred_block, Zone* zone) {
189 if (that_block->IsReachable()) { 206 if (pred_block->IsReachable()) {
190 if (that->size_ == 0) { 207 if (that->size_ == 0) {
191 // If the other state is empty, simply reset. 208 // If the other state is empty, simply reset.
192 size_ = 0; 209 size_ = 0;
193 cursor_ = 0; 210 cursor_ = 0;
194 } else { 211 } else {
212 int pred_index = succ->PredecessorIndexOf(pred_block);
195 bool compact = false; 213 bool compact = false;
196 for (int i = 0; i < size_; i++) { 214 for (int i = 0; i < size_; i++) {
197 HCheckTableEntry* this_entry = &entries_[i]; 215 HCheckTableEntry* this_entry = &entries_[i];
198 HCheckTableEntry* that_entry = that->Find(this_entry->object_); 216 HCheckTableEntry* that_entry;
217 if (this_entry->object_->IsPhi() &&
218 this_entry->object_->block() == succ) {
219 HPhi* phi = HPhi::cast(this_entry->object_);
220 HValue* phi_operand = phi->OperandAt(pred_index);
221 that_entry = that->Find(phi_operand);
222
223 } else {
224 that_entry = that->Find(this_entry->object_);
225 }
226
199 if (that_entry == NULL) { 227 if (that_entry == NULL) {
200 this_entry->object_ = NULL; 228 this_entry->object_ = NULL;
201 compact = true; 229 compact = true;
202 } else { 230 } else {
203 this_entry->maps_ = 231 this_entry->maps_ =
204 this_entry->maps_->Union(that_entry->maps_, phase_->zone()); 232 this_entry->maps_->Union(that_entry->maps_, phase_->zone());
205 if (this_entry->check_ != that_entry->check_) { 233 if (this_entry->check_ != that_entry->check_) {
206 this_entry->check_ = NULL; 234 this_entry->check_ = NULL;
207 } 235 }
208 ASSERT(this_entry->maps_->size() > 0); 236 ASSERT(this_entry->maps_->size() > 0);
209 } 237 }
210 } 238 }
211 if (compact) Compact(); 239 if (compact) Compact();
212 } 240 }
213 } 241 }
214 if (FLAG_trace_check_elimination) { 242 if (FLAG_trace_check_elimination) {
215 PrintF("B%d checkmaps-table merged with B%d table:\n", 243 PrintF("B%d checkmaps-table merged with B%d table:\n",
216 succ->block_id(), that_block->block_id()); 244 succ->block_id(), pred_block->block_id());
217 Print(); 245 Print();
218 } 246 }
219 return this; 247 return this;
220 } 248 }
221 249
222 void ReduceCheckMaps(HCheckMaps* instr) { 250 void ReduceCheckMaps(HCheckMaps* instr) {
223 HValue* object = instr->value()->ActualValue(); 251 HValue* object = instr->value()->ActualValue();
224 HCheckTableEntry* entry = Find(object); 252 HCheckTableEntry* entry = Find(object);
225 if (entry != NULL) { 253 if (entry != NULL) {
226 // entry found; 254 // entry found;
(...skipping 10 matching lines...) Expand all
237 TRACE(("Marking redundant CheckMaps #%d at B%d as dead\n", 265 TRACE(("Marking redundant CheckMaps #%d at B%d as dead\n",
238 instr->id(), instr->block()->block_id())); 266 instr->id(), instr->block()->block_id()));
239 // Mark check as dead but leave it in the graph as a checkpoint for 267 // Mark check as dead but leave it in the graph as a checkpoint for
240 // subsequent checks. 268 // subsequent checks.
241 instr->SetFlag(HValue::kIsDead); 269 instr->SetFlag(HValue::kIsDead);
242 entry->check_ = instr; 270 entry->check_ = instr;
243 INC_STAT(removed_); 271 INC_STAT(removed_);
244 } 272 }
245 return; 273 return;
246 } 274 }
247 i = i->Intersect(a, phase_->zone()); 275 MapSet intersection = i->Intersect(a, phase_->zone());
248 if (i->size() == 0) { 276 if (intersection->size() == 0) {
249 // Intersection is empty; probably megamorphic, which is likely to 277 // Intersection is empty; probably megamorphic, which is likely to
250 // deopt anyway, so just leave things as they are. 278 // deopt anyway, so just leave things as they are.
251 INC_STAT(empty_); 279 INC_STAT(empty_);
252 } else { 280 } else {
253 // TODO(titzer): replace the first check with a more strict check 281 // Update set of maps in the entry.
254 INC_STAT(narrowed_); 282 entry->maps_ = intersection;
283 if (intersection->size() != i->size()) {
284 // Narrow set of maps in the second check maps instruction.
285 HGraph* graph = instr->block()->graph();
286 HCheckMaps* new_check_maps =
287 HCheckMaps::New(graph->zone(), NULL, instr->value(),
288 intersection, instr->typecheck());
289 if (entry->check_ != NULL &&
290 entry->check_->block() == instr->block()) {
291 // There is a check in the same block so replace it with a more
292 // strict check and eliminate the second check entirely.
293 new_check_maps->InsertBefore(entry->check_);
294 entry->check_->DeleteAndReplaceWith(new_check_maps);
295 TRACE(("Check #%d narrowed to #%d\n",
296 entry->check_->id(), new_check_maps->id()));
297
298 } else {
299 new_check_maps->InsertBefore(instr);
300 }
301 TRACE(("CheckMaps #%d for #%d narrowed to #%d:\n",
302 instr->id(), instr->value()->id(), new_check_maps->id()));
303 instr->DeleteAndReplaceWith(new_check_maps);
304 entry->check_ = new_check_maps;
305
306 if (FLAG_trace_check_elimination) {
307 Print();
308 }
309 INC_STAT(narrowed_);
310 }
255 } 311 }
256 } else { 312 } else {
257 // No entry; insert a new one. 313 // No entry; insert a new one.
258 Insert(object, instr, instr->map_set().Copy(phase_->zone())); 314 Insert(object, instr, instr->map_set().Copy(phase_->zone()));
259 } 315 }
260 } 316 }
261 317
262 void ReduceCheckValue(HCheckValue* instr) { 318 void ReduceCheckValue(HCheckValue* instr) {
263 // Canonicalize HCheckValues; they might have their values load-eliminated. 319 // Canonicalize HCheckValues; they might have their values load-eliminated.
264 HValue* value = instr->Canonicalize(); 320 HValue* value = instr->Canonicalize();
(...skipping 150 matching lines...) Expand 10 before | Expand all | Expand 10 after
415 OS::MemMove(&entries_[R], &tmp_entries[0], L * sizeof(HCheckTableEntry)); 471 OS::MemMove(&entries_[R], &tmp_entries[0], L * sizeof(HCheckTableEntry));
416 } 472 }
417 473
418 cursor_ = size_; // Move cursor to end. 474 cursor_ = size_; // Move cursor to end.
419 } 475 }
420 476
421 void Print() { 477 void Print() {
422 for (int i = 0; i < size_; i++) { 478 for (int i = 0; i < size_; i++) {
423 HCheckTableEntry* entry = &entries_[i]; 479 HCheckTableEntry* entry = &entries_[i];
424 ASSERT(entry->object_ != NULL); 480 ASSERT(entry->object_ != NULL);
425 PrintF(" checkmaps-table @%d: object #%d ", i, entry->object_->id()); 481 PrintF(" checkmaps-table @%d: %s #%d ", i,
482 entry->object_->IsPhi() ? "phi" : "object",
483 entry->object_->id());
426 if (entry->check_ != NULL) { 484 if (entry->check_ != NULL) {
427 PrintF("check #%d ", entry->check_->id()); 485 PrintF("check #%d ", entry->check_->id());
428 } 486 }
429 MapSet list = entry->maps_; 487 MapSet list = entry->maps_;
430 PrintF("%d maps { ", list->size()); 488 PrintF("%d maps { ", list->size());
431 for (int j = 0; j < list->size(); j++) { 489 for (int j = 0; j < list->size(); j++) {
432 if (j > 0) PrintF(", "); 490 if (j > 0) PrintF(", ");
433 PrintF("%" V8PRIxPTR, list->at(j).Hashcode()); 491 PrintF("%" V8PRIxPTR, list->at(j).Hashcode());
434 } 492 }
435 PrintF(" }\n"); 493 PrintF(" }\n");
(...skipping 144 matching lines...) Expand 10 before | Expand all | Expand 10 after
580 PRINT_STAT(removed_cho); 638 PRINT_STAT(removed_cho);
581 PRINT_STAT(narrowed); 639 PRINT_STAT(narrowed);
582 PRINT_STAT(loads); 640 PRINT_STAT(loads);
583 PRINT_STAT(empty); 641 PRINT_STAT(empty);
584 PRINT_STAT(compares_true); 642 PRINT_STAT(compares_true);
585 PRINT_STAT(compares_false); 643 PRINT_STAT(compares_false);
586 PRINT_STAT(transitions); 644 PRINT_STAT(transitions);
587 } 645 }
588 646
589 } } // namespace v8::internal 647 } } // namespace v8::internal
OLDNEW
« no previous file with comments | « src/hydrogen.cc ('k') | src/hydrogen-instructions.h » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698