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

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-dev/] [or1k-gcc/] [gcc/] [sese.h] - Blame information for rev 720

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

Line No. Rev Author Line
1 684 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 build_sese_loop_nests (sese);
59
extern edge copy_bb_and_scalar_dependences (basic_block, sese, edge,
60
                                            VEC (tree, heap) *, bool *);
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
#endif
99
 
100
  return dominated_by_p (CDI_DOMINATORS, bb, entry)
101
         && !(dominated_by_p (CDI_DOMINATORS, bb, exit)
102
              && !dominated_by_p (CDI_DOMINATORS, entry, exit));
103
}
104
 
105
/* Checks whether BB is contained in the region delimited by ENTRY and
106
   EXIT blocks.  */
107
 
108
static inline bool
109
bb_in_sese_p (basic_block bb, sese region)
110
{
111
  basic_block entry = SESE_ENTRY_BB (region);
112
  basic_block exit = SESE_EXIT_BB (region);
113
 
114
  return bb_in_region (bb, entry, exit);
115
}
116
 
117
/* Returns true when STMT is defined in REGION.  */
118
 
119
static inline bool
120
stmt_in_sese_p (gimple stmt, sese region)
121
{
122
  basic_block bb = gimple_bb (stmt);
123
  return bb && bb_in_sese_p (bb, region);
124
}
125
 
126
/* Returns true when NAME is defined in REGION.  */
127
 
128
static inline bool
129
defined_in_sese_p (tree name, sese region)
130
{
131
  gimple stmt = SSA_NAME_DEF_STMT (name);
132
  return stmt_in_sese_p (stmt, region);
133
}
134
 
135
/* Returns true when LOOP is in REGION.  */
136
 
137
static inline bool
138
loop_in_sese_p (struct loop *loop, sese region)
139
{
140
  return (bb_in_sese_p (loop->header, region)
141
          && bb_in_sese_p (loop->latch, region));
142
}
143
 
144
/* Returns the loop depth of LOOP in REGION.  The loop depth
145
   is the same as the normal loop depth, but limited by a region.
146
 
147
   Example:
148
 
149
   loop_0
150
     loop_1
151
       {
152
         S0
153
            <- region start
154
         S1
155
 
156
         loop_2
157
           S2
158
 
159
         S3
160
            <- region end
161
       }
162
 
163
    loop_0 does not exist in the region -> invalid
164
    loop_1 exists, but is not completely contained in the region -> depth 0
165
    loop_2 is completely contained -> depth 1  */
166
 
167
static inline unsigned int
168
sese_loop_depth (sese region, loop_p loop)
169
{
170
  unsigned int depth = 0;
171
 
172
  gcc_assert ((!loop_in_sese_p (loop, region)
173
               && (SESE_ENTRY_BB (region)->loop_father == loop
174
                   || SESE_EXIT (region)->src->loop_father == loop))
175
              || loop_in_sese_p (loop, region));
176
 
177
  while (loop_in_sese_p (loop, region))
178
    {
179
      depth++;
180
      loop = loop_outer (loop);
181
    }
182
 
183
  return depth;
184
}
185
 
186
/* Splits BB to make a single entry single exit region.  */
187
 
188
static inline sese
189
split_region_for_bb (basic_block bb)
190
{
191
  edge entry, exit;
192
 
193
  if (single_pred_p (bb))
194
    entry = single_pred_edge (bb);
195
  else
196
    {
197
      entry = split_block_after_labels (bb);
198
      bb = single_succ (bb);
199
    }
200
 
201
  if (single_succ_p (bb))
202
    exit = single_succ_edge (bb);
203
  else
204
    {
205
      gimple_stmt_iterator gsi = gsi_last_bb (bb);
206
      gsi_prev (&gsi);
207
      exit = split_block (bb, gsi_stmt (gsi));
208
    }
209
 
210
  return new_sese (entry, exit);
211
}
212
 
213
/* Returns the block preceding the entry of a SESE.  */
214
 
215
static inline basic_block
216
block_before_sese (sese sese)
217
{
218
  return SESE_ENTRY (sese)->src;
219
}
220
 
221
 
222
 
223
/* A single entry single exit specialized for conditions.  */
224
 
225
typedef struct ifsese_s {
226
  sese region;
227
  sese true_region;
228
  sese false_region;
229
} *ifsese;
230
 
231
extern void if_region_set_false_region (ifsese, sese);
232
extern ifsese move_sese_in_condition (sese);
233
extern edge get_true_edge_from_guard_bb (basic_block);
234
extern edge get_false_edge_from_guard_bb (basic_block);
235
extern void set_ifsese_condition (ifsese, tree);
236
 
237
static inline edge
238
if_region_entry (ifsese if_region)
239
{
240
  return SESE_ENTRY (if_region->region);
241
}
242
 
243
static inline edge
244
if_region_exit (ifsese if_region)
245
{
246
  return SESE_EXIT (if_region->region);
247
}
248
 
249
static inline basic_block
250
if_region_get_condition_block (ifsese if_region)
251
{
252
  return if_region_entry (if_region)->dest;
253
}
254
 
255
/* Structure containing the mapping between the old names and the new
256
   names used after block copy in the new loop context.  */
257
typedef struct rename_map_elt_s
258
{
259
  tree old_name, expr;
260
} *rename_map_elt;
261
 
262
DEF_VEC_P(rename_map_elt);
263
DEF_VEC_ALLOC_P (rename_map_elt, heap);
264
 
265
extern void debug_rename_map (htab_t);
266
extern hashval_t rename_map_elt_info (const void *);
267
extern int eq_rename_map_elts (const void *, const void *);
268
 
269
/* Constructs a new SCEV_INFO_STR structure for VAR and INSTANTIATED_BELOW.  */
270
 
271
static inline rename_map_elt
272
new_rename_map_elt (tree old_name, tree expr)
273
{
274
  rename_map_elt res;
275
 
276
  res = XNEW (struct rename_map_elt_s);
277
  res->old_name = old_name;
278
  res->expr = expr;
279
 
280
  return res;
281
}
282
 
283
/* Structure containing the mapping between the CLooG's induction
284
   variable and the type of the old induction variable.  */
285
typedef struct ivtype_map_elt_s
286
{
287
  tree type;
288
  const char *cloog_iv;
289
} *ivtype_map_elt;
290
 
291
extern void debug_ivtype_map (htab_t);
292
extern hashval_t ivtype_map_elt_info (const void *);
293
extern int eq_ivtype_map_elts (const void *, const void *);
294
 
295
/* Constructs a new SCEV_INFO_STR structure for VAR and INSTANTIATED_BELOW.  */
296
 
297
static inline ivtype_map_elt
298
new_ivtype_map_elt (const char *cloog_iv, tree type)
299
{
300
  ivtype_map_elt res;
301
 
302
  res = XNEW (struct ivtype_map_elt_s);
303
  res->cloog_iv = cloog_iv;
304
  res->type = type;
305
 
306
  return res;
307
}
308
 
309
/* Free and compute again all the dominators information.  */
310
 
311
static inline void
312
recompute_all_dominators (void)
313
{
314
  mark_irreducible_loops ();
315
  free_dominance_info (CDI_DOMINATORS);
316
  calculate_dominance_info (CDI_DOMINATORS);
317
}
318
 
319
typedef struct gimple_bb
320
{
321
  basic_block bb;
322
  struct poly_bb *pbb;
323
 
324
  /* Lists containing the restrictions of the conditional statements
325
     dominating this bb.  This bb can only be executed, if all conditions
326
     are true.
327
 
328
     Example:
329
 
330
     for (i = 0; i <= 20; i++)
331
     {
332
       A
333
 
334
       if (2i <= 8)
335
         B
336
     }
337
 
338
     So for B there is an additional condition (2i <= 8).
339
 
340
     List of COND_EXPR and SWITCH_EXPR.  A COND_EXPR is true only if the
341
     corresponding element in CONDITION_CASES is not NULL_TREE.  For a
342
     SWITCH_EXPR the corresponding element in CONDITION_CASES is a
343
     CASE_LABEL_EXPR.  */
344
  VEC (gimple, heap) *conditions;
345
  VEC (gimple, heap) *condition_cases;
346
  VEC (data_reference_p, heap) *data_refs;
347
} *gimple_bb_p;
348
 
349
#define GBB_BB(GBB) (GBB)->bb
350
#define GBB_PBB(GBB) (GBB)->pbb
351
#define GBB_DATA_REFS(GBB) (GBB)->data_refs
352
#define GBB_CONDITIONS(GBB) (GBB)->conditions
353
#define GBB_CONDITION_CASES(GBB) (GBB)->condition_cases
354
 
355
/* Return the innermost loop that contains the basic block GBB.  */
356
 
357
static inline struct loop *
358
gbb_loop (struct gimple_bb *gbb)
359
{
360
  return GBB_BB (gbb)->loop_father;
361
}
362
 
363
/* Returns the gimple loop, that corresponds to the loop_iterator_INDEX.
364
   If there is no corresponding gimple loop, we return NULL.  */
365
 
366
static inline loop_p
367
gbb_loop_at_index (gimple_bb_p gbb, sese region, int index)
368
{
369
  loop_p loop = gbb_loop (gbb);
370
  int depth = sese_loop_depth (region, loop);
371
 
372
  while (--depth > index)
373
    loop = loop_outer (loop);
374
 
375
  gcc_assert (sese_contains_loop (region, loop));
376
 
377
  return loop;
378
}
379
 
380
/* The number of common loops in REGION for GBB1 and GBB2.  */
381
 
382
static inline int
383
nb_common_loops (sese region, gimple_bb_p gbb1, gimple_bb_p gbb2)
384
{
385
  loop_p l1 = gbb_loop (gbb1);
386
  loop_p l2 = gbb_loop (gbb2);
387
  loop_p common = find_common_loop (l1, l2);
388
 
389
  return sese_loop_depth (region, common);
390
}
391
 
392
/* Return true when DEF can be analyzed in REGION by the scalar
393
   evolution analyzer.  */
394
 
395
static inline bool
396
scev_analyzable_p (tree def, sese region)
397
{
398
  loop_p loop;
399
  tree scev;
400
  tree type = TREE_TYPE (def);
401
 
402
  /* When Graphite generates code for a scev, the code generator
403
     expresses the scev in function of a single induction variable.
404
     This is unsafe for floating point computations, as it may replace
405
     a floating point sum reduction with a multiplication.  The
406
     following test returns false for non integer types to avoid such
407
     problems.  */
408
  if (!INTEGRAL_TYPE_P (type)
409
      && !POINTER_TYPE_P (type))
410
    return false;
411
 
412
  loop = loop_containing_stmt (SSA_NAME_DEF_STMT (def));
413
  scev = scalar_evolution_in_region (region, loop, def);
414
 
415
  return !chrec_contains_undetermined (scev)
416
    && (TREE_CODE (scev) != SSA_NAME
417
        || !defined_in_sese_p (scev, region))
418
    && (tree_does_not_contain_chrecs (scev)
419
        || evolution_function_is_affine_p (scev));
420
}
421
 
422
#endif

powered by: WebSVN 2.1.0

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