gcc/loop-invariant.c

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