gcc/lra-lives.c

   1 /* Build live ranges for pseudos.
   2    Copyright (C) 2010-2013 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 "tm.h"
  32 #include "hard-reg-set.h"
  33 #include "rtl.h"
  34 #include "tm_p.h"
  35 #include "insn-config.h"
  36 #include "recog.h"
  37 #include "output.h"
  38 #include "regs.h"
  39 #include "function.h"
  40 #include "expr.h"
  41 #include "basic-block.h"
  42 #include "except.h"
  43 #include "df.h"
  44 #include "ira.h"
  45 #include "sparseset.h"
  46 #include "lra-int.h"
  47
  48 /* Program points are enumerated by numbers from range
  49    0..LRA_LIVE_MAX_POINT-1.  There are approximately two times more
  50    program points than insns.  Program points are places in the
  51    program where liveness info can be changed.  In most general case
  52    (there are more complicated cases too) some program points
  53    correspond to places where input operand dies and other ones
  54    correspond to places where output operands are born.  */
  55 int lra_live_max_point;
  56
  57 /* Accumulated execution frequency of all references for each hard
  58    register.  */
  59 int lra_hard_reg_usage[FIRST_PSEUDO_REGISTER];
  60
  61 /* A global flag whose true value says to build live ranges for all
  62    pseudos, otherwise the live ranges only for pseudos got memory is
  63    build.  True value means also building copies and setting up hard
  64    register preferences.  The complete info is necessary only for the
  65    assignment pass.  The complete info is not needed for the
  66    coalescing and spill passes.  */
  67 static bool complete_info_p;
  68
  69 /* Pseudos live at current point in the RTL scan.  */
  70 static sparseset pseudos_live;
  71
  72 /* Pseudos probably living through calls and setjumps.  As setjump is
  73    a call too, if a bit in PSEUDOS_LIVE_THROUGH_SETJUMPS is set up
  74    then the corresponding bit in PSEUDOS_LIVE_THROUGH_CALLS is set up
  75    too.  These data are necessary for cases when only one subreg of a
  76    multi-reg pseudo is set up after a call.  So we decide it is
  77    probably live when traversing bb backward.  We are sure about
  78    living when we see its usage or definition of the pseudo.  */
  79 static sparseset pseudos_live_through_calls;
  80 static sparseset pseudos_live_through_setjumps;
  81
  82 /* Set of hard regs (except eliminable ones) currently live.  */
  83 static HARD_REG_SET hard_regs_live;
  84
  85 /* Set of pseudos and hard registers start living/dying in the current
  86    insn.  These sets are used to update REG_DEAD and REG_UNUSED notes
  87    in the insn.  */
  88 static sparseset start_living, start_dying;
  89
  90 /* Set of pseudos and hard regs dead and unused in the current
  91    insn.  */
  92 static sparseset unused_set, dead_set;
  93
  94 /* Pool for pseudo live ranges.  */
  95 static alloc_pool live_range_pool;
  96
  97 /* Free live range LR.  */
  98 static void
  99 free_live_range (lra_live_range_t lr)
 100 {
 101   pool_free (live_range_pool, lr);
 102 }
 103
 104 /* Free live range list LR.  */
 105 static void
 106 free_live_range_list (lra_live_range_t lr)
 107 {
 108   lra_live_range_t next;
 109
 110   while (lr != NULL)
 111     {
 112       next = lr->next;
 113       free_live_range (lr);
 114       lr = next;
 115     }
 116 }
 117
 118 /* Create and return pseudo live range with given attributes.  */
 119 static lra_live_range_t
 120 create_live_range (int regno, int start, int finish, lra_live_range_t next)
 121 {
 122   lra_live_range_t p;
 123
 124   p = (lra_live_range_t) pool_alloc (live_range_pool);
 125   p->regno = regno;
 126   p->start = start;
 127   p->finish = finish;
 128   p->next = next;
 129   return p;
 130 }
 131
 132 /* Copy live range R and return the result.  */
 133 static lra_live_range_t
 134 copy_live_range (lra_live_range_t r)
 135 {
 136   lra_live_range_t p;
 137
 138   p = (lra_live_range_t) pool_alloc (live_range_pool);
 139   *p = *r;
 140   return p;
 141 }
 142
 143 /* Copy live range list given by its head R and return the result.  */
 144 lra_live_range_t
 145 lra_copy_live_range_list (lra_live_range_t r)
 146 {
 147   lra_live_range_t p, first, *chain;
 148
 149   first = NULL;
 150   for (chain = &first; r != NULL; r = r->next)
 151     {
 152       p = copy_live_range (r);
 153       *chain = p;
 154       chain = &p->next;
 155     }
 156   return first;
 157 }
 158
 159 /* Merge *non-intersected* ranges R1 and R2 and returns the result.
 160    The function maintains the order of ranges and tries to minimize
 161    size of the result range list.  Ranges R1 and R2 may not be used
 162    after the call.  */
 163 lra_live_range_t
 164 lra_merge_live_ranges (lra_live_range_t r1, lra_live_range_t r2)
 165 {
 166   lra_live_range_t first, last, temp;
 167
 168   if (r1 == NULL)
 169     return r2;
 170   if (r2 == NULL)
 171     return r1;
 172   for (first = last = NULL; r1 != NULL && r2 != NULL;)
 173     {
 174       if (r1->start < r2->start)
 175         {
 176           temp = r1;
 177           r1 = r2;
 178           r2 = temp;
 179         }
 180       if (r1->start == r2->finish + 1)
 181         {
 182           /* Joint ranges: merge r1 and r2 into r1.  */
 183           r1->start = r2->start;
 184           temp = r2;
 185           r2 = r2->next;
 186           pool_free (live_range_pool, temp);
 187         }
 188       else
 189         {
 190           gcc_assert (r2->finish + 1 < r1->start);
 191           /* Add r1 to the result.  */
 192           if (first == NULL)
 193             first = last = r1;
 194           else
 195             {
 196               last->next = r1;
 197               last = r1;
 198             }
 199           r1 = r1->next;
 200         }
 201     }
 202   if (r1 != NULL)
 203     {
 204       if (first == NULL)
 205         first = r1;
 206       else
 207         last->next = r1;
 208     }
 209   else
 210     {
 211       lra_assert (r2 != NULL);
 212       if (first == NULL)
 213         first = r2;
 214       else
 215         last->next = r2;
 216     }
 217   return first;
 218 }
 219
 220 /* Return TRUE if live ranges R1 and R2 intersect.  */
 221 bool
 222 lra_intersected_live_ranges_p (lra_live_range_t r1, lra_live_range_t r2)
 223 {
 224   /* Remember the live ranges are always kept ordered.  */
 225   while (r1 != NULL && r2 != NULL)
 226     {
 227       if (r1->start > r2->finish)
 228         r1 = r1->next;
 229       else if (r2->start > r1->finish)
 230         r2 = r2->next;
 231       else
 232         return true;
 233     }
 234   return false;
 235 }
 236
 237 /* The function processing birth of hard register REGNO.  It updates
 238    living hard regs, conflict hard regs for living pseudos, and
 239    START_LIVING.  */
 240 static void
 241 make_hard_regno_born (int regno)
 242 {
 243   unsigned int i;
 244
 245   lra_assert (regno < FIRST_PSEUDO_REGISTER);
 246   if (TEST_HARD_REG_BIT (lra_no_alloc_regs, regno)
 247       || TEST_HARD_REG_BIT (hard_regs_live, regno))
 248     return;
 249   SET_HARD_REG_BIT (hard_regs_live, regno);
 250   sparseset_set_bit (start_living, regno);
 251   EXECUTE_IF_SET_IN_SPARSESET (pseudos_live, i)
 252     SET_HARD_REG_BIT (lra_reg_info[i].conflict_hard_regs, regno);
 253 }
 254
 255 /* Process the death of hard register REGNO.  This updates
 256    hard_regs_live and START_DYING.  */
 257 static void
 258 make_hard_regno_dead (int regno)
 259 {
 260   lra_assert (regno < FIRST_PSEUDO_REGISTER);
 261   if (TEST_HARD_REG_BIT (lra_no_alloc_regs, regno)
 262       || ! TEST_HARD_REG_BIT (hard_regs_live, regno))
 263     return;
 264   sparseset_set_bit (start_dying, regno);
 265   CLEAR_HARD_REG_BIT (hard_regs_live, regno);
 266 }
 267
 268 /* Mark pseudo REGNO as living at program point POINT, update conflicting
 269    hard registers of the pseudo and START_LIVING, and start a new live
 270    range for the pseudo corresponding to REGNO if it is necessary.  */
 271 static void
 272 mark_pseudo_live (int regno, int point)
 273 {
 274   lra_live_range_t p;
 275
 276   lra_assert (regno >= FIRST_PSEUDO_REGISTER);
 277   lra_assert (! sparseset_bit_p (pseudos_live, regno));
 278   sparseset_set_bit (pseudos_live, regno);
 279   IOR_HARD_REG_SET (lra_reg_info[regno].conflict_hard_regs, hard_regs_live);
 280
 281   if ((complete_info_p || lra_get_regno_hard_regno (regno) < 0)
 282       && ((p = lra_reg_info[regno].live_ranges) == NULL
 283           || (p->finish != point && p->finish + 1 != point)))
 284      lra_reg_info[regno].live_ranges
 285        = create_live_range (regno, point, -1, p);
 286   sparseset_set_bit (start_living, regno);
 287 }
 288
 289 /* Mark pseudo REGNO as not living at program point POINT and update
 290    START_DYING.
 291    This finishes the current live range for the pseudo corresponding
 292    to REGNO.  */
 293 static void
 294 mark_pseudo_dead (int regno, int point)
 295 {
 296   lra_live_range_t p;
 297
 298   lra_assert (regno >= FIRST_PSEUDO_REGISTER);
 299   lra_assert (sparseset_bit_p (pseudos_live, regno));
 300   sparseset_clear_bit (pseudos_live, regno);
 301   sparseset_set_bit (start_dying, regno);
 302   if (complete_info_p || lra_get_regno_hard_regno (regno) < 0)
 303     {
 304       p = lra_reg_info[regno].live_ranges;
 305       lra_assert (p != NULL);
 306       p->finish = point;
 307     }
 308 }
 309
 310 /* Mark register REGNO (pseudo or hard register) in MODE as live
 311    at program point POINT.
 312    Return TRUE if the liveness tracking sets were modified,
 313    or FALSE if nothing changed.  */
 314 static bool
 315 mark_regno_live (int regno, enum machine_mode mode, int point)
 316 {
 317   int last;
 318   bool changed = false;
 319
 320   if (regno < FIRST_PSEUDO_REGISTER)
 321     {
 322       for (last = regno + hard_regno_nregs[regno][mode];
 323            regno < last;
 324            regno++)
 325         make_hard_regno_born (regno);
 326     }
 327   else if (! sparseset_bit_p (pseudos_live, regno))
 328     {
 329       mark_pseudo_live (regno, point);
 330       changed = true;
 331     }
 332   return changed;
 333 }
 334
 335
 336 /* Mark register REGNO in MODE as dead at program point POINT.
 337    Return TRUE if the liveness tracking sets were modified,
 338    or FALSE if nothing changed.  */
 339 static bool
 340 mark_regno_dead (int regno, enum machine_mode mode, int point)
 341 {
 342   int last;
 343   bool changed = false;
 344
 345   if (regno < FIRST_PSEUDO_REGISTER)
 346     {
 347       for (last = regno + hard_regno_nregs[regno][mode];
 348            regno < last;
 349            regno++)
 350         make_hard_regno_dead (regno);
 351     }
 352   else if (sparseset_bit_p (pseudos_live, regno))
 353     {
 354       mark_pseudo_dead (regno, point);
 355       changed = true;
 356     }
 357   return changed;
 358 }
 359
 360 /* Insn currently scanned.  */
 361 static rtx curr_insn;
 362 /* The insn data.  */
 363 static lra_insn_recog_data_t curr_id;
 364 /* The insn static data.  */
 365 static struct lra_static_insn_data *curr_static_id;
 366
 367 /* Return true when one of the predecessor edges of BB is marked with
 368    EDGE_ABNORMAL_CALL or EDGE_EH.  */
 369 static bool
 370 bb_has_abnormal_call_pred (basic_block bb)
 371 {
 372   edge e;
 373   edge_iterator ei;
 374
 375   FOR_EACH_EDGE (e, ei, bb->preds)
 376     {
 377       if (e->flags & (EDGE_ABNORMAL_CALL | EDGE_EH))
 378         return true;
 379     }
 380   return false;
 381 }
 382
 383 /* Vec containing execution frequencies of program points.  */
 384 static vec<int> point_freq_vec;
 385
 386 /* The start of the above vector elements.  */
 387 int *lra_point_freq;
 388
 389 /* Increment the current program point POINT to the next point which has
 390    execution frequency FREQ.  */
 391 static void
 392 next_program_point (int &point, int freq)
 393 {
 394   point_freq_vec.safe_push (freq);
 395   lra_point_freq = point_freq_vec.address ();
 396   point++;
 397 }
 398
 399 /* Update the preference of HARD_REGNO for pseudo REGNO by PROFIT.  */
 400 void
 401 lra_setup_reload_pseudo_preferenced_hard_reg (int regno,
 402                                               int hard_regno, int profit)
 403 {
 404   lra_assert (regno >= lra_constraint_new_regno_start);
 405   if (lra_reg_info[regno].preferred_hard_regno1 == hard_regno)
 406     lra_reg_info[regno].preferred_hard_regno_profit1 += profit;
 407   else if (lra_reg_info[regno].preferred_hard_regno2 == hard_regno)
 408     lra_reg_info[regno].preferred_hard_regno_profit2 += profit;
 409   else if (lra_reg_info[regno].preferred_hard_regno1 < 0)
 410     {
 411       lra_reg_info[regno].preferred_hard_regno1 = hard_regno;
 412       lra_reg_info[regno].preferred_hard_regno_profit1 = profit;
 413     }
 414   else if (lra_reg_info[regno].preferred_hard_regno2 < 0
 415            || profit > lra_reg_info[regno].preferred_hard_regno_profit2)
 416     {
 417       lra_reg_info[regno].preferred_hard_regno2 = hard_regno;
 418       lra_reg_info[regno].preferred_hard_regno_profit2 = profit;
 419     }
 420   else
 421     return;
 422   /* Keep the 1st hard regno as more profitable.  */
 423   if (lra_reg_info[regno].preferred_hard_regno1 >= 0
 424       && lra_reg_info[regno].preferred_hard_regno2 >= 0
 425       && (lra_reg_info[regno].preferred_hard_regno_profit2
 426           > lra_reg_info[regno].preferred_hard_regno_profit1))
 427     {
 428       int temp;
 429
 430       temp = lra_reg_info[regno].preferred_hard_regno1;
 431       lra_reg_info[regno].preferred_hard_regno1
 432         = lra_reg_info[regno].preferred_hard_regno2;
 433       lra_reg_info[regno].preferred_hard_regno2 = temp;
 434       temp = lra_reg_info[regno].preferred_hard_regno_profit1;
 435       lra_reg_info[regno].preferred_hard_regno_profit1
 436         = lra_reg_info[regno].preferred_hard_regno_profit2;
 437       lra_reg_info[regno].preferred_hard_regno_profit2 = temp;
 438     }
 439   if (lra_dump_file != NULL)
 440     {
 441       if ((hard_regno = lra_reg_info[regno].preferred_hard_regno1) >= 0)
 442         fprintf (lra_dump_file,
 443                  "      Hard reg %d is preferable by r%d with profit %d\n",
 444                  hard_regno, regno,
 445                  lra_reg_info[regno].preferred_hard_regno_profit1);
 446       if ((hard_regno = lra_reg_info[regno].preferred_hard_regno2) >= 0)
 447         fprintf (lra_dump_file,
 448                  "      Hard reg %d is preferable by r%d with profit %d\n",
 449                  hard_regno, regno,
 450                  lra_reg_info[regno].preferred_hard_regno_profit2);
 451     }
 452 }
 453
 454 /* Check that REGNO living through calls and setjumps, set up conflict
 455    regs, and clear corresponding bits in PSEUDOS_LIVE_THROUGH_CALLS and
 456    PSEUDOS_LIVE_THROUGH_SETJUMPS.  */
 457 static inline void
 458 check_pseudos_live_through_calls (int regno)
 459 {
 460   if (! sparseset_bit_p (pseudos_live_through_calls, regno))
 461     return;
 462   sparseset_clear_bit (pseudos_live_through_calls, regno);
 463   IOR_HARD_REG_SET (lra_reg_info[regno].conflict_hard_regs,
 464                     call_used_reg_set);
 465 #ifdef ENABLE_CHECKING
 466   lra_reg_info[regno].call_p = true;
 467 #endif
 468   if (! sparseset_bit_p (pseudos_live_through_setjumps, regno))
 469     return;
 470   sparseset_clear_bit (pseudos_live_through_setjumps, regno);
 471   /* Don't allocate pseudos that cross setjmps or any call, if this
 472      function receives a nonlocal goto.  */
 473   SET_HARD_REG_SET (lra_reg_info[regno].conflict_hard_regs);
 474 }
 475
 476 /* Process insns of the basic block BB to update pseudo live ranges,
 477    pseudo hard register conflicts, and insn notes.  We do it on
 478    backward scan of BB insns.  CURR_POINT is the program point where
 479    BB ends.  The function updates this counter and returns in
 480    CURR_POINT the program point where BB starts.  */
 481 static void
 482 process_bb_lives (basic_block bb, int &curr_point)
 483 {
 484   int i, regno, freq;
 485   unsigned int j;
 486   bitmap_iterator bi;
 487   bitmap reg_live_out;
 488   unsigned int px;
 489   rtx link, *link_loc;
 490   bool need_curr_point_incr;
 491
 492   reg_live_out = df_get_live_out (bb);
 493   sparseset_clear (pseudos_live);
 494   sparseset_clear (pseudos_live_through_calls);
 495   sparseset_clear (pseudos_live_through_setjumps);
 496   REG_SET_TO_HARD_REG_SET (hard_regs_live, reg_live_out);
 497   AND_COMPL_HARD_REG_SET (hard_regs_live, eliminable_regset);
 498   AND_COMPL_HARD_REG_SET (hard_regs_live, lra_no_alloc_regs);
 499   EXECUTE_IF_SET_IN_BITMAP (reg_live_out, FIRST_PSEUDO_REGISTER, j, bi)
 500     mark_pseudo_live (j, curr_point);
 501
 502   freq = REG_FREQ_FROM_BB (bb);
 503
 504   if (lra_dump_file != NULL)
 505     fprintf (lra_dump_file, "  BB %d\n", bb->index);
 506
 507   /* Scan the code of this basic block, noting which pseudos and hard
 508      regs are born or die.
 509
 510      Note that this loop treats uninitialized values as live until the
 511      beginning of the block.  For example, if an instruction uses
 512      (reg:DI foo), and only (subreg:SI (reg:DI foo) 0) is ever set,
 513      FOO will remain live until the beginning of the block.  Likewise
 514      if FOO is not set at all.  This is unnecessarily pessimistic, but
 515      it probably doesn't matter much in practice.  */
 516   FOR_BB_INSNS_REVERSE (bb, curr_insn)
 517     {
 518       bool call_p;
 519       int dst_regno, src_regno;
 520       rtx set;
 521       struct lra_insn_reg *reg;
 522
 523       if (!NONDEBUG_INSN_P (curr_insn))
 524         continue;
 525
 526       curr_id = lra_get_insn_recog_data (curr_insn);
 527       curr_static_id = curr_id->insn_static_data;
 528       if (lra_dump_file != NULL)
 529         fprintf (lra_dump_file, "   Insn %u: point = %d\n",
 530                  INSN_UID (curr_insn), curr_point);
 531
 532       /* Update max ref width and hard reg usage.  */
 533       for (reg = curr_id->regs; reg != NULL; reg = reg->next)
 534         if (reg->regno >= FIRST_PSEUDO_REGISTER
 535             && (GET_MODE_SIZE (reg->biggest_mode)
 536                 > GET_MODE_SIZE (lra_reg_info[reg->regno].biggest_mode)))
 537           lra_reg_info[reg->regno].biggest_mode = reg->biggest_mode;
 538         else if (reg->regno < FIRST_PSEUDO_REGISTER)
 539           lra_hard_reg_usage[reg->regno] += freq;
 540
 541       call_p = CALL_P (curr_insn);
 542       if (complete_info_p
 543           && (set = single_set (curr_insn)) != NULL_RTX
 544           && REG_P (SET_DEST (set)) && REG_P (SET_SRC (set))
 545           /* Check that source regno does not conflict with
 546              destination regno to exclude most impossible
 547              preferences.  */
 548           && ((((src_regno = REGNO (SET_SRC (set))) >= FIRST_PSEUDO_REGISTER
 549                 && ! sparseset_bit_p (pseudos_live, src_regno))
 550                || (src_regno < FIRST_PSEUDO_REGISTER
 551                    && ! TEST_HARD_REG_BIT (hard_regs_live, src_regno)))
 552               /* It might be 'inheritance pseudo <- reload pseudo'.  */
 553               || (src_regno >= lra_constraint_new_regno_start
 554                   && ((int) REGNO (SET_DEST (set))
 555                       >= lra_constraint_new_regno_start))))
 556         {
 557           int hard_regno = -1, regno = -1;
 558
 559           dst_regno = REGNO (SET_DEST (set));
 560           if (dst_regno >= lra_constraint_new_regno_start
 561               && src_regno >= lra_constraint_new_regno_start)
 562             lra_create_copy (dst_regno, src_regno, freq);
 563           else if (dst_regno >= lra_constraint_new_regno_start)
 564             {
 565               if ((hard_regno = src_regno) >= FIRST_PSEUDO_REGISTER)
 566                 hard_regno = reg_renumber[src_regno];
 567               regno = dst_regno;
 568             }
 569           else if (src_regno >= lra_constraint_new_regno_start)
 570             {
 571               if ((hard_regno = dst_regno) >= FIRST_PSEUDO_REGISTER)
 572                 hard_regno = reg_renumber[dst_regno];
 573               regno = src_regno;
 574             }
 575           if (regno >= 0 && hard_regno >= 0)
 576             lra_setup_reload_pseudo_preferenced_hard_reg
 577               (regno, hard_regno, freq);
 578         }
 579
 580       sparseset_clear (start_living);
 581
 582       /* Try to avoid unnecessary program point increments, this saves
 583          a lot of time in remove_some_program_points_and_update_live_ranges.
 584          We only need an increment if something becomes live or dies at this
 585          program point.  */
 586       need_curr_point_incr = false;
 587
 588       /* Mark each defined value as live.  We need to do this for
 589          unused values because they still conflict with quantities
 590          that are live at the time of the definition.  */
 591       for (reg = curr_id->regs; reg != NULL; reg = reg->next)
 592         if (reg->type != OP_IN)
 593           {
 594             need_curr_point_incr |= mark_regno_live (reg->regno,
 595                                                      reg->biggest_mode,
 596                                                      curr_point);
 597             check_pseudos_live_through_calls (reg->regno);
 598           }
 599
 600       for (reg = curr_static_id->hard_regs; reg != NULL; reg = reg->next)
 601         if (reg->type != OP_IN)
 602           make_hard_regno_born (reg->regno);
 603
 604       sparseset_copy (unused_set, start_living);
 605
 606       sparseset_clear (start_dying);
 607
 608       /* See which defined values die here.  */
 609       for (reg = curr_id->regs; reg != NULL; reg = reg->next)
 610         if (reg->type == OP_OUT && ! reg->early_clobber && ! reg->subreg_p)
 611           need_curr_point_incr |= mark_regno_dead (reg->regno,
 612                                                    reg->biggest_mode,
 613                                                    curr_point);
 614
 615       for (reg = curr_static_id->hard_regs; reg != NULL; reg = reg->next)
 616         if (reg->type == OP_OUT && ! reg->early_clobber && ! reg->subreg_p)
 617           make_hard_regno_dead (reg->regno);
 618
 619       if (call_p)
 620         {
 621           sparseset_ior (pseudos_live_through_calls,
 622                          pseudos_live_through_calls, pseudos_live);
 623           if (cfun->has_nonlocal_label
 624               || find_reg_note (curr_insn, REG_SETJMP,
 625                                 NULL_RTX) != NULL_RTX)
 626             sparseset_ior (pseudos_live_through_setjumps,
 627                            pseudos_live_through_setjumps, pseudos_live);
 628         }
 629
 630       /* Increment the current program point if we must.  */
 631       if (need_curr_point_incr)
 632         next_program_point (curr_point, freq);
 633
 634       sparseset_clear (start_living);
 635
 636       need_curr_point_incr = false;
 637
 638       /* Mark each used value as live.  */
 639       for (reg = curr_id->regs; reg != NULL; reg = reg->next)
 640         if (reg->type == OP_IN)
 641           {
 642             need_curr_point_incr |= mark_regno_live (reg->regno,
 643                                                      reg->biggest_mode,
 644                                                      curr_point);
 645             check_pseudos_live_through_calls (reg->regno);
 646           }
 647
 648       for (reg = curr_static_id->hard_regs; reg != NULL; reg = reg->next)
 649         if (reg->type == OP_IN)
 650           make_hard_regno_born (reg->regno);
 651
 652       if (curr_id->arg_hard_regs != NULL)
 653         /* Make argument hard registers live.  */
 654         for (i = 0; (regno = curr_id->arg_hard_regs[i]) >= 0; i++)
 655           make_hard_regno_born (regno);
 656
 657       sparseset_and_compl (dead_set, start_living, start_dying);
 658
 659       /* Mark early clobber outputs dead.  */
 660       for (reg = curr_id->regs; reg != NULL; reg = reg->next)
 661         if (reg->type == OP_OUT && reg->early_clobber && ! reg->subreg_p)
 662           need_curr_point_incr = mark_regno_dead (reg->regno,
 663                                                   reg->biggest_mode,
 664                                                   curr_point);
 665
 666       for (reg = curr_static_id->hard_regs; reg != NULL; reg = reg->next)
 667         if (reg->type == OP_OUT && reg->early_clobber && ! reg->subreg_p)
 668           make_hard_regno_dead (reg->regno);
 669
 670       if (need_curr_point_incr)
 671         next_program_point (curr_point, freq);
 672
 673       /* Update notes.  */
 674       for (link_loc = &REG_NOTES (curr_insn); (link = *link_loc) != NULL_RTX;)
 675         {
 676           if (REG_NOTE_KIND (link) != REG_DEAD
 677               && REG_NOTE_KIND (link) != REG_UNUSED)
 678             ;
 679           else if (REG_P (XEXP (link, 0)))
 680             {
 681               regno = REGNO (XEXP (link, 0));
 682               if ((REG_NOTE_KIND (link) == REG_DEAD
 683                    && ! sparseset_bit_p (dead_set, regno))
 684                   || (REG_NOTE_KIND (link) == REG_UNUSED
 685                       && ! sparseset_bit_p (unused_set, regno)))
 686                 {
 687                   *link_loc = XEXP (link, 1);
 688                   continue;
 689                 }
 690               if (REG_NOTE_KIND (link) == REG_DEAD)
 691                 sparseset_clear_bit (dead_set, regno);
 692               else if (REG_NOTE_KIND (link) == REG_UNUSED)
 693                 sparseset_clear_bit (unused_set, regno);
 694             }
 695           link_loc = &XEXP (link, 1);
 696         }
 697       EXECUTE_IF_SET_IN_SPARSESET (dead_set, j)
 698         add_reg_note (curr_insn, REG_DEAD, regno_reg_rtx[j]);
 699       EXECUTE_IF_SET_IN_SPARSESET (unused_set, j)
 700         add_reg_note (curr_insn, REG_UNUSED, regno_reg_rtx[j]);
 701     }
 702
 703 #ifdef EH_RETURN_DATA_REGNO
 704   if (bb_has_eh_pred (bb))
 705     for (j = 0; ; ++j)
 706       {
 707         unsigned int regno = EH_RETURN_DATA_REGNO (j);
 708
 709         if (regno == INVALID_REGNUM)
 710           break;
 711         make_hard_regno_born (regno);
 712       }
 713 #endif
 714
 715   /* Pseudos can't go in stack regs at the start of a basic block that
 716      is reached by an abnormal edge. Likewise for call clobbered regs,
 717      because caller-save, fixup_abnormal_edges and possibly the table
 718      driven EH machinery are not quite ready to handle such pseudos
 719      live across such edges.  */
 720   if (bb_has_abnormal_pred (bb))
 721     {
 722 #ifdef STACK_REGS
 723       EXECUTE_IF_SET_IN_SPARSESET (pseudos_live, px)
 724         lra_reg_info[px].no_stack_p = true;
 725       for (px = FIRST_STACK_REG; px <= LAST_STACK_REG; px++)
 726         make_hard_regno_born (px);
 727 #endif
 728       /* No need to record conflicts for call clobbered regs if we
 729          have nonlocal labels around, as we don't ever try to
 730          allocate such regs in this case.  */
 731       if (!cfun->has_nonlocal_label && bb_has_abnormal_call_pred (bb))
 732         for (px = 0; px < FIRST_PSEUDO_REGISTER; px++)
 733           if (call_used_regs[px])
 734             make_hard_regno_born (px);
 735     }
 736
 737   /* See if we'll need an increment at the end of this basic block.
 738      An increment is needed if the PSEUDOS_LIVE set is not empty,
 739      to make sure the finish points are set up correctly.  */
 740   need_curr_point_incr = (sparseset_cardinality (pseudos_live) > 0);
 741
 742   EXECUTE_IF_SET_IN_SPARSESET (pseudos_live, i)
 743     mark_pseudo_dead (i, curr_point);
 744
 745   EXECUTE_IF_SET_IN_BITMAP (df_get_live_in (bb), FIRST_PSEUDO_REGISTER, j, bi)
 746     {
 747       if (sparseset_cardinality (pseudos_live_through_calls) == 0)
 748         break;
 749       if (sparseset_bit_p (pseudos_live_through_calls, j))
 750         check_pseudos_live_through_calls (j);
 751     }
 752
 753   if (need_curr_point_incr)
 754     next_program_point (curr_point, freq);
 755 }
 756
 757 /* Compress pseudo live ranges by removing program points where
 758    nothing happens.  Complexity of many algorithms in LRA is linear
 759    function of program points number.  To speed up the code we try to
 760    minimize the number of the program points here.  */
 761 static void
 762 remove_some_program_points_and_update_live_ranges (void)
 763 {
 764   unsigned i;
 765   int n, max_regno;
 766   int *map;
 767   lra_live_range_t r, prev_r, next_r;
 768   sbitmap born_or_dead, born, dead;
 769   sbitmap_iterator sbi;
 770   bool born_p, dead_p, prev_born_p, prev_dead_p;
 771
 772   born = sbitmap_alloc (lra_live_max_point);
 773   dead = sbitmap_alloc (lra_live_max_point);
 774   bitmap_clear (born);
 775   bitmap_clear (dead);
 776   max_regno = max_reg_num ();
 777   for (i = FIRST_PSEUDO_REGISTER; i < (unsigned) max_regno; i++)
 778     {
 779       for (r = lra_reg_info[i].live_ranges; r != NULL; r = r->next)
 780         {
 781           lra_assert (r->start <= r->finish);
 782           bitmap_set_bit (born, r->start);
 783           bitmap_set_bit (dead, r->finish);
 784         }
 785     }
 786   born_or_dead = sbitmap_alloc (lra_live_max_point);
 787   bitmap_ior (born_or_dead, born, dead);
 788   map = XCNEWVEC (int, lra_live_max_point);
 789   n = -1;
 790   prev_born_p = prev_dead_p = false;
 791   EXECUTE_IF_SET_IN_BITMAP (born_or_dead, 0, i, sbi)
 792     {
 793       born_p = bitmap_bit_p (born, i);
 794       dead_p = bitmap_bit_p (dead, i);
 795       if ((prev_born_p && ! prev_dead_p && born_p && ! dead_p)
 796           || (prev_dead_p && ! prev_born_p && dead_p && ! born_p))
 797         {
 798           map[i] = n;
 799           lra_point_freq[n] = MAX (lra_point_freq[n], lra_point_freq[i]);
 800         }
 801       else
 802         {
 803           map[i] = ++n;
 804           lra_point_freq[n] = lra_point_freq[i];
 805         }
 806       prev_born_p = born_p;
 807       prev_dead_p = dead_p;
 808     }
 809   sbitmap_free (born_or_dead);
 810   sbitmap_free (born);
 811   sbitmap_free (dead);
 812   n++;
 813   if (lra_dump_file != NULL)
 814     fprintf (lra_dump_file, "Compressing live ranges: from %d to %d - %d%%\n",
 815              lra_live_max_point, n, 100 * n / lra_live_max_point);
 816   if (n < lra_live_max_point)
 817     {
 818       lra_live_max_point = n;
 819       for (i = FIRST_PSEUDO_REGISTER; i < (unsigned) max_regno; i++)
 820         {
 821           for (prev_r = NULL, r = lra_reg_info[i].live_ranges;
 822                r != NULL;
 823                r = next_r)
 824             {
 825               next_r = r->next;
 826               r->start = map[r->start];
 827               r->finish = map[r->finish];
 828               if (prev_r == NULL || prev_r->start > r->finish + 1)
 829                 {
 830                   prev_r = r;
 831                   continue;
 832                 }
 833               prev_r->start = r->start;
 834               prev_r->next = next_r;
 835               free_live_range (r);
 836             }
 837         }
 838     }
 839   free (map);
 840 }
 841
 842 /* Print live ranges R to file F.  */
 843 void
 844 lra_print_live_range_list (FILE *f, lra_live_range_t r)
 845 {
 846   for (; r != NULL; r = r->next)
 847     fprintf (f, " [%d..%d]", r->start, r->finish);
 848   fprintf (f, "\n");
 849 }
 850
 851 /* Print live ranges R to stderr.  */
 852 void
 853 lra_debug_live_range_list (lra_live_range_t r)
 854 {
 855   lra_print_live_range_list (stderr, r);
 856 }
 857
 858 /* Print live ranges of pseudo REGNO to file F.  */
 859 static void
 860 print_pseudo_live_ranges (FILE *f, int regno)
 861 {
 862   if (lra_reg_info[regno].live_ranges == NULL)
 863     return;
 864   fprintf (f, " r%d:", regno);
 865   lra_print_live_range_list (f, lra_reg_info[regno].live_ranges);
 866 }
 867
 868 /* Print live ranges of pseudo REGNO to stderr.  */
 869 void
 870 lra_debug_pseudo_live_ranges (int regno)
 871 {
 872   print_pseudo_live_ranges (stderr, regno);
 873 }
 874
 875 /* Print live ranges of all pseudos to file F.  */
 876 static void
 877 print_live_ranges (FILE *f)
 878 {
 879   int i, max_regno;
 880
 881   max_regno = max_reg_num ();
 882   for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
 883     print_pseudo_live_ranges (f, i);
 884 }
 885
 886 /* Print live ranges of all pseudos to stderr.  */
 887 void
 888 lra_debug_live_ranges (void)
 889 {
 890   print_live_ranges (stderr);
 891 }
 892
 893 /* Compress pseudo live ranges.  */
 894 static void
 895 compress_live_ranges (void)
 896 {
 897   remove_some_program_points_and_update_live_ranges ();
 898   if (lra_dump_file != NULL)
 899     {
 900       fprintf (lra_dump_file, "Ranges after the compression:\n");
 901       print_live_ranges (lra_dump_file);
 902     }
 903 }
 904
 905 /* The number of the current live range pass.  */
 906 int lra_live_range_iter;
 907
 908 /* The main entry function creates live ranges only for memory pseudos
 909    (or for all ones if ALL_P), set up CONFLICT_HARD_REGS for
 910    the pseudos.  */
 911 void
 912 lra_create_live_ranges (bool all_p)
 913 {
 914   basic_block bb;
 915   int i, hard_regno, max_regno = max_reg_num ();
 916   int curr_point;
 917   bool have_referenced_pseudos = false;
 918
 919   timevar_push (TV_LRA_CREATE_LIVE_RANGES);
 920
 921   complete_info_p = all_p;
 922   if (lra_dump_file != NULL)
 923     fprintf (lra_dump_file,
 924              "\n********** Pseudo live ranges #%d: **********\n\n",
 925              ++lra_live_range_iter);
 926   memset (lra_hard_reg_usage, 0, sizeof (lra_hard_reg_usage));
 927   for (i = 0; i < max_regno; i++)
 928     {
 929       lra_reg_info[i].live_ranges = NULL;
 930       CLEAR_HARD_REG_SET (lra_reg_info[i].conflict_hard_regs);
 931       lra_reg_info[i].preferred_hard_regno1 = -1;
 932       lra_reg_info[i].preferred_hard_regno2 = -1;
 933       lra_reg_info[i].preferred_hard_regno_profit1 = 0;
 934       lra_reg_info[i].preferred_hard_regno_profit2 = 0;
 935 #ifdef STACK_REGS
 936       lra_reg_info[i].no_stack_p = false;
 937 #endif
 938       /* The biggest mode is already set but its value might be to
 939          conservative because of recent transformation.  Here in this
 940          file we recalculate it again as it costs practically
 941          nothing.  */
 942       if (regno_reg_rtx[i] != NULL_RTX)
 943         lra_reg_info[i].biggest_mode = GET_MODE (regno_reg_rtx[i]);
 944       else
 945         lra_reg_info[i].biggest_mode = VOIDmode;
 946 #ifdef ENABLE_CHECKING
 947       lra_reg_info[i].call_p = false;
 948 #endif
 949       if (i >= FIRST_PSEUDO_REGISTER
 950           && lra_reg_info[i].nrefs != 0)
 951         {
 952           if ((hard_regno = reg_renumber[i]) >= 0)
 953             lra_hard_reg_usage[hard_regno] += lra_reg_info[i].freq;
 954           have_referenced_pseudos = true;
 955         }
 956     }
 957   lra_free_copies ();
 958
 959   /* Under some circumstances, we can have functions without pseudo
 960      registers.  For such functions, lra_live_max_point will be 0,
 961      see e.g. PR55604, and there's nothing more to do for us here.  */
 962   if (! have_referenced_pseudos)
 963     {
 964       timevar_pop (TV_LRA_CREATE_LIVE_RANGES);
 965       return;
 966     }
 967
 968   pseudos_live = sparseset_alloc (max_regno);
 969   pseudos_live_through_calls = sparseset_alloc (max_regno);
 970   pseudos_live_through_setjumps = sparseset_alloc (max_regno);
 971   start_living = sparseset_alloc (max_regno);
 972   start_dying = sparseset_alloc (max_regno);
 973   dead_set = sparseset_alloc (max_regno);
 974   unused_set = sparseset_alloc (max_regno);
 975   curr_point = 0;
 976   point_freq_vec.create (get_max_uid () * 2);
 977   lra_point_freq = point_freq_vec.address ();
 978   int *post_order_rev_cfg = XNEWVEC (int, last_basic_block);
 979   int n_blocks_inverted = inverted_post_order_compute (post_order_rev_cfg);
 980   lra_assert (n_blocks_inverted == n_basic_blocks);
 981   for (i = n_blocks_inverted - 1; i >= 0; --i)
 982     {
 983       bb = BASIC_BLOCK (post_order_rev_cfg[i]);
 984       if (bb == EXIT_BLOCK_PTR || bb == ENTRY_BLOCK_PTR)
 985         continue;
 986       process_bb_lives (bb, curr_point);
 987     }
 988   free (post_order_rev_cfg);
 989   lra_live_max_point = curr_point;
 990   gcc_checking_assert (lra_live_max_point > 0);
 991   if (lra_dump_file != NULL)
 992     print_live_ranges (lra_dump_file);
 993   /* Clean up.  */
 994   sparseset_free (unused_set);
 995   sparseset_free (dead_set);
 996   sparseset_free (start_dying);
 997   sparseset_free (start_living);
 998   sparseset_free (pseudos_live_through_calls);
 999   sparseset_free (pseudos_live_through_setjumps);
1000   sparseset_free (pseudos_live);
1001   compress_live_ranges ();
1002   timevar_pop (TV_LRA_CREATE_LIVE_RANGES);
1003 }
1004
1005 /* Finish all live ranges.  */
1006 void
1007 lra_clear_live_ranges (void)
1008 {
1009   int i;
1010
1011   for (i = 0; i < max_reg_num (); i++)
1012     free_live_range_list (lra_reg_info[i].live_ranges);
1013   point_freq_vec.release ();
1014 }
1015
1016 /* Initialize live ranges data once per function.  */
1017 void
1018 lra_live_ranges_init (void)
1019 {
1020   live_range_pool = create_alloc_pool ("live ranges",
1021                                        sizeof (struct lra_live_range), 100);
1022 }
1023
1024 /* Finish live ranges data once per function.  */
1025 void
1026 lra_live_ranges_finish (void)
1027 {
1028   free_alloc_pool (live_range_pool);
1029 }