Mercurial > hg > graal-compiler
view visualizer/HierarchicalLayout/src/com/sun/hotspot/igv/hierarchicallayout/Graph.java @ 10662:4ef92b67aeae
added HSAIL backend and tests
Contributed-by: Vasanth Venkatachalam <vasanth.venkatachalam@amd.com>
Contributed-by: Tom.Deneau <tom.deneau@amd.com>
Contributed-by: Eric Caspole <eric.caspole@amd.com>
author | Doug Simon <doug.simon@oracle.com> |
---|---|
date | Tue, 09 Jul 2013 10:40:37 +0200 |
parents | 015fb895586b |
children |
line wrap: on
line source
/* * Copyright (c) 2008, Oracle and/or its affiliates. All rights reserved. * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. * * This code is free software; you can redistribute it and/or modify it * under the terms of the GNU General Public License version 2 only, as * published by the Free Software Foundation. * * This code is distributed in the hope that it will be useful, but WITHOUT * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License * version 2 for more details (a copy is included in the LICENSE file that * accompanied this code). * * You should have received a copy of the GNU General Public License version * 2 along with this work; if not, write to the Free Software Foundation, * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. * * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA * or visit www.oracle.com if you need additional information or have any * questions. * */ package com.sun.hotspot.igv.hierarchicallayout; import java.util.*; /** * * @author Thomas Wuerthinger */ public class Graph<N, E> { private HashMap<Object, Node<N, E>> nodes; private HashMap<Object, Edge<N, E>> edges; private List<Node<N, E>> nodeList; public Graph() { nodes = new HashMap<>(); edges = new HashMap<>(); nodeList = new ArrayList<>(); } public Node<N, E> createNode(N data, Object key) { Node<N, E> n = new Node<>(this, data); assert key == null || !nodes.containsKey(key); if (key != null) { nodes.put(key, n); } nodeList.add(n); return n; } public Edge<N, E> createEdge(Node<N, E> source, Node<N, E> dest, E data, Object key) { Edge<N, E> e = new Edge<>(this, source, dest, data); source.addOutEdge(e); dest.addInEdge(e); if (key != null) { edges.put(key, e); } return e; } public Node<N, E> getNode(Object key) { return nodes.get(key); } public Edge<N, E> getEdge(Object key) { return edges.get(key); } public Collection<Edge<N, E>> getEdges() { return Collections.unmodifiableCollection(edges.values()); } public Collection<Node<N, E>> getNodes() { return Collections.unmodifiableList(nodeList); } public void removeEdge(Edge<N, E> e, Object key) { assert key == null || edges.containsKey(key); if (key != null) { edges.remove(key); } e.getSource().removeOutEdge(e); e.getDest().removeInEdge(e); } public class DFSTraversalVisitor { public void visitNode(Node<N, E> n) { } public boolean visitEdge(Edge<N, E> e, boolean backEdge) { return true; } } public class BFSTraversalVisitor { public void visitNode(Node<N, E> n, int depth) { } } public List<Node<N, E>> getNodesWithInDegree(int x) { return getNodesWithInDegree(x, true); } public List<Node<N, E>> getNodesWithInDegree(int x, boolean countSelfLoops) { List<Node<N, E>> result = new ArrayList<>(); for (Node<N, E> n : getNodes()) { if (n.getInDegree(countSelfLoops) == x) { result.add(n); } } return result; } private void markReachable(Node<N, E> startingNode) { ArrayList<Node<N, E>> arr = new ArrayList<>(); arr.add(startingNode); for (Node<N, E> n : getNodes()) { n.setReachable(false); } traverseDFS(arr, new DFSTraversalVisitor() { @Override public void visitNode(Node<N, E> n) { n.setReachable(true); } }); } public void traverseBFS(Node<N, E> startingNode, BFSTraversalVisitor tv, boolean longestPath) { if (longestPath) { markReachable(startingNode); } for (Node<N, E> n : getNodes()) { n.setVisited(false); n.setActive(false); } Queue<Node<N, E>> queue = new LinkedList<>(); queue.add(startingNode); startingNode.setVisited(true); int layer = 0; Node<N, E> lastOfLayer = startingNode; Node<N, E> lastAdded = null; while (!queue.isEmpty()) { Node<N, E> current = queue.poll(); tv.visitNode(current, layer); current.setActive(false); for (Edge<N, E> e : current.getOutEdges()) { if (!e.getDest().isVisited()) { boolean allow = true; if (longestPath) { for (Node<N, E> pred : e.getDest().getPredecessors()) { if ((!pred.isVisited() || pred.isActive()) && pred.isReachable()) { allow = false; break; } } } if (allow) { queue.offer(e.getDest()); lastAdded = e.getDest(); e.getDest().setVisited(true); e.getDest().setActive(true); } } } if (current == lastOfLayer && !queue.isEmpty()) { lastOfLayer = lastAdded; layer++; } } } public void traverseDFS(DFSTraversalVisitor tv) { traverseDFS(getNodes(), tv); } public void traverseDFS(Collection<Node<N, E>> startingNodes, DFSTraversalVisitor tv) { for (Node<N, E> n : getNodes()) { n.setVisited(false); n.setActive(false); } boolean result = false; for (Node<N, E> n : startingNodes) { traverse(tv, n); } } private void traverse(DFSTraversalVisitor tv, Node<N, E> n) { if (!n.isVisited()) { n.setVisited(true); n.setActive(true); tv.visitNode(n); for (Edge<N, E> e : n.getOutEdges()) { Node<N, E> next = e.getDest(); if (next.isActive()) { tv.visitEdge(e, true); } else { if (tv.visitEdge(e, false)) { traverse(tv, next); } } } n.setActive(false); } } public boolean hasCycles() { for (Node<N, E> n : getNodes()) { n.setVisited(false); n.setActive(false); } boolean result = false; for (Node<N, E> n : getNodes()) { result |= checkCycles(n); if (result) { break; } } return result; } private boolean checkCycles(Node<N, E> n) { if (n.isActive()) { return true; } if (!n.isVisited()) { n.setVisited(true); n.setActive(true); for (Node<N, E> succ : n.getSuccessors()) { if (checkCycles(succ)) { return true; } } n.setActive(false); } return false; } @Override public String toString() { StringBuilder s = new StringBuilder(); s.append("Nodes: "); for (Node<N, E> n : getNodes()) { s.append(n.toString()); s.append("\n"); } s.append("Edges: "); for (Edge<N, E> e : getEdges()) { s.append(e.toString()); s.append("\n"); } return s.toString(); } }