gcc/loop-invariant.c

   1 /* Rtl-level loop invariant motion.
   2    Copyright (C) 2004 Free Software Foundation, Inc.
   3
   4 This file is part of GCC.
   5
   6 GCC is free software; you can redistribute it and/or modify it
   7 under the terms of the GNU General Public License as published by the
   8 Free Software Foundation; either version 2, or (at your option) any
   9 later version.
  10
  11 GCC is distributed in the hope that it will be useful, but WITHOUT
  12 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  14 for more details.
  15
  16 You should have received a copy of the GNU General Public License
  17 along with GCC; see the file COPYING.  If not, write to the Free
  18 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
  19 02111-1307, USA.  */
  20
  21 /* This implements the loop invariant motion pass.  It is very simple
  22    (no calls, libcalls, etc.).  This should be sufficient to cleanup things like
  23    address arithmetics -- other more complicated invariants should be
  24    eliminated on tree level either in tree-ssa-loop-im.c or in tree-ssa-pre.c.
  25
  26    We proceed loop by loop -- it is simpler than trying to handle things
  27    globally and should not lose much.  First we inspect all sets inside loop
  28    and create a dependency graph on insns (saying "to move this insn, you must
  29    also move the following insns").
  30
  31    We then need to determine what to move.  We estimate the number of registers
  32    used and move as many invariants as possible while we still have enough free
  33    registers.  We prefer the expensive invariants.
  34
  35    Then we move the selected invariants out of the loop, creating a new
  36    temporaries for them if necessary.  */
  37
  38 #include "config.h"
  39 #include "system.h"
  40 #include "coretypes.h"
  41 #include "tm.h"
  42 #include "rtl.h"
  43 #include "hard-reg-set.h"
  44 #include "basic-block.h"
  45 #include "cfgloop.h"
  46 #include "expr.h"
  47 #include "output.h"
  48 #include "function.h"
  49 #include "flags.h"
  50 #include "df.h"
  51
  52 /* The data stored for the loop.  */
  53
  54 struct loop_data
  55 {
  56   struct loop *outermost_exit;  /* The outermost exit of the loop.  */
  57   bool has_call;                /* True if the loop contains a call.  */
  58 };
  59
  60 #define LOOP_DATA(LOOP) ((struct loop_data *) (LOOP)->aux)
  61
  62 /* The description of an use.  */
  63
  64 struct use
  65 {
  66   rtx *pos;                     /* Position of the use.  */
  67   rtx insn;                     /* The insn in that the use occurs.  */
  68
  69   struct use *next;             /* Next use in the list.  */
  70 };
  71
  72 /* The description of a def.  */
  73
  74 struct def
  75 {
  76   struct use *uses;             /* The list of uses that are uniquely reached
  77                                    by it.  */
  78   unsigned n_uses;              /* Number of such uses.  */
  79   unsigned invno;               /* The corresponding invariant.  */
  80 };
  81
  82 /* The data stored for each invariant.  */
  83
  84 struct invariant
  85 {
  86   /* The number of the invariant.  */
  87   unsigned invno;
  88
  89   /* Whether we already processed the invariant.  */
  90   bool processed;
  91
  92   /* The definition of the invariant.  */
  93   struct def *def;
  94
  95   /* The insn in that it is defined.  */
  96   rtx insn;
  97
  98   /* Whether it is always executed.  */
  99   bool always_executed;
 100
 101   /* Whether to move the invariant.  */
 102   bool move;
 103
 104   /* Cost if the invariant.  */
 105   unsigned cost;
 106
 107   /* The invariants it depends on.  */
 108   bitmap depends_on;
 109
 110   /* Used for detecting already visited invariants during determining
 111      costs of movements.  */
 112   unsigned stamp;
 113 };
 114
 115 /* The actual stamp for marking already visited invariants during determining
 116    costs of movements.  */
 117
 118 static unsigned actual_stamp;
 119
 120 /* The invariants.  */
 121
 122 static varray_type invariants;
 123
 124 /* Test for possibility of invariantness of X.  */
 125
 126 static bool
 127 check_maybe_invariant (rtx x)
 128 {
 129   enum rtx_code code = GET_CODE (x);
 130   int i, j;
 131   const char *fmt;
 132
 133   switch (code)
 134     {
 135     case CONST_INT:
 136     case CONST_DOUBLE:
 137     case SYMBOL_REF:
 138     case CONST:
 139     case LABEL_REF:
 140       return true;
 141
 142     case PC:
 143     case CC0:
 144     case UNSPEC_VOLATILE:
 145     case CALL:
 146       return false;
 147
 148     case REG:
 149       return true;
 150
 151     case MEM:
 152       /* Load/store motion is done elsewhere.  ??? Perhaps also add it here?
 153          It should not be hard, and might be faster than "elsewhere".  */
 154
 155       /* Just handle the most trivial case where we load from an unchanging
 156          location (most importantly, pic tables).  */
 157       if (MEM_READONLY_P (x))
 158         break;
 159
 160       return false;
 161
 162     case ASM_OPERANDS:
 163       /* Don't mess with insns declared volatile.  */
 164       if (MEM_VOLATILE_P (x))
 165         return false;
 166       break;
 167
 168     default:
 169       break;
 170     }
 171
 172   fmt = GET_RTX_FORMAT (code);
 173   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
 174     {
 175       if (fmt[i] == 'e')
 176         {
 177           if (!check_maybe_invariant (XEXP (x, i)))
 178             return false;
 179         }
 180       else if (fmt[i] == 'E')
 181         {
 182           for (j = 0; j < XVECLEN (x, i); j++)
 183             if (!check_maybe_invariant (XVECEXP (x, i, j)))
 184               return false;
 185         }
 186     }
 187
 188   return true;
 189 }
 190
 191 /* Determines the basic blocks inside LOOP that are always executed and
 192    stores their bitmap to ALWAYS_REACHED.  MAY_EXIT is a bitmap of
 193    basic blocks that may either exit the loop, or contain the call that
 194    does not have to return.  BODY is body of the loop obtained by
 195    get_loop_body_in_dom_order.  */
 196
 197 static void
 198 compute_always_reached (struct loop *loop, basic_block *body,
 199                         bitmap may_exit, bitmap always_reached)
 200 {
 201   unsigned i;
 202
 203   for (i = 0; i < loop->num_nodes; i++)
 204     {
 205       if (dominated_by_p (CDI_DOMINATORS, loop->latch, body[i]))
 206         bitmap_set_bit (always_reached, i);
 207
 208       if (bitmap_bit_p (may_exit, i))
 209         return;
 210     }
 211 }
 212
 213 /* Finds exits out of the LOOP with body BODY.  Marks blocks in that we may
 214    exit the loop by cfg edge to HAS_EXIT and MAY_EXIT.  In MAY_EXIT
 215    additionally mark blocks that may exit due to a call.  */
 216
 217 static void
 218 find_exits (struct loop *loop, basic_block *body,
 219             bitmap may_exit, bitmap has_exit)
 220 {
 221   unsigned i;
 222   edge e;
 223   struct loop *outermost_exit = loop, *aexit;
 224   bool has_call = false;
 225   rtx insn;
 226
 227   for (i = 0; i < loop->num_nodes; i++)
 228     {
 229       if (body[i]->loop_father == loop)
 230         {
 231           FOR_BB_INSNS (body[i], insn)
 232             {
 233               if (CALL_P (insn)
 234                   && !CONST_OR_PURE_CALL_P (insn))
 235                 {
 236                   has_call = true;
 237                   bitmap_set_bit (may_exit, i);
 238                   break;
 239                 }
 240             }
 241
 242           for (e = body[i]->succ; e; e = e->succ_next)
 243             {
 244               if (flow_bb_inside_loop_p (loop, e->dest))
 245                 continue;
 246
 247               bitmap_set_bit (may_exit, i);
 248               bitmap_set_bit (has_exit, i);
 249               outermost_exit = find_common_loop (outermost_exit,
 250                                                  e->dest->loop_father);
 251             }
 252           continue;
 253         }
 254
 255       /* Use the data stored for the subloop to decide whether we may exit
 256          through it.  It is sufficient to do this for header of the loop,
 257          as other basic blocks inside it must be dominated by it.  */
 258       if (body[i]->loop_father->header != body[i])
 259         continue;
 260
 261       if (LOOP_DATA (body[i]->loop_father)->has_call)
 262         {
 263           has_call = true;
 264           bitmap_set_bit (may_exit, i);
 265         }
 266       aexit = LOOP_DATA (body[i]->loop_father)->outermost_exit;
 267       if (aexit != loop)
 268         {
 269           bitmap_set_bit (may_exit, i);
 270           bitmap_set_bit (has_exit, i);
 271
 272           if (flow_loop_nested_p (aexit, outermost_exit))
 273             outermost_exit = aexit;
 274         }
 275     }
 276
 277   loop->aux = xcalloc (1, sizeof (struct loop_data));
 278   LOOP_DATA (loop)->outermost_exit = outermost_exit;
 279   LOOP_DATA (loop)->has_call = has_call;
 280 }
 281
 282 /* Check whether we may assign a value to X from a register.  */
 283
 284 static bool
 285 may_assign_reg_p (rtx x)
 286 {
 287   return can_copy_p (GET_MODE (x));
 288 }
 289
 290 /* Finds definitions that may correspond to invariants in LOOP with body BODY.
 291    DF is the dataflow object.  */
 292
 293 static void
 294 find_defs (struct loop *loop, basic_block *body, struct df *df)
 295 {
 296   unsigned i;
 297   bitmap blocks = BITMAP_XMALLOC ();
 298
 299   for (i = 0; i < loop->num_nodes; i++)
 300     bitmap_set_bit (blocks, body[i]->index);
 301
 302   df_analyze_subcfg (df, blocks, DF_UD_CHAIN | DF_HARD_REGS | DF_EQUIV_NOTES);
 303   BITMAP_XFREE (blocks);
 304 }
 305
 306 /* Creates a new invariant for definition DEF in INSN, depending on invariants
 307    in DEPENDS_ON.  ALWAYS_EXECUTED is true if the insn is always executed,
 308    unless the program ends due to a function call.  */
 309
 310 static void
 311 create_new_invariant (struct def *def, rtx insn, bitmap depends_on,
 312                       bool always_executed)
 313 {
 314   struct invariant *inv = xmalloc (sizeof (struct invariant));
 315   rtx set = single_set (insn);
 316
 317   inv->def = def;
 318   inv->always_executed = always_executed;
 319   inv->depends_on = depends_on;
 320
 321   /* If the set is simple, usually by moving it we move the whole store out of
 322      the loop.  Otherwise we save only cost of the computation.  */
 323   if (def)
 324     inv->cost = rtx_cost (set, SET);
 325   else
 326     inv->cost = rtx_cost (SET_SRC (set), SET);
 327
 328   inv->move = false;
 329   inv->processed = false;
 330   inv->stamp = 0;
 331   inv->insn = insn;
 332
 333   inv->invno = VARRAY_ACTIVE_SIZE (invariants);
 334   if (def)
 335     def->invno = inv->invno;
 336   VARRAY_PUSH_GENERIC_PTR_NOGC (invariants, inv);
 337
 338   if (dump_file)
 339     {
 340       fprintf (dump_file,
 341                "Set in insn %d is invariant (%d), cost %d, depends on ",
 342                INSN_UID (insn), inv->invno, inv->cost);
 343       dump_bitmap (dump_file, inv->depends_on);
 344     }
 345 }
 346
 347 /* Record USE at DEF.  */
 348
 349 static void
 350 record_use (struct def *def, rtx *use, rtx insn)
 351 {
 352   struct use *u = xmalloc (sizeof (struct use));
 353
 354   if (GET_CODE (*use) == SUBREG)
 355     use = &SUBREG_REG (*use);
 356   gcc_assert (REG_P (*use));
 357
 358   u->pos = use;
 359   u->insn = insn;
 360   u->next = def->uses;
 361   def->uses = u;
 362   def->n_uses++;
 363 }
 364
 365 /* Finds the invariants INSN depends on and store them to the DEPENDS_ON
 366    bitmap.  DF is the dataflow object.  */
 367
 368 static bool
 369 check_dependencies (rtx insn, struct df *df, bitmap depends_on)
 370 {
 371   struct df_link *uses, *defs;
 372   struct ref *use, *def;
 373   basic_block bb = BLOCK_FOR_INSN (insn), def_bb;
 374   struct def *def_data;
 375
 376   for (uses = DF_INSN_USES (df, insn); uses; uses = uses->next)
 377     {
 378       use = uses->ref;
 379
 380       defs = DF_REF_CHAIN (use);
 381       if (!defs)
 382         continue;
 383
 384       if (defs->next)
 385         return false;
 386
 387       def = defs->ref;
 388       def_data = DF_REF_DATA (def);
 389       if (!def_data)
 390         return false;
 391
 392       def_bb = DF_REF_BB (def);
 393       if (!dominated_by_p (CDI_DOMINATORS, bb, def_bb))
 394         return false;
 395
 396       bitmap_set_bit (depends_on, def_data->invno);
 397     }
 398
 399   return true;
 400 }
 401
 402 /* Finds invariant in INSN.  ALWAYS_REACHED is true if the insn is always
 403    executed.  ALWAYS_EXECUTED is true if the insn is always executed,
 404    unless the program ends due to a function call.  DF is the dataflow
 405    object.  */
 406
 407 static void
 408 find_invariant_insn (rtx insn, bool always_reached, bool always_executed,
 409                      struct df *df)
 410 {
 411   struct ref *ref;
 412   struct def *def;
 413   bitmap depends_on;
 414   rtx set, dest;
 415   bool simple = true;
 416
 417   /* Until we get rid of LIBCALLS.  */
 418   if (find_reg_note (insn, REG_RETVAL, NULL_RTX)
 419       || find_reg_note (insn, REG_LIBCALL, NULL_RTX)
 420       || find_reg_note (insn, REG_NO_CONFLICT, NULL_RTX))
 421     return;
 422
 423   set = single_set (insn);
 424   if (!set)
 425     return;
 426   dest = SET_DEST (set);
 427
 428   if (GET_CODE (dest) != REG
 429       || HARD_REGISTER_P (dest))
 430     simple = false;
 431
 432   if (!check_maybe_invariant (SET_SRC (set))
 433       || !may_assign_reg_p (SET_DEST (set)))
 434     return;
 435
 436   if (may_trap_p (PATTERN (insn)))
 437     {
 438       if (!always_reached)
 439         return;
 440
 441       /* Unless the exceptions are handled, the behavior is undefined
 442          if the trap occurs.  */
 443       if (flag_non_call_exceptions)
 444         return;
 445     }
 446
 447   depends_on = BITMAP_XMALLOC ();
 448   if (!check_dependencies (insn, df, depends_on))
 449     {
 450       BITMAP_XFREE (depends_on);
 451       return;
 452     }
 453
 454   if (simple)
 455     {
 456       ref = df_find_def (df, insn, dest);
 457       def = xcalloc (1, sizeof (struct def));
 458       DF_REF_DATA (ref) = def;
 459     }
 460   else
 461     def = NULL;
 462
 463   create_new_invariant (def, insn, depends_on, always_executed);
 464 }
 465
 466 /* Record registers used in INSN that have an unique invariant definition.
 467    DF is the dataflow object.  */
 468
 469 static void
 470 record_uses (rtx insn, struct df *df)
 471 {
 472   struct df_link *uses, *defs;
 473   struct ref *use, *def;
 474   basic_block bb = BLOCK_FOR_INSN (insn), def_bb;
 475
 476   for (uses = DF_INSN_USES (df, insn); uses; uses = uses->next)
 477     {
 478       use = uses->ref;
 479
 480       defs = DF_REF_CHAIN (use);
 481       if (!defs || defs->next)
 482         continue;
 483       def = defs->ref;
 484       if (!DF_REF_DATA (def))
 485         continue;
 486
 487       def_bb = DF_REF_BB (def);
 488       if (!dominated_by_p (CDI_DOMINATORS, bb, def_bb))
 489         continue;
 490
 491       record_use (DF_REF_DATA (def), DF_REF_LOC (use), DF_REF_INSN (use));
 492     }
 493 }
 494
 495 /* Finds invariants in INSN.  ALWAYS_REACHED is true if the insn is always
 496    executed.  ALWAYS_EXECUTED is true if the insn is always executed,
 497    unless the program ends due to a function call.  DF is the dataflow
 498    object.  */
 499
 500 static void
 501 find_invariants_insn (rtx insn, bool always_reached, bool always_executed,
 502                       struct df *df)
 503 {
 504   find_invariant_insn (insn, always_reached, always_executed, df);
 505   record_uses (insn, df);
 506 }
 507
 508 /* Finds invariants in basic block BB.  ALWAYS_REACHED is true if the
 509    basic block is always executed.  ALWAYS_EXECUTED is true if the basic
 510    block is always executed, unless the program ends due to a function
 511    call.  DF is the dataflow object.  */
 512
 513 static void
 514 find_invariants_bb (basic_block bb, bool always_reached, bool always_executed,
 515                     struct df *df)
 516 {
 517   rtx insn;
 518
 519   FOR_BB_INSNS (bb, insn)
 520     {
 521       if (!INSN_P (insn))
 522         continue;
 523
 524       find_invariants_insn (insn, always_reached, always_executed, df);
 525
 526       if (always_reached
 527           && CALL_P (insn)
 528           && !CONST_OR_PURE_CALL_P (insn))
 529         always_reached = false;
 530     }
 531 }
 532
 533 /* Finds invariants in LOOP with body BODY.  ALWAYS_REACHED is the bitmap of
 534    basic blocks in BODY that are always executed.  ALWAYS_EXECUTED is the
 535    bitmap of basic blocks in BODY that are always executed unless the program
 536    ends due to a function call.  DF is the dataflow object.  */
 537
 538 static void
 539 find_invariants_body (struct loop *loop, basic_block *body,
 540                       bitmap always_reached, bitmap always_executed,
 541                       struct df *df)
 542 {
 543   unsigned i;
 544
 545   for (i = 0; i < loop->num_nodes; i++)
 546     find_invariants_bb (body[i],
 547                         bitmap_bit_p (always_reached, i),
 548                         bitmap_bit_p (always_executed, i),
 549                         df);
 550 }
 551
 552 /* Finds invariants in LOOP.  DF is the dataflow object.  */
 553
 554 static void
 555 find_invariants (struct loop *loop, struct df *df)
 556 {
 557   bitmap may_exit = BITMAP_XMALLOC ();
 558   bitmap always_reached = BITMAP_XMALLOC ();
 559   bitmap has_exit = BITMAP_XMALLOC ();
 560   bitmap always_executed = BITMAP_XMALLOC ();
 561   basic_block *body = get_loop_body_in_dom_order (loop);
 562
 563   find_exits (loop, body, may_exit, has_exit);
 564   compute_always_reached (loop, body, may_exit, always_reached);
 565   compute_always_reached (loop, body, has_exit, always_executed);
 566
 567   find_defs (loop, body, df);
 568   find_invariants_body (loop, body, always_reached, always_executed, df);
 569
 570   BITMAP_XFREE (always_reached);
 571   BITMAP_XFREE (always_executed);
 572   BITMAP_XFREE (may_exit);
 573   BITMAP_XFREE (has_exit);
 574   free (body);
 575 }
 576
 577 /* Frees a list of uses USE.  */
 578
 579 static void
 580 free_use_list (struct use *use)
 581 {
 582   struct use *next;
 583
 584   for (; use; use = next)
 585     {
 586       next = use->next;
 587       free (use);
 588     }
 589 }
 590
 591 /* Calculates cost and number of registers needed for moving invariant INV
 592    out of the loop and stores them to *COST and *REGS_NEEDED.  */
 593
 594 static void
 595 get_inv_cost (struct invariant *inv, int *comp_cost, unsigned *regs_needed)
 596 {
 597   int acomp_cost;
 598   unsigned aregs_needed;
 599   unsigned depno;
 600   struct invariant *dep;
 601
 602   *comp_cost = 0;
 603   *regs_needed = 0;
 604   if (inv->move
 605       || inv->stamp == actual_stamp)
 606     return;
 607   inv->stamp = actual_stamp;
 608
 609   (*regs_needed)++;
 610   (*comp_cost) += inv->cost;
 611
 612   EXECUTE_IF_SET_IN_BITMAP (inv->depends_on, 0, depno,
 613     {
 614       dep = VARRAY_GENERIC_PTR_NOGC (invariants, depno);
 615
 616       get_inv_cost (dep, &acomp_cost, &aregs_needed);
 617
 618       if (aregs_needed
 619           /* We need to check always_executed, since if the original value of
 620              the invariant may be preserved, we may need to keep it in a
 621              separate register.  TODO check whether the register has an
 622              use outside of the loop.  */
 623           && dep->always_executed
 624           && !dep->def->uses->next)
 625         {
 626           /* If this is a single use, after moving the dependency we will not
 627              need a new register.  */
 628           aregs_needed--;
 629         }
 630
 631       (*regs_needed) += aregs_needed;
 632       (*comp_cost) += acomp_cost;
 633     });
 634 }
 635
 636 /* Calculates gain for eliminating invariant INV.  REGS_USED is the number
 637    of registers used in the loop, N_INV_USES is the number of uses of
 638    invariants, NEW_REGS is the number of new variables already added due to
 639    the invariant motion.  The number of registers needed for it is stored in
 640    *REGS_NEEDED.  */
 641
 642 static int
 643 gain_for_invariant (struct invariant *inv, unsigned *regs_needed,
 644                     unsigned new_regs, unsigned regs_used, unsigned n_inv_uses)
 645 {
 646   int comp_cost, size_cost;
 647
 648   get_inv_cost (inv, &comp_cost, regs_needed);
 649   actual_stamp++;
 650
 651   size_cost = (global_cost_for_size (new_regs + *regs_needed,
 652                                      regs_used, n_inv_uses)
 653                - global_cost_for_size (new_regs, regs_used, n_inv_uses));
 654
 655   return comp_cost - size_cost;
 656 }
 657
 658 /* Finds invariant with best gain for moving.  Returns the gain, stores
 659    the invariant in *BEST and number of registers needed for it to
 660    *REGS_NEEDED.  REGS_USED is the number of registers used in
 661    the loop, N_INV_USES is the number of uses of invariants.  NEW_REGS
 662    is the number of new variables already added due to invariant motion.  */
 663
 664 static int
 665 best_gain_for_invariant (struct invariant **best, unsigned *regs_needed,
 666                          unsigned new_regs, unsigned regs_used,
 667                          unsigned n_inv_uses)
 668 {
 669   struct invariant *inv;
 670   int gain = 0, again;
 671   unsigned aregs_needed, invno;
 672
 673   for (invno = 0; invno < VARRAY_ACTIVE_SIZE (invariants); invno++)
 674     {
 675       inv = VARRAY_GENERIC_PTR_NOGC (invariants, invno);
 676       if (inv->move)
 677         continue;
 678
 679       again = gain_for_invariant (inv, &aregs_needed,
 680                                   new_regs, regs_used, n_inv_uses);
 681       if (again > gain)
 682         {
 683           gain = again;
 684           *best = inv;
 685           *regs_needed = aregs_needed;
 686         }
 687     }
 688
 689   return gain;
 690 }
 691
 692 /* Marks invariant INVNO and all its dependencies for moving.  */
 693
 694 static void
 695 set_move_mark (unsigned invno)
 696 {
 697   struct invariant *inv = VARRAY_GENERIC_PTR_NOGC (invariants, invno);
 698
 699   if (inv->move)
 700     return;
 701   inv->move = true;
 702
 703   if (dump_file)
 704     fprintf (dump_file, "Decided to move invariant %d\n", invno);
 705
 706   EXECUTE_IF_SET_IN_BITMAP (inv->depends_on, 0, invno, set_move_mark (invno));
 707 }
 708
 709 /* Determines which invariants to move.  DF is the dataflow object.  */
 710
 711 static void
 712 find_invariants_to_move (struct df *df)
 713 {
 714   unsigned i, regs_used, n_inv_uses, regs_needed = 0, new_regs;
 715   struct invariant *inv = NULL;
 716
 717   if (flag_move_all_movables)
 718     {
 719       /* This is easy & stupid.  */
 720       for (i = 0; i < VARRAY_ACTIVE_SIZE (invariants); i++)
 721         {
 722           inv = VARRAY_GENERIC_PTR_NOGC (invariants, i);
 723           inv->move = true;
 724         }
 725       return;
 726     }
 727
 728   if (!VARRAY_ACTIVE_SIZE (invariants))
 729     return;
 730
 731   /* Now something slightly more involved.  First estimate the number of used
 732      registers.  */
 733   n_inv_uses = 0;
 734
 735   /* We do not really do a good job in this estimation; put some initial bound
 736      here to stand for induction variables etc. that we do not detect.  */
 737   regs_used = 2;
 738
 739   for (i = 0; i < df->n_regs; i++)
 740     {
 741       if (!DF_REGNO_FIRST_DEF (df, i) && DF_REGNO_LAST_USE (df, i))
 742         {
 743           /* This is a value that is used but not changed inside loop.  */
 744           regs_used++;
 745         }
 746     }
 747
 748   for (i = 0; i < VARRAY_ACTIVE_SIZE (invariants); i++)
 749     {
 750       inv = VARRAY_GENERIC_PTR_NOGC (invariants, i);
 751       if (inv->def)
 752         n_inv_uses += inv->def->n_uses;
 753     }
 754
 755   new_regs = 0;
 756   while (best_gain_for_invariant (&inv, &regs_needed,
 757                                   new_regs, regs_used, n_inv_uses) > 0)
 758     {
 759       set_move_mark (inv->invno);
 760       new_regs += regs_needed;
 761     }
 762 }
 763
 764 /* Move invariant INVNO out of the LOOP.  DF is the dataflow object.  */
 765
 766 static void
 767 move_invariant_reg (struct loop *loop, unsigned invno, struct df *df)
 768 {
 769   struct invariant *inv = VARRAY_GENERIC_PTR_NOGC (invariants, invno);
 770   unsigned i;
 771   basic_block preheader = loop_preheader_edge (loop)->src;
 772   rtx reg, set;
 773   struct use *use;
 774
 775   if (inv->processed)
 776     return;
 777   inv->processed = true;
 778
 779   if (inv->depends_on)
 780     {
 781       EXECUTE_IF_SET_IN_BITMAP (inv->depends_on, 0, i,
 782         {
 783           move_invariant_reg (loop, i, df);
 784         });
 785     }
 786
 787   /* Move the set out of the loop.  If the set is always executed (we could
 788      omit this condition if we know that the register is unused outside of the
 789      loop, but it does not seem worth finding out) and it has no uses that
 790      would not be dominated by it, we may just move it (TODO).  Otherwise we
 791      need to create a temporary register.  */
 792   set = single_set (inv->insn);
 793   reg = gen_reg_rtx (GET_MODE (SET_DEST (set)));
 794   df_pattern_emit_after (df, gen_move_insn (SET_DEST (set), reg),
 795                          BLOCK_FOR_INSN (inv->insn), inv->insn);
 796   SET_DEST (set) = reg;
 797   reorder_insns (inv->insn, inv->insn, BB_END (preheader));
 798   df_insn_modify (df, preheader, inv->insn);
 799
 800   /* Replace the uses we know to be dominated.  It saves work for copy
 801      propagation, and also it is necessary so that dependent invariants
 802      are computed right.  */
 803   if (inv->def)
 804     {
 805       for (use = inv->def->uses; use; use = use->next)
 806         {
 807           *use->pos = reg;
 808           df_insn_modify (df, BLOCK_FOR_INSN (use->insn), use->insn);
 809         }
 810     }
 811 }
 812
 813 /* Move selected invariant out of the LOOP.  Newly created regs are marked
 814    in TEMPORARY_REGS.  DF is the dataflow object.  */
 815
 816 static void
 817 move_invariants (struct loop *loop, struct df *df)
 818 {
 819   struct invariant *inv;
 820   unsigned i;
 821
 822   for (i = 0; i < VARRAY_ACTIVE_SIZE (invariants); i++)
 823     {
 824       inv = VARRAY_GENERIC_PTR_NOGC (invariants, i);
 825       if (inv->move)
 826         move_invariant_reg (loop, i, df);
 827     }
 828 }
 829
 830 /* Initializes invariant motion data.  */
 831
 832 static void
 833 init_inv_motion_data (void)
 834 {
 835   actual_stamp = 1;
 836
 837   if (!invariants)
 838     VARRAY_GENERIC_PTR_NOGC_INIT (invariants, 100, "invariants");
 839 }
 840
 841 /* Frees the data allocated by invariant motion.  DF is the dataflow
 842    object.  */
 843
 844 static void
 845 free_inv_motion_data (struct df *df)
 846 {
 847   unsigned i;
 848   struct def *def;
 849   struct invariant *inv;
 850
 851   for (i = 0; i < df->n_defs; i++)
 852     {
 853       if (!df->defs[i])
 854         continue;
 855
 856       def = DF_REF_DATA (df->defs[i]);
 857       if (!def)
 858         continue;
 859
 860       free_use_list (def->uses);
 861       free (def);
 862       DF_REF_DATA (df->defs[i]) = NULL;
 863     }
 864
 865   for (i = 0; i < VARRAY_ACTIVE_SIZE (invariants); i++)
 866     {
 867       inv = VARRAY_GENERIC_PTR_NOGC (invariants, i);
 868       BITMAP_XFREE (inv->depends_on);
 869       free (inv);
 870     }
 871   VARRAY_POP_ALL (invariants);
 872 }
 873
 874 /* Move the invariants out of the LOOP.  DF is the dataflow object.  */
 875
 876 static void
 877 move_single_loop_invariants (struct loop *loop, struct df *df)
 878 {
 879   init_inv_motion_data ();
 880
 881   find_invariants (loop, df);
 882   find_invariants_to_move (df);
 883   move_invariants (loop, df);
 884
 885   free_inv_motion_data (df);
 886 }
 887
 888 /* Releases the auxiliary data for LOOP.  */
 889
 890 static void
 891 free_loop_data (struct loop *loop)
 892 {
 893   struct loop_data *data = LOOP_DATA (loop);
 894
 895   free (data);
 896   loop->aux = NULL;
 897 }
 898
 899 /* Move the invariants out of the LOOPS.  */
 900
 901 void
 902 move_loop_invariants (struct loops *loops)
 903 {
 904   struct loop *loop;
 905   unsigned i;
 906   struct df *df = df_init ();
 907
 908   /* Process the loops, innermost first.  */
 909   loop = loops->tree_root;
 910   while (loop->inner)
 911     loop = loop->inner;
 912
 913   while (loop != loops->tree_root)
 914     {
 915       move_single_loop_invariants (loop, df);
 916
 917       if (loop->next)
 918         {
 919           loop = loop->next;
 920           while (loop->inner)
 921             loop = loop->inner;
 922         }
 923       else
 924         loop = loop->outer;
 925     }
 926
 927   for (i = 1; i < loops->num; i++)
 928     if (loops->parray[i])
 929       free_loop_data (loops->parray[i]);
 930
 931   df_finish (df);
 932 }