• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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/ast/scopes.h"
6 #include "src/compiler.h"
7 #include "src/compiler/all-nodes.h"
8 #include "src/compiler/common-operator.h"
9 #include "src/compiler/common-operator-reducer.h"
10 #include "src/compiler/dead-code-elimination.h"
11 #include "src/compiler/frame.h"
12 #include "src/compiler/graph.h"
13 #include "src/compiler/graph-reducer.h"
14 #include "src/compiler/graph-trimmer.h"
15 #include "src/compiler/graph-visualizer.h"
16 #include "src/compiler/js-graph.h"
17 #include "src/compiler/loop-analysis.h"
18 #include "src/compiler/node.h"
19 #include "src/compiler/node-marker.h"
20 #include "src/compiler/osr.h"
21 
22 namespace v8 {
23 namespace internal {
24 namespace compiler {
25 
OsrHelper(CompilationInfo * info)26 OsrHelper::OsrHelper(CompilationInfo* info)
27     : parameter_count_(info->scope()->num_parameters()),
28       stack_slot_count_(info->scope()->num_stack_slots() +
29                         info->osr_expr_stack_height()) {}
30 
31 
32 #ifdef DEBUG
33 #define TRACE_COND (FLAG_trace_turbo_graph && FLAG_trace_osr)
34 #else
35 #define TRACE_COND false
36 #endif
37 
38 #define TRACE(...)                       \
39   do {                                   \
40     if (TRACE_COND) PrintF(__VA_ARGS__); \
41   } while (false)
42 
43 
44 // Peel outer loops and rewire the graph so that control reduction can
45 // produce a properly formed graph.
PeelOuterLoopsForOsr(Graph * graph,CommonOperatorBuilder * common,Zone * tmp_zone,Node * dead,LoopTree * loop_tree,LoopTree::Loop * osr_loop,Node * osr_normal_entry,Node * osr_loop_entry)46 static void PeelOuterLoopsForOsr(Graph* graph, CommonOperatorBuilder* common,
47                                  Zone* tmp_zone, Node* dead,
48                                  LoopTree* loop_tree, LoopTree::Loop* osr_loop,
49                                  Node* osr_normal_entry, Node* osr_loop_entry) {
50   const size_t original_count = graph->NodeCount();
51   AllNodes all(tmp_zone, graph);
52   NodeVector tmp_inputs(tmp_zone);
53   Node* sentinel = graph->NewNode(dead->op());
54 
55   // Make a copy of the graph for each outer loop.
56   ZoneVector<NodeVector*> copies(tmp_zone);
57   for (LoopTree::Loop* loop = osr_loop->parent(); loop; loop = loop->parent()) {
58     void* stuff = tmp_zone->New(sizeof(NodeVector));
59     NodeVector* mapping =
60         new (stuff) NodeVector(original_count, sentinel, tmp_zone);
61     copies.push_back(mapping);
62     TRACE("OsrDuplication #%zu, depth %zu, header #%d:%s\n", copies.size(),
63           loop->depth(), loop_tree->HeaderNode(loop)->id(),
64           loop_tree->HeaderNode(loop)->op()->mnemonic());
65 
66     // Prepare the mapping for OSR values and the OSR loop entry.
67     mapping->at(osr_normal_entry->id()) = dead;
68     mapping->at(osr_loop_entry->id()) = dead;
69 
70     // The outer loops are dead in this copy.
71     for (LoopTree::Loop* outer = loop->parent(); outer;
72          outer = outer->parent()) {
73       for (Node* node : loop_tree->HeaderNodes(outer)) {
74         mapping->at(node->id()) = dead;
75         TRACE(" ---- #%d:%s -> dead (header)\n", node->id(),
76               node->op()->mnemonic());
77       }
78     }
79 
80     // Copy all nodes.
81     for (size_t i = 0; i < all.live.size(); i++) {
82       Node* orig = all.live[i];
83       Node* copy = mapping->at(orig->id());
84       if (copy != sentinel) {
85         // Mapping already exists.
86         continue;
87       }
88       if (orig->InputCount() == 0 || orig->opcode() == IrOpcode::kParameter ||
89           orig->opcode() == IrOpcode::kOsrValue) {
90         // No need to copy leaf nodes or parameters.
91         mapping->at(orig->id()) = orig;
92         continue;
93       }
94 
95       // Copy the node.
96       tmp_inputs.clear();
97       for (Node* input : orig->inputs()) {
98         tmp_inputs.push_back(mapping->at(input->id()));
99       }
100       copy = graph->NewNode(orig->op(), orig->InputCount(), &tmp_inputs[0]);
101       if (NodeProperties::IsTyped(orig)) {
102         NodeProperties::SetType(copy, NodeProperties::GetType(orig));
103       }
104       mapping->at(orig->id()) = copy;
105       TRACE(" copy #%d:%s -> #%d\n", orig->id(), orig->op()->mnemonic(),
106             copy->id());
107     }
108 
109     // Fix missing inputs.
110     for (Node* orig : all.live) {
111       Node* copy = mapping->at(orig->id());
112       for (int j = 0; j < copy->InputCount(); j++) {
113         if (copy->InputAt(j) == sentinel) {
114           copy->ReplaceInput(j, mapping->at(orig->InputAt(j)->id()));
115         }
116       }
117     }
118 
119     // Construct the entry into this loop from previous copies.
120 
121     // Gather the live loop header nodes, {loop_header} first.
122     Node* loop_header = loop_tree->HeaderNode(loop);
123     NodeVector header_nodes(tmp_zone);
124     header_nodes.reserve(loop->HeaderSize());
125     header_nodes.push_back(loop_header);  // put the loop header first.
126     for (Node* node : loop_tree->HeaderNodes(loop)) {
127       if (node != loop_header && all.IsLive(node)) {
128         header_nodes.push_back(node);
129       }
130     }
131 
132     // Gather backedges from the previous copies of the inner loops of {loop}.
133     NodeVectorVector backedges(tmp_zone);
134     TRACE("Gathering backedges...\n");
135     for (int i = 1; i < loop_header->InputCount(); i++) {
136       if (TRACE_COND) {
137         Node* control = loop_header->InputAt(i);
138         size_t incoming_depth = 0;
139         for (int j = 0; j < control->op()->ControlInputCount(); j++) {
140           Node* k = NodeProperties::GetControlInput(control, j);
141           incoming_depth =
142               std::max(incoming_depth, loop_tree->ContainingLoop(k)->depth());
143         }
144 
145         TRACE(" edge @%d #%d:%s, incoming depth %zu\n", i, control->id(),
146               control->op()->mnemonic(), incoming_depth);
147       }
148 
149       for (int pos = static_cast<int>(copies.size()) - 1; pos >= 0; pos--) {
150         backedges.push_back(NodeVector(tmp_zone));
151         backedges.back().reserve(header_nodes.size());
152 
153         NodeVector* previous_map = pos > 0 ? copies[pos - 1] : nullptr;
154 
155         for (Node* node : header_nodes) {
156           Node* input = node->InputAt(i);
157           if (previous_map) input = previous_map->at(input->id());
158           backedges.back().push_back(input);
159           TRACE("   node #%d:%s(@%d) = #%d:%s\n", node->id(),
160                 node->op()->mnemonic(), i, input->id(),
161                 input->op()->mnemonic());
162         }
163       }
164     }
165 
166     int backedge_count = static_cast<int>(backedges.size());
167     if (backedge_count == 1) {
168       // Simple case of single backedge, therefore a single entry.
169       int index = 0;
170       for (Node* node : header_nodes) {
171         Node* copy = mapping->at(node->id());
172         Node* input = backedges[0][index];
173         copy->ReplaceInput(0, input);
174         TRACE(" header #%d:%s(0) => #%d:%s\n", copy->id(),
175               copy->op()->mnemonic(), input->id(), input->op()->mnemonic());
176         index++;
177       }
178     } else {
179       // Complex case of multiple backedges from previous copies requires
180       // merging the backedges to create the entry into the loop header.
181       Node* merge = nullptr;
182       int index = 0;
183       for (Node* node : header_nodes) {
184         // Gather edge inputs into {tmp_inputs}.
185         tmp_inputs.clear();
186         for (int edge = 0; edge < backedge_count; edge++) {
187           tmp_inputs.push_back(backedges[edge][index]);
188         }
189         Node* copy = mapping->at(node->id());
190         Node* input;
191         if (node == loop_header) {
192           // Create the merge for the entry into the loop header.
193           input = merge = graph->NewNode(common->Merge(backedge_count),
194                                          backedge_count, &tmp_inputs[0]);
195           copy->ReplaceInput(0, merge);
196         } else {
197           // Create a phi that merges values at entry into the loop header.
198           DCHECK_NOT_NULL(merge);
199           DCHECK(IrOpcode::IsPhiOpcode(node->opcode()));
200           tmp_inputs.push_back(merge);
201           Node* phi = input = graph->NewNode(
202               common->ResizeMergeOrPhi(node->op(), backedge_count),
203               backedge_count + 1, &tmp_inputs[0]);
204           copy->ReplaceInput(0, phi);
205         }
206 
207         // Print the merge.
208         if (TRACE_COND) {
209           TRACE(" header #%d:%s(0) => #%d:%s(", copy->id(),
210                 copy->op()->mnemonic(), input->id(), input->op()->mnemonic());
211           for (size_t i = 0; i < tmp_inputs.size(); i++) {
212             if (i > 0) TRACE(", ");
213             Node* input = tmp_inputs[i];
214             TRACE("#%d:%s", input->id(), input->op()->mnemonic());
215           }
216           TRACE(")\n");
217         }
218 
219         index++;
220       }
221     }
222   }
223 
224   // Kill the outer loops in the original graph.
225   TRACE("Killing outer loop headers...\n");
226   for (LoopTree::Loop* outer = osr_loop->parent(); outer;
227        outer = outer->parent()) {
228     Node* loop_header = loop_tree->HeaderNode(outer);
229     loop_header->ReplaceUses(dead);
230     TRACE(" ---- #%d:%s\n", loop_header->id(), loop_header->op()->mnemonic());
231   }
232 
233   // Merge the ends of the graph copies.
234   Node* const end = graph->end();
235   int const input_count = end->InputCount();
236   for (int i = 0; i < input_count; ++i) {
237     NodeId const id = end->InputAt(i)->id();
238     for (NodeVector* const copy : copies) {
239       end->AppendInput(graph->zone(), copy->at(id));
240       NodeProperties::ChangeOp(end, common->End(end->InputCount()));
241     }
242   }
243 
244   if (FLAG_trace_turbo_graph) {  // Simple textual RPO.
245     OFStream os(stdout);
246     os << "-- Graph after OSR duplication -- " << std::endl;
247     os << AsRPO(*graph);
248   }
249 }
250 
251 
Deconstruct(JSGraph * jsgraph,CommonOperatorBuilder * common,Zone * tmp_zone)252 void OsrHelper::Deconstruct(JSGraph* jsgraph, CommonOperatorBuilder* common,
253                             Zone* tmp_zone) {
254   Graph* graph = jsgraph->graph();
255   Node* osr_normal_entry = nullptr;
256   Node* osr_loop_entry = nullptr;
257   Node* osr_loop = nullptr;
258 
259   for (Node* node : graph->start()->uses()) {
260     if (node->opcode() == IrOpcode::kOsrLoopEntry) {
261       osr_loop_entry = node;  // found the OSR loop entry
262     } else if (node->opcode() == IrOpcode::kOsrNormalEntry) {
263       osr_normal_entry = node;
264     }
265   }
266 
267   if (osr_loop_entry == nullptr) {
268     // No OSR entry found, do nothing.
269     CHECK(osr_normal_entry);
270     return;
271   }
272 
273   for (Node* use : osr_loop_entry->uses()) {
274     if (use->opcode() == IrOpcode::kLoop) {
275       CHECK(!osr_loop);             // should be only one OSR loop.
276       osr_loop = use;               // found the OSR loop.
277     }
278   }
279 
280   CHECK(osr_loop);  // Should have found the OSR loop.
281 
282   // Analyze the graph to determine how deeply nested the OSR loop is.
283   LoopTree* loop_tree = LoopFinder::BuildLoopTree(graph, tmp_zone);
284 
285   Node* dead = jsgraph->Dead();
286   LoopTree::Loop* loop = loop_tree->ContainingLoop(osr_loop);
287   if (loop->depth() > 0) {
288     PeelOuterLoopsForOsr(graph, common, tmp_zone, dead, loop_tree, loop,
289                          osr_normal_entry, osr_loop_entry);
290   }
291 
292   // Replace the normal entry with {Dead} and the loop entry with {Start}
293   // and run the control reducer to clean up the graph.
294   osr_normal_entry->ReplaceUses(dead);
295   osr_normal_entry->Kill();
296   osr_loop_entry->ReplaceUses(graph->start());
297   osr_loop_entry->Kill();
298 
299   // Remove the first input to the {osr_loop}.
300   int const live_input_count = osr_loop->InputCount() - 1;
301   CHECK_NE(0, live_input_count);
302   for (Node* const use : osr_loop->uses()) {
303     if (NodeProperties::IsPhi(use)) {
304       use->RemoveInput(0);
305       NodeProperties::ChangeOp(
306           use, common->ResizeMergeOrPhi(use->op(), live_input_count));
307     }
308   }
309   osr_loop->RemoveInput(0);
310   NodeProperties::ChangeOp(
311       osr_loop, common->ResizeMergeOrPhi(osr_loop->op(), live_input_count));
312 
313   // Run control reduction and graph trimming.
314   // TODO(bmeurer): The OSR deconstruction could be a regular reducer and play
315   // nice together with the rest, instead of having this custom stuff here.
316   GraphReducer graph_reducer(tmp_zone, graph);
317   DeadCodeElimination dce(&graph_reducer, graph, common);
318   CommonOperatorReducer cor(&graph_reducer, graph, common, jsgraph->machine());
319   graph_reducer.AddReducer(&dce);
320   graph_reducer.AddReducer(&cor);
321   graph_reducer.ReduceGraph();
322   GraphTrimmer trimmer(tmp_zone, graph);
323   NodeVector roots(tmp_zone);
324   jsgraph->GetCachedNodes(&roots);
325   trimmer.TrimGraph(roots.begin(), roots.end());
326 }
327 
328 
SetupFrame(Frame * frame)329 void OsrHelper::SetupFrame(Frame* frame) {
330   // The optimized frame will subsume the unoptimized frame. Do so by reserving
331   // the first spill slots.
332   frame->ReserveSpillSlots(UnoptimizedFrameSlots());
333 }
334 
335 }  // namespace compiler
336 }  // namespace internal
337 }  // namespace v8
338