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

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