OLD | NEW |
(Empty) | |
| 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 void HRangeAnalysisPhase::TraceRange(const char* msg, ...) { |
| 35 if (FLAG_trace_range) { |
| 36 va_list arguments; |
| 37 va_start(arguments, msg); |
| 38 OS::VPrint(msg, arguments); |
| 39 va_end(arguments); |
| 40 } |
| 41 } |
| 42 |
| 43 |
| 44 void HRangeAnalysisPhase::Analyze(HBasicBlock* block) { |
| 45 TraceRange("Analyzing block B%d\n", block->block_id()); |
| 46 |
| 47 int last_changed_range = changed_ranges_.length() - 1; |
| 48 |
| 49 // Infer range based on control flow. |
| 50 if (block->predecessors()->length() == 1) { |
| 51 HBasicBlock* pred = block->predecessors()->first(); |
| 52 if (pred->end()->IsCompareIDAndBranch()) { |
| 53 InferControlFlowRange(HCompareIDAndBranch::cast(pred->end()), block); |
| 54 } |
| 55 } |
| 56 |
| 57 // Process phi instructions. |
| 58 for (int i = 0; i < block->phis()->length(); ++i) { |
| 59 HPhi* phi = block->phis()->at(i); |
| 60 InferRange(phi); |
| 61 } |
| 62 |
| 63 // Go through all instructions of the current block. |
| 64 for (HInstructionIterator it(block); !it.Done(); it.Advance()) { |
| 65 InferRange(it.Current()); |
| 66 } |
| 67 |
| 68 // Continue analysis in all dominated blocks. |
| 69 for (int i = 0; i < block->dominated_blocks()->length(); ++i) { |
| 70 Analyze(block->dominated_blocks()->at(i)); |
| 71 } |
| 72 |
| 73 RollBackTo(last_changed_range); |
| 74 } |
| 75 |
| 76 |
| 77 void HRangeAnalysisPhase::InferControlFlowRange(HCompareIDAndBranch* test, |
| 78 HBasicBlock* dest) { |
| 79 ASSERT((test->FirstSuccessor() == dest) == (test->SecondSuccessor() != dest)); |
| 80 if (test->representation().IsSmiOrInteger32()) { |
| 81 Token::Value op = test->token(); |
| 82 if (test->SecondSuccessor() == dest) { |
| 83 op = Token::NegateCompareOp(op); |
| 84 } |
| 85 Token::Value inverted_op = Token::ReverseCompareOp(op); |
| 86 UpdateControlFlowRange(op, test->left(), test->right()); |
| 87 UpdateControlFlowRange(inverted_op, test->right(), test->left()); |
| 88 } |
| 89 } |
| 90 |
| 91 |
| 92 // We know that value [op] other. Use this information to update the range on |
| 93 // value. |
| 94 void HRangeAnalysisPhase::UpdateControlFlowRange(Token::Value op, |
| 95 HValue* value, |
| 96 HValue* other) { |
| 97 Range temp_range; |
| 98 Range* range = other->range() != NULL ? other->range() : &temp_range; |
| 99 Range* new_range = NULL; |
| 100 |
| 101 TraceRange("Control flow range infer %d %s %d\n", |
| 102 value->id(), |
| 103 Token::Name(op), |
| 104 other->id()); |
| 105 |
| 106 if (op == Token::EQ || op == Token::EQ_STRICT) { |
| 107 // The same range has to apply for value. |
| 108 new_range = range->Copy(graph()->zone()); |
| 109 } else if (op == Token::LT || op == Token::LTE) { |
| 110 new_range = range->CopyClearLower(graph()->zone()); |
| 111 if (op == Token::LT) { |
| 112 new_range->AddConstant(-1); |
| 113 } |
| 114 } else if (op == Token::GT || op == Token::GTE) { |
| 115 new_range = range->CopyClearUpper(graph()->zone()); |
| 116 if (op == Token::GT) { |
| 117 new_range->AddConstant(1); |
| 118 } |
| 119 } |
| 120 |
| 121 if (new_range != NULL && !new_range->IsMostGeneric()) { |
| 122 AddRange(value, new_range); |
| 123 } |
| 124 } |
| 125 |
| 126 |
| 127 void HRangeAnalysisPhase::InferRange(HValue* value) { |
| 128 ASSERT(!value->HasRange()); |
| 129 if (!value->representation().IsNone()) { |
| 130 value->ComputeInitialRange(graph()->zone()); |
| 131 Range* range = value->range(); |
| 132 TraceRange("Initial inferred range of %d (%s) set to [%d,%d]\n", |
| 133 value->id(), |
| 134 value->Mnemonic(), |
| 135 range->lower(), |
| 136 range->upper()); |
| 137 } |
| 138 } |
| 139 |
| 140 |
| 141 void HRangeAnalysisPhase::RollBackTo(int index) { |
| 142 for (int i = index + 1; i < changed_ranges_.length(); ++i) { |
| 143 changed_ranges_[i]->RemoveLastAddedRange(); |
| 144 } |
| 145 changed_ranges_.Rewind(index + 1); |
| 146 } |
| 147 |
| 148 |
| 149 void HRangeAnalysisPhase::AddRange(HValue* value, Range* range) { |
| 150 Range* original_range = value->range(); |
| 151 value->AddNewRange(range, graph()->zone()); |
| 152 changed_ranges_.Add(value, zone()); |
| 153 Range* new_range = value->range(); |
| 154 TraceRange("Updated range of %d set to [%d,%d]\n", |
| 155 value->id(), |
| 156 new_range->lower(), |
| 157 new_range->upper()); |
| 158 if (original_range != NULL) { |
| 159 TraceRange("Original range was [%d,%d]\n", |
| 160 original_range->lower(), |
| 161 original_range->upper()); |
| 162 } |
| 163 TraceRange("New information was [%d,%d]\n", |
| 164 range->lower(), |
| 165 range->upper()); |
| 166 } |
| 167 |
| 168 |
| 169 } } // namespace v8::internal |
OLD | NEW |