store-store-elimination.cc 17.7 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
  // 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;
97 98
  UnobservablesSet& operator=(const UnobservablesSet& other)
      V8_NOEXCEPT = default;
99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119

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

120
  const SetT* set() const { return set_; }
121 122

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

  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:
144 145 146 147
  UnobservablesSet() = default;
  explicit UnobservablesSet(const SetT* set) : set_(set) {}

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

  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;
157 158
};

159 160 161 162 163
// 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;

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 243 244
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() {
245 246 247
  Visit(jsgraph()->graph()->end());

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

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

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

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

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

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

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

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

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

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

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

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

    return unobservables_visited_empty_;
  }

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

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

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

439 440 441
  DCHECK(!cur_set.IsUnvisited());
  return cur_set;
}
442

443
UnobservablesSet UnobservablesSet::VisitedEmpty(Zone* zone) {
444
  return UnobservablesSet(NewSet(zone));
445
}
446

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

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

  return UnobservablesSet(intersection);
460
}
461

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

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

  return UnobservablesSet(new_set);
471
}
472

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

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

484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506
  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();
  }
507
}
508

509 510 511 512
#undef TRACE
#undef CHECK_EXTRA
#undef DCHECK_EXTRA

513 514 515
}  // namespace compiler
}  // namespace internal
}  // namespace v8