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 induction *
  37 newInduction (operand * sym, unsigned int op,
  38               long constVal, iCode * ic, operand * asym)
  39 {
  40   induction *ip;
  41
  42   ip = Safe_calloc (1, sizeof (induction));
  43
  44   ip->sym = sym;
  45   ip->asym = asym;
  46   ip->op = op;
  47   ip->cval = constVal;
  48   ip->ic = ic;
  49
  50   return ip;
  51 }
  52
  53 /*-----------------------------------------------------------------*/
  54 /* newRegion - allocate & returns a loop structure                 */
  55 /*-----------------------------------------------------------------*/
  56 region *
  57 newRegion ()
  58 {
  59   region *lp;
  60
  61   lp = Safe_calloc (1, sizeof (region));
  62
  63   return lp;
  64 }
  65
  66
  67 /*-----------------------------------------------------------------*/
  68 /* pinduction - prints induction                                   */
  69 /*-----------------------------------------------------------------*/
  70 DEFSETFUNC (pinduction)
  71 {
  72   induction *ip = item;
  73   iCodeTable *icTab;
  74
  75   fprintf (stdout, "\t");
  76   printOperand (ip->sym, stdout);
  77   icTab = getTableEntry (ip->ic->op);
  78   icTab->iCodePrint (stdout, ip->ic, icTab->printName);
  79   fprintf (stdout, " %04d\n", (int) ip->cval);
  80   return 0;
  81 }
  82
  83 /*-----------------------------------------------------------------*/
  84 /* pregion - prints loop information                                */
  85 /*-----------------------------------------------------------------*/
  86 DEFSETFUNC (pregion)
  87 {
  88   region *lp = item;
  89
  90   printf ("================\n");
  91   printf (" loop with entry -- > ");
  92   printEntryLabel (lp->entry, ap);
  93   printf ("\n");
  94   printf (" loop body --> ");
  95   applyToSet (lp->regBlocks, printEntryLabel);
  96   printf ("\n");
  97   printf (" loop exits --> ");
  98   applyToSet (lp->exits, printEntryLabel);
  99   printf ("\n");
 100   return 0;
 101 }
 102
 103 /*-----------------------------------------------------------------*/
 104 /* backEdges - returns a list of back edges                        */
 105 /*-----------------------------------------------------------------*/
 106 DEFSETFUNC (backEdges)
 107 {
 108   edge *ep = item;
 109   V_ARG (set **, bEdges);
 110
 111   /* if this is a back edge ; to determine this we check */
 112   /* to see if the 'to' is in the dominator list of the  */
 113   /* 'from' if yes then this is a back edge              */
 114   if (bitVectBitValue (ep->from->domVect, ep->to->bbnum))
 115     {
 116       addSetHead (bEdges, ep);
 117       return 1;
 118     }
 119
 120   return 0;
 121 }
 122
 123 /*-----------------------------------------------------------------*/
 124 /* intersectLoopSucc - returns intersection of loop Successors     */
 125 /*-----------------------------------------------------------------*/
 126 static bitVect *
 127 intersectLoopSucc (set * lexits, eBBlock ** ebbs)
 128 {
 129   bitVect *succVect = NULL;
 130   eBBlock *exit = setFirstItem (lexits);
 131
 132   if (!exit)
 133     return NULL;
 134
 135   succVect = bitVectCopy (exit->succVect);
 136
 137   for (exit = setNextItem (lexits); exit;
 138        exit = setNextItem (lexits))
 139     {
 140       succVect = bitVectIntersect (succVect,
 141                                    exit->succVect);
 142     }
 143
 144   return succVect;
 145 }
 146
 147
 148 /*-----------------------------------------------------------------*/
 149 /* loopInsert will insert a block into the loop set                */
 150 /*-----------------------------------------------------------------*/
 151 static void
 152 loopInsert (set ** regionSet, eBBlock * block)
 153 {
 154   if (!isinSet (*regionSet, block))
 155     {
 156       addSetHead (regionSet, block);
 157       STACK_PUSH (regionStack, block);
 158     }
 159 }
 160
 161 /*-----------------------------------------------------------------*/
 162 /* insertIntoLoop - insert item into loop                          */
 163 /*-----------------------------------------------------------------*/
 164 DEFSETFUNC (insertIntoLoop)
 165 {
 166   eBBlock *ebp = item;
 167   V_ARG (set **, regionSet);
 168
 169   loopInsert (regionSet, ebp);
 170   return 0;
 171 }
 172
 173 /*-----------------------------------------------------------------*/
 174 /* isNotInBlocks - will return 1 if not is blocks                  */
 175 /*-----------------------------------------------------------------*/
 176 DEFSETFUNC (isNotInBlocks)
 177 {
 178   eBBlock *ebp = item;
 179   V_ARG (set *, blocks);
 180
 181   if (!isinSet (blocks, ebp))
 182     return 1;
 183
 184   return 0;
 185 }
 186
 187 /*-----------------------------------------------------------------*/
 188 /* hasIncomingDefs - has definitions coming into the loop. i.e.    */
 189 /* check to see if the preheaders outDefs has any definitions      */
 190 /*-----------------------------------------------------------------*/
 191 int
 192 hasIncomingDefs (region * lreg, operand * op)
 193 {
 194   eBBlock *preHdr = lreg->entry->preHeader;
 195
 196   if (preHdr && bitVectBitsInCommon (preHdr->outDefs, OP_DEFS (op)))
 197     return 1;
 198   return 0;
 199 }
 200
 201 /*-----------------------------------------------------------------*/
 202 /* findLoopEndSeq - will return the sequence number of the last    */
 203 /* iCode with the maximum dfNumber in the region                   */
 204 /*-----------------------------------------------------------------*/
 205 int
 206 findLoopEndSeq (region * lreg)
 207 {
 208   eBBlock *block;
 209   eBBlock *lblock;
 210
 211   for (block = lblock = setFirstItem (lreg->regBlocks); block;
 212        block = setNextItem (lreg->regBlocks))
 213     {
 214       if (block != lblock && block->lSeq > lblock->lSeq)
 215         lblock = block;
 216     }
 217
 218   return lblock->lSeq;
 219 }
 220
 221 /*-----------------------------------------------------------------*/
 222 /* addToExitsMarkDepth - will add the the exitSet all blocks that  */
 223 /* have exits, will also update the depth field in the blocks      */
 224 /*-----------------------------------------------------------------*/
 225 DEFSETFUNC (addToExitsMarkDepth)
 226 {
 227   eBBlock *ebp = item;
 228   V_ARG (set *, loopBlocks);
 229   V_ARG (set **, exits);
 230   V_ARG (int, depth);
 231   V_ARG (region *, lr);
 232
 233   /* mark the loop depth of this block */
 234   if (!ebp->depth)
 235     ebp->depth = depth;
 236
 237   /* put the loop region info in the block */
 238   /* NOTE: here we will update only the inner most loop
 239      that it is a part of */
 240   if (!ebp->partOfLoop)
 241     ebp->partOfLoop = lr;
 242
 243   /* if any of the successors go out of the loop then */
 244   /* we add this one to the exits */
 245   if (applyToSet (ebp->succList, isNotInBlocks, loopBlocks))
 246     {
 247       addSetHead (exits, ebp);
 248       return 1;
 249     }
 250
 251   return 0;
 252 }
 253
 254 /*-----------------------------------------------------------------*/
 255 /* createLoop - will create a set of region                        */
 256 /*-----------------------------------------------------------------*/
 257 DEFSETFUNC (createLoop)
 258 {
 259   edge *ep = item;
 260   V_ARG (set **, allRegion);
 261   region *aloop = newRegion ();
 262   eBBlock *block;
 263
 264   /* make sure regionStack is empty */
 265   while (!STACK_EMPTY (regionStack))
 266     STACK_POP (regionStack);
 267
 268   /* add the entryBlock */
 269   addSet (&aloop->regBlocks, ep->to);
 270   loopInsert (&aloop->regBlocks, ep->from);
 271
 272   while (!STACK_EMPTY (regionStack))
 273     {
 274       block = STACK_POP (regionStack);
 275       /* if block != entry */
 276       if (block != ep->to)
 277         applyToSet (block->predList, insertIntoLoop, &aloop->regBlocks);
 278     }
 279
 280   aloop->entry = ep->to;
 281
 282   /* now add it to the set */
 283   addSetHead (allRegion, aloop);
 284   return 0;
 285 }
 286
 287 /*-----------------------------------------------------------------*/
 288 /* dominatedBy - will return 1 if item is dominated by block       */
 289 /*-----------------------------------------------------------------*/
 290 DEFSETFUNC (dominatedBy)
 291 {
 292   eBBlock *ebp = item;
 293   V_ARG (eBBlock *, block);
 294
 295   return bitVectBitValue (ebp->domVect, block->bbnum);
 296 }
 297
 298 /*-----------------------------------------------------------------*/
 299 /* addDefInExprs - adds an expression into the inexpressions       */
 300 /*-----------------------------------------------------------------*/
 301 DEFSETFUNC (addDefInExprs)
 302 {
 303   eBBlock *ebp = item;
 304   V_ARG (cseDef *, cdp);
 305   V_ARG (eBBlock **, ebbs);
 306   V_ARG (int, count);
 307
 308   addSetHead (&ebp->inExprs, cdp);
 309   cseBBlock (ebp, 0, ebbs, count);
 310   return 0;
 311 }
 312
 313 /*-----------------------------------------------------------------*/
 314 /* assignmentsToSym - for a set of blocks determine # time assigned */
 315 /*-----------------------------------------------------------------*/
 316 int
 317 assignmentsToSym (set * sset, operand * sym)
 318 {
 319   eBBlock *ebp;
 320   int assigns = 0;
 321   set *blocks = setFromSet (sset);
 322
 323   for (ebp = setFirstItem (blocks); ebp;
 324        ebp = setNextItem (blocks))
 325     {
 326
 327       /* get all the definitions for this symbol
 328          in this block */
 329       bitVect *defs = bitVectIntersect (ebp->ldefs, OP_DEFS (sym));
 330       assigns += bitVectnBitsOn (defs);
 331       setToNull ((void **) &defs);
 332
 333     }
 334
 335   return assigns;
 336 }
 337
 338
 339 /*-----------------------------------------------------------------*/
 340 /* isOperandInvariant - determines if an operand is an invariant   */
 341 /*-----------------------------------------------------------------*/
 342 int
 343 isOperandInvariant (operand * op, region * theLoop, set * lInvars)
 344 {
 345   int opin = 0;
 346   /* operand is an invariant if it is a                */
 347   /*       a. constants .                              */
 348   /*       b. that have defintions reaching loop entry */
 349   /*       c. that are already defined as invariant    */
 350   /*       d. has no assignments in the loop           */
 351   if (op)
 352     {
 353       if (IS_OP_LITERAL (op))
 354         opin = 1;
 355       else if (IS_SYMOP (op) &&
 356                OP_SYMBOL (op)->addrtaken)
 357         opin = 0;
 358       else if (ifDefSymIs (theLoop->entry->inExprs, op))
 359         opin = 1;
 360       else if (ifDefSymIs (lInvars, op))
 361         opin = 1;
 362       else if (IS_SYMOP (op) &&
 363                !IS_OP_GLOBAL (op) &&
 364                !IS_OP_VOLATILE (op) &&
 365                assignmentsToSym (theLoop->regBlocks, op) == 0)
 366         opin = 1;
 367     }
 368   else
 369     opin++;
 370
 371   return opin;
 372 }
 373
 374 /*-----------------------------------------------------------------*/
 375 /* pointerAssigned - will return 1 if pointer set found            */
 376 /*-----------------------------------------------------------------*/
 377 DEFSETFUNC (pointerAssigned)
 378 {
 379   eBBlock *ebp = item;
 380   V_ARG (operand *, op);
 381
 382   return ebp->hasFcall || bitVectBitValue (ebp->ptrsSet, op->key);
 383 }
 384
 385 /*-----------------------------------------------------------------*/
 386 /* hasNonPtrUse - returns true if operand has non pointer usage    */
 387 /*-----------------------------------------------------------------*/
 388 DEFSETFUNC (hasNonPtrUse)
 389 {
 390   eBBlock *ebp = item;
 391   V_ARG (operand *, op);
 392   iCode *ic = usedInRemaining (op, ebp->sch);
 393
 394   if (ic && !POINTER_SET (ic) && !POINTER_GET (ic))
 395     return 1;
 396
 397   return 0;
 398
 399 }
 400
 401 /*-----------------------------------------------------------------*/
 402 /* loopInvariants - takes loop invariants out of region            */
 403 /*-----------------------------------------------------------------*/
 404 int
 405 loopInvariants (region * theLoop, eBBlock ** ebbs, int count)
 406 {
 407   eBBlock *lBlock;
 408   set *lInvars = NULL;
 409
 410   int change = 0;
 411
 412   /* if the preHeader does not exist then do nothing */
 413   /* or no exits then do nothing ( have to think about this situation */
 414   if (theLoop->entry->preHeader == NULL ||
 415       theLoop->exits == NULL)
 416     return 0;
 417
 418   /* we will do the elimination for those blocks        */
 419   /* in the loop that dominates all exits from the loop */
 420   for (lBlock = setFirstItem (theLoop->regBlocks); lBlock;
 421        lBlock = setNextItem (theLoop->regBlocks))
 422     {
 423
 424       iCode *ic;
 425       int domsAllExits;
 426       int i;
 427
 428       /* mark the dominates all exits flag */
 429       domsAllExits = (applyToSet (theLoop->exits, dominatedBy, lBlock) ==
 430                       elementsInSet (theLoop->exits));
 431
 432
 433       /* now we go thru the instructions of this block and */
 434       /* collect those instructions with invariant operands */
 435       for (ic = lBlock->sch; ic; ic = ic->next)
 436         {
 437
 438           int lin, rin;
 439           cseDef *ivar;
 440
 441           if (SKIP_IC (ic) || POINTER_SET (ic) || ic->op == IFX)
 442             continue;
 443
 444           /* if result is volatile then skip */
 445           if (IC_RESULT (ic) &&
 446               (isOperandVolatile (IC_RESULT (ic), TRUE) ||
 447                IS_OP_PARM (IC_RESULT (ic))))
 448             continue;
 449
 450           /* if result depends on a volatile then skip */
 451           if ((IC_LEFT(ic) && isOperandVolatile(IC_LEFT(ic), TRUE)) ||
 452               (IC_RIGHT(ic) && isOperandVolatile(IC_RIGHT(ic), TRUE)))
 453             continue;
 454
 455           lin = rin = 0;
 456
 457           /* special case */
 458           /* if address of then it is an invariant */
 459           if (ic->op == ADDRESS_OF &&
 460               IS_SYMOP (IC_LEFT (ic)) &&
 461               IS_AGGREGATE (operandType (IC_LEFT (ic))))
 462             lin++;
 463           else
 464             /* check if left operand is an invariant */
 465           if ((lin = isOperandInvariant (IC_LEFT (ic), theLoop, lInvars)))
 466             /* if this is a pointer get then make sure
 467                that the pointer set does not exist in
 468                any of the blocks */
 469             if (POINTER_GET (ic) &&
 470             (applyToSet (theLoop->regBlocks, pointerAssigned, IC_LEFT (ic))))
 471               lin = 0;
 472
 473           /* do the same for right */
 474           rin = isOperandInvariant (IC_RIGHT (ic), theLoop, lInvars);
 475
 476           /* if this is a POINTER_GET then special case, make sure all
 477              usages within the loop are POINTER_GET any other usage
 478              would mean that this is not an invariant , since the pointer
 479              could then be passed as a parameter */
 480           if (POINTER_GET (ic) &&
 481               applyToSet (theLoop->regBlocks, hasNonPtrUse, IC_LEFT (ic)))
 482             continue;
 483
 484           /* if both the left & right are invariants : then check that */
 485           /* this definition exists in the out definition of all the  */
 486           /* blocks, this will ensure that this is not assigned any   */
 487           /* other value in the loop , and not used in this block     */
 488           /* prior to this definition which means only this definition */
 489           /* is used in this loop                                     */
 490           if (lin && rin && IC_RESULT (ic))
 491             {
 492               eBBlock *sBlock;
 493               set *lSet = setFromSet (theLoop->regBlocks);
 494
 495               /* if this block does not dominate all exists */
 496               /* make sure this defintion is not used anywhere else */
 497               if (!domsAllExits)
 498                 {
 499
 500                   if (isOperandGlobal (IC_RESULT (ic)))
 501                     continue;
 502                   /* for successors for all exits */
 503                   for (sBlock = setFirstItem (theLoop->exits); sBlock;
 504                        sBlock = setNextItem (theLoop->exits))
 505                     {
 506
 507                       for (i = 0; i < count; ebbs[i++]->visited = 0);
 508                       lBlock->visited = 1;
 509                       if (applyToSet (sBlock->succList, isDefAlive, ic))
 510                         break;
 511                     }
 512
 513                   /* we have found usage */
 514                   if (sBlock)
 515                     continue;
 516                 }
 517
 518               /* now make sure this is the only definition */
 519               for (sBlock = setFirstItem (lSet); sBlock;
 520                    sBlock = setNextItem (lSet))
 521                 {
 522                   /* if this is the block make sure the definition */
 523                   /* reaches the end of the block */
 524                   if (sBlock == lBlock)
 525                     {
 526                       if (!ifDiCodeIs (sBlock->outExprs, ic))
 527                         break;
 528                     }
 529                   else if (bitVectBitsInCommon (sBlock->defSet, OP_DEFS (IC_RESULT (ic))))
 530                     break;
 531                 }
 532
 533               if (sBlock)
 534                 continue;       /* another definition present in the block */
 535
 536               /* now check if it exists in the in of this block */
 537               /* if not then it was killed before this instruction */
 538               if (!bitVectBitValue (lBlock->inDefs, ic->key))
 539                 continue;
 540
 541               /* now we know it is a true invariant */
 542               /* remove it from the insts chain & put */
 543               /* in the invariant set                */
 544               OP_SYMBOL (IC_RESULT (ic))->isinvariant = 1;
 545               remiCodeFromeBBlock (lBlock, ic);
 546
 547               /* maintain the data flow */
 548               /* this means removing from definition from the */
 549               /* defset of this block and adding it to the    */
 550               /* inexpressions of all blocks within the loop  */
 551               bitVectUnSetBit (lBlock->defSet, ic->key);
 552               bitVectUnSetBit (lBlock->ldefs, ic->key);
 553               ivar = newCseDef (IC_RESULT (ic), ic);
 554               applyToSet (theLoop->regBlocks, addDefInExprs, ivar, ebbs, count);
 555               addSet (&lInvars, ivar);
 556             }
 557         }
 558     }                           /* for all loop blocks */
 559
 560   /* if we have some invariants then */
 561   if (lInvars)
 562     {
 563       eBBlock *preHdr = theLoop->entry->preHeader;
 564       iCode *icFirst = NULL, *icLast = NULL;
 565       cseDef *cdp;
 566
 567       /* create an iCode chain from it */
 568       for (cdp = setFirstItem (lInvars); cdp; cdp = setNextItem (lInvars))
 569         {
 570
 571           /* maintain data flow .. add it to the */
 572           /* ldefs defSet & outExprs of the preheader  */
 573           preHdr->defSet = bitVectSetBit (preHdr->defSet, cdp->diCode->key);
 574           preHdr->ldefs = bitVectSetBit (preHdr->ldefs, cdp->diCode->key);
 575           cdp->diCode->lineno = preHdr->ech->lineno;
 576           addSetHead (&preHdr->outExprs, cdp);
 577
 578
 579           if (!icFirst)
 580             icFirst = cdp->diCode;
 581           if (icLast)
 582             {
 583               icLast->next = cdp->diCode;
 584               cdp->diCode->prev = icLast;
 585               icLast = cdp->diCode;
 586             }
 587           else
 588             icLast = cdp->diCode;
 589           change++;
 590         }
 591
 592       /* add the instruction chain to the end of the
 593          preheader for this loop, preheaders will always
 594          have atleast a label */
 595       preHdr->ech->next = icFirst;
 596       icFirst->prev = preHdr->ech;
 597       preHdr->ech = icLast;
 598       icLast->next = NULL;
 599
 600     }
 601   return change;
 602 }
 603
 604 /*-----------------------------------------------------------------*/
 605 /* addressTaken - returns true if the symbol is found in the addrof */
 606 /*-----------------------------------------------------------------*/
 607 int
 608 addressTaken (set * sset, operand * sym)
 609 {
 610   set *loop;
 611   eBBlock *ebp;
 612   set *loop2;
 613
 614   for (loop = sset; loop; loop = loop->next)
 615     {
 616       ebp = loop->item;
 617       loop2 = ebp->addrOf;
 618       while (loop2)
 619         {
 620           if (isOperandEqual ((operand *) loop2->item, sym))
 621             return 1;
 622           loop2 = loop2->next;
 623         }
 624     }
 625
 626   return 0;
 627 }
 628
 629
 630 /*-----------------------------------------------------------------*/
 631 /* findInduction :- returns 1 & the item if the induction is found */
 632 /*-----------------------------------------------------------------*/
 633 DEFSETFUNC (findInduction)
 634 {
 635   induction *ip = item;
 636   V_ARG (operand *, sym);
 637   V_ARG (induction **, ipp);
 638
 639   if (isOperandEqual (ip->sym, sym))
 640     {
 641       *ipp = ip;
 642       return 1;
 643     }
 644
 645   return 0;
 646 }
 647
 648 /*-----------------------------------------------------------------*/
 649 /* findDefInRegion - finds the definition within the region        */
 650 /*-----------------------------------------------------------------*/
 651 iCode *
 652 findDefInRegion (set * regBlocks, operand * defOp, eBBlock ** owner)
 653 {
 654   eBBlock *lBlock;
 655
 656   /* for all blocks in the region */
 657   for (lBlock = setFirstItem (regBlocks); lBlock;
 658        lBlock = setNextItem (regBlocks))
 659     {
 660
 661       /* if a definition for this exists */
 662       if (bitVectBitsInCommon (lBlock->defSet, OP_DEFS (defOp)))
 663         {
 664           iCode *ic;
 665
 666           /* go thru the instruction chain to find it */
 667           for (ic = lBlock->sch; ic; ic = ic->next)
 668             if (bitVectBitValue (OP_DEFS (defOp), ic->key))
 669               {
 670                 if (owner)
 671                   *owner = lBlock;
 672                 return ic;
 673               }
 674         }
 675     }
 676
 677   return NULL;
 678 }
 679
 680 /*-----------------------------------------------------------------*/
 681 /* basicInduction - finds the basic induction variables in a loop  */
 682 /*-----------------------------------------------------------------*/
 683 set *
 684 basicInduction (region * loopReg, eBBlock ** ebbs, int count)
 685 {
 686   eBBlock *lBlock;
 687   set *indVars = NULL;
 688
 689   /* i.e. all assignments of the form a := a +/- const */
 690   /* for all blocks within the loop do */
 691   for (lBlock = setFirstItem (loopReg->regBlocks); lBlock;
 692        lBlock = setNextItem (loopReg->regBlocks))
 693     {
 694
 695       iCode *ic, *dic;
 696
 697       /* for all instructions in the blocks do */
 698       for (ic = lBlock->sch; ic; ic = ic->next)
 699         {
 700
 701           operand *aSym;
 702           unsigned long litValue;
 703           induction *ip;
 704           iCode *indIc;
 705           eBBlock *owner = NULL;
 706           int nexits;
 707
 708           /* look for assignments of the form */
 709           /*   symbolVar := iTempNN */
 710           if (ic->op != '=')
 711             continue;
 712
 713           if (!IS_TRUE_SYMOP (IC_RESULT (ic)) &&
 714               !OP_SYMBOL (IC_RESULT (ic))->isreqv)
 715             continue;
 716
 717           if (isOperandGlobal (IC_RESULT (ic)))
 718             continue;
 719
 720           if (!IS_ITEMP (IC_RIGHT (ic)))
 721             continue;
 722
 723           /* if it has multiple assignments within the loop then skip */
 724           if (assignmentsToSym (loopReg->regBlocks, IC_RESULT (ic)) > 1)
 725             continue;
 726
 727           /* if the address of this was taken inside the loop then continue */
 728           if (addressTaken (loopReg->regBlocks, IC_RESULT (ic)))
 729             continue;
 730
 731           /* find the definition for the result in the block */
 732           if (!(dic = findDefInRegion (setFromSet (loopReg->regBlocks),
 733                                        IC_RIGHT (ic), &owner)))
 734             continue;
 735
 736           /* if not +/- continue */
 737           if (dic->op != '+' && dic->op != '-')
 738             continue;
 739
 740           /* make sure definition is of the form  a +/- c */
 741           if (!IS_OP_LITERAL (IC_LEFT (dic)) && !IS_OP_LITERAL (IC_RIGHT (dic)))
 742             continue;
 743
 744           aSym = (IS_OP_LITERAL (IC_RIGHT (dic)) ?
 745               (litValue = operandLitValue (IC_RIGHT (dic)), IC_LEFT (dic)) :
 746               (litValue = operandLitValue (IC_LEFT (dic)), IC_RIGHT (dic)));
 747
 748           if (!isOperandEqual (IC_RESULT (ic), aSym) &&
 749               !isOperandEqual (IC_RIGHT (ic), aSym))
 750             {
 751               iCode *ddic;
 752               /* find the definition for this and check */
 753               if (!(ddic = findDefInRegion (setFromSet (loopReg->regBlocks),
 754                                             aSym, &owner)))
 755                 continue;
 756
 757               if (ddic->op != '=')
 758                 continue;
 759
 760               if (!isOperandEqual (IC_RESULT (ddic), aSym) ||
 761                   !isOperandEqual (IC_RIGHT (ddic), IC_RESULT (ic)))
 762                 continue;
 763             }
 764
 765           /* if the right hand side has more than one usage then
 766              don't make it an induction (will have to think some more) */
 767           if (bitVectnBitsOn (OP_USES (IC_RIGHT (ic))) > 1)
 768             continue;
 769
 770           /* if the definition is volatile then it cannot be
 771              an induction object */
 772           if (isOperandVolatile (IC_RIGHT (ic), FALSE) ||
 773               isOperandVolatile (IC_RESULT (ic), FALSE))
 774             continue;
 775
 776           /* whew !! that was a lot of work to find the definition */
 777           /* create an induction object */
 778           indIc = newiCode ('=', NULL, IC_RESULT (ic));
 779           indIc->lineno = ic->lineno;
 780           IC_RESULT (indIc) = operandFromOperand (IC_RIGHT (ic));
 781           IC_RESULT (indIc)->isaddr = 0;
 782           OP_SYMBOL (IC_RESULT (indIc))->isind = 1;
 783           ip = newInduction (IC_RIGHT (ic), dic->op, litValue, indIc, NULL);
 784
 785           /* replace the inducted variable by the iTemp */
 786           replaceSymBySym (loopReg->regBlocks, IC_RESULT (ic), IC_RIGHT (ic));
 787
 788           /* if it has only one exit then remove it from here
 789              and put it in the exit block */
 790           nexits = elementsInSet (loopReg->exits);
 791           if (nexits == 1)
 792             {
 793               eBBlock *exit = setFirstItem (loopReg->exits);
 794
 795               /* if it is the same block then there is no
 796                  need to move it about */
 797               if (exit != lBlock)
 798                 {
 799                   iCode *saveic = ic->prev;
 800                   /* remove it */
 801                   remiCodeFromeBBlock (lBlock, ic);
 802                   /* clear the definition */
 803                   bitVectUnSetBit (lBlock->defSet, ic->key);
 804                   /* add it to the exit */
 805                   addiCodeToeBBlock (exit, ic, NULL);
 806                   /* set the definition bit */
 807                   exit->defSet = bitVectSetBit (exit->defSet, ic->key);
 808                   ic = saveic;
 809                 }
 810             }
 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
 816              and insert a new definition in them */
 817           if (nexits > 1)
 818             {
 819
 820               bitVect *loopSuccs = intersectLoopSucc (loopReg->exits, ebbs);
 821
 822               /* loopSuccs now contains intersection
 823                  of all the loops successors */
 824               if (loopSuccs)
 825                 {
 826                   int i;
 827                   for (i = 0; i < loopSuccs->size; i++)
 828                     {
 829                       if (bitVectBitValue (loopSuccs, i))
 830                         {
 831
 832                           eBBlock *eblock = ebbs[i];
 833
 834                           /* if the successor does not belong to the loop
 835                              and will be executed after the loop : then
 836                              add a definition to the block */
 837                           if (!isinSet (loopReg->regBlocks, eblock) &&
 838                               eblock->dfnum > loopReg->entry->dfnum)
 839                             {
 840                               /* create the definition */
 841                               iCode *newic = newiCode ('=', NULL,
 842                                         operandFromOperand (IC_RIGHT (ic)));
 843                               IC_RESULT (newic) = operandFromOperand (IC_RESULT (ic));
 844                               OP_DEFS (IC_RESULT (newic)) =
 845                                 bitVectSetBit (OP_DEFS (IC_RESULT (newic)), newic->key);
 846                               OP_USES (IC_RIGHT (newic)) =
 847                                 bitVectSetBit (OP_USES (IC_RIGHT (newic)), newic->key);
 848                               /* and add it */
 849                               if (eblock->sch && eblock->sch->op == LABEL)
 850                                 addiCodeToeBBlock (eblock, newic, eblock->sch->next);
 851                               else
 852                                 addiCodeToeBBlock (eblock, newic, eblock->sch);
 853                               /* set the definition bit */
 854                               eblock->defSet = bitVectSetBit (eblock->defSet, ic->key);
 855                             }
 856                         }
 857                     }
 858                 }
 859             }
 860
 861           addSet (&indVars, ip);
 862         }
 863
 864     }                           /* end of all blocks for basic induction variables */
 865
 866   return indVars;
 867 }
 868
 869 /*-----------------------------------------------------------------*/
 870 /* loopInduction - remove induction variables from a loop          */
 871 /*-----------------------------------------------------------------*/
 872 int
 873 loopInduction (region * loopReg, eBBlock ** ebbs, int count)
 874 {
 875   int change = 0;
 876   eBBlock *lBlock, *lastBlock = NULL;
 877   set *indVars = NULL;
 878   set *basicInd = NULL;
 879
 880   if (loopReg->entry->preHeader == NULL)
 881     return 0;
 882
 883   /* we first determine the basic Induction variables */
 884   basicInd = setFromSet (indVars = basicInduction (loopReg, ebbs, count));
 885
 886   /* find other induction variables : by other we mean definitions of */
 887   /* the form x := y (* | / ) <constant> .. we will move  this one to */
 888   /* beginning of the loop and reduce strength i.e. replace with +/-  */
 889   /* these expensive expressions: OH! and y must be induction too     */
 890   for (lBlock = setFirstItem (loopReg->regBlocks), lastBlock = lBlock;
 891        lBlock && indVars;
 892        lBlock = setNextItem (loopReg->regBlocks))
 893     {
 894
 895       iCode *ic, *indIc;
 896       induction *ip;
 897
 898       /* last block is the one with the highest block
 899          number */
 900       if (lastBlock->bbnum < lBlock->bbnum)
 901         lastBlock = lBlock;
 902
 903       for (ic = lBlock->sch; ic; ic = ic->next)
 904         {
 905           operand *aSym;
 906           unsigned long litVal;
 907           int lr = 0;
 908
 909           /* consider only * & / */
 910           if (ic->op != '*' && ic->op != '/')
 911             continue;
 912
 913           /* if the result has more definitions then */
 914           if (assignmentsToSym (loopReg->regBlocks, IC_RESULT (ic)) > 1)
 915             continue;
 916
 917           /* check if the operands are what we want */
 918           /* i.e. one of them an symbol the other a literal */
 919           if (!((IS_SYMOP (IC_LEFT (ic)) && IS_OP_LITERAL (IC_RIGHT (ic))) ||
 920                 (IS_OP_LITERAL (IC_LEFT (ic)) && IS_SYMOP (IC_RIGHT (ic)))))
 921             continue;
 922
 923           aSym = (IS_SYMOP (IC_LEFT (ic)) ?
 924           (lr = 1, litVal = operandLitValue (IC_RIGHT (ic)), IC_LEFT (ic)) :
 925                   (litVal = operandLitValue (IC_LEFT (ic)), IC_RIGHT (ic)));
 926
 927           ip = NULL;
 928           /* check if this is an induction variable */
 929           if (!applyToSetFTrue (basicInd, findInduction, aSym, &ip))
 930             continue;
 931
 932           /* ask port for size not worth if native instruction
 933              exist for multiply & divide */
 934           if (getSize (operandType (IC_LEFT (ic))) <= port->muldiv.native_below ||
 935           getSize (operandType (IC_RIGHT (ic))) <= port->muldiv.native_below)
 936             continue;
 937
 938           /* if this is a division then the remainder should be zero
 939              for it to be inducted */
 940           if (ic->op == '/' && (ip->cval % litVal))
 941             continue;
 942
 943           /* create the iCode to be placed in the loop header */
 944           /* and create the induction object */
 945
 946           /* create an instruction */
 947           /* this will be put on the loop header */
 948           indIc = newiCode (ic->op,
 949                             operandFromOperand (aSym),
 950                             operandFromLit (litVal));
 951           indIc->lineno = ic->lineno;
 952           IC_RESULT (indIc) = operandFromOperand (IC_RESULT (ic));
 953           OP_SYMBOL (IC_RESULT (indIc))->isind = 1;
 954
 955           /* keep track of the inductions */
 956           litVal = (ic->op == '*' ? (litVal * ip->cval) :
 957                     (ip->cval / litVal));
 958
 959           addSet (&indVars,
 960                 newInduction (IC_RESULT (ic), ip->op, litVal, indIc, NULL));
 961
 962           /* now change this instruction */
 963           ic->op = ip->op;
 964           if (lr)
 965             {
 966               IC_LEFT (ic) = operandFromOperand (IC_RESULT (ic));
 967               IC_RIGHT (ic) = operandFromLit (litVal);
 968             }
 969           else
 970             {
 971               IC_RIGHT (ic) = operandFromOperand (IC_RESULT (ic));
 972               IC_LEFT (ic) = operandFromLit (litVal);
 973             }
 974
 975           /* we need somemore initialisation code */
 976           /* we subtract the litVal from itself if increment */
 977           if (ic->op == '+')
 978             {
 979               indIc = newiCode ('-',
 980                                 operandFromOperand (IC_RESULT (ic)),
 981                                 operandFromLit (litVal));
 982               indIc->lineno = ic->lineno;
 983               IC_RESULT (indIc) = operandFromOperand (IC_RESULT (ic));
 984
 985               addSet (&indVars,
 986                 newInduction (IC_RESULT (ic), ip->op, litVal, indIc, NULL));
 987             }
 988         }
 989     }
 990
 991   /* if we have some induction variables then */
 992   if (indVars)
 993     {
 994       eBBlock *preHdr = loopReg->entry->preHeader;
 995       iCode *icFirst = NULL, *icLast = NULL;
 996       induction *ip;
 997       bitVect *indVect = NULL;
 998
 999       /* create an iCode chain from it */
1000       for (ip = setFirstItem (indVars);
1001            ip;
1002            ip = setNextItem (indVars))
1003         {
1004
1005           indVect = bitVectSetBit (indVect, ip->ic->key);
1006           ip->ic->lineno = preHdr->ech->lineno;
1007           if (!icFirst)
1008             icFirst = ip->ic;
1009           if (icLast)
1010             {
1011               icLast->next = ip->ic;
1012               ip->ic->prev = icLast;
1013               icLast = ip->ic;
1014             }
1015           else
1016             icLast = ip->ic;
1017           change++;
1018         }
1019
1020       /* add the instruction chain to the end of the */
1021       /* preheader for this loop                     */
1022       preHdr->ech->next = icFirst;
1023       icFirst->prev = preHdr->ech;
1024       preHdr->ech = icLast;
1025       icLast->next = NULL;
1026
1027       /* add the induction variable vector to the last
1028          block in the loop */
1029       lastBlock->isLastInLoop = 1;
1030       lastBlock->linds = indVect;
1031     }
1032
1033   setToNull ((void **) &indVars);
1034   return change;
1035 }
1036
1037 /*-----------------------------------------------------------------*/
1038 /* mergeRegions - will merge region with same entry point           */
1039 /*-----------------------------------------------------------------*/
1040 DEFSETFUNC (mergeRegions)
1041 {
1042   region *theLoop = item;
1043   V_ARG (set *, allRegion);
1044   region *lp;
1045
1046   /* if this has already been merged then do nothing */
1047   if (theLoop->merged)
1048     return 0;
1049
1050   /* go thru all the region and check if any of them have the */
1051   /* entryPoint as the Loop                                  */
1052   for (lp = setFirstItem (allRegion); lp; lp = setNextItem (allRegion))
1053     {
1054
1055       if (lp == theLoop)
1056         continue;
1057
1058       if (lp->entry == theLoop->entry)
1059         {
1060           theLoop->regBlocks = unionSets (theLoop->regBlocks,
1061                                           lp->regBlocks, THROW_BOTH);
1062           lp->merged = 1;
1063         }
1064     }
1065
1066   return 1;
1067 }
1068
1069 /*-----------------------------------------------------------------*/
1070 /* ifMerged - return 1 if the merge flag is 1                      */
1071 /*-----------------------------------------------------------------*/
1072 DEFSETFUNC (ifMerged)
1073 {
1074   region *lp = item;
1075
1076   return lp->merged;
1077 }
1078
1079 /*-----------------------------------------------------------------*/
1080 /* mergeInnerLoops - will merge into body when entry is present    */
1081 /*-----------------------------------------------------------------*/
1082 DEFSETFUNC (mergeInnerLoops)
1083 {
1084   region *theLoop = item;
1085   V_ARG (set *, allRegion);
1086   V_ARG (int *, maxDepth);
1087   region *lp;
1088
1089   /* check if the entry point is present in the body of any */
1090   /* loop then put the body of this loop into the outer loop */
1091   for (lp = setFirstItem (allRegion); lp; lp = setNextItem (allRegion))
1092     {
1093
1094       if (lp == theLoop)
1095         continue;
1096
1097       if (isinSet (lp->regBlocks, theLoop->entry))
1098         {
1099           lp->containsLoops += theLoop->containsLoops + 1;
1100           if (lp->containsLoops > (*maxDepth))
1101             *maxDepth = lp->containsLoops;
1102
1103           lp->regBlocks = unionSets (lp->regBlocks,
1104                                      theLoop->regBlocks, THROW_DEST);
1105         }
1106     }
1107
1108   return 1;
1109 }
1110
1111
1112 /*-----------------------------------------------------------------*/
1113 /* createLoopRegions - will detect and create a set of natural loops */
1114 /*-----------------------------------------------------------------*/
1115 hTab *
1116 createLoopRegions (eBBlock ** ebbs, int count)
1117 {
1118   set *allRegion = NULL;        /* set of all loops */
1119   hTab *orderedLoops = NULL;
1120   set *bEdges = NULL;
1121   int maxDepth = 0;
1122   region *lp;
1123
1124   /* get all the back edges in the graph */
1125   if (!applyToSet (graphEdges, backEdges, &bEdges))
1126     return 0;                   /* found no loops */
1127
1128   /* for each of these back edges get the blocks that */
1129   /* constitute the loops                             */
1130   applyToSet (bEdges, createLoop, &allRegion);
1131
1132   /* now we will create regions from these loops               */
1133   /* loops with the same entry points are considered to be the */
1134   /* same loop & they are merged. If the entry point of a loop */
1135   /* is found in the body of another loop then , all the blocks */
1136   /* in that loop are added to the loops containing the header */
1137   applyToSet (allRegion, mergeRegions, allRegion);
1138
1139   /* delete those already merged */
1140   deleteItemIf (&allRegion, ifMerged);
1141
1142   applyToSet (allRegion, mergeInnerLoops, allRegion, &maxDepth);
1143   maxDepth++;
1144   /* now create all the exits .. also */
1145   /* create an ordered set of loops   */
1146   /* i.e. we process loops in the inner to outer order */
1147   for (lp = setFirstItem (allRegion); lp; lp = setNextItem (allRegion))
1148     {
1149       applyToSet (lp->regBlocks, addToExitsMarkDepth,
1150                   lp->regBlocks, &lp->exits,
1151                   (maxDepth - lp->containsLoops), lp);
1152
1153       hTabAddItem (&orderedLoops, lp->containsLoops, lp);
1154
1155     }
1156   return orderedLoops;
1157 }
1158
1159 /*-----------------------------------------------------------------*/
1160 /* loopOptimizations - identify region & remove invariants & ind   */
1161 /*-----------------------------------------------------------------*/
1162 int
1163 loopOptimizations (hTab * orderedLoops, eBBlock ** ebbs, int count)
1164 {
1165   region *lp;
1166   int change = 0;
1167   int k;
1168
1169   /* if no loop optimizations requested */
1170   if (!optimize.loopInvariant &&
1171       !optimize.loopInduction)
1172     return 0;
1173
1174   /* now we process the loops inner to outer order */
1175   /* this is essential to maintain data flow information */
1176   /* the other choice is an ugly iteration for the depth */
1177   /* of the loops would hate that */
1178   for (lp = hTabFirstItem (orderedLoops, &k); lp;
1179        lp = hTabNextItem (orderedLoops, &k))
1180     {
1181
1182       if (optimize.loopInvariant)
1183         change += loopInvariants (lp, ebbs, count);
1184
1185       if (optimize.loopInduction)
1186         change += loopInduction (lp, ebbs, count);
1187     }
1188
1189   return change;
1190 }