src/forjunk.c

   1 /*
   2 ** forjunk.c
   3 */
   4
   5 //#define DEBUGPRINT 1
   6
   7 # include <ctype.h> /* for isdigit */
   8 # include "lclintMacros.nf"
   9 # include "basic.h"
  10 # include "cgrammar.h"
  11 # include "cgrammar_tokens.h"
  12
  13 # include "exprChecks.h"
  14 # include "aliasChecks.h"
  15 # include "exprNodeSList.h"
  16
  17 # include "exprDataQuite.i"
  18
  19 /*@access constraint, exprNode @*/
  20
  21 /*@access constraintExpr @*/
  22
  23 static bool isInc (/*@observer@*/ constraintExpr c) /*@*/
  24 {
  25
  26   llassert(constraintExpr_isDefined(c) );
  27  if (c->kind == binaryexpr )
  28     {
  29       constraintExprBinaryOpKind binOP;
  30       constraintExpr t1, t2;
  31       t1 = constraintExprData_binaryExprGetExpr1 (c->data);
  32       t2 = constraintExprData_binaryExprGetExpr2 (c->data);
  33
  34       binOP = constraintExprData_binaryExprGetOp (c->data);
  35       if (binOP == PLUS)
  36         if (constraintExpr_isLit (t2) && constraintExpr_getValue (t2) == 1 )
  37           {
  38             return TRUE;
  39           }
  40     }
  41
  42  return FALSE;
  43 }
  44
  45
  46
  47 // look for constraints like cexrp = cexrp + 1
  48 static bool incVar (/*@notnull@*/ constraint c) /*@*/
  49 {
  50   constraintExpr t1;
  51   if (c->ar != EQ)
  52     {
  53       return FALSE;
  54     }
  55   if (! isInc (c->expr ) )
  56     return FALSE;
  57
  58   llassert (constraintExpr_isDefined(c->expr) );
  59   llassert (c->expr->kind == binaryexpr);
  60
  61   t1 = constraintExprData_binaryExprGetExpr1 (c->expr->data);
  62   if (constraintExpr_similar (c->lexpr, t1) )
  63     return TRUE;
  64
  65   return FALSE;
  66 }
  67 /*@noaccess constraintExpr @*/
  68
  69
  70 static bool increments (/*@observer@*/ constraint c,
  71                         /*@observer@*/ constraintExpr var)
  72 {
  73   llassert(constraint_isDefined(c) );
  74
  75   if (constraint_isUndefined(c) )
  76     {
  77       return FALSE;
  78     }
  79
  80   llassert (incVar (c));
  81   if (constraintExpr_similar (c->lexpr, var) )
  82     return TRUE;
  83   else
  84     return FALSE;
  85 }
  86
  87 static bool canGetForTimes (/*@notnull@*/ exprNode forPred, /*@notnull@*/ exprNode forBody)
  88 {
  89
  90   exprNode init, test, inc, t1, t2;
  91   lltok tok;
  92
  93   llassert(exprNode_isDefined (forPred) );
  94   llassert(exprNode_isDefined (forBody) );
  95
  96   init  =  exprData_getTripleInit (forPred->edata);
  97   test  =   exprData_getTripleTest (forPred->edata);
  98   inc   =   exprData_getTripleInc (forPred->edata);
  99
 100   llassert(exprNode_isDefined(test) );
 101
 102   if (exprNode_isUndefined(test) )
 103     {
 104       return FALSE;
 105     }
 106
 107   llassert(exprNode_isDefined(inc) );
 108
 109   if (exprNode_isUndefined(inc) )
 110     {
 111       return FALSE;
 112     }
 113
 114   if (test->kind != XPR_PREOP)
 115     return FALSE;
 116
 117   tok = (exprData_getUopTok (test->edata));
 118   if (!lltok_isMult (tok) )
 119     {
 120       return FALSE;
 121     }
 122
 123   //should check preop too
 124   if (inc->kind != XPR_POSTOP)
 125     {
 126       return FALSE;
 127     }
 128
 129   tok = (exprData_getUopTok (inc->edata));
 130   if (lltok_isInc_Op (tok) )
 131       {
 132         t1 = exprData_getUopNode (test->edata);
 133         t2 = exprData_getUopNode (inc->edata);
 134         llassert(exprNode_isDefined(t2) && exprNode_isDefined(t2)  );
 135
 136         if (exprNode_isUndefined(t1) || exprNode_isUndefined(t2)  )
 137           {
 138             return FALSE;
 139           }
 140
 141         if (sRef_sameName (t1->sref, t2->sref) )
 142           {
 143             return TRUE;
 144           }
 145       }
 146   return FALSE;
 147 }
 148
 149 static /*@only@*/ constraintList getLessThanConstraints (/*@observer@*/ constraintList c)
 150 {
 151   constraintList ret;
 152
 153   ret = constraintList_makeNew();
 154   constraintList_elements (c, el)
 155     {
 156       llassert(constraint_isDefined(el));
 157       if ( constraint_isUndefined(el)  )
 158         continue;
 159
 160       if (el->ar == LT || el->ar == LTE)
 161         {
 162           constraint temp;
 163           temp = constraint_copy(el);
 164
 165           ret = constraintList_add (ret, temp);
 166         }
 167     }
 168   end_constraintList_elements;
 169
 170   return ret;
 171 }
 172
 173 static /*@only@*/ constraintList getIncConstraints (/*@observer@*/ constraintList c)
 174 {
 175   constraintList ret;
 176
 177   ret = constraintList_makeNew();
 178   constraintList_elements (c, el)
 179     {
 180       if (incVar (el) )
 181         {
 182           constraint temp;
 183           temp = constraint_copy(el);
 184           ret = constraintList_add (ret, temp);
 185         }
 186     }
 187   end_constraintList_elements;
 188
 189   return ret;
 190 }
 191
 192 static /*@only@*/ constraintExpr getForTimes (/*@notnull@*/ exprNode forPred, /*@notnull@*/ exprNode forBody)
 193 {
 194
 195   exprNode init, test, inc, t1, t2;
 196   constraintList ltCon;
 197   constraintList incCon;
 198   constraintExpr ret;
 199
 200   lltok tok;
 201
 202   init  =  exprData_getTripleInit (forPred->edata);
 203   test  =  exprData_getTripleTest (forPred->edata);
 204   inc   =  exprData_getTripleInc (forPred->edata);
 205
 206   llassert(exprNode_isDefined(test) );
 207   llassert(exprNode_isDefined(inc) );
 208
 209   ltCon =  getLessThanConstraints (test->trueEnsuresConstraints);
 210   incCon = getIncConstraints (inc->ensuresConstraints);
 211
 212   DPRINTF(( message ("getForTimes: ltCon: %s from %s", constraintList_print(ltCon), constraintList_print(test->trueEnsuresConstraints) ) ));
 213
 214   DPRINTF(( message ("getForTimes: incCon: %s from %s", constraintList_print(incCon), constraintList_print(inc->ensuresConstraints) ) ));
 215
 216   constraintList_elements (ltCon, el)
 217     {
 218       constraintList_elements(incCon, el2)
 219       {
 220         if ( increments(el2, el->lexpr) )
 221           {
 222             DPRINTF(( message ("getForTimes: %s increments %s", constraint_print(el2), constraint_print(el) ) ));
 223             ret =  constraintExpr_copy (el->expr);
 224             constraintList_free(ltCon);
 225             constraintList_free(incCon);
 226             return ret;
 227
 228           }
 229         else
 230           DPRINTF(( message ("getForTimes: %s doesn't increment %s", constraint_print(el2), constraint_print(el) )   ));
 231       }
 232       end_constraintList_elements;
 233     }
 234
 235   end_constraintList_elements;
 236
 237   constraintList_free(ltCon);
 238   constraintList_free(incCon);
 239
 240   DPRINTF (( message ("getForTimes: %s  %s resorting to ugly hack", exprNode_unparse(forPred), exprNode_unparse(forBody) ) ));
 241   if (! canGetForTimes (forPred, forBody) )
 242     {
 243       return NULL;
 244     }
 245
 246
 247   if (test->kind != XPR_PREOP)
 248     llassert (FALSE);
 249
 250   tok = (exprData_getUopTok (test->edata));
 251   if (!lltok_isMult (tok) )
 252     {
 253       llassert ( FALSE );
 254     }
 255
 256   //should check preop too
 257   if (inc->kind != XPR_POSTOP)
 258     {
 259       llassert (FALSE );
 260     }
 261
 262   tok = (exprData_getUopTok (inc->edata));
 263   if (lltok_isInc_Op (tok) )
 264       {
 265         t1 = exprData_getUopNode (test->edata);
 266         t2 = exprData_getUopNode (inc->edata);
 267         if (sRef_sameName (t1->sref, t2->sref) )
 268           {
 269             return (constraintExpr_makeMaxSetExpr (t1) );
 270           }
 271       }
 272   llassert( FALSE);
 273   BADEXIT;
 274 }
 275
 276 /*@access constraintExpr @*/
 277
 278 static /*@only@*/ constraintExpr constraintExpr_searchAndAdd (/*@only@*/ constraintExpr c, /*@observer@*/ constraintExpr find, /*@observer@*/ constraintExpr add)
 279 {
 280   constraintExprKind kind;
 281   constraintExpr temp;
 282
 283   DPRINTF(( message ("Doing constraintExpr_searchAndAdd  %s %s %s ",
 284                      constraintExpr_unparse(c), constraintExpr_unparse(find), constraintExpr_unparse(add) ) ) );
 285
 286   if ( constraintExpr_similar (c, find) )
 287     {
 288       #warning mem leak
 289
 290       constraintExpr new;
 291
 292       cstring cPrint;
 293
 294       cPrint = constraintExpr_unparse(c);
 295
 296
 297       new = constraintExpr_makeAddExpr (c, constraintExpr_copy(add) );
 298
 299       DPRINTF((message ("Replacing %q with %q",
 300                         cPrint, constraintExpr_unparse(new)
 301                         )));
 302       return new;
 303     }
 304
 305   kind = c->kind;
 306
 307   switch (kind)
 308     {
 309     case term:
 310       break;
 311     case unaryExpr:
 312       temp = constraintExprData_unaryExprGetExpr (c->data);
 313       temp = constraintExpr_searchAndAdd (constraintExpr_copy(temp), find, add);
 314       c->data = constraintExprData_unaryExprSetExpr (c->data, temp);
 315       break;
 316     case binaryexpr:
 317
 318       temp = constraintExprData_binaryExprGetExpr1 (c->data);
 319       temp = constraintExpr_searchAndAdd (constraintExpr_copy(temp), find, add);
 320       c->data = constraintExprData_binaryExprSetExpr1 (c->data, temp);
 321
 322       temp = constraintExprData_binaryExprGetExpr2 (c->data);
 323       temp = constraintExpr_searchAndAdd (constraintExpr_copy(temp), find, add);
 324       c->data = constraintExprData_binaryExprSetExpr2 (c->data, temp);
 325       break;
 326     default:
 327       llassert(FALSE);
 328     }
 329   return c;
 330
 331 }
 332
 333 /*@noaccess constraintExpr @*/
 334
 335 static constraint  constraint_searchAndAdd (/*@returned@*/ constraint c, /*@observer@*/ constraintExpr find, /*@observer@*/ constraintExpr add)
 336 {
 337
 338   llassert (constraint_search (c, find)  );
 339   DPRINTF(( message ("Doing constraint_searchAndAdd  %s %s %s ",
 340                      constraint_print(c), constraintExpr_unparse(find), constraintExpr_unparse(add) ) ) );
 341
 342   c->lexpr = constraintExpr_searchAndAdd (c->lexpr, find, add);
 343   c->expr =  constraintExpr_searchAndAdd (c->expr, find, add);
 344
 345    c = constraint_simplify (c);
 346    c = constraint_simplify (c);
 347
 348   return c;
 349
 350 }
 351
 352 /*@only@*/ static constraintList constraintList_searchAndAdd (/*@returned@*/ constraintList list,
 353                                                    /*@observer@*/ constraintExpr find, /*@observer@*/ constraintExpr add)
 354 {
 355   constraintList newConstraints;
 356   constraintList ret;
 357
 358   newConstraints = constraintList_makeNew();
 359
 360   constraintList_elements (list, el)
 361     {
 362       if (constraint_search (el, find) )
 363         {
 364           constraint new;
 365           new = constraint_copy (el);
 366
 367           new = constraint_searchAndAdd (new, find, add);
 368                   DPRINTF (( (message ("Adding constraint %s ", constraint_print (new)) )  ));
 369           newConstraints = constraintList_add (newConstraints, new);
 370         }
 371
 372     }
 373   end_constraintList_elements;
 374
 375   ret =  constraintList_addListFree (list, newConstraints);
 376   return ret;
 377 }
 378
 379 static void doAdjust(/*@unused@*/ exprNode e, /*@unused@*/ exprNode forPred, /*@observer@*/ exprNode forBody, /*@observer@*/ constraintExpr iterations)
 380 {
 381
 382   constraintList_elements (forBody->ensuresConstraints, el)
 383     {
 384       // look for var = var + 1
 385       if (incVar(el) )
 386         {
 387           DPRINTF((message ("Found inc variable constraint : %s", constraint_print (el) )  ));
 388           forBody->requiresConstraints = constraintList_searchAndAdd(forBody->requiresConstraints, el->lexpr, iterations);
 389         }
 390     }
 391   end_constraintList_elements;
 392 }
 393
 394 void forLoopHeuristics( exprNode e, exprNode forPred, exprNode forBody)
 395 {
 396   exprNode init, test, inc;
 397
 398   constraintExpr iterations;
 399
 400   init  =  exprData_getTripleInit (forPred->edata);
 401   test =   exprData_getTripleTest (forPred->edata);
 402   inc  =   exprData_getTripleInc (forPred->edata);
 403
 404   if (exprNode_isError (test) || exprNode_isError (inc) )
 405     return;
 406
 407   iterations = getForTimes (forPred, forBody );
 408
 409   if (iterations != NULL)
 410     {
 411       doAdjust ( e, forPred, forBody, iterations);
 412       constraintExpr_free(iterations);
 413     }
 414 }
 415
 416
 417 /*    else */
 418 /*      { */
 419 /*        DPRINTF (("Can't get for time ")); */
 420 /*      } */
 421
 422 /*    if (exprNode_isError(init) ) */
 423 /*      { */
 424 /*        return; */
 425 /*      } */
 426
 427 /*    if (init->kind == XPR_ASSIGN) */
 428 /*      { */
 429 /*        t1 = exprData_getOpA (init->edata); */
 430 /*        t2 = exprData_getOpB (init->edata); */
 431
 432 /*        if (! (t1->kind == XPR_VAR) ) */
 433 /*      return; */
 434 /*      } */
 435 /*    else */
 436 /*      return; */
 437
 438 /*    if (test->kind == XPR_FETCH) */
 439 /*      { */
 440 /*        t3 = exprData_getPairA (test->edata); */
 441 /*        t4 = exprData_getPairB (test->edata); */
 442
 443 /*        if (sRef_sameName(t1->sref, t4->sref) ) */
 444 /*      { */
 445 /*        DPRINTF((message ("Found a for loop matching heuristic:%s", exprNode_unparse (forPred) ) )); */
 446 /*        con = constraint_makeEnsureLteMaxRead(t1, t3); */
 447 /*        forPred->ensuresConstraints = constraintList_add(forPred->ensuresConstraints, con);      */
 448 /*      } */
 449 /*        else */
 450 /*      { */
 451 /*        DPRINTF((message ("Didn't Find a for loop matching heuristic:%s %s and %s differ", exprNode_unparse (forPred), exprNode_unparse(t1), exprNode_unparse(t3) ) )); */
 452 /*      } */
 453 /*        return; */
 454 /*      } */