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   return ebp->hasFcall || bitVectBitValue (ebp->ptrsSet, op->key);
 383 }
 384
 385 /*-----------------------------------------------------------------*/
 386 /* hasNonPtrUse - returns true if operand has non pointer usage    */
 387 /*-----------------------------------------------------------------*/
 388 DEFSETFUNC (hasNonPtrUse)
 389 {
 390   eBBlock *ebp = item;
 391   V_ARG (operand *, op);
 392   iCode *ic = usedInRemaining (op, ebp->sch);
 393
 394   if (ic && !POINTER_SET (ic) && !POINTER_GET (ic))
 395     return 1;
 396
 397   return 0;
 398
 399 }
 400
 401 /*-----------------------------------------------------------------*/
 402 /* loopInvariants - takes loop invariants out of region            */
 403 /*-----------------------------------------------------------------*/
 404 int
 405 loopInvariants (region * theLoop, eBBlock ** ebbs, int count)
 406 {
 407   eBBlock *lBlock;
 408   set *lInvars = NULL;
 409
 410   int change = 0;
 411   int fCallsInBlock;
 412
 413   /* if the preHeader does not exist then do nothing */
 414   /* or no exits then do nothing ( have to think about this situation */
 415   if (theLoop->entry->preHeader == NULL ||
 416       theLoop->exits == NULL)
 417     return 0;
 418
 419   /* we will do the elimination for those blocks        */
 420   /* in the loop that dominates all exits from the loop */
 421   for (lBlock = setFirstItem (theLoop->regBlocks); lBlock;
 422        lBlock = setNextItem (theLoop->regBlocks))
 423     {
 424
 425       iCode *ic;
 426       int domsAllExits;
 427       int i;
 428
 429       /* mark the dominates all exits flag */
 430       domsAllExits = (applyToSet (theLoop->exits, dominatedBy, lBlock) ==
 431                       elementsInSet (theLoop->exits));
 432
 433       /* find out if we have a function call in this block */
 434       for (ic = lBlock->sch, fCallsInBlock=0; ic; ic = ic->next) {
 435         if (SKIP_IC(ic)) {
 436           fCallsInBlock++;
 437         }
 438       }
 439
 440       /* now we go thru the instructions of this block and */
 441       /* collect those instructions with invariant operands */
 442       for (ic = lBlock->sch; ic; ic = ic->next)
 443         {
 444
 445           int lin, rin;
 446           cseDef *ivar;
 447
 448           /* TODO this is only needed if the call is between
 449              here and the definition, but I am too lazy to do that now */
 450
 451           /* if there are function calls in this block */
 452           if (fCallsInBlock) {
 453
 454             /* if this is a pointer get */
 455             if (POINTER_GET(ic)) {
 456               continue;
 457             }
 458
 459             /* if this is an assignment from a global */
 460             if (ic->op=='=' && isOperandGlobal(IC_RIGHT(ic))) {
 461               continue;
 462             }
 463           }
 464
 465           if (SKIP_IC (ic) || POINTER_SET (ic) || ic->op == IFX)
 466             continue;
 467
 468           /* if result is volatile then skip */
 469           if (IC_RESULT (ic) &&
 470               (isOperandVolatile (IC_RESULT (ic), TRUE) ||
 471                IS_OP_PARM (IC_RESULT (ic))))
 472             continue;
 473
 474           /* if result depends on a volatile then skip */
 475           if ((IC_LEFT(ic) && isOperandVolatile(IC_LEFT(ic), TRUE)) ||
 476               (IC_RIGHT(ic) && isOperandVolatile(IC_RIGHT(ic), TRUE)))
 477             continue;
 478
 479           lin = rin = 0;
 480
 481           /* special case */
 482           /* if address of then it is an invariant */
 483           if (ic->op == ADDRESS_OF &&
 484               IS_SYMOP (IC_LEFT (ic)) &&
 485               IS_AGGREGATE (operandType (IC_LEFT (ic))))
 486             lin++;
 487           else {
 488             /* check if left operand is an invariant */
 489             if ((lin = isOperandInvariant (IC_LEFT (ic), theLoop, lInvars)))
 490               /* if this is a pointer get then make sure
 491                  that the pointer set does not exist in
 492                  any of the blocks */
 493               if (POINTER_GET (ic) &&
 494                   (applyToSet (theLoop->regBlocks,
 495                                pointerAssigned, IC_LEFT (ic))))
 496                 lin = 0;
 497           }
 498
 499           /* do the same for right */
 500           rin = isOperandInvariant (IC_RIGHT (ic), theLoop, lInvars);
 501
 502           /* if this is a POINTER_GET then special case, make sure all
 503              usages within the loop are POINTER_GET any other usage
 504              would mean that this is not an invariant , since the pointer
 505              could then be passed as a parameter */
 506           if (POINTER_GET (ic) &&
 507               applyToSet (theLoop->regBlocks, hasNonPtrUse, IC_LEFT (ic)))
 508             continue;
 509
 510           /* if both the left & right are invariants : then check that */
 511           /* this definition exists in the out definition of all the  */
 512           /* blocks, this will ensure that this is not assigned any   */
 513           /* other value in the loop , and not used in this block     */
 514           /* prior to this definition which means only this definition */
 515           /* is used in this loop                                     */
 516           if (lin && rin && IC_RESULT (ic))
 517             {
 518               eBBlock *sBlock;
 519               set *lSet = setFromSet (theLoop->regBlocks);
 520
 521               /* if this block does not dominate all exists */
 522               /* make sure this defintion is not used anywhere else */
 523               if (!domsAllExits)
 524                 {
 525
 526                   if (isOperandGlobal (IC_RESULT (ic)))
 527                     continue;
 528                   /* for successors for all exits */
 529                   for (sBlock = setFirstItem (theLoop->exits); sBlock;
 530                        sBlock = setNextItem (theLoop->exits))
 531                     {
 532
 533                       for (i = 0; i < count; ebbs[i++]->visited = 0);
 534                       lBlock->visited = 1;
 535                       if (applyToSet (sBlock->succList, isDefAlive, ic))
 536                         break;
 537                     }
 538
 539                   /* we have found usage */
 540                   if (sBlock)
 541                     continue;
 542                 }
 543
 544               /* now make sure this is the only definition */
 545               for (sBlock = setFirstItem (lSet); sBlock;
 546                    sBlock = setNextItem (lSet))
 547                 {
 548                   /* if this is the block make sure the definition */
 549                   /* reaches the end of the block */
 550                   if (sBlock == lBlock)
 551                     {
 552                       if (!ifDiCodeIs (sBlock->outExprs, ic))
 553                         break;
 554                     }
 555                   else if (bitVectBitsInCommon (sBlock->defSet, OP_DEFS (IC_RESULT (ic))))
 556                     break;
 557                 }
 558
 559               if (sBlock)
 560                 continue;       /* another definition present in the block */
 561
 562               /* now check if it exists in the in of this block */
 563               /* if not then it was killed before this instruction */
 564               if (!bitVectBitValue (lBlock->inDefs, ic->key))
 565                 continue;
 566
 567               /* now we know it is a true invariant */
 568               /* remove it from the insts chain & put */
 569               /* in the invariant set                */
 570               OP_SYMBOL (IC_RESULT (ic))->isinvariant = 1;
 571               remiCodeFromeBBlock (lBlock, ic);
 572
 573               /* maintain the data flow */
 574               /* this means removing from definition from the */
 575               /* defset of this block and adding it to the    */
 576               /* inexpressions of all blocks within the loop  */
 577               bitVectUnSetBit (lBlock->defSet, ic->key);
 578               bitVectUnSetBit (lBlock->ldefs, ic->key);
 579               ivar = newCseDef (IC_RESULT (ic), ic);
 580               applyToSet (theLoop->regBlocks, addDefInExprs, ivar, ebbs, count);
 581               addSet (&lInvars, ivar);
 582             }
 583         }
 584     }                           /* for all loop blocks */
 585
 586   /* if we have some invariants then */
 587   if (lInvars)
 588     {
 589       eBBlock *preHdr = theLoop->entry->preHeader;
 590       iCode *icFirst = NULL, *icLast = NULL;
 591       cseDef *cdp;
 592
 593       /* create an iCode chain from it */
 594       for (cdp = setFirstItem (lInvars); cdp; cdp = setNextItem (lInvars))
 595         {
 596
 597           /* maintain data flow .. add it to the */
 598           /* ldefs defSet & outExprs of the preheader  */
 599           preHdr->defSet = bitVectSetBit (preHdr->defSet, cdp->diCode->key);
 600           preHdr->ldefs = bitVectSetBit (preHdr->ldefs, cdp->diCode->key);
 601           cdp->diCode->lineno = preHdr->ech->lineno;
 602           addSetHead (&preHdr->outExprs, cdp);
 603
 604
 605           if (!icFirst)
 606             icFirst = cdp->diCode;
 607           if (icLast)
 608             {
 609               icLast->next = cdp->diCode;
 610               cdp->diCode->prev = icLast;
 611               icLast = cdp->diCode;
 612             }
 613           else
 614             icLast = cdp->diCode;
 615           change++;
 616         }
 617
 618       /* add the instruction chain to the end of the
 619          preheader for this loop, preheaders will always
 620          have atleast a label */
 621       preHdr->ech->next = icFirst;
 622       icFirst->prev = preHdr->ech;
 623       preHdr->ech = icLast;
 624       icLast->next = NULL;
 625
 626     }
 627   return change;
 628 }
 629
 630 /*-----------------------------------------------------------------*/
 631 /* addressTaken - returns true if the symbol is found in the addrof */
 632 /*-----------------------------------------------------------------*/
 633 int
 634 addressTaken (set * sset, operand * sym)
 635 {
 636   set *loop;
 637   eBBlock *ebp;
 638   set *loop2;
 639
 640   for (loop = sset; loop; loop = loop->next)
 641     {
 642       ebp = loop->item;
 643       loop2 = ebp->addrOf;
 644       while (loop2)
 645         {
 646           if (isOperandEqual ((operand *) loop2->item, sym))
 647             return 1;
 648           loop2 = loop2->next;
 649         }
 650     }
 651
 652   return 0;
 653 }
 654
 655
 656 /*-----------------------------------------------------------------*/
 657 /* findInduction :- returns 1 & the item if the induction is found */
 658 /*-----------------------------------------------------------------*/
 659 DEFSETFUNC (findInduction)
 660 {
 661   induction *ip = item;
 662   V_ARG (operand *, sym);
 663   V_ARG (induction **, ipp);
 664
 665   if (isOperandEqual (ip->sym, sym))
 666     {
 667       *ipp = ip;
 668       return 1;
 669     }
 670
 671   return 0;
 672 }
 673
 674 /*-----------------------------------------------------------------*/
 675 /* findDefInRegion - finds the definition within the region        */
 676 /*-----------------------------------------------------------------*/
 677 iCode *
 678 findDefInRegion (set * regBlocks, operand * defOp, eBBlock ** owner)
 679 {
 680   eBBlock *lBlock;
 681
 682   /* for all blocks in the region */
 683   for (lBlock = setFirstItem (regBlocks); lBlock;
 684        lBlock = setNextItem (regBlocks))
 685     {
 686
 687       /* if a definition for this exists */
 688       if (bitVectBitsInCommon (lBlock->defSet, OP_DEFS (defOp)))
 689         {
 690           iCode *ic;
 691
 692           /* go thru the instruction chain to find it */
 693           for (ic = lBlock->sch; ic; ic = ic->next)
 694             if (bitVectBitValue (OP_DEFS (defOp), ic->key))
 695               {
 696                 if (owner)
 697                   *owner = lBlock;
 698                 return ic;
 699               }
 700         }
 701     }
 702
 703   return NULL;
 704 }
 705
 706 /*-----------------------------------------------------------------*/
 707 /* basicInduction - finds the basic induction variables in a loop  */
 708 /*-----------------------------------------------------------------*/
 709 set *
 710 basicInduction (region * loopReg, eBBlock ** ebbs, int count)
 711 {
 712   eBBlock *lBlock;
 713   set *indVars = NULL;
 714
 715   /* i.e. all assignments of the form a := a +/- const */
 716   /* for all blocks within the loop do */
 717   for (lBlock = setFirstItem (loopReg->regBlocks); lBlock;
 718        lBlock = setNextItem (loopReg->regBlocks))
 719     {
 720
 721       iCode *ic, *dic;
 722
 723       /* for all instructions in the blocks do */
 724       for (ic = lBlock->sch; ic; ic = ic->next)
 725         {
 726
 727           operand *aSym;
 728           unsigned long litValue;
 729           induction *ip;
 730           iCode *indIc;
 731           eBBlock *owner = NULL;
 732           int nexits;
 733
 734           /* look for assignments of the form */
 735           /*   symbolVar := iTempNN */
 736           if (ic->op != '=')
 737             continue;
 738
 739           if (!IS_TRUE_SYMOP (IC_RESULT (ic)) &&
 740               !OP_SYMBOL (IC_RESULT (ic))->isreqv)
 741             continue;
 742
 743           if (isOperandGlobal (IC_RESULT (ic)))
 744             continue;
 745
 746           if (!IS_ITEMP (IC_RIGHT (ic)))
 747             continue;
 748
 749           /* if it has multiple assignments within the loop then skip */
 750           if (assignmentsToSym (loopReg->regBlocks, IC_RESULT (ic)) > 1)
 751             continue;
 752
 753           /* if the address of this was taken inside the loop then continue */
 754           if (addressTaken (loopReg->regBlocks, IC_RESULT (ic)))
 755             continue;
 756
 757           /* find the definition for the result in the block */
 758           if (!(dic = findDefInRegion (setFromSet (loopReg->regBlocks),
 759                                        IC_RIGHT (ic), &owner)))
 760             continue;
 761
 762           /* if not +/- continue */
 763           if (dic->op != '+' && dic->op != '-')
 764             continue;
 765
 766           /* make sure definition is of the form  a +/- c */
 767           if (!IS_OP_LITERAL (IC_LEFT (dic)) && !IS_OP_LITERAL (IC_RIGHT (dic)))
 768             continue;
 769
 770           aSym = (IS_OP_LITERAL (IC_RIGHT (dic)) ?
 771               (litValue = (unsigned long) operandLitValue (IC_RIGHT (dic)), IC_LEFT (dic)) :
 772               (litValue = (unsigned long) operandLitValue (IC_LEFT (dic)), IC_RIGHT (dic)));
 773
 774           if (!isOperandEqual (IC_RESULT (ic), aSym) &&
 775               !isOperandEqual (IC_RIGHT (ic), aSym))
 776             {
 777               iCode *ddic;
 778               /* find the definition for this and check */
 779               if (!(ddic = findDefInRegion (setFromSet (loopReg->regBlocks),
 780                                             aSym, &owner)))
 781                 continue;
 782
 783               if (ddic->op != '=')
 784                 continue;
 785
 786               if (!isOperandEqual (IC_RESULT (ddic), aSym) ||
 787                   !isOperandEqual (IC_RIGHT (ddic), IC_RESULT (ic)))
 788                 continue;
 789             }
 790
 791           /* if the right hand side has more than one usage then
 792              don't make it an induction (will have to think some more) */
 793           if (bitVectnBitsOn (OP_USES (IC_RIGHT (ic))) > 1)
 794             continue;
 795
 796           /* if the definition is volatile then it cannot be
 797              an induction object */
 798           if (isOperandVolatile (IC_RIGHT (ic), FALSE) ||
 799               isOperandVolatile (IC_RESULT (ic), FALSE))
 800             continue;
 801
 802           /* whew !! that was a lot of work to find the definition */
 803           /* create an induction object */
 804           indIc = newiCode ('=', NULL, IC_RESULT (ic));
 805           indIc->lineno = ic->lineno;
 806           IC_RESULT (indIc) = operandFromOperand (IC_RIGHT (ic));
 807           IC_RESULT (indIc)->isaddr = 0;
 808           OP_SYMBOL (IC_RESULT (indIc))->isind = 1;
 809           ip = newInduction (IC_RIGHT (ic), dic->op, litValue, indIc, NULL);
 810
 811           /* replace the inducted variable by the iTemp */
 812           replaceSymBySym (loopReg->regBlocks, IC_RESULT (ic), IC_RIGHT (ic));
 813
 814           /* if it has only one exit then remove it from here
 815              and put it in the exit block */
 816           nexits = elementsInSet (loopReg->exits);
 817           if (nexits == 1)
 818             {
 819               eBBlock *exit = setFirstItem (loopReg->exits);
 820
 821               /* if it is the same block then there is no
 822                  need to move it about */
 823               if (exit != lBlock)
 824                 {
 825                   iCode *saveic = ic->prev;
 826                   /* remove it */
 827                   remiCodeFromeBBlock (lBlock, ic);
 828                   /* clear the definition */
 829                   bitVectUnSetBit (lBlock->defSet, ic->key);
 830                   /* add it to the exit */
 831                   addiCodeToeBBlock (exit, ic, NULL);
 832                   /* set the definition bit */
 833                   exit->defSet = bitVectSetBit (exit->defSet, ic->key);
 834                   ic = saveic;
 835                 }
 836             }
 837
 838           /* if the number of exits is greater than one then
 839              we use another trick ; we will create an intersection
 840              of succesors of the exits, then take those that are not
 841              part of the loop and have dfNumber greater loop entry
 842              and insert a new definition in them */
 843           if (nexits > 1)
 844             {
 845
 846               bitVect *loopSuccs = intersectLoopSucc (loopReg->exits, ebbs);
 847
 848               /* loopSuccs now contains intersection
 849                  of all the loops successors */
 850               if (loopSuccs)
 851                 {
 852                   int i;
 853                   for (i = 0; i < loopSuccs->size; i++)
 854                     {
 855                       if (bitVectBitValue (loopSuccs, i))
 856                         {
 857
 858                           eBBlock *eblock = ebbs[i];
 859
 860                           /* if the successor does not belong to the loop
 861                              and will be executed after the loop : then
 862                              add a definition to the block */
 863                           if (!isinSet (loopReg->regBlocks, eblock) &&
 864                               eblock->dfnum > loopReg->entry->dfnum)
 865                             {
 866                               /* create the definition */
 867                               iCode *newic = newiCode ('=', NULL,
 868                                         operandFromOperand (IC_RIGHT (ic)));
 869                               IC_RESULT (newic) = operandFromOperand (IC_RESULT (ic));
 870                               OP_DEFS(IC_RESULT (newic))=
 871                                 bitVectSetBit (OP_DEFS (IC_RESULT (newic)), newic->key);
 872                               OP_USES(IC_RIGHT (newic))=
 873                                 bitVectSetBit (OP_USES (IC_RIGHT (newic)), newic->key);
 874                               /* and add it */
 875                               if (eblock->sch && eblock->sch->op == LABEL)
 876                                 addiCodeToeBBlock (eblock, newic, eblock->sch->next);
 877                               else
 878                                 addiCodeToeBBlock (eblock, newic, eblock->sch);
 879                               /* set the definition bit */
 880                               eblock->defSet = bitVectSetBit (eblock->defSet, ic->key);
 881                             }
 882                         }
 883                     }
 884                 }
 885             }
 886
 887           addSet (&indVars, ip);
 888         }
 889
 890     }                           /* end of all blocks for basic induction variables */
 891
 892   return indVars;
 893 }
 894
 895 /*-----------------------------------------------------------------*/
 896 /* loopInduction - remove induction variables from a loop          */
 897 /*-----------------------------------------------------------------*/
 898 int
 899 loopInduction (region * loopReg, eBBlock ** ebbs, int count)
 900 {
 901   int change = 0;
 902   eBBlock *lBlock, *lastBlock = NULL;
 903   set *indVars = NULL;
 904   set *basicInd = NULL;
 905
 906   if (loopReg->entry->preHeader == NULL)
 907     return 0;
 908
 909   /* we first determine the basic Induction variables */
 910   basicInd = setFromSet (indVars = basicInduction (loopReg, ebbs, count));
 911
 912   /* find other induction variables : by other we mean definitions of */
 913   /* the form x := y (* | / ) <constant> .. we will move  this one to */
 914   /* beginning of the loop and reduce strength i.e. replace with +/-  */
 915   /* these expensive expressions: OH! and y must be induction too     */
 916   for (lBlock = setFirstItem (loopReg->regBlocks), lastBlock = lBlock;
 917        lBlock && indVars;
 918        lBlock = setNextItem (loopReg->regBlocks))
 919     {
 920
 921       iCode *ic, *indIc;
 922       induction *ip;
 923
 924       /* last block is the one with the highest block
 925          number */
 926       if (lastBlock->bbnum < lBlock->bbnum)
 927         lastBlock = lBlock;
 928
 929       for (ic = lBlock->sch; ic; ic = ic->next)
 930         {
 931           operand *aSym;
 932           unsigned long litVal;
 933           int lr = 0;
 934
 935           /* consider only * & / */
 936           if (ic->op != '*' && ic->op != '/')
 937             continue;
 938
 939           /* if the result has more definitions then */
 940           if (assignmentsToSym (loopReg->regBlocks, IC_RESULT (ic)) > 1)
 941             continue;
 942
 943           /* check if the operands are what we want */
 944           /* i.e. one of them an symbol the other a literal */
 945           if (!((IS_SYMOP (IC_LEFT (ic)) && IS_OP_LITERAL (IC_RIGHT (ic))) ||
 946                 (IS_OP_LITERAL (IC_LEFT (ic)) && IS_SYMOP (IC_RIGHT (ic)))))
 947             continue;
 948
 949           aSym = (IS_SYMOP (IC_LEFT (ic)) ?
 950           (lr = 1, litVal = (unsigned long) operandLitValue (IC_RIGHT (ic)), IC_LEFT (ic)) :
 951                   (litVal = (unsigned long) operandLitValue (IC_LEFT (ic)), IC_RIGHT (ic)));
 952
 953           ip = NULL;
 954           /* check if this is an induction variable */
 955           if (!applyToSetFTrue (basicInd, findInduction, aSym, &ip))
 956             continue;
 957
 958           /* ask port for size not worth if native instruction
 959              exist for multiply & divide */
 960           if (getSize (operandType (IC_LEFT (ic))) <= (unsigned long) port->support.muldiv ||
 961           getSize (operandType (IC_RIGHT (ic))) <= (unsigned long) port->support.muldiv)
 962             continue;
 963
 964           /* if this is a division then the remainder should be zero
 965              for it to be inducted */
 966           if (ic->op == '/' && (ip->cval % litVal))
 967             continue;
 968
 969           /* create the iCode to be placed in the loop header */
 970           /* and create the induction object */
 971
 972           /* create an instruction */
 973           /* this will be put on the loop header */
 974           indIc = newiCode (ic->op,
 975                             operandFromOperand (aSym),
 976                             operandFromLit (litVal));
 977           indIc->lineno = ic->lineno;
 978           IC_RESULT (indIc) = operandFromOperand (IC_RESULT (ic));
 979           OP_SYMBOL (IC_RESULT (indIc))->isind = 1;
 980
 981           /* keep track of the inductions */
 982           litVal = (ic->op == '*' ? (litVal * ip->cval) :
 983                     (ip->cval / litVal));
 984
 985           addSet (&indVars,
 986                 newInduction (IC_RESULT (ic), ip->op, litVal, indIc, NULL));
 987
 988           /* now change this instruction */
 989           ic->op = ip->op;
 990           if (lr)
 991             {
 992               IC_LEFT (ic) = operandFromOperand (IC_RESULT (ic));
 993               IC_RIGHT (ic) = operandFromLit (litVal);
 994             }
 995           else
 996             {
 997               IC_RIGHT (ic) = operandFromOperand (IC_RESULT (ic));
 998               IC_LEFT (ic) = operandFromLit (litVal);
 999             }
1000
1001           /* we need somemore initialisation code */
1002           /* we subtract the litVal from itself if increment */
1003           if (ic->op == '+')
1004             {
1005               indIc = newiCode ('-',
1006                                 operandFromOperand (IC_RESULT (ic)),
1007                                 operandFromLit (litVal));
1008               indIc->lineno = ic->lineno;
1009               IC_RESULT (indIc) = operandFromOperand (IC_RESULT (ic));
1010
1011               addSet (&indVars,
1012                 newInduction (IC_RESULT (ic), ip->op, litVal, indIc, NULL));
1013             }
1014         }
1015     }
1016
1017   /* if we have some induction variables then */
1018   if (indVars)
1019     {
1020       eBBlock *preHdr = loopReg->entry->preHeader;
1021       iCode *icFirst = NULL, *icLast = NULL;
1022       induction *ip;
1023       bitVect *indVect = NULL;
1024
1025       /* create an iCode chain from it */
1026       for (ip = setFirstItem (indVars);
1027            ip;
1028            ip = setNextItem (indVars))
1029         {
1030
1031           indVect = bitVectSetBit (indVect, ip->ic->key);
1032           ip->ic->lineno = preHdr->ech->lineno;
1033           if (!icFirst)
1034             icFirst = ip->ic;
1035           if (icLast)
1036             {
1037               icLast->next = ip->ic;
1038               ip->ic->prev = icLast;
1039               icLast = ip->ic;
1040             }
1041           else
1042             icLast = ip->ic;
1043           change++;
1044         }
1045
1046       /* add the instruction chain to the end of the */
1047       /* preheader for this loop                     */
1048       preHdr->ech->next = icFirst;
1049       icFirst->prev = preHdr->ech;
1050       preHdr->ech = icLast;
1051       icLast->next = NULL;
1052
1053       /* add the induction variable vector to the last
1054          block in the loop */
1055       lastBlock->isLastInLoop = 1;
1056       lastBlock->linds = bitVectUnion(lastBlock->linds,indVect);
1057     }
1058
1059   setToNull ((void *) &indVars);
1060   return change;
1061 }
1062
1063 /*-----------------------------------------------------------------*/
1064 /* mergeRegions - will merge region with same entry point           */
1065 /*-----------------------------------------------------------------*/
1066 DEFSETFUNC (mergeRegions)
1067 {
1068   region *theLoop = item;
1069   V_ARG (set *, allRegion);
1070   region *lp;
1071
1072   /* if this has already been merged then do nothing */
1073   if (theLoop->merged)
1074     return 0;
1075
1076   /* go thru all the region and check if any of them have the */
1077   /* entryPoint as the Loop                                  */
1078   for (lp = setFirstItem (allRegion); lp; lp = setNextItem (allRegion))
1079     {
1080
1081       if (lp == theLoop)
1082         continue;
1083
1084       if (lp->entry == theLoop->entry)
1085         {
1086           theLoop->regBlocks = unionSets (theLoop->regBlocks,
1087                                           lp->regBlocks, THROW_DEST);
1088           lp->merged = 1;
1089         }
1090     }
1091
1092   return 1;
1093 }
1094
1095 /*-----------------------------------------------------------------*/
1096 /* ifMerged - return 1 if the merge flag is 1                      */
1097 /*-----------------------------------------------------------------*/
1098 DEFSETFUNC (ifMerged)
1099 {
1100   region *lp = item;
1101
1102   return lp->merged;
1103 }
1104
1105 /*-----------------------------------------------------------------*/
1106 /* mergeInnerLoops - will merge into body when entry is present    */
1107 /*-----------------------------------------------------------------*/
1108 DEFSETFUNC (mergeInnerLoops)
1109 {
1110   region *theLoop = item;
1111   V_ARG (set *, allRegion);
1112   V_ARG (int *, maxDepth);
1113   region *lp;
1114
1115   /* check if the entry point is present in the body of any */
1116   /* loop then put the body of this loop into the outer loop */
1117   for (lp = setFirstItem (allRegion); lp; lp = setNextItem (allRegion))
1118     {
1119
1120       if (lp == theLoop)
1121         continue;
1122
1123       if (isinSet (lp->regBlocks, theLoop->entry))
1124         {
1125           lp->containsLoops += theLoop->containsLoops + 1;
1126           if (lp->containsLoops > (*maxDepth))
1127             *maxDepth = lp->containsLoops;
1128
1129           lp->regBlocks = unionSets (lp->regBlocks,
1130                                      theLoop->regBlocks, THROW_DEST);
1131         }
1132     }
1133
1134   return 1;
1135 }
1136
1137
1138 /*-----------------------------------------------------------------*/
1139 /* createLoopRegions - will detect and create a set of natural loops */
1140 /*-----------------------------------------------------------------*/
1141 hTab *
1142 createLoopRegions (eBBlock ** ebbs, int count)
1143 {
1144   set *allRegion = NULL;        /* set of all loops */
1145   hTab *orderedLoops = NULL;
1146   set *bEdges = NULL;
1147   int maxDepth = 0;
1148   region *lp;
1149
1150   /* get all the back edges in the graph */
1151   if (!applyToSet (graphEdges, backEdges, &bEdges))
1152     return 0;                   /* found no loops */
1153
1154   /* for each of these back edges get the blocks that */
1155   /* constitute the loops                             */
1156   applyToSet (bEdges, createLoop, &allRegion);
1157
1158   /* now we will create regions from these loops               */
1159   /* loops with the same entry points are considered to be the */
1160   /* same loop & they are merged. If the entry point of a loop */
1161   /* is found in the body of another loop then , all the blocks */
1162   /* in that loop are added to the loops containing the header */
1163   applyToSet (allRegion, mergeRegions, allRegion);
1164
1165   /* delete those already merged */
1166   deleteItemIf (&allRegion, ifMerged);
1167
1168   applyToSet (allRegion, mergeInnerLoops, allRegion, &maxDepth);
1169   maxDepth++;
1170
1171   /* now create all the exits .. also */
1172   /* create an ordered set of loops   */
1173   /* i.e. we process loops in the inner to outer order */
1174   for (lp = setFirstItem (allRegion); lp; lp = setNextItem (allRegion))
1175     {
1176       applyToSet (lp->regBlocks, addToExitsMarkDepth,
1177                   lp->regBlocks, &lp->exits,
1178                   (maxDepth - lp->containsLoops), lp);
1179
1180       hTabAddItem (&orderedLoops, lp->containsLoops, lp);
1181
1182     }
1183   return orderedLoops;
1184 }
1185
1186 /*-----------------------------------------------------------------*/
1187 /* loopOptimizations - identify region & remove invariants & ind   */
1188 /*-----------------------------------------------------------------*/
1189 int
1190 loopOptimizations (hTab * orderedLoops, eBBlock ** ebbs, int count)
1191 {
1192   region *lp;
1193   int change = 0;
1194   int k;
1195
1196   /* if no loop optimizations requested */
1197   if (!optimize.loopInvariant &&
1198       !optimize.loopInduction)
1199     return 0;
1200
1201   /* now we process the loops inner to outer order */
1202   /* this is essential to maintain data flow information */
1203   /* the other choice is an ugly iteration for the depth */
1204   /* of the loops would hate that */
1205   for (lp = hTabFirstItem (orderedLoops, &k); lp;
1206        lp = hTabNextItem (orderedLoops, &k))
1207     {
1208
1209       if (optimize.loopInvariant)
1210         change += loopInvariants (lp, ebbs, count);
1211
1212       if (optimize.loopInduction)
1213         change += loopInduction (lp, ebbs, count);
1214     }
1215
1216   return change;
1217 }