Robust/src/Analysis/MLP/SESETree.java

   1 package Analysis.MLP;
   2 import IR.*;
   3 import IR.Flat.*;
   4 import java.util.*;
   5 import Analysis.CallGraph.*;
   6
   7 public class SESETree {
   8   State state;
   9   TypeUtil typeutil;
  10   CallGraph callgraph;
  11   SESENode root;
  12   Hashtable<MethodDescriptor, Set<SESENode>> toanalyze=new Hashtable<MethodDescriptor,Set<SESENode>>();
  13   Hashtable<MethodDescriptor, Set<SESENode>> discovered=new Hashtable<MethodDescriptor,Set<SESENode>>();
  14   Hashtable<FlatSESEEnterNode, SESENode> sesemap=new Hashtable<FlatSESEEnterNode, SESENode>();
  15
  16   public SESETree(State state, TypeUtil typeutil, CallGraph callgraph) {
  17     this.state=state;
  18     this.typeutil=typeutil;
  19     this.callgraph=callgraph;
  20     root=new SESENode(null, true);
  21     doAnalysis();
  22   }
  23
  24   public SESENode getRoot() {
  25     return root;
  26   }
  27
  28   public void doAnalysis() {
  29     MethodDescriptor main=typeutil.getMain();
  30     add(toanalyze, main, root);
  31     add(discovered, main, root);
  32
  33     while(!toanalyze.isEmpty()) {
  34       MethodDescriptor md=toanalyze.keySet().iterator().next();
  35       Set<SESENode> context=toanalyze.get(md);
  36       toanalyze.remove(md);
  37       FlatMethod fm=state.getMethodFlat(md);
  38       analyzeMethod(fm, context);
  39     }
  40   }
  41
  42   public SESENode getSESE(FlatSESEEnterNode enter) {
  43     if (!sesemap.containsKey(enter)) {
  44       sesemap.put(enter, new SESENode(enter, false));
  45     }
  46     return sesemap.get(enter);
  47   }
  48
  49   private void analyzeMethod(FlatMethod fm, Set<SESENode> context) {
  50     Hashtable<FlatNode, Stack<SESENode>> stacks=new Hashtable<FlatNode, Stack<SESENode>> ();
  51     stacks.put(fm, new Stack<SESENode>());
  52     HashSet<FlatNode> tovisit=new HashSet<FlatNode>();
  53     HashSet<FlatNode> fndiscovered=new HashSet<FlatNode>();
  54     tovisit.add(fm);
  55     fndiscovered.add(fm);
  56     while(!tovisit.isEmpty()) {
  57       FlatNode fn=tovisit.iterator().next();
  58       tovisit.remove(fn);
  59       Stack<SESENode> instack=stacks.get(fm);
  60       switch(fn.kind()) {
  61       case FKind.FlatCall: {
  62         FlatCall fc=(FlatCall)fn;
  63         //handle method call
  64         Set<SESENode> parents;
  65         if (instack.isEmpty()) {
  66           parents=context;
  67         } else {
  68           parents=new HashSet<SESENode>();
  69           parents.add(instack.peek());
  70         }
  71         for(Iterator<SESENode> parentit=parents.iterator();parentit.hasNext();) {
  72           SESENode parentsese=parentit.next();
  73           for(Iterator<MethodDescriptor> calleeit=(fc.getThis()==null?callgraph.getMethods(fc.getMethod()):callgraph.getMethods(fc.getMethod(), fc.getThis().getType())).iterator(); calleeit.hasNext();) {
  74             MethodDescriptor md=calleeit.next();
  75             if (add(discovered,md, parentsese)) {
  76               add(toanalyze, md, parentsese);
  77             }
  78           }
  79         }
  80         break;
  81       }
  82       case FKind.FlatSESEEnterNode: {
  83         FlatSESEEnterNode enter=(FlatSESEEnterNode)fn;
  84         Set<SESENode> parents;
  85         if (instack.isEmpty()) {
  86           parents=context;
  87         } else {
  88           parents=new HashSet<SESENode>();
  89           parents.add(instack.peek());
  90         }
  91         SESENode sese=getSESE(enter);
  92         for(Iterator<SESENode> parentit=parents.iterator();parentit.hasNext();) {
  93           SESENode parentsese=parentit.next();
  94           parentsese.addChild(sese);
  95         }
  96         Stack<SESENode> copy=(Stack<SESENode>)instack.clone();
  97         copy.push(sese);
  98         instack=copy;
  99         break;
 100       }
 101       case FKind.FlatSESEExitNode: {
 102         FlatSESEExitNode exit=(FlatSESEExitNode)fn;
 103         Stack<SESENode> copy=(Stack<SESENode>)instack.clone();
 104         copy.pop();
 105         instack=copy;
 106         break;
 107       }
 108       }
 109       for(int i=0;i<fn.numNext();i++) {
 110         FlatNode fnext=fn.getNext(i);
 111         if (!fndiscovered.contains(fnext)) {
 112           fndiscovered.add(fnext);
 113           tovisit.add(fnext);
 114           stacks.put(fnext, instack);
 115         }
 116       }
 117     }
 118
 119
 120   }
 121
 122   public static boolean add(Hashtable<MethodDescriptor, Set<SESENode>> discovered, MethodDescriptor md, SESENode sese) {
 123     if (!discovered.containsKey(md))
 124       discovered.put(md, new HashSet<SESENode>());
 125     if (discovered.get(md).contains(sese))
 126       return false;
 127     discovered.get(md).add(sese);
 128     return true;
 129   }
 130
 131
 132   class SESENode {
 133     boolean isRoot;
 134     HashSet<SESENode> children;
 135     FlatSESEEnterNode node;
 136     SESENode(FlatSESEEnterNode node, boolean isRoot) {
 137       children=new HashSet<SESENode>();
 138       this.isRoot=isRoot;
 139       this.node=node;
 140     }
 141
 142     public boolean isLeaf() {
 143       return children.isEmpty();
 144     }
 145
 146     public void addChild(SESENode child) {
 147       children.add(child);
 148     }
 149
 150     public Set<SESENode> getChildren() {
 151       return children;
 152     }
 153   }
 154 }