src/constraintExpr.c

   1 /*
   2 ** constraintExpr.c
   3 */
   4
   5 //#define DEBUGPRINT 1
   6
   7 # include "lclintMacros.nf"
   8 # include "basic.h"
   9 # include "cgrammar.h"
  10 # include "cgrammar_tokens.h"
  11
  12 # include "exprChecks.h"
  13 # include "aliasChecks.h"
  14 # include "exprNodeSList.h"
  15
  16
  17 # include "exprData.i"
  18 # include "exprDataQuite.i"
  19
  20
  21 /*@-czechfcns@*/
  22
  23 #include "constraintExpr.h"
  24
  25
  26
  27
  28 constraintExpr constraintExpr_parseMakeBinaryOp (constraintExpr expr1, lltok op, constraintExpr expr2);
  29
  30 constraintExpr constraintExpr_makeMaxSetConstraintExpr (constraintExpr c);
  31
  32 bool constraintExpr_isLit (constraintExpr expr)
  33 {
  34   llassert (expr);
  35
  36   if (expr->kind == term)
  37     {
  38       constraintTerm term = constraintExprData_termGetTerm (expr->data);
  39       if (constraintTerm_isIntLiteral (term) )
  40         {
  41           return TRUE;
  42         }
  43
  44     }
  45   return FALSE;
  46 }
  47
  48
  49 constraintExpr constraintExpr_propagateConstants (constraintExpr expr,
  50                                                 /*@out@*/ bool * propagate,
  51                                                   /*@out@*/ int *literal)
  52 {
  53   constraintExpr expr1;
  54   constraintExpr expr2;
  55   bool propagate1, propagate2;
  56   int literal1, literal2;
  57
  58   propagate1 = FALSE;
  59   propagate2 = FALSE;
  60
  61   literal1 = 0;
  62   literal2 = 0;
  63
  64   *propagate = FALSE;
  65   *literal = 0;
  66
  67   llassert (expr);
  68
  69   // we simplify unaryExpr else where
  70   if (expr->kind == unaryExpr)
  71     return expr;
  72
  73   if (expr->kind == term)
  74     return expr;
  75
  76   if (constraintExpr_isLit (expr) )
  77     return expr;
  78
  79   BPRINTF( (message("constraintExpr_propagateConstants: binaryexpr: %s", constraintExpr_unparse(expr) ) ) );
  80
  81   expr1 = constraintExprData_binaryExprGetExpr1(expr->data);
  82   expr2 = constraintExprData_binaryExprGetExpr2(expr->data);
  83
  84   expr1 = constraintExpr_propagateConstants (expr1, &propagate1, &literal1);
  85   expr2 = constraintExpr_propagateConstants (expr2, &propagate2, &literal2);
  86
  87   expr->data = constraintExprData_binaryExprSetExpr1 (expr->data, expr1);
  88   expr->data = constraintExprData_binaryExprSetExpr2 (expr->data, expr2);
  89
  90   *propagate = propagate1 || propagate2;
  91   *literal    = literal1 +  literal2;
  92
  93   if ( constraintExpr_isLit (expr1) && constraintExpr_isLit (expr2) )
  94     {
  95       int t1, t2;
  96       t1 = constraintExpr_getValue (expr1);
  97       t2 = constraintExpr_getValue (expr2);
  98       *propagate = FALSE;
  99       if (constraintExprData_binaryExprGetOp (expr->data) == PLUS )
 100         return (constraintExpr_makeIntLiteral ( (t1+t2) ));
 101       else if (constraintExprData_binaryExprGetOp (expr->data) ==  MINUS)
 102         return (constraintExpr_makeIntLiteral ( (t1-t2) ));
 103       else
 104         llassert(FALSE);
 105     }
 106
 107   if (constraintExpr_isLit (expr1) )
 108     {
 109       /*@i334*/
 110       /*handle MINUS case right */
 111       *propagate = TRUE;
 112       *literal += constraintExpr_getValue (expr1);
 113       return expr2;
 114     }
 115
 116
 117   if (constraintExpr_isLit (expr2) )
 118     {
 119       *propagate = TRUE;
 120
 121       if (constraintExprData_binaryExprGetOp (expr->data) == PLUS )
 122         *literal += constraintExpr_getValue (expr2);
 123       else
 124         *literal -= constraintExpr_getValue (expr2);
 125       return expr1;
 126     }
 127
 128
 129
 130   BPRINTF( (message("constraintExpr_propagateConstants returning: %s", constraintExpr_unparse(expr) ) ) );
 131
 132   return expr;
 133 }
 134
 135 constraintExpr constraintExpr_combineConstants (constraintExpr expr )
 136 {
 137   bool propagate;
 138   int literal;
 139
 140   BPRINTF ( (message ("Before combine %s", constraintExpr_unparse(expr) ) ) );
 141   expr = constraintExpr_propagateConstants (expr, &propagate, &literal);
 142
 143
 144   if (propagate)
 145     {
 146       constraintExpr ret;
 147
 148       if (literal != 0)
 149         {
 150           ret = constraintExpr_makeBinaryOpConstraintExprIntLiteral (expr, literal);
 151           expr = ret;
 152         }
 153     }
 154    BPRINTF ( (message ("After combine %s", constraintExpr_unparse(expr) ) ) );
 155   return expr;
 156 }
 157
 158 constraintExpr constraintExpr_alloc (void)
 159 {
 160   constraintExpr ret;
 161   ret = dmalloc (sizeof (*ret) );
 162   ret->kind = term;
 163   ret->data = NULL;
 164   return ret;
 165 }
 166
 167
 168 constraintExpr constraintExpr_copy (constraintExpr expr)
 169 {
 170   constraintExpr ret;
 171   ret = constraintExpr_alloc();
 172   ret->kind = expr->kind;
 173   ret->data = constraintExprData_copy (expr->data, expr->kind);
 174   return ret;
 175 }
 176
 177
 178 constraintExpr oldconstraintExpr_makeTermExprNode (exprNode e)
 179 {
 180   constraintExpr ret;
 181   constraintTerm t;
 182   ret = constraintExpr_alloc();
 183   ret->kind = term;
 184   ret->data = dmalloc (sizeof *(ret->data) );
 185   t = constraintTerm_makeExprNode (e);
 186   ret->data = constraintExprData_termSetTerm (ret->data, t);
 187   return ret;
 188 }
 189
 190 constraintExpr constraintExpr_makeExprNode (exprNode e)
 191 {
 192  sRef s;
 193  constraintExpr ret, ce1, ce2;
 194  exprData data;
 195  exprNode t, t1, t2;
 196  lltok tok;
 197
 198
 199  llassert (e);
 200
 201  data = e->edata;
 202
 203  switch (e->kind)
 204    {
 205    case XPR_SIZEOF:
 206      t = exprData_getSingle (data);
 207      s = exprNode_getSref (t);
 208      if (sRef_isFixedArray(s) )
 209       {
 210         int size;
 211
 212         size = sRef_getArraySize(s);
 213         ret = constraintExpr_makeIntLiteral (size);
 214       }
 215      else
 216        {
 217          BPRINTF ((message ("could not determine the size of %s", exprNode_unparse (e) ) ) );
 218          ret = oldconstraintExpr_makeTermExprNode (e);
 219        }
 220      break;
 221
 222    case XPR_OP:
 223       BPRINTF ((message ("Examining operation %s", exprNode_unparse (e) ) ) );
 224      t1 = exprData_getOpA (data);
 225      t2 = exprData_getOpB (data);
 226      tok = exprData_getOpTok (data);
 227
 228      if (lltok_isPlus_Op (tok) || lltok_isMinus_Op (tok) )
 229        {
 230          ce1 = constraintExpr_makeExprNode (t1);
 231          ce2 = constraintExpr_makeExprNode (t2);
 232          ret = constraintExpr_parseMakeBinaryOp (ce1, tok, ce2);
 233        }
 234      else
 235        {
 236         ret = oldconstraintExpr_makeTermExprNode (e);
 237        }
 238      break;
 239    case XPR_PARENS:
 240      t = exprData_getUopNode (data);
 241      ret = constraintExpr_makeExprNode (t);
 242      break;
 243
 244    case XPR_PREOP:
 245       t = exprData_getUopNode (data);
 246       tok =  exprData_getUopTok (data);
 247       if (lltok_isInc_Op (tok) )
 248         {
 249           constraintExpr temp;
 250           temp = constraintExpr_makeExprNode(t);
 251           ret = constraintExpr_makeIncConstraintExpr(temp);
 252         }
 253       else if (lltok_isDec_Op (tok) )
 254         {
 255           constraintExpr temp;
 256           temp = constraintExpr_makeExprNode(t);
 257           ret = constraintExpr_makeDecConstraintExpr(temp);
 258         }
 259       else
 260         ret =  oldconstraintExpr_makeTermExprNode (e);
 261       break;
 262
 263    case XPR_POSTOP:
 264      t = exprData_getUopNode (data);
 265           ret = constraintExpr_makeExprNode (t);
 266      break;
 267    default:
 268      ret = oldconstraintExpr_makeTermExprNode (e);
 269
 270    }
 271   return ret;
 272 }
 273
 274
 275 constraintExpr constraintExpr_makeTermExprNode (exprNode e)
 276 {
 277   return  oldconstraintExpr_makeTermExprNode(e); //constraintExpr_makeExprNode (e);
 278 }
 279
 280
 281 constraintExpr constraintExpr_makeTermsRef (sRef s)
 282 {
 283   constraintExpr ret;
 284   constraintTerm t;
 285   ret = constraintExpr_alloc();
 286   ret->kind = term;
 287   ret->data = dmalloc (sizeof *(ret->data) );
 288   t = constraintTerm_makesRef (s);
 289   ret->data = constraintExprData_termSetTerm (ret->data, t);
 290   return ret;
 291 }
 292
 293 constraintExpr constraintExpr_makeUnaryOp (void)
 294 {
 295   constraintExpr ret;
 296   ret = constraintExpr_alloc();
 297   ret->kind = unaryExpr;
 298   ret->data = dmalloc ( sizeof *(ret->data) );
 299   return ret;
 300 }
 301
 302 constraintExpr constraintExpr_makeUnaryOpConstraintExpr (constraintExpr cexpr)
 303 {
 304   constraintExpr ret;
 305   ret = constraintExpr_makeUnaryOp();
 306   ret->data = constraintExprData_unaryExprSetExpr (ret->data, cexpr);
 307   return ret;
 308 }
 309
 310 constraintExpr constraintExpr_makeMaxSetConstraintExpr (constraintExpr c)
 311 {
 312   constraintExpr ret;
 313   ret = constraintExpr_makeUnaryOpConstraintExpr (c);
 314   ret->data = constraintExprData_unaryExprSetOp (ret->data, MAXSET);
 315   return ret;
 316 }
 317
 318 constraintExpr constraintExpr_makeUnaryOpExprNode (exprNode expr)
 319 {
 320   constraintExpr ret;
 321   constraintExpr sub;
 322   sub = constraintExpr_makeExprNode (expr);
 323   ret = constraintExpr_makeUnaryOpConstraintExpr(sub);
 324   return ret;
 325 }
 326
 327
 328
 329 constraintExpr constraintExpr_makeSRefUnaryOp (sRef s,  constraintExprUnaryOpKind op)
 330 {
 331   constraintExpr ret;
 332   constraintExpr t;
 333
 334   t = constraintExpr_makeTermsRef (s);
 335   ret = constraintExpr_makeUnaryOpConstraintExpr (t);
 336   ret->data = constraintExprData_unaryExprSetOp (ret->data, op);
 337   return ret;
 338 }
 339
 340 constraintExpr constraintExpr_makeSRefMaxset (sRef s)
 341 {
 342   return (constraintExpr_makeSRefUnaryOp (s, MAXSET) );
 343 }
 344
 345 constraintExpr constraintExpr_parseMakeUnaryOp (lltok op, constraintExpr cexpr)
 346 {
 347   constraintExpr ret;
 348   ret = constraintExpr_makeUnaryOpConstraintExpr ( cexpr);
 349
 350   switch (op.tok)
 351     {
 352     case QMAXSET:
 353       ret->data = constraintExprData_unaryExprSetOp (ret->data, MAXSET);
 354       break;
 355     case QMAXREAD:
 356       ret->data = constraintExprData_unaryExprSetOp (ret->data, MAXREAD);
 357       break;
 358     default:
 359       llfatalbug("Unhandled Operation in Constraint");
 360     }
 361   return ret;
 362 }
 363
 364 constraintExpr constraintExpr_makeMaxSetExpr (exprNode expr)
 365 {
 366   constraintExpr ret;
 367   ret = constraintExpr_makeExprNode (expr);
 368
 369   ret = constraintExpr_makeMaxSetConstraintExpr (ret);
 370
 371   llassert (ret);
 372   return ret;
 373 }
 374
 375 constraintExpr  constraintExpr_makeMaxReadExpr (exprNode expr)
 376 {
 377   constraintExpr ret;
 378   ret = constraintExpr_makeUnaryOpExprNode(expr);
 379   ret->data      = constraintExprData_unaryExprSetOp (ret->data, MAXREAD);
 380   return ret;
 381 }
 382
 383 constraintExpr  constraintExpr_makeMinSetExpr (exprNode expr)
 384 {
 385   constraintExpr ret;
 386   ret = constraintExpr_makeUnaryOpExprNode(expr);
 387   ret->data      = constraintExprData_unaryExprSetOp (ret->data, MINSET);
 388   return ret;
 389 }
 390
 391 constraintExpr  constraintExpr_makeMinReadExpr (exprNode expr)
 392 {
 393   constraintExpr ret;
 394   ret = constraintExpr_makeUnaryOpExprNode(expr);
 395   ret->data      = constraintExprData_unaryExprSetOp (ret->data, MINREAD);
 396   return ret;
 397 }
 398
 399
 400 constraintExpr constraintExpr_makeValueExpr (exprNode expr)
 401 {
 402   constraintExpr ret;
 403   ret = constraintExpr_makeExprNode (expr);
 404   return ret;
 405 }
 406
 407 constraintExpr constraintExpr_makeIntLiteral (int i)
 408 {
 409   constraintExpr ret;
 410   constraintTerm t;
 411   ret = constraintExpr_alloc();
 412   ret->kind = term;
 413   ret->data = dmalloc (sizeof *(ret->data) );
 414   t = constraintTerm_makeIntLiteral (i);
 415   ret->data = constraintExprData_termSetTerm (ret->data, t);
 416   return ret;
 417 }
 418
 419
 420 constraintExpr constraintExpr_makeValueInt (int i)
 421 {
 422   return constraintExpr_makeIntLiteral (i);
 423 }
 424
 425 static constraintExpr constraintExpr_makeBinaryOp (void)
 426 {
 427   constraintExpr ret;
 428   ret = constraintExpr_alloc();
 429   ret->kind = binaryexpr;
 430   ret->data = dmalloc ( sizeof *(ret->data) );
 431   ret->data = constraintExprData_binaryExprSetOp (ret->data, PLUS);
 432   return ret;
 433 }
 434
 435
 436 constraintExpr constraintExpr_makeBinaryOpConstraintExpr (constraintExpr expr1,constraintExpr expr2)
 437
 438 {
 439   constraintExpr ret;
 440   ret = constraintExpr_makeBinaryOp();
 441   ret->data = constraintExprData_binaryExprSetExpr1 (ret->data, expr1);
 442   ret->data = constraintExprData_binaryExprSetExpr2 (ret->data, expr2);
 443   return ret;
 444 }
 445
 446 constraintExpr constraintExpr_parseMakeBinaryOp (constraintExpr expr1, lltok op, constraintExpr expr2)
 447 {
 448   constraintExpr ret;
 449   ret = constraintExpr_makeBinaryOpConstraintExpr (expr1, expr2);
 450   if (op.tok == TPLUS)
 451     ret->data = constraintExprData_binaryExprSetOp(ret->data, PLUS);
 452   else if (op.tok == TMINUS)
 453     ret->data = constraintExprData_binaryExprSetOp(ret->data, MINUS);
 454     else
 455       {
 456         llassert(FALSE);
 457       }
 458   return ret;
 459 }
 460
 461 constraintExpr constraintExpr_makeBinaryOpExprNode (exprNode expr1, exprNode expr2)
 462 {
 463   constraintExpr ret;
 464   constraintExpr sub1, sub2;
 465   sub1 = constraintExpr_makeTermExprNode (expr1);
 466   sub2 = constraintExpr_makeTermExprNode (expr2);
 467   ret = constraintExpr_makeBinaryOpConstraintExpr(sub1, sub2);
 468   return ret;
 469 }
 470
 471 constraintExpr constraintExpr_makeBinaryOpConstraintExprIntLiteral (constraintExpr expr, int literal)
 472 {
 473   constraintExpr ret;
 474   constraintExpr constExpr;
 475
 476   constExpr = constraintExpr_makeIntLiteral (literal);
 477   ret = constraintExpr_makeBinaryOpConstraintExpr (expr, constExpr);
 478   ret->data = constraintExprData_binaryExprSetOp(ret->data, PLUS);
 479   return ret;
 480 }
 481
 482 constraintExpr constraintExpr_makeDecConstraintExpr (constraintExpr expr)
 483 {
 484   constraintExpr ret;
 485   constraintExpr inc;
 486
 487   inc = constraintExpr_makeIntLiteral (1);
 488   ret = constraintExpr_makeBinaryOpConstraintExpr (expr, inc);
 489   ret->data = constraintExprData_binaryExprSetOp(ret->data, MINUS);
 490   return ret;
 491 }
 492
 493 constraintExpr constraintExpr_makeAddConstraintExpr (constraintExpr expr, constraintExpr add)
 494 {
 495   constraintExpr ret;
 496
 497   ret = constraintExpr_makeBinaryOpConstraintExpr (expr, add);
 498
 499   ret->data = constraintExprData_binaryExprSetOp(ret->data, PLUS);
 500
 501   return ret;
 502 }
 503
 504 constraintExpr constraintExpr_makeIncConstraintExpr (constraintExpr expr)
 505 {
 506   constraintExpr ret;
 507   constraintExpr inc;
 508
 509   inc = constraintExpr_makeIntLiteral (1);
 510   ret = constraintExpr_makeBinaryOpConstraintExpr (expr, inc);
 511   ret->data = constraintExprData_binaryExprSetOp(ret->data, PLUS);
 512   return ret;
 513 }
 514
 515 cstring constraintExprUnaryOpKind_print (constraintExprUnaryOpKind op)
 516 {
 517   switch (op)
 518     {
 519     case MAXSET:
 520       return message("MAXSET");
 521     case MINSET:
 522       return message("MINSET");
 523     case MAXREAD:
 524       return message("MAXREAD");
 525     case MINREAD:
 526       return message("MINREAD");
 527     default:
 528       llassert(FALSE);
 529       return message ("<(Unary OP OTHER>");
 530     }
 531 }
 532
 533
 534 cstring constraintExprBinaryOpKind_print (constraintExprBinaryOpKind op)
 535 {
 536
 537   switch (op)
 538     {
 539     case PLUS:
 540       return message("+");
 541     case MINUS:
 542       return message("-");
 543     }
 544   llassert(FALSE);
 545   return message ("<binary OP Unknown>");
 546 }
 547
 548 bool constraintExpr_similar (constraintExpr expr1, constraintExpr expr2)
 549 {
 550   constraintExprKind kind;
 551
 552   llassert (expr1 != NULL);
 553   llassert (expr2 != NULL);
 554   if (expr1->kind != expr2->kind)
 555     return FALSE;
 556
 557   kind = expr1->kind;
 558
 559   switch (kind)
 560     {
 561     case term:
 562       return constraintTerm_similar (constraintExprData_termGetTerm(expr1->data),
 563                                   constraintExprData_termGetTerm(expr2->data) );
 564       break;
 565
 566     case unaryExpr:
 567       if (constraintExprData_unaryExprGetOp (expr1->data) != constraintExprData_unaryExprGetOp (expr2->data) )
 568         return FALSE;
 569
 570       return (constraintExpr_similar (
 571               constraintExprData_unaryExprGetExpr (expr1->data),
 572               constraintExprData_unaryExprGetExpr (expr2->data)
 573               ));
 574
 575     case binaryexpr:
 576       if (constraintExprData_binaryExprGetOp (expr1->data) != constraintExprData_binaryExprGetOp (expr2->data) )
 577         return FALSE;
 578
 579       if (! constraintExpr_similar (constraintExprData_binaryExprGetExpr1 (expr1->data),
 580                                  constraintExprData_binaryExprGetExpr1 (expr2->data)) )
 581         return FALSE;
 582
 583       if (! constraintExpr_similar (constraintExprData_binaryExprGetExpr2 (expr1->data),
 584                                  constraintExprData_binaryExprGetExpr2 (expr2->data)) )
 585         return FALSE;
 586       else
 587         return TRUE;
 588       /*@notreached@*/
 589       break;
 590
 591     default:
 592       llassert(FALSE);
 593       return FALSE;
 594     }
 595   /*@notreached@*/
 596   return FALSE;
 597 }
 598
 599 bool constraintExpr_same (constraintExpr expr1, constraintExpr expr2)
 600 {
 601   constraintExprKind kind;
 602
 603   llassert (expr1 != NULL);
 604   llassert (expr2 != NULL);
 605   if (expr1->kind != expr2->kind)
 606     return FALSE;
 607
 608   kind = expr1->kind;
 609
 610   switch (kind)
 611     {
 612     case term:
 613       return constraintTerm_similar (constraintExprData_termGetTerm(expr1->data),
 614                                   constraintExprData_termGetTerm(expr2->data) );
 615       break;
 616
 617     case unaryExpr:
 618       if (constraintExprData_unaryExprGetOp (expr1->data) != constraintExprData_unaryExprGetOp (expr2->data) )
 619         return FALSE;
 620
 621       return (constraintExpr_same (
 622               constraintExprData_unaryExprGetExpr (expr1->data),
 623               constraintExprData_unaryExprGetExpr (expr2->data)
 624               ));
 625
 626
 627     case binaryexpr:
 628       if (constraintExprData_binaryExprGetOp (expr1->data) != constraintExprData_binaryExprGetOp (expr2->data) )
 629         return FALSE;
 630
 631       if (! constraintExpr_same (constraintExprData_binaryExprGetExpr1 (expr1->data),
 632                                  constraintExprData_binaryExprGetExpr1 (expr2->data)) )
 633         return FALSE;
 634
 635       if (! constraintExpr_same (constraintExprData_binaryExprGetExpr2 (expr1->data),
 636                                  constraintExprData_binaryExprGetExpr2 (expr2->data)) )
 637         return FALSE;
 638       else
 639         return TRUE;
 640       break;
 641
 642     default:
 643       llassert(FALSE);
 644       return FALSE;
 645     }
 646
 647   /*@notreached@*/
 648   BADEXIT;
 649 }
 650
 651 bool constraintExpr_search (constraintExpr c, constraintExpr old)
 652 {
 653   bool ret = FALSE;
 654   constraintExprKind kind;
 655   constraintExpr temp;
 656
 657   if ( constraintExpr_similar (c, old) )
 658     {
 659       #warning mem leak
 660       DPRINTF((message ("Found  %s",
 661                         constraintExpr_unparse(old)
 662                         )));
 663       return TRUE;
 664     }
 665
 666   kind = c->kind;
 667
 668   switch (kind)
 669     {
 670     case term:
 671       break;
 672     case unaryExpr:
 673       temp = constraintExprData_unaryExprGetExpr (c->data);
 674       ret = ret || constraintExpr_search (temp, old);
 675       break;
 676     case binaryexpr:
 677
 678       temp = constraintExprData_binaryExprGetExpr1 (c->data);
 679       ret = ret || constraintExpr_search(temp, old);
 680
 681       temp = constraintExprData_binaryExprGetExpr2 (c->data);
 682       ret = ret || constraintExpr_search(temp, old);
 683       break;
 684     default:
 685       llassert(FALSE);
 686     }
 687   return ret;
 688
 689 }
 690
 691
 692 constraintExpr constraintExpr_searchandreplace (constraintExpr c, constraintExpr old, constraintExpr new )
 693 {
 694   constraintExprKind kind;
 695   constraintExpr temp;
 696
 697   if ( constraintExpr_similar (c, old) )
 698     {
 699       #warning mem leak
 700       BPRINTF((message ("Replacing %s with %s",
 701                         constraintExpr_unparse(old), constraintExpr_unparse(new)
 702                         )));
 703       return constraintExpr_copy (new);
 704     }
 705
 706   kind = c->kind;
 707
 708   switch (kind)
 709     {
 710     case term:
 711       break;
 712     case unaryExpr:
 713       temp = constraintExprData_unaryExprGetExpr (c->data);
 714       temp = constraintExpr_searchandreplace (temp, old, new);
 715       c->data = constraintExprData_unaryExprSetExpr (c->data, temp);
 716       break;
 717     case binaryexpr:
 718
 719       temp = constraintExprData_binaryExprGetExpr1 (c->data);
 720       temp = constraintExpr_searchandreplace (temp, old, new);
 721       c->data = constraintExprData_binaryExprSetExpr1 (c->data, temp);
 722
 723       temp = constraintExprData_binaryExprGetExpr2 (c->data);
 724       temp = constraintExpr_searchandreplace (temp, old, new);
 725       c->data = constraintExprData_binaryExprSetExpr2 (c->data, temp);
 726       break;
 727     default:
 728       llassert(FALSE);
 729     }
 730   return c;
 731
 732 }
 733
 734 constraintExpr constraintExpr_simplifyChildren (constraintExpr c)
 735 {
 736   constraintExprKind kind;
 737   constraintExpr temp;
 738
 739   kind = c->kind;
 740
 741   switch (kind)
 742     {
 743     case term:
 744       break;
 745     case unaryExpr:
 746       temp = constraintExprData_unaryExprGetExpr (c->data);
 747       temp = constraintExpr_simplify (temp);
 748       c->data = constraintExprData_unaryExprSetExpr (c->data, temp);
 749       break;
 750     case binaryexpr:
 751       BPRINTF((message("constraintExpr_simplfiyChildren: simplify binary expression: %s",constraintExpr_unparse(c) ) ) );
 752       temp = constraintExprData_binaryExprGetExpr1 (c->data);
 753       temp = constraintExpr_simplify (temp);
 754
 755       c->data = constraintExprData_binaryExprSetExpr1 (c->data, temp);
 756
 757       temp = constraintExprData_binaryExprGetExpr2 (c->data);
 758       temp = constraintExpr_simplify (temp);
 759
 760       c->data = constraintExprData_binaryExprSetExpr2 (c->data, temp);
 761       break;
 762     default:
 763       llassert(FALSE);
 764     }
 765   return c;
 766
 767 }
 768
 769
 770 constraintExpr constraintExpr_setFileloc (constraintExpr c, fileloc loc)
 771 {
 772   constraintTerm t;
 773   constraintExpr temp;
 774
 775   llassert(c);
 776
 777   switch (c->kind)
 778     {
 779     case term:
 780       t = constraintExprData_termGetTerm (c->data);
 781       t = constraintTerm_setFileloc (t, loc);
 782       c->data = constraintExprData_termSetTerm (c->data, t);
 783       break;
 784     case binaryexpr:
 785
 786       temp = constraintExprData_binaryExprGetExpr1 (c->data);
 787       temp = constraintExpr_setFileloc (temp, loc);
 788       c->data = constraintExprData_binaryExprSetExpr1 (c->data, temp);
 789
 790       temp = constraintExprData_binaryExprGetExpr2 (c->data);
 791       temp = constraintExpr_setFileloc (temp, loc);
 792       c->data = constraintExprData_binaryExprSetExpr2 (c->data, temp);
 793       break;
 794     case unaryExpr:
 795       temp = constraintExprData_unaryExprGetExpr (c->data);
 796       temp = constraintExpr_setFileloc (temp, loc);
 797       c->data = constraintExprData_unaryExprSetExpr (c->data, temp);
 798       break;
 799     }
 800   return c;
 801 }
 802
 803 constraintExpr constraintExpr_simplifybinaryExpr (constraintExpr c)
 804 {
 805   constraintExpr e1, e2;
 806
 807   e1 = constraintExprData_binaryExprGetExpr1 (c->data);
 808   e2 = constraintExprData_binaryExprGetExpr2 (c->data);
 809
 810   if (constraintExpr_canGetValue (e1) && constraintExpr_canGetValue(e2) )
 811     {
 812       int i;
 813
 814       i = constraintExpr_getValue(e1) + constraintExpr_getValue (e2);
 815
 816       c = constraintExpr_makeIntLiteral (i);
 817
 818     }
 819   return c;
 820 }
 821
 822
 823 constraintExpr constraintExpr_subtractExpr (constraintExpr expr, constraintExpr addent)
 824 {
 825   constraintExpr  new;
 826
 827   BPRINTF ( (message ("Doing subtraceTerm simplification") ) );
 828
 829   new = constraintExpr_makeBinaryOpConstraintExpr (expr, addent);
 830   new->data = constraintExprData_binaryExprSetOp (new->data, MINUS);
 831   return new;
 832 }
 833
 834 constraintExpr constraintExpr_addExpr (constraintExpr expr, constraintExpr addent)
 835 {
 836   constraintExpr  new;
 837
 838  BPRINTF ( (message ("Doing addTerm simplification") ) );
 839
 840   new = constraintExpr_makeBinaryOpConstraintExpr (expr, addent);
 841   new->data = constraintExprData_binaryExprSetOp (new->data, PLUS);
 842   return new;
 843 }
 844
 845 constraintExpr constraintExpr_solveBinaryExpr (constraintExpr lexpr, constraintExpr expr)
 846 {
 847   constraintExpr expr1, expr2;
 848   constraintExprBinaryOpKind op;
 849
 850   if (lexpr->kind != binaryexpr)
 851     return expr;
 852
 853   expr2 = constraintExprData_binaryExprGetExpr2 (lexpr->data);
 854   expr1 = constraintExprData_binaryExprGetExpr1 (lexpr->data);
 855   op    = constraintExprData_binaryExprGetOp (lexpr->data);
 856
 857
 858   //  if (constraintExpr_canGetValue (expr2) )
 859     {
 860       #warning make sure this works
 861
 862       lexpr->kind = expr1->kind;
 863       lexpr->data = constraintExprData_copy (expr1->data, expr1->kind);
 864
 865
 866       if (op == PLUS)
 867         expr = constraintExpr_subtractExpr (expr, expr2);
 868       else
 869         expr = constraintExpr_addExpr (expr, expr2);
 870
 871       return expr;
 872     }
 873   expr = constraintExpr_solveBinaryExpr (expr1, expr);
 874
 875   expr = constraintExpr_solveBinaryExpr (expr2, expr);
 876   return expr;
 877 }
 878
 879 constraintExpr constraintExpr_simplifyunaryExpr (constraintExpr c)
 880 {
 881   constraintExpr exp;
 882
 883   llassert (c->kind == unaryExpr);
 884
 885   BPRINTF ( (message ("Doing constraintExpr_simplifyunaryExpr:%s", constraintExpr_unparse (c) ) ) );
 886
 887   if ( (constraintExprData_unaryExprGetOp (c->data) != MAXSET) &&
 888        (constraintExprData_unaryExprGetOp (c->data) != MAXREAD) )
 889     {
 890       return c;
 891     }
 892   // pattern mxr ( var + const) = mxr(var) - const
 893
 894   exp = constraintExprData_unaryExprGetExpr (c->data);
 895
 896   if (exp->kind == term)
 897     {
 898       constraintTerm cterm;
 899
 900       cterm = constraintExprData_termGetTerm (exp->data);
 901
 902       if (constraintTerm_isStringLiteral(cterm) )
 903         {
 904           cstring val;
 905           val = constraintTerm_getStringLiteral (cterm);
 906           if (constraintExprData_unaryExprGetOp (c->data) == MAXSET)
 907             {
 908               return constraintExpr_makeIntLiteral (strlen (val) );
 909             }
 910           if (constraintExprData_unaryExprGetOp (c->data) == MAXREAD)
 911             {
 912               return constraintExpr_makeIntLiteral (strlen (val) );
 913             }
 914           BADEXIT;
 915         }
 916       return c;
 917     }
 918
 919   if (exp->kind != binaryexpr)
 920     return c;
 921
 922   if (constraintExprData_binaryExprGetOp (exp->data) == PLUS  )
 923     {
 924
 925       //      if (constraintExpr_canGetValue (constraintExprData_binaryExprGetExpr2 (exp->data) ) )
 926         {
 927
 928           constraintExpr  temp, temp2, new;
 929
 930           DPRINTF ( (message ("Doing fancy simplification") ) );
 931
 932           temp = constraintExprData_binaryExprGetExpr2 (exp->data);
 933
 934           temp2 = constraintExprData_binaryExprGetExpr1 (exp->data);
 935           c->data = constraintExprData_unaryExprSetExpr (c->data, temp2);
 936
 937
 938
 939           new = constraintExpr_subtractExpr (c, temp);
 940
 941           DPRINTF ( (message ("Done fancy simplification:%s", constraintExpr_unparse (new) ) ) );
 942
 943           c = new;
 944         }
 945     }
 946
 947   DPRINTF ( (message ("Done simplification:%s", constraintExpr_unparse (c) ) ) );
 948   return c;
 949 }
 950
 951
 952 constraintExpr constraintExpr_simplify (constraintExpr c)
 953 {
 954   constraintExprKind kind;
 955   constraintTerm t;
 956
 957
 958   BPRINTF ( (message ("Doing constraintExpr_simplify:%s", constraintExpr_unparse (c) ) ) );
 959
 960   c = constraintExpr_simplifyChildren (c);
 961   c = constraintExpr_combineConstants (c);
 962   c = constraintExpr_simplifyChildren (c);
 963
 964   kind = c->kind;
 965
 966   switch (kind)
 967     {
 968     case term:
 969       t = constraintExprData_termGetTerm (c->data);
 970       t = constraintTerm_simplify (t);
 971       c->data = constraintExprData_termSetTerm (c->data, t);
 972       break;
 973     case unaryExpr:
 974       c = constraintExpr_simplifyunaryExpr (c);
 975       break;
 976     case binaryexpr:
 977       c = constraintExpr_simplifybinaryExpr (c);
 978       break;
 979     default:
 980       llassert(FALSE);
 981     }
 982   return c;
 983
 984 }
 985
 986 cstring constraintExpr_unparse (constraintExpr ex)
 987 {
 988   cstring st;
 989   constraintExprKind kind;
 990
 991   llassert (ex != NULL);
 992
 993   kind = ex->kind;
 994
 995   switch (kind)
 996     {
 997     case term:
 998       st = message ("(%s) ", constraintTerm_print (constraintExprData_termGetTerm(ex->data) ) );
 999       break;
1000     case unaryExpr:
1001       st = message ("%s (%s)",
1002                     constraintExprUnaryOpKind_print (constraintExprData_unaryExprGetOp (ex->data)
1003                                                      ),
1004                     constraintExpr_unparse (constraintExprData_unaryExprGetExpr (ex->data) )
1005                     );
1006       break;
1007     case binaryexpr:
1008       st = message ("(%s) %s (%s)",
1009                     constraintExpr_unparse (constraintExprData_binaryExprGetExpr1 (ex->data) ),
1010                     constraintExprBinaryOpKind_print (constraintExprData_binaryExprGetOp (ex->data)
1011                                                      ),
1012                     constraintExpr_unparse (constraintExprData_binaryExprGetExpr2 (ex->data) )
1013                     );
1014       break;
1015     default:
1016       llassert(FALSE);
1017       st = message ("error");
1018
1019     }
1020
1021   DPRINTF((message ("constraintExpr_unparse: '%s'",st) ) );
1022   return st;
1023 }
1024
1025 constraintExpr constraintExpr_doSRefFixBaseParam (/*@returned@*/  constraintExpr expr, exprNodeList arglist)
1026 {
1027   constraintTerm Term;
1028   constraintExprKind kind;
1029   constraintExpr expr1, expr2;
1030   constraintExprData data;
1031   llassert (expr != NULL);
1032
1033   data = expr->data;
1034
1035   kind = expr->kind;
1036
1037   switch (kind)
1038     {
1039     case term:
1040       Term = constraintExprData_termGetTerm(data);
1041       Term = constraintTerm_doSRefFixBaseParam (Term, arglist);
1042       data = constraintExprData_termSetTerm(data, Term);
1043       break;
1044     case unaryExpr:
1045       expr1 = constraintExprData_unaryExprGetExpr (data);
1046       expr1 = constraintExpr_doSRefFixBaseParam (expr1, arglist);
1047       data = constraintExprData_unaryExprSetExpr (data, expr1);
1048       break;
1049     case binaryexpr:
1050       expr1 = constraintExprData_binaryExprGetExpr1 (data);
1051       expr2 = constraintExprData_binaryExprGetExpr2 (data);
1052
1053       expr1 = constraintExpr_doSRefFixBaseParam (expr1, arglist);
1054       data = constraintExprData_binaryExprSetExpr1 (data, expr1);
1055       expr2 = constraintExpr_doSRefFixBaseParam (expr2, arglist);
1056       data = constraintExprData_binaryExprSetExpr2 (data, expr2);
1057
1058       break;
1059     default:
1060       llassert(FALSE);
1061       data = NULL;
1062     }
1063   return expr;
1064 }
1065
1066 constraintExpr constraintExpr_doSRefFixConstraintParam (/*@returned@*/  constraintExpr expr, exprNodeList arglist)
1067 {
1068   constraintExprKind kind;
1069   constraintExpr expr1, expr2;
1070   constraintExprData data;
1071   llassert (expr != NULL);
1072
1073   data = expr->data;
1074
1075   kind = expr->kind;
1076
1077   switch (kind)
1078     {
1079     case term:
1080       expr = constraintTerm_doSRefFixConstraintParam (expr, arglist);
1081       break;
1082     case unaryExpr:
1083       expr1 = constraintExprData_unaryExprGetExpr (data);
1084       expr1 = constraintExpr_doSRefFixConstraintParam (expr1, arglist);
1085       data = constraintExprData_unaryExprSetExpr (data, expr1);
1086       break;
1087     case binaryexpr:
1088       expr1 = constraintExprData_binaryExprGetExpr1 (data);
1089       expr2 = constraintExprData_binaryExprGetExpr2 (data);
1090
1091       expr1 = constraintExpr_doSRefFixConstraintParam (expr1, arglist);
1092       data = constraintExprData_binaryExprSetExpr1 (data, expr1);
1093       expr2 = constraintExpr_doSRefFixConstraintParam (expr2, arglist);
1094       data = constraintExprData_binaryExprSetExpr2 (data, expr2);
1095
1096       break;
1097     default:
1098       llassert(FALSE);
1099       data = NULL;
1100     }
1101   return expr;
1102 }
1103
1104 constraintExpr constraintExpr_doFixResult (/*@returned@*/  constraintExpr expr, exprNode fcnCall)
1105 {
1106   constraintExprKind kind;
1107   constraintExpr expr1, expr2;
1108   constraintExprData data;
1109   llassert (expr != NULL);
1110
1111   data = expr->data;
1112
1113   kind = expr->kind;
1114
1115   switch (kind)
1116     {
1117     case term:
1118       expr = constraintTerm_doFixResult (expr, fcnCall);
1119       break;
1120     case unaryExpr:
1121       expr1 = constraintExprData_unaryExprGetExpr (data);
1122       expr1 = constraintExpr_doFixResult (expr1, fcnCall);
1123       data = constraintExprData_unaryExprSetExpr (data, expr1);
1124       break;
1125     case binaryexpr:
1126       expr1 = constraintExprData_binaryExprGetExpr1 (data);
1127       expr2 = constraintExprData_binaryExprGetExpr2 (data);
1128
1129       expr1 = constraintExpr_doFixResult (expr1, fcnCall);
1130       data = constraintExprData_binaryExprSetExpr1 (data, expr1);
1131       expr2 = constraintExpr_doFixResult (expr2, fcnCall);
1132       data = constraintExprData_binaryExprSetExpr2 (data, expr2);
1133
1134       break;
1135     default:
1136       llassert(FALSE);
1137       data = NULL;
1138     }
1139   return expr;
1140 }
1141
1142 cstring constraintExpr_print (constraintExpr expr)
1143 {
1144   return constraintExpr_unparse(expr);
1145 }
1146
1147 bool constraintExpr_hasMaxSet (constraintExpr expr)
1148 {
1149   cstring t;
1150
1151   t = constraintExpr_unparse(expr);
1152
1153   return (strstr (t, "MAXSET") );
1154 }
1155
1156
1157
1158       /*returns 1 0 -1 like strcmp
1159         1 => expr1 > expr2
1160         0 => expr1 == expr2
1161         -1 => expr1 < expr2
1162        */
1163 int constraintExpr_compare (constraintExpr expr1, constraintExpr expr2)
1164 {
1165   int value1, value2;
1166
1167   if (constraintExpr_similar (expr1, expr2) )
1168     {
1169       return 0;
1170     }
1171   value1 = constraintExpr_getValue(expr1);
1172   value2 = constraintExpr_getValue(expr2);
1173
1174   if (value1 > value2)
1175     return 1;
1176
1177   if (value1 == value2)
1178     return 0;
1179
1180   else
1181     return -1;
1182 }
1183
1184 int constraintExpr_getValue (constraintExpr expr)
1185 {
1186   llassert (expr->kind == term);
1187   return (constraintTerm_getValue (constraintExprData_termGetTerm (expr->data) ) );
1188 }
1189
1190 bool constraintExpr_canGetValue (constraintExpr expr)
1191 {
1192   switch (expr->kind)
1193     {
1194     case term:
1195       return constraintTerm_canGetValue (constraintExprData_termGetTerm (expr->data) );
1196     default:
1197       return FALSE;
1198
1199     }
1200         llassert(FALSE);
1201 }
1202
1203 bool constraintExpr_canCompare (constraintExpr expr1, constraintExpr expr2)
1204 {
1205
1206   llassert(expr1 && expr2);
1207   return (  constraintExpr_canGetValue(expr1) &&
1208             constraintExpr_canGetValue(expr2)
1209             );
1210 }
1211
1212
1213 fileloc constraintExpr_getFileloc (constraintExpr expr)
1214 {
1215   constraintExpr e;
1216 constraintTerm t;
1217   constraintExprKind kind;
1218
1219  kind = expr->kind;
1220
1221   switch (kind)
1222     {
1223     case term:
1224       t = constraintExprData_termGetTerm (expr->data);
1225       return (constraintTerm_getFileloc (t) );
1226       break;
1227     case unaryExpr:
1228       e = constraintExprData_unaryExprGetExpr (expr->data);
1229       return (constraintExpr_getFileloc (e) );
1230       break;
1231     case binaryexpr:
1232       e = constraintExprData_binaryExprGetExpr1 (expr->data);
1233       return (constraintExpr_getFileloc (e) );
1234     }
1235   llassert (FALSE);
1236   //  llfatalbug("Code should be reached");
1237   return (fileloc_undefined);
1238 }
1239
1240
1241
1242 /* bool constraintExpr_includesTerm (constraintExpr expr, constraintTerm term) */
1243 /* { */
1244 /*   if (constraintTerm_hasTerm (expr->term, term) ) */
1245 /*     return TRUE; */
1246
1247 /*   if ( (expr->expr) != NULL) */
1248 /*     { */
1249 /*       return ( constraintExpr_includesTerm (expr->expr, term) ); */
1250 /*     } */
1251 /*   return FALSE; */
1252
1253 /* } */
1254
1255
1256
1257