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.h"
11 #include "src/crankshaft/hydrogen-instructions.h"
12 #include "src/zone.h"
13 
14 namespace v8 {
15 namespace 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).
21 class SideEffects final {
22  public:
23   static const int kNumberOfSpecials = 64 - kNumberOfFlags;
24 
SideEffects()25   SideEffects() : bits_(0) {
26     DCHECK(kNumberOfFlags + kNumberOfSpecials == sizeof(bits_) * CHAR_BIT);
27   }
SideEffects(GVNFlagSet flags)28   explicit SideEffects(GVNFlagSet flags) : bits_(flags.ToIntegral()) {}
IsEmpty()29   bool IsEmpty() const { return bits_ == 0; }
ContainsFlag(GVNFlag flag)30   bool ContainsFlag(GVNFlag flag) const {
31     return (bits_ & MaskFlag(flag)) != 0;
32   }
ContainsSpecial(int special)33   bool ContainsSpecial(int special) const {
34     return (bits_ & MaskSpecial(special)) != 0;
35   }
ContainsAnyOf(SideEffects set)36   bool ContainsAnyOf(SideEffects set) const { return (bits_ & set.bits_) != 0; }
Add(SideEffects set)37   void Add(SideEffects set) { bits_ |= set.bits_; }
AddSpecial(int special)38   void AddSpecial(int special) { bits_ |= MaskSpecial(special); }
RemoveFlag(GVNFlag flag)39   void RemoveFlag(GVNFlag flag) { bits_ &= ~MaskFlag(flag); }
RemoveAll()40   void RemoveAll() { bits_ = 0; }
ToIntegral()41   uint64_t ToIntegral() const { return bits_; }
42 
43  private:
MaskFlag(GVNFlag flag)44   uint64_t MaskFlag(GVNFlag flag) const {
45     return static_cast<uint64_t>(1) << static_cast<unsigned>(flag);
46   }
MaskSpecial(int special)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 
58 struct 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.
65 class SideEffectsTracker final BASE_EMBEDDED {
66  public:
SideEffectsTracker()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 
GlobalVar(int index)76   static int GlobalVar(int index) {
77     DCHECK(index >= 0);
78     DCHECK(index < kNumberOfGlobalVars);
79     return index;
80   }
InobjectField(int index)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.
101 struct TrackedEffects {
TrackedEffectsTrackedEffects102   TrackedEffects(SideEffectsTracker* t, SideEffects e)
103       : tracker(t), effects(e) {}
104   SideEffectsTracker* tracker;
105   SideEffects effects;
106 };
107 
108 
109 std::ostream& operator<<(std::ostream& os, const TrackedEffects& f);
110 
111 
112 // Perform common subexpression elimination and loop-invariant code motion.
113 class 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 AllowCodeMotion();
130   bool ShouldMove(HInstruction* instr, HBasicBlock* loop_header);
Print(SideEffects side_effects)131   TrackedEffects Print(SideEffects side_effects) {
132     return TrackedEffects(&side_effects_tracker_, side_effects);
133   }
134 
135   SideEffectsTracker side_effects_tracker_;
136   bool removed_side_effects_;
137 
138   // A map of block IDs to their side effects.
139   ZoneList<SideEffects> block_side_effects_;
140 
141   // A map of loop header block IDs to their loop's side effects.
142   ZoneList<SideEffects> loop_side_effects_;
143 
144   // Used when collecting side effects on paths from dominator to
145   // dominated.
146   BitVector visited_on_paths_;
147 
148   DISALLOW_COPY_AND_ASSIGN(HGlobalValueNumberingPhase);
149 };
150 
151 }  // namespace internal
152 }  // namespace v8
153 
154 #endif  // V8_CRANKSHAFT_HYDROGEN_GVN_H_
155