gcc/loop-invariant.c

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