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

Subversion Repositories openrisc

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

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

Line No. Rev Author Line
1 280 jeremybenn
/* Routines to implement minimum-cost maximal flow algorithm used to smooth
2
   basic block and edge frequency counts.
3
   Copyright (C) 2008, 2009
4
   Free Software Foundation, Inc.
5
   Contributed by Paul Yuan (yingbo.com@gmail.com) and
6
                  Vinodha Ramasamy (vinodha@google.com).
7
 
8
This file is part of GCC.
9
GCC is free software; you can redistribute it and/or modify it under
10
the terms of the GNU General Public License as published by the Free
11
Software Foundation; either version 3, or (at your option) any later
12
version.
13
 
14
GCC is distributed in the hope that it will be useful, but WITHOUT ANY
15
WARRANTY; without even the implied warranty of MERCHANTABILITY or
16
FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
17
for more details.
18
 
19
You should have received a copy of the GNU General Public License
20
along with GCC; see the file COPYING3.  If not see
21
<http://www.gnu.org/licenses/>.  */
22
 
23
/* References:
24
   [1] "Feedback-directed Optimizations in GCC with Estimated Edge Profiles
25
        from Hardware Event Sampling", Vinodha Ramasamy, Paul Yuan, Dehao Chen,
26
        and Robert Hundt; GCC Summit 2008.
27
   [2] "Complementing Missing and Inaccurate Profiling Using a Minimum Cost
28
        Circulation Algorithm", Roy Levin, Ilan Newman and Gadi Haber;
29
        HiPEAC '08.
30
 
31
   Algorithm to smooth basic block and edge counts:
32
   1. create_fixup_graph: Create fixup graph by translating function CFG into
33
      a graph that satisfies MCF algorithm requirements.
34
   2. find_max_flow: Find maximal flow.
35
   3. compute_residual_flow: Form residual network.
36
   4. Repeat:
37
      cancel_negative_cycle: While G contains a negative cost cycle C, reverse
38
      the flow on the found cycle by the minimum residual capacity in that
39
      cycle.
40
   5. Form the minimal cost flow
41
      f(u,v) = rf(v, u).
42
   6. adjust_cfg_counts: Update initial edge weights with corrected weights.
43
      delta(u.v) = f(u,v) -f(v,u).
44
      w*(u,v) = w(u,v) + delta(u,v).  */
45
 
46
#include "config.h"
47
#include "system.h"
48
#include "coretypes.h"
49
#include "tm.h"
50
#include "basic-block.h"
51
#include "output.h"
52
#include "langhooks.h"
53
#include "tree.h"
54
#include "gcov-io.h"
55
 
56
#include "profile.h"
57
 
58
/* CAP_INFINITY: Constant to represent infinite capacity.  */
59
#define CAP_INFINITY INTTYPE_MAXIMUM (HOST_WIDEST_INT)
60
 
61
/* COST FUNCTION.  */
62
#define K_POS(b)        ((b))
63
#define K_NEG(b)        (50 * (b))
64
#define COST(k, w)      ((k) / mcf_ln ((w) + 2))
65
/* Limit the number of iterations for cancel_negative_cycles() to ensure
66
   reasonable compile time.  */
67
#define MAX_ITER(n, e)  10 + (1000000 / ((n) * (e)))
68
typedef enum
69
{
70
  INVALID_EDGE,
71
  VERTEX_SPLIT_EDGE,        /* Edge to represent vertex with w(e) = w(v).  */
72
  REDIRECT_EDGE,            /* Edge after vertex transformation.  */
73
  REVERSE_EDGE,
74
  SOURCE_CONNECT_EDGE,      /* Single edge connecting to single source.  */
75
  SINK_CONNECT_EDGE,        /* Single edge connecting to single sink.  */
76
  BALANCE_EDGE,             /* Edge connecting with source/sink: cp(e) = 0.  */
77
  REDIRECT_NORMALIZED_EDGE, /* Normalized edge for a redirect edge.  */
78
  REVERSE_NORMALIZED_EDGE   /* Normalized edge for a reverse edge.  */
79
} edge_type;
80
 
81
/* Structure to represent an edge in the fixup graph.  */
82
typedef struct fixup_edge_d
83
{
84
  int src;
85
  int dest;
86
  /* Flag denoting type of edge and attributes for the flow field.  */
87
  edge_type type;
88
  bool is_rflow_valid;
89
  /* Index to the normalization vertex added for this edge.  */
90
  int norm_vertex_index;
91
  /* Flow for this edge.  */
92
  gcov_type flow;
93
  /* Residual flow for this edge - used during negative cycle canceling.  */
94
  gcov_type rflow;
95
  gcov_type weight;
96
  gcov_type cost;
97
  gcov_type max_capacity;
98
} fixup_edge_type;
99
 
100
typedef fixup_edge_type *fixup_edge_p;
101
 
102
DEF_VEC_P (fixup_edge_p);
103
DEF_VEC_ALLOC_P (fixup_edge_p, heap);
104
 
105
/* Structure to represent a vertex in the fixup graph.  */
106
typedef struct fixup_vertex_d
107
{
108
  VEC (fixup_edge_p, heap) *succ_edges;
109
} fixup_vertex_type;
110
 
111
typedef fixup_vertex_type *fixup_vertex_p;
112
 
113
/* Fixup graph used in the MCF algorithm.  */
114
typedef struct fixup_graph_d
115
{
116
  /* Current number of vertices for the graph.  */
117
  int num_vertices;
118
  /* Current number of edges for the graph.  */
119
  int num_edges;
120
  /* Index of new entry vertex.  */
121
  int new_entry_index;
122
  /* Index of new exit vertex.  */
123
  int new_exit_index;
124
  /* Fixup vertex list. Adjacency list for fixup graph.  */
125
  fixup_vertex_p vertex_list;
126
  /* Fixup edge list.  */
127
  fixup_edge_p edge_list;
128
} fixup_graph_type;
129
 
130
typedef struct queue_d
131
{
132
  int *queue;
133
  int head;
134
  int tail;
135
  int size;
136
} queue_type;
137
 
138
/* Structure used in the maximal flow routines to find augmenting path.  */
139
typedef struct augmenting_path_d
140
{
141
  /* Queue used to hold vertex indices.  */
142
  queue_type queue_list;
143
  /* Vector to hold chain of pred vertex indices in augmenting path.  */
144
  int *bb_pred;
145
  /* Vector that indicates if basic block i has been visited.  */
146
  int *is_visited;
147
} augmenting_path_type;
148
 
149
 
150
/* Function definitions.  */
151
 
152
/* Dump routines to aid debugging.  */
153
 
154
/* Print basic block with index N for FIXUP_GRAPH in n' and n'' format.  */
155
 
156
static void
157
print_basic_block (FILE *file, fixup_graph_type *fixup_graph, int n)
158
{
159
  if (n == ENTRY_BLOCK)
160
    fputs ("ENTRY", file);
161
  else if (n == ENTRY_BLOCK + 1)
162
    fputs ("ENTRY''", file);
163
  else if (n == 2 * EXIT_BLOCK)
164
    fputs ("EXIT", file);
165
  else if (n == 2 * EXIT_BLOCK + 1)
166
    fputs ("EXIT''", file);
167
  else if (n == fixup_graph->new_exit_index)
168
    fputs ("NEW_EXIT", file);
169
  else if (n == fixup_graph->new_entry_index)
170
    fputs ("NEW_ENTRY", file);
171
  else
172
    {
173
      fprintf (file, "%d", n / 2);
174
      if (n % 2)
175
        fputs ("''", file);
176
      else
177
        fputs ("'", file);
178
    }
179
}
180
 
181
 
182
/* Print edge S->D for given fixup_graph with n' and n'' format.
183
   PARAMETERS:
184
   S is the index of the source vertex of the edge (input) and
185
   D is the index of the destination vertex of the edge (input) for the given
186
   fixup_graph (input).  */
187
 
188
static void
189
print_edge (FILE *file, fixup_graph_type *fixup_graph, int s, int d)
190
{
191
  print_basic_block (file, fixup_graph, s);
192
  fputs ("->", file);
193
  print_basic_block (file, fixup_graph, d);
194
}
195
 
196
 
197
/* Dump out the attributes of a given edge FEDGE in the fixup_graph to a
198
   file.  */
199
static void
200
dump_fixup_edge (FILE *file, fixup_graph_type *fixup_graph, fixup_edge_p fedge)
201
{
202
  if (!fedge)
203
    {
204
      fputs ("NULL fixup graph edge.\n", file);
205
      return;
206
    }
207
 
208
  print_edge (file, fixup_graph, fedge->src, fedge->dest);
209
  fputs (": ", file);
210
 
211
  if (fedge->type)
212
    {
213
      fprintf (file, "flow/capacity=" HOST_WIDEST_INT_PRINT_DEC "/",
214
               fedge->flow);
215
      if (fedge->max_capacity == CAP_INFINITY)
216
        fputs ("+oo,", file);
217
      else
218
        fprintf (file, "" HOST_WIDEST_INT_PRINT_DEC ",", fedge->max_capacity);
219
    }
220
 
221
  if (fedge->is_rflow_valid)
222
    {
223
      if (fedge->rflow == CAP_INFINITY)
224
        fputs (" rflow=+oo.", file);
225
      else
226
        fprintf (file, " rflow=" HOST_WIDEST_INT_PRINT_DEC ",", fedge->rflow);
227
    }
228
 
229
  fprintf (file, " cost=" HOST_WIDEST_INT_PRINT_DEC ".", fedge->cost);
230
 
231
  fprintf (file, "\t(%d->%d)", fedge->src, fedge->dest);
232
 
233
  if (fedge->type)
234
    {
235
      switch (fedge->type)
236
        {
237
        case VERTEX_SPLIT_EDGE:
238
          fputs (" @VERTEX_SPLIT_EDGE", file);
239
          break;
240
 
241
        case REDIRECT_EDGE:
242
          fputs (" @REDIRECT_EDGE", file);
243
          break;
244
 
245
        case SOURCE_CONNECT_EDGE:
246
          fputs (" @SOURCE_CONNECT_EDGE", file);
247
          break;
248
 
249
        case SINK_CONNECT_EDGE:
250
          fputs (" @SINK_CONNECT_EDGE", file);
251
          break;
252
 
253
        case REVERSE_EDGE:
254
          fputs (" @REVERSE_EDGE", file);
255
          break;
256
 
257
        case BALANCE_EDGE:
258
          fputs (" @BALANCE_EDGE", file);
259
          break;
260
 
261
        case REDIRECT_NORMALIZED_EDGE:
262
        case REVERSE_NORMALIZED_EDGE:
263
          fputs ("  @NORMALIZED_EDGE", file);
264
          break;
265
 
266
        default:
267
          fputs (" @INVALID_EDGE", file);
268
          break;
269
        }
270
    }
271
  fputs ("\n", file);
272
}
273
 
274
 
275
/* Print out the edges and vertices of the given FIXUP_GRAPH, into the dump
276
   file. The input string MSG is printed out as a heading.  */
277
 
278
static void
279
dump_fixup_graph (FILE *file, fixup_graph_type *fixup_graph, const char *msg)
280
{
281
  int i, j;
282
  int fnum_vertices, fnum_edges;
283
 
284
  fixup_vertex_p fvertex_list, pfvertex;
285
  fixup_edge_p pfedge;
286
 
287
  gcc_assert (fixup_graph);
288
  fvertex_list = fixup_graph->vertex_list;
289
  fnum_vertices = fixup_graph->num_vertices;
290
  fnum_edges = fixup_graph->num_edges;
291
 
292
  fprintf (file, "\nDump fixup graph for %s(): %s.\n",
293
           lang_hooks.decl_printable_name (current_function_decl, 2), msg);
294
  fprintf (file,
295
           "There are %d vertices and %d edges. new_exit_index is %d.\n\n",
296
           fnum_vertices, fnum_edges, fixup_graph->new_exit_index);
297
 
298
  for (i = 0; i < fnum_vertices; i++)
299
    {
300
      pfvertex = fvertex_list + i;
301
      fprintf (file, "vertex_list[%d]: %d succ fixup edges.\n",
302
               i, VEC_length (fixup_edge_p, pfvertex->succ_edges));
303
 
304
      for (j = 0; VEC_iterate (fixup_edge_p, pfvertex->succ_edges, j, pfedge);
305
           j++)
306
        {
307
          /* Distinguish forward edges and backward edges in the residual flow
308
             network.  */
309
          if (pfedge->type)
310
            fputs ("(f) ", file);
311
          else if (pfedge->is_rflow_valid)
312
            fputs ("(b) ", file);
313
          dump_fixup_edge (file, fixup_graph, pfedge);
314
        }
315
    }
316
 
317
  fputs ("\n", file);
318
}
319
 
320
 
321
/* Utility routines.  */
322
/* ln() implementation: approximate calculation. Returns ln of X.  */
323
 
324
static double
325
mcf_ln (double x)
326
{
327
#define E       2.71828
328
  int l = 1;
329
  double m = E;
330
 
331
  gcc_assert (x >= 0);
332
 
333
  while (m < x)
334
    {
335
      m *= E;
336
      l++;
337
    }
338
 
339
  return l;
340
}
341
 
342
 
343
/* sqrt() implementation: based on open source QUAKE3 code (magic sqrt
344
   implementation) by John Carmack.  Returns sqrt of X.  */
345
 
346
static double
347
mcf_sqrt (double x)
348
{
349
#define MAGIC_CONST1    0x1fbcf800
350
#define MAGIC_CONST2    0x5f3759df
351
  union {
352
    int intPart;
353
    float floatPart;
354
  } convertor, convertor2;
355
 
356
  gcc_assert (x >= 0);
357
 
358
  convertor.floatPart = x;
359
  convertor2.floatPart = x;
360
  convertor.intPart = MAGIC_CONST1 + (convertor.intPart >> 1);
361
  convertor2.intPart = MAGIC_CONST2 - (convertor2.intPart >> 1);
362
 
363
  return 0.5f * (convertor.floatPart + (x * convertor2.floatPart));
364
}
365
 
366
 
367
/* Common code shared between add_fixup_edge and add_rfixup_edge. Adds an edge
368
   (SRC->DEST) to the edge_list maintained in FIXUP_GRAPH with cost of the edge
369
   added set to COST.  */
370
 
371
static fixup_edge_p
372
add_edge (fixup_graph_type *fixup_graph, int src, int dest, gcov_type cost)
373
{
374
  fixup_vertex_p curr_vertex = fixup_graph->vertex_list + src;
375
  fixup_edge_p curr_edge = fixup_graph->edge_list + fixup_graph->num_edges;
376
  curr_edge->src = src;
377
  curr_edge->dest = dest;
378
  curr_edge->cost = cost;
379
  fixup_graph->num_edges++;
380
  if (dump_file)
381
    dump_fixup_edge (dump_file, fixup_graph, curr_edge);
382
  VEC_safe_push (fixup_edge_p, heap, curr_vertex->succ_edges, curr_edge);
383
  return curr_edge;
384
}
385
 
386
 
387
/* Add a fixup edge (src->dest) with attributes TYPE, WEIGHT, COST and
388
   MAX_CAPACITY to the edge_list in the fixup graph.  */
389
 
390
static void
391
add_fixup_edge (fixup_graph_type *fixup_graph, int src, int dest,
392
                edge_type type, gcov_type weight, gcov_type cost,
393
                gcov_type max_capacity)
394
{
395
  fixup_edge_p curr_edge = add_edge(fixup_graph, src, dest, cost);
396
  curr_edge->type = type;
397
  curr_edge->weight = weight;
398
  curr_edge->max_capacity = max_capacity;
399
}
400
 
401
 
402
/* Add a residual edge (SRC->DEST) with attributes RFLOW and COST
403
   to the fixup graph.  */
404
 
405
static void
406
add_rfixup_edge (fixup_graph_type *fixup_graph, int src, int dest,
407
                 gcov_type rflow, gcov_type cost)
408
{
409
  fixup_edge_p curr_edge = add_edge (fixup_graph, src, dest, cost);
410
  curr_edge->rflow = rflow;
411
  curr_edge->is_rflow_valid = true;
412
  /* This edge is not a valid edge - merely used to hold residual flow.  */
413
  curr_edge->type = INVALID_EDGE;
414
}
415
 
416
 
417
/* Return the pointer to fixup edge SRC->DEST or NULL if edge does not
418
   exist in the FIXUP_GRAPH.  */
419
 
420
static fixup_edge_p
421
find_fixup_edge (fixup_graph_type *fixup_graph, int src, int dest)
422
{
423
  int j;
424
  fixup_edge_p pfedge;
425
  fixup_vertex_p pfvertex;
426
 
427
  gcc_assert (src < fixup_graph->num_vertices);
428
 
429
  pfvertex = fixup_graph->vertex_list + src;
430
 
431
  for (j = 0; VEC_iterate (fixup_edge_p, pfvertex->succ_edges, j, pfedge);
432
       j++)
433
    if (pfedge->dest == dest)
434
      return pfedge;
435
 
436
  return NULL;
437
}
438
 
439
 
440
/* Cleanup routine to free structures in FIXUP_GRAPH.  */
441
 
442
static void
443
delete_fixup_graph (fixup_graph_type *fixup_graph)
444
{
445
  int i;
446
  int fnum_vertices = fixup_graph->num_vertices;
447
  fixup_vertex_p pfvertex = fixup_graph->vertex_list;
448
 
449
  for (i = 0; i < fnum_vertices; i++, pfvertex++)
450
    VEC_free (fixup_edge_p, heap, pfvertex->succ_edges);
451
 
452
  free (fixup_graph->vertex_list);
453
  free (fixup_graph->edge_list);
454
}
455
 
456
 
457
/* Creates a fixup graph FIXUP_GRAPH from the function CFG.  */
458
 
459
static void
460
create_fixup_graph (fixup_graph_type *fixup_graph)
461
{
462
  double sqrt_avg_vertex_weight = 0;
463
  double total_vertex_weight = 0;
464
  double k_pos = 0;
465
  double k_neg = 0;
466
  /* Vector to hold D(v) = sum_out_edges(v) - sum_in_edges(v).  */
467
  gcov_type *diff_out_in = NULL;
468
  gcov_type supply_value = 1, demand_value = 0;
469
  gcov_type fcost = 0;
470
  int new_entry_index = 0, new_exit_index = 0;
471
  int i = 0, j = 0;
472
  int new_index = 0;
473
  basic_block bb;
474
  edge e;
475
  edge_iterator ei;
476
  fixup_edge_p pfedge, r_pfedge;
477
  fixup_edge_p fedge_list;
478
  int fnum_edges;
479
 
480
  /* Each basic_block will be split into 2 during vertex transformation.  */
481
  int fnum_vertices_after_transform =  2 * n_basic_blocks;
482
  int fnum_edges_after_transform = n_edges + n_basic_blocks;
483
 
484
  /* Count the new SOURCE and EXIT vertices to be added.  */
485
  int fmax_num_vertices =
486
    fnum_vertices_after_transform + n_edges + n_basic_blocks + 2;
487
 
488
  /* In create_fixup_graph: Each basic block and edge can be split into 3
489
     edges. Number of balance edges = n_basic_blocks. So after
490
     create_fixup_graph:
491
     max_edges = 4 * n_basic_blocks + 3 * n_edges
492
     Accounting for residual flow edges
493
     max_edges = 2 * (4 * n_basic_blocks + 3 * n_edges)
494
     = 8 * n_basic_blocks + 6 * n_edges
495
     < 8 * n_basic_blocks + 8 * n_edges.  */
496
  int fmax_num_edges = 8 * (n_basic_blocks + n_edges);
497
 
498
  /* Initial num of vertices in the fixup graph.  */
499
  fixup_graph->num_vertices = n_basic_blocks;
500
 
501
  /* Fixup graph vertex list.  */
502
  fixup_graph->vertex_list =
503
    (fixup_vertex_p) xcalloc (fmax_num_vertices, sizeof (fixup_vertex_type));
504
 
505
  /* Fixup graph edge list.  */
506
  fixup_graph->edge_list =
507
    (fixup_edge_p) xcalloc (fmax_num_edges, sizeof (fixup_edge_type));
508
 
509
  diff_out_in =
510
    (gcov_type *) xcalloc (1 + fnum_vertices_after_transform,
511
                           sizeof (gcov_type));
512
 
513
  /* Compute constants b, k_pos, k_neg used in the cost function calculation.
514
     b = sqrt(avg_vertex_weight(cfg)); k_pos = b; k_neg = 50b.  */
515
  FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
516
    total_vertex_weight += bb->count;
517
 
518
  sqrt_avg_vertex_weight = mcf_sqrt (total_vertex_weight / n_basic_blocks);
519
 
520
  k_pos = K_POS (sqrt_avg_vertex_weight);
521
  k_neg = K_NEG (sqrt_avg_vertex_weight);
522
 
523
  /* 1. Vertex Transformation: Split each vertex v into two vertices v' and v'',
524
     connected by an edge e from v' to v''. w(e) = w(v).  */
525
 
526
  if (dump_file)
527
    fprintf (dump_file, "\nVertex transformation:\n");
528
 
529
  FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
530
  {
531
    /* v'->v'': index1->(index1+1).  */
532
    i = 2 * bb->index;
533
    fcost = (gcov_type) COST (k_pos, bb->count);
534
    add_fixup_edge (fixup_graph, i, i + 1, VERTEX_SPLIT_EDGE, bb->count,
535
                    fcost, CAP_INFINITY);
536
    fixup_graph->num_vertices++;
537
 
538
    FOR_EACH_EDGE (e, ei, bb->succs)
539
    {
540
      /* Edges with ignore attribute set should be treated like they don't
541
         exist.  */
542
      if (EDGE_INFO (e) && EDGE_INFO (e)->ignore)
543
        continue;
544
      j = 2 * e->dest->index;
545
      fcost = (gcov_type) COST (k_pos, e->count);
546
      add_fixup_edge (fixup_graph, i + 1, j, REDIRECT_EDGE, e->count, fcost,
547
                      CAP_INFINITY);
548
    }
549
  }
550
 
551
  /* After vertex transformation.  */
552
  gcc_assert (fixup_graph->num_vertices == fnum_vertices_after_transform);
553
  /* Redirect edges are not added for edges with ignore attribute.  */
554
  gcc_assert (fixup_graph->num_edges <= fnum_edges_after_transform);
555
 
556
  fnum_edges_after_transform = fixup_graph->num_edges;
557
 
558
  /* 2. Initialize D(v).  */
559
  for (i = 0; i < fnum_edges_after_transform; i++)
560
    {
561
      pfedge = fixup_graph->edge_list + i;
562
      diff_out_in[pfedge->src] += pfedge->weight;
563
      diff_out_in[pfedge->dest] -= pfedge->weight;
564
    }
565
 
566
  /* Entry block - vertex indices 0, 1; EXIT block - vertex indices 2, 3.  */
567
  for (i = 0; i <= 3; i++)
568
    diff_out_in[i] = 0;
569
 
570
  /* 3. Add reverse edges: needed to decrease counts during smoothing.  */
571
  if (dump_file)
572
    fprintf (dump_file, "\nReverse edges:\n");
573
  for (i = 0; i < fnum_edges_after_transform; i++)
574
    {
575
      pfedge = fixup_graph->edge_list + i;
576
      if ((pfedge->src == 0) || (pfedge->src == 2))
577
        continue;
578
      r_pfedge = find_fixup_edge (fixup_graph, pfedge->dest, pfedge->src);
579
      if (!r_pfedge && pfedge->weight)
580
        {
581
          /* Skip adding reverse edges for edges with w(e) = 0, as its maximum
582
             capacity is 0.  */
583
          fcost = (gcov_type) COST (k_neg, pfedge->weight);
584
          add_fixup_edge (fixup_graph, pfedge->dest, pfedge->src,
585
                          REVERSE_EDGE, 0, fcost, pfedge->weight);
586
        }
587
    }
588
 
589
  /* 4. Create single source and sink. Connect new source vertex s' to function
590
     entry block. Connect sink vertex t' to function exit.  */
591
  if (dump_file)
592
    fprintf (dump_file, "\ns'->S, T->t':\n");
593
 
594
  new_entry_index = fixup_graph->new_entry_index = fixup_graph->num_vertices;
595
  fixup_graph->num_vertices++;
596
  /* Set supply_value to 1 to avoid zero count function ENTRY.  */
597
  add_fixup_edge (fixup_graph, new_entry_index, ENTRY_BLOCK, SOURCE_CONNECT_EDGE,
598
                  1 /* supply_value */, 0, 1 /* supply_value */);
599
 
600
  /* Create new exit with EXIT_BLOCK as single pred.  */
601
  new_exit_index = fixup_graph->new_exit_index = fixup_graph->num_vertices;
602
  fixup_graph->num_vertices++;
603
  add_fixup_edge (fixup_graph, 2 * EXIT_BLOCK + 1, new_exit_index,
604
                  SINK_CONNECT_EDGE,
605
 
606
 
607
  /* Connect vertices with unbalanced D(v) to source/sink.  */
608
  if (dump_file)
609
    fprintf (dump_file, "\nD(v) balance:\n");
610
  /* Skip vertices for ENTRY (0, 1) and EXIT (2,3) blocks, so start with i = 4.
611
     diff_out_in[v''] will be 0, so skip v'' vertices, hence i += 2.  */
612
  for (i = 4; i < new_entry_index; i += 2)
613
    {
614
      if (diff_out_in[i] > 0)
615
        {
616
          add_fixup_edge (fixup_graph, i, new_exit_index, BALANCE_EDGE, 0, 0,
617
                          diff_out_in[i]);
618
          demand_value += diff_out_in[i];
619
        }
620
      else if (diff_out_in[i] < 0)
621
        {
622
          add_fixup_edge (fixup_graph, new_entry_index, i, BALANCE_EDGE, 0, 0,
623
                          -diff_out_in[i]);
624
          supply_value -= diff_out_in[i];
625
        }
626
    }
627
 
628
  /* Set supply = demand.  */
629
  if (dump_file)
630
    {
631
      fprintf (dump_file, "\nAdjust supply and demand:\n");
632
      fprintf (dump_file, "supply_value=" HOST_WIDEST_INT_PRINT_DEC "\n",
633
               supply_value);
634
      fprintf (dump_file, "demand_value=" HOST_WIDEST_INT_PRINT_DEC "\n",
635
               demand_value);
636
    }
637
 
638
  if (demand_value > supply_value)
639
    {
640
      pfedge = find_fixup_edge (fixup_graph, new_entry_index, ENTRY_BLOCK);
641
      pfedge->max_capacity += (demand_value - supply_value);
642
    }
643
  else
644
    {
645
      pfedge = find_fixup_edge (fixup_graph, 2 * EXIT_BLOCK + 1, new_exit_index);
646
      pfedge->max_capacity += (supply_value - demand_value);
647
    }
648
 
649
  /* 6. Normalize edges: remove anti-parallel edges. Anti-parallel edges are
650
     created by the vertex transformation step from self-edges in the original
651
     CFG and by the reverse edges added earlier.  */
652
  if (dump_file)
653
    fprintf (dump_file, "\nNormalize edges:\n");
654
 
655
  fnum_edges = fixup_graph->num_edges;
656
  fedge_list = fixup_graph->edge_list;
657
 
658
  for (i = 0; i < fnum_edges; i++)
659
    {
660
      pfedge = fedge_list + i;
661
      r_pfedge = find_fixup_edge (fixup_graph, pfedge->dest, pfedge->src);
662
      if (((pfedge->type == VERTEX_SPLIT_EDGE)
663
           || (pfedge->type == REDIRECT_EDGE)) && r_pfedge)
664
        {
665
          new_index = fixup_graph->num_vertices;
666
          fixup_graph->num_vertices++;
667
 
668
          if (dump_file)
669
            {
670
              fprintf (dump_file, "\nAnti-parallel edge:\n");
671
              dump_fixup_edge (dump_file, fixup_graph, pfedge);
672
              dump_fixup_edge (dump_file, fixup_graph, r_pfedge);
673
              fprintf (dump_file, "New vertex is %d.\n", new_index);
674
              fprintf (dump_file, "------------------\n");
675
            }
676
 
677
          pfedge->cost /= 2;
678
          pfedge->norm_vertex_index = new_index;
679
          if (dump_file)
680
            {
681
              fprintf (dump_file, "After normalization:\n");
682
              dump_fixup_edge (dump_file, fixup_graph, pfedge);
683
            }
684
 
685
          /* Add a new fixup edge: new_index->src.  */
686
          add_fixup_edge (fixup_graph, new_index, pfedge->src,
687
                          REVERSE_NORMALIZED_EDGE, 0, r_pfedge->cost,
688
                          r_pfedge->max_capacity);
689
          gcc_assert (fixup_graph->num_vertices <= fmax_num_vertices);
690
 
691
          /* Edge: r_pfedge->src -> r_pfedge->dest
692
             ==> r_pfedge->src -> new_index.  */
693
          r_pfedge->dest = new_index;
694
          r_pfedge->type = REVERSE_NORMALIZED_EDGE;
695
          r_pfedge->cost = pfedge->cost;
696
          r_pfedge->max_capacity = pfedge->max_capacity;
697
          if (dump_file)
698
            dump_fixup_edge (dump_file, fixup_graph, r_pfedge);
699
        }
700
    }
701
 
702
  if (dump_file)
703
    dump_fixup_graph (dump_file, fixup_graph, "After create_fixup_graph()");
704
 
705
  /* Cleanup.  */
706
  free (diff_out_in);
707
}
708
 
709
 
710
/* Allocates space for the structures in AUGMENTING_PATH.  The space needed is
711
   proportional to the number of nodes in the graph, which is given by
712
   GRAPH_SIZE.  */
713
 
714
static void
715
init_augmenting_path (augmenting_path_type *augmenting_path, int graph_size)
716
{
717
  augmenting_path->queue_list.queue = (int *)
718
    xcalloc (graph_size + 2, sizeof (int));
719
  augmenting_path->queue_list.size = graph_size + 2;
720
  augmenting_path->bb_pred = (int *) xcalloc (graph_size, sizeof (int));
721
  augmenting_path->is_visited = (int *) xcalloc (graph_size, sizeof (int));
722
}
723
 
724
/* Free the structures in AUGMENTING_PATH.  */
725
static void
726
free_augmenting_path (augmenting_path_type *augmenting_path)
727
{
728
  free (augmenting_path->queue_list.queue);
729
  free (augmenting_path->bb_pred);
730
  free (augmenting_path->is_visited);
731
}
732
 
733
 
734
/* Queue routines. Assumes queue will never overflow.  */
735
 
736
static void
737
init_queue (queue_type *queue_list)
738
{
739
  gcc_assert (queue_list);
740
  queue_list->head = 0;
741
  queue_list->tail = 0;
742
}
743
 
744
/* Return true if QUEUE_LIST is empty.  */
745
static bool
746
is_empty (queue_type *queue_list)
747
{
748
  return (queue_list->head == queue_list->tail);
749
}
750
 
751
/* Insert element X into QUEUE_LIST.  */
752
static void
753
enqueue (queue_type *queue_list, int x)
754
{
755
  gcc_assert (queue_list->tail < queue_list->size);
756
  queue_list->queue[queue_list->tail] = x;
757
  (queue_list->tail)++;
758
}
759
 
760
/* Return the first element in QUEUE_LIST.  */
761
static int
762
dequeue (queue_type *queue_list)
763
{
764
  int x;
765
  gcc_assert (queue_list->head >= 0);
766
  x = queue_list->queue[queue_list->head];
767
  (queue_list->head)++;
768
  return x;
769
}
770
 
771
 
772
/* Finds a negative cycle in the residual network using
773
   the Bellman-Ford algorithm. The flow on the found cycle is reversed by the
774
   minimum residual capacity of that cycle. ENTRY and EXIT vertices are not
775
   considered.
776
 
777
Parameters:
778
   FIXUP_GRAPH - Residual graph  (input/output)
779
   The following are allocated/freed by the caller:
780
   PI - Vector to hold predecessors in path  (pi = pred index)
781
   D - D[I] holds minimum cost of path from i to sink
782
   CYCLE - Vector to hold the minimum cost cycle
783
 
784
Return:
785
   true if a negative cycle was found, false otherwise.  */
786
 
787
static bool
788
cancel_negative_cycle (fixup_graph_type *fixup_graph,
789
                       int *pi, gcov_type *d, int *cycle)
790
{
791
  int i, j, k;
792
  int fnum_vertices, fnum_edges;
793
  fixup_edge_p fedge_list, pfedge, r_pfedge;
794
  bool found_cycle = false;
795
  int cycle_start = 0, cycle_end = 0;
796
  gcov_type sum_cost = 0, cycle_flow = 0;
797
  int new_entry_index;
798
  bool propagated = false;
799
 
800
  gcc_assert (fixup_graph);
801
  fnum_vertices = fixup_graph->num_vertices;
802
  fnum_edges = fixup_graph->num_edges;
803
  fedge_list = fixup_graph->edge_list;
804
  new_entry_index = fixup_graph->new_entry_index;
805
 
806
  /* Initialize.  */
807
  /* Skip ENTRY.  */
808
  for (i = 1; i < fnum_vertices; i++)
809
    {
810
      d[i] = CAP_INFINITY;
811
      pi[i] = -1;
812
      cycle[i] = -1;
813
    }
814
  d[ENTRY_BLOCK] = 0;
815
 
816
  /* Relax.  */
817
  for (k = 1; k < fnum_vertices; k++)
818
  {
819
    propagated = false;
820
    for (i = 0; i < fnum_edges; i++)
821
      {
822
        pfedge = fedge_list + i;
823
        if (pfedge->src == new_entry_index)
824
          continue;
825
        if (pfedge->is_rflow_valid && pfedge->rflow
826
            && d[pfedge->src] != CAP_INFINITY
827
            && (d[pfedge->dest] > d[pfedge->src] + pfedge->cost))
828
          {
829
            d[pfedge->dest] = d[pfedge->src] + pfedge->cost;
830
            pi[pfedge->dest] = pfedge->src;
831
            propagated = true;
832
          }
833
      }
834
    if (!propagated)
835
      break;
836
  }
837
 
838
  if (!propagated)
839
  /* No negative cycles exist.  */
840
    return 0;
841
 
842
  /* Detect.  */
843
  for (i = 0; i < fnum_edges; i++)
844
    {
845
      pfedge = fedge_list + i;
846
      if (pfedge->src == new_entry_index)
847
        continue;
848
      if (pfedge->is_rflow_valid && pfedge->rflow
849
          && d[pfedge->src] != CAP_INFINITY
850
          && (d[pfedge->dest] > d[pfedge->src] + pfedge->cost))
851
        {
852
          found_cycle = true;
853
          break;
854
        }
855
    }
856
 
857
  if (!found_cycle)
858
    return 0;
859
 
860
  /* Augment the cycle with the cycle's minimum residual capacity.  */
861
  found_cycle = false;
862
  cycle[0] = pfedge->dest;
863
  j = pfedge->dest;
864
 
865
  for (i = 1; i < fnum_vertices; i++)
866
    {
867
      j = pi[j];
868
      cycle[i] = j;
869
      for (k = 0; k < i; k++)
870
        {
871
          if (cycle[k] == j)
872
            {
873
              /* cycle[k] -> ... -> cycle[i].  */
874
              cycle_start = k;
875
              cycle_end = i;
876
              found_cycle = true;
877
              break;
878
            }
879
        }
880
      if (found_cycle)
881
        break;
882
    }
883
 
884
  gcc_assert (cycle[cycle_start] == cycle[cycle_end]);
885
  if (dump_file)
886
    fprintf (dump_file, "\nNegative cycle length is %d:\n",
887
             cycle_end - cycle_start);
888
 
889
  sum_cost = 0;
890
  cycle_flow = CAP_INFINITY;
891
  for (k = cycle_start; k < cycle_end; k++)
892
    {
893
      pfedge = find_fixup_edge (fixup_graph, cycle[k + 1], cycle[k]);
894
      cycle_flow = MIN (cycle_flow, pfedge->rflow);
895
      sum_cost += pfedge->cost;
896
      if (dump_file)
897
        fprintf (dump_file, "%d ", cycle[k]);
898
    }
899
 
900
  if (dump_file)
901
    {
902
      fprintf (dump_file, "%d", cycle[k]);
903
      fprintf (dump_file,
904
               ": (" HOST_WIDEST_INT_PRINT_DEC ", " HOST_WIDEST_INT_PRINT_DEC
905
               ")\n", sum_cost, cycle_flow);
906
      fprintf (dump_file,
907
               "Augment cycle with " HOST_WIDEST_INT_PRINT_DEC "\n",
908
               cycle_flow);
909
    }
910
 
911
  for (k = cycle_start; k < cycle_end; k++)
912
    {
913
      pfedge = find_fixup_edge (fixup_graph, cycle[k + 1], cycle[k]);
914
      r_pfedge = find_fixup_edge (fixup_graph, cycle[k], cycle[k + 1]);
915
      pfedge->rflow -= cycle_flow;
916
      if (pfedge->type)
917
        pfedge->flow += cycle_flow;
918
      r_pfedge->rflow += cycle_flow;
919
      if (r_pfedge->type)
920
        r_pfedge->flow -= cycle_flow;
921
    }
922
 
923
  return true;
924
}
925
 
926
 
927
/* Computes the residual flow for FIXUP_GRAPH by setting the rflow field of
928
   the edges. ENTRY and EXIT vertices should not be considered.  */
929
 
930
static void
931
compute_residual_flow (fixup_graph_type *fixup_graph)
932
{
933
  int i;
934
  int fnum_edges;
935
  fixup_edge_p fedge_list, pfedge;
936
 
937
  gcc_assert (fixup_graph);
938
 
939
  if (dump_file)
940
    fputs ("\ncompute_residual_flow():\n", dump_file);
941
 
942
  fnum_edges = fixup_graph->num_edges;
943
  fedge_list = fixup_graph->edge_list;
944
 
945
  for (i = 0; i < fnum_edges; i++)
946
    {
947
      pfedge = fedge_list + i;
948
      pfedge->rflow = pfedge->max_capacity - pfedge->flow;
949
      pfedge->is_rflow_valid = true;
950
      add_rfixup_edge (fixup_graph, pfedge->dest, pfedge->src, pfedge->flow,
951
                       -pfedge->cost);
952
    }
953
}
954
 
955
 
956
/* Uses Edmonds-Karp algorithm - BFS to find augmenting path from SOURCE to
957
   SINK. The fields in the edge vector in the FIXUP_GRAPH are not modified by
958
   this routine. The vector bb_pred in the AUGMENTING_PATH structure is updated
959
   to reflect the path found.
960
   Returns: 0 if no augmenting path is found, 1 otherwise.  */
961
 
962
static int
963
find_augmenting_path (fixup_graph_type *fixup_graph,
964
                      augmenting_path_type *augmenting_path, int source,
965
                      int sink)
966
{
967
  int u = 0;
968
  int i;
969
  fixup_vertex_p fvertex_list, pfvertex;
970
  fixup_edge_p pfedge;
971
  int *bb_pred, *is_visited;
972
  queue_type *queue_list;
973
 
974
  gcc_assert (augmenting_path);
975
  bb_pred = augmenting_path->bb_pred;
976
  gcc_assert (bb_pred);
977
  is_visited = augmenting_path->is_visited;
978
  gcc_assert (is_visited);
979
  queue_list = &(augmenting_path->queue_list);
980
 
981
  gcc_assert (fixup_graph);
982
 
983
  fvertex_list = fixup_graph->vertex_list;
984
 
985
  for (u = 0; u < fixup_graph->num_vertices; u++)
986
    is_visited[u] = 0;
987
 
988
  init_queue (queue_list);
989
  enqueue (queue_list, source);
990
  bb_pred[source] = -1;
991
 
992
  while (!is_empty (queue_list))
993
    {
994
      u = dequeue (queue_list);
995
      is_visited[u] = 1;
996
      pfvertex = fvertex_list + u;
997
      for (i = 0; VEC_iterate (fixup_edge_p, pfvertex->succ_edges, i, pfedge);
998
           i++)
999
        {
1000
          int dest = pfedge->dest;
1001
          if ((pfedge->rflow > 0) && (is_visited[dest] == 0))
1002
            {
1003
              enqueue (queue_list, dest);
1004
              bb_pred[dest] = u;
1005
              is_visited[dest] = 1;
1006
              if (dest == sink)
1007
                return 1;
1008
            }
1009
        }
1010
    }
1011
 
1012
  return 0;
1013
}
1014
 
1015
 
1016
/* Routine to find the maximal flow:
1017
   Algorithm:
1018
   1. Initialize flow to 0
1019
   2. Find an augmenting path form source to sink.
1020
   3. Send flow equal to the path's residual capacity along the edges of this path.
1021
   4. Repeat steps 2 and 3 until no new augmenting path is found.
1022
 
1023
Parameters:
1024
SOURCE: index of source vertex (input)
1025
SINK: index of sink vertex    (input)
1026
FIXUP_GRAPH: adjacency matrix representing the graph. The flow of the edges will be
1027
             set to have a valid maximal flow by this routine. (input)
1028
Return: Maximum flow possible.  */
1029
 
1030
static gcov_type
1031
find_max_flow (fixup_graph_type *fixup_graph, int source, int sink)
1032
{
1033
  int fnum_edges;
1034
  augmenting_path_type augmenting_path;
1035
  int *bb_pred;
1036
  gcov_type max_flow = 0;
1037
  int i, u;
1038
  fixup_edge_p fedge_list, pfedge, r_pfedge;
1039
 
1040
  gcc_assert (fixup_graph);
1041
 
1042
  fnum_edges = fixup_graph->num_edges;
1043
  fedge_list = fixup_graph->edge_list;
1044
 
1045
  /* Initialize flow to 0.  */
1046
  for (i = 0; i < fnum_edges; i++)
1047
    {
1048
      pfedge = fedge_list + i;
1049
      pfedge->flow = 0;
1050
    }
1051
 
1052
  compute_residual_flow (fixup_graph);
1053
 
1054
  init_augmenting_path (&augmenting_path, fixup_graph->num_vertices);
1055
 
1056
  bb_pred = augmenting_path.bb_pred;
1057
  while (find_augmenting_path (fixup_graph, &augmenting_path, source, sink))
1058
    {
1059
      /* Determine the amount by which we can increment the flow.  */
1060
      gcov_type increment = CAP_INFINITY;
1061
      for (u = sink; u != source; u = bb_pred[u])
1062
        {
1063
          pfedge = find_fixup_edge (fixup_graph, bb_pred[u], u);
1064
          increment = MIN (increment, pfedge->rflow);
1065
        }
1066
      max_flow += increment;
1067
 
1068
      /* Now increment the flow. EXIT vertex index is 1.  */
1069
      for (u = sink; u != source; u = bb_pred[u])
1070
        {
1071
          pfedge = find_fixup_edge (fixup_graph, bb_pred[u], u);
1072
          r_pfedge = find_fixup_edge (fixup_graph, u, bb_pred[u]);
1073
          if (pfedge->type)
1074
            {
1075
              /* forward edge.  */
1076
              pfedge->flow += increment;
1077
              pfedge->rflow -= increment;
1078
              r_pfedge->rflow += increment;
1079
            }
1080
          else
1081
            {
1082
              /* backward edge.  */
1083
              gcc_assert (r_pfedge->type);
1084
              r_pfedge->rflow += increment;
1085
              r_pfedge->flow -= increment;
1086
              pfedge->rflow -= increment;
1087
            }
1088
        }
1089
 
1090
      if (dump_file)
1091
        {
1092
          fprintf (dump_file, "\nDump augmenting path:\n");
1093
          for (u = sink; u != source; u = bb_pred[u])
1094
            {
1095
              print_basic_block (dump_file, fixup_graph, u);
1096
              fprintf (dump_file, "<-");
1097
            }
1098
          fprintf (dump_file,
1099
                   "ENTRY  (path_capacity=" HOST_WIDEST_INT_PRINT_DEC ")\n",
1100
                   increment);
1101
          fprintf (dump_file,
1102
                   "Network flow is " HOST_WIDEST_INT_PRINT_DEC ".\n",
1103
                   max_flow);
1104
        }
1105
    }
1106
 
1107
  free_augmenting_path (&augmenting_path);
1108
  if (dump_file)
1109
    dump_fixup_graph (dump_file, fixup_graph, "After find_max_flow()");
1110
  return max_flow;
1111
}
1112
 
1113
 
1114
/* Computes the corrected edge and basic block weights using FIXUP_GRAPH
1115
   after applying the find_minimum_cost_flow() routine.  */
1116
 
1117
static void
1118
adjust_cfg_counts (fixup_graph_type *fixup_graph)
1119
{
1120
  basic_block bb;
1121
  edge e;
1122
  edge_iterator ei;
1123
  int i, j;
1124
  fixup_edge_p pfedge, pfedge_n;
1125
 
1126
  gcc_assert (fixup_graph);
1127
 
1128
  if (dump_file)
1129
    fprintf (dump_file, "\nadjust_cfg_counts():\n");
1130
 
1131
  FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
1132
    {
1133
      i = 2 * bb->index;
1134
 
1135
      /* Fixup BB.  */
1136
      if (dump_file)
1137
        fprintf (dump_file,
1138
                 "BB%d: " HOST_WIDEST_INT_PRINT_DEC "", bb->index, bb->count);
1139
 
1140
      pfedge = find_fixup_edge (fixup_graph, i, i + 1);
1141
      if (pfedge->flow)
1142
        {
1143
          bb->count += pfedge->flow;
1144
          if (dump_file)
1145
            {
1146
              fprintf (dump_file, " + " HOST_WIDEST_INT_PRINT_DEC "(",
1147
                       pfedge->flow);
1148
              print_edge (dump_file, fixup_graph, i, i + 1);
1149
              fprintf (dump_file, ")");
1150
            }
1151
        }
1152
 
1153
      pfedge_n =
1154
        find_fixup_edge (fixup_graph, i + 1, pfedge->norm_vertex_index);
1155
      /* Deduct flow from normalized reverse edge.  */
1156
      if (pfedge->norm_vertex_index && pfedge_n->flow)
1157
        {
1158
          bb->count -= pfedge_n->flow;
1159
          if (dump_file)
1160
            {
1161
              fprintf (dump_file, " - " HOST_WIDEST_INT_PRINT_DEC "(",
1162
                       pfedge_n->flow);
1163
              print_edge (dump_file, fixup_graph, i + 1,
1164
                          pfedge->norm_vertex_index);
1165
              fprintf (dump_file, ")");
1166
            }
1167
        }
1168
      if (dump_file)
1169
        fprintf (dump_file, " = " HOST_WIDEST_INT_PRINT_DEC "\n", bb->count);
1170
 
1171
      /* Fixup edge.  */
1172
      FOR_EACH_EDGE (e, ei, bb->succs)
1173
        {
1174
          /* Treat edges with ignore attribute set as if they don't exist.  */
1175
          if (EDGE_INFO (e) && EDGE_INFO (e)->ignore)
1176
            continue;
1177
 
1178
          j = 2 * e->dest->index;
1179
          if (dump_file)
1180
            fprintf (dump_file, "%d->%d: " HOST_WIDEST_INT_PRINT_DEC "",
1181
                     bb->index, e->dest->index, e->count);
1182
 
1183
          pfedge = find_fixup_edge (fixup_graph, i + 1, j);
1184
 
1185
          if (bb->index != e->dest->index)
1186
            {
1187
              /* Non-self edge.  */
1188
              if (pfedge->flow)
1189
                {
1190
                  e->count += pfedge->flow;
1191
                  if (dump_file)
1192
                    {
1193
                      fprintf (dump_file, " + " HOST_WIDEST_INT_PRINT_DEC "(",
1194
                               pfedge->flow);
1195
                      print_edge (dump_file, fixup_graph, i + 1, j);
1196
                      fprintf (dump_file, ")");
1197
                    }
1198
                }
1199
 
1200
              pfedge_n =
1201
                find_fixup_edge (fixup_graph, j, pfedge->norm_vertex_index);
1202
              /* Deduct flow from normalized reverse edge.  */
1203
              if (pfedge->norm_vertex_index && pfedge_n->flow)
1204
                {
1205
                  e->count -= pfedge_n->flow;
1206
                  if (dump_file)
1207
                    {
1208
                      fprintf (dump_file, " - " HOST_WIDEST_INT_PRINT_DEC "(",
1209
                               pfedge_n->flow);
1210
                      print_edge (dump_file, fixup_graph, j,
1211
                                  pfedge->norm_vertex_index);
1212
                      fprintf (dump_file, ")");
1213
                    }
1214
                }
1215
            }
1216
          else
1217
            {
1218
              /* Handle self edges. Self edge is split with a normalization
1219
                 vertex. Here i=j.  */
1220
              pfedge = find_fixup_edge (fixup_graph, j, i + 1);
1221
              pfedge_n =
1222
                find_fixup_edge (fixup_graph, i + 1, pfedge->norm_vertex_index);
1223
              e->count += pfedge_n->flow;
1224
              bb->count += pfedge_n->flow;
1225
              if (dump_file)
1226
                {
1227
                  fprintf (dump_file, "(self edge)");
1228
                  fprintf (dump_file, " + " HOST_WIDEST_INT_PRINT_DEC "(",
1229
                           pfedge_n->flow);
1230
                  print_edge (dump_file, fixup_graph, i + 1,
1231
                              pfedge->norm_vertex_index);
1232
                  fprintf (dump_file, ")");
1233
                }
1234
            }
1235
 
1236
          if (bb->count)
1237
            e->probability = REG_BR_PROB_BASE * e->count / bb->count;
1238
          if (dump_file)
1239
            fprintf (dump_file, " = " HOST_WIDEST_INT_PRINT_DEC "\t(%.1f%%)\n",
1240
                     e->count, e->probability * 100.0 / REG_BR_PROB_BASE);
1241
        }
1242
    }
1243
 
1244
  ENTRY_BLOCK_PTR->count = sum_edge_counts (ENTRY_BLOCK_PTR->succs);
1245
  EXIT_BLOCK_PTR->count = sum_edge_counts (EXIT_BLOCK_PTR->preds);
1246
 
1247
  /* Compute edge probabilities.  */
1248
  FOR_ALL_BB (bb)
1249
    {
1250
      if (bb->count)
1251
        {
1252
          FOR_EACH_EDGE (e, ei, bb->succs)
1253
            e->probability = REG_BR_PROB_BASE * e->count / bb->count;
1254
        }
1255
      else
1256
        {
1257
          int total = 0;
1258
          FOR_EACH_EDGE (e, ei, bb->succs)
1259
            if (!(e->flags & (EDGE_COMPLEX | EDGE_FAKE)))
1260
              total++;
1261
          if (total)
1262
            {
1263
              FOR_EACH_EDGE (e, ei, bb->succs)
1264
                {
1265
                  if (!(e->flags & (EDGE_COMPLEX | EDGE_FAKE)))
1266
                    e->probability = REG_BR_PROB_BASE / total;
1267
                  else
1268
                    e->probability = 0;
1269
                }
1270
            }
1271
          else
1272
            {
1273
              total += EDGE_COUNT (bb->succs);
1274
              FOR_EACH_EDGE (e, ei, bb->succs)
1275
                  e->probability = REG_BR_PROB_BASE / total;
1276
            }
1277
        }
1278
    }
1279
 
1280
  if (dump_file)
1281
    {
1282
      fprintf (dump_file, "\nCheck %s() CFG flow conservation:\n",
1283
           lang_hooks.decl_printable_name (current_function_decl, 2));
1284
      FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR->next_bb, EXIT_BLOCK_PTR, next_bb)
1285
        {
1286
          if ((bb->count != sum_edge_counts (bb->preds))
1287
               || (bb->count != sum_edge_counts (bb->succs)))
1288
            {
1289
              fprintf (dump_file,
1290
                       "BB%d(" HOST_WIDEST_INT_PRINT_DEC ")  **INVALID**: ",
1291
                       bb->index, bb->count);
1292
              fprintf (stderr,
1293
                       "******** BB%d(" HOST_WIDEST_INT_PRINT_DEC
1294
                       ")  **INVALID**: \n", bb->index, bb->count);
1295
              fprintf (dump_file, "in_edges=" HOST_WIDEST_INT_PRINT_DEC " ",
1296
                       sum_edge_counts (bb->preds));
1297
              fprintf (dump_file, "out_edges=" HOST_WIDEST_INT_PRINT_DEC "\n",
1298
                       sum_edge_counts (bb->succs));
1299
            }
1300
         }
1301
    }
1302
}
1303
 
1304
 
1305
/* Implements the negative cycle canceling algorithm to compute a minimum cost
1306
   flow.
1307
Algorithm:
1308
1. Find maximal flow.
1309
2. Form residual network
1310
3. Repeat:
1311
  While G contains a negative cost cycle C, reverse the flow on the found cycle
1312
  by the minimum residual capacity in that cycle.
1313
4. Form the minimal cost flow
1314
  f(u,v) = rf(v, u)
1315
Input:
1316
  FIXUP_GRAPH - Initial fixup graph.
1317
  The flow field is modified to represent the minimum cost flow.  */
1318
 
1319
static void
1320
find_minimum_cost_flow (fixup_graph_type *fixup_graph)
1321
{
1322
  /* Holds the index of predecessor in path.  */
1323
  int *pred;
1324
  /* Used to hold the minimum cost cycle.  */
1325
  int *cycle;
1326
  /* Used to record the number of iterations of cancel_negative_cycle.  */
1327
  int iteration;
1328
  /* Vector d[i] holds the minimum cost of path from i to sink.  */
1329
  gcov_type *d;
1330
  int fnum_vertices;
1331
  int new_exit_index;
1332
  int new_entry_index;
1333
 
1334
  gcc_assert (fixup_graph);
1335
  fnum_vertices = fixup_graph->num_vertices;
1336
  new_exit_index = fixup_graph->new_exit_index;
1337
  new_entry_index = fixup_graph->new_entry_index;
1338
 
1339
  find_max_flow (fixup_graph, new_entry_index, new_exit_index);
1340
 
1341
  /* Initialize the structures for find_negative_cycle().  */
1342
  pred = (int *) xcalloc (fnum_vertices, sizeof (int));
1343
  d = (gcov_type *) xcalloc (fnum_vertices, sizeof (gcov_type));
1344
  cycle = (int *) xcalloc (fnum_vertices, sizeof (int));
1345
 
1346
  /* Repeatedly find and cancel negative cost cycles, until
1347
     no more negative cycles exist. This also updates the flow field
1348
     to represent the minimum cost flow so far.  */
1349
  iteration = 0;
1350
  while (cancel_negative_cycle (fixup_graph, pred, d, cycle))
1351
    {
1352
      iteration++;
1353
      if (iteration > MAX_ITER (fixup_graph->num_vertices,
1354
                                fixup_graph->num_edges))
1355
        break;
1356
    }
1357
 
1358
  if (dump_file)
1359
    dump_fixup_graph (dump_file, fixup_graph,
1360
                      "After find_minimum_cost_flow()");
1361
 
1362
  /* Cleanup structures.  */
1363
  free (pred);
1364
  free (d);
1365
  free (cycle);
1366
}
1367
 
1368
 
1369
/* Compute the sum of the edge counts in TO_EDGES.  */
1370
 
1371
gcov_type
1372
sum_edge_counts (VEC (edge, gc) *to_edges)
1373
{
1374
  gcov_type sum = 0;
1375
  edge e;
1376
  edge_iterator ei;
1377
 
1378
  FOR_EACH_EDGE (e, ei, to_edges)
1379
    {
1380
      if (EDGE_INFO (e) && EDGE_INFO (e)->ignore)
1381
        continue;
1382
      sum += e->count;
1383
    }
1384
  return sum;
1385
}
1386
 
1387
 
1388
/* Main routine. Smoothes the intial assigned basic block and edge counts using
1389
   a minimum cost flow algorithm, to ensure that the flow consistency rule is
1390
   obeyed: sum of outgoing edges = sum of incoming edges for each basic
1391
   block.  */
1392
 
1393
void
1394
mcf_smooth_cfg (void)
1395
{
1396
  fixup_graph_type fixup_graph;
1397
  memset (&fixup_graph, 0, sizeof (fixup_graph));
1398
  create_fixup_graph (&fixup_graph);
1399
  find_minimum_cost_flow (&fixup_graph);
1400
  adjust_cfg_counts (&fixup_graph);
1401
  delete_fixup_graph (&fixup_graph);
1402
}

powered by: WebSVN 2.1.0

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