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
5var DEFAULT_NODE_ROW_SEPARATION = 130
6
7var traceLayout = false;
8
9function 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) + "  " + slotToLeftPosition(to + 1) + ")");
98    }
99    setIndexRange(from, to, true);
100  }
101
102  function clearSlotRange(from, to) {
103    if (traceLayout) {
104      console.log("Cleared [" + slotToLeftPosition(from) + "  " + slotToLeftPosition(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 " + horizontalPos);
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 + paddedWidth) + ")");
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
249function layoutNodeGraph(graph) {
250  // First determine the set of nodes that have no outputs. Those are the
251  // basis for bottom-up DFS to determine rank and node placement.
252  var endNodesHasNoOutputs = [];
253  var startNodesHasNoInputs = [];
254  graph.nodes.forEach(function(n, i){
255    endNodesHasNoOutputs[n.id] = true;
256    startNodesHasNoInputs[n.id] = true;
257  });
258  graph.edges.forEach(function(e, i){
259    endNodesHasNoOutputs[e.source.id] = false;
260    startNodesHasNoInputs[e.target.id] = false;
261  });
262
263  // Finialize the list of start and end nodes.
264  var endNodes = [];
265  var startNodes = [];
266  var visited = [];
267  var rank = [];
268  graph.nodes.forEach(function(n, i){
269    if (endNodesHasNoOutputs[n.id]) {
270      endNodes.push(n);
271    }
272    if (startNodesHasNoInputs[n.id]) {
273      startNodes.push(n);
274    }
275    visited[n.id] = false;
276    rank[n.id] = -1;
277    n.rank = 0;
278    n.visitOrderWithinRank = 0;
279    n.outputApproach = MINIMUM_NODE_OUTPUT_APPROACH;
280  });
281
282
283  var maxRank = 0;
284  var visited = [];
285  var dfsStack = [];
286  var visitOrderWithinRank = 0;
287
288  var worklist = startNodes.slice();
289  while (worklist.length != 0) {
290    var n = worklist.pop();
291    var changed = false;
292    if (n.rank == MAX_RANK_SENTINEL) {
293      n.rank = 1;
294      changed = true;
295    }
296    var begin = 0;
297    var end = n.inputs.length;
298    if (n.opcode == 'Phi' || n.opcode == 'EffectPhi') {
299      // Keep with merge or loop node
300      begin = n.inputs.length - 1;
301    } else if (n.hasBackEdges()) {
302      end = 1;
303    }
304    for (var l = begin; l < end; ++l) {
305      var input = n.inputs[l].source;
306      if (input.visible && input.rank >= n.rank) {
307        n.rank = input.rank + 1;
308        changed = true;
309      }
310    }
311    if (changed) {
312      var hasBackEdges = n.hasBackEdges();
313      for (var l = n.outputs.length - 1; l >= 0; --l) {
314        if (hasBackEdges && (l != 0)) {
315          worklist.unshift(n.outputs[l].target);
316        } else {
317          worklist.push(n.outputs[l].target);
318        }
319      }
320    }
321    if (n.rank > maxRank) {
322      maxRank = n.rank;
323    }
324  }
325
326   visited = [];
327  function dfsFindRankLate(n) {
328    if (visited[n.id]) return;
329    visited[n.id] = true;
330    var originalRank = n.rank;
331    var newRank = n.rank;
332    var firstInput = true;
333    for (var l = 0; l < n.outputs.length; ++l) {
334      var output = n.outputs[l].target;
335      dfsFindRankLate(output);
336      var outputRank = output.rank;
337      if (output.visible && (firstInput || outputRank <= newRank) &&
338          (outputRank > originalRank)) {
339        newRank = outputRank - 1;
340      }
341      firstInput = false;
342    }
343    if (n.opcode != "Start" && n.opcode != "Phi" && n.opcode != "EffectPhi") {
344      n.rank = newRank;
345    }
346  }
347
348  startNodes.forEach(dfsFindRankLate);
349
350  visited = [];
351  function dfsRankOrder(n) {
352    if (visited[n.id]) return;
353    visited[n.id] = true;
354    for (var l = 0; l < n.outputs.length; ++l) {
355      var edge = n.outputs[l];
356      if (edge.isVisible()) {
357        var output = edge.target;
358        dfsRankOrder(output);
359      }
360    }
361    if (n.visitOrderWithinRank == 0) {
362      n.visitOrderWithinRank = ++visitOrderWithinRank;
363    }
364  }
365  startNodes.forEach(dfsRankOrder);
366
367  endNodes.forEach(function(n) {
368    n.rank = maxRank + 1;
369  });
370
371  var rankSets = [];
372  // Collect sets for each rank.
373  graph.nodes.forEach(function(n, i){
374    n.y = n.rank * (DEFAULT_NODE_ROW_SEPARATION + graph.getNodeHeight(n) +
375                    2 * DEFAULT_NODE_BUBBLE_RADIUS);
376    if (n.visible) {
377      if (rankSets[n.rank] === undefined) {
378        rankSets[n.rank] = [n];
379      } else {
380        rankSets[n.rank].push(n);
381      }
382    }
383  });
384
385  // Iterate backwards from highest to lowest rank, placing nodes so that they
386  // spread out from the "center" as much as possible while still being
387  // compact and not overlapping live input lines.
388  var occupation = newGraphOccupation(graph);
389  var rankCount = 0;
390
391  rankSets.reverse().forEach(function(rankSet) {
392
393    for (var i = 0; i < rankSet.length; ++i) {
394      occupation.clearNodeOutputs(rankSet[i]);
395    }
396
397    if (traceLayout) {
398      console.log("After clearing outputs");
399      occupation.print();
400    }
401
402    var placedCount = 0;
403    rankSet = rankSet.sort(function(a,b) {
404      return a.visitOrderWithinRank < b.visitOrderWithinRank;
405    });
406    for (var i = 0; i < rankSet.length; ++i) {
407      var nodeToPlace = rankSet[i];
408      if (nodeToPlace.visible) {
409        nodeToPlace.x = occupation.occupyNode(nodeToPlace);
410        if (traceLayout) {
411          console.log("Node " + nodeToPlace.id + " is placed between [" + nodeToPlace.x + ", " + (nodeToPlace.x + nodeToPlace.getTotalNodeWidth()) + ")");
412        }
413        var staggeredFlooredI = Math.floor(placedCount++ % 3);
414        var delta = MINIMUM_EDGE_SEPARATION * staggeredFlooredI
415        nodeToPlace.outputApproach += delta;
416      } else {
417        nodeToPlace.x = 0;
418      }
419    }
420
421    if (traceLayout) {
422      console.log("Before clearing nodes");
423      occupation.print();
424    }
425
426    occupation.clearOccupiedNodes();
427
428    if (traceLayout) {
429      console.log("After clearing nodes");
430      occupation.print();
431    }
432
433    for (var i = 0; i < rankSet.length; ++i) {
434      var node = rankSet[i];
435      occupation.occupyNodeInputs(node);
436    }
437
438    if (traceLayout) {
439      console.log("After occupying inputs");
440      occupation.print();
441    }
442
443    if (traceLayout) {
444      console.log("After determining bounding box");
445      occupation.print();
446    }
447  });
448
449  graph.maxBackEdgeNumber = 0;
450  graph.visibleEdges.each(function (e) {
451    if (e.isBackEdge()) {
452      e.backEdgeNumber = ++graph.maxBackEdgeNumber;
453    } else {
454      e.backEdgeNumber = 0;
455    }
456  });
457
458  redetermineGraphBoundingBox(graph);
459
460}
461
462function redetermineGraphBoundingBox(graph) {
463  graph.minGraphX = 0;
464  graph.maxGraphNodeX = 1;
465  graph.maxGraphX = undefined;  // see below
466  graph.minGraphY = 0;
467  graph.maxGraphY = 1;
468
469  for (var i = 0; i < graph.nodes.length; ++i) {
470    var node = graph.nodes[i];
471
472    if (!node.visible) {
473      continue;
474    }
475
476    if (node.x < graph.minGraphX) {
477      graph.minGraphX = node.x;
478    }
479    if ((node.x + node.getTotalNodeWidth()) > graph.maxGraphNodeX) {
480      graph.maxGraphNodeX = node.x + node.getTotalNodeWidth();
481    }
482    if ((node.y - 50) < graph.minGraphY) {
483      graph.minGraphY = node.y - 50;
484    }
485    if ((node.y + graph.getNodeHeight(node) + 50) > graph.maxGraphY) {
486      graph.maxGraphY = node.y + graph.getNodeHeight(node) + 50;
487    }
488  }
489
490  graph.maxGraphX = graph.maxGraphNodeX +
491    graph.maxBackEdgeNumber * MINIMUM_EDGE_SEPARATION;
492
493}
494