OLD | NEW |
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 114 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
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 // Branch-sensitive analysis for certain comparisons may add more facts | 133 // Branch-sensitive analysis for certain comparisons may add more facts |
134 // to the state for the successor on the true branch. | 134 // to the state for the successor on the true branch. |
| 135 bool learned = false; |
135 HControlInstruction* end = succ->predecessors()->at(0)->end(); | 136 HControlInstruction* end = succ->predecessors()->at(0)->end(); |
136 if (succ->predecessors()->length() == 1 && end->SuccessorAt(0) == succ) { | 137 if (succ->predecessors()->length() == 1 && end->SuccessorAt(0) == succ) { |
137 if (end->IsCompareMap()) { | 138 if (end->IsCompareMap()) { |
138 // Learn on the true branch of if(CompareMap(x)). | 139 // Learn on the true branch of if(CompareMap(x)). |
139 HCompareMap* cmp = HCompareMap::cast(end); | 140 HCompareMap* cmp = HCompareMap::cast(end); |
140 HValue* object = cmp->value()->ActualValue(); | 141 HValue* object = cmp->value()->ActualValue(); |
141 HCheckTableEntry* entry = copy->Find(object); | 142 HCheckTableEntry* entry = copy->Find(object); |
142 if (entry == NULL) { | 143 if (entry == NULL) { |
143 copy->Insert(object, cmp->map()); | 144 copy->Insert(object, cmp->map()); |
144 } else { | 145 } else { |
145 MapSet list = new(phase_->zone()) UniqueSet<Map>(); | 146 MapSet list = new(phase_->zone()) UniqueSet<Map>(); |
146 list->Add(cmp->map(), phase_->zone()); | 147 list->Add(cmp->map(), phase_->zone()); |
147 entry->maps_ = list; | 148 entry->maps_ = list; |
148 } | 149 } |
| 150 learned = true; |
149 } else if (end->IsCompareObjectEqAndBranch()) { | 151 } else if (end->IsCompareObjectEqAndBranch()) { |
150 // Learn on the true branch of if(CmpObjectEq(x, y)). | 152 // Learn on the true branch of if(CmpObjectEq(x, y)). |
151 HCompareObjectEqAndBranch* cmp = | 153 HCompareObjectEqAndBranch* cmp = |
152 HCompareObjectEqAndBranch::cast(end); | 154 HCompareObjectEqAndBranch::cast(end); |
153 HValue* left = cmp->left()->ActualValue(); | 155 HValue* left = cmp->left()->ActualValue(); |
154 HValue* right = cmp->right()->ActualValue(); | 156 HValue* right = cmp->right()->ActualValue(); |
155 HCheckTableEntry* le = copy->Find(left); | 157 HCheckTableEntry* le = copy->Find(left); |
156 HCheckTableEntry* re = copy->Find(right); | 158 HCheckTableEntry* re = copy->Find(right); |
157 if (le == NULL) { | 159 if (le == NULL) { |
158 if (re != NULL) { | 160 if (re != NULL) { |
159 copy->Insert(left, NULL, re->maps_->Copy(zone)); | 161 copy->Insert(left, NULL, re->maps_->Copy(zone)); |
160 } | 162 } |
161 } else if (re == NULL) { | 163 } else if (re == NULL) { |
162 copy->Insert(right, NULL, le->maps_->Copy(zone)); | 164 copy->Insert(right, NULL, le->maps_->Copy(zone)); |
163 } else { | 165 } else { |
164 MapSet intersect = le->maps_->Intersect(re->maps_, zone); | 166 MapSet intersect = le->maps_->Intersect(re->maps_, zone); |
165 le->maps_ = intersect; | 167 le->maps_ = intersect; |
166 re->maps_ = intersect->Copy(zone); | 168 re->maps_ = intersect->Copy(zone); |
167 } | 169 } |
| 170 learned = true; |
168 } | 171 } |
169 // Learning on false branches requires storing negative facts. | 172 // Learning on false branches requires storing negative facts. |
170 } | 173 } |
171 | 174 |
| 175 if (FLAG_trace_check_elimination) { |
| 176 PrintF("B%d checkmaps-table %s from B%d:\n", |
| 177 succ->block_id(), |
| 178 learned ? "learned" : "copied", |
| 179 from_block->block_id()); |
| 180 copy->Print(); |
| 181 } |
| 182 |
172 return copy; | 183 return copy; |
173 } | 184 } |
174 | 185 |
175 // Global analysis: Merge this state with the other incoming state. | 186 // Global analysis: Merge this state with the other incoming state. |
176 HCheckTable* Merge(HBasicBlock* succ, HCheckTable* that, | 187 HCheckTable* Merge(HBasicBlock* succ, HCheckTable* that, |
177 HBasicBlock* that_block, Zone* zone) { | 188 HBasicBlock* that_block, Zone* zone) { |
178 if (that->size_ == 0) { | 189 if (that_block->IsReachable()) { |
179 // If the other state is empty, simply reset. | 190 if (that->size_ == 0) { |
180 size_ = 0; | 191 // If the other state is empty, simply reset. |
181 cursor_ = 0; | 192 size_ = 0; |
182 return this; | 193 cursor_ = 0; |
183 } | |
184 bool compact = false; | |
185 for (int i = 0; i < size_; i++) { | |
186 HCheckTableEntry* this_entry = &entries_[i]; | |
187 HCheckTableEntry* that_entry = that->Find(this_entry->object_); | |
188 if (that_entry == NULL) { | |
189 this_entry->object_ = NULL; | |
190 compact = true; | |
191 } else { | 194 } else { |
192 this_entry->maps_ = this_entry->maps_->Union( | 195 bool compact = false; |
193 that_entry->maps_, phase_->zone()); | 196 for (int i = 0; i < size_; i++) { |
194 if (this_entry->check_ != that_entry->check_) this_entry->check_ = NULL; | 197 HCheckTableEntry* this_entry = &entries_[i]; |
195 ASSERT(this_entry->maps_->size() > 0); | 198 HCheckTableEntry* that_entry = that->Find(this_entry->object_); |
| 199 if (that_entry == NULL) { |
| 200 this_entry->object_ = NULL; |
| 201 compact = true; |
| 202 } else { |
| 203 this_entry->maps_ = |
| 204 this_entry->maps_->Union(that_entry->maps_, phase_->zone()); |
| 205 if (this_entry->check_ != that_entry->check_) { |
| 206 this_entry->check_ = NULL; |
| 207 } |
| 208 ASSERT(this_entry->maps_->size() > 0); |
| 209 } |
| 210 } |
| 211 if (compact) Compact(); |
196 } | 212 } |
197 } | 213 } |
198 if (compact) Compact(); | 214 if (FLAG_trace_check_elimination) { |
| 215 PrintF("B%d checkmaps-table merged with B%d table:\n", |
| 216 succ->block_id(), that_block->block_id()); |
| 217 Print(); |
| 218 } |
199 return this; | 219 return this; |
200 } | 220 } |
201 | 221 |
202 void ReduceCheckMaps(HCheckMaps* instr) { | 222 void ReduceCheckMaps(HCheckMaps* instr) { |
203 HValue* object = instr->value()->ActualValue(); | 223 HValue* object = instr->value()->ActualValue(); |
204 HCheckTableEntry* entry = Find(object); | 224 HCheckTableEntry* entry = Find(object); |
205 if (entry != NULL) { | 225 if (entry != NULL) { |
206 // entry found; | 226 // entry found; |
207 MapSet a = entry->maps_; | 227 MapSet a = entry->maps_; |
208 MapSet i = instr->map_set().Copy(phase_->zone()); | 228 MapSet i = instr->map_set().Copy(phase_->zone()); |
209 if (a->IsSubset(i)) { | 229 if (a->IsSubset(i)) { |
210 // The first check is more strict; the second is redundant. | 230 // The first check is more strict; the second is redundant. |
211 if (entry->check_ != NULL) { | 231 if (entry->check_ != NULL) { |
| 232 TRACE(("Replacing redundant CheckMaps #%d at B%d with #%d\n", |
| 233 instr->id(), instr->block()->block_id(), entry->check_->id())); |
212 instr->DeleteAndReplaceWith(entry->check_); | 234 instr->DeleteAndReplaceWith(entry->check_); |
213 INC_STAT(redundant_); | 235 INC_STAT(redundant_); |
214 } else { | 236 } else { |
215 instr->DeleteAndReplaceWith(instr->value()); | 237 TRACE(("Marking redundant CheckMaps #%d at B%d as dead\n", |
| 238 instr->id(), instr->block()->block_id())); |
| 239 // Mark check as dead but leave it in the graph as a checkpoint for |
| 240 // subsequent checks. |
| 241 instr->SetFlag(HValue::kIsDead); |
| 242 entry->check_ = instr; |
216 INC_STAT(removed_); | 243 INC_STAT(removed_); |
217 } | 244 } |
218 return; | 245 return; |
219 } | 246 } |
220 i = i->Intersect(a, phase_->zone()); | 247 i = i->Intersect(a, phase_->zone()); |
221 if (i->size() == 0) { | 248 if (i->size() == 0) { |
222 // Intersection is empty; probably megamorphic, which is likely to | 249 // Intersection is empty; probably megamorphic, which is likely to |
223 // deopt anyway, so just leave things as they are. | 250 // deopt anyway, so just leave things as they are. |
224 INC_STAT(empty_); | 251 INC_STAT(empty_); |
225 } else { | 252 } else { |
(...skipping 327 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
553 PRINT_STAT(removed_cho); | 580 PRINT_STAT(removed_cho); |
554 PRINT_STAT(narrowed); | 581 PRINT_STAT(narrowed); |
555 PRINT_STAT(loads); | 582 PRINT_STAT(loads); |
556 PRINT_STAT(empty); | 583 PRINT_STAT(empty); |
557 PRINT_STAT(compares_true); | 584 PRINT_STAT(compares_true); |
558 PRINT_STAT(compares_false); | 585 PRINT_STAT(compares_false); |
559 PRINT_STAT(transitions); | 586 PRINT_STAT(transitions); |
560 } | 587 } |
561 | 588 |
562 } } // namespace v8::internal | 589 } } // namespace v8::internal |
OLD | NEW |