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