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