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 (RTX_UNCHANGING_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 (GET_CODE (insn) == CALL_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   if (!REG_P (*use))
 357     abort ();
 358
 359   u->pos = use;
 360   u->insn = insn;
 361   u->next = def->uses;
 362   def->uses = u;
 363   def->n_uses++;
 364 }
 365
 366 /* Finds the invariants INSN depends on and store them to the DEPENDS_ON
 367    bitmap.  DF is the dataflow object.  */
 368
 369 static bool
 370 check_dependencies (rtx insn, struct df *df, bitmap depends_on)
 371 {
 372   struct df_link *uses, *defs;
 373   struct ref *use, *def;
 374   basic_block bb = BLOCK_FOR_INSN (insn), def_bb;
 375   struct def *def_data;
 376
 377   for (uses = DF_INSN_USES (df, insn); uses; uses = uses->next)
 378     {
 379       use = uses->ref;
 380
 381       defs = DF_REF_CHAIN (use);
 382       if (!defs)
 383         continue;
 384
 385       if (defs->next)
 386         return false;
 387
 388       def = defs->ref;
 389       def_data = DF_REF_DATA (def);
 390       if (!def_data)
 391         return false;
 392
 393       def_bb = DF_REF_BB (def);
 394       if (!dominated_by_p (CDI_DOMINATORS, bb, def_bb))
 395         return false;
 396
 397       bitmap_set_bit (depends_on, def_data->invno);
 398     }
 399
 400   return true;
 401 }
 402
 403 /* Finds invariant in INSN.  ALWAYS_REACHED is true if the insn is always
 404    executed.  ALWAYS_EXECUTED is true if the insn is always executed,
 405    unless the program ends due to a function call.  DF is the dataflow
 406    object.  */
 407
 408 static void
 409 find_invariant_insn (rtx insn, bool always_reached, bool always_executed,
 410                      struct df *df)
 411 {
 412   struct ref *ref;
 413   struct def *def;
 414   bitmap depends_on;
 415   rtx set, dest;
 416   bool simple = true;
 417
 418   /* Until we get rid of LIBCALLS.  */
 419   if (find_reg_note (insn, REG_RETVAL, NULL_RTX)
 420       || find_reg_note (insn, REG_LIBCALL, NULL_RTX)
 421       || find_reg_note (insn, REG_NO_CONFLICT, NULL_RTX))
 422     return;
 423
 424   set = single_set (insn);
 425   if (!set)
 426     return;
 427   dest = SET_DEST (set);
 428
 429   if (GET_CODE (dest) != REG
 430       || HARD_REGISTER_P (dest))
 431     simple = false;
 432
 433   if (!check_maybe_invariant (SET_SRC (set))
 434       || !may_assign_reg_p (SET_DEST (set)))
 435     return;
 436
 437   if (may_trap_p (PATTERN (insn)))
 438     {
 439       if (!always_reached)
 440         return;
 441
 442       /* Unless the exceptions are handled, the behavior is undefined
 443          if the trap occurs.  */
 444       if (flag_non_call_exceptions)
 445         return;
 446     }
 447
 448   depends_on = BITMAP_XMALLOC ();
 449   if (!check_dependencies (insn, df, depends_on))
 450     {
 451       BITMAP_XFREE (depends_on);
 452       return;
 453     }
 454
 455   if (simple)
 456     {
 457       ref = df_find_def (df, insn, dest);
 458       def = xcalloc (1, sizeof (struct def));
 459       DF_REF_DATA (ref) = def;
 460     }
 461   else
 462     def = NULL;
 463
 464   create_new_invariant (def, insn, depends_on, always_executed);
 465 }
 466
 467 /* Record registers used in INSN that have an unique invariant definition.
 468    DF is the dataflow object.  */
 469
 470 static void
 471 record_uses (rtx insn, struct df *df)
 472 {
 473   struct df_link *uses, *defs;
 474   struct ref *use, *def;
 475   basic_block bb = BLOCK_FOR_INSN (insn), def_bb;
 476
 477   for (uses = DF_INSN_USES (df, insn); uses; uses = uses->next)
 478     {
 479       use = uses->ref;
 480
 481       defs = DF_REF_CHAIN (use);
 482       if (!defs || defs->next)
 483         continue;
 484       def = defs->ref;
 485       if (!DF_REF_DATA (def))
 486         continue;
 487
 488       def_bb = DF_REF_BB (def);
 489       if (!dominated_by_p (CDI_DOMINATORS, bb, def_bb))
 490         continue;
 491
 492       record_use (DF_REF_DATA (def), DF_REF_LOC (use), DF_REF_INSN (use));
 493     }
 494 }
 495
 496 /* Finds invariants in INSN.  ALWAYS_REACHED is true if the insn is always
 497    executed.  ALWAYS_EXECUTED is true if the insn is always executed,
 498    unless the program ends due to a function call.  DF is the dataflow
 499    object.  */
 500
 501 static void
 502 find_invariants_insn (rtx insn, bool always_reached, bool always_executed,
 503                       struct df *df)
 504 {
 505   find_invariant_insn (insn, always_reached, always_executed, df);
 506   record_uses (insn, df);
 507 }
 508
 509 /* Finds invariants in basic block BB.  ALWAYS_REACHED is true if the
 510    basic block is always executed.  ALWAYS_EXECUTED is true if the basic
 511    block is always executed, unless the program ends due to a function
 512    call.  DF is the dataflow object.  */
 513
 514 static void
 515 find_invariants_bb (basic_block bb, bool always_reached, bool always_executed,
 516                     struct df *df)
 517 {
 518   rtx insn;
 519
 520   FOR_BB_INSNS (bb, insn)
 521     {
 522       if (!INSN_P (insn))
 523         continue;
 524
 525       find_invariants_insn (insn, always_reached, always_executed, df);
 526
 527       if (always_reached
 528           && GET_CODE (insn) == CALL_INSN
 529           && !CONST_OR_PURE_CALL_P (insn))
 530         always_reached = false;
 531     }
 532 }
 533
 534 /* Finds invariants in LOOP with body BODY.  ALWAYS_REACHED is the bitmap of
 535    basic blocks in BODY that are always executed.  ALWAYS_EXECUTED is the
 536    bitmap of basic blocks in BODY that are always executed unless the program
 537    ends due to a function call.  DF is the dataflow object.  */
 538
 539 static void
 540 find_invariants_body (struct loop *loop, basic_block *body,
 541                       bitmap always_reached, bitmap always_executed,
 542                       struct df *df)
 543 {
 544   unsigned i;
 545
 546   for (i = 0; i < loop->num_nodes; i++)
 547     find_invariants_bb (body[i],
 548                         bitmap_bit_p (always_reached, i),
 549                         bitmap_bit_p (always_executed, i),
 550                         df);
 551 }
 552
 553 /* Finds invariants in LOOP.  DF is the dataflow object.  */
 554
 555 static void
 556 find_invariants (struct loop *loop, struct df *df)
 557 {
 558   bitmap may_exit = BITMAP_XMALLOC ();
 559   bitmap always_reached = BITMAP_XMALLOC ();
 560   bitmap has_exit = BITMAP_XMALLOC ();
 561   bitmap always_executed = BITMAP_XMALLOC ();
 562   basic_block *body = get_loop_body_in_dom_order (loop);
 563
 564   find_exits (loop, body, may_exit, has_exit);
 565   compute_always_reached (loop, body, may_exit, always_reached);
 566   compute_always_reached (loop, body, has_exit, always_executed);
 567
 568   find_defs (loop, body, df);
 569   find_invariants_body (loop, body, always_reached, always_executed, df);
 570
 571   BITMAP_XFREE (always_reached);
 572   BITMAP_XFREE (always_executed);
 573   BITMAP_XFREE (may_exit);
 574   BITMAP_XFREE (has_exit);
 575   free (body);
 576 }
 577
 578 /* Frees a list of uses USE.  */
 579
 580 static void
 581 free_use_list (struct use *use)
 582 {
 583   struct use *next;
 584
 585   for (; use; use = next)
 586     {
 587       next = use->next;
 588       free (use);
 589     }
 590 }
 591
 592 /* Calculates cost and number of registers needed for moving invariant INV
 593    out of the loop and stores them to *COST and *REGS_NEEDED.  */
 594
 595 static void
 596 get_inv_cost (struct invariant *inv, int *comp_cost, unsigned *regs_needed)
 597 {
 598   int acomp_cost;
 599   unsigned aregs_needed;
 600   unsigned depno;
 601   struct invariant *dep;
 602
 603   *comp_cost = 0;
 604   *regs_needed = 0;
 605   if (inv->move
 606       || inv->stamp == actual_stamp)
 607     return;
 608   inv->stamp = actual_stamp;
 609
 610   (*regs_needed)++;
 611   (*comp_cost) += inv->cost;
 612
 613   EXECUTE_IF_SET_IN_BITMAP (inv->depends_on, 0, depno,
 614     {
 615       dep = VARRAY_GENERIC_PTR_NOGC (invariants, depno);
 616
 617       get_inv_cost (dep, &acomp_cost, &aregs_needed);
 618
 619       if (aregs_needed
 620           /* We need to check always_executed, since if the original value of
 621              the invariant may be preserved, we may need to keep it in a
 622              separate register.  TODO check whether the register has an
 623              use outside of the loop.  */
 624           && dep->always_executed
 625           && !dep->def->uses->next)
 626         {
 627           /* If this is a single use, after moving the dependency we will not
 628              need a new register.  */
 629           aregs_needed--;
 630         }
 631
 632       (*regs_needed) += aregs_needed;
 633       (*comp_cost) += acomp_cost;
 634     });
 635 }
 636
 637 /* Calculates gain for eliminating invariant INV.  REGS_USED is the number
 638    of registers used in the loop, N_INV_USES is the number of uses of
 639    invariants, NEW_REGS is the number of new variables already added due to
 640    the invariant motion.  The number of registers needed for it is stored in
 641    *REGS_NEEDED.  */
 642
 643 static int
 644 gain_for_invariant (struct invariant *inv, unsigned *regs_needed,
 645                     unsigned new_regs, unsigned regs_used, unsigned n_inv_uses)
 646 {
 647   int comp_cost, size_cost;
 648
 649   get_inv_cost (inv, &comp_cost, regs_needed);
 650   actual_stamp++;
 651
 652   size_cost = (global_cost_for_size (new_regs + *regs_needed,
 653                                      regs_used, n_inv_uses)
 654                - global_cost_for_size (new_regs, regs_used, n_inv_uses));
 655
 656   return comp_cost - size_cost;
 657 }
 658
 659 /* Finds invariant with best gain for moving.  Returns the gain, stores
 660    the invariant in *BEST and number of registers needed for it to
 661    *REGS_NEEDED.  REGS_USED is the number of registers used in
 662    the loop, N_INV_USES is the number of uses of invariants.  NEW_REGS
 663    is the number of new variables already added due to invariant motion.  */
 664
 665 static int
 666 best_gain_for_invariant (struct invariant **best, unsigned *regs_needed,
 667                          unsigned new_regs, unsigned regs_used,
 668                          unsigned n_inv_uses)
 669 {
 670   struct invariant *inv;
 671   int gain = 0, again;
 672   unsigned aregs_needed, invno;
 673
 674   for (invno = 0; invno < VARRAY_ACTIVE_SIZE (invariants); invno++)
 675     {
 676       inv = VARRAY_GENERIC_PTR_NOGC (invariants, invno);
 677       if (inv->move)
 678         continue;
 679
 680       again = gain_for_invariant (inv, &aregs_needed,
 681                                   new_regs, regs_used, n_inv_uses);
 682       if (again > gain)
 683         {
 684           gain = again;
 685           *best = inv;
 686           *regs_needed = aregs_needed;
 687         }
 688     }
 689
 690   return gain;
 691 }
 692
 693 /* Marks invariant INVNO and all its dependencies for moving.  */
 694
 695 static void
 696 set_move_mark (unsigned invno)
 697 {
 698   struct invariant *inv = VARRAY_GENERIC_PTR_NOGC (invariants, invno);
 699
 700   if (inv->move)
 701     return;
 702   inv->move = true;
 703
 704   if (dump_file)
 705     fprintf (dump_file, "Decided to move invariant %d\n", invno);
 706
 707   EXECUTE_IF_SET_IN_BITMAP (inv->depends_on, 0, invno, set_move_mark (invno));
 708 }
 709
 710 /* Determines which invariants to move.  DF is the dataflow object.  */
 711
 712 static void
 713 find_invariants_to_move (struct df *df)
 714 {
 715   unsigned i, regs_used, n_inv_uses, regs_needed = 0, new_regs;
 716   struct invariant *inv = NULL;
 717
 718   if (flag_move_all_movables)
 719     {
 720       /* This is easy & stupid.  */
 721       for (i = 0; i < VARRAY_ACTIVE_SIZE (invariants); i++)
 722         {
 723           inv = VARRAY_GENERIC_PTR_NOGC (invariants, i);
 724           inv->move = true;
 725         }
 726       return;
 727     }
 728
 729   if (!VARRAY_ACTIVE_SIZE (invariants))
 730     return;
 731
 732   /* Now something slightly more involved.  First estimate the number of used
 733      registers.  */
 734   n_inv_uses = 0;
 735
 736   /* We do not really do a good job in this estimation; put some initial bound
 737      here to stand for induction variables etc. that we do not detect.  */
 738   regs_used = 2;
 739
 740   for (i = 0; i < df->n_regs; i++)
 741     {
 742       if (!DF_REGNO_FIRST_DEF (df, i) && DF_REGNO_LAST_USE (df, i))
 743         {
 744           /* This is a value that is used but not changed inside loop.  */
 745           regs_used++;
 746         }
 747     }
 748
 749   for (i = 0; i < VARRAY_ACTIVE_SIZE (invariants); i++)
 750     {
 751       inv = VARRAY_GENERIC_PTR_NOGC (invariants, i);
 752       if (inv->def)
 753         n_inv_uses += inv->def->n_uses;
 754     }
 755
 756   new_regs = 0;
 757   while (best_gain_for_invariant (&inv, &regs_needed,
 758                                   new_regs, regs_used, n_inv_uses) > 0)
 759     {
 760       set_move_mark (inv->invno);
 761       new_regs += regs_needed;
 762     }
 763 }
 764
 765 /* Move invariant INVNO out of the LOOP.  DF is the dataflow object.  */
 766
 767 static void
 768 move_invariant_reg (struct loop *loop, unsigned invno, struct df *df)
 769 {
 770   struct invariant *inv = VARRAY_GENERIC_PTR_NOGC (invariants, invno);
 771   unsigned i;
 772   basic_block preheader = loop_preheader_edge (loop)->src;
 773   rtx reg, set;
 774   struct use *use;
 775
 776   if (inv->processed)
 777     return;
 778   inv->processed = true;
 779
 780   if (inv->depends_on)
 781     {
 782       EXECUTE_IF_SET_IN_BITMAP (inv->depends_on, 0, i,
 783         {
 784           move_invariant_reg (loop, i, df);
 785         });
 786     }
 787
 788   /* Move the set out of the loop.  If the set is always executed (we could
 789      omit this condition if we know that the register is unused outside of the
 790      loop, but it does not seem worth finding out) and it has no uses that
 791      would not be dominated by it, we may just move it (TODO).  Otherwise we
 792      need to create a temporary register.  */
 793   set = single_set (inv->insn);
 794   reg = gen_reg_rtx (GET_MODE (SET_DEST (set)));
 795   df_pattern_emit_after (df, gen_move_insn (SET_DEST (set), reg),
 796                          BLOCK_FOR_INSN (inv->insn), inv->insn);
 797   SET_DEST (set) = reg;
 798   reorder_insns (inv->insn, inv->insn, BB_END (preheader));
 799   df_insn_modify (df, preheader, inv->insn);
 800
 801   /* Replace the uses we know to be dominated.  It saves work for copy
 802      propagation, and also it is necessary so that dependent invariants
 803      are computed right.  */
 804   if (inv->def)
 805     {
 806       for (use = inv->def->uses; use; use = use->next)
 807         {
 808           *use->pos = reg;
 809           df_insn_modify (df, BLOCK_FOR_INSN (use->insn), use->insn);
 810         }
 811     }
 812 }
 813
 814 /* Move selected invariant out of the LOOP.  Newly created regs are marked
 815    in TEMPORARY_REGS.  DF is the dataflow object.  */
 816
 817 static void
 818 move_invariants (struct loop *loop, struct df *df)
 819 {
 820   struct invariant *inv;
 821   unsigned i;
 822
 823   for (i = 0; i < VARRAY_ACTIVE_SIZE (invariants); i++)
 824     {
 825       inv = VARRAY_GENERIC_PTR_NOGC (invariants, i);
 826       if (inv->move)
 827         move_invariant_reg (loop, i, df);
 828     }
 829 }
 830
 831 /* Initializes invariant motion data.  */
 832
 833 static void
 834 init_inv_motion_data (void)
 835 {
 836   actual_stamp = 1;
 837
 838   if (!invariants)
 839     VARRAY_GENERIC_PTR_NOGC_INIT (invariants, 100, "invariants");
 840 }
 841
 842 /* Frees the data allocated by invariant motion.  DF is the dataflow
 843    object.  */
 844
 845 static void
 846 free_inv_motion_data (struct df *df)
 847 {
 848   unsigned i;
 849   struct def *def;
 850   struct invariant *inv;
 851
 852   for (i = 0; i < df->n_defs; i++)
 853     {
 854       if (!df->defs[i])
 855         continue;
 856
 857       def = DF_REF_DATA (df->defs[i]);
 858       if (!def)
 859         continue;
 860
 861       free_use_list (def->uses);
 862       free (def);
 863       DF_REF_DATA (df->defs[i]) = NULL;
 864     }
 865
 866   for (i = 0; i < VARRAY_ACTIVE_SIZE (invariants); i++)
 867     {
 868       inv = VARRAY_GENERIC_PTR_NOGC (invariants, i);
 869       BITMAP_XFREE (inv->depends_on);
 870       free (inv);
 871     }
 872   VARRAY_POP_ALL (invariants);
 873 }
 874
 875 /* Move the invariants out of the LOOP.  DF is the dataflow object.  */
 876
 877 static void
 878 move_single_loop_invariants (struct loop *loop, struct df *df)
 879 {
 880   init_inv_motion_data ();
 881
 882   find_invariants (loop, df);
 883   find_invariants_to_move (df);
 884   move_invariants (loop, df);
 885
 886   free_inv_motion_data (df);
 887 }
 888
 889 /* Releases the auxiliary data for LOOP.  */
 890
 891 static void
 892 free_loop_data (struct loop *loop)
 893 {
 894   struct loop_data *data = LOOP_DATA (loop);
 895
 896   free (data);
 897   loop->aux = NULL;
 898 }
 899
 900 /* Move the invariants out of the LOOPS.  */
 901
 902 void
 903 move_loop_invariants (struct loops *loops)
 904 {
 905   struct loop *loop;
 906   unsigned i;
 907   struct df *df = df_init ();
 908
 909   /* Process the loops, innermost first.  */
 910   loop = loops->tree_root;
 911   while (loop->inner)
 912     loop = loop->inner;
 913
 914   while (loop != loops->tree_root)
 915     {
 916       move_single_loop_invariants (loop, df);
 917
 918       if (loop->next)
 919         {
 920           loop = loop->next;
 921           while (loop->inner)
 922             loop = loop->inner;
 923         }
 924       else
 925         loop = loop->outer;
 926     }
 927
 928   for (i = 1; i < loops->num; i++)
 929     if (loops->parray[i])
 930       free_loop_data (loops->parray[i]);
 931
 932   df_finish (df);
 933 }