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-infer-representation.h"
6
7namespace v8 {
8namespace internal {
9
10void HInferRepresentationPhase::AddToWorklist(HValue* current) {
11  if (current->representation().IsTagged()) return;
12  if (!current->CheckFlag(HValue::kFlexibleRepresentation)) return;
13  if (in_worklist_.Contains(current->id())) return;
14  worklist_.Add(current, zone());
15  in_worklist_.Add(current->id());
16}
17
18
19void HInferRepresentationPhase::Run() {
20  // (1) Initialize bit vectors and count real uses. Each phi gets a
21  // bit-vector of length <number of phis>.
22  const ZoneList<HPhi*>* phi_list = graph()->phi_list();
23  int phi_count = phi_list->length();
24  ZoneList<BitVector*> connected_phis(phi_count, zone());
25  for (int i = 0; i < phi_count; ++i) {
26    phi_list->at(i)->InitRealUses(i);
27    BitVector* connected_set = new(zone()) BitVector(phi_count, zone());
28    connected_set->Add(i);
29    connected_phis.Add(connected_set, zone());
30  }
31
32  // (2) Do a fixed point iteration to find the set of connected phis.  A
33  // phi is connected to another phi if its value is used either directly or
34  // indirectly through a transitive closure of the def-use relation.
35  bool change = true;
36  while (change) {
37    change = false;
38    // We normally have far more "forward edges" than "backward edges",
39    // so we terminate faster when we walk backwards.
40    for (int i = phi_count - 1; i >= 0; --i) {
41      HPhi* phi = phi_list->at(i);
42      for (HUseIterator it(phi->uses()); !it.Done(); it.Advance()) {
43        HValue* use = it.value();
44        if (use->IsPhi()) {
45          int id = HPhi::cast(use)->phi_id();
46          if (connected_phis[i]->UnionIsChanged(*connected_phis[id]))
47            change = true;
48        }
49      }
50    }
51  }
52
53  // Set truncation flags for groups of connected phis. This is a conservative
54  // approximation; the flag will be properly re-computed after representations
55  // have been determined.
56  if (phi_count > 0) {
57    BitVector done(phi_count, zone());
58    for (int i = 0; i < phi_count; ++i) {
59      if (done.Contains(i)) continue;
60
61      // Check if all uses of all connected phis in this group are truncating.
62      bool all_uses_everywhere_truncating_int32 = true;
63      bool all_uses_everywhere_truncating_smi = true;
64      for (BitVector::Iterator it(connected_phis[i]);
65           !it.Done();
66           it.Advance()) {
67        int index = it.Current();
68        all_uses_everywhere_truncating_int32 &=
69            phi_list->at(index)->CheckFlag(HInstruction::kTruncatingToInt32);
70        all_uses_everywhere_truncating_smi &=
71            phi_list->at(index)->CheckFlag(HInstruction::kTruncatingToSmi);
72        done.Add(index);
73      }
74
75      if (!all_uses_everywhere_truncating_int32) {
76        // Clear truncation flag of this group of connected phis.
77        for (BitVector::Iterator it(connected_phis[i]);
78             !it.Done();
79             it.Advance()) {
80          int index = it.Current();
81          phi_list->at(index)->ClearFlag(HInstruction::kTruncatingToInt32);
82        }
83      }
84      if (!all_uses_everywhere_truncating_smi) {
85        // Clear truncation flag of this group of connected phis.
86        for (BitVector::Iterator it(connected_phis[i]);
87             !it.Done();
88             it.Advance()) {
89          int index = it.Current();
90          phi_list->at(index)->ClearFlag(HInstruction::kTruncatingToSmi);
91        }
92      }
93    }
94  }
95
96  // Simplify constant phi inputs where possible.
97  // This step uses kTruncatingToInt32 flags of phis.
98  for (int i = 0; i < phi_count; ++i) {
99    phi_list->at(i)->SimplifyConstantInputs();
100  }
101
102  // Use the phi reachability information from step 2 to
103  // sum up the non-phi use counts of all connected phis.
104  for (int i = 0; i < phi_count; ++i) {
105    HPhi* phi = phi_list->at(i);
106    for (BitVector::Iterator it(connected_phis[i]);
107         !it.Done();
108         it.Advance()) {
109      int index = it.Current();
110      HPhi* it_use = phi_list->at(index);
111      if (index != i) phi->AddNonPhiUsesFrom(it_use);  // Don't count twice.
112    }
113  }
114
115  // Initialize work list
116  for (int i = 0; i < graph()->blocks()->length(); ++i) {
117    HBasicBlock* block = graph()->blocks()->at(i);
118    const ZoneList<HPhi*>* phis = block->phis();
119    for (int j = 0; j < phis->length(); ++j) {
120      AddToWorklist(phis->at(j));
121    }
122
123    for (HInstructionIterator it(block); !it.Done(); it.Advance()) {
124      HInstruction* current = it.Current();
125      AddToWorklist(current);
126    }
127  }
128
129  // Do a fixed point iteration, trying to improve representations
130  while (!worklist_.is_empty()) {
131    HValue* current = worklist_.RemoveLast();
132    current->InferRepresentation(this);
133    in_worklist_.Remove(current->id());
134  }
135
136  // Lastly: any instruction that we don't have representation information
137  // for defaults to Tagged.
138  for (int i = 0; i < graph()->blocks()->length(); ++i) {
139    HBasicBlock* block = graph()->blocks()->at(i);
140    const ZoneList<HPhi*>* phis = block->phis();
141    for (int j = 0; j < phis->length(); ++j) {
142      HPhi* phi = phis->at(j);
143      if (phi->representation().IsNone()) {
144        phi->ChangeRepresentation(Representation::Tagged());
145      }
146    }
147    for (HInstructionIterator it(block); !it.Done(); it.Advance()) {
148      HInstruction* current = it.Current();
149      if (current->representation().IsNone() &&
150          current->CheckFlag(HInstruction::kFlexibleRepresentation)) {
151        if (current->CheckFlag(HInstruction::kCannotBeTagged)) {
152          current->ChangeRepresentation(Representation::Double());
153        } else {
154          current->ChangeRepresentation(Representation::Tagged());
155        }
156      }
157    }
158  }
159}
160
161}  // namespace internal
162}  // namespace v8
163