[Soot-list] patch to make HashMutablePDG not loop forever for figure 5 from cytron's SSA construction paper.

[Phil Pratt-Szeliga]

Hello,

Here is a patch to make HashMutablePDG not loop forever for figure 5
from cytron's SSA construction paper. I also made a public getter for
m_blockCFG because I need that.

My test case that caused the bug behavior is:

//////////////////////////////////////////////////////////////////////
// CytronFigure5.java
//////////////////////////////////////////////////////////////////////

package edu.syr.pcpratts.symarray.test;

public class CytronFigure5 {

  public void figure5(boolean p, boolean q, boolean r, boolean s, boolean t){
    int i = 1;
    int j = 1;
    int k = 1;
    int l = 1;
    do {
      if(p){
        j = i;
        if(q){
          l = 2;
        } else {
          l = 3;
        }
        ++k;
      } else {
        k += 2;
      }
      System.out.println("i: "+i+" j: "+j+" k: "+k+" l: "+l);
      do {
        if(r){
          l += 4;
        }
      } while(s == false);
      i += 6;
    } while(t == false);
  }
}

////////////////////////////////////////////////////////////
// The patch
////////////////////////////////////////////////////////////

diff --git a/src/soot/toolkits/graph/pdg/HashMutablePDG.java
b/src/soot/toolkits/graph/pdg/HashMutablePDG.java
--- a/src/soot/toolkits/graph/pdg/HashMutablePDG.java
+++ b/src/soot/toolkits/graph/pdg/HashMutablePDG.java
@@ -26,6 +26,8 @@
 import java.util.LinkedList;
 import java.util.List;
 import java.util.Queue;
+import java.util.Set;
+import java.util.HashSet;

 import soot.Body;
 import soot.SootClass;
@@ -36,6 +38,7 @@
 import soot.toolkits.graph.HashMutableEdgeLabelledDirectedGraph;
 import soot.toolkits.graph.UnitGraph;
 import soot.toolkits.graph.pdg.IRegion;
+import soot.toolkits.graph.DirectedGraph;


 /**
@@ -91,7 +94,6 @@
 	protected List<PDGRegion> m_pdgRegions = null;
 	private RegionAnalysis m_regionAnalysis = null;
 	private int m_strongRegionStartID;
-
 	
 	public HashMutablePDG(UnitGraph cfg)
 	{
@@ -126,6 +128,10 @@
 		this.m_startNode.setNode(r);
 		
 	}
+
+  public BlockGraph getBlockGraph(){
+    return m_blockCFG;
+  }
 	
 	/**
 	 * This is the heart of the PDG contruction. It is huge and definitely needs
@@ -153,12 +159,14 @@
 		this.m_startNode = pdgnode;
 		topLevelRegion.setParent(null);
 		
+    Set<Region> processedRegions = new HashSet<Region>();
 		regions2process.add(topLevelRegion);
 		
 		//while there's a (weak) region to process
 		while(!regions2process.isEmpty())
 		{
 			Region r = regions2process.remove(0);
+      processedRegions.add(r);
 			
 			//get the corresponding pdgnode
 			pdgnode = this.m_obj2pdgNode.get(r);
@@ -276,7 +284,9 @@
 					//add the dependency edges
 					this.addEdge(pdgNodeOfA, pdgnodeOfBRegion, "dependency");
 					pdgNodeOfA.addDependent(pdgnodeOfBRegion);
-					regions2process.add(regionOfB);
+          if(!processedRegions.contains(regionOfB)){
+					  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());
@@ -326,7 +336,9 @@
 							//add the dependency edges
 							this.addEdge(pdgnodeOfBRegion, pdgnodeOfdepBRegion, "dependency");
 							pdgnodeOfBRegion.addDependent(pdgnodeOfdepBRegion);
-							regions2process.add(rdepB);
+              if(!processedRegions.contains(rdepB)){
+							  regions2process.add(rdepB);
+              }
 							
 							//now remove all the nodes in the same weak region from the
list of dependents
 							
@@ -371,7 +383,9 @@
 							
 							this.addEdge(pdgnodeOfBRegion, pdgnodeOfdepBRegion, "dependency");
 							pdgnodeOfBRegion.addDependent(pdgnodeOfdepBRegion);
-							regions2process.add(rdepB);
+              if(!processedRegions.contains(rdepB)){
+							  regions2process.add(rdepB);
+              }
 							
 							//now remove all the nodes in the same weak region from the
list of dependents
 							
@@ -686,8 +700,11 @@
 	
 	private static PDGRegion pdgpostorder(PDGNode node, List<PDGRegion> list)
 	{
+    if(node.getVisited()){
+      return null;
+    }
 		node.setVisited(true);
-		
+
 		PDGRegion region = null;
 		if(!node2Region.containsKey(node))
 		{
@@ -696,8 +713,7 @@
 		}
 		else
 			region = node2Region.get(node);
-		
-		
+
 		//If there are children, push the children to the stack
 		List<PDGNode> dependents = node.getDependets();
 		if(!dependents.isEmpty())
@@ -713,12 +729,13 @@
 				{
 					PDGNode body = ((LoopedPDGNode)curNode).getBody();
 					PDGRegion kid = pdgpostorder(body, list);
-					kid.setParent(region);
-					region.addChildRegion(kid);
+          if(kid != null){
+					  kid.setParent(region);
+					  region.addChildRegion(kid);
 					
-					//This sets the node from the old Region into a PDGRegion
-					body.setNode(kid);
-					
+					  //This sets the node from the old Region into a PDGRegion
+					  body.setNode(kid);
+          }
 				}
 				else if(curNode instanceof ConditionalPDGNode)
 				{
@@ -728,12 +745,13 @@
 					{
 						PDGNode child = (PDGNode)condItr.next();
 						PDGRegion kid = pdgpostorder(child, list);
-						kid.setParent(region);
-						region.addChildRegion(kid);
-						//This sets the node from the old Region into a PDGRegion
+            if(kid != null){
+						  kid.setParent(region);
+						  region.addChildRegion(kid);
+						  //This sets the node from the old Region into a PDGRegion

-						child.setNode(kid);
-						
+						  child.setNode(kid);
+						}
 					}

 				}

diff --git a/src/soot/toolkits/graph/pdg/ProgramDependenceGraph.java
b/src/soot/toolkits/graph/pdg/ProgramDependenceGraph.java
--- a/src/soot/toolkits/graph/pdg/ProgramDependenceGraph.java
+++ b/src/soot/toolkits/graph/pdg/ProgramDependenceGraph.java
@@ -22,6 +22,7 @@
 import java.util.List;

 import soot.toolkits.graph.MutableEdgeLabelledDirectedGraph;
+import soot.toolkits.graph.BlockGraph;


 /**
@@ -60,6 +61,8 @@
 	 * @return The root region of the PDG.
 	 */
 	public IRegion GetStartRegion();
+
+  public BlockGraph getBlockGraph();
 	
 	/**
 	 * @return The root node of the PDG, which is essentially the same
as the start region



Phil Pratt-Szeliga
Syracuse University