| OLD | NEW |
|---|
| (Empty) |
| 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 base::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 DCHECK(from.Equals(instr->from())); | |
| 68 if (from.IsSmiOrInteger32()) { | |
| 69 DCHECK(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 DCHECK((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 DCHECK(!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 DCHECK(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 DCHECK(worklist_.is_empty()); | |
| 217 DCHECK(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 DCHECK(in_worklist_.IsEmpty()); | |
| 286 DCHECK(worklist_.is_empty()); | |
| 287 } | |
| 288 | |
| 289 | |
| 290 } // namespace internal | |
| 291 } // namespace v8 | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 1405363003:
Move Hydrogen and Lithium to src/crankshaft/ (Closed)
Base URL: https://chromium.googlesource.com/v8/v8.git@master