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 1366169 : : 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 16876002 : void HRangeAnalysisPhase::TraceRange(const char* msg, ...) {
27 16876002 : 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 16876002 : }
34 :
35 :
36 283728 : void HRangeAnalysisPhase::Run() {
37 4795294 : HBasicBlock* block(graph()->entry_block());
38 283728 : ZoneList<Pending> stack(graph()->blocks()->length(), zone());
39 5079022 : while (block != NULL) {
40 4511566 : TraceRange("Analyzing block B%d\n", block->block_id());
41 :
42 : // Infer range based on control flow.
43 4511579 : if (block->predecessors()->length() == 1) {
44 4116530 : HBasicBlock* pred = block->predecessors()->first();
45 7564532 : if (pred->end()->IsCompareNumericAndBranch()) {
46 : InferControlFlowRange(HCompareNumericAndBranch::cast(pred->end()),
47 334268 : block);
48 : }
49 : }
50 :
51 : // Process phi instructions.
52 301146 : for (int i = 0; i < block->phis()->length(); ++i) {
53 301145 : HPhi* phi = block->phis()->at(i);
54 301145 : InferRange(phi);
55 : }
56 :
57 : // Go through all instructions of the current block.
58 29725973 : for (HInstructionIterator it(block); !it.Done(); it.Advance()) {
59 : HValue* value = it.Current();
60 25214349 : InferRange(value);
61 :
62 : // Compute the bailout-on-minus-zero flag.
63 25214307 : 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 369992 : if (from.IsSmiOrInteger32()) {
70 : DCHECK(instr->to().IsTagged() ||
71 : instr->to().IsDouble() ||
72 : instr->to().IsSmiOrInteger32());
73 175922 : PropagateMinusZeroChecks(instr->value());
74 : }
75 : }
76 : }
77 :
78 : // Continue analysis in all dominated blocks.
79 : const ZoneList<HBasicBlock*>* dominated_blocks(block->dominated_blocks());
80 4511624 : if (!dominated_blocks->is_empty()) {
81 : // Continue with first dominated block, and push the
82 : // remaining blocks on the stack (in reverse order).
83 2861729 : int last_changed_range = changed_ranges_.length();
84 4227899 : for (int i = dominated_blocks->length() - 1; i > 0; --i) {
85 2732339 : stack.Add(Pending(dominated_blocks->at(i), last_changed_range), zone());
86 : }
87 2861730 : block = dominated_blocks->at(0);
88 1649895 : } else if (!stack.is_empty()) {
89 : // Pop next pending block from stack.
90 : Pending pending = stack.RemoveLast();
91 1366171 : 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 283729 : }
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 632930 : void HRangeAnalysisPhase::InferControlFlowRange(HCompareNumericAndBranch* test,
118 : HBasicBlock* dest) {
119 : DCHECK((test->FirstSuccessor() == dest) == (test->SecondSuccessor() != dest));
120 334268 : if (test->representation().IsSmiOrInteger32()) {
121 : Token::Value op = test->token();
122 298662 : if (test->SecondSuccessor() == dest) {
123 149331 : op = Token::NegateCompareOp(op);
124 : }
125 298662 : Token::Value inverted_op = Token::ReverseCompareOp(op);
126 298662 : UpdateControlFlowRange(op, test->left(), test->right());
127 298662 : UpdateControlFlowRange(inverted_op, test->right(), test->left());
128 : }
129 334268 : }
130 :
131 :
132 : // We know that value [op] other. Use this information to update the range on
133 : // value.
134 597323 : void HRangeAnalysisPhase::UpdateControlFlowRange(Token::Value op,
135 597323 : HValue* value,
136 1194646 : HValue* other) {
137 : Range temp_range;
138 597323 : 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 597323 : other->id());
145 :
146 597324 : if (op == Token::EQ || op == Token::EQ_STRICT) {
147 : // The same range has to apply for value.
148 447940 : new_range = range->Copy(graph()->zone());
149 447940 : } else if (op == Token::LT || op == Token::LTE) {
150 149278 : new_range = range->CopyClearLower(graph()->zone());
151 149278 : if (op == Token::LT) {
152 74639 : new_range->AddConstant(-1);
153 : }
154 298662 : } else if (op == Token::GT || op == Token::GTE) {
155 149278 : new_range = range->CopyClearUpper(graph()->zone());
156 149278 : if (op == Token::GT) {
157 74639 : new_range->AddConstant(1);
158 : }
159 : }
160 :
161 1045263 : if (new_range != NULL && !new_range->IsMostGeneric()) {
162 438859 : AddRange(value, new_range);
163 : }
164 597323 : }
165 :
166 :
167 46417528 : void HRangeAnalysisPhase::InferRange(HValue* value) {
168 : DCHECK(!value->HasRange());
169 25515449 : if (!value->representation().IsNone()) {
170 10450941 : value->ComputeInitialRange(graph()->zone());
171 10451067 : 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 20902079 : range->upper());
177 : }
178 25515496 : }
179 :
180 :
181 1366171 : void HRangeAnalysisPhase::RollBackTo(int index) {
182 : DCHECK(index <= changed_ranges_.length());
183 3568544 : for (int i = index; i < changed_ranges_.length(); ++i) {
184 2620474 : changed_ranges_[i]->RemoveLastAddedRange();
185 : }
186 : changed_ranges_.Rewind(index);
187 1366171 : }
188 :
189 :
190 877718 : void HRangeAnalysisPhase::AddRange(HValue* value, Range* range) {
191 1755436 : Range* original_range = value->range();
192 438859 : value->AddNewRange(range, graph()->zone());
193 438859 : changed_ranges_.Add(value, zone());
194 438859 : Range* new_range = value->range();
195 : TraceRange("Updated range of %d set to [%d,%d]\n",
196 : value->id(),
197 : new_range->lower(),
198 438859 : new_range->upper());
199 438859 : if (original_range != NULL) {
200 : TraceRange("Original range was [%d,%d]\n",
201 : original_range->lower(),
202 438859 : original_range->upper());
203 : }
204 : TraceRange("New information was [%d,%d]\n",
205 : range->lower(),
206 438859 : range->upper());
207 438858 : }
208 :
209 :
210 175922 : void HRangeAnalysisPhase::PropagateMinusZeroChecks(HValue* value) {
211 : DCHECK(worklist_.is_empty());
212 : DCHECK(in_worklist_.IsEmpty());
213 :
214 175922 : AddToWorklist(value);
215 597313 : while (!worklist_.is_empty()) {
216 666856 : value = worklist_.RemoveLast();
217 :
218 245465 : if (value->IsPhi()) {
219 : // For phis, we must propagate the check to all of its inputs.
220 : HPhi* phi = HPhi::cast(value);
221 149554 : for (int i = 0; i < phi->OperandCount(); ++i) {
222 60065 : AddToWorklist(phi->OperandAt(i));
223 : }
224 216041 : } else if (value->IsUnaryMathOperation()) {
225 : HUnaryMathOperation* instr = HUnaryMathOperation::cast(value);
226 39280 : if (instr->representation().IsSmiOrInteger32() &&
227 : !instr->value()->representation().Equals(instr->representation())) {
228 38978 : if (instr->value()->range() == NULL ||
229 : instr->value()->range()->CanBeMinusZero()) {
230 : instr->SetFlag(HValue::kBailoutOnMinusZero);
231 : }
232 : }
233 58920 : if (instr->RequiredInputRepresentation(0).IsSmiOrInteger32() &&
234 : instr->representation().Equals(
235 19640 : instr->RequiredInputRepresentation(0))) {
236 0 : AddToWorklist(instr->value());
237 : }
238 196402 : } else if (value->IsChange()) {
239 : HChange* instr = HChange::cast(value);
240 50143 : if (!instr->from().IsSmiOrInteger32() &&
241 45042 : !instr->CanTruncateToInt32() &&
242 37300 : (instr->value()->range() == NULL ||
243 : instr->value()->range()->CanBeMinusZero())) {
244 : instr->SetFlag(HValue::kBailoutOnMinusZero);
245 : }
246 170049 : } else if (value->IsForceRepresentation()) {
247 : HForceRepresentation* instr = HForceRepresentation::cast(value);
248 0 : AddToWorklist(instr->value());
249 170050 : } else if (value->IsMod()) {
250 : HMod* instr = HMod::cast(value);
251 6710 : if (instr->range() == NULL || instr->range()->CanBeMinusZero()) {
252 : instr->SetFlag(HValue::kBailoutOnMinusZero);
253 1362 : AddToWorklist(instr->left());
254 : }
255 330976 : } else if (value->IsDiv() || value->IsMul()) {
256 : HBinaryOperation* instr = HBinaryOperation::cast(value);
257 14162 : if (instr->range() == NULL || instr->range()->CanBeMinusZero()) {
258 : instr->SetFlag(HValue::kBailoutOnMinusZero);
259 : }
260 7087 : AddToWorklist(instr->right());
261 7087 : AddToWorklist(instr->left());
262 159608 : } else if (value->IsMathFloorOfDiv()) {
263 : HMathFloorOfDiv* instr = HMathFloorOfDiv::cast(value);
264 : instr->SetFlag(HValue::kBailoutOnMinusZero);
265 227473 : } else if (value->IsAdd() || value->IsSub()) {
266 : HBinaryOperation* instr = HBinaryOperation::cast(value);
267 174508 : 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 13122 : AddToWorklist(instr->left());
271 : }
272 64656 : } else if (value->IsMathMinMax()) {
273 : HMathMinMax* instr = HMathMinMax::cast(value);
274 232 : AddToWorklist(instr->right());
275 232 : AddToWorklist(instr->left());
276 : }
277 : }
278 :
279 175924 : in_worklist_.Clear();
280 : DCHECK(in_worklist_.IsEmpty());
281 : DCHECK(worklist_.is_empty());
282 175924 : }
283 :
284 :
285 : } // namespace internal
286 : } // namespace v8
|
