| // Copyright 2013 the V8 project authors. All rights reserved. |
| // Redistribution and use in source and binary forms, with or without |
| // modification, are permitted provided that the following conditions are |
| // met: |
| // |
| // * Redistributions of source code must retain the above copyright |
| // notice, this list of conditions and the following disclaimer. |
| // * Redistributions in binary form must reproduce the above |
| // copyright notice, this list of conditions and the following |
| // disclaimer in the documentation and/or other materials provided |
| // with the distribution. |
| // * Neither the name of Google Inc. nor the names of its |
| // contributors may be used to endorse or promote products derived |
| // from this software without specific prior written permission. |
| // |
| // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS |
| // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT |
| // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR |
| // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT |
| // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, |
| // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT |
| // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, |
| // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY |
| // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |
| // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE |
| // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
| |
| #include "hydrogen-check-elimination.h" |
| #include "hydrogen-alias-analysis.h" |
| |
| namespace v8 { |
| namespace internal { |
| |
| static const int kMaxTrackedObjects = 10; |
| typedef UniqueSet<Map>* MapSet; |
| |
| // The main datastructure used during check elimination, which stores a |
| // set of known maps for each object. |
| class HCheckTable { |
| public: |
| explicit HCheckTable(Zone* zone) : zone_(zone) { |
| Kill(); |
| redundant_ = 0; |
| narrowed_ = 0; |
| empty_ = 0; |
| removed_ = 0; |
| compares_true_ = 0; |
| compares_false_ = 0; |
| transitions_ = 0; |
| loads_ = 0; |
| } |
| |
| void ReduceCheckMaps(HCheckMaps* instr) { |
| HValue* object = instr->value()->ActualValue(); |
| int index = Find(object); |
| if (index >= 0) { |
| // entry found; |
| MapSet a = known_maps_[index]; |
| MapSet i = instr->map_set().Copy(zone_); |
| if (a->IsSubset(i)) { |
| // The first check is more strict; the second is redundant. |
| if (checks_[index] != NULL) { |
| instr->DeleteAndReplaceWith(checks_[index]); |
| redundant_++; |
| } else { |
| instr->DeleteAndReplaceWith(instr->value()); |
| removed_++; |
| } |
| return; |
| } |
| i = i->Intersect(a, zone_); |
| if (i->size() == 0) { |
| // Intersection is empty; probably megamorphic, which is likely to |
| // deopt anyway, so just leave things as they are. |
| empty_++; |
| } else { |
| // TODO(titzer): replace the first check with a more strict check. |
| narrowed_++; |
| } |
| } else { |
| // No entry; insert a new one. |
| Insert(object, instr, instr->map_set().Copy(zone_)); |
| } |
| } |
| |
| void ReduceCheckValue(HCheckValue* instr) { |
| // Canonicalize HCheckValues; they might have their values load-eliminated. |
| HValue* value = instr->Canonicalize(); |
| if (value == NULL) { |
| instr->DeleteAndReplaceWith(instr->value()); |
| removed_++; |
| } else if (value != instr) { |
| instr->DeleteAndReplaceWith(value); |
| redundant_++; |
| } |
| } |
| |
| void ReduceLoadNamedField(HLoadNamedField* instr) { |
| // Reduce a load of the map field when it is known to be a constant. |
| if (!IsMapAccess(instr->access())) return; |
| |
| HValue* object = instr->object()->ActualValue(); |
| MapSet maps = FindMaps(object); |
| if (maps == NULL || maps->size() != 1) return; // Not a constant. |
| |
| Unique<Map> map = maps->at(0); |
| HConstant* constant = HConstant::CreateAndInsertBefore( |
| instr->block()->graph()->zone(), map, true, instr); |
| instr->DeleteAndReplaceWith(constant); |
| loads_++; |
| } |
| |
| void ReduceCheckMapValue(HCheckMapValue* instr) { |
| if (!instr->map()->IsConstant()) return; // Nothing to learn. |
| |
| HValue* object = instr->value()->ActualValue(); |
| // Match a HCheckMapValue(object, HConstant(map)) |
| Unique<Map> map = MapConstant(instr->map()); |
| MapSet maps = FindMaps(object); |
| if (maps != NULL) { |
| if (maps->Contains(map)) { |
| if (maps->size() == 1) { |
| // Object is known to have exactly this map. |
| instr->DeleteAndReplaceWith(NULL); |
| removed_++; |
| } else { |
| // Only one map survives the check. |
| maps->Clear(); |
| maps->Add(map, zone_); |
| } |
| } |
| } else { |
| // No prior information. |
| Insert(object, map); |
| } |
| } |
| |
| void ReduceStoreNamedField(HStoreNamedField* instr) { |
| HValue* object = instr->object()->ActualValue(); |
| if (instr->has_transition()) { |
| // This store transitions the object to a new map. |
| Kill(object); |
| Insert(object, MapConstant(instr->transition())); |
| } else if (IsMapAccess(instr->access())) { |
| // This is a store directly to the map field of the object. |
| Kill(object); |
| if (!instr->value()->IsConstant()) return; |
| Insert(object, MapConstant(instr->value())); |
| } else if (instr->CheckGVNFlag(kChangesMaps)) { |
| // This store indirectly changes the map of the object. |
| Kill(instr->object()); |
| UNREACHABLE(); |
| } |
| } |
| |
| void ReduceCompareMap(HCompareMap* instr) { |
| MapSet maps = FindMaps(instr->value()->ActualValue()); |
| if (maps == NULL) return; |
| if (maps->Contains(instr->map())) { |
| // TODO(titzer): replace with goto true branch |
| if (maps->size() == 1) compares_true_++; |
| } else { |
| // TODO(titzer): replace with goto false branch |
| compares_false_++; |
| } |
| } |
| |
| void ReduceTransitionElementsKind(HTransitionElementsKind* instr) { |
| MapSet maps = FindMaps(instr->object()->ActualValue()); |
| // Can only learn more about an object that already has a known set of maps. |
| if (maps == NULL) return; |
| if (maps->Contains(instr->original_map())) { |
| // If the object has the original map, it will be transitioned. |
| maps->Remove(instr->original_map()); |
| maps->Add(instr->transitioned_map(), zone_); |
| } else { |
| // Object does not have the given map, thus the transition is redundant. |
| instr->DeleteAndReplaceWith(instr->object()); |
| transitions_++; |
| } |
| } |
| |
| // Kill everything in the table. |
| void Kill() { |
| memset(objects_, 0, sizeof(objects_)); |
| } |
| |
| // Kill everything in the table that may alias {object}. |
| void Kill(HValue* object) { |
| for (int i = 0; i < kMaxTrackedObjects; i++) { |
| if (objects_[i] == NULL) continue; |
| if (aliasing_.MayAlias(objects_[i], object)) objects_[i] = NULL; |
| } |
| ASSERT(Find(object) < 0); |
| } |
| |
| void Print() { |
| for (int i = 0; i < kMaxTrackedObjects; i++) { |
| if (objects_[i] == NULL) continue; |
| PrintF(" checkmaps-table @%d: object #%d ", i, objects_[i]->id()); |
| if (checks_[i] != NULL) { |
| PrintF("check #%d ", checks_[i]->id()); |
| } |
| MapSet list = known_maps_[i]; |
| PrintF("%d maps { ", list->size()); |
| for (int j = 0; j < list->size(); j++) { |
| if (j > 0) PrintF(", "); |
| PrintF("%" V8PRIxPTR, list->at(j).Hashcode()); |
| } |
| PrintF(" }\n"); |
| } |
| } |
| |
| void PrintStats() { |
| if (redundant_ > 0) PrintF(" redundant = %2d\n", redundant_); |
| if (removed_ > 0) PrintF(" removed = %2d\n", removed_); |
| if (narrowed_ > 0) PrintF(" narrowed = %2d\n", narrowed_); |
| if (loads_ > 0) PrintF(" loads = %2d\n", loads_); |
| if (empty_ > 0) PrintF(" empty = %2d\n", empty_); |
| if (compares_true_ > 0) PrintF(" cmp_true = %2d\n", compares_true_); |
| if (compares_false_ > 0) PrintF(" cmp_false = %2d\n", compares_false_); |
| if (transitions_ > 0) PrintF(" transitions = %2d\n", transitions_); |
| } |
| |
| private: |
| int Find(HValue* object) { |
| for (int i = 0; i < kMaxTrackedObjects; i++) { |
| if (objects_[i] == NULL) continue; |
| if (aliasing_.MustAlias(objects_[i], object)) return i; |
| } |
| return -1; |
| } |
| |
| MapSet FindMaps(HValue* object) { |
| int index = Find(object); |
| return index < 0 ? NULL : known_maps_[index]; |
| } |
| |
| void Insert(HValue* object, Unique<Map> map) { |
| MapSet list = new(zone_) UniqueSet<Map>(); |
| list->Add(map, zone_); |
| Insert(object, NULL, list); |
| } |
| |
| void Insert(HValue* object, HCheckMaps* check, MapSet maps) { |
| for (int i = 0; i < kMaxTrackedObjects; i++) { |
| // TODO(titzer): drop old entries instead of disallowing new ones. |
| if (objects_[i] == NULL) { |
| objects_[i] = object; |
| checks_[i] = check; |
| known_maps_[i] = maps; |
| return; |
| } |
| } |
| } |
| |
| bool IsMapAccess(HObjectAccess access) { |
| return access.IsInobject() && access.offset() == JSObject::kMapOffset; |
| } |
| |
| Unique<Map> MapConstant(HValue* value) { |
| return Unique<Map>::cast(HConstant::cast(value)->GetUnique()); |
| } |
| |
| Zone* zone_; |
| HValue* objects_[kMaxTrackedObjects]; |
| HValue* checks_[kMaxTrackedObjects]; |
| MapSet known_maps_[kMaxTrackedObjects]; |
| HAliasAnalyzer aliasing_; |
| int redundant_; |
| int removed_; |
| int narrowed_; |
| int loads_; |
| int empty_; |
| int compares_true_; |
| int compares_false_; |
| int transitions_; |
| }; |
| |
| |
| void HCheckEliminationPhase::Run() { |
| for (int i = 0; i < graph()->blocks()->length(); i++) { |
| EliminateLocalChecks(graph()->blocks()->at(i)); |
| } |
| } |
| |
| |
| // For code de-uglification. |
| #define TRACE(x) if (FLAG_trace_check_elimination) PrintF x |
| |
| |
| // Eliminate checks local to a block. |
| void HCheckEliminationPhase::EliminateLocalChecks(HBasicBlock* block) { |
| HCheckTable table(zone()); |
| TRACE(("-- check-elim B%d ------------------------------------------------\n", |
| block->block_id())); |
| |
| for (HInstructionIterator it(block); !it.Done(); it.Advance()) { |
| bool changed = false; |
| HInstruction* instr = it.Current(); |
| |
| switch (instr->opcode()) { |
| case HValue::kCheckMaps: { |
| table.ReduceCheckMaps(HCheckMaps::cast(instr)); |
| changed = true; |
| break; |
| } |
| case HValue::kCheckValue: { |
| table.ReduceCheckValue(HCheckValue::cast(instr)); |
| changed = true; |
| break; |
| } |
| case HValue::kLoadNamedField: { |
| table.ReduceLoadNamedField(HLoadNamedField::cast(instr)); |
| changed = true; |
| break; |
| } |
| case HValue::kStoreNamedField: { |
| table.ReduceStoreNamedField(HStoreNamedField::cast(instr)); |
| changed = true; |
| break; |
| } |
| case HValue::kCompareMap: { |
| table.ReduceCompareMap(HCompareMap::cast(instr)); |
| changed = true; |
| break; |
| } |
| case HValue::kTransitionElementsKind: { |
| table.ReduceTransitionElementsKind( |
| HTransitionElementsKind::cast(instr)); |
| changed = true; |
| break; |
| } |
| case HValue::kCheckMapValue: { |
| table.ReduceCheckMapValue(HCheckMapValue::cast(instr)); |
| changed = true; |
| break; |
| } |
| default: { |
| // If the instruction changes maps uncontrollably, kill the whole town. |
| if (instr->CheckGVNFlag(kChangesMaps)) { |
| table.Kill(); |
| changed = true; |
| } |
| } |
| // Improvements possible: |
| // - eliminate HCheckSmi and HCheckHeapObject |
| } |
| |
| if (changed && FLAG_trace_check_elimination) table.Print(); |
| } |
| |
| if (FLAG_trace_check_elimination) table.PrintStats(); |
| } |
| |
| |
| } } // namespace v8::internal |