graph.java~

该工具也是用于字节码插桩

/*
 * Graph.java
 *
 * Created on July 20, 2001, 12:24 AM
 *
 * See LICENSE file for license conditions.
 */

package residue.graph;

import de.fub.bytecode.generic.*;
import de.fub.bytecode.classfile.*;

import java.util.*;
import java.io.*;

import residue.graph.Node;

/**
 * This class is an overall control class for flow
 * control graphs.
 *
 * @author  Carl Howells
 * @version 
 */
public class Graph
{
	// InstructionHandle -> Node table
	private Map nodeTable;
		
	// InstructionHandle -> Block table
	private Map blockTable;
	
	// The set of blocks which are start points of execution.
	// This is used in predominator calculation only.
	private Set headBlocks;
	
	/**
	 * Left protected in case subclasses are ever created.
	 */
	protected Graph()
	{
		nodeTable = new HashMap();
		blockTable = new HashMap();
		headBlocks = new HashSet();
	} // Graph
	
	/**
	 * Method for creating a control flow graph
	 * given the necessary information.
	 */
	public Graph(InstructionList il,
	             LineNumberTable lt,
	             CodeExceptionGen [] exes,
	             ConstantPoolGen cp
				 )
	{
		this();
		
		// if the LineNumberTable is absent, replace with a default.
		if (lt == null)
		{
			lt = new LineNumberTable(0, 1, new LineNumber [] { new LineNumber(0, 0) }, null);
		}
		
		// First pass:  Build a node for each instruction.  Put in table
		InstructionHandle curr = il.getStart();
		while (curr != null)
		{
			int srcline = lt.getSourceLine(curr.getPosition());
			nodeTable.put(curr, new Node(curr, srcline));
			curr = curr.getNext();
		} // while
		
		// Second pass:  Use visitor to connect nodes
		ConnectionVisitor cv = new ConnectionVisitor(nodeTable, cp);
		curr = il.getStart();
		while (curr != null)
		{
			cv.startVisit(curr);
			if (cv.shouldConnectToNext())
			{
				Node n = (Node)nodeTable.get(curr);
				Node t = (Node)nodeTable.get(curr.getNext());
				
				n.addEdge(t);
			}
			curr = curr.getNext();
		} // while
		
		// Second and a half pass:  Connect the start of 
		// exception handler blocks to their handler
		if (exes != null)
		{
			for (int i = 0; i < exes.length; i++)
			{
				Node n = (Node)nodeTable.get(exes[i].getStartPC());
				Node t = (Node)nodeTable.get(exes[i].getHandlerPC());
				n.addEdge(t);
			}
		} // if
		
		// Third pass:  Condense nodes to basic blocks
		BasicBlock block = new BasicBlock();
		curr = il.getStart();
		
		while (curr != null)
		{
			Node n = (Node)nodeTable.get(curr);
			
			// check to see if the beginning of a block:
			if (n.getNumberIncomingEdges() != 1)
				block = new BasicBlock();
			
			// put in current block, and put current block in table
			blockTable.put(curr, block);
			block.add(n);
			
			// check to see if the end of a block:
			if (n.getEdges().size() != 1)
			{
				block = new BasicBlock();
			}
			else
			{
				// check for goto
				Node next = (Node)nodeTable.get(curr.getNext());
				if (!n.getEdges().contains(next))
					block = new BasicBlock();
			} // else
			
			curr = curr.getNext();
		} // while
		
		// create set of head Blocks
		Iterator it = cv.getHeads().iterator();
		while (it.hasNext())
			headBlocks.add(blockTable.get(it.next()));
		
	} // Graph
	
	public Set getNodes()
	{
		return Collections.unmodifiableSet(new HashSet(nodeTable.values()));
	} // getNodes
	
	public Set getBlocks()
	{
		return Collections.unmodifiableSet(new HashSet(blockTable.values()));
	} // getBlocks
	
	public Map getNodeTable()
	{
		return Collections.unmodifiableMap(nodeTable);
	} // getNodeTable
	
	public Map getBlockTable()
	{
		return Collections.unmodifiableMap(blockTable);
	} // getBlockTable
	
	/**
	 * Reverses the graph.  Implemented so that
	 * calculation of dominators can be done in one
	 * spot only.
	 */
	private void reverse()
	{
		Map parents = new HashMap();
		
		List l = new ArrayList(getBlocks());
		
		// calculate parents
		Iterator it = l.iterator();
		while (it.hasNext())
		{
			BasicBlock b = (BasicBlock)it.next();
			
			Iterator children = b.getEdges().iterator();
			while (children.hasNext())
			{
				BasicBlock child = (BasicBlock)children.next();
				
				if (!parents.containsKey(child))
					parents.put(child, new HashSet());
				
				Set p = (Set)parents.get(child);
				p.add(b);
			} // while
		} // while
		
		// replace children with parents
		it = l.iterator();
		while (it.hasNext())
		{
			BasicBlock b = (BasicBlock)it.next();
			
			if (parents.containsKey(b))
				b.setEdges((Set)parents.get(b));
			else
				b.setEdges(new HashSet());
		}
	} // reverse
	
	/**
	 * Returns a map from each block to its set of predominators
	 */
	public Map predominators()
	{
		// implemented by reversing this graph, using the postDominator
		// relationship, and then reversing it again.
		reverse();
		Map result = postdominators(headBlocks);
		reverse();
		return result;
	} // predominators
	
	/**
	 * Returns a map from each block to its set of postdominators
	 */
	public Map postdominators()
	{
		return postdominators(new HashSet());
	} // postdominators
	
	/**
	 * The actual implementation for finding postdominators, using
	 * a set of start blocks.
	 */
	private Map postdominators(Set startblocks)
	{
		LinkedList ll = new LinkedList(getBlocks());
		Map result = new HashMap();
		
		// map from a block to its parents
		Map parents = new HashMap();
		
		// initialize postdominator sets to universe, and set parent relations.
		Iterator it = ll.iterator();
		while (it.hasNext())
		{
			BasicBlock b = (BasicBlock)it.next();
			result.put(b, new HashSet(getBlocks()));
			
			Iterator children = b.getEdges().iterator();
			while (children.hasNext())
			{
				BasicBlock child = (BasicBlock)children.next();
				
				if (!parents.containsKey(child))
					parents.put(child, new HashSet());
				
				Set p = (Set)parents.get(child);
				p.add(b);
			}
		} // while
		
		// work towards greatest fixed point
		while (!ll.isEmpty())
		{
			BasicBlock bb = (BasicBlock)ll.removeLast();
			
			Set bbdom = (Set)result.get(bb);
			
			int size = bbdom.size();
			
			if (startblocks.contains(bb) || bb.getEdges().size() == 0)
			{
				// no children, so no postdominators
				bbdom.clear();
			}
			else
			{
				// intersect with children's postdominaters
				it = bb.getEdges().iterator();
				while (it.hasNext())
				{
					BasicBlock child = (BasicBlock)it.next();
					Set childdom = (Set)result.get(child);
					
					bbdom.retainAll(childdom);
				}
			}
			
			// put the block back into its own dominator set
			bbdom.add(bb);
			
			// put dependent values back in worklist
			if (bbdom.size() < size && parents.containsKey(bb))
			{
				it = ((Set)parents.get(bb)).iterator();
				while (it.hasNext())
					ll.addLast(it.next());
			}
		} // while
		
		return result;
	} // postdominators
	
	/**
	 * returns a map from each BasicBlock to its set of children
	 * in the predominator tree
	 */
	public Map predominatorTree()
	{
		reverse();
		Map result = postdominatorTree(headBlocks);
		reverse();
		return result;
	} // predominatorTree()
	
	/**
	 * returns a map from each BasicBlock to its set of children
	 * in the postdominator tree
	 */
	public Map postdominatorTree()
	{
		return postdominatorTree(new HashSet());
	} // postdominatorTree
	
	/**
	 * Actual implementation of finding dominator trees
	 */
	private Map postdominatorTree(Set startblocks)
	{
		Map result = new HashMap();
		
		Map doms = postdominators(startblocks);
		Iterator it = doms.keySet().iterator();
		while (it.hasNext())
		{
			BasicBlock b = (BasicBlock)it.next();
			
			Set domsleft = new HashSet((Set)doms.get(b));
			
			domsleft.remove(b);
			
			Iterator removable = new ArrayList(domsleft).iterator();
			while (removable.hasNext())
			{
				BasicBlock dom = (BasicBlock)removable.next();
				
				if (!domsleft.contains(dom)) continue;
				
				Iterator transdoms = ((Set)doms.get(dom)).iterator();
				while (transdoms.hasNext())
					domsleft.remove(transdoms.next());
				
				domsleft.add(dom);
			}
			
			if (domsleft.size() == 0)
			{
				// don't do anything
			}
			else if (domsleft.size() == 1)
			{
				BasicBlock dom = (BasicBlock)domsleft.iterator().next();
				
				if (!result.containsKey(dom))
					result.put(dom, new HashSet());
				
				Set s = (Set)result.get(dom);
				s.add(b);
			}
			else
			{
				throw new RuntimeException("broken algorithm " + domsleft.size());
			}
			
		} // while
		
		return result;
	} // postdominatorTree
	
	/**
	 * Debug method for routines that produce a map
	 * from BasicBlock to Set of BasicBlock, with blocks
	 * within the current graph.
	 */
	public void mapToGXL(Map m, PrintStream p)
	{
		p.println("<?xml version=\"1.0\" ?>\n");
		p.println("<gxl>");
		p.println("  <graph>");
		
		// output nodes		
		Iterator it = getBlocks().iterator();
		while (it.hasNext())
		{
			BasicBlock b = (BasicBlock)it.next();
			
			p.println("    <node id=\"" + b.getPosition() + "\" type=\"basicblock\">");
			p.print("      <attr name=\"lines\"><set>");
			
			Iterator lines = b.getLines().iterator();
			while (lines.hasNext())
			{
				p.print("<int>" + lines.next() + "</int>");
			}
			p.println("</set></attr>");
			p.println("    </node>\n");
		} // while
		
		// output edges
		it = m.keySet().iterator();
		while (it.hasNext())
		{
			BasicBlock b = (BasicBlock)it.next();
			
			Iterator edges = ((Set)m.get(b)).iterator();
			while (edges.hasNext())
			{
				BasicBlock t = (BasicBlock)edges.next();
				p.println("    <edge from=\"" + b.getPosition() + "\" to=\"" + t.getPosition() + "\"/>");
			}
		} // while
		
		p.println("  </graph>");
		p.println("</gxl>");
	} // mapToGXL
	
	/**
	 * Creates a representation of the current graph in GXL and
	 * outputs it to the given PrintStream
	 */
	public void toGXL(PrintStream p)
	{
		blocks2GXL(getBlocks(), p);
	} // toGXL
	
	/**
	 * Debug method, backing for toGXL method
	 */
	private static void blocks2GXL(Set blocks, PrintStream p)
	{
		p.println("<?xml version=\"1.0\" ?>\n");
		p.println("<gxl>");
		p.println("  <graph>");
		
		// output nodes		
		Iterator it = blocks.iterator();
		while (it.hasNext())
		{
			BasicBlock b = (BasicBlock)it.next();
			
			p.println("    <node id=\"" + b.getPosition() + "\" type=\"basicblock\">");
			p.print("      <attr name=\"lines\"><set>");
			
			Iterator lines = b.getLines().iterator();
			while (lines.hasNext())
			{
				p.print("<int>" + lines.next() + "</int>");
			}
			p.println("</set></attr>");
			p.println("    </node>\n");
		} // while
		
		// output edges
		it = blocks.iterator();
		while (it.hasNext())
		{
			BasicBlock b = (BasicBlock)it.next();
			
			Iterator edges = b.getEdges().iterator();
			while (edges.hasNext())
			{
				BasicBlock t = (BasicBlock)edges.next();
				p.println("    <edge from=\"" + b.getPosition() + "\" to=\"" + t.getPosition() + "\"/>");
			}
		} // while
		
		p.println("  </graph>");
		p.println("</gxl>");
	} // block2GXL
	
	
	/**
	 * debug method, left in for completeness.
	 */
	private static void nodes2GXL(Set nodes, PrintStream p)
	{
		p.println("<?xml version=\"1.0\" ?>\n");
		p.println("<gxl>");
		p.println("  <graph>");
		
		// write out nodes
		Iterator it = nodes.iterator();
		while (it.hasNext())
		{
			Node n = (Node)it.next();
			
			p.println("    <node id=\"" + n.getPosition() + "\" type=\"instruction\">");
			p.println("      <attr name=\"line\"><int>" + n.getLine() + "</int></attr>");
			p.println("      <attr name=\"incomingedges\"><int>" + n.getNumberIncomingEdges() + "</int></attr>");
			p.println("    </node>\n");
		} // while
		
		p.println();
		
		// write out edges
		it = nodes.iterator();
		while (it.hasNext())
		{
			Node n = (Node)it.next();
			Iterator edges = n.getEdges().iterator();
			while (edges.hasNext())
			{
				Node t = (Node)edges.next();
				p.println("    <edge from=\"" + n.getPosition() + "\" to=\"" + t.getPosition() + "\"/>");
			}
		} // while
		
		p.println("  </graph>");
		p.println("</gxl>");
	} // nodes2GXL
	
	
	/**
	 * Debug method, left in for further testing.
	 */
	public static void main(String [] args) throws Exception
	{
		String s;
		String t;
		if (args.length < 2)
		{
			s = ClassLoader.getSystemResource("residue/graph/Graph.class").getFile();
			t = "main([Ljava/lang/String;)V";
		}
		else
		{
			s = args[0];
			t = args[1];
		}
		
		JavaClass jc = new ClassParser(s).parse();
		
		Method [] m = jc.getMethods();
		
		for (int i = 0; i < m.length; i++)
		{
			if ((m[i].getName() + m[i].getSignature()).equals(t))
			{
				ConstantPoolGen cp = new ConstantPoolGen(m[i].getConstantPool());
				MethodGen mg = new MethodGen(m[i], null, cp);
				Graph g = new Graph(mg.getInstructionList(),
				                    m[i].getCode().getLineNumberTable(),
				                    mg.getExceptionHandlers(),
									cp);
				g.toGXL(System.out);
				
				//Map map = g.predominatorTree();
				//Map map = residue.Instrumenter.reduceBlocksConservative(g);
				//g.mapToGXL(map, System.out);
			}
		}
		
	} // main
	
} // class Graph