From f0b01b967f4ae1974eff877aee851db287086f20 Mon Sep 17 00:00:00 2001
From: jjenista <jjenista>
Date: Tue, 19 Feb 2008 22:23:09 +0000
Subject: [PATCH] Updated CallGraph to keep an inverse map (callee->caller set)
---
Robust/src/Analysis/CallGraph/CallGraph.java | 135 +++++++++++++++---
Robust/src/Tests/CallGraph/makefile | 26 ++++
Robust/src/Tests/CallGraph/reduceDotFile | 24 ++++
Robust/src/Tests/CallGraph/testCallGraph.java | 44 ++++++
4 files changed, 209 insertions(+), 20 deletions(-)
create mode 100644 Robust/src/Tests/CallGraph/makefile
create mode 100755 Robust/src/Tests/CallGraph/reduceDotFile
create mode 100644 Robust/src/Tests/CallGraph/testCallGraph.java
diff --git a/Robust/src/Analysis/CallGraph/CallGraph.java b/Robust/src/Analysis/CallGraph/CallGraph.java
index 72c0232e..772e8157 100644
--- a/Robust/src/Analysis/CallGraph/CallGraph.java
+++ b/Robust/src/Analysis/CallGraph/CallGraph.java
@@ -4,25 +4,38 @@ import IR.Flat.FlatMethod;
import IR.Flat.FlatNode;
import IR.Flat.FlatCall;
import IR.Flat.FKind;
-import java.util.*;
+import IR.Descriptor;
import IR.ClassDescriptor;
import IR.MethodDescriptor;
+import IR.TaskDescriptor;
import IR.TypeDescriptor;
+import java.util.*;
+import java.io.*;
public class CallGraph {
- State state;
- Hashtable methods;
- Hashtable methodmap;
+ private State state;
+
+ // MethodDescriptor maps to HashSet<MethodDescriptor>
+ private Hashtable mapVirtual2ImplementationSet;
+
+ // MethodDescriptor or TaskDescriptor maps to HashSet<MethodDescriptor>
+ private Hashtable mapCaller2CalleeSet;
+
+ // MethodDescriptor maps to HashSet<MethodDescriptor or TaskDescriptor>
+ private Hashtable mapCallee2CallerSet;
public CallGraph(State state) {
this.state=state;
- methods=new Hashtable();
- methodmap=new Hashtable();
- buildMethodTable();
+ mapVirtual2ImplementationSet = new Hashtable();
+ mapCaller2CalleeSet = new Hashtable();
+ mapCallee2CallerSet = new Hashtable();
+ buildVirtualMap();
buildGraph();
}
- private void buildMethodTable() {
+ // build a mapping of virtual methods to all
+ // possible implementations of that method
+ private void buildVirtualMap() {
//Iterator through classes
Iterator it=state.getClassSymbolTable().getDescriptorsIterator();
while(it.hasNext()) {
@@ -40,9 +53,9 @@ public class CallGraph {
for(Iterator matchit=possiblematches.iterator();matchit.hasNext();) {
MethodDescriptor matchmd=(MethodDescriptor)matchit.next();
if (md.matches(matchmd)) {
- if (!methods.containsKey(matchmd))
- methods.put(matchmd,new HashSet());
- ((HashSet)methods.get(matchmd)).add(md);
+ if (!mapVirtual2ImplementationSet.containsKey(matchmd))
+ mapVirtual2ImplementationSet.put(matchmd,new HashSet());
+ ((HashSet)mapVirtual2ImplementationSet.get(matchmd)).add(md);
break;
}
}
@@ -51,7 +64,6 @@ public class CallGraph {
}
}
-
public Set getMethods(MethodDescriptor md, TypeDescriptor type) {
return getMethods(md);
}
@@ -61,7 +73,7 @@ public class CallGraph {
public Set getMethods(MethodDescriptor md) {
HashSet ns=new HashSet();
ns.add(md);
- Set s=(Set)methods.get(md);
+ Set s=(Set)mapVirtual2ImplementationSet.get(md);
if (s!=null)
for(Iterator it=s.iterator();it.hasNext();) {
MethodDescriptor md2=(MethodDescriptor)it.next();
@@ -75,7 +87,7 @@ public class CallGraph {
public Set getMethodCalls(MethodDescriptor md) {
HashSet ns=new HashSet();
ns.add(md);
- Set s=(Set)methodmap.get(md);
+ Set s=(Set)mapCaller2CalleeSet.get(md);
if (s!=null)
for(Iterator it=s.iterator();it.hasNext();) {
MethodDescriptor md2=(MethodDescriptor)it.next();
@@ -92,13 +104,17 @@ public class CallGraph {
//Iterator through methods
while(methodit.hasNext()) {
MethodDescriptor md=(MethodDescriptor)methodit.next();
- analyzeMethod(md);
+ analyzeMethod( (Object)md, state.getMethodFlat(md) );
}
}
+ it=state.getTaskSymbolTable().getDescriptorsIterator();
+ while(it.hasNext()) {
+ TaskDescriptor td=(TaskDescriptor)it.next();
+ analyzeMethod( (Object)td, state.getMethodFlat(td) );
+ }
}
- private void analyzeMethod(MethodDescriptor md) {
- FlatMethod fm=state.getMethodFlat(md);
+ private void analyzeMethod(Object caller, FlatMethod fm) {
HashSet toexplore=new HashSet();
toexplore.add(fm);
HashSet explored=new HashSet();
@@ -117,10 +133,89 @@ public class CallGraph {
MethodDescriptor calledmethod=fc.getMethod();
Set methodsthatcouldbecalled=fc.getThis()==null?getMethods(calledmethod):
getMethods(calledmethod, fc.getThis().getType());
- if (!methodmap.containsKey(md))
- methodmap.put(md,new HashSet());
- ((HashSet)methodmap.get(md)).addAll(methodsthatcouldbecalled);
+
+ // add caller -> callee maps
+ if( !mapCaller2CalleeSet.containsKey( caller ) ) {
+ mapCaller2CalleeSet.put( caller, new HashSet() );
+ }
+ ((HashSet)mapCaller2CalleeSet.get( caller )).addAll( methodsthatcouldbecalled );
+
+ // add callee -> caller maps
+ Iterator calleeItr = methodsthatcouldbecalled.iterator();
+ while( calleeItr.hasNext() ) {
+ MethodDescriptor callee = (MethodDescriptor) calleeItr.next();
+ if( !mapCallee2CallerSet.containsKey( callee ) ) {
+ mapCallee2CallerSet.put( callee, new HashSet() );
+ }
+ ((HashSet)mapCallee2CallerSet.get( callee )).add( caller );
+ }
+ }
+ }
+ }
+
+ public void writeToDot( String graphName ) throws java.io.IOException {
+ // each task or method only needs to be labeled once
+ // in a dot file
+ HashSet labeledInDot = new HashSet();
+
+ // write out the call graph using the callees mapping
+ BufferedWriter bw = new BufferedWriter( new FileWriter( graphName+"byCallees.dot" ) );
+ bw.write( "digraph "+graphName+"byCallees {\n" );
+ Iterator mapItr = mapCallee2CallerSet.entrySet().iterator();
+ while( mapItr.hasNext() ) {
+ Map.Entry me = (Map.Entry) mapItr.next();
+ MethodDescriptor callee = (MethodDescriptor) me.getKey();
+ HashSet callerSet = (HashSet) me.getValue();
+
+ if( !labeledInDot.contains( callee ) ) {
+ labeledInDot.add( callee );
+ bw.write( " " + callee.getNum() + "[label=\"" + callee + "\"];\n" );
+ }
+
+ Iterator callerItr = callerSet.iterator();
+ while( callerItr.hasNext() ) {
+ Descriptor caller = (Descriptor) callerItr.next();
+
+ if( !labeledInDot.contains( caller ) ) {
+ labeledInDot.add( caller );
+ bw.write( " " + caller.getNum() + "[label=\"" + caller + "\"];\n" );
+ }
+
+ bw.write( " " + callee.getNum() + "->" + caller.getNum() + ";\n" );
+ }
+ }
+ bw.write( "}\n" );
+ bw.close();
+
+ // write out the call graph (should be equivalent) by
+ // using the callers mapping
+ labeledInDot = new HashSet();
+ bw = new BufferedWriter( new FileWriter( graphName+"byCallers.dot" ) );
+ bw.write( "digraph "+graphName+"byCallers {\n" );
+ mapItr = mapCaller2CalleeSet.entrySet().iterator();
+ while( mapItr.hasNext() ) {
+ Map.Entry me = (Map.Entry) mapItr.next();
+ Descriptor caller = (Descriptor) me.getKey();
+ HashSet calleeSet = (HashSet) me.getValue();
+
+ if( !labeledInDot.contains( caller ) ) {
+ labeledInDot.add( caller );
+ bw.write( " " + caller.getNum() + "[label=\"" + caller + "\"];\n" );
+ }
+
+ Iterator calleeItr = calleeSet.iterator();
+ while( calleeItr.hasNext() ) {
+ MethodDescriptor callee = (MethodDescriptor) calleeItr.next();
+
+ if( !labeledInDot.contains( callee ) ) {
+ labeledInDot.add( callee );
+ bw.write( " " + callee.getNum() + "[label=\"" + callee + "\"];\n" );
+ }
+
+ bw.write( " " + callee.getNum() + "->" + caller.getNum() + ";\n" );
}
}
+ bw.write( "}\n" );
+ bw.close();
}
}
diff --git a/Robust/src/Tests/CallGraph/makefile b/Robust/src/Tests/CallGraph/makefile
new file mode 100644
index 00000000..6c6a6fdc
--- /dev/null
+++ b/Robust/src/Tests/CallGraph/makefile
@@ -0,0 +1,26 @@
+PROGRAM=testCallGraph
+
+SOURCE_FILES=testCallGraph.java
+
+BUILDSCRIPT=~/research/Robust/src/buildscript
+BSFLAGS= -recover -taskstate -webinterface -ownership
+
+all: $(PROGRAM).bin
+
+view: PNGs
+ eog *.png &
+
+PNGs: DOTs
+ d2p *.dot
+
+DOTs: $(PROGRAM).bin
+
+$(PROGRAM).bin: $(SOURCE_FILES)
+ $(BUILDSCRIPT) $(BSFLAGS) -o $(PROGRAM) $(SOURCE_FILES)
+
+clean:
+ rm -f $(PROGRAM).bin
+ rm -fr tmpbuilddirectory
+ rm -f *~
+ rm -f *.dot
+ rm -f *.png
diff --git a/Robust/src/Tests/CallGraph/reduceDotFile b/Robust/src/Tests/CallGraph/reduceDotFile
new file mode 100755
index 00000000..14dfdb97
--- /dev/null
+++ b/Robust/src/Tests/CallGraph/reduceDotFile
@@ -0,0 +1,24 @@
+#!/bin/bash
+
+echo 'Removing all entries in call graph dot files without'
+echo 'the prefix CGTest...'
+
+for dfile in `ls *.dot`
+do
+
+# we definitely want the first line of
+# the dot file, so just send it to the
+# temporary file
+sed -n '1,1 p' <$dfile >$dfile.temp
+
+# now take only the directed edge statements
+# from the dot file that have the pattern CGtest
+sed -n '/CGTest/ p' <$dfile >>$dfile.temp
+
+# then throw the closing bracket at the end
+echo '}' >>$dfile.temp
+
+# and then clobber the old file
+mv $dfile.temp $dfile
+done
+
diff --git a/Robust/src/Tests/CallGraph/testCallGraph.java b/Robust/src/Tests/CallGraph/testCallGraph.java
new file mode 100644
index 00000000..fe8c632e
--- /dev/null
+++ b/Robust/src/Tests/CallGraph/testCallGraph.java
@@ -0,0 +1,44 @@
+public class CGTestParam {
+ flag w;
+ int a, b;
+ public CGTestParam() { a = 0; b = 0; }
+ public void CGTestFoo() {}
+ public void CGTestBar() {}
+}
+
+public class CGTestParamChild1 extends CGTestParam {
+ flag x;
+ public CGTestParamChild1() {}
+ public void CGTestBar() {}
+}
+
+public class CGTestParamChild2 extends CGTestParam {
+ flag y;
+ public CGTestParamChild2() {}
+ public void CGTestFoo() {}
+ public void CGTestBar() {}
+}
+
+task Startup( StartupObject s{ initialstate } ) {
+ CGTestParam p = new CGTestParam(){!w};
+ taskexit( s{ !initialstate } );
+}
+
+task CGTestTask1( CGTestParam p{!w} ) {
+ p.CGTestFoo();
+ CGTestParamChild1 p1 = new CGTestParamChild1(){!x};
+ CGTestParamChild2 p2 = new CGTestParamChild2(){!y};
+ taskexit( p{w} );
+}
+
+task CGTestTask2( CGTestParamChild1 p{!x} ) {
+ p.CGTestFoo();
+ p.CGTestBar();
+ taskexit( p{x} );
+}
+
+task CGTestTask3( CGTestParamChild2 p{!y} ) {
+ p.CGTestFoo();
+ p.CGTestBar();
+ taskexit( p{y} );
+}
--
2.34.1