gcc/loop-invariant.c

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