Mercurial > hg > graal-compiler

comparison visualizer/Difference/src/com/sun/hotspot/igv/difference/Difference.java @ 4512:015fb895586b

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Moved visualizer to new directory.
author Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
date Tue, 07 Feb 2012 22:41:09 +0100
parents
children
comparison
equal deleted inserted replaced
4511:6cb549627941 4512:015fb895586b
1 /*
2 * Copyright (c) 1998, 2008, Oracle and/or its affiliates. All rights reserved.
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. Oracle designates this
8 * particular file as subject to the "Classpath" exception as provided
9 * by Oracle in the LICENSE file that accompanied this code.
10 *
11 * This code is distributed in the hope that it will be useful, but WITHOUT
12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 * version 2 for more details (a copy is included in the LICENSE file that
15 * accompanied this code).
16 *
17 * You should have received a copy of the GNU General Public License version
18 * 2 along with this work; if not, write to the Free Software Foundation,
19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20 *
21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22 * or visit www.oracle.com if you need additional information or have any
23 * questions.
24 */
25 package com.sun.hotspot.igv.difference;
26
27 import com.sun.hotspot.igv.data.Properties;
28 import com.sun.hotspot.igv.data.*;
29 import com.sun.hotspot.igv.data.services.Scheduler;
30 import java.util.*;
31 import org.openide.util.Lookup;
32
33 /**
34 *
35 * @author Thomas Wuerthinger
36 */
37 public class Difference {
38
39 public static final String PROPERTY_STATE = "state";
40 public static final String VALUE_NEW = "new";
41 public static final String VALUE_CHANGED = "changed";
42 public static final String VALUE_SAME = "same";
43 public static final String VALUE_DELETED = "deleted";
44 public static final String OLD_PREFIX = "OLD_";
45 public static final String MAIN_PROPERTY = "name";
46 public static final double LIMIT = 100.0;
47 public static final String[] IGNORE_PROPERTIES = new String[]{"idx", "debug_idx"};
48
49 public static InputGraph createDiffGraph(InputGraph a, InputGraph b) {
50 if (a.getGroup() == b.getGroup()) {
51 return createDiffSameGroup(a, b);
52 } else {
53 return createDiff(a, b);
54 }
55 }
56
57 private static InputGraph createDiffSameGroup(InputGraph a, InputGraph b) {
58 Map<Integer, InputNode> keyMapB = new HashMap<>(b.getNodes().size());
59 for (InputNode n : b.getNodes()) {
60 Integer key = n.getId();
61 assert !keyMapB.containsKey(key);
62 keyMapB.put(key, n);
63 }
64
65 Set<NodePair> pairs = new HashSet<>();
66
67 for (InputNode n : a.getNodes()) {
68 Integer key = n.getId();
69
70
71 if (keyMapB.containsKey(key)) {
72 InputNode nB = keyMapB.get(key);
73 pairs.add(new NodePair(n, nB));
74 }
75 }
76
77 return createDiff(a, b, pairs);
78 }
79
80 private static void ensureScheduled(InputGraph a) {
81 if (a.getBlocks().isEmpty()) {
82 Scheduler s = Lookup.getDefault().lookup(Scheduler.class);
83 a.clearBlocks();
84 s.schedule(a);
85 a.ensureNodesInBlocks();
86 }
87 }
88
89 private static InputGraph createDiff(InputGraph a, InputGraph b, Set<NodePair> pairs) {
90 ensureScheduled(a);
91 ensureScheduled(b);
92
93 Group g = new Group(null);
94 g.setMethod(a.getGroup().getMethod());
95 if (a.getGroup() == b.getGroup()) {
96 g.getProperties().add(a.getGroup().getProperties());
97 } else {
98 // copy properties that have the same value in both groups
99 Properties bps = b.getGroup().getProperties();
100 for (Property p : a.getGroup().getProperties()) {
101 String value = p.getValue();
102 if (value != null && value.equals(bps.get(p.getName()))) {
103 g.getProperties().setProperty(p.getName(), value);
104 }
105 }
106 }
107 g.getProperties().setProperty("name", "Difference");
108 InputGraph graph = new InputGraph(a.getName() + ", " + b.getName());
109 g.addElement(graph);
110
111 Map<InputBlock, InputBlock> blocksMap = new HashMap<>();
112 for (InputBlock blk : a.getBlocks()) {
113 InputBlock diffblk = graph.addBlock(blk.getName());
114 blocksMap.put(blk, diffblk);
115 }
116 for (InputBlock blk : b.getBlocks()) {
117 InputBlock diffblk = graph.getBlock(blk.getName());
118 if (diffblk == null) {
119 diffblk = graph.addBlock(blk.getName());
120 }
121 blocksMap.put(blk, diffblk);
122 }
123
124 // Difference between block edges
125 Set<Pair<String, String>> aEdges = new HashSet<>();
126 for (InputBlockEdge edge : a.getBlockEdges()) {
127 aEdges.add(new Pair<>(edge.getFrom().getName(), edge.getTo().getName()));
128 }
129 for (InputBlockEdge bEdge : b.getBlockEdges()) {
130 InputBlock from = bEdge.getFrom();
131 InputBlock to = bEdge.getTo();
132 Pair<String, String> pair = new Pair<>(from.getName(), to.getName());
133 if (aEdges.contains(pair)) {
134 // same
135 graph.addBlockEdge(blocksMap.get(from), blocksMap.get(to));
136 aEdges.remove(pair);
137 } else {
138 // added
139 InputBlockEdge edge = graph.addBlockEdge(blocksMap.get(from), blocksMap.get(to));
140 edge.setState(InputBlockEdge.State.NEW);
141 }
142 }
143 for (Pair<String, String> deleted : aEdges) {
144 // removed
145 InputBlock from = graph.getBlock(deleted.getLeft());
146 InputBlock to = graph.getBlock(deleted.getRight());
147 InputBlockEdge edge = graph.addBlockEdge(from, to);
148 edge.setState(InputBlockEdge.State.DELETED);
149 }
150
151 Set<InputNode> nodesA = new HashSet<>(a.getNodes());
152 Set<InputNode> nodesB = new HashSet<>(b.getNodes());
153
154 Map<InputNode, InputNode> inputNodeMap = new HashMap<>(pairs.size());
155 for (NodePair p : pairs) {
156 InputNode n = p.getLeft();
157 assert nodesA.contains(n);
158 InputNode nB = p.getRight();
159 assert nodesB.contains(nB);
160
161 nodesA.remove(n);
162 nodesB.remove(nB);
163 InputNode n2 = new InputNode(n);
164 inputNodeMap.put(n, n2);
165 inputNodeMap.put(nB, n2);
166 graph.addNode(n2);
167 InputBlock block = blocksMap.get(a.getBlock(n));
168 block.addNode(n2.getId());
169 markAsChanged(n2, n, nB);
170 }
171
172 for (InputNode n : nodesA) {
173 InputNode n2 = new InputNode(n);
174 graph.addNode(n2);
175 InputBlock block = blocksMap.get(a.getBlock(n));
176 block.addNode(n2.getId());
177 markAsDeleted(n2);
178 inputNodeMap.put(n, n2);
179 }
180
181 int curIndex = 0;
182 for (InputNode n : nodesB) {
183 InputNode n2 = new InputNode(n);
184
185 // Find new ID for node of b, does not change the id property
186 while (graph.getNode(curIndex) != null) {
187 curIndex++;
188 }
189
190 n2.setId(curIndex);
191 graph.addNode(n2);
192 InputBlock block = blocksMap.get(b.getBlock(n));
193 block.addNode(n2.getId());
194 markAsNew(n2);
195 inputNodeMap.put(n, n2);
196 }
197
198 Collection<InputEdge> edgesA = a.getEdges();
199 Collection<InputEdge> edgesB = b.getEdges();
200
201 Set<InputEdge> newEdges = new HashSet<>();
202
203 for (InputEdge e : edgesA) {
204 int from = e.getFrom();
205 int to = e.getTo();
206 InputNode nodeFrom = inputNodeMap.get(a.getNode(from));
207 InputNode nodeTo = inputNodeMap.get(a.getNode(to));
208 char fromIndex = e.getFromIndex();
209 char toIndex = e.getToIndex();
210
211 InputEdge newEdge = new InputEdge(fromIndex, toIndex, nodeFrom.getId(), nodeTo.getId());
212 if (!newEdges.contains(newEdge)) {
213 markAsDeleted(newEdge);
214 newEdges.add(newEdge);
215 graph.addEdge(newEdge);
216 }
217 }
218
219 for (InputEdge e : edgesB) {
220 int from = e.getFrom();
221 int to = e.getTo();
222 InputNode nodeFrom = inputNodeMap.get(b.getNode(from));
223 InputNode nodeTo = inputNodeMap.get(b.getNode(to));
224 char fromIndex = e.getFromIndex();
225 char toIndex = e.getToIndex();
226
227 InputEdge newEdge = new InputEdge(fromIndex, toIndex, nodeFrom.getId(), nodeTo.getId());
228 if (!newEdges.contains(newEdge)) {
229 markAsNew(newEdge);
230 newEdges.add(newEdge);
231 graph.addEdge(newEdge);
232 } else {
233 newEdges.remove(newEdge);
234 graph.removeEdge(newEdge);
235 markAsSame(newEdge);
236 newEdges.add(newEdge);
237 graph.addEdge(newEdge);
238 }
239 }
240
241 return graph;
242 }
243
244 private static class NodePair extends Pair<InputNode, InputNode> {
245
246
247 public NodePair(InputNode n1, InputNode n2) {
248 super(n1, n2);
249 }
250
251 public double getValue() {
252
253 double result = 0.0;
254 for (Property p : getLeft().getProperties()) {
255 double faktor = 1.0;
256 for (String forbidden : IGNORE_PROPERTIES) {
257 if (p.getName().equals(forbidden)) {
258 faktor = 0.1;
259 break;
260 }
261 }
262 String p2 = getRight().getProperties().get(p.getName());
263 result += evaluate(p.getValue(), p2) * faktor;
264 }
265
266 return result;
267 }
268
269 private double evaluate(String p, String p2) {
270 if (p2 == null) {
271 return 1.0;
272 }
273 if (p.equals(p2)) {
274 return 0.0;
275 } else {
276 return (double) (Math.abs(p.length() - p2.length())) / p.length() + 0.5;
277 }
278 }
279 }
280
281 private static InputGraph createDiff(InputGraph a, InputGraph b) {
282
283 Set<InputNode> matched = new HashSet<>();
284
285 Set<NodePair> pairs = new HashSet<>();
286 for (InputNode n : a.getNodes()) {
287 String s = n.getProperties().get(MAIN_PROPERTY);
288 if (s == null) {
289 s = "";
290 }
291 for (InputNode n2 : b.getNodes()) {
292 String s2 = n2.getProperties().get(MAIN_PROPERTY);
293 if (s2 == null) {
294 s2 = "";
295 }
296
297 if (s.equals(s2)) {
298 NodePair p = new NodePair(n, n2);
299 pairs.add(p);
300 }
301 }
302 }
303
304 Set<NodePair> selectedPairs = new HashSet<>();
305 while (pairs.size() > 0) {
306
307 double min = Double.MAX_VALUE;
308 NodePair minPair = null;
309 for (NodePair p : pairs) {
310 double cur = p.getValue();
311 if (cur < min) {
312 minPair = p;
313 min = cur;
314 }
315 }
316
317 if (min > LIMIT) {
318 break;
319 } else {
320 selectedPairs.add(minPair);
321
322 Set<NodePair> toRemove = new HashSet<>();
323 for (NodePair p : pairs) {
324 if (p.getLeft() == minPair.getLeft() || p.getRight() == minPair.getRight()) {
325 toRemove.add(p);
326 }
327 }
328 pairs.removeAll(toRemove);
329 }
330 }
331
332 return createDiff(a, b, selectedPairs);
333 }
334
335 private static void markAsNew(InputEdge e) {
336 e.setState(InputEdge.State.NEW);
337 }
338
339 private static void markAsDeleted(InputEdge e) {
340 e.setState(InputEdge.State.DELETED);
341
342 }
343
344 private static void markAsSame(InputEdge e) {
345 e.setState(InputEdge.State.SAME);
346 }
347
348 private static void markAsChanged(InputNode n, InputNode firstNode, InputNode otherNode) {
349
350 boolean difference = false;
351 for (Property p : otherNode.getProperties()) {
352 String s = firstNode.getProperties().get(p.getName());
353 if (!p.getValue().equals(s)) {
354 difference = true;
355 n.getProperties().setProperty(OLD_PREFIX + p.getName(), p.getValue());
356 }
357 }
358
359 for (Property p : firstNode.getProperties()) {
360 String s = otherNode.getProperties().get(p.getName());
361 if (s == null && p.getValue().length() > 0) {
362 difference = true;
363 n.getProperties().setProperty(OLD_PREFIX + p.getName(), "");
364 }
365 }
366
367 if (difference) {
368 n.getProperties().setProperty(PROPERTY_STATE, VALUE_CHANGED);
369 } else {
370 n.getProperties().setProperty(PROPERTY_STATE, VALUE_SAME);
371 }
372 }
373
374 private static void markAsDeleted(InputNode n) {
375 n.getProperties().setProperty(PROPERTY_STATE, VALUE_DELETED);
376 }
377
378 private static void markAsNew(InputNode n) {
379 n.getProperties().setProperty(PROPERTY_STATE, VALUE_NEW);
380 }
381 }