store-store-elimination.cc 17.6 KB
Newer Older
1 2 3 4 5 6
// 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 "src/compiler/store-store-elimination.h"

7
#include "src/codegen/tick-counter.h"
8
#include "src/compiler/all-nodes.h"
9
#include "src/compiler/common-operator.h"
10 11
#include "src/compiler/js-graph.h"
#include "src/compiler/node-properties.h"
12
#include "src/compiler/persistent-map.h"
13 14
#include "src/compiler/simplified-operator.h"
#include "src/zone/zone-containers.h"
15 16 17 18 19

namespace v8 {
namespace internal {
namespace compiler {

20 21 22 23 24
#define TRACE(fmt, ...)                                         \
  do {                                                          \
    if (FLAG_trace_store_elimination) {                         \
      PrintF("RedundantStoreFinder: " fmt "\n", ##__VA_ARGS__); \
    }                                                           \
25 26
  } while (false)

27 28 29 30 31
// 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.
32 33 34 35 36
#define CHECK_EXTRA(condition, fmt, ...)                                      \
  do {                                                                        \
    if (V8_UNLIKELY(!(condition))) {                                          \
      FATAL("Check failed: %s. Extra info: " fmt, #condition, ##__VA_ARGS__); \
    }                                                                         \
37
  } while (false)
38 39 40 41 42 43 44 45

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

46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62
namespace {

using StoreOffset = uint32_t;

struct UnobservableStore {
  NodeId id_;
  StoreOffset offset_;

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

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

63 64 65 66
size_t hash_value(const UnobservableStore& p) {
  return base::hash_combine(p.id_, p.offset_);
}

67 68 69 70 71 72 73 74 75 76 77
// 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 {
78 79 80 81 82 83 84 85 86
 private:
  using KeyT = UnobservableStore;
  using ValueT = bool;  // Emulates set semantics in the map.

  // The PersistentMap uses a special value to signify 'not present'. We use
  // a boolean value to emulate set semantics.
  static constexpr ValueT kNotPresent = false;
  static constexpr ValueT kPresent = true;

87
 public:
88 89
  using SetT = PersistentMap<KeyT, ValueT>;

90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117
  // Creates a new UnobservablesSet, with the null set.
  static UnobservablesSet Unvisited() { return UnobservablesSet(); }

  // Create a new empty UnobservablesSet. This allocates in the zone, and
  // can probably be optimized to use a global singleton.
  static UnobservablesSet VisitedEmpty(Zone* zone);
  UnobservablesSet(const UnobservablesSet& other) V8_NOEXCEPT = default;

  // Computes the intersection of two UnobservablesSets. If one of the sets is
  // empty, will return empty.
  UnobservablesSet Intersect(const UnobservablesSet& other,
                             const UnobservablesSet& empty, Zone* zone) const;

  // Returns a set that it is the current one, plus the observation obs passed
  // as parameter. If said obs it's already in the set, we don't have to
  // create a new one.
  UnobservablesSet Add(UnobservableStore obs, Zone* zone) const;

  // Returns a set that it is the current one, except for all of the
  // observations with offset off. This is done by creating a new set and
  // copying all observations with different offsets.
  // This can probably be done better if the observations are stored first by
  // offset and then by node.
  // We are removing all nodes with offset off since different nodes may
  // alias one another, and we currently we don't have the means to know if
  // two nodes are definitely the same value.
  UnobservablesSet RemoveSameOffset(StoreOffset off, Zone* zone) const;

118
  const SetT* set() const { return set_; }
119 120

  bool IsUnvisited() const { return set_ == nullptr; }
121 122 123
  bool IsEmpty() const {
    return set_ == nullptr || set_->begin() == set_->end();
  }
124
  bool Contains(UnobservableStore obs) const {
125
    return set_ != nullptr && set_->Get(obs) != kNotPresent;
126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141
  }

  bool 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 operator!=(const UnobservablesSet& other) const {
    return !(*this == other);
  }

 private:
142 143 144 145
  UnobservablesSet() = default;
  explicit UnobservablesSet(const SetT* set) : set_(set) {}

  static SetT* NewSet(Zone* zone) {
146
    return zone->New<UnobservablesSet::SetT>(zone, kNotPresent);
147 148 149 150 151 152 153 154
  }

  static void SetAdd(SetT* set, const KeyT& key) { set->Set(key, kPresent); }
  static void SetErase(SetT* set, const KeyT& key) {
    set->Set(key, kNotPresent);
  }

  const SetT* set_ = nullptr;
155 156
};

157 158 159 160 161
// These definitions are here in order to please the linker, which in debug mode
// sometimes requires static constants to be defined in .cc files.
constexpr UnobservablesSet::ValueT UnobservablesSet::kNotPresent;
constexpr UnobservablesSet::ValueT UnobservablesSet::kPresent;

162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242
class RedundantStoreFinder final {
 public:
  // Note that we Initialize unobservable_ with js_graph->graph->NodeCount()
  // amount of empty sets.
  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)) {}

  // Crawls from the end of the graph to the beginning, with the objective of
  // finding redundant stores.
  void Find();

  // This method is used for const correctness to go through the final list of
  // redundant stores that are replaced on the graph.
  const ZoneSet<Node*>& to_remove_const() { return to_remove_; }

 private:
  // Assumption: All effectful nodes are reachable from End via a sequence of
  // control, then a sequence of effect edges.
  // Visit goes through the control chain, visiting effectful nodes that it
  // encounters.
  void Visit(Node* node);

  // Marks effect inputs for visiting, if we are able to update this path of
  // the graph.
  void VisitEffectfulNode(Node* node);

  // Compute the intersection of the UnobservablesSets of all effect uses and
  // return it.
  // The result UnobservablesSet will never be null.
  UnobservablesSet RecomputeUseIntersection(Node* node);

  // Recompute unobservables-set for a node. Will also mark superfluous nodes
  // as to be removed.
  UnobservablesSet RecomputeSet(Node* node, const UnobservablesSet& uses);

  // Returns true if node's opcode cannot observe StoreFields.
  static bool CannotObserveStoreField(Node* node);

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

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

  JSGraph* jsgraph() const { return jsgraph_; }
  Isolate* isolate() { return jsgraph()->isolate(); }
  Zone* temp_zone() const { return temp_zone_; }
  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_;
};

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

  while (!revisit_.empty()) {
246
    tick_counter_->TickAndMaybeEnterSafepoint();
247 248 249 250 251 252 253 254 255 256 257 258 259 260
    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());
261 262
    }
  }
263
#endif
264 265
}

266
void RedundantStoreFinder::MarkForRevisit(Node* node) {
267 268 269 270 271
  DCHECK_LT(node->id(), in_revisit_.size());
  if (!in_revisit_[node->id()]) {
    revisit_.push(node);
    in_revisit_[node->id()] = true;
  }
272 273
}

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

278 279
UnobservablesSet RedundantStoreFinder::RecomputeSet(
    Node* node, const UnobservablesSet& uses) {
280 281 282
  switch (node->op()->opcode()) {
    case IrOpcode::kStoreField: {
      Node* stored_to = node->InputAt(0);
283
      const FieldAccess& access = FieldAccessOf(node->op());
284 285 286
      StoreOffset offset = ToOffset(access);

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

289
      if (is_not_observable) {
290 291 292 293 294
        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;
295
      } else {
296 297 298 299 300 301 302 303 304
        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());
      }
    }
    case IrOpcode::kLoadField: {
      Node* loaded_from = node->InputAt(0);
305
      const FieldAccess& access = FieldAccessOf(node->op());
306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322
      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());
    }
    default:
      if (CannotObserveStoreField(node)) {
        TRACE("  #%d:%s can observe nothing, set stays unchanged", node->id(),
              node->op()->mnemonic());
        return uses;
      } else {
323 324
        TRACE("  #%d:%s might observe anything, recording empty set",
              node->id(), node->op()->mnemonic());
325 326 327 328
        return unobservables_visited_empty_;
      }
  }
  UNREACHABLE();
329 330
}

331
bool RedundantStoreFinder::CannotObserveStoreField(Node* node) {
332 333 334 335 336
  IrOpcode::Value opcode = node->opcode();
  return opcode == IrOpcode::kLoadElement || opcode == IrOpcode::kLoad ||
         opcode == IrOpcode::kStore || opcode == IrOpcode::kEffectPhi ||
         opcode == IrOpcode::kStoreElement ||
         opcode == IrOpcode::kUnsafePointerAdd || opcode == IrOpcode::kRetain;
337 338
}

339
void RedundantStoreFinder::Visit(Node* node) {
340 341 342 343 344 345 346 347 348
  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);
      }
    }
  }

349 350
  bool is_effectful = node->op()->EffectInputCount() >= 1;
  if (is_effectful) {
351
    // mark all effect inputs for revisiting (if they might have stale state).
352 353
    VisitEffectfulNode(node);
    DCHECK(HasBeenVisited(node));
354
  } else if (!HasBeenVisited(node)) {
355 356 357 358
    // Mark as visited.
    unobservable_for_id(node->id()) = unobservables_visited_empty_;
  }
}
359

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

368
  UnobservablesSet stores_for_node = unobservable_for_id(node->id());
369
  bool cur_set_changed =
370
      stores_for_node.IsUnvisited() || stores_for_node != before_set;
371 372 373 374 375 376 377 378 379 380
  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);
381 382 383
      TRACE("    marking #%d:%s for revisit", input->id(),
            input->op()->mnemonic());
      MarkForRevisit(input);
384 385
    }
  }
386 387
}

388
UnobservablesSet RedundantStoreFinder::RecomputeUseIntersection(Node* node) {
389
  // There were no effect uses. Break early.
390 391 392 393
  if (node->op()->EffectOutputCount() == 0) {
    IrOpcode::Value opcode = node->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
394
    // general check. Add opcodes to this list as it suits you.
395 396 397 398
    //
    // Everything is observable after these opcodes; return the empty set.
    DCHECK_EXTRA(
        opcode == IrOpcode::kReturn || opcode == IrOpcode::kTerminate ||
399 400
            opcode == IrOpcode::kDeoptimize || opcode == IrOpcode::kThrow ||
            opcode == IrOpcode::kTailCall,
401 402 403 404 405 406
        "for #%d:%s", node->id(), node->op()->mnemonic());
    USE(opcode);

    return unobservables_visited_empty_;
  }

407 408 409 410
  // {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;
411
  UnobservablesSet cur_set = UnobservablesSet::Unvisited();  // irrelevant
412 413 414 415
  for (Edge edge : node->use_edges()) {
    if (!NodeProperties::IsEffectEdge(edge)) {
      continue;
    }
416

417
    // Intersect with the new use node.
418
    Node* use = edge.from();
419
    UnobservablesSet new_set = unobservable_for_id(use->id());
420 421 422
    if (first) {
      first = false;
      cur_set = new_set;
423 424 425
      if (cur_set.IsUnvisited()) {
        cur_set = unobservables_visited_empty_;
      }
426
    } else {
427 428
      cur_set =
          cur_set.Intersect(new_set, unobservables_visited_empty_, temp_zone());
429
    }
430

431 432 433
    // Break fast for the empty set since the intersection will always be empty.
    if (cur_set.IsEmpty()) {
      break;
434 435
    }
  }
436

437 438 439
  DCHECK(!cur_set.IsUnvisited());
  return cur_set;
}
440

441
UnobservablesSet UnobservablesSet::VisitedEmpty(Zone* zone) {
442
  return UnobservablesSet(NewSet(zone));
443
}
444

445 446 447
UnobservablesSet UnobservablesSet::Intersect(const UnobservablesSet& other,
                                             const UnobservablesSet& empty,
                                             Zone* zone) const {
448 449 450 451 452 453 454
  if (IsEmpty() || other.IsEmpty()) return empty;

  UnobservablesSet::SetT* intersection = NewSet(zone);
  for (const auto& triple : set()->Zip(*other.set())) {
    if (std::get<1>(triple) && std::get<2>(triple)) {
      intersection->Set(std::get<0>(triple), kPresent);
    }
455
  }
456 457

  return UnobservablesSet(intersection);
458
}
459

460 461
UnobservablesSet UnobservablesSet::Add(UnobservableStore obs,
                                       Zone* zone) const {
462 463 464 465 466 467 468
  if (set()->Get(obs) != kNotPresent) return *this;

  UnobservablesSet::SetT* new_set = NewSet(zone);
  *new_set = *set();
  SetAdd(new_set, obs);

  return UnobservablesSet(new_set);
469
}
470

471 472
UnobservablesSet UnobservablesSet::RemoveSameOffset(StoreOffset offset,
                                                    Zone* zone) const {
473 474 475 476 477 478 479
  UnobservablesSet::SetT* new_set = NewSet(zone);
  *new_set = *set();

  // Remove elements with the given offset.
  for (const auto& entry : *new_set) {
    const UnobservableStore& obs = entry.first;
    if (obs.offset_ == offset) SetErase(new_set, obs);
480 481
  }

482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504
  return UnobservablesSet(new_set);
}

}  // namespace

// static
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();
  }
505
}
506

507 508 509 510
#undef TRACE
#undef CHECK_EXTRA
#undef DCHECK_EXTRA

511 512 513
}  // namespace compiler
}  // namespace internal
}  // namespace v8