1// Copyright 2014 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/base/adapters.h"
6#include "src/compiler/js-graph.h"
7#include "src/compiler/liveness-analyzer.h"
8#include "src/compiler/node.h"
9#include "src/compiler/node-matchers.h"
10#include "src/compiler/state-values-utils.h"
11
12namespace v8 {
13namespace internal {
14namespace compiler {
15
16
17LivenessAnalyzer::LivenessAnalyzer(size_t local_count, Zone* zone)
18    : zone_(zone), blocks_(zone), local_count_(local_count), queue_(zone) {}
19
20
21void LivenessAnalyzer::Print(std::ostream& os) {
22  for (auto block : blocks_) {
23    block->Print(os);
24    os << std::endl;
25  }
26}
27
28
29LivenessAnalyzerBlock* LivenessAnalyzer::NewBlock() {
30  LivenessAnalyzerBlock* result =
31      new (zone()->New(sizeof(LivenessAnalyzerBlock)))
32          LivenessAnalyzerBlock(blocks_.size(), local_count_, zone());
33  blocks_.push_back(result);
34  return result;
35}
36
37
38LivenessAnalyzerBlock* LivenessAnalyzer::NewBlock(
39    LivenessAnalyzerBlock* predecessor) {
40  LivenessAnalyzerBlock* result = NewBlock();
41  result->AddPredecessor(predecessor);
42  return result;
43}
44
45
46void LivenessAnalyzer::Queue(LivenessAnalyzerBlock* block) {
47  if (!block->IsQueued()) {
48    block->SetQueued();
49    queue_.push(block);
50  }
51}
52
53
54void LivenessAnalyzer::Run(NonLiveFrameStateSlotReplacer* replacer) {
55  if (local_count_ == 0) {
56    // No local variables => nothing to do.
57    return;
58  }
59
60  // Put all blocks into the queue.
61  DCHECK(queue_.empty());
62  for (auto block : blocks_) {
63    Queue(block);
64  }
65
66  // Compute the fix-point.
67  BitVector working_area(static_cast<int>(local_count_), zone_);
68  while (!queue_.empty()) {
69    LivenessAnalyzerBlock* block = queue_.front();
70    queue_.pop();
71    block->Process(&working_area, nullptr);
72
73    for (auto i = block->pred_begin(); i != block->pred_end(); i++) {
74      if ((*i)->UpdateLive(&working_area)) {
75        Queue(*i);
76      }
77    }
78  }
79
80  // Update the frame states according to the liveness.
81  for (auto block : blocks_) {
82    block->Process(&working_area, replacer);
83  }
84}
85
86LivenessAnalyzerBlock::LivenessAnalyzerBlock(size_t id, size_t local_count,
87                                             Zone* zone)
88    : entries_(zone),
89      predecessors_(zone),
90      live_(local_count == 0 ? 1 : static_cast<int>(local_count), zone),
91      queued_(false),
92      id_(id) {}
93
94void LivenessAnalyzerBlock::Process(BitVector* result,
95                                    NonLiveFrameStateSlotReplacer* replacer) {
96  queued_ = false;
97
98  // Copy the bitvector to the target bit vector.
99  result->CopyFrom(live_);
100
101  for (auto entry : base::Reversed(entries_)) {
102    switch (entry.kind()) {
103      case Entry::kLookup:
104        result->Add(entry.var());
105        break;
106      case Entry::kBind:
107        result->Remove(entry.var());
108        break;
109      case Entry::kCheckpoint:
110        if (replacer != nullptr) {
111          replacer->ClearNonLiveFrameStateSlots(entry.node(), result);
112        }
113        break;
114    }
115  }
116}
117
118
119bool LivenessAnalyzerBlock::UpdateLive(BitVector* working_area) {
120  return live_.UnionIsChanged(*working_area);
121}
122
123
124void NonLiveFrameStateSlotReplacer::ClearNonLiveFrameStateSlots(
125    Node* frame_state, BitVector* liveness) {
126  DCHECK_EQ(frame_state->opcode(), IrOpcode::kFrameState);
127  Node* locals_state = frame_state->InputAt(1);
128  DCHECK_EQ(locals_state->opcode(), IrOpcode::kStateValues);
129  int count = static_cast<int>(StateValuesAccess(locals_state).size());
130  DCHECK_EQ(count == 0 ? 1 : count, liveness->length());
131  for (int i = 0; i < count; i++) {
132    bool live = liveness->Contains(i) || permanently_live_.Contains(i);
133    if (!live || locals_state->InputAt(i) != replacement_node_) {
134      Node* new_values = ClearNonLiveStateValues(locals_state, liveness);
135      frame_state->ReplaceInput(1, new_values);
136      break;
137    }
138  }
139}
140
141
142Node* NonLiveFrameStateSlotReplacer::ClearNonLiveStateValues(
143    Node* values, BitVector* liveness) {
144  DCHECK(inputs_buffer_.empty());
145  for (StateValuesAccess::TypedNode node : StateValuesAccess(values)) {
146    // Index of the next variable is its furure index in the inputs buffer,
147    // i.e., the buffer's size.
148    int var = static_cast<int>(inputs_buffer_.size());
149    bool live = liveness->Contains(var) || permanently_live_.Contains(var);
150    inputs_buffer_.push_back(live ? node.node : replacement_node_);
151  }
152  Node* result = state_values_cache()->GetNodeForValues(
153      inputs_buffer_.empty() ? nullptr : &(inputs_buffer_.front()),
154      inputs_buffer_.size());
155  inputs_buffer_.clear();
156  return result;
157}
158
159
160void LivenessAnalyzerBlock::Print(std::ostream& os) {
161  os << "Block " << id();
162  bool first = true;
163  for (LivenessAnalyzerBlock* pred : predecessors_) {
164    if (!first) {
165      os << ", ";
166    } else {
167      os << "; predecessors: ";
168      first = false;
169    }
170    os << pred->id();
171  }
172  os << std::endl;
173
174  for (auto entry : entries_) {
175    os << "    ";
176    switch (entry.kind()) {
177      case Entry::kLookup:
178        os << "- Lookup " << entry.var() << std::endl;
179        break;
180      case Entry::kBind:
181        os << "- Bind " << entry.var() << std::endl;
182        break;
183      case Entry::kCheckpoint:
184        os << "- Checkpoint " << entry.node()->id() << std::endl;
185        break;
186    }
187  }
188
189  if (live_.length() > 0) {
190    os << "    Live set: ";
191    for (int i = 0; i < live_.length(); i++) {
192      os << (live_.Contains(i) ? "L" : ".");
193    }
194    os << std::endl;
195  }
196}
197
198}  // namespace compiler
199}  // namespace internal
200}  // namespace v8
201