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