Mercurial > hg > truffle
annotate src/share/tools/IdealGraphVisualizer/Layout/src/com/sun/hotspot/igv/layout/LayoutGraph.java @ 21146:33ff6b03fad1
add support for control flow window and basic block view on graphs
Contributed-by: Michael Haupt <michael.haupt@oracle.com>
Contributed-by: Peter Hofer <peter.hofer@jku.at>
Contributed-by: Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
| author | Michael Haupt <michael.haupt@oracle.com> |
|---|---|
| date | Wed, 29 Apr 2015 08:31:28 +0200 |
| parents | 2b2ac41e70dd |
| children |
| rev | line source |
|---|---|
| 220 | 1 /* |
|
21146
33ff6b03fad1
add support for control flow window and basic block view on graphs
Michael Haupt <michael.haupt@oracle.com>
parents:
4391
diff
changeset
|
2 * Copyright (c) 2008, 2015, Oracle and/or its affiliates. All rights reserved. |
| 220 | 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. |
| 4 * | |
| 5 * This code is free software; you can redistribute it and/or modify it | |
| 6 * under the terms of the GNU General Public License version 2 only, as | |
| 7 * published by the Free Software Foundation. | |
| 8 * | |
| 9 * This code is distributed in the hope that it will be useful, but WITHOUT | |
| 10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or | |
| 11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License | |
| 12 * version 2 for more details (a copy is included in the LICENSE file that | |
| 13 * accompanied this code). | |
| 14 * | |
| 15 * You should have received a copy of the GNU General Public License version | |
| 16 * 2 along with this work; if not, write to the Free Software Foundation, | |
| 17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. | |
| 18 * | |
|
1552
c18cbe5936b8
6941466: Oracle rebranding changes for Hotspot repositories
trims
parents:
417
diff
changeset
|
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA |
|
c18cbe5936b8
6941466: Oracle rebranding changes for Hotspot repositories
trims
parents:
417
diff
changeset
|
20 * or visit www.oracle.com if you need additional information or have any |
|
c18cbe5936b8
6941466: Oracle rebranding changes for Hotspot repositories
trims
parents:
417
diff
changeset
|
21 * questions. |
| 220 | 22 * |
| 23 */ | |
| 24 package com.sun.hotspot.igv.layout; | |
| 25 | |
|
4391
2b2ac41e70dd
Organize imports in IGV.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
4390
diff
changeset
|
26 import java.util.*; |
| 220 | 27 |
| 28 /** | |
| 29 * | |
| 30 * @author Thomas Wuerthinger | |
| 31 */ | |
| 32 public class LayoutGraph { | |
| 33 | |
| 34 private Set<? extends Link> links; | |
| 35 private SortedSet<Vertex> vertices; | |
| 417 | 36 private HashMap<Vertex, Set<Port>> inputPorts; |
| 37 private HashMap<Vertex, Set<Port>> outputPorts; | |
| 38 private HashMap<Port, Set<Link>> portLinks; | |
| 220 | 39 |
| 40 public LayoutGraph(Set<? extends Link> links) { | |
| 41 this(links, new HashSet<Vertex>()); | |
| 42 } | |
| 43 | |
| 44 public LayoutGraph(Set<? extends Link> links, Set<? extends Vertex> additionalVertices) { | |
| 45 this.links = links; | |
| 46 assert verify(); | |
| 47 | |
|
4382
f22dc0a63f03
Removed old hierarchical layout manager; start removing cluster layout. apply diamond operator to whole source.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
2898
diff
changeset
|
48 vertices = new TreeSet<>(); |
|
f22dc0a63f03
Removed old hierarchical layout manager; start removing cluster layout. apply diamond operator to whole source.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
2898
diff
changeset
|
49 portLinks = new HashMap<>(links.size()); |
|
f22dc0a63f03
Removed old hierarchical layout manager; start removing cluster layout. apply diamond operator to whole source.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
2898
diff
changeset
|
50 inputPorts = new HashMap<>(links.size()); |
|
f22dc0a63f03
Removed old hierarchical layout manager; start removing cluster layout. apply diamond operator to whole source.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
2898
diff
changeset
|
51 outputPorts = new HashMap<>(links.size()); |
| 220 | 52 |
| 53 for (Link l : links) { | |
| 54 Port p = l.getFrom(); | |
| 55 Port p2 = l.getTo(); | |
| 56 Vertex v1 = p.getVertex(); | |
| 57 Vertex v2 = p2.getVertex(); | |
| 58 | |
| 59 if (!vertices.contains(v1)) { | |
| 60 | |
| 61 outputPorts.put(v1, new HashSet<Port>(1)); | |
| 62 inputPorts.put(v1, new HashSet<Port>(3)); | |
| 63 vertices.add(v1); | |
| 64 assert vertices.contains(v1); | |
| 65 } | |
| 66 | |
| 67 if (!vertices.contains(v2)) { | |
| 68 vertices.add(v2); | |
| 69 assert vertices.contains(v2); | |
| 70 outputPorts.put(v2, new HashSet<Port>(1)); | |
| 71 inputPorts.put(v2, new HashSet<Port>(3)); | |
| 72 } | |
| 73 | |
| 74 if (!portLinks.containsKey(p)) { | |
|
4382
f22dc0a63f03
Removed old hierarchical layout manager; start removing cluster layout. apply diamond operator to whole source.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
2898
diff
changeset
|
75 HashSet<Link> hashSet = new HashSet<>(3); |
| 220 | 76 portLinks.put(p, hashSet); |
| 77 } | |
| 78 | |
| 79 if (!portLinks.containsKey(p2)) { | |
| 80 portLinks.put(p2, new HashSet<Link>(3)); | |
| 81 } | |
| 82 | |
| 83 outputPorts.get(v1).add(p); | |
| 84 inputPorts.get(v2).add(p2); | |
| 85 | |
| 86 portLinks.get(p).add(l); | |
| 87 portLinks.get(p2).add(l); | |
| 88 } | |
| 89 | |
| 90 for (Vertex v : additionalVertices) { | |
| 91 if (!vertices.contains(v)) { | |
| 92 outputPorts.put(v, new HashSet<Port>(1)); | |
| 93 inputPorts.put(v, new HashSet<Port>(3)); | |
| 94 vertices.add(v); | |
| 95 vertices.contains(v); | |
| 96 } | |
| 97 } | |
| 98 } | |
| 99 | |
| 100 public Set<Port> getInputPorts(Vertex v) { | |
| 101 return this.inputPorts.get(v); | |
| 102 } | |
| 103 | |
| 104 public Set<Port> getOutputPorts(Vertex v) { | |
| 105 return this.outputPorts.get(v); | |
| 106 } | |
| 107 | |
| 108 public Set<Link> getPortLinks(Port p) { | |
| 109 return portLinks.get(p); | |
| 110 } | |
| 111 | |
| 112 public Set<? extends Link> getLinks() { | |
| 113 return links; | |
| 114 } | |
| 115 | |
| 116 public boolean verify() { | |
| 117 return true; | |
| 118 } | |
| 119 | |
| 120 public SortedSet<Vertex> getVertices() { | |
| 121 return vertices; | |
| 122 } | |
| 123 | |
| 124 private void markNotRoot(Set<Vertex> notRootSet, Vertex v, Vertex startingVertex) { | |
| 125 | |
| 126 if (notRootSet.contains(v)) { | |
| 127 return; | |
| 128 } | |
| 129 if (v != startingVertex) { | |
| 130 notRootSet.add(v); | |
| 131 } | |
| 132 Set<Port> outPorts = getOutputPorts(v); | |
| 133 for (Port p : outPorts) { | |
| 134 Set<Link> portLinks = getPortLinks(p); | |
| 135 for (Link l : portLinks) { | |
| 136 Port other = l.getTo(); | |
| 137 Vertex otherVertex = other.getVertex(); | |
| 138 if (otherVertex != startingVertex) { | |
| 139 markNotRoot(notRootSet, otherVertex, startingVertex); | |
| 140 } | |
| 141 } | |
| 142 } | |
| 143 } | |
| 144 | |
| 145 // Returns a set of vertices with the following properties: | |
| 146 // - All Vertices in the set startingRoots are elements of the set. | |
|
2898
53ddfe305645
IdealGraphVisualizer: merge changes from the IGV project on Kenai and add Oracle copyright notices where necessary
Peter Hofer <peter.hofer@jku.at>
parents:
1552
diff
changeset
|
147 // - When starting a DFS at every vertex in the set, every vertex of the |
| 220 | 148 // whole graph is visited. |
| 149 public Set<Vertex> findRootVertices(Set<Vertex> startingRoots) { | |
| 150 | |
|
4382
f22dc0a63f03
Removed old hierarchical layout manager; start removing cluster layout. apply diamond operator to whole source.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
2898
diff
changeset
|
151 Set<Vertex> notRootSet = new HashSet<>(); |
| 220 | 152 for (Vertex v : startingRoots) { |
| 153 if (!notRootSet.contains(v)) { | |
| 154 markNotRoot(notRootSet, v, v); | |
| 155 } | |
| 156 } | |
| 157 | |
| 158 Set<Vertex> tmpVertices = getVertices(); | |
| 159 for (Vertex v : tmpVertices) { | |
| 160 if (!notRootSet.contains(v)) { | |
| 161 if (this.getInputPorts(v).size() == 0) { | |
| 162 markNotRoot(notRootSet, v, v); | |
| 163 } | |
| 164 } | |
| 165 } | |
| 166 | |
| 167 for (Vertex v : tmpVertices) { | |
| 168 if (!notRootSet.contains(v)) { | |
| 169 markNotRoot(notRootSet, v, v); | |
| 170 } | |
| 171 } | |
| 172 | |
|
4382
f22dc0a63f03
Removed old hierarchical layout manager; start removing cluster layout. apply diamond operator to whole source.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
2898
diff
changeset
|
173 Set<Vertex> result = new HashSet<>(); |
| 220 | 174 for (Vertex v : tmpVertices) { |
| 175 if (!notRootSet.contains(v)) { | |
| 176 result.add(v); | |
| 177 } | |
| 178 } | |
| 179 assert tmpVertices.size() == 0 || result.size() > 0; | |
| 180 return result; | |
| 181 } | |
| 182 | |
| 183 public Set<Vertex> findRootVertices() { | |
| 184 return findRootVertices(new HashSet<Vertex>()); | |
| 185 } | |
|
21146
33ff6b03fad1
add support for control flow window and basic block view on graphs
Michael Haupt <michael.haupt@oracle.com>
parents:
4391
diff
changeset
|
186 |
|
33ff6b03fad1
add support for control flow window and basic block view on graphs
Michael Haupt <michael.haupt@oracle.com>
parents:
4391
diff
changeset
|
187 public SortedSet<Cluster> getClusters() { |
|
33ff6b03fad1
add support for control flow window and basic block view on graphs
Michael Haupt <michael.haupt@oracle.com>
parents:
4391
diff
changeset
|
188 |
|
33ff6b03fad1
add support for control flow window and basic block view on graphs
Michael Haupt <michael.haupt@oracle.com>
parents:
4391
diff
changeset
|
189 SortedSet<Cluster> clusters = new TreeSet<Cluster>(); |
|
33ff6b03fad1
add support for control flow window and basic block view on graphs
Michael Haupt <michael.haupt@oracle.com>
parents:
4391
diff
changeset
|
190 for (Vertex v : getVertices()) { |
|
33ff6b03fad1
add support for control flow window and basic block view on graphs
Michael Haupt <michael.haupt@oracle.com>
parents:
4391
diff
changeset
|
191 if (v.getCluster() != null) { |
|
33ff6b03fad1
add support for control flow window and basic block view on graphs
Michael Haupt <michael.haupt@oracle.com>
parents:
4391
diff
changeset
|
192 clusters.add(v.getCluster()); |
|
33ff6b03fad1
add support for control flow window and basic block view on graphs
Michael Haupt <michael.haupt@oracle.com>
parents:
4391
diff
changeset
|
193 } |
|
33ff6b03fad1
add support for control flow window and basic block view on graphs
Michael Haupt <michael.haupt@oracle.com>
parents:
4391
diff
changeset
|
194 } |
|
33ff6b03fad1
add support for control flow window and basic block view on graphs
Michael Haupt <michael.haupt@oracle.com>
parents:
4391
diff
changeset
|
195 |
|
33ff6b03fad1
add support for control flow window and basic block view on graphs
Michael Haupt <michael.haupt@oracle.com>
parents:
4391
diff
changeset
|
196 return clusters; |
|
33ff6b03fad1
add support for control flow window and basic block view on graphs
Michael Haupt <michael.haupt@oracle.com>
parents:
4391
diff
changeset
|
197 } |
| 220 | 198 } |