git.gag.com Git - fw/sdcc/blob - src/SDCCloop.c

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