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