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