git.gag.com Git - fw/sdcc/blob - src/SDCCloop.c

   1 //#define LIVERANGEHUNT
   2 #ifdef LIVERANGEHUNT
   3   #define LRH(x) x
   4 #else
   5   #define LRH(x)
   6 #endif
   7 /*-------------------------------------------------------------------------
   8
   9   SDCCloop.c - source file for loop detection & optimizations
  10
  11              Written By -  Sandeep Dutta . sandeep.dutta@usa.net (1998)
  12
  13    This program is free software; you can redistribute it and/or modify it
  14    under the terms of the GNU General Public License as published by the
  15    Free Software Foundation; either version 2, or (at your option) any
  16    later version.
  17
  18    This program is distributed in the hope that it will be useful,
  19    but WITHOUT ANY WARRANTY; without even the implied warranty of
  20    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  21    GNU General Public License for more details.
  22
  23    You should have received a copy of the GNU General Public License
  24    along with this program; if not, write to the Free Software
  25    Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
  26
  27    In other words, you are welcome to use, share and improve this program.
  28    You are forbidden to forbid anyone else to use, share and improve
  29    what you give them.   Help stamp out software-hoarding!
  30 -------------------------------------------------------------------------*/
  31
  32 #include "common.h"
  33 #include "newalloc.h"
  34
  35 DEFSETFUNC (isDefAlive);
  36
  37 STACK_DCL (regionStack, eBBlock *, MAX_NEST_LEVEL * 10);
  38
  39 /*-----------------------------------------------------------------*/
  40 /* newInduction - creates a new induction variable                 */
  41 /*-----------------------------------------------------------------*/
  42 induction *
  43 newInduction (operand * sym, unsigned int op,
  44               long constVal, iCode * ic, operand * asym)
  45 {
  46   induction *ip;
  47
  48   ip = Safe_alloc ( sizeof (induction));
  49
  50   ip->sym = sym;
  51   ip->asym = asym;
  52   ip->op = op;
  53   ip->cval = constVal;
  54   ip->ic = ic;
  55   updateSpillLocation(ic,1);
  56   return ip;
  57 }
  58
  59 /*-----------------------------------------------------------------*/
  60 /* newRegion - allocate & returns a loop structure                 */
  61 /*-----------------------------------------------------------------*/
  62 region *
  63 newRegion ()
  64 {
  65   region *lp;
  66
  67   lp = Safe_alloc ( sizeof (region));
  68
  69   return lp;
  70 }
  71
  72
  73 /*-----------------------------------------------------------------*/
  74 /* pinduction - prints induction                                   */
  75 /*-----------------------------------------------------------------*/
  76 DEFSETFUNC (pinduction)
  77 {
  78   induction *ip = item;
  79   iCodeTable *icTab;
  80
  81   fprintf (stdout, "\t");
  82   printOperand (ip->sym, stdout);
  83   icTab = getTableEntry (ip->ic->op);
  84   icTab->iCodePrint (stdout, ip->ic, icTab->printName);
  85   fprintf (stdout, " %04d\n", (int) ip->cval);
  86   return 0;
  87 }
  88
  89 /*-----------------------------------------------------------------*/
  90 /* pregion - prints loop information                                */
  91 /*-----------------------------------------------------------------*/
  92 DEFSETFUNC (pregion)
  93 {
  94   region *lp = item;
  95
  96   printf ("================\n");
  97   printf (" loop with entry -- > ");
  98   printEntryLabel (lp->entry, ap);
  99   printf ("\n");
 100   printf (" loop body --> ");
 101   applyToSet (lp->regBlocks, printEntryLabel);
 102   printf ("\n");
 103   printf (" loop exits --> ");
 104   applyToSet (lp->exits, printEntryLabel);
 105   printf ("\n");
 106   return 0;
 107 }
 108
 109 /*-----------------------------------------------------------------*/
 110 /* backEdges - returns a list of back edges                        */
 111 /*-----------------------------------------------------------------*/
 112 DEFSETFUNC (backEdges)
 113 {
 114   edge *ep = item;
 115   V_ARG (set **, bEdges);
 116
 117   /* if this is a back edge ; to determine this we check */
 118   /* to see if the 'to' is in the dominator list of the  */
 119   /* 'from' if yes then this is a back edge              */
 120   if (bitVectBitValue (ep->from->domVect, ep->to->bbnum))
 121     {
 122       addSetHead (bEdges, ep);
 123       return 1;
 124     }
 125
 126   return 0;
 127 }
 128
 129 /*-----------------------------------------------------------------*/
 130 /* intersectLoopSucc - returns intersection of loop Successors     */
 131 /*-----------------------------------------------------------------*/
 132 static bitVect *
 133 intersectLoopSucc (set * lexits, eBBlock ** ebbs)
 134 {
 135   bitVect *succVect = NULL;
 136   eBBlock *exit = setFirstItem (lexits);
 137
 138   if (!exit)
 139     return NULL;
 140
 141   succVect = bitVectCopy (exit->succVect);
 142
 143   for (exit = setNextItem (lexits); exit;
 144        exit = setNextItem (lexits))
 145     {
 146       succVect = bitVectIntersect (succVect,
 147                                    exit->succVect);
 148     }
 149
 150   return succVect;
 151 }
 152
 153
 154 /*-----------------------------------------------------------------*/
 155 /* loopInsert will insert a block into the loop set                */
 156 /*-----------------------------------------------------------------*/
 157 static void
 158 loopInsert (set ** regionSet, eBBlock * block)
 159 {
 160   if (!isinSet (*regionSet, block))
 161     {
 162       LRH(printf ("loopInsert: %s\n", block->entryLabel->name));
 163       addSetHead (regionSet, block);
 164       STACK_PUSH (regionStack, block);
 165     }
 166 }
 167
 168 /*-----------------------------------------------------------------*/
 169 /* insertIntoLoop - insert item into loop                          */
 170 /*-----------------------------------------------------------------*/
 171 DEFSETFUNC (insertIntoLoop)
 172 {
 173   eBBlock *ebp = item;
 174   V_ARG (set **, regionSet);
 175
 176   loopInsert (regionSet, ebp);
 177   return 0;
 178 }
 179
 180 /*-----------------------------------------------------------------*/
 181 /* isNotInBlocks - will return 1 if not is blocks                  */
 182 /*-----------------------------------------------------------------*/
 183 DEFSETFUNC (isNotInBlocks)
 184 {
 185   eBBlock *ebp = item;
 186   V_ARG (set *, blocks);
 187
 188   if (!isinSet (blocks, ebp))
 189     return 1;
 190
 191   return 0;
 192 }
 193
 194 /*-----------------------------------------------------------------*/
 195 /* hasIncomingDefs - has definitions coming into the loop. i.e.    */
 196 /* check to see if the preheaders outDefs has any definitions      */
 197 /*-----------------------------------------------------------------*/
 198 int
 199 hasIncomingDefs (region * lreg, operand * op)
 200 {
 201   eBBlock *preHdr = lreg->entry->preHeader;
 202
 203   if (preHdr && bitVectBitsInCommon (preHdr->outDefs, OP_DEFS (op)))
 204     return 1;
 205   return 0;
 206 }
 207
 208 /*-----------------------------------------------------------------*/
 209 /* findLoopEndSeq - will return the sequence number of the last    */
 210 /* iCode with the maximum dfNumber in the region                   */
 211 /*-----------------------------------------------------------------*/
 212 int
 213 findLoopEndSeq (region * lreg)
 214 {
 215   eBBlock *block;
 216   eBBlock *lblock;
 217
 218   for (block = lblock = setFirstItem (lreg->regBlocks); block;
 219        block = setNextItem (lreg->regBlocks))
 220     {
 221       if (block != lblock && block->lSeq > lblock->lSeq)
 222         lblock = block;
 223     }
 224
 225   return lblock->lSeq;
 226 }
 227
 228 /*-----------------------------------------------------------------*/
 229 /* addToExitsMarkDepth - will add the the exitSet all blocks that  */
 230 /* have exits, will also update the depth field in the blocks      */
 231 /*-----------------------------------------------------------------*/
 232 DEFSETFUNC (addToExitsMarkDepth)
 233 {
 234   eBBlock *ebp = item;
 235   V_ARG (set *, loopBlocks);
 236   V_ARG (set **, exits);
 237   V_ARG (int, depth);
 238   V_ARG (region *, lr);
 239   LRH(printf ("addToExitsMarkDepth: %s %d\n", ebp->entryLabel->name, depth));
 240   /* mark the loop depth of this block */
 241   //if (!ebp->depth)
 242   if (ebp->depth<depth)
 243     ebp->depth = depth;
 244
 245   /* put the loop region info in the block */
 246   /* NOTE: here we will update only the inner most loop
 247      that it is a part of */
 248   if (!ebp->partOfLoop)
 249     ebp->partOfLoop = lr;
 250
 251   /* if any of the successors go out of the loop then */
 252   /* we add this one to the exits */
 253   if (applyToSet (ebp->succList, isNotInBlocks, loopBlocks))
 254     {
 255       addSetHead (exits, ebp);
 256       return 1;
 257     }
 258
 259   return 0;
 260 }
 261
 262 /*-----------------------------------------------------------------*/
 263 /* createLoop - will create a set of region                        */
 264 /*-----------------------------------------------------------------*/
 265 DEFSETFUNC (createLoop)
 266 {
 267   edge *ep = item;
 268   V_ARG (set **, allRegion);
 269   V_ARG (eBBlock **,ebbs);
 270   V_ARG (int,count);
 271   region *aloop = newRegion ();
 272   eBBlock *block;
 273   int dfMin = count ,dfMax =0, i;
 274
 275   LRH(printf("CreateLoop\n"));
 276   /* make sure regionStack is empty */
 277   while (!STACK_EMPTY (regionStack))
 278     STACK_POP (regionStack);
 279
 280   /* add the entryBlock */
 281   addSet (&aloop->regBlocks, ep->to);
 282 #ifdef LIVERANGEHUNT
 283   // print regBlocks jwk
 284   {
 285     eBBlock *ebp;
 286     region *lp=aloop;
 287     for (ebp=setFirstItem(lp->regBlocks); ebp; ebp=setNextItem(lp->regBlocks)) {
 288       printf ("cl1 %s ", ebp->entryLabel->name);
 289     }
 290     printf (" %d\n", count);
 291   }
 292 #endif
 293   loopInsert (&aloop->regBlocks, ep->from);
 294 #ifdef LIVERANGEHUNT
 295   // print regBlocks jwk
 296   {
 297     eBBlock *ebp;
 298     region *lp=aloop;
 299     for (ebp=setFirstItem(lp->regBlocks); ebp; ebp=setNextItem(lp->regBlocks)) {
 300       printf ("cl2 %s ", ebp->entryLabel->name);
 301     }
 302     printf (" %d\n", count);
 303   }
 304 #endif
 305
 306   while (!STACK_EMPTY (regionStack))
 307     {
 308       block = STACK_POP (regionStack);
 309       /* if block != entry */
 310       if (block != ep->to)
 311         applyToSet (block->predList, insertIntoLoop, &aloop->regBlocks);
 312     }
 313
 314 #ifdef LIVERANGEHUNT
 315   // print regBlocks jwk
 316   {
 317     eBBlock *ebp;
 318     region *lp=aloop;
 319     for (ebp=setFirstItem(lp->regBlocks); ebp; ebp=setNextItem(lp->regBlocks)) {
 320       printf ("cl3 %s ", ebp->entryLabel->name);
 321     }
 322     printf (" %d\n", count);
 323   }
 324 #endif
 325
 326   aloop->entry = ep->to;
 327   /* set max & min dfNum for loopRegion */
 328   for ( block = setFirstItem(aloop->regBlocks); block;
 329         block = setNextItem(aloop->regBlocks)) {
 330       if (block->dfnum > dfMax) dfMax = block->dfnum;
 331       if (block->dfnum < dfMin) dfMin = block->dfnum;
 332   }
 333
 334   /* all blocks that have dfnumbers between dfMin & dfMax are also
 335      part of loop */
 336   for (i = 0 ; i < count ; i++) {
 337     if (ebbs[i]->dfnum > dfMin &&
 338            ebbs[i]->dfnum < dfMax &&
 339           !isinSet(aloop->regBlocks,ebbs[i])) {
 340           if (!ebbs[i]->partOfLoop) ebbs[i]->partOfLoop = aloop;
 341       }
 342     LRH(printf("****** %d %d %d %x %s\n", ebbs[i]->dfnum, dfMin, dfMax, ebbs[i]->partOfLoop, ebbs[i]->entryLabel->name));
 343   }
 344
 345   /* now add it to the set */
 346   addSetHead (allRegion, aloop);
 347   return 0;
 348 }
 349
 350 /*-----------------------------------------------------------------*/
 351 /* dominatedBy - will return 1 if item is dominated by block       */
 352 /*-----------------------------------------------------------------*/
 353 DEFSETFUNC (dominatedBy)
 354 {
 355   eBBlock *ebp = item;
 356   V_ARG (eBBlock *, block);
 357
 358   return bitVectBitValue (ebp->domVect, block->bbnum);
 359 }
 360
 361 /*-----------------------------------------------------------------*/
 362 /* addDefInExprs - adds an expression into the inexpressions       */
 363 /*-----------------------------------------------------------------*/
 364 DEFSETFUNC (addDefInExprs)
 365 {
 366   eBBlock *ebp = item;
 367   V_ARG (cseDef *, cdp);
 368   V_ARG (eBBlock **, ebbs);
 369   V_ARG (int, count);
 370
 371   addSetHead (&ebp->inExprs, cdp);
 372   cseBBlock (ebp, 0, ebbs, count);
 373   return 0;
 374 }
 375
 376 /*-----------------------------------------------------------------*/
 377 /* assignmentsToSym - for a set of blocks determine # time assigned */
 378 /*-----------------------------------------------------------------*/
 379 int
 380 assignmentsToSym (set * sset, operand * sym)
 381 {
 382   eBBlock *ebp;
 383   int assigns = 0;
 384   set *blocks = setFromSet (sset);
 385
 386   for (ebp = setFirstItem (blocks); ebp;
 387        ebp = setNextItem (blocks))
 388     {
 389
 390       /* get all the definitions for this symbol
 391          in this block */
 392       bitVect *defs = bitVectIntersect (ebp->ldefs, OP_DEFS (sym));
 393       assigns += bitVectnBitsOn (defs);
 394       setToNull ((void **) &defs);
 395
 396     }
 397
 398   return assigns;
 399 }
 400
 401
 402 /*-----------------------------------------------------------------*/
 403 /* isOperandInvariant - determines if an operand is an invariant   */
 404 /*-----------------------------------------------------------------*/
 405 int
 406 isOperandInvariant (operand * op, region * theLoop, set * lInvars)
 407 {
 408   int opin = 0;
 409   /* operand is an invariant if it is a                */
 410   /*       a. constants .                              */
 411   /*       b. that have defintions reaching loop entry */
 412   /*       c. that are already defined as invariant    */
 413   /*       d. has no assignments in the loop           */
 414   if (op)
 415     {
 416       if (IS_OP_LITERAL (op))
 417         opin = 1;
 418       else if (IS_SYMOP (op) &&
 419                OP_SYMBOL (op)->addrtaken)
 420         opin = 0;
 421       else if (ifDefSymIs (theLoop->entry->inExprs, op))
 422         opin = 1;
 423       else if (ifDefSymIs (lInvars, op))
 424         opin = 1;
 425       else if (IS_SYMOP (op) &&
 426                !IS_OP_GLOBAL (op) &&
 427                !IS_OP_VOLATILE (op) &&
 428                assignmentsToSym (theLoop->regBlocks, op) == 0)
 429         opin = 1;
 430     }
 431   else
 432     opin++;
 433
 434   return opin;
 435 }
 436
 437 /*-----------------------------------------------------------------*/
 438 /* pointerAssigned - will return 1 if pointer set found            */
 439 /*-----------------------------------------------------------------*/
 440 DEFSETFUNC (pointerAssigned)
 441 {
 442   eBBlock *ebp = item;
 443   V_ARG (operand *, op);
 444
 445   return ebp->hasFcall || bitVectBitValue (ebp->ptrsSet, op->key);
 446 }
 447
 448 /*-----------------------------------------------------------------*/
 449 /* hasNonPtrUse - returns true if operand has non pointer usage    */
 450 /*-----------------------------------------------------------------*/
 451 DEFSETFUNC (hasNonPtrUse)
 452 {
 453   eBBlock *ebp = item;
 454   V_ARG (operand *, op);
 455   iCode *ic = usedInRemaining (op, ebp->sch);
 456
 457   if (ic && !POINTER_SET (ic) && !POINTER_GET (ic))
 458     return 1;
 459
 460   return 0;
 461
 462 }
 463
 464 /*-----------------------------------------------------------------*/
 465 /* loopInvariants - takes loop invariants out of region            */
 466 /*-----------------------------------------------------------------*/
 467 int
 468 loopInvariants (region * theLoop, eBBlock ** ebbs, int count)
 469 {
 470   eBBlock *lBlock;
 471   set *lInvars = NULL;
 472
 473   int change = 0;
 474   int fCallsInBlock;
 475
 476   /* if the preHeader does not exist then do nothing */
 477   /* or no exits then do nothing ( have to think about this situation */
 478   if (theLoop->entry->preHeader == NULL ||
 479       theLoop->exits == NULL)
 480     return 0;
 481
 482   /* we will do the elimination for those blocks        */
 483   /* in the loop that dominates all exits from the loop */
 484   for (lBlock = setFirstItem (theLoop->regBlocks); lBlock;
 485        lBlock = setNextItem (theLoop->regBlocks))
 486     {
 487
 488       iCode *ic;
 489       int domsAllExits;
 490       int i;
 491
 492       /* mark the dominates all exits flag */
 493       domsAllExits = (applyToSet (theLoop->exits, dominatedBy, lBlock) ==
 494                       elementsInSet (theLoop->exits));
 495
 496       /* find out if we have a function call in this block */
 497       for (ic = lBlock->sch, fCallsInBlock=0; ic; ic = ic->next) {
 498         if (SKIP_IC(ic)) {
 499           fCallsInBlock++;
 500         }
 501       }
 502
 503       /* now we go thru the instructions of this block and */
 504       /* collect those instructions with invariant operands */
 505       for (ic = lBlock->sch; ic; ic = ic->next)
 506         {
 507
 508           int lin, rin;
 509           cseDef *ivar;
 510
 511           /* jwk: TODO this is only needed if the call is between
 512              here and the definition, but I am too lazy to do that now */
 513
 514           /* if there are function calls in this block */
 515           if (fCallsInBlock) {
 516
 517             /* if this is a pointer get */
 518             if (POINTER_GET(ic)) {
 519               continue;
 520             }
 521
 522             /* if this is an assignment from a global */
 523             if (ic->op=='=' && isOperandGlobal(IC_RIGHT(ic))) {
 524               continue;
 525             }
 526           }
 527
 528           if (SKIP_IC (ic) || POINTER_SET (ic) || ic->op == IFX)
 529             continue;
 530
 531           /* if result is volatile then skip */
 532           if (IC_RESULT (ic) &&
 533               (isOperandVolatile (IC_RESULT (ic), TRUE) ||
 534                IS_OP_PARM (IC_RESULT (ic))))
 535             continue;
 536
 537           /* if result depends on a volatile then skip */
 538           if ((IC_LEFT(ic) && isOperandVolatile(IC_LEFT(ic), TRUE)) ||
 539               (IC_RIGHT(ic) && isOperandVolatile(IC_RIGHT(ic), TRUE)))
 540             continue;
 541
 542           lin = rin = 0;
 543
 544           /* special case */
 545           /* if address of then it is an invariant */
 546           if (ic->op == ADDRESS_OF &&
 547               IS_SYMOP (IC_LEFT (ic)) &&
 548               IS_AGGREGATE (operandType (IC_LEFT (ic))))
 549             lin++;
 550           else {
 551             /* check if left operand is an invariant */
 552             if ((lin = isOperandInvariant (IC_LEFT (ic), theLoop, lInvars)))
 553               /* if this is a pointer get then make sure
 554                  that the pointer set does not exist in
 555                  any of the blocks */
 556               if (POINTER_GET (ic) &&
 557                   (applyToSet (theLoop->regBlocks,
 558                                pointerAssigned, IC_LEFT (ic))))
 559                 lin = 0;
 560           }
 561
 562           /* do the same for right */
 563           rin = isOperandInvariant (IC_RIGHT (ic), theLoop, lInvars);
 564
 565           /* if this is a POINTER_GET then special case, make sure all
 566              usages within the loop are POINTER_GET any other usage
 567              would mean that this is not an invariant , since the pointer
 568              could then be passed as a parameter */
 569           if (POINTER_GET (ic) &&
 570               applyToSet (theLoop->regBlocks, hasNonPtrUse, IC_LEFT (ic)))
 571             continue;
 572
 573           /* if both the left & right are invariants : then check that */
 574           /* this definition exists in the out definition of all the  */
 575           /* blocks, this will ensure that this is not assigned any   */
 576           /* other value in the loop , and not used in this block     */
 577           /* prior to this definition which means only this definition */
 578           /* is used in this loop                                     */
 579           if (lin && rin && IC_RESULT (ic))
 580             {
 581               eBBlock *sBlock;
 582               set *lSet = setFromSet (theLoop->regBlocks);
 583
 584               /* if this block does not dominate all exists */
 585               /* make sure this defintion is not used anywhere else */
 586               if (!domsAllExits)
 587                 {
 588
 589                   if (isOperandGlobal (IC_RESULT (ic)))
 590                     continue;
 591                   /* for successors for all exits */
 592                   for (sBlock = setFirstItem (theLoop->exits); sBlock;
 593                        sBlock = setNextItem (theLoop->exits))
 594                     {
 595
 596                       for (i = 0; i < count; ebbs[i++]->visited = 0);
 597                       lBlock->visited = 1;
 598                       if (applyToSet (sBlock->succList, isDefAlive, ic))
 599                         break;
 600                     }
 601
 602                   /* we have found usage */
 603                   if (sBlock)
 604                     continue;
 605                 }
 606
 607               /* now make sure this is the only definition */
 608               for (sBlock = setFirstItem (lSet); sBlock;
 609                    sBlock = setNextItem (lSet))
 610                 {
 611                   /* if this is the block make sure the definition */
 612                   /* reaches the end of the block */
 613                   if (sBlock == lBlock)
 614                     {
 615                       if (!ifDiCodeIs (sBlock->outExprs, ic))
 616                         break;
 617                     }
 618                   else if (bitVectBitsInCommon (sBlock->defSet, OP_DEFS (IC_RESULT (ic))))
 619                     break;
 620                 }
 621
 622               if (sBlock)
 623                 continue;       /* another definition present in the block */
 624
 625               /* now check if it exists in the in of this block */
 626               /* if not then it was killed before this instruction */
 627               if (!bitVectBitValue (lBlock->inDefs, ic->key))
 628                 continue;
 629
 630               /* now we know it is a true invariant */
 631               /* remove it from the insts chain & put */
 632               /* in the invariant set                */
 633               OP_SYMBOL (IC_RESULT (ic))->isinvariant = 1;
 634               remiCodeFromeBBlock (lBlock, ic);
 635
 636               /* maintain the data flow */
 637               /* this means removing from definition from the */
 638               /* defset of this block and adding it to the    */
 639               /* inexpressions of all blocks within the loop  */
 640               bitVectUnSetBit (lBlock->defSet, ic->key);
 641               bitVectUnSetBit (lBlock->ldefs, ic->key);
 642               ivar = newCseDef (IC_RESULT (ic), ic);
 643               applyToSet (theLoop->regBlocks, addDefInExprs, ivar, ebbs, count);
 644               addSet (&lInvars, ivar);
 645             }
 646         }
 647     }                           /* for all loop blocks */
 648
 649   /* if we have some invariants then */
 650   if (lInvars)
 651     {
 652       eBBlock *preHdr = theLoop->entry->preHeader;
 653       iCode *icFirst = NULL, *icLast = NULL;
 654       cseDef *cdp;
 655
 656       /* create an iCode chain from it */
 657       for (cdp = setFirstItem (lInvars); cdp; cdp = setNextItem (lInvars))
 658         {
 659
 660           /* maintain data flow .. add it to the */
 661           /* ldefs defSet & outExprs of the preheader  */
 662           preHdr->defSet = bitVectSetBit (preHdr->defSet, cdp->diCode->key);
 663           preHdr->ldefs = bitVectSetBit (preHdr->ldefs, cdp->diCode->key);
 664           cdp->diCode->lineno = preHdr->ech->lineno;
 665           addSetHead (&preHdr->outExprs, cdp);
 666
 667
 668           if (!icFirst)
 669             icFirst = cdp->diCode;
 670           if (icLast)
 671             {
 672               icLast->next = cdp->diCode;
 673               cdp->diCode->prev = icLast;
 674               icLast = cdp->diCode;
 675             }
 676           else
 677             icLast = cdp->diCode;
 678           change++;
 679         }
 680
 681       /* add the instruction chain to the end of the
 682          preheader for this loop, preheaders will always
 683          have atleast a label */
 684       preHdr->ech->next = icFirst;
 685       icFirst->prev = preHdr->ech;
 686       preHdr->ech = icLast;
 687       icLast->next = NULL;
 688
 689     }
 690   return change;
 691 }
 692
 693 /*-----------------------------------------------------------------*/
 694 /* addressTaken - returns true if the symbol is found in the addrof */
 695 /*-----------------------------------------------------------------*/
 696 int
 697 addressTaken (set * sset, operand * sym)
 698 {
 699   set *loop;
 700   eBBlock *ebp;
 701   set *loop2;
 702
 703   for (loop = sset; loop; loop = loop->next)
 704     {
 705       ebp = loop->item;
 706       loop2 = ebp->addrOf;
 707       while (loop2)
 708         {
 709           if (isOperandEqual ((operand *) loop2->item, sym))
 710             return 1;
 711           loop2 = loop2->next;
 712         }
 713     }
 714
 715   return 0;
 716 }
 717
 718
 719 /*-----------------------------------------------------------------*/
 720 /* findInduction :- returns 1 & the item if the induction is found */
 721 /*-----------------------------------------------------------------*/
 722 DEFSETFUNC (findInduction)
 723 {
 724   induction *ip = item;
 725   V_ARG (operand *, sym);
 726   V_ARG (induction **, ipp);
 727
 728   if (isOperandEqual (ip->sym, sym))
 729     {
 730       *ipp = ip;
 731       return 1;
 732     }
 733
 734   return 0;
 735 }
 736
 737 /*-----------------------------------------------------------------*/
 738 /* findDefInRegion - finds the definition within the region        */
 739 /*-----------------------------------------------------------------*/
 740 iCode *
 741 findDefInRegion (set * regBlocks, operand * defOp, eBBlock ** owner)
 742 {
 743   eBBlock *lBlock;
 744
 745   /* for all blocks in the region */
 746   for (lBlock = setFirstItem (regBlocks); lBlock;
 747        lBlock = setNextItem (regBlocks))
 748     {
 749
 750       /* if a definition for this exists */
 751       if (bitVectBitsInCommon (lBlock->defSet, OP_DEFS (defOp)))
 752         {
 753           iCode *ic;
 754
 755           /* go thru the instruction chain to find it */
 756           for (ic = lBlock->sch; ic; ic = ic->next)
 757             if (bitVectBitValue (OP_DEFS (defOp), ic->key))
 758               {
 759                 if (owner)
 760                   *owner = lBlock;
 761                 return ic;
 762               }
 763         }
 764     }
 765
 766   return NULL;
 767 }
 768
 769 /*-----------------------------------------------------------------*/
 770 /* basicInduction - finds the basic induction variables in a loop  */
 771 /*-----------------------------------------------------------------*/
 772 set *
 773 basicInduction (region * loopReg, eBBlock ** ebbs, int count)
 774 {
 775   eBBlock *lBlock;
 776   set *indVars = NULL;
 777
 778   /* i.e. all assignments of the form a := a +/- const */
 779   /* for all blocks within the loop do */
 780   for (lBlock = setFirstItem (loopReg->regBlocks); lBlock;
 781        lBlock = setNextItem (loopReg->regBlocks))
 782     {
 783
 784       iCode *ic, *dic;
 785
 786       /* for all instructions in the blocks do */
 787       for (ic = lBlock->sch; ic; ic = ic->next)
 788         {
 789
 790           operand *aSym;
 791           unsigned long litValue;
 792           induction *ip;
 793           iCode *indIc;
 794           eBBlock *owner = NULL;
 795           int nexits;
 796
 797           /* look for assignments of the form */
 798           /*   symbolVar := iTempNN */
 799           if (ic->op != '=')
 800             continue;
 801
 802           if (!IS_TRUE_SYMOP (IC_RESULT (ic)) &&
 803               !OP_SYMBOL (IC_RESULT (ic))->isreqv)
 804             continue;
 805
 806           if (isOperandGlobal (IC_RESULT (ic)))
 807             continue;
 808
 809           if (!IS_ITEMP (IC_RIGHT (ic)))
 810             continue;
 811
 812           /* if it has multiple assignments within the loop then skip */
 813           if (assignmentsToSym (loopReg->regBlocks, IC_RESULT (ic)) > 1)
 814             continue;
 815
 816           /* if the address of this was taken inside the loop then continue */
 817           if (addressTaken (loopReg->regBlocks, IC_RESULT (ic)))
 818             continue;
 819
 820           /* find the definition for the result in the block */
 821           if (!(dic = findDefInRegion (setFromSet (loopReg->regBlocks),
 822                                        IC_RIGHT (ic), &owner)))
 823             continue;
 824
 825           /* if not +/- continue */
 826           if (dic->op != '+' && dic->op != '-')
 827             continue;
 828
 829           /* make sure definition is of the form  a +/- c */
 830           if (!IS_OP_LITERAL (IC_LEFT (dic)) && !IS_OP_LITERAL (IC_RIGHT (dic)))
 831             continue;
 832
 833           aSym = (IS_OP_LITERAL (IC_RIGHT (dic)) ?
 834               (litValue = (unsigned long) operandLitValue (IC_RIGHT (dic)), IC_LEFT (dic)) :
 835               (litValue = (unsigned long) operandLitValue (IC_LEFT (dic)), IC_RIGHT (dic)));
 836
 837           if (!isOperandEqual (IC_RESULT (ic), aSym) &&
 838               !isOperandEqual (IC_RIGHT (ic), aSym))
 839             {
 840               iCode *ddic;
 841               /* find the definition for this and check */
 842               if (!(ddic = findDefInRegion (setFromSet (loopReg->regBlocks),
 843                                             aSym, &owner)))
 844                 continue;
 845
 846               if (ddic->op != '=')
 847                 continue;
 848
 849               if (!isOperandEqual (IC_RESULT (ddic), aSym) ||
 850                   !isOperandEqual (IC_RIGHT (ddic), IC_RESULT (ic)))
 851                 continue;
 852             }
 853
 854           /* if the right hand side has more than one usage then
 855              don't make it an induction (will have to think some more) */
 856           if (bitVectnBitsOn (OP_USES (IC_RIGHT (ic))) > 1)
 857             continue;
 858
 859           /* if the definition is volatile then it cannot be
 860              an induction object */
 861           if (isOperandVolatile (IC_RIGHT (ic), FALSE) ||
 862               isOperandVolatile (IC_RESULT (ic), FALSE))
 863             continue;
 864
 865           /* whew !! that was a lot of work to find the definition */
 866           /* create an induction object */
 867           indIc = newiCode ('=', NULL, IC_RESULT (ic));
 868           indIc->lineno = ic->lineno;
 869           IC_RESULT (indIc) = operandFromOperand (IC_RIGHT (ic));
 870           IC_RESULT (indIc)->isaddr = 0;
 871           OP_SYMBOL (IC_RESULT (indIc))->isind = 1;
 872           ip = newInduction (IC_RIGHT (ic), dic->op, litValue, indIc, NULL);
 873
 874           /* replace the inducted variable by the iTemp */
 875           replaceSymBySym (loopReg->regBlocks, IC_RESULT (ic), IC_RIGHT (ic));
 876
 877           /* if it has only one exit then remove it from here
 878              and put it in the exit block */
 879           nexits = elementsInSet (loopReg->exits);
 880           if (nexits == 1)
 881             {
 882               eBBlock *exit = setFirstItem (loopReg->exits);
 883
 884               /* if it is the same block then there is no
 885                  need to move it about */
 886               if (exit != lBlock)
 887                 {
 888                   iCode *saveic = ic->prev;
 889                   /* remove it */
 890                   remiCodeFromeBBlock (lBlock, ic);
 891                   /* clear the definition */
 892                   bitVectUnSetBit (lBlock->defSet, ic->key);
 893                   /* add it to the exit */
 894                   addiCodeToeBBlock (exit, ic, NULL);
 895                   /* set the definition bit */
 896                   exit->defSet = bitVectSetBit (exit->defSet, ic->key);
 897                   ic = saveic;
 898                 }
 899             }
 900
 901           /* if the number of exits is greater than one then
 902              we use another trick ; we will create an intersection
 903              of succesors of the exits, then take those that are not
 904              part of the loop and have dfNumber greater loop entry
 905              and insert a new definition in them */
 906           if (nexits > 1)
 907             {
 908
 909               bitVect *loopSuccs = intersectLoopSucc (loopReg->exits, ebbs);
 910
 911               /* loopSuccs now contains intersection
 912                  of all the loops successors */
 913               if (loopSuccs)
 914                 {
 915                   int i;
 916                   for (i = 0; i < loopSuccs->size; i++)
 917                     {
 918                       if (bitVectBitValue (loopSuccs, i))
 919                         {
 920
 921                           eBBlock *eblock = ebbs[i];
 922
 923                           /* if the successor does not belong to the loop
 924                              and will be executed after the loop : then
 925                              add a definition to the block */
 926                           if (!isinSet (loopReg->regBlocks, eblock) &&
 927                               eblock->dfnum > loopReg->entry->dfnum)
 928                             {
 929                               /* create the definition */
 930                               iCode *newic = newiCode ('=', NULL,
 931                                         operandFromOperand (IC_RIGHT (ic)));
 932                               IC_RESULT (newic) = operandFromOperand (IC_RESULT (ic));
 933                               OP_DEFS_SET ((IC_RESULT (newic)),
 934                                 bitVectSetBit (OP_DEFS (IC_RESULT (newic)), newic->key));
 935                               OP_USES_SET ((IC_RIGHT (newic)),
 936                                 bitVectSetBit (OP_USES (IC_RIGHT (newic)), newic->key));
 937                               /* and add it */
 938                               if (eblock->sch && eblock->sch->op == LABEL)
 939                                 addiCodeToeBBlock (eblock, newic, eblock->sch->next);
 940                               else
 941                                 addiCodeToeBBlock (eblock, newic, eblock->sch);
 942                               /* set the definition bit */
 943                               eblock->defSet = bitVectSetBit (eblock->defSet, ic->key);
 944                             }
 945                         }
 946                     }
 947                 }
 948             }
 949
 950           addSet (&indVars, ip);
 951         }
 952
 953     }                           /* end of all blocks for basic induction variables */
 954
 955   return indVars;
 956 }
 957
 958 /*-----------------------------------------------------------------*/
 959 /* loopInduction - remove induction variables from a loop          */
 960 /*-----------------------------------------------------------------*/
 961 int
 962 loopInduction (region * loopReg, eBBlock ** ebbs, int count)
 963 {
 964   int change = 0;
 965   eBBlock *lBlock, *lastBlock = NULL;
 966   set *indVars = NULL;
 967   set *basicInd = NULL;
 968
 969   if (loopReg->entry->preHeader == NULL)
 970     return 0;
 971
 972   /* we first determine the basic Induction variables */
 973   basicInd = setFromSet (indVars = basicInduction (loopReg, ebbs, count));
 974
 975   /* find other induction variables : by other we mean definitions of */
 976   /* the form x := y (* | / ) <constant> .. we will move  this one to */
 977   /* beginning of the loop and reduce strength i.e. replace with +/-  */
 978   /* these expensive expressions: OH! and y must be induction too     */
 979   for (lBlock = setFirstItem (loopReg->regBlocks), lastBlock = lBlock;
 980        lBlock && indVars;
 981        lBlock = setNextItem (loopReg->regBlocks))
 982     {
 983
 984       iCode *ic, *indIc;
 985       induction *ip;
 986
 987       /* last block is the one with the highest block
 988          number */
 989       if (lastBlock->bbnum < lBlock->bbnum)
 990         lastBlock = lBlock;
 991
 992       for (ic = lBlock->sch; ic; ic = ic->next)
 993         {
 994           operand *aSym;
 995           unsigned long litVal;
 996           int lr = 0;
 997
 998           /* consider only * & / */
 999           if (ic->op != '*' && ic->op != '/')
1000             continue;
1001
1002           /* if the result has more definitions then */
1003           if (assignmentsToSym (loopReg->regBlocks, IC_RESULT (ic)) > 1)
1004             continue;
1005
1006           /* check if the operands are what we want */
1007           /* i.e. one of them an symbol the other a literal */
1008           if (!((IS_SYMOP (IC_LEFT (ic)) && IS_OP_LITERAL (IC_RIGHT (ic))) ||
1009                 (IS_OP_LITERAL (IC_LEFT (ic)) && IS_SYMOP (IC_RIGHT (ic)))))
1010             continue;
1011
1012           aSym = (IS_SYMOP (IC_LEFT (ic)) ?
1013           (lr = 1, litVal = (unsigned long) operandLitValue (IC_RIGHT (ic)), IC_LEFT (ic)) :
1014                   (litVal = (unsigned long) operandLitValue (IC_LEFT (ic)), IC_RIGHT (ic)));
1015
1016           ip = NULL;
1017           /* check if this is an induction variable */
1018           if (!applyToSetFTrue (basicInd, findInduction, aSym, &ip))
1019             continue;
1020
1021           /* ask port for size not worth if native instruction
1022              exist for multiply & divide */
1023           if (getSize (operandType (IC_LEFT (ic))) <= (unsigned long) port->support.muldiv ||
1024           getSize (operandType (IC_RIGHT (ic))) <= (unsigned long) port->support.muldiv)
1025             continue;
1026
1027           /* if this is a division then the remainder should be zero
1028              for it to be inducted */
1029           if (ic->op == '/' && (ip->cval % litVal))
1030             continue;
1031
1032           /* create the iCode to be placed in the loop header */
1033           /* and create the induction object */
1034
1035           /* create an instruction */
1036           /* this will be put on the loop header */
1037           indIc = newiCode (ic->op,
1038                             operandFromOperand (aSym),
1039                             operandFromLit (litVal));
1040           indIc->lineno = ic->lineno;
1041           IC_RESULT (indIc) = operandFromOperand (IC_RESULT (ic));
1042           OP_SYMBOL (IC_RESULT (indIc))->isind = 1;
1043
1044           /* keep track of the inductions */
1045           litVal = (ic->op == '*' ? (litVal * ip->cval) :
1046                     (ip->cval / litVal));
1047
1048           addSet (&indVars,
1049                 newInduction (IC_RESULT (ic), ip->op, litVal, indIc, NULL));
1050
1051           /* now change this instruction */
1052           ic->op = ip->op;
1053           if (lr)
1054             {
1055               IC_LEFT (ic) = operandFromOperand (IC_RESULT (ic));
1056               IC_RIGHT (ic) = operandFromLit (litVal);
1057             }
1058           else
1059             {
1060               IC_RIGHT (ic) = operandFromOperand (IC_RESULT (ic));
1061               IC_LEFT (ic) = operandFromLit (litVal);
1062             }
1063
1064           /* we need somemore initialisation code */
1065           /* we subtract the litVal from itself if increment */
1066           if (ic->op == '+')
1067             {
1068               indIc = newiCode ('-',
1069                                 operandFromOperand (IC_RESULT (ic)),
1070                                 operandFromLit (litVal));
1071               indIc->lineno = ic->lineno;
1072               IC_RESULT (indIc) = operandFromOperand (IC_RESULT (ic));
1073
1074               addSet (&indVars,
1075                 newInduction (IC_RESULT (ic), ip->op, litVal, indIc, NULL));
1076             }
1077         }
1078     }
1079
1080   /* if we have some induction variables then */
1081   if (indVars)
1082     {
1083       eBBlock *preHdr = loopReg->entry->preHeader;
1084       iCode *icFirst = NULL, *icLast = NULL;
1085       induction *ip;
1086       bitVect *indVect = NULL;
1087
1088       /* create an iCode chain from it */
1089       for (ip = setFirstItem (indVars);
1090            ip;
1091            ip = setNextItem (indVars))
1092         {
1093
1094           indVect = bitVectSetBit (indVect, ip->ic->key);
1095           ip->ic->lineno = preHdr->ech->lineno;
1096           if (!icFirst)
1097             icFirst = ip->ic;
1098           if (icLast)
1099             {
1100               icLast->next = ip->ic;
1101               ip->ic->prev = icLast;
1102               icLast = ip->ic;
1103             }
1104           else
1105             icLast = ip->ic;
1106           change++;
1107         }
1108
1109       /* add the instruction chain to the end of the */
1110       /* preheader for this loop                     */
1111       preHdr->ech->next = icFirst;
1112       icFirst->prev = preHdr->ech;
1113       preHdr->ech = icLast;
1114       icLast->next = NULL;
1115
1116       /* add the induction variable vector to the last
1117          block in the loop */
1118       lastBlock->isLastInLoop = 1;
1119       lastBlock->linds = bitVectUnion(lastBlock->linds,indVect);
1120     }
1121
1122   setToNull ((void **) &indVars);
1123   return change;
1124 }
1125
1126 /*-----------------------------------------------------------------*/
1127 /* mergeRegions - will merge region with same entry point           */
1128 /*-----------------------------------------------------------------*/
1129 DEFSETFUNC (mergeRegions)
1130 {
1131   region *theLoop = item;
1132   V_ARG (set *, allRegion);
1133   region *lp;
1134
1135   /* if this has already been merged then do nothing */
1136   if (theLoop->merged)
1137     return 0;
1138
1139   /* go thru all the region and check if any of them have the */
1140   /* entryPoint as the Loop                                  */
1141   for (lp = setFirstItem (allRegion); lp; lp = setNextItem (allRegion))
1142     {
1143
1144       if (lp == theLoop)
1145         continue;
1146
1147       if (lp->entry == theLoop->entry)
1148         {
1149           theLoop->regBlocks = unionSets (theLoop->regBlocks,
1150                                           lp->regBlocks, THROW_BOTH);
1151           lp->merged = 1;
1152         }
1153     }
1154
1155   return 1;
1156 }
1157
1158 /*-----------------------------------------------------------------*/
1159 /* ifMerged - return 1 if the merge flag is 1                      */
1160 /*-----------------------------------------------------------------*/
1161 DEFSETFUNC (ifMerged)
1162 {
1163   region *lp = item;
1164
1165   return lp->merged;
1166 }
1167
1168 /*-----------------------------------------------------------------*/
1169 /* mergeInnerLoops - will merge into body when entry is present    */
1170 /*-----------------------------------------------------------------*/
1171 DEFSETFUNC (mergeInnerLoops)
1172 {
1173   region *theLoop = item;
1174   V_ARG (set *, allRegion);
1175   V_ARG (int *, maxDepth);
1176   region *lp;
1177
1178   /* check if the entry point is present in the body of any */
1179   /* loop then put the body of this loop into the outer loop */
1180   for (lp = setFirstItem (allRegion); lp; lp = setNextItem (allRegion))
1181     {
1182
1183       if (lp == theLoop)
1184         continue;
1185
1186       if (isinSet (lp->regBlocks, theLoop->entry))
1187         {
1188           lp->containsLoops += theLoop->containsLoops + 1;
1189           if (lp->containsLoops > (*maxDepth))
1190             *maxDepth = lp->containsLoops;
1191
1192           lp->regBlocks = unionSets (lp->regBlocks,
1193                                      theLoop->regBlocks, THROW_DEST);
1194         }
1195     }
1196
1197   return 1;
1198 }
1199
1200
1201 /*-----------------------------------------------------------------*/
1202 /* createLoopRegions - will detect and create a set of natural loops */
1203 /*-----------------------------------------------------------------*/
1204 hTab *
1205 createLoopRegions (eBBlock ** ebbs, int count)
1206 {
1207   set *allRegion = NULL;        /* set of all loops */
1208   hTab *orderedLoops = NULL;
1209   set *bEdges = NULL;
1210   int maxDepth = 0;
1211   region *lp;
1212
1213   LRH(printf ("createLoopRegions: %x\n", ebbs));
1214   /* get all the back edges in the graph */
1215   if (!applyToSet (graphEdges, backEdges, &bEdges))
1216     return 0;                   /* found no loops */
1217
1218   /* for each of these back edges get the blocks that */
1219   /* constitute the loops                             */
1220   applyToSet (bEdges, createLoop, &allRegion, ebbs,count);
1221 #ifdef LIVERANGEHUNT
1222   // print regBlocks
1223   {
1224     eBBlock *ebp;
1225     lp=setFirstItem(allRegion);
1226     printf ("createLoopRegions: ");
1227     for (ebp=setFirstItem(lp->regBlocks); ebp; ebp=setNextItem(lp->regBlocks)) {
1228       printf ("%s ", ebp->entryLabel->name);
1229     }
1230     printf (" %d\n", count);
1231   }
1232 #endif
1233
1234   /* now we will create regions from these loops               */
1235   /* loops with the same entry points are considered to be the */
1236   /* same loop & they are merged. If the entry point of a loop */
1237   /* is found in the body of another loop then , all the blocks */
1238   /* in that loop are added to the loops containing the header */
1239   applyToSet (allRegion, mergeRegions, allRegion);
1240
1241   /* delete those already merged */
1242   deleteItemIf (&allRegion, ifMerged);
1243
1244   applyToSet (allRegion, mergeInnerLoops, allRegion, &maxDepth);
1245   maxDepth++;
1246
1247   /* now create all the exits .. also */
1248   /* create an ordered set of loops   */
1249   /* i.e. we process loops in the inner to outer order */
1250   for (lp = setFirstItem (allRegion); lp; lp = setNextItem (allRegion))
1251     {
1252       applyToSet (lp->regBlocks, addToExitsMarkDepth,
1253                   lp->regBlocks, &lp->exits,
1254                   (maxDepth - lp->containsLoops), lp);
1255
1256       hTabAddItem (&orderedLoops, lp->containsLoops, lp);
1257
1258     }
1259   return orderedLoops;
1260 }
1261
1262 /*-----------------------------------------------------------------*/
1263 /* loopOptimizations - identify region & remove invariants & ind   */
1264 /*-----------------------------------------------------------------*/
1265 int
1266 loopOptimizations (hTab * orderedLoops, eBBlock ** ebbs, int count)
1267 {
1268   region *lp;
1269   int change = 0;
1270   int k;
1271
1272   /* if no loop optimizations requested */
1273   if (!optimize.loopInvariant &&
1274       !optimize.loopInduction)
1275     return 0;
1276
1277   /* now we process the loops inner to outer order */
1278   /* this is essential to maintain data flow information */
1279   /* the other choice is an ugly iteration for the depth */
1280   /* of the loops would hate that */
1281   for (lp = hTabFirstItem (orderedLoops, &k); lp;
1282        lp = hTabNextItem (orderedLoops, &k))
1283     {
1284
1285       if (optimize.loopInvariant)
1286         change += loopInvariants (lp, ebbs, count);
1287
1288       if (optimize.loopInduction)
1289         change += loopInduction (lp, ebbs, count);
1290     }
1291
1292   return change;
1293 }