Mercurial > hg > CbC > CbC_gcc
annotate gcc/mcf.c @ 55:77e2b8dfacca gcc-4.4.5
update it from 4.4.3 to 4.5.0
| author | ryoma <e075725@ie.u-ryukyu.ac.jp> |
|---|---|
| date | Fri, 12 Feb 2010 23:39:51 +0900 |
| parents | a06113de4d67 |
| children | 04ced10e8804 |
| rev | line source |
|---|---|
| 0 | 1 /* Routines to implement minimum-cost maximal flow algorithm used to smooth |
| 2 basic block and edge frequency counts. | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
3 Copyright (C) 2008, 2009 |
| 0 | 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 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
391 add_fixup_edge (fixup_graph_type *fixup_graph, int src, int dest, |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
392 edge_type type, gcov_type weight, gcov_type cost, |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
393 gcov_type max_capacity) |
| 0 | 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 0 /* demand_value */, 0, 0 /* demand_value */); | |
| 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. | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
1022 |
| 0 | 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 } | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
1242 } |
| 0 | 1243 |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
1244 ENTRY_BLOCK_PTR->count = sum_edge_counts (ENTRY_BLOCK_PTR->succs); |
| 0 | 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 } |