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, N_INV_USES is the number of uses of
 987    invariants, NEW_REGS is the number of new variables already added due to
 988    the invariant motion.  The number of registers needed for it is stored in
 989    *REGS_NEEDED.  */
 990
 991 static int
 992 gain_for_invariant (struct invariant *inv, unsigned *regs_needed,
 993                     unsigned new_regs, unsigned regs_used, unsigned n_inv_uses)
 994 {
 995   int comp_cost, size_cost;
 996
 997   get_inv_cost (inv, &comp_cost, regs_needed);
 998   actual_stamp++;
 999
1000   size_cost = (global_cost_for_size (new_regs + *regs_needed,
1001                                      regs_used, n_inv_uses)
1002                - global_cost_for_size (new_regs, regs_used, n_inv_uses));
1003
1004   return comp_cost - size_cost;
1005 }
1006
1007 /* Finds invariant with best gain for moving.  Returns the gain, stores
1008    the invariant in *BEST and number of registers needed for it to
1009    *REGS_NEEDED.  REGS_USED is the number of registers used in
1010    the loop, N_INV_USES is the number of uses of invariants.  NEW_REGS
1011    is the number of new variables already added due to invariant motion.  */
1012
1013 static int
1014 best_gain_for_invariant (struct invariant **best, unsigned *regs_needed,
1015                          unsigned new_regs, unsigned regs_used,
1016                          unsigned n_inv_uses)
1017 {
1018   struct invariant *inv;
1019   int gain = 0, again;
1020   unsigned aregs_needed, invno;
1021
1022   for (invno = 0; VEC_iterate (invariant_p, invariants, invno, inv); invno++)
1023     {
1024       if (inv->move)
1025         continue;
1026
1027       /* Only consider the "representatives" of equivalent invariants.  */
1028       if (inv->eqto != inv->invno)
1029         continue;
1030
1031       again = gain_for_invariant (inv, &aregs_needed,
1032                                   new_regs, regs_used, n_inv_uses);
1033       if (again > gain)
1034         {
1035           gain = again;
1036           *best = inv;
1037           *regs_needed = aregs_needed;
1038         }
1039     }
1040
1041   return gain;
1042 }
1043
1044 /* Marks invariant INVNO and all its dependencies for moving.  */
1045
1046 static void
1047 set_move_mark (unsigned invno)
1048 {
1049   struct invariant *inv = VEC_index (invariant_p, invariants, invno);
1050   bitmap_iterator bi;
1051
1052   /* Find the representative of the class of the equivalent invariants.  */
1053   inv = VEC_index (invariant_p, invariants, inv->eqto);
1054
1055   if (inv->move)
1056     return;
1057   inv->move = true;
1058
1059   if (dump_file)
1060     fprintf (dump_file, "Decided to move invariant %d\n", invno);
1061
1062   EXECUTE_IF_SET_IN_BITMAP (inv->depends_on, 0, invno, bi)
1063     {
1064       set_move_mark (invno);
1065     }
1066 }
1067
1068 /* Determines which invariants to move.  */
1069
1070 static void
1071 find_invariants_to_move (void)
1072 {
1073   unsigned i, regs_used, n_inv_uses, regs_needed = 0, new_regs;
1074   struct invariant *inv = NULL;
1075   unsigned int n_regs = DF_REG_SIZE (df);
1076
1077   if (!VEC_length (invariant_p, invariants))
1078     return;
1079
1080   /* Now something slightly more involved.  First estimate the number of used
1081      registers.  */
1082   n_inv_uses = 0;
1083
1084   /* We do not really do a good job in this estimation; put some initial bound
1085      here to stand for induction variables etc. that we do not detect.  */
1086   regs_used = 2;
1087
1088   for (i = 0; i < n_regs; i++)
1089     {
1090       if (!DF_REGNO_FIRST_DEF (df, i) && DF_REGNO_LAST_USE (df, i))
1091         {
1092           /* This is a value that is used but not changed inside loop.  */
1093           regs_used++;
1094         }
1095     }
1096
1097   for (i = 0; VEC_iterate (invariant_p, invariants, i, inv); i++)
1098     {
1099       if (inv->def)
1100         n_inv_uses += inv->def->n_uses;
1101     }
1102
1103   new_regs = 0;
1104   while (best_gain_for_invariant (&inv, &regs_needed,
1105                                   new_regs, regs_used, n_inv_uses) > 0)
1106     {
1107       set_move_mark (inv->invno);
1108       new_regs += regs_needed;
1109     }
1110 }
1111
1112 /* Returns true if all insns in SEQ are valid.  */
1113
1114 static bool
1115 seq_insns_valid_p (rtx seq)
1116 {
1117   rtx x;
1118
1119   for (x = seq; x; x = NEXT_INSN (x))
1120     if (insn_invalid_p (x))
1121       return false;
1122
1123   return true;
1124 }
1125
1126 /* Move invariant INVNO out of the LOOP.  Returns true if this succeeds, false
1127    otherwise.  */
1128
1129 static bool
1130 move_invariant_reg (struct loop *loop, unsigned invno)
1131 {
1132   struct invariant *inv = VEC_index (invariant_p, invariants, invno);
1133   struct invariant *repr = VEC_index (invariant_p, invariants, inv->eqto);
1134   unsigned i;
1135   basic_block preheader = loop_preheader_edge (loop)->src;
1136   rtx reg, set, dest, seq, op;
1137   struct use *use;
1138   bitmap_iterator bi;
1139
1140   if (inv->reg)
1141     return true;
1142   if (!repr->move)
1143     return false;
1144
1145   /* If this is a representative of the class of equivalent invariants,
1146      really move the invariant.  Otherwise just replace its use with
1147      the register used for the representative.  */
1148   if (inv == repr)
1149     {
1150       if (inv->depends_on)
1151         {
1152           EXECUTE_IF_SET_IN_BITMAP (inv->depends_on, 0, i, bi)
1153             {
1154               if (!move_invariant_reg (loop, i))
1155                 goto fail;
1156             }
1157         }
1158
1159       /* Move the set out of the loop.  If the set is always executed (we could
1160          omit this condition if we know that the register is unused outside of the
1161          loop, but it does not seem worth finding out) and it has no uses that
1162          would not be dominated by it, we may just move it (TODO).  Otherwise we
1163          need to create a temporary register.  */
1164       set = single_set (inv->insn);
1165       dest = SET_DEST (set);
1166       reg = gen_reg_rtx (GET_MODE (dest));
1167
1168       /* If the SET_DEST of the invariant insn is a pseudo, we can just move
1169          the insn out of the loop.  Otherwise, we have to use gen_move_insn
1170          to let emit_move_insn produce a valid instruction stream.  */
1171       if (REG_P (dest) && !HARD_REGISTER_P (dest))
1172         {
1173           emit_insn_after (gen_move_insn (dest, reg), inv->insn);
1174           SET_DEST (set) = reg;
1175           reorder_insns (inv->insn, inv->insn, BB_END (preheader));
1176         }
1177       else
1178         {
1179           start_sequence ();
1180           op = force_operand (SET_SRC (set), reg);
1181           if (op != reg)
1182             emit_move_insn (reg, op);
1183           seq = get_insns ();
1184           end_sequence ();
1185
1186           if (!seq_insns_valid_p (seq))
1187             goto fail;
1188           emit_insn_after (seq, BB_END (preheader));
1189
1190           emit_insn_after (gen_move_insn (dest, reg), inv->insn);
1191           delete_insn (inv->insn);
1192         }
1193     }
1194   else
1195     {
1196       if (!move_invariant_reg (loop, repr->invno))
1197         goto fail;
1198       reg = repr->reg;
1199       set = single_set (inv->insn);
1200       emit_insn_after (gen_move_insn (SET_DEST (set), reg), inv->insn);
1201       delete_insn (inv->insn);
1202     }
1203
1204   inv->reg = reg;
1205
1206   /* Replace the uses we know to be dominated.  It saves work for copy
1207      propagation, and also it is necessary so that dependent invariants
1208      are computed right.  */
1209   if (inv->def)
1210     {
1211       for (use = inv->def->uses; use; use = use->next)
1212         *use->pos = reg;
1213     }
1214
1215   return true;
1216
1217 fail:
1218   /* If we failed, clear move flag, so that we do not try to move inv
1219      again.  */
1220   if (dump_file)
1221     fprintf (dump_file, "Failed to move invariant %d\n", invno);
1222   inv->move = false;
1223   inv->reg = NULL_RTX;
1224   return false;
1225 }
1226
1227 /* Move selected invariant out of the LOOP.  Newly created regs are marked
1228    in TEMPORARY_REGS.  */
1229
1230 static void
1231 move_invariants (struct loop *loop)
1232 {
1233   struct invariant *inv;
1234   unsigned i;
1235
1236   for (i = 0; VEC_iterate (invariant_p, invariants, i, inv); i++)
1237     move_invariant_reg (loop, i);
1238 }
1239
1240 /* Initializes invariant motion data.  */
1241
1242 static void
1243 init_inv_motion_data (void)
1244 {
1245   actual_stamp = 1;
1246
1247   invariants = VEC_alloc (invariant_p, heap, 100);
1248 }
1249
1250 /* Frees the data allocated by invariant motion.  */
1251
1252 static void
1253 free_inv_motion_data (void)
1254 {
1255   unsigned i;
1256   struct def *def;
1257   struct invariant *inv;
1258
1259   for (i = 0; i < DF_DEFS_SIZE (df); i++)
1260     {
1261       struct df_ref * ref = DF_DEFS_GET (df, i);
1262       if (!ref)
1263         continue;
1264
1265       inv = DF_REF_DATA (ref);
1266       if (!inv)
1267         continue;
1268
1269       def = inv->def;
1270       gcc_assert (def != NULL);
1271
1272       free_use_list (def->uses);
1273       free (def);
1274       DF_REF_DATA (ref) = NULL;
1275     }
1276
1277   for (i = 0; VEC_iterate (invariant_p, invariants, i, inv); i++)
1278     {
1279       BITMAP_FREE (inv->depends_on);
1280       free (inv);
1281     }
1282   VEC_free (invariant_p, heap, invariants);
1283 }
1284
1285 /* Move the invariants out of the LOOP.  */
1286
1287 static void
1288 move_single_loop_invariants (struct loop *loop)
1289 {
1290   init_inv_motion_data ();
1291
1292   find_invariants (loop);
1293   find_invariants_to_move ();
1294   move_invariants (loop);
1295
1296   free_inv_motion_data ();
1297 }
1298
1299 /* Releases the auxiliary data for LOOP.  */
1300
1301 static void
1302 free_loop_data (struct loop *loop)
1303 {
1304   struct loop_data *data = LOOP_DATA (loop);
1305
1306   free (data);
1307   loop->aux = NULL;
1308 }
1309
1310 /* Move the invariants out of the LOOPS.  */
1311
1312 void
1313 move_loop_invariants (struct loops *loops)
1314 {
1315   struct loop *loop;
1316   unsigned i;
1317
1318   df = df_init (DF_HARD_REGS | DF_EQUIV_NOTES);
1319   df_chain_add_problem (df, DF_UD_CHAIN);
1320
1321   /* Process the loops, innermost first.  */
1322   loop = loops->tree_root;
1323   while (loop->inner)
1324     loop = loop->inner;
1325
1326   while (loop != loops->tree_root)
1327     {
1328       move_single_loop_invariants (loop);
1329
1330       if (loop->next)
1331         {
1332           loop = loop->next;
1333           while (loop->inner)
1334             loop = loop->inner;
1335         }
1336       else
1337         loop = loop->outer;
1338     }
1339
1340   for (i = 1; i < loops->num; i++)
1341     if (loops->parray[i])
1342       free_loop_data (loops->parray[i]);
1343
1344   df_finish (df);
1345   df = NULL;
1346
1347 #ifdef ENABLE_CHECKING
1348   verify_flow_info ();
1349 #endif
1350 }