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 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 ShouldMove(HInstruction* instr, HBasicBlock* loop_header); Print(SideEffects side_effects)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