From d48a11a9b20368069386de0437a44fb9177acd98 Mon Sep 17 00:00:00 2001 From: jjenista Date: Mon, 26 Sep 2011 22:20:07 +0000 Subject: [PATCH] Incrementing on definite reach analysis --- .../src/Analysis/Disjoint/DefReachFuVal.java | 89 ++++++++++++ .../Disjoint/DefiniteReachAnalysis.java | 3 + .../Analysis/Disjoint/DefiniteReachState.java | 135 +++++++++++++++--- Robust/src/Util/JoinOpNop.java | 17 +++ Robust/src/Util/MultiViewMap.java | 37 ++++- 5 files changed, 259 insertions(+), 22 deletions(-) create mode 100644 Robust/src/Analysis/Disjoint/DefReachFuVal.java create mode 100644 Robust/src/Util/JoinOpNop.java diff --git a/Robust/src/Analysis/Disjoint/DefReachFuVal.java b/Robust/src/Analysis/Disjoint/DefReachFuVal.java new file mode 100644 index 00000000..810349f5 --- /dev/null +++ b/Robust/src/Analysis/Disjoint/DefReachFuVal.java @@ -0,0 +1,89 @@ +package Analysis.Disjoint; + +import java.util.*; + +import IR.*; +import IR.Flat.*; +import Util.*; + +//////////////////////////////////////////// +// +// This is just a logical union of the set +// of temp descriptors in a program and the +// value "unknown" to support the Fu map +// implemented in DefiniteReachState. +// +//////////////////////////////////////////// +public class DefReachFuVal { + + // When v == null, that means "unknown" + // Note, a DefReachFuVal composite itself + // can be null in the analysis state, which + // means yet a different thing (the analysis + // has not run for that pp/var yet). + TempDescriptor v; + + // use this instead of null so callers of this + // code see the meaning + public enum Val { + UNKNOWN, + } + + + public static DefReachFuVal factory( Val unknown ) { + return new DefReachFuVal( null ); + } + + public static DefReachFuVal factory( TempDescriptor v ) { + return new DefReachFuVal( v ); + } + + + private DefReachFuVal( TempDescriptor v ) { + this.v = v; + } + + + public boolean isUnknown() { + return v == null; + } + + public TempDescriptor getVar() { + assert( v != null ); + return v; + } + + + public boolean equals( Object o ) { + if( this == o ) { + return true; + } + if( o == null ) { + return false; + } + if( !(o instanceof DefReachFuVal) ) { + return false; + } + DefReachFuVal that = (DefReachFuVal) o; + if( this.v == null ) { + return that.v == null; + } + return this.v.equals( that.v ); + } + + + public int hashCode() { + if( v == null ) { + return 1; + } + return v.hashCode(); + } + + + public String toString() { + if( v == null ) { + return "UNKNOWN"; + } + return v.toString(); + } +} diff --git a/Robust/src/Analysis/Disjoint/DefiniteReachAnalysis.java b/Robust/src/Analysis/Disjoint/DefiniteReachAnalysis.java index cb69890c..5fec38af 100644 --- a/Robust/src/Analysis/Disjoint/DefiniteReachAnalysis.java +++ b/Robust/src/Analysis/Disjoint/DefiniteReachAnalysis.java @@ -15,6 +15,9 @@ public class DefiniteReachAnalysis { private Map fn2state; public DefiniteReachAnalysis() { + // a class-wide initialization + DefiniteReachState.initBuilders(); + fn2state = new HashMap(); } diff --git a/Robust/src/Analysis/Disjoint/DefiniteReachState.java b/Robust/src/Analysis/Disjoint/DefiniteReachState.java index a08b4a2b..8b64181c 100644 --- a/Robust/src/Analysis/Disjoint/DefiniteReachState.java +++ b/Robust/src/Analysis/Disjoint/DefiniteReachState.java @@ -25,16 +25,50 @@ public class DefiniteReachState { UNKNOWN, KNOWN, } - private Map rs; + private Map Rs; + // Fu (upstream) + // + // Maps a variable that points to object o0 to the + // set of variables that point to objects o1...oN + // that have a reference to o0. + private static MultiViewMapBuilder FuBuilder; + private static BitSet viewFu0; + private static BitSet viewFu1; + private MultiViewMap Fu; + + + // Fd (downstream) + + + + + // for MultiViewMaps that don't need to use the value, + // always map to this dummy + private static Object dummy = new Integer( -1234 ); + + + // call before instantiating this class + static public void initBuilders() { + FuBuilder = + new MultiViewMapBuilder( new Class[] { + TempDescriptor.class, + DefReachFuVal.class}, + new JoinOpNop() ); + viewFu0 = FuBuilder.addPartialView( 0 ); + viewFu1 = FuBuilder.addPartialView( 1 ); + FuBuilder.setCheckTypes( true ); + FuBuilder.setCheckConsistency( true ); + } + + - // Fu - // Fd public DefiniteReachState() { - rs = new HashMap(); + Rs = new HashMap(); + Fu = FuBuilder.build(); } @@ -43,12 +77,12 @@ public class DefiniteReachState { // R' := {} // R.clear(); - rs.clear(); - + Rs.clear(); for( TempDescriptor p : parameters ) { - rs.put( p, DefReachKnown.UNKNOWN ); + Rs.put( p, DefReachKnown.UNKNOWN ); } + Fu = FuBuilder.build(); } public void copy(TempDescriptor x, @@ -65,9 +99,32 @@ public class DefiniteReachState { // for each ->e: R'.put(, e); // Rs' := (Rs - ) U { | in Rs} - DefReachKnown v = rs.get( y ); - assert( v != null ); - rs.put( x, v ); + DefReachKnown valRs = Rs.get( y ); + assert( valRs != null ); + Rs.put( x, valRs ); + + // Fu' := (Fu - - <*, x>) U + // { | in Fu} U + // { | in Fu} U + // { | > in Fu} + Fu.remove( viewFu0, MultiKey.factory( x ) ); + Fu.remove( viewFu1, MultiKey.factory( x ) ); + for( MultiKey key : Fu.get( viewFu0, MultiKey.factory( y ) ).keySet() ) { + DefReachFuVal val = (DefReachFuVal) key.get( 1 ); + Fu.put( MultiKey.factory( x, val ), dummy ); + } + for( MultiKey key : Fu.get( viewFu1, MultiKey.factory( y ) ).keySet() ) { + TempDescriptor v = (TempDescriptor) key.get( 0 ); + Fu.put( MultiKey.factory( v, DefReachFuVal.factory( x ) ), dummy ); + } + for( MultiKey key : + Fu.get( viewFu1, + MultiKey.factory( DefReachFuVal.factory( DefReachFuVal.Val.UNKNOWN ) ) + ).keySet() + ) { + TempDescriptor z = (TempDescriptor) key.get( 0 ); + Fu.put( MultiKey.factory( z, DefReachFuVal.factory( x ) ), dummy ); + } } public void load(TempDescriptor x, @@ -85,7 +142,7 @@ public class DefiniteReachState { // for each ->e: R'.put(, eee!Ue); // Rs' := (Rs - ) U {} - rs.put( x, DefReachKnown.UNKNOWN ); + Rs.put( x, DefReachKnown.UNKNOWN ); } public void store(TempDescriptor x, @@ -108,7 +165,7 @@ public class DefiniteReachState { // R'.remove(view1, x); // Rs' := (Rs - ) U {} - rs.put( x, DefReachKnown.KNOWN ); + Rs.put( x, DefReachKnown.KNOWN ); } @@ -120,7 +177,7 @@ public class DefiniteReachState { // R'.remove(view1, x); // Rs' := (Rs - ) U {} - rs.put( x, DefReachKnown.UNKNOWN ); + Rs.put( x, DefReachKnown.UNKNOWN ); } public void merge( DefiniteReachState that ) { @@ -130,28 +187,64 @@ public class DefiniteReachState { mergeRs( that ); } + + /////////////////////////////////////////////////////////// + // + // This is WRONG + // + // It definitely tests the current R as well as Rs + // + // but also be careful what null means, is it actually + // equivalent to UNKOWN? I'd rather put nothing, meaning + // we have to do an analysis pass over all the incoming edges + // before there is a sensical answer. I think... private void mergeRs( DefiniteReachState that ) { // merge "that" into "this" and leave "that" unchanged Set allVars = new HashSet(); - allVars.addAll( this.rs.keySet() ); - allVars.addAll( that.rs.keySet() ); + allVars.addAll( this.Rs.keySet() ); + allVars.addAll( that.Rs.keySet() ); for( TempDescriptor x : allVars ) { - DefReachKnown vThis = this.rs.get( x ); - DefReachKnown vThat = that.rs.get( x ); + DefReachKnown vThis = this.Rs.get( x ); + DefReachKnown vThat = that.Rs.get( x ); if( vThis != null && vThis.equals( DefReachKnown.KNOWN ) && vThat != null && vThat.equals( DefReachKnown.KNOWN ) ) { - this.rs.put( x, DefReachKnown.KNOWN ); + this.Rs.put( x, DefReachKnown.KNOWN ); } else { - this.rs.put( x, DefReachKnown.UNKNOWN ); + this.Rs.put( x, DefReachKnown.UNKNOWN ); } } } + + public boolean equals( Object o ) { + if( this == o ) { + return true; + } + if( o == null ) { + return false; + } + if( !(o instanceof DefiniteReachState) ) { + return false; + } + DefiniteReachState that = (DefiniteReachState) o; + + assert( false ); + return false; + } + + + public int hashCode() { + assert( false ); + return 0; + } + + + public String toString() { StringBuilder s = new StringBuilder( "R_s = {" ); - for( TempDescriptor x : rs.keySet() ) { - s.append( " "+x+"->"+rs.get( x ) ); + for( TempDescriptor x : Rs.keySet() ) { + s.append( " "+x+"->"+Rs.get( x ) ); } s.append( "}" ); return s.toString(); diff --git a/Robust/src/Util/JoinOpNop.java b/Robust/src/Util/JoinOpNop.java new file mode 100644 index 00000000..fe602550 --- /dev/null +++ b/Robust/src/Util/JoinOpNop.java @@ -0,0 +1,17 @@ +//////////////////////////////////////////// +// +// This join op is useful for multiviewmaps +// where the multikey holds all useful values +// and the templated value of the map is ignored. +// When used this way, the multiviewmap functions +// like an indexed set of tuples. +// +//////////////////////////////////////////// + +package Util; + +public class JoinOpNop implements JoinOp { + public Object join( Object a, Object b ) { + return null; + } +} diff --git a/Robust/src/Util/MultiViewMap.java b/Robust/src/Util/MultiViewMap.java index 2cf626d0..aad5f0bb 100644 --- a/Robust/src/Util/MultiViewMap.java +++ b/Robust/src/Util/MultiViewMap.java @@ -77,6 +77,40 @@ public class MultiViewMap { return fullKey2value.size(); } + public boolean equals( Object o ) { + if( this == o ) { + return true; + } + if( o == null ) { + return false; + } + if( !(o instanceof MultiViewMap) ) { + return false; + } + MultiViewMap that = (MultiViewMap) o; + + // check whether key types and views match + if( !this.isHomogenous( that ) ) { + return false; + } + + // check contents + return fullKey2value.equals( that.fullKey2value ) && + view2partialKey2fullKeys.equals( that.view2partialKey2fullKeys ); + } + + public int hashCode() { + int hash = 1; + hash = hash*31 + keyTypes.hashCode(); + hash = hash*31 + joinOp.hashCode(); + hash = hash*31 + fullView.hashCode(); + hash = hash*31 + partialViews.hashCode(); + hash = hash*31 + fullKey2value.hashCode(); + hash = hash*31 + view2partialKey2fullKeys.hashCode(); + return hash; + } + + public void put( MultiKey fullKey, T value ) { assert( typesMatch( fullKey ) ); @@ -233,7 +267,8 @@ public class MultiViewMap { } return this.partialViews.equals( in.partialViews ) && - this.fullView.equals( in.fullView ); + this.fullView.equals( in.fullView ) && + this.joinOp.equals( in.joinOp ); } -- 2.34.1