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

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-stable/] [gcc-4.5.1/] [gcc/] [cfgloop.c] - Blame information for rev 847

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

Line No. Rev Author Line
1 280 jeremybenn
/* Natural loop discovery code for GNU compiler.
2
   Copyright (C) 2000, 2001, 2003, 2004, 2005, 2006, 2007, 2008
3
   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
#include "config.h"
22
#include "system.h"
23
#include "coretypes.h"
24
#include "tm.h"
25
#include "rtl.h"
26
#include "hard-reg-set.h"
27
#include "obstack.h"
28
#include "function.h"
29
#include "basic-block.h"
30
#include "toplev.h"
31
#include "cfgloop.h"
32
#include "flags.h"
33
#include "tree.h"
34
#include "tree-flow.h"
35
#include "pointer-set.h"
36
#include "output.h"
37
#include "ggc.h"
38
 
39
static void flow_loops_cfg_dump (FILE *);
40
 
41
/* Dump loop related CFG information.  */
42
 
43
static void
44
flow_loops_cfg_dump (FILE *file)
45
{
46
  basic_block bb;
47
 
48
  if (!file)
49
    return;
50
 
51
  FOR_EACH_BB (bb)
52
    {
53
      edge succ;
54
      edge_iterator ei;
55
 
56
      fprintf (file, ";; %d succs { ", bb->index);
57
      FOR_EACH_EDGE (succ, ei, bb->succs)
58
        fprintf (file, "%d ", succ->dest->index);
59
      fprintf (file, "}\n");
60
    }
61
}
62
 
63
/* Return nonzero if the nodes of LOOP are a subset of OUTER.  */
64
 
65
bool
66
flow_loop_nested_p (const struct loop *outer, const struct loop *loop)
67
{
68
  unsigned odepth = loop_depth (outer);
69
 
70
  return (loop_depth (loop) > odepth
71
          && VEC_index (loop_p, loop->superloops, odepth) == outer);
72
}
73
 
74
/* Returns the loop such that LOOP is nested DEPTH (indexed from zero)
75
   loops within LOOP.  */
76
 
77
struct loop *
78
superloop_at_depth (struct loop *loop, unsigned depth)
79
{
80
  unsigned ldepth = loop_depth (loop);
81
 
82
  gcc_assert (depth <= ldepth);
83
 
84
  if (depth == ldepth)
85
    return loop;
86
 
87
  return VEC_index (loop_p, loop->superloops, depth);
88
}
89
 
90
/* Returns the list of the latch edges of LOOP.  */
91
 
92
static VEC (edge, heap) *
93
get_loop_latch_edges (const struct loop *loop)
94
{
95
  edge_iterator ei;
96
  edge e;
97
  VEC (edge, heap) *ret = NULL;
98
 
99
  FOR_EACH_EDGE (e, ei, loop->header->preds)
100
    {
101
      if (dominated_by_p (CDI_DOMINATORS, e->src, loop->header))
102
        VEC_safe_push (edge, heap, ret, e);
103
    }
104
 
105
  return ret;
106
}
107
 
108
/* Dump the loop information specified by LOOP to the stream FILE
109
   using auxiliary dump callback function LOOP_DUMP_AUX if non null.  */
110
 
111
void
112
flow_loop_dump (const struct loop *loop, FILE *file,
113
                void (*loop_dump_aux) (const struct loop *, FILE *, int),
114
                int verbose)
115
{
116
  basic_block *bbs;
117
  unsigned i;
118
  VEC (edge, heap) *latches;
119
  edge e;
120
 
121
  if (! loop || ! loop->header)
122
    return;
123
 
124
  fprintf (file, ";;\n;; Loop %d\n", loop->num);
125
 
126
  fprintf (file, ";;  header %d, ", loop->header->index);
127
  if (loop->latch)
128
    fprintf (file, "latch %d\n", loop->latch->index);
129
  else
130
    {
131
      fprintf (file, "multiple latches:");
132
      latches = get_loop_latch_edges (loop);
133
      for (i = 0; VEC_iterate (edge, latches, i, e); i++)
134
        fprintf (file, " %d", e->src->index);
135
      VEC_free (edge, heap, latches);
136
      fprintf (file, "\n");
137
    }
138
 
139
  fprintf (file, ";;  depth %d, outer %ld\n",
140
           loop_depth (loop), (long) (loop_outer (loop)
141
                                      ? loop_outer (loop)->num : -1));
142
 
143
  fprintf (file, ";;  nodes:");
144
  bbs = get_loop_body (loop);
145
  for (i = 0; i < loop->num_nodes; i++)
146
    fprintf (file, " %d", bbs[i]->index);
147
  free (bbs);
148
  fprintf (file, "\n");
149
 
150
  if (loop_dump_aux)
151
    loop_dump_aux (loop, file, verbose);
152
}
153
 
154
/* Dump the loop information about loops to the stream FILE,
155
   using auxiliary dump callback function LOOP_DUMP_AUX if non null.  */
156
 
157
void
158
flow_loops_dump (FILE *file, void (*loop_dump_aux) (const struct loop *, FILE *, int), int verbose)
159
{
160
  loop_iterator li;
161
  struct loop *loop;
162
 
163
  if (!current_loops || ! file)
164
    return;
165
 
166
  fprintf (file, ";; %d loops found\n", number_of_loops ());
167
 
168
  FOR_EACH_LOOP (li, loop, LI_INCLUDE_ROOT)
169
    {
170
      flow_loop_dump (loop, file, loop_dump_aux, verbose);
171
    }
172
 
173
  if (verbose)
174
    flow_loops_cfg_dump (file);
175
}
176
 
177
/* Free data allocated for LOOP.  */
178
 
179
void
180
flow_loop_free (struct loop *loop)
181
{
182
  struct loop_exit *exit, *next;
183
 
184
  VEC_free (loop_p, gc, loop->superloops);
185
 
186
  /* Break the list of the loop exit records.  They will be freed when the
187
     corresponding edge is rescanned or removed, and this avoids
188
     accessing the (already released) head of the list stored in the
189
     loop structure.  */
190
  for (exit = loop->exits->next; exit != loop->exits; exit = next)
191
    {
192
      next = exit->next;
193
      exit->next = exit;
194
      exit->prev = exit;
195
    }
196
 
197
  ggc_free (loop->exits);
198
  ggc_free (loop);
199
}
200
 
201
/* Free all the memory allocated for LOOPS.  */
202
 
203
void
204
flow_loops_free (struct loops *loops)
205
{
206
  if (loops->larray)
207
    {
208
      unsigned i;
209
      loop_p loop;
210
 
211
      /* Free the loop descriptors.  */
212
      for (i = 0; VEC_iterate (loop_p, loops->larray, i, loop); i++)
213
        {
214
          if (!loop)
215
            continue;
216
 
217
          flow_loop_free (loop);
218
        }
219
 
220
      VEC_free (loop_p, gc, loops->larray);
221
    }
222
}
223
 
224
/* Find the nodes contained within the LOOP with header HEADER.
225
   Return the number of nodes within the loop.  */
226
 
227
int
228
flow_loop_nodes_find (basic_block header, struct loop *loop)
229
{
230
  VEC (basic_block, heap) *stack = NULL;
231
  int num_nodes = 1;
232
  edge latch;
233
  edge_iterator latch_ei;
234
  unsigned depth = loop_depth (loop);
235
 
236
  header->loop_father = loop;
237
  header->loop_depth = depth;
238
 
239
  FOR_EACH_EDGE (latch, latch_ei, loop->header->preds)
240
    {
241
      if (latch->src->loop_father == loop
242
          || !dominated_by_p (CDI_DOMINATORS, latch->src, loop->header))
243
        continue;
244
 
245
      num_nodes++;
246
      VEC_safe_push (basic_block, heap, stack, latch->src);
247
      latch->src->loop_father = loop;
248
      latch->src->loop_depth = depth;
249
 
250
      while (!VEC_empty (basic_block, stack))
251
        {
252
          basic_block node;
253
          edge e;
254
          edge_iterator ei;
255
 
256
          node = VEC_pop (basic_block, stack);
257
 
258
          FOR_EACH_EDGE (e, ei, node->preds)
259
            {
260
              basic_block ancestor = e->src;
261
 
262
              if (ancestor->loop_father != loop)
263
                {
264
                  ancestor->loop_father = loop;
265
                  ancestor->loop_depth = depth;
266
                  num_nodes++;
267
                  VEC_safe_push (basic_block, heap, stack, ancestor);
268
                }
269
            }
270
        }
271
    }
272
  VEC_free (basic_block, heap, stack);
273
 
274
  return num_nodes;
275
}
276
 
277
/* Records the vector of superloops of the loop LOOP, whose immediate
278
   superloop is FATHER.  */
279
 
280
static void
281
establish_preds (struct loop *loop, struct loop *father)
282
{
283
  loop_p ploop;
284
  unsigned depth = loop_depth (father) + 1;
285
  unsigned i;
286
 
287
  VEC_truncate (loop_p, loop->superloops, 0);
288
  VEC_reserve (loop_p, gc, loop->superloops, depth);
289
  for (i = 0; VEC_iterate (loop_p, father->superloops, i, ploop); i++)
290
    VEC_quick_push (loop_p, loop->superloops, ploop);
291
  VEC_quick_push (loop_p, loop->superloops, father);
292
 
293
  for (ploop = loop->inner; ploop; ploop = ploop->next)
294
    establish_preds (ploop, loop);
295
}
296
 
297
/* Add LOOP to the loop hierarchy tree where FATHER is father of the
298
   added loop.  If LOOP has some children, take care of that their
299
   pred field will be initialized correctly.  */
300
 
301
void
302
flow_loop_tree_node_add (struct loop *father, struct loop *loop)
303
{
304
  loop->next = father->inner;
305
  father->inner = loop;
306
 
307
  establish_preds (loop, father);
308
}
309
 
310
/* Remove LOOP from the loop hierarchy tree.  */
311
 
312
void
313
flow_loop_tree_node_remove (struct loop *loop)
314
{
315
  struct loop *prev, *father;
316
 
317
  father = loop_outer (loop);
318
 
319
  /* Remove loop from the list of sons.  */
320
  if (father->inner == loop)
321
    father->inner = loop->next;
322
  else
323
    {
324
      for (prev = father->inner; prev->next != loop; prev = prev->next)
325
        continue;
326
      prev->next = loop->next;
327
    }
328
 
329
  VEC_truncate (loop_p, loop->superloops, 0);
330
}
331
 
332
/* Allocates and returns new loop structure.  */
333
 
334
struct loop *
335
alloc_loop (void)
336
{
337
  struct loop *loop = GGC_CNEW (struct loop);
338
 
339
  loop->exits = GGC_CNEW (struct loop_exit);
340
  loop->exits->next = loop->exits->prev = loop->exits;
341
  loop->can_be_parallel = false;
342
  loop->single_iv = NULL_TREE;
343
 
344
  return loop;
345
}
346
 
347
/* Initializes loops structure LOOPS, reserving place for NUM_LOOPS loops
348
   (including the root of the loop tree).  */
349
 
350
static void
351
init_loops_structure (struct loops *loops, unsigned num_loops)
352
{
353
  struct loop *root;
354
 
355
  memset (loops, 0, sizeof *loops);
356
  loops->larray = VEC_alloc (loop_p, gc, num_loops);
357
 
358
  /* Dummy loop containing whole function.  */
359
  root = alloc_loop ();
360
  root->num_nodes = n_basic_blocks;
361
  root->latch = EXIT_BLOCK_PTR;
362
  root->header = ENTRY_BLOCK_PTR;
363
  ENTRY_BLOCK_PTR->loop_father = root;
364
  EXIT_BLOCK_PTR->loop_father = root;
365
 
366
  VEC_quick_push (loop_p, loops->larray, root);
367
  loops->tree_root = root;
368
}
369
 
370
/* Find all the natural loops in the function and save in LOOPS structure and
371
   recalculate loop_depth information in basic block structures.
372
   Return the number of natural loops found.  */
373
 
374
int
375
flow_loops_find (struct loops *loops)
376
{
377
  int b;
378
  int num_loops;
379
  edge e;
380
  sbitmap headers;
381
  int *dfs_order;
382
  int *rc_order;
383
  basic_block header;
384
  basic_block bb;
385
 
386
  /* Ensure that the dominators are computed.  */
387
  calculate_dominance_info (CDI_DOMINATORS);
388
 
389
  /* Taking care of this degenerate case makes the rest of
390
     this code simpler.  */
391
  if (n_basic_blocks == NUM_FIXED_BLOCKS)
392
    {
393
      init_loops_structure (loops, 1);
394
      return 1;
395
    }
396
 
397
  dfs_order = NULL;
398
  rc_order = NULL;
399
 
400
  /* Count the number of loop headers.  This should be the
401
     same as the number of natural loops.  */
402
  headers = sbitmap_alloc (last_basic_block);
403
  sbitmap_zero (headers);
404
 
405
  num_loops = 0;
406
  FOR_EACH_BB (header)
407
    {
408
      edge_iterator ei;
409
 
410
      header->loop_depth = 0;
411
 
412
      /* If we have an abnormal predecessor, do not consider the
413
         loop (not worth the problems).  */
414
      FOR_EACH_EDGE (e, ei, header->preds)
415
        if (e->flags & EDGE_ABNORMAL)
416
          break;
417
      if (e)
418
        continue;
419
 
420
      FOR_EACH_EDGE (e, ei, header->preds)
421
        {
422
          basic_block latch = e->src;
423
 
424
          gcc_assert (!(e->flags & EDGE_ABNORMAL));
425
 
426
          /* Look for back edges where a predecessor is dominated
427
             by this block.  A natural loop has a single entry
428
             node (header) that dominates all the nodes in the
429
             loop.  It also has single back edge to the header
430
             from a latch node.  */
431
          if (latch != ENTRY_BLOCK_PTR
432
              && dominated_by_p (CDI_DOMINATORS, latch, header))
433
            {
434
              /* Shared headers should be eliminated by now.  */
435
              SET_BIT (headers, header->index);
436
              num_loops++;
437
            }
438
        }
439
    }
440
 
441
  /* Allocate loop structures.  */
442
  init_loops_structure (loops, num_loops + 1);
443
 
444
  /* Find and record information about all the natural loops
445
     in the CFG.  */
446
  FOR_EACH_BB (bb)
447
    bb->loop_father = loops->tree_root;
448
 
449
  if (num_loops)
450
    {
451
      /* Compute depth first search order of the CFG so that outer
452
         natural loops will be found before inner natural loops.  */
453
      dfs_order = XNEWVEC (int, n_basic_blocks);
454
      rc_order = XNEWVEC (int, n_basic_blocks);
455
      pre_and_rev_post_order_compute (dfs_order, rc_order, false);
456
 
457
      num_loops = 1;
458
 
459
      for (b = 0; b < n_basic_blocks - NUM_FIXED_BLOCKS; b++)
460
        {
461
          struct loop *loop;
462
          edge_iterator ei;
463
 
464
          /* Search the nodes of the CFG in reverse completion order
465
             so that we can find outer loops first.  */
466
          if (!TEST_BIT (headers, rc_order[b]))
467
            continue;
468
 
469
          header = BASIC_BLOCK (rc_order[b]);
470
 
471
          loop = alloc_loop ();
472
          VEC_quick_push (loop_p, loops->larray, loop);
473
 
474
          loop->header = header;
475
          loop->num = num_loops;
476
          num_loops++;
477
 
478
          flow_loop_tree_node_add (header->loop_father, loop);
479
          loop->num_nodes = flow_loop_nodes_find (loop->header, loop);
480
 
481
          /* Look for the latch for this header block, if it has just a
482
             single one.  */
483
          FOR_EACH_EDGE (e, ei, header->preds)
484
            {
485
              basic_block latch = e->src;
486
 
487
              if (flow_bb_inside_loop_p (loop, latch))
488
                {
489
                  if (loop->latch != NULL)
490
                    {
491
                      /* More than one latch edge.  */
492
                      loop->latch = NULL;
493
                      break;
494
                    }
495
                  loop->latch = latch;
496
                }
497
            }
498
        }
499
 
500
      free (dfs_order);
501
      free (rc_order);
502
    }
503
 
504
  sbitmap_free (headers);
505
 
506
  loops->exits = NULL;
507
  return VEC_length (loop_p, loops->larray);
508
}
509
 
510
/* Ratio of frequencies of edges so that one of more latch edges is
511
   considered to belong to inner loop with same header.  */
512
#define HEAVY_EDGE_RATIO 8
513
 
514
/* Minimum number of samples for that we apply
515
   find_subloop_latch_edge_by_profile heuristics.  */
516
#define HEAVY_EDGE_MIN_SAMPLES 10
517
 
518
/* If the profile info is available, finds an edge in LATCHES that much more
519
   frequent than the remaining edges.  Returns such an edge, or NULL if we do
520
   not find one.
521
 
522
   We do not use guessed profile here, only the measured one.  The guessed
523
   profile is usually too flat and unreliable for this (and it is mostly based
524
   on the loop structure of the program, so it does not make much sense to
525
   derive the loop structure from it).  */
526
 
527
static edge
528
find_subloop_latch_edge_by_profile (VEC (edge, heap) *latches)
529
{
530
  unsigned i;
531
  edge e, me = NULL;
532
  gcov_type mcount = 0, tcount = 0;
533
 
534
  for (i = 0; VEC_iterate (edge, latches, i, e); i++)
535
    {
536
      if (e->count > mcount)
537
        {
538
          me = e;
539
          mcount = e->count;
540
        }
541
      tcount += e->count;
542
    }
543
 
544
  if (tcount < HEAVY_EDGE_MIN_SAMPLES
545
      || (tcount - mcount) * HEAVY_EDGE_RATIO > tcount)
546
    return NULL;
547
 
548
  if (dump_file)
549
    fprintf (dump_file,
550
             "Found latch edge %d -> %d using profile information.\n",
551
             me->src->index, me->dest->index);
552
  return me;
553
}
554
 
555
/* Among LATCHES, guesses a latch edge of LOOP corresponding to subloop, based
556
   on the structure of induction variables.  Returns this edge, or NULL if we
557
   do not find any.
558
 
559
   We are quite conservative, and look just for an obvious simple innermost
560
   loop (which is the case where we would lose the most performance by not
561
   disambiguating the loop).  More precisely, we look for the following
562
   situation: The source of the chosen latch edge dominates sources of all
563
   the other latch edges.  Additionally, the header does not contain a phi node
564
   such that the argument from the chosen edge is equal to the argument from
565
   another edge.  */
566
 
567
static edge
568
find_subloop_latch_edge_by_ivs (struct loop *loop ATTRIBUTE_UNUSED, VEC (edge, heap) *latches)
569
{
570
  edge e, latch = VEC_index (edge, latches, 0);
571
  unsigned i;
572
  gimple phi;
573
  gimple_stmt_iterator psi;
574
  tree lop;
575
  basic_block bb;
576
 
577
  /* Find the candidate for the latch edge.  */
578
  for (i = 1; VEC_iterate (edge, latches, i, e); i++)
579
    if (dominated_by_p (CDI_DOMINATORS, latch->src, e->src))
580
      latch = e;
581
 
582
  /* Verify that it dominates all the latch edges.  */
583
  for (i = 0; VEC_iterate (edge, latches, i, e); i++)
584
    if (!dominated_by_p (CDI_DOMINATORS, e->src, latch->src))
585
      return NULL;
586
 
587
  /* Check for a phi node that would deny that this is a latch edge of
588
     a subloop.  */
589
  for (psi = gsi_start_phis (loop->header); !gsi_end_p (psi); gsi_next (&psi))
590
    {
591
      phi = gsi_stmt (psi);
592
      lop = PHI_ARG_DEF_FROM_EDGE (phi, latch);
593
 
594
      /* Ignore the values that are not changed inside the subloop.  */
595
      if (TREE_CODE (lop) != SSA_NAME
596
          || SSA_NAME_DEF_STMT (lop) == phi)
597
        continue;
598
      bb = gimple_bb (SSA_NAME_DEF_STMT (lop));
599
      if (!bb || !flow_bb_inside_loop_p (loop, bb))
600
        continue;
601
 
602
      for (i = 0; VEC_iterate (edge, latches, i, e); i++)
603
        if (e != latch
604
            && PHI_ARG_DEF_FROM_EDGE (phi, e) == lop)
605
          return NULL;
606
    }
607
 
608
  if (dump_file)
609
    fprintf (dump_file,
610
             "Found latch edge %d -> %d using iv structure.\n",
611
             latch->src->index, latch->dest->index);
612
  return latch;
613
}
614
 
615
/* If we can determine that one of the several latch edges of LOOP behaves
616
   as a latch edge of a separate subloop, returns this edge.  Otherwise
617
   returns NULL.  */
618
 
619
static edge
620
find_subloop_latch_edge (struct loop *loop)
621
{
622
  VEC (edge, heap) *latches = get_loop_latch_edges (loop);
623
  edge latch = NULL;
624
 
625
  if (VEC_length (edge, latches) > 1)
626
    {
627
      latch = find_subloop_latch_edge_by_profile (latches);
628
 
629
      if (!latch
630
          /* We consider ivs to guess the latch edge only in SSA.  Perhaps we
631
             should use cfghook for this, but it is hard to imagine it would
632
             be useful elsewhere.  */
633
          && current_ir_type () == IR_GIMPLE)
634
        latch = find_subloop_latch_edge_by_ivs (loop, latches);
635
    }
636
 
637
  VEC_free (edge, heap, latches);
638
  return latch;
639
}
640
 
641
/* Callback for make_forwarder_block.  Returns true if the edge E is marked
642
   in the set MFB_REIS_SET.  */
643
 
644
static struct pointer_set_t *mfb_reis_set;
645
static bool
646
mfb_redirect_edges_in_set (edge e)
647
{
648
  return pointer_set_contains (mfb_reis_set, e);
649
}
650
 
651
/* Creates a subloop of LOOP with latch edge LATCH.  */
652
 
653
static void
654
form_subloop (struct loop *loop, edge latch)
655
{
656
  edge_iterator ei;
657
  edge e, new_entry;
658
  struct loop *new_loop;
659
 
660
  mfb_reis_set = pointer_set_create ();
661
  FOR_EACH_EDGE (e, ei, loop->header->preds)
662
    {
663
      if (e != latch)
664
        pointer_set_insert (mfb_reis_set, e);
665
    }
666
  new_entry = make_forwarder_block (loop->header, mfb_redirect_edges_in_set,
667
                                    NULL);
668
  pointer_set_destroy (mfb_reis_set);
669
 
670
  loop->header = new_entry->src;
671
 
672
  /* Find the blocks and subloops that belong to the new loop, and add it to
673
     the appropriate place in the loop tree.  */
674
  new_loop = alloc_loop ();
675
  new_loop->header = new_entry->dest;
676
  new_loop->latch = latch->src;
677
  add_loop (new_loop, loop);
678
}
679
 
680
/* Make all the latch edges of LOOP to go to a single forwarder block --
681
   a new latch of LOOP.  */
682
 
683
static void
684
merge_latch_edges (struct loop *loop)
685
{
686
  VEC (edge, heap) *latches = get_loop_latch_edges (loop);
687
  edge latch, e;
688
  unsigned i;
689
 
690
  gcc_assert (VEC_length (edge, latches) > 0);
691
 
692
  if (VEC_length (edge, latches) == 1)
693
    loop->latch = VEC_index (edge, latches, 0)->src;
694
  else
695
    {
696
      if (dump_file)
697
        fprintf (dump_file, "Merged latch edges of loop %d\n", loop->num);
698
 
699
      mfb_reis_set = pointer_set_create ();
700
      for (i = 0; VEC_iterate (edge, latches, i, e); i++)
701
        pointer_set_insert (mfb_reis_set, e);
702
      latch = make_forwarder_block (loop->header, mfb_redirect_edges_in_set,
703
                                    NULL);
704
      pointer_set_destroy (mfb_reis_set);
705
 
706
      loop->header = latch->dest;
707
      loop->latch = latch->src;
708
    }
709
 
710
  VEC_free (edge, heap, latches);
711
}
712
 
713
/* LOOP may have several latch edges.  Transform it into (possibly several)
714
   loops with single latch edge.  */
715
 
716
static void
717
disambiguate_multiple_latches (struct loop *loop)
718
{
719
  edge e;
720
 
721
  /* We eliminate the multiple latches by splitting the header to the forwarder
722
     block F and the rest R, and redirecting the edges.  There are two cases:
723
 
724
     1) If there is a latch edge E that corresponds to a subloop (we guess
725
        that based on profile -- if it is taken much more often than the
726
        remaining edges; and on trees, using the information about induction
727
        variables of the loops), we redirect E to R, all the remaining edges to
728
        F, then rescan the loops and try again for the outer loop.
729
     2) If there is no such edge, we redirect all latch edges to F, and the
730
        entry edges to R, thus making F the single latch of the loop.  */
731
 
732
  if (dump_file)
733
    fprintf (dump_file, "Disambiguating loop %d with multiple latches\n",
734
             loop->num);
735
 
736
  /* During latch merging, we may need to redirect the entry edges to a new
737
     block.  This would cause problems if the entry edge was the one from the
738
     entry block.  To avoid having to handle this case specially, split
739
     such entry edge.  */
740
  e = find_edge (ENTRY_BLOCK_PTR, loop->header);
741
  if (e)
742
    split_edge (e);
743
 
744
  while (1)
745
    {
746
      e = find_subloop_latch_edge (loop);
747
      if (!e)
748
        break;
749
 
750
      form_subloop (loop, e);
751
    }
752
 
753
  merge_latch_edges (loop);
754
}
755
 
756
/* Split loops with multiple latch edges.  */
757
 
758
void
759
disambiguate_loops_with_multiple_latches (void)
760
{
761
  loop_iterator li;
762
  struct loop *loop;
763
 
764
  FOR_EACH_LOOP (li, loop, 0)
765
    {
766
      if (!loop->latch)
767
        disambiguate_multiple_latches (loop);
768
    }
769
}
770
 
771
/* Return nonzero if basic block BB belongs to LOOP.  */
772
bool
773
flow_bb_inside_loop_p (const struct loop *loop, const_basic_block bb)
774
{
775
  struct loop *source_loop;
776
 
777
  if (bb == ENTRY_BLOCK_PTR || bb == EXIT_BLOCK_PTR)
778
    return 0;
779
 
780
  source_loop = bb->loop_father;
781
  return loop == source_loop || flow_loop_nested_p (loop, source_loop);
782
}
783
 
784
/* Enumeration predicate for get_loop_body_with_size.  */
785
static bool
786
glb_enum_p (const_basic_block bb, const void *glb_loop)
787
{
788
  const struct loop *const loop = (const struct loop *) glb_loop;
789
  return (bb != loop->header
790
          && dominated_by_p (CDI_DOMINATORS, bb, loop->header));
791
}
792
 
793
/* Gets basic blocks of a LOOP.  Header is the 0-th block, rest is in dfs
794
   order against direction of edges from latch.  Specially, if
795
   header != latch, latch is the 1-st block.  LOOP cannot be the fake
796
   loop tree root, and its size must be at most MAX_SIZE.  The blocks
797
   in the LOOP body are stored to BODY, and the size of the LOOP is
798
   returned.  */
799
 
800
unsigned
801
get_loop_body_with_size (const struct loop *loop, basic_block *body,
802
                         unsigned max_size)
803
{
804
  return dfs_enumerate_from (loop->header, 1, glb_enum_p,
805
                             body, max_size, loop);
806
}
807
 
808
/* Gets basic blocks of a LOOP.  Header is the 0-th block, rest is in dfs
809
   order against direction of edges from latch.  Specially, if
810
   header != latch, latch is the 1-st block.  */
811
 
812
basic_block *
813
get_loop_body (const struct loop *loop)
814
{
815
  basic_block *body, bb;
816
  unsigned tv = 0;
817
 
818
  gcc_assert (loop->num_nodes);
819
 
820
  body = XCNEWVEC (basic_block, loop->num_nodes);
821
 
822
  if (loop->latch == EXIT_BLOCK_PTR)
823
    {
824
      /* There may be blocks unreachable from EXIT_BLOCK, hence we need to
825
         special-case the fake loop that contains the whole function.  */
826
      gcc_assert (loop->num_nodes == (unsigned) n_basic_blocks);
827
      body[tv++] = loop->header;
828
      body[tv++] = EXIT_BLOCK_PTR;
829
      FOR_EACH_BB (bb)
830
        body[tv++] = bb;
831
    }
832
  else
833
    tv = get_loop_body_with_size (loop, body, loop->num_nodes);
834
 
835
  gcc_assert (tv == loop->num_nodes);
836
  return body;
837
}
838
 
839
/* Fills dominance descendants inside LOOP of the basic block BB into
840
   array TOVISIT from index *TV.  */
841
 
842
static void
843
fill_sons_in_loop (const struct loop *loop, basic_block bb,
844
                   basic_block *tovisit, int *tv)
845
{
846
  basic_block son, postpone = NULL;
847
 
848
  tovisit[(*tv)++] = bb;
849
  for (son = first_dom_son (CDI_DOMINATORS, bb);
850
       son;
851
       son = next_dom_son (CDI_DOMINATORS, son))
852
    {
853
      if (!flow_bb_inside_loop_p (loop, son))
854
        continue;
855
 
856
      if (dominated_by_p (CDI_DOMINATORS, loop->latch, son))
857
        {
858
          postpone = son;
859
          continue;
860
        }
861
      fill_sons_in_loop (loop, son, tovisit, tv);
862
    }
863
 
864
  if (postpone)
865
    fill_sons_in_loop (loop, postpone, tovisit, tv);
866
}
867
 
868
/* Gets body of a LOOP (that must be different from the outermost loop)
869
   sorted by dominance relation.  Additionally, if a basic block s dominates
870
   the latch, then only blocks dominated by s are be after it.  */
871
 
872
basic_block *
873
get_loop_body_in_dom_order (const struct loop *loop)
874
{
875
  basic_block *tovisit;
876
  int tv;
877
 
878
  gcc_assert (loop->num_nodes);
879
 
880
  tovisit = XCNEWVEC (basic_block, loop->num_nodes);
881
 
882
  gcc_assert (loop->latch != EXIT_BLOCK_PTR);
883
 
884
  tv = 0;
885
  fill_sons_in_loop (loop, loop->header, tovisit, &tv);
886
 
887
  gcc_assert (tv == (int) loop->num_nodes);
888
 
889
  return tovisit;
890
}
891
 
892
/* Gets body of a LOOP sorted via provided BB_COMPARATOR.  */
893
 
894
basic_block *
895
get_loop_body_in_custom_order (const struct loop *loop,
896
                               int (*bb_comparator) (const void *, const void *))
897
{
898
  basic_block *bbs = get_loop_body (loop);
899
 
900
  qsort (bbs, loop->num_nodes, sizeof (basic_block), bb_comparator);
901
 
902
  return bbs;
903
}
904
 
905
/* Get body of a LOOP in breadth first sort order.  */
906
 
907
basic_block *
908
get_loop_body_in_bfs_order (const struct loop *loop)
909
{
910
  basic_block *blocks;
911
  basic_block bb;
912
  bitmap visited;
913
  unsigned int i = 0;
914
  unsigned int vc = 1;
915
 
916
  gcc_assert (loop->num_nodes);
917
  gcc_assert (loop->latch != EXIT_BLOCK_PTR);
918
 
919
  blocks = XCNEWVEC (basic_block, loop->num_nodes);
920
  visited = BITMAP_ALLOC (NULL);
921
 
922
  bb = loop->header;
923
  while (i < loop->num_nodes)
924
    {
925
      edge e;
926
      edge_iterator ei;
927
 
928
      if (!bitmap_bit_p (visited, bb->index))
929
        {
930
          /* This basic block is now visited */
931
          bitmap_set_bit (visited, bb->index);
932
          blocks[i++] = bb;
933
        }
934
 
935
      FOR_EACH_EDGE (e, ei, bb->succs)
936
        {
937
          if (flow_bb_inside_loop_p (loop, e->dest))
938
            {
939
              if (!bitmap_bit_p (visited, e->dest->index))
940
                {
941
                  bitmap_set_bit (visited, e->dest->index);
942
                  blocks[i++] = e->dest;
943
                }
944
            }
945
        }
946
 
947
      gcc_assert (i >= vc);
948
 
949
      bb = blocks[vc++];
950
    }
951
 
952
  BITMAP_FREE (visited);
953
  return blocks;
954
}
955
 
956
/* Hash function for struct loop_exit.  */
957
 
958
static hashval_t
959
loop_exit_hash (const void *ex)
960
{
961
  const struct loop_exit *const exit = (const struct loop_exit *) ex;
962
 
963
  return htab_hash_pointer (exit->e);
964
}
965
 
966
/* Equality function for struct loop_exit.  Compares with edge.  */
967
 
968
static int
969
loop_exit_eq (const void *ex, const void *e)
970
{
971
  const struct loop_exit *const exit = (const struct loop_exit *) ex;
972
 
973
  return exit->e == e;
974
}
975
 
976
/* Frees the list of loop exit descriptions EX.  */
977
 
978
static void
979
loop_exit_free (void *ex)
980
{
981
  struct loop_exit *exit = (struct loop_exit *) ex, *next;
982
 
983
  for (; exit; exit = next)
984
    {
985
      next = exit->next_e;
986
 
987
      exit->next->prev = exit->prev;
988
      exit->prev->next = exit->next;
989
 
990
      ggc_free (exit);
991
    }
992
}
993
 
994
/* Returns the list of records for E as an exit of a loop.  */
995
 
996
static struct loop_exit *
997
get_exit_descriptions (edge e)
998
{
999
  return (struct loop_exit *) htab_find_with_hash (current_loops->exits, e,
1000
                                                   htab_hash_pointer (e));
1001
}
1002
 
1003
/* Updates the lists of loop exits in that E appears.
1004
   If REMOVED is true, E is being removed, and we
1005
   just remove it from the lists of exits.
1006
   If NEW_EDGE is true and E is not a loop exit, we
1007
   do not try to remove it from loop exit lists.  */
1008
 
1009
void
1010
rescan_loop_exit (edge e, bool new_edge, bool removed)
1011
{
1012
  void **slot;
1013
  struct loop_exit *exits = NULL, *exit;
1014
  struct loop *aloop, *cloop;
1015
 
1016
  if (!loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS))
1017
    return;
1018
 
1019
  if (!removed
1020
      && e->src->loop_father != NULL
1021
      && e->dest->loop_father != NULL
1022
      && !flow_bb_inside_loop_p (e->src->loop_father, e->dest))
1023
    {
1024
      cloop = find_common_loop (e->src->loop_father, e->dest->loop_father);
1025
      for (aloop = e->src->loop_father;
1026
           aloop != cloop;
1027
           aloop = loop_outer (aloop))
1028
        {
1029
          exit = GGC_NEW (struct loop_exit);
1030
          exit->e = e;
1031
 
1032
          exit->next = aloop->exits->next;
1033
          exit->prev = aloop->exits;
1034
          exit->next->prev = exit;
1035
          exit->prev->next = exit;
1036
 
1037
          exit->next_e = exits;
1038
          exits = exit;
1039
        }
1040
    }
1041
 
1042
  if (!exits && new_edge)
1043
    return;
1044
 
1045
  slot = htab_find_slot_with_hash (current_loops->exits, e,
1046
                                   htab_hash_pointer (e),
1047
                                   exits ? INSERT : NO_INSERT);
1048
  if (!slot)
1049
    return;
1050
 
1051
  if (exits)
1052
    {
1053
      if (*slot)
1054
        loop_exit_free (*slot);
1055
      *slot = exits;
1056
    }
1057
  else
1058
    htab_clear_slot (current_loops->exits, slot);
1059
}
1060
 
1061
/* For each loop, record list of exit edges, and start maintaining these
1062
   lists.  */
1063
 
1064
void
1065
record_loop_exits (void)
1066
{
1067
  basic_block bb;
1068
  edge_iterator ei;
1069
  edge e;
1070
 
1071
  if (!current_loops)
1072
    return;
1073
 
1074
  if (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS))
1075
    return;
1076
  loops_state_set (LOOPS_HAVE_RECORDED_EXITS);
1077
 
1078
  gcc_assert (current_loops->exits == NULL);
1079
  current_loops->exits = htab_create_alloc (2 * number_of_loops (),
1080
                                            loop_exit_hash,
1081
                                            loop_exit_eq,
1082
                                            loop_exit_free,
1083
                                            ggc_calloc, ggc_free);
1084
 
1085
  FOR_EACH_BB (bb)
1086
    {
1087
      FOR_EACH_EDGE (e, ei, bb->succs)
1088
        {
1089
          rescan_loop_exit (e, true, false);
1090
        }
1091
    }
1092
}
1093
 
1094
/* Dumps information about the exit in *SLOT to FILE.
1095
   Callback for htab_traverse.  */
1096
 
1097
static int
1098
dump_recorded_exit (void **slot, void *file)
1099
{
1100
  struct loop_exit *exit = (struct loop_exit *) *slot;
1101
  unsigned n = 0;
1102
  edge e = exit->e;
1103
 
1104
  for (; exit != NULL; exit = exit->next_e)
1105
    n++;
1106
 
1107
  fprintf ((FILE*) file, "Edge %d->%d exits %u loops\n",
1108
           e->src->index, e->dest->index, n);
1109
 
1110
  return 1;
1111
}
1112
 
1113
/* Dumps the recorded exits of loops to FILE.  */
1114
 
1115
extern void dump_recorded_exits (FILE *);
1116
void
1117
dump_recorded_exits (FILE *file)
1118
{
1119
  if (!current_loops->exits)
1120
    return;
1121
  htab_traverse (current_loops->exits, dump_recorded_exit, file);
1122
}
1123
 
1124
/* Releases lists of loop exits.  */
1125
 
1126
void
1127
release_recorded_exits (void)
1128
{
1129
  gcc_assert (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS));
1130
  htab_delete (current_loops->exits);
1131
  current_loops->exits = NULL;
1132
  loops_state_clear (LOOPS_HAVE_RECORDED_EXITS);
1133
}
1134
 
1135
/* Returns the list of the exit edges of a LOOP.  */
1136
 
1137
VEC (edge, heap) *
1138
get_loop_exit_edges (const struct loop *loop)
1139
{
1140
  VEC (edge, heap) *edges = NULL;
1141
  edge e;
1142
  unsigned i;
1143
  basic_block *body;
1144
  edge_iterator ei;
1145
  struct loop_exit *exit;
1146
 
1147
  gcc_assert (loop->latch != EXIT_BLOCK_PTR);
1148
 
1149
  /* If we maintain the lists of exits, use them.  Otherwise we must
1150
     scan the body of the loop.  */
1151
  if (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS))
1152
    {
1153
      for (exit = loop->exits->next; exit->e; exit = exit->next)
1154
        VEC_safe_push (edge, heap, edges, exit->e);
1155
    }
1156
  else
1157
    {
1158
      body = get_loop_body (loop);
1159
      for (i = 0; i < loop->num_nodes; i++)
1160
        FOR_EACH_EDGE (e, ei, body[i]->succs)
1161
          {
1162
            if (!flow_bb_inside_loop_p (loop, e->dest))
1163
              VEC_safe_push (edge, heap, edges, e);
1164
          }
1165
      free (body);
1166
    }
1167
 
1168
  return edges;
1169
}
1170
 
1171
/* Counts the number of conditional branches inside LOOP.  */
1172
 
1173
unsigned
1174
num_loop_branches (const struct loop *loop)
1175
{
1176
  unsigned i, n;
1177
  basic_block * body;
1178
 
1179
  gcc_assert (loop->latch != EXIT_BLOCK_PTR);
1180
 
1181
  body = get_loop_body (loop);
1182
  n = 0;
1183
  for (i = 0; i < loop->num_nodes; i++)
1184
    if (EDGE_COUNT (body[i]->succs) >= 2)
1185
      n++;
1186
  free (body);
1187
 
1188
  return n;
1189
}
1190
 
1191
/* Adds basic block BB to LOOP.  */
1192
void
1193
add_bb_to_loop (basic_block bb, struct loop *loop)
1194
{
1195
  unsigned i;
1196
  loop_p ploop;
1197
  edge_iterator ei;
1198
  edge e;
1199
 
1200
  gcc_assert (bb->loop_father == NULL);
1201
  bb->loop_father = loop;
1202
  bb->loop_depth = loop_depth (loop);
1203
  loop->num_nodes++;
1204
  for (i = 0; VEC_iterate (loop_p, loop->superloops, i, ploop); i++)
1205
    ploop->num_nodes++;
1206
 
1207
  FOR_EACH_EDGE (e, ei, bb->succs)
1208
    {
1209
      rescan_loop_exit (e, true, false);
1210
    }
1211
  FOR_EACH_EDGE (e, ei, bb->preds)
1212
    {
1213
      rescan_loop_exit (e, true, false);
1214
    }
1215
}
1216
 
1217
/* Remove basic block BB from loops.  */
1218
void
1219
remove_bb_from_loops (basic_block bb)
1220
{
1221
  int i;
1222
  struct loop *loop = bb->loop_father;
1223
  loop_p ploop;
1224
  edge_iterator ei;
1225
  edge e;
1226
 
1227
  gcc_assert (loop != NULL);
1228
  loop->num_nodes--;
1229
  for (i = 0; VEC_iterate (loop_p, loop->superloops, i, ploop); i++)
1230
    ploop->num_nodes--;
1231
  bb->loop_father = NULL;
1232
  bb->loop_depth = 0;
1233
 
1234
  FOR_EACH_EDGE (e, ei, bb->succs)
1235
    {
1236
      rescan_loop_exit (e, false, true);
1237
    }
1238
  FOR_EACH_EDGE (e, ei, bb->preds)
1239
    {
1240
      rescan_loop_exit (e, false, true);
1241
    }
1242
}
1243
 
1244
/* Finds nearest common ancestor in loop tree for given loops.  */
1245
struct loop *
1246
find_common_loop (struct loop *loop_s, struct loop *loop_d)
1247
{
1248
  unsigned sdepth, ddepth;
1249
 
1250
  if (!loop_s) return loop_d;
1251
  if (!loop_d) return loop_s;
1252
 
1253
  sdepth = loop_depth (loop_s);
1254
  ddepth = loop_depth (loop_d);
1255
 
1256
  if (sdepth < ddepth)
1257
    loop_d = VEC_index (loop_p, loop_d->superloops, sdepth);
1258
  else if (sdepth > ddepth)
1259
    loop_s = VEC_index (loop_p, loop_s->superloops, ddepth);
1260
 
1261
  while (loop_s != loop_d)
1262
    {
1263
      loop_s = loop_outer (loop_s);
1264
      loop_d = loop_outer (loop_d);
1265
    }
1266
  return loop_s;
1267
}
1268
 
1269
/* Removes LOOP from structures and frees its data.  */
1270
 
1271
void
1272
delete_loop (struct loop *loop)
1273
{
1274
  /* Remove the loop from structure.  */
1275
  flow_loop_tree_node_remove (loop);
1276
 
1277
  /* Remove loop from loops array.  */
1278
  VEC_replace (loop_p, current_loops->larray, loop->num, NULL);
1279
 
1280
  /* Free loop data.  */
1281
  flow_loop_free (loop);
1282
}
1283
 
1284
/* Cancels the LOOP; it must be innermost one.  */
1285
 
1286
static void
1287
cancel_loop (struct loop *loop)
1288
{
1289
  basic_block *bbs;
1290
  unsigned i;
1291
  struct loop *outer = loop_outer (loop);
1292
 
1293
  gcc_assert (!loop->inner);
1294
 
1295
  /* Move blocks up one level (they should be removed as soon as possible).  */
1296
  bbs = get_loop_body (loop);
1297
  for (i = 0; i < loop->num_nodes; i++)
1298
    bbs[i]->loop_father = outer;
1299
 
1300
  delete_loop (loop);
1301
}
1302
 
1303
/* Cancels LOOP and all its subloops.  */
1304
void
1305
cancel_loop_tree (struct loop *loop)
1306
{
1307
  while (loop->inner)
1308
    cancel_loop_tree (loop->inner);
1309
  cancel_loop (loop);
1310
}
1311
 
1312
/* Checks that information about loops is correct
1313
     -- sizes of loops are all right
1314
     -- results of get_loop_body really belong to the loop
1315
     -- loop header have just single entry edge and single latch edge
1316
     -- loop latches have only single successor that is header of their loop
1317
     -- irreducible loops are correctly marked
1318
  */
1319
void
1320
verify_loop_structure (void)
1321
{
1322
  unsigned *sizes, i, j;
1323
  sbitmap irreds;
1324
  basic_block *bbs, bb;
1325
  struct loop *loop;
1326
  int err = 0;
1327
  edge e;
1328
  unsigned num = number_of_loops ();
1329
  loop_iterator li;
1330
  struct loop_exit *exit, *mexit;
1331
 
1332
  /* Check sizes.  */
1333
  sizes = XCNEWVEC (unsigned, num);
1334
  sizes[0] = 2;
1335
 
1336
  FOR_EACH_BB (bb)
1337
    for (loop = bb->loop_father; loop; loop = loop_outer (loop))
1338
      sizes[loop->num]++;
1339
 
1340
  FOR_EACH_LOOP (li, loop, LI_INCLUDE_ROOT)
1341
    {
1342
      i = loop->num;
1343
 
1344
      if (loop->num_nodes != sizes[i])
1345
        {
1346
          error ("size of loop %d should be %d, not %d",
1347
                   i, sizes[i], loop->num_nodes);
1348
          err = 1;
1349
        }
1350
    }
1351
 
1352
  /* Check get_loop_body.  */
1353
  FOR_EACH_LOOP (li, loop, 0)
1354
    {
1355
      bbs = get_loop_body (loop);
1356
 
1357
      for (j = 0; j < loop->num_nodes; j++)
1358
        if (!flow_bb_inside_loop_p (loop, bbs[j]))
1359
          {
1360
            error ("bb %d do not belong to loop %d",
1361
                    bbs[j]->index, loop->num);
1362
            err = 1;
1363
          }
1364
      free (bbs);
1365
    }
1366
 
1367
  /* Check headers and latches.  */
1368
  FOR_EACH_LOOP (li, loop, 0)
1369
    {
1370
      i = loop->num;
1371
 
1372
      if (loops_state_satisfies_p (LOOPS_HAVE_PREHEADERS)
1373
          && EDGE_COUNT (loop->header->preds) != 2)
1374
        {
1375
          error ("loop %d's header does not have exactly 2 entries", i);
1376
          err = 1;
1377
        }
1378
      if (loops_state_satisfies_p (LOOPS_HAVE_SIMPLE_LATCHES))
1379
        {
1380
          if (!single_succ_p (loop->latch))
1381
            {
1382
              error ("loop %d's latch does not have exactly 1 successor", i);
1383
              err = 1;
1384
            }
1385
          if (single_succ (loop->latch) != loop->header)
1386
            {
1387
              error ("loop %d's latch does not have header as successor", i);
1388
              err = 1;
1389
            }
1390
          if (loop->latch->loop_father != loop)
1391
            {
1392
              error ("loop %d's latch does not belong directly to it", i);
1393
              err = 1;
1394
            }
1395
        }
1396
      if (loop->header->loop_father != loop)
1397
        {
1398
          error ("loop %d's header does not belong directly to it", i);
1399
          err = 1;
1400
        }
1401
      if (loops_state_satisfies_p (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS)
1402
          && (loop_latch_edge (loop)->flags & EDGE_IRREDUCIBLE_LOOP))
1403
        {
1404
          error ("loop %d's latch is marked as part of irreducible region", i);
1405
          err = 1;
1406
        }
1407
    }
1408
 
1409
  /* Check irreducible loops.  */
1410
  if (loops_state_satisfies_p (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS))
1411
    {
1412
      /* Record old info.  */
1413
      irreds = sbitmap_alloc (last_basic_block);
1414
      FOR_EACH_BB (bb)
1415
        {
1416
          edge_iterator ei;
1417
          if (bb->flags & BB_IRREDUCIBLE_LOOP)
1418
            SET_BIT (irreds, bb->index);
1419
          else
1420
            RESET_BIT (irreds, bb->index);
1421
          FOR_EACH_EDGE (e, ei, bb->succs)
1422
            if (e->flags & EDGE_IRREDUCIBLE_LOOP)
1423
              e->flags |= EDGE_ALL_FLAGS + 1;
1424
        }
1425
 
1426
      /* Recount it.  */
1427
      mark_irreducible_loops ();
1428
 
1429
      /* Compare.  */
1430
      FOR_EACH_BB (bb)
1431
        {
1432
          edge_iterator ei;
1433
 
1434
          if ((bb->flags & BB_IRREDUCIBLE_LOOP)
1435
              && !TEST_BIT (irreds, bb->index))
1436
            {
1437
              error ("basic block %d should be marked irreducible", bb->index);
1438
              err = 1;
1439
            }
1440
          else if (!(bb->flags & BB_IRREDUCIBLE_LOOP)
1441
              && TEST_BIT (irreds, bb->index))
1442
            {
1443
              error ("basic block %d should not be marked irreducible", bb->index);
1444
              err = 1;
1445
            }
1446
          FOR_EACH_EDGE (e, ei, bb->succs)
1447
            {
1448
              if ((e->flags & EDGE_IRREDUCIBLE_LOOP)
1449
                  && !(e->flags & (EDGE_ALL_FLAGS + 1)))
1450
                {
1451
                  error ("edge from %d to %d should be marked irreducible",
1452
                         e->src->index, e->dest->index);
1453
                  err = 1;
1454
                }
1455
              else if (!(e->flags & EDGE_IRREDUCIBLE_LOOP)
1456
                       && (e->flags & (EDGE_ALL_FLAGS + 1)))
1457
                {
1458
                  error ("edge from %d to %d should not be marked irreducible",
1459
                         e->src->index, e->dest->index);
1460
                  err = 1;
1461
                }
1462
              e->flags &= ~(EDGE_ALL_FLAGS + 1);
1463
            }
1464
        }
1465
      free (irreds);
1466
    }
1467
 
1468
  /* Check the recorded loop exits.  */
1469
  FOR_EACH_LOOP (li, loop, 0)
1470
    {
1471
      if (!loop->exits || loop->exits->e != NULL)
1472
        {
1473
          error ("corrupted head of the exits list of loop %d",
1474
                 loop->num);
1475
          err = 1;
1476
        }
1477
      else
1478
        {
1479
          /* Check that the list forms a cycle, and all elements except
1480
             for the head are nonnull.  */
1481
          for (mexit = loop->exits, exit = mexit->next, i = 0;
1482
               exit->e && exit != mexit;
1483
               exit = exit->next)
1484
            {
1485
              if (i++ & 1)
1486
                mexit = mexit->next;
1487
            }
1488
 
1489
          if (exit != loop->exits)
1490
            {
1491
              error ("corrupted exits list of loop %d", loop->num);
1492
              err = 1;
1493
            }
1494
        }
1495
 
1496
      if (!loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS))
1497
        {
1498
          if (loop->exits->next != loop->exits)
1499
            {
1500
              error ("nonempty exits list of loop %d, but exits are not recorded",
1501
                     loop->num);
1502
              err = 1;
1503
            }
1504
        }
1505
    }
1506
 
1507
  if (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS))
1508
    {
1509
      unsigned n_exits = 0, eloops;
1510
 
1511
      memset (sizes, 0, sizeof (unsigned) * num);
1512
      FOR_EACH_BB (bb)
1513
        {
1514
          edge_iterator ei;
1515
          if (bb->loop_father == current_loops->tree_root)
1516
            continue;
1517
          FOR_EACH_EDGE (e, ei, bb->succs)
1518
            {
1519
              if (flow_bb_inside_loop_p (bb->loop_father, e->dest))
1520
                continue;
1521
 
1522
              n_exits++;
1523
              exit = get_exit_descriptions (e);
1524
              if (!exit)
1525
                {
1526
                  error ("Exit %d->%d not recorded",
1527
                         e->src->index, e->dest->index);
1528
                  err = 1;
1529
                }
1530
              eloops = 0;
1531
              for (; exit; exit = exit->next_e)
1532
                eloops++;
1533
 
1534
              for (loop = bb->loop_father;
1535
                   loop != e->dest->loop_father;
1536
                   loop = loop_outer (loop))
1537
                {
1538
                  eloops--;
1539
                  sizes[loop->num]++;
1540
                }
1541
 
1542
              if (eloops != 0)
1543
                {
1544
                  error ("Wrong list of exited loops for edge  %d->%d",
1545
                         e->src->index, e->dest->index);
1546
                  err = 1;
1547
                }
1548
            }
1549
        }
1550
 
1551
      if (n_exits != htab_elements (current_loops->exits))
1552
        {
1553
          error ("Too many loop exits recorded");
1554
          err = 1;
1555
        }
1556
 
1557
      FOR_EACH_LOOP (li, loop, 0)
1558
        {
1559
          eloops = 0;
1560
          for (exit = loop->exits->next; exit->e; exit = exit->next)
1561
            eloops++;
1562
          if (eloops != sizes[loop->num])
1563
            {
1564
              error ("%d exits recorded for loop %d (having %d exits)",
1565
                     eloops, loop->num, sizes[loop->num]);
1566
              err = 1;
1567
            }
1568
        }
1569
    }
1570
 
1571
  gcc_assert (!err);
1572
 
1573
  free (sizes);
1574
}
1575
 
1576
/* Returns latch edge of LOOP.  */
1577
edge
1578
loop_latch_edge (const struct loop *loop)
1579
{
1580
  return find_edge (loop->latch, loop->header);
1581
}
1582
 
1583
/* Returns preheader edge of LOOP.  */
1584
edge
1585
loop_preheader_edge (const struct loop *loop)
1586
{
1587
  edge e;
1588
  edge_iterator ei;
1589
 
1590
  gcc_assert (loops_state_satisfies_p (LOOPS_HAVE_PREHEADERS));
1591
 
1592
  FOR_EACH_EDGE (e, ei, loop->header->preds)
1593
    if (e->src != loop->latch)
1594
      break;
1595
 
1596
  return e;
1597
}
1598
 
1599
/* Returns true if E is an exit of LOOP.  */
1600
 
1601
bool
1602
loop_exit_edge_p (const struct loop *loop, const_edge e)
1603
{
1604
  return (flow_bb_inside_loop_p (loop, e->src)
1605
          && !flow_bb_inside_loop_p (loop, e->dest));
1606
}
1607
 
1608
/* Returns the single exit edge of LOOP, or NULL if LOOP has either no exit
1609
   or more than one exit.  If loops do not have the exits recorded, NULL
1610
   is returned always.  */
1611
 
1612
edge
1613
single_exit (const struct loop *loop)
1614
{
1615
  struct loop_exit *exit = loop->exits->next;
1616
 
1617
  if (!loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS))
1618
    return NULL;
1619
 
1620
  if (exit->e && exit->next == loop->exits)
1621
    return exit->e;
1622
  else
1623
    return NULL;
1624
}
1625
 
1626
/* Returns true when BB has an edge exiting LOOP.  */
1627
 
1628
bool
1629
is_loop_exit (struct loop *loop, basic_block bb)
1630
{
1631
  edge e;
1632
  edge_iterator ei;
1633
 
1634
  FOR_EACH_EDGE (e, ei, bb->preds)
1635
    if (loop_exit_edge_p (loop, e))
1636
      return true;
1637
 
1638
  return false;
1639
}

powered by: WebSVN 2.1.0

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