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