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

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-dev/] [or1k-gcc/] [gcc/] [lcm.c] - Blame information for rev 714

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

Line No. Rev Author Line
1 684 jeremybenn
/* Generic partial redundancy elimination with lazy code motion support.
2
   Copyright (C) 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2007, 2008,
3
   2010, 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
/* These routines are meant to be used by various optimization
22
   passes which can be modeled as lazy code motion problems.
23
   Including, but not limited to:
24
 
25
        * Traditional partial redundancy elimination.
26
 
27
        * Placement of caller/caller register save/restores.
28
 
29
        * Load/store motion.
30
 
31
        * Copy motion.
32
 
33
        * Conversion of flat register files to a stacked register
34
        model.
35
 
36
        * Dead load/store elimination.
37
 
38
  These routines accept as input:
39
 
40
        * Basic block information (number of blocks, lists of
41
        predecessors and successors).  Note the granularity
42
        does not need to be basic block, they could be statements
43
        or functions.
44
 
45
        * Bitmaps of local properties (computed, transparent and
46
        anticipatable expressions).
47
 
48
  The output of these routines is bitmap of redundant computations
49
  and a bitmap of optimal placement points.  */
50
 
51
 
52
#include "config.h"
53
#include "system.h"
54
#include "coretypes.h"
55
#include "tm.h"
56
#include "rtl.h"
57
#include "regs.h"
58
#include "hard-reg-set.h"
59
#include "flags.h"
60
#include "insn-config.h"
61
#include "recog.h"
62
#include "basic-block.h"
63
#include "output.h"
64
#include "tm_p.h"
65
#include "function.h"
66
#include "sbitmap.h"
67
 
68
/* We want target macros for the mode switching code to be able to refer
69
   to instruction attribute values.  */
70
#include "insn-attr.h"
71
 
72
/* Edge based LCM routines.  */
73
static void compute_antinout_edge (sbitmap *, sbitmap *, sbitmap *, sbitmap *);
74
static void compute_earliest (struct edge_list *, int, sbitmap *, sbitmap *,
75
                              sbitmap *, sbitmap *, sbitmap *);
76
static void compute_laterin (struct edge_list *, sbitmap *, sbitmap *,
77
                             sbitmap *, sbitmap *);
78
static void compute_insert_delete (struct edge_list *edge_list, sbitmap *,
79
                                   sbitmap *, sbitmap *, sbitmap *, sbitmap *);
80
 
81
/* Edge based LCM routines on a reverse flowgraph.  */
82
static void compute_farthest (struct edge_list *, int, sbitmap *, sbitmap *,
83
                              sbitmap*, sbitmap *, sbitmap *);
84
static void compute_nearerout (struct edge_list *, sbitmap *, sbitmap *,
85
                               sbitmap *, sbitmap *);
86
static void compute_rev_insert_delete (struct edge_list *edge_list, sbitmap *,
87
                                       sbitmap *, sbitmap *, sbitmap *,
88
                                       sbitmap *);
89
 
90
/* Edge based lcm routines.  */
91
 
92
/* Compute expression anticipatability at entrance and exit of each block.
93
   This is done based on the flow graph, and not on the pred-succ lists.
94
   Other than that, its pretty much identical to compute_antinout.  */
95
 
96
static void
97
compute_antinout_edge (sbitmap *antloc, sbitmap *transp, sbitmap *antin,
98
                       sbitmap *antout)
99
{
100
  basic_block bb;
101
  edge e;
102
  basic_block *worklist, *qin, *qout, *qend;
103
  unsigned int qlen;
104
  edge_iterator ei;
105
 
106
  /* Allocate a worklist array/queue.  Entries are only added to the
107
     list if they were not already on the list.  So the size is
108
     bounded by the number of basic blocks.  */
109
  qin = qout = worklist = XNEWVEC (basic_block, n_basic_blocks);
110
 
111
  /* We want a maximal solution, so make an optimistic initialization of
112
     ANTIN.  */
113
  sbitmap_vector_ones (antin, last_basic_block);
114
 
115
  /* Put every block on the worklist; this is necessary because of the
116
     optimistic initialization of ANTIN above.  */
117
  FOR_EACH_BB_REVERSE (bb)
118
    {
119
      *qin++ = bb;
120
      bb->aux = bb;
121
    }
122
 
123
  qin = worklist;
124
  qend = &worklist[n_basic_blocks - NUM_FIXED_BLOCKS];
125
  qlen = n_basic_blocks - NUM_FIXED_BLOCKS;
126
 
127
  /* Mark blocks which are predecessors of the exit block so that we
128
     can easily identify them below.  */
129
  FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
130
    e->src->aux = EXIT_BLOCK_PTR;
131
 
132
  /* Iterate until the worklist is empty.  */
133
  while (qlen)
134
    {
135
      /* Take the first entry off the worklist.  */
136
      bb = *qout++;
137
      qlen--;
138
 
139
      if (qout >= qend)
140
        qout = worklist;
141
 
142
      if (bb->aux == EXIT_BLOCK_PTR)
143
        /* Do not clear the aux field for blocks which are predecessors of
144
           the EXIT block.  That way we never add then to the worklist
145
           again.  */
146
        sbitmap_zero (antout[bb->index]);
147
      else
148
        {
149
          /* Clear the aux field of this block so that it can be added to
150
             the worklist again if necessary.  */
151
          bb->aux = NULL;
152
          sbitmap_intersection_of_succs (antout[bb->index], antin, bb->index);
153
        }
154
 
155
      if (sbitmap_a_or_b_and_c_cg (antin[bb->index], antloc[bb->index],
156
                                   transp[bb->index], antout[bb->index]))
157
        /* If the in state of this block changed, then we need
158
           to add the predecessors of this block to the worklist
159
           if they are not already on the worklist.  */
160
        FOR_EACH_EDGE (e, ei, bb->preds)
161
          if (!e->src->aux && e->src != ENTRY_BLOCK_PTR)
162
            {
163
              *qin++ = e->src;
164
              e->src->aux = e;
165
              qlen++;
166
              if (qin >= qend)
167
                qin = worklist;
168
            }
169
    }
170
 
171
  clear_aux_for_edges ();
172
  clear_aux_for_blocks ();
173
  free (worklist);
174
}
175
 
176
/* Compute the earliest vector for edge based lcm.  */
177
 
178
static void
179
compute_earliest (struct edge_list *edge_list, int n_exprs, sbitmap *antin,
180
                  sbitmap *antout, sbitmap *avout, sbitmap *kill,
181
                  sbitmap *earliest)
182
{
183
  sbitmap difference, temp_bitmap;
184
  int x, num_edges;
185
  basic_block pred, succ;
186
 
187
  num_edges = NUM_EDGES (edge_list);
188
 
189
  difference = sbitmap_alloc (n_exprs);
190
  temp_bitmap = sbitmap_alloc (n_exprs);
191
 
192
  for (x = 0; x < num_edges; x++)
193
    {
194
      pred = INDEX_EDGE_PRED_BB (edge_list, x);
195
      succ = INDEX_EDGE_SUCC_BB (edge_list, x);
196
      if (pred == ENTRY_BLOCK_PTR)
197
        sbitmap_copy (earliest[x], antin[succ->index]);
198
      else
199
        {
200
          if (succ == EXIT_BLOCK_PTR)
201
            sbitmap_zero (earliest[x]);
202
          else
203
            {
204
              sbitmap_difference (difference, antin[succ->index],
205
                                  avout[pred->index]);
206
              sbitmap_not (temp_bitmap, antout[pred->index]);
207
              sbitmap_a_and_b_or_c (earliest[x], difference,
208
                                    kill[pred->index], temp_bitmap);
209
            }
210
        }
211
    }
212
 
213
  sbitmap_free (temp_bitmap);
214
  sbitmap_free (difference);
215
}
216
 
217
/* later(p,s) is dependent on the calculation of laterin(p).
218
   laterin(p) is dependent on the calculation of later(p2,p).
219
 
220
     laterin(ENTRY) is defined as all 0's
221
     later(ENTRY, succs(ENTRY)) are defined using laterin(ENTRY)
222
     laterin(succs(ENTRY)) is defined by later(ENTRY, succs(ENTRY)).
223
 
224
   If we progress in this manner, starting with all basic blocks
225
   in the work list, anytime we change later(bb), we need to add
226
   succs(bb) to the worklist if they are not already on the worklist.
227
 
228
   Boundary conditions:
229
 
230
     We prime the worklist all the normal basic blocks.   The ENTRY block can
231
     never be added to the worklist since it is never the successor of any
232
     block.  We explicitly prevent the EXIT block from being added to the
233
     worklist.
234
 
235
     We optimistically initialize LATER.  That is the only time this routine
236
     will compute LATER for an edge out of the entry block since the entry
237
     block is never on the worklist.  Thus, LATERIN is neither used nor
238
     computed for the ENTRY block.
239
 
240
     Since the EXIT block is never added to the worklist, we will neither
241
     use nor compute LATERIN for the exit block.  Edges which reach the
242
     EXIT block are handled in the normal fashion inside the loop.  However,
243
     the insertion/deletion computation needs LATERIN(EXIT), so we have
244
     to compute it.  */
245
 
246
static void
247
compute_laterin (struct edge_list *edge_list, sbitmap *earliest,
248
                 sbitmap *antloc, sbitmap *later, sbitmap *laterin)
249
{
250
  int num_edges, i;
251
  edge e;
252
  basic_block *worklist, *qin, *qout, *qend, bb;
253
  unsigned int qlen;
254
  edge_iterator ei;
255
 
256
  num_edges = NUM_EDGES (edge_list);
257
 
258
  /* Allocate a worklist array/queue.  Entries are only added to the
259
     list if they were not already on the list.  So the size is
260
     bounded by the number of basic blocks.  */
261
  qin = qout = worklist
262
    = XNEWVEC (basic_block, n_basic_blocks);
263
 
264
  /* Initialize a mapping from each edge to its index.  */
265
  for (i = 0; i < num_edges; i++)
266
    INDEX_EDGE (edge_list, i)->aux = (void *) (size_t) i;
267
 
268
  /* We want a maximal solution, so initially consider LATER true for
269
     all edges.  This allows propagation through a loop since the incoming
270
     loop edge will have LATER set, so if all the other incoming edges
271
     to the loop are set, then LATERIN will be set for the head of the
272
     loop.
273
 
274
     If the optimistic setting of LATER on that edge was incorrect (for
275
     example the expression is ANTLOC in a block within the loop) then
276
     this algorithm will detect it when we process the block at the head
277
     of the optimistic edge.  That will requeue the affected blocks.  */
278
  sbitmap_vector_ones (later, num_edges);
279
 
280
  /* Note that even though we want an optimistic setting of LATER, we
281
     do not want to be overly optimistic.  Consider an outgoing edge from
282
     the entry block.  That edge should always have a LATER value the
283
     same as EARLIEST for that edge.  */
284
  FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
285
    sbitmap_copy (later[(size_t) e->aux], earliest[(size_t) e->aux]);
286
 
287
  /* Add all the blocks to the worklist.  This prevents an early exit from
288
     the loop given our optimistic initialization of LATER above.  */
289
  FOR_EACH_BB (bb)
290
    {
291
      *qin++ = bb;
292
      bb->aux = bb;
293
    }
294
 
295
  /* Note that we do not use the last allocated element for our queue,
296
     as EXIT_BLOCK is never inserted into it. */
297
  qin = worklist;
298
  qend = &worklist[n_basic_blocks - NUM_FIXED_BLOCKS];
299
  qlen = n_basic_blocks - NUM_FIXED_BLOCKS;
300
 
301
  /* Iterate until the worklist is empty.  */
302
  while (qlen)
303
    {
304
      /* Take the first entry off the worklist.  */
305
      bb = *qout++;
306
      bb->aux = NULL;
307
      qlen--;
308
      if (qout >= qend)
309
        qout = worklist;
310
 
311
      /* Compute the intersection of LATERIN for each incoming edge to B.  */
312
      sbitmap_ones (laterin[bb->index]);
313
      FOR_EACH_EDGE (e, ei, bb->preds)
314
        sbitmap_a_and_b (laterin[bb->index], laterin[bb->index],
315
                         later[(size_t)e->aux]);
316
 
317
      /* Calculate LATER for all outgoing edges.  */
318
      FOR_EACH_EDGE (e, ei, bb->succs)
319
        if (sbitmap_union_of_diff_cg (later[(size_t) e->aux],
320
                                      earliest[(size_t) e->aux],
321
                                      laterin[e->src->index],
322
                                      antloc[e->src->index])
323
            /* If LATER for an outgoing edge was changed, then we need
324
               to add the target of the outgoing edge to the worklist.  */
325
            && e->dest != EXIT_BLOCK_PTR && e->dest->aux == 0)
326
          {
327
            *qin++ = e->dest;
328
            e->dest->aux = e;
329
            qlen++;
330
            if (qin >= qend)
331
              qin = worklist;
332
          }
333
    }
334
 
335
  /* Computation of insertion and deletion points requires computing LATERIN
336
     for the EXIT block.  We allocated an extra entry in the LATERIN array
337
     for just this purpose.  */
338
  sbitmap_ones (laterin[last_basic_block]);
339
  FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
340
    sbitmap_a_and_b (laterin[last_basic_block],
341
                     laterin[last_basic_block],
342
                     later[(size_t) e->aux]);
343
 
344
  clear_aux_for_edges ();
345
  free (worklist);
346
}
347
 
348
/* Compute the insertion and deletion points for edge based LCM.  */
349
 
350
static void
351
compute_insert_delete (struct edge_list *edge_list, sbitmap *antloc,
352
                       sbitmap *later, sbitmap *laterin, sbitmap *insert,
353
                       sbitmap *del)
354
{
355
  int x;
356
  basic_block bb;
357
 
358
  FOR_EACH_BB (bb)
359
    sbitmap_difference (del[bb->index], antloc[bb->index],
360
                        laterin[bb->index]);
361
 
362
  for (x = 0; x < NUM_EDGES (edge_list); x++)
363
    {
364
      basic_block b = INDEX_EDGE_SUCC_BB (edge_list, x);
365
 
366
      if (b == EXIT_BLOCK_PTR)
367
        sbitmap_difference (insert[x], later[x], laterin[last_basic_block]);
368
      else
369
        sbitmap_difference (insert[x], later[x], laterin[b->index]);
370
    }
371
}
372
 
373
/* Given local properties TRANSP, ANTLOC, AVOUT, KILL return the insert and
374
   delete vectors for edge based LCM.  Returns an edgelist which is used to
375
   map the insert vector to what edge an expression should be inserted on.  */
376
 
377
struct edge_list *
378
pre_edge_lcm (int n_exprs, sbitmap *transp,
379
              sbitmap *avloc, sbitmap *antloc, sbitmap *kill,
380
              sbitmap **insert, sbitmap **del)
381
{
382
  sbitmap *antin, *antout, *earliest;
383
  sbitmap *avin, *avout;
384
  sbitmap *later, *laterin;
385
  struct edge_list *edge_list;
386
  int num_edges;
387
 
388
  edge_list = create_edge_list ();
389
  num_edges = NUM_EDGES (edge_list);
390
 
391
#ifdef LCM_DEBUG_INFO
392
  if (dump_file)
393
    {
394
      fprintf (dump_file, "Edge List:\n");
395
      verify_edge_list (dump_file, edge_list);
396
      print_edge_list (dump_file, edge_list);
397
      dump_sbitmap_vector (dump_file, "transp", "", transp, last_basic_block);
398
      dump_sbitmap_vector (dump_file, "antloc", "", antloc, last_basic_block);
399
      dump_sbitmap_vector (dump_file, "avloc", "", avloc, last_basic_block);
400
      dump_sbitmap_vector (dump_file, "kill", "", kill, last_basic_block);
401
    }
402
#endif
403
 
404
  /* Compute global availability.  */
405
  avin = sbitmap_vector_alloc (last_basic_block, n_exprs);
406
  avout = sbitmap_vector_alloc (last_basic_block, n_exprs);
407
  compute_available (avloc, kill, avout, avin);
408
  sbitmap_vector_free (avin);
409
 
410
  /* Compute global anticipatability.  */
411
  antin = sbitmap_vector_alloc (last_basic_block, n_exprs);
412
  antout = sbitmap_vector_alloc (last_basic_block, n_exprs);
413
  compute_antinout_edge (antloc, transp, antin, antout);
414
 
415
#ifdef LCM_DEBUG_INFO
416
  if (dump_file)
417
    {
418
      dump_sbitmap_vector (dump_file, "antin", "", antin, last_basic_block);
419
      dump_sbitmap_vector (dump_file, "antout", "", antout, last_basic_block);
420
    }
421
#endif
422
 
423
  /* Compute earliestness.  */
424
  earliest = sbitmap_vector_alloc (num_edges, n_exprs);
425
  compute_earliest (edge_list, n_exprs, antin, antout, avout, kill, earliest);
426
 
427
#ifdef LCM_DEBUG_INFO
428
  if (dump_file)
429
    dump_sbitmap_vector (dump_file, "earliest", "", earliest, num_edges);
430
#endif
431
 
432
  sbitmap_vector_free (antout);
433
  sbitmap_vector_free (antin);
434
  sbitmap_vector_free (avout);
435
 
436
  later = sbitmap_vector_alloc (num_edges, n_exprs);
437
 
438
  /* Allocate an extra element for the exit block in the laterin vector.  */
439
  laterin = sbitmap_vector_alloc (last_basic_block + 1, n_exprs);
440
  compute_laterin (edge_list, earliest, antloc, later, laterin);
441
 
442
#ifdef LCM_DEBUG_INFO
443
  if (dump_file)
444
    {
445
      dump_sbitmap_vector (dump_file, "laterin", "", laterin, last_basic_block + 1);
446
      dump_sbitmap_vector (dump_file, "later", "", later, num_edges);
447
    }
448
#endif
449
 
450
  sbitmap_vector_free (earliest);
451
 
452
  *insert = sbitmap_vector_alloc (num_edges, n_exprs);
453
  *del = sbitmap_vector_alloc (last_basic_block, n_exprs);
454
  sbitmap_vector_zero (*insert, num_edges);
455
  sbitmap_vector_zero (*del, last_basic_block);
456
  compute_insert_delete (edge_list, antloc, later, laterin, *insert, *del);
457
 
458
  sbitmap_vector_free (laterin);
459
  sbitmap_vector_free (later);
460
 
461
#ifdef LCM_DEBUG_INFO
462
  if (dump_file)
463
    {
464
      dump_sbitmap_vector (dump_file, "pre_insert_map", "", *insert, num_edges);
465
      dump_sbitmap_vector (dump_file, "pre_delete_map", "", *del,
466
                           last_basic_block);
467
    }
468
#endif
469
 
470
  return edge_list;
471
}
472
 
473
/* Compute the AVIN and AVOUT vectors from the AVLOC and KILL vectors.
474
   Return the number of passes we performed to iterate to a solution.  */
475
 
476
void
477
compute_available (sbitmap *avloc, sbitmap *kill, sbitmap *avout,
478
                   sbitmap *avin)
479
{
480
  edge e;
481
  basic_block *worklist, *qin, *qout, *qend, bb;
482
  unsigned int qlen;
483
  edge_iterator ei;
484
 
485
  /* Allocate a worklist array/queue.  Entries are only added to the
486
     list if they were not already on the list.  So the size is
487
     bounded by the number of basic blocks.  */
488
  qin = qout = worklist =
489
    XNEWVEC (basic_block, n_basic_blocks - NUM_FIXED_BLOCKS);
490
 
491
  /* We want a maximal solution.  */
492
  sbitmap_vector_ones (avout, last_basic_block);
493
 
494
  /* Put every block on the worklist; this is necessary because of the
495
     optimistic initialization of AVOUT above.  */
496
  FOR_EACH_BB (bb)
497
    {
498
      *qin++ = bb;
499
      bb->aux = bb;
500
    }
501
 
502
  qin = worklist;
503
  qend = &worklist[n_basic_blocks - NUM_FIXED_BLOCKS];
504
  qlen = n_basic_blocks - NUM_FIXED_BLOCKS;
505
 
506
  /* Mark blocks which are successors of the entry block so that we
507
     can easily identify them below.  */
508
  FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
509
    e->dest->aux = ENTRY_BLOCK_PTR;
510
 
511
  /* Iterate until the worklist is empty.  */
512
  while (qlen)
513
    {
514
      /* Take the first entry off the worklist.  */
515
      bb = *qout++;
516
      qlen--;
517
 
518
      if (qout >= qend)
519
        qout = worklist;
520
 
521
      /* If one of the predecessor blocks is the ENTRY block, then the
522
         intersection of avouts is the null set.  We can identify such blocks
523
         by the special value in the AUX field in the block structure.  */
524
      if (bb->aux == ENTRY_BLOCK_PTR)
525
        /* Do not clear the aux field for blocks which are successors of the
526
           ENTRY block.  That way we never add then to the worklist again.  */
527
        sbitmap_zero (avin[bb->index]);
528
      else
529
        {
530
          /* Clear the aux field of this block so that it can be added to
531
             the worklist again if necessary.  */
532
          bb->aux = NULL;
533
          sbitmap_intersection_of_preds (avin[bb->index], avout, bb->index);
534
        }
535
 
536
      if (sbitmap_union_of_diff_cg (avout[bb->index], avloc[bb->index],
537
                                    avin[bb->index], kill[bb->index]))
538
        /* If the out state of this block changed, then we need
539
           to add the successors of this block to the worklist
540
           if they are not already on the worklist.  */
541
        FOR_EACH_EDGE (e, ei, bb->succs)
542
          if (!e->dest->aux && e->dest != EXIT_BLOCK_PTR)
543
            {
544
              *qin++ = e->dest;
545
              e->dest->aux = e;
546
              qlen++;
547
 
548
              if (qin >= qend)
549
                qin = worklist;
550
            }
551
    }
552
 
553
  clear_aux_for_edges ();
554
  clear_aux_for_blocks ();
555
  free (worklist);
556
}
557
 
558
/* Compute the farthest vector for edge based lcm.  */
559
 
560
static void
561
compute_farthest (struct edge_list *edge_list, int n_exprs,
562
                  sbitmap *st_avout, sbitmap *st_avin, sbitmap *st_antin,
563
                  sbitmap *kill, sbitmap *farthest)
564
{
565
  sbitmap difference, temp_bitmap;
566
  int x, num_edges;
567
  basic_block pred, succ;
568
 
569
  num_edges = NUM_EDGES (edge_list);
570
 
571
  difference = sbitmap_alloc (n_exprs);
572
  temp_bitmap = sbitmap_alloc (n_exprs);
573
 
574
  for (x = 0; x < num_edges; x++)
575
    {
576
      pred = INDEX_EDGE_PRED_BB (edge_list, x);
577
      succ = INDEX_EDGE_SUCC_BB (edge_list, x);
578
      if (succ == EXIT_BLOCK_PTR)
579
        sbitmap_copy (farthest[x], st_avout[pred->index]);
580
      else
581
        {
582
          if (pred == ENTRY_BLOCK_PTR)
583
            sbitmap_zero (farthest[x]);
584
          else
585
            {
586
              sbitmap_difference (difference, st_avout[pred->index],
587
                                  st_antin[succ->index]);
588
              sbitmap_not (temp_bitmap, st_avin[succ->index]);
589
              sbitmap_a_and_b_or_c (farthest[x], difference,
590
                                    kill[succ->index], temp_bitmap);
591
            }
592
        }
593
    }
594
 
595
  sbitmap_free (temp_bitmap);
596
  sbitmap_free (difference);
597
}
598
 
599
/* Compute nearer and nearerout vectors for edge based lcm.
600
 
601
   This is the mirror of compute_laterin, additional comments on the
602
   implementation can be found before compute_laterin.  */
603
 
604
static void
605
compute_nearerout (struct edge_list *edge_list, sbitmap *farthest,
606
                   sbitmap *st_avloc, sbitmap *nearer, sbitmap *nearerout)
607
{
608
  int num_edges, i;
609
  edge e;
610
  basic_block *worklist, *tos, bb;
611
  edge_iterator ei;
612
 
613
  num_edges = NUM_EDGES (edge_list);
614
 
615
  /* Allocate a worklist array/queue.  Entries are only added to the
616
     list if they were not already on the list.  So the size is
617
     bounded by the number of basic blocks.  */
618
  tos = worklist = XNEWVEC (basic_block, n_basic_blocks + 1);
619
 
620
  /* Initialize NEARER for each edge and build a mapping from an edge to
621
     its index.  */
622
  for (i = 0; i < num_edges; i++)
623
    INDEX_EDGE (edge_list, i)->aux = (void *) (size_t) i;
624
 
625
  /* We want a maximal solution.  */
626
  sbitmap_vector_ones (nearer, num_edges);
627
 
628
  /* Note that even though we want an optimistic setting of NEARER, we
629
     do not want to be overly optimistic.  Consider an incoming edge to
630
     the exit block.  That edge should always have a NEARER value the
631
     same as FARTHEST for that edge.  */
632
  FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
633
    sbitmap_copy (nearer[(size_t)e->aux], farthest[(size_t)e->aux]);
634
 
635
  /* Add all the blocks to the worklist.  This prevents an early exit
636
     from the loop given our optimistic initialization of NEARER.  */
637
  FOR_EACH_BB (bb)
638
    {
639
      *tos++ = bb;
640
      bb->aux = bb;
641
    }
642
 
643
  /* Iterate until the worklist is empty.  */
644
  while (tos != worklist)
645
    {
646
      /* Take the first entry off the worklist.  */
647
      bb = *--tos;
648
      bb->aux = NULL;
649
 
650
      /* Compute the intersection of NEARER for each outgoing edge from B.  */
651
      sbitmap_ones (nearerout[bb->index]);
652
      FOR_EACH_EDGE (e, ei, bb->succs)
653
        sbitmap_a_and_b (nearerout[bb->index], nearerout[bb->index],
654
                         nearer[(size_t) e->aux]);
655
 
656
      /* Calculate NEARER for all incoming edges.  */
657
      FOR_EACH_EDGE (e, ei, bb->preds)
658
        if (sbitmap_union_of_diff_cg (nearer[(size_t) e->aux],
659
                                      farthest[(size_t) e->aux],
660
                                      nearerout[e->dest->index],
661
                                      st_avloc[e->dest->index])
662
            /* If NEARER for an incoming edge was changed, then we need
663
               to add the source of the incoming edge to the worklist.  */
664
            && e->src != ENTRY_BLOCK_PTR && e->src->aux == 0)
665
          {
666
            *tos++ = e->src;
667
            e->src->aux = e;
668
          }
669
    }
670
 
671
  /* Computation of insertion and deletion points requires computing NEAREROUT
672
     for the ENTRY block.  We allocated an extra entry in the NEAREROUT array
673
     for just this purpose.  */
674
  sbitmap_ones (nearerout[last_basic_block]);
675
  FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
676
    sbitmap_a_and_b (nearerout[last_basic_block],
677
                     nearerout[last_basic_block],
678
                     nearer[(size_t) e->aux]);
679
 
680
  clear_aux_for_edges ();
681
  free (tos);
682
}
683
 
684
/* Compute the insertion and deletion points for edge based LCM.  */
685
 
686
static void
687
compute_rev_insert_delete (struct edge_list *edge_list, sbitmap *st_avloc,
688
                           sbitmap *nearer, sbitmap *nearerout,
689
                           sbitmap *insert, sbitmap *del)
690
{
691
  int x;
692
  basic_block bb;
693
 
694
  FOR_EACH_BB (bb)
695
    sbitmap_difference (del[bb->index], st_avloc[bb->index],
696
                        nearerout[bb->index]);
697
 
698
  for (x = 0; x < NUM_EDGES (edge_list); x++)
699
    {
700
      basic_block b = INDEX_EDGE_PRED_BB (edge_list, x);
701
      if (b == ENTRY_BLOCK_PTR)
702
        sbitmap_difference (insert[x], nearer[x], nearerout[last_basic_block]);
703
      else
704
        sbitmap_difference (insert[x], nearer[x], nearerout[b->index]);
705
    }
706
}
707
 
708
/* Given local properties TRANSP, ST_AVLOC, ST_ANTLOC, KILL return the
709
   insert and delete vectors for edge based reverse LCM.  Returns an
710
   edgelist which is used to map the insert vector to what edge
711
   an expression should be inserted on.  */
712
 
713
struct edge_list *
714
pre_edge_rev_lcm (int n_exprs, sbitmap *transp,
715
                  sbitmap *st_avloc, sbitmap *st_antloc, sbitmap *kill,
716
                  sbitmap **insert, sbitmap **del)
717
{
718
  sbitmap *st_antin, *st_antout;
719
  sbitmap *st_avout, *st_avin, *farthest;
720
  sbitmap *nearer, *nearerout;
721
  struct edge_list *edge_list;
722
  int num_edges;
723
 
724
  edge_list = create_edge_list ();
725
  num_edges = NUM_EDGES (edge_list);
726
 
727
  st_antin = sbitmap_vector_alloc (last_basic_block, n_exprs);
728
  st_antout = sbitmap_vector_alloc (last_basic_block, n_exprs);
729
  sbitmap_vector_zero (st_antin, last_basic_block);
730
  sbitmap_vector_zero (st_antout, last_basic_block);
731
  compute_antinout_edge (st_antloc, transp, st_antin, st_antout);
732
 
733
  /* Compute global anticipatability.  */
734
  st_avout = sbitmap_vector_alloc (last_basic_block, n_exprs);
735
  st_avin = sbitmap_vector_alloc (last_basic_block, n_exprs);
736
  compute_available (st_avloc, kill, st_avout, st_avin);
737
 
738
#ifdef LCM_DEBUG_INFO
739
  if (dump_file)
740
    {
741
      fprintf (dump_file, "Edge List:\n");
742
      verify_edge_list (dump_file, edge_list);
743
      print_edge_list (dump_file, edge_list);
744
      dump_sbitmap_vector (dump_file, "transp", "", transp, last_basic_block);
745
      dump_sbitmap_vector (dump_file, "st_avloc", "", st_avloc, last_basic_block);
746
      dump_sbitmap_vector (dump_file, "st_antloc", "", st_antloc, last_basic_block);
747
      dump_sbitmap_vector (dump_file, "st_antin", "", st_antin, last_basic_block);
748
      dump_sbitmap_vector (dump_file, "st_antout", "", st_antout, last_basic_block);
749
      dump_sbitmap_vector (dump_file, "st_kill", "", kill, last_basic_block);
750
    }
751
#endif
752
 
753
#ifdef LCM_DEBUG_INFO
754
  if (dump_file)
755
    {
756
      dump_sbitmap_vector (dump_file, "st_avout", "", st_avout, last_basic_block);
757
      dump_sbitmap_vector (dump_file, "st_avin", "", st_avin, last_basic_block);
758
    }
759
#endif
760
 
761
  /* Compute farthestness.  */
762
  farthest = sbitmap_vector_alloc (num_edges, n_exprs);
763
  compute_farthest (edge_list, n_exprs, st_avout, st_avin, st_antin,
764
                    kill, farthest);
765
 
766
#ifdef LCM_DEBUG_INFO
767
  if (dump_file)
768
    dump_sbitmap_vector (dump_file, "farthest", "", farthest, num_edges);
769
#endif
770
 
771
  sbitmap_vector_free (st_antin);
772
  sbitmap_vector_free (st_antout);
773
 
774
  sbitmap_vector_free (st_avin);
775
  sbitmap_vector_free (st_avout);
776
 
777
  nearer = sbitmap_vector_alloc (num_edges, n_exprs);
778
 
779
  /* Allocate an extra element for the entry block.  */
780
  nearerout = sbitmap_vector_alloc (last_basic_block + 1, n_exprs);
781
  compute_nearerout (edge_list, farthest, st_avloc, nearer, nearerout);
782
 
783
#ifdef LCM_DEBUG_INFO
784
  if (dump_file)
785
    {
786
      dump_sbitmap_vector (dump_file, "nearerout", "", nearerout,
787
                           last_basic_block + 1);
788
      dump_sbitmap_vector (dump_file, "nearer", "", nearer, num_edges);
789
    }
790
#endif
791
 
792
  sbitmap_vector_free (farthest);
793
 
794
  *insert = sbitmap_vector_alloc (num_edges, n_exprs);
795
  *del = sbitmap_vector_alloc (last_basic_block, n_exprs);
796
  compute_rev_insert_delete (edge_list, st_avloc, nearer, nearerout,
797
                             *insert, *del);
798
 
799
  sbitmap_vector_free (nearerout);
800
  sbitmap_vector_free (nearer);
801
 
802
#ifdef LCM_DEBUG_INFO
803
  if (dump_file)
804
    {
805
      dump_sbitmap_vector (dump_file, "pre_insert_map", "", *insert, num_edges);
806
      dump_sbitmap_vector (dump_file, "pre_delete_map", "", *del,
807
                           last_basic_block);
808
    }
809
#endif
810
  return edge_list;
811
}
812
 

powered by: WebSVN 2.1.0

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