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

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