Polaris: cdg_types.h Source File

00001 ///
00002 /// $Documentation Manager$ = "Doxygen"
00003 ///
00004 /*!
00005   \file cdg_types.h
00006   \author Silvius Rus
00007   \date 9/19/00
00008   \brief This file contains definitions for data types used in the Control Dependence Graph (CDG).
00009 */
00010 ///
00011 #ifndef _cdg_types_h
00012 #define _cdg_types_h
00013 ///
00014 #include <vector.h>
00015 ///
00016 #include "Array.h"
00017 #include "Statement/Statement.h"
00018 ///
00019 class CDGNode;
00020 
00021 /*!
00022   \brief A pair of a CDG node and a truth value.
00023  */
00024 class CDElement: public Listable{
00025 
00026  private:
00027   CDGNode* _node;
00028   bool _value;
00029 
00030  public:
00031   CDElement();
00032   CDElement(CDGNode* n, bool v);
00033   ~CDElement();
00034 
00035   void node(CDGNode* n);
00036   CDGNode* node();
00037   void value(bool v);
00038   bool value();
00039 
00040   Listable* listable_clone() const;
00041   void print(ostream& o) const;
00042 };
00043 
00044 
00045 /*!
00046   \brief A set of CDElement's.
00047 
00048   Allows for equality and inclusion testing.  Elements are stored sorted by the address of their CDG node in memory.
00049  */
00050 class CDSet: public List<CDElement> {
00051 
00052  public:
00053   CDSet();
00054   CDSet(CDSet& another);
00055   ~CDSet();
00056 
00057   void ins(CDElement& e);   ///< Keep them sorted by node (use address as index).
00058   /*!
00059     \brief Tests for equality - same nodes AND same truth values.
00060    */
00061   bool operator==(CDSet& another);
00062   /*!
00063     \brief Tests for inclusion (considering the truth values also).
00064    */
00065   bool operator <=(CDSet& another);
00066 };
00067 
00068 /*!
00069   \brief The representatin of a CDG node.
00070  */
00071 class CDGNode: public Listable{
00072   
00073  private:
00074   /*!
00075     \brief Corresponding statement (Control Flow Graph node).
00076    */
00077   Statement* _cfgnode;
00078   /*!
00079     The CDG node that corresponds to the immediate postdominator of this statement in the CFG.
00080    */
00081   CDGNode* _ipdom_parent;
00082   /*!
00083     \brief The set of nodes that have myself as immediate postdominator.
00084    */
00085   vector<CDGNode*> _ipdom_children;
00086   /*!
00087     \brief The set of predecessors in the CDG (and their labels as truth values).
00088    */
00089   CDSet _ins;
00090   /*!
00091     \brief The set of successors in the CDG (and their labels as truth values).
00092    */
00093   CDSet _outs;
00094   /*!
00095     \brief A flag used for traversal.
00096    */
00097   int _visited;
00098 
00099  public:
00100   /*!
00101     \brief Builds an empty node.
00102    */
00103   CDGNode();  
00104   /*!
00105     \brief Builds a node and attaches it to the given statement.
00106    */
00107   CDGNode(Statement* stmt); 
00108   ~CDGNode();
00109   
00110   CDSet& ins();
00111   void ins(CDSet& cd);
00112   CDSet& outs();
00113   Statement* cfgnode();
00114   CDGNode* ipdom_parent();
00115   vector<CDGNode*>& ipdom_children();
00116   void ipdom_parent(CDGNode*);
00117   int visited();
00118   void visited(int);
00119 
00120   Listable* listable_clone() const;
00121   void print(ostream& o) const;
00122 };
00123 
00124 
00125 /*!
00126   \brief It defines an entry in a repository of CDSet's.
00127  */
00128 class CDRepositoryEntry: public Listable{
00129  public:
00130   CDSet cdset;
00131   CDGNode* rnode;
00132   CDRepositoryEntry(CDSet& cd, CDGNode* node);
00133   ~CDRepositoryEntry();
00134 
00135   Listable* listable_clone() const;
00136   void print(ostream& o) const;
00137 };
00138 
00139 
00140 /*!
00141   \brief It defines a repository of CDSet's.
00142 
00143   The current implementation uses a hash table.
00144  */
00145 class CDRepository: public Array<List<CDRepositoryEntry> >{
00146  private:
00147   int hash(CDSet& cd);
00148  public:
00149   CDRepository();
00150   CDRepository(int entries);
00151   ~CDRepository();
00152   
00153   void ins(CDSet& cd, CDGNode* node);
00154   CDGNode* lookup(CDSet& cd);
00155 };
00156 
00157 
00158 /*!
00159   \brief This data type was designed for grouping nodes into CD-equivalent regions.  It is currently not used.
00160  */
00161 class CDRegion: public Listable{
00162  private:
00163   CDSet _ins;
00164   CDSet _outs;
00165   CDSet _members;
00166   int _visited;
00167 
00168  public:
00169   CDRegion();
00170   ~CDRegion();
00171   CDSet& ins();
00172   CDSet& outs();
00173   CDSet& members();
00174 
00175   Listable* listable_clone() const;
00176   void print(ostream& o) const;
00177 };
00178 
00179 
00180 
00181 ///<   Implementation of inline methods
00182 
00183 
00184 ///< Class CDElement.
00185 
00186 inline CDElement::CDElement(){
00187   _node=0;
00188   _value=False;
00189 }
00190 
00191 inline CDElement::CDElement(CDGNode* n, bool v){
00192   _node=n;
00193   _value=v;
00194 }
00195 
00196 inline CDElement::~CDElement(){
00197 }
00198 
00199 
00200 inline void CDElement::node(CDGNode* n){
00201   _node=n;
00202 }
00203 
00204 inline CDGNode* CDElement::node(){
00205   return _node;
00206 }
00207 
00208 inline void CDElement::value(bool v){
00209   _value=v;
00210 }
00211 
00212 inline bool CDElement::value(){
00213   return _value;
00214 }
00215 
00216 inline Listable* CDElement::listable_clone() const{
00217   return (Listable*)new CDElement(_node,_value);
00218 }
00219 
00220 inline void CDElement::print(ostream& o) const{
00221   o<<"\nCDElement has node: "<<(void*)_node<<" and value ";
00222   if (_value) o<<"T.";
00223   else o<<"F";
00224 }
00225 
00226 
00227 
00228 ///< Class CDSet.
00229 inline CDSet::CDSet(){
00230 }
00231 
00232 inline CDSet::CDSet(CDSet& another)
00233   :List<CDElement>(another){
00234 }
00235 
00236 inline CDSet::~CDSet(){
00237 }
00238 
00239 
00240 
00241 ///< CDGNode.
00242 inline CDGNode::CDGNode(){
00243   _cfgnode=0;
00244   _ipdom_parent=0;
00245 }
00246 
00247 inline CDGNode::CDGNode(Statement* stmt){
00248   _ipdom_parent=0;
00249   _cfgnode=stmt;
00250 }
00251 
00252 inline CDGNode::~CDGNode(){
00253 }
00254   
00255 inline CDSet& CDGNode::ins(){
00256   return _ins;
00257 }
00258 
00259 inline void CDGNode::ins(CDSet& cd){
00260   _ins=cd;
00261   ///< Go to all cdg predecessors.
00262   for( Iterator<CDElement> cdit=_ins; cdit.valid(); ++cdit){
00263     CDElement& cd=cdit.current();
00264     ///< Insert myself in this predecessor's successor list.
00265     CDElement newcd(this,cd.value());
00266     cd.node()->outs().ins(newcd);
00267   }
00268 }
00269 
00270 
00271 inline CDSet& CDGNode::outs(){
00272   return _outs;
00273 }
00274 
00275 inline Statement* CDGNode::cfgnode(){
00276   return _cfgnode;
00277 }
00278 
00279 inline CDGNode* CDGNode::ipdom_parent(){
00280   return _ipdom_parent;
00281 }
00282 
00283 inline vector<CDGNode*>& CDGNode::ipdom_children(){
00284   return _ipdom_children;
00285 }
00286 
00287 inline void CDGNode::ipdom_parent(CDGNode* n){
00288   _ipdom_parent=n;
00289 }
00290 
00291 inline int CDGNode::visited(){
00292   return _visited;
00293 }
00294 
00295 inline void CDGNode::visited(int v){
00296   _visited=v;
00297 }
00298 
00299 inline Listable* CDGNode::listable_clone() const{
00300   CDGNode* to_return=new CDGNode;
00301   to_return->_cfgnode=_cfgnode;
00302   to_return->_ins=_ins;
00303   to_return->_outs=_outs;
00304   return (Listable*) to_return;
00305 }
00306 
00307 inline void CDGNode::print(ostream& o) const{
00308 
00309   o<<"\nCDGNode";
00310   o<<" corresponds to CFG node: ";
00311   o<<_cfgnode->tag()<<".";
00312   o<<"\nAddress: "<<(void*)this;
00313   o<<"\nIns:";
00314   o<<_ins;
00315   o<<"\nOuts:";
00316   o<<_outs;
00317 }
00318 
00319 
00320 inline CDRepositoryEntry::CDRepositoryEntry(CDSet& cd, CDGNode* node){
00321   cdset=cd;
00322   rnode=node;
00323 }
00324 
00325 inline CDRepositoryEntry::~CDRepositoryEntry(){
00326 }
00327 
00328 inline Listable* CDRepositoryEntry::listable_clone() const{
00329   return (Listable*) new CDRepositoryEntry((CDSet&)cdset,rnode);
00330 }
00331 
00332 inline void CDRepositoryEntry::print(ostream& o) const{
00333   o<<"\nCDRepositoryEntry is:";
00334   cdset.print(o);
00335   if(rnode) rnode->print(o);
00336 }
00337 
00338 
00339 
00340 inline CDRepository::CDRepository(){
00341 }
00342 
00343 inline CDRepository::CDRepository(int entries)
00344   :Array<List<CDRepositoryEntry> >(entries){
00345 }
00346 
00347 inline CDRepository::~CDRepository(){
00348 }
00349 
00350 
00351 inline CDRegion::CDRegion(){
00352 }
00353 
00354 inline CDRegion::~CDRegion(){
00355 }
00356 
00357 inline CDSet& CDRegion::ins(){
00358   return _ins;
00359 }
00360 
00361 inline CDSet& CDRegion::outs(){
00362   return _outs;
00363 }
00364 
00365 inline CDSet& CDRegion::members(){
00366   return _members;
00367 }
00368 
00369 inline Listable* CDRegion::listable_clone() const{
00370   CDRegion* to_ret=new CDRegion;
00371   to_ret->_ins=_ins;
00372   to_ret->_outs=_outs;
00373   return (Listable*) to_ret;
00374 }
00375 
00376 inline void CDRegion::print(ostream& o) const{
00377   o<<"\nCDRegion::print:\nIns:";
00378   _ins.print(o);
00379   o<<"\nOuts:";
00380   _outs.print(o);
00381 }
00382 
00383 
00384 
00385 #endif