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