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

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