From 40beaa760457126a337cdae483e2ca17edeeb106 Mon Sep 17 00:00:00 2001 From: jjenista Date: Mon, 16 May 2011 22:32:57 +0000 Subject: [PATCH] Create analysis model for string literals in disjointness analysis that supports checking allocation sites at runtime --- .../Analysis/Disjoint/DisjointAnalysis.java | 119 ++++++++++++------ .../src/Analysis/Disjoint/HeapAnalysis.java | 3 +- Robust/src/Analysis/Disjoint/ReachGraph.java | 34 ++++- Robust/src/Analysis/Pointer/Pointer.java | 4 +- Robust/src/Benchmarks/oooJava/master-makefile | 15 ++- .../src/IR/Flat/BCXallocsiteObjectField.java | 34 ++--- 6 files changed, 146 insertions(+), 63 deletions(-) diff --git a/Robust/src/Analysis/Disjoint/DisjointAnalysis.java b/Robust/src/Analysis/Disjoint/DisjointAnalysis.java index 802a6ca0..c8bde2d8 100644 --- a/Robust/src/Analysis/Disjoint/DisjointAnalysis.java +++ b/Robust/src/Analysis/Disjoint/DisjointAnalysis.java @@ -362,6 +362,9 @@ public class DisjointAnalysis implements HeapAnalysis { public Alloc getNewStringLiteralAlloc() { return newStringLiteralAlloc; } + public Alloc getNewStringLiteralBytesAlloc() { + return newStringLiteralBytesAlloc; + } /////////////////////////////////////////// // @@ -573,11 +576,70 @@ public class DisjointAnalysis implements HeapAnalysis { protected FlatNew constructedCmdLineArgNew; protected FlatNew constructedCmdLineArgBytesNew; - // similar to above, the runtime allocates new strings // for literal nodes, so make up an alloc to model that - protected TypeDescriptor strLiteralType; protected AllocSite newStringLiteralAlloc; + protected AllocSite newStringLiteralBytesAlloc; + + // both of the above need the descriptor of the field + // for the String's value field to reference by the + // byte array from the string object + protected TypeDescriptor stringType; + protected TypeDescriptor stringBytesType; + protected FieldDescriptor stringBytesField; + + + protected void initImplicitStringsModel() { + + ClassDescriptor cdString = typeUtil.getClass( typeUtil.StringClass ); + assert cdString != null; + + + stringType = + new TypeDescriptor( cdString ); + + stringBytesType = + new TypeDescriptor(TypeDescriptor.CHAR).makeArray( state ); + + + stringBytesField = null; + Iterator sFieldsItr = cdString.getFields(); + while( sFieldsItr.hasNext() ) { + FieldDescriptor fd = (FieldDescriptor) sFieldsItr.next(); + if( fd.getSymbol().equals( typeUtil.StringClassValueField ) ) { + stringBytesField = fd; + break; + } + } + assert stringBytesField != null; + + + TempDescriptor throwAway1 = + new TempDescriptor("stringLiteralTemp_dummy1", + stringType + ); + FlatNew fnStringLiteral = + new FlatNew(stringType, + throwAway1, + false // is global + ); + newStringLiteralAlloc + = getAllocSiteFromFlatNewPRIVATE( fnStringLiteral ); + + + TempDescriptor throwAway2 = + new TempDescriptor("stringLiteralTemp_dummy2", + stringBytesType + ); + FlatNew fnStringLiteralBytes = + new FlatNew(stringBytesType, + throwAway2, + false // is global + ); + newStringLiteralBytesAlloc + = getAllocSiteFromFlatNewPRIVATE( fnStringLiteralBytes ); + } + @@ -756,6 +818,8 @@ public class DisjointAnalysis implements HeapAnalysis { ReachGraph.typeUtil = typeUtil; ReachGraph.state = state; + ReachGraph.initOutOfScopeTemps(); + ReachGraph.debugCallSiteVisitStartCapture = state.DISJOINTDEBUGCALLVISITTOSTART; @@ -770,27 +834,14 @@ public class DisjointAnalysis implements HeapAnalysis { - if( suppressOutput ) { System.out.println("* Running disjoint reachability analysis with output suppressed! *"); } - allocateStructures(); - // model the implicit alloction site for new string literals - strLiteralType = new TypeDescriptor( typeUtil.getClass( typeUtil.StringClass ) ); - TempDescriptor throwAway = - new TempDescriptor("stringLiteralTemp_dummy", - strLiteralType - ); - FlatNew fnStringLiteral = - new FlatNew(strLiteralType, - throwAway, - false // is global - ); - newStringLiteralAlloc - = getAllocSiteFromFlatNewPRIVATE( fnStringLiteral ); + allocateStructures(); + initImplicitStringsModel(); @@ -1516,9 +1567,11 @@ public class DisjointAnalysis implements HeapAnalysis { // care about references to literals. FlatLiteralNode fln = (FlatLiteralNode) fn; - if( fln.getType().equals( strLiteralType ) ) { - rg.assignTempEqualToNewAlloc( fln.getDst(), - newStringLiteralAlloc ); + if( fln.getType().equals( stringType ) ) { + rg.assignTempEqualToStringLiteral( fln.getDst(), + newStringLiteralAlloc, + newStringLiteralBytesAlloc, + stringBytesField ); } break; @@ -1570,7 +1623,7 @@ public class DisjointAnalysis implements HeapAnalysis { // all this jimma jamma to debug call sites is WELL WORTH the - // effort, so many bugs or buggy info goes crazy through call + // effort, so so so many bugs or buggy info appears through call // sites boolean debugCallSite = false; if( state.DISJOINTDEBUGCALLEE != null && @@ -1706,6 +1759,8 @@ public class DisjointAnalysis implements HeapAnalysis { ); } + + ReachGraph rgMergeOfPossibleCallers = new ReachGraph(); Iterator mdItr = setPossibleCallees.iterator(); @@ -2036,7 +2091,7 @@ public class DisjointAnalysis implements HeapAnalysis { mods.addModifier(Modifiers.STATIC); TypeDescriptor returnType = new TypeDescriptor(TypeDescriptor.VOID); - + this.mdAnalysisEntry = new MethodDescriptor(mods, returnType, @@ -2095,35 +2150,21 @@ public class DisjointAnalysis implements HeapAnalysis { sizeBytes ); - TypeDescriptor typeBytes = - new TypeDescriptor(TypeDescriptor.CHAR).makeArray( state ); TempDescriptor strBytes = new TempDescriptor("analysisEntryTemp_strBytes", - typeBytes + stringBytesType ); FlatNew fnBytes = - new FlatNew(typeBytes, + new FlatNew(stringBytesType, strBytes, //sizeBytes, false // is global ); this.constructedCmdLineArgBytesNew = fnBytes; - ClassDescriptor cdString = argType.getClassDesc(); - assert cdString != null; - FieldDescriptor argBytes = null; - Iterator sFieldsItr = cdString.getFields(); - while( sFieldsItr.hasNext() ) { - FieldDescriptor fd = (FieldDescriptor) sFieldsItr.next(); - if( fd.getSymbol().equals( typeUtil.StringClassValueField ) ) { - argBytes = fd; - break; - } - } - assert argBytes != null; FlatSetFieldNode fsf = new FlatSetFieldNode(anArg, - argBytes, + stringBytesField, strBytes ); diff --git a/Robust/src/Analysis/Disjoint/HeapAnalysis.java b/Robust/src/Analysis/Disjoint/HeapAnalysis.java index 04b96a9c..53c816d1 100644 --- a/Robust/src/Analysis/Disjoint/HeapAnalysis.java +++ b/Robust/src/Analysis/Disjoint/HeapAnalysis.java @@ -27,7 +27,8 @@ public interface HeapAnalysis { // similar to above, new string literals have a runtime alloc site (not in // code explicitly) so make one in your model and return it here - public Alloc getNewStringLiteralAlloc(); // a String + public Alloc getNewStringLiteralAlloc(); // a String + public Alloc getNewStringLiteralBytesAlloc();// an array of char // Use these methods to find out what allocation sites diff --git a/Robust/src/Analysis/Disjoint/ReachGraph.java b/Robust/src/Analysis/Disjoint/ReachGraph.java index 2e16ad1f..6eedd6ba 100644 --- a/Robust/src/Analysis/Disjoint/ReachGraph.java +++ b/Robust/src/Analysis/Disjoint/ReachGraph.java @@ -12,8 +12,18 @@ public class ReachGraph { protected static final boolean DISABLE_STRONG_UPDATES = false; protected static final boolean DISABLE_GLOBAL_SWEEP = false; - // a special out-of-scope temp - protected static final TempDescriptor tdReturn = new TempDescriptor("_Return___"); + // a special out-of-scope temps + protected static TempDescriptor tdReturn; + protected static TempDescriptor tdStrLiteralBytes; + + public static void initOutOfScopeTemps() { + tdReturn = new TempDescriptor("_Return___"); + + tdStrLiteralBytes = + new TempDescriptor("_strLiteralBytes___", + new TypeDescriptor(TypeDescriptor.CHAR).makeArray( state ) + ); + } // predicate constants public static final ExistPred predTrue = ExistPred.factory(); // if no args, true @@ -380,6 +390,26 @@ public class ReachGraph { // //////////////////////////////////////////////////// + public void assignTempEqualToStringLiteral(TempDescriptor x, + AllocSite asStringLiteral, + AllocSite asStringLiteralBytes, + FieldDescriptor fdStringBytesField) { + // model this to get points-to information right for + // pointers to string literals, even though it doesn't affect + // reachability paths in the heap + assignTempEqualToNewAlloc( x, + asStringLiteral ); + + assignTempEqualToNewAlloc( tdStrLiteralBytes, + asStringLiteralBytes ); + + assignTempXFieldFEqualToTempY( x, + fdStringBytesField, + tdStrLiteralBytes, + null ); + } + + public void assignTempXEqualToTempY(TempDescriptor x, TempDescriptor y) { assignTempXEqualToCastedTempY(x, y, null); diff --git a/Robust/src/Analysis/Pointer/Pointer.java b/Robust/src/Analysis/Pointer/Pointer.java index 2c76a76d..4947b959 100644 --- a/Robust/src/Analysis/Pointer/Pointer.java +++ b/Robust/src/Analysis/Pointer/Pointer.java @@ -2108,7 +2108,9 @@ nextdelta: public Alloc getNewStringLiteralAlloc() { return null; } - + public Alloc getNewStringLiteralBytesAlloc() { + return null; + } public Set canPointToAt( TempDescriptor x, FlatNode programPoint ) { diff --git a/Robust/src/Benchmarks/oooJava/master-makefile b/Robust/src/Benchmarks/oooJava/master-makefile index 0e81a39b..debd68cf 100644 --- a/Robust/src/Benchmarks/oooJava/master-makefile +++ b/Robust/src/Benchmarks/oooJava/master-makefile @@ -40,7 +40,7 @@ RCRDEBUGV= -rcr_debug_verbose -printlinenum BSFLAGS= -64bit -mainclass $(PROGRAM) -heapsize-mb 5000 -garbagestats -joptimize -noloop -optimize -nolock -debug #-nooptimize #src-after-pp -CHECKPOINTSTO= -disjoint -printlinenum -pointsto-check-v-runtime #-disjoint-write-dots final +CHECKPOINTSTO= -printlinenum -pointsto-check-v-runtime DRELEASEMODE=-disjoint-release-mode -disjoint-dvisit-stack-callees-on-top -disjoint-alias-file aliases.txt tabbed @@ -76,13 +76,16 @@ DISJOINT= -disjoint -disjoint-k 1 -enable-assertions $(DRELEASEMODE) #-disjoint- # EX: (skip first 10 visits, capture the next 3, then halt) # -disjoint-debug-snap-method Remove 10 3 true -DISJOINTDEBUG= -justanalyze -disjoint -disjoint-k 1 -enable-assertions -# -disjoint-write-dots final \ -# -disjoint-debug-callsite Demand.add Lateral.compute 1 1000 true +DISJOINTDEBUG= -disjoint -disjoint-k 1 -enable-assertions \ + -disjoint-write-dots final \ + -flatirusermethods +# -disjoint-debug-callsite String.valueOf Power.main 1 1000 true \ +# -justanalyze # -disjoint-desire-determinism +# -disjoint-debug-callsite Demand.add Lateral.compute 1 1000 true # -disjoint-debug-snap-method ComputeCenterOfMass 6 2 true # -disjoint-debug-scheduling -# -flatirusermethods + @@ -106,7 +109,7 @@ $(PROGRAM)s.bin: $(SOURCE_FILES) ../master-makefile check-pointsto: $(PROGRAM)c.bin $(PROGRAM)c.bin: $(SOURCE_FILES) ../master-makefile - $(BUILDSCRIPT) $(BMFLAGS) $(BSFLAGS) $(USECOREPROF) $(CHECKPOINTSTO) -o $(PROGRAM)c -builddir chk $(SOURCE_FILES) + $(BUILDSCRIPT) $(BMFLAGS) $(BSFLAGS) $(USECOREPROF) $(DISJOINTDEBUG) $(CHECKPOINTSTO) -o $(PROGRAM)c -builddir chk $(SOURCE_FILES) diff --git a/Robust/src/IR/Flat/BCXallocsiteObjectField.java b/Robust/src/IR/Flat/BCXallocsiteObjectField.java index 3d33ad25..03312575 100644 --- a/Robust/src/IR/Flat/BCXallocsiteObjectField.java +++ b/Robust/src/IR/Flat/BCXallocsiteObjectField.java @@ -21,7 +21,7 @@ public class BCXallocsiteObjectField implements BuildCodeExtension { protected HeapAnalysis heapAnalysis; protected ClassDescriptor cdString; - protected FieldDescriptor argBytes; + protected FieldDescriptor strBytes; public BCXallocsiteObjectField( BuildCode buildCode, @@ -30,31 +30,30 @@ public class BCXallocsiteObjectField implements BuildCodeExtension { this.buildCode = buildCode; this.typeUtil = typeUtil; this.heapAnalysis = heapAnalysis; - } - - - public void additionalClassObjectFields(PrintWriter outclassdefs) { - outclassdefs.println(" int allocsite;"); - } - - - public void additionalCodeForCommandLineArgs(PrintWriter outmethod, String argsVar) { cdString = typeUtil.getClass( typeUtil.StringClass ); assert cdString != null; - argBytes = null; + strBytes = null; Iterator sFieldsItr = cdString.getFields(); while( sFieldsItr.hasNext() ) { FieldDescriptor fd = (FieldDescriptor) sFieldsItr.next(); if( fd.getSymbol().equals( typeUtil.StringClassValueField ) ) { - argBytes = fd; + strBytes = fd; break; } } - assert argBytes != null; + assert strBytes != null; + } + + + public void additionalClassObjectFields(PrintWriter outclassdefs) { + outclassdefs.println(" int allocsite;"); + } + public void additionalCodeForCommandLineArgs(PrintWriter outmethod, String argsVar) { + String argsAccess = "((struct "+cdString.getSafeSymbol()+ " **)(((char *)& "+argsVar+"->___length___)+sizeof(int)))"; @@ -70,7 +69,7 @@ public class BCXallocsiteObjectField implements BuildCodeExtension { ";" ); outmethod.println(" "+argsAccess+"[i]->"+ - argBytes.getSafeSymbol()+ + strBytes.getSafeSymbol()+ "->allocsite = "+ heapAnalysis.getCmdLineArgBytesAlloc().getUniqueAllocSiteID()+ ";" @@ -94,6 +93,13 @@ public class BCXallocsiteObjectField implements BuildCodeExtension { heapAnalysis.getNewStringLiteralAlloc().getUniqueAllocSiteID()+ ";" ); + + output.println(dstVar+"->"+ + strBytes.getSafeSymbol()+ + "->allocsite = "+ + heapAnalysis.getNewStringLiteralBytesAlloc().getUniqueAllocSiteID()+ + ";" + ); } -- 2.34.1