1// Copyright 2016 the V8 project authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5#ifndef V8_COMPILER_REDUNDANCY_ELIMINATION_H_
6#define V8_COMPILER_REDUNDANCY_ELIMINATION_H_
7
8#include "src/compiler/graph-reducer.h"
9
10namespace v8 {
11namespace internal {
12namespace compiler {
13
14class V8_EXPORT_PRIVATE RedundancyElimination final : public AdvancedReducer {
15 public:
16  RedundancyElimination(Editor* editor, Zone* zone);
17  ~RedundancyElimination() final;
18  RedundancyElimination(const RedundancyElimination&) = delete;
19  RedundancyElimination& operator=(const RedundancyElimination&) = delete;
20
21  const char* reducer_name() const override { return "RedundancyElimination"; }
22
23  Reduction Reduce(Node* node) final;
24
25 private:
26  struct Check {
27    Check(Node* node, Check* next) : node(node), next(next) {}
28    Node* node;
29    Check* next;
30  };
31
32  class EffectPathChecks final {
33   public:
34    static EffectPathChecks* Copy(Zone* zone, EffectPathChecks const* checks);
35    static EffectPathChecks const* Empty(Zone* zone);
36    bool Equals(EffectPathChecks const* that) const;
37    void Merge(EffectPathChecks const* that);
38
39    EffectPathChecks const* AddCheck(Zone* zone, Node* node) const;
40    Node* LookupCheck(Node* node) const;
41    Node* LookupBoundsCheckFor(Node* node) const;
42
43   private:
44    friend Zone;
45
46    EffectPathChecks(Check* head, size_t size) : head_(head), size_(size) {}
47
48    // We keep track of the list length so that we can find the longest
49    // common tail easily.
50    Check* head_;
51    size_t size_;
52  };
53
54  class PathChecksForEffectNodes final {
55   public:
56    explicit PathChecksForEffectNodes(Zone* zone) : info_for_node_(zone) {}
57    EffectPathChecks const* Get(Node* node) const;
58    void Set(Node* node, EffectPathChecks const* checks);
59
60   private:
61    ZoneVector<EffectPathChecks const*> info_for_node_;
62  };
63
64  Reduction ReduceCheckNode(Node* node);
65  Reduction ReduceEffectPhi(Node* node);
66  Reduction ReduceSpeculativeNumberComparison(Node* node);
67  Reduction ReduceSpeculativeNumberOperation(Node* node);
68  Reduction ReduceStart(Node* node);
69  Reduction ReduceOtherNode(Node* node);
70
71  Reduction TakeChecksFromFirstEffect(Node* node);
72  Reduction UpdateChecks(Node* node, EffectPathChecks const* checks);
73
74  Zone* zone() const { return zone_; }
75
76  PathChecksForEffectNodes node_checks_;
77  Zone* const zone_;
78};
79
80}  // namespace compiler
81}  // namespace internal
82}  // namespace v8
83
84#endif  // V8_COMPILER_REDUNDANCY_ELIMINATION_H_
85