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