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