Mercurial > hg > CbC > CbC_gcc
annotate gcc/graphite.c @ 131:84e7813d76e9
gcc-8.2
| author | mir3636 |
|---|---|
| date | Thu, 25 Oct 2018 07:37:49 +0900 |
| parents | 04ced10e8804 |
| children | 1830386684a0 |
| rev | line source |
|---|---|
| 0 | 1 /* Gimple Represented as Polyhedra. |
| 131 | 2 Copyright (C) 2006-2018 Free Software Foundation, Inc. |
| 0 | 3 Contributed by Sebastian Pop <sebastian.pop@inria.fr>. |
| 4 | |
| 5 This file is part of GCC. | |
| 6 | |
| 7 GCC is free software; you can redistribute it and/or modify | |
| 8 it under the terms of the GNU General Public License as published by | |
| 9 the Free Software Foundation; either version 3, or (at your option) | |
| 10 any later version. | |
| 11 | |
| 12 GCC is distributed in the hope that it will be useful, | |
| 13 but WITHOUT ANY WARRANTY; without even the implied warranty of | |
| 14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
| 15 GNU General Public License for more details. | |
| 16 | |
| 17 You should have received a copy of the GNU General Public License | |
| 18 along with GCC; see the file COPYING3. If not see | |
| 19 <http://www.gnu.org/licenses/>. */ | |
| 20 | |
| 21 /* This pass converts GIMPLE to GRAPHITE, performs some loop | |
| 22 transformations and then converts the resulting representation back | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
23 to GIMPLE. |
| 0 | 24 |
| 25 An early description of this pass can be found in the GCC Summit'06 | |
| 26 paper "GRAPHITE: Polyhedral Analyses and Optimizations for GCC". | |
| 27 The wiki page http://gcc.gnu.org/wiki/Graphite contains pointers to | |
| 111 | 28 the related work. */ |
| 0 | 29 |
| 111 | 30 #define USES_ISL |
| 0 | 31 |
| 32 #include "config.h" | |
| 33 #include "system.h" | |
| 34 #include "coretypes.h" | |
| 111 | 35 #include "backend.h" |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
36 #include "diagnostic-core.h" |
| 0 | 37 #include "cfgloop.h" |
| 111 | 38 #include "tree-pass.h" |
| 39 #include "params.h" | |
| 40 #include "pretty-print.h" | |
| 131 | 41 #include "cfganal.h" |
| 111 | 42 |
| 43 #ifdef HAVE_isl | |
| 44 #include "cfghooks.h" | |
| 45 #include "tree.h" | |
| 46 #include "gimple.h" | |
| 47 #include "ssa.h" | |
| 48 #include "fold-const.h" | |
| 49 #include "gimple-iterator.h" | |
| 50 #include "tree-cfg.h" | |
| 51 #include "tree-ssa-loop.h" | |
| 0 | 52 #include "tree-data-ref.h" |
| 53 #include "tree-scalar-evolution.h" | |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
54 #include "dbgcnt.h" |
| 111 | 55 #include "tree-parloops.h" |
| 56 #include "tree-cfgcleanup.h" | |
| 57 #include "tree-vectorizer.h" | |
| 58 #include "tree-ssa-loop-manip.h" | |
| 59 #include "tree-ssa.h" | |
| 60 #include "tree-into-ssa.h" | |
| 61 #include "graphite.h" | |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
62 |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
63 /* Print global statistics to FILE. */ |
| 0 | 64 |
| 65 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
|
66 print_global_statistics (FILE* file) |
| 0 | 67 { |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
68 long n_bbs = 0; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
69 long n_loops = 0; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
70 long n_stmts = 0; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
71 long n_conditions = 0; |
| 111 | 72 profile_count n_p_bbs = profile_count::zero (); |
| 73 profile_count n_p_loops = profile_count::zero (); | |
| 74 profile_count n_p_stmts = profile_count::zero (); | |
| 75 profile_count n_p_conditions = profile_count::zero (); | |
| 0 | 76 |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
77 basic_block bb; |
| 0 | 78 |
| 111 | 79 FOR_ALL_BB_FN (bb, cfun) |
| 0 | 80 { |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
81 gimple_stmt_iterator psi; |
| 0 | 82 |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
83 n_bbs++; |
| 111 | 84 if (bb->count.initialized_p ()) |
| 85 n_p_bbs += bb->count; | |
| 0 | 86 |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
87 /* Ignore artificial surrounding loop. */ |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
88 if (bb == bb->loop_father->header |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
89 && bb->index != 0) |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
90 { |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
91 n_loops++; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
92 n_p_loops += bb->count; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
93 } |
| 0 | 94 |
| 111 | 95 if (EDGE_COUNT (bb->succs) > 1) |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
96 { |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
97 n_conditions++; |
| 111 | 98 if (bb->count.initialized_p ()) |
| 99 n_p_conditions += bb->count; | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
100 } |
| 0 | 101 |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
102 for (psi = gsi_start_bb (bb); !gsi_end_p (psi); gsi_next (&psi)) |
| 0 | 103 { |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
104 n_stmts++; |
| 111 | 105 if (bb->count.initialized_p ()) |
| 106 n_p_stmts += bb->count; | |
| 0 | 107 } |
| 108 } | |
| 109 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
110 fprintf (file, "\nGlobal statistics ("); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
111 fprintf (file, "BBS:%ld, ", n_bbs); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
112 fprintf (file, "LOOPS:%ld, ", n_loops); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
113 fprintf (file, "CONDITIONS:%ld, ", n_conditions); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
114 fprintf (file, "STMTS:%ld)\n", n_stmts); |
| 111 | 115 fprintf (file, "Global profiling statistics ("); |
| 116 fprintf (file, "BBS:"); | |
| 117 n_p_bbs.dump (file); | |
| 118 fprintf (file, ", LOOPS:"); | |
| 119 n_p_loops.dump (file); | |
| 120 fprintf (file, ", CONDITIONS:"); | |
| 121 n_p_conditions.dump (file); | |
| 122 fprintf (file, ", STMTS:"); | |
| 123 n_p_stmts.dump (file); | |
| 124 fprintf (file, ")\n\n"); | |
| 0 | 125 } |
| 126 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
127 /* Print statistics for SCOP to FILE. */ |
| 0 | 128 |
| 129 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
|
130 print_graphite_scop_statistics (FILE* file, scop_p scop) |
| 0 | 131 { |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
132 long n_bbs = 0; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
133 long n_loops = 0; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
134 long n_stmts = 0; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
135 long n_conditions = 0; |
| 111 | 136 profile_count n_p_bbs = profile_count::zero (); |
| 137 profile_count n_p_loops = profile_count::zero (); | |
| 138 profile_count n_p_stmts = profile_count::zero (); | |
| 139 profile_count n_p_conditions = profile_count::zero (); | |
| 0 | 140 |
| 141 basic_block bb; | |
| 142 | |
| 111 | 143 FOR_ALL_BB_FN (bb, cfun) |
| 0 | 144 { |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
145 gimple_stmt_iterator psi; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
146 loop_p loop = bb->loop_father; |
| 0 | 147 |
| 111 | 148 if (!bb_in_sese_p (bb, scop->scop_info->region)) |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
149 continue; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
150 |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
151 n_bbs++; |
| 111 | 152 if (bb->count.initialized_p ()) |
| 153 n_p_bbs += bb->count; | |
| 0 | 154 |
| 111 | 155 if (EDGE_COUNT (bb->succs) > 1) |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
156 { |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
157 n_conditions++; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
158 n_p_conditions += bb->count; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
159 } |
| 0 | 160 |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
161 for (psi = gsi_start_bb (bb); !gsi_end_p (psi); gsi_next (&psi)) |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
162 { |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
163 n_stmts++; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
164 n_p_stmts += bb->count; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
165 } |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
166 |
| 111 | 167 if (loop->header == bb && loop_in_sese_p (loop, scop->scop_info->region)) |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
168 { |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
169 n_loops++; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
170 n_p_loops += bb->count; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
171 } |
| 0 | 172 } |
| 173 | |
| 111 | 174 fprintf (file, "\nFunction Name: %s\n", current_function_name ()); |
| 175 | |
| 176 edge scop_begin = scop->scop_info->region.entry; | |
| 177 edge scop_end = scop->scop_info->region.exit; | |
| 178 | |
| 179 fprintf (file, "\nSCoP (entry_edge (bb_%d, bb_%d), ", | |
| 180 scop_begin->src->index, scop_begin->dest->index); | |
| 181 fprintf (file, "exit_edge (bb_%d, bb_%d))", | |
| 182 scop_end->src->index, scop_end->dest->index); | |
| 183 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
184 fprintf (file, "\nSCoP statistics ("); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
185 fprintf (file, "BBS:%ld, ", n_bbs); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
186 fprintf (file, "LOOPS:%ld, ", n_loops); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
187 fprintf (file, "CONDITIONS:%ld, ", n_conditions); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
188 fprintf (file, "STMTS:%ld)\n", n_stmts); |
| 111 | 189 fprintf (file, "SCoP profiling statistics ("); |
| 190 fprintf (file, "BBS:"); | |
| 191 n_p_bbs.dump (file); | |
| 192 fprintf (file, ", LOOPS:"); | |
| 193 n_p_loops.dump (file); | |
| 194 fprintf (file, ", CONDITIONS:"); | |
| 195 n_p_conditions.dump (file); | |
| 196 fprintf (file, ", STMTS:"); | |
| 197 n_p_stmts.dump (file); | |
| 198 fprintf (file, ")\n\n"); | |
| 0 | 199 } |
| 200 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
201 /* Print statistics for SCOPS to FILE. */ |
| 0 | 202 |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
203 static void |
| 111 | 204 print_graphite_statistics (FILE* file, vec<scop_p> scops) |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
205 { |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
206 int i; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
207 scop_p scop; |
| 0 | 208 |
| 111 | 209 FOR_EACH_VEC_ELT (scops, i, scop) |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
210 print_graphite_scop_statistics (file, scop); |
| 0 | 211 } |
| 212 | |
| 111 | 213 /* Deletes all scops in SCOPS. */ |
| 214 | |
| 215 static void | |
| 216 free_scops (vec<scop_p> scops) | |
| 217 { | |
| 218 int i; | |
| 219 scop_p scop; | |
| 220 | |
| 221 FOR_EACH_VEC_ELT (scops, i, scop) | |
| 222 free_scop (scop); | |
| 223 | |
| 224 scops.release (); | |
| 225 } | |
| 0 | 226 |
| 111 | 227 /* Transforms LOOP to the canonical loop closed SSA form. */ |
| 228 | |
| 229 static void | |
| 131 | 230 canonicalize_loop_closed_ssa (loop_p loop, edge e) |
| 0 | 231 { |
| 111 | 232 basic_block bb; |
| 233 gphi_iterator psi; | |
| 234 | |
| 235 bb = e->dest; | |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
236 |
| 111 | 237 /* Make the loop-close PHI node BB contain only PHIs and have a |
| 238 single predecessor. */ | |
| 239 if (single_pred_p (bb)) | |
| 240 { | |
| 241 e = split_block_after_labels (bb); | |
| 242 bb = e->src; | |
| 243 } | |
| 244 else | |
| 0 | 245 { |
| 111 | 246 basic_block close = split_edge (e); |
| 247 e = single_succ_edge (close); | |
| 248 for (psi = gsi_start_phis (bb); !gsi_end_p (psi); gsi_next (&psi)) | |
| 249 { | |
| 250 gphi *phi = psi.phi (); | |
| 251 use_operand_p use_p = PHI_ARG_DEF_PTR_FROM_EDGE (phi, e); | |
| 252 tree arg = USE_FROM_PTR (use_p); | |
| 0 | 253 |
| 111 | 254 /* Only add close phi nodes for SSA_NAMEs defined in LOOP. */ |
| 255 if (TREE_CODE (arg) != SSA_NAME | |
| 256 || SSA_NAME_IS_DEFAULT_DEF (arg) | |
| 257 || ! flow_bb_inside_loop_p (loop, | |
| 258 gimple_bb (SSA_NAME_DEF_STMT (arg)))) | |
| 259 continue; | |
| 260 | |
| 261 tree res = copy_ssa_name (arg); | |
| 262 gphi *close_phi = create_phi_node (res, close); | |
| 263 add_phi_arg (close_phi, arg, gimple_phi_arg_edge (close_phi, 0), | |
| 264 UNKNOWN_LOCATION); | |
| 265 SET_USE (use_p, res); | |
| 266 } | |
| 267 bb = close; | |
| 0 | 268 } |
| 269 | |
| 111 | 270 /* Eliminate duplicates. This relies on processing loops from |
| 271 innermost to outer. */ | |
| 272 for (psi = gsi_start_phis (bb); !gsi_end_p (psi); gsi_next (&psi)) | |
| 273 { | |
| 274 gphi_iterator gsi = psi; | |
| 275 gphi *phi = psi.phi (); | |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
276 |
| 111 | 277 /* At this point, PHI should be a close phi in normal form. */ |
| 278 gcc_assert (gimple_phi_num_args (phi) == 1); | |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
279 |
| 111 | 280 /* Iterate over the next phis and remove duplicates. */ |
| 281 gsi_next (&gsi); | |
| 282 while (!gsi_end_p (gsi)) | |
| 283 if (gimple_phi_arg_def (phi, 0) == gimple_phi_arg_def (gsi.phi (), 0)) | |
| 284 { | |
| 285 replace_uses_by (gimple_phi_result (gsi.phi ()), | |
| 286 gimple_phi_result (phi)); | |
| 287 remove_phi_node (&gsi, true); | |
| 288 } | |
| 289 else | |
| 290 gsi_next (&gsi); | |
| 291 } | |
| 0 | 292 } |
| 293 | |
| 111 | 294 /* Converts the current loop closed SSA form to a canonical form |
| 295 expected by the Graphite code generation. | |
| 296 | |
| 297 The loop closed SSA form has the following invariant: a variable | |
| 298 defined in a loop that is used outside the loop appears only in the | |
| 299 phi nodes in the destination of the loop exit. These phi nodes are | |
| 300 called close phi nodes. | |
| 301 | |
| 302 The canonical loop closed SSA form contains the extra invariants: | |
| 303 | |
| 304 - when the loop contains only one exit, the close phi nodes contain | |
| 305 only one argument. That implies that the basic block that contains | |
| 306 the close phi nodes has only one predecessor, that is a basic block | |
| 307 in the loop. | |
| 308 | |
| 309 - the basic block containing the close phi nodes does not contain | |
| 310 other statements. | |
| 311 | |
| 312 - there exist only one phi node per definition in the loop. | |
| 131 | 313 |
| 314 In addition to that we also make sure that loop exit edges are | |
| 315 first in the successor edge vector. This is to make RPO order | |
| 316 as computed by pre_and_rev_post_order_compute be consistent with | |
| 317 what initial schedule generation expects. | |
| 111 | 318 */ |
| 0 | 319 |
| 320 static void | |
| 131 | 321 canonicalize_loop_form (void) |
| 0 | 322 { |
| 111 | 323 loop_p loop; |
| 324 FOR_EACH_LOOP (loop, LI_FROM_INNERMOST) | |
| 131 | 325 { |
| 326 edge e = single_exit (loop); | |
| 327 if (!e || (e->flags & (EDGE_COMPLEX|EDGE_FAKE))) | |
| 328 continue; | |
| 329 | |
| 330 canonicalize_loop_closed_ssa (loop, e); | |
| 331 | |
| 332 /* If the exit is not first in the edge vector make it so. */ | |
| 333 if (e != EDGE_SUCC (e->src, 0)) | |
| 334 { | |
| 335 unsigned ei; | |
| 336 for (ei = 0; EDGE_SUCC (e->src, ei) != e; ++ei) | |
| 337 ; | |
| 338 std::swap (EDGE_SUCC (e->src, ei), EDGE_SUCC (e->src, 0)); | |
| 339 } | |
| 340 } | |
| 341 | |
| 342 /* We can end up releasing duplicate exit PHIs and also introduce | |
| 343 additional copies so the cached information isn't correct anymore. */ | |
| 344 scev_reset (); | |
| 0 | 345 |
| 111 | 346 checking_verify_loop_closed_ssa (true); |
| 347 } | |
| 0 | 348 |
| 111 | 349 isl_ctx *the_isl_ctx; |
| 0 | 350 |
| 351 /* Perform a set of linear transforms on the loops of the current | |
| 352 function. */ | |
| 353 | |
| 354 void | |
| 355 graphite_transform_loops (void) | |
| 356 { | |
| 357 int i; | |
| 358 scop_p scop; | |
| 111 | 359 bool changed = false; |
| 360 vec<scop_p> scops = vNULL; | |
| 361 isl_ctx *ctx; | |
| 0 | 362 |
| 111 | 363 /* If a function is parallel it was most probably already run through graphite |
| 364 once. No need to run again. */ | |
| 365 if (parallelized_function_p (cfun->decl)) | |
| 0 | 366 return; |
| 367 | |
| 111 | 368 calculate_dominance_info (CDI_DOMINATORS); |
| 369 | |
| 131 | 370 /* We rely on post-dominators during merging of SESE regions so those |
| 371 have to be meaningful. */ | |
| 372 connect_infinite_loops_to_exit (); | |
| 373 | |
| 111 | 374 ctx = isl_ctx_alloc (); |
| 375 isl_options_set_on_error (ctx, ISL_ON_ERROR_ABORT); | |
| 376 the_isl_ctx = ctx; | |
| 377 | |
| 378 sort_sibling_loops (cfun); | |
| 131 | 379 canonicalize_loop_form (); |
| 111 | 380 |
| 381 /* Print the loop structure. */ | |
| 382 if (dump_file && (dump_flags & TDF_DETAILS)) | |
| 383 { | |
| 384 print_loops (dump_file, 2); | |
| 385 print_loops (dump_file, 3); | |
| 386 } | |
| 387 | |
| 388 calculate_dominance_info (CDI_POST_DOMINATORS); | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
389 build_scops (&scops); |
| 111 | 390 free_dominance_info (CDI_POST_DOMINATORS); |
| 0 | 391 |
| 131 | 392 /* Remove the fake exits before transform given they are not reflected |
| 393 in loop structures we end up verifying. */ | |
| 394 remove_fake_exit_edges (); | |
| 395 | |
| 0 | 396 if (dump_file && (dump_flags & TDF_DETAILS)) |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
397 { |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
398 print_graphite_statistics (dump_file, scops); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
399 print_global_statistics (dump_file); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
400 } |
| 0 | 401 |
| 111 | 402 FOR_EACH_VEC_ELT (scops, i, scop) |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
403 if (dbg_cnt (graphite_scop)) |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
404 { |
| 111 | 405 scop->isl_context = ctx; |
| 406 if (!build_poly_scop (scop)) | |
| 407 continue; | |
| 408 | |
| 409 if (!apply_poly_transforms (scop)) | |
| 410 continue; | |
| 0 | 411 |
| 111 | 412 changed = true; |
| 413 if (graphite_regenerate_ast_isl (scop)) | |
| 414 { | |
| 131 | 415 dump_user_location_t loc = find_loop_location |
| 111 | 416 (scops[i]->scop_info->region.entry->dest->loop_father); |
| 417 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, loc, | |
| 418 "loop nest optimized\n"); | |
| 419 } | |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
420 } |
| 0 | 421 |
| 111 | 422 if (changed) |
| 423 { | |
| 424 mark_virtual_operands_for_renaming (cfun); | |
| 425 update_ssa (TODO_update_ssa); | |
| 426 checking_verify_ssa (true, true); | |
| 427 rewrite_into_loop_closed_ssa (NULL, 0); | |
| 428 scev_reset (); | |
| 429 checking_verify_loop_structure (); | |
| 430 } | |
| 431 | |
| 432 if (dump_file && (dump_flags & TDF_DETAILS)) | |
| 433 { | |
| 434 loop_p loop; | |
| 435 int num_no_dependency = 0; | |
| 436 | |
| 437 FOR_EACH_LOOP (loop, 0) | |
| 438 if (loop->can_be_parallel) | |
| 439 num_no_dependency++; | |
| 440 | |
| 441 fprintf (dump_file, "%d loops carried no dependency.\n", | |
| 442 num_no_dependency); | |
| 443 } | |
| 444 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
445 free_scops (scops); |
| 111 | 446 the_isl_ctx = NULL; |
| 447 isl_ctx_free (ctx); | |
| 448 | |
| 449 if (changed) | |
| 450 { | |
| 451 cleanup_tree_cfg (); | |
| 452 profile_status_for_fn (cfun) = PROFILE_ABSENT; | |
| 453 release_recorded_exits (cfun); | |
| 454 tree_estimate_probability (false); | |
| 455 } | |
| 0 | 456 } |
| 457 | |
| 111 | 458 #else /* If isl is not available: #ifndef HAVE_isl. */ |
| 0 | 459 |
| 111 | 460 static void |
| 0 | 461 graphite_transform_loops (void) |
| 462 { | |
| 111 | 463 sorry ("Graphite loop optimizations cannot be used (isl is not available)."); |
| 0 | 464 } |
| 465 | |
| 466 #endif | |
| 111 | 467 |
| 468 | |
| 469 static unsigned int | |
| 470 graphite_transforms (struct function *fun) | |
| 471 { | |
| 472 if (number_of_loops (fun) <= 1) | |
| 473 return 0; | |
| 474 | |
| 475 graphite_transform_loops (); | |
| 476 | |
| 477 return 0; | |
| 478 } | |
| 479 | |
| 480 static bool | |
| 481 gate_graphite_transforms (void) | |
| 482 { | |
| 483 /* Enable -fgraphite pass if any one of the graphite optimization flags | |
| 484 is turned on. */ | |
| 485 if (flag_graphite_identity | |
| 486 || flag_loop_parallelize_all | |
| 487 || flag_loop_nest_optimize) | |
| 488 flag_graphite = 1; | |
| 489 | |
| 490 return flag_graphite != 0; | |
| 491 } | |
| 492 | |
| 493 namespace { | |
| 494 | |
| 495 const pass_data pass_data_graphite = | |
| 496 { | |
| 497 GIMPLE_PASS, /* type */ | |
| 498 "graphite0", /* name */ | |
| 499 OPTGROUP_LOOP, /* optinfo_flags */ | |
| 500 TV_GRAPHITE, /* tv_id */ | |
| 501 ( PROP_cfg | PROP_ssa ), /* properties_required */ | |
| 502 0, /* properties_provided */ | |
| 503 0, /* properties_destroyed */ | |
| 504 0, /* todo_flags_start */ | |
| 505 0, /* todo_flags_finish */ | |
| 506 }; | |
| 507 | |
| 508 class pass_graphite : public gimple_opt_pass | |
| 509 { | |
| 510 public: | |
| 511 pass_graphite (gcc::context *ctxt) | |
| 512 : gimple_opt_pass (pass_data_graphite, ctxt) | |
| 513 {} | |
| 514 | |
| 515 /* opt_pass methods: */ | |
| 516 virtual bool gate (function *) { return gate_graphite_transforms (); } | |
| 517 | |
| 518 }; // class pass_graphite | |
| 519 | |
| 520 } // anon namespace | |
| 521 | |
| 522 gimple_opt_pass * | |
| 523 make_pass_graphite (gcc::context *ctxt) | |
| 524 { | |
| 525 return new pass_graphite (ctxt); | |
| 526 } | |
| 527 | |
| 528 namespace { | |
| 529 | |
| 530 const pass_data pass_data_graphite_transforms = | |
| 531 { | |
| 532 GIMPLE_PASS, /* type */ | |
| 533 "graphite", /* name */ | |
| 534 OPTGROUP_LOOP, /* optinfo_flags */ | |
| 535 TV_GRAPHITE_TRANSFORMS, /* tv_id */ | |
| 536 ( PROP_cfg | PROP_ssa ), /* properties_required */ | |
| 537 0, /* properties_provided */ | |
| 538 0, /* properties_destroyed */ | |
| 539 0, /* todo_flags_start */ | |
| 540 0, /* todo_flags_finish */ | |
| 541 }; | |
| 542 | |
| 543 class pass_graphite_transforms : public gimple_opt_pass | |
| 544 { | |
| 545 public: | |
| 546 pass_graphite_transforms (gcc::context *ctxt) | |
| 547 : gimple_opt_pass (pass_data_graphite_transforms, ctxt) | |
| 548 {} | |
| 549 | |
| 550 /* opt_pass methods: */ | |
| 551 virtual bool gate (function *) { return gate_graphite_transforms (); } | |
| 552 virtual unsigned int execute (function *fun) { return graphite_transforms (fun); } | |
| 553 | |
| 554 }; // class pass_graphite_transforms | |
| 555 | |
| 556 } // anon namespace | |
| 557 | |
| 558 gimple_opt_pass * | |
| 559 make_pass_graphite_transforms (gcc::context *ctxt) | |
| 560 { | |
| 561 return new pass_graphite_transforms (ctxt); | |
| 562 } | |
| 563 | |
| 564 |