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

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-stable/] [gcc-4.5.1/] [gcc/] [cfgloop.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
/* Natural loop functions
2
   Copyright (C) 1987, 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004,
3
   2005, 2006, 2007, 2008, 2009  Free Software Foundation, Inc.
4
 
5
This file is part of GCC.
6
 
7
GCC is free software; you can redistribute it and/or modify it under
8
the terms of the GNU General Public License as published by the Free
9
Software Foundation; either version 3, or (at your option) any later
10
version.
11
 
12
GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13
WARRANTY; without even the implied warranty of MERCHANTABILITY or
14
FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
15
for more details.
16
 
17
You should have received a copy of the GNU General Public License
18
along with GCC; see the file COPYING3.  If not see
19
<http://www.gnu.org/licenses/>.  */
20
 
21
#ifndef GCC_CFGLOOP_H
22
#define GCC_CFGLOOP_H
23
 
24
#include "basic-block.h"
25
/* For rtx_code.  */
26
#include "rtl.h"
27
#include "vecprim.h"
28
#include "double-int.h"
29
 
30
/* Structure to hold decision about unrolling/peeling.  */
31
enum lpt_dec
32
{
33
  LPT_NONE,
34
  LPT_PEEL_COMPLETELY,
35
  LPT_PEEL_SIMPLE,
36
  LPT_UNROLL_CONSTANT,
37
  LPT_UNROLL_RUNTIME,
38
  LPT_UNROLL_STUPID
39
};
40
 
41
struct GTY (()) lpt_decision {
42
  enum lpt_dec decision;
43
  unsigned times;
44
};
45
 
46
/* The structure describing a bound on number of iterations of a loop.  */
47
 
48
struct GTY ((chain_next ("%h.next"))) nb_iter_bound {
49
  /* The statement STMT is executed at most ...  */
50
  gimple stmt;
51
 
52
  /* ... BOUND + 1 times (BOUND must be an unsigned constant).
53
     The + 1 is added for the following reasons:
54
 
55
     a) 0 would otherwise be unused, while we would need to care more about
56
        overflows (as MAX + 1 is sometimes produced as the estimate on number
57
        of executions of STMT).
58
     b) it is consistent with the result of number_of_iterations_exit.  */
59
  double_int bound;
60
 
61
  /* True if the statement will cause the loop to be leaved the (at most)
62
     BOUND + 1-st time it is executed, that is, all the statements after it
63
     are executed at most BOUND times.  */
64
  bool is_exit;
65
 
66
  /* The next bound in the list.  */
67
  struct nb_iter_bound *next;
68
};
69
 
70
/* Description of the loop exit.  */
71
 
72
struct GTY (()) loop_exit {
73
  /* The exit edge.  */
74
  struct edge_def *e;
75
 
76
  /* Previous and next exit in the list of the exits of the loop.  */
77
  struct loop_exit *prev;
78
  struct loop_exit *next;
79
 
80
  /* Next element in the list of loops from that E exits.  */
81
  struct loop_exit *next_e;
82
};
83
 
84
typedef struct loop *loop_p;
85
DEF_VEC_P (loop_p);
86
DEF_VEC_ALLOC_P (loop_p, heap);
87
DEF_VEC_ALLOC_P (loop_p, gc);
88
 
89
/* An integer estimation of the number of iterations.  Estimate_state
90
   describes what is the state of the estimation.  */
91
enum loop_estimation
92
{
93
  /* Estimate was not computed yet.  */
94
  EST_NOT_COMPUTED,
95
  /* Estimate is ready.  */
96
  EST_AVAILABLE
97
};
98
 
99
/* Structure to hold information for each natural loop.  */
100
struct GTY ((chain_next ("%h.next"))) loop {
101
  /* Index into loops array.  */
102
  int num;
103
 
104
  /* Number of loop insns.  */
105
  unsigned ninsns;
106
 
107
  /* Basic block of loop header.  */
108
  struct basic_block_def *header;
109
 
110
  /* Basic block of loop latch.  */
111
  struct basic_block_def *latch;
112
 
113
  /* For loop unrolling/peeling decision.  */
114
  struct lpt_decision lpt_decision;
115
 
116
  /* Average number of executed insns per iteration.  */
117
  unsigned av_ninsns;
118
 
119
  /* Number of blocks contained within the loop.  */
120
  unsigned num_nodes;
121
 
122
  /* Superloops of the loop, starting with the outermost loop.  */
123
  VEC (loop_p, gc) *superloops;
124
 
125
  /* The first inner (child) loop or NULL if innermost loop.  */
126
  struct loop *inner;
127
 
128
  /* Link to the next (sibling) loop.  */
129
  struct loop *next;
130
 
131
  /* Auxiliary info specific to a pass.  */
132
  PTR GTY ((skip (""))) aux;
133
 
134
  /* The number of times the latch of the loop is executed.
135
     This is an INTEGER_CST or an expression containing symbolic
136
     names.  Don't access this field directly:
137
     number_of_latch_executions computes and caches the computed
138
     information in this field.  */
139
  tree nb_iterations;
140
 
141
  /* An integer guaranteed to bound the number of iterations of the loop
142
     from above.  */
143
  double_int nb_iterations_upper_bound;
144
 
145
  /* An integer giving the expected number of iterations of the loop.  */
146
  double_int nb_iterations_estimate;
147
 
148
  bool any_upper_bound;
149
  bool any_estimate;
150
 
151
  /* An integer estimation of the number of iterations.  Estimate_state
152
     describes what is the state of the estimation.  */
153
  enum loop_estimation estimate_state;
154
 
155
  /* Upper bound on number of iterations of a loop.  */
156
  struct nb_iter_bound *bounds;
157
 
158
  /* Head of the cyclic list of the exits of the loop.  */
159
  struct loop_exit *exits;
160
 
161
  /* True if the loop can be parallel.  */
162
  bool can_be_parallel;
163
 
164
  /* The single induction variable of the loop when the loop is in
165
     normal form.  */
166
  tree single_iv;
167
};
168
 
169
/* Flags for state of loop structure.  */
170
enum
171
{
172
  LOOPS_HAVE_PREHEADERS = 1,
173
  LOOPS_HAVE_SIMPLE_LATCHES = 2,
174
  LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS = 4,
175
  LOOPS_HAVE_RECORDED_EXITS = 8,
176
  LOOPS_MAY_HAVE_MULTIPLE_LATCHES = 16,
177
  LOOP_CLOSED_SSA = 32,
178
  LOOPS_NEED_FIXUP = 64,
179
  LOOPS_HAVE_FALLTHRU_PREHEADERS = 128
180
};
181
 
182
#define LOOPS_NORMAL (LOOPS_HAVE_PREHEADERS | LOOPS_HAVE_SIMPLE_LATCHES \
183
                      | LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS)
184
#define AVOID_CFG_MODIFICATIONS (LOOPS_MAY_HAVE_MULTIPLE_LATCHES)
185
 
186
/* Structure to hold CFG information about natural loops within a function.  */
187
struct GTY (()) loops {
188
  /* State of loops.  */
189
  int state;
190
 
191
  /* Array of the loops.  */
192
  VEC (loop_p, gc) *larray;
193
 
194
  /* Maps edges to the list of their descriptions as loop exits.  Edges
195
     whose sources or destinations have loop_father == NULL (which may
196
     happen during the cfg manipulations) should not appear in EXITS.  */
197
  htab_t GTY((param_is (struct loop_exit))) exits;
198
 
199
  /* Pointer to root of loop hierarchy tree.  */
200
  struct loop *tree_root;
201
};
202
 
203
/* Loop recognition.  */
204
extern int flow_loops_find (struct loops *);
205
extern void disambiguate_loops_with_multiple_latches (void);
206
extern void flow_loops_free (struct loops *);
207
extern void flow_loops_dump (FILE *,
208
                             void (*)(const struct loop *, FILE *, int), int);
209
extern void flow_loop_dump (const struct loop *, FILE *,
210
                            void (*)(const struct loop *, FILE *, int), int);
211
struct loop *alloc_loop (void);
212
extern void flow_loop_free (struct loop *);
213
int flow_loop_nodes_find (basic_block, struct loop *);
214
void fix_loop_structure (bitmap changed_bbs);
215
bool mark_irreducible_loops (void);
216
void release_recorded_exits (void);
217
void record_loop_exits (void);
218
void rescan_loop_exit (edge, bool, bool);
219
 
220
/* Loop data structure manipulation/querying.  */
221
extern void flow_loop_tree_node_add (struct loop *, struct loop *);
222
extern void flow_loop_tree_node_remove (struct loop *);
223
extern void add_loop (struct loop *, struct loop *);
224
extern bool flow_loop_nested_p  (const struct loop *, const struct loop *);
225
extern bool flow_bb_inside_loop_p (const struct loop *, const_basic_block);
226
extern struct loop * find_common_loop (struct loop *, struct loop *);
227
struct loop *superloop_at_depth (struct loop *, unsigned);
228
struct eni_weights_d;
229
extern unsigned tree_num_loop_insns (struct loop *, struct eni_weights_d *);
230
extern int num_loop_insns (const struct loop *);
231
extern int average_num_loop_insns (const struct loop *);
232
extern unsigned get_loop_level (const struct loop *);
233
extern bool loop_exit_edge_p (const struct loop *, const_edge);
234
extern bool is_loop_exit (struct loop *, basic_block);
235
extern void mark_loop_exit_edges (void);
236
 
237
/* Loops & cfg manipulation.  */
238
extern basic_block *get_loop_body (const struct loop *);
239
extern unsigned get_loop_body_with_size (const struct loop *, basic_block *,
240
                                         unsigned);
241
extern basic_block *get_loop_body_in_dom_order (const struct loop *);
242
extern basic_block *get_loop_body_in_bfs_order (const struct loop *);
243
extern basic_block *get_loop_body_in_custom_order (const struct loop *,
244
                               int (*) (const void *, const void *));
245
 
246
extern VEC (edge, heap) *get_loop_exit_edges (const struct loop *);
247
edge single_exit (const struct loop *);
248
extern unsigned num_loop_branches (const struct loop *);
249
 
250
extern edge loop_preheader_edge (const struct loop *);
251
extern edge loop_latch_edge (const struct loop *);
252
 
253
extern void add_bb_to_loop (basic_block, struct loop *);
254
extern void remove_bb_from_loops (basic_block);
255
 
256
extern void cancel_loop_tree (struct loop *);
257
extern void delete_loop (struct loop *);
258
 
259
enum
260
{
261
  CP_SIMPLE_PREHEADERS = 1,
262
  CP_FALLTHRU_PREHEADERS = 2
263
};
264
 
265
basic_block create_preheader (struct loop *, int);
266
extern void create_preheaders (int);
267
extern void force_single_succ_latches (void);
268
 
269
extern void verify_loop_structure (void);
270
 
271
/* Loop analysis.  */
272
extern bool just_once_each_iteration_p (const struct loop *, const_basic_block);
273
gcov_type expected_loop_iterations_unbounded (const struct loop *);
274
extern unsigned expected_loop_iterations (const struct loop *);
275
extern rtx doloop_condition_get (rtx);
276
 
277
void estimate_numbers_of_iterations_loop (struct loop *);
278
HOST_WIDE_INT estimated_loop_iterations_int (struct loop *, bool);
279
bool estimated_loop_iterations (struct loop *, bool, double_int *);
280
 
281
/* Loop manipulation.  */
282
extern bool can_duplicate_loop_p (const struct loop *loop);
283
 
284
#define DLTHE_FLAG_UPDATE_FREQ  1       /* Update frequencies in
285
                                           duplicate_loop_to_header_edge.  */
286
#define DLTHE_RECORD_COPY_NUMBER 2      /* Record copy number in the aux
287
                                           field of newly create BB.  */
288
#define DLTHE_FLAG_COMPLETTE_PEEL 4     /* Update frequencies expecting
289
                                           a complete peeling.  */
290
 
291
extern edge create_empty_if_region_on_edge (edge, tree);
292
extern struct loop *create_empty_loop_on_edge (edge, tree, tree, tree, tree,
293
                                               tree *, tree *, struct loop *);
294
extern struct loop * duplicate_loop (struct loop *, struct loop *);
295
extern void duplicate_subloops (struct loop *, struct loop *);
296
extern bool duplicate_loop_to_header_edge (struct loop *, edge,
297
                                           unsigned, sbitmap, edge,
298
                                           VEC (edge, heap) **, int);
299
extern struct loop *loopify (edge, edge,
300
                             basic_block, edge, edge, bool,
301
                             unsigned, unsigned);
302
struct loop * loop_version (struct loop *, void *,
303
                            basic_block *, unsigned, unsigned, unsigned, bool);
304
extern bool remove_path (edge);
305
void scale_loop_frequencies (struct loop *, int, int);
306
 
307
/* Induction variable analysis.  */
308
 
309
/* The description of induction variable.  The things are a bit complicated
310
   due to need to handle subregs and extends.  The value of the object described
311
   by it can be obtained as follows (all computations are done in extend_mode):
312
 
313
   Value in i-th iteration is
314
     delta + mult * extend_{extend_mode} (subreg_{mode} (base + i * step)).
315
 
316
   If first_special is true, the value in the first iteration is
317
     delta + mult * base
318
 
319
   If extend = UNKNOWN, first_special must be false, delta 0, mult 1 and value is
320
     subreg_{mode} (base + i * step)
321
 
322
   The get_iv_value function can be used to obtain these expressions.
323
 
324
   ??? Add a third mode field that would specify the mode in that inner
325
   computation is done, which would enable it to be different from the
326
   outer one?  */
327
 
328
struct rtx_iv
329
{
330
  /* Its base and step (mode of base and step is supposed to be extend_mode,
331
     see the description above).  */
332
  rtx base, step;
333
 
334
  /* The type of extend applied to it (SIGN_EXTEND, ZERO_EXTEND or UNKNOWN).  */
335
  enum rtx_code extend;
336
 
337
  /* Operations applied in the extended mode.  */
338
  rtx delta, mult;
339
 
340
  /* The mode it is extended to.  */
341
  enum machine_mode extend_mode;
342
 
343
  /* The mode the variable iterates in.  */
344
  enum machine_mode mode;
345
 
346
  /* Whether the first iteration needs to be handled specially.  */
347
  unsigned first_special : 1;
348
};
349
 
350
/* The description of an exit from the loop and of the number of iterations
351
   till we take the exit.  */
352
 
353
struct niter_desc
354
{
355
  /* The edge out of the loop.  */
356
  edge out_edge;
357
 
358
  /* The other edge leading from the condition.  */
359
  edge in_edge;
360
 
361
  /* True if we are able to say anything about number of iterations of the
362
     loop.  */
363
  bool simple_p;
364
 
365
  /* True if the loop iterates the constant number of times.  */
366
  bool const_iter;
367
 
368
  /* Number of iterations if constant.  */
369
  unsigned HOST_WIDEST_INT niter;
370
 
371
  /* Upper bound on the number of iterations.  */
372
  unsigned HOST_WIDEST_INT niter_max;
373
 
374
  /* Assumptions under that the rest of the information is valid.  */
375
  rtx assumptions;
376
 
377
  /* Assumptions under that the loop ends before reaching the latch,
378
     even if value of niter_expr says otherwise.  */
379
  rtx noloop_assumptions;
380
 
381
  /* Condition under that the loop is infinite.  */
382
  rtx infinite;
383
 
384
  /* Whether the comparison is signed.  */
385
  bool signed_p;
386
 
387
  /* The mode in that niter_expr should be computed.  */
388
  enum machine_mode mode;
389
 
390
  /* The number of iterations of the loop.  */
391
  rtx niter_expr;
392
};
393
 
394
extern void iv_analysis_loop_init (struct loop *);
395
extern bool iv_analyze (rtx, rtx, struct rtx_iv *);
396
extern bool iv_analyze_result (rtx, rtx, struct rtx_iv *);
397
extern bool iv_analyze_expr (rtx, rtx, enum machine_mode, struct rtx_iv *);
398
extern rtx get_iv_value (struct rtx_iv *, rtx);
399
extern bool biv_p (rtx, rtx);
400
extern void find_simple_exit (struct loop *, struct niter_desc *);
401
extern void iv_analysis_done (void);
402
 
403
extern struct niter_desc *get_simple_loop_desc (struct loop *loop);
404
extern void free_simple_loop_desc (struct loop *loop);
405
 
406
static inline struct niter_desc *
407
simple_loop_desc (struct loop *loop)
408
{
409
  return (struct niter_desc *) loop->aux;
410
}
411
 
412
/* Accessors for the loop structures.  */
413
 
414
/* Returns the loop with index NUM from current_loops.  */
415
 
416
static inline struct loop *
417
get_loop (unsigned num)
418
{
419
  return VEC_index (loop_p, current_loops->larray, num);
420
}
421
 
422
/* Returns the number of superloops of LOOP.  */
423
 
424
static inline unsigned
425
loop_depth (const struct loop *loop)
426
{
427
  return VEC_length (loop_p, loop->superloops);
428
}
429
 
430
/* Returns the immediate superloop of LOOP, or NULL if LOOP is the outermost
431
   loop.  */
432
 
433
static inline struct loop *
434
loop_outer (const struct loop *loop)
435
{
436
  unsigned n = VEC_length (loop_p, loop->superloops);
437
 
438
  if (n == 0)
439
    return NULL;
440
 
441
  return VEC_index (loop_p, loop->superloops, n - 1);
442
}
443
 
444
/* Returns the list of loops in current_loops.  */
445
 
446
static inline VEC (loop_p, gc) *
447
get_loops (void)
448
{
449
  if (!current_loops)
450
    return NULL;
451
 
452
  return current_loops->larray;
453
}
454
 
455
/* Returns the number of loops in current_loops (including the removed
456
   ones and the fake loop that forms the root of the loop tree).  */
457
 
458
static inline unsigned
459
number_of_loops (void)
460
{
461
  if (!current_loops)
462
    return 0;
463
 
464
  return VEC_length (loop_p, current_loops->larray);
465
}
466
 
467
/* Returns true if state of the loops satisfies all properties
468
   described by FLAGS.  */
469
 
470
static inline bool
471
loops_state_satisfies_p (unsigned flags)
472
{
473
  return (current_loops->state & flags) == flags;
474
}
475
 
476
/* Sets FLAGS to the loops state.  */
477
 
478
static inline void
479
loops_state_set (unsigned flags)
480
{
481
  current_loops->state |= flags;
482
}
483
 
484
/* Clears FLAGS from the loops state.  */
485
 
486
static inline void
487
loops_state_clear (unsigned flags)
488
{
489
  if (!current_loops)
490
    return;
491
  current_loops->state &= ~flags;
492
}
493
 
494
/* Loop iterators.  */
495
 
496
/* Flags for loop iteration.  */
497
 
498
enum li_flags
499
{
500
  LI_INCLUDE_ROOT = 1,          /* Include the fake root of the loop tree.  */
501
  LI_FROM_INNERMOST = 2,        /* Iterate over the loops in the reverse order,
502
                                   starting from innermost ones.  */
503
  LI_ONLY_INNERMOST = 4         /* Iterate only over innermost loops.  */
504
};
505
 
506
/* The iterator for loops.  */
507
 
508
typedef struct
509
{
510
  /* The list of loops to visit.  */
511
  VEC(int,heap) *to_visit;
512
 
513
  /* The index of the actual loop.  */
514
  unsigned idx;
515
} loop_iterator;
516
 
517
static inline void
518
fel_next (loop_iterator *li, loop_p *loop)
519
{
520
  int anum;
521
 
522
  while (VEC_iterate (int, li->to_visit, li->idx, anum))
523
    {
524
      li->idx++;
525
      *loop = get_loop (anum);
526
      if (*loop)
527
        return;
528
    }
529
 
530
  VEC_free (int, heap, li->to_visit);
531
  *loop = NULL;
532
}
533
 
534
static inline void
535
fel_init (loop_iterator *li, loop_p *loop, unsigned flags)
536
{
537
  struct loop *aloop;
538
  unsigned i;
539
  int mn;
540
 
541
  li->idx = 0;
542
  if (!current_loops)
543
    {
544
      li->to_visit = NULL;
545
      *loop = NULL;
546
      return;
547
    }
548
 
549
  li->to_visit = VEC_alloc (int, heap, number_of_loops ());
550
  mn = (flags & LI_INCLUDE_ROOT) ? 0 : 1;
551
 
552
  if (flags & LI_ONLY_INNERMOST)
553
    {
554
      for (i = 0; VEC_iterate (loop_p, current_loops->larray, i, aloop); i++)
555
        if (aloop != NULL
556
            && aloop->inner == NULL
557
            && aloop->num >= mn)
558
          VEC_quick_push (int, li->to_visit, aloop->num);
559
    }
560
  else if (flags & LI_FROM_INNERMOST)
561
    {
562
      /* Push the loops to LI->TO_VISIT in postorder.  */
563
      for (aloop = current_loops->tree_root;
564
           aloop->inner != NULL;
565
           aloop = aloop->inner)
566
        continue;
567
 
568
      while (1)
569
        {
570
          if (aloop->num >= mn)
571
            VEC_quick_push (int, li->to_visit, aloop->num);
572
 
573
          if (aloop->next)
574
            {
575
              for (aloop = aloop->next;
576
                   aloop->inner != NULL;
577
                   aloop = aloop->inner)
578
                continue;
579
            }
580
          else if (!loop_outer (aloop))
581
            break;
582
          else
583
            aloop = loop_outer (aloop);
584
        }
585
    }
586
  else
587
    {
588
      /* Push the loops to LI->TO_VISIT in preorder.  */
589
      aloop = current_loops->tree_root;
590
      while (1)
591
        {
592
          if (aloop->num >= mn)
593
            VEC_quick_push (int, li->to_visit, aloop->num);
594
 
595
          if (aloop->inner != NULL)
596
            aloop = aloop->inner;
597
          else
598
            {
599
              while (aloop != NULL && aloop->next == NULL)
600
                aloop = loop_outer (aloop);
601
              if (aloop == NULL)
602
                break;
603
              aloop = aloop->next;
604
            }
605
        }
606
    }
607
 
608
  fel_next (li, loop);
609
}
610
 
611
#define FOR_EACH_LOOP(LI, LOOP, FLAGS) \
612
  for (fel_init (&(LI), &(LOOP), FLAGS); \
613
       (LOOP); \
614
       fel_next (&(LI), &(LOOP)))
615
 
616
#define FOR_EACH_LOOP_BREAK(LI) \
617
  { \
618
    VEC_free (int, heap, (LI)->to_visit); \
619
    break; \
620
  }
621
 
622
/* The properties of the target.  */
623
 
624
extern unsigned target_avail_regs;
625
extern unsigned target_res_regs;
626
extern unsigned target_reg_cost [2];
627
extern unsigned target_spill_cost [2];
628
 
629
/* Register pressure estimation for induction variable optimizations & loop
630
   invariant motion.  */
631
extern unsigned estimate_reg_pressure_cost (unsigned, unsigned, bool);
632
extern void init_set_costs (void);
633
 
634
/* Loop optimizer initialization.  */
635
extern void loop_optimizer_init (unsigned);
636
extern void loop_optimizer_finalize (void);
637
 
638
/* Optimization passes.  */
639
extern void unswitch_loops (void);
640
 
641
enum
642
{
643
  UAP_PEEL = 1,         /* Enables loop peeling.  */
644
  UAP_UNROLL = 2,       /* Enables unrolling of loops if it seems profitable.  */
645
  UAP_UNROLL_ALL = 4    /* Enables unrolling of all loops.  */
646
};
647
 
648
extern void unroll_and_peel_loops (int);
649
extern void doloop_optimize_loops (void);
650
extern void move_loop_invariants (void);
651
extern bool finite_loop_p (struct loop *);
652
 
653
#endif /* GCC_CFGLOOP_H */

powered by: WebSVN 2.1.0

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