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