LCOV - code coverage report
Current view: top level - src/crankshaft - hydrogen-range-analysis.cc (source / functions) Hit Total Coverage
Test: app.info Lines: 108 115 93.9 %
Date: 2017-04-26 Functions: 8 9 88.9 %

          Line data    Source code
       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     1366169 :       : 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    16876002 : void HRangeAnalysisPhase::TraceRange(const char* msg, ...) {
      27    16876002 :   if (FLAG_trace_range) {
      28             :     va_list arguments;
      29           0 :     va_start(arguments, msg);
      30           0 :     base::OS::VPrint(msg, arguments);
      31           0 :     va_end(arguments);
      32             :   }
      33    16876002 : }
      34             : 
      35             : 
      36      283728 : void HRangeAnalysisPhase::Run() {
      37     4795294 :   HBasicBlock* block(graph()->entry_block());
      38      283728 :   ZoneList<Pending> stack(graph()->blocks()->length(), zone());
      39     5079022 :   while (block != NULL) {
      40     4511566 :     TraceRange("Analyzing block B%d\n", block->block_id());
      41             : 
      42             :     // Infer range based on control flow.
      43     4511579 :     if (block->predecessors()->length() == 1) {
      44     4116530 :       HBasicBlock* pred = block->predecessors()->first();
      45     7564532 :       if (pred->end()->IsCompareNumericAndBranch()) {
      46             :         InferControlFlowRange(HCompareNumericAndBranch::cast(pred->end()),
      47      334268 :                               block);
      48             :       }
      49             :     }
      50             : 
      51             :     // Process phi instructions.
      52      301146 :     for (int i = 0; i < block->phis()->length(); ++i) {
      53      301145 :       HPhi* phi = block->phis()->at(i);
      54      301145 :       InferRange(phi);
      55             :     }
      56             : 
      57             :     // Go through all instructions of the current block.
      58    29725973 :     for (HInstructionIterator it(block); !it.Done(); it.Advance()) {
      59             :       HValue* value = it.Current();
      60    25214349 :       InferRange(value);
      61             : 
      62             :       // Compute the bailout-on-minus-zero flag.
      63    25214307 :       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      369992 :         if (from.IsSmiOrInteger32()) {
      70             :           DCHECK(instr->to().IsTagged() ||
      71             :                 instr->to().IsDouble() ||
      72             :                 instr->to().IsSmiOrInteger32());
      73      175922 :           PropagateMinusZeroChecks(instr->value());
      74             :         }
      75             :       }
      76             :     }
      77             : 
      78             :     // Continue analysis in all dominated blocks.
      79             :     const ZoneList<HBasicBlock*>* dominated_blocks(block->dominated_blocks());
      80     4511624 :     if (!dominated_blocks->is_empty()) {
      81             :       // Continue with first dominated block, and push the
      82             :       // remaining blocks on the stack (in reverse order).
      83     2861729 :       int last_changed_range = changed_ranges_.length();
      84     4227899 :       for (int i = dominated_blocks->length() - 1; i > 0; --i) {
      85     2732339 :         stack.Add(Pending(dominated_blocks->at(i), last_changed_range), zone());
      86             :       }
      87     2861730 :       block = dominated_blocks->at(0);
      88     1649895 :     } else if (!stack.is_empty()) {
      89             :       // Pop next pending block from stack.
      90             :       Pending pending = stack.RemoveLast();
      91     1366171 :       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      283729 : }
     102             : 
     103             : 
     104           0 : 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           0 : }
     115             : 
     116             : 
     117      632930 : void HRangeAnalysisPhase::InferControlFlowRange(HCompareNumericAndBranch* test,
     118             :                                                 HBasicBlock* dest) {
     119             :   DCHECK((test->FirstSuccessor() == dest) == (test->SecondSuccessor() != dest));
     120      334268 :   if (test->representation().IsSmiOrInteger32()) {
     121             :     Token::Value op = test->token();
     122      298662 :     if (test->SecondSuccessor() == dest) {
     123      149331 :       op = Token::NegateCompareOp(op);
     124             :     }
     125      298662 :     Token::Value inverted_op = Token::ReverseCompareOp(op);
     126      298662 :     UpdateControlFlowRange(op, test->left(), test->right());
     127      298662 :     UpdateControlFlowRange(inverted_op, test->right(), test->left());
     128             :   }
     129      334268 : }
     130             : 
     131             : 
     132             : // We know that value [op] other. Use this information to update the range on
     133             : // value.
     134      597323 : void HRangeAnalysisPhase::UpdateControlFlowRange(Token::Value op,
     135      597323 :                                                  HValue* value,
     136     1194646 :                                                  HValue* other) {
     137             :   Range temp_range;
     138      597323 :   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      597323 :              other->id());
     145             : 
     146      597324 :   if (op == Token::EQ || op == Token::EQ_STRICT) {
     147             :     // The same range has to apply for value.
     148      447940 :     new_range = range->Copy(graph()->zone());
     149      447940 :   } else if (op == Token::LT || op == Token::LTE) {
     150      149278 :     new_range = range->CopyClearLower(graph()->zone());
     151      149278 :     if (op == Token::LT) {
     152       74639 :       new_range->AddConstant(-1);
     153             :     }
     154      298662 :   } else if (op == Token::GT || op == Token::GTE) {
     155      149278 :     new_range = range->CopyClearUpper(graph()->zone());
     156      149278 :     if (op == Token::GT) {
     157       74639 :       new_range->AddConstant(1);
     158             :     }
     159             :   }
     160             : 
     161     1045263 :   if (new_range != NULL && !new_range->IsMostGeneric()) {
     162      438859 :     AddRange(value, new_range);
     163             :   }
     164      597323 : }
     165             : 
     166             : 
     167    46417528 : void HRangeAnalysisPhase::InferRange(HValue* value) {
     168             :   DCHECK(!value->HasRange());
     169    25515449 :   if (!value->representation().IsNone()) {
     170    10450941 :     value->ComputeInitialRange(graph()->zone());
     171    10451067 :     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    20902079 :                range->upper());
     177             :   }
     178    25515496 : }
     179             : 
     180             : 
     181     1366171 : void HRangeAnalysisPhase::RollBackTo(int index) {
     182             :   DCHECK(index <= changed_ranges_.length());
     183     3568544 :   for (int i = index; i < changed_ranges_.length(); ++i) {
     184     2620474 :     changed_ranges_[i]->RemoveLastAddedRange();
     185             :   }
     186             :   changed_ranges_.Rewind(index);
     187     1366171 : }
     188             : 
     189             : 
     190      877718 : void HRangeAnalysisPhase::AddRange(HValue* value, Range* range) {
     191     1755436 :   Range* original_range = value->range();
     192      438859 :   value->AddNewRange(range, graph()->zone());
     193      438859 :   changed_ranges_.Add(value, zone());
     194      438859 :   Range* new_range = value->range();
     195             :   TraceRange("Updated range of %d set to [%d,%d]\n",
     196             :              value->id(),
     197             :              new_range->lower(),
     198      438859 :              new_range->upper());
     199      438859 :   if (original_range != NULL) {
     200             :     TraceRange("Original range was [%d,%d]\n",
     201             :                original_range->lower(),
     202      438859 :                original_range->upper());
     203             :   }
     204             :   TraceRange("New information was [%d,%d]\n",
     205             :              range->lower(),
     206      438859 :              range->upper());
     207      438858 : }
     208             : 
     209             : 
     210      175922 : void HRangeAnalysisPhase::PropagateMinusZeroChecks(HValue* value) {
     211             :   DCHECK(worklist_.is_empty());
     212             :   DCHECK(in_worklist_.IsEmpty());
     213             : 
     214      175922 :   AddToWorklist(value);
     215      597313 :   while (!worklist_.is_empty()) {
     216      666856 :     value = worklist_.RemoveLast();
     217             : 
     218      245465 :     if (value->IsPhi()) {
     219             :       // For phis, we must propagate the check to all of its inputs.
     220             :       HPhi* phi = HPhi::cast(value);
     221      149554 :       for (int i = 0; i < phi->OperandCount(); ++i) {
     222       60065 :         AddToWorklist(phi->OperandAt(i));
     223             :       }
     224      216041 :     } else if (value->IsUnaryMathOperation()) {
     225             :       HUnaryMathOperation* instr = HUnaryMathOperation::cast(value);
     226       39280 :       if (instr->representation().IsSmiOrInteger32() &&
     227             :           !instr->value()->representation().Equals(instr->representation())) {
     228       38978 :         if (instr->value()->range() == NULL ||
     229             :             instr->value()->range()->CanBeMinusZero()) {
     230             :           instr->SetFlag(HValue::kBailoutOnMinusZero);
     231             :         }
     232             :       }
     233       58920 :       if (instr->RequiredInputRepresentation(0).IsSmiOrInteger32() &&
     234             :           instr->representation().Equals(
     235       19640 :               instr->RequiredInputRepresentation(0))) {
     236           0 :         AddToWorklist(instr->value());
     237             :       }
     238      196402 :     } else if (value->IsChange()) {
     239             :       HChange* instr = HChange::cast(value);
     240       50143 :       if (!instr->from().IsSmiOrInteger32() &&
     241       45042 :           !instr->CanTruncateToInt32() &&
     242       37300 :           (instr->value()->range() == NULL ||
     243             :            instr->value()->range()->CanBeMinusZero())) {
     244             :         instr->SetFlag(HValue::kBailoutOnMinusZero);
     245             :       }
     246      170049 :     } else if (value->IsForceRepresentation()) {
     247             :       HForceRepresentation* instr = HForceRepresentation::cast(value);
     248           0 :       AddToWorklist(instr->value());
     249      170050 :     } else if (value->IsMod()) {
     250             :       HMod* instr = HMod::cast(value);
     251        6710 :       if (instr->range() == NULL || instr->range()->CanBeMinusZero()) {
     252             :         instr->SetFlag(HValue::kBailoutOnMinusZero);
     253        1362 :         AddToWorklist(instr->left());
     254             :       }
     255      330976 :     } else if (value->IsDiv() || value->IsMul()) {
     256             :       HBinaryOperation* instr = HBinaryOperation::cast(value);
     257       14162 :       if (instr->range() == NULL || instr->range()->CanBeMinusZero()) {
     258             :         instr->SetFlag(HValue::kBailoutOnMinusZero);
     259             :       }
     260        7087 :       AddToWorklist(instr->right());
     261        7087 :       AddToWorklist(instr->left());
     262      159608 :     } else if (value->IsMathFloorOfDiv()) {
     263             :       HMathFloorOfDiv* instr = HMathFloorOfDiv::cast(value);
     264             :       instr->SetFlag(HValue::kBailoutOnMinusZero);
     265      227473 :     } else if (value->IsAdd() || value->IsSub()) {
     266             :       HBinaryOperation* instr = HBinaryOperation::cast(value);
     267      174508 :       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       13122 :         AddToWorklist(instr->left());
     271             :       }
     272       64656 :     } else if (value->IsMathMinMax()) {
     273             :       HMathMinMax* instr = HMathMinMax::cast(value);
     274         232 :       AddToWorklist(instr->right());
     275         232 :       AddToWorklist(instr->left());
     276             :     }
     277             :   }
     278             : 
     279      175924 :   in_worklist_.Clear();
     280             :   DCHECK(in_worklist_.IsEmpty());
     281             :   DCHECK(worklist_.is_empty());
     282      175924 : }
     283             : 
     284             : 
     285             : }  // namespace internal
     286             : }  // namespace v8

Generated by: LCOV version 1.10