001: package soot.jimple.toolkits.thread.mhp;
002:
003: import soot.toolkits.scalar.*;
004: import soot.toolkits.graph.*;
005: import soot.jimple.toolkits.thread.mhp.stmt.JPegStmt;
006: import soot.tagkit.*;
007: import soot.util.*;
008: import java.util.*;
009:
010: // *** USE AT YOUR OWN RISK ***
011: // May Happen in Parallel (MHP) analysis by Lin Li.
012: // This code should be treated as beta-quality code.
013: // It was written in 2003, but not incorporated into Soot until 2006.
014: // As such, it may contain incorrect assumptions about the usage
015: // of certain Soot classes.
016: // Some portions of this MHP analysis have been quality-checked, and are
017: // now used by the Transactions toolkit.
018: //
019: // -Richard L. Halpert, 2006-11-30
020:
021: public class DfsForBackEdge {
022:
023: private final Map<Object, Object> backEdges = new HashMap<Object, Object>();
024: private final Set<Object> gray = new HashSet<Object>();
025: private final Set<Object> black = new HashSet<Object>();
026: private final DominatorsFinder domFinder;
027:
028: DfsForBackEdge(Chain chain, DirectedGraph peg) {
029:
030: domFinder = new DominatorsFinder(chain, peg);
031: Iterator it = chain.iterator();
032: dfs(it, peg);
033: testBackEdge();
034: }
035:
036: private void dfs(Iterator it, DirectedGraph g) {
037:
038: // Visit each node
039: {
040:
041: while (it.hasNext()) {
042: Object s = it.next();
043: if (!gray.contains(s)) {
044:
045: visitNode(g, s);
046: }
047: }
048:
049: }
050:
051: }
052:
053: private void visitNode(DirectedGraph g, Object s) {
054: // System.out.println("s is: "+ s);
055: gray.add(s);
056: Iterator it = g.getSuccsOf(s).iterator();
057:
058: if (g.getSuccsOf(s).size() > 0) {
059: while (it.hasNext()) {
060: Object succ = it.next();
061: if (!gray.contains(succ)) {
062:
063: visitNode(g, succ);
064: } else {
065: //if the color of the node is gray, then we found a retreating edge
066: if (gray.contains(succ) && !black.contains(succ)) {
067: /* If succ is in s's dominator list,
068: * then this retreating edge is a back edge.
069: */
070: FlowSet dominators = domFinder
071: .getDominatorsOf(s);
072: if (dominators.contains(succ)) {
073: System.out.println("s is " + s);
074: System.out.println("succ is " + succ);
075: backEdges.put(s, succ);
076: }
077: }
078:
079: }
080: }
081: }
082: black.add(s);
083:
084: }
085:
086: protected Map<Object, Object> getBackEdges() {
087: return backEdges;
088: }
089:
090: private void testBackEdge() {
091: System.out.println("===test backEdges==");
092: Set maps = backEdges.entrySet();
093: for (Iterator iter = maps.iterator(); iter.hasNext();) {
094: Map.Entry entry = (Map.Entry) iter.next();
095: JPegStmt key = (JPegStmt) entry.getKey();
096: Tag tag = (Tag) key.getTags().get(0);
097: System.out.println("---key= " + tag + " " + key);
098: JPegStmt value = (JPegStmt) entry.getValue();
099: Tag tag1 = (Tag) value.getTags().get(0);
100: System.out.println("---value= " + tag1 + " " + value);
101: }
102: System.out.println("===test backEdges==end==");
103: }
104:
105: }
|