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