Line data Source code
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:
14 : Pending(HBasicBlock* block, int last_changed_range)
15 1359572 : : block_(block), last_changed_range_(last_changed_range) {}
16 :
17 : HBasicBlock* block() const { return block_; }
18 : int last_changed_range() const { return last_changed_range_; }
19 :
20 : private:
21 : HBasicBlock* block_;
22 : int last_changed_range_;
23 : };
24 :
25 :
26 16833764 : void HRangeAnalysisPhase::TraceRange(const char* msg, ...) {
27 16833764 : if (FLAG_trace_range) {
28 : va_list arguments;
29 0 : va_start(arguments, msg);
30 0 : base::OS::VPrint(msg, arguments);
31 0 : va_end(arguments);
32 : }
33 16833764 : }
34 :
35 :
36 283197 : void HRangeAnalysisPhase::Run() {
37 4776737 : HBasicBlock* block(graph()->entry_block());
38 283197 : ZoneList<Pending> stack(graph()->blocks()->length(), zone());
39 5059939 : while (block != NULL) {
40 4493540 : TraceRange("Analyzing block B%d\n", block->block_id());
41 :
42 : // Infer range based on control flow.
43 4493541 : if (block->predecessors()->length() == 1) {
44 4100300 : HBasicBlock* pred = block->predecessors()->first();
45 7533526 : if (pred->end()->IsCompareNumericAndBranch()) {
46 : InferControlFlowRange(HCompareNumericAndBranch::cast(pred->end()),
47 333538 : block);
48 : }
49 : }
50 :
51 : // Process phi instructions.
52 299951 : for (int i = 0; i < block->phis()->length(); ++i) {
53 299951 : HPhi* phi = block->phis()->at(i);
54 299951 : InferRange(phi);
55 : }
56 :
57 : // Go through all instructions of the current block.
58 29636660 : for (HInstructionIterator it(block); !it.Done(); it.Advance()) {
59 : HValue* value = it.Current();
60 25143105 : InferRange(value);
61 :
62 : // Compute the bailout-on-minus-zero flag.
63 25143062 : 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 369526 : if (from.IsSmiOrInteger32()) {
70 : DCHECK(instr->to().IsTagged() ||
71 : instr->to().IsDouble() ||
72 : instr->to().IsSmiOrInteger32());
73 175712 : PropagateMinusZeroChecks(instr->value());
74 : }
75 : }
76 : }
77 :
78 : // Continue analysis in all dominated blocks.
79 : const ZoneList<HBasicBlock*>* dominated_blocks(block->dominated_blocks());
80 4493555 : if (!dominated_blocks->is_empty()) {
81 : // Continue with first dominated block, and push the
82 : // remaining blocks on the stack (in reverse order).
83 2850790 : int last_changed_range = changed_ranges_.length();
84 4210363 : for (int i = dominated_blocks->length() - 1; i > 0; --i) {
85 2719145 : stack.Add(Pending(dominated_blocks->at(i), last_changed_range), zone());
86 : }
87 2850791 : block = dominated_blocks->at(0);
88 1642765 : } else if (!stack.is_empty()) {
89 : // Pop next pending block from stack.
90 : Pending pending = stack.RemoveLast();
91 1359572 : 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 283197 : }
102 :
103 :
104 0 : 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 0 : }
115 :
116 :
117 631668 : void HRangeAnalysisPhase::InferControlFlowRange(HCompareNumericAndBranch* test,
118 : HBasicBlock* dest) {
119 : DCHECK((test->FirstSuccessor() == dest) == (test->SecondSuccessor() != dest));
120 333538 : if (test->representation().IsSmiOrInteger32()) {
121 : Token::Value op = test->token();
122 298130 : if (test->SecondSuccessor() == dest) {
123 149065 : op = Token::NegateCompareOp(op);
124 : }
125 298130 : Token::Value inverted_op = Token::ReverseCompareOp(op);
126 298130 : UpdateControlFlowRange(op, test->left(), test->right());
127 298130 : UpdateControlFlowRange(inverted_op, test->right(), test->left());
128 : }
129 333538 : }
130 :
131 :
132 : // We know that value [op] other. Use this information to update the range on
133 : // value.
134 596260 : void HRangeAnalysisPhase::UpdateControlFlowRange(Token::Value op,
135 596260 : HValue* value,
136 1192520 : HValue* other) {
137 : Range temp_range;
138 596260 : 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 596260 : other->id());
145 :
146 596260 : if (op == Token::EQ || op == Token::EQ_STRICT) {
147 : // The same range has to apply for value.
148 447322 : new_range = range->Copy(graph()->zone());
149 447322 : } else if (op == Token::LT || op == Token::LTE) {
150 149192 : new_range = range->CopyClearLower(graph()->zone());
151 149192 : if (op == Token::LT) {
152 74596 : new_range->AddConstant(-1);
153 : }
154 298130 : } else if (op == Token::GT || op == Token::GTE) {
155 149192 : new_range = range->CopyClearUpper(graph()->zone());
156 149192 : if (op == Token::GT) {
157 74596 : new_range->AddConstant(1);
158 : }
159 : }
160 :
161 1043582 : if (new_range != NULL && !new_range->IsMostGeneric()) {
162 438203 : AddRange(value, new_range);
163 : }
164 596260 : }
165 :
166 :
167 46302382 : void HRangeAnalysisPhase::InferRange(HValue* value) {
168 : DCHECK(!value->HasRange());
169 25443012 : if (!value->representation().IsNone()) {
170 10429664 : value->ComputeInitialRange(graph()->zone());
171 10429690 : 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 20859370 : range->upper());
177 : }
178 25443047 : }
179 :
180 :
181 1359573 : void HRangeAnalysisPhase::RollBackTo(int index) {
182 : DCHECK(index <= changed_ranges_.length());
183 3554064 : for (int i = index; i < changed_ranges_.length(); ++i) {
184 2611950 : changed_ranges_[i]->RemoveLastAddedRange();
185 : }
186 : changed_ranges_.Rewind(index);
187 1359573 : }
188 :
189 :
190 876406 : void HRangeAnalysisPhase::AddRange(HValue* value, Range* range) {
191 1752812 : Range* original_range = value->range();
192 438203 : value->AddNewRange(range, graph()->zone());
193 438203 : changed_ranges_.Add(value, zone());
194 438203 : Range* new_range = value->range();
195 : TraceRange("Updated range of %d set to [%d,%d]\n",
196 : value->id(),
197 : new_range->lower(),
198 438203 : new_range->upper());
199 438203 : if (original_range != NULL) {
200 : TraceRange("Original range was [%d,%d]\n",
201 : original_range->lower(),
202 438203 : original_range->upper());
203 : }
204 : TraceRange("New information was [%d,%d]\n",
205 : range->lower(),
206 438203 : range->upper());
207 438203 : }
208 :
209 :
210 175712 : void HRangeAnalysisPhase::PropagateMinusZeroChecks(HValue* value) {
211 : DCHECK(worklist_.is_empty());
212 : DCHECK(in_worklist_.IsEmpty());
213 :
214 175712 : AddToWorklist(value);
215 596877 : while (!worklist_.is_empty()) {
216 666617 : value = worklist_.RemoveLast();
217 :
218 245454 : if (value->IsPhi()) {
219 : // For phis, we must propagate the check to all of its inputs.
220 : HPhi* phi = HPhi::cast(value);
221 150734 : for (int i = 0; i < phi->OperandCount(); ++i) {
222 60537 : AddToWorklist(phi->OperandAt(i));
223 : }
224 215793 : } else if (value->IsUnaryMathOperation()) {
225 : HUnaryMathOperation* instr = HUnaryMathOperation::cast(value);
226 39262 : if (instr->representation().IsSmiOrInteger32() &&
227 : !instr->value()->representation().Equals(instr->representation())) {
228 38960 : if (instr->value()->range() == NULL ||
229 : instr->value()->range()->CanBeMinusZero()) {
230 : instr->SetFlag(HValue::kBailoutOnMinusZero);
231 : }
232 : }
233 58893 : if (instr->RequiredInputRepresentation(0).IsSmiOrInteger32() &&
234 : instr->representation().Equals(
235 19631 : instr->RequiredInputRepresentation(0))) {
236 0 : AddToWorklist(instr->value());
237 : }
238 196162 : } else if (value->IsChange()) {
239 : HChange* instr = HChange::cast(value);
240 50297 : if (!instr->from().IsSmiOrInteger32() &&
241 45278 : !instr->CanTruncateToInt32() &&
242 37612 : (instr->value()->range() == NULL ||
243 : instr->value()->range()->CanBeMinusZero())) {
244 : instr->SetFlag(HValue::kBailoutOnMinusZero);
245 : }
246 169733 : } else if (value->IsForceRepresentation()) {
247 : HForceRepresentation* instr = HForceRepresentation::cast(value);
248 0 : AddToWorklist(instr->value());
249 169733 : } else if (value->IsMod()) {
250 : HMod* instr = HMod::cast(value);
251 6636 : if (instr->range() == NULL || instr->range()->CanBeMinusZero()) {
252 : instr->SetFlag(HValue::kBailoutOnMinusZero);
253 1362 : AddToWorklist(instr->left());
254 : }
255 330490 : } else if (value->IsDiv() || value->IsMul()) {
256 : HBinaryOperation* instr = HBinaryOperation::cast(value);
257 13970 : if (instr->range() == NULL || instr->range()->CanBeMinusZero()) {
258 : instr->SetFlag(HValue::kBailoutOnMinusZero);
259 : }
260 6991 : AddToWorklist(instr->right());
261 6991 : AddToWorklist(instr->left());
262 159421 : } else if (value->IsMathFloorOfDiv()) {
263 : HMathFloorOfDiv* instr = HMathFloorOfDiv::cast(value);
264 : instr->SetFlag(HValue::kBailoutOnMinusZero);
265 227219 : } else if (value->IsAdd() || value->IsSub()) {
266 : HBinaryOperation* instr = HBinaryOperation::cast(value);
267 174540 : 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 13168 : AddToWorklist(instr->left());
271 : }
272 64498 : } else if (value->IsMathMinMax()) {
273 : HMathMinMax* instr = HMathMinMax::cast(value);
274 231 : AddToWorklist(instr->right());
275 231 : AddToWorklist(instr->left());
276 : }
277 : }
278 :
279 175713 : in_worklist_.Clear();
280 : DCHECK(in_worklist_.IsEmpty());
281 : DCHECK(worklist_.is_empty());
282 175713 : }
283 :
284 :
285 : } // namespace internal
286 : } // namespace v8
|
