gcc/loop-invariant.c

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