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 |
11 // with the distribution. | 11 // with the distribution. |
12 // * Neither the name of Google Inc. nor the names of its | 12 // * Neither the name of Google Inc. nor the names of its |
13 // contributors may be used to endorse or promote products derived | 13 // contributors may be used to endorse or promote products derived |
14 // from this software without specific prior written permission. | 14 // from this software without specific prior written permission. |
15 // | 15 // |
16 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS | 16 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS |
17 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT | 17 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT |
18 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR | 18 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR |
19 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT | 19 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT |
20 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, | 20 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, |
21 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT | 21 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT |
22 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, | 22 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, |
23 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY | 23 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY |
24 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT | 24 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |
25 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE | 25 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE |
26 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. | 26 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
27 | 27 |
28 #include "hydrogen-check-elimination.h" | 28 #include "hydrogen-check-elimination.h" |
29 #include "hydrogen-alias-analysis.h" | 29 #include "hydrogen-alias-analysis.h" |
| 30 #include "hydrogen-flow-engine.h" |
| 31 |
| 32 #define GLOBAL 1 |
| 33 |
| 34 // Only collect stats in debug mode. |
| 35 #if DEBUG |
| 36 #define INC_STAT(x) phase_->x++ |
| 37 #else |
| 38 #define INC_STAT(x) |
| 39 #endif |
| 40 |
| 41 // For code de-uglification. |
| 42 #define TRACE(x) if (FLAG_trace_check_elimination) PrintF x |
30 | 43 |
31 namespace v8 { | 44 namespace v8 { |
32 namespace internal { | 45 namespace internal { |
33 | 46 |
34 static const int kMaxTrackedObjects = 10; | |
35 typedef UniqueSet<Map>* MapSet; | 47 typedef UniqueSet<Map>* MapSet; |
36 | 48 |
| 49 struct HCheckTableEntry { |
| 50 HValue* object_; // The object being approximated. NULL => invalid entry. |
| 51 HValue* check_; // The last check instruction. |
| 52 MapSet maps_; // The set of known maps for the object. |
| 53 }; |
| 54 |
| 55 |
37 // The main datastructure used during check elimination, which stores a | 56 // The main datastructure used during check elimination, which stores a |
38 // set of known maps for each object. | 57 // set of known maps for each object. |
39 class HCheckTable { | 58 class HCheckTable : public ZoneObject { |
40 public: | 59 public: |
41 explicit HCheckTable(Zone* zone) : zone_(zone) { | 60 static const int kMaxTrackedObjects = 10; |
42 Kill(); | 61 |
43 redundant_ = 0; | 62 explicit HCheckTable(HCheckEliminationPhase* phase) |
44 narrowed_ = 0; | 63 : phase_(phase), |
45 empty_ = 0; | 64 cursor_(0), |
46 removed_ = 0; | 65 size_(0) { |
47 compares_true_ = 0; | 66 } |
48 compares_false_ = 0; | 67 |
49 transitions_ = 0; | 68 // The main processing of instructions. |
50 loads_ = 0; | 69 HCheckTable* Process(HInstruction* instr, Zone* zone) { |
| 70 switch (instr->opcode()) { |
| 71 case HValue::kCheckMaps: { |
| 72 ReduceCheckMaps(HCheckMaps::cast(instr)); |
| 73 break; |
| 74 } |
| 75 case HValue::kCheckValue: { |
| 76 ReduceCheckValue(HCheckValue::cast(instr)); |
| 77 break; |
| 78 } |
| 79 case HValue::kLoadNamedField: { |
| 80 ReduceLoadNamedField(HLoadNamedField::cast(instr)); |
| 81 break; |
| 82 } |
| 83 case HValue::kStoreNamedField: { |
| 84 ReduceStoreNamedField(HStoreNamedField::cast(instr)); |
| 85 break; |
| 86 } |
| 87 case HValue::kCompareMap: { |
| 88 ReduceCompareMap(HCompareMap::cast(instr)); |
| 89 break; |
| 90 } |
| 91 case HValue::kTransitionElementsKind: { |
| 92 ReduceTransitionElementsKind( |
| 93 HTransitionElementsKind::cast(instr)); |
| 94 break; |
| 95 } |
| 96 case HValue::kCheckMapValue: { |
| 97 ReduceCheckMapValue(HCheckMapValue::cast(instr)); |
| 98 break; |
| 99 } |
| 100 default: { |
| 101 // If the instruction changes maps uncontrollably, drop everything. |
| 102 if (instr->CheckGVNFlag(kChangesMaps) || |
| 103 instr->CheckGVNFlag(kChangesOsrEntries)) { |
| 104 Kill(); |
| 105 } |
| 106 } |
| 107 // Improvements possible: |
| 108 // - eliminate HCheckSmi and HCheckHeapObject |
| 109 } |
| 110 |
| 111 return this; |
| 112 } |
| 113 |
| 114 // Global analysis: Copy state to successor block. |
| 115 HCheckTable* Copy(HBasicBlock* succ, Zone* zone) { |
| 116 HCheckTable* copy = new(phase_->zone()) HCheckTable(phase_); |
| 117 for (int i = 0; i < size_; i++) { |
| 118 HCheckTableEntry* old_entry = &entries_[i]; |
| 119 HCheckTableEntry* new_entry = ©->entries_[i]; |
| 120 // TODO(titzer): keep the check if this block dominates the successor? |
| 121 new_entry->object_ = old_entry->object_; |
| 122 new_entry->check_ = NULL; |
| 123 new_entry->maps_ = old_entry->maps_->Copy(phase_->zone()); |
| 124 } |
| 125 return copy; |
| 126 } |
| 127 |
| 128 // Global analysis: Merge this state with the other incoming state. |
| 129 HCheckTable* Merge(HBasicBlock* succ, HCheckTable* that, Zone* zone) { |
| 130 if (that->size_ == 0) { |
| 131 // If the other state is empty, simply reset. |
| 132 size_ = 0; |
| 133 cursor_ = 0; |
| 134 return this; |
| 135 } |
| 136 bool compact = false; |
| 137 for (int i = 0; i < size_; i++) { |
| 138 HCheckTableEntry* this_entry = &entries_[i]; |
| 139 HCheckTableEntry* that_entry = that->Find(this_entry->object_); |
| 140 if (that_entry == NULL) { |
| 141 this_entry->object_ = NULL; |
| 142 compact = true; |
| 143 } else { |
| 144 this_entry->maps_ = this_entry->maps_->Union( |
| 145 that_entry->maps_, phase_->zone()); |
| 146 if (this_entry->check_ != that_entry->check_) this_entry->check_ = NULL; |
| 147 ASSERT(this_entry->maps_->size() > 0); |
| 148 } |
| 149 } |
| 150 if (compact) Compact(); |
| 151 return this; |
51 } | 152 } |
52 | 153 |
53 void ReduceCheckMaps(HCheckMaps* instr) { | 154 void ReduceCheckMaps(HCheckMaps* instr) { |
54 HValue* object = instr->value()->ActualValue(); | 155 HValue* object = instr->value()->ActualValue(); |
55 int index = Find(object); | 156 HCheckTableEntry* entry = Find(object); |
56 if (index >= 0) { | 157 if (entry != NULL) { |
57 // entry found; | 158 // entry found; |
58 MapSet a = known_maps_[index]; | 159 MapSet a = entry->maps_; |
59 MapSet i = instr->map_set().Copy(zone_); | 160 MapSet i = instr->map_set().Copy(phase_->zone()); |
60 if (a->IsSubset(i)) { | 161 if (a->IsSubset(i)) { |
61 // The first check is more strict; the second is redundant. | 162 // The first check is more strict; the second is redundant. |
62 if (checks_[index] != NULL) { | 163 if (entry->check_ != NULL) { |
63 instr->DeleteAndReplaceWith(checks_[index]); | 164 instr->DeleteAndReplaceWith(entry->check_); |
64 redundant_++; | 165 INC_STAT(redundant_); |
65 } else { | 166 } else { |
66 instr->DeleteAndReplaceWith(instr->value()); | 167 instr->DeleteAndReplaceWith(instr->value()); |
67 removed_++; | 168 INC_STAT(removed_); |
68 } | 169 } |
69 return; | 170 return; |
70 } | 171 } |
71 i = i->Intersect(a, zone_); | 172 i = i->Intersect(a, phase_->zone()); |
72 if (i->size() == 0) { | 173 if (i->size() == 0) { |
73 // Intersection is empty; probably megamorphic, which is likely to | 174 // Intersection is empty; probably megamorphic, which is likely to |
74 // deopt anyway, so just leave things as they are. | 175 // deopt anyway, so just leave things as they are. |
75 empty_++; | 176 INC_STAT(empty_); |
76 } else { | 177 } else { |
77 // TODO(titzer): replace the first check with a more strict check. | 178 // TODO(titzer): replace the first check with a more strict check |
78 narrowed_++; | 179 INC_STAT(narrowed_); |
79 } | 180 } |
80 } else { | 181 } else { |
81 // No entry; insert a new one. | 182 // No entry; insert a new one. |
82 Insert(object, instr, instr->map_set().Copy(zone_)); | 183 Insert(object, instr, instr->map_set().Copy(phase_->zone())); |
83 } | 184 } |
84 } | 185 } |
85 | 186 |
86 void ReduceCheckValue(HCheckValue* instr) { | 187 void ReduceCheckValue(HCheckValue* instr) { |
87 // Canonicalize HCheckValues; they might have their values load-eliminated. | 188 // Canonicalize HCheckValues; they might have their values load-eliminated. |
88 HValue* value = instr->Canonicalize(); | 189 HValue* value = instr->Canonicalize(); |
89 if (value == NULL) { | 190 if (value == NULL) { |
90 instr->DeleteAndReplaceWith(instr->value()); | 191 instr->DeleteAndReplaceWith(instr->value()); |
91 removed_++; | 192 INC_STAT(removed_); |
92 } else if (value != instr) { | 193 } else if (value != instr) { |
93 instr->DeleteAndReplaceWith(value); | 194 instr->DeleteAndReplaceWith(value); |
94 redundant_++; | 195 INC_STAT(redundant_); |
95 } | 196 } |
96 } | 197 } |
97 | 198 |
98 void ReduceLoadNamedField(HLoadNamedField* instr) { | 199 void ReduceLoadNamedField(HLoadNamedField* instr) { |
99 // Reduce a load of the map field when it is known to be a constant. | 200 // Reduce a load of the map field when it is known to be a constant. |
100 if (!IsMapAccess(instr->access())) return; | 201 if (!IsMapAccess(instr->access())) return; |
101 | 202 |
102 HValue* object = instr->object()->ActualValue(); | 203 HValue* object = instr->object()->ActualValue(); |
103 MapSet maps = FindMaps(object); | 204 MapSet maps = FindMaps(object); |
104 if (maps == NULL || maps->size() != 1) return; // Not a constant. | 205 if (maps == NULL || maps->size() != 1) return; // Not a constant. |
105 | 206 |
106 Unique<Map> map = maps->at(0); | 207 Unique<Map> map = maps->at(0); |
107 HConstant* constant = HConstant::CreateAndInsertBefore( | 208 HConstant* constant = HConstant::CreateAndInsertBefore( |
108 instr->block()->graph()->zone(), map, true, instr); | 209 instr->block()->graph()->zone(), map, true, instr); |
109 instr->DeleteAndReplaceWith(constant); | 210 instr->DeleteAndReplaceWith(constant); |
110 loads_++; | 211 INC_STAT(loads_); |
111 } | 212 } |
112 | 213 |
113 void ReduceCheckMapValue(HCheckMapValue* instr) { | 214 void ReduceCheckMapValue(HCheckMapValue* instr) { |
114 if (!instr->map()->IsConstant()) return; // Nothing to learn. | 215 if (!instr->map()->IsConstant()) return; // Nothing to learn. |
115 | 216 |
116 HValue* object = instr->value()->ActualValue(); | 217 HValue* object = instr->value()->ActualValue(); |
117 // Match a HCheckMapValue(object, HConstant(map)) | 218 // Match a HCheckMapValue(object, HConstant(map)) |
118 Unique<Map> map = MapConstant(instr->map()); | 219 Unique<Map> map = MapConstant(instr->map()); |
119 MapSet maps = FindMaps(object); | 220 MapSet maps = FindMaps(object); |
120 if (maps != NULL) { | 221 if (maps != NULL) { |
121 if (maps->Contains(map)) { | 222 if (maps->Contains(map)) { |
122 if (maps->size() == 1) { | 223 if (maps->size() == 1) { |
123 // Object is known to have exactly this map. | 224 // Object is known to have exactly this map. |
124 instr->DeleteAndReplaceWith(NULL); | 225 instr->DeleteAndReplaceWith(NULL); |
125 removed_++; | 226 INC_STAT(removed_); |
126 } else { | 227 } else { |
127 // Only one map survives the check. | 228 // Only one map survives the check. |
128 maps->Clear(); | 229 maps->Clear(); |
129 maps->Add(map, zone_); | 230 maps->Add(map, phase_->zone()); |
130 } | 231 } |
131 } | 232 } |
132 } else { | 233 } else { |
133 // No prior information. | 234 // No prior information. |
134 Insert(object, map); | 235 Insert(object, map); |
135 } | 236 } |
136 } | 237 } |
137 | 238 |
138 void ReduceStoreNamedField(HStoreNamedField* instr) { | 239 void ReduceStoreNamedField(HStoreNamedField* instr) { |
139 HValue* object = instr->object()->ActualValue(); | 240 HValue* object = instr->object()->ActualValue(); |
140 if (instr->has_transition()) { | 241 if (instr->has_transition()) { |
141 // This store transitions the object to a new map. | 242 // This store transitions the object to a new map. |
142 Kill(object); | 243 Kill(object); |
143 Insert(object, MapConstant(instr->transition())); | 244 Insert(object, MapConstant(instr->transition())); |
144 } else if (IsMapAccess(instr->access())) { | 245 } else if (IsMapAccess(instr->access())) { |
145 // This is a store directly to the map field of the object. | 246 // This is a store directly to the map field of the object. |
146 Kill(object); | 247 Kill(object); |
147 if (!instr->value()->IsConstant()) return; | 248 if (!instr->value()->IsConstant()) return; |
148 Insert(object, MapConstant(instr->value())); | 249 Insert(object, MapConstant(instr->value())); |
149 } else if (instr->CheckGVNFlag(kChangesMaps)) { | 250 } else { |
150 // This store indirectly changes the map of the object. | 251 // If the instruction changes maps, it should be handled above. |
151 Kill(instr->object()); | 252 CHECK(!instr->CheckGVNFlag(kChangesMaps)); |
152 UNREACHABLE(); | |
153 } | 253 } |
154 } | 254 } |
155 | 255 |
156 void ReduceCompareMap(HCompareMap* instr) { | 256 void ReduceCompareMap(HCompareMap* instr) { |
157 MapSet maps = FindMaps(instr->value()->ActualValue()); | 257 MapSet maps = FindMaps(instr->value()->ActualValue()); |
158 if (maps == NULL) return; | 258 if (maps == NULL) return; |
159 if (maps->Contains(instr->map())) { | 259 if (maps->Contains(instr->map())) { |
160 // TODO(titzer): replace with goto true branch | 260 if (maps->size() == 1) { |
161 if (maps->size() == 1) compares_true_++; | 261 // TODO(titzer): replace with goto true branch |
| 262 INC_STAT(compares_true_); |
| 263 } |
162 } else { | 264 } else { |
163 // TODO(titzer): replace with goto false branch | 265 // TODO(titzer): replace with goto false branch |
164 compares_false_++; | 266 INC_STAT(compares_false_); |
165 } | 267 } |
166 } | 268 } |
167 | 269 |
168 void ReduceTransitionElementsKind(HTransitionElementsKind* instr) { | 270 void ReduceTransitionElementsKind(HTransitionElementsKind* instr) { |
169 MapSet maps = FindMaps(instr->object()->ActualValue()); | 271 MapSet maps = FindMaps(instr->object()->ActualValue()); |
170 // Can only learn more about an object that already has a known set of maps. | 272 // Can only learn more about an object that already has a known set of maps. |
171 if (maps == NULL) return; | 273 if (maps == NULL) return; |
172 if (maps->Contains(instr->original_map())) { | 274 if (maps->Contains(instr->original_map())) { |
173 // If the object has the original map, it will be transitioned. | 275 // If the object has the original map, it will be transitioned. |
174 maps->Remove(instr->original_map()); | 276 maps->Remove(instr->original_map()); |
175 maps->Add(instr->transitioned_map(), zone_); | 277 maps->Add(instr->transitioned_map(), phase_->zone()); |
176 } else { | 278 } else { |
177 // Object does not have the given map, thus the transition is redundant. | 279 // Object does not have the given map, thus the transition is redundant. |
178 instr->DeleteAndReplaceWith(instr->object()); | 280 instr->DeleteAndReplaceWith(instr->object()); |
179 transitions_++; | 281 INC_STAT(transitions_); |
180 } | 282 } |
181 } | 283 } |
182 | 284 |
183 // Kill everything in the table. | 285 // Kill everything in the table. |
184 void Kill() { | 286 void Kill() { |
185 memset(objects_, 0, sizeof(objects_)); | 287 size_ = 0; |
| 288 cursor_ = 0; |
186 } | 289 } |
187 | 290 |
188 // Kill everything in the table that may alias {object}. | 291 // Kill everything in the table that may alias {object}. |
189 void Kill(HValue* object) { | 292 void Kill(HValue* object) { |
190 for (int i = 0; i < kMaxTrackedObjects; i++) { | 293 bool compact = false; |
191 if (objects_[i] == NULL) continue; | 294 for (int i = 0; i < size_; i++) { |
192 if (aliasing_.MayAlias(objects_[i], object)) objects_[i] = NULL; | 295 HCheckTableEntry* entry = &entries_[i]; |
| 296 ASSERT(entry->object_ != NULL); |
| 297 if (phase_->aliasing_->MayAlias(entry->object_, object)) { |
| 298 entry->object_ = NULL; |
| 299 compact = true; |
| 300 } |
193 } | 301 } |
194 ASSERT(Find(object) < 0); | 302 if (compact) Compact(); |
| 303 ASSERT(Find(object) == NULL); |
| 304 } |
| 305 |
| 306 void Compact() { |
| 307 // First, compact the array in place. |
| 308 int max = size_, dest = 0, old_cursor = cursor_; |
| 309 for (int i = 0; i < max; i++) { |
| 310 if (entries_[i].object_ != NULL) { |
| 311 if (dest != i) entries_[dest] = entries_[i]; |
| 312 dest++; |
| 313 } else { |
| 314 if (i < old_cursor) cursor_--; |
| 315 size_--; |
| 316 } |
| 317 } |
| 318 ASSERT(size_ == dest); |
| 319 ASSERT(cursor_ <= size_); |
| 320 |
| 321 // Preserve the age of the entries by moving the older entries to the end. |
| 322 if (cursor_ == size_) return; // Cursor already points at end. |
| 323 if (cursor_ != 0) { |
| 324 // | L = oldest | R = newest | | |
| 325 // ^ cursor ^ size ^ MAX |
| 326 HCheckTableEntry tmp_entries[kMaxTrackedObjects]; |
| 327 int L = cursor_; |
| 328 int R = size_ - cursor_; |
| 329 |
| 330 OS::MemMove(&tmp_entries[0], &entries_[0], L * sizeof(HCheckTableEntry)); |
| 331 OS::MemMove(&entries_[0], &entries_[L], R * sizeof(HCheckTableEntry)); |
| 332 OS::MemMove(&entries_[R], &tmp_entries[0], L * sizeof(HCheckTableEntry)); |
| 333 } |
| 334 |
| 335 cursor_ = size_; // Move cursor to end. |
195 } | 336 } |
196 | 337 |
197 void Print() { | 338 void Print() { |
198 for (int i = 0; i < kMaxTrackedObjects; i++) { | 339 for (int i = 0; i < size_; i++) { |
199 if (objects_[i] == NULL) continue; | 340 HCheckTableEntry* entry = &entries_[i]; |
200 PrintF(" checkmaps-table @%d: object #%d ", i, objects_[i]->id()); | 341 ASSERT(entry->object_ != NULL); |
201 if (checks_[i] != NULL) { | 342 PrintF(" checkmaps-table @%d: object #%d ", i, entry->object_->id()); |
202 PrintF("check #%d ", checks_[i]->id()); | 343 if (entry->check_ != NULL) { |
| 344 PrintF("check #%d ", entry->check_->id()); |
203 } | 345 } |
204 MapSet list = known_maps_[i]; | 346 MapSet list = entry->maps_; |
205 PrintF("%d maps { ", list->size()); | 347 PrintF("%d maps { ", list->size()); |
206 for (int j = 0; j < list->size(); j++) { | 348 for (int j = 0; j < list->size(); j++) { |
207 if (j > 0) PrintF(", "); | 349 if (j > 0) PrintF(", "); |
208 PrintF("%" V8PRIxPTR, list->at(j).Hashcode()); | 350 PrintF("%" V8PRIxPTR, list->at(j).Hashcode()); |
209 } | 351 } |
210 PrintF(" }\n"); | 352 PrintF(" }\n"); |
211 } | 353 } |
212 } | 354 } |
213 | 355 |
214 void PrintStats() { | |
215 if (redundant_ > 0) PrintF(" redundant = %2d\n", redundant_); | |
216 if (removed_ > 0) PrintF(" removed = %2d\n", removed_); | |
217 if (narrowed_ > 0) PrintF(" narrowed = %2d\n", narrowed_); | |
218 if (loads_ > 0) PrintF(" loads = %2d\n", loads_); | |
219 if (empty_ > 0) PrintF(" empty = %2d\n", empty_); | |
220 if (compares_true_ > 0) PrintF(" cmp_true = %2d\n", compares_true_); | |
221 if (compares_false_ > 0) PrintF(" cmp_false = %2d\n", compares_false_); | |
222 if (transitions_ > 0) PrintF(" transitions = %2d\n", transitions_); | |
223 } | |
224 | |
225 private: | 356 private: |
226 int Find(HValue* object) { | 357 HCheckTableEntry* Find(HValue* object) { |
227 for (int i = 0; i < kMaxTrackedObjects; i++) { | 358 for (int i = size_ - 1; i >= 0; i--) { |
228 if (objects_[i] == NULL) continue; | 359 // Search from most-recently-inserted to least-recently-inserted. |
229 if (aliasing_.MustAlias(objects_[i], object)) return i; | 360 HCheckTableEntry* entry = &entries_[i]; |
| 361 ASSERT(entry->object_ != NULL); |
| 362 if (phase_->aliasing_->MustAlias(entry->object_, object)) return entry; |
230 } | 363 } |
231 return -1; | 364 return NULL; |
232 } | 365 } |
233 | 366 |
234 MapSet FindMaps(HValue* object) { | 367 MapSet FindMaps(HValue* object) { |
235 int index = Find(object); | 368 HCheckTableEntry* entry = Find(object); |
236 return index < 0 ? NULL : known_maps_[index]; | 369 return entry == NULL ? NULL : entry->maps_; |
237 } | 370 } |
238 | 371 |
239 void Insert(HValue* object, Unique<Map> map) { | 372 void Insert(HValue* object, Unique<Map> map) { |
240 MapSet list = new(zone_) UniqueSet<Map>(); | 373 MapSet list = new(phase_->zone()) UniqueSet<Map>(); |
241 list->Add(map, zone_); | 374 list->Add(map, phase_->zone()); |
242 Insert(object, NULL, list); | 375 Insert(object, NULL, list); |
243 } | 376 } |
244 | 377 |
245 void Insert(HValue* object, HCheckMaps* check, MapSet maps) { | 378 void Insert(HValue* object, HCheckMaps* check, MapSet maps) { |
246 for (int i = 0; i < kMaxTrackedObjects; i++) { | 379 HCheckTableEntry* entry = &entries_[cursor_++]; |
247 // TODO(titzer): drop old entries instead of disallowing new ones. | 380 entry->object_ = object; |
248 if (objects_[i] == NULL) { | 381 entry->check_ = check; |
249 objects_[i] = object; | 382 entry->maps_ = maps; |
250 checks_[i] = check; | 383 // If the table becomes full, wrap around and overwrite older entries. |
251 known_maps_[i] = maps; | 384 if (cursor_ == kMaxTrackedObjects) cursor_ = 0; |
252 return; | 385 if (size_ < kMaxTrackedObjects) size_++; |
253 } | |
254 } | |
255 } | 386 } |
256 | 387 |
257 bool IsMapAccess(HObjectAccess access) { | 388 bool IsMapAccess(HObjectAccess access) { |
258 return access.IsInobject() && access.offset() == JSObject::kMapOffset; | 389 return access.IsInobject() && access.offset() == JSObject::kMapOffset; |
259 } | 390 } |
260 | 391 |
261 Unique<Map> MapConstant(HValue* value) { | 392 Unique<Map> MapConstant(HValue* value) { |
262 return Unique<Map>::cast(HConstant::cast(value)->GetUnique()); | 393 return Unique<Map>::cast(HConstant::cast(value)->GetUnique()); |
263 } | 394 } |
264 | 395 |
265 Zone* zone_; | 396 friend class HCheckMapsEffects; |
266 HValue* objects_[kMaxTrackedObjects]; | 397 |
267 HValue* checks_[kMaxTrackedObjects]; | 398 HCheckEliminationPhase* phase_; |
268 MapSet known_maps_[kMaxTrackedObjects]; | 399 HCheckTableEntry entries_[kMaxTrackedObjects]; |
269 HAliasAnalyzer aliasing_; | 400 int16_t cursor_; // Must be <= kMaxTrackedObjects |
270 int redundant_; | 401 int16_t size_; // Must be <= kMaxTrackedObjects |
271 int removed_; | 402 |
272 int narrowed_; | 403 STATIC_ASSERT((1L << (sizeof(cursor_) * 8)) > kMaxTrackedObjects); |
273 int loads_; | 404 STATIC_ASSERT((1L << (sizeof(size_) * 8)) > kMaxTrackedObjects); |
274 int empty_; | |
275 int compares_true_; | |
276 int compares_false_; | |
277 int transitions_; | |
278 }; | 405 }; |
279 | 406 |
280 | 407 |
| 408 // Collects instructions that can cause effects that invalidate information |
| 409 // needed for check elimination. |
| 410 class HCheckMapsEffects : public ZoneObject { |
| 411 public: |
| 412 explicit HCheckMapsEffects(Zone* zone) |
| 413 : maps_stored_(false), |
| 414 stores_(5, zone) { } |
| 415 |
| 416 inline bool Disabled() { |
| 417 return false; // Effects are _not_ disabled. |
| 418 } |
| 419 |
| 420 // Process a possibly side-effecting instruction. |
| 421 void Process(HInstruction* instr, Zone* zone) { |
| 422 switch (instr->opcode()) { |
| 423 case HValue::kStoreNamedField: { |
| 424 stores_.Add(HStoreNamedField::cast(instr), zone); |
| 425 break; |
| 426 } |
| 427 case HValue::kOsrEntry: { |
| 428 // Kill everything. Loads must not be hoisted past the OSR entry. |
| 429 maps_stored_ = true; |
| 430 } |
| 431 default: { |
| 432 maps_stored_ |= (instr->CheckGVNFlag(kChangesMaps) | |
| 433 instr->CheckGVNFlag(kChangesElementsKind)); |
| 434 } |
| 435 } |
| 436 } |
| 437 |
| 438 // Apply these effects to the given check elimination table. |
| 439 void Apply(HCheckTable* table) { |
| 440 if (maps_stored_) { |
| 441 // Uncontrollable map modifications; kill everything. |
| 442 table->Kill(); |
| 443 return; |
| 444 } |
| 445 |
| 446 // Kill maps for each store contained in these effects. |
| 447 for (int i = 0; i < stores_.length(); i++) { |
| 448 HStoreNamedField* s = stores_[i]; |
| 449 if (table->IsMapAccess(s->access()) || s->has_transition()) { |
| 450 table->Kill(s->object()->ActualValue()); |
| 451 } |
| 452 } |
| 453 } |
| 454 |
| 455 // Union these effects with the other effects. |
| 456 void Union(HCheckMapsEffects* that, Zone* zone) { |
| 457 maps_stored_ |= that->maps_stored_; |
| 458 for (int i = 0; i < that->stores_.length(); i++) { |
| 459 stores_.Add(that->stores_[i], zone); |
| 460 } |
| 461 } |
| 462 |
| 463 private: |
| 464 bool maps_stored_ : 1; |
| 465 ZoneList<HStoreNamedField*> stores_; |
| 466 }; |
| 467 |
| 468 |
| 469 // The main routine of the analysis phase. Use the HFlowEngine for either a |
| 470 // local or a global analysis. |
281 void HCheckEliminationPhase::Run() { | 471 void HCheckEliminationPhase::Run() { |
282 for (int i = 0; i < graph()->blocks()->length(); i++) { | 472 HFlowEngine<HCheckTable, HCheckMapsEffects> engine(graph(), zone()); |
283 EliminateLocalChecks(graph()->blocks()->at(i)); | 473 HCheckTable* table = new(zone()) HCheckTable(this); |
| 474 |
| 475 if (GLOBAL) { |
| 476 // Perform a global analysis. |
| 477 engine.AnalyzeDominatedBlocks(graph()->blocks()->at(0), table); |
| 478 } else { |
| 479 // Perform only local analysis. |
| 480 for (int i = 0; i < graph()->blocks()->length(); i++) { |
| 481 table->Kill(); |
| 482 engine.AnalyzeOneBlock(graph()->blocks()->at(i), table); |
| 483 } |
284 } | 484 } |
| 485 |
| 486 if (FLAG_trace_check_elimination) PrintStats(); |
285 } | 487 } |
286 | 488 |
287 | 489 |
288 // For code de-uglification. | 490 // Are we eliminated yet? |
289 #define TRACE(x) if (FLAG_trace_check_elimination) PrintF x | 491 void HCheckEliminationPhase::PrintStats() { |
290 | 492 #if DEBUG |
291 | 493 if (redundant_ > 0) PrintF(" redundant = %2d\n", redundant_); |
292 // Eliminate checks local to a block. | 494 if (removed_ > 0) PrintF(" removed = %2d\n", removed_); |
293 void HCheckEliminationPhase::EliminateLocalChecks(HBasicBlock* block) { | 495 if (narrowed_ > 0) PrintF(" narrowed = %2d\n", narrowed_); |
294 HCheckTable table(zone()); | 496 if (loads_ > 0) PrintF(" loads = %2d\n", loads_); |
295 TRACE(("-- check-elim B%d ------------------------------------------------\n", | 497 if (empty_ > 0) PrintF(" empty = %2d\n", empty_); |
296 block->block_id())); | 498 if (compares_true_ > 0) PrintF(" cmp_true = %2d\n", compares_true_); |
297 | 499 if (compares_false_ > 0) PrintF(" cmp_false = %2d\n", compares_false_); |
298 for (HInstructionIterator it(block); !it.Done(); it.Advance()) { | 500 if (transitions_ > 0) PrintF(" transitions = %2d\n", transitions_); |
299 bool changed = false; | 501 #endif |
300 HInstruction* instr = it.Current(); | |
301 | |
302 switch (instr->opcode()) { | |
303 case HValue::kCheckMaps: { | |
304 table.ReduceCheckMaps(HCheckMaps::cast(instr)); | |
305 changed = true; | |
306 break; | |
307 } | |
308 case HValue::kCheckValue: { | |
309 table.ReduceCheckValue(HCheckValue::cast(instr)); | |
310 changed = true; | |
311 break; | |
312 } | |
313 case HValue::kLoadNamedField: { | |
314 table.ReduceLoadNamedField(HLoadNamedField::cast(instr)); | |
315 changed = true; | |
316 break; | |
317 } | |
318 case HValue::kStoreNamedField: { | |
319 table.ReduceStoreNamedField(HStoreNamedField::cast(instr)); | |
320 changed = true; | |
321 break; | |
322 } | |
323 case HValue::kCompareMap: { | |
324 table.ReduceCompareMap(HCompareMap::cast(instr)); | |
325 changed = true; | |
326 break; | |
327 } | |
328 case HValue::kTransitionElementsKind: { | |
329 table.ReduceTransitionElementsKind( | |
330 HTransitionElementsKind::cast(instr)); | |
331 changed = true; | |
332 break; | |
333 } | |
334 case HValue::kCheckMapValue: { | |
335 table.ReduceCheckMapValue(HCheckMapValue::cast(instr)); | |
336 changed = true; | |
337 break; | |
338 } | |
339 default: { | |
340 // If the instruction changes maps uncontrollably, kill the whole town. | |
341 if (instr->CheckGVNFlag(kChangesMaps)) { | |
342 table.Kill(); | |
343 changed = true; | |
344 } | |
345 } | |
346 // Improvements possible: | |
347 // - eliminate HCheckSmi and HCheckHeapObject | |
348 } | |
349 | |
350 if (changed && FLAG_trace_check_elimination) table.Print(); | |
351 } | |
352 | |
353 if (FLAG_trace_check_elimination) table.PrintStats(); | |
354 } | 502 } |
355 | 503 |
356 | |
357 } } // namespace v8::internal | 504 } } // namespace v8::internal |
OLD | NEW |