contrib/gcc-5.0/gcc/shrink-wrap.c

   1 /* Shrink-wrapping related optimizations.
   2    Copyright (C) 1987-2015 Free Software Foundation, Inc.
   3
   4 This file is part of GCC.
   5
   6 GCC is free software; you can redistribute it and/or modify it under
   7 the terms of the GNU General Public License as published by the Free
   8 Software Foundation; either version 3, or (at your option) any later
   9 version.
  10
  11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  14 for more details.
  15
  16 You should have received a copy of the GNU General Public License
  17 along with GCC; see the file COPYING3.  If not see
  18 <http://www.gnu.org/licenses/>.  */
  19
  20 /* This file handles shrink-wrapping related optimizations.  */
  21
  22 #include "config.h"
  23 #include "system.h"
  24 #include "coretypes.h"
  25 #include "tm.h"
  26 #include "rtl-error.h"
  27 #include "hash-set.h"
  28 #include "machmode.h"
  29 #include "vec.h"
  30 #include "double-int.h"
  31 #include "input.h"
  32 #include "alias.h"
  33 #include "symtab.h"
  34 #include "wide-int.h"
  35 #include "inchash.h"
  36 #include "tree.h"
  37 #include "fold-const.h"
  38 #include "stor-layout.h"
  39 #include "varasm.h"
  40 #include "stringpool.h"
  41 #include "flags.h"
  42 #include "except.h"
  43 #include "hard-reg-set.h"
  44 #include "function.h"
  45 #include "hashtab.h"
  46 #include "rtl.h"
  47 #include "statistics.h"
  48 #include "real.h"
  49 #include "fixed-value.h"
  50 #include "insn-config.h"
  51 #include "expmed.h"
  52 #include "dojump.h"
  53 #include "explow.h"
  54 #include "calls.h"
  55 #include "emit-rtl.h"
  56 #include "stmt.h"
  57 #include "expr.h"
  58 #include "insn-codes.h"
  59 #include "optabs.h"
  60 #include "libfuncs.h"
  61 #include "regs.h"
  62 #include "recog.h"
  63 #include "output.h"
  64 #include "tm_p.h"
  65 #include "langhooks.h"
  66 #include "target.h"
  67 #include "common/common-target.h"
  68 #include "gimple-expr.h"
  69 #include "gimplify.h"
  70 #include "tree-pass.h"
  71 #include "predict.h"
  72 #include "dominance.h"
  73 #include "cfg.h"
  74 #include "cfgrtl.h"
  75 #include "basic-block.h"
  76 #include "df.h"
  77 #include "params.h"
  78 #include "bb-reorder.h"
  79 #include "shrink-wrap.h"
  80 #include "regcprop.h"
  81 #include "rtl-iter.h"
  82
  83 #ifdef HAVE_simple_return
  84
  85 /* Return true if INSN requires the stack frame to be set up.
  86    PROLOGUE_USED contains the hard registers used in the function
  87    prologue.  SET_UP_BY_PROLOGUE is the set of registers we expect the
  88    prologue to set up for the function.  */
  89 bool
  90 requires_stack_frame_p (rtx_insn *insn, HARD_REG_SET prologue_used,
  91                         HARD_REG_SET set_up_by_prologue)
  92 {
  93   df_ref def, use;
  94   HARD_REG_SET hardregs;
  95   unsigned regno;
  96
  97   if (CALL_P (insn))
  98     return !SIBLING_CALL_P (insn);
  99
 100   /* We need a frame to get the unique CFA expected by the unwinder.  */
 101   if (cfun->can_throw_non_call_exceptions && can_throw_internal (insn))
 102     return true;
 103
 104   CLEAR_HARD_REG_SET (hardregs);
 105   FOR_EACH_INSN_DEF (def, insn)
 106     {
 107       rtx dreg = DF_REF_REG (def);
 108
 109       if (!REG_P (dreg))
 110         continue;
 111
 112       add_to_hard_reg_set (&hardregs, GET_MODE (dreg),
 113                            REGNO (dreg));
 114     }
 115   if (hard_reg_set_intersect_p (hardregs, prologue_used))
 116     return true;
 117   AND_COMPL_HARD_REG_SET (hardregs, call_used_reg_set);
 118   for (regno = 0; regno < FIRST_PSEUDO_REGISTER; regno++)
 119     if (TEST_HARD_REG_BIT (hardregs, regno)
 120         && df_regs_ever_live_p (regno))
 121       return true;
 122
 123   FOR_EACH_INSN_USE (use, insn)
 124     {
 125       rtx reg = DF_REF_REG (use);
 126
 127       if (!REG_P (reg))
 128         continue;
 129
 130       add_to_hard_reg_set (&hardregs, GET_MODE (reg),
 131                            REGNO (reg));
 132     }
 133   if (hard_reg_set_intersect_p (hardregs, set_up_by_prologue))
 134     return true;
 135
 136   return false;
 137 }
 138
 139 /* See whether there has a single live edge from BB, which dest uses
 140    [REGNO, END_REGNO).  Return the live edge if its dest bb has
 141    one or two predecessors.  Otherwise return NULL.  */
 142
 143 static edge
 144 live_edge_for_reg (basic_block bb, int regno, int end_regno)
 145 {
 146   edge e, live_edge;
 147   edge_iterator ei;
 148   bitmap live;
 149   int i;
 150
 151   live_edge = NULL;
 152   FOR_EACH_EDGE (e, ei, bb->succs)
 153     {
 154       live = df_get_live_in (e->dest);
 155       for (i = regno; i < end_regno; i++)
 156         if (REGNO_REG_SET_P (live, i))
 157           {
 158             if (live_edge && live_edge != e)
 159               return NULL;
 160             live_edge = e;
 161           }
 162     }
 163
 164   /* We can sometimes encounter dead code.  Don't try to move it
 165      into the exit block.  */
 166   if (!live_edge || live_edge->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
 167     return NULL;
 168
 169   /* Reject targets of abnormal edges.  This is needed for correctness
 170      on ports like Alpha and MIPS, whose pic_offset_table_rtx can die on
 171      exception edges even though it is generally treated as call-saved
 172      for the majority of the compilation.  Moving across abnormal edges
 173      isn't going to be interesting for shrink-wrap usage anyway.  */
 174   if (live_edge->flags & EDGE_ABNORMAL)
 175     return NULL;
 176
 177   /* When live_edge->dest->preds == 2, we can create a new block on
 178      the edge to make it meet the requirement.  */
 179   if (EDGE_COUNT (live_edge->dest->preds) > 2)
 180     return NULL;
 181
 182   return live_edge;
 183 }
 184
 185 /* Try to move INSN from BB to a successor.  Return true on success.
 186    USES and DEFS are the set of registers that are used and defined
 187    after INSN in BB.  SPLIT_P indicates whether a live edge from BB
 188    is splitted or not.  */
 189
 190 static bool
 191 move_insn_for_shrink_wrap (basic_block bb, rtx_insn *insn,
 192                            const HARD_REG_SET uses,
 193                            const HARD_REG_SET defs,
 194                            bool *split_p)
 195 {
 196   rtx set, src, dest;
 197   bitmap live_out, live_in, bb_uses, bb_defs;
 198   unsigned int i, dregno, end_dregno;
 199   unsigned int sregno = FIRST_PSEUDO_REGISTER;
 200   unsigned int end_sregno = FIRST_PSEUDO_REGISTER;
 201   basic_block next_block;
 202   edge live_edge;
 203
 204   /* Look for a simple register assignment.  We don't use single_set here
 205      because we can't deal with any CLOBBERs, USEs, or REG_UNUSED secondary
 206      destinations.  */
 207   if (!INSN_P (insn))
 208     return false;
 209   set = PATTERN (insn);
 210   if (GET_CODE (set) != SET)
 211     return false;
 212   src = SET_SRC (set);
 213   dest = SET_DEST (set);
 214
 215   /* For the destination, we want only a register.  Also disallow STACK
 216      or FRAME related adjustments.  They are likely part of the prologue,
 217      so keep them in the entry block.  */
 218   if (!REG_P (dest)
 219       || dest == stack_pointer_rtx
 220       || dest == frame_pointer_rtx
 221       || dest == hard_frame_pointer_rtx)
 222     return false;
 223
 224   /* For the source, we want one of:
 225       (1) A (non-overlapping) register
 226       (2) A constant,
 227       (3) An expression involving no more than one register.
 228
 229      That last point comes from the code following, which was originally
 230      written to handle only register move operations, and still only handles
 231      a single source register when checking for overlaps.  Happily, the
 232      same checks can be applied to expressions like (plus reg const).  */
 233
 234   if (CONSTANT_P (src))
 235     ;
 236   else if (!REG_P (src))
 237     {
 238       rtx src_inner = NULL_RTX;
 239
 240       if (can_throw_internal (insn))
 241         return false;
 242
 243       subrtx_var_iterator::array_type array;
 244       FOR_EACH_SUBRTX_VAR (iter, array, src, ALL)
 245         {
 246           rtx x = *iter;
 247           switch (GET_RTX_CLASS (GET_CODE (x)))
 248             {
 249             case RTX_CONST_OBJ:
 250             case RTX_COMPARE:
 251             case RTX_COMM_COMPARE:
 252             case RTX_BIN_ARITH:
 253             case RTX_COMM_ARITH:
 254             case RTX_UNARY:
 255             case RTX_TERNARY:
 256               /* Constant or expression.  Continue.  */
 257               break;
 258
 259             case RTX_OBJ:
 260             case RTX_EXTRA:
 261               switch (GET_CODE (x))
 262                 {
 263                 case UNSPEC:
 264                 case SUBREG:
 265                 case STRICT_LOW_PART:
 266                 case PC:
 267                 case LO_SUM:
 268                   /* Ok.  Continue.  */
 269                   break;
 270
 271                 case REG:
 272                   /* Fail if we see a second inner register.  */
 273                   if (src_inner != NULL)
 274                     return false;
 275                   src_inner = x;
 276                   break;
 277
 278                 default:
 279                   return false;
 280                 }
 281               break;
 282
 283             default:
 284               return false;
 285             }
 286         }
 287
 288       if (src_inner != NULL)
 289         src = src_inner;
 290     }
 291
 292   /* Make sure that the source register isn't defined later in BB.  */
 293   if (REG_P (src))
 294     {
 295       sregno = REGNO (src);
 296       end_sregno = END_REGNO (src);
 297       if (overlaps_hard_reg_set_p (defs, GET_MODE (src), sregno))
 298         return false;
 299     }
 300
 301   /* Make sure that the destination register isn't referenced later in BB.  */
 302   dregno = REGNO (dest);
 303   end_dregno = END_REGNO (dest);
 304   if (overlaps_hard_reg_set_p (uses, GET_MODE (dest), dregno)
 305       || overlaps_hard_reg_set_p (defs, GET_MODE (dest), dregno))
 306     return false;
 307
 308   /* See whether there is a successor block to which we could move INSN.  */
 309   live_edge = live_edge_for_reg (bb, dregno, end_dregno);
 310   if (!live_edge)
 311     return false;
 312
 313   next_block = live_edge->dest;
 314   /* Create a new basic block on the edge.  */
 315   if (EDGE_COUNT (next_block->preds) == 2)
 316     {
 317       /* split_edge for a block with only one successor is meaningless.  */
 318       if (EDGE_COUNT (bb->succs) == 1)
 319         return false;
 320
 321       /* If DF_LIVE doesn't exist, i.e. at -O1, just give up.  */
 322       if (!df_live)
 323         return false;
 324
 325       basic_block old_dest = live_edge->dest;
 326       next_block = split_edge (live_edge);
 327
 328       /* We create a new basic block.  Call df_grow_bb_info to make sure
 329          all data structures are allocated.  */
 330       df_grow_bb_info (df_live);
 331
 332       bitmap_and (df_get_live_in (next_block), df_get_live_out (bb),
 333                   df_get_live_in (old_dest));
 334       df_set_bb_dirty (next_block);
 335
 336       /* We should not split more than once for a function.  */
 337       if (*split_p)
 338         return false;
 339
 340       *split_p = true;
 341     }
 342
 343   /* At this point we are committed to moving INSN, but let's try to
 344      move it as far as we can.  */
 345   do
 346     {
 347       live_out = df_get_live_out (bb);
 348       live_in = df_get_live_in (next_block);
 349       bb = next_block;
 350
 351       /* Check whether BB uses DEST or clobbers DEST.  We need to add
 352          INSN to BB if so.  Either way, DEST is no longer live on entry,
 353          except for any part that overlaps SRC (next loop).  */
 354       bb_uses = &DF_LR_BB_INFO (bb)->use;
 355       bb_defs = &DF_LR_BB_INFO (bb)->def;
 356       if (df_live)
 357         {
 358           for (i = dregno; i < end_dregno; i++)
 359             {
 360               if (*split_p
 361                   || REGNO_REG_SET_P (bb_uses, i)
 362                   || REGNO_REG_SET_P (bb_defs, i)
 363                   || REGNO_REG_SET_P (&DF_LIVE_BB_INFO (bb)->gen, i))
 364                 next_block = NULL;
 365               CLEAR_REGNO_REG_SET (live_out, i);
 366               CLEAR_REGNO_REG_SET (live_in, i);
 367             }
 368
 369           /* Check whether BB clobbers SRC.  We need to add INSN to BB if so.
 370              Either way, SRC is now live on entry.  */
 371           for (i = sregno; i < end_sregno; i++)
 372             {
 373               if (*split_p
 374                   || REGNO_REG_SET_P (bb_defs, i)
 375                   || REGNO_REG_SET_P (&DF_LIVE_BB_INFO (bb)->gen, i))
 376                 next_block = NULL;
 377               SET_REGNO_REG_SET (live_out, i);
 378               SET_REGNO_REG_SET (live_in, i);
 379             }
 380         }
 381       else
 382         {
 383           /* DF_LR_BB_INFO (bb)->def does not comprise the DF_REF_PARTIAL and
 384              DF_REF_CONDITIONAL defs.  So if DF_LIVE doesn't exist, i.e.
 385              at -O1, just give up searching NEXT_BLOCK.  */
 386           next_block = NULL;
 387           for (i = dregno; i < end_dregno; i++)
 388             {
 389               CLEAR_REGNO_REG_SET (live_out, i);
 390               CLEAR_REGNO_REG_SET (live_in, i);
 391             }
 392
 393           for (i = sregno; i < end_sregno; i++)
 394             {
 395               SET_REGNO_REG_SET (live_out, i);
 396               SET_REGNO_REG_SET (live_in, i);
 397             }
 398         }
 399
 400       /* If we don't need to add the move to BB, look for a single
 401          successor block.  */
 402       if (next_block)
 403         {
 404           live_edge = live_edge_for_reg (next_block, dregno, end_dregno);
 405           if (!live_edge || EDGE_COUNT (live_edge->dest->preds) > 1)
 406             break;
 407           next_block = live_edge->dest;
 408         }
 409     }
 410   while (next_block);
 411
 412   /* For the new created basic block, there is no dataflow info at all.
 413      So skip the following dataflow update and check.  */
 414   if (!(*split_p))
 415     {
 416       /* BB now defines DEST.  It only uses the parts of DEST that overlap SRC
 417          (next loop).  */
 418       for (i = dregno; i < end_dregno; i++)
 419         {
 420           CLEAR_REGNO_REG_SET (bb_uses, i);
 421           SET_REGNO_REG_SET (bb_defs, i);
 422         }
 423
 424       /* BB now uses SRC.  */
 425       for (i = sregno; i < end_sregno; i++)
 426         SET_REGNO_REG_SET (bb_uses, i);
 427     }
 428
 429   emit_insn_after (PATTERN (insn), bb_note (bb));
 430   delete_insn (insn);
 431   return true;
 432 }
 433
 434 /* Look for register copies in the first block of the function, and move
 435    them down into successor blocks if the register is used only on one
 436    path.  This exposes more opportunities for shrink-wrapping.  These
 437    kinds of sets often occur when incoming argument registers are moved
 438    to call-saved registers because their values are live across one or
 439    more calls during the function.  */
 440
 441 void
 442 prepare_shrink_wrap (basic_block entry_block)
 443 {
 444   rtx_insn *insn, *curr;
 445   rtx x;
 446   HARD_REG_SET uses, defs;
 447   df_ref def, use;
 448   bool split_p = false;
 449
 450   if (JUMP_P (BB_END (entry_block)))
 451     {
 452       /* To have more shrink-wrapping opportunities, prepare_shrink_wrap tries
 453          to sink the copies from parameter to callee saved register out of
 454          entry block.  copyprop_hardreg_forward_bb_without_debug_insn is called
 455          to release some dependences.  */
 456       copyprop_hardreg_forward_bb_without_debug_insn (entry_block);
 457     }
 458
 459   CLEAR_HARD_REG_SET (uses);
 460   CLEAR_HARD_REG_SET (defs);
 461   FOR_BB_INSNS_REVERSE_SAFE (entry_block, insn, curr)
 462     if (NONDEBUG_INSN_P (insn)
 463         && !move_insn_for_shrink_wrap (entry_block, insn, uses, defs,
 464                                        &split_p))
 465       {
 466         /* Add all defined registers to DEFs.  */
 467         FOR_EACH_INSN_DEF (def, insn)
 468           {
 469             x = DF_REF_REG (def);
 470             if (REG_P (x) && HARD_REGISTER_P (x))
 471               SET_HARD_REG_BIT (defs, REGNO (x));
 472           }
 473
 474         /* Add all used registers to USESs.  */
 475         FOR_EACH_INSN_USE (use, insn)
 476           {
 477             x = DF_REF_REG (use);
 478             if (REG_P (x) && HARD_REGISTER_P (x))
 479               SET_HARD_REG_BIT (uses, REGNO (x));
 480           }
 481       }
 482 }
 483
 484 /* Create a copy of BB instructions and insert at BEFORE.  Redirect
 485    preds of BB to COPY_BB if they don't appear in NEED_PROLOGUE.  */
 486 void
 487 dup_block_and_redirect (basic_block bb, basic_block copy_bb, rtx_insn *before,
 488                         bitmap_head *need_prologue)
 489 {
 490   edge_iterator ei;
 491   edge e;
 492   rtx_insn *insn = BB_END (bb);
 493
 494   /* We know BB has a single successor, so there is no need to copy a
 495      simple jump at the end of BB.  */
 496   if (simplejump_p (insn))
 497     insn = PREV_INSN (insn);
 498
 499   start_sequence ();
 500   duplicate_insn_chain (BB_HEAD (bb), insn);
 501   if (dump_file)
 502     {
 503       unsigned count = 0;
 504       for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
 505         if (active_insn_p (insn))
 506           ++count;
 507       fprintf (dump_file, "Duplicating bb %d to bb %d, %u active insns.\n",
 508                bb->index, copy_bb->index, count);
 509     }
 510   insn = get_insns ();
 511   end_sequence ();
 512   emit_insn_before (insn, before);
 513
 514   /* Redirect all the paths that need no prologue into copy_bb.  */
 515   for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei));)
 516     if (!bitmap_bit_p (need_prologue, e->src->index))
 517       {
 518         int freq = EDGE_FREQUENCY (e);
 519         copy_bb->count += e->count;
 520         copy_bb->frequency += EDGE_FREQUENCY (e);
 521         e->dest->count -= e->count;
 522         if (e->dest->count < 0)
 523           e->dest->count = 0;
 524         e->dest->frequency -= freq;
 525         if (e->dest->frequency < 0)
 526           e->dest->frequency = 0;
 527         redirect_edge_and_branch_force (e, copy_bb);
 528         continue;
 529       }
 530     else
 531       ei_next (&ei);
 532 }
 533
 534
 535 /* Try to perform a kind of shrink-wrapping, making sure the
 536    prologue/epilogue is emitted only around those parts of the
 537    function that require it.  */
 538
 539 void
 540 try_shrink_wrapping (edge *entry_edge, edge orig_entry_edge,
 541                      bitmap_head *bb_flags, rtx_insn *prologue_seq)
 542 {
 543   edge e;
 544   edge_iterator ei;
 545   bool nonempty_prologue = false;
 546   unsigned max_grow_size;
 547   rtx_insn *seq;
 548
 549   for (seq = prologue_seq; seq; seq = NEXT_INSN (seq))
 550     if (!NOTE_P (seq) || NOTE_KIND (seq) != NOTE_INSN_PROLOGUE_END)
 551       {
 552         nonempty_prologue = true;
 553         break;
 554       }
 555
 556   if (flag_shrink_wrap && HAVE_simple_return
 557       && (targetm.profile_before_prologue () || !crtl->profile)
 558       && nonempty_prologue && !crtl->calls_eh_return)
 559     {
 560       HARD_REG_SET prologue_clobbered, prologue_used, live_on_edge;
 561       struct hard_reg_set_container set_up_by_prologue;
 562       rtx_insn *p_insn;
 563       vec<basic_block> vec;
 564       basic_block bb;
 565       bitmap_head bb_antic_flags;
 566       bitmap_head bb_on_list;
 567       bitmap_head bb_tail;
 568
 569       if (dump_file)
 570         fprintf (dump_file, "Attempting shrink-wrapping optimization.\n");
 571
 572       /* Compute the registers set and used in the prologue.  */
 573       CLEAR_HARD_REG_SET (prologue_clobbered);
 574       CLEAR_HARD_REG_SET (prologue_used);
 575       for (p_insn = prologue_seq; p_insn; p_insn = NEXT_INSN (p_insn))
 576         {
 577           HARD_REG_SET this_used;
 578           if (!NONDEBUG_INSN_P (p_insn))
 579             continue;
 580
 581           CLEAR_HARD_REG_SET (this_used);
 582           note_uses (&PATTERN (p_insn), record_hard_reg_uses,
 583                      &this_used);
 584           AND_COMPL_HARD_REG_SET (this_used, prologue_clobbered);
 585           IOR_HARD_REG_SET (prologue_used, this_used);
 586           note_stores (PATTERN (p_insn), record_hard_reg_sets,
 587                        &prologue_clobbered);
 588         }
 589
 590       prepare_shrink_wrap ((*entry_edge)->dest);
 591
 592       bitmap_initialize (&bb_antic_flags, &bitmap_default_obstack);
 593       bitmap_initialize (&bb_on_list, &bitmap_default_obstack);
 594       bitmap_initialize (&bb_tail, &bitmap_default_obstack);
 595
 596       /* Find the set of basic blocks that require a stack frame,
 597          and blocks that are too big to be duplicated.  */
 598
 599       vec.create (n_basic_blocks_for_fn (cfun));
 600
 601       CLEAR_HARD_REG_SET (set_up_by_prologue.set);
 602       add_to_hard_reg_set (&set_up_by_prologue.set, Pmode,
 603                            STACK_POINTER_REGNUM);
 604       add_to_hard_reg_set (&set_up_by_prologue.set, Pmode, ARG_POINTER_REGNUM);
 605       if (frame_pointer_needed)
 606         add_to_hard_reg_set (&set_up_by_prologue.set, Pmode,
 607                              HARD_FRAME_POINTER_REGNUM);
 608       if (pic_offset_table_rtx
 609           && (unsigned) PIC_OFFSET_TABLE_REGNUM != INVALID_REGNUM)
 610         add_to_hard_reg_set (&set_up_by_prologue.set, Pmode,
 611                              PIC_OFFSET_TABLE_REGNUM);
 612       if (crtl->drap_reg)
 613         add_to_hard_reg_set (&set_up_by_prologue.set,
 614                              GET_MODE (crtl->drap_reg),
 615                              REGNO (crtl->drap_reg));
 616       if (targetm.set_up_by_prologue)
 617         targetm.set_up_by_prologue (&set_up_by_prologue);
 618
 619       /* We don't use a different max size depending on
 620          optimize_bb_for_speed_p because increasing shrink-wrapping
 621          opportunities by duplicating tail blocks can actually result
 622          in an overall decrease in code size.  */
 623       max_grow_size = get_uncond_jump_length ();
 624       max_grow_size *= PARAM_VALUE (PARAM_MAX_GROW_COPY_BB_INSNS);
 625
 626       FOR_EACH_BB_FN (bb, cfun)
 627         {
 628           rtx_insn *insn;
 629           unsigned size = 0;
 630
 631           FOR_BB_INSNS (bb, insn)
 632             if (NONDEBUG_INSN_P (insn))
 633               {
 634                 if (requires_stack_frame_p (insn, prologue_used,
 635                                             set_up_by_prologue.set))
 636                   {
 637                     if (bb == (*entry_edge)->dest)
 638                       goto fail_shrinkwrap;
 639                     bitmap_set_bit (bb_flags, bb->index);
 640                     vec.quick_push (bb);
 641                     break;
 642                   }
 643                 else if (size <= max_grow_size)
 644                   {
 645                     size += get_attr_min_length (insn);
 646                     if (size > max_grow_size)
 647                       bitmap_set_bit (&bb_on_list, bb->index);
 648                   }
 649               }
 650         }
 651
 652       /* Blocks that really need a prologue, or are too big for tails.  */
 653       bitmap_ior_into (&bb_on_list, bb_flags);
 654
 655       /* For every basic block that needs a prologue, mark all blocks
 656          reachable from it, so as to ensure they are also seen as
 657          requiring a prologue.  */
 658       while (!vec.is_empty ())
 659         {
 660           basic_block tmp_bb = vec.pop ();
 661
 662           FOR_EACH_EDGE (e, ei, tmp_bb->succs)
 663             if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)
 664                 && bitmap_set_bit (bb_flags, e->dest->index))
 665               vec.quick_push (e->dest);
 666         }
 667
 668       /* Find the set of basic blocks that need no prologue, have a
 669          single successor, can be duplicated, meet a max size
 670          requirement, and go to the exit via like blocks.  */
 671       vec.quick_push (EXIT_BLOCK_PTR_FOR_FN (cfun));
 672       while (!vec.is_empty ())
 673         {
 674           basic_block tmp_bb = vec.pop ();
 675
 676           FOR_EACH_EDGE (e, ei, tmp_bb->preds)
 677             if (single_succ_p (e->src)
 678                 && !bitmap_bit_p (&bb_on_list, e->src->index)
 679                 && can_duplicate_block_p (e->src))
 680               {
 681                 edge pe;
 682                 edge_iterator pei;
 683
 684                 /* If there is predecessor of e->src which doesn't
 685                    need prologue and the edge is complex,
 686                    we might not be able to redirect the branch
 687                    to a copy of e->src.  */
 688                 FOR_EACH_EDGE (pe, pei, e->src->preds)
 689                   if ((pe->flags & EDGE_COMPLEX) != 0
 690                       && !bitmap_bit_p (bb_flags, pe->src->index))
 691                     break;
 692                 if (pe == NULL && bitmap_set_bit (&bb_tail, e->src->index))
 693                   vec.quick_push (e->src);
 694               }
 695         }
 696
 697       /* Now walk backwards from every block that is marked as needing
 698          a prologue to compute the bb_antic_flags bitmap.  Exclude
 699          tail blocks; They can be duplicated to be used on paths not
 700          needing a prologue.  */
 701       bitmap_clear (&bb_on_list);
 702       bitmap_and_compl (&bb_antic_flags, bb_flags, &bb_tail);
 703       FOR_EACH_BB_FN (bb, cfun)
 704         {
 705           if (!bitmap_bit_p (&bb_antic_flags, bb->index))
 706             continue;
 707           FOR_EACH_EDGE (e, ei, bb->preds)
 708             if (!bitmap_bit_p (&bb_antic_flags, e->src->index)
 709                 && bitmap_set_bit (&bb_on_list, e->src->index))
 710               vec.quick_push (e->src);
 711         }
 712       while (!vec.is_empty ())
 713         {
 714           basic_block tmp_bb = vec.pop ();
 715           bool all_set = true;
 716
 717           bitmap_clear_bit (&bb_on_list, tmp_bb->index);
 718           FOR_EACH_EDGE (e, ei, tmp_bb->succs)
 719             if (!bitmap_bit_p (&bb_antic_flags, e->dest->index))
 720               {
 721                 all_set = false;
 722                 break;
 723               }
 724
 725           if (all_set)
 726             {
 727               bitmap_set_bit (&bb_antic_flags, tmp_bb->index);
 728               FOR_EACH_EDGE (e, ei, tmp_bb->preds)
 729                 if (!bitmap_bit_p (&bb_antic_flags, e->src->index)
 730                     && bitmap_set_bit (&bb_on_list, e->src->index))
 731                   vec.quick_push (e->src);
 732             }
 733         }
 734       /* Find exactly one edge that leads to a block in ANTIC from
 735          a block that isn't.  */
 736       if (!bitmap_bit_p (&bb_antic_flags, (*entry_edge)->dest->index))
 737         FOR_EACH_BB_FN (bb, cfun)
 738           {
 739             if (!bitmap_bit_p (&bb_antic_flags, bb->index))
 740               continue;
 741             FOR_EACH_EDGE (e, ei, bb->preds)
 742               if (!bitmap_bit_p (&bb_antic_flags, e->src->index))
 743                 {
 744                   if (*entry_edge != orig_entry_edge)
 745                     {
 746                       *entry_edge = orig_entry_edge;
 747                       if (dump_file)
 748                         fprintf (dump_file, "More than one candidate edge.\n");
 749                       goto fail_shrinkwrap;
 750                     }
 751                   if (dump_file)
 752                     fprintf (dump_file, "Found candidate edge for "
 753                              "shrink-wrapping, %d->%d.\n", e->src->index,
 754                              e->dest->index);
 755                   *entry_edge = e;
 756                 }
 757           }
 758
 759       if (*entry_edge != orig_entry_edge)
 760         {
 761           /* Test whether the prologue is known to clobber any register
 762              (other than FP or SP) which are live on the edge.  */
 763           CLEAR_HARD_REG_BIT (prologue_clobbered, STACK_POINTER_REGNUM);
 764           if (frame_pointer_needed)
 765             CLEAR_HARD_REG_BIT (prologue_clobbered, HARD_FRAME_POINTER_REGNUM);
 766           REG_SET_TO_HARD_REG_SET (live_on_edge,
 767                                    df_get_live_in ((*entry_edge)->dest));
 768           if (hard_reg_set_intersect_p (live_on_edge, prologue_clobbered))
 769             {
 770               *entry_edge = orig_entry_edge;
 771               if (dump_file)
 772                 fprintf (dump_file,
 773                          "Shrink-wrapping aborted due to clobber.\n");
 774             }
 775         }
 776       if (*entry_edge != orig_entry_edge)
 777         {
 778           crtl->shrink_wrapped = true;
 779           if (dump_file)
 780             fprintf (dump_file, "Performing shrink-wrapping.\n");
 781
 782           /* Find tail blocks reachable from both blocks needing a
 783              prologue and blocks not needing a prologue.  */
 784           if (!bitmap_empty_p (&bb_tail))
 785             FOR_EACH_BB_FN (bb, cfun)
 786               {
 787                 bool some_pro, some_no_pro;
 788                 if (!bitmap_bit_p (&bb_tail, bb->index))
 789                   continue;
 790                 some_pro = some_no_pro = false;
 791                 FOR_EACH_EDGE (e, ei, bb->preds)
 792                   {
 793                     if (bitmap_bit_p (bb_flags, e->src->index))
 794                       some_pro = true;
 795                     else
 796                       some_no_pro = true;
 797                   }
 798                 if (some_pro && some_no_pro)
 799                   vec.quick_push (bb);
 800                 else
 801                   bitmap_clear_bit (&bb_tail, bb->index);
 802               }
 803           /* Find the head of each tail.  */
 804           while (!vec.is_empty ())
 805             {
 806               basic_block tbb = vec.pop ();
 807
 808               if (!bitmap_bit_p (&bb_tail, tbb->index))
 809                 continue;
 810
 811               while (single_succ_p (tbb))
 812                 {
 813                   tbb = single_succ (tbb);
 814                   bitmap_clear_bit (&bb_tail, tbb->index);
 815                 }
 816             }
 817           /* Now duplicate the tails.  */
 818           if (!bitmap_empty_p (&bb_tail))
 819             FOR_EACH_BB_REVERSE_FN (bb, cfun)
 820               {
 821                 basic_block copy_bb, tbb;
 822                 rtx_insn *insert_point;
 823                 int eflags;
 824
 825                 if (!bitmap_clear_bit (&bb_tail, bb->index))
 826                   continue;
 827
 828                 /* Create a copy of BB, instructions and all, for
 829                    use on paths that don't need a prologue.
 830                    Ideal placement of the copy is on a fall-thru edge
 831                    or after a block that would jump to the copy.  */
 832                 FOR_EACH_EDGE (e, ei, bb->preds)
 833                   if (!bitmap_bit_p (bb_flags, e->src->index)
 834                       && single_succ_p (e->src))
 835                     break;
 836                 if (e)
 837                   {
 838                     /* Make sure we insert after any barriers.  */
 839                     rtx_insn *end = get_last_bb_insn (e->src);
 840                     copy_bb = create_basic_block (NEXT_INSN (end),
 841                                                   NULL_RTX, e->src);
 842                     BB_COPY_PARTITION (copy_bb, e->src);
 843                   }
 844                 else
 845                   {
 846                     /* Otherwise put the copy at the end of the function.  */
 847                     copy_bb = create_basic_block (NULL_RTX, NULL_RTX,
 848                                                   EXIT_BLOCK_PTR_FOR_FN (cfun)->prev_bb);
 849                     BB_COPY_PARTITION (copy_bb, bb);
 850                   }
 851
 852                 insert_point = emit_note_after (NOTE_INSN_DELETED,
 853                                                 BB_END (copy_bb));
 854                 emit_barrier_after (BB_END (copy_bb));
 855
 856                 tbb = bb;
 857                 while (1)
 858                   {
 859                     dup_block_and_redirect (tbb, copy_bb, insert_point,
 860                                             bb_flags);
 861                     tbb = single_succ (tbb);
 862                     if (tbb == EXIT_BLOCK_PTR_FOR_FN (cfun))
 863                       break;
 864                     e = split_block (copy_bb, PREV_INSN (insert_point));
 865                     copy_bb = e->dest;
 866                   }
 867
 868                 /* Quiet verify_flow_info by (ab)using EDGE_FAKE.
 869                    We have yet to add a simple_return to the tails,
 870                    as we'd like to first convert_jumps_to_returns in
 871                    case the block is no longer used after that.  */
 872                 eflags = EDGE_FAKE;
 873                 if (CALL_P (PREV_INSN (insert_point))
 874                     && SIBLING_CALL_P (PREV_INSN (insert_point)))
 875                   eflags = EDGE_SIBCALL | EDGE_ABNORMAL;
 876                 make_single_succ_edge (copy_bb, EXIT_BLOCK_PTR_FOR_FN (cfun),
 877                                        eflags);
 878
 879                 /* verify_flow_info doesn't like a note after a
 880                    sibling call.  */
 881                 delete_insn (insert_point);
 882                 if (bitmap_empty_p (&bb_tail))
 883                   break;
 884               }
 885         }
 886
 887     fail_shrinkwrap:
 888       bitmap_clear (&bb_tail);
 889       bitmap_clear (&bb_antic_flags);
 890       bitmap_clear (&bb_on_list);
 891       vec.release ();
 892     }
 893 }
 894
 895 /* If we're allowed to generate a simple return instruction, then by
 896    definition we don't need a full epilogue.  If the last basic
 897    block before the exit block does not contain active instructions,
 898    examine its predecessors and try to emit (conditional) return
 899    instructions.  */
 900
 901 edge
 902 get_unconverted_simple_return (edge exit_fallthru_edge, bitmap_head bb_flags,
 903                                vec<edge> *unconverted_simple_returns,
 904                                rtx_insn **returnjump)
 905 {
 906   if (optimize)
 907     {
 908       unsigned i, last;
 909
 910       /* convert_jumps_to_returns may add to preds of the exit block
 911          (but won't remove).  Stop at end of current preds.  */
 912       last = EDGE_COUNT (EXIT_BLOCK_PTR_FOR_FN (cfun)->preds);
 913       for (i = 0; i < last; i++)
 914         {
 915           edge e = EDGE_I (EXIT_BLOCK_PTR_FOR_FN (cfun)->preds, i);
 916           if (LABEL_P (BB_HEAD (e->src))
 917               && !bitmap_bit_p (&bb_flags, e->src->index)
 918               && !active_insn_between (BB_HEAD (e->src), BB_END (e->src)))
 919             *unconverted_simple_returns
 920                   = convert_jumps_to_returns (e->src, true,
 921                                               *unconverted_simple_returns);
 922         }
 923     }
 924
 925   if (exit_fallthru_edge != NULL
 926       && EDGE_COUNT (exit_fallthru_edge->src->preds) != 0
 927       && !bitmap_bit_p (&bb_flags, exit_fallthru_edge->src->index))
 928     {
 929       basic_block last_bb;
 930
 931       last_bb = emit_return_for_exit (exit_fallthru_edge, true);
 932       *returnjump = BB_END (last_bb);
 933       exit_fallthru_edge = NULL;
 934     }
 935   return exit_fallthru_edge;
 936 }
 937
 938 /* If there were branches to an empty LAST_BB which we tried to
 939    convert to conditional simple_returns, but couldn't for some
 940    reason, create a block to hold a simple_return insn and redirect
 941    those remaining edges.  */
 942
 943 void
 944 convert_to_simple_return (edge entry_edge, edge orig_entry_edge,
 945                           bitmap_head bb_flags, rtx_insn *returnjump,
 946                           vec<edge> unconverted_simple_returns)
 947 {
 948   edge e;
 949   edge_iterator ei;
 950
 951   if (!unconverted_simple_returns.is_empty ())
 952     {
 953       basic_block simple_return_block_hot = NULL;
 954       basic_block simple_return_block_cold = NULL;
 955       edge pending_edge_hot = NULL;
 956       edge pending_edge_cold = NULL;
 957       basic_block exit_pred;
 958       int i;
 959
 960       gcc_assert (entry_edge != orig_entry_edge);
 961
 962       /* See if we can reuse the last insn that was emitted for the
 963          epilogue.  */
 964       if (returnjump != NULL_RTX
 965           && JUMP_LABEL (returnjump) == simple_return_rtx)
 966         {
 967           e = split_block (BLOCK_FOR_INSN (returnjump), PREV_INSN (returnjump));
 968           if (BB_PARTITION (e->src) == BB_HOT_PARTITION)
 969             simple_return_block_hot = e->dest;
 970           else
 971             simple_return_block_cold = e->dest;
 972         }
 973
 974       /* Also check returns we might need to add to tail blocks.  */
 975       FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR_FOR_FN (cfun)->preds)
 976         if (EDGE_COUNT (e->src->preds) != 0
 977             && (e->flags & EDGE_FAKE) != 0
 978             && !bitmap_bit_p (&bb_flags, e->src->index))
 979           {
 980             if (BB_PARTITION (e->src) == BB_HOT_PARTITION)
 981               pending_edge_hot = e;
 982             else
 983               pending_edge_cold = e;
 984           }
 985
 986       /* Save a pointer to the exit's predecessor BB for use in
 987          inserting new BBs at the end of the function.  Do this
 988          after the call to split_block above which may split
 989          the original exit pred.  */
 990       exit_pred = EXIT_BLOCK_PTR_FOR_FN (cfun)->prev_bb;
 991
 992       FOR_EACH_VEC_ELT (unconverted_simple_returns, i, e)
 993         {
 994           basic_block *pdest_bb;
 995           edge pending;
 996
 997           if (BB_PARTITION (e->src) == BB_HOT_PARTITION)
 998             {
 999               pdest_bb = &simple_return_block_hot;
1000               pending = pending_edge_hot;
1001             }
1002           else
1003             {
1004               pdest_bb = &simple_return_block_cold;
1005               pending = pending_edge_cold;
1006             }
1007
1008           if (*pdest_bb == NULL && pending != NULL)
1009             {
1010               emit_return_into_block (true, pending->src);
1011               pending->flags &= ~(EDGE_FALLTHRU | EDGE_FAKE);
1012               *pdest_bb = pending->src;
1013             }
1014           else if (*pdest_bb == NULL)
1015             {
1016               basic_block bb;
1017               rtx_insn *start;
1018
1019               bb = create_basic_block (NULL, NULL, exit_pred);
1020               BB_COPY_PARTITION (bb, e->src);
1021               start = emit_jump_insn_after (gen_simple_return (),
1022                                             BB_END (bb));
1023               JUMP_LABEL (start) = simple_return_rtx;
1024               emit_barrier_after (start);
1025
1026               *pdest_bb = bb;
1027               make_edge (bb, EXIT_BLOCK_PTR_FOR_FN (cfun), 0);
1028             }
1029           redirect_edge_and_branch_force (e, *pdest_bb);
1030         }
1031       unconverted_simple_returns.release ();
1032     }
1033
1034   if (entry_edge != orig_entry_edge)
1035     {
1036       FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR_FOR_FN (cfun)->preds)
1037         if (EDGE_COUNT (e->src->preds) != 0
1038             && (e->flags & EDGE_FAKE) != 0
1039             && !bitmap_bit_p (&bb_flags, e->src->index))
1040           {
1041             emit_return_into_block (true, e->src);
1042             e->flags &= ~(EDGE_FALLTHRU | EDGE_FAKE);
1043           }
1044     }
1045 }
1046
1047 #endif