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   if (getenv ("SDCC_LRKLAUS"))
 239     {
 240       /* put the loop region info in the block */
 241       if (!isinSet (ebp->KpartOfLoop, lr))
 242         addSetHead (&ebp->KpartOfLoop, lr);
 243     }
 244   else
 245     {
 246       /* NOTE: here we will update only the inner most loop
 247          that it is a part of */
 248       if (!ebp->partOfLoop)
 249         ebp->partOfLoop = lr;
 250     }
 251
 252   /* if any of the successors go out of the loop then */
 253   /* we add this one to the exits */
 254   if (applyToSet (ebp->succList, isNotInBlocks, loopBlocks))
 255     {
 256       addSetHead (exits, ebp);
 257       return 1;
 258     }
 259
 260   return 0;
 261 }
 262
 263 /*-----------------------------------------------------------------*/
 264 /* createLoop - will create a set of region                        */
 265 /*-----------------------------------------------------------------*/
 266 DEFSETFUNC (createLoop)
 267 {
 268   edge *ep = item;
 269   V_ARG (set **, allRegion);
 270   region *aloop = newRegion ();
 271   eBBlock *block;
 272
 273   /* make sure regionStack is empty */
 274   while (!STACK_EMPTY (regionStack))
 275     STACK_POP (regionStack);
 276
 277   /* add the entryBlock */
 278   addSet (&aloop->regBlocks, ep->to);
 279   loopInsert (&aloop->regBlocks, ep->from);
 280
 281   while (!STACK_EMPTY (regionStack))
 282     {
 283       block = STACK_POP (regionStack);
 284       /* if block != entry */
 285       if (block != ep->to)
 286         applyToSet (block->predList, insertIntoLoop, &aloop->regBlocks);
 287     }
 288
 289   aloop->entry = ep->to;
 290
 291   /* now add it to the set */
 292   addSetHead (allRegion, aloop);
 293   return 0;
 294 }
 295
 296 /*-----------------------------------------------------------------*/
 297 /* dominatedBy - will return 1 if item is dominated by block       */
 298 /*-----------------------------------------------------------------*/
 299 DEFSETFUNC (dominatedBy)
 300 {
 301   eBBlock *ebp = item;
 302   V_ARG (eBBlock *, block);
 303
 304   return bitVectBitValue (ebp->domVect, block->bbnum);
 305 }
 306
 307 /*-----------------------------------------------------------------*/
 308 /* addDefInExprs - adds an expression into the inexpressions       */
 309 /*-----------------------------------------------------------------*/
 310 DEFSETFUNC (addDefInExprs)
 311 {
 312   eBBlock *ebp = item;
 313   V_ARG (cseDef *, cdp);
 314   V_ARG (eBBlock **, ebbs);
 315   V_ARG (int, count);
 316
 317   addSetHead (&ebp->inExprs, cdp);
 318   cseBBlock (ebp, optimize.global_cse, ebbs, count);
 319   return 0;
 320 }
 321
 322 /*-----------------------------------------------------------------*/
 323 /* assignmentsToSym - for a set of blocks determine # time assigned */
 324 /*-----------------------------------------------------------------*/
 325 int
 326 assignmentsToSym (set * sset, operand * sym)
 327 {
 328   eBBlock *ebp;
 329   int assigns = 0;
 330   set *blocks = setFromSet (sset);
 331
 332   for (ebp = setFirstItem (blocks); ebp;
 333        ebp = setNextItem (blocks))
 334     {
 335
 336       /* get all the definitions for this symbol
 337          in this block */
 338       bitVect *defs = bitVectIntersect (ebp->ldefs, OP_DEFS (sym));
 339       assigns += bitVectnBitsOn (defs);
 340       setToNull ((void *) &defs);
 341
 342     }
 343
 344   return assigns;
 345 }
 346
 347
 348 /*-----------------------------------------------------------------*/
 349 /* isOperandInvariant - determines if an operand is an invariant   */
 350 /*-----------------------------------------------------------------*/
 351 int
 352 isOperandInvariant (operand * op, region * theLoop, set * lInvars)
 353 {
 354   int opin = 0;
 355   /* operand is an invariant if it is a                */
 356   /*       a. constants .                              */
 357   /*       b. that have defintions reaching loop entry */
 358   /*       c. that are already defined as invariant    */
 359   /*       d. has no assignments in the loop           */
 360   if (op)
 361     {
 362       if (IS_OP_LITERAL (op))
 363         opin = 1;
 364       else if (IS_SYMOP (op) &&
 365                OP_SYMBOL (op)->addrtaken)
 366         opin = 0;
 367       else if (ifDefSymIs (theLoop->entry->inExprs, op))
 368         opin = 1;
 369       else if (ifDefSymIs (lInvars, op))
 370         opin = 1;
 371       else if (IS_SYMOP (op) &&
 372                !IS_OP_GLOBAL (op) &&
 373                !IS_OP_VOLATILE (op) &&
 374                assignmentsToSym (theLoop->regBlocks, op) == 0)
 375         opin = 1;
 376     }
 377   else
 378     opin++;
 379
 380   return opin;
 381 }
 382
 383 /*-----------------------------------------------------------------*/
 384 /* pointerAssigned - will return 1 if pointer set found            */
 385 /*-----------------------------------------------------------------*/
 386 DEFSETFUNC (pointerAssigned)
 387 {
 388   eBBlock *ebp = item;
 389   V_ARG (operand *, op);
 390
 391   return ebp->hasFcall || bitVectBitValue (ebp->ptrsSet, op->key);
 392 }
 393
 394 /*-----------------------------------------------------------------*/
 395 /* hasNonPtrUse - returns true if operand has non pointer usage    */
 396 /*-----------------------------------------------------------------*/
 397 DEFSETFUNC (hasNonPtrUse)
 398 {
 399   eBBlock *ebp = item;
 400   V_ARG (operand *, op);
 401   iCode *ic = usedInRemaining (op, ebp->sch);
 402
 403   if (ic && !POINTER_SET (ic) && !POINTER_GET (ic))
 404     return 1;
 405
 406   return 0;
 407
 408 }
 409
 410 /*-----------------------------------------------------------------*/
 411 /* loopInvariants - takes loop invariants out of region            */
 412 /*-----------------------------------------------------------------*/
 413 int
 414 loopInvariants (region * theLoop, eBBlock ** ebbs, int count)
 415 {
 416   eBBlock *lBlock;
 417   set *lInvars = NULL;
 418
 419   int change = 0;
 420   int fCallsInBlock;
 421
 422   /* if the preHeader does not exist then do nothing */
 423   /* or no exits then do nothing ( have to think about this situation */
 424   if (theLoop->entry->preHeader == NULL ||
 425       theLoop->exits == NULL)
 426     return 0;
 427
 428   /* we will do the elimination for those blocks        */
 429   /* in the loop that dominates all exits from the loop */
 430   for (lBlock = setFirstItem (theLoop->regBlocks); lBlock;
 431        lBlock = setNextItem (theLoop->regBlocks))
 432     {
 433
 434       iCode *ic;
 435       int domsAllExits;
 436       int i;
 437
 438       /* mark the dominates all exits flag */
 439       domsAllExits = (applyToSet (theLoop->exits, dominatedBy, lBlock) ==
 440                       elementsInSet (theLoop->exits));
 441
 442       /* find out if we have a function call in this block */
 443       for (ic = lBlock->sch, fCallsInBlock=0; ic; ic = ic->next) {
 444         if (SKIP_IC(ic)) {
 445           fCallsInBlock++;
 446         }
 447       }
 448
 449       /* now we go thru the instructions of this block and */
 450       /* collect those instructions with invariant operands */
 451       for (ic = lBlock->sch; ic; ic = ic->next)
 452         {
 453
 454           int lin, rin;
 455           cseDef *ivar;
 456
 457           /* TODO this is only needed if the call is between
 458              here and the definition, but I am too lazy to do that now */
 459
 460           /* if there are function calls in this block */
 461           if (fCallsInBlock) {
 462
 463             /* if this is a pointer get */
 464             if (POINTER_GET(ic)) {
 465               continue;
 466             }
 467
 468             /* if this is an assignment from a global */
 469             if (ic->op=='=' && isOperandGlobal(IC_RIGHT(ic))) {
 470               continue;
 471             }
 472           }
 473
 474           if (SKIP_IC (ic) || POINTER_SET (ic) || ic->op == IFX)
 475             continue;
 476
 477           /* if result is volatile then skip */
 478           if (IC_RESULT (ic) &&
 479               (isOperandVolatile (IC_RESULT (ic), TRUE) ||
 480                IS_OP_PARM (IC_RESULT (ic))))
 481             continue;
 482
 483           /* if result depends on a volatile then skip */
 484           if ((IC_LEFT(ic) && isOperandVolatile(IC_LEFT(ic), TRUE)) ||
 485               (IC_RIGHT(ic) && isOperandVolatile(IC_RIGHT(ic), TRUE)))
 486             continue;
 487
 488           lin = rin = 0;
 489
 490           /* special case */
 491           /* if address of then it is an invariant */
 492           if (ic->op == ADDRESS_OF &&
 493               IS_SYMOP (IC_LEFT (ic)) &&
 494               IS_AGGREGATE (operandType (IC_LEFT (ic))))
 495             lin++;
 496           else {
 497             /* check if left operand is an invariant */
 498             if ((lin = isOperandInvariant (IC_LEFT (ic), theLoop, lInvars)))
 499               /* if this is a pointer get then make sure
 500                  that the pointer set does not exist in
 501                  any of the blocks */
 502               if (POINTER_GET (ic) &&
 503                   (applyToSet (theLoop->regBlocks,
 504                                pointerAssigned, IC_LEFT (ic))))
 505                 lin = 0;
 506           }
 507
 508           /* do the same for right */
 509           rin = isOperandInvariant (IC_RIGHT (ic), theLoop, lInvars);
 510
 511           /* if this is a POINTER_GET then special case, make sure all
 512              usages within the loop are POINTER_GET any other usage
 513              would mean that this is not an invariant , since the pointer
 514              could then be passed as a parameter */
 515           if (POINTER_GET (ic) &&
 516               applyToSet (theLoop->regBlocks, hasNonPtrUse, IC_LEFT (ic)))
 517             continue;
 518
 519           /* if both the left & right are invariants : then check that */
 520           /* this definition exists in the out definition of all the  */
 521           /* blocks, this will ensure that this is not assigned any   */
 522           /* other value in the loop , and not used in this block     */
 523           /* prior to this definition which means only this definition */
 524           /* is used in this loop                                     */
 525           if (lin && rin && IC_RESULT (ic))
 526             {
 527               eBBlock *sBlock;
 528               set *lSet = setFromSet (theLoop->regBlocks);
 529
 530               /* if this block does not dominate all exists */
 531               /* make sure this defintion is not used anywhere else */
 532               if (!domsAllExits)
 533                 {
 534
 535                   if (isOperandGlobal (IC_RESULT (ic)))
 536                     continue;
 537                   /* for successors for all exits */
 538                   for (sBlock = setFirstItem (theLoop->exits); sBlock;
 539                        sBlock = setNextItem (theLoop->exits))
 540                     {
 541
 542                       for (i = 0; i < count; ebbs[i++]->visited = 0);
 543                       lBlock->visited = 1;
 544                       if (applyToSet (sBlock->succList, isDefAlive, ic))
 545                         break;
 546                     }
 547
 548                   /* we have found usage */
 549                   if (sBlock)
 550                     continue;
 551                 }
 552
 553               /* now make sure this is the only definition */
 554               for (sBlock = setFirstItem (lSet); sBlock;
 555                    sBlock = setNextItem (lSet))
 556                 {
 557                   /* if this is the block make sure the definition */
 558                   /* reaches the end of the block */
 559                   if (sBlock == lBlock)
 560                     {
 561                       if (!ifDiCodeIs (sBlock->outExprs, ic))
 562                         break;
 563                     }
 564                   else if (bitVectBitsInCommon (sBlock->defSet, OP_DEFS (IC_RESULT (ic))))
 565                     break;
 566                 }
 567
 568               if (sBlock)
 569                 continue;       /* another definition present in the block */
 570
 571               /* now check if it exists in the in of this block */
 572               /* if not then it was killed before this instruction */
 573               if (!bitVectBitValue (lBlock->inDefs, ic->key))
 574                 continue;
 575
 576               /* now we know it is a true invariant */
 577               /* remove it from the insts chain & put */
 578               /* in the invariant set                */
 579               OP_SYMBOL (IC_RESULT (ic))->isinvariant = 1;
 580               remiCodeFromeBBlock (lBlock, ic);
 581
 582               /* maintain the data flow */
 583               /* this means removing from definition from the */
 584               /* defset of this block and adding it to the    */
 585               /* inexpressions of all blocks within the loop  */
 586               bitVectUnSetBit (lBlock->defSet, ic->key);
 587               bitVectUnSetBit (lBlock->ldefs, ic->key);
 588               ivar = newCseDef (IC_RESULT (ic), ic);
 589               applyToSet (theLoop->regBlocks, addDefInExprs, ivar, ebbs, count);
 590               addSet (&lInvars, ivar);
 591             }
 592         }
 593     }                           /* for all loop blocks */
 594
 595   /* if we have some invariants then */
 596   if (lInvars)
 597     {
 598       eBBlock *preHdr = theLoop->entry->preHeader;
 599       iCode *icFirst = NULL, *icLast = NULL;
 600       cseDef *cdp;
 601
 602       /* create an iCode chain from it */
 603       for (cdp = setFirstItem (lInvars); cdp; cdp = setNextItem (lInvars))
 604         {
 605
 606           /* maintain data flow .. add it to the */
 607           /* ldefs defSet & outExprs of the preheader  */
 608           preHdr->defSet = bitVectSetBit (preHdr->defSet, cdp->diCode->key);
 609           preHdr->ldefs = bitVectSetBit (preHdr->ldefs, cdp->diCode->key);
 610           cdp->diCode->lineno = preHdr->ech->lineno;
 611           addSetHead (&preHdr->outExprs, cdp);
 612
 613
 614           if (!icFirst)
 615             icFirst = cdp->diCode;
 616           if (icLast)
 617             {
 618               icLast->next = cdp->diCode;
 619               cdp->diCode->prev = icLast;
 620               icLast = cdp->diCode;
 621             }
 622           else
 623             icLast = cdp->diCode;
 624           change++;
 625         }
 626
 627       /* add the instruction chain to the end of the
 628          preheader for this loop, preheaders will always
 629          have atleast a label */
 630       preHdr->ech->next = icFirst;
 631       icFirst->prev = preHdr->ech;
 632       preHdr->ech = icLast;
 633       icLast->next = NULL;
 634
 635     }
 636   return change;
 637 }
 638
 639 /*-----------------------------------------------------------------*/
 640 /* addressTaken - returns true if the symbol is found in the addrof */
 641 /*-----------------------------------------------------------------*/
 642 int
 643 addressTaken (set * sset, operand * sym)
 644 {
 645   set *loop;
 646   eBBlock *ebp;
 647   set *loop2;
 648
 649   for (loop = sset; loop; loop = loop->next)
 650     {
 651       ebp = loop->item;
 652       loop2 = ebp->addrOf;
 653       while (loop2)
 654         {
 655           if (isOperandEqual ((operand *) loop2->item, sym))
 656             return 1;
 657           loop2 = loop2->next;
 658         }
 659     }
 660
 661   return 0;
 662 }
 663
 664
 665 /*-----------------------------------------------------------------*/
 666 /* findInduction :- returns 1 & the item if the induction is found */
 667 /*-----------------------------------------------------------------*/
 668 DEFSETFUNC (findInduction)
 669 {
 670   induction *ip = item;
 671   V_ARG (operand *, sym);
 672   V_ARG (induction **, ipp);
 673
 674   if (isOperandEqual (ip->sym, sym))
 675     {
 676       *ipp = ip;
 677       return 1;
 678     }
 679
 680   return 0;
 681 }
 682
 683 /*-----------------------------------------------------------------*/
 684 /* findDefInRegion - finds the definition within the region        */
 685 /*-----------------------------------------------------------------*/
 686 iCode *
 687 findDefInRegion (set * regBlocks, operand * defOp, eBBlock ** owner)
 688 {
 689   eBBlock *lBlock;
 690
 691   /* for all blocks in the region */
 692   for (lBlock = setFirstItem (regBlocks); lBlock;
 693        lBlock = setNextItem (regBlocks))
 694     {
 695
 696       /* if a definition for this exists */
 697       if (bitVectBitsInCommon (lBlock->defSet, OP_DEFS (defOp)))
 698         {
 699           iCode *ic;
 700
 701           /* go thru the instruction chain to find it */
 702           for (ic = lBlock->sch; ic; ic = ic->next)
 703             if (bitVectBitValue (OP_DEFS (defOp), ic->key))
 704               {
 705                 if (owner)
 706                   *owner = lBlock;
 707                 return ic;
 708               }
 709         }
 710     }
 711
 712   return NULL;
 713 }
 714
 715 /*-----------------------------------------------------------------*/
 716 /* basicInduction - finds the basic induction variables in a loop  */
 717 /*-----------------------------------------------------------------*/
 718 set *
 719 basicInduction (region * loopReg, eBBlock ** ebbs, int count)
 720 {
 721   eBBlock *lBlock;
 722   set *indVars = NULL;
 723
 724   /* i.e. all assignments of the form a := a +/- const */
 725   /* for all blocks within the loop do */
 726   for (lBlock = setFirstItem (loopReg->regBlocks); lBlock;
 727        lBlock = setNextItem (loopReg->regBlocks))
 728     {
 729
 730       iCode *ic, *dic;
 731
 732       /* for all instructions in the blocks do */
 733       for (ic = lBlock->sch; ic; ic = ic->next)
 734         {
 735
 736           operand *aSym;
 737           unsigned long litValue;
 738           induction *ip;
 739           iCode *indIc;
 740           eBBlock *owner = NULL;
 741           int nexits;
 742
 743           /* look for assignments of the form */
 744           /*   symbolVar := iTempNN */
 745           if (ic->op != '=')
 746             continue;
 747
 748           if (!IS_TRUE_SYMOP (IC_RESULT (ic)) &&
 749               !OP_SYMBOL (IC_RESULT (ic))->isreqv)
 750             continue;
 751
 752           if (isOperandGlobal (IC_RESULT (ic)))
 753             continue;
 754
 755           if (!IS_ITEMP (IC_RIGHT (ic)))
 756             continue;
 757
 758           /* if it has multiple assignments within the loop then skip */
 759           if (assignmentsToSym (loopReg->regBlocks, IC_RESULT (ic)) > 1)
 760             continue;
 761
 762           /* if the address of this was taken inside the loop then continue */
 763           if (addressTaken (loopReg->regBlocks, IC_RESULT (ic)))
 764             continue;
 765
 766           /* find the definition for the result in the block */
 767           if (!(dic = findDefInRegion (setFromSet (loopReg->regBlocks),
 768                                        IC_RIGHT (ic), &owner)))
 769             continue;
 770
 771           /* if not +/- continue */
 772           if (dic->op != '+' && dic->op != '-')
 773             continue;
 774
 775           /* make sure definition is of the form  a +/- c */
 776           if (!IS_OP_LITERAL (IC_LEFT (dic)) && !IS_OP_LITERAL (IC_RIGHT (dic)))
 777             continue;
 778
 779           aSym = (IS_OP_LITERAL (IC_RIGHT (dic)) ?
 780               (litValue = (unsigned long) operandLitValue (IC_RIGHT (dic)), IC_LEFT (dic)) :
 781               (litValue = (unsigned long) operandLitValue (IC_LEFT (dic)), IC_RIGHT (dic)));
 782
 783           if (!isOperandEqual (IC_RESULT (ic), aSym) &&
 784               !isOperandEqual (IC_RIGHT (ic), aSym))
 785             {
 786               iCode *ddic;
 787               /* find the definition for this and check */
 788               if (!(ddic = findDefInRegion (setFromSet (loopReg->regBlocks),
 789                                             aSym, &owner)))
 790                 continue;
 791
 792               if (ddic->op != '=')
 793                 continue;
 794
 795               if (!isOperandEqual (IC_RESULT (ddic), aSym) ||
 796                   !isOperandEqual (IC_RIGHT (ddic), IC_RESULT (ic)))
 797                 continue;
 798             }
 799
 800           /* if the right hand side has more than one usage then
 801              don't make it an induction (will have to think some more) */
 802           if (bitVectnBitsOn (OP_USES (IC_RIGHT (ic))) > 1)
 803             continue;
 804
 805           /* if the definition is volatile then it cannot be
 806              an induction object */
 807           if (isOperandVolatile (IC_RIGHT (ic), FALSE) ||
 808               isOperandVolatile (IC_RESULT (ic), FALSE))
 809             continue;
 810
 811           /* whew !! that was a lot of work to find the definition */
 812           /* create an induction object */
 813           indIc = newiCode ('=', NULL, IC_RESULT (ic));
 814           indIc->lineno = ic->lineno;
 815           IC_RESULT (indIc) = operandFromOperand (IC_RIGHT (ic));
 816           IC_RESULT (indIc)->isaddr = 0;
 817           OP_SYMBOL (IC_RESULT (indIc))->isind = 1;
 818           ip = newInduction (IC_RIGHT (ic), dic->op, litValue, indIc, NULL);
 819
 820           /* replace the inducted variable by the iTemp */
 821           replaceSymBySym (loopReg->regBlocks, IC_RESULT (ic), IC_RIGHT (ic));
 822
 823           /* if it has only one exit then remove it from here
 824              and put it in the exit block */
 825           nexits = elementsInSet (loopReg->exits);
 826           if (nexits == 1)
 827             {
 828               eBBlock *exit = setFirstItem (loopReg->exits);
 829
 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 = ebbs[i];
 868
 869                           /* if the successor does not belong to the loop
 870                              and will be executed after the loop : then
 871                              add a definition to the block */
 872                           if (!isinSet (loopReg->regBlocks, eblock) &&
 873                               eblock->dfnum > loopReg->entry->dfnum)
 874                             {
 875                               /* create the definition */
 876                               iCode *newic = newiCode ('=', NULL,
 877                                         operandFromOperand (IC_RIGHT (ic)));
 878                               IC_RESULT (newic) = operandFromOperand (IC_RESULT (ic));
 879                               OP_DEFS(IC_RESULT (newic))=
 880                                 bitVectSetBit (OP_DEFS (IC_RESULT (newic)), newic->key);
 881                               OP_USES(IC_RIGHT (newic))=
 882                                 bitVectSetBit (OP_USES (IC_RIGHT (newic)), newic->key);
 883                               /* and add it */
 884                               if (eblock->sch && eblock->sch->op == LABEL)
 885                                 addiCodeToeBBlock (eblock, newic, eblock->sch->next);
 886                               else
 887                                 addiCodeToeBBlock (eblock, newic, eblock->sch);
 888                               /* set the definition bit */
 889                               eblock->defSet = bitVectSetBit (eblock->defSet, ic->key);
 890                             }
 891                         }
 892                     }
 893                 }
 894             }
 895
 896           addSet (&indVars, ip);
 897         }
 898
 899     }                           /* end of all blocks for basic induction variables */
 900
 901   return indVars;
 902 }
 903
 904 /*-----------------------------------------------------------------*/
 905 /* loopInduction - remove induction variables from a loop          */
 906 /*-----------------------------------------------------------------*/
 907 int
 908 loopInduction (region * loopReg, eBBlock ** ebbs, int count)
 909 {
 910   int change = 0;
 911   eBBlock *lBlock, *lastBlock = NULL;
 912   set *indVars = NULL;
 913   set *basicInd = NULL;
 914
 915   if (loopReg->entry->preHeader == NULL)
 916     return 0;
 917
 918   /* we first determine the basic Induction variables */
 919   basicInd = setFromSet (indVars = basicInduction (loopReg, ebbs, count));
 920
 921   /* find other induction variables : by other we mean definitions of */
 922   /* the form x := y (* | / ) <constant> .. we will move  this one to */
 923   /* beginning of the loop and reduce strength i.e. replace with +/-  */
 924   /* these expensive expressions: OH! and y must be induction too     */
 925   for (lBlock = setFirstItem (loopReg->regBlocks), lastBlock = lBlock;
 926        lBlock && indVars;
 927        lBlock = setNextItem (loopReg->regBlocks))
 928     {
 929
 930       iCode *ic, *indIc;
 931       induction *ip;
 932
 933       /* last block is the one with the highest block
 934          number */
 935       if (lastBlock->bbnum < lBlock->bbnum)
 936         lastBlock = lBlock;
 937
 938       for (ic = lBlock->sch; ic; ic = ic->next)
 939         {
 940           operand *aSym;
 941           unsigned long litVal;
 942           int lr = 0;
 943
 944           /* consider only * & / */
 945           if (ic->op != '*' && ic->op != '/')
 946             continue;
 947
 948           /* if the result has more definitions then */
 949           if (assignmentsToSym (loopReg->regBlocks, IC_RESULT (ic)) > 1)
 950             continue;
 951
 952           /* check if the operands are what we want */
 953           /* i.e. one of them an symbol the other a literal */
 954           if (!((IS_SYMOP (IC_LEFT (ic)) && IS_OP_LITERAL (IC_RIGHT (ic))) ||
 955                 (IS_OP_LITERAL (IC_LEFT (ic)) && IS_SYMOP (IC_RIGHT (ic)))))
 956             continue;
 957
 958           aSym = (IS_SYMOP (IC_LEFT (ic)) ?
 959           (lr = 1, litVal = (unsigned long) operandLitValue (IC_RIGHT (ic)), IC_LEFT (ic)) :
 960                   (litVal = (unsigned long) operandLitValue (IC_LEFT (ic)), IC_RIGHT (ic)));
 961
 962           ip = NULL;
 963           /* check if this is an induction variable */
 964           if (!applyToSetFTrue (basicInd, findInduction, aSym, &ip))
 965             continue;
 966
 967           /* ask port for size not worth if native instruction
 968              exist for multiply & divide */
 969           if (getSize (operandType (IC_LEFT (ic))) <= (unsigned long) port->support.muldiv ||
 970           getSize (operandType (IC_RIGHT (ic))) <= (unsigned long) port->support.muldiv)
 971             continue;
 972
 973           /* if this is a division then the remainder should be zero
 974              for it to be inducted */
 975           if (ic->op == '/' && (ip->cval % litVal))
 976             continue;
 977
 978           /* create the iCode to be placed in the loop header */
 979           /* and create the induction object */
 980
 981           /* create an instruction */
 982           /* this will be put on the loop header */
 983           indIc = newiCode (ic->op,
 984                             operandFromOperand (aSym),
 985                             operandFromLit (litVal));
 986           indIc->lineno = ic->lineno;
 987           IC_RESULT (indIc) = operandFromOperand (IC_RESULT (ic));
 988           OP_SYMBOL (IC_RESULT (indIc))->isind = 1;
 989
 990           /* keep track of the inductions */
 991           litVal = (ic->op == '*' ? (litVal * ip->cval) :
 992                     (ip->cval / litVal));
 993
 994           addSet (&indVars,
 995                 newInduction (IC_RESULT (ic), ip->op, litVal, indIc, NULL));
 996
 997           /* now change this instruction */
 998           ic->op = ip->op;
 999           if (lr)
1000             {
1001               IC_LEFT (ic) = operandFromOperand (IC_RESULT (ic));
1002               IC_RIGHT (ic) = operandFromLit (litVal);
1003             }
1004           else
1005             {
1006               IC_RIGHT (ic) = operandFromOperand (IC_RESULT (ic));
1007               IC_LEFT (ic) = operandFromLit (litVal);
1008             }
1009
1010           /* we need somemore initialisation code */
1011           /* we subtract the litVal from itself if increment */
1012           if (ic->op == '+')
1013             {
1014               indIc = newiCode ('-',
1015                                 operandFromOperand (IC_RESULT (ic)),
1016                                 operandFromLit (litVal));
1017               indIc->lineno = ic->lineno;
1018               IC_RESULT (indIc) = operandFromOperand (IC_RESULT (ic));
1019
1020               addSet (&indVars,
1021                 newInduction (IC_RESULT (ic), ip->op, litVal, indIc, NULL));
1022             }
1023         }
1024     }
1025
1026   /* if we have some induction variables then */
1027   if (indVars)
1028     {
1029       eBBlock *preHdr = loopReg->entry->preHeader;
1030       iCode *icFirst = NULL, *icLast = NULL;
1031       induction *ip;
1032       bitVect *indVect = NULL;
1033
1034       /* create an iCode chain from it */
1035       for (ip = setFirstItem (indVars);
1036            ip;
1037            ip = setNextItem (indVars))
1038         {
1039
1040           indVect = bitVectSetBit (indVect, ip->ic->key);
1041           ip->ic->lineno = preHdr->ech->lineno;
1042           if (!icFirst)
1043             icFirst = ip->ic;
1044           if (icLast)
1045             {
1046               icLast->next = ip->ic;
1047               ip->ic->prev = icLast;
1048               icLast = ip->ic;
1049             }
1050           else
1051             icLast = ip->ic;
1052           change++;
1053         }
1054
1055       /* add the instruction chain to the end of the */
1056       /* preheader for this loop                     */
1057       preHdr->ech->next = icFirst;
1058       icFirst->prev = preHdr->ech;
1059       preHdr->ech = icLast;
1060       icLast->next = NULL;
1061
1062       /* add the induction variable vector to the last
1063          block in the loop */
1064       lastBlock->isLastInLoop = 1;
1065       lastBlock->linds = bitVectUnion(lastBlock->linds,indVect);
1066     }
1067
1068   setToNull ((void *) &indVars);
1069   return change;
1070 }
1071
1072 /*-----------------------------------------------------------------*/
1073 /* mergeRegions - will merge region with same entry point           */
1074 /*-----------------------------------------------------------------*/
1075 DEFSETFUNC (mergeRegions)
1076 {
1077   region *theLoop = item;
1078   V_ARG (set *, allRegion);
1079   region *lp;
1080
1081   /* if this has already been merged then do nothing */
1082   if (theLoop->merged)
1083     return 0;
1084
1085   /* go thru all the region and check if any of them have the */
1086   /* entryPoint as the Loop                                  */
1087   for (lp = setFirstItem (allRegion); lp; lp = setNextItem (allRegion))
1088     {
1089
1090       if (lp == theLoop)
1091         continue;
1092
1093       if (lp->entry == theLoop->entry)
1094         {
1095           theLoop->regBlocks = unionSets (theLoop->regBlocks,
1096                                           lp->regBlocks, THROW_DEST);
1097           lp->merged = 1;
1098         }
1099     }
1100
1101   return 1;
1102 }
1103
1104 /*-----------------------------------------------------------------*/
1105 /* ifMerged - return 1 if the merge flag is 1                      */
1106 /*-----------------------------------------------------------------*/
1107 DEFSETFUNC (ifMerged)
1108 {
1109   region *lp = item;
1110
1111   return lp->merged;
1112 }
1113
1114 /*-----------------------------------------------------------------*/
1115 /* mergeInnerLoops - will merge into body when entry is present    */
1116 /*-----------------------------------------------------------------*/
1117 DEFSETFUNC (mergeInnerLoops)
1118 {
1119   region *theLoop = item;
1120   V_ARG (set *, allRegion);
1121   V_ARG (int *, maxDepth);
1122   region *lp;
1123
1124   /* check if the entry point is present in the body of any */
1125   /* loop then put the body of this loop into the outer loop */
1126   for (lp = setFirstItem (allRegion); lp; lp = setNextItem (allRegion))
1127     {
1128
1129       if (lp == theLoop)
1130         continue;
1131
1132       if (isinSet (lp->regBlocks, theLoop->entry))
1133         {
1134           lp->containsLoops += theLoop->containsLoops + 1;
1135           if (lp->containsLoops > (*maxDepth))
1136             *maxDepth = lp->containsLoops;
1137
1138           lp->regBlocks = unionSets (lp->regBlocks,
1139                                      theLoop->regBlocks, THROW_DEST);
1140         }
1141     }
1142
1143   return 1;
1144 }
1145
1146
1147 /*-----------------------------------------------------------------*/
1148 /* createLoopRegions - will detect and create a set of natural loops */
1149 /*-----------------------------------------------------------------*/
1150 hTab *
1151 createLoopRegions (eBBlock ** ebbs, int count)
1152 {
1153   set *allRegion = NULL;        /* set of all loops */
1154   hTab *orderedLoops = NULL;
1155   set *bEdges = NULL;
1156   int maxDepth = 0;
1157   region *lp;
1158
1159   /* get all the back edges in the graph */
1160   if (!applyToSet (graphEdges, backEdges, &bEdges))
1161     return 0;                   /* found no loops */
1162
1163   /* for each of these back edges get the blocks that */
1164   /* constitute the loops                             */
1165   applyToSet (bEdges, createLoop, &allRegion);
1166
1167   /* now we will create regions from these loops               */
1168   /* loops with the same entry points are considered to be the */
1169   /* same loop & they are merged. If the entry point of a loop */
1170   /* is found in the body of another loop then , all the blocks */
1171   /* in that loop are added to the loops containing the header */
1172   applyToSet (allRegion, mergeRegions, allRegion);
1173
1174   /* delete those already merged */
1175   deleteItemIf (&allRegion, ifMerged);
1176
1177   applyToSet (allRegion, mergeInnerLoops, allRegion, &maxDepth);
1178   maxDepth++;
1179
1180   /* now create all the exits .. also */
1181   /* create an ordered set of loops   */
1182   /* i.e. we process loops in the inner to outer order */
1183   for (lp = setFirstItem (allRegion); lp; lp = setNextItem (allRegion))
1184     {
1185       applyToSet (lp->regBlocks, addToExitsMarkDepth,
1186                   lp->regBlocks, &lp->exits,
1187                   (maxDepth - lp->containsLoops), lp);
1188
1189       hTabAddItem (&orderedLoops, lp->containsLoops, lp);
1190
1191     }
1192   return orderedLoops;
1193 }
1194
1195 /*-----------------------------------------------------------------*/
1196 /* loopOptimizations - identify region & remove invariants & ind   */
1197 /*-----------------------------------------------------------------*/
1198 int
1199 loopOptimizations (hTab * orderedLoops, eBBlock ** ebbs, int count)
1200 {
1201   region *lp;
1202   int change = 0;
1203   int k;
1204
1205   /* if no loop optimizations requested */
1206   if (!optimize.loopInvariant &&
1207       !optimize.loopInduction)
1208     return 0;
1209
1210   /* now we process the loops inner to outer order */
1211   /* this is essential to maintain data flow information */
1212   /* the other choice is an ugly iteration for the depth */
1213   /* of the loops would hate that */
1214   for (lp = hTabFirstItem (orderedLoops, &k); lp;
1215        lp = hTabNextItem (orderedLoops, &k))
1216     {
1217
1218       if (optimize.loopInvariant)
1219         change += loopInvariants (lp, ebbs, count);
1220
1221       if (optimize.loopInduction)
1222         change += loopInduction (lp, ebbs, count);
1223     }
1224
1225   return change;
1226 }
1227
1228 /*-----------------------------------------------------------------*/
1229 /* addLoopBlocks - will add all blocks inside a loop to this loop  */
1230 /* this should fix most of the liverange problems                  */
1231 /*-----------------------------------------------------------------*/
1232 void
1233 addLoopBlocks (eBBlock ** ebbs, int count)
1234 {
1235   region *aloop;
1236   struct eBBlock *block;
1237   int seqMin, seqMax;
1238   int i, j;
1239
1240   for (i = 0; i < count; i++)
1241     {
1242       if (!ebbs[i]->KpartOfLoop)
1243         continue;
1244
1245       /* for all loops this block belongs to */
1246       /* add inner block not already marked as part of this loop */
1247       aloop = setFirstItem (ebbs[i]->KpartOfLoop);
1248       for (; aloop; aloop = setNextItem (ebbs[i]->KpartOfLoop))
1249         {
1250
1251           if (aloop->visited)
1252             continue;
1253
1254           aloop->visited = 1;
1255
1256           /* set max & min Seq for loopRegion */
1257           block = setFirstItem (aloop->regBlocks);
1258           seqMax = block->lSeq;
1259           seqMin = block->fSeq;
1260           for (; block; block = setNextItem (aloop->regBlocks))
1261             {
1262               if (block->lSeq > seqMax)
1263                 seqMax = block->lSeq;
1264               if (block->fSeq < seqMin)
1265                 seqMin = block->fSeq;
1266             }
1267
1268           /* add all blocks between seqMin, seqMax to loop */
1269           for (j = 0; j < count; j++)
1270             {
1271               if (ebbs[j]->fSeq > seqMin && ebbs[j]->lSeq < seqMax &&
1272                   !isinSet (aloop->regBlocks, ebbs[j]))
1273                 {
1274                   if (!isinSet (ebbs[j]->KpartOfLoop, aloop))
1275                     addSetHead (&ebbs[j]->KpartOfLoop, aloop);
1276                 }
1277             }
1278         }
1279     }
1280 }