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->expr == NULL)
  93     return FALSE;
  94   return rangeCheck (pre->ar, pre->expr, post->ar, post->expr);
  95
  96   return TRUE;
  97 }
  98
  99 constraintExpr constraintExpr_simplify (constraintExpr expr)
 100 {
 101
 102   expr->term = constraintTerm_simplify (expr->term);
 103   if (expr->expr == NULL)
 104     return expr;
 105
 106     expr->expr = constraintExpr_simplify (expr->expr);
 107   if ( (expr->term->constrType == INTLITERAL) && (expr->expr->term->constrType == INTLITERAL)  )
 108     {
 109       TPRINTF( ("EVENTUAL IMPLEMENTATION OF LITERAL MERGE " ));
 110
 111       TPRINTF ( (message ("Expression is %s ", constraintExpr_print (expr) ) ) );
 112
 113       if (expr->op == PLUS )
 114         {
 115           TPRINTF( (message ("Adding %d and %d ", expr->term->value.intlit,
 116                              expr->expr->term->value.intlit) ) );
 117           expr->term->value.intlit += expr->expr->term->value.intlit;
 118         }
 119       else if (expr->op == MINUS )
 120         {
 121           expr->term->value.intlit -= expr->expr->term->value.intlit;
 122         }
 123       expr->op = expr->expr->op;
 124
 125       expr->expr = expr->expr->expr;
 126     }
 127   return expr;
 128
 129 }
 130
 131 constraintExpr constraintExpr_add (constraintExpr e, constraintTerm term,  constraintExprOp op)
 132 {
 133   constraintExpr p;
 134
 135   p = e;
 136   while (p->expr != NULL)
 137     {
 138       p = p->expr;
 139     }
 140
 141   p->op = op;
 142   p->expr = constraintExpr_alloc();
 143   p->expr->term = term;
 144
 145   return e;
 146 }
 147
 148 constraintExpr termMove (constraintExpr dst, constraintExpr src)
 149 {
 150   constraintTerm term;
 151   llassert (src->expr != NULL);
 152   term = src->expr->term;
 153   if (src->op == PLUS)
 154     dst = constraintExpr_add (dst, term, MINUS);
 155   else
 156     if (src->op == MINUS)
 157       dst = constraintExpr_add (dst, term, PLUS);
 158
 159   return dst;
 160 }
 161
 162 constraint solveforterm (constraint c)
 163 {
 164   constraintExpr p;
 165     p = c->lexpr;
 166     while (p->expr != NULL)
 167       {
 168         TPRINTF( (message("Moving %s", constraintExpr_print (c->expr) ) ) );
 169         c->expr = termMove(c->expr, p);
 170         p->op = p->expr->op;
 171         #warning memleak
 172
 173         p->expr = p->expr->expr;
 174       }
 175     return c;
 176 }
 177
 178 constraint constraint_simplify (constraint c)
 179 {
 180   c =  solveforterm (c);
 181   c->lexpr = constraintExpr_simplify (c->lexpr);
 182   c->expr  = constraintExpr_simplify (c->expr);
 183   return c;
 184 }
 185
 186 bool resolve (constraint c, constraintList p)
 187 {
 188   constraintList_elements (p, el)
 189     {
 190       if ( satifies (c, el) )
 191         {
 192           TPRINTF ( (message ("\n%s Satifies %s\n ", constraint_print(el), constraint_print(c) ) ) );
 193           return TRUE;
 194         }
 195     }
 196   end_constraintList_elements;
 197   TPRINTF ( (message ("no constraints satify %s", constraint_print(c) ) ));
 198   return FALSE;
 199 }
 200
 201 constraint substitute (constraint c, constraintList p)
 202 {
 203   constraintList_elements (p, el)
 204     {
 205       if (constraintTerm_same(c->lexpr->term, el->lexpr->term) )
 206         {
 207           if ( el->ar == EQ)
 208             {
 209               c->lexpr = constraintExpr_copy (el->expr);
 210               c = constraint_simplify(c);
 211               return c;
 212             }
 213         }
 214     }
 215   end_constraintList_elements;
 216
 217   c = constraint_simplify(c);
 218   return c;
 219 }
 220
 221
 222 constraintList reflectChanges (constraintList pre2, constraintList post1)
 223 {
 224
 225   constraintList ret;
 226   constraint temp;
 227   ret = constraintList_new();
 228   constraintList_elements (pre2, el)
 229     {
 230       if (!resolve (el, post1) )
 231         {
 232           temp = substitute (el, post1);
 233           ret = constraintList_add (ret, temp);
 234         }
 235     } end_constraintList_elements;
 236
 237     return ret;
 238 }
 239
 240
 241 /*check if rvalue side has term*/
 242 bool constraintExpr_hasTerm (constraint c, constraintTerm term)
 243 {
 244   constraintExpr p;
 245   p = c->expr;
 246   while (p != NULL)
 247     {
 248       if (constraintTerm_same (p->term, term) )
 249         return TRUE;
 250
 251       p = p->expr->expr;
 252     }
 253   TPRINTF((
 254            message ("constraintExpr_hasTerm returned fallse for %s %S",
 255                     constraint_print(c), constraintTerm_print(term)
 256                     )
 257            ));
 258   return FALSE;
 259 }
 260
 261 constraintExpr solveEq (constraint c, constraintTerm t)
 262 {
 263   constraintExpr p;
 264   c = constraint_copy (c);
 265   TPRINTF(("\ndoing solveEq\n"));
 266   if (! constraintTerm_same (c->expr->term, t) )
 267     {
 268       TPRINTF ( (message ("\n\nconstraintTerms: %s %s not same ", constraintTerm_print(c->expr->term),
 269                           constraintTerm_print(t) )
 270                  ) );
 271       return NULL;
 272     }
 273
 274   p = c->expr;
 275   while (p->expr != NULL)
 276     {
 277       TPRINTF( (message("\n\nMoving %s", constraintExpr_print (c->expr) ) ) );
 278       c->lexpr = termMove(c->lexpr, p);
 279       p->expr = p->expr->expr;
 280     }
 281
 282   return c->lexpr;
 283
 284 }
 285
 286 constraint updateConstraint (constraint c, constraintList p)
 287 {
 288   TPRINTF(("start updateConstraints"));
 289   constraintList_elements (p, el)
 290     {
 291
 292       if (constraintTerm_same(c->lexpr->term, el->lexpr->term) )
 293         {
 294           TPRINTF((""));
 295           if ( el->ar == EQ)
 296             {
 297                   TPRINTF((""));
 298
 299               if  (constraintExpr_hasTerm (el, c->lexpr->term) )
 300                 {
 301                   constraintExpr solve;
 302                   TPRINTF((""));
 303                   solve = solveEq (el, c->lexpr->term);
 304                   if (solve)
 305                     {
 306                       c->lexpr = constraintExpr_copy (solve);
 307                       c = constraint_simplify(c);
 308                       return c;
 309                     }
 310                 }
 311             }
 312         }
 313     }
 314   end_constraintList_elements;
 315   c = constraint_simplify(c);
 316
 317   TPRINTF(("end updateConstraints"));
 318   return c;
 319 }
 320
 321
 322 constraintList reflectChangesEnsures (constraintList pre2, constraintList post1)
 323 {
 324   constraintList ret;
 325   constraint temp;
 326   ret = constraintList_new();
 327   constraintList_elements (pre2, el)
 328     {
 329       if (!resolve (el, post1) )
 330         {
 331           temp = updateConstraint (el, post1);
 332           if (temp != NULL)
 333             ret = constraintList_add (ret, temp);
 334         }
 335     } end_constraintList_elements;
 336
 337     return ret;
 338 }
 339
 340 void mergeResolve (exprNode parent, exprNode child1, exprNode child2)
 341 {
 342   constraintList temp;
 343   TPRINTF( (message ("magically merging constraint into parent:%s for children:  %s and %s", exprNode_unparse (parent), exprNode_unparse (child1), exprNode_unparse(child2) )
 344             ) );
 345   llassert (!exprNode_isError (child1)  || !exprNode_isError(child2) );
 346   if (exprNode_isError (child1) )
 347       {
 348         parent->requiresConstraints = constraintList_copy (child2->requiresConstraints);
 349         parent->ensuresConstraints = constraintList_copy (child2->ensuresConstraints);
 350         DPRINTF((message ("Copied child constraints: pre: %s and post: %s ",
 351                           constraintList_print( child2->requiresConstraints),
 352                           constraintList_print (child2->ensuresConstraints)
 353                           )
 354                  ));
 355         return;
 356       }
 357
 358   llassert(!exprNode_isError(child2) );
 359
 360   TPRINTF( (message ("Child constraints are %s and %s ",
 361                      constraintList_print (child1->requiresConstraints),
 362                      constraintList_print (child2->requiresConstraints)
 363                      ) ) );
 364
 365   parent->requiresConstraints = constraintList_new();
 366   parent->ensuresConstraints = constraintList_new();
 367
 368   parent->requiresConstraints = constraintList_copy (child1->requiresConstraints);
 369
 370   temp = reflectChanges (child2->requiresConstraints, child1->ensuresConstraints);
 371   parent->requiresConstraints = constraintList_addList (parent->requiresConstraints, temp);
 372
 373
 374   temp = reflectChangesEnsures (child1->ensuresConstraints, child2->ensuresConstraints);
 375   // temp = constraintList_copy (child1->ensuresConstraints);
 376
 377
 378   parent->ensuresConstraints = constraintList_copy (child2->ensuresConstraints);
 379   parent->ensuresConstraints = constraintList_addList (parent->ensuresConstraints, temp);
 380
 381   TPRINTF( (message ("Parent constraints are %s and %s ",
 382                      constraintList_print (parent->requiresConstraints),
 383                      constraintList_print (parent->ensuresConstraints)
 384                      ) ) );
 385
 386 }
 387