OpenCores
URL https://opencores.org/ocsvn/openrisc/openrisc/trunk

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-stable/] [gcc-4.5.1/] [gcc/] [sese.h] - Blame information for rev 859

Go to most recent revision | Details | Compare with Previous | View Log

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

powered by: WebSVN 2.1.0

© copyright 1999-2024 OpenCores.org, equivalent to Oliscience, all rights reserved. OpenCores®, registered trademark.