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