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