src/baseparsuif/suifmath/named_lin_ineq.cc

   1
   2 /* file "named_lin_ineq.cc" */
   3
   4 /*  Copyright (c) 1994 Stanford University
   5
   6     All rights reserved.
   7
   8     This software is provided under the terms described in
   9     the "suif_copyright.h" include file. */
  10
  11 #include <suif_copyright.h>
  12
  13 #define _MODULE_ "libsuifmath.a"
  14 #pragma implementation "named_lin_ineq.h"
  15
  16 #include <stdio.h>
  17 #include <suif1.h>
  18 #include <builder.h>
  19 #include "suifmath.h"
  20
  21
  22 int named_lin_ineq::unum_cnt = 0;
  23
  24
  25
  26 /* ##################################################
  27    #####   name_table_entry                     #####
  28    ################################################## */
  29
  30 name_table_entry::~name_table_entry()
  31 {
  32
  33 }
  34
  35 /***************************************************************************
  36  *                                                                         *
  37  ***************************************************************************/
  38
  39 void name_table_entry::init(const immed & im)
  40 {
  41     if(im.is_symbol()) {
  42         assert(im.symbol()->is_var());
  43         is_var = TRUE;
  44         vsname.v = (var_sym *)im.symbol();
  45         knd = nte_symconst;
  46     } else if(im.is_string()) {
  47         is_var = FALSE;
  48         vsname.s = im.string();
  49         knd = nte_symconst;
  50     } else {
  51         is_var = FALSE;
  52         vsname.s = NULL;
  53         knd = nte_aux;
  54     }
  55 }
  56
  57
  58 void name_table_entry::init(name_table_entry_kind k,
  59                             const immed & im)
  60 {
  61     init(im);
  62     // assert(knd != nte_aux);
  63     knd = k;
  64
  65 }
  66
  67 void name_table_entry::set_name(const immed & im)
  68 {
  69     name_table_entry_kind kk = kind();
  70     init(im);
  71     if(kind() != nte_aux) {
  72         knd = kk;
  73         if((kind() == nte_aux)||
  74            (kind() == nte_none))
  75             knd = nte_symconst;
  76     }
  77 }
  78
  79 /***************************************************************************
  80  *                                                                         *
  81  ***************************************************************************/
  82 void name_table_entry::init(const name_table_entry & nte)
  83 {
  84     knd = nte.knd;
  85     is_var = nte.is_var;
  86     if(is_var)
  87         vsname.v = nte.vsname.v;
  88     else
  89         vsname.s = nte.vsname.s;
  90 }
  91
  92
  93 /***************************************************************************
  94  *  Following functions will change the type of a table entry              *
  95  ***************************************************************************/
  96 void name_table_entry::mark_sym()
  97 {
  98     assert(vsname.s);
  99     assert(knd != nte_aux);
 100     knd = nte_symconst;
 101 }
 102
 103 void name_table_entry::mark_cond()
 104 {
 105     assert(vsname.s);
 106     assert(knd != nte_aux);
 107     knd = nte_cond;
 108 }
 109
 110 void name_table_entry::mark_loop()
 111 {
 112     assert(vsname.s);
 113     assert(knd != nte_aux);
 114     knd = nte_loop;
 115 }
 116
 117 void name_table_entry::mark_dim()
 118 {
 119     assert(vsname.s);
 120     assert(knd != nte_aux);
 121     knd = nte_dim;
 122 }
 123
 124 void name_table_entry::mark_summary()
 125 {
 126     assert(vsname.s);
 127     assert(knd != nte_aux);
 128     knd = nte_summary;
 129 }
 130
 131 void name_table_entry::mark_aux()
 132 {
 133     knd = nte_aux;
 134     is_var = FALSE;
 135     vsname.s = NULL;
 136 }
 137
 138
 139  /***************************************************************************
 140  *                                                                         *
 141  ***************************************************************************/
 142 boolean name_table_entry::operator==(const name_table_entry & nte) const
 143 {
 144     if((nte.knd != knd)||
 145        (knd == nte_aux))
 146         return FALSE;
 147     if(is_var && nte.is_var)
 148         return (var() == nte.var()) || var()->overlaps(nte.var());
 149     else
 150         return (nte.name() == name());
 151 }
 152
 153
 154 immed name_table_entry::name() const
 155 {
 156     if(is_var) {
 157         assert(vsname.v);
 158         return immed(vsname.v);
 159     } else if(vsname.s)
 160         return immed(vsname.s);
 161     else
 162         return immed(0);
 163 }
 164
 165 const char * name_table_entry::string() const
 166 {
 167     if(is_var) {
 168         assert(vsname.v);
 169         return vsname.v->name();
 170     } else
 171         return vsname.s;
 172 }
 173
 174
 175 static boolean is_ancestor(base_symtab * ans, base_symtab * chld)
 176 {
 177     if(chld == ans) return TRUE;
 178     if(chld->parent() == NULL) return FALSE;
 179     return is_ancestor(ans, chld->parent());
 180 }
 181
 182
 183 static base_symtab * inner_symtab(base_symtab * st1, base_symtab * st2)
 184 {
 185     if(is_ancestor(st1, st2)) return st2;
 186     if(is_ancestor(st2, st1)) return st1;
 187     // assert_msg(0, ("Symbols are in different scopes, no single scope that covers all the symbols used"));
 188     return NULL;
 189 }
 190
 191
 192 base_symtab * name_table_entry::get_symtab(base_symtab * in) const
 193 {
 194     if((kind() == nte_aux)||(!is_var))
 195         return in;
 196
 197     base_symtab * st = var()->parent();
 198     assert(st);
 199
 200     if(in == NULL)
 201         return st;
 202     else
 203         return inner_symtab(st, in);
 204 }
 205
 206
 207
 208
 209 /* ##################################################
 210    #####   name_table                           #####
 211    ################################################## */
 212
 213 #define SETTABLE(N)  if(n() > N) { \
 214                                    if(v##N) \
 215                                        L[N-1].set_name(*(v##N));\
 216                                    else \
 217                                        L[N-1].mark_aux(); \
 218                                    }
 219
 220 name_table::name_table(const immed * v1,  const immed * v2,  const immed * v3,
 221                        const immed * v4,  const immed * v5,  const immed * v6,
 222                        const immed * v7,  const immed * v8,  const immed * v9,
 223                        const immed * v10, const immed * v11, const immed * v12,
 224                        const immed * v13, const immed * v14, const immed * v15,
 225                        const immed * v16)
 226 {
 227     L = NULL;
 228     sz = 1;
 229     rsz = 1;
 230     int s = 1;
 231     if(v1) s=2;
 232     if(v2) s=3;
 233     if(v3) s=4;
 234     if(v4) s=5;
 235     if(v5) s=6;
 236     if(v6) s=7;
 237     if(v7) s=8;
 238     if(v8) s=9;
 239     if(v9) s=10;
 240     if(v10) s=11;
 241     if(v11) s=12;
 242     if(v12) s=13;
 243     if(v13) s=14;
 244     if(v14) s=15;
 245     if(v15) s=16;
 246     if(v16) s=17;
 247
 248     init(s);
 249
 250     SETTABLE(1);
 251     SETTABLE(2);
 252     SETTABLE(3);
 253     SETTABLE(4);
 254     SETTABLE(5);
 255     SETTABLE(6);
 256     SETTABLE(7);
 257     SETTABLE(8);
 258     SETTABLE(9);
 259     SETTABLE(10);
 260     SETTABLE(11);
 261     SETTABLE(12);
 262     SETTABLE(13);
 263     SETTABLE(14);
 264     SETTABLE(15);
 265     SETTABLE(16);
 266 }
 267 #undef SETTABLE
 268
 269 /***************************************************************************
 270  *                                                                         *
 271  ***************************************************************************/
 272 name_table::~name_table()
 273 {
 274     if(L) delete[] L;
 275 }
 276
 277
 278 name_table &name_table::operator=(const name_table &nt)
 279 {
 280     init(nt);
 281     return *this;
 282 }
 283
 284 /***************************************************************************
 285  *                                                                         *
 286  ***************************************************************************/
 287 void name_table::resize(int newsz)
 288 {
 289     assert(newsz >= 0);
 290     if (newsz >= rsz) {
 291         int osz = MIN(sz,newsz);
 292         name_table_entry *L1 = L;
 293         rsz = newsz;
 294         L = (rsz-1>0)?(new name_table_entry[rsz-1]):NULL;
 295
 296         for(int i=1; i<osz; i++)
 297             L[i-1] = L1[i-1];
 298         if(L1) delete[] L1;
 299     }
 300     sz = newsz;
 301 }
 302
 303 void name_table::init(const name_table &nt)
 304 {
 305     if(&nt == this) return;
 306
 307     if(nt.n() >= rsz) {
 308         if(L) delete[] L;
 309         rsz = nt.n();
 310         L = (rsz-1>0)?(new name_table_entry[rsz-1]):NULL;
 311     };
 312     sz = nt.n();
 313
 314     for(int i=1; i<n(); i++)
 315         L[i-1].init(nt.e(i));
 316 }
 317
 318 /***************************************************************************
 319  *                                                                         *
 320  ***************************************************************************/
 321 void name_table::init(int s)
 322 {
 323     if(s > rsz) {
 324         if(L) delete[] L;
 325         rsz = s;
 326         L = (rsz-1>0)?(new name_table_entry[rsz-1]):NULL;
 327     };
 328     sz = s;
 329
 330     for(int i=1; i<n(); i++)
 331         L[i-1].init();
 332 }
 333
 334
 335 /***************************************************************************
 336  *                                                                         *
 337  ***************************************************************************/
 338 int name_table::find(const name_table_entry & nte) const
 339 {
 340     for(int i=1; i<n(); i++)
 341         if(L[i-1] == nte) return i;
 342     return -1;
 343 }
 344
 345
 346 /***************************************************************************
 347  *                                                                         *
 348  ***************************************************************************/
 349 int name_table::find(const immed & v) const
 350 {
 351     for(int i=1; i<n(); i++)
 352         if(L[i-1].name() == v) return i;
 353     return -1;
 354 }
 355
 356 constraint name_table::lio_code_type() const
 357 {
 358     constraint c(n());
 359     c[0] = NM_CONSTANT;
 360     for(int i=1; i<n(); i++)
 361         switch(e(i).kind()) {
 362         case nte_symconst:
 363             c[i] = NM_CONSTANT;
 364             break;
 365         case nte_cond:
 366         case nte_loop:
 367         case nte_dim:
 368         case nte_summary:
 369             c[i] = NM_LOCATIONS;
 370             break;
 371         case nte_aux:
 372         case nte_none:
 373             assert(0);
 374         }
 375     return c;
 376 }
 377
 378 void name_table::remove(int i, int j)
 379 {
 380     assert((0<i)&&(i<=j)&&(j<n()));
 381
 382     int src=j+1;
 383     int dst=i;
 384
 385     while (src<n()) {
 386         L[dst-1] = L[src-1];
 387         dst++; src++;
 388     };
 389     sz = n()-(j-i+1);
 390 }
 391
 392 void name_table::remove(const integer_row & mask)
 393 {
 394     int src, dst;
 395     assert(mask.n() == n());
 396
 397     for (dst=1, src=1; (src <  n()); src++) {
 398         if (!mask.c(src)) {
 399             L[dst-1] = L[src-1];
 400             dst++;
 401         };
 402     }
 403
 404     sz = dst;
 405 }
 406
 407 void name_table::insert(const name_table_entry & nte, int i)
 408 {
 409     assert((i>=1)&&(i<=n()));
 410     if (sz >= rsz) {
 411         int lln = MAX(n()-1+1,(n()-1)*2);
 412         name_table_entry * LL = (lln>0)?(new name_table_entry[lln]):NULL;
 413
 414         int k;
 415         for(k=1; k<i; k++)
 416             LL[k-1] = L[k-1];
 417         LL[i-1].init(nte);
 418         for(k=i; k<n(); k++)
 419             LL[k] = L[k-1];
 420
 421         if(L) delete[] L;
 422         L = LL;
 423         sz++;
 424         rsz = lln+1;
 425     } else {
 426         for (int k=sz; k>i; k--)
 427             L[k-1] = L[k-2];
 428         L[i-1].init(nte);
 429         sz++;
 430     }
 431 }
 432
 433 void name_table::insert(const immed & v, int i)
 434 {
 435     insert(name_table_entry(v), i);
 436 }
 437
 438
 439
 440 /***************************************************************************
 441  * use B and change A                                                      *
 442  ***************************************************************************/
 443 void name_table::change_name_types(name_table & na, name_table & nb)
 444 {
 445     for(int i=1; i<nb.n(); i++) {
 446         immed bv(nb.e(i).name());
 447         if(bv.is_symbol() || bv.is_string()) {     // not an aux
 448             int j = na.find(bv);
 449             if(j > 0) {
 450                 name_table_entry_kind ka = na.e(j).kind();
 451                 name_table_entry_kind kb = nb.e(i).kind();
 452                 name_table_entry_kind kk = nte_none;
 453                 if(ka == kb)
 454                     kk = kb;
 455                 else if(ka == nte_none)
 456                     kk = kb;
 457                 else if(kb == nte_none) /* can't happen */
 458                     kk = ka;
 459                 else if(ka == nte_symconst)
 460                     kk = kb;
 461                 else if(kb == nte_symconst)
 462                     kk = ka;
 463                 else if((ka == nte_cond)&&(kb == nte_loop))
 464                     kk = nte_cond;
 465                 else if((kb == nte_cond)&&(ka == nte_loop))
 466                     kk = nte_cond;
 467                 else if((ka == nte_summary)||(kb == nte_summary))
 468                     kk = nte_summary;
 469                 else
 470                     assert(0);
 471                 na[j].knd = kk;
 472                 nb[i].knd = kk;
 473             }
 474         }
 475     }
 476 }
 477
 478
 479 /***************************************************************************
 480  *                                                                         *
 481  ***************************************************************************/
 482 boolean name_table::is_aligned(const name_table & na,
 483                                const name_table & nb)
 484 {
 485     if(na.n() != nb.n()) return FALSE;
 486
 487     for(int i=1; i<na.n(); i++) {
 488         if(na.e(i).name() != nb.e(i).name())
 489           if (na.e(i).kind() != nte_summary)
 490             return FALSE;
 491         if(na.e(i).name() == immed(0))
 492             return FALSE;
 493         else if(na.e(i).kind() != nb.e(i).kind())
 494             return FALSE;
 495     }
 496     // make sure table is ordered;
 497     name_table_entry_kind oldkind=nte_none;
 498     for (int j=1; j<na.n(); j++) {
 499         name_table_entry_kind newkind=na.e(j).kind();
 500         switch(newkind) {
 501           case nte_symconst:
 502             if (oldkind == nte_cond) return FALSE;
 503           case nte_cond:
 504             if (oldkind == nte_loop) return FALSE;
 505           case nte_loop:
 506             if (oldkind == nte_dim) return FALSE;
 507           case nte_dim:
 508             if (oldkind == nte_summary) return FALSE;
 509           case nte_summary:
 510             if (oldkind == nte_aux) return FALSE;
 511           case nte_aux:
 512           case nte_none:
 513             break;
 514         }
 515         oldkind = newkind;
 516     }
 517
 518     return TRUE;
 519 }
 520
 521
 522 /***************************************************************************
 523  *                                                                         *
 524  ***************************************************************************/
 525 name_table name_table::operator&(const name_table & b) const
 526 {
 527     name_table ret(this);
 528     ret &= b;
 529     return ret;
 530 }
 531
 532 /***************************************************************************
 533  *                                                                         *
 534  ***************************************************************************/
 535 name_table &name_table::operator&=(const name_table & b)
 536 {
 537     if(is_aligned(*this, b)) {
 538         return *this;
 539     }
 540     integer_row ca(n());
 541     integer_row cb(b.n());
 542     this->align_with(b,ca,cb);
 543     return *this;
 544 }
 545
 546 /***************************************************************************
 547  *                                                                         *
 548  ***************************************************************************/
 549 name_table * name_table::align_tables(const name_table &na,
 550                                       const name_table &nb,
 551                                       integer_row & ca,
 552                                       integer_row & cb)
 553 {
 554     name_table *newnt = new name_table(na);
 555
 556     newnt->align_with(nb, ca, cb);
 557
 558     return newnt;
 559 }
 560
 561 /***************************************************************************
 562  *                                                                         *
 563  ***************************************************************************/
 564 void name_table::align_with(const name_table &nb,
 565                             integer_row & ca,
 566                             integer_row & cb)
 567 {
 568     int ii;
 569     name_table nbcopy(nb);
 570     assert(n() == ca.n());
 571     assert(nb.n() == cb.n());
 572     change_name_types(*this, nbcopy);
 573
 574     for(ii=1; ii<n(); ii++)
 575         assert(e(ii).kind() != nte_none);
 576     for(ii=1; ii<nbcopy.n(); ii++)
 577         assert(nbcopy.e(ii).kind() != nte_none);
 578
 579     ca[0] = cb[0] = 0;                  // consant position does not change
 580
 581     for (ii=1; ii <ca.n(); ii++)
 582         ca[ii] = ii;
 583     int curr = ca.n();
 584
 585     for (ii=1; ii < nbcopy.n(); ii++) {
 586         if ((cb[ii] = find(nbcopy.e(ii))) == -1)
 587             curr++;
 588     }
 589     resize(curr);
 590
 591     curr = ca.n();
 592     for (ii=1; ii < nbcopy.n(); ii++) {
 593         if ((cb[ii]) == -1) {
 594             (*this)[curr] = nbcopy.e(ii);
 595             cb[ii] = curr++;
 596         }
 597     };
 598     integer_row extrac(n());
 599     if (do_reorder_table(extrac)) {
 600         integer_row newca(ca.n()), newcb(cb.n());
 601         for (ii=1; ii < ca.n(); ii++) {
 602             // was:     this[ca[ii]] = old[ii];
 603             // becomes: this[extrac[ii]] =
 604             // ii moves to elt extrac[ca[ii]]
 605             newca[ii] = extrac[ca[ii]];
 606         }
 607         ca.init(newca);
 608         for (ii=1; ii < cb.n(); ii++) {
 609             newcb[ii] = extrac[cb[ii]];
 610         }
 611         cb.init(newcb);
 612     }
 613 }
 614
 615 static void find_elements(name_table_entry_kind k,
 616                           const name_table &na, integer_row &ca,
 617                           int &curr)
 618 {
 619     int currloc = curr;
 620     for (int ai=1; ai<na.n(); ai++) {
 621         if (na.e(ai).kind()==k) {
 622             ca[ai] = currloc++;
 623         };
 624     }
 625     curr = currloc;
 626 }
 627
 628
 629 boolean name_table::do_reorder_table(integer_row &ca)
 630 {
 631     int curr=1;
 632     assert(ca.n() == n());
 633     find_elements(nte_symconst, *this, ca, curr);
 634     find_elements(nte_cond, *this, ca, curr);
 635     find_elements(nte_loop, *this, ca, curr);
 636     find_elements(nte_dim, *this, ca, curr);
 637     find_elements(nte_summary, *this, ca, curr);
 638     find_elements(nte_aux, *this, ca, curr);
 639     assert(curr == ca.n());
 640
 641     name_table thiscopy(*this);
 642     int i;
 643     for (i=1; i<n(); i++)
 644         (*this)[ca[i]] = thiscopy[i];
 645     for (i=1; i<n(); i++)
 646         if (ca[i] != i)
 647             return TRUE;
 648     return FALSE;
 649 }
 650
 651 /***************************************************************************
 652  *                                                                         *
 653  ***************************************************************************/
 654 name_table * name_table::mk_align(const name_table & na,
 655                                   const name_table & nb)
 656 {
 657     name_table * newnt;
 658     if(is_aligned(na, nb))
 659         newnt = new name_table(na);
 660     else {
 661         // indexes to the new list
 662         integer_row ca(na.n());
 663         integer_row cb(nb.n());
 664
 665         newnt = name_table::align_tables(na, nb, ca, cb);
 666     }
 667
 668     return newnt;
 669 }
 670
 671 base_symtab * name_table::get_symtab(base_symtab * in) const
 672 {
 673     base_symtab * curr = in;
 674     for(int i=1; i<n(); i++)
 675         curr = e(i).get_symtab(curr);
 676
 677     return curr;
 678 }
 679
 680
 681
 682
 683 /* ##################################################
 684    #####   named_lin_ineq                       #####
 685    ################################################## */
 686
 687 /***************************************************************************
 688  *                                                                         *
 689  ***************************************************************************/
 690 named_lin_ineq::~named_lin_ineq()
 691 {
 692
 693 }
 694
 695 void named_lin_ineq::init()
 696 {
 697     unum=unum_cnt++;
 698 }
 699
 700 void named_lin_ineq::init(int m, int n)
 701 {
 702     unum=unum_cnt++;
 703     names().init(n);
 704     ineqs().init(m,n);
 705 }
 706
 707 /***************************************************************************
 708  *                                                                         *
 709  ***************************************************************************/
 710 void named_lin_ineq::init(const named_lin_ineq & c)
 711 {
 712     nt.init(c.nt);
 713     lq = c.lq;
 714 }
 715
 716
 717 int named_lin_ineq::init(const immed_list & il, int c)
 718 {
 719     unum = il[c++].integer();
 720     unum_cnt = MAX(unum_cnt, unum+1);
 721
 722     int num = il[c++].integer();
 723
 724     names().init(num);
 725     for(int i=1; i<num; i++)
 726        names()[i].init((name_table_entry_kind)il[c++].integer(),il[c++]);
 727     c = ineqs().integer_matrix::init(il, c);
 728     return c;
 729 }
 730
 731 immed_list * named_lin_ineq::cvt_immed_list() const
 732 {
 733     immed_list * L = new immed_list;
 734
 735     L->append(immed(uid()));
 736     L->append(immed(n()));
 737     for(int i=1; i<n(); i++) {
 738         L->append(immed((int)const_names().e(i).kind()));
 739         L->append(const_names().e(i).name());
 740     }
 741     immed_list * iq = const_ineqs().cvt_immed_list();
 742     L->append(iq);
 743     return L;
 744 }
 745
 746 void named_lin_ineq::swap_col(int i, int j)
 747 {
 748     name_table_entry tmp(names()[i]);
 749     names()[i].init(names()[j]);
 750     names()[j].init(tmp);
 751
 752     if(ineqs().m() > 0) {
 753         assert(names().n() == ineqs().n());
 754         lq.do_swap_col(i, j);
 755     }
 756 }
 757
 758 void named_lin_ineq::del_col(int i, int j)
 759 {
 760     assert(j>=i);
 761     assert((i>0)&&(j>0));
 762     assert((i<n())&&(j<n()));
 763
 764     names().remove(i,j);
 765     lq.do_del_col(i,j);
 766 }
 767
 768
 769 void named_lin_ineq::del_col(const integer_row & rem)
 770 {
 771     assert(rem.n() == n());
 772     names().remove(rem);
 773     ineqs().do_del_columns(rem);
 774     assert(names().n() == ineqs().n());
 775 }
 776
 777 boolean named_lin_ineq::is_clean_false() const
 778 {
 779     if ((m()==1) && (n()==1) && (const_ineqs().r(0).c(0) < 0))
 780         return TRUE;
 781     else
 782         return FALSE;
 783 }
 784
 785 static void normalize_aux_offset(lin_ineq &leq, int auxcol)
 786 {
 787     int bestrow = -1;
 788     int bestcoeff = 0;
 789     for (int i1=0; i1<leq.m(); i1++) {
 790         const integer_row &rowi = leq.r(i1);
 791         int coeff = rowi.c(auxcol);
 792         if (coeff > 0) {
 793             if ((bestcoeff <= 0) || (coeff < bestcoeff)) {
 794                 bestrow = i1;
 795                 bestcoeff = coeff;
 796             }
 797         } else if (coeff < 0) {
 798             if ((bestcoeff == 0) || (coeff > bestcoeff)) {
 799                 bestrow = i1;
 800                 bestcoeff = coeff;
 801             }
 802         }
 803     }
 804
 805     int bestconst = leq[bestrow][0];
 806     int abscoeff = ABS(bestcoeff);
 807     int newconst = bestconst % abscoeff;
 808     newconst = (newconst > 0) ? newconst : newconst + abscoeff;
 809     int constdiff = (newconst - bestconst)/bestcoeff;
 810
 811     for (int i2=0; i2<leq.m(); i2++) {
 812         int coeffi = leq[i2][auxcol];
 813         if (coeffi != 0) {
 814             leq[i2][0] += constdiff * coeffi;
 815         }
 816     }
 817 }
 818
 819 void named_lin_ineq::cleanup()
 820 {
 821     del_zero_cols();
 822     ineqs().del_zeros();
 823     if(ineqs().m() == 0)
 824         return;
 825
 826     if (is_clean_false()) return;
 827
 828     if(~ineqs() == TRUE) {
 829         name_table nt0(1);
 830         lin_ineq leq0(1,1);
 831         leq0[0][0] = -1;
 832         init(named_lin_ineq(nt0, leq0));
 833         return;
 834     }
 835
 836     integer_row rem(n());
 837     rem = 0;
 838     boolean remmed = FALSE;
 839
 840     // remove aux vars that are empty.
 841     // also remove aux vars that are multiple of 1
 842     // also remove auxes which are only a lower or upper bound
 843     for(int i=1; i<n(); i++)
 844         if(names()[i].kind() == nte_aux) {
 845             boolean zero_or_one = TRUE;
 846             int upper_bds = 0;
 847             int upper_row = 0;
 848             int lower_bds = 0;
 849             int lower_row = 0;
 850             for(int j=0; (j<ineqs().m()); j++)
 851                 if(ineqs()[j][i] != 0) {
 852                     if (ineqs()[j][i] > 0) {
 853                         lower_bds++;
 854                         lower_row = j;
 855                     } else {
 856                         upper_bds++;
 857                         upper_row = j;
 858                     }
 859                     if (ABS(ineqs()[j][i]) > 1)
 860                         zero_or_one = FALSE;
 861                     else {
 862                         fprintf(stderr,
 863                                 "\n### Warning: bad aux var ineq in cleanup\n");
 864                         print(stderr);
 865                     }
 866                 }
 867             if (zero_or_one || (upper_bds == 0) || (lower_bds == 0))
 868                 rem[i] = remmed = TRUE;
 869             else if ((upper_bds == 1) && (lower_bds == 1)) {
 870                 constraint upper_bd(ineqs()[upper_row]);
 871                 constraint lower_bd(ineqs()[lower_row]);
 872                 upper_bd += ineqs()[lower_row];
 873                 if (upper_bd.rank() == 0) {
 874                     int diffi = ineqs()[upper_row][0] + ineqs()[lower_row][0];
 875                     int mult = ineqs()[lower_row][i];
 876                     if (ABS(diffi) >= mult-1) {
 877                         // S has aux X with only constraints
 878                         // c1 <= Y + mX <= c2 where c2-c1 >= m,
 879                         // so remove X and its constraints
 880                         rem[i] = remmed = TRUE;
 881                     }
 882                 };
 883             }
 884         }
 885
 886     // check if two auxilary vars are doing the same job
 887     for(int i1=1; i1<n(); i1++)
 888         if((names()[i1].kind() == nte_aux)&&(!rem[i1]))
 889             for(int i2=i1+1; i2<n(); i2++)
 890                 if((names()[i2].kind() == nte_aux)&&(!rem[i2])) {
 891                     constraint filter(n());
 892                     filter = 0;
 893                     filter[i1] = 1;
 894                     filter[i2] = 1;             // c1*i1=a(); c2*i2=b()
 895                     // get rows with occurrences of i1 or i2;
 896                     lin_ineq L = ineqs().filter_thru(filter, 0);
 897                     // assert(!(~L));              // has to have an answer
 898                     L.do_add_rows(1);
 899                     L[L.m()-1] = 0;
 900                     L[L.m()-1][0]  = 1;
 901                     L[L.m()-1][i1] = 1;         // if both are the same
 902                     L[L.m()-1][i2] = -1;        // c1 > c2 is empty
 903                     if(~L) {
 904                         L[L.m()-1][i1] = -1;    // and c2 > c1 is empty
 905                         L[L.m()-1][i2] =  1;
 906                         if(~L) rem[i2] = remmed = TRUE;
 907                     }
 908                 }
 909
 910     if (remmed) {
 911         ineqs().do_filter_away(rem,0);
 912         del_zero_cols();
 913     }
 914
 915     // canonicalize aux offsets;
 916     for(int i3=1; i3<n(); i3++)
 917         if (names()[i3].kind() == nte_aux)
 918             normalize_aux_offset(ineqs(),i3);
 919 }
 920
 921 void named_lin_ineq::simplify()
 922 {
 923     ineqs().normalize(TRUE);
 924     ineqs().sort();
 925     ineqs().del_repetition();
 926     ineqs().del_loose();
 927     cleanup();
 928     return;
 929 }
 930
 931 void named_lin_ineq::del_zero_cols()
 932 {
 933     integer_row zeros(n());
 934
 935     for(int i=n()-1; i>=1; i--) {
 936         int zero = zeros[i] = 1;
 937         for(int j=0; zero && (j<ineqs().m()); j++)
 938             if(ineqs()[j][i] != 0) {
 939                 zeros[i] = zero = 0;
 940             }
 941     }
 942     del_col(zeros);
 943 }
 944
 945
 946 named_lin_ineq & named_lin_ineq::operator=(const named_lin_ineq & c)
 947 {
 948     if(&c == this) return *this;
 949
 950     this->init(c);
 951     return *this;
 952 }
 953
 954
 955 named_lin_ineq & named_lin_ineq::operator=(const lin_ineq & l)
 956 {
 957     assert(l.n() == names().n());
 958     ineqs().init(l);
 959     return *this;
 960 }
 961
 962 void named_lin_ineq::align_named_lin_ineqs(named_lin_ineq & A,
 963                                            named_lin_ineq & B)
 964 {
 965     A.align_with(B);
 966 }
 967
 968 boolean named_lin_ineq::operator==(const named_lin_ineq & c2) const
 969 {
 970     if((this->const_ineqs().m() == 0)&&(c2.const_ineqs().m() == 0))
 971         return TRUE;
 972     if((this->const_ineqs().m() == 0)||(c2.const_ineqs().m() == 0))
 973         return FALSE;
 974
 975     named_lin_ineq * l1;
 976     named_lin_ineq * l2;
 977     boolean delend = FALSE;
 978
 979     if(is_aligned(*this, c2)) {
 980         l1 = (named_lin_ineq *)this;
 981         l2 = (named_lin_ineq *)&c2;
 982     } else {
 983         l1 = new named_lin_ineq(this);
 984         l2 = new named_lin_ineq(c2);
 985         delend = TRUE;
 986         l1->align_with(*l2);
 987     }
 988
 989     boolean ret = (((*l1) >> (*l2))&&
 990                    ((*l2) >> (*l1)));
 991     if(delend) {
 992         delete l1;
 993         delete l2;
 994     }
 995     return ret;
 996 }
 997
 998
 999
1000 named_lin_ineq named_lin_ineq::operator&(const named_lin_ineq & c) const
1001 {
1002     if (m() == 0)
1003         if (c.m() == 0)
1004             return named_lin_ineq();
1005         else
1006             return c;
1007     else if (c.m() == 0)
1008         return *this;
1009     else if (is_aligned(*this, c)) {
1010         named_lin_ineq a1(this);
1011         a1 &= c.const_ineqs();
1012         return a1;
1013     } else {
1014         named_lin_ineq a1(this);
1015         named_lin_ineq a2(c);
1016         a1.align_with(a2);
1017
1018         a1 &= a2.const_ineqs();
1019         return a1;
1020     }
1021 }
1022
1023 // Deletes are there to save memory
1024 named_lin_ineq * named_lin_ineq::and2(named_lin_ineq * c1,
1025                                       named_lin_ineq * c2,
1026                                       boolean del1,
1027                                       boolean del2)
1028 {
1029     if (c1)
1030         if (c2) {
1031             named_lin_ineq * ret = new named_lin_ineq(c1);
1032             *ret &= *c2;
1033             if(del1) delete c1;
1034             if(del2) delete c2;
1035             return ret;
1036         } else {
1037             if (del1) return c1;
1038             else
1039                 return new named_lin_ineq(c1);
1040         }
1041     else
1042         if (c2) {
1043             if(del2) return c2;
1044             else
1045                 return new named_lin_ineq(c2);
1046         } else {
1047             return 0;
1048         }
1049 }
1050
1051 named_lin_ineq & named_lin_ineq::operator&=(const named_lin_ineq & c)
1052 {
1053     named_lin_ineq cc(c);
1054     this->align_with(cc);
1055     (*this) &= cc.ineqs();
1056     simplify();
1057     return *this;
1058 }
1059
1060 named_lin_ineq & named_lin_ineq::operator&=(const lin_ineq & l)
1061 {
1062     assert(l.n() == names().n());
1063
1064     int oldm = m();
1065
1066     ineqs() &= l;
1067
1068     // get rid of linearly dependent new rows;
1069     ineqs().del_repetition(oldm, m()-1);
1070     ineqs().del_loose(oldm, m()-1);
1071
1072     return *this;
1073 }
1074
1075 // Given lower and upper bounds for two seperate aux vars
1076 // see if they can be combined toghter to form a single aux var
1077 // returns TRUE if it works, and swaps i1 and i2 in bounds2;
1078 boolean nli_merged_aux(lin_ineq & bounds1, lin_ineq & bounds2,
1079                        int i1, int i2)
1080 {
1081     if (bounds1.m() != bounds2.m()) return FALSE;
1082
1083     bounds2.do_swap_col(i1, i2);
1084
1085     // faster approximation to bounds1[1:n-1] == bounds2[1:n-1];
1086     integer_row used(bounds2.m());
1087     int i, j, k;
1088     int m = bounds1.m();
1089     int n = bounds1.n();
1090     for (i=0; i<m; i++) {
1091         for (j=0; j<m; j++) {
1092             if (used[j]==0) {
1093                 const constraint &b1 = bounds1.r(i);
1094                 const constraint &b2 = bounds2.r(j);
1095
1096                 // ignore constant term;
1097                 for (k=1; k<n; k++) {
1098                     if (b1.c(k) != b2.c(k))
1099                         break;
1100                 }
1101                 if (k<n)
1102                     continue;
1103                 used[j] = 1;
1104                 break;
1105             };
1106         };
1107         if (j >= m) {
1108             // failed;
1109             bounds2.do_swap_col(i1,i2);
1110             return FALSE;
1111         }
1112     }
1113
1114     return TRUE;
1115
1116     /*
1117       int i, j;
1118       for (i=0; i<
1119       if ((bounds1 <= bounds2) &&
1120           (bounds2 <= bounds1)) {
1121           return TRUE;
1122       }
1123
1124       bounds2.do_swap_col(i1, i2);
1125       return FALSE;
1126       */
1127 }
1128
1129 int named_lin_ineq::merge_auxes(named_lin_ineq &c)
1130 {
1131     named_lin_ineq *r1 = this;
1132     named_lin_ineq *r2 = &c;
1133
1134     // do we need these?
1135     r1->del_zero_cols();
1136     r2->del_zero_cols();
1137
1138     r1->align_with(*r2);
1139
1140     int naux = 0;
1141     constraint indx(r1->n());
1142     int i, j, ix, jx;
1143
1144     // count the number of aux variables and record their positions
1145     for(i=1; i<r1->n(); i++)
1146         if(r1->names()[i].kind() == nte_aux) {
1147             indx[naux] = i;
1148             naux++;
1149         }
1150
1151     if (naux > 0) {
1152         // For each aux variable, find the lower bounds and the upper bounds
1153         // BUGBUG: ignore relations between different aux vars for now;
1154         // this is conservative, at least;
1155         lin_ineq * baux1 = new lin_ineq[naux];
1156         lin_ineq * baux2 = new lin_ineq[naux];
1157         constraint kernel(r1->n());
1158         constraint kernel2(r1->n());
1159         kernel = 0;
1160         kernel2 = 0;
1161         for(i=0; i<naux; i++) {
1162             ix = indx[i];
1163             kernel2[ix] = 1;
1164         }
1165         for(i=0; i<naux; i++) {
1166             ix = indx[i];
1167             kernel[ix] = 1;
1168             kernel2[ix] = 0;
1169             baux1[i].init(r1->ineqs().filter_thru(kernel, 0));
1170             baux1[i].init(baux1[i].filter_away(kernel2, 0));
1171             baux2[i].init(r2->ineqs().filter_thru(kernel, 0));
1172             baux2[i].init(baux2[i].filter_away(kernel2, 0));
1173             kernel[ix] = 0;
1174             kernel2[ix] = 1;
1175         }
1176
1177         // See if two aux variables can be merged toghter.
1178         // one var has to be of r1 and other has to be of r2
1179         // ignore aux interactions for now;
1180         int mergedaux = 0;
1181         integer_row rmauxlist(r1->n());
1182         for (i=0; i<naux; i++)
1183             if (baux1[i].m()>0) {
1184                 for (j=0; j<naux; j++)
1185                     if (baux2[j].m()>0) {
1186                         assert(i != j);
1187                         ix = indx[i];
1188                         jx = indx[j];
1189                         // try to equate ix(in 1) and jx(in 2);
1190                         if (nli_merged_aux(baux1[i], baux2[j], ix, jx)) {
1191                             // merge found, record it and
1192                             // mark the aux to be removed.
1193                             rmauxlist[jx] = 1;
1194                             mergedaux += 1;
1195                             r2->ineqs().do_swap_col(ix,jx);
1196                             baux1[i].clear();
1197                             baux2[j].clear();
1198                             break;
1199                         }
1200                     };
1201             }
1202         delete[] baux1;
1203         delete[] baux2;
1204
1205         if (mergedaux > 0) {
1206             r1->del_col(rmauxlist);
1207             r2->del_col(rmauxlist);
1208         }
1209         return mergedaux;
1210     } else
1211         return 0;
1212 }
1213
1214 // err towards FALSE;
1215 boolean named_lin_ineq::operator>=(const named_lin_ineq & c) const
1216 {
1217     named_lin_ineq l1(*this);
1218     named_lin_ineq l2(c);
1219
1220     int i;
1221     int naux1 = 0;
1222     int naux2 = 0;
1223
1224     // do we need these?
1225     l1.del_zero_cols();
1226     l2.del_zero_cols();
1227
1228     const name_table &nt1 = l1.const_names();
1229     const name_table &nt2 = l2.const_names();
1230
1231     // count the number of aux variables;
1232     for(i=1; i<nt1.n(); i++) {
1233         const name_table_entry &ntei = nt1.e(i);
1234         if(ntei.kind() == nte_aux) {
1235             naux1++;
1236         } else if (nt2.find(ntei) < 0)
1237             // this constrains a variable not constrained by c;
1238             // so there is no way this contains c;
1239             return FALSE; //
1240     }
1241
1242     for(i=1; i<nt2.n(); i++) {
1243         const name_table_entry &ntei = nt2.e(i);
1244         if(ntei.kind() == nte_aux)
1245             naux2++;
1246     }
1247
1248     if (naux1 > naux2) return FALSE; // same problem with this;
1249
1250     if (naux1 > 0) {
1251         int mergedauxes = l1.merge_auxes(l2);
1252
1253         if (naux1 > mergedauxes) return FALSE;
1254
1255         // BUGBUG; still doesnt handle auxes right in general;
1256         // consider { x = 2*aux } and { x = 4*aux };
1257     } else
1258         l1.align_with(l2);
1259
1260     if(~(l1.ineqs() && l2.ineqs())) {
1261         return FALSE;
1262     }
1263     boolean ret = (l1.ineqs() >= l2.ineqs());
1264     return ret;
1265 }
1266
1267 /**************************************************************************
1268  * a simple substitution method                                           *
1269  * This is a cheap alternative to expensive Fourier-Motzkin               *
1270  * substitution expression given in expr is of the form                   *
1271  * var >= sub_expr and var <= sub_expr or                                 *
1272  * sub_expr >= 0                                                          *
1273  **************************************************************************/
1274 named_lin_ineq * named_lin_ineq::substitute(const immed & var,
1275                                             const named_lin_ineq & expr) const
1276 {
1277     named_lin_ineq *ret = new named_lin_ineq(this);
1278     ret->do_substitute(var, expr);
1279     return ret;
1280 }
1281
1282 void named_lin_ineq::do_substitute(const immed & var,
1283                                    const named_lin_ineq & expr)
1284 {
1285     int pos = find(var);
1286     if(pos <= 0)
1287         return;
1288
1289     int col = expr.find(var);
1290
1291     boolean tested = 1;
1292
1293     tested &= (expr.m() == 2);
1294     tested &= ABS(expr.const_ineqs().r(0).c(col) == 1);
1295     for(int i=0; tested && i<expr.n(); i++)
1296         tested &=
1297             (expr.const_ineqs().r(0).c(i) + expr.const_ineqs().r(1).c(i) == 0);
1298     assert_msg(tested,("do_substitute, expr not of right form"));
1299
1300     // leave in row with -var;
1301     int row = (expr.const_ineqs().r(0).c(col) > 0) ? 0 : 1;
1302     named_lin_ineq myex(expr);
1303     myex.del_col(col);
1304     myex.ineqs().do_del_row(row);
1305
1306     align_with(myex);
1307     pos = find(var);
1308     for(int im=0; im<m(); im++) {
1309         int coeff = ineqs()[im][pos];
1310         if(coeff) {
1311             ineqs()[im].do_addmul(myex.ineqs()[0], coeff);
1312             ineqs()[im][pos] = 0;
1313         }
1314     }
1315
1316     del_col(pos);
1317 }
1318
1319 void named_lin_ineq::find_bounds()
1320 {
1321     poly_iterator Poly(ineqs());
1322     constraint del_list(ineqs().n());
1323     del_list = 0;
1324     for(int a=1; a< ineqs().n(); a++)
1325         if(names()[a].kind() == nte_symconst)
1326             del_list[a] = -1;
1327     // sort by symconsts, then by rank;
1328     Poly.set_sort_order(del_list.data_array());
1329
1330     assert(!~ineqs());
1331     // fm-pairwise project ineqs, sort them;
1332     lin_ineq *M = Poly.get_iterator(0);
1333     assert(!~*M);
1334     // try to get rid of some of the extra constraints;
1335     M = Poly.reduce_extra_constraints2_ptr();
1336     assert(!~*M);
1337     ineqs().init(M);
1338     // sort them again;
1339     ineqs().sort();
1340 }
1341
1342
1343 void named_lin_ineq::add_col(const name_table_entry & nte, int i)
1344 {
1345     names().insert(nte, i);
1346     ineqs().do_insert_col(i);
1347     assert(ineqs().n() == names().n());
1348 }
1349
1350
1351 void named_lin_ineq::project()
1352 {
1353     constraint del_list(n());
1354     del_list = 0;
1355
1356     // sort order is approximately;
1357     // symbolic constants eqns last, then others vaguely by rank;
1358     // (really something close to (rank+sum(i+1 | col i is non-0)));
1359     for(int a=1; a<n(); a++)
1360         if(names()[a].kind() == nte_symconst)
1361             del_list[a] = -1;
1362         else
1363             del_list[a] = 1;
1364
1365     // project
1366     poly_iterator Poly(ineqs());
1367     Poly.set_sort_order(del_list.data_array());
1368     Poly.get_iterator(1);
1369     ineqs().init(Poly.reduce_extra_constraints2_ptr());
1370     ineqs().sort();
1371
1372     cleanup();
1373 }
1374
1375 void named_lin_ineq::project_away(const immed & var, int *changedp)
1376 {
1377     name_table N;
1378     N.insert(name_table_entry(var), 1);
1379     project_away(N, changedp);
1380 }
1381
1382 extern lin_ineq * fast_fourier_motzkin(lin_ineq & in, integer_row *elim = 0,
1383                                        boolean iterate=TRUE);
1384
1385 static void del_unit_stride_rows(lin_ineq &lq,
1386                                  const integer_row &elim)
1387 {
1388     int i, j;
1389     integer_row delrows(lq.m());
1390     for (j=0; j<lq.n(); j++) {
1391         if (elim.c(j))
1392             for (i=0; i<lq.m(); i++) {
1393                 int entry = lq[i][j];
1394                 if (entry)
1395                     if (ABS(entry) <= 1)
1396                         delrows[i]=1; // do del it;
1397             }
1398     }
1399     lq.do_del_rows(delrows);
1400 }
1401
1402 int use_alt_project = 0;
1403 int debug_suifmath_project = 0;
1404
1405 void named_lin_ineq::project_away(const name_table & N, int *changed)
1406 {
1407     constraint elim(n());
1408     int i;
1409     int j=1;
1410
1411     for(i=1; i<N.n(); i++) {           // for each name to be deleted
1412         int pos = names().find(N.e(i).name());  // position of that name
1413         if ((pos > 0) && !elim[pos]) {
1414             elim[pos] = 1;               // filter anything in that pos;
1415             swap_col(pos, n()-j);         // switch it to the end;
1416             elim.do_swap_col(pos, n()-j);
1417             j++;
1418         }
1419     }
1420     if (j==1) return;  // nothing to project;
1421     if (changed) *changed = 1;
1422
1423     // look for existing aux vars; eliminate them, too;
1424     for(i=1; i<n(); i++) {
1425         if (names()[n()-i].kind() == nte_aux) {
1426             if (i>j) {
1427                 swap_col(n()-i, n()-j);
1428             }
1429             elim[n()-j] = 1;
1430             j++;
1431         };
1432     }
1433
1434     // project;
1435     lin_ineq involved = ineqs().filter_thru(elim,0);
1436     if (involved.m() > 0) {
1437         ineqs().do_filter_away(elim,0);
1438         if (debug_suifmath_project) {
1439             fprintf(stderr,"for_project: filtering away, elim:\n");
1440             elim.print(stderr);
1441             fprintf(stderr,"uninvolved:\n");
1442             ineqs().print(stderr);
1443             fprintf(stderr,"involved:\n");
1444             involved.print(stderr);
1445         }
1446         lin_ineq *projeq =
1447              fast_fourier_motzkin(involved, &elim, (use_alt_project > 1));
1448         if (debug_suifmath_project) {
1449             fprintf(stderr,"after projection:\n");
1450             projeq->print(stderr);
1451         }
1452         if (use_alt_project > 0) {
1453             del_unit_stride_rows(*projeq, elim);
1454             if (debug_suifmath_project) {
1455                 fprintf(stderr,"after unit rows deleted:\n");
1456                 projeq->print(stderr);
1457             }
1458             constraint noelim(n());
1459             noelim = 1;
1460             noelim -= elim;
1461             noelim[0] = 0;
1462             projeq->do_filter_thru(noelim,0);
1463         } else {
1464             projeq->do_filter_away(elim,0);
1465         }
1466         if (debug_suifmath_project) {
1467             fprintf(stderr,"after uninteresting rows deleted:\n");
1468             projeq->print(stderr);
1469         }
1470         ineqs() &= *projeq;
1471         if (debug_suifmath_project) {
1472             fprintf(stderr,"replacing uninvolved rows:\n");
1473             ineqs().print(stderr);
1474         }
1475         delete projeq; projeq = 0;
1476         for (i=0; i<n(); i++) {
1477             if (elim[i])
1478                 names()[i].mark_aux();
1479         }
1480         if (debug_suifmath_project) {
1481             fprintf(stderr,"before cleanup:\n");
1482             print(stderr);
1483         }
1484     }
1485
1486     ineqs().sort();
1487     ineqs().del_repetition();
1488     ineqs().del_loose();
1489     cleanup();
1490     return;
1491 }
1492
1493 boolean named_lin_ineq::operator~() const
1494 {
1495     return ~const_ineqs();
1496 }
1497
1498 /***************************************************************************
1499  *                                                                         *
1500  ***************************************************************************/
1501 void named_lin_ineq::print(FILE *fp) const
1502 {
1503 //    fprintf(fp, "       ");
1504 //    for(int i=1; i<names().n(); i++) {
1505 //        fprintf(fp, "%6s",
1506 //                (names()[i].map())?names()[i].map()->name():"       ");
1507 //        fprintf(fp, "%s", (names()[i].kind() == nte_loop)?".":" ");
1508 //    }
1509 //    for(; i<9; i++) fprintf(fp, "       ");
1510 //    fprintf(fp, "%3d %s  <%X>\n", uid(), (is_killed()?"XXX":"   "),
1511 //            get_home());
1512
1513     fprintf(fp, "[%6d] ", unum);
1514     int i;
1515     for(i=1; i<const_names().n(); i++)
1516         fprintf(fp, "%7s",
1517                 (const_names().e(i).string())?const_names().e(i).string():
1518                 "<aux>");
1519     fprintf(fp, "     [ ");
1520     for(i=1; i<const_names().n(); i++) {
1521       char c = '.';
1522       switch(const_names().e(i).kind()) {
1523       case nte_none:       c = '?'; break;
1524       case nte_symconst:   c = 's'; break;
1525       case nte_cond:       c = 'c'; break;
1526       case nte_loop:       c = 'l'; break;
1527       case nte_dim:        c = 'd'; break;
1528       case nte_summary:    c = 'y'; break;
1529       case nte_aux:        c = 'a'; break;
1530       }
1531       fprintf(fp,"%c", c);
1532     }
1533     fprintf(fp, "]\n");
1534     const_ineqs().print(fp);
1535     fprintf(fp, "\n");
1536 }
1537
1538 void named_lin_ineq::print_exp(print_exp_type type, FILE *fp) const
1539 {
1540     if(type == pet_single) assert(const_ineqs().m() == 1);
1541
1542     for(int x=0; x<const_ineqs().m(); x++) {
1543         switch(type) {
1544         case pet_system_nl:
1545             break;
1546         case pet_system:
1547             if(const_ineqs().m() > 1)
1548                 fprintf(fp, "(");
1549             break;
1550         case pet_min:
1551         case pet_max:
1552             if((const_ineqs().m() > 1) && (x==0))
1553                 fprintf(fp, "%s(", (type==pet_min)?"MIN":"MAX");
1554             break;
1555         default:
1556             break;
1557         }
1558
1559         int pr = 0;
1560         integer_row R = const_ineqs().r(x);
1561         if(R[0]) {
1562             fprintf(fp, "%d ", R[0]);
1563             pr = 1;
1564         }
1565
1566         for(int i=1; i<n(); i++)
1567             if(R[i]) {
1568                 if(R[i] == 1) {
1569                     if(pr)
1570                         fprintf(fp, "+ ");
1571                 } else if(R[i] == -1) {
1572                     if(pr)
1573                         fprintf(fp, "- ");
1574                     else
1575                         fprintf(fp, "-");
1576                 } else if(R[i] > 0) {
1577                     if(pr)
1578                         fprintf(fp, "+ %d", R[i]);
1579                     else
1580                         fprintf(fp, "%d", R[i]);
1581                 } else {
1582                     if(pr)
1583                         fprintf(fp, "- %d", -R[i]);
1584                     else
1585                         fprintf(fp, "%d", R[i]);
1586                 }
1587                 fprintf(fp, "%s ", const_names().e(i).string());
1588                 pr = 1;
1589             }
1590         if(pr==0) fprintf(fp, "0 ");
1591         switch(type) {
1592         case pet_system:
1593             fprintf(fp, ">= 0");
1594             if(const_ineqs().m() > 1) fprintf(fp, ")");
1595             if(x < const_ineqs().m()-1)
1596                 fprintf(fp, "&&");
1597             break;
1598         case pet_system_nl:
1599             fprintf(fp, ">= 0\n");
1600             break;
1601         case pet_min:
1602         case pet_max:
1603             if(x < const_ineqs().m()-1)
1604                 fprintf(fp, ", ");
1605             if((const_ineqs().m() >1)&&(x == const_ineqs().m()-1))
1606                 fprintf(fp, ")");
1607             break;
1608         default:
1609             break;
1610         }
1611     }
1612 }
1613
1614
1615 instruction * named_lin_ineq::mk_bounds() const
1616 {
1617     block bnf(0);
1618     constraint filter(n());
1619     filter = 0;
1620     int i;
1621     for(i=1; i<n(); i++)
1622         if(const_names().e(i).kind() == nte_aux)
1623             filter[i] = 1;
1624     lin_ineq Laux    = const_ineqs().filter_thru(filter, -1);
1625             // only A - aux >= 0
1626     lin_ineq Lbounds = const_ineqs().filter_away(filter, 0);
1627
1628     boolean first = TRUE;
1629
1630     for(i=0; i<Lbounds.m(); i++) {
1631         block stmt(Lbounds[i][0]);
1632         for(int j=1; j<n(); j++)
1633             if(const_names().e(j).kind() != nte_aux) {
1634                 int val = Lbounds[i][j];
1635                 block sym((var_sym *)const_names().e(j).name().symbol());
1636                 if(val == 1)
1637                     stmt.set(stmt + sym);
1638                 else if(val == -1)
1639                     stmt.set(stmt - sym);
1640                 else if(val != 0)
1641                     stmt.set(stmt + block(val)*sym);
1642             }
1643         if(first) {
1644             bnf.set(stmt >= block(0));
1645             first = FALSE;
1646         } else
1647             bnf.set(bnf & (stmt >= block(0)));
1648     }
1649
1650     for(i=0; i<Laux.m(); i++) {
1651         block stmt(Laux[i][0]);
1652         int done = FALSE;
1653         for(int j=1; (j<n())&&(!done); j++) {
1654             int val = Laux[i][j];
1655             if(const_names().e(j).kind() != nte_aux) {
1656                 block sym((var_sym *)const_names().e(j).name().symbol());
1657                 if(val == 1)
1658                     stmt.set(stmt + sym);
1659                 else if(val == -1)
1660                     stmt.set(stmt - sym);
1661                 else if(val != 0)
1662                     stmt.set(stmt + block(val)*sym);
1663             } else if(val) {
1664                 done = TRUE;
1665                 if(first) {
1666                     bnf.set((stmt % block(-val)) == block(0));
1667                     first = FALSE;
1668                 } else
1669                     bnf.set(bnf & ((stmt % block(-val)) == block(0)));
1670             }
1671         }
1672     }
1673
1674     base_symtab * bs = const_names().get_symtab();
1675 //    bnf.print();
1676     instruction * ins = bs ? bnf.make_instruction((block_symtab *)bs) : 0;
1677     return ins;
1678 }
1679
1680
1681 instruction * named_lin_ineq::create_expression(const immed & v,
1682                                                 boolean is_ub,
1683                                                 block_symtab * sym) const
1684 {
1685     assert(const_ineqs().m() > 0);
1686     int pos = find(v);
1687     assert(pos > 0);
1688
1689     if(!sym)
1690         sym = (block_symtab *)const_names().get_symtab();
1691     if(!sym)
1692         return 0;
1693
1694     constraint filter(n());
1695     filter = 0;
1696     filter[pos] = 1;
1697     lin_ineq L = const_ineqs().filter_thru(filter, (is_ub)?-1:1);
1698     if(!is_ub) L *= -1;
1699
1700     block exp;
1701     for(int i=0; i<L.m(); i++) {
1702         block curr(L[i][0]);
1703         int val = -1*L[i][pos];
1704         L[i][pos] = 0;
1705         for(int j=1; j<n(); j++)
1706             if(const_names().e(j).name().is_symbol() ||
1707                const_names().e(j).name().is_string()) {
1708                 block var((var_sym *)const_names().e(j).name().symbol());
1709                 if(L[i][j] == 1)
1710                     curr.set(curr + var);
1711                 else if(L[i][j] == -1)
1712                     curr.set(curr - var);
1713                 else if(L[i][j] != 0)
1714                     curr.set(curr + block(L[i][j])*var);
1715             }
1716         if(val != 1)
1717             curr.set(block::op(curr,
1718                                (is_ub)?bop_divfloor:bop_divceil,
1719                                block(val)));
1720         if(i==0)
1721             exp.set(curr);
1722         else
1723             exp.set(block::op(exp, (is_ub)?bop_min:bop_max, curr));
1724     }
1725     instruction * ret = exp.make_instruction(sym);
1726     return ret;
1727 }
1728
1729
1730
1731 /***************************************************************************
1732  *                                                                         *
1733  ***************************************************************************/
1734 boolean named_lin_ineq::is_aligned(const named_lin_ineq & A,
1735                                    const named_lin_ineq & B)
1736 {
1737     const name_table & na = A.const_names();
1738     const name_table & nb = B.const_names();
1739
1740     return name_table::is_aligned(na, nb);
1741 }
1742
1743
1744 /***************************************************************************
1745  *                                                                         *
1746  ***************************************************************************/
1747 void named_lin_ineq::align(const name_table & ant)
1748 {
1749     if(name_table::is_aligned(ant, names())) return;
1750
1751     named_lin_ineq tmp(this);
1752     integer_row rmap(n());
1753     rmap[0] = 0;
1754     int i;
1755     for(i=1; i<n(); i++) {
1756         assert_msg(names()[i].kind() != nte_aux,
1757                    ("Handling aux. vars. is not implemented"));
1758         int x = ant.find(names()[i]);
1759         assert_msg(x > 0, ("The variable %s is not in align name table",
1760                            names()[i].string()));
1761         rmap[i] = x;
1762     }
1763
1764     names().init(ant);
1765     ineqs().init(m(), ant.n());
1766
1767     for(i=0; i<m(); i++)
1768         for(int j=0; j<tmp.n(); j++)
1769             ineqs()[i][rmap[j]] = tmp.ineqs()[i][j];
1770 }
1771
1772
1773 /***************************************************************************
1774  *                                                                         *
1775  ***************************************************************************/
1776 void named_lin_ineq::align_with(named_lin_ineq & B)
1777 {
1778     named_lin_ineq & A = *this;
1779     if(is_aligned(A,B)) return;
1780
1781     A.cleanup();
1782     B.cleanup();
1783
1784     name_table & na = A.names();
1785     name_table & nb = B.names();
1786
1787     // indexes to the new list
1788     integer_row ca(na.n());
1789     integer_row cb(nb.n());
1790
1791     name_table * newnt = name_table::align_tables(na, nb, ca, cb);
1792
1793     A.nt.init(newnt);
1794     B.nt.init(newnt);
1795
1796     // Readjust the inequalities to match the new name table
1797     lin_ineq leqa(A.lq.m(), newnt->n());
1798     int i;
1799     for(i=0; i<A.lq.m(); i++)
1800         for(int j1=0; j1<A.lq.n(); j1++)
1801             leqa[i][ca[j1]] = A.lq[i][j1];
1802     A.lq.init(leqa);
1803
1804     lin_ineq leqb(B.lq.m(), newnt->n());
1805     for(i=0; i<B.lq.m(); i++)
1806         for(int j2=0; j2<B.lq.n(); j2++)
1807             leqb[i][cb[j2]] = B.lq[i][j2];
1808     B.lq.init(leqb);
1809
1810     delete newnt;
1811 }
1812
1813 // reorders the table so element kind ordering matches historical ordering;
1814 // if ca, then sets ca so that new[*ca[i]] = old[i];
1815 void named_lin_ineq::do_reorder_table(integer_row *retca)
1816 {
1817     integer_row ca(n());
1818     boolean changed = nt.do_reorder_table(ca);
1819
1820     if (changed) {
1821         integer_row tmp(n());
1822         for (int j=0; j<m(); j++) {
1823             constraint &rowj = lq[j];
1824             tmp[0] = rowj[0];
1825             for (int i=1; i<n(); i++)
1826                 tmp[ca[i]] = rowj[i];
1827             rowj.init(tmp);
1828         }
1829     }
1830     if (retca) retca->init(ca);
1831 }
1832
1833
1834 /***************************************************************************
1835  *                                                                         *
1836  ***************************************************************************/
1837 named_lin_ineq * named_lin_ineq::merge_named_lin_ineqs(
1838         const named_lin_ineq & A, const named_lin_ineq & B)
1839 {
1840     named_lin_ineq * nA = new named_lin_ineq(A);
1841     named_lin_ineq * nB = new named_lin_ineq(B);
1842     align_named_lin_ineqs(*nA, *nB);
1843
1844     (*nA) &= nB->ineqs();
1845
1846     delete nB;
1847     return nA;
1848 }
1849
1850
1851
1852
1853
1854 /* ##################################################
1855    #####   other routines for debugging only    #####
1856    ################################################## */
1857
1858 /***************************************************************************
1859  *                                                                         *
1860  ***************************************************************************/
1861 void name_table_entry::print(FILE * fp) const
1862 {
1863 //     fprintf(fp, "(");
1864 //     switch(kind()) {
1865 //     case nte_none:
1866 //         fprintf(fp, "n ");
1867 //         break;
1868 //     case nte_symconst:
1869 //         fprintf(fp, "s ");
1870 //         break;
1871 //     case nte_cond:
1872 //         fprintf(fp, "c ");
1873 //         break;
1874 //     case nte_loop:
1875 //         fprintf(fp, "l ");
1876 //         break;
1877 //     default:
1878 //         fprintf(fp, "? ");
1879 //         break;
1880 //     }
1881 //     if(name)
1882 //         name->print();
1883 //     else
1884 //         fprintf(fp, "?");
1885 //     fprintf(fp, " ");
1886 //     if(old_name) old_name->print();
1887 //     fprintf(fp, ")");
1888     fprintf(fp, "%s ", (string())?string():"?");
1889 }
1890
1891
1892 void name_table::print(FILE * fp) const
1893 {
1894     for(int i=1; i<n(); i++) e(i).print(fp);
1895     fprintf(fp, "\n");
1896 }
1897
1898
1899 void name_table::print_symtabs(FILE * fp) const
1900 {
1901     fprintf(fp, "     ");
1902     for(int i=1; i<n(); i++) {
1903       if(e(i).is_var)
1904         fprintf(fp, "%7s", e(i).vsname.v->parent()->name());
1905     }
1906     fprintf(fp, "\n");
1907 }
1908
1909