Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 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/crankshaft/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 | } |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 74 | } |
| 75 | } |
| 76 | |
| 77 | // Continue analysis in all dominated blocks. |
| 78 | const ZoneList<HBasicBlock*>* dominated_blocks(block->dominated_blocks()); |
| 79 | if (!dominated_blocks->is_empty()) { |
| 80 | // Continue with first dominated block, and push the |
| 81 | // remaining blocks on the stack (in reverse order). |
| 82 | int last_changed_range = changed_ranges_.length(); |
| 83 | for (int i = dominated_blocks->length() - 1; i > 0; --i) { |
| 84 | stack.Add(Pending(dominated_blocks->at(i), last_changed_range), zone()); |
| 85 | } |
| 86 | block = dominated_blocks->at(0); |
| 87 | } else if (!stack.is_empty()) { |
| 88 | // Pop next pending block from stack. |
| 89 | Pending pending = stack.RemoveLast(); |
| 90 | RollBackTo(pending.last_changed_range()); |
| 91 | block = pending.block(); |
| 92 | } else { |
| 93 | // All blocks done. |
| 94 | block = NULL; |
| 95 | } |
| 96 | } |
| 97 | |
| 98 | // The ranges are not valid anymore due to SSI vs. SSA! |
| 99 | PoisonRanges(); |
| 100 | } |
| 101 | |
| 102 | |
| 103 | void HRangeAnalysisPhase::PoisonRanges() { |
| 104 | #ifdef DEBUG |
| 105 | for (int i = 0; i < graph()->blocks()->length(); ++i) { |
| 106 | HBasicBlock* block = graph()->blocks()->at(i); |
| 107 | for (HInstructionIterator it(block); !it.Done(); it.Advance()) { |
| 108 | HInstruction* instr = it.Current(); |
| 109 | if (instr->HasRange()) instr->PoisonRange(); |
| 110 | } |
| 111 | } |
| 112 | #endif |
| 113 | } |
| 114 | |
| 115 | |
| 116 | void HRangeAnalysisPhase::InferControlFlowRange(HCompareNumericAndBranch* test, |
| 117 | HBasicBlock* dest) { |
| 118 | DCHECK((test->FirstSuccessor() == dest) == (test->SecondSuccessor() != dest)); |
| 119 | if (test->representation().IsSmiOrInteger32()) { |
| 120 | Token::Value op = test->token(); |
| 121 | if (test->SecondSuccessor() == dest) { |
| 122 | op = Token::NegateCompareOp(op); |
| 123 | } |
| 124 | Token::Value inverted_op = Token::ReverseCompareOp(op); |
| 125 | UpdateControlFlowRange(op, test->left(), test->right()); |
| 126 | UpdateControlFlowRange(inverted_op, test->right(), test->left()); |
| 127 | } |
| 128 | } |
| 129 | |
| 130 | |
| 131 | // We know that value [op] other. Use this information to update the range on |
| 132 | // value. |
| 133 | void HRangeAnalysisPhase::UpdateControlFlowRange(Token::Value op, |
| 134 | HValue* value, |
| 135 | HValue* other) { |
| 136 | Range temp_range; |
| 137 | Range* range = other->range() != NULL ? other->range() : &temp_range; |
| 138 | Range* new_range = NULL; |
| 139 | |
| 140 | TraceRange("Control flow range infer %d %s %d\n", |
| 141 | value->id(), |
| 142 | Token::Name(op), |
| 143 | other->id()); |
| 144 | |
| 145 | if (op == Token::EQ || op == Token::EQ_STRICT) { |
| 146 | // The same range has to apply for value. |
| 147 | new_range = range->Copy(graph()->zone()); |
| 148 | } else if (op == Token::LT || op == Token::LTE) { |
| 149 | new_range = range->CopyClearLower(graph()->zone()); |
| 150 | if (op == Token::LT) { |
| 151 | new_range->AddConstant(-1); |
| 152 | } |
| 153 | } else if (op == Token::GT || op == Token::GTE) { |
| 154 | new_range = range->CopyClearUpper(graph()->zone()); |
| 155 | if (op == Token::GT) { |
| 156 | new_range->AddConstant(1); |
| 157 | } |
| 158 | } |
| 159 | |
| 160 | if (new_range != NULL && !new_range->IsMostGeneric()) { |
| 161 | AddRange(value, new_range); |
| 162 | } |
| 163 | } |
| 164 | |
| 165 | |
| 166 | void HRangeAnalysisPhase::InferRange(HValue* value) { |
| 167 | DCHECK(!value->HasRange()); |
| 168 | if (!value->representation().IsNone()) { |
| 169 | value->ComputeInitialRange(graph()->zone()); |
| 170 | Range* range = value->range(); |
| 171 | TraceRange("Initial inferred range of %d (%s) set to [%d,%d]\n", |
| 172 | value->id(), |
| 173 | value->Mnemonic(), |
| 174 | range->lower(), |
| 175 | range->upper()); |
| 176 | } |
| 177 | } |
| 178 | |
| 179 | |
| 180 | void HRangeAnalysisPhase::RollBackTo(int index) { |
| 181 | DCHECK(index <= changed_ranges_.length()); |
| 182 | for (int i = index; i < changed_ranges_.length(); ++i) { |
| 183 | changed_ranges_[i]->RemoveLastAddedRange(); |
| 184 | } |
| 185 | changed_ranges_.Rewind(index); |
| 186 | } |
| 187 | |
| 188 | |
| 189 | void HRangeAnalysisPhase::AddRange(HValue* value, Range* range) { |
| 190 | Range* original_range = value->range(); |
| 191 | value->AddNewRange(range, graph()->zone()); |
| 192 | changed_ranges_.Add(value, zone()); |
| 193 | Range* new_range = value->range(); |
| 194 | TraceRange("Updated range of %d set to [%d,%d]\n", |
| 195 | value->id(), |
| 196 | new_range->lower(), |
| 197 | new_range->upper()); |
| 198 | if (original_range != NULL) { |
| 199 | TraceRange("Original range was [%d,%d]\n", |
| 200 | original_range->lower(), |
| 201 | original_range->upper()); |
| 202 | } |
| 203 | TraceRange("New information was [%d,%d]\n", |
| 204 | range->lower(), |
| 205 | range->upper()); |
| 206 | } |
| 207 | |
| 208 | |
| 209 | void HRangeAnalysisPhase::PropagateMinusZeroChecks(HValue* value) { |
| 210 | DCHECK(worklist_.is_empty()); |
| 211 | DCHECK(in_worklist_.IsEmpty()); |
| 212 | |
| 213 | AddToWorklist(value); |
| 214 | while (!worklist_.is_empty()) { |
| 215 | value = worklist_.RemoveLast(); |
| 216 | |
| 217 | if (value->IsPhi()) { |
| 218 | // For phis, we must propagate the check to all of its inputs. |
| 219 | HPhi* phi = HPhi::cast(value); |
| 220 | for (int i = 0; i < phi->OperandCount(); ++i) { |
| 221 | AddToWorklist(phi->OperandAt(i)); |
| 222 | } |
| 223 | } else if (value->IsUnaryMathOperation()) { |
| 224 | HUnaryMathOperation* instr = HUnaryMathOperation::cast(value); |
| 225 | if (instr->representation().IsSmiOrInteger32() && |
| 226 | !instr->value()->representation().Equals(instr->representation())) { |
| 227 | if (instr->value()->range() == NULL || |
| 228 | instr->value()->range()->CanBeMinusZero()) { |
| 229 | instr->SetFlag(HValue::kBailoutOnMinusZero); |
| 230 | } |
| 231 | } |
| 232 | if (instr->RequiredInputRepresentation(0).IsSmiOrInteger32() && |
| 233 | instr->representation().Equals( |
| 234 | instr->RequiredInputRepresentation(0))) { |
| 235 | AddToWorklist(instr->value()); |
| 236 | } |
| 237 | } else if (value->IsChange()) { |
| 238 | HChange* instr = HChange::cast(value); |
| 239 | if (!instr->from().IsSmiOrInteger32() && |
| 240 | !instr->CanTruncateToInt32() && |
| 241 | (instr->value()->range() == NULL || |
| 242 | instr->value()->range()->CanBeMinusZero())) { |
| 243 | instr->SetFlag(HValue::kBailoutOnMinusZero); |
| 244 | } |
| 245 | } else if (value->IsForceRepresentation()) { |
| 246 | HForceRepresentation* instr = HForceRepresentation::cast(value); |
| 247 | AddToWorklist(instr->value()); |
| 248 | } else if (value->IsMod()) { |
| 249 | HMod* instr = HMod::cast(value); |
| 250 | if (instr->range() == NULL || instr->range()->CanBeMinusZero()) { |
| 251 | instr->SetFlag(HValue::kBailoutOnMinusZero); |
| 252 | AddToWorklist(instr->left()); |
| 253 | } |
| 254 | } else if (value->IsDiv() || value->IsMul()) { |
| 255 | HBinaryOperation* instr = HBinaryOperation::cast(value); |
| 256 | if (instr->range() == NULL || instr->range()->CanBeMinusZero()) { |
| 257 | instr->SetFlag(HValue::kBailoutOnMinusZero); |
| 258 | } |
| 259 | AddToWorklist(instr->right()); |
| 260 | AddToWorklist(instr->left()); |
| 261 | } else if (value->IsMathFloorOfDiv()) { |
| 262 | HMathFloorOfDiv* instr = HMathFloorOfDiv::cast(value); |
| 263 | instr->SetFlag(HValue::kBailoutOnMinusZero); |
| 264 | } else if (value->IsAdd() || value->IsSub()) { |
| 265 | HBinaryOperation* instr = HBinaryOperation::cast(value); |
| 266 | if (instr->range() == NULL || instr->range()->CanBeMinusZero()) { |
| 267 | // Propagate to the left argument. If the left argument cannot be -0, |
| 268 | // then the result of the add/sub operation cannot be either. |
| 269 | AddToWorklist(instr->left()); |
| 270 | } |
| 271 | } else if (value->IsMathMinMax()) { |
| 272 | HMathMinMax* instr = HMathMinMax::cast(value); |
| 273 | AddToWorklist(instr->right()); |
| 274 | AddToWorklist(instr->left()); |
| 275 | } |
| 276 | } |
| 277 | |
| 278 | in_worklist_.Clear(); |
| 279 | DCHECK(in_worklist_.IsEmpty()); |
| 280 | DCHECK(worklist_.is_empty()); |
| 281 | } |
| 282 | |
| 283 | |
| 284 | } // namespace internal |
| 285 | } // namespace v8 |