From b124b7bf09a5eed6e272119acba9cfc5a1374b60 Mon Sep 17 00:00:00 2001 From: yeom Date: Sat, 13 Aug 2011 01:28:26 +0000 Subject: [PATCH] 1) allow to set the maximum threshold for the liveness analysis. if threashold is set to -1, there is no threshold. 2) bug fix on CSE --- Robust/src/Analysis/Liveness.java | 13 ++++++---- .../Analysis/Locality/DelayComputation.java | 10 ++++---- .../Analysis/Locality/DiscoverConflicts.java | 4 +-- .../Analysis/Locality/LocalityAnalysis.java | 4 +-- Robust/src/Analysis/Loops/CSE.java | 19 +++++++++++--- .../src/Analysis/Loops/CopyPropagation.java | 25 +++++++++++++------ Robust/src/Analysis/Loops/UseDef.java | 2 +- Robust/src/Analysis/Pointer/Pointer.java | 2 +- 8 files changed, 52 insertions(+), 27 deletions(-) diff --git a/Robust/src/Analysis/Liveness.java b/Robust/src/Analysis/Liveness.java index b4b3a8dc..1374b24e 100644 --- a/Robust/src/Analysis/Liveness.java +++ b/Robust/src/Analysis/Liveness.java @@ -13,10 +13,10 @@ public class Liveness { /* This methods takes in a FlatMethod and returns a map from a * FlatNode to the set of temps that are live into the FlatNode.*/ - public static Hashtable> computeLiveTemps(FlatMethod fm) { - return computeLiveTemps(fm, null); + public static Hashtable> computeLiveTemps(FlatMethod fm, int threshold) { + return computeLiveTemps(fm, null, threshold); } - public static Hashtable> computeLiveTemps(FlatMethod fm, LocalityBinding lb) { + public static Hashtable> computeLiveTemps(FlatMethod fm, LocalityBinding lb, int threshold) { Hashtable> nodetotemps=new Hashtable>(); Set toprocess=fm.getNodeSet(); @@ -42,6 +42,9 @@ public class Liveness { if (!nodetotemps.containsKey(fn)|| !nodetotemps.get(fn).equals(tempset)) { nodetotemps.put(fn, tempset); + if(threshold!=-1 && nodetotemps.size()>threshold){ + return null; + } for(int i=0; i> computeLiveOut(FlatMethod fm, LocalityBinding lb) { - Hashtable> liveinmap=computeLiveTemps(fm, lb); + Hashtable> liveinmap=computeLiveTemps(fm, lb,-1); Hashtable> liveoutmap=new Hashtable>(); for(Iterator fnit=fm.getNodeSet().iterator(); fnit.hasNext();) { @@ -88,7 +91,7 @@ public class Liveness { public Set getLiveInTemps( FlatMethod fm, FlatNode fn ) { if( !fm2liveMap.containsKey( fm ) ) { - fm2liveMap.put( fm, Liveness.computeLiveTemps( fm ) ); + fm2liveMap.put( fm, Liveness.computeLiveTemps( fm,-1 ) ); } return fm2liveMap.get( fm ).get( fn ); } diff --git a/Robust/src/Analysis/Locality/DelayComputation.java b/Robust/src/Analysis/Locality/DelayComputation.java index d032cfae..2d9cbe10 100644 --- a/Robust/src/Analysis/Locality/DelayComputation.java +++ b/Robust/src/Analysis/Locality/DelayComputation.java @@ -199,7 +199,7 @@ public class DelayComputation { Set liveinto=new HashSet(); - Hashtable>> reachingdefs=ReachingDefs.computeReachingDefs(fm, Liveness.computeLiveTemps(fm), true); + Hashtable>> reachingdefs=ReachingDefs.computeReachingDefs(fm, Liveness.computeLiveTemps(fm,-1), true); for(Iterator fnit=secondpart.iterator(); fnit.hasNext(); ) { FlatNode fn=fnit.next(); @@ -227,8 +227,8 @@ public class DelayComputation { MethodDescriptor md=lb.getMethod(); FlatMethod fm=state.getMethodFlat(md); Set exits=faen.getExits(); - Hashtable> livemap=Liveness.computeLiveTemps(fm); - Hashtable>> reachingdefs=ReachingDefs.computeReachingDefs(fm, Liveness.computeLiveTemps(fm), true); + Hashtable> livemap=Liveness.computeLiveTemps(fm,-1); + Hashtable>> reachingdefs=ReachingDefs.computeReachingDefs(fm, Liveness.computeLiveTemps(fm,-1), true); Set atomicnodes=faen.getReachableSet(faen.getExits()); @@ -272,7 +272,7 @@ public class DelayComputation { MethodDescriptor md=lb.getMethod(); FlatMethod fm=state.getMethodFlat(md); Set exits=faen.getExits(); - Hashtable> livemap=Liveness.computeLiveTemps(fm); + Hashtable> livemap=Liveness.computeLiveTemps(fm,-1); Hashtable>> reachingdefs=ReachingDefs.computeReachingDefs(fm, livemap, true); Set atomicnodes=faen.getReachableSet(faen.getExits()); @@ -324,7 +324,7 @@ public class DelayComputation { derefset=derefmap.get(lb); HashSet otherset=othermap.get(lb); HashSet cannotdelayset=cannotdelaymap.get(lb); - Hashtable> livemap=Liveness.computeLiveTemps(fm); + Hashtable> livemap=Liveness.computeLiveTemps(fm,-1); Hashtable>> reachingdefsmap=ReachingDefs.computeReachingDefs(fm, livemap, true); HashSet unionset=new HashSet(delayedset); Hashtable>> map=new Hashtable>>(); diff --git a/Robust/src/Analysis/Locality/DiscoverConflicts.java b/Robust/src/Analysis/Locality/DiscoverConflicts.java index 44fb4790..eb9aad85 100644 --- a/Robust/src/Analysis/Locality/DiscoverConflicts.java +++ b/Robust/src/Analysis/Locality/DiscoverConflicts.java @@ -568,7 +568,7 @@ public class DiscoverConflicts { MethodDescriptor md=lb.getMethod(); FlatMethod fm=state.getMethodFlat(md); Hashtable atomictable=locality.getAtomic(lb); - Hashtable> livetemps=Liveness.computeLiveTemps(fm); + Hashtable> livetemps=Liveness.computeLiveTemps(fm,-1); tovisit.add(fm); discovered.add(fm); @@ -726,7 +726,7 @@ public class DiscoverConflicts { MethodDescriptor md=lb.getMethod(); FlatMethod fm=state.getMethodFlat(md); Hashtable atomictable=locality.getAtomic(lb); - Hashtable> livetemps=Liveness.computeLiveTemps(fm); + Hashtable> livetemps=Liveness.computeLiveTemps(fm,-1); tovisit.add(fm); discovered.add(fm); diff --git a/Robust/src/Analysis/Locality/LocalityAnalysis.java b/Robust/src/Analysis/Locality/LocalityAnalysis.java index 04418984..d036269e 100644 --- a/Robust/src/Analysis/Locality/LocalityAnalysis.java +++ b/Robust/src/Analysis/Locality/LocalityAnalysis.java @@ -323,7 +323,7 @@ public class LocalityAnalysis { } } - Hashtable> livemap=Liveness.computeLiveTemps(fm); + Hashtable> livemap=Liveness.computeLiveTemps(fm,-1); while(!tovisit.isEmpty()) { FlatNode fn=tovisit.iterator().next(); @@ -1213,7 +1213,7 @@ public class LocalityAnalysis { Hashtable> temptab=getNodeTempInfo(lb); MethodDescriptor md=lb.getMethod(); FlatMethod fm=state.getMethodFlat(md); - Hashtable> nodetotemps=Liveness.computeLiveTemps(fm); + Hashtable> nodetotemps=Liveness.computeLiveTemps(fm,-1); Hashtable> nodetosavetemps=new Hashtable>(); tempstosave.put(lb, nodetosavetemps); Hashtable nodemap=new Hashtable(); diff --git a/Robust/src/Analysis/Loops/CSE.java b/Robust/src/Analysis/Loops/CSE.java index 9615fdb1..efa1f843 100644 --- a/Robust/src/Analysis/Loops/CSE.java +++ b/Robust/src/Analysis/Loops/CSE.java @@ -37,13 +37,26 @@ public class CSE { } } Hashtable tab=computeIntersection(fn, availexpr); - + +// if(tab.size()>1000){ +// System.out.println("Skipping CSE of "+fm.getMethod()+" due to size."); +// return; +// } + //Do kills of expression/variable mappings TempDescriptor[] write=fn.writesTemps(); for(int i=0; i> livetemps=Liveness.computeLiveTemps(fm); Hashtable> table =new Hashtable>(); boolean changed=false; TempDescriptor bogustd=new TempDescriptor("bogus"); do { + Hashtable> livetemps=Liveness.computeLiveTemps(fm,1000); + if(livetemps==null){ + System.out.println("Skipping CopyPropagation of "+fm.getMethod()+" due to size."); + return; + } changed=false; HashSet tovisit=new HashSet(); tovisit.add(fm); while(!tovisit.isEmpty()) { FlatNode fn=(FlatNode) tovisit.iterator().next(); tovisit.remove(fn); - Hashtable tab; - if (fn.numPrev()>=1&&table.containsKey(fn.getPrev(0))) - tab=new Hashtable(table.get(fn.getPrev(0))); - else + Set liveset=livetemps.get(fn); + + if (fn.numPrev()>=1&&table.containsKey(fn.getPrev(0))) { + tab=new Hashtable(); + for(Map.Entry entry:table.get(fn.getPrev(0)).entrySet()) { + if (liveset.contains(entry.getKey())) { + tab.put(entry.getKey(), entry.getValue()); + } + } + } else tab=new Hashtable(); //Compute intersection - Set liveset=livetemps.get(fn); for(int i=1; i tp=table.get(fn.getPrev(i)); if (tp==null) @@ -45,13 +54,13 @@ public class CopyPropagation { continue; TempDescriptor dsttmp=tp.get(tmp); if (!tab.containsKey(tmp)) { - tab.put(tmp, dsttmp); + tab.put(tmp, dsttmp); } else if (tab.get(tmp)!=dsttmp) { tab.put(tmp, bogustd); } } } - + HashSet toremove=new HashSet(); TempDescriptor[] writes=fn.writesTemps(); for(int i=0; i> tmp=new Hashtable>(); HashSet toanalyze=new HashSet(); - Hashtable> livemap=Liveness.computeLiveTemps(fm); + Hashtable> livemap=Liveness.computeLiveTemps(fm,-1); toanalyze.addAll(fm.getNodeSet()); while(!toanalyze.isEmpty()) { FlatNode fn=toanalyze.iterator().next(); diff --git a/Robust/src/Analysis/Pointer/Pointer.java b/Robust/src/Analysis/Pointer/Pointer.java index 5a648767..8b0ce00b 100644 --- a/Robust/src/Analysis/Pointer/Pointer.java +++ b/Robust/src/Analysis/Pointer/Pointer.java @@ -76,7 +76,7 @@ public class Pointer implements HeapAnalysis { public BasicBlock getBBlock(FlatMethod fm) { if (!blockMap.containsKey(fm)) { blockMap.put(fm, BasicBlock.getBBlock(fm)); - Hashtable> livemap=Liveness.computeLiveTemps(fm); + Hashtable> livemap=Liveness.computeLiveTemps(fm,-1); for(BBlock bblock : blockMap.get(fm).getBlocks()) { FlatNode fn=bblock.nodes.get(0); if (fn==fm) { -- 2.34.1