1 | /* Routines to implement minimum-cost maximal flow algorithm used to smooth |
---|---|

2 | basic block and edge frequency counts. |

3 | Copyright (C) 2008-2017 Free Software Foundation, Inc. |

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" |

48 | #include "backend.h" |

49 | #include "profile.h" |

50 | #include "dumpfile.h" |

51 | |

52 | /* CAP_INFINITY: Constant to represent infinite capacity. */ |

53 | #define CAP_INFINITY INTTYPE_MAXIMUM (int64_t) |

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))) |

62 | enum edge_type |

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. */ |

73 | }; |

74 | |

75 | /* Structure to represent an edge in the fixup graph. */ |

76 | struct fixup_edge_type |

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; |

92 | }; |

93 | |

94 | typedef fixup_edge_type *fixup_edge_p; |

95 | |

96 | |

97 | /* Structure to represent a vertex in the fixup graph. */ |

98 | struct fixup_vertex_type |

99 | { |

100 | vec<fixup_edge_p> succ_edges; |

101 | }; |

102 | |

103 | typedef fixup_vertex_type *fixup_vertex_p; |

104 | |

105 | /* Fixup graph used in the MCF algorithm. */ |

106 | struct fixup_graph_type |

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; |

120 | }; |

121 | |

122 | struct queue_type |

123 | { |

124 | int *queue; |

125 | int head; |

126 | int tail; |

127 | int size; |

128 | }; |

129 | |

130 | /* Structure used in the maximal flow routines to find augmenting path. */ |

131 | struct augmenting_path_type |

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; |

139 | }; |

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 | { |

205 | fprintf (file, "flow/capacity=%"PRId64 "/", |

206 | fedge->flow); |

207 | if (fedge->max_capacity == CAP_INFINITY) |

208 | fputs ("+oo,", file); |

209 | else |

210 | fprintf (file, "%"PRId64 ",", fedge->max_capacity); |

211 | } |

212 | |

213 | if (fedge->is_rflow_valid) |

214 | { |

215 | if (fedge->rflow == CAP_INFINITY) |

216 | fputs (" rflow=+oo.", file); |

217 | else |

218 | fprintf (file, " rflow=%"PRId64 ",", fedge->rflow); |

219 | } |

220 | |

221 | fprintf (file, " cost=%"PRId64 ".", fedge->cost); |

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", |

285 | current_function_name (), msg); |

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", |

294 | i, pfvertex->succ_edges.length ()); |

295 | |

296 | for (j = 0; pfvertex->succ_edges.iterate (j, &pfedge); |

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); |

374 | curr_vertex->succ_edges.safe_push (curr_edge); |

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 |

383 | add_fixup_edge (fixup_graph_type *fixup_graph, int src, int dest, |

384 | edge_type type, gcov_type weight, gcov_type cost, |

385 | gcov_type max_capacity) |

386 | { |

387 | fixup_edge_p curr_edge = add_edge (fixup_graph, src, dest, cost); |

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 | |

423 | for (j = 0; pfvertex->succ_edges.iterate (j, &pfedge); |

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++) |

442 | pfvertex->succ_edges.release (); |

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. */ |

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); |

476 | |

477 | /* Count the new SOURCE and EXIT vertices to be added. */ |

478 | int fmax_num_vertices = |

479 | (fnum_vertices_after_transform + n_edges_for_fn (cfun) |

480 | + n_basic_blocks_for_fn (cfun) + 2); |

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. */ |

490 | int fmax_num_edges = 8 * (n_basic_blocks_for_fn (cfun) + |

491 | n_edges_for_fn (cfun)); |

492 | |

493 | /* Initial num of vertices in the fixup graph. */ |

494 | fixup_graph->num_vertices = n_basic_blocks_for_fn (cfun); |

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. */ |

510 | FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb) |

511 | total_vertex_weight += bb_gcov_count (bb); |

512 | |

513 | sqrt_avg_vertex_weight = mcf_sqrt (total_vertex_weight / |

514 | n_basic_blocks_for_fn (cfun)); |

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 | |

525 | FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb) |

526 | { |

527 | /* v'->v'': index1->(index1+1). */ |

528 | i = 2 * bb->index; |

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), |

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; |

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); |

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"); |

628 | fprintf (dump_file, "supply_value=%"PRId64 "\n", |

629 | supply_value); |

630 | fprintf (dump_file, "demand_value=%"PRId64 "\n", |

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, |

900 | ": (%"PRId64 ", %"PRId64 |

901 | ")\n", sum_cost, cycle_flow); |

902 | fprintf (dump_file, |

903 | "Augment cycle with %"PRId64 "\n", |

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; |

993 | for (i = 0; pfvertex->succ_edges.iterate (i, &pfedge); |

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. |

1018 | |

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, |

1095 | "ENTRY (path_capacity=%"PRId64 ")\n", |

1096 | increment); |

1097 | fprintf (dump_file, |

1098 | "Network flow is %"PRId64 ".\n", |

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 | |

1127 | FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), |

1128 | EXIT_BLOCK_PTR_FOR_FN (cfun), next_bb) |

1129 | { |

1130 | i = 2 * bb->index; |

1131 | |

1132 | /* Fixup BB. */ |

1133 | if (dump_file) |

1134 | fprintf (dump_file, |

1135 | "BB%d: %"PRId64 "", bb->index, bb_gcov_count (bb)); |

1136 | |

1137 | pfedge = find_fixup_edge (fixup_graph, i, i + 1); |

1138 | if (pfedge->flow) |

1139 | { |

1140 | bb_gcov_count (bb) += pfedge->flow; |

1141 | if (dump_file) |

1142 | { |

1143 | fprintf (dump_file, " + %"PRId64 "(", |

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 | { |

1155 | bb_gcov_count (bb) -= pfedge_n->flow; |

1156 | if (dump_file) |

1157 | { |

1158 | fprintf (dump_file, " - %"PRId64 "(", |

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) |

1166 | fprintf (dump_file, " = %"PRId64 "\n", bb_gcov_count (bb)); |

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) |

1177 | fprintf (dump_file, "%d->%d: %"PRId64 "", |

1178 | bb->index, e->dest->index, edge_gcov_count (e)); |

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 | { |

1187 | edge_gcov_count (e) += pfedge->flow; |

1188 | if (dump_file) |

1189 | { |

1190 | fprintf (dump_file, " + %"PRId64 "(", |

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 | { |

1202 | edge_gcov_count (e) -= pfedge_n->flow; |

1203 | if (dump_file) |

1204 | { |

1205 | fprintf (dump_file, " - %"PRId64 "(", |

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); |

1220 | edge_gcov_count (e) += pfedge_n->flow; |

1221 | bb_gcov_count (bb) += pfedge_n->flow; |

1222 | if (dump_file) |

1223 | { |

1224 | fprintf (dump_file, "(self edge)"); |

1225 | fprintf (dump_file, " + %"PRId64 "(", |

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 | |

1233 | if (bb_gcov_count (bb)) |

1234 | e->probability = profile_probability::probability_in_gcov_type |

1235 | (edge_gcov_count (e), bb_gcov_count (bb)); |

1236 | if (dump_file) |

1237 | { |

1238 | fprintf (dump_file, " = %"PRId64 "\t", |

1239 | edge_gcov_count (e)); |

1240 | e->probability.dump (dump_file); |

1241 | fprintf (dump_file, "\n"); |

1242 | } |

1243 | } |

1244 | } |

1245 | |

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); |

1250 | |

1251 | /* Compute edge probabilities. */ |

1252 | FOR_ALL_BB_FN (bb, cfun) |

1253 | { |

1254 | if (bb_gcov_count (bb)) |

1255 | { |

1256 | FOR_EACH_EDGE (e, ei, bb->succs) |

1257 | e->probability = profile_probability::probability_in_gcov_type |

1258 | (edge_gcov_count (e), bb_gcov_count (bb)); |

1259 | } |

1260 | } |

1261 | |

1262 | if (dump_file) |

1263 | { |

1264 | fprintf (dump_file, "\nCheck %s() CFG flow conservation:\n", |

1265 | current_function_name ()); |

1266 | FOR_EACH_BB_FN (bb, cfun) |

1267 | { |

1268 | if ((bb_gcov_count (bb) != sum_edge_counts (bb->preds)) |

1269 | || (bb_gcov_count (bb) != sum_edge_counts (bb->succs))) |

1270 | { |

1271 | fprintf (dump_file, |

1272 | "BB%d(%"PRId64 ") **INVALID**: ", |

1273 | bb->index, bb_gcov_count (bb)); |

1274 | fprintf (stderr, |

1275 | "******** BB%d(%"PRId64 |

1276 | ") **INVALID**: \n", bb->index, bb_gcov_count (bb)); |

1277 | fprintf (dump_file, "in_edges=%"PRId64 " ", |

1278 | sum_edge_counts (bb->preds)); |

1279 | fprintf (dump_file, "out_edges=%"PRId64 "\n", |

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 |

1354 | sum_edge_counts (vec<edge, va_gc> *to_edges) |

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; |

1364 | sum += edge_gcov_count (e); |

1365 | } |

1366 | return sum; |

1367 | } |

1368 | |

1369 | |

1370 | /* Main routine. Smoothes the initial assigned basic block and edge counts using |

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 | } |

1385 |