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 (df_ref use)
 247 {
 248   struct df_link *defs;
 249   df_ref def;
 250   basic_block bb = DF_REF_BB (use), def_bb;
 251
 252   if (DF_REF_FLAGS (use) & 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   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   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   bool speed = optimize_bb_for_speed_p (BLOCK_FOR_INSN (insn));
 672
 673   inv->def = def;
 674   inv->always_executed = always_executed;
 675   inv->depends_on = depends_on;
 676
 677   /* If the set is simple, usually by moving it we move the whole store out of
 678      the loop.  Otherwise we save only cost of the computation.  */
 679   if (def)
 680     inv->cost = rtx_cost (set, SET, speed);
 681   else
 682     inv->cost = rtx_cost (SET_SRC (set), SET, speed);
 683
 684   inv->move = false;
 685   inv->reg = NULL_RTX;
 686   inv->stamp = 0;
 687   inv->insn = insn;
 688
 689   inv->invno = VEC_length (invariant_p, invariants);
 690   inv->eqto = ~0u;
 691   if (def)
 692     def->invno = inv->invno;
 693   VEC_safe_push (invariant_p, heap, invariants, inv);
 694
 695   if (dump_file)
 696     {
 697       fprintf (dump_file,
 698                "Set in insn %d is invariant (%d), cost %d, depends on ",
 699                INSN_UID (insn), inv->invno, inv->cost);
 700       dump_bitmap (dump_file, inv->depends_on);
 701     }
 702
 703   return inv;
 704 }
 705
 706 /* Record USE at DEF.  */
 707
 708 static void
 709 record_use (struct def *def, rtx *use, rtx insn)
 710 {
 711   struct use *u = XNEW (struct use);
 712
 713   gcc_assert (REG_P (*use));
 714
 715   u->pos = use;
 716   u->insn = insn;
 717   u->next = def->uses;
 718   def->uses = u;
 719   def->n_uses++;
 720 }
 721
 722 /* Finds the invariants USE depends on and store them to the DEPENDS_ON
 723    bitmap.  Returns true if all dependencies of USE are known to be
 724    loop invariants, false otherwise.  */
 725
 726 static bool
 727 check_dependency (basic_block bb, df_ref use, bitmap depends_on)
 728 {
 729   df_ref def;
 730   basic_block def_bb;
 731   struct df_link *defs;
 732   struct def *def_data;
 733   struct invariant *inv;
 734
 735   if (DF_REF_FLAGS (use) & DF_REF_READ_WRITE)
 736     return false;
 737
 738   defs = DF_REF_CHAIN (use);
 739   if (!defs)
 740     return true;
 741
 742   if (defs->next)
 743     return false;
 744
 745   def = defs->ref;
 746   check_invariant_table_size ();
 747   inv = invariant_table[DF_REF_ID(def)];
 748   if (!inv)
 749     return false;
 750
 751   def_data = inv->def;
 752   gcc_assert (def_data != NULL);
 753
 754   def_bb = DF_REF_BB (def);
 755   /* Note that in case bb == def_bb, we know that the definition
 756      dominates insn, because def has invariant_table[DF_REF_ID(def)]
 757      defined and we process the insns in the basic block bb
 758      sequentially.  */
 759   if (!dominated_by_p (CDI_DOMINATORS, bb, def_bb))
 760     return false;
 761
 762   bitmap_set_bit (depends_on, def_data->invno);
 763   return true;
 764 }
 765
 766
 767 /* Finds the invariants INSN depends on and store them to the DEPENDS_ON
 768    bitmap.  Returns true if all dependencies of INSN are known to be
 769    loop invariants, false otherwise.  */
 770
 771 static bool
 772 check_dependencies (rtx insn, bitmap depends_on)
 773 {
 774   struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
 775   df_ref *use_rec;
 776   basic_block bb = BLOCK_FOR_INSN (insn);
 777
 778   for (use_rec = DF_INSN_INFO_USES (insn_info); *use_rec; use_rec++)
 779     if (!check_dependency (bb, *use_rec, depends_on))
 780       return false;
 781   for (use_rec = DF_INSN_INFO_EQ_USES (insn_info); *use_rec; use_rec++)
 782     if (!check_dependency (bb, *use_rec, depends_on))
 783       return false;
 784
 785   return true;
 786 }
 787
 788 /* Finds invariant in INSN.  ALWAYS_REACHED is true if the insn is always
 789    executed.  ALWAYS_EXECUTED is true if the insn is always executed,
 790    unless the program ends due to a function call.  */
 791
 792 static void
 793 find_invariant_insn (rtx insn, bool always_reached, bool always_executed)
 794 {
 795   df_ref ref;
 796   struct def *def;
 797   bitmap depends_on;
 798   rtx set, dest;
 799   bool simple = true;
 800   struct invariant *inv;
 801
 802 #ifdef HAVE_cc0
 803   /* We can't move a CC0 setter without the user.  */
 804   if (sets_cc0_p (insn))
 805     return;
 806 #endif
 807
 808   set = single_set (insn);
 809   if (!set)
 810     return;
 811   dest = SET_DEST (set);
 812
 813   if (!REG_P (dest)
 814       || HARD_REGISTER_P (dest))
 815     simple = false;
 816
 817   if (!may_assign_reg_p (SET_DEST (set))
 818       || !check_maybe_invariant (SET_SRC (set)))
 819     return;
 820
 821   /* If the insn can throw exception, we cannot move it at all without changing
 822      cfg.  */
 823   if (can_throw_internal (insn))
 824     return;
 825
 826   /* We cannot make trapping insn executed, unless it was executed before.  */
 827   if (may_trap_after_code_motion_p (PATTERN (insn)) && !always_reached)
 828     return;
 829
 830   depends_on = BITMAP_ALLOC (NULL);
 831   if (!check_dependencies (insn, depends_on))
 832     {
 833       BITMAP_FREE (depends_on);
 834       return;
 835     }
 836
 837   if (simple)
 838     def = XCNEW (struct def);
 839   else
 840     def = NULL;
 841
 842   inv = create_new_invariant (def, insn, depends_on, always_executed);
 843
 844   if (simple)
 845     {
 846       ref = df_find_def (insn, dest);
 847       check_invariant_table_size ();
 848       invariant_table[DF_REF_ID(ref)] = inv;
 849     }
 850 }
 851
 852 /* Record registers used in INSN that have a unique invariant definition.  */
 853
 854 static void
 855 record_uses (rtx insn)
 856 {
 857   struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
 858   df_ref *use_rec;
 859   struct invariant *inv;
 860
 861   for (use_rec = DF_INSN_INFO_USES (insn_info); *use_rec; use_rec++)
 862     {
 863       df_ref use = *use_rec;
 864       inv = invariant_for_use (use);
 865       if (inv)
 866         record_use (inv->def, DF_REF_REAL_LOC (use), DF_REF_INSN (use));
 867     }
 868   for (use_rec = DF_INSN_INFO_EQ_USES (insn_info); *use_rec; use_rec++)
 869     {
 870       df_ref use = *use_rec;
 871       inv = invariant_for_use (use);
 872       if (inv)
 873         record_use (inv->def, DF_REF_REAL_LOC (use), DF_REF_INSN (use));
 874     }
 875 }
 876
 877 /* Finds invariants in INSN.  ALWAYS_REACHED is true if the insn is always
 878    executed.  ALWAYS_EXECUTED is true if the insn is always executed,
 879    unless the program ends due to a function call.  */
 880
 881 static void
 882 find_invariants_insn (rtx insn, bool always_reached, bool always_executed)
 883 {
 884   find_invariant_insn (insn, always_reached, always_executed);
 885   record_uses (insn);
 886 }
 887
 888 /* Finds invariants in basic block BB.  ALWAYS_REACHED is true if the
 889    basic block is always executed.  ALWAYS_EXECUTED is true if the basic
 890    block is always executed, unless the program ends due to a function
 891    call.  */
 892
 893 static void
 894 find_invariants_bb (basic_block bb, bool always_reached, bool always_executed)
 895 {
 896   rtx insn;
 897
 898   FOR_BB_INSNS (bb, insn)
 899     {
 900       if (!INSN_P (insn))
 901         continue;
 902
 903       find_invariants_insn (insn, always_reached, always_executed);
 904
 905       if (always_reached
 906           && CALL_P (insn)
 907           && (RTL_LOOPING_CONST_OR_PURE_CALL_P (insn)
 908               || ! RTL_CONST_OR_PURE_CALL_P (insn)))
 909         always_reached = false;
 910     }
 911 }
 912
 913 /* Finds invariants in LOOP with body BODY.  ALWAYS_REACHED is the bitmap of
 914    basic blocks in BODY that are always executed.  ALWAYS_EXECUTED is the
 915    bitmap of basic blocks in BODY that are always executed unless the program
 916    ends due to a function call.  */
 917
 918 static void
 919 find_invariants_body (struct loop *loop, basic_block *body,
 920                       bitmap always_reached, bitmap always_executed)
 921 {
 922   unsigned i;
 923
 924   for (i = 0; i < loop->num_nodes; i++)
 925     find_invariants_bb (body[i],
 926                         bitmap_bit_p (always_reached, i),
 927                         bitmap_bit_p (always_executed, i));
 928 }
 929
 930 /* Finds invariants in LOOP.  */
 931
 932 static void
 933 find_invariants (struct loop *loop)
 934 {
 935   bitmap may_exit = BITMAP_ALLOC (NULL);
 936   bitmap always_reached = BITMAP_ALLOC (NULL);
 937   bitmap has_exit = BITMAP_ALLOC (NULL);
 938   bitmap always_executed = BITMAP_ALLOC (NULL);
 939   basic_block *body = get_loop_body_in_dom_order (loop);
 940
 941   find_exits (loop, body, may_exit, has_exit);
 942   compute_always_reached (loop, body, may_exit, always_reached);
 943   compute_always_reached (loop, body, has_exit, always_executed);
 944
 945   find_defs (loop, body);
 946   find_invariants_body (loop, body, always_reached, always_executed);
 947   merge_identical_invariants ();
 948
 949   BITMAP_FREE (always_reached);
 950   BITMAP_FREE (always_executed);
 951   BITMAP_FREE (may_exit);
 952   BITMAP_FREE (has_exit);
 953   free (body);
 954 }
 955
 956 /* Frees a list of uses USE.  */
 957
 958 static void
 959 free_use_list (struct use *use)
 960 {
 961   struct use *next;
 962
 963   for (; use; use = next)
 964     {
 965       next = use->next;
 966       free (use);
 967     }
 968 }
 969
 970 /* Calculates cost and number of registers needed for moving invariant INV
 971    out of the loop and stores them to *COST and *REGS_NEEDED.  */
 972
 973 static void
 974 get_inv_cost (struct invariant *inv, int *comp_cost, unsigned *regs_needed)
 975 {
 976   int acomp_cost;
 977   unsigned aregs_needed;
 978   unsigned depno;
 979   struct invariant *dep;
 980   bitmap_iterator bi;
 981
 982   /* Find the representative of the class of the equivalent invariants.  */
 983   inv = VEC_index (invariant_p, invariants, inv->eqto);
 984
 985   *comp_cost = 0;
 986   *regs_needed = 0;
 987   if (inv->move
 988       || inv->stamp == actual_stamp)
 989     return;
 990   inv->stamp = actual_stamp;
 991
 992   (*regs_needed)++;
 993   (*comp_cost) += inv->cost;
 994
 995 #ifdef STACK_REGS
 996   {
 997     /* Hoisting constant pool constants into stack regs may cost more than
 998        just single register.  On x87, the balance is affected both by the
 999        small number of FP registers, and by its register stack organization,
1000        that forces us to add compensation code in and around the loop to
1001        shuffle the operands to the top of stack before use, and pop them
1002        from the stack after the loop finishes.
1003
1004        To model this effect, we increase the number of registers needed for
1005        stack registers by two: one register push, and one register pop.
1006        This usually has the effect that FP constant loads from the constant
1007        pool are not moved out of the loop.
1008
1009        Note that this also means that dependent invariants can not be moved.
1010        However, the primary purpose of this pass is to move loop invariant
1011        address arithmetic out of loops, and address arithmetic that depends
1012        on floating point constants is unlikely to ever occur.  */
1013     rtx set = single_set (inv->insn);
1014     if (set
1015        && IS_STACK_MODE (GET_MODE (SET_SRC (set)))
1016        && constant_pool_constant_p (SET_SRC (set)))
1017       (*regs_needed) += 2;
1018   }
1019 #endif
1020
1021   EXECUTE_IF_SET_IN_BITMAP (inv->depends_on, 0, depno, bi)
1022     {
1023       dep = VEC_index (invariant_p, invariants, depno);
1024
1025       get_inv_cost (dep, &acomp_cost, &aregs_needed);
1026
1027       if (aregs_needed
1028           /* We need to check always_executed, since if the original value of
1029              the invariant may be preserved, we may need to keep it in a
1030              separate register.  TODO check whether the register has an
1031              use outside of the loop.  */
1032           && dep->always_executed
1033           && !dep->def->uses->next)
1034         {
1035           /* If this is a single use, after moving the dependency we will not
1036              need a new register.  */
1037           aregs_needed--;
1038         }
1039
1040       (*regs_needed) += aregs_needed;
1041       (*comp_cost) += acomp_cost;
1042     }
1043 }
1044
1045 /* Calculates gain for eliminating invariant INV.  REGS_USED is the number
1046    of registers used in the loop, NEW_REGS is the number of new variables
1047    already added due to the invariant motion.  The number of registers needed
1048    for it is stored in *REGS_NEEDED.  */
1049
1050 static int
1051 gain_for_invariant (struct invariant *inv, unsigned *regs_needed,
1052                     unsigned new_regs, unsigned regs_used, bool speed)
1053 {
1054   int comp_cost, size_cost;
1055
1056   get_inv_cost (inv, &comp_cost, regs_needed);
1057   actual_stamp++;
1058
1059   size_cost = (estimate_reg_pressure_cost (new_regs + *regs_needed, regs_used, speed)
1060                - estimate_reg_pressure_cost (new_regs, regs_used, speed));
1061
1062   return comp_cost - size_cost;
1063 }
1064
1065 /* Finds invariant with best gain for moving.  Returns the gain, stores
1066    the invariant in *BEST and number of registers needed for it to
1067    *REGS_NEEDED.  REGS_USED is the number of registers used in the loop.
1068    NEW_REGS is the number of new variables already added due to invariant
1069    motion.  */
1070
1071 static int
1072 best_gain_for_invariant (struct invariant **best, unsigned *regs_needed,
1073                          unsigned new_regs, unsigned regs_used, bool speed)
1074 {
1075   struct invariant *inv;
1076   int gain = 0, again;
1077   unsigned aregs_needed, invno;
1078
1079   for (invno = 0; VEC_iterate (invariant_p, invariants, invno, inv); invno++)
1080     {
1081       if (inv->move)
1082         continue;
1083
1084       /* Only consider the "representatives" of equivalent invariants.  */
1085       if (inv->eqto != inv->invno)
1086         continue;
1087
1088       again = gain_for_invariant (inv, &aregs_needed, new_regs, regs_used,
1089                                   speed);
1090       if (again > gain)
1091         {
1092           gain = again;
1093           *best = inv;
1094           *regs_needed = aregs_needed;
1095         }
1096     }
1097
1098   return gain;
1099 }
1100
1101 /* Marks invariant INVNO and all its dependencies for moving.  */
1102
1103 static void
1104 set_move_mark (unsigned invno)
1105 {
1106   struct invariant *inv = VEC_index (invariant_p, invariants, invno);
1107   bitmap_iterator bi;
1108
1109   /* Find the representative of the class of the equivalent invariants.  */
1110   inv = VEC_index (invariant_p, invariants, inv->eqto);
1111
1112   if (inv->move)
1113     return;
1114   inv->move = true;
1115
1116   if (dump_file)
1117     fprintf (dump_file, "Decided to move invariant %d\n", invno);
1118
1119   EXECUTE_IF_SET_IN_BITMAP (inv->depends_on, 0, invno, bi)
1120     {
1121       set_move_mark (invno);
1122     }
1123 }
1124
1125 /* Determines which invariants to move.  */
1126
1127 static void
1128 find_invariants_to_move (bool speed)
1129 {
1130   unsigned i, regs_used, regs_needed = 0, new_regs;
1131   struct invariant *inv = NULL;
1132   unsigned int n_regs = DF_REG_SIZE (df);
1133
1134   if (!VEC_length (invariant_p, invariants))
1135     return;
1136
1137   /* We do not really do a good job in estimating number of registers used;
1138      we put some initial bound here to stand for induction variables etc.
1139      that we do not detect.  */
1140   regs_used = 2;
1141
1142   for (i = 0; i < n_regs; i++)
1143     {
1144       if (!DF_REGNO_FIRST_DEF (i) && DF_REGNO_LAST_USE (i))
1145         {
1146           /* This is a value that is used but not changed inside loop.  */
1147           regs_used++;
1148         }
1149     }
1150
1151   new_regs = 0;
1152   while (best_gain_for_invariant (&inv, &regs_needed, new_regs, regs_used, speed) > 0)
1153     {
1154       set_move_mark (inv->invno);
1155       new_regs += regs_needed;
1156     }
1157 }
1158
1159 /* Move invariant INVNO out of the LOOP.  Returns true if this succeeds, false
1160    otherwise.  */
1161
1162 static bool
1163 move_invariant_reg (struct loop *loop, unsigned invno)
1164 {
1165   struct invariant *inv = VEC_index (invariant_p, invariants, invno);
1166   struct invariant *repr = VEC_index (invariant_p, invariants, inv->eqto);
1167   unsigned i;
1168   basic_block preheader = loop_preheader_edge (loop)->src;
1169   rtx reg, set, dest, note;
1170   struct use *use;
1171   bitmap_iterator bi;
1172
1173   if (inv->reg)
1174     return true;
1175   if (!repr->move)
1176     return false;
1177   /* If this is a representative of the class of equivalent invariants,
1178      really move the invariant.  Otherwise just replace its use with
1179      the register used for the representative.  */
1180   if (inv == repr)
1181     {
1182       if (inv->depends_on)
1183         {
1184           EXECUTE_IF_SET_IN_BITMAP (inv->depends_on, 0, i, bi)
1185             {
1186               if (!move_invariant_reg (loop, i))
1187                 goto fail;
1188             }
1189         }
1190
1191       /* Move the set out of the loop.  If the set is always executed (we could
1192          omit this condition if we know that the register is unused outside of the
1193          loop, but it does not seem worth finding out) and it has no uses that
1194          would not be dominated by it, we may just move it (TODO).  Otherwise we
1195          need to create a temporary register.  */
1196       set = single_set (inv->insn);
1197       dest = SET_DEST (set);
1198       reg = gen_reg_rtx_and_attrs (dest);
1199
1200       /* Try replacing the destination by a new pseudoregister.  */
1201       if (!validate_change (inv->insn, &SET_DEST (set), reg, false))
1202         goto fail;
1203       df_insn_rescan (inv->insn);
1204
1205       emit_insn_after (gen_move_insn (dest, reg), inv->insn);
1206       reorder_insns (inv->insn, inv->insn, BB_END (preheader));
1207
1208       /* If there is a REG_EQUAL note on the insn we just moved, and
1209          insn is in a basic block that is not always executed, the note
1210          may no longer be valid after we move the insn.
1211          Note that uses in REG_EQUAL notes are taken into account in
1212          the computation of invariants.  Hence it is safe to retain the
1213          note even if the note contains register references.  */
1214       if (! inv->always_executed
1215           && (note = find_reg_note (inv->insn, REG_EQUAL, NULL_RTX)))
1216         remove_note (inv->insn, note);
1217     }
1218   else
1219     {
1220       if (!move_invariant_reg (loop, repr->invno))
1221         goto fail;
1222       reg = repr->reg;
1223       set = single_set (inv->insn);
1224       emit_insn_after (gen_move_insn (SET_DEST (set), reg), inv->insn);
1225       delete_insn (inv->insn);
1226     }
1227
1228
1229   inv->reg = reg;
1230
1231   /* Replace the uses we know to be dominated.  It saves work for copy
1232      propagation, and also it is necessary so that dependent invariants
1233      are computed right.  */
1234   if (inv->def)
1235     {
1236       for (use = inv->def->uses; use; use = use->next)
1237         {
1238           *use->pos = reg;
1239           df_insn_rescan (use->insn);
1240         }
1241     }
1242
1243   return true;
1244
1245 fail:
1246   /* If we failed, clear move flag, so that we do not try to move inv
1247      again.  */
1248   if (dump_file)
1249     fprintf (dump_file, "Failed to move invariant %d\n", invno);
1250   inv->move = false;
1251   inv->reg = NULL_RTX;
1252
1253   return false;
1254 }
1255
1256 /* Move selected invariant out of the LOOP.  Newly created regs are marked
1257    in TEMPORARY_REGS.  */
1258
1259 static void
1260 move_invariants (struct loop *loop)
1261 {
1262   struct invariant *inv;
1263   unsigned i;
1264
1265   for (i = 0; VEC_iterate (invariant_p, invariants, i, inv); i++)
1266     move_invariant_reg (loop, i);
1267 }
1268
1269 /* Initializes invariant motion data.  */
1270
1271 static void
1272 init_inv_motion_data (void)
1273 {
1274   actual_stamp = 1;
1275
1276   invariants = VEC_alloc (invariant_p, heap, 100);
1277 }
1278
1279 /* Frees the data allocated by invariant motion.  */
1280
1281 static void
1282 free_inv_motion_data (void)
1283 {
1284   unsigned i;
1285   struct def *def;
1286   struct invariant *inv;
1287
1288   check_invariant_table_size ();
1289   for (i = 0; i < DF_DEFS_TABLE_SIZE (); i++)
1290     {
1291       inv = invariant_table[i];
1292       if (inv)
1293         {
1294           def = inv->def;
1295           gcc_assert (def != NULL);
1296
1297           free_use_list (def->uses);
1298           free (def);
1299           invariant_table[i] = NULL;
1300         }
1301     }
1302
1303   for (i = 0; VEC_iterate (invariant_p, invariants, i, inv); i++)
1304     {
1305       BITMAP_FREE (inv->depends_on);
1306       free (inv);
1307     }
1308   VEC_free (invariant_p, heap, invariants);
1309 }
1310
1311 /* Move the invariants out of the LOOP.  */
1312
1313 static void
1314 move_single_loop_invariants (struct loop *loop)
1315 {
1316   init_inv_motion_data ();
1317
1318   find_invariants (loop);
1319   find_invariants_to_move (optimize_loop_for_speed_p (loop));
1320   move_invariants (loop);
1321
1322   free_inv_motion_data ();
1323 }
1324
1325 /* Releases the auxiliary data for LOOP.  */
1326
1327 static void
1328 free_loop_data (struct loop *loop)
1329 {
1330   struct loop_data *data = LOOP_DATA (loop);
1331
1332   free (data);
1333   loop->aux = NULL;
1334 }
1335
1336 /* Move the invariants out of the loops.  */
1337
1338 void
1339 move_loop_invariants (void)
1340 {
1341   struct loop *loop;
1342   loop_iterator li;
1343
1344   df_set_flags (DF_EQ_NOTES + DF_DEFER_INSN_RESCAN);
1345   /* Process the loops, innermost first.  */
1346   FOR_EACH_LOOP (li, loop, LI_FROM_INNERMOST)
1347     {
1348       move_single_loop_invariants (loop);
1349     }
1350
1351   FOR_EACH_LOOP (li, loop, 0)
1352     {
1353       free_loop_data (loop);
1354     }
1355
1356   free (invariant_table);
1357   invariant_table = NULL;
1358   invariant_table_size = 0;
1359
1360 #ifdef ENABLE_CHECKING
1361   verify_flow_info ();
1362 #endif
1363 }