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

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