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   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           && CALL_P (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 (!VARRAY_ACTIVE_SIZE (invariants))
 719     return;
 720
 721   /* Now something slightly more involved.  First estimate the number of used
 722      registers.  */
 723   n_inv_uses = 0;
 724
 725   /* We do not really do a good job in this estimation; put some initial bound
 726      here to stand for induction variables etc. that we do not detect.  */
 727   regs_used = 2;
 728
 729   for (i = 0; i < df->n_regs; i++)
 730     {
 731       if (!DF_REGNO_FIRST_DEF (df, i) && DF_REGNO_LAST_USE (df, i))
 732         {
 733           /* This is a value that is used but not changed inside loop.  */
 734           regs_used++;
 735         }
 736     }
 737
 738   for (i = 0; i < VARRAY_ACTIVE_SIZE (invariants); i++)
 739     {
 740       inv = VARRAY_GENERIC_PTR_NOGC (invariants, i);
 741       if (inv->def)
 742         n_inv_uses += inv->def->n_uses;
 743     }
 744
 745   new_regs = 0;
 746   while (best_gain_for_invariant (&inv, &regs_needed,
 747                                   new_regs, regs_used, n_inv_uses) > 0)
 748     {
 749       set_move_mark (inv->invno);
 750       new_regs += regs_needed;
 751     }
 752 }
 753
 754 /* Move invariant INVNO out of the LOOP.  DF is the dataflow object.  */
 755
 756 static void
 757 move_invariant_reg (struct loop *loop, unsigned invno, struct df *df)
 758 {
 759   struct invariant *inv = VARRAY_GENERIC_PTR_NOGC (invariants, invno);
 760   unsigned i;
 761   basic_block preheader = loop_preheader_edge (loop)->src;
 762   rtx reg, set;
 763   struct use *use;
 764
 765   if (inv->processed)
 766     return;
 767   inv->processed = true;
 768
 769   if (inv->depends_on)
 770     {
 771       EXECUTE_IF_SET_IN_BITMAP (inv->depends_on, 0, i,
 772         {
 773           move_invariant_reg (loop, i, df);
 774         });
 775     }
 776
 777   /* Move the set out of the loop.  If the set is always executed (we could
 778      omit this condition if we know that the register is unused outside of the
 779      loop, but it does not seem worth finding out) and it has no uses that
 780      would not be dominated by it, we may just move it (TODO).  Otherwise we
 781      need to create a temporary register.  */
 782   set = single_set (inv->insn);
 783   reg = gen_reg_rtx (GET_MODE (SET_DEST (set)));
 784   df_pattern_emit_after (df, gen_move_insn (SET_DEST (set), reg),
 785                          BLOCK_FOR_INSN (inv->insn), inv->insn);
 786   SET_DEST (set) = reg;
 787   reorder_insns (inv->insn, inv->insn, BB_END (preheader));
 788   df_insn_modify (df, preheader, inv->insn);
 789
 790   /* Replace the uses we know to be dominated.  It saves work for copy
 791      propagation, and also it is necessary so that dependent invariants
 792      are computed right.  */
 793   if (inv->def)
 794     {
 795       for (use = inv->def->uses; use; use = use->next)
 796         {
 797           *use->pos = reg;
 798           df_insn_modify (df, BLOCK_FOR_INSN (use->insn), use->insn);
 799         }
 800     }
 801 }
 802
 803 /* Move selected invariant out of the LOOP.  Newly created regs are marked
 804    in TEMPORARY_REGS.  DF is the dataflow object.  */
 805
 806 static void
 807 move_invariants (struct loop *loop, struct df *df)
 808 {
 809   struct invariant *inv;
 810   unsigned i;
 811
 812   for (i = 0; i < VARRAY_ACTIVE_SIZE (invariants); i++)
 813     {
 814       inv = VARRAY_GENERIC_PTR_NOGC (invariants, i);
 815       if (inv->move)
 816         move_invariant_reg (loop, i, df);
 817     }
 818 }
 819
 820 /* Initializes invariant motion data.  */
 821
 822 static void
 823 init_inv_motion_data (void)
 824 {
 825   actual_stamp = 1;
 826
 827   if (!invariants)
 828     VARRAY_GENERIC_PTR_NOGC_INIT (invariants, 100, "invariants");
 829 }
 830
 831 /* Frees the data allocated by invariant motion.  DF is the dataflow
 832    object.  */
 833
 834 static void
 835 free_inv_motion_data (struct df *df)
 836 {
 837   unsigned i;
 838   struct def *def;
 839   struct invariant *inv;
 840
 841   for (i = 0; i < df->n_defs; i++)
 842     {
 843       if (!df->defs[i])
 844         continue;
 845
 846       def = DF_REF_DATA (df->defs[i]);
 847       if (!def)
 848         continue;
 849
 850       free_use_list (def->uses);
 851       free (def);
 852       DF_REF_DATA (df->defs[i]) = NULL;
 853     }
 854
 855   for (i = 0; i < VARRAY_ACTIVE_SIZE (invariants); i++)
 856     {
 857       inv = VARRAY_GENERIC_PTR_NOGC (invariants, i);
 858       BITMAP_XFREE (inv->depends_on);
 859       free (inv);
 860     }
 861   VARRAY_POP_ALL (invariants);
 862 }
 863
 864 /* Move the invariants out of the LOOP.  DF is the dataflow object.  */
 865
 866 static void
 867 move_single_loop_invariants (struct loop *loop, struct df *df)
 868 {
 869   init_inv_motion_data ();
 870
 871   find_invariants (loop, df);
 872   find_invariants_to_move (df);
 873   move_invariants (loop, df);
 874
 875   free_inv_motion_data (df);
 876 }
 877
 878 /* Releases the auxiliary data for LOOP.  */
 879
 880 static void
 881 free_loop_data (struct loop *loop)
 882 {
 883   struct loop_data *data = LOOP_DATA (loop);
 884
 885   free (data);
 886   loop->aux = NULL;
 887 }
 888
 889 /* Move the invariants out of the LOOPS.  */
 890
 891 void
 892 move_loop_invariants (struct loops *loops)
 893 {
 894   struct loop *loop;
 895   unsigned i;
 896   struct df *df = df_init ();
 897
 898   /* Process the loops, innermost first.  */
 899   loop = loops->tree_root;
 900   while (loop->inner)
 901     loop = loop->inner;
 902
 903   while (loop != loops->tree_root)
 904     {
 905       move_single_loop_invariants (loop, df);
 906
 907       if (loop->next)
 908         {
 909           loop = loop->next;
 910           while (loop->inner)
 911             loop = loop->inner;
 912         }
 913       else
 914         loop = loop->outer;
 915     }
 916
 917   for (i = 1; i < loops->num; i++)
 918     if (loops->parray[i])
 919       free_loop_data (loops->parray[i]);
 920
 921   df_finish (df);
 922 }