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

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-old/] [gcc-4.2.2/] [gcc/] [cfgloopmanip.c] - Blame information for rev 827

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

Line No. Rev Author Line
1 38 julius
/* Loop manipulation code for GNU compiler.
2
   Copyright (C) 2002, 2003, 2004, 2005, 2007 Free Software Foundation, Inc.
3
 
4
This file is part of GCC.
5
 
6
GCC is free software; you can redistribute it and/or modify it under
7
the terms of the GNU General Public License as published by the Free
8
Software Foundation; either version 3, or (at your option) any later
9
version.
10
 
11
GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12
WARRANTY; without even the implied warranty of MERCHANTABILITY or
13
FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
14
for more details.
15
 
16
You should have received a copy of the GNU General Public License
17
along with GCC; see the file COPYING3.  If not see
18
<http://www.gnu.org/licenses/>.  */
19
 
20
#include "config.h"
21
#include "system.h"
22
#include "coretypes.h"
23
#include "tm.h"
24
#include "rtl.h"
25
#include "hard-reg-set.h"
26
#include "obstack.h"
27
#include "basic-block.h"
28
#include "cfgloop.h"
29
#include "cfglayout.h"
30
#include "cfghooks.h"
31
#include "output.h"
32
 
33
static void duplicate_subloops (struct loops *, struct loop *, struct loop *);
34
static void copy_loops_to (struct loops *, struct loop **, int,
35
                           struct loop *);
36
static void loop_redirect_edge (edge, basic_block);
37
static bool loop_delete_branch_edge (edge, int);
38
static void remove_bbs (basic_block *, int);
39
static bool rpe_enum_p (basic_block, void *);
40
static int find_path (edge, basic_block **);
41
static bool alp_enum_p (basic_block, void *);
42
static void add_loop (struct loops *, struct loop *);
43
static void fix_loop_placements (struct loops *, struct loop *, bool *);
44
static bool fix_bb_placement (struct loops *, basic_block);
45
static void fix_bb_placements (struct loops *, basic_block, bool *);
46
static void place_new_loop (struct loops *, struct loop *);
47
static void scale_loop_frequencies (struct loop *, int, int);
48
static basic_block create_preheader (struct loop *, int);
49
static void unloop (struct loops *, struct loop *, bool *);
50
 
51
#define RDIV(X,Y) (((X) + (Y) / 2) / (Y))
52
 
53
/* Checks whether basic block BB is dominated by DATA.  */
54
static bool
55
rpe_enum_p (basic_block bb, void *data)
56
{
57
  return dominated_by_p (CDI_DOMINATORS, bb, data);
58
}
59
 
60
/* Remove basic blocks BBS from loop structure and dominance info,
61
   and delete them afterwards.  */
62
static void
63
remove_bbs (basic_block *bbs, int nbbs)
64
{
65
  int i;
66
 
67
  for (i = 0; i < nbbs; i++)
68
    {
69
      remove_bb_from_loops (bbs[i]);
70
      delete_basic_block (bbs[i]);
71
    }
72
}
73
 
74
/* Find path -- i.e. the basic blocks dominated by edge E and put them
75
   into array BBS, that will be allocated large enough to contain them.
76
   E->dest must have exactly one predecessor for this to work (it is
77
   easy to achieve and we do not put it here because we do not want to
78
   alter anything by this function).  The number of basic blocks in the
79
   path is returned.  */
80
static int
81
find_path (edge e, basic_block **bbs)
82
{
83
  gcc_assert (EDGE_COUNT (e->dest->preds) <= 1);
84
 
85
  /* Find bbs in the path.  */
86
  *bbs = XCNEWVEC (basic_block, n_basic_blocks);
87
  return dfs_enumerate_from (e->dest, 0, rpe_enum_p, *bbs,
88
                             n_basic_blocks, e->dest);
89
}
90
 
91
/* Fix placement of basic block BB inside loop hierarchy stored in LOOPS --
92
   Let L be a loop to that BB belongs.  Then every successor of BB must either
93
     1) belong to some superloop of loop L, or
94
     2) be a header of loop K such that K->outer is superloop of L
95
   Returns true if we had to move BB into other loop to enforce this condition,
96
   false if the placement of BB was already correct (provided that placements
97
   of its successors are correct).  */
98
static bool
99
fix_bb_placement (struct loops *loops, basic_block bb)
100
{
101
  edge e;
102
  edge_iterator ei;
103
  struct loop *loop = loops->tree_root, *act;
104
 
105
  FOR_EACH_EDGE (e, ei, bb->succs)
106
    {
107
      if (e->dest == EXIT_BLOCK_PTR)
108
        continue;
109
 
110
      act = e->dest->loop_father;
111
      if (act->header == e->dest)
112
        act = act->outer;
113
 
114
      if (flow_loop_nested_p (loop, act))
115
        loop = act;
116
    }
117
 
118
  if (loop == bb->loop_father)
119
    return false;
120
 
121
  remove_bb_from_loops (bb);
122
  add_bb_to_loop (bb, loop);
123
 
124
  return true;
125
}
126
 
127
/* Fix placements of basic blocks inside loop hierarchy stored in loops; i.e.
128
   enforce condition condition stated in description of fix_bb_placement. We
129
   start from basic block FROM that had some of its successors removed, so that
130
   his placement no longer has to be correct, and iteratively fix placement of
131
   its predecessors that may change if placement of FROM changed.  Also fix
132
   placement of subloops of FROM->loop_father, that might also be altered due
133
   to this change; the condition for them is similar, except that instead of
134
   successors we consider edges coming out of the loops.
135
 
136
   If the changes may invalidate the information about irreducible regions,
137
   IRRED_INVALIDATED is set to true.  */
138
 
139
static void
140
fix_bb_placements (struct loops *loops, basic_block from,
141
                   bool *irred_invalidated)
142
{
143
  sbitmap in_queue;
144
  basic_block *queue, *qtop, *qbeg, *qend;
145
  struct loop *base_loop;
146
  edge e;
147
 
148
  /* We pass through blocks back-reachable from FROM, testing whether some
149
     of their successors moved to outer loop.  It may be necessary to
150
     iterate several times, but it is finite, as we stop unless we move
151
     the basic block up the loop structure.  The whole story is a bit
152
     more complicated due to presence of subloops, those are moved using
153
     fix_loop_placement.  */
154
 
155
  base_loop = from->loop_father;
156
  if (base_loop == loops->tree_root)
157
    return;
158
 
159
  in_queue = sbitmap_alloc (last_basic_block);
160
  sbitmap_zero (in_queue);
161
  SET_BIT (in_queue, from->index);
162
  /* Prevent us from going out of the base_loop.  */
163
  SET_BIT (in_queue, base_loop->header->index);
164
 
165
  queue = XNEWVEC (basic_block, base_loop->num_nodes + 1);
166
  qtop = queue + base_loop->num_nodes + 1;
167
  qbeg = queue;
168
  qend = queue + 1;
169
  *qbeg = from;
170
 
171
  while (qbeg != qend)
172
    {
173
      edge_iterator ei;
174
      from = *qbeg;
175
      qbeg++;
176
      if (qbeg == qtop)
177
        qbeg = queue;
178
      RESET_BIT (in_queue, from->index);
179
 
180
      if (from->loop_father->header == from)
181
        {
182
          /* Subloop header, maybe move the loop upward.  */
183
          if (!fix_loop_placement (from->loop_father))
184
            continue;
185
        }
186
      else
187
        {
188
          /* Ordinary basic block.  */
189
          if (!fix_bb_placement (loops, from))
190
            continue;
191
        }
192
 
193
      FOR_EACH_EDGE (e, ei, from->succs)
194
        {
195
          if (e->flags & EDGE_IRREDUCIBLE_LOOP)
196
            *irred_invalidated = true;
197
        }
198
 
199
      /* Something has changed, insert predecessors into queue.  */
200
      FOR_EACH_EDGE (e, ei, from->preds)
201
        {
202
          basic_block pred = e->src;
203
          struct loop *nca;
204
 
205
          if (e->flags & EDGE_IRREDUCIBLE_LOOP)
206
            *irred_invalidated = true;
207
 
208
          if (TEST_BIT (in_queue, pred->index))
209
            continue;
210
 
211
          /* If it is subloop, then it either was not moved, or
212
             the path up the loop tree from base_loop do not contain
213
             it.  */
214
          nca = find_common_loop (pred->loop_father, base_loop);
215
          if (pred->loop_father != base_loop
216
              && (nca == base_loop
217
                  || nca != pred->loop_father))
218
            pred = pred->loop_father->header;
219
          else if (!flow_loop_nested_p (from->loop_father, pred->loop_father))
220
            {
221
              /* No point in processing it.  */
222
              continue;
223
            }
224
 
225
          if (TEST_BIT (in_queue, pred->index))
226
            continue;
227
 
228
          /* Schedule the basic block.  */
229
          *qend = pred;
230
          qend++;
231
          if (qend == qtop)
232
            qend = queue;
233
          SET_BIT (in_queue, pred->index);
234
        }
235
    }
236
  free (in_queue);
237
  free (queue);
238
}
239
 
240
/* Removes path beginning at edge E, i.e. remove basic blocks dominated by E
241
   and update loop structure stored in LOOPS and dominators.  Return true if
242
   we were able to remove the path, false otherwise (and nothing is affected
243
   then).  */
244
bool
245
remove_path (struct loops *loops, edge e)
246
{
247
  edge ae;
248
  basic_block *rem_bbs, *bord_bbs, *dom_bbs, from, bb;
249
  int i, nrem, n_bord_bbs, n_dom_bbs;
250
  sbitmap seen;
251
  bool deleted, irred_invalidated = false;
252
 
253
  if (!loop_delete_branch_edge (e, 0))
254
    return false;
255
 
256
  /* Keep track of whether we need to update information about irreducible
257
     regions.  This is the case if the removed area is a part of the
258
     irreducible region, or if the set of basic blocks that belong to a loop
259
     that is inside an irreducible region is changed, or if such a loop is
260
     removed.  */
261
  if (e->flags & EDGE_IRREDUCIBLE_LOOP)
262
    irred_invalidated = true;
263
 
264
  /* We need to check whether basic blocks are dominated by the edge
265
     e, but we only have basic block dominators.  This is easy to
266
     fix -- when e->dest has exactly one predecessor, this corresponds
267
     to blocks dominated by e->dest, if not, split the edge.  */
268
  if (!single_pred_p (e->dest))
269
    e = single_pred_edge (loop_split_edge_with (e, NULL_RTX));
270
 
271
  /* It may happen that by removing path we remove one or more loops
272
     we belong to.  In this case first unloop the loops, then proceed
273
     normally.   We may assume that e->dest is not a header of any loop,
274
     as it now has exactly one predecessor.  */
275
  while (e->src->loop_father->outer
276
         && dominated_by_p (CDI_DOMINATORS,
277
                            e->src->loop_father->latch, e->dest))
278
    unloop (loops, e->src->loop_father, &irred_invalidated);
279
 
280
  /* Identify the path.  */
281
  nrem = find_path (e, &rem_bbs);
282
 
283
  n_bord_bbs = 0;
284
  bord_bbs = XCNEWVEC (basic_block, n_basic_blocks);
285
  seen = sbitmap_alloc (last_basic_block);
286
  sbitmap_zero (seen);
287
 
288
  /* Find "border" hexes -- i.e. those with predecessor in removed path.  */
289
  for (i = 0; i < nrem; i++)
290
    SET_BIT (seen, rem_bbs[i]->index);
291
  for (i = 0; i < nrem; i++)
292
    {
293
      edge_iterator ei;
294
      bb = rem_bbs[i];
295
      FOR_EACH_EDGE (ae, ei, rem_bbs[i]->succs)
296
        if (ae->dest != EXIT_BLOCK_PTR && !TEST_BIT (seen, ae->dest->index))
297
          {
298
            SET_BIT (seen, ae->dest->index);
299
            bord_bbs[n_bord_bbs++] = ae->dest;
300
 
301
            if (ae->flags & EDGE_IRREDUCIBLE_LOOP)
302
              irred_invalidated = true;
303
          }
304
    }
305
 
306
  /* Remove the path.  */
307
  from = e->src;
308
  deleted = loop_delete_branch_edge (e, 1);
309
  gcc_assert (deleted);
310
  dom_bbs = XCNEWVEC (basic_block, n_basic_blocks);
311
 
312
  /* Cancel loops contained in the path.  */
313
  for (i = 0; i < nrem; i++)
314
    if (rem_bbs[i]->loop_father->header == rem_bbs[i])
315
      cancel_loop_tree (loops, rem_bbs[i]->loop_father);
316
 
317
  remove_bbs (rem_bbs, nrem);
318
  free (rem_bbs);
319
 
320
  /* Find blocks whose dominators may be affected.  */
321
  n_dom_bbs = 0;
322
  sbitmap_zero (seen);
323
  for (i = 0; i < n_bord_bbs; i++)
324
    {
325
      basic_block ldom;
326
 
327
      bb = get_immediate_dominator (CDI_DOMINATORS, bord_bbs[i]);
328
      if (TEST_BIT (seen, bb->index))
329
        continue;
330
      SET_BIT (seen, bb->index);
331
 
332
      for (ldom = first_dom_son (CDI_DOMINATORS, bb);
333
           ldom;
334
           ldom = next_dom_son (CDI_DOMINATORS, ldom))
335
        if (!dominated_by_p (CDI_DOMINATORS, from, ldom))
336
          dom_bbs[n_dom_bbs++] = ldom;
337
    }
338
 
339
  free (seen);
340
 
341
  /* Recount dominators.  */
342
  iterate_fix_dominators (CDI_DOMINATORS, dom_bbs, n_dom_bbs);
343
  free (dom_bbs);
344
  free (bord_bbs);
345
 
346
  /* Fix placements of basic blocks inside loops and the placement of
347
     loops in the loop tree.  */
348
  fix_bb_placements (loops, from, &irred_invalidated);
349
  fix_loop_placements (loops, from->loop_father, &irred_invalidated);
350
 
351
  if (irred_invalidated
352
      && (loops->state & LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS) != 0)
353
    mark_irreducible_loops (loops);
354
 
355
  return true;
356
}
357
 
358
/* Predicate for enumeration in add_loop.  */
359
static bool
360
alp_enum_p (basic_block bb, void *alp_header)
361
{
362
  return bb != (basic_block) alp_header;
363
}
364
 
365
/* Given LOOP structure with filled header and latch, find the body of the
366
   corresponding loop and add it to LOOPS tree.  */
367
static void
368
add_loop (struct loops *loops, struct loop *loop)
369
{
370
  basic_block *bbs;
371
  int i, n;
372
 
373
  /* Add it to loop structure.  */
374
  place_new_loop (loops, loop);
375
  loop->level = 1;
376
 
377
  /* Find its nodes.  */
378
  bbs = XCNEWVEC (basic_block, n_basic_blocks);
379
  n = dfs_enumerate_from (loop->latch, 1, alp_enum_p,
380
                          bbs, n_basic_blocks, loop->header);
381
 
382
  for (i = 0; i < n; i++)
383
    add_bb_to_loop (bbs[i], loop);
384
  add_bb_to_loop (loop->header, loop);
385
 
386
  free (bbs);
387
}
388
 
389
/* Multiply all frequencies in LOOP by NUM/DEN.  */
390
static void
391
scale_loop_frequencies (struct loop *loop, int num, int den)
392
{
393
  basic_block *bbs;
394
 
395
  bbs = get_loop_body (loop);
396
  scale_bbs_frequencies_int (bbs, loop->num_nodes, num, den);
397
  free (bbs);
398
}
399
 
400
/* Make area between HEADER_EDGE and LATCH_EDGE a loop by connecting
401
   latch to header and update loop tree stored in LOOPS and dominators
402
   accordingly. Everything between them plus LATCH_EDGE destination must
403
   be dominated by HEADER_EDGE destination, and back-reachable from
404
   LATCH_EDGE source.  HEADER_EDGE is redirected to basic block SWITCH_BB,
405
   FALSE_EDGE of SWITCH_BB to original destination of HEADER_EDGE and
406
   TRUE_EDGE of SWITCH_BB to original destination of LATCH_EDGE.
407
   Returns newly created loop.  */
408
 
409
struct loop *
410
loopify (struct loops *loops, edge latch_edge, edge header_edge,
411
         basic_block switch_bb, edge true_edge, edge false_edge,
412
         bool redirect_all_edges)
413
{
414
  basic_block succ_bb = latch_edge->dest;
415
  basic_block pred_bb = header_edge->src;
416
  basic_block *dom_bbs, *body;
417
  unsigned n_dom_bbs, i;
418
  sbitmap seen;
419
  struct loop *loop = XCNEW (struct loop);
420
  struct loop *outer = succ_bb->loop_father->outer;
421
  int freq, prob, tot_prob;
422
  gcov_type cnt;
423
  edge e;
424
  edge_iterator ei;
425
 
426
  loop->header = header_edge->dest;
427
  loop->latch = latch_edge->src;
428
 
429
  freq = EDGE_FREQUENCY (header_edge);
430
  cnt = header_edge->count;
431
  prob = EDGE_SUCC (switch_bb, 0)->probability;
432
  tot_prob = prob + EDGE_SUCC (switch_bb, 1)->probability;
433
  if (tot_prob == 0)
434
    tot_prob = 1;
435
 
436
  /* Redirect edges.  */
437
  loop_redirect_edge (latch_edge, loop->header);
438
  loop_redirect_edge (true_edge, succ_bb);
439
 
440
  /* During loop versioning, one of the switch_bb edge is already properly
441
     set. Do not redirect it again unless redirect_all_edges is true.  */
442
  if (redirect_all_edges)
443
    {
444
      loop_redirect_edge (header_edge, switch_bb);
445
      loop_redirect_edge (false_edge, loop->header);
446
 
447
      /* Update dominators.  */
448
      set_immediate_dominator (CDI_DOMINATORS, switch_bb, pred_bb);
449
      set_immediate_dominator (CDI_DOMINATORS, loop->header, switch_bb);
450
    }
451
 
452
  set_immediate_dominator (CDI_DOMINATORS, succ_bb, switch_bb);
453
 
454
  /* Compute new loop.  */
455
  add_loop (loops, loop);
456
  flow_loop_tree_node_add (outer, loop);
457
 
458
  /* Add switch_bb to appropriate loop.  */
459
  add_bb_to_loop (switch_bb, outer);
460
 
461
  /* Fix frequencies.  */
462
  switch_bb->frequency = freq;
463
  switch_bb->count = cnt;
464
  FOR_EACH_EDGE (e, ei, switch_bb->succs)
465
    e->count = (switch_bb->count * e->probability) / REG_BR_PROB_BASE;
466
  scale_loop_frequencies (loop, prob, tot_prob);
467
  scale_loop_frequencies (succ_bb->loop_father, tot_prob - prob, tot_prob);
468
 
469
  /* Update dominators of blocks outside of LOOP.  */
470
  dom_bbs = XCNEWVEC (basic_block, n_basic_blocks);
471
  n_dom_bbs = 0;
472
  seen = sbitmap_alloc (last_basic_block);
473
  sbitmap_zero (seen);
474
  body = get_loop_body (loop);
475
 
476
  for (i = 0; i < loop->num_nodes; i++)
477
    SET_BIT (seen, body[i]->index);
478
 
479
  for (i = 0; i < loop->num_nodes; i++)
480
    {
481
      basic_block ldom;
482
 
483
      for (ldom = first_dom_son (CDI_DOMINATORS, body[i]);
484
           ldom;
485
           ldom = next_dom_son (CDI_DOMINATORS, ldom))
486
        if (!TEST_BIT (seen, ldom->index))
487
          {
488
            SET_BIT (seen, ldom->index);
489
            dom_bbs[n_dom_bbs++] = ldom;
490
          }
491
    }
492
 
493
  iterate_fix_dominators (CDI_DOMINATORS, dom_bbs, n_dom_bbs);
494
 
495
  free (body);
496
  free (seen);
497
  free (dom_bbs);
498
 
499
  return loop;
500
}
501
 
502
/* Remove the latch edge of a LOOP and update LOOPS tree to indicate that
503
   the LOOP was removed.  After this function, original loop latch will
504
   have no successor, which caller is expected to fix somehow.
505
 
506
   If this may cause the information about irreducible regions to become
507
   invalid, IRRED_INVALIDATED is set to true.  */
508
 
509
static void
510
unloop (struct loops *loops, struct loop *loop, bool *irred_invalidated)
511
{
512
  basic_block *body;
513
  struct loop *ploop;
514
  unsigned i, n;
515
  basic_block latch = loop->latch;
516
  bool dummy = false;
517
 
518
  if (loop_preheader_edge (loop)->flags & EDGE_IRREDUCIBLE_LOOP)
519
    *irred_invalidated = true;
520
 
521
  /* This is relatively straightforward.  The dominators are unchanged, as
522
     loop header dominates loop latch, so the only thing we have to care of
523
     is the placement of loops and basic blocks inside the loop tree.  We
524
     move them all to the loop->outer, and then let fix_bb_placements do
525
     its work.  */
526
 
527
  body = get_loop_body (loop);
528
  n = loop->num_nodes;
529
  for (i = 0; i < n; i++)
530
    if (body[i]->loop_father == loop)
531
      {
532
        remove_bb_from_loops (body[i]);
533
        add_bb_to_loop (body[i], loop->outer);
534
      }
535
  free(body);
536
 
537
  while (loop->inner)
538
    {
539
      ploop = loop->inner;
540
      flow_loop_tree_node_remove (ploop);
541
      flow_loop_tree_node_add (loop->outer, ploop);
542
    }
543
 
544
  /* Remove the loop and free its data.  */
545
  flow_loop_tree_node_remove (loop);
546
  loops->parray[loop->num] = NULL;
547
  flow_loop_free (loop);
548
 
549
  remove_edge (single_succ_edge (latch));
550
 
551
  /* We do not pass IRRED_INVALIDATED to fix_bb_placements here, as even if
552
     there is an irreducible region inside the cancelled loop, the flags will
553
     be still correct.  */
554
  fix_bb_placements (loops, latch, &dummy);
555
}
556
 
557
/* Fix placement of LOOP inside loop tree, i.e. find the innermost superloop
558
   FATHER of LOOP such that all of the edges coming out of LOOP belong to
559
   FATHER, and set it as outer loop of LOOP.  Return true if placement of
560
   LOOP changed.  */
561
 
562
int
563
fix_loop_placement (struct loop *loop)
564
{
565
  basic_block *body;
566
  unsigned i;
567
  edge e;
568
  edge_iterator ei;
569
  struct loop *father = loop->pred[0], *act;
570
 
571
  body = get_loop_body (loop);
572
  for (i = 0; i < loop->num_nodes; i++)
573
    FOR_EACH_EDGE (e, ei, body[i]->succs)
574
      if (!flow_bb_inside_loop_p (loop, e->dest))
575
        {
576
          act = find_common_loop (loop, e->dest->loop_father);
577
          if (flow_loop_nested_p (father, act))
578
            father = act;
579
        }
580
  free (body);
581
 
582
  if (father != loop->outer)
583
    {
584
      for (act = loop->outer; act != father; act = act->outer)
585
        act->num_nodes -= loop->num_nodes;
586
      flow_loop_tree_node_remove (loop);
587
      flow_loop_tree_node_add (father, loop);
588
      return 1;
589
    }
590
  return 0;
591
}
592
 
593
/* Fix placement of superloops of LOOP inside loop tree, i.e. ensure that
594
   condition stated in description of fix_loop_placement holds for them.
595
   It is used in case when we removed some edges coming out of LOOP, which
596
   may cause the right placement of LOOP inside loop tree to change.
597
 
598
   IRRED_INVALIDATED is set to true if a change in the loop structures might
599
   invalidate the information about irreducible regions.  */
600
 
601
static void
602
fix_loop_placements (struct loops *loops, struct loop *loop,
603
                     bool *irred_invalidated)
604
{
605
  struct loop *outer;
606
 
607
  while (loop->outer)
608
    {
609
      outer = loop->outer;
610
      if (!fix_loop_placement (loop))
611
        break;
612
 
613
      /* Changing the placement of a loop in the loop tree may alter the
614
         validity of condition 2) of the description of fix_bb_placement
615
         for its preheader, because the successor is the header and belongs
616
         to the loop.  So call fix_bb_placements to fix up the placement
617
         of the preheader and (possibly) of its predecessors.  */
618
      fix_bb_placements (loops, loop_preheader_edge (loop)->src,
619
                         irred_invalidated);
620
      loop = outer;
621
    }
622
}
623
 
624
/* Creates place for a new LOOP in LOOPS structure.  */
625
static void
626
place_new_loop (struct loops *loops, struct loop *loop)
627
{
628
  loops->parray =
629
    xrealloc (loops->parray, (loops->num + 1) * sizeof (struct loop *));
630
  loops->parray[loops->num] = loop;
631
 
632
  loop->num = loops->num++;
633
}
634
 
635
/* Copies copy of LOOP as subloop of TARGET loop, placing newly
636
   created loop into LOOPS structure.  */
637
struct loop *
638
duplicate_loop (struct loops *loops, struct loop *loop, struct loop *target)
639
{
640
  struct loop *cloop;
641
  cloop = XCNEW (struct loop);
642
  place_new_loop (loops, cloop);
643
 
644
  /* Initialize copied loop.  */
645
  cloop->level = loop->level;
646
 
647
  /* Set it as copy of loop.  */
648
  loop->copy = cloop;
649
 
650
  /* Add it to target.  */
651
  flow_loop_tree_node_add (target, cloop);
652
 
653
  return cloop;
654
}
655
 
656
/* Copies structure of subloops of LOOP into TARGET loop, placing
657
   newly created loops into loop tree stored in LOOPS.  */
658
static void
659
duplicate_subloops (struct loops *loops, struct loop *loop, struct loop *target)
660
{
661
  struct loop *aloop, *cloop;
662
 
663
  for (aloop = loop->inner; aloop; aloop = aloop->next)
664
    {
665
      cloop = duplicate_loop (loops, aloop, target);
666
      duplicate_subloops (loops, aloop, cloop);
667
    }
668
}
669
 
670
/* Copies structure of subloops of N loops, stored in array COPIED_LOOPS,
671
   into TARGET loop, placing newly created loops into loop tree LOOPS.  */
672
static void
673
copy_loops_to (struct loops *loops, struct loop **copied_loops, int n, struct loop *target)
674
{
675
  struct loop *aloop;
676
  int i;
677
 
678
  for (i = 0; i < n; i++)
679
    {
680
      aloop = duplicate_loop (loops, copied_loops[i], target);
681
      duplicate_subloops (loops, copied_loops[i], aloop);
682
    }
683
}
684
 
685
/* Redirects edge E to basic block DEST.  */
686
static void
687
loop_redirect_edge (edge e, basic_block dest)
688
{
689
  if (e->dest == dest)
690
    return;
691
 
692
  redirect_edge_and_branch_force (e, dest);
693
}
694
 
695
/* Deletes edge E from a branch if possible.  Unless REALLY_DELETE is set,
696
   just test whether it is possible to remove the edge.  */
697
static bool
698
loop_delete_branch_edge (edge e, int really_delete)
699
{
700
  basic_block src = e->src;
701
  basic_block newdest;
702
  int irr;
703
  edge snd;
704
 
705
  gcc_assert (EDGE_COUNT (src->succs) > 1);
706
 
707
  /* Cannot handle more than two exit edges.  */
708
  if (EDGE_COUNT (src->succs) > 2)
709
    return false;
710
  /* And it must be just a simple branch.  */
711
  if (!any_condjump_p (BB_END (src)))
712
    return false;
713
 
714
  snd = e == EDGE_SUCC (src, 0) ? EDGE_SUCC (src, 1) : EDGE_SUCC (src, 0);
715
  newdest = snd->dest;
716
  if (newdest == EXIT_BLOCK_PTR)
717
    return false;
718
 
719
  /* Hopefully the above conditions should suffice.  */
720
  if (!really_delete)
721
    return true;
722
 
723
  /* Redirecting behaves wrongly wrto this flag.  */
724
  irr = snd->flags & EDGE_IRREDUCIBLE_LOOP;
725
 
726
  if (!redirect_edge_and_branch (e, newdest))
727
    return false;
728
  single_succ_edge (src)->flags &= ~EDGE_IRREDUCIBLE_LOOP;
729
  single_succ_edge (src)->flags |= irr;
730
 
731
  return true;
732
}
733
 
734
/* Check whether LOOP's body can be duplicated.  */
735
bool
736
can_duplicate_loop_p (struct loop *loop)
737
{
738
  int ret;
739
  basic_block *bbs = get_loop_body (loop);
740
 
741
  ret = can_copy_bbs_p (bbs, loop->num_nodes);
742
  free (bbs);
743
 
744
  return ret;
745
}
746
 
747
/* The NBBS blocks in BBS will get duplicated and the copies will be placed
748
   to LOOP.  Update the single_exit information in superloops of LOOP.  */
749
 
750
static void
751
update_single_exits_after_duplication (basic_block *bbs, unsigned nbbs,
752
                                       struct loop *loop)
753
{
754
  unsigned i;
755
 
756
  for (i = 0; i < nbbs; i++)
757
    bbs[i]->flags |= BB_DUPLICATED;
758
 
759
  for (; loop->outer; loop = loop->outer)
760
    {
761
      if (!loop->single_exit)
762
        continue;
763
 
764
      if (loop->single_exit->src->flags & BB_DUPLICATED)
765
        loop->single_exit = NULL;
766
    }
767
 
768
  for (i = 0; i < nbbs; i++)
769
    bbs[i]->flags &= ~BB_DUPLICATED;
770
}
771
 
772
/* Duplicates body of LOOP to given edge E NDUPL times.  Takes care of updating
773
   LOOPS structure and dominators.  E's destination must be LOOP header for
774
   this to work, i.e. it must be entry or latch edge of this loop; these are
775
   unique, as the loops must have preheaders for this function to work
776
   correctly (in case E is latch, the function unrolls the loop, if E is entry
777
   edge, it peels the loop).  Store edges created by copying ORIG edge from
778
   copies corresponding to set bits in WONT_EXIT bitmap (bit 0 corresponds to
779
   original LOOP body, the other copies are numbered in order given by control
780
   flow through them) into TO_REMOVE array.  Returns false if duplication is
781
   impossible.  */
782
bool
783
duplicate_loop_to_header_edge (struct loop *loop, edge e, struct loops *loops,
784
                               unsigned int ndupl, sbitmap wont_exit,
785
                               edge orig, edge *to_remove,
786
                               unsigned int *n_to_remove, int flags)
787
{
788
  struct loop *target, *aloop;
789
  struct loop **orig_loops;
790
  unsigned n_orig_loops;
791
  basic_block header = loop->header, latch = loop->latch;
792
  basic_block *new_bbs, *bbs, *first_active;
793
  basic_block new_bb, bb, first_active_latch = NULL;
794
  edge ae, latch_edge;
795
  edge spec_edges[2], new_spec_edges[2];
796
#define SE_LATCH 0
797
#define SE_ORIG 1
798
  unsigned i, j, n;
799
  int is_latch = (latch == e->src);
800
  int scale_act = 0, *scale_step = NULL, scale_main = 0;
801
  int p, freq_in, freq_le, freq_out_orig;
802
  int prob_pass_thru, prob_pass_wont_exit, prob_pass_main;
803
  int add_irreducible_flag;
804
  basic_block place_after;
805
 
806
  gcc_assert (e->dest == loop->header);
807
  gcc_assert (ndupl > 0);
808
 
809
  if (orig)
810
    {
811
      /* Orig must be edge out of the loop.  */
812
      gcc_assert (flow_bb_inside_loop_p (loop, orig->src));
813
      gcc_assert (!flow_bb_inside_loop_p (loop, orig->dest));
814
    }
815
 
816
  n = loop->num_nodes;
817
  bbs = get_loop_body_in_dom_order (loop);
818
  gcc_assert (bbs[0] == loop->header);
819
  gcc_assert (bbs[n  - 1] == loop->latch);
820
 
821
  /* Check whether duplication is possible.  */
822
  if (!can_copy_bbs_p (bbs, loop->num_nodes))
823
    {
824
      free (bbs);
825
      return false;
826
    }
827
  new_bbs = XNEWVEC (basic_block, loop->num_nodes);
828
 
829
  /* In case we are doing loop peeling and the loop is in the middle of
830
     irreducible region, the peeled copies will be inside it too.  */
831
  add_irreducible_flag = e->flags & EDGE_IRREDUCIBLE_LOOP;
832
  gcc_assert (!is_latch || !add_irreducible_flag);
833
 
834
  /* Find edge from latch.  */
835
  latch_edge = loop_latch_edge (loop);
836
 
837
  if (flags & DLTHE_FLAG_UPDATE_FREQ)
838
    {
839
      /* Calculate coefficients by that we have to scale frequencies
840
         of duplicated loop bodies.  */
841
      freq_in = header->frequency;
842
      freq_le = EDGE_FREQUENCY (latch_edge);
843
      if (freq_in == 0)
844
        freq_in = 1;
845
      if (freq_in < freq_le)
846
        freq_in = freq_le;
847
      freq_out_orig = orig ? EDGE_FREQUENCY (orig) : freq_in - freq_le;
848
      if (freq_out_orig > freq_in - freq_le)
849
        freq_out_orig = freq_in - freq_le;
850
      prob_pass_thru = RDIV (REG_BR_PROB_BASE * freq_le, freq_in);
851
      prob_pass_wont_exit =
852
              RDIV (REG_BR_PROB_BASE * (freq_le + freq_out_orig), freq_in);
853
 
854
      scale_step = XNEWVEC (int, ndupl);
855
 
856
        for (i = 1; i <= ndupl; i++)
857
          scale_step[i - 1] = TEST_BIT (wont_exit, i)
858
                                ? prob_pass_wont_exit
859
                                : prob_pass_thru;
860
 
861
      /* Complete peeling is special as the probability of exit in last
862
         copy becomes 1.  */
863
      if (flags & DLTHE_FLAG_COMPLETTE_PEEL)
864
        {
865
          int wanted_freq = EDGE_FREQUENCY (e);
866
 
867
          if (wanted_freq > freq_in)
868
            wanted_freq = freq_in;
869
 
870
          gcc_assert (!is_latch);
871
          /* First copy has frequency of incoming edge.  Each subsequent
872
             frequency should be reduced by prob_pass_wont_exit.  Caller
873
             should've managed the flags so all except for original loop
874
             has won't exist set.  */
875
          scale_act = RDIV (wanted_freq * REG_BR_PROB_BASE, freq_in);
876
          /* Now simulate the duplication adjustments and compute header
877
             frequency of the last copy.  */
878
          for (i = 0; i < ndupl; i++)
879
            wanted_freq = RDIV (wanted_freq * scale_step[i], REG_BR_PROB_BASE);
880
          scale_main = RDIV (wanted_freq * REG_BR_PROB_BASE, freq_in);
881
        }
882
      else if (is_latch)
883
        {
884
          prob_pass_main = TEST_BIT (wont_exit, 0)
885
                                ? prob_pass_wont_exit
886
                                : prob_pass_thru;
887
          p = prob_pass_main;
888
          scale_main = REG_BR_PROB_BASE;
889
          for (i = 0; i < ndupl; i++)
890
            {
891
              scale_main += p;
892
              p = RDIV (p * scale_step[i], REG_BR_PROB_BASE);
893
            }
894
          scale_main = RDIV (REG_BR_PROB_BASE * REG_BR_PROB_BASE, scale_main);
895
          scale_act = RDIV (scale_main * prob_pass_main, REG_BR_PROB_BASE);
896
        }
897
      else
898
        {
899
          scale_main = REG_BR_PROB_BASE;
900
          for (i = 0; i < ndupl; i++)
901
            scale_main = RDIV (scale_main * scale_step[i], REG_BR_PROB_BASE);
902
          scale_act = REG_BR_PROB_BASE - prob_pass_thru;
903
        }
904
      for (i = 0; i < ndupl; i++)
905
        gcc_assert (scale_step[i] >= 0 && scale_step[i] <= REG_BR_PROB_BASE);
906
      gcc_assert (scale_main >= 0 && scale_main <= REG_BR_PROB_BASE
907
                  && scale_act >= 0  && scale_act <= REG_BR_PROB_BASE);
908
    }
909
 
910
  /* Loop the new bbs will belong to.  */
911
  target = e->src->loop_father;
912
 
913
  /* Original loops.  */
914
  n_orig_loops = 0;
915
  for (aloop = loop->inner; aloop; aloop = aloop->next)
916
    n_orig_loops++;
917
  orig_loops = XCNEWVEC (struct loop *, n_orig_loops);
918
  for (aloop = loop->inner, i = 0; aloop; aloop = aloop->next, i++)
919
    orig_loops[i] = aloop;
920
 
921
  loop->copy = target;
922
 
923
  first_active = XNEWVEC (basic_block, n);
924
  if (is_latch)
925
    {
926
      memcpy (first_active, bbs, n * sizeof (basic_block));
927
      first_active_latch = latch;
928
    }
929
 
930
  /* Update the information about single exits.  */
931
  if (loops->state & LOOPS_HAVE_MARKED_SINGLE_EXITS)
932
    update_single_exits_after_duplication (bbs, n, target);
933
 
934
  /* Record exit edge in original loop body.  */
935
  if (orig && TEST_BIT (wont_exit, 0))
936
    to_remove[(*n_to_remove)++] = orig;
937
 
938
  spec_edges[SE_ORIG] = orig;
939
  spec_edges[SE_LATCH] = latch_edge;
940
 
941
  place_after = e->src;
942
  for (j = 0; j < ndupl; j++)
943
    {
944
      /* Copy loops.  */
945
      copy_loops_to (loops, orig_loops, n_orig_loops, target);
946
 
947
      /* Copy bbs.  */
948
      copy_bbs (bbs, n, new_bbs, spec_edges, 2, new_spec_edges, loop,
949
                place_after);
950
      place_after = new_spec_edges[SE_LATCH]->src;
951
 
952
      if (flags & DLTHE_RECORD_COPY_NUMBER)
953
        for (i = 0; i < n; i++)
954
          {
955
            gcc_assert (!new_bbs[i]->aux);
956
            new_bbs[i]->aux = (void *)(size_t)(j + 1);
957
          }
958
 
959
      /* Note whether the blocks and edges belong to an irreducible loop.  */
960
      if (add_irreducible_flag)
961
        {
962
          for (i = 0; i < n; i++)
963
            new_bbs[i]->flags |= BB_DUPLICATED;
964
          for (i = 0; i < n; i++)
965
            {
966
              edge_iterator ei;
967
              new_bb = new_bbs[i];
968
              if (new_bb->loop_father == target)
969
                new_bb->flags |= BB_IRREDUCIBLE_LOOP;
970
 
971
              FOR_EACH_EDGE (ae, ei, new_bb->succs)
972
                if ((ae->dest->flags & BB_DUPLICATED)
973
                    && (ae->src->loop_father == target
974
                        || ae->dest->loop_father == target))
975
                  ae->flags |= EDGE_IRREDUCIBLE_LOOP;
976
            }
977
          for (i = 0; i < n; i++)
978
            new_bbs[i]->flags &= ~BB_DUPLICATED;
979
        }
980
 
981
      /* Redirect the special edges.  */
982
      if (is_latch)
983
        {
984
          redirect_edge_and_branch_force (latch_edge, new_bbs[0]);
985
          redirect_edge_and_branch_force (new_spec_edges[SE_LATCH],
986
                                          loop->header);
987
          set_immediate_dominator (CDI_DOMINATORS, new_bbs[0], latch);
988
          latch = loop->latch = new_bbs[n - 1];
989
          e = latch_edge = new_spec_edges[SE_LATCH];
990
        }
991
      else
992
        {
993
          redirect_edge_and_branch_force (new_spec_edges[SE_LATCH],
994
                                          loop->header);
995
          redirect_edge_and_branch_force (e, new_bbs[0]);
996
          set_immediate_dominator (CDI_DOMINATORS, new_bbs[0], e->src);
997
          e = new_spec_edges[SE_LATCH];
998
        }
999
 
1000
      /* Record exit edge in this copy.  */
1001
      if (orig && TEST_BIT (wont_exit, j + 1))
1002
        to_remove[(*n_to_remove)++] = new_spec_edges[SE_ORIG];
1003
 
1004
      /* Record the first copy in the control flow order if it is not
1005
         the original loop (i.e. in case of peeling).  */
1006
      if (!first_active_latch)
1007
        {
1008
          memcpy (first_active, new_bbs, n * sizeof (basic_block));
1009
          first_active_latch = new_bbs[n - 1];
1010
        }
1011
 
1012
      /* Set counts and frequencies.  */
1013
      if (flags & DLTHE_FLAG_UPDATE_FREQ)
1014
        {
1015
          scale_bbs_frequencies_int (new_bbs, n, scale_act, REG_BR_PROB_BASE);
1016
          scale_act = RDIV (scale_act * scale_step[j], REG_BR_PROB_BASE);
1017
        }
1018
    }
1019
  free (new_bbs);
1020
  free (orig_loops);
1021
 
1022
  /* Update the original loop.  */
1023
  if (!is_latch)
1024
    set_immediate_dominator (CDI_DOMINATORS, e->dest, e->src);
1025
  if (flags & DLTHE_FLAG_UPDATE_FREQ)
1026
    {
1027
      scale_bbs_frequencies_int (bbs, n, scale_main, REG_BR_PROB_BASE);
1028
      free (scale_step);
1029
    }
1030
 
1031
  /* Update dominators of outer blocks if affected.  */
1032
  for (i = 0; i < n; i++)
1033
    {
1034
      basic_block dominated, dom_bb, *dom_bbs;
1035
      int n_dom_bbs,j;
1036
 
1037
      bb = bbs[i];
1038
      bb->aux = 0;
1039
 
1040
      n_dom_bbs = get_dominated_by (CDI_DOMINATORS, bb, &dom_bbs);
1041
      for (j = 0; j < n_dom_bbs; j++)
1042
        {
1043
          dominated = dom_bbs[j];
1044
          if (flow_bb_inside_loop_p (loop, dominated))
1045
            continue;
1046
          dom_bb = nearest_common_dominator (
1047
                        CDI_DOMINATORS, first_active[i], first_active_latch);
1048
          set_immediate_dominator (CDI_DOMINATORS, dominated, dom_bb);
1049
        }
1050
      free (dom_bbs);
1051
    }
1052
  free (first_active);
1053
 
1054
  free (bbs);
1055
 
1056
  return true;
1057
}
1058
 
1059
/* A callback for make_forwarder block, to redirect all edges except for
1060
   MFB_KJ_EDGE to the entry part.  E is the edge for that we should decide
1061
   whether to redirect it.  */
1062
 
1063
static edge mfb_kj_edge;
1064
static bool
1065
mfb_keep_just (edge e)
1066
{
1067
  return e != mfb_kj_edge;
1068
}
1069
 
1070
/* A callback for make_forwarder block, to update data structures for a basic
1071
   block JUMP created by redirecting an edge (only the latch edge is being
1072
   redirected).  */
1073
 
1074
static void
1075
mfb_update_loops (basic_block jump)
1076
{
1077
  struct loop *loop = single_succ (jump)->loop_father;
1078
 
1079
  if (dom_computed[CDI_DOMINATORS])
1080
    set_immediate_dominator (CDI_DOMINATORS, jump, single_pred (jump));
1081
  add_bb_to_loop (jump, loop);
1082
  loop->latch = jump;
1083
}
1084
 
1085
/* Creates a pre-header for a LOOP.  Returns newly created block.  Unless
1086
   CP_SIMPLE_PREHEADERS is set in FLAGS, we only force LOOP to have single
1087
   entry; otherwise we also force preheader block to have only one successor.
1088
   The function also updates dominators.  */
1089
 
1090
static basic_block
1091
create_preheader (struct loop *loop, int flags)
1092
{
1093
  edge e, fallthru;
1094
  basic_block dummy;
1095
  struct loop *cloop, *ploop;
1096
  int nentry = 0;
1097
  bool irred = false;
1098
  bool latch_edge_was_fallthru;
1099
  edge one_succ_pred = 0;
1100
  edge_iterator ei;
1101
 
1102
  cloop = loop->outer;
1103
 
1104
  FOR_EACH_EDGE (e, ei, loop->header->preds)
1105
    {
1106
      if (e->src == loop->latch)
1107
        continue;
1108
      irred |= (e->flags & EDGE_IRREDUCIBLE_LOOP) != 0;
1109
      nentry++;
1110
      if (single_succ_p (e->src))
1111
        one_succ_pred = e;
1112
    }
1113
  gcc_assert (nentry);
1114
  if (nentry == 1)
1115
    {
1116
      /* Get an edge that is different from the one from loop->latch
1117
         to loop->header.  */
1118
      e = EDGE_PRED (loop->header,
1119
                     EDGE_PRED (loop->header, 0)->src == loop->latch);
1120
 
1121
      if (!(flags & CP_SIMPLE_PREHEADERS) || single_succ_p (e->src))
1122
        return NULL;
1123
    }
1124
 
1125
  mfb_kj_edge = loop_latch_edge (loop);
1126
  latch_edge_was_fallthru = (mfb_kj_edge->flags & EDGE_FALLTHRU) != 0;
1127
  fallthru = make_forwarder_block (loop->header, mfb_keep_just,
1128
                                   mfb_update_loops);
1129
  dummy = fallthru->src;
1130
  loop->header = fallthru->dest;
1131
 
1132
  /* The header could be a latch of some superloop(s); due to design of
1133
     split_block, it would now move to fallthru->dest.  */
1134
  for (ploop = loop; ploop; ploop = ploop->outer)
1135
    if (ploop->latch == dummy)
1136
      ploop->latch = fallthru->dest;
1137
 
1138
  /* Try to be clever in placing the newly created preheader.  The idea is to
1139
     avoid breaking any "fallthruness" relationship between blocks.
1140
 
1141
     The preheader was created just before the header and all incoming edges
1142
     to the header were redirected to the preheader, except the latch edge.
1143
     So the only problematic case is when this latch edge was a fallthru
1144
     edge: it is not anymore after the preheader creation so we have broken
1145
     the fallthruness.  We're therefore going to look for a better place.  */
1146
  if (latch_edge_was_fallthru)
1147
    {
1148
      if (one_succ_pred)
1149
        e = one_succ_pred;
1150
      else
1151
        e = EDGE_PRED (dummy, 0);
1152
 
1153
      move_block_after (dummy, e->src);
1154
    }
1155
 
1156
  loop->header->loop_father = loop;
1157
  add_bb_to_loop (dummy, cloop);
1158
 
1159
  if (irred)
1160
    {
1161
      dummy->flags |= BB_IRREDUCIBLE_LOOP;
1162
      single_succ_edge (dummy)->flags |= EDGE_IRREDUCIBLE_LOOP;
1163
    }
1164
 
1165
  if (dump_file)
1166
    fprintf (dump_file, "Created preheader block for loop %i\n",
1167
             loop->num);
1168
 
1169
  return dummy;
1170
}
1171
 
1172
/* Create preheaders for each loop from loop tree stored in LOOPS; for meaning
1173
   of FLAGS see create_preheader.  */
1174
void
1175
create_preheaders (struct loops *loops, int flags)
1176
{
1177
  unsigned i;
1178
  for (i = 1; i < loops->num; i++)
1179
    create_preheader (loops->parray[i], flags);
1180
  loops->state |= LOOPS_HAVE_PREHEADERS;
1181
}
1182
 
1183
/* Forces all loop latches of loops from loop tree LOOPS to have only single
1184
   successor.  */
1185
void
1186
force_single_succ_latches (struct loops *loops)
1187
{
1188
  unsigned i;
1189
  struct loop *loop;
1190
  edge e;
1191
 
1192
  for (i = 1; i < loops->num; i++)
1193
    {
1194
      loop = loops->parray[i];
1195
      if (loop->latch != loop->header && single_succ_p (loop->latch))
1196
        continue;
1197
 
1198
      e = find_edge (loop->latch, loop->header);
1199
 
1200
      loop_split_edge_with (e, NULL_RTX);
1201
    }
1202
  loops->state |= LOOPS_HAVE_SIMPLE_LATCHES;
1203
}
1204
 
1205
/* A quite stupid function to put INSNS on edge E. They are supposed to form
1206
   just one basic block.  Jumps in INSNS are not handled, so cfg do not have to
1207
   be ok after this function.  The created block is placed on correct place
1208
   in LOOPS structure and its dominator is set.  */
1209
basic_block
1210
loop_split_edge_with (edge e, rtx insns)
1211
{
1212
  basic_block src, dest, new_bb;
1213
  struct loop *loop_c;
1214
 
1215
  src = e->src;
1216
  dest = e->dest;
1217
 
1218
  loop_c = find_common_loop (src->loop_father, dest->loop_father);
1219
 
1220
  /* Create basic block for it.  */
1221
 
1222
  new_bb = split_edge (e);
1223
  add_bb_to_loop (new_bb, loop_c);
1224
  new_bb->flags |= (insns ? BB_SUPERBLOCK : 0);
1225
 
1226
  if (insns)
1227
    emit_insn_after (insns, BB_END (new_bb));
1228
 
1229
  if (dest->loop_father->latch == src)
1230
    dest->loop_father->latch = new_bb;
1231
 
1232
  return new_bb;
1233
}
1234
 
1235
/* This function is called from loop_version.  It splits the entry edge
1236
   of the loop we want to version, adds the versioning condition, and
1237
   adjust the edges to the two versions of the loop appropriately.
1238
   e is an incoming edge. Returns the basic block containing the
1239
   condition.
1240
 
1241
   --- edge e ---- > [second_head]
1242
 
1243
   Split it and insert new conditional expression and adjust edges.
1244
 
1245
    --- edge e ---> [cond expr] ---> [first_head]
1246
                        |
1247
                        +---------> [second_head]
1248
*/
1249
 
1250
static basic_block
1251
lv_adjust_loop_entry_edge (basic_block first_head,
1252
                           basic_block second_head,
1253
                           edge e,
1254
                           void *cond_expr)
1255
{
1256
  basic_block new_head = NULL;
1257
  edge e1;
1258
 
1259
  gcc_assert (e->dest == second_head);
1260
 
1261
  /* Split edge 'e'. This will create a new basic block, where we can
1262
     insert conditional expr.  */
1263
  new_head = split_edge (e);
1264
 
1265
 
1266
  lv_add_condition_to_bb (first_head, second_head, new_head,
1267
                          cond_expr);
1268
 
1269
  /* Don't set EDGE_TRUE_VALUE in RTL mode, as it's invalid there.  */
1270
  e1 = make_edge (new_head, first_head, ir_type () ? EDGE_TRUE_VALUE : 0);
1271
  set_immediate_dominator (CDI_DOMINATORS, first_head, new_head);
1272
  set_immediate_dominator (CDI_DOMINATORS, second_head, new_head);
1273
 
1274
  /* Adjust loop header phi nodes.  */
1275
  lv_adjust_loop_header_phi (first_head, second_head, new_head, e1);
1276
 
1277
  return new_head;
1278
}
1279
 
1280
/* Main entry point for Loop Versioning transformation.
1281
 
1282
   This transformation given a condition and a loop, creates
1283
   -if (condition) { loop_copy1 } else { loop_copy2 },
1284
   where loop_copy1 is the loop transformed in one way, and loop_copy2
1285
   is the loop transformed in another way (or unchanged). 'condition'
1286
   may be a run time test for things that were not resolved by static
1287
   analysis (overlapping ranges (anti-aliasing), alignment, etc.).
1288
 
1289
   If PLACE_AFTER is true, we place the new loop after LOOP in the
1290
   instruction stream, otherwise it is placed before LOOP.  */
1291
 
1292
struct loop *
1293
loop_version (struct loops *loops, struct loop * loop,
1294
              void *cond_expr, basic_block *condition_bb,
1295
              bool place_after)
1296
{
1297
  basic_block first_head, second_head;
1298
  edge entry, latch_edge, exit, true_edge, false_edge;
1299
  int irred_flag;
1300
  struct loop *nloop;
1301
  basic_block cond_bb;
1302
 
1303
  /* CHECKME: Loop versioning does not handle nested loop at this point.  */
1304
  if (loop->inner)
1305
    return NULL;
1306
 
1307
  /* Record entry and latch edges for the loop */
1308
  entry = loop_preheader_edge (loop);
1309
  irred_flag = entry->flags & EDGE_IRREDUCIBLE_LOOP;
1310
  entry->flags &= ~EDGE_IRREDUCIBLE_LOOP;
1311
 
1312
  /* Note down head of loop as first_head.  */
1313
  first_head = entry->dest;
1314
 
1315
  /* Duplicate loop.  */
1316
  if (!cfg_hook_duplicate_loop_to_header_edge (loop, entry, loops, 1,
1317
                                               NULL, NULL, NULL, NULL, 0))
1318
    return NULL;
1319
 
1320
  /* After duplication entry edge now points to new loop head block.
1321
     Note down new head as second_head.  */
1322
  second_head = entry->dest;
1323
 
1324
  /* Split loop entry edge and insert new block with cond expr.  */
1325
  cond_bb =  lv_adjust_loop_entry_edge (first_head, second_head,
1326
                                        entry, cond_expr);
1327
  if (condition_bb)
1328
    *condition_bb = cond_bb;
1329
 
1330
  if (!cond_bb)
1331
    {
1332
      entry->flags |= irred_flag;
1333
      return NULL;
1334
    }
1335
 
1336
  latch_edge = single_succ_edge (get_bb_copy (loop->latch));
1337
 
1338
  extract_cond_bb_edges (cond_bb, &true_edge, &false_edge);
1339
  nloop = loopify (loops,
1340
                   latch_edge,
1341
                   single_pred_edge (get_bb_copy (loop->header)),
1342
                   cond_bb, true_edge, false_edge,
1343
                   false /* Do not redirect all edges.  */);
1344
 
1345
  exit = loop->single_exit;
1346
  if (exit)
1347
    nloop->single_exit = find_edge (get_bb_copy (exit->src), exit->dest);
1348
 
1349
  /* loopify redirected latch_edge. Update its PENDING_STMTS.  */
1350
  lv_flush_pending_stmts (latch_edge);
1351
 
1352
  /* loopify redirected condition_bb's succ edge. Update its PENDING_STMTS.  */
1353
  extract_cond_bb_edges (cond_bb, &true_edge, &false_edge);
1354
  lv_flush_pending_stmts (false_edge);
1355
  /* Adjust irreducible flag.  */
1356
  if (irred_flag)
1357
    {
1358
      cond_bb->flags |= BB_IRREDUCIBLE_LOOP;
1359
      loop_preheader_edge (loop)->flags |= EDGE_IRREDUCIBLE_LOOP;
1360
      loop_preheader_edge (nloop)->flags |= EDGE_IRREDUCIBLE_LOOP;
1361
      single_pred_edge (cond_bb)->flags |= EDGE_IRREDUCIBLE_LOOP;
1362
    }
1363
 
1364
  if (place_after)
1365
    {
1366
      basic_block *bbs = get_loop_body_in_dom_order (nloop), after;
1367
      unsigned i;
1368
 
1369
      after = loop->latch;
1370
 
1371
      for (i = 0; i < nloop->num_nodes; i++)
1372
        {
1373
          move_block_after (bbs[i], after);
1374
          after = bbs[i];
1375
        }
1376
      free (bbs);
1377
    }
1378
 
1379
  /* At this point condition_bb is loop predheader with two successors,
1380
     first_head and second_head.   Make sure that loop predheader has only
1381
     one successor.  */
1382
  loop_split_edge_with (loop_preheader_edge (loop), NULL);
1383
  loop_split_edge_with (loop_preheader_edge (nloop), NULL);
1384
 
1385
  return nloop;
1386
}
1387
 
1388
/* The structure of LOOPS might have changed.  Some loops might get removed
1389
   (and their headers and latches were set to NULL), loop exists might get
1390
   removed (thus the loop nesting may be wrong), and some blocks and edges
1391
   were changed (so the information about bb --> loop mapping does not have
1392
   to be correct).  But still for the remaining loops the header dominates
1393
   the latch, and loops did not get new subloobs (new loops might possibly
1394
   get created, but we are not interested in them).  Fix up the mess.
1395
 
1396
   If CHANGED_BBS is not NULL, basic blocks whose loop has changed are
1397
   marked in it.  */
1398
 
1399
void
1400
fix_loop_structure (struct loops *loops, bitmap changed_bbs)
1401
{
1402
  basic_block bb;
1403
  struct loop *loop, *ploop;
1404
  unsigned i;
1405
 
1406
  /* Remove the old bb -> loop mapping.  */
1407
  FOR_EACH_BB (bb)
1408
    {
1409
      bb->aux = (void *) (size_t) bb->loop_father->depth;
1410
      bb->loop_father = loops->tree_root;
1411
    }
1412
 
1413
  /* Remove the dead loops from structures.  */
1414
  loops->tree_root->num_nodes = n_basic_blocks;
1415
  for (i = 1; i < loops->num; i++)
1416
    {
1417
      loop = loops->parray[i];
1418
      if (!loop)
1419
        continue;
1420
 
1421
      loop->num_nodes = 0;
1422
      if (loop->header)
1423
        continue;
1424
 
1425
      while (loop->inner)
1426
        {
1427
          ploop = loop->inner;
1428
          flow_loop_tree_node_remove (ploop);
1429
          flow_loop_tree_node_add (loop->outer, ploop);
1430
        }
1431
 
1432
      /* Remove the loop and free its data.  */
1433
      flow_loop_tree_node_remove (loop);
1434
      loops->parray[loop->num] = NULL;
1435
      flow_loop_free (loop);
1436
    }
1437
 
1438
  /* Rescan the bodies of loops, starting from the outermost.  */
1439
  loop = loops->tree_root;
1440
  while (1)
1441
    {
1442
      if (loop->inner)
1443
        loop = loop->inner;
1444
      else
1445
        {
1446
          while (!loop->next
1447
                 && loop != loops->tree_root)
1448
            loop = loop->outer;
1449
          if (loop == loops->tree_root)
1450
            break;
1451
 
1452
          loop = loop->next;
1453
        }
1454
 
1455
      loop->num_nodes = flow_loop_nodes_find (loop->header, loop);
1456
    }
1457
 
1458
  /* Now fix the loop nesting.  */
1459
  for (i = 1; i < loops->num; i++)
1460
    {
1461
      loop = loops->parray[i];
1462
      if (!loop)
1463
        continue;
1464
 
1465
      bb = loop_preheader_edge (loop)->src;
1466
      if (bb->loop_father != loop->outer)
1467
        {
1468
          flow_loop_tree_node_remove (loop);
1469
          flow_loop_tree_node_add (bb->loop_father, loop);
1470
        }
1471
    }
1472
 
1473
  /* Mark the blocks whose loop has changed.  */
1474
  FOR_EACH_BB (bb)
1475
    {
1476
      if (changed_bbs
1477
          && (void *) (size_t) bb->loop_father->depth != bb->aux)
1478
        bitmap_set_bit (changed_bbs, bb->index);
1479
 
1480
      bb->aux = NULL;
1481
    }
1482
 
1483
  if (loops->state & LOOPS_HAVE_MARKED_SINGLE_EXITS)
1484
    mark_single_exit_loops (loops);
1485
  if (loops->state & LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS)
1486
    mark_irreducible_loops (loops);
1487
}

powered by: WebSVN 2.1.0

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