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
 289       constraintExpr new;
 290
 291       cstring cPrint;
 292
 293       cPrint = constraintExpr_unparse(c);
 294
 295
 296       new = constraintExpr_makeAddExpr (c, constraintExpr_copy(add) );
 297
 298       DPRINTF((message ("Replacing %q with %q",
 299                         cPrint, constraintExpr_unparse(new)
 300                         )));
 301       return new;
 302     }
 303
 304   kind = c->kind;
 305
 306   switch (kind)
 307     {
 308     case term:
 309       break;
 310     case unaryExpr:
 311       temp = constraintExprData_unaryExprGetExpr (c->data);
 312       temp = constraintExpr_searchAndAdd (constraintExpr_copy(temp), find, add);
 313       c->data = constraintExprData_unaryExprSetExpr (c->data, temp);
 314       break;
 315     case binaryexpr:
 316
 317       temp = constraintExprData_binaryExprGetExpr1 (c->data);
 318       temp = constraintExpr_searchAndAdd (constraintExpr_copy(temp), find, add);
 319       c->data = constraintExprData_binaryExprSetExpr1 (c->data, temp);
 320
 321       temp = constraintExprData_binaryExprGetExpr2 (c->data);
 322       temp = constraintExpr_searchAndAdd (constraintExpr_copy(temp), find, add);
 323       c->data = constraintExprData_binaryExprSetExpr2 (c->data, temp);
 324       break;
 325     default:
 326       llassert(FALSE);
 327     }
 328   return c;
 329
 330 }
 331
 332 /*@noaccess constraintExpr @*/
 333
 334 static constraint  constraint_searchAndAdd (/*@returned@*/ constraint c, /*@observer@*/ constraintExpr find, /*@observer@*/ constraintExpr add)
 335 {
 336
 337   llassert (constraint_search (c, find)  );
 338   DPRINTF(( message ("Doing constraint_searchAndAdd  %s %s %s ",
 339                      constraint_print(c), constraintExpr_unparse(find), constraintExpr_unparse(add) ) ) );
 340
 341   c->lexpr = constraintExpr_searchAndAdd (c->lexpr, find, add);
 342   c->expr =  constraintExpr_searchAndAdd (c->expr, find, add);
 343
 344    c = constraint_simplify (c);
 345    c = constraint_simplify (c);
 346
 347   return c;
 348
 349 }
 350
 351 /*@only@*/ static constraintList constraintList_searchAndAdd (/*@returned@*/ constraintList list,
 352                                                    /*@observer@*/ constraintExpr find, /*@observer@*/ constraintExpr add)
 353 {
 354   constraintList newConstraints;
 355   constraintList ret;
 356
 357   newConstraints = constraintList_makeNew();
 358
 359   constraintList_elements (list, el)
 360     {
 361       if (constraint_search (el, find) )
 362         {
 363           constraint new;
 364           new = constraint_copy (el);
 365
 366           new = constraint_searchAndAdd (new, find, add);
 367                   DPRINTF (( (message ("Adding constraint %s ", constraint_print (new)) )  ));
 368           newConstraints = constraintList_add (newConstraints, new);
 369         }
 370
 371     }
 372   end_constraintList_elements;
 373
 374   ret =  constraintList_addListFree (list, newConstraints);
 375   return ret;
 376 }
 377
 378 static void doAdjust(/*@unused@*/ exprNode e, /*@unused@*/ exprNode forPred, /*@observer@*/ exprNode forBody, /*@observer@*/ constraintExpr iterations)
 379 {
 380
 381   constraintList_elements (forBody->ensuresConstraints, el)
 382     {
 383       // look for var = var + 1
 384       if (incVar(el) )
 385         {
 386           DPRINTF((message ("Found inc variable constraint : %s", constraint_print (el) )  ));
 387           forBody->requiresConstraints = constraintList_searchAndAdd(forBody->requiresConstraints, el->lexpr, iterations);
 388         }
 389     }
 390   end_constraintList_elements;
 391 }
 392
 393 void forLoopHeuristics( exprNode e, exprNode forPred, exprNode forBody)
 394 {
 395   exprNode init, test, inc;
 396
 397   constraintExpr iterations;
 398
 399   init  =  exprData_getTripleInit (forPred->edata);
 400   test =   exprData_getTripleTest (forPred->edata);
 401   inc  =   exprData_getTripleInc (forPred->edata);
 402
 403   if (exprNode_isError (test) || exprNode_isError (inc) )
 404     return;
 405
 406   iterations = getForTimes (forPred, forBody );
 407
 408   if (iterations != NULL)
 409     {
 410       doAdjust ( e, forPred, forBody, iterations);
 411       constraintExpr_free(iterations);
 412     }
 413 }
 414
 415
 416 /*    else */
 417 /*      { */
 418 /*        DPRINTF (("Can't get for time ")); */
 419 /*      } */
 420
 421 /*    if (exprNode_isError(init) ) */
 422 /*      { */
 423 /*        return; */
 424 /*      } */
 425
 426 /*    if (init->kind == XPR_ASSIGN) */
 427 /*      { */
 428 /*        t1 = exprData_getOpA (init->edata); */
 429 /*        t2 = exprData_getOpB (init->edata); */
 430
 431 /*        if (! (t1->kind == XPR_VAR) ) */
 432 /*      return; */
 433 /*      } */
 434 /*    else */
 435 /*      return; */
 436
 437 /*    if (test->kind == XPR_FETCH) */
 438 /*      { */
 439 /*        t3 = exprData_getPairA (test->edata); */
 440 /*        t4 = exprData_getPairB (test->edata); */
 441
 442 /*        if (sRef_sameName(t1->sref, t4->sref) ) */
 443 /*      { */
 444 /*        DPRINTF((message ("Found a for loop matching heuristic:%s", exprNode_unparse (forPred) ) )); */
 445 /*        con = constraint_makeEnsureLteMaxRead(t1, t3); */
 446 /*        forPred->ensuresConstraints = constraintList_add(forPred->ensuresConstraints, con);      */
 447 /*      } */
 448 /*        else */
 449 /*      { */
 450 /*        DPRINTF((message ("Didn't Find a for loop matching heuristic:%s %s and %s differ", exprNode_unparse (forPred), exprNode_unparse(t1), exprNode_unparse(t3) ) )); */
 451 /*      } */
 452 /*        return; */
 453 /*      } */