gcc/loop-invariant.c

   1 /* RTL-level loop invariant motion.
   2    Copyright (C) 2004, 2005, 2006, 2007, 2008 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 3, 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 COPYING3.  If not see
  18 <http://www.gnu.org/licenses/>.  */
  19
  20 /* This implements the loop invariant motion pass.  It is very simple
  21    (no calls, no loads/stores, etc.).  This should be sufficient to cleanup
  22    things like address arithmetics -- other more complicated invariants should
  23    be eliminated on GIMPLE either in tree-ssa-loop-im.c or in tree-ssa-pre.c.
  24
  25    We proceed loop by loop -- it is simpler than trying to handle things
  26    globally and should not lose much.  First we inspect all sets inside loop
  27    and create a dependency graph on insns (saying "to move this insn, you must
  28    also move the following insns").
  29
  30    We then need to determine what to move.  We estimate the number of registers
  31    used and move as many invariants as possible while we still have enough free
  32    registers.  We prefer the expensive invariants.
  33
  34    Then we move the selected invariants out of the loop, creating a new
  35    temporaries for them if necessary.  */
  36
  37 #include "config.h"
  38 #include "system.h"
  39 #include "coretypes.h"
  40 #include "tm.h"
  41 #include "rtl.h"
  42 #include "tm_p.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 "recog.h"
  49 #include "output.h"
  50 #include "function.h"
  51 #include "flags.h"
  52 #include "df.h"
  53 #include "hashtab.h"
  54 #include "except.h"
  55
  56 /* The data stored for the loop.  */
  57
  58 struct loop_data
  59 {
  60   struct loop *outermost_exit;  /* The outermost exit of the loop.  */
  61   bool has_call;                /* True if the loop contains a call.  */
  62 };
  63
  64 #define LOOP_DATA(LOOP) ((struct loop_data *) (LOOP)->aux)
  65
  66 /* The description of an use.  */
  67
  68 struct use
  69 {
  70   rtx *pos;                     /* Position of the use.  */
  71   rtx insn;                     /* The insn in that the use occurs.  */
  72
  73   struct use *next;             /* Next use in the list.  */
  74 };
  75
  76 /* The description of a def.  */
  77
  78 struct def
  79 {
  80   struct use *uses;             /* The list of uses that are uniquely reached
  81                                    by it.  */
  82   unsigned n_uses;              /* Number of such uses.  */
  83   unsigned invno;               /* The corresponding invariant.  */
  84 };
  85
  86 /* The data stored for each invariant.  */
  87
  88 struct invariant
  89 {
  90   /* The number of the invariant.  */
  91   unsigned invno;
  92
  93   /* The number of the invariant with the same value.  */
  94   unsigned eqto;
  95
  96   /* If we moved the invariant out of the loop, the register that contains its
  97      value.  */
  98   rtx reg;
  99
 100   /* The definition of the invariant.  */
 101   struct def *def;
 102
 103   /* The insn in that it is defined.  */
 104   rtx insn;
 105
 106   /* Whether it is always executed.  */
 107   bool always_executed;
 108
 109   /* Whether to move the invariant.  */
 110   bool move;
 111
 112   /* Cost of the invariant.  */
 113   unsigned cost;
 114
 115   /* The invariants it depends on.  */
 116   bitmap depends_on;
 117
 118   /* Used for detecting already visited invariants during determining
 119      costs of movements.  */
 120   unsigned stamp;
 121 };
 122
 123 /* Table of invariants indexed by the df_ref uid field.  */
 124
 125 static unsigned int invariant_table_size = 0;
 126 static struct invariant ** invariant_table;
 127
 128 /* Entry for hash table of invariant expressions.  */
 129
 130 struct invariant_expr_entry
 131 {
 132   /* The invariant.  */
 133   struct invariant *inv;
 134
 135   /* Its value.  */
 136   rtx expr;
 137
 138   /* Its mode.  */
 139   enum machine_mode mode;
 140
 141   /* Its hash.  */
 142   hashval_t hash;
 143 };
 144
 145 /* The actual stamp for marking already visited invariants during determining
 146    costs of movements.  */
 147
 148 static unsigned actual_stamp;
 149
 150 typedef struct invariant *invariant_p;
 151
 152 DEF_VEC_P(invariant_p);
 153 DEF_VEC_ALLOC_P(invariant_p, heap);
 154
 155 /* The invariants.  */
 156
 157 static VEC(invariant_p,heap) *invariants;
 158
 159 /* Check the size of the invariant table and realloc if necessary.  */
 160
 161 static void
 162 check_invariant_table_size (void)
 163 {
 164   if (invariant_table_size < DF_DEFS_TABLE_SIZE())
 165     {
 166       unsigned int new_size = DF_DEFS_TABLE_SIZE () + (DF_DEFS_TABLE_SIZE () / 4);
 167       invariant_table = XRESIZEVEC (struct invariant *, invariant_table, new_size);
 168       memset (&invariant_table[invariant_table_size], 0,
 169               (new_size - invariant_table_size) * sizeof (struct rtx_iv *));
 170       invariant_table_size = new_size;
 171     }
 172 }
 173
 174 /* Test for possibility of invariantness of X.  */
 175
 176 static bool
 177 check_maybe_invariant (rtx x)
 178 {
 179   enum rtx_code code = GET_CODE (x);
 180   int i, j;
 181   const char *fmt;
 182
 183   switch (code)
 184     {
 185     case CONST_INT:
 186     case CONST_DOUBLE:
 187     case CONST_FIXED:
 188     case SYMBOL_REF:
 189     case CONST:
 190     case LABEL_REF:
 191       return true;
 192
 193     case PC:
 194     case CC0:
 195     case UNSPEC_VOLATILE:
 196     case CALL:
 197       return false;
 198
 199     case REG:
 200       return true;
 201
 202     case MEM:
 203       /* Load/store motion is done elsewhere.  ??? Perhaps also add it here?
 204          It should not be hard, and might be faster than "elsewhere".  */
 205
 206       /* Just handle the most trivial case where we load from an unchanging
 207          location (most importantly, pic tables).  */
 208       if (MEM_READONLY_P (x) && !MEM_VOLATILE_P (x))
 209         break;
 210
 211       return false;
 212
 213     case ASM_OPERANDS:
 214       /* Don't mess with insns declared volatile.  */
 215       if (MEM_VOLATILE_P (x))
 216         return false;
 217       break;
 218
 219     default:
 220       break;
 221     }
 222
 223   fmt = GET_RTX_FORMAT (code);
 224   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
 225     {
 226       if (fmt[i] == 'e')
 227         {
 228           if (!check_maybe_invariant (XEXP (x, i)))
 229             return false;
 230         }
 231       else if (fmt[i] == 'E')
 232         {
 233           for (j = 0; j < XVECLEN (x, i); j++)
 234             if (!check_maybe_invariant (XVECEXP (x, i, j)))
 235               return false;
 236         }
 237     }
 238
 239   return true;
 240 }
 241
 242 /* Returns the invariant definition for USE, or NULL if USE is not
 243    invariant.  */
 244
 245 static struct invariant *
 246 invariant_for_use (struct df_ref *use)
 247 {
 248   struct df_link *defs;
 249   struct df_ref *def;
 250   basic_block bb = DF_REF_BB (use), def_bb;
 251
 252   if (use->flags & DF_REF_READ_WRITE)
 253     return NULL;
 254
 255   defs = DF_REF_CHAIN (use);
 256   if (!defs || defs->next)
 257     return NULL;
 258   def = defs->ref;
 259   check_invariant_table_size ();
 260   if (!invariant_table[DF_REF_ID(def)])
 261     return NULL;
 262
 263   def_bb = DF_REF_BB (def);
 264   if (!dominated_by_p (CDI_DOMINATORS, bb, def_bb))
 265     return NULL;
 266   return invariant_table[DF_REF_ID(def)];
 267 }
 268
 269 /* Computes hash value for invariant expression X in INSN.  */
 270
 271 static hashval_t
 272 hash_invariant_expr_1 (rtx insn, rtx x)
 273 {
 274   enum rtx_code code = GET_CODE (x);
 275   int i, j;
 276   const char *fmt;
 277   hashval_t val = code;
 278   int do_not_record_p;
 279   struct df_ref *use;
 280   struct invariant *inv;
 281
 282   switch (code)
 283     {
 284     case CONST_INT:
 285     case CONST_DOUBLE:
 286     case CONST_FIXED:
 287     case SYMBOL_REF:
 288     case CONST:
 289     case LABEL_REF:
 290       return hash_rtx (x, GET_MODE (x), &do_not_record_p, NULL, false);
 291
 292     case REG:
 293       use = df_find_use (insn, x);
 294       if (!use)
 295         return hash_rtx (x, GET_MODE (x), &do_not_record_p, NULL, false);
 296       inv = invariant_for_use (use);
 297       if (!inv)
 298         return hash_rtx (x, GET_MODE (x), &do_not_record_p, NULL, false);
 299
 300       gcc_assert (inv->eqto != ~0u);
 301       return inv->eqto;
 302
 303     default:
 304       break;
 305     }
 306
 307   fmt = GET_RTX_FORMAT (code);
 308   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
 309     {
 310       if (fmt[i] == 'e')
 311         val ^= hash_invariant_expr_1 (insn, XEXP (x, i));
 312       else if (fmt[i] == 'E')
 313         {
 314           for (j = 0; j < XVECLEN (x, i); j++)
 315             val ^= hash_invariant_expr_1 (insn, XVECEXP (x, i, j));
 316         }
 317       else if (fmt[i] == 'i' || fmt[i] == 'n')
 318         val ^= XINT (x, i);
 319     }
 320
 321   return val;
 322 }
 323
 324 /* Returns true if the invariant expressions E1 and E2 used in insns INSN1
 325    and INSN2 have always the same value.  */
 326
 327 static bool
 328 invariant_expr_equal_p (rtx insn1, rtx e1, rtx insn2, rtx e2)
 329 {
 330   enum rtx_code code = GET_CODE (e1);
 331   int i, j;
 332   const char *fmt;
 333   struct df_ref *use1, *use2;
 334   struct invariant *inv1 = NULL, *inv2 = NULL;
 335   rtx sub1, sub2;
 336
 337   /* If mode of only one of the operands is VOIDmode, it is not equivalent to
 338      the other one.  If both are VOIDmode, we rely on the caller of this
 339      function to verify that their modes are the same.  */
 340   if (code != GET_CODE (e2) || GET_MODE (e1) != GET_MODE (e2))
 341     return false;
 342
 343   switch (code)
 344     {
 345     case CONST_INT:
 346     case CONST_DOUBLE:
 347     case CONST_FIXED:
 348     case SYMBOL_REF:
 349     case CONST:
 350     case LABEL_REF:
 351       return rtx_equal_p (e1, e2);
 352
 353     case REG:
 354       use1 = df_find_use (insn1, e1);
 355       use2 = df_find_use (insn2, e2);
 356       if (use1)
 357         inv1 = invariant_for_use (use1);
 358       if (use2)
 359         inv2 = invariant_for_use (use2);
 360
 361       if (!inv1 && !inv2)
 362         return rtx_equal_p (e1, e2);
 363
 364       if (!inv1 || !inv2)
 365         return false;
 366
 367       gcc_assert (inv1->eqto != ~0u);
 368       gcc_assert (inv2->eqto != ~0u);
 369       return inv1->eqto == inv2->eqto;
 370
 371     default:
 372       break;
 373     }
 374
 375   fmt = GET_RTX_FORMAT (code);
 376   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
 377     {
 378       if (fmt[i] == 'e')
 379         {
 380           sub1 = XEXP (e1, i);
 381           sub2 = XEXP (e2, i);
 382
 383           if (!invariant_expr_equal_p (insn1, sub1, insn2, sub2))
 384             return false;
 385         }
 386
 387       else if (fmt[i] == 'E')
 388         {
 389           if (XVECLEN (e1, i) != XVECLEN (e2, i))
 390             return false;
 391
 392           for (j = 0; j < XVECLEN (e1, i); j++)
 393             {
 394               sub1 = XVECEXP (e1, i, j);
 395               sub2 = XVECEXP (e2, i, j);
 396
 397               if (!invariant_expr_equal_p (insn1, sub1, insn2, sub2))
 398                 return false;
 399             }
 400         }
 401       else if (fmt[i] == 'i' || fmt[i] == 'n')
 402         {
 403           if (XINT (e1, i) != XINT (e2, i))
 404             return false;
 405         }
 406       /* Unhandled type of subexpression, we fail conservatively.  */
 407       else
 408         return false;
 409     }
 410
 411   return true;
 412 }
 413
 414 /* Returns hash value for invariant expression entry E.  */
 415
 416 static hashval_t
 417 hash_invariant_expr (const void *e)
 418 {
 419   const struct invariant_expr_entry *const entry =
 420     (const struct invariant_expr_entry *) e;
 421
 422   return entry->hash;
 423 }
 424
 425 /* Compares invariant expression entries E1 and E2.  */
 426
 427 static int
 428 eq_invariant_expr (const void *e1, const void *e2)
 429 {
 430   const struct invariant_expr_entry *const entry1 =
 431     (const struct invariant_expr_entry *) e1;
 432   const struct invariant_expr_entry *const entry2 =
 433     (const struct invariant_expr_entry *) e2;
 434
 435   if (entry1->mode != entry2->mode)
 436     return 0;
 437
 438   return invariant_expr_equal_p (entry1->inv->insn, entry1->expr,
 439                                  entry2->inv->insn, entry2->expr);
 440 }
 441
 442 /* Checks whether invariant with value EXPR in machine mode MODE is
 443    recorded in EQ.  If this is the case, return the invariant.  Otherwise
 444    insert INV to the table for this expression and return INV.  */
 445
 446 static struct invariant *
 447 find_or_insert_inv (htab_t eq, rtx expr, enum machine_mode mode,
 448                     struct invariant *inv)
 449 {
 450   hashval_t hash = hash_invariant_expr_1 (inv->insn, expr);
 451   struct invariant_expr_entry *entry;
 452   struct invariant_expr_entry pentry;
 453   PTR *slot;
 454
 455   pentry.expr = expr;
 456   pentry.inv = inv;
 457   pentry.mode = mode;
 458   slot = htab_find_slot_with_hash (eq, &pentry, hash, INSERT);
 459   entry = (struct invariant_expr_entry *) *slot;
 460
 461   if (entry)
 462     return entry->inv;
 463
 464   entry = XNEW (struct invariant_expr_entry);
 465   entry->inv = inv;
 466   entry->expr = expr;
 467   entry->mode = mode;
 468   entry->hash = hash;
 469   *slot = entry;
 470
 471   return inv;
 472 }
 473
 474 /* Finds invariants identical to INV and records the equivalence.  EQ is the
 475    hash table of the invariants.  */
 476
 477 static void
 478 find_identical_invariants (htab_t eq, struct invariant *inv)
 479 {
 480   unsigned depno;
 481   bitmap_iterator bi;
 482   struct invariant *dep;
 483   rtx expr, set;
 484   enum machine_mode mode;
 485
 486   if (inv->eqto != ~0u)
 487     return;
 488
 489   EXECUTE_IF_SET_IN_BITMAP (inv->depends_on, 0, depno, bi)
 490     {
 491       dep = VEC_index (invariant_p, invariants, depno);
 492       find_identical_invariants (eq, dep);
 493     }
 494
 495   set = single_set (inv->insn);
 496   expr = SET_SRC (set);
 497   mode = GET_MODE (expr);
 498   if (mode == VOIDmode)
 499     mode = GET_MODE (SET_DEST (set));
 500   inv->eqto = find_or_insert_inv (eq, expr, mode, inv)->invno;
 501
 502   if (dump_file && inv->eqto != inv->invno)
 503     fprintf (dump_file,
 504              "Invariant %d is equivalent to invariant %d.\n",
 505              inv->invno, inv->eqto);
 506 }
 507
 508 /* Find invariants with the same value and record the equivalences.  */
 509
 510 static void
 511 merge_identical_invariants (void)
 512 {
 513   unsigned i;
 514   struct invariant *inv;
 515   htab_t eq = htab_create (VEC_length (invariant_p, invariants),
 516                            hash_invariant_expr, eq_invariant_expr, free);
 517
 518   for (i = 0; VEC_iterate (invariant_p, invariants, i, inv); i++)
 519     find_identical_invariants (eq, inv);
 520
 521   htab_delete (eq);
 522 }
 523
 524 /* Determines the basic blocks inside LOOP that are always executed and
 525    stores their bitmap to ALWAYS_REACHED.  MAY_EXIT is a bitmap of
 526    basic blocks that may either exit the loop, or contain the call that
 527    does not have to return.  BODY is body of the loop obtained by
 528    get_loop_body_in_dom_order.  */
 529
 530 static void
 531 compute_always_reached (struct loop *loop, basic_block *body,
 532                         bitmap may_exit, bitmap always_reached)
 533 {
 534   unsigned i;
 535
 536   for (i = 0; i < loop->num_nodes; i++)
 537     {
 538       if (dominated_by_p (CDI_DOMINATORS, loop->latch, body[i]))
 539         bitmap_set_bit (always_reached, i);
 540
 541       if (bitmap_bit_p (may_exit, i))
 542         return;
 543     }
 544 }
 545
 546 /* Finds exits out of the LOOP with body BODY.  Marks blocks in that we may
 547    exit the loop by cfg edge to HAS_EXIT and MAY_EXIT.  In MAY_EXIT
 548    additionally mark blocks that may exit due to a call.  */
 549
 550 static void
 551 find_exits (struct loop *loop, basic_block *body,
 552             bitmap may_exit, bitmap has_exit)
 553 {
 554   unsigned i;
 555   edge_iterator ei;
 556   edge e;
 557   struct loop *outermost_exit = loop, *aexit;
 558   bool has_call = false;
 559   rtx insn;
 560
 561   for (i = 0; i < loop->num_nodes; i++)
 562     {
 563       if (body[i]->loop_father == loop)
 564         {
 565           FOR_BB_INSNS (body[i], insn)
 566             {
 567               if (CALL_P (insn)
 568                   && (RTL_LOOPING_CONST_OR_PURE_CALL_P (insn)
 569                       || !RTL_CONST_OR_PURE_CALL_P (insn)))
 570                 {
 571                   has_call = true;
 572                   bitmap_set_bit (may_exit, i);
 573                   break;
 574                 }
 575             }
 576
 577           FOR_EACH_EDGE (e, ei, body[i]->succs)
 578             {
 579               if (flow_bb_inside_loop_p (loop, e->dest))
 580                 continue;
 581
 582               bitmap_set_bit (may_exit, i);
 583               bitmap_set_bit (has_exit, i);
 584               outermost_exit = find_common_loop (outermost_exit,
 585                                                  e->dest->loop_father);
 586             }
 587           continue;
 588         }
 589
 590       /* Use the data stored for the subloop to decide whether we may exit
 591          through it.  It is sufficient to do this for header of the loop,
 592          as other basic blocks inside it must be dominated by it.  */
 593       if (body[i]->loop_father->header != body[i])
 594         continue;
 595
 596       if (LOOP_DATA (body[i]->loop_father)->has_call)
 597         {
 598           has_call = true;
 599           bitmap_set_bit (may_exit, i);
 600         }
 601       aexit = LOOP_DATA (body[i]->loop_father)->outermost_exit;
 602       if (aexit != loop)
 603         {
 604           bitmap_set_bit (may_exit, i);
 605           bitmap_set_bit (has_exit, i);
 606
 607           if (flow_loop_nested_p (aexit, outermost_exit))
 608             outermost_exit = aexit;
 609         }
 610     }
 611
 612   loop->aux = xcalloc (1, sizeof (struct loop_data));
 613   LOOP_DATA (loop)->outermost_exit = outermost_exit;
 614   LOOP_DATA (loop)->has_call = has_call;
 615 }
 616
 617 /* Check whether we may assign a value to X from a register.  */
 618
 619 static bool
 620 may_assign_reg_p (rtx x)
 621 {
 622   return (GET_MODE (x) != VOIDmode
 623           && GET_MODE (x) != BLKmode
 624           && can_copy_p (GET_MODE (x))
 625           && (!REG_P (x)
 626               || !HARD_REGISTER_P (x)
 627               || REGNO_REG_CLASS (REGNO (x)) != NO_REGS));
 628 }
 629
 630 /* Finds definitions that may correspond to invariants in LOOP with body
 631    BODY.  */
 632
 633 static void
 634 find_defs (struct loop *loop, basic_block *body)
 635 {
 636   unsigned i;
 637   bitmap blocks = BITMAP_ALLOC (NULL);
 638
 639   for (i = 0; i < loop->num_nodes; i++)
 640     bitmap_set_bit (blocks, body[i]->index);
 641
 642   df_remove_problem (df_chain);
 643   df_process_deferred_rescans ();
 644   df_chain_add_problem (DF_UD_CHAIN);
 645   df_set_blocks (blocks);
 646   df_analyze ();
 647
 648   if (dump_file)
 649     {
 650       df_dump_region (dump_file);
 651       fprintf (dump_file, "*****starting processing of loop  ******\n");
 652       print_rtl_with_bb (dump_file, get_insns ());
 653       fprintf (dump_file, "*****ending processing of loop  ******\n");
 654     }
 655   check_invariant_table_size ();
 656
 657   BITMAP_FREE (blocks);
 658 }
 659
 660 /* Creates a new invariant for definition DEF in INSN, depending on invariants
 661    in DEPENDS_ON.  ALWAYS_EXECUTED is true if the insn is always executed,
 662    unless the program ends due to a function call.  The newly created invariant
 663    is returned.  */
 664
 665 static struct invariant *
 666 create_new_invariant (struct def *def, rtx insn, bitmap depends_on,
 667                       bool always_executed)
 668 {
 669   struct invariant *inv = XNEW (struct invariant);
 670   rtx set = single_set (insn);
 671
 672   inv->def = def;
 673   inv->always_executed = always_executed;
 674   inv->depends_on = depends_on;
 675
 676   /* If the set is simple, usually by moving it we move the whole store out of
 677      the loop.  Otherwise we save only cost of the computation.  */
 678   if (def)
 679     inv->cost = rtx_cost (set, SET);
 680   else
 681     inv->cost = rtx_cost (SET_SRC (set), SET);
 682
 683   inv->move = false;
 684   inv->reg = NULL_RTX;
 685   inv->stamp = 0;
 686   inv->insn = insn;
 687
 688   inv->invno = VEC_length (invariant_p, invariants);
 689   inv->eqto = ~0u;
 690   if (def)
 691     def->invno = inv->invno;
 692   VEC_safe_push (invariant_p, heap, invariants, inv);
 693
 694   if (dump_file)
 695     {
 696       fprintf (dump_file,
 697                "Set in insn %d is invariant (%d), cost %d, depends on ",
 698                INSN_UID (insn), inv->invno, inv->cost);
 699       dump_bitmap (dump_file, inv->depends_on);
 700     }
 701
 702   return inv;
 703 }
 704
 705 /* Record USE at DEF.  */
 706
 707 static void
 708 record_use (struct def *def, rtx *use, rtx insn)
 709 {
 710   struct use *u = XNEW (struct use);
 711
 712   gcc_assert (REG_P (*use));
 713
 714   u->pos = use;
 715   u->insn = insn;
 716   u->next = def->uses;
 717   def->uses = u;
 718   def->n_uses++;
 719 }
 720
 721 /* Finds the invariants USE depends on and store them to the DEPENDS_ON
 722    bitmap.  Returns true if all dependencies of USE are known to be
 723    loop invariants, false otherwise.  */
 724
 725 static bool
 726 check_dependency (basic_block bb, struct df_ref *use, bitmap depends_on)
 727 {
 728   struct df_ref *def;
 729   basic_block def_bb;
 730   struct df_link *defs;
 731   struct def *def_data;
 732   struct invariant *inv;
 733
 734   if (use->flags & DF_REF_READ_WRITE)
 735     return false;
 736
 737   defs = DF_REF_CHAIN (use);
 738   if (!defs)
 739     return true;
 740
 741   if (defs->next)
 742     return false;
 743
 744   def = defs->ref;
 745   check_invariant_table_size ();
 746   inv = invariant_table[DF_REF_ID(def)];
 747   if (!inv)
 748     return false;
 749
 750   def_data = inv->def;
 751   gcc_assert (def_data != NULL);
 752
 753   def_bb = DF_REF_BB (def);
 754   /* Note that in case bb == def_bb, we know that the definition
 755      dominates insn, because def has invariant_table[DF_REF_ID(def)]
 756      defined and we process the insns in the basic block bb
 757      sequentially.  */
 758   if (!dominated_by_p (CDI_DOMINATORS, bb, def_bb))
 759     return false;
 760
 761   bitmap_set_bit (depends_on, def_data->invno);
 762   return true;
 763 }
 764
 765
 766 /* Finds the invariants INSN depends on and store them to the DEPENDS_ON
 767    bitmap.  Returns true if all dependencies of INSN are known to be
 768    loop invariants, false otherwise.  */
 769
 770 static bool
 771 check_dependencies (rtx insn, bitmap depends_on)
 772 {
 773   struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
 774   struct df_ref **use_rec;
 775   basic_block bb = BLOCK_FOR_INSN (insn);
 776
 777   for (use_rec = DF_INSN_INFO_USES (insn_info); *use_rec; use_rec++)
 778     if (!check_dependency (bb, *use_rec, depends_on))
 779       return false;
 780   for (use_rec = DF_INSN_INFO_EQ_USES (insn_info); *use_rec; use_rec++)
 781     if (!check_dependency (bb, *use_rec, depends_on))
 782       return false;
 783
 784   return true;
 785 }
 786
 787 /* Finds invariant in INSN.  ALWAYS_REACHED is true if the insn is always
 788    executed.  ALWAYS_EXECUTED is true if the insn is always executed,
 789    unless the program ends due to a function call.  */
 790
 791 static void
 792 find_invariant_insn (rtx insn, bool always_reached, bool always_executed)
 793 {
 794   struct df_ref *ref;
 795   struct def *def;
 796   bitmap depends_on;
 797   rtx set, dest;
 798   bool simple = true;
 799   struct invariant *inv;
 800
 801 #ifdef HAVE_cc0
 802   /* We can't move a CC0 setter without the user.  */
 803   if (sets_cc0_p (insn))
 804     return;
 805 #endif
 806
 807   set = single_set (insn);
 808   if (!set)
 809     return;
 810   dest = SET_DEST (set);
 811
 812   if (!REG_P (dest)
 813       || HARD_REGISTER_P (dest))
 814     simple = false;
 815
 816   if (!may_assign_reg_p (SET_DEST (set))
 817       || !check_maybe_invariant (SET_SRC (set)))
 818     return;
 819
 820   /* If the insn can throw exception, we cannot move it at all without changing
 821      cfg.  */
 822   if (can_throw_internal (insn))
 823     return;
 824
 825   /* We cannot make trapping insn executed, unless it was executed before.  */
 826   if (may_trap_after_code_motion_p (PATTERN (insn)) && !always_reached)
 827     return;
 828
 829   depends_on = BITMAP_ALLOC (NULL);
 830   if (!check_dependencies (insn, depends_on))
 831     {
 832       BITMAP_FREE (depends_on);
 833       return;
 834     }
 835
 836   if (simple)
 837     def = XCNEW (struct def);
 838   else
 839     def = NULL;
 840
 841   inv = create_new_invariant (def, insn, depends_on, always_executed);
 842
 843   if (simple)
 844     {
 845       ref = df_find_def (insn, dest);
 846       check_invariant_table_size ();
 847       invariant_table[DF_REF_ID(ref)] = inv;
 848     }
 849 }
 850
 851 /* Record registers used in INSN that have a unique invariant definition.  */
 852
 853 static void
 854 record_uses (rtx insn)
 855 {
 856   struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
 857   struct df_ref **use_rec;
 858   struct invariant *inv;
 859
 860   for (use_rec = DF_INSN_INFO_USES (insn_info); *use_rec; use_rec++)
 861     {
 862       struct df_ref *use = *use_rec;
 863       inv = invariant_for_use (use);
 864       if (inv)
 865         record_use (inv->def, DF_REF_REAL_LOC (use), DF_REF_INSN (use));
 866     }
 867   for (use_rec = DF_INSN_INFO_EQ_USES (insn_info); *use_rec; use_rec++)
 868     {
 869       struct df_ref *use = *use_rec;
 870       inv = invariant_for_use (use);
 871       if (inv)
 872         record_use (inv->def, DF_REF_REAL_LOC (use), DF_REF_INSN (use));
 873     }
 874 }
 875
 876 /* Finds invariants in INSN.  ALWAYS_REACHED is true if the insn is always
 877    executed.  ALWAYS_EXECUTED is true if the insn is always executed,
 878    unless the program ends due to a function call.  */
 879
 880 static void
 881 find_invariants_insn (rtx insn, bool always_reached, bool always_executed)
 882 {
 883   find_invariant_insn (insn, always_reached, always_executed);
 884   record_uses (insn);
 885 }
 886
 887 /* Finds invariants in basic block BB.  ALWAYS_REACHED is true if the
 888    basic block is always executed.  ALWAYS_EXECUTED is true if the basic
 889    block is always executed, unless the program ends due to a function
 890    call.  */
 891
 892 static void
 893 find_invariants_bb (basic_block bb, bool always_reached, bool always_executed)
 894 {
 895   rtx insn;
 896
 897   FOR_BB_INSNS (bb, insn)
 898     {
 899       if (!INSN_P (insn))
 900         continue;
 901
 902       find_invariants_insn (insn, always_reached, always_executed);
 903
 904       if (always_reached
 905           && CALL_P (insn)
 906           && (RTL_LOOPING_CONST_OR_PURE_CALL_P (insn)
 907               || ! RTL_CONST_OR_PURE_CALL_P (insn)))
 908         always_reached = false;
 909     }
 910 }
 911
 912 /* Finds invariants in LOOP with body BODY.  ALWAYS_REACHED is the bitmap of
 913    basic blocks in BODY that are always executed.  ALWAYS_EXECUTED is the
 914    bitmap of basic blocks in BODY that are always executed unless the program
 915    ends due to a function call.  */
 916
 917 static void
 918 find_invariants_body (struct loop *loop, basic_block *body,
 919                       bitmap always_reached, bitmap always_executed)
 920 {
 921   unsigned i;
 922
 923   for (i = 0; i < loop->num_nodes; i++)
 924     find_invariants_bb (body[i],
 925                         bitmap_bit_p (always_reached, i),
 926                         bitmap_bit_p (always_executed, i));
 927 }
 928
 929 /* Finds invariants in LOOP.  */
 930
 931 static void
 932 find_invariants (struct loop *loop)
 933 {
 934   bitmap may_exit = BITMAP_ALLOC (NULL);
 935   bitmap always_reached = BITMAP_ALLOC (NULL);
 936   bitmap has_exit = BITMAP_ALLOC (NULL);
 937   bitmap always_executed = BITMAP_ALLOC (NULL);
 938   basic_block *body = get_loop_body_in_dom_order (loop);
 939
 940   find_exits (loop, body, may_exit, has_exit);
 941   compute_always_reached (loop, body, may_exit, always_reached);
 942   compute_always_reached (loop, body, has_exit, always_executed);
 943
 944   find_defs (loop, body);
 945   find_invariants_body (loop, body, always_reached, always_executed);
 946   merge_identical_invariants ();
 947
 948   BITMAP_FREE (always_reached);
 949   BITMAP_FREE (always_executed);
 950   BITMAP_FREE (may_exit);
 951   BITMAP_FREE (has_exit);
 952   free (body);
 953 }
 954
 955 /* Frees a list of uses USE.  */
 956
 957 static void
 958 free_use_list (struct use *use)
 959 {
 960   struct use *next;
 961
 962   for (; use; use = next)
 963     {
 964       next = use->next;
 965       free (use);
 966     }
 967 }
 968
 969 /* Calculates cost and number of registers needed for moving invariant INV
 970    out of the loop and stores them to *COST and *REGS_NEEDED.  */
 971
 972 static void
 973 get_inv_cost (struct invariant *inv, int *comp_cost, unsigned *regs_needed)
 974 {
 975   int acomp_cost;
 976   unsigned aregs_needed;
 977   unsigned depno;
 978   struct invariant *dep;
 979   bitmap_iterator bi;
 980
 981   /* Find the representative of the class of the equivalent invariants.  */
 982   inv = VEC_index (invariant_p, invariants, inv->eqto);
 983
 984   *comp_cost = 0;
 985   *regs_needed = 0;
 986   if (inv->move
 987       || inv->stamp == actual_stamp)
 988     return;
 989   inv->stamp = actual_stamp;
 990
 991   (*regs_needed)++;
 992   (*comp_cost) += inv->cost;
 993
 994 #ifdef STACK_REGS
 995   {
 996     /* Hoisting constant pool constants into stack regs may cost more than
 997        just single register.  On x87, the balance is affected both by the
 998        small number of FP registers, and by its register stack organization,
 999        that forces us to add compensation code in and around the loop to
1000        shuffle the operands to the top of stack before use, and pop them
1001        from the stack after the loop finishes.
1002
1003        To model this effect, we increase the number of registers needed for
1004        stack registers by two: one register push, and one register pop.
1005        This usually has the effect that FP constant loads from the constant
1006        pool are not moved out of the loop.
1007
1008        Note that this also means that dependent invariants can not be moved.
1009        However, the primary purpose of this pass is to move loop invariant
1010        address arithmetic out of loops, and address arithmetic that depends
1011        on floating point constants is unlikely to ever occur.  */
1012     rtx set = single_set (inv->insn);
1013     if (set
1014        && IS_STACK_MODE (GET_MODE (SET_SRC (set)))
1015        && constant_pool_constant_p (SET_SRC (set)))
1016       (*regs_needed) += 2;
1017   }
1018 #endif
1019
1020   EXECUTE_IF_SET_IN_BITMAP (inv->depends_on, 0, depno, bi)
1021     {
1022       dep = VEC_index (invariant_p, invariants, depno);
1023
1024       get_inv_cost (dep, &acomp_cost, &aregs_needed);
1025
1026       if (aregs_needed
1027           /* We need to check always_executed, since if the original value of
1028              the invariant may be preserved, we may need to keep it in a
1029              separate register.  TODO check whether the register has an
1030              use outside of the loop.  */
1031           && dep->always_executed
1032           && !dep->def->uses->next)
1033         {
1034           /* If this is a single use, after moving the dependency we will not
1035              need a new register.  */
1036           aregs_needed--;
1037         }
1038
1039       (*regs_needed) += aregs_needed;
1040       (*comp_cost) += acomp_cost;
1041     }
1042 }
1043
1044 /* Calculates gain for eliminating invariant INV.  REGS_USED is the number
1045    of registers used in the loop, NEW_REGS is the number of new variables
1046    already added due to the invariant motion.  The number of registers needed
1047    for it is stored in *REGS_NEEDED.  */
1048
1049 static int
1050 gain_for_invariant (struct invariant *inv, unsigned *regs_needed,
1051                     unsigned new_regs, unsigned regs_used)
1052 {
1053   int comp_cost, size_cost;
1054
1055   get_inv_cost (inv, &comp_cost, regs_needed);
1056   actual_stamp++;
1057
1058   size_cost = (estimate_reg_pressure_cost (new_regs + *regs_needed, regs_used)
1059                - estimate_reg_pressure_cost (new_regs, regs_used));
1060
1061   return comp_cost - size_cost;
1062 }
1063
1064 /* Finds invariant with best gain for moving.  Returns the gain, stores
1065    the invariant in *BEST and number of registers needed for it to
1066    *REGS_NEEDED.  REGS_USED is the number of registers used in the loop.
1067    NEW_REGS is the number of new variables already added due to invariant
1068    motion.  */
1069
1070 static int
1071 best_gain_for_invariant (struct invariant **best, unsigned *regs_needed,
1072                          unsigned new_regs, unsigned regs_used)
1073 {
1074   struct invariant *inv;
1075   int gain = 0, again;
1076   unsigned aregs_needed, invno;
1077
1078   for (invno = 0; VEC_iterate (invariant_p, invariants, invno, inv); invno++)
1079     {
1080       if (inv->move)
1081         continue;
1082
1083       /* Only consider the "representatives" of equivalent invariants.  */
1084       if (inv->eqto != inv->invno)
1085         continue;
1086
1087       again = gain_for_invariant (inv, &aregs_needed, new_regs, regs_used);
1088       if (again > gain)
1089         {
1090           gain = again;
1091           *best = inv;
1092           *regs_needed = aregs_needed;
1093         }
1094     }
1095
1096   return gain;
1097 }
1098
1099 /* Marks invariant INVNO and all its dependencies for moving.  */
1100
1101 static void
1102 set_move_mark (unsigned invno)
1103 {
1104   struct invariant *inv = VEC_index (invariant_p, invariants, invno);
1105   bitmap_iterator bi;
1106
1107   /* Find the representative of the class of the equivalent invariants.  */
1108   inv = VEC_index (invariant_p, invariants, inv->eqto);
1109
1110   if (inv->move)
1111     return;
1112   inv->move = true;
1113
1114   if (dump_file)
1115     fprintf (dump_file, "Decided to move invariant %d\n", invno);
1116
1117   EXECUTE_IF_SET_IN_BITMAP (inv->depends_on, 0, invno, bi)
1118     {
1119       set_move_mark (invno);
1120     }
1121 }
1122
1123 /* Determines which invariants to move.  */
1124
1125 static void
1126 find_invariants_to_move (void)
1127 {
1128   unsigned i, regs_used, regs_needed = 0, new_regs;
1129   struct invariant *inv = NULL;
1130   unsigned int n_regs = DF_REG_SIZE (df);
1131
1132   if (!VEC_length (invariant_p, invariants))
1133     return;
1134
1135   /* We do not really do a good job in estimating number of registers used;
1136      we put some initial bound here to stand for induction variables etc.
1137      that we do not detect.  */
1138   regs_used = 2;
1139
1140   for (i = 0; i < n_regs; i++)
1141     {
1142       if (!DF_REGNO_FIRST_DEF (i) && DF_REGNO_LAST_USE (i))
1143         {
1144           /* This is a value that is used but not changed inside loop.  */
1145           regs_used++;
1146         }
1147     }
1148
1149   new_regs = 0;
1150   while (best_gain_for_invariant (&inv, &regs_needed, new_regs, regs_used) > 0)
1151     {
1152       set_move_mark (inv->invno);
1153       new_regs += regs_needed;
1154     }
1155 }
1156
1157 /* Move invariant INVNO out of the LOOP.  Returns true if this succeeds, false
1158    otherwise.  */
1159
1160 static bool
1161 move_invariant_reg (struct loop *loop, unsigned invno)
1162 {
1163   struct invariant *inv = VEC_index (invariant_p, invariants, invno);
1164   struct invariant *repr = VEC_index (invariant_p, invariants, inv->eqto);
1165   unsigned i;
1166   basic_block preheader = loop_preheader_edge (loop)->src;
1167   rtx reg, set, dest, note;
1168   struct use *use;
1169   bitmap_iterator bi;
1170
1171   if (inv->reg)
1172     return true;
1173   if (!repr->move)
1174     return false;
1175   /* If this is a representative of the class of equivalent invariants,
1176      really move the invariant.  Otherwise just replace its use with
1177      the register used for the representative.  */
1178   if (inv == repr)
1179     {
1180       if (inv->depends_on)
1181         {
1182           EXECUTE_IF_SET_IN_BITMAP (inv->depends_on, 0, i, bi)
1183             {
1184               if (!move_invariant_reg (loop, i))
1185                 goto fail;
1186             }
1187         }
1188
1189       /* Move the set out of the loop.  If the set is always executed (we could
1190          omit this condition if we know that the register is unused outside of the
1191          loop, but it does not seem worth finding out) and it has no uses that
1192          would not be dominated by it, we may just move it (TODO).  Otherwise we
1193          need to create a temporary register.  */
1194       set = single_set (inv->insn);
1195       dest = SET_DEST (set);
1196       reg = gen_reg_rtx_and_attrs (dest);
1197
1198       /* Try replacing the destination by a new pseudoregister.  */
1199       if (!validate_change (inv->insn, &SET_DEST (set), reg, false))
1200         goto fail;
1201       df_insn_rescan (inv->insn);
1202
1203       emit_insn_after (gen_move_insn (dest, reg), inv->insn);
1204       reorder_insns (inv->insn, inv->insn, BB_END (preheader));
1205
1206       /* If there is a REG_EQUAL note on the insn we just moved, and
1207          insn is in a basic block that is not always executed, the note
1208          may no longer be valid after we move the insn.
1209          Note that uses in REG_EQUAL notes are taken into account in
1210          the computation of invariants.  Hence it is safe to retain the
1211          note even if the note contains register references.  */
1212       if (! inv->always_executed
1213           && (note = find_reg_note (inv->insn, REG_EQUAL, NULL_RTX)))
1214         remove_note (inv->insn, note);
1215     }
1216   else
1217     {
1218       if (!move_invariant_reg (loop, repr->invno))
1219         goto fail;
1220       reg = repr->reg;
1221       set = single_set (inv->insn);
1222       emit_insn_after (gen_move_insn (SET_DEST (set), reg), inv->insn);
1223       delete_insn (inv->insn);
1224     }
1225
1226
1227   inv->reg = reg;
1228
1229   /* Replace the uses we know to be dominated.  It saves work for copy
1230      propagation, and also it is necessary so that dependent invariants
1231      are computed right.  */
1232   if (inv->def)
1233     {
1234       for (use = inv->def->uses; use; use = use->next)
1235         {
1236           *use->pos = reg;
1237           df_insn_rescan (use->insn);
1238         }
1239     }
1240
1241   return true;
1242
1243 fail:
1244   /* If we failed, clear move flag, so that we do not try to move inv
1245      again.  */
1246   if (dump_file)
1247     fprintf (dump_file, "Failed to move invariant %d\n", invno);
1248   inv->move = false;
1249   inv->reg = NULL_RTX;
1250
1251   return false;
1252 }
1253
1254 /* Move selected invariant out of the LOOP.  Newly created regs are marked
1255    in TEMPORARY_REGS.  */
1256
1257 static void
1258 move_invariants (struct loop *loop)
1259 {
1260   struct invariant *inv;
1261   unsigned i;
1262
1263   for (i = 0; VEC_iterate (invariant_p, invariants, i, inv); i++)
1264     move_invariant_reg (loop, i);
1265 }
1266
1267 /* Initializes invariant motion data.  */
1268
1269 static void
1270 init_inv_motion_data (void)
1271 {
1272   actual_stamp = 1;
1273
1274   invariants = VEC_alloc (invariant_p, heap, 100);
1275 }
1276
1277 /* Frees the data allocated by invariant motion.  */
1278
1279 static void
1280 free_inv_motion_data (void)
1281 {
1282   unsigned i;
1283   struct def *def;
1284   struct invariant *inv;
1285
1286   check_invariant_table_size ();
1287   for (i = 0; i < DF_DEFS_TABLE_SIZE (); i++)
1288     {
1289       inv = invariant_table[i];
1290       if (inv)
1291         {
1292           def = inv->def;
1293           gcc_assert (def != NULL);
1294
1295           free_use_list (def->uses);
1296           free (def);
1297           invariant_table[i] = NULL;
1298         }
1299     }
1300
1301   for (i = 0; VEC_iterate (invariant_p, invariants, i, inv); i++)
1302     {
1303       BITMAP_FREE (inv->depends_on);
1304       free (inv);
1305     }
1306   VEC_free (invariant_p, heap, invariants);
1307 }
1308
1309 /* Move the invariants out of the LOOP.  */
1310
1311 static void
1312 move_single_loop_invariants (struct loop *loop)
1313 {
1314   init_inv_motion_data ();
1315
1316   find_invariants (loop);
1317   find_invariants_to_move ();
1318   move_invariants (loop);
1319
1320   free_inv_motion_data ();
1321 }
1322
1323 /* Releases the auxiliary data for LOOP.  */
1324
1325 static void
1326 free_loop_data (struct loop *loop)
1327 {
1328   struct loop_data *data = LOOP_DATA (loop);
1329
1330   free (data);
1331   loop->aux = NULL;
1332 }
1333
1334 /* Move the invariants out of the loops.  */
1335
1336 void
1337 move_loop_invariants (void)
1338 {
1339   struct loop *loop;
1340   loop_iterator li;
1341
1342   df_set_flags (DF_EQ_NOTES + DF_DEFER_INSN_RESCAN);
1343   /* Process the loops, innermost first.  */
1344   FOR_EACH_LOOP (li, loop, LI_FROM_INNERMOST)
1345     {
1346       move_single_loop_invariants (loop);
1347     }
1348
1349   FOR_EACH_LOOP (li, loop, 0)
1350     {
1351       free_loop_data (loop);
1352     }
1353
1354   free (invariant_table);
1355   invariant_table = NULL;
1356   invariant_table_size = 0;
1357
1358 #ifdef ENABLE_CHECKING
1359   verify_flow_info ();
1360 #endif
1361 }