hydrogen-range-analysis.cc 9.38 KB
Newer Older
1
// Copyright 2013 the V8 project authors. All rights reserved.
2 3
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
4

5
#include "src/crankshaft/hydrogen-range-analysis.h"
6 7 8 9 10

namespace v8 {
namespace internal {


11 12 13 14 15 16 17 18 19 20 21 22 23 24
class Pending {
 public:
  Pending(HBasicBlock* block, int last_changed_range)
      : block_(block), last_changed_range_(last_changed_range) {}

  HBasicBlock* block() const { return block_; }
  int last_changed_range() const { return last_changed_range_; }

 private:
  HBasicBlock* block_;
  int last_changed_range_;
};


25 26 27 28
void HRangeAnalysisPhase::TraceRange(const char* msg, ...) {
  if (FLAG_trace_range) {
    va_list arguments;
    va_start(arguments, msg);
29
    base::OS::VPrint(msg, arguments);
30 31 32 33 34
    va_end(arguments);
  }
}


35 36 37 38 39
void HRangeAnalysisPhase::Run() {
  HBasicBlock* block(graph()->entry_block());
  ZoneList<Pending> stack(graph()->blocks()->length(), zone());
  while (block != NULL) {
    TraceRange("Analyzing block B%d\n", block->block_id());
40

41 42 43 44 45 46 47
    // Infer range based on control flow.
    if (block->predecessors()->length() == 1) {
      HBasicBlock* pred = block->predecessors()->first();
      if (pred->end()->IsCompareNumericAndBranch()) {
        InferControlFlowRange(HCompareNumericAndBranch::cast(pred->end()),
                              block);
      }
48 49
    }

50 51 52 53 54
    // Process phi instructions.
    for (int i = 0; i < block->phis()->length(); ++i) {
      HPhi* phi = block->phis()->at(i);
      InferRange(phi);
    }
55

56 57
    // Go through all instructions of the current block.
    for (HInstructionIterator it(block); !it.Done(); it.Advance()) {
58 59 60 61 62 63 64 65 66
      HValue* value = it.Current();
      InferRange(value);

      // Compute the bailout-on-minus-zero flag.
      if (value->IsChange()) {
        HChange* instr = HChange::cast(value);
        // Propagate flags for negative zero checks upwards from conversions
        // int32-to-tagged and int32-to-double.
        Representation from = instr->value()->representation();
67
        DCHECK(from.Equals(instr->from()));
68
        if (from.IsSmiOrInteger32()) {
69
          DCHECK(instr->to().IsTagged() ||
70 71 72 73 74
                instr->to().IsDouble() ||
                instr->to().IsSmiOrInteger32());
          PropagateMinusZeroChecks(instr->value());
        }
      }
75
    }
76

77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95
    // Continue analysis in all dominated blocks.
    const ZoneList<HBasicBlock*>* dominated_blocks(block->dominated_blocks());
    if (!dominated_blocks->is_empty()) {
      // Continue with first dominated block, and push the
      // remaining blocks on the stack (in reverse order).
      int last_changed_range = changed_ranges_.length();
      for (int i = dominated_blocks->length() - 1; i > 0; --i) {
        stack.Add(Pending(dominated_blocks->at(i), last_changed_range), zone());
      }
      block = dominated_blocks->at(0);
    } else if (!stack.is_empty()) {
      // Pop next pending block from stack.
      Pending pending = stack.RemoveLast();
      RollBackTo(pending.last_changed_range());
      block = pending.block();
    } else {
      // All blocks done.
      block = NULL;
    }
96
  }
97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112

  // The ranges are not valid anymore due to SSI vs. SSA!
  PoisonRanges();
}


void HRangeAnalysisPhase::PoisonRanges() {
#ifdef DEBUG
  for (int i = 0; i < graph()->blocks()->length(); ++i) {
    HBasicBlock* block = graph()->blocks()->at(i);
    for (HInstructionIterator it(block); !it.Done(); it.Advance()) {
      HInstruction* instr = it.Current();
      if (instr->HasRange()) instr->PoisonRange();
    }
  }
#endif
113 114 115
}


116
void HRangeAnalysisPhase::InferControlFlowRange(HCompareNumericAndBranch* test,
117
                                                HBasicBlock* dest) {
118
  DCHECK((test->FirstSuccessor() == dest) == (test->SecondSuccessor() != dest));
119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166
  if (test->representation().IsSmiOrInteger32()) {
    Token::Value op = test->token();
    if (test->SecondSuccessor() == dest) {
      op = Token::NegateCompareOp(op);
    }
    Token::Value inverted_op = Token::ReverseCompareOp(op);
    UpdateControlFlowRange(op, test->left(), test->right());
    UpdateControlFlowRange(inverted_op, test->right(), test->left());
  }
}


// We know that value [op] other. Use this information to update the range on
// value.
void HRangeAnalysisPhase::UpdateControlFlowRange(Token::Value op,
                                                 HValue* value,
                                                 HValue* other) {
  Range temp_range;
  Range* range = other->range() != NULL ? other->range() : &temp_range;
  Range* new_range = NULL;

  TraceRange("Control flow range infer %d %s %d\n",
             value->id(),
             Token::Name(op),
             other->id());

  if (op == Token::EQ || op == Token::EQ_STRICT) {
    // The same range has to apply for value.
    new_range = range->Copy(graph()->zone());
  } else if (op == Token::LT || op == Token::LTE) {
    new_range = range->CopyClearLower(graph()->zone());
    if (op == Token::LT) {
      new_range->AddConstant(-1);
    }
  } else if (op == Token::GT || op == Token::GTE) {
    new_range = range->CopyClearUpper(graph()->zone());
    if (op == Token::GT) {
      new_range->AddConstant(1);
    }
  }

  if (new_range != NULL && !new_range->IsMostGeneric()) {
    AddRange(value, new_range);
  }
}


void HRangeAnalysisPhase::InferRange(HValue* value) {
167
  DCHECK(!value->HasRange());
168 169 170 171 172 173 174 175 176 177 178 179 180
  if (!value->representation().IsNone()) {
    value->ComputeInitialRange(graph()->zone());
    Range* range = value->range();
    TraceRange("Initial inferred range of %d (%s) set to [%d,%d]\n",
               value->id(),
               value->Mnemonic(),
               range->lower(),
               range->upper());
  }
}


void HRangeAnalysisPhase::RollBackTo(int index) {
181
  DCHECK(index <= changed_ranges_.length());
182
  for (int i = index; i < changed_ranges_.length(); ++i) {
183 184
    changed_ranges_[i]->RemoveLastAddedRange();
  }
185
  changed_ranges_.Rewind(index);
186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208
}


void HRangeAnalysisPhase::AddRange(HValue* value, Range* range) {
  Range* original_range = value->range();
  value->AddNewRange(range, graph()->zone());
  changed_ranges_.Add(value, zone());
  Range* new_range = value->range();
  TraceRange("Updated range of %d set to [%d,%d]\n",
             value->id(),
             new_range->lower(),
             new_range->upper());
  if (original_range != NULL) {
    TraceRange("Original range was [%d,%d]\n",
               original_range->lower(),
               original_range->upper());
  }
  TraceRange("New information was [%d,%d]\n",
             range->lower(),
             range->upper());
}


209
void HRangeAnalysisPhase::PropagateMinusZeroChecks(HValue* value) {
210 211
  DCHECK(worklist_.is_empty());
  DCHECK(in_worklist_.IsEmpty());
212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278

  AddToWorklist(value);
  while (!worklist_.is_empty()) {
    value = worklist_.RemoveLast();

    if (value->IsPhi()) {
      // For phis, we must propagate the check to all of its inputs.
      HPhi* phi = HPhi::cast(value);
      for (int i = 0; i < phi->OperandCount(); ++i) {
        AddToWorklist(phi->OperandAt(i));
      }
    } else if (value->IsUnaryMathOperation()) {
      HUnaryMathOperation* instr = HUnaryMathOperation::cast(value);
      if (instr->representation().IsSmiOrInteger32() &&
          !instr->value()->representation().Equals(instr->representation())) {
        if (instr->value()->range() == NULL ||
            instr->value()->range()->CanBeMinusZero()) {
          instr->SetFlag(HValue::kBailoutOnMinusZero);
        }
      }
      if (instr->RequiredInputRepresentation(0).IsSmiOrInteger32() &&
          instr->representation().Equals(
              instr->RequiredInputRepresentation(0))) {
        AddToWorklist(instr->value());
      }
    } else if (value->IsChange()) {
      HChange* instr = HChange::cast(value);
      if (!instr->from().IsSmiOrInteger32() &&
          !instr->CanTruncateToInt32() &&
          (instr->value()->range() == NULL ||
           instr->value()->range()->CanBeMinusZero())) {
        instr->SetFlag(HValue::kBailoutOnMinusZero);
      }
    } else if (value->IsForceRepresentation()) {
      HForceRepresentation* instr = HForceRepresentation::cast(value);
      AddToWorklist(instr->value());
    } else if (value->IsMod()) {
      HMod* instr = HMod::cast(value);
      if (instr->range() == NULL || instr->range()->CanBeMinusZero()) {
        instr->SetFlag(HValue::kBailoutOnMinusZero);
        AddToWorklist(instr->left());
      }
    } else if (value->IsDiv() || value->IsMul()) {
      HBinaryOperation* instr = HBinaryOperation::cast(value);
      if (instr->range() == NULL || instr->range()->CanBeMinusZero()) {
        instr->SetFlag(HValue::kBailoutOnMinusZero);
      }
      AddToWorklist(instr->right());
      AddToWorklist(instr->left());
    } else if (value->IsMathFloorOfDiv()) {
      HMathFloorOfDiv* instr = HMathFloorOfDiv::cast(value);
      instr->SetFlag(HValue::kBailoutOnMinusZero);
    } else if (value->IsAdd() || value->IsSub()) {
      HBinaryOperation* instr = HBinaryOperation::cast(value);
      if (instr->range() == NULL || instr->range()->CanBeMinusZero()) {
        // Propagate to the left argument. If the left argument cannot be -0,
        // then the result of the add/sub operation cannot be either.
        AddToWorklist(instr->left());
      }
    } else if (value->IsMathMinMax()) {
      HMathMinMax* instr = HMathMinMax::cast(value);
      AddToWorklist(instr->right());
      AddToWorklist(instr->left());
    }
  }

  in_worklist_.Clear();
279 280
  DCHECK(in_worklist_.IsEmpty());
  DCHECK(worklist_.is_empty());
281 282 283
}


284 285
}  // namespace internal
}  // namespace v8