Home | History | Annotate | Download | only in src 
      1 // Copyright 2013 the V8 project authors. All rights reserved.
      2 // Redistribution and use in source and binary forms, with or without
      3 // modification, are permitted provided that the following conditions are
      4 // met:
      5 //
      6 //     * Redistributions of source code must retain the above copyright
      7 //       notice, this list of conditions and the following disclaimer.
      8 //     * Redistributions in binary form must reproduce the above
      9 //       copyright notice, this list of conditions and the following
     10 //       disclaimer in the documentation and/or other materials provided
     11 //       with the distribution.
     12 //     * Neither the name of Google Inc. nor the names of its
     13 //       contributors may be used to endorse or promote products derived
     14 //       from this software without specific prior written permission.
     15 //
     16 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
     17 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
     18 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
     19 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
     20 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
     21 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
     22 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
     23 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
     24 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
     25 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
     26 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
     27 
     28 #include "hydrogen-range-analysis.h"
     29 
     30 namespace v8 {
     31 namespace internal {
     32 
     33 
     34 class Pending {
     35  public:
     36   Pending(HBasicBlock* block, int last_changed_range)
     37       : block_(block), last_changed_range_(last_changed_range) {}
     38 
     39   HBasicBlock* block() const { return block_; }
     40   int last_changed_range() const { return last_changed_range_; }
     41 
     42  private:
     43   HBasicBlock* block_;
     44   int last_changed_range_;
     45 };
     46 
     47 
     48 void HRangeAnalysisPhase::TraceRange(const char* msg, ...) {
     49   if (FLAG_trace_range) {
     50     va_list arguments;
     51     va_start(arguments, msg);
     52     OS::VPrint(msg, arguments);
     53     va_end(arguments);
     54   }
     55 }
     56 
     57 
     58 void HRangeAnalysisPhase::Run() {
     59   HBasicBlock* block(graph()->entry_block());
     60   ZoneList<Pending> stack(graph()->blocks()->length(), zone());
     61   while (block != NULL) {
     62     TraceRange("Analyzing block B%d\n", block->block_id());
     63 
     64     // Infer range based on control flow.
     65     if (block->predecessors()->length() == 1) {
     66       HBasicBlock* pred = block->predecessors()->first();
     67       if (pred->end()->IsCompareNumericAndBranch()) {
     68         InferControlFlowRange(HCompareNumericAndBranch::cast(pred->end()),
     69                               block);
     70       }
     71     }
     72 
     73     // Process phi instructions.
     74     for (int i = 0; i < block->phis()->length(); ++i) {
     75       HPhi* phi = block->phis()->at(i);
     76       InferRange(phi);
     77     }
     78 
     79     // Go through all instructions of the current block.
     80     for (HInstructionIterator it(block); !it.Done(); it.Advance()) {
     81       InferRange(it.Current());
     82     }
     83 
     84     // Continue analysis in all dominated blocks.
     85     const ZoneList<HBasicBlock*>* dominated_blocks(block->dominated_blocks());
     86     if (!dominated_blocks->is_empty()) {
     87       // Continue with first dominated block, and push the
     88       // remaining blocks on the stack (in reverse order).
     89       int last_changed_range = changed_ranges_.length();
     90       for (int i = dominated_blocks->length() - 1; i > 0; --i) {
     91         stack.Add(Pending(dominated_blocks->at(i), last_changed_range), zone());
     92       }
     93       block = dominated_blocks->at(0);
     94     } else if (!stack.is_empty()) {
     95       // Pop next pending block from stack.
     96       Pending pending = stack.RemoveLast();
     97       RollBackTo(pending.last_changed_range());
     98       block = pending.block();
     99     } else {
    100       // All blocks done.
    101       block = NULL;
    102     }
    103   }
    104 }
    105 
    106 
    107 void HRangeAnalysisPhase::InferControlFlowRange(HCompareNumericAndBranch* test,
    108                                                 HBasicBlock* dest) {
    109   ASSERT((test->FirstSuccessor() == dest) == (test->SecondSuccessor() != dest));
    110   if (test->representation().IsSmiOrInteger32()) {
    111     Token::Value op = test->token();
    112     if (test->SecondSuccessor() == dest) {
    113       op = Token::NegateCompareOp(op);
    114     }
    115     Token::Value inverted_op = Token::ReverseCompareOp(op);
    116     UpdateControlFlowRange(op, test->left(), test->right());
    117     UpdateControlFlowRange(inverted_op, test->right(), test->left());
    118   }
    119 }
    120 
    121 
    122 // We know that value [op] other. Use this information to update the range on
    123 // value.
    124 void HRangeAnalysisPhase::UpdateControlFlowRange(Token::Value op,
    125                                                  HValue* value,
    126                                                  HValue* other) {
    127   Range temp_range;
    128   Range* range = other->range() != NULL ? other->range() : &temp_range;
    129   Range* new_range = NULL;
    130 
    131   TraceRange("Control flow range infer %d %s %d\n",
    132              value->id(),
    133              Token::Name(op),
    134              other->id());
    135 
    136   if (op == Token::EQ || op == Token::EQ_STRICT) {
    137     // The same range has to apply for value.
    138     new_range = range->Copy(graph()->zone());
    139   } else if (op == Token::LT || op == Token::LTE) {
    140     new_range = range->CopyClearLower(graph()->zone());
    141     if (op == Token::LT) {
    142       new_range->AddConstant(-1);
    143     }
    144   } else if (op == Token::GT || op == Token::GTE) {
    145     new_range = range->CopyClearUpper(graph()->zone());
    146     if (op == Token::GT) {
    147       new_range->AddConstant(1);
    148     }
    149   }
    150 
    151   if (new_range != NULL && !new_range->IsMostGeneric()) {
    152     AddRange(value, new_range);
    153   }
    154 }
    155 
    156 
    157 void HRangeAnalysisPhase::InferRange(HValue* value) {
    158   ASSERT(!value->HasRange());
    159   if (!value->representation().IsNone()) {
    160     value->ComputeInitialRange(graph()->zone());
    161     Range* range = value->range();
    162     TraceRange("Initial inferred range of %d (%s) set to [%d,%d]\n",
    163                value->id(),
    164                value->Mnemonic(),
    165                range->lower(),
    166                range->upper());
    167   }
    168 }
    169 
    170 
    171 void HRangeAnalysisPhase::RollBackTo(int index) {
    172   ASSERT(index <= changed_ranges_.length());
    173   for (int i = index; i < changed_ranges_.length(); ++i) {
    174     changed_ranges_[i]->RemoveLastAddedRange();
    175   }
    176   changed_ranges_.Rewind(index);
    177 }
    178 
    179 
    180 void HRangeAnalysisPhase::AddRange(HValue* value, Range* range) {
    181   Range* original_range = value->range();
    182   value->AddNewRange(range, graph()->zone());
    183   changed_ranges_.Add(value, zone());
    184   Range* new_range = value->range();
    185   TraceRange("Updated range of %d set to [%d,%d]\n",
    186              value->id(),
    187              new_range->lower(),
    188              new_range->upper());
    189   if (original_range != NULL) {
    190     TraceRange("Original range was [%d,%d]\n",
    191                original_range->lower(),
    192                original_range->upper());
    193   }
    194   TraceRange("New information was [%d,%d]\n",
    195              range->lower(),
    196              range->upper());
    197 }
    198 
    199 
    200 } }  // namespace v8::internal
    201