- Generated by
1.8.1.1
|
GCC Middle and Back End API Reference
|
Functions | |
| static isl_constraint * | build_linearized_memory_access () |
| static void | pdr_stride_in_loop () |
| static void | memory_strides_in_loop_1 () |
| static void | memory_strides_in_loop () |
| static bool | lst_interchange_profitable_p () |
| static void | pbb_interchange_loop_depths (graphite_dim_t depth1, graphite_dim_t depth2, poly_bb_p pbb) |
| static void | lst_apply_interchange () |
| static bool | lst_perfectly_nested_p () |
| static void | lst_perfect_nestify (lst_p loop1, lst_p loop2, lst_p *before, lst_p *nest, lst_p *after) |
| static bool | lst_try_interchange_loops () |
| static bool | lst_interchange_select_inner (scop_p scop, lst_p outer_father, int outer, lst_p inner_father) |
| static int | lst_interchange_select_outer () |
| int | scop_do_interchange () |
|
static |
@verbatim Interchange heuristics and transform for loop interchange on
polyhedral representation.
Copyright (C) 2009-2013 Free Software Foundation, Inc. Contributed by Sebastian Pop sebastian.pop@amd.com and Harsha Jagasia harsha.jagasia@amd.com.
This file is part of GCC.
GCC is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 3, or (at your option) any later version.
GCC is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
You should have received a copy of the GNU General Public License along with GCC; see the file COPYING3. If not see http://www.gnu.org/licenses/.
XXX isl rewrite following comment
Builds a linear expression, of dimension DIM, representing PDR's
memory access:
L = r_{n}*r_{n-1}*...*r_{1}*s_{0} + ... + r_{n}*s_{n-1} + s_{n}.
For an array A[10][20] with two subscript locations s0 and s1, the
linear memory access is 20 * s0 + s1: a stride of 1 in subscript s0
corresponds to a memory stride of 20.
OFFSET is a number of dimensions to prepend before the
subscript dimensions: s_0, s_1, ..., s_n.
Thus, the final linear expression has the following format:
0 .. 0_{offset} | 0 .. 0_{nit} | 0 .. 0_{gd} | 0 | c_0 c_1 ... c_n
where the expression itself is:
c_0 * s_0 + c_1 * s_1 + ... c_n * s_n.
References poly_dr::extent, and offset.
Referenced by pdr_stride_in_loop().
|
static |
Apply the interchange of loops at depths DEPTH1 and DEPTH2 to all the statements below LST.
References pbb_interchange_loop_depths().
Referenced by lst_try_interchange_loops().
|
static |
Return true when the interchange of loops LOOP1 and LOOP2 is
profitable.
Example:
| int a[100][100];
|
| int
| foo (int N)
| {
| int j;
| int i;
|
| for (i = 0; i < N; i++)
| for (j = 0; j < N; j++)
| a[j][2 * i] += 1;
|
| return a[N][12];
| }
The data access A[j][i] is described like this:
| i j N a s0 s1 1
| 0 0 0 1 0 0 -5 = 0
| 0 -1 0 0 1 0 0 = 0
|-2 0 0 0 0 1 0 = 0
| 0 0 0 0 1 0 0 >= 0
| 0 0 0 0 0 1 0 >= 0
| 0 0 0 0 -1 0 100 >= 0
| 0 0 0 0 0 -1 100 >= 0
The linearized memory access L to A[100][100] is:
| i j N a s0 s1 1
| 0 0 0 0 100 1 0
TODO: the shown format is not valid as it does not show the fact
that the iteration domain "i j" is transformed using the scattering.
Next, to measure the impact of iterating once in loop "i", we build
a maximization problem: first, we add to DR accesses the dimensions
k, s2, s3, L1 = 100 * s0 + s1, L2, and D1: this is the polyhedron P1.
L1 and L2 are the linearized memory access functions.
| i j N a s0 s1 k s2 s3 L1 L2 D1 1
| 0 0 0 1 0 0 0 0 0 0 0 0 -5 = 0 alias = 5
| 0 -1 0 0 1 0 0 0 0 0 0 0 0 = 0 s0 = j
|-2 0 0 0 0 1 0 0 0 0 0 0 0 = 0 s1 = 2 * i
| 0 0 0 0 1 0 0 0 0 0 0 0 0 >= 0
| 0 0 0 0 0 1 0 0 0 0 0 0 0 >= 0
| 0 0 0 0 -1 0 0 0 0 0 0 0 100 >= 0
| 0 0 0 0 0 -1 0 0 0 0 0 0 100 >= 0
| 0 0 0 0 100 1 0 0 0 -1 0 0 0 = 0 L1 = 100 * s0 + s1
Then, we generate the polyhedron P2 by interchanging the dimensions
(s0, s2), (s1, s3), (L1, L2), (k, i)
| i j N a s0 s1 k s2 s3 L1 L2 D1 1
| 0 0 0 1 0 0 0 0 0 0 0 0 -5 = 0 alias = 5
| 0 -1 0 0 0 0 0 1 0 0 0 0 0 = 0 s2 = j
| 0 0 0 0 0 0 -2 0 1 0 0 0 0 = 0 s3 = 2 * k
| 0 0 0 0 0 0 0 1 0 0 0 0 0 >= 0
| 0 0 0 0 0 0 0 0 1 0 0 0 0 >= 0
| 0 0 0 0 0 0 0 -1 0 0 0 0 100 >= 0
| 0 0 0 0 0 0 0 0 -1 0 0 0 100 >= 0
| 0 0 0 0 0 0 0 100 1 0 -1 0 0 = 0 L2 = 100 * s2 + s3
then we add to P2 the equality k = i + 1:
|-1 0 0 0 0 0 1 0 0 0 0 0 -1 = 0 k = i + 1
and finally we maximize the expression "D1 = max (P1 inter P2, L2 - L1)".
Similarly, to determine the impact of one iteration on loop "j", we
interchange (k, j), we add "k = j + 1", and we compute D2 the
maximal value of the difference.
Finally, the profitability test is D1 < D2: if in the outer loop
the strides are smaller than in the inner loop, then it is
profitable to interchange the loops at DEPTH1 and DEPTH2.
References d1, d2, and memory_strides_in_loop().
Referenced by lst_try_interchange_loops().
|
static |
Selects the inner loop in LST_SEQ (INNER_FATHER) to be interchanged with the loop OUTER in LST_SEQ (OUTER_FATHER).
References lst_try_interchange_loops().
Referenced by lst_interchange_select_outer().
|
static |
Interchanges all the loops of LOOP and the loops of its body that are considered profitable to interchange. Return the number of interchanged loops. OUTER is the index in LST_SEQ (LOOP) that points to the next outer loop to be considered for interchange.
References lst_interchange_select_inner().
Referenced by scop_do_interchange().
|
static |
Transform the loop nest between LOOP1 and LOOP2 into a perfect nest. To continue the naming tradition, this function is called after perfect_nestify. NEST is set to the perfectly nested loop that is created. BEFORE/AFTER are set to the loops distributed before/after the loop NEST.
References copy_lst(), first, free_lst(), last, lst_empty_p(), lst_find_first_pbb(), lst_find_last_pbb(), lst_remove_all_before_excluding_pbb(), and lst_remove_all_before_including_pbb().
Referenced by lst_try_interchange_loops().
|
static |
Return true when the nest starting at LOOP1 and ending on LOOP2 is perfect: i.e. there are no sequence of statements.
Referenced by lst_try_interchange_loops().
|
static |
Try to interchange LOOP1 with LOOP2 for all the statements of the body of LOOP2. LOOP1 contains LOOP2. Return true if it did the interchange.
References dump_file, dump_flags, free_lst(), graphite_legal_transform(), lst_apply_interchange(), lst_depth(), lst_insert_in_sequence(), lst_interchange_profitable_p(), lst_perfect_nestify(), lst_perfectly_nested_p(), lst_replace(), lst_substitute_3(), and lst_update_scattering().
Referenced by lst_interchange_select_inner().
|
static |
Sets STRIDES to the sum of all the strides of the data references accessed in LOOP at DEPTH.
References lst::memory_strides, and memory_strides_in_loop_1().
Referenced by lst_interchange_profitable_p().
|
static |
Sets STRIDES to the sum of all the strides of the data references accessed in LOOP at DEPTH.
References pdr_stride_in_loop().
Referenced by memory_strides_in_loop().
|
static |
Interchanges the loops at DEPTH1 and DEPTH2 of the original scattering and assigns the resulting polyhedron to the transformed scattering.
References d1, d2, psct_dynamic_dim(), and poly_bb::transformed.
Referenced by lst_apply_interchange().
|
static |
Set STRIDE to the stride of PDR in memory by advancing by one in the loop at DEPTH.
References poly_dr::accesses, build_linearized_memory_access(), dump_file, dump_flags, map, offset, pbb_index(), pbb_nb_local_vars(), pbb_nb_scattering_transform(), psct_dynamic_dim(), and poly_bb::transformed.
Referenced by memory_strides_in_loop_1().
| int scop_do_interchange | ( | ) |
Interchanges all the loop depths that are considered profitable for SCOP. Return the number of interchanged loops.
References lst_interchange_select_outer(), and lst_update_scattering().
Referenced by apply_poly_transforms(), and scop_do_block().
1.8.1.1