gcc/cfgloopmanip.c

   1 /* Loop manipulation code for GNU compiler.
   2    Copyright (C) 2002, 2003 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 2, 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 COPYING.  If not, write to the Free
  18 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
  19 02111-1307, USA.  */
  20
  21 #include "config.h"
  22 #include "system.h"
  23 #include "coretypes.h"
  24 #include "tm.h"
  25 #include "rtl.h"
  26 #include "hard-reg-set.h"
  27 #include "basic-block.h"
  28 #include "cfgloop.h"
  29 #include "cfglayout.h"
  30 #include "output.h"
  31
  32 static basic_block create_preheader     PARAMS ((struct loop *, dominance_info,
  33                                                 int));
  34
  35 /* Creates a pre-header for a LOOP.  Returns newly created block.  Unless
  36    CP_SIMPLE_PREHEADERS is set in FLAGS, we only force LOOP to have single
  37    entry; otherwise we also force preheader block to have only one successor.
  38    */
  39 static basic_block
  40 create_preheader (loop, dom, flags)
  41      struct loop *loop;
  42      dominance_info dom;
  43      int flags;
  44 {
  45   edge e, fallthru;
  46   basic_block dummy;
  47   basic_block jump, src = 0;
  48   struct loop *cloop, *ploop;
  49   int nentry = 0;
  50   rtx insn;
  51
  52   cloop = loop->outer;
  53
  54   for (e = loop->header->pred; e; e = e->pred_next)
  55     {
  56       if (e->src == loop->latch)
  57         continue;
  58       nentry++;
  59     }
  60   if (!nentry)
  61     abort ();
  62   if (nentry == 1)
  63     {
  64       for (e = loop->header->pred; e->src == loop->latch; e = e->pred_next);
  65       if (!(flags & CP_SIMPLE_PREHEADERS)
  66           || !e->src->succ->succ_next)
  67         return NULL;
  68     }
  69
  70   insn = first_insn_after_basic_block_note (loop->header);
  71   if (insn)
  72     insn = PREV_INSN (insn);
  73   else
  74     insn = get_last_insn ();
  75   if (insn == loop->header->end)
  76     {
  77       /* Split_block would not split block after its end.  */
  78       emit_note_after (NOTE_INSN_DELETED, insn);
  79     }
  80   if (flags & CP_INSIDE_CFGLAYOUT)
  81     fallthru = cfg_layout_split_block (loop->header, insn);
  82   else
  83     fallthru = split_block (loop->header, insn);
  84   dummy = fallthru->src;
  85   loop->header = fallthru->dest;
  86
  87   /* The header could be a latch of some superloop(s); due to design of
  88      split_block, it would now move to fallthru->dest.  */
  89   for (ploop = loop; ploop; ploop = ploop->outer)
  90     if (ploop->latch == dummy)
  91       ploop->latch = fallthru->dest;
  92
  93   add_to_dominance_info (dom, fallthru->dest);
  94
  95   /* Redirect edges. */
  96   for (e = dummy->pred; e; e = e->pred_next)
  97     {
  98       src = e->src;
  99       if (src == loop->latch)
 100         break;
 101     }
 102   if (!e)
 103     abort ();
 104
 105   dummy->frequency -= EDGE_FREQUENCY (e);
 106   dummy->count -= e->count;
 107   fallthru->count -= e->count;
 108   if (flags & CP_INSIDE_CFGLAYOUT)
 109     cfg_layout_redirect_edge (e, loop->header);
 110   else
 111     {
 112       jump = redirect_edge_and_branch_force (e, loop->header);
 113       if (jump)
 114         {
 115           add_to_dominance_info (dom, jump);
 116           set_immediate_dominator (dom, jump, src);
 117           add_bb_to_loop (jump, loop);
 118           loop->latch = jump;
 119         }
 120     }
 121
 122   /* Update structures.  */
 123   redirect_immediate_dominators (dom, dummy, loop->header);
 124   set_immediate_dominator (dom, loop->header, dummy);
 125   loop->header->loop_father = loop;
 126   add_bb_to_loop (dummy, cloop);
 127   if (rtl_dump_file)
 128     fprintf (rtl_dump_file, "Created preheader block for loop %i\n",
 129              loop->num);
 130
 131   return dummy;
 132 }
 133
 134 /* Create preheaders for each loop; for meaning of flags see
 135    create_preheader.  */
 136 void
 137 create_preheaders (loops, flags)
 138      struct loops *loops;
 139      int flags;
 140 {
 141   unsigned i;
 142   for (i = 1; i < loops->num; i++)
 143     create_preheader (loops->parray[i], loops->cfg.dom, flags);
 144   loops->state |= LOOPS_HAVE_PREHEADERS;
 145 }
 146
 147 /* Forces all loop latches to have only single successor.  */
 148 void
 149 force_single_succ_latches (loops)
 150      struct loops *loops;
 151 {
 152   unsigned i;
 153   struct loop *loop;
 154   edge e;
 155
 156   for (i = 1; i < loops->num; i++)
 157     {
 158       loop = loops->parray[i];
 159       if (!loop->latch->succ->succ_next)
 160         continue;
 161
 162       for (e = loop->header->pred; e->src != loop->latch; e = e->pred_next)
 163         continue;
 164
 165       loop_split_edge_with (e, NULL_RTX, loops);
 166     }
 167   loops->state |= LOOPS_HAVE_SIMPLE_LATCHES;
 168 }
 169
 170 /* A quite stupid function to put INSNS on E. They are supposed to form
 171    just one basic block. Jumps out are not handled, so cfg do not have to
 172    be ok after this function.  */
 173 basic_block
 174 loop_split_edge_with (e, insns, loops)
 175      edge e;
 176      rtx insns;
 177      struct loops *loops;
 178 {
 179   basic_block src, dest, new_bb;
 180   struct loop *loop_c;
 181   edge new_e;
 182
 183   src = e->src;
 184   dest = e->dest;
 185
 186   loop_c = find_common_loop (src->loop_father, dest->loop_father);
 187
 188   /* Create basic block for it.  */
 189
 190   new_bb = create_basic_block (NULL_RTX, NULL_RTX, EXIT_BLOCK_PTR->prev_bb);
 191   add_to_dominance_info (loops->cfg.dom, new_bb);
 192   add_bb_to_loop (new_bb, loop_c);
 193   new_bb->flags = insns ? BB_SUPERBLOCK : 0;
 194   if (src->flags & BB_IRREDUCIBLE_LOOP)
 195     {
 196       /* We expect simple preheaders here.  */
 197       if ((dest->flags & BB_IRREDUCIBLE_LOOP)
 198           || dest->loop_father->header == dest)
 199         new_bb->flags |= BB_IRREDUCIBLE_LOOP;
 200     }
 201
 202   new_e = make_edge (new_bb, dest, EDGE_FALLTHRU);
 203   new_e->probability = REG_BR_PROB_BASE;
 204   new_e->count = e->count;
 205
 206   new_bb->count = e->count;
 207   new_bb->frequency = EDGE_FREQUENCY (e);
 208   cfg_layout_redirect_edge (e, new_bb);
 209
 210   alloc_aux_for_block (new_bb, sizeof (struct reorder_block_def));
 211   if (insns)
 212     {
 213       start_sequence ();
 214       emit_insn (insns);
 215       insns = get_insns ();
 216       end_sequence ();
 217       emit_insn_after (insns, new_bb->end);
 218     }
 219
 220   set_immediate_dominator (loops->cfg.dom, new_bb, src);
 221   set_immediate_dominator (loops->cfg.dom, dest,
 222     recount_dominator (loops->cfg.dom, dest));
 223
 224   if (dest->loop_father->latch == src)
 225     dest->loop_father->latch = new_bb;
 226
 227   return new_bb;
 228 }