contrib/gcc-3.4/gcc/loop-init.c

   1 /* Loop optimizer initialization routines.
   2    Copyright (C) 2002, 2003, 2004 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
  31 static void fixup_loop_exit_succesor (basic_block, basic_block);
  32
  33 /* Initialize loop optimizer.  */
  34
  35 struct loops *
  36 loop_optimizer_init (FILE *dumpfile)
  37 {
  38   struct loops *loops = xcalloc (1, sizeof (struct loops));
  39   edge e;
  40
  41   /* Initialize structures for layout changes.  */
  42   cfg_layout_initialize ();
  43
  44   /* Avoid annoying special cases of edges going to exit
  45      block.  */
  46   for (e = EXIT_BLOCK_PTR->pred; e; e = e->pred_next)
  47     if ((e->flags & EDGE_FALLTHRU) && e->src->succ->succ_next)
  48       split_edge (e);
  49
  50   /* Find the loops.  */
  51
  52   if (flow_loops_find (loops, LOOP_TREE) <= 1)
  53     {
  54       basic_block bb;
  55
  56       /* No loops.  */
  57       flow_loops_free (loops);
  58       free_dominance_info (CDI_DOMINATORS);
  59       free (loops);
  60
  61       /* Make chain.  */
  62       FOR_EACH_BB (bb)
  63         if (bb->next_bb != EXIT_BLOCK_PTR)
  64           bb->rbi->next = bb->next_bb;
  65           cfg_layout_finalize ();
  66       return NULL;
  67     }
  68
  69   /* Not going to update these.  */
  70   free (loops->cfg.rc_order);
  71   loops->cfg.rc_order = NULL;
  72   free (loops->cfg.dfs_order);
  73   loops->cfg.dfs_order = NULL;
  74
  75   /* Create pre-headers.  */
  76   create_preheaders (loops, CP_SIMPLE_PREHEADERS);
  77
  78   /* Force all latches to have only single successor.  */
  79   force_single_succ_latches (loops);
  80
  81   /* Mark irreducible loops.  */
  82   mark_irreducible_loops (loops);
  83
  84   /* Dump loops.  */
  85   flow_loops_dump (loops, dumpfile, NULL, 1);
  86
  87 #ifdef ENABLE_CHECKING
  88   verify_dominators (CDI_DOMINATORS);
  89   verify_loop_structure (loops);
  90 #endif
  91
  92   return loops;
  93 }
  94
  95 /* The first basic block is moved after the second in the reorder chain.  */
  96 static void
  97 fixup_loop_exit_succesor (basic_block exit_succ, basic_block latch)
  98 {
  99   basic_block bb = exit_succ;
 100   basic_block bb1 = latch;
 101
 102   if (!(bb && bb->rbi->next))
 103     return;
 104
 105   if (!bb1)
 106     return;
 107
 108
 109   if (bb && bb->rbi->next)
 110     {
 111       basic_block c = ENTRY_BLOCK_PTR->next_bb;
 112
 113       while (c->rbi->next != bb)
 114         c = c->rbi->next;
 115
 116       c->rbi->next = bb->rbi->next;
 117     }
 118
 119   if(bb1->rbi->next == NULL)
 120     {
 121       bb1->rbi->next=bb;
 122       bb->rbi->next=NULL;
 123     }
 124   else
 125
 126     {
 127       basic_block tmp;
 128
 129       tmp = bb1->rbi->next;
 130       bb1->rbi->next = bb;
 131       bb->rbi->next = tmp;
 132     }
 133 }
 134
 135 /* Finalize loop optimizer.  */
 136 void
 137 loop_optimizer_finalize (struct loops *loops, FILE *dumpfile)
 138 {
 139   basic_block bb;
 140   unsigned int i;
 141
 142   /* Finalize layout changes.  */
 143   /* Make chain.  */
 144   FOR_EACH_BB (bb)
 145     if (bb->next_bb != EXIT_BLOCK_PTR)
 146       bb->rbi->next = bb->next_bb;
 147
 148   /* Another dump.  */
 149   flow_loops_dump (loops, dumpfile, NULL, 1);
 150
 151   /* For loops ending with a branch and count instruction, move the basic
 152      block found before the unrolling on the fallthru path of this branch,
 153      after the unrolled code.  This will allow branch simplification.  */
 154   for (i = 1; i < loops->num; i++)
 155     {
 156       struct loop *loop = loops->parray[i];
 157       struct loop_desc *desc;
 158       basic_block loop_real_latch, bb, bb_exit;
 159       edge e;
 160
 161       if (loop == NULL)
 162         continue;
 163       if (!loop->simple)
 164         continue;
 165       if (!loop->has_desc)
 166         continue;
 167
 168       if (loop->lpt_decision.decision != LPT_UNROLL_RUNTIME)
 169         continue;
 170
 171       desc = &loop->desc;
 172       if (desc == NULL)
 173         continue;
 174       if (loop->latch->pred == NULL)
 175         continue;
 176
 177       loop_real_latch = loop->latch->pred->src;
 178
 179
 180       if (desc->postincr)
 181         continue;
 182       if (!is_bct_cond (BB_END (loop_real_latch)))
 183          continue;
 184
 185       for (e = loop_real_latch->succ; e ; e = e->succ_next)
 186         if (e->flags & EDGE_FALLTHRU)
 187           break;
 188
 189       if (e == NULL)
 190         continue;
 191
 192       bb_exit = e->dest;
 193
 194       bb = NULL;
 195
 196       /* Leave the case of the bb_exit falling through to exit to
 197          fixed_fallthru_exit_predecessor */
 198       for (e = EXIT_BLOCK_PTR->pred; e; e = e->pred_next)
 199          if (e->flags & EDGE_FALLTHRU)
 200         bb = e->src;
 201
 202       if (bb_exit == bb)
 203         continue;
 204
 205       fixup_loop_exit_succesor (bb_exit, loop->latch);
 206     }
 207
 208   /* Clean up.  */
 209   flow_loops_free (loops);
 210   free_dominance_info (CDI_DOMINATORS);
 211   free (loops);
 212
 213   /* Finalize changes.  */
 214   cfg_layout_finalize ();
 215
 216   /* Checking.  */
 217 #ifdef ENABLE_CHECKING
 218   verify_flow_info ();
 219 #endif
 220 }