Mercurial > hg > truffle
changeset 4389:6ffa3413096e
Improved layout algorithm to put an emphasis on CFG edges.
line wrap: on
line diff
--- a/graal/com.oracle.max.graal.printer/src/com/oracle/max/graal/printer/IdealGraphPrinterDumpHandler.java Sat Jan 28 00:44:26 2012 +0100 +++ b/graal/com.oracle.max.graal.printer/src/com/oracle/max/graal/printer/IdealGraphPrinterDumpHandler.java Sat Jan 28 15:48:40 2012 +0100 @@ -45,6 +45,7 @@ private String fileName; private String host; private int port; + private boolean initialized; /** * Creates a new {@link IdealGraphPrinterDumpHandler} that writes output to a file named after the compiled method. @@ -64,12 +65,15 @@ private void ensureInitialized() { - if (fileName != null) { - initializeFilePrinter(); - } else { - initializeNetworkPrinter(); + if (!initialized) { + initialized = true; + if (fileName != null) { + initializeFilePrinter(); + } else { + initializeNetworkPrinter(); + } + printer.begin(); } - printer.begin(); } private void initializeFilePrinter() {
--- a/src/share/tools/IdealGraphVisualizer/ControlFlow/src/com/sun/hotspot/igv/controlflow/BlockConnectionWidget.java Sat Jan 28 00:44:26 2012 +0100 +++ b/src/share/tools/IdealGraphVisualizer/ControlFlow/src/com/sun/hotspot/igv/controlflow/BlockConnectionWidget.java Sat Jan 28 15:48:40 2012 +0100 @@ -116,4 +116,9 @@ public String toString() { return "Connection[ " + from.toString() + " - " + to.toString() + "]"; } + + @Override + public boolean isVIP() { + return false; + } }
--- a/src/share/tools/IdealGraphVisualizer/ControlFlow/src/com/sun/hotspot/igv/controlflow/HierarchicalGraphLayout.java Sat Jan 28 00:44:26 2012 +0100 +++ b/src/share/tools/IdealGraphVisualizer/ControlFlow/src/com/sun/hotspot/igv/controlflow/HierarchicalGraphLayout.java Sat Jan 28 15:48:40 2012 +0100 @@ -80,6 +80,11 @@ public void setControlPoints(List<Point> list) { // Do nothing for now } + + @Override + public boolean isVIP() { + return false; + } } private class VertexWrapper implements Vertex {
--- a/src/share/tools/IdealGraphVisualizer/Graal/src/com/sun/hotspot/igv/graal/filters/GraalEdgeColorFilter.java Sat Jan 28 00:44:26 2012 +0100 +++ b/src/share/tools/IdealGraphVisualizer/Graal/src/com/sun/hotspot/igv/graal/filters/GraalEdgeColorFilter.java Sat Jan 28 15:48:40 2012 +0100 @@ -26,6 +26,7 @@ import com.sun.hotspot.igv.data.Properties; import com.sun.hotspot.igv.filter.AbstractFilter; import com.sun.hotspot.igv.graph.Connection; +import com.sun.hotspot.igv.graph.Connection.ConnectionStyle; import com.sun.hotspot.igv.graph.Diagram; import com.sun.hotspot.igv.graph.Figure; import com.sun.hotspot.igv.graph.InputSlot; @@ -64,8 +65,10 @@ } for (InputSlot is : f.getInputSlots()) { Color color; + ConnectionStyle style = ConnectionStyle.NORMAL; if (is.getPosition() < predCount) { color = successorColor; + style = ConnectionStyle.BOLD; } else { color = usageColor; } @@ -74,9 +77,11 @@ for (Connection c : is.getConnections()) { if (c.getLabel() == null || !c.getLabel().endsWith("#NDF")) { c.setColor(color); + c.setStyle(style); } else if ("EndNode".equals(c.getOutputSlot().getFigure().getProperties().get("class")) || "EndNode".equals(c.getOutputSlot().getProperties().get("class"))) { c.setColor(successorColor); + c.setStyle(ConnectionStyle.BOLD); } } }
--- a/src/share/tools/IdealGraphVisualizer/Graph/src/com/sun/hotspot/igv/graph/Connection.java Sat Jan 28 00:44:26 2012 +0100 +++ b/src/share/tools/IdealGraphVisualizer/Graph/src/com/sun/hotspot/igv/graph/Connection.java Sat Jan 28 15:48:40 2012 +0100 @@ -37,6 +37,11 @@ */ public class Connection implements Source.Provider, Link { + @Override + public boolean isVIP() { + return style == ConnectionStyle.BOLD; + } + public enum ConnectionStyle { NORMAL,
--- a/src/share/tools/IdealGraphVisualizer/HierarchicalLayout/src/com/sun/hotspot/igv/hierarchicallayout/HierarchicalLayoutManager.java Sat Jan 28 00:44:26 2012 +0100 +++ b/src/share/tools/IdealGraphVisualizer/HierarchicalLayout/src/com/sun/hotspot/igv/hierarchicallayout/HierarchicalLayoutManager.java Sat Jan 28 15:48:40 2012 +0100 @@ -59,6 +59,7 @@ public static final int LAYER_OFFSET = 30; public static final int MAX_LAYER_LENGTH = -1; public static final int MIN_LAYER_DIFFERENCE = 1; + public static final int VIP_BONUS = 10; public enum Combine { @@ -124,6 +125,7 @@ public int relativeFrom; public int relativeTo; public Link link; + public boolean vip; } private abstract class AlgorithmPart { @@ -249,8 +251,7 @@ // ############################################################# // STEP 7: Assign X coordinates - //new AssignXCoordinates().start(); - new AssignXCoordinates2().start(); + new AssignXCoordinates().start(); // ############################################################# // STEP 6: Assign Y coordinates @@ -568,7 +569,7 @@ } }; - private class AssignXCoordinates2 extends AlgorithmPart { + private class AssignXCoordinates extends AlgorithmPart { private ArrayList<Integer>[] space; private ArrayList<LayoutNode>[] downProcessingOrder; @@ -613,10 +614,11 @@ sweepDown(); sweepUp(); } - - for (int i = 0; i < SWEEP_ITERATIONS; i++) { - doubleSweep(); - } + + sweepDown(); + //for (int i = 0; i < SWEEP_ITERATIONS; i++) { + // doubleSweep(); + //} } private int calculateOptimalDown(LayoutNode n) { @@ -628,6 +630,9 @@ for (int i = 0; i < size; i++) { LayoutEdge e = n.preds.get(i); values[i] = e.from.x + e.relativeFrom - e.relativeTo; + if (e.vip) { + return values[i]; + } } return median(values); } @@ -658,11 +663,15 @@ if (size == 0) { return n.x; } - long sum = 0; - for (LayoutEdge e : n.succs) { - sum += e.to.x + e.relativeTo - e.relativeFrom; + int[] values = new int[size]; + for (int i = 0; i < size; i++) { + LayoutEdge e = n.succs.get(i); + values[i] = e.to.x + e.relativeTo - e.relativeFrom; + if (e.vip) { + return values[i]; + } } - return (int) (sum / size); // why not the median? + return median(values); } private int median(int[] values) { @@ -682,14 +691,6 @@ r.insert(n, optimal); } } - /* - for(int i=0; i<layers.length; i++) { - NodeRow r = new NodeRow(space[i]); - for(LayoutNode n : upProcessingOrder[i]) { - int optimal = calculateOptimalUp(n); - r.insert(n, optimal); - } - }*/ } private void doubleSweep() { @@ -764,350 +765,6 @@ treeSet.add(n); } } - - private class AssignXCoordinates extends AlgorithmPart { - - HashMap<LayoutNode, Segment> hashMap = new HashMap<>(); - ArrayList<Segment> segments = new ArrayList<>(); - - private void generateSegments() { - - for (int i = 0; i < layerCount; i++) { - for (LayoutNode n : layers[i]) { - if (!hashMap.containsKey(n)) { - Segment s = new Segment(); - segments.add(s); - LayoutNode curNode = n; - - int maxLength = 0; - while (curNode.succs.size() == 1 && curNode.preds.size() == 1) { - s.nodes.add(curNode); - assert !hashMap.containsKey(curNode); - hashMap.put(curNode, s); - curNode = curNode.succs.get(0).to; - maxLength++; - //if(maxLength > 10) break; - } - - if (s.nodes.size() > 0 && curNode.preds.size() == 1 && curNode.vertex == null) { - s.nodes.add(curNode); - assert !hashMap.containsKey(curNode); - hashMap.put(curNode, s); - } - - if (s.nodes.size() == 0) { - // Simple segment with a single node - s.nodes.add(n); - hashMap.put(n, s); - } - } - } - } - } - - private void addEdges() { - - for (int i = 0; i < layerCount; i++) { - LayoutNode prev = null; - for (LayoutNode n : layers[i]) { - - if (prev != null) { - Segment s1 = hashMap.get(prev); - Segment s2 = hashMap.get(n); - - if (s1 != s2) { - s1.succs.add(s2); - s2.preds.add(s1); - } - } - prev = n; - - } - } - } - - private void topologicalSorting() { - - Queue<Segment> queue = new LinkedList<>(); - - int index = 0; - ArrayList<Segment> newList = new ArrayList<>(); - for (Segment s : segments) { - if (s.preds.size() == 0) { - s.orderNumber = index; - newList.add(s); - index++; - queue.add(s); - } - } - - while (!queue.isEmpty()) { - Segment s = queue.remove(); - - for (Segment succ : s.succs) { - succ.preds.remove(s); - if (succ.preds.size() == 0) { - queue.add(succ); - succ.orderNumber = index; - newList.add(succ); - index++; - } - } - } - - segments = newList; - } - - private void initialPositions() { - - int[] minPos = new int[layers.length]; - - for (Segment s : segments) { - int max = 0; - for (LayoutNode n : s.nodes) { - int x = minPos[n.layer]; - if (x > max) { - max = x; - } - } - - for (LayoutNode n : s.nodes) { - minPos[n.layer] = max + n.width + xOffset; - n.x = max; - } - } - } - - private int predSum(LayoutNode n) { - int sum = 0; - for (LayoutEdge e : n.preds) { - assert e.to == n; - //sum += (e.from.x + e.relativeFrom + (int)hashMap.get(e.from).d) - (e.to.x + e.relativeTo + (int)hashMap.get(e.to).d); - sum += (e.from.x + e.relativeFrom) - (e.to.x + e.relativeTo); - } - - return sum; - } - - private int succSum(LayoutNode n) { - int sum = 0; - for (LayoutEdge e : n.succs) { - - assert e.from == n; - sum += (e.to.x + e.relativeTo) - (e.from.x + e.relativeFrom); - //sum += (e.to.x + e.relativeTo + (int)hashMap.get(e.to).d) - (e.from.x + e.relativeFrom + (int)hashMap.get(e.from).d); - } - - return sum; - - } - - private void downValues() { - - for (Segment s : segments) { - downValues(s); - - } - - } - - private void downValues(Segment s) { - LayoutNode n = s.nodes.get(0); // Only first node needed, all other have same coordinate - - if (n.preds.size() == 0) { - // Value is 0.0; - if (n.succs.size() == 0) { - s.d = 0.0f; - } else { - s.d = (((float) succSum(n) / (float) n.succs.size())) / 2; - } - } else { - s.d = (float) predSum(n) / (float) n.preds.size(); - } - } - - private void upValues() { - for (Segment s : segments) { - upValues(s); - } - } - - private void upValues(Segment s) { - LayoutNode n = s.nodes.get(0); // Only first node needed, all other have same coordinate - - if (n.succs.size() == 0) { - // Value is 0.0; - if (n.preds.size() == 0) { - s.d = 0.0f; - } else { - s.d = (float) predSum(n) / (float) n.preds.size(); - } - } else { - s.d = ((float) succSum(n) / (float) n.succs.size()) / 2; - } - } - - private void sweep(boolean down) { - - if (down) { - downValues(); - } else { - upValues(); - } - - SortedSet<Region> regions = new TreeSet<>(regionComparator); - for (Segment s : segments) { - s.region = new Region(); - s.region.minOrderNumber = s.orderNumber; - s.region.segments.add(s); - s.region.d = s.d; - regions.add(s.region); - } - - for (Segment s : segments) { - for (LayoutNode n : s.nodes) { - if (n.pos != 0) { - LayoutNode prevNode = layers[n.layer].get(n.pos - 1); - if (prevNode.x + prevNode.width + xOffset == n.x) { - Segment other = hashMap.get(prevNode); - Region r1 = s.region; - Region r2 = other.region; - // They are close together - if (r1 != r2 && r2.d >= r1.d) { - - if (r2.segments.size() < r1.segments.size()) { - - r1.d = (r1.d * r1.segments.size() + r2.d * r2.segments.size()) / (r1.segments.size() + r2.segments.size()); - - for (Segment tempS : r2.segments) { - r1.segments.add(tempS); - tempS.region = r1; - r1.minOrderNumber = Math.min(r1.minOrderNumber, tempS.orderNumber); - } - - regions.remove(r2); - } else { - - r2.d = (r1.d * r1.segments.size() + r2.d * r2.segments.size()) / (r1.segments.size() + r2.segments.size()); - - for (Segment tempS : r1.segments) { - r2.segments.add(tempS); - tempS.region = r2; - r2.minOrderNumber = Math.min(r2.minOrderNumber, tempS.orderNumber); - } - - regions.remove(r1); - } - } - } - } - } - } - - - - ArrayList<Region> reversedRegions = new ArrayList<>(); - for (Region r : regions) { - if (r.d < 0) { - processRegion(r, down); - } else { - reversedRegions.add(0, r); - } - } - - for (Region r : reversedRegions) { - processRegion(r, down); - } - - } - - private void processRegion(Region r, boolean down) { - - // Do not move - if ((int) r.d == 0) { - return; - } - - ArrayList<Segment> arr = new ArrayList<>(); - for (Segment s : r.segments) { - arr.add(s); - } - - if (r.d > 0) { - Collections.reverse(arr); - } - - for (Segment s : arr) { - - - int min = (int) r.d; - if (min < 0) { - min = -min; - } - - for (LayoutNode n : s.nodes) { - - int layer = n.layer; - int pos = n.pos; - - - if (r.d > 0) { - - if (pos != layers[layer].size() - 1) { - - int off = layers[layer].get(pos + 1).x - n.x - xOffset - n.width; - assert off >= 0; - if (off < min) { - min = off; - } - } - - } else { - - if (pos != 0) { - - int off = n.x - xOffset - layers[layer].get(pos - 1).x - layers[layer].get(pos - 1).width; - assert off >= 0; - if (off < min) { - min = off; - } - } - } - } - - assert min >= 0; - if (min != 0) { - for (LayoutNode n : s.nodes) { - if (r.d > 0) { - n.x += min; - } else { - n.x -= min; - } - - } - } - } - } - - @Override - protected void run() { - - generateSegments(); - addEdges(); - topologicalSorting(); - initialPositions(); - for (int i = 0; i < SWEEP_ITERATIONS; i++) { - - sweep(true); - sweep(true); - sweep(false); - sweep(false); - } - - sweep(true); - sweep(true); - } - } private static Comparator<LayoutNode> crossingNodeComparator = new Comparator<LayoutNode>() { @Override @@ -1217,21 +874,20 @@ for (LayoutNode n : layers[i]) { int sum = 0; + int count = 0; for (LayoutEdge e : n.preds) { int cur = e.from.x + e.relativeFrom; - - /*pos; - if(e.from.width != 0 && e.relativeFrom != 0) { - cur += (float)e.relativeFrom / (float)(e.from.width); - }*/ - - sum += cur; + int factor = 1; + if (e.vip) { + factor = VIP_BONUS; + } + sum += cur*factor; + count+=factor; } - if (n.preds.size() > 0) { - sum /= n.preds.size(); + if (count > 0) { + sum /= count; n.crossingNumber = sum; - //if(n.vertex == null) n.crossingNumber += layers[i].size(); } } @@ -1260,9 +916,9 @@ next = layers[index].get(i + 1); } - boolean cond = (n.succs.size() == 0); + boolean cond = n.succs.isEmpty(); if (down) { - cond = (n.preds.size() == 0); + cond = n.preds.isEmpty(); } if (cond) { @@ -1288,21 +944,21 @@ for (LayoutNode n : layers[i]) { + int count = 0; int sum = 0; for (LayoutEdge e : n.succs) { - int cur = e.to.x + e.relativeTo;//pos; - /* - if(e.to.width != 0 && e.relativeTo != 0) { - cur += (float)e.relativeTo / (float)(e.to.width); - }*/ - - sum += cur; + int cur = e.to.x + e.relativeTo; + int factor = 1; + if (e.vip) { + factor = VIP_BONUS; + } + sum += cur*factor; + count+=factor; } - if (n.succs.size() > 0) { - sum /= n.succs.size(); + if (count > 0) { + sum /= count; n.crossingNumber = sum; - //if(n.vertex == null) n.crossingNumber += layers[i].size(); } } @@ -1433,6 +1089,7 @@ topEdge.relativeTo = topNode.width / 2; topEdge.to = topNode; topEdge.link = e.link; + topEdge.vip = e.vip; e.from.succs.add(topEdge); topNode.preds.add(topEdge); } else { @@ -1448,6 +1105,7 @@ topEdge.relativeTo = topNode.width / 2; topEdge.to = topNode; topEdge.link = e.link; + topEdge.vip = e.vip; e.from.succs.add(topEdge); topNode.preds.add(topEdge); topNodeHash.put(e.relativeFrom, topNode); @@ -1475,6 +1133,7 @@ bottomEdge.relativeFrom = bottomNode.width / 2; bottomEdge.from = bottomNode; bottomEdge.link = e.link; + bottomEdge.vip = e.vip; e.to.preds.add(bottomEdge); bottomEdgeHash.put(topEdge, bottomEdge); bottomNode.succs.add(bottomEdge); @@ -1514,6 +1173,7 @@ edges[0] = new LayoutEdge(); edges[0].from = n; edges[0].relativeFrom = i; + edges[0].vip = e.vip; n.succs.add(edges[0]); nodes[0] = new LayoutNode(); @@ -1525,6 +1185,7 @@ edges[0].relativeTo = nodes[0].width / 2; for (int j = 1; j < cnt; j++) { edges[j] = new LayoutEdge(); + edges[j].vip = e.vip; edges[j].from = nodes[j - 1]; edges[j].relativeFrom = nodes[j - 1].width / 2; nodes[j - 1].succs.add(edges[j]); @@ -1583,6 +1244,7 @@ n.preds.add(e); nodes.add(n); LayoutEdge result = new LayoutEdge(); + result.vip = e.vip; n.succs.add(result); result.from = n; result.relativeFrom = n.width / 2; @@ -2050,6 +1712,7 @@ edge.link = l; edge.from.succs.add(edge); edge.to.preds.add(edge); + edge.vip = l.isVIP(); //assert edge.from != edge.to; // No self-loops allowed }
--- a/src/share/tools/IdealGraphVisualizer/Layout/src/com/sun/hotspot/igv/layout/Link.java Sat Jan 28 00:44:26 2012 +0100 +++ b/src/share/tools/IdealGraphVisualizer/Layout/src/com/sun/hotspot/igv/layout/Link.java Sat Jan 28 15:48:40 2012 +0100 @@ -35,6 +35,8 @@ public Port getFrom(); public Port getTo(); + + public boolean isVIP(); public List<Point> getControlPoints();