Home | History | Annotate | Download | only in crankshaft 
      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         }
     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
    286