src/constraintResolve.c

   1 /*
   2 /*
   3 ** constraintResolve.c
   4 */
   5
   6 # include <ctype.h> /* for isdigit */
   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 # include "exprData.i"
  16
  17
  18 int constraintExpr_getValue (constraintExpr expr)
  19 {
  20   if (expr->expr != NULL)
  21     {
  22       TPRINTF( ( "Not Implemented" ));
  23       llassert(FALSE);
  24     }
  25   return (constraintTerm_getValue (expr->term) );
  26 }
  27
  28 // returns 1 0 -1 like strcopy
  29 int constraintExpr_compare (constraintExpr expr1, constraintExpr expr2)
  30 {
  31   int value1, value2;
  32
  33   value1 = constraintExpr_getValue(expr1);
  34   value2 = constraintExpr_getValue(expr2);
  35
  36   if (value1 > value2)
  37     return 1;
  38
  39   if (value1 == value2)
  40     return 0;
  41
  42   else
  43     return -1;
  44 }
  45
  46 bool constraintExpr_canCompare (constraintExpr expr1, constraintExpr expr2)
  47 {
  48   if (expr1->expr != NULL)
  49     {
  50       return FALSE;
  51     }
  52
  53   if (expr2->expr  != NULL)
  54     {
  55       return FALSE;
  56     }
  57
  58   return TRUE;
  59 }
  60
  61 bool rangeCheck (arithType ar1, constraintExpr expr1, arithType ar2, constraintExpr expr2)
  62
  63 {
  64   switch (ar1)
  65  {
  66  case GTE:
  67  case GT:
  68       /*irst constraint is > only > => or == cosntraint can satify it */
  69       if ( (ar2 == GT) || (ar2 == GTE) || (ar2 == EQ) )
  70         {
  71           if (! constraintExpr_canCompare (expr1, expr2) )
  72             return FALSE;
  73
  74           if (constraintExpr_compare (expr2, expr1) >= 0)
  75             return TRUE;
  76
  77         }
  78   return FALSE;
  79  default:
  80    TPRINTF(("case not handled"));
  81  }
  82   return FALSE;
  83 }
  84
  85 /*returns true if cosntraint post satifies cosntriant pre */
  86 bool satifies (constraint pre, constraint post)
  87 {
  88   if (!constraintTerm_same(pre->lexpr->term, post->lexpr->term) )
  89     {
  90       return FALSE;
  91     }
  92   if (post->expr == NULL)
  93     return FALSE;
  94
  95   return rangeCheck (pre->ar, pre->expr, post->ar, post->expr);
  96 }
  97
  98 constraintExpr constraintExpr_simplify (constraintExpr expr)
  99 {
 100
 101   expr->term = constraintTerm_simplify (expr->term);
 102   if (expr->expr == NULL)
 103     {
 104       if ( (expr->term->kind == CONSTRAINTEXPR) &&  (expr->term->constrType == VALUE) )
 105         {
 106           expr->op =  expr->term->value.constrExpr->op;
 107           expr->expr = expr->term->value.constrExpr->expr;
 108           expr->term = expr->term->value.constrExpr->term;
 109         }
 110
 111       return expr;
 112     }
 113
 114     expr->expr = constraintExpr_simplify (expr->expr);
 115
 116
 117
 118   if ( (expr->term->kind == INTLITERAL) && (expr->expr->term->kind == INTLITERAL)  )
 119     {
 120       DPRINTF( ("INTLITERAL MERGE " ));
 121
 122       DPRINTF ( (message ("Expression is %s ", constraintExpr_print (expr) ) ) );
 123
 124       if (expr->op == PLUS )
 125         {
 126           DPRINTF( (message ("Adding %d and %d ", expr->term->value.intlit,
 127                              expr->expr->term->value.intlit) ) );
 128           expr->term->value.intlit += expr->expr->term->value.intlit;
 129         }
 130       else if (expr->op == MINUS )
 131         {
 132           expr->term->value.intlit -= expr->expr->term->value.intlit;
 133         }
 134       expr->op = expr->expr->op;
 135
 136       expr->expr = expr->expr->expr;
 137     }
 138
 139   return expr;
 140
 141 }
 142
 143 constraintExpr constraintExpr_add (constraintExpr e, constraintTerm term,  constraintExprOp op)
 144 {
 145   constraintExpr p;
 146
 147   p = e;
 148   while (p->expr != NULL)
 149     {
 150       p = p->expr;
 151     }
 152
 153   p->op = op;
 154   p->expr = constraintExpr_alloc();
 155   p->expr->term = term;
 156
 157   return e;
 158 }
 159
 160 constraintExpr termMove (constraintExpr dst, constraintExpr src)
 161 {
 162   constraintTerm term;
 163   llassert (src->expr != NULL);
 164   term = src->expr->term;
 165   if (src->op == PLUS)
 166     dst = constraintExpr_add (dst, term, MINUS);
 167   else
 168     if (src->op == MINUS)
 169       dst = constraintExpr_add (dst, term, PLUS);
 170
 171   return dst;
 172 }
 173
 174 constraint solveforterm (constraint c)
 175 {
 176   constraintExpr p;
 177     p = c->lexpr;
 178     while (p->expr != NULL)
 179       {
 180         DPRINTF( (message("Moving %s", constraintExpr_print (c->expr) ) ) );
 181         c->expr = termMove(c->expr, p);
 182         p->op = p->expr->op;
 183         #warning memleak
 184
 185         p->expr = p->expr->expr;
 186       }
 187     return c;
 188 }
 189
 190 constraint solveforOther (constraint c)
 191 {
 192   constraintExpr p;
 193     p = c->expr;
 194     while (p->expr != NULL)
 195       {
 196         TPRINTF( (message("Moving %s", constraintExpr_print (c->expr) ) ) );
 197         c->lexpr = termMove(c->lexpr, p);
 198         p->op = p->expr->op;
 199         #warning memleak
 200
 201         p->expr = p->expr->expr;
 202       }
 203     return c;
 204 }
 205
 206 constraint constraint_simplify (constraint c)
 207 {
 208   c =  solveforterm (c);
 209   c->lexpr = constraintExpr_simplify (c->lexpr);
 210   c->expr  = constraintExpr_simplify (c->expr);
 211   return c;
 212 }
 213
 214 bool resolve (constraint c, constraintList p)
 215 {
 216   constraintList_elements (p, el)
 217     {
 218       if ( satifies (c, el) )
 219         {
 220           DPRINTF ( (message ("\n%s Satifies %s\n ", constraint_print(el), constraint_print(c) ) ) );
 221           return TRUE;
 222         }
 223     }
 224   end_constraintList_elements;
 225   DPRINTF ( (message ("no constraints satify %s", constraint_print(c) ) ));
 226   return FALSE;
 227 }
 228
 229
 230 constraintTerm  constraintTerm_substituteTerm (constraintTerm term, constraintTerm oldterm, constraintExpr replacement)
 231 {
 232   if ( constraintTerm_similar (term, oldterm) )
 233     {
 234       // do the substitution
 235       term->kind = CONSTRAINTEXPR;
 236       term->value.constrExpr = constraintExpr_copy (replacement);
 237     }
 238   return term;
 239 }
 240
 241 constraintExpr constraintExpr_substituteTerm (constraintExpr expr, constraintTerm oldterm, constraintExpr replacement)
 242 {
 243    expr->term = constraintTerm_substituteTerm (expr->term, oldterm, replacement);
 244    if (expr->expr != NULL)
 245      expr->expr = constraintExpr_substituteTerm (expr->expr, oldterm, replacement);
 246
 247    return expr;
 248 }
 249
 250 /* returns true  if fileloc for term2 is closer to file for term1 than is term3*/
 251
 252 bool fileloc_closer (constraintTerm term1, constraintTerm term2, constraintTerm term3)
 253 {
 254    if ( fileloc_lessthan (term1->loc, term2->loc) )
 255      {
 256        if (fileloc_lessthan (term2->loc, term3->loc) )
 257          {
 258            llassert (fileloc_lessthan (term1->loc, term3->loc) );
 259            return TRUE;
 260          }
 261        else
 262          {
 263            return FALSE;
 264          }
 265      }
 266
 267    if ( ! (fileloc_lessthan (term1->loc, term2->loc) ) )
 268      {
 269        if (!fileloc_lessthan (term2->loc, term3->loc) )
 270          {
 271            llassert (fileloc_lessthan (term3->loc, term1->loc) );
 272            return TRUE;
 273          }
 274        else
 275          {
 276            return FALSE;
 277
 278          }
 279      }
 280
 281    llassert(FALSE);
 282    return FALSE;
 283 }
 284
 285 constraint constraint_substituteTerm (constraint c, constraint subs)
 286 {
 287   constraintTerm oldterm;
 288   constraintExpr replacement;
 289
 290     llassert(subs->lexpr->expr == NULL);
 291
 292
 293     oldterm = subs->lexpr->term;
 294     replacement = subs->expr;
 295
 296     // Chessy hack assumes that subs always has the form g:1 = g:2 + expr
 297
 298     /*@i2*/
 299
 300     /*find out which value to substitute*/
 301     TPRINTF((message ("doing substitute for %s and %s", constraint_print (c), constraint_print(subs) ) ) );
 302     if ( constraintExpr_containsTerm (subs->expr, subs->lexpr->term) )
 303       {
 304         TPRINTF(("doing new stuff"));
 305         if (fileloc_closer (c->lexpr->term, subs->expr->term, subs->lexpr->term) )
 306           {
 307             // use the other term
 308             constraint new;
 309             new = constraint_copy (subs);
 310             new = solveforOther(new);
 311             oldterm = new->expr->term;
 312             replacement = new->lexpr;
 313           }
 314       }
 315
 316     c->lexpr = constraintExpr_substituteTerm (c->lexpr, oldterm, replacement);
 317     c->expr   = constraintExpr_substituteTerm (c->expr, oldterm, replacement);
 318     return c;
 319 }
 320
 321 constraint substitute (constraint c, constraintList p)
 322 {
 323   constraintList_elements (p, el)
 324     {
 325       if ( el->ar == EQ)
 326         if (constraint_hasTerm (c, el->lexpr->term) )
 327           {
 328               llassert(el->lexpr->expr == NULL);
 329               DPRINTF((message ("doing substitute for %s", constraint_print (c) ) ) );
 330
 331               c = constraint_substituteTerm (c, el);
 332               DPRINTF((message ("substituted constraint is now %s", constraint_print (c) ) ) );
 333               // c->lexpr = constraintExpr_copy (el->expr);
 334               c = constraint_simplify(c);
 335               c = constraint_simplify(c);
 336               c = constraint_simplify(c);
 337               return c;
 338           }
 339     }
 340   end_constraintList_elements;
 341
 342   c = constraint_simplify(c);
 343   return c;
 344 }
 345
 346
 347 constraintList reflectChanges (constraintList pre2, constraintList post1)
 348 {
 349
 350   constraintList ret;
 351   constraint temp;
 352   ret = constraintList_new();
 353   constraintList_elements (pre2, el)
 354     {
 355       if (!resolve (el, post1) )
 356         {
 357           temp = substitute (el, post1);
 358           ret = constraintList_add (ret, temp);
 359         }
 360     } end_constraintList_elements;
 361
 362     return ret;
 363 }
 364
 365 bool constraintExpr_containsTerm (constraintExpr p, constraintTerm term)
 366 {
 367   TPRINTF(("constraintExpr_containsTerm"));
 368
 369   while (p != NULL)
 370     {
 371       if (constraintTerm_similar (p->term, term) )
 372         return TRUE;
 373
 374       p = p->expr->expr;
 375     }
 376   DPRINTF((
 377            message ("constraintExpr_hasTerm returned fallse for %s %S",
 378                     constraint_print(c), constraintTerm_print(term)
 379                     )
 380            ));
 381   return FALSE;
 382 }
 383
 384
 385 /*check if rvalue side has term*/
 386 bool constraintExpr_hasTerm (constraint c, constraintTerm term)
 387 {
 388   constraintExpr p;
 389   p = c->expr;
 390   while (p != NULL)
 391     {
 392       if (constraintTerm_same (p->term, term) )
 393         return TRUE;
 394
 395       p = p->expr->expr;
 396     }
 397   DPRINTF((
 398            message ("constraintExpr_hasTerm returned fallse for %s %S",
 399                     constraint_print(c), constraintTerm_print(term)
 400                     )
 401            ));
 402   return FALSE;
 403 }
 404
 405 constraintExpr solveEq (constraint c, constraintTerm t)
 406 {
 407   constraintExpr p;
 408   c = constraint_copy (c);
 409   DPRINTF(("\ndoing solveEq\n"));
 410   if (! constraintTerm_same (c->expr->term, t) )
 411     {
 412       DPRINTF ( (message ("\n\nconstraintTerms: %s %s not same ", constraintTerm_print(c->expr->term),
 413                           constraintTerm_print(t) )
 414                  ) );
 415       return NULL;
 416     }
 417
 418   p = c->expr;
 419   while (p->expr != NULL)
 420     {
 421       DPRINTF( (message("\n\nMoving %s", constraintExpr_print (c->expr) ) ) );
 422       c->lexpr = termMove(c->lexpr, p);
 423       p->expr = p->expr->expr;
 424     }
 425
 426   return c->lexpr;
 427
 428 }
 429
 430 constraint updateConstraint (constraint c, constraintList p)
 431 {
 432   TPRINTF(("start updateConstraints"));
 433   constraintList_elements (p, el)
 434     {
 435
 436       if (constraintTerm_same(c->lexpr->term, el->lexpr->term) )
 437         {
 438           TPRINTF((""));
 439           if ( el->ar == EQ)
 440             {
 441                   TPRINTF(("j"));
 442
 443               if  (constraintExpr_hasTerm (el, c->lexpr->term) )
 444                 {
 445                   constraintExpr solve;
 446                   TPRINTF((""));
 447                   solve = solveEq (el, c->lexpr->term);
 448                   if (solve)
 449                     {
 450                       c->lexpr = constraintExpr_copy (solve);
 451                       c = constraint_simplify(c);
 452                       return c;
 453                     }
 454                 }
 455             }
 456         }
 457     }
 458   end_constraintList_elements;
 459   c = constraint_simplify(c);
 460
 461   DPRINTF(("end updateConstraints"));
 462   return c;
 463 }
 464
 465
 466 constraintList reflectChangesEnsures (constraintList pre2, constraintList post1)
 467 {
 468   constraintList ret;
 469   constraint temp;
 470   ret = constraintList_new();
 471   constraintList_elements (pre2, el)
 472     {
 473       if (!resolve (el, post1) )
 474         {
 475           temp = substitute (el, post1);
 476           if (temp != NULL)
 477             ret = constraintList_add (ret, temp);
 478         }
 479     } end_constraintList_elements;
 480
 481     return ret;
 482 }
 483
 484 void mergeResolve (exprNode parent, exprNode child1, exprNode child2)
 485 {
 486   constraintList temp;
 487   DPRINTF( (message ("magically merging constraint into parent:%s for children:  %s and %s", exprNode_unparse (parent), exprNode_unparse (child1), exprNode_unparse(child2) )
 488             ) );
 489    if (exprNode_isError (child1)  || exprNode_isError(child2) )
 490      {
 491        if (exprNode_isError (child1) && !exprNode_isError(child2) )
 492          {
 493            parent->requiresConstraints = constraintList_copy (child2->requiresConstraints);
 494            parent->ensuresConstraints = constraintList_copy (child2->ensuresConstraints);
 495            DPRINTF((message ("Copied child constraints: pre: %s and post: %s",
 496                              constraintList_print( child2->requiresConstraints),
 497                              constraintList_print (child2->ensuresConstraints)
 498                              )
 499                     ));
 500            return;
 501          }
 502        else
 503          {
 504            llassert(exprNode_isError(child2) );
 505            parent->requiresConstraints = constraintList_new();
 506            parent->ensuresConstraints = constraintList_new();
 507            return;
 508          }
 509      }
 510
 511    llassert(!exprNode_isError (child1)  && ! exprNode_isError(child2) );
 512
 513   DPRINTF( (message ("Child constraints are %s %s and %s %s",
 514                      constraintList_print (child1->requiresConstraints),
 515                      constraintList_print (child1->ensuresConstraints),
 516                      constraintList_print (child2->requiresConstraints),
 517                      constraintList_print (child2->ensuresConstraints)
 518                      ) ) );
 519
 520   parent->requiresConstraints = constraintList_new();
 521   parent->ensuresConstraints = constraintList_new();
 522
 523   parent->requiresConstraints = constraintList_copy (child1->requiresConstraints);
 524
 525   temp = reflectChanges (child2->requiresConstraints, child1->ensuresConstraints);
 526   parent->requiresConstraints = constraintList_addList (parent->requiresConstraints, temp);
 527
 528
 529   temp = reflectChangesEnsures (child1->ensuresConstraints, child2->ensuresConstraints);
 530   // temp = constraintList_copy (child1->ensuresConstraints);
 531
 532
 533   parent->ensuresConstraints = constraintList_copy (child2->ensuresConstraints);
 534   parent->ensuresConstraints = constraintList_addList (parent->ensuresConstraints, temp);
 535
 536   DPRINTF( (message ("Parent constraints are %s and %s ",
 537                      constraintList_print (parent->requiresConstraints),
 538                      constraintList_print (parent->ensuresConstraints)
 539                      ) ) );
 540
 541 }
 542
 543