|
||
Main Page | Modules | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages
unification.hGo to the documentation of this file.00001 // ---------------------------------------------------------------------- 00002 // 00003 // C-Breeze 00004 // C Compiler Framework 00005 // 00006 // Copyright (c) 2000 University of Texas at Austin 00007 // 00008 // Teck Bok Tok 00009 // Samuel Z. Guyer 00010 // Daniel A. Jimenez 00011 // Calvin Lin 00012 // 00013 // Permission is hereby granted, free of charge, to any person 00014 // obtaining a copy of this software and associated documentation 00015 // files (the "Software"), to deal in the Software without 00016 // restriction, including without limitation the rights to use, copy, 00017 // modify, merge, publish, distribute, sublicense, and/or sell copies 00018 // of the Software, and to permit persons to whom the Software is 00019 // furnished to do so, subject to the following conditions: 00020 // 00021 // The above copyright notice and this permission notice shall be 00022 // included in all copies or substantial portions of the Software. 00023 // 00024 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 00025 // EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 00026 // MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 00027 // NONINFRINGEMENT. IN NO EVENT SHALL THE UNIVERSITY OF TEXAS AT 00028 // AUSTIN BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER 00029 // IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF 00030 // OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN 00031 // THE SOFTWARE. 00032 // 00033 // We acknowledge the C-to-C Translator from MIT Laboratory for 00034 // Computer Science for inspiring parts of the C-Breeze design. 00035 // 00036 // ---------------------------------------------------------------------- 00037 00038 #ifndef UNIFICATION_H 00039 #define UNIFICATION_H 00040 00041 #include "c_breeze.h" 00042 00043 class Linker; 00044 00045 /* Algorithm source: 00046 Bjarne Steensgaard. Points-to Analysis in Almost Linear Time. 00047 In Symposium on Principles of Programming Languages, pages 32--41, 1996 00048 */ 00049 00050 class Unify_ECR; 00051 class Unify_Offset; 00052 class Unify_Size; 00053 00054 class UnifyType; 00055 class UnificationBasedPtr; 00056 00057 class Unify_Pending; 00058 class Unify_Pendings { 00059 set<Unify_Pending*> _set; 00060 bool cleaned; 00061 public: 00062 Unify_Pendings() : cleaned(true) {} 00063 inline bool empty() const { return _set.empty(); } 00064 inline int size() const { return _set.size(); } 00065 inline void clear() { _set.clear(); } 00066 inline set<Unify_Pending*> set() const { return _set; } 00067 void insert(Unify_Pending *p, bool is_new); 00068 void cleanup(); 00069 }; // Unify_Pendings 00070 00071 00072 //%{ /* Unify_ECR's */ 00073 class Unify_ECR { 00074 protected: 00075 REF declNode *_var; 00076 REF procNode *_proc; 00077 REF Unify_ECR *_parent, *_root; 00078 int _ndecestors; 00079 set<Unify_ECR*> _children; 00080 Unify_Pendings _pending; 00081 TREE int _id; 00082 TREE UnifyType *_type; 00083 00084 static int id_count; 00085 static set<Unify_ECR*> all_ECR; 00086 00087 public: 00088 Unify_ECR(declNode *v, procNode *p); 00089 Unify_ECR(UnifyType *t); 00090 00091 inline declNode *var() const { return _var; } 00092 inline void var(declNode *d) { _var = d; } 00093 inline procNode *proc() const { return _proc; } 00094 inline void proc(procNode *p) { _proc=p; } 00095 inline Unify_ECR *parent() const { return _parent; } 00096 inline void parent(Unify_ECR *p) { _root = _parent = p; } 00097 Unify_ECR * root(); 00098 inline Unify_Pendings & pending() { return _pending; } 00099 inline int id() const { return _id; } 00100 bool operator==(Unify_ECR &other) { return root()==other.root(); } 00101 Unify_ECR * Union(Unify_ECR *other); 00102 decl_list all_decls() const; 00103 UnifyType * type(); 00104 void type(UnifyType *t); 00105 void print(); 00106 inline friend ostream & operator<<(ostream &o, Unify_ECR &ecr) { 00107 ecr.print(); return o; 00108 } 00109 static set<Unify_ECR*> allECR() { return all_ECR; } 00110 }; // Unify_ECR 00111 00112 //%} 00113 00114 //%{ /* misc */ 00115 class Unify_Offset { 00116 public: 00117 typedef enum { zero, unknown } Value; 00118 private: 00119 Value _value; 00120 Unify_Pendings _pending; 00121 public: 00122 Unify_Offset(Value v) : _value(v) {} 00123 inline Value value() const { return _value; } 00124 inline void value(Value v) { _value=v; } 00125 inline Unify_Pendings & pending() { return _pending; } 00126 inline bool leq(Unify_Offset *o) const 00127 { return _value==zero || _value==o->_value;} 00128 inline void print() const { cout << (_value==zero ? "zero" : "unknown"); } 00129 inline friend ostream & operator<<(ostream &o, const Unify_Offset &off) { 00130 off.print(); return o; 00131 } 00132 }; 00133 00134 class Alpha { 00135 Unify_ECR *_tao; 00136 Unify_Offset *_offset; 00137 public: 00138 Alpha(Unify_ECR *t, Unify_Offset *o) : _tao(t), _offset(o) { assert(t && o); } 00139 Alpha(); 00140 inline Unify_ECR *tao() const { return _tao; } 00141 inline Unify_Offset *offset() const { return _offset; } 00142 bool leq(Alpha *o, Unify_Size s) const; 00143 bool equal(Alpha *o) { return _tao->type()==o->tao()->type() && 00144 _offset->value()==o->offset()->value(); } 00145 void print() const; 00146 inline friend ostream & operator<<(ostream &o, const Alpha &a) { 00147 a.print(); return o; 00148 } 00149 }; 00150 00151 typedef set<declNode*> declSet; 00152 typedef list<declSet> FieldOrder; 00153 typedef list<typeNode*> FieldTypeOrder; 00154 typedef map<declSet,Unify_ECR*> EltMap; 00155 00156 class Lambda { 00157 int _n,_m; 00158 bool _ellipsis; // contain ellipsis? 00159 Unify_ECR **_taos, *_taoR; // array of tao 00160 bool _is_bottom; 00161 int _id; 00162 Unify_Pendings _pending; 00163 static int id_count; 00164 public: 00165 /*Lambda(int n, int m, ECR **t) : _n(n), _m(m), _taos(t), _is_bottom(false), 00166 _ellipsis(false), _id(id_count++) {}*/ 00167 Lambda() : _is_bottom(true), _ellipsis(false), _n(0), _m(0), _taos(NULL), 00168 _taoR(NULL), _id(id_count++) {} 00169 inline int id() const { return _id; } 00170 inline bool is_bottom() const { return _is_bottom; } 00171 inline int n() const { return _n; } 00172 inline int m() const { return _m; } 00173 inline bool ellipsis() const { return _ellipsis; } 00174 inline Unify_ECR *tao(int i) const { assert(i<_n); return _taos[i]; } 00175 inline void tao(int i, Unify_ECR *t) { assert(i<_n); _taos[i]=t; } 00176 inline Unify_ECR *taoR() const { assert(0<_m); return _taoR; } 00177 inline void taoR(Unify_ECR *r) { assert(0<_m); _taoR=r; } 00178 inline Unify_Pendings & pending() { return _pending; } 00179 void settype(int n, int m, Unify_ECR **t, Unify_ECR *r, bool ellipse); 00180 void addArg(int plus_n); 00181 inline bool leq(Lambda *o) const { return is_bottom() || equal(o); } 00182 bool equal(Lambda *o) const; 00183 void print() const; 00184 inline friend ostream & operator<<(ostream &o, const Lambda &l) { 00185 l.print(); return o; 00186 } 00187 00188 static Lambda * bottom(); 00189 }; // Lambda 00190 00191 class Unify_Size { 00192 bool _is_top; 00193 int _size; 00194 public: 00195 Unify_Size(int size) : _size(size), _is_top(size<=0 ? true : false) {} 00196 Unify_Size() : _size(0), _is_top(true) {} 00197 inline bool is_top() const { return _is_top; } 00198 inline int size() const { return _size; } 00199 inline bool leq(Unify_Size o) const { return _size==o.size() || o.is_top(); } 00200 inline bool equal(Unify_Size o) 00201 { return _size==o.size() && _is_top==o.is_top(); } 00202 string str() const; 00203 static int sizeOf(typeNode *ty); 00204 static int sizeOfAssign(threeAddrNode *t, Linker &, UnificationBasedPtr *); 00205 }; 00206 00207 class Unify_Parents { 00208 set<Unify_ECR*> _parents; 00209 bool _is_top; 00210 public: 00211 Unify_Parents(set<Unify_ECR*> parents) : _parents(parents), _is_top(false) {} 00212 Unify_Parents(bool top) : _is_top(top) {} 00213 inline bool is_top() const { return _is_top; } 00214 inline void top(bool t) { _is_top=t; } 00215 inline bool empty() const { return !_is_top && _parents.empty(); } 00216 inline bool equal(Unify_Parents o) 00217 { return _parents==o.parents() && _is_top==o.is_top(); } 00218 inline set<Unify_ECR*> & parents() { return _parents; } 00219 string str() const; 00220 }; 00221 //%} 00222 00223 //%{ /* UnifyType's types */ 00224 typedef enum { BOTTOM, SIMPLE, STRUCTURE, OBJECT, BLANK } Object_Typ; 00225 00226 typedef struct Unify_Simple { 00227 Alpha *alpha; 00228 Lambda *lambda; 00229 Unify_Size s; 00230 Unify_Parents p; 00231 Unify_Simple(Alpha *a, Lambda *l, Unify_Size _s, Unify_Parents _p) 00232 : alpha(a), lambda(l), s(_s), p(_p) { } 00233 } Unify_Simple; 00234 00235 typedef struct Unify_Structure { 00236 FieldOrder fo; 00237 FieldTypeOrder fto; 00238 EltMap m; 00239 Unify_Size s; 00240 Unify_Parents p; 00241 Unify_Structure(suespecNode *sue, EltMap _m, Unify_Size _s, Unify_Parents _p); 00242 Unify_Structure(FieldOrder _fo, FieldTypeOrder _fto, EltMap _m, Unify_Size _s, 00243 Unify_Parents _p) : fo(_fo), fto(_fto), m(_m), s(_s), p(_p){} 00244 Unify_ECR *get(declNode *field, Unify_ECR *container); 00245 string map_str(); 00246 string all_str(); 00247 } Unify_Structure; 00248 00249 typedef struct Unify_Object { 00250 Alpha *alpha; 00251 Lambda *lambda; 00252 Unify_Size s; 00253 Unify_Parents p; 00254 Unify_Object(Alpha *a, Lambda *l, Unify_Size _s, Unify_Parents _p) 00255 : alpha(a), lambda(l), s(_s), p(_p) {} 00256 } Unify_Object; 00257 00258 typedef struct Unify_Blank { 00259 Unify_Size s; 00260 Unify_Parents p; 00261 Unify_Blank(Unify_Size _s, Unify_Parents _p) : s(_s), p(_p) {} 00262 } Unify_Blank; 00263 //%} 00264 00265 class memoryBlock; 00266 00267 //%{ /* actual type */ 00268 class UnifyType { 00269 private: 00270 Unify_ECR *_ecr; 00271 int _id; 00272 static int id_count; 00273 union { 00274 Unify_Simple *simple; 00275 Unify_Structure *structure; 00276 Unify_Object *object; 00277 Unify_Blank *blank; 00278 } _tao; 00279 Object_Typ obj_typ; 00280 memoryBlock *_block; 00281 set<procNode*> _procs; // NEW: this type represent this set of procedures. 00282 00283 bool _is_bottom; 00284 00285 public: 00286 UnifyType() : obj_typ(BOTTOM), _is_bottom(true), _id(id_count++), _block(0) 00287 { _ecr=new Unify_ECR(this); } 00288 UnifyType(Unify_Simple *s) : obj_typ(SIMPLE),_is_bottom(false),_id(id_count++) 00289 { _block=0; _tao.simple=s; _ecr=new Unify_ECR(this); } 00290 UnifyType(Unify_Structure *s) : obj_typ(STRUCTURE), _is_bottom(false), 00291 _id(id_count++), _block(0) { _tao.structure=s; _ecr=new Unify_ECR(this); } 00292 UnifyType(Unify_Object *o) : obj_typ(OBJECT),_is_bottom(false),_id(id_count++) 00293 { _block=0; _tao.object=o; _ecr=new Unify_ECR(this); } 00294 UnifyType(Unify_Blank *b) : obj_typ(BLANK), _is_bottom(false), _id(id_count++) 00295 { _block=0; _tao.blank=b; _ecr=new Unify_ECR(this); } 00296 UnifyType(Unify_Blank *b, Unify_ECR *ecr) : obj_typ(BLANK), 00297 _is_bottom(false), _id(id_count++) { _block=0; _tao.blank=b; _ecr=ecr; } 00298 00299 inline Unify_ECR *ecr() const { if(_ecr) return _ecr->root(); return _ecr; } 00300 inline Unify_ECR *ecr_no_root() const { return _ecr; } 00301 inline void ecr(Unify_ECR *ecr) { _ecr=ecr; } 00302 inline bool is_bottom() const { return _is_bottom; } 00303 inline int id() const { return _id; } 00304 inline Object_Typ objTyp() const { return obj_typ; } 00305 inline memoryBlock *block() const { return _block; } 00306 inline void block(memoryBlock *b) { _block=b; } 00307 inline set<procNode*> & procs() { return _procs; } 00308 00309 inline Unify_Simple *simple() const 00310 { assert(obj_typ==SIMPLE); return _tao.simple; } 00311 inline Unify_Structure *structure() const 00312 { assert(obj_typ==STRUCTURE); return _tao.structure; } 00313 inline Unify_Object *object() const 00314 { assert(obj_typ==OBJECT); return _tao.object; } 00315 inline Unify_Blank *blank() const 00316 { assert(obj_typ==BLANK); return _tao.blank; } 00317 00318 inline bool leq(UnifyType *o, Unify_Size s) const 00319 { return this==o || s.leq(size()); } 00320 Unify_Size size() const; 00321 void print() const; 00322 inline friend ostream & operator<<(ostream &o, const UnifyType &t) { 00323 t.print(); return o; 00324 } 00325 00326 static UnifyType *toTao(UnifyType *t); 00327 static inline UnifyType *bottom() { return new UnifyType(); } 00328 }; // UnifyType 00329 00330 00331 #define T_bottom UnifyType::bottom() 00332 #define L_bottom Lambda::bottom() 00333 00334 //%} 00335 00336 class Unify_Pending { 00337 public: 00338 typedef enum { makeunknown, join_ECR, join_Lambda, cjoin, collapse } Typ; 00339 private: 00340 Typ _typ; 00341 void *_arg1, *_arg2, *_arg3; 00342 bool _served; 00343 public: 00344 Unify_Pending(Unify_ECR *e1, Unify_ECR *e2) : _typ(join_ECR), _arg1(e1), 00345 _arg2(e2), _arg3(NULL), _served(false) {} 00346 Unify_Pending(Lambda *l1, Lambda *l2) : _typ(join_Lambda), _arg1(l1), 00347 _arg2(l2), _arg3(NULL), _served(false) {} 00348 Unify_Pending(Unify_Offset *o) : _typ(makeunknown), _arg1(o), _arg2(NULL), 00349 _arg3(NULL), _served(false) {} 00350 Unify_Pending(Unify_ECR *e) : _typ(collapse), _arg1(e), _arg2(NULL), 00351 _arg3(NULL), _served(false) {} 00352 Unify_Pending(Unify_Size &s, Unify_ECR *e1, Unify_ECR *e2) : _typ(cjoin), 00353 _arg1(new Unify_Size(s)), _arg2(e1), _arg3(e2), _served(false) {} 00354 ~Unify_Pending() { if(_typ==cjoin) delete (Unify_Size*) _arg1; } 00355 inline Typ typ() const { return _typ; } 00356 inline void *arg1() const { return _arg1; } 00357 inline void *arg2() const { return _arg2; } 00358 inline void *arg3() const { return _arg3; } 00359 inline bool is_served() const { return _served; } 00360 inline void served() { _served=true; } 00361 inline void un_served() { _served=false; } 00362 void print() const; 00363 inline friend ostream & operator<<(ostream &o, const Unify_Pending &p) { 00364 p.print(); return o; 00365 } 00366 }; 00367 00368 typedef set<Unify_Pending*>::iterator Pendings_p; 00369 typedef set<UnifyType*> UnifyTypes; 00370 00371 class memoryModel; 00372 class stmtLocation; 00373 class procLocation; 00374 00375 class UnificationBasedPtr : public Walker { 00376 public: 00377 static UnificationBasedPtr *analyze_all(Linker &); 00378 00379 inline Unify_ECR *ecr(declNode *decl) const { 00380 if(_ecr.find(decl) != _ecr.end()) return _ecr.find(decl)->second; 00381 return NULL; 00382 } 00383 inline Unify_ECR *ecr(threeAddrNode *alloc_site) const { 00384 if(_alloc.find(alloc_site) != _alloc.end()) 00385 return _alloc.find(alloc_site)->second; 00386 return NULL; 00387 } 00388 inline UnifyType *proctype(procNode *p) { return _proctype[p]; } 00389 void createProcBlock(procNode *, memoryModel &, procLocation*); 00390 00391 // annotation mark this stmt as it create obj 00392 virtual void mark_alloc(stmtNode *stmt, declNode *source_decl, 00393 declNode *target_decl) {} 00394 00395 void ensure_no_bottom(Unify_ECR *tao, declNode *decl, 00396 UnifyType *parent); // new 00397 00398 virtual bool isField(declNode *f, bool &from_annotation) const { 00399 from_annotation = false; 00400 return _unique_field_defn.find(f) != _unique_field_defn.end(); 00401 } 00402 Unify_ECR *ecrField(UnifyType *container, declNode *field, 00403 bool field_from_annotation); 00404 Unify_ECR *ecrDeref(UnifyType *container); 00405 static bool reachable(UnifyType *src, UnifyTypes & targets, 00406 UnifyTypes & visited); 00407 00408 inline Alpha *string_alpha(constNode *con) { return _string_alpha[con]; } 00409 set<Unify_ECR*> unique_ecr() const; 00410 inline procNode *synthetic_proc(declNode *d) { return _synthetic_proc[d]; } 00411 static bool compatible_type(typeNode *, typeNode *); 00412 00413 void print_ecr(); 00414 00415 static int unify_points_to_max; 00416 00417 protected: 00418 TREE map<declNode*, Unify_ECR*> _ecr; 00419 TREE map<procNode*, UnifyType*> _proctype; 00420 TREE map<threeAddrNode*, Unify_ECR*> _alloc; // ecr for allocation sites 00421 TREE map<constNode*,Alpha*> _string_alpha; 00422 //#tmp vars created by diamantler 00423 TREE int _dismantler_tmp; 00424 00425 TREE map<declNode*, suespecNode*> _field2sue; 00426 TREE map<declNode*, decl_list> _fieldpos; 00427 00428 TREE set<suespecNode*> _unique_sue, //want only unique suespecNode 00429 _visited_sue; 00430 TREE map<declNode*, declNode*> _unique_field_defn; 00431 00432 map<threeAddrNode*,UnifyType*> _ptr_call; 00433 00434 unitNode *cur_unit; 00435 procNode *cur_proc; 00436 bool inside_call_func; 00437 bool finalizing, serve_again, new_pending; 00438 set<Unify_Pending*> more_pending; 00439 00440 Linker &linker; 00441 map<declNode*,procNode*> _synthetic_proc; 00442 set<procNode*> _analyzed_proc; //, _skip_proc; 00443 00444 class findVarAssign; // find number of times a variable is assigned to. 00445 map<declNode*,int> _assignments; 00446 map<declNode*,bool> _uses; // any use for this var? 00447 00448 UnificationBasedPtr(Linker &l) : Walker(Both,Subtree), cur_proc(0), 00449 inside_call_func(false), finalizing(false), serve_again(false), 00450 new_pending(true), linker(l), _dismantler_tmp(0) {} 00451 00452 void at_unit(unitNode *u, Order) { cur_unit = u; } 00453 void at_proc(procNode *, Order); 00454 void at_decl(declNode *, Order); 00455 void at_suespec(suespecNode *, Order); 00456 void at_threeAddr(threeAddrNode *, Order); 00457 00458 void at_allocation(threeAddrNode *, Unify_Size); 00459 void at_call(threeAddrNode *, Unify_Size); 00460 void at_initializer(initializerNode *init, typeNode *init_type, 00461 Unify_ECR *init_ecr); 00462 void mergeOperand(operandNode *lhs, operandNode *rhs, Unify_Size); 00463 00464 // condition to use alpha(): operand is addr(). 00465 Alpha *alpha(operandNode *, Unify_Size); 00466 // condition to use ecr(): opposite of alpha() above. 00467 Unify_ECR *ecr(operandNode *, Unify_Size, Unify_Offset **offset=NULL); 00468 // similar to ecr(declNode*) but if not found, attempt to create. 00469 Unify_ECR *ecr1(declNode *decl); 00470 00471 void join(Alpha *a1, Alpha *a2, bool *recursion_detected=NULL); 00472 void join(Unify_ECR *e1, Unify_ECR *e2, bool *recursion_detected=NULL); 00473 void join(Lambda *l1, Lambda *l2); // new 00474 void settype(Unify_ECR *e, UnifyType *t); 00475 void settype(Lambda *l, int n, int m, Unify_ECR **t, Unify_ECR *r, 00476 bool ellipse); 00477 void ensure_sim_obj(Unify_ECR *tao, Unify_Size &s); 00478 Unify_Structure *ensure_struct_obj(Unify_ECR *tao, suespecNode *sue, //new 00479 bool redo_pending = false); 00480 void expand(Unify_ECR *e); 00481 void promote(Unify_ECR *e, Unify_Size &s); 00482 void collapse(Unify_ECR *e); 00483 void make_unknown(Unify_Offset *o); 00484 void unless_zero(Unify_Offset *o, Unify_ECR *tao); 00485 void cjoin(Unify_Size &s, Unify_ECR *e1, Unify_ECR *e2); 00486 UnifyType *unify(UnifyType *t1, UnifyType *t2); 00487 bool make_compatible(declSet n, Unify_Structure *s, Unify_ECR *container, 00488 bool force=false); 00489 void merge_EltMap(/*IN*/ UnifyType *t1, UnifyType *t2, 00490 /*IN,OUT*/ Unify_Structure *); 00491 00492 void finalize(); 00493 00494 static bool is_va_list(declNode * decl); 00495 procNode *create_synthetic_proc(declNode *); 00496 00497 inline declNode *unique_field_defn(declNode *d) 00498 { return _unique_field_defn[d]; } 00499 inline suespecNode *field2sue(declNode *d) 00500 { return _field2sue[_unique_field_defn[d]]; } 00501 00502 // to be overwritten by subclass 00503 virtual bool annotation_returns_object(procNode *proc) const { return false; } 00504 virtual void annotation_call_arg(procNode*, int arg, typeNode*, Unify_ECR*) {} 00505 virtual void annotation_call_arg(procNode*, int arg, typeNode*, Alpha*) {} 00506 virtual void annotation_ret_val(procNode *, Unify_ECR *taoR, unitNode *unit){} 00507 virtual void annotation_init_global(declNode *global) {} 00508 }; // UnificationBasedPtr 00509 00510 #define is_Sim_Obj(t) assert(t->objTyp()==SIMPLE || t->objTyp()==OBJECT) 00511 #define Sim_Obj_Size(t) (t->objTyp()==SIMPLE ? t->simple()->s : t->object()->s) 00512 #define Sim_Obj_Lambda(t) \ 00513 (t->objTyp()==SIMPLE ? t->simple()->lambda : t->object()->lambda) 00514 #define Sim_Obj_Alpha(t) ((t->objTyp()==SIMPLE) ? t->simple()->alpha : t->object()->alpha) 00515 00516 00517 #endif |
Generated on February 1, 2006
Back to the C-Breeze home page