gcc/shrink-wrap.c

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