CSE2410 Fall 2014 Bounce

// 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