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 14namespace v8 { 15namespace 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). 21class SideEffects final { 22 public: 23 static const int kNumberOfSpecials = 64 - kNumberOfFlags; 24 25 SideEffects() : bits_(0) { 26 DCHECK(kNumberOfFlags + kNumberOfSpecials == sizeof(bits_) * CHAR_BIT); 27 } 28 explicit SideEffects(GVNFlagSet flags) : bits_(flags.ToIntegral()) {} 29 bool IsEmpty() const { return bits_ == 0; } 30 bool ContainsFlag(GVNFlag flag) const { 31 return (bits_ & MaskFlag(flag)) != 0; 32 } 33 bool ContainsSpecial(int special) const { 34 return (bits_ & MaskSpecial(special)) != 0; 35 } 36 bool ContainsAnyOf(SideEffects set) const { return (bits_ & set.bits_) != 0; } 37 void Add(SideEffects set) { bits_ |= set.bits_; } 38 void AddSpecial(int special) { bits_ |= MaskSpecial(special); } 39 void RemoveFlag(GVNFlag flag) { bits_ &= ~MaskFlag(flag); } 40 void RemoveAll() { bits_ = 0; } 41 uint64_t ToIntegral() const { return bits_; } 42 43 private: 44 uint64_t MaskFlag(GVNFlag flag) const { 45 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 special + kNumberOfFlags); 52 } 53 54 uint64_t bits_; 55}; 56 57 58struct 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. 65class SideEffectsTracker final BASE_EMBEDDED { 66 public: 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 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 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. 101struct TrackedEffects { 102 TrackedEffects(SideEffectsTracker* t, SideEffects e) 103 : tracker(t), effects(e) {} 104 SideEffectsTracker* tracker; 105 SideEffects effects; 106}; 107 108 109std::ostream& operator<<(std::ostream& os, const TrackedEffects& f); 110 111 112// Perform common subexpression elimination and loop-invariant code motion. 113class 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 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