gcc/lra-lives.c

   1 /* Build live ranges for pseudos.
   2    Copyright (C) 2010-2016 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
  22 /* This file contains code to build pseudo live-ranges (analogous
  23    structures used in IRA, so read comments about the live-ranges
  24    there) and other info necessary for other passes to assign
  25    hard-registers to pseudos, coalesce the spilled pseudos, and assign
  26    stack memory slots to spilled pseudos.  */
  27
  28 #include "config.h"
  29 #include "system.h"
  30 #include "coretypes.h"
  31 #include "backend.h"
  32 #include "rtl.h"
  33 #include "tree.h"
  34 #include "predict.h"
  35 #include "df.h"
  36 #include "tm_p.h"
  37 #include "insn-config.h"
  38 #include "regs.h"
  39 #include "ira.h"
  40 #include "recog.h"
  41 #include "cfganal.h"
  42 #include "sparseset.h"
  43 #include "lra-int.h"
  44
  45 /* Program points are enumerated by numbers from range
  46    0..LRA_LIVE_MAX_POINT-1.  There are approximately two times more
  47    program points than insns.  Program points are places in the
  48    program where liveness info can be changed.  In most general case
  49    (there are more complicated cases too) some program points
  50    correspond to places where input operand dies and other ones
  51    correspond to places where output operands are born.  */
  52 int lra_live_max_point;
  53
  54 /* Accumulated execution frequency of all references for each hard
  55    register.  */
  56 int lra_hard_reg_usage[FIRST_PSEUDO_REGISTER];
  57
  58 /* A global flag whose true value says to build live ranges for all
  59    pseudos, otherwise the live ranges only for pseudos got memory is
  60    build.  True value means also building copies and setting up hard
  61    register preferences.  The complete info is necessary only for the
  62    assignment pass.  The complete info is not needed for the
  63    coalescing and spill passes.  */
  64 static bool complete_info_p;
  65
  66 /* Pseudos live at current point in the RTL scan.  */
  67 static sparseset pseudos_live;
  68
  69 /* Pseudos probably living through calls and setjumps.  As setjump is
  70    a call too, if a bit in PSEUDOS_LIVE_THROUGH_SETJUMPS is set up
  71    then the corresponding bit in PSEUDOS_LIVE_THROUGH_CALLS is set up
  72    too.  These data are necessary for cases when only one subreg of a
  73    multi-reg pseudo is set up after a call.  So we decide it is
  74    probably live when traversing bb backward.  We are sure about
  75    living when we see its usage or definition of the pseudo.  */
  76 static sparseset pseudos_live_through_calls;
  77 static sparseset pseudos_live_through_setjumps;
  78
  79 /* Set of hard regs (except eliminable ones) currently live.  */
  80 static HARD_REG_SET hard_regs_live;
  81
  82 /* Set of pseudos and hard registers start living/dying in the current
  83    insn.  These sets are used to update REG_DEAD and REG_UNUSED notes
  84    in the insn.  */
  85 static sparseset start_living, start_dying;
  86
  87 /* Set of pseudos and hard regs dead and unused in the current
  88    insn.  */
  89 static sparseset unused_set, dead_set;
  90
  91 /* Bitmap used for holding intermediate bitmap operation results.  */
  92 static bitmap_head temp_bitmap;
  93
  94 /* Pool for pseudo live ranges.  */
  95 static object_allocator<lra_live_range> lra_live_range_pool ("live ranges");
  96
  97 /* Free live range list LR.  */
  98 static void
  99 free_live_range_list (lra_live_range_t lr)
 100 {
 101   lra_live_range_t next;
 102
 103   while (lr != NULL)
 104     {
 105       next = lr->next;
 106       lra_live_range_pool.remove (lr);
 107       lr = next;
 108     }
 109 }
 110
 111 /* Create and return pseudo live range with given attributes.  */
 112 static lra_live_range_t
 113 create_live_range (int regno, int start, int finish, lra_live_range_t next)
 114 {
 115   lra_live_range_t p = lra_live_range_pool.allocate ();
 116   p->regno = regno;
 117   p->start = start;
 118   p->finish = finish;
 119   p->next = next;
 120   return p;
 121 }
 122
 123 /* Copy live range R and return the result.  */
 124 static lra_live_range_t
 125 copy_live_range (lra_live_range_t r)
 126 {
 127   return new (lra_live_range_pool) lra_live_range (*r);
 128 }
 129
 130 /* Copy live range list given by its head R and return the result.  */
 131 lra_live_range_t
 132 lra_copy_live_range_list (lra_live_range_t r)
 133 {
 134   lra_live_range_t p, first, *chain;
 135
 136   first = NULL;
 137   for (chain = &first; r != NULL; r = r->next)
 138     {
 139       p = copy_live_range (r);
 140       *chain = p;
 141       chain = &p->next;
 142     }
 143   return first;
 144 }
 145
 146 /* Merge *non-intersected* ranges R1 and R2 and returns the result.
 147    The function maintains the order of ranges and tries to minimize
 148    size of the result range list.  Ranges R1 and R2 may not be used
 149    after the call.  */
 150 lra_live_range_t
 151 lra_merge_live_ranges (lra_live_range_t r1, lra_live_range_t r2)
 152 {
 153   lra_live_range_t first, last;
 154
 155   if (r1 == NULL)
 156     return r2;
 157   if (r2 == NULL)
 158     return r1;
 159   for (first = last = NULL; r1 != NULL && r2 != NULL;)
 160     {
 161       if (r1->start < r2->start)
 162         std::swap (r1, r2);
 163
 164       if (r1->start == r2->finish + 1)
 165         {
 166           /* Joint ranges: merge r1 and r2 into r1.  */
 167           r1->start = r2->start;
 168           lra_live_range_t temp = r2;
 169           r2 = r2->next;
 170           lra_live_range_pool.remove (temp);
 171         }
 172       else
 173         {
 174           gcc_assert (r2->finish + 1 < r1->start);
 175           /* Add r1 to the result.  */
 176           if (first == NULL)
 177             first = last = r1;
 178           else
 179             {
 180               last->next = r1;
 181               last = r1;
 182             }
 183           r1 = r1->next;
 184         }
 185     }
 186   if (r1 != NULL)
 187     {
 188       if (first == NULL)
 189         first = r1;
 190       else
 191         last->next = r1;
 192     }
 193   else
 194     {
 195       lra_assert (r2 != NULL);
 196       if (first == NULL)
 197         first = r2;
 198       else
 199         last->next = r2;
 200     }
 201   return first;
 202 }
 203
 204 /* Return TRUE if live ranges R1 and R2 intersect.  */
 205 bool
 206 lra_intersected_live_ranges_p (lra_live_range_t r1, lra_live_range_t r2)
 207 {
 208   /* Remember the live ranges are always kept ordered.  */
 209   while (r1 != NULL && r2 != NULL)
 210     {
 211       if (r1->start > r2->finish)
 212         r1 = r1->next;
 213       else if (r2->start > r1->finish)
 214         r2 = r2->next;
 215       else
 216         return true;
 217     }
 218   return false;
 219 }
 220
 221 /* The function processing birth of hard register REGNO.  It updates
 222    living hard regs, START_LIVING, and conflict hard regs for living
 223    pseudos.  Conflict hard regs for the pic pseudo is not updated if
 224    REGNO is REAL_PIC_OFFSET_TABLE_REGNUM and CHECK_PIC_PSEUDO_P is
 225    true.  */
 226 static void
 227 make_hard_regno_born (int regno, bool check_pic_pseudo_p ATTRIBUTE_UNUSED)
 228 {
 229   unsigned int i;
 230
 231   lra_assert (regno < FIRST_PSEUDO_REGISTER);
 232   if (TEST_HARD_REG_BIT (hard_regs_live, regno))
 233     return;
 234   SET_HARD_REG_BIT (hard_regs_live, regno);
 235   sparseset_set_bit (start_living, regno);
 236   EXECUTE_IF_SET_IN_SPARSESET (pseudos_live, i)
 237 #ifdef REAL_PIC_OFFSET_TABLE_REGNUM
 238     if (! check_pic_pseudo_p
 239         || regno != REAL_PIC_OFFSET_TABLE_REGNUM
 240         || pic_offset_table_rtx == NULL
 241         || i != REGNO (pic_offset_table_rtx))
 242 #endif
 243       SET_HARD_REG_BIT (lra_reg_info[i].conflict_hard_regs, regno);
 244 }
 245
 246 /* Process the death of hard register REGNO.  This updates
 247    hard_regs_live and START_DYING.  */
 248 static void
 249 make_hard_regno_dead (int regno)
 250 {
 251   lra_assert (regno < FIRST_PSEUDO_REGISTER);
 252   if (! TEST_HARD_REG_BIT (hard_regs_live, regno))
 253     return;
 254   sparseset_set_bit (start_dying, regno);
 255   CLEAR_HARD_REG_BIT (hard_regs_live, regno);
 256 }
 257
 258 /* Mark pseudo REGNO as living at program point POINT, update conflicting
 259    hard registers of the pseudo and START_LIVING, and start a new live
 260    range for the pseudo corresponding to REGNO if it is necessary.  */
 261 static void
 262 mark_pseudo_live (int regno, int point)
 263 {
 264   lra_live_range_t p;
 265
 266   lra_assert (regno >= FIRST_PSEUDO_REGISTER);
 267   lra_assert (! sparseset_bit_p (pseudos_live, regno));
 268   sparseset_set_bit (pseudos_live, regno);
 269   IOR_HARD_REG_SET (lra_reg_info[regno].conflict_hard_regs, hard_regs_live);
 270
 271   if ((complete_info_p || lra_get_regno_hard_regno (regno) < 0)
 272       && ((p = lra_reg_info[regno].live_ranges) == NULL
 273           || (p->finish != point && p->finish + 1 != point)))
 274      lra_reg_info[regno].live_ranges
 275        = create_live_range (regno, point, -1, p);
 276   sparseset_set_bit (start_living, regno);
 277 }
 278
 279 /* Mark pseudo REGNO as not living at program point POINT and update
 280    START_DYING.
 281    This finishes the current live range for the pseudo corresponding
 282    to REGNO.  */
 283 static void
 284 mark_pseudo_dead (int regno, int point)
 285 {
 286   lra_live_range_t p;
 287
 288   lra_assert (regno >= FIRST_PSEUDO_REGISTER);
 289   lra_assert (sparseset_bit_p (pseudos_live, regno));
 290   sparseset_clear_bit (pseudos_live, regno);
 291   sparseset_set_bit (start_dying, regno);
 292   if (complete_info_p || lra_get_regno_hard_regno (regno) < 0)
 293     {
 294       p = lra_reg_info[regno].live_ranges;
 295       lra_assert (p != NULL);
 296       p->finish = point;
 297     }
 298 }
 299
 300 /* The corresponding bitmaps of BB currently being processed.  */
 301 static bitmap bb_killed_pseudos, bb_gen_pseudos;
 302
 303 /* Mark register REGNO (pseudo or hard register) in MODE as live at
 304    program point POINT.  Update BB_GEN_PSEUDOS.
 305    Return TRUE if the liveness tracking sets were modified, or FALSE
 306    if nothing changed.  */
 307 static bool
 308 mark_regno_live (int regno, machine_mode mode, int point)
 309 {
 310   int last;
 311   bool changed = false;
 312
 313   if (regno < FIRST_PSEUDO_REGISTER)
 314     {
 315       for (last = regno + hard_regno_nregs[regno][mode];
 316            regno < last;
 317            regno++)
 318         make_hard_regno_born (regno, false);
 319     }
 320   else
 321     {
 322       if (! sparseset_bit_p (pseudos_live, regno))
 323         {
 324           mark_pseudo_live (regno, point);
 325           changed = true;
 326         }
 327       bitmap_set_bit (bb_gen_pseudos, regno);
 328     }
 329   return changed;
 330 }
 331
 332
 333 /* Mark register REGNO in MODE as dead at program point POINT.  Update
 334    BB_GEN_PSEUDOS and BB_KILLED_PSEUDOS.  Return TRUE if the liveness
 335    tracking sets were modified, or FALSE if nothing changed.  */
 336 static bool
 337 mark_regno_dead (int regno, machine_mode mode, int point)
 338 {
 339   int last;
 340   bool changed = false;
 341
 342   if (regno < FIRST_PSEUDO_REGISTER)
 343     {
 344       for (last = regno + hard_regno_nregs[regno][mode];
 345            regno < last;
 346            regno++)
 347         make_hard_regno_dead (regno);
 348     }
 349   else
 350     {
 351       if (sparseset_bit_p (pseudos_live, regno))
 352         {
 353           mark_pseudo_dead (regno, point);
 354           changed = true;
 355         }
 356       bitmap_clear_bit (bb_gen_pseudos, regno);
 357       bitmap_set_bit (bb_killed_pseudos, regno);
 358     }
 359   return changed;
 360 }
 361
 362 \f
 363
 364 /* This page contains code for making global live analysis of pseudos.
 365    The code works only when pseudo live info is changed on a BB
 366    border.  That might be a consequence of some global transformations
 367    in LRA, e.g. PIC pseudo reuse or rematerialization.  */
 368
 369 /* Structure describing local BB data used for pseudo
 370    live-analysis.  */
 371 struct bb_data_pseudos
 372 {
 373   /* Basic block about which the below data are.  */
 374   basic_block bb;
 375   bitmap_head killed_pseudos; /* pseudos killed in the BB.  */
 376   bitmap_head gen_pseudos; /* pseudos generated in the BB.  */
 377 };
 378
 379 /* Array for all BB data.  Indexed by the corresponding BB index.  */
 380 typedef struct bb_data_pseudos *bb_data_t;
 381
 382 /* All basic block data are referred through the following array.  */
 383 static bb_data_t bb_data;
 384
 385 /* Two small functions for access to the bb data.  */
 386 static inline bb_data_t
 387 get_bb_data (basic_block bb)
 388 {
 389   return &bb_data[(bb)->index];
 390 }
 391
 392 static inline bb_data_t
 393 get_bb_data_by_index (int index)
 394 {
 395   return &bb_data[index];
 396 }
 397
 398 /* Bitmap with all hard regs.  */
 399 static bitmap_head all_hard_regs_bitmap;
 400
 401 /* The transfer function used by the DF equation solver to propagate
 402    live info through block with BB_INDEX according to the following
 403    equation:
 404
 405      bb.livein = (bb.liveout - bb.kill) OR bb.gen
 406 */
 407 static bool
 408 live_trans_fun (int bb_index)
 409 {
 410   basic_block bb = get_bb_data_by_index (bb_index)->bb;
 411   bitmap bb_liveout = df_get_live_out (bb);
 412   bitmap bb_livein = df_get_live_in (bb);
 413   bb_data_t bb_info = get_bb_data (bb);
 414
 415   bitmap_and_compl (&temp_bitmap, bb_liveout, &all_hard_regs_bitmap);
 416   return bitmap_ior_and_compl (bb_livein, &bb_info->gen_pseudos,
 417                                &temp_bitmap, &bb_info->killed_pseudos);
 418 }
 419
 420 /* The confluence function used by the DF equation solver to set up
 421    live info for a block BB without predecessor.  */
 422 static void
 423 live_con_fun_0 (basic_block bb)
 424 {
 425   bitmap_and_into (df_get_live_out (bb), &all_hard_regs_bitmap);
 426 }
 427
 428 /* The confluence function used by the DF equation solver to propagate
 429    live info from successor to predecessor on edge E according to the
 430    following equation:
 431
 432       bb.liveout = 0 for entry block | OR (livein of successors)
 433  */
 434 static bool
 435 live_con_fun_n (edge e)
 436 {
 437   basic_block bb = e->src;
 438   basic_block dest = e->dest;
 439   bitmap bb_liveout = df_get_live_out (bb);
 440   bitmap dest_livein = df_get_live_in (dest);
 441
 442   return bitmap_ior_and_compl_into (bb_liveout,
 443                                     dest_livein, &all_hard_regs_bitmap);
 444 }
 445
 446 /* Indexes of all function blocks.  */
 447 static bitmap_head all_blocks;
 448
 449 /* Allocate and initialize data needed for global pseudo live
 450    analysis.  */
 451 static void
 452 initiate_live_solver (void)
 453 {
 454   bitmap_initialize (&all_hard_regs_bitmap, &reg_obstack);
 455   bitmap_set_range (&all_hard_regs_bitmap, 0, FIRST_PSEUDO_REGISTER);
 456   bb_data = XNEWVEC (struct bb_data_pseudos, last_basic_block_for_fn (cfun));
 457   bitmap_initialize (&all_blocks, &reg_obstack);
 458
 459   basic_block bb;
 460   FOR_ALL_BB_FN (bb, cfun)
 461     {
 462       bb_data_t bb_info = get_bb_data (bb);
 463       bb_info->bb = bb;
 464       bitmap_initialize (&bb_info->killed_pseudos, &reg_obstack);
 465       bitmap_initialize (&bb_info->gen_pseudos, &reg_obstack);
 466       bitmap_set_bit (&all_blocks, bb->index);
 467     }
 468 }
 469
 470 /* Free all data needed for global pseudo live analysis.  */
 471 static void
 472 finish_live_solver (void)
 473 {
 474   basic_block bb;
 475
 476   bitmap_clear (&all_blocks);
 477   FOR_ALL_BB_FN (bb, cfun)
 478     {
 479       bb_data_t bb_info = get_bb_data (bb);
 480       bitmap_clear (&bb_info->killed_pseudos);
 481       bitmap_clear (&bb_info->gen_pseudos);
 482     }
 483   free (bb_data);
 484   bitmap_clear (&all_hard_regs_bitmap);
 485 }
 486
 487 \f
 488
 489 /* Insn currently scanned.  */
 490 static rtx_insn *curr_insn;
 491 /* The insn data.  */
 492 static lra_insn_recog_data_t curr_id;
 493 /* The insn static data.  */
 494 static struct lra_static_insn_data *curr_static_id;
 495
 496 /* Vec containing execution frequencies of program points.  */
 497 static vec<int> point_freq_vec;
 498
 499 /* The start of the above vector elements.  */
 500 int *lra_point_freq;
 501
 502 /* Increment the current program point POINT to the next point which has
 503    execution frequency FREQ.  */
 504 static void
 505 next_program_point (int &point, int freq)
 506 {
 507   point_freq_vec.safe_push (freq);
 508   lra_point_freq = point_freq_vec.address ();
 509   point++;
 510 }
 511
 512 /* Update the preference of HARD_REGNO for pseudo REGNO by PROFIT.  */
 513 void
 514 lra_setup_reload_pseudo_preferenced_hard_reg (int regno,
 515                                               int hard_regno, int profit)
 516 {
 517   lra_assert (regno >= lra_constraint_new_regno_start);
 518   if (lra_reg_info[regno].preferred_hard_regno1 == hard_regno)
 519     lra_reg_info[regno].preferred_hard_regno_profit1 += profit;
 520   else if (lra_reg_info[regno].preferred_hard_regno2 == hard_regno)
 521     lra_reg_info[regno].preferred_hard_regno_profit2 += profit;
 522   else if (lra_reg_info[regno].preferred_hard_regno1 < 0)
 523     {
 524       lra_reg_info[regno].preferred_hard_regno1 = hard_regno;
 525       lra_reg_info[regno].preferred_hard_regno_profit1 = profit;
 526     }
 527   else if (lra_reg_info[regno].preferred_hard_regno2 < 0
 528            || profit > lra_reg_info[regno].preferred_hard_regno_profit2)
 529     {
 530       lra_reg_info[regno].preferred_hard_regno2 = hard_regno;
 531       lra_reg_info[regno].preferred_hard_regno_profit2 = profit;
 532     }
 533   else
 534     return;
 535   /* Keep the 1st hard regno as more profitable.  */
 536   if (lra_reg_info[regno].preferred_hard_regno1 >= 0
 537       && lra_reg_info[regno].preferred_hard_regno2 >= 0
 538       && (lra_reg_info[regno].preferred_hard_regno_profit2
 539           > lra_reg_info[regno].preferred_hard_regno_profit1))
 540     {
 541       std::swap (lra_reg_info[regno].preferred_hard_regno1,
 542                  lra_reg_info[regno].preferred_hard_regno2);
 543       std::swap (lra_reg_info[regno].preferred_hard_regno_profit1,
 544                  lra_reg_info[regno].preferred_hard_regno_profit2);
 545     }
 546   if (lra_dump_file != NULL)
 547     {
 548       if ((hard_regno = lra_reg_info[regno].preferred_hard_regno1) >= 0)
 549         fprintf (lra_dump_file,
 550                  "      Hard reg %d is preferable by r%d with profit %d\n",
 551                  hard_regno, regno,
 552                  lra_reg_info[regno].preferred_hard_regno_profit1);
 553       if ((hard_regno = lra_reg_info[regno].preferred_hard_regno2) >= 0)
 554         fprintf (lra_dump_file,
 555                  "      Hard reg %d is preferable by r%d with profit %d\n",
 556                  hard_regno, regno,
 557                  lra_reg_info[regno].preferred_hard_regno_profit2);
 558     }
 559 }
 560
 561 /* Check that REGNO living through calls and setjumps, set up conflict
 562    regs, and clear corresponding bits in PSEUDOS_LIVE_THROUGH_CALLS and
 563    PSEUDOS_LIVE_THROUGH_SETJUMPS.  */
 564 static inline void
 565 check_pseudos_live_through_calls (int regno)
 566 {
 567   int hr;
 568
 569   if (! sparseset_bit_p (pseudos_live_through_calls, regno))
 570     return;
 571   sparseset_clear_bit (pseudos_live_through_calls, regno);
 572   IOR_HARD_REG_SET (lra_reg_info[regno].conflict_hard_regs,
 573                     call_used_reg_set);
 574
 575   for (hr = 0; hr < FIRST_PSEUDO_REGISTER; hr++)
 576     if (HARD_REGNO_CALL_PART_CLOBBERED (hr, PSEUDO_REGNO_MODE (regno)))
 577       SET_HARD_REG_BIT (lra_reg_info[regno].conflict_hard_regs, hr);
 578   lra_reg_info[regno].call_p = true;
 579   if (! sparseset_bit_p (pseudos_live_through_setjumps, regno))
 580     return;
 581   sparseset_clear_bit (pseudos_live_through_setjumps, regno);
 582   /* Don't allocate pseudos that cross setjmps or any call, if this
 583      function receives a nonlocal goto.  */
 584   SET_HARD_REG_SET (lra_reg_info[regno].conflict_hard_regs);
 585 }
 586
 587 /* Process insns of the basic block BB to update pseudo live ranges,
 588    pseudo hard register conflicts, and insn notes.  We do it on
 589    backward scan of BB insns.  CURR_POINT is the program point where
 590    BB ends.  The function updates this counter and returns in
 591    CURR_POINT the program point where BB starts.  The function also
 592    does local live info updates and can delete the dead insns if
 593    DEAD_INSN_P.  It returns true if pseudo live info was
 594    changed at the BB start.  */
 595 static bool
 596 process_bb_lives (basic_block bb, int &curr_point, bool dead_insn_p)
 597 {
 598   int i, regno, freq;
 599   unsigned int j;
 600   bitmap_iterator bi;
 601   bitmap reg_live_out;
 602   unsigned int px;
 603   rtx_insn *next;
 604   rtx link, *link_loc;
 605   bool need_curr_point_incr;
 606
 607   reg_live_out = df_get_live_out (bb);
 608   sparseset_clear (pseudos_live);
 609   sparseset_clear (pseudos_live_through_calls);
 610   sparseset_clear (pseudos_live_through_setjumps);
 611   REG_SET_TO_HARD_REG_SET (hard_regs_live, reg_live_out);
 612   AND_COMPL_HARD_REG_SET (hard_regs_live, eliminable_regset);
 613   EXECUTE_IF_SET_IN_BITMAP (reg_live_out, FIRST_PSEUDO_REGISTER, j, bi)
 614     mark_pseudo_live (j, curr_point);
 615
 616   bb_gen_pseudos = &get_bb_data (bb)->gen_pseudos;
 617   bb_killed_pseudos = &get_bb_data (bb)->killed_pseudos;
 618   bitmap_clear (bb_gen_pseudos);
 619   bitmap_clear (bb_killed_pseudos);
 620   freq = REG_FREQ_FROM_BB (bb);
 621
 622   if (lra_dump_file != NULL)
 623     fprintf (lra_dump_file, "  BB %d\n", bb->index);
 624
 625   /* Scan the code of this basic block, noting which pseudos and hard
 626      regs are born or die.
 627
 628      Note that this loop treats uninitialized values as live until the
 629      beginning of the block.  For example, if an instruction uses
 630      (reg:DI foo), and only (subreg:SI (reg:DI foo) 0) is ever set,
 631      FOO will remain live until the beginning of the block.  Likewise
 632      if FOO is not set at all.  This is unnecessarily pessimistic, but
 633      it probably doesn't matter much in practice.  */
 634   FOR_BB_INSNS_REVERSE_SAFE (bb, curr_insn, next)
 635     {
 636       bool call_p;
 637       int dst_regno, src_regno;
 638       rtx set;
 639       struct lra_insn_reg *reg;
 640
 641       if (!NONDEBUG_INSN_P (curr_insn))
 642         continue;
 643
 644       curr_id = lra_get_insn_recog_data (curr_insn);
 645       curr_static_id = curr_id->insn_static_data;
 646       if (lra_dump_file != NULL)
 647         fprintf (lra_dump_file, "   Insn %u: point = %d\n",
 648                  INSN_UID (curr_insn), curr_point);
 649
 650       set = single_set (curr_insn);
 651
 652       if (dead_insn_p && set != NULL_RTX
 653           && REG_P (SET_DEST (set)) && REGNO (SET_DEST (set)) >= FIRST_PSEUDO_REGISTER
 654           && find_reg_note (curr_insn, REG_EH_REGION, NULL_RTX) == NULL_RTX
 655           && ! may_trap_p (PATTERN (curr_insn))
 656           /* Don't do premature remove of pic offset pseudo as we can
 657              start to use it after some reload generation.  */
 658           && (pic_offset_table_rtx == NULL_RTX
 659               || pic_offset_table_rtx != SET_DEST (set)))
 660         {
 661           bool remove_p = true;
 662
 663           for (reg = curr_id->regs; reg != NULL; reg = reg->next)
 664             if (reg->type != OP_IN && sparseset_bit_p (pseudos_live, reg->regno))
 665               {
 666                 remove_p = false;
 667                 break;
 668               }
 669           for (reg = curr_static_id->hard_regs; reg != NULL; reg = reg->next)
 670             if (reg->type != OP_IN)
 671               {
 672                 remove_p = false;
 673                 break;
 674               }
 675           if (remove_p && ! volatile_refs_p (PATTERN (curr_insn)))
 676             {
 677               dst_regno = REGNO (SET_DEST (set));
 678               if (lra_dump_file != NULL)
 679                 fprintf (lra_dump_file, "   Deleting dead insn %u\n",
 680                          INSN_UID (curr_insn));
 681               lra_set_insn_deleted (curr_insn);
 682               if (lra_reg_info[dst_regno].nrefs == 0)
 683                 {
 684                   /* There might be some debug insns with the pseudo.  */
 685                   unsigned int uid;
 686                   rtx_insn *insn;
 687
 688                   bitmap_copy (&temp_bitmap, &lra_reg_info[dst_regno].insn_bitmap);
 689                   EXECUTE_IF_SET_IN_BITMAP (&temp_bitmap, 0, uid, bi)
 690                     {
 691                       insn = lra_insn_recog_data[uid]->insn;
 692                       lra_substitute_pseudo_within_insn (insn, dst_regno,
 693                                                          SET_SRC (set), true);
 694                       lra_update_insn_regno_info (insn);
 695                     }
 696                 }
 697               continue;
 698             }
 699         }
 700
 701       /* Update max ref width and hard reg usage.  */
 702       for (reg = curr_id->regs; reg != NULL; reg = reg->next)
 703         if (reg->regno >= FIRST_PSEUDO_REGISTER
 704             && (GET_MODE_SIZE (reg->biggest_mode)
 705                 > GET_MODE_SIZE (lra_reg_info[reg->regno].biggest_mode)))
 706           lra_reg_info[reg->regno].biggest_mode = reg->biggest_mode;
 707         else if (reg->regno < FIRST_PSEUDO_REGISTER)
 708           lra_hard_reg_usage[reg->regno] += freq;
 709
 710       call_p = CALL_P (curr_insn);
 711       src_regno = (set != NULL_RTX && REG_P (SET_SRC (set))
 712                    ? REGNO (SET_SRC (set)) : -1);
 713       dst_regno = (set != NULL_RTX && REG_P (SET_DEST (set))
 714                    ? REGNO (SET_DEST (set)) : -1);
 715       if (complete_info_p
 716           && src_regno >= 0 && dst_regno >= 0
 717           /* Check that source regno does not conflict with
 718              destination regno to exclude most impossible
 719              preferences.  */
 720           && (((src_regno >= FIRST_PSEUDO_REGISTER
 721                 && (! sparseset_bit_p (pseudos_live, src_regno)
 722                     || (dst_regno >= FIRST_PSEUDO_REGISTER
 723                         && lra_reg_val_equal_p (src_regno,
 724                                                 lra_reg_info[dst_regno].val,
 725                                                 lra_reg_info[dst_regno].offset))))
 726                || (src_regno < FIRST_PSEUDO_REGISTER
 727                    && ! TEST_HARD_REG_BIT (hard_regs_live, src_regno)))
 728               /* It might be 'inheritance pseudo <- reload pseudo'.  */
 729               || (src_regno >= lra_constraint_new_regno_start
 730                   && dst_regno >= lra_constraint_new_regno_start
 731                   /* Remember to skip special cases where src/dest regnos are
 732                      the same, e.g. insn SET pattern has matching constraints
 733                      like =r,0.  */
 734                   && src_regno != dst_regno)))
 735         {
 736           int hard_regno = -1, regno = -1;
 737
 738           if (dst_regno >= lra_constraint_new_regno_start
 739               && src_regno >= lra_constraint_new_regno_start)
 740             {
 741               /* It might be still an original (non-reload) insn with
 742                  one unused output and a constraint requiring to use
 743                  the same reg for input/output operands. In this case
 744                  dst_regno and src_regno have the same value, we don't
 745                  need a misleading copy for this case.  */
 746               if (dst_regno != src_regno)
 747                 lra_create_copy (dst_regno, src_regno, freq);
 748             }
 749           else if (dst_regno >= lra_constraint_new_regno_start)
 750             {
 751               if ((hard_regno = src_regno) >= FIRST_PSEUDO_REGISTER)
 752                 hard_regno = reg_renumber[src_regno];
 753               regno = dst_regno;
 754             }
 755           else if (src_regno >= lra_constraint_new_regno_start)
 756             {
 757               if ((hard_regno = dst_regno) >= FIRST_PSEUDO_REGISTER)
 758                 hard_regno = reg_renumber[dst_regno];
 759               regno = src_regno;
 760             }
 761           if (regno >= 0 && hard_regno >= 0)
 762             lra_setup_reload_pseudo_preferenced_hard_reg
 763               (regno, hard_regno, freq);
 764         }
 765
 766       sparseset_clear (start_living);
 767
 768       /* Try to avoid unnecessary program point increments, this saves
 769          a lot of time in remove_some_program_points_and_update_live_ranges.
 770          We only need an increment if something becomes live or dies at this
 771          program point.  */
 772       need_curr_point_incr = false;
 773
 774       /* Mark each defined value as live.  We need to do this for
 775          unused values because they still conflict with quantities
 776          that are live at the time of the definition.  */
 777       for (reg = curr_id->regs; reg != NULL; reg = reg->next)
 778         if (reg->type != OP_IN)
 779           {
 780             need_curr_point_incr
 781               |= mark_regno_live (reg->regno, reg->biggest_mode,
 782                                   curr_point);
 783             check_pseudos_live_through_calls (reg->regno);
 784           }
 785
 786       for (reg = curr_static_id->hard_regs; reg != NULL; reg = reg->next)
 787         if (reg->type != OP_IN)
 788           make_hard_regno_born (reg->regno, false);
 789
 790       if (curr_id->arg_hard_regs != NULL)
 791         for (i = 0; (regno = curr_id->arg_hard_regs[i]) >= 0; i++)
 792           if (regno >= FIRST_PSEUDO_REGISTER)
 793             /* It is a clobber.  */
 794             make_hard_regno_born (regno - FIRST_PSEUDO_REGISTER, false);
 795
 796       sparseset_copy (unused_set, start_living);
 797
 798       sparseset_clear (start_dying);
 799
 800       /* See which defined values die here.  */
 801       for (reg = curr_id->regs; reg != NULL; reg = reg->next)
 802         if (reg->type == OP_OUT && ! reg->early_clobber && ! reg->subreg_p)
 803           need_curr_point_incr
 804             |= mark_regno_dead (reg->regno, reg->biggest_mode,
 805                                 curr_point);
 806
 807       for (reg = curr_static_id->hard_regs; reg != NULL; reg = reg->next)
 808         if (reg->type == OP_OUT && ! reg->early_clobber && ! reg->subreg_p)
 809           make_hard_regno_dead (reg->regno);
 810
 811       if (curr_id->arg_hard_regs != NULL)
 812         for (i = 0; (regno = curr_id->arg_hard_regs[i]) >= 0; i++)
 813           if (regno >= FIRST_PSEUDO_REGISTER)
 814             /* It is a clobber.  */
 815             make_hard_regno_dead (regno - FIRST_PSEUDO_REGISTER);
 816
 817       if (call_p)
 818         {
 819           if (flag_ipa_ra)
 820             {
 821               HARD_REG_SET this_call_used_reg_set;
 822               get_call_reg_set_usage (curr_insn, &this_call_used_reg_set,
 823                                       call_used_reg_set);
 824
 825               EXECUTE_IF_SET_IN_SPARSESET (pseudos_live, j)
 826                 IOR_HARD_REG_SET (lra_reg_info[j].actual_call_used_reg_set,
 827                                   this_call_used_reg_set);
 828             }
 829
 830           sparseset_ior (pseudos_live_through_calls,
 831                          pseudos_live_through_calls, pseudos_live);
 832           if (cfun->has_nonlocal_label
 833               || find_reg_note (curr_insn, REG_SETJMP,
 834                                 NULL_RTX) != NULL_RTX)
 835             sparseset_ior (pseudos_live_through_setjumps,
 836                            pseudos_live_through_setjumps, pseudos_live);
 837         }
 838
 839       /* Increment the current program point if we must.  */
 840       if (need_curr_point_incr)
 841         next_program_point (curr_point, freq);
 842
 843       sparseset_clear (start_living);
 844
 845       need_curr_point_incr = false;
 846
 847       /* Mark each used value as live.  */
 848       for (reg = curr_id->regs; reg != NULL; reg = reg->next)
 849         if (reg->type == OP_IN)
 850           {
 851             need_curr_point_incr
 852               |= mark_regno_live (reg->regno, reg->biggest_mode,
 853                                   curr_point);
 854             check_pseudos_live_through_calls (reg->regno);
 855           }
 856
 857       for (reg = curr_static_id->hard_regs; reg != NULL; reg = reg->next)
 858         if (reg->type == OP_IN)
 859           make_hard_regno_born (reg->regno, false);
 860
 861       if (curr_id->arg_hard_regs != NULL)
 862         /* Make argument hard registers live.  Don't create conflict
 863            of used REAL_PIC_OFFSET_TABLE_REGNUM and the pic pseudo.  */
 864         for (i = 0; (regno = curr_id->arg_hard_regs[i]) >= 0; i++)
 865           if (regno < FIRST_PSEUDO_REGISTER)
 866             make_hard_regno_born (regno, true);
 867
 868       sparseset_and_compl (dead_set, start_living, start_dying);
 869
 870       /* Mark early clobber outputs dead.  */
 871       for (reg = curr_id->regs; reg != NULL; reg = reg->next)
 872         if (reg->type == OP_OUT && reg->early_clobber && ! reg->subreg_p)
 873           need_curr_point_incr
 874             |= mark_regno_dead (reg->regno, reg->biggest_mode,
 875                                 curr_point);
 876
 877       for (reg = curr_static_id->hard_regs; reg != NULL; reg = reg->next)
 878         if (reg->type == OP_OUT && reg->early_clobber && ! reg->subreg_p)
 879           make_hard_regno_dead (reg->regno);
 880
 881       if (need_curr_point_incr)
 882         next_program_point (curr_point, freq);
 883
 884       /* Update notes.  */
 885       for (link_loc = &REG_NOTES (curr_insn); (link = *link_loc) != NULL_RTX;)
 886         {
 887           if (REG_NOTE_KIND (link) != REG_DEAD
 888               && REG_NOTE_KIND (link) != REG_UNUSED)
 889             ;
 890           else if (REG_P (XEXP (link, 0)))
 891             {
 892               regno = REGNO (XEXP (link, 0));
 893               if ((REG_NOTE_KIND (link) == REG_DEAD
 894                    && ! sparseset_bit_p (dead_set, regno))
 895                   || (REG_NOTE_KIND (link) == REG_UNUSED
 896                       && ! sparseset_bit_p (unused_set, regno)))
 897                 {
 898                   *link_loc = XEXP (link, 1);
 899                   continue;
 900                 }
 901               if (REG_NOTE_KIND (link) == REG_DEAD)
 902                 sparseset_clear_bit (dead_set, regno);
 903               else if (REG_NOTE_KIND (link) == REG_UNUSED)
 904                 sparseset_clear_bit (unused_set, regno);
 905             }
 906           link_loc = &XEXP (link, 1);
 907         }
 908       EXECUTE_IF_SET_IN_SPARSESET (dead_set, j)
 909         add_reg_note (curr_insn, REG_DEAD, regno_reg_rtx[j]);
 910       EXECUTE_IF_SET_IN_SPARSESET (unused_set, j)
 911         add_reg_note (curr_insn, REG_UNUSED, regno_reg_rtx[j]);
 912     }
 913
 914   if (bb_has_eh_pred (bb))
 915     for (j = 0; ; ++j)
 916       {
 917         unsigned int regno = EH_RETURN_DATA_REGNO (j);
 918
 919         if (regno == INVALID_REGNUM)
 920           break;
 921         make_hard_regno_born (regno, false);
 922       }
 923
 924   /* Pseudos can't go in stack regs at the start of a basic block that
 925      is reached by an abnormal edge. Likewise for call clobbered regs,
 926      because caller-save, fixup_abnormal_edges and possibly the table
 927      driven EH machinery are not quite ready to handle such pseudos
 928      live across such edges.  */
 929   if (bb_has_abnormal_pred (bb))
 930     {
 931 #ifdef STACK_REGS
 932       EXECUTE_IF_SET_IN_SPARSESET (pseudos_live, px)
 933         lra_reg_info[px].no_stack_p = true;
 934       for (px = FIRST_STACK_REG; px <= LAST_STACK_REG; px++)
 935         make_hard_regno_born (px, false);
 936 #endif
 937       /* No need to record conflicts for call clobbered regs if we
 938          have nonlocal labels around, as we don't ever try to
 939          allocate such regs in this case.  */
 940       if (!cfun->has_nonlocal_label
 941           && has_abnormal_call_or_eh_pred_edge_p (bb))
 942         for (px = 0; px < FIRST_PSEUDO_REGISTER; px++)
 943           if (call_used_regs[px]
 944 #ifdef REAL_PIC_OFFSET_TABLE_REGNUM
 945               /* We should create a conflict of PIC pseudo with PIC
 946                  hard reg as PIC hard reg can have a wrong value after
 947                  jump described by the abnormal edge.  In this case we
 948                  can not allocate PIC hard reg to PIC pseudo as PIC
 949                  pseudo will also have a wrong value.  */
 950               || (px == REAL_PIC_OFFSET_TABLE_REGNUM
 951                   && pic_offset_table_rtx != NULL_RTX
 952                   && REGNO (pic_offset_table_rtx) >= FIRST_PSEUDO_REGISTER)
 953 #endif
 954               )
 955             make_hard_regno_born (px, false);
 956     }
 957
 958   bool live_change_p = false;
 959   /* Check if bb border live info was changed.  */
 960   unsigned int live_pseudos_num = 0;
 961   EXECUTE_IF_SET_IN_BITMAP (df_get_live_in (bb),
 962                             FIRST_PSEUDO_REGISTER, j, bi)
 963     {
 964       live_pseudos_num++;
 965       if (! sparseset_bit_p (pseudos_live, j))
 966         {
 967           live_change_p = true;
 968           if (lra_dump_file != NULL)
 969             fprintf (lra_dump_file,
 970                      "  r%d is removed as live at bb%d start\n", j, bb->index);
 971           break;
 972         }
 973     }
 974   if (! live_change_p
 975       && sparseset_cardinality (pseudos_live) != live_pseudos_num)
 976     {
 977       live_change_p = true;
 978       if (lra_dump_file != NULL)
 979         EXECUTE_IF_SET_IN_SPARSESET (pseudos_live, j)
 980           if (! bitmap_bit_p (df_get_live_in (bb), j))
 981             fprintf (lra_dump_file,
 982                      "  r%d is added to live at bb%d start\n", j, bb->index);
 983     }
 984   /* See if we'll need an increment at the end of this basic block.
 985      An increment is needed if the PSEUDOS_LIVE set is not empty,
 986      to make sure the finish points are set up correctly.  */
 987   need_curr_point_incr = (sparseset_cardinality (pseudos_live) > 0);
 988
 989   EXECUTE_IF_SET_IN_SPARSESET (pseudos_live, i)
 990     mark_pseudo_dead (i, curr_point);
 991
 992   EXECUTE_IF_SET_IN_BITMAP (df_get_live_in (bb), FIRST_PSEUDO_REGISTER, j, bi)
 993     {
 994       if (sparseset_cardinality (pseudos_live_through_calls) == 0)
 995         break;
 996       if (sparseset_bit_p (pseudos_live_through_calls, j))
 997         check_pseudos_live_through_calls (j);
 998     }
 999
1000   if (need_curr_point_incr)
1001     next_program_point (curr_point, freq);
1002
1003   return live_change_p;
1004 }
1005
1006 /* Compress pseudo live ranges by removing program points where
1007    nothing happens.  Complexity of many algorithms in LRA is linear
1008    function of program points number.  To speed up the code we try to
1009    minimize the number of the program points here.  */
1010 static void
1011 remove_some_program_points_and_update_live_ranges (void)
1012 {
1013   unsigned i;
1014   int n, max_regno;
1015   int *map;
1016   lra_live_range_t r, prev_r, next_r;
1017   sbitmap born_or_dead, born, dead;
1018   sbitmap_iterator sbi;
1019   bool born_p, dead_p, prev_born_p, prev_dead_p;
1020
1021   born = sbitmap_alloc (lra_live_max_point);
1022   dead = sbitmap_alloc (lra_live_max_point);
1023   bitmap_clear (born);
1024   bitmap_clear (dead);
1025   max_regno = max_reg_num ();
1026   for (i = FIRST_PSEUDO_REGISTER; i < (unsigned) max_regno; i++)
1027     {
1028       for (r = lra_reg_info[i].live_ranges; r != NULL; r = r->next)
1029         {
1030           lra_assert (r->start <= r->finish);
1031           bitmap_set_bit (born, r->start);
1032           bitmap_set_bit (dead, r->finish);
1033         }
1034     }
1035   born_or_dead = sbitmap_alloc (lra_live_max_point);
1036   bitmap_ior (born_or_dead, born, dead);
1037   map = XCNEWVEC (int, lra_live_max_point);
1038   n = -1;
1039   prev_born_p = prev_dead_p = false;
1040   EXECUTE_IF_SET_IN_BITMAP (born_or_dead, 0, i, sbi)
1041     {
1042       born_p = bitmap_bit_p (born, i);
1043       dead_p = bitmap_bit_p (dead, i);
1044       if ((prev_born_p && ! prev_dead_p && born_p && ! dead_p)
1045           || (prev_dead_p && ! prev_born_p && dead_p && ! born_p))
1046         {
1047           map[i] = n;
1048           lra_point_freq[n] = MAX (lra_point_freq[n], lra_point_freq[i]);
1049         }
1050       else
1051         {
1052           map[i] = ++n;
1053           lra_point_freq[n] = lra_point_freq[i];
1054         }
1055       prev_born_p = born_p;
1056       prev_dead_p = dead_p;
1057     }
1058   sbitmap_free (born_or_dead);
1059   sbitmap_free (born);
1060   sbitmap_free (dead);
1061   n++;
1062   if (lra_dump_file != NULL)
1063     fprintf (lra_dump_file, "Compressing live ranges: from %d to %d - %d%%\n",
1064              lra_live_max_point, n, 100 * n / lra_live_max_point);
1065   if (n < lra_live_max_point)
1066     {
1067       lra_live_max_point = n;
1068       for (i = FIRST_PSEUDO_REGISTER; i < (unsigned) max_regno; i++)
1069         {
1070           for (prev_r = NULL, r = lra_reg_info[i].live_ranges;
1071                r != NULL;
1072                r = next_r)
1073             {
1074               next_r = r->next;
1075               r->start = map[r->start];
1076               r->finish = map[r->finish];
1077               if (prev_r == NULL || prev_r->start > r->finish + 1)
1078                 {
1079                   prev_r = r;
1080                   continue;
1081                 }
1082               prev_r->start = r->start;
1083               prev_r->next = next_r;
1084               lra_live_range_pool.remove (r);
1085             }
1086         }
1087     }
1088   free (map);
1089 }
1090
1091 /* Print live ranges R to file F.  */
1092 void
1093 lra_print_live_range_list (FILE *f, lra_live_range_t r)
1094 {
1095   for (; r != NULL; r = r->next)
1096     fprintf (f, " [%d..%d]", r->start, r->finish);
1097   fprintf (f, "\n");
1098 }
1099
1100 DEBUG_FUNCTION void
1101 debug (lra_live_range &ref)
1102 {
1103   lra_print_live_range_list (stderr, &ref);
1104 }
1105
1106 DEBUG_FUNCTION void
1107 debug (lra_live_range *ptr)
1108 {
1109   if (ptr)
1110     debug (*ptr);
1111   else
1112     fprintf (stderr, "<nil>\n");
1113 }
1114
1115 /* Print live ranges R to stderr.  */
1116 void
1117 lra_debug_live_range_list (lra_live_range_t r)
1118 {
1119   lra_print_live_range_list (stderr, r);
1120 }
1121
1122 /* Print live ranges of pseudo REGNO to file F.  */
1123 static void
1124 print_pseudo_live_ranges (FILE *f, int regno)
1125 {
1126   if (lra_reg_info[regno].live_ranges == NULL)
1127     return;
1128   fprintf (f, " r%d:", regno);
1129   lra_print_live_range_list (f, lra_reg_info[regno].live_ranges);
1130 }
1131
1132 /* Print live ranges of pseudo REGNO to stderr.  */
1133 void
1134 lra_debug_pseudo_live_ranges (int regno)
1135 {
1136   print_pseudo_live_ranges (stderr, regno);
1137 }
1138
1139 /* Print live ranges of all pseudos to file F.  */
1140 static void
1141 print_live_ranges (FILE *f)
1142 {
1143   int i, max_regno;
1144
1145   max_regno = max_reg_num ();
1146   for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
1147     print_pseudo_live_ranges (f, i);
1148 }
1149
1150 /* Print live ranges of all pseudos to stderr.  */
1151 void
1152 lra_debug_live_ranges (void)
1153 {
1154   print_live_ranges (stderr);
1155 }
1156
1157 /* Compress pseudo live ranges.  */
1158 static void
1159 compress_live_ranges (void)
1160 {
1161   remove_some_program_points_and_update_live_ranges ();
1162   if (lra_dump_file != NULL)
1163     {
1164       fprintf (lra_dump_file, "Ranges after the compression:\n");
1165       print_live_ranges (lra_dump_file);
1166     }
1167 }
1168
1169 \f
1170
1171 /* The number of the current live range pass.  */
1172 int lra_live_range_iter;
1173
1174 /* The function creates live ranges only for memory pseudos (or for
1175    all ones if ALL_P), set up CONFLICT_HARD_REGS for the pseudos.  It
1176    also does dead insn elimination if DEAD_INSN_P and global live
1177    analysis only for pseudos and only if the pseudo live info was
1178    changed on a BB border.  Return TRUE if the live info was
1179    changed.  */
1180 static bool
1181 lra_create_live_ranges_1 (bool all_p, bool dead_insn_p)
1182 {
1183   basic_block bb;
1184   int i, hard_regno, max_regno = max_reg_num ();
1185   int curr_point;
1186   bool bb_live_change_p, have_referenced_pseudos = false;
1187
1188   timevar_push (TV_LRA_CREATE_LIVE_RANGES);
1189
1190   complete_info_p = all_p;
1191   if (lra_dump_file != NULL)
1192     fprintf (lra_dump_file,
1193              "\n********** Pseudo live ranges #%d: **********\n\n",
1194              ++lra_live_range_iter);
1195   memset (lra_hard_reg_usage, 0, sizeof (lra_hard_reg_usage));
1196   for (i = 0; i < max_regno; i++)
1197     {
1198       lra_reg_info[i].live_ranges = NULL;
1199       CLEAR_HARD_REG_SET (lra_reg_info[i].conflict_hard_regs);
1200       lra_reg_info[i].preferred_hard_regno1 = -1;
1201       lra_reg_info[i].preferred_hard_regno2 = -1;
1202       lra_reg_info[i].preferred_hard_regno_profit1 = 0;
1203       lra_reg_info[i].preferred_hard_regno_profit2 = 0;
1204 #ifdef STACK_REGS
1205       lra_reg_info[i].no_stack_p = false;
1206 #endif
1207       /* The biggest mode is already set but its value might be to
1208          conservative because of recent transformation.  Here in this
1209          file we recalculate it again as it costs practically
1210          nothing.  */
1211       if (regno_reg_rtx[i] != NULL_RTX)
1212         lra_reg_info[i].biggest_mode = GET_MODE (regno_reg_rtx[i]);
1213       else
1214         lra_reg_info[i].biggest_mode = VOIDmode;
1215       lra_reg_info[i].call_p = false;
1216       if (i >= FIRST_PSEUDO_REGISTER
1217           && lra_reg_info[i].nrefs != 0)
1218         {
1219           if ((hard_regno = reg_renumber[i]) >= 0)
1220             lra_hard_reg_usage[hard_regno] += lra_reg_info[i].freq;
1221           have_referenced_pseudos = true;
1222         }
1223     }
1224   lra_free_copies ();
1225
1226   /* Under some circumstances, we can have functions without pseudo
1227      registers.  For such functions, lra_live_max_point will be 0,
1228      see e.g. PR55604, and there's nothing more to do for us here.  */
1229   if (! have_referenced_pseudos)
1230     {
1231       timevar_pop (TV_LRA_CREATE_LIVE_RANGES);
1232       return false;
1233     }
1234
1235   pseudos_live = sparseset_alloc (max_regno);
1236   pseudos_live_through_calls = sparseset_alloc (max_regno);
1237   pseudos_live_through_setjumps = sparseset_alloc (max_regno);
1238   start_living = sparseset_alloc (max_regno);
1239   start_dying = sparseset_alloc (max_regno);
1240   dead_set = sparseset_alloc (max_regno);
1241   unused_set = sparseset_alloc (max_regno);
1242   curr_point = 0;
1243   unsigned new_length = get_max_uid () * 2;
1244   point_freq_vec.truncate (0);
1245   point_freq_vec.reserve_exact (new_length);
1246   lra_point_freq = point_freq_vec.address ();
1247   int *post_order_rev_cfg = XNEWVEC (int, last_basic_block_for_fn (cfun));
1248   int n_blocks_inverted = inverted_post_order_compute (post_order_rev_cfg);
1249   lra_assert (n_blocks_inverted == n_basic_blocks_for_fn (cfun));
1250   bb_live_change_p = false;
1251   for (i = n_blocks_inverted - 1; i >= 0; --i)
1252     {
1253       bb = BASIC_BLOCK_FOR_FN (cfun, post_order_rev_cfg[i]);
1254       if (bb == EXIT_BLOCK_PTR_FOR_FN (cfun) || bb
1255           == ENTRY_BLOCK_PTR_FOR_FN (cfun))
1256         continue;
1257       if (process_bb_lives (bb, curr_point, dead_insn_p))
1258         bb_live_change_p = true;
1259     }
1260   if (bb_live_change_p)
1261     {
1262       /* We need to clear pseudo live info as some pseudos can
1263          disappear, e.g. pseudos with used equivalences.  */
1264       FOR_EACH_BB_FN (bb, cfun)
1265         {
1266           bitmap_clear_range (df_get_live_in (bb), FIRST_PSEUDO_REGISTER,
1267                               max_regno - FIRST_PSEUDO_REGISTER);
1268           bitmap_clear_range (df_get_live_out (bb), FIRST_PSEUDO_REGISTER,
1269                               max_regno - FIRST_PSEUDO_REGISTER);
1270         }
1271       /* As we did not change CFG since LRA start we can use
1272          DF-infrastructure solver to solve live data flow problem.  */
1273       df_simple_dataflow
1274         (DF_BACKWARD, NULL, live_con_fun_0, live_con_fun_n,
1275          live_trans_fun, &all_blocks,
1276          df_get_postorder (DF_BACKWARD), df_get_n_blocks (DF_BACKWARD));
1277       if (lra_dump_file != NULL)
1278         {
1279           fprintf (lra_dump_file,
1280                    "Global pseudo live data have been updated:\n");
1281           basic_block bb;
1282           FOR_EACH_BB_FN (bb, cfun)
1283             {
1284               bb_data_t bb_info = get_bb_data (bb);
1285               bitmap bb_livein = df_get_live_in (bb);
1286               bitmap bb_liveout = df_get_live_out (bb);
1287
1288               fprintf (lra_dump_file, "\nBB %d:\n", bb->index);
1289               lra_dump_bitmap_with_title ("  gen:",
1290                                           &bb_info->gen_pseudos, bb->index);
1291               lra_dump_bitmap_with_title ("  killed:",
1292                                           &bb_info->killed_pseudos, bb->index);
1293               lra_dump_bitmap_with_title ("  livein:", bb_livein, bb->index);
1294               lra_dump_bitmap_with_title ("  liveout:", bb_liveout, bb->index);
1295             }
1296         }
1297     }
1298   free (post_order_rev_cfg);
1299   lra_live_max_point = curr_point;
1300   if (lra_dump_file != NULL)
1301     print_live_ranges (lra_dump_file);
1302   /* Clean up.  */
1303   sparseset_free (unused_set);
1304   sparseset_free (dead_set);
1305   sparseset_free (start_dying);
1306   sparseset_free (start_living);
1307   sparseset_free (pseudos_live_through_calls);
1308   sparseset_free (pseudos_live_through_setjumps);
1309   sparseset_free (pseudos_live);
1310   compress_live_ranges ();
1311   timevar_pop (TV_LRA_CREATE_LIVE_RANGES);
1312   return bb_live_change_p;
1313 }
1314
1315 /* The main entry function creates live-ranges and other live info
1316    necessary for the assignment sub-pass.  It uses
1317    lra_creates_live_ranges_1 -- so read comments for the
1318    function.  */
1319 void
1320 lra_create_live_ranges (bool all_p, bool dead_insn_p)
1321 {
1322   if (! lra_create_live_ranges_1 (all_p, dead_insn_p))
1323     return;
1324   if (lra_dump_file != NULL)
1325     fprintf (lra_dump_file, "Live info was changed -- recalculate it\n");
1326   /* Live info was changed on a bb border.  It means that some info,
1327      e.g. about conflict regs, calls crossed, and live ranges may be
1328      wrong.  We need this info for allocation.  So recalculate it
1329      again but without removing dead insns which can change live info
1330      again.  Repetitive live range calculations are expensive therefore
1331      we stop here as we already have correct info although some
1332      improvement in rare cases could be possible on this sub-pass if
1333      we do dead insn elimination again (still the improvement may
1334      happen later).  */
1335   lra_clear_live_ranges ();
1336   bool res = lra_create_live_ranges_1 (all_p, false);
1337   lra_assert (! res);
1338 }
1339
1340 /* Finish all live ranges.  */
1341 void
1342 lra_clear_live_ranges (void)
1343 {
1344   int i;
1345
1346   for (i = 0; i < max_reg_num (); i++)
1347     free_live_range_list (lra_reg_info[i].live_ranges);
1348   point_freq_vec.release ();
1349 }
1350
1351 /* Initialize live ranges data once per function.  */
1352 void
1353 lra_live_ranges_init (void)
1354 {
1355   bitmap_initialize (&temp_bitmap, &reg_obstack);
1356   initiate_live_solver ();
1357 }
1358
1359 /* Finish live ranges data once per function.  */
1360 void
1361 lra_live_ranges_finish (void)
1362 {
1363   finish_live_solver ();
1364   bitmap_clear (&temp_bitmap);
1365   lra_live_range_pool.release ();
1366 }