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