init

darcs-hash:20050502225749-5007d-653594717a9e31c078ff4adff20564d2e7abe1c9.gz

diff --git a/Makefile b/Makefile
new file mode 100644 (file)
index 0000000..2d2a9f6
--- /dev/null
+++ b/Makefile
@@ -0,0 +1,7 @@
+cp        = lib/soot.jar:bin
+sootcp    = ${cp}:/System/Library/Frameworks/JavaVM.framework/Versions/1.4.2/Classes/classes.jar
+mainclass = edu.berkeley.cs.megacz.Test
+
+go:
+       javac -classpath lib/soot.jar -d bin `find src/ -name \*.java`
+       java -cp ${cp} edu.berkeley.cs.megacz.Transformer -outjar -cp ${sootcp} -process-dir bin -main-class ${mainclass}

diff --git a/src/edu/berkeley/cs/megacz/JArena.java b/src/edu/berkeley/cs/megacz/JArena.java
new file mode 100644 (file)
index 0000000..a9c5d9d
--- /dev/null
+++ b/src/edu/berkeley/cs/megacz/JArena.java
@@ -0,0 +1,223 @@
+package edu.berkeley.cs.megacz;
+
+import soot.*;
+import soot.util.*;
+import java.util.*;
+import soot.toolkits.scalar.*;
+import soot.jimple.*;
+import soot.toolkits.graph.*;
+import soot.*;
+import soot.jimple.*;
+import soot.toolkits.scalar.*;
+import soot.toolkits.graph.*;
+import soot.util.*;
+import java.util.*;
+
+/** Tracks which locals are definitely non-null.
+ * Author: Patrick Lam (plam@sable.mcgill.ca)
+ * Based on BranchedRefVarsAnalysis by Janus Godard (janus@place.org). */
+class JArena extends ForwardBranchedFlowAnalysis {
+
+    protected Object newInitialFlow() { return fullSet.clone(); }
+    protected Object entryInitialFlow() { return emptySet.clone(); }
+    private void addGen(Unit u, Value v) { ArraySparseSet l = (ArraySparseSet)unitToGenerateSet.get(u); l.add(v); }
+    private void addGensFor(DefinitionStmt u) {
+        Value lo = u.getLeftOp();
+        Value ro = u.getRightOp();
+        if (ro instanceof NewExpr ||
+             ro instanceof NewArrayExpr ||
+             ro instanceof NewMultiArrayExpr ||
+             ro instanceof ThisRef ||
+             ro instanceof CaughtExceptionRef)
+            addGen(u, lo);
+    }
+
+    protected void copy(Object src, Object dest) {
+        FlowSet sourceSet = (FlowSet)src, destSet = (FlowSet) dest;
+        sourceSet.copy(destSet);
+    }
+
+    protected void merge(Object src1, Object src2, Object dest) {
+        FlowSet srcSet1 = (FlowSet) src1;
+        FlowSet srcSet2 = (FlowSet) src2;
+        FlowSet destSet = (FlowSet) dest;
+        srcSet1.intersection(srcSet2, destSet);
+    }
+
+    FlowSet fullSet, emptySet;
+    FlowUniverse allRefLocals;
+    Map unitToGenerateSet;
+
+    protected void flowThrough(Object srcValue, Unit unit, List fallOut, List branchOuts) {
+        FlowSet dest;
+        FlowSet src  = (FlowSet) srcValue;
+        Unit    s    = (Unit)    unit;
+
+        // Create working set.
+        dest = (FlowSet)src.clone();
+
+        // Take out kill set.
+        Iterator boxIt = s.getDefBoxes().iterator();
+        while (boxIt.hasNext()) {
+            ValueBox box = (ValueBox) boxIt.next();
+            Value value = box.getValue();
+            if (value instanceof Local && value.getType() instanceof RefLikeType)
+                dest.remove(value);
+        }
+
+        // Perform gen.
+        dest.union((FlowSet)unitToGenerateSet.get(unit), dest);
+
+        // Handle copy statements: 
+        //    x = y && 'y' in src => add 'x' to dest
+        if (s instanceof DefinitionStmt)
+        {
+            DefinitionStmt as = (DefinitionStmt) s;
+
+            Value ro = as.getRightOp();
+
+            // extract cast argument
+            if (ro instanceof CastExpr) ro = ((CastExpr) ro).getOp();
+        
+            if (src.contains(ro) && as.getLeftOp() instanceof Local)
+                dest.add(as.getLeftOp());
+        }
+
+        // Copy the out value to the fallthrough box (don't need iterator)
+        {
+            Iterator it = fallOut.iterator();
+            while (it.hasNext()) {
+                FlowSet fs = (FlowSet) (it.next());
+                copy(dest, fs);
+            }
+        }
+        
+        // Copy the out value to all branch boxes.
+        {
+            Iterator it = branchOuts.iterator();
+            while (it.hasNext()) {
+                FlowSet fs = (FlowSet) (it.next());
+                copy(dest, fs);
+            }
+        }
+
+        // Handle if statements by patching dest sets.
+        if (unit instanceof IfStmt)
+        {
+            Value cond = ((IfStmt)unit).getCondition();
+            Value op1 = ((BinopExpr) cond).getOp1();
+            Value op2 = ((BinopExpr) cond).getOp2();
+            boolean isNeg = cond instanceof NeExpr;
+            Value toGen = null;
+
+            // case 1: opN is a local and opM is NullConstant
+            //          => opN nonnull on ne branch.
+            if (op1 instanceof Local && op2 instanceof NullConstant)
+                toGen = op1;
+
+            if (op2 instanceof Local && op1 instanceof NullConstant)
+                toGen = op2;
+
+            if (toGen != null)
+            {
+                Iterator it = null;
+
+                // if (toGen != null) goto l1: on branch, toGen nonnull.
+                if (isNeg)
+                    it = branchOuts.iterator();
+                else
+                    it = fallOut.iterator();
+
+                while(it.hasNext()) {
+                    FlowSet fs = (FlowSet) (it.next());
+                    fs.add(toGen);
+                }
+            }
+
+            // case 2: both ops are local and one op is non-null and testing equality
+            if (op1 instanceof Local && op2 instanceof Local && 
+                cond instanceof EqExpr)
+            {
+                toGen = null;
+
+                if (src.contains(op1))
+                    toGen = op2;
+                if (src.contains(op2))
+                    toGen = op1;
+
+                if (toGen != null)
+                {
+                    Iterator branchIt = branchOuts.iterator();
+                    while (branchIt.hasNext()) {
+                        FlowSet fs = (FlowSet) (branchIt.next());
+                        fs.add(toGen);
+                    }
+                }
+            }    
+        }
+    }
+
+    public JArena(UnitGraph g) {
+        super(g);
+
+        unitToGenerateSet = new HashMap();
+
+        Body b = g.getBody();
+
+        List refLocals = new LinkedList();
+
+        // set up universe, empty, full sets.
+
+        emptySet = new ArraySparseSet();
+        fullSet = new ArraySparseSet();
+
+        // Find all locals in body.
+        Iterator localIt = b.getLocals().iterator();
+        while (localIt.hasNext()) {
+            Local l = (Local)localIt.next();
+            if (l.getType() instanceof RefLikeType) fullSet.add(l);
+        }
+
+        // Create gen sets.
+        Iterator unitIt = b.getUnits().iterator();
+        while (unitIt.hasNext()) {
+            Unit u = (Unit)unitIt.next();
+            unitToGenerateSet.put(u, new ArraySparseSet());
+
+            if (u instanceof DefinitionStmt) {
+                Value lo = ((DefinitionStmt)u).getLeftOp();
+                if (lo instanceof Local && lo.getType() instanceof RefLikeType)
+                    addGensFor((DefinitionStmt)u);
+            }
+
+            Iterator boxIt = u.getUseAndDefBoxes().iterator();
+            while (boxIt.hasNext()) {
+                Value boxValue = ((ValueBox) boxIt.next()).getValue();
+                Value base = null;
+                    
+                if(boxValue instanceof InstanceFieldRef) {
+                    base = ((InstanceFieldRef) (boxValue)).getBase();
+                } else if (boxValue instanceof ArrayRef) {
+                    base = ((ArrayRef) (boxValue)).getBase();
+                } else if (boxValue instanceof InstanceInvokeExpr) {
+                    base = ((InstanceInvokeExpr) boxValue).getBase();
+                } else if (boxValue instanceof LengthExpr) {
+                    base = ((LengthExpr) boxValue).getOp();
+                } else if (u instanceof ThrowStmt) {
+                    base = ((ThrowStmt)u).getOp();
+                } else if (u instanceof MonitorStmt) {
+                    base = ((MonitorStmt)u).getOp();
+                }
+
+                if (base != null && 
+                      base instanceof Local && 
+                      base.getType() instanceof RefLikeType)
+                    addGen(u, base);
+            }
+        }
+
+        // Call superclass method to do work.
+        doAnalysis();
+    }
+}
+

diff --git a/src/edu/berkeley/cs/megacz/Test.java b/src/edu/berkeley/cs/megacz/Test.java
new file mode 100644 (file)
index 0000000..a13fd44
--- /dev/null
+++ b/src/edu/berkeley/cs/megacz/Test.java
@@ -0,0 +1,7 @@
+package edu.berkeley.cs.megacz;
+
+public class Test {
+    public static void main(String[] s) {
+        System.out.println("hello");
+    }
+}

diff --git a/src/edu/berkeley/cs/megacz/Transformer.java b/src/edu/berkeley/cs/megacz/Transformer.java
new file mode 100644 (file)
index 0000000..8cf610f
--- /dev/null
+++ b/src/edu/berkeley/cs/megacz/Transformer.java
@@ -0,0 +1,156 @@
+package edu.berkeley.cs.megacz;
+import soot.*;
+import soot.jimple.*;
+import soot.util.*;
+import java.io.*;
+import java.util.*;
+
+public class Transformer {    
+    public static void main(String[] args) 
+    {
+        if(args.length == 0)
+        {
+            System.out.println("Syntax: java ashes.examples.countgotos.Main [soot options]");
+            System.exit(0);
+        }            
+        
+        PackManager.v().getPack("jtp").add(new Transform("jtp.instrumenter", GotoInstrumenter.v()));
+
+       // Just in case, resolve the PrintStream SootClass.
+       Scene.v().addBasicClass("java.io.PrintStream",SootClass.SIGNATURES);
+        soot.Main.main(args);
+    }
+
+    static class GotoInstrumenter extends BodyTransformer {
+        private static GotoInstrumenter instance = new GotoInstrumenter();
+        private GotoInstrumenter() {}
+
+        public static GotoInstrumenter v() { return instance; }
+
+        private boolean addedFieldToMainClassAndLoadedPrintStream = false;
+        private SootClass javaIoPrintStream;
+
+        private Local addTmpRef(Body body) {
+            Local tmpRef = Jimple.v().newLocal("tmpRef", RefType.v("java.io.PrintStream"));
+            body.getLocals().add(tmpRef);
+            return tmpRef;
+        }
+     
+        private Local addTmpLong(Body body) {
+            Local tmpLong = Jimple.v().newLocal("tmpLong", LongType.v()); 
+            body.getLocals().add(tmpLong);
+            return tmpLong;
+        }
+
+        private void addStmtsToBefore(Chain units, Stmt s, SootField gotoCounter, Local tmpRef, Local tmpLong)
+        {
+            // insert "tmpRef = java.lang.System.out;" 
+            units.insertBefore(Jimple.v().newAssignStmt( 
+                                                        tmpRef, Jimple.v().newStaticFieldRef( 
+                                                                                             Scene.v().getField("<java.lang.System: java.io.PrintStream out>").makeRef())), s);
+
+            // insert "tmpLong = gotoCounter;" 
+            units.insertBefore(Jimple.v().newAssignStmt(tmpLong, 
+                                                        Jimple.v().newStaticFieldRef(gotoCounter.makeRef())), s);
+            
+            // insert "tmpRef.println(tmpLong);" 
+            SootMethod toCall = javaIoPrintStream.getMethod("void println(long)");                    
+            units.insertBefore(Jimple.v().newInvokeStmt(
+                                                        Jimple.v().newVirtualInvokeExpr(tmpRef, toCall.makeRef(), tmpLong)), s);
+        }
+
+        protected void internalTransform(Body body, String phaseName, Map options) {
+            SootClass sClass = body.getMethod().getDeclaringClass();
+            SootField gotoCounter = null;
+            boolean addedLocals = false;
+            Local tmpRef = null, tmpLong = null;
+            Chain units = body.getUnits();
+
+            System.out.println("sClass is " + sClass);
+        
+            // Add code at the end of the main method to print out the 
+            // gotoCounter (this only works in simple cases, because you may have multiple returns or System.exit()'s )
+            synchronized(this)
+                {
+                    if (!Scene.v().getMainClass().
+                        declaresMethod("void main(java.lang.String[])"))
+                        throw new RuntimeException("couldn't find main() in mainClass");
+
+                    if (addedFieldToMainClassAndLoadedPrintStream)
+                        gotoCounter = Scene.v().getMainClass().getFieldByName("gotoCount");
+                    else
+                        {
+                            // Add gotoCounter field
+                            gotoCounter = new SootField("gotoCount", LongType.v(), 
+                                                        Modifier.STATIC);
+                            Scene.v().getMainClass().addField(gotoCounter);
+
+                            javaIoPrintStream = Scene.v().getSootClass("java.io.PrintStream");
+
+                            addedFieldToMainClassAndLoadedPrintStream = true;
+                        }
+                }
+            
+            // Add code to increase goto counter each time a goto is encountered
+            {
+                boolean isMainMethod = body.getMethod().getSubSignature().equals("void main(java.lang.String[])");
+
+                Local tmpLocal = Jimple.v().newLocal("tmp", LongType.v());
+                body.getLocals().add(tmpLocal);
+                
+                Iterator stmtIt = units.snapshotIterator();
+            
+                while(stmtIt.hasNext())
+                    {
+                        Stmt s = (Stmt) stmtIt.next();
+
+                        if(s instanceof GotoStmt)
+                            {
+                                AssignStmt toAdd1 = Jimple.v().newAssignStmt(tmpLocal, 
+                                                                             Jimple.v().newStaticFieldRef(gotoCounter.makeRef()));
+                                AssignStmt toAdd2 = Jimple.v().newAssignStmt(tmpLocal,
+                                                                             Jimple.v().newAddExpr(tmpLocal, LongConstant.v(1L)));
+                                AssignStmt toAdd3 = Jimple.v().newAssignStmt(Jimple.v().newStaticFieldRef(gotoCounter.makeRef()), 
+                                                                             tmpLocal);
+
+                                // insert "tmpLocal = gotoCounter;"
+                                units.insertBefore(toAdd1, s);
+                        
+                                // insert "tmpLocal = tmpLocal + 1L;" 
+                                units.insertBefore(toAdd2, s);
+
+                                // insert "gotoCounter = tmpLocal;" 
+                                units.insertBefore(toAdd3, s);
+                            }
+                        else if (s instanceof InvokeStmt)
+                            {
+                                InvokeExpr iexpr = (InvokeExpr) ((InvokeStmt)s).getInvokeExpr();
+                                if (iexpr instanceof StaticInvokeExpr)
+                                    {
+                                        SootMethod target = ((StaticInvokeExpr)iexpr).getMethod();
+                        
+                                        if (target.getSignature().equals("<java.lang.System: void exit(int)>"))
+                                            {
+                                                if (!addedLocals)
+                                                    {
+                                                        tmpRef = addTmpRef(body); tmpLong = addTmpLong(body);
+                                                        addedLocals = true;
+                                                    }
+                                                addStmtsToBefore(units, s, gotoCounter, tmpRef, tmpLong);
+                                            }
+                                    }
+                            }
+                        else if (isMainMethod && (s instanceof ReturnStmt || s instanceof ReturnVoidStmt))
+                            {
+                                if (!addedLocals)
+                                    {
+                                        tmpRef = addTmpRef(body); tmpLong = addTmpLong(body);
+                                        addedLocals = true;
+                                    }
+                                addStmtsToBefore(units, s, gotoCounter, tmpRef, tmpLong);
+                            }
+                    }
+            }
+        }
+    }
+}