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