gcc/loop-invariant.c

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