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
7namespace v8 {
8namespace internal {
9
10
11class Pending {
12 public:
13  Pending(HBasicBlock* block, int last_changed_range)
14      : block_(block), last_changed_range_(last_changed_range) {}
15
16  HBasicBlock* block() const { return block_; }
17  int last_changed_range() const { return last_changed_range_; }
18
19 private:
20  HBasicBlock* block_;
21  int last_changed_range_;
22};
23
24
25void 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
35void 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
109void 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
122void 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.
139void 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
172void 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
186void 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
195void 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
215void 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