1// Copyright 2013 the V8 project authors. All rights reserved.
2// Redistribution and use in source and binary forms, with or without
3// modification, are permitted provided that the following conditions are
4// met:
5//
6//     * Redistributions of source code must retain the above copyright
7//       notice, this list of conditions and the following disclaimer.
8//     * Redistributions in binary form must reproduce the above
9//       copyright notice, this list of conditions and the following
10//       disclaimer in the documentation and/or other materials provided
11//       with the distribution.
12//     * Neither the name of Google Inc. nor the names of its
13//       contributors may be used to endorse or promote products derived
14//       from this software without specific prior written permission.
15//
16// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
17// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
18// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
19// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
20// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
21// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
22// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
26// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27
28#include "hydrogen-infer-representation.h"
29
30namespace v8 {
31namespace internal {
32
33void HInferRepresentationPhase::AddToWorklist(HValue* current) {
34  if (current->representation().IsTagged()) return;
35  if (!current->CheckFlag(HValue::kFlexibleRepresentation)) return;
36  if (in_worklist_.Contains(current->id())) return;
37  worklist_.Add(current, zone());
38  in_worklist_.Add(current->id());
39}
40
41
42void HInferRepresentationPhase::Run() {
43  // (1) Initialize bit vectors and count real uses. Each phi gets a
44  // bit-vector of length <number of phis>.
45  const ZoneList<HPhi*>* phi_list = graph()->phi_list();
46  int phi_count = phi_list->length();
47  ZoneList<BitVector*> connected_phis(phi_count, zone());
48  for (int i = 0; i < phi_count; ++i) {
49    phi_list->at(i)->InitRealUses(i);
50    BitVector* connected_set = new(zone()) BitVector(phi_count, zone());
51    connected_set->Add(i);
52    connected_phis.Add(connected_set, zone());
53  }
54
55  // (2) Do a fixed point iteration to find the set of connected phis.  A
56  // phi is connected to another phi if its value is used either directly or
57  // indirectly through a transitive closure of the def-use relation.
58  bool change = true;
59  while (change) {
60    change = false;
61    // We normally have far more "forward edges" than "backward edges",
62    // so we terminate faster when we walk backwards.
63    for (int i = phi_count - 1; i >= 0; --i) {
64      HPhi* phi = phi_list->at(i);
65      for (HUseIterator it(phi->uses()); !it.Done(); it.Advance()) {
66        HValue* use = it.value();
67        if (use->IsPhi()) {
68          int id = HPhi::cast(use)->phi_id();
69          if (connected_phis[i]->UnionIsChanged(*connected_phis[id]))
70            change = true;
71        }
72      }
73    }
74  }
75
76  // Set truncation flags for groups of connected phis. This is a conservative
77  // approximation; the flag will be properly re-computed after representations
78  // have been determined.
79  if (phi_count > 0) {
80    BitVector done(phi_count, zone());
81    for (int i = 0; i < phi_count; ++i) {
82      if (done.Contains(i)) continue;
83
84      // Check if all uses of all connected phis in this group are truncating.
85      bool all_uses_everywhere_truncating_int32 = true;
86      bool all_uses_everywhere_truncating_smi = true;
87      for (BitVector::Iterator it(connected_phis[i]);
88           !it.Done();
89           it.Advance()) {
90        int index = it.Current();
91        all_uses_everywhere_truncating_int32 &=
92            phi_list->at(index)->CheckFlag(HInstruction::kTruncatingToInt32);
93        all_uses_everywhere_truncating_smi &=
94            phi_list->at(index)->CheckFlag(HInstruction::kTruncatingToSmi);
95        done.Add(index);
96      }
97
98      if (!all_uses_everywhere_truncating_int32) {
99        // Clear truncation flag of this group of connected phis.
100        for (BitVector::Iterator it(connected_phis[i]);
101             !it.Done();
102             it.Advance()) {
103          int index = it.Current();
104          phi_list->at(index)->ClearFlag(HInstruction::kTruncatingToInt32);
105        }
106      }
107      if (!all_uses_everywhere_truncating_smi) {
108        // Clear truncation flag of this group of connected phis.
109        for (BitVector::Iterator it(connected_phis[i]);
110             !it.Done();
111             it.Advance()) {
112          int index = it.Current();
113          phi_list->at(index)->ClearFlag(HInstruction::kTruncatingToSmi);
114        }
115      }
116    }
117  }
118
119  // Simplify constant phi inputs where possible.
120  // This step uses kTruncatingToInt32 flags of phis.
121  for (int i = 0; i < phi_count; ++i) {
122    phi_list->at(i)->SimplifyConstantInputs();
123  }
124
125  // Use the phi reachability information from step 2 to
126  // sum up the non-phi use counts of all connected phis.
127  for (int i = 0; i < phi_count; ++i) {
128    HPhi* phi = phi_list->at(i);
129    for (BitVector::Iterator it(connected_phis[i]);
130         !it.Done();
131         it.Advance()) {
132      int index = it.Current();
133      HPhi* it_use = phi_list->at(index);
134      if (index != i) phi->AddNonPhiUsesFrom(it_use);  // Don't count twice.
135    }
136  }
137
138  // Initialize work list
139  for (int i = 0; i < graph()->blocks()->length(); ++i) {
140    HBasicBlock* block = graph()->blocks()->at(i);
141    const ZoneList<HPhi*>* phis = block->phis();
142    for (int j = 0; j < phis->length(); ++j) {
143      AddToWorklist(phis->at(j));
144    }
145
146    for (HInstructionIterator it(block); !it.Done(); it.Advance()) {
147      HInstruction* current = it.Current();
148      AddToWorklist(current);
149    }
150  }
151
152  // Do a fixed point iteration, trying to improve representations
153  while (!worklist_.is_empty()) {
154    HValue* current = worklist_.RemoveLast();
155    current->InferRepresentation(this);
156    in_worklist_.Remove(current->id());
157  }
158
159  // Lastly: any instruction that we don't have representation information
160  // for defaults to Tagged.
161  for (int i = 0; i < graph()->blocks()->length(); ++i) {
162    HBasicBlock* block = graph()->blocks()->at(i);
163    const ZoneList<HPhi*>* phis = block->phis();
164    for (int j = 0; j < phis->length(); ++j) {
165      HPhi* phi = phis->at(j);
166      if (phi->representation().IsNone()) {
167        phi->ChangeRepresentation(Representation::Tagged());
168      }
169    }
170    for (HInstructionIterator it(block); !it.Done(); it.Advance()) {
171      HInstruction* current = it.Current();
172      if (current->representation().IsNone() &&
173          current->CheckFlag(HInstruction::kFlexibleRepresentation)) {
174        if (current->CheckFlag(HInstruction::kCannotBeTagged)) {
175          current->ChangeRepresentation(Representation::Double());
176        } else {
177          current->ChangeRepresentation(Representation::Tagged());
178        }
179      }
180    }
181  }
182}
183
184} }  // namespace v8::internal
185