[patch] TSP based bb reordering
James Morrison
ja2morri@csclub.uwaterloo.ca
Wed Apr 7 01:12:00 GMT 2004
Hi,
Zdenek Dvorak <rakdver@atrey.karlin.mff.cuni.cz> writes:
> Hello,
>
> this patch implements basic block reordering based on the reduction
> to the traveling salesman problem as described in
> www.research.att.com/~dsj/papers/PLDI.ps. I have done the testing
> on i686 (-march=athlon), so the original motivation (optimization for
> the static branch prediction) was not useful, but using it just to
> minimize the number of executed unconditional jumps turned out to
> also have benefits (mostly on sizes of binaries, see test results
> below). The time of compilation is increased by about 3% when using
> it. Bootstrapped (with -ftsp-ordering) & regtested on i686.
>
> Zdenek
>
> Index: bb-reorder.c
> ===================================================================
> RCS file: /cvs/gcc/gcc/gcc/bb-reorder.c,v
> retrieving revision 1.66
> diff -c -3 -p -r1.66 bb-reorder.c
> *** bb-reorder.c 20 Mar 2004 16:50:30 -0000 1.66
> --- bb-reorder.c 31 Mar 2004 07:02:05 -0000
> *************** static int exec_threshold[N_ROUNDS] = {5
> *** 91,96 ****
> --- 91,121 ----
> block the edge destination is not duplicated while connecting traces. */
> #define DUPLICATION_THRESHOLD 100
>
> + /* The parameters of the cost function for the tsp based reordering. These
> + can be redefined by targets as needed. The values here correspond simply
> + to minimising the total number of jumps executed, and a slight preference
> + for the taken branch to be the less frequent one, which is usually a good
> + thing to do. Making the value of HIT_TAKEN_COST and MISS_TAKEN_COST
> + different makes sense only on targets with static branch prediction. */
> +
> + /* Cost of an unconditional jump. */
> + #define JUMP_COST 100
> +
Should JUMP_COST be wrapped in an ifndef?
> Index: tsp.c
> ===================================================================
> RCS file: tsp.c
> diff -N tsp.c
> *** /dev/null 1 Jan 1970 00:00:00 -0000
> --- tsp.c 31 Mar 2004 07:02:05 -0000
> ***************
> *** 0 ****
> --- 1,540 ----
> + /* All orders HyperOPT heuristics tries. */
What about /* The HyperOPT heuristic tries all orders. */
> + static int hopt_h_ords[HOPT_H_NORDS][HOPT_H_VERT] =
> + {
> + {0, 1, 2, 3},
> + {0, 1, 3, 2},
> + {0, 2, 1, 3},
> + {0, 2, 3, 1},
> + {0, 3, 1, 2},
> + {0, 3, 2, 1}
> + };
> +
> + /* For each edge indices of sums in the HyperOPT heuristics to that the
> + weight of the edge should be added. */
I'm not sure what this comment says.
> + static int hopt_h_sums[HOPT_H_VERT][HOPT_H_VERT][ORDS_PER_EDGE] =
> + {
> + { /* (0, *) */
> + {HOPT_H_NORDS, HOPT_H_NORDS}, /* (0, 0) */
> + {0, 1}, /* (0, 1) */
> + {2, 3}, /* (0, 2) */
> + {4, 5} /* (0, 3) */
> + },
> + { /* (1, *) */
> + {3, 5}, /* (1, 0) */
> + {HOPT_H_NORDS, HOPT_H_NORDS}, /* (1, 1) */
> + {0, 4}, /* (1, 2) */
> + {1, 2} /* (1, 3) */
> + },
> + { /* (2, *) */
> + {1, 4}, /* (2, 0) */
> + {2, 5}, /* (2, 1) */
> + {HOPT_H_NORDS, HOPT_H_NORDS}, /* (2, 2) */
> + {0, 3} /* (2, 3) */
> + },
> + { /* (3, *) */
> + {0, 2}, /* (3, 0) */
> + {3, 4}, /* (3, 1) */
> + {1, 5}, /* (3, 2) */
> + {HOPT_H_NORDS, HOPT_H_NORDS} /* (3, 3) */
> + }
> + };
> +
> + /* Weights of edges are cached here. */
/* Edge weight cache. */ ?
> +
> + static int graph[MAX_TSP_SIZE + 2][MAX_TSP_SIZE + 2];
> +
> + /* Returns weight of edge A --> B. */
> +
> + #define edge_weight(A, B) graph[A][B]
> +
> + static void optimize_tsp (int, int *, struct vertex *, int);
> + static int tsp_value (int, int *);
> + static int three_swap_delta (int *, int, int, int);
> + void dump_tour (FILE *, int *, int);
> + static int hopt_delta (int [], int [], int [], sbitmap, int *, struct vertex *);
> + static void best_three_swap (int, int, int *, int *, int *, int *, int, int *);
> + static void hopt_perform (int *, int, int, int);
> +
> + /* Solves a tsp instance of size N. WEIGHTS is a matrix of weights of
> + edges. Result is retunrned in TOUR; the initial tour is also obtained
> + from there. */
^^^^^
Does this indicate that TOUR holds both the optimal tour and the initial tour?
Typo as well on returned.
> +
> + void
> + solve_tsp (int n, int *tour, struct vertex *weights, int iterate)
> + {
> + int tspvalue;
> + int i, j;
> +
> + if (dump_file)
> + fprintf (dump_file, "TSP:\n");
> +
> + for (i = 0; i < n; i++)
> + {
> + for (j = 0; j < n; j++)
> + graph[i][j] = weights[i].def_cost;
> + for (j = 0; j < weights[i].n_spec; j++)
> + graph[i][weights[i].spec_tgt[j]] = weights[i].spec_cost[j];
> + }
> +
> + tspvalue = tsp_value (n, tour);
> +
> + if (dump_file)
> + {
> + dump_tour (dump_file, tour, n);
> + fprintf (dump_file, "%d\n", tspvalue);
> + }
> +
> + if (tspvalue)
> + optimize_tsp (n, tour, weights, iterate);
> +
> + if (dump_file)
> + {
> + dump_tour (dump_file, tour, n);
> + fprintf (dump_file, "FINAL: %d\n", tsp_value (n, tour));
> + }
> + }
> +
> + /* Dumps TOUR of length N to FILE. */
> +
> + void
> + dump_tour (FILE *file, int *tour, int n)
> + {
> + int i, a;
> +
> + for (i = 0, a = 0; i < n - 1; i++, a = tour[a])
> + fprintf (file, "%d ", a);
> + fprintf (file, "%d\n", a);
> + }
> +
> + /* Return value of a tsp TOUR on N vertices. */
Would using cost instead of value here make sense?
> +
> + static int
> + tsp_value (int n, int *tour)
> + {
> + int i, act, sum = 0;
> +
> + act = 0;
> + for (i = 0; i < n - 1; i++, act = tour[act])
> + sum += edge_weight (act, tour[act]);
> +
> + return sum;
> + }
> +
> + static void
> + optimize_tsp (int n, int *tour, struct vertex *weights, int iterate)
> + {
> + int i1, i2, best_3opt, bi1, bi2, bi3, a, best_hopt, hi2, hperm, aperm, f, i;
> + int changed = true;
> + int temp;
> + int value = 0, new_value;
> + int work[MAX_TSP_SIZE + 2];
> + int wbot, wtop;
> + sbitmap in_work, v2s;
> + int v1[HOPT_H_VERT], v2[HOPT_H_VERT];
> +
> + #ifndef ENABLE_CHECKING
> + if (dump_file)
> + {
> + #endif
> + value = tsp_value (n, tour);
> + #ifndef ENABLE_CHECKING
> + }
> + #endif
This looks strange, if checking is enabled buy dump_file is 0 then
value, or new_value later on, will never be set.
> Index: doc/invoke.texi
> ===================================================================
> RCS file: /cvs/gcc/gcc/gcc/doc/invoke.texi,v
> retrieving revision 1.438
> diff -c -3 -p -r1.438 invoke.texi
> *** doc/invoke.texi 25 Mar 2004 17:43:24 -0000 1.438
> --- doc/invoke.texi 31 Mar 2004 07:02:05 -0000
> *************** in the following sections.
> *** 284,290 ****
> -foptimize-sibling-calls -fprefetch-loop-arrays @gol
> -fprofile-generate -fprofile-use @gol
> -freduce-all-givs -fregmove -frename-registers @gol
> ! -freorder-blocks -freorder-functions @gol
> -frerun-cse-after-loop -frerun-loop-opt @gol
> -frounding-math -fschedule-insns -fschedule-insns2 @gol
> -fno-sched-interblock -fno-sched-spec -fsched-spec-load @gol
> --- 284,290 ----
> -foptimize-sibling-calls -fprefetch-loop-arrays @gol
> -fprofile-generate -fprofile-use @gol
> -freduce-all-givs -fregmove -frename-registers @gol
> ! -freorder-blocks -ftsp-ordering -freorder-functions @gol
At one point I went through and put two spaces between every option.
See: http://gcc.gnu.org/ml/gcc-patches/2003-04/msg00464.html
> -frerun-cse-after-loop -frerun-loop-opt @gol
> -frounding-math -fschedule-insns -fschedule-insns2 @gol
> -fno-sched-interblock -fno-sched-spec -fsched-spec-load @gol
> *************** invoking @option{-O2} on programs that u
> *** 3655,3661 ****
> @opindex O3
> Optimize yet more. @option{-O3} turns on all optimizations specified by
> @option{-O2} and also turns on the @option{-finline-functions},
> ! @option{-fweb} and @option{-frename-registers} options.
>
> @item -O0
> @opindex O0
> --- 3655,3661 ----
> @opindex O3
> Optimize yet more. @option{-O3} turns on all optimizations specified by
> @option{-O2} and also turns on the @option{-finline-functions},
> ! @option{-ftsp-ordering}, @option{-fweb} and @option{-frename-registers} options.
>
> @item -O0
> @opindex O0
> *************** Reorder basic blocks in the compiled fun
> *** 4194,4199 ****
> --- 4194,4208 ----
> taken branches and improve code locality.
>
> Enabled at levels @option{-O2}, @option{-O3}.
> +
> + @item -ftsp-ordering
> + @opindex ftsp-ordering
> + In addition to heuristic used at @option{-freorder-blocks}, use also a more
> + powerful method based on the reduction to the Travelling Salesman Problem
> + to determine the good order of basic blocks in the function. This generally
> + produces smaller and faster programs, at the expense of longer compile times.
> +
> + Enabled at level @option{-O3}.
I'd try
@item -freorder-blocks
@opindex freorder-blocks
Reorder basic blocks in each function in order to reduce the number of
taken branches and improve code locality.
Enabled at levels @option{-O2}, @option{-O3}.
@item -ftsp-ordering
@opindex ftsp-ordering
Reorder basic blocks using a method based on the reduction to the Travelling
Salesman Problem to determine a good ordering of basic blocks in each function.
This generally produces smaller and faster programs, at the expense of longer
compile times.
Enabled at level @option{-O3}.
Jim
More information about the Gcc-patches
mailing list