View Javadoc

1   package joeq.Compiler.Analysis.IPSSA;
2   
3   import java.util.Iterator;
4   import java.util.LinkedHashSet;
5   import java.util.Vector;
6   import joeq.Class.jq_Method;
7   import joeq.Compiler.Analysis.IPSSA.SSAIterator.DefinitionIterator;
8   import joeq.Compiler.Analysis.IPSSA.Utils.DefinitionSet;
9   import joeq.Compiler.Analysis.IPSSA.Utils.IteratorHelper;
10  import joeq.Compiler.Quad.Quad;
11  import jwutil.util.Assert;
12  
13  /***
14   * The RHS of a binding. Has multiple subclasses.
15   * @see joeq.Compiler.Analysis.IPSSA.SSADefinition
16   * @version $Id: SSAValue.java 1931 2004-09-22 22:17:47Z joewhaley $
17   * */
18  public abstract class  SSAValue {
19      protected SSADefinition _destination;
20      
21      public SSADefinition getDestination(){
22          return _destination;
23      }
24      
25      void setDestination(SSADefinition def){
26          _destination = def;
27      }
28      
29      public Quad getQuad() {
30          return getDestination().getQuad();
31      }
32      
33      public abstract SSAIterator.DefinitionIterator getUsedDefinitionIterator();
34      
35      public abstract String toString();
36          
37      /***
38       * This value is just a reference to a definition.
39       * TODO: do we still have copies in the reduced representation?..
40       * */
41      public static class Copy extends SSAValue {
42          SSADefinition _definition;
43  
44          public static class FACTORY {
45              // TODO: maybe add caching of these to increase sharing?..
46              static Copy create_copy(SSADefinition def){
47                  return new Copy(def);
48              }
49          }
50          
51          private Copy(SSADefinition def){
52              this._definition = def;
53              
54              def.appendUse(this);
55          }
56          
57          public SSAIterator.DefinitionIterator getUsedDefinitionIterator(){
58              return new SSAIterator.DefinitionIterator(new IteratorHelper.SingleIterator(_definition));
59          }
60          
61          public SSADefinition getDefinition(){
62              return _definition;
63          }
64  
65          public String toString() {
66              return "(" + _definition + ")";
67          }        
68      }
69      
70      public static class Alloc extends SSAValue {
71          Quad _quad;
72          private Alloc(Quad quad) {
73              this._quad = quad;
74          }
75          
76          public static class FACTORY {
77              public static Alloc createAlloc(Quad quad) {
78                  return new Alloc(quad);
79              }
80          }
81  
82          public DefinitionIterator getUsedDefinitionIterator() {
83              return new SSAIterator.DefinitionIterator(IteratorHelper.EmptyIterator.FACTORY.get());
84          }
85  
86          public String toString() {
87              return "Alloc @ " + _quad;
88          }
89      }
90  
91  
92      public static abstract class Terminal extends SSAValue {}
93      
94      public static abstract class Constant extends Terminal {
95          public SSAIterator.DefinitionIterator getUsedDefinitionIterator(){
96              return new SSAIterator.DefinitionIterator(IteratorHelper.EmptyIterator.FACTORY.get());
97          }
98      }
99      
100     public static class UnknownConstant extends Constant {
101         /*** Use UnknownContant.FACTORY */
102         private UnknownConstant(){}
103         
104         public static class FACTORY {
105             static UnknownConstant _sample = null;                    
106             public static UnknownConstant create_unknown_contant(){
107                 if(_sample == null){
108                     _sample = new UnknownConstant();
109                 }
110                 return _sample;                
111             }
112         }
113         
114         public String toString(){return "<Unknown>";}
115     }
116     
117     public static class NullConstant extends Constant {
118         /*** Use NullContant.FACTORY */
119         private NullConstant(){}
120 
121         public static class FACTORY {
122             static NullConstant _sample = null;                    
123             public static NullConstant create_null_contant(){
124                 if(_sample == null){
125                     _sample = new NullConstant();
126                 }
127                 return _sample;                
128             }
129         }
130         public String toString(){return "<Null>";}
131     }
132     
133     public static abstract class Normal extends Terminal {
134         // TODO: this may contain arbitrary expressions
135         public abstract SSAIterator.DefinitionIterator getUsedDefinitionIterator();
136     }
137     
138     
139     public static class UseCollection extends Normal {
140         DefinitionSet _usedDefinitions;
141         
142         private UseCollection() {
143             _usedDefinitions = new DefinitionSet();
144         }
145         
146         public static class FACTORY {
147             static UseCollection createUseCollection() {
148                 return new UseCollection();
149             }
150         }
151 
152         public DefinitionIterator getUsedDefinitionIterator() {
153             return _usedDefinitions.getDefinitionIterator();
154         }
155 
156         public void addUsedDefinition(SSADefinition def) {
157             _usedDefinitions.add(def);
158             def.appendUse(this);            
159         }
160         
161         public String toString() {
162             StringBuffer buf = new StringBuffer("{ ");
163             for(SSAIterator.DefinitionIterator iter = getUsedDefinitionIterator(); iter.hasNext(); ) {
164                 SSADefinition def = iter.nextDefinition();
165                 buf.append(def.toString());
166                 buf.append(" ");
167             }
168             buf.append("}");
169             
170             return buf.toString();            
171         }        
172     }
173     
174     public static abstract class Phi extends  SSAValue {
175         protected Vector/*<SSADefinition>*/         _definitions          = new Vector();
176         protected LinkedHashSet /*<SSADefinition>*/ _usedDefinitions     = new LinkedHashSet(); 
177         
178         public int getDefinitionCount(){
179             return _definitions.size();
180         }
181         public SSADefinition getDefinition(int pos){
182             return (SSADefinition)_definitions.get(pos);
183         }
184         public Iterator/*<SSADefinition>*/ getDefinitionIterator(){
185             return _definitions.iterator();
186         }
187         
188         public SSAIterator.DefinitionIterator getUsedDefinitionIterator(){
189             return new SSAIterator.DefinitionIterator(_usedDefinitions.iterator());
190         }
191         
192         abstract public String getLetter();
193         
194         public String toString(){
195             String result = getLetter() + "(";
196             for(int i = 0; i < _definitions.size(); i++){
197                 SSADefinition def = getDefinition(i);
198                 
199                 result += def.toString() + ", ";
200             }
201             if(_definitions.size()>0){
202                 result = result.substring(0, result.length() - 2);
203             }
204             
205             return result + ")";
206         }
207     }
208     
209     /***
210      *     The representation of predicates is yet to be determined. It's currently pretty lame.
211      * */
212     public static class Predicate {
213         private String _predicate;
214         public static String UNKNOWN = "<unknown>";
215 
216         public Predicate(String predicate){
217             this._predicate = predicate;
218         }
219         public String toString(){
220             return _predicate;
221         }
222         public static Predicate True() {
223             return null;        // TODO
224         }
225     }
226     
227     public static abstract class Predicated extends Phi {
228         protected Vector/* <SSAPredicate> */ _predicates = new Vector();            
229         
230         public Predicate getPredicate(int pos){
231             return (Predicate)_predicates.get(pos);
232         }
233         
234         public void add(SSADefinition def, String predicate){
235             _definitions.addElement(def);
236             _predicates.addElement(predicate);
237             
238             def.appendUse(this);
239             _usedDefinitions.add(def);
240         }
241         
242         public String toString(){
243             Assert._assert(_predicates.size() == _definitions.size());
244             String result = getLetter() + "(";
245             for(int i = 0; i < _definitions.size(); i++){
246                 SSADefinition def = getDefinition(i);
247                 Predicate pred = getPredicate(i);
248         
249                 if(pred == null){ 
250                     result += "<" + def + ">, ";
251                 }else{
252                     result += "<" + def + ", " + pred.toString() + ">, ";
253                 }
254             }
255             if(_definitions.size() > 0){
256                 result = result.substring(0, result.length() - 2);
257             }
258     
259             return result + ")";
260         }        
261     }
262         
263     /***
264      * This represents a merge of definitions but without any further 
265      * information such as predicates. 
266      * */
267     public static class OmegaPhi extends Phi {
268         public String getLetter(){return "omega";}
269         
270         public void addUsedDefinition(SSADefinition def){
271             _definitions.addElement(def);
272             
273             def.appendUse(this);
274             _usedDefinitions.add(def);
275         }
276     }
277     
278     public static class SigmaPhi extends Phi {
279         private ContextSet _context;
280         
281         public SigmaPhi(ContextSet context, SSADefinition newDef, SSADefinition oldDef){
282             setContext(context);
283             _definitions.add(newDef);
284             _definitions.add(oldDef);
285             
286             _usedDefinitions.add(newDef);
287             _usedDefinitions.add(oldDef);
288             
289             oldDef.appendUse(this);
290             newDef.appendUse(this);
291         }
292         public String getLetter(){return "sigma";}
293 
294         protected void setContext(ContextSet _context) {
295             this._context = _context;
296         }
297         protected ContextSet getContext() {
298             return _context;
299         }
300     }
301 
302     public static class Gamma extends Predicated {
303         public String getLetter(){return "gamma";}    
304     }
305         
306     public static abstract class IPPhi extends Phi {
307 
308     }
309     
310     public static class FormalIn extends IPPhi {
311         protected Vector/*<Quad>*/ _callers;
312         
313         FormalIn(){
314             _callers = new Vector();
315         }
316         
317         Quad getCaller(int pos){
318             return (Quad)_callers.get(pos); 
319         }
320         void add(SSADefinition def, Quad caller){
321             _definitions.addElement(def);
322             _callers.addElement(caller);
323             
324             _usedDefinitions.add(def);
325             def.appendUse(this);
326         }
327         public String getLetter(){return "iota";}
328         public String toString(){
329             String result = getLetter() + "(";
330             for(int i = 0; i < _definitions.size(); i++){
331                 SSADefinition def = getDefinition(i);
332                 Quad caller = getCaller(i);
333 
334                 result += "<" + def.toString() + ", " + caller + ">, ";
335             }
336             if(_definitions.size()>0){
337                 result = result.substring(0, result.length() - 2);
338             }
339 
340             return result + ")";
341         }
342 
343         public boolean hasCallSite(Quad quad) {
344             return _callers.contains(quad);
345         }
346     }
347     
348     public static class ActualOut extends IPPhi {
349         protected Vector/*<jq_Method>*/ _callees;
350         
351         ActualOut(){
352             _callees = new Vector();
353         }
354         
355         jq_Method getCallee(int pos){
356             return (jq_Method)_callees.get(pos); 
357         }
358         void add(SSADefinition def, jq_Method method){
359             _definitions.addElement(def);
360             _callees.addElement(method);
361             
362             _usedDefinitions.add(def);
363             def.appendUse(this);
364         }
365         public String getLetter(){return "rho";}
366         
367         public String toString(){
368             String result = getLetter() + "(";
369             for(int i = 0; i < _definitions.size(); i++){
370                 SSADefinition def = getDefinition(i);
371                 jq_Method method = getCallee(i);
372 
373                 result += "<" + def.toString() + ", " + method + ">, ";
374             }
375             if(_definitions.size()>0){
376                 result = result.substring(0, result.length() - 2);
377             }
378 
379             return result + ")";
380         }
381     }
382 }
383