Open64: osprey/be/cg/SL/pqs.cxx 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 /*================================================================
00037 
00038 This file implements the predicate query system
00039 
00040 Key assumptions and requirements:
00041 
00042 1) the PQS data structures are built once, and maintained as needed. 
00043 
00044 2) Any predicate TN which is defined more than once is subject to the following two 
00045 restrictions:
00046   A) All definitions are in the same basic block.
00047   B) There is no use of the TN as a qualifying predicate in between the first definition
00048      and the last definition. This restriction allows the PQS to not have to keep around instance
00049      numbers for each use of a predicate register, and simplifies things considerably. 
00050 
00051 
00052 ================================================================*/
00053 
00054 
00055 #ifndef PQSTEST
00056 #include "defs.h"
00057 #include "pqs_defs.h"
00058 #include "pqs_cg.h"
00059 #include "pqs_cg_ia64.h"
00060 #include "mempool.h"
00061 #include "mempool_allocator.h"
00062 #include "tracing.h"
00063 
00064 #else
00065 #include "pqstest.h"
00066 #include "pqs_defs.h"
00067 #include "pqsstubs.h"
00068 
00069 #endif
00070 
00071 #include "pqs.h"
00072 
00073 #ifdef PQS_USE_MEMPOOLS
00074 // Mempool variable
00075 MEM_POOL PQS_mem_pool;
00076 static BOOL pqs_mempool_init=FALSE;
00077 
00078 // Memory initialization
00079 void PQS_Init_Memory(void)
00080 {
00081   if (pqs_mempool_init) return;
00082   pqs_mempool_init = TRUE;
00083   MEM_POOL_Initialize(&PQS_mem_pool,"PQS_mem_pool",FALSE);
00084   MEM_POOL_Push(&PQS_mem_pool);
00085 }
00086 #endif
00087 
00088 
00089 // Values used internally for implementation of setting inquiry routines
00090 enum truth_val {
00091    TRUTH_UNKNOWN=0,
00092    TRUTH_MAY_SET_TRUE=1,
00093    TRUTH_MAY_SET_FALSE=2,
00094    TRUTH_ALWAYS_SET_TRUE=4,
00095    TRUTH_ALWAYS_SET_FALSE=8,
00096    TRUTH_NEVER_SET_TRUE=16,
00097    TRUTH_NEVER_SET_FALSE=32,
00098    TRUTH_QUAL_PRED_TRUE=64
00099 };
00100 
00101 //================================================================
00102 
00103 template<> void
00104 PQS_TN_SET::Print(FILE *f,BOOL newline)
00105 {
00106   PQS_TN_SET_TYPE::iterator p;
00107 
00108   fprintf(f,"{ ");
00109   p = _set.begin();
00110   while (p != _set.end()) {
00111     fprintf(f,"%d ",TN_number(*p));
00112     ++p;
00113   }
00114   fprintf(f,"}");
00115   if (newline) fprintf(f,"\n");
00116 }
00117 
00118 template<> void
00119 PQS_TNI_SET::Print(FILE *f, BOOL newline)
00120 {
00121   PQS_TNI_SET::set_iterator_type p;
00122   
00123   fprintf(f,"{ ");
00124   p = _set.begin();
00125   while (p != _set.end()) {
00126     fprintf(f,"<%d,TN%d> ",PQS_TNI_IDX(*p),TN_number(PQS_TNI_TN(*p)));
00127     ++p;
00128   }
00129   fprintf(f,"}");
00130   if (newline) fprintf(f,"\n");
00131 }
00132 
00133 /*****************************************************************
00134 
00135 static inline BOOL
00136 PQS_ITYPE_sets_unconditionally(PQS_ITYPE itype) 
00137 
00138 Returns true if the instruction type always sets its P reg outputs.
00139 
00140 ****************************************************************/
00141 
00142 static inline BOOL
00143 PQS_ITYPE_sets_unconditionally(PQS_ITYPE itype) 
00144 {
00145    return (itype == PQS_ITYPE_UNC || itype == PQS_ITYPE_DIVSQRT);
00146 }
00147 
00148 
00149 /*================================================================
00150   Check a TN set for all valid queriable entries
00151   returns TRUE if any of the elements is marked no_query.
00152   ==================================================================
00153 */
00154 static BOOL check_for_unqueriable(const PQS_TN_SET &t)
00155 {
00156    BOOL result = FALSE;
00157    PQS_TN_SET::set_iterator_type p;
00158    
00159    for (p = t.begin(); !result && p != t.end(); p++) {
00160       result |= PQS_TN_no_query(*p);
00161    }
00162    return (result);
00163 }
00164 
00165 
00166 /*================================================================
00167 
00168 Infrastructure routines, not inplemented in
00169 the header file since they are only called here.
00170 
00171 ================================================================
00172 */
00173 
00174 inline PQS_NODE_IDX
00175 PQS_MANAGER::New_pqs_idx(PQS_ITYPE itype, PQS_OP inst) {
00176    PQS_NODE new_node(itype,inst);
00177    _data.push_back(new_node);
00178    return (_data.size() - 1);
00179 }
00180 
00181 
00182 // Set up the contents of a PQS_NODE
00183 void
00184 PQS_NODE::Init()
00185 {
00186    _inst = NULL;
00187    _itype = PQS_ITYPE_INVALID;
00188    in_pred1 = in_pred2 = PQS_IDX_NONE;
00189    qual_pred = PQS_IDX_NONE;
00190    qual_tn = NULL;
00191    out_pred1 = out_pred2 = NULL;
00192    other_instruction = PQS_IDX_NONE;
00193    flags = 0;
00194    _marker1 = 0;
00195    _marker2 = 0;
00196 }
00197 
00198 // Adds a use of a TN/idx pair to a node.
00199 void
00200 PQS_NODE::add_use(PQS_TN tn, PQS_NODE_IDX idx) {
00201    if (tn == out_pred1) {
00202       use1.push_back(idx);
00203    } else if (tn == out_pred2) {
00204       use2.push_back(idx);
00205    } else {
00206       FmtAssert(0,("PQS_NODE::add_use: no uses of TN"));
00207    }
00208 }
00209 
00210 
00211 /*****************************************************************
00212 
00213 inline BOOL
00214 PQS_MANAGER::may_set_TRUE(PQS_NODE_IDX tni, PQS_TN tn)
00215 PQS_MANAGER::may_set_FALSE(PQS_NODE_IDX tni, PQS_TN tn)
00216 PQS_MANAGER::never_set_TRUE(PQS_NODE_IDX tni, PQS_TN tn)
00217 PQS_MANAGER::never_set_FALSE(PQS_NODE_IDX tni, PQS_TN tn)
00218 PQS_MANAGER::always_set_TRUE(PQS_NODE_IDX tni, PQS_TN tn)
00219 PQS_MANAGER::always_set_FALSE(PQS_NODE_IDX tni, PQS_TN tn)
00220 
00221 PQS_MANAGER::may_set_TRUE(INT32 truth)
00222 PQS_MANAGER::may_set_FALSE(INT32 truth)
00223 PQS_MANAGER::never_set_TRUE(INT32 truth)
00224 PQS_MANAGER::never_set_FALSE(INT32 truth)
00225 PQS_MANAGER::always_set_TRUE(INT32 truth)
00226 PQS_MANAGER::always_set_FALSE(INT32 truth)
00227 PQS_MANAGER::qual_always_true(INT32 truth)
00228 
00229 Queries about what a predicate setting instruction might do to a TN
00230 The "always" should be understood to mean "subject to a TRUE qualifying predicate."
00231 
00232 ****************************************************************/
00233 
00234 BOOL
00235 PQS_MANAGER::may_set_TRUE(PQS_NODE_IDX tni, PQS_TN tn)
00236 {
00237    INT32 truth = get_truth_info(tni,tn);
00238    return (truth & TRUTH_MAY_SET_TRUE) != 0;
00239 }
00240 
00241 BOOL
00242 PQS_MANAGER::may_set_FALSE(PQS_NODE_IDX tni, PQS_TN tn)
00243 {
00244    INT32 truth = get_truth_info(tni,tn);
00245    return (truth & TRUTH_MAY_SET_FALSE) != 0;
00246 }
00247 
00248 BOOL
00249 PQS_MANAGER::never_set_TRUE(PQS_NODE_IDX tni, PQS_TN tn)
00250 {
00251    INT32 truth = get_truth_info(tni,tn);
00252    return (truth & TRUTH_NEVER_SET_TRUE) != 0;
00253 }
00254 
00255 BOOL
00256 PQS_MANAGER::never_set_FALSE(PQS_NODE_IDX tni, PQS_TN tn)
00257 {
00258    INT32 truth = get_truth_info(tni,tn);
00259    return (truth & TRUTH_NEVER_SET_FALSE) != 0;
00260 }
00261 
00262 BOOL
00263 PQS_MANAGER::always_set_TRUE(PQS_NODE_IDX tni, PQS_TN tn)
00264 {
00265    INT32 truth = get_truth_info(tni,tn);
00266    return (truth & TRUTH_ALWAYS_SET_TRUE) != 0;
00267 }
00268 
00269 BOOL
00270 PQS_MANAGER::always_set_FALSE(PQS_NODE_IDX tni, PQS_TN tn)
00271 {
00272    INT32 truth = get_truth_info(tni,tn);
00273    return (truth & TRUTH_ALWAYS_SET_FALSE) != 0;
00274 }
00275 
00276 BOOL
00277 PQS_MANAGER::may_set_TRUE(INT32 truth)
00278 {
00279    return (truth & TRUTH_MAY_SET_TRUE) != 0;
00280 }
00281 
00282 BOOL
00283 PQS_MANAGER::may_set_FALSE(INT32 truth)
00284 {
00285    return (truth & TRUTH_MAY_SET_FALSE) != 0;
00286 }
00287 
00288 BOOL
00289 PQS_MANAGER::never_set_TRUE(INT32 truth)
00290 {
00291    return (truth & TRUTH_NEVER_SET_TRUE) != 0;
00292 }
00293 
00294 BOOL
00295 PQS_MANAGER::never_set_FALSE(INT32 truth)
00296 {
00297    return (truth & TRUTH_NEVER_SET_FALSE) != 0;
00298 }
00299 
00300 BOOL
00301 PQS_MANAGER::always_set_TRUE(INT32 truth)
00302 {
00303    return (truth & TRUTH_ALWAYS_SET_TRUE) != 0;
00304 }
00305 
00306 BOOL
00307 PQS_MANAGER::always_set_FALSE(INT32 truth)
00308 {
00309    return (truth & TRUTH_ALWAYS_SET_FALSE) != 0;
00310 }
00311 
00312 BOOL
00313 PQS_MANAGER::qual_always_true(INT32 truth)
00314 {
00315    return (truth & TRUTH_QUAL_PRED_TRUE) != 0;
00316 }
00317 
00318 /****************************************************************/
00319 
00320 #define SET_RESULT12(t1,t2,t3,t4,t5,t6) \
00321        if (one_or_two == 1) { \
00322     if (always_false) { \
00323        result |= (t1); \
00324     } else if (always_true) {\
00325        result |= (t2);\
00326     } else {\
00327        result |= (t3);\
00328     }\
00329        } else {\
00330     if (always_false) {\
00331        result |= (t4);\
00332     } else if (always_true) {\
00333        result |= (t5);\
00334     } else {\
00335        result |= (t6);\
00336     }\
00337        }
00338 
00339 #define SET_RESULT(t1,t2,t3) \
00340     if (always_false) { \
00341        result |= (t1); \
00342     } else if (always_true) {\
00343        result |= (t2);\
00344     } else {\
00345        result |= (t3);\
00346     }
00347 
00348 
00349 /*****************************************************************
00350 
00351 INT32
00352 PQS_MANAGER::get_truth_info(PQS_NODE_IDX tni, PQS_TN tn)
00353 
00354 Return a truth value indicating what the instruction may do. 
00355 Tn must be set by the node tni.
00356 
00357 ****************************************************************/
00358 INT32
00359 PQS_MANAGER::get_truth_info(PQS_NODE_IDX tni, PQS_TN tn)
00360 {
00361    INT32 result = TRUTH_UNKNOWN;
00362    BOOL always_true = PQS_NODE_condition_true(tni);
00363    BOOL always_false = PQS_NODE_condition_false(tni);
00364    PQS_ITYPE itype = PQS_NODE_get_itype(tni);
00365    INT32  one_or_two = PQS_NODE_get_1_2(tni,tn);
00366    BOOL qual_is_true = (PQS_NODE_get_qual_pred(tni) == PQS_IDX_TRUE);
00367    if (qual_is_true) result |= TRUTH_QUAL_PRED_TRUE;
00368 
00369    switch (itype) {
00370     case PQS_ITYPE_UNC:
00371        if (!qual_is_true) result |= TRUTH_MAY_SET_FALSE;
00372        // Fall through
00373     case PQS_ITYPE_NORM:
00374        SET_RESULT12(TRUTH_NEVER_SET_TRUE|TRUTH_MAY_SET_FALSE|TRUTH_ALWAYS_SET_FALSE,
00375         TRUTH_NEVER_SET_FALSE|TRUTH_MAY_SET_TRUE|TRUTH_ALWAYS_SET_TRUE,
00376         TRUTH_MAY_SET_TRUE|TRUTH_MAY_SET_FALSE,
00377         TRUTH_NEVER_SET_FALSE|TRUTH_MAY_SET_TRUE|TRUTH_ALWAYS_SET_TRUE,
00378         TRUTH_NEVER_SET_TRUE|TRUTH_MAY_SET_FALSE|TRUTH_ALWAYS_SET_FALSE,
00379         TRUTH_MAY_SET_TRUE|TRUTH_MAY_SET_FALSE);
00380        break;
00381 
00382     case PQS_ITYPE_AND:
00383        result |= TRUTH_NEVER_SET_TRUE;
00384        SET_RESULT(TRUTH_MAY_SET_FALSE|TRUTH_ALWAYS_SET_FALSE,
00385       TRUTH_NEVER_SET_FALSE,
00386       TRUTH_MAY_SET_FALSE);
00387        break;
00388 
00389     case PQS_ITYPE_ANDCM:
00390        result |= TRUTH_NEVER_SET_TRUE;
00391        SET_RESULT(TRUTH_NEVER_SET_FALSE,
00392       TRUTH_MAY_SET_FALSE|TRUTH_ALWAYS_SET_FALSE,
00393       TRUTH_MAY_SET_FALSE);
00394        break;
00395 
00396 
00397     case PQS_ITYPE_OR:
00398        result |= TRUTH_NEVER_SET_FALSE;
00399        SET_RESULT(TRUTH_NEVER_SET_TRUE,
00400       TRUTH_MAY_SET_TRUE|TRUTH_ALWAYS_SET_TRUE,
00401       TRUTH_MAY_SET_TRUE);
00402        break;
00403        
00404     case PQS_ITYPE_ORCM:
00405        result |= TRUTH_NEVER_SET_FALSE;
00406        SET_RESULT(TRUTH_MAY_SET_TRUE|TRUTH_ALWAYS_SET_TRUE,
00407       TRUTH_NEVER_SET_TRUE,
00408       TRUTH_MAY_SET_TRUE);
00409        break;
00410        
00411     case PQS_ITYPE_ANDORCM:
00412        SET_RESULT12(TRUTH_NEVER_SET_TRUE|TRUTH_MAY_SET_FALSE|TRUTH_ALWAYS_SET_FALSE,
00413       TRUTH_NEVER_SET_TRUE|TRUTH_NEVER_SET_FALSE,
00414       TRUTH_NEVER_SET_TRUE|TRUTH_MAY_SET_FALSE,
00415       TRUTH_NEVER_SET_FALSE|TRUTH_MAY_SET_TRUE|TRUTH_ALWAYS_SET_TRUE,
00416       TRUTH_NEVER_SET_FALSE|TRUTH_NEVER_SET_TRUE,
00417       TRUTH_NEVER_SET_FALSE|TRUTH_MAY_SET_TRUE);
00418        break;
00419 
00420     case PQS_ITYPE_ORANDCM:
00421        SET_RESULT12(TRUTH_NEVER_SET_FALSE|TRUTH_NEVER_SET_TRUE,
00422       TRUTH_NEVER_SET_FALSE|TRUTH_MAY_SET_TRUE|TRUTH_ALWAYS_SET_TRUE,
00423       TRUTH_NEVER_SET_FALSE|TRUTH_MAY_SET_TRUE,
00424       TRUTH_NEVER_SET_TRUE|TRUTH_NEVER_SET_FALSE,
00425       TRUTH_NEVER_SET_TRUE|TRUTH_MAY_SET_FALSE|TRUTH_ALWAYS_SET_FALSE,
00426       TRUTH_NEVER_SET_TRUE|TRUTH_MAY_SET_FALSE);
00427        break;
00428 
00429     case PQS_ITYPE_DIVSQRT:
00430        result |= TRUTH_MAY_SET_FALSE | TRUTH_MAY_SET_TRUE;
00431        break;
00432 
00433     default:
00434        // Should never get here
00435        FmtAssert(0,("Can't test truth value of ITYPE %d\n",itype));
00436    }       
00437 
00438    // Fixup special handling of false
00439    if (result | TRUTH_MAY_SET_FALSE) result &= ~TRUTH_NEVER_SET_FALSE;
00440    return (result);
00441 }
00442 
00443 
00444 
00445 /*****************************************************************
00446 
00447 void PQS_MANAGER::PQS_Mark_TN_Parents_TRUE(TN *tn) 
00448 void PQS_MANAGER::PQS_Mark_TN_Parents_TRUE(PQS_NODE_IDX tni, TN *tn)
00449 
00450 Walk up the PQS tree, marking all ancestors of tn. The second form is the
00451 one used internally. This will only mark nodes which have the potential
00452 for setting things TRUE. For example, the qualifying predicate of an 
00453 AND is never walked, since the node can never set something TRUE.
00454 
00455 ****************************************************************/
00456 
00457 void 
00458 PQS_MANAGER::PQS_Mark_TN_Parents_TRUE(PQS_NODE_IDX tni, PQS_TN tn)
00459 {
00460    PQS_TN qual_tn;
00461    PQS_NODE_IDX qual_idx;
00462    PQS_NODE_IDX up_idx;
00463 
00464    /* Early exit */
00465    if (!PQS_Is_Real_Idx(tni)) return;
00466 
00467    /* Set the marker on the current index */
00468    PQS_NODE_Mark(tni,tn);
00469    
00470    /* Walk the qualifying predicate */
00471    if (may_set_TRUE(tni,tn)) {
00472       qual_idx = PQS_NODE_get_qual_pred(tni);
00473       qual_tn  = PQS_NODE_get_qual_tn(tni);
00474       PQS_Mark_TN_Parents_TRUE(qual_idx,qual_tn);
00475    }
00476 
00477    /* Walk the previous instances if necessary */
00478    up_idx = PQS_NODE_get_up_idx(tni,tn);
00479    PQS_Mark_TN_Parents_TRUE(up_idx,tn);
00480 }
00481 
00482 // Alternative entry
00483 void 
00484 PQS_MANAGER::PQS_Mark_TN_Parents_TRUE(PQS_TN tn)
00485 {
00486    PQS_Mark_TN_Parents_TRUE(PQS_TN_get_last_definition(tn),tn);
00487 }
00488 
00489 
00490 /*****************************************************************
00491 
00492 void
00493 PQS_MANAGER::PQS_Add_Instruction (PQS_OP instruction)
00494 
00495 Add an instruction to the current PQS_MANAGER. Instructions must be added in 
00496 flow sequence. 
00497 
00498  To add an instruction to a PQS block
00499 
00500  1) Allocate the new PQS_NODE, and point it at the instruction. Point the 
00501     instruction at the PQS_NODE. 
00502 
00503  2) Get the TN_MAP for the qualifying predicate. Find the instruction setting this instance (the last)
00504     and set the qualifying PQS_NODE.
00505 
00506  3) For each of the TN's defined,
00507     A) allocate the PQS_TN_MAP if necessary
00508     B) add the previous instance (if present) as the input to the PQS_NODE (when required)
00509     C) Point the PQS_NODE at the TN
00510 
00511 
00512 ****************************************************************/
00513 
00514 
00515 PQS_NODE_IDX
00516 PQS_MANAGER::PQS_Add_Instruction (PQS_OP inst)
00517 {
00518    PQS_ITYPE itype;
00519    PQS_NODE_IDX pqsnode = PQS_IDX_NONE;
00520    PQS_NODE_IDX last_definition;
00521    PQS_TN qual;
00522    PQS_TN p1,p2;
00523    PQS_NODE_IDX p1_last,p2_last;
00524    PQS_NODE_FLAGS flags;
00525    
00526    // Check out the instruction to see which class it is. 
00527    itype = PQS_classify_instruction(inst,qual,p1,p2,flags);
00528    if (qual) PQS_TN_set_used_as_qual_pred(qual);
00529 
00530 
00531    if (itype == PQS_ITYPE_NOPREDICATES) {
00532       PQS_OP_set_pqs_idx(inst,PQS_IDX_NONE);
00533       return pqsnode;
00534    }
00535    
00536    // Point the node at the instruction and vice versa
00537    pqsnode = New_pqs_idx(itype,inst);
00538    PQS_NODE_set_flags(pqsnode,flags);
00539    PQS_OP_set_pqs_idx(inst,pqsnode);
00540 
00541    // Set the qualifying predicate information
00542    if (qual == PQS_TN_P0) {
00543       PQS_NODE_set_qual_pred(pqsnode,PQS_IDX_TRUE);
00544       // A Normal with a true predicate behaves like an UNC
00545       if (itype == PQS_ITYPE_NORM) {
00546    itype = PQS_ITYPE_UNC;
00547    PQS_NODE_set_itype(pqsnode,itype);
00548       }
00549    } else {
00550       last_definition = PQS_TN_get_last_definition(qual);
00551       PQS_NODE_set_qual_pred(pqsnode,last_definition);
00552    }
00553    PQS_NODE_set_qual_tn(pqsnode,qual);
00554    
00555    // Set up the predicate pointers
00556    if (p1 && (p1 != PQS_TN_P0)) {
00557       PQS_NODE_set_out_pred1(pqsnode,p1);
00558       p1_last = PQS_TN_get_last_definition(p1);
00559       PQS_TN_set_last_definition(p1,pqsnode);
00560       
00561       if (PQS_ITYPE_sets_unconditionally(itype)) {
00562    // These two set unconditionally
00563    PQS_NODE_set_in_pred1(pqsnode,PQS_IDX_NONE);
00564       } else {
00565    PQS_NODE_set_in_pred1(pqsnode,p1_last);
00566    PQS_NODE_add_use(p1_last,p1,pqsnode);
00567       }
00568       // Set the NO_QUERY flag if the predicate has already been used a s qualifying predicate
00569       if (PQS_TN_used_as_qual_pred(p1)) {
00570    PQS_TN_set_no_query(p1);
00571       }
00572    }
00573    
00574    if (p2 && (p2 != PQS_TN_P0)) {
00575       PQS_NODE_set_out_pred2(pqsnode,p2);
00576       p2_last = PQS_TN_get_last_definition(p2);
00577       PQS_TN_set_last_definition(p2,pqsnode);
00578       
00579       if (PQS_ITYPE_sets_unconditionally(itype)) {
00580    PQS_NODE_set_in_pred2(pqsnode,PQS_IDX_NONE);
00581       } else {
00582    PQS_NODE_set_in_pred2(pqsnode,p2_last);
00583    PQS_NODE_add_use(p2_last,p2,pqsnode);
00584       }
00585       // Set the NO_QUERY flag if the predicate has already been used a s qualifying predicate
00586       if (PQS_TN_used_as_qual_pred(p2)) {
00587    PQS_TN_set_no_query(p2);
00588       }
00589    }
00590    
00591    return pqsnode;
00592 }
00593 
00594 
00595 //
00596 // Utility routine, returns posibility of two TNs never being true together
00597 //
00598 PQS_TRUTH
00599 PQS_MANAGER::never_true_together(PQS_TN t1, PQS_TN t2, PQS_NODE_IDX tni)
00600 {
00601 
00602    PQS_TRUTH tval = PQS_TRUTH_UNKNOWN;
00603 
00604    // Trivial case
00605    if (t1 == t2) return PQS_TRUTH_NEVER;
00606    
00607    // Check to make sure these two are set by this tni
00608    if (!((t1 == PQS_NODE_get_out_pred1(tni) &&
00609       t2 == PQS_NODE_get_out_pred2(tni)) ||
00610      (t2 == PQS_NODE_get_out_pred1(tni) &&
00611       t1 == PQS_NODE_get_out_pred2(tni)))) {
00612      printf("bad tni %d\n",tni);
00613    }
00614 #if 0
00615    Is_True((t1 == PQS_NODE_get_out_pred1(tni) &&
00616       t2 == PQS_NODE_get_out_pred2(tni)) ||
00617      (t2 == PQS_NODE_get_out_pred1(tni) &&
00618       t1 == PQS_NODE_get_out_pred2(tni)),("Bad args to never_true_together"));
00619 #endif
00620 
00621    /* Check for getting set under an unconditional FALSE */
00622    if ((PQS_NODE_get_qual_pred(tni) == PQS_IDX_TRUE) &&
00623        (always_set_FALSE(tni,t1) ||
00624   always_set_FALSE(tni,t2))) {
00625       return (PQS_TRUTH_ALWAYS);
00626    }
00627 
00628    switch (PQS_NODE_get_itype(tni)) {
00629     case PQS_ITYPE_UNC:
00630        tval = PQS_TRUTH_ALWAYS;
00631        break;
00632        
00633     case PQS_ITYPE_NORM:
00634     case PQS_ITYPE_ORANDCM:
00635     case PQS_ITYPE_ANDORCM:
00636        // Can't rule it out, since this may set them complementarily
00637        tval = PQS_TRUTH_POSSIBLE;
00638        break;
00639 
00640     case PQS_ITYPE_OR:
00641        if (PQS_NODE_condition_false(tni)) {
00642     tval = PQS_TRUTH_POSSIBLE;
00643        } else {
00644     tval = PQS_TRUTH_NEVER;
00645        }
00646 
00647     case PQS_ITYPE_ORCM:
00648        if (PQS_NODE_condition_true(tni)) {
00649     tval = PQS_TRUTH_POSSIBLE;
00650        } else {
00651     tval = PQS_TRUTH_NEVER;
00652        }
00653        
00654     case PQS_ITYPE_AND:
00655     case PQS_ITYPE_ANDCM:
00656        // May set both to zero
00657        tval = PQS_TRUTH_POSSIBLE;
00658        break;
00659 
00660     default:
00661        FmtAssert(0,("Can't test truth value of this ITYPE\n"));
00662        break;
00663    }
00664    return tval;
00665 }
00666 
00667 
00668 
00669 BOOL
00670 PQS_MANAGER::PQS_is_disjoint_helper(PQS_NODE_IDX tni2, PQS_TN tn2)
00671 {
00672    PQS_TN tnm;
00673    PQS_TRUTH is_disjoint;
00674    PQS_NODE_IDX up_idx, qual_idx;
00675    PQS_TN qual_tn;
00676    BOOL up_value;
00677    BOOL qual_value;
00678    BOOL val_1,val_2, need_upwalk;
00679    BOOL result;
00680 
00681    // Go until we get a match on an ancestor of tni2, or until tni2 is 
00682    // an invalid
00683 
00684    if (!PQS_Is_Real_Idx(tni2)) return FALSE; // If we get here, we have not been able to prove it
00685    
00686    if (Is_Marked(tni2)) {
00687       // We have a collision with an ancestor of tni1
00688       val_1 = TRUE;
00689       val_2 = TRUE;
00690       need_upwalk = FALSE;
00691       if (Is_Marked1(tni2)) {
00692    tnm = PQS_NODE_get_out_pred1(tni2);
00693    is_disjoint = never_true_together(tnm,tn2,tni2);
00694    if (is_disjoint == PQS_TRUTH_ALWAYS) {
00695       val_1 = TRUE;
00696    } else if (is_disjoint == PQS_TRUTH_NEVER) {
00697       val_1 = FALSE;
00698    } else if (is_disjoint == PQS_TRUTH_POSSIBLE) {
00699       need_upwalk = TRUE;
00700    }
00701       }
00702       if (Is_Marked2(tni2)) {
00703    tnm = PQS_NODE_get_out_pred2(tni2);
00704    is_disjoint = never_true_together(tnm,tn2,tni2);
00705    if (is_disjoint == PQS_TRUTH_ALWAYS) {
00706       val_2 = TRUE;
00707    } else if (is_disjoint == PQS_TRUTH_NEVER) {
00708       val_2 = FALSE;
00709    } else  if (is_disjoint == PQS_TRUTH_POSSIBLE) {
00710       need_upwalk = TRUE;
00711    }
00712       }
00713       if (need_upwalk) {
00714    // Harder case; the two may be disjoint, but we can only determine this
00715    // by walking upward. 
00716    up_value = PQS_is_disjoint_helper(PQS_NODE_get_up_idx(tni2,tn2),tn2);
00717       } else {
00718    up_value = TRUE;
00719       }
00720       result = (up_value && val_1 && val_2);
00721 
00722    } else {
00723       // This node is not marked, so we need to check that 
00724       // 1) The qualifying predicate is disjoint, and
00725       // 2) The previous instance is disjoint
00726       up_idx = PQS_NODE_get_up_idx(tni2,tn2);
00727       if (PQS_Is_Real_Idx(up_idx)) {
00728    up_value = PQS_is_disjoint_helper(up_idx,tn2);
00729       } else {
00730    up_value = TRUE; // No previous instance
00731       }
00732       if (may_set_TRUE(tni2,tn2)) {
00733    qual_idx = PQS_NODE_get_qual_pred(tni2);
00734    qual_tn = PQS_NODE_get_qual_tn(tni2);
00735    qual_value = PQS_is_disjoint_helper(qual_idx,qual_tn);
00736       } else {
00737    qual_value = TRUE;
00738       }
00739       
00740       result = (qual_value && up_value);
00741    }
00742    return (result);
00743 }
00744 
00745 
00746 /*****************************************************************
00747 
00748 BOOL PQS_is_disjoint (TN * tn1, TN * tn2)
00749 BOOL PQS_is_disjoint (PQS_NODE_IDX tni1, PQS_NODE_IDX tni2, TN *tn1, TN *tn2)
00750 
00751 Return TRUE if it is never possible for tn1 and tn2 to be true at the same
00752 time.  The first form is the main inqiry form, and uses the last set
00753 instance of the TN as the inquiry point. The second form is used internally
00754 to indicate the start point for the inquiry.
00755 
00756 
00757 ****************************************************************/
00758 
00759 BOOL
00760 PQS_MANAGER::PQS_is_disjoint (PQS_NODE_IDX tni1, PQS_NODE_IDX tni2, PQS_TN tn1, PQS_TN tn2)
00761 {
00762   // A couple of quick exits
00763   if (tn1 == tn2) return (FALSE);
00764 
00765   BOOL r=PQS_is_disjoint_h(tni1,tni2,tn1,tn2);
00766   if (PQS_Tracing && (tni1 != PQS_IDX_TRUE || tni2 != PQS_IDX_TRUE)) {
00767     fprintf(TFile,"<PQS> Is_Disjoint(TN%d[%d],TN%d[%d]) = %d\n",TN_number(tn1),tni1,
00768       TN_number(tn2),tni2,r);
00769   }
00770   
00771   return r;
00772 }
00773 
00774 
00775 BOOL
00776 PQS_MANAGER::PQS_is_disjoint_h (PQS_NODE_IDX tni1, PQS_NODE_IDX tni2, PQS_TN tn1, PQS_TN tn2)
00777 {
00778    PQS_TRUTH same_tnis;
00779 
00780    // Degenerate cases
00781    if (tni1 == PQS_IDX_FALSE || tni2 == PQS_IDX_FALSE) {
00782       return (TRUE);
00783    } else if (tni1 == PQS_IDX_TRUE || tni2 == PQS_IDX_TRUE) {
00784       return (FALSE);
00785    }
00786 
00787    // Simple case, tni1 and tni2 are the same
00788    if (tni1 == tni2) {
00789       same_tnis = never_true_together(tn1,tn2,tni1);
00790       if (same_tnis == PQS_TRUTH_ALWAYS) {
00791    return TRUE;
00792       } else if (same_tnis == PQS_TRUTH_NEVER) {
00793    return FALSE;
00794       }
00795    }
00796 
00797    // Either we missed the simple case or the tni's are not the same.
00798 
00799    // Mark all ancestors of tn1
00800    Update_Marker();
00801    PQS_Mark_TN_Parents_TRUE(tni1,tn1);
00802 
00803    return PQS_is_disjoint_helper(tni2,tn2);
00804 
00805 }
00806 
00807 
00808 // ================ Public published entries ================
00809 
00810 BOOL
00811 PQS_MANAGER::PQS_is_disjoint(PQS_TN tn1, PQS_TN tn2)
00812 {
00813    if (PQS_TN_no_query(tn1) || PQS_TN_no_query(tn2)) {
00814       return FALSE;
00815    }
00816    
00817    return PQS_is_disjoint(PQS_TN_get_last_definition(tn1),
00818         PQS_TN_get_last_definition(tn2),
00819         PQS_TN_get_tn_to_use(tn1),
00820         PQS_TN_get_tn_to_use(tn2));
00821 }
00822 
00823 BOOL
00824 PQS_MANAGER::PQS_is_disjoint(PQS_TN_SET &tns1, PQS_TN_SET &tns2)
00825 {
00826    PQS_TN_SET_TYPE &tnset1 = tns1._set;
00827    PQS_TN_SET_TYPE &tnset2 = tns2._set;
00828    PQS_TN_SET_TYPE::iterator p,q;
00829    BOOL result = TRUE;
00830 
00831    if (check_for_unqueriable(tns1) || check_for_unqueriable(tns2)) {
00832       return (FALSE);
00833    }
00834 
00835    // Iterate overall pairs checking for disjoint-ness
00836    for (p = tnset1.begin(); result && (p != tnset1.end()); ++p) {
00837       for (q = tnset2.begin(); result && (q != tnset2.end()); ++q) {
00838    result != PQS_is_disjoint(PQS_TN_get_last_definition(*p),
00839            PQS_TN_get_last_definition(*q),
00840            *p,*q);
00841       }
00842    }
00843    return (result);
00844 }
00845 
00846 /*****************************************************************
00847 
00848 BOOL PQS_is_subset_of (PQS_TN tn1, PQS_TN tn2)
00849 BOOL PQS_is_subset_of (PQS_TN tn1, PQS_TN_SET &tns2)
00850 BOOL PQS_is_subset_of (PQS_TN_SET &tns1, PQS_TN_SET &tns2)
00851 
00852 Return TRUE if it is always the case that if TN1 is true, then TN2 must also be true. 
00853 For the set forms, return TRUE if any element in the first set is true, than at least one
00854 element of the second set must be true.
00855 
00856 ****************************************************************/
00857 
00858 BOOL
00859 PQS_MANAGER::PQS_is_subset_of (PQS_NODE_IDX tni1, PQS_TN tn1, PQS_NODE_IDX tni2, PQS_TN tn2)
00860 {
00861    BOOL qual_val, prev_val;
00862    INT32 truth;
00863    BOOL needs_upwalk;
00864    
00865    // Stopping cases
00866    if (tni2 == PQS_IDX_TRUE) return (TRUE);
00867    if (tni2 == PQS_IDX_FALSE) return (FALSE);
00868    if (tni1 == tni2) {
00869       if (tn1 == tn2) {
00870    return (TRUE);
00871       } else {
00872    return (FALSE);
00873       }
00874    } else if (!PQS_Is_Real_Idx(tni1)) {
00875       return (FALSE);
00876    }
00877    
00878    truth = get_truth_info(tni1,tn1);
00879    if (may_set_TRUE(truth)) {
00880       qual_val = PQS_is_subset_of(PQS_NODE_get_qual_pred(tni1),
00881           PQS_NODE_get_qual_tn(tni1),tni2,tn2);
00882    } else {
00883       qual_val = TRUE;
00884    }
00885 
00886    // Don't needs to check the previous value if this node is guaranteed
00887    // to set something, which means it's an unconditional setter, or the
00888    // qual pred is TRUE and the node is an ALWAYS setter. 
00889    needs_upwalk = TRUE;
00890    if (PQS_ITYPE_sets_unconditionally(PQS_NODE_get_itype(tni1)) ||
00891        (qual_always_true(truth) &&
00892   (always_set_TRUE(truth) || always_set_FALSE(truth)))) {
00893       needs_upwalk = FALSE;
00894    }
00895    
00896    if (needs_upwalk) {
00897       prev_val = PQS_is_subset_of(PQS_NODE_get_up_idx(tni1,tn1),
00898           tn1,tni2,tn2);
00899    } else {
00900       prev_val = TRUE;
00901    }
00902 
00903    return (prev_val && qual_val);
00904 }
00905 
00906 
00907 BOOL
00908 PQS_MANAGER::PQS_is_subset_of (PQS_NODE_IDX tni1, PQS_TN tn1, PQS_TN_SET &tns2)
00909 {
00910    BOOL qual_val, prev_val, needs_upwalk;
00911    INT32 truth;
00912    
00913    // Stopping cases
00914    if (tns2.Is_Subset(PQS_TN_P0)) return (TRUE);
00915    if (tns2.Is_Subset(tn1))       return (TRUE);
00916    if (!PQS_Is_Real_Idx(tni1))    return (FALSE);
00917 
00918    truth = get_truth_info(tni1,tn1);
00919    if (may_set_TRUE(truth)) {
00920       qual_val = PQS_is_subset_of(PQS_NODE_get_qual_pred(tni1),
00921           PQS_NODE_get_qual_tn(tni1),tns2);
00922    } else {
00923       qual_val = TRUE;
00924    }
00925    
00926    // Don't needs to check the previous value if this node is guaranteed
00927    // to set something, which means it's an unconditional setter, or the
00928    // qual pred is TRUE and the node is an ALWAYS setter. 
00929    needs_upwalk = TRUE;
00930    if (PQS_ITYPE_sets_unconditionally(PQS_NODE_get_itype(tni1)) ||
00931        (qual_always_true(truth) &&
00932   (always_set_TRUE(truth) || always_set_FALSE(truth)))) {
00933       needs_upwalk = FALSE;
00934    }
00935    
00936    if (needs_upwalk) {
00937       prev_val = PQS_is_subset_of(PQS_NODE_get_up_idx(tni1,tn1),
00938           tn1,tns2);
00939    } else {
00940       prev_val = TRUE;
00941    }
00942 
00943    return (prev_val && qual_val);
00944 }
00945 
00946 // ================ Public published entries ================
00947 
00948 BOOL
00949 PQS_MANAGER::PQS_is_subset_of(PQS_TN tn1, PQS_TN tn2)
00950 {
00951   BOOL result;
00952   if (PQS_Tracing) {
00953     fprintf(TFile,"<PQS> Is_Subset_Of(TN%d,TN%d) = ",TN_number(tn1),TN_number(tn2));
00954   }
00955   
00956   if (PQS_TN_no_query(tn1) || PQS_TN_no_query(tn2)) {
00957     if (PQS_Tracing) {
00958       fprintf(TFile,"0\n");
00959     }
00960     return FALSE;
00961   }
00962   result = PQS_is_subset_of(PQS_TN_get_last_definition(tn1),
00963           PQS_TN_get_tn_to_use(tn1),
00964           PQS_TN_get_last_definition(tn2),
00965           PQS_TN_get_tn_to_use(tn2));
00966   if (PQS_Tracing) {
00967     fprintf(TFile,"%d\n",result);
00968   }
00969   return result;
00970 }
00971 
00972 BOOL
00973 PQS_MANAGER::PQS_is_subset_of(PQS_TN tn1, PQS_TN_SET &tns2)
00974 {
00975    PQS_TN_SET tns_simp;
00976    BOOL result;
00977 
00978    if (PQS_Tracing) {
00979      fprintf(TFile,"<PQS> Is_Subset_Of(TN%d,",TN_number(tn1));
00980      tns2.Print(TFile,FALSE);
00981      fprintf(TFile,") = ");
00982    }
00983 
00984    if (PQS_TN_no_query(tn1) || check_for_unqueriable(tns2)) {
00985      if (PQS_Tracing) {
00986        fprintf(TFile,"0\n");
00987      }
00988      return (FALSE);
00989    }
00990 
00991    tns_simp = Simplify_TN_Set(tns2);
00992    result = PQS_is_subset_of(PQS_TN_get_last_definition(tn1),
00993            PQS_TN_get_tn_to_use(tn1),
00994            tns_simp);
00995 
00996    if (PQS_Tracing) {
00997      fprintf(TFile,"%d\n",result);
00998    }
00999    return result;
01000 }
01001 
01002 
01003 BOOL
01004 PQS_MANAGER::PQS_is_subset_of(PQS_TN_SET &tns1, PQS_TN_SET &tns2)
01005 {
01006    PQS_TN tn1;
01007    BOOL result = TRUE;
01008    PQS_TN_SET_TYPE &tnset = tns1._set;
01009    PQS_TN_SET_TYPE::iterator p;
01010    PQS_TN_SET tns_simp;
01011 
01012    if (PQS_Tracing) {
01013      fprintf(TFile,"<PQS> Is_Subset_Of(");
01014      tns1.Print(TFile,FALSE);
01015      fprintf(TFile,",");
01016      tns2.Print(TFile,FALSE);
01017      fprintf(TFile,") = ");
01018    }
01019      
01020    if (check_for_unqueriable(tns1) || check_for_unqueriable(tns2)) {
01021      if (PQS_Tracing) {
01022        fprintf(TFile,"0\n");
01023      }
01024      return (FALSE);
01025    }
01026 
01027    tns_simp = Simplify_TN_Set(tns2);
01028 
01029    p = tnset.begin();
01030    while (result && (p != tnset.end())) {
01031       tn1 = *p;
01032       result &= PQS_is_subset_of(PQS_TN_get_last_definition(tn1),
01033          PQS_TN_get_tn_to_use(tn1),
01034          tns_simp);
01035       ++p;
01036    }
01037 
01038    if (PQS_Tracing) {
01039      fprintf(TFile,"%d\n",result);
01040    }
01041    return result;
01042 }
01043 
01044 
01045 /*****************************************************************
01046 
01047 Utility routine to simplify sets of TNs, etc. What it does it try 
01048 to replace complementary pairs with the qualifying predicate. For example, 
01049 If we had (pq) px,py = UNC..., and the set contains px and py, replace the two 
01050 with pq. 
01051 
01052 PQS_TN_SET
01053 PQS_MANAGER::Simplify_TN_Set (PQS_TN_SET &tni)
01054 
01055  ****************************************************************
01056 */
01057 
01058 PQS_TN_SET
01059 PQS_MANAGER::Simplify_TN_Set (const PQS_TN_SET &tns)
01060 {
01061    // First, generate a TNI set
01062    PQS_TN_SET::set_iterator_type p;
01063    PQS_TNI_SET::set_iterator_type q;
01064    PQS_TN tn;
01065    PQS_NODE_IDX tni;
01066    PQS_TNI_SET tnis;
01067    PQS_TN_SET result;
01068    
01069    for (p = tns.begin(); p != tns.end(); ++p) {
01070       tnis.Insert(PQS_TNI(PQS_TN_get_last_definition(*p),PQS_TN_get_tn_to_use(*p)));
01071    }
01072    
01073    Simplify_TNI_Set(tnis);
01074 
01075    // check for the TRUE predicate
01076    if (tnis.Is_Subset(PQS_TNI(PQS_IDX_TRUE,PQS_TN_P0))) {
01077       result.Insert(PQS_TN_P0);
01078    } else {
01079 
01080       // Convert back to a TN set, removing all elements which are not the last definition 
01081       for (q = tnis.begin(); q != tnis.end(); ++q) {
01082    tn = PQS_TNI_TN(*q);
01083    tni = PQS_TNI_IDX(*q);
01084    if (tn) {
01085       if (tni == PQS_TN_get_last_definition(tn)) {
01086          result.Insert(tn); 
01087       }
01088    }
01089       }
01090    }
01091    
01092    // Add back the original set, just in case
01093    // result = result.Union(result,tns);
01094    return (result);
01095 }
01096 
01097 
01098 /*****************************************************************
01099 
01100 Utility routine to simplify sets of TNs, etc. What it does it try 
01101 to replace complementary pairs with the qualifying predicate. For example, 
01102 If we had (pq) px,py = UNC..., and the set contains px and py, replace the two 
01103 with pq. 
01104 
01105 PQS_TNI_SET
01106 PQS_MANAGER::Simplify_TNI_Set (PQS_TNI_SET &tni)
01107 
01108  ****************************************************************
01109 */
01110 
01111 void
01112 PQS_MANAGER::Simplify_TNI_Set (PQS_TNI_SET &result)
01113 {
01114    PQS_TNI_SET::set_iterator_type p,p_end;
01115    BOOL any_combining;
01116    PQS_TNI_SET_TYPE &r_set = result._set;
01117    // Look for combinable pairs
01118    do {
01119       any_combining = FALSE;
01120       for (p = r_set.begin(); p != r_set.end(); ++p) {
01121    any_combining = Simplify_In_Set(PQS_TNI_IDX(*p),PQS_TNI_TN(*p),result);
01122    if (any_combining) break;
01123       }
01124    } while (any_combining);
01125 
01126    return;
01127 }
01128 
01129 
01130 // Helper routine for above
01131 
01132 BOOL 
01133 PQS_MANAGER::Simplify_In_Set(PQS_NODE_IDX tni, PQS_TN tn, PQS_TNI_SET &tnis)
01134 {
01135    BOOL something_changed=FALSE;
01136    INT32 truth;
01137 
01138    // Simple things, if the TN is null or the tni is nothing, remove it from the set
01139    if (tn == NULL || tni == PQS_IDX_INVALID) {
01140       tnis.Clear(PQS_TNI(tni,tn));   
01141       return (TRUE);
01142    } else if (tni == PQS_IDX_NONE) {
01143       return (FALSE);
01144    } else if (tni == PQS_IDX_TRUE) {
01145      return (FALSE);
01146    }
01147 
01148    PQS_ITYPE itype=PQS_NODE_get_itype(tni);
01149 
01150    // If the TN can never be set TRUE, remove it
01151    truth = get_truth_info(tni,tn);
01152    if (never_set_TRUE(truth)) {
01153       // If it can never be true, remove it
01154       something_changed = TRUE;
01155       tnis.Clear(PQS_TNI(tni,tn));
01156    } else if (never_set_FALSE(truth) && !PQS_ITYPE_sets_unconditionally(itype)) {
01157       // Never sets a false, value so safe to add in the previous value
01158       PQS_TNI prev(PQS_NODE_get_up_idx(tni,tn),tn);
01159       if (!tnis.Is_Subset(prev)) {
01160    something_changed = TRUE;
01161    tnis.Insert(PQS_TNI(PQS_NODE_get_up_idx(tni,tn),tn));
01162       }
01163    } else if (always_set_TRUE(truth)) {
01164       // This always sets the predicate if the qualifying predicate is true,
01165       // so add the qual predicate to the set
01166       something_changed = TRUE;
01167       tnis.Insert(PQS_TNI(PQS_NODE_get_qual_pred(tni),PQS_NODE_get_qual_tn(tni)));
01168       tnis.Clear(PQS_TNI(tni,tn));
01169    }
01170    
01171    
01172    if (itype==PQS_ITYPE_UNC || itype==PQS_ITYPE_NORM) {
01173      PQS_TN other = PQS_NODE_get_other_tn(tni,tn);
01174      if (other && tnis.Is_Subset(PQS_TNI(tni,other))) {
01175    // Both are in the set, remove them, insert the qualifying predicate, 
01176        something_changed = TRUE;
01177        tnis.Clear(PQS_TNI(tni,other));
01178        tnis.Clear(PQS_TNI(tni,tn));
01179        tnis.Insert(PQS_TNI(PQS_NODE_get_qual_pred(tni),PQS_NODE_get_qual_tn(tni)));
01180        // If both are in the set, then it's safe to add in both previous
01181        // values.
01182        if (itype == PQS_ITYPE_NORM) {
01183    tnis.Insert(PQS_TNI(PQS_NODE_get_up_idx(tni,tn),tn));
01184    tnis.Insert(PQS_TNI(PQS_NODE_get_up_idx(tni,other),other));
01185        }
01186      }
01187    }
01188    
01189    if (tnis.Is_Subset(PQS_TNI(PQS_IDX_TRUE,PQS_TN_P0))) {
01190       // Delete everything but this
01191       // Don't set something_changed, or we will get an infinite loop
01192       tnis.Clear();
01193       tnis.Insert(PQS_TNI(PQS_IDX_TRUE,PQS_TN_P0));
01194    }
01195 
01196    return something_changed;
01197 }
01198 
01199 
01200 
01201 
01202 //================================================================
01203 //================================================================
01204 
01205 // Dumping routines
01206 static char * itype_name(PQS_ITYPE p)
01207 {
01208    char *r;
01209    switch (p) {
01210     case PQS_ITYPE_INVALID: r = " PQS_ITYPE_INVALID"; break;
01211     case PQS_ITYPE_NOPREDICATES: r = " PQS_ITYPE_NOPREDICATES"; break;
01212     case PQS_ITYPE_NORM: r = " PQS_ITYPE_NORM"; break;
01213     case PQS_ITYPE_UNC: r = " PQS_ITYPE_UNC"; break;
01214     case PQS_ITYPE_OR: r = " PQS_ITYPE_OR"; break;
01215     case PQS_ITYPE_AND: r = " PQS_ITYPE_AND"; break;
01216     case PQS_ITYPE_ORANDCM: r = " PQS_ITYPE_ORANDCM"; break;
01217     case PQS_ITYPE_ORCM: r = " PQS_ITYPE_ORCM"; break;
01218     case PQS_ITYPE_ANDCM: r = " PQS_ITYPE_ANDCM"; break;
01219     case PQS_ITYPE_ANDORCM: r = " PQS_ITYPE_ANDORCM"; break;
01220     case PQS_ITYPE_DIVSQRT: r = " PQS_ITYPE_DIVSQRT"; break;
01221     case PQS_ITYPE_LAST: r = " PQS_ITYPE_LAST"; break;
01222    }
01223    return r;
01224 }
01225 
01226 
01227 void PQS_MANAGER::Print_all(FILE *f)
01228 {
01229    PQS_NODE_IDX i;
01230    fprintf(f,"PQS data dump =========================================\n");
01231    for (i=1; i < _data.size(); ++i) {
01232       Print_idx(i,f);
01233    }
01234    fprintf(f,"=======================================================\n");
01235 }
01236 
01237 
01238 void PQS_MANAGER::Print_idx(PQS_NODE_IDX p, FILE *f)
01239 {
01240    fprintf(f,"Node %5d: ",p);
01241    _data[p].Print(f);
01242 }
01243 
01244 static char * get_nq_flag(TN *tn)
01245 {
01246   if (tn && PQS_TN_no_query(tn)) return ("*");
01247   return ("");
01248 }
01249 
01250 void PQS_NODE::Print(FILE *f)
01251 {
01252    TN_NUM n1,n2,nq;
01253    n1 = out_pred1 ? TN_number(out_pred1) : -1;
01254    n2 = out_pred2 ? TN_number(out_pred2) : -1;
01255    nq = qual_tn   ? TN_number(qual_tn) : -1;
01256    fprintf(f,"  (%d[%d]%s) %d[%d]%s, %d[%d]%s = %s [0x%p] ",
01257      nq,qual_pred,get_nq_flag(qual_tn),
01258      n1,in_pred1,get_nq_flag(out_pred1),
01259      n2,in_pred2,get_nq_flag(out_pred2),
01260      itype_name(_itype),_inst);
01261    if (flags & PQS_FLAG_CONDITION_TRUE) fprintf(f,"TRUE");
01262    if (flags & PQS_FLAG_CONDITION_FALSE) fprintf(f,"FALSE");
01263    fprintf(f,"\n");
01264 }
01265 
01266 
01267 
01268 void dump_tn_set(PQS_TN_SET &tn)
01269 {
01270    tn.Print();
01271 }
01272 
01273 void dump_tni_set(PQS_TNI_SET &tn)
01274 {
01275    tn.Print();
01276 }