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       }
 463   /* Find the rematerialization operand.  */
 464   int nop = static_id->n_operands;
 465   for (int i = 0; i < nop; i++)
 466     if (REG_P (*id->operand_loc[i])
 467         && (int) REGNO (*id->operand_loc[i]) == found_reg->regno)
 468       return i;
 469   return -1;
 470 }
 471
 472 /* Create candidate for INSN with rematerialization operand NOP and
 473    REGNO.  Insert the candidate into the table and set up the
 474    corresponding INSN_TO_CAND element.  */
 475 static void
 476 create_cand (rtx_insn *insn, int nop, int regno)
 477 {
 478   lra_insn_recog_data_t id = lra_get_insn_recog_data (insn);
 479   rtx reg = *id->operand_loc[nop];
 480   gcc_assert (REG_P (reg));
 481   int op_regno = REGNO (reg);
 482   gcc_assert (op_regno >= FIRST_PSEUDO_REGISTER);
 483   cand_t cand = XNEW (struct cand);
 484   cand->insn = insn;
 485   cand->nop = nop;
 486   cand->regno = regno;
 487   cand->reload_regno = op_regno == regno ? -1 : op_regno;
 488   gcc_assert (cand->regno >= 0);
 489   cand_t cand_in_table = insert_cand (cand);
 490   insn_to_cand[INSN_UID (insn)] = cand_in_table;
 491   if (cand != cand_in_table)
 492     free (cand);
 493   else
 494     {
 495       /* A new cand.  */
 496       cand->index = all_cands.length ();
 497       all_cands.safe_push (cand);
 498       cand->next_regno_cand = regno_cands[cand->regno];
 499       regno_cands[cand->regno] = cand;
 500     }
 501 }
 502
 503 /* Create rematerialization candidates (inserting them into the
 504    table).  */
 505 static void
 506 create_cands (void)
 507 {
 508   rtx_insn *insn;
 509   struct potential_cand
 510   {
 511     rtx_insn *insn;
 512     int nop;
 513   };
 514   struct potential_cand *regno_potential_cand;
 515
 516   /* Create candidates.  */
 517   regno_potential_cand = XCNEWVEC (struct potential_cand, max_reg_num ());
 518   for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
 519     if (INSN_P (insn))
 520       {
 521         rtx set;
 522         int src_regno, dst_regno;
 523         rtx_insn *insn2;
 524         lra_insn_recog_data_t id = lra_get_insn_recog_data (insn);
 525         int nop = operand_to_remat (insn);
 526         int regno = -1;
 527
 528         if ((set = single_set (insn)) != NULL
 529             && REG_P (SET_SRC (set)) && REG_P (SET_DEST (set))
 530             && ((src_regno = REGNO (SET_SRC (set)))
 531                 >= lra_constraint_new_regno_start)
 532             && (dst_regno = REGNO (SET_DEST (set))) >= FIRST_PSEUDO_REGISTER
 533             && reg_renumber[dst_regno] < 0
 534             && (insn2 = regno_potential_cand[src_regno].insn) != NULL
 535             && BLOCK_FOR_INSN (insn2) == BLOCK_FOR_INSN (insn))
 536           /* It is an output reload insn after insn can be
 537              rematerialized (potential candidate).  */
 538           create_cand (insn2, regno_potential_cand[src_regno].nop, dst_regno);
 539         if (nop < 0)
 540           goto fail;
 541         gcc_assert (REG_P (*id->operand_loc[nop]));
 542         regno = REGNO (*id->operand_loc[nop]);
 543         gcc_assert (regno >= FIRST_PSEUDO_REGISTER);
 544         if (reg_renumber[regno] < 0)
 545           create_cand (insn, nop, regno);
 546         else
 547           {
 548             regno_potential_cand[regno].insn = insn;
 549             regno_potential_cand[regno].nop = nop;
 550             goto fail;
 551           }
 552         regno = -1;
 553       fail:
 554         for (struct lra_insn_reg *reg = id->regs; reg != NULL; reg = reg->next)
 555           if (reg->type != OP_IN && reg->regno != regno
 556               && reg->regno >= FIRST_PSEUDO_REGISTER)
 557             regno_potential_cand[reg->regno].insn = NULL;
 558       }
 559   cands_num = all_cands.length ();
 560   free (regno_potential_cand);
 561 }
 562
 563 \f
 564
 565 /* Create and initialize BB data.  */
 566 static void
 567 create_remat_bb_data (void)
 568 {
 569   basic_block bb;
 570   remat_bb_data_t bb_info;
 571
 572   remat_bb_data = XNEWVEC (struct remat_bb_data,
 573                            last_basic_block_for_fn (cfun));
 574   FOR_ALL_BB_FN (bb, cfun)
 575     {
 576 #ifdef ENABLE_CHECKING
 577       if (bb->index < 0 || bb->index >= last_basic_block_for_fn (cfun))
 578         abort ();
 579 #endif
 580       bb_info = get_remat_bb_data (bb);
 581       bb_info->bb = bb;
 582       bitmap_initialize (&bb_info->changed_regs, &reg_obstack);
 583       bitmap_initialize (&bb_info->dead_regs, &reg_obstack);
 584       bitmap_initialize (&bb_info->gen_cands, &reg_obstack);
 585       bitmap_initialize (&bb_info->livein_cands, &reg_obstack);
 586       bitmap_initialize (&bb_info->pavin_cands, &reg_obstack);
 587       bitmap_initialize (&bb_info->pavout_cands, &reg_obstack);
 588       bitmap_initialize (&bb_info->avin_cands, &reg_obstack);
 589       bitmap_initialize (&bb_info->avout_cands, &reg_obstack);
 590     }
 591 }
 592
 593 /* Dump all candidates to DUMP_FILE.  */
 594 static void
 595 dump_cands (FILE *dump_file)
 596 {
 597   int i;
 598   cand_t cand;
 599
 600   fprintf (dump_file, "\nCands:\n");
 601   for (i = 0; i < (int) cands_num; i++)
 602     {
 603       cand = all_cands[i];
 604       fprintf (dump_file, "%d (nop=%d, remat_regno=%d, reload_regno=%d):\n",
 605                i, cand->nop, cand->regno, cand->reload_regno);
 606       print_inline_rtx (dump_file, cand->insn, 6);
 607       fprintf (dump_file, "\n");
 608     }
 609 }
 610
 611 /* Dump all candidates and BB data.  */
 612 static void
 613 dump_candidates_and_remat_bb_data (void)
 614 {
 615   basic_block bb;
 616
 617   if (lra_dump_file == NULL)
 618     return;
 619   dump_cands (lra_dump_file);
 620   FOR_EACH_BB_FN (bb, cfun)
 621     {
 622       fprintf (lra_dump_file, "\nBB %d:\n", bb->index);
 623       /* Livein */
 624       fprintf (lra_dump_file, "  register live in:");
 625       dump_regset (df_get_live_in (bb), lra_dump_file);
 626       putc ('\n', lra_dump_file);
 627       /* Liveout */
 628       fprintf (lra_dump_file, "  register live out:");
 629       dump_regset (df_get_live_out (bb), lra_dump_file);
 630       putc ('\n', lra_dump_file);
 631       /* Changed/dead regs: */
 632       fprintf (lra_dump_file, "  changed regs:");
 633       dump_regset (&get_remat_bb_data (bb)->changed_regs, lra_dump_file);
 634       putc ('\n', lra_dump_file);
 635       fprintf (lra_dump_file, "  dead regs:");
 636       dump_regset (&get_remat_bb_data (bb)->dead_regs, lra_dump_file);
 637       putc ('\n', lra_dump_file);
 638       lra_dump_bitmap_with_title ("cands generated in BB",
 639                                   &get_remat_bb_data (bb)->gen_cands, bb->index);
 640       lra_dump_bitmap_with_title ("livein cands in BB",
 641                                   &get_remat_bb_data (bb)->livein_cands, bb->index);
 642       lra_dump_bitmap_with_title ("pavin cands in BB",
 643                                   &get_remat_bb_data (bb)->pavin_cands, bb->index);
 644       lra_dump_bitmap_with_title ("pavout cands in BB",
 645                                   &get_remat_bb_data (bb)->pavout_cands, bb->index);
 646       lra_dump_bitmap_with_title ("avin cands in BB",
 647                                   &get_remat_bb_data (bb)->avin_cands, bb->index);
 648       lra_dump_bitmap_with_title ("avout cands in BB",
 649                                   &get_remat_bb_data (bb)->avout_cands, bb->index);
 650     }
 651 }
 652
 653 /* Free all BB data.  */
 654 static void
 655 finish_remat_bb_data (void)
 656 {
 657   basic_block bb;
 658
 659   FOR_EACH_BB_FN (bb, cfun)
 660     {
 661       bitmap_clear (&get_remat_bb_data (bb)->avout_cands);
 662       bitmap_clear (&get_remat_bb_data (bb)->avin_cands);
 663       bitmap_clear (&get_remat_bb_data (bb)->pavout_cands);
 664       bitmap_clear (&get_remat_bb_data (bb)->pavin_cands);
 665       bitmap_clear (&get_remat_bb_data (bb)->livein_cands);
 666       bitmap_clear (&get_remat_bb_data (bb)->gen_cands);
 667       bitmap_clear (&get_remat_bb_data (bb)->dead_regs);
 668       bitmap_clear (&get_remat_bb_data (bb)->changed_regs);
 669     }
 670   free (remat_bb_data);
 671 }
 672
 673 \f
 674
 675 /* Update changed_regs and dead_regs of BB from INSN.  */
 676 static void
 677 set_bb_regs (basic_block bb, rtx_insn *insn)
 678 {
 679   lra_insn_recog_data_t id = lra_get_insn_recog_data (insn);
 680   struct lra_insn_reg *reg;
 681
 682   for (reg = id->regs; reg != NULL; reg = reg->next)
 683     if (reg->type != OP_IN)
 684       bitmap_set_bit (&get_remat_bb_data (bb)->changed_regs, reg->regno);
 685     else
 686       {
 687         if (find_regno_note (insn, REG_DEAD, (unsigned) reg->regno) != NULL)
 688           bitmap_set_bit (&get_remat_bb_data (bb)->dead_regs, reg->regno);
 689       }
 690   if (CALL_P (insn))
 691     for (int i = 0; i < call_used_regs_arr_len; i++)
 692       bitmap_set_bit (&get_remat_bb_data (bb)->dead_regs,
 693                       call_used_regs_arr[i]);
 694 }
 695
 696 /* Calculate changed_regs and dead_regs for each BB.  */
 697 static void
 698 calculate_local_reg_remat_bb_data (void)
 699 {
 700   basic_block bb;
 701   rtx_insn *insn;
 702
 703   FOR_EACH_BB_FN (bb, cfun)
 704     FOR_BB_INSNS (bb, insn)
 705       if (INSN_P (insn))
 706         set_bb_regs (bb, insn);
 707 }
 708
 709 \f
 710
 711 /* Return true if REGNO is an input operand of INSN.  */
 712 static bool
 713 input_regno_present_p (rtx_insn *insn, int regno)
 714 {
 715   lra_insn_recog_data_t id = lra_get_insn_recog_data (insn);
 716   struct lra_insn_reg *reg;
 717
 718   for (reg = id->regs; reg != NULL; reg = reg->next)
 719     if (reg->type == OP_IN && reg->regno == regno)
 720       return true;
 721   return false;
 722 }
 723
 724 /* Return true if a call used register is an input operand of INSN.  */
 725 static bool
 726 call_used_input_regno_present_p (rtx_insn *insn)
 727 {
 728   lra_insn_recog_data_t id = lra_get_insn_recog_data (insn);
 729   struct lra_insn_reg *reg;
 730
 731   for (reg = id->regs; reg != NULL; reg = reg->next)
 732     if (reg->type == OP_IN && reg->regno <= FIRST_PSEUDO_REGISTER
 733         && TEST_HARD_REG_BIT (call_used_reg_set, reg->regno))
 734       return true;
 735   return false;
 736 }
 737
 738 /* Calculate livein_cands for each BB.  */
 739 static void
 740 calculate_livein_cands (void)
 741 {
 742   basic_block bb;
 743
 744   FOR_EACH_BB_FN (bb, cfun)
 745     {
 746       bitmap livein_regs = df_get_live_in (bb);
 747       bitmap livein_cands = &get_remat_bb_data (bb)->livein_cands;
 748       for (unsigned int i = 0; i < cands_num; i++)
 749         {
 750           cand_t cand = all_cands[i];
 751           lra_insn_recog_data_t id = lra_get_insn_recog_data (cand->insn);
 752           struct lra_insn_reg *reg;
 753
 754           for (reg = id->regs; reg != NULL; reg = reg->next)
 755             if (reg->type == OP_IN && ! bitmap_bit_p (livein_regs, reg->regno))
 756               break;
 757           if (reg == NULL)
 758             bitmap_set_bit (livein_cands, i);
 759         }
 760     }
 761 }
 762
 763 /* Calculate gen_cands for each BB.  */
 764 static void
 765 calculate_gen_cands (void)
 766 {
 767   basic_block bb;
 768   bitmap gen_cands;
 769   bitmap_head gen_insns;
 770   rtx_insn *insn;
 771
 772   bitmap_initialize (&gen_insns, &reg_obstack);
 773   FOR_EACH_BB_FN (bb, cfun)
 774     {
 775       gen_cands = &get_remat_bb_data (bb)->gen_cands;
 776       bitmap_clear (&gen_insns);
 777       FOR_BB_INSNS (bb, insn)
 778         if (INSN_P (insn))
 779           {
 780             lra_insn_recog_data_t id = lra_get_insn_recog_data (insn);
 781             struct lra_insn_reg *reg;
 782             unsigned int uid;
 783             bitmap_iterator bi;
 784             cand_t cand;
 785             rtx set;
 786             int src_regno = -1, dst_regno = -1;
 787
 788             if ((set = single_set (insn)) != NULL
 789                 && REG_P (SET_SRC (set)) && REG_P (SET_DEST (set)))
 790               {
 791                 src_regno = REGNO (SET_SRC (set));
 792                 dst_regno = REGNO (SET_DEST (set));
 793               }
 794
 795             /* Update gen_cands:  */
 796             bitmap_clear (&temp_bitmap);
 797             for (reg = id->regs; reg != NULL; reg = reg->next)
 798               if (reg->type != OP_IN
 799                   || find_regno_note (insn, REG_DEAD, reg->regno) != NULL)
 800                 EXECUTE_IF_SET_IN_BITMAP (&gen_insns, 0, uid, bi)
 801                   {
 802                     rtx_insn *insn2 = lra_insn_recog_data[uid]->insn;
 803
 804                     cand = insn_to_cand[INSN_UID (insn2)];
 805                     gcc_assert (cand != NULL);
 806                     /* Ignore the reload insn.  */
 807                     if (src_regno == cand->reload_regno
 808                         && dst_regno == cand->regno)
 809                       continue;
 810                     if (cand->regno == reg->regno
 811                         || input_regno_present_p (insn2, reg->regno))
 812                       {
 813                         bitmap_clear_bit (gen_cands, cand->index);
 814                         bitmap_set_bit (&temp_bitmap, uid);
 815                       }
 816                   }
 817
 818             if (CALL_P (insn))
 819               EXECUTE_IF_SET_IN_BITMAP (&gen_insns, 0, uid, bi)
 820                 {
 821                   rtx_insn *insn2 = lra_insn_recog_data[uid]->insn;
 822
 823                   cand = insn_to_cand[INSN_UID (insn2)];
 824                   gcc_assert (cand != NULL);
 825                   if (call_used_input_regno_present_p (insn2))
 826                     {
 827                       bitmap_clear_bit (gen_cands, cand->index);
 828                       bitmap_set_bit (&temp_bitmap, uid);
 829                     }
 830                 }
 831             bitmap_and_compl_into (&gen_insns, &temp_bitmap);
 832
 833             cand = insn_to_cand[INSN_UID (insn)];
 834             if (cand != NULL)
 835               {
 836                 bitmap_set_bit (gen_cands, cand->index);
 837                 bitmap_set_bit (&gen_insns, INSN_UID (insn));
 838               }
 839           }
 840     }
 841   bitmap_clear (&gen_insns);
 842 }
 843
 844 \f
 845
 846 /* The common transfer function used by the DF equation solver to
 847    propagate (partial) availability info BB_IN to BB_OUT through block
 848    with BB_INDEX according to the following equation:
 849
 850       bb.out =  ((bb.in & bb.livein) - bb.killed) OR  bb.gen
 851 */
 852 static bool
 853 cand_trans_fun (int bb_index, bitmap bb_in, bitmap bb_out)
 854 {
 855   remat_bb_data_t bb_info;
 856   bitmap bb_livein, bb_changed_regs, bb_dead_regs;
 857   unsigned int cid;
 858   bitmap_iterator bi;
 859
 860   bb_info = get_remat_bb_data_by_index (bb_index);
 861   bb_livein = &bb_info->livein_cands;
 862   bb_changed_regs = &bb_info->changed_regs;
 863   bb_dead_regs = &bb_info->dead_regs;
 864   /* Calculate killed avin cands -- cands whose regs are changed or
 865      becoming dead in the BB.  We calculate it here as we hope that
 866      repeated calculations are compensated by smaller size of BB_IN in
 867      comparison with all candidates number.  */
 868   bitmap_clear (&temp_bitmap);
 869   EXECUTE_IF_SET_IN_BITMAP (bb_in, 0, cid, bi)
 870     {
 871       cand_t cand = all_cands[cid];
 872       lra_insn_recog_data_t id = lra_get_insn_recog_data (cand->insn);
 873       struct lra_insn_reg *reg;
 874
 875       if (! bitmap_bit_p (bb_livein, cid))
 876         {
 877           bitmap_set_bit (&temp_bitmap, cid);
 878           continue;
 879         }
 880       for (reg = id->regs; reg != NULL; reg = reg->next)
 881         /* Ignore all outputs which are not the regno for
 882            rematerialization.  */
 883         if (reg->type == OP_OUT && reg->regno != cand->regno)
 884           continue;
 885         else if (bitmap_bit_p (bb_changed_regs, reg->regno)
 886                  || bitmap_bit_p (bb_dead_regs, reg->regno))
 887           {
 888             bitmap_set_bit (&temp_bitmap, cid);
 889             break;
 890           }
 891       /* Check regno for rematerialization.  */
 892       if (bitmap_bit_p (bb_changed_regs, cand->regno)
 893           || bitmap_bit_p (bb_dead_regs, cand->regno))
 894         bitmap_set_bit (&temp_bitmap, cid);
 895     }
 896   return bitmap_ior_and_compl (bb_out,
 897                                &bb_info->gen_cands, bb_in, &temp_bitmap);
 898 }
 899
 900 \f
 901
 902 /* The transfer function used by the DF equation solver to propagate
 903    partial candidate availability info through block with BB_INDEX
 904    according to the following equation:
 905
 906      bb.pavout = ((bb.pavin & bb.livein) - bb.killed) OR bb.gen
 907 */
 908 static bool
 909 cand_pav_trans_fun (int bb_index)
 910 {
 911   remat_bb_data_t bb_info;
 912
 913   bb_info = get_remat_bb_data_by_index (bb_index);
 914   return cand_trans_fun (bb_index, &bb_info->pavin_cands,
 915                          &bb_info->pavout_cands);
 916 }
 917
 918 /* The confluence function used by the DF equation solver to set up
 919    cand_pav info for a block BB without predecessor.  */
 920 static void
 921 cand_pav_con_fun_0 (basic_block bb)
 922 {
 923   bitmap_clear (&get_remat_bb_data (bb)->pavin_cands);
 924 }
 925
 926 /* The confluence function used by the DF equation solver to propagate
 927    partial candidate availability info from predecessor to successor
 928    on edge E (pred->bb) according to the following equation:
 929
 930       bb.pavin_cands = 0 for entry block | OR (pavout_cands of predecessors)
 931  */
 932 static bool
 933 cand_pav_con_fun_n (edge e)
 934 {
 935   basic_block pred = e->src;
 936   basic_block bb = e->dest;
 937   remat_bb_data_t bb_info;
 938   bitmap bb_pavin, pred_pavout;
 939
 940   bb_info = get_remat_bb_data (bb);
 941   bb_pavin = &bb_info->pavin_cands;
 942   pred_pavout = &get_remat_bb_data (pred)->pavout_cands;
 943   return bitmap_ior_into (bb_pavin, pred_pavout);
 944 }
 945
 946 \f
 947
 948 /* The transfer function used by the DF equation solver to propagate
 949    candidate availability info through block with BB_INDEX according
 950    to the following equation:
 951
 952       bb.avout =  ((bb.avin & bb.livein) - bb.killed) OR  bb.gen
 953 */
 954 static bool
 955 cand_av_trans_fun (int bb_index)
 956 {
 957   remat_bb_data_t bb_info;
 958
 959   bb_info = get_remat_bb_data_by_index (bb_index);
 960   return cand_trans_fun (bb_index, &bb_info->avin_cands,
 961                          &bb_info->avout_cands);
 962 }
 963
 964 /* The confluence function used by the DF equation solver to set up
 965    cand_av info for a block BB without predecessor.  */
 966 static void
 967 cand_av_con_fun_0 (basic_block bb)
 968 {
 969   bitmap_clear (&get_remat_bb_data (bb)->avin_cands);
 970 }
 971
 972 /* The confluence function used by the DF equation solver to propagate
 973    cand_av info from predecessor to successor on edge E (pred->bb)
 974    according to the following equation:
 975
 976       bb.avin_cands = 0 for entry block | AND (avout_cands of predecessors)
 977  */
 978 static bool
 979 cand_av_con_fun_n (edge e)
 980 {
 981   basic_block pred = e->src;
 982   basic_block bb = e->dest;
 983   remat_bb_data_t bb_info;
 984   bitmap bb_avin, pred_avout;
 985
 986   bb_info = get_remat_bb_data (bb);
 987   bb_avin = &bb_info->avin_cands;
 988   pred_avout = &get_remat_bb_data (pred)->avout_cands;
 989   return bitmap_and_into (bb_avin, pred_avout);
 990 }
 991
 992 /* Calculate available candidates for each BB.  */
 993 static void
 994 calculate_global_remat_bb_data (void)
 995 {
 996   basic_block bb;
 997
 998   df_simple_dataflow
 999     (DF_FORWARD, NULL, cand_pav_con_fun_0, cand_pav_con_fun_n,
1000      cand_pav_trans_fun, &all_blocks,
1001      df_get_postorder (DF_FORWARD), df_get_n_blocks (DF_FORWARD));
1002   /* Initialize avin by pavin.  */
1003   FOR_EACH_BB_FN (bb, cfun)
1004     bitmap_copy (&get_remat_bb_data (bb)->avin_cands,
1005                  &get_remat_bb_data (bb)->pavin_cands);
1006   df_simple_dataflow
1007     (DF_FORWARD, NULL, cand_av_con_fun_0, cand_av_con_fun_n,
1008      cand_av_trans_fun, &all_blocks,
1009      df_get_postorder (DF_FORWARD), df_get_n_blocks (DF_FORWARD));
1010 }
1011
1012 \f
1013
1014 /* Setup sp offset attribute to SP_OFFSET for all INSNS.  */
1015 static void
1016 change_sp_offset (rtx_insn *insns, HOST_WIDE_INT sp_offset)
1017 {
1018   for (rtx_insn *insn = insns; insn != NULL; insn = NEXT_INSN (insn))
1019     eliminate_regs_in_insn (insn, false, false, sp_offset);
1020 }
1021
1022 /* Return start hard register of REG (can be a hard or a pseudo reg)
1023    or -1 (if it is a spilled pseudo).  Return number of hard registers
1024    occupied by REG through parameter NREGS if the start hard reg is
1025    not negative.  */
1026 static int
1027 get_hard_regs (struct lra_insn_reg *reg, int &nregs)
1028 {
1029   int regno = reg->regno;
1030   int hard_regno = regno < FIRST_PSEUDO_REGISTER ? regno : reg_renumber[regno];
1031
1032   if (hard_regno >= 0)
1033     nregs = hard_regno_nregs[hard_regno][reg->biggest_mode];
1034   return hard_regno;
1035 }
1036
1037 /* Insert rematerialization insns using the data-flow data calculated
1038    earlier.  */
1039 static bool
1040 do_remat (void)
1041 {
1042   rtx_insn *insn;
1043   basic_block bb;
1044   bitmap_head avail_cands;
1045   bool changed_p = false;
1046   /* Living hard regs and hard registers of living pseudos.  */
1047   HARD_REG_SET live_hard_regs;
1048
1049   bitmap_initialize (&avail_cands, &reg_obstack);
1050   FOR_EACH_BB_FN (bb, cfun)
1051     {
1052       REG_SET_TO_HARD_REG_SET (live_hard_regs, df_get_live_out (bb));
1053       bitmap_and (&avail_cands, &get_remat_bb_data (bb)->avin_cands,
1054                   &get_remat_bb_data (bb)->livein_cands);
1055       FOR_BB_INSNS (bb, insn)
1056         {
1057           if (!NONDEBUG_INSN_P (insn))
1058             continue;
1059
1060           lra_insn_recog_data_t id = lra_get_insn_recog_data (insn);
1061           struct lra_static_insn_data *static_id = id->insn_static_data;
1062           struct lra_insn_reg *reg;
1063           cand_t cand;
1064           unsigned int cid;
1065           bitmap_iterator bi;
1066           rtx set;
1067           int src_regno = -1, dst_regno = -1;
1068
1069           if ((set = single_set (insn)) != NULL
1070               && REG_P (SET_SRC (set)) && REG_P (SET_DEST (set)))
1071             {
1072               src_regno = REGNO (SET_SRC (set));
1073               dst_regno = REGNO (SET_DEST (set));
1074             }
1075
1076           cand = NULL;
1077           /* Check possibility of rematerialization (hard reg or
1078              unpsilled pseudo <- spilled pseudo): */
1079           if (dst_regno >= 0 && src_regno >= FIRST_PSEUDO_REGISTER
1080               && reg_renumber[src_regno] < 0
1081               && (dst_regno < FIRST_PSEUDO_REGISTER
1082                   || reg_renumber[dst_regno] >= 0))
1083             {
1084               for (cand = regno_cands[src_regno];
1085                    cand != NULL;
1086                    cand = cand->next_regno_cand)
1087                 if (bitmap_bit_p (&avail_cands, cand->index))
1088                   break;
1089             }
1090           int i, hard_regno, nregs;
1091           rtx_insn *remat_insn = NULL;
1092           HOST_WIDE_INT cand_sp_offset = 0;
1093           if (cand != NULL)
1094             {
1095               lra_insn_recog_data_t cand_id
1096                 = lra_get_insn_recog_data (cand->insn);
1097               struct lra_static_insn_data *static_cand_id
1098                 = cand_id->insn_static_data;
1099               rtx saved_op = *cand_id->operand_loc[cand->nop];
1100
1101               /* Check clobbers do not kill something living.  */
1102               gcc_assert (REG_P (saved_op));
1103               int ignore_regno = REGNO (saved_op);
1104
1105               for (reg = cand_id->regs; reg != NULL; reg = reg->next)
1106                 if (reg->type != OP_IN && reg->regno != ignore_regno)
1107                   {
1108                     hard_regno = get_hard_regs (reg, nregs);
1109                     gcc_assert (hard_regno >= 0);
1110                     for (i = 0; i < nregs; i++)
1111                       if (TEST_HARD_REG_BIT (live_hard_regs, hard_regno + i))
1112                         break;
1113                     if (i < nregs)
1114                       break;
1115                   }
1116
1117               if (reg == NULL)
1118                 {
1119                   for (reg = static_cand_id->hard_regs;
1120                        reg != NULL;
1121                        reg = reg->next)
1122                     if (reg->type != OP_IN
1123                         && TEST_HARD_REG_BIT (live_hard_regs, reg->regno))
1124                       break;
1125                 }
1126
1127               if (reg == NULL)
1128                 {
1129                   *cand_id->operand_loc[cand->nop] = SET_DEST (set);
1130                   lra_update_insn_regno_info (cand->insn);
1131                   bool ok_p = lra_constrain_insn (cand->insn);
1132                   if (ok_p)
1133                     {
1134                       rtx remat_pat = copy_insn (PATTERN (cand->insn));
1135
1136                       start_sequence ();
1137                       emit_insn (remat_pat);
1138                       remat_insn = get_insns ();
1139                       end_sequence ();
1140                       if (recog_memoized (remat_insn) < 0)
1141                         remat_insn = NULL;
1142                       cand_sp_offset = cand_id->sp_offset;
1143                     }
1144                   *cand_id->operand_loc[cand->nop] = saved_op;
1145                   lra_update_insn_regno_info (cand->insn);
1146                 }
1147             }
1148
1149           bitmap_clear (&temp_bitmap);
1150           /* Update avail_cands (see analogous code for
1151              calculate_gen_cands).  */
1152           for (reg = id->regs; reg != NULL; reg = reg->next)
1153             if (reg->type != OP_IN
1154                 || find_regno_note (insn, REG_DEAD, reg->regno) != NULL)
1155               EXECUTE_IF_SET_IN_BITMAP (&avail_cands, 0, cid, bi)
1156                 {
1157                   cand = all_cands[cid];
1158
1159                   /* Ignore the reload insn.  */
1160                   if (src_regno == cand->reload_regno
1161                       && dst_regno == cand->regno)
1162                     continue;
1163                   if (cand->regno == reg->regno
1164                       || input_regno_present_p (cand->insn, reg->regno))
1165                     bitmap_set_bit (&temp_bitmap, cand->index);
1166                 }
1167
1168           if (CALL_P (insn))
1169             EXECUTE_IF_SET_IN_BITMAP (&avail_cands, 0, cid, bi)
1170               {
1171                 cand = all_cands[cid];
1172
1173                 if (call_used_input_regno_present_p (cand->insn))
1174                   bitmap_set_bit (&temp_bitmap, cand->index);
1175               }
1176
1177           bitmap_and_compl_into (&avail_cands, &temp_bitmap);
1178           if ((cand = insn_to_cand[INSN_UID (insn)]) != NULL)
1179             bitmap_set_bit (&avail_cands, cand->index);
1180
1181           if (remat_insn != NULL)
1182             {
1183               HOST_WIDE_INT sp_offset_change = cand_sp_offset - id->sp_offset;
1184               if (sp_offset_change != 0)
1185                 change_sp_offset (remat_insn, sp_offset_change);
1186               lra_process_new_insns (insn, remat_insn, NULL,
1187                                      "Inserting rematerialization insn");
1188               lra_set_insn_deleted (insn);
1189               changed_p = true;
1190               continue;
1191             }
1192
1193           /* Update live hard regs: */
1194           for (reg = id->regs; reg != NULL; reg = reg->next)
1195             if (reg->type == OP_IN
1196                 && find_regno_note (insn, REG_DEAD, reg->regno) != NULL)
1197               {
1198                 if ((hard_regno = get_hard_regs (reg, nregs)) < 0)
1199                   continue;
1200                 for (i = 0; i < nregs; i++)
1201                   CLEAR_HARD_REG_BIT (live_hard_regs, hard_regno + i);
1202               }
1203             else if (reg->type != OP_IN
1204                      && find_regno_note (insn, REG_UNUSED, reg->regno) == NULL)
1205               {
1206                 if ((hard_regno = get_hard_regs (reg, nregs)) < 0)
1207                   continue;
1208                 for (i = 0; i < nregs; i++)
1209                   SET_HARD_REG_BIT (live_hard_regs, hard_regno + i);
1210               }
1211           /* Process also hard regs (e.g. CC register) which are part
1212              of insn definition.  */
1213           for (reg = static_id->hard_regs; reg != NULL; reg = reg->next)
1214             if (reg->type == OP_IN
1215                 && find_regno_note (insn, REG_DEAD, reg->regno) != NULL)
1216               CLEAR_HARD_REG_BIT (live_hard_regs, reg->regno);
1217             else if (reg->type != OP_IN
1218                      && find_regno_note (insn, REG_UNUSED, reg->regno) == NULL)
1219               SET_HARD_REG_BIT (live_hard_regs, reg->regno);
1220         }
1221     }
1222   bitmap_clear (&avail_cands);
1223   return changed_p;
1224 }
1225
1226 \f
1227
1228 /* Entry point of the rematerialization sub-pass.  Return true if we
1229    did any rematerialization.  */
1230 bool
1231 lra_remat (void)
1232 {
1233   basic_block bb;
1234   bool result;
1235   int max_regno = max_reg_num ();
1236
1237   if (! flag_lra_remat)
1238     return false;
1239   timevar_push (TV_LRA_REMAT);
1240   insn_to_cand = XCNEWVEC (cand_t, get_max_uid ());
1241   regno_cands = XCNEWVEC (cand_t, max_regno);
1242   all_cands.create (8000);
1243   call_used_regs_arr_len = 0;
1244   for (int i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1245     if (call_used_regs[i])
1246       call_used_regs_arr[call_used_regs_arr_len++] = i;
1247   initiate_cand_table ();
1248   create_cands ();
1249   create_remat_bb_data ();
1250   bitmap_initialize (&temp_bitmap, &reg_obstack);
1251   calculate_local_reg_remat_bb_data ();
1252   calculate_livein_cands ();
1253   calculate_gen_cands ();
1254   bitmap_initialize (&all_blocks, &reg_obstack);
1255   FOR_ALL_BB_FN (bb, cfun)
1256     bitmap_set_bit (&all_blocks, bb->index);
1257   calculate_global_remat_bb_data ();
1258   dump_candidates_and_remat_bb_data ();
1259   result = do_remat ();
1260   all_cands.release ();
1261   bitmap_clear (&temp_bitmap);
1262   finish_remat_bb_data ();
1263   finish_cand_table ();
1264   bitmap_clear (&all_blocks);
1265   free (regno_cands);
1266   free (insn_to_cand);
1267   timevar_pop (TV_LRA_REMAT);
1268   return result;
1269 }