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 5014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch#include "src/crankshaft/hydrogen-gvn.h" 6014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 7014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch#include "src/crankshaft/hydrogen.h" 8b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#include "src/v8.h" 9b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 10b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochnamespace v8 { 11b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochnamespace internal { 12b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 13014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdochclass HInstructionMap final : public ZoneObject { 14b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch public: 15b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HInstructionMap(Zone* zone, SideEffectsTracker* side_effects_tracker) 16b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch : array_size_(0), 17b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch lists_size_(0), 18b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch count_(0), 19b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch array_(NULL), 20b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch lists_(NULL), 21b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch free_list_head_(kNil), 22b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch side_effects_tracker_(side_effects_tracker) { 23b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch ResizeLists(kInitialSize, zone); 24b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Resize(kInitialSize, zone); 25b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 26b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 27b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch void Kill(SideEffects side_effects); 28b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 29b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch void Add(HInstruction* instr, Zone* zone) { 30b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch present_depends_on_.Add(side_effects_tracker_->ComputeDependsOn(instr)); 31b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Insert(instr, zone); 32b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 33b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 34b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HInstruction* Lookup(HInstruction* instr) const; 35b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 36b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HInstructionMap* Copy(Zone* zone) const { 37b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch return new(zone) HInstructionMap(zone, this); 38b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 39b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 40b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch bool IsEmpty() const { return count_ == 0; } 41b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 42b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch private: 43b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // A linked list of HInstruction* values. Stored in arrays. 44b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch struct HInstructionMapListElement { 45b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HInstruction* instr; 46b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch int next; // Index in the array of the next list element. 47b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch }; 48b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch static const int kNil = -1; // The end of a linked list 49b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 50b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Must be a power of 2. 51b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch static const int kInitialSize = 16; 52b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 53b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HInstructionMap(Zone* zone, const HInstructionMap* other); 54b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 55b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch void Resize(int new_size, Zone* zone); 56b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch void ResizeLists(int new_size, Zone* zone); 57b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch void Insert(HInstruction* instr, Zone* zone); 58b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch uint32_t Bound(uint32_t value) const { return value & (array_size_ - 1); } 59b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 60b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch int array_size_; 61b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch int lists_size_; 62b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch int count_; // The number of values stored in the HInstructionMap. 63b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch SideEffects present_depends_on_; 64b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HInstructionMapListElement* array_; 65b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Primary store - contains the first value 66b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // with a given hash. Colliding elements are stored in linked lists. 67b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HInstructionMapListElement* lists_; 68b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // The linked lists containing hash collisions. 69b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch int free_list_head_; // Unused elements in lists_ are on the free list. 70b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch SideEffectsTracker* side_effects_tracker_; 71b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch}; 72b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 73b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 74014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdochclass HSideEffectMap final BASE_EMBEDDED { 75b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch public: 76b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HSideEffectMap(); 77b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch explicit HSideEffectMap(HSideEffectMap* other); 78b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HSideEffectMap& operator= (const HSideEffectMap& other); 79b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 80b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch void Kill(SideEffects side_effects); 81b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 82b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch void Store(SideEffects side_effects, HInstruction* instr); 83b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 84b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch bool IsEmpty() const { return count_ == 0; } 85b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 86b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch inline HInstruction* operator[](int i) const { 87b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(0 <= i); 88b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(i < kNumberOfTrackedSideEffects); 89b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch return data_[i]; 90b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 91b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch inline HInstruction* at(int i) const { return operator[](i); } 92b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 93b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch private: 94b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch int count_; 95b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HInstruction* data_[kNumberOfTrackedSideEffects]; 96b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch}; 97b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 98b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 99b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochvoid TraceGVN(const char* msg, ...) { 100b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch va_list arguments; 101b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch va_start(arguments, msg); 102b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch base::OS::VPrint(msg, arguments); 103b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch va_end(arguments); 104b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch} 105b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 106b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 107b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// Wrap TraceGVN in macros to avoid the expense of evaluating its arguments when 108b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// --trace-gvn is off. 109b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#define TRACE_GVN_1(msg, a1) \ 110b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (FLAG_trace_gvn) { \ 111b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch TraceGVN(msg, a1); \ 112b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 113b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 114b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#define TRACE_GVN_2(msg, a1, a2) \ 115b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (FLAG_trace_gvn) { \ 116b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch TraceGVN(msg, a1, a2); \ 117b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 118b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 119b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#define TRACE_GVN_3(msg, a1, a2, a3) \ 120b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (FLAG_trace_gvn) { \ 121b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch TraceGVN(msg, a1, a2, a3); \ 122b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 123b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 124b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#define TRACE_GVN_4(msg, a1, a2, a3, a4) \ 125b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (FLAG_trace_gvn) { \ 126b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch TraceGVN(msg, a1, a2, a3, a4); \ 127b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 128b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 129b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#define TRACE_GVN_5(msg, a1, a2, a3, a4, a5) \ 130b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (FLAG_trace_gvn) { \ 131b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch TraceGVN(msg, a1, a2, a3, a4, a5); \ 132b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 133b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 134b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 135b8a8cc1952d61a2f3a2568848933943a543b5d3eBen MurdochHInstructionMap::HInstructionMap(Zone* zone, const HInstructionMap* other) 136b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch : array_size_(other->array_size_), 137b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch lists_size_(other->lists_size_), 138b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch count_(other->count_), 139b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch present_depends_on_(other->present_depends_on_), 140b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch array_(zone->NewArray<HInstructionMapListElement>(other->array_size_)), 141b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch lists_(zone->NewArray<HInstructionMapListElement>(other->lists_size_)), 142b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch free_list_head_(other->free_list_head_), 143b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch side_effects_tracker_(other->side_effects_tracker_) { 144b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch MemCopy(array_, other->array_, 145b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch array_size_ * sizeof(HInstructionMapListElement)); 146b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch MemCopy(lists_, other->lists_, 147b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch lists_size_ * sizeof(HInstructionMapListElement)); 148b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch} 149b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 150b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 151b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochvoid HInstructionMap::Kill(SideEffects changes) { 152b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (!present_depends_on_.ContainsAnyOf(changes)) return; 153b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch present_depends_on_.RemoveAll(); 154b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch for (int i = 0; i < array_size_; ++i) { 155b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HInstruction* instr = array_[i].instr; 156b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (instr != NULL) { 157b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Clear list of collisions first, so we know if it becomes empty. 158b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch int kept = kNil; // List of kept elements. 159b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch int next; 160b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch for (int current = array_[i].next; current != kNil; current = next) { 161b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch next = lists_[current].next; 162b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HInstruction* instr = lists_[current].instr; 163b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch SideEffects depends_on = side_effects_tracker_->ComputeDependsOn(instr); 164b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (depends_on.ContainsAnyOf(changes)) { 165b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Drop it. 166b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch count_--; 167b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch lists_[current].next = free_list_head_; 168b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch free_list_head_ = current; 169b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } else { 170b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Keep it. 171b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch lists_[current].next = kept; 172b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch kept = current; 173b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch present_depends_on_.Add(depends_on); 174b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 175b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 176b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch array_[i].next = kept; 177b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 178b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Now possibly drop directly indexed element. 179b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch instr = array_[i].instr; 180b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch SideEffects depends_on = side_effects_tracker_->ComputeDependsOn(instr); 181b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (depends_on.ContainsAnyOf(changes)) { // Drop it. 182b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch count_--; 183b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch int head = array_[i].next; 184b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (head == kNil) { 185b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch array_[i].instr = NULL; 186b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } else { 187b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch array_[i].instr = lists_[head].instr; 188b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch array_[i].next = lists_[head].next; 189b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch lists_[head].next = free_list_head_; 190b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch free_list_head_ = head; 191b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 192b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } else { 193b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch present_depends_on_.Add(depends_on); // Keep it. 194b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 195b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 196b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 197b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch} 198b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 199b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 200b8a8cc1952d61a2f3a2568848933943a543b5d3eBen MurdochHInstruction* HInstructionMap::Lookup(HInstruction* instr) const { 201b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch uint32_t hash = static_cast<uint32_t>(instr->Hashcode()); 202b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch uint32_t pos = Bound(hash); 203b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (array_[pos].instr != NULL) { 204b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (array_[pos].instr->Equals(instr)) return array_[pos].instr; 205b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch int next = array_[pos].next; 206b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch while (next != kNil) { 207b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (lists_[next].instr->Equals(instr)) return lists_[next].instr; 208b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch next = lists_[next].next; 209b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 210b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 211b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch return NULL; 212b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch} 213b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 214b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 215b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochvoid HInstructionMap::Resize(int new_size, Zone* zone) { 216b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(new_size > count_); 217b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Hashing the values into the new array has no more collisions than in the 218b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // old hash map, so we can use the existing lists_ array, if we are careful. 219b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 220b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Make sure we have at least one free element. 221b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (free_list_head_ == kNil) { 222b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch ResizeLists(lists_size_ << 1, zone); 223b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 224b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 225b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HInstructionMapListElement* new_array = 226b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch zone->NewArray<HInstructionMapListElement>(new_size); 227b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch memset(new_array, 0, sizeof(HInstructionMapListElement) * new_size); 228b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 229b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HInstructionMapListElement* old_array = array_; 230b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch int old_size = array_size_; 231b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 232b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch int old_count = count_; 233b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch count_ = 0; 234b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Do not modify present_depends_on_. It is currently correct. 235b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch array_size_ = new_size; 236b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch array_ = new_array; 237b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 238b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (old_array != NULL) { 239b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Iterate over all the elements in lists, rehashing them. 240b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch for (int i = 0; i < old_size; ++i) { 241b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (old_array[i].instr != NULL) { 242b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch int current = old_array[i].next; 243b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch while (current != kNil) { 244b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Insert(lists_[current].instr, zone); 245b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch int next = lists_[current].next; 246b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch lists_[current].next = free_list_head_; 247b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch free_list_head_ = current; 248b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch current = next; 249b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 250b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Rehash the directly stored instruction. 251b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Insert(old_array[i].instr, zone); 252b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 253b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 254b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 255b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch USE(old_count); 256b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(count_ == old_count); 257b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch} 258b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 259b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 260b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochvoid HInstructionMap::ResizeLists(int new_size, Zone* zone) { 261b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(new_size > lists_size_); 262b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 263b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HInstructionMapListElement* new_lists = 264b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch zone->NewArray<HInstructionMapListElement>(new_size); 265b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch memset(new_lists, 0, sizeof(HInstructionMapListElement) * new_size); 266b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 267b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HInstructionMapListElement* old_lists = lists_; 268b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch int old_size = lists_size_; 269b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 270b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch lists_size_ = new_size; 271b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch lists_ = new_lists; 272b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 273b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (old_lists != NULL) { 274b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch MemCopy(lists_, old_lists, old_size * sizeof(HInstructionMapListElement)); 275b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 276b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch for (int i = old_size; i < lists_size_; ++i) { 277b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch lists_[i].next = free_list_head_; 278b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch free_list_head_ = i; 279b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 280b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch} 281b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 282b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 283b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochvoid HInstructionMap::Insert(HInstruction* instr, Zone* zone) { 284b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(instr != NULL); 285b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Resizing when half of the hashtable is filled up. 286b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (count_ >= array_size_ >> 1) Resize(array_size_ << 1, zone); 287b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(count_ < array_size_); 288b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch count_++; 289b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch uint32_t pos = Bound(static_cast<uint32_t>(instr->Hashcode())); 290b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (array_[pos].instr == NULL) { 291b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch array_[pos].instr = instr; 292b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch array_[pos].next = kNil; 293b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } else { 294b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (free_list_head_ == kNil) { 295b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch ResizeLists(lists_size_ << 1, zone); 296b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 297b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch int new_element_pos = free_list_head_; 298b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(new_element_pos != kNil); 299b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch free_list_head_ = lists_[free_list_head_].next; 300b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch lists_[new_element_pos].instr = instr; 301b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch lists_[new_element_pos].next = array_[pos].next; 302b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(array_[pos].next == kNil || lists_[array_[pos].next].instr != NULL); 303b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch array_[pos].next = new_element_pos; 304b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 305b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch} 306b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 307b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 308b8a8cc1952d61a2f3a2568848933943a543b5d3eBen MurdochHSideEffectMap::HSideEffectMap() : count_(0) { 309b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch memset(data_, 0, kNumberOfTrackedSideEffects * kPointerSize); 310b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch} 311b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 312b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 313b8a8cc1952d61a2f3a2568848933943a543b5d3eBen MurdochHSideEffectMap::HSideEffectMap(HSideEffectMap* other) : count_(other->count_) { 314b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch *this = *other; // Calls operator=. 315b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch} 316b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 317b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 318b8a8cc1952d61a2f3a2568848933943a543b5d3eBen MurdochHSideEffectMap& HSideEffectMap::operator=(const HSideEffectMap& other) { 319b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (this != &other) { 320b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch MemCopy(data_, other.data_, kNumberOfTrackedSideEffects * kPointerSize); 321b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 322b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch return *this; 323b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch} 324b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 325b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 326b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochvoid HSideEffectMap::Kill(SideEffects side_effects) { 327b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch for (int i = 0; i < kNumberOfTrackedSideEffects; i++) { 328b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (side_effects.ContainsFlag(GVNFlagFromInt(i))) { 329b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (data_[i] != NULL) count_--; 330b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch data_[i] = NULL; 331b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 332b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 333b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch} 334b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 335b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 336b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochvoid HSideEffectMap::Store(SideEffects side_effects, HInstruction* instr) { 337b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch for (int i = 0; i < kNumberOfTrackedSideEffects; i++) { 338b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (side_effects.ContainsFlag(GVNFlagFromInt(i))) { 339b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (data_[i] == NULL) count_++; 340b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch data_[i] = instr; 341b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 342b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 343b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch} 344b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 345b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 346b8a8cc1952d61a2f3a2568848933943a543b5d3eBen MurdochSideEffects SideEffectsTracker::ComputeChanges(HInstruction* instr) { 347b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch int index; 348b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch SideEffects result(instr->ChangesFlags()); 349b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (result.ContainsFlag(kGlobalVars)) { 350014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch if (instr->IsStoreNamedField()) { 351014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch HStoreNamedField* store = HStoreNamedField::cast(instr); 352014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch HConstant* target = HConstant::cast(store->object()); 353014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch if (ComputeGlobalVar(Unique<PropertyCell>::cast(target->GetUnique()), 354014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch &index)) { 355014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch result.RemoveFlag(kGlobalVars); 356b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch result.AddSpecial(GlobalVar(index)); 357014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch return result; 358b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 359b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 360014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch for (index = 0; index < kNumberOfGlobalVars; ++index) { 361014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch result.AddSpecial(GlobalVar(index)); 362014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } 363014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } else if (result.ContainsFlag(kInobjectFields)) { 364b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (instr->IsStoreNamedField() && 365b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch ComputeInobjectField(HStoreNamedField::cast(instr)->access(), &index)) { 366b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch result.RemoveFlag(kInobjectFields); 367b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch result.AddSpecial(InobjectField(index)); 368b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } else { 369b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch for (index = 0; index < kNumberOfInobjectFields; ++index) { 370b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch result.AddSpecial(InobjectField(index)); 371b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 372b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 373b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 374b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch return result; 375b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch} 376b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 377b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 378b8a8cc1952d61a2f3a2568848933943a543b5d3eBen MurdochSideEffects SideEffectsTracker::ComputeDependsOn(HInstruction* instr) { 379b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch int index; 380b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch SideEffects result(instr->DependsOnFlags()); 381b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (result.ContainsFlag(kGlobalVars)) { 382014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch if (instr->IsLoadNamedField()) { 383014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch HLoadNamedField* load = HLoadNamedField::cast(instr); 384014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch HConstant* target = HConstant::cast(load->object()); 385014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch if (ComputeGlobalVar(Unique<PropertyCell>::cast(target->GetUnique()), 386014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch &index)) { 387014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch result.RemoveFlag(kGlobalVars); 388b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch result.AddSpecial(GlobalVar(index)); 389014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch return result; 390b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 391b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 392014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch for (index = 0; index < kNumberOfGlobalVars; ++index) { 393014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch result.AddSpecial(GlobalVar(index)); 394014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } 395014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } else if (result.ContainsFlag(kInobjectFields)) { 396b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (instr->IsLoadNamedField() && 397b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch ComputeInobjectField(HLoadNamedField::cast(instr)->access(), &index)) { 398b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch result.RemoveFlag(kInobjectFields); 399b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch result.AddSpecial(InobjectField(index)); 400b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } else { 401b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch for (index = 0; index < kNumberOfInobjectFields; ++index) { 402b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch result.AddSpecial(InobjectField(index)); 403b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 404b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 405b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 406b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch return result; 407b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch} 408b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 409b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 410958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernierstd::ostream& operator<<(std::ostream& os, const TrackedEffects& te) { 411b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch SideEffectsTracker* t = te.tracker; 412b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch const char* separator = ""; 413b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch os << "["; 414b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch for (int bit = 0; bit < kNumberOfFlags; ++bit) { 415b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch GVNFlag flag = GVNFlagFromInt(bit); 416b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (te.effects.ContainsFlag(flag)) { 417b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch os << separator; 418b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch separator = ", "; 419b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch switch (flag) { 420b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#define DECLARE_FLAG(Type) \ 421b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch case k##Type: \ 422b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch os << #Type; \ 423b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch break; 424b8a8cc1952d61a2f3a2568848933943a543b5d3eBen MurdochGVN_TRACKED_FLAG_LIST(DECLARE_FLAG) 425b8a8cc1952d61a2f3a2568848933943a543b5d3eBen MurdochGVN_UNTRACKED_FLAG_LIST(DECLARE_FLAG) 426b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#undef DECLARE_FLAG 427b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch default: 428b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch break; 429b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 430b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 431b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 432b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch for (int index = 0; index < t->num_global_vars_; ++index) { 433b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (te.effects.ContainsSpecial(t->GlobalVar(index))) { 434b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch os << separator << "[" << *t->global_vars_[index].handle() << "]"; 435b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch separator = ", "; 436b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 437b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 438b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch for (int index = 0; index < t->num_inobject_fields_; ++index) { 439b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (te.effects.ContainsSpecial(t->InobjectField(index))) { 440b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch os << separator << t->inobject_fields_[index]; 441b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch separator = ", "; 442b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 443b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 444b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch os << "]"; 445b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch return os; 446b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch} 447b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 448b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 449014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdochbool SideEffectsTracker::ComputeGlobalVar(Unique<PropertyCell> cell, 450014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch int* index) { 451b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch for (int i = 0; i < num_global_vars_; ++i) { 452b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (cell == global_vars_[i]) { 453b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch *index = i; 454b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch return true; 455b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 456b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 457b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (num_global_vars_ < kNumberOfGlobalVars) { 458b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (FLAG_trace_gvn) { 459b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch OFStream os(stdout); 460b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch os << "Tracking global var [" << *cell.handle() << "] " 461958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier << "(mapped to index " << num_global_vars_ << ")" << std::endl; 462b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 463b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch *index = num_global_vars_; 464b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch global_vars_[num_global_vars_++] = cell; 465b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch return true; 466b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 467b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch return false; 468b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch} 469b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 470b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 471b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochbool SideEffectsTracker::ComputeInobjectField(HObjectAccess access, 472b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch int* index) { 473b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch for (int i = 0; i < num_inobject_fields_; ++i) { 474b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (access.Equals(inobject_fields_[i])) { 475b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch *index = i; 476b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch return true; 477b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 478b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 479b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (num_inobject_fields_ < kNumberOfInobjectFields) { 480b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (FLAG_trace_gvn) { 481b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch OFStream os(stdout); 482b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch os << "Tracking inobject field access " << access << " (mapped to index " 483958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier << num_inobject_fields_ << ")" << std::endl; 484b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 485b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch *index = num_inobject_fields_; 486b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch inobject_fields_[num_inobject_fields_++] = access; 487b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch return true; 488b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 489b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch return false; 490b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch} 491b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 492b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 493b8a8cc1952d61a2f3a2568848933943a543b5d3eBen MurdochHGlobalValueNumberingPhase::HGlobalValueNumberingPhase(HGraph* graph) 494b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch : HPhase("H_Global value numbering", graph), 495b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch removed_side_effects_(false), 496b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch block_side_effects_(graph->blocks()->length(), zone()), 497b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch loop_side_effects_(graph->blocks()->length(), zone()), 498b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch visited_on_paths_(graph->blocks()->length(), zone()) { 499b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(!AllowHandleAllocation::IsAllowed()); 500b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch block_side_effects_.AddBlock( 501b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch SideEffects(), graph->blocks()->length(), zone()); 502b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch loop_side_effects_.AddBlock( 503b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch SideEffects(), graph->blocks()->length(), zone()); 504b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch} 505b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 506b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 507b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochvoid HGlobalValueNumberingPhase::Run() { 508b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(!removed_side_effects_); 509b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch for (int i = FLAG_gvn_iterations; i > 0; --i) { 510b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Compute the side effects. 511b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch ComputeBlockSideEffects(); 512b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 513b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Perform loop invariant code motion if requested. 514b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (FLAG_loop_invariant_code_motion) LoopInvariantCodeMotion(); 515b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 516b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Perform the actual value numbering. 517b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch AnalyzeGraph(); 518b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 519b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Continue GVN if we removed any side effects. 520b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (!removed_side_effects_) break; 521b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch removed_side_effects_ = false; 522b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 523b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Clear all side effects. 524b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK_EQ(block_side_effects_.length(), graph()->blocks()->length()); 525b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK_EQ(loop_side_effects_.length(), graph()->blocks()->length()); 526b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch for (int i = 0; i < graph()->blocks()->length(); ++i) { 527b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch block_side_effects_[i].RemoveAll(); 528b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch loop_side_effects_[i].RemoveAll(); 529b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 530b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch visited_on_paths_.Clear(); 531b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 532b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch} 533b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 534b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 535b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochvoid HGlobalValueNumberingPhase::ComputeBlockSideEffects() { 536b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch for (int i = graph()->blocks()->length() - 1; i >= 0; --i) { 537b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Compute side effects for the block. 538b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HBasicBlock* block = graph()->blocks()->at(i); 539b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch SideEffects side_effects; 540b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (block->IsReachable() && !block->IsDeoptimizing()) { 541b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch int id = block->block_id(); 542b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch for (HInstructionIterator it(block); !it.Done(); it.Advance()) { 543b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HInstruction* instr = it.Current(); 544b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch side_effects.Add(side_effects_tracker_.ComputeChanges(instr)); 545b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 546b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch block_side_effects_[id].Add(side_effects); 547b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 548b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Loop headers are part of their loop. 549b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (block->IsLoopHeader()) { 550b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch loop_side_effects_[id].Add(side_effects); 551b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 552b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 553b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Propagate loop side effects upwards. 554b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (block->HasParentLoopHeader()) { 555b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HBasicBlock* with_parent = block; 556b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (block->IsLoopHeader()) side_effects = loop_side_effects_[id]; 557b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch do { 558b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HBasicBlock* parent_block = with_parent->parent_loop_header(); 559b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch loop_side_effects_[parent_block->block_id()].Add(side_effects); 560b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch with_parent = parent_block; 561b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } while (with_parent->HasParentLoopHeader()); 562b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 563b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 564b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 565b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch} 566b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 567b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 568b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochvoid HGlobalValueNumberingPhase::LoopInvariantCodeMotion() { 569b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch TRACE_GVN_1("Using optimistic loop invariant code motion: %s\n", 570b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch graph()->use_optimistic_licm() ? "yes" : "no"); 571b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch for (int i = graph()->blocks()->length() - 1; i >= 0; --i) { 572b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HBasicBlock* block = graph()->blocks()->at(i); 573b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (block->IsLoopHeader()) { 574b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch SideEffects side_effects = loop_side_effects_[block->block_id()]; 575b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (FLAG_trace_gvn) { 576b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch OFStream os(stdout); 577b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch os << "Try loop invariant motion for " << *block << " changes " 578958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier << Print(side_effects) << std::endl; 579b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 580b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HBasicBlock* last = block->loop_information()->GetLastBackEdge(); 581b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch for (int j = block->block_id(); j <= last->block_id(); ++j) { 582b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch ProcessLoopBlock(graph()->blocks()->at(j), block, side_effects); 583b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 584b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 585b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 586b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch} 587b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 588b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 589b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochvoid HGlobalValueNumberingPhase::ProcessLoopBlock( 590b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HBasicBlock* block, 591b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HBasicBlock* loop_header, 592b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch SideEffects loop_kills) { 593b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HBasicBlock* pre_header = loop_header->predecessors()->at(0); 594b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (FLAG_trace_gvn) { 595b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch OFStream os(stdout); 596b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch os << "Loop invariant code motion for " << *block << " depends on " 597958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier << Print(loop_kills) << std::endl; 598b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 599b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HInstruction* instr = block->first(); 600b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch while (instr != NULL) { 601b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HInstruction* next = instr->next(); 602b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (instr->CheckFlag(HValue::kUseGVN)) { 603b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch SideEffects changes = side_effects_tracker_.ComputeChanges(instr); 604b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch SideEffects depends_on = side_effects_tracker_.ComputeDependsOn(instr); 605b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (FLAG_trace_gvn) { 606b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch OFStream os(stdout); 607b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch os << "Checking instruction i" << instr->id() << " (" 608b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch << instr->Mnemonic() << ") changes " << Print(changes) 609b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch << ", depends on " << Print(depends_on) << ". Loop changes " 610958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier << Print(loop_kills) << std::endl; 611b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 612b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch bool can_hoist = !depends_on.ContainsAnyOf(loop_kills); 613b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (can_hoist && !graph()->use_optimistic_licm()) { 614b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch can_hoist = block->IsLoopSuccessorDominator(); 615b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 616b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 617b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (can_hoist) { 618b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch bool inputs_loop_invariant = true; 619b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch for (int i = 0; i < instr->OperandCount(); ++i) { 620b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (instr->OperandAt(i)->IsDefinedAfter(pre_header)) { 621b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch inputs_loop_invariant = false; 622b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 623b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 624b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 625b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (inputs_loop_invariant && ShouldMove(instr, loop_header)) { 626b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch TRACE_GVN_2("Hoisting loop invariant instruction i%d to block B%d\n", 627b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch instr->id(), pre_header->block_id()); 628b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Move the instruction out of the loop. 629b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch instr->Unlink(); 630b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch instr->InsertBefore(pre_header->end()); 631b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (instr->HasSideEffects()) removed_side_effects_ = true; 632b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 633b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 634b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 635b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch instr = next; 636b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 637b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch} 638b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 639b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 640b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochbool HGlobalValueNumberingPhase::ShouldMove(HInstruction* instr, 641b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HBasicBlock* loop_header) { 642b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // If we've disabled code motion or we're in a block that unconditionally 643b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // deoptimizes, don't move any instructions. 644537ba893e2530051ec7f296e769fdd37bb4ae4a0Ben Murdoch return graph()->allow_code_motion() && !instr->block()->IsDeoptimizing() && 645537ba893e2530051ec7f296e769fdd37bb4ae4a0Ben Murdoch instr->block()->IsReachable(); 646b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch} 647b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 648b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 649b8a8cc1952d61a2f3a2568848933943a543b5d3eBen MurdochSideEffects 650b8a8cc1952d61a2f3a2568848933943a543b5d3eBen MurdochHGlobalValueNumberingPhase::CollectSideEffectsOnPathsToDominatedBlock( 651b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HBasicBlock* dominator, HBasicBlock* dominated) { 652b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch SideEffects side_effects; 653b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch for (int i = 0; i < dominated->predecessors()->length(); ++i) { 654b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HBasicBlock* block = dominated->predecessors()->at(i); 655b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (dominator->block_id() < block->block_id() && 656b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch block->block_id() < dominated->block_id() && 657b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch !visited_on_paths_.Contains(block->block_id())) { 658b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch visited_on_paths_.Add(block->block_id()); 659b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch side_effects.Add(block_side_effects_[block->block_id()]); 660b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (block->IsLoopHeader()) { 661b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch side_effects.Add(loop_side_effects_[block->block_id()]); 662b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 663b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch side_effects.Add(CollectSideEffectsOnPathsToDominatedBlock( 664b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch dominator, block)); 665b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 666b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 667b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch return side_effects; 668b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch} 669b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 670b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 671b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// Each instance of this class is like a "stack frame" for the recursive 672b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// traversal of the dominator tree done during GVN (the stack is handled 673b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// as a double linked list). 674b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// We reuse frames when possible so the list length is limited by the depth 675b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// of the dominator tree but this forces us to initialize each frame calling 676b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// an explicit "Initialize" method instead of a using constructor. 677b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochclass GvnBasicBlockState: public ZoneObject { 678b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch public: 679b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch static GvnBasicBlockState* CreateEntry(Zone* zone, 680b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HBasicBlock* entry_block, 681b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HInstructionMap* entry_map) { 682b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch return new(zone) 683b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch GvnBasicBlockState(NULL, entry_block, entry_map, NULL, zone); 684b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 685b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 686b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HBasicBlock* block() { return block_; } 687b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HInstructionMap* map() { return map_; } 688b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HSideEffectMap* dominators() { return &dominators_; } 689b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 690b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch GvnBasicBlockState* next_in_dominator_tree_traversal( 691b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Zone* zone, 692b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HBasicBlock** dominator) { 693b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // This assignment needs to happen before calling next_dominated() because 694b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // that call can reuse "this" if we are at the last dominated block. 695b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch *dominator = block(); 696b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch GvnBasicBlockState* result = next_dominated(zone); 697b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (result == NULL) { 698b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch GvnBasicBlockState* dominator_state = pop(); 699b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (dominator_state != NULL) { 700b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // This branch is guaranteed not to return NULL because pop() never 701b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // returns a state where "is_done() == true". 702b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch *dominator = dominator_state->block(); 703b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch result = dominator_state->next_dominated(zone); 704b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } else { 705b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Unnecessary (we are returning NULL) but done for cleanness. 706b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch *dominator = NULL; 707b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 708b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 709b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch return result; 710b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 711b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 712b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch private: 713b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch void Initialize(HBasicBlock* block, 714b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HInstructionMap* map, 715b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HSideEffectMap* dominators, 716b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch bool copy_map, 717b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Zone* zone) { 718b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch block_ = block; 719b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch map_ = copy_map ? map->Copy(zone) : map; 720b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch dominated_index_ = -1; 721b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch length_ = block->dominated_blocks()->length(); 722b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (dominators != NULL) { 723b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch dominators_ = *dominators; 724b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 725b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 726b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch bool is_done() { return dominated_index_ >= length_; } 727b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 728b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch GvnBasicBlockState(GvnBasicBlockState* previous, 729b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HBasicBlock* block, 730b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HInstructionMap* map, 731b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HSideEffectMap* dominators, 732b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Zone* zone) 733b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch : previous_(previous), next_(NULL) { 734b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Initialize(block, map, dominators, true, zone); 735b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 736b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 737b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch GvnBasicBlockState* next_dominated(Zone* zone) { 738b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch dominated_index_++; 739b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (dominated_index_ == length_ - 1) { 740b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // No need to copy the map for the last child in the dominator tree. 741b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Initialize(block_->dominated_blocks()->at(dominated_index_), 742b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch map(), 743b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch dominators(), 744b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch false, 745b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch zone); 746b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch return this; 747b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } else if (dominated_index_ < length_) { 748b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch return push(zone, block_->dominated_blocks()->at(dominated_index_)); 749b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } else { 750b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch return NULL; 751b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 752b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 753b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 754b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch GvnBasicBlockState* push(Zone* zone, HBasicBlock* block) { 755b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (next_ == NULL) { 756b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch next_ = 757b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch new(zone) GvnBasicBlockState(this, block, map(), dominators(), zone); 758b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } else { 759b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch next_->Initialize(block, map(), dominators(), true, zone); 760b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 761b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch return next_; 762b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 763b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch GvnBasicBlockState* pop() { 764b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch GvnBasicBlockState* result = previous_; 765b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch while (result != NULL && result->is_done()) { 766b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch TRACE_GVN_2("Backtracking from block B%d to block b%d\n", 767b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch block()->block_id(), 768b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch previous_->block()->block_id()) 769b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch result = result->previous_; 770b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 771b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch return result; 772b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 773b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 774b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch GvnBasicBlockState* previous_; 775b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch GvnBasicBlockState* next_; 776b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HBasicBlock* block_; 777b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HInstructionMap* map_; 778b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HSideEffectMap dominators_; 779b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch int dominated_index_; 780b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch int length_; 781b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch}; 782b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 783b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 784b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// This is a recursive traversal of the dominator tree but it has been turned 785b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// into a loop to avoid stack overflows. 786b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// The logical "stack frames" of the recursion are kept in a list of 787b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// GvnBasicBlockState instances. 788b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochvoid HGlobalValueNumberingPhase::AnalyzeGraph() { 789b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HBasicBlock* entry_block = graph()->entry_block(); 790b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HInstructionMap* entry_map = 791b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch new(zone()) HInstructionMap(zone(), &side_effects_tracker_); 792b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch GvnBasicBlockState* current = 793b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch GvnBasicBlockState::CreateEntry(zone(), entry_block, entry_map); 794b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 795b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch while (current != NULL) { 796b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HBasicBlock* block = current->block(); 797b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HInstructionMap* map = current->map(); 798b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HSideEffectMap* dominators = current->dominators(); 799b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 800b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch TRACE_GVN_2("Analyzing block B%d%s\n", 801b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch block->block_id(), 802b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch block->IsLoopHeader() ? " (loop header)" : ""); 803b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 804b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // If this is a loop header kill everything killed by the loop. 805b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (block->IsLoopHeader()) { 806b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch map->Kill(loop_side_effects_[block->block_id()]); 807b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch dominators->Kill(loop_side_effects_[block->block_id()]); 808b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 809b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 810b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Go through all instructions of the current block. 811b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch for (HInstructionIterator it(block); !it.Done(); it.Advance()) { 812b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HInstruction* instr = it.Current(); 813b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (instr->CheckFlag(HValue::kTrackSideEffectDominators)) { 814b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch for (int i = 0; i < kNumberOfTrackedSideEffects; i++) { 815b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HValue* other = dominators->at(i); 816b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch GVNFlag flag = GVNFlagFromInt(i); 817b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (instr->DependsOnFlags().Contains(flag) && other != NULL) { 818b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch TRACE_GVN_5("Side-effect #%d in %d (%s) is dominated by %d (%s)\n", 819b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch i, 820b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch instr->id(), 821b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch instr->Mnemonic(), 822b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch other->id(), 823b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch other->Mnemonic()); 824b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (instr->HandleSideEffectDominator(flag, other)) { 825b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch removed_side_effects_ = true; 826b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 827b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 828b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 829b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 830b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Instruction was unlinked during graph traversal. 831b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (!instr->IsLinked()) continue; 832b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 833b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch SideEffects changes = side_effects_tracker_.ComputeChanges(instr); 834b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (!changes.IsEmpty()) { 835b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Clear all instructions in the map that are affected by side effects. 836b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Store instruction as the dominating one for tracked side effects. 837b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch map->Kill(changes); 838b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch dominators->Store(changes, instr); 839b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (FLAG_trace_gvn) { 840b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch OFStream os(stdout); 841b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch os << "Instruction i" << instr->id() << " changes " << Print(changes) 842958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier << std::endl; 843b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 844b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 845b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (instr->CheckFlag(HValue::kUseGVN) && 846b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch !instr->CheckFlag(HValue::kCantBeReplaced)) { 847b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(!instr->HasObservableSideEffects()); 848b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HInstruction* other = map->Lookup(instr); 849b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (other != NULL) { 850b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(instr->Equals(other) && other->Equals(instr)); 851b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch TRACE_GVN_4("Replacing instruction i%d (%s) with i%d (%s)\n", 852b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch instr->id(), 853b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch instr->Mnemonic(), 854b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch other->id(), 855b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch other->Mnemonic()); 856b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (instr->HasSideEffects()) removed_side_effects_ = true; 857b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch instr->DeleteAndReplaceWith(other); 858b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } else { 859b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch map->Add(instr, zone()); 860b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 861b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 862b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 863b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 864b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HBasicBlock* dominator_block; 865b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch GvnBasicBlockState* next = 866b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch current->next_in_dominator_tree_traversal(zone(), 867b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch &dominator_block); 868b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 869b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (next != NULL) { 870b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HBasicBlock* dominated = next->block(); 871b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HInstructionMap* successor_map = next->map(); 872b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HSideEffectMap* successor_dominators = next->dominators(); 873b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 874b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Kill everything killed on any path between this block and the 875b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // dominated block. We don't have to traverse these paths if the 876b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // value map and the dominators list is already empty. If the range 877b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // of block ids (block_id, dominated_id) is empty there are no such 878b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // paths. 879b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if ((!successor_map->IsEmpty() || !successor_dominators->IsEmpty()) && 880b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch dominator_block->block_id() + 1 < dominated->block_id()) { 881b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch visited_on_paths_.Clear(); 882b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch SideEffects side_effects_on_all_paths = 883b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CollectSideEffectsOnPathsToDominatedBlock(dominator_block, 884b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch dominated); 885b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch successor_map->Kill(side_effects_on_all_paths); 886b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch successor_dominators->Kill(side_effects_on_all_paths); 887b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 888b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 889b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch current = next; 890b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 891b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch} 892b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 893014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch} // namespace internal 894014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch} // namespace v8 895