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

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