Robust/src/Analysis/OoOJava/Accessible.java

   1 package Analysis.OoOJava;
   2 import Util.Pair;
   3 import java.util.*;
   4 import IR.Flat.*;
   5 import IR.*;
   6 import Analysis.Liveness;
   7 import Analysis.CallGraph.CallGraph;
   8
   9 public class Accessible {
  10   //Try to compute InAccessible
  11   HashMap<FlatNode, Set<TempDescriptor>> inAccessible;
  12   State state;
  13   CallGraph callGraph;
  14   RBlockRelationAnalysis taskAnalysis;
  15   Liveness liveness;
  16   Stack<Pair<FlatNode,MethodDescriptor>> toprocess=new Stack<Pair<FlatNode, MethodDescriptor>>();
  17   HashMap<MethodDescriptor, Set<Pair<FlatCall, MethodDescriptor>>> methodmap=new HashMap<MethodDescriptor, Set<Pair<FlatCall, MethodDescriptor>>>();
  18
  19   public Accessible(State state, CallGraph callGraph, RBlockRelationAnalysis taskAnalysis, Liveness liveness) {
  20     inAccessible=new HashMap<FlatNode, Set<TempDescriptor>>();
  21     this.state=state;
  22     this.callGraph=callGraph;
  23     this.taskAnalysis=taskAnalysis;
  24     this.liveness=liveness;
  25   }
  26
  27   public boolean isAccessible(FlatNode fn, TempDescriptor tmp) {
  28     for(int i=0; i<fn.numPrev(); i++) {
  29       FlatNode fprev=fn.getPrev(i);
  30       if (inAccessible.containsKey(fprev)&&inAccessible.get(fprev).contains(tmp))
  31         return false;
  32     }
  33     return true;
  34   }
  35
  36   public void computeFixPoint() {
  37 nextNode:
  38     while(!toprocess.isEmpty()) {
  39       Pair<FlatNode, MethodDescriptor> fnpair=toprocess.pop();
  40       FlatNode fn=fnpair.getFirst();
  41       MethodDescriptor pairmd=fnpair.getSecond();
  42       HashSet<TempDescriptor> inAccessibleSet=new HashSet<TempDescriptor>();
  43       for(int i=0; i<fn.numPrev(); i++) {
  44         Set<TempDescriptor> inAccess=inAccessible.get(fn.getPrev(i));
  45         if (inAccess!=null)
  46           inAccessibleSet.addAll(inAccess);
  47       }
  48
  49       switch(fn.kind()) {
  50       case FKind.FlatNew:
  51       case FKind.FlatFieldNode:
  52       case FKind.FlatElementNode:
  53       case FKind.FlatSetFieldNode:
  54       case FKind.FlatSetElementNode:
  55       {
  56         TempDescriptor[] rdtmps=fn.readsTemps();
  57         for(int i=0; i<rdtmps.length; i++) {
  58           inAccessibleSet.remove(rdtmps[i]);
  59         }
  60         TempDescriptor[] wrtmps=fn.writesTemps();
  61         for(int i=0; i<wrtmps.length; i++) {
  62           inAccessibleSet.remove(wrtmps[i]);
  63         }
  64       }
  65       break;
  66
  67       case FKind.FlatCastNode:
  68       case FKind.FlatOpNode:
  69       {
  70         TempDescriptor[] rdtmps=fn.readsTemps();
  71         TempDescriptor[] wrtmps=fn.writesTemps();
  72         if (inAccessibleSet.contains(rdtmps[0]))
  73           inAccessibleSet.add(wrtmps[0]);
  74       }
  75       break;
  76
  77       case FKind.FlatReturnNode:
  78       {
  79         FlatReturnNode fr=(FlatReturnNode)fn;
  80         if (fr.getReturnTemp()!=null&&inAccessibleSet.contains(fr.getReturnTemp())) {
  81           //Need to inform callers
  82           Set<Pair<FlatCall, MethodDescriptor>> callset=methodmap.get(pairmd);
  83           for(Pair<FlatCall, MethodDescriptor> fcallpair : callset) {
  84             FlatCall fcall=fcallpair.getFirst();
  85             Set<TempDescriptor> inAccess=inAccessible.get(fcall);
  86             if (fcall.getReturnTemp()!=null&&!inAccess.contains(fcall.getReturnTemp())) {
  87               inAccess.add(fcall.getReturnTemp());
  88               for(int i=0; i<fcall.numNext(); i++) {
  89                 toprocess.add(new Pair<FlatNode, MethodDescriptor>(fcall.getNext(i), fcallpair.getSecond()));
  90               }
  91             }
  92           }
  93         }
  94       }
  95         continue nextNode;
  96
  97       case FKind.FlatSESEEnterNode:
  98       case FKind.FlatSESEExitNode:
  99         continue nextNode;
 100
 101       case FKind.FlatCall: {
 102         FlatCall fcall=(FlatCall)fn;
 103         MethodDescriptor calledmethod=fcall.getMethod();
 104         Set methodsthatcouldbecalled=fcall.getThis()==null?callGraph.getMethods(calledmethod):
 105                                       callGraph.getMethods(calledmethod, fcall.getThis().getType());
 106         for(Object o : methodsthatcouldbecalled) {
 107           MethodDescriptor md=(MethodDescriptor)o;
 108           FlatMethod fm=state.getMethodFlat(md);
 109
 110           if (!methodmap.containsKey(md))
 111             methodmap.put(md, new HashSet<Pair<FlatCall, MethodDescriptor>>());
 112
 113           methodmap.get(md).add(new Pair<FlatCall, MethodDescriptor>(fcall, pairmd));
 114
 115           HashSet<TempDescriptor> tmpinaccess=new HashSet<TempDescriptor>();
 116           for(int i=0; i<fm.numParameters(); i++) {
 117             TempDescriptor fmtmp=fm.getParameter(i);
 118             TempDescriptor tmpcall=fcall.getArgMatchingParamIndex(fm, i);
 119             if (inAccessibleSet.contains(tmpcall)) {
 120               tmpinaccess.add(fmtmp);
 121             }
 122           }
 123           if (!tmpinaccess.isEmpty()&&(!inAccessible.containsKey(fm)||!inAccessible.get(fm).containsAll(tmpinaccess))) {
 124             for(int i=0; i<fm.numNext(); i++)
 125               toprocess.add(new Pair<FlatNode, MethodDescriptor>(fm.getNext(i),md));
 126             if (!inAccessible.containsKey(fm))
 127               inAccessible.put(fm, new HashSet<TempDescriptor>());
 128             inAccessible.get(fm).addAll(tmpinaccess);
 129           }
 130         }
 131         //be sure not to wipe out return value or other inaccessible temps
 132         Set<TempDescriptor> oldtemps=inAccessible.get(fcall);
 133         if (oldtemps!=null)
 134           inAccessibleSet.addAll(oldtemps);
 135       }
 136       break;
 137
 138       default:
 139       }
 140       if (!inAccessibleSet.isEmpty()&&(!inAccessible.containsKey(fn)||!inAccessible.get(fn).equals(inAccessibleSet))) {
 141         inAccessible.put(fn, inAccessibleSet);
 142         for(int i=0; i<fn.numNext(); i++)
 143           toprocess.add(new Pair<FlatNode, MethodDescriptor>(fn.getNext(i),pairmd));
 144       }
 145     }
 146   }
 147
 148   public void doAnalysis() {
 149     for(FlatSESEEnterNode sese : taskAnalysis.getAllSESEs()) {
 150       FlatSESEExitNode seseexit=sese.getFlatExit();
 151       HashSet<TempDescriptor> liveout=new HashSet<TempDescriptor>(liveness.getLiveOutTemps(sese.getfmEnclosing(), seseexit));
 152       for(Iterator<TempDescriptor> tmpit=liveout.iterator(); tmpit.hasNext(); ) {
 153         TempDescriptor tmp=tmpit.next();
 154         if (!tmp.getType().isPtr())
 155           tmpit.remove();
 156       }
 157       inAccessible.put(seseexit, liveout);
 158       for(int i=0; i<seseexit.numNext(); i++)
 159         toprocess.add(new Pair<FlatNode, MethodDescriptor>(seseexit.getNext(i),sese.getmdEnclosing()));
 160     }
 161
 162     Set<MethodDescriptor> methodSet=taskAnalysis.getMethodsWithSESEs();
 163     Set<MethodDescriptor> canCallSESE=new HashSet<MethodDescriptor>(methodSet);
 164     Stack<MethodDescriptor> methodStack=new Stack<MethodDescriptor>();
 165     methodStack.addAll(methodSet);
 166     //Set up exits of SESEs
 167     while(!methodStack.isEmpty()) {
 168       MethodDescriptor md=methodStack.pop();
 169       Set callers=callGraph.getCallerSet(md);
 170       for(Object o : callers) {
 171         MethodDescriptor callermd=(MethodDescriptor)o;
 172         if (!canCallSESE.contains(callermd)) {
 173           //new method descriptor
 174           canCallSESE.add(callermd);
 175           methodStack.add(callermd);
 176         }
 177       }
 178     }
 179
 180     //Set up exits of methods
 181     for(MethodDescriptor md : canCallSESE) {
 182       FlatMethod fm=state.getMethodFlat(md);
 183       for(FlatNode fn : fm.getNodeSet()) {
 184         if (fn.kind()==FKind.FlatCall) {
 185           FlatCall fcall=(FlatCall)fn;
 186           MethodDescriptor calledmethod=fcall.getMethod();
 187           Set methodsthatcouldbecalled=fcall.getThis()==null?callGraph.getMethods(calledmethod):
 188                                         callGraph.getMethods(calledmethod, fcall.getThis().getType());
 189           boolean specialcall=false;
 190           for(Object o : methodsthatcouldbecalled) {
 191             MethodDescriptor callermd=(MethodDescriptor)o;
 192             if (canCallSESE.contains(callermd)) {
 193               //TODO: NEED TO BUILD MAP FROM MD -> CALLS
 194               specialcall=true;
 195               if (!methodmap.containsKey(callermd))
 196                 methodmap.put(callermd, new HashSet<Pair<FlatCall, MethodDescriptor>>());
 197               methodmap.get(callermd).add(new Pair<FlatCall, MethodDescriptor>(fcall,md));
 198             }
 199           }
 200           if (specialcall) {
 201             Set<TempDescriptor> liveout=new HashSet<TempDescriptor>(liveness.getLiveOutTemps(fm, fcall));
 202             TempDescriptor returntmp=fcall.getReturnTemp();
 203             liveout.remove(returntmp);
 204             for(Iterator<TempDescriptor> tmpit=liveout.iterator(); tmpit.hasNext(); ) {
 205               TempDescriptor tmp=tmpit.next();
 206               if (!tmp.getType().isPtr())
 207                 tmpit.remove();
 208             }
 209             inAccessible.put(fcall, liveout);
 210             for(int i=0; i<fcall.numNext(); i++)
 211               toprocess.add(new Pair<FlatNode, MethodDescriptor>(fcall.getNext(i),md));
 212           }
 213         }
 214       }
 215     }
 216     computeFixPoint();
 217   }
 218 }