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