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