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