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