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

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