1 package Analysis.Locality;
5 import java.util.Arrays;
6 import java.util.HashSet;
7 import java.util.Iterator;
8 import java.util.Hashtable;
9 import Analysis.CallGraph.CallGraph;
13 import IR.TypeDescriptor;
14 import IR.MethodDescriptor;
15 import IR.FieldDescriptor;
17 public class TypeAnalysis {
18 /* This analysis is essentially a dataflow analysis.
20 LocalityAnalysis locality;
24 Hashtable<TypeDescriptor, Set<TypeDescriptor>> map;
25 HashSet<TypeDescriptor> roottypes;
26 Hashtable<TypeDescriptor, Set<TypeDescriptor>> transmap;
27 Hashtable<TypeDescriptor, Set<TypeDescriptor>> namemap;
29 public TypeAnalysis(LocalityAnalysis locality, State state, TypeUtil typeutil, CallGraph cg) {
31 this.locality=locality;
32 this.typeutil=typeutil;
34 map=new Hashtable<TypeDescriptor, Set<TypeDescriptor>>();
35 transmap=new Hashtable<TypeDescriptor, Set<TypeDescriptor>>();
36 namemap=new Hashtable<TypeDescriptor, Set<TypeDescriptor>>();
37 roottypes=new HashSet<TypeDescriptor>();
41 /* We use locality bindings to get calleable methods. This could be
42 * changed to use the callgraph starting from the main method. */
45 Set<LocalityBinding> localityset=locality.getLocalityBindings();
46 for(Iterator<LocalityBinding> lb=localityset.iterator(); lb.hasNext(); ) {
47 computeTypes(lb.next().getMethod());
53 void computeOtherNames() {
54 for(Iterator<TypeDescriptor> it=transmap.keySet().iterator(); it.hasNext(); ) {
55 TypeDescriptor td=it.next();
56 Set<TypeDescriptor> set=transmap.get(td);
57 for(Iterator<TypeDescriptor> it2=set.iterator(); it2.hasNext(); ) {
58 TypeDescriptor type=it2.next();
59 if (!namemap.containsKey(type))
60 namemap.put(type, new HashSet<TypeDescriptor>());
61 namemap.get(type).addAll(set);
67 //Idea: for each type we want to know all of the possible types it could be called
68 for(Iterator<TypeDescriptor> it=roottypes.iterator(); it.hasNext(); ) {
69 TypeDescriptor td=it.next();
70 HashSet<TypeDescriptor> tovisit=new HashSet<TypeDescriptor>();
71 transmap.put(td, new HashSet<TypeDescriptor>());
73 transmap.get(td).add(td);
75 while(!tovisit.isEmpty()) {
76 TypeDescriptor type=tovisit.iterator().next();
78 //Is type a supertype of td...if not skip along
79 if (!typeutil.isSuperorType(type,td))
81 //Check if we have seen it before
82 if (!transmap.get(td).contains(type)) {
83 //If not, add to set and continue processing
84 transmap.get(td).add(type);
91 public Set<TypeDescriptor> expand(TypeDescriptor td) {
92 Set<TypeDescriptor> expandset=namemap.get(td);
96 public Set<TypeDescriptor> expandSet(Set<TypeDescriptor> tdset) {
97 HashSet<TypeDescriptor> expandedSet=new HashSet<TypeDescriptor>();
98 for(Iterator<TypeDescriptor> it=tdset.iterator(); it.hasNext(); ) {
99 TypeDescriptor td=it.next();
100 Set<TypeDescriptor> etdset=expand(td);
104 expandedSet.addAll(etdset);
109 public boolean couldAlias(TypeDescriptor td1, TypeDescriptor td2) {
110 return namemap.get(td1).contains(td2);
113 public void addMapping(TypeDescriptor src, TypeDescriptor dst) {
114 if (!map.containsKey(src))
115 map.put(src, new HashSet<TypeDescriptor>());
116 map.get(src).add(dst);
119 void computeTypes(MethodDescriptor md) {
120 FlatMethod fm=state.getMethodFlat(md);
121 for(Iterator<FlatNode> fnit=fm.getNodeSet().iterator(); fnit.hasNext(); ) {
122 FlatNode fn=fnit.next();
124 case FKind.FlatOpNode: {
125 FlatOpNode fon=(FlatOpNode)fn;
126 if(fon.getOp().getOp()==Operation.ASSIGN) {
127 addMapping(fon.getLeft().getType(),fon.getDest().getType());
132 case FKind.FlatNew: {
133 FlatNew fnew=(FlatNew)fn;
134 roottypes.add(fnew.getType());
138 case FKind.FlatCastNode: {
139 FlatCastNode fcn=(FlatCastNode)fn;
140 addMapping(fcn.getSrc().getType(), fcn.getDst().getType());
144 case FKind.FlatFieldNode: {
145 FlatFieldNode ffn=(FlatFieldNode)fn;
146 addMapping(ffn.getField().getType(), ffn.getDst().getType());
150 case FKind.FlatSetFieldNode: {
151 FlatSetFieldNode fsfn=(FlatSetFieldNode) fn;
152 addMapping(fsfn.getSrc().getType(), fsfn.getField().getType());
156 case FKind.FlatElementNode: {
157 FlatElementNode fen=(FlatElementNode)fn;
158 addMapping(fen.getSrc().getType().dereference(), fen.getDst().getType());
162 case FKind.FlatSetElementNode: {
163 FlatSetElementNode fsen=(FlatSetElementNode)fn;
164 addMapping(fsen.getSrc().getType(), fsen.getDst().getType().dereference());
168 case FKind.FlatCall: {
169 FlatCall fc=(FlatCall)fn;
170 if (fc.getReturnTemp()!=null) {
171 addMapping(fc.getMethod().getReturnType(), fc.getReturnTemp().getType());
173 MethodDescriptor callmd=fc.getMethod();
174 if (fc.getThis()!=null) {
175 //complicated...need to deal with virtual dispatch here
176 Set methods=cg.getMethods(callmd);
177 for(Iterator mdit=methods.iterator(); mdit.hasNext(); ) {
178 MethodDescriptor md2=(MethodDescriptor)mdit.next();
179 if (fc.getThis()!=null) {
180 TypeDescriptor ttype=new TypeDescriptor(md2.getClassDesc());
181 if (!typeutil.isSuperorType(fc.getThis().getType(),ttype)&&
182 !typeutil.isSuperorType(ttype,fc.getThis().getType()))
184 addMapping(fc.getThis().getType(), ttype);
188 for(int i=0; i<fc.numArgs(); i++) {
189 TempDescriptor arg=fc.getArg(i);
190 TypeDescriptor ptype=callmd.getParamType(i);
191 addMapping(arg.getType(), ptype);
196 //both inputs and output
197 case FKind.FlatReturnNode: {
198 FlatReturnNode frn=(FlatReturnNode) fn;
199 if (frn.getReturnTemp()!=null)
200 addMapping(frn.getReturnTemp().getType(), md.getReturnType());