store-store-elimination.cc 20.9 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 9 10
#include "src/compiler/all-nodes.h"
#include "src/compiler/js-graph.h"
#include "src/compiler/node-properties.h"
11
#include "src/compiler/persistent-map.h"
12 13
#include "src/compiler/simplified-operator.h"
#include "src/zone/zone-containers.h"
14 15 16 17 18

namespace v8 {
namespace internal {
namespace compiler {

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

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

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

45 46 47 48 49 50 51
namespace {

using StoreOffset = uint32_t;

struct UnobservableStore {
  NodeId id_;
  StoreOffset offset_;
52
  bool maybe_gc_observable_ = false;
53 54 55 56 57 58 59 60 61 62

  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
 private:
79 80 81 82 83 84
  enum ObservableState {
    kObservable = 0,    // We haven't seen a store to this offset before.
    kUnobservable = 1,  // Stores to the same offset can be eliminated.
    kGCObservable = 2   // Stores to the same offset can only be eliminated,
                        // if they are not initializing or transitioning.
  };
85

86 87
  using KeyT = UnobservableStore;
  using ValueT = ObservableState;
88

89
 public:
90 91
  using SetT = PersistentMap<KeyT, ValueT>;

92 93 94 95 96 97 98
  // 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;
99 100
  UnobservablesSet& operator=(const UnobservablesSet& other)
      V8_NOEXCEPT = default;
101

102 103 104 105
  // Computes the intersection of two states.
  ObservableState Intersect(const ObservableState state1,
                            const ObservableState state2) const;

106 107 108 109 110 111
  // 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
112
  // as parameter. If said obs it's already unobservable, we don't have to
113 114 115 116 117 118 119 120 121
  // 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
122
  // alias one another, and currently we don't have the means to know if
123 124 125
  // two nodes are definitely the same value.
  UnobservablesSet RemoveSameOffset(StoreOffset off, Zone* zone) const;

126 127 128 129
  // Returns a new set where all observations are marked as being observable
  // by GC.
  UnobservablesSet MarkGCObservable(Zone* zone) const;

130
  const SetT* set() const { return set_; }
131 132

  bool IsUnvisited() const { return set_ == nullptr; }
133 134 135
  bool IsEmpty() const {
    return set_ == nullptr || set_->begin() == set_->end();
  }
136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158

  // We need to guarantee that objects are fully initialized and fields are in
  // sync with their map when a GC is triggered (potentially by any allocation).
  // Therefore initializing or transitioning stores are observable if they are
  // observable by GC. All other stores are not relevant for correct GC
  // behaviour and can be eliminated even if they are observable by GC.
  bool IsUnobservable(UnobservableStore obs,
                      bool maybe_initializing_or_transitioning) const {
    if (set_ == nullptr) return false;
    ObservableState state = set_->Get(obs);
    switch (state) {
      case kUnobservable:
        return true;
      case kObservable:
        return false;
      case kGCObservable:
        return !maybe_initializing_or_transitioning;
    }
    UNREACHABLE();
  }

  bool IsGCObservable(UnobservableStore obs) const {
    return set_ != nullptr && set_->Get(obs) == kGCObservable;
159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174
  }

  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:
175 176 177 178
  UnobservablesSet() = default;
  explicit UnobservablesSet(const SetT* set) : set_(set) {}

  static SetT* NewSet(Zone* zone) {
179
    return zone->New<UnobservablesSet::SetT>(zone, kObservable);
180 181
  }

182 183 184
  static void SetAdd(SetT* set, const KeyT& key) {
    set->Set(key, kUnobservable);
  }
185
  static void SetErase(SetT* set, const KeyT& key) {
186 187 188 189
    set->Set(key, kObservable);
  }
  static void SetGCObservable(SetT* set, const KeyT& key) {
    set->Set(key, kGCObservable);
190 191 192
  }

  const SetT* set_ = nullptr;
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 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275
};

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() {
276 277 278
  Visit(jsgraph()->graph()->end());

  while (!revisit_.empty()) {
279
    tick_counter_->TickAndMaybeEnterSafepoint();
280 281 282 283 284 285 286 287 288 289 290 291 292 293
    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());
294 295
    }
  }
296
#endif
297 298
}

299
void RedundantStoreFinder::MarkForRevisit(Node* node) {
300 301 302 303 304
  DCHECK_LT(node->id(), in_revisit_.size());
  if (!in_revisit_[node->id()]) {
    revisit_.push(node);
    in_revisit_[node->id()] = true;
  }
305 306
}

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

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

319
      UnobservableStore observation = {stored_to->id(), offset};
320 321
      const bool is_not_observable = uses.IsUnobservable(
          observation, access.maybe_initializing_or_transitioning_store);
322

323
      if (is_not_observable) {
324 325
        TRACE("  #%d is StoreField[+%d,%s](#%d), unobservable", node->id(),
              offset, MachineReprToString(access.machine_type.representation()),
326 327 328
              stored_to->id());
        to_remove().insert(node);
        return uses;
329
      } else {
330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352
        const bool is_gc_observable =
            access.maybe_initializing_or_transitioning_store &&
            uses.IsGCObservable(observation);
        // A GC observable store could have been unobservable in a previous
        // visit. This is possible if the node that previously shadowed the
        // initializing store is now unobservable, due to additional stores
        // added to the unobservables set. Example:
        //            StoreA --> StoreB (init)
        //               ^
        //               |
        // PathX --> Allocate <-- StoreC <-- PathY
        // When traversing PathX, StoreA will shadow StoreB and we will
        // eliminate StoreB. When traversing PathY, StoreA will be shadowed by
        // StoreC and we will eliminate StoreA, but StoreB is now observable by
        // GC and should not be eliminated.
        if (is_gc_observable) {
          to_remove().erase(node);
        }
        TRACE(
            "  #%d is StoreField[+%d,%s](#%d), observable%s, recording in set",
            node->id(), offset,
            MachineReprToString(access.machine_type.representation()),
            stored_to->id(), is_gc_observable ? " by GC" : "");
353 354 355 356 357
        return uses.Add(observation, temp_zone());
      }
    }
    case IrOpcode::kLoadField: {
      Node* loaded_from = node->InputAt(0);
358
      const FieldAccess& access = FieldAccessOf(node->op());
359 360 361 362 363 364 365 366 367 368 369
      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());
    }
370 371 372 373 374 375 376 377 378 379 380
    case IrOpcode::kAllocate:
    case IrOpcode::kAllocateRaw: {
      // Allocations can trigger a GC, therefore stores observable by allocation
      // can not be eliminated, if they are initializing or tranisitioning
      // stores.
      TRACE(
          "  #%d is Allocate or AllocateRaw, marking recorded offsets as "
          "observable by GC",
          node->id());
      return uses.MarkGCObservable(temp_zone());
    }
381 382 383 384 385 386
    default:
      if (CannotObserveStoreField(node)) {
        TRACE("  #%d:%s can observe nothing, set stays unchanged", node->id(),
              node->op()->mnemonic());
        return uses;
      } else {
387 388
        TRACE("  #%d:%s might observe anything, recording empty set",
              node->id(), node->op()->mnemonic());
389 390 391 392
        return unobservables_visited_empty_;
      }
  }
  UNREACHABLE();
393 394
}

395
bool RedundantStoreFinder::CannotObserveStoreField(Node* node) {
396 397
  IrOpcode::Value opcode = node->opcode();
  return opcode == IrOpcode::kLoadElement || opcode == IrOpcode::kLoad ||
398 399
         opcode == IrOpcode::kLoadImmutable || opcode == IrOpcode::kStore ||
         opcode == IrOpcode::kEffectPhi || opcode == IrOpcode::kStoreElement ||
400
         opcode == IrOpcode::kRetain;
401 402
}

403
void RedundantStoreFinder::Visit(Node* node) {
404 405 406 407 408 409 410 411 412
  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);
      }
    }
  }

413 414
  bool is_effectful = node->op()->EffectInputCount() >= 1;
  if (is_effectful) {
415
    // mark all effect inputs for revisiting (if they might have stale state).
416 417
    VisitEffectfulNode(node);
    DCHECK(HasBeenVisited(node));
418
  } else if (!HasBeenVisited(node)) {
419 420 421 422
    // Mark as visited.
    unobservable_for_id(node->id()) = unobservables_visited_empty_;
  }
}
423

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

432
  UnobservablesSet stores_for_node = unobservable_for_id(node->id());
433
  bool cur_set_changed =
434
      stores_for_node.IsUnvisited() || stores_for_node != before_set;
435 436 437 438 439 440 441 442 443 444
  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);
445 446 447
      TRACE("    marking #%d:%s for revisit", input->id(),
            input->op()->mnemonic());
      MarkForRevisit(input);
448 449
    }
  }
450 451
}

452
UnobservablesSet RedundantStoreFinder::RecomputeUseIntersection(Node* node) {
453
  // There were no effect uses. Break early.
454 455 456 457
  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
458
    // general check. Add opcodes to this list as it suits you.
459 460 461 462
    //
    // Everything is observable after these opcodes; return the empty set.
    DCHECK_EXTRA(
        opcode == IrOpcode::kReturn || opcode == IrOpcode::kTerminate ||
463 464
            opcode == IrOpcode::kDeoptimize || opcode == IrOpcode::kThrow ||
            opcode == IrOpcode::kTailCall,
465 466 467 468 469 470
        "for #%d:%s", node->id(), node->op()->mnemonic());
    USE(opcode);

    return unobservables_visited_empty_;
  }

471 472 473 474
  // {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;
475
  UnobservablesSet cur_set = UnobservablesSet::Unvisited();  // irrelevant
476 477 478 479
  for (Edge edge : node->use_edges()) {
    if (!NodeProperties::IsEffectEdge(edge)) {
      continue;
    }
480

481
    // Intersect with the new use node.
482
    Node* use = edge.from();
483
    UnobservablesSet new_set = unobservable_for_id(use->id());
484 485 486
    if (first) {
      first = false;
      cur_set = new_set;
487 488 489
      if (cur_set.IsUnvisited()) {
        cur_set = unobservables_visited_empty_;
      }
490
    } else {
491 492
      cur_set =
          cur_set.Intersect(new_set, unobservables_visited_empty_, temp_zone());
493
    }
494

495 496 497
    // Break fast for the empty set since the intersection will always be empty.
    if (cur_set.IsEmpty()) {
      break;
498 499
    }
  }
500

501 502 503
  DCHECK(!cur_set.IsUnvisited());
  return cur_set;
}
504

505
UnobservablesSet UnobservablesSet::VisitedEmpty(Zone* zone) {
506
  return UnobservablesSet(NewSet(zone));
507
}
508

509 510 511 512 513 514 515 516 517 518
UnobservablesSet::ObservableState UnobservablesSet::Intersect(
    const ObservableState state1, const ObservableState state2) const {
  if (state1 == state2) return state1;
  if (state1 == kObservable || state2 == kObservable) return kObservable;
  if (state1 == kGCObservable || state2 == kGCObservable) {
    return kGCObservable;
  }
  UNREACHABLE();
}

519 520 521
UnobservablesSet UnobservablesSet::Intersect(const UnobservablesSet& other,
                                             const UnobservablesSet& empty,
                                             Zone* zone) const {
522 523 524
  if (IsEmpty() || other.IsEmpty()) return empty;

  UnobservablesSet::SetT* intersection = NewSet(zone);
525
  for (auto triple : set()->Zip(*other.set())) {
526 527 528
    ObservableState new_state =
        Intersect(std::get<1>(triple), std::get<2>(triple));
    intersection->Set(std::get<0>(triple), new_state);
529
  }
530 531

  return UnobservablesSet(intersection);
532
}
533

534 535
UnobservablesSet UnobservablesSet::Add(UnobservableStore obs,
                                       Zone* zone) const {
536
  if (set()->Get(obs) == kUnobservable) return *this;
537 538 539 540 541 542

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

  return UnobservablesSet(new_set);
543
}
544

545 546
UnobservablesSet UnobservablesSet::RemoveSameOffset(StoreOffset offset,
                                                    Zone* zone) const {
547 548 549 550
  UnobservablesSet::SetT* new_set = NewSet(zone);
  *new_set = *set();

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

556 557 558
  return UnobservablesSet(new_set);
}

559 560 561 562 563 564 565 566 567 568 569 570 571
UnobservablesSet UnobservablesSet::MarkGCObservable(Zone* zone) const {
  UnobservablesSet::SetT* new_set = NewSet(zone);
  *new_set = *set();

  // Mark all elements as observable by GC.
  for (auto entry : *new_set) {
    const UnobservableStore& obs = entry.first;
    SetGCObservable(new_set, obs);
  }

  return UnobservablesSet(new_set);
}

572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591
}  // 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();
  }
592
}
593

594 595 596 597
#undef TRACE
#undef CHECK_EXTRA
#undef DCHECK_EXTRA

598 599 600
}  // namespace compiler
}  // namespace internal
}  // namespace v8