diff options
Diffstat (limited to 'deps/v8/tools/turbolizer/src/graph-layout.ts')
| -rw-r--r-- | deps/v8/tools/turbolizer/src/graph-layout.ts | 509 |
1 files changed, 509 insertions, 0 deletions
diff --git a/deps/v8/tools/turbolizer/src/graph-layout.ts b/deps/v8/tools/turbolizer/src/graph-layout.ts new file mode 100644 index 0000000000..302a98aacc --- /dev/null +++ b/deps/v8/tools/turbolizer/src/graph-layout.ts @@ -0,0 +1,509 @@ +// Copyright 2015 the V8 project authors. All rights reserved. +// Use of this source code is governed by a BSD-style license that can be +// found in the LICENSE file. + + +import {MAX_RANK_SENTINEL} from "./constants.js" +import {MINIMUM_EDGE_SEPARATION} from "./edge.js" +import {NODE_INPUT_WIDTH, MINIMUM_NODE_OUTPUT_APPROACH, DEFAULT_NODE_BUBBLE_RADIUS} from "./node.js" + + +const DEFAULT_NODE_ROW_SEPARATION = 130 + +var traceLayout = false; + +function newGraphOccupation(graph) { + var isSlotFilled = []; + var maxSlot = 0; + var minSlot = 0; + var nodeOccupation = []; + + function slotToIndex(slot) { + if (slot >= 0) { + return slot * 2; + } else { + return slot * 2 + 1; + } + } + + function indexToSlot(index) { + if ((index % 0) == 0) { + return index / 2; + } else { + return -((index - 1) / 2); + } + } + + function positionToSlot(pos) { + return Math.floor(pos / NODE_INPUT_WIDTH); + } + + function slotToLeftPosition(slot) { + return slot * NODE_INPUT_WIDTH + } + + function slotToRightPosition(slot) { + return (slot + 1) * NODE_INPUT_WIDTH + } + + function findSpace(pos, width, direction) { + var widthSlots = Math.floor((width + NODE_INPUT_WIDTH - 1) / + NODE_INPUT_WIDTH); + var currentSlot = positionToSlot(pos + width / 2); + var currentScanSlot = currentSlot; + var widthSlotsRemainingLeft = widthSlots; + var widthSlotsRemainingRight = widthSlots; + var slotsChecked = 0; + while (true) { + var mod = slotsChecked++ % 2; + currentScanSlot = currentSlot + (mod ? -1 : 1) * (slotsChecked >> 1); + if (!isSlotFilled[slotToIndex(currentScanSlot)]) { + if (mod) { + if (direction <= 0)--widthSlotsRemainingLeft + } else { + if (direction >= 0)--widthSlotsRemainingRight + } + if (widthSlotsRemainingLeft == 0 || + widthSlotsRemainingRight == 0 || + (widthSlotsRemainingLeft + widthSlotsRemainingRight) == widthSlots && + (widthSlots == slotsChecked)) { + if (mod) { + return [currentScanSlot, widthSlots]; + } else { + return [currentScanSlot - widthSlots + 1, widthSlots]; + } + } + } else { + if (mod) { + widthSlotsRemainingLeft = widthSlots; + } else { + widthSlotsRemainingRight = widthSlots; + } + } + } + } + + function setIndexRange(from, to, value) { + if (to < from) { + throw ("illegal slot range"); + } + while (from <= to) { + if (from > maxSlot) { + maxSlot = from; + } + if (from < minSlot) { + minSlot = from; + } + isSlotFilled[slotToIndex(from++)] = value; + } + } + + function occupySlotRange(from, to) { + if (traceLayout) { + console.log("Occupied [" + slotToLeftPosition(from) + " " + slotToLeftPosition(to + 1) + ")"); + } + setIndexRange(from, to, true); + } + + function clearSlotRange(from, to) { + if (traceLayout) { + console.log("Cleared [" + slotToLeftPosition(from) + " " + slotToLeftPosition(to + 1) + ")"); + } + setIndexRange(from, to, false); + } + + function occupyPositionRange(from, to) { + occupySlotRange(positionToSlot(from), positionToSlot(to - 1)); + } + + function clearPositionRange(from, to) { + clearSlotRange(positionToSlot(from), positionToSlot(to - 1)); + } + + function occupyPositionRangeWithMargin(from, to, margin) { + var fromMargin = from - Math.floor(margin); + var toMargin = to + Math.floor(margin); + occupyPositionRange(fromMargin, toMargin); + } + + function clearPositionRangeWithMargin(from, to, margin) { + var fromMargin = from - Math.floor(margin); + var toMargin = to + Math.floor(margin); + clearPositionRange(fromMargin, toMargin); + } + + var occupation = { + occupyNodeInputs: function (node) { + for (var i = 0; i < node.inputs.length; ++i) { + if (node.inputs[i].isVisible()) { + var edge = node.inputs[i]; + if (!edge.isBackEdge()) { + var source = edge.source; + var horizontalPos = edge.getInputHorizontalPosition(graph); + if (traceLayout) { + console.log("Occupying input " + i + " of " + node.id + " at " + horizontalPos); + } + occupyPositionRangeWithMargin(horizontalPos, + horizontalPos, + NODE_INPUT_WIDTH / 2); + } + } + } + }, + occupyNode: function (node) { + var getPlacementHint = function (n) { + var pos = 0; + var direction = -1; + var outputEdges = 0; + var inputEdges = 0; + for (var k = 0; k < n.outputs.length; ++k) { + var outputEdge = n.outputs[k]; + if (outputEdge.isVisible()) { + var output = n.outputs[k].target; + for (var l = 0; l < output.inputs.length; ++l) { + if (output.rank > n.rank) { + var inputEdge = output.inputs[l]; + if (inputEdge.isVisible()) { + ++inputEdges; + } + if (output.inputs[l].source == n) { + pos += output.x + output.getInputX(l) + NODE_INPUT_WIDTH / 2; + outputEdges++; + if (l >= (output.inputs.length / 2)) { + direction = 1; + } + } + } + } + } + } + if (outputEdges != 0) { + pos = pos / outputEdges; + } + if (outputEdges > 1 || inputEdges == 1) { + direction = 0; + } + return [direction, pos]; + } + var width = node.getTotalNodeWidth(); + var margin = MINIMUM_EDGE_SEPARATION; + var paddedWidth = width + 2 * margin; + var placementHint = getPlacementHint(node); + var x = placementHint[1] - paddedWidth + margin; + if (traceLayout) { + console.log("Node " + node.id + " placement hint [" + x + ", " + (x + paddedWidth) + ")"); + } + var placement = findSpace(x, paddedWidth, placementHint[0]); + var firstSlot = placement[0]; + var slotWidth = placement[1]; + var endSlotExclusive = firstSlot + slotWidth - 1; + occupySlotRange(firstSlot, endSlotExclusive); + nodeOccupation.push([firstSlot, endSlotExclusive]); + if (placementHint[0] < 0) { + return slotToLeftPosition(firstSlot + slotWidth) - width - margin; + } else if (placementHint[0] > 0) { + return slotToLeftPosition(firstSlot) + margin; + } else { + return slotToLeftPosition(firstSlot + slotWidth / 2) - (width / 2); + } + }, + clearOccupiedNodes: function () { + nodeOccupation.forEach(function (o) { + clearSlotRange(o[0], o[1]); + }); + nodeOccupation = []; + }, + clearNodeOutputs: function (source) { + source.outputs.forEach(function (edge) { + if (edge.isVisible()) { + var target = edge.target; + for (var i = 0; i < target.inputs.length; ++i) { + if (target.inputs[i].source === source) { + var horizontalPos = edge.getInputHorizontalPosition(graph); + clearPositionRangeWithMargin(horizontalPos, + horizontalPos, + NODE_INPUT_WIDTH / 2); + } + } + } + }); + }, + print: function () { + var s = ""; + for (var currentSlot = -40; currentSlot < 40; ++currentSlot) { + if (currentSlot != 0) { + s += " "; + } else { + s += "|"; + } + } + console.log(s); + s = ""; + for (var currentSlot2 = -40; currentSlot2 < 40; ++currentSlot2) { + if (isSlotFilled[slotToIndex(currentSlot2)]) { + s += "*"; + } else { + s += " "; + } + } + console.log(s); + } + } + return occupation; +} + +export function layoutNodeGraph(graph) { + // First determine the set of nodes that have no outputs. Those are the + // basis for bottom-up DFS to determine rank and node placement. + var endNodesHasNoOutputs = []; + var startNodesHasNoInputs = []; + graph.nodes.forEach(function (n, i) { + endNodesHasNoOutputs[n.id] = true; + startNodesHasNoInputs[n.id] = true; + }); + graph.edges.forEach(function (e, i) { + endNodesHasNoOutputs[e.source.id] = false; + startNodesHasNoInputs[e.target.id] = false; + }); + + // Finialize the list of start and end nodes. + var endNodes = []; + var startNodes = []; + var visited = []; + var rank = []; + graph.nodes.forEach(function (n, i) { + if (endNodesHasNoOutputs[n.id]) { + endNodes.push(n); + } + if (startNodesHasNoInputs[n.id]) { + startNodes.push(n); + } + visited[n.id] = false; + rank[n.id] = -1; + n.rank = 0; + n.visitOrderWithinRank = 0; + n.outputApproach = MINIMUM_NODE_OUTPUT_APPROACH; + }); + + + var maxRank = 0; + var visited = []; + var dfsStack = []; + var visitOrderWithinRank = 0; + + var worklist = startNodes.slice(); + while (worklist.length != 0) { + var n = worklist.pop(); + var changed = false; + if (n.rank == MAX_RANK_SENTINEL) { + n.rank = 1; + changed = true; + } + var begin = 0; + var end = n.inputs.length; + if (n.opcode == 'Phi' || n.opcode == 'EffectPhi') { + // Keep with merge or loop node + begin = n.inputs.length - 1; + } else if (n.hasBackEdges()) { + end = 1; + } + for (var l = begin; l < end; ++l) { + var input = n.inputs[l].source; + if (input.visible && input.rank >= n.rank) { + n.rank = input.rank + 1; + changed = true; + } + } + if (changed) { + var hasBackEdges = n.hasBackEdges(); + for (var l = n.outputs.length - 1; l >= 0; --l) { + if (hasBackEdges && (l != 0)) { + worklist.unshift(n.outputs[l].target); + } else { + worklist.push(n.outputs[l].target); + } + } + } + if (n.rank > maxRank) { + maxRank = n.rank; + } + } + + visited = []; + function dfsFindRankLate(n) { + if (visited[n.id]) return; + visited[n.id] = true; + var originalRank = n.rank; + var newRank = n.rank; + var firstInput = true; + for (var l = 0; l < n.outputs.length; ++l) { + var output = n.outputs[l].target; + dfsFindRankLate(output); + var outputRank = output.rank; + if (output.visible && (firstInput || outputRank <= newRank) && + (outputRank > originalRank)) { + newRank = outputRank - 1; + } + firstInput = false; + } + if (n.opcode != "Start" && n.opcode != "Phi" && n.opcode != "EffectPhi") { + n.rank = newRank; + } + } + + startNodes.forEach(dfsFindRankLate); + + visited = []; + function dfsRankOrder(n) { + if (visited[n.id]) return; + visited[n.id] = true; + for (var l = 0; l < n.outputs.length; ++l) { + var edge = n.outputs[l]; + if (edge.isVisible()) { + var output = edge.target; + dfsRankOrder(output); + } + } + if (n.visitOrderWithinRank == 0) { + n.visitOrderWithinRank = ++visitOrderWithinRank; + } + } + startNodes.forEach(dfsRankOrder); + + endNodes.forEach(function (n) { + n.rank = maxRank + 1; + }); + + var rankSets = []; + // Collect sets for each rank. + graph.nodes.forEach(function (n, i) { + n.y = n.rank * (DEFAULT_NODE_ROW_SEPARATION + graph.getNodeHeight(n) + + 2 * DEFAULT_NODE_BUBBLE_RADIUS); + if (n.visible) { + if (rankSets[n.rank] === undefined) { + rankSets[n.rank] = [n]; + } else { + rankSets[n.rank].push(n); + } + } + }); + + // Iterate backwards from highest to lowest rank, placing nodes so that they + // spread out from the "center" as much as possible while still being + // compact and not overlapping live input lines. + var occupation = newGraphOccupation(graph); + var rankCount = 0; + + rankSets.reverse().forEach(function (rankSet) { + + for (var i = 0; i < rankSet.length; ++i) { + occupation.clearNodeOutputs(rankSet[i]); + } + + if (traceLayout) { + console.log("After clearing outputs"); + occupation.print(); + } + + var placedCount = 0; + rankSet = rankSet.sort(function (a, b) { + return a.visitOrderWithinRank < b.visitOrderWithinRank; + }); + for (var i = 0; i < rankSet.length; ++i) { + var nodeToPlace = rankSet[i]; + if (nodeToPlace.visible) { + nodeToPlace.x = occupation.occupyNode(nodeToPlace); + if (traceLayout) { + console.log("Node " + nodeToPlace.id + " is placed between [" + nodeToPlace.x + ", " + (nodeToPlace.x + nodeToPlace.getTotalNodeWidth()) + ")"); + } + var staggeredFlooredI = Math.floor(placedCount++ % 3); + var delta = MINIMUM_EDGE_SEPARATION * staggeredFlooredI + nodeToPlace.outputApproach += delta; + } else { + nodeToPlace.x = 0; + } + } + + if (traceLayout) { + console.log("Before clearing nodes"); + occupation.print(); + } + + occupation.clearOccupiedNodes(); + + if (traceLayout) { + console.log("After clearing nodes"); + occupation.print(); + } + + for (var i = 0; i < rankSet.length; ++i) { + var node = rankSet[i]; + occupation.occupyNodeInputs(node); + } + + if (traceLayout) { + console.log("After occupying inputs"); + occupation.print(); + } + + if (traceLayout) { + console.log("After determining bounding box"); + occupation.print(); + } + }); + + graph.maxBackEdgeNumber = 0; + graph.visibleEdges.selectAll("path").each(function (e) { + if (e.isBackEdge()) { + e.backEdgeNumber = ++graph.maxBackEdgeNumber; + } else { + e.backEdgeNumber = 0; + } + }); + + redetermineGraphBoundingBox(graph); +} + +function redetermineGraphBoundingBox(graph) { + graph.minGraphX = 0; + graph.maxGraphNodeX = 1; + graph.maxGraphX = undefined; // see below + graph.minGraphY = 0; + graph.maxGraphY = 1; + + for (var i = 0; i < graph.nodes.length; ++i) { + var node = graph.nodes[i]; + + if (!node.visible) { + continue; + } + + if (node.x < graph.minGraphX) { + graph.minGraphX = node.x; + } + if ((node.x + node.getTotalNodeWidth()) > graph.maxGraphNodeX) { + graph.maxGraphNodeX = node.x + node.getTotalNodeWidth(); + } + if ((node.y - 50) < graph.minGraphY) { + graph.minGraphY = node.y - 50; + } + if ((node.y + graph.getNodeHeight(node) + 50) > graph.maxGraphY) { + graph.maxGraphY = node.y + graph.getNodeHeight(node) + 50; + } + } + + graph.maxGraphX = graph.maxGraphNodeX + + graph.maxBackEdgeNumber * MINIMUM_EDGE_SEPARATION; + + const width = (graph.maxGraphX - graph.minGraphX); + const height = graph.maxGraphY - graph.minGraphY; + graph.width = width; + graph.height = height; + + const extent = [ + [graph.minGraphX - width / 2, graph.minGraphY - height / 2], + [graph.maxGraphX + width / 2, graph.maxGraphY + height / 2] + ]; + graph.panZoom.translateExtent(extent); + graph.minScale(); +} |