gcc/lra-lives.c

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