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