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                   iCode *ic2;
 573                   int used;
 574                   int defDominates;
 575
 576                   /* if this is the block make sure the definition */
 577                   /* reaches the end of the block */
 578                   if (sBlock == lBlock)
 579                     {
 580                       if (!ifDiCodeIs (sBlock->outExprs, ic))
 581                         break;
 582                     }
 583                   else if (bitVectBitsInCommon (sBlock->defSet, OP_DEFS (IC_RESULT (ic))))
 584                     break;
 585
 586                   /* Check that this definition is not assigned */
 587                   /* any other value in this block. Also check */
 588                   /* that any usage in the block is dominated by */
 589                   /* by this definition. */
 590                   defDominates = bitVectBitValue (sBlock->domVect, lBlock->bbnum);
 591                   used = 0;
 592                   for (ic2 = sBlock->sch; ic2; ic2 = ic2->next)
 593                     {
 594                       if (ic2->op == IFX)
 595                         {
 596                           if (isOperandEqual (IC_RESULT (ic), IC_COND (ic2)))
 597                             used = 1;
 598                         }
 599                       else if (ic2->op == JUMPTABLE)
 600                         {
 601                           if (isOperandEqual (IC_RESULT (ic), IC_JTCOND (ic2)))
 602                             used = 1;
 603                         }
 604                       else
 605                         {
 606                           if (IC_LEFT (ic2) && isOperandEqual (IC_RESULT (ic), IC_LEFT (ic2)))
 607                             used = 1;
 608                           if (IC_RIGHT (ic2) && isOperandEqual (IC_RESULT (ic), IC_RIGHT (ic2)))
 609                             used = 1;
 610                           if ((ic != ic2) && (isOperandEqual(IC_RESULT(ic), IC_RESULT(ic2))))
 611                             break;
 612                           /* If used before this definition, might not be invariant */
 613                           if ((ic == ic2) && used)
 614                             break;
 615                         }
 616                       if (used && !defDominates)
 617                         break;
 618                     }
 619                   if (ic2) /* found another definition or a usage before the definition */
 620                     break;
 621                 }
 622
 623               if (sBlock)
 624                 continue;       /* another definition present in the block */
 625
 626
 627               /* now check if it exists in the in of this block */
 628               /* if not then it was killed before this instruction */
 629               if (!bitVectBitValue (lBlock->inDefs, ic->key))
 630                 continue;
 631
 632               /* now we know it is a true invariant */
 633               /* remove it from the insts chain & put */
 634               /* in the invariant set                */
 635
 636               OP_SYMBOL (IC_RESULT (ic))->isinvariant = 1;
 637               SPIL_LOC (IC_RESULT (ic)) = NULL;
 638               remiCodeFromeBBlock (lBlock, ic);
 639
 640               /* maintain the data flow */
 641               /* this means removing from definition from the */
 642               /* defset of this block and adding it to the    */
 643               /* inexpressions of all blocks within the loop  */
 644               bitVectUnSetBit (lBlock->defSet, ic->key);
 645               bitVectUnSetBit (lBlock->ldefs, ic->key);
 646               ivar = newCseDef (IC_RESULT (ic), ic);
 647               applyToSet (theLoop->regBlocks, addDefInExprs, ivar, ebbi);
 648               addSet (&lInvars, ivar);
 649             }
 650         }
 651     }                           /* for all loop blocks */
 652
 653   /* if we have some invariants then */
 654   if (lInvars)
 655     {
 656       eBBlock *preHdr = theLoop->entry->preHeader;
 657       iCode *icFirst = NULL, *icLast = NULL;
 658       cseDef *cdp;
 659
 660       /* create an iCode chain from it */
 661       for (cdp = setFirstItem (lInvars); cdp; cdp = setNextItem (lInvars))
 662         {
 663
 664           /* maintain data flow .. add it to the */
 665           /* ldefs defSet & outExprs of the preheader  */
 666           preHdr->defSet = bitVectSetBit (preHdr->defSet, cdp->diCode->key);
 667           preHdr->ldefs = bitVectSetBit (preHdr->ldefs, cdp->diCode->key);
 668           cdp->diCode->lineno = preHdr->ech->lineno;
 669           addSetHead (&preHdr->outExprs, cdp);
 670
 671
 672           if (!icFirst)
 673             icFirst = cdp->diCode;
 674           if (icLast)
 675             {
 676               icLast->next = cdp->diCode;
 677               cdp->diCode->prev = icLast;
 678               icLast = cdp->diCode;
 679             }
 680           else
 681             icLast = cdp->diCode;
 682           change++;
 683         }
 684
 685       /* add the instruction chain to the end of the
 686          preheader for this loop, preheaders will always
 687          have atleast a label */
 688       preHdr->ech->next = icFirst;
 689       icFirst->prev = preHdr->ech;
 690       preHdr->ech = icLast;
 691       icLast->next = NULL;
 692
 693     }
 694   return change;
 695 }
 696
 697 /*-----------------------------------------------------------------*/
 698 /* addressTaken - returns true if the symbol is found in the addrof */
 699 /*-----------------------------------------------------------------*/
 700 int
 701 addressTaken (set * sset, operand * sym)
 702 {
 703   set *loop;
 704   eBBlock *ebp;
 705   set *loop2;
 706
 707   for (loop = sset; loop; loop = loop->next)
 708     {
 709       ebp = loop->item;
 710       loop2 = ebp->addrOf;
 711       while (loop2)
 712         {
 713           if (isOperandEqual ((operand *) loop2->item, sym))
 714             return 1;
 715           loop2 = loop2->next;
 716         }
 717     }
 718
 719   return 0;
 720 }
 721
 722
 723 /*-----------------------------------------------------------------*/
 724 /* findInduction :- returns 1 & the item if the induction is found */
 725 /*-----------------------------------------------------------------*/
 726 DEFSETFUNC (findInduction)
 727 {
 728   induction *ip = item;
 729   V_ARG (operand *, sym);
 730   V_ARG (induction **, ipp);
 731
 732   if (isOperandEqual (ip->sym, sym))
 733     {
 734       *ipp = ip;
 735       return 1;
 736     }
 737
 738   return 0;
 739 }
 740
 741 /*-----------------------------------------------------------------*/
 742 /* findDefInRegion - finds the definition within the region        */
 743 /*-----------------------------------------------------------------*/
 744 iCode *
 745 findDefInRegion (set * regBlocks, operand * defOp, eBBlock ** owner)
 746 {
 747   eBBlock *lBlock;
 748
 749   /* for all blocks in the region */
 750   for (lBlock = setFirstItem (regBlocks); lBlock;
 751        lBlock = setNextItem (regBlocks))
 752     {
 753
 754       /* if a definition for this exists */
 755       if (bitVectBitsInCommon (lBlock->defSet, OP_DEFS (defOp)))
 756         {
 757           iCode *ic;
 758
 759           /* go thru the instruction chain to find it */
 760           for (ic = lBlock->sch; ic; ic = ic->next)
 761             if (bitVectBitValue (OP_DEFS (defOp), ic->key))
 762               {
 763                 if (owner)
 764                   *owner = lBlock;
 765                 return ic;
 766               }
 767         }
 768     }
 769
 770   return NULL;
 771 }
 772
 773 /*-----------------------------------------------------------------*/
 774 /* basicInduction - finds the basic induction variables in a loop  */
 775 /*-----------------------------------------------------------------*/
 776 set *
 777 basicInduction (region * loopReg, eBBlock ** ebbs, int count)
 778 {
 779   eBBlock *lBlock;
 780   set *indVars = NULL;
 781
 782   /* i.e. all assignments of the form a := a +/- const */
 783   /* for all blocks within the loop do */
 784   for (lBlock = setFirstItem (loopReg->regBlocks); lBlock;
 785        lBlock = setNextItem (loopReg->regBlocks))
 786     {
 787
 788       iCode *ic, *dic;
 789
 790       /* for all instructions in the blocks do */
 791       for (ic = lBlock->sch; ic; ic = ic->next)
 792         {
 793
 794           operand *aSym;
 795           long litValue;
 796           induction *ip;
 797           iCode *indIc;
 798           eBBlock *owner = NULL;
 799           int nexits;
 800           sym_link *optype;
 801
 802           /* To find an induction variable, we need to */
 803           /* find within the loop three iCodes in this */
 804           /* general form:                             */
 805           /*                                           */
 806           /* ddic: iTempB    := symbolVar              */
 807           /* dic:  iTempA    := iTempB + lit           */
 808           /*    or iTempA    := iTempB - lit           */
 809           /*    or iTempA    := lit + iTempB           */
 810           /* ic:   symbolVar := iTempA                 */
 811           /*                                           */
 812           /* (symbolVar may also be an iTemp if it is  */
 813           /*  register equivalent)                     */
 814
 815           /* look for assignments of the form */
 816           /*   symbolVar := iTempNN */
 817           if (ic->op != '=')
 818             continue;
 819
 820           if (!IS_TRUE_SYMOP (IC_RESULT (ic)) &&
 821               !OP_SYMBOL (IC_RESULT (ic))->isreqv)
 822             continue;
 823
 824           if (isOperandGlobal (IC_RESULT (ic)))
 825             continue;
 826
 827           if (!IS_ITEMP (IC_RIGHT (ic)))
 828             continue;
 829
 830           /* if it has multiple assignments within the loop then skip */
 831           if (assignmentsToSym (loopReg->regBlocks, IC_RESULT (ic)) > 1)
 832             continue;
 833
 834           /* if the address of this was taken inside the loop then continue */
 835           if (addressTaken (loopReg->regBlocks, IC_RESULT (ic)))
 836             continue;
 837
 838           /* Only consider variables with integral type. */
 839           /* (2004/12/06 - EEP - ds390 fails regression tests unless */
 840           /* pointers are also considered for induction (due to some */
 841           /* register alloctaion bugs). Remove !IS_PTR clause when */
 842           /* that gets fixed) */
 843           optype = operandType (IC_RIGHT (ic));
 844           if (!IS_INTEGRAL (optype) && !IS_PTR (optype))
 845             continue;
 846
 847           /* find the definition for the result in the block */
 848           if (!(dic = findDefInRegion (setFromSet (loopReg->regBlocks),
 849                                        IC_RIGHT (ic), &owner)))
 850             continue;
 851
 852           /* if not +/- continue */
 853           if (dic->op != '+' && dic->op != '-')
 854             continue;
 855
 856           /* make sure definition is of the form  a +/- c */
 857           if (!IS_OP_LITERAL (IC_LEFT (dic)) && !IS_OP_LITERAL (IC_RIGHT (dic)))
 858             continue;
 859
 860           /* make sure the definition found is the only one */
 861           if (assignmentsToSym (loopReg->regBlocks, IC_RIGHT (ic)) > 1)
 862             continue;
 863
 864           if (IS_OP_LITERAL (IC_RIGHT (dic)))
 865             {
 866               aSym = IC_LEFT (dic);
 867               litValue = (long) operandLitValue (IC_RIGHT (dic));
 868             }
 869           else
 870             {
 871               /* For minus, the literal must not be on the left side. */
 872               /* (Actually, this case could be handled, but it's probably */
 873               /* not worth the extra code) */
 874               if (dic->op == '-')
 875                 continue;
 876               aSym = IC_RIGHT (dic);
 877               litValue = (long) operandLitValue (IC_LEFT (dic));
 878             }
 879
 880           if (!isOperandEqual (IC_RESULT (ic), aSym) &&
 881               !isOperandEqual (IC_RIGHT (ic), aSym))
 882             {
 883               iCode *ddic;
 884               /* find the definition for this and check */
 885               if (!(ddic = findDefInRegion (setFromSet (loopReg->regBlocks),
 886                                             aSym, &owner)))
 887                 continue;
 888
 889               if (ddic->op != '=')
 890                 continue;
 891
 892               if (!isOperandEqual (IC_RESULT (ddic), aSym) ||
 893                   !isOperandEqual (IC_RIGHT (ddic), IC_RESULT (ic)))
 894                 continue;
 895             }
 896
 897           /* if the right hand side has more than one usage then
 898              don't make it an induction (will have to think some more) */
 899           if (bitVectnBitsOn (OP_USES (IC_RIGHT (ic))) > 1)
 900             continue;
 901
 902           /* if the definition is volatile then it cannot be
 903              an induction object */
 904           if (isOperandVolatile (IC_RIGHT (ic), FALSE) ||
 905               isOperandVolatile (IC_RESULT (ic), FALSE))
 906             continue;
 907
 908           /* whew !! that was a lot of work to find the definition */
 909           /* create an induction object */
 910           indIc = newiCode ('=', NULL, IC_RESULT (ic));
 911           indIc->lineno = ic->lineno;
 912           IC_RESULT (indIc) = operandFromOperand (IC_RIGHT (ic));
 913           IC_RESULT (indIc)->isaddr = 0;
 914           OP_SYMBOL (IC_RESULT (indIc))->isind = 1;
 915           ip = newInduction (IC_RIGHT (ic), dic->op, litValue, indIc, NULL);
 916
 917           /* replace the inducted variable by the iTemp */
 918           replaceSymBySym (loopReg->regBlocks, IC_RESULT (ic), IC_RIGHT (ic));
 919
 920           /* if it has only one exit then remove it from here
 921              and put it in the exit block */
 922           nexits = elementsInSet (loopReg->exits);
 923           if (nexits == 1)
 924             {
 925               eBBlock *exit = setFirstItem (loopReg->exits);
 926               /* if it is the same block then there is no
 927                  need to move it about */
 928               if (exit != lBlock)
 929                 {
 930                   iCode *saveic = ic->prev;
 931                   /* remove it */
 932                   remiCodeFromeBBlock (lBlock, ic);
 933                   /* clear the definition */
 934                   bitVectUnSetBit (lBlock->defSet, ic->key);
 935                   /* add it to the exit */
 936                   addiCodeToeBBlock (exit, ic, NULL);
 937                   /* set the definition bit */
 938                   exit->defSet = bitVectSetBit (exit->defSet, ic->key);
 939                   ic = saveic;
 940                 }
 941             }
 942
 943           /* if the number of exits is greater than one then
 944              we use another trick ; we will create an intersection
 945              of succesors of the exits, then take those that are not
 946              part of the loop and have dfNumber greater loop entry
 947              and insert a new definition in them */
 948           if (nexits > 1)
 949             {
 950
 951               bitVect *loopSuccs = intersectLoopSucc (loopReg->exits, ebbs);
 952
 953               /* loopSuccs now contains intersection
 954                  of all the loops successors */
 955               if (loopSuccs)
 956                 {
 957                   int i;
 958                   for (i = 0; i < loopSuccs->size; i++)
 959                     {
 960                       if (bitVectBitValue (loopSuccs, i))
 961                         {
 962
 963                           eBBlock *eblock = NULL;
 964                           int j;
 965
 966                           /* Need to search for bbnum == i since ebbs is  */
 967                           /* sorted by dfnum; a direct index won't do.  */
 968                           for (j=0; j<count; j++)
 969                             if (ebbs[j]->bbnum == i)
 970                               {
 971                                 eblock = ebbs[j];
 972                                 break;
 973                               }
 974                           assert(eblock);
 975
 976                           /* if the successor does not belong to the loop
 977                              and will be executed after the loop : then
 978                              add a definition to the block */
 979                           if (!isinSet (loopReg->regBlocks, eblock) &&
 980                               eblock->dfnum > loopReg->entry->dfnum)
 981                             {
 982                               /* create the definition */
 983                               iCode *newic = newiCode ('=', NULL,
 984                                         operandFromOperand (IC_RIGHT (ic)));
 985                               IC_RESULT (newic) = operandFromOperand (IC_RESULT (ic));
 986                               OP_DEFS(IC_RESULT (newic))=
 987                                 bitVectSetBit (OP_DEFS (IC_RESULT (newic)), newic->key);
 988                               OP_USES(IC_RIGHT (newic))=
 989                                 bitVectSetBit (OP_USES (IC_RIGHT (newic)), newic->key);
 990                               /* and add it */
 991                               if (eblock->sch && eblock->sch->op == LABEL)
 992                                 addiCodeToeBBlock (eblock, newic, eblock->sch->next);
 993                               else
 994                                 addiCodeToeBBlock (eblock, newic, eblock->sch);
 995                               /* set the definition bit */
 996                               eblock->defSet = bitVectSetBit (eblock->defSet, ic->key);
 997                             }
 998                         }
 999                     }
1000                 }
1001             }
1002
1003           addSet (&indVars, ip);
1004         }
1005
1006     }                           /* end of all blocks for basic induction variables */
1007
1008   return indVars;
1009 }
1010
1011 /*-----------------------------------------------------------------*/
1012 /* loopInduction - remove induction variables from a loop          */
1013 /*-----------------------------------------------------------------*/
1014 int
1015 loopInduction (region * loopReg, ebbIndex * ebbi)
1016 {
1017   eBBlock ** ebbs = ebbi->dfOrder;
1018   int count = ebbi->count;
1019   int change = 0;
1020   eBBlock *lBlock, *owner, *lastBlock = NULL;
1021   set *indVars = NULL;
1022   set *basicInd = NULL;
1023
1024   if (loopReg->entry->preHeader == NULL)
1025     return 0;
1026
1027   /* we first determine the basic Induction variables */
1028   basicInd = setFromSet (indVars = basicInduction (loopReg, ebbs, count));
1029
1030   /* find other induction variables : by other we mean definitions of */
1031   /* the form x := y (* | / ) <constant> .. we will move  this one to */
1032   /* beginning of the loop and reduce strength i.e. replace with +/-  */
1033   /* these expensive expressions: OH! and y must be induction too     */
1034   for (lBlock = setFirstItem (loopReg->regBlocks), lastBlock = lBlock;
1035        lBlock && indVars;
1036        lBlock = setNextItem (loopReg->regBlocks))
1037     {
1038
1039       iCode *ic, *indIc, *dic;
1040       induction *ip;
1041
1042       /* last block is the one with the highest block
1043          number */
1044       if (lastBlock->bbnum < lBlock->bbnum)
1045         lastBlock = lBlock;
1046
1047       for (ic = lBlock->sch; ic; ic = ic->next)
1048         {
1049           operand *aSym;
1050           long litVal;
1051
1052           /* consider only * & / */
1053           if (ic->op != '*' && ic->op != '/')
1054             continue;
1055
1056           /* only consider variables with integral type */
1057           if (!IS_INTEGRAL (operandType (IC_RESULT (ic))))
1058             continue;
1059
1060           /* if the result has more definitions then */
1061           if (assignmentsToSym (loopReg->regBlocks, IC_RESULT (ic)) > 1)
1062             continue;
1063
1064           /* check if the operands are what we want */
1065           /* i.e. one of them an symbol the other a literal */
1066           if (!((IS_SYMOP (IC_LEFT (ic)) && IS_OP_LITERAL (IC_RIGHT (ic))) ||
1067                 (IS_OP_LITERAL (IC_LEFT (ic)) && IS_SYMOP (IC_RIGHT (ic)))))
1068             continue;
1069
1070           if (IS_SYMOP (IC_LEFT (ic)))
1071             {
1072               aSym = IC_LEFT (ic);
1073               litVal = (long) operandLitValue (IC_RIGHT (ic));
1074             }
1075           else
1076             {
1077               /* For division, the literal must not be on the left side */
1078               if (ic->op == '/')
1079                 continue;
1080               aSym = IC_RIGHT (ic);
1081               litVal = (long) operandLitValue (IC_LEFT (ic));
1082             }
1083
1084           ip = NULL;
1085           /* check if this is an induction variable */
1086           if (!applyToSetFTrue (basicInd, findInduction, aSym, &ip))
1087             continue;
1088
1089           /* ask port for size not worth if native instruction
1090              exist for multiply & divide */
1091           if (getSize (operandType (IC_LEFT (ic))) <= (unsigned long) port->support.muldiv ||
1092           getSize (operandType (IC_RIGHT (ic))) <= (unsigned long) port->support.muldiv)
1093             continue;
1094
1095           /* if this is a division then the remainder should be zero
1096              for it to be inducted */
1097           if (ic->op == '/' && (ip->cval % litVal))
1098             continue;
1099
1100           /* create the iCode to be placed in the loop header */
1101           /* and create the induction object */
1102
1103           /* create an instruction */
1104           /* this will be put on the loop header */
1105           indIc = newiCode (ic->op,
1106                             operandFromOperand (aSym),
1107                             operandFromLit (litVal));
1108           indIc->lineno = ic->lineno;
1109           IC_RESULT (indIc) = operandFromOperand (IC_RESULT (ic));
1110           OP_SYMBOL (IC_RESULT (indIc))->isind = 1;
1111
1112           /* keep track of the inductions */
1113           litVal = (ic->op == '*' ? (litVal * ip->cval) :
1114                     (ip->cval / litVal));
1115
1116           addSet (&indVars,
1117                 newInduction (IC_RESULT (ic), ip->op, litVal, indIc, NULL));
1118
1119           /* Replace mul/div with assignment to self; killDeadCode() will */
1120           /* clean this up since we can't use remiCodeFromeBBlock() here. */
1121           ic->op = '=';
1122           IC_LEFT (ic) = NULL;
1123           IC_RIGHT (ic) = IC_RESULT (ic);
1124
1125           /* Insert an update of the induction variable just before */
1126           /* the update of the basic induction variable. */
1127           indIc = newiCode (ip->op,
1128                             operandFromOperand (IC_RESULT (ic)),
1129                             operandFromLit (litVal));
1130           IC_RESULT (indIc) = operandFromOperand (IC_RESULT (ic));
1131           owner = NULL;
1132           dic = findDefInRegion (setFromSet (loopReg->regBlocks), aSym, &owner);
1133           assert (dic);
1134           addiCodeToeBBlock (owner, indIc, dic);
1135
1136         }
1137     }
1138
1139   /* if we have some induction variables then */
1140   if (indVars)
1141     {
1142       eBBlock *preHdr = loopReg->entry->preHeader;
1143       iCode *icFirst = NULL, *icLast = NULL;
1144       induction *ip;
1145       bitVect *indVect = NULL;
1146
1147       /* create an iCode chain from it */
1148       for (ip = setFirstItem (indVars);
1149            ip;
1150            ip = setNextItem (indVars))
1151         {
1152
1153           indVect = bitVectSetBit (indVect, ip->ic->key);
1154           ip->ic->lineno = preHdr->ech->lineno;
1155           if (!icFirst)
1156             icFirst = ip->ic;
1157           if (icLast)
1158             {
1159               icLast->next = ip->ic;
1160               ip->ic->prev = icLast;
1161               icLast = ip->ic;
1162             }
1163           else
1164             icLast = ip->ic;
1165           change++;
1166         }
1167
1168       /* add the instruction chain to the end of the */
1169       /* preheader for this loop                     */
1170       preHdr->ech->next = icFirst;
1171       icFirst->prev = preHdr->ech;
1172       preHdr->ech = icLast;
1173       icLast->next = NULL;
1174
1175       /* add the induction variable vector to the last
1176          block in the loop */
1177       lastBlock->isLastInLoop = 1;
1178       lastBlock->linds = bitVectUnion(lastBlock->linds,indVect);
1179     }
1180
1181   setToNull ((void *) &indVars);
1182   return change;
1183 }
1184
1185 /*-----------------------------------------------------------------*/
1186 /* mergeRegions - will merge region with same entry point           */
1187 /*-----------------------------------------------------------------*/
1188 DEFSETFUNC (mergeRegions)
1189 {
1190   region *theLoop = item;
1191   V_ARG (set *, allRegion);
1192   region *lp;
1193
1194   /* if this has already been merged then do nothing */
1195   if (theLoop->merged)
1196     return 0;
1197
1198   /* go thru all the region and check if any of them have the */
1199   /* entryPoint as the Loop                                  */
1200   for (lp = setFirstItem (allRegion); lp; lp = setNextItem (allRegion))
1201     {
1202
1203       if (lp == theLoop)
1204         continue;
1205
1206       if (lp->entry == theLoop->entry)
1207         {
1208           theLoop->regBlocks = unionSets (theLoop->regBlocks,
1209                                           lp->regBlocks, THROW_DEST);
1210           lp->merged = 1;
1211         }
1212     }
1213
1214   return 1;
1215 }
1216
1217 /*-----------------------------------------------------------------*/
1218 /* ifMerged - return 1 if the merge flag is 1                      */
1219 /*-----------------------------------------------------------------*/
1220 DEFSETFUNC (ifMerged)
1221 {
1222   region *lp = item;
1223
1224   return lp->merged;
1225 }
1226
1227 /*-----------------------------------------------------------------*/
1228 /* mergeInnerLoops - will merge into body when entry is present    */
1229 /*-----------------------------------------------------------------*/
1230 DEFSETFUNC (mergeInnerLoops)
1231 {
1232   region *theLoop = item;
1233   V_ARG (set *, allRegion);
1234   V_ARG (int *, maxDepth);
1235   region *lp;
1236
1237   /* check if the entry point is present in the body of any */
1238   /* loop then put the body of this loop into the outer loop */
1239   for (lp = setFirstItem (allRegion); lp; lp = setNextItem (allRegion))
1240     {
1241
1242       if (lp == theLoop)
1243         continue;
1244
1245       if (isinSet (lp->regBlocks, theLoop->entry))
1246         {
1247           lp->containsLoops += theLoop->containsLoops + 1;
1248           if (lp->containsLoops > (*maxDepth))
1249             *maxDepth = lp->containsLoops;
1250
1251           lp->regBlocks = unionSets (lp->regBlocks,
1252                                      theLoop->regBlocks, THROW_DEST);
1253         }
1254     }
1255
1256   return 1;
1257 }
1258
1259
1260 /*-----------------------------------------------------------------*/
1261 /* createLoopRegions - will detect and create a set of natural loops */
1262 /*-----------------------------------------------------------------*/
1263 hTab *
1264 createLoopRegions (ebbIndex * ebbi)
1265 {
1266   set *allRegion = NULL;        /* set of all loops */
1267   hTab *orderedLoops = NULL;
1268   set *bEdges = NULL;
1269   int maxDepth = 0;
1270   region *lp;
1271
1272   /* get all the back edges in the graph */
1273   if (!applyToSet (graphEdges, backEdges, &bEdges))
1274     return 0;                   /* found no loops */
1275
1276   /* for each of these back edges get the blocks that */
1277   /* constitute the loops                             */
1278   applyToSet (bEdges, createLoop, &allRegion);
1279
1280   /* now we will create regions from these loops               */
1281   /* loops with the same entry points are considered to be the */
1282   /* same loop & they are merged. If the entry point of a loop */
1283   /* is found in the body of another loop then , all the blocks */
1284   /* in that loop are added to the loops containing the header */
1285   applyToSet (allRegion, mergeRegions, allRegion);
1286
1287   /* delete those already merged */
1288   deleteItemIf (&allRegion, ifMerged);
1289
1290   applyToSet (allRegion, mergeInnerLoops, allRegion, &maxDepth);
1291   maxDepth++;
1292
1293   /* now create all the exits .. also */
1294   /* create an ordered set of loops   */
1295   /* i.e. we process loops in the inner to outer order */
1296   for (lp = setFirstItem (allRegion); lp; lp = setNextItem (allRegion))
1297     {
1298       applyToSet (lp->regBlocks, addToExitsMarkDepth,
1299                   lp->regBlocks, &lp->exits,
1300                   (maxDepth - lp->containsLoops), lp);
1301
1302       hTabAddItem (&orderedLoops, lp->containsLoops, lp);
1303
1304     }
1305   return orderedLoops;
1306 }
1307
1308 /*-----------------------------------------------------------------*/
1309 /* loopOptimizations - identify region & remove invariants & ind   */
1310 /*-----------------------------------------------------------------*/
1311 int
1312 loopOptimizations (hTab * orderedLoops, ebbIndex * ebbi)
1313 {
1314   region *lp;
1315   int change = 0;
1316   int k;
1317
1318   /* if no loop optimizations requested */
1319   if (!optimize.loopInvariant &&
1320       !optimize.loopInduction)
1321     return 0;
1322
1323   /* now we process the loops inner to outer order */
1324   /* this is essential to maintain data flow information */
1325   /* the other choice is an ugly iteration for the depth */
1326   /* of the loops would hate that */
1327   for (lp = hTabFirstItem (orderedLoops, &k); lp;
1328        lp = hTabNextItem (orderedLoops, &k))
1329     {
1330
1331       if (optimize.loopInvariant)
1332         change += loopInvariants (lp, ebbi);
1333
1334       if (optimize.loopInduction)
1335         change += loopInduction (lp, ebbi);
1336     }
1337
1338   return change;
1339 }