Open64: osprey/be/cg/SL/pqs.h Source File

00001 /*
00002 
00003   Copyright (C) 2000, 2001 Silicon Graphics, Inc.  All Rights Reserved.
00004 
00005   This program is free software; you can redistribute it and/or modify it
00006   under the terms of version 2 of the GNU General Public License as
00007   published by the Free Software Foundation.
00008 
00009   This program is distributed in the hope that it would be useful, but
00010   WITHOUT ANY WARRANTY; without even the implied warranty of
00011   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  
00012 
00013   Further, this software is distributed without any warranty that it is
00014   free of the rightful claim of any third person regarding infringement 
00015   or the like.  Any license provided herein, whether implied or 
00016   otherwise, applies only to this software file.  Patent licenses, if 
00017   any, provided herein do not apply to combinations of this program with 
00018   other software, or any other product whatsoever.  
00019 
00020   You should have received a copy of the GNU General Public License along
00021   with this program; if not, write the Free Software Foundation, Inc., 59
00022   Temple Place - Suite 330, Boston MA 02111-1307, USA.
00023 
00024   Contact information:  Silicon Graphics, Inc., 1600 Amphitheatre Pky,
00025   Mountain View, CA 94043, or:
00026 
00027   http://www.sgi.com
00028 
00029   For further information regarding this notice, see:
00030 
00031   http://oss.sgi.com/projects/GenInfo/NoticeExplan
00032 
00033 */
00034 
00035 
00036 #ifndef PQS_H_INCLUDED
00037 #define PQS_H_INCLUDED
00038 
00039 #ifndef PQSTEST
00040 #define PQS_USE_MEMPOOLS
00041 #endif
00042 
00043 // Tracing variable
00044 extern BOOL PQS_Tracing;
00045 
00046 #ifdef PQS_USE_MEMPOOLS
00047 // Mempool variable
00048 extern MEM_POOL PQS_mem_pool;
00049 extern void PQS_Init_Memory(void);
00050 #endif
00051  
00052 /*================================================================
00053 //================================================================
00054 
00055 Vectors of PQS_NODEs
00056 
00057 //================================================================
00058 */
00059 
00060 #ifdef PQS_USE_MEMPOOLS
00061 typedef mempool_allocator<PQS_NODE_IDX> PQS_NODE_IDX_ALLOCATOR;
00062 #else
00063 typedef alloc PQS_NODE_IDX_ALLOCATOR;
00064 #endif
00065 
00066 typedef vector<PQS_NODE_IDX,PQS_NODE_IDX_ALLOCATOR> PQS_NODE_IDX_VECTOR;
00067 
00068 
00069 /*================================================================
00070 //================================================================
00071 //================================================================
00072 */
00073 
00074 // Pairs of index and TN.
00075 typedef pair<PQS_NODE_IDX,PQS_TN> PQS_TNI;
00076 #define PQS_TNI_TN(x) ((x).second)
00077 #define PQS_TNI_IDX(x) ((x).first)
00078 
00079 struct lt_tni {
00080    inline bool operator()(const PQS_TNI &t1, const PQS_TNI &t2) const {
00081       if (PQS_TNI_TN(t1) == PQS_TNI_TN(t2)) {
00082    return PQS_TNI_IDX(t1) < PQS_TNI_IDX(t2);
00083       } else {
00084    return TN_number(PQS_TNI_TN(t1)) < TN_number(PQS_TNI_TN(t2));
00085       }
00086    }
00087 };
00088 
00089 typedef PQS_SET<PQS_TNI,lt_tni> PQS_TNI_SET;
00090 typedef PQS_SET<PQS_TNI,lt_tni>::set_type PQS_TNI_SET_TYPE;
00091 
00092 //================================================================
00093 //================================================================
00094 //================================================================
00095 /* This is the definition of the NODE class 
00096  */
00097 
00098 class PQS_NODE {
00099 friend class PQS_MANAGER;
00100 private:
00101 // Data members
00102    PQS_OP    _inst;                    // pointer to actual instruction setting things
00103    PQS_ITYPE _itype;                   // Style of the instruction (i.e. UNC, OR,  AND, etc.)
00104    PQS_TN       out_pred1,out_pred2;   // Points to the TN's for the predicates set by the instruction
00105    PQS_NODE_IDX in_pred1,in_pred2;     // Nodes for the instructions setting previous instances
00106    PQS_NODE_IDX qual_pred;             // Node for the qualifying predicate
00107    PQS_TN       qual_tn;               // TN of the qualifying predicate
00108    PQS_NODE_IDX other_instruction;     // Pointer to another instruction having the same condition
00109    PQS_NODE_IDX_VECTOR use1,use2;
00110    PQS_NODE_FLAGS flags;               // Miscellaneous flags
00111 
00112    PQS_MARKER_TYPE _marker1,_marker2;        // For tree walks
00113    void Init(void);
00114 
00115 public:
00116    PQS_NODE()
00117 #ifdef PQS_USE_MEMPOOLS
00118       : use1(PQS_NODE_IDX_VECTOR::allocator_type(&PQS_mem_pool)),
00119   use2(PQS_NODE_IDX_VECTOR::allocator_type(&PQS_mem_pool)) 
00120 #endif
00121    {
00122       Init();
00123    }
00124    PQS_NODE(PQS_ITYPE itype, PQS_OP inst)
00125 #ifdef PQS_USE_MEMPOOLS
00126       : use1(PQS_NODE_IDX_VECTOR::allocator_type(&PQS_mem_pool)),
00127   use2(PQS_NODE_IDX_VECTOR::allocator_type(&PQS_mem_pool)) 
00128 #endif
00129    {
00130       Init();
00131       _inst = inst;
00132       _itype = itype;
00133    }
00134 
00135    ~PQS_NODE(){};
00136 
00137    void add_use(PQS_TN tn, PQS_NODE_IDX idx);
00138    inline INT32 num_use1() { return use1.size(); }
00139    inline INT32 num_use2() { return use2.size(); }
00140    inline PQS_NODE_IDX get_use1(INT32 i) { Is_True((i>=0 && i<num_use1()),("Bad i")); return use1[i]; }
00141    inline PQS_NODE_IDX get_use2(INT32 i) { Is_True((i>=0 && i<num_use2()),("Bad i")); return use2[i]; }
00142    
00143    inline PQS_MARKER_TYPE Get_Marker1(void) {return _marker1;}
00144    inline PQS_MARKER_TYPE Get_Marker2(void) {return _marker2;}
00145    inline void Set_Marker1(PQS_MARKER_TYPE m) {_marker1 = m;}
00146    inline void Set_Marker2(PQS_MARKER_TYPE m) {_marker2 = m;}
00147    inline void Set_Flags(PQS_NODE_FLAGS f) {flags = f;}
00148    inline PQS_NODE_FLAGS Get_Flags(void) {return flags;}
00149 
00150    void Print(FILE *f=stdout);
00151 };
00152 
00153 #ifdef PQS_USE_MEMPOOLS
00154 typedef mempool_allocator<PQS_NODE> PQS_NODE_ALLOCATOR;
00155 #else
00156 typedef alloc PQS_NODE_ALLOCATOR;
00157 #endif
00158 typedef vector <PQS_NODE,PQS_NODE_ALLOCATOR> PQS_NODE_VECTOR;
00159 
00160 class PQS_MANAGER {
00161 private:
00162    PQS_NODE_VECTOR _data;
00163    PQS_MARKER_TYPE _mark_number;
00164 
00165    BOOL PQS_is_disjoint_helper(PQS_NODE_IDX tni2, PQS_TN tn2);
00166    PQS_TRUTH never_true_together(PQS_TN t1, PQS_TN t2, PQS_NODE_IDX tni);
00167    BOOL may_set_TRUE(PQS_NODE_IDX tni, PQS_TN tn);
00168    BOOL may_set_FALSE(PQS_NODE_IDX tni, PQS_TN tn);
00169    BOOL always_set_TRUE(PQS_NODE_IDX tni, PQS_TN tn);
00170    BOOL always_set_FALSE(PQS_NODE_IDX tni, PQS_TN tn);
00171    BOOL never_set_TRUE(PQS_NODE_IDX tni, PQS_TN tn);
00172    BOOL never_set_FALSE(PQS_NODE_IDX tni, PQS_TN tn);
00173    BOOL may_set_TRUE(INT32 truth);
00174    BOOL may_set_FALSE(INT32 truth);
00175    BOOL never_set_TRUE(INT32 truth);
00176    BOOL never_set_FALSE(INT32 truth);
00177    BOOL always_set_TRUE(INT32 truth);
00178    BOOL always_set_FALSE(INT32 truth);
00179    BOOL qual_always_true(INT32 truth);
00180    INT32  get_truth_info(PQS_NODE_IDX tni, PQS_TN tn);
00181    BOOL PQS_is_subset_of(PQS_NODE_IDX tni1, PQS_TN tn1, PQS_NODE_IDX tni2, PQS_TN tn2);
00182    BOOL PQS_is_subset_of(PQS_NODE_IDX tni1, PQS_TN tn1, PQS_TN_SET &tns2);
00183    BOOL PQS_is_disjoint (PQS_NODE_IDX tni1, PQS_NODE_IDX tni2, PQS_TN tn1, PQS_TN tn2);
00184    BOOL PQS_is_disjoint_h (PQS_NODE_IDX tni1, PQS_NODE_IDX tni2, PQS_TN tn1, PQS_TN tn2);
00185    void PQS_Mark_TN_Parents_TRUE(PQS_NODE_IDX tni, PQS_TN tn);
00186    void PQS_Mark_TN_Parents_TRUE(PQS_TN tn);
00187    PQS_TN_SET Simplify_TN_Set (const PQS_TN_SET &tn_in);
00188    void Simplify_TNI_Set (PQS_TNI_SET &tni_in);
00189    BOOL Simplify_In_Set(PQS_NODE_IDX tni, PQS_TN tn, PQS_TNI_SET &tnis);
00190    void Init_TN_OP_Info(void);
00191 
00192 public:
00193 
00194    PQS_MANAGER()
00195 #ifdef PQS_USE_MEMPOOLS
00196       : _data(&PQS_mem_pool)
00197 #endif
00198    {
00199       PQS_NODE dummy;
00200       _mark_number=0;
00201       _data.push_back(dummy);
00202       Init_TN_OP_Info();
00203    }
00204 
00205    ~PQS_MANAGER();
00206 
00207 #ifndef PQSTEST
00208    TN_MAP PQS_tn_map;
00209    OP_MAP PQS_op_map;
00210 #endif   
00211    
00212    inline PQS_MARKER_TYPE Current_Marker() {return _mark_number;}
00213    inline void Update_Marker(void) {++_mark_number;}
00214    inline void Set_Manager_Marker(PQS_MARKER_TYPE mark) {_mark_number = mark;}
00215 
00216    inline PQS_NODE_IDX New_pqs_idx(PQS_ITYPE itype, PQS_OP inst); 
00217 
00218    // Accessors
00219    inline void PQS_NODE_set_out_pred1(PQS_NODE_IDX i, PQS_TN p1) {_data[i].out_pred1 = p1;}
00220    inline void PQS_NODE_set_itype(PQS_NODE_IDX i, PQS_ITYPE itype) {_data[i]._itype = itype;}
00221    inline void PQS_NODE_set_out_pred2(PQS_NODE_IDX i, PQS_TN p2) {_data[i].out_pred2 = p2;}
00222    inline void PQS_NODE_set_in_pred1(PQS_NODE_IDX i, PQS_NODE_IDX p1) {_data[i].in_pred1 = p1;}
00223    inline void PQS_NODE_set_in_pred2(PQS_NODE_IDX i, PQS_NODE_IDX p2) {_data[i].in_pred2 = p2;}
00224    inline void PQS_NODE_set_qual_pred(PQS_NODE_IDX i, PQS_NODE_IDX p1) {_data[i].qual_pred = p1;}
00225    inline void PQS_NODE_set_qual_tn(PQS_NODE_IDX i, PQS_TN t) {_data[i].qual_tn = t;}
00226    inline void PQS_NODE_add_use(PQS_NODE_IDX i, PQS_TN p, PQS_NODE_IDX use) {
00227       if (PQS_Is_Real_Idx(i)) _data[i].add_use(p,use);
00228    }
00229    inline void PQS_NODE_Mark(PQS_NODE_IDX i) {
00230       _data[i].Set_Marker1(_mark_number);
00231       _data[i].Set_Marker2(_mark_number);
00232    }
00233    inline void PQS_NODE_Mark(PQS_NODE_IDX i,PQS_TN t) {
00234       // set the marker for the specific TN t
00235       if (_data[i].out_pred1 == t) _data[i].Set_Marker1(_mark_number);
00236       if (_data[i].out_pred2 == t) _data[i].Set_Marker2(_mark_number);
00237    }
00238    inline void PQS_NODE_set_flags(PQS_NODE_IDX i,PQS_NODE_FLAGS f) {_data[i].flags=f;}
00239    inline void PQS_NODE_set_condition_true(PQS_NODE_IDX i) {_data[i].flags |= PQS_FLAG_CONDITION_TRUE;}
00240    inline void PQS_NODE_set_condition_false(PQS_NODE_IDX i) {_data[i].flags |= PQS_FLAG_CONDITION_FALSE;}
00241    
00242    // getters
00243 
00244    inline PQS_OP PQS_NODE_get_op(PQS_NODE_IDX i) {      return _data[i]._inst;   }
00245    inline PQS_ITYPE PQS_NODE_get_itype(PQS_NODE_IDX i) {      return _data[i]._itype;   }
00246    inline PQS_TN PQS_NODE_get_out_pred1(PQS_NODE_IDX i) {      return _data[i].out_pred1;   }
00247    inline PQS_TN PQS_NODE_get_out_pred2(PQS_NODE_IDX i) {      return _data[i].out_pred2;   }
00248    inline PQS_NODE_IDX PQS_NODE_get_in_pred1(PQS_NODE_IDX i) {      return _data[i].in_pred1;   }
00249    inline PQS_NODE_IDX PQS_NODE_get_in_pred2(PQS_NODE_IDX i) {      return _data[i].in_pred2;   }
00250    inline PQS_TN PQS_NODE_get_qual_tn(PQS_NODE_IDX i) {      return _data[i].qual_tn;   }
00251    inline PQS_NODE_IDX PQS_NODE_get_qual_pred(PQS_NODE_IDX i) {      return _data[i].qual_pred;   }
00252    inline INT32 PQS_NODE_num_use1(PQS_NODE_IDX i) {      return _data[i].num_use1();   }
00253    inline INT32 PQS_NODE_num_use2(PQS_NODE_IDX i) {     return _data[i].num_use2();   }
00254    inline PQS_NODE_IDX PQS_NODE_get_use1(PQS_NODE_IDX i,INT32 num) {      return _data[i].get_use1(num);   }
00255    inline PQS_NODE_IDX PQS_NODE_get_use2(PQS_NODE_IDX i,INT32 num) {      return _data[i].get_use2(num);   }
00256    inline BOOL Is_Marked(PQS_NODE_IDX i) {return (_mark_number == _data[i]._marker1 || _mark_number == _data[i]._marker2);
00257    }
00258 
00259    inline BOOL Is_Marked1(PQS_NODE_IDX i) {return (_mark_number == _data[i]._marker1);}
00260    inline BOOL Is_Marked2(PQS_NODE_IDX i) {return (_mark_number == _data[i]._marker2);}
00261 
00262    inline PQS_MARKER_TYPE PQS_NODE_get_marker(PQS_NODE_IDX i, INT32 num) { 
00263       if (num==1) return _data[i].Get_Marker1();
00264       else return _data[i].Get_Marker2();
00265    }
00266    inline PQS_NODE_FLAGS PQS_NODE_get_flags(PQS_NODE_IDX i) {return _data[i].flags;}
00267    inline BOOL PQS_NODE_condition_true(PQS_NODE_IDX i) {return (_data[i].flags & PQS_FLAG_CONDITION_TRUE) != 0;}
00268    inline BOOL PQS_NODE_condition_false(PQS_NODE_IDX i) {return (_data[i].flags & PQS_FLAG_CONDITION_FALSE) != 0;}
00269 
00270 
00271    // Utility
00272    
00273    // given an index and a TN, return the index of the previous instance
00274    inline PQS_NODE_IDX PQS_NODE_get_up_idx(PQS_NODE_IDX i, PQS_TN t)
00275    {
00276       if (PQS_NODE_get_out_pred1(i) == t) {
00277    return PQS_NODE_get_in_pred1(i);
00278       } else if (PQS_NODE_get_out_pred2(i) == t) {
00279    return PQS_NODE_get_in_pred2(i);
00280       } else {
00281    FmtAssert(0,("get_up_idx: malformed idx %d\n",i));
00282    return PQS_IDX_INVALID;
00283       }
00284    }
00285    
00286   
00287    // given an index and a TN, return whether this is the TN in the 1 slot or the TN in the 2 slot
00288    inline INT32 PQS_NODE_get_1_2(PQS_NODE_IDX i, PQS_TN t) {
00289       if (PQS_NODE_get_out_pred1(i) == t) {
00290    return 1;
00291       } else if (PQS_NODE_get_out_pred2(i) == t) {
00292    return 2;
00293       } 
00294       FmtAssert(0,("get_1_2: malformed idx %d\n",i));
00295       return 0;
00296    }
00297 
00298    // Get the other TN in an index
00299    inline PQS_TN PQS_NODE_get_other_tn(PQS_NODE_IDX i, PQS_TN t) {
00300       if (PQS_NODE_get_out_pred1(i) == t) {
00301    return PQS_NODE_get_out_pred2(i);
00302       } else if (PQS_NODE_get_out_pred2(i) == t) {
00303    return PQS_NODE_get_out_pred1(i);
00304       }
00305       FmtAssert(0,("get_other: malformed idx %d\n",i));
00306       return 0;
00307    }
00308 
00309 
00310    // Global functions
00311   
00312    void Print_all(FILE *f=stdout);
00313    void Print_idx(PQS_NODE_IDX idx, FILE *f=stdout);
00314 
00315    BOOL PQS_is_disjoint(PQS_TN tn1, PQS_TN tn2);
00316    BOOL PQS_is_disjoint(PQS_TN_SET &tns1, PQS_TN_SET &tns2);
00317    
00318    BOOL PQS_is_subset_of (PQS_TN tn1, PQS_TN tn2);
00319    BOOL PQS_is_subset_of (PQS_TN tn1, PQS_TN_SET &tns2);
00320    BOOL PQS_is_subset_of (PQS_TN_SET &tns1, PQS_TN_SET &tns2);
00321 
00322    PQS_NODE_IDX PQS_Add_Instruction (PQS_OP inst);
00323 
00324    // The dedicated P0 TN
00325    PQS_TN PQS_TN_P0;
00326 
00327 };
00328 
00329 #endif
00330 
00331 // Local Variables:
00332 // mode:C++
00333 // End: