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-range-analysis.h" 6 7 namespace v8 { 8 namespace internal { 9 10 11 class Pending { 12 public: 13 Pending(HBasicBlock* block, int last_changed_range) 14 : block_(block), last_changed_range_(last_changed_range) {} 15 16 HBasicBlock* block() const { return block_; } 17 int last_changed_range() const { return last_changed_range_; } 18 19 private: 20 HBasicBlock* block_; 21 int last_changed_range_; 22 }; 23 24 25 void HRangeAnalysisPhase::TraceRange(const char* msg, ...) { 26 if (FLAG_trace_range) { 27 va_list arguments; 28 va_start(arguments, msg); 29 OS::VPrint(msg, arguments); 30 va_end(arguments); 31 } 32 } 33 34 35 void HRangeAnalysisPhase::Run() { 36 HBasicBlock* block(graph()->entry_block()); 37 ZoneList<Pending> stack(graph()->blocks()->length(), zone()); 38 while (block != NULL) { 39 TraceRange("Analyzing block B%d\n", block->block_id()); 40 41 // Infer range based on control flow. 42 if (block->predecessors()->length() == 1) { 43 HBasicBlock* pred = block->predecessors()->first(); 44 if (pred->end()->IsCompareNumericAndBranch()) { 45 InferControlFlowRange(HCompareNumericAndBranch::cast(pred->end()), 46 block); 47 } 48 } 49 50 // Process phi instructions. 51 for (int i = 0; i < block->phis()->length(); ++i) { 52 HPhi* phi = block->phis()->at(i); 53 InferRange(phi); 54 } 55 56 // Go through all instructions of the current block. 57 for (HInstructionIterator it(block); !it.Done(); it.Advance()) { 58 HValue* value = it.Current(); 59 InferRange(value); 60 61 // Compute the bailout-on-minus-zero flag. 62 if (value->IsChange()) { 63 HChange* instr = HChange::cast(value); 64 // Propagate flags for negative zero checks upwards from conversions 65 // int32-to-tagged and int32-to-double. 66 Representation from = instr->value()->representation(); 67 ASSERT(from.Equals(instr->from())); 68 if (from.IsSmiOrInteger32()) { 69 ASSERT(instr->to().IsTagged() || 70 instr->to().IsDouble() || 71 instr->to().IsSmiOrInteger32()); 72 PropagateMinusZeroChecks(instr->value()); 73 } 74 } else if (value->IsCompareMinusZeroAndBranch()) { 75 HCompareMinusZeroAndBranch* instr = 76 HCompareMinusZeroAndBranch::cast(value); 77 if (instr->value()->representation().IsSmiOrInteger32()) { 78 PropagateMinusZeroChecks(instr->value()); 79 } 80 } 81 } 82 83 // Continue analysis in all dominated blocks. 84 const ZoneList<HBasicBlock*>* dominated_blocks(block->dominated_blocks()); 85 if (!dominated_blocks->is_empty()) { 86 // Continue with first dominated block, and push the 87 // remaining blocks on the stack (in reverse order). 88 int last_changed_range = changed_ranges_.length(); 89 for (int i = dominated_blocks->length() - 1; i > 0; --i) { 90 stack.Add(Pending(dominated_blocks->at(i), last_changed_range), zone()); 91 } 92 block = dominated_blocks->at(0); 93 } else if (!stack.is_empty()) { 94 // Pop next pending block from stack. 95 Pending pending = stack.RemoveLast(); 96 RollBackTo(pending.last_changed_range()); 97 block = pending.block(); 98 } else { 99 // All blocks done. 100 block = NULL; 101 } 102 } 103 104 // The ranges are not valid anymore due to SSI vs. SSA! 105 PoisonRanges(); 106 } 107 108 109 void HRangeAnalysisPhase::PoisonRanges() { 110 #ifdef DEBUG 111 for (int i = 0; i < graph()->blocks()->length(); ++i) { 112 HBasicBlock* block = graph()->blocks()->at(i); 113 for (HInstructionIterator it(block); !it.Done(); it.Advance()) { 114 HInstruction* instr = it.Current(); 115 if (instr->HasRange()) instr->PoisonRange(); 116 } 117 } 118 #endif 119 } 120 121 122 void HRangeAnalysisPhase::InferControlFlowRange(HCompareNumericAndBranch* test, 123 HBasicBlock* dest) { 124 ASSERT((test->FirstSuccessor() == dest) == (test->SecondSuccessor() != dest)); 125 if (test->representation().IsSmiOrInteger32()) { 126 Token::Value op = test->token(); 127 if (test->SecondSuccessor() == dest) { 128 op = Token::NegateCompareOp(op); 129 } 130 Token::Value inverted_op = Token::ReverseCompareOp(op); 131 UpdateControlFlowRange(op, test->left(), test->right()); 132 UpdateControlFlowRange(inverted_op, test->right(), test->left()); 133 } 134 } 135 136 137 // We know that value [op] other. Use this information to update the range on 138 // value. 139 void HRangeAnalysisPhase::UpdateControlFlowRange(Token::Value op, 140 HValue* value, 141 HValue* other) { 142 Range temp_range; 143 Range* range = other->range() != NULL ? other->range() : &temp_range; 144 Range* new_range = NULL; 145 146 TraceRange("Control flow range infer %d %s %d\n", 147 value->id(), 148 Token::Name(op), 149 other->id()); 150 151 if (op == Token::EQ || op == Token::EQ_STRICT) { 152 // The same range has to apply for value. 153 new_range = range->Copy(graph()->zone()); 154 } else if (op == Token::LT || op == Token::LTE) { 155 new_range = range->CopyClearLower(graph()->zone()); 156 if (op == Token::LT) { 157 new_range->AddConstant(-1); 158 } 159 } else if (op == Token::GT || op == Token::GTE) { 160 new_range = range->CopyClearUpper(graph()->zone()); 161 if (op == Token::GT) { 162 new_range->AddConstant(1); 163 } 164 } 165 166 if (new_range != NULL && !new_range->IsMostGeneric()) { 167 AddRange(value, new_range); 168 } 169 } 170 171 172 void HRangeAnalysisPhase::InferRange(HValue* value) { 173 ASSERT(!value->HasRange()); 174 if (!value->representation().IsNone()) { 175 value->ComputeInitialRange(graph()->zone()); 176 Range* range = value->range(); 177 TraceRange("Initial inferred range of %d (%s) set to [%d,%d]\n", 178 value->id(), 179 value->Mnemonic(), 180 range->lower(), 181 range->upper()); 182 } 183 } 184 185 186 void HRangeAnalysisPhase::RollBackTo(int index) { 187 ASSERT(index <= changed_ranges_.length()); 188 for (int i = index; i < changed_ranges_.length(); ++i) { 189 changed_ranges_[i]->RemoveLastAddedRange(); 190 } 191 changed_ranges_.Rewind(index); 192 } 193 194 195 void HRangeAnalysisPhase::AddRange(HValue* value, Range* range) { 196 Range* original_range = value->range(); 197 value->AddNewRange(range, graph()->zone()); 198 changed_ranges_.Add(value, zone()); 199 Range* new_range = value->range(); 200 TraceRange("Updated range of %d set to [%d,%d]\n", 201 value->id(), 202 new_range->lower(), 203 new_range->upper()); 204 if (original_range != NULL) { 205 TraceRange("Original range was [%d,%d]\n", 206 original_range->lower(), 207 original_range->upper()); 208 } 209 TraceRange("New information was [%d,%d]\n", 210 range->lower(), 211 range->upper()); 212 } 213 214 215 void HRangeAnalysisPhase::PropagateMinusZeroChecks(HValue* value) { 216 ASSERT(worklist_.is_empty()); 217 ASSERT(in_worklist_.IsEmpty()); 218 219 AddToWorklist(value); 220 while (!worklist_.is_empty()) { 221 value = worklist_.RemoveLast(); 222 223 if (value->IsPhi()) { 224 // For phis, we must propagate the check to all of its inputs. 225 HPhi* phi = HPhi::cast(value); 226 for (int i = 0; i < phi->OperandCount(); ++i) { 227 AddToWorklist(phi->OperandAt(i)); 228 } 229 } else if (value->IsUnaryMathOperation()) { 230 HUnaryMathOperation* instr = HUnaryMathOperation::cast(value); 231 if (instr->representation().IsSmiOrInteger32() && 232 !instr->value()->representation().Equals(instr->representation())) { 233 if (instr->value()->range() == NULL || 234 instr->value()->range()->CanBeMinusZero()) { 235 instr->SetFlag(HValue::kBailoutOnMinusZero); 236 } 237 } 238 if (instr->RequiredInputRepresentation(0).IsSmiOrInteger32() && 239 instr->representation().Equals( 240 instr->RequiredInputRepresentation(0))) { 241 AddToWorklist(instr->value()); 242 } 243 } else if (value->IsChange()) { 244 HChange* instr = HChange::cast(value); 245 if (!instr->from().IsSmiOrInteger32() && 246 !instr->CanTruncateToInt32() && 247 (instr->value()->range() == NULL || 248 instr->value()->range()->CanBeMinusZero())) { 249 instr->SetFlag(HValue::kBailoutOnMinusZero); 250 } 251 } else if (value->IsForceRepresentation()) { 252 HForceRepresentation* instr = HForceRepresentation::cast(value); 253 AddToWorklist(instr->value()); 254 } else if (value->IsMod()) { 255 HMod* instr = HMod::cast(value); 256 if (instr->range() == NULL || instr->range()->CanBeMinusZero()) { 257 instr->SetFlag(HValue::kBailoutOnMinusZero); 258 AddToWorklist(instr->left()); 259 } 260 } else if (value->IsDiv() || value->IsMul()) { 261 HBinaryOperation* instr = HBinaryOperation::cast(value); 262 if (instr->range() == NULL || instr->range()->CanBeMinusZero()) { 263 instr->SetFlag(HValue::kBailoutOnMinusZero); 264 } 265 AddToWorklist(instr->right()); 266 AddToWorklist(instr->left()); 267 } else if (value->IsMathFloorOfDiv()) { 268 HMathFloorOfDiv* instr = HMathFloorOfDiv::cast(value); 269 instr->SetFlag(HValue::kBailoutOnMinusZero); 270 } else if (value->IsAdd() || value->IsSub()) { 271 HBinaryOperation* instr = HBinaryOperation::cast(value); 272 if (instr->range() == NULL || instr->range()->CanBeMinusZero()) { 273 // Propagate to the left argument. If the left argument cannot be -0, 274 // then the result of the add/sub operation cannot be either. 275 AddToWorklist(instr->left()); 276 } 277 } else if (value->IsMathMinMax()) { 278 HMathMinMax* instr = HMathMinMax::cast(value); 279 AddToWorklist(instr->right()); 280 AddToWorklist(instr->left()); 281 } 282 } 283 284 in_worklist_.Clear(); 285 ASSERT(in_worklist_.IsEmpty()); 286 ASSERT(worklist_.is_empty()); 287 } 288 289 290 } } // namespace v8::internal 291
