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