* gcc.dg/const-elim-1.c: Remove xfail for xtensa-*-*.
[official-gcc.git] / gcc / tree-ssa-loop-ch.c
blob18afec1e079265f458678f9dfb92c2b5555c7e78
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;
134 gcov_type entry_count, body_count, total_count;
136 loops = loop_optimizer_init (dump_file);
137 if (!loops)
138 return;
139 rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
141 /* We do not try to keep the information about irreducible regions
142 up-to-date. */
143 loops->state &= ~LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS;
145 #ifdef ENABLE_CHECKING
146 verify_loop_structure (loops);
147 #endif
149 bbs = xmalloc (sizeof (basic_block) * n_basic_blocks);
150 copied_bbs = xmalloc (sizeof (basic_block) * n_basic_blocks);
151 bbs_size = n_basic_blocks;
153 for (i = 1; i < loops->num; i++)
155 /* Copy at most 20 insns. */
156 int limit = 20;
158 loop = loops->parray[i];
159 if (!loop)
160 continue;
161 header = loop->header;
163 /* If the loop is already a do-while style one (either because it was
164 written as such, or because jump threading transformed it into one),
165 we might be in fact peeling the first iteration of the loop. This
166 in general is not a good idea. */
167 if (do_while_loop_p (loop))
168 continue;
170 /* Iterate the header copying up to limit; this takes care of the cases
171 like while (a && b) {...}, where we want to have both of the conditions
172 copied. TODO -- handle while (a || b) - like cases, by not requiring
173 the header to have just a single successor and copying up to
174 postdominator. */
176 exit = NULL;
177 n_bbs = 0;
178 while (should_duplicate_loop_header_p (header, loop, &limit))
180 /* Find a successor of header that is inside a loop; i.e. the new
181 header after the condition is copied. */
182 if (flow_bb_inside_loop_p (loop, EDGE_SUCC (header, 0)->dest))
183 exit = EDGE_SUCC (header, 0);
184 else
185 exit = EDGE_SUCC (header, 1);
186 bbs[n_bbs++] = header;
187 gcc_assert (bbs_size > n_bbs);
188 header = exit->dest;
191 if (!exit)
192 continue;
194 if (dump_file && (dump_flags & TDF_DETAILS))
195 fprintf (dump_file,
196 "Duplicating header of the loop %d up to edge %d->%d.\n",
197 loop->num, exit->src->index, exit->dest->index);
199 /* Ensure that the header will have just the latch as a predecessor
200 inside the loop. */
201 if (!single_pred_p (exit->dest))
202 exit = single_succ_edge (loop_split_edge_with (exit, NULL));
204 entry = loop_preheader_edge (loop);
205 entry_count = entry->src->count;
206 body_count = exit->dest->count;
208 if (!tree_duplicate_sese_region (entry, exit, bbs, n_bbs, copied_bbs))
210 fprintf (dump_file, "Duplication failed.\n");
211 continue;
214 /* Fix profiling info. Scaling is done in gcov_type arithmetic to
215 avoid losing information; this is slow, but is done at most
216 once per loop. We special case 0 to avoid division by 0;
217 probably other special cases exist. */
218 total_count = body_count + entry_count;
219 if (total_count == 0LL)
221 scale_bbs_frequencies_int (bbs, n_bbs, 0, 1);
222 scale_bbs_frequencies_int (copied_bbs, n_bbs, 0, 1);
224 else
226 scale_bbs_frequencies_gcov_type (bbs, n_bbs, body_count, total_count);
227 scale_bbs_frequencies_gcov_type (copied_bbs, n_bbs, entry_count,
228 total_count);
231 /* Ensure that the latch and the preheader is simple (we know that they
232 are not now, since there was the loop exit condition. */
233 loop_split_edge_with (loop_preheader_edge (loop), NULL);
234 loop_split_edge_with (loop_latch_edge (loop), NULL);
237 free (bbs);
238 free (copied_bbs);
240 loop_optimizer_finalize (loops, NULL);
243 static bool
244 gate_ch (void)
246 return flag_tree_ch != 0;
249 struct tree_opt_pass pass_ch =
251 "ch", /* name */
252 gate_ch, /* gate */
253 copy_loop_headers, /* execute */
254 NULL, /* sub */
255 NULL, /* next */
256 0, /* static_pass_number */
257 TV_TREE_CH, /* tv_id */
258 PROP_cfg | PROP_ssa, /* properties_required */
259 0, /* properties_provided */
260 0, /* properties_destroyed */
261 0, /* todo_flags_start */
262 TODO_cleanup_cfg | TODO_dump_func
263 | TODO_verify_ssa, /* todo_flags_finish */
264 0 /* letter */