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         {
 704           if (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           if (reg->regno < FIRST_PSEUDO_REGISTER)
 708             lra_hard_reg_usage[reg->regno] += freq;
 709         }
 710
 711       call_p = CALL_P (curr_insn);
 712       src_regno = (set != NULL_RTX && REG_P (SET_SRC (set))
 713                    ? REGNO (SET_SRC (set)) : -1);
 714       dst_regno = (set != NULL_RTX && REG_P (SET_DEST (set))
 715                    ? REGNO (SET_DEST (set)) : -1);
 716       if (complete_info_p
 717           && src_regno >= 0 && dst_regno >= 0
 718           /* Check that source regno does not conflict with
 719              destination regno to exclude most impossible
 720              preferences.  */
 721           && (((src_regno >= FIRST_PSEUDO_REGISTER
 722                 && (! sparseset_bit_p (pseudos_live, src_regno)
 723                     || (dst_regno >= FIRST_PSEUDO_REGISTER
 724                         && lra_reg_val_equal_p (src_regno,
 725                                                 lra_reg_info[dst_regno].val,
 726                                                 lra_reg_info[dst_regno].offset))))
 727                || (src_regno < FIRST_PSEUDO_REGISTER
 728                    && ! TEST_HARD_REG_BIT (hard_regs_live, src_regno)))
 729               /* It might be 'inheritance pseudo <- reload pseudo'.  */
 730               || (src_regno >= lra_constraint_new_regno_start
 731                   && dst_regno >= lra_constraint_new_regno_start
 732                   /* Remember to skip special cases where src/dest regnos are
 733                      the same, e.g. insn SET pattern has matching constraints
 734                      like =r,0.  */
 735                   && src_regno != dst_regno)))
 736         {
 737           int hard_regno = -1, regno = -1;
 738
 739           if (dst_regno >= lra_constraint_new_regno_start
 740               && src_regno >= lra_constraint_new_regno_start)
 741             {
 742               /* It might be still an original (non-reload) insn with
 743                  one unused output and a constraint requiring to use
 744                  the same reg for input/output operands. In this case
 745                  dst_regno and src_regno have the same value, we don't
 746                  need a misleading copy for this case.  */
 747               if (dst_regno != src_regno)
 748                 lra_create_copy (dst_regno, src_regno, freq);
 749             }
 750           else if (dst_regno >= lra_constraint_new_regno_start)
 751             {
 752               if ((hard_regno = src_regno) >= FIRST_PSEUDO_REGISTER)
 753                 hard_regno = reg_renumber[src_regno];
 754               regno = dst_regno;
 755             }
 756           else if (src_regno >= lra_constraint_new_regno_start)
 757             {
 758               if ((hard_regno = dst_regno) >= FIRST_PSEUDO_REGISTER)
 759                 hard_regno = reg_renumber[dst_regno];
 760               regno = src_regno;
 761             }
 762           if (regno >= 0 && hard_regno >= 0)
 763             lra_setup_reload_pseudo_preferenced_hard_reg
 764               (regno, hard_regno, freq);
 765         }
 766
 767       sparseset_clear (start_living);
 768
 769       /* Try to avoid unnecessary program point increments, this saves
 770          a lot of time in remove_some_program_points_and_update_live_ranges.
 771          We only need an increment if something becomes live or dies at this
 772          program point.  */
 773       need_curr_point_incr = false;
 774
 775       /* Mark each defined value as live.  We need to do this for
 776          unused values because they still conflict with quantities
 777          that are live at the time of the definition.  */
 778       for (reg = curr_id->regs; reg != NULL; reg = reg->next)
 779         if (reg->type != OP_IN)
 780           {
 781             need_curr_point_incr
 782               |= mark_regno_live (reg->regno, reg->biggest_mode,
 783                                   curr_point);
 784             check_pseudos_live_through_calls (reg->regno);
 785           }
 786
 787       for (reg = curr_static_id->hard_regs; reg != NULL; reg = reg->next)
 788         if (reg->type != OP_IN)
 789           make_hard_regno_born (reg->regno, false);
 790
 791       if (curr_id->arg_hard_regs != NULL)
 792         for (i = 0; (regno = curr_id->arg_hard_regs[i]) >= 0; i++)
 793           if (regno >= FIRST_PSEUDO_REGISTER)
 794             /* It is a clobber.  */
 795             make_hard_regno_born (regno - FIRST_PSEUDO_REGISTER, false);
 796
 797       sparseset_copy (unused_set, start_living);
 798
 799       sparseset_clear (start_dying);
 800
 801       /* See which defined values die here.  */
 802       for (reg = curr_id->regs; reg != NULL; reg = reg->next)
 803         if (reg->type == OP_OUT && ! reg->early_clobber && ! reg->subreg_p)
 804           need_curr_point_incr
 805             |= mark_regno_dead (reg->regno, reg->biggest_mode,
 806                                 curr_point);
 807
 808       for (reg = curr_static_id->hard_regs; reg != NULL; reg = reg->next)
 809         if (reg->type == OP_OUT && ! reg->early_clobber && ! reg->subreg_p)
 810           make_hard_regno_dead (reg->regno);
 811
 812       if (curr_id->arg_hard_regs != NULL)
 813         for (i = 0; (regno = curr_id->arg_hard_regs[i]) >= 0; i++)
 814           if (regno >= FIRST_PSEUDO_REGISTER)
 815             /* It is a clobber.  */
 816             make_hard_regno_dead (regno - FIRST_PSEUDO_REGISTER);
 817
 818       if (call_p)
 819         {
 820           if (flag_ipa_ra)
 821             {
 822               HARD_REG_SET this_call_used_reg_set;
 823               get_call_reg_set_usage (curr_insn, &this_call_used_reg_set,
 824                                       call_used_reg_set);
 825
 826               EXECUTE_IF_SET_IN_SPARSESET (pseudos_live, j)
 827                 IOR_HARD_REG_SET (lra_reg_info[j].actual_call_used_reg_set,
 828                                   this_call_used_reg_set);
 829             }
 830
 831           sparseset_ior (pseudos_live_through_calls,
 832                          pseudos_live_through_calls, pseudos_live);
 833           if (cfun->has_nonlocal_label
 834               || find_reg_note (curr_insn, REG_SETJMP,
 835                                 NULL_RTX) != NULL_RTX)
 836             sparseset_ior (pseudos_live_through_setjumps,
 837                            pseudos_live_through_setjumps, pseudos_live);
 838         }
 839
 840       /* Increment the current program point if we must.  */
 841       if (need_curr_point_incr)
 842         next_program_point (curr_point, freq);
 843
 844       sparseset_clear (start_living);
 845
 846       need_curr_point_incr = false;
 847
 848       /* Mark each used value as live.  */
 849       for (reg = curr_id->regs; reg != NULL; reg = reg->next)
 850         if (reg->type == OP_IN)
 851           {
 852             need_curr_point_incr
 853               |= mark_regno_live (reg->regno, reg->biggest_mode,
 854                                   curr_point);
 855             check_pseudos_live_through_calls (reg->regno);
 856           }
 857
 858       for (reg = curr_static_id->hard_regs; reg != NULL; reg = reg->next)
 859         if (reg->type == OP_IN)
 860           make_hard_regno_born (reg->regno, false);
 861
 862       if (curr_id->arg_hard_regs != NULL)
 863         /* Make argument hard registers live.  Don't create conflict
 864            of used REAL_PIC_OFFSET_TABLE_REGNUM and the pic pseudo.  */
 865         for (i = 0; (regno = curr_id->arg_hard_regs[i]) >= 0; i++)
 866           if (regno < FIRST_PSEUDO_REGISTER)
 867             make_hard_regno_born (regno, true);
 868
 869       sparseset_and_compl (dead_set, start_living, start_dying);
 870
 871       /* Mark early clobber outputs dead.  */
 872       for (reg = curr_id->regs; reg != NULL; reg = reg->next)
 873         if (reg->type == OP_OUT && reg->early_clobber && ! reg->subreg_p)
 874           need_curr_point_incr
 875             |= mark_regno_dead (reg->regno, reg->biggest_mode,
 876                                 curr_point);
 877
 878       for (reg = curr_static_id->hard_regs; reg != NULL; reg = reg->next)
 879         if (reg->type == OP_OUT && reg->early_clobber && ! reg->subreg_p)
 880           make_hard_regno_dead (reg->regno);
 881
 882       if (need_curr_point_incr)
 883         next_program_point (curr_point, freq);
 884
 885       /* Update notes.  */
 886       for (link_loc = &REG_NOTES (curr_insn); (link = *link_loc) != NULL_RTX;)
 887         {
 888           if (REG_NOTE_KIND (link) != REG_DEAD
 889               && REG_NOTE_KIND (link) != REG_UNUSED)
 890             ;
 891           else if (REG_P (XEXP (link, 0)))
 892             {
 893               regno = REGNO (XEXP (link, 0));
 894               if ((REG_NOTE_KIND (link) == REG_DEAD
 895                    && ! sparseset_bit_p (dead_set, regno))
 896                   || (REG_NOTE_KIND (link) == REG_UNUSED
 897                       && ! sparseset_bit_p (unused_set, regno)))
 898                 {
 899                   *link_loc = XEXP (link, 1);
 900                   continue;
 901                 }
 902               if (REG_NOTE_KIND (link) == REG_DEAD)
 903                 sparseset_clear_bit (dead_set, regno);
 904               else if (REG_NOTE_KIND (link) == REG_UNUSED)
 905                 sparseset_clear_bit (unused_set, regno);
 906             }
 907           link_loc = &XEXP (link, 1);
 908         }
 909       EXECUTE_IF_SET_IN_SPARSESET (dead_set, j)
 910         add_reg_note (curr_insn, REG_DEAD, regno_reg_rtx[j]);
 911       EXECUTE_IF_SET_IN_SPARSESET (unused_set, j)
 912         add_reg_note (curr_insn, REG_UNUSED, regno_reg_rtx[j]);
 913     }
 914
 915   if (bb_has_eh_pred (bb))
 916     for (j = 0; ; ++j)
 917       {
 918         unsigned int regno = EH_RETURN_DATA_REGNO (j);
 919
 920         if (regno == INVALID_REGNUM)
 921           break;
 922         make_hard_regno_born (regno, false);
 923       }
 924
 925   /* Pseudos can't go in stack regs at the start of a basic block that
 926      is reached by an abnormal edge. Likewise for call clobbered regs,
 927      because caller-save, fixup_abnormal_edges and possibly the table
 928      driven EH machinery are not quite ready to handle such pseudos
 929      live across such edges.  */
 930   if (bb_has_abnormal_pred (bb))
 931     {
 932 #ifdef STACK_REGS
 933       EXECUTE_IF_SET_IN_SPARSESET (pseudos_live, px)
 934         lra_reg_info[px].no_stack_p = true;
 935       for (px = FIRST_STACK_REG; px <= LAST_STACK_REG; px++)
 936         make_hard_regno_born (px, false);
 937 #endif
 938       /* No need to record conflicts for call clobbered regs if we
 939          have nonlocal labels around, as we don't ever try to
 940          allocate such regs in this case.  */
 941       if (!cfun->has_nonlocal_label
 942           && has_abnormal_call_or_eh_pred_edge_p (bb))
 943         for (px = 0; px < FIRST_PSEUDO_REGISTER; px++)
 944           if (call_used_regs[px]
 945 #ifdef REAL_PIC_OFFSET_TABLE_REGNUM
 946               /* We should create a conflict of PIC pseudo with PIC
 947                  hard reg as PIC hard reg can have a wrong value after
 948                  jump described by the abnormal edge.  In this case we
 949                  can not allocate PIC hard reg to PIC pseudo as PIC
 950                  pseudo will also have a wrong value.  */
 951               || (px == REAL_PIC_OFFSET_TABLE_REGNUM
 952                   && pic_offset_table_rtx != NULL_RTX
 953                   && REGNO (pic_offset_table_rtx) >= FIRST_PSEUDO_REGISTER)
 954 #endif
 955               )
 956             make_hard_regno_born (px, false);
 957     }
 958
 959   bool live_change_p = false;
 960   /* Check if bb border live info was changed.  */
 961   unsigned int live_pseudos_num = 0;
 962   EXECUTE_IF_SET_IN_BITMAP (df_get_live_in (bb),
 963                             FIRST_PSEUDO_REGISTER, j, bi)
 964     {
 965       live_pseudos_num++;
 966       if (! sparseset_bit_p (pseudos_live, j))
 967         {
 968           live_change_p = true;
 969           if (lra_dump_file != NULL)
 970             fprintf (lra_dump_file,
 971                      "  r%d is removed as live at bb%d start\n", j, bb->index);
 972           break;
 973         }
 974     }
 975   if (! live_change_p
 976       && sparseset_cardinality (pseudos_live) != live_pseudos_num)
 977     {
 978       live_change_p = true;
 979       if (lra_dump_file != NULL)
 980         EXECUTE_IF_SET_IN_SPARSESET (pseudos_live, j)
 981           if (! bitmap_bit_p (df_get_live_in (bb), j))
 982             fprintf (lra_dump_file,
 983                      "  r%d is added to live at bb%d start\n", j, bb->index);
 984     }
 985   /* See if we'll need an increment at the end of this basic block.
 986      An increment is needed if the PSEUDOS_LIVE set is not empty,
 987      to make sure the finish points are set up correctly.  */
 988   need_curr_point_incr = (sparseset_cardinality (pseudos_live) > 0);
 989
 990   EXECUTE_IF_SET_IN_SPARSESET (pseudos_live, i)
 991     mark_pseudo_dead (i, curr_point);
 992
 993   EXECUTE_IF_SET_IN_BITMAP (df_get_live_in (bb), FIRST_PSEUDO_REGISTER, j, bi)
 994     {
 995       if (sparseset_cardinality (pseudos_live_through_calls) == 0)
 996         break;
 997       if (sparseset_bit_p (pseudos_live_through_calls, j))
 998         check_pseudos_live_through_calls (j);
 999     }
1000
1001   if (need_curr_point_incr)
1002     next_program_point (curr_point, freq);
1003
1004   return live_change_p;
1005 }
1006
1007 /* Compress pseudo live ranges by removing program points where
1008    nothing happens.  Complexity of many algorithms in LRA is linear
1009    function of program points number.  To speed up the code we try to
1010    minimize the number of the program points here.  */
1011 static void
1012 remove_some_program_points_and_update_live_ranges (void)
1013 {
1014   unsigned i;
1015   int n, max_regno;
1016   int *map;
1017   lra_live_range_t r, prev_r, next_r;
1018   sbitmap born_or_dead, born, dead;
1019   sbitmap_iterator sbi;
1020   bool born_p, dead_p, prev_born_p, prev_dead_p;
1021
1022   born = sbitmap_alloc (lra_live_max_point);
1023   dead = sbitmap_alloc (lra_live_max_point);
1024   bitmap_clear (born);
1025   bitmap_clear (dead);
1026   max_regno = max_reg_num ();
1027   for (i = FIRST_PSEUDO_REGISTER; i < (unsigned) max_regno; i++)
1028     {
1029       for (r = lra_reg_info[i].live_ranges; r != NULL; r = r->next)
1030         {
1031           lra_assert (r->start <= r->finish);
1032           bitmap_set_bit (born, r->start);
1033           bitmap_set_bit (dead, r->finish);
1034         }
1035     }
1036   born_or_dead = sbitmap_alloc (lra_live_max_point);
1037   bitmap_ior (born_or_dead, born, dead);
1038   map = XCNEWVEC (int, lra_live_max_point);
1039   n = -1;
1040   prev_born_p = prev_dead_p = false;
1041   EXECUTE_IF_SET_IN_BITMAP (born_or_dead, 0, i, sbi)
1042     {
1043       born_p = bitmap_bit_p (born, i);
1044       dead_p = bitmap_bit_p (dead, i);
1045       if ((prev_born_p && ! prev_dead_p && born_p && ! dead_p)
1046           || (prev_dead_p && ! prev_born_p && dead_p && ! born_p))
1047         {
1048           map[i] = n;
1049           lra_point_freq[n] = MAX (lra_point_freq[n], lra_point_freq[i]);
1050         }
1051       else
1052         {
1053           map[i] = ++n;
1054           lra_point_freq[n] = lra_point_freq[i];
1055         }
1056       prev_born_p = born_p;
1057       prev_dead_p = dead_p;
1058     }
1059   sbitmap_free (born_or_dead);
1060   sbitmap_free (born);
1061   sbitmap_free (dead);
1062   n++;
1063   if (lra_dump_file != NULL)
1064     fprintf (lra_dump_file, "Compressing live ranges: from %d to %d - %d%%\n",
1065              lra_live_max_point, n, 100 * n / lra_live_max_point);
1066   if (n < lra_live_max_point)
1067     {
1068       lra_live_max_point = n;
1069       for (i = FIRST_PSEUDO_REGISTER; i < (unsigned) max_regno; i++)
1070         {
1071           for (prev_r = NULL, r = lra_reg_info[i].live_ranges;
1072                r != NULL;
1073                r = next_r)
1074             {
1075               next_r = r->next;
1076               r->start = map[r->start];
1077               r->finish = map[r->finish];
1078               if (prev_r == NULL || prev_r->start > r->finish + 1)
1079                 {
1080                   prev_r = r;
1081                   continue;
1082                 }
1083               prev_r->start = r->start;
1084               prev_r->next = next_r;
1085               lra_live_range_pool.remove (r);
1086             }
1087         }
1088     }
1089   free (map);
1090 }
1091
1092 /* Print live ranges R to file F.  */
1093 void
1094 lra_print_live_range_list (FILE *f, lra_live_range_t r)
1095 {
1096   for (; r != NULL; r = r->next)
1097     fprintf (f, " [%d..%d]", r->start, r->finish);
1098   fprintf (f, "\n");
1099 }
1100
1101 DEBUG_FUNCTION void
1102 debug (lra_live_range &ref)
1103 {
1104   lra_print_live_range_list (stderr, &ref);
1105 }
1106
1107 DEBUG_FUNCTION void
1108 debug (lra_live_range *ptr)
1109 {
1110   if (ptr)
1111     debug (*ptr);
1112   else
1113     fprintf (stderr, "<nil>\n");
1114 }
1115
1116 /* Print live ranges R to stderr.  */
1117 void
1118 lra_debug_live_range_list (lra_live_range_t r)
1119 {
1120   lra_print_live_range_list (stderr, r);
1121 }
1122
1123 /* Print live ranges of pseudo REGNO to file F.  */
1124 static void
1125 print_pseudo_live_ranges (FILE *f, int regno)
1126 {
1127   if (lra_reg_info[regno].live_ranges == NULL)
1128     return;
1129   fprintf (f, " r%d:", regno);
1130   lra_print_live_range_list (f, lra_reg_info[regno].live_ranges);
1131 }
1132
1133 /* Print live ranges of pseudo REGNO to stderr.  */
1134 void
1135 lra_debug_pseudo_live_ranges (int regno)
1136 {
1137   print_pseudo_live_ranges (stderr, regno);
1138 }
1139
1140 /* Print live ranges of all pseudos to file F.  */
1141 static void
1142 print_live_ranges (FILE *f)
1143 {
1144   int i, max_regno;
1145
1146   max_regno = max_reg_num ();
1147   for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
1148     print_pseudo_live_ranges (f, i);
1149 }
1150
1151 /* Print live ranges of all pseudos to stderr.  */
1152 void
1153 lra_debug_live_ranges (void)
1154 {
1155   print_live_ranges (stderr);
1156 }
1157
1158 /* Compress pseudo live ranges.  */
1159 static void
1160 compress_live_ranges (void)
1161 {
1162   remove_some_program_points_and_update_live_ranges ();
1163   if (lra_dump_file != NULL)
1164     {
1165       fprintf (lra_dump_file, "Ranges after the compression:\n");
1166       print_live_ranges (lra_dump_file);
1167     }
1168 }
1169
1170 \f
1171
1172 /* The number of the current live range pass.  */
1173 int lra_live_range_iter;
1174
1175 /* The function creates live ranges only for memory pseudos (or for
1176    all ones if ALL_P), set up CONFLICT_HARD_REGS for the pseudos.  It
1177    also does dead insn elimination if DEAD_INSN_P and global live
1178    analysis only for pseudos and only if the pseudo live info was
1179    changed on a BB border.  Return TRUE if the live info was
1180    changed.  */
1181 static bool
1182 lra_create_live_ranges_1 (bool all_p, bool dead_insn_p)
1183 {
1184   basic_block bb;
1185   int i, hard_regno, max_regno = max_reg_num ();
1186   int curr_point;
1187   bool bb_live_change_p, have_referenced_pseudos = false;
1188
1189   timevar_push (TV_LRA_CREATE_LIVE_RANGES);
1190
1191   complete_info_p = all_p;
1192   if (lra_dump_file != NULL)
1193     fprintf (lra_dump_file,
1194              "\n********** Pseudo live ranges #%d: **********\n\n",
1195              ++lra_live_range_iter);
1196   memset (lra_hard_reg_usage, 0, sizeof (lra_hard_reg_usage));
1197   for (i = 0; i < max_regno; i++)
1198     {
1199       lra_reg_info[i].live_ranges = NULL;
1200       CLEAR_HARD_REG_SET (lra_reg_info[i].conflict_hard_regs);
1201       lra_reg_info[i].preferred_hard_regno1 = -1;
1202       lra_reg_info[i].preferred_hard_regno2 = -1;
1203       lra_reg_info[i].preferred_hard_regno_profit1 = 0;
1204       lra_reg_info[i].preferred_hard_regno_profit2 = 0;
1205 #ifdef STACK_REGS
1206       lra_reg_info[i].no_stack_p = false;
1207 #endif
1208       /* The biggest mode is already set but its value might be to
1209          conservative because of recent transformation.  Here in this
1210          file we recalculate it again as it costs practically
1211          nothing.  */
1212       if (i >= FIRST_PSEUDO_REGISTER && regno_reg_rtx[i] != NULL_RTX)
1213         lra_reg_info[i].biggest_mode = GET_MODE (regno_reg_rtx[i]);
1214       else
1215         lra_reg_info[i].biggest_mode = VOIDmode;
1216       lra_reg_info[i].call_p = false;
1217       if (i >= FIRST_PSEUDO_REGISTER
1218           && lra_reg_info[i].nrefs != 0)
1219         {
1220           if ((hard_regno = reg_renumber[i]) >= 0)
1221             lra_hard_reg_usage[hard_regno] += lra_reg_info[i].freq;
1222           have_referenced_pseudos = true;
1223         }
1224     }
1225   lra_free_copies ();
1226
1227   /* Under some circumstances, we can have functions without pseudo
1228      registers.  For such functions, lra_live_max_point will be 0,
1229      see e.g. PR55604, and there's nothing more to do for us here.  */
1230   if (! have_referenced_pseudos)
1231     {
1232       timevar_pop (TV_LRA_CREATE_LIVE_RANGES);
1233       return false;
1234     }
1235
1236   pseudos_live = sparseset_alloc (max_regno);
1237   pseudos_live_through_calls = sparseset_alloc (max_regno);
1238   pseudos_live_through_setjumps = sparseset_alloc (max_regno);
1239   start_living = sparseset_alloc (max_regno);
1240   start_dying = sparseset_alloc (max_regno);
1241   dead_set = sparseset_alloc (max_regno);
1242   unused_set = sparseset_alloc (max_regno);
1243   curr_point = 0;
1244   unsigned new_length = get_max_uid () * 2;
1245   point_freq_vec.truncate (0);
1246   point_freq_vec.reserve_exact (new_length);
1247   lra_point_freq = point_freq_vec.address ();
1248   int *post_order_rev_cfg = XNEWVEC (int, last_basic_block_for_fn (cfun));
1249   int n_blocks_inverted = inverted_post_order_compute (post_order_rev_cfg);
1250   lra_assert (n_blocks_inverted == n_basic_blocks_for_fn (cfun));
1251   bb_live_change_p = false;
1252   for (i = n_blocks_inverted - 1; i >= 0; --i)
1253     {
1254       bb = BASIC_BLOCK_FOR_FN (cfun, post_order_rev_cfg[i]);
1255       if (bb == EXIT_BLOCK_PTR_FOR_FN (cfun) || bb
1256           == ENTRY_BLOCK_PTR_FOR_FN (cfun))
1257         continue;
1258       if (process_bb_lives (bb, curr_point, dead_insn_p))
1259         bb_live_change_p = true;
1260     }
1261   if (bb_live_change_p)
1262     {
1263       /* We need to clear pseudo live info as some pseudos can
1264          disappear, e.g. pseudos with used equivalences.  */
1265       FOR_EACH_BB_FN (bb, cfun)
1266         {
1267           bitmap_clear_range (df_get_live_in (bb), FIRST_PSEUDO_REGISTER,
1268                               max_regno - FIRST_PSEUDO_REGISTER);
1269           bitmap_clear_range (df_get_live_out (bb), FIRST_PSEUDO_REGISTER,
1270                               max_regno - FIRST_PSEUDO_REGISTER);
1271         }
1272       /* As we did not change CFG since LRA start we can use
1273          DF-infrastructure solver to solve live data flow problem.  */
1274       df_simple_dataflow
1275         (DF_BACKWARD, NULL, live_con_fun_0, live_con_fun_n,
1276          live_trans_fun, &all_blocks,
1277          df_get_postorder (DF_BACKWARD), df_get_n_blocks (DF_BACKWARD));
1278       if (lra_dump_file != NULL)
1279         {
1280           fprintf (lra_dump_file,
1281                    "Global pseudo live data have been updated:\n");
1282           basic_block bb;
1283           FOR_EACH_BB_FN (bb, cfun)
1284             {
1285               bb_data_t bb_info = get_bb_data (bb);
1286               bitmap bb_livein = df_get_live_in (bb);
1287               bitmap bb_liveout = df_get_live_out (bb);
1288
1289               fprintf (lra_dump_file, "\nBB %d:\n", bb->index);
1290               lra_dump_bitmap_with_title ("  gen:",
1291                                           &bb_info->gen_pseudos, bb->index);
1292               lra_dump_bitmap_with_title ("  killed:",
1293                                           &bb_info->killed_pseudos, bb->index);
1294               lra_dump_bitmap_with_title ("  livein:", bb_livein, bb->index);
1295               lra_dump_bitmap_with_title ("  liveout:", bb_liveout, bb->index);
1296             }
1297         }
1298     }
1299   free (post_order_rev_cfg);
1300   lra_live_max_point = curr_point;
1301   if (lra_dump_file != NULL)
1302     print_live_ranges (lra_dump_file);
1303   /* Clean up.  */
1304   sparseset_free (unused_set);
1305   sparseset_free (dead_set);
1306   sparseset_free (start_dying);
1307   sparseset_free (start_living);
1308   sparseset_free (pseudos_live_through_calls);
1309   sparseset_free (pseudos_live_through_setjumps);
1310   sparseset_free (pseudos_live);
1311   compress_live_ranges ();
1312   timevar_pop (TV_LRA_CREATE_LIVE_RANGES);
1313   return bb_live_change_p;
1314 }
1315
1316 /* The main entry function creates live-ranges and other live info
1317    necessary for the assignment sub-pass.  It uses
1318    lra_creates_live_ranges_1 -- so read comments for the
1319    function.  */
1320 void
1321 lra_create_live_ranges (bool all_p, bool dead_insn_p)
1322 {
1323   if (! lra_create_live_ranges_1 (all_p, dead_insn_p))
1324     return;
1325   if (lra_dump_file != NULL)
1326     fprintf (lra_dump_file, "Live info was changed -- recalculate it\n");
1327   /* Live info was changed on a bb border.  It means that some info,
1328      e.g. about conflict regs, calls crossed, and live ranges may be
1329      wrong.  We need this info for allocation.  So recalculate it
1330      again but without removing dead insns which can change live info
1331      again.  Repetitive live range calculations are expensive therefore
1332      we stop here as we already have correct info although some
1333      improvement in rare cases could be possible on this sub-pass if
1334      we do dead insn elimination again (still the improvement may
1335      happen later).  */
1336   lra_clear_live_ranges ();
1337   bool res = lra_create_live_ranges_1 (all_p, false);
1338   lra_assert (! res);
1339 }
1340
1341 /* Finish all live ranges.  */
1342 void
1343 lra_clear_live_ranges (void)
1344 {
1345   int i;
1346
1347   for (i = 0; i < max_reg_num (); i++)
1348     free_live_range_list (lra_reg_info[i].live_ranges);
1349   point_freq_vec.release ();
1350 }
1351
1352 /* Initialize live ranges data once per function.  */
1353 void
1354 lra_live_ranges_init (void)
1355 {
1356   bitmap_initialize (&temp_bitmap, &reg_obstack);
1357   initiate_live_solver ();
1358 }
1359
1360 /* Finish live ranges data once per function.  */
1361 void
1362 lra_live_ranges_finish (void)
1363 {
1364   finish_live_solver ();
1365   bitmap_clear (&temp_bitmap);
1366   lra_live_range_pool.release ();
1367 }