1// Copyright 2013 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_CRANKSHAFT_HYDROGEN_GVN_H_
6#define V8_CRANKSHAFT_HYDROGEN_GVN_H_
7
8#include <iosfwd>
9
10#include "src/crankshaft/hydrogen-instructions.h"
11#include "src/crankshaft/hydrogen.h"
12#include "src/zone/zone.h"
13
14namespace v8 {
15namespace internal {
16
17// This class extends GVNFlagSet with additional "special" dynamic side effects,
18// which can be used to represent side effects that cannot be expressed using
19// the GVNFlags of an HInstruction. These special side effects are tracked by a
20// SideEffectsTracker (see below).
21class SideEffects final {
22 public:
23  static const int kNumberOfSpecials = 64 - kNumberOfFlags;
24
25  SideEffects() : bits_(0) {
26    DCHECK(kNumberOfFlags + kNumberOfSpecials == sizeof(bits_) * CHAR_BIT);
27  }
28  explicit SideEffects(GVNFlagSet flags) : bits_(flags.ToIntegral()) {}
29  bool IsEmpty() const { return bits_ == 0; }
30  bool ContainsFlag(GVNFlag flag) const {
31    return (bits_ & MaskFlag(flag)) != 0;
32  }
33  bool ContainsSpecial(int special) const {
34    return (bits_ & MaskSpecial(special)) != 0;
35  }
36  bool ContainsAnyOf(SideEffects set) const { return (bits_ & set.bits_) != 0; }
37  void Add(SideEffects set) { bits_ |= set.bits_; }
38  void AddSpecial(int special) { bits_ |= MaskSpecial(special); }
39  void RemoveFlag(GVNFlag flag) { bits_ &= ~MaskFlag(flag); }
40  void RemoveAll() { bits_ = 0; }
41  uint64_t ToIntegral() const { return bits_; }
42
43 private:
44  uint64_t MaskFlag(GVNFlag flag) const {
45    return static_cast<uint64_t>(1) << static_cast<unsigned>(flag);
46  }
47  uint64_t MaskSpecial(int special) const {
48    DCHECK(special >= 0);
49    DCHECK(special < kNumberOfSpecials);
50    return static_cast<uint64_t>(1) << static_cast<unsigned>(
51        special + kNumberOfFlags);
52  }
53
54  uint64_t bits_;
55};
56
57
58struct TrackedEffects;
59
60// Tracks global variable and inobject field loads/stores in a fine grained
61// fashion, and represents them using the "special" dynamic side effects of the
62// SideEffects class (see above). This way unrelated global variable/inobject
63// field stores don't prevent hoisting and merging of global variable/inobject
64// field loads.
65class SideEffectsTracker final BASE_EMBEDDED {
66 public:
67  SideEffectsTracker() : num_global_vars_(0), num_inobject_fields_(0) {}
68  SideEffects ComputeChanges(HInstruction* instr);
69  SideEffects ComputeDependsOn(HInstruction* instr);
70
71 private:
72  friend std::ostream& operator<<(std::ostream& os, const TrackedEffects& f);
73  bool ComputeGlobalVar(Unique<PropertyCell> cell, int* index);
74  bool ComputeInobjectField(HObjectAccess access, int* index);
75
76  static int GlobalVar(int index) {
77    DCHECK(index >= 0);
78    DCHECK(index < kNumberOfGlobalVars);
79    return index;
80  }
81  static int InobjectField(int index) {
82    DCHECK(index >= 0);
83    DCHECK(index < kNumberOfInobjectFields);
84    return index + kNumberOfGlobalVars;
85  }
86
87  // Track up to four global vars.
88  static const int kNumberOfGlobalVars = 4;
89  Unique<PropertyCell> global_vars_[kNumberOfGlobalVars];
90  int num_global_vars_;
91
92  // Track up to n inobject fields.
93  static const int kNumberOfInobjectFields =
94      SideEffects::kNumberOfSpecials - kNumberOfGlobalVars;
95  HObjectAccess inobject_fields_[kNumberOfInobjectFields];
96  int num_inobject_fields_;
97};
98
99
100// Helper class for printing, because the effects don't know their tracker.
101struct TrackedEffects {
102  TrackedEffects(SideEffectsTracker* t, SideEffects e)
103      : tracker(t), effects(e) {}
104  SideEffectsTracker* tracker;
105  SideEffects effects;
106};
107
108
109std::ostream& operator<<(std::ostream& os, const TrackedEffects& f);
110
111
112// Perform common subexpression elimination and loop-invariant code motion.
113class HGlobalValueNumberingPhase final : public HPhase {
114 public:
115  explicit HGlobalValueNumberingPhase(HGraph* graph);
116
117  void Run();
118
119 private:
120  SideEffects CollectSideEffectsOnPathsToDominatedBlock(
121      HBasicBlock* dominator,
122      HBasicBlock* dominated);
123  void AnalyzeGraph();
124  void ComputeBlockSideEffects();
125  void LoopInvariantCodeMotion();
126  void ProcessLoopBlock(HBasicBlock* block,
127                        HBasicBlock* before_loop,
128                        SideEffects loop_kills);
129  bool ShouldMove(HInstruction* instr, HBasicBlock* loop_header);
130  TrackedEffects Print(SideEffects side_effects) {
131    return TrackedEffects(&side_effects_tracker_, side_effects);
132  }
133
134  SideEffectsTracker side_effects_tracker_;
135  bool removed_side_effects_;
136
137  // A map of block IDs to their side effects.
138  ZoneList<SideEffects> block_side_effects_;
139
140  // A map of loop header block IDs to their loop's side effects.
141  ZoneList<SideEffects> loop_side_effects_;
142
143  // Used when collecting side effects on paths from dominator to
144  // dominated.
145  BitVector visited_on_paths_;
146
147  DISALLOW_COPY_AND_ASSIGN(HGlobalValueNumberingPhase);
148};
149
150}  // namespace internal
151}  // namespace v8
152
153#endif  // V8_CRANKSHAFT_HYDROGEN_GVN_H_
154