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.
5 #ifndef V8_HYDROGEN_GVN_H_
6 #define V8_HYDROGEN_GVN_H_
10 #include "src/hydrogen.h"
11 #include "src/hydrogen-instructions.h"
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).
21 class SideEffects final {
23 static const int kNumberOfSpecials = 64 - kNumberOfFlags;
25 SideEffects() : bits_(0) {
26 DCHECK(kNumberOfFlags + kNumberOfSpecials == sizeof(bits_) * CHAR_BIT);
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;
33 bool ContainsSpecial(int special) const {
34 return (bits_ & MaskSpecial(special)) != 0;
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_; }
44 uint64_t MaskFlag(GVNFlag flag) const {
45 return static_cast<uint64_t>(1) << static_cast<unsigned>(flag);
47 uint64_t MaskSpecial(int special) const {
49 DCHECK(special < kNumberOfSpecials);
50 return static_cast<uint64_t>(1) << static_cast<unsigned>(
51 special + kNumberOfFlags);
58 struct TrackedEffects;
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
65 class SideEffectsTracker final BASE_EMBEDDED {
67 SideEffectsTracker() : num_global_vars_(0), num_inobject_fields_(0) {}
68 SideEffects ComputeChanges(HInstruction* instr);
69 SideEffects ComputeDependsOn(HInstruction* instr);
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);
76 static int GlobalVar(int index) {
78 DCHECK(index < kNumberOfGlobalVars);
81 static int InobjectField(int index) {
83 DCHECK(index < kNumberOfInobjectFields);
84 return index + kNumberOfGlobalVars;
87 // Track up to four global vars.
88 static const int kNumberOfGlobalVars = 4;
89 Unique<PropertyCell> global_vars_[kNumberOfGlobalVars];
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_;
100 // Helper class for printing, because the effects don't know their tracker.
101 struct TrackedEffects {
102 TrackedEffects(SideEffectsTracker* t, SideEffects e)
103 : tracker(t), effects(e) {}
104 SideEffectsTracker* tracker;
109 std::ostream& operator<<(std::ostream& os, const TrackedEffects& f);
112 // Perform common subexpression elimination and loop-invariant code motion.
113 class HGlobalValueNumberingPhase final : public HPhase {
115 explicit HGlobalValueNumberingPhase(HGraph* graph);
120 SideEffects CollectSideEffectsOnPathsToDominatedBlock(
121 HBasicBlock* dominator,
122 HBasicBlock* dominated);
124 void ComputeBlockSideEffects();
125 void LoopInvariantCodeMotion();
126 void ProcessLoopBlock(HBasicBlock* block,
127 HBasicBlock* before_loop,
128 SideEffects loop_kills);
129 bool AllowCodeMotion();
130 bool ShouldMove(HInstruction* instr, HBasicBlock* loop_header);
131 TrackedEffects Print(SideEffects side_effects) {
132 return TrackedEffects(&side_effects_tracker_, side_effects);
135 SideEffectsTracker side_effects_tracker_;
136 bool removed_side_effects_;
138 // A map of block IDs to their side effects.
139 ZoneList<SideEffects> block_side_effects_;
141 // A map of loop header block IDs to their loop's side effects.
142 ZoneList<SideEffects> loop_side_effects_;
144 // Used when collecting side effects on paths from dominator to
146 BitVector visited_on_paths_;
148 DISALLOW_COPY_AND_ASSIGN(HGlobalValueNumberingPhase);
151 } } // namespace v8::internal
153 #endif // V8_HYDROGEN_GVN_H_