1// Copyright 2013 the V8 project authors. All rights reserved. 2// Redistribution and use in source and binary forms, with or without 3// modification, are permitted provided that the following conditions are 4// met: 5// 6// * Redistributions of source code must retain the above copyright 7// notice, this list of conditions and the following disclaimer. 8// * Redistributions in binary form must reproduce the above 9// copyright notice, this list of conditions and the following 10// disclaimer in the documentation and/or other materials provided 11// with the distribution. 12// * Neither the name of Google Inc. nor the names of its 13// contributors may be used to endorse or promote products derived 14// from this software without specific prior written permission. 15// 16// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 17// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 18// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 19// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 20// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 21// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 22// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 23// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 24// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 25// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 26// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 27 28#include "hydrogen-infer-representation.h" 29 30namespace v8 { 31namespace internal { 32 33void HInferRepresentationPhase::AddToWorklist(HValue* current) { 34 if (current->representation().IsTagged()) return; 35 if (!current->CheckFlag(HValue::kFlexibleRepresentation)) return; 36 if (in_worklist_.Contains(current->id())) return; 37 worklist_.Add(current, zone()); 38 in_worklist_.Add(current->id()); 39} 40 41 42void HInferRepresentationPhase::Run() { 43 // (1) Initialize bit vectors and count real uses. Each phi gets a 44 // bit-vector of length <number of phis>. 45 const ZoneList<HPhi*>* phi_list = graph()->phi_list(); 46 int phi_count = phi_list->length(); 47 ZoneList<BitVector*> connected_phis(phi_count, zone()); 48 for (int i = 0; i < phi_count; ++i) { 49 phi_list->at(i)->InitRealUses(i); 50 BitVector* connected_set = new(zone()) BitVector(phi_count, zone()); 51 connected_set->Add(i); 52 connected_phis.Add(connected_set, zone()); 53 } 54 55 // (2) Do a fixed point iteration to find the set of connected phis. A 56 // phi is connected to another phi if its value is used either directly or 57 // indirectly through a transitive closure of the def-use relation. 58 bool change = true; 59 while (change) { 60 change = false; 61 // We normally have far more "forward edges" than "backward edges", 62 // so we terminate faster when we walk backwards. 63 for (int i = phi_count - 1; i >= 0; --i) { 64 HPhi* phi = phi_list->at(i); 65 for (HUseIterator it(phi->uses()); !it.Done(); it.Advance()) { 66 HValue* use = it.value(); 67 if (use->IsPhi()) { 68 int id = HPhi::cast(use)->phi_id(); 69 if (connected_phis[i]->UnionIsChanged(*connected_phis[id])) 70 change = true; 71 } 72 } 73 } 74 } 75 76 // Set truncation flags for groups of connected phis. This is a conservative 77 // approximation; the flag will be properly re-computed after representations 78 // have been determined. 79 if (phi_count > 0) { 80 BitVector done(phi_count, zone()); 81 for (int i = 0; i < phi_count; ++i) { 82 if (done.Contains(i)) continue; 83 84 // Check if all uses of all connected phis in this group are truncating. 85 bool all_uses_everywhere_truncating_int32 = true; 86 bool all_uses_everywhere_truncating_smi = true; 87 for (BitVector::Iterator it(connected_phis[i]); 88 !it.Done(); 89 it.Advance()) { 90 int index = it.Current(); 91 all_uses_everywhere_truncating_int32 &= 92 phi_list->at(index)->CheckFlag(HInstruction::kTruncatingToInt32); 93 all_uses_everywhere_truncating_smi &= 94 phi_list->at(index)->CheckFlag(HInstruction::kTruncatingToSmi); 95 done.Add(index); 96 } 97 98 if (!all_uses_everywhere_truncating_int32) { 99 // Clear truncation flag of this group of connected phis. 100 for (BitVector::Iterator it(connected_phis[i]); 101 !it.Done(); 102 it.Advance()) { 103 int index = it.Current(); 104 phi_list->at(index)->ClearFlag(HInstruction::kTruncatingToInt32); 105 } 106 } 107 if (!all_uses_everywhere_truncating_smi) { 108 // Clear truncation flag of this group of connected phis. 109 for (BitVector::Iterator it(connected_phis[i]); 110 !it.Done(); 111 it.Advance()) { 112 int index = it.Current(); 113 phi_list->at(index)->ClearFlag(HInstruction::kTruncatingToSmi); 114 } 115 } 116 } 117 } 118 119 // Simplify constant phi inputs where possible. 120 // This step uses kTruncatingToInt32 flags of phis. 121 for (int i = 0; i < phi_count; ++i) { 122 phi_list->at(i)->SimplifyConstantInputs(); 123 } 124 125 // Use the phi reachability information from step 2 to 126 // sum up the non-phi use counts of all connected phis. 127 for (int i = 0; i < phi_count; ++i) { 128 HPhi* phi = phi_list->at(i); 129 for (BitVector::Iterator it(connected_phis[i]); 130 !it.Done(); 131 it.Advance()) { 132 int index = it.Current(); 133 HPhi* it_use = phi_list->at(index); 134 if (index != i) phi->AddNonPhiUsesFrom(it_use); // Don't count twice. 135 } 136 } 137 138 // Initialize work list 139 for (int i = 0; i < graph()->blocks()->length(); ++i) { 140 HBasicBlock* block = graph()->blocks()->at(i); 141 const ZoneList<HPhi*>* phis = block->phis(); 142 for (int j = 0; j < phis->length(); ++j) { 143 AddToWorklist(phis->at(j)); 144 } 145 146 for (HInstructionIterator it(block); !it.Done(); it.Advance()) { 147 HInstruction* current = it.Current(); 148 AddToWorklist(current); 149 } 150 } 151 152 // Do a fixed point iteration, trying to improve representations 153 while (!worklist_.is_empty()) { 154 HValue* current = worklist_.RemoveLast(); 155 current->InferRepresentation(this); 156 in_worklist_.Remove(current->id()); 157 } 158 159 // Lastly: any instruction that we don't have representation information 160 // for defaults to Tagged. 161 for (int i = 0; i < graph()->blocks()->length(); ++i) { 162 HBasicBlock* block = graph()->blocks()->at(i); 163 const ZoneList<HPhi*>* phis = block->phis(); 164 for (int j = 0; j < phis->length(); ++j) { 165 HPhi* phi = phis->at(j); 166 if (phi->representation().IsNone()) { 167 phi->ChangeRepresentation(Representation::Tagged()); 168 } 169 } 170 for (HInstructionIterator it(block); !it.Done(); it.Advance()) { 171 HInstruction* current = it.Current(); 172 if (current->representation().IsNone() && 173 current->CheckFlag(HInstruction::kFlexibleRepresentation)) { 174 if (current->CheckFlag(HInstruction::kCannotBeTagged)) { 175 current->ChangeRepresentation(Representation::Double()); 176 } else { 177 current->ChangeRepresentation(Representation::Tagged()); 178 } 179 } 180 } 181 } 182} 183 184} } // namespace v8::internal 185