* opt-functions.awk (var_type): New function.
[official-gcc.git] / gcc / tree-ssa-loop-ch.c
blob378755c9eaa36791a93dc37bfd19a7ce944f2738
1 /* Loop header copying on trees.
2 Copyright (C) 2004, 2005 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it
7 under the terms of the GNU General Public License as published by the
8 Free Software Foundation; either version 2, or (at your option) any
9 later version.
11 GCC is distributed in the hope that it will be useful, but WITHOUT
12 ANY 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.
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. */
21 #include "config.h"
22 #include "system.h"
23 #include "coretypes.h"
24 #include "tm.h"
25 #include "tree.h"
26 #include "rtl.h"
27 #include "tm_p.h"
28 #include "hard-reg-set.h"
29 #include "basic-block.h"
30 #include "output.h"
31 #include "diagnostic.h"
32 #include "tree-flow.h"
33 #include "tree-dump.h"
34 #include "tree-pass.h"
35 #include "timevar.h"
36 #include "cfgloop.h"
37 #include "tree-inline.h"
38 #include "flags.h"
39 #include "tree-inline.h"
41 /* Duplicates headers of loops if they are small enough, so that the statements
42 in the loop body are always executed when the loop is entered. This
43 increases effectiveness of code motion optimizations, and reduces the need
44 for loop preconditioning. */
46 /* Check whether we should duplicate HEADER of LOOP. At most *LIMIT
47 instructions should be duplicated, limit is decreased by the actual
48 amount. */
50 static bool
51 should_duplicate_loop_header_p (basic_block header, struct loop *loop,
52 int *limit)
54 block_stmt_iterator bsi;
55 tree last;
57 /* Do not copy one block more than once (we do not really want to do
58 loop peeling here). */
59 if (header->aux)
60 return false;
62 gcc_assert (EDGE_COUNT (header->succs) > 0);
63 if (single_succ_p (header))
64 return false;
65 if (flow_bb_inside_loop_p (loop, EDGE_SUCC (header, 0)->dest)
66 && flow_bb_inside_loop_p (loop, EDGE_SUCC (header, 1)->dest))
67 return false;
69 /* If this is not the original loop header, we want it to have just
70 one predecessor in order to match the && pattern. */
71 if (header != loop->header && !single_pred_p (header))
72 return false;
74 last = last_stmt (header);
75 if (TREE_CODE (last) != COND_EXPR)
76 return false;
78 /* Approximately copy the conditions that used to be used in jump.c --
79 at most 20 insns and no calls. */
80 for (bsi = bsi_start (header); !bsi_end_p (bsi); bsi_next (&bsi))
82 last = bsi_stmt (bsi);
84 if (TREE_CODE (last) == LABEL_EXPR)
85 continue;
87 if (get_call_expr_in (last))
88 return false;
90 *limit -= estimate_num_insns (last);
91 if (*limit < 0)
92 return false;
95 return true;
98 /* Checks whether LOOP is a do-while style loop. */
100 static bool
101 do_while_loop_p (struct loop *loop)
103 tree stmt = last_stmt (loop->latch);
105 /* If the latch of the loop is not empty, it is not a do-while loop. */
106 if (stmt
107 && TREE_CODE (stmt) != LABEL_EXPR)
108 return false;
110 /* If the header contains just a condition, it is not a do-while loop. */
111 stmt = last_and_only_stmt (loop->header);
112 if (stmt
113 && TREE_CODE (stmt) == COND_EXPR)
114 return false;
116 return true;
119 /* For all loops, copy the condition at the end of the loop body in front
120 of the loop. This is beneficial since it increases efficiency of
121 code motion optimizations. It also saves one jump on entry to the loop. */
123 static void
124 copy_loop_headers (void)
126 struct loops *loops;
127 unsigned i;
128 struct loop *loop;
129 basic_block header;
130 edge exit, entry;
131 basic_block *bbs, *copied_bbs;
132 unsigned n_bbs;
133 unsigned bbs_size;
135 loops = loop_optimizer_init (dump_file);
136 if (!loops)
137 return;
139 /* We do not try to keep the information about irreducible regions
140 up-to-date. */
141 loops->state &= ~LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS;
143 #ifdef ENABLE_CHECKING
144 verify_loop_structure (loops);
145 #endif
147 bbs = xmalloc (sizeof (basic_block) * n_basic_blocks);
148 copied_bbs = xmalloc (sizeof (basic_block) * n_basic_blocks);
149 bbs_size = n_basic_blocks;
151 for (i = 1; i < loops->num; i++)
153 /* Copy at most 20 insns. */
154 int limit = 20;
156 loop = loops->parray[i];
157 if (!loop)
158 continue;
159 header = loop->header;
161 /* If the loop is already a do-while style one (either because it was
162 written as such, or because jump threading transformed it into one),
163 we might be in fact peeling the first iteration of the loop. This
164 in general is not a good idea. */
165 if (do_while_loop_p (loop))
166 continue;
168 /* Iterate the header copying up to limit; this takes care of the cases
169 like while (a && b) {...}, where we want to have both of the conditions
170 copied. TODO -- handle while (a || b) - like cases, by not requiring
171 the header to have just a single successor and copying up to
172 postdominator. */
174 exit = NULL;
175 n_bbs = 0;
176 while (should_duplicate_loop_header_p (header, loop, &limit))
178 /* Find a successor of header that is inside a loop; i.e. the new
179 header after the condition is copied. */
180 if (flow_bb_inside_loop_p (loop, EDGE_SUCC (header, 0)->dest))
181 exit = EDGE_SUCC (header, 0);
182 else
183 exit = EDGE_SUCC (header, 1);
184 bbs[n_bbs++] = header;
185 gcc_assert (bbs_size > n_bbs);
186 header = exit->dest;
189 if (!exit)
190 continue;
192 if (dump_file && (dump_flags & TDF_DETAILS))
193 fprintf (dump_file,
194 "Duplicating header of the loop %d up to edge %d->%d.\n",
195 loop->num, exit->src->index, exit->dest->index);
197 /* Ensure that the header will have just the latch as a predecessor
198 inside the loop. */
199 if (!single_pred_p (exit->dest))
200 exit = single_succ_edge (loop_split_edge_with (exit, NULL));
202 entry = loop_preheader_edge (loop);
204 if (!tree_duplicate_sese_region (entry, exit, bbs, n_bbs, copied_bbs))
206 fprintf (dump_file, "Duplication failed.\n");
207 continue;
210 /* Ensure that the latch and the preheader is simple (we know that they
211 are not now, since there was the loop exit condition. */
212 loop_split_edge_with (loop_preheader_edge (loop), NULL);
213 loop_split_edge_with (loop_latch_edge (loop), NULL);
216 free (bbs);
217 free (copied_bbs);
219 loop_optimizer_finalize (loops, NULL);
222 static bool
223 gate_ch (void)
225 return flag_tree_ch != 0;
228 struct tree_opt_pass pass_ch =
230 "ch", /* name */
231 gate_ch, /* gate */
232 copy_loop_headers, /* execute */
233 NULL, /* sub */
234 NULL, /* next */
235 0, /* static_pass_number */
236 TV_TREE_CH, /* tv_id */
237 PROP_cfg | PROP_ssa, /* properties_required */
238 0, /* properties_provided */
239 0, /* properties_destroyed */
240 0, /* todo_flags_start */
241 TODO_cleanup_cfg | TODO_dump_func
242 | TODO_verify_ssa, /* todo_flags_finish */
243 0 /* letter */