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#include "src/hydrogen-infer-representation.h" 6b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 7b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochnamespace v8 { 8b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochnamespace internal { 9b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 10b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochvoid HInferRepresentationPhase::AddToWorklist(HValue* current) { 11b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (current->representation().IsTagged()) return; 12b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (!current->CheckFlag(HValue::kFlexibleRepresentation)) return; 13b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (in_worklist_.Contains(current->id())) return; 14b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch worklist_.Add(current, zone()); 15b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch in_worklist_.Add(current->id()); 16b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch} 17b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 18b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 19b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochvoid HInferRepresentationPhase::Run() { 20b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // (1) Initialize bit vectors and count real uses. Each phi gets a 21b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // bit-vector of length <number of phis>. 22b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch const ZoneList<HPhi*>* phi_list = graph()->phi_list(); 23b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch int phi_count = phi_list->length(); 24b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch ZoneList<BitVector*> connected_phis(phi_count, zone()); 25b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch for (int i = 0; i < phi_count; ++i) { 26b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch phi_list->at(i)->InitRealUses(i); 27b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch BitVector* connected_set = new(zone()) BitVector(phi_count, zone()); 28b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch connected_set->Add(i); 29b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch connected_phis.Add(connected_set, zone()); 30b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 31b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 32b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // (2) Do a fixed point iteration to find the set of connected phis. A 33b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // phi is connected to another phi if its value is used either directly or 34b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // indirectly through a transitive closure of the def-use relation. 35b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch bool change = true; 36b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch while (change) { 37b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch change = false; 38b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // We normally have far more "forward edges" than "backward edges", 39b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // so we terminate faster when we walk backwards. 40b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch for (int i = phi_count - 1; i >= 0; --i) { 41b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HPhi* phi = phi_list->at(i); 42b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch for (HUseIterator it(phi->uses()); !it.Done(); it.Advance()) { 43b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HValue* use = it.value(); 44b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (use->IsPhi()) { 45b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch int id = HPhi::cast(use)->phi_id(); 46b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (connected_phis[i]->UnionIsChanged(*connected_phis[id])) 47b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch change = true; 48b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 49b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 50b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 51b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 52b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 53b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Set truncation flags for groups of connected phis. This is a conservative 54b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // approximation; the flag will be properly re-computed after representations 55b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // have been determined. 56b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (phi_count > 0) { 57b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch BitVector done(phi_count, zone()); 58b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch for (int i = 0; i < phi_count; ++i) { 59b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (done.Contains(i)) continue; 60b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 61b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Check if all uses of all connected phis in this group are truncating. 62b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch bool all_uses_everywhere_truncating_int32 = true; 63b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch bool all_uses_everywhere_truncating_smi = true; 64b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch for (BitVector::Iterator it(connected_phis[i]); 65b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch !it.Done(); 66b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch it.Advance()) { 67b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch int index = it.Current(); 68b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch all_uses_everywhere_truncating_int32 &= 69b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch phi_list->at(index)->CheckFlag(HInstruction::kTruncatingToInt32); 70b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch all_uses_everywhere_truncating_smi &= 71b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch phi_list->at(index)->CheckFlag(HInstruction::kTruncatingToSmi); 72b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch done.Add(index); 73b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 74b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 75b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (!all_uses_everywhere_truncating_int32) { 76b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Clear truncation flag of this group of connected phis. 77b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch for (BitVector::Iterator it(connected_phis[i]); 78b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch !it.Done(); 79b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch it.Advance()) { 80b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch int index = it.Current(); 81b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch phi_list->at(index)->ClearFlag(HInstruction::kTruncatingToInt32); 82b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 83b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 84b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (!all_uses_everywhere_truncating_smi) { 85b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Clear truncation flag of this group of connected phis. 86b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch for (BitVector::Iterator it(connected_phis[i]); 87b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch !it.Done(); 88b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch it.Advance()) { 89b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch int index = it.Current(); 90b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch phi_list->at(index)->ClearFlag(HInstruction::kTruncatingToSmi); 91b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 92b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 93b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 94b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 95b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 96b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Simplify constant phi inputs where possible. 97b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // This step uses kTruncatingToInt32 flags of phis. 98b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch for (int i = 0; i < phi_count; ++i) { 99b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch phi_list->at(i)->SimplifyConstantInputs(); 100b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 101b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 102b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Use the phi reachability information from step 2 to 103b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // sum up the non-phi use counts of all connected phis. 104b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch for (int i = 0; i < phi_count; ++i) { 105b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HPhi* phi = phi_list->at(i); 106b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch for (BitVector::Iterator it(connected_phis[i]); 107b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch !it.Done(); 108b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch it.Advance()) { 109b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch int index = it.Current(); 110b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HPhi* it_use = phi_list->at(index); 111b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (index != i) phi->AddNonPhiUsesFrom(it_use); // Don't count twice. 112b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 113b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 114b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 115b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Initialize work list 116b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch for (int i = 0; i < graph()->blocks()->length(); ++i) { 117b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HBasicBlock* block = graph()->blocks()->at(i); 118b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch const ZoneList<HPhi*>* phis = block->phis(); 119b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch for (int j = 0; j < phis->length(); ++j) { 120b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch AddToWorklist(phis->at(j)); 121b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 122b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 123b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch for (HInstructionIterator it(block); !it.Done(); it.Advance()) { 124b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HInstruction* current = it.Current(); 125b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch AddToWorklist(current); 126b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 127b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 128b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 129b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Do a fixed point iteration, trying to improve representations 130b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch while (!worklist_.is_empty()) { 131b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HValue* current = worklist_.RemoveLast(); 132b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch current->InferRepresentation(this); 133b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch in_worklist_.Remove(current->id()); 134b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 135b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 136b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Lastly: any instruction that we don't have representation information 137b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // for defaults to Tagged. 138b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch for (int i = 0; i < graph()->blocks()->length(); ++i) { 139b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HBasicBlock* block = graph()->blocks()->at(i); 140b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch const ZoneList<HPhi*>* phis = block->phis(); 141b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch for (int j = 0; j < phis->length(); ++j) { 142b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HPhi* phi = phis->at(j); 143b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (phi->representation().IsNone()) { 144b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch phi->ChangeRepresentation(Representation::Tagged()); 145b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 146b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 147b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch for (HInstructionIterator it(block); !it.Done(); it.Advance()) { 148b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HInstruction* current = it.Current(); 149b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (current->representation().IsNone() && 150b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch current->CheckFlag(HInstruction::kFlexibleRepresentation)) { 151b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (current->CheckFlag(HInstruction::kCannotBeTagged)) { 152b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch current->ChangeRepresentation(Representation::Double()); 153b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } else { 154b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch current->ChangeRepresentation(Representation::Tagged()); 155b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 156b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 157b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 158b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 159b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch} 160b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 161b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch} } // namespace v8::internal 162