machenbach@chromium.org | 528ce02 | 2013-09-23 14:09:36 +0000 | [diff] [blame] | 1 | // Copyright 2013 the V8 project authors. All rights reserved. |
| 2 | // Redistribution and use in source and binary forms, with or without |
| 3 | // modification, are permitted provided that the following conditions are |
| 4 | // met: |
| 5 | // |
| 6 | // * Redistributions of source code must retain the above copyright |
| 7 | // notice, this list of conditions and the following disclaimer. |
| 8 | // * Redistributions in binary form must reproduce the above |
| 9 | // copyright notice, this list of conditions and the following |
| 10 | // disclaimer in the documentation and/or other materials provided |
| 11 | // with the distribution. |
| 12 | // * Neither the name of Google Inc. nor the names of its |
| 13 | // contributors may be used to endorse or promote products derived |
| 14 | // from this software without specific prior written permission. |
| 15 | // |
| 16 | // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS |
| 17 | // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT |
| 18 | // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR |
| 19 | // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT |
| 20 | // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, |
| 21 | // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT |
| 22 | // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, |
| 23 | // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY |
| 24 | // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |
| 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. |
| 27 | |
| 28 | #include "hydrogen-alias-analysis.h" |
| 29 | #include "hydrogen-load-elimination.h" |
| 30 | #include "hydrogen-instructions.h" |
bmeurer@chromium.org | 0fdb2a6 | 2013-10-21 07:19:36 +0000 | [diff] [blame] | 31 | #include "hydrogen-flow-engine.h" |
machenbach@chromium.org | 528ce02 | 2013-09-23 14:09:36 +0000 | [diff] [blame] | 32 | |
| 33 | namespace v8 { |
| 34 | namespace internal { |
| 35 | |
bmeurer@chromium.org | 0fdb2a6 | 2013-10-21 07:19:36 +0000 | [diff] [blame] | 36 | #define GLOBAL true |
| 37 | #define TRACE(x) if (FLAG_trace_load_elimination) PrintF x |
| 38 | |
machenbach@chromium.org | 528ce02 | 2013-09-23 14:09:36 +0000 | [diff] [blame] | 39 | static const int kMaxTrackedFields = 16; |
| 40 | static const int kMaxTrackedObjects = 5; |
| 41 | |
| 42 | // An element in the field approximation list. |
| 43 | class HFieldApproximation : public ZoneObject { |
| 44 | public: // Just a data blob. |
| 45 | HValue* object_; |
machenbach@chromium.org | 528ce02 | 2013-09-23 14:09:36 +0000 | [diff] [blame] | 46 | HValue* last_value_; |
| 47 | HFieldApproximation* next_; |
bmeurer@chromium.org | 0fdb2a6 | 2013-10-21 07:19:36 +0000 | [diff] [blame] | 48 | |
| 49 | // Recursively copy the entire linked list of field approximations. |
| 50 | HFieldApproximation* Copy(Zone* zone) { |
| 51 | if (this == NULL) return NULL; |
| 52 | HFieldApproximation* copy = new(zone) HFieldApproximation(); |
| 53 | copy->object_ = this->object_; |
bmeurer@chromium.org | 0fdb2a6 | 2013-10-21 07:19:36 +0000 | [diff] [blame] | 54 | copy->last_value_ = this->last_value_; |
| 55 | copy->next_ = this->next_->Copy(zone); |
| 56 | return copy; |
| 57 | } |
machenbach@chromium.org | 528ce02 | 2013-09-23 14:09:36 +0000 | [diff] [blame] | 58 | }; |
| 59 | |
| 60 | |
| 61 | // The main datastructure used during load/store elimination. Each in-object |
| 62 | // field is tracked separately. For each field, store a list of known field |
| 63 | // values for known objects. |
bmeurer@chromium.org | 0fdb2a6 | 2013-10-21 07:19:36 +0000 | [diff] [blame] | 64 | class HLoadEliminationTable : public ZoneObject { |
machenbach@chromium.org | 528ce02 | 2013-09-23 14:09:36 +0000 | [diff] [blame] | 65 | public: |
| 66 | HLoadEliminationTable(Zone* zone, HAliasAnalyzer* aliasing) |
| 67 | : zone_(zone), fields_(kMaxTrackedFields, zone), aliasing_(aliasing) { } |
| 68 | |
bmeurer@chromium.org | 0fdb2a6 | 2013-10-21 07:19:36 +0000 | [diff] [blame] | 69 | // The main processing of instructions. |
| 70 | HLoadEliminationTable* Process(HInstruction* instr, Zone* zone) { |
| 71 | switch (instr->opcode()) { |
| 72 | case HValue::kLoadNamedField: { |
| 73 | HLoadNamedField* l = HLoadNamedField::cast(instr); |
| 74 | TRACE((" process L%d field %d (o%d)\n", |
| 75 | instr->id(), |
| 76 | FieldOf(l->access()), |
| 77 | l->object()->ActualValue()->id())); |
| 78 | HValue* result = load(l); |
hpayer@chromium.org | 0f6d2bb | 2014-02-25 12:34:22 +0000 | [diff] [blame^] | 79 | if (result != instr && |
| 80 | result->type().Equals(instr->type()) && |
| 81 | result->representation().Equals(instr->representation())) { |
bmeurer@chromium.org | 0fdb2a6 | 2013-10-21 07:19:36 +0000 | [diff] [blame] | 82 | // The load can be replaced with a previous load or a value. |
| 83 | TRACE((" replace L%d -> v%d\n", instr->id(), result->id())); |
| 84 | instr->DeleteAndReplaceWith(result); |
| 85 | } |
| 86 | break; |
| 87 | } |
| 88 | case HValue::kStoreNamedField: { |
| 89 | HStoreNamedField* s = HStoreNamedField::cast(instr); |
| 90 | TRACE((" process S%d field %d (o%d) = v%d\n", |
| 91 | instr->id(), |
| 92 | FieldOf(s->access()), |
| 93 | s->object()->ActualValue()->id(), |
| 94 | s->value()->id())); |
| 95 | HValue* result = store(s); |
| 96 | if (result == NULL) { |
| 97 | // The store is redundant. Remove it. |
| 98 | TRACE((" remove S%d\n", instr->id())); |
| 99 | instr->DeleteAndReplaceWith(NULL); |
| 100 | } |
| 101 | break; |
| 102 | } |
machenbach@chromium.org | bfd1d20 | 2014-02-19 01:05:38 +0000 | [diff] [blame] | 103 | case HValue::kTransitionElementsKind: { |
| 104 | HTransitionElementsKind* t = HTransitionElementsKind::cast(instr); |
| 105 | HValue* object = t->object()->ActualValue(); |
| 106 | KillFieldInternal(object, FieldOf(JSArray::kElementsOffset), NULL); |
| 107 | KillFieldInternal(object, FieldOf(JSObject::kMapOffset), NULL); |
| 108 | break; |
| 109 | } |
bmeurer@chromium.org | 0fdb2a6 | 2013-10-21 07:19:36 +0000 | [diff] [blame] | 110 | default: { |
machenbach@chromium.org | 7d6bc7d | 2014-02-11 08:13:48 +0000 | [diff] [blame] | 111 | if (instr->CheckChangesFlag(kInobjectFields)) { |
bmeurer@chromium.org | 0fdb2a6 | 2013-10-21 07:19:36 +0000 | [diff] [blame] | 112 | TRACE((" kill-all i%d\n", instr->id())); |
| 113 | Kill(); |
| 114 | break; |
| 115 | } |
machenbach@chromium.org | 7d6bc7d | 2014-02-11 08:13:48 +0000 | [diff] [blame] | 116 | if (instr->CheckChangesFlag(kMaps)) { |
bmeurer@chromium.org | 0fdb2a6 | 2013-10-21 07:19:36 +0000 | [diff] [blame] | 117 | TRACE((" kill-maps i%d\n", instr->id())); |
| 118 | KillOffset(JSObject::kMapOffset); |
| 119 | } |
machenbach@chromium.org | 7d6bc7d | 2014-02-11 08:13:48 +0000 | [diff] [blame] | 120 | if (instr->CheckChangesFlag(kElementsKind)) { |
bmeurer@chromium.org | 0fdb2a6 | 2013-10-21 07:19:36 +0000 | [diff] [blame] | 121 | TRACE((" kill-elements-kind i%d\n", instr->id())); |
| 122 | KillOffset(JSObject::kMapOffset); |
| 123 | KillOffset(JSObject::kElementsOffset); |
| 124 | } |
machenbach@chromium.org | 7d6bc7d | 2014-02-11 08:13:48 +0000 | [diff] [blame] | 125 | if (instr->CheckChangesFlag(kElementsPointer)) { |
bmeurer@chromium.org | 0fdb2a6 | 2013-10-21 07:19:36 +0000 | [diff] [blame] | 126 | TRACE((" kill-elements i%d\n", instr->id())); |
| 127 | KillOffset(JSObject::kElementsOffset); |
| 128 | } |
machenbach@chromium.org | 7d6bc7d | 2014-02-11 08:13:48 +0000 | [diff] [blame] | 129 | if (instr->CheckChangesFlag(kOsrEntries)) { |
bmeurer@chromium.org | 0fdb2a6 | 2013-10-21 07:19:36 +0000 | [diff] [blame] | 130 | TRACE((" kill-osr i%d\n", instr->id())); |
| 131 | Kill(); |
| 132 | } |
| 133 | } |
| 134 | // Improvements possible: |
| 135 | // - learn from HCheckMaps for field 0 |
| 136 | // - remove unobservable stores (write-after-write) |
| 137 | // - track cells |
| 138 | // - track globals |
| 139 | // - track roots |
| 140 | } |
| 141 | return this; |
| 142 | } |
| 143 | |
machenbach@chromium.org | b7234fa | 2014-02-12 08:13:07 +0000 | [diff] [blame] | 144 | // Support for global analysis with HFlowEngine: Merge given state with |
| 145 | // the other incoming state. |
| 146 | static HLoadEliminationTable* Merge(HLoadEliminationTable* succ_state, |
| 147 | HBasicBlock* succ_block, |
| 148 | HLoadEliminationTable* pred_state, |
| 149 | HBasicBlock* pred_block, |
| 150 | Zone* zone) { |
| 151 | ASSERT(pred_state != NULL); |
| 152 | if (succ_state == NULL) { |
| 153 | return pred_state->Copy(succ_block, pred_block, zone); |
| 154 | } else { |
| 155 | return succ_state->Merge(succ_block, pred_state, pred_block, zone); |
| 156 | } |
| 157 | } |
| 158 | |
| 159 | // Support for global analysis with HFlowEngine: Given state merged with all |
| 160 | // the other incoming states, prepare it for use. |
| 161 | static HLoadEliminationTable* Finish(HLoadEliminationTable* state, |
| 162 | HBasicBlock* block, |
| 163 | Zone* zone) { |
| 164 | ASSERT(state != NULL); |
| 165 | return state; |
| 166 | } |
| 167 | |
| 168 | private: |
| 169 | // Copy state to successor block. |
machenbach@chromium.org | 05150ab | 2014-01-29 08:13:29 +0000 | [diff] [blame] | 170 | HLoadEliminationTable* Copy(HBasicBlock* succ, HBasicBlock* from_block, |
| 171 | Zone* zone) { |
bmeurer@chromium.org | 0fdb2a6 | 2013-10-21 07:19:36 +0000 | [diff] [blame] | 172 | HLoadEliminationTable* copy = |
| 173 | new(zone) HLoadEliminationTable(zone, aliasing_); |
| 174 | copy->EnsureFields(fields_.length()); |
| 175 | for (int i = 0; i < fields_.length(); i++) { |
| 176 | copy->fields_[i] = fields_[i]->Copy(zone); |
| 177 | } |
| 178 | if (FLAG_trace_load_elimination) { |
| 179 | TRACE((" copy-to B%d\n", succ->block_id())); |
| 180 | copy->Print(); |
| 181 | } |
| 182 | return copy; |
| 183 | } |
| 184 | |
machenbach@chromium.org | b7234fa | 2014-02-12 08:13:07 +0000 | [diff] [blame] | 185 | // Merge this state with the other incoming state. |
machenbach@chromium.org | 05150ab | 2014-01-29 08:13:29 +0000 | [diff] [blame] | 186 | HLoadEliminationTable* Merge(HBasicBlock* succ, HLoadEliminationTable* that, |
| 187 | HBasicBlock* that_block, Zone* zone) { |
bmeurer@chromium.org | 0fdb2a6 | 2013-10-21 07:19:36 +0000 | [diff] [blame] | 188 | if (that->fields_.length() < fields_.length()) { |
| 189 | // Drop fields not in the other table. |
| 190 | fields_.Rewind(that->fields_.length()); |
| 191 | } |
| 192 | for (int i = 0; i < fields_.length(); i++) { |
| 193 | // Merge the field approximations for like fields. |
| 194 | HFieldApproximation* approx = fields_[i]; |
| 195 | HFieldApproximation* prev = NULL; |
| 196 | while (approx != NULL) { |
| 197 | // TODO(titzer): Merging is O(N * M); sort? |
| 198 | HFieldApproximation* other = that->Find(approx->object_, i); |
| 199 | if (other == NULL || !Equal(approx->last_value_, other->last_value_)) { |
| 200 | // Kill an entry that doesn't agree with the other value. |
| 201 | if (prev != NULL) { |
| 202 | prev->next_ = approx->next_; |
| 203 | } else { |
| 204 | fields_[i] = approx->next_; |
| 205 | } |
| 206 | approx = approx->next_; |
| 207 | continue; |
| 208 | } |
| 209 | prev = approx; |
| 210 | approx = approx->next_; |
| 211 | } |
| 212 | } |
machenbach@chromium.org | 05150ab | 2014-01-29 08:13:29 +0000 | [diff] [blame] | 213 | if (FLAG_trace_load_elimination) { |
| 214 | TRACE((" merge-to B%d\n", succ->block_id())); |
| 215 | Print(); |
| 216 | } |
bmeurer@chromium.org | 0fdb2a6 | 2013-10-21 07:19:36 +0000 | [diff] [blame] | 217 | return this; |
| 218 | } |
| 219 | |
| 220 | friend class HLoadEliminationEffects; // Calls Kill() and others. |
| 221 | friend class HLoadEliminationPhase; |
| 222 | |
| 223 | private: |
machenbach@chromium.org | 528ce02 | 2013-09-23 14:09:36 +0000 | [diff] [blame] | 224 | // Process a load instruction, updating internal table state. If a previous |
| 225 | // load or store for this object and field exists, return the new value with |
| 226 | // which the load should be replaced. Otherwise, return {instr}. |
| 227 | HValue* load(HLoadNamedField* instr) { |
machenbach@chromium.org | 0a73036 | 2014-02-05 03:04:56 +0000 | [diff] [blame] | 228 | // There must be no loads from non observable in-object properties. |
| 229 | ASSERT(!instr->access().IsInobject() || |
| 230 | instr->access().existing_inobject_property()); |
| 231 | |
machenbach@chromium.org | 528ce02 | 2013-09-23 14:09:36 +0000 | [diff] [blame] | 232 | int field = FieldOf(instr->access()); |
| 233 | if (field < 0) return instr; |
| 234 | |
| 235 | HValue* object = instr->object()->ActualValue(); |
| 236 | HFieldApproximation* approx = FindOrCreate(object, field); |
| 237 | |
| 238 | if (approx->last_value_ == NULL) { |
| 239 | // Load is not redundant. Fill out a new entry. |
machenbach@chromium.org | 528ce02 | 2013-09-23 14:09:36 +0000 | [diff] [blame] | 240 | approx->last_value_ = instr; |
| 241 | return instr; |
machenbach@chromium.org | 57a54ac | 2014-01-31 14:01:53 +0000 | [diff] [blame] | 242 | } else if (approx->last_value_->block()->EqualToOrDominates( |
| 243 | instr->block())) { |
machenbach@chromium.org | 528ce02 | 2013-09-23 14:09:36 +0000 | [diff] [blame] | 244 | // Eliminate the load. Reuse previously stored value or load instruction. |
| 245 | return approx->last_value_; |
machenbach@chromium.org | 57a54ac | 2014-01-31 14:01:53 +0000 | [diff] [blame] | 246 | } else { |
| 247 | return instr; |
machenbach@chromium.org | 528ce02 | 2013-09-23 14:09:36 +0000 | [diff] [blame] | 248 | } |
| 249 | } |
| 250 | |
| 251 | // Process a store instruction, updating internal table state. If a previous |
| 252 | // store to the same object and field makes this store redundant (e.g. because |
| 253 | // the stored values are the same), return NULL indicating that this store |
| 254 | // instruction is redundant. Otherwise, return {instr}. |
| 255 | HValue* store(HStoreNamedField* instr) { |
machenbach@chromium.org | 0a73036 | 2014-02-05 03:04:56 +0000 | [diff] [blame] | 256 | if (instr->access().IsInobject() && |
| 257 | !instr->access().existing_inobject_property()) { |
| 258 | TRACE((" skipping non existing property initialization store\n")); |
machenbach@chromium.org | 05150ab | 2014-01-29 08:13:29 +0000 | [diff] [blame] | 259 | return instr; |
| 260 | } |
| 261 | |
machenbach@chromium.org | 528ce02 | 2013-09-23 14:09:36 +0000 | [diff] [blame] | 262 | int field = FieldOf(instr->access()); |
bmeurer@chromium.org | 71f9fca | 2013-10-22 08:00:09 +0000 | [diff] [blame] | 263 | if (field < 0) return KillIfMisaligned(instr); |
machenbach@chromium.org | 528ce02 | 2013-09-23 14:09:36 +0000 | [diff] [blame] | 264 | |
| 265 | HValue* object = instr->object()->ActualValue(); |
| 266 | HValue* value = instr->value(); |
| 267 | |
machenbach@chromium.org | 528ce02 | 2013-09-23 14:09:36 +0000 | [diff] [blame] | 268 | if (instr->has_transition()) { |
hpayer@chromium.org | ea9b8ba | 2013-12-20 19:22:39 +0000 | [diff] [blame] | 269 | // A transition introduces a new field and alters the map of the object. |
| 270 | // Since the field in the object is new, it cannot alias existing entries. |
| 271 | // TODO(titzer): introduce a constant for the new map and remember it. |
machenbach@chromium.org | 528ce02 | 2013-09-23 14:09:36 +0000 | [diff] [blame] | 272 | KillFieldInternal(object, FieldOf(JSObject::kMapOffset), NULL); |
hpayer@chromium.org | ea9b8ba | 2013-12-20 19:22:39 +0000 | [diff] [blame] | 273 | } else { |
| 274 | // Kill non-equivalent may-alias entries. |
| 275 | KillFieldInternal(object, field, value); |
machenbach@chromium.org | 528ce02 | 2013-09-23 14:09:36 +0000 | [diff] [blame] | 276 | } |
| 277 | HFieldApproximation* approx = FindOrCreate(object, field); |
| 278 | |
| 279 | if (Equal(approx->last_value_, value)) { |
| 280 | // The store is redundant because the field already has this value. |
| 281 | return NULL; |
| 282 | } else { |
| 283 | // The store is not redundant. Update the entry. |
machenbach@chromium.org | 528ce02 | 2013-09-23 14:09:36 +0000 | [diff] [blame] | 284 | approx->last_value_ = value; |
| 285 | return instr; |
| 286 | } |
| 287 | } |
| 288 | |
| 289 | // Kill everything in this table. |
| 290 | void Kill() { |
| 291 | fields_.Rewind(0); |
| 292 | } |
| 293 | |
| 294 | // Kill all entries matching the given offset. |
| 295 | void KillOffset(int offset) { |
| 296 | int field = FieldOf(offset); |
| 297 | if (field >= 0 && field < fields_.length()) { |
| 298 | fields_[field] = NULL; |
| 299 | } |
| 300 | } |
| 301 | |
bmeurer@chromium.org | 71f9fca | 2013-10-22 08:00:09 +0000 | [diff] [blame] | 302 | // Kill all entries aliasing the given store. |
| 303 | void KillStore(HStoreNamedField* s) { |
| 304 | int field = FieldOf(s->access()); |
| 305 | if (field >= 0) { |
| 306 | KillFieldInternal(s->object()->ActualValue(), field, s->value()); |
| 307 | } else { |
| 308 | KillIfMisaligned(s); |
| 309 | } |
| 310 | } |
| 311 | |
| 312 | // Kill multiple entries in the case of a misaligned store. |
| 313 | HValue* KillIfMisaligned(HStoreNamedField* instr) { |
| 314 | HObjectAccess access = instr->access(); |
| 315 | if (access.IsInobject()) { |
| 316 | int offset = access.offset(); |
| 317 | if ((offset % kPointerSize) != 0) { |
| 318 | // Kill the field containing the first word of the access. |
| 319 | HValue* object = instr->object()->ActualValue(); |
| 320 | int field = offset / kPointerSize; |
| 321 | KillFieldInternal(object, field, NULL); |
| 322 | |
| 323 | // Kill the next field in case of overlap. |
machenbach@chromium.org | 935a779 | 2013-11-12 09:05:18 +0000 | [diff] [blame] | 324 | int size = access.representation().size(); |
bmeurer@chromium.org | 71f9fca | 2013-10-22 08:00:09 +0000 | [diff] [blame] | 325 | int next_field = (offset + size - 1) / kPointerSize; |
| 326 | if (next_field != field) KillFieldInternal(object, next_field, NULL); |
| 327 | } |
| 328 | } |
| 329 | return instr; |
| 330 | } |
| 331 | |
bmeurer@chromium.org | 0fdb2a6 | 2013-10-21 07:19:36 +0000 | [diff] [blame] | 332 | // Find an entry for the given object and field pair. |
| 333 | HFieldApproximation* Find(HValue* object, int field) { |
| 334 | // Search for a field approximation for this object. |
| 335 | HFieldApproximation* approx = fields_[field]; |
| 336 | while (approx != NULL) { |
| 337 | if (aliasing_->MustAlias(object, approx->object_)) return approx; |
| 338 | approx = approx->next_; |
machenbach@chromium.org | 528ce02 | 2013-09-23 14:09:36 +0000 | [diff] [blame] | 339 | } |
bmeurer@chromium.org | 0fdb2a6 | 2013-10-21 07:19:36 +0000 | [diff] [blame] | 340 | return NULL; |
machenbach@chromium.org | 528ce02 | 2013-09-23 14:09:36 +0000 | [diff] [blame] | 341 | } |
| 342 | |
machenbach@chromium.org | 528ce02 | 2013-09-23 14:09:36 +0000 | [diff] [blame] | 343 | // Find or create an entry for the given object and field pair. |
| 344 | HFieldApproximation* FindOrCreate(HValue* object, int field) { |
| 345 | EnsureFields(field + 1); |
| 346 | |
| 347 | // Search for a field approximation for this object. |
| 348 | HFieldApproximation* approx = fields_[field]; |
| 349 | int count = 0; |
| 350 | while (approx != NULL) { |
| 351 | if (aliasing_->MustAlias(object, approx->object_)) return approx; |
| 352 | count++; |
| 353 | approx = approx->next_; |
| 354 | } |
| 355 | |
| 356 | if (count >= kMaxTrackedObjects) { |
| 357 | // Pull the last entry off the end and repurpose it for this object. |
| 358 | approx = ReuseLastApproximation(field); |
| 359 | } else { |
| 360 | // Allocate a new entry. |
| 361 | approx = new(zone_) HFieldApproximation(); |
| 362 | } |
| 363 | |
| 364 | // Insert the entry at the head of the list. |
| 365 | approx->object_ = object; |
machenbach@chromium.org | 528ce02 | 2013-09-23 14:09:36 +0000 | [diff] [blame] | 366 | approx->last_value_ = NULL; |
| 367 | approx->next_ = fields_[field]; |
| 368 | fields_[field] = approx; |
| 369 | |
| 370 | return approx; |
| 371 | } |
| 372 | |
| 373 | // Kill all entries for a given field that _may_ alias the given object |
| 374 | // and do _not_ have the given value. |
| 375 | void KillFieldInternal(HValue* object, int field, HValue* value) { |
| 376 | if (field >= fields_.length()) return; // Nothing to do. |
| 377 | |
| 378 | HFieldApproximation* approx = fields_[field]; |
| 379 | HFieldApproximation* prev = NULL; |
| 380 | while (approx != NULL) { |
| 381 | if (aliasing_->MayAlias(object, approx->object_)) { |
| 382 | if (!Equal(approx->last_value_, value)) { |
| 383 | // Kill an aliasing entry that doesn't agree on the value. |
| 384 | if (prev != NULL) { |
| 385 | prev->next_ = approx->next_; |
| 386 | } else { |
| 387 | fields_[field] = approx->next_; |
| 388 | } |
| 389 | approx = approx->next_; |
| 390 | continue; |
| 391 | } |
| 392 | } |
| 393 | prev = approx; |
| 394 | approx = approx->next_; |
| 395 | } |
| 396 | } |
| 397 | |
| 398 | bool Equal(HValue* a, HValue* b) { |
| 399 | if (a == b) return true; |
yangguo@chromium.org | cc53605 | 2013-11-29 11:43:20 +0000 | [diff] [blame] | 400 | if (a != NULL && b != NULL && a->CheckFlag(HValue::kUseGVN)) { |
| 401 | return a->Equals(b); |
| 402 | } |
machenbach@chromium.org | 528ce02 | 2013-09-23 14:09:36 +0000 | [diff] [blame] | 403 | return false; |
| 404 | } |
| 405 | |
| 406 | // Remove the last approximation for a field so that it can be reused. |
| 407 | // We reuse the last entry because it was the first inserted and is thus |
| 408 | // farthest away from the current instruction. |
| 409 | HFieldApproximation* ReuseLastApproximation(int field) { |
| 410 | HFieldApproximation* approx = fields_[field]; |
| 411 | ASSERT(approx != NULL); |
| 412 | |
| 413 | HFieldApproximation* prev = NULL; |
| 414 | while (approx->next_ != NULL) { |
| 415 | prev = approx; |
| 416 | approx = approx->next_; |
| 417 | } |
| 418 | if (prev != NULL) prev->next_ = NULL; |
| 419 | return approx; |
| 420 | } |
| 421 | |
bmeurer@chromium.org | 0fdb2a6 | 2013-10-21 07:19:36 +0000 | [diff] [blame] | 422 | // Compute the field index for the given object access; -1 if not tracked. |
| 423 | int FieldOf(HObjectAccess access) { |
| 424 | return access.IsInobject() ? FieldOf(access.offset()) : -1; |
machenbach@chromium.org | 528ce02 | 2013-09-23 14:09:36 +0000 | [diff] [blame] | 425 | } |
| 426 | |
bmeurer@chromium.org | 0fdb2a6 | 2013-10-21 07:19:36 +0000 | [diff] [blame] | 427 | // Compute the field index for the given in-object offset; -1 if not tracked. |
machenbach@chromium.org | 528ce02 | 2013-09-23 14:09:36 +0000 | [diff] [blame] | 428 | int FieldOf(int offset) { |
| 429 | if (offset >= kMaxTrackedFields * kPointerSize) return -1; |
bmeurer@chromium.org | 71f9fca | 2013-10-22 08:00:09 +0000 | [diff] [blame] | 430 | // TODO(titzer): track misaligned loads in a separate list? |
| 431 | if ((offset % kPointerSize) != 0) return -1; // Ignore misaligned accesses. |
machenbach@chromium.org | 528ce02 | 2013-09-23 14:09:36 +0000 | [diff] [blame] | 432 | return offset / kPointerSize; |
| 433 | } |
| 434 | |
bmeurer@chromium.org | 0fdb2a6 | 2013-10-21 07:19:36 +0000 | [diff] [blame] | 435 | // Ensure internal storage for the given number of fields. |
| 436 | void EnsureFields(int num_fields) { |
| 437 | if (fields_.length() < num_fields) { |
| 438 | fields_.AddBlock(NULL, num_fields - fields_.length(), zone_); |
| 439 | } |
| 440 | } |
| 441 | |
| 442 | // Print this table to stdout. |
| 443 | void Print() { |
| 444 | for (int i = 0; i < fields_.length(); i++) { |
| 445 | PrintF(" field %d: ", i); |
| 446 | for (HFieldApproximation* a = fields_[i]; a != NULL; a = a->next_) { |
| 447 | PrintF("[o%d =", a->object_->id()); |
bmeurer@chromium.org | 0fdb2a6 | 2013-10-21 07:19:36 +0000 | [diff] [blame] | 448 | if (a->last_value_ != NULL) PrintF(" v%d", a->last_value_->id()); |
| 449 | PrintF("] "); |
| 450 | } |
| 451 | PrintF("\n"); |
| 452 | } |
| 453 | } |
| 454 | |
machenbach@chromium.org | 528ce02 | 2013-09-23 14:09:36 +0000 | [diff] [blame] | 455 | Zone* zone_; |
| 456 | ZoneList<HFieldApproximation*> fields_; |
| 457 | HAliasAnalyzer* aliasing_; |
| 458 | }; |
| 459 | |
| 460 | |
bmeurer@chromium.org | 0fdb2a6 | 2013-10-21 07:19:36 +0000 | [diff] [blame] | 461 | // Support for HFlowEngine: collect store effects within loops. |
| 462 | class HLoadEliminationEffects : public ZoneObject { |
| 463 | public: |
| 464 | explicit HLoadEliminationEffects(Zone* zone) |
mstarzinger@chromium.org | 1e71c4d | 2014-02-13 10:16:41 +0000 | [diff] [blame] | 465 | : zone_(zone), stores_(5, zone) { } |
bmeurer@chromium.org | 0fdb2a6 | 2013-10-21 07:19:36 +0000 | [diff] [blame] | 466 | |
| 467 | inline bool Disabled() { |
| 468 | return false; // Effects are _not_ disabled. |
machenbach@chromium.org | 528ce02 | 2013-09-23 14:09:36 +0000 | [diff] [blame] | 469 | } |
machenbach@chromium.org | 528ce02 | 2013-09-23 14:09:36 +0000 | [diff] [blame] | 470 | |
bmeurer@chromium.org | 0fdb2a6 | 2013-10-21 07:19:36 +0000 | [diff] [blame] | 471 | // Process a possibly side-effecting instruction. |
| 472 | void Process(HInstruction* instr, Zone* zone) { |
mstarzinger@chromium.org | 1e71c4d | 2014-02-13 10:16:41 +0000 | [diff] [blame] | 473 | if (instr->IsStoreNamedField()) { |
| 474 | stores_.Add(HStoreNamedField::cast(instr), zone_); |
| 475 | } else { |
| 476 | flags_.Add(instr->ChangesFlags()); |
bmeurer@chromium.org | 0fdb2a6 | 2013-10-21 07:19:36 +0000 | [diff] [blame] | 477 | } |
| 478 | } |
| 479 | |
| 480 | // Apply these effects to the given load elimination table. |
| 481 | void Apply(HLoadEliminationTable* table) { |
mstarzinger@chromium.org | 1e71c4d | 2014-02-13 10:16:41 +0000 | [diff] [blame] | 482 | // Loads must not be hoisted past the OSR entry, therefore we kill |
| 483 | // everything if we see an OSR entry. |
| 484 | if (flags_.Contains(kInobjectFields) || flags_.Contains(kOsrEntries)) { |
bmeurer@chromium.org | 0fdb2a6 | 2013-10-21 07:19:36 +0000 | [diff] [blame] | 485 | table->Kill(); |
| 486 | return; |
| 487 | } |
mstarzinger@chromium.org | 1e71c4d | 2014-02-13 10:16:41 +0000 | [diff] [blame] | 488 | if (flags_.Contains(kElementsKind) || flags_.Contains(kMaps)) { |
bmeurer@chromium.org | 0fdb2a6 | 2013-10-21 07:19:36 +0000 | [diff] [blame] | 489 | table->KillOffset(JSObject::kMapOffset); |
| 490 | } |
mstarzinger@chromium.org | 1e71c4d | 2014-02-13 10:16:41 +0000 | [diff] [blame] | 491 | if (flags_.Contains(kElementsKind) || flags_.Contains(kElementsPointer)) { |
bmeurer@chromium.org | 0fdb2a6 | 2013-10-21 07:19:36 +0000 | [diff] [blame] | 492 | table->KillOffset(JSObject::kElementsOffset); |
machenbach@chromium.org | 528ce02 | 2013-09-23 14:09:36 +0000 | [diff] [blame] | 493 | } |
| 494 | |
bmeurer@chromium.org | 0fdb2a6 | 2013-10-21 07:19:36 +0000 | [diff] [blame] | 495 | // Kill non-agreeing fields for each store contained in these effects. |
| 496 | for (int i = 0; i < stores_.length(); i++) { |
bmeurer@chromium.org | 71f9fca | 2013-10-22 08:00:09 +0000 | [diff] [blame] | 497 | table->KillStore(stores_[i]); |
bmeurer@chromium.org | 0fdb2a6 | 2013-10-21 07:19:36 +0000 | [diff] [blame] | 498 | } |
| 499 | } |
| 500 | |
| 501 | // Union these effects with the other effects. |
| 502 | void Union(HLoadEliminationEffects* that, Zone* zone) { |
mstarzinger@chromium.org | 1e71c4d | 2014-02-13 10:16:41 +0000 | [diff] [blame] | 503 | flags_.Add(that->flags_); |
bmeurer@chromium.org | 0fdb2a6 | 2013-10-21 07:19:36 +0000 | [diff] [blame] | 504 | for (int i = 0; i < that->stores_.length(); i++) { |
| 505 | stores_.Add(that->stores_[i], zone); |
| 506 | } |
| 507 | } |
| 508 | |
| 509 | private: |
| 510 | Zone* zone_; |
mstarzinger@chromium.org | 1e71c4d | 2014-02-13 10:16:41 +0000 | [diff] [blame] | 511 | GVNFlagSet flags_; |
bmeurer@chromium.org | 0fdb2a6 | 2013-10-21 07:19:36 +0000 | [diff] [blame] | 512 | ZoneList<HStoreNamedField*> stores_; |
| 513 | }; |
| 514 | |
| 515 | |
| 516 | // The main routine of the analysis phase. Use the HFlowEngine for either a |
| 517 | // local or a global analysis. |
| 518 | void HLoadEliminationPhase::Run() { |
| 519 | HFlowEngine<HLoadEliminationTable, HLoadEliminationEffects> |
| 520 | engine(graph(), zone()); |
| 521 | HAliasAnalyzer aliasing; |
| 522 | HLoadEliminationTable* table = |
| 523 | new(zone()) HLoadEliminationTable(zone(), &aliasing); |
| 524 | |
| 525 | if (GLOBAL) { |
| 526 | // Perform a global analysis. |
| 527 | engine.AnalyzeDominatedBlocks(graph()->blocks()->at(0), table); |
| 528 | } else { |
| 529 | // Perform only local analysis. |
| 530 | for (int i = 0; i < graph()->blocks()->length(); i++) { |
| 531 | table->Kill(); |
| 532 | engine.AnalyzeOneBlock(graph()->blocks()->at(i), table); |
machenbach@chromium.org | 528ce02 | 2013-09-23 14:09:36 +0000 | [diff] [blame] | 533 | } |
| 534 | } |
| 535 | } |
| 536 | |
machenbach@chromium.org | 528ce02 | 2013-09-23 14:09:36 +0000 | [diff] [blame] | 537 | } } // namespace v8::internal |