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         {
 464           if (SKIP_IC(ic))
 465             {
 466               fCallsInBlock++;
 467             }
 468         }
 469
 470       /* now we go thru the instructions of this block and */
 471       /* collect those instructions with invariant operands */
 472       for (ic = lBlock->sch; ic; ic = ic->next)
 473         {
 474
 475           int lin, rin;
 476           cseDef *ivar;
 477
 478           /* TODO this is only needed if the call is between
 479              here and the definition, but I am too lazy to do that now */
 480
 481           /* if there are function calls in this block */
 482           if (fCallsInBlock)
 483             {
 484               /* if this is a pointer get */
 485               if (POINTER_GET(ic))
 486                 {
 487                   continue;
 488                 }
 489
 490               /* if this is an assignment from a global */
 491               if (ic->op=='=' && isOperandGlobal(IC_RIGHT(ic)))
 492                 {
 493                   continue;
 494                 }
 495
 496               /* Bug 1717943,
 497                * if this is an assignment to a global */
 498               if (ic->op=='=' && isOperandGlobal(IC_RESULT(ic)))
 499                 {
 500                   continue;
 501                 }
 502             }
 503
 504           if (SKIP_IC (ic) || POINTER_SET (ic) || ic->op == IFX)
 505             continue;
 506
 507           /* iTemp assignment from a literal may be invariant, but it
 508              will needlessly increase register pressure if the
 509              iCode(s) that use this iTemp are not also invariant */
 510           if (ic->op=='=' && IS_ITEMP (IC_RESULT (ic))
 511               && IS_OP_LITERAL (IC_RIGHT (ic)))
 512             continue;
 513
 514           /* if result is volatile then skip */
 515           if (IC_RESULT (ic) &&
 516               (isOperandVolatile (IC_RESULT (ic), TRUE) ||
 517                IS_OP_PARM (IC_RESULT (ic))))
 518             continue;
 519
 520           /* if result depends on a volatile then skip */
 521           if ((IC_LEFT(ic) && isOperandVolatile(IC_LEFT(ic), TRUE)) ||
 522               (IC_RIGHT(ic) && isOperandVolatile(IC_RIGHT(ic), TRUE)))
 523             continue;
 524
 525           lin = rin = 0;
 526
 527           /* special case */
 528           /* if address of then it is an invariant */
 529           if (ic->op == ADDRESS_OF &&
 530               IS_SYMOP (IC_LEFT (ic)) &&
 531               IS_AGGREGATE (operandType (IC_LEFT (ic))))
 532             {
 533               lin++;
 534             }
 535           else
 536             {
 537               /* check if left operand is an invariant */
 538               if ((lin = isOperandInvariant (IC_LEFT (ic), theLoop, lInvars)) &&
 539                 /* if this is a pointer get then make sure
 540                    that the pointer set does not exist in
 541                    any of the blocks */
 542                   POINTER_GET (ic) &&
 543                   applyToSet (theLoop->regBlocks, pointerAssigned, IC_LEFT (ic)))
 544                 {
 545                   lin = 0;
 546                 }
 547             }
 548
 549           /* do the same for right */
 550           rin = isOperandInvariant (IC_RIGHT (ic), theLoop, lInvars);
 551
 552           /* if this is a POINTER_GET then special case, make sure all
 553              usages within the loop are POINTER_GET any other usage
 554              would mean that this is not an invariant , since the pointer
 555              could then be passed as a parameter */
 556           if (POINTER_GET (ic) &&
 557               applyToSet (theLoop->regBlocks, hasNonPtrUse, IC_LEFT (ic)))
 558             continue;
 559
 560
 561           /* if both the left & right are invariants : then check that */
 562           /* this definition exists in the out definition of all the   */
 563           /* blocks, this will ensure that this is not assigned any    */
 564           /* other value in the loop, and not used in this block       */
 565           /* prior to this definition which means only this definition */
 566           /* is used in this loop                                      */
 567           if (lin && rin && IC_RESULT (ic))
 568             {
 569               eBBlock *sBlock;
 570               set *lSet = setFromSet (theLoop->regBlocks);
 571
 572               /* if this block does not dominate all exits */
 573               /* make sure this defintion is not used anywhere else */
 574               if (!domsAllExits)
 575                 {
 576
 577                   if (isOperandGlobal (IC_RESULT (ic)))
 578                     continue;
 579                   /* for successors for all exits */
 580                   for (sBlock = setFirstItem (theLoop->exits); sBlock;
 581                        sBlock = setNextItem (theLoop->exits))
 582                     {
 583
 584                       for (i = 0; i < count; ebbs[i++]->visited = 0);
 585                       lBlock->visited = 1;
 586                       if (applyToSet (sBlock->succList, isDefAlive, ic))
 587                         break;
 588                     }
 589
 590                   /* we have found usage */
 591                   if (sBlock)
 592                     continue;
 593                 }
 594
 595               /* now make sure this is the only definition */
 596               for (sBlock = setFirstItem (lSet); sBlock;
 597                    sBlock = setNextItem (lSet))
 598                 {
 599                   iCode *ic2;
 600                   int used;
 601                   int defDominates;
 602
 603                   /* if this is the block make sure the definition */
 604                   /* reaches the end of the block */
 605                   if (sBlock == lBlock)
 606                     {
 607                       if (!ifDiCodeIs (sBlock->outExprs, ic))
 608                         break;
 609                     }
 610                   else if (bitVectBitsInCommon (sBlock->defSet, OP_DEFS (IC_RESULT (ic))))
 611                     break;
 612
 613                   /* Check that this definition is not assigned */
 614                   /* any other value in this block. Also check */
 615                   /* that any usage in the block is dominated by */
 616                   /* by this definition. */
 617                   defDominates = bitVectBitValue (sBlock->domVect, lBlock->bbnum);
 618                   used = 0;
 619                   for (ic2 = sBlock->sch; ic2; ic2 = ic2->next)
 620                     {
 621                       if (ic2->op == IFX)
 622                         {
 623                           if (isOperandEqual (IC_RESULT (ic), IC_COND (ic2)))
 624                             used = 1;
 625                         }
 626                       else if (ic2->op == JUMPTABLE)
 627                         {
 628                           if (isOperandEqual (IC_RESULT (ic), IC_JTCOND (ic2)))
 629                             used = 1;
 630                         }
 631                       else
 632                         {
 633                           if (IC_LEFT (ic2) && isOperandEqual (IC_RESULT (ic), IC_LEFT (ic2)))
 634                             used = 1;
 635                           if (IC_RIGHT (ic2) && isOperandEqual (IC_RESULT (ic), IC_RIGHT (ic2)))
 636                             used = 1;
 637                           if ((ic != ic2) && (isOperandEqual(IC_RESULT(ic), IC_RESULT(ic2))))
 638                             break;
 639                           /* If used before this definition, might not be invariant */
 640                           if ((ic == ic2) && used)
 641                             break;
 642                         }
 643                       if (used && !defDominates)
 644                         break;
 645                     }
 646                   if (ic2) /* found another definition or a usage before the definition */
 647                     break;
 648                 }
 649
 650               if (sBlock)
 651                 continue;       /* another definition present in the block */
 652
 653
 654               /* now check if it exists in the in of this block */
 655               /* if not then it was killed before this instruction */
 656               if (!bitVectBitValue (lBlock->inDefs, ic->key))
 657                 continue;
 658
 659               /* now we know it is a true invariant */
 660               /* remove it from the insts chain & put */
 661               /* in the invariant set                */
 662
 663               OP_SYMBOL (IC_RESULT (ic))->isinvariant = 1;
 664               SPIL_LOC (IC_RESULT (ic)) = NULL;
 665               remiCodeFromeBBlock (lBlock, ic);
 666
 667               /* maintain the data flow */
 668               /* this means removing from definition from the */
 669               /* defset of this block and adding it to the    */
 670               /* inexpressions of all blocks within the loop  */
 671               bitVectUnSetBit (lBlock->defSet, ic->key);
 672               bitVectUnSetBit (lBlock->ldefs, ic->key);
 673               ivar = newCseDef (IC_RESULT (ic), ic);
 674               applyToSet (theLoop->regBlocks, addDefInExprs, ivar, ebbi);
 675               addSet (&lInvars, ivar);
 676             }
 677         }
 678     }                           /* for all loop blocks */
 679
 680   /* if we have some invariants then */
 681   if (lInvars)
 682     {
 683       eBBlock *preHdr = theLoop->entry->preHeader;
 684       iCode *icFirst = NULL, *icLast = NULL;
 685       cseDef *cdp;
 686
 687       /* create an iCode chain from it */
 688       for (cdp = setFirstItem (lInvars); cdp; cdp = setNextItem (lInvars))
 689         {
 690
 691           /* maintain data flow .. add it to the */
 692           /* ldefs defSet & outExprs of the preheader  */
 693           preHdr->defSet = bitVectSetBit (preHdr->defSet, cdp->diCode->key);
 694           preHdr->ldefs = bitVectSetBit (preHdr->ldefs, cdp->diCode->key);
 695           cdp->diCode->filename = preHdr->ech->filename;
 696           cdp->diCode->lineno = preHdr->ech->lineno;
 697           addSetHead (&preHdr->outExprs, cdp);
 698
 699
 700           if (!icFirst)
 701             icFirst = cdp->diCode;
 702           if (icLast)
 703             {
 704               icLast->next = cdp->diCode;
 705               cdp->diCode->prev = icLast;
 706               icLast = cdp->diCode;
 707             }
 708           else
 709             icLast = cdp->diCode;
 710           change++;
 711         }
 712
 713       /* add the instruction chain to the end of the
 714          preheader for this loop, preheaders will always
 715          have atleast a label */
 716       preHdr->ech->next = icFirst;
 717       icFirst->prev = preHdr->ech;
 718       preHdr->ech = icLast;
 719       icLast->next = NULL;
 720
 721     }
 722   return change;
 723 }
 724
 725 /*-----------------------------------------------------------------*/
 726 /* addressTaken - returns true if the symbol is found in the addrof */
 727 /*-----------------------------------------------------------------*/
 728 static int
 729 addressTaken (set * sset, operand * sym)
 730 {
 731   set *loop;
 732   eBBlock *ebp;
 733   set *loop2;
 734
 735   for (loop = sset; loop; loop = loop->next)
 736     {
 737       ebp = loop->item;
 738       loop2 = ebp->addrOf;
 739       while (loop2)
 740         {
 741           if (isOperandEqual ((operand *) loop2->item, sym))
 742             return 1;
 743           loop2 = loop2->next;
 744         }
 745     }
 746
 747   return 0;
 748 }
 749
 750
 751 /*-----------------------------------------------------------------*/
 752 /* findInduction :- returns 1 & the item if the induction is found */
 753 /*-----------------------------------------------------------------*/
 754 static
 755 DEFSETFUNC (findInduction)
 756 {
 757   induction *ip = item;
 758   V_ARG (operand *, sym);
 759   V_ARG (induction **, ipp);
 760
 761   if (isOperandEqual (ip->sym, sym))
 762     {
 763       *ipp = ip;
 764       return 1;
 765     }
 766
 767   return 0;
 768 }
 769
 770 /*-----------------------------------------------------------------*/
 771 /* findDefInRegion - finds the definition within the region        */
 772 /*-----------------------------------------------------------------*/
 773 static iCode *
 774 findDefInRegion (set * regBlocks, operand * defOp, eBBlock ** owner)
 775 {
 776   eBBlock *lBlock;
 777
 778   /* for all blocks in the region */
 779   for (lBlock = setFirstItem (regBlocks); lBlock;
 780        lBlock = setNextItem (regBlocks))
 781     {
 782
 783       /* if a definition for this exists */
 784       if (bitVectBitsInCommon (lBlock->defSet, OP_DEFS (defOp)))
 785         {
 786           iCode *ic;
 787
 788           /* go thru the instruction chain to find it */
 789           for (ic = lBlock->sch; ic; ic = ic->next)
 790             if (bitVectBitValue (OP_DEFS (defOp), ic->key))
 791               {
 792                 if (owner)
 793                   *owner = lBlock;
 794                 return ic;
 795               }
 796         }
 797     }
 798
 799   return NULL;
 800 }
 801
 802 /*-----------------------------------------------------------------*/
 803 /* addPostLoopBlock - add a ebblock before the successors of the   */
 804 /*                    loop exits                                   */
 805 /*-----------------------------------------------------------------*/
 806 static void
 807 addPostLoopBlock (region *loopReg, ebbIndex *ebbi, iCode *ic)
 808 {
 809   bitVect *loopSuccs;
 810   int i;
 811
 812   /* if the number of exits is greater than one then
 813      we use another trick: we will create an intersection
 814      of succesors of the exits, then take those that are not
 815      part of the loop and have dfNumber greater loop entry (eblock),
 816      insert a new predecessor postLoopBlk before them and add
 817      a copy of ic in the new block. The postLoopBlk in between
 818      is necessary, because the old successors of the loop exits can
 819      be successors of other blocks too: see bug-136564. */
 820
 821   /* loopSuccs now contains intersection
 822       of all the loops successors */
 823   loopSuccs = intersectLoopSucc (loopReg->exits, ebbi->dfOrder);
 824   if (!loopSuccs)
 825     return;
 826
 827   for (i = 0; i < loopSuccs->size; i++)
 828     {
 829       eBBlock *eblock = NULL;
 830       eBBlock *postLoopBlk;
 831       iCode *newic;
 832       int j;
 833
 834       if (!bitVectBitValue (loopSuccs, i))
 835         continue;
 836
 837       /* Need to search for bbnum == i since ebbi->dfOrder is
 838          sorted by dfnum; a direct index won't do.  */
 839       for (j = 0; j < ebbi->count; j++)
 840         if (ebbi->dfOrder[j]->bbnum == i)
 841           {
 842             eblock = ebbi->dfOrder[j];
 843             break;
 844           }
 845       assert(eblock);
 846
 847       /* if the successor does not belong to the loop
 848           and will be executed after the loop : then
 849           add a definition to the block */
 850       if (isinSet (loopReg->regBlocks, eblock))
 851         continue;
 852       if (eblock->dfnum <= loopReg->entry->dfnum)
 853         continue;
 854
 855       /* look for an existing loopExitBlock */
 856       if (strncmp (LOOPEXITLBL,
 857                     eblock->entryLabel->name,
 858                     sizeof(LOOPEXITLBL) - 1) == 0)
 859         {
 860           /* reuse the existing one */
 861           postLoopBlk = eblock;
 862         }
 863       else
 864         {
 865           /* create and insert a new eBBlock.
 866               Damn, that's messy ... */
 867           int i;
 868           set *oldPredList;
 869           eBBlock *ebpi;
 870
 871           postLoopBlk = neweBBlock();
 872
 873           /* create a loopExit-label */
 874           postLoopBlk->entryLabel = newiTempLoopHeaderLabel (0);
 875
 876           /* increase bbnum for all blocks after
 877               (and including) eblock */
 878           for (i = 0; i < ebbi->count; i++)
 879             {
 880               if (ebbi->bbOrder[i]->bbnum >= eblock->bbnum)
 881                 ++ebbi->bbOrder[i]->bbnum;
 882             }
 883           /* insert postLoopBlk before bbnum */
 884           postLoopBlk->bbnum = eblock->bbnum - 1;
 885
 886           ++ebbi->count;
 887
 888           /* these arrays need one more block, which ... */
 889           ebbi->bbOrder = Safe_realloc (ebbi->bbOrder,
 890                                         (ebbi->count + 1) * sizeof(eBBlock *));
 891           /* ... must be initialized with 0 */
 892           ebbi->bbOrder[ebbi->count] = NULL;
 893           /* move the blocks up ... */
 894           memmove (&ebbi->bbOrder[postLoopBlk->bbnum + 1],
 895                    &ebbi->bbOrder[postLoopBlk->bbnum],
 896                    (ebbi->count - postLoopBlk->bbnum - 1) * sizeof(eBBlock *));
 897           /* ... and insert postLoopBlk */
 898           ebbi->bbOrder[postLoopBlk->bbnum] = postLoopBlk;
 899
 900           /* just add postLoopBlk at the end of dfOrder,
 901               computeControlFlow() will compute the new dfnum */
 902           ebbi->dfOrder = Safe_realloc (ebbi->dfOrder,
 903                                         (ebbi->count + 1) * sizeof(eBBlock *));
 904           ebbi->dfOrder[ebbi->count] = NULL;
 905           ebbi->dfOrder[ebbi->count - 1] = postLoopBlk;
 906
 907           /* copy loop information from eblock to postLoopBlk */
 908           if (eblock->partOfLoop)
 909             {
 910               postLoopBlk->partOfLoop = eblock->partOfLoop;
 911               /* add postLoopBlk to loop region */
 912               addSetHead (&postLoopBlk->partOfLoop->regBlocks, postLoopBlk);
 913             }
 914
 915           /* go through loop exits and replace the old exit block eblock
 916               with the new postLoopBlk */
 917           for (ebpi = setFirstItem (loopReg->exits);
 918                ebpi;
 919                ebpi = setNextItem (loopReg->exits))
 920             {
 921               /* replace old label with new label */
 922               replaceLabel (ebpi, eblock->entryLabel, postLoopBlk->entryLabel);
 923             }
 924
 925           /* now eblock is replaced by postLoopBlk.
 926              It's possible, that eblock has an immediate predecessor
 927              (with ebpi->bbnum + 1 == eblock->bbnum), which isn't part of the
 928              loop. This predecessor must stay predecessor of eblock, not of
 929              postLoopBlk. But now postLoopBlk is in between, therefore a GOTO
 930              from this predecessor to eblock must be appended.
 931              Example: bug-136564.c */
 932
 933           /* take all predecessors and subtract the loop exits */
 934           oldPredList = subtractFromSet (eblock->predList,
 935                                          loopReg->exits,
 936                                          THROW_NONE);
 937           for (ebpi = setFirstItem (oldPredList);
 938                ebpi;
 939                ebpi = setNextItem (oldPredList))
 940             {
 941               /* Is it an immediate predecessor (without GOTO)?
 942                  All other predecessors end with a
 943                  GOTO, IF, IFX or JUMPTABLE: nothing to to do */
 944               if (ebpi->bbnum + 1 == postLoopBlk->bbnum)
 945                 {
 946                   /* insert goto to old predecessor of eblock */
 947                   newic = newiCodeLabelGoto (GOTO, eblock->entryLabel);
 948                   addiCodeToeBBlock (ebpi, newic, NULL);
 949                   break; /* got it, only one is possible */
 950                 }
 951             }
 952
 953           /* set the label */
 954           postLoopBlk->sch =
 955           postLoopBlk->ech = newiCodeLabelGoto (LABEL, postLoopBlk->entryLabel);
 956         }
 957
 958       /* create the definition in postLoopBlk */
 959       newic = newiCode ('=', NULL, operandFromOperand (IC_RIGHT (ic)));
 960       IC_RESULT (newic) = operandFromOperand (IC_RESULT (ic));
 961       /* maintain data flow */
 962       OP_DEFS(IC_RESULT (newic)) = bitVectSetBit (OP_DEFS (IC_RESULT (newic)),
 963                                                   newic->key);
 964       OP_USES(IC_RIGHT (newic)) = bitVectSetBit (OP_USES (IC_RIGHT (newic)),
 965                                                  newic->key);
 966
 967       /* and add it */
 968       addiCodeToeBBlock (postLoopBlk, newic, NULL);
 969       postLoopBlk->sch->filename =
 970       postLoopBlk->ech->filename = eblock->sch->filename;
 971       postLoopBlk->sch->lineno =
 972       postLoopBlk->ech->lineno = eblock->sch->lineno;
 973
 974       /* outDefs is needed by computeControlFlow(), anything
 975          else will be set up by computeControlFlow() */
 976       postLoopBlk->outDefs = bitVectSetBit (postLoopBlk->outDefs, newic->key);
 977     } /* for (i = 0; i < loopSuccs->size; i++) */
 978
 979   /* the postLoopBlk and the induction significantly
 980       changed the control flow, recompute it */
 981   computeControlFlow (ebbi);
 982 }
 983
 984 /*-----------------------------------------------------------------*/
 985 /* basicInduction - finds the basic induction variables in a loop  */
 986 /*-----------------------------------------------------------------*/
 987 static set *
 988 basicInduction (region * loopReg, ebbIndex * ebbi)
 989 {
 990   eBBlock *lBlock;
 991   set *indVars = NULL;
 992
 993   /* i.e. all assignments of the form a := a +/- const */
 994   /* for all blocks within the loop do */
 995   for (lBlock = setFirstItem (loopReg->regBlocks); lBlock;
 996        lBlock = setNextItem (loopReg->regBlocks))
 997     {
 998
 999       iCode *ic, *dic;
1000
1001       /* for all instructions in the blocks do */
1002       for (ic = lBlock->sch; ic; ic = ic->next)
1003         {
1004
1005           operand *aSym;
1006           long litValue;
1007           induction *ip;
1008           iCode *indIc;
1009           eBBlock *owner = NULL;
1010           int nexits;
1011           sym_link *optype;
1012
1013           /* To find an induction variable, we need to */
1014           /* find within the loop three iCodes in this */
1015           /* general form:                             */
1016           /*                                           */
1017           /* ddic: iTempB    := symbolVar              */
1018           /* dic:  iTempA    := iTempB + lit           */
1019           /*    or iTempA    := iTempB - lit           */
1020           /*    or iTempA    := lit + iTempB           */
1021           /* ic:   symbolVar := iTempA                 */
1022           /*                                           */
1023           /* (symbolVar may also be an iTemp if it is  */
1024           /*  register equivalent)                     */
1025
1026           /* look for assignments of the form */
1027           /*   symbolVar := iTempNN */
1028           if (ic->op != '=')
1029             continue;
1030
1031           if (!IS_TRUE_SYMOP (IC_RESULT (ic)) &&
1032               !OP_SYMBOL (IC_RESULT (ic))->isreqv)
1033             continue;
1034
1035           if (isOperandGlobal (IC_RESULT (ic)))
1036             continue;
1037
1038           if (!IS_ITEMP (IC_RIGHT (ic)))
1039             continue;
1040
1041           /* if it has multiple assignments within the loop then skip */
1042           if (assignmentsToSym (loopReg->regBlocks, IC_RESULT (ic)) > 1)
1043             continue;
1044
1045           /* if the address of this was taken inside the loop then continue */
1046           if (addressTaken (loopReg->regBlocks, IC_RESULT (ic)))
1047             continue;
1048
1049           /* Only consider variables with integral type. */
1050           /* (2004/12/06 - EEP - ds390 fails regression tests unless */
1051           /* pointers are also considered for induction (due to some */
1052           /* register alloctaion bugs). Remove !IS_PTR clause when */
1053           /* that gets fixed) */
1054           optype = operandType (IC_RIGHT (ic));
1055           if (!IS_INTEGRAL (optype) && !IS_PTR (optype))
1056             continue;
1057
1058           /* find the definition for the result in the block */
1059           if (!(dic = findDefInRegion (setFromSet (loopReg->regBlocks),
1060                                        IC_RIGHT (ic), &owner)))
1061             continue;
1062
1063           /* if not +/- continue */
1064           if (dic->op != '+' && dic->op != '-')
1065             continue;
1066
1067           /* make sure definition is of the form  a +/- c */
1068           if (!IS_OP_LITERAL (IC_LEFT (dic)) && !IS_OP_LITERAL (IC_RIGHT (dic)))
1069             continue;
1070
1071           /* make sure the definition found is the only one */
1072           if (assignmentsToSym (loopReg->regBlocks, IC_RIGHT (ic)) > 1)
1073             continue;
1074
1075           if (IS_OP_LITERAL (IC_RIGHT (dic)))
1076             {
1077               aSym = IC_LEFT (dic);
1078               litValue = (long) operandLitValue (IC_RIGHT (dic));
1079             }
1080           else
1081             {
1082               /* For minus, the literal must not be on the left side. */
1083               /* (Actually, this case could be handled, but it's probably */
1084               /* not worth the extra code) */
1085               if (dic->op == '-')
1086                 continue;
1087               aSym = IC_RIGHT (dic);
1088               litValue = (long) operandLitValue (IC_LEFT (dic));
1089             }
1090
1091           if (!isOperandEqual (IC_RESULT (ic), aSym) &&
1092               !isOperandEqual (IC_RIGHT (ic), aSym))
1093             {
1094               iCode *ddic;
1095               /* find the definition for this and check */
1096               if (!(ddic = findDefInRegion (setFromSet (loopReg->regBlocks),
1097                                             aSym, &owner)))
1098                 continue;
1099
1100               if (ddic->op != '=')
1101                 continue;
1102
1103               if (!isOperandEqual (IC_RESULT (ddic), aSym) ||
1104                   !isOperandEqual (IC_RIGHT (ddic), IC_RESULT (ic)))
1105                 continue;
1106             }
1107
1108           /* if the right hand side has more than one usage then
1109              don't make it an induction (will have to think some more) */
1110           if (bitVectnBitsOn (OP_USES (IC_RIGHT (ic))) > 1)
1111             continue;
1112
1113           /* if the definition is volatile then it cannot be
1114              an induction object */
1115           if (isOperandVolatile (IC_RIGHT (ic), FALSE) ||
1116               isOperandVolatile (IC_RESULT (ic), FALSE))
1117             continue;
1118
1119           /* whew !! that was a lot of work to find the definition */
1120           /* create an induction object */
1121           indIc = newiCode ('=', NULL, IC_RESULT (ic));
1122           indIc->filename = ic->filename;
1123           indIc->lineno = ic->lineno;
1124           IC_RESULT (indIc) = operandFromOperand (IC_RIGHT (ic));
1125           IC_RESULT (indIc)->isaddr = 0;
1126           OP_SYMBOL (IC_RESULT (indIc))->isind = 1;
1127           ip = newInduction (IC_RIGHT (ic), dic->op, litValue, indIc, NULL);
1128
1129           /* replace the inducted variable by the iTemp */
1130           replaceSymBySym (loopReg->regBlocks, IC_RESULT (ic), IC_RIGHT (ic));
1131           /* ic should now be moved to the exit block(s) */
1132
1133           nexits = elementsInSet (loopReg->exits);
1134           if (nexits == 0)
1135             {
1136               /* this is a endless loop without exits: there's
1137                  no need to restore the inducted variable */
1138               iCode *saveic = ic->prev;
1139
1140               /* ic will be removed by killDeadCode() too,
1141                  but it's a nice to see a clean dumploop now. */
1142               remiCodeFromeBBlock (lBlock, ic);
1143               /* clear the definition */
1144               bitVectUnSetBit (lBlock->defSet, ic->key);
1145               ic = saveic;
1146             }
1147           else
1148             addPostLoopBlock (loopReg, ebbi, ic);
1149           addSet (&indVars, ip);
1150         } /* for ic */
1151     }     /* end of all blocks for basic induction variables */
1152
1153   return indVars;
1154 }
1155
1156 /*-----------------------------------------------------------------*/
1157 /* loopInduction - remove induction variables from a loop          */
1158 /*-----------------------------------------------------------------*/
1159 static int
1160 loopInduction (region * loopReg, ebbIndex * ebbi)
1161 {
1162   int change = 0;
1163   eBBlock *lBlock, *owner, *lastBlock = NULL;
1164   set *indVars = NULL;
1165   set *basicInd = NULL;
1166
1167   if (loopReg->entry->preHeader == NULL)
1168     return 0;
1169
1170   /* we first determine the basic Induction variables */
1171   basicInd = setFromSet (indVars = basicInduction (loopReg, ebbi));
1172
1173   /* find other induction variables : by other we mean definitions of */
1174   /* the form x := y (* | / ) <constant> .. we will move  this one to */
1175   /* beginning of the loop and reduce strength i.e. replace with +/-  */
1176   /* these expensive expressions: OH! and y must be induction too     */
1177   for (lBlock = setFirstItem (loopReg->regBlocks), lastBlock = lBlock;
1178        lBlock && indVars;
1179        lBlock = setNextItem (loopReg->regBlocks))
1180     {
1181
1182       iCode *ic, *indIc, *dic;
1183       induction *ip;
1184
1185       /* last block is the one with the highest block
1186          number */
1187       if (lastBlock->bbnum < lBlock->bbnum)
1188         lastBlock = lBlock;
1189
1190       for (ic = lBlock->sch; ic; ic = ic->next)
1191         {
1192           operand *aSym;
1193           long litVal;
1194
1195           /* consider only * & / */
1196           if (ic->op != '*' && ic->op != '/')
1197             continue;
1198
1199           /* only consider variables with integral type */
1200           if (!IS_INTEGRAL (operandType (IC_RESULT (ic))))
1201             continue;
1202
1203           /* if the result has more definitions then */
1204           if (assignmentsToSym (loopReg->regBlocks, IC_RESULT (ic)) > 1)
1205             continue;
1206
1207           /* check if the operands are what we want */
1208           /* i.e. one of them an symbol the other a literal */
1209           if (!((IS_SYMOP (IC_LEFT (ic)) && IS_OP_LITERAL (IC_RIGHT (ic))) ||
1210                 (IS_OP_LITERAL (IC_LEFT (ic)) && IS_SYMOP (IC_RIGHT (ic)))))
1211             continue;
1212
1213           if (IS_SYMOP (IC_LEFT (ic)))
1214             {
1215               aSym = IC_LEFT (ic);
1216               litVal = (long) operandLitValue (IC_RIGHT (ic));
1217             }
1218           else
1219             {
1220               /* For division, the literal must not be on the left side */
1221               if (ic->op == '/')
1222                 continue;
1223               aSym = IC_RIGHT (ic);
1224               litVal = (long) operandLitValue (IC_LEFT (ic));
1225             }
1226
1227           ip = NULL;
1228           /* check if this is an induction variable */
1229           if (!applyToSetFTrue (basicInd, findInduction, aSym, &ip))
1230             continue;
1231
1232           /* ask port for size not worth if native instruction
1233              exist for multiply & divide */
1234           if (getSize (operandType (IC_LEFT (ic))) <= (unsigned long) port->support.muldiv ||
1235           getSize (operandType (IC_RIGHT (ic))) <= (unsigned long) port->support.muldiv)
1236             continue;
1237
1238           /* if this is a division then the remainder should be zero
1239              for it to be inducted */
1240           if (ic->op == '/' && (ip->cval % litVal))
1241             continue;
1242
1243           /* create the iCode to be placed in the loop header */
1244           /* and create the induction object */
1245
1246           /* create an instruction */
1247           /* this will be put on the loop header */
1248           indIc = newiCode (ic->op,
1249                             operandFromOperand (aSym),
1250                             operandFromLit (litVal));
1251           indIc->filename = ic->filename;
1252           indIc->lineno = ic->lineno;
1253           IC_RESULT (indIc) = operandFromOperand (IC_RESULT (ic));
1254           OP_SYMBOL (IC_RESULT (indIc))->isind = 1;
1255
1256           /* keep track of the inductions */
1257           litVal = (ic->op == '*' ? (litVal * ip->cval) :
1258                     (ip->cval / litVal));
1259
1260           addSet (&indVars,
1261                 newInduction (IC_RESULT (ic), ip->op, litVal, indIc, NULL));
1262
1263           /* Replace mul/div with assignment to self; killDeadCode() will */
1264           /* clean this up since we can't use remiCodeFromeBBlock() here. */
1265           ic->op = '=';
1266           IC_LEFT (ic) = NULL;
1267           IC_RIGHT (ic) = IC_RESULT (ic);
1268
1269           /* Insert an update of the induction variable just before */
1270           /* the update of the basic induction variable. */
1271           indIc = newiCode (ip->op,
1272                             operandFromOperand (IC_RESULT (ic)),
1273                             operandFromLit (litVal));
1274           IC_RESULT (indIc) = operandFromOperand (IC_RESULT (ic));
1275           owner = NULL;
1276           dic = findDefInRegion (setFromSet (loopReg->regBlocks), aSym, &owner);
1277           assert (dic);
1278           addiCodeToeBBlock (owner, indIc, dic);
1279
1280         }
1281     }
1282
1283   /* if we have some induction variables then */
1284   if (indVars)
1285     {
1286       eBBlock *preHdr = loopReg->entry->preHeader;
1287       iCode *icFirst = NULL, *icLast = NULL;
1288       induction *ip;
1289       bitVect *indVect = NULL;
1290
1291       /* create an iCode chain from it */
1292       for (ip = setFirstItem (indVars);
1293            ip;
1294            ip = setNextItem (indVars))
1295         {
1296           indVect = bitVectSetBit (indVect, ip->ic->key);
1297           ip->ic->filename = preHdr->ech->filename;
1298           ip->ic->lineno = preHdr->ech->lineno;
1299           if (!icFirst)
1300             icFirst = ip->ic;
1301           if (icLast)
1302             {
1303               icLast->next = ip->ic;
1304               ip->ic->prev = icLast;
1305               icLast = ip->ic;
1306             }
1307           else
1308             icLast = ip->ic;
1309           change++;
1310         }
1311
1312       /* add the instruction chain to the end of the */
1313       /* preheader for this loop                     */
1314       preHdr->ech->next = icFirst;
1315       icFirst->prev = preHdr->ech;
1316       preHdr->ech = icLast;
1317       icLast->next = NULL;
1318
1319       /* add the induction variable vector to the last
1320          block in the loop */
1321       lastBlock->isLastInLoop = 1;
1322       lastBlock->linds = bitVectUnion(lastBlock->linds,indVect);
1323     }
1324
1325   setToNull ((void *) &indVars);
1326   return change;
1327 }
1328
1329 /*-----------------------------------------------------------------*/
1330 /* mergeRegions - will merge region with same entry point           */
1331 /*-----------------------------------------------------------------*/
1332 static
1333 DEFSETFUNC (mergeRegions)
1334 {
1335   region *theLoop = item;
1336   V_ARG (set *, allRegion);
1337   region *lp;
1338
1339   /* if this has already been merged then do nothing */
1340   if (theLoop->merged)
1341     return 0;
1342
1343   /* go thru all the region and check if any of them have the */
1344   /* entryPoint as the Loop                                  */
1345   for (lp = setFirstItem (allRegion); lp; lp = setNextItem (allRegion))
1346     {
1347
1348       if (lp == theLoop)
1349         continue;
1350
1351       if (lp->entry == theLoop->entry)
1352         {
1353           theLoop->regBlocks = unionSets (theLoop->regBlocks,
1354                                           lp->regBlocks, THROW_DEST);
1355           lp->merged = 1;
1356         }
1357     }
1358
1359   return 1;
1360 }
1361
1362 /*-----------------------------------------------------------------*/
1363 /* ifMerged - return 1 if the merge flag is 1                      */
1364 /*-----------------------------------------------------------------*/
1365 static
1366 DEFSETFUNC (ifMerged)
1367 {
1368   region *lp = item;
1369
1370   return lp->merged;
1371 }
1372
1373 /*-----------------------------------------------------------------*/
1374 /* mergeInnerLoops - will merge into body when entry is present    */
1375 /*-----------------------------------------------------------------*/
1376 static
1377 DEFSETFUNC (mergeInnerLoops)
1378 {
1379   region *theLoop = item;
1380   V_ARG (set *, allRegion);
1381   V_ARG (int *, maxDepth);
1382   region *lp;
1383
1384   /* check if the entry point is present in the body of any */
1385   /* loop then put the body of this loop into the outer loop */
1386   for (lp = setFirstItem (allRegion); lp; lp = setNextItem (allRegion))
1387     {
1388
1389       if (lp == theLoop)
1390         continue;
1391
1392       if (isinSet (lp->regBlocks, theLoop->entry))
1393         {
1394           lp->containsLoops += theLoop->containsLoops + 1;
1395           if (lp->containsLoops > (*maxDepth))
1396             *maxDepth = lp->containsLoops;
1397
1398           lp->regBlocks = unionSets (lp->regBlocks,
1399                                      theLoop->regBlocks, THROW_DEST);
1400         }
1401     }
1402
1403   return 1;
1404 }
1405
1406
1407 /*-----------------------------------------------------------------*/
1408 /* createLoopRegions - will detect and create a set of natural loops */
1409 /*-----------------------------------------------------------------*/
1410 hTab *
1411 createLoopRegions (ebbIndex * ebbi)
1412 {
1413   set *allRegion = NULL;        /* set of all loops */
1414   hTab *orderedLoops = NULL;
1415   set *bEdges = NULL;
1416   int maxDepth = 0;
1417   region *lp;
1418
1419   /* get all the back edges in the graph */
1420   if (!applyToSet (graphEdges, backEdges, &bEdges))
1421     return 0;                   /* found no loops */
1422
1423   /* for each of these back edges get the blocks that */
1424   /* constitute the loops                             */
1425   applyToSet (bEdges, createLoop, &allRegion);
1426
1427   /* now we will create regions from these loops               */
1428   /* loops with the same entry points are considered to be the */
1429   /* same loop & they are merged. If the entry point of a loop */
1430   /* is found in the body of another loop then , all the blocks */
1431   /* in that loop are added to the loops containing the header */
1432   applyToSet (allRegion, mergeRegions, allRegion);
1433
1434   /* delete those already merged */
1435   deleteItemIf (&allRegion, ifMerged);
1436
1437   applyToSet (allRegion, mergeInnerLoops, allRegion, &maxDepth);
1438   maxDepth++;
1439
1440   /* now create all the exits .. also */
1441   /* create an ordered set of loops   */
1442   /* i.e. we process loops in the inner to outer order */
1443   for (lp = setFirstItem (allRegion); lp; lp = setNextItem (allRegion))
1444     {
1445       applyToSet (lp->regBlocks, addToExitsMarkDepth,
1446                   lp->regBlocks, &lp->exits,
1447                   (maxDepth - lp->containsLoops), lp);
1448
1449       hTabAddItem (&orderedLoops, lp->containsLoops, lp);
1450
1451     }
1452   return orderedLoops;
1453 }
1454
1455 /*-----------------------------------------------------------------*/
1456 /* loopOptimizations - identify region & remove invariants & ind   */
1457 /*-----------------------------------------------------------------*/
1458 int
1459 loopOptimizations (hTab * orderedLoops, ebbIndex * ebbi)
1460 {
1461   region *lp;
1462   int change = 0;
1463   int k;
1464
1465   /* if no loop optimizations requested */
1466   if (!optimize.loopInvariant &&
1467       !optimize.loopInduction)
1468     return 0;
1469
1470   /* now we process the loops inner to outer order */
1471   /* this is essential to maintain data flow information */
1472   /* the other choice is an ugly iteration for the depth */
1473   /* of the loops would hate that */
1474   for (lp = hTabFirstItem (orderedLoops, &k); lp;
1475        lp = hTabNextItem (orderedLoops, &k))
1476     {
1477
1478       if (optimize.loopInvariant)
1479         change += loopInvariants (lp, ebbi);
1480
1481       if (optimize.loopInduction)
1482         change += loopInduction (lp, ebbi);
1483     }
1484
1485   return change;
1486 }