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