Start line:  
End line:  

Snippet Preview

Snippet HTML Code

Stack Overflow Questions
  /* Soot - a J*va Optimization Framework
   * Copyright (C) 1999-2010 Hossein Sadat-Mohtasham
   *
   * This library is free software; you can redistribute it and/or
   * modify it under the terms of the GNU Lesser General Public
   * License as published by the Free Software Foundation; either
   * version 2.1 of the License, or (at your option) any later version.
   *
   * This library 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
  * Lesser General Public License for more details.
  *
  * You should have received a copy of the GNU Lesser General Public
  * License along with this library; if not, write to the
  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  * Boston, MA 02111-1307, USA.
  */
 package soot.toolkits.graph.pdg;
 
 
 import java.util.List;
 
 import soot.Body;
 import soot.SootClass;
This class implements a Program Dependence Graph as defined in Ferrante, J., Ottenstein, K. J., and Warren, J. D. 1987. The program dependence graph and its use in optimization. ACM Trans. Program. Lang. Syst. 9, 3 (Jul. 1987), 319-349. DOI= http://doi.acm.org/10.1145/24039.24041 Note: the implementation is not exactly as in the above paper. It first finds the regions of control dependence then uses part of the algorithm given in the above paper to build the graph. The constructor accepts a UnitGraph, which can be a BriefUnitGraph, an ExceptionalUnitGraph, or an EnhancedUnitGraph. At the absence of exception handling constructs in a method, all of these work the same. However, at the presence of exception handling constructs, BriefUnitGraph is multi-headed and potentially multi-tailed which makes the results of RegionAnalysis and PDG construction unreliable (It's not clear if it would be useful anyway); Also, ExceptionalGraph's usefulness when exception handling is present is not so clear since almost every unit can throw exception hence the dependency is affected. Currently, the PDG is based on a UnitGraph (BlockGraph) and does not care whether flow is exceptional or not. The nodes in a PDG are of type PDGNode and the edges can have three labels: "dependency", "dependency-back", and "controlflow"; however, the "controlflow" edges are auxiliary and the dependencies are represented by the labels beginning with "dependency". Other labels can be added later for application or domain-specific cases. To support methods that contain exception-handling and multiple-heads or tails, use EnhancedUnitGraph. It does not represent exceptional flow in the way ExceptionalUnitGraph does, but it integrates them in a concise way. Also, it adds START/STOP nodes to graph if necessary to make the graph single entry single exit.

Author(s):
Hossein Sadat-Mohtasham Sep 2009
 
 
 	
 	protected Body m_body = null;
 	protected SootClass m_class = null;
 	protected UnitGraph m_cfg = null;
 	protected BlockGraph m_blockCFG = null;
 	protected List<Regionm_weakRegions = null;
 	protected List<Regionm_strongRegions = null;
 	protected PDGNode m_startNode = null;
 	protected List<PDGRegionm_pdgRegions = null;
 	private RegionAnalysis m_regionAnalysis = null;
 	private int m_strongRegionStartID;
 
 	
 	public HashMutablePDG(UnitGraph cfg)
 	{
 		this. = cfg.getBody();
		this. = cfg;
		this. = new RegionAnalysis(this.this..getMethod(), this.);
		/*
		 * Get the weak regions and save a copy. Note that the strong regions list is
		 * initially cloned from the weak region to be later modified.
		 */
		//Construct the PDG
		this. = HashMutablePDG.computePDGRegions(this.);
		/*This is needed to convert the initially Region-typed inner node of the PDG's head
			to a PDGRegion-typed one after the whole graph is computed.
			The root PDGRegion is the one with no parent.
		*/
		IRegion r = this..get(0);
		while(r.getParent() != null)
			r = r.getParent();
	}

This is the heart of the PDG contruction. It is huge and definitely needs some refactorings, but since it's been evlovong to cover some boundary cases it has become hard to rafactor. It uses the list of weak regions, along with the dominator and post-dominator trees to construct the PDG nodes.
	@SuppressWarnings("unchecked")
	protected void constructPDG()
	{
		List<Regionregions2process = new LinkedList<Region>();
		Region topLevelRegion = this..getTopLevelRegion();
		//This becomes the top-level region (or ENTRY region node)
		PDGNode pdgnode = new PDGNode(topLevelRegion..);
		this.addNode(pdgnode);
		this..put(topLevelRegionpdgnode);
		this. = pdgnode;
		topLevelRegion.setParent(null);
		regions2process.add(topLevelRegion);
		//while there's a (weak) region to process
		while(!regions2process.isEmpty())
		{
			Region r = regions2process.remove(0);
			//get the corresponding pdgnode
			pdgnode = this..get(r);
			/*
			 * For all the CFG nodes in the region, create the corresponding PDG node and edges, and
			 * process them if they are in the dependence set of other regions, i.e. other regions
			 * depend on them.
			 */
			List<Blockblocks = r.getBlocks();
			Hashtable<RegionList<Block>> toBeRemoved = new Hashtable<RegionList<Block>>();
			PDGNode prevPDGNodeInRegion = null;
			PDGNode curNodeInRegion = null;
			for(Iterator<Blockitr = blocks.iterator(); itr.hasNext();)
			{
				/*
				 * Add the PDG node corresponding to the CFG block node.
				 */
				Block a = itr.next();
				PDGNode pdgNodeOfA = null;
				{
					pdgNodeOfA = new PDGNode(a..);
					this.addNode(pdgNodeOfA);
					this..put(apdgNodeOfA);
				}
				else
					pdgNodeOfA = this..get(a);
				this.addEdge(pdgnodepdgNodeOfA"dependency");
				pdgnode.addDependent(pdgNodeOfA);
				//
				curNodeInRegion = pdgNodeOfA;
				/*
				 * For each successor B of A, if B does not post-dominate A, add all the
				 * nodes on the path from B to the L in the post-dominator tree, where L is the least
				 * common ancestor of A and B in the post-dominator tree (L will be either A itself or 
				 * the parent of A.).
				 */
				List<Blockbs = this..getSuccsOf(a);
				for(Iterator<BlockbItr = bs.iterator(); bItr.hasNext();)
				{
					List<Blockdependents = new ArrayList<Block>();
					Block b = bItr.next();
					if(b.equals(a))
						throw new RuntimeException("PDG construction: A and B are not supposed to be the same node!");
					DominatorNode aDode = pdom.getDode(a);
					DominatorNode bDode = pdom.getDode(b);
					//If B post-dominates A, go to the next successor.
					if(pdom.isDominatorOf(bDodeaDode))
						continue;
					//FIXME: what if the parent is null?!!
					DominatorNode aParentDode = aDode.getParent();
					DominatorNode dode = bDode;
					while(dode != aParentDode)
					{
						dependents.add((Block)dode.getGode());
						//This occurs if the CFG is multi-tailed and therefore the pdom is a forest.
						if(dode.getParent() == null)
							//throw new RuntimeException("parent dode in pdom is null: dode is " + aDode);
							break;
						dode = dode.getParent();						
					}
					/*
					 * If node A is in the dependent list of A, then A is the header of a loop.
					 * Otherwise, A could still be the header of a loop or just a simple predicate.
					 */
					//first make A's pdg node be a conditional (predicate) pdgnode, if it's not already.					
					if(pdgNodeOfA.getAttrib() != ..)
					{
						PDGNode oldA = pdgNodeOfA;
						pdgNodeOfA = new ConditionalPDGNode(pdgNodeOfA);
						this.replaceInGraph(pdgNodeOfAoldA);
						pdgnode.removeDependent(oldA);
						this..put(apdgNodeOfA);
						pdgnode.addDependent(pdgNodeOfA);
						curNodeInRegion = pdgNodeOfA;
					}		
					List<BlockcopyOfDependents = new ArrayList<Block>();
					copyOfDependents.addAll(dependents);
					//First, add the dependency for B and its corresponding region.
					Region regionOfB = block2region.get(b);
					PDGNode pdgnodeOfBRegion = null;
					if(!this..containsKey(regionOfB))
					{
						pdgnodeOfBRegion = new PDGNode(regionOfB..);
						this.addNode(pdgnodeOfBRegion);
						this..put(regionOfBpdgnodeOfBRegion);
					}
					else
						pdgnodeOfBRegion = this..get(regionOfB);
					//set the region hierarchy
					regionOfB.setParent(r);
					r.addChildRegion(regionOfB);
					//add the dependency edges
					this.addEdge(pdgNodeOfApdgnodeOfBRegion"dependency");
					pdgNodeOfA.addDependent(pdgnodeOfBRegion);
					regions2process.add(regionOfB);
					//now remove b and all the nodes in the same weak region from the list of dependents
					copyOfDependents.remove(b);
					copyOfDependents.removeAll(regionOfB.getBlocks());
					/* What remains here in the dependence set needs to be processed separately. For
					 * each node X remained in the dependency set, find the corresponding PDG region node
					 * and add a dependency edge from the region of B to the region of X. If X's weak 
					 * region contains other nodes not in the dependency set of A, create a new region
					 * for X and add the proper dependency edges (this actually happens if X is the header
					 * of a loop and B is a predicate guarding a break/continue.)
					 * 
					 * Note: it seems the only case that there is a node remained in the dependents is when there 
					 * is a path from b to the header of a loop. 
					 */
					while(!copyOfDependents.isEmpty())
					{
						Block depB = copyOfDependents.remove(0);
						Region rdepB = block2region.get(depB);
						/* 
						 * Actually, there are cases when depB is not the header of a loop and therefore would not dominate the current node
						 * (A) and therefore might not have been created yet. This has happened when an inner loop breaks out of the outer 
						 * loop but could have other cases too.
						 */
						PDGNode depBPDGNode = this..get(depB);
						if(depBPDGNode == null)
						{						
							//First, add the dependency for depB and its corresponding region.
							PDGNode pdgnodeOfdepBRegion = null;
							if(!this..containsKey(rdepB))
							{
								pdgnodeOfdepBRegion = new PDGNode(rdepB..);
								this.addNode(pdgnodeOfdepBRegion);
								this..put(rdepBpdgnodeOfdepBRegion);
							}
							else
								pdgnodeOfdepBRegion = this..get(rdepB);
							//set the region hierarchy
							rdepB.setParent(regionOfB);
							regionOfB.addChildRegion(rdepB);
							//add the dependency edges
							this.addEdge(pdgnodeOfBRegionpdgnodeOfdepBRegion"dependency");
							pdgnodeOfBRegion.addDependent(pdgnodeOfdepBRegion);
							regions2process.add(rdepB);
							//now remove all the nodes in the same weak region from the list of dependents
							copyOfDependents.removeAll(rdepB.getBlocks());
							continue;
						}

If all the nodes in the weak region of depB are dependent on A, then add an edge from the region of B to the region of depB. else, a new region has to be created to contain the dependences of depB, if not already created.
						if(dependents.containsAll(rdepB.getBlocks()))
						{
							/*
							 * Just add an edge to the pdg node of the existing depB region.
							 * 
							 */
							//add the dependency edges
							//First, add the dependency for depB and its corresponding region.
							PDGNode pdgnodeOfdepBRegion = null;
							if(!this..containsKey(rdepB))
							{
								pdgnodeOfdepBRegion = new PDGNode(rdepB..);
								this.addNode(pdgnodeOfdepBRegion);
								this..put(rdepBpdgnodeOfdepBRegion);
							}
							else
								pdgnodeOfdepBRegion = this..get(rdepB);
							//set the region hierarchy
							//Do not set this because the region was created before so must have the
							//proper parent already.
							//rdepB.setParent(regionOfB);
							//regionOfB.addChildRegion(rdepB);
							this.addEdge(pdgnodeOfBRegionpdgnodeOfdepBRegion"dependency");
							pdgnodeOfBRegion.addDependent(pdgnodeOfdepBRegion);
							regions2process.add(rdepB);
							//now remove all the nodes in the same weak region from the list of dependents
							copyOfDependents.removeAll(rdepB.getBlocks());
							continue;
						}
						else
						{
							PDGNode predPDGofdepB = (PDGNodethis.getPredsOf(depBPDGNode).get(0);
							assert(this..containsKey(rdepB));							
							PDGNode pdgnodeOfdepBRegion = this..get(rdepB);
							//If the loop header has not been separated from its weak region yet
							if(predPDGofdepB == pdgnodeOfdepBRegion)
							{
								/*
								 * Create a new region to represent the whole loop. In fact, this is a strong
								 * region as opposed to the weak regions that were created in the RegionAnalysis.
								 * This strong region only contains the header of the loop, A, and is dependent 
								 * on it. Also, A is dependent on this strong region as well.
								 */
								Region newRegion = new Region(this.++, topLevelRegion.getSootMethod(), topLevelRegion.getSootClass(), this.);
								newRegion.add(depB);
								this..add(newRegion);
								//toBeRemoved.add(depB);
								List<Blockblocks2BRemoved;
								if(toBeRemoved.contains(predPDGofdepB))
									blocks2BRemoved = toBeRemoved.get(predPDGofdepB);
								else
								{
									blocks2BRemoved = new ArrayList<Block>();
									toBeRemoved.put(rdepBblocks2BRemoved);
								}
								blocks2BRemoved.add(depB);
								PDGNode newpdgnode = new LoopedPDGNode(newRegion..depBPDGNode);
								this.addNode(newpdgnode);
								this..put(newRegionnewpdgnode);
								this.removeEdge(pdgnodeOfdepBRegiondepBPDGNode"dependency");
								pdgnodeOfdepBRegion.removeDependent(depBPDGNode);
								this.addEdge(pdgnodeOfdepBRegionnewpdgnode"dependency");
								this.addEdge(newpdgnodedepBPDGNode"dependency");
								pdgnodeOfdepBRegion.addDependent(newpdgnode);
								newpdgnode.addDependent(depBPDGNode);
								//If a is dependent on itself (simple loop)
								if(depB == a)
								{
									PDGNode loopBodyPDGNode = (PDGNodethis.getSuccsOf(depBPDGNode).get(0);
									this.addEdge(depBPDGNodenewpdgnode"dependency-back");
									((LoopedPDGNode)newpdgnode).setBody(loopBodyPDGNode);
									depBPDGNode.addBackDependent(newpdgnode);
									//This is needed to correctly adjust the prev/next pointers for the new loop node. We should not need
									//to adjust the old loop header node because the prev/next should not have been set previously for it.
									curNodeInRegion = newpdgnode;
								}
								else
								{
									//this is a back-dependency
									pdgnodeOfBRegion.addBackDependent(newpdgnode);
									this.addEdge(pdgnodeOfBRegionnewpdgnode"dependency-back");
									//DEtermine which dependent of the loop header is actually the loop body region
									PDGNode loopBodyPDGNode = null;
									List<PDGNodesuccessors = this.getSuccsOf(depBPDGNode);
									Iterator<PDGNodesuccItr = successors.iterator();
									while(succItr.hasNext())
									{
										PDGNode succRPDGNode = succItr.next();
										assert(succRPDGNode.getType() == ..);
										Region succR = (RegionsuccRPDGNode.getNode();
										Block h = succR.getBlocks().get(0);
										DominatorNode hdode = dom.getDode(h);
										DominatorNode adode = dom.getDode(a);
										if(dom.isDominatorOf(hdodeadode))
										{
											loopBodyPDGNode = succRPDGNode;
											break;
										}
									}
									assert(loopBodyPDGNode != null);
									((LoopedPDGNode)newpdgnode).setBody(loopBodyPDGNode);
									PDGNode prev = depBPDGNode.getPrev();
									if(prev != null)
									{
										this.removeEdge(prevdepBPDGNode"controlflow");
										this.addEdge(prevnewpdgnode"controlflow");
										prev.setNext(newpdgnode);
										newpdgnode.setPrev(prev);
										depBPDGNode.setPrev(null);
									}
									PDGNode next = depBPDGNode.getNext();
									if(next != null)
									{
										this.removeEdge(depBPDGNodenext"controlflow");
										this.addEdge(newpdgnodenext"controlflow");
										newpdgnode.setNext(next);
										next.setPrev(newpdgnode);
										depBPDGNode.setNext(null);
									}
								}
							}
							else
							{
								/*
								 * The strong region for the header has already been created and its 
								 * corresponding PDGNode exist. Just add the dependency edge.
								 */
								this.addEdge(pdgnodeOfBRegionpredPDGofdepB"dependency-back");
								//this is a back-dependency
								pdgnodeOfBRegion.addBackDependent(predPDGofdepB);
							}
						}		
					}
				}	
				/* If there is a previous node in this region, add a control flow edge to indicate the
				 * the correct direction of control flow in the region.
				 */
				if(prevPDGNodeInRegion != null)
				{
					this.addEdge(prevPDGNodeInRegioncurNodeInRegion"controlflow");
					prevPDGNodeInRegion.setNext(curNodeInRegion);
					curNodeInRegion.setPrev(prevPDGNodeInRegion);
				}
				prevPDGNodeInRegion = curNodeInRegion;
			}
			//remove all the blocks marked to be removed from the region (to change a weak region
			//to a strong region.)
			Enumeration<Regionitr1 = toBeRemoved.keys();
			while(itr1.hasMoreElements())
			{
				Region region = itr1.nextElement();
				Iterator<BlockblockItr = toBeRemoved.get(region).iterator();
				while(blockItr.hasNext())
					region.remove(blockItr.next());
			}
		}
	}
	private List<RegioncloneRegions(List<Regionweak)
	{
		List<Regionstrong = new ArrayList<Region>();
		Iterator<Regionitr = weak.iterator();
		while(itr.hasNext())
		{
			Region r = itr.next();
			strong.add((Region)r.clone());
		}
		return strong;
	}

Returns:
The Corresponding UnitGraph
	public UnitGraph getCFG()
	{
		return this.;
	}

	{
		return this.;
	}

	{
		return this.;
	}

	{
		return this..get(0);
	}

	{
		return this.;
	}
	{
		List<IRegionlist = new ArrayList<IRegion>();
		Queue<IRegiontoProcess = new LinkedList<IRegion>();
		toProcess.add(r);
		while(!toProcess.isEmpty())
		{
			IRegion reg = toProcess.poll();
			list.add(reg);
			for(Iterator<IRegionitr = reg.getChildRegions().iterator(); itr.hasNext(); )
				toProcess.add((Region)itr.next());
		}
		return list;
	}
	{
		List<IRegionlist = new ArrayList<IRegion>();			
		postorder(rlist);
		return list;
	}
	private static List<IRegionpostorder(IRegion rList<IRegionlist)
	{
		//If there are children, push the children to the stack
			for(Iterator<IRegionitr = r.getChildRegions().iterator(); itr.hasNext(); )
				postorder(itr.next(), list);
		list.add(r);
		return list;
	}

	{
		return this.;
	}

This method returns a list of regions obtained by post-order traversal of the region hierarchy. This takes advantage of the hierarchical (parent/child) information encoded within the PDGNodes at construction time; it should be noted that, we have not counted the strong regions that represent the loop header as a separate region; instead, a PDGRegion that represents both the loop header and its body are counted.

Parameters:
The root from which the traversal should begin.
Returns:
The list of regions obtained thru post-order traversal of the region hierarchy.
	{
	}
	private static Hashtable<PDGNodePDGRegionnode2Region = new Hashtable<PDGNodePDGRegion>();
	//compute the pdg region list with in post order 
	private static List<PDGRegioncomputePDGRegions(PDGNode root)
	{
		List<PDGRegionregions = new ArrayList<PDGRegion>();
		pdgpostorder(rootregions);
		return regions;
	}
	private static PDGRegion pdgpostorder(PDGNode nodeList<PDGRegionlist)
	{
		node.setVisited(true);
		PDGRegion region = null;
		{
			region = new PDGRegion(node);
			.put(noderegion);
		}
		else
			region = .get(node);
		//If there are children, push the children to the stack
		List<PDGNodedependents = node.getDependets();
		if(!dependents.isEmpty())
			for(Iterator<PDGNodeitr = dependents.iterator(); itr.hasNext(); )
			{
				PDGNode curNode = (PDGNodeitr.next();
				if(curNode.getVisited())
					continue;
				region.addPDGNode(curNode);
				if(curNode instanceof LoopedPDGNode)
				{
					PDGNode body = ((LoopedPDGNode)curNode).getBody();
					PDGRegion kid = pdgpostorder(bodylist);
					kid.setParent(region);
					region.addChildRegion(kid);
					//This sets the node from the old Region into a PDGRegion
					body.setNode(kid);
				}
				else if(curNode instanceof ConditionalPDGNode)
				{
					List<PDGNodechilds = curNode.getDependets();
					Iterator<PDGNodecondItr = childs.iterator();
					while(condItr.hasNext())
					{
						PDGNode child = (PDGNode)condItr.next();
						PDGRegion kid = pdgpostorder(childlist);
						kid.setParent(region);
						region.addChildRegion(kid);
						//This sets the node from the old Region into a PDGRegion
						child.setNode(kid);
					}
				}
			}
		list.add(region);
		return region;
	}

	public boolean dependentOn(PDGNode node1PDGNode node2)
	{
		return node2.getDependets().contains(node1);
	}

	@SuppressWarnings("unchecked")
	{
		return this.getSuccsOf(node);
		//Or return node.getDependents();
	}

	public PDGNode getPDGNode(Object cfgNode)
	{
		if(cfgNode != null && cfgNode instanceof Block)
			if(this..containsKey(cfgNode))
				return this..get(cfgNode);
		return null;
	}
	@SuppressWarnings("unchecked")
	private void replaceInGraph(PDGNode newnodePDGNode oldnode)
	{		
		this.addNode(newnode);
		List succs = graph.getSuccsOf(oldnode);
		List preds = graph.getPredsOf(oldnode);
		Iterator<Objectitr = succs.iterator();
		while(itr.hasNext())
		{
			PDGNode succ = (PDGNodeitr.next();
			List<Objectlabels = graph.getLabelsForEdges(oldnodesucc);
			for(Iterator<ObjectlabelItr = labels.iterator(); labelItr.hasNext(); )
			{
				Object label = labelItr.next();
				this.addEdge(newnodesuccnew String(label.toString()));	
			}	
		}
		itr = preds.iterator();
		while(itr.hasNext())
		{
			PDGNode pred = (PDGNodeitr.next();
			List<Objectlabels = graph.getLabelsForEdges(predoldnode);
			for(Iterator<ObjectlabelItr = labels.iterator(); labelItr.hasNext(); )
			{
				Object label = labelItr.next();
				this.addEdge(prednewnodenew String(label.toString()));
			}		
		}
		this.removeNode(oldnode);
	}
The existing removeAllEdges in the parent class seems to be throwing concurrentmodification exception most of the time. Here is a version that doesn't throw that exception.
    @SuppressWarnings("unchecked")
	public void removeAllEdges(Object fromObject to)
	{
        if (!containsAnyEdge(fromto))
            return;
            
        List labels = this.getLabelsForEdges(fromto);
        
        List lablesClone = new ArrayList();
        lablesClone.addAll(labels);
        
        for(Object label : lablesClone)
        {        
	        this.removeEdge(fromtolabel);
	    }
	}

	@SuppressWarnings("unchecked")
	public String toString()
	{
		String s = new String("\nProgram Dependence Graph for Method " + this..getMethod().getName());
		s += "\n*********CFG******** \n" + this..CFGtoString(this.true);
		s += "\n*********PDG******** \n";
		List<PDGNodeprocessed = new ArrayList<PDGNode>();
		Queue nodes = new LinkedList();
		nodes.offer(this.);
		while(nodes.peek() != null)
		{
			PDGNode node = (PDGNodenodes.remove();
			processed.add(node);
			s += "\n Begin PDGNode: " + node;
			List succs = this.getSuccsOf(node);
			s += "\n has " + succs.size() + " successors:\n";
			int i = 0;
			Iterator itr = succs.iterator();
			while(itr.hasNext())
			{
				PDGNode succ = (PDGNode)itr.next();
				List labels = this.getLabelsForEdges(nodesucc);
				s += i++;
				s += ": Edge's label: " + labels + " \n";
				s += "   Target: " + succ.toShortString();
				s += "\n";
				if(labels.get(0).equals("dependency"))
				if(!processed.contains(succ))
					nodes.offer(succ);
			}
			s += "\n End PDGNode.";
		}
		return s;
	}
New to GrepCode? Check out our FAQ X