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       } 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
    292