Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(177)

Side by Side Diff: tools/turbolizer/graph-layout.js

Issue 729913004: Add a html-based visualizer for TurboFan graphs (Closed) Base URL: https://chromium.googlesource.com/v8/v8.git@master
Patch Set: Review feedback Created 4 years, 7 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch
« no previous file with comments | « tools/turbolizer/expand-all.jpg ('k') | tools/turbolizer/graph-view.js » ('j') | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
(Empty)
1 // Copyright 2015 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 var DEFAULT_NODE_ROW_SEPARATION = 130
6
7 var traceLayout = false;
8
9 function newGraphOccupation(graph){
10 var isSlotFilled = [];
11 var maxSlot = 0;
12 var minSlot = 0;
13 var nodeOccupation = [];
14
15 function slotToIndex(slot) {
16 if (slot >= 0) {
17 return slot * 2;
18 } else {
19 return slot * 2 + 1;
20 }
21 }
22
23 function indexToSlot(index) {
24 if ((index % 0) == 0) {
25 return index / 2;
26 } else {
27 return -((index - 1) / 2);
28 }
29 }
30
31 function positionToSlot(pos) {
32 return Math.floor(pos / NODE_INPUT_WIDTH);
33 }
34
35 function slotToLeftPosition(slot) {
36 return slot * NODE_INPUT_WIDTH
37 }
38
39 function slotToRightPosition(slot) {
40 return (slot + 1) * NODE_INPUT_WIDTH
41 }
42
43 function findSpace(pos, width, direction) {
44 var widthSlots = Math.floor((width + NODE_INPUT_WIDTH - 1) /
45 NODE_INPUT_WIDTH);
46 var currentSlot = positionToSlot(pos + width / 2);
47 var currentScanSlot = currentSlot;
48 var widthSlotsRemainingLeft = widthSlots;
49 var widthSlotsRemainingRight = widthSlots;
50 var slotsChecked = 0;
51 while (true) {
52 var mod = slotsChecked++ % 2;
53 currentScanSlot = currentSlot + (mod ? -1 : 1) * (slotsChecked >> 1);
54 if (!isSlotFilled[slotToIndex(currentScanSlot)]) {
55 if (mod) {
56 if (direction <= 0) --widthSlotsRemainingLeft
57 } else {
58 if (direction >= 0) --widthSlotsRemainingRight
59 }
60 if (widthSlotsRemainingLeft == 0 ||
61 widthSlotsRemainingRight == 0 ||
62 (widthSlotsRemainingLeft + widthSlotsRemainingRight) == widthSlots & &
63 (widthSlots == slotsChecked)) {
64 if (mod) {
65 return [currentScanSlot, widthSlots];
66 } else {
67 return [currentScanSlot - widthSlots + 1, widthSlots];
68 }
69 }
70 } else {
71 if (mod) {
72 widthSlotsRemainingLeft = widthSlots;
73 } else {
74 widthSlotsRemainingRight = widthSlots;
75 }
76 }
77 }
78 }
79
80 function setIndexRange(from, to, value) {
81 if (to < from) {
82 throw("illegal slot range");
83 }
84 while (from <= to) {
85 if (from > maxSlot) {
86 maxSlot = from;
87 }
88 if (from < minSlot) {
89 minSlot = from;
90 }
91 isSlotFilled[slotToIndex(from++)] = value;
92 }
93 }
94
95 function occupySlotRange(from, to) {
96 if (traceLayout) {
97 console.log("Occupied [" + slotToLeftPosition(from) + " " + slotToLeftPos ition(to + 1) + ")");
98 }
99 setIndexRange(from, to, true);
100 }
101
102 function clearSlotRange(from, to) {
103 if (traceLayout) {
104 console.log("Cleared [" + slotToLeftPosition(from) + " " + slotToLeftPosi tion(to + 1) + ")");
105 }
106 setIndexRange(from, to, false);
107 }
108
109 function occupyPositionRange(from, to) {
110 occupySlotRange(positionToSlot(from), positionToSlot(to - 1));
111 }
112
113 function clearPositionRange(from, to) {
114 clearSlotRange(positionToSlot(from), positionToSlot(to - 1));
115 }
116
117 function occupyPositionRangeWithMargin(from, to, margin) {
118 var fromMargin = from - Math.floor(margin);
119 var toMargin = to + Math.floor(margin);
120 occupyPositionRange(fromMargin, toMargin);
121 }
122
123 function clearPositionRangeWithMargin(from, to, margin) {
124 var fromMargin = from - Math.floor(margin);
125 var toMargin = to + Math.floor(margin);
126 clearPositionRange(fromMargin, toMargin);
127 }
128
129 var occupation = {
130 occupyNodeInputs: function(node) {
131 for (var i = 0; i < node.inputs.length; ++i) {
132 if (node.inputs[i].isVisible()) {
133 var edge = node.inputs[i];
134 if (!edge.isBackEdge()) {
135 var source = edge.source;
136 var horizontalPos = edge.getInputHorizontalPosition(graph);
137 if (traceLayout) {
138 console.log("Occupying input " + i + " of " + node.id + " at " + h orizontalPos);
139 }
140 occupyPositionRangeWithMargin(horizontalPos,
141 horizontalPos,
142 NODE_INPUT_WIDTH / 2);
143 }
144 }
145 }
146 },
147 occupyNode: function(node) {
148 var getPlacementHint = function(n) {
149 var pos = 0;
150 var direction = -1;
151 var outputEdges = 0;
152 var inputEdges = 0;
153 for (var k = 0; k < n.outputs.length; ++k) {
154 var outputEdge = n.outputs[k];
155 if (outputEdge.isVisible()) {
156 var output = n.outputs[k].target;
157 for (var l = 0; l < output.inputs.length; ++l) {
158 if (output.rank > n.rank) {
159 var inputEdge = output.inputs[l];
160 if (inputEdge.isVisible()) {
161 ++inputEdges;
162 }
163 if (output.inputs[l].source == n) {
164 pos += output.x + output.getInputX(l) + NODE_INPUT_WIDTH / 2;
165 outputEdges++;
166 if (l >= (output.inputs.length / 2)) {
167 direction = 1;
168 }
169 }
170 }
171 }
172 }
173 }
174 if (outputEdges != 0) {
175 pos = pos / outputEdges;
176 }
177 if (outputEdges > 1 || inputEdges == 1) {
178 direction = 0;
179 }
180 return [direction, pos];
181 }
182 var width = node.getTotalNodeWidth();
183 var margin = MINIMUM_EDGE_SEPARATION;
184 var paddedWidth = width + 2 * margin;
185 var placementHint = getPlacementHint(node);
186 var x = placementHint[1] - paddedWidth + margin;
187 if (traceLayout) {
188 console.log("Node " + node.id + " placement hint [" + x + ", " + (x + pa ddedWidth) + ")");
189 }
190 var placement = findSpace(x, paddedWidth, placementHint[0]);
191 var firstSlot = placement[0];
192 var slotWidth = placement[1];
193 var endSlotExclusive = firstSlot + slotWidth - 1;
194 occupySlotRange(firstSlot, endSlotExclusive);
195 nodeOccupation.push([firstSlot, endSlotExclusive]);
196 if (placementHint[0] < 0) {
197 return slotToLeftPosition(firstSlot + slotWidth) - width - margin;
198 } else if (placementHint[0] > 0) {
199 return slotToLeftPosition(firstSlot) + margin;
200 } else {
201 return slotToLeftPosition(firstSlot + slotWidth / 2) - (width / 2);
202 }
203 },
204 clearOccupiedNodes: function() {
205 nodeOccupation.forEach(function(o) {
206 clearSlotRange(o[0], o[1]);
207 });
208 nodeOccupation = [];
209 },
210 clearNodeOutputs: function(source) {
211 source.outputs.forEach(function(edge) {
212 if (edge.isVisible()) {
213 var target = edge.target;
214 for (var i = 0; i < target.inputs.length; ++i) {
215 if (target.inputs[i].source === source) {
216 var horizontalPos = edge.getInputHorizontalPosition(graph);
217 clearPositionRangeWithMargin(horizontalPos,
218 horizontalPos,
219 NODE_INPUT_WIDTH / 2);
220 }
221 }
222 }
223 });
224 },
225 print: function() {
226 var s = "";
227 for (var currentSlot = -40; currentSlot < 40; ++currentSlot) {
228 if (currentSlot != 0) {
229 s += " ";
230 } else {
231 s += "|";
232 }
233 }
234 console.log(s);
235 s = "";
236 for (var currentSlot2 = -40; currentSlot2 < 40; ++currentSlot2) {
237 if (isSlotFilled[slotToIndex(currentSlot2)]) {
238 s += "*";
239 } else {
240 s += " ";
241 }
242 }
243 console.log(s);
244 }
245 }
246 return occupation;
247 }
248
249 function layoutNodeGraph(graph) {
250 graph.minGraphX = 0;
251 graph.maxGraphNodeX = 1;
252 graph.maxGraphX = 1;
253 graph.minGraphY = 0;
254 graph.maxGraphY = 1;
255
256 // First determine the set of nodes that have no outputs. Those are the
257 // basis for bottom-up DFS to determine rank and node placement.
258 var endNodesHasNoOutputs = [];
259 var startNodesHasNoInputs = [];
260 graph.nodes.forEach(function(n, i){
261 endNodesHasNoOutputs[n.id] = true;
262 startNodesHasNoInputs[n.id] = true;
263 });
264 graph.edges.forEach(function(e, i){
265 endNodesHasNoOutputs[e.source.id] = false;
266 startNodesHasNoInputs[e.target.id] = false;
267 });
268
269 // Finialize the list of start and end nodes.
270 var endNodes = [];
271 var startNodes = [];
272 var visited = [];
273 var rank = [];
274 graph.nodes.forEach(function(n, i){
275 if (endNodesHasNoOutputs[n.id]) {
276 endNodes.push(n);
277 }
278 if (startNodesHasNoInputs[n.id]) {
279 startNodes.push(n);
280 }
281 visited[n.id] = false;
282 rank[n.id] = -1;
283 n.rank = 0;
284 n.visitOrderWithinRank = 0;
285 n.outputApproach = MINIMUM_NODE_OUTPUT_APPROACH;
286 });
287
288
289 var maxRank = 0;
290 var visited = [];
291 var dfsStack = [];
292 var visitOrderWithinRank = 0;
293
294 var worklist = startNodes.slice();
295 while (worklist.length != 0) {
296 var n = worklist.pop();
297 var changed = false;
298 if (n.rank == MAX_RANK_SENTINEL) {
299 n.rank = 1;
300 changed = true;
301 }
302 var begin = 0;
303 var end = n.inputs.length;
304 if (n.opcode == 'Phi' || n.opcode == 'EffectPhi') {
305 // Keep with merge or loop node
306 begin = n.inputs.length - 1;
307 } else if (n.hasBackEdges()) {
308 end = 1;
309 }
310 for (var l = begin; l < end; ++l) {
311 var input = n.inputs[l].source;
312 if (input.visible && input.rank >= n.rank) {
313 n.rank = input.rank + 1;
314 changed = true;
315 }
316 }
317 if (changed) {
318 var hasBackEdges = n.hasBackEdges();
319 for (var l = n.outputs.length - 1; l >= 0; --l) {
320 if (hasBackEdges && (l != 0)) {
321 worklist.unshift(n.outputs[l].target);
322 } else {
323 worklist.push(n.outputs[l].target);
324 }
325 }
326 }
327 if (n.rank > maxRank) {
328 maxRank = n.rank;
329 }
330 }
331
332 visited = [];
333 function dfsFindRankLate(n) {
334 if (visited[n.id]) return;
335 visited[n.id] = true;
336 var originalRank = n.rank;
337 var newRank = n.rank;
338 var firstInput = true;
339 for (var l = 0; l < n.outputs.length; ++l) {
340 var output = n.outputs[l].target;
341 dfsFindRankLate(output);
342 var outputRank = output.rank;
343 if (output.visible && (firstInput || outputRank <= newRank) &&
344 (outputRank > originalRank)) {
345 newRank = outputRank - 1;
346 }
347 firstInput = false;
348 }
349 if (n.opcode != "Start" && n.opcode != "Phi" && n.opcode != "EffectPhi") {
350 n.rank = newRank;
351 }
352 }
353
354 startNodes.forEach(dfsFindRankLate);
355
356 visited = [];
357 function dfsRankOrder(n) {
358 if (visited[n.id]) return;
359 visited[n.id] = true;
360 for (var l = 0; l < n.outputs.length; ++l) {
361 var edge = n.outputs[l];
362 if (edge.isVisible()) {
363 var output = edge.target;
364 dfsRankOrder(output);
365 }
366 }
367 if (n.visitOrderWithinRank == 0) {
368 n.visitOrderWithinRank = ++visitOrderWithinRank;
369 }
370 }
371 startNodes.forEach(dfsRankOrder);
372
373 endNodes.forEach(function(n) {
374 n.rank = maxRank + 1;
375 });
376
377 var rankSets = [];
378 // Collect sets for each rank.
379 graph.nodes.forEach(function(n, i){
380 n.y = n.rank * (DEFAULT_NODE_ROW_SEPARATION + graph.getNodeHeight() +
381 2 * DEFAULT_NODE_BUBBLE_RADIUS);
382 if (n.visible) {
383 if (rankSets[n.rank] === undefined) {
384 rankSets[n.rank] = [n];
385 } else {
386 rankSets[n.rank].push(n);
387 }
388 }
389 });
390
391 // Iterate backwards from highest to lowest rank, placing nodes so that they
392 // spread out from the "center" as much as possible while still being
393 // compact and not overlapping live input lines.
394 var occupation = newGraphOccupation(graph);
395 var rankCount = 0;
396
397 rankSets.reverse().forEach(function(rankSet) {
398
399 for (var i = 0; i < rankSet.length; ++i) {
400 occupation.clearNodeOutputs(rankSet[i]);
401 }
402
403 if (traceLayout) {
404 console.log("After clearing outputs");
405 occupation.print();
406 }
407
408 var placedCount = 0;
409 rankSet = rankSet.sort(function(a,b) {
410 return a.visitOrderWithinRank < b.visitOrderWithinRank;
411 });
412 for (var i = 0; i < rankSet.length; ++i) {
413 var nodeToPlace = rankSet[i];
414 if (nodeToPlace.visible) {
415 nodeToPlace.x = occupation.occupyNode(nodeToPlace);
416 if (traceLayout) {
417 console.log("Node " + nodeToPlace.id + " is placed between [" + nodeTo Place.x + ", " + (nodeToPlace.x + nodeToPlace.getTotalNodeWidth()) + ")");
418 }
419 var staggeredFlooredI = Math.floor(placedCount++ % 3);
420 var delta = MINIMUM_EDGE_SEPARATION * staggeredFlooredI
421 nodeToPlace.outputApproach += delta;
422 } else {
423 nodeToPlace.x = 0;
424 }
425
426 if (nodeToPlace.x < graph.minGraphX) {
427 graph.minGraphX = nodeToPlace.x;
428 }
429 if ((nodeToPlace.y - 50) < graph.minGraphY) {
430 graph.minGraphY = nodeToPlace.y - 50;
431 }
432 if ((nodeToPlace.x + nodeToPlace.getTotalNodeWidth()) > graph.maxGraphNode X) {
433 graph.maxGraphNodeX = nodeToPlace.x + nodeToPlace.getTotalNodeWidth();
434 }
435 if ((nodeToPlace.y + graph.getNodeHeight() + 50) > graph.maxGraphY) {
436 graph.maxGraphY = nodeToPlace.y + graph.getNodeHeight() + 50;
437 }
438 }
439
440 if (traceLayout) {
441 console.log("Before clearing nodes");
442 occupation.print();
443 }
444
445 occupation.clearOccupiedNodes();
446
447 if (traceLayout) {
448 console.log("After clearing nodes");
449 occupation.print();
450 }
451
452 for (var i = 0; i < rankSet.length; ++i) {
453 var node = rankSet[i];
454 occupation.occupyNodeInputs(node);
455 }
456
457 if (traceLayout) {
458 console.log("After occupying inputs");
459 occupation.print();
460 }
461 });
462
463 var backEdgeNumber = 0;
464 graph.visibleEdges.each(function (e) {
465 if (e.isBackEdge()) {
466 e.backEdgeNumber = ++backEdgeNumber;
467 } else {
468 e.backEdgeNumber = 0;
469 }
470 });
471
472 graph.maxGraphX = graph.maxGraphNodeX +
473 backEdgeNumber * MINIMUM_EDGE_SEPARATION;
474 }
OLDNEW
« no previous file with comments | « tools/turbolizer/expand-all.jpg ('k') | tools/turbolizer/graph-view.js » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698