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