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