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
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 }
75 }
76
77 // Continue analysis in all dominated blocks.
78 const ZoneList<HBasicBlock*>* dominated_blocks(block->dominated_blocks());
79 if (!dominated_blocks->is_empty()) {
80 // Continue with first dominated block, and push the
81 // remaining blocks on the stack (in reverse order).
82 int last_changed_range = changed_ranges_.length();
83 for (int i = dominated_blocks->length() - 1; i > 0; --i) {
84 stack.Add(Pending(dominated_blocks->at(i), last_changed_range), zone());
85 }
86 block = dominated_blocks->at(0);
87 } else if (!stack.is_empty()) {
88 // Pop next pending block from stack.
89 Pending pending = stack.RemoveLast();
90 RollBackTo(pending.last_changed_range());
91 block = pending.block();
92 } else {
93 // All blocks done.
94 block = NULL;
95 }
96 }
97
98 // The ranges are not valid anymore due to SSI vs. SSA!
99 PoisonRanges();
100 }
101
102
PoisonRanges()103 void HRangeAnalysisPhase::PoisonRanges() {
104 #ifdef DEBUG
105 for (int i = 0; i < graph()->blocks()->length(); ++i) {
106 HBasicBlock* block = graph()->blocks()->at(i);
107 for (HInstructionIterator it(block); !it.Done(); it.Advance()) {
108 HInstruction* instr = it.Current();
109 if (instr->HasRange()) instr->PoisonRange();
110 }
111 }
112 #endif
113 }
114
115
InferControlFlowRange(HCompareNumericAndBranch * test,HBasicBlock * dest)116 void HRangeAnalysisPhase::InferControlFlowRange(HCompareNumericAndBranch* test,
117 HBasicBlock* dest) {
118 DCHECK((test->FirstSuccessor() == dest) == (test->SecondSuccessor() != dest));
119 if (test->representation().IsSmiOrInteger32()) {
120 Token::Value op = test->token();
121 if (test->SecondSuccessor() == dest) {
122 op = Token::NegateCompareOp(op);
123 }
124 Token::Value inverted_op = Token::ReverseCompareOp(op);
125 UpdateControlFlowRange(op, test->left(), test->right());
126 UpdateControlFlowRange(inverted_op, test->right(), test->left());
127 }
128 }
129
130
131 // We know that value [op] other. Use this information to update the range on
132 // value.
UpdateControlFlowRange(Token::Value op,HValue * value,HValue * other)133 void HRangeAnalysisPhase::UpdateControlFlowRange(Token::Value op,
134 HValue* value,
135 HValue* other) {
136 Range temp_range;
137 Range* range = other->range() != NULL ? other->range() : &temp_range;
138 Range* new_range = NULL;
139
140 TraceRange("Control flow range infer %d %s %d\n",
141 value->id(),
142 Token::Name(op),
143 other->id());
144
145 if (op == Token::EQ || op == Token::EQ_STRICT) {
146 // The same range has to apply for value.
147 new_range = range->Copy(graph()->zone());
148 } else if (op == Token::LT || op == Token::LTE) {
149 new_range = range->CopyClearLower(graph()->zone());
150 if (op == Token::LT) {
151 new_range->AddConstant(-1);
152 }
153 } else if (op == Token::GT || op == Token::GTE) {
154 new_range = range->CopyClearUpper(graph()->zone());
155 if (op == Token::GT) {
156 new_range->AddConstant(1);
157 }
158 }
159
160 if (new_range != NULL && !new_range->IsMostGeneric()) {
161 AddRange(value, new_range);
162 }
163 }
164
165
InferRange(HValue * value)166 void HRangeAnalysisPhase::InferRange(HValue* value) {
167 DCHECK(!value->HasRange());
168 if (!value->representation().IsNone()) {
169 value->ComputeInitialRange(graph()->zone());
170 Range* range = value->range();
171 TraceRange("Initial inferred range of %d (%s) set to [%d,%d]\n",
172 value->id(),
173 value->Mnemonic(),
174 range->lower(),
175 range->upper());
176 }
177 }
178
179
RollBackTo(int index)180 void HRangeAnalysisPhase::RollBackTo(int index) {
181 DCHECK(index <= changed_ranges_.length());
182 for (int i = index; i < changed_ranges_.length(); ++i) {
183 changed_ranges_[i]->RemoveLastAddedRange();
184 }
185 changed_ranges_.Rewind(index);
186 }
187
188
AddRange(HValue * value,Range * range)189 void HRangeAnalysisPhase::AddRange(HValue* value, Range* range) {
190 Range* original_range = value->range();
191 value->AddNewRange(range, graph()->zone());
192 changed_ranges_.Add(value, zone());
193 Range* new_range = value->range();
194 TraceRange("Updated range of %d set to [%d,%d]\n",
195 value->id(),
196 new_range->lower(),
197 new_range->upper());
198 if (original_range != NULL) {
199 TraceRange("Original range was [%d,%d]\n",
200 original_range->lower(),
201 original_range->upper());
202 }
203 TraceRange("New information was [%d,%d]\n",
204 range->lower(),
205 range->upper());
206 }
207
208
PropagateMinusZeroChecks(HValue * value)209 void HRangeAnalysisPhase::PropagateMinusZeroChecks(HValue* value) {
210 DCHECK(worklist_.is_empty());
211 DCHECK(in_worklist_.IsEmpty());
212
213 AddToWorklist(value);
214 while (!worklist_.is_empty()) {
215 value = worklist_.RemoveLast();
216
217 if (value->IsPhi()) {
218 // For phis, we must propagate the check to all of its inputs.
219 HPhi* phi = HPhi::cast(value);
220 for (int i = 0; i < phi->OperandCount(); ++i) {
221 AddToWorklist(phi->OperandAt(i));
222 }
223 } else if (value->IsUnaryMathOperation()) {
224 HUnaryMathOperation* instr = HUnaryMathOperation::cast(value);
225 if (instr->representation().IsSmiOrInteger32() &&
226 !instr->value()->representation().Equals(instr->representation())) {
227 if (instr->value()->range() == NULL ||
228 instr->value()->range()->CanBeMinusZero()) {
229 instr->SetFlag(HValue::kBailoutOnMinusZero);
230 }
231 }
232 if (instr->RequiredInputRepresentation(0).IsSmiOrInteger32() &&
233 instr->representation().Equals(
234 instr->RequiredInputRepresentation(0))) {
235 AddToWorklist(instr->value());
236 }
237 } else if (value->IsChange()) {
238 HChange* instr = HChange::cast(value);
239 if (!instr->from().IsSmiOrInteger32() &&
240 !instr->CanTruncateToInt32() &&
241 (instr->value()->range() == NULL ||
242 instr->value()->range()->CanBeMinusZero())) {
243 instr->SetFlag(HValue::kBailoutOnMinusZero);
244 }
245 } else if (value->IsForceRepresentation()) {
246 HForceRepresentation* instr = HForceRepresentation::cast(value);
247 AddToWorklist(instr->value());
248 } else if (value->IsMod()) {
249 HMod* instr = HMod::cast(value);
250 if (instr->range() == NULL || instr->range()->CanBeMinusZero()) {
251 instr->SetFlag(HValue::kBailoutOnMinusZero);
252 AddToWorklist(instr->left());
253 }
254 } else if (value->IsDiv() || value->IsMul()) {
255 HBinaryOperation* instr = HBinaryOperation::cast(value);
256 if (instr->range() == NULL || instr->range()->CanBeMinusZero()) {
257 instr->SetFlag(HValue::kBailoutOnMinusZero);
258 }
259 AddToWorklist(instr->right());
260 AddToWorklist(instr->left());
261 } else if (value->IsMathFloorOfDiv()) {
262 HMathFloorOfDiv* instr = HMathFloorOfDiv::cast(value);
263 instr->SetFlag(HValue::kBailoutOnMinusZero);
264 } else if (value->IsAdd() || value->IsSub()) {
265 HBinaryOperation* instr = HBinaryOperation::cast(value);
266 if (instr->range() == NULL || instr->range()->CanBeMinusZero()) {
267 // Propagate to the left argument. If the left argument cannot be -0,
268 // then the result of the add/sub operation cannot be either.
269 AddToWorklist(instr->left());
270 }
271 } else if (value->IsMathMinMax()) {
272 HMathMinMax* instr = HMathMinMax::cast(value);
273 AddToWorklist(instr->right());
274 AddToWorklist(instr->left());
275 }
276 }
277
278 in_worklist_.Clear();
279 DCHECK(in_worklist_.IsEmpty());
280 DCHECK(worklist_.is_empty());
281 }
282
283
284 } // namespace internal
285 } // namespace v8
286