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