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