Line data Source code
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 :
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 :
25 856270 : SideEffects() : bits_(0) {
26 : DCHECK(kNumberOfFlags + kNumberOfSpecials == sizeof(bits_) * CHAR_BIT);
27 : }
28 148441148 : explicit SideEffects(GVNFlagSet flags) : bits_(flags.ToIntegral()) {}
29 34911034 : bool IsEmpty() const { return bits_ == 0; }
30 : bool ContainsFlag(GVNFlag flag) const {
31 298106365 : return (bits_ & MaskFlag(flag)) != 0;
32 : }
33 : bool ContainsSpecial(int special) const {
34 0 : return (bits_ & MaskSpecial(special)) != 0;
35 : }
36 80205266 : bool ContainsAnyOf(SideEffects set) const { return (bits_ & set.bits_) != 0; }
37 135380788 : void Add(SideEffects set) { bits_ |= set.bits_; }
38 15365395 : void AddSpecial(int special) { bits_ |= MaskSpecial(special); }
39 707583 : void RemoveFlag(GVNFlag flag) { bits_ &= ~MaskFlag(flag); }
40 3353887 : void RemoveAll() { bits_ = 0; }
41 : uint64_t ToIntegral() const { return bits_; }
42 :
43 : private:
44 : uint64_t MaskFlag(GVNFlag flag) const {
45 4945260 : 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 15365395 : 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:
67 13331332 : 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 699921 : 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 {
102 : 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 283651 : 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 ShouldMove(HInstruction* instr, HBasicBlock* loop_header);
130 : TrackedEffects Print(SideEffects side_effects) {
131 0 : 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_
|