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