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   public Set<SESENode> getSESE(MethodDescriptor md) {
  50     return discovered.get(md);
  51   }
  52
  53   public Hashtable<FlatNode, Stack<SESENode>> analyzeMethod(FlatMethod fm) {
  54     return analyzeMethod(fm, null);
  55   }
  56
  57   private Hashtable<FlatNode, Stack<SESENode>> analyzeMethod(FlatMethod fm, Set<SESENode> context) {
  58     Hashtable<FlatNode, Stack<SESENode>> stacks=new Hashtable<FlatNode, Stack<SESENode>> ();
  59     stacks.put(fm, new Stack<SESENode>());
  60     HashSet<FlatNode> tovisit=new HashSet<FlatNode>();
  61     HashSet<FlatNode> fndiscovered=new HashSet<FlatNode>();
  62     tovisit.add(fm);
  63     fndiscovered.add(fm);
  64     while(!tovisit.isEmpty()) {
  65       FlatNode fn=tovisit.iterator().next();
  66       tovisit.remove(fn);
  67       Stack<SESENode> instack=stacks.get(fm);
  68       switch(fn.kind()) {
  69       case FKind.FlatCall: {
  70         if (context==null)
  71           break;
  72         FlatCall fc=(FlatCall)fn;
  73         //handle method call
  74         Set<SESENode> parents;
  75         if (instack.isEmpty()) {
  76           parents=context;
  77         } else {
  78           parents=new HashSet<SESENode>();
  79           parents.add(instack.peek());
  80         }
  81         for(Iterator<SESENode> parentit=parents.iterator();parentit.hasNext();) {
  82           SESENode parentsese=parentit.next();
  83           for(Iterator<MethodDescriptor> calleeit=(fc.getThis()==null?callgraph.getMethods(fc.getMethod()):callgraph.getMethods(fc.getMethod(), fc.getThis().getType())).iterator(); calleeit.hasNext();) {
  84             MethodDescriptor md=calleeit.next();
  85             if (add(discovered,md, parentsese)) {
  86               add(toanalyze, md, parentsese);
  87             }
  88           }
  89         }
  90         break;
  91       }
  92       case FKind.FlatSESEEnterNode: {
  93         FlatSESEEnterNode enter=(FlatSESEEnterNode)fn;
  94
  95         if (context!=null) {
  96           Set<SESENode> parents;
  97           if (instack.isEmpty()) {
  98             parents=context;
  99           } else {
 100             parents=new HashSet<SESENode>();
 101             parents.add(instack.peek());
 102           }
 103           SESENode sese=getSESE(enter);
 104           for(Iterator<SESENode> parentit=parents.iterator();parentit.hasNext();) {
 105             SESENode parentsese=parentit.next();
 106             parentsese.addChild(sese);
 107           }
 108         }
 109         Stack<SESENode> copy=(Stack<SESENode>)instack.clone();
 110         copy.push(sese);
 111         instack=copy;
 112         break;
 113       }
 114       case FKind.FlatSESEExitNode: {
 115         FlatSESEExitNode exit=(FlatSESEExitNode)fn;
 116         Stack<SESENode> copy=(Stack<SESENode>)instack.clone();
 117         copy.pop();
 118         instack=copy;
 119         break;
 120       }
 121       }
 122       for(int i=0;i<fn.numNext();i++) {
 123         FlatNode fnext=fn.getNext(i);
 124         if (!fndiscovered.contains(fnext)) {
 125           fndiscovered.add(fnext);
 126           tovisit.add(fnext);
 127           stacks.put(fnext, instack);
 128         }
 129       }
 130     }
 131     return stacks;
 132   }
 133
 134   public static boolean add(Hashtable<MethodDescriptor, Set<SESENode>> discovered, MethodDescriptor md, SESENode sese) {
 135     if (!discovered.containsKey(md))
 136       discovered.put(md, new HashSet<SESENode>());
 137     if (discovered.get(md).contains(sese))
 138       return false;
 139     discovered.get(md).add(sese);
 140     return true;
 141   }
 142
 143
 144   class SESENode {
 145     boolean isRoot;
 146     HashSet<SESENode> children;
 147     HashSet<SESENode> parents;
 148
 149     FlatSESEEnterNode node;
 150     SESENode(FlatSESEEnterNode node, boolean isRoot) {
 151       children=new HashSet<SESENode>();
 152       this.isRoot=isRoot;
 153       this.node=node;
 154     }
 155
 156     public boolean isLeaf() {
 157       return children.isEmpty();
 158     }
 159
 160     protected void addChild(SESENode child) {
 161       children.add(child);
 162       child.parents.add(this);
 163     }
 164
 165     public Set<SESENode> getParents() {
 166       return parents;
 167     }
 168
 169     public Set<SESENode> getChildren() {
 170       return children;
 171     }
 172   }
 173 }