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

Subversion Repositories openrisc_me

[/] [openrisc/] [trunk/] [gnu-src/] [gcc-4.2.2/] [gcc/] [lcm.c] - Blame information for rev 154

Details | Compare with Previous | View Log

Line No. Rev Author Line
1 38 julius
/* Generic partial redundancy elimination with lazy code motion support.
2
   Copyright (C) 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2007
3
   Free Software Foundation, Inc.
4
 
5
This file is part of GCC.
6
 
7
GCC is free software; you can redistribute it and/or modify it under
8
the terms of the GNU General Public License as published by the Free
9
Software Foundation; either version 3, or (at your option) any later
10
version.
11
 
12
GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13
WARRANTY; without even the implied warranty of MERCHANTABILITY or
14
FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
15
for more details.
16
 
17
You should have received a copy of the GNU General Public License
18
along with GCC; see the file COPYING3.  If not see
19
<http://www.gnu.org/licenses/>.  */
20
 
21
/* 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 "real.h"
61
#include "insn-config.h"
62
#include "recog.h"
63
#include "basic-block.h"
64
#include "output.h"
65
#include "tm_p.h"
66
#include "function.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 *delete)
354
{
355
  int x;
356
  basic_block bb;
357
 
358
  FOR_EACH_BB (bb)
359
    sbitmap_difference (delete[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 **delete)
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
  *delete = sbitmap_vector_alloc (last_basic_block, n_exprs);
454
  compute_insert_delete (edge_list, antloc, later, laterin, *insert, *delete);
455
 
456
  sbitmap_vector_free (laterin);
457
  sbitmap_vector_free (later);
458
 
459
#ifdef LCM_DEBUG_INFO
460
  if (dump_file)
461
    {
462
      dump_sbitmap_vector (dump_file, "pre_insert_map", "", *insert, num_edges);
463
      dump_sbitmap_vector (dump_file, "pre_delete_map", "", *delete,
464
                           last_basic_block);
465
    }
466
#endif
467
 
468
  return edge_list;
469
}
470
 
471
/* Compute the AVIN and AVOUT vectors from the AVLOC and KILL vectors.
472
   Return the number of passes we performed to iterate to a solution.  */
473
 
474
void
475
compute_available (sbitmap *avloc, sbitmap *kill, sbitmap *avout,
476
                   sbitmap *avin)
477
{
478
  edge e;
479
  basic_block *worklist, *qin, *qout, *qend, bb;
480
  unsigned int qlen;
481
  edge_iterator ei;
482
 
483
  /* Allocate a worklist array/queue.  Entries are only added to the
484
     list if they were not already on the list.  So the size is
485
     bounded by the number of basic blocks.  */
486
  qin = qout = worklist =
487
    XNEWVEC (basic_block, n_basic_blocks - NUM_FIXED_BLOCKS);
488
 
489
  /* We want a maximal solution.  */
490
  sbitmap_vector_ones (avout, last_basic_block);
491
 
492
  /* Put every block on the worklist; this is necessary because of the
493
     optimistic initialization of AVOUT above.  */
494
  FOR_EACH_BB (bb)
495
    {
496
      *qin++ = bb;
497
      bb->aux = bb;
498
    }
499
 
500
  qin = worklist;
501
  qend = &worklist[n_basic_blocks - NUM_FIXED_BLOCKS];
502
  qlen = n_basic_blocks - NUM_FIXED_BLOCKS;
503
 
504
  /* Mark blocks which are successors of the entry block so that we
505
     can easily identify them below.  */
506
  FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
507
    e->dest->aux = ENTRY_BLOCK_PTR;
508
 
509
  /* Iterate until the worklist is empty.  */
510
  while (qlen)
511
    {
512
      /* Take the first entry off the worklist.  */
513
      bb = *qout++;
514
      qlen--;
515
 
516
      if (qout >= qend)
517
        qout = worklist;
518
 
519
      /* If one of the predecessor blocks is the ENTRY block, then the
520
         intersection of avouts is the null set.  We can identify such blocks
521
         by the special value in the AUX field in the block structure.  */
522
      if (bb->aux == ENTRY_BLOCK_PTR)
523
        /* Do not clear the aux field for blocks which are successors of the
524
           ENTRY block.  That way we never add then to the worklist again.  */
525
        sbitmap_zero (avin[bb->index]);
526
      else
527
        {
528
          /* Clear the aux field of this block so that it can be added to
529
             the worklist again if necessary.  */
530
          bb->aux = NULL;
531
          sbitmap_intersection_of_preds (avin[bb->index], avout, bb->index);
532
        }
533
 
534
      if (sbitmap_union_of_diff_cg (avout[bb->index], avloc[bb->index],
535
                                    avin[bb->index], kill[bb->index]))
536
        /* If the out state of this block changed, then we need
537
           to add the successors of this block to the worklist
538
           if they are not already on the worklist.  */
539
        FOR_EACH_EDGE (e, ei, bb->succs)
540
          if (!e->dest->aux && e->dest != EXIT_BLOCK_PTR)
541
            {
542
              *qin++ = e->dest;
543
              e->dest->aux = e;
544
              qlen++;
545
 
546
              if (qin >= qend)
547
                qin = worklist;
548
            }
549
    }
550
 
551
  clear_aux_for_edges ();
552
  clear_aux_for_blocks ();
553
  free (worklist);
554
}
555
 
556
/* Compute the farthest vector for edge based lcm.  */
557
 
558
static void
559
compute_farthest (struct edge_list *edge_list, int n_exprs,
560
                  sbitmap *st_avout, sbitmap *st_avin, sbitmap *st_antin,
561
                  sbitmap *kill, sbitmap *farthest)
562
{
563
  sbitmap difference, temp_bitmap;
564
  int x, num_edges;
565
  basic_block pred, succ;
566
 
567
  num_edges = NUM_EDGES (edge_list);
568
 
569
  difference = sbitmap_alloc (n_exprs);
570
  temp_bitmap = sbitmap_alloc (n_exprs);
571
 
572
  for (x = 0; x < num_edges; x++)
573
    {
574
      pred = INDEX_EDGE_PRED_BB (edge_list, x);
575
      succ = INDEX_EDGE_SUCC_BB (edge_list, x);
576
      if (succ == EXIT_BLOCK_PTR)
577
        sbitmap_copy (farthest[x], st_avout[pred->index]);
578
      else
579
        {
580
          if (pred == ENTRY_BLOCK_PTR)
581
            sbitmap_zero (farthest[x]);
582
          else
583
            {
584
              sbitmap_difference (difference, st_avout[pred->index],
585
                                  st_antin[succ->index]);
586
              sbitmap_not (temp_bitmap, st_avin[succ->index]);
587
              sbitmap_a_and_b_or_c (farthest[x], difference,
588
                                    kill[succ->index], temp_bitmap);
589
            }
590
        }
591
    }
592
 
593
  sbitmap_free (temp_bitmap);
594
  sbitmap_free (difference);
595
}
596
 
597
/* Compute nearer and nearerout vectors for edge based lcm.
598
 
599
   This is the mirror of compute_laterin, additional comments on the
600
   implementation can be found before compute_laterin.  */
601
 
602
static void
603
compute_nearerout (struct edge_list *edge_list, sbitmap *farthest,
604
                   sbitmap *st_avloc, sbitmap *nearer, sbitmap *nearerout)
605
{
606
  int num_edges, i;
607
  edge e;
608
  basic_block *worklist, *tos, bb;
609
  edge_iterator ei;
610
 
611
  num_edges = NUM_EDGES (edge_list);
612
 
613
  /* Allocate a worklist array/queue.  Entries are only added to the
614
     list if they were not already on the list.  So the size is
615
     bounded by the number of basic blocks.  */
616
  tos = worklist = XNEWVEC (basic_block, n_basic_blocks + 1);
617
 
618
  /* Initialize NEARER for each edge and build a mapping from an edge to
619
     its index.  */
620
  for (i = 0; i < num_edges; i++)
621
    INDEX_EDGE (edge_list, i)->aux = (void *) (size_t) i;
622
 
623
  /* We want a maximal solution.  */
624
  sbitmap_vector_ones (nearer, num_edges);
625
 
626
  /* Note that even though we want an optimistic setting of NEARER, we
627
     do not want to be overly optimistic.  Consider an incoming edge to
628
     the exit block.  That edge should always have a NEARER value the
629
     same as FARTHEST for that edge.  */
630
  FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
631
    sbitmap_copy (nearer[(size_t)e->aux], farthest[(size_t)e->aux]);
632
 
633
  /* Add all the blocks to the worklist.  This prevents an early exit
634
     from the loop given our optimistic initialization of NEARER.  */
635
  FOR_EACH_BB (bb)
636
    {
637
      *tos++ = bb;
638
      bb->aux = bb;
639
    }
640
 
641
  /* Iterate until the worklist is empty.  */
642
  while (tos != worklist)
643
    {
644
      /* Take the first entry off the worklist.  */
645
      bb = *--tos;
646
      bb->aux = NULL;
647
 
648
      /* Compute the intersection of NEARER for each outgoing edge from B.  */
649
      sbitmap_ones (nearerout[bb->index]);
650
      FOR_EACH_EDGE (e, ei, bb->succs)
651
        sbitmap_a_and_b (nearerout[bb->index], nearerout[bb->index],
652
                         nearer[(size_t) e->aux]);
653
 
654
      /* Calculate NEARER for all incoming edges.  */
655
      FOR_EACH_EDGE (e, ei, bb->preds)
656
        if (sbitmap_union_of_diff_cg (nearer[(size_t) e->aux],
657
                                      farthest[(size_t) e->aux],
658
                                      nearerout[e->dest->index],
659
                                      st_avloc[e->dest->index])
660
            /* If NEARER for an incoming edge was changed, then we need
661
               to add the source of the incoming edge to the worklist.  */
662
            && e->src != ENTRY_BLOCK_PTR && e->src->aux == 0)
663
          {
664
            *tos++ = e->src;
665
            e->src->aux = e;
666
          }
667
    }
668
 
669
  /* Computation of insertion and deletion points requires computing NEAREROUT
670
     for the ENTRY block.  We allocated an extra entry in the NEAREROUT array
671
     for just this purpose.  */
672
  sbitmap_ones (nearerout[last_basic_block]);
673
  FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
674
    sbitmap_a_and_b (nearerout[last_basic_block],
675
                     nearerout[last_basic_block],
676
                     nearer[(size_t) e->aux]);
677
 
678
  clear_aux_for_edges ();
679
  free (tos);
680
}
681
 
682
/* Compute the insertion and deletion points for edge based LCM.  */
683
 
684
static void
685
compute_rev_insert_delete (struct edge_list *edge_list, sbitmap *st_avloc,
686
                           sbitmap *nearer, sbitmap *nearerout,
687
                           sbitmap *insert, sbitmap *delete)
688
{
689
  int x;
690
  basic_block bb;
691
 
692
  FOR_EACH_BB (bb)
693
    sbitmap_difference (delete[bb->index], st_avloc[bb->index],
694
                        nearerout[bb->index]);
695
 
696
  for (x = 0; x < NUM_EDGES (edge_list); x++)
697
    {
698
      basic_block b = INDEX_EDGE_PRED_BB (edge_list, x);
699
      if (b == ENTRY_BLOCK_PTR)
700
        sbitmap_difference (insert[x], nearer[x], nearerout[last_basic_block]);
701
      else
702
        sbitmap_difference (insert[x], nearer[x], nearerout[b->index]);
703
    }
704
}
705
 
706
/* Given local properties TRANSP, ST_AVLOC, ST_ANTLOC, KILL return the
707
   insert and delete vectors for edge based reverse LCM.  Returns an
708
   edgelist which is used to map the insert vector to what edge
709
   an expression should be inserted on.  */
710
 
711
struct edge_list *
712
pre_edge_rev_lcm (int n_exprs, sbitmap *transp,
713
                  sbitmap *st_avloc, sbitmap *st_antloc, sbitmap *kill,
714
                  sbitmap **insert, sbitmap **delete)
715
{
716
  sbitmap *st_antin, *st_antout;
717
  sbitmap *st_avout, *st_avin, *farthest;
718
  sbitmap *nearer, *nearerout;
719
  struct edge_list *edge_list;
720
  int num_edges;
721
 
722
  edge_list = create_edge_list ();
723
  num_edges = NUM_EDGES (edge_list);
724
 
725
  st_antin = sbitmap_vector_alloc (last_basic_block, n_exprs);
726
  st_antout = sbitmap_vector_alloc (last_basic_block, n_exprs);
727
  sbitmap_vector_zero (st_antin, last_basic_block);
728
  sbitmap_vector_zero (st_antout, last_basic_block);
729
  compute_antinout_edge (st_antloc, transp, st_antin, st_antout);
730
 
731
  /* Compute global anticipatability.  */
732
  st_avout = sbitmap_vector_alloc (last_basic_block, n_exprs);
733
  st_avin = sbitmap_vector_alloc (last_basic_block, n_exprs);
734
  compute_available (st_avloc, kill, st_avout, st_avin);
735
 
736
#ifdef LCM_DEBUG_INFO
737
  if (dump_file)
738
    {
739
      fprintf (dump_file, "Edge List:\n");
740
      verify_edge_list (dump_file, edge_list);
741
      print_edge_list (dump_file, edge_list);
742
      dump_sbitmap_vector (dump_file, "transp", "", transp, last_basic_block);
743
      dump_sbitmap_vector (dump_file, "st_avloc", "", st_avloc, last_basic_block);
744
      dump_sbitmap_vector (dump_file, "st_antloc", "", st_antloc, last_basic_block);
745
      dump_sbitmap_vector (dump_file, "st_antin", "", st_antin, last_basic_block);
746
      dump_sbitmap_vector (dump_file, "st_antout", "", st_antout, last_basic_block);
747
      dump_sbitmap_vector (dump_file, "st_kill", "", kill, last_basic_block);
748
    }
749
#endif
750
 
751
#ifdef LCM_DEBUG_INFO
752
  if (dump_file)
753
    {
754
      dump_sbitmap_vector (dump_file, "st_avout", "", st_avout, last_basic_block);
755
      dump_sbitmap_vector (dump_file, "st_avin", "", st_avin, last_basic_block);
756
    }
757
#endif
758
 
759
  /* Compute farthestness.  */
760
  farthest = sbitmap_vector_alloc (num_edges, n_exprs);
761
  compute_farthest (edge_list, n_exprs, st_avout, st_avin, st_antin,
762
                    kill, farthest);
763
 
764
#ifdef LCM_DEBUG_INFO
765
  if (dump_file)
766
    dump_sbitmap_vector (dump_file, "farthest", "", farthest, num_edges);
767
#endif
768
 
769
  sbitmap_vector_free (st_antin);
770
  sbitmap_vector_free (st_antout);
771
 
772
  sbitmap_vector_free (st_avin);
773
  sbitmap_vector_free (st_avout);
774
 
775
  nearer = sbitmap_vector_alloc (num_edges, n_exprs);
776
 
777
  /* Allocate an extra element for the entry block.  */
778
  nearerout = sbitmap_vector_alloc (last_basic_block + 1, n_exprs);
779
  compute_nearerout (edge_list, farthest, st_avloc, nearer, nearerout);
780
 
781
#ifdef LCM_DEBUG_INFO
782
  if (dump_file)
783
    {
784
      dump_sbitmap_vector (dump_file, "nearerout", "", nearerout,
785
                           last_basic_block + 1);
786
      dump_sbitmap_vector (dump_file, "nearer", "", nearer, num_edges);
787
    }
788
#endif
789
 
790
  sbitmap_vector_free (farthest);
791
 
792
  *insert = sbitmap_vector_alloc (num_edges, n_exprs);
793
  *delete = sbitmap_vector_alloc (last_basic_block, n_exprs);
794
  compute_rev_insert_delete (edge_list, st_avloc, nearer, nearerout,
795
                             *insert, *delete);
796
 
797
  sbitmap_vector_free (nearerout);
798
  sbitmap_vector_free (nearer);
799
 
800
#ifdef LCM_DEBUG_INFO
801
  if (dump_file)
802
    {
803
      dump_sbitmap_vector (dump_file, "pre_insert_map", "", *insert, num_edges);
804
      dump_sbitmap_vector (dump_file, "pre_delete_map", "", *delete,
805
                           last_basic_block);
806
    }
807
#endif
808
  return edge_list;
809
}
810
 

powered by: WebSVN 2.1.0

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