contrib/gcc-5.0/gcc/lra-remat.c

   1 /* Rematerialize pseudos values.
   2    Copyright (C) 2014-2015 Free Software Foundation, Inc.
   3    Contributed by Vladimir Makarov <vmakarov@redhat.com>.
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify it under
   8 the terms of the GNU General Public License as published by the Free
   9 Software Foundation; either version 3, or (at your option) any later
  10 version.
  11
  12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  15 for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING3.  If not see
  19 <http://www.gnu.org/licenses/>.  */
  20
  21 /* This code objective is to rematerialize spilled pseudo values.  To
  22    do this we calculate available insn candidates.  The candidate is
  23    available at some point if there is dominated set of insns with the
  24    same pattern, the insn inputs are not dying or modified on any path
  25    from the set, the outputs are not modified.
  26
  27    The insns containing memory or spilled pseudos (except for the
  28    rematerialized pseudo) are not considered as such insns are not
  29    profitable in comparison with regular loads of spilled pseudo
  30    values.  That simplifies the implementation as we don't need to
  31    deal with memory aliasing.
  32
  33    To speed up available candidate calculation, we calculate partially
  34    available candidates first and use them for initialization of the
  35    availability.  That is because (partial) availability sets are
  36    sparse.
  37
  38    The rematerialization sub-pass could be improved further in the
  39    following ways:
  40
  41    o We could make longer live ranges of inputs in the
  42      rematerialization candidates if their hard registers are not used
  43      for other purposes.  This could be complicated if we need to
  44      update BB live info information as LRA does not use
  45      DF-infrastructure for compile-time reasons.  This problem could
  46      be overcome if constrain making live ranges longer only in BB/EBB
  47      scope.
  48    o We could use cost-based decision to choose rematerialization insn
  49      (currently all insns without memory is can be used).
  50    o We could use other free hard regs for unused output pseudos in
  51      rematerialization candidates although such cases probably will
  52      be very rare.  */
  53
  54
  55 #include "config.h"
  56 #include "system.h"
  57 #include "coretypes.h"
  58 #include "tm.h"
  59 #include "hard-reg-set.h"
  60 #include "rtl.h"
  61 #include "rtl-error.h"
  62 #include "tm_p.h"
  63 #include "target.h"
  64 #include "insn-config.h"
  65 #include "recog.h"
  66 #include "output.h"
  67 #include "regs.h"
  68 #include "hashtab.h"
  69 #include "hash-set.h"
  70 #include "vec.h"
  71 #include "machmode.h"
  72 #include "input.h"
  73 #include "function.h"
  74 #include "symtab.h"
  75 #include "flags.h"
  76 #include "statistics.h"
  77 #include "double-int.h"
  78 #include "real.h"
  79 #include "fixed-value.h"
  80 #include "alias.h"
  81 #include "wide-int.h"
  82 #include "inchash.h"
  83 #include "tree.h"
  84 #include "expmed.h"
  85 #include "dojump.h"
  86 #include "explow.h"
  87 #include "calls.h"
  88 #include "emit-rtl.h"
  89 #include "varasm.h"
  90 #include "stmt.h"
  91 #include "expr.h"
  92 #include "predict.h"
  93 #include "dominance.h"
  94 #include "cfg.h"
  95 #include "basic-block.h"
  96 #include "except.h"
  97 #include "df.h"
  98 #include "ira.h"
  99 #include "sparseset.h"
 100 #include "params.h"
 101 #include "lra-int.h"
 102
 103 /* Number of candidates for rematerialization.  */
 104 static unsigned int cands_num;
 105
 106 /* The following is used for representation of call_used_reg_set in
 107    form array whose elements are hard register numbers with nonzero bit
 108    in CALL_USED_REG_SET. */
 109 static int call_used_regs_arr_len;
 110 static int call_used_regs_arr[FIRST_PSEUDO_REGISTER];
 111
 112 /* Bitmap used for different calculations.  */
 113 static bitmap_head temp_bitmap;
 114
 115 typedef struct cand *cand_t;
 116 typedef const struct cand *const_cand_t;
 117
 118 /* Insn candidates for rematerialization.  The candidate insn should
 119    have the following properies:
 120    o no any memory (as access to memory is non-profitable)
 121    o no INOUT regs (it means no non-paradoxical subreg of output reg)
 122    o one output spilled pseudo (or reload pseudo of a spilled pseudo)
 123    o all other pseudos are with assigned hard regs.  */
 124 struct cand
 125 {
 126   /* Index of the candidates in all_cands. */
 127   int index;
 128   /* The candidate insn.  */
 129   rtx_insn *insn;
 130   /* Insn pseudo regno for rematerialization.  */
 131   int regno;
 132   /* Non-negative if a reload pseudo is in the insn instead of the
 133      pseudo for rematerialization.  */
 134   int reload_regno;
 135   /* Number of the operand containing the regno or its reload
 136      regno.  */
 137   int nop;
 138   /* Next candidate for the same regno.  */
 139   cand_t next_regno_cand;
 140 };
 141
 142 /* Vector containing all candidates.  */
 143 static vec<cand_t> all_cands;
 144 /* Map: insn -> candidate representing it.  It is null if the insn can
 145    not be used for rematerialization.  */
 146 static cand_t *insn_to_cand;
 147
 148 /* Map regno -> candidates can be used for the regno
 149    rematerialization.  */
 150 static cand_t *regno_cands;
 151
 152 /* Data about basic blocks used for the rematerialization
 153    sub-pass.  */
 154 struct remat_bb_data
 155 {
 156   /* Basic block about which the below data are.  */
 157   basic_block bb;
 158   /* Registers changed in the basic block: */
 159   bitmap_head changed_regs;
 160   /* Registers becoming dead in the BB.  */
 161   bitmap_head dead_regs;
 162   /* Cands present in the BB whose in/out regs are not changed after
 163      the cands occurence and are not dead (except the reload
 164      regno).  */
 165   bitmap_head gen_cands;
 166   bitmap_head livein_cands; /* cands whose inputs live at the BB start.  */
 167   bitmap_head pavin_cands; /* cands partially available at BB entry.  */
 168   bitmap_head pavout_cands; /* cands partially available at BB exit.  */
 169   bitmap_head avin_cands; /* cands available at the entry of the BB.  */
 170   bitmap_head avout_cands; /* cands available at the exit of the BB.  */
 171 };
 172
 173 /* Array for all BB data.  Indexed by the corresponding BB index.  */
 174 typedef struct remat_bb_data *remat_bb_data_t;
 175
 176 /* Basic blocks for data flow problems -- all bocks except the special
 177    ones.  */
 178 static bitmap_head all_blocks;
 179
 180 /* All basic block data are referred through the following array.  */
 181 static remat_bb_data_t remat_bb_data;
 182
 183 /* Two small functions for access to the bb data.  */
 184 static inline remat_bb_data_t
 185 get_remat_bb_data (basic_block bb)
 186 {
 187   return &remat_bb_data[(bb)->index];
 188 }
 189
 190 static inline remat_bb_data_t
 191 get_remat_bb_data_by_index (int index)
 192 {
 193   return &remat_bb_data[index];
 194 }
 195
 196 \f
 197
 198 /* Recursive hash function for RTL X.  */
 199 static hashval_t
 200 rtx_hash (rtx x)
 201 {
 202   int i, j;
 203   enum rtx_code code;
 204   const char *fmt;
 205   hashval_t val = 0;
 206
 207   if (x == 0)
 208     return val;
 209
 210   code = GET_CODE (x);
 211   val += (int) code + 4095;
 212
 213   /* Some RTL can be compared nonrecursively.  */
 214   switch (code)
 215     {
 216     case REG:
 217       return val + REGNO (x);
 218
 219     case LABEL_REF:
 220       return iterative_hash_object (XEXP (x, 0), val);
 221
 222     case SYMBOL_REF:
 223       return iterative_hash_object (XSTR (x, 0), val);
 224
 225     case SCRATCH:
 226     case CONST_DOUBLE:
 227     case CONST_INT:
 228     case CONST_VECTOR:
 229       return val;
 230
 231     default:
 232       break;
 233     }
 234
 235   /* Hash the elements.  */
 236   fmt = GET_RTX_FORMAT (code);
 237   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
 238     {
 239       switch (fmt[i])
 240         {
 241         case 'w':
 242           val += XWINT (x, i);
 243           break;
 244
 245         case 'n':
 246         case 'i':
 247           val += XINT (x, i);
 248           break;
 249
 250         case 'V':
 251         case 'E':
 252           val += XVECLEN (x, i);
 253
 254           for (j = 0; j < XVECLEN (x, i); j++)
 255             val += rtx_hash (XVECEXP (x, i, j));
 256           break;
 257
 258         case 'e':
 259           val += rtx_hash (XEXP (x, i));
 260           break;
 261
 262         case 'S':
 263         case 's':
 264           val += htab_hash_string (XSTR (x, i));
 265           break;
 266
 267         case 'u':
 268         case '0':
 269         case 't':
 270           break;
 271
 272           /* It is believed that rtx's at this level will never
 273              contain anything but integers and other rtx's, except for
 274              within LABEL_REFs and SYMBOL_REFs.  */
 275         default:
 276           abort ();
 277         }
 278     }
 279   return val;
 280 }
 281
 282 \f
 283
 284 /* Hash table for the candidates.  Different insns (e.g. structurally
 285    the same insns or even insns with different unused output regs) can
 286    be represented by the same candidate in the table.  */
 287 static htab_t cand_table;
 288
 289 /* Hash function for candidate CAND.  */
 290 static hashval_t
 291 cand_hash (const void *cand)
 292 {
 293   const_cand_t c = (const_cand_t) cand;
 294   lra_insn_recog_data_t id = lra_get_insn_recog_data (c->insn);
 295   struct lra_static_insn_data *static_id = id->insn_static_data;
 296   int nops = static_id->n_operands;
 297   hashval_t hash = 0;
 298
 299   for (int i = 0; i < nops; i++)
 300     if (i == c->nop)
 301       hash = iterative_hash_object (c->regno, hash);
 302     else if (static_id->operand[i].type == OP_IN)
 303       hash = iterative_hash_object (*id->operand_loc[i], hash);
 304   return hash;
 305 }
 306
 307 /* Equal function for candidates CAND1 and CAND2.  They are equal if
 308    the corresponding candidate insns have the same code, the same
 309    regno for rematerialization, the same input operands.  */
 310 static int
 311 cand_eq_p (const void *cand1, const void *cand2)
 312 {
 313   const_cand_t c1 = (const_cand_t) cand1;
 314   const_cand_t c2 = (const_cand_t) cand2;
 315   lra_insn_recog_data_t id1 = lra_get_insn_recog_data (c1->insn);
 316   lra_insn_recog_data_t id2 = lra_get_insn_recog_data (c2->insn);
 317   struct lra_static_insn_data *static_id1 = id1->insn_static_data;
 318   int nops = static_id1->n_operands;
 319
 320   if (c1->regno != c2->regno
 321       || INSN_CODE (c1->insn) < 0
 322       || INSN_CODE (c1->insn) != INSN_CODE (c2->insn))
 323     return false;
 324   gcc_assert (c1->nop == c2->nop);
 325   for (int i = 0; i < nops; i++)
 326     if (i != c1->nop && static_id1->operand[i].type == OP_IN
 327         && *id1->operand_loc[i] != *id2->operand_loc[i])
 328       return false;
 329   return true;
 330 }
 331
 332 /* Insert candidate CAND into the table if it is not there yet.
 333    Return candidate which is in the table.  */
 334 static cand_t
 335 insert_cand (cand_t cand)
 336 {
 337   void **entry_ptr;
 338
 339   entry_ptr = htab_find_slot (cand_table, cand, INSERT);
 340   if (*entry_ptr == NULL)
 341     *entry_ptr = (void *) cand;
 342   return (cand_t) *entry_ptr;
 343 }
 344
 345 /* Free candidate CAND memory.  */
 346 static void
 347 free_cand (void *cand)
 348 {
 349   free (cand);
 350 }
 351
 352 /* Initiate the candidate table.  */
 353 static void
 354 initiate_cand_table (void)
 355 {
 356   cand_table = htab_create (8000, cand_hash, cand_eq_p,
 357                             (htab_del) free_cand);
 358 }
 359
 360 /* Finish the candidate table.  */
 361 static void
 362 finish_cand_table (void)
 363 {
 364   htab_delete (cand_table);
 365 }
 366
 367 \f
 368
 369 /* Return true if X contains memory or some UNSPEC.  We can not just
 370    check insn operands as memory or unspec might be not an operand
 371    itself but contain an operand.  Insn with memory access is not
 372    profitable for rematerialization.  Rematerialization of UNSPEC
 373    might result in wrong code generation as the UNPEC effect is
 374    unknown (e.g. generating a label).  */
 375 static bool
 376 bad_for_rematerialization_p (rtx x)
 377 {
 378   int i, j;
 379   const char *fmt;
 380   enum rtx_code code;
 381
 382   if (MEM_P (x) || GET_CODE (x) == UNSPEC || GET_CODE (x) == UNSPEC_VOLATILE)
 383     return true;
 384   code = GET_CODE (x);
 385   fmt = GET_RTX_FORMAT (code);
 386   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
 387     {
 388       if (fmt[i] == 'e')
 389         {
 390           if (bad_for_rematerialization_p (XEXP (x, i)))
 391             return true;
 392         }
 393       else if (fmt[i] == 'E')
 394         {
 395           for (j = XVECLEN (x, i) - 1; j >= 0; j--)
 396             if (bad_for_rematerialization_p (XVECEXP (x, i, j)))
 397               return true;
 398         }
 399     }
 400   return false;
 401 }
 402
 403 /* If INSN can not be used for rematerialization, return negative
 404    value.  If INSN can be considered as a candidate for
 405    rematerialization, return value which is the operand number of the
 406    pseudo for which the insn can be used for rematerialization.  Here
 407    we consider the insns without any memory, spilled pseudo (except
 408    for the rematerialization pseudo), or dying or unused regs.  */
 409 static int
 410 operand_to_remat (rtx_insn *insn)
 411 {
 412   lra_insn_recog_data_t id = lra_get_insn_recog_data (insn);
 413   struct lra_static_insn_data *static_id = id->insn_static_data;
 414   struct lra_insn_reg *reg, *found_reg = NULL;
 415
 416   /* Don't rematerialize insns which can change PC.  */
 417   if (JUMP_P (insn) || CALL_P (insn))
 418     return -1;
 419   /* First find a pseudo which can be rematerialized.  */
 420   for (reg = id->regs; reg != NULL; reg = reg->next)
 421     /* True FRAME_POINTER_NEEDED might be because we can not follow
 422        changing sp offsets, e.g. alloca is used.  If the insn contains
 423        stack pointer in such case, we can not rematerialize it as we
 424        can not know sp offset at a rematerialization place.  */
 425     if (reg->regno == STACK_POINTER_REGNUM && frame_pointer_needed)
 426       return -1;
 427     else if (reg->type == OP_OUT && ! reg->subreg_p
 428              && find_regno_note (insn, REG_UNUSED, reg->regno) == NULL)
 429       {
 430         /* We permits only one spilled reg.  */
 431         if (found_reg != NULL)
 432           return -1;
 433         found_reg = reg;
 434       }
 435   if (found_reg == NULL)
 436     return -1;
 437   if (found_reg->regno < FIRST_PSEUDO_REGISTER)
 438     return -1;
 439   if (bad_for_rematerialization_p (PATTERN (insn)))
 440     return -1;
 441   /* Check the other regs are not spilled. */
 442   for (reg = id->regs; reg != NULL; reg = reg->next)
 443     if (found_reg == reg)
 444       continue;
 445     else if (reg->type == OP_INOUT)
 446       return -1;
 447     else if (reg->regno >= FIRST_PSEUDO_REGISTER
 448              && reg_renumber[reg->regno] < 0)
 449       /* Another spilled reg.  */
 450       return -1;
 451     else if (reg->type == OP_IN)
 452       {
 453         if (find_regno_note (insn, REG_DEAD, reg->regno) != NULL)
 454           /* We don't want to make live ranges longer.  */
 455           return -1;
 456         /* Check that there is no output reg as the input one.  */
 457         for (struct lra_insn_reg *reg2 = id->regs;
 458              reg2 != NULL;
 459              reg2 = reg2->next)
 460           if (reg2->type == OP_OUT && reg->regno == reg2->regno)
 461             return -1;
 462         if (reg->regno < FIRST_PSEUDO_REGISTER)
 463           for (struct lra_insn_reg *reg2 = static_id->hard_regs;
 464                reg2 != NULL;
 465                reg2 = reg2->next)
 466             if (reg2->type == OP_OUT
 467                 && reg->regno <= reg2->regno
 468                 && (reg2->regno
 469                     < (reg->regno
 470                        + hard_regno_nregs[reg->regno][reg->biggest_mode])))
 471               return -1;
 472       }
 473   /* Find the rematerialization operand.  */
 474   int nop = static_id->n_operands;
 475   for (int i = 0; i < nop; i++)
 476     if (REG_P (*id->operand_loc[i])
 477         && (int) REGNO (*id->operand_loc[i]) == found_reg->regno)
 478       return i;
 479   return -1;
 480 }
 481
 482 /* Create candidate for INSN with rematerialization operand NOP and
 483    REGNO.  Insert the candidate into the table and set up the
 484    corresponding INSN_TO_CAND element.  */
 485 static void
 486 create_cand (rtx_insn *insn, int nop, int regno)
 487 {
 488   lra_insn_recog_data_t id = lra_get_insn_recog_data (insn);
 489   rtx reg = *id->operand_loc[nop];
 490   gcc_assert (REG_P (reg));
 491   int op_regno = REGNO (reg);
 492   gcc_assert (op_regno >= FIRST_PSEUDO_REGISTER);
 493   cand_t cand = XNEW (struct cand);
 494   cand->insn = insn;
 495   cand->nop = nop;
 496   cand->regno = regno;
 497   cand->reload_regno = op_regno == regno ? -1 : op_regno;
 498   gcc_assert (cand->regno >= 0);
 499   cand_t cand_in_table = insert_cand (cand);
 500   insn_to_cand[INSN_UID (insn)] = cand_in_table;
 501   if (cand != cand_in_table)
 502     free (cand);
 503   else
 504     {
 505       /* A new cand.  */
 506       cand->index = all_cands.length ();
 507       all_cands.safe_push (cand);
 508       cand->next_regno_cand = regno_cands[cand->regno];
 509       regno_cands[cand->regno] = cand;
 510     }
 511 }
 512
 513 /* Create rematerialization candidates (inserting them into the
 514    table).  */
 515 static void
 516 create_cands (void)
 517 {
 518   rtx_insn *insn;
 519   struct potential_cand
 520   {
 521     rtx_insn *insn;
 522     int nop;
 523   };
 524   struct potential_cand *regno_potential_cand;
 525
 526   /* Create candidates.  */
 527   regno_potential_cand = XCNEWVEC (struct potential_cand, max_reg_num ());
 528   for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
 529     if (INSN_P (insn))
 530       {
 531         rtx set;
 532         int src_regno, dst_regno;
 533         rtx_insn *insn2;
 534         lra_insn_recog_data_t id = lra_get_insn_recog_data (insn);
 535         int nop = operand_to_remat (insn);
 536         int regno = -1;
 537
 538         if ((set = single_set (insn)) != NULL
 539             && REG_P (SET_SRC (set)) && REG_P (SET_DEST (set))
 540             && ((src_regno = REGNO (SET_SRC (set)))
 541                 >= lra_constraint_new_regno_start)
 542             && (dst_regno = REGNO (SET_DEST (set))) >= FIRST_PSEUDO_REGISTER
 543             && reg_renumber[dst_regno] < 0
 544             && (insn2 = regno_potential_cand[src_regno].insn) != NULL
 545             && BLOCK_FOR_INSN (insn2) == BLOCK_FOR_INSN (insn))
 546           /* It is an output reload insn after insn can be
 547              rematerialized (potential candidate).  */
 548           create_cand (insn2, regno_potential_cand[src_regno].nop, dst_regno);
 549         if (nop < 0)
 550           goto fail;
 551         gcc_assert (REG_P (*id->operand_loc[nop]));
 552         regno = REGNO (*id->operand_loc[nop]);
 553         gcc_assert (regno >= FIRST_PSEUDO_REGISTER);
 554         if (reg_renumber[regno] < 0)
 555           create_cand (insn, nop, regno);
 556         else
 557           {
 558             regno_potential_cand[regno].insn = insn;
 559             regno_potential_cand[regno].nop = nop;
 560             goto fail;
 561           }
 562         regno = -1;
 563       fail:
 564         for (struct lra_insn_reg *reg = id->regs; reg != NULL; reg = reg->next)
 565           if (reg->type != OP_IN && reg->regno != regno
 566               && reg->regno >= FIRST_PSEUDO_REGISTER)
 567             regno_potential_cand[reg->regno].insn = NULL;
 568       }
 569   cands_num = all_cands.length ();
 570   free (regno_potential_cand);
 571 }
 572
 573 \f
 574
 575 /* Create and initialize BB data.  */
 576 static void
 577 create_remat_bb_data (void)
 578 {
 579   basic_block bb;
 580   remat_bb_data_t bb_info;
 581
 582   remat_bb_data = XNEWVEC (struct remat_bb_data,
 583                            last_basic_block_for_fn (cfun));
 584   FOR_ALL_BB_FN (bb, cfun)
 585     {
 586 #ifdef ENABLE_CHECKING
 587       if (bb->index < 0 || bb->index >= last_basic_block_for_fn (cfun))
 588         abort ();
 589 #endif
 590       bb_info = get_remat_bb_data (bb);
 591       bb_info->bb = bb;
 592       bitmap_initialize (&bb_info->changed_regs, &reg_obstack);
 593       bitmap_initialize (&bb_info->dead_regs, &reg_obstack);
 594       bitmap_initialize (&bb_info->gen_cands, &reg_obstack);
 595       bitmap_initialize (&bb_info->livein_cands, &reg_obstack);
 596       bitmap_initialize (&bb_info->pavin_cands, &reg_obstack);
 597       bitmap_initialize (&bb_info->pavout_cands, &reg_obstack);
 598       bitmap_initialize (&bb_info->avin_cands, &reg_obstack);
 599       bitmap_initialize (&bb_info->avout_cands, &reg_obstack);
 600     }
 601 }
 602
 603 /* Dump all candidates to DUMP_FILE.  */
 604 static void
 605 dump_cands (FILE *dump_file)
 606 {
 607   int i;
 608   cand_t cand;
 609
 610   fprintf (dump_file, "\nCands:\n");
 611   for (i = 0; i < (int) cands_num; i++)
 612     {
 613       cand = all_cands[i];
 614       fprintf (dump_file, "%d (nop=%d, remat_regno=%d, reload_regno=%d):\n",
 615                i, cand->nop, cand->regno, cand->reload_regno);
 616       print_inline_rtx (dump_file, cand->insn, 6);
 617       fprintf (dump_file, "\n");
 618     }
 619 }
 620
 621 /* Dump all candidates and BB data.  */
 622 static void
 623 dump_candidates_and_remat_bb_data (void)
 624 {
 625   basic_block bb;
 626
 627   if (lra_dump_file == NULL)
 628     return;
 629   dump_cands (lra_dump_file);
 630   FOR_EACH_BB_FN (bb, cfun)
 631     {
 632       fprintf (lra_dump_file, "\nBB %d:\n", bb->index);
 633       /* Livein */
 634       fprintf (lra_dump_file, "  register live in:");
 635       dump_regset (df_get_live_in (bb), lra_dump_file);
 636       putc ('\n', lra_dump_file);
 637       /* Liveout */
 638       fprintf (lra_dump_file, "  register live out:");
 639       dump_regset (df_get_live_out (bb), lra_dump_file);
 640       putc ('\n', lra_dump_file);
 641       /* Changed/dead regs: */
 642       fprintf (lra_dump_file, "  changed regs:");
 643       dump_regset (&get_remat_bb_data (bb)->changed_regs, lra_dump_file);
 644       putc ('\n', lra_dump_file);
 645       fprintf (lra_dump_file, "  dead regs:");
 646       dump_regset (&get_remat_bb_data (bb)->dead_regs, lra_dump_file);
 647       putc ('\n', lra_dump_file);
 648       lra_dump_bitmap_with_title ("cands generated in BB",
 649                                   &get_remat_bb_data (bb)->gen_cands, bb->index);
 650       lra_dump_bitmap_with_title ("livein cands in BB",
 651                                   &get_remat_bb_data (bb)->livein_cands, bb->index);
 652       lra_dump_bitmap_with_title ("pavin cands in BB",
 653                                   &get_remat_bb_data (bb)->pavin_cands, bb->index);
 654       lra_dump_bitmap_with_title ("pavout cands in BB",
 655                                   &get_remat_bb_data (bb)->pavout_cands, bb->index);
 656       lra_dump_bitmap_with_title ("avin cands in BB",
 657                                   &get_remat_bb_data (bb)->avin_cands, bb->index);
 658       lra_dump_bitmap_with_title ("avout cands in BB",
 659                                   &get_remat_bb_data (bb)->avout_cands, bb->index);
 660     }
 661 }
 662
 663 /* Free all BB data.  */
 664 static void
 665 finish_remat_bb_data (void)
 666 {
 667   basic_block bb;
 668
 669   FOR_EACH_BB_FN (bb, cfun)
 670     {
 671       bitmap_clear (&get_remat_bb_data (bb)->avout_cands);
 672       bitmap_clear (&get_remat_bb_data (bb)->avin_cands);
 673       bitmap_clear (&get_remat_bb_data (bb)->pavout_cands);
 674       bitmap_clear (&get_remat_bb_data (bb)->pavin_cands);
 675       bitmap_clear (&get_remat_bb_data (bb)->livein_cands);
 676       bitmap_clear (&get_remat_bb_data (bb)->gen_cands);
 677       bitmap_clear (&get_remat_bb_data (bb)->dead_regs);
 678       bitmap_clear (&get_remat_bb_data (bb)->changed_regs);
 679     }
 680   free (remat_bb_data);
 681 }
 682
 683 \f
 684
 685 /* Update changed_regs and dead_regs of BB from INSN.  */
 686 static void
 687 set_bb_regs (basic_block bb, rtx_insn *insn)
 688 {
 689   lra_insn_recog_data_t id = lra_get_insn_recog_data (insn);
 690   struct lra_insn_reg *reg;
 691
 692   for (reg = id->regs; reg != NULL; reg = reg->next)
 693     if (reg->type != OP_IN)
 694       bitmap_set_bit (&get_remat_bb_data (bb)->changed_regs, reg->regno);
 695     else
 696       {
 697         if (find_regno_note (insn, REG_DEAD, (unsigned) reg->regno) != NULL)
 698           bitmap_set_bit (&get_remat_bb_data (bb)->dead_regs, reg->regno);
 699       }
 700   if (CALL_P (insn))
 701     for (int i = 0; i < call_used_regs_arr_len; i++)
 702       bitmap_set_bit (&get_remat_bb_data (bb)->dead_regs,
 703                       call_used_regs_arr[i]);
 704 }
 705
 706 /* Calculate changed_regs and dead_regs for each BB.  */
 707 static void
 708 calculate_local_reg_remat_bb_data (void)
 709 {
 710   basic_block bb;
 711   rtx_insn *insn;
 712
 713   FOR_EACH_BB_FN (bb, cfun)
 714     FOR_BB_INSNS (bb, insn)
 715       if (INSN_P (insn))
 716         set_bb_regs (bb, insn);
 717 }
 718
 719 \f
 720
 721 /* Return true if REGNO is an input operand of INSN.  */
 722 static bool
 723 input_regno_present_p (rtx_insn *insn, int regno)
 724 {
 725   lra_insn_recog_data_t id = lra_get_insn_recog_data (insn);
 726   struct lra_insn_reg *reg;
 727
 728   for (reg = id->regs; reg != NULL; reg = reg->next)
 729     if (reg->type == OP_IN && reg->regno == regno)
 730       return true;
 731   return false;
 732 }
 733
 734 /* Return true if a call used register is an input operand of INSN.  */
 735 static bool
 736 call_used_input_regno_present_p (rtx_insn *insn)
 737 {
 738   lra_insn_recog_data_t id = lra_get_insn_recog_data (insn);
 739   struct lra_insn_reg *reg;
 740
 741   for (reg = id->regs; reg != NULL; reg = reg->next)
 742     if (reg->type == OP_IN && reg->regno <= FIRST_PSEUDO_REGISTER
 743         && TEST_HARD_REG_BIT (call_used_reg_set, reg->regno))
 744       return true;
 745   return false;
 746 }
 747
 748 /* Calculate livein_cands for each BB.  */
 749 static void
 750 calculate_livein_cands (void)
 751 {
 752   basic_block bb;
 753
 754   FOR_EACH_BB_FN (bb, cfun)
 755     {
 756       bitmap livein_regs = df_get_live_in (bb);
 757       bitmap livein_cands = &get_remat_bb_data (bb)->livein_cands;
 758       for (unsigned int i = 0; i < cands_num; i++)
 759         {
 760           cand_t cand = all_cands[i];
 761           lra_insn_recog_data_t id = lra_get_insn_recog_data (cand->insn);
 762           struct lra_insn_reg *reg;
 763
 764           for (reg = id->regs; reg != NULL; reg = reg->next)
 765             if (reg->type == OP_IN && ! bitmap_bit_p (livein_regs, reg->regno))
 766               break;
 767           if (reg == NULL)
 768             bitmap_set_bit (livein_cands, i);
 769         }
 770     }
 771 }
 772
 773 /* Calculate gen_cands for each BB.  */
 774 static void
 775 calculate_gen_cands (void)
 776 {
 777   basic_block bb;
 778   bitmap gen_cands;
 779   bitmap_head gen_insns;
 780   rtx_insn *insn;
 781
 782   bitmap_initialize (&gen_insns, &reg_obstack);
 783   FOR_EACH_BB_FN (bb, cfun)
 784     {
 785       gen_cands = &get_remat_bb_data (bb)->gen_cands;
 786       bitmap_clear (&gen_insns);
 787       FOR_BB_INSNS (bb, insn)
 788         if (INSN_P (insn))
 789           {
 790             lra_insn_recog_data_t id = lra_get_insn_recog_data (insn);
 791             struct lra_insn_reg *reg;
 792             unsigned int uid;
 793             bitmap_iterator bi;
 794             cand_t cand;
 795             rtx set;
 796             int src_regno = -1, dst_regno = -1;
 797
 798             if ((set = single_set (insn)) != NULL
 799                 && REG_P (SET_SRC (set)) && REG_P (SET_DEST (set)))
 800               {
 801                 src_regno = REGNO (SET_SRC (set));
 802                 dst_regno = REGNO (SET_DEST (set));
 803               }
 804
 805             /* Update gen_cands:  */
 806             bitmap_clear (&temp_bitmap);
 807             for (reg = id->regs; reg != NULL; reg = reg->next)
 808               if (reg->type != OP_IN
 809                   || find_regno_note (insn, REG_DEAD, reg->regno) != NULL)
 810                 EXECUTE_IF_SET_IN_BITMAP (&gen_insns, 0, uid, bi)
 811                   {
 812                     rtx_insn *insn2 = lra_insn_recog_data[uid]->insn;
 813
 814                     cand = insn_to_cand[INSN_UID (insn2)];
 815                     gcc_assert (cand != NULL);
 816                     /* Ignore the reload insn.  */
 817                     if (src_regno == cand->reload_regno
 818                         && dst_regno == cand->regno)
 819                       continue;
 820                     if (cand->regno == reg->regno
 821                         || input_regno_present_p (insn2, reg->regno))
 822                       {
 823                         bitmap_clear_bit (gen_cands, cand->index);
 824                         bitmap_set_bit (&temp_bitmap, uid);
 825                       }
 826                   }
 827
 828             if (CALL_P (insn))
 829               EXECUTE_IF_SET_IN_BITMAP (&gen_insns, 0, uid, bi)
 830                 {
 831                   rtx_insn *insn2 = lra_insn_recog_data[uid]->insn;
 832
 833                   cand = insn_to_cand[INSN_UID (insn2)];
 834                   gcc_assert (cand != NULL);
 835                   if (call_used_input_regno_present_p (insn2))
 836                     {
 837                       bitmap_clear_bit (gen_cands, cand->index);
 838                       bitmap_set_bit (&temp_bitmap, uid);
 839                     }
 840                 }
 841             bitmap_and_compl_into (&gen_insns, &temp_bitmap);
 842
 843             cand = insn_to_cand[INSN_UID (insn)];
 844             if (cand != NULL)
 845               {
 846                 bitmap_set_bit (gen_cands, cand->index);
 847                 bitmap_set_bit (&gen_insns, INSN_UID (insn));
 848               }
 849           }
 850     }
 851   bitmap_clear (&gen_insns);
 852 }
 853
 854 \f
 855
 856 /* The common transfer function used by the DF equation solver to
 857    propagate (partial) availability info BB_IN to BB_OUT through block
 858    with BB_INDEX according to the following equation:
 859
 860       bb.out =  ((bb.in & bb.livein) - bb.killed) OR  bb.gen
 861 */
 862 static bool
 863 cand_trans_fun (int bb_index, bitmap bb_in, bitmap bb_out)
 864 {
 865   remat_bb_data_t bb_info;
 866   bitmap bb_livein, bb_changed_regs, bb_dead_regs;
 867   unsigned int cid;
 868   bitmap_iterator bi;
 869
 870   bb_info = get_remat_bb_data_by_index (bb_index);
 871   bb_livein = &bb_info->livein_cands;
 872   bb_changed_regs = &bb_info->changed_regs;
 873   bb_dead_regs = &bb_info->dead_regs;
 874   /* Calculate killed avin cands -- cands whose regs are changed or
 875      becoming dead in the BB.  We calculate it here as we hope that
 876      repeated calculations are compensated by smaller size of BB_IN in
 877      comparison with all candidates number.  */
 878   bitmap_clear (&temp_bitmap);
 879   EXECUTE_IF_SET_IN_BITMAP (bb_in, 0, cid, bi)
 880     {
 881       cand_t cand = all_cands[cid];
 882       lra_insn_recog_data_t id = lra_get_insn_recog_data (cand->insn);
 883       struct lra_insn_reg *reg;
 884
 885       if (! bitmap_bit_p (bb_livein, cid))
 886         {
 887           bitmap_set_bit (&temp_bitmap, cid);
 888           continue;
 889         }
 890       for (reg = id->regs; reg != NULL; reg = reg->next)
 891         /* Ignore all outputs which are not the regno for
 892            rematerialization.  */
 893         if (reg->type == OP_OUT && reg->regno != cand->regno)
 894           continue;
 895         else if (bitmap_bit_p (bb_changed_regs, reg->regno)
 896                  || bitmap_bit_p (bb_dead_regs, reg->regno))
 897           {
 898             bitmap_set_bit (&temp_bitmap, cid);
 899             break;
 900           }
 901       /* Check regno for rematerialization.  */
 902       if (bitmap_bit_p (bb_changed_regs, cand->regno)
 903           || bitmap_bit_p (bb_dead_regs, cand->regno))
 904         bitmap_set_bit (&temp_bitmap, cid);
 905     }
 906   return bitmap_ior_and_compl (bb_out,
 907                                &bb_info->gen_cands, bb_in, &temp_bitmap);
 908 }
 909
 910 \f
 911
 912 /* The transfer function used by the DF equation solver to propagate
 913    partial candidate availability info through block with BB_INDEX
 914    according to the following equation:
 915
 916      bb.pavout = ((bb.pavin & bb.livein) - bb.killed) OR bb.gen
 917 */
 918 static bool
 919 cand_pav_trans_fun (int bb_index)
 920 {
 921   remat_bb_data_t bb_info;
 922
 923   bb_info = get_remat_bb_data_by_index (bb_index);
 924   return cand_trans_fun (bb_index, &bb_info->pavin_cands,
 925                          &bb_info->pavout_cands);
 926 }
 927
 928 /* The confluence function used by the DF equation solver to set up
 929    cand_pav info for a block BB without predecessor.  */
 930 static void
 931 cand_pav_con_fun_0 (basic_block bb)
 932 {
 933   bitmap_clear (&get_remat_bb_data (bb)->pavin_cands);
 934 }
 935
 936 /* The confluence function used by the DF equation solver to propagate
 937    partial candidate availability info from predecessor to successor
 938    on edge E (pred->bb) according to the following equation:
 939
 940       bb.pavin_cands = 0 for entry block | OR (pavout_cands of predecessors)
 941  */
 942 static bool
 943 cand_pav_con_fun_n (edge e)
 944 {
 945   basic_block pred = e->src;
 946   basic_block bb = e->dest;
 947   remat_bb_data_t bb_info;
 948   bitmap bb_pavin, pred_pavout;
 949
 950   bb_info = get_remat_bb_data (bb);
 951   bb_pavin = &bb_info->pavin_cands;
 952   pred_pavout = &get_remat_bb_data (pred)->pavout_cands;
 953   return bitmap_ior_into (bb_pavin, pred_pavout);
 954 }
 955
 956 \f
 957
 958 /* The transfer function used by the DF equation solver to propagate
 959    candidate availability info through block with BB_INDEX according
 960    to the following equation:
 961
 962       bb.avout =  ((bb.avin & bb.livein) - bb.killed) OR  bb.gen
 963 */
 964 static bool
 965 cand_av_trans_fun (int bb_index)
 966 {
 967   remat_bb_data_t bb_info;
 968
 969   bb_info = get_remat_bb_data_by_index (bb_index);
 970   return cand_trans_fun (bb_index, &bb_info->avin_cands,
 971                          &bb_info->avout_cands);
 972 }
 973
 974 /* The confluence function used by the DF equation solver to set up
 975    cand_av info for a block BB without predecessor.  */
 976 static void
 977 cand_av_con_fun_0 (basic_block bb)
 978 {
 979   bitmap_clear (&get_remat_bb_data (bb)->avin_cands);
 980 }
 981
 982 /* The confluence function used by the DF equation solver to propagate
 983    cand_av info from predecessor to successor on edge E (pred->bb)
 984    according to the following equation:
 985
 986       bb.avin_cands = 0 for entry block | AND (avout_cands of predecessors)
 987  */
 988 static bool
 989 cand_av_con_fun_n (edge e)
 990 {
 991   basic_block pred = e->src;
 992   basic_block bb = e->dest;
 993   remat_bb_data_t bb_info;
 994   bitmap bb_avin, pred_avout;
 995
 996   bb_info = get_remat_bb_data (bb);
 997   bb_avin = &bb_info->avin_cands;
 998   pred_avout = &get_remat_bb_data (pred)->avout_cands;
 999   return bitmap_and_into (bb_avin, pred_avout);
1000 }
1001
1002 /* Calculate available candidates for each BB.  */
1003 static void
1004 calculate_global_remat_bb_data (void)
1005 {
1006   basic_block bb;
1007
1008   df_simple_dataflow
1009     (DF_FORWARD, NULL, cand_pav_con_fun_0, cand_pav_con_fun_n,
1010      cand_pav_trans_fun, &all_blocks,
1011      df_get_postorder (DF_FORWARD), df_get_n_blocks (DF_FORWARD));
1012   /* Initialize avin by pavin.  */
1013   FOR_EACH_BB_FN (bb, cfun)
1014     bitmap_copy (&get_remat_bb_data (bb)->avin_cands,
1015                  &get_remat_bb_data (bb)->pavin_cands);
1016   df_simple_dataflow
1017     (DF_FORWARD, NULL, cand_av_con_fun_0, cand_av_con_fun_n,
1018      cand_av_trans_fun, &all_blocks,
1019      df_get_postorder (DF_FORWARD), df_get_n_blocks (DF_FORWARD));
1020 }
1021
1022 \f
1023
1024 /* Setup sp offset attribute to SP_OFFSET for all INSNS.  */
1025 static void
1026 change_sp_offset (rtx_insn *insns, HOST_WIDE_INT sp_offset)
1027 {
1028   for (rtx_insn *insn = insns; insn != NULL; insn = NEXT_INSN (insn))
1029     eliminate_regs_in_insn (insn, false, false, sp_offset);
1030 }
1031
1032 /* Return start hard register of REG (can be a hard or a pseudo reg)
1033    or -1 (if it is a spilled pseudo).  Return number of hard registers
1034    occupied by REG through parameter NREGS if the start hard reg is
1035    not negative.  */
1036 static int
1037 get_hard_regs (struct lra_insn_reg *reg, int &nregs)
1038 {
1039   int regno = reg->regno;
1040   int hard_regno = regno < FIRST_PSEUDO_REGISTER ? regno : reg_renumber[regno];
1041
1042   if (hard_regno >= 0)
1043     nregs = hard_regno_nregs[hard_regno][reg->biggest_mode];
1044   return hard_regno;
1045 }
1046
1047 /* Make copy of and register scratch pseudos in rematerialized insn
1048    REMAT_INSN.  */
1049 static void
1050 update_scratch_ops (rtx_insn *remat_insn)
1051 {
1052   lra_insn_recog_data_t id = lra_get_insn_recog_data (remat_insn);
1053   struct lra_static_insn_data *static_id = id->insn_static_data;
1054   for (int i = 0; i < static_id->n_operands; i++)
1055     {
1056       rtx *loc = id->operand_loc[i];
1057       if (! REG_P (*loc))
1058         continue;
1059       int regno = REGNO (*loc);
1060       if (! lra_former_scratch_p (regno))
1061         continue;
1062       *loc = lra_create_new_reg (GET_MODE (*loc), *loc,
1063                                  lra_get_allocno_class (regno),
1064                                  "scratch pseudo copy");
1065       lra_register_new_scratch_op (remat_insn, i);
1066     }
1067
1068 }
1069
1070 /* Insert rematerialization insns using the data-flow data calculated
1071    earlier.  */
1072 static bool
1073 do_remat (void)
1074 {
1075   rtx_insn *insn;
1076   basic_block bb;
1077   bitmap_head avail_cands;
1078   bool changed_p = false;
1079   /* Living hard regs and hard registers of living pseudos.  */
1080   HARD_REG_SET live_hard_regs;
1081
1082   bitmap_initialize (&avail_cands, &reg_obstack);
1083   FOR_EACH_BB_FN (bb, cfun)
1084     {
1085       REG_SET_TO_HARD_REG_SET (live_hard_regs, df_get_live_out (bb));
1086       bitmap_and (&avail_cands, &get_remat_bb_data (bb)->avin_cands,
1087                   &get_remat_bb_data (bb)->livein_cands);
1088       FOR_BB_INSNS (bb, insn)
1089         {
1090           if (!NONDEBUG_INSN_P (insn))
1091             continue;
1092
1093           lra_insn_recog_data_t id = lra_get_insn_recog_data (insn);
1094           struct lra_static_insn_data *static_id = id->insn_static_data;
1095           struct lra_insn_reg *reg;
1096           cand_t cand;
1097           unsigned int cid;
1098           bitmap_iterator bi;
1099           rtx set;
1100           int src_regno = -1, dst_regno = -1;
1101
1102           if ((set = single_set (insn)) != NULL
1103               && REG_P (SET_SRC (set)) && REG_P (SET_DEST (set)))
1104             {
1105               src_regno = REGNO (SET_SRC (set));
1106               dst_regno = REGNO (SET_DEST (set));
1107             }
1108
1109           cand = NULL;
1110           /* Check possibility of rematerialization (hard reg or
1111              unpsilled pseudo <- spilled pseudo): */
1112           if (dst_regno >= 0 && src_regno >= FIRST_PSEUDO_REGISTER
1113               && reg_renumber[src_regno] < 0
1114               && (dst_regno < FIRST_PSEUDO_REGISTER
1115                   || reg_renumber[dst_regno] >= 0))
1116             {
1117               for (cand = regno_cands[src_regno];
1118                    cand != NULL;
1119                    cand = cand->next_regno_cand)
1120                 if (bitmap_bit_p (&avail_cands, cand->index))
1121                   break;
1122             }
1123           int i, hard_regno, nregs;
1124           rtx_insn *remat_insn = NULL;
1125           HOST_WIDE_INT cand_sp_offset = 0;
1126           if (cand != NULL)
1127             {
1128               lra_insn_recog_data_t cand_id
1129                 = lra_get_insn_recog_data (cand->insn);
1130               struct lra_static_insn_data *static_cand_id
1131                 = cand_id->insn_static_data;
1132               rtx saved_op = *cand_id->operand_loc[cand->nop];
1133
1134               /* Check clobbers do not kill something living.  */
1135               gcc_assert (REG_P (saved_op));
1136               int ignore_regno = REGNO (saved_op);
1137
1138               for (reg = cand_id->regs; reg != NULL; reg = reg->next)
1139                 if (reg->type != OP_IN && reg->regno != ignore_regno)
1140                   {
1141                     hard_regno = get_hard_regs (reg, nregs);
1142                     gcc_assert (hard_regno >= 0);
1143                     for (i = 0; i < nregs; i++)
1144                       if (TEST_HARD_REG_BIT (live_hard_regs, hard_regno + i))
1145                         break;
1146                     if (i < nregs)
1147                       break;
1148                   }
1149
1150               if (reg == NULL)
1151                 {
1152                   for (reg = static_cand_id->hard_regs;
1153                        reg != NULL;
1154                        reg = reg->next)
1155                     if (reg->type != OP_IN
1156                         && TEST_HARD_REG_BIT (live_hard_regs, reg->regno))
1157                       break;
1158                 }
1159
1160               if (reg == NULL)
1161                 {
1162                   *cand_id->operand_loc[cand->nop] = SET_DEST (set);
1163                   lra_update_insn_regno_info (cand->insn);
1164                   bool ok_p = lra_constrain_insn (cand->insn);
1165                   if (ok_p)
1166                     {
1167                       rtx remat_pat = copy_insn (PATTERN (cand->insn));
1168
1169                       start_sequence ();
1170                       emit_insn (remat_pat);
1171                       remat_insn = get_insns ();
1172                       end_sequence ();
1173                       if (recog_memoized (remat_insn) < 0)
1174                         remat_insn = NULL;
1175                       cand_sp_offset = cand_id->sp_offset;
1176                     }
1177                   *cand_id->operand_loc[cand->nop] = saved_op;
1178                   lra_update_insn_regno_info (cand->insn);
1179                 }
1180             }
1181
1182           bitmap_clear (&temp_bitmap);
1183           /* Update avail_cands (see analogous code for
1184              calculate_gen_cands).  */
1185           for (reg = id->regs; reg != NULL; reg = reg->next)
1186             if (reg->type != OP_IN
1187                 || find_regno_note (insn, REG_DEAD, reg->regno) != NULL)
1188               EXECUTE_IF_SET_IN_BITMAP (&avail_cands, 0, cid, bi)
1189                 {
1190                   cand = all_cands[cid];
1191
1192                   /* Ignore the reload insn.  */
1193                   if (src_regno == cand->reload_regno
1194                       && dst_regno == cand->regno)
1195                     continue;
1196                   if (cand->regno == reg->regno
1197                       || input_regno_present_p (cand->insn, reg->regno))
1198                     bitmap_set_bit (&temp_bitmap, cand->index);
1199                 }
1200
1201           if (CALL_P (insn))
1202             EXECUTE_IF_SET_IN_BITMAP (&avail_cands, 0, cid, bi)
1203               {
1204                 cand = all_cands[cid];
1205
1206                 if (call_used_input_regno_present_p (cand->insn))
1207                   bitmap_set_bit (&temp_bitmap, cand->index);
1208               }
1209
1210           bitmap_and_compl_into (&avail_cands, &temp_bitmap);
1211           if ((cand = insn_to_cand[INSN_UID (insn)]) != NULL)
1212             bitmap_set_bit (&avail_cands, cand->index);
1213
1214           if (remat_insn != NULL)
1215             {
1216               HOST_WIDE_INT sp_offset_change = cand_sp_offset - id->sp_offset;
1217               if (sp_offset_change != 0)
1218                 change_sp_offset (remat_insn, sp_offset_change);
1219               update_scratch_ops (remat_insn);
1220               lra_process_new_insns (insn, remat_insn, NULL,
1221                                      "Inserting rematerialization insn");
1222               lra_set_insn_deleted (insn);
1223               changed_p = true;
1224               continue;
1225             }
1226
1227           /* Update live hard regs: */
1228           for (reg = id->regs; reg != NULL; reg = reg->next)
1229             if (reg->type == OP_IN
1230                 && find_regno_note (insn, REG_DEAD, reg->regno) != NULL)
1231               {
1232                 if ((hard_regno = get_hard_regs (reg, nregs)) < 0)
1233                   continue;
1234                 for (i = 0; i < nregs; i++)
1235                   CLEAR_HARD_REG_BIT (live_hard_regs, hard_regno + i);
1236               }
1237             else if (reg->type != OP_IN
1238                      && find_regno_note (insn, REG_UNUSED, reg->regno) == NULL)
1239               {
1240                 if ((hard_regno = get_hard_regs (reg, nregs)) < 0)
1241                   continue;
1242                 for (i = 0; i < nregs; i++)
1243                   SET_HARD_REG_BIT (live_hard_regs, hard_regno + i);
1244               }
1245           /* Process also hard regs (e.g. CC register) which are part
1246              of insn definition.  */
1247           for (reg = static_id->hard_regs; reg != NULL; reg = reg->next)
1248             if (reg->type == OP_IN
1249                 && find_regno_note (insn, REG_DEAD, reg->regno) != NULL)
1250               CLEAR_HARD_REG_BIT (live_hard_regs, reg->regno);
1251             else if (reg->type != OP_IN
1252                      && find_regno_note (insn, REG_UNUSED, reg->regno) == NULL)
1253               SET_HARD_REG_BIT (live_hard_regs, reg->regno);
1254         }
1255     }
1256   bitmap_clear (&avail_cands);
1257   return changed_p;
1258 }
1259
1260 \f
1261
1262 /* Entry point of the rematerialization sub-pass.  Return true if we
1263    did any rematerialization.  */
1264 bool
1265 lra_remat (void)
1266 {
1267   basic_block bb;
1268   bool result;
1269   int max_regno = max_reg_num ();
1270
1271   if (! flag_lra_remat)
1272     return false;
1273   timevar_push (TV_LRA_REMAT);
1274   insn_to_cand = XCNEWVEC (cand_t, get_max_uid ());
1275   regno_cands = XCNEWVEC (cand_t, max_regno);
1276   all_cands.create (8000);
1277   call_used_regs_arr_len = 0;
1278   for (int i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1279     if (call_used_regs[i])
1280       call_used_regs_arr[call_used_regs_arr_len++] = i;
1281   initiate_cand_table ();
1282   create_cands ();
1283   create_remat_bb_data ();
1284   bitmap_initialize (&temp_bitmap, &reg_obstack);
1285   calculate_local_reg_remat_bb_data ();
1286   calculate_livein_cands ();
1287   calculate_gen_cands ();
1288   bitmap_initialize (&all_blocks, &reg_obstack);
1289   FOR_ALL_BB_FN (bb, cfun)
1290     bitmap_set_bit (&all_blocks, bb->index);
1291   calculate_global_remat_bb_data ();
1292   dump_candidates_and_remat_bb_data ();
1293   result = do_remat ();
1294   all_cands.release ();
1295   bitmap_clear (&temp_bitmap);
1296   finish_remat_bb_data ();
1297   finish_cand_table ();
1298   bitmap_clear (&all_blocks);
1299   free (regno_cands);
1300   free (insn_to_cand);
1301   timevar_pop (TV_LRA_REMAT);
1302   return result;
1303 }