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 RedundancyElimination final : public AdvancedReducer {
15 public:
16  RedundancyElimination(Editor* editor, Zone* zone);
17  ~RedundancyElimination() final;
18
19  Reduction Reduce(Node* node) final;
20
21 private:
22  struct Check {
23    Check(Node* node, Check* next) : node(node), next(next) {}
24    Node* node;
25    Check* next;
26  };
27
28  class EffectPathChecks final {
29   public:
30    static EffectPathChecks* Copy(Zone* zone, EffectPathChecks const* checks);
31    static EffectPathChecks const* Empty(Zone* zone);
32    bool Equals(EffectPathChecks const* that) const;
33    void Merge(EffectPathChecks const* that);
34
35    EffectPathChecks const* AddCheck(Zone* zone, Node* node) const;
36    Node* LookupCheck(Node* node) const;
37    Node* LookupBoundsCheckFor(Node* node) const;
38
39   private:
40    EffectPathChecks(Check* head, size_t size) : head_(head), size_(size) {}
41
42    // We keep track of the list length so that we can find the longest
43    // common tail easily.
44    Check* head_;
45    size_t size_;
46  };
47
48  class PathChecksForEffectNodes final {
49   public:
50    explicit PathChecksForEffectNodes(Zone* zone) : info_for_node_(zone) {}
51    EffectPathChecks const* Get(Node* node) const;
52    void Set(Node* node, EffectPathChecks const* checks);
53
54   private:
55    ZoneVector<EffectPathChecks const*> info_for_node_;
56  };
57
58  Reduction ReduceCheckNode(Node* node);
59  Reduction ReduceEffectPhi(Node* node);
60  Reduction ReduceStart(Node* node);
61  Reduction ReduceOtherNode(Node* node);
62
63  Reduction TakeChecksFromFirstEffect(Node* node);
64  Reduction UpdateChecks(Node* node, EffectPathChecks const* checks);
65
66  Reduction TryReuseBoundsCheckForFirstInput(Node* node);
67
68  Zone* zone() const { return zone_; }
69
70  PathChecksForEffectNodes node_checks_;
71  Zone* const zone_;
72
73  DISALLOW_COPY_AND_ASSIGN(RedundancyElimination);
74};
75
76}  // namespace compiler
77}  // namespace internal
78}  // namespace v8
79
80#endif  // V8_COMPILER_REDUNDANCY_ELIMINATION_H_
81