// Copyright 2016 the V8 project authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#include <iterator>

#include "src/compiler/store-store-elimination.h"

#include "src/codegen/tick-counter.h"
#include "src/compiler/all-nodes.h"
#include "src/compiler/js-graph.h"
#include "src/compiler/node-properties.h"
#include "src/compiler/simplified-operator.h"

namespace v8 {
namespace internal {
namespace compiler {

#define TRACE(fmt, ...)                                         \
  do {                                                          \
    if (FLAG_trace_store_elimination) {                         \
      PrintF("RedundantStoreFinder: " fmt "\n", ##__VA_ARGS__); \
    }                                                           \
  } while (false)

// CHECK_EXTRA is like CHECK, but has two or more arguments: a boolean
// expression, a format string, and any number of extra arguments. The boolean
// expression will be evaluated at runtime. If it evaluates to false, then an
// error message will be shown containing the condition, as well as the extra
// info formatted like with printf.
#define CHECK_EXTRA(condition, fmt, ...)                                      \
  do {                                                                        \
    if (V8_UNLIKELY(!(condition))) {                                          \
      FATAL("Check failed: %s. Extra info: " fmt, #condition, ##__VA_ARGS__); \
    }                                                                         \
  } while (false)

#ifdef DEBUG
#define DCHECK_EXTRA(condition, fmt, ...) \
  CHECK_EXTRA(condition, fmt, ##__VA_ARGS__)
#else
#define DCHECK_EXTRA(condition, fmt, ...) ((void)0)
#endif

// Store-store elimination.
//
// The aim of this optimization is to detect the following pattern in the
// effect graph:
//
// - StoreField[+24, kRepTagged](263, ...)
//
//   ... lots of nodes from which the field at offset 24 of the object
//       returned by node #263 cannot be observed ...
//
// - StoreField[+24, kRepTagged](263, ...)
//
// In such situations, the earlier StoreField cannot be observed, and can be
// eliminated. This optimization should work for any offset and input node, of
// course.
//
// The optimization also works across splits. It currently does not work for
// loops, because we tend to put a stack check in loops, and like deopts,
// stack checks can observe anything.

// Assumption: every byte of a JS object is only ever accessed through one
// offset. For instance, byte 15 of a given object may be accessed using a
// two-byte read at offset 14, or a four-byte read at offset 12, but never
// both in the same program.
//
// This implementation needs all dead nodes removed from the graph, and the
// graph should be trimmed.

namespace {

using StoreOffset = uint32_t;

struct UnobservableStore {
  NodeId id_;
  StoreOffset offset_;

  bool operator==(const UnobservableStore) const;
  bool operator<(const UnobservableStore) const;
};

}  // namespace

namespace {

// Instances of UnobservablesSet are immutable. They represent either a set of
// UnobservableStores, or the "unvisited empty set".
//
// We apply some sharing to save memory. The class UnobservablesSet is only a
// pointer wide, and a copy does not use any heap (or temp_zone) memory. Most
// changes to an UnobservablesSet might allocate in the temp_zone.
//
// The size of an instance should be the size of a pointer, plus additional
// space in the zone in the case of non-unvisited UnobservablesSets. Copying
// an UnobservablesSet allocates no memory.
class UnobservablesSet final {
 public:
  static UnobservablesSet Unvisited();
  static UnobservablesSet VisitedEmpty(Zone* zone);
  UnobservablesSet();  // unvisited
  UnobservablesSet(const UnobservablesSet& other) V8_NOEXCEPT = default;

  UnobservablesSet Intersect(const UnobservablesSet& other, Zone* zone) const;
  UnobservablesSet Add(UnobservableStore obs, Zone* zone) const;
  UnobservablesSet RemoveSameOffset(StoreOffset off, Zone* zone) const;

  const ZoneSet<UnobservableStore>* set() const { return set_; }

  bool IsUnvisited() const { return set_ == nullptr; }
  bool IsEmpty() const { return set_ == nullptr || set_->empty(); }
  bool Contains(UnobservableStore obs) const {
    return set_ != nullptr && (set_->find(obs) != set_->end());
  }

  bool operator==(const UnobservablesSet&) const;
  bool operator!=(const UnobservablesSet&) const;

 private:
  explicit UnobservablesSet(const ZoneSet<UnobservableStore>* set)
      : set_(set) {}
  const ZoneSet<UnobservableStore>* set_;
};

}  // namespace

namespace {

class RedundantStoreFinder final {
 public:
  RedundantStoreFinder(JSGraph* js_graph, TickCounter* tick_counter,
                       Zone* temp_zone);

  void Find();

  const ZoneSet<Node*>& to_remove_const() { return to_remove_; }

  void Visit(Node* node);

 private:
  void VisitEffectfulNode(Node* node);
  UnobservablesSet RecomputeUseIntersection(Node* node);
  UnobservablesSet RecomputeSet(Node* node, const UnobservablesSet& uses);
  static bool CannotObserveStoreField(Node* node);

  void MarkForRevisit(Node* node);
  bool HasBeenVisited(Node* node);

  JSGraph* jsgraph() const { return jsgraph_; }
  Isolate* isolate() { return jsgraph()->isolate(); }
  Zone* temp_zone() const { return temp_zone_; }
  ZoneVector<UnobservablesSet>& unobservable() { return unobservable_; }
  UnobservablesSet& unobservable_for_id(NodeId id) {
    DCHECK_LT(id, unobservable().size());
    return unobservable()[id];
  }
  ZoneSet<Node*>& to_remove() { return to_remove_; }

  JSGraph* const jsgraph_;
  TickCounter* const tick_counter_;
  Zone* const temp_zone_;

  ZoneStack<Node*> revisit_;
  ZoneVector<bool> in_revisit_;
  // Maps node IDs to UnobservableNodeSets.
  ZoneVector<UnobservablesSet> unobservable_;
  ZoneSet<Node*> to_remove_;
  const UnobservablesSet unobservables_visited_empty_;
};

// To safely cast an offset from a FieldAccess, which has a potentially wider
// range (namely int).
StoreOffset ToOffset(int offset) {
  CHECK_LE(0, offset);
  return static_cast<StoreOffset>(offset);
}

StoreOffset ToOffset(const FieldAccess& access) {
  return ToOffset(access.offset);
}

unsigned int RepSizeOf(MachineRepresentation rep) {
  return 1u << ElementSizeLog2Of(rep);
}
unsigned int RepSizeOf(FieldAccess access) {
  return RepSizeOf(access.machine_type.representation());
}

bool AtMostTagged(FieldAccess access) {
  return RepSizeOf(access) <= RepSizeOf(MachineRepresentation::kTagged);
}

bool AtLeastTagged(FieldAccess access) {
  return RepSizeOf(access) >= RepSizeOf(MachineRepresentation::kTagged);
}

}  // namespace

void RedundantStoreFinder::Find() {
  Visit(jsgraph()->graph()->end());

  while (!revisit_.empty()) {
    tick_counter_->DoTick();
    Node* next = revisit_.top();
    revisit_.pop();
    DCHECK_LT(next->id(), in_revisit_.size());
    in_revisit_[next->id()] = false;
    Visit(next);
  }

#ifdef DEBUG
  // Check that we visited all the StoreFields
  AllNodes all(temp_zone(), jsgraph()->graph());
  for (Node* node : all.reachable) {
    if (node->op()->opcode() == IrOpcode::kStoreField) {
      DCHECK_EXTRA(HasBeenVisited(node), "#%d:%s", node->id(),
                   node->op()->mnemonic());
    }
  }
#endif
}

void RedundantStoreFinder::MarkForRevisit(Node* node) {
  DCHECK_LT(node->id(), in_revisit_.size());
  if (!in_revisit_[node->id()]) {
    revisit_.push(node);
    in_revisit_[node->id()] = true;
  }
}

bool RedundantStoreFinder::HasBeenVisited(Node* node) {
  return !unobservable_for_id(node->id()).IsUnvisited();
}

void StoreStoreElimination::Run(JSGraph* js_graph, TickCounter* tick_counter,
                                Zone* temp_zone) {
  // Find superfluous nodes
  RedundantStoreFinder finder(js_graph, tick_counter, temp_zone);
  finder.Find();

  // Remove superfluous nodes

  for (Node* node : finder.to_remove_const()) {
    if (FLAG_trace_store_elimination) {
      PrintF("StoreStoreElimination::Run: Eliminating node #%d:%s\n",
             node->id(), node->op()->mnemonic());
    }
    Node* previous_effect = NodeProperties::GetEffectInput(node);
    NodeProperties::ReplaceUses(node, nullptr, previous_effect, nullptr,
                                nullptr);
    node->Kill();
  }
}

// Recompute unobservables-set for a node. Will also mark superfluous nodes
// as to be removed.

UnobservablesSet RedundantStoreFinder::RecomputeSet(
    Node* node, const UnobservablesSet& uses) {
  switch (node->op()->opcode()) {
    case IrOpcode::kStoreField: {
      Node* stored_to = node->InputAt(0);
      const FieldAccess& access = FieldAccessOf(node->op());
      StoreOffset offset = ToOffset(access);

      UnobservableStore observation = {stored_to->id(), offset};
      bool isNotObservable = uses.Contains(observation);

      if (isNotObservable && AtMostTagged(access)) {
        TRACE("  #%d is StoreField[+%d,%s](#%d), unobservable", node->id(),
              offset, MachineReprToString(access.machine_type.representation()),
              stored_to->id());
        to_remove().insert(node);
        return uses;
      } else if (isNotObservable && !AtMostTagged(access)) {
        TRACE(
            "  #%d is StoreField[+%d,%s](#%d), repeated in future but too "
            "big to optimize away",
            node->id(), offset,
            MachineReprToString(access.machine_type.representation()),
            stored_to->id());
        return uses;
      } else if (!isNotObservable && AtLeastTagged(access)) {
        TRACE("  #%d is StoreField[+%d,%s](#%d), observable, recording in set",
              node->id(), offset,
              MachineReprToString(access.machine_type.representation()),
              stored_to->id());
        return uses.Add(observation, temp_zone());
      } else if (!isNotObservable && !AtLeastTagged(access)) {
        TRACE(
            "  #%d is StoreField[+%d,%s](#%d), observable but too small to "
            "record",
            node->id(), offset,
            MachineReprToString(access.machine_type.representation()),
            stored_to->id());
        return uses;
      } else {
        UNREACHABLE();
      }
      break;
    }
    case IrOpcode::kLoadField: {
      Node* loaded_from = node->InputAt(0);
      const FieldAccess& access = FieldAccessOf(node->op());
      StoreOffset offset = ToOffset(access);

      TRACE(
          "  #%d is LoadField[+%d,%s](#%d), removing all offsets [+%d] from "
          "set",
          node->id(), offset,
          MachineReprToString(access.machine_type.representation()),
          loaded_from->id(), offset);

      return uses.RemoveSameOffset(offset, temp_zone());
      break;
    }
    default:
      if (CannotObserveStoreField(node)) {
        TRACE("  #%d:%s can observe nothing, set stays unchanged", node->id(),
              node->op()->mnemonic());
        return uses;
      } else {
        TRACE("  #%d:%s might observe anything, recording empty set",
              node->id(), node->op()->mnemonic());
        return unobservables_visited_empty_;
      }
  }
  UNREACHABLE();
}

bool RedundantStoreFinder::CannotObserveStoreField(Node* node) {
  return node->opcode() == IrOpcode::kLoadElement ||
         node->opcode() == IrOpcode::kLoad ||
         node->opcode() == IrOpcode::kStore ||
         node->opcode() == IrOpcode::kEffectPhi ||
         node->opcode() == IrOpcode::kStoreElement ||
         node->opcode() == IrOpcode::kUnsafePointerAdd ||
         node->opcode() == IrOpcode::kRetain;
}

// Initialize unobservable_ with js_graph->graph->NodeCount() empty sets.
RedundantStoreFinder::RedundantStoreFinder(JSGraph* js_graph,
                                           TickCounter* tick_counter,
                                           Zone* temp_zone)
    : jsgraph_(js_graph),
      tick_counter_(tick_counter),
      temp_zone_(temp_zone),
      revisit_(temp_zone),
      in_revisit_(js_graph->graph()->NodeCount(), temp_zone),
      unobservable_(js_graph->graph()->NodeCount(),
                    UnobservablesSet::Unvisited(), temp_zone),
      to_remove_(temp_zone),
      unobservables_visited_empty_(UnobservablesSet::VisitedEmpty(temp_zone)) {}

void RedundantStoreFinder::Visit(Node* node) {
  // All effectful nodes should be reachable from End via a sequence of
  // control, then a sequence of effect edges. In VisitEffectfulNode we mark
  // all effect inputs for revisiting (if they might have stale state); here
  // we mark all control inputs at least once.

  if (!HasBeenVisited(node)) {
    for (int i = 0; i < node->op()->ControlInputCount(); i++) {
      Node* control_input = NodeProperties::GetControlInput(node, i);
      if (!HasBeenVisited(control_input)) {
        MarkForRevisit(control_input);
      }
    }
  }

  bool isEffectful = (node->op()->EffectInputCount() >= 1);
  if (isEffectful) {
    VisitEffectfulNode(node);
    DCHECK(HasBeenVisited(node));
  }

  if (!HasBeenVisited(node)) {
    // Mark as visited.
    unobservable_for_id(node->id()) = unobservables_visited_empty_;
  }
}

void RedundantStoreFinder::VisitEffectfulNode(Node* node) {
  if (HasBeenVisited(node)) {
    TRACE("- Revisiting: #%d:%s", node->id(), node->op()->mnemonic());
  }
  UnobservablesSet after_set = RecomputeUseIntersection(node);
  UnobservablesSet before_set = RecomputeSet(node, after_set);
  DCHECK(!before_set.IsUnvisited());

  UnobservablesSet stored_for_node = unobservable_for_id(node->id());
  bool cur_set_changed =
      (stored_for_node.IsUnvisited() || stored_for_node != before_set);
  if (!cur_set_changed) {
    // We will not be able to update the part of this chain above any more.
    // Exit.
    TRACE("+ No change: stabilized. Not visiting effect inputs.");
  } else {
    unobservable_for_id(node->id()) = before_set;

    // Mark effect inputs for visiting.
    for (int i = 0; i < node->op()->EffectInputCount(); i++) {
      Node* input = NodeProperties::GetEffectInput(node, i);
      TRACE("    marking #%d:%s for revisit", input->id(),
            input->op()->mnemonic());
      MarkForRevisit(input);
    }
  }
}

// Compute the intersection of the UnobservablesSets of all effect uses and
// return it. This function only works if {node} has an effect use.
//
// The result UnobservablesSet will always be visited.
UnobservablesSet RedundantStoreFinder::RecomputeUseIntersection(Node* node) {
  // {first} == true indicates that we haven't looked at any elements yet.
  // {first} == false indicates that cur_set is the intersection of at least one
  // thing.

  bool first = true;
  UnobservablesSet cur_set = UnobservablesSet::Unvisited();  // irrelevant

  for (Edge edge : node->use_edges()) {
    // Skip non-effect edges
    if (!NodeProperties::IsEffectEdge(edge)) {
      continue;
    }

    Node* use = edge.from();
    UnobservablesSet new_set = unobservable_for_id(use->id());
    // Include new_set in the intersection.
    if (first) {
      // Intersection of a one-element set is that one element
      first = false;
      cur_set = new_set;
    } else {
      // Take the intersection of cur_set and new_set.
      cur_set = cur_set.Intersect(new_set, temp_zone());
    }
  }

  if (first) {
    // There were no effect uses.
    auto opcode = node->op()->opcode();
    // List of opcodes that may end this effect chain. The opcodes are not
    // important to the soundness of this optimization; this serves as a
    // general sanity check. Add opcodes to this list as it suits you.
    //
    // Everything is observable after these opcodes; return the empty set.
    DCHECK_EXTRA(
        opcode == IrOpcode::kReturn || opcode == IrOpcode::kTerminate ||
            opcode == IrOpcode::kDeoptimize || opcode == IrOpcode::kThrow,
        "for #%d:%s", node->id(), node->op()->mnemonic());
    USE(opcode);  // silence warning about unused variable in release mode

    return unobservables_visited_empty_;
  } else {
    if (cur_set.IsUnvisited()) {
      cur_set = unobservables_visited_empty_;
    }

    return cur_set;
  }
}

UnobservablesSet UnobservablesSet::Unvisited() { return UnobservablesSet(); }

UnobservablesSet::UnobservablesSet() : set_(nullptr) {}

UnobservablesSet UnobservablesSet::VisitedEmpty(Zone* zone) {
  // Create a new empty UnobservablesSet. This allocates in the zone, and
  // can probably be optimized to use a global singleton.
  ZoneSet<UnobservableStore>* empty_set =
      new (zone->New(sizeof(ZoneSet<UnobservableStore>)))
          ZoneSet<UnobservableStore>(zone);
  return UnobservablesSet(empty_set);
}

// Computes the intersection of two UnobservablesSets. May return
// UnobservablesSet::Unvisited() instead of an empty UnobservablesSet for
// speed.
UnobservablesSet UnobservablesSet::Intersect(const UnobservablesSet& other,
                                             Zone* zone) const {
  if (IsEmpty() || other.IsEmpty()) {
    return Unvisited();
  } else {
    ZoneSet<UnobservableStore>* intersection =
        new (zone->New(sizeof(ZoneSet<UnobservableStore>)))
            ZoneSet<UnobservableStore>(zone);
    // Put the intersection of set() and other.set() in intersection.
    set_intersection(set()->begin(), set()->end(), other.set()->begin(),
                     other.set()->end(),
                     std::inserter(*intersection, intersection->end()));

    return UnobservablesSet(intersection);
  }
}

UnobservablesSet UnobservablesSet::Add(UnobservableStore obs,
                                       Zone* zone) const {
  bool present = (set()->find(obs) != set()->end());
  if (present) {
    return *this;
  } else {
    // Make a new empty set.
    ZoneSet<UnobservableStore>* new_set =
        new (zone->New(sizeof(ZoneSet<UnobservableStore>)))
            ZoneSet<UnobservableStore>(zone);
    // Copy the old elements over.
    *new_set = *set();
    // Add the new element.
    bool inserted = new_set->insert(obs).second;
    DCHECK(inserted);
    USE(inserted);  // silence warning about unused variable

    return UnobservablesSet(new_set);
  }
}

UnobservablesSet UnobservablesSet::RemoveSameOffset(StoreOffset offset,
                                                    Zone* zone) const {
  // Make a new empty set.
  ZoneSet<UnobservableStore>* new_set =
      new (zone->New(sizeof(ZoneSet<UnobservableStore>)))
          ZoneSet<UnobservableStore>(zone);
  // Copy all elements over that have a different offset.
  for (auto obs : *set()) {
    if (obs.offset_ != offset) {
      new_set->insert(obs);
    }
  }

  return UnobservablesSet(new_set);
}

// Used for debugging.
bool UnobservablesSet::operator==(const UnobservablesSet& other) const {
  if (IsUnvisited() || other.IsUnvisited()) {
    return IsEmpty() && other.IsEmpty();
  } else {
    // Both pointers guaranteed not to be nullptrs.
    return *set() == *other.set();
  }
}

bool UnobservablesSet::operator!=(const UnobservablesSet& other) const {
  return !(*this == other);
}

bool UnobservableStore::operator==(const UnobservableStore other) const {
  return (id_ == other.id_) && (offset_ == other.offset_);
}


bool UnobservableStore::operator<(const UnobservableStore other) const {
  return (id_ < other.id_) || (id_ == other.id_ && offset_ < other.offset_);
}

#undef TRACE
#undef CHECK_EXTRA
#undef DCHECK_EXTRA

}  // namespace compiler
}  // namespace internal
}  // namespace v8