gcc/loop-invariant.c

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