Mercurial > hg > CbC > CbC_gcc

comparison gcc/sese.h @ 55:77e2b8dfacca gcc-4.4.5

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
update it from 4.4.3 to 4.5.0
author ryoma <e075725@ie.u-ryukyu.ac.jp>
date Fri, 12 Feb 2010 23:39:51 +0900
parents
children b7f97abdc517
comparison
equal deleted inserted replaced
52:c156f1bd5cd9 55:77e2b8dfacca
1 /* Single entry single exit control flow regions.
2 Copyright (C) 2008, 2009 Free Software Foundation, Inc.
3 Contributed by Jan Sjodin <jan.sjodin@amd.com> and
4 Sebastian Pop <sebastian.pop@amd.com>.
5
6 This file is part of GCC.
7
8 GCC is free software; you can redistribute it and/or modify
9 it under the terms of the GNU General Public License as published by
10 the Free Software Foundation; either version 3, or (at your option)
11 any later version.
12
13 GCC is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 GNU General Public License for more details.
17
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
21
22 #ifndef GCC_SESE_H
23 #define GCC_SESE_H
24
25 /* A Single Entry, Single Exit region is a part of the CFG delimited
26 by two edges. */
27 typedef struct sese_s
28 {
29 /* Single ENTRY and single EXIT from the SESE region. */
30 edge entry, exit;
31
32 /* Parameters used within the SCOP. */
33 VEC (tree, heap) *params;
34
35 /* Loops completely contained in the SCOP. */
36 bitmap loops;
37 VEC (loop_p, heap) *loop_nest;
38
39 /* Are we allowed to add more params? This is for debugging purpose. We
40 can only add new params before generating the bb domains, otherwise they
41 become invalid. */
42 bool add_params;
43 } *sese;
44
45 #define SESE_ENTRY(S) (S->entry)
46 #define SESE_ENTRY_BB(S) (S->entry->dest)
47 #define SESE_EXIT(S) (S->exit)
48 #define SESE_EXIT_BB(S) (S->exit->dest)
49 #define SESE_PARAMS(S) (S->params)
50 #define SESE_LOOPS(S) (S->loops)
51 #define SESE_LOOP_NEST(S) (S->loop_nest)
52 #define SESE_ADD_PARAMS(S) (S->add_params)
53
54 extern sese new_sese (edge, edge);
55 extern void free_sese (sese);
56 extern void sese_insert_phis_for_liveouts (sese, basic_block, edge, edge);
57 extern void sese_adjust_liveout_phis (sese, htab_t, basic_block, edge, edge);
58 extern void build_sese_loop_nests (sese);
59 extern edge copy_bb_and_scalar_dependences (basic_block, sese, edge, htab_t);
60 extern struct loop *outermost_loop_in_sese (sese, basic_block);
61 extern void insert_loop_close_phis (htab_t, loop_p);
62 extern void insert_guard_phis (basic_block, edge, edge, htab_t, htab_t);
63 extern tree scalar_evolution_in_region (sese, loop_p, tree);
64
65 /* Check that SESE contains LOOP. */
66
67 static inline bool
68 sese_contains_loop (sese sese, struct loop *loop)
69 {
70 return bitmap_bit_p (SESE_LOOPS (sese), loop->num);
71 }
72
73 /* The number of parameters in REGION. */
74
75 static inline unsigned
76 sese_nb_params (sese region)
77 {
78 return VEC_length (tree, SESE_PARAMS (region));
79 }
80
81 /* Checks whether BB is contained in the region delimited by ENTRY and
82 EXIT blocks. */
83
84 static inline bool
85 bb_in_region (basic_block bb, basic_block entry, basic_block exit)
86 {
87 #ifdef ENABLE_CHECKING
88 {
89 edge e;
90 edge_iterator ei;
91
92 /* Check that there are no edges coming in the region: all the
93 predecessors of EXIT are dominated by ENTRY. */
94 FOR_EACH_EDGE (e, ei, exit->preds)
95 dominated_by_p (CDI_DOMINATORS, e->src, entry);
96
97 /* Check that there are no edges going out of the region: the
98 entry is post-dominated by the exit. FIXME: This cannot be
99 checked right now as the CDI_POST_DOMINATORS are needed. */
100 }
101 #endif
102
103 return dominated_by_p (CDI_DOMINATORS, bb, entry)
104 && !(dominated_by_p (CDI_DOMINATORS, bb, exit)
105 && !dominated_by_p (CDI_DOMINATORS, entry, exit));
106 }
107
108 /* Checks whether BB is contained in the region delimited by ENTRY and
109 EXIT blocks. */
110
111 static inline bool
112 bb_in_sese_p (basic_block bb, sese region)
113 {
114 basic_block entry = SESE_ENTRY_BB (region);
115 basic_block exit = SESE_EXIT_BB (region);
116
117 return bb_in_region (bb, entry, exit);
118 }
119
120 /* Returns true when NAME is defined in REGION. */
121
122 static inline bool
123 defined_in_sese_p (tree name, sese region)
124 {
125 gimple stmt = SSA_NAME_DEF_STMT (name);
126 basic_block bb = gimple_bb (stmt);
127
128 return bb && bb_in_sese_p (bb, region);
129 }
130
131 /* Returns true when LOOP is in REGION. */
132
133 static inline bool
134 loop_in_sese_p (struct loop *loop, sese region)
135 {
136 return (bb_in_sese_p (loop->header, region)
137 && bb_in_sese_p (loop->latch, region));
138 }
139
140 /* Returns the loop depth of LOOP in REGION. The loop depth
141 is the same as the normal loop depth, but limited by a region.
142
143 Example:
144
145 loop_0
146 loop_1
147 {
148 S0
149 <- region start
150 S1
151
152 loop_2
153 S2
154
155 S3
156 <- region end
157 }
158
159 loop_0 does not exist in the region -> invalid
160 loop_1 exists, but is not completely contained in the region -> depth 0
161 loop_2 is completely contained -> depth 1 */
162
163 static inline unsigned int
164 sese_loop_depth (sese region, loop_p loop)
165 {
166 unsigned int depth = 0;
167
168 gcc_assert ((!loop_in_sese_p (loop, region)
169 && (SESE_ENTRY_BB (region)->loop_father == loop
170 || SESE_EXIT (region)->src->loop_father == loop))
171 || loop_in_sese_p (loop, region));
172
173 while (loop_in_sese_p (loop, region))
174 {
175 depth++;
176 loop = loop_outer (loop);
177 }
178
179 return depth;
180 }
181
182 /* Splits BB to make a single entry single exit region. */
183
184 static inline sese
185 split_region_for_bb (basic_block bb)
186 {
187 edge entry, exit;
188
189 if (single_pred_p (bb))
190 entry = single_pred_edge (bb);
191 else
192 {
193 entry = split_block_after_labels (bb);
194 bb = single_succ (bb);
195 }
196
197 if (single_succ_p (bb))
198 exit = single_succ_edge (bb);
199 else
200 {
201 gimple_stmt_iterator gsi = gsi_last_bb (bb);
202 gsi_prev (&gsi);
203 exit = split_block (bb, gsi_stmt (gsi));
204 }
205
206 return new_sese (entry, exit);
207 }
208
209 /* Returns the block preceding the entry of a SESE. */
210
211 static inline basic_block
212 block_before_sese (sese sese)
213 {
214 return SESE_ENTRY (sese)->src;
215 }
216
217
218
219 /* A single entry single exit specialized for conditions. */
220
221 typedef struct ifsese_s {
222 sese region;
223 sese true_region;
224 sese false_region;
225 } *ifsese;
226
227 extern void if_region_set_false_region (ifsese, sese);
228 extern ifsese create_if_region_on_edge (edge, tree);
229 extern ifsese move_sese_in_condition (sese);
230 extern edge get_true_edge_from_guard_bb (basic_block);
231 extern edge get_false_edge_from_guard_bb (basic_block);
232
233 static inline edge
234 if_region_entry (ifsese if_region)
235 {
236 return SESE_ENTRY (if_region->region);
237 }
238
239 static inline edge
240 if_region_exit (ifsese if_region)
241 {
242 return SESE_EXIT (if_region->region);
243 }
244
245 static inline basic_block
246 if_region_get_condition_block (ifsese if_region)
247 {
248 return if_region_entry (if_region)->dest;
249 }
250
251 /* Structure containing the mapping between the old names and the new
252 names used after block copy in the new loop context. */
253 typedef struct rename_map_elt_s
254 {
255 tree old_name, expr;
256 } *rename_map_elt;
257
258 DEF_VEC_P(rename_map_elt);
259 DEF_VEC_ALLOC_P (rename_map_elt, heap);
260
261 extern void debug_rename_map (htab_t);
262 extern hashval_t rename_map_elt_info (const void *);
263 extern int eq_rename_map_elts (const void *, const void *);
264 extern void set_rename (htab_t, tree, tree);
265
266 /* Constructs a new SCEV_INFO_STR structure for VAR and INSTANTIATED_BELOW. */
267
268 static inline rename_map_elt
269 new_rename_map_elt (tree old_name, tree expr)
270 {
271 rename_map_elt res;
272
273 res = XNEW (struct rename_map_elt_s);
274 res->old_name = old_name;
275 res->expr = expr;
276
277 return res;
278 }
279
280 /* Structure containing the mapping between the CLooG's induction
281 variable and the type of the old induction variable. */
282 typedef struct ivtype_map_elt_s
283 {
284 tree type;
285 const char *cloog_iv;
286 } *ivtype_map_elt;
287
288 extern void debug_ivtype_map (htab_t);
289 extern hashval_t ivtype_map_elt_info (const void *);
290 extern int eq_ivtype_map_elts (const void *, const void *);
291
292 /* Constructs a new SCEV_INFO_STR structure for VAR and INSTANTIATED_BELOW. */
293
294 static inline ivtype_map_elt
295 new_ivtype_map_elt (const char *cloog_iv, tree type)
296 {
297 ivtype_map_elt res;
298
299 res = XNEW (struct ivtype_map_elt_s);
300 res->cloog_iv = cloog_iv;
301 res->type = type;
302
303 return res;
304 }
305
306 /* Free and compute again all the dominators information. */
307
308 static inline void
309 recompute_all_dominators (void)
310 {
311 mark_irreducible_loops ();
312 free_dominance_info (CDI_DOMINATORS);
313 free_dominance_info (CDI_POST_DOMINATORS);
314 calculate_dominance_info (CDI_DOMINATORS);
315 calculate_dominance_info (CDI_POST_DOMINATORS);
316 }
317
318 typedef struct gimple_bb
319 {
320 basic_block bb;
321
322 /* Lists containing the restrictions of the conditional statements
323 dominating this bb. This bb can only be executed, if all conditions
324 are true.
325
326 Example:
327
328 for (i = 0; i <= 20; i++)
329 {
330 A
331
332 if (2i <= 8)
333 B
334 }
335
336 So for B there is an additional condition (2i <= 8).
337
338 List of COND_EXPR and SWITCH_EXPR. A COND_EXPR is true only if the
339 corresponding element in CONDITION_CASES is not NULL_TREE. For a
340 SWITCH_EXPR the corresponding element in CONDITION_CASES is a
341 CASE_LABEL_EXPR. */
342 VEC (gimple, heap) *conditions;
343 VEC (gimple, heap) *condition_cases;
344 VEC (data_reference_p, heap) *data_refs;
345 htab_t cloog_iv_types;
346 } *gimple_bb_p;
347
348 #define GBB_BB(GBB) GBB->bb
349 #define GBB_DATA_REFS(GBB) GBB->data_refs
350 #define GBB_CONDITIONS(GBB) GBB->conditions
351 #define GBB_CONDITION_CASES(GBB) GBB->condition_cases
352 #define GBB_CLOOG_IV_TYPES(GBB) GBB->cloog_iv_types
353
354 /* Return the innermost loop that contains the basic block GBB. */
355
356 static inline struct loop *
357 gbb_loop (struct gimple_bb *gbb)
358 {
359 return GBB_BB (gbb)->loop_father;
360 }
361
362 /* Returns the gimple loop, that corresponds to the loop_iterator_INDEX.
363 If there is no corresponding gimple loop, we return NULL. */
364
365 static inline loop_p
366 gbb_loop_at_index (gimple_bb_p gbb, sese region, int index)
367 {
368 loop_p loop = gbb_loop (gbb);
369 int depth = sese_loop_depth (region, loop);
370
371 while (--depth > index)
372 loop = loop_outer (loop);
373
374 gcc_assert (sese_contains_loop (region, loop));
375
376 return loop;
377 }
378
379 /* The number of common loops in REGION for GBB1 and GBB2. */
380
381 static inline int
382 nb_common_loops (sese region, gimple_bb_p gbb1, gimple_bb_p gbb2)
383 {
384 loop_p l1 = gbb_loop (gbb1);
385 loop_p l2 = gbb_loop (gbb2);
386 loop_p common = find_common_loop (l1, l2);
387
388 return sese_loop_depth (region, common);
389 }
390
391 extern void print_gimple_bb (FILE *, gimple_bb_p, int, int);
392 extern void debug_gbb (gimple_bb_p, int);
393
394 #endif