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

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