Merge V8 5.3.332.45. DO NOT MERGE
Test: Manual
FPIIM-449
Change-Id: Id3254828b068abdea3cb10442e0172a8c9a98e03
(cherry picked from commit 13e2dadd00298019ed862f2b2fc5068bba730bcf)
diff --git a/tools/turbolizer/graph-layout.js b/tools/turbolizer/graph-layout.js
new file mode 100644
index 0000000..8e411b7
--- /dev/null
+++ b/tools/turbolizer/graph-layout.js
@@ -0,0 +1,474 @@
+// 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.
+
+var 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;
+}
+
+function layoutNodeGraph(graph) {
+ graph.minGraphX = 0;
+ graph.maxGraphNodeX = 1;
+ graph.maxGraphX = 1;
+ graph.minGraphY = 0;
+ graph.maxGraphY = 1;
+
+ // 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() +
+ 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 (nodeToPlace.x < graph.minGraphX) {
+ graph.minGraphX = nodeToPlace.x;
+ }
+ if ((nodeToPlace.y - 50) < graph.minGraphY) {
+ graph.minGraphY = nodeToPlace.y - 50;
+ }
+ if ((nodeToPlace.x + nodeToPlace.getTotalNodeWidth()) > graph.maxGraphNodeX) {
+ graph.maxGraphNodeX = nodeToPlace.x + nodeToPlace.getTotalNodeWidth();
+ }
+ if ((nodeToPlace.y + graph.getNodeHeight() + 50) > graph.maxGraphY) {
+ graph.maxGraphY = nodeToPlace.y + graph.getNodeHeight() + 50;
+ }
+ }
+
+ 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();
+ }
+ });
+
+ var backEdgeNumber = 0;
+ graph.visibleEdges.each(function (e) {
+ if (e.isBackEdge()) {
+ e.backEdgeNumber = ++backEdgeNumber;
+ } else {
+ e.backEdgeNumber = 0;
+ }
+ });
+
+ graph.maxGraphX = graph.maxGraphNodeX +
+ backEdgeNumber * MINIMUM_EDGE_SEPARATION;
+}