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         loop_split_edge_with (e, NULL_RTX, loops);
 164     }
 165   loops->state |= LOOPS_HAVE_SIMPLE_LATCHES;
 166 }
 167
 168 /* A quite stupid function to put INSNS on E. They are supposed to form
 169    just one basic block. Jumps out are not handled, so cfg do not have to
 170    be ok after this function.  */
 171 basic_block
 172 loop_split_edge_with (e, insns, loops)
 173      edge e;
 174      rtx insns;
 175      struct loops *loops;
 176 {
 177   basic_block src, dest, new_bb;
 178   struct loop *loop_c;
 179   edge new_e;
 180
 181   src = e->src;
 182   dest = e->dest;
 183
 184   loop_c = find_common_loop (src->loop_father, dest->loop_father);
 185
 186   /* Create basic block for it.  */
 187
 188   new_bb = create_basic_block (NULL_RTX, NULL_RTX, EXIT_BLOCK_PTR->prev_bb);
 189   add_to_dominance_info (loops->cfg.dom, new_bb);
 190   add_bb_to_loop (new_bb, loop_c);
 191   new_bb->flags = insns ? BB_SUPERBLOCK : 0;
 192   if (src->flags & BB_IRREDUCIBLE_LOOP)
 193     {
 194       /* We expect simple preheaders here.  */
 195       if ((dest->flags & BB_IRREDUCIBLE_LOOP)
 196           || dest->loop_father->header == dest)
 197         new_bb->flags |= BB_IRREDUCIBLE_LOOP;
 198     }
 199
 200   new_e = make_edge (new_bb, dest, EDGE_FALLTHRU);
 201   new_e->probability = REG_BR_PROB_BASE;
 202   new_e->count = e->count;
 203
 204   new_bb->count = e->count;
 205   new_bb->frequency = EDGE_FREQUENCY (e);
 206   cfg_layout_redirect_edge (e, new_bb);
 207
 208   alloc_aux_for_block (new_bb, sizeof (struct reorder_block_def));
 209   if (insns)
 210     {
 211       start_sequence ();
 212       emit_insn (insns);
 213       insns = get_insns ();
 214       end_sequence ();
 215       emit_insn_after (insns, new_bb->end);
 216     }
 217
 218   set_immediate_dominator (loops->cfg.dom, new_bb, src);
 219   set_immediate_dominator (loops->cfg.dom, dest,
 220     recount_dominator (loops->cfg.dom, dest));
 221
 222   if (dest->loop_father->latch == src)
 223     dest->loop_father->latch = new_bb;
 224
 225   return new_bb;
 226 }