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
 328 #ifdef LIVERANGEHUNT
 329   // now also include those blocks that conditionally escape from this loop
 330   for (i=1; i<count; i++) {
 331     if (ebbs[i]->hasConditionalExit) {
 332       for (block=setFirstItem(aloop->regBlocks);
 333            block;
 334            block=setNextItem(aloop->regBlocks)) {
 335         if (isinSet(block->predList, ebbs[i])) {
 336           printf ("%s has a forced exit from %s\n",
 337                   ebbs[i]->entryLabel->name,
 338                   block->entryLabel->name);
 339         }
 340       }
 341     }
 342   }
 343 #else
 344   /* set max & min dfNum for loopRegion */
 345   for ( block = setFirstItem(aloop->regBlocks); block;
 346         block = setNextItem(aloop->regBlocks)) {
 347       if (block->dfnum > dfMax) dfMax = block->dfnum;
 348       if (block->dfnum < dfMin) dfMin = block->dfnum;
 349   }
 350
 351   /* all blocks that have dfnumbers between dfMin & dfMax are also
 352      part of loop */
 353   for (i = 0 ; i < count ; i++) {
 354     if (ebbs[i]->dfnum > dfMin &&
 355            ebbs[i]->dfnum < dfMax &&
 356           !isinSet(aloop->regBlocks,ebbs[i])) {
 357           if (!ebbs[i]->partOfLoop) {
 358             ebbs[i]->partOfLoop = aloop;
 359           }
 360       }
 361   }
 362 #endif
 363
 364 #ifdef LIVERANGEHUNT
 365   printf ("================\n");
 366   printf (" loop with entry -- > ");
 367   printEntryLabel (aloop->entry, ap);
 368   printf ("\n");
 369   printf (" loop body --> ");
 370   applyToSet (aloop->regBlocks, printEntryLabel);
 371   printf ("\n");
 372   printf (" loop exits --> ");
 373   applyToSet (aloop->exits, printEntryLabel);
 374   printf ("\n");
 375 #endif
 376
 377   /* and if this is a conditional block, the other side of the IFX
 378      (if any, that could have a greater dfnum) is too */
 379   {
 380     // just a burp, but I'm getting close :)
 381   }
 382
 383
 384   /* now add it to the set */
 385   addSetHead (allRegion, aloop);
 386   return 0;
 387 }
 388
 389 /*-----------------------------------------------------------------*/
 390 /* dominatedBy - will return 1 if item is dominated by block       */
 391 /*-----------------------------------------------------------------*/
 392 DEFSETFUNC (dominatedBy)
 393 {
 394   eBBlock *ebp = item;
 395   V_ARG (eBBlock *, block);
 396
 397   return bitVectBitValue (ebp->domVect, block->bbnum);
 398 }
 399
 400 /*-----------------------------------------------------------------*/
 401 /* addDefInExprs - adds an expression into the inexpressions       */
 402 /*-----------------------------------------------------------------*/
 403 DEFSETFUNC (addDefInExprs)
 404 {
 405   eBBlock *ebp = item;
 406   V_ARG (cseDef *, cdp);
 407   V_ARG (eBBlock **, ebbs);
 408   V_ARG (int, count);
 409
 410   addSetHead (&ebp->inExprs, cdp);
 411   cseBBlock (ebp, 0, ebbs, count);
 412   return 0;
 413 }
 414
 415 /*-----------------------------------------------------------------*/
 416 /* assignmentsToSym - for a set of blocks determine # time assigned */
 417 /*-----------------------------------------------------------------*/
 418 int
 419 assignmentsToSym (set * sset, operand * sym)
 420 {
 421   eBBlock *ebp;
 422   int assigns = 0;
 423   set *blocks = setFromSet (sset);
 424
 425   for (ebp = setFirstItem (blocks); ebp;
 426        ebp = setNextItem (blocks))
 427     {
 428
 429       /* get all the definitions for this symbol
 430          in this block */
 431       bitVect *defs = bitVectIntersect (ebp->ldefs, OP_DEFS (sym));
 432       assigns += bitVectnBitsOn (defs);
 433       setToNull ((void **) &defs);
 434
 435     }
 436
 437   return assigns;
 438 }
 439
 440
 441 /*-----------------------------------------------------------------*/
 442 /* isOperandInvariant - determines if an operand is an invariant   */
 443 /*-----------------------------------------------------------------*/
 444 int
 445 isOperandInvariant (operand * op, region * theLoop, set * lInvars)
 446 {
 447   int opin = 0;
 448   /* operand is an invariant if it is a                */
 449   /*       a. constants .                              */
 450   /*       b. that have defintions reaching loop entry */
 451   /*       c. that are already defined as invariant    */
 452   /*       d. has no assignments in the loop           */
 453   if (op)
 454     {
 455       if (IS_OP_LITERAL (op))
 456         opin = 1;
 457       else if (IS_SYMOP (op) &&
 458                OP_SYMBOL (op)->addrtaken)
 459         opin = 0;
 460       else if (ifDefSymIs (theLoop->entry->inExprs, op))
 461         opin = 1;
 462       else if (ifDefSymIs (lInvars, op))
 463         opin = 1;
 464       else if (IS_SYMOP (op) &&
 465                !IS_OP_GLOBAL (op) &&
 466                !IS_OP_VOLATILE (op) &&
 467                assignmentsToSym (theLoop->regBlocks, op) == 0)
 468         opin = 1;
 469       LRH(if (opin && IS_SYMOP(op)) {
 470         printf("isOperandInvariant: %s\n", OP_SYMBOL(op)->name);
 471       });
 472     }
 473   else
 474     opin++;
 475
 476   return opin;
 477 }
 478
 479 /*-----------------------------------------------------------------*/
 480 /* pointerAssigned - will return 1 if pointer set found            */
 481 /*-----------------------------------------------------------------*/
 482 DEFSETFUNC (pointerAssigned)
 483 {
 484   eBBlock *ebp = item;
 485   V_ARG (operand *, op);
 486
 487   return ebp->hasFcall || bitVectBitValue (ebp->ptrsSet, op->key);
 488 }
 489
 490 /*-----------------------------------------------------------------*/
 491 /* hasNonPtrUse - returns true if operand has non pointer usage    */
 492 /*-----------------------------------------------------------------*/
 493 DEFSETFUNC (hasNonPtrUse)
 494 {
 495   eBBlock *ebp = item;
 496   V_ARG (operand *, op);
 497   iCode *ic = usedInRemaining (op, ebp->sch);
 498
 499   if (ic && !POINTER_SET (ic) && !POINTER_GET (ic))
 500     return 1;
 501
 502   return 0;
 503
 504 }
 505
 506 /*-----------------------------------------------------------------*/
 507 /* loopInvariants - takes loop invariants out of region            */
 508 /*-----------------------------------------------------------------*/
 509 int
 510 loopInvariants (region * theLoop, eBBlock ** ebbs, int count)
 511 {
 512   eBBlock *lBlock;
 513   set *lInvars = NULL;
 514
 515   int change = 0;
 516   int fCallsInBlock;
 517
 518   /* if the preHeader does not exist then do nothing */
 519   /* or no exits then do nothing ( have to think about this situation */
 520   if (theLoop->entry->preHeader == NULL ||
 521       theLoop->exits == NULL)
 522     return 0;
 523
 524   /* we will do the elimination for those blocks        */
 525   /* in the loop that dominates all exits from the loop */
 526   for (lBlock = setFirstItem (theLoop->regBlocks); lBlock;
 527        lBlock = setNextItem (theLoop->regBlocks))
 528     {
 529
 530       iCode *ic;
 531       int domsAllExits;
 532       int i;
 533
 534       /* mark the dominates all exits flag */
 535       domsAllExits = (applyToSet (theLoop->exits, dominatedBy, lBlock) ==
 536                       elementsInSet (theLoop->exits));
 537
 538       /* find out if we have a function call in this block */
 539       for (ic = lBlock->sch, fCallsInBlock=0; ic; ic = ic->next) {
 540         if (SKIP_IC(ic)) {
 541           fCallsInBlock++;
 542         }
 543       }
 544
 545       /* now we go thru the instructions of this block and */
 546       /* collect those instructions with invariant operands */
 547       for (ic = lBlock->sch; ic; ic = ic->next)
 548         {
 549
 550           int lin, rin;
 551           cseDef *ivar;
 552
 553           /* jwk: TODO this is only needed if the call is between
 554              here and the definition, but I am too lazy to do that now */
 555
 556           /* if there are function calls in this block */
 557           if (fCallsInBlock) {
 558
 559             /* if this is a pointer get */
 560             if (POINTER_GET(ic)) {
 561               continue;
 562             }
 563
 564             /* if this is an assignment from a global */
 565             if (ic->op=='=' && isOperandGlobal(IC_RIGHT(ic))) {
 566               continue;
 567             }
 568           }
 569
 570           if (SKIP_IC (ic) || POINTER_SET (ic) || ic->op == IFX)
 571             continue;
 572
 573           /* if result is volatile then skip */
 574           if (IC_RESULT (ic) &&
 575               (isOperandVolatile (IC_RESULT (ic), TRUE) ||
 576                IS_OP_PARM (IC_RESULT (ic))))
 577             continue;
 578
 579           /* if result depends on a volatile then skip */
 580           if ((IC_LEFT(ic) && isOperandVolatile(IC_LEFT(ic), TRUE)) ||
 581               (IC_RIGHT(ic) && isOperandVolatile(IC_RIGHT(ic), TRUE)))
 582             continue;
 583
 584           lin = rin = 0;
 585
 586           /* special case */
 587           /* if address of then it is an invariant */
 588           if (ic->op == ADDRESS_OF &&
 589               IS_SYMOP (IC_LEFT (ic)) &&
 590               IS_AGGREGATE (operandType (IC_LEFT (ic))))
 591             lin++;
 592           else {
 593             /* check if left operand is an invariant */
 594             if ((lin = isOperandInvariant (IC_LEFT (ic), theLoop, lInvars)))
 595               /* if this is a pointer get then make sure
 596                  that the pointer set does not exist in
 597                  any of the blocks */
 598               if (POINTER_GET (ic) &&
 599                   (applyToSet (theLoop->regBlocks,
 600                                pointerAssigned, IC_LEFT (ic))))
 601                 lin = 0;
 602           }
 603
 604           /* do the same for right */
 605           rin = isOperandInvariant (IC_RIGHT (ic), theLoop, lInvars);
 606
 607           /* if this is a POINTER_GET then special case, make sure all
 608              usages within the loop are POINTER_GET any other usage
 609              would mean that this is not an invariant , since the pointer
 610              could then be passed as a parameter */
 611           if (POINTER_GET (ic) &&
 612               applyToSet (theLoop->regBlocks, hasNonPtrUse, IC_LEFT (ic)))
 613             continue;
 614
 615           /* if both the left & right are invariants : then check that */
 616           /* this definition exists in the out definition of all the  */
 617           /* blocks, this will ensure that this is not assigned any   */
 618           /* other value in the loop , and not used in this block     */
 619           /* prior to this definition which means only this definition */
 620           /* is used in this loop                                     */
 621           if (lin && rin && IC_RESULT (ic))
 622             {
 623               eBBlock *sBlock;
 624               set *lSet = setFromSet (theLoop->regBlocks);
 625
 626               /* if this block does not dominate all exists */
 627               /* make sure this defintion is not used anywhere else */
 628               if (!domsAllExits)
 629                 {
 630
 631                   if (isOperandGlobal (IC_RESULT (ic)))
 632                     continue;
 633                   /* for successors for all exits */
 634                   for (sBlock = setFirstItem (theLoop->exits); sBlock;
 635                        sBlock = setNextItem (theLoop->exits))
 636                     {
 637
 638                       for (i = 0; i < count; ebbs[i++]->visited = 0);
 639                       lBlock->visited = 1;
 640                       if (applyToSet (sBlock->succList, isDefAlive, ic))
 641                         break;
 642                     }
 643
 644                   /* we have found usage */
 645                   if (sBlock)
 646                     continue;
 647                 }
 648
 649               /* now make sure this is the only definition */
 650               for (sBlock = setFirstItem (lSet); sBlock;
 651                    sBlock = setNextItem (lSet))
 652                 {
 653                   /* if this is the block make sure the definition */
 654                   /* reaches the end of the block */
 655                   if (sBlock == lBlock)
 656                     {
 657                       if (!ifDiCodeIs (sBlock->outExprs, ic))
 658                         break;
 659                     }
 660                   else if (bitVectBitsInCommon (sBlock->defSet, OP_DEFS (IC_RESULT (ic))))
 661                     break;
 662                 }
 663
 664               if (sBlock)
 665                 continue;       /* another definition present in the block */
 666
 667               /* now check if it exists in the in of this block */
 668               /* if not then it was killed before this instruction */
 669               if (!bitVectBitValue (lBlock->inDefs, ic->key))
 670                 continue;
 671
 672               /* now we know it is a true invariant */
 673               /* remove it from the insts chain & put */
 674               /* in the invariant set                */
 675               OP_SYMBOL (IC_RESULT (ic))->isinvariant = 1;
 676               remiCodeFromeBBlock (lBlock, ic);
 677
 678               /* maintain the data flow */
 679               /* this means removing from definition from the */
 680               /* defset of this block and adding it to the    */
 681               /* inexpressions of all blocks within the loop  */
 682               bitVectUnSetBit (lBlock->defSet, ic->key);
 683               bitVectUnSetBit (lBlock->ldefs, ic->key);
 684               ivar = newCseDef (IC_RESULT (ic), ic);
 685               applyToSet (theLoop->regBlocks, addDefInExprs, ivar, ebbs, count);
 686               addSet (&lInvars, ivar);
 687             }
 688         }
 689     }                           /* for all loop blocks */
 690
 691   /* if we have some invariants then */
 692   if (lInvars)
 693     {
 694       eBBlock *preHdr = theLoop->entry->preHeader;
 695       iCode *icFirst = NULL, *icLast = NULL;
 696       cseDef *cdp;
 697
 698       /* create an iCode chain from it */
 699       for (cdp = setFirstItem (lInvars); cdp; cdp = setNextItem (lInvars))
 700         {
 701
 702           /* maintain data flow .. add it to the */
 703           /* ldefs defSet & outExprs of the preheader  */
 704           preHdr->defSet = bitVectSetBit (preHdr->defSet, cdp->diCode->key);
 705           preHdr->ldefs = bitVectSetBit (preHdr->ldefs, cdp->diCode->key);
 706           cdp->diCode->lineno = preHdr->ech->lineno;
 707           addSetHead (&preHdr->outExprs, cdp);
 708
 709
 710           if (!icFirst)
 711             icFirst = cdp->diCode;
 712           if (icLast)
 713             {
 714               icLast->next = cdp->diCode;
 715               cdp->diCode->prev = icLast;
 716               icLast = cdp->diCode;
 717             }
 718           else
 719             icLast = cdp->diCode;
 720           change++;
 721         }
 722
 723       /* add the instruction chain to the end of the
 724          preheader for this loop, preheaders will always
 725          have atleast a label */
 726       preHdr->ech->next = icFirst;
 727       icFirst->prev = preHdr->ech;
 728       preHdr->ech = icLast;
 729       icLast->next = NULL;
 730
 731     }
 732   return change;
 733 }
 734
 735 /*-----------------------------------------------------------------*/
 736 /* addressTaken - returns true if the symbol is found in the addrof */
 737 /*-----------------------------------------------------------------*/
 738 int
 739 addressTaken (set * sset, operand * sym)
 740 {
 741   set *loop;
 742   eBBlock *ebp;
 743   set *loop2;
 744
 745   for (loop = sset; loop; loop = loop->next)
 746     {
 747       ebp = loop->item;
 748       loop2 = ebp->addrOf;
 749       while (loop2)
 750         {
 751           if (isOperandEqual ((operand *) loop2->item, sym))
 752             return 1;
 753           loop2 = loop2->next;
 754         }
 755     }
 756
 757   return 0;
 758 }
 759
 760
 761 /*-----------------------------------------------------------------*/
 762 /* findInduction :- returns 1 & the item if the induction is found */
 763 /*-----------------------------------------------------------------*/
 764 DEFSETFUNC (findInduction)
 765 {
 766   induction *ip = item;
 767   V_ARG (operand *, sym);
 768   V_ARG (induction **, ipp);
 769
 770   if (isOperandEqual (ip->sym, sym))
 771     {
 772       *ipp = ip;
 773       return 1;
 774     }
 775
 776   return 0;
 777 }
 778
 779 /*-----------------------------------------------------------------*/
 780 /* findDefInRegion - finds the definition within the region        */
 781 /*-----------------------------------------------------------------*/
 782 iCode *
 783 findDefInRegion (set * regBlocks, operand * defOp, eBBlock ** owner)
 784 {
 785   eBBlock *lBlock;
 786
 787   /* for all blocks in the region */
 788   for (lBlock = setFirstItem (regBlocks); lBlock;
 789        lBlock = setNextItem (regBlocks))
 790     {
 791
 792       /* if a definition for this exists */
 793       if (bitVectBitsInCommon (lBlock->defSet, OP_DEFS (defOp)))
 794         {
 795           iCode *ic;
 796
 797           /* go thru the instruction chain to find it */
 798           for (ic = lBlock->sch; ic; ic = ic->next)
 799             if (bitVectBitValue (OP_DEFS (defOp), ic->key))
 800               {
 801                 if (owner)
 802                   *owner = lBlock;
 803                 return ic;
 804               }
 805         }
 806     }
 807
 808   return NULL;
 809 }
 810
 811 /*-----------------------------------------------------------------*/
 812 /* basicInduction - finds the basic induction variables in a loop  */
 813 /*-----------------------------------------------------------------*/
 814 set *
 815 basicInduction (region * loopReg, eBBlock ** ebbs, int count)
 816 {
 817   eBBlock *lBlock;
 818   set *indVars = NULL;
 819
 820   /* i.e. all assignments of the form a := a +/- const */
 821   /* for all blocks within the loop do */
 822   for (lBlock = setFirstItem (loopReg->regBlocks); lBlock;
 823        lBlock = setNextItem (loopReg->regBlocks))
 824     {
 825
 826       iCode *ic, *dic;
 827
 828       /* for all instructions in the blocks do */
 829       for (ic = lBlock->sch; ic; ic = ic->next)
 830         {
 831
 832           operand *aSym;
 833           unsigned long litValue;
 834           induction *ip;
 835           iCode *indIc;
 836           eBBlock *owner = NULL;
 837           int nexits;
 838
 839           /* look for assignments of the form */
 840           /*   symbolVar := iTempNN */
 841           if (ic->op != '=')
 842             continue;
 843
 844           if (!IS_TRUE_SYMOP (IC_RESULT (ic)) &&
 845               !OP_SYMBOL (IC_RESULT (ic))->isreqv)
 846             continue;
 847
 848           if (isOperandGlobal (IC_RESULT (ic)))
 849             continue;
 850
 851           if (!IS_ITEMP (IC_RIGHT (ic)))
 852             continue;
 853
 854           /* if it has multiple assignments within the loop then skip */
 855           if (assignmentsToSym (loopReg->regBlocks, IC_RESULT (ic)) > 1)
 856             continue;
 857
 858           /* if the address of this was taken inside the loop then continue */
 859           if (addressTaken (loopReg->regBlocks, IC_RESULT (ic)))
 860             continue;
 861
 862           /* find the definition for the result in the block */
 863           if (!(dic = findDefInRegion (setFromSet (loopReg->regBlocks),
 864                                        IC_RIGHT (ic), &owner)))
 865             continue;
 866
 867           /* if not +/- continue */
 868           if (dic->op != '+' && dic->op != '-')
 869             continue;
 870
 871           /* make sure definition is of the form  a +/- c */
 872           if (!IS_OP_LITERAL (IC_LEFT (dic)) && !IS_OP_LITERAL (IC_RIGHT (dic)))
 873             continue;
 874
 875           aSym = (IS_OP_LITERAL (IC_RIGHT (dic)) ?
 876               (litValue = (unsigned long) operandLitValue (IC_RIGHT (dic)), IC_LEFT (dic)) :
 877               (litValue = (unsigned long) operandLitValue (IC_LEFT (dic)), IC_RIGHT (dic)));
 878
 879           if (!isOperandEqual (IC_RESULT (ic), aSym) &&
 880               !isOperandEqual (IC_RIGHT (ic), aSym))
 881             {
 882               iCode *ddic;
 883               /* find the definition for this and check */
 884               if (!(ddic = findDefInRegion (setFromSet (loopReg->regBlocks),
 885                                             aSym, &owner)))
 886                 continue;
 887
 888               if (ddic->op != '=')
 889                 continue;
 890
 891               if (!isOperandEqual (IC_RESULT (ddic), aSym) ||
 892                   !isOperandEqual (IC_RIGHT (ddic), IC_RESULT (ic)))
 893                 continue;
 894             }
 895
 896           /* if the right hand side has more than one usage then
 897              don't make it an induction (will have to think some more) */
 898           if (bitVectnBitsOn (OP_USES (IC_RIGHT (ic))) > 1)
 899             continue;
 900
 901           /* if the definition is volatile then it cannot be
 902              an induction object */
 903           if (isOperandVolatile (IC_RIGHT (ic), FALSE) ||
 904               isOperandVolatile (IC_RESULT (ic), FALSE))
 905             continue;
 906
 907           /* whew !! that was a lot of work to find the definition */
 908           /* create an induction object */
 909           indIc = newiCode ('=', NULL, IC_RESULT (ic));
 910           indIc->lineno = ic->lineno;
 911           IC_RESULT (indIc) = operandFromOperand (IC_RIGHT (ic));
 912           IC_RESULT (indIc)->isaddr = 0;
 913           OP_SYMBOL (IC_RESULT (indIc))->isind = 1;
 914           ip = newInduction (IC_RIGHT (ic), dic->op, litValue, indIc, NULL);
 915
 916           /* replace the inducted variable by the iTemp */
 917           replaceSymBySym (loopReg->regBlocks, IC_RESULT (ic), IC_RIGHT (ic));
 918
 919           /* if it has only one exit then remove it from here
 920              and put it in the exit block */
 921           nexits = elementsInSet (loopReg->exits);
 922           if (nexits == 1)
 923             {
 924               eBBlock *exit = setFirstItem (loopReg->exits);
 925
 926               /* if it is the same block then there is no
 927                  need to move it about */
 928               if (exit != lBlock)
 929                 {
 930                   iCode *saveic = ic->prev;
 931                   /* remove it */
 932                   remiCodeFromeBBlock (lBlock, ic);
 933                   /* clear the definition */
 934                   bitVectUnSetBit (lBlock->defSet, ic->key);
 935                   /* add it to the exit */
 936                   addiCodeToeBBlock (exit, ic, NULL);
 937                   /* set the definition bit */
 938                   exit->defSet = bitVectSetBit (exit->defSet, ic->key);
 939                   ic = saveic;
 940                 }
 941             }
 942
 943           /* if the number of exits is greater than one then
 944              we use another trick ; we will create an intersection
 945              of succesors of the exits, then take those that are not
 946              part of the loop and have dfNumber greater loop entry
 947              and insert a new definition in them */
 948           if (nexits > 1)
 949             {
 950
 951               bitVect *loopSuccs = intersectLoopSucc (loopReg->exits, ebbs);
 952
 953               /* loopSuccs now contains intersection
 954                  of all the loops successors */
 955               if (loopSuccs)
 956                 {
 957                   int i;
 958                   for (i = 0; i < loopSuccs->size; i++)
 959                     {
 960                       if (bitVectBitValue (loopSuccs, i))
 961                         {
 962
 963                           eBBlock *eblock = ebbs[i];
 964
 965                           /* if the successor does not belong to the loop
 966                              and will be executed after the loop : then
 967                              add a definition to the block */
 968                           if (!isinSet (loopReg->regBlocks, eblock) &&
 969                               eblock->dfnum > loopReg->entry->dfnum)
 970                             {
 971                               /* create the definition */
 972                               iCode *newic = newiCode ('=', NULL,
 973                                         operandFromOperand (IC_RIGHT (ic)));
 974                               IC_RESULT (newic) = operandFromOperand (IC_RESULT (ic));
 975                               OP_DEFS(IC_RESULT (newic))=
 976                                 bitVectSetBit (OP_DEFS (IC_RESULT (newic)), newic->key);
 977                               OP_USES(IC_RIGHT (newic))=
 978                                 bitVectSetBit (OP_USES (IC_RIGHT (newic)), newic->key);
 979                               /* and add it */
 980                               if (eblock->sch && eblock->sch->op == LABEL)
 981                                 addiCodeToeBBlock (eblock, newic, eblock->sch->next);
 982                               else
 983                                 addiCodeToeBBlock (eblock, newic, eblock->sch);
 984                               /* set the definition bit */
 985                               eblock->defSet = bitVectSetBit (eblock->defSet, ic->key);
 986                             }
 987                         }
 988                     }
 989                 }
 990             }
 991
 992           addSet (&indVars, ip);
 993         }
 994
 995     }                           /* end of all blocks for basic induction variables */
 996
 997   return indVars;
 998 }
 999
1000 /*-----------------------------------------------------------------*/
1001 /* loopInduction - remove induction variables from a loop          */
1002 /*-----------------------------------------------------------------*/
1003 int
1004 loopInduction (region * loopReg, eBBlock ** ebbs, int count)
1005 {
1006   int change = 0;
1007   eBBlock *lBlock, *lastBlock = NULL;
1008   set *indVars = NULL;
1009   set *basicInd = NULL;
1010
1011   if (loopReg->entry->preHeader == NULL)
1012     return 0;
1013
1014   /* we first determine the basic Induction variables */
1015   basicInd = setFromSet (indVars = basicInduction (loopReg, ebbs, count));
1016
1017   /* find other induction variables : by other we mean definitions of */
1018   /* the form x := y (* | / ) <constant> .. we will move  this one to */
1019   /* beginning of the loop and reduce strength i.e. replace with +/-  */
1020   /* these expensive expressions: OH! and y must be induction too     */
1021   for (lBlock = setFirstItem (loopReg->regBlocks), lastBlock = lBlock;
1022        lBlock && indVars;
1023        lBlock = setNextItem (loopReg->regBlocks))
1024     {
1025
1026       iCode *ic, *indIc;
1027       induction *ip;
1028
1029       /* last block is the one with the highest block
1030          number */
1031       if (lastBlock->bbnum < lBlock->bbnum)
1032         lastBlock = lBlock;
1033
1034       for (ic = lBlock->sch; ic; ic = ic->next)
1035         {
1036           operand *aSym;
1037           unsigned long litVal;
1038           int lr = 0;
1039
1040           /* consider only * & / */
1041           if (ic->op != '*' && ic->op != '/')
1042             continue;
1043
1044           /* if the result has more definitions then */
1045           if (assignmentsToSym (loopReg->regBlocks, IC_RESULT (ic)) > 1)
1046             continue;
1047
1048           /* check if the operands are what we want */
1049           /* i.e. one of them an symbol the other a literal */
1050           if (!((IS_SYMOP (IC_LEFT (ic)) && IS_OP_LITERAL (IC_RIGHT (ic))) ||
1051                 (IS_OP_LITERAL (IC_LEFT (ic)) && IS_SYMOP (IC_RIGHT (ic)))))
1052             continue;
1053
1054           aSym = (IS_SYMOP (IC_LEFT (ic)) ?
1055           (lr = 1, litVal = (unsigned long) operandLitValue (IC_RIGHT (ic)), IC_LEFT (ic)) :
1056                   (litVal = (unsigned long) operandLitValue (IC_LEFT (ic)), IC_RIGHT (ic)));
1057
1058           ip = NULL;
1059           /* check if this is an induction variable */
1060           if (!applyToSetFTrue (basicInd, findInduction, aSym, &ip))
1061             continue;
1062
1063           /* ask port for size not worth if native instruction
1064              exist for multiply & divide */
1065           if (getSize (operandType (IC_LEFT (ic))) <= (unsigned long) port->support.muldiv ||
1066           getSize (operandType (IC_RIGHT (ic))) <= (unsigned long) port->support.muldiv)
1067             continue;
1068
1069           /* if this is a division then the remainder should be zero
1070              for it to be inducted */
1071           if (ic->op == '/' && (ip->cval % litVal))
1072             continue;
1073
1074           /* create the iCode to be placed in the loop header */
1075           /* and create the induction object */
1076
1077           /* create an instruction */
1078           /* this will be put on the loop header */
1079           indIc = newiCode (ic->op,
1080                             operandFromOperand (aSym),
1081                             operandFromLit (litVal));
1082           indIc->lineno = ic->lineno;
1083           IC_RESULT (indIc) = operandFromOperand (IC_RESULT (ic));
1084           OP_SYMBOL (IC_RESULT (indIc))->isind = 1;
1085
1086           /* keep track of the inductions */
1087           litVal = (ic->op == '*' ? (litVal * ip->cval) :
1088                     (ip->cval / litVal));
1089
1090           addSet (&indVars,
1091                 newInduction (IC_RESULT (ic), ip->op, litVal, indIc, NULL));
1092
1093           /* now change this instruction */
1094           ic->op = ip->op;
1095           if (lr)
1096             {
1097               IC_LEFT (ic) = operandFromOperand (IC_RESULT (ic));
1098               IC_RIGHT (ic) = operandFromLit (litVal);
1099             }
1100           else
1101             {
1102               IC_RIGHT (ic) = operandFromOperand (IC_RESULT (ic));
1103               IC_LEFT (ic) = operandFromLit (litVal);
1104             }
1105
1106           /* we need somemore initialisation code */
1107           /* we subtract the litVal from itself if increment */
1108           if (ic->op == '+')
1109             {
1110               indIc = newiCode ('-',
1111                                 operandFromOperand (IC_RESULT (ic)),
1112                                 operandFromLit (litVal));
1113               indIc->lineno = ic->lineno;
1114               IC_RESULT (indIc) = operandFromOperand (IC_RESULT (ic));
1115
1116               addSet (&indVars,
1117                 newInduction (IC_RESULT (ic), ip->op, litVal, indIc, NULL));
1118             }
1119         }
1120     }
1121
1122   /* if we have some induction variables then */
1123   if (indVars)
1124     {
1125       eBBlock *preHdr = loopReg->entry->preHeader;
1126       iCode *icFirst = NULL, *icLast = NULL;
1127       induction *ip;
1128       bitVect *indVect = NULL;
1129
1130       /* create an iCode chain from it */
1131       for (ip = setFirstItem (indVars);
1132            ip;
1133            ip = setNextItem (indVars))
1134         {
1135
1136           indVect = bitVectSetBit (indVect, ip->ic->key);
1137           ip->ic->lineno = preHdr->ech->lineno;
1138           if (!icFirst)
1139             icFirst = ip->ic;
1140           if (icLast)
1141             {
1142               icLast->next = ip->ic;
1143               ip->ic->prev = icLast;
1144               icLast = ip->ic;
1145             }
1146           else
1147             icLast = ip->ic;
1148           change++;
1149         }
1150
1151       /* add the instruction chain to the end of the */
1152       /* preheader for this loop                     */
1153       preHdr->ech->next = icFirst;
1154       icFirst->prev = preHdr->ech;
1155       preHdr->ech = icLast;
1156       icLast->next = NULL;
1157
1158       /* add the induction variable vector to the last
1159          block in the loop */
1160       lastBlock->isLastInLoop = 1;
1161       lastBlock->linds = bitVectUnion(lastBlock->linds,indVect);
1162     }
1163
1164   setToNull ((void **) &indVars);
1165   return change;
1166 }
1167
1168 /*-----------------------------------------------------------------*/
1169 /* mergeRegions - will merge region with same entry point           */
1170 /*-----------------------------------------------------------------*/
1171 DEFSETFUNC (mergeRegions)
1172 {
1173   region *theLoop = item;
1174   V_ARG (set *, allRegion);
1175   region *lp;
1176
1177   /* if this has already been merged then do nothing */
1178   if (theLoop->merged)
1179     return 0;
1180
1181   /* go thru all the region and check if any of them have the */
1182   /* entryPoint as the Loop                                  */
1183   for (lp = setFirstItem (allRegion); lp; lp = setNextItem (allRegion))
1184     {
1185
1186       if (lp == theLoop)
1187         continue;
1188
1189       if (lp->entry == theLoop->entry)
1190         {
1191           theLoop->regBlocks = unionSets (theLoop->regBlocks,
1192                                           lp->regBlocks, THROW_DEST);
1193           lp->merged = 1;
1194         }
1195     }
1196
1197   return 1;
1198 }
1199
1200 /*-----------------------------------------------------------------*/
1201 /* ifMerged - return 1 if the merge flag is 1                      */
1202 /*-----------------------------------------------------------------*/
1203 DEFSETFUNC (ifMerged)
1204 {
1205   region *lp = item;
1206
1207   return lp->merged;
1208 }
1209
1210 /*-----------------------------------------------------------------*/
1211 /* mergeInnerLoops - will merge into body when entry is present    */
1212 /*-----------------------------------------------------------------*/
1213 DEFSETFUNC (mergeInnerLoops)
1214 {
1215   region *theLoop = item;
1216   V_ARG (set *, allRegion);
1217   V_ARG (int *, maxDepth);
1218   region *lp;
1219
1220   /* check if the entry point is present in the body of any */
1221   /* loop then put the body of this loop into the outer loop */
1222   for (lp = setFirstItem (allRegion); lp; lp = setNextItem (allRegion))
1223     {
1224
1225       if (lp == theLoop)
1226         continue;
1227
1228       if (isinSet (lp->regBlocks, theLoop->entry))
1229         {
1230           lp->containsLoops += theLoop->containsLoops + 1;
1231           if (lp->containsLoops > (*maxDepth))
1232             *maxDepth = lp->containsLoops;
1233
1234           lp->regBlocks = unionSets (lp->regBlocks,
1235                                      theLoop->regBlocks, THROW_DEST);
1236         }
1237     }
1238
1239   return 1;
1240 }
1241
1242
1243 /*-----------------------------------------------------------------*/
1244 /* createLoopRegions - will detect and create a set of natural loops */
1245 /*-----------------------------------------------------------------*/
1246 hTab *
1247 createLoopRegions (eBBlock ** ebbs, int count)
1248 {
1249   set *allRegion = NULL;        /* set of all loops */
1250   hTab *orderedLoops = NULL;
1251   set *bEdges = NULL;
1252   int maxDepth = 0;
1253   region *lp;
1254
1255   LRH(printf ("createLoopRegions: %p\n", ebbs));
1256   /* get all the back edges in the graph */
1257   if (!applyToSet (graphEdges, backEdges, &bEdges))
1258     return 0;                   /* found no loops */
1259
1260   /* for each of these back edges get the blocks that */
1261   /* constitute the loops                             */
1262   applyToSet (bEdges, createLoop, &allRegion, ebbs,count);
1263 #ifdef LIVERANGEHUNT
1264   // print regBlocks
1265   {
1266     eBBlock *ebp;
1267     lp=setFirstItem(allRegion);
1268     printf ("createLoopRegions: ");
1269     for (ebp=setFirstItem(lp->regBlocks); ebp; ebp=setNextItem(lp->regBlocks)) {
1270       printf ("%s ", ebp->entryLabel->name);
1271     }
1272     printf (" %d\n", count);
1273   }
1274 #endif
1275
1276   /* now we will create regions from these loops               */
1277   /* loops with the same entry points are considered to be the */
1278   /* same loop & they are merged. If the entry point of a loop */
1279   /* is found in the body of another loop then , all the blocks */
1280   /* in that loop are added to the loops containing the header */
1281   applyToSet (allRegion, mergeRegions, allRegion);
1282
1283   /* delete those already merged */
1284   deleteItemIf (&allRegion, ifMerged);
1285
1286   applyToSet (allRegion, mergeInnerLoops, allRegion, &maxDepth);
1287   maxDepth++;
1288
1289   /* now create all the exits .. also */
1290   /* create an ordered set of loops   */
1291   /* i.e. we process loops in the inner to outer order */
1292   for (lp = setFirstItem (allRegion); lp; lp = setNextItem (allRegion))
1293     {
1294       applyToSet (lp->regBlocks, addToExitsMarkDepth,
1295                   lp->regBlocks, &lp->exits,
1296                   (maxDepth - lp->containsLoops), lp);
1297
1298       hTabAddItem (&orderedLoops, lp->containsLoops, lp);
1299
1300     }
1301   return orderedLoops;
1302 }
1303
1304 /*-----------------------------------------------------------------*/
1305 /* loopOptimizations - identify region & remove invariants & ind   */
1306 /*-----------------------------------------------------------------*/
1307 int
1308 loopOptimizations (hTab * orderedLoops, eBBlock ** ebbs, int count)
1309 {
1310   region *lp;
1311   int change = 0;
1312   int k;
1313
1314   /* if no loop optimizations requested */
1315   if (!optimize.loopInvariant &&
1316       !optimize.loopInduction)
1317     return 0;
1318
1319   /* now we process the loops inner to outer order */
1320   /* this is essential to maintain data flow information */
1321   /* the other choice is an ugly iteration for the depth */
1322   /* of the loops would hate that */
1323   for (lp = hTabFirstItem (orderedLoops, &k); lp;
1324        lp = hTabNextItem (orderedLoops, &k))
1325     {
1326
1327       if (optimize.loopInvariant)
1328         change += loopInvariants (lp, ebbs, count);
1329
1330       if (optimize.loopInduction)
1331         change += loopInduction (lp, ebbs, count);
1332     }
1333
1334   return change;
1335 }