Mercurial > hg > CbC > CbC_gcc
annotate gcc/graphite.c @ 158:494b0b89df80 default tip
...
| author | Shinji KONO <kono@ie.u-ryukyu.ac.jp> |
|---|---|
| date | Mon, 25 May 2020 18:13:55 +0900 |
| parents | 1830386684a0 |
| children |
| rev | line source |
|---|---|
| 0 | 1 /* Gimple Represented as Polyhedra. |
| 145 | 2 Copyright (C) 2006-2020 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 "pretty-print.h" | |
| 131 | 40 #include "cfganal.h" |
| 111 | 41 |
| 42 #ifdef HAVE_isl | |
| 43 #include "cfghooks.h" | |
| 44 #include "tree.h" | |
| 45 #include "gimple.h" | |
| 46 #include "ssa.h" | |
| 47 #include "fold-const.h" | |
| 48 #include "gimple-iterator.h" | |
| 49 #include "tree-cfg.h" | |
| 50 #include "tree-ssa-loop.h" | |
| 0 | 51 #include "tree-data-ref.h" |
| 52 #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
|
53 #include "dbgcnt.h" |
| 111 | 54 #include "tree-parloops.h" |
| 55 #include "tree-cfgcleanup.h" | |
| 56 #include "tree-vectorizer.h" | |
| 57 #include "tree-ssa-loop-manip.h" | |
| 58 #include "tree-ssa.h" | |
| 59 #include "tree-into-ssa.h" | |
| 60 #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
|
61 |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
62 /* Print global statistics to FILE. */ |
| 0 | 63 |
| 64 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
|
65 print_global_statistics (FILE* file) |
| 0 | 66 { |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
67 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
|
68 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
|
69 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
|
70 long n_conditions = 0; |
| 111 | 71 profile_count n_p_bbs = profile_count::zero (); |
| 72 profile_count n_p_loops = profile_count::zero (); | |
| 73 profile_count n_p_stmts = profile_count::zero (); | |
| 74 profile_count n_p_conditions = profile_count::zero (); | |
| 0 | 75 |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
76 basic_block bb; |
| 0 | 77 |
| 111 | 78 FOR_ALL_BB_FN (bb, cfun) |
| 0 | 79 { |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
80 gimple_stmt_iterator psi; |
| 0 | 81 |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
82 n_bbs++; |
| 111 | 83 if (bb->count.initialized_p ()) |
| 84 n_p_bbs += bb->count; | |
| 0 | 85 |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
86 /* 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
|
87 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
|
88 && 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
|
89 { |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
90 n_loops++; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
91 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
|
92 } |
| 0 | 93 |
| 111 | 94 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
|
95 { |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
96 n_conditions++; |
| 111 | 97 if (bb->count.initialized_p ()) |
| 98 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
|
99 } |
| 0 | 100 |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
101 for (psi = gsi_start_bb (bb); !gsi_end_p (psi); gsi_next (&psi)) |
| 0 | 102 { |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
103 n_stmts++; |
| 111 | 104 if (bb->count.initialized_p ()) |
| 105 n_p_stmts += bb->count; | |
| 0 | 106 } |
| 107 } | |
| 108 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
109 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
|
110 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
|
111 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
|
112 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
|
113 fprintf (file, "STMTS:%ld)\n", n_stmts); |
| 111 | 114 fprintf (file, "Global profiling statistics ("); |
| 115 fprintf (file, "BBS:"); | |
| 116 n_p_bbs.dump (file); | |
| 117 fprintf (file, ", LOOPS:"); | |
| 118 n_p_loops.dump (file); | |
| 119 fprintf (file, ", CONDITIONS:"); | |
| 120 n_p_conditions.dump (file); | |
| 121 fprintf (file, ", STMTS:"); | |
| 122 n_p_stmts.dump (file); | |
| 123 fprintf (file, ")\n\n"); | |
| 0 | 124 } |
| 125 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
126 /* Print statistics for SCOP to FILE. */ |
| 0 | 127 |
| 128 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
|
129 print_graphite_scop_statistics (FILE* file, scop_p scop) |
| 0 | 130 { |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
131 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
|
132 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
|
133 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
|
134 long n_conditions = 0; |
| 111 | 135 profile_count n_p_bbs = profile_count::zero (); |
| 136 profile_count n_p_loops = profile_count::zero (); | |
| 137 profile_count n_p_stmts = profile_count::zero (); | |
| 138 profile_count n_p_conditions = profile_count::zero (); | |
| 0 | 139 |
| 140 basic_block bb; | |
| 141 | |
| 111 | 142 FOR_ALL_BB_FN (bb, cfun) |
| 0 | 143 { |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
144 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
|
145 loop_p loop = bb->loop_father; |
| 0 | 146 |
| 111 | 147 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
|
148 continue; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
149 |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
150 n_bbs++; |
| 111 | 151 if (bb->count.initialized_p ()) |
| 152 n_p_bbs += bb->count; | |
| 0 | 153 |
| 111 | 154 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
|
155 { |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
156 n_conditions++; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
157 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
|
158 } |
| 0 | 159 |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
160 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
|
161 { |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
162 n_stmts++; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
163 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
|
164 } |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
165 |
| 111 | 166 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
|
167 { |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
168 n_loops++; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
169 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
|
170 } |
| 0 | 171 } |
| 172 | |
| 111 | 173 fprintf (file, "\nFunction Name: %s\n", current_function_name ()); |
| 174 | |
| 175 edge scop_begin = scop->scop_info->region.entry; | |
| 176 edge scop_end = scop->scop_info->region.exit; | |
| 177 | |
| 178 fprintf (file, "\nSCoP (entry_edge (bb_%d, bb_%d), ", | |
| 179 scop_begin->src->index, scop_begin->dest->index); | |
| 180 fprintf (file, "exit_edge (bb_%d, bb_%d))", | |
| 181 scop_end->src->index, scop_end->dest->index); | |
| 182 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
183 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
|
184 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
|
185 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
|
186 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
|
187 fprintf (file, "STMTS:%ld)\n", n_stmts); |
| 111 | 188 fprintf (file, "SCoP profiling statistics ("); |
| 189 fprintf (file, "BBS:"); | |
| 190 n_p_bbs.dump (file); | |
| 191 fprintf (file, ", LOOPS:"); | |
| 192 n_p_loops.dump (file); | |
| 193 fprintf (file, ", CONDITIONS:"); | |
| 194 n_p_conditions.dump (file); | |
| 195 fprintf (file, ", STMTS:"); | |
| 196 n_p_stmts.dump (file); | |
| 197 fprintf (file, ")\n\n"); | |
| 0 | 198 } |
| 199 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
200 /* Print statistics for SCOPS to FILE. */ |
| 0 | 201 |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
202 static void |
| 111 | 203 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
|
204 { |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
205 int i; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
206 scop_p scop; |
| 0 | 207 |
| 111 | 208 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
|
209 print_graphite_scop_statistics (file, scop); |
| 0 | 210 } |
| 211 | |
| 145 | 212 struct seir_cache_key |
| 213 { | |
| 214 hashval_t hash; | |
| 215 int entry_dest; | |
| 216 int exit_src; | |
| 217 int loop_num; | |
| 218 tree expr; | |
| 219 }; | |
| 220 | |
| 221 struct sese_scev_hash : typed_noop_remove <seir_cache_key> | |
| 222 { | |
| 223 typedef seir_cache_key value_type; | |
| 224 typedef seir_cache_key compare_type; | |
| 225 static hashval_t hash (const seir_cache_key &key) { return key.hash; } | |
| 226 static bool | |
| 227 equal (const seir_cache_key &key1, const seir_cache_key &key2) | |
| 228 { | |
| 229 return (key1.hash == key2.hash | |
| 230 && key1.entry_dest == key2.entry_dest | |
| 231 && key1.exit_src == key2.exit_src | |
| 232 && key1.loop_num == key2.loop_num | |
| 233 && operand_equal_p (key1.expr, key2.expr, 0)); | |
| 234 } | |
| 235 static void mark_deleted (seir_cache_key &key) { key.expr = NULL_TREE; } | |
| 236 static const bool empty_zero_p = false; | |
| 237 static void mark_empty (seir_cache_key &key) { key.entry_dest = 0; } | |
| 238 static bool is_deleted (const seir_cache_key &key) { return !key.expr; } | |
| 239 static bool is_empty (const seir_cache_key &key) { return key.entry_dest == 0; } | |
| 240 }; | |
| 241 | |
| 242 static hash_map<sese_scev_hash, tree> *seir_cache; | |
| 243 | |
| 244 /* Same as scalar_evolution_in_region but caches results so we avoid | |
| 245 re-computing evolutions during transform phase. */ | |
| 246 | |
| 247 tree | |
| 248 cached_scalar_evolution_in_region (const sese_l ®ion, loop_p loop, | |
| 249 tree expr) | |
| 250 { | |
| 251 seir_cache_key key; | |
| 252 key.entry_dest = region.entry->dest->index; | |
| 253 key.exit_src = region.exit->src->index; | |
| 254 key.loop_num = loop->num; | |
| 255 key.expr = expr; | |
| 256 inchash::hash hstate (0); | |
| 257 hstate.add_int (key.entry_dest); | |
| 258 hstate.add_int (key.exit_src); | |
| 259 hstate.add_int (key.loop_num); | |
| 260 inchash::add_expr (key.expr, hstate); | |
| 261 key.hash = hstate.end (); | |
| 262 | |
| 263 bool existed; | |
| 264 tree &chrec = seir_cache->get_or_insert (key, &existed); | |
| 265 if (!existed) | |
| 266 chrec = scalar_evolution_in_region (region, loop, expr); | |
| 267 return chrec; | |
| 268 } | |
| 269 | |
| 111 | 270 /* Deletes all scops in SCOPS. */ |
| 271 | |
| 272 static void | |
| 273 free_scops (vec<scop_p> scops) | |
| 274 { | |
| 275 int i; | |
| 276 scop_p scop; | |
| 277 | |
| 278 FOR_EACH_VEC_ELT (scops, i, scop) | |
| 279 free_scop (scop); | |
| 280 | |
| 281 scops.release (); | |
| 282 } | |
| 0 | 283 |
| 111 | 284 /* Transforms LOOP to the canonical loop closed SSA form. */ |
| 285 | |
| 286 static void | |
| 131 | 287 canonicalize_loop_closed_ssa (loop_p loop, edge e) |
| 0 | 288 { |
| 111 | 289 basic_block bb; |
| 290 gphi_iterator psi; | |
| 291 | |
| 292 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
|
293 |
| 111 | 294 /* Make the loop-close PHI node BB contain only PHIs and have a |
| 295 single predecessor. */ | |
| 296 if (single_pred_p (bb)) | |
| 297 { | |
| 298 e = split_block_after_labels (bb); | |
| 299 bb = e->src; | |
| 300 } | |
| 301 else | |
| 0 | 302 { |
| 111 | 303 basic_block close = split_edge (e); |
| 304 e = single_succ_edge (close); | |
| 305 for (psi = gsi_start_phis (bb); !gsi_end_p (psi); gsi_next (&psi)) | |
| 306 { | |
| 307 gphi *phi = psi.phi (); | |
| 308 use_operand_p use_p = PHI_ARG_DEF_PTR_FROM_EDGE (phi, e); | |
| 309 tree arg = USE_FROM_PTR (use_p); | |
| 0 | 310 |
| 111 | 311 /* Only add close phi nodes for SSA_NAMEs defined in LOOP. */ |
| 312 if (TREE_CODE (arg) != SSA_NAME | |
| 313 || SSA_NAME_IS_DEFAULT_DEF (arg) | |
| 314 || ! flow_bb_inside_loop_p (loop, | |
| 315 gimple_bb (SSA_NAME_DEF_STMT (arg)))) | |
| 316 continue; | |
| 317 | |
| 318 tree res = copy_ssa_name (arg); | |
| 319 gphi *close_phi = create_phi_node (res, close); | |
| 320 add_phi_arg (close_phi, arg, gimple_phi_arg_edge (close_phi, 0), | |
| 321 UNKNOWN_LOCATION); | |
| 322 SET_USE (use_p, res); | |
| 323 } | |
| 324 bb = close; | |
| 0 | 325 } |
| 326 | |
| 111 | 327 /* Eliminate duplicates. This relies on processing loops from |
| 328 innermost to outer. */ | |
| 329 for (psi = gsi_start_phis (bb); !gsi_end_p (psi); gsi_next (&psi)) | |
| 330 { | |
| 331 gphi_iterator gsi = psi; | |
| 332 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
|
333 |
| 111 | 334 /* At this point, PHI should be a close phi in normal form. */ |
| 335 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
|
336 |
| 111 | 337 /* Iterate over the next phis and remove duplicates. */ |
| 338 gsi_next (&gsi); | |
| 339 while (!gsi_end_p (gsi)) | |
| 340 if (gimple_phi_arg_def (phi, 0) == gimple_phi_arg_def (gsi.phi (), 0)) | |
| 341 { | |
| 342 replace_uses_by (gimple_phi_result (gsi.phi ()), | |
| 343 gimple_phi_result (phi)); | |
| 344 remove_phi_node (&gsi, true); | |
| 345 } | |
| 346 else | |
| 347 gsi_next (&gsi); | |
| 348 } | |
| 0 | 349 } |
| 350 | |
| 111 | 351 /* Converts the current loop closed SSA form to a canonical form |
| 352 expected by the Graphite code generation. | |
| 353 | |
| 354 The loop closed SSA form has the following invariant: a variable | |
| 355 defined in a loop that is used outside the loop appears only in the | |
| 356 phi nodes in the destination of the loop exit. These phi nodes are | |
| 357 called close phi nodes. | |
| 358 | |
| 359 The canonical loop closed SSA form contains the extra invariants: | |
| 360 | |
| 361 - when the loop contains only one exit, the close phi nodes contain | |
| 362 only one argument. That implies that the basic block that contains | |
| 363 the close phi nodes has only one predecessor, that is a basic block | |
| 364 in the loop. | |
| 365 | |
| 366 - the basic block containing the close phi nodes does not contain | |
| 367 other statements. | |
| 368 | |
| 369 - there exist only one phi node per definition in the loop. | |
| 131 | 370 |
| 371 In addition to that we also make sure that loop exit edges are | |
| 372 first in the successor edge vector. This is to make RPO order | |
| 373 as computed by pre_and_rev_post_order_compute be consistent with | |
| 374 what initial schedule generation expects. | |
| 111 | 375 */ |
| 0 | 376 |
| 377 static void | |
| 131 | 378 canonicalize_loop_form (void) |
| 0 | 379 { |
| 111 | 380 loop_p loop; |
| 381 FOR_EACH_LOOP (loop, LI_FROM_INNERMOST) | |
| 131 | 382 { |
| 383 edge e = single_exit (loop); | |
| 384 if (!e || (e->flags & (EDGE_COMPLEX|EDGE_FAKE))) | |
| 385 continue; | |
| 386 | |
| 387 canonicalize_loop_closed_ssa (loop, e); | |
| 388 | |
| 389 /* If the exit is not first in the edge vector make it so. */ | |
| 390 if (e != EDGE_SUCC (e->src, 0)) | |
| 391 { | |
| 392 unsigned ei; | |
| 393 for (ei = 0; EDGE_SUCC (e->src, ei) != e; ++ei) | |
| 394 ; | |
| 395 std::swap (EDGE_SUCC (e->src, ei), EDGE_SUCC (e->src, 0)); | |
| 396 } | |
| 397 } | |
| 398 | |
| 399 /* We can end up releasing duplicate exit PHIs and also introduce | |
| 400 additional copies so the cached information isn't correct anymore. */ | |
| 401 scev_reset (); | |
| 0 | 402 |
| 111 | 403 checking_verify_loop_closed_ssa (true); |
| 404 } | |
| 0 | 405 |
| 111 | 406 isl_ctx *the_isl_ctx; |
| 0 | 407 |
| 408 /* Perform a set of linear transforms on the loops of the current | |
| 409 function. */ | |
| 410 | |
| 411 void | |
| 412 graphite_transform_loops (void) | |
| 413 { | |
| 414 int i; | |
| 415 scop_p scop; | |
| 111 | 416 bool changed = false; |
| 417 vec<scop_p> scops = vNULL; | |
| 418 isl_ctx *ctx; | |
| 0 | 419 |
| 111 | 420 /* If a function is parallel it was most probably already run through graphite |
| 421 once. No need to run again. */ | |
| 422 if (parallelized_function_p (cfun->decl)) | |
| 0 | 423 return; |
| 424 | |
| 111 | 425 calculate_dominance_info (CDI_DOMINATORS); |
| 426 | |
| 131 | 427 /* We rely on post-dominators during merging of SESE regions so those |
| 428 have to be meaningful. */ | |
| 429 connect_infinite_loops_to_exit (); | |
| 430 | |
| 111 | 431 ctx = isl_ctx_alloc (); |
| 432 isl_options_set_on_error (ctx, ISL_ON_ERROR_ABORT); | |
| 433 the_isl_ctx = ctx; | |
| 434 | |
| 435 sort_sibling_loops (cfun); | |
| 131 | 436 canonicalize_loop_form (); |
| 111 | 437 |
| 438 /* Print the loop structure. */ | |
| 439 if (dump_file && (dump_flags & TDF_DETAILS)) | |
| 440 { | |
| 441 print_loops (dump_file, 2); | |
| 442 print_loops (dump_file, 3); | |
| 443 } | |
| 444 | |
| 145 | 445 seir_cache = new hash_map<sese_scev_hash, tree>; |
| 446 | |
| 111 | 447 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
|
448 build_scops (&scops); |
| 111 | 449 free_dominance_info (CDI_POST_DOMINATORS); |
| 0 | 450 |
| 131 | 451 /* Remove the fake exits before transform given they are not reflected |
| 452 in loop structures we end up verifying. */ | |
| 453 remove_fake_exit_edges (); | |
| 454 | |
| 0 | 455 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
|
456 { |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
457 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
|
458 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
|
459 } |
| 0 | 460 |
| 111 | 461 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
|
462 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
|
463 { |
| 111 | 464 scop->isl_context = ctx; |
| 465 if (!build_poly_scop (scop)) | |
| 466 continue; | |
| 467 | |
| 468 if (!apply_poly_transforms (scop)) | |
| 469 continue; | |
| 0 | 470 |
| 111 | 471 changed = true; |
| 145 | 472 if (graphite_regenerate_ast_isl (scop) |
| 473 && dump_enabled_p ()) | |
| 111 | 474 { |
| 131 | 475 dump_user_location_t loc = find_loop_location |
| 111 | 476 (scops[i]->scop_info->region.entry->dest->loop_father); |
| 477 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, loc, | |
| 478 "loop nest optimized\n"); | |
| 479 } | |
|
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
|
480 } |
| 0 | 481 |
| 145 | 482 delete seir_cache; |
| 483 seir_cache = NULL; | |
| 484 | |
| 111 | 485 if (changed) |
| 486 { | |
| 487 mark_virtual_operands_for_renaming (cfun); | |
| 488 update_ssa (TODO_update_ssa); | |
| 489 checking_verify_ssa (true, true); | |
| 490 rewrite_into_loop_closed_ssa (NULL, 0); | |
| 491 scev_reset (); | |
| 492 checking_verify_loop_structure (); | |
| 493 } | |
| 494 | |
| 495 if (dump_file && (dump_flags & TDF_DETAILS)) | |
| 496 { | |
| 497 loop_p loop; | |
| 498 int num_no_dependency = 0; | |
| 499 | |
| 500 FOR_EACH_LOOP (loop, 0) | |
| 501 if (loop->can_be_parallel) | |
| 502 num_no_dependency++; | |
| 503 | |
| 504 fprintf (dump_file, "%d loops carried no dependency.\n", | |
| 505 num_no_dependency); | |
| 506 } | |
| 507 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
508 free_scops (scops); |
| 111 | 509 the_isl_ctx = NULL; |
| 510 isl_ctx_free (ctx); | |
| 511 | |
| 512 if (changed) | |
| 513 { | |
| 514 cleanup_tree_cfg (); | |
| 515 profile_status_for_fn (cfun) = PROFILE_ABSENT; | |
| 516 release_recorded_exits (cfun); | |
| 517 tree_estimate_probability (false); | |
| 518 } | |
| 0 | 519 } |
| 520 | |
| 111 | 521 #else /* If isl is not available: #ifndef HAVE_isl. */ |
| 0 | 522 |
| 111 | 523 static void |
| 0 | 524 graphite_transform_loops (void) |
| 525 { | |
| 111 | 526 sorry ("Graphite loop optimizations cannot be used (isl is not available)."); |
| 0 | 527 } |
| 528 | |
| 529 #endif | |
| 111 | 530 |
| 531 | |
| 532 static unsigned int | |
| 533 graphite_transforms (struct function *fun) | |
| 534 { | |
| 535 if (number_of_loops (fun) <= 1) | |
| 536 return 0; | |
| 537 | |
| 538 graphite_transform_loops (); | |
| 539 | |
| 540 return 0; | |
| 541 } | |
| 542 | |
| 543 static bool | |
| 544 gate_graphite_transforms (void) | |
| 545 { | |
| 546 /* Enable -fgraphite pass if any one of the graphite optimization flags | |
| 547 is turned on. */ | |
| 548 if (flag_graphite_identity | |
| 549 || flag_loop_parallelize_all | |
| 550 || flag_loop_nest_optimize) | |
| 551 flag_graphite = 1; | |
| 552 | |
| 553 return flag_graphite != 0; | |
| 554 } | |
| 555 | |
| 556 namespace { | |
| 557 | |
| 558 const pass_data pass_data_graphite = | |
| 559 { | |
| 560 GIMPLE_PASS, /* type */ | |
| 561 "graphite0", /* name */ | |
| 562 OPTGROUP_LOOP, /* optinfo_flags */ | |
| 563 TV_GRAPHITE, /* tv_id */ | |
| 564 ( PROP_cfg | PROP_ssa ), /* properties_required */ | |
| 565 0, /* properties_provided */ | |
| 566 0, /* properties_destroyed */ | |
| 567 0, /* todo_flags_start */ | |
| 568 0, /* todo_flags_finish */ | |
| 569 }; | |
| 570 | |
| 571 class pass_graphite : public gimple_opt_pass | |
| 572 { | |
| 573 public: | |
| 574 pass_graphite (gcc::context *ctxt) | |
| 575 : gimple_opt_pass (pass_data_graphite, ctxt) | |
| 576 {} | |
| 577 | |
| 578 /* opt_pass methods: */ | |
| 579 virtual bool gate (function *) { return gate_graphite_transforms (); } | |
| 580 | |
| 581 }; // class pass_graphite | |
| 582 | |
| 583 } // anon namespace | |
| 584 | |
| 585 gimple_opt_pass * | |
| 586 make_pass_graphite (gcc::context *ctxt) | |
| 587 { | |
| 588 return new pass_graphite (ctxt); | |
| 589 } | |
| 590 | |
| 591 namespace { | |
| 592 | |
| 593 const pass_data pass_data_graphite_transforms = | |
| 594 { | |
| 595 GIMPLE_PASS, /* type */ | |
| 596 "graphite", /* name */ | |
| 597 OPTGROUP_LOOP, /* optinfo_flags */ | |
| 598 TV_GRAPHITE_TRANSFORMS, /* tv_id */ | |
| 599 ( PROP_cfg | PROP_ssa ), /* properties_required */ | |
| 600 0, /* properties_provided */ | |
| 601 0, /* properties_destroyed */ | |
| 602 0, /* todo_flags_start */ | |
| 603 0, /* todo_flags_finish */ | |
| 604 }; | |
| 605 | |
| 606 class pass_graphite_transforms : public gimple_opt_pass | |
| 607 { | |
| 608 public: | |
| 609 pass_graphite_transforms (gcc::context *ctxt) | |
| 610 : gimple_opt_pass (pass_data_graphite_transforms, ctxt) | |
| 611 {} | |
| 612 | |
| 613 /* opt_pass methods: */ | |
| 614 virtual bool gate (function *) { return gate_graphite_transforms (); } | |
| 615 virtual unsigned int execute (function *fun) { return graphite_transforms (fun); } | |
| 616 | |
| 617 }; // class pass_graphite_transforms | |
| 618 | |
| 619 } // anon namespace | |
| 620 | |
| 621 gimple_opt_pass * | |
| 622 make_pass_graphite_transforms (gcc::context *ctxt) | |
| 623 { | |
| 624 return new pass_graphite_transforms (ctxt); | |
| 625 } | |
| 626 | |
| 627 |