loop-init.c revision 132718 
1/* Loop optimizer initialization routines.
2   Copyright (C) 2002, 2003, 2004 Free Software Foundation, Inc.
3
4This file is part of GCC.
5
6GCC is free software; you can redistribute it and/or modify it under
7the terms of the GNU General Public License as published by the Free
8Software Foundation; either version 2, or (at your option) any later
9version.
10
11GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12WARRANTY; without even the implied warranty of MERCHANTABILITY or
13FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
14for more details.
15
16You should have received a copy of the GNU General Public License
17along with GCC; see the file COPYING.  If not, write to the Free
18Software Foundation, 59 Temple Place - Suite 330, Boston, MA
1902111-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
31static void fixup_loop_exit_succesor (basic_block, basic_block);
32
33/* Initialize loop optimizer.  */
34
35struct loops *
36loop_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 (0);
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.  */
96static void
97fixup_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.  */
136void
137loop_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}
221