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