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