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 #include "src/objects-inl.h"
      7 
      8 namespace v8 {
      9 namespace internal {
     10 
     11 
     12 class Pending {
     13  public:
     14   Pending(HBasicBlock* block, int last_changed_range)
     15       : block_(block), last_changed_range_(last_changed_range) {}
     16 
     17   HBasicBlock* block() const { return block_; }
     18   int last_changed_range() const { return last_changed_range_; }
     19 
     20  private:
     21   HBasicBlock* block_;
     22   int last_changed_range_;
     23 };
     24 
     25 
     26 void HRangeAnalysisPhase::TraceRange(const char* msg, ...) {
     27   if (FLAG_trace_range) {
     28     va_list arguments;
     29     va_start(arguments, msg);
     30     base::OS::VPrint(msg, arguments);
     31     va_end(arguments);
     32   }
     33 }
     34 
     35 
     36 void HRangeAnalysisPhase::Run() {
     37   HBasicBlock* block(graph()->entry_block());
     38   ZoneList<Pending> stack(graph()->blocks()->length(), zone());
     39   while (block != NULL) {
     40     TraceRange("Analyzing block B%d\n", block->block_id());
     41 
     42     // Infer range based on control flow.
     43     if (block->predecessors()->length() == 1) {
     44       HBasicBlock* pred = block->predecessors()->first();
     45       if (pred->end()->IsCompareNumericAndBranch()) {
     46         InferControlFlowRange(HCompareNumericAndBranch::cast(pred->end()),
     47                               block);
     48       }
     49     }
     50 
     51     // Process phi instructions.
     52     for (int i = 0; i < block->phis()->length(); ++i) {
     53       HPhi* phi = block->phis()->at(i);
     54       InferRange(phi);
     55     }
     56 
     57     // Go through all instructions of the current block.
     58     for (HInstructionIterator it(block); !it.Done(); it.Advance()) {
     59       HValue* value = it.Current();
     60       InferRange(value);
     61 
     62       // Compute the bailout-on-minus-zero flag.
     63       if (value->IsChange()) {
     64         HChange* instr = HChange::cast(value);
     65         // Propagate flags for negative zero checks upwards from conversions
     66         // int32-to-tagged and int32-to-double.
     67         Representation from = instr->value()->representation();
     68         DCHECK(from.Equals(instr->from()));
     69         if (from.IsSmiOrInteger32()) {
     70           DCHECK(instr->to().IsTagged() ||
     71                 instr->to().IsDouble() ||
     72                 instr->to().IsSmiOrInteger32());
     73           PropagateMinusZeroChecks(instr->value());
     74         }
     75       }
     76     }
     77 
     78     // Continue analysis in all dominated blocks.
     79     const ZoneList<HBasicBlock*>* dominated_blocks(block->dominated_blocks());
     80     if (!dominated_blocks->is_empty()) {
     81       // Continue with first dominated block, and push the
     82       // remaining blocks on the stack (in reverse order).
     83       int last_changed_range = changed_ranges_.length();
     84       for (int i = dominated_blocks->length() - 1; i > 0; --i) {
     85         stack.Add(Pending(dominated_blocks->at(i), last_changed_range), zone());
     86       }
     87       block = dominated_blocks->at(0);
     88     } else if (!stack.is_empty()) {
     89       // Pop next pending block from stack.
     90       Pending pending = stack.RemoveLast();
     91       RollBackTo(pending.last_changed_range());
     92       block = pending.block();
     93     } else {
     94       // All blocks done.
     95       block = NULL;
     96     }
     97   }
     98 
     99   // The ranges are not valid anymore due to SSI vs. SSA!
    100   PoisonRanges();
    101 }
    102 
    103 
    104 void HRangeAnalysisPhase::PoisonRanges() {
    105 #ifdef DEBUG
    106   for (int i = 0; i < graph()->blocks()->length(); ++i) {
    107     HBasicBlock* block = graph()->blocks()->at(i);
    108     for (HInstructionIterator it(block); !it.Done(); it.Advance()) {
    109       HInstruction* instr = it.Current();
    110       if (instr->HasRange()) instr->PoisonRange();
    111     }
    112   }
    113 #endif
    114 }
    115 
    116 
    117 void HRangeAnalysisPhase::InferControlFlowRange(HCompareNumericAndBranch* test,
    118                                                 HBasicBlock* dest) {
    119   DCHECK((test->FirstSuccessor() == dest) == (test->SecondSuccessor() != dest));
    120   if (test->representation().IsSmiOrInteger32()) {
    121     Token::Value op = test->token();
    122     if (test->SecondSuccessor() == dest) {
    123       op = Token::NegateCompareOp(op);
    124     }
    125     Token::Value inverted_op = Token::ReverseCompareOp(op);
    126     UpdateControlFlowRange(op, test->left(), test->right());
    127     UpdateControlFlowRange(inverted_op, test->right(), test->left());
    128   }
    129 }
    130 
    131 
    132 // We know that value [op] other. Use this information to update the range on
    133 // value.
    134 void HRangeAnalysisPhase::UpdateControlFlowRange(Token::Value op,
    135                                                  HValue* value,
    136                                                  HValue* other) {
    137   Range temp_range;
    138   Range* range = other->range() != NULL ? other->range() : &temp_range;
    139   Range* new_range = NULL;
    140 
    141   TraceRange("Control flow range infer %d %s %d\n",
    142              value->id(),
    143              Token::Name(op),
    144              other->id());
    145 
    146   if (op == Token::EQ || op == Token::EQ_STRICT) {
    147     // The same range has to apply for value.
    148     new_range = range->Copy(graph()->zone());
    149   } else if (op == Token::LT || op == Token::LTE) {
    150     new_range = range->CopyClearLower(graph()->zone());
    151     if (op == Token::LT) {
    152       new_range->AddConstant(-1);
    153     }
    154   } else if (op == Token::GT || op == Token::GTE) {
    155     new_range = range->CopyClearUpper(graph()->zone());
    156     if (op == Token::GT) {
    157       new_range->AddConstant(1);
    158     }
    159   }
    160 
    161   if (new_range != NULL && !new_range->IsMostGeneric()) {
    162     AddRange(value, new_range);
    163   }
    164 }
    165 
    166 
    167 void HRangeAnalysisPhase::InferRange(HValue* value) {
    168   DCHECK(!value->HasRange());
    169   if (!value->representation().IsNone()) {
    170     value->ComputeInitialRange(graph()->zone());
    171     Range* range = value->range();
    172     TraceRange("Initial inferred range of %d (%s) set to [%d,%d]\n",
    173                value->id(),
    174                value->Mnemonic(),
    175                range->lower(),
    176                range->upper());
    177   }
    178 }
    179 
    180 
    181 void HRangeAnalysisPhase::RollBackTo(int index) {
    182   DCHECK(index <= changed_ranges_.length());
    183   for (int i = index; i < changed_ranges_.length(); ++i) {
    184     changed_ranges_[i]->RemoveLastAddedRange();
    185   }
    186   changed_ranges_.Rewind(index);
    187 }
    188 
    189 
    190 void HRangeAnalysisPhase::AddRange(HValue* value, Range* range) {
    191   Range* original_range = value->range();
    192   value->AddNewRange(range, graph()->zone());
    193   changed_ranges_.Add(value, zone());
    194   Range* new_range = value->range();
    195   TraceRange("Updated range of %d set to [%d,%d]\n",
    196              value->id(),
    197              new_range->lower(),
    198              new_range->upper());
    199   if (original_range != NULL) {
    200     TraceRange("Original range was [%d,%d]\n",
    201                original_range->lower(),
    202                original_range->upper());
    203   }
    204   TraceRange("New information was [%d,%d]\n",
    205              range->lower(),
    206              range->upper());
    207 }
    208 
    209 
    210 void HRangeAnalysisPhase::PropagateMinusZeroChecks(HValue* value) {
    211   DCHECK(worklist_.is_empty());
    212   DCHECK(in_worklist_.IsEmpty());
    213 
    214   AddToWorklist(value);
    215   while (!worklist_.is_empty()) {
    216     value = worklist_.RemoveLast();
    217 
    218     if (value->IsPhi()) {
    219       // For phis, we must propagate the check to all of its inputs.
    220       HPhi* phi = HPhi::cast(value);
    221       for (int i = 0; i < phi->OperandCount(); ++i) {
    222         AddToWorklist(phi->OperandAt(i));
    223       }
    224     } else if (value->IsUnaryMathOperation()) {
    225       HUnaryMathOperation* instr = HUnaryMathOperation::cast(value);
    226       if (instr->representation().IsSmiOrInteger32() &&
    227           !instr->value()->representation().Equals(instr->representation())) {
    228         if (instr->value()->range() == NULL ||
    229             instr->value()->range()->CanBeMinusZero()) {
    230           instr->SetFlag(HValue::kBailoutOnMinusZero);
    231         }
    232       }
    233       if (instr->RequiredInputRepresentation(0).IsSmiOrInteger32() &&
    234           instr->representation().Equals(
    235               instr->RequiredInputRepresentation(0))) {
    236         AddToWorklist(instr->value());
    237       }
    238     } else if (value->IsChange()) {
    239       HChange* instr = HChange::cast(value);
    240       if (!instr->from().IsSmiOrInteger32() &&
    241           !instr->CanTruncateToInt32() &&
    242           (instr->value()->range() == NULL ||
    243            instr->value()->range()->CanBeMinusZero())) {
    244         instr->SetFlag(HValue::kBailoutOnMinusZero);
    245       }
    246     } else if (value->IsForceRepresentation()) {
    247       HForceRepresentation* instr = HForceRepresentation::cast(value);
    248       AddToWorklist(instr->value());
    249     } else if (value->IsMod()) {
    250       HMod* instr = HMod::cast(value);
    251       if (instr->range() == NULL || instr->range()->CanBeMinusZero()) {
    252         instr->SetFlag(HValue::kBailoutOnMinusZero);
    253         AddToWorklist(instr->left());
    254       }
    255     } else if (value->IsDiv() || value->IsMul()) {
    256       HBinaryOperation* instr = HBinaryOperation::cast(value);
    257       if (instr->range() == NULL || instr->range()->CanBeMinusZero()) {
    258         instr->SetFlag(HValue::kBailoutOnMinusZero);
    259       }
    260       AddToWorklist(instr->right());
    261       AddToWorklist(instr->left());
    262     } else if (value->IsMathFloorOfDiv()) {
    263       HMathFloorOfDiv* instr = HMathFloorOfDiv::cast(value);
    264       instr->SetFlag(HValue::kBailoutOnMinusZero);
    265     } else if (value->IsAdd() || value->IsSub()) {
    266       HBinaryOperation* instr = HBinaryOperation::cast(value);
    267       if (instr->range() == NULL || instr->range()->CanBeMinusZero()) {
    268         // Propagate to the left argument. If the left argument cannot be -0,
    269         // then the result of the add/sub operation cannot be either.
    270         AddToWorklist(instr->left());
    271       }
    272     } else if (value->IsMathMinMax()) {
    273       HMathMinMax* instr = HMathMinMax::cast(value);
    274       AddToWorklist(instr->right());
    275       AddToWorklist(instr->left());
    276     }
    277   }
    278 
    279   in_worklist_.Clear();
    280   DCHECK(in_worklist_.IsEmpty());
    281   DCHECK(worklist_.is_empty());
    282 }
    283 
    284 
    285 }  // namespace internal
    286 }  // namespace v8
    287