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:
Pending(HBasicBlock * block,int last_changed_range)36 Pending(HBasicBlock* block, int last_changed_range)
37 : block_(block), last_changed_range_(last_changed_range) {}
38
block() const39 HBasicBlock* block() const { return block_; }
last_changed_range() const40 int last_changed_range() const { return last_changed_range_; }
41
42 private:
43 HBasicBlock* block_;
44 int last_changed_range_;
45 };
46
47
TraceRange(const char * msg,...)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
Run()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
InferControlFlowRange(HCompareNumericAndBranch * test,HBasicBlock * dest)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.
UpdateControlFlowRange(Token::Value op,HValue * value,HValue * other)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
InferRange(HValue * value)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
RollBackTo(int index)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
AddRange(HValue * value,Range * range)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