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

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-dev/] [or1k-gcc/] [gcc/] [hw-doloop.c] - Blame information for rev 684

Details | Compare with Previous | View Log

Line No. Rev Author Line
1 684 jeremybenn
/* Code to analyze doloop loops in order for targets to perform late
2
   optimizations converting doloops to other forms of hardware loops.
3
   Copyright (C) 2011 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 "flags.h"
27
#include "expr.h"
28
#include "hard-reg-set.h"
29
#include "regs.h"
30
#include "basic-block.h"
31
#include "tm_p.h"
32
#include "df.h"
33
#include "cfglayout.h"
34
#include "cfgloop.h"
35
#include "output.h"
36
#include "recog.h"
37
#include "target.h"
38
#include "hw-doloop.h"
39
 
40
#ifdef HAVE_doloop_end
41
 
42
/* Dump information collected in LOOPS.  */
43
static void
44
dump_hwloops (hwloop_info loops)
45
{
46
  hwloop_info loop;
47
 
48
  for (loop = loops; loop; loop = loop->next)
49
    {
50
      hwloop_info i;
51
      basic_block b;
52
      unsigned ix;
53
 
54
      fprintf (dump_file, ";; loop %d: ", loop->loop_no);
55
      if (loop->bad)
56
        fprintf (dump_file, "(bad) ");
57
      fprintf (dump_file, "{head:%d, depth:%d, reg:%u}",
58
               loop->head == NULL ? -1 : loop->head->index,
59
               loop->depth, REGNO (loop->iter_reg));
60
 
61
      fprintf (dump_file, " blocks: [ ");
62
      for (ix = 0; VEC_iterate (basic_block, loop->blocks, ix, b); ix++)
63
        fprintf (dump_file, "%d ", b->index);
64
      fprintf (dump_file, "] ");
65
 
66
      fprintf (dump_file, " inner loops: [ ");
67
      for (ix = 0; VEC_iterate (hwloop_info, loop->loops, ix, i); ix++)
68
        fprintf (dump_file, "%d ", i->loop_no);
69
      fprintf (dump_file, "]\n");
70
    }
71
  fprintf (dump_file, "\n");
72
}
73
 
74
/* Return true if BB is part of LOOP.  */
75
static bool
76
bb_in_loop_p (hwloop_info loop, basic_block bb)
77
{
78
  return bitmap_bit_p (loop->block_bitmap, bb->index);
79
}
80
 
81
/* Scan the blocks of LOOP (and its inferiors), and record things such as
82
   hard registers set, jumps out of and within the loop.  */
83
static void
84
scan_loop (hwloop_info loop)
85
{
86
  unsigned ix;
87
  basic_block bb;
88
 
89
  if (loop->bad)
90
    return;
91
 
92
  if (REGNO_REG_SET_P (df_get_live_in (loop->successor),
93
                       REGNO (loop->iter_reg)))
94
    loop->iter_reg_used_outside = true;
95
 
96
  for (ix = 0; VEC_iterate (basic_block, loop->blocks, ix, bb); ix++)
97
    {
98
      rtx insn;
99
      edge e;
100
      edge_iterator ei;
101
 
102
      if (bb != loop->tail)
103
        FOR_EACH_EDGE (e, ei, bb->succs)
104
          {
105
            if (bb_in_loop_p (loop, e->dest))
106
              {
107
                if (!(e->flags & EDGE_FALLTHRU))
108
                  loop->jumps_within = true;
109
              }
110
            else
111
              {
112
                loop->jumps_outof = true;
113
                if (!loop->bad)
114
                  gcc_assert (!REGNO_REG_SET_P (df_get_live_in (e->dest),
115
                                                REGNO (loop->iter_reg)));
116
              }
117
          }
118
 
119
      for (insn = BB_HEAD (bb);
120
           insn != NEXT_INSN (BB_END (bb));
121
           insn = NEXT_INSN (insn))
122
        {
123
          df_ref *def_rec;
124
          HARD_REG_SET set_this_insn;
125
 
126
          if (!NONDEBUG_INSN_P (insn))
127
            continue;
128
 
129
          if (recog_memoized (insn) < 0
130
              && (GET_CODE (PATTERN (insn)) == ASM_INPUT
131
                  || asm_noperands (PATTERN (insn)) >= 0))
132
            loop->has_asm = true;
133
 
134
          CLEAR_HARD_REG_SET (set_this_insn);
135
          for (def_rec = DF_INSN_DEFS (insn); *def_rec; def_rec++)
136
            {
137
              rtx dreg = DF_REF_REG (*def_rec);
138
 
139
              if (!REG_P (dreg))
140
                continue;
141
 
142
              add_to_hard_reg_set (&set_this_insn, GET_MODE (dreg),
143
                                   REGNO (dreg));
144
            }
145
 
146
          if (insn == loop->loop_end)
147
            CLEAR_HARD_REG_BIT (set_this_insn, REGNO (loop->iter_reg));
148
          else if (reg_mentioned_p (loop->iter_reg, PATTERN (insn)))
149
            loop->iter_reg_used = true;
150
          IOR_HARD_REG_SET (loop->regs_set_in_loop, set_this_insn);
151
        }
152
    }
153
}
154
 
155
/* Compute the incoming_dest and incoming_src members of LOOP by
156
   identifying the edges that jump into the loop.  If there is more
157
   than one block that jumps into the loop, incoming_src will be set
158
   to NULL; likewise, if there is more than one block in the loop that
159
   is the destination of an incoming edge, incoming_dest will be NULL.
160
 
161
   Return true if either of these two fields is nonnull, false
162
   otherwise.  */
163
static bool
164
process_incoming_edges (hwloop_info loop)
165
{
166
  edge e;
167
  edge_iterator ei;
168
  bool first = true;
169
 
170
  FOR_EACH_EDGE (e, ei, loop->incoming)
171
    {
172
      if (first)
173
        {
174
          loop->incoming_src = e->src;
175
          loop->incoming_dest = e->dest;
176
          first = false;
177
        }
178
      else
179
        {
180
          if (e->dest != loop->incoming_dest)
181
            loop->incoming_dest = NULL;
182
          if (e->src != loop->incoming_src)
183
            loop->incoming_src = NULL;
184
        }
185
    }
186
  if (loop->incoming_src == NULL && loop->incoming_dest == NULL)
187
    return false;
188
 
189
  return true;
190
}
191
 
192
/* Try to identify a forwarder block that jump into LOOP, and add it to
193
   the set of blocks in the loop, updating the vector of incoming blocks as
194
   well.  This transformation gives a second chance to loops we couldn't
195
   otherwise handle by increasing the chance that we'll end up with one
196
   incoming_src block.
197
   Return true if we made a change, false otherwise.  */
198
static bool
199
add_forwarder_blocks (hwloop_info loop)
200
{
201
  edge e;
202
  edge_iterator ei;
203
 
204
  FOR_EACH_EDGE (e, ei, loop->incoming)
205
    {
206
      if (forwarder_block_p (e->src))
207
        {
208
          edge e2;
209
          edge_iterator ei2;
210
 
211
          if (dump_file)
212
            fprintf (dump_file,
213
                     ";; Adding forwarder block %d to loop %d and retrying\n",
214
                     e->src->index, loop->loop_no);
215
          VEC_safe_push (basic_block, heap, loop->blocks, e->src);
216
          bitmap_set_bit (loop->block_bitmap, e->src->index);
217
          FOR_EACH_EDGE (e2, ei2, e->src->preds)
218
            VEC_safe_push (edge, gc, loop->incoming, e2);
219
          VEC_unordered_remove (edge, loop->incoming, ei.index);
220
          return true;
221
        }
222
    }
223
  return false;
224
}
225
 
226
/* Called from reorg_loops when a potential loop end is found.  LOOP is
227
   a newly set up structure describing the loop, it is this function's
228
   responsibility to fill most of it.  TAIL_BB and TAIL_INSN point to the
229
   loop_end insn and its enclosing basic block.  REG is the loop counter
230
   register.
231
   For our purposes, a loop is defined by the set of blocks reachable from
232
   the loop head in which the loop counter register is live.  This matches
233
   the expected use; targets that call into this code usually replace the
234
   loop counter with a different special register.  */
235
static void
236
discover_loop (hwloop_info loop, basic_block tail_bb, rtx tail_insn, rtx reg)
237
{
238
  bool found_tail;
239
  unsigned dwork = 0;
240
  basic_block bb;
241
  VEC (basic_block,heap) *works;
242
 
243
  loop->tail = tail_bb;
244
  loop->loop_end = tail_insn;
245
  loop->iter_reg = reg;
246
  loop->incoming = VEC_alloc (edge, gc, 2);
247
  loop->start_label = JUMP_LABEL (tail_insn);
248
 
249
  if (EDGE_COUNT (tail_bb->succs) != 2)
250
    {
251
      loop->bad = true;
252
      return;
253
    }
254
  loop->head = BRANCH_EDGE (tail_bb)->dest;
255
  loop->successor = FALLTHRU_EDGE (tail_bb)->dest;
256
 
257
  works = VEC_alloc (basic_block, heap, 20);
258
  VEC_safe_push (basic_block, heap, works, loop->head);
259
 
260
  found_tail = false;
261
  for (dwork = 0; VEC_iterate (basic_block, works, dwork, bb); dwork++)
262
    {
263
      edge e;
264
      edge_iterator ei;
265
      if (bb == EXIT_BLOCK_PTR)
266
        {
267
          /* We've reached the exit block.  The loop must be bad. */
268
          if (dump_file)
269
            fprintf (dump_file,
270
                     ";; Loop is bad - reached exit block while scanning\n");
271
          loop->bad = true;
272
          break;
273
        }
274
 
275
      if (bitmap_bit_p (loop->block_bitmap, bb->index))
276
        continue;
277
 
278
      /* We've not seen this block before.  Add it to the loop's
279
         list and then add each successor to the work list.  */
280
 
281
      VEC_safe_push (basic_block, heap, loop->blocks, bb);
282
      bitmap_set_bit (loop->block_bitmap, bb->index);
283
 
284
      if (bb == tail_bb)
285
        found_tail = true;
286
      else
287
        {
288
          FOR_EACH_EDGE (e, ei, bb->succs)
289
            {
290
              basic_block succ = EDGE_SUCC (bb, ei.index)->dest;
291
              if (REGNO_REG_SET_P (df_get_live_in (succ),
292
                                   REGNO (loop->iter_reg)))
293
                VEC_safe_push (basic_block, heap, works, succ);
294
            }
295
        }
296
    }
297
 
298
  if (!found_tail)
299
    loop->bad = true;
300
 
301
  /* Find the predecessor, and make sure nothing else jumps into this loop.  */
302
  if (!loop->bad)
303
    {
304
      FOR_EACH_VEC_ELT (basic_block, loop->blocks, dwork, bb)
305
        {
306
          edge e;
307
          edge_iterator ei;
308
          FOR_EACH_EDGE (e, ei, bb->preds)
309
            {
310
              basic_block pred = e->src;
311
 
312
              if (!bb_in_loop_p (loop, pred))
313
                {
314
                  if (dump_file)
315
                    fprintf (dump_file, ";; Loop %d: incoming edge %d -> %d\n",
316
                             loop->loop_no, pred->index,
317
                             e->dest->index);
318
                  VEC_safe_push (edge, gc, loop->incoming, e);
319
                }
320
            }
321
        }
322
 
323
      if (!process_incoming_edges (loop))
324
        {
325
          if (dump_file)
326
            fprintf (dump_file,
327
                     ";; retrying loop %d with forwarder blocks\n",
328
                     loop->loop_no);
329
          if (!add_forwarder_blocks (loop))
330
            {
331
              if (dump_file)
332
                fprintf (dump_file, ";; No forwarder blocks found\n");
333
              loop->bad = true;
334
            }
335
          else if (!process_incoming_edges (loop))
336
            {
337
              if (dump_file)
338
                fprintf (dump_file,
339
                         ";; can't find suitable entry for loop %d\n",
340
                         loop->loop_no);
341
            }
342
        }
343
    }
344
 
345
  VEC_free (basic_block, heap, works);
346
}
347
 
348
/* Analyze the structure of the loops in the current function.  Use
349
   STACK for bitmap allocations.  Returns all the valid candidates for
350
   hardware loops found in this function.  HOOKS is the argument
351
   passed to reorg_loops, used here to find the iteration registers
352
   from a loop_end pattern.  */
353
static hwloop_info
354
discover_loops (bitmap_obstack *stack, struct hw_doloop_hooks *hooks)
355
{
356
  hwloop_info loops = NULL;
357
  hwloop_info loop;
358
  basic_block bb;
359
  int nloops = 0;
360
 
361
  /* Find all the possible loop tails.  This means searching for every
362
     loop_end instruction.  For each one found, create a hwloop_info
363
     structure and add the head block to the work list. */
364
  FOR_EACH_BB (bb)
365
    {
366
      rtx tail = BB_END (bb);
367
      rtx insn, reg;
368
 
369
      while (tail && GET_CODE (tail) == NOTE && tail != BB_HEAD (bb))
370
        tail = PREV_INSN (tail);
371
 
372
      if (tail == NULL_RTX)
373
        continue;
374
 
375
      if (!JUMP_P (tail))
376
        continue;
377
      reg = hooks->end_pattern_reg (tail);
378
      if (reg == NULL_RTX)
379
        continue;
380
 
381
      /* A possible loop end */
382
 
383
      /* There's a degenerate case we can handle - an empty loop consisting
384
         of only a back branch.  Handle that by deleting the branch.  */
385
      insn = JUMP_LABEL (tail);
386
      while (insn && !NONDEBUG_INSN_P (insn))
387
        insn = NEXT_INSN (insn);
388
      if (insn == tail)
389
        {
390
          basic_block succ = FALLTHRU_EDGE (bb)->dest;
391
          if (dump_file)
392
            {
393
              fprintf (dump_file, ";; degenerate loop ending at\n");
394
              print_rtl_single (dump_file, tail);
395
            }
396
          if (!REGNO_REG_SET_P (df_get_live_in (succ), REGNO (reg)))
397
            {
398
              if (dump_file)
399
                fprintf (dump_file, ";; deleting it\n");
400
              delete_insn_and_edges (tail);
401
              continue;
402
            }
403
        }
404
 
405
      loop = XCNEW (struct hwloop_info_d);
406
      loop->next = loops;
407
      loops = loop;
408
      loop->loop_no = nloops++;
409
      loop->blocks = VEC_alloc (basic_block, heap, 20);
410
      loop->block_bitmap = BITMAP_ALLOC (stack);
411
 
412
      if (dump_file)
413
        {
414
          fprintf (dump_file, ";; potential loop %d ending at\n",
415
                   loop->loop_no);
416
          print_rtl_single (dump_file, tail);
417
        }
418
 
419
      discover_loop (loop, bb, tail, reg);
420
    }
421
 
422
  /* Compute loop nestings.  Given two loops A and B, either the sets
423
     of their blocks don't intersect at all, or one is the subset of
424
     the other, or the blocks don't form a good nesting structure.  */
425
  for (loop = loops; loop; loop = loop->next)
426
    {
427
      hwloop_info other;
428
 
429
      if (loop->bad)
430
        continue;
431
 
432
      for (other = loops; other; other = other->next)
433
        {
434
          if (other->bad)
435
            continue;
436
 
437
          if (!bitmap_intersect_p (other->block_bitmap, loop->block_bitmap))
438
            continue;
439
          if (!bitmap_intersect_compl_p (other->block_bitmap,
440
                                         loop->block_bitmap))
441
            VEC_safe_push (hwloop_info, heap, loop->loops, other);
442
          else if (!bitmap_intersect_compl_p (loop->block_bitmap,
443
                                              other->block_bitmap))
444
            VEC_safe_push (hwloop_info, heap, other->loops, loop);
445
          else
446
            {
447
              if (dump_file)
448
                fprintf (dump_file,
449
                         ";; can't find suitable nesting for loops %d and %d\n",
450
                         loop->loop_no, other->loop_no);
451
              loop->bad = other->bad = true;
452
            }
453
        }
454
    }
455
 
456
  if (dump_file)
457
    dump_hwloops (loops);
458
 
459
  return loops;
460
}
461
 
462
/* Free up the loop structures in LOOPS.  */
463
static void
464
free_loops (hwloop_info loops)
465
{
466
  while (loops)
467
    {
468
      hwloop_info loop = loops;
469
      loops = loop->next;
470
      VEC_free (hwloop_info, heap, loop->loops);
471
      VEC_free (basic_block, heap, loop->blocks);
472
      BITMAP_FREE (loop->block_bitmap);
473
      XDELETE (loop);
474
    }
475
}
476
 
477
#define BB_AUX_INDEX(BB) ((intptr_t) (BB)->aux)
478
 
479
/* Initialize the aux fields to give ascending indices to basic blocks.  */
480
static void
481
set_bb_indices (void)
482
{
483
  basic_block bb;
484
  intptr_t index;
485
 
486
  index = 0;
487
  FOR_EACH_BB (bb)
488
    bb->aux = (void *) index++;
489
}
490
 
491
/* The taken-branch edge from the loop end can actually go forward.
492
   If the target's hardware loop support requires that the loop end be
493
   after the loop start, try to reorder a loop's basic blocks when we
494
   find such a case.
495
   This is not very aggressive; it only moves at most one block.  It
496
   does not introduce new branches into loops; it may remove them, or
497
   it may switch fallthru/jump edges.  */
498
static void
499
reorder_loops (hwloop_info loops)
500
{
501
  basic_block bb;
502
  hwloop_info loop;
503
 
504
  cfg_layout_initialize (0);
505
 
506
  set_bb_indices ();
507
 
508
  for (loop = loops; loop; loop = loop->next)
509
    {
510
      edge e;
511
      edge_iterator ei;
512
 
513
      if (loop->bad)
514
        continue;
515
 
516
      if (BB_AUX_INDEX (loop->head) <= BB_AUX_INDEX (loop->tail))
517
        continue;
518
 
519
      FOR_EACH_EDGE (e, ei, loop->head->succs)
520
        {
521
          if (bitmap_bit_p (loop->block_bitmap, e->dest->index)
522
              && BB_AUX_INDEX (e->dest) < BB_AUX_INDEX (loop->tail))
523
            {
524
              basic_block start_bb = e->dest;
525
              basic_block start_prev_bb = start_bb->prev_bb;
526
 
527
              if (dump_file)
528
                fprintf (dump_file, ";; Moving block %d before block %d\n",
529
                         loop->head->index, start_bb->index);
530
              loop->head->prev_bb->next_bb = loop->head->next_bb;
531
              loop->head->next_bb->prev_bb = loop->head->prev_bb;
532
 
533
              loop->head->prev_bb = start_prev_bb;
534
              loop->head->next_bb = start_bb;
535
              start_prev_bb->next_bb = start_bb->prev_bb = loop->head;
536
 
537
              set_bb_indices ();
538
              break;
539
            }
540
        }
541
      loops = loops->next;
542
    }
543
 
544
  FOR_EACH_BB (bb)
545
    {
546
      if (bb->next_bb != EXIT_BLOCK_PTR)
547
        bb->aux = bb->next_bb;
548
      else
549
        bb->aux = NULL;
550
    }
551
  cfg_layout_finalize ();
552
  clear_aux_for_blocks ();
553
  df_analyze ();
554
}
555
 
556
/* Call the OPT function for LOOP and all of its sub-loops.  This is
557
   done in a depth-first search; innermost loops are visited first.
558
   OPTIMIZE and FAIL are the functions passed to reorg_loops by the
559
   target's reorg pass.  */
560
static void
561
optimize_loop (hwloop_info loop, struct hw_doloop_hooks *hooks)
562
{
563
  int ix;
564
  hwloop_info inner;
565
  int inner_depth = 0;
566
 
567
  if (loop->visited)
568
    return;
569
 
570
  loop->visited = 1;
571
 
572
  if (loop->bad)
573
    {
574
      if (dump_file)
575
        fprintf (dump_file, ";; loop %d bad when found\n", loop->loop_no);
576
      goto bad_loop;
577
    }
578
 
579
  /* Every loop contains in its list of inner loops every loop nested inside
580
     it, even if there are intermediate loops.  This works because we're doing
581
     a depth-first search here and never visit a loop more than once.
582
     Recursion depth is effectively limited by the number of available
583
     hardware registers.  */
584
  for (ix = 0; VEC_iterate (hwloop_info, loop->loops, ix, inner); ix++)
585
    {
586
      optimize_loop (inner, hooks);
587
 
588
      if (!inner->bad && inner_depth < inner->depth)
589
        inner_depth = inner->depth;
590
      /* The set of registers may be changed while optimizing the inner
591
         loop.  */
592
      IOR_HARD_REG_SET (loop->regs_set_in_loop, inner->regs_set_in_loop);
593
    }
594
 
595
  loop->depth = inner_depth + 1;
596
 
597
  if (hooks->opt (loop))
598
    return;
599
 
600
 bad_loop:
601
  if (dump_file)
602
    fprintf (dump_file, ";; loop %d is bad\n", loop->loop_no);
603
 
604
  loop->bad = true;
605
  hooks->fail (loop);
606
}
607
 
608
/* This function can be used from a port's machine_dependent_reorg to
609
   find and analyze loops that end in loop_end instructions.  It uses
610
   a set of function pointers in HOOKS to call back into the
611
   target-specific functions to perform the actual machine-specific
612
   transformations.
613
 
614
   Such transformations typically involve additional set-up
615
   instructions before the loop, to define loop bounds or set up a
616
   special loop counter register.
617
 
618
   DO_REORDER should be set to true if we should try to use the
619
   reorder_loops function to ensure the loop end occurs after the loop
620
   start.  This is for use by targets where the loop hardware requires
621
   this condition.
622
 
623
   HOOKS is used to pass in target specific hooks; see
624
   hw-doloop.h.  */
625
void
626
reorg_loops (bool do_reorder, struct hw_doloop_hooks *hooks)
627
{
628
  hwloop_info loops = NULL;
629
  hwloop_info loop;
630
  bitmap_obstack stack;
631
 
632
  df_live_add_problem ();
633
  df_live_set_all_dirty ();
634
  df_analyze ();
635
 
636
  bitmap_obstack_initialize (&stack);
637
 
638
  if (dump_file)
639
    fprintf (dump_file, ";; Find loops, first pass\n\n");
640
 
641
  loops = discover_loops (&stack, hooks);
642
 
643
  if (do_reorder)
644
    {
645
      reorder_loops (loops);
646
      free_loops (loops);
647
 
648
      if (dump_file)
649
        fprintf (dump_file, ";; Find loops, second pass\n\n");
650
 
651
      loops = discover_loops (&stack, hooks);
652
    }
653
 
654
  for (loop = loops; loop; loop = loop->next)
655
    scan_loop (loop);
656
 
657
  /* Now apply the optimizations.  */
658
  for (loop = loops; loop; loop = loop->next)
659
    optimize_loop (loop, hooks);
660
 
661
  if (dump_file)
662
    {
663
      fprintf (dump_file, ";; After hardware loops optimization:\n\n");
664
      dump_hwloops (loops);
665
    }
666
 
667
  free_loops (loops);
668
 
669
  if (dump_file)
670
    print_rtl (dump_file, get_insns ());
671
}
672
#endif

powered by: WebSVN 2.1.0

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